Solving a puzzle in Racket

问题:

I tried to solve this puzzle https://puzzling.stackexchange.com/questions/40094/who-committed-the-crime using Racket.

A crime has been carried out by one person, there are 5 suspects. Each suspect is asked under polygraph who they think committed the crime.

Their answers are as follows:

Terry : It wasn't Carl, It was Steve 
Steve : It wasn't Matt, It wasn't Carl 
Matt : It was Carl, It wasn't Terry 
Ben : It was Matt, It was Steve 
Carl : It was Ben, It wasn't Terry 

The polygraph showed that each suspect told one lie and one truth. Who committed the crime?

Following is my code:

(define (oneof a b)
  (or (and a (not b)) (and b (not a))))

(for ((i 5))
  (define templist (list #f #f #f #f #f))  ; make a temporary list of all false; 
  (set! templist (list-set templist i #t)) ; one by one keep one as true in this loop; 
  (define t (list-ref templist 0))   ; allocate each person according to above list (one kept true one by one)
  (define s (list-ref templist 1))
  (define m (list-ref templist 2))
  (define b (list-ref templist 3))
  (define c (list-ref templist 4))

  (when                              ; test if all statements fit with above assignment: 
    (and
     (oneof  (not c) s)              ; Terry's statement
     (oneof  (not m) (not c))        ; Steve's statement
     (oneof  c (not t))              ; Matt's statement
     (oneof  m s)                    ; Ben's statement
     (oneof  b (not t)))             ; Carl's statement
    (println (list "t" "s" "m" "b" "c"))  ; print allocation if all statement fit in; 
    (println templist)))

Output indicates Matt committed the crime:

'("t" "s" "m" "b" "c")
'(#f #f #t #f #f)

It works but the code is imperative and not very functional (especially define t, define s, ... part). How can it can be improved? Thanks for your comments/answers.

回答1:

This is an equivalent program written in idiomatic Racket - and avoiding all those pesky set! and list-ref which are frowned upon when writing functional-style code:

; generate a matrix with possibilities
(define (make-matrix n)
  (for/list [(i (in-range n))]
    (build-list n (λ (j) (= i j)))))

; iterate over each row
(for [(row (make-matrix 5))]
  ; unpack each row into the corresponding variables
  (match-let ([(list t s m b c) row])
    ; don't reinvent the wheel, `oneof` is called `xor`
    (when (and (xor (not c) s)
               (xor (not m) (not c))
               (xor c (not t))
               (xor m s)
               (xor b (not t)))
      (println '(t s m b c))
      (println row))))

回答2:

This answer is based on @Oscar Lopez's answer, but modified to use more idiomatic features like filter with a helper function instead of for, when, and println.

This style of code returning a value is much more useful because the value it produces could be used in later code, where an imperative action like println would be much less reusable.

@Oscar Lopez's make-matrix function produces an initial list of possibilities, but we have to filter out the ones that are impossible, and leave only the ones that are possible. So write that down:

;; If there are no valid solutions, this will be an empty list,
;; if there's one, this will be a list of one element,
;; and if there are more, this will include all of them.
(filter valid-solution? (make-matrix 5))

;; Wish list:
;; valid-solution? : (Listof Boolean) -> Boolean

Now we just need to add a definition for valid-solution?

;; valid-solution? : (Listof Boolean) -> Boolean
;; Given a list containing booleans for whether Terry, Steve, Matt, Ben, and Carl did it,
;; this determines whether that combination is possible under the constraints in the problem.
(define (valid-solution? row)
  ; unpack each row into the corresponding variables
  (match-define (list t s m b c) row)
  ; don't reinvent the wheel, `oneof` is called `xor`
  (and (xor (not c) s)
       (xor (not m) (not c))
       (xor c (not t))
       (xor m s)
       (xor b (not t))))

And that's it. The full program including make-matrix is this:

#lang racket

;; make-matrix : Natural -> (Listof (Listof Boolean))
;; generate a matrix with possibilities
(define (make-matrix n)
  (for/list ([i (in-range n)])
    (build-list n (λ (j) (= i j)))))

;; valid-solution? : (Listof Boolean) -> Boolean
;; Given a list containing booleans for whether Terry, Steve, Matt, Ben, and Carl did it,
;; this determines whether that combination is possible under the constraints in the problem.
(define (valid-solution? row)
  ; unpack each row into the corresponding variables
  (match-define (list t s m b c) row)
  ; don't reinvent the wheel, `oneof` is called `xor`
  (and (xor (not c) s)
       (xor (not m) (not c))
       (xor c (not t))
       (xor m s)
       (xor b (not t))))

;; If there are no valid solutions, this will be an empty list,
;; if there's one, this will be a list of one element,
;; and if there are more, this will include all of them.
(filter valid-solution? (make-matrix 5))