Well I just wasted a ton of time...

[Sohcahtoa]

...writing a program to solve the current Ultimate Crush bonus offer.

The idea is that you could input the grid of ball colors, and it would brute force a solution on exactly which *bleep* to click to obtain the target score.  It took me about 4 hours to code it, but then I discovered the big problem:

There's a 3 minute time limit to complete the game.

Now, this is a real problem, considering it takes about 3 minutes just to enter the colors into the program.  Of course, it then gets worse.  Even if you've practiced entering the grid fast enough to enter it within the time limit, my program works through brute force.  It checks every possible combination of clicks to find the solution.  I've had it running now on one specific puzzle for over 15 minutes and the highest score it has achieved is 1142.  I'm going to let it run overnight just to see if it ever finds a solution with a high enough score to earn the bonus.

[debraleesparks]

 :thumbsup:Just do one color at a time.

[Sohcahtoa]

You're right.  I don't know why I didn't think of just doing it that way.  I usually try too hard and try to create combos to eliminate a lot of *bleep* at once, but I rarely get more than 10 or so.

But if I instead just get rid of all of one color first, ignoring the fact that I'm often only eliminating 2-4 *bleep*, by the time I've got two of the colors into isolated single *bleep*, I've got HUGE groups of the other two colors.  I got 2500 points from a single click and EASILY made the 75 cent bonus.

Oh well.  It was good programming practice.  I still plan on letting this program run just to see how high of a score it could have gotten on that specific board.

[debraleesparks]

  Good for you!!!

[Administrator]

As a further exercise you could code a routine that takes a screenshot of the board as input and outputs the array of colors on the board.  Then, improve your algorithm and you could solve it in less than 3 minutes

[dgourd]

As a further exercise you could code a routine that takes a screenshot of the board as input and outputs the array of colors on the board.  Then, improve your algorithm and you could solve it in less than 3 minutes

Apparently your not a programmer, cause deciphering a picture is an incredibly complex task.  Might take days to write it up.  Also, its a brute force attack, so improving the algorithm doesn't help, unless he creates a significantly more efficient method of completing the same task which is unlikely considering the simplicity of the game.

[Sohcahtoa]

As a further exercise you could code a routine that takes a screenshot of the board as input and outputs the array of colors on the board.  Then, improve your algorithm and you could solve it in less than 3 minutes

Apparently your not a programmer, cause deciphering a picture is an incredibly complex task.  Might take days to write it up.  Also, its a brute force attack, so improving the algorithm doesn't help, unless he creates a significantly more efficient method of completing the same task which is unlikely considering the simplicity of the game.

Actually, deciphering this wouldn't be too hard, since the *bleep* are in a nice neat grid.  I could easily just test one pixel for each ball, and test for an exact pixel color.

As for improving the algorithm, not really sure how much I can really improve.  This game is really simple, but the number of possibilities to test is immense.  I mean, just from the starting grid, there are 240 (20x12 grid) possible *bleep* to click on.  And after clicking on one of those, it presents another 240 possible places to click, minus the number of *bleep* removed.  It then goes through every possible click after that click, and recurses until it runs into a grid of *bleep* with nothing else to click.

Skipping the clicking of an empty square or a square with no adjacent matches is simple, but that still leaves an absolutely absurd number of possibilities.  So many possibilities, in fact, that even if it took a single clock cycle to do each click, and we ran it on a 4 Ghz CPU, it would STILL take so long to evaluate every single possibility that the Sun would have died by the time it was done.

[Administrator]

Apparently your not a programmer, cause deciphering a picture is an incredibly complex task.  Might take days to write it up.  Also, its a brute force attack, so improving the algorithm doesn't help, unless he creates a significantly more efficient method of completing the same task which is unlikely considering the simplicity of the game.

Actually, deciphering this wouldn't be too hard, since the *bleep* are in a nice neat grid.  I could easily just test one pixel for each ball, and test for an exact pixel color.

As for improving the algorithm, not really sure how much I can really improve.  This game is really simple, but the number of possibilities to test is immense.  I mean, just from the starting grid, there are 240 (20x12 grid) possible *bleep* to click on.  And after clicking on one of those, it presents another 240 possible places to click, minus the number of *bleep* removed.  It then goes through every possible click after that click, and recurses until it runs into a grid of *bleep* with nothing else to click.

Skipping the clicking of an empty square or a square with no adjacent matches is simple, but that still leaves an absolutely absurd number of possibilities.  So many possibilities, in fact, that even if it took a single clock cycle to do each click, and we ran it on a 4 Ghz CPU, it would STILL take so long to evaluate every single possibility that the Sun would have died by the time it was done.

Sohcahtoa is right - it's not too hard since each ball just needs one pixel tested.  It would be pretty difficult to implement this from scratch but most programming languages have an image toolkit which would allow you to accomplish the task relatively easily.

As for improving the algorithm, you could limit the simulated "clicks" to *bleep* which have at least one adjacent ball of the same color.  You could also identify the biggest existing blocks of solid color and try to optimize their size by eliminating nearby *bleep* of other colors.

[Sohcahtoa]

I already do make sure its not a single lonely ball before clicking it.  Its pretty trivial.

As for making it try to create large groups of color...eh...that begins to involve AI, which I have absolutely zero experience with.  I wouldn't know where to begin.  I mean, finding the largest block of similar *bleep* is easily, but trying to make it bigger is hard.

[Administrator]

So if you can identify a big block of color, you can calculate its centroid and then search in an expanding radius for other-colored *bleep* to click...

[Sohcahtoa]

More trouble than its worth, imo.  Sure, its great programming practice, but I've already gotten plenty of that by solving several problems on Project Euler.  I taught myself the basics of C++ by writing programs to solve problems on that page.

To keep going and try to find a better method isn't really worth my time.