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 So I've got this decision problem. 01:29:38 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 However, each person will only accept fruits of particular kinds. 01:31:05 There's an FxP matrix of booleans which indicates whether or not each person will accept each kind of fruit. 01:31:28 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 Now, this sounds like an NP-complete problem. Is it? 01:36:36 Pretty sure it's NP-hard because I can reduce set-packing to it: https://en.wikipedia.org/wiki/Set_packing 01:36:46 "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 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 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 There is also one person who demands enough "otherwise" fruits that k other people must receive fruits that are not "otherwise". 01:40:05 No, scratch that last person. 01:40:16 There are only the people who demand exactly one fruit. 01:40:27 I'm given exactly enough "otherwise" fruits that I can give them to all but k people. 01:40:35 I'm also given exactly one of every other type of fruit. 01:40:36 Done. 01:42:46 So, that proves that it's NP-hard. 01:43:45 Is it in NP? 01:48:46 Warrigal: if the p_i are given in unary, then yes, since the solution is polynomial size in the input data 01:48:51 otherwise, i'm not sure. 01:51:29 I'm assuming that all the numbers are given in binary or decimal. 01:51:49 hm wait, it works even without 01:52:02 isn't this an integer linear programming problem anyway 01:52:11 the list of all assignments just tells how many of each fruit to each person 01:52:44 and that can be done in binary/decimal. 01:53:06 so yeah, NP. 01:54:33 -!- mrrmx has quit (Quit: Leaving). 02:22:28 Yeah, it's probably obviously integer linear programming. 02:22:37 Here's another way of stating it. 02:23:14 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 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 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 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 [[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 [[MediaWiki talk:Common.js]] M https://esolangs.org/w/index.php?diff=56460&oldid=56459 * Oerjan * (+1) punct. 02:40:19 ^bf +[-->-[>>+>-----<<]<--<---]>-.>>>+.>>..+++[.>]<<<<.+++.------.<<-. 02:40:19 Hello, World 02:54:03 what's more general than a hypergraph? <-- supercalifragilisticexpialigraph hth 03:01:59 Here's the paper on dual concatenation: https://www.sciencedirect.com/science/article/pii/S0304397505004056 03:02:06 (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 oerjan: it did help. :P 04:07:31 [[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 [[Truth-machine]] https://esolangs.org/w/index.php?diff=56462&oldid=56436 * A * (-14) /* brainfuck */ 07:17:45 [[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 [[Shorten your Brainfuck code]] https://esolangs.org/w/index.php?diff=56464&oldid=56438 * A * (+28) /* Really? A shorter one */ 07:22:54 [[User talk:A]] https://esolangs.org/w/index.php?diff=56465&oldid=56313 * Oerjan * (+406) /* Your brainfuck truth-machine */ new section 07:25:03 [[Shorten your Brainfuck code]] https://esolangs.org/w/index.php?diff=56466&oldid=56464 * A * (+65) /* Really? A shorter one */ 07:29:02 [[Truth-machine]] https://esolangs.org/w/index.php?diff=56467&oldid=56463 * A * (+109) /* brainfuck */ 07:30:13 ^bf ,.[->+>+<<]++++++[->--------<]>[>[.]]!0 07:30:14 0 07:30:16 ^bf ,.[->+>+<<]++++++[->--------<]>[>[.]]!1 07:30:16 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 ... 07:30:19 checks out 07:31:20 [[Truth-machine]] https://esolangs.org/w/index.php?diff=56468&oldid=56467 * A * (-3) /* brainfuck */ 07:32:18 [[Truth-machine]] https://esolangs.org/w/index.php?diff=56469&oldid=56468 * A * (-106) /* brainfuck */ 07:34:51 [[User talk:A]] https://esolangs.org/w/index.php?diff=56470&oldid=56465 * A * (+149) /* Your brainfuck truth-machine */ 07:43:45 [[User talk:A]] https://esolangs.org/w/index.php?diff=56471&oldid=56470 * A * (+144) /* Your brainfuck truth-machine */ 07:47:32 [[User talk:A]] https://esolangs.org/w/index.php?diff=56472&oldid=56471 * A * (-69) /* Your brainfuck truth-machine */ 07:50:24 [[User talk:A]] https://esolangs.org/w/index.php?diff=56473&oldid=56472 * A * (+5) /* Your brainfuck truth-machine */ 07:54:56 [[Shorten your Brainfuck code]] https://esolangs.org/w/index.php?diff=56474&oldid=56466 * A * (+123) 07:54:56 [[User talk:A]] https://esolangs.org/w/index.php?diff=56475&oldid=56473 * Oerjan * (+207) /* Your brainfuck truth-machine */ 07:59:26 [[User talk:A]] https://esolangs.org/w/index.php?diff=56476&oldid=56475 * A * (+175) /* Your brainfuck truth-machine */ 08:02:16 ^bf ,.[->+>+<<]++++++[->--------<]>[>[.]] 08:02:22 ^bf ,.[->+>+<<]++++++[->--------<]>[>[.]]!0 08:02:22 0 08:05:13 [[User talk:A]] https://esolangs.org/w/index.php?diff=56477&oldid=56476 * Oerjan * (+163) Yes 08:10:40 [[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 @metar EGLL 15:25:27 EGLL 071520Z AUTO 30008KT 250V020 9999 NCD 30/12 Q1023 NOSIG 15:25:32 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 @metar BHX 17:09:59 hmm that doesn't work 17:10:15 @metar egbb 17:10:15 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 `iata BHX 18:22:59 Birmingham (BHX, EGBB) 18:29:43 -!- laerling has joined. 18:31:44 @metar EGSC 18:31:45 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 [[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 It's far too warm... 18:56:38 `icao EGSC 18:56:39 Cambridge (CBG, EGSC) 18:57:47 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 [[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 [[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 [[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 [[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 [[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 @metar ENVA 23:41:05 ENVA 072320Z 13008KT CAVOK 08/07 Q1023 RMK WIND 670FT 16007KT 23:41:27 E2HOT <-- E2DAMP 23:42:04 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.