Flash fun
July 12, 2005 12:45 PM   Subscribe

Planarity Arrange the vertices such that no edges overlap. Or, A Farewell to Productivity
posted by boo_radley (91 comments total)
Bad boo. Bad..
posted by smcniven at 12:48 PM on July 12, 2005

I can't do the third one. Grr.
posted by iconomy at 12:49 PM on July 12, 2005

Thise is awesome.
posted by oddman at 12:50 PM on July 12, 2005

There's got to be some simple mathematical rule one can follow to solve these, hasn't there?

(also: fun!)
posted by Marquis at 12:51 PM on July 12, 2005

I think it's fair to say that, given the chance, my boss would beat the sh*t out of you for this.
posted by NinjaPirate at 12:51 PM on July 12, 2005

So awesome it left me temporarily unable to spell simple words.
posted by oddman at 12:51 PM on July 12, 2005

Ok I did the third one, but no way am I doing the next one. But then again I said that last time, so...

[this is fun]
posted by iconomy at 12:53 PM on July 12, 2005

I finished 6 before the boss started throwing things at me.
posted by monju_bosatsu at 12:58 PM on July 12, 2005

This rocks my world. First flash puzzle game that seems to be based on a new concept that I have seen in a long time.

Level 6 and counting...
posted by googly at 12:58 PM on July 12, 2005

I'm on the fifth one, and as soon as I finish it, I'm going to go find boo radley and kill him/her.

As soon as I finish the 6th one.

Okay, the 7th, definitely by the 8th, I'll be ready to hunt down boo...
posted by jennaratrix at 1:01 PM on July 12, 2005

I'm pretty sure there are algorithms for finding planar embeddings of graphs. That said, I don't think they are obvious or simple.
posted by chunking express at 1:03 PM on July 12, 2005

Nice, nice. I'd like to see a version of this implemented on a toroidal playing surface (even if it's just done by identifying edges in the current implementation). Many more graphs would be possible.
posted by Wolfdog at 1:05 PM on July 12, 2005

Like untying a knot (an activity I find oddly soothing).
posted by jrossi4r at 1:07 PM on July 12, 2005

There's got to be some simple mathematical rule one can follow to solve these, hasn't there?

Mathematically, the game is to find a planar embedding of a planar graph. This problem can be solved for a graph in a number of steps linear in the number of vertices, but it isn't particularly simple.
posted by driveler at 1:09 PM on July 12, 2005

From the perspective of 4 pm-ish local time, it must be due to the long ago exhaustion of any residual brain power gleaned from my morning stimulant, but "arrange the vertices such that no edges overlap" ??

Can someone please re-cast that in, maybe, plainer English (and no that's not a "planar" typo!)?

posted by Mike D at 1:10 PM on July 12, 2005

There's got to be some simple mathematical rule one can follow to solve these, hasn't there?

Simple, no. But there are algorithms for creating network diagrams. A list of software for both analyzing and drawing here.

Crippled from years of using these programs, I couldn't get past the second diagram when I first heard about this a few days ago...I'm going to try again now.
posted by duck at 1:11 PM on July 12, 2005

Mike: arrange the dots so that no lines cross.
posted by googly at 1:11 PM on July 12, 2005

Couldn't you just wait for Friday? Jeez!
posted by carmina at 1:13 PM on July 12, 2005

This is fantastic.
posted by evinrude at 1:14 PM on July 12, 2005

Time Sink Hole... I got to Level Four! Sent this to The Boyfriend™ - I won't see him again for hours!
posted by Corky at 1:26 PM on July 12, 2005

Wow, reminds me of all the abstrac Comp Sci classes I ever took, for good reason.

Here's the stratagy I used to solve #5. Take all the dots connected to only two other dots, and put them on the outside, then do the same for the dots with three, and put all the dots with four in the center. Then try to get all the connected dots close to their 'parents' (meaning the dots farther from the center), you might have to move around the outer dots. From there, just work it out as you had been doing. on the easier stages.
posted by delmoi at 1:38 PM on July 12, 2005

This is fun, but I'd find it a lot easier if I could see the whole thing on my screen at once.
posted by jacquilynne at 1:42 PM on July 12, 2005

Not a mathematical model as such (though as pointed out earlier such solutions are an important study) but I do have some tips.

Try thinking of the diagram as being a 'web' of springs. Bring nodes closely connected closer together. Try taking some highly connected nodes and move them until their vertices radiate evenly, starfish like. Reduce tension. Optomize locally.

On preview - what delmoi said ;)
posted by mce at 1:43 PM on July 12, 2005

