S2T2

Jim Randell 9:53 am on 29 May 2022 Permalink Reply
Tags: by: J S Rowley ( 9 )   

• 

  Jim Randell 9:54 am on 29 May 2022 Permalink | Reply

  For blocks with dimensions (x, y, z) this Python program consider blocks that be made with the same (x + y + z) value, and then looks for two with the same surface area, but with areas that differ by 140.

  It runs in 62ms. (Internal runtime is 4.7ms).

  Run: [ @replit ]

  from enigma import (irange, inf, decompose, subsets, multiply, printf)
  
  # for comparing surface areas
  area = lambda ds: 2 * sum(x * y for (x, y) in subsets(ds, size=2))
  
  # for calculating volumes
  vol = multiply
  
  # find the first solution
  def main():
    # consider increasing x + y + z values
    for t in irange(18, inf):
      # consider possible dimensions for the blocks
      for (b1, b2) in subsets(decompose(t, 3, increasing=1, sep=1, min_v=5), size=2):
        ds = set(b1 + b2)
        if not (len(ds) == 6 and 5 in ds): continue
        if not (area(b1) == area(b2)): continue
        if not (abs(vol(b1) - vol(b2)) == 140): continue
        printf("t={t}: {b1} {b2}")
        return  # we only need the first value
  
  main()
  

  Solution: The dimensions of the blocks are: (5 × 14 × 17) inches, (7 × 10 × 19) inches.

  LikeLike

• 

  Jim Randell 11:38 am on 29 May 2022 Permalink | Reply

  Or, using some analysis:

  If the blocks have dimensions (a, b, c) and (x, y, z), then we have (assuming (a, b, c) has the larger volume):

  a + b + c = x + y + z
  ab + ac + bc = xy + xz + yz
  abc − xyz = 140

  Now, if we consider the expression:

  (a − 5)(b − 5)(c − 5) − (x − 5)(y − 5)(z − 5)
  = (abc − 5(ab + ac + bc) + 25(a + b + c) − 125) − (xyz − 5(xy + xz + yz) + 25(x + y + z) − 125)
  = 140

  We note that one side of the subtraction must equal zero, so the other is ±140.

  And as all the numbers multiplied together in each side of the subtraction are non-negative, it must be the right-hand term that is zero. Hence x = 5.

  So we can look at divisors of 140 to determine the dimensions (a, b, c), and then choose (x, y, z) to give the same sum, and check the surface area constraint.

  Here is a Python program that fully explores the solution space. It runs in 57ms. (Internal run time is 236µs).

  Run: [ @replit ]

  from enigma import (subsets, divisors_tuples, is_pairwise_distinct, div, printf)
  
  # surface area
  area = lambda *ds: 2 * sum(x * y for (x, y) in subsets(ds, size=2))
  
  # start with x = 5
  x = 5
  # calculate dimensions for (a, b, c)
  for (a, b, c) in divisors_tuples(140, 3):
    (a, b, c) = (a + x, b + x, c + x)
    if not is_pairwise_distinct(a, b, c, x): continue
    # find possible y, z values, given xyz = abc - 140
    n = div(a * b * c - 140, x)
    if n is None: continue
    for (y, z) in divisors_tuples(n, 2):
      if not (x < y < z and x + y + z == a + b + c): continue
      # all dimensions are distinct
      if not is_pairwise_distinct(x, y, z, a, b, c): continue
      # check the areas
      if area(a, b, c) != area(x, y, z): continue
      # output solution
      printf("{b1} {b2}", b1=(x, y, z), b2=(a, b, c))
  

  LikeLike

  • 

    Mark Valentine 12:42 pm on 30 May 2022 Permalink | Reply

    Nice trick to factorise with x-5 to obtain the zero. I was factorising with x+1 not getting anywhere.

    LikeLike

  • 

    Frits 1:44 pm on 31 May 2022 Permalink | Reply

    @Jim,

    I you disable the area check in the first program you get answer (5, 6, 14) (7, 8, 10) and if you disable in the second program you get anwer (5, 14, 17) (7, 10, 19).

    LikeLike

  • 

    Frits 2:16 pm on 31 May 2022 Permalink | Reply

    @GeoffR, the problem with MiniZinc most of the times that you have to set boundaries.
    You have chosen 25 as upper limit.

    LikeLike

    • 

      GeoffR 6:59 pm on 31 May 2022 Permalink | Reply

      @Frits:
      The teaser description gives us a means to fix the LB.

      With no prior knowledge of the solution and no logical means to set the UB, I guess the UB could be set fairly high to try and find a solution in MiniZinc. It could then reduced by trial and error if an improvement in total run-time was needed.

      I did an experiment for this teaser, varying the upper bound, to see the variation in run-time to find a solution and the total run-time:

      Upper bound = 25 (Soln = 170ms, Total time = 170ms)
      Upper bound = 50 (Soln = 170ms, Total time = 180ms)
      Upper bound = 100 (Soln = 170ms, Total time = 230ms)
      Upper bound = 200 (Soln = 170ms, Total time = 530ms)

      Absolute boundaries do not seem that important practically in this case.

      LikeLike

  • 

    Frits 8:41 pm on 31 May 2022 Permalink | Reply

       
    from enigma import is_square_p
    
    # dimensions are (a + 5), (b + 5), (c + 5) and 5, y, z
    
    # as (4, 5, 7) is the 140-factorization with the highest lowest factor
    # a is less equal to 4 (and not divisble by 3)
    for a in [1, 2, 4]:
      # as (1, 10, 14) is the 140-factorization with the highest middle factor
      # b is less equal to 10 (and not divisble by 3 or 8)
      for b in [2, 4, 5, 7, 10]:
        if b <= a: continue
        
        # a * b * c = 140
        (c, r) = divmod(140, a * b)
        if r or c <= b: continue
        
        # sum of edges is the same
        # a + b + c + 15 - 5 - y = z
        # volume difference is equal to 140
        # ((a + 5) * (b + 5) * (c + 5) - 140) / 5y = z
        
        # (5 * y) * (a + b + c + 10 - y) = ((a + 5) * (b + 5) * (c + 5) - 140) 
        # 5y^2 - 5 * (a + b + c + 10) * y + (a + 5) * (b + 5) * (c + 5) - 140 = 0
        
        # calculate discriminant
        D = (5 * (a + b + c + 10))**2 - 20 * ((a + 5) * (b + 5) * (c + 5) - 140)
        if D < 0 or not is_square_p(D): continue
        
        # choose lowest solution as y < z
        y = (5 * (a + b + c + 10) - D**.5) // 10 
        z = a + b + c + 15 - 5 - y
        print((a + 5, b + 5, c + 5), (5, y, z))
    

    LikeLike

