Finding solutions to the date puzzle using APL
The problem
Karl has a puzzle with 8 pieces that almost covers a board with 43 slots, leaving 2 uncovered. Each slot has either the name of a month, or a day number between 1 and 31. The goal is to place all the pieces on the board every day, so that the two slots that aren't covered shows the current date.
We decided to write a program to find solutions.
The program
The program is written using Dyalog APL, and it finds all possible solutions (for all days) in about 30 seconds on my laptop.
The Solve function finds all solutions and stores them in the global variable SOLUTIONS. The Date function finds all solutions for a given date (by finding all possible solutions and filtering them).
Solve
Solve;board;combine;pieces;size;variants;⎕IO
⎕IO←0
size←7 7
board←size⍴' '
board[0 1;6]←'x'
board[6;3 4 5 6]←'x'
board←,board
variants←{
v←,⍵∘{size↑⍵↓(-size)↑⍺}¨⍳1+size-⍴⍵
v,←⌽¨v
v←∪(⌽⍤⍉¨v),(⍉⍤⌽¨v),(⌽⍤⊖¨v),v
v←↑,¨v
v⌿⍨~∨/v∧⍤1⊢board≠' '
}
pieces←⊂4 2⍴1 1 0 1 0 1 0 1
pieces,←⊂3 2⍴1 1 1 1 0 1
pieces,←⊂3 3⍴0 1 1 0 1 0 1 1 0
pieces,←⊂4 2⍴1 0 1 1 0 1 0 1
pieces,←⊂3 3⍴1 0 0 1 0 0 1 1 1
pieces,←⊂2 3⍴1 1 1 1 0 1 1
pieces,←⊂2 3⍴1 1 1 1 1 1
pieces,←⊂2 4⍴0 1 0 0 1 1 1 1
pieces←variants¨pieces
combine←{
(char places)←⍺
boards←⍵
⊃⍪⌿(boards≠' ')∘{n←boards⌿⍨~∨/⍺(∧⍤1)⍵ ⋄ n[;⍸⍵]←char ⋄ n}¨↓places
}
SOLUTIONS←size∘⍴¨↓⊃combine⌿(↓⍉↑'ABCDEFGH'pieces),⊂⍉⍪board
Date
solutions←Date(month day);dindex;mindex;⎕IO
⎕IO←1
:If ~month∊⍳12
'Invalid month'⎕SIGNAL 11
:EndIf
:If ~day∊⍳31
'Invalid day'⎕SIGNAL 11
:EndIf
⎕IO←0
:If 0=⎕NC'SOLUTIONS'
⎕←'Finding all solutions...'
Solve
⎕←'Done :)'
:EndIf
mindex←2 6⊤month-1
dindex←2 0+5 7⊤day-1
solutions←SOLUTIONS⌿⍨{' '≡⍵[mindex dindex]}¨SOLUTIONS
Example run
Date 10 6
┌───────┬───────┬───────┬───────┬───────┬───────┬───────┐
│HHHHBBx│GGAAAAx│GGAAAAx│GGAAAAx│GGAAAAx│GGAAAAx│GGAAAAx│
│DDH BBx│GGF FAx│GGF FAx│GGA DDx│GGA DDx│GGA DDx│GGA DDx│
│CDDDB A│GGFFF H│GGFFF H│GGDDD C│GGDDD C│GGDDD H│GGDDD H│
│CCCAAAA│EEECBHH│EEEDBHH│HHHHCCC│HEEECCC│CEEEFFH│CCBBFFH│
│EFCFGGG│ECCCBBH│ECCDBBH│EFHFCBB│HFFECBB│CCCEFHH│ECBBFHH│
│EFFFGGG│ECDDBBH│ECDDBBH│EFFFBBB│HHFEBBB│BBCEFFH│ECCBFFH│
│EEExxxx│DDDxxxx│CCDxxxx│EEExxxx│HFFxxxx│BBBxxxx│EEExxxx│
└───────┴───────┴───────┴───────┴───────┴───────┴───────┘
Each nested array represents one solution. An x indicates the parts of the board that doesn't exist, and each piece is represented by an uppercase letter from A to H. So, October 6th has different solutions :)