[PHA/LLA] - Game Over - The Grid is Secured.

Capfalcon

Damn it. Why must Advanced Data Structures be next quarter!

Phyphor

Oops, actually I had a bug that stopped the search too soon. Uh now I have to determine which paths are unique

Farangu

kill all smart people

Capfalcon

Actually, I think I might have this! Gimmie a sec.

Phyphor

Um, okay. Barring any more bugs there are 234 paths

http://codepad.org/tdh8psQn

Infidel

I am interested in cycles only.

Phyphor

FunkyWaltDogg wrote: »

Phyphor wrote: »

Wildcat wrote: »

Phyphor is obviously the smart one. We must kill him first.

Nope, I just wrote 300 lines of C

Real men do it by hand!

Nice work!

In a phalla about hacking???

Thanks! You actually did yours by hand?

Infidel

Phyphor just sent me a multithreaded C program that builds and searches my graph.

Ghostly Clockwork

I have to ask, reading the rules and mechanics, how in the world are you going to keep all of this straight? I'd have to do something like set up a huge gameboard on a table with little pictures for each player or something insane like that.

Infidel

Dragon6860 wrote: »

I have to ask, reading the rules and mechanics, how in the world are you going to keep all of this straight? I'd have to do something like set up a huge gameboard on a table with little pictures for each player or something insane like that.

Let's just say I am a professional programmer.

Phyphor

So picky

8 cycles

0 -> 9 -> 11 -> 10 -> 42 -> 40 -> 43 -> 33 -> 44 -> 28 -> 27 -> 24 -> 45 -> 20 -> 46 -> 16 -> 15 -> 17 -> 6 -> 5 -> 21 -> 18 -> 19 -> 22 -> 23 -> 25 -> 26 -> 4 -> 3 -> 30 -> 29 -> 31 -> 32 -> 34 -> 38 -> 39 -> 37 -> 36 -> 35 -> 2 -> 1 -> 12 -> 8 -> 7 -> 14 -> 13 -> 41 -> end

0 -> 9 -> 11 -> 10 -> 42 -> 40 -> 43 -> 33 -> 44 -> 28 -> 27 -> 25 -> 26 -> 4 -> 3 -> 30 -> 29 -> 31 -> 32 -> 34 -> 38 -> 39 -> 37 -> 36 -> 35 -> 2 -> 1 -> 12 -> 8 -> 7 -> 14 -> 15 -> 17 -> 6 -> 5 -> 21 -> 18 -> 19 -> 22 -> 23 -> 24 -> 45 -> 20 -> 46 -> 16 -> 13 -> 41 -> end

0 -> 41 -> 13 -> 14 -> 7 -> 6 -> 17 -> 15 -> 16 -> 46 -> 20 -> 45 -> 24 -> 23 -> 22 -> 19 -> 18 -> 21 -> 5 -> 1 -> 2 -> 35 -> 36 -> 37 -> 39 -> 38 -> 34 -> 32 -> 31 -> 29 -> 30 -> 3 -> 4 -> 26 -> 25 -> 27 -> 28 -> 44 -> 33 -> 43 -> 40 -> 42 -> 10 -> 11 -> 9 -> 12 -> 8 -> end

0 -> 8 -> 12 -> 9 -> 11 -> 10 -> 42 -> 40 -> 43 -> 33 -> 44 -> 28 -> 27 -> 25 -> 26 -> 4 -> 3 -> 30 -> 29 -> 31 -> 32 -> 34 -> 38 -> 39 -> 37 -> 36 -> 35 -> 2 -> 1 -> 5 -> 21 -> 18 -> 19 -> 22 -> 23 -> 24 -> 45 -> 20 -> 46 -> 16 -> 15 -> 17 -> 6 -> 7 -> 14 -> 13 -> 41 -> end

0 -> 8 -> 7 -> 14 -> 15 -> 17 -> 6 -> 5 -> 21 -> 18 -> 19 -> 22 -> 23 -> 25 -> 26 -> 4 -> 3 -> 30 -> 29 -> 31 -> 32 -> 34 -> 38 -> 39 -> 37 -> 36 -> 35 -> 2 -> 1 -> 12 -> 9 -> 11 -> 10 -> 42 -> 40 -> 43 -> 33 -> 44 -> 28 -> 27 -> 24 -> 45 -> 20 -> 46 -> 16 -> 13 -> 41 -> end

