Jamie Grant
[image src=”http://www.gchq.gov.uk/SiteCollectionImages/grid-shading-puzzle.jpg” href=”http://www.gchq.gov.uk/press_and_media/news_and_features/Pages/Directors-Christmas-puzzle-2015.aspx” alt=”GCHQ Christmas Card Puzzle”]
[custom_headline type=”center” style=”margin-top: 0;” level=”h4″ looks_like=”h4″ accent=”true”]Introduction[/custom_headline]
Rikesh posted a link to the GCHQ Christmas Card Puzzle on the K4 listbox, so I decided to take a look. Described as a grid shading problem, it consists of a 25 X 25 grid, on which a number of cells are shaded black. The sequence of numbers against each row and column specifies the length of runs of unbroken black squares in the line, which may be separated by one or more white squares.
We’re going to model this problem by thinking of each cell as being in one of 3 states – known black, known white, and unknown. Given the inputs in the problem, using black/white/grey for the three states, the current state of the grid is:
[image type=”thumbnail” src=”https://aquaq.co.uk/wp-content/uploads/2015/12/step1-e1450045545319.png” alt=”Initial State”]
Our first task is to try and use the information provided about the rows and columns to work out all valid lines which satisfy those constraints. It is helpful to think of the line consisting of N black sections, with N+1 white sections between and around them.
[code]
blacks: | B1 | | B2 | … | Bn-1 | | Bn |
whites: | W1 | | W2 | | … | | Wn | | Wn+1 |
[/code]
The first and last white sections may have zero length, while the sections which separate the black ones must be at least of length one.
[custom_headline type=”center” style=”margin-top: 0;” level=”h4″ looks_like=”h4″ accent=”true”]Permutations[/custom_headline]
[code]
p:{$[x>1;raze n,/:’.z.s'[x-1;y-n:til 1+y];enlist x#y]}
[/code]
The function p returns all the possible distributions of y items across x slots, for example, if we have 2 items and 3 slots:
[code]
q)p[3;2]
0 0 2
0 1 1
0 2 0
1 0 1
1 1 0
2 0 0
[/code]
We can use this function to generate the different possible white run lengths, since we know how many there should be (n+1), and we know the total number of white squares by subtracting the total number of black squares from the grid dimension.
[custom_headline type=”center” style=”margin-top: 0;” level=”h4″ looks_like=”h4″ accent=”true”]White run sizes[/custom_headline]
[code]
w:{(0,#[n-1;1],0)+/:p[1+n;y+1-sum[x]+n:count x]}
[/code]
The function w returns all possible white run lengths given the black runs (x) and the line length (y). It creates an initial list with the minimum values – zero at each end and one otherwise, then adds this to each permutation of the remaining whites, of which there are line length (y) less the ones already allocated (n-1) and the total number of blacks (sum x).
[custom_headline type=”center” style=”margin-top: 0;” level=”h4″ looks_like=”h4″ accent=”true”]Possible lines[/custom_headline]
[code]
j:{raze each (w[x;y]#”0b),’\:(x,0)#’1b}
[/code]
With all these combinations, the next step is to reconstitute the run lengths into regular lines of 25 booleans – true for black and false for white. The function j does this. The example shown is using the 5th row of the grid, which was chosen because there are only a few valid lines for that input. Some rows and columns have more than 10,000 valid line outputs.
q)j[1 3 1 5 2 1 3 1;25]
1011101011111011010111010b
1011101011111011010111001b
1011101011111011010011101b
1011101011111011001011101b
1011101011111001101011101b
1011101001111101101011101b
1011100101111101101011101b
1001110101111101101011101b
0101110101111101101011101b
[custom_headline type=”center” style=”margin-top: 0;” level=”h4″ looks_like=”h4″ accent=”true”]Filtering[/custom_headline]
[code]
m:{x~x and y}/:
[/code]
Given all the possibilities, we now want to use the information we already have about the line, to filter out potential lines which don’t fit the known values. We can use an integer matrix to hold the grid state – +1 for known black, 0 for unknown and -1 for known white. As an example, we’ll look at the 17th row in the matrix, one of the ones for which some known blacks are marked in the problem description.
[code]
q)x[16]>0
0000001000010000100010000b
q)count j[3 1 1 1 1 5 1;25]
1716
[/code]
For this row, there are 1716 potential lines which would fit the specified black run lengths. We can use the known blacks to filter out impossible candidates with the function m.
[code]
q)count where m[x[16]>0;j[3 1 1 1 1 5 1;25]]
71
[/code]
Only 71 out of 1716 have all four given black squares in the correct place, so we can throw away the rest and see if any other inferences can be made from the new, smaller set.
At this point it’s appropriate to point out that if we have known white values, we can filter for those using the same function:
[code]
q)count where m[x[16]<0;not j[3 1 1 1 1 5 1;25]]
1716
[/code]
We don’t have any known whites to start, so this filter can’t help us restrict the set, but as we gain information about the grid, this check will help us reach the solution.
[custom_headline type=”center” style=”margin-top: 0;” level=”h4″ looks_like=”h4″ accent=”true”]Line state[/custom_headline]
[code]
f:{all[b]-all not b:r where m[y<0;not r] and m[y>0;r:j[x;count y]]}
[/code]
When we use our filters to reduce the full set of possibilities to ones which are consistent with the currnt state, we then use the results to see whether any more conclusions can be drawn. If all the possible lines have a black square at position N, which was previously unknown, then we can mark that square as a known black, likewise for squares where all remaining lines have a white at that position.
For an example, we’ll look at the 9th row:
[code]
q)h 8
1 2 3 1 1 3 1 1 2
q)count j[h 8;25]
55
q)x[8]
0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0
q)count where m[x[8]>0;j[h 8;25]]
12
q)r where m[x[8]>0] r:j[h 8;25]
1011011100101011101010110b
1011011100101011101010011b
1011011100101011101001011b
1011001110101011101010110b
1011001110101011101010011b
1011001110101011101001011b
1001101110101011101010110b
1001101110101011101010011b
1001101110101011101001011b
0101101110101011101010110b
0101101110101011101010011b
0101101110101011101001011b
[/code]
There are 55 possible configurations, restricted to 12 which match the puzzle input. Looking at the result, there is a section in the middle which is common to all, so we should be able to return a new known state of the row with information which wasn’t in the input.
[code]
q)a:all r where m[x[8]>0] r:j[h 8;25] / all true
q)b:all not r where m[x[8]>0] r:j[h 8;25] / all false
q)a
0001001100101011101000010b
q)b
0000000001010100010100000b
q)a-b
0 0 0 1 0 0 1 1 0 -1 1 -1 1 -1 1 1 1 -1 1 -1 0 0 0 1 0i
[/code]
Combining our permutation function, our two filters, and calculating the new state, we have function f, above.
[custom_headline type=”center” style=”margin-top: 0;” level=”h4″ looks_like=”h4″ accent=”true”]Rows and columns[/custom_headline]
[code]
g:{flip f'[y;flip f'[x;z]]}
[/code]
Our function f takes a line constraint and line state, and returns the new line state. If we want to run f against each row, the resulting state looks like:
[image type=”thumbnail” src=”https://aquaq.co.uk/wp-content/uploads/2015/12/firstpass-e1450054975832.png” alt=”First pass”]
We also have information about the black run sequences down the columns. The function g combines a vertical scan down the rows with a scan across the columns on the row result by transposing the matrix. After scanning down the rows then across columns, we have the following state:
[image type=”thumbnail” src=”https://aquaq.co.uk/wp-content/uploads/2015/12/step2-e1450055617488.png” alt=”First full scan”]
[custom_headline type=”center” style=”margin-top: 0;” level=”h4″ looks_like=”h4″ accent=”true”]Solution[/custom_headline]
[code]
g[h;v]/[x]
[/code]
To find a solution, our function g is called successively with the results of the previous run, until it converges on a result
[image type=”thumbnail” src=”https://aquaq.co.uk/wp-content/uploads/2015/12/output_TGJ5e11.gif” alt=”Iterating to reach solution”]
The result is a QR code which can be scanned by a QR code app on a mobile device to produce a link which leads to the next stage of the GCHQ Christmas Puzzle. To produce a QR code which you can scan, download and run the q script, and open the qr.html file which it produces.
[icon type=”file-text-o”]
gchq.q
Share this: