kdb programming challenge – countdown numbers game

Matt Doherty kdb+ 2 Comments

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…

Richard Whiteley


The late Richard “Twice Nightly” Whiteley.

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!

Matt Dohertykdb programming challenge – countdown numbers game

Comments 2

  1. Jose Cambronero

    a brute force approach, would be interested in seeing possible optimizations (or a smart way of doing this overall)

    OPS:(*;-;+)

    cn:{(cross/)x#enlist y}; //cross-n times

    p:{x {raze y,/:’x except/:y}[ix;]/[-1+count x;ix:til count x]} //all permutations of a list

    //takes a list of operators and operands, and applies a lambda z, to a sublist formed by an operator and 2 operands. The results is put back into the list of operands. Continues until only 1 operand is left.

    traverse:{last last {(1_o; (x (first o:y 0),2 sublist n),2 _ n:y 1)}[z;]/[{1< count last x};(x;y)]}

    exists:{any y=traverse[;;eval] ./: (0,no) cut/:cn[no:-1+count x;OPS] cross p x}

    print:{`$ssr/[“({e673f69332cd905c29729b47ae3366d39dce868d0ab3fb1859a79a424737f2bd}a1 {e673f69332cd905c29729b47ae3366d39dce868d0ab3fb1859a79a424737f2bd}op {e673f69332cd905c29729b47ae3366d39dce868d0ab3fb1859a79a424737f2bd}a2)”;(“{e673f69332cd905c29729b47ae3366d39dce868d0ab3fb1859a79a424737f2bd}op”;”{e673f69332cd905c29729b47ae3366d39dce868d0ab3fb1859a79a424737f2bd}a1″;”{e673f69332cd905c29729b47ae3366d39dce868d0ab3fb1859a79a424737f2bd}a2″);string x]}

    shownearest:{traverse[ ; ;print] . first a where d=min d:abs y-traverse[;;eval] ./: a:(0,no) cut/:cn[no:-1+count x;OPS] cross p x}

    q)exists[1 2 4; 12]

    1b

    q)exists[1 2 4; 11]

    0b

    q)shownearest[1 2 4; 12]

    `((1 + 2) * 4)

  2. Pingback: Let the countdown begin

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax