How to resolve the algorithm Sum and product puzzle step by step in the Picat programming language

Published on 12 May 2024 09:40 PM
#Picat

How to resolve the algorithm Sum and product puzzle step by step in the Picat programming language

Table of Contents

Problem Statement

Solve the "Impossible Puzzle": It can be hard to wrap one's head around what the three lines of dialog between S (the "sum guy") and P (the "product guy") convey about the values of X and Y. So for your convenience, here's a break-down: Terminology:

Your program can solve the puzzle by considering all possible pairs (X, Y) in the range 2 ≤ X < Y ≤ 98, and then successively eliminating candidates based on the three facts. It turns out only one solution remains! See the Python example for an implementation that uses this approach with a few optimizations.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sum and product puzzle step by step in the Picat programming language

Source code in the picat programming language

main =>
    N = 98, 
    PD = new_array(N*N), % PD[I] = no. of product decompositions of I
    foreach(I in 1..N*N) PD[I] = 0 end, 
    foreach(X in 2..N-1, Y in X+1..N) PD[X * Y] := PD[X * Y] + 1 end, 

    % Fact 1: S says "P does not know X and Y.", i.e.
    % For every possible sum decomposition of the number X+Y, the product has in turn more than one product decomposition:
    Solutions1 = [[X,Y] : X in 2..N-1, Y in X+1..100-X, foreach(XX in 2..X+Y-3) PD[XX * (X+Y-XX)] > 1 end], 

    % Fact 2: P says "Now I know X and Y.", i.e.
    % The number X*Y has only one product decomposition for which fact 1 is true: 
    Solutions2 = [[X,Y] : [X,Y] in Solutions1, foreach([XX,YY] in Solutions1, XX * YY = X * Y) XX = X, YY = Y end], 

    % Fact 3: S says "Now I also know X and Y.", i.e.
    % The number X+Y has only one sum decomposition for which fact 2 is true.
    Solutions3 = [[X,Y] : [X,Y] in Solutions2, foreach([XX,YY] in Solutions2, XX + YY = X + Y) XX = X, YY = Y end], 

    println(Solutions3).

You may also check:How to resolve the algorithm Parse an IP Address step by step in the Wren programming language
You may also check:How to resolve the algorithm Random number generator (included) step by step in the Chapel programming language
You may also check:How to resolve the algorithm Mertens function step by step in the Raku programming language
You may also check:How to resolve the algorithm Y combinator step by step in the Klingphix programming language
You may also check:How to resolve the algorithm Inheritance/Multiple step by step in the Aikido programming language