Author |
Topic: Maximize chain reaction (Read 1772 times) |
|
Leo Broukhis
Senior Riddler
Gender: 
Posts: 459
|
 |
Maximize chain reaction
« on: Apr 18th, 2005, 8:14pm » |
 Quote  Modify
|
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.)
|
| « Last Edit: Apr 18th, 2005, 9:26pm by Leo Broukhis » |
 IP Logged |
|
|
|
GoodAdvice
Guest
|
|
Re: Maximize chain reaction
« Reply #1 on: Apr 18th, 2005, 8:43pm » |
Quote Modify
 Remove
|
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.
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Maximize chain reaction
« Reply #2 on: Apr 18th, 2005, 9:29pm » |
Quote Modify
|
on Apr 18th, 2005, 8:43pm, 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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Maximize chain reaction
« Reply #3 on: Apr 19th, 2005, 1:51am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Maximize chain reaction
« Reply #4 on: Apr 19th, 2005, 3:12am » |
Quote Modify
|
I got 1358 on the first chain.  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.
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Maximize chain reaction
« Reply #5 on: Apr 19th, 2005, 8:10am » |
Quote Modify
|
on Apr 19th, 2005, 1:51am, 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.
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Maximize chain reaction
« Reply #6 on: Apr 19th, 2005, 8:23am » |
Quote Modify
|
on Apr 19th, 2005, 3:12am, Deedlit wrote:| I got 1358 on the first chain. 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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Maximize chain reaction
« Reply #7 on: Apr 19th, 2005, 9:34am » |
Quote Modify
|
3149.
But I was just playing around, no particular order.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Maximize chain reaction
« Reply #8 on: Apr 19th, 2005, 12:26pm » |
Quote Modify
|
on Apr 19th, 2005, 8:10am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: Maximize chain reaction
« Reply #9 on: Apr 19th, 2005, 12:54pm » |
Quote Modify
|
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 
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Maximize chain reaction
« Reply #10 on: Apr 19th, 2005, 2:38pm » |
Quote Modify
|
on Apr 19th, 2005, 8:23am, 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.
|
| « Last Edit: Apr 19th, 2005, 2:41pm by Deedlit » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
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 )
--SMQ
|
| « Last Edit: Apr 22nd, 2005, 8:55am by SMQ » |
IP Logged |
--SMQ
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
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.
|
| « Last Edit: Apr 20th, 2005, 3:54pm by Leo Broukhis » |
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Maximize chain reaction
« Reply #13 on: Apr 20th, 2005, 11:36pm » |
Quote Modify
|
on Apr 20th, 2005, 2:03pm, 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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Maximize chain reaction
« Reply #14 on: Apr 21st, 2005, 12:01am » |
Quote Modify
|
on Apr 20th, 2005, 11:36pm, 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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Maximize chain reaction
« Reply #15 on: Apr 21st, 2005, 12:23am » |
Quote Modify
|
on Apr 21st, 2005, 12:01am, 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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Maximize chain reaction
« Reply #16 on: Apr 21st, 2005, 12:53am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Maximize chain reaction
« Reply #17 on: Apr 21st, 2005, 5:43am » |
Quote Modify
|
on Apr 20th, 2005, 11:36pm, 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
|
|
IP Logged |
--SMQ
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
Attached is the relevant script of the original application, for study purposes only (yay Flash Decompiler)
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
|
| « Last Edit: Apr 22nd, 2005, 9:05am by SMQ » |
IP Logged |
--SMQ
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
chainreact1.zip