| --- Log opened Sun Mar 04 00:00:51 2007 |
| 00:10 | | Chalcedon [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has joined #code |
| 00:10 | | mode/#code [+o Chalcedon] by ChanServ |
| 00:14 | | Forj [~Forj@Nightstar-869.bitstream.orcon.net.nz] has joined #code |
| 00:14 | | Janus is now known as Jan[draw] |
| 00:32 | | Thaqui [~Thaqui@Nightstar-25354.jetstream.xtra.co.nz] has joined #code |
| 00:44 | | Chalcedon is now known as ChalcyCleaning |
| 02:34 | | gnolam [Lenin@Nightstar-13557.8.5.253.se.wasadata.net] has quit [Quit: Z?] |
| 03:01 | | MahalBEDD is now known as Mahal |
| 03:14 | | Forj [~Forj@Nightstar-869.bitstream.orcon.net.nz] has quit [Quit: Gone] |
| 03:17 | | Forj [~Forj@Nightstar-869.bitstream.orcon.net.nz] has joined #code |
| 03:23 | | Forj [~Forj@Nightstar-869.bitstream.orcon.net.nz] has quit [Connection reset by peer] |
| 03:25 | | Forj [~Forj@Nightstar-869.bitstream.orcon.net.nz] has joined #code |
| 04:01 | | McMartin[WonderCon] is now known as McMartin |
| 04:14 | | Thaqui [~Thaqui@Nightstar-25354.jetstream.xtra.co.nz] has quit [Quit: This computer has gone to sleep] |
| 04:17 | | CommanderFrog is now known as ToxicFrog |
| 04:22 | | Thaqui [~Thaqui@Nightstar-25354.jetstream.xtra.co.nz] has joined #code |
| 04:29 | | Chalcy [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has joined #code |
| 04:29 | | mode/#code [+o Chalcy] by ChanServ |
| 04:30 | | ChalcyCleaning [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has quit [Ping Timeout] |
| 04:30 | | Forj [~Forj@Nightstar-869.bitstream.orcon.net.nz] has quit [Ping Timeout] |
| 04:30 | | Forj [~Forj@Nightstar-869.bitstream.orcon.net.nz] has joined #code |
| 04:56 | | McMartin [~mcmartin@Nightstar-5796.dsl.pltn13.sbcglobal.net] has quit [Quit: Kernel upgrade] |
| 05:00 | | MyCatVerbs is now known as MyCatSleeps |
| 05:28 | | Forjeh [~Forj@Nightstar-869.bitstream.orcon.net.nz] has joined #code |
| 05:29 | < Jan[draw]> | Strange... |
| 05:29 | | Chalcy [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has quit [Ping Timeout] |
| 05:30 | | Forj [~Forj@Nightstar-869.bitstream.orcon.net.nz] has quit [Ping Timeout] |
| 05:30 | | Chalcedon [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has joined #code |
| 05:30 | | mode/#code [+o Chalcedon] by ChanServ |
| 05:31 | < Jan[draw]> | A drawing can look perfectly fine, then when it's fliped horizontally, it's like looking into East Burlen. |
| 05:35 | <@Raif> | Berlin? |
| 05:36 | | * Jan[draw] doesn't speak German. |
| 05:37 | < Jan[draw]> | Try speaking in American, it's the only language I understand. |
| 05:37 | < Doctor_Nick> | hurf durf blurf slurf |
| 05:38 | | * Jan[draw] gives Dr. Nick another beer. |
| 05:38 | | * Doctor_Nick spills it on himself and slumps on the credenza |
| 05:42 | | ReivClass [~Reiverta@Nightstar-23347.ubs-dsl.xnet.co.nz] has joined #Code |
| 05:43 | | ReivClass is now known as Reiver |
| 05:44 | | Reiver is now known as NSGuest-795 |
| 05:48 | | NSGuest-795 is now known as Reiver |
| 05:57 | | Jan[draw] [~Cerulean@Nightstar-10302.columbus.res.rr.com] has quit [Quit: "Self-esteem is overrated anyway. Most of the work in this country is done by people who hate themselves."] |
| 06:26 | | Mahal [~Mahal@Nightstar-4998.worldnet.co.nz] has quit [Quit: fuk off i got biskit] |
| 06:38 | | Vornicus-Latens is now known as Vornicus |
| 07:16 | | ErikMesoy|sleep is now known as ErikMesoy |
| 07:27 | | Thaqui [~Thaqui@Nightstar-25354.jetstream.xtra.co.nz] has quit [Quit: This computer has gone to sleep] |
| 07:32 | | Thaqui [~Thaqui@Nightstar-25354.jetstream.xtra.co.nz] has joined #code |
| 08:07 | | Chalcedon [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has quit [Quit: ] |
| 08:37 | | Forjeh [~Forj@Nightstar-869.bitstream.orcon.net.nz] has quit [Quit: Gone] |
| 08:38 | | GeekSoldier_ [Rob@Nightstar-2916.pools.arcor-ip.net] has joined #code |
| 08:39 | | GeekSoldier [Rob@Nightstar-3246.pools.arcor-ip.net] has quit [Ping Timeout] |
| 08:51 | | Mahal [~Mahal@Nightstar-4998.worldnet.co.nz] has joined #Code |
| 08:51 | | mode/#code [+o Mahal] by ChanServ |
| 09:26 | | GeekSoldier_ is now known as GeekSoldier |
| 09:44 | | You're now known as TheWatcher |
| 10:08 | <@jerith> | Afternoon all. |
| 10:15 | | Thaqui [~Thaqui@Nightstar-25354.jetstream.xtra.co.nz] has left #code [Leaving] |
| 10:23 | | Reiver [~Reiverta@Nightstar-23347.ubs-dsl.xnet.co.nz] has quit [Ping Timeout] |
| 10:31 | | Reivtop [~reiver@Nightstar-27222.ubs-dsl.xnet.co.nz] has joined #Code |
| 10:31 | < Reivtop> | Dear Murphy: |
| 10:32 | < Reivtop> | While I understand you and I have not seen eye to eye in the past, and that you have delighted in destroying my livelihoods in the process, I feel that destroying my main boxen's PSU was a bit much. |
| 10:32 | < Reivtop> | But did you have to kill my LCD screen too? |
| 11:11 | | Reivtop is now known as Reiver |
| 12:11 | | Reiver is now known as ReivZzz |
| 13:30 | | gnolam [Lenin@Nightstar-13557.8.5.253.se.wasadata.net] has joined #Code |
| 14:00 | | ErikMesoy is now known as ErikMesoy|chibicatboy |
| 14:51 | | ErikMesoy|chibicatboy is now known as ErikMesoy |
| 14:55 | | Mahal is now known as MahalBEDD |
| 15:09 | | * Serah PatPats ReivZzz. |
| 15:09 | < MyCatSleeps> | That was gracious. |
| 15:09 | | MyCatSleeps is now known as MyCatVerbs |
| 15:11 | | * Vornicus rewrites his longest-path finder to not prune locations you can get to in a longer time, because it turns out that that's bad. |
| 15:12 | <@jerith> | Generating infinite loops? |
| 15:12 | <@jerith> | Or something? |
| 15:12 | <@Vornicus> | No |
| 15:12 | <@Vornicus> | It is possible for a shorter path to a particular point to be better because it doesn't block entrance to certain segments of the graph. |
| 15:13 | <@jerith> | Umm... Are you only allowed to traverse each node once or something? |
| 15:13 | <@Vornicus> | Yep. |
| 15:15 | <@Vornicus> | Also, recursion and results caching are your tiny gods. |
| 15:15 | <@jerith> | Indeed. |
| 15:16 | <@jerith> | Very tiny, or more just sort of smallish? |
| 15:16 | <@Vornicus> | Just sort of smallish. |
| 15:16 | <@jerith> | :-) |
| 15:17 | <@Vornicus> | A depth first search with caching of failed lines has reduced what would be exponential time to almost-linear time. |
| 15:17 | <@Vornicus> | (for a given target node, I have to check all the paths that the node would be on for a duplicate of that node) |
| 15:17 | <@jerith> | :-D |
| 15:19 | | * MyCatVerbs blinks. |
| 15:19 | < MyCatVerbs> | I thought the optimal running times for longest-path finding algorithms were exponential. oO |
| 15:21 | <@Vornicus> | If you don't store anything, I imagine so. Right now I'm looking at something around quartic time; if I were willing to more aggressively cache, it would be more along the lines of cubic time. |
| 15:22 | < MyCatVerbs> | Vornicus: "optimal," is defined to mean, "no algorithm can ever have a worst-case better than this." >_> |
| 15:22 | <@Vornicus> | Heh |
| 15:23 | < ErikMesoy> | Of course, no matter how many times the programmers and mathematicians say that you have to use the worst case as your baseline, PHBs will still give orders to code a moderately good system that does something nasty when given the worst case, such as taking indefinite time. |
| 15:24 | < MyCatVerbs> | ErikMesoy: that calls for excruciating hacks. |
| 15:24 | <@Vornicus> | I'm looking at entirely batshit storage, though - nodes * edges storage for paths, and good caching would be nodes^2 plus another nodes^2 intermittent. |
| 15:24 | < MyCatVerbs> | ErikMesoy: such as (if it's possible to do so cheaply) detecting that you're looking at something resembling your algorithm's worst case and switching algorithm to cope with it. =) |
| 15:25 | < ErikMesoy> | Oh, that's smart. |
| 15:25 | <@Vornicus> | But if you do that, you end up with, uh, 2 * nodes * nodes * edges time. |
| 15:25 | < ErikMesoy> | :D |
| 15:26 | < MyCatVerbs> | Vornicus: you're trading off storage for time? |
| 15:26 | <@Vornicus> | MCV: very much so. |
| 15:27 | < MyCatVerbs> | Fun. ^^ |
| 15:29 | <@Vornicus> | But, yeah, my previous method was 1. crap, and 2. slower than this. |
| 15:30 | <@Vornicus> | By about an order of magnitude. |
| 15:30 | < MyCatVerbs> | Eh, just so long as you don't hit your swap file. |
| 15:30 | <@Vornicus> | I'm about at 50MB for an 1100-ish node graph, halfway through. |
| 15:31 | <@Vornicus> | This is in Python, though, so it's got overhead. |
| 15:31 | < Doctor_Nick> | N^N |
| 15:31 | < MyCatVerbs> | Vornicus: niiiice. |
| 15:32 | < Doctor_Nick> | im not even sure how to do an N^N function |
| 15:33 | < MyCatVerbs> | Doctor_Nick: some variations on bogosort exceed N^N. |
| 15:33 | <@Vornicus> | ...though it has occurred to me that I haven't figured out how to get an actual path from the final data... |
| 15:34 | <@Vornicus> | ...oh, duh, real simple. Adapt my valid-path-checking function to return a list or None, and if it returns a list, append current to it. |
| 15:36 | < MyCatVerbs> | This is the handy thing about languages like Python, especially when they have good C integration. |
| 15:37 | <@Vornicus> | ...this is some wacky data, though - it dropped from 1067 to 993 live nodes after 8 moves, and has stayed there ever since. I suspect it might have a loop of 993 or thereabouts in it. |
| 15:37 | < MyCatVerbs> | If you need to make the whole program really really fast, it's entirely feasible to rewrite the path finding algorithm in C and link it in - *after* having prototyped and tuned it for complexity while working in Python. |
| 15:40 | <@Vornicus> | Indeed. |
| 15:41 | <@Vornicus> | I will eventually adapt this for my Settlers project; right now, however, I am content to watch it grind away on 1100 nodes of evil graph goodness. |
| 15:42 | < Doctor_Nick> | im not even sure how to do an N^N function |
| 15:42 | < Doctor_Nick> | oops |
| 15:42 | <@Vornicus> | You said that. |
| 15:42 | < Doctor_Nick> | i said that already |
| 15:43 | <@Vornicus> | Well, visiting n-tuples of n possible objects would do it. |
| 15:52 | <@Vornicus> | (so counting from 0 to 9,999,999,999, given 10...) |
| 15:52 | < MyCatVerbs> | Vornicus: Settlers? |
| 15:53 | <@Vornicus> | I'm making a Settlers of Catan webgame. |
| 15:53 | <@Vornicus> | Because the ones that are out there suck. |
| 15:53 | < MyCatVerbs> | Aaaand I have no idea what that is. *googles!* |
| 15:54 | < GeekSoldier> | only one of the greatest board games of all time. |
| 15:54 | < GeekSoldier> | :) |
| 15:54 | < gnolam> | Vornicus: what do you need fancy path finding for in SoC? |
| 15:54 | <@Vornicus> | gnolam: to find the longest road. |
| 15:54 | < GeekSoldier> | longroad? |
| 15:55 | < ErikMesoy> | Hmm. If you have memory, it seems like it might be better to count the increasing length of roads as they go, checking whenever a road is played. |
| 15:55 | < gnolam> | Since the number of roads is so limited, you shouldn't need anything special... |
| 15:55 | < gnolam> | IMO. |
| 15:55 | < GeekSoldier> | but roads may branch, so you'd need to check that too. |
| 15:56 | <@Vornicus> | Branch, and loop. |
| 15:56 | | * GeekSoldier nods. |
| 15:56 | <@Vornicus> | My brother once won a game by creating a loop where once there was none. |
| 15:56 | <@Vornicus> | too bad, too, because had he not done so, I would have won by playing my third soldier. |
| 16:00 | <@Vornicus> | And with other considerations - Ships can move (and C&K's Diplomat card can remove or move roads), players can break your roads by playing settlements - it quickly becomes difficult to determine how these things affect road length directly. So much so that just performing an exhaustive search is simpler. |
| 16:03 | < gnolam> | But still, isn't it still just a DFS with a directed graph? |
| 16:03 | < gnolam> | -still, or something. |
| 16:03 | < gnolam> | Need. More. Caffeine. |
| 16:04 | < gnolam> | NEED. |
| 16:04 | <@Vornicus> | Yes. And that's what I'm doing. |
| 16:04 | <@Vornicus> | Well, except that I'm doing breadth-first, because it's cheaper to do all possible starting points at once. |
| 16:08 | <@Vornicus> | depth 650, 23000 cache items, 200,000 cache hits. |
| 16:26 | | MyCatVerbs is now known as MyCatHungers |
| 17:01 | | GeekSoldier is now known as Rosie |
| 17:10 | | You're now known as TheWatcher[afk] |
| 17:26 | | Rosie is now known as GeekSoldier |
| 17:35 | | Forj [~Forj@Nightstar-869.bitstream.orcon.net.nz] has joined #code |
| 17:54 | | Forj [~Forj@Nightstar-869.bitstream.orcon.net.nz] has quit [Quit: Gone] |
| 17:56 | | Chalcedon [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has joined #code |
| 17:56 | | mode/#code [+o Chalcedon] by ChanServ |
| 18:32 | | You're now known as TheWatcher |
| 18:38 | | MyCatHungers is now known as MyCatVerbs |
| 18:56 | | Forj [~Forj@Nightstar-869.bitstream.orcon.net.nz] has joined #code |
| 19:01 | | Forj [~Forj@Nightstar-869.bitstream.orcon.net.nz] has quit [Quit: Gone] |
| 19:14 | | Janus [~Cerulean@Nightstar-10302.columbus.res.rr.com] has joined #Code |
| 19:18 | | AnnoDomini is now known as Kiers |
| 19:22 | | Kiers is now known as KiersBrown |
| 19:30 | < GeekSoldier> | http://c2.com/cgi/wiki?LanguagesByKeyboard |
| 19:47 | | Thaqui [~Thaqui@Nightstar-25354.jetstream.xtra.co.nz] has joined #code |
| 19:54 | | Syloq [Syloq@NetAdmin.Nightstar.Net] has joined #code |
| 20:10 | | Doctor_Nick [~fdsaf@Nightstar-1992.9-67.se.res.rr.com] has quit [Quit: ] |
| 20:11 | | EvilDarkLord is now known as Thokk |
| 20:31 | | Syloq is now known as Syloqs-AFH |
| 20:49 | | Syloqs-AFH [Syloq@NetAdmin.Nightstar.Net] has quit [Ping Timeout] |
| 20:56 | | introc [~introc@Nightstar-24886.est.estpak.ee] has joined #Code |
| 20:57 | < introc> | offering safe and simple way to earn money! see the second half of the presentation: www.website.ws/whiteride/show |
| 20:57 | | introc [~introc@Nightstar-24886.est.estpak.ee] has left #Code [] |
| 20:57 | < GeekSoldier> | damn estonian pyramid schemes. |
| 21:16 | <@Vornicus> | On further analysis, the aggressive caching scheme I mentioned earlier doesn't really work - the last part of the algorithm is to actually generate a working path, and for that you need to traverse the entire graph - and for /that/ you'd better be caching the dead sections. |
| 21:25 | | GeekSoldier [Rob@Nightstar-2916.pools.arcor-ip.net] has left #code [] |
| 21:34 | | Doctor_Nick [~fdsaf@Nightstar-1992.9-67.se.res.rr.com] has joined #code |
| 21:35 | < Doctor_Nick> | would any of you guys happen to have a copy of the 16-bit version of Turbo Debugger? |
| 21:36 | | AnnoDomini [~farkoff@Nightstar-29071.neoplus.adsl.tpnet.pl] has joined #Code |
| 21:36 | | AnnoDomini is now known as Kiers |
| 21:37 | | KiersBrown [~farkoff@Nightstar-29017.neoplus.adsl.tpnet.pl] has quit [Ping Timeout] |
| 21:51 | | ErikMesoy is now known as ErikMesoy|sleep |
| 22:11 | | MyCatVerbs [~mycatownz@Nightstar-379.dsl.in-addr.zen.co.uk] has quit [Ping Timeout] |
| 22:12 | | MyCatVerbs [~mycatownz@Nightstar-379.dsl.in-addr.zen.co.uk] has joined #code |
| 22:28 | | Thaqui [~Thaqui@Nightstar-25354.jetstream.xtra.co.nz] has left #code [Leaving] |
| 22:30 | | Thokk is now known as EvilDarkLord |
| 22:41 | | Kiers is now known as AnnoDomini |
| 22:55 | | Janus [~Cerulean@Nightstar-10302.columbus.res.rr.com] has quit [Quit: Jouets de Dieu, jouets de jouets, les jouets de me, na?tre Clair enfant voire.] |
| 22:55 | | You're now known as TheWatcher[T-2] |
| 22:58 | | You're now known as TheWatcher[zZzZ] |
| 23:00 | | MahalBEDD is now known as Mahal |
| 23:09 | | AnnoDomini [~farkoff@Nightstar-29071.neoplus.adsl.tpnet.pl] has quit [Quit: Those who slay dragons become dragons themselves. Stare into the abyss long enough, and it will stare back at you.] |
| 23:23 | | ReivZzz is now known as Reiver |
| 23:25 | | Chalcedon is now known as ChalcyOut |
| 23:32 | | Chalcy [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has joined #code |
| 23:32 | | mode/#code [+o Chalcy] by ChanServ |
| 23:33 | | ChalcyOut [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has quit [Ping Timeout] |
| --- Log closed Mon Mar 05 00:00:51 2007 |