S2T2

Jim Randell 11:16 am on 5 March 2019 Permalink Reply
Tags: by: C Skeffington Quin ( 11 )   

• 

  Jim Randell 11:19 am on 5 March 2019 Permalink | Reply

  Before decimalisation £1 was the same as 20 shillings, so each crate has a monetary value of 900 shillings.

  I solved this using a similar approach to Enigma 486 (and borrowed some of the code too).

  This Python 3 program runs in 108ms.

  from enigma import (defaultdict, irange, subsets, printf)
  
  # express total <t> using denominations <ds>, min quantity 1
  def express(t, ds, s=[]):
    if not ds:
      if t == 0:
        yield s
    else:
      (d, *ds) = ds
      for i in irange(1, t // d):
        yield from express(t - d * i, ds, s + [i])
  
  # the weights and costs of the cans
  weights = (1, 2, 4)
  costs = (8, 15, 27)
  
  # find ways to split the cost of a crate into cans
  crates = defaultdict(list)
  for ns in express(900, costs):
    # but each crate has 60 cans
    if not (sum(ns) == 60): continue
    # calculate the total weight of the crate
    t = sum(n * w for (n, w) in zip(ns, weights))
    printf("[{ns} -> weight = {t}]")
    crates[t].append(ns)
  
  # possible weights of 3 cans to be removed
  w3s = defaultdict(list)
  for rs in subsets(weights, size=3, select='R'):
    w3s[sum(rs)].append(rs)
  
  # find two crates with weights that differ by 3 cans
  for (w1, w2) in subsets(sorted(crates.keys()), size=2):
    for rs in w3s[w2 - w1]:
      # check there are enough cans in the w2 crate
      if not any(all(not (r > n) for (r, n) in zip(rs, ns)) for ns in crates[w2]): continue
      # output solution
      printf("{w2} lb -> {w1} lb by removing {rs} x {weights} lb cans")
  

  Solution: The crates the foreman had packed weighed 122 lb and 126 lb.

  Rob reduced the weight of the 126 lb crate to 122 lb by removing 2× 1 lb cans and 1× 2 lb can.

  There are only 3 ways to pack the crates so they have 60 cans and are worth 900 shillings (900s) (where the is at least 1 of each type of can included):

  12× 1 lb @ 8s + 41× 2 lb @ 15s + 7× 4 lb @ 27s = 60 cans, 122 lb, 900s
  24× 1 lb @ 8s + 22× 2 lb @ 15s + 14× 4 lb @ 27s = 60 cans, 124 lb, 900s
  36× 1 lb @ 8s + 3× 2 lb @ 15s + 21× 4 lb @ 27s = 60 cans, 126 lb, 900s

  If we don’t require that all three weights of can are represented in the crate then we can make a crate with 60× 2 lb cans, which weighs 120 lb, and gives rise to multiple solutions.

  LikeLike

• 

  GeoffR 7:42 am on 6 March 2019 Permalink | Reply

  The only 3 ways to pack a crate are found in my MiniZinc programme as 122 lb, 124 lb and 126 lb

  The only way of removing 3 cans to make the crates equal is to remove 3 cans ( 2 of 1lb and 1 of 2lb = 4lb) to reduce the crate weighing 126 ilb to 122 lb.

  Therefore, the foreman had packed 122 lb and 126 lb into the two crates.

  var 1..60: n1; var 1..60: n2;  var 1..60: n3;   % Numbers of  three types of can
  var 1..200: wt;   %total weight of all cans in 1 crate
  
  constraint n1 + n2 + n3 == 60;  % Every crate contains 60 cans
  constraint n1 * 8 + n2 * 15 + n3 * 27 == 900;   %sh £45 * 20 = 900 shillings for 1 crate
  constraint wt = n1 * 1 + n2 * 2 + n3 * 4;
  
  solve satisfy;
  
  % n1 = 12;  n2 = 41;  n3 = 7;  wt = 122;
  %----------
  % n1 = 24;  n2 = 22;  n3 = 14;  wt = 124;
  % ----------
  % n1 = 36;  n2 = 3;  n3 = 21;  wt = 126;
  %----------
  %==========
  %Finished in 199msec
  
  

  LikeLike