Mister X: Difference between revisions

From This Prolog Life
Jump to navigation Jump to search
(6 intermediate revisions by the same user not shown)
Line 2: Line 2:
Although this problem has a straightforward solution, it does demonstrate the value of thinking declaratively in understanding the problem, which relates to “don't know” nondeterminism, and an appropriate use of lemmas.
Although this problem has a straightforward solution, it does demonstrate the value of thinking declaratively in understanding the problem, which relates to “don't know” nondeterminism, and an appropriate use of lemmas.
== Problem: ==
== Problem: ==
[http://groups.google.com/group/de.comp.lang.java/msg/12cb7c2083cde4f8 Problem as posted to comp.lang.prolog] by Thorsten Seelend. Also known as Hans Freudenthal's [[wikipedia:Impossible Puzzle|Impossible Puzzle]].
[https://groups.google.com/forum/#!msg/de.comp.lang.java/xQ6T3kZGqcE/-OTNgyB8yxIJ Problem as posted to comp.lang.prolog] by Thorsten Seelend. Also known as Hans Freudenthal's [[wikipedia:Impossible Puzzle|Impossible Puzzle]].


<blockquote>Mister X thinks about two integers between 1 and 100 excluding:
<blockquote>Mister X thinks about two integers between 1 and 100 excluding:
</blockquote>
</blockquote>
=====MISTERX: Two integers, X and Y between 2 and 99 (My formalization of the given information)=====
=====MISTERX: Two integers, X and Y between 2 and 99 (My formalization of the given information)=====
<syntaxhighlight lang="prolog">two_integers( X, Y ) :-
<pre class="prolog">two_integers( X, Y ) :-
     between( 2, 98, X ),
     between( 2, 98, X ),
     between( X, 99, Y ).</syntaxhighlight>
     between( X, 99, Y ).</pre>
He tells Susan the Sum of them and Peter their Product. Their task is to get the two original values without telling each other the numbers that Mister X told them.
He tells Susan the Sum of them and Peter their Product. Their task is to get the two original values without telling each other the numbers that Mister X told them.
<blockquote>After some time Peter says:
<blockquote>After some time Peter says:
&ldquo;I can't say definitively which are the original numbers.&rdquo;</blockquote>
&ldquo;I can't say definitively which are the original numbers.&rdquo;</blockquote>
=====PETER1: There is more than one pair of factors giving Product=====
=====PETER1: There is more than one pair of factors giving Product=====
<syntaxhighlight lang="prolog">property( peter1, Product ) :-
<pre class="prolog">property( peter1, Product ) :-
     \+ unique_factors( Product ).</syntaxhighlight>
     \+ unique_factors( Product ).</pre>
<blockquote>Then Susan responds: &ldquo;Neither can I, but I knew that you couldn't know it.&rdquo;</blockquote>
<blockquote>Then Susan responds: &ldquo;Neither can I, but I knew that you couldn't know it.&rdquo;</blockquote>


=====SUSAN1: The product of ''every'' pair of summands giving Sum has the property PETER1=====
=====SUSAN1: The product of ''every'' pair of summands giving Sum has the property PETER1=====
<syntaxhighlight lang="prolog">property( susan1, Sum ) :-
<pre class="prolog">property( susan1, Sum ) :-
     forall( ordered_summands(Sum, X, Y), peter1(X * Y) ).</syntaxhighlight>
     forall( ordered_summands(Sum, X, Y), peter1(X * Y) ).</pre>


<blockquote>Peter: &ldquo;Really? So now I know the original numbers&rdquo;.</blockquote>
<blockquote>Peter: &ldquo;Really? So now I know the original numbers&rdquo;.</blockquote>
=====PETER2: ''exactly one'' pair of factors giving Product gives a sum with the property SUSAN1=====
=====PETER2: ''exactly one'' pair of factors giving Product gives a sum with the property SUSAN1=====
<syntaxhighlight lang="prolog">property( peter2, Product ) :-
<pre class="prolog">property( peter2, Product ) :-
     unique_solution( (ordered_factors(Product, X, Y), susan1(X+Y)) ).</syntaxhighlight>
     unique_solution( (ordered_factors(Product, X, Y), susan1(X+Y)) ).</pre>


<blockquote>Susan: &ldquo;Now I know them too&rdquo;.</blockquote>
<blockquote>Susan: &ldquo;Now I know them too&rdquo;.</blockquote>
=====SUSAN2: ''exactly one'' pair of summands giving Sum has a product with the property PETER2=====
=====SUSAN2: ''exactly one'' pair of summands giving Sum has a product with the property PETER2=====
<syntaxhighlight lang="prolog">property( susan2, Sum ) :-
<pre class="prolog">property( susan2, Sum ) :-
     unique_solution( (ordered_summands(Sum, X, Y), peter2(X * Y)) ).</syntaxhighlight>
     unique_solution( (ordered_summands(Sum, X, Y), peter2(X * Y)) ).</pre>
<blockquote>Question: What are the two numbers that Mister X thought of?</blockquote>
<blockquote>Question: What are the two numbers that Mister X thought of?</blockquote>
=====Unique solution=====
=====Unique solution=====
<syntaxhighlight lang="prolog">solve( X, Y ) :-
<pre class="prolog">solve( X, Y ) :-
     unique_solution( mister_x(X, Y) ).
     unique_solution( mister_x(X, Y) ).


Line 43: Line 43:
     susan1( Sum ),
     susan1( Sum ),
     peter2( Product ),
     peter2( Product ),
     susan2( Sum ).</syntaxhighlight>
     susan2( Sum ).</pre>


== Macros ==
== Macros ==
<syntaxhighlight lang="prolog">peter1( Product ) :-
<pre class="prolog">peter1( Product ) :-
     lemma( peter1, Product ).
     lemma( peter1, Product ).


Line 56: Line 56:


susan2( Sum ) :-
susan2( Sum ) :-
     lemma( susan2, Sum ).</syntaxhighlight>
     lemma( susan2, Sum ).</pre>


== Lemmas ==
== Lemmas ==
Line 67: Line 67:


Using lemmas or tabling to cache results is an order of magnitude faster than recalculating each property every time it is used.
Using lemmas or tabling to cache results is an order of magnitude faster than recalculating each property every time it is used.
<syntaxhighlight lang="prolog">:- dynamic positive/2, negative/2.
<pre class="prolog">:- dynamic positive/2, negative/2.


lemma( Name, Expression ) :-
lemma( Name, Expression ) :-
Line 80: Line 80:
           fail
           fail
         )
         )
     ).</syntaxhighlight>
     ).</pre>


