# Overview

The goal here is to solve a puzzle (the "pieces of paper" kind of puzzle). You will receive different pieces of that puzzle as input, and you will have to find in what order you have to rearrange them so that the "picture" of the puzzle is complete.



## Puzzle pieces

All the pieces of the puzzle will be represented in the following way:

* 4 numbers, grouped in 2 tuples, which are representing the "picture" on the piece. Every piece has a 2x2 size.
* 1 id number. All id numbers are unique in a puzzle, but their value may be random.
* Note that all numbers will be non-negative integers (except for outer border "picture" numbers in C#)

For example, 
                
    ((1, 2), (3, 4), 1) 
     Puzzle piece id ^  

is equivalent the the following square piece of puzzle, having the id number `1`:

    +---+
    |1 2|
    |3 4|
    +---+

If the piece is on a border or is a corner, some numbers will be replaced with `None` (`-1` in C#):
```python
((None, None), (1, 2), 10)       -->   upper border
((9, None), (None, None), 11)   -->   bottom right corner
```

 

Note that you cannot flip or rotate the pieces (_would you like to change the picture!?_)



## Solving the puzzle

* You'll get an array of pieces as well as the size of the puzzle (width and height).  
* Two pieces can be assembled if they share the same pattern on the border where they are in contact (see example below).
* Puzzle pieces being unique, you'll never encounter two different pieces that could be assembled with the same third one. So to say: borders are unique.
* Once you found the proper arrangment for all the pieces, return the solved puzzle as a list of tuples (height * width) of the id number of the piece at its correct position. (For C#, return the solved puzzle as a 2-dimensional array of integers.)

## Example:

Inputs:

```python
width, height = 3,3
pieces = [ ((None, 5), (None, None), 3), 
           ((17, None), (None, None), 9),
           ((None, 4), (None, 5), 8),
           ((4, 11), (5, 17), 5),
           ((11, None), (17, None), 2),   
           ((None, None), (None, 4), 7),
           ((5, 17), (None, None), 1), 
           ((None, None), (11, None), 4),
           ((None, None), (4, 11), 6) ]`
```

In this case, the expected output would be:

```python
expected = [(7, 6, 4), (8, 5, 2), (3, 1, 9)]
```

... the solved puzzle looking like this:

```python
         Puzzle Solved:                     Related id numbers:
 -----------------------------                  7    6    4
|None None|None None|None None|                 
|None   4 | 4    11 | 11  None|                 8    5    2
|-----------------------------|
|None   4 | 4    11 | 11  None|                 3    1    9
|None   5 | 5    17 | 17  None|
|-----------------------------| 
|None   5 | 5    17 | 17  None| 
|None None|None None|None None|
 -----------------------------
```

### Notes:

* Be careful about performances, you'll have to handle rather big puzzles.
* Width and height will be between 2 and 100 (inclusive)
* The puzzle may be rectangular too

Difficulty: interview

Starter code:

def puzzle_solver(pieces, width, height):
	

Solutions:
def puzzle_solver(pieces, w, h):
    memo, D, result = {}, {None: (None, None)}, [[None]*w for _ in range(h)]
    
    for (a, b), (c, d), id in pieces:
        memo[(a, b, c)] = id
        D[id] = (c, d)
    
    for i in range(h):
        for j in range(w):
            a, b = D[result[i-1][j]]
            _, c = D[result[i][j-1]]
            result[i][j] = memo[(a, b, c)]
    
    return list(map(tuple, result))

from collections import defaultdict


def puzzle_solver(pieces, h, w):
    pool   = defaultdict(lambda:defaultdict(int))
    pieces = [ Piece(a,b,i,pool) for a,b,i in pieces ]
    return next(p for p in pieces if p.isTopLeft()).build()


class Piece(object):

    def __init__(self,a,b,i,pool):
        self.U,self.D,self.L,self.R = a,b,*zip(a,b)
        self.id,self.pool = i,pool
        for d,r in zip('UDLR','DURL'):
            k = getattr(self,d)
            if k!=(None,None): pool[k][r] = self
    
    def isTopLeft(self): return self.U == self.L == (None,None)
    def build(self):     return [ tuple(pp.id for pp in p._iter('R')) for p in self._iter('D')]
        
    def _iter(piece,d):
        while piece:
            yield piece
            piece = piece.pool[getattr(piece,d)][d]

def puzzle_solver(pieces, width, height):
    solution,corner,d3={},{},{}
    for y in range(height+1):corner[0,y]=None
    for x in range(width+1): corner[x,0]=None
    for (a,b),(c,d),e in pieces:d3[a,b,c]=(d,e)
    for y in range(height):
        for x in range(width):
            corner[x+1,y+1],solution[x,y]=d3[corner[x,y],corner[x+1,y],corner[x,y+1]]
    return [tuple(solution[x,y] for x in range(width)) for y in range(height)]

def puzzle_solver(puzzle, w, h):
    sol = {}
    res = []
    p = {}
    for pc in puzzle:
        p[pc[0],pc[1][0]] = pc
    for j in range(h):
        rl = []
        for i in range(w):
            if i == 0:
                lu, ld = None, None
            else:
                lu = sol[i-1,j][0][1]
                ld = sol[i-1,j][1][1]
            if j == 0:
                ru = None
            else:
                ru = sol[i,j-1][1][1]
            pc = p[(lu, ru), ld]
            sol[i,j] = pc
            rl.append(pc[2])
        res.append(tuple(rl))
    return res

from collections import defaultdict, namedtuple

def puzzle_solver(pieces, width, height):
    
    # Lookup tree: top_left -> top_right -> bottom_left -> (bottom_right, id)
    catalogue = defaultdict(lambda: defaultdict(dict))
    
    rows, columns = 0, 0
    for piece in pieces:
        (top_left, top_right), (bottom_left, bottom_right), id = piece
        catalogue[top_left][top_right][bottom_left] = bottom_right, id
        if None is top_left is bottom_left:
            rows += 1
        if None is top_left is top_right:
            columns += 1
    
    puzzle = tuple([None] * columns for _ in range(rows))
    
    # top left corner
    puzzle[0][0] = catalogue[None][None][None]
    
    # top row
    for col in range(1, columns):
        puzzle[0][col] = catalogue[None][None][puzzle[0][col - 1][0]]
    
    # left column
    for row in range(1, rows):
        puzzle[row][0] = catalogue[None][puzzle[row - 1][0][0]][None]
    
    # body
    for row in range(1, rows):
        for col in range(1, columns):
            top_left = puzzle[row - 1][col - 1][0]
            top_right = puzzle[row - 1][col][0]
            bottom_left = puzzle[row][col - 1][0]
            puzzle[row][col] = catalogue[top_left][top_right][bottom_left]
    
    return [tuple(piece[1] for piece in row) for row in puzzle]

def puzzle_solver(pieces, width, height):
    l,u,p={},{},{}
    s=[]
    r=[]
    for ((a,b),(c,d),e) in pieces:
        p[e]=(a,b),(c,d)
        l[(a,c)]=e
        u[(a,b)]=e
        if a==b==c==None:r+=[e]
    while 1:
        (a,b),(c,d)=p[r[-1]]
        if b==d==None:
            s+=[tuple(r)]
            r=[]
            if c==None:
                break
            (w,x),(y,z)=p[s[-1][0]]
            r+=[u[(y,z)]]
        else:
            n=l[(b,d)]
            r+=[n]
    return s

from enum import Enum

class Positions(Enum):
    UPPER_LEFT = 1
    UPPER_RIGTHT = 2
    BOTTOM_LEFT = 3
    BOTTOM_RIGTHT = 4

class PuzzlePiece:
    def __init__(self, tup):
        self.values = { Positions.UPPER_LEFT: tup[0][0], Positions.UPPER_RIGTHT: tup[0][1], 
                        Positions.BOTTOM_LEFT: tup[1][0], Positions.BOTTOM_RIGTHT: tup[1][1] }
        self.id = tup[2]
        self.corner = None
        values_lst = [value for position, value in list(self.values.items())]
        corners_positions_with_values = { Positions.UPPER_LEFT: Positions.BOTTOM_RIGTHT, Positions.UPPER_RIGTHT: Positions.BOTTOM_LEFT, 
                                          Positions.BOTTOM_LEFT: Positions.UPPER_RIGTHT, Positions.BOTTOM_RIGTHT: Positions.UPPER_LEFT  }
        if 3 == values_lst.count(None):
            for position in corners_positions_with_values:
                if self.values[position] is not None:
                    self.corner = corners_positions_with_values[position]
            
class Puzzle:        
    def __init__(self, pieces):
        self.cornaners = dict()
        self.piece_map = dict()
        for piece in pieces:
            piece = PuzzlePiece(piece)
            if piece.corner is not None:
                self.cornaners[piece.corner] = piece
            for position, value in list(piece.values.items()):
                if value is not None:
                    if value not in self.piece_map:
                        self.piece_map[value] = { Positions.UPPER_LEFT: None, Positions.UPPER_RIGTHT: None, 
                                                  Positions.BOTTOM_LEFT: None, Positions.BOTTOM_RIGTHT: None }
                    self.piece_map[value][position] = piece
    
    def solve(self):
        res = [[self.cornaners[Positions.UPPER_LEFT]]]
        while True:
            if res[-1][-1].values[Positions.BOTTOM_RIGTHT] is not None:
                res[-1].append(self.piece_map[res[-1][-1].values[Positions.BOTTOM_RIGTHT]][Positions.BOTTOM_LEFT])
            elif res[-1][0].values[Positions.BOTTOM_RIGTHT] is not None:
                res.append([])
                res[-1].append(self.piece_map[res[-2][0].values[Positions.BOTTOM_RIGTHT]][Positions.UPPER_RIGTHT])
            elif res[-1][-1].values[Positions.UPPER_RIGTHT] is not None:
                res[-1].append(self.piece_map[res[-1][-1].values[Positions.UPPER_RIGTHT]][Positions.UPPER_LEFT])
            else:
                break
        res = [tuple(piece.id for piece in row) for row in res]
        return res
            
def puzzle_solver(pieces, width, height):
    puzzle = Puzzle(pieces)
    return puzzle.solve()


def puzzle_solver(li, width, height):
    
    # save pieces of puzzle for later use
    id_number = {i[:2]: i[2] for i in li}
    li, puzzle = list(id_number.keys()), [[() for _ in range(width)] for _ in range(height)] 
    left, right, top, bottom, rest = [], [], [], [], []
    
    # set fixed corners and store sub grid to their correct place
    for grid in li:
        nones, nn = sum(i.count(None) for i in grid), (None, None)
        if nones == 3:
            x, y = [(-1, -1), (-1, 0), (0, -1), (0, 0)][next(i for i, j in enumerate(sum(grid, ())) if j is not None)]
            puzzle[x][y] = grid
        elif nones == 2:
            use = bottom if grid[1] == nn else top if grid[0] == nn else left if (grid[0][0], grid[1][0]) == nn else right
            use.append(grid)
        else:
            rest.append(grid)
    
    # function to set all sidelines
    def set_row(line, start, i, j, o, p, till):
        lookup = {k[o][p]: k for k in line}
        decide = lambda x: {(1, 1, 1, 0): (0, x), (0, 1, 0, 0): (-1, x), (1, 1, 0, 1): (x, 0)}.get((i, j, o, p), (x, -1))
    
        for k in range(1, till - 1):
            x, y = decide(k)
            puzzle[x][y] = lookup[start[i][j]]
            start = puzzle[x][y]
    
    # set all side lines
    for line, start, i, j, o, p, till in [(top, puzzle[0][0], 1, 1, 1, 0, width),
                                          (bottom, puzzle[-1][0], 0, 1, 0, 0, width),
                                          (left, puzzle[0][0], 1, 1, 0, 1, height),
                                          (right, puzzle[0][-1], 1, 0, 0, 0, height)]:
        set_row(line, start, i, j, o, p, till)
    
    #now, all easy set rest of puzzle
    prev = puzzle[0]
    lookup = {k[0]: k for k in rest}
    for k in range(1, height - 1):
        for l in range(1, width - 1):
            puzzle[k][l] = lookup[prev[l][1]]
        prev = puzzle[k]
  
    return [tuple([id_number[j] for j in i]) for i in puzzle]

def puzzle_solver(pieces, width, height):
    xs, ys, edge = list(range(width)), list(range(height)), ((None, None), (None, None))
    solution_grid = [[None for _ in xs] for _ in ys]
    id_to_piece = {p[2]: (p[0], p[1]) for p in pieces}
    code_to_id = {encode(p[0], p[1][0]): id for id, p in list(id_to_piece.items())}
    for y in ys:
        for x in xs:
            top_piece = id_to_piece[solution_grid[y-1][x]] if y > 0 else edge
            left_piece = id_to_piece[solution_grid[y][x-1]] if x > 0 else edge
            solution_grid[y][x] = code_to_id[encode(top_piece[1], left_piece[1][1])]
    return [tuple([solution_grid[y][x] for x in xs]) for y in ys]

def encode(top, left_bottom):
    return f"{top},{left_bottom}"
        


def puzzle_solver(pieces, width, height):
    xs, ys, edge = list(range(width)), list(range(height)), ((None, None), (None, None))
    solution_grid = [[None for _ in xs] for _ in ys]
    id_to_piece = {p[2]: (p[0], p[1]) for p in pieces}
    code_to_id = {encode(p[0], p[1][0]): id for id, p in list(id_to_piece.items())}
    for y in ys:
        for x in xs:
            top_piece = id_to_piece[solution_grid[y-1][x]] if y > 0 else edge
            left_piece = id_to_piece[solution_grid[y][x-1]] if x > 0 else edge
            target_code = encode(top_piece[1], left_piece[1][1])
            target_id = code_to_id[target_code]
            solution_grid[y][x] = target_id
    return [tuple([solution_grid[y][x] for x in xs]) for y in ys]

def encode(top, left_bottom):
    return f"{top},{left_bottom}"