Enigmatic Code

Programming Enigma Puzzles

Enigma 1302: Luncheon meet

From New Scientist #2460, 14th August 2004

As the crow flies, Joe lives 5 miles from each of his friends Ken and Les, who live 8 miles apart. Every Sunday lunchtime they meet at a convenient pub. It is convenient because the roads to it are straight and flat. They also chose this pub because its location meant they could all leave home at the same time and, after the shortest possible time, all arrive at the same time. Joe can only manage a steady 11 mph and Les a steady 14 mph on their bicycles. Ken, on his motor bike, is limited to 30 mph by the speed limit.

How long do they each take to reach the pub?

Note: I am waiting for a phone line to be connected at my new house, so I only have sporadic access to the internet at the moment.

[enigma1302]

Advertisements

3 responses to “Enigma 1302: Luncheon meet

  1. Jim Randell 12 August 2014 at 6:37 am

    This is an analytical solution, but I used SymPy to handle the equations. This Python program runs in 318ms.

    from sympy import symbols, sqrt, simplify, Eq, solve
    from enigma import printf
    
    # suppose J=(0,3), K=(-4, 0), L=(4, 0)
    
    # consider a point P = (x, y)
    (x, y) = symbols(('x', 'y'))
    
    # j = distance from P to J, j^2 is...
    j2 = x ** 2 + (y - 3) ** 2
    
    # k = distance from P to K, k^2 is...
    k2 = (x + 4) ** 2 + y ** 2
    
    # l = distance from P to L, l^2 is...
    l2 = (x - 4) ** 2 + y ** 2
    
    # so consider a curve of points where j:k = 11:30
    s1 = Eq(30 ** 2 * j2, 11 ** 2 * k2)
    printf("s1: {s1}")
    
    # and where l:k = 14:30
    s2 = Eq(30 ** 2 * l2, 14 ** 2 * k2)
    printf("s2: {s2}")
    
    # and where j:l = 11:14
    s3 = Eq(14 ** 2 * j2, 11 ** 2 * l2)
    printf("s3: {s3}")
    
    # and solve them (we only solve s1 and s2)
    ts = list()
    for s in solve((s1, s2), (x, y)):
      printf("(x, y)={s}")
      (sx, sy) = s
      # all the times should be the same
      tj = sqrt(j2.subs(((x, sx), (y, sy)))) / 11
      tk = sqrt(k2.subs(((x, sx), (y, sy)))) / 30
      tl = sqrt(l2.subs(((x, sx), (y, sy)))) / 14
      t = float(tj)
      printf("t={t} [tj={tj} tk={tk} tl={tl}]")
      ts.append(tj)
    
    # find the shortest time
    t = min(ts)
    m = t * 60
    printf("solution: t={t} ({m} minutes)", t=float(t), m=float(m))
    

    Solution: Each friend takes 12 minutes to reach the pub.

    There is a second solution of 14 minutes, 56.4 seconds, but we are looking for the shortest possible time.

    The solution works by considering the curves of points that are the required ratios of distances between J, K and L, as seen in the three curves on the graph.

    Enigma 1302 - Graph

    All three curves intersect at two points, and these are the points of equal travel time between J, K and L.

    • Jim Randell 12 August 2014 at 3:04 pm

      Originally I solved this using Heron’s Formula for the area of a triangle, which gives the solution, but only because the location of the Pub does not lie outside the triangle JKL. If, for example, K was willing to risk travelling at 31mph, it wouldn’t find a solution. But it is quite simple to code up. Here it is:

      from sympy import symbols, sqrt, simplify, Eq, solve
      from enigma import printf
      
      # area of a triangle using Heron's formula
      def area(a, b, c):
        s = (a + b + c) / 2
        return sqrt(s * (s - a) * (s - b) * (s - c))
      
      JKL = area(5, 5, 8)
      printf("area(JKL) = {JKL}")
      
      t = symbols('t')
      
      j = 11 * t
      k = 30 * t
      l = 14 * t
      
      XJK = simplify(area(5, j, k))
      printf("area(XJK) = {XJK}")
      
      XJL = simplify(area(5, j, l))
      printf("area(XJL) = {XJL}")
      
      XKL = simplify(area(8, k, l))
      printf("area(XKL) = {XKL}")
      
      # solve JKL = XJK + XJL + XKL for t
      for s in solve(Eq(JKL, XJK + XJL + XKL), t):
        if s.is_real and s > 0:
          m = s * 60
          printf("t={t} ({m} minutes) [{s}]", t=float(s), m=float(m))
      
  2. Jim Randell 13 August 2014 at 6:46 am

    And here’s a numerical solution, using the find_min() GSS solver from the enigma.py library. It runs in 37ms.

    from math import sin, cos, sqrt, pi
    from enigma import find_min, printf
    
    # given a time and an angle
    def f(t, a):
      # how far can we get from K in that time
      r = t * 30.0
      # where is the point?
      (x, y) = (r * cos(a) - 4, r * sin(a))
      # time from J and L
      tj = sqrt(x ** 2 + (y - 3) ** 2) / 11.0
      tl = sqrt((x - 4) ** 2 + y ** 2) / 14.0
      # return the sums of the differences of the times
      return abs(t - tj) + abs(t - tl)
    
    # for a given time determine the minimum difference
    def ft(t):
      # vary the angle between 0 and 2 pi
      r = find_min(lambda a: f(t, a), 0.0, 2 * pi)
      # return the minimum time difference
      return r.fv
    
    # find the time with the minimum possible time difference
    r = find_min(ft, 0.0, 168.0)
    printf("minimum time = {r.v:.8f}")
    

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: