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 [[Ttttt]] https://esolangs.org/w/index.php?diff=67860&oldid=67760 * Hex96 * (+49) 08:02:10 [[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:57:14 hi 11:57:16 got a problem 11:58:53 i have a graph with 142k nodes and 2.5mil edges 11:59:23 and i want to compute the diameter 12:07:37 how do i make this problem tractable? 12:08:14 Solve the problem of making yourself not want that? 12:08:22 well i really want that 12:08:32 and cloud computing is cheap 12:09:16 so i need a way to distrubute the floyd warshall algorithm across different machines 12:09:50 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 https://www3.nd.edu/~tweninge/pubs/PW_HPGM.pdf here is a paper 12:10:49 It might even be helpful 12:16:34 I don't know if I'd use floyd warshall to compute the diameter in this case at all 12:16:58 like, given the graph is simple, you can already calculate an upper bound of the diameter 12:17:32 how? 12:21:10 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 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 i think i can do dijkstra from each node to every other node 12:26:36 it's trivially parallelisable by just having a local copy of the adjacency matrix on each machine 12:28:22 is this stupid? 12:30:20 is this really an advantage over a normal floyd warshall? 12:31:27 i don't know how to split it across machines 12:31:38 well 12:31:42 ok i'm dumb 12:31:44 no 12:31:59 you will need to have at least n^3/(n log n) processes for that to be faster 12:32:39 with floyd warshall you'd need to write to the shared cache all the time 12:32:46 how do you parallelise that? 12:35:04 not sure, that's why I wouldn't use that :D 12:35:26 i just want an algorithm that's reasonably fast and that can be split 12:40:19 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 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 i have a strong feeling that the diameter is like 7 12:45:14 but i'm not sure 12:46:37 altho i'm not sure i understand how your idea works 12:48:12 I am thinking about generating a transitive hull and check for completeness of the resulting graph 12:48:41 that might work 13:02:04 Here's another paper: https://www.ntu.edu.sg/home/arijit.khan/Papers/vertex_centric_edbt17.pdf 13:03:01 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 (TBH, it doesn't look particularly efficient, more a toy example.) 13:11:15 fizzie: https://pregel.it/en/ 13:11:18 looks delicious 13:12:34 https://blog.acolyer.org/2015/05/26/pregel-a-system-for-large-scale-graph-processing/ 13:12:38 seems like a google thing 13:12:43 didn't know that you're at google 13:36:20 izabera: did you look at the PDF I linked 13:39:53 I don't go around advertising it, though it's not a secret either. 13:42:22 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:19 lol wut 15:22:49 (ignore me, my client is acting up) 15:24:06 -!- wib_jonas has joined. 15:25:58 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 if you do have enough RAM for that, then use Floyd's algorithm to compute the pairwise distances 15:27:28 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:28:00 izabera: are there edge weights? 15:30:21 is computing a single transitivity step for a graph in matrix form that hard? 15:32:11 if you suspect that the diameter is small, then you can optimize it well, you don't need a full Floyd 15:32:30 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 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 in fact, that's probably faster than anything with a full matrix, because your graph is sparse enough 15:35:02 so ignore my previous idea about a large matrix and floyd's algorithm 15:35:26 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 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 I suggest sorting the edge list for some speedup 15:39:10 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 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:40:50 so that's what I'd recommend 15:40:55 hth 15:42:53 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 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 ah yes, the O(incentive) approach 15:49:36 wib_jonas: that would not suffice 15:50:06 i can easily claim the diameter being 1 and give you two nodes with a distance of 1 15:53:08 you would need to have at least one honest participant 15:53:24 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 the failure case is that everyone claims a diameter that is lower than the actual one 15:54:08 or that izabera is DOSed by too many incorrect submissions 15:55:35 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 well yeah, but i should be able to find some nodes with distance 3 pretty easily 15:57:09 oh, couldn't you just contract parts of the graph? 15:58:36 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 if you do end on a complete graph, you just need to find the biggest weight 16:00:00 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 (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 [[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 wtf is this "The download cannot be saved because an unknown error occurred." 16:51:17 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 [[Truth-machine]] https://esolangs.org/w/index.php?diff=67863&oldid=67519 * Hex96 * (+54) 17:38:57 [[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 huh. long time no see I guess 18:29:21 -!- b_jonas has joined. 18:29:41 https://pastebin.com/EcuX91Hk <- and I'm already back at doing useless things. 18:32:55 -!- kritixilithos has quit (Quit: quit). 18:36:28 [[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 [[User:Hex96]] https://esolangs.org/w/index.php?diff=67866&oldid=67774 * Hex96 * (+41) 19:59:40 [[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 [[4]] https://esolangs.org/w/index.php?diff=67868&oldid=65112 * Hex96 * (+151) /* Hello, World! */ 20:03:15 [[4]] https://esolangs.org/w/index.php?diff=67869&oldid=67868 * Hex96 * (-23) /* Hello, World! */ 20:04:11 [[4]] https://esolangs.org/w/index.php?diff=67870&oldid=67869 * Hex96 * (+80) /* Cat program */ 20:05:27 `? 4 20:05:29 ​`4 is equivalent to `5 , except that it only repeats 4 times. Useful when you've already run a command forgetting to use `5. 20:12:25 can't people invent normal names for these brainfuck-equivalents? 20:13:07 ok, I'm not sure I'm allowed to complain, given how I name things 20:36:58 b_jonas: how? 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 b_jonas: I've solved the AoC problems so far over the past 6 hours. 22:31:53 Today's AoC challenge: Prove that every vector space has a basis. 22:32:04 KISS is such a powerful principle. 22:32:23 I have no idea how long I've spent, because the timing starts from what's 5am here. 22:32:59 Guess I could extrapolate from the delta between part 1 and part 2 though. 22:33:07 You can still keep track of the time *you* spend. 22:33:15 Yes, but not retroactively. :) 22:33:19 Right. 22:33:21 Well, maybe from file timestamps. 22:33:41 I'm extrapolating from part 1 of the 1st day ;) 22:34:00 I'll lose track if I continue doing this. 22:34:10 The leaderboard scoring is atrocious, btw. 22:34:44 I'm kind of happy it is, because otherwise I'd probably start caring about it. 22:35:00 (In fact I did today's right when it opened, because happened to be awake.) 22:35:58 Fortunately it's fun enough to just write those things. 22:39:43 for the later problems I could reconstruct things reasonably well by the file stamps of the inputs 22:40:34 Hmm, or maybe not. I have not been consistent about downloading the input when I start. 22:40:47 Oh well, who really cares. 22:42:02 shachaf: https://www.xkcd.com/804/ I told you not to take the axiom of choice 22:45:54 meh, perhaps somebody cares: wc counts of what I've produced: http://paste.debian.net/1120577/ 22:50:10 I think my Python's been more verbose. 22:50:32 http://ix.io/245v 22:51:10 Well, same order of magnitude. 22:53:11 (Flatter directory structure though.) 22:53:53 I expected slightly harder problem (so more exploration) 22:54:21 It's still nice not having to rename the 'input' files, but it's a minor thing. 22:54:37 Also I broke the Intcode API once so having copies is actually healthy. 22:55:10 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 Although from the "your Intcode computer is now complete", maybe there won't be any more. 22:56:12 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 yeah, the 2019 is a bit silly :) 22:57:38 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 https://www.xkcd.com/2235 haha 23:54:31 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 quick, we need an axiom of code