• 

  GeoffR 12:45 pm on 29 May 2022 Permalink | Reply

  
  % A Solution in MiniZinc
  include "globals.mzn";
  
  var 5..25:a; var 5..25:b; var 5..25:c; % 1st block
  
  var 6..25:x; var 6..25:y; var 6..25:z; % 2nd block (bigger)
  
  constraint all_different([a, b, c, x, y, z]);
  
  constraint a == 5;
  constraint a < b /\ b < c;
  constraint x < y /\ y < z;
  
  % The sum of the edges of one block is equal
  % to the sum of the edges of the other.
  constraint 4 * (a + b + c) == 4 * (x + y + z);
  
  % The sum of the areas of the faces of one block is equal 
  % to the sum of the areas of the faces of the other.
  constraint 2 * (a * b + a * c + b * c) == 2 *(x * y + y * z + x * z);
  
  % The volumes of the two blocks differ by 140 cubic inches.
  constraint x * y * z == a * b * c + 140;
  
  solve satisfy;
  
  output[ "First block dimensions(inches) : " ++ show(a) ++ 
  " by " ++ show(b) ++ " by " ++ show(c) 
  ++ "\n" ++ "Second block dimensions(inches) : " ++ show(x) 
  ++ " by " ++ show(y) ++ " by " ++ show(z)];
  
  % First block dimensions(inches) : 5 by 14 by 17
  % Second block dimensions(inches) : 7 by 10 by 19
  % ----------
  % ==========
  
  
  

  LikeLike