0 -> 41 -> 13 -> 14 -> 7 -> 8 -> 12 -> 1 -> 2 -> 35 -> 36 -> 37 -> 39 -> 38 -> 34 -> 32 -> 31 -> 29 -> 30 -> 3 -> 4 -> 26 -> 25 -> 23 -> 22 -> 19 -> 18 -> 21 -> 5 -> 6 -> 17 -> 15 -> 16 -> 46 -> 20 -> 45 -> 24 -> 27 -> 28 -> 44 -> 33 -> 43 -> 40 -> 42 -> 10 -> 11 -> 9 -> end

0 -> 41 -> 13 -> 16 -> 46 -> 20 -> 45 -> 24 -> 23 -> 22 -> 19 -> 18 -> 21 -> 5 -> 6 -> 17 -> 15 -> 14 -> 7 -> 8 -> 12 -> 1 -> 2 -> 35 -> 36 -> 37 -> 39 -> 38 -> 34 -> 32 -> 31 -> 29 -> 30 -> 3 -> 4 -> 26 -> 25 -> 27 -> 28 -> 44 -> 33 -> 43 -> 40 -> 42 -> 10 -> 11 -> 9 -> end

0 -> 41 -> 13 -> 16 -> 46 -> 20 -> 45 -> 24 -> 27 -> 28 -> 44 -> 33 -> 43 -> 40 -> 42 -> 10 -> 11 -> 9 -> 12 -> 1 -> 2 -> 35 -> 36 -> 37 -> 39 -> 38 -> 34 -> 32 -> 31 -> 29 -> 30 -> 3 -> 4 -> 26 -> 25 -> 23 -> 22 -> 19 -> 18 -> 21 -> 5 -> 6 -> 17 -> 15 -> 14 -> 7 -> 8 -> end

Infidel

Phyphor wrote: »

So picky

8 cycles

0 -> 9 -> 11 -> 10 -> 42 -> 40 -> 43 -> 33 -> 44 -> 28 -> 27 -> 24 -> 45 -> 20 -> 46 -> 16 -> 15 -> 17 -> 6 -> 5 -> 21 -> 18 -> 19 -> 22 -> 23 -> 25 -> 26 -> 4 -> 3 -> 30 -> 29 -> 31 -> 32 -> 34 -> 38 -> 39 -> 37 -> 36 -> 35 -> 2 -> 1 -> 12 -> 8 -> 7 -> 14 -> 13 -> 41 -> end

0 -> 9 -> 11 -> 10 -> 42 -> 40 -> 43 -> 33 -> 44 -> 28 -> 27 -> 25 -> 26 -> 4 -> 3 -> 30 -> 29 -> 31 -> 32 -> 34 -> 38 -> 39 -> 37 -> 36 -> 35 -> 2 -> 1 -> 12 -> 8 -> 7 -> 14 -> 15 -> 17 -> 6 -> 5 -> 21 -> 18 -> 19 -> 22 -> 23 -> 24 -> 45 -> 20 -> 46 -> 16 -> 13 -> 41 -> end

0 -> 41 -> 13 -> 14 -> 7 -> 6 -> 17 -> 15 -> 16 -> 46 -> 20 -> 45 -> 24 -> 23 -> 22 -> 19 -> 18 -> 21 -> 5 -> 1 -> 2 -> 35 -> 36 -> 37 -> 39 -> 38 -> 34 -> 32 -> 31 -> 29 -> 30 -> 3 -> 4 -> 26 -> 25 -> 27 -> 28 -> 44 -> 33 -> 43 -> 40 -> 42 -> 10 -> 11 -> 9 -> 12 -> 8 -> end

0 -> 8 -> 12 -> 9 -> 11 -> 10 -> 42 -> 40 -> 43 -> 33 -> 44 -> 28 -> 27 -> 25 -> 26 -> 4 -> 3 -> 30 -> 29 -> 31 -> 32 -> 34 -> 38 -> 39 -> 37 -> 36 -> 35 -> 2 -> 1 -> 5 -> 21 -> 18 -> 19 -> 22 -> 23 -> 24 -> 45 -> 20 -> 46 -> 16 -> 15 -> 17 -> 6 -> 7 -> 14 -> 13 -> 41 -> end

