After missing one minigolf, I had some time to take part in Card Trick 2.
The mission was to determine the result of the 'trick' outlined below, when getting as input the initial layout of cards and the actions of the 'audience'.
In my hand I have 21 cards that I deal out face up, one each to 3 spread piles, until there are 3 rows of 7. You silently chose your card and inform me of which 'pile' your card is in (1, 2, or 3). I then pick up each pile making sure to put the pile with your card between the two other piles. I deal them out as before, and again you tell me which pile your card is in. We repeat the process a third time, and when I again pick up the piles, placing the pile with your card in the middle, your card will invariably be the center card (11 of 21 in this case).
By the time I'd even read the rules, there was already a mass of people with a solution of 40-41 (and Ton Hospel at 38, but we all know that he isn't human). Given the length of those solutions, it's obvious that the solution is going to involve some cute mathematical formula, instead of directly manipulating the cards to execute the trick.
The way I thought of the formula was this: Given an index I into the set of cards (for example with the 21 cards below, 0-20) and the pick P (1-3) we need a formula for determining from I and P the index which would get translated to I.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Let's determine this by hand for for the interesting elements (we're only interested in cards that are rearranged into the middle third):
7 8 9 10 11 12 13 1 0 3 6 9 12 15 18 2 1 4 7 10 13 16 19 3 2 5 8 11 14 17 20
Obviously our formula looks like I' = P + 3I - 22. To generalize this we just note that 22 is the number of cards + 1 (which happens to be @F-2). Now, to solve the problem we just need to remember that the card that we're interested in ends up in the middlemost position (i.e. for 21 cards in index 10, @F/2-2), and we can just repeat the formula three times to find out the original position:
I_0 = @F/2-2 I_1 = P_3 + 3*I_0 - (@F-2) = P_3 + 3*(@F/2-2) - @F + 2 = P_3 + @F/2 - 4 I_2 = P_2 + 3*I_1 - (@F-2) = P_2 + 3*(P_3 + @F/2 - 4) - @F + 2 = P_2 + 3*P_3 + @F/2 - 10 I_3 = P_1 + 3*I_2 - (@F-2) = P_1 + 3*P_2 + 9*P_3 + @F/2 - 28
So that's the theory. In practice few Perl tricks are
needed for this problem. The cards can be accessed from
@F by turning on autosplitting with the
The picks could also be accessed from
@F, but it turns out that it's easier to access them using
regexps. By crafting a suitable regular expression, we can get the
picks into the special regep variables (
$&, $', $1, etc). And finally, by using a repeated substitution, we can use the return
value of operation to count the amount of cards in the input (to save one
character when compared to using
@F/2. My final solution
is 39 characters (and a shared second place):
#!perl -lpa $_=$F[s/ ..(.)//g-27+9*$'+3*$1+$&]