Heya fellas, I was just wondering if you could give me a push in the right direction with this simple program I'm writing.
So I downloaded this game, Flow, for my phone and I am unable to solve two of the puzzles. In essence, there is a square grid with two of multiple colors (two reds, two blues, etc.) that one must connect while filling up the entire grid and without crossing lines. My program will take any set-up of initial positions and colors and make the necessary movements, which are ones that MUST be taken, of course. As in this picture: http://imgur.com/mo6D3
I'm now wondering how I should handle the brute force action that I have concluded to be the simplest way. Right now I have a two dimensional array filled with structs that hold info like color, whether the block is either of the ends of the 'snake' that the colors make, and which directions the blocks have been entered from or exited from.
My idea right now is to make a vector of these arrays and push and pop different iterations of them until a single color is finished (the two ends are connected), then begin on the next. I realize this will take a lot of time for bigger grids.
Anything you guys could think of that may help me out here? I feel like I'm going about it the hard way.
Btw, I am programming in C++.
E/G/IN POST /G/RO FIVE STARS HI FIVE /G/ENTOO/G/RO
LEEEEEEEEEEEEELLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL
I
LITERALLY
PEED
MY
PANTS
BUT
JUST
A
LITTLE
NOT
LIKE
IT
GOT
ON
MY
CHAIR
OR
ANYTHING
XDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD /E/GIN TROLL FOR THE WIN
hm, i think i get it. So, in the image somewhere off to the right, there is another column with [R; G; B], you have to link them together and fill the grid.
Sounds like you could use the A* path-finder, with some sort of tree struct, and then 'Prune' all the bad branches as you go?
That is a simple puzzle. The grids become quite large and there are potentially multiple solutions. As you can see, each color has two circles, which are the beginning positions. And in the top- and bottom-right corners, green and yellow, respectively, only have a single move they can make. Those are 'necessary' moves, which my programs already accounts for.
But when the puzzles get larger, those moves stop making as big an impact, because there's so much empty space in between them that it'd take an impressive amount of random guesses to find a correct solution.
If you need more info about the set-up of the puzzles themselves or of my code so far, I'd be happy to oblige.
Name:
Anonymous2012-12-27 3:23
Kind of tricky really...
You could try mapping out all possible links for each colour seperately, just avoiding the other-coloured dots, eg. the red has only three paths, but the blue has 6, and the rest only have 1 each. Then start with the low numbers, so 1, 1, 1 (yellow / green / orange) are fixed paths, then for each red path see if it blocks all the blue paths / crosses any other colours, if it doesn't then it's a solution?
>>13
I may be able to use some form of this, thanks.
The only problem I see, which I have illustrated, is that it seems to look for the shortest paths between two points. This, however, is not always the desired behavior. http://imgur.com/O6eD2
In the picture you can see the hypothetical puzzle set-up in the top-left. In the top-middle is one of the solutions that this wave expansion would give. The top-right shows a desired solution, as it fills the entire grid. The bottom grid shows the wave expansion as the Lee algorithm would have it.
Currently I'm counting the number of empty spaces of the grid and use it as an exit condition from the main loop. Given that an number of empty spaces could be the result of a faulty wire between any of the colors, I'm not exactly sure how I'd go about detecting that and fixing the problem.
I suppose I could check every index in the grid to see if its empty, then check the colors around it and try integrating them into one of their wires?
>>12
Something to this effect may work, but as the grids get bigger each color will have a bunch of possible paths, and I'm not exactly sure how I'd go about counting all of them.
is that it seems to look for the shortest paths between two points
That's the whole point of the algorithm... if you want to fill in I suppose you could route all the traces first, then work on altering the paths to meander them.
So I've run into another little problem. I've always had some trouble with references and pointers, unfortunately.
What I want to do, to avoid continually searching through my 2D array of structs, is create a sort of reference I think.
For example, I'd like to define a variable x to be the same as an index in the array, say array[0][0]. Whenever I change x, array[0][0] changes accordingly. In essence, x IS array[0][0], but with a much simpler name to deal with.
Is this possible? I've tired messing around making pointers and references willy nilly, but I'm not making any headway.
Now *x = v will write to array[0][0], and y = *x will read from it.
Name:
Anonymous2012-12-29 5:17
>>21
Thank you.
I think I tried this, but I'll have to check again in the morning. If the array is of structures, how would I write to its individual index's parts through the referenced pointer?
*x.whatever = w ?
And will I have to keep resetting *x = &array[0][0] so it knows what it'll be writing to? Or does the initialization permanently tie it to that array index in memory?
I've got a buzz on, please forgive.
Name:
Anonymous2012-12-29 5:51
>>21 is that correct? I'm pretty useless when it comes to pointers, but somehow I think it might be
int *x = &array[0][0];
x = v; ? // x.whatever = w; ? >>20,22 the pointer should stay tied to the target's address, unless you tell it to point elsewhere, as in *x++ ? (using a pointer to step through an array?)
>>27
Let's make it, with the updates. Shit is going to be so cash.
Name:
Anonymous2012-12-30 3:22
>>20 Kind of sounds like you want some form of indexing?
Name:
Anonymous2012-12-30 18:37
After some more fiddling, I've found that
int &x = array[0][0];
is the form I'm looking form. So whenever I assign a new value to x, the index it's tied to also changes. This will definitely make things easier and cut down on searching through my array.
Now I'm stuck with the fact that if I use the routing function on a set of color points and it's wrong, then everything after that will be wrong too. So I'm wondering, would it be better to have a secondary array holding a safe 'state' of the board while I work with the other? Or how else might you recommend I deal with this?
Thanks for all the help, I just need to bounce ideas off of people to work out getting stuck in a thought loop.
A photo of a pencil-and-paper sketch uploaded to imgur? I'm so confused!
Name:
Anonymous2012-12-31 9:28
>>36
Why is Cudder-sama so smart? I wish I were like her!
Name:
Anonymous2012-12-31 12:23
You should try asking /g/, I hear they're a lot more knowledgeable than /douche/
Name:
Anonymous2012-12-31 20:17
>>36
Yeah, i didn't expect that it would be equivalent. Still, it should be easier, and a related problem. As a worst-case, you might even be able to use the generator as a brute solver..?