THESE ARE THE FORMS THE PARTICIPANTS FILLED OUT. THANKS EVERYONE! I hope they give you a final lookback at the various approaches - they vary somewhat, but all appear to tackle the brute force issue. Even after a few months, I can't help but "feel" there must be some elusive magic solution somewhere ... I guess that's what helps make for a good problem! Thank you all for participating, and watch for the NEXT POTM in about a month! =Fred ======================================================================== ======================================================================== ============> 1. branch_and_hang <================ 1. branch_and_hang 112 369 1797900 Jim Roche Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== branch_and_hang 22/101 26/97 *22/48 *18/27* 24/96 ================= branch_and_hang was submitted by Jim Roche at roche@research.att.com ================= WHAT DID branch_and_hang DO THAT WAS SPECIAL? Used obvious facts that FF = CC = Identity and that F commutes with C and S to allow search to depth D in time that grew like 1.618^D. Used meet-in-the- middle attack, going forward from the initial deck and backward from the desired unmixed deck, to find sequences of moves that put the first 3 cards (and thus the last 3 cards, as well, by symmetry property) in the correct position. This technique finds all move sequences of length less than 50 or so that restore the deck perfectly. For other decks, the technique essentially gives 3 "free" pairs of matches beyond what is yielded by simple forward search. Typically this gives 9 or 10 pairs of matches in all. After spending half of the allowed time on the meet-in-the middle search described above, the program took the best solution and fed it back in as if it were the starting deck. This typically picked another 2 pairs of matches or so. NOTE to Fred: The more advanced program that Allan Wilks and I are debugging uses the meet-in-the-middle attack above as a front end to get 9 or 10 pairs of matches within 5 minutes. In Stage 2, a set of precomputed operators (stored in packed format) is used to "fix" the cards that are still out of position. A typical iteration of Stage 2 takes about 150 moves and yields another 2 pairs of matches or so. We therefore expect that this program will typically yield about 30 matches (i.e., 15 pairs of matches). >>> [Note back to Jim: POTMs have been known to be addictive. In fact, >>> there are several folks at the Betty Ford clinic still working on >>> trying to solve the ODOMETER problem from 2 years ago. Beware!!!] TRICKS THAT OTHERS MAY NOT HAVE THOUGHT OF: MATH THEORY, PROGRAMMING TRICKS, ETC.: See comments in source code for reference to paper that addresses essentially this problem. (The information in the paper doesn't really help much in developing a practical algorithm, but it has some very interesting results.) ANY OTHER COMMENTS? WHAT DO YOU DO FOR A LIVING? FOR FUN? I'm just wrapping up a postdoc in the Mathematical Sciences Research Center at Murray Hill. My background is in information theory and related areas. Hobbies include volleyball, football, softball, and juggling. ======================================================================== ======================================================================== ============> 2. fulldeck <================ 2. fulldeck 108 894 1743410 Bob Hall Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== fulldeck 22/284 24/245 *22/168 *18/35 22/162 ================= fulldeck was submitted by Bob Hall at hall@research.att.com ================= WHAT DID fulldeck DO THAT WAS SPECIAL? The key idea behind fulldeck is that instead of searching in a space of Shuffles and Cuts, which essentially randomly permute the cards, why not (1) first find a S/C sequence that reaches a state in which some (e.g. 6) of the cards are in the right position, then (2) search in a space of operators each of which guarantees not to foul up those (e.g. 6) positions. (I used positions (not 0), 1,2,3, n-4, n-3, and n-2, but that was arbitrary.) This way each step in the search has to generate a position scoring at least 6, and maybe more. Computationally, you can think of it like a thermonuclear bomb: there is an initial phase that generates the first 6-scoring position(s) as well as the operators (S/C sequences that preserve those positions) that preserve them. THen, Phase-II kicks in and searches in that space, where each step has enhanced search power. If the high-scoring sequences are randomly distributed in each space (as they seem to be), then if you search in a space guaranteed to score 6 no matter what you do, you might expect to see scores about 6 better than a program that searches in the raw S/C space itself. (This is, in fact, close to what I measured (5.6) when I ran my program against earlier S/C searchers on 15 randomly generated test cases of various sizes.) Note that even though each step in the Phase-II space is a longish sequence of S/Cs, we can apply it directly (by looking at it as a permutation and doing the pointwise mapping), instead of executing the Ss and Cs each time we apply it. This saves a great deal of time. This approach leads to longer solution sequences, since each step in the Phase-II space is typically a 10 to 30 long S/C sequence. I figured the very robust improvement of an average of 6 points was worth losing a few tiebreakers. TRICKS THAT OTHERS MAY NOT HAVE THOUGHT OF: - One wants to do breadth-first search (to find short sequences) but BFS is costly in space. You can get essentially the same effect and virtually the same performance using very little space by using Iterative-Deepening Depth-first Search. Essentially, use depth first search, but instead of evaluating every intermediate position, only evaluate those at the leaves, and do it iteratively: first to level 1, then to level 2, etc. The duplicated work of regenerating all previous levels to get to the leaves of the next level is actually insignificant because of the high branching factor of the search space. - Instead of frequently checking the time yourself, your program can schedule an interrupt timer in Unix to wake up the program after ten minutes and pick the current best solution, dump it out, and exit. This saves the computational effort involved in doing frequent system calls to check the time, as well as guarantees using up as close as possible to the whole ten minutes. (see 'man setitimer'). MATH THEORY, PROGRAMMING TRICKS, ETC.: - Flips (ie reversals) commute with both Shuffles and Cuts, so you don't have to consider S/C/F sequences, instead you can just evaluate each S/C result and the F of that without missing any sequences. - For all n, shuffling over and over generates the identity after a rather short time. (For many n, half of that number of shuffles generates the flip of the identity, in fact.) Thus, the S/C space is a k-way branching tree where k is either the order of the shuffle (or the semi-order when k/2 shuffles reverse the sequence). - Curiously, S/C/Fs maintain the property that (if we number the cards from 0 to n-1) card i plus card (n-1-i) is always equal to n-1. This allows us to represent permutations in half the space, since one can always compute the paired card for any card in position < n/2. - Some spaces are tiny, and some are huge so it seems worthwhile to separate the cases. Tiny spaces can be searched exhaustively using ID-DFS, while big ones need other techniques. The tiny spaces I know about: S(2)=2, S(4)=8, S(6)=48, S(8)=24, S(10)=1920, S(12)=7680, S(14)=, S(16)=64, S(32)=160, and S(64)=384 In general, S(2^k) = k*(2^k), seems to be true, but I'm not sure why. ANY OTHER COMMENTS? - My nuclear-fusion technique can obviously be extended recursively, but the sequences grow long quickly. I think (IMHO) you should have either removed or relaxed the length restriction on answers. - This was a good contest. Thanks for running it, Fred! WHAT DO YOU DO FOR A LIVING? FOR FUN? I am a researcher in 11384, working in the areas of program profiling, software engineering and artificial intelligence, and software agents. I also play first base and some outfield if necessary. ======================================================================== ======================================================================== ============> 3. motorhoyle <================ 3. motorhoyle 102 232 1117670 =Vincent Goffin Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== motorhoyle 20/54 20/49 *22/47* *18/27* 22/55 ================= motorhoyle was submitted by =Vincent Goffin at vjg@mozart.att.com ================= WHAT DID motorhoyle DO THAT WAS SPECIAL? I despaired of finding anything clever to do and cast my lot with a brute force approach. In the absence of ANY clue, I concluded it would be just as productive to examine all possible moves up to whatever length the hardware and time constraints would allow. That means moves up to length 55, maybe a bit more. If the solution is shorter than that, motorhoyle will find it. If the solution is longer (and most problems for most deck sizes are much longer) motorhoyle might be able to unscramble 20 cards. It will usually NOT find the best solution for the length of moves examined -- that search is very expensive and could lead to missing an exact solution, and an exact solution usually has a bigger pay-off. Special? motorhoyle knocked off after 6 mins instead of the allowed 10: In Solaris 5.2 CLK_TCK is in limits.h... I guess it's not there in 5.3! (It probably wouldn't have affected the outcome, anyway). TRICKS THAT OTHERS MAY NOT HAVE THOUGHT OF: I worked with N cards instead of 2*N. The hash function contains a parameter that allows more approximate solutions to be found than would otherwise be possible. MATH THEORY, PROGRAMMING TRICKS, ETC.: I tried various things but there was always some step that required a brute force solution, so I gave up. ANY OTHER COMMENTS? The problem is interesting -- I wonder if there is a really clever way of doing this kind of thing... WHAT DO YOU DO FOR A LIVING? FOR FUN? I port and develop version control software -- but the POTM is more fun! ======================================================================== ======================================================================== ============> 4. buffalo <================ 4. buffalo 86 172 1620690 Dennis Sanger Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== buffalo 16/28 14/24 *22/47* *18/47 16/26 ================= buffalo was submitted by Dennis Sanger at drs@bighorn.dr.att.com ================= MATH THEORY, PROGRAMMING TRICKS, ETC.: Basic stuff: Flipping more than once is superfluous, and that flip can occur anywhere in the string of moves, so I flip (if necessary) at the very end for simplicity. Two cuts in a row negate each other. More interesting: any string of moves can be viewed as one meta-move, and these meta-moves can be combined arbitrarily, allowing, for example, the string CSCSSSSCSCSSSS to be performed as two CSCSSSS moves rather than fourteen cuts and shuffles. Also fun: only half the deck needs to be stored, since cut, shuffle, and flip don't affect symmetry, i.e. for a 52-card deck, A is always opposite z, B is always opposite y, etc. WHAT DID buffalo DO THAT WAS SPECIAL? I dunno if it's special, but my approach was to build a library of unique meta-moves of length up to 24, then for each length 24 meta-move I search (via a hash table) the dictionary for the meta-move that will combine with that move to unshuffle the deck. Since two of the five problems were solvable within 48 moves, this worked out nicely. I theorized that I would find the shortest possible solution this way, and never found a counter-example until the fourth final problem... I never figured out how to pull the closest match out of the dictionary, so if the solution wasn't within 48 moves, I didn't have a very good score. To improve the score, I use the remaining time to construct (but not store) meta-moves of increasing size: concatenate the length 24 moves to all the length 1 moves, then to the length 2 moves, etc., looking for high scorers until time runs out. This second phase usually only reaches a depth of about 30. TRICKS THAT OTHERS MAY NOT HAVE THOUGHT OF: If I had any of these... ANY OTHER COMMENTS? A frustrating POTM, since I never came up with any techniques that I would characterize as clever. Just plain brute force... WHAT DO YOU DO FOR A LIVING? FOR FUN? I live for fun. ======================================================================== ======================================================================== ============> 5. serpico <================ 5. serpico 84 717 205480 Lew Mammel Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== serpico 0/204 22/183 *22/90 *18/97 22/143 ================= serpico was submitted by Lew Mammel at lew@uscbu.ih.att.com ================= WHAT DID serpico DO THAT WAS SPECIAL? Two things: 1) It stored two sets of operations, ( to be thought of as the head and tail of a snake ) together in a binary tree such that if any head matched any tail a solution was found. This meant that with 2N operations in the tree, it effectively checked N possible matches each time an operation was added. To make the matches, I stored the inverse permutation of the heads. If U is the given unknown, UA is a head and B is a tail, then UAB = I if and only if inv(UA) = B . My first submission stayed at the top of the leader board for 2 weeks on the strength of this method. 2) It post-processed the best match, trying to improve it, as described below. TRICKS THAT OTHERS MAY NOT HAVE THOUGHT OF: I wonder how many noticed that the group factored. This at least could be used to reduce storage, and I used it for my "improvement" scheme, but it didn't really seem to be the magic bullet I was hoping for. MATH THEORY, PROGRAMMING TRICKS, ETC.: If you write the decks as (e.g.) ABCDEedcba instead of ABCDEabcde you'll see right away that every letter stays paired with its complement through all operations. Therefore the first half determines the second half by order inversion and case complement. This makes it obvious why the flip commutes with the cut and shuffle - it is equivalent to taking the case complements, which is just a relabelling. Operations which preserve order, altering only case, form an invariant subgroup. That is, if A is such an operation, and G is any operation with G' its inverse, then G'AG is also an order preserving operation. These form a kernel of a quotient group. If you can find one of these its relatively easy to apply other kernel elements to it to get a complete answer. It won't be optimal length, though. In my method, I tried to create kernel elements and then tried to improve my best answer by splicing it into the sequence in all possible ways. e.g. ACSS, CASS, CSAS, CSSA. ( This lead to trouble, though - I dropped a flip somewhere ) Regarding the first half as a representation of the quotient group ( disregarding case ), it's interesting that the cut becomes a flip. Also, CS leaves the first letter alone and is equivalent to a shuffle on the next smaller size deck. If you could generate the next smaller cut algorithmically, you would have a recursive method of solving the problem. There is a lot of theory on "free groups", which are formal sequences of operations just as we are dealing with. There is in fact a formal method for obtaining an answer to our problem, ( Shcreier ordering, etc. ) but it defines new operations recursively in terms of others, and ends up creating really long sequences - tens of thousands, I think. I think it might take a lot of time as well. I didn't really work this all out, obviously. There is other theory that can be applied, particulary conjugacy classes. I messed around a lot with these, ( serpico was supposed to stand for SERPIntine COnjugates ) but it was hard to keep length under control. The length, that is, of the operation sequence, but also the length of the program! I really wonder how far you could go with the application of theory. Maybe some others did more. ANY OTHER COMMENTS? Fred ran a great contest. I especially appreciate his emphasis on participation. As it turned out, I dropped a flip in one of the final problems and dropped out of the running. I took it kind of hard when I tried it myself, so I appreciated it when Fred took note of it when he reported the results to me. Oh well! WHAT DO YOU DO FOR A LIVING? FOR FUN? I work on 5ESS switch data base software for a living. For fun? this and that - reading, golf, games. ======================================================================== ======================================================================== ============> 6. a.cut.above <================ 6. a.cut.above 84 788 2563430 Fred Hicinbothem Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== a.cut.above 8/9 20/345 *22/172 *18/35 16/227 ================= a.cut.above was submitted by Fred Hicinbothem at fah@potm.ffast.att.com ================= WHAT DID a.cut.above DO THAT WAS SPECIAL? Like everyone else, figured out the minimum shuffles for the deck size, forgot about more than a single flip. double cuts, etc. 1) For the deck size, I found the N unique move combinations that could be applied at any step. For example, since a deck of 34 cards is returned to original state in 12 shuffles, at each "step" I would try only the following operations: C, CS, CSS, CSSS, .... CSSSSSSSSSSS (cut and 11 shuffles). 2) Each deck from the previous step had these operations applied. I started the process with an F deck, an S deck, and a noop deck. (so at step 2 of a 34 card problem I would have 3x12 decks with move sequences ranging in length from 2 to 13). At the next step I'd have about 3x12^2, then 3x12^3, etc. decks to keep track of. 3) This was just a different way to search the move space - at my "step 10" of a 34 card deck for example, I have "move strings" ranging from the short CSCSCSCSCSCSCSCSCSCS to something over 120 moves long, each one would have the same number of "cuts" in it though. TRICKS THAT OTHERS MAY NOT HAVE THOUGHT OF: 4) Since I'm not much of a programmer (don't know how to use malloc just yet!) I couldn't keep very many decks around - so after every one of my "steps", I examined all the decks and picked out 200 (or so) to keep. The rest I threw away. Unfortunately, it wasn't easy to come up with a scoring mechanism that would somehow get me "closer" to a solution. I tried many, and eventually settled on: 5) I measured the "distance" between consecutive letters (A->B, B->C, etc.) in the deck I had, made a histogram of all the distances between consecutive letters. I figured the ideal solution would have a distance of "zero" between consecutive letters, and a really messed up deck would have distances all over the place. So my measure was the number of bins that had entries - lowest numbers are saved at each level. (hey - I tried a bunch of 'em, this one was the last!) 6) So, bottom line - since I only operated on 200 decks or so at each "step" - I was able to go about 100 or so "steps" deep - examining move strings from 200 to a couple of thousand. BUT NOT ALL OF THEM! MATH THEORY, PROGRAMMING TRICKS, ETC.: Used the sequence mailer to tackle some of the theory and get ideas! ANY OTHER COMMENTS? Fred runs a great contest. He is superior in every way to the average human being. His feet rarely are damp after walking on water. WHAT DO YOU DO FOR A LIVING? FOR FUN? Systems Engineering for the Fast Feature Adjunct Services Technology (FFAST) department in West Long Branch NJ. (System's Engineers are the ones who are not good enough at any one thing to earn a living at it.) For Fun? Why POTMs of course - is there another raison d'etre???? My motivation is to try and bring back some of the fun that seemed to be a whole lot more prevalent at the Labs 25 years ago ... (yeah - I'm an old guy). ======================================================================== ======================================================================== ============> 7. bigbrute <================ 7. bigbrute 82 135 2550430 Kevin Ahrens Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== bigbrute 16/28 16/34 16/20 *18/27* 16/26 ================= bigbrute was submitted by Kevin Ahrens at kea@ih4sm.ih.att.com ================= WHAT DID bigbrute DO THAT WAS SPECIAL? [ed note: bigbrute and mutator are actually both the work of Greg Youngdahl, a perfectly legal way to use a friend to help out! ] Bigbrute works from the mutator code and adds what I call a "shuffle look ahead" algorithm. For each candidate string generated by mutator, the shuffle look ahead adds shuffle operations one at a time (up to the maximum number of shuffles that would restore the deck to its previous order - including looking back at the mutator operations to see how many consecutive shuffles had been performed to yield the current deck) and checks them to see if they produce a better answer than has been seen so far (both in properly located cards and number of operations). While this reduces the total number of variations that the mutator algorithm can produce it does produce a greater operation length (shuffles only) and thus can possibly find more cards in place (at the expense of not always finding the shortest sequence of operations that produce that number of properly located cards). Mutator will always report the shortest number of operations that produce the number of in place cards that it discovers. OTHER SECTIONS: See discussion for mutator. ======================================================================== ======================================================================== ============> 8. curlyshuffle <================ 8. curlyshuffle 80 124 1436870 =Neil Weinstock Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== curlyshuffle 16/27 14/24 16/20 *18/27* 16/26 > ================= > curlyshuffle was submitted by =Neil Weinstock at nsw@garage.att.com > ================= > WHAT DID curlyshuffle DO THAT WAS SPECIAL? Very little, which is why it performs rather poorly. The approach was a very basic breadth-first search of the ridiculously large solution space. The version submitted was my first go at it; I could have improved it considerably but not to the extent that it could have competed effectively. I was missing either a heuristic that would have helped me home in on the solution faster, or a faster way of scoring a partial solution. Oh well. > TRICKS THAT OTHERS MAY NOT HAVE THOUGHT OF: None, most likely (at least not in the submitted version.) > MATH THEORY, PROGRAMMING TRICKS, ETC.: Ditto. > ANY OTHER COMMENTS? Nope. > WHAT DO YOU DO FOR A LIVING? FOR FUN? I'm a hardware designer working on Datakit II and BNS-2000. I'm into keyboards, volleyball, and banging my head against the wall working on programming competitions. ======================================================================== ======================================================================== ============> 9. mutator <================ 9. mutator 80 124 2452500 Greg Youngdahl Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== mutator 16/27 14/24 16/20 *18/27* 16/26 ================= mutator was submitted by Greg Youngdahl at greg@ihlpm.att.com ================= WHAT DID mutator DO THAT WAS SPECIAL? Mutator is basically a brute force algorithm that could recognize certain conditions (such as two consecutive cuts or a sequence of shuffles that would put the deck back the way it was - dependent on deck size) and quickly bypass any operation sets that included those conditions. TRICKS THAT OTHERS MAY NOT HAVE THOUGHT OF: Once I decided that I could put the Flip operation in my analysis routine (see below) I was left manipulating strings of Cuts and Shuffles. I then decided to use integers to represent operation strings (rather than the character arrays I had been using) where a 0 bit represented a Shuffle and a 1 bit represented a Cut. "Incrementing" to the next operation set became an actual ++ operation (extended over a pair of longs to provide for a possible 64 operation set - I found I couldn't get much past 33 operations anyway in the 10 minutes allowed). Then I could slide bit masks over these to check for pairs of consecutive Cuts or strings of Shuffles that exceeded the limit for the deck size, and set all bits below the masks to 1 so that the next increment would cause the offending bits to get altered (since the pair of Cuts or string of Shuffles resulted in no change to the deck at that point, there would already have been an analysis of the shorter operation string that would result from eliminating the pair of Cuts or string of Shuffles). This technique effectively trippled the number of operation strings I was able to analyze, but obviously there were more tricks that I didn't pick up on as evidenced by the leaders in the system test decks. MATH THEORY, PROGRAMMING TRICKS, ETC.: Well, I don't have a mathematical proof of this, but aside from the observation that two consecutive Cuts or Flips result in the deck being back the way it was, I came to the realization that a pair of Flips would cancel each other out no matter where they occured in the order of operations. With that information I was able to imbed a Flip test in my routine for analyzing a prospective solution (knowing that if a flip were necessary for the solution it could be done as the last operation, and that no more than one Flip would ever be necessary), and concentrate on testing combinations of Shuffles and Cuts. ANY OTHER COMMENTS? Can't wait to see the winning entires approaches! WHAT DO YOU DO FOR A LIVING? Development (and at the moment current engineering) of Fault Recovery software for the 1B processors (which are replacing the 1A processors that control the 4ESSs in the AT&T long distance network). FOR FUN? Playing with my 5 yr. old son, playing guitar, piano, synthesizers, bicycle riding, cross country skiing, slot car racing, kite flying, woodworking, writing software for my PC to control my synths, tinkering with microcontrollers and embedded processors and interfacing them to things around the house. The first item and the next several often combine well, the last two (software writing, and tinkering) tend to work better after item 1 goes to bed ;-) ======================================================================== ======================================================================== ============> 10. scarne <================ 10. scarne 80 230 2690980 David Wood Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== scarne 14/23 14/24 18/61 *18/61 16/61 ================= scarne was submitted by David Wood at dww@mrspock.att.com ================= WHAT DID scarne DO THAT WAS SPECIAL? Used breath first search, saving only current deck and path. This allowed depth of 23-24 with ~20Meg of memory (300K decks). Then it transistioned to depth first search. Tracked the number of consecutive shuffles and used a max consecutive shuffles table to cut off dead branchs. Nothing really special. TRICKS THAT OTHERS MAY NOT HAVE THOUGHT OF: A better trick, which I didn't get a chance to submit, is to track a single card. This can be done using translation vectors allowing Shuffle, Cut, Flip to be done in a few machine instructions (very fast!). This coupled with using a 4byte integer to hold the path (0-cut, 1-shuffle) (don't need to store flips since you can try a flip and if it doesn't work, drop it and keep going) you can do breath first search to a depth of 31 (~2 million decks). When the card you are tracking is in the right position, generate the actual deck using the path. This is fine for breath first, but sucks for depth first since you miss out on partials. MATH THEORY, PROGRAMMING TRICKS, ETC.: ANY OTHER COMMENTS? WHAT DO YOU DO FOR A LIVING? FOR FUN? Read and write Sci-Fi, read military Software Process Reengineering history and Improvment ======================================================================== ======================================================================== ============> 10+ gillette <================ 10+ gillette 76 115 342180 Tim Tjarks Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== gillette 14/23 14/24 16/20 16/22 16/26 ================= gillette was submitted by Tim Tjarks at tjarks@iesde.att.com ================= WHAT DID gillette DO THAT WAS SPECIAL? It was pretty much brute force. The only thing that it did to limit the generated tree of moves is to recognize that only one flip was needed in any given solution (FS == SF, FC == CF, FF == ""), and to limit the number of consecutive shuffles to one less than the number that would produce a Flip or bring the deck back to original form. WHAT DO YOU DO FOR A LIVING? FOR FUN? At work: Toolsmith in the 5ESS Global Platform organization, primarily in call load generation. At play: I collect and index comic books, and coach my daughters' softball team. ======================================================================== ======================================================================== ============> 10+ cardtrick <================ 10+ cardtrick 74 115 228770 Warren Montgomery Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== cardtrick 14/23 12/22 16/20 *18/27* 14/23 ==== Sorry, no information on cardtrick is available ======================================================================== ======================================================================== ============> 10+ pfiulhfsetlufc <================ 10+ pfiulhfsetlufc 74 176 2942570 Keith Vollherbst Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== pfiulhfsetlufc 14/55 14/44 16/20 *18/35 12/22 ==== Sorry, no information on pfiulhfsetlufc is available ======================================================================== ======================================================================== ============> 10+ deal <================ 10+ deal 70 110 112170 Dave Lynch Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== deal 12/21 12/22 16/20 *18/27* 12/20 ================= deal was submitted by Dave Lynch at dfl@esun.ho.att.com ================= WHAT DID deal DO THAT WAS SPECIAL? Not much. Built a pair of search trees rooted at the starting and ending positions in hopes of meeting in the middle. Not very effective for long shuffle sequences. TRICKS THAT OTHERS MAY NOT HAVE THOUGHT OF: MATH THEORY, PROGRAMMING TRICKS, ETC.: Flips are commutative. Two flips = Two cuts = Identity. A series of k consecutive shuffles will produce an Identity (where k depends on the deck size). ANY OTHER COMMENTS? Thanks, Fred!!! WHAT DO YOU DO FOR A LIVING? FOR FUN? Develop data network design software. Anything else. ======================================================================== ======================================================================== ============> 10+ transmogrifier <================ 10+ transmogrifier 66 167 98350 Cliff Martin Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== transmogrifier 12/37 12/47 16/32 14/13 12/38 ==== Sorry, no information on transmogrifier is available ======================================================================== ======================================================================== ============> 10+ Wayfinder <================ 10+ Wayfinder 60 106 2819720 David Loewenstern Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== Wayfinder 12/21 10/21 10/21 16/22 12/21 ==== Sorry, no information on Wayfinder is available ======================================================================== ======================================================================== ============> 10+ shuffle_this <================ 10+ shuffle_this 54 86 2890140 Alfredo Machuca Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== shuffle_this 10/17 10/17 10/18 14/17 10/17 ==== Sorry, no information on shuffle_this is available ======================================================================== ======================================================================== ============> 10+ cardshark <================ 10+ cardshark 52 140 2531870 Don Shugard Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== cardshark 16/32 2/28 14/23 *18/31 2/26 ================= cardshark was submitted by Don Shugard at dds@boole.l1135.att.com soon to be dds@boole.info.att.com ================= WHAT DID cardshark DO THAT WAS SPECIAL? I recognized that the flip can always be done at the end of a series of moves therefore the problem becomes a binary problem of cuts and shuffles. Since the max number of cuts to get back to the original deck is 2 only 1 cut before a shuffle is allowed. I computed the maximum shuffles to get either to a flipped deck or the original deck. Based on this number, generate a list of possible 16 bit moves where a 0 is a cut and a 1 is a shuffle. I used this list to generate all possible moves in a breadth first fashion. (10 minutes only gets me about 34 moves deep). I couldn't come up with ways to efficiently prune the tree. TRICKS THAT OTHERS MAY NOT HAVE THOUGHT OF: I used tables to perform shuffles, cuts and flips and calculated transforms for the following. C SC SSC SSSC SSSSC >>>>>C where >>>> is the max number of shuffles I Identity or unshuffled deck S SS SSS >>>>> this allowed me to calculate moves as a series of transfroms instead of each function (ie shuffle or cut ); MATH THEORY, PROGRAMMING TRICKS, ETC.: Nope. Pure brute force ANY OTHER COMMENTS? Wasted too much time pursueing remembering decks, moves and running out of memory. Eventually hit on the transforms June 9, Wish I had more time to think about traversing them more efficiently. I only looked at solutions that had the "A" in the correct place therefore missing some better intermediate solutions. WHAT DO YOU DO FOR A LIVING? I am a VLSI designer both hardware and software FOR FUN? Fly model airplanes; ======================================================================== ======================================================================== ============> 10+ ShuFliPi <================ 10+ ShuFliPi - - - Gerald Williams Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== ShuFliPi 0/0 8/5 8/21 4/28 6/17 ==== Sorry, no information on ShuFliPi is available ======================================================================== ======================================================================== ============> 10+ 3cardmonte <================ 10+ 3cardmonte - - - Michael Chin Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== 3cardmonte 0/0 12/127 6/69 0/0 6/83 ==== Sorry, no information on 3cardmonte is available ======================================================================== ======================================================================== ============> 10+ lotpack <================ 10+ lotpack - - - Bob Vanderwall Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== lotpack 0/0 0/32 0/0 18/27 0/0 ================= lotpack was submitted by Bob Vanderwall at rlv@baseworx.cb.att.com ================= WHAT DID lotpack DO THAT WAS SPECIAL? Breadth first search of the solution space. TRICKS THAT OTHERS MAY NOT HAVE THOUGHT OF: Combinations of operations were eliminated. CF=FC SF=FS, FF=null hence, all F operations can be 'pushed' to the end and combined into zero or one F. Also any CC operation is used to prune the search tree since it is also a null operation. MATH THEORY, PROGRAMMING TRICKS, ETC.: Note that I did not have time to pursue. for a given deck, there is also a sequence of some number of S operations which is NULL, as is SC and CS ANY OTHER COMMENTS? Neat little problem. WHAT DO YOU DO FOR A LIVING? FOR FUN? Living: Software tester. Fun: School, martial arts, POTM. ======================================================================== ======================================================================== ============> 10+ jumble <================ 10+ jumble - - - Subramani Ramachandran Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== jumble 0/0 0/0 0/0 0/0 0/0 ==== Sorry, no information on jumble is available ======================================================================== ======================================================================== ============> 10+ KingAndI <================ 10+ KingAndI - - - Clester Keaton Entry Name ONE TWO THREE FOUR FIVE 52/250 46/150 22/455 18/125 36/160 ========== === === ===== ==== ==== KingAndI 0/0 0/0 0/0 0/0 0/0 ==== Sorry, no information on KingAndI is available