wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Maximize chain reaction
        
(Message started by: Leonid Broukhis on Apr 18th, 2005, 8:14pm)
Title: Maximize chain reaction
Post by Leonid Broukhis on Apr 18th, 2005, 8:14pm
There is a game (Flash required, slow-loading)

http://prikolista.narod.ru/game/gridgame.html

that consists of a 16x16 grid of cells. Each cell contains a disk with two "hands" 90 degrees apart that can be in any of 4 positions within the cell (pointing N &E, E & S, S & W, or W & N). Original position
or the disks is random. A click on a cell causes the disk in the cell to turn 90 deg clockwise.

If at any time a hand of a turning disk at the end of its turn meets a hand of an adjacent disk, the latter turns 90 deg clockwise. (The initial starting position can have connecting hands, in which case one turning disk cat trigger two turns)

The task is to maximise the number of turns caused by chain reactions. What is the starting position and the trigger location for the max. number of turns?

(I got 1947 turns using the flash applet starting from a very regular configuration - maybe their implementation of the algorithm fails to handle higher numbers of simultaneous turns.)
Title: Re: Maximize chain reaction
Post by GoodAdvice on Apr 18th, 2005, 8:43pm
Be wise with Russian websites as many many of them are crack, virus, and trogan related. You'll only know it yourself if your computer becomes infected.
Title: Re: Maximize chain reaction
Post by Leonid Broukhis on Apr 18th, 2005, 9:29pm

on 04/18/05 at 20:43:32, GoodAdvice wrote:
Be wise with Russian websites as many many of them are crack, virus, and trogan related. You'll only know it yourself if your computer becomes infected.


I use 3 different virus/spyware checkers on my Windows machine, and if I want to be comppletely safe, I can always use wget under linux, download the applet and run it from a handwritten HTML page.
Title: Re: Maximize chain reaction
Post by towr on Apr 19th, 2005, 1:51am
The best I got so far is 1394
It does seem though that sometimes it doesn't cascade when it should. Some disk just make a full turn without adjacent discs which are touched reacting.
Title: Re: Maximize chain reaction
Post by Deedlit on Apr 19th, 2005, 3:12am
I got 1358 on the first chain.   :D   Probably the best approach is to try to prove disprove the existence of an infinite chain - if you manage to disprove it, the proof will likely help you find long chains.
Title: Re: Maximize chain reaction
Post by Leonid Broukhis on Apr 19th, 2005, 8:10am

on 04/19/05 at 01:51:09, towr wrote:
The best I got so far is 1394
It does seem though that sometimes it doesn't cascade when it should. Some disk just make a full turn without adjacent discs which are touched reacting.


I am not sure if I've seen a full turn.  A half-turn is possible if both hands of a disk become connected due to simultaneous turning of two neighboring disks. But there is definitely something wrong with the implementation, as sometimes after a massive chain reaction some disks are left connected, often in a group of 4 making a circle.

Maybe someone who knows java can write a better graphical  implementation.
Title: Re: Maximize chain reaction
Post by Leonid Broukhis on Apr 19th, 2005, 8:23am

on 04/19/05 at 03:12:21, Deedlit wrote:
I got 1358 on the first chain.   :D   Probably the best approach is to try to prove disprove the existence of an infinite chain - if you manage to disprove it, the proof will likely help you find long chains.


The proof is trivial: after a corner disk turns to point with both hands to the walls, it will not turn anymore (call such a disk "dead"). After a disk turns to point with each hand to a dead disk or the wall, it dies. There is no way to keep a disk that has two dead neighbors (or a dead neighbor and a wall) 90 degrees apart, from dying indefinitely even with the half-turn rule.
Title: Re: Maximize chain reaction
Post by Grimbal on Apr 19th, 2005, 9:34am
3149.
But I was just playing around, no particular order.
Title: Re: Maximize chain reaction
Post by towr on Apr 19th, 2005, 12:26pm

on 04/19/05 at 08:10:28, Leonid Broukhis wrote:
But there is definitely something wrong with the implementation, as sometimes after a massive chain reaction some disks are left connected, often in a group of 4 making a circle.
I haven't seen that happening.
Unless it was already there in the starting position and didn't move.
Title: Re: Maximize chain reaction
Post by Sjoerd Job Postmus on Apr 19th, 2005, 12:54pm
Some stuff I noticed:
- When you have a circle/circuit, if the chosen turn does not dismantle it, it won't.

- If you do dismantle it, it seems to create about 4 cascades. (depending on the surroundings).

- The layout will become more and more organized every try. A piece will have a > .25 procent change of being oriented a certain way. The most likely direction is towards the nearest corner. Although the latest click does seem to somewhat influence it...

Just some observations :)
Title: Re: Maximize chain reaction
Post by Deedlit on Apr 19th, 2005, 2:38pm

on 04/19/05 at 08:23:37, Leonid Broukhis wrote:
The proof is trivial: after a corner disk turns to point with both hands to the walls, it will not turn anymore (call such a disk "dead"). After a disk turns to point with each hand to a dead disk or the wall, it dies. There is no way to keep a disk that has two dead neighbors (or a dead neighbor and a wall) 90 degrees apart, from dying indefinitely even with the half-turn rule.


