Logs: liberachat/#haskell
| 2026-02-24 21:54:51 | × | ChaiTRex quits (~ChaiTRex@user/chaitrex) (Remote host closed the connection) |
| 2026-02-24 21:55:00 | <monochrom> | Who writes 1000 lines of code on a REPL anyway? Be realistic. |
| 2026-02-24 21:55:02 | <geekosaur> | probably just hint |
| 2026-02-24 21:55:10 | <Guest81> | OK so basically "Try it!" is not a true interpreter. |
| 2026-02-24 21:55:12 | → | ChaiTRex joins (~ChaiTRex@user/chaitrex) |
| 2026-02-24 21:55:35 | <tomsmeding> | it is an interpreter, but not ghci |
| 2026-02-24 21:55:46 | <mauke> | a = [1,2,3] is not an expression |
| 2026-02-24 21:55:48 | <tomsmeding> | ghci does quite a bit more than just an interpreter for basic expressions, and "learn you a haskell" assumes ghci |
| 2026-02-24 21:56:55 | <Guest81> | So i need ghci. Thanks all. |
| 2026-02-24 21:57:07 | <tomsmeding> | that's probably easiest, yes (use ghcup) |
| 2026-02-24 21:57:44 | <EvanR> | repl is overrated, you want to load a file anyway. Then reload |
| 2026-02-24 21:58:31 | × | ChaiTRex quits (~ChaiTRex@user/chaitrex) (Client Quit) |
| 2026-02-24 21:59:39 | → | philderbeast joins (~philderbe@57-134-39-54.resi.cgocable.ca) |
| 2026-02-24 21:59:44 | ← | Guest81 parts (~Guest81@52.144.37.132) () |
| 2026-02-24 22:00:27 | → | ChaiTRex joins (~ChaiTRex@user/chaitrex) |
| 2026-02-24 22:01:02 | → | merijn joins (~merijn@host-cl.cgnat-g.v4.dfn.nl) |
| 2026-02-24 22:01:40 | × | Milan_Vanca quits (~milan@user/Milan-Vanca:32634) (Quit: WeeChat 4.7.2) |
| 2026-02-24 22:02:15 | × | humasect quits (~humasect@dyn-192-249-132-90.nexicom.net) (Quit: Leaving...) |
| 2026-02-24 22:03:14 | × | philderbeast quits (~philderbe@57-134-39-54.resi.cgocable.ca) (Client Quit) |
| 2026-02-24 22:03:59 | <haskellbridge> | <ijouw> Isn't the two sets algorithm discussed above easy to compute? The question is whether the sum [1..n] is even (solvable in constant time) (or am I missing something?). Printing could indeed be slowest part. |
| 2026-02-24 22:04:21 | × | takuan quits (~takuan@d8D86B9E9.access.telenet.be) (Ping timeout: 255 seconds) |
| 2026-02-24 22:04:25 | <tomsmeding> | ijouw: do you have a proof that if sum [1..n] is even, there is such a splitting? |
| 2026-02-24 22:04:32 | → | peterbecich joins (~Thunderbi@71.84.33.135) |
| 2026-02-24 22:04:35 | × | target_i quits (~target_i@user/target-i/x-6023099) (Quit: leaving) |
| 2026-02-24 22:04:44 | <tomsmeding> | (there is, but figuring out what the splitting is, requires a little trick) |
| 2026-02-24 22:04:47 | <haskellbridge> | <ijouw> Working on it |
| 2026-02-24 22:08:07 | × | merijn quits (~merijn@host-cl.cgnat-g.v4.dfn.nl) (Ping timeout: 264 seconds) |
| 2026-02-24 22:10:01 | → | abiss27 joins (~abiss27@user/abiss) |
| 2026-02-24 22:11:53 | × | petrichor quits (~jez@user/petrichor) (Ping timeout: 248 seconds) |
| 2026-02-24 22:12:45 | <mauke> | ah, I see it |
| 2026-02-24 22:13:01 | <mauke> | 1 + 2 = 3 |
| 2026-02-24 22:15:12 | <mauke> | nvm, I'm blind |
| 2026-02-24 22:17:05 | <mauke> | hah, no. I was wrong about being wrong. I just did it backwards :-) |
| 2026-02-24 22:17:36 | <newmind> | mauke: did you get nerdsniped there? |
| 2026-02-24 22:17:39 | × | gmc quits (sid58314@id-58314.ilkley.irccloud.com) (Server closed connection) |
| 2026-02-24 22:17:50 | → | gmc joins (sid58314@id-58314.ilkley.irccloud.com) |
| 2026-02-24 22:19:06 | → | merijn joins (~merijn@host-cl.cgnat-g.v4.dfn.nl) |
| 2026-02-24 22:19:31 | → | petrichor joins (~jez@user/petrichor) |
| 2026-02-24 22:19:53 | × | tremon quits (~tremon@83.80.159.219) (Quit: getting boxed in) |
| 2026-02-24 22:21:16 | <tomsmeding> | lantti: I'm not sure what you did, but it can probably be done more efficiently; this is haskell with `putStrLn . unwords . map show` https://tomsmeding.com/ss/get/tomsmeding/RnFf4z |
| 2026-02-24 22:23:02 | <tomsmeding> | (I figured out a way to compute what numbers to print in constant time; then I just have to print all those numbers) |
| 2026-02-24 22:23:28 | <tomsmeding> | it's a fun problem :) |
| 2026-02-24 22:24:08 | × | merijn quits (~merijn@host-cl.cgnat-g.v4.dfn.nl) (Ping timeout: 268 seconds) |
| 2026-02-24 22:24:58 | <tomsmeding> | and I'm not sure where even that 0.30s comes from; it takes less than 1ms on that input on my machine |
| 2026-02-24 22:25:35 | × | peterbecich quits (~Thunderbi@71.84.33.135) (Ping timeout: 245 seconds) |
| 2026-02-24 22:25:48 | <geekosaur> | `sum [1..n]` isn't there a number theory approach for that? |
| 2026-02-24 22:26:22 | <haskellbridge> | <ijouw> yes, it is (n*(n+1))/2 |
| 2026-02-24 22:26:41 | <tomsmeding> | it seems printing is actually rather slow on that judge server! On roughly 260000 I take 0.08s, on roughly 653000 I take 0.21s, and on 1000000 I take 0.30s |
| 2026-02-24 22:27:25 | <tomsmeding> | and I can assure you that I am actually doing work that should take <10us plus `putStrLn . unwords . map show` on a lazy list of Int |
| 2026-02-24 22:28:21 | <tomsmeding> | (I'm not sure if it's responsible to post my solution publically for people to scrutinise) |
| 2026-02-24 22:28:43 | → | terrorjack joins (~terrorjac@2a01:4f8:271:2d98::2) |
| 2026-02-24 22:29:56 | <lantti> | tomsmeding: I already passed so you won't boost my grade with it |
| 2026-02-24 22:30:21 | <lantti> | of course I don't know if any other students are reading this |
| 2026-02-24 22:31:07 | <tomsmeding> | lantti: do you determine what numbers to print in constant time? |
| 2026-02-24 22:31:19 | <tomsmeding> | or is there a little loop or something involved |
| 2026-02-24 22:31:32 | <lantti> | yes, but I still generate a list of them. eliminating that list now... |
| 2026-02-24 22:31:33 | <tomsmeding> | (and how do your judge times compare to mine?) |
| 2026-02-24 22:31:42 | → | prdak joins (~Thunderbi@user/prdak) |
| 2026-02-24 22:31:48 | <lantti> | yes, to the constant time |
| 2026-02-24 22:31:55 | <tomsmeding> | interesting |
| 2026-02-24 22:32:41 | × | arandombit quits (~arandombi@user/arandombit) (Ping timeout: 248 seconds) |
| 2026-02-24 22:32:50 | <lantti> | I also use a delete on one of the lists to remove that one int that needs to move to the other set |
| 2026-02-24 22:33:12 | <lantti> | all that can still go away if i make a loop instead of a list |
| 2026-02-24 22:33:30 | <lantti> | but that might work against me as well, lets see |
| 2026-02-24 22:33:39 | × | kawzeg quits (kawzeg@2a01:4f9:c013:cfbf::1) (Server closed connection) |
| 2026-02-24 22:33:57 | → | kawzeg joins (kawzeg@2a01:4f9:c013:cfbf::1) |
| 2026-02-24 22:34:27 | → | arahael joins (~wetfoot@user/arahael) |
| 2026-02-24 22:34:59 | → | machinedgod joins (~machinedg@d172-219-48-230.abhsia.telus.net) |
| 2026-02-24 22:36:19 | × | prdak quits (~Thunderbi@user/prdak) (Ping timeout: 264 seconds) |
| 2026-02-24 22:36:26 | → | pavonia joins (~user@user/siracusa) |
| 2026-02-24 22:36:59 | <tomsmeding> | turns out my lists weren't actually lazy when printed -- I was materialising them with 'length'. If I don't do that, my worst-case time on the judge server goes from 0.30s to 0.21s |
| 2026-02-24 22:38:13 | × | tromp quits (~textual@2001:1c00:3487:1b00:7955:9591:6018:7ef9) (Quit: My iMac has gone to sleep. ZZZzzz…) |
| 2026-02-24 22:38:37 | <tomsmeding> | (that server is really slow...) |
| 2026-02-24 22:39:15 | <mauke> | you guys are using lists? |
| 2026-02-24 22:39:30 | <tomsmeding> | I am using lists only to pass to `putStrLn . unwords . map show` |
| 2026-02-24 22:40:31 | <newmind> | tomsmeding: without printing and just evaluating its fast on the server too? |
| 2026-02-24 22:42:19 | <tomsmeding> | then the server would mark my answer wrong and (presumably? didn't try) not proceed to the larger test cases |
| 2026-02-24 22:42:41 | <mauke> | it should run all of them |
| 2026-02-24 22:44:39 | → | merijn joins (~merijn@host-cl.cgnat-g.v4.dfn.nl) |
| 2026-02-24 22:45:57 | <tomsmeding> | ok if I replace the `putStrLn . unwords . map show` with `mapM_ evaluate` then maximum runtime goes from 0.21s to 0.02s |
| 2026-02-24 22:46:14 | <lantti> | ah, ok, I got it to 0.21s too by eliminating two calls to length and one to delete |
| 2026-02-24 22:46:41 | × | __monty__ quits (~toonn@user/toonn) (Quit: leaving) |
| 2026-02-24 22:46:49 | <lantti> | ah, so there it is :) |
| 2026-02-24 22:47:01 | <tomsmeding> | and if I do `evaluate . length . unwords . map show` instead, I get 0.16s |
| 2026-02-24 22:47:21 | <tomsmeding> | so that's 0.02s for the computation, 0.14s for the serialisation, and 0.05s for the printing |
| 2026-02-24 22:47:36 | <tomsmeding> | this is all <0.001s on my machine lol |
| 2026-02-24 22:48:52 | <haskellbridge> | <ijouw> I now have a formal proof by induction with step 4 |
| 2026-02-24 22:48:57 | × | merijn quits (~merijn@host-cl.cgnat-g.v4.dfn.nl) (Ping timeout: 246 seconds) |
| 2026-02-24 22:49:17 | <tomsmeding> | that sounds like mauke's solution (exchanged ideas in private chat) |
| 2026-02-24 22:49:28 | <tomsmeding> | mine is overengineered, I used a sqrt |
| 2026-02-24 22:50:41 | <mauke> | my solution doesn't use lists :-) |
| 2026-02-24 22:50:42 | <haskellbridge> | <ijouw> I am debating whether i want to put it in an automatic solver |
| 2026-02-24 22:51:52 | <tomsmeding> | mauke: I tool the liberty to submit your solution to the judge; it takes 0.59s |
| 2026-02-24 22:52:11 | <tomsmeding> | stdout handling is slow, told you |
| 2026-02-24 22:52:26 | <tomsmeding> | *took |
| 2026-02-24 22:53:22 | <mauke> | spoilers: https://cses.fi/paste/7167882c695ce46ff9ce6b/ |
| 2026-02-24 22:54:57 | <tomsmeding> | overengineered spoilers: https://cses.fi/paste/b23bf94c9440505af9ce60/ (if we're sharing anyway...) |
| 2026-02-24 22:56:05 | <haskellbridge> | <ijouw> There is div from Integral, no need for double cast for /2 |
| 2026-02-24 22:56:18 | <tomsmeding> | yes, because there's also sqrt |
| 2026-02-24 22:57:40 | <tomsmeding> | *yes I do because |
All times are in UTC.