(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 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 surprises or two.

[Lawrence D'Oliveiro]

Post by HenHanna
Could you share a short, VERY Readable Pythonic code that solves this?

import itertools

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

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 answer in itertools.product(*(range(10),) * 3) :
if all \
(
score(candidate, answer) == required_score
for candidate, required_score in required_scores
) \
:
print(answer)
#end if
#end for

[HenHanna]

wow... Thank you... I'm glad i asked.



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

== the last clue is not required.

[Paul Rubin]

Post by HenHanna
Could you share a short, VERY Readable Pythonic code that solves this?

I like that approach. Here is my version:

from typing import Tuple
def digits(n): return n//100, (n//10)%10, n%10

def score(answer,n) -> Tuple[int,int]:
def count(*v): return sum(filter(bool,v))
x,y,z = digits(answer)
a,b,c = digits(n)

well_placed = count(a==x,b==y,c==z)
wrongly_placed = count(a in {y,z}, b in {x,z}, c in {x,y})
return well_placed, wrongly_placed

wanted = [(682,1,0),(614,0,1),(206,0,2),(738,0,0),(780,0,1)]

def check(n: int) -> bool:
return all(score(n,a)==(b,c) for a,b,c in wanted)

print(list(filter(check2, range(0,1000))))

[Paul Rubin]

Oops, garbled. Fixed here, and I updated to follow your naming
convention.
================================================================
from typing import Tuple
def digits(n): return n//100, (n//10)%10, n%10

def score(answer,candidate) -> Tuple[int,int]:
def count(*v): return sum(filter(bool,v))
x,y,z = digits(answer)
a,b,c = digits(candidate)

well_placed = count(a==x,b==y,c==z)
wrongly_placed = count(a in {y,z}, b in {x,z}, c in {x,y})
return well_placed, wrongly_placed

wanted = [(682,1,0),(614,0,1),(206,0,2),(738,0,0),(780,0,1)]

def check2(n: int) -> bool:
return all(score(n,candidate)==(right,wrong)
for candidate,right,wrong in wanted)

print(list(filter(check2, range(0,1000))))

[HenHanna]

wow... Thank you... I'm glad i asked.


HINT -- A mark of a great puzzle, this one contains a surprise (or two)
== the last 2 clues are not required.



1. Could there be a different approach? (not exhaustive search) ?


2. What's a nice tweak on this problem that
would call for a program that's just a bit longer, harder?

[Paul Rubin]

Post by HenHanna
1. Could there be a different approach? (not exhaustive search) ?

Yes, this type of puzzle is called a constraint satisfaction problem
(CSP). There is a big literature on how to solve those. Basically you
use the different clues to narrow the search space. There is a language
called Prolog which is designed for this type of problem. Beyond that,
there are tools called SAT solvers (SAT = boolean satisfiability
problem) that try to solve a related class of problems as efficiently as
they can. But, in general, there is no known algorithm that solves the
entire class efficiently, and probably none exists (this is the famous P
vs NP problem).

Post by HenHanna
2. What's a nice tweak on this problem that
would call for a program that's just a bit longer, harder?

I think it is ok the way it is.

[HenHanna]

bard.google.com (now Gemini) can't write Python code that solves this.

can ChatGPT do it?

Post by Paul Rubin

Post by HenHanna
1. Could there be a different approach? (not exhaustive search) ?

Yes, this type of puzzle is called a constraint satisfaction problem
(CSP). There is a big literature on how to solve those. Basically you
use the different clues to narrow the search space. There is a language
called Prolog which is designed for this type of problem.

i have Knuth's book on CSP... i'll check inside.


yes, i studied Prolog when i was younger. (Wrote a Prolog interpreter in Lisp, etc.)

Is this a typical easy exercise in Prolog programming? Could someone share Prolog code for it?

[Greg Ewing]

Post by Lawrence D'Oliveiro
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)
)
)

This is not correct. score((1,1,1), (1,1,2)) gives (2,4). According to
the usual rules of Mastermind, it should be (2, 0).

[Lawrence D'Oliveiro]

Post by Greg Ewing
This is not correct. score((1,1,1), (1,1,2)) gives (2,4).

As a general solution, you would be right. As a solution to this
particular problem (with no repeated numbers), it did the job.

[Lawrence D'Oliveiro]

Post by Greg Ewing
This is not correct. score((1,1,1), (1,1,2)) gives (2,4). According to
the usual rules of Mastermind, it should be (2, 0).

How about this as a more general Mastermind scoring function, then:

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)
for s in (set(i for i, (a, b) in enumerate(zip(candidate, answer)) if a == b),)
if i not in s and j not in s
)
)
#end score

[Paul Rubin]

This works for me:

from collections import Counter as multiset
def msum(m: multiset) -> int: return sum(m.values())
def digits(n: int) -> int: return n//100, (n//10)%10, n%10

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 = msum(multiset(a) & multiset(b)) - well_placed
return well_placed, wrongly_placed

print (score(111,112)) # prints (2, 0)

[Paul Rubin]

Post by HenHanna
Could you share a short, VERY Readable Pythonic code that solves this?

Here is my brute force solution. It prints the list [42] which means
that the 3-digit answer is 042.

def check(n: int) -> bool:
"""return true iff n satisfies all the constraints. n is a 3 digit number
possibly with leading zeros."""
a,b,c = n//100, (n//10)%10, n%10

# 682 -- one number correct and well placed
k1 = (a==6 or b==8 or c==2) and len({a,b,c} & {6,8,2})==1
# 614 -- one number correct but wrongly placed
k2 = a != 6 and b != 1 and c != 4 and \
len({a,b,c} & {6,1,4})==1
# 206 -- two numbers correct but wrongly placed
k3 = len({a,b,c} & {2,0,6})==2 and a!=2 and b!=0 and c!=6
# 738 -- nothing correct
k4 = len({a,b,c} & {7,3,8}) == 0
# 780 -- one number correct but wrongly placed
k5 = len({a,b,c} & {7,8,0})==1 and a!=7 and b!=8 and c!=1

return all([k1,k2,k3,k4,k5])

print(list(filter(check, range(0,1000))))