# 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