Cutey Zone

General Category => Cute Discussion => Topic started by: aimaina on August 15, 2018, 11:56:12 PM

Title: blob puzzle
Post by: aimaina on August 15, 2018, 11:56:12 PM
i coded up a quick puzzley thing..... might add more levels and stuff but its just one puzzle now....

(http://love-game.net/img/blob.png)

these are the somewhat complicated rules. the game takes place on a grid, and is divided into "rounds" that proceed as follows:

1. when you click "Split", all big blobs split into two small blobs
2. one of the two small blobs can move any distance on the grid but only horizontally, and the other can move any distance but only vertically. when you click a small blob, it will turn red and a bunch of blue blobs will appear; the blue blobs represent legal moves for the red blob (you click the blue blob to move the red blob there)
3. a blob is allowed to stay in the same square (it counts as a move of distance zero)
4. multiple small blobs are allowed to move onto the same square (in-game they just overlap each other)
5. (important! this is what makes the puzzle hard) horizontal-moving small blobs that are in the same column must make the same move. vertical-moving small blobs that are in the same row must make the same move. when you click a blob, it will also highlight all the other blobs that are forced to make the same move
6. once all small blobs have been moved, you can click "Grow" to end the round. the small blobs all regrow into big blobs, and small blobs that ended up on the same square are subsumed into one big blob

my code is kind of shitty and probably buggy so let me know if you manage to do anything that violates these rules

how did i come up with this terribly convoluted puzzle you ask. well its based on an open problem in theoretical computer science that i am working on. its not a famous problem with a $1000000000 prize or anything but its important to a small community of researchers. say a configuration of big blobs on the grid is "valid" if the topmost row contains at least one blob, and the leftmost column contains at least one blob. the problem is to formally prove that for all m x n grids (where m and n are arbitrary positive integers), every valid configuration is reachable from the initial configuration (with one big blob in the top-left). if you can figure this out then pm me and we can write a joint paper about it

html5 version: love-game.net/blobpuzzle (http://love-game.net/blobpuzzle)
windows version: love-game.net/blobpuzzle.zip (http://love-game.net/blobpuzzle.zip)

the undo feature currently does not work in the html5 version (i used the gm built in save feature bc i was lazy) so i recommend the windows version if you can be bothered to download it
Title: Re: blob puzzle
Post by: aimaina on August 16, 2018, 12:51:39 AM
added a second level, not so much intended to actually be fun to play but more to demonstrate how difficult this can get. i havent tried very hard to solve it. if you manage to solve it and document/describe your solution process, that might be helpful to me, as long as your solution isnt just intense amounts of trial and error or a brute-force search or something

the difficulty i have with this problem is finding "predecessors" of configurations. if you have a configuration C, say that C' is a predecessor if a) C' contains fewer blobs than C and b) C can be reached from C' in a single round. if i had a general technique to find predecessors of arbitrary valid configurations, then i could build up solutions by induction on the number of blobs or something, but for certain configurations (like the one in the second level) it seems very non-obvious to me how to construct a predecessor
Title: Re: blob puzzle
Post by: hubol on August 16, 2018, 01:26:02 AM
puzzle hard...
Title: Re: blob puzzle
Post by: SquareWheel on August 16, 2018, 02:06:05 AM
Yep I'm not really sure how to approach this.  I find it difficult to visualize the other blobs moving on the same axis.  Maybe hovering over the blue blobs should preview shifting the other pieces over as well?
Title: Re: blob puzzle
Post by: aimaina on August 16, 2018, 03:31:33 AM
i upgraded the visual design a bit..... check it out (might need to clear cache if u get graphics glitches)
Title: Re: blob puzzle
Post by: SquareWheel on August 16, 2018, 03:34:22 AM
Yep I think that's a lot clearer.
Title: Re: blob puzzle
Post by: SquareWheel on August 16, 2018, 03:37:29 AM
Should it be possible to grow without placing all pieces?  Seeing as it's the equivalent of just placing them in the same spots again.
Title: Re: blob puzzle
Post by: aimaina on August 16, 2018, 03:38:40 AM
yeha good point that should make things faster
Title: Re: blob puzzle
Post by: aimaina on August 16, 2018, 03:45:54 AM
added that, as well as a 4x4 level
Title: Re: blob puzzle
Post by: SquareWheel on August 16, 2018, 03:58:00 AM
Feels better.  Growing after each move is kinda helpful for taking stock of the board.

Two bugs I found:
1. The first click on a large kitty will often select the vertical or horizontal small kitties as well.  Maybe release the LMB after a split action to prevent that.
2. I had a crash in the html5 version that I haven't been able to reproduce.  I reset while I had a full board and small kitty selected.  Some blue ones were still visible on the board while everything else reset correctly.  The game froze up and the JS console was spitting out errors.  I didn't record them because I'm a dumdum.
Title: Re: blob puzzle
Post by: aimaina on August 16, 2018, 04:03:15 AM
im not sure if forcing an lmb release in the conventional way works in gm html5. theres probably a stupid workaround i can do though. i think the windows version doesnt have the problem you describe

and i have no idea what could have caused that crash, because the reset button just calls room_restart instead of doing anything fancy. might be a mysterious game maker bug
Title: Re: blob puzzle
Post by: aimaina on August 16, 2018, 04:19:09 AM
i found a solution to the 4x4 puzzle by just messing around for a while.....
Spoiler (click to show/hide)
Title: Re: blob puzzle
Post by: aimaina on August 16, 2018, 04:47:32 AM
i think i want to have a level select screen with a whole bunch of systematically generated levels, and a feature that lets you "preload" the board with configurations you have previously reached or something, then it will be possible to really experiment with techniques for solving these and see if i can find patterns....

im not gonna do that tonight thou.....
Title: Re: blob puzzle
Post by: aimaina on August 16, 2018, 03:59:28 PM
i managed to solve the 5x5 puzzle by working backwards but im not sure how to formalize/generalize the method yet. here are my notes
Spoiler (click to show/hide)
i guess the problem i have now is to prove for general boards that either the "combining technique" or "overlap technique" is always possible in at least one place.... if thats even true
Title: Re: blob puzzle
Post by: aimaina on August 17, 2018, 09:26:11 PM

000..
00.0.
0.0.0
.0.00
..000

thinking about this puzzle.... my "combining technique" doesnt seem to work here
Title: Re: blob puzzle
Post by: aimaina on August 18, 2018, 10:45:43 AM
web version has undo now. it also defaults to the puzzle from the previous post that im stuck on because i might post this on my twitter to ask for help lol

you can also edit the target board by clicking it if you want to temporarily set it to an intermediate solution step or something, and you can place some markings on the target board by right clicking blobs which may or may not be useful for finding intermediate steps
Title: Re: blob puzzle
Post by: aimaina on August 18, 2018, 03:41:20 PM
solved the puzzle with some help from a paper on the subject..... the target is this

000..
00.0.
0.0.0
.0.00
..000

below is one possible predecessor configuration, given by deleting a column and rearranging the remaining columns according to a specific permutation. thats an approach i didnt think of at all but someone else figured it out so i dont have to

0..0.
...00
0.0..
..000
0.0.0

now that i understand the method from that paper, this gives a new class of puzzles i know how to solve..... will have to search for more puzzles that these techniques cannot do
Title: Re: blob puzzle
Post by: dcco on August 20, 2018, 06:31:52 PM
what kind of research problem does this solve? im curious
Title: Re: blob puzzle
Post by: aimaina on August 20, 2018, 08:08:30 PM
i can pm you about it, since if u know what area of research im in its not too hard to find my full name and school and etc
Title: Re: blob puzzle
Post by: aimaina on August 21, 2018, 05:26:05 AM
i think i have given up on this because i dont know how to solve this puzzle and even if i figure it out, who knows what other weird kinds of puzzles are out there.....

0.0..0...
0.0...0..
0.0....0.
0.0.....0
0..0..0..
0..0...0.
0..0....0
0...0..0.
0...0...0
0....0..0
.0.0..0..
.0.0...0.
.0.0....0
.0..0..0.
.0..0...0
.0...0..0
..0.0..0.
..0.0...0
..0..0..0
...0.0..0
Title: Re: blob puzzle
Post by: aimaina on August 21, 2018, 07:32:03 PM
another smaller puzzle i dont know hjow to do with the techniques i know of....

0000..
00..00
0.000.
0.0.00
.000.0
.0.00.
Title: Re: blob puzzle
Post by: aimaina on August 21, 2018, 07:35:28 PM
oh wait its easy to find a predecessor there i just didnt try by hand
Title: Re: blob puzzle
Post by: dcco on September 12, 2018, 02:43:43 AM
hey, did you just check the cutey zone to see if someone made a new post and found this post? if so hello.
Title: Re: blob puzzle
Post by: SquareWheel on September 12, 2018, 03:55:39 AM
Hi!
Title: Re: blob puzzle
Post by: wilde32 on September 16, 2018, 10:53:34 AM
Quote from: dcco on September 12, 2018, 02:43:43 AM
hey, did you just check the cutey zone to see if someone made a new post and found this post? if so hello.
i am the ducko
Title: Re: blob puzzle
Post by: hubol on September 16, 2018, 12:28:07 PM
LOVE these new posts!!!
Title: Re: blob puzzle
Post by: wilde32 on September 16, 2018, 02:04:18 PM
Quote from: hubol on September 16, 2018, 12:28:07 PM
LOVE these new posts!!!
i love you too
Title: Re: blob puzzle
Post by: SquareWheel on September 16, 2018, 07:56:47 PM
 :chili: