Message #1253

From: Andrey <andreyastrelin@yahoo.com>
Subject: Re: [MC4D] Parity in 12 Colors
Date: Fri, 05 Nov 2010 08:27:40 -0000

Melinda,
there is no problem in this hash function.
Suppose that you know the symmetric group of your puzzle body. It my be tesseract (192 states), 100x100 duoprism (20000 states), 3^7 (64*5040=322560 states) and so on. You take the state of the puzzle in the form of array of sticker colors. Then perform the loop for all orientations of the puzzle:

• build array of sticker colors for this orientation;
  
• renumerate colors so that first color in array has number 0, second different of it has numer 1 and so on…
  
• select the minimal colors array (in lexicographis order) for all states.
  This array will be the "canonical form" of the puzzle state. For the hash value just code it in the best numeric system (like 3 bits per color for 3^4). Of course, it will be longer then the shortest possible representation, but not much.

Andrey

— In 4D_Cubing@yahoogroups.com, Melinda Green <melinda@…> wrote:
>
> MC4D contains an optimization function that Don wrote, but I currently
> don’t connect it to any commands or controls because it got broken at
> some point; probably by me.
>
> You also just gave me a great idea for a math problem for someone on
> this list: Develop a function that takes a puzzle state and returns a
> hash code that will be identical for all permutations of color codes and
> whole model rotations, and will be different from all other states. That
> may be extremely difficult or even impossible, but if it is possible
> then it would clearly be very valuable.
>
> -Melinda
>
> On 11/4/2010 6:07 PM, Andrey wrote:
> > Sometimes I had a trouble with undo after removing of a pair of twists. Usually it happens when you make wrong operation sequence that is started with the removed twist, find that it was wrong sequence (in wrong direction, or on wrong faces), undo it (by the proper number of Ctrl-Z) and find yourself in couple of twists from where you started. And no way to return back. That was a reason why I removed this feature from MC7D. Another reason was with F1-F4 commands: you need extra marks to make start and end of the "setup" sequence unremovable. And I thought that it will be better solution to write optimization command one day… but didn’t do it in MC7D. May be MHT will be more lucky.
> > I’m not sure that it will be easy and good idea to optimize movements of one cell: if user can’t find two twist sequence that sets cell in the desired position and makes eigth twists instead - why should the program think for him? But remove parts of sequence between identical positions is a good idea. We don’t need to keep complete positions for it - it’s enough to remember some 64-bit hash codes for positions (and probably check that positions with equal codes are identical indeed). And I agree that we don’t need to check orientations of 1C stickers: if the program considers some position as solved one then it’s identical to the starting position.
> >
> > Andrey
> >
> >
> > — In 4D_Cubing@yahoogroups.com, Melinda Green<melinda@> wrote:
> >> On 11/4/2010 2:12 PM, Brandon Enright wrote:
> >>> —–BEGIN PGP SIGNED MESSAGE—–
> >>> Hash: SHA1
> >>>
> >>> On Thu, 04 Nov 2010 14:01:30 -0700
> >>> Melinda Green<melinda@> wrote:
> >>>
> >>> […]
> >>>> I’d really
> >>>> like to take that to it’s ultimate extreme and prune out any move
> >>>> sequences that loop back to any previous state, regardless of the
> >>>> number of moves involved. With the exception of returning to the
> >>>> solved state of course. :-)
> >>> This would be great and easy to do at the expense of a bit of memory.
> >>> Puzzle state is small though so storing 10,000+ puzzle states is no big
> >>> deal for modern computers. We could stuff the states into a tree for
> >>> faster searching.
> >>>
> >>> I think it is important though that the state is truly identical
> >>> rather than just apparently identical. That is – shuffling around
> >>> some identical 1c pieces should count as a different state.
> >> Well to do that right does not seem easy to me, at least not with the
> >> definition of puzzle state that I’m thinking about. I feel that the
> >> ideal implementation wouldn’t distinguish between states that are
> >> identical except for color swapping, or state changes that amount to 4D
> >> rotations or both. For example, if you got to within a single 90 degree
> >> twist of being fully solved but then took a detour that eventually
> >> brought you to another state that has a different face that’s also one
> >> 90 degree twist from being solved, I would want to "subtract" all the
> >> moves in that detour. The trouble is that I’m not at all sure how to
> >> efficiently detect those sorts of cases. At the very least I’d love to
> >> turn any consecutive sequence of twists of a single face into a single
> >> twist, whenever possible. For example, four identical 90 degree twists
> >> should simply vanish from the history, or at least there should be an
> >> option to have that happen, and solutions that used that sort of pruning
> >> should count towards shortest records.
> >>
> >> -Melinda
> >>
> >
> >
> >
> > ————————————
> >
> > Yahoo! Groups Links
> >
> >
> >
> >
>