SHARE
TWEET

Untitled

a guest Jun 16th, 2019 52 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import svgwrite
  2. from copy import copy
  3.  
  4. colours = [
  5. ('purple','purple'),
  6. ('magenta','magenta'),
  7. ('yellow','yellow'),
  8. ('lightpink','lightpink'),
  9. ('cyan','blue'),
  10. ('navy','midnightblue'),
  11. ('green','darkgreen'),
  12. ('red','darkred'),
  13. ('slategray','slategray'),
  14. ('orange','orange'),
  15. ('lightgreen','lightgreen'),
  16. ('whitesmoke','slategray')
  17. ]
  18.  
  19. pieces_s = """
  20. ....
  21.  
  22. ..
  23.  ..
  24.   .
  25.  
  26. ...
  27. . .
  28.  
  29. ....
  30.  .
  31.  
  32. ...
  33. .
  34. .
  35.  
  36. ....
  37. .
  38.  
  39. ..
  40.  ...
  41.  
  42. ...
  43. ..
  44.  
  45.  .
  46. ...
  47.  .
  48.  
  49. ...
  50. .
  51.  
  52. ..
  53. ..
  54.  
  55. ..
  56. .
  57. """
  58.  
  59. def print_piece(piece):
  60.     w,d,h,ps = piece
  61.     print(piece)
  62.     for z in range(h):
  63.         for y in range(z & 1, d, 2):
  64.             s = [' '] * w
  65.             for x in range(z & 1, w, 2):
  66.                 if ((z,x,y) in ps):
  67.                     s[x] = '*'
  68.             print(''.join(s))
  69.         print('----')
  70.  
  71. def make_piece(p):
  72.     """ make piece (w,d,h,[(z,x,y)]) -- with extra spaces for lattice"""
  73.     rows = p.split('\n')
  74.     d = (len(rows) - 1) * 2 + 1
  75.     mx = 0
  76.     sparse = []
  77.     for y,r in enumerate(rows):
  78.         for x,i in enumerate(r):
  79.             if i == '.':
  80.                 if x > mx:
  81.                     mx = x
  82.                 sparse.append((0,x*2,y*2))
  83.     sparse.sort()
  84.     return ((mx*2)+1,d,1,sparse)
  85.  
  86. pieces = [make_piece(p) for p in pieces_s[1:-1].split('\n\n')]
  87.  
  88. def rotate_right(p):
  89.     w,d,h,s = p
  90.     wo = w
  91.     if (wo & 1):
  92.         wo -= 1
  93.     rs = [(z,y,wo-x) for z,x,y in s]
  94.     rs.sort()
  95.     return (d,w,h,rs)
  96.  
  97. def _rotate_xy_z(b):
  98.     """assuming z == 0"""
  99.     z,x,y = b
  100.     x2 = x//2
  101.     y2 = y//2
  102.     xy = x2 + y2
  103.     z_ = x2 - y2
  104.     return (z_,xy,xy)
  105.  
  106. def rotate_up(p):
  107.     """rotate 90degrees around x = y, z = 0"""
  108.     w,d,h,s = p
  109.     rs = [_rotate_xy_z(b) for b in s]
  110.     rs.sort()
  111.     min_z = rs[0][0]
  112.     min_xy = min([x for z,x,y in rs])
  113.     xyo = -(min_z & 1)
  114.     if (min_xy+xyo < 0):
  115.         xyo += 2
  116.     rsa = [(z-min_z,x+xyo,y+xyo) for z,x,y in rs]
  117.     max_z = rs[-1][0]
  118.     wd = max([x for z,x,y in rsa]) + 1
  119.     return (wd,wd,max_z-min_z+1,rsa)
  120.  
  121. def _all_rotations(p):
  122.     c = p
  123.     for r in range(4):
  124.         yield c
  125.         ru = rotate_up(c)
  126.         yield ru
  127.         yield rotate_right(ru)
  128.         c = rotate_right(c)
  129.  
  130. def rotations(p):
  131.     a = [r for r in _all_rotations(p)]
  132.     a.sort()
  133.     c = a[0]
  134.     ret = [c]
  135.     for r in a[1:]:
  136.         if c != r:
  137.             ret.append(r)
  138.         c = r
  139.     return ret
  140.  
  141. BASE = 5
  142. LIMIT = BASE * 2 - 1
  143.  
  144. def in_lattice(z,x,y):
  145.     """check if a point is in the lattice"""
  146.     layers = BASE
  147.     min_xy = z
  148.     limit_xy = LIMIT - z
  149.     odd = z & 1
  150.     return ((z >= 0 and z < layers)
  151.         and (odd == x & 1 and odd == y & 1)
  152.         and (x >= min_xy and x <= limit_xy)
  153.         and (y >= min_xy and y <= limit_xy))
  154.  
  155. def valid_piece_offset(zo,xo,yo,piece):
  156.     """check a piece at that place in the lattice is valid"""
  157.     w,d,h,ps = piece
  158.     for z,x,y in ps:
  159.         if (not in_lattice(z+zo,x+xo,y+yo)):
  160.             return False
  161.     return True
  162.  
  163. def _offset_is_used(zo,xo,yo,piece,used):
  164.     w,d,h,ps = piece
  165.     for z,x,y in ps:
  166.         if used[zo+z][xo+x][yo+y]:
  167.             return True
  168.     return False
  169.  
  170. def _use(zo,xo,yo,piece,used):
  171.     w,d,h,ps = piece
  172.     for z,x,y in ps:
  173.         used[zo+z][xo+x][yo+y] = True
  174.  
  175. def _unuse(zo,xo,yo,piece,used):
  176.     w,d,h,ps = piece
  177.     for z,x,y in ps:
  178.         used[zo+z][xo+x][yo+y] = False
  179.  
  180. def _is_used(point, used):
  181.     z,x,y = point
  182.     return used[z][x][y]
  183.  
  184. candidates = [rotations(p) for p in pieces]
  185. p = pieces[-1]
  186. candidates[-1] = [p, rotate_up(p), rotate_right(rotate_up(p))]
  187.  
  188. # all the positions an item can take
  189. places = []
  190. for z in range(BASE):
  191.     for x in range(z, LIMIT-z, 2):
  192.         for y in range(z, LIMIT-z,2):
  193.             places.append((z,x,y))
  194.  
  195. def make_empty_used():
  196.     return [[[False for y in range(LIMIT)] for x in range(LIMIT)] for z in range(BASE)] #dense (ish) used matrix
  197.  
  198. def fs(pc,used,placed,result,solutions):
  199.     """find a piece to fill place pc
  200.     NOTE: assumes that places[pc] is not used"""
  201.     z,x,y = places[pc]
  202.     for p,piece in enumerate(candidates):
  203.         if p in placed:
  204.             continue
  205.         for r,rotation in enumerate(piece):
  206.             w,d,h,points = rotation
  207.             fz,fx,fy = points[0]
  208.             xo = x - fx
  209.             yo = y - fy
  210.             zo = z - fz
  211.             if (valid_piece_offset(zo,xo,yo,rotation) and
  212.                 not _offset_is_used(zo,xo,yo, rotation, used)):
  213.                 result.append((pc,p,r))
  214.                 if len(result) == len(candidates):
  215.                     solutions.append(copy(result))
  216.                     result.pop()
  217.                     return
  218.                 if len(result) == 3: #increase this number for more logging output
  219.                     print(len(solutions),result)
  220.                 _use(zo,xo,yo, rotation, used)
  221.                 placed.append(p)
  222.                 #find next available point
  223.                 npc = pc + 1
  224.                 while _is_used(places[npc],used):
  225.                     npc += 1
  226.                 fs(npc, used, placed, result, solutions)
  227.                 placed.pop()
  228.                 _unuse(zo,xo,yo, rotation, used)
  229.                 result.pop()
  230.     return
  231.  
  232. used = make_empty_used()
  233. placed = []
  234. result = []
  235. solutions = []
  236. # TAKES approx 8 minutes on Core i7-7660U
  237. # to find the first solution (estimate 4 hours for
  238. # all solutions - including mirror but not rotational
  239. # symmetry)
  240. fs(0,used,placed,result,solutions)
  241.  
  242. # Ready made solution
  243. #stack = [0, 1, 5, 8, 10, 13, 16, 18, 20, 26, 32, 42]
  244. #result = [(0, 1), (5, 0), (9, 2), (7, 7), (11, 0), (2, 7), (10, 0), (6, 3), (3, 6), (1, 6), (4, 5), (8, 2)]
  245. #result = zip(stack, result)
  246. result = solutions[0]
  247.  
  248.  
  249. def zorder(solution):
  250.     """make a list of bits of objects in z-order,y-order
  251.     [(z,y,x,p)]"""
  252.     out = []
  253.     for pc,p,r in solution:
  254.         w,d,h,points = candidates[p][r]
  255.         z,x,y = places[pc]
  256.         fz,fx,fy = points[0]
  257.         xo = x - fx
  258.         yo = y - fy
  259.         zo = z - fz
  260.         for zp,xp,yp in points:
  261.             out.append((zp+zo,yp+yo,xp+xo,p))
  262.     out.sort()
  263.     return out
  264.  
  265. def svg(solution):
  266.     out = zorder(solution)
  267.     dwg = svgwrite.Drawing('test.svg', profile='full')
  268.     filtr = svgwrite.filters.Filter(id="Shadow", start=(0, 0), size=('200%', '200%'), filterUnits="userSpaceOnUse")
  269.     filtr.feOffset("SourceAlpha", result="offOut", dx="20", dy="20" )
  270.     filtr.feGaussianBlur("offOut", result="blurOut", stdDeviation="10" )
  271.     filtr.feBlend("SourceGraphic", in2="blurOut", mode="normal" )
  272.     dwg.defs.add(filtr)
  273.     for z,y,x,p in out:
  274.         fill, stroke = colours[p]
  275.         shape = dwg.add(dwg.circle((60+x*100-z*10,60+y*100-z*25), 60, stroke=stroke, fill=fill))
  276.         shape['filter'] = 'url(#Shadow)'
  277.     return dwg
  278.  
  279. # save all the solutions as svg images
  280. for i,solution in enumerate(solutions):
  281.     dwg = svg(solution)
  282.     dwg.saveas('solution_' + str(i) + '.svg')
  283.  
  284.  
  285. """
  286. TODO:
  287.  
  288. Ways to speed this up.
  289.  
  290. Reduce search space by removing the rotations from one of the pieces.
  291. Take a piece that has 12 rotations and only include 3. 4x speedup (Done)
  292.  
  293. Dense used matrix: zused for O(1) checks of place filled already
  294.  
  295. Work queue: Own stack for restartability and avoid all the extra used checking
  296.  
  297.  
  298. """
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top