# Introduction


Dots and Boxes is a pencil-and-paper game for two players (sometimes more). It was first published in the 19th century by Édouard Lucas, who called it la pipopipette. It has gone by many other names, including the game of dots, boxes, dot to dot grid, and pigs in a pen.

Starting with an empty grid of dots, two players take turns adding a single horizontal or vertical line between two unjoined adjacent dots. The player who completes the fourth side of a 1×1 box earns one point and takes another turn only if another box can be made. (A point is typically recorded by placing a mark that identifies the player in the box, such as an initial). The game ends when no more lines can be placed. The winner is the player with the most points. The board may be of any size. When short on time, a 2×2 board (a square of 9 dots) is good for beginners. A 5×5 is good for experts. (Source Wikipedia)



# Task


Your task is to complete the class called Game. You will be given the board size as an integer board that will be between 1 and 26, therefore the game size will be board x board. You will be given an array of lines that have already been taken, so you must complete all possible squares.


# Rules

1.  The integer board will be passed when the class is initialised.

2.  board will be between 1 and 26.

3.  The lines array maybe empty or contain a list of line integers.

4.  You can only complete a square if 3 out of the 4 sides are already complete.

5.  The lines array that is passed into the play() function may not be sorted numerically!


# Returns

Return an array of all the lines filled in including the original lines.

Return array must be sorted numerically.

Return array must not contain duplicate integers.


# Example 1
## Initialise
Initialise a board of 2 squares by 2 squares where ```board = 2```

## Line Numbering


## Line Input
So for the line input of `[1, 3, 4]` the below lines would be complete

to complete the square line `6` is needed
## Game Play
```python
board = 2
lines = [1, 3, 4]
game = Game(board)
game.play(lines) => [1, 3, 4, 6]
```

# Example 2
## Initialise
```python
board = 2
lines = [1, 2, 3, 4, 5, 8, 10, 11, 12]
game = Game.new(board)
game.play(lines) => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
```
## Solution 


Good luck and enjoy!

# Kata Series
If you enjoyed this, then please try one of my other Katas. Any feedback, translations and grading of beta Katas are greatly appreciated. Thank you.

 Maze Runner
 Scooby Doo Puzzle
 Driving License
 Connect 4
 Vending Machine
 Snakes and Ladders
 Mastermind
 Guess Who?
 Am I safe to drive?
 Mexican Wave
 Pigs in a Pen
 Hungry Hippos
 Plenty of Fish in the Pond
 Fruit Machine
 Car Park Escape

Difficulty: EASY
Tags: Fundamentals

Data structures

Ad-hoc
Skill types: Data structures

Starter code:
def __init__(self, board):
	

Solutions:
class Game:

	def __init__(self, n):
		k = 2 * n + 1
		self.board = {frozenset((k * r + 1 + c + d for d in (0, n, n + 1, k))) for r in range(n) for c in range(n)}

	def play(self, lines):
		lines = set(lines)
		while 1:
			for cell in self.board:
				stick = cell - lines
				if len(stick) <= 1:
					lines |= stick
					self.board.remove(cell)
					break
			else:
				break
		return sorted(lines)


class Game:

	def __init__(self, s):
		self.s = s
		self.sq = [{d + (2 * s + 1) * y + x for d in [0, s, s + 1, 2 * s + 1]} for x in range(1, s + 1) for y in range(s)]

	def play(self, lines):
		(lines, prevlen) = (set(lines), 0)
		while len(lines) != prevlen:
			(keep, prevlen) = ([], len(lines))
			for sq in self.sq:
				if len(sq & lines) >= 3:
					lines |= sq
				else:
					keep.append(sq)
			self.sq = keep
		return [n for n in range(1, (2 * self.s + 2) * self.s + 1) if n in lines]


