[Beowulf] A start in Parallel Programming?

[Robert G. Brown]

On Mon, 19 Mar 2007, Joe Landman wrote:

> ps disclosure: FWIW I do play the occasional Perl golf.  Last one I
> played with was to write a roman numeral calculator (c.f.
> http://www.fonality.com/golf/ and
> http://www.fonality.com/golf/post_mortem.cgi?id=1).

Just for grins I did this too (and thanks for nothing -- gawds, all I
need is another mindless programming task:-)

The only problem I have with it is the "least number of keystrokes"
thing.  I personally think that this part at the very least needs to be
"in the active subroutine, exclusive of debugging code" to eliminate the
trivial overhead of getting the number in from the command line or
whereever and various good-practice things like comments, indentation,
newlines.

The other problem I have with the challenge is that a) the test strings
are all trivial and are far from exhaustive of the available test space;
b) the routine doesn't have to REJECT strings that are technically
invalid (or at least odd) since the "roman numeral algorithm" isn't
single valued without additional restriction.  For example,

   XLII = 42 = VIIIL = XXXXII?

(Note well that the answer in all cases, curiously enough, is "42",
hmmmm:-)

One kind of "good" parser (mine, for example:-) is recursive and
sort-ordered and will translate XXXXII into 42 without complaint.
Another (possibly better one) would complain or refuse to function, but
the test curiously doesn't require that it do this.  This makes the
algorithm much easier and shorter to code -- no error checking on the
input -- but, well, it does no error checking on the input.

However, in the past I've played this game with myself, usually as a way
of learning a new (to me) language.  I programmed Mastermind in APL on
an IBM 5100 (and later in Basica on a PC, where one could do code
patterns with e.g. 10 code peg positions and not just four).  That got
me in time traveller trouble...

I like to play hangman, so I coded a letter frequency counter.  Feed it
a big block of text, it will tell you the frequency of occurrence of a,
b, c...  This was the first C program I ever wrote that had well over
100 lines of code and compiled and worked perfectly the first time.  Of
course the exact same program would work gangbusters well as a simple
substitution code decryption engine with a bit more work...:-)

The first and only program I wrote using Pascal was an "Easter
calculator".  Easter is on the first Sunday after the first full moon
after the spring solstice.  This requires to co-evaluation of solstice
(year/4 modulo leap year, or IS it...), full moon (hmmm, should we use
synodic or sidereal for our modulus, and don't forget leap year), and
Sunday (at last, a simple mod 7 except for leap year!).

And so on... I use similar program assignment to teach programming to
the few programming independent students I take from time to time.  In
some cases one can really learn some language features from doing this,
and in all cases the algorithms and tasks are complex enough that they
use most of the standard logic/syntax features of a languange -- enough
to get you going.

If I didn't have far more better things to do, I'd work on redoing
mastermind yet again under glade, sort of a once and for all version of
the game.  Maybe one that can do an "arbitrary" number of symbols in
"arbitrary" length strings for the code to be broken with lotsa pretty
colors.

Or a sudoku generator puzzle/play engine, ditto.  "Hard" sudoku really
requires the ability to follow possibilities down a tree to a
contradiction AND the ability to back off to a previous node.  Really
fairly ugly on paper.  There is a nice wooden set I've seen to permit it
with a physical grid and scrabble-like tiles (including "guess" tiles of
a different size) but having it on a computer would be much better, and
would permit the smooth/transparent extension to "decahexadoku" -- 0-F in a
(4x4)x4 grid.  or "quadradoku" in a (2x2)x2 grid.  Or (gawds)
icosipentadoku (5x5)x5, using e.g. all the letters but Z.  I'd guess
that solving a single icosipentadoku puzzle at the 'hard' level would
keep a puzzle field busy for several weeks, and just finding a
permutation of the letters to create a "valid" puzzle before starting to
wipe out all but some percentage of them in presentation would be a good
learning-to-code chore.  To me it is just crazy that people actually
sell books of puzzles when a trivial computer program could generate all
the possible puzzles given nothing but time and the will.  Quite a lot
of time, mind you -- maybe even a good parallel computing problem;-)
What IS the count of self-avoiding permutations that constitute all the
valid solutions, times the number of permutations of the ways one can
remove letters from an arbitrary grid of 81?  Oooo, I bet that's a big
number.... and then there is icosipentadoku with 25x25 = 625 boxes if
sudoku = enneadoku (9x9) isn't enough...

Which is almost, arguable, sorta, back on topic.  There's a nice little
MPI/PVM problem for people learning parallel programming.  Given a
sudoku puzzle out of the newspaper, perform a brute-force parallel
search for >>a<< solution that matches at all the given letters.  No use
of logic permitted.

As an optional part b) see if the solution is unique (that is, find ALL
such solutions).  It is dead certain that "many" puzzles, especially
those rated "hard" by virtue of having relatively few letters to start
you off, have multiple solutions.  There are almost certainly
group-theoretic things happening in the solution space and of course any
two valid solutions have an extremely high probability of overlapping on
at least some, possibly nine but maybe a few less (oops, this sounds
like part c), how MANY positions on average overlap?), grid positions.

Problems like this often seem useless at first glance.  But then someone
comes along and maps the problem space into some aspect of physics,
information theory, cryptography, and it turns out that "the sudoku
problem" is homomorphic to a critical problem in string theory or
something equally valuable.  So for those of you looking for interesting
parallel computing challenges that might make a pretty demo one day,
here's one.  Generating a valid solution is probably not a good enough
problem, but finding ALL the valid solutions, exhaustively, and testing
them against an input solution in a parallel search, that might just be
difficult enough to be a good problem, especially at the decahexa or
icosipenta level.

    rgb

-- 
Robert G. Brown	                       http://www.phy.duke.edu/~rgb/
Duke University Dept. of Physics, Box 90305
Durham, N.C. 27708-0305
Phone: 1-919-660-2567  Fax: 919-660-2525     email:rgb at phy.duke.edu