mirror of
https://github.com/correl/correl.github.io.git
synced 2024-12-29 11:09:24 +00:00
474 lines
12 KiB
HTML
474 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>
|