←2019-04-26 2019-04-27 2019-04-28→ ↑2019 ↑all
00:39:08 -!- arseniiv has quit (Ping timeout: 255 seconds).
00:58:52 -!- sftp_ has joined.
00:59:29 -!- sftp has quit (Ping timeout: 246 seconds).
00:59:30 -!- sftp_ has changed nick to sftp.
01:06:45 -!- ais523 has joined.
01:08:07 <ais523> suppose I have a large set of strings of distinct letters, all of which contain the same letters (i.e. they're all anagrams of each other); each is split into tiers (with letters in the same tier being consecutive within the string), and letters within the same tier can be reordered freely
01:08:44 <ais523> the aim is to do this tier-shuffling to make as many of the strings identical as possible (i.e. to have the fewest number of distinct strings afterwards)
01:09:27 <ais523> examples: "(cab)(dfe)" and "(ba)(fdce)" can eah be rearranged into "(abc)(def)" and "(ab)(cdef)" respectively, so they can both be made the same
01:10:27 <ais523> I'm trying to find an algorithm for solving this problem; is it possible to have three such strings that can pairwise be made to match, but cannot collectively be made to match? if so, it's probably NP-complete, in which case I'm looking for an algorithm to find an approximate solution efficiently
01:10:51 <ais523> (this problem actually came up during esolang development, although I suspect it'd be ontopic here even if the context were different…)
01:11:13 <ais523> I have 5638 such strings, so doing this by hand would take way too long
01:12:51 <ais523> I'd be surprised if anyone knew it already, but was hoping that someone would see a way to work it out
01:13:33 <ais523> it's easy enough to see if two lists are compatible with each other (you can convert the "must come before" relations to directed graph edges and do a topological sort)
01:19:37 <ais523> oh, bleh, it's probably NP-complete anyway, I think you can probably encode the exact cover problem in it?
01:21:36 <ais523> maybe not, our primitives are "can be placed in the same set" rather than "belongs in this specific set", which may make enough of a difference to the meaning of n to change the complexity class
01:24:47 <ais523> is "decompose a graph into a minimal number of cliques" NP-complete? at least that sounds generic enough that someone might have worked on it already
01:25:25 <ais523> https://en.wikipedia.org/wiki/Clique_cover says it's NP-complete, bleh
01:25:38 <zzo38> I found that Lynx supports NNTP just fine; you can go to nntp://zzo38computer.org/ and it will list the newsgroups and messages, and allow posting new messages to them.
01:25:58 <ais523> so unless this specific instance happens to collapse into sub-NP special case, I'll need to find an approximate solution
01:36:30 <zemhill_______> web.le-basic-rush-2: points -8.98, score 12.80, rank 44/47
01:50:44 <ais523> I wonder who that is; they've (just about) gotten onto the leaderboard, at least
01:51:05 <ais523> it seems to win, when it wins, by getting so far inside the enemy decoy setup that they don't even notice they've been infiltrated
01:52:39 -!- oerjan has quit (Quit: Nite).
01:53:33 <ais523> the win against finnel is bizarre, though, it seems to be able to outrace finnel's complex offset clear with its very simple and straightforward clear /even though/ its decoys are inside finnel's offset!
01:53:40 <ais523> although it's incredibly close and quite fun to watch
01:54:10 <ais523> (that's on long sieve-polarity tapes, the other situations are more normal)
02:58:05 -!- FreeFull has quit.
03:54:21 -!- ais523 has quit (Quit: quit).
06:41:36 -!- Frater_EST has joined.
07:29:59 -!- Lord_of_Life has quit (Ping timeout: 255 seconds).
07:33:02 -!- Lord_of_Life has joined.
07:42:37 -!- Frater_EST has left.
08:07:47 -!- Cale has quit (Remote host closed the connection).
08:09:05 -!- Cale has joined.
08:15:28 -!- AnotherTest has joined.
09:14:59 -!- LKoen has joined.
09:30:42 -!- LKoen has quit (Remote host closed the connection).
09:33:52 -!- LKoen has joined.
10:44:42 <rain1> zzo38: this is cool
10:50:27 -!- LKoen has quit (Remote host closed the connection).
10:54:40 -!- LKoen has joined.
11:32:51 -!- FreeFull has joined.
12:11:23 <esowiki> [[Talk:Bitch]] M https://esolangs.org/w/index.php?diff=61374&oldid=61336 * A * (-5) Change odd subheading: it changes its opinion about Turing-completeness.
12:32:10 <esowiki> [[Esolang:Featured languages/Candidates]] M https://esolangs.org/w/index.php?diff=61375&oldid=61335 * A * (+55) /* List of candidates */
12:37:13 <esowiki> [[Talk:Bitch]] M https://esolangs.org/w/index.php?diff=61376&oldid=61374 * A * (+62) I always felt uncomfortable when I see this.
12:41:58 -!- LKoen has quit (Read error: Connection reset by peer).
12:48:13 -!- LKoen has joined.
12:52:47 -!- LKoen has quit (Ping timeout: 246 seconds).
13:32:13 <orin> I added the new square era name ㋿ to my font
13:34:17 <orin> (if your terminal font has been updated that will appear as 令和 crammed into one space)
13:36:23 <esowiki> [[RarVM]] M https://esolangs.org/w/index.php?diff=61378&oldid=61367 * Void * (+73) /* Jumping processes */
13:38:34 -!- user24 has joined.
13:38:45 <user24> Is there a definition of 'minor edit' somewhere?
13:39:15 <user24> Does it matter which one it is if it is my own article?
13:51:58 -!- LKoen has joined.
14:02:08 <esowiki> [[RarVM]] M https://esolangs.org/w/index.php?diff=61380&oldid=61378 * Void * (+89) /* Jumping processes */
14:17:28 <rain1> use your own judgement
14:21:24 -!- 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.”).
14:25:30 -!- grumble has quit (Quit: Well, would you look at the time. I've almost missed my ambiguous, non-existent appointment that I have scheduled just when I start to lose interest in my current conversation.).
14:30:13 -!- grumble has joined.
15:45:56 -!- Phantom_Hoover has joined.
16:15:04 -!- arseniiv has joined.
16:36:08 -!- user24 has quit (Quit: Leaving).
18:37:28 -!- APic has quit (Quit: Reconnecting).
18:37:36 -!- APic has joined.
18:53:18 -!- b_jonas has joined.
18:53:32 <b_jonas> ais523: can the strings have repeated letters?
18:53:38 <b_jonas> for the anagram question
18:54:25 <b_jonas> ais523: "I have 5638 such strings" => how long are they?
18:55:18 <b_jonas> ais523: "is "decompose a graph into a minimal number of cliques" NP-complete?" => yes, because that's the chromatic number of the complement of the graph
19:30:52 -!- Lord_of_Life_ has joined.
19:32:16 -!- Lord_of_Life has quit (Ping timeout: 246 seconds).
19:32:16 <esowiki> [[User:Total Vacuum]] https://esolangs.org/w/index.php?diff=61381&oldid=61333 * Total Vacuum * (+1)
19:33:21 -!- Lord_of_Life_ has changed nick to Lord_of_Life.
19:43:41 <esowiki> [[User:Total Vacuum]] https://esolangs.org/w/index.php?diff=61382&oldid=61381 * Total Vacuum * (+0)
19:43:53 <esowiki> [[User:Total Vacuum]] https://esolangs.org/w/index.php?diff=61383&oldid=61382 * Total Vacuum * (-1)
19:45:11 <esowiki> [[User:Total Vacuum]] https://esolangs.org/w/index.php?diff=61384&oldid=61383 * Total Vacuum * (+1)
19:45:15 <esowiki> [[Bfstack]] M https://esolangs.org/w/index.php?diff=61385&oldid=46428 * Coates * (-1) Fixed typo
19:45:16 -!- AnotherTest has quit (Ping timeout: 276 seconds).
19:55:25 <b_jonas> ais523: if you allow repeated letters, than (a)(ab)(a) can match both (ab)(aa) and (aa)(ab), but the latter two can't match
20:12:15 <esowiki> [[User:Total Vacuum]] https://esolangs.org/w/index.php?diff=61386&oldid=61384 * Total Vacuum * (+8)
20:15:54 -!- oerjan has joined.
20:19:59 <b_jonas> ais523: I have the feeling that this might be easier if I knew matroid theory
20:36:34 -!- b_jonas has quit (Quit: leaving).
20:38:03 -!- atslash has quit (Quit: This computer has gone to sleep).
21:28:07 -!- arseniiv has quit (Ping timeout: 246 seconds).
21:58:19 <zzo38> In order to implement x+=strlen(x) it should not be necessary to actually calculate the length of the string; you should just advance the pointer to the next zero byte. If the compiler knows what strlen() means then it should be able to optimize it, but it doesn't seem to do.
22:00:35 <fizzie> Does it do any better for x = strchr(x, '\0') then?
22:01:54 <zzo38> I don't know; I haven't tried. But they should presumably be the same thing, isn't it?
22:04:23 <fizzie> Yes, it should have the same effect.
22:04:51 <fizzie> In fact, the version of GCC I have translates `char *g(char *x) { return strchr(x, '\0'); }` into a call to `strlen`, which is kind of interesting.
22:05:36 <fizzie> http://ix.io/1HoR
22:07:34 <fizzie> I guess the logic there might be that strlen is a highly optimized implementation for locating a zero byte, while a generic strchr implementation can't be as good.
22:10:13 -!- Sgeo__ has quit (Read error: Connection reset by peer).
22:10:36 -!- Sgeo__ has joined.
22:13:56 <zzo38> Would something like REPNE SCASB work?
22:46:47 <oerjan> @metar ENVA
22:46:47 <lambdabot> ENVA 272220Z 09010KT CAVOK 14/01 Q1016 RMK WIND 670FT 12011KT
23:10:29 -!- Phantom_Hoover has quit (Read error: Connection reset by peer).
23:18:34 -!- oerjan has quit (Quit: Nite).
←2019-04-26 2019-04-27 2019-04-28→ ↑2019 ↑all