class Game:

	def __init__(self, board):
		self.n = board

	def play(self, given):
		(n, make, given) = (self.n, [list(range(1, self.n + 1))], set(given))
		for i in range(n - 1):
			make.append([k + n + (n + 1) for k in make[-1]])
		(possible, i) = ([[i, i + n, i + n + 1, i + n + 1 + n] for i in sum(make, [])], 0)
		while i < len(possible):
			t = [k for k in possible[i] if k not in given]
			if len(t) == 1:
				given.add(t[0])
				i = -1
			i += 1
		return sorted(given)


class Game:

	def __init__(self, board):
		self.board = board

	def play(self, lines):
		self.lines = set(lines)
		change = True
		while change:
			change = False
			for row in range(self.board):
				for col in range(self.board):
					offset = row * (2 * self.board + 1)
					top = offset + col + 1
					left = top + self.board
					right = left + 1
					bottom = right + self.board
					cell = [top, left, right, bottom]
					sides = 0
					for side in cell:
						if side in self.lines:
							sides += 1
					if sides == 3:
						self.lines = self.lines.union(set(cell))
						change = True
		return sorted(list(self.lines))


class Game:

	def __init__(self, n):
		k = 2 * n + 1
		self.board = [{k * r + 1 + c, k * (r + 1) + 1 + c, k * r + n + 1 + c, k * r + n + 2 + c} for r in range(n) for c in range(n)]

	def play(self, lines):
		(L, last) = (set(lines), None)
		while self.board != last:
			last = self.board[:]
			for k in [s for s in self.board if len(L & s) == 3]:
				L |= k
				self.board.remove(k)
		return sorted(list(L))


class Game:

	def ad_line(self, board):
		work = [[] for _ in range(board ** 2 + 1)]
		line_list = [[] for _ in range(2 * board * (board + 1) + 1)]
		for i in range(1, board ** 2 + 1):
			numwork = (i - 1) // board * (2 * board + 1)
			numwork += (i - 1) % board + 1
			work[i].append(numwork)
			line_list[numwork].append(i)
			numwork += board
			work[i].append(numwork)
			work[i].append(numwork + 1)
			line_list[numwork].append(i)
			line_list[numwork + 1].append(i)
			numwork += board + 1
			work[i].append(numwork)
			line_list[numwork].append(i)
		return (work, line_list)

	def __init__(self, board):
		self.box = [0] * (board ** 2 + 1)
		work = self.ad_line(board)
		self.box_line = work[0]
		self.line_list = work[1]

	def play(self, lines):
		out = lines[:]
		work_next = []
		for line in lines:
			for box in self.line_list[line]:
				self.box[box] += 1
				if self.box[box] == 3:
					work_next.append(box)
		while work_next:
			box = work_next.pop(0)
			for line in self.box_line[box]:
				if line in out:
					continue
				out.append(line)
				for n_box in self.line_list[line]:
					self.box[n_box] += 1
					if self.box[n_box] == 3:
						work_next.append(n_box)
		return sorted(out)


class Game:

	def __init__(self, board):
		self._board = board
		self._lines = []
		self._flines = []
		self._gboard = []
		self._cboard = []
		self._sqcheck = [(0, 0), (1, -1), (1, 1), (2, 0)]
		self._sqctotal = 0
		self._dot = 0
		self._score = 0
		self._inner = 'X'
		self._blank = '_'
		self.createcompleteb()

	def play(self, lines):
		if lines == []:
			return lines
		self._lines = lines
		creategameb(self, self._lines)
		breaker = False
		lskip = False
		complete = False
		while not complete:
			breaker = False
			lskip = False
			for y in range(len(self._gboard)):
				if not lskip:
					lskip = True
					if y != len(self._gboard) - 1:
						for x in range(len(self._gboard)):
							if self._gboard[y][x] != self._dot:
								for sqc in self._sqcheck:
									if self._gboard[y + sqc[0]][x + sqc[1]] != self._blank:
										self._sqctotal += 1
								if self._sqctotal == 3:
									for sqc in self._sqcheck:
										if self._gboard[y + sqc[0]][x + sqc[1]] == self._blank:
											self._gboard[y + sqc[0]][x + sqc[1]] = self._cboard[y + sqc[0]][x + sqc[1]]
											self._sqctotal = 0
											self._score = 1
											breaker = True
											break
								elif self._sqctotal == 4:
									self._sqctotal = 0
									self._score = 1
								else:
									self._sqctotal = 0
							else:
								pass
					else:
						complete = True
				else:
					lskip = False
				if breaker:
					breaker = False
					break
		for y in range(len(self._gboard)):
			for x in range(len(self._gboard)):
				if isinstance(self._gboard[y][x], int):
					if self._gboard[y][x] > 0:
						self._flines.append(self._gboard[y][x])
		if self._score:
			return self._flines
		else:
			return self._lines

	def createcompleteb(self):
		switch = 1
		doi = 0
		count = 1
		tmp = []
		for y in range(self._board + 1 + self._board):
			for x in range(self._board + 1 + self._board):
				if switch:
					if not doi:
						tmp.append(self._dot)
						switch = 0
					else:
						tmp.append(self._inner)
						switch = 0
				else:
					tmp.append(count)
					count += 1
					switch = 1
			if doi == 1:
				doi = 0
			else:
				doi = 1
			self._cboard.append(tmp)
			tmp = []

