S2T2

Jim Randell 11:18 am on 20 August 2024 Permalink Reply
Tags: by: J S Rowley ( 9 )   

• 

  Jim Randell 11:20 am on 20 August 2024 Permalink | Reply

  We have encountered puzzles involving magic circles before (see: Teaser 1986, Enigma 985, Puzzle #171), and developed tools for generating them

  This Python program considers magic circles of size 6, and then looks for ones that meet the specified requirements.

  It runs in 75ms. (Internal runtime is 4.1ms).

  Run: [ @replit ]

  from magic_circles import magic_circle
  from enigma import printf
  
  # look for a size 6 magic circle (including reflections)
  for ds in magic_circle(6, refl=1):
    # distance AB = 1
    assert ds[0] == 1
    # distance EF > distance FA > distance BC
    if not (ds[4] > ds[5] > ds[1]): continue
    # output solution
    printf("distance EF = {ds[4]} [ds = {ds}]")
  

  Solution: The distance from Earley to Farley is 12 miles.

  And we have the following distances around the circle:

  A→B = 1
  B→C = 2
  C→D = 7
  D→E = 4
  E→F = 12
  F→A = 5

  LikeLike

  • 

    Ruud 2:09 pm on 21 August 2024 Permalink | Reply

    A bit verbose and certainly very brute force:

    import itertools
    
    ab = 1
    for bc, cd, de, ef, fa in itertools.permutations(range(2, 20), 5):
        ac = ab + bc
        ad = ac + cd
        ae = ad + de
        af = ae + ef
        bd = bc + cd
        be = bd + de
        bf = be + ef
        ba = bf + fa
        ce = cd + de
        cf = ce + ef
        ca = cf + fa
        cb = ca + ab
        df = de + ef
        da = df + fa
        db = da + ab
        dc = db + bc
        ea = ef + fa
        eb = ea + ab
        ec = eb + bc
        ed = ec + cd
        fb = fa + ab
        fc = fb + bc
        fd = fc + cd
        fe = fd + de
    
        if ef > fa > bc and af+fa == 31:
            if {ab, ac, ad, ae, af, bc, bd, be, bf, ba, cd, ce, cf, ca, cb, de, df, da, db, dc, ef, ea, eb, ec, ed, fa, fb, fc, fd, fe} == set(range(1, 31)):
                print(ab, ac, ad, ae, af, bc, bd, be, bf, ba, cd, ce, cf, ca, cb, de, df, da, db, dc, ef, ea, eb, ec, ed, fa, fb, fc, fd, fe)
                print(ef)
    

    LikeLike

• 

  Lise Andreasen 10:27 pm on 20 August 2024 Permalink | Reply

  So… The bus travels 31 miles on 1 circuit. And there’s also 2 villages, 31 miles apart on the circuit. Is this the distance from a village to itself?

  LikeLike

  • 

    Jim Randell 8:14 am on 21 August 2024 Permalink | Reply

    That’s right. A complete circuit is 31 miles, but we can also travel all the distances between 1 and 30 miles.

    A→B = 1; B→A = 30
    B→C = 2; C→B = 29
    A→C = 3; C→A = 28
    D→E = 4; E→D = 27
    F→A = 5; A→F = 26
    F→B = 6; B→F = 25
    C→D = 7; D→C = 24
    F→C = 8; C→F = 23
    B→D = 9; D→B = 22
    A→D = 10; D→A = 21
    C→E = 11; E→C = 20
    E→F = 12; F→E = 19
    B→E = 13; E→B = 18
    A→E = 14; E→A = 17
    F→D = 15; D→F = 16

    LikeLike

    • 

      Lise Andreasen 6:29 pm on 21 August 2024 Permalink | Reply

      Just an odd way to describe the 31 miles “distance”.

      “The distances from any village to any other village on the route are all different and all an exact number of miles, consisting of every possible whole number from 1 mile up to the distance for the whole circuit.”

      LikeLike

• 

  GeoffR 9:48 am on 21 August 2024 Permalink | Reply

  There are 6 single trips between villages and 6 trips for each of 2,3,4 and 5 bus stops between villages e.g. AB, BC, CD, DE, EF, FA for single stops between villages. There is only 1 circular bus trip visiting all 6 villages i.e. AB + BC + CD + DE + EF + FA.
  In total, therefore, there are 5 X 6 + 1 = 31 total bus trips.
  This MiniZinc solution enumerates all possible bus trips.

  % A Solution in MiniZinc
  include "globals.mzn";
   
  % Villages are A,B,C,D,E,F
  
  % Assumed upper bounds of six distances between villages
  var 1..15:AB; var 1..15:BC; var 1..15:CD; var 1..15:DE; var 1..15:EF; var 1..15:FA;
  
  constraint all_different ([AB, BC, CD, DE, EF, FA]);
  
  constraint FA > BC /\ FA < EF;
  constraint AB == 1; 
  
  % There are 31 possible distances between villages, as shown below:
  var set of int: soln_nums == {AB, BC, CD, DE, EF, FA,  % 1 stop
  AB+BC, BC+CD, CD+DE, DE+EF, EF+FA, FA+AB,              % 2 stops
  AB+BC+CD, BC+CD+DE, CD+DE+EF, DE+EF+FA, EF+FA+AB, FA+AB+BC,  % 3 stops
  AB+BC+CD+DE, BC+CD+DE+EF, CD+DE+EF+FA, DE+EF+FA+AB, EF+FA+AB+BC, FA+AB+BC+CD, % 4 stops
  AB+BC+CD+DE+EF, BC+CD+DE+EF+FA, CD+DE+EF+FA+AB, DE+EF+FA+AB+BC, % 5 stops
  EF+FA+AB+BC+CD, FA+AB+BC+CD+DE, 
  AB+BC+CD+DE+EF+FA};  % 6 stops
  
  set of int: req_nums = 1..31;
   
  constraint soln_nums == req_nums;
  
  constraint card(soln_nums) == AB + BC + CD + DE + EF + FA;
  
  solve satisfy;
  
  output["[AB, BC, CD, DE, EF, FA] = " ++ show( [AB, BC, CD, DE, EF, FA] )
  ++"\n" ++ "Distance from Earley to Farley =  "  ++ show(EF) ++ " miles."];
  
  % [AB, BC, CD, DE, EF, FA] = [1, 2, 7, 4, 12, 5]
  % Distance from Earley to Farley =  12 miles.
  % ----------
  % ==========
  
  
  

  LikeLike

• 

  Ruud 11:24 am on 22 August 2024 Permalink | Reply

  A bit less verbose:

  import itertools
  
  succ = dict(zip("abcdef", "bcdefa"))
  
  for x5 in itertools.permutations(range(2, 20), 5):
      dist = dict(zip("ab bc cd de ef fa".split(), [1, *x5]))
      for d in "abcdef":
          d1 = succ[d]
          for _ in range(4):
              dist[d + succ[d1]] = dist[d + d1] + dist[d1 + succ[d1]]
              d1 = succ[d1]
      if dist["ef"] > dist["fa"] > dist["ac"] and set(dist.values()) == set(range(1, 31)):
          print(dist["ef"])
  

  LikeLike

• 

  Frits 4:10 pm on 22 August 2024 Permalink | Reply

  Using my Puzzle #171 code but now using decomposition.

       
  from itertools import permutations
  
  # for a list with n numbers check if the set of sums of 1...n-1 adjacent items
  # (also circular) is complete (with n.(n-1) different sums)
  def allOccurOnce(s, ln):                                         
    sms = set(s)
    for i in range(ln):
      for j in range(2, ln):
        if (sm := sum((s * 2)[i:i + j])) in sms: 
          return False
        sms.add(sm)
    return True  
  
  # decompose <t> into <k> increasing numbers from <ns>
  def decompose(t, k, ns, s=[]):
    if k == 1:
      if t in ns:
        yield s + [t]
    else:
      for i, n in enumerate(ns):
        # make sure we don't overshoot
        if 2 * t < (2 * n + k - 1) * k: break
        yield from decompose(t - n, k - 1, ns[i + 1:], s + [n])
  
  N = 6
  T = N**2 - N + 1
  H = int(T // 2)
  
  # for a magic circle with N numbers and total sum T
  # the highest possible circle number is T - N(N-1)/2 which equals H + 1
  
  # exclude mandatory numbers 1 and 2 from the decomposition
  for dc in decompose(T - 3, N - 2, range(3, H + 2)):
    # weave in the number 2
    for p in permutations([2] + dc):
      p1 = (1, ) + p
      
      # distance EF > distance FA > distance BC
      if not (p1[4] > p1[5] > p1[1]): continue
      # can we make N.(N - 1) different sums?
      if not allOccurOnce(p1, N): continue
      print(f"answer: {p1[4]} miles")
  

  LikeLike