== Supporting Predicates ==
== Supporting Predicates ==
Line 86: Line 86:
when <var>X</var> &le; <var>Y</var> and Sum = <var>X</var>+<var>Y</var>.
when <var>X</var> &le; <var>Y</var> and Sum = <var>X</var>+<var>Y</var>.
NB: Since <var>X</var>&le;<var>Y</var> it follows that <var>X</var> &le; <var>Sum</var>/2.
NB: Since <var>X</var>&le;<var>Y</var> it follows that <var>X</var> &le; <var>Sum</var>/2.
<syntaxhighlight lang="prolog">ordered_summands( Z, X, Y ) :-
<pre class="prolog">ordered_summands( Z, X, Y ) :-
     Half is Z//2,
     Half is Z//2,
     between( 2, Half, X ),
     between( 2, Half, X ),
     Y is Z - X,
     Y is Z - X,
     between( X, 98, Y ).</syntaxhighlight>
     between( X, 98, Y ).</pre>
====ordered_factors( +Product, ?X, ?Y )====
====ordered_factors( +Product, ?X, ?Y )====
when <var>X</var> &le; <var>Y</var> and <var>Product</var> = <var>X</var> &times; <var>Y</var>.
when <var>X</var> &le; <var>Y</var> and <var>Product</var> = <var>X</var> &times; <var>Y</var>.
NB: Since <var>X</var>&le;<var>Y</var> it follows that
NB: Since <var>X</var>&le;<var>Y</var> it follows that
<var>X</var> &le; &radic;<var>Product</var>.
<var>X</var> &le; &radic;<var>Product</var>.
<syntaxhighlight lang="prolog">ordered_factors( Z, X, Y ) :-
<pre class="prolog">ordered_factors( Z, X, Y ) :-
     integer_sqrt( Z, SqrtZ ),
     integer_sqrt( Z, SqrtZ ),
     between( 2, SqrtZ, X ),
     between( 2, SqrtZ, X ),
     Y is Z // X,
     Y is Z // X,
     between( X, 99, Y ),
     between( X, 99, Y ),
     Z =:= X * Y.</syntaxhighlight>
     Z =:= X * Y.</pre>
