SPOILER ALTER: THIS POST CONTAINS A POSSIBLE SOLUTION
you are allowed to mix.
15 is neither divisable by 6 nor by nine, but 9 + 6 = 15
I was aware of that, thats whhy I wrote:
"or any combination of 6, 9, 20"
I guess, trying to find the result with divisions and remainders is
overly complicated.
Python 2.6.4 (r264:75706, Jul 1 2010, 12:52:41)
[GCC 4.2.1 20070719 [FreeBSD]] on freebsd8
Type "help", "copyright", "credits" or "license" for more information.
MODULO_COMBINATIONS = [[20], [9], [6],
... [20, 9], [20, 6], [9, 20],
... [9, 6], [6, 20], [6, 9],
... [20, 9, 6], [20, 6, 9], [9, 20, 6],
... [9, 6, 20], [6, 20, 9], [6, 9, 20]] ... tmp = list()
... for combination in MODULO_COMBINATIONS:
... remainder = number
... for modulo_value in combination:
... if remainder == 0:
... remainder = None
... break
...
... result = remainder % modulo_value
...
... if result == remainder :
... remainder = None
... break
...
... remainder = result
...
... if remainder == 0:
... tmp.append(str(combination))
... return(tmp)
...
print(apply_combinations_on(15)) ['[9, 6]']
What is so over complicated about it?
What I meant with complicated is your mathematical assumption about
modulos, which are probably not obvious to everybody on the first glance.
Saying, that you can find out, whether for integers a,b.c,n
the equation
n = a*6 + b*9 + c*20 is true
by verifying
whether
n mod 6 == 0
or
n mod 9 == 0
or
(n mod 6) mod 9 == 0
or
(n mod 9) mod 6 == 0
Trial error is not so smart, but much easier to explain to beginners.
One can even return a,b,c for verification.
Being a little (and incrementally) smart, the search space can then be
reduced by some degrees
with rather easy to explain and incremental assumptions,
For given example the run times are so short, that it's not really an issue.
Another advantage of brute force is, that you can return a,b,c
and not only say, whether a,b,c exist.
This allows simple verification or assertions during debugging and learning.
# plain brute force.
#------------------------------------
def can_buy(n_nuggets):
for a in range (n_nuggets):
for b in range (n_nuggets):
for c in range (n_nuggets):
print "trying for %2d: %2d %2d %2d" % (n,a,b,c)
if 6*a + 9*b + 20*c == n_nuggets:
return (a,b,c)
return ()
# brute force but reduce the upper limit for each loop by saying,
# that one can stop if one a*6 > n or b*9 > n or c*20 >n
#------------------------------------------
def can_buy(n_nuggets):
for a in range (n_nuggets / 6 + 1):
for b in range (n_nuggets / 9 + 1):
for c in range (n_nuggets / 20 + 1):
print "trying for %2d: %2d %2d %2d" % (n,a,b,c)
if 6*a + 9*b + 20*c == n_nuggets:
return (a,b,c)
return ()
# as above code, but try even less in inner loops by
# removing what has been taken in outer loop
#--------------------------------------------
def can_buy(n_nuggets):
for a in range (1, n_nuggets / 6 + 1):
left_6 = n)nuggets - a * 6
for b in range (1, left_6 / 9 + 1):
left_9 = left_6 - b * 9
for c in range (1, left_9/ 20 + 1):
print "trying for %2d: %2d %2d %2d" % (n,a,b,c)
if 6*a+9*b+20*c==n_nuggets:
return (a,b,c)
return ()
# as above code, but do less multiplications
# in inner loop
#-------------------------------------------
def can_buy(n_nuggets):
for a in range (1, n_nuggets / 6 + 1):
left_6 = n)nuggets - a * 6
for b in range (1, left_6 / 9 + 1):
left_9 = left_6 - b * 9
for c in range (1, left_9/ 20 + 1):
print "trying for %2d: %2d %2d %2d" % (n,a,b,c)
if 20*c == left_9:
return (a,b,c)
return ()
# as above code, but use modulo in inner loop
# ------------------------------------------
def can_buy(n_nuggets):
for a in range (1, n_nuggets / 6 + 1):
left_6 = n)nuggets - a * 6
for b in range (1, left_6 / 9 + 1):
left_9 = left_6 - b * 9
print "trying for %2d: %2d %2d c" % (n,a,b)
if left_9 % 20 == 0:
return (a,b,left_9/20)
return ()
