kdb programming challenge – number bases

In systems of numbers the radix or base is the number of unique digits or symbols that are used to represent numbers. By far the most well known and widely used is the decimal system, which uses the ten digits from 0 through 9 (largely because – much to William Shatner’s surprise – we have 10 fingers).

My. Only intention. In. Speaking this way. Is. To. Make absolutely sure. That. You! The listening audience. Are. Able to. Hear my words! Clearly.

Some other handy bases include binary (radix of 2) since it’s the language most computers speak, and sexagesimal (radix of 60) which is used for time and circular coordinates because 60 is very divisible.

So, the challenge this time is to write a base number converter that accepts any positive integer (in base 10, like normal) and a base to convert to as the two arguments, and returns a list which is the digits of the number in the new base. The digits themselves can be in base 10, no need to start using “A-F” etc. The answer should never return zeros at the start; we don’t typically write two as 000002.

So for example some numbers in binary:

q) f[15;2]
1 1 1 1
q) f[16;2]
1 0 0 0 0

Or in some other bases:

q) f[123;6]
3 2 3
q) f[123;7]
2 3 4
q) f[123456;60]
34 17 36

This problem will be the first in a short series involving number bases and some hopefully interesting related topics.

Show Solution

There’s definitely more than one nice solution to this problem, so I’ll show you two of the best from our office. The first (courtesy of Kent Lee) makes very nice use of recursion to divide by successively bigger powers of the radix until we can’t divide any further:

f:{$[x<y;(),x;.z.s[x div y;y],x mod y]}

The second (straight from the mind of Andrew Steele), takes a different approach and makes very clever use of iterate to solve the problem:

f:{1_reverse div[;y]\[x]mod y}

This one also wins the “who can use the least characters” competition, despite the inclusion of reverse! Very impressive. I’m sure there are other nice ways to do this too, as always feel free to post your answers in the comments!

Remember – you can’t beam through a forcefield, so don’t try it.

Comments 12

Akash

2014/10/04 at 18:51

using scan adverb
f:{[n;b]reverse mod[({floor {e673f69332cd905c29729b47ae3366d39dce868d0ab3fb1859a79a424737f2bd}[y;x]}[b;])[{x>1};n];b]}

using While loop
f:{[n;b]res:();while[n>=1;res,:mod[n;b];n:floor {e673f69332cd905c29729b47ae3366d39dce868d0ab3fb1859a79a424737f2bd}[n;b]];:reverse res}

Post
Author

Matt Doherty
2014/10/08 at 13:32

Hey Akash,

Thanks for contributing! The first solution doesn’t seem to work, maybe there’s a typo in there? I don’t see a scan anywhere.

Reply
1. Akash
  2014/10/12 at 13:51
  
  yes.there is.
  f:{[n;b]1_reverse mod[({floor {e673f69332cd905c29729b47ae3366d39dce868d0ab3fb1859a79a424737f2bd}[y;x]}[b;])\[{x>=1};n];b]}
  
  Reply
  1. Post
    Author
    
    Matt Doherty
    2014/10/13 at 10:36
    
    Cool, looks good. Cheers Akash!
    
    Reply

Pingback: Challenge Series, Part 1, Number Bases

Jose Cambronero

2014/10/13 at 23:35

here is my solution:

q)f:{last flip (x;0){$[a>=y;a mod y;a],(a:first x) div y}\`int$reverse y xexp til 1+floor log[x]{e673f69332cd905c29729b47ae3366d39dce868d0ab3fb1859a79a424737f2bd}log y}

WooiKent Lee
2014/10/20 at 10:03

Hey Jose, just to let you know you can use x xlog y to substitute log[x]{e673f69332cd905c29729b47ae3366d39dce868d0ab3fb1859a79a424737f2bd}log y 🙂

Reply
WooiKent Lee
2014/10/20 at 10:05

Sorry it should be y xlog x in your case 😀

Reply

Pingback: kdb programming challenge - square-free sequences - AquaQ Analytics

Karl

2017/05/18 at 15:47

Less characters again:

f:{1_(|)div[;y][x]mod y}

givan

2018/08/18 at 04:37

How about this

f:{n:{if[(floor x{e673f69332cd905c29729b47ae3366d39dce868d0ab3fb1859a79a424737f2bd}y)=0;:z,x mod y];z:z,x mod y; n[floor x{e673f69332cd905c29729b47ae3366d39dce868d0ab3fb1859a79a424737f2bd}y;y;z]};:reverse n[x;y;()]}

wimble

2019/04/05 at 00:35

The simplest solution is

f:{y vs x}


q)f[15;2]

1 1 1 1
q)f[16;2]

1 0 0 0 0
q)f[123;6]

3 2 3
q)f[123;7]

2 3 4

q)f[123456;60] 34 17 36

Comments 12

Leave a Reply Cancel reply