Problem of the Day
A new programming or logic puzzle every Mon-Fri

Comments:

• Foppe - 10 years, 9 months ago

  #! /usr/bin/pyhton
  
  i = 0
  j = 0
  k = 0
  l = 0
  m = 0
  n = 0
  
  counter = 0
  
  v = [0.03, 0.08, 0.33, 0.5, 2, 10]
  for i in range(333):
      for j in range(120):
          for k in range(30):
              for l in range(20):
                  for m in range(5):
                      for n in range(1):
                          c = i * v[0] + j * v[1] + k * v[2] + l * v[3] \
                              + m * v[4] + n * v[5]
                          if c == 10 and  c % 1 == 0:
                              counter = counter + 1
                              print(c)
                              print("%d * .03, %d * .08, %d * .33, %d * .5, \
                                  %d * 2, %d * 10" % (i, j, k, l, m, n))
  print(counter)
  

  ---

  $ time python change.py
  8934
  
  real    5m43.244s
  user    5m42.173s
  sys 0m0.620s
  

  reply permalink

• Foppe - 10 years, 9 months ago

  The range function is not inclusive so you need to add 1 to everyone of this. The final grand total is 8937

  reply permalink

• Max Burstein - 10 years, 9 months ago

  Definitely an interesting solution. Good stuff

  reply permalink

• vick - 10 years, 9 months ago

  I've found a small typo in line "for j in range(120):"

  I think, it should be "for j in range(125 + 1):", since 10 / 0.08 = 125

  Thus, grand total is 8939.

  Thank you for the nice solution!

  reply permalink

• Foppe - 10 years, 9 months ago

  The difference with the Haskell solution is due to rounding errors. When using integers I get the correct result 8954 with $10 <-> $10. Also I thought this would speed up a littlebit. #! /usr/bin/python

  i = 0
  j = 0
  k = 0
  l = 0
  m = 0
  n = 0
  
  counter = 0
  
  v = [3, 8, 33, 50, 200, 1000]
  for i in range(334):
      ii = i * v[0]
      for j in range(126):
          jj = j * v[1]
          for k in range(31):
              kk = k * v[2]
              for l in range(21):
                  ll = l * v[3]
                  for m in range(6):
                      mm = m * v[4]
                      for n in range(2):
                          nn = n * v[5]
                          c = ii + jj + kk + ll + mm + nn
                          if c == 1000:
                              counter = counter + 1
                              # You could add a print statement here if
                              # you want to see all solutions
  print(counter)
  

  reply permalink

• Foppe - 10 years, 9 months ago

  Optimization: By adding lines like for k in range(31): kk = k * v[2] if ii + jj + kk > 1000: # <- Added break # <- Added in all for loops this speeds up to $ time python change.py 8954

  real    0m9.733s
  user    0m9.710s
  sys 0m0.010s
  

  That's from 7 minutes to 10 seconds.

  reply permalink

• Foppe - 10 years, 9 months ago

  Formatted: for k in range(31): kk = k * v[2] if ii + jj + kk > 1000: # <- Added break # <- Added

  reply permalink

• Anonymous - 10 years, 9 months ago

  Awesome stuff man.

  reply permalink

• Max! - 10 years, 9 months ago

  In Wolfram Alpha : power series (1/((1-x^3)(1-x^8)(1-x^33)(1-x^50)(1-x^200)(1-x^1000)))

  Then expand terms till the 1000th coefficient and I see 8954 ways. Is my combinatorial equation incorrect? I wanted to find the right solution before trying to code it up.

  reply permalink

• Apanatshka - 10 years, 9 months ago

  That sounds about correct. My program gives back 8953, because I filtered the solution where you give back the $10 note as change.

  reply permalink

• Apanatshka - 10 years, 9 months ago

  Haskell implementation, not as trivial as I expected:

  import Data.List
  import Data.Ratio
  
  denominations = [3 % 100, 8 % 100, 33 % 100, 1 % 2, 2, 10, 50, 100]
  
  toChange = 10 :: Ratio Int
  
  making_change :: Ratio Int -> [Ratio Int] -> ([[(Int, Ratio Int)]], Int)
  making_change todo d = (map (\l -> zip l ds) lst, ans) -- go from large to small
    where
      ds = dropWhile (>= todo) $ reverse $ sort d
      (lst, ans) = mc todo ds
      mc :: Ratio Int -> [Ratio Int] -> ([[Int]], Int)
      mc t (d:ds) = (concatMap fst tries, sum $ map snd tries)
        where
          tries :: [([[Int]], Int)]
          tries = map (\(n,t') -> let (l,m) = mc t' ds in (map (n:) l,m)) possibles -- tries to use the other denominations to make change for the amount todo
          possibles = zip [0..] $ takeWhile (>= 0) $ scanl (-) t $ repeat d -- get a list of possible left over numbers
      mc t [] = if t == 0 then ([[]],1) else ([],0)
  
  answer = making_change toChange denominations
  
  main = print $ snd answer
  

  It prints 8953. If you write main = print $ fst answer you get the different ways in stead of the count.

  reply permalink

• btgrant - 10 years, 8 months ago

  Using integers like the Haskel submission, here's a solution in Scala:

  def countChange(money: Int, coins: List[Int]): Int = {
    if (coins.isEmpty || money < 0)
      0
    else if (money == 0)
      1
    else {
      countChange(money - coins.head, coins) + countChange(money, coins.tail)
    }
  }
  val denominations = List(3, 8, 33, 50, 200, 1000)
  val changeFor = 1000
  println(countChange(changeFor, denominations))
  

  reply permalink