def creategameb(self, lines):
	switch = 1
	doi = 0
	count = 1
	tmp = []
	for y in range(self._board + 1 + self._board):
		for x in range(self._board + 1 + self._board):
			if switch:
				if not doi:
					tmp.append(self._dot)
					switch = 0
				else:
					tmp.append(self._inner)
					switch = 0
			elif count in lines:
				tmp.append(count)
				count += 1
				switch = 1
			else:
				tmp.append(self._blank)
				count += 1
				switch = 1
		if doi == 1:
			doi = 0
		else:
			doi = 1
		self._gboard.append(tmp)
		tmp = []


class Game:

	def __init__(self, board):
		self.board_list = []
		for n in range(board):
			if n == 0:
				for row in range(1, board + 1):
					self.board_list.append([row, row + board, row + board + 1, row + board + 1 + board])
			else:
				for row in range((board + (board + 1)) * n + 1, (board + (board + 1)) * n + board + 1):
					self.board_list.append([row, row + board, row + board + 1, row + board + 1 + board])

	def play(self, lines):
		lines = set(lines)
		changes = True
		while changes == True:
			changes = False
			for combination in self.board_list:
				if len(set(combination) & lines) == 3:
					changes = True
					lines.add(list(set(combination) - (set(combination) & lines))[0])
		return sorted(list(lines))


class Game:

	def __init__(self, board):
		self.board = board

	def internal(self, lines):
		result = set()
		retval = False
		pts_per_line = self.board * 2 + 1
		for by in range(self.board):
			for bx in range(self.board):
				h1 = 1 + by * pts_per_line + bx
				h2 = h1 + pts_per_line
				v1 = h1 + self.board
				v2 = v1 + 1
				count = 0
				if h1 in lines:
					count += 1
					result.add(h1)
				if h2 in lines:
					count += 1
					result.add(h2)
				if v1 in lines:
					count += 1
					result.add(v1)
				if v2 in lines:
					count += 1
					result.add(v2)
				if count == 3:
					retval = True
					result.add(h1)
					result.add(h2)
					result.add(v1)
					result.add(v2)
		ret = list(result)
		ret.sort()
		return (ret, retval)

	def play(self, lines):
		cont = True
		while cont:
			(ret, cont) = self.internal(lines)
			lines = ret
		return lines


class Game:

	def __init__(self, board):
		self.board = board

	def play(self, lines):
		r = set(lines)
		while len(r) < 2 * self.board * (self.board + 1):
			flag = False
			for i in range(self.board):
				for j in range(self.board):
					x = (2 * self.board + 1) * i + j + 1
					s = {x, x + self.board, x + self.board + 1, x + 2 * self.board + 1}
					if len(r & s) == 3:
						r |= s
						flag = True
						break
				if flag:
					break
			if not flag:
				break
		return sorted(r)