Four fours to get any number

Question

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[0]
    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[0]:
                return n,[l,result[1]]

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)

Answer 1

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.

Answer 2

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.