Hi all,
On Tue, 3 Jul 2012 17:47:49 +0300
Shlomi Fish <shlomif_at_shlomifish.org> wrote:
> Hi all,
>
> On Tue, 3 Jul 2012 14:02:34 +0300
> Shlomi Fish <shlomif_at_shlomifish.org> wrote:
>
> > Hi all,
> >
> > in continuation to
> > http://tech.groups.yahoo.com/group/fc-solve-discuss/message/1115 ,
> > I was thinking how to represent Baker’s Dozen positions.
> >
> > What I came with was:
> >
> > 1. I can use 4 * log2(14) data to represent the foundations.
> >
> > 2. The 13 bottom-most cards will always be either in the foundations or in
> > their original place (due to the prune at
> > http://tech.groups.yahoo.com/group/fc-solve-discuss/message/1121 ).
> > We can tell which one is that based on the encodings in #1 - so:
> > 13 * log2(1)
> >
> > 3. The rest of the cards can be either in their original position or on top of
> > one of the 4 parents of all suits - H, C, D, S. So 39 * log2(5).
> >
> > To sum up:
> >
> > $ perl -MLog2 -e 'plog2(4 => 14, 13 => 1, 39 => 5)'
> > log2(14) * 4 + log2(1) * 13 + log2(5) * 39 = 105.784615388838 bits (bytes: 14)
> >
> > so this is even better than Freecell. There may be some complications in trying
> > to represent games in mid-play where the prune was not completely followed.
> >
> > For this, there is:
> >
> > $ perl -MLog2 -e 'plog2(4 => 14, 48 => 5)'
> > log2(14) * 4 + log2(5) * 48 = 126.681968242824 bits (bytes: 16)
> >
> > (Because the kings cannot be moved).
>
> replying to myself I'd like to note that I found a way in which we can improve
> on it. At the moment, each card contains the option of {OriginalPlace,
> Parent-H, Parent-C, Parent-S, Parent-D}. However, since if we take the
> 3H/3C/3S/3D, only at most one of them can be on top of the 4H, we can do the
> following analysis on a rank by rank basis:
>
> Rank = r | S=0 | S=1 | S=2 | S=3 |
>
> 4! (All Rank = r-1 cards are above their ancestors, no card is
> in original place.)
> +
> 4 * 4*3*2 (Only one card is in its original place).
> +
> nCr(4,2) * 4*3 (Two cards are in their original place.)
> +
> 4 * 4 (Three cards are in their original place.)
> +
> 1 (All four cards are in their original place.)
>
> Then we get for the four cards in total:
>
> $ perl -E 'say 4*3*2*1 + 4*4*3*2 + 4*3/2 * 4*3 + 4*4 + 1'
> 209
>
> This is instead of 5 to the power of 4 (5**4 == 625) for the four cards
> individually.
>
> Since we don't need to consider the placement of either Kings or Aces, we get:
>
> $ perl -MLog2 -e 'plog2(4 => 14, 12 => 209)'
> log2(14) * 4 + log2(209) * 12 = 107.717729273201 bits (bytes: 14)
>
> Which is lower than the previous attempt. Now to think how to apply this
> technique to Freecell where columns are built by alternate colour.
>
replying to myself again I'd like to note that log2(209) * 12 should have been
log(2) * 11 because there are only 11 ranks excluding Ace and King - not 12, so
we get:
$ perl -MLog2 -e 'plog2(4 => 14, 11 => 209)'
log2(14) * 4 + log2(209) * 11 = 100.01037014112 bits (bytes: 13)
This is really good. We have over 3 bytes to spare to get to 16.
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
"Star Trek: We, the Living Dead" - http://shlom.in/st-wtld
Failure is not an option! It’s bundled with the product.
— Cipher-0 in Freenode’s #perl
Please reply to list if it's a mailing list post - http://shlom.in/reply .
Received on Tue Jul 03 2012 - 08:03:28 IDT