kdb programming challenge – countdown numbers game

This weeks challenge is in honour of the the late Richard Whiteley, who in his time clocked up more hours on British TV screens than anyone else alive! Consonant please, Carol…

Puzzle 4 – Countdown Numbers Game

The challenge is based on the countdown numbers game and is a little more difficult than previous weeks, so we’ve split it into a normal and a difficult version. In the numbers round the contestant receives six random numbers, and a random three-digit target which is generated by a machine affectionately known as CECIL (Countdown Electronic Computer In Leeds). The contestants then have thirty seconds to get as near to the target as possible by combining the six numbers selected using addition, subtraction, multiplication and division. A number can be used as many times as it appears. Fractions are not allowed—only positive integers may be used at any stage of the calculation.

Normal Version

Write a function of the form:

f:{[n;t]...}

where n is a list of the numbers available, and t is the target number. The function should return a single boolean value indicating if it is possible to get to the target number using the 6 numbers and operations +,-,x (not div, as it makes things a little more tricky). For example:

q)f[1 2 4;12]
1b
q)f[1 2 4;11]
0b

Hard Version

Write a function of the same form:

f:{[n;t]...}

where n is the list of the numbers available, t is the target number. The function should return a string which shows how the target can be calculated from the numbers. Optionally, the function can return all possible solutions, and/or if the target is not possible, the closest possible result.

For example:

q)f[75 3 5 7 8 2;478]
"((((75-8)+2)*7)-5)"

This week we are only providing the solution for the easy version – a solution for the hard version will be covered in a follow up blog post. We’ll post some of our solutions in the comments, feel free to comment with a solution of your own!

[showhide type=”post” more_text=”Show Solution” less_text=”Solution” hidden=”yes”]

So, our solution looks like:

f:{y in raze {{value[3#x],3_x}each raze(+;-;*),\:/:raze x@\:{t,'x except/: t:raze x,/:'x(_)/:x}til count first x}/[count[x]-1;enlist x]}

So let’s dig in a little to how that nasty looking piece of code works. The most important part is the inner function which looks for all the possible pairs in the lists supplied, and uses each operator on each pair. It returns a list of lists, each one shorter than the original list with the results of these operations and the remaining unused numbers. For example:

q){{value[3#x],3_x}each raze(+;-;*),\:/:raze x@\:{t,'x except/: t:raze x,/:'x(_)/:x}til count first x}enlist 1 2 3
3  3
-1 3
2  3
4  2
-2 2
3  2
3  3
1  3
2  3
5  1
-1 1
6  1
4  2
2  2
3  2
5  1
1  1
6  1

The key part here is that we then use a scan to pass this list of lists back into the same function and repeat the process, until we have a list of single numbers, each of which is a number we can make using the initial list n. For example:

q)asc distinct raze {{value[3#x],3_x}each raze(+;-;*),\:/:raze x@\:{t,'x except/: t:raze x,/:'x(_)/:x}til count first x}/[2;enlist 1 2 3]
-5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9

Then we simply check this list for our target number!

[/showhide]