This time it's a bit harder.

Given this matrix, try to find five seven letter words all starting with 'pr' by adding one letter of each row without using any letter twice.

a e i o u

m d s l v

a p i i i

s u n e c

r h y m e

This time I had to go for checking the word candidates against a dictionary. Too many possibilities. I started out thinking about an efficient way to do it and thought of a tree which turned out to be a

trie tree, as I found out later. Next time I might optimize this to a

DAWG which is a bit more space efficient. Reading all words and building the tree is done in a breeze.

Then I go through all possible combinations in the letter matrix with a couple of for loops and check them against the tree. If they exist they're saved as candidates for further inspection. I also save the position of the letter chosen in each row.

Again a recursive function which really f@#cked up my mind a couple of times until I got it straight to get all possible 5-combinations of the saved candidates. Every combination is checked for validity (i.e. every letter only used once) by adding all letters of all words to a row-wise set. Since a set only can hold one element of each value one set for a row would hold less than five elements if any letter was used twice or more often.

Row three has three 'i', so there will be a couple of equal, but not identical solutions. The output looks like this:

Possible solution:

03224 praline

10313 premium

24042 privacy

32130 prosper

41401 prudish

Possible solution:

03224 praline

10413 premium

24042 privacy

32130 prosper

41301 prudish

...

Watch the third column which represents the letters chosen in the third row to form the word of that line.

Remember: This is quick and dirty. Code quality is measured inversely to the time it took me to hack it down.

lettergrid2.cpp
wordtree2.cpp
wordtree2.hpp
Download

corncobs list of English words to populate the tree with.

Here we go with the second puzzle.

Find a seven letter sequence in the alphabet and rearrange the letters to form something you'll find in a kitchen.

1. find all possible 7 letter sequences. I assume no overlapping at the end of the alphabet because that would be mean.

2. rearrange letters and check all possibilities against a dictionary. Too much right now I'll just have a look at the output and see if I can figure it out from there.

Code is very simple this time:

sevenletters.cpp
Check the output. The seventh line

**guijklm** can be rearranged to form the word

**milkjug**. Nice one.

### Mittwoch, 27. April 2011

My girlfriend gave me a

puzzle calendar for Christmas. Great fun every day. But some of them I can't figure out. Math problems are easy, but those where you have to find, combine, complete etc. English words often are too tough for me. I wouldn't give up and look up the solutions. I'll write a program to solve those riddles. You might think of this doing it not the way intended, I'll respond I'm just using computers the way they are intended.

Here we go with the first puzzle:

Given a matrix with the following equations. Fill in the fields a to i with the numbers 1 to 9. Evaluate the mathematical operations in the order of appearance, ignoring common operation ordering rules.

a + b / c = 2

- + *

d * e / f = 9

+ / /

g * h - i = 1

= = =

5 3 4

I decided to go with a brute-force attack here:

1. create all permutations of the numbers 1 to 9

2. check if above equations are true, if so print out current permutation

Since I use C/C++ a lot lately it's the language of my choice. Also I write most of these during bus rides or other idling periods, so expect dirty code.

Check out the recursive code for the permutations.

matrixtester.cpp