pastebin - collaborative debugging

pastebin is a collaborative debugging tool allowing you to share and modify code snippets while chatting on IRC, IM or a message board.

This site is developed to XHTML and CSS2 W3C standards. If you see this paragraph, your browser does not support those standards and you need to upgrade. Visit WaSP for a variety of options.

Python pastebin - collaborative debugging tool View Help


Posted by Jonathan on Mon 31 Aug 03:53
report abuse | View followups from Jonathan and Jonathan | download | new post

  1. import numpy, matplotlib, pylab
  2.  
  3. pieces = [
  4.     numpy.matrix([[1,-1,1,-1],[0,0,0,1]]),
  5.     numpy.matrix([[1,-1,1,-1],[-1,0,0,0]]),
  6.     numpy.matrix([[-1,1,0],[0,-1,0],[0,1,-1]]),
  7.     numpy.matrix([[-1,0],[1,-1],[0,1]]),
  8.     numpy.matrix([[0,-1,1],[0,1,0],[1,-1,0]]),
  9.     numpy.matrix([[-1,1,-1,1],[0,-1,0,0]]),
  10.     numpy.matrix([[1,0,0],[-1,1,-1]]),
  11.     numpy.matrix([[0,-1,0],[-1,1,-1]]),
  12.     numpy.matrix([[1,0,0],[-1,1,0],[0,-1,1]]),
  13.     numpy.matrix([[1,-1,1,0],[0,0,-1,1]]),
  14.     numpy.matrix([[1,-1,1],[-1,0,0]]),
  15.     numpy.matrix([[0,0,1,-1],[-1,1,-1,0]]),
  16.     numpy.matrix([[0,1,0,0],[1,-1,1,-1]])
  17.     ]
  18.  
  19. board = numpy.zeros([8,8], dtype=int)
  20. board[6,6]=1
  21. board[7,6]=1
  22. board[7,7]=1
  23.  
  24. positions = [(0,0) for piece in pieces] # starting positions of pieces
  25. rotations = [0 for piece in pieces] # n of counterclockwise rotations [0..3]
  26. placed = [False for piece in pieces]
  27. curpiece = 0
  28.  
  29. def placePiece(curpiece):
  30.     """Returns true if piece placed correctly, False if not valid position.
  31.    Doesn't check boundaries."""
  32.     # check inouty
  33.     piece = pieces[curpiece]
  34.     position = positions[curpiece]
  35.     for x in range(piece.shape[0]):
  36.         for y in range(piece.shape[1]):
  37.             if (piece[x,y] != 0 and
  38.                 not inouty(position[0]+x, position[1]+y) == piece[x,y]
  39.                 ):                
  40.                 return False
  41.             if piece[x,y] != 0 and board[position[0]+x, position[1]+y] == 1:
  42.                 return False
  43.     return True
  44.  
  45. def incpos(curpiece):
  46.     while True:
  47.         if rotations[curpiece] < 3:
  48.             rotations[curpiece] += 1
  49.             pieces[curpiece] = numpy.rot90(pieces[curpiece])
  50.         elif 8-positions[curpiece][1]-min(pieces[curpiece].shape)>0:
  51.             positions[curpiece] = (positions[curpiece][0], positions[curpiece][1]+1)
  52.             rotations[curpiece] = 0
  53.             pieces[curpiece] = numpy.rot90(pieces[curpiece])
  54.         elif 8-positions[curpiece][0]-min(pieces[curpiece].shape)>0:
  55.             positions[curpiece] = (positions[curpiece][0]+1, 0)
  56.             rotations[curpiece] = 0
  57.             pieces[curpiece] = numpy.rot90(pieces[curpiece])
  58.         else:
  59.             return False
  60.         # break if position valid
  61.         if (8-positions[curpiece][1]-pieces[curpiece].shape[1]>=0 and
  62.             8-positions[curpiece][0]-pieces[curpiece].shape[0]>=0):
  63.             return True
  64.  
  65. def inouty(x,y):
  66.     """+1 if male square, -1 if female square. Anomalous square hard-coded."""
  67.     return ((x+y+1)%2)*2-1
  68.  
  69. def tobin(piece, position):
  70.     n=0L
  71.     for x in range(piece.shape[0]):
  72.         for y in range(piece.shape[1]):
  73.             if piece[x,y] != 0:
  74.                 n = n | (2**((x+position[0])*8+y+position[1]))
  75.     return n
  76.  
  77. def frombin(piece, n):
  78.     mat = numpy.zeros([8,8],int)
  79.     for s in range(8**2):
  80.         if n & 2**s:
  81.             mat[s // 8, s % 8] = piece+1
  82.     return mat
  83.  
  84. allpositions = []
  85. for i in range(len(pieces)):
  86.     if placePiece(i):
  87.         allpositions.append((i, tobin(pieces[i], positions[i])))
  88.     while incpos(i):
  89.         if placePiece(i):
  90.             allpositions.append((i, tobin(pieces[i], positions[i])))
  91.  
  92. fixedpiece = tobin(board, (0,0))
  93.  
  94. def findSolution(boardstate, usedpieces, remainingpieces, uptosquare):
  95.     if len(remainingpieces) == 0:
  96.         return usedpieces
  97.     if boardstate & 2**uptosquare:
  98.         return findSolution(boardstate, usedpieces, remainingpieces, uptosquare + 1)
  99.     else:
  100.         for piece in remainingpieces:
  101.             if (boardstate & piece[1]) == 0 and (piece[1] & 2**uptosquare) != 0:
  102.                 result = findSolution(boardstate | piece[1], usedpieces + [piece],
  103.                                        [p for p in remainingpieces if p[0] != piece[0]], uptosquare+1)
  104.                 if result != None:
  105.                     return result
  106.         return None
  107.    
  108. solution = findSolution(fixedpiece, [], allpositions, 0)
  109. pylab.matshow(sum([frombin(*piecet) for piecet in solution]))
  110. pylab.show()

Submit a correction or amendment below (click here to make a fresh posting)
After submitting an amendment, you'll be able to view the differences between the old and new posts easily.

Syntax highlighting:

To highlight particular lines, prefix each line with @@


Remember me so that I can delete my post