# Four fours to get any number

I decided to solve a problem from Code Golf called the four fours.

Problem description:

The Four fours puzzle is a popular recreational mathematical puzzle that involves using exactly four 4s (and no other number) and a defined set of operations to reach every number from 0 to a given maximum.

In this version, the only following operators are allowed:

• Any grouping symbols may be used
• Addition (+), Subtraction (-), Multiplication (*), Division (/)
• Factorial (!), Gamma function (Γ)
• Exponentiation (^), Square root (√) *Concatenation (eg. 44 is two 4s) Decimal point (eg. 4.4 is two 4s), Overbar (eg. .4~ = 4/9)

Some assumption/changes I made:

• I assumed that squaring a number is ok (using 4**2 or 16)
• I assumed that decimal values, in the cases where they occur can be truncated (4.9 = 4)

## Description of the algorithm

First I create a list of all the possible start values, that is:

• The number itself
• The number squared
• The sqrt of the number
• The factorial of the number
• The gamma function of the number (factorial(number -1))

Then I iterate throu them with the random_reduce function that 'reduces' the list by applying each time a random function.

The function takes about 2 secons for all numbers upto a 100, finding a way to create all the numbers along the way.

I am looking for code-style advice and maybe a better algorithm suggestion.

from __future__ import division

import random
import operator as op
import math

def get_starts(lst,n):
sqrt,power,fact,gamma = int(n**0.5),n**2,math.factorial(n),math.factorial(n-1)
return ( [a,b,c,d] for a in (sqrt,n,power,fact,gamma) \
for b in (sqrt,n,power,fact,gamma) for c in (sqrt,n,power,fact,gamma) \
for d in (sqrt,n,power,fact,gamma))

def random_reduce(lst,functions):
functions_used = []
result = lst
for i in lst[1:]:
fun = random.choice(functions)
functions_used.append(fun)
result = fun(result,i)
return result,[i.__name__ for i in functions_used]

def how_to_obtain(n,lst,functions):
for i in range(500):
for l in get_starts(lst,4):
result = random_reduce(l,functions)
if n == result:
return n,[l,result]

def concat(a,b):
return int(str(a) + str(b))

def div(a,b):
return a // b

def solve_44(max_):
numbers_solutions = {}
for i in range(max_):
numbers_solutions[i] = how_to_obtain(i,[4,4,4,4],[concat, op.add, op.mul, op.sub,
div, op.pow, op.mod])

return numbers_solutions

def ratio_of_Nones_in_dictionary(dict_):
return (len({i:dict_[i] for i in dict_ if dict_[i] == None}) / len(dict_))

def main(max_):
solution = solve_44(max_)
for i in solution:
print(solution[i])
print("The random search failed to find a solution {}% of the times.".format(
ratio_of_Nones_in_dictionary(solution)*100))

if __name__ == "__main__":
main(100)


## 2 Answers

I am looking for code-style advice and maybe a better algorithm suggestion.

As for coding style, first and foremost, please follow PEP8.

### Simplify

You could simplify get_starts using product from itertools:

def get_starts(n):
sqrt, power, fact, gamma = int(n ** 0.5), n ** 2, math.factorial(n), math.factorial(n - 1)
return product((sqrt, n, power, fact, gamma), repeat=4)


I also dropped the unused lst parameter. In fact many of the functions have unused parameters, remove them everywhere.

### Use generators, they are awesome

Since you accumulate solutions in an array, the program seems to freeze for a few seconds while calculating, rather than printing the solutions that are ready. You could improve that by using a generator instead, for example:

def solve_44(max_):
for i in range(max_):
yield how_to_obtain(i, [concat, op.add, op.mul, op.sub, div, op.pow, op.mod])

def main(max_):
none_count = 0
for solution in solve_44(max_):
print(solution)
if solution is None:
none_count += 1
print("The random search failed to find a solution {}% of the times.".format(
none_count / max_ * 100))


Another correction here is using is None instead of == None for comparing with None values.

As a rule, doing maths is quicker than playing with strings. In this case, a bit of testing suggests that mixing the two gives the best performance. You can speed up your concat operation by a factor of 2 on that basis:

>>> import math
>>> def concat_strings(a, b):
"""Original version, converts both numbers to strings and back."""
return int(str(a) + str(b))

>>> def do_maths(a, b):
"""Pure mathematical version."""
return b + (a * (10 ** (int(math.log(b, 10)) + 1)))

>>> def combined(a, b):
"""Pragmatic version; avoid relatively slow library call."""
return b + (a * (10 ** len(str(b))))

>>> tests = [(1, 2), (12, 3), (1, 23), (1, 234), (12, 34), (123, 4)]
>>> for t in tests:
assert concat_strings(*t) == do_maths(*t) == combined(*t)

>>> import timeit
>>> setup = "from __main__ import tests, concat_strings, do_maths, combined"
>>> for method in ['concat_strings', 'do_maths', 'combined']:
print method,
timeit.timeit("for t in tests: {}(*t)".format(method), setup=setup)

concat_strings
10.974838972091675
do_maths
6.453880071640015
combined
4.8371992111206055


Also, note that your div function is available as operator.floordiv.