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 (1--9, 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/...._[0-9]*\([0-9]\)0$/\10/
s/..._[0-9]*\([1-9]\)$/\1/

#Advance the Fizz counter
y/abc/bca/


#Check the fizz and buzz counters and write
#out appropriate text
h
s/c.*/&Fizz/
/[0-9][50]/s/$/Buzz/
s/[^z]*\(..zz.*\)/\1/
s/[abc]_0\?//
p
x

/00/!bloop
D
q

Sed

Sedoku

Elimination

99 Green Bottles

BrainF*@!

FizzBuzz

Links