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(n0.5),n2,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 resul

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.

StackExchange Code Review Q#77216, answer score: 5