0 -> 8 -> 7 -> 14 -> 15 -> 17 -> 6 -> 5 -> 21 -> 18 -> 19 -> 22 -> 23 -> 25 -> 26 -> 4 -> 3 -> 30 -> 29 -> 31 -> 32 -> 34 -> 38 -> 39 -> 37 -> 36 -> 35 -> 2 -> 1 -> 12 -> 9 -> 11 -> 10 -> 42 -> 40 -> 43 -> 33 -> 44 -> 28 -> 27 -> 24 -> 45 -> 20 -> 46 -> 16 -> 13 -> 41 -> end

0 -> 41 -> 13 -> 14 -> 7 -> 8 -> 12 -> 1 -> 2 -> 35 -> 36 -> 37 -> 39 -> 38 -> 34 -> 32 -> 31 -> 29 -> 30 -> 3 -> 4 -> 26 -> 25 -> 23 -> 22 -> 19 -> 18 -> 21 -> 5 -> 6 -> 17 -> 15 -> 16 -> 46 -> 20 -> 45 -> 24 -> 27 -> 28 -> 44 -> 33 -> 43 -> 40 -> 42 -> 10 -> 11 -> 9 -> end

0 -> 41 -> 13 -> 16 -> 46 -> 20 -> 45 -> 24 -> 23 -> 22 -> 19 -> 18 -> 21 -> 5 -> 6 -> 17 -> 15 -> 14 -> 7 -> 8 -> 12 -> 1 -> 2 -> 35 -> 36 -> 37 -> 39 -> 38 -> 34 -> 32 -> 31 -> 29 -> 30 -> 3 -> 4 -> 26 -> 25 -> 27 -> 28 -> 44 -> 33 -> 43 -> 40 -> 42 -> 10 -> 11 -> 9 -> end

0 -> 41 -> 13 -> 16 -> 46 -> 20 -> 45 -> 24 -> 27 -> 28 -> 44 -> 33 -> 43 -> 40 -> 42 -> 10 -> 11 -> 9 -> 12 -> 1 -> 2 -> 35 -> 36 -> 37 -> 39 -> 38 -> 34 -> 32 -> 31 -> 29 -> 30 -> 3 -> 4 -> 26 -> 25 -> 23 -> 22 -> 19 -> 18 -> 21 -> 5 -> 6 -> 17 -> 15 -> 14 -> 7 -> 8 -> end

Pffft, it's just that paths are BORING.

I mean, there are dozens for each cycle just by going "okay, I break the cycle HERE, yay path! okay, noowwwwww HERE, yay path!" Not to mention the paths that don't meet end to end.

The "grid tour" circuit seems more appropriate anyhow!

MaxFrost

Phyphor wrote: »

FunkyWaltDogg wrote: »

Phyphor wrote: »

Wildcat wrote: »

Phyphor is obviously the smart one. We must kill him first.

Nope, I just wrote 300 lines of C

Real men do it by hand!

Nice work!

In a phalla about hacking???

Thanks! You actually did yours by hand?

I did mine by hand O_o

towndrunk34

Looks like Phyphors off to a good start.
Damn this public computer being unable to show the grid pictures :x

Phyphor

Okay, you people are also nuts. Oh NP-complete problem. Whatever, I'll just trace out the solution

MaxFrost

Phyphor wrote: »

So picky

8 cycles

0 -> 9 -> 11 -> 10 -> 42 -> 40 -> 43 -> 33 -> 44 -> 28 -> 27 -> 24 -> 45 -> 20 -> 46 -> 16 -> 15 -> 17 -> 6 -> 5 -> 21 -> 18 -> 19 -> 22 -> 23 -> 25 -> 26 -> 4 -> 3 -> 30 -> 29 -> 31 -> 32 -> 34 -> 38 -> 39 -> 37 -> 36 -> 35 -> 2 -> 1 -> 12 -> 8 -> 7 -> 14 -> 13 -> 41 -> end

0 -> 9 -> 11 -> 10 -> 42 -> 40 -> 43 -> 33 -> 44 -> 28 -> 27 -> 25 -> 26 -> 4 -> 3 -> 30 -> 29 -> 31 -> 32 -> 34 -> 38 -> 39 -> 37 -> 36 -> 35 -> 2 -> 1 -> 12 -> 8 -> 7 -> 14 -> 15 -> 17 -> 6 -> 5 -> 21 -> 18 -> 19 -> 22 -> 23 -> 24 -> 45 -> 20 -> 46 -> 16 -> 13 -> 41 -> end

