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!


Adjacency Matrix Generator

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


Tile Puzzle

It’s been a while1, but I’m back. Today’s post is inspired by a post from /r/dailyprogrammer almost a month ago now: Challenge #183 [Intermediate] Edge Matching Tile Puzzle. Basically, we’re going to solve puzzles like this:

If you look carefully, the tiles are the same between the two, although they might be rotated.


Regular Expression Fractals

Oops, turns out I haven’t had a post in a good long while. Before it gets even longer, I figure that I should take one off my backlog and just write it up, even if it is a little on the shorter side.

Today’s post was inspired by this post on /r/dailyprogrammer a month ago today: Challenge #178 [Hard] Regular Expression Fractals. The basic idea is that you are going to take a rectangular region and divide it into four quadrants, again and again, recording the path as you go (images from that post):


Look and Say

Random quick post today1. Basically, we want to write code to generate what’s known as Look and Say sequence:

To generate a member of the sequence from the previous member, read off the digits of the previous member, counting the number of digits in groups of the same digit. For example:

  • 1 is read off as “one 1” or 11.
  • 11 is read off as “two 1s” or 21.
  • 21 is read off as “one 2, then one 1” or 1211.
  • 1211 is read off as “one 1, then one 2, then two 1s” or 111221.
  • 111221 is read off as “three 1s, then two 2s, then one 1” or 312211.


Langton's ant

Here’s another post from /r/DailyProgrammer: Advanced Langton’s Ant. I’m a bit behind the times (see tomorrow’s post), but it’s still an interesting enough exercise, so let’s go for it!


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.


Novel compression

Last week on /r/dailyprogrammer, there was a neat trio of posts all about a new compression algorithm:

More specifically, we’re going to represent compressed text with the following rules:

  • If the chunk is just a number (eg. 37), word number 37 from the dictionary (zero-indexed, so 0 is the 1st word) is printed lower-case.
  • If the chunk is a number followed by a caret (eg. 37^), then word 37 from the dictionary will be printed lower-case, with the first letter capitalised.
  • If the chunk is a number followed by an exclamation point (eg. 37!), then word 37 from the dictionary will be printed upper-case.
  • If it’s a hyphen (-), then instead of putting a space in-between the previous and next words, put a hyphen instead.
  • If it’s any of the following symbols: . , ? ! ; : (edit: also ‘ and “), then put that symbol at the end of the previous outputted word.
  • If it’s a letter R (upper or lower), print a new line.
  • If it’s a letter E (upper or lower), the end of input has been reached.
  • edit: any other block of text, represent as a literal ‘word’ in the dictionary

Got it? Let’s go!

(If you’d like to follow along: full source)


Trigonometric Triangle Trouble

Yesterday’s post at /r/dailyprogrammer managed to pique my interest1:

A triangle on a flat plane is described by its angles and side lengths, and you don’t need all of the angles and side lengths to work out everything about the triangle. (This is the same as last time.) However, this time, the triangle will not necessarily have a right angle. This is where more trigonometry comes in. Break out your trig again, people.