←2020-07-09 2020-07-10 2020-07-11→ ↑2020 ↑all
00:00:08 -!- Rick has changed nick to Errick.
00:02:25 -!- Errick has quit (Remote host closed the connection).
00:21:13 -!- Phantom_Hoover has quit (Ping timeout: 264 seconds).
00:23:41 <esowiki> [[Dotlang]] https://esolangs.org/w/index.php?diff=75717&oldid=68673 * Bangyen * (-23) /* Implementations */
00:24:17 <esowiki> [[Dotlang]] https://esolangs.org/w/index.php?diff=75718&oldid=75717 * Bangyen * (-2)
00:25:04 <esowiki> [[User:Bangyen]] https://esolangs.org/w/index.php?diff=75719&oldid=75694 * Bangyen * (+22) /* Implementations */
00:25:32 -!- bangyen has joined.
00:33:49 -!- clog has joined.
00:39:28 <esowiki> [[Dotlang]] M https://esolangs.org/w/index.php?diff=75720&oldid=75718 * PythonshellDebugwindow * (+4) /* Computational class */ Wouk
00:58:00 -!- bangyen has quit (Ping timeout: 245 seconds).
01:43:49 <zzo38> Now you can post follow up messages to <1594277001.bystand@zzo38computer.org> on un2.org.zzo38computer.magic.custom if you want to write comments/complaints about my custom set of Magic: the Gathering cards.
01:46:07 <shachaf> `? zzo38mtg
01:46:10 <HackEso> zzo38mtg? ¯\(°​_o)/¯
01:46:33 <shachaf> `? zzo38card
01:46:34 <HackEso> zzo38cards are at http://zzo38computer.org/textfile/miscellaneous/magic_card/cards.txt
01:46:37 <shachaf> `? zzo38mtg.php
01:46:39 <HackEso> http://zzo38computer.org/mtg/cardfile.php
01:47:37 <shachaf> zzo38: Instead of MD5 I recommend a slow key-derivation sort of function.
01:49:02 <int-e> . o O ( MD5 run through homeomorphic encryption )
01:49:28 <int-e> (No, this isn't supposed to make any actual sense.)
01:50:13 <int-e> This whole (fully) homeomorphic encryption business is a bit of a mystery to me. It's hard to conceive of applications.
01:50:30 <int-e> A bit like blockchain, which essentially has *one* application.
01:50:53 <int-e> (which is to make some electricity companies rich)
01:51:29 <shachaf> I thought the main application was to scam people?
01:51:56 <int-e> That's an additional layer on top.
01:52:57 <shachaf> As far as overall global transfer of wealth goes, I imagine there's more of that? Though I don't really know.
01:55:14 <int-e> probably, not sure it's all that significant
01:55:15 <zzo38> shachaf: OK, although those are old; see http://zzo38computer.org/mtg/zivstr/ for the newest one, which is a specific card set.
01:55:21 <int-e> (probably not)
01:56:05 <zzo38> The NNTP server at zzo38computer.org does not require you to register an account to post.
01:56:19 <shachaf> I mean, global transfer of wealth as a result of Blockchain Technology
01:56:32 <shachaf> Man, I really don't like the grammar that "blockchain" has taken on.
01:56:41 <shachaf> "We used blockchain to do X and Y"
01:57:43 <int-e> we blocked X by chaining it to Y
01:58:09 <shachaf> I think people are using "coronavirus" similarly now, and it also irritates me.
01:58:36 <int-e> we used coronavirus to do X and Y?
01:59:00 <int-e> or do you mean the lack of articles
01:59:05 -!- ipk has joined.
01:59:09 <shachaf> Something like the lack of articles, I guess.
01:59:53 <int-e> . o O ( Let's compensate: We used a shachaf to confuse #esoteric. )
02:03:07 <zzo38> There is also a mirror of this card set on Magic Multiverse, although that is mainly for testing the Magic Multiverse export template for TeXnicard, although nevertheless it is there in case it is preferred by someone.
02:09:05 <zzo38> shachaf: Also, the reason I used MD5 is because of the specification of HTTP.
02:09:30 <shachaf> Oh, you use HTTP digest authentication.
02:09:55 <shachaf> I guess I shouldn't be surprised.
02:12:16 -!- Phantom_Hoover has joined.
04:08:14 -!- tswett[m] has quit (*.net *.split).
04:08:14 -!- clog has quit (*.net *.split).
04:08:15 -!- diginet has quit (*.net *.split).
04:08:15 -!- grumble has quit (*.net *.split).
04:08:15 -!- laerling has quit (*.net *.split).
04:08:15 -!- lifthrasiir has quit (*.net *.split).
04:08:15 -!- int-e has quit (*.net *.split).
04:08:15 -!- trn has quit (*.net *.split).
04:08:15 -!- tromp has quit (*.net *.split).
04:08:16 -!- hakatashi3 has quit (*.net *.split).
04:08:16 -!- HackEso has quit (*.net *.split).
04:08:16 -!- Deewiant_ has quit (*.net *.split).
04:08:17 -!- xylochoron[m] has quit (*.net *.split).
04:08:18 -!- Phantom_Hoover has quit (*.net *.split).
04:08:18 -!- zzo38 has quit (*.net *.split).
04:08:18 -!- Sgeo has quit (*.net *.split).
04:08:18 -!- MDude has quit (*.net *.split).
04:08:18 -!- sprocklem has quit (*.net *.split).
04:08:19 -!- ocharles has quit (*.net *.split).
04:08:19 -!- lambdabot has quit (*.net *.split).
04:08:20 -!- j4cbo has quit (*.net *.split).
04:08:20 -!- lucky has quit (*.net *.split).
04:08:21 -!- fungot has quit (*.net *.split).
04:08:21 -!- fizzie has quit (*.net *.split).
04:08:21 -!- relrod has quit (*.net *.split).
04:08:21 -!- vertrex has quit (*.net *.split).
04:08:21 -!- atslash has quit (*.net *.split).
04:08:21 -!- spruit11 has quit (*.net *.split).
04:08:22 -!- craigo has quit (*.net *.split).
04:08:23 -!- erdic has quit (*.net *.split).
04:08:24 -!- Arcorann has quit (*.net *.split).
04:08:24 -!- mich181189 has quit (*.net *.split).
04:08:25 -!- shachaf has quit (*.net *.split).
04:08:25 -!- kmc has quit (*.net *.split).
04:08:25 -!- shig_ has quit (*.net *.split).
04:08:25 -!- haavard has quit (*.net *.split).
04:08:25 -!- imode has quit (*.net *.split).
04:08:25 -!- Cale has quit (*.net *.split).
04:08:26 -!- Hooloovo0 has quit (*.net *.split).
04:08:26 -!- Melvar has quit (*.net *.split).
04:08:26 -!- glowcoil has quit (*.net *.split).
04:08:26 -!- aaaaaa has quit (*.net *.split).
04:08:26 -!- FreeFull has quit (*.net *.split).
04:08:27 -!- j-bot has quit (*.net *.split).
04:08:27 -!- joast has quit (*.net *.split).
04:08:28 -!- jix has quit (*.net *.split).
04:08:28 -!- oren has quit (*.net *.split).
04:08:28 -!- mniip has quit (*.net *.split).
04:08:28 -!- shikhin has quit (*.net *.split).
04:08:28 -!- ornxka_ has quit (*.net *.split).
04:08:28 -!- Bowserinator has quit (*.net *.split).
04:08:29 -!- orbitaldecay has quit (*.net *.split).
04:08:30 -!- iovoid has quit (*.net *.split).
04:08:30 -!- myndzi has quit (*.net *.split).
04:08:30 -!- Lymia has quit (*.net *.split).
04:08:30 -!- Lykaina has quit (*.net *.split).
04:08:31 -!- ^[_ has quit (*.net *.split).
04:08:31 -!- paul2520 has quit (*.net *.split).
04:08:31 -!- myname has quit (*.net *.split).
04:08:31 -!- gitlogger has quit (*.net *.split).
04:08:31 -!- Soni has quit (*.net *.split).
04:08:32 -!- ipk has quit (*.net *.split).
04:08:32 -!- Lord_of_Life has quit (*.net *.split).
04:08:32 -!- catern has quit (*.net *.split).
04:08:32 -!- rodgort` has quit (*.net *.split).
04:08:32 -!- APic has quit (*.net *.split).
04:08:32 -!- aloril has quit (*.net *.split).
04:08:34 -!- sebbu has quit (*.net *.split).
04:08:34 -!- ski has quit (*.net *.split).
04:08:34 -!- FireFly has quit (*.net *.split).
04:08:34 -!- wmww has quit (*.net *.split).
04:08:35 -!- dog_star has quit (*.net *.split).
04:08:35 -!- pikhq has quit (*.net *.split).
04:08:35 -!- heroux has quit (*.net *.split).
04:08:35 -!- olsner has quit (*.net *.split).
04:08:35 -!- BWBellairs has quit (*.net *.split).
04:08:36 -!- dnm has quit (*.net *.split).
04:08:36 -!- sftp has quit (*.net *.split).
04:08:36 -!- stux has quit (*.net *.split).
04:08:37 -!- xelxebar has quit (*.net *.split).
04:13:21 -!- Lykaina has joined.
04:13:21 -!- Lymia has joined.
04:13:21 -!- myndzi has joined.
04:13:21 -!- iovoid has joined.
04:13:21 -!- spruit11 has joined.
04:13:21 -!- atslash has joined.
04:13:21 -!- erdic has joined.
04:13:21 -!- craigo has joined.
04:13:21 -!- haavard has joined.
04:13:21 -!- shig_ has joined.
04:13:21 -!- kmc has joined.
04:13:21 -!- shachaf has joined.
04:13:21 -!- mich181189 has joined.
04:13:21 -!- Arcorann has joined.
04:13:21 -!- HackEso has joined.
04:13:21 -!- aloril has joined.
04:13:21 -!- APic has joined.
04:13:21 -!- rodgort` has joined.
04:13:21 -!- catern has joined.
04:13:21 -!- Lord_of_Life has joined.
04:13:21 -!- ipk has joined.
04:13:21 -!- xylochoron[m] has joined.
04:13:21 -!- ^[_ has joined.
04:13:21 -!- dog_star has joined.
04:13:21 -!- dnm has joined.
04:13:21 -!- pikhq has joined.
04:13:21 -!- Soni has joined.
04:13:21 -!- gitlogger has joined.
04:13:21 -!- myname has joined.
04:13:21 -!- paul2520 has joined.
04:13:21 -!- FireFly has joined.
04:13:21 -!- ski has joined.
04:13:21 -!- sebbu has joined.
04:13:21 -!- heroux has joined.
04:13:21 -!- sftp has joined.
04:13:21 -!- stux has joined.
04:13:21 -!- olsner has joined.
04:13:21 -!- BWBellairs has joined.
04:13:21 -!- xelxebar has joined.
04:13:31 -!- adu has joined.
04:13:38 -!- jix has joined.
04:13:38 -!- oren has joined.
04:13:38 -!- mniip has joined.
04:13:38 -!- shikhin has joined.
04:13:38 -!- ornxka_ has joined.
04:13:38 -!- Bowserinator has joined.
04:13:38 -!- orbitaldecay has joined.
04:13:48 -!- tswett[m] has joined.
04:14:06 -!- tromp has joined.
04:14:06 -!- Deewiant_ has joined.
04:14:17 -!- j4cbo has joined.
04:14:17 -!- lucky has joined.
04:14:17 -!- fungot has joined.
04:14:17 -!- fizzie has joined.
04:14:17 -!- relrod has joined.
04:14:17 -!- vertrex has joined.
04:14:28 -!- Phantom_Hoover has joined.
04:14:28 -!- zzo38 has joined.
04:14:28 -!- Sgeo has joined.
04:14:28 -!- MDude has joined.
04:14:28 -!- sprocklem has joined.
04:14:28 -!- ocharles has joined.
04:14:28 -!- lambdabot has joined.
04:14:42 -!- hakatashi has joined.
04:14:42 -!- aaaaaa has joined.
04:14:42 -!- glowcoil has joined.
04:14:42 -!- FreeFull has joined.
04:14:42 -!- j-bot has joined.
04:14:42 -!- joast has joined.
04:14:59 -!- imode has joined.
04:14:59 -!- Cale has joined.
04:14:59 -!- Hooloovo0 has joined.
04:14:59 -!- Melvar has joined.
04:15:12 -!- clog has joined.
04:15:12 -!- diginet has joined.
04:15:12 -!- grumble has joined.
04:15:12 -!- laerling has joined.
04:15:12 -!- lifthrasiir has joined.
04:15:12 -!- int-e has joined.
04:15:12 -!- trn has joined.
04:15:16 -!- xylochoron[m] has quit (Ping timeout: 246 seconds).
04:15:19 -!- ^[_ has quit (Ping timeout: 240 seconds).
04:15:21 -!- tswett[m] has quit (Ping timeout: 246 seconds).
04:19:23 -!- ^[_ has joined.
04:23:45 -!- xylochoron[m] has joined.
04:28:01 -!- Sgeo has quit (Read error: Connection reset by peer).
04:37:39 -!- Sgeo has joined.
04:39:53 -!- ipk has quit (Quit: Leaving).
04:51:31 -!- tswett[m] has joined.
04:51:31 -!- wmww has joined.
04:55:53 -!- lucky has quit (Ping timeout: 272 seconds).
05:27:37 -!- craigo has quit (Ping timeout: 244 seconds).
05:49:43 -!- joel2 has joined.
06:41:18 -!- sprocklem has quit (Quit: ...).
06:44:18 -!- adu has quit (Quit: adu).
06:46:50 -!- rain1 has joined.
07:45:21 -!- Sgeo has quit (Read error: Connection reset by peer).
08:14:13 <int-e> where's oerjan when you need somebody to discuss the latest TWIST in GG...
08:16:18 <shachaf> I have also wondered about small variations of that sentence.
08:16:22 <esowiki> [[Back]] https://esolangs.org/w/index.php?diff=75721&oldid=61875 * Bangyen * (+104)
08:17:05 <esowiki> [[User:Bangyen]] https://esolangs.org/w/index.php?diff=75722&oldid=75719 * Bangyen * (+11) /* Implementations */
08:29:55 <rain1> yes where is oerjan
08:40:40 -!- imode has quit (Ping timeout: 246 seconds).
08:46:40 <int-e> shachaf: I guess GG is one of the more inane topics to ask this about :)
08:47:15 <int-e> (GG = Girl Genius)
08:48:08 <shachaf> int-e: I mean, it's no password of the month.
08:48:30 <shachaf> Now that's a critically important topic.
08:48:38 <int-e> Yeah, nobody cares about the potm.
08:48:39 <int-e> ;)
08:48:59 <int-e> Maybe 3 weeks from now.
08:49:06 <shachaf> i,i `learn The password of the day is [...]
08:49:11 <int-e> But for now, the topic is done, over and best left to rest.
08:49:40 <shachaf> So I jammed up my SAT solver with a couple of extra features and it made a big qualitative difference.
08:49:52 <shachaf> I mean, it can quickly solve instances that it wasn't able to solve previously.
08:50:42 <int-e> But how does it compare to minisat?
08:51:00 <int-e> (which is kind of the baseline solver)
08:51:24 <shachaf> And some of them -- like n-queens -- it solves a lot faster than MiniSAT! Somehow.
08:51:44 <shachaf> ...Was the line I just had in my text buffer, when I switched to the other window to verify that it was n-queens.
08:51:49 <int-e> that's interesting, unless it knows somthing about symmetries.
08:52:05 <shachaf> It doesn't. I think it's just getting lucky using silly simple heuristics.
08:52:23 <int-e> though hmm, those tend to be satisfiable, right?
08:52:33 <shachaf> I need to implement better restarts. I finally added restarts, but I don't even save level-0 assignments when I restart.
08:52:44 <int-e> so luck may be a factor :-/
08:52:59 <shachaf> Yes. I should probably have more UNSAT problems.
08:53:00 <rain1> have you tried to solve puzzles like slitherlink with your SAT solver?
08:53:31 <shachaf> Is sudoku a puzzle like slitherlink?
08:53:37 <int-e> Slitherlink is a bit awkward to encode...
08:53:39 <rain1> no, it's unlike slitherlink
08:53:42 <shachaf> I've solved sudoku and knight's tour.
08:53:50 <rain1> although it is created by the same author
08:53:53 <shachaf> Knights tour is kind of silly since there's a linear time algorithm for it.
08:54:00 <int-e> Though if you have knight's tour you can also do slitherlink.
08:54:18 <shachaf> Oh, Slitherlink is Loopy.
08:54:24 <int-e> Because it's also a tour.
08:54:43 <shachaf> I have some kind of quadratic encoding for knight's tour.
08:54:45 <rain1> yeah encoding that into SAT seems interesting, because you have global/topological constraints
08:54:55 <int-e> yeah, slitherlink = loopy
08:55:24 <int-e> IME these puzzles that involve tours or connectivity are better solved with incremental SAT-solving.
08:55:38 <shachaf> OK, this UNSAT problem -- pigeon-hole-10.cnf -- is interesting.
08:56:10 <shachaf> It's UNSAT, and I solve it quickly if I use static variable ordering, but not any of my really terrible dynamic variable orderings.
08:57:30 <int-e> (What I do is look for solutions without the connectivity constraint. Then, if there's a loop, I assert that I only want solutions that use one of the edges *adjacent* to the loop (for each loop) and continue. Or something closely resembling that.)
08:58:33 <shachaf> My static variable ordering is just to sort variables by the number of occurrences in all (initial) clauses.
08:58:52 <shachaf> And whenever I need a new variable I linearly scan through the list until I see one that isn't assigned.
08:58:55 <int-e> That's for hamiltonian (or close to hamiltonian) cycles that appear in Slitherlink. For connectivity, I do the same thing but for cuts through the underlying graph: For each cut in the candidate solution, one of the involved edges must be in the solution.
08:59:24 <shachaf> That's interesting.
08:59:27 <int-e> Does this make sense? Not sure anybody is reading this. If not I should probably stop :)
08:59:55 <shachaf> I guess you can easily just add clauses incrementally, for CDCL solvers.
08:59:59 <rain1> is there some kind of polynomial time witness to a sat problem being unsatisfiable?
09:00:05 <shachaf> In fact I do that anyway for model counting.
09:00:54 <shachaf> I"m surprised that this kind of thing works better than asserting connectivity upfront.
09:01:04 <shachaf> Is that just because it's really awkward to encode?
09:01:10 <int-e> shachaf: There's *some* difficulty connected to simplification (which some SAT solvers do and which may eliminate variables) but nothing that can't be dealt with by some additional bookkeeping.
09:01:22 <int-e> yes.
09:01:45 <int-e> For those puzzles it's a *huge* unwieldy constraint (compared to all the other, local constraints).
09:02:00 <int-e> Which takes time to generate, and slows down unit propagation and all that.
09:02:10 <shachaf> Are there other kinds of constraint satisfaction problems that let you express that kind of thing more easily?
09:02:29 <int-e> And at least for human solvable puzzles, the connectivity/single loop constraints tend to play a rather minor role.
09:03:33 <int-e> There's actually an SMT solver that incorporates such things, https://github.com/sambayless/monosat
09:03:45 <int-e> Which I've never got around to play with...
09:04:23 <int-e> I view the incremental SAT solving approach I outlined as a poor person's version of SMT solving :)
09:05:20 <int-e> (Rather than checking the theory constraints on the fly, one waits for a complete solution of the propositional skeleton, and analyzes that for theory conflicts. Those become new clauses, and then the SAT solver can proceed.)
09:05:57 <int-e> (And hopefully this finishes before the clauses exceed the available memory.)
09:05:58 <shachaf> I see, you're viewing the circuitude as a theory constraint.
09:06:05 <int-e> Yes.
09:06:25 <shachaf> I need to learn how SMT solvers work better.
09:08:57 <shachaf> If you liked minisat, you're sure to like microsat: https://github.com/marijnheule/microsat/blob/master/microsat.c
09:10:24 <int-e> that coding style...
09:10:40 <shachaf> It's great, isn't it?
09:10:44 <shachaf> One thing per line, with a comment.
09:11:23 <int-e> "thing"
09:12:08 <int-e> lines 33 and 34 alone...
09:13:10 <int-e> (Though tbf, MiniSAT isn't all that pretty either, for different reasons.)
09:14:06 <shachaf> My solver is ~1000 lines of C right now.
09:14:43 <int-e> shachaf: btw do you use github often enough to confirm my suspicion that they moved the link to the commit history recently?
09:15:14 <int-e> or maybe I should hunt down an older screenshot... that may be easier than asking people
09:15:24 <shachaf> They redesigned the whole page recently, right?
09:15:37 <shachaf> https://github.blog/changelog/2020-06-23-design-updates-to-repositories-and-github-ui/
09:17:30 <shachaf> I've also found myself flummxed on this specific task since then.
09:18:51 <int-e> Here's an old screenshot, with "$nnn commits" at the top https://d1jnx9ba8s6j9r.cloudfront.net/blog/wp-content/uploads/2017/11/Cloning-how-to-use-github-Edureka.png ... I'm pretty sure that was a link.
09:19:22 <int-e> I'm sure I'll get used to the change in a month or two.
09:19:28 <int-e> But for now it's pretty annoying.
09:19:37 <rain1> like that coding
09:19:41 <shachaf> It was.
09:19:46 <rain1> must be a fucking pest to work on without editor support
09:19:46 <shachaf> Another screenshot: https://tonsky.me/blog/github-redesign/10_as-is.png
09:20:11 <int-e> thanks
09:20:53 -!- wib_jonas has joined.
09:22:32 <int-e> The other thing I've been wondering is who that 'Add file' UI is supposed to be for.
09:22:46 <int-e> Because I'm pretty sure it's not for developers.
09:23:27 <shachaf> Wow.
09:23:30 <int-e> (Or maybe... they are unifying the github and gist UIs?)
09:23:38 <shachaf> I clicked the "Add File" button and it automatically forked the repository?!
09:24:10 <int-e> That makes some amount of sense.
09:24:18 <shachaf> Now it needs my password to delete it.
09:24:26 <int-e> But it also seems rather surprising.
09:24:46 <shachaf> I am not particularly a fan of the whole forking model in GitHub.
09:24:47 <int-e> Right, because deleting repos requires a password.
09:24:50 <int-e> FUN.
09:24:54 <wib_jonas> hi #esoteric
09:25:27 <rain1> hi!
09:25:31 <int-e> Hmm, but it matches the git model... to make a change, you get your own copy of the repo, modify that, and then make a pull request.
09:25:49 <shachaf> Did y'all see https://github.com/shachaf/mustardwatch ?
09:25:52 <int-e> (Or send the patches by email.)
09:26:02 <rain1> lol
09:26:06 <int-e> shachaf: You've talked about it at length.
09:26:09 <shachaf> Oh.
09:26:23 <shachaf> Sounds like the kind of thing I might do.
09:26:37 <shachaf> Well, the GitHub pull requests aren't really part of the whole git model in the first place.
09:26:43 <shachaf> They're a separate code review tool.
09:26:57 <shachaf> I guess there's some connection to regular git pull requests.
09:27:33 <wib_jonas> "<rain1> is there some kind of polynomial time witness to a sat problem being unsatisfiable?" => not in general, because that would mean NP = coNP which we can't prove (though a few people suspect that it's true)
09:27:41 <wib_jonas> I think it's false
09:28:13 <int-e> shachaf: I think this is what you get if you combine the review-by-email and pull-from-this-repo requests in one UI, and modify it to be web-friendly.
09:28:27 <int-e> Yes, it's not the same, but most of the spirit seems to be preserved. YMMV.
09:28:56 <shachaf> Doesn't NP=coNP lead to some sort of hierarchy collapse?
09:29:30 <int-e> I thought it's weaker than the infamous NP = P.
09:29:47 <int-e> Which I think means no.
09:29:55 <int-e> But I'm not sure :-/
09:30:42 <shachaf> Wikipedia says "If NP = co-NP then NP = PH."
09:30:51 <shachaf> I should know these things properly.
09:31:26 <wib_jonas> "<shachaf> They redesigned the whole page [github] recently, right?" => yes, they needed to do that to hide the change that they -- wait, Wikipedia? don't you look that up in the Complexity Zoo? -- show some other branch name instead of "master"
09:31:35 <int-e> Hmm.
09:31:45 <shachaf> I looked it up on the Google.
09:32:10 <wib_jonas> also, no way, last time I heard about this we certainly didn't know that
09:32:35 <int-e> I still get master branches.
09:33:22 <wib_jonas> int-e: ok, maybe not then
09:33:23 <shachaf> Now I'm thinking about it and I'm not even sure what sorts of things are in PSPACE and not in PH.
09:33:49 <shachaf> I guess a thing in PH requires you to specify the number of quantifiers upfront rather than being part of the input.
09:34:07 <shachaf> So I guess I actually do know.
09:34:12 <int-e> Well, PSPACE-complete stuff like QBF...
09:34:15 <shachaf> (I mean, unless PSPACE = PH.)
09:34:16 <wib_jonas> shachaf: the sokoban kind of problems, where you need to find solution that may be exponentially long
09:34:37 <shachaf> Right, but my question would have been, why is QBF not in PH? But then I figured it out.
09:34:40 <int-e> Or your favorite PSPACE-hard problem, #SAT.
09:34:53 <int-e> (Unless I'm mixing things up again. I may.)
09:35:25 <shachaf> #SAT is PSPACE-hard? Hm, what does that mean?
09:35:32 <shachaf> Er.
09:35:40 <int-e> Yeah, I can see the fun there... each QBF instance is in PH.
09:35:44 -!- TheLie has joined.
09:35:51 <shachaf> I thought you said PSPACE-complete again somehow, despite typing a different phrase.
09:36:11 <shachaf> I'm still not sure what it means, since #SAT isn't normally a decision problem, but maybe you just do the usual thing.
09:37:17 <wib_jonas> "<shachaf> Well, the GitHub pull requests aren't really part of the whole git model in the first place." => yes, the original git model is sending patch sets by email
09:38:08 <wib_jonas> github does the same but tries to remove the email part and do a web forum thread for pull requests instead of an email threads, because email is harder to centralize (at least if you're Microsoft not Google) and so harder to monetize
09:38:21 <wib_jonas> I think it's logical
09:38:29 <int-e> Hmm, the complexity wiki just has the weaker statement that PH is in P^{#P}
09:39:25 <shachaf> Last time I looked, GitHub didn't look like a good code review tool.
09:39:31 <shachaf> But people say it's better so maybe it's better?
09:39:41 <wib_jonas> shachaf: can you give a link to where wikipedia says that if NP = coNP then NP = PH?
09:39:57 <shachaf> https://en.wikipedia.org/wiki/Polynomial_hierarchy#Relations_between_classes_in_the_polynomial_hierarchy
09:40:46 <int-e> https://en.wikipedia.org/wiki/Toda%27s_theorem
09:40:59 <int-e> (is about #P)
09:42:13 <wib_jonas> hmm, it does say that there
09:42:31 <int-e> So yeah by the preceeding discussion this falls short of making it PSPACE-hard.
09:43:32 <shachaf> The nice thing about designing sudoku puzzles to be human-solvable is that id minisat doesn't find a solution within a few seconds, the puzzle probably won't be fun for a human.
09:43:33 <int-e> (Why? Maybe the reduction is exponential in the number of quantifier alternations or something like that.)
09:43:47 <shachaf> Or at least that's my heuristic. Maybe it's not entirely true.
09:44:20 <int-e> I imagine that's true.
09:44:37 <int-e> I imagine the converse doesn't work :P
09:44:40 <wib_jonas> I fail to find solving sokoban fun. It's a nice game in theory, but actually playing it just doesn't work well for me.
09:45:06 <int-e> Hmm. I used to play Sokoban *a lot*.
09:45:14 <shachaf> Do you find solving Stephen's Sausage Roll fun?
09:45:26 <int-e> shachaf: Only up to a point.
09:45:54 <shachaf> int-e: I found puzzles that were extremely restrictive with the SAT solver, so I thought they would be interesting for humans.
09:46:08 <shachaf> But it turns out to be too difficult, at least for me and a couple of other people.
09:46:13 <wib_jonas> ah yes, you are right
09:46:15 <wib_jonas> https://complexityzoo.uwaterloo.ca/Petting_Zoo#PH
09:46:16 <int-e> I gave up on it, around the point where puzzles started to rely on detaching the fork.
09:46:21 <wib_jonas> that confirms your statement
09:46:41 <wib_jonas> I don't know what Stephen's Sausage Roll is
09:47:29 <wib_jonas> anyway, I have an algorithm design question for you #esoteric
09:48:29 <int-e> SSR put some twists on a Sokoban-like game.
09:49:23 <int-e> My main complaint is actually that you don't get access to all the levels from the start, even though there's actually a reason for that...
09:50:20 <wib_jonas> I have N small boxes, where let's say N <= 40000. Each box has two states: empty or full. Initially all boxes are full. Then I want to perform an interactive sequence of three types of steps. (A) Query the state of a bunch of boxes. (B) Set a bunch of boxes from full to empty. (C) Given a number K, fill exactly K empty boxes such that the set of
09:50:20 <wib_jonas> boxes filled is chosen uniformly among all empty boxes and independently from previous random choices.
09:51:37 <wib_jonas> In practice, the boxes are in pages often accessed together, so I'll query all boxes in a few page together or fill a set of boxes that are some of the boxes within a few pages.
09:52:00 <wib_jonas> I know at least one way to do this, but I'd like the best practical way, in terms of memory efficiency and time efficiency.
09:53:10 <int-e> Meh I forgot how this works, wasn't there a way to turn the sausages...
09:53:46 <int-e> oh I know.
09:54:18 <wib_jonas> The best method I found so far is to store the empty boxes in a binary heap, with a dense index table from all boxes into the heap. For (A) we just look up which indexes are filled in the index table; for (B) we add boxes to the heap with random weights, (C) we remove the box with the highest weigh repeatedly K times.
09:55:28 <wib_jonas> You can alternately use a treap, sorted by box number, in which case you don't need a separate indexing table because you can traverse a section of the treap in order, but this doesn't seem better, it takes slightly more memory, and now you have child pointers among the nodes which a binary heap doesn't need.
09:55:43 <wib_jonas> They involve a bunch of random access in either case.
09:56:17 <wib_jonas> There's probably some better method by amortizing stuff, marking how many more boxes you have to fill in each page, but it doesn't seem trivial.
09:56:59 <wib_jonas> Does my question make sense?
09:58:49 <int-e> So (A) and (B) are just operations on a boolean array?
09:59:51 <int-e> (Which does not support (C) efficiently by itself, but I'm trying to understand the problem here.)
10:04:33 <shachaf> Does it not?
10:04:49 <int-e> you'll have to scan the whole thing
10:05:42 <shachaf> Oh, I was thinking of a slightly different problem.
10:06:16 <int-e> I'm referring to the thing starting with "I have N small boxes"
10:06:41 <int-e> Mainly I'm trying to clarify what (A) and (B) are.
10:07:41 <int-e> The "bunch of boxes" is confusing me.
10:07:43 <wib_jonas> int-e: all of them are operations on a boolean array, yes, but if you have only a boolean array, (C) will be slow. that's correct.
10:08:09 <wib_jonas> each box is a boolean
10:08:15 <wib_jonas> and they're numbered to be in an array
10:08:35 <wib_jonas> (if they aren't entirely dense that doesn't matter, we'll just never empty those boxes then)
10:08:39 <int-e> Yeah "they're numbered" is what I was fishing for.
10:09:14 <int-e> (Hah, it feels odd to type "fishing" without 'ph'.)
10:09:41 <shachaf> fiphing?
10:09:58 <int-e> the phunster at work
10:10:01 -!- Lord_of_Life has quit (Read error: Connection reset by peer).
10:10:58 -!- Lord_of_Life has joined.
10:11:15 <wib_jonas> I guess I could keep a counter for each page for the number of balls to be distributed
10:11:40 <wib_jonas> and to do (C), I iterate on all pages and generate the balls I add to the count in the correct distribution,
10:11:55 <wib_jonas> which I think you can somehow do with binomial magic... I'll have to look that up
10:12:28 <wib_jonas> I could even do that hierarchically on a high-arity tree with the boxes in the nodes
10:23:57 <shachaf> What is the context of this problem?
10:26:27 <wib_jonas> shachaf: the motivation is a hypothetical game where the balls are resources that the player can collect then spend, like coins or ammo, a box is a fixed place on the map where the player can collect the resource, but unlike in traditional games, you can't just collect infinitely many resources by just replaying the same one level (whichever is
10:26:27 <wib_jonas> easy and fast and has lots of boxes), but there's also not just a finite amount of resources you can collect, they respawn in levels when you spend them.
10:27:28 <wib_jonas> The pages are levels or rooms, or just regions of the map handled together for efficiency if there are no level/room boundaries.
10:35:38 <int-e> wib_jonas: not sure what you want to do with the page constraint https://paste.debian.net/1155884/ is a sketch of something that I might try
10:36:44 <wib_jonas> int-e: pages are not a constraint, they're just a hint that may make it possible to optimize the real-world implementation, especially on a machine where RAM doesn't have uniform access time.
10:37:16 <wib_jonas> It can be useful because the heap solutions that I mentioned use a lot of ugly random access of single records each across many cache lines.
10:38:04 <int-e> the thing I'm sketching doesn't have brilliant locality properties either
10:38:19 <int-e> but it's way simpler than a heap
10:39:29 -!- Lord_of_Life_ has joined.
10:40:26 <int-e> (it's related to the trick that you use to get constant time operations (including initialization to zero) using two arrays)
10:40:46 <rain1> <shachaf> Do you find solving Stephen's Sausage Roll fun?
10:41:05 <rain1> I like this game a lot, but it's hard. I haven't completed it
10:41:05 <shachaf> I like that trick, I was just thinking about that.
10:41:30 <shachaf> I mean, I was thinking about it after seeing your code.
10:42:58 -!- Lord_of_Life has quit (Ping timeout: 260 seconds).
10:43:04 -!- Lord_of_Life_ has changed nick to Lord_of_Life.
10:44:57 <int-e> rain1: how many sausages did you get?
10:45:22 <int-e> (174 here)
10:45:38 <rain1> 105
10:46:12 <int-e> I feel better ;)
10:46:50 <int-e> But yes, seriously, it's hard. It *starts out* with levels that would be hard in other games, and mostly it just gets harder.
10:47:01 <int-e> Or that's how I recall it, I've played this years ago.
10:48:45 <int-e> Apparently (looking at save files) May 3 2017 is when I started, May 13 2017 is when I solved my last level.
10:49:18 <rain1> yeah it starts out very very hard
10:49:22 <wib_jonas> I see, you have a right-growable array that stores the indexes of the empty boxes in an arbitrary order, and a full array that stores for each box the index into that full array. You keep the two in sync.
10:49:24 <rain1> and then it gets way harder
10:49:35 <rain1> i like the courage of a game to do that, baba is like that too
10:49:56 -!- tromp has quit (Ping timeout: 256 seconds).
10:50:12 <int-e> Hmm. Baba has some tutorial levels at least. Hmm.
10:50:25 <shachaf> int-e: I'm confused by your code, actually.
10:50:44 <int-e> I tried, but I may have gotten it wrong.
10:50:53 <wib_jonas> For (A) you just look in the second array, for (B) you push a value to the first array an mark its index in the second, for (C) you repeatedly pick a random element from the first array, remove it, keep it dense by moving an element from the there, adjust first array in both places.
10:51:07 <wib_jonas> That does work and is better than what I suggested. I should have thought of it, thank you.
10:51:19 <shachaf> int-e: Say you empty 3, and then empty 1, and then fill 3. What's the state you're supposed to be in?
10:51:34 <int-e> But the idea is that -1 in `filled` represents filled boxes and each empty box has a corresponding entry in the `avail` array; these two entries point to each other.
10:51:57 <shachaf> Yes, I understand that bit, with the dense and sparse arrays.
10:52:07 <wib_jonas> I'm also confused by the code, but to be fair int-e said "sketch"
10:52:08 <int-e> Oh. I'm missing an update to `filled` when I move avail[i] = avail[free-1];
10:52:15 <int-e> As I said, I may have gotten it wrong.
10:52:34 <shachaf> Oh, you want to be setting avail[filled[i]]
10:52:40 <int-e> The missing bit is setting filled[avail[i]] = i.
10:53:12 <shachaf> I think it's a bit more complicated than that?
10:53:36 <int-e> filled[avail[i] = avail[free-1]] = i;
10:54:03 <wib_jonas> The more local version needs to do the ugly binomial calculations, which is sort of a tradeoff of more time for less storage.
10:54:34 <int-e> shachaf: I'm not sure why it needs to be more complicated than that
10:55:38 <int-e> I suppose C++ frowns upon using `free` as an identifier ;-)
10:55:40 <wib_jonas> I guess you could do an intermediate thing where instead of binomial calculations you just repeatedly increase the delay counters by one. You still need a weighted random choice, but that's not that bad.
10:55:59 <wib_jonas> int-e: I think it only frowns upon using it as a *global* identifier or macro
10:56:20 <wib_jonas> I think you're fine using it as local
10:57:20 <wib_jonas> also don't try to use j0 as a global function name in C, as I learned from mysterious linker errors...
10:58:01 <int-e> Bessel
10:58:03 <wib_jonas> nor nl, beacuse curses is old and pollutes the global C namespace with nonsense like that, and we couldn't get rid of it yet
10:59:09 <int-e> rain1: I've started a new game just to see what it was like and... how do you figure out what the objective is ;)
10:59:20 <rain1> that's part of the fun!
10:59:33 <int-e> I mean, I remember it.
10:59:46 <wib_jonas> the objective is to get the credit screen to appear... wait, what game is this?
10:59:52 <int-e> But I don't recall how I figured it out.
10:59:57 <rain1> replaying it, I find different win conditions
11:00:08 <wib_jonas> is it still the sausage roll?
11:00:14 <int-e> yes
11:00:38 <rain1> oh sorry, I was thinking baba
11:00:48 <int-e> oh sorry
11:00:57 <int-e> Baba made it easier, I think
11:02:01 <int-e> Let's see.I deleted all my progress anyway
11:02:28 <wib_jonas> well Baba has the first level say "flag is win" or some such thing, right?
11:03:55 <shachaf> int-e: OK, I think you want something like: { int f = filled[i]; if (f != -1) { avail[f] = avail[free-1]; filled[avail[f]] = f; filled[i] = -1; free--; } }
11:04:30 <shachaf> You don't ever want avail[i], I think, probably you meant avail[f]? That's the bit that was confusing me.
11:05:26 <int-e> wib_jonas: yes. and the level is designed in a way that doesn't tempt you to mess with the text
11:06:35 <int-e> https://int-e.eu/~bf3/tmp/baba_start.png
11:08:16 <int-e> shachaf: ah yes. that looks like what I want indeed.
11:08:20 -!- adu has joined.
11:08:48 <shachaf> In some universe you would have different types for sparse and dense indices.
11:08:52 <shachaf> (Not this one, though.)
11:09:06 <shachaf> Anyway this solution is good. I like it.
11:10:06 <wib_jonas> int-e: thanks for the link
11:11:01 <wib_jonas> shachaf: nah, I'd just use uint16_t or uint32_t for both, depending on whether I can have more than 65000 coins
11:11:24 <shachaf> I don't mean machine types but type checker types.
11:11:44 <shachaf> I don't think that's actually a great idea, but I do think it's easy to mix them up.
11:11:59 <shachaf> Do you know the problem of sampling k integers (in the range [0,N)) without replacement?
11:12:33 <wib_jonas> shachaf: yes, but still no, because this is simple enough to not require types. I might choose better identifier names of course.
11:12:52 <shachaf> When I tried to figure it out I came up with an OK answer, with the right asymptotic behavior, but it turned out there was an even nicer algorithm.
11:13:01 <shachaf> wib_jonas: Yes, that's why I said it's not in this universe.
11:14:28 <wib_jonas> shachaf: yes, I actually researched that. the dense case (k is on the order of magnitude of N) is well known. For the sparse case, TAOCP has one solution, but there's another solution that seems equally good, and was either invented or independently reinvented by Roger Hui, and that I should send as an improvement ticket to TAOCP, but I'm lazy and
11:14:29 <wib_jonas> have been putting it off as Knuth won't work on volume 2 for a long time.
11:14:55 <shachaf> wib_jonas: What are the two solutions?
11:14:57 <wib_jonas> I don't think either solution is clearly nicer than the other.
11:15:22 <shachaf> My solution used a lookup table, int->int, whereas the nicer solution only used a set of ints.
11:15:30 <shachaf> Uh, not a lookup table.
11:15:36 <shachaf> A map, modified at runtime.
11:16:12 <wib_jonas> shachaf: both solutions need a hash of size constant times k where the keys are indexes up to N, but in both cases the hash part is easy because you can use a trivial hash function because you will be storing random keys only.
11:16:22 <wib_jonas> but there are two ways to use that hash to pick a sample of size k.
11:16:50 <shachaf> wib_jonas: whoa, somehow I didn't make that observation, that you can use a simpler hash table because your keys are guaranteed random.
11:17:15 <shachaf> Or are they? Hmm.
11:17:40 <wib_jonas> shachaf: maybe you should read TAOCP then? the solution in TAOCP is to use the hash to store which items have been picked, keep picking a random item out of the N, redo the pick if you have already picked the same item, and repeat until you got k successes.
11:17:44 <int-e> rain1: Oh looks like 105 is actually a relatively nice phase of the game where you have plenty of levels to choose from (but it's hard to say)
11:18:15 <shachaf> wib_jonas: Redo the pick? Doesn't that have arbitrarily long worst case runtime?
11:18:34 <shachaf> You can do this with exactly k calls to the RNG.
11:18:40 <wib_jonas> shachaf: yes, but again it's uniform random so it's exponentially fast,
11:19:08 <wib_jonas> and in both cases you do this only if k is significantly less than N, so the probability that you pick the wrong thing is less than k/N, which is less than 1/5
11:19:22 <wib_jonas> you just do the normal dense solution if 5*k>=N
11:19:47 <rain1> yeah the difficulty curve isa lot kinder
11:19:49 <int-e> rain1: Anyway, at the point I reached I have one level to solve and I got totally stuck on that one. Which is... meh.
11:19:50 <shachaf> OK, but there are nice algorithms that just works in all cases.
11:19:52 <rain1> but still ends up being a super hard game
11:20:01 <rain1> int-e in SSR?
11:20:07 <int-e> rain1: yeah in SSR
11:20:12 <rain1> is that in the fire zone?
11:20:25 <int-e> No, I'm past that.
11:20:26 <wib_jonas> Roger Hui's solution is to simulate the dense algorithm, which maintains a permutation that is initially the identity permutation. It will change k random items and the k last items in that. So you store the k last items in a dense array, and any other items that don't match the identity in your hash. In this case the hash has values too, not just
11:20:26 <wib_jonas> keys.
11:20:28 <rain1> oh exciting
11:20:31 <rain1> i thought this was the last zone
11:20:52 <shachaf> wib_jonas: Oh, that's my solution.
11:20:56 <wib_jonas> In this case there's still potential redo: it comes from the algorithm to pick a uniform random number from a size that's something between N and N-k+1
11:20:57 <int-e> there's a sort of vikings zone
11:21:14 <wib_jonas> shachaf: right, that's why I think Roger Hui may have independently reinvented the solution
11:21:28 <shachaf> But Floyd's solution is even better.
11:21:31 <wib_jonas> shachaf: note that generating the single random pick comes with a chance to redo in first place
11:21:48 <wib_jonas> What's Floyd's solution?
11:21:49 <shachaf> Yes, noted.
11:22:28 <wib_jonas> I don't think you can have ANY solution with no chance to redo, because you have to pick one solution among binomial(N,k), and that's usually not a power of 2
11:23:18 <shachaf> I was taking "pick a single random number in [0,n)" as a primitive.
11:23:42 <wib_jonas> it can probably only be a power of 2 if k<=1, and k=1 is a special case with well-known solution, k=0 is trivial
11:23:48 <shachaf> Let me see if I can remember Floyd's solution and the phrasing I liked.
11:23:52 -!- Phantom_Hoover has quit (*.net *.split).
11:23:53 -!- zzo38 has quit (*.net *.split).
11:23:53 -!- MDude has quit (*.net *.split).
11:23:53 -!- ocharles has quit (*.net *.split).
11:23:53 -!- lambdabot has quit (*.net *.split).
11:24:21 <wib_jonas> shachaf: you can do that, but then you're cheating with accounting. in exchange for perhaps slightly more retries, the TAOCP solution has less bookkeeping and an easier implementation.
11:24:41 <wib_jonas> The hash table stores only values, not keys, and you only have to modify one element, not two.
11:24:47 <shachaf> That's a fair argument that I hadn't thought of.
11:25:03 <wib_jonas> There's no special case for when you pick one of the last elements either.
11:25:05 <shachaf> Floyd's algorithm also stored only values rather than key-value pairs.
11:25:48 <shachaf> Let me see if I can remember it exactly. It took me a bit to convince myself it was correct, but with the right phrasing it's hopefully obvious.
11:25:50 <wib_jonas> And if there's a "Floyd's solution" that isn't clearly worse than the TAOCP solution, why is that not in TAOCP in first place?
11:26:11 <wib_jonas> shachaf: yes, the same is true about Roger Hui's algorithm, since I read it in source code form
11:26:14 <shachaf> I don't know. I've only read the SAT section of TAOCP.
11:26:38 -!- clog has quit (Ping timeout: 264 seconds).
11:26:49 <int-e> rain1: there's a huge area to the south that goes all the way back (eastward) to the starting island... and probably beyond but that's about where I'm stuck
11:27:01 <wib_jonas> unless that solution is later or close in time to the third edition of vol 2 of course
11:27:31 -!- Phantom_Hoover has joined.
11:27:31 -!- zzo38 has joined.
11:27:31 -!- MDude has joined.
11:27:31 -!- ocharles has joined.
11:27:31 -!- lambdabot has joined.
11:29:40 <shachaf> To sample k numbers < N: First sample a smaller set of k-1 numbers < N-1. Then choose a random number i < N. If i isn't in the smaller set, then just add it. If i is in the set, add N-1 instead.
11:30:29 -!- arseniiv has joined.
11:34:13 <int-e> rain1: https://int-e.eu/~bf3/tmp/ssr-south-of-start.png ... actually I'm stuck quite a bit east from there.
11:34:33 <rain1> hmm
11:34:45 <int-e> rain1: and if I place the area correctly, the fire area is a good way west (and a bit to the north) from there.
11:34:55 <int-e> the ssr world is huge.
11:35:16 <rain1> ive restarted the game a couple times, to reintegrate the knowledge from earlier levels
11:35:31 <rain1> but i havent got past the fire zone yet
11:36:03 <int-e> I forgot what the twist in that area was... I played one level where you had to kind of plan for your way back
11:36:37 <int-e> and you had to work pretty hard on turning a roll by 90 degrees
11:37:02 -!- tromp has joined.
11:37:34 <int-e> But meh, I think it'll just be an unfinished game for the time being. Lots of other games around.
11:38:31 <rain1> what other games do you like?
11:39:53 <shachaf> IntSet sample(int N, int k) { IntSet s = empty_set(); for (int i = N - k + 1; i <= N; i++) { int v = rand(i); if (!has(s, v)) { add(s, v); } else { add(s, i-1); } } return s; }
11:40:05 -!- craigo has joined.
11:40:27 <shachaf> This is just better than the simulated shuffle algorithm I came up with (which I guess Hui did first?).
11:41:29 <shachaf> If TAOCP has a section on sampling naturals sparsely without replacement, and it doesn't mention this algorithm, that's a glaring omission.
11:41:39 <esowiki> [[Special:Log/newusers]] create * The Esolanger * New user account
11:41:40 <shachaf> I doubt that's the situation of the world.
11:42:00 <rain1> claim your $2.56
11:42:20 <wib_jonas> shachaf: I don't know who did first. I heard the solution from Roger Hui, and he confirmed in an email that he came up with the solution idependently, but this is something multiple people could have invented.
11:45:04 <int-e> rain1: I guess the genre that I play most is click&point adventures. But I kind of want to finish a first person shooter at some point. I almost made it through Bioshock Infinite... and then I lost the savegame in an OS reinstall (because it was in a place I didn't think to back up).
11:45:05 <esowiki> [[Esolang:Introduce yourself]] https://esolangs.org/w/index.php?diff=75723&oldid=75539 * The Esolanger * (+188) /* Introductions */
11:46:07 <wib_jonas> rain1: it's not an error but a significant suggestion, so it's worth only $0.32, and that only if you're the first to suggest it
11:46:16 <int-e> I guess the only hard constraint is that I don't do multiplayer.
11:46:35 <wib_jonas> shachaf: I don't understand why that solution works yet
11:48:41 <int-e> it doesn't feel uniform
11:48:54 <shachaf> It is. But it uses trickery.
11:50:38 <wib_jonas> I kind of want to finish a first person shooter at some point => I think the most popular ones are Doom, Hexen, Perfect Dark, Half-Life.
11:50:59 <wib_jonas> Most popular as story in single-player mode that is, as opposed to multiplayer fights.
11:51:24 <wib_jonas> You should probably at least know about those four before deciding what to play.
11:51:49 <int-e> Ah, I think I get it. When you use i-1 you pretend that the element you clashed it actually had that index.
11:52:12 <int-e> But using a set obscures that fact, you should really sample an ordered list.
11:53:07 <wib_jonas> int-e: both the TAOCP algorithm and Roger Hui's algorithm actually samples an ordered list
11:54:29 <shachaf> Say you've sampled k numbers < N, stored in a set S. So each number <N has k/N probability of being in S.
11:54:49 <shachaf> You want k+1/N+1 numbers <N+1.
11:55:39 <shachaf> There are k numbers you've already chosen, along with N+1 itself, in the range you're picking from. So that gives the right probability of picking N+1.
11:55:59 <shachaf> And certainly all the other numbers are treated uniformly.
11:58:44 <shachaf> Uh, I meant you want k+1 numbers <N+1, each with probability k+1/N+1
11:59:50 <int-e> https://paste.debian.net/1155889/
12:00:25 <int-e> I find this conceptually easier, don't sort, just produce permutations
12:01:07 <shachaf> But that searches the array linearly.
12:01:16 <int-e> it's not about performance
12:01:26 <int-e> it's about correctness
12:01:33 <shachaf> Sure. I mean, this is why I phrased it as a set.
12:01:47 <int-e> I find it harder to digest as a set
12:03:01 <shachaf> Fair enough.
12:03:31 <shachaf> Here's a source: https://fermatslibrary.com/s/a-sample-of-brilliance
12:04:40 <int-e> (The advantage of the list is that each sequence of random sample produces excactly one list *and vice versa*)
12:04:46 <shachaf> I didn't even think about producing permutations with it, that's neat.
12:05:05 <shachaf> In particular the way it distinguishes the picking N+1 case from the picking some previously-picked number case.
12:05:21 <shachaf> Even though they have the same effect on the set.
12:05:23 <int-e> (Still something to think about but you don't have to count anything to see that it's fair.)
12:10:55 <wib_jonas> shachaf: so this is like Roger Hui's solution, but doesn't keep track of the order of the objects in the output, so if you want an ordered sample, you need an extra permute step afterwards?
12:11:08 <wib_jonas> interesting
12:11:46 <wib_jonas> of course, Roger Hui's solution specifically wants to pick an ordered set, and... let me look up how Knuth's exercise is phrased, but I guess it should ideally talk about both
12:12:15 <wib_jonas> and Roger Hui's solution needs the extra bookkeeping to know which element to move even if k is large
12:14:36 <wib_jonas> shachaf: interesting, thank you for mentioning this algorithm.
12:15:01 <wib_jonas> shachaf: to be clear, is this the one you said was Floyd's?
12:15:03 <shachaf> If you want the order, you can do what int-e did.
12:15:20 <int-e> mumble 'If you are a programmer, you might be surprised but other people normally don’t like hierarchies.'
12:15:27 <int-e> unfortunately, I'm a programmer
12:15:30 <esowiki> [[Obfuna]] https://esolangs.org/w/index.php?diff=75724&oldid=36826 * DmilkaSTD * (-3)
12:15:52 <wib_jonas> shachaf: yes, int-e does a linear traversal, which works for small k only
12:15:57 <shachaf> I didn't actually read your description of Roger Hui's solution carefully. My solution doesn't store the dense array, only the hash table, and extracted the result from the hash table keys later.
12:16:12 <shachaf> wib_jonas: Sure, but if you want to store both an array and a set, you can do that.
12:16:25 -!- t20kdc has joined.
12:16:30 <shachaf> The same transformation applies to both algorithms.
12:16:35 <wib_jonas> shachaf: or you can permute randomly afterwards
12:16:36 <shachaf> Or, hmm, maybe I'm just saying nonsense.
12:18:56 <shachaf> Anyway, if you don't care about the order of the elements, you can just store a hash table, without the dense array, for the algorithm you described.
12:18:58 <wib_jonas> TAOCP 3.4.2. exercise 16. and it asks for a sorted output, so that Floyd thing is acceptable for that
12:19:10 <wib_jonas> shachaf: yes, and you only store keys in the hash table, not values
12:20:18 <shachaf> I do not have TAOCP unfortunately.
12:21:56 <esowiki> [[Recurl]] M https://esolangs.org/w/index.php?diff=75725&oldid=23463 * PythonshellDebugwindow * (+66) notice
12:22:45 <shachaf> So this is presented as an exercise, not a full thing discussed in the main text?
12:22:58 <esowiki> [[Amycus]] M https://esolangs.org/w/index.php?diff=75726&oldid=58495 * PythonshellDebugwindow * (+2) fix term
12:23:10 <wib_jonas> shachaf: yes
12:23:15 <wib_jonas> the dense case is in the main text
12:23:20 <int-e> wib_jonas: again, I wrote that code not to be fast but to be clear and simple
12:23:22 <shachaf> I guess it has no obligation to be complete.
12:23:34 <esowiki> [[Amicus]] M https://esolangs.org/w/index.php?diff=75727&oldid=58499 * PythonshellDebugwindow * (+2) erm
12:23:42 <int-e> wib_jonas: because I didn't understand why the sampling was uniform when it was phrased in terms of a set
12:24:04 <esowiki> [[Amycus Severus]] M https://esolangs.org/w/index.php?diff=75728&oldid=57642 * PythonshellDebugwindow * (-7) unpipe & term
12:24:43 <esowiki> [[Hyperamicus]] M https://esolangs.org/w/index.php?diff=75729&oldid=58494 * PythonshellDebugwindow * (+2) link
12:24:56 <esowiki> [[Hyperamicus]] M https://esolangs.org/w/index.php?diff=75730&oldid=75729 * PythonshellDebugwindow * (+0) user a
12:25:04 <shachaf> Is the dense case "do a Fisher-Yates shuffle, but stop once you've shuffled the last k elements of the array"?
12:25:21 <wib_jonas> shachaf: yes
12:25:31 <esowiki> [[GolfScript]] M https://esolangs.org/w/index.php?diff=75731&oldid=67212 * PythonshellDebugwindow * (+0) /* Overview */
12:25:45 <wib_jonas> The main text also discusses the problem where you read N records in sequence once and want to keep k random records from them, but you don't know N in advance
12:25:55 <esowiki> [[GolfScript]] M https://esolangs.org/w/index.php?diff=75732&oldid=75731 * PythonshellDebugwindow * (+23) /* External resources */ cat langs
12:26:18 <shachaf> The thing called reservoir sampling?
12:26:47 <wib_jonas> yes
12:26:54 <wib_jonas> and wait, I might be wrong here about the dense case, let me reread
12:28:46 <shachaf> A lot of these things seem almost too simple to have names.
12:29:19 <int-e> Oh the "Add file" UI isn't new, it's just much more visible now.
12:29:39 <wib_jonas> the main text says "Algorithm P can easily be modified to yield a random permutation of a
12:29:39 <wib_jonas> random combination" where Algorithm P is the shuffle
12:29:57 -!- clog has joined.
12:30:20 <wib_jonas> shachaf: they don't really have names to me, I just look them up in Knuth and refer to a chapter number or algorithm in a chapter number or an exercise in a chapter number
12:30:38 <wib_jonas> TAOCP is one of the bibles for this, so those references are as good as canonical names
12:30:41 <esowiki> [[StubScript]] M https://esolangs.org/w/index.php?diff=75733&oldid=73062 * PythonshellDebugwindow * (+364) interpreter and cats
12:30:56 <esowiki> [[StubScript]] M https://esolangs.org/w/index.php?diff=75734&oldid=75733 * PythonshellDebugwindow * (+6) bold
12:32:38 <wib_jonas> sure, a few of them also have fancy names
12:32:56 <shachaf> I mean, nothing wrong with naming things, but I think I came up with simple versions of both Fisher-Yates shuffles and reservoir sampling when I first thought about these problems.
12:33:09 <wib_jonas> we need those fancy names to be able to mention them in the short description of what will be in the exam
12:33:10 <shachaf> Not that that means it was trivial originally, of course.
12:33:56 <esowiki> [[BrainCurses/implementation.js]] M https://esolangs.org/w/index.php?diff=75735&oldid=53986 * PythonshellDebugwindow * (+22) back
12:34:16 <shachaf> Anyway, Floyd's algorithm I did not come up with, even though it's super duper simple and (in retrospect) obviously the right thing.
12:34:29 <wib_jonas> Remembering which name refers to what theorem was actually non-trivial for me for the calculus exams, and I think the dual problem of writing concise but clear names on the exam topic sheet is also nontrivial.
12:34:42 <shachaf> I mean, I read the algorithm, didn't understand it, and then realized that it was "obviously" correct in the shower the next day.
12:35:06 <wib_jonas> Because, as they say, programming has two hard problems, naming, off-by-one errors, and caching.
12:35:06 <esowiki> [[BrainCurses]] M https://esolangs.org/w/index.php?diff=75736&oldid=51089 * PythonshellDebugwindow * (+18)
12:36:18 <esowiki> [[Malbolge]] M https://esolangs.org/w/index.php?diff=75737&oldid=65587 * PythonshellDebugwindow * (+4) ok
12:36:27 <shachaf> int-e: Oh, the paper I linked to actually mentions a variation of your variation.
12:36:41 <esowiki> [[Lisp]] M https://esolangs.org/w/index.php?diff=75738&oldid=70712 * PythonshellDebugwindow * (+0)
12:36:45 <shachaf> On the third page, "Floyd's Permutation Algorithm".
12:36:50 <wib_jonas> shachaf: I'll have to look at that later then
12:36:58 <wib_jonas> good thing we have channel logs
12:37:00 <esowiki> [[Topline]] M https://esolangs.org/w/index.php?diff=75739&oldid=69673 * PythonshellDebugwindow * (-8) rm redundancy
12:38:11 <esowiki> [[Urban Mller]] M https://esolangs.org/w/index.php?diff=75740&oldid=69972 * PythonshellDebugwindow * (-1)
12:39:35 <esowiki> [[Dc]] M https://esolangs.org/w/index.php?diff=75741&oldid=70769 * PythonshellDebugwindow * (+4) /* Computational class */ link
12:41:04 <esowiki> [[Befunge]] M https://esolangs.org/w/index.php?diff=75742&oldid=70604 * PythonshellDebugwindow * (+4) l
12:41:51 <esowiki> [[BitCycle]] M https://esolangs.org/w/index.php?diff=75743&oldid=50900 * PythonshellDebugwindow * (+4) /* Computational class */ l
12:42:41 <esowiki> [[Haddock]] M https://esolangs.org/w/index.php?diff=75744&oldid=65159 * PythonshellDebugwindow * (+55) /* Implementing Haddock */ cats
12:43:36 <esowiki> [[Deadfish]] M https://esolangs.org/w/index.php?diff=75745&oldid=72890 * PythonshellDebugwindow * (+56) /* External resources */ cats
12:45:56 <esowiki> [[Obfuna]] M https://esolangs.org/w/index.php?diff=75746&oldid=75724 * PythonshellDebugwindow * (+5) "a unary" is correct, "yoonary" has a consonant start sound
12:47:02 <esowiki> [[Back]] M https://esolangs.org/w/index.php?diff=75747&oldid=75721 * PythonshellDebugwindow * (+0)
12:56:31 -!- TheLie has quit (Remote host closed the connection).
13:28:32 -!- BWBellairs[NNRF] has joined.
13:29:53 -!- BWBellairs has quit (Ping timeout: 256 seconds).
13:29:54 -!- BWBellairs[NNRF] has changed nick to BWBellairs.
13:30:28 -!- pikhq has quit (Ping timeout: 256 seconds).
13:30:58 -!- HackEso has quit (Ping timeout: 256 seconds).
13:31:56 -!- HackEso has joined.
13:32:01 -!- pikhq has joined.
13:34:41 -!- deschutron has joined.
13:41:18 <int-e> Oh, I found my slitherlink solver.
13:41:59 <int-e> It's Haskell, uses an unpublished minisat binding, and has snarky comments that are pretty useless.
13:42:58 <int-e> But, for posterity: https://int-e.eu/~bf3/tmp/SL.hs
13:44:48 <int-e> I wonder what the input format was.
13:53:51 <int-e> (it's the dimenstions on two lines, then the puzzle constraints as digits, with '4' for no constraint)
13:54:26 <int-e> (but I have no sample inputs. not that it matters because I won't be compiling this anyway)
14:05:16 <arseniiv> <int-e> It's Haskell, uses an unpublished minisat binding, and has snarky comments that are pretty useless. => rofoldr
14:23:57 <esowiki> [[BF-ASM:8]] https://esolangs.org/w/index.php?diff=75748&oldid=75670 * DmilkaSTD * (+2)
14:32:45 <esowiki> [[BF-ASM:8]] https://esolangs.org/w/index.php?diff=75749&oldid=75748 * DmilkaSTD * (+2)
14:35:38 <esowiki> [[BF-ASM:8]] https://esolangs.org/w/index.php?diff=75750&oldid=75749 * DmilkaSTD * (-7)
14:38:12 <esowiki> [[BF-ASM:8]] https://esolangs.org/w/index.php?diff=75751&oldid=75750 * DmilkaSTD * (+55)
14:38:31 <esowiki> [[BF-ASM:8]] https://esolangs.org/w/index.php?diff=75752&oldid=75751 * DmilkaSTD * (-5)
14:40:38 <esowiki> [[BF-ASM:8]] https://esolangs.org/w/index.php?diff=75753&oldid=75752 * DmilkaSTD * (-16)
14:45:37 <esowiki> [[BF-ASM:8]] https://esolangs.org/w/index.php?diff=75754&oldid=75753 * DmilkaSTD * (+88)
15:04:01 -!- wib_jonas has quit (Quit: Connection closed).
15:22:25 -!- Arcorann has quit (Read error: Connection reset by peer).
15:27:28 <esowiki> [[BF-ASM:8]] M https://esolangs.org/w/index.php?diff=75755&oldid=75754 * PythonshellDebugwindow * (+0) /* Syntax */ grm
15:43:00 <esowiki> [[Talk:Dig]] https://esolangs.org/w/index.php?diff=75756&oldid=75691 * DeybisMelendez * (+534) /* Length of Duration Underground */
15:57:57 <esowiki> [[ReThue]] M https://esolangs.org/w/index.php?diff=75757&oldid=73214 * PythonshellDebugwindow * (+118)
16:05:43 -!- atslash has quit (Quit: Leaving).
16:16:54 <esowiki> [[Ni]] https://esolangs.org/w/index.php?diff=75758&oldid=75187 * DeybisMelendez * (+531) Major update
16:18:31 <esowiki> [[Ni]] https://esolangs.org/w/index.php?diff=75759&oldid=75758 * DeybisMelendez * (+3) little error
16:25:21 <esowiki> [[SYCPOL]] M https://esolangs.org/w/index.php?diff=75760&oldid=53791 * PythonshellDebugwindow * (+56)
16:25:42 <esowiki> [[COBOL]] M https://esolangs.org/w/index.php?diff=75761&oldid=66152 * PythonshellDebugwindow * (+6)
16:35:28 -!- joel2 has changed nick to lucky.
16:35:34 -!- lucky has quit (Changing host).
16:35:34 -!- lucky has joined.
16:58:09 <esowiki> [[Deklare]] M https://esolangs.org/w/index.php?diff=75762&oldid=68163 * PythonshellDebugwindow * (+15) fix tmp
16:58:17 <esowiki> [[Deklare]] M https://esolangs.org/w/index.php?diff=75763&oldid=75762 * PythonshellDebugwindow * (+4) link
16:59:11 <esowiki> [[Befunge/index.php]] M https://esolangs.org/w/index.php?diff=75764&oldid=30388 * PythonshellDebugwindow * (+4)
17:16:41 <esowiki> [[BF-ASM:8]] M https://esolangs.org/w/index.php?diff=75765&oldid=75755 * DmilkaSTD * (-4)
17:16:48 <esowiki> [[COW]] M https://esolangs.org/w/index.php?diff=75766&oldid=72358 * PythonshellDebugwindow * (+28) cat
17:16:59 <esowiki> [[COW]] M https://esolangs.org/w/index.php?diff=75767&oldid=75766 * PythonshellDebugwindow * (+0) /* External resources */
17:24:55 <esowiki> [[BF-ASM:8]] https://esolangs.org/w/index.php?diff=75768&oldid=75765 * DmilkaSTD * (+829) +hello world compiled
17:32:35 -!- Sgeo has joined.
17:42:45 <esowiki> [[Mind reader]] M https://esolangs.org/w/index.php?diff=75769&oldid=68828 * DmilkaSTD * (-776) I'm ashamed of this
17:47:24 -!- aaaaaa has quit (Ping timeout: 256 seconds).
17:47:25 <esowiki> [[Mind reader]] M https://esolangs.org/w/index.php?diff=75770&oldid=75769 * PythonshellDebugwindow * (+108)
17:48:13 <esowiki> [[InDec]] M https://esolangs.org/w/index.php?diff=75771&oldid=44554 * PythonshellDebugwindow * (+37) ca
17:48:54 <esowiki> [[Meander]] M https://esolangs.org/w/index.php?diff=75772&oldid=73035 * PythonshellDebugwindow * (+24) ns notice
17:49:29 <esowiki> [[AlphaBeta]] M https://esolangs.org/w/index.php?diff=75773&oldid=66410 * PythonshellDebugwindow * (-20) rm reduntant pipes
17:51:06 <esowiki> [[Re:direction]] M https://esolangs.org/w/index.php?diff=75774&oldid=58999 * PythonshellDebugwindow * (+4) /* Hello world program */ ln
17:52:25 <esowiki> [[Colambda]] M https://esolangs.org/w/index.php?diff=75775&oldid=20549 * PythonshellDebugwindow * (+27)
17:54:11 <esowiki> [[Numeric Batch]] M https://esolangs.org/w/index.php?diff=75776&oldid=39048 * PythonshellDebugwindow * (+47)
17:54:28 <esowiki> [[Numeric Batch]] M https://esolangs.org/w/index.php?diff=75777&oldid=75776 * PythonshellDebugwindow * (+1) /* Information */ fix
17:55:43 <esowiki> [[Gopher]] M https://esolangs.org/w/index.php?diff=75778&oldid=64377 * PythonshellDebugwindow * (+38) link, cat, __quine
18:14:23 <esowiki> [[User:PythonshellDebugwindow/(Unnamed language)]] M https://esolangs.org/w/index.php?diff=75779&oldid=75715 * PythonshellDebugwindow * (+1366)
18:28:00 -!- b_jonas has joined.
18:32:33 <esowiki> [[User:PythonshellDebugwindow/(Unnamed language)]] M https://esolangs.org/w/index.php?diff=75780&oldid=75779 * PythonshellDebugwindow * (+654) /* Truth-machine */ is tc
18:33:08 <b_jonas> I have a musing about programming concept where I want to explain to you #esoteric teddy bear style, and ask for references and names
18:35:18 <b_jonas> you know how all APLs have this feature where a lot of basic operations, including most arithmetic like multiplication, automatically maps over arrays, so if you write (x + y) where y is an array then that's the same as (map (x +) y)
18:35:43 <b_jonas> only this gets more complicated because of multi-dimensional arrays and because of uncurried multi-arity functions
18:38:24 <esowiki> [[Eitherf*ck]] https://esolangs.org/w/index.php?diff=75781&oldid=68887 * DmilkaSTD * (+25)
18:39:34 <esowiki> [[Mindwhipper]] https://esolangs.org/w/index.php?diff=75782&oldid=70028 * Asasnat * (+155)
18:41:09 <esowiki> [[User:PythonshellDebugwindow/(Unnamed language)]] M https://esolangs.org/w/index.php?diff=75783&oldid=75780 * PythonshellDebugwindow * (+136)
18:41:28 <esowiki> [[User:PythonshellDebugwindow/(Unnamed language)]] M https://esolangs.org/w/index.php?diff=75784&oldid=75783 * PythonshellDebugwindow * (+6) /* Computational class */
18:43:14 <esowiki> [[Mindwhipper]] M https://esolangs.org/w/index.php?diff=75785&oldid=75782 * Asasnat * (+189)
18:43:38 <esowiki> [[Mindwhipper]] https://esolangs.org/w/index.php?diff=75786&oldid=75785 * Asasnat * (+27)
18:45:27 <esowiki> [[User:PythonshellDebugwindow/(Unnamed language)]] M https://esolangs.org/w/index.php?diff=75787&oldid=75784 * PythonshellDebugwindow * (+32) /* BREAK */
18:46:03 <esowiki> [[User:PythonshellDebugwindow/(Unnamed language)]] M https://esolangs.org/w/index.php?diff=75788&oldid=75787 * PythonshellDebugwindow * (-18) /* END */
18:49:39 <esowiki> [[User:PythonshellDebugwindow/(Unnamed language)]] M https://esolangs.org/w/index.php?diff=75789&oldid=75788 * PythonshellDebugwindow * (-2468) Blanked the page
18:49:55 <esowiki> [[Point Break]] N https://esolangs.org/w/index.php?oldid=75790 * PythonshellDebugwindow * (+2501) add Point Break
18:51:43 <esowiki> [[Poochiewuddledumpling-Boobledarling]] M https://esolangs.org/w/index.php?diff=75791&oldid=35646 * PythonshellDebugwindow * (+63) link & impl
18:52:23 <esowiki> [[User:DmilkaSTD]] https://esolangs.org/w/index.php?diff=75792&oldid=75683 * DmilkaSTD * (-1056)
18:53:34 <esowiki> [[BF-ASM:8]] https://esolangs.org/w/index.php?diff=75793&oldid=75768 * DmilkaSTD * (+91)
18:53:55 <esowiki> [[Code is eso]] https://esolangs.org/w/index.php?diff=75794&oldid=75406 * DmilkaSTD * (+91)
18:54:10 <esowiki> [[MineScript]] https://esolangs.org/w/index.php?diff=75795&oldid=69873 * DmilkaSTD * (+91)
18:54:29 <esowiki> [[Asvi]] https://esolangs.org/w/index.php?diff=75796&oldid=74387 * DmilkaSTD * (+91)
18:54:42 <esowiki> [[Asvi]] https://esolangs.org/w/index.php?diff=75797&oldid=75796 * DmilkaSTD * (-230)
18:58:11 <esowiki> [[Anarchysm]] M https://esolangs.org/w/index.php?diff=75798&oldid=75240 * DmilkaSTD * (-23)
19:00:26 <esowiki> [[Language list]] M https://esolangs.org/w/index.php?diff=75799&oldid=75698 * PythonshellDebugwindow * (+18) /* P */ +[[Point Break]]
19:01:11 <esowiki> [[Fscratch]] M https://esolangs.org/w/index.php?diff=75800&oldid=74654 * DmilkaSTD * (-296)
19:01:28 <esowiki> [[Fscratch]] https://esolangs.org/w/index.php?diff=75801&oldid=75800 * DmilkaSTD * (-60)
19:02:19 <esowiki> [[PPAP++]] M https://esolangs.org/w/index.php?diff=75802&oldid=60767 * PythonshellDebugwindow * (+171)
19:02:27 <esowiki> [[PPAP++]] M https://esolangs.org/w/index.php?diff=75803&oldid=75802 * PythonshellDebugwindow * (-1) /* External resources */
19:03:59 <esowiki> [[User:PythonshellDebugwindow]] M https://esolangs.org/w/index.php?diff=75804&oldid=75699 * PythonshellDebugwindow * (+77) /* Languages */
19:19:34 <arseniiv> b_jonas: please go on
19:21:43 <arseniiv> finally I sat up to listen to a recording of a course on Clifford algebras but this is just the introduction and overview I hadn’t yet climbed over (in that course). Want my knowledge on them be systematic and general, and hopefully I’ll get spinors after it
19:21:48 <b_jonas> sorry I am sidetracked
19:21:54 <b_jonas> I'll return
19:22:40 <arseniiv> oh, and there is some bibliography!
19:25:41 <arseniiv> b_jonas: BTW that’s an interesting topic for a language design—an unambiguous notation for various function actions which is simple to use. What APL does may be one extreme and what e. g. Haskell does may be another (though with careful type classes, one can make (+) work in interesting ways and at the same time not too mysteriously)
19:26:59 -!- adu has quit (Quit: adu).
19:31:56 <b_jonas> Anyway, so in APL all arrays are mapped over like this, but there's also a possible design where ordinary arrays don't have this property, but you have a special type of immutable arrays that does this, and ways to convert both ways. The only language I know that clearly takes this path is perl6, where the latter kind are called junctions. J and its boxed arrays are somewhat similar, but in J the
19:32:02 <b_jonas> default array type is the unboxed one that does map through.
19:32:50 <b_jonas> Now you could also imagine a language where the mapping is done not in the primitives but in every function by default, so if you define a function the simplest way, it will map over all its array arguments, but you can define special kinds of functions that don't do this and let you introspect an array eg. index it.
19:34:08 <b_jonas> Of course for some functions, mapping outside and mapping inside are equivalent, or are related by transposing the axis of the results, and in those cases an interpreter may transparently optimize between them, in both directions in fact because sometimes one is better sometimes the other, and
19:35:11 <b_jonas> it can even optimize to the middle ground where it breaks an input array to L1-cache-sized chunks and calls the function for each chunk, looping over the elements of the chunks in the primitives that the function calls.
19:36:19 <b_jonas> Now there's another phenomenon: perl 5 has lists where if you pass the list to an ordinary function, it will automatically splat it to multiple arguments. Mathematica has that kind of list too, IIRC called List, but it's not the default kind of array. In both cases, there are some functions and/or builtins
19:36:56 <b_jonas> where arguments aren't splatted, and these can be used to introspect such a list, although a vararg function can introspect them too if you have vararg functions.
19:37:20 <b_jonas> You can even do this one with static typing if you only allow this sort of list to have a length known at compile time.
19:37:27 <arseniiv> b_jonas: in Mathematica, it should be a Sequence if I understood correctly
19:38:19 <b_jonas> Now what I'd like to know is if there's a name for these two types of immutable arrays, and/or the phenomenon where a language has them. I think the former is called "array languages", that's the grouping for APL and matlab/octave.
19:38:34 <b_jonas> Iirc maple also has the latter kind of lists.
19:38:38 <b_jonas> But I'm not sure about that.
19:38:51 <b_jonas> And there's a third phenomenon, which is not about lists, but might be related here.
19:39:50 <b_jonas> Namely in Mathematica, when you call an ordinary function, it first evaluates each of the arguments that you pass, just like an ordinary function in any language, and this applies to new functions you define. But you can define special macro-like functions that don't do this, and they can do anything they want with their unevaluated arguments.
19:40:31 <b_jonas> Normal languages either always evaluate the arguments of functions before calling, which is eager evaluation, or postpone evaluating them to when they're first needed, which is lazy evaluation,
19:40:49 <b_jonas> but some languages like scheme allow you to define macros that do neither, and can introspect their unevaluated arguments.
19:41:49 <b_jonas> Mathematica also has a simple container that contains one unevaluated value, called Hold, and maple sort of has its equivalent, backticks, except that in maple, there are some arithmetic evaluation rules that are always done even inside backticks.
19:42:42 <b_jonas> And I think cpressey has a language where functions are primarily macro-like, but the standard library has a macro to define a lambda function, which is a special kind of macro that always evaluates its arguments before doing anything else.
19:43:02 <b_jonas> (And doesn't access the unevaluated arguments in any way other than throught their evaluations.)
19:43:40 <arseniiv> Mathematica went even further and added Defer in ≈v8 which works thus: Defer[e] evaluates into unevaluated e and then you can evaluate it once more and that will evaluate e
19:43:41 <b_jonas> So I'd also like to know the name of this feature, or more examples for any of the above.
19:44:13 <b_jonas> arseniiv: ah, I know an example for that primitive!
19:44:49 <b_jonas> https://esolangs.org/wiki/SIMPLE_(preprocessor)
19:45:05 <b_jonas> Also there's TeX, in which normal functions that you define are macro-like, they don't evaluate their argument
19:45:58 <b_jonas> Of course if everything is macro-like then the question is, how do you actually call those macros
19:46:06 <arseniiv> b_jonas: I think languages with sufficiently lispy macros may have several different approaches to the second thing too, though the good way I think is to treat arguments as valid ASTs. Sequence-like splats were in some lispy languages too
19:46:15 <b_jonas> and TeX's answer is, the top level evaluates a macro call
19:47:08 -!- sprocklem has joined.
19:47:10 <arseniiv> Weyl algebras
19:47:11 <b_jonas> also SIMPLE is somewhat based on m4, which also has this defer feature
19:47:11 <zzo38> Well, expansion evaluates macro calls, and expansion can sometimes occur inside of other stuff too. Some tokens are unexpandable and are executed only after they reach the top level, though.
19:47:51 <b_jonas> zzo38: yes, inside romannumeral IIRC, which you can use as a kludge to initiate expansion in a place that doesn't normally expand anything
19:49:23 <b_jonas> frankly I don't really understand how TeX works, and I understand METAFONT to an even lesser degree. the latter has to do with TeX/METAFONT's localized tokens combined that interacts with the expansion and with multi-token names in a way that I don't understand
19:49:26 <zzo38> Well, \romannumeral will expand its argument, and is expandable, but it won't expand if expansion is suppressed.
19:49:58 <b_jonas> I am not a TeX hacker and really don't feel how TeX programming works
19:50:15 <zzo38> One way to expand something when expansion is normally suppressed is to use \expandafter, and you can also use \edef or \xdef to expand the definition of a macro at definition time, rather than later
19:50:34 <b_jonas> but there's some really interesting esoteric parts of TeX and METAFONT that might be worth for someone to study for furthering esoteric languages
19:51:44 <zzo38> In METAFONT, you can define a macro to evaluate its arguments either before expanding its definition or to don't do that; if the type of argument is expr then it will evaluate it and substitute a "capsule" where its name occurs inside of its body.
19:51:52 -!- bangyen has joined.
19:53:16 <arseniiv> that it is Knuth who devised TeX in all its esotericity is bothering
19:54:06 <b_jonas> arseniiv: why?
19:54:35 <b_jonas> I mean that's one of the defining features of Knuth
19:54:51 <arseniiv> hmm well he wanted to write software to be simple I hope
19:55:22 <arseniiv> <b_jonas> I mean that's one of the defining features of Knuth => is MIX as esoteric? I haven’t look at it in detail and assumed it’s pretty normal
19:55:33 <b_jonas> simple in what sense? he had a goal, to be able to typeset TAOCP vol 2 and further volumes. he made whatever he could for that.
19:56:11 <b_jonas> arseniiv: MIX isn't esoteric, but it's old, in the sense that TeX is old in that it doesn't have lambdas and lexically local variables because back then those weren't standard features of an interpreted language
19:56:28 <arseniiv> I see
19:56:44 <b_jonas> MMIX may be esoteric, and I argue for that it is in the wiki article, but it's stealth esoteric in that it does a good attempt at the esotericness being plausibly deniable,
19:57:13 <b_jonas> to make it seem like it could be a real machine, but make it subtly impractical to make sure it will never be a real machine on hardware, or at least not one that spreads.
19:57:43 -!- adu has joined.
19:58:23 <b_jonas> If MIX is esoteric in that sense, then I'm too old to notice that, I don't know much about archeological computer design, and don't recognize any way how it's not like what could be a real computer at that time.
19:58:46 <b_jonas> Maybe someone who designed computers back then and really understood what that entails would notice such details.
20:00:03 <zzo38> There are some features I don't know if it is, such as automatic character set conversion, and having the possibility of both binary and decimal versions of the same kind of computer, but maybe they are, I don't know
20:01:50 <b_jonas> zzo38: what do you mean by automatic character set conversion? any Hollerith card reader does that, because there are 12 holes but the reader encodes them in an Ebcdic byte that has less than 12 bits. MIX just uses an encoding to a character code that isn't used elsewhere.
20:02:11 <zzo38> Yes, but MIX doesn't use EBCDIC.
20:02:40 <b_jonas> it uses a similar encoding that is easy to encode or decode between Hollerith cards, at least on a decimal MIX
20:03:04 <b_jonas> for letters and numbers, bottom hole encodes the second digit, top hole if any encodes first digit
20:03:31 <b_jonas> it differs because EBCDIC is an eight-bit encoding and MIX has six-bit bytes
20:03:46 <b_jonas> and EBCDIC has a shitton of variants, like ASCII has a lot of ISO-646-* variants
20:04:22 <b_jonas> MIX character code probaly has variants with different printers printing different ones, and possibly for Hollerith cards too
20:04:49 <b_jonas> since some codes don't correspond to characters, or correspond to characters that not all card readers or card punchers or printers or teletypes can read/write
20:05:38 <b_jonas> that's why the two different version of what two of the three greek characters in the character sets are isn't necessarily a bug, there may be MIX printers with different characters of the corresponding head or place of the head
20:06:06 <b_jonas> just like how 8-bit computers have video cards with different accented characters in some places by different ROMs
20:06:46 <b_jonas> there are 8-bit BASIC-based personal computers where instead of @ they display an É or something
20:07:07 <b_jonas> and you have to write PRINTÉ instead of PRINT@ to write to a text file
20:07:32 <b_jonas> but the difference isn't in how BASIC works, just what character is shown on the monitor
20:11:48 <zzo38> But I think how some of the punctuations are encoded in MIX are not a standard card code, nor is the encoding of spaces matching codes of punch cards
20:12:38 <b_jonas> zzo38: is that even for punctuation that all MIX card readers are required to be able to read?
20:13:10 <zzo38> I do not remember, unfortunately. But, I suppose that is a valid point.
20:14:16 <b_jonas> Also, crap, my lip is swollen. If this worsense too much doesn't improve soon enough, I'll have to go to a weekend doctor or dentist, which always sucks.
20:14:30 <b_jonas> It started to swell during the afternoon.
20:18:54 <b_jonas> And the swelling is moving around my lip, counterclockwise when viewed from the font
20:18:57 <b_jonas> from the front
20:26:09 <arseniiv> oh
21:05:31 -!- TheLie has joined.
21:07:36 -!- arseniiv has quit (Ping timeout: 256 seconds).
21:15:48 -!- imode has joined.
21:20:49 -!- aaaaaa has joined.
21:23:52 <b_jonas> and if the swelling worsens a lot, then I'll need a night dentist/doctor, which is even worse
21:24:09 <b_jonas> but that's true for just about any condition that may need a weekend doctor
21:47:31 <b_jonas> Is there a M:tG card that gives both you and the opponent an advantageous effect, but one of you get to choose who gets which one?
21:48:37 <zzo38> I don't know, but, maybe, make up such a card.
22:00:35 <esowiki> [[Eval]] https://esolangs.org/w/index.php?diff=75805&oldid=73752 * Bangyen * (+99)
22:01:00 <esowiki> [[User:Bangyen]] https://esolangs.org/w/index.php?diff=75806&oldid=75722 * Bangyen * (+11)
22:13:18 <esowiki> [[Dotlang]] https://esolangs.org/w/index.php?diff=75807&oldid=75720 * Bangyen * (+64) /* Examples */
22:21:07 -!- rain1 has quit (Quit: Leaving).
22:40:49 -!- Lord_of_Life_ has joined.
22:43:25 -!- Lord_of_Life has quit (Ping timeout: 264 seconds).
22:43:37 -!- Lord_of_Life_ has changed nick to Lord_of_Life.
22:49:34 -!- sprocklem has quit (Ping timeout: 260 seconds).
22:49:53 -!- sprocklem has joined.
22:52:12 -!- mniip has quit (Ping timeout: 606 seconds).
23:02:40 -!- zzo38 has quit (Disconnected by services).
23:02:45 -!- zzo38 has joined.
23:04:25 -!- TheLie has quit (Remote host closed the connection).
23:37:51 <esowiki> [[*brainfuck]] M https://esolangs.org/w/index.php?diff=75808&oldid=34061 * PythonshellDebugwindow * (+4) knil
23:38:41 <esowiki> [[From INTERCAL to LOLCODE: The Esoteric Programming Story]] M https://esolangs.org/w/index.php?diff=75809&oldid=35160 * PythonshellDebugwindow * (+3) nolc
23:39:30 <esowiki> [[Keta]] M https://esolangs.org/w/index.php?diff=75810&oldid=69685 * PythonshellDebugwindow * (-193) stub template
23:40:11 <esowiki> [[Keg]] M https://esolangs.org/w/index.php?diff=75811&oldid=69692 * PythonshellDebugwindow * (+10)
23:40:48 <esowiki> [[Esolang:Sandbox]] M https://esolangs.org/w/index.php?diff=75812&oldid=75685 * PythonshellDebugwindow * (+40) /* yrotsiH */
23:41:03 <esowiki> [[Esolang:Sandbox]] M https://esolangs.org/w/index.php?diff=75813&oldid=75812 * PythonshellDebugwindow * (-1) fix/* =yrotsiH */
23:42:44 <esowiki> [[Jelly]] M https://esolangs.org/w/index.php?diff=75814&oldid=49881 * PythonshellDebugwindow * (+92) inter wiki
23:46:14 -!- imode has quit (Ping timeout: 240 seconds).
23:46:33 <shachaf> `"
23:46:35 <HackEso> 1/1:817) <elliott> i wrote a better version once but it was broken \ 77) <ais523> (still, whatever possessed anyone to invent the N-Gage?)
23:46:43 <shachaf> `5 w
23:46:46 <HackEso> 1/2:tc//Tc is the abbreviation for Technetium, an element so sophisticated that it does not exist naturally. \ j//J started out as a synonym for I, but then branched out into an array of other uses. \ internationale//You have been reported to the House Un-American Activities Committee. \ boredome//The Boredome is a dangerous place swarming with woodpeckers, dentists, and bookworms. \ stume//A stume cowears and goatears you. That is t
23:46:50 <shachaf> `n
23:46:51 <HackEso> 2/2:he main reason why the often look so ackward.
23:47:36 -!- imode has joined.
23:56:15 <esowiki> [[7Basic]] M https://esolangs.org/w/index.php?diff=75815&oldid=65115 * PythonshellDebugwindow * (+45) (Cat and bold and link and fix_hw)()
23:56:40 <esowiki> [[High Rise]] M https://esolangs.org/w/index.php?diff=75816&oldid=58740 * PythonshellDebugwindow * (+4) Link
23:57:52 <esowiki> [[6ix]] M https://esolangs.org/w/index.php?diff=75817&oldid=69810 * PythonshellDebugwindow * (+8) Link bold
23:58:47 <esowiki> [[5-logic]] M https://esolangs.org/w/index.php?diff=75818&oldid=20653 * PythonshellDebugwindow * (+27) Cat
←2020-07-09 2020-07-10 2020-07-11→ ↑2020 ↑all