[ Home :
Programs

libCVD

Hardware hacks

Publications

Teaching

TooN

Research
]
Sed
Sedoku
This program solves Sudoku puzzles using sed.
Puzzles are entered in the following form on the standard input:
..59.43..
4.87.....
.1..8....
2..63..5.
.5.....3.
.8..41..6
....7..2.
.....56.7
..12.34..
with a dot representing an unsolved square, and the result coming out of the
standard output. The algorithm works as follows:
 Squares with number in above are solved squares, otherwise they are unsolved squares.
 A list of possible numbers is kept for all squares. It contains a single number for a
solved square, and a list of numbers (19, initially) for unsolved squares.

Elimination
 A row is considered: the numbers from all the solved cells in the row are removed from
the list of numbers in the unsolved squares. If unsolved squares have a single number
left, they become solved.
 The above step is repeated for all rows, then all columns, then the 3x3 squares.
 The above step is iterated until no further changes happen
 At this point the puzzle may be solved. If not, a search is performed.
 For each unsolved square in turn, the square is replaced
by each possible number in turn (tentatively solving the square). All of these are put in an
ordered bag (a stack or queue: a queue works best because the search depth never seems to
be greater than 1. In practice, the bag is filled using lazy evaluation and the order in
which things appear in the bag from the lazy evaluation is independent of the bag type.
 The front of the bag is put through the elimination step. If it is inconsistent, then it
is rejected. If it is unsolved, then it is put back in the bag. This step is repeated
until a solution is reached, or the bag becomes empty. If the bag becomes empty, then there
is no valid solution.
The sed required to implement this algorithm is explained in the sedoku program.
Edit: Apparently there's a bug and it can't solve some puzzles.
Download: sedoku.sed
99 Green Bottles
You know the song 10 green bottles, and the 99 bottle version commonly song
on very long school coach journey's (much to the chagrin of the driver)?
99 Green bottles hanging on the wall
99 Green bottles hanging on the wall
And if one green bottle should accidentally fall...
98 Green bottles hanging on the wall
...and so on.
Well, here is a sed program which will print it out, using either numbers or
the names of numbers.
BrainF*@!
I did this to see if sed was Turing complete. BrainF!@k is a minimalist
structured language, and it happens to be Turing complete. So if sed can
interpret BF programs, then it too must be Turing complete. And it is. The
interpreter can only cope with a maximum of 255 loops in the program (it could
be adapted to do more, but probably won't be).
Download: brainf__k.sed
FizzBuzz
You never know when you're going to be asked to solve FizzBuzz in an interview.
Here's a canned solution for you to present at interview:
s/^$/c_00/
:loop
#Advance the number counter:
#Advance both numbers
h
y/0123456789/1234567890/
x
G
#Keep the 10s only if we've ended in 0
s/...._[09]*\([09]\)0$/\10/
s/..._[09]*\([19]\)$/\1/
#Advance the Fizz counter
y/abc/bca/
#Check the fizz and buzz counters and write
#out appropriate text
h
s/c.*/&Fizz/
/[09][50]/s/$/Buzz/
s/[^z]*\(..zz.*\)/\1/
s/[abc]_0\?//
p
x
/00/!bloop
D
q
Links
If you're interested in sed, I can recommend the following sites:
If you're interested in advanced sed hackery, then the most impressive programs are:
Updated March 27^{th} 2013, 05:58