fork download
copy 
  1. import random
  2. from math import inf
  3.  
  4. def alg(demand, supply, depth = 0):
  5.     if not demand: return 0
  6.  
  7.     (wanted_len, wanted_count) = demand[0]
  8.  
  9.     indent = "   " * depth
  10.     print(indent + f"Making {demand} with {supply}")
  11.  
  12.     options = []
  13.  
  14.     for i, (supply_len, supply_count) in enumerate(supply):
  15.         if supply_len >= wanted_len:
  16.             # copy them for mutation
  17.             new_demand = demand[::]
  18.             new_supply = supply[::]
  19.  
  20.             add_pipe(wanted_len, -1, new_demand)
  21.             add_pipe(supply_len, -1, new_supply)
  22.  
  23.             if supply_len > wanted_len:
  24.                 add_pipe(supply_len - wanted_len, 1, new_supply)
  25.  
  26.             options.append(
  27.                 alg(new_demand, new_supply, depth + 1)
  28.                 + (1 if supply_count == inf else 0))
  29.  
  30.     res = min(options)
  31.     print(indent + f"Best option is {res} out of {options}")
  32.     return res
  33.  
  34.  
  35.  
  36. def add_pipe(new_pipe_len, amount, to_pipes):
  37.     if amount < -1 or amount > 1: raise Exception("Can add/remove no more than 1 at a time.")
  38.     if new_pipe_len == 0: return
  39.  
  40.     for i, (pipe_len, pipe_count) in enumerate(to_pipes):
  41.         if new_pipe_len == pipe_len: # perfect match!
  42.             new_amount = pipe_count + amount
  43.             if new_amount > 0:
  44.                 to_pipes[i] = (pipe_len, new_amount)
  45.             elif new_amount == 0:
  46.                 to_pipes.pop(i)
  47.             else:
  48.                 raise Exception(f"Impossible! Negative new_amount: {new_amount}")
  49.             return
  50.         if new_pipe_len > pipe_len:
  51.             to_pipes.insert(i, (new_pipe_len, 1))
  52.             return
  53.  
  54.     to_pipes.append((new_pipe_len, 1))
  55.  
  56. def test(): # generate some tests
  57.     for k in range(2,6):
  58.         for _ in range(20):
  59.             demand = []
  60.             for length in random.sample(range(1, 10), k = k):
  61.                 demand.append((length, random.randrange(1,6)))
  62.             demand.sort(reverse=True, key=lambda p: p[0])
  63.             print(f"{demand}")
  64.             res = alg(demand, [(10, inf)])
  65.             print(f"{demand} {res}")
  66. # test()
  67.  
  68. demand = [(5,20),(4,10),(0.1,1)]
  69. supply = [(6,inf)]
  70. print(alg(demand,supply))
  71.  
  72. # print(alg([(8, 4), (5, 1), (3, 1), (2, 5), (1, 5)], [(10, inf)])) # a few seconds!
  73. # print(alg([(7, 2), (5, 3), (4, 3), (3, 5), (1, 5)], [(10, inf)])) # a few minutes!!
  74.  
  75. # print(alg([(50, 3), (10, 2), (1, 1)], [(60, inf)]))
  76. # print(alg([(1,3)], [(6, inf), ((1,3))]))