====unique_factors( +Product )====
====unique_factors( +Product )====
when <var>Product</var> has exactly one pair of factors.
when <var>Product</var> has exactly one pair of factors.
<syntaxhighlight lang="prolog">unique_factors( Product ) :-
<pre class="prolog">unique_factors( Product ) :-
     ordered_factors( Product, X, _Y ),
     ordered_factors( Product, X, _Y ),
     \+ (ordered_factors(Product, X1, _Y1), X1 =\= X).</syntaxhighlight>
     \+ (ordered_factors(Product, X1, _Y1), X1 =\= X).</pre>
====integer_sqrt( +N, ?Sqrt )====
====integer_sqrt( +N, ?Sqrt )====
when <var>Sqrt</var><sup>2</sup> &le; <var>N</var> and (<var>Sqrt</var>+1)<sup>2</sup> &ge; <var>N</var>.
when <var>Sqrt</var><sup>2</sup> &le; <var>N</var> &lt; (<var>Sqrt</var>+1)<sup>2</sup>.
<syntaxhighlight lang="prolog">integer_sqrt( N, Sqrt ) :-
<pre class="prolog">integer_sqrt( N, Sqrt ) :-
     Float is N * 1.0,
     Float is N * 1.0,
     sqrt( Float, FSqrt ),
     sqrt( Float, FSqrt ),
     Sqrt is integer(FSqrt).</syntaxhighlight>
     Sqrt is integer(FSqrt).</pre>
Load a small library of [[Puzzle Utilities]].
Load a small library of [[Puzzle Utilities]].


<syntaxhighlight lang="prolog">
<pre class="prolog">:- ensure_loaded( misc ).</pre>
 
