fork download 
  1. import copy
  2.  
  3. found = set()
  4.  
  5. def moves_to_angles(moves):
  6.     angles = ""
  7.  
  8.     MOVE = {"U": 0, "R": 1, "D": 2, "L": 3}
  9.  
  10.     def convert(x,y):
  11.         if x == y:
  12.             return "F"
  13.  
  14.         elif (MOVE[x] - MOVE[y]) % 4 == 1:
  15.             return "C"
  16.  
  17.         else:
  18.             return "A"
  19.  
  20.     for i in range(1, len(moves)):
  21.         angles += convert(moves[i], moves[i-1])
  22.  
  23.     angles += convert(moves[0], moves[len(moves)-1])
  24.  
  25.     return angles
  26.  
  27. def equal(moves2a, moves2b):
  28.     # Cyclically equal or cyclically equal after A <-> C
  29.     for i in range(len(moves2a)):
  30.         if moves2a[i:]+moves2a[:i] == moves2b: # or (moves2a[i:]+moves2a[:i])[::-1] == moves2b:
  31.             return True
  32.  
  33.     new_moves2a = ""
  34.     D = {"A": "C", "F": "F", "C": "A"}
  35.  
  36.     for c in moves2a:
  37.         new_moves2a += D[c]
  38.  
  39.     for i in range(len(new_moves2a)):
  40.         if new_moves2a[i:]+new_moves2a[:i] == moves2b: # or (new_moves2a[i:]+new_moves2a[:i])[::-1] == moves2b:
  41.             return True
  42.  
  43.     return False
  44.  
  45. def solve(rods, point=(0,0), moves="", moves2="", visited=None):
  46.     if not rods:
  47.         if point == (0, 0):
  48.             angles2 = moves_to_angles(moves2)
  49.  
  50.             if angles2.count("A") - angles2.count("C") == 4:
  51.                 # Take anticlockwise
  52.                 for f in found:
  53.                     if equal(f, angles2):
  54.                         break
  55.  
  56.                 else:
  57.                     found.add(angles2)            
  58.                     print(moves, angles2)
  59.         return
  60.  
  61.     if not visited:
  62.         visited = set()
  63.  
  64.     new_rods = rods[:]
  65.     r = new_rods.pop(0)
  66.  
  67.     for m,d in [((r,0), "R"), ((0,r), "U"), ((-r,0), "L"), ((0,-r), "D")]:
  68.         new_point = (m[0]+point[0],m[1]+point[1])
  69.         new_visited = copy.deepcopy(visited)
  70.         search = True
  71.  
  72.         for i in range(min(point[0],new_point[0]), max(point[0],new_point[0])+1):
  73.             for j in range(min(point[1],new_point[1]), max(point[1],new_point[1])+1):
  74.                 if (i, j) != point:
  75.                     if (i, j) in new_visited:
  76.                         search = False
  77.                     else:
  78.                         new_visited.add((i, j))
  79.  
  80.         if search:
  81.             solve(new_rods, new_point, moves+d, moves2+d*r, new_visited)
  82.  
  83.  
  84. solve([1,2,3,4,5,6,7])
  85.  
Success #stdin #stdout 1.47s 9696KB
comments (?)
stdin 
Standard input is empty
stdout 
RULULDR AFAFFCFFFAFFFFAFFFFFAFFFFFFF
https://ideone.com/VWrykM
language:
Python 3 (python  3.12)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!