Constraints solving a silly number puzzle

A toy example of a constraints solver, provided by Cognisys (https://cognisys.co.uk/). We are given four four-digit numbers, and told for each how many digits are a) in the right place, b) in the wrong place. For example:

1453 => “one digit is in the right place, and one is in the wrong place”

There are (implicitly) no repeat digits. Guess the combination.

You could do this iteratively, and solving by hand, we’d start with the strongest constraint first. But we’re programmers, and thinking is hard. Since there’s only 10,000 combinations, why not just test them all?

def right(cand, tgt):
    return sum(1 for c, t in zip(list(cand), list(tgt)) if c == t)

def wrong(cand, tgt):
    return sum(1 for i, c in enumerate(list(cand)) if c in tgt and tgt.index(c) != i)

def one(cand):
    return right(cand, "7068") == 1 and wrong(cand, "7068") == 0

def two(cand):
    return right(cand, "0378") == 0 and wrong(cand, "0378") == 2

def three(cand):
    return right(cand, "1453") == 2 and wrong(cand, "1453") == 0

def four(cand):
    return right(cand, "6792") == 1 and wrong(cand, "6792") == 1

def solve_bruteforce():
    for i in range(10_000):
        cand = str(i).rjust(4, "0")
        if one(cand) and two(cand) and three(cand) and four(cand):
            return i

print(solve_bruteforce())

Actually, there’s possibly one better way. What is we try a hill-climbing (or arguably, a “genetic”-type) approach?

def solve_hillclimb():
    from random import randint
    def fitness(cand):
        return int(one(c)) + int(two(c)) + int(three(c)) + int(four(c))
    best = [randint(0,9) for _ in range(4)]
    score = 0
    while True:
        cand = best
        cand[randint(0, 3)] = randint(0,9)
        c = "".join(str(c) for c in cand)
        new_score = fitness(c)
        if new_score > score:
            best = cand
            score = new_score
        if score == 4:
            break
    return int("".join(str(c) for c in cand))

print(solve_hillclimb())

Timing results were interesting - about 27 ms for both. If I’m honest, lots of time here is being wasted doing debatably necessary type conversions. For larger puzzles, the hillclimb should be faster, but again… we’re trying 10,000 combinations here.