Home freenode/#haskell: Logs Calendar

Logs: freenode/#haskell

←Prev  Next→
Page 1 .. 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 .. 5022
— 502,152 events total
2020-11-05 08:54:49 Axma50981 is now known as Axman6
2020-11-05 08:54:56 × dmiles quits (dmiles@c-73-67-179-188.hsd1.wa.comcast.net) (Ping timeout: 272 seconds)
2020-11-05 08:55:04 <fraktor> I'm trying to think if there are any situations in which doing a grouping of 3 in one board and 1 in another is more wasteful than doing 2 and 2.
2020-11-05 08:55:10 <[exa]> anyway this reduces to subset sum, for items of total size W and subset of size S you give it boards of size S and (W-S) and it will either solve the subset or prove that it's easier by subdividing S into pieces
2020-11-05 08:55:37 → sord937 joins (~sord937@gateway/tor-sasl/sord937)
2020-11-05 08:55:47 <[exa]> (modulo corner cases)
2020-11-05 08:56:06 <tomsmeding> total waste = sum_{b in used boards} length(b) - sum_{o in objects} length(o)
2020-11-05 08:56:19 <tomsmeding> so minimal waste <=> minimal total length of boards chosen
2020-11-05 08:57:22 <fraktor> tomsmeding: I don't think so. At least not in all cases.
2020-11-05 08:57:44 <fraktor> Because I'm not saying "I have chosen these boards, fit these cuts into them." I'm trying to choose which boards to get in the first place.
2020-11-05 08:58:03 <tomsmeding> "minimal total length of boards chosen"
2020-11-05 08:58:32 <fraktor> Oh! I misread. I thought it was "minimal number of boards chosen." In that case, you're correct.
2020-11-05 08:58:53 × Amras quits (~Amras@unaffiliated/amras0000) (Ping timeout: 246 seconds)
2020-11-05 08:58:59 <tomsmeding> not sure if this observation helps in any way though :p
2020-11-05 08:59:23 <fraktor> It's either completely useless or the key to cracking the puzzle
2020-11-05 08:59:28 <fraktor> Not sure which
2020-11-05 08:59:58 <tomsmeding> it's fairly easy to formulate as an ILP problem
2020-11-05 09:00:02 × Sanchayan quits (~Sanchayan@223.226.118.59) (Quit: leaving)
2020-11-05 09:00:26 ski . o O ( "Inductive Logic Programming" ? )
2020-11-05 09:00:33 <tomsmeding> integer linear programming :')
2020-11-05 09:00:37 <tomsmeding> yay acronyms
2020-11-05 09:00:41 <ski> ah
2020-11-05 09:00:56 × christo quits (~chris@81.96.113.213) (Remote host closed the connection)
2020-11-05 09:00:57 <fraktor> Oh wow, that's hard though
2020-11-05 09:01:12 <tomsmeding> ILP problems are NP-complete in general so this proves nothing
2020-11-05 09:01:20 <ski> (why's it called "Linear Programming", btw ?)
2020-11-05 09:01:31 <tomsmeding> but ILP solvers are notoriously good at solving hard problems faster than expected
2020-11-05 09:01:43 <tomsmeding> ski: ILP = LP + branch-and-bound, where LP = linear programming
2020-11-05 09:02:10 <tomsmeding> the standard algorithm is solving the problem without the restriction that all variables need to be integral, and then doing branch-and-bound to find a valid ILP solution
2020-11-05 09:02:12 <fraktor> I think it's called LP because the underlying systems have linear relationships to each other?
2020-11-05 09:02:30 <tomsmeding> (that first step is just solving an LP problem)
2020-11-05 09:03:02 → christo joins (~chris@81.96.113.213)
2020-11-05 09:03:09 <tomsmeding> I'm struggling to understand [exa]'s reduction though; have you just proven that this problem is at least as hard as subset sum?
2020-11-05 09:03:21 <[exa]> ski: because it's so np-hard that you can encode programs into that :D
2020-11-05 09:03:44 <tomsmeding> oh _that_ was the question, yeah the name is atrocious
2020-11-05 09:04:13 <fraktor> tomsmeding: I've never used a linear programming library before, would you be willing to help me encode this into it?
2020-11-05 09:04:18 <tomsmeding> [exa]: because if you've proven that, expressing this as an ILP might be fairly optimal :p
2020-11-05 09:04:23 <tomsmeding> fraktor: sure
2020-11-05 09:04:25 × PlasmaSt` quits (~mattplasm@45.83.89.28) (Ping timeout: 264 seconds)
2020-11-05 09:04:27 <[exa]> tomsmeding: given some careful choice of board lengths I guess you can solve a good number of subset sum cases with that
2020-11-05 09:04:40 <tomsmeding> all, or a good number?
2020-11-05 09:04:50 <ski> fraktor : doesn't explain the "programming" part, though
2020-11-05 09:05:04 <ski> [exa] : isn't that just for the integer variety ?
2020-11-05 09:05:14 <[exa]> tomsmeding: what I wanted to point out, it's better to have a heuristic search written in 10 minutes than pulling in the ILP solver and hoping it's going to reinvent the heuristic
2020-11-05 09:05:21 <lortabac> ski: "programming" is not meant as computer programming, but more like "planning"
2020-11-05 09:05:44 <tomsmeding> except if you're sadistic and want an exactly optimal solution :p
2020-11-05 09:06:09 <fraktor> If nothing else I'll learn how to use an ILP solver.
2020-11-05 09:06:43 <tomsmeding> (I have to dig how it worked again too, give me a minute :p
2020-11-05 09:06:44 <tomsmeding> )
2020-11-05 09:07:36 ski . o O ( "Why “dynamic programming”?" by Arcane Sentiment in 2010-04-23 <http://arcanesentiment.blogspot.com/2010/04/why-dynamic-programming.html> )
2020-11-05 09:07:38 × rprije quits (~rprije@194-193-168-77.tpgi.com.au) (Ping timeout: 260 seconds)
2020-11-05 09:07:46 × christo quits (~chris@81.96.113.213) (Remote host closed the connection)
2020-11-05 09:07:52 → Franciman joins (~francesco@host-79-36-167-172.retail.telecomitalia.it)
2020-11-05 09:08:31 → rprije joins (~rprije@124.148.131.132)
2020-11-05 09:10:25 <tomsmeding> fraktor: so the idea of an LP problem (let's start with that) is the following
2020-11-05 09:10:37 <tomsmeding> you define a number of real-valued variables, x1,...,xn
2020-11-05 09:10:51 <tomsmeding> and 1. give an optimisation function, which is a linear combination of those variables
2020-11-05 09:11:09 <tomsmeding> and 2. a list of linear constraints, which are of the form (linear combination of the variables) <= (real constant)
2020-11-05 09:11:31 <tomsmeding> then the LP solver gives you an assignment of the variables such that the target function is minimised
2020-11-05 09:11:37 <tomsmeding> (s/optimisation function/target function/)
2020-11-05 09:11:53 <tomsmeding> ILP solvers can additionally handle the restriction that certain variables may only be integer-valued
2020-11-05 09:12:28 <fraktor> I'm really sorry, but something came up and I gotta go
2020-11-05 09:12:35 <tomsmeding> np :)
2020-11-05 09:12:40 <fraktor> I'll definitely look into this though, thank you
2020-11-05 09:12:41 × fraktor quits (~walt@129.93.191.18) (Quit: WeeChat 2.8)
2020-11-05 09:13:03 tomsmeding might still code this up for reason of procrastination
2020-11-05 09:13:09 <[exa]> sounds like fedex delivered the boards!
2020-11-05 09:13:22 <tomsmeding> :D
2020-11-05 09:14:12 <__monty__> s/np/np-hard/ FTFY
2020-11-05 09:14:30 <[exa]> anyway the sum problems are cool from the hardness perspective
2020-11-05 09:14:53 <[exa]> https://en.wikipedia.org/wiki/3SUM <- most illustrative one I know of
2020-11-05 09:15:01 × zaquest quits (~notzaques@5.128.210.178) (Quit: Leaving)
2020-11-05 09:15:49 <tomsmeding> ah the log bounds, O(n^2 / (log n / log log n)^(2/3)) lovely <3
2020-11-05 09:16:28 → zaquest joins (~notzaques@5.128.210.178)
2020-11-05 09:16:52 <ski> this is an instance of CP (Constraint Programming) (of which CLP, Constraint Logic Programming, is a more nicely integrated form)
2020-11-05 09:17:48 → christo joins (~chris@81.96.113.213)
2020-11-05 09:18:15 × xff0x quits (~fox@2001:1a81:522f:7b00:d95:27ea:7e18:f05f) (Ping timeout: 272 seconds)
2020-11-05 09:18:41 → DavidEichmann joins (~david@43.240.198.146.dyn.plus.net)
2020-11-05 09:19:02 → xff0x joins (~fox@2001:1a81:522f:7b00:1cd6:2f35:f89:eebf)
2020-11-05 09:19:04 → ggole joins (~ggole@2001:8003:8119:7200:3462:7213:ea5b:f472)
2020-11-05 09:22:06 → slewis joins (~slewis@185.204.1.185)
2020-11-05 09:22:57 → avdb joins (~avdb@ip-83-134-202-8.dsl.scarlet.be)
2020-11-05 09:24:15 → raichoo joins (~raichoo@213.240.178.58)
2020-11-05 09:25:24 <raichoo> Hi everyone, we have rebooted Advent of Haskell 2020 and are currently collecting potential blog articles. www.adventofhaskell.com
2020-11-05 09:25:57 × TMA quits (tma@twin.jikos.cz) (Read error: Connection reset by peer)
2020-11-05 09:26:05 <Axman6> hooray!
2020-11-05 09:26:27 <Axman6> also I feel like that's a nick I haven't aseen for a very long time...
2020-11-05 09:26:34 × britva quits (~britva@2a02:aa13:7240:2980:9117:32f5:aa09:6904) (Quit: This computer has gone to sleep)
2020-11-05 09:27:10 <raichoo> I've been MIA from twitter for kind of a long time and I'm not posting that much in here :D
2020-11-05 09:27:20 <raichoo> But glad someone remembers me nevertheless ^^
2020-11-05 09:27:32 → dmiles joins (dmiles@c-73-67-179-188.hsd1.wa.comcast.net)
2020-11-05 09:29:15 <Axman6> hmm, I could possibly make soething for this too
2020-11-05 09:29:26 <Axman6> something too. mauybe IRC + pub is a bad idea
2020-11-05 09:29:51 → thc202 joins (~thc202@unaffiliated/thc202)
2020-11-05 09:29:52 × christo quits (~chris@81.96.113.213) (Remote host closed the connection)
2020-11-05 09:30:07 → britva joins (~britva@2a02:aa13:7240:2980:9117:32f5:aa09:6904)
2020-11-05 09:31:30 <raichoo> Axman6: That would be cool :) Just drop me a mail, all the submissions to advent@antei.de go straight to me.
2020-11-05 09:31:58 <merijn> raichoo: Did you mail the Haskell Weekly News guy yet?
2020-11-05 09:32:12 → christo joins (~chris@81.96.113.213)
2020-11-05 09:33:36 <raichoo> merijn: Just blasted things out on social media. We just pushed the website online yesterday. Could you drop me the contact in a DM?
←Prev  Next→
Page 1 .. 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 .. 5022

All times are in UTC.