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