Success #stdin #stdout 0.03s 9884KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Making [(5, 20), (4, 10), (0.1, 1)] with [(6, inf)]
   Making [(5, 19), (4, 10), (0.1, 1)] with [(6, inf), (1, 1)]
      Making [(5, 18), (4, 10), (0.1, 1)] with [(6, inf), (1, 2)]
         Making [(5, 17), (4, 10), (0.1, 1)] with [(6, inf), (1, 3)]
            Making [(5, 16), (4, 10), (0.1, 1)] with [(6, inf), (1, 4)]
               Making [(5, 15), (4, 10), (0.1, 1)] with [(6, inf), (1, 5)]
                  Making [(5, 14), (4, 10), (0.1, 1)] with [(6, inf), (1, 6)]
                     Making [(5, 13), (4, 10), (0.1, 1)] with [(6, inf), (1, 7)]
                        Making [(5, 12), (4, 10), (0.1, 1)] with [(6, inf), (1, 8)]
                           Making [(5, 11), (4, 10), (0.1, 1)] with [(6, inf), (1, 9)]
                              Making [(5, 10), (4, 10), (0.1, 1)] with [(6, inf), (1, 10)]
                                 Making [(5, 9), (4, 10), (0.1, 1)] with [(6, inf), (1, 11)]
                                    Making [(5, 8), (4, 10), (0.1, 1)] with [(6, inf), (1, 12)]
                                       Making [(5, 7), (4, 10), (0.1, 1)] with [(6, inf), (1, 13)]
                                          Making [(5, 6), (4, 10), (0.1, 1)] with [(6, inf), (1, 14)]
                                             Making [(5, 5), (4, 10), (0.1, 1)] with [(6, inf), (1, 15)]
                                                Making [(5, 4), (4, 10), (0.1, 1)] with [(6, inf), (1, 16)]
                                                   Making [(5, 3), (4, 10), (0.1, 1)] with [(6, inf), (1, 17)]
                                                      Making [(5, 2), (4, 10), (0.1, 1)] with [(6, inf), (1, 18)]
                                                         Making [(5, 1), (4, 10), (0.1, 1)] with [(6, inf), (1, 19)]
                                                            Making [(4, 10), (0.1, 1)] with [(6, inf), (1, 20)]
                                                               Making [(4, 9), (0.1, 1)] with [(6, inf), (2, 1), (1, 20)]
                                                                  Making [(4, 8), (0.1, 1)] with [(6, inf), (2, 2), (1, 20)]
                                                                     Making [(4, 7), (0.1, 1)] with [(6, inf), (2, 3), (1, 20)]
                                                                        Making [(4, 6), (0.1, 1)] with [(6, inf), (2, 4), (1, 20)]
                                                                           Making [(4, 5), (0.1, 1)] with [(6, inf), (2, 5), (1, 20)]
                                                                              Making [(4, 4), (0.1, 1)] with [(6, inf), (2, 6), (1, 20)]
                                                                                 Making [(4, 3), (0.1, 1)] with [(6, inf), (2, 7), (1, 20)]
                                                                                    Making [(4, 2), (0.1, 1)] with [(6, inf), (2, 8), (1, 20)]
                                                                                       Making [(4, 1), (0.1, 1)] with [(6, inf), (2, 9), (1, 20)]
                                                                                          Making [(0.1, 1)] with [(6, inf), (2, 10), (1, 20)]
                                                                                          Best option is 0 out of [1, 0, 0]
                                                                                       Best option is 1 out of [1]
                                                                                    Best option is 2 out of [2]
                                                                                 Best option is 3 out of [3]
                                                                              Best option is 4 out of [4]
                                                                           Best option is 5 out of [5]
                                                                        Best option is 6 out of [6]
                                                                     Best option is 7 out of [7]
                                                                  Best option is 8 out of [8]
                                                               Best option is 9 out of [9]
                                                            Best option is 10 out of [10]
                                                         Best option is 11 out of [11]
                                                      Best option is 12 out of [12]
                                                   Best option is 13 out of [13]
                                                Best option is 14 out of [14]
                                             Best option is 15 out of [15]
                                          Best option is 16 out of [16]
                                       Best option is 17 out of [17]
                                    Best option is 18 out of [18]
                                 Best option is 19 out of [19]
                              Best option is 20 out of [20]
                           Best option is 21 out of [21]
                        Best option is 22 out of [22]
                     Best option is 23 out of [23]
                  Best option is 24 out of [24]
               Best option is 25 out of [25]
            Best option is 26 out of [26]
         Best option is 27 out of [27]
      Best option is 28 out of [28]
   Best option is 29 out of [29]
Best option is 30 out of [30]
30
https://ideone.com/4G4Nay
language:
Python 3 (python  3.12)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!