OK, I guess that gives us an upper bound of 3n, where n is the number of squares.  Let f(n) be the max for n squres. Take an n square configuration, remove a square with at most two neighbors.  The remaining configuration will have at most f(n-1) rotations before it comes a stop; the extra square can restart the chain at most two times before it becomes dead, so the max for n squares is no more than 3 f(n-1) + 4 (the extra square could be the first turned, and could then get turned three more times).  That plus f(1) = 1 gives the bound 3n.
Title: Re: Maximize chain reaction
Post by SMQ on Apr 20th, 2005, 2:03pm
Attached is a Windows (98/Me/2K/XP) version I whipped up for anyone who's interested.

Left mouse button starts the raction
Right mouse buttoin rotates w/o reacting
Middle mouse button shows/hides
(all are dragable to select multiple cells)

The rest of the UI should be self explanatory.

Save/Open could be useful for creating/editing a pattern in a text file rather then through the GUI.

Oh, and in case you don't trust me not to be posting a virus (hey, I understand!), the VC6 source is included.

Hopefully somebody will find this useful. (Or at least fun;D)

--SMQ
Title: Re: Maximize chain reaction
Post by Leonid Broukhis on Apr 20th, 2005, 3:16pm
Well, here's mine (Linux, command line).  Compile with C++,
run (with no arguments for speed, with any argument to step through moves), enter "0 0" as the first trigger point, then "0 15" twice, then "15 15" to get 4780 moves.

[e] My program uses a different algorithm (with the half-turn rotation as fast as quarter-turn). I'll keep you posted.
Title: Re: Maximize chain reaction
Post by Leonid Broukhis on Apr 20th, 2005, 11:36pm

on 04/20/05 at 14:03:56, SMQ wrote:
Attached is a Windows (98/Me/2K/XP) version I whipped up for anyone who's interested.


I see you've decided to dispense with double moves altogether. This algorithm does not produce chains that are as unpredictably spectacular as the original or as my variant.  I've looked at the original and although I was able to deduce that it has a notion of gravity (unlike mine), I was not able to figure out the rule allowing to make three quarter-turns without triggering a neighboring cell.
Title: Re: Maximize chain reaction
Post by towr on Apr 21st, 2005, 12:01am

on 04/20/05 at 23:36:33, Leonid Broukhis wrote:
I see you've decided to dispense with double moves altogether. This algorithm does not produce chains that are as unpredictably spectacular as the original or as my variant.
So in which cases do you do double moves?
Because possibly with double moves, the chain could go on for ever because both hands are never against the wall (due to double moves preventing it)
Title: Re: Maximize chain reaction
Post by Leonid Broukhis on Apr 21st, 2005, 12:23am

on 04/21/05 at 00:01:53, towr wrote:
So in which cases do you do double moves?
Because possibly with double moves, the chain could go on for ever because both hands are never against the wall (due to double moves preventing it)


A double move happens if both hands are triggered at the same time.  If it happens to a corner cell, both hands turn to the wall and the cell dies. If one hand points to the wall, a double move is impossible.
Title: Re: Maximize chain reaction
Post by towr on Apr 21st, 2005, 12:53am
I think I found out how a 3 quarter turn happens.
If the disc is doing a double turn, and does seem to pick up a turn from an adjacent disc, without returning the favour.
If my suspicion is right, with a lot of luck, you could get an infinite loop as well. But you can't construct it it the applet.
Title: Re: Maximize chain reaction
Post by SMQ on Apr 21st, 2005, 5:43am

on 04/20/05 at 23:36:33, Leonid Broukhis wrote:
I see you've decided to dispense with double moves altogether

I'm working on adding it (and several other things) as options, but I thought I'd start with the simplest-to-analyze case and go from there.

--SMQ
Title: Re: Maximize chain reaction
Post by SMQ on Apr 21st, 2005, 6:06am
Attached is the relevant script of the original application, for study purposes only (yay Flash Decompiler) ;D

That should be enough to answer any implementation questions.


Edit: Those unfamiliar with the implementation details of Flash (like myself) may find http://www.macromedia.com/support/flash/action_scripts_dict.html useful.


Edit 2: To sum up:

a) The relevant state of each cell consists of its current orientation (this._rotation) and a target orientation (this.rot)

b) Clicking a cell increments its target orientation by 90 degrees CW

c) Cells rotate (all at the same speed) until their target orientation is reached without influencing other cells

d) When a cell comes to rest, any neighbors it is "shaking hands" with have their target orientations incremented by 90 degrees CW even if they are already rotating

I think those rules explain the observed 1/2 turn and 3/4 turn rotations.


Edit 3: The original Shockwave app has a race condition--if two adjacent cells come to rest simultaneously with "hands touching" only one of them will start the other (which ever one is scheduled first by Flash's internal task scheduler.)  That may account for some of people's observations of cells not turning when they should.


Edit 4: There's another race condition with the ready flag, which also can cause cells not to trigger when they should.  The original was obviously written just for fun rather than as a serious simulation...


Edit 5: I updated my program above to allow you to choose different simulation rules:

"Simple" is the ruleset I started with: multiple touches cause only one 90 degree turn.

"Original" is as close to the Shockwave app as I can get without introducing a random factor to mimic the ready-state race condition.  It is (in my estimation) qualitatively the same as the original.

"Accurate" also removes the mutual-touch race condition, leading to generally higher numbers than the original but much the same "feel."

"Every Touch" adds a trigger when a cell turning >90 degrees brushes past a neighbor.  This can lead to cells building up a substantial "rotation debt", and so has a much higher count than the original


--SMQ


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board