XSB Mister X: Difference between revisions

Latest revision as of 20:42, 1 March 2024

Although this problem has a straightforward solution, it does demonstrate the value of thinking deductively to understand 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

:- table peter1/1.
 
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

:- table susan1/1.
 
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

:- table peter2/1.
 
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

:- table susan2/1.
 
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 ).

Supporting Predicates

ordered_summands( +Sum, ?X, ?Y )

when X ≤ Y and Sum = X+Y. NB: Since X≤Y it follows that X ≤ Sum/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 X ≤ Y and Product = X × Y. NB: Since X≤Y 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 Sqrt² ≤ N < (Sqrt+1)².

integer_sqrt( N, Sqrt ) :-
    Sqrt is floor(sqrt(N)).

Utility Predicates

Load a small library of Puzzle Utilities.

:- ensure_loaded( misc ).

Result

This program finds X and Y as 4 and 13.

@@ Line 57: / Line 57: @@
      peter2( Product ),
      susan2( Sum ).</pre>
-== Lemmas ==
-====lemma( +Property, +Expression )====
-holds wherever <var>Property</var> holds for <var>Expression</var>.
-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.
-<pre class="prolog">:- 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
-        )
-    ).</pre>
 == Supporting Predicates ==
@@ Line 109: / Line 85: @@
 when <var>Sqrt</var><sup>2</sup> &le; <var>N</var> &lt; (<var>Sqrt</var>+1)<sup>2</sup>.
 <pre class="prolog">integer_sqrt( N, Sqrt ) :-
-     Float is N * 1.0,
+     Sqrt is floor(sqrt(N)).</pre>
-    sqrt( Float, FSqrt ),
+== Utility Predicates ==
-    Sqrt is integer(FSqrt).</pre>
 Load a small library of [[Puzzle Utilities]].
 <pre class="prolog">:- ensure_loaded( misc ).</pre>
-The code is available as plain text [https://binding-time.co.uk/download/mister_x.txt here].
 == Result ==
 This program finds X and Y as '''4''' and '''13'''.
-== Tabling ==
-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.]