00:01:55 -!- FreeFull has quit.
00:10:23 -!- Frater_EST has left.
00:17:40 -!- LKoen has quit (Quit: “It’s only logical. First you learn to talk, then you learn to think. Too bad it’s not the other way round.”).
00:24:27 -!- arseniiv has quit (Ping timeout: 250 seconds).
01:10:16 -!- shinh has quit (Ping timeout: 240 seconds).
01:12:45 -!- shinh has joined.
01:49:59 -!- orvira has joined.
01:53:20 -!- Lord_of_Life_ has joined.
01:55:38 -!- Lord_of_Life has quit (Ping timeout: 268 seconds).
01:56:12 -!- Lord_of_Life_ has changed nick to Lord_of_Life.
02:46:17 -!- ineiros has quit (Ping timeout: 240 seconds).
02:47:16 -!- imode has joined.
02:47:49 -!- ineiros has joined.
02:59:54 -!- imode has quit (Ping timeout: 265 seconds).
03:33:11 -!- imode has joined.
03:34:20 -!- imode has quit (Client Quit).
04:40:04 -!- orvira has quit (Quit: leaving).
05:36:44 -!- ArthurStrong has quit (Quit: leaving).
07:41:11 <esowiki> [[Ttttt]] https://esolangs.org/w/index.php?diff=67860&oldid=67760 * Hex96 * (+49)
08:02:10 <esowiki> [[Talk:Tttt]] https://esolangs.org/w/index.php?diff=67861&oldid=67814 * Hex96 * (+12)
08:57:04 -!- b_jonas has quit (Quit: leaving).
10:43:18 -!- nico_nico has joined.
11:11:32 -!- nico_nico has quit (Quit: WeeChat 2.6).
11:34:17 -!- arseniiv has joined.
11:57:10 -!- izabera has joined.
11:58:53 <izabera> i have a graph with 142k nodes and 2.5mil edges
11:59:23 <izabera> and i want to compute the diameter
12:07:37 <izabera> how do i make this problem tractable?
12:08:14 <Taneb> Solve the problem of making yourself not want that?
12:08:32 <izabera> and cloud computing is cheap
12:09:16 <izabera> so i need a way to distrubute the floyd warshall algorithm across different machines
12:09:50 <izabera> in a smart way so that machines try to do as much as they can locally and don't always compete for shared resources
12:10:41 <Taneb> https://www3.nd.edu/~tweninge/pubs/PW_HPGM.pdf here is a paper
12:10:49 <Taneb> It might even be helpful
12:16:34 <myname> I don't know if I'd use floyd warshall to compute the diameter in this case at all
12:16:58 <myname> like, given the graph is simple, you can already calculate an upper bound of the diameter
12:21:10 <myname> that's a tough one I maybe think about later, but I just assumed that you can make assertions about cycle lengths which in turn will reduce the diameter
12:22:33 <myname> like, if you have at leas as much edges as you have nodes, you will have a cycle of at least length 3 reducing the diameter from a maximum of n to a maximum of n-1
12:26:13 <izabera> i think i can do dijkstra from each node to every other node
12:26:36 <izabera> it's trivially parallelisable by just having a local copy of the adjacency matrix on each machine
12:30:20 <myname> is this really an advantage over a normal floyd warshall?
12:31:27 <izabera> i don't know how to split it across machines
12:31:59 <myname> you will need to have at least n^3/(n log n) processes for that to be faster
12:32:39 <izabera> with floyd warshall you'd need to write to the shared cache all the time
12:32:46 <izabera> how do you parallelise that?
12:35:04 <myname> not sure, that's why I wouldn't use that :D
12:35:26 <izabera> i just want an algorithm that's reasonably fast and that can be split
12:40:19 <myname> yeah, but I would assume there exists a reasonably parallelizable algorithm to calculate the diameter of a graph that does not rely on calculating each distance and finding the maximum in those
12:41:42 <myname> like, if you can give an upper bound on the diameter (which I believe you can), you may be able to parallelise the search based on clusters of size g(max diameter)
12:45:04 <izabera> i have a strong feeling that the diameter is like 7
12:46:37 <izabera> altho i'm not sure i understand how your idea works
12:48:12 <myname> I am thinking about generating a transitive hull and check for completeness of the resulting graph
13:02:04 <fizzie> Here's another paper: https://www.ntu.edu.sg/home/arijit.khan/Papers/vertex_centric_edbt17.pdf
13:03:01 <fizzie> I don't know if it's any good, but it's got a "vertex-centric" algorithm for a diameter, and there are things to parallelize algorithms like that, like our "Pregel".
13:03:53 <fizzie> (TBH, it doesn't look particularly efficient, more a toy example.)
13:11:15 <izabera> fizzie: https://pregel.it/en/
13:12:34 <izabera> https://blog.acolyer.org/2015/05/26/pregel-a-system-for-large-scale-graph-processing/
13:12:43 <izabera> didn't know that you're at google
13:36:20 <Taneb> izabera: did you look at the PDF I linked
13:39:53 <fizzie> I don't go around advertising it, though it's not a secret either.
13:42:22 <izabera> Taneb: i'm dumb and it's complicated
13:56:07 -!- Lord_of_Life_ has joined.
13:56:31 -!- Lord_of_Life has quit (Ping timeout: 268 seconds).
13:57:29 -!- Lord_of_Life_ has changed nick to Lord_of_Life.
14:18:56 -!- kritixilithos has joined.
15:22:49 <LBPHacker> (ignore me, my client is acting up)
15:24:06 -!- wib_jonas has joined.
15:25:58 <wib_jonas> izabera: re computing diameter, that looks borderline. do you have enough RAM to allocate a square matrix whose width and height is the number of points, or at least a triangular half of it? the elements themselves can be small, probably single bytes, possibly two bytes if the diameter is large.
15:26:16 <wib_jonas> if you do have enough RAM for that, then use Floyd's algorithm to compute the pairwise distances
15:27:28 <wib_jonas> that's not an impossibly large amount of memory these days, you can probably borrow some time on a machine with that much RAM
15:30:21 <myname> is computing a single transitivity step for a graph in matrix form that hard?
15:32:11 <wib_jonas> if you suspect that the diameter is small, then you can optimize it well, you don't need a full Floyd
15:32:30 <wib_jonas> it still won't be fast, but it will be much faster and easier than trying to figure out some distributed solution
15:34:19 <wib_jonas> if you don't have enough RAM, then yes, run an individual BFS from each node, to make sure that you can reach all nodes of the graph in few steps
15:34:48 <wib_jonas> in fact, that's probably faster than anything with a full matrix, because your graph is sparse enough
15:35:02 <wib_jonas> so ignore my previous idea about a large matrix and floyd's algorithm
15:35:26 <wib_jonas> you said your graph is very sparse, so just do a BFS from each individual node to find the distance of the farthest node from there
15:37:18 <wib_jonas> I suggest that you implement the DFS using two arrays with one bit each for each node, to know which one you've visited in the previous step and the current step, and passes of reading through the edge list in sequence
15:37:55 <wib_jonas> I suggest sorting the edge list for some speedup
15:39:10 <wib_jonas> izabera: ^ that would work reasonably fast for a graph of small diameter, because you're reading the edge list sequentially, and you only need to access 284000 bits i.e. 35 kilobytes random access
15:40:39 <wib_jonas> if you double the edge list, making it an arc list (storing each edge in both directions) and sort it by destination node, the you only need random access to one of the bit arrays and sequential access to the other bit array, so the array with random access just fits in the L1 cache
15:42:53 <wib_jonas> this is assuming that the graph is confidental or you want to solve it yourself; otherwise just publish the graph and offer money to people for computing the diameter
15:45:20 <wib_jonas> require solvers to give not only the diameter, but the indexes of two nodes that are that far apart, so you can verify easily
15:47:00 <FireFly> ah yes, the O(incentive) approach
15:49:36 <myname> wib_jonas: that would not suffice
15:50:06 <myname> i can easily claim the diameter being 1 and give you two nodes with a distance of 1
15:53:08 <myname> you would need to have at least one honest participant
15:53:24 <wib_jonas> myname: it doesn't suffice, but your solution doesn't work, because izabera can find the submission that claims the highest diameter, and run a single breadth-first search from one of the nodes that it claims to find the distance of the two nodes that it claims, and if that's 7 then that proves your submission incorrect
15:53:54 <wib_jonas> the failure case is that everyone claims a diameter that is lower than the actual one
15:54:08 <wib_jonas> or that izabera is DOSed by too many incorrect submissions
15:55:35 <wib_jonas> myname: also the spec said "i have a graph with 142k nodes and 2.5mil edges", that's not a complete graph so the diameter can't be 1
15:56:13 <myname> well yeah, but i should be able to find some nodes with distance 3 pretty easily
15:57:09 <myname> oh, couldn't you just contract parts of the graph?
15:58:36 <myname> like, if you have a path of length n > 1, you could just make that into a path of length 1 with a weight of n
15:59:08 <myname> if you do end on a complete graph, you just need to find the biggest weight
16:00:00 <myname> or you could just split the graph in half, substitute the missing half with a new node and try some clever merging of paths, that run through that
16:01:20 <myname> (paths meaning longest distance travels between two nodes in the later case)
16:25:59 -!- nico_nico has joined.
16:34:08 -!- nico_nico has quit (Quit: WeeChat 2.6).
16:37:10 <esowiki> [[Dd]] https://esolangs.org/w/index.php?diff=67862&oldid=56366 * Dart * (+4206) Stretching the essay to the 500 word requirement like:
16:49:23 <int-e> wtf is this "The download cannot be saved because an unknown error occurred."
16:51:17 <int-e> Oh, it's me, more specifically umatrix interfering in a way I have not identified before--it categorizes the request as "other" and blocks it. Fine.
16:58:08 -!- zzo38 has quit (Ping timeout: 246 seconds).
17:01:52 -!- wib_jonas has quit (Remote host closed the connection).
17:35:57 <esowiki> [[Truth-machine]] https://esolangs.org/w/index.php?diff=67863&oldid=67519 * Hex96 * (+54)
17:38:57 <esowiki> [[Dd]] M https://esolangs.org/w/index.php?diff=67864&oldid=67862 * Dart * (+4)
17:59:50 -!- nico_nico has joined.
18:03:00 -!- FreeFull has joined.
18:26:58 -!- mroman has joined.
18:27:41 <mroman> huh. long time no see I guess
18:29:21 -!- b_jonas has joined.
18:29:41 <mroman> https://pastebin.com/EcuX91Hk <- and I'm already back at doing useless things.
18:32:55 -!- kritixilithos has quit (Quit: quit).
18:36:28 <esowiki> [[Talk:Tttt]] https://esolangs.org/w/index.php?diff=67865&oldid=67861 * Hex96 * (+174) /* Other Programs */
18:51:46 -!- LKoen has joined.
19:01:46 -!- LKoen has quit (Remote host closed the connection).
19:01:58 -!- LKoen has joined.
19:10:12 -!- nico_nico has quit (Quit: WeeChat 2.6).
19:27:43 -!- Boko_ggeahbf has joined.
19:28:12 -!- Boko_ggeahbf has quit (Read error: Connection reset by peer).
19:59:15 <esowiki> [[User:Hex96]] https://esolangs.org/w/index.php?diff=67866&oldid=67774 * Hex96 * (+41)
19:59:40 <esowiki> [[User:Hex96]] https://esolangs.org/w/index.php?diff=67867&oldid=67866 * Hex96 * (+4) /* List of esolangs */
20:01:48 -!- ArthurStrong has joined.
20:02:40 <esowiki> [[4]] https://esolangs.org/w/index.php?diff=67868&oldid=65112 * Hex96 * (+151) /* Hello, World! */
20:03:15 <esowiki> [[4]] https://esolangs.org/w/index.php?diff=67869&oldid=67868 * Hex96 * (-23) /* Hello, World! */
20:04:11 <esowiki> [[4]] https://esolangs.org/w/index.php?diff=67870&oldid=67869 * Hex96 * (+80) /* Cat program */
20:05:29 <HackEso> `4 <cmd> is equivalent to `5 <cmd>, except that it only repeats 4 times. Useful when you've already run a command forgetting to use `5.
20:12:25 <b_jonas> can't people invent normal names for these brainfuck-equivalents?
20:13:07 <b_jonas> ok, I'm not sure I'm allowed to complain, given how I name things
21:01:37 -!- mroman has quit (Remote host closed the connection).
21:02:37 -!- djhoulihan has quit (Ping timeout: 240 seconds).
21:09:43 -!- MDude has joined.
22:31:12 <int-e> b_jonas: I've solved the AoC problems so far over the past 6 hours.
22:31:53 <shachaf> Today's AoC challenge: Prove that every vector space has a basis.
22:32:04 <int-e> KISS is such a powerful principle.
22:32:23 <fizzie> I have no idea how long I've spent, because the timing starts from what's 5am here.
22:32:59 <fizzie> Guess I could extrapolate from the delta between part 1 and part 2 though.
22:33:07 <int-e> You can still keep track of the time *you* spend.
22:33:15 <fizzie> Yes, but not retroactively. :)
22:33:21 <fizzie> Well, maybe from file timestamps.
22:33:41 <int-e> I'm extrapolating from part 1 of the 1st day ;)
22:34:00 <int-e> I'll lose track if I continue doing this.
22:34:10 <int-e> The leaderboard scoring is atrocious, btw.
22:34:44 <fizzie> I'm kind of happy it is, because otherwise I'd probably start caring about it.
22:35:00 <fizzie> (In fact I did today's right when it opened, because happened to be awake.)
22:35:58 <fizzie> Fortunately it's fun enough to just write those things.
22:39:43 <int-e> for the later problems I could reconstruct things reasonably well by the file stamps of the inputs
22:40:34 <int-e> Hmm, or maybe not. I have not been consistent about downloading the input when I start.
22:40:47 <int-e> Oh well, who really cares.
22:42:02 <b_jonas> shachaf: https://www.xkcd.com/804/ I told you not to take the axiom of choice
22:45:54 <int-e> meh, perhaps somebody cares: wc counts of what I've produced: http://paste.debian.net/1120577/
22:50:10 <fizzie> I think my Python's been more verbose.
22:51:10 <fizzie> Well, same order of magnitude.
22:53:11 <fizzie> (Flatter directory structure though.)
22:53:53 <int-e> I expected slightly harder problem (so more exploration)
22:54:21 <int-e> It's still nice not having to rename the 'input' files, but it's a minor thing.
22:54:37 <int-e> Also I broke the Intcode API once so having copies is actually healthy.
22:55:10 <fizzie> I'm sharing, that's why I have test.py (which runs all the day*.py and compares their outputs to a golden copy).
22:55:23 <fizzie> Although from the "your Intcode computer is now complete", maybe there won't be any more.
22:56:12 <fizzie> I'm pretty sure I was doing these some previous year as well, but no idea where I've stashed the solutions.
22:56:37 <int-e> yeah, the 2019 is a bit silly :)
22:57:38 <fizzie> To be fair, 'aoc2019' is the only thing in my '~/src/puzzles'. Not because there haven't been any puzzles, I just think I've used ~/tmp, ~/src/misc, or whatever.
23:20:41 -!- Sgeo_ has quit (Read error: Connection reset by peer).
23:26:01 -!- LKoen has quit (Quit: “It’s only logical. First you learn to talk, then you learn to think. Too bad it’s not the other way round.”).
23:26:05 -!- Sgeo has joined.
23:27:38 <arseniiv> https://www.xkcd.com/2235 haha
23:54:31 <arseniiv> luckily AoC can be googled by “aoc of code”; just "AoC" in quotes gives bizarre results, apparently lacking respect for mixed case in queries
23:56:21 <int-e> quick, we need an axiom of code