Problem #109 concerns checking out in a game of darts. The question reads:
My solution for this problem is another example of the powers of brute force. Here’s my solution:
Solution #1: Brute Force Approach
We simply check every combination of dart scores that end in a double and count the ones with a total less than 100. There are 62 possibilities for each of the three darts, so at most there are 62^3 = 238328 possibilities to consider. Here’s an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #109
'''
import time
def checkout(n):
possible = [25,50]
for x in range(1,21):
possible.append(x)
possible.append(2*x)
possible.append(3*x)
possible = sorted(possible)
total = 0
for a in possible:
v = n-a
for b in possible:
if(b>a):
break
else:
w = v-b
if(w%2==0 and (w<=40 or w==50)):
total+=1
return total
def projectEulerProblemOneHundredNine(n):
possible = [25,50]
doubles = []
for x in range(1,21):
possible.append(x)
possible.append(2*x)
possible.append(3*x)
doubles.append(2*x)
possible = sorted(possible)
doubles.append(50)
total = 0
l = len(possible)
for i in range(l):
for j in range(i,l):
v = possible[i]+possible[j]
for d in doubles:
if v+d<n:
total+=1
else:
break
if v>=n:
break
for i in range(l):
v = possible[i]
for d in doubles:
if v+d<n:
total+=1
else:
break
if v>=n:
break
for d in doubles:
if d<n:
total+=1
else:
break
return total
start = time.time()
print projectEulerProblemOneHundredNine(100)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
38182
--- 0.00199699401855 seconds ---
for input of n = 100.
'''
And with that, we’re done. While this may have been a brute force solution, it was more than efficient enough for this problem. I may come back to this problem eventually to look for a different approach.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 