S2T2

Jim Randell 4:15 pm on 11 March 2022 Permalink Reply
Tags: by: Howard Williams ( 43 )   

• 

  Jim Randell 4:55 pm on 11 March 2022 Permalink | Reply

  The shortest amount of ducting is to cross the exposed area at right angles. The remaining length of cable required is then the diagonal of the garden with the exposed area removed.

  This Python program runs in 47ms.

  Run: [ @replit ]

  from enigma import (pythagorean_triples, irange, ihypot, printf)
  
  # look for pythagorean triples with hypotenuse 123
  for (x, y, z) in pythagorean_triples(123):
    if z != 123: continue
  
    # consider possible w = width of exposed area
    for w in irange(1, x - 1):
      # calculate d = length of cable required
      d = ihypot(x - w, y)
      if d is None: continue
      d += w
      # output solution
      printf("x={x} y={y} z={z}; w={w} d={d}")
  

  Solution: The total length of cable required is 127 feet.

  The garden is an x by y rectangle, where (x, y, 123) form a Pythagorean triple. So:

  x² + y² = 123²

  There is only one possible triple: (27, 120, 123).

  Also the width of the exposed area is w (where: w < x).

  And the amount of cable required is d we have:

  d = w + √((x − w)² + y²)
  (d − w)² = (x − w)² + y²

  So (x − w, y, d − w) is also a Pythagorean triple.

  The only triple with x < 27 and y = 120 is: (22, 120, 122).

  Hence:

  w = 5
  d = 127

  LikeLike

• 

  GeoffR 10:07 am on 12 March 2022 Permalink | Reply

  I looked at this teaser as two triangles with one above the horizontal strip and one below the horizontal strip. The cable length was then the sum of the two hypotenuses and the vertical crossing depth of the horizontal strip.

  It turns out that the two right angled triangles are the same, with dimensions (11, 60, 61).

  
  % A Solution in MiniZinc
  include "globals.mzn";
  
  % Main rectangle x by y with z as diagonal and x horizontal dimensions
  % Upper triangle is above horizontal strip (a, x1, h1) 
  % ... and lower triangle (below  horizontal strip)  is (b, x2, h2)
  
  % Cable length = Hypotenuse h1 + w(vertical) + Hypotenuse h2
  % Top triangle has vertical dimension (a) above horizontal strip 
  var 1..50:a; var 1..100:x1;  var 1..100:h1;
  
  int: z == 123; % main diagonal of rectangle
  var 1..200:x; var 1..100:y; % main rectangle dimensions
  
  % w = vertical depth of strip, c = cable length
  var 1..50:w; var 124..150:c;
  
  % Bottom triangle - vertical dimension (b) below horizontal strip
  var 1..50:b; var 1..100:x2;  var 1..100:h2; 
  
  constraint x*x + y*y == z*z;  % main rectangle
  constraint a*a + x1*x1 == h1*h1; % triangle above strip
  constraint b*b + x2*x2 == h2*h2; % triangle below strip
  
  constraint c == h1 + w + h2;  % cable length (> z)
  
  % Main rectangle dimensions and part side dimensions
  constraint y == a + b + w /\ x == x1 + x2;
  
  % minimise the length of ducting used
  solve minimize(w);
  output ["Length of cable needed = " ++ show(c) ++ " feet"];
  
  
  

  LikeLike

  • 

    Jim Randell 12:17 pm on 12 March 2022 Permalink | Reply

    @Geoff: Of course we don’t know that (a, x1, h1) and (b, x2, h2) are all integers. But we do know a+b and h1+h2 must be integers, so we can just consider (a+b, x, h1+h2) to find the solution.

    LikeLike

• 

  GeoffR 1:28 pm on 12 March 2022 Permalink | Reply

  @Jim:

  True, but it seemed a reasonable assumption at the time.

  The output from the programme verified my assumption, but I understand the technical point you make about these dimensions not being specifically stated as integers.

  We do know that the length of the cable(c) is a whole number of feet longer than the diagonal(z), and that c = h1 + w + h2. This suggested to me that it would be perhaps be unlikely for any of h1, w, or h2 to be floating point numbers. My two triangle approach also needs integers to work as Pythagorean triangles, of course.

  LikeLike

• 

  GeoffR 7:50 am on 14 March 2022 Permalink | Reply

  A simpler solution, based on Brian’s manual solution.

  % A Solution in MiniZinc
  include "globals.mzn";
   
  int: z == 123; % main diagonal of rectangle
  var 1..200:x; var 1..100:y; % main rectangle dimensions
   
  % d = duct length, c = cable length
  var 1..20:d; 
  var 124..150:c;
  
  constraint x * x + y * y = z * z;
  
  % Moving the strip to bottom of the rectangle, to give geometrical equivalency,
  % - the following formula can be derived:
  constraint d == (c * c - z * z) / (2 * (c - y));
  
  solve satisfy;
  output [ "Cable length = " ++ show(c) ++" feet"];
  
  
  

  LikeLike

  • 

    Jim Randell 12:56 pm on 14 March 2022 Permalink | Reply

    @Geoff: Yes, that is what I was getting at. There is no need to split the garden into two rectangles, when we can just consider the diagonal of the garden with the exposed area removed. (And in the general case, I don’t think it would always be possible to split the remaining garden into two rectangles with integer sides, and with an integer length of cable running through them, so it is lucky that it occurs in this instance).

    And we don’t even need to derive a formula for the width of the exposed area.

    Here’s my MiniZinc model that interprets my original program:

    %#! minizinc -a
    
    % garden is x by y (x < y), diagonal z
    int: z = 123;
    var 1..121: x;
    var 2..122: y;
    constraint  x < y;
    % (x, y, z) is a pythagorean triple
    constraint pow(x, 2) + pow(y, 2) = pow(z, 2);
    
    % exposed area width = w (< x)
    var 1..120: w;
    constraint w < x;
    
    % total length of cable = d
    var 124..245: d;
    % (x - w, y, d - w) is a pythagorean triple
    constraint pow(x - w, 2) + pow(y, 2) = pow(d - w, 2);
    
    solve satisfy;
    

    LikeLike

• 

  Hugh+Casement 7:22 am on 21 March 2022 Permalink | Reply

  I find that a strange shape for a garden.
  A more realistic puzzle would have involved one 140 × 51 ft (diagonal 149 ft),
  with a path 3 ft wide, parallel to the long sides, that for practical reasons has to be traversed at right angles to its length.

  LikeLike