# 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: MEDIUM
Tags: Game theory

Ad-hoc

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):
	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)))
	puzzle[0][0] = catalogue[None][None][None]
	for col in range(1, columns):
		puzzle[0][col] = catalogue[None][None][puzzle[0][col - 1][0]]
	for row in range(1, rows):
		puzzle[row][0] = catalogue[None][puzzle[row - 1][0][0]][None]
	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):
	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) = ([], [], [], [], [])
	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)

	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]
	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)
	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}'