00:32:11 -!- ais523 has joined.
01:10:08 <esolangs> [[User:Squidmanescape]] https://esolangs.org/w/index.php?diff=121016&oldid=120978 * Squidmanescape * (-2) /* My Languages */
01:11:33 -!- Lord_of_Life has joined.
01:12:21 -!- tswett has joined.
01:14:42 <tswett> So I'm working on figuring out how to convert term rewriting systems to string rewriting systems.
01:16:19 <tswett> (I assume someone has already written a paper somewhere about how to do that, using either a technique similar to mine or a better one. It would be really embarrassing if this turned out to be something nobody's done before.)
01:18:49 <tswett> My current solution involves imagining the string to be a sequence of instructions for a machine with 3 stacks, where the items on the stacks are S-expressions.
01:19:13 <tswett> I just ran into a problem, and I thought of a solution so hilarious that I had to come here and share it :D
01:22:53 <tswett> The two "primitive" instructions are push and cons. The instruction push(s1, a) pushes the atom a onto stack 1; the instruction cons(s1) pops a value x from stack 1, then a value y, then pushes the cons cell (x . y).
01:23:56 <esolangs> [[Danicb]] https://esolangs.org/w/index.php?diff=121017&oldid=118516 * Squidmanescape * (+0) /* Cat Program */
01:24:26 <tswett> Okay, how could we implement move_one(s1, s2), which pops the top item from s1 and pushes it onto s2? The rule for atoms is obvious: push(s1, a) move_one(s1, s2) -> push(s2, a)
01:25:20 <ais523> I think string rewriters have the problem of moving data "past" other data, unless they have sufficiently powerful wildcarding systems
01:25:25 <ais523> this got studied for Thue a long time back
01:25:38 <tswett> The rule for a cons cell is less obvious. The "obvious solution" is wrong: if we do cons(s1) move_one(s1, s2) -> move_one(s1, s2) move_one(s1, s2) cons(s2), then the two top items will end up moving, but they'll end up in the wrong order.
01:26:33 <tswett> Here's the hilarious solution: cons(s1) move_one(s1, s2) -> move_one(s1, s3) move_one(s1, s2) move_one(s3, s2) cons(s2), where s3 is any stack that is neither s1 nor s2.
01:26:42 <tswett> In other words, THE FREAKING TOWERS OF HANOI ALGORITHM
01:27:42 <ais523> well, isn't it conceptually the same problem as the towers of Hanoi?
01:28:35 <tswett> ais523: Yeah, that is definitely the "Big Problem" with string rewriting systems. I've basically spent, like, 10 or 20 hours trying to figure out how to do a "swap." And I think I finally have the solution.
01:28:49 <ais523> alternatively you can think of it as the problem of reversing a stack in a stack machine whilst leaving the output on the same stack, which you have to do by reversing three times (because you can't reverse it without moving it, and moves reverse, so you need three moves to avoid the reverses cancelling each other out)
01:29:30 <ais523> I am also reminded of the shunting yard algorithm for parsing
01:29:42 <tswett> I wouldn't necessarily say that "it" is conceptually the same problem. You can certainly impose constraints on the problem which result in it being a Towers of Hanoi problem.
01:30:32 <ais523> well, imagine your cons cells form a list, and you want to move the list
01:30:45 <tswett> However, the Towers of Hanoi solution takes... I think exponential time in the depth of the S-expression you're transferring. Something like that.
01:31:24 <ais523> yes, Towers of Hanoi solution is exponential (and unique up to a few trivial changes)
01:32:30 <ais523> there's a very easily memorisable algorithm for performing it: imagine the three stacks as having a cyclic order (perhaps they're arranged in a cycle and the order goes clockwise): alternate between a) moving the smallest disk clockwise and b) moving a disk other than the smallest
01:32:33 <tswett> I think it's possible to do much better. The obvious bound on how quickly you can exchange two S-expressions in a string rewriting system is quadratic in the length of the strings.
01:32:39 <ais523> (in the latter case there will only ever be one such legal move)
01:32:54 <tswett> And I think that quadratic time is, in fact, achievable.
01:33:20 <ais523> yes, this sort of thing comes up in cellular automata a lot
01:33:26 -!- ais523 has quit (Quit: sorry about my connection).
01:33:40 -!- ais523 has joined.
01:33:51 <ais523> my TC proof for Addition Automaton b=10 basically treats it like a sort of string rewriter
01:34:17 <ais523> and yet it is implementing a queue-based language via continually moving the end of the queue to the start, so it has to be able to move data through other data
01:34:26 <tswett> The move_one(s1, s2) instruction basically only has to identify one S-expression on its left-hand side and relabel it from s1 to s2. The hard part is identifying one S-expression.
01:34:33 <ais523> which it does by using separate symbols for left-moving and right-moving data
01:35:34 <ais523> I think the basic technique for bracket matching in a string rewriter is to change an innermost pair of brackets to a different sort of bracket, then ignore that bracket for the purpose of matching the next-outer pair, etc.
01:36:33 <ais523> e.g. in ((a)((b)(c))), the matching goes ((a)((b)(c))) ([a]((b)(c))) ([a]([b](c))) ([a]([b][c])) ([a][[b][c]]) ([a][[b][c]]
01:36:41 <ais523> * e.g. in ((a)((b)(c))), the matching goes ((a)((b)(c))) ([a]((b)(c))) ([a]([b](c))) ([a]([b][c])) ([a][[b][c]]) [[a][[b][c]]
01:36:44 <ais523> * e.g. in ((a)((b)(c))), the matching goes ((a)((b)(c))) ([a]((b)(c))) ([a]([b](c))) ([a]([b][c])) ([a][[b][c]]) [[a][[b][c]]
01:36:47 <ais523> * e.g. in ((a)((b)(c))), the matching goes ((a)((b)(c))) ([a]((b)(c))) ([a]([b](c))) ([a]([b][c])) ([a][[b][c]]) [[a][[b][c]]]
01:36:53 <ais523> my ] key is right next to my newline key
01:37:06 <tswett> Here's an almost-solution: push(s1, a) move_one(s1, s2) -> push(s2, a); cons(s1) move_one(s1, s2) -> move_two(s1, s2) cons(s2); push(s1, a) move_two(s1, s2) -> move_one(s1, s2) push(s2, a); cons(s1) move_two(s1, s2) -> move_three(s1, s2) cons(s2); ...
01:37:14 <ais523> and all you are doing is looking for a ( followed by any number of non-() followed by a )
01:38:14 <tswett> Hmmm, that technique might work for what I'm doing.
01:38:54 <esolangs> [[Danicb]] https://esolangs.org/w/index.php?diff=121018&oldid=121017 * Squidmanescape * (+383)
01:38:59 <ais523> (this is also the reliable way to parse with regex, if you get to run the regex in a loop)
01:39:10 <ais523> (and don't have bracket-matching operators in your regex language)
02:00:43 <tswett> Wait, duh. I don't have to figure out a way to move multiple items from one stack to another while somehow having them land in the same order. I can just do this:
02:01:05 -!- wpa has quit (Quit: Connection closed for inactivity).
02:01:21 <tswett> cons(s1) move_one(s1, s2) -> move_one(s1, s2) move_one(s1, s2) reverse_cons(s2)
02:05:19 <tswett> In other words, if the cons cell (A . B) is at the top of the first stack, and I deconstruct it to form B below A, I don't have to somehow figure out how to move the top two items from the first stack to the second as a unit.
02:06:10 <tswett> I can just move them one at a time, so that the top of the second stack is A below B, and then invoke a reverse cons instruction to reconstruct the correct cons cell.
02:14:38 <ais523> that is going to be quadratic when operating on a list
02:14:53 <ais523> because the cons cells you reverse get larger as the list gets larger
02:16:08 <tswett> True, but I can get around that by using a second trick.
02:16:20 <esolangs> [[Talk:New]] https://esolangs.org/w/index.php?diff=121019&oldid=121015 * Squidmanescape * (+2304)
02:17:21 <tswett> Instead of using the reverse_cons technique to move stuff straight from s1 to s2, I'll use it to move stuff first from s1 to a special stack, then from the special stack to s2. On the special stack, reverse_cons doesn't get normalized.
02:18:38 <tswett> So I'm never *physically* reversing anything; I'm merely rewriting "cons" to "reverse_cons" and later rewriting "reverse_cons" to "cons."
02:27:01 -!- Thelie has quit (Ping timeout: 245 seconds).
02:33:41 -!- Thelie has joined.
02:33:59 -!- Thelie has quit (Client Quit).
02:34:57 <tswett> No, I think I was wrong. I'm doing a reduction by hand and the order of stuff does, in fact, end up getting reversed.
02:58:00 <esolangs> [[List of quines]] https://esolangs.org/w/index.php?diff=121020&oldid=118650 * Tastyfish * (+87) Added Comun
04:07:04 <tswett> Well, writing this Thue program was definitely a good use of my time. https://pastebin.com/Em1cLbAU
04:08:32 <tswett> Conceptually, that program pushes the letters A, L, E, R, T, E, D to stack 1, and then uses "cons," "move," and "break" instructions to shuffle them around a bit so that the stack instead says A, L, T, E, R, E, D.
04:42:06 -!- FreeFull has quit.
04:58:06 -!- ais523 has quit (Quit: quit).
06:49:00 <int-e> . o O ( Whoever prepared today's AoC input was a terrible Blockout player. )
07:21:39 <esolangs> [[Comun]] M https://esolangs.org/w/index.php?diff=121021&oldid=120927 * PythonshellDebugwindow * (+25) Category
07:32:44 -!- tromp has joined.
08:07:21 -!- tswett has quit (Quit: Client closed).
08:12:31 <int-e> What else... we haven't had a tree or CFG parsing task yet this year.
08:33:52 <shachaf> i,i good old control flow graph parsing
08:40:58 <int-e> There are only so many TLAs.
08:56:59 <b_jonas> yeah. my job is full of TLAs and other deliberately obscure jargon terms. including a TLA that means two different things.
09:41:37 <shachaf> Do all y'all know about self-stabilizing systems?
09:41:46 <shachaf> As in Dijkstra's https://dl.acm.org/doi/pdf/10.1145/361179.361202
09:57:31 -!- Sgeo has quit (Read error: Connection reset by peer).
10:02:34 -!- __monty__ has joined.
10:36:19 -!- Koen_ has joined.
11:37:31 <esolangs> [[WeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeBasic++]] M https://esolangs.org/w/index.php?diff=121022&oldid=120998 * None1 * (+1275) /* Deadfish */
12:04:39 -!- tromp has quit (Read error: Connection reset by peer).
13:21:44 <esolangs> [[GPTLang]] M https://esolangs.org/w/index.php?diff=121023&oldid=89374 * PythonshellDebugwindow * (+68) /* Concepts */ Categories
13:41:11 <esolangs> [[TypeInt]] N https://esolangs.org/w/index.php?oldid=121024 * GUAqwq * (+493) Created page with "{{infobox proglang |name=TypeInt (Tn) |author=[[User:GUAqwq]] |year=[[:Category:2023|2023]] |class=[[:Category:maybe_tc(change after proving)]] |files=<code>.ts_</code> }} '''TypeInt''' is a esolang which is created by [[User:GUAqwq]]. The program runs on an unbounded in
14:00:20 <esolangs> [[TypeInt]] https://esolangs.org/w/index.php?diff=121025&oldid=121024 * GUAqwq * (+535)
14:04:19 <esolangs> [[TypeInt]] https://esolangs.org/w/index.php?diff=121026&oldid=121025 * GUAqwq * (+107) /* Decrease */
14:04:30 <esolangs> [[TypeInt]] https://esolangs.org/w/index.php?diff=121027&oldid=121026 * GUAqwq * (+1) /* Overview */
14:14:33 <esolangs> [[TypeInt]] https://esolangs.org/w/index.php?diff=121028&oldid=121027 * GUAqwq * (+660) /* Decrease */
15:12:24 -!- tromp has joined.
15:35:59 -!- Sgeo has joined.
16:04:28 -!- wib_jonas has joined.
16:04:49 <wib_jonas> I'm told this is about this year's AoC and especially so I'll throw the link in here: https://blogs.perl.org/users/e_choroba/2023/12/step-counter-advent-of-code-202321.html
16:07:53 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
16:24:42 -!- tromp has joined.
16:31:15 -!- wib_jonas has quit (Quit: Client closed).
16:51:18 <fizzie> Yeah, that was yesterday.
17:34:37 <esolangs> [[Special:Log/newusers]] create * Szajzan * New user account
18:40:07 -!- chiselfuse has quit (Ping timeout: 240 seconds).
18:41:19 -!- chiselfuse has joined.
18:52:54 -!- Koen_ has quit (Quit: Leaving...).
20:01:04 -!- chiselfu1e has joined.
20:01:19 -!- chiselfuse has quit (Ping timeout: 240 seconds).
20:25:23 <int-e> I'm still puzzling over day 20... there can be an unbounded number of signals in flight, is that enough to make it TC?
20:28:03 <int-e> (that would most likely make part 2 undecidable for general inputs)
20:32:37 -!- __monty__ has quit (Quit: leaving).
20:44:32 <fizzie> Just finished day 22 part 2 (last working day of the year was busy) with a pretty "brute-force" solution, and it runs in 23 milliseconds. Now I don't know if I should do something smarter or not. There's already a 26-millisecond day (17), so it's not even a new low.
20:44:44 <fizzie> Already had an arguably smarter part 1 (ohvyq gur tencu bs juvpu oevpxf fhccbeg rnpu bgure naq pbhag ubj znal oevpxf ner gur bayl fhccbeg bs nabgure), and it feels like part 2 pbhyq or qbar va gur fnzr tencu, but the alternative (whfg er-qebc nyy gur oevpxf rkprcg bar, sbe rnpu bar, naq pbhag ubj znal zbirq) was just so easy.
20:46:00 <fizzie> Maybe I'll just keep it as it is on the rationale that shorter code is also worth something.
20:46:51 <b_jonas> there are two new tasks per day. I say 23 milliseconds is quick enough, unless you have at least a hundred thousands of other daily puzzle websites similar to AoC that you are solving.
20:48:55 <b_jonas> I guess at that point you'd just buy more servers
20:51:36 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
20:52:18 <fizzie> Does English have a corresponding idiom to the Finnish one that literally translated goes something like "to cross where the fence is lowest"? Meaning, to choose an option that may not necessarily lead to the very best result, but is the one that takes the least amount of effort for an acceptable outcome.
20:52:35 <fizzie> I guess there's a little bit of "go with the flow" in it, but it's maybe not quite the same.
20:54:00 <int-e> I'd say "path of least resistance"
20:54:41 <int-e> Though it's not much of an idiom, it's too literal. But it is a stock phrase.
20:57:21 <b_jonas> fizzie: hmm, maybe "searching under the streetlight" as in the drunk man does that when he lost his keys not because that's where the keys are but because he can't see anywhere else
20:57:43 <b_jonas> fungot, is Gimp's mascot called Wilber or Wilbur? and what kind of animal is it supposed to represent?
20:58:17 <b_jonas> huh, but fizzie fixed fungot! fungot, where are you?
20:59:30 -!- fungot has joined.
20:59:31 <int-e> b_jonas: http://gimpchat.com/viewtopic.php?f=4&t=10265
21:00:58 <fizzie> It had done that thing where the TCP connection dies and the other side never notices because there's no keepalive or any timed writes from fungot so it just stays like that forever.
21:01:03 <fizzie> fungot: You just got here!
21:01:04 <fungot> fizzie: that's probably a bit fnord here. ( sub1 ( x 1))
21:01:44 <fizzie> (I'd figure out a fix for that if it weren't for the fact that even if it did automatically reconnect, it doesn't have the capability of automatically joining channels, so it wouldn't come back anyway.)
21:13:04 -!- tromp has joined.
21:26:52 <b_jonas> fizzie: yeah, I know, he's written in an esolang so it's hard to modify
21:50:43 <esolangs> [[TypeInt]] M https://esolangs.org/w/index.php?diff=121029&oldid=121028 * PythonshellDebugwindow * (+87) Infobox, categories
21:52:49 <esolangs> [[Typeform]] M https://esolangs.org/w/index.php?diff=121030&oldid=87275 * PythonshellDebugwindow * (+2) Categories
21:56:04 <esolangs> [[Language list]] M https://esolangs.org/w/index.php?diff=121031&oldid=120964 * PythonshellDebugwindow * (+14) /* T */ add
22:18:55 -!- chiselfu1e has quit (Ping timeout: 240 seconds).
22:19:25 -!- chiselfuse has joined.
22:43:54 <esolangs> [[Special:Log/newusers]] create * BuzzZ80 * New user account
22:49:57 <esolangs> [[Esolang:Introduce yourself]] https://esolangs.org/w/index.php?diff=121032&oldid=120865 * BuzzZ80 * (+259) /* Introductions */
23:18:51 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
23:22:06 -!- chiselfu1e has joined.
23:22:31 -!- chiselfuse has quit (Ping timeout: 240 seconds).
23:30:27 -!- ais523 has joined.
23:45:22 -!- chiselfu1e has quit (Remote host closed the connection).
23:45:40 -!- chiselfuse has joined.