~kris/krisyotam.net (main): reference/pmikkelsen/pmikkelsen.com/APL-and-J/Date-puzzle-solver.html

<!DOCTYPE HTML>
<html>
<head>

    <title>APL-and-J - Date puzzle solver</title>
    <style media="screen, handheld">
body { display: flex; flex-wrap: wrap; font-family: sans;}
header { flex-basis: 100%; flex-shrink: 0; }
article { flex-basis: 60%; padding-left: 1em; }
footer { flex-basis: 100%; flex-shrink: 0; }
header nav { display: flex; justify-content: space-between; }
nav a, header a { text-decoration: none ; color: inherit; }
header h1 span { margin-left: 1em; font-size: 50%; font-style: italic; }
.mainContent > nav { flex-basis: content; padding-right: 1vw; min-width: 16em; }
nav ul { display: flex; flex-direction: column; list-style-type: none; list-style-position: outside; padding-left: 0;  }
nav li ul { padding-left: 0.6em }
footer { display: flex; justify-content: space-between; }

/* cut here to leave vanity behind */

body { margin:0; padding: 0; font-size: 84%; font-family: Helvetica, Verdana, Arial, 'Liberation Sans', FreeSans, sans-serif; }
a { text-decoration: none; color: }
a:hover { text-decoration: underline; }
.thisPage { color: black; }

