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:[EMAIL PROTECTED] _______________________________________________ Beowulf mailing list, Beowulf@beowulf.org To change your subscription (digest mode or unsubscribe) visit http://www.beowulf.org/mailman/listinfo/beowulf
