Enigmatic Code

Programming Enigma Puzzles

Enigma 1708: Pentagon

From New Scientist #2875, 28th July 2012 [link]

From a point on one side of a rectangular sheet of paper I drew two straight lines, one of them to a point on one adjacent side and the other to a point on the other adjacent side. My sheet of paper was now divided into two triangles and a pentagon. The lengths of the sides of the triangles were all integers, the lengths of the sides of the pentagon were, in some order, five consecutive integers, each less than 50.

What were the dimensions of the sheet of paper?

Note: It might have been clearer if the puzzle talked about the edges of the sheet of paper, rather than the sides of the corresponding rectangle.

[enigma1708]

Advertisements

4 responses to “Enigma 1708: Pentagon

  1. Jim Randell 25 July 2012 at 5:03 pm

    Here’s my first attempt. It runs in 43ms, but I’m not entirely happy with it. I lifted the generator for Pythagorean triples from a Project Euler problem I was looking at.

    Here’s a diagram to illustrate how I tackled the problem.

    import sys
    from enigma import sqrt, irange, printf
    
    # generate pythagorean triples (including non-primitive ones)
    def generate():
      a = 0
      while True:
        a += 2
        n = (a * a) // 2
        s = int(sqrt(n))
        for b in irange(s, 1, step=-1):
          (c, r) = divmod(n, b)
          if r > 0: continue
          yield (a + b, a + c, a + b + c)
    
    # is this arrangement a solution?
    def check(a, b, c, d, e, f):
      # three sides of the pentagon are: c, f, a+d
      p3 = set((c, f, a + d))
      # there must be three different values, max - min less than 5
      if len(p3) != 3: continue
      (pmin, pmax) = (min(p3), max(p3))
      if not(pmax < 50): continue
      if pmax - pmin > 4: continue
      # find possible 5-tuples for the pentagon
      for p in irange(min(pmin, pmax - 4), max(pmin, pmax - 4)):
        p5 = set(range(p, p + 5))
        # what are the remaining two sides?
        p2 = p5.difference(p3)
        #  the difference between the two sides must be the difference between b and e
        if max(p2) - min(p2) != abs(b - e): continue
        # what are the dimensions of the rectangle
        printf("{w}x{l} [{t1} {t2} {p5}]", w = a + d, l = (b + e + sum(p2)) // 2, t1 = (a, b, c), t2 = (d, e, f), p5 = tuple(sorted(p5)))
        # and we're done
        sys.exit(0)
    
    # solve the problem
    def solve():
      # accumulate the pythagorean triples
      tris = []
      # t2
      for (d, e, f) in generate():
        # t1 < t2
        for (a, b, c) in tris:
          # try the possibilities
          check(a, b, c, d, e, f)
          check(b, a, c, d, e, f)
          check(a, b, c, e, d, f)
          check(b, a, c, e, d, f)
        tris.append((d, e, f))
    
    solve()
    

    Solution: The dimensions of the sheet of paper are 37 x 66.

    • Jim Randell 25 July 2012 at 7:14 pm

      Here’s a slightly modified approach. It generates all possible Pythagorean triples with a hypotenuse less than 50 up front, and then checks all pairs of them. This does away with the exit() for termination, and hence checks all possible answers, instead of stopping at the first one. It runs in 37ms.

      from itertools import combinations
      from enigma import sqrt, is_square, irange, printf
      
      # pythagorean triples with hypotenuse < 50 (unnormalised)
      tris = []
      for h in irange(1, 49):
        for a in irange(1, int(sqrt(0.5) * h)):
          b = is_square(h * h - a * a)
          if b is None: continue
          tris.extend(((a, b, h), (b, a, h)))
      
      for ((a, b, c), (d, e, f)) in combinations(tris, 2):
        # three sides of the pentagon are: c, f, a+d
        p3 = set((c, f, a + d))
        # there must be three different values, max - min less than 5
        if len(p3) != 3: continue
        (pmin, pmax) = (min(p3), max(p3))
        if not(pmax < 50): continue
        if pmax - pmin > 4: continue
        # find possible 5-tuples for the pentagon
        for p in irange(min(pmin, pmax - 4), max(pmin, pmax - 4)):
          p5 = set(range(p, p + 5))
          # what are the remaining two sides?
          p2 = p5.difference(p3)
          # difference between the two sides = difference between b and e
          if max(p2) - min(p2) != abs(b - e): continue
          # what are the dimensions of the rectangle
          printf("{w}x{l} [{t1} {t2} {p5}]", w = a + d, l = (b + e + sum(p2)) // 2, t1 = (a, b, c), t2 = (d, e, f), p5 = tuple(sorted(p5)))
      
  2. arthurvause 25 July 2012 at 7:42 pm

    I probably should have done this one in SQL, but here is some Python:

    squares = {n*n:n for n in range(5,50)}
    pythag = [(a,b,squares[a*a+b*b]) for a in range(3,50) for b in range(3,50) if a*a+b*b in squares]
    candidates = [(p[0]+q[0],p[2],q[2],p[1],q[1]) for p in pythag for q in pythag 
                  if 0 < abs(p[2]-q[2])<5   
                  and 0<abs(p[0]+q[0]-p[2])<5  
                  and 0<abs(p[0]+q[0]-q[2])<5
                  and 0 < abs(p[1]-q[1])<5
                  and p[2]<q[2]
                  ]
    
    for s in range(1,100):
      for c in candidates:
        pent = (c[0],c[1],c[2],s-c[3],s-c[4])
        if len(set(pent))==5 and min(pent)+4==max(pent):
          print "Paper dimensions are:", c[0],s
    
  3. Naim Uygun 29 July 2012 at 8:55 pm
    """
    New Scientist Enigma 1708
    The dimensions of the rectangular sheet are:
    Width=37
    Length=66
    Right angled triangles are: (16,30,34), (21,28,35)
    Pentagon sides are (34,35,36,37,38)
    
    """
    
    print("Please wait to see the answer which is")
    for length in range(99,5,-1):
       
        for a in range(1,50):
            for b in range(1,50):
                for c in range(1,50):
                    if   a**2+b**2 != c**2 : continue
    
                    for d in range(1,50):
                        for  e in range(1,50):
                            for f in range(1,50):
                                if d**2+e**2 != f**2: continue
    
                                if length-e >=50: continue
                                if length-b>=50: continue
                                if a+d>=50:continue
                                l=set()
                                l.add(c)
                                l.add(f)
                                l.add(length-e)
                                l.add(length-b)
                                l.add(a+d)
                                if len(l) != 5 : continue
                                if max(l)-min(l)  != 4: continue
                                print("Triangles: ", (a,b,c),(d,e,f))
                                print(" Rectangular width=",a+d, " length=",length)
                                print(" Pentagon sides are ",l)
                                input("THE END")
    

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: