fork(1) download
copy 
  1. #!/usr/bin/python
  2. ROWS = 2
  3. COLS = 3
  4.  
  5. ## different cell representations
  6. def cell(r,c): 
  7.     ## exercise for the reader: _gues_ which of the following is the fastest
  8.     ## ...
  9.     ## then profile it :)
  10.     index = COLS*(r) + c
  11.     # return [ r,c ]
  12.     # return ( r,c )
  13.     # return index
  14.     # return "(%i,%i)" % (r,c)
  15.  
  16.     def baseN(num,b,numerals="abcdefghijklmnopqrstuvwxyz"):
  17.         return ((num == 0) and numerals[0]) or (baseN(num // b, b, numerals).lstrip(numerals[0]) + numerals[num % b])
  18.  
  19.     return baseN(index, 26)
  20.  
  21. ORIGIN = cell(0,0)
  22.  
  23. def debug(t): pass; #print t
  24. def dump(grid): print("\n".join(map(str, grid)))
  25.  
  26. def print_path(path):
  27.     ## Note: to 'normalize' to start at (1,1) node:
  28.     # while ORIGIN != path[0]: path = path[1:] + path[:1] 
  29.     print " -> ".join(map(str, path))
  30.  
  31. def bruteforce_hamiltonians(grid, whenfound):
  32.     def inner(grid, whenfound, partial):
  33.  
  34.         cols = len(grid[-1]) # number of columns remaining in last rank
  35.         if cols<1:
  36.             # assert 1 == len(set([ len(r) for r in grid ])) # for debug only
  37.             whenfound(partial)                             # disable when benchmarking
  38.             pass
  39.         else:
  40.             #debug(" ------ cols: %i ------- " % cols)
  41.  
  42.             for i,rank in enumerate(grid):
  43.                 if len(rank)<cols: continue
  44.                 #debug("debug: %i, %s (partial: %s%s)" % (i,rank, "... " if len(partial)>3 else "", partial[-3:]))
  45.                 for ci,cell in enumerate(rank):
  46.                     partial.append(cell)
  47.                     grid[i] = rank[:ci]+rank[ci+1:] # modify grid in-place, keeps rank
  48.  
  49.                     inner(grid, whenfound, partial)
  50.  
  51.                     grid[i] = rank # restore in-place
  52.                     partial.pop()
  53.                 break
  54.         pass
  55.     # start of recursion
  56.     inner(grid, whenfound, [])
  57.  
  58. grid = [ [ cell(c,r) for r in range(COLS) ] for c in range(ROWS) ]
  59.  
  60. dump(grid)
  61.  
  62. bruteforce_hamiltonians(grid, print_path)
  63.  
Success #stdin #stdout 0.01s 6660KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
['a', 'b', 'c']
['d', 'e', 'f']
a -> d -> b -> e -> c -> f
a -> d -> b -> f -> c -> e
a -> d -> c -> e -> b -> f
a -> d -> c -> f -> b -> e
a -> e -> b -> d -> c -> f
a -> e -> b -> f -> c -> d
a -> e -> c -> d -> b -> f
a -> e -> c -> f -> b -> d
a -> f -> b -> d -> c -> e
a -> f -> b -> e -> c -> d
a -> f -> c -> d -> b -> e
a -> f -> c -> e -> b -> d
b -> d -> a -> e -> c -> f
b -> d -> a -> f -> c -> e
b -> d -> c -> e -> a -> f
b -> d -> c -> f -> a -> e
b -> e -> a -> d -> c -> f
b -> e -> a -> f -> c -> d
b -> e -> c -> d -> a -> f
b -> e -> c -> f -> a -> d
b -> f -> a -> d -> c -> e
b -> f -> a -> e -> c -> d
b -> f -> c -> d -> a -> e
b -> f -> c -> e -> a -> d
c -> d -> a -> e -> b -> f
c -> d -> a -> f -> b -> e
c -> d -> b -> e -> a -> f
c -> d -> b -> f -> a -> e
c -> e -> a -> d -> b -> f
c -> e -> a -> f -> b -> d
c -> e -> b -> d -> a -> f
c -> e -> b -> f -> a -> d
c -> f -> a -> d -> b -> e
c -> f -> a -> e -> b -> d
c -> f -> b -> d -> a -> e
c -> f -> b -> e -> a -> d
https://ideone.com/YsVRE
language:
Python (cpython 2.7.16)
created:
12 years ago
visibility:
public

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!