Home freenode/#haskell: Logs Calendar

Logs: freenode/#haskell

←Prev  Next→
Page 1 .. 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 .. 5022
— 502,152 events total
2020-11-22 14:09:54 → boxscape joins (54a35f37@gateway/web/cgi-irc/kiwiirc.com/ip.84.163.95.55)
2020-11-22 14:11:12 <halbGefressen> Now, how do I recursively apply this function with >>= until it either returns a valid sudoku or an empty clause?
2020-11-22 14:12:40 × son0p quits (~son0p@181.136.122.143) (Ping timeout: 256 seconds)
2020-11-22 14:13:05 <Rembane> halbGefressen: That sounds really fun! What is the type of your function?
2020-11-22 14:13:52 × invaser quits (~Thunderbi@31.148.23.125) (Ping timeout: 265 seconds)
2020-11-22 14:14:27 <ski> halbGefressen : should it, given a position, attempt to fill that position in every possible way ?
2020-11-22 14:14:33 <halbGefressen> https://paste.gnome.org/pebsnonzq
2020-11-22 14:14:40 → son0p joins (~son0p@181.136.122.143)
2020-11-22 14:14:48 <halbGefressen> Sudoku is the type [[Int]]
2020-11-22 14:15:24 <Rembane> The implementation of the list monad should IIRC give you every possible Sudoku
2020-11-22 14:16:29 <halbGefressen> And if I manually bind advanceStep exactly n times to my sudoku where n is the number of 0s in the sudoku, it will return the solution or the empty list. Now how would I wrap this into a function using the do notation?
2020-11-22 14:17:09 <merijn> tbh, [[Int]] is probably a bad datatype for sudoku. I'd probably use either "Array (Int, Int) Int" or "Map (Int, Int) Int"
2020-11-22 14:17:22 <merijn> (that's not really an answer, but worth considering)
2020-11-22 14:18:03 <halbGefressen> I know, actually it is part of a university homework challenge (normally I would do it with backtracking, but I just wanted to mess around a little :))
2020-11-22 14:18:46 → phaul joins (~phaul@ruby/staff/phaul)
2020-11-22 14:18:49 × NieDzejkob quits (~quassel@188.123.215.55) (Quit: https://quassel-irc.org - Chat comfortably. Anywhere.)
2020-11-22 14:19:53 ← ben_m parts (~ben@unaffiliated/ben-m/x-8385872) ("WeeChat 2.8")
2020-11-22 14:20:35 → Franciman joins (~francesco@host-82-51-90-98.retail.telecomitalia.it)
2020-11-22 14:20:36 × Boomerang quits (~Boomerang@xd520f68c.cust.hiper.dk) (Ping timeout: 256 seconds)
2020-11-22 14:20:39 → NieDzejkob joins (~quassel@188.123.215.55)
2020-11-22 14:24:36 × phaul quits (~phaul@ruby/staff/phaul) (Ping timeout: 240 seconds)
2020-11-22 14:24:57 × berberman_ quits (~berberman@unaffiliated/berberman) (Quit: ZNC 1.7.5 - https://znc.in)
2020-11-22 14:25:03 → heatsink joins (~heatsink@107-136-5-69.lightspeed.sntcca.sbcglobal.net)
2020-11-22 14:25:34 → berberman joins (~berberman@unaffiliated/berberman)
2020-11-22 14:25:50 × alp quits (~alp@2a01:e0a:58b:4920:c027:cd9b:f7aa:d6c9) (Ping timeout: 264 seconds)
2020-11-22 14:26:27 <kuribas> you know about this pearl? https://www.cs.tufts.edu/~nr/cs257/archive/richard-bird/sudoku.pdf
2020-11-22 14:26:53 <halbGefressen> Thanks, I'll definitely look into it!
2020-11-22 14:27:15 <ski> halbGefressen : you have lots of useless/redundant nondeterminism
2020-11-22 14:27:17 <kuribas> halbGefressen: if that solves your challenge, better try solving it first yourself :)
2020-11-22 14:27:58 <ski> (also, your second `$' is useless. and you could move the `filter' guard into the list comprehension)
2020-11-22 14:28:09 → Tario joins (~Tario@201.192.165.173)
2020-11-22 14:28:12 → acidjnk_new joins (~acidjnk@p200300d0c719ff94358934eb0dfd70c0.dip0.t-ipconnect.de)
2020-11-22 14:28:29 <kuribas> the interesting bit here is how they reduce the search space by reordering the operations
2020-11-22 14:29:07 → elfets_ joins (~elfets@ip-37-201-23-96.hsi13.unitymediagroup.de)
2020-11-22 14:29:16 × heatsink quits (~heatsink@107-136-5-69.lightspeed.sntcca.sbcglobal.net) (Ping timeout: 240 seconds)
2020-11-22 14:29:29 → phaul joins (~phaul@ruby/staff/phaul)
2020-11-22 14:29:41 <kuribas> I benchmarked my CPS version of ExceptT on my parser library, and it gave me a 15% improvement :)
2020-11-22 14:30:26 × dirediresalt quits (DirefulSal@gateway/vpn/privateinternetaccess/direfulsalt) (Remote host closed the connection)
2020-11-22 14:30:28 <kuribas> not that much, but still something, and completely for free :)
2020-11-22 14:30:40 <ski> halbGefressen : eventually, every hole will have to be filled. it's not really useful to count filling A first, and then B, as generating separate solutions to filling B first, and then A. doing this results in duplicate solutions, and doing this *repeatedly* will cause an exponential blow-up
2020-11-22 14:31:21 → dirediresalt joins (DirefulSal@gateway/vpn/privateinternetaccess/direfulsalt)
2020-11-22 14:31:29 <halbGefressen> I know, thats exactly my problem
2020-11-22 14:31:48 <ski> so .. "Don't do that, then !" ?
2020-11-22 14:32:05 <halbGefressen> Thats my problem, I don't know how to do it in this manner xD
2020-11-22 14:32:43 × elfets quits (~elfets@ip-37-201-23-96.hsi13.unitymediagroup.de) (Ping timeout: 256 seconds)
2020-11-22 14:32:49 <halbGefressen> It can solve 2x2 sudokus, but with 3x3 it just computes into eternity
2020-11-22 14:32:53 <ski> pick one location to fill in. don't use nondeterminism for that. (you still have nondeterminism for *how* you're filling it, of course), then continue from there
2020-11-22 14:33:53 <kuribas> the solution to avoid combinatorial explosion is to prune *early*.
2020-11-22 14:34:48 <ski> an improvment then would be to, if possible, pick a location for which there is only one way to fill it in. (or, even better, to pick a location that's impossible to fill, if that kind of situation is possible in your scheme. "fail earlier, fail fast" is the slogan, followed by "delay choices")
2020-11-22 14:35:23 × Franciman quits (~francesco@host-82-51-90-98.retail.telecomitalia.it) (Quit: Leaving)
2020-11-22 14:35:58 × phaul quits (~phaul@ruby/staff/phaul) (Ping timeout: 256 seconds)
2020-11-22 14:36:27 <halbGefressen> Would it be a good idea to implement the DPLL algorithm for SAT and then just reduce my sudoku to SAT?
2020-11-22 14:37:07 <kuribas> that's cheating :)
2020-11-22 14:37:35 <kuribas> but it would work
2020-11-22 14:37:50 <ski> dunno what the DPLL algorithm is
2020-11-22 14:39:06 → whatisRT joins (~whatisRT@2002:5b41:6a33:0:1094:8ebf:d3e9:e277)
2020-11-22 14:39:20 <Feuermagier> how do I find the index of the first 0 in a [[Int]]?
2020-11-22 14:39:32 <halbGefressen> It's basically an algorithm to determine a solution to a boolean term given its conjunctive normal form
2020-11-22 14:39:46 → invaser joins (~Thunderbi@31.148.23.125)
2020-11-22 14:39:50 <halbGefressen> ahh, another sudoku solver :)
2020-11-22 14:40:17 <Feuermagier> halbGefressen, what are you doing here? :D
2020-11-22 14:40:43 <ski> @type findIndex
2020-11-22 14:40:44 <lambdabot> (a -> Bool) -> [a] -> Maybe Int
2020-11-22 14:41:06 <ski> hm
2020-11-22 14:42:38 <Feuermagier> halbGefressen, take a look at https://en.wikipedia.org/wiki/Mathematics_of_Sudoku + http://www2.imm.dtu.dk/pubdb/edoc/imm5625.pdf
2020-11-22 14:44:17 <kuribas> it's fairly trivial to turn a sudoku in something that a SAT solver can solve, but it's not interesting.
2020-11-22 14:45:00 → alp joins (~alp@2a01:e0a:58b:4920:bd6e:5194:b82b:da55)
2020-11-22 14:46:00 <Feuermagier> halbGefressen, if you want, you can throw AC-3 at it and then brute-force on. but you'll have to change your datatype to something more sensible (I'd probably take a Map)
2020-11-22 14:46:19 × geekosaur quits (ac3a8c23@172.58.140.35) (Ping timeout: 245 seconds)
2020-11-22 14:46:44 <Feuermagier> halbGefressen, there's also https://wiki.haskell.org/Sudoku#Backtrack_monad_solver
2020-11-22 14:46:44 × chkno quits (~chkno@75-7-2-127.lightspeed.sntcca.sbcglobal.net) (Read error: Connection reset by peer)
2020-11-22 14:46:53 → chkno joins (~chkno@75-7-2-127.lightspeed.sntcca.sbcglobal.net)
2020-11-22 14:46:58 <halbGefressen> yea, I read that a little as well
2020-11-22 14:47:04 <halbGefressen> but i wanna do it myself haha
2020-11-22 14:47:10 → knupfer joins (~Thunderbi@mue-88-130-61-241.dsl.tropolys.de)
2020-11-22 14:47:21 × Tario quits (~Tario@201.192.165.173) (Read error: Connection reset by peer)
2020-11-22 14:47:34 × elfets_ quits (~elfets@ip-37-201-23-96.hsi13.unitymediagroup.de) (Quit: Leaving)
2020-11-22 14:48:47 <ski> two observations that can be used to prune, inform the choices, are (a) there can't be duplicates in a row (/ column / block); (b) every value has to appear in a row (/ column / block). so, for each cell, you can keep track of the values which could still conceivably appear in it (not being forbidden by (a)), and if a value can only occur in one of the cells in a row (/ ...), then it must occur there
2020-11-22 14:49:45 × geowiesnot quits (~user@i15-les02-ix2-87-89-181-157.sfr.lns.abo.bbox.fr) (Ping timeout: 240 seconds)
2020-11-22 14:49:57 <Feuermagier> halbGefressen, If you are looking for the proper approach I suggest taking a look at chapter 6.1 of "Artificial Intelligence A Modern Approach" by Stuart Russell (page 378 for sudokus)
2020-11-22 14:50:10 × polyphem quits (~p0lyph3m@2a02:810d:640:776c:76d7:55f6:f85b:c889) (Read error: Connection reset by peer)
2020-11-22 14:50:37 → neiluj joins (~jco@91-167-203-101.subs.proxad.net)
2020-11-22 14:50:37 × neiluj quits (~jco@91-167-203-101.subs.proxad.net) (Changing host)
2020-11-22 14:50:37 → neiluj joins (~jco@unaffiliated/neiluj)
2020-11-22 14:50:37 <ski> the latter (b) part can be generalized. if there are two cells (in the same row / ...) where only `3' and `5' can occur, then you can remove `3' and `5' from the possibilities from the other cells (in the same row / ...)
2020-11-22 14:50:38 → jonatanb joins (jonatanb@gateway/vpn/protonvpn/jonatanb)
2020-11-22 14:53:17 × da39a3ee5e6b4b0d quits (~da39a3ee5@2403:6200:8876:6c06:c056:20b8:f8ee:6530) (Quit: My MacBook has gone to sleep. ZZZzzz…)
2020-11-22 14:53:29 <ski> this can lead to a Constraint Programming (CP) approach to solving it, where each cell keeps track of a domain of possible values, and there are (a) and (b) constraints that, when a change (shrinking) occurs in the domain of one of the cells involved in the constraint, then (possibly) the constraint will propagate some further shrinking to some of the other cells in the constraint
2020-11-22 14:53:46 → noCheese joins (~nocheese@gw2.aibor.de)
2020-11-22 14:53:46 × noCheese quits (~nocheese@gw2.aibor.de) (Changing host)
2020-11-22 14:53:46 → noCheese joins (~nocheese@unaffiliated/nocheese)
2020-11-22 14:54:05 <Feuermagier> since my question probably disappeared; how can i find the (y,x) index of an element in a 2d list? [[int]] -> int -> maybe (int,int)
2020-11-22 14:54:47 → geekosaur joins (ac3a8c23@172.58.140.35)
2020-11-22 14:54:54 <ski> then, after all constraints have propagated a change, you start looking for a cell to nondeterministically fill (e.g. a cell with a minimal number of possibilities)
2020-11-22 14:55:05 × shailangsa quits (~shailangs@host86-186-177-233.range86-186.btcentralplus.com) (Ping timeout: 240 seconds)
2020-11-22 14:55:09 × kuribas quits (~user@ptr-25vy0i8mmgylw13a4p4.18120a2.ip6.access.telenet.be) (Quit: ERC (IRC client for Emacs 26.3))
2020-11-22 14:55:21 → erisco joins (~erisco@d24-57-249-233.home.cgocable.net)
2020-11-22 14:56:01 hackage servant 0.18.2 - A family of combinators for defining webservices APIs https://hackage.haskell.org/package/servant-0.18.2 (maksbotan)
2020-11-22 14:56:07 × erisco quits (~erisco@d24-57-249-233.home.cgocable.net) (Client Quit)
2020-11-22 14:57:01 hackage servant-server 0.18.2, servant-http-streams 0.18.2, servant-foreign 0.15.3, servant-docs 0.11.8, servant-client-core 0.18.2, servant-client 0.18.2 (maksbotan)
←Prev  Next→
Page 1 .. 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 .. 5022

All times are in UTC.