0 -> 41 -> 13 -> 14 -> 7 -> 6 -> 17 -> 15 -> 16 -> 46 -> 20 -> 45 -> 24 -> 23 -> 22 -> 19 -> 18 -> 21 -> 5 -> 1 -> 2 -> 35 -> 36 -> 37 -> 39 -> 38 -> 34 -> 32 -> 31 -> 29 -> 30 -> 3 -> 4 -> 26 -> 25 -> 27 -> 28 -> 44 -> 33 -> 43 -> 40 -> 42 -> 10 -> 11 -> 9 -> 12 -> 8 -> end

0 -> 8 -> 12 -> 9 -> 11 -> 10 -> 42 -> 40 -> 43 -> 33 -> 44 -> 28 -> 27 -> 25 -> 26 -> 4 -> 3 -> 30 -> 29 -> 31 -> 32 -> 34 -> 38 -> 39 -> 37 -> 36 -> 35 -> 2 -> 1 -> 5 -> 21 -> 18 -> 19 -> 22 -> 23 -> 24 -> 45 -> 20 -> 46 -> 16 -> 15 -> 17 -> 6 -> 7 -> 14 -> 13 -> 41 -> end

0 -> 8 -> 7 -> 14 -> 15 -> 17 -> 6 -> 5 -> 21 -> 18 -> 19 -> 22 -> 23 -> 25 -> 26 -> 4 -> 3 -> 30 -> 29 -> 31 -> 32 -> 34 -> 38 -> 39 -> 37 -> 36 -> 35 -> 2 -> 1 -> 12 -> 9 -> 11 -> 10 -> 42 -> 40 -> 43 -> 33 -> 44 -> 28 -> 27 -> 24 -> 45 -> 20 -> 46 -> 16 -> 13 -> 41 -> end

0 -> 41 -> 13 -> 14 -> 7 -> 8 -> 12 -> 1 -> 2 -> 35 -> 36 -> 37 -> 39 -> 38 -> 34 -> 32 -> 31 -> 29 -> 30 -> 3 -> 4 -> 26 -> 25 -> 23 -> 22 -> 19 -> 18 -> 21 -> 5 -> 6 -> 17 -> 15 -> 16 -> 46 -> 20 -> 45 -> 24 -> 27 -> 28 -> 44 -> 33 -> 43 -> 40 -> 42 -> 10 -> 11 -> 9 -> end

0 -> 41 -> 13 -> 16 -> 46 -> 20 -> 45 -> 24 -> 23 -> 22 -> 19 -> 18 -> 21 -> 5 -> 6 -> 17 -> 15 -> 14 -> 7 -> 8 -> 12 -> 1 -> 2 -> 35 -> 36 -> 37 -> 39 -> 38 -> 34 -> 32 -> 31 -> 29 -> 30 -> 3 -> 4 -> 26 -> 25 -> 27 -> 28 -> 44 -> 33 -> 43 -> 40 -> 42 -> 10 -> 11 -> 9 -> end

0 -> 41 -> 13 -> 16 -> 46 -> 20 -> 45 -> 24 -> 27 -> 28 -> 44 -> 33 -> 43 -> 40 -> 42 -> 10 -> 11 -> 9 -> 12 -> 1 -> 2 -> 35 -> 36 -> 37 -> 39 -> 38 -> 34 -> 32 -> 31 -> 29 -> 30 -> 3 -> 4 -> 26 -> 25 -> 23 -> 22 -> 19 -> 18 -> 21 -> 5 -> 6 -> 17 -> 15 -> 14 -> 7 -> 8 -> end

No, just 4. You're going in the opposite direction on the other 4.

Phyphor

Bah, I knew I was forgetting something. I needed to check if the reverse was identical too

Capfalcon

Nope, I give. Short of breaking this up into a whole lot of little paths/graphs, I'm pretty certain it's beyond my abilities. All the accepted theorems are for simple graphs.

MaxFrost

I know I could set up the chart in Java or C++, but creating the actual pathfinding code is slightly more intimidating.

