# 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 figure find solutions.

## The program

The program is written using Dyalog APL, and it finds all possible solutions (for all days) in about 14 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 7 12
	┌───────┬───────┬───────┬───────┐
	│CCAAAAx│CCFFFHx│AACEEEx│AACEEEx│
	│ CAHBBx│ CFDFHx│ ACCCEx│ ACCCEx│
	│DCCHBBB│BCCDHHE│DABBCEH│DAGGCEB│
	│DDHH GG│BBDD HE│DABB HH│DAGG BB│
	│EDFHFGG│BBDAEEE│DDBGGGH│DDGGHBB│
	│EDFFFGG│GGGAAAA│FDFGGGH│FDFHHHH│
	│EEExxxx│GGGxxxx│FFFxxxx│FFFxxxx│
	└───────┴───────┴───────┴───────┘

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, today has 4 different solutions :)


[1]: https://images.pmikkelsen.com/date-puzzle.png