Subversion Repositories blog

computer. Since I hate word puzzles quite a bit, I'd taken similar steps in the

computer. Since I hate word puzzles quite a bit, I'd taken similar steps in the

past. For example, [this recent challenge][4]: 

past. For example, [this recent challenge][4]: 

Fill in the 4x4 square crossword with common uncapitalized words, using no 

Fill in the 4x4 square crossword with common uncapitalized words, using no 

letter more than once:

letter more than once:

My secret weapon? [GNU coreutils][1]. Regex are a great tool, but I rarely have

My secret weapon? [GNU coreutils][1]. Regex are a great tool, but I rarely have

to use some of the more obscure features, which hurts on the occasions where

to use some of the more obscure features, which hurts on the occasions where

they're called for. So the NPR puzzle can be a good way to practice and learn!

they're called for. So the NPR puzzle can be a good way to practice and learn!

`/usr/share/dict/words`. The format of this file is one word per line. Every 

`/usr/share/dict/words`. The format of this file is one word per line. Every 

form of a word, including contractions and possessives, gets its own line. We 

form of a word, including contractions and possessives, gets its own line. We 

use `|` (pipe) to chain the output of one command as the input of the next. 

use `|` (pipe) to chain the output of one command as the input of the next. 

Cat simply outputs a file, and wc -l counts the lines in it.

Cat simply outputs a file, and wc -l counts the lines in it.

2. I assume no apostrophes are in the puzzle. Grep reads input and outputs only

2. I assume no apostrophes are in the puzzle. Grep reads input and outputs only

those lines that match a regular expression (regex).  Using the -v option to 

those lines that match a regular expression (regex).  Using the -v option to 

grep changes it to output only lines that don't match our pattern.

grep changes it to output only lines that don't match our pattern.

3. That's a lot of words to fuddle around with, so lets winnow this down. 

3. That's a lot of words to fuddle around with, so lets winnow this down. 

Firstly, we only care about 4 letter words. We can use grep to give us only 

Firstly, we only care about 4 letter words. We can use grep to give us only 

these words, using the regular expression "^....$". Caret (^) represents 

these words, using the regular expression "^....$". Caret (^) represents 

the start of a line, and $ represents the end of one. Each period is a single 

the start of a line, and $ represents the end of one. Each period is a single 

free choice character for grep, matching exactly one character in the input. 

free choice character for grep, matching exactly one character in the input. 

4. Having cut the search space by 96 percent, we now turn to the clues for... 

4. Having cut the search space by 96 percent, we now turn to the clues for... 

clues. Fortunately, nags and newts define which letters every word can start 

clues. Fortunately, nags and newts define which letters every word can start 

with. Grep treats symbols within [] as alternatives, meaning any any one 

with. Grep treats symbols within [] as alternatives, meaning any any one 

symbol within can match the input. Below alters the regex from 3 to only match 

symbol within can match the input. Below alters the regex from 3 to only match 

words starting with a, g, s, e, w or t.

words starting with a, g, s, e, w or t.

5. Rules say no two letters repeat in the puzzle, so we'll exclude all words 

5. Rules say no two letters repeat in the puzzle, so we'll exclude all words 

with the letters from nags and newts anywhere other than the first letter. As 

with the letters from nags and newts anywhere other than the first letter. As 

an alternative to -v, we can use carets inside brackets to indicate "not". 

an alternative to -v, we can use carets inside brackets to indicate "not". 

6. Next, we can rule out words with repeated letters, like solo and wool. To do

6. Next, we can rule out words with repeated letters, like solo and wool. To do

this quickly, we'll need to use [backreferences][2]. Backreferences can be 

this quickly, we'll need to use [backreferences][2]. Backreferences can be 

[slow][3], but since our dataset is so tiny, it will be fine to add it to the

[slow][3], but since our dataset is so tiny, it will be fine to add it to the

end of the pipeline.

end of the pipeline.

7. Starting to get close! From here on out, this plays a lot like sudoku. Our 

7. Starting to get close! From here on out, this plays a lot like sudoku. Our 

goal is now to start constructing regex for each word. We replace the leading 

goal is now to start constructing regex for each word. We replace the leading 

alternative for a specific letter. To start off, we've only got 7 options for 2

alternative for a specific letter. To start off, we've only got 7 options for 2

across:

across:

    laptop:~$ cat /usr/share/dict/words | grep "^e[cmpuvx][hipr][cloru]$" | grep -vE "([a-z]).*(\1)" | wc -l

    laptop:~$ cat /usr/share/dict/words | grep "^e[cmpuvx][hipr][cloru]$" | grep -vE "([a-z]).*(\1)" | wc -l

    7

    7

Now we build a similar regex for 2 down. Adding in what we know about it's 

Now we build a similar regex for 2 down. Adding in what we know about it's 

intersection with 2 across (cmpuvx) is the sudoku like step:

intersection with 2 across (cmpuvx) is the sudoku like step:

    laptop:~$ cat /usr/share/dict/words | grep -v "'" | grep "^a[cmpuvx][^nagsewt][^nagsewt]$" | grep -vE "([a-z]).*(\1)"

    laptop:~$ cat /usr/share/dict/words | grep -v "'" | grep "^a[cmpuvx][^nagsewt][^nagsewt]$" | grep -vE "([a-z]).*(\1)"

    achy

    achy

    acid

    acid

    amid

    amid

    amok

    amok

    avid

    avid

We rewrite this one as 

We rewrite this one as 

    laptop:~$ cat /usr/share/dict/words | grep -v "'" | grep "^a[cmv][hio][dky]$" | grep -vE "([a-z]).*(\1)" | wc -l

    laptop:~$ cat /usr/share/dict/words | grep -v "'" | grep "^a[cmv][hio][dky]$" | grep -vE "([a-z]).*(\1)" | wc -l

    5

    5

8. The last positions in each down regex constructs a new regex for 4 across:

8. The last positions in each down regex constructs a new regex for 4 across:

A unique solution to 4 across!

A unique solution to 4 across!

9. Revisiting 2 down with this new fact also yields a unique answer. I leave

9. Revisiting 2 down with this new fact also yields a unique answer. I leave

it from here as an exercise to the reader to solve the entire puzzle.

it from here as an exercise to the reader to solve the entire puzzle.