(Mastermind) puzzle (with 3 digits) -- Elegant (readable) code Sought

[HenHanna]

(i just wrote (non-elegant) Python code.)


Could you share a short, VERY Readable Pythonic (or Lisp, Scheme) code
that solves this?


Thank you!


Loading Image...


3 digit lock
[682]: One number is correct and well-placed
[614]: One number is correct but wrongly placed
[206]: Two numbers are correct but wrongly placed
[738]: Nothing is correct
[780]: One number is correct but wrongly placed


HINT -- A mark of a great puzzle, this one contains a surprise or two.

[Lawrence D'Oliveiro]

Post by HenHanna
Could you share a short, VERY Readable Pythonic (or Lisp, Scheme) code
that solves this?

This is my answer after spending this afternoon learning Guile. Much
more wordy than the Python version I previously posted. Anybody know
how to do it better?

(import
(rnrs base)
(rnrs lists)
)

(define (range n)
; returns a list of integers from 0 up to n - 1 inclusive.
(letrec
(
(subrange
(lambda (n)
(cond
((>= n 0) (cons n (subrange (- n 1))))
(#t '())
) ; cond
) ; lambda
)
)
(reverse (subrange (- n 1)))
) ; let
) ; define

(define (score candidate answer)
(let
(
(in-right-place 0)
(in-wrong-place 0)
)
(for-each
(lambda (a)
(for-each
(lambda (b)
(when (eq? a b)
(set! in-wrong-place (+ in-wrong-place 1))
; might be in right place, fixed up below
) ; when
) ; lambda
answer
) ; for-each
) ; lambda
candidate
) ; for-each
(for-each
(lambda (a b)
(when (eq? a b)
(set! in-right-place (+ in-right-place 1))
(set! in-wrong-place (- in-wrong-place 1))
) ; when
) ; lambda
candidate
answer
) ; for-each
(list in-right-place in-wrong-place)
) ; let
) ; score

(define required-scores
'(
((6 8 2) (1 0))
((6 1 4) (0 1))
((2 0 6) (0 2))
((7 3 8) (0 0))
((7 8 0) (0 1))
)
)

(for-each
(lambda (n)
(let-values
(
((a b c answer) (values #f #f #f #f))
)
(set! a (div n 100))
(set! n (- n (* a 100)))
(set! b (div n 10))
(set! c (- n (* b 10)))
(set! answer (list a b c))
(when
(for-all
(lambda (candidate)
(let
(
(required-score (cadr candidate))
)
(set! candidate (car candidate))
(equal? (score candidate answer) required-score)
) ; let
) ; lambda
required-scores
) ; for-all
(display answer)
(display "\n")
) ; when
) ; let-values
) ; lambda
(range 1000)
) ; let

[Paul Rubin]

Post by Lawrence D'Oliveiro
This is my answer after spending this afternoon learning Guile. Much
more wordy than the Python version I previously posted. Anybody know
how to do it better?

The following works for me as a fairly simple port of the concise Python
version to Guile. Note that the parenthesis style is pretty much
universal in Lisp and variants. Editors support it, and automatic paren
balancing in the editors keep them from getting too confusing.

If you want to understand Scheme, I suggest reading through SICP (click
the open access link at mitpress.mit.edu/sicp for a download). That
said, I'm not much of a Scheme user myself, so the below might have some
style issues.

I think by now, the methods introduced in Scheme have moved on to newer
languages like OCaml and then Haskell, so you might want to study those
instead. learnyouahaskell.com is a good start with Haskell.

================================================================

(use-modules (srfi srfi-1)
(srfi srfi-11))

(define clues '((682 1 0) (614 0 1) (206 0 2) (738 0 0) (780 0 1)))
(define (digits n)
(values (quotient n 100) (remainder (quotient n 10) 10) (remainder n 10)))
(define (count . args) (length (filter identity args)))

(define (score candidate answer)
(let-values (((a b c) (digits candidate))
((x y z) (digits answer)))
(let ((well-placed (count (= a x) (= b y) (= c z)))
(wrongly-placed (count (or (= a y) (= a z))
(or (= b x) (= b z))
(or (= c x) (= c y)))))
(values well-placed wrongly-placed))))

(define (test)
(let ((n 682) (a 1) (b 0))
(let-values (((well-placed wrongly-placed) (score n 042)))
(and (= a well-placed) (= b wrongly-placed)))))

(define (check candidate)
(define (check1 clue)
(let ((n (car clue))
(a (cadr clue))
(b (caddr clue)))
(let-values (((well-placed wrongly-placed) (score candidate n)))
(and (= a well-placed) (= b wrongly-placed)))))
(every check1 clues))

(display (filter check (iota 1000)))
(newline)

[Lawrence D'Oliveiro]

Note that the parenthesis style is pretty much universal in Lisp and
variants.

Sorry, not a fan of “parenthesis pileup” layout.

[Kaz Kylheku]

Post by Lawrence D'Oliveiro

Note that the parenthesis style is pretty much universal in Lisp and
variants.

Sorry, not a fan of “parenthesis pileup” layout.

You've certainly come to the right language family, if you want to
forever hack by yourself, doing things Your Way.

I suspect you're doing your formatting manually, though, which takes
more effort. The parentheses pileup is well supported in editors.

If you don't want collaborators, you can just communicate that
explicitly (e.g. a block comment saying ";; this is my solo work,
patches will be rejected regardless of quality") and not inflict an
unergonomic way of working on yourself.

[Kaz Kylheku]

Post by Paul Rubin

Post by Lawrence D'Oliveiro
This is my answer after spending this afternoon learning Guile. Much
more wordy than the Python version I previously posted. Anybody know
how to do it better?

The following works for me as a fairly simple port of the concise Python
version to Guile.

Based on code formatting alone, I'm declaring yours vastly better.

The problem is actually trivial.

All you have to do is close your parentheses ))) like a sane person, and
the solution will pop out sooner or later.

[Paul Rubin]

Post by Lawrence D'Oliveiro
This is my answer after spending this afternoon learning Guile. Much
more wordy than the Python version I previously posted. Anybody know
how to do it better?

The "parenthesis pileup" aside, the following things jump out at me:

1) Your "range" function already exists, called "iota" (after the iota
operation in APL).

2) Even if it didn't exist, your recursive definition is messy.
This is more idiomatic:

(define (range n)
(define (go n a)
(if (< n 0)
a
(go (1- n) (cons n a))))
(go n 0))

Note that the accumulation parameter in "go" makes go tail recursive, so
it uses a fixed number of stack cells.

2) Similarly the "score" function looks translated from C to Scheme or
something like that. Generally, the use of set! is a code smell in
Scheme. It's preferable to use recursion and combinators like map and
filter. In Haskell, set! doesn't even exist in any convenient form.

