←2018-07-06 2018-07-07 2018-07-08→ ↑2018 ↑all
00:09:04 -!- Phantom__Hoover has quit (Read error: Connection reset by peer).
00:09:48 -!- Naergon has joined.
00:15:28 -!- S_Gautam has joined.
00:48:23 -!- oerjan has joined.
01:08:53 -!- Warrigal has joined.
01:09:29 -!- contrapumpkin has joined.
01:16:13 -!- imode has joined.
01:27:44 <Warrigal> So I've got this decision problem.
01:29:38 <Warrigal> There are F types of fruits and P people. I have f_1 fruits of the first kind, f_2 fruits of the second kind, ..., f_F fruits of the F'th kind. I need to give p_1 fruits to the first person, ..., p_P fruits to the P'th person.
01:30:17 <Warrigal> However, each person will only accept fruits of particular kinds.
01:31:05 <Warrigal> There's an FxP matrix of booleans which indicates whether or not each person will accept each kind of fruit.
01:31:28 <Warrigal> The question is, can I give each person the required number of fruits, without giving any person a kind of fruit that they will not accept?
01:31:46 <Warrigal> Now, this sounds like an NP-complete problem. Is it?
01:36:36 <Warrigal> Pretty sure it's NP-hard because I can reduce set-packing to it: https://en.wikipedia.org/wiki/Set_packing
01:36:46 <Warrigal> "Suppose one has a finite set S and a list of subsets of S. Then, the set packing problem asks if some k subsets in the list are pairwise disjoint (in other words, no two of them share an element)."
01:38:07 <Warrigal> Okay, so I set F = |S| + 1. There is one type of fruit for each element of S, plus one more fruit, designated "otherwise".
01:38:49 <Warrigal> For each element of the list of subsets of S, there's a person who demands exactly one fruit, and that fruit is permitted to be either one of the fruits from the subset of S, or the "otherwise" fruit.
01:39:23 <Warrigal> There is also one person who demands enough "otherwise" fruits that k other people must receive fruits that are not "otherwise".
01:40:05 <Warrigal> No, scratch that last person.
01:40:16 <Warrigal> There are only the people who demand exactly one fruit.
01:40:27 <Warrigal> I'm given exactly enough "otherwise" fruits that I can give them to all but k people.
01:40:35 <Warrigal> I'm also given exactly one of every other type of fruit.
01:40:36 <Warrigal> Done.
01:42:46 <Warrigal> So, that proves that it's NP-hard.
01:43:45 <Warrigal> Is it in NP?
01:48:46 <oerjan> Warrigal: if the p_i are given in unary, then yes, since the solution is polynomial size in the input data
01:48:51 <oerjan> otherwise, i'm not sure.
01:51:29 <Warrigal> I'm assuming that all the numbers are given in binary or decimal.
01:51:49 <oerjan> hm wait, it works even without
01:52:02 <shachaf> isn't this an integer linear programming problem anyway
01:52:11 <oerjan> the list of all assignments just tells how many of each fruit to each person
01:52:44 <oerjan> and that can be done in binary/decimal.
01:53:06 <oerjan> so yeah, NP.
01:54:33 -!- mrrmx has quit (Quit: Leaving).
02:22:28 <Warrigal> Yeah, it's probably obviously integer linear programming.
02:22:37 <Warrigal> Here's another way of stating it.
02:23:14 <Warrigal> You've got a grid of squares. Some of the squares have pencil marks in them. Each row and each column is labeled with a number.
02:23:35 <Warrigal> Can you erase pencil marks such that each row contains *at least* the designated number of marks, and each column contains *at most* the designated number of marks?
02:25:40 <shachaf> Oh! Of course the (universal) dual of Kleene star is complement(star(complement(L))). I don't know why I didn't think of that.
02:25:46 <shachaf> But, hmm, can you even define concatenation of universal finite automata?
02:28:18 -!- Bowserinator_ has changed nick to Bowserinator.
02:30:36 -!- Warrigal has changed nick to tswett.
02:36:38 <esowiki> [[MediaWiki talk:Common.js]] N https://esolangs.org/w/index.php?oldid=56459 * Oerjan * (+472) That doesn't work for the cache problems
02:37:35 <esowiki> [[MediaWiki talk:Common.js]] M https://esolangs.org/w/index.php?diff=56460&oldid=56459 * Oerjan * (+1) punct.
02:40:19 <oerjan> ^bf +[-->-[>>+>-----<<]<--<---]>-.>>>+.>>..+++[.>]<<<<.+++.------.<<-.
02:40:19 <fungot> Hello, World
02:54:03 <oerjan> <imode> what's more general than a hypergraph? <-- supercalifragilisticexpialigraph hth
03:01:59 <shachaf> Here's the paper on dual concatenation: https://www.sciencedirect.com/science/article/pii/S0304397505004056
03:02:06 <shachaf> (And dual regular expressions in general.)
03:04:59 -!- S_Gautam has quit (Quit: Connection closed for inactivity).
03:44:01 -!- moei has quit (Quit: Leaving...).
04:07:07 <imode> oerjan: it did help. :P
04:07:31 <esowiki> [[Esolang:Introduce yourself]] https://esolangs.org/w/index.php?diff=56461&oldid=56434 * Yhara * (+65)
04:10:01 -!- doesthiswork has quit (Quit: Leaving.).
04:13:39 -!- doesthiswork has joined.
04:50:45 -!- moei has joined.
05:45:41 -!- Sgeo_ has joined.
05:46:09 -!- Sgeo has quit (Ping timeout: 248 seconds).
05:51:56 -!- rodgort has quit (Quit: Leaving).
06:00:45 -!- doesthiswork has quit (Quit: Leaving.).
06:03:49 -!- rodgort has joined.
06:15:51 -!- imode has quit (Ping timeout: 268 seconds).
07:03:43 -!- XorSwap has quit (Ping timeout: 256 seconds).
07:15:10 <esowiki> [[Truth-machine]] https://esolangs.org/w/index.php?diff=56462&oldid=56436 * A * (-14) /* brainfuck */
07:17:45 <esowiki> [[Truth-machine]] https://esolangs.org/w/index.php?diff=56463&oldid=56462 * Oerjan * (+14) Undo revision 56462 by [[Special:Contributions/A|A]] ([[User talk:A|talk]]) (See previous edit summaries)
07:21:26 <esowiki> [[Shorten your Brainfuck code]] https://esolangs.org/w/index.php?diff=56464&oldid=56438 * A * (+28) /* Really? A shorter one */
07:22:54 <esowiki> [[User talk:A]] https://esolangs.org/w/index.php?diff=56465&oldid=56313 * Oerjan * (+406) /* Your brainfuck truth-machine */ new section
07:25:03 <esowiki> [[Shorten your Brainfuck code]] https://esolangs.org/w/index.php?diff=56466&oldid=56464 * A * (+65) /* Really? A shorter one */
07:29:02 <esowiki> [[Truth-machine]] https://esolangs.org/w/index.php?diff=56467&oldid=56463 * A * (+109) /* brainfuck */
07:30:13 <oerjan> ^bf ,.[->+>+<<]++++++[->--------<]>[>[.]]!0
07:30:14 <fungot> 0
07:30:16 <oerjan> ^bf ,.[->+>+<<]++++++[->--------<]>[>[.]]!1
07:30:16 <fungot> 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 ...
07:30:19 <oerjan> checks out
07:31:20 <esowiki> [[Truth-machine]] https://esolangs.org/w/index.php?diff=56468&oldid=56467 * A * (-3) /* brainfuck */
07:32:18 <esowiki> [[Truth-machine]] https://esolangs.org/w/index.php?diff=56469&oldid=56468 * A * (-106) /* brainfuck */
07:34:51 <esowiki> [[User talk:A]] https://esolangs.org/w/index.php?diff=56470&oldid=56465 * A * (+149) /* Your brainfuck truth-machine */
07:43:45 <esowiki> [[User talk:A]] https://esolangs.org/w/index.php?diff=56471&oldid=56470 * A * (+144) /* Your brainfuck truth-machine */
07:47:32 <esowiki> [[User talk:A]] https://esolangs.org/w/index.php?diff=56472&oldid=56471 * A * (-69) /* Your brainfuck truth-machine */
07:50:24 <esowiki> [[User talk:A]] https://esolangs.org/w/index.php?diff=56473&oldid=56472 * A * (+5) /* Your brainfuck truth-machine */
07:54:56 <esowiki> [[Shorten your Brainfuck code]] https://esolangs.org/w/index.php?diff=56474&oldid=56466 * A * (+123)
07:54:56 <esowiki> [[User talk:A]] https://esolangs.org/w/index.php?diff=56475&oldid=56473 * Oerjan * (+207) /* Your brainfuck truth-machine */
07:59:26 <esowiki> [[User talk:A]] https://esolangs.org/w/index.php?diff=56476&oldid=56475 * A * (+175) /* Your brainfuck truth-machine */
08:02:16 <oerjan> ^bf ,.[->+>+<<]++++++[->--------<]>[>[.]]
08:02:22 <oerjan> ^bf ,.[->+>+<<]++++++[->--------<]>[>[.]]!0
08:02:22 <fungot> 0
08:05:13 <esowiki> [[User talk:A]] https://esolangs.org/w/index.php?diff=56477&oldid=56476 * Oerjan * (+163) Yes
08:10:40 <esowiki> [[Truth-machine]] https://esolangs.org/w/index.php?diff=56478&oldid=56469 * A * (+103) /* brainfuck */
09:34:25 -!- Phantom_Hoover has joined.
09:41:35 -!- oerjan has quit (Quit: Nite).
10:05:23 -!- AnotherTest has joined.
10:19:15 -!- erkin has joined.
10:26:29 -!- SopaXorzTaker has joined.
10:48:15 -!- erkin has quit (Quit: Ouch! Got SIGIRL, dying...).
11:33:33 -!- erkin has joined.
11:33:50 -!- erkin has quit (Remote host closed the connection).
11:33:56 -!- sebbu2 has joined.
11:35:24 -!- sebbu has quit (Ping timeout: 256 seconds).
12:14:45 -!- S_Gautam has joined.
12:33:49 -!- erkin has joined.
13:00:31 -!- doesthiswork has joined.
14:44:25 -!- S_Gautam has quit (Quit: Connection closed for inactivity).
15:25:27 <fizzie> @metar EGLL
15:25:27 <lambdabot> EGLL 071520Z AUTO 30008KT 250V020 9999 NCD 30/12 Q1023 NOSIG
15:25:32 <fizzie> E2HOT
15:32:50 -!- variable has quit (Quit: /dev/null is full).
15:41:29 -!- variable has joined.
15:50:20 -!- trout has joined.
15:52:27 -!- variable has quit (Ping timeout: 240 seconds).
16:20:10 -!- impomatic has quit (Ping timeout: 264 seconds).
16:22:11 -!- Gregor has quit (Ping timeout: 276 seconds).
16:27:38 -!- Gregor has joined.
17:09:53 <int-e> @metar BHX
17:09:59 <int-e> hmm that doesn't work
17:10:15 <int-e> @metar egbb
17:10:15 <lambdabot> EGBB 071650Z 32008KT 280V010 CAVOK 28/09 Q1024
17:13:52 -!- mrrmx has joined.
17:18:32 -!- Phantom__Hoover has joined.
17:22:12 -!- Phantom_Hoover has quit (Ping timeout: 256 seconds).
17:42:46 -!- sebbu2 has changed nick to sebbu.
17:55:58 -!- trout has quit (Quit: /dev/null is full).
18:09:36 -!- variable has joined.
18:22:58 <fizzie> `iata BHX
18:22:59 <HackEso> Birmingham (BHX, EGBB)
18:29:43 -!- laerling has joined.
18:31:44 <Taneb> @metar EGSC
18:31:45 <lambdabot> EGSC 071650Z 36006KT 300V090 CAVOK 28/10 Q1023
18:37:14 -!- laerling has quit (Quit: Leaving).
18:39:19 -!- XorSwap has joined.
18:41:04 <esowiki> [[User:Language]] https://esolangs.org/w/index.php?diff=56479&oldid=56398 * HereToAnnoy * (+4159) Language update + examples
18:42:12 -!- trout has joined.
18:45:47 -!- variable has quit (Ping timeout: 265 seconds).
18:54:52 <Taneb> It's far too warm...
18:56:38 <fizzie> `icao EGSC
18:56:39 <HackEso> Cambridge (CBG, EGSC)
18:57:47 <Taneb> Somehow, Cambridge has an international airport with zero scheduled flights
19:13:41 -!- variable has joined.
19:16:46 -!- trout has quit (Ping timeout: 260 seconds).
19:18:11 -!- SopaXorzTaker has quit (Remote host closed the connection).
19:20:20 <esowiki> [[User:Language]] M https://esolangs.org/w/index.php?diff=56480&oldid=56479 * HereToAnnoy * (-328) edits to a language about a wiki
19:45:41 -!- trout has joined.
19:46:52 -!- Phantom__Hoover has quit (Ping timeout: 245 seconds).
19:48:35 -!- variable has quit (Ping timeout: 255 seconds).
20:16:34 -!- variable has joined.
20:19:46 -!- trout has quit (Ping timeout: 260 seconds).
20:22:34 -!- aloril_ has quit (Ping timeout: 264 seconds).
20:28:12 -!- Phantom__Hoover has joined.
20:33:15 -!- aloril_ has joined.
20:47:53 -!- trout has joined.
20:52:02 -!- variable has quit (Ping timeout: 276 seconds).
21:19:35 -!- variable has joined.
21:22:17 -!- trout has quit (Ping timeout: 245 seconds).
21:51:39 -!- trout has joined.
21:53:48 -!- variable has quit (Ping timeout: 265 seconds).
22:20:51 -!- AnotherTest has quit (Ping timeout: 240 seconds).
22:22:41 -!- variable has joined.
22:24:23 -!- Cale has quit (Remote host closed the connection).
22:26:05 -!- trout has quit (Ping timeout: 255 seconds).
22:26:44 -!- Cale has joined.
22:41:04 -!- impomatic has joined.
22:55:02 -!- trout has joined.
22:58:08 -!- variable has quit (Ping timeout: 276 seconds).
23:05:14 <esowiki> [[User:Language]] https://esolangs.org/w/index.php?diff=56481&oldid=56480 * Ais523 * (+52) add a few extra cats to this: [[Category:Unimplemented]] is particularly important as it may inspire someone to write an interpreter (which should be entirely possible!)
23:24:38 <esowiki> [[Fusion Tag]] N https://esolangs.org/w/index.php?oldid=56482 * Ais523 * (+2369) I wanted to prove this TC before posting it, but I'm struggling, so it makes more sense to post it to see what other people think about it
23:25:07 <esowiki> [[Language list]] https://esolangs.org/w/index.php?diff=56483&oldid=56458 * Ais523 * (+17) /* F */ +[[Fusion Tag]]
23:26:04 -!- variable has joined.
23:26:13 <esowiki> [[User:Ais523]] https://esolangs.org/w/index.php?diff=56484&oldid=55708 * Ais523 * (+200) +[[Fusion Tag]]; notes about the current status of Feather
23:29:25 -!- trout has quit (Ping timeout: 245 seconds).
23:39:28 -!- oerjan has joined.
23:41:04 <oerjan> @metar ENVA
23:41:05 <lambdabot> ENVA 072320Z 13008KT CAVOK 08/07 Q1023 RMK WIND 670FT 16007KT
23:41:27 <oerjan> <fizzie> E2HOT <-- E2DAMP
23:42:04 <oerjan> opening the door should help, i hope
23:48:36 -!- imode has joined.
23:54:04 -!- erkin has quit (Quit: Ouch! Got SIGIRL, dying...).
23:58:24 -!- trout has joined.
←2018-07-06 2018-07-07 2018-07-08→ ↑2018 ↑all