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

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Sum and product puzzle step by step in the Scheme 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 Scheme programming language

Source code in the scheme programming language

(import (scheme base)
        (scheme cxr)
        (scheme write)
        (srfi 1))

;; utility method to find unique sum/product in given list
(define (unique-items lst key)
  (let ((all-items (map key lst)))
    (filter (lambda (i) (= 1 (count (lambda (p) (= p (key i)))
                                    all-items)))
            lst)))

;; list of all (x y x+y x*y) combinations with y > x
(define *xy-pairs* 
  (apply append
         (map (lambda (i)
                (map (lambda (j)
                       (list i j (+ i j) (* i j)))
                     (iota (- 98 i) (+ 1 i))))
              (iota 96 2))))
  
;; S says "P does not know X and Y"
(define *products* ; get products which have multiple decompositions
  (let ((all-products (map fourth *xy-pairs*)))
    (filter (lambda (p) (> (count (lambda (i) (= i p)) all-products) 1))
            all-products)))

(define *fact-1* ; every x+y has x*y in *products*
  (filter (lambda (i) 
            (every (lambda (p) (memq (fourth p) *products*))
                   (filter (lambda (p) (= (third i) (third p))) *xy-pairs*)))
          *xy-pairs*))

;; P says "Now I know X and Y"
(define *fact-2* ; find the unique X*Y
  (unique-items *fact-1* fourth))

;; S says "Now I also know X and Y"
(define *fact-3* ; find the unique X+Y
  (unique-items *fact-2* third))

(display (string-append "Initial pairs: " (number->string (length *xy-pairs*)) "\n"))
(display (string-append "After S: " (number->string (length *fact-1*)) "\n"))
(display (string-append "After P: " (number->string (length *fact-2*)) "\n"))
(display (string-append "After S: " (number->string (length *fact-3*)) "\n"))
(display (string-append "X: " 
                        (number->string (caar *fact-3*))
                        " Y: "
                        (number->string (cadar *fact-3*))
                        "\n"))


  

You may also check:How to resolve the algorithm Balanced brackets step by step in the Erlang programming language
You may also check:How to resolve the algorithm 100 doors step by step in the XPL0 programming language
You may also check:How to resolve the algorithm Selectively replace multiple instances of a character within a string step by step in the Perl programming language
You may also check:How to resolve the algorithm Respond to an unknown method call step by step in the Icon and Unicon programming language
You may also check:How to resolve the algorithm Loops/Continue step by step in the Oforth programming language