Day 4: Giant Squid
Spoilers ahead: this post contains solutions
The bingo boards are nicely readable in the text file, but we shall find them more tractable as vectors.
q)q:read0`:test4.txtq)nums:valuefirstq q)showboards:valueeach" "sv'(where0=counteachq)cutq22131711082234242191416761031851122015193150222918131751987252320111024414211612614211724410161591918823262022111365201237
A perfectly sensible looping approach would follow real life. We would call each number and see if any board has won.
Were not going to do that. Were going to call all the numbers and see where the wins occur.
s:(or\')boards=/:\:nums / states: call all the numbers in turn
The derived function =/:\: (Equal Each Right Each Left) gives us a cross-product on the Equal operator. The list boards=/:\:nums has an item for each board. Each item is a boolean matrix: a row for each of the called numbers, the columns corresponding to the board numbers. Heres the first board with 1s flagging the numbers as they are called in turn.
q)firstboards=/:\:nums0000000000000010000000000b0000000010000000000000000b0000000000010000000000000b0000000000000000000100000b0001000000000000000000000b0010000000000000000000000b..
Of course, once a number is called, it stays called.
q)(or\)firstboards=/:\:nums0000000000000010000000000b0000000010000010000000000b0000000010010010000000000b0000000010010010000100000b0001000010010010000100000b0011000010010010000100000b..
That is just the first board. We want the same for every board.
s:(or\')boards=/:\:nums / states: call all the numbers in turn
How to tell if a board has won? Here is the state of board 0 after 9 numbers have been called.
q)s[0;9;]0011101110011010000100000b
Has it won?
q)5cuts[0;9;]00111b01110b01101b00001b00000b
Clearly not. That would require all 1s on at least one row. Or a column.
q)anyalleach{x,flipx}5cuts[0;9;]0b
Now we can flag the wins.
q)showw:{anyalleach{x,flipx}5cutx}''[s]000000000000011111111111111b000000000000001111111111111b000000000001111111111111111b
From this we can see that the third board is the first to win and the second is the last to win. Also that they win on (respectively) the 11th and 14th numbers called.
q)sumeachnotw131411i
So the state of the winning board is s[2;11;]
q)5cuts[2;11;]11111b00010b00100b01001b11001bq)sumboards[2]wherenots[2;11;] / sum the unmarked numbers188q)nums[11]*sumboards[2]wherenots[2;11;] / board score4512
That makes our complete solution:
q:read0`:day4.txtnums:valuefirstqboards:valueeach" "sv'(where0=counteachq)cutqs:(or\')boards=/:\:nums / states: call all the numbers in turnw:sumeachnot{anyalleachb,flipb:5cutx}''[s] / find winsbs:{nums[x]*sumboards[y]wherenots[y;x;]} / score for board y after xth numbera[`$"4-1"]:bs.{m,x?m:minx} w / winning board scorea[`$"4-2"]:bs.{m,x?m:maxx} w / losing board score
This is a nice example of the overcomputing characteristic of vector languages. Clearly, an efficient algorithm would stop when it reached the first win. Or, for Part 2, the last win.
But sometimes it is convenient to calculate all the results and search them. And, with vector operations, sometimes it is faster as well.