Without destructive updates, you end up using a programming style with a
rather different set of idioms. Scheme was an early enabler of that
style. Lisp predated Scheme and was sort of an intermediate step.
See the SICP book for a deeper intro.

[Paul Rubin]

(define (range n) ...

Oops:

(define (range n)
(define (go n a)
(if (< n 0)
a
(go (1- n) (cons n a))))
(go (1- n) '()))

[Lawrence D'Oliveiro]

Post by Paul Rubin
1) Your "range" function already exists, called "iota" (after the iota
operation in APL).

Just checked, and I don’t even need to import anything to use it. Thanks.

Post by Paul Rubin
2) Similarly the "score" function looks translated from C to Scheme or
something like that.

It was my attempt to translate this Python code:

def score(candidate, answer) :
return \
(
sum(a == b for a, b in zip(candidate, answer)),
sum
(
i != j and a == b
for i, a in enumerate(candidate)
for j, b in enumerate(answer)
)
)
#end score

[Paul Rubin]

Post by Lawrence D'Oliveiro
sum(a == b for a, b in zip(candidate, answer))

zip is in srfi-1 but I would write this as

(length (filter identity (map = candidate answer)))

Post by Lawrence D'Oliveiro
sum
(
i != j and a == b
for i, a in enumerate(candidate)
for j, b in enumerate(answer)
)
)

In Python you might avoid the nested loops by writing that in terms of
set or multiset (collections.Counter) intersections. In Scheme, maybe
this:

(define (score2 candidate answer)
(let* ((well-placed (length (filter identity (map = candidate answer))))
(wrongly-placed (- (length (lset-intersection = candidate answer))
well-placed)))
(values well-placed wrongly-placed)))

lset-intersection is also in srfi-1. Here, candidate and answer are
both lists of digits. I don't know the running time (complexity) of
lset-intersection. In Python, sets are represented with hashes so the
equivalent operation should take linear time. Scheme might uses hashes
(linear time), sorted lists (n log n time), or quadratic time.

[Lawrence D'Oliveiro]

Post by Paul Rubin

sum
(
i != j and a == b for i, a in enumerate(candidate)
for j, b in enumerate(answer)
)

In Python you might avoid the nested loops by writing that in terms of
set or multiset (collections.Counter) intersections.

Why would that be better?

[George Neuner]

On Wed, 28 Feb 2024 21:57:46 -0000 (UTC), Lawrence D'Oliveiro

Post by Lawrence D'Oliveiro

Post by Paul Rubin

sum
(
i != j and a == b for i, a in enumerate(candidate)
for j, b in enumerate(answer)
)

In Python you might avoid the nested loops by writing that in terms of
set or multiset (collections.Counter) intersections.

Why would that be better?

Because almost all of Python's standard libraries are written in C.
Most versions of Python are just too slow to use for anything but toy
programs.

[Paul Rubin]

Post by Lawrence D'Oliveiro

Post by Paul Rubin
In Python you might avoid the nested loops by writing that in terms of
set or multiset (collections.Counter) intersections.

Why would that be better?

You are trying to handle N digits and your algorithm does O(N**2)
comparisons. Ok, I guess the whole search strategy is impractical if N
is larger than just a few, and in traditional Mastermind N=4, so maybe
that isn't an issue. But the idea is that sets in Python are
implemented with hashing, so finding a set intersection is takes O(N).

A purely functional approach (idk how lset in Guile works) might use
sorted lists for O(N log N) complexity, but either beats O(N**2).

[Lawrence D'Oliveiro]

Post by Paul Rubin

Post by Lawrence D'Oliveiro
Why would that be better?

You are trying to handle N digits and your algorithm does O(N**2)
comparisons. Ok, I guess the whole search strategy is impractical if N
is larger than just a few, and in traditional Mastermind N=4, so maybe
that isn't an issue.

“Premature optimization is the root of all evil.”
-- variously attributed to Tony Hoare or Donald Knuth

[Paul Rubin]

Post by Lawrence D'Oliveiro
“Premature optimization is the root of all evil.”

I would say using set intersections is clearer and more concise than
that code with loop indices too. It is what you were trying to compute
in the first place. Same idea as writing a matrix product as A*B
instead of as some messy thing with subscripts.

[Lawrence D'Oliveiro]

Same idea as writing a matrix product as A*B instead of as some messy
thing with subscripts.

Somebody still has to write the underlying code with the subscripts.

[Paul Rubin]

Post by Lawrence D'Oliveiro
Somebody still has to write the underlying code with the subscripts.

Sure, that's pushed down into a library or helper function though.
Doing it at the higher level is related to the "primitive obsession"
antipattern. It's normal to bang out code like that when you're trying
to keep moving, but refactoring afterwards generally helps. Here's a
refactored Python version of the score function I posted earlier:

def score(answer: int, candidate: int) -> Tuple[int,int]:
a = digits(answer)
b = digits(candidate)
well_placed = sum(x==y for x,y in zip(a,b))
wrongly_placed = len(set(a) & set(b)) - well_placed
return well_placed, wrongly_placed

Maybe it's more correct to use multisets (collections.Counter) instead
of sets, depending on how the problem is specified.

[Lawrence D'Oliveiro]

Post by Lawrence D'Oliveiro
Somebody still has to write the underlying code with the subscripts.

Sure, that's pushed down into a library or helper function though. Doing
it at the higher level is related to the "primitive obsession"
antipattern.

I only push things into separate/library functions if I’m going to reuse
them. Splitting things off just for the sake of doing so is what we could
call a “fragmentation smell” or a “gratuitous hierarchy antipattern”.

[Paul Rubin]

Post by Lawrence D'Oliveiro
I only push things into separate/library functions if I’m going to reuse
them. Splitting things off just for the sake of doing so is what we could
call a “fragmentation smell” or a “gratuitous hierarchy antipattern”.

In the case of matrix multiplication, the code is already in a linear
algebra library. In the case of set intersection, it is built into
Python's set type.

[Kaz Kylheku]

Post by Lawrence D'Oliveiro

Post by Paul Rubin

Post by Lawrence D'Oliveiro
Why would that be better?

You are trying to handle N digits and your algorithm does O(N**2)
comparisons. Ok, I guess the whole search strategy is impractical if N
is larger than just a few, and in traditional Mastermind N=4, so maybe
that isn't an issue.

“Premature optimization is the root of all evil.”
-- variously attributed to Tony Hoare or Donald Knuth

Pinning it down more precisely at this stage would be premature
attribution.

[Nuno Silva]

Post by Kaz Kylheku

Post by Lawrence D'Oliveiro

Post by Paul Rubin

Post by Lawrence D'Oliveiro
Why would that be better?

You are trying to handle N digits and your algorithm does O(N**2)
comparisons. Ok, I guess the whole search strategy is impractical if N
is larger than just a few, and in traditional Mastermind N=4, so maybe
that isn't an issue.

“Premature optimization is the root of all evil.”
-- variously attributed to Tony Hoare or Donald Knuth

Pinning it down more precisely at this stage would be premature
attribution.

I sometimes feel that this specific sentence from Knuth's quote might be
being used as a way to discourage even thinking about optimization, when
the intent of the whole quote might be actually the opposite: yes, there
are places where it doesn't bring much benefit to optimize, but there
are also the parts where it *does*.

"We should forget about small efficiencies, say about 97% of the
time: premature optimization is the root of all evil. Yet we should
not pass up our opportunities in that critical 3%."


But I'll read the whole thing when I can, at this point I'm not even
sure I've read this before or not...

https://dl.acm.org/doi/10.1145/356635.356640

[Lawrence D'Oliveiro]

yes, there are places where it doesn't bring much benefit to optimize,
but there are also the parts where it *does*.

The point being, you determine those by actually running benchmarks on
your code. Programmers who assume they know which parts need speeding up a
priori are often surprised to discover they’re wrong.

[HenHanna]

sum ( i != j and a == b for i, a in enumerate(candidate)
for j, b in enumerate(answer) )


--------- i certainly enjoyed seeing this code. Thanks for sharing it!


it's written in a [functional] or [mathematical] or "comprehensive" style.

Post by Nuno Silva

Post by Lawrence D'Oliveiro
“Premature optimization is the root of all evil.”
----- variously attributed to Tony Hoare or Donald Knuth

and not Perlis?

Post by Nuno Silva

Pinning it down more precisely at this stage would be premature attribution.

I sometimes feel that this specific sentence from Knuth's quote might be
being used as a way to discourage even thinking about optimization, when
the intent of the whole quote might be actually the opposite: yes, there
are places where it doesn't bring much benefit to optimize, but there
are also the parts where it *does*.

[Lawrence D'Oliveiro]

Post by HenHanna
it's written in a [functional] or [mathematical] or
"comprehensive" style.

Yup, I like writing functional constructs in primarily-procedural
languages. It’s better than trying to work in supposedly pure-functional
languages.

Python also uses the term “comprehension” for certain uses of that kind of
construct.

Post by HenHanna
and not Perlis?

I like another quote of his: “There are two ways to write error-free
programs; only the third one works.”

[HenHanna]

Post by Lawrence D'Oliveiro

Post by HenHanna
it's written in a [functional] or [mathematical] or "comprehensive" style.

Yup, I like writing functional constructs in primarily-procedural
languages. It’s better than trying to work in supposedly pure-functional
languages.
Python also uses the term “comprehension” for certain uses of that kind of construct.

Post by HenHanna
and not Perlis?

I like another quote of his: “There are two ways to write error-free
programs; only the third one works.”

i love it.... i thought it must be THE most enigmatic of his quotes, but...



https://www.cs.yale.edu/homes/perlis-alan/quotes.html


38. Structured Programming supports the law of the excluded middle. --------- ??????????

39. Re graphics: A picture is worth 10K words - but only those to describe the picture. Hardly any sets of 10K words can be adequately described with pictures.

40. There are two ways to write error-free programs; only the third one works.

41. Some programming languages manage to absorb change, but withstand progress. -------- For example?????

42. You can measure a programmer's perspective by noting his attitude on the continuing vitality of FORTRAN.

43. In software systems, it is often the early bird that makes the worm. ---------- meaning, ...that introduces the BUG ?

44.Sometimes I think the only universal in the computing field is the fetch-execute cycle.

[Lawrence D'Oliveiro]

Post by HenHanna
41. Some programming languages manage to absorb change, but withstand
progress. -------- For example?????

PHP being the obvious one. It manages to copy features from other
languages (initially Perl, currently Python) without quite understanding
how they’re supposed to work, and so completely botching them.

Post by HenHanna
42. You can measure a programmer's perspective by noting his attitude on
the continuing vitality of FORTRAN.

That was the first language I learned, even before I got my hands on a
computer, back in the day. I have been through so many others since then,
I thought Fortran had had its day.

But have you looked at the specs for Fortran-90 onwards? It has gone free-
format. It has proper control constructs, so you can write entire programs
without statement labels at all. It has local variables and recursion. It
has structured types and something resembling object orientation. (OK, so
pointers might still be a bit clunky.)

And above all, it has “coarrays”, for partitioning work among the nodes of
a massively parallel supercomputer. If you want proof that Fortran is
still relevant to the modern computing era, this is it.

[Andreas Eder]

Post by Paul Rubin
1) Your "range" function already exists, called "iota" (after the iota
operation in APL).
2) Even if it didn't exist, your recursive definition is messy.
(define (range n)
(define (go n a)
(if (< n 0)
a
(go (1- n) (cons n a))))
(go n 0))

I would write it without the second define using a named let:

(define (range n)
(let go ((n n) (a '()))
(if (< n 0)
a
(go (1- n) (cons n a)))))

'Andreas

[Paul Rubin]

Post by Lawrence D'Oliveiro
(define (range n)
(let go ((n n) (a '())) ...

Oh interesting, I didn't know that syntax. I will check the docs. Thanks.

[Lawrence D'Oliveiro]

Post by Lawrence D'Oliveiro
(define (range n)
(let go ((n n) (a '()))
(if (< n 0)
a
(go (1- n) (cons n a)))))

Interesting. r6rs (section 11.4.6) doesn’t seem to allow that form. Also
it would seem you would need “letrec” rather than “let”, but that doesn’t
work for me.

[George Neuner]

On Fri, 1 Mar 2024 21:08:13 -0000 (UTC), Lawrence D'Oliveiro

Post by Lawrence D'Oliveiro

Post by Lawrence D'Oliveiro
(define (range n)
(let go ((n n) (a '()))
(if (< n 0)
a
(go (1- n) (cons n a)))))

Interesting. r6rs (section 11.4.6) doesn’t seem to allow that form. Also
it would seem you would need “letrec” rather than “let”, but that doesn’t
work for me.

Named Let is not a binding construct - it's a looping construct.
See 11.16

[Paul Rubin]

Post by George Neuner
Named Let is not a binding construct - it's a looping construct.
See 11.16

Thanks, I wonder if that is something relatively recent (i.e. arrived
between r4rs and r6rs). It is kind of ugly and I'm used to seeing
nested defines. Maybe there are some situations where the named let is
more convenient. Or maybe I can get used to it.

Part of the idea of Guile was to be the execution engine for various
other languages that would get transpiled to Scheme, but idk if that
went anywhere.

[George Neuner]

On Fri, 01 Mar 2024 14:24:37 -0800, Paul Rubin

Post by Paul Rubin

Post by George Neuner
Named Let is not a binding construct - it's a looping construct.
See 11.16

Thanks, I wonder if that is something relatively recent (i.e. arrived
between r4rs and r6rs). It is kind of ugly and I'm used to seeing
nested defines. Maybe there are some situations where the named let is
more convenient. Or maybe I can get used to it.
Part of the idea of Guile was to be the execution engine for various
other languages that would get transpiled to Scheme, but idk if that
went anywhere.

Named Let was formally added to Scheme in R5RS, but it was recognized
as being a legal variant at least as far back as R3RS.


=======================

R3RS [4.2.4 Iteration]:
R4RS [4.2.4 Iteration]:

:

(let <variable> <bindings> <body>) syntax

Some implementations of Scheme permit a variant on the
syntax of let called \named let" which provides a more
general looping construct than do, and may also be used
to express recursions.

Named let has the same syntax and semantics as ordinary
let except that <variable> is bound within <body> to
a procedure whose formal arguments are the bound vari-
ables and whose body is <body>. Thus the execution of
hbodyi may be repeated by invoking the procedure named
by <variable>.

(let loop ((numbers '(3 -2 1 6 -5))
(nonneg '())
(neg '()))
(cond ((null? numbers) (list nonneg neg))
((>= (car numbers) 0)
(loop (cdr numbers)
(cons (car numbers) nonneg)
neg))
((< (car numbers) 0)
(loop (cdr numbers)
nonneg
(cons (car numbers) neg)))))
==> ((6 1 3) (-5 -2))

=======================

R5RS [4.2.4 Iteration]:

:

(let <variable> <bindings> <body>) library syntax

“Named let” is a variant on the syntax of let which pro-
vides a more general looping construct than do and may
also be used to express recursions. It has the same syn-
tax and semantics as ordinary let except that <variable>
is bound within <body> to a procedure whose formal argu-
ments are the bound variables and whose body is <body>.
Thus the execution of <body> may be repeated by invoking
the procedure named by <variable>.

:

=======================



Unfortunately I don't have any references older than R3RS.

George

[B. Pym]

Post by Lawrence D'Oliveiro
(define (range n)
(let go ((n n) (a '()))
(if (< n 0)
a
(go (1- n) (cons n a)))))

Looks good.

Using "do":

(define (range n)
(do ((i n (- i 1))
(a '() (cons i a)))
((< i 0) a)))


Using "unfold-right" in Gauche Scheme:

(use srfi-1)

Gauche doesn't have "1-".

(define (1- n) (- n 1))

(define (range n) (unfold-right negative? values 1- n))

(range 9)
===>
(0 1 2 3 4 5 6 7 8 9)