fork download 
  1. allow_reflections = True
  2.  
  3. ANGLE_COMPLEMENTS = {"A": "C", "F": "F", "C": "A"}
  4. MOVE_ENUMS = {"U": 0, "R": 1, "D": 2, "L": 3}
  5. FOUND_ANGLE_STRS = set()
  6.  
  7. def convert(x,y):
  8.     if x == y:
  9.         return "F"
  10.     elif (MOVE_ENUMS[x] - MOVE_ENUMS[y]) % 4 == 1:
  11.         return "C"
  12.     else:
  13.         return "A"
  14.  
  15. def to_angles(moves):
  16.     angles = []
  17.  
  18.     for i in range(1, len(moves)):
  19.         angles.append(convert(moves[i], moves[i-1]))
  20.  
  21.     angles.append(convert(moves[0], moves[len(moves)-1]))
  22.  
  23.     return "".join(angles)
  24.  
  25.  
  26. def equal(angle_str1, angle_str2):
  27.     n = len(angle_str1)
  28.  
  29.     # Check if cyclically equal
  30.     for i in range(n):
  31.         rotated_as1 = angle_str1[i:] + angle_str1[:i]
  32.  
  33.         if rotated_as1 == angle_str2 or (not allow_reflections and rotated_as1[::-1] == angle_str2):
  34.                 return True
  35.  
  36.     # Convert A <-> C and check if cyclically equal
  37.     converted_as1 = "".join(ANGLE_COMPLEMENTS[c] for c in angle_str1)
  38.  
  39.     for i in range(n):
  40.         rotated_cas1 = converted_as1[i:] + converted_as1[:i]
  41.  
  42.         if rotated_cas1 == angle_str2 or (not allow_reflections and rotated_cas1[::-1] == angle_str2):
  43.                 return True
  44.  
  45.     return False
  46.  
  47. def solve(rods, point=(0, 0), moves="", moves2="", visited=None):
  48.     if not rods:
  49.         angle_str = to_angles(moves2)
  50.  
  51.         if point == (0, 0) and angle_str.count("A") - angle_str.count("C") == 4:
  52.             for f in FOUND_ANGLE_STRS:
  53.                 if equal(f, angle_str):
  54.                     break
  55.  
  56.             else:
  57.                 FOUND_ANGLE_STRS.add(angle_str)
  58.                 print(moves, angle_str)
  59.  
  60.         return
  61.  
  62.     if not visited:
  63.         visited = set()
  64.  
  65.     r = rods.pop(0)
  66.  
  67.     for move, direction in [((r,0), "R"), ((0,r), "U"), ((-r,0), "L"), ((0,-r), "D")]:
  68.         new_point = (move[0] + point[0], move[1] + point[1])
  69.         added_visited = set()
  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 visited:
  76.                         search = False
  77.  
  78.                         for a in added_visited:
  79.                             visited.remove(a)
  80.  
  81.                         added_visited = set()                            
  82.                         break
  83.  
  84.                     else:
  85.                         visited.add((i, j))
  86.                         added_visited.add((i, j))
  87.  
  88.             if not search:
  89.                 break
  90.  
  91.         if search:
  92.             solve(rods, new_point, moves + direction, moves2 + direction*r, visited)
  93.  
  94.         for a in added_visited:
  95.             visited.remove(a)
  96.  
  97.     rods.insert(0, r)
  98.  
  99. solve([1]*10)
Success #stdin #stdout 1.78s 10104KB
comments (?)
stdin 
Standard input is empty
stdout 
RRRRULLLLD FFFAAFFFAA
RRRUULLLDD FFAFAFFAFA
RRRUULLDLD FFAFAFACAA
RRRUULDLLD FFAFAACFAA
RRRULULLDD FFAACAFAFA
RRRULULDLD FFAACAACAA
RRRULLULDD FFAAFCAAFA
RRURULLDLD FACAAFACAA
RRULULLDRD FAACAFAACA
https://ideone.com/epY5Rc
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!