The code is available as plain text [https://binding-time.co.uk/download/mister_x.txt here].
:- ensure_loaded( misc ).
 
</syntaxhighlight>
The code is available as plain text [http://www.binding-time.co.uk/download/mister_x.txt here].


== Result ==
== Result ==
This program finds X and Y as '''4''' and '''13'''.
This program finds X and Y as '''4''' and '''13'''.
== Tabling ==
== Tabling ==
Using tabling, rather than explicit lemmas, can simplify code. [http://binding-time.co.uk/download/xsb_mister_x.txt A version adapted for XSB Prolog is available here.]
Using tabling, rather than explicit lemmas, can simplify code. [https://binding-time.co.uk/download/xsb_mister_x.txt A version adapted for XSB Prolog is available here.]

Revision as of 19:56, 20 January 2018

Although this problem has a straightforward solution, it does demonstrate the value of thinking declaratively in understanding the problem, which relates to “don't know” nondeterminism, and an appropriate use of lemmas.

Problem:

Problem as posted to comp.lang.prolog by Thorsten Seelend. Also known as Hans Freudenthal's Impossible Puzzle.

Mister X thinks about two integers between 1 and 100 excluding:

MISTERX: Two integers, X and Y between 2 and 99 (My formalization of the given information)
two_integers( X, Y ) :-
    between( 2, 98, X ),
    between( X, 99, Y ).

He tells Susan the Sum of them and Peter their Product. Their task is to get the two original values without telling each other the numbers that Mister X told them.

After some time Peter says: “I can't say definitively which are the original numbers.”

PETER1: There is more than one pair of factors giving Product
property( peter1, Product ) :-
    \+ unique_factors( Product ).

Then Susan responds: “Neither can I, but I knew that you couldn't know it.”

SUSAN1: The product of every pair of summands giving Sum has the property PETER1
property( susan1, Sum ) :-
    forall( ordered_summands(Sum, X, Y), peter1(X * Y) ).

Peter: “Really? So now I know the original numbers”.

PETER2: exactly one pair of factors giving Product gives a sum with the property SUSAN1
property( peter2, Product ) :-
    unique_solution( (ordered_factors(Product, X, Y), susan1(X+Y)) ).

Susan: “Now I know them too”.

SUSAN2: exactly one pair of summands giving Sum has a product with the property PETER2
property( susan2, Sum ) :-
    unique_solution( (ordered_summands(Sum, X, Y), peter2(X * Y)) ).

Question: What are the two numbers that Mister X thought of?

Unique solution
solve( X, Y ) :-
    unique_solution( mister_x(X, Y) ).

mister_x( X, Y ) :-
    two_integers( X, Y ),
    Sum is X + Y,
    Product is X * Y,
    peter1( Product ),
    susan1( Sum ),
    peter2( Product ),
    susan2( Sum ).

Macros

peter1( Product ) :-
    lemma( peter1, Product ).

peter2( Product ) :-
    lemma( peter2, Product ).

susan1( Sum ) :-
    lemma( susan1, Sum ).

susan2( Sum ) :-
    lemma( susan2, Sum ).

Lemmas

lemma( +Property, +Expression )

holds wherever Property holds for Expression.

Asserted facts are used to record successful (positive) or failed (negative) demonstrations. This saves recomputation without changing the meaning of the pure program.

Although the use of side-effects is generally undesirable, the use of lemmas is justified when the alternative is to compromise performance or clarity.

Using lemmas or tabling to cache results is an order of magnitude faster than recalculating each property every time it is used.

:- dynamic positive/2, negative/2.

lemma( Name, Expression ) :-
    Value is Expression,
    ( positive( Value, Name ) ->
        true
    ; \+ negative( Value, Name ) ->
        ( property(Name, Value) ->
           assert( positive(Value, Name) )
        ; otherwise ->
           assert( negative(Value, Name) ),
           fail
        )
    ).

Supporting Predicates

ordered_summands( +Sum, ?X, ?Y )

when XY and Sum = X+Y. NB: Since XY it follows that XSum/2.

ordered_summands( Z, X, Y ) :-
    Half is Z//2,
    between( 2, Half, X ),
    Y is Z - X,
    between( X, 98, Y ).

ordered_factors( +Product, ?X, ?Y )

when XY and Product = X × Y. NB: Since XY it follows that X ≤ √Product.

ordered_factors( Z, X, Y ) :-
    integer_sqrt( Z, SqrtZ ),
    between( 2, SqrtZ, X ),
    Y is Z // X,
    between( X, 99, Y ),
    Z =:= X * Y.

unique_factors( +Product )

when Product has exactly one pair of factors.

unique_factors( Product ) :-
    ordered_factors( Product, X, _Y ),
    \+ (ordered_factors(Product, X1, _Y1), X1 =\= X).

integer_sqrt( +N, ?Sqrt )

when Sqrt2N < (Sqrt+1)2.

integer_sqrt( N, Sqrt ) :-
    Float is N * 1.0,
    sqrt( Float, FSqrt ),
    Sqrt is integer(FSqrt).

Load a small library of Puzzle Utilities.

:- ensure_loaded( misc ).

The code is available as plain text here.

Result

This program finds X and Y as 4 and 13.

Tabling

Using tabling, rather than explicit lemmas, can simplify code. A version adapted for XSB Prolog is available here.