mirror of
https://github.com/correl/correl.github.io.git
synced 2024-12-28 19:19:17 +00:00
473 lines
12 KiB
HTML
473 lines
12 KiB
HTML
---
|
||
title: Birthday Puzzle
|
||
author: Correl Roush
|
||
---
|
||
<p>
|
||
This logic puzzle has been floating around the internet lately. When I
|
||
caught wind of it, I thought it would be a great exercise to tackle
|
||
using Prolog. I'm not especially good with the language yet, so it
|
||
added to the challenge a bit, but it was a pretty worthwhile
|
||
undertaking. When I got stumped, I discovered that mapping out the
|
||
birthdays into a grid helped me visualize the problem and ultimately
|
||
solve it, so I've included that with my prolog code so you can see how
|
||
I arrived at the answer.
|
||
</p>
|
||
|
||
<div id="outline-container-sec-1" class="outline-2">
|
||
<h2 id="sec-1">The Puzzle</h2>
|
||
<div class="outline-text-2" id="text-1">
|
||
<p>
|
||
Albert and Bernard have just met Cheryl. “When is your birthday?”
|
||
Albert asked Cheryl. Cheryl thought for a moment and said, “I won’t
|
||
tell you, but I’ll give you some clues”. She wrote down a list of
|
||
ten dates:
|
||
</p>
|
||
|
||
|
||
<ul class="org-ul">
|
||
<li>May 15, May 16, May 19
|
||
</li>
|
||
<li>June 17, June 18
|
||
</li>
|
||
<li>July 14, July 16
|
||
</li>
|
||
<li>August 14, August 15, August 17
|
||
</li>
|
||
</ul>
|
||
|
||
<p>
|
||
“One of these is my birthday,” she said.
|
||
</p>
|
||
|
||
|
||
<p>
|
||
Cheryl whispered in Albert’s ear the month, and only the month, of
|
||
her birthday. To Bernard, she whispered the day, and only the
|
||
day. “Can you figure it out now?” she asked Albert.
|
||
</p>
|
||
|
||
|
||
<p>
|
||
Albert: “I don’t know when your birthday is, but I know Bernard
|
||
doesn’t know, either.”
|
||
</p>
|
||
|
||
<p>
|
||
Bernard: “I didn’t know originally, but now I do.”
|
||
</p>
|
||
|
||
<p>
|
||
Albert: “Well, now I know, too!”
|
||
</p>
|
||
|
||
<p>
|
||
<i>When is Cheryl’s birthday?</i>
|
||
</p>
|
||
</div>
|
||
</div>
|
||
|
||
<div id="outline-container-sec-2" class="outline-2">
|
||
<h2 id="sec-2">The Solution</h2>
|
||
<div class="outline-text-2" id="text-2">
|
||
</div><div id="outline-container-sec-2-1" class="outline-3">
|
||
<h3 id="sec-2-1">The Dates</h3>
|
||
<div class="outline-text-3" id="text-2-1">
|
||
<p>
|
||
To start off, i entered each of the possible birthdays as facts:
|
||
</p>
|
||
|
||
<div class="org-src-container">
|
||
|
||
<pre class="src src-prolog"><span style="color: #268bd2;">possible_birthday</span>(may, 15).
|
||
<span style="color: #268bd2;">possible_birthday</span>(may, 16).
|
||
<span style="color: #268bd2;">possible_birthday</span>(may, 19).
|
||
<span style="color: #268bd2;">possible_birthday</span>(june, 17).
|
||
<span style="color: #268bd2;">possible_birthday</span>(june, 18).
|
||
<span style="color: #268bd2;">possible_birthday</span>(july, 14).
|
||
<span style="color: #268bd2;">possible_birthday</span>(july, 16).
|
||
<span style="color: #268bd2;">possible_birthday</span>(august, 14).
|
||
<span style="color: #268bd2;">possible_birthday</span>(august, 15).
|
||
<span style="color: #268bd2;">possible_birthday</span>(august, 17).
|
||
</pre>
|
||
</div>
|
||
|
||
<p>
|
||
And here they are, mapped out in a grid:
|
||
</p>
|
||
|
||
<table border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides">
|
||
|
||
|
||
<colgroup>
|
||
<col class="right" />
|
||
|
||
<col class="left" />
|
||
|
||
<col class="left" />
|
||
|
||
<col class="left" />
|
||
|
||
<col class="left" />
|
||
</colgroup>
|
||
<thead>
|
||
<tr>
|
||
<th scope="col" class="right"> </th>
|
||
<th scope="col" class="left">May</th>
|
||
<th scope="col" class="left">June</th>
|
||
<th scope="col" class="left">July</th>
|
||
<th scope="col" class="left">August</th>
|
||
</tr>
|
||
</thead>
|
||
<tbody>
|
||
<tr>
|
||
<td class="right">14</td>
|
||
<td class="left"> </td>
|
||
<td class="left"> </td>
|
||
<td class="left">X</td>
|
||
<td class="left">X</td>
|
||
</tr>
|
||
|
||
<tr>
|
||
<td class="right">15</td>
|
||
<td class="left">X</td>
|
||
<td class="left"> </td>
|
||
<td class="left"> </td>
|
||
<td class="left">X</td>
|
||
</tr>
|
||
|
||
<tr>
|
||
<td class="right">16</td>
|
||
<td class="left">X</td>
|
||
<td class="left"> </td>
|
||
<td class="left">X</td>
|
||
<td class="left"> </td>
|
||
</tr>
|
||
|
||
<tr>
|
||
<td class="right">17</td>
|
||
<td class="left"> </td>
|
||
<td class="left">X</td>
|
||
<td class="left"> </td>
|
||
<td class="left">X</td>
|
||
</tr>
|
||
|
||
<tr>
|
||
<td class="right">18</td>
|
||
<td class="left"> </td>
|
||
<td class="left">X</td>
|
||
<td class="left"> </td>
|
||
<td class="left"> </td>
|
||
</tr>
|
||
|
||
<tr>
|
||
<td class="right">19</td>
|
||
<td class="left">X</td>
|
||
<td class="left"> </td>
|
||
<td class="left"> </td>
|
||
<td class="left"> </td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
</div>
|
||
</div>
|
||
|
||
<div id="outline-container-sec-2-2" class="outline-3">
|
||
<h3 id="sec-2-2">Albert's Statement</h3>
|
||
<div class="outline-text-3" id="text-2-2">
|
||
<blockquote>
|
||
<p>
|
||
I don’t know when your birthday is,…
|
||
</p>
|
||
</blockquote>
|
||
|
||
<p>
|
||
Albert only knows the month, and the month isn't enough to uniquely
|
||
identify Cheryl's birthday.
|
||
</p>
|
||
|
||
<div class="org-src-container">
|
||
|
||
<pre class="src src-prolog"><span style="color: #268bd2;">month_is_not_unique</span>(<span style="color: #268bd2;">M</span>) :-
|
||
bagof(<span style="color: #268bd2;">D</span>, possible_birthday(<span style="color: #268bd2;">M</span>, <span style="color: #268bd2;">D</span>), <span style="color: #268bd2;">Days</span>),
|
||
length(<span style="color: #268bd2;">Days</span>, <span style="color: #268bd2;">Len</span>),
|
||
<span style="color: #268bd2;">Len</span> > 1.
|
||
</pre>
|
||
</div>
|
||
|
||
<blockquote>
|
||
<p>
|
||
… but I know Bernard doesn’t know, either.
|
||
</p>
|
||
</blockquote>
|
||
|
||
<p>
|
||
Albert knows that Bernard doesn't know Cheryl's
|
||
birthday. Therefore, the day alone isn't enough to know Cheryl's
|
||
birthday, and we can infer that the month of Cheryl's birthday does
|
||
not include any of the unique dates.
|
||
</p>
|
||
|
||
<div class="org-src-container">
|
||
|
||
<pre class="src src-prolog"><span style="color: #268bd2;">day_is_not_unique</span>(<span style="color: #268bd2;">D</span>) :-
|
||
bagof(<span style="color: #268bd2;">M</span>, possible_birthday(<span style="color: #268bd2;">M</span>, <span style="color: #268bd2;">D</span>), <span style="color: #268bd2;">Months</span>),
|
||
length(<span style="color: #268bd2;">Months</span>, <span style="color: #268bd2;">Len</span>),
|
||
<span style="color: #268bd2;">Len</span> > 1.
|
||
|
||
<span style="color: #268bd2;">month_has_no_unique_days</span>(<span style="color: #268bd2;">M</span>) :-
|
||
forall(possible_birthday(<span style="color: #268bd2;">M</span>,<span style="color: #268bd2;">D</span>),
|
||
day_is_not_unique(<span style="color: #268bd2;">D</span>)).
|
||
</pre>
|
||
</div>
|
||
|
||
<p>
|
||
Based on what Albert knows at this point, let's see how we've
|
||
reduced the possible dates:
|
||
</p>
|
||
|
||
<div class="org-src-container">
|
||
|
||
<pre class="src src-prolog"><span style="color: #268bd2;">part_one</span>(<span style="color: #268bd2;">M</span>,<span style="color: #268bd2;">D</span>) :-
|
||
possible_birthday(<span style="color: #268bd2;">M</span>,<span style="color: #268bd2;">D</span>),
|
||
month_is_not_unique(<span style="color: #268bd2;">M</span>),
|
||
month_has_no_unique_days(<span style="color: #268bd2;">M</span>),
|
||
day_is_not_unique(<span style="color: #268bd2;">D</span>).
|
||
</pre>
|
||
</div>
|
||
|
||
<pre class="example">
|
||
Results = [ (july, 14), (july, 16), (august, 14), (august, 15), (august, 17)].
|
||
</pre>
|
||
|
||
<p>
|
||
So the unique days (the 18th and 19th) are out, as are the months
|
||
that contained them (May and June).
|
||
</p>
|
||
|
||
<table border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides">
|
||
|
||
|
||
<colgroup>
|
||
<col class="right" />
|
||
|
||
<col class="left" />
|
||
|
||
<col class="left" />
|
||
</colgroup>
|
||
<thead>
|
||
<tr>
|
||
<th scope="col" class="right"> </th>
|
||
<th scope="col" class="left">July</th>
|
||
<th scope="col" class="left">August</th>
|
||
</tr>
|
||
</thead>
|
||
<tbody>
|
||
<tr>
|
||
<td class="right">14</td>
|
||
<td class="left">X</td>
|
||
<td class="left">X</td>
|
||
</tr>
|
||
|
||
<tr>
|
||
<td class="right">15</td>
|
||
<td class="left"> </td>
|
||
<td class="left">X</td>
|
||
</tr>
|
||
|
||
<tr>
|
||
<td class="right">16</td>
|
||
<td class="left">X</td>
|
||
<td class="left"> </td>
|
||
</tr>
|
||
|
||
<tr>
|
||
<td class="right">17</td>
|
||
<td class="left"> </td>
|
||
<td class="left">X</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
</div>
|
||
</div>
|
||
|
||
<div id="outline-container-sec-2-3" class="outline-3">
|
||
<h3 id="sec-2-3">Bernard's Statement</h3>
|
||
<div class="outline-text-3" id="text-2-3">
|
||
<blockquote>
|
||
<p>
|
||
I didn’t know originally, but now I do.
|
||
</p>
|
||
</blockquote>
|
||
|
||
<p>
|
||
For Bernard to know Cheryl's birthday, the day he knows must be
|
||
unique within the constraints we have so far.
|
||
</p>
|
||
|
||
<div class="org-src-container">
|
||
|
||
<pre class="src src-prolog"><span style="color: #268bd2;">day_is_unique</span>(<span style="color: #268bd2;">Month</span>, <span style="color: #268bd2;">Day</span>) :-
|
||
findall(<span style="color: #268bd2;">M</span>, part_one(<span style="color: #268bd2;">M</span>, <span style="color: #268bd2;">Day</span>), <span style="color: #859900; font-weight: bold;">[</span><span style="color: #268bd2;">Month</span><span style="color: #859900; font-weight: bold;">]</span>).
|
||
<span style="color: #268bd2;">part_two</span>(<span style="color: #268bd2;">Month</span>, <span style="color: #268bd2;">Day</span>) :-
|
||
possible_birthday(<span style="color: #268bd2;">Month</span>, <span style="color: #268bd2;">Day</span>),
|
||
day_is_unique(<span style="color: #268bd2;">Month</span>, <span style="color: #268bd2;">Day</span>).
|
||
</pre>
|
||
</div>
|
||
|
||
<pre class="example">
|
||
Results = [ (july, 16), (august, 15), (august, 17)].
|
||
</pre>
|
||
|
||
<p>
|
||
Both July and August contain the 14th, so that row is out.
|
||
</p>
|
||
|
||
<table border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides">
|
||
|
||
|
||
<colgroup>
|
||
<col class="right" />
|
||
|
||
<col class="left" />
|
||
|
||
<col class="left" />
|
||
</colgroup>
|
||
<thead>
|
||
<tr>
|
||
<th scope="col" class="right"> </th>
|
||
<th scope="col" class="left">July</th>
|
||
<th scope="col" class="left">August</th>
|
||
</tr>
|
||
</thead>
|
||
<tbody>
|
||
<tr>
|
||
<td class="right">15</td>
|
||
<td class="left"> </td>
|
||
<td class="left">X</td>
|
||
</tr>
|
||
|
||
<tr>
|
||
<td class="right">16</td>
|
||
<td class="left">X</td>
|
||
<td class="left"> </td>
|
||
</tr>
|
||
|
||
<tr>
|
||
<td class="right">17</td>
|
||
<td class="left"> </td>
|
||
<td class="left">X</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
</div>
|
||
</div>
|
||
|
||
<div id="outline-container-sec-2-4" class="outline-3">
|
||
<h3 id="sec-2-4">Albert's Second Statement</h3>
|
||
<div class="outline-text-3" id="text-2-4">
|
||
<blockquote>
|
||
<p>
|
||
Well, now I know, too!
|
||
</p>
|
||
</blockquote>
|
||
|
||
<p>
|
||
Albert's month must be the remaining unique month:
|
||
</p>
|
||
|
||
<div class="org-src-container">
|
||
|
||
<pre class="src src-prolog"><span style="color: #268bd2;">month_is_not_unique</span>(<span style="color: #268bd2;">Month</span>, <span style="color: #268bd2;">Day</span>) :-
|
||
findall(<span style="color: #268bd2;">D</span>, part_two(<span style="color: #268bd2;">Month</span>, <span style="color: #268bd2;">D</span>), <span style="color: #859900; font-weight: bold;">[</span><span style="color: #268bd2;">Day</span><span style="color: #859900; font-weight: bold;">]</span>).
|
||
<span style="color: #268bd2;">part_three</span>(<span style="color: #268bd2;">Month</span>, <span style="color: #268bd2;">Day</span>) :-
|
||
possible_birthday(<span style="color: #268bd2;">Month</span>, <span style="color: #268bd2;">Day</span>),
|
||
month_is_not_unique(<span style="color: #268bd2;">Month</span>, <span style="color: #268bd2;">Day</span>).
|
||
</pre>
|
||
</div>
|
||
|
||
<pre class="example">
|
||
Results = [ (july, 16)].
|
||
</pre>
|
||
|
||
<p>
|
||
August had two possible days, so it's now clear that the only
|
||
possible unique answer is July 16th.
|
||
</p>
|
||
|
||
<table border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides">
|
||
|
||
|
||
<colgroup>
|
||
<col class="right" />
|
||
|
||
<col class="left" />
|
||
</colgroup>
|
||
<thead>
|
||
<tr>
|
||
<th scope="col" class="right"> </th>
|
||
<th scope="col" class="left">July</th>
|
||
</tr>
|
||
</thead>
|
||
<tbody>
|
||
<tr>
|
||
<td class="right">15</td>
|
||
<td class="left"> </td>
|
||
</tr>
|
||
|
||
<tr>
|
||
<td class="right">16</td>
|
||
<td class="left">X</td>
|
||
</tr>
|
||
|
||
<tr>
|
||
<td class="right">17</td>
|
||
<td class="left"> </td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
</div>
|
||
</div>
|
||
|
||
<div id="outline-container-sec-2-5" class="outline-3">
|
||
<h3 id="sec-2-5">Cheryl's Birthday</h3>
|
||
<div class="outline-text-3" id="text-2-5">
|
||
<div class="org-src-container">
|
||
|
||
<pre class="src src-prolog"><span style="color: #268bd2;">cheryls_birthday</span>(<span style="color: #268bd2;">Month</span>, <span style="color: #268bd2;">Day</span>) :-
|
||
part_three(<span style="color: #268bd2;">Month</span>, <span style="color: #268bd2;">Day</span>).
|
||
</pre>
|
||
</div>
|
||
|
||
<pre class="example">
|
||
Month = july,
|
||
Day = 16.
|
||
</pre>
|
||
|
||
<p>
|
||
So, there we have it. Cheryl's birthday is July 16th!
|
||
</p>
|
||
|
||
<table border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides">
|
||
|
||
|
||
<colgroup>
|
||
<col class="right" />
|
||
|
||
<col class="left" />
|
||
</colgroup>
|
||
<thead>
|
||
<tr>
|
||
<th scope="col" class="right"> </th>
|
||
<th scope="col" class="left">July</th>
|
||
</tr>
|
||
</thead>
|
||
<tbody>
|
||
<tr>
|
||
<td class="right">16</td>
|
||
<td class="left">X</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
</div>
|
||
</div>
|
||
</div>
|