1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
# 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.
[![A picture of the puzzle][1]][1]
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 :)
[1]: https://images.pmikkelsen.com/date-puzzle.png
|