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)