| --- Log opened Sun Dec 28 00:00:04 2014 |
| --- Day changed Sun Dec 28 2014 |
| 00:00 | | Alek [omegaboot@Nightstar-c8t.a00.36.73.IP] has quit [Ping timeout: 121 seconds] |
| 00:07 | | Thalass [thalass@Nightstar-9ai58o.bigpond.net.au] has quit [Ping timeout: 121 seconds] |
| 00:11 | < simon_> | hmmmm |
| 00:13 | < simon_> | I've got this dice game: roll a 6-sided die, if it's a 1, end the game. if it's the first die roll or the roll is either 1 higher or 1 lower than the most recently noted number, the roll is noted. otherwise the number is skipped. this process is repeated until the game ends. |
| 00:13 | < simon_> | i.e. if I roll 3465241, I note down 3454 |
| 00:14 | < simon_> | s/i.e./e.g./ |
| 00:14 | < simon_> | this is a language of number sequences that go one up or down |
| 00:14 | < simon_> | is it regular? |
| 00:14 | < simon_> | when writing the regex for this, something tells me it isn't. |
| 00:15 | | ^Xires is now known as Xires |
| 00:15 | < simon_> | but when I try to write a DFA that accepts only valid notations, something tells me it is. |
| 00:15 | <@celticminstrel> | Hmm. |
| 00:16 | <@celticminstrel> | I think it sounds like it's regular. |
| 00:17 | < simon_> | since I can write a somewhat simple DFA where all states are accepting and each vertex is either 2, 3, 4, 5 or 6, and each edge goes to the vertices that are 1 from itself, I would agree. |
| 00:17 | < simon_> | but then why is writing a regex for this language so hard? |
| 00:18 | < simon_> | [2-6]|23|3[24]|4[35]|5[46]|65|... but this approach only gives me notations of a certain length. |
| 00:18 | < simon_> | hmm... |
| 00:19 | < simon_> | one thing that is wrong with my DFA: it does not care what particular string I'm matching. |
| 00:21 | < simon_> | but I'm not sure if that's enough to make it not regular. |
| 00:22 | <@celticminstrel> | If your DFA has all states accepting, then it'll also accept the empty string, right? |
| 00:23 | | * celticminstrel just drew up a 7-state DFA that looks like it fits. |
| 00:23 | < simon_> | yes |
| 00:23 | < simon_> | the empty string is valid. |
| 00:24 | < simon_> | since if I roll a 1, the game stops and I haven't noted down any numbers. |
| 00:24 | | * celticminstrel nods. |
| 00:24 | < simon_> | I only have 6 states in my DFA. |
| 00:24 | <@celticminstrel> | My start state has edges branching out to all the others. |
| 00:25 | < simon_> | and there are only 5 others |
| 00:25 | <@celticminstrel> | Hm? |
| 00:25 | < simon_> | since rolling 1 will end the game and not produce anything. |
| 00:25 | <@celticminstrel> | Ahh, right. |
| 00:25 | < simon_> | if this is the only difference between ours, then that's fine. |
| 00:25 | < simon_> | I just needed a mechanism to stop. |
| 00:26 | <@celticminstrel> | So, I should have no edges leading out of my 1-state. |
| 00:26 | < simon_> | nope. no point in having a 1-state since it's basically "EOF" |
| 00:26 | <@celticminstrel> | Right, but if I do have one, it's the sole accepting state. |
| 00:26 | | * celticminstrel erases stuff. |
| 00:26 | < simon_> | I suppose it's regular then! but I wonder why there isn't a trivial regex for it. |
| 00:27 | < simon_> | ahhh, yes. |
| 00:27 | < simon_> | I guess that since "1"s are not part of the noted down numbers, there should not be an edge with a 1 on it. I should make that explicit somehow. |
| 00:27 | | * celticminstrel nods. |
| 00:35 | <@celticminstrel> | All your states are interlinked. I think that might be why there isn't a trivial regex. |
| 00:35 | | * celticminstrel is trying to figure this out though. |
| 00:38 | | Alek [omegaboot@Nightstar-c8t.a00.36.73.IP] has joined #code |
| 00:38 | | mode/#code [+o Alek] by ChanServ |
| 00:38 | <@celticminstrel> | Ah, wait. This is not a DFA. |
| 00:46 | <@celticminstrel> | Not that that makes a significant difference. |
| 00:54 | | Checkmate [Z@Nightstar-484uip.cust.comxnet.dk] has quit [Ping timeout: 121 seconds] |
| 01:25 | < simon_> | celticminstrel, why is this not a DFA? |
| 02:10 | | VirusJTG [VirusJTG@Nightstar-6i5vf7.sta.comporium.net] has quit [Connection closed] |
| 02:33 | <@celticminstrel> | simon_: To be a DFA, each state needs an exiting edge for every possible input character. |
| 02:33 | <@celticminstrel> | I think> |
| 02:33 | <@celticminstrel> | ^? |
| 02:34 | | * celticminstrel suddenlt wonders if that was something even stricter than a DFA. |
| 02:34 | <@celticminstrel> | ^suddenly |
| 02:35 | <&McMartin> | Well, generally each unstated input is assumed to go to a FAIL state that loops all input back to itself. |
| 02:35 | <&McMartin> | The difference between DFA and NFA is that NFAs are allowed to have multiple edges with the *same* input out of one node, and also edges that require no input whatsoever to traverse. |
| 02:36 | <&McMartin> | Every DFA is itself a restricted NFA, and any NFA can be mechanically converted into a DFA that accepts an identical set of strings. |
| 02:36 | <@celticminstrel> | Ah, okay. |
| 02:36 | <&McMartin> | However, this can, in the worst case, increase the number of nodes from N to 2^N. |
| 02:36 | <@celticminstrel> | So I'm just confused. |
| 02:36 | <&McMartin> | (The resulting DFA is one where each node corresponds to a set of the NFA's nodes that given the input so far you could theoretically be in) |
| 02:37 | <@celticminstrel> | Which is kinda bad, since it's barely been a year since I studied this stuff. >_> |
| 02:40 | <&McMartin> | I kept most of my old university textbooks, but CLR and Sipser are pretty much the only ones I've consulted after graduating because I needed information contained within them. |
| 02:45 | | Alek [omegaboot@Nightstar-c8t.a00.36.73.IP] has quit [Ping timeout: 121 seconds] |
| 02:52 | | Alek [omegaboot@Nightstar-c8t.a00.36.73.IP] has joined #code |
| 02:52 | | mode/#code [+o Alek] by ChanServ |
| 03:07 | | macdjord [macdjord@Nightstar-r9vt2h.mc.videotron.ca] has joined #code |
| 03:07 | | mode/#code [+o macdjord] by ChanServ |
| 03:13 | <@Alek> | http://imgur.com/gallery/gyU0me4 |
| 04:01 | < simon_> | McMartin, can you tell me if this language is regular? |
| 04:01 | <&McMartin> | Which? |
| 04:01 | < simon_> | McMartin, and if so, why is the regex so hard to construct? (I know that there are DFAs for which the regex is exponentially sized as well as the other way around.) |
| 04:01 | < simon_> | (...but I don't know if this is one such case.) |
| 04:02 | <@celticminstrel> | The language consisting of numerals 2-6 such that adjacent numerals have a difference of exactly 1. |
| 04:02 | <&McMartin> | I think I missed the beginning of this convo |
| 04:02 | <&McMartin> | Aha |
| 04:02 | < simon_> | McMartin, sequences of numbers where each number is 1 higher or 1 lower than the previous. |
| 04:03 | < simon_> | McMartin, e.g. "234345" |
| 04:03 | <&McMartin> | Right |
| 04:03 | <&McMartin> | The regex is hard to construct because the point where you loop back is not at all obvious |
| 04:04 | < simon_> | the closest I got was using perl's look-behinds, ^(((?<=2|^)3)|((?<=3|^)[24])|((?<=4|^)[35])|((?<=5|^)[46])|((?<=6)5))*$ |
| 04:04 | <@celticminstrel> | That's not a regular expression, though. I think. |
| 04:04 | < simon_> | but I'm using them illegally, since Perl will complain that these look-behinds are "variable-length" |
| 04:04 | < simon_> | celticminstrel, well, look-behinds are actually regular. |
| 04:04 | < simon_> | celticminstrel, but my usage of them is beyond what Perl supports... |
| 04:04 | < simon_> | celticminstrel, so I don't know about *that*. |
| 04:05 | <@celticminstrel> | Lookbehinds are regular? |
| 04:05 | <&McMartin> | I can generate a DFA that matches that language easily |
| 04:05 | < simon_> | celticminstrel, yeah. but it's sort of cheating because the equivalent regex without them is perhaps extremely large. |
| 04:05 | < simon_> | McMartin, so can I! |
| 04:05 | <&McMartin> | However, it is not made of the "building blocks" that regexes translate to |
| 04:05 | < simon_> | McMartin, no! |
| 04:05 | <&McMartin> | So that is why translating it to a regex is Hard (tm) |
| 04:05 | < simon_> | McMartin, yes! |
| 04:05 | < simon_> | :) |
| 04:06 | <@celticminstrel> | Huh. |
| 04:06 | < simon_> | maybe this is a case of a regular language for which the regex is explosively large. but I can't even imagine how it looks like for arbitrary-sized sequences. |
| 04:07 | <&McMartin> | Here is an algorithm for converting mechanically. |
| 04:07 | <@celticminstrel> | Isn't a lookbehind equivalent to saying "run this separate DFA in reverse and move to the next state if it matches"? |
| 04:07 | <&McMartin> | http://regex-automaton.com/conversion_of_dfa_to_regular_expressions.php |
| 04:08 | < simon_> | McMartin, cool. |
| 04:08 | <&McMartin> | I do not pretend to understand this algorithm |
| 04:08 | < simon_> | me neither. I didn't know it existed. |
| 04:17 | < simon_> | celticminstrel, look-arounds mainly help in doing negative matches of multiple characters. |
| 04:21 | < simon_> | celticminstrel, e.g. (?!<foo)bar becomes (^(|.|..|)|[^f][^o][^o])bar, but the non-look-around alternatives get exceedingly complex... |
| 04:21 | <@celticminstrel> | That doesn't quite look right. |
| 04:22 | < simon_> | oh? |
| 04:22 | <@celticminstrel> | (?!<foo)bar would match "goobar", but your translation wouldn't. |
| 04:22 | <@celticminstrel> | I think. |
| 04:23 | < simon_> | oh, yeah. |
| 04:23 | <@celticminstrel> | Ah, also, lookbehinds don't consume space, so you'd need a .{3} somewhere. |
| 04:23 | <@celticminstrel> | ^consume input |
| 04:24 | | Turaiel[Offline] is now known as Turaiel |
| 04:24 | < simon_> | well, space consumation is only a matter of what your parser returns, not what languages it matches. |
| 04:24 | <@celticminstrel> | Otherwise it matches only "bar". |
| 04:24 | <@celticminstrel> | Oh wait, that applies if it was a lookahead. |
| 04:25 | <@celticminstrel> | Not sure if it applies to a lookbehind. |
| 04:25 | < simon_> | i.e. look-arounds are much more useful in practical parsing, but they don't extend the set of possible languages. |
| 04:25 | <@celticminstrel> | The main thing that does is backreferences, as I recall. |
| 04:25 | < simon_> | neither lookahead nor lookbehind consume spaces |
| 04:25 | < simon_> | the main thing that does extend regexes to non-regular languages? yes. |
| 04:25 | <@celticminstrel> | Right, but that lookbehind could match "goobar" if you assume a non-anchored match. |
| 04:28 | < simon_> | (^(|.|..)|fo[^o]|f[^o]o|[^f]oo|f[^o][^o]|[^f]o[^o]|[^f][^o]o|[^f][^o][^o])bar |
| 04:29 | <@celticminstrel> | It's huge. |
| 04:29 | < simon_> | yes, and this is just from a small lookbehind |
| 04:29 | < simon_> | what I'm trying to say is that a lookaround will always have a non-lookaround equivalent that is most likely huge if not overwhelmingly huge to the point that it just exists to make a theoretical point. |
| 04:30 | < simon_> | so they're regular. unlike e.g. backrefs: (a*)b\1 is not a regular language. |
| 04:31 | | * celticminstrel nods. |
| 05:02 | | Turaiel is now known as Turaiel[Offline] |
| 05:09 | | Turaiel[Offline] is now known as Turaiel |
| 05:10 | | Thalass [thalass@Nightstar-9ai58o.bigpond.net.au] has joined #code |
| 05:10 | | mode/#code [+o Thalass] by ChanServ |
| 05:20 | | celticminstrel [celticminst@Nightstar-jeiu0g.dsl.bell.ca] has quit [[NS] Quit: And lo! The computer falls into a deep sleep, to awake again some other day!] |
| 05:52 | | Turaiel is now known as Turaiel[Offline] |
| 07:22 | | Kindamoody[zZz] is now known as Kindamoody |
| 07:39 | | Vornicus [vorn@ServerAdministrator.Nightstar.Net] has quit [[NS] Quit: Leaving] |
| 07:56 | | macdjord is now known as macdjord|slep |
| 08:41 | | Orthia [orthianz@Nightstar-a1ieog.callplus.net.nz] has quit [Ping timeout: 121 seconds] |
| 08:46 | | Orthia [orthianz@Nightstar-ohb366.callplus.net.nz] has joined #code |
| 08:46 | | mode/#code [+o Orthia] by ChanServ |
| 09:59 | | Checkmate [Z@Nightstar-484uip.cust.comxnet.dk] has joined #code |
| 09:59 | | mode/#code [+o Checkmate] by ChanServ |
| 10:13 | | Kindamoody is now known as Kindamoody|afk |
| 10:42 | | Orthia [orthianz@Nightstar-ohb366.callplus.net.nz] has quit [Ping timeout: 121 seconds] |
| 10:46 | | Orthia [orthianz@Nightstar-a1ieog.callplus.net.nz] has joined #code |
| 10:46 | | mode/#code [+o Orthia] by ChanServ |
| 11:54 | | Checkmate [Z@Nightstar-484uip.cust.comxnet.dk] has quit [Ping timeout: 121 seconds] |
| 12:20 | | Checkmate [Z@Nightstar-ev6.6um.94.83.IP] has joined #code |
| 12:20 | | mode/#code [+o Checkmate] by ChanServ |
| 12:22 | | VirusJTG [VirusJTG@Nightstar-6i5vf7.sta.comporium.net] has joined #code |
| 12:57 | | gnolam [lenin@Nightstar-afpphi.tbcn.telia.com] has joined #code |
| 12:57 | | mode/#code [+o gnolam] by ChanServ |
| 12:58 | <@gnolam> | Well this is scary: http://streaming.media.ccc.de/relive/6249/ (starts at ~16:00) |
| 12:59 | | Orthia [orthianz@Nightstar-a1ieog.callplus.net.nz] has quit [Ping timeout: 121 seconds] |
| 13:04 | | Orthia [orthianz@Nightstar-4j4.kvk.224.119.IP] has joined #code |
| 13:04 | | mode/#code [+o Orthia] by ChanServ |
| 13:45 | | Thalass is now known as Thalasleep |
| 14:19 | | celticminstrel [celticminst@Nightstar-jeiu0g.dsl.bell.ca] has joined #code |
| 14:19 | | mode/#code [+o celticminstrel] by ChanServ |
| 14:20 | | celticminstrel [celticminst@Nightstar-jeiu0g.dsl.bell.ca] has quit [[NS] Quit: KABOOM! It seems that I have exploded. Please wait while I reinstall the universe.] |
| 14:20 | | celticminstrel [celticminst@Nightstar-jeiu0g.dsl.bell.ca] has joined #code |
| 14:20 | | mode/#code [+o celticminstrel] by ChanServ |
| 14:22 | | gnolam [lenin@Nightstar-afpphi.tbcn.telia.com] has quit [[NS] Quit: Shutdown] |
| 14:35 | <@froztbyte> | gn[tab] |
| 14:35 | | * froztbyte wonders if that's the SS7 one |
| 14:35 | | * froztbyte looks |
| 14:35 | <@Tarinaky> | It is |
| 14:35 | <@froztbyte> | ah |
| 14:35 | <@froztbyte> | lulz |
| 14:36 | <@froztbyte> | it's all so much worse than anyone realizes :) |
| 14:36 | <@Tarinaky> | Well so far I'm up to attacks against their prepaid credit. |
| 14:36 | <@Tarinaky> | Which is pretty bad. |
| 14:37 | <@froztbyte> | I haven't even seen the talk yet |
| 14:37 | <@froztbyte> | just dealt with building various bits of telco infra a couple of years ago |
| 14:37 | <@Tarinaky> | Yeah. |
| 14:37 | <@froztbyte> | it's all fucked. |
| 14:37 | <@froztbyte> | utterly and completely, irreparably fucked |
| 14:37 | <@froztbyte> | beyond hope |
| 14:38 | <@froztbyte> | (many reasons, among them ITU shitherdery) |
| 14:38 | <@Tarinaky> | itu? |
| 14:38 | <@froztbyte> | http://www.itu.int/en/Pages/default.aspx |
| 14:38 | <@froztbyte> | IETF for phone networks |
| 14:39 | <@froztbyte> | except older and dumber |
| 14:39 | <@froztbyte> | (hilariously so) |
| 14:39 | | gnolam [lenin@Nightstar-afpphi.tbcn.telia.com] has joined #code |
| 14:39 | | mode/#code [+o gnolam] by ChanServ |
| 14:39 | | gnolam [lenin@Nightstar-afpphi.tbcn.telia.com] has quit [[NS] Quit: Quit] |
| 15:09 | | Vornicus [vorn@ServerAdministrator.Nightstar.Net] has joined #code |
| 15:09 | | mode/#code [+qo Vornicus Vornicus] by ChanServ |
| 15:57 | <&jerith> | froztbyte: Why do you say the ITU's dumb? |
| 15:57 | <@froztbyte> | Just based on a couple of interactions I've had and observed |
| 15:58 | <@froztbyte> | They're basically like 60% responsible for how terrible telco things are, too |
| 15:58 | <@froztbyte> | (takes a couple of outside clowns as well) |
| 18:28 | | Kindamoody|afk is now known as Kindamoody |
| 19:46 | | Thalasleep [thalass@Nightstar-9ai58o.bigpond.net.au] has quit [[NS] Quit: Leaving] |
| 21:32 | | iospace is now known as io\PACKERS |
| 21:41 | | * Alek wonders how hard it would be to make a game completely modular. graphics engine. terrain engine. AI engine. UI engine. setting engine. etc. |
| 21:43 | <@Alek> | so you could swap a few engines to turn your fantasy roguelike into a zeldalike. swap out the classical-Everquest-graphics on your MMO for Skyrim-quality graphics. swap out the fantasy setting for a scifi or urban setting. |
| 21:50 | < simon_> | I'm sure you can devise a modular pipeline. replacing stuff like graphics/UI doesn't sound overwhelmingly abstract. switching AI sounds easy as well. making a game switch from e.g. 1st person to roguelike or even mud-like presents some problems, I think. |
| 21:53 | <@ErikMesoy> | "Skyrim-quality graphics" is going to be blatantly lying though. |
| 21:54 | <@ErikMesoy> | It has barriers thinner than the PC. This is incompatible with most roguelikes. |
| 21:55 | <@ErikMesoy> | If you stuck to the roguelike aspect, you'd instead get very very finely painted 5x5x5ft blocks of terrain. :P |
| 21:58 | | Kindamoody is now known as Kindamoody[zZz] |
| 22:04 | <&McMartin> | Haven't you basically described Unity here |
| 22:09 | | grindhold [quassel@Nightstar-uufabm.zebra.fastwebserver.de] has quit [[NS] Quit: No Ping reply in 180 seconds.] |
| 22:10 | | grindhold [quassel@Nightstar-uufabm.zebra.fastwebserver.de] has joined #code |
| 23:21 | | Checkmate [Z@Nightstar-ev6.6um.94.83.IP] has quit [Ping timeout: 121 seconds] |
| 23:40 | <@Alek> | I don't know, have I? |
| 23:42 | <@Alek> | and yeah, engine between First Person and Top Down 2D is a big difference. which is why I mentioned Roguelike to Zeldalike as an example - jumping small gaps aside, and climbing stairs, that's a pretty close transition from top-down to quarter-view, and not much difference from there to isometric. |
| 23:43 | <&McMartin> | Yeah, Unity has been used for: Kerbal Space Program, Rochard, Sunless Sea, La-Mulana 2, Wasteland 2 |
| 23:44 | <&McMartin> | So that's two side-to-side 2D, top-down 2D, free-flowing 3D, isometric 3D |
| 23:44 | <@Alek> | in fact, stuff like Torchlight can almost be rendered in ascii graphics already, all it has is the ability to partially block ranged fire to higher levels. |
| 23:44 | <@Alek> | from what I can tell. |
| 23:44 | <&McMartin> | Oh yeah, it looks like Hexcells is also Unity-based |
| 23:45 | <@Alek> | I'll take a look at that then. :P |
| 23:45 | <~Vornicus> | One thing I've always wondered about was a diabloish where each character class had a different camera angle, depending on the style of play |
| 23:45 | <@ErikMesoy> | You could replace the *sprites* in Torchlight with ascii, I guess |
| 23:45 | <@Alek> | Vorn: ooh, GOOD one. |
| 23:45 | <@Alek> | Erik: the background too. |
| 23:45 | <@ErikMesoy> | The sub-character movement doesn't seem like something doable with what is normally called "ascii graphics" |
| 23:45 | <@ErikMesoy> | Alek: There are backgrounds not composed of player-sized units. |
| 23:45 | <@Alek> | you never actually get to cross your path on any one level. it's all a single level, with just tricks to make it look like parts are higher and lower. |
| 23:46 | <@ErikMesoy> | At some point you wind up doing this: http://mkweb.bcgsc.ca/asciiart/img/ascii-art-mona-lisa-fixed-string-full.png |
| 23:46 | <@ErikMesoy> | Which is very clever and all, but whyyyyyy. |
| 23:47 | <@Alek> | Vorn... now I'm reminded of those games where you can either be a grunt, in FPS, or a commander, doing top-down RTS, or transition between them. |
| 23:49 | | Omega [omegaboot@Nightstar-c8t.a00.36.73.IP] has joined #code |
| 23:49 | | mode/#code [+o Omega] by ChanServ |
| 23:51 | | Alek [omegaboot@Nightstar-c8t.a00.36.73.IP] has quit [Ping timeout: 121 seconds] |
| 23:52 | | Omega is now known as Alek |
| 23:52 | <@Alek> | gah |
| 23:52 | <@Alek> | nephew crawled down and powered off the UPS again. |
| 23:52 | <@Alek> | what'd I miss? |
| 23:53 | <@ErikMesoy> | Nothing |
| 23:59 | | Checkmate [Z@Nightstar-484uip.cust.comxnet.dk] has joined #code |
| 23:59 | | mode/#code [+o Checkmate] by ChanServ |
| --- Log closed Mon Dec 29 00:00:26 2014 |