July 09, 2005

Planarity. (flash) Move the circles so the lines don't cross.

(via del.icio.us) To read more about planar graphs, look here, here, and, if you're feeling scholarly, here. More generally, this is an excellent listing of math texts available for free online (in addition to the arXiv, of course).

posted by pmdboi 19 years ago
  • I finished level 4 before I stopped caring. I was pretty proud of myself.
  • I like this.
  • level six is a bitch!!! anyone crack it??
  • This is good. Got to lvl 6 but couldn't get it. I started thinking too much. Then I looked at the high scores. o_O
  • I got to level 7 and then saw checked the high score to see that people have scores in the hundred of millions and gave up. basically, just concentrate on a few dots at a time. get one section clean, then move on to another section. pretty fun.
  • great game
  • Where's the board game version?
  • drivingmenuts: Man, I wish. I think you'd run into problems with tangling, though... anyway, I'm thinking about implementing it myself for OS X or something like that. This Flash implementation gets kind of pokey when you get up around level 10. I have a feeling it's using an O(n²) algorithm for checking whether it's solved or not, when it really only needs to be O(n)... (Yes, I have no life.)
  • Awesome game.
  • I just finished level 10. This next one looks pretty difficult. At around level 7 it started slowing down my computer pretty bad. I don't know if it'll survive level 11. pmdboi, I think your absolutely right about it not being O(n). I thought it was my slow computer (pentium II), but since everyone is getting bogged down, I blame the maker. (still fun though)
  • Nice. Finished level 7, but couldn't face 8.
  • Yeah, my poor computer couldn't handle level 11 either. It's a pretty neat game though.
  • Nice. Much prefer your title, pmdboi. Ray, when someone asks you if you're a god, you say YES!
  • Nice. Much prefer your title, pmdboi. Ray, when someone asks you if you're a god, you say YES!
  • Fun But I don't want to do the math.
  • No, no, you see, when it's O(n²) it means that the quadr... Oh, who gives a flying one.
  • Oh, who gives a flying one. I do. My favorite paper on incremental planarity testing, which uses a neat union-find-like approach. It's a joy to implement even, in case anyone is thinking of some light weekend programming.
  • Does this mean tensor is billed like a geek god?
  • Nah, I'm billed like a duck. Quack quack!
  • Psst! Hush! for the infamous habits of ducks who won't hide their lusts under a blanket or bush may just put randy old goats and doe-eyed rabbits to the blush.
  • So, I beat level 17. Twice. (level 17 has 125 vertices, I believe. I counted 100 at level 12, 105 at level 13, and 110 at level 14. So I'm assuming it's adding 5 vertices each level from here on out) I have some advice on how to get farther (avoiding the slowdown): Adjust the quality to low. That does make some difference; I didn't start getting slowdown until level 10 on low quality (as opposed to level 7 on high quality). After getting one quarter to one half finished, recross a line or two in an area that's completely solved. I haven't quite figured out it's algorithm for checking lines, but it seems to use a flagged line, one that it knows is crossed. As long as that flagged line remains crossed, it doesn't go into slowdown. When you recross lines in a solved area, it usually ends up making this line the flagged line (but not always. If it doesn't become the flagged one immediately, it will become it after unflagging the current flagged one and maybe a couple more). This should be the last line you uncross. You'll get slowdown for this movement, but it should be your only slowdown. TIP: the algorithm connects vertices so that there's a "right" answer of sorts. In this "right answer, the higher levels will have about 20-30 vertices on the outer border. Any vertice that only has two connections belongs on the outer border. It is possible, though much more difficult to solve using a different set of vertices as an outer border, but if you do so, your outer border will only have 6-7 vertices MAX. This does have a huge effect. (I did manage to solve level 14 the "wrong" way, with a border of 6 vertics). TIP: After finding a starting vertice (one with two connections), move the rest out of the way, to one side of the board. this'll give you some working room. Pull connections over, rearranging when neccessary. Make sure every vertice with two connections you pull over is put on the outside border. I just finished level 17 again. Tomorrow I'll keep working from there, and see what I can get to before exploding my computer. (I'm shrinking this post a little, since it's so large)
  • ... vertice ... vertice ...
    vertex
  • *ahem* GEEEEEEEEEKS!