/* header and top bar */
header nav { background-color: rgb(100,135,220); color: white; padding: 0.3em; border-bottom: 2px solid black; font-size: 91%; }
header h1 { background-color: #ff6d06; color: black; margin: 0; border-bottom: 2px solid black; font-weight: normal; padding: 0.25ex; font-size: 233%; }
header a:hover { text-decoration: none; }

/* sidebar */
.mainContent > nav { border-right: 1px solid #ddd; padding: 0;  } 
.mainContent > nav > div { border-bottom: 1px solid #ddd; } 
.mainContent > nav > div a { color: rgb(0, 102, 204); display: block; text-transform: capitalize; font-weight: bold; padding: 0.25em 1ex 0.25em 2mm; font-size: 102%} 
.mainContent > nav > div a:hover { color: white; background-color: rgb(100,135,220); border-left: black solid 0.2em; text-decoration: none; }
.mainContent > nav > div p { font-weight: bold; margin: 0 0 0.5em 2mm; padding: 1em 0 0 0; }

/* main copy */
article { padding: 0.5ex 0 5vh 1vw;  }
article h1, article h2 { color: rgb(0,102,204); font-weight: bold; margin: 2em 0 0 0; border-bottom: 2px solid rgb(0,102,204); }
article h3, article h4, article h5 { color: rgb(0,102,204); font-weight: bold; margin: 2em 0 0 0; }
article h6, article h7, article h8 { color: rgb(0,102,204); font-weight: bold; margin: 2em 0 0 0; }
article a { color: rgb(0,102,204); }
article a:hover { color:  rgb(100,135,220); }
article pre { font-size: 1.2em; }

/* footer */
footer { color: white; background-color: rgb(100,135,220); }
footer a { color: inherit; }
footer div { padding: 1em; }

/* tables */
table { border: 1px solid rgba(128,128,128,0.5); padding: 0; }
th { color: white; background-color: rgb(100,135,220); }
tr:nth-child(odd) { background-color: rgba(128,128,128,0.1)  }

/* modifications */
img {
	max-width: 100%;
	border: 1px solid black;
}

body {
	
}

header h1 {
	background-color: #c2d2c6;
}

html {
	font-size: 1.2em;
}

header nav, footer {
	background-color: #442a13;
}

code > pre {
	border: 2px solid #442a13;
	background-color: #c2d2c6;
	width: max-content;
	padding: 0 0.5em;
}

.mainContent > nav > div a, article a:hover {
	color: #442a13;
}

.mainContent > nav > div a:hover {
	color: #442a13;
	background-color: #c2d2c6;
}

article h1, article h2 {
	color: #c48f3b;
	border-bottom: 2px solid #442a13;
}

article a, .thisPage, footer, header nav {
	color: #c48f3b;
}

footer {
	padding: 0.5em;
	flex-shrink: 1;
	flex-basis: unset;
}

header {
	flex-basis: unset;
}

html {
	display: flex;
	min-height: 100%;
}

body {
	flex-direction: column;
	flex: 1;
	background-color: #e3dfd7;
}

.mainContent {
	display: flex;
	flex-grow: 1;
}    </style>
    <link rel="shortcut icon" href="https://images.pmikkelsen.com/favicon.ico" type="image/vnd.microsoft.icon">
    <meta charset="UTF-8">
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 



    

</head>
<body>

<header>
    <nav>
    <div class="left">
		<a href="https://pmikkelsen.com">notes</a> |
		<a href="https://git.pmikkelsen.com">git</a> |
		<a href="https://images.pmikkelsen.com">images</a> |
		<a href="https://files.pmikkelsen.com">files</a> |
		<a href="https://prolog.pmikkelsen.com">PProlog</a> |
		<a href="https://apl.pmikkelsen.com">APL9</a> |
		<a href="https://aplwc.org">aplwc</a>
    </div>

    <div class="right">
		<a href="https://git.sr.ht/~pmikkelsen">sourcehut</a> |
		<a href="https://9front.org">9front</a> |
		<a href="https://openbsd.org">OpenBSD</a> |
		<a href="https://dyalog.com">Dyalog</a>
    </div>

    </nav>
    <h1><a href="../index.html">Peter&#39;s website <span id="headerSubTitle">- random notes</span></a></h1>
</header>

<div class=mainContent>
    <nav id="side-bar">
        <div>
<ul>
<li><a href="index.html" class="thisPage">&raquo;<i> APL and J/</i></a></li>
<li><ul>
<li><a href="Advent-of-code-2020-in-APL/index.html">&rsaquo; Advent of code 2020 in APL/</a></li>
<li><a href="Date-puzzle-solver.html" class="thisPage">&raquo;<i> Date puzzle solver</i></a></li>
<li><a href="Designing_an_APL_for_9front.html">&rsaquo; Designing an APL for 9front</a></li>
<li><a href="hello_world_apl_and_j.html">&rsaquo; hello world apl and j</a></li>
</ul></li>
<li><a href="../OpenBSD/index.html">&rsaquo; OpenBSD/</a></li>
<li><a href="../contact.html">&rsaquo; contact</a></li>
<li><a href="../facts/index.html">&rsaquo; facts/</a></li>
<li><a href="../haskell/index.html">&rsaquo; haskell/</a></li>
<li><a href="../linux/index.html">&rsaquo; linux/</a></li>
<li><a href="../mainframe/index.html">&rsaquo; mainframe/</a></li>
<li><a href="../me/index.html">&rsaquo; me/</a></li>
<li><a href="../opinions/index.html">&rsaquo; opinions/</a></li>
<li><a href="../plan9/index.html">&rsaquo; plan9/</a></li>
<li><a href="../prolog/index.html">&rsaquo; prolog/</a></li>
<li><a href="../web/index.html">&rsaquo; web/</a></li>
</ul>
        </div>
    </nav>

<article>
<h1>Finding solutions to the date puzzle using APL</h1>
<h2>The problem</h2>
<p>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.</p>

<p><a href="https://images.pmikkelsen.com/date-puzzle.png" /><img src="https://images.pmikkelsen.com/date-puzzle.png" alt="A picture of the puzzle" /></a></p>
<p>We decided to write a program to find solutions.</p>
<h2>The program</h2>
<p>The program is written using Dyalog APL, and it finds all possible solutions (for all days) in about 30 seconds on my laptop.</p>
<p>The <code>Solve</code> function finds all solutions and stores them in the global variable <code>SOLUTIONS</code>. The <code>Date</code> function finds all solutions for a given date (by finding all possible solutions and filtering them).</p>
<h3>Solve</h3>
<code><pre>
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
</pre></code>
<h3>Date </h3>
<code><pre>
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
</pre></code>
<h2>Example run</h2>
<code><pre>
      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│
└───────┴───────┴───────┴───────┴───────┴───────┴───────┘
</pre></code>
<p>Each nested array represents one solution. An <code>x</code> indicates the parts of the board that doesn't exist, and each piece is represented by an uppercase letter from <code>A</code> to <code>H</code>. So, October 6th has different solutions :)</p>

</article>
</div>

<footer>
<a href="http://werc.cat-v.org">Powered by werc</a> © Peter Mikkelsen 2019-2025
</footer>
</body></html>
~kris/9p

krisyotam.net
