Sed

Sedoku

..59.43..
4.87.....
.1..8....
2..63..5.
.5.....3.
.8..41..6
....7..2.
.....56.7
..12.34..

• 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.

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

Links

If you're interested in sed, I can recommend the following sites:

• The sed $HOME page
• The sed-users mailing list

• dc: an arbitrary precision, arbitrary base calculator.
• The block shuffling maze game, sokoban.
• An implementation of the obfuscated functional language, unlambda.

Updated July 14^th 2011, 10:52

Home : Programs | libCVD | Hardware hacks | Publications | Teaching | TooN | Research
* Programs : EPS to ARTK | Autoconf tutorial | Awk | Numerical Disasters in C | Floating point templates in C++ | Gnokiifs | Parallel | PostScript | Sed Hacking | X11 programs


ed (at) edwardrosten . com
Check HTML compliance