After doing one and two lickety-split I was beginning to feel like some sort of genius. Three put me in my place at which point I quit.
posted by Carbolic at 1:49 PM on July 12, 2005

I finished level 9 last night (mostly because Kottke [Waxy?] said he got through level 8, and I'm stubborn).

No way am I getting back into it here at work. _Far_ too much of a time sink.

Tonight, though...

On preview: my general take was similar to mce's. I ended up thinking of the strings as elastic, and doing what I could to bunch clusters together in the center...after a while, it made it easier to start to see patterns and intuit which movements would work best next.

That, and a _lot_ of trial and error.
posted by djwudi at 1:49 PM on July 12, 2005

Back in college I was screwing around with Kohonen Self Organizing Feature Maps, which learn a relatively smooth n-dimensional surface in an m-dimensional space that roughly confirm to a set of m-dimentional points it's trained on. With m and n = 2, it was really easy to show on the screen - just a grid which starts out all tangled (like these do) on the screen. As I fed it training points it would kind of shake itself out and end up being a regular grid, with maybe a twist in it. It was really fun to watch (or to train it on your mouse!) and this strongly reminds me of it.

It had that feeling of just kind of shaking it until it settles out into a simpler configuration.
posted by aubilenon at 1:50 PM on July 12, 2005

This is great. Levels one through four I could fiddle through intuitively within a couple of minutes. Level five feels like it will take three times that long just to move the dots around to the appropriate sides.

(On preview, keeping something like mce's well-said "reduce tension" directive at heart is probably roughly how I had been stumbling through the earlier levels.)
posted by nobody at 1:50 PM on July 12, 2005

got to level 7
posted by delmoi at 1:51 PM on July 12, 2005

My metaphore is to think of it like a piece of crumpled paper that I am trying to uncrumple. Crossed edges indicate that part of the "paper" is overlapping, and that image can sometimes help find the axis/crease that needs to be unfolded next.

The springs metaphore works well at the start of each level, although if you take it too far you can wind up with all the vertices clumped in an ugly little blob in the middle.

I got to 10, but at that point it was taking so long for the program to detect if I had won or not it was getting more frustrating than fun. There was about a 10-20 second pause after moving each vertex towards the end of level 9. Makes it hard to experiment.
posted by bhorling at 1:52 PM on July 12, 2005

8 is a pain...
posted by carmina at 1:52 PM on July 12, 2005

That sheet is fun!
posted by dig_duggler at 1:52 PM on July 12, 2005

great game -
thanks, boo_radley
posted by tcp at 1:54 PM on July 12, 2005

bhorling, what (seems) to work for me is to gather a few red dots together at a time and then (usually) you can see what
could act as a perimeter (or a larger loop)...
posted by carmina at 1:55 PM on July 12, 2005

> I'm pretty sure there are algorithms for finding planar embeddings of graphs.
If you're good at 3-d thinking, it's easy to embed any one of these graphs into a surface of higher genus. Now repeatedly surger the surface to reduce genus until it's a punctured sphere and project back into the plane.
posted by Wolfdog at 1:55 PM on July 12, 2005

I have a similar approach to mce and djwudi. I start out by clearing a space in one part of the screen, then move a point there and start "bunching" together points that are joined. Points with only two connections form little self-contained triangles that often don't have to be adjusted for the rest of the screen. Got me to level 9, then I quit because it becomes tedious trying to arrange the points in such a small space...
posted by googly at 1:58 PM on July 12, 2005

It's like a untying a knot alright, a knot designed by SATAN!
posted by tula at 2:00 PM on July 12, 2005

I'm really good at this game, for once. I always was good at spatial relationships. I got through level 8 after 10 minutes, then stopped.
posted by sciurus at 2:02 PM on July 12, 2005

wolfdog just made my brain asplode. great game, thanks!
posted by crunchywelch at 2:03 PM on July 12, 2005

got to level 8 :)
posted by delmoi at 2:09 PM on July 12, 2005

Wolfdog: I tried that but my brain broke. You owe me a new brain.
posted by Sparx at 2:12 PM on July 12, 2005

stopped after level 7 because i got tired of moving those circles around.

they should have a shift-click multi-select of the vertices...
posted by growli at 2:21 PM on July 12, 2005

It is a lot like doing printed circuit board layout (the memories...)
posted by Chuckles at 2:24 PM on July 12, 2005

I'm always the one who untangles the Christmas lights every year, and and my girl-friends always bring me their necklaces to unknot (my like jrossi, I find this fun to do, for some odd reason). I finished level 10 after 16 minutes.

My strategy is to go around the outside and put the dots that are connected to four others in the "center" of their group. Keep doing that continuously until you get done with the circle. It helps.

I'd do 11, but I'm afraid it's going to crash my laptop. (Boo, hiss.) Thanks boo_radley.
posted by ArsncHeart at 2:36 PM on July 12, 2005

got to level 9 :P
posted by delmoi at 2:49 PM on July 12, 2005

Well, that was fun. Back to food, sex, and sleep.
posted by buzzman at 2:50 PM on July 12, 2005

and, there I stopped.

By the way, if you click "reshuffle" you'll get the same graph (I think) but rearanged randomly. It's still a better starting place then the circle, IMO.
posted by delmoi at 2:52 PM on July 12, 2005

Okay...I went and did 11 anyway, and specifically concentrated on centering every dot in the middle of its group. Makes things messier at first, but eventually works for me. YMMV.
posted by ArsncHeart at 2:52 PM on July 12, 2005

This is evil. I'm glad it's 6:00 and time for me to go home.

Now all I have to fear is a palm version.
posted by alms at 2:57 PM on July 12, 2005

ArsncHeart, that's called the "rubber band" solution. It's mathematically pretty complex, actually, but the idea is beautifully simple. (It doesn't always work for this problem...)
posted by louigi at 3:04 PM on July 12, 2005

Got to level 8 before I remembered I have a job. I found a good initial strategy was to assume that at the finish most dots will not connect with dots on the other side of the graph. So, grab a dot at random and drag it to the side, then grab every other dot connected to it and make a pile near first one. Do this for about 20% of the dots, then grab an as-yet-unmoved dot and start a new pile. Eventually you should have several piles with a (relatively) manageable number of connections between them.
posted by bjrubble at 3:06 PM on July 12, 2005

That's pretty fun though I didn't find it especially difficult. I think it needs the rag doll bikini lady bouncing around it to make it more exciting.
posted by fenriq at 3:23 PM on July 12, 2005

Hrmm, the more I play this, the more I think the function behind it would be nice and useful for laying out complex interface charts. I'd like to be able to custom link my dots and then drag them around to get a nice layout of my applications with no crossing lines.
posted by jacquilynne at 3:30 PM on July 12, 2005

Wouldn't we all.
posted by nervousfritz at 3:43 PM on July 12, 2005

I'm at level 11 with a score of 97,133. Not bored yet.
posted by furtive at 3:51 PM on July 12, 2005

You people are sick.
posted by jokeefe at 4:05 PM on July 12, 2005

1,631,398 - Level 14 complete. I think I will have to quite, it is getting really really slow!
posted by Chuckles at 4:06 PM on July 12, 2005

I think being a rock climber has helped me out with this excercise especially one who initially had to deal with multipitch climbs with parties of 3, tangled ropes, and not much time before the sun went down.

Fun game, though I wish it would say just how many levels there are!
posted by Fricka at 4:06 PM on July 12, 2005

Fantastic game. I cruised through level 5 and now I'm stumped. There's an art to it, though.
posted by ryanhealy at 4:06 PM on July 12, 2005

I think Chucles wins. I'm at 12 and not sure if I feel like going futher.
posted by furtive at 4:13 PM on July 12, 2005

I wasted hours playing this last night. I thought level 12 would be the last, as the circle looked full. When I got to 13, I thought about leaving it open until the morning, but decided instead to quit and pretend it wasn't there, taunting me with its chaos, begging to be ordered. Only to see this post now. They either need to provide game saves (or level passwords), or start a 12 step program.
posted by scottreynen at 4:21 PM on July 12, 2005

Okay, I just completed level 15. That took about half an hour, it must have teken 5 minutes just to calculate my last move... I think that means it is time to quite.
posted by Chuckles at 4:41 PM on July 12, 2005

all the fun of undoing knots!
posted by es_de_bah at 6:10 PM on July 12, 2005

I bet if you solve level sixteen some guy with pins in his face comes and shoots chains into your body...
posted by Citizen Premier at 6:28 PM on July 12, 2005

Having just completed Discrete Math last semester...I hate you ;)
posted by Who_Am_I at 6:36 PM on July 12, 2005

Got through Level 3 before I realized I'd been sucked in. I didn't mean to do it.
posted by Peach at 7:03 PM on July 12, 2005

Finished level 10 just now. I think that's it for me. I'm supposed to be packing!

I was using a modified rubber band method. I would get a random node in the middle of all it's attached nodes and repeat that for a while until an obvious pattern emerged. When I lost the pattern, I'd go back to the rubber band thing.

posted by Elsbet at 7:09 PM on July 12, 2005

Theoretically, if I keep hitting "shuffle vertices" they will all solve themselves eventually, correct?
posted by yhbc at 7:36 PM on July 12, 2005

If you finish 16 you get drafted into an alien army to fight a war where the enemies are intersections of lines... ala last starfighter if any of you remember that fantastic, fantastic movie.
posted by BlackLeotardFront at 7:52 PM on July 12, 2005

It's more like Time Out of Joint, actually.
posted by kenko at 8:05 PM on July 12, 2005

Made it to 13 and decided it was no longer worth it. Been dreaming of nodes and tangles all night.
posted by Falconetti at 8:25 PM on July 12, 2005

This is about as much fun as untangling string.

Image Hosted by ImageShack.us

And yes, I did other things during that 2 hours. I don't think I will attempt level 17. There won't be enough blank space for copying structures. My basic approach in the higher levels is to get regions sorta right then transfer them into a blank area while preserving most of the 'topology' and fixing the errors.

If the screen could scroll infinitely to the left and right the some of the needless copying could be avoided.
posted by MonkeySaltedNuts at 8:52 PM on July 12, 2005

level 37 had colored vertices that had to be arranged in a certain order.
posted by angry modem at 10:58 PM on July 12, 2005

Watch out! After level 50 there are gas pockets that can kill you instantly!
posted by squidlarkin at 11:42 PM on July 12, 2005

But then you fight the devil and it's so awesome.
posted by rafter at 11:47 PM on July 12, 2005

I say we nuke boo from orbit. It's the only way to be sure.

I tried earlier and gave up after the first one. I just did the fourth one. Yay me!
posted by deborah at 12:17 AM on July 13, 2005

I finished Level 13 before my CPU crapped out on me. Great game... and under 7KB in size, at that!
posted by Down10 at 12:26 AM on July 13, 2005

Check out the high scores, #3 - apparently someone at G4 (or a fan) is a bit obsessive.
posted by abcde at 12:44 AM on July 13, 2005

It would be awesome if graph untangling were isomorphic to prime factorization and John Tantalo were using a distributed network of humans to crack crypto.
posted by aubilenon at 1:29 AM on July 13, 2005

boo_radley: Please die or be killed. Now. Or help me die. Faster.
posted by bdave at 5:54 AM on July 13, 2005

MonkeySaltedNuts, if you did a board layout like that you would be fired (looks like an effective enough strategy for the game though).
posted by Chuckles at 5:54 AM on July 13, 2005

this is too much like UV mapping for textures in 3d animation .. so it kinda is my job. perhaps i won't get fired
posted by mrben at 6:08 AM on July 13, 2005

"Mike: arrange the dots so that no lines cross."


Mike (who is not stupid, but who does interpret "vertices" to mean vertical things and "edges" to mean "things at the periphery".)
posted by Mike D at 7:01 AM on July 13, 2005

um - i have these two vertices RIGHT on top of each other - COMPLETELY appearing as one... that's ok, right? i can move on now? no? but... you really can't even tell they coexist...

shoot. alright.
posted by PrincessRue at 7:14 AM on July 13, 2005

What would be nice would be able to move portions of the graph without losing their structure, after a while the portion of the graph you're working on gets crowded, and you can't go on.
posted by delmoi at 11:37 AM on July 13, 2005

My version of flash was unable to cope with the script about half-way through level 18, and crashed my browser. Which is probably a good thing, because my brain was starting to melt.
posted by monju_bosatsu at 3:27 PM on July 13, 2005

when my computer started to get boggy, I turned down the flash quality and sallied forth
posted by boo_radley at 3:48 PM on July 13, 2005

posted by Toecutter at 8:47 PM on July 13, 2005

Inspired by MonkeySaltedNuts, I tried for the long square lines and nested vertices on the diagonal. How did I end up with something that looks like New York State? A girlfriend once remarked that our life drawing figures were twisted reflections of our unconscious demons. So are these twisted reflections of my unconscious road atlas?
posted by pointilist at 10:02 PM on July 13, 2005

Very cool. I have no idea why I waited so long to click the link.
posted by OmieWise at 8:22 AM on July 14, 2005

Level 8 in 9:21, and here I was feeling proud until I saw the screen grab from MonkeySaltedNuts.


Someone send me a reminder that this flash thing exists after I finish my thesis.
posted by caution live frogs at 9:03 AM on July 14, 2005

Odd. 9 took nearly 20 minutes and 10 I finished in under 9 minutes.

Somebody unplug my computer now, please.
posted by caution live frogs at 9:27 AM on July 14, 2005

« Older Ankle bone's connected to the doorknob.   |   T-22 hours, and counting Newer »

This thread has been archived and is closed to new comments