KeiruaProd

I help my clients acquire new users and make more money with their web businesses. I have ten years of experience with SaaS projects. If that’s something you need help with, we should get in touch!
< Back to article list

Solving Countle/Countdown/Le compte est bon

The problem

Countle is a fun problem, a mix between Wordle and the numbers round of the Countdown Game Show.

You are provided with a target number (ex:564), a list of numbers (ex: [2, 3, 7, 8, 50, 75]), and you should combine them with the standard operations (+, -, /, *) in order to reach the target. No negative numbers (2-3=-1 is not a possible operation), and only integer division (17/5=3.4 is not allowed).

In the french version, six numbers are chosen at random in the set {1,2,…,9,10, 25, 50, 75, 100} and another number between 1 and 999 is also picked at random as the target.

Here is a possible solution:

In this post, we’ll implement backtracking in order both to solve any problem, and to solve all the problems from countle.

I’ve found solving them by hand to be quite frustrating, but writing a solver was quite fun.

Solving one problem

A way to solve those problems is to use backtracking. We’ll keep a list of the states, add more states until with explored all the possible states and not found a solution.

We are not interested in the shortest solution, and we do not want all the solutions. All we care about is to find ONE solution.

def search(target, initial_numbers):
    # a state is a list of operations, as well as a list of numbers
    # At first, we have performed no operation: the operation list is empty
    # and we have all the starting numbers
    state = [([], list(sorted(initial_numbers)))]
    seen = set()
    while len(state) > 0:
        ops_history, numbers = state.pop(0)
        # We generate every pair (i, j) of indices (i!=j)
        # for every possible operation (+, -, /, *). 
        for i in range(len(numbers)):
            for j in range(len(numbers)):
                if i == j:
                    continue
                a,b = numbers[i],numbers[j]

                for op in ["+", "-", "*", "/"]:
                    values = numbers[:]
                    values.remove(a)
                    values.remove(b)
                    if op == "+":
                        new_val = a+b
                    if op == "*":
                        new_val = a*b
                    if op == "-":
                        new_val = a-b
                        if new_val < 0:
                            continue
                    if op == "/":
                        if b == 0 or a%b != 0:
                            continue
                        new_val = a//b

                    # Now we can create a new state:
                    #  - we already removed the 2 numbers we used from the list,
                    # but now we add the result of their operation
                    #  - we add the operation we realized to the list of operation
                    new_ops_history = ops_history + [[a, op, b, new_val]]
                    # If we reached the target value, we are done
                    if new_val == target:
                        return new_ops_history
                    # If this state has not been reached before, we stack it
                    all_values = list(sorted(values + [new_val]))
                    hashed = ".".join(map(str,all_values))
                    if hashed not in seen:
                        seen.add(hashed)
                        state.append([new_ops_history, all_values])
    return None

Now we can give it a problem to solve:

if __name__ == "__main__":
    target = 564
    initial_numbers = [ 2,3,7,8, 50, 75]

    solution = search(target, initial_numbers)
    if solution is not None:
        for a, op, b, new_val in solution:
            print(f"{a} {op} {b} = {new_val}")      
    else:
        print("no solution found")

Yay, it works:

$ python solve_one.py
564 [2, 3, 7, 8, 50, 75]
2 * 7 = 14
3 + 8 = 11
11 * 50 = 550
14 + 550 = 564

Solving all problems

Countle has one problem a day for many days of the year 2022. You can download all problems as json. Use the developper toolbar to open it correctly:

https://www.countle.org/2022.json

With our solver, we can now solve all those problems in a few instants:

def print_solution(solution):
    for a, op, b, new_val in solution:
        print(f"{a} {op} {b} = {new_val}")

def benchmark(problems, callback):
    nb_solved = 0
    # The json is in this form:
    # {
    #   "2022-06-28": "954.25.100.50.7.8.6",
    #   "2022-06-29": "589.25.75.50.100.7.3",
    # }
    for day, problem in problems.items():
        # Extract the numbers from the "954.25.100.50.7.8.6" format
        numbers = list(map(int,problem.split('.')))
        # The first number is the target that you have to reach
        # by combining the other numbers
        target, initial_numbers = numbers[0], numbers[1:]
        solution = callback(target,initial_numbers)
        if solution is not None:
            nb_solved += 1
            print(target, initial_numbers)
            print_solution(solution)    
            print()
    return (nb_solved, len(problems.values()))

if __name__ == "__main__":
    problems = json.loads(open("2022.json").read())
    nb_solved, nb_problems = benchmark(problems, search)
    print(f"solved {nb_solved}/{nb_problems}")