Author Topic: blob puzzle  (Read 14245 times)

aimaina

  • Administrator
  • Cutesterest
  • *****
  • Posts: 1320
  • Cutes: 211
    • View Profile
  • Pronouns: she/her
blob puzzle
« 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....



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
windows version: 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
~Without love, the truth cannot be seen~

this is watermelon :watermelon: put her in your signature so she can achieve world domination

aimaina

  • Administrator
  • Cutesterest
  • *****
  • Posts: 1320
  • Cutes: 211
    • View Profile
  • Pronouns: she/her
Re: blob puzzle
« Reply #1 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
~Without love, the truth cannot be seen~

this is watermelon :watermelon: put her in your signature so she can achieve world domination

hubol

  • Cutesterest
  • ******
  • Posts: 1135
  • Cutes: 630
    • View Profile
    • hubolhubolhubol
Re: blob puzzle
« Reply #2 on: August 16, 2018, 01:26:02 AM »
puzzle hard...

SquareWheel

  • Administrator
  • Cutester
  • *****
  • Posts: 802
  • Cutes: 139
    • View Profile
Re: blob puzzle
« Reply #3 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?

aimaina

  • Administrator
  • Cutesterest
  • *****
  • Posts: 1320
  • Cutes: 211
    • View Profile
  • Pronouns: she/her
Re: blob puzzle
« Reply #4 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)
~Without love, the truth cannot be seen~

this is watermelon :watermelon: put her in your signature so she can achieve world domination

SquareWheel

  • Administrator
  • Cutester
  • *****
  • Posts: 802
  • Cutes: 139
    • View Profile
Re: blob puzzle
« Reply #5 on: August 16, 2018, 03:34:22 AM »
Yep I think that's a lot clearer.

SquareWheel

  • Administrator
  • Cutester
  • *****
  • Posts: 802
  • Cutes: 139
    • View Profile
Re: blob puzzle
« Reply #6 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.

aimaina

  • Administrator
  • Cutesterest
  • *****
  • Posts: 1320
  • Cutes: 211
    • View Profile
  • Pronouns: she/her
Re: blob puzzle
« Reply #7 on: August 16, 2018, 03:38:40 AM »
yeha good point that should make things faster
~Without love, the truth cannot be seen~

this is watermelon :watermelon: put her in your signature so she can achieve world domination

aimaina

  • Administrator
  • Cutesterest
  • *****
  • Posts: 1320
  • Cutes: 211
    • View Profile
  • Pronouns: she/her
Re: blob puzzle
« Reply #8 on: August 16, 2018, 03:45:54 AM »
added that, as well as a 4x4 level
~Without love, the truth cannot be seen~

this is watermelon :watermelon: put her in your signature so she can achieve world domination

SquareWheel

  • Administrator
  • Cutester
  • *****
  • Posts: 802
  • Cutes: 139
    • View Profile
Re: blob puzzle
« Reply #9 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.

aimaina

  • Administrator
  • Cutesterest
  • *****
  • Posts: 1320
  • Cutes: 211
    • View Profile
  • Pronouns: she/her
Re: blob puzzle
« Reply #10 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
~Without love, the truth cannot be seen~

this is watermelon :watermelon: put her in your signature so she can achieve world domination

aimaina

  • Administrator
  • Cutesterest
  • *****
  • Posts: 1320
  • Cutes: 211
    • View Profile
  • Pronouns: she/her
Re: blob puzzle
« Reply #11 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)
~Without love, the truth cannot be seen~

this is watermelon :watermelon: put her in your signature so she can achieve world domination

aimaina

  • Administrator
  • Cutesterest
  • *****
  • Posts: 1320
  • Cutes: 211
    • View Profile
  • Pronouns: she/her
Re: blob puzzle
« Reply #12 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.....
~Without love, the truth cannot be seen~

this is watermelon :watermelon: put her in your signature so she can achieve world domination

aimaina

  • Administrator
  • Cutesterest
  • *****
  • Posts: 1320
  • Cutes: 211
    • View Profile
  • Pronouns: she/her
Re: blob puzzle
« Reply #13 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
~Without love, the truth cannot be seen~

this is watermelon :watermelon: put her in your signature so she can achieve world domination

aimaina

  • Administrator
  • Cutesterest
  • *****
  • Posts: 1320
  • Cutes: 211
    • View Profile
  • Pronouns: she/her
Re: blob puzzle
« Reply #14 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
~Without love, the truth cannot be seen~

this is watermelon :watermelon: put her in your signature so she can achieve world domination