XPost: comp.lang.scheme

On Sun, 25 Feb 2024 20:27:42 -0800, HenHanna wrote:

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

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)

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

On 2024-02-27, Paul Rubin <no.email@nospam.invalid> wrote:

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

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.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

Paul Rubin <no.email@nospam.invalid> writes:

(define (range n) ...

Oops:

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

On Tue, 27 Feb 2024 13:36:25 -0800, Paul Rubin wrote:

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.

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

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)))

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

On Tue, 27 Feb 2024 17:46:48 -0800, Paul Rubin wrote:

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

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?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

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).

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

On Wed, 28 Feb 2024 21:57:46 -0000 (UTC), Lawrence D'Oliveiro
<ldo@nz.invalid> wrote:

On Tue, 27 Feb 2024 17:46:48 -0800, Paul Rubin wrote:

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

On Wed, 28 Feb 2024 15:54:48 -0800, Paul Rubin wrote:

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

“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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

On Thu, 29 Feb 2024 14:21:12 -0800, Paul Rubin wrote:

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

On 2024-02-29, Lawrence D'Oliveiro <ldo@nz.invalid> wrote:

On Wed, 28 Feb 2024 15:54:48 -0800, Paul Rubin wrote:

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

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.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

On Thu, 29 Feb 2024 18:18:31 -0800, Paul Rubin wrote:

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

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”.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

On Di 27 Feb 2024 at 13:36, Paul Rubin <no.email@nospam.invalid> wrote:

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))

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

--
ceterum censeo redmondinem esse delendam

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

On 2024-03-01, Kaz Kylheku wrote:

On 2024-02-29, Lawrence D'Oliveiro <ldo@nz.invalid> wrote:

On Wed, 28 Feb 2024 15:54:48 -0800, Paul Rubin wrote:

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

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

--
Nuno Silva
(not reading comp.lang.scheme, just comp.lang.lisp)

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

On Sun, 03 Mar 2024 09:23:02 +0000, Nuno Silva wrote:

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

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.



Nuno Silva wrote:

On 2024-03-01, Kaz Kylheku wrote:

On 2024-02-29, Lawrence D'Oliveiro <ldo@nz.invalid> wrote: .....

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

and not Perlis?

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*.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

On Sun, 3 Mar 2024 22:56:25 +0000, HenHanna wrote:

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.

and not Perlis?

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

Lawrence D'Oliveiro wrote:

On Sun, 3 Mar 2024 22:56:25 +0000, HenHanna wrote:

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.

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.lang.scheme

On Mon, 4 Mar 2024 10:30:26 +0000, HenHanna wrote:

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.

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)