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