I'm thinking an object with a peek() (lets you see if the node has been visted yet, but don't actually travel there, goto() (travel to object, set visted to true), and connectedto() functions at minimum.

Capfalcon

MaxFrost wrote: »

I know I could set up the chart in Java or C++, but creating the actual pathfinding code is slightly more intimidating.

I'm thinking an object with a peek() (lets you see if the node has been visted yet, but don't actually travel there, goto() (travel to object, set visted to true), and connectedto() functions at minimum.

Yeah, I think I could whip some C++ up that would get the job done. May not be the quickest, but it would probably work. But, SOMEONE already beat us novices to payday.

But graphs and sets were always fun, so I figured I'd give it a shot.

EDIT:

I think it would go something like:

Go along your merry little path, making sure to peek before you leap.
If you run into a spot where you have no options, and every node hasn't been visited, back up and "unvisit" this node.

I'm just having trouble thinking about how I'm make sure it was a cycle...

Alt_Raven

Phyphor is gonna have all the monies, get him!

Phyphor

I brute forced it with a recursive search (spawning out sub-paths to separate threads). It takes 12 CPU-seconds on my core 2 duo work machine

Ardor

If we're able to beat up players for their credits, Phyphor might not be in the best Cycle 1 position!

Day 1:
You help beat up Phyphor with 40 other players.
You gain 3 credits and a $1 off domino's pizza coupon.

Capfalcon

Phyphor wrote: »

I brute forced it with a recursive search (spawning out sub-paths to separate threads). It takes 12 CPU-seconds on my core 2 duo work machine

Well, if we're brute forcing it, I guess just define one of them as the start, and then check to see if you end up back there.

...Which is what you did, it looks like :P

Phyphor

Ardor wrote: »

If we're able to beat up players for their credits, Phyphor might not be in the best Cycle 1 position!

Day 1:
You help beat up Phyphor with 40 other players.
You gain 3 credits and a $1 off domino's pizza coupon.

So, what you're saying is I should spend it all right away?

MaxFrost

Recursion. It's awesome.

FunkyWaltDogg

I spent an hour and got well into the by-hand proof, but I don't know if I've got the energy to finish it.

immortal squish

I found a path Phyphor's script didn't catch!

(Please don't hurt me)

FunkyWaltDogg

immortal squish wrote: »

I found path Phyphor's script didn't catch!

(Please don't hurt me)

:^:

Phyphor

That is the best path

immortal squish

There's a special prize for whoever is starting off in Hub Node 6

daniant

There is no point in me posting today, because I majored in Spanish Literature in college.

Now let me compare Cantar de mio Cid and Chanson de Roland for you...

Secretly I'm jealous of you tech gods and also I want to learn programming, because it sounds like logic puzzles, and I like logic puzzles.

MaxFrost

daniant wrote: »

There is no point in me posting today, because I majored in Spanish Literature in college.

Now let me compare Cantar de mio Cid and Chanson de Roland for you...

Secretly I'm jealous of you tech gods and also I want to learn programming, because it sounds like logic puzzles, and I like logic puzzles.

Just go take a comp sci class. Programming at is core is about solving puzzles, and it's not to terribly hard to get started with.

Now thinking in ways to let you solve harder problems takes more work. And for this particular problem, there's like....a truckload of possible paths, so brute forcing it, while fast, still takes time.

(I could do the stat math, but blargh, too many nodes)

Phyphor

Well, the brute force approach for this graph visits 294058598 nodes

Dunadan019

I hate programmers.

CaptainPlanet82

> EXEC INDFAY_YPHORPHAY_ULLYBAY_AKETAY_UNCHMONEYLAY.EXE
*** Program Started ***
*** Starting Node Result Posted ***
*** Share spoils with immortal squish for knowing Phyphor's true agenda ***

Phyphor

Nobody on the Internets is allowed to hate programmers :P

CaptainPlanet82

IRL, I have this Alchemy app on my iPhone where you combine two elements to make new elements...

Computer + Sex = Developer... Yikes!
Internet + Pirate = Hacker... Arrrrrrgh!

Dunadan019

Phyphor wrote: »

Nobody on the Internets is allowed to hate programmers :P

I have a note from my doctor that says I'm allowed.

Dunadan019

I also hate doctors.