# AoC 2017 Day 12: Gridlock

### Source: Digital Plumber

Part 1: A network of nodes is defined by a list of lines formatted as such:

2 <-> 0, 3, 4

# Takuzu solver

Based on a /r/dailyprogrammer puzzle: Takuzu solver.

Basically, Takuzu is a logic puzzle similar to Sudoku. You are given a grid partially filled with 0s and 1s. You have to fill in the rest of the grid according to three simple rules:

• You cannot have more than three of the same number in a line
• Each column must have an equal number of 0s and 1s1
• No two rows or no two columns can be identical

Thus, if you have a puzzle like this:

0.01.1
0....1
..00..
..00..
1....0
10.0.0


One valid solution (most puzzles should have only a single valid answer, but that doesn’t always seem to be the case):

010101
001101
110010
010011
101100
101010


Let’s do it!

Been a while since I’ve actually tackled one of the Daily Programmer challenges, so let’s try one out. From a week and a half ago, we are challeneged to make an adjacency matrix generator, turning a graphical representation of a graph into an adjacency matrix.

Input:

a-----b
|\   / \
| \ /   \
|  /     e
| / \   /
|/   \ /
c-----d


Output:

01110
10101
11010
10101
01010


# Phone networks

Another day, another challenge from /r/dailyprogrammer. It’s almost two weeks old now, but I’ve just now had a chance to get around it.

Your company has built its own telephone network. This allows all your remote locations to talk to each other. It is your job to implement the program to establish calls between locations.

# Graph coloring

Here’s another one from /r/dailyprogrammer:

… Your goal is to color a map of these regions with two requirements: 1) make sure that each adjacent department do not share a color, so you can clearly distinguish each department, and 2) minimize these numbers of colors.

Essentially, graph coloring.

Here’s a quick problem from the DailyProgrammer subreddit. Basically, we want to calculate the radius of a graph:

radius(g) = \min\limits_{n_0 \in g} \max\limits_{n_1 \in g} d_g(n_0, n_1)