2012-10-09T00:13:12 *** mleise has quit IRC (Quit: Leaving.) 2012-10-09T00:39:19 *** antimatroidl has joined #aichallenge 2012-10-09T01:21:07 *** mceier has quit IRC (Quit: leaving) 2012-10-09T01:31:13 *** grc has joined #aichallenge 2012-10-09T02:29:00 *** amstan has quit IRC (Quit: Konversation terminated!) 2012-10-09T02:29:38 *** pairofdice has joined #aichallenge 2012-10-09T03:01:17 *** epicmonkey has joined #aichallenge 2012-10-09T03:11:00 *** mlp has joined #aichallenge 2012-10-09T03:14:28 *** grc has quit IRC (Quit: This computer has gone to sleep) 2012-10-09T03:15:03 *** mceier has joined #aichallenge 2012-10-09T03:21:13 *** epicmonkey has quit IRC (Ping timeout: 246 seconds) 2012-10-09T03:23:25 *** antimatroidl has quit IRC (Ping timeout: 245 seconds) 2012-10-09T03:27:43 *** antimatroidl has joined #aichallenge 2012-10-09T03:53:04 *** seswu has joined #aichallenge 2012-10-09T03:59:40 *** grc has joined #aichallenge 2012-10-09T04:13:13 *** coeus has quit IRC (Ping timeout: 260 seconds) 2012-10-09T04:32:39 *** epicmonkey has joined #aichallenge 2012-10-09T04:44:43 *** grc has joined #aichallenge 2012-10-09T04:47:41 *** sigh has joined #aichallenge 2012-10-09T04:50:16 *** InsaneMalkavian has joined #aichallenge 2012-10-09T04:55:43 *** seswu is now known as Seswu_AFK 2012-10-09T05:32:03 *** Seswu_AFK is now known as Seswu 2012-10-09T05:33:35 *** antimatroidl has quit IRC (Ping timeout: 244 seconds) 2012-10-09T05:37:20 *** grc has quit IRC (Quit: Leaving) 2012-10-09T05:38:56 *** antimatroidl has joined #aichallenge 2012-10-09T05:53:28 *** Seswu has quit IRC (Quit: Leaving) 2012-10-09T05:57:02 *** Fearless has joined #aichallenge 2012-10-09T05:58:59 *** Fearless has quit IRC (Client Quit) 2012-10-09T06:01:08 *** binw has quit IRC (Remote host closed the connection) 2012-10-09T06:30:40 *** Scooper has joined #aichallenge 2012-10-09T07:11:52 *** epicmonkey has quit IRC (Ping timeout: 246 seconds) 2012-10-09T07:23:01 *** epicmonkey has joined #aichallenge 2012-10-09T07:51:20 *** epicmonkey has quit IRC (Ping timeout: 276 seconds) 2012-10-09T07:56:21 *** InsaneMalkavian has quit IRC (Ping timeout: 245 seconds) 2012-10-09T08:06:25 *** epicmonkey has joined #aichallenge 2012-10-09T08:15:18 *** thestinger has joined #aichallenge 2012-10-09T08:17:11 *** mleise has joined #aichallenge 2012-10-09T08:22:44 *** mcstar has joined #aichallenge 2012-10-09T08:34:52 *** pairofdice has quit IRC (Quit: In girum imus nocte et consumimur igni.) 2012-10-09T08:35:48 *** pairofdice has joined #aichallenge 2012-10-09T08:42:15 mcstar: The bug I had yesterday... it's gone! I can now produce valid solutions. And I kept the validator in. It doesn't take away too much processing time anyway. 2012-10-09T08:43:00 good 2012-10-09T08:43:04 The correct algorithm now doesn't run in 600ms for the top95 any more. It runs 13 times faster. :p 2012-10-09T08:43:17 amazing 2012-10-09T08:44:15 there must be some temporal anomaly in space where you live :D 2012-10-09T08:46:33 I just read on a blog: "The basic idea behind these fast solvers is simple: we select the cell or the constraint with the minimum choices, fix to one number and move forward" 2012-10-09T08:46:52 Did you come up with that idea yourself ? 2012-10-09T08:47:26 well, its not rocket science 2012-10-09T08:47:29 I integrated it, too when you mentioned it. 2012-10-09T08:47:44 im trying to write a new one 2012-10-09T08:47:47 im failing 2012-10-09T08:48:16 It wasn't obvious to me that the square with minimum choices is the fastest way to find a solution 2012-10-09T08:49:06 it gives you minimal branching 2012-10-09T08:50:53 mcstar has a blog? 2012-10-09T08:51:09 i have, but that is irrelevant 2012-10-09T08:51:22 "I just read on a blog" 2012-10-09T08:51:41 mleise | Did you come up with that idea yourself ? 2012-10-09T08:51:54 we talked about is yesterday 2012-10-09T08:51:59 thestinger: yes, mcstar posted this idea yesterday on the chat here 2012-10-09T08:52:00 and i said something to him 2012-10-09T08:52:11 and today I found the same on some unrelated blog 2012-10-09T08:52:16 *** pairofdice has quit IRC (Quit: In girum imus nocte et consumimur igni.) 2012-10-09T08:52:36 *** pairofdice has joined #aichallenge 2012-10-09T08:54:05 "It is the great variability in algorithms and implementations that makes Sudoku fascinating." 2012-10-09T08:56:34 the author also posts his benchmark file: https://raw.github.com/attractivechaos/plb/master/sudoku/sudoku.txt 2012-10-09T08:58:08 O.o I am unable to solve the last one 2012-10-09T08:58:46 mleise: tell your computer to update the user 2012-10-09T08:59:24 but my program seems to be at least 5 times faster than any of the other programs he benchmarked 2012-10-09T09:00:00 oh wait... 1000 sudokus ? 2012-10-09T09:00:04 shit 2012-10-09T09:00:41 rollercoaster 2012-10-09T09:04:45 thestinger: http://fc20630405.wordpress.com/ stay tuned, ill publish my hot computer science articles here 2012-10-09T09:07:25 mcstar: http://ethanschoonover.com/solarized :P 2012-10-09T09:07:54 whats the apropo? 2012-10-09T09:08:23 the background color 2012-10-09T09:08:40 pink? 2012-10-09T09:08:46 ish 2012-10-09T09:08:53 cherrypink? 2012-10-09T09:09:02 idk 2012-10-09T09:11:09 thestinger: maybe im just plain stupid, but i dont understand what you are trying to tell me 2012-10-09T09:11:26 whats wrong with that background? 2012-10-09T09:11:30 it doesnt flicker 2012-10-09T09:11:59 (also, i dont like solarize, tried it, but....) 2012-10-09T09:12:00 no I'm saying you should use solarized light for your blog 2012-10-09T09:12:03 mcstar: oh 2012-10-09T09:12:07 nah 2012-10-09T09:18:27 mleise: i think its working 2012-10-09T09:18:51 what is working? 2012-10-09T09:19:13 my new code 2012-10-09T09:19:47 probably it sucks though 2012-10-09T09:20:11 needs a bit of tuning 2012-10-09T09:25:21 so slow 2012-10-09T09:26:09 http://attractivechaos.wordpress.com/2011/06/19/an-incomplete-review-of-sudoku-solver-implementations/ 2012-10-09T09:26:54 no thanks 2012-10-09T09:26:56 mine would take ~4 seconds for his benchmark (i compared cpu speeds by running fast_solv_9r2 on my computer) 2012-10-09T09:27:06 i need to apply my 'good idea' to speed it up 2012-10-09T09:27:27 He just mentions some buzz words, the actual implementations aren't shown 2012-10-09T09:28:05 btw. Norvigs solver takes 147 seconds and stops at the first solution 2012-10-09T09:28:06 yay 2012-10-09T09:28:11 im doing backtracking too 2012-10-09T09:28:52 so, his implementation isnt that fast after all? 2012-10-09T09:28:59 it is WAAAYY slow 2012-10-09T09:29:25 even othe Python implementations beat his code by almost an order of magnitude as you can see 2012-10-09T09:30:04 but his is probably the fastest clean Python code ;) 2012-10-09T09:32:11 *** amstan has joined #aichallenge 2012-10-09T09:32:11 *** ChanServ sets mode: +o amstan 2012-10-09T09:39:36 *** UncleVasya has joined #aichallenge 2012-10-09T09:47:00 mleise: http://sprunge.us/SPhN?haskell 2012-10-09T09:47:02 mcstar: ok, Boris Borcic's solver assumes that there is a unique solution to the puzzle. 2012-10-09T09:47:05 can you give me yours? 2012-10-09T09:47:16 http://dpaste.dzfl.pl/728800e3 2012-10-09T09:47:35 yes, yes, 500 loc 2012-10-09T09:48:21 mleise: your code is so long, the browser cant even load it 2012-10-09T09:48:26 XD 2012-10-09T09:48:27 oh come one ^^ 2012-10-09T09:48:31 j/k 2012-10-09T09:49:00 mleise: you wrote all that yesterday evening? 2012-10-09T09:49:35 this is the file that cannot be loaded because of its size: https://github.com/D-Programming-Language/phobos/blob/master/std/datetime.d 2012-10-09T09:49:48 mcstar: no, I started one day earlier 2012-10-09T09:52:54 mleise: can you send me a binary? 2012-10-09T09:53:07 sure wait a sec 2012-10-09T09:53:14 do you have dropbox by chance? 2012-10-09T09:53:23 i think i do 2012-10-09T09:53:29 but dont ask me to use it 2012-10-09T09:53:36 or 2012-10-09T09:53:40 i can try to log in 2012-10-09T09:53:50 http://ompldr.org/ 2012-10-09T09:53:51 it has a nice client for Linux Desktops 2012-10-09T09:54:28 im in 2012-10-09T09:54:36 "powered by 631 scientologist nerds" ^^ 2012-10-09T09:54:42 good god, theres an upside to consistent paswwords 2012-10-09T09:54:51 http://ompldr.org/vZnQ4eQ/SudokuSolver 2012-10-09T09:55:12 mleise: why did i log into dropbox then? 2012-10-09T09:55:44 we can still create a shared folder in there 2012-10-09T09:55:55 d'awww sharing 2012-10-09T09:59:14 mcstar: I invited you to the shared folder 'programming' 2012-10-09T10:00:24 mleise: what should i do? 2012-10-09T10:00:36 oh 2012-10-09T10:00:38 check your email 2012-10-09T10:00:39 i have a message 2012-10-09T10:01:19 i have to verify y email first 2012-10-09T10:02:35 *** sigh has quit IRC (Remote host closed the connection) 2012-10-09T10:04:25 *** epicmonkey has quit IRC (Ping timeout: 246 seconds) 2012-10-09T10:11:35 I updated the program. I accidentially left the iterations @ 50. 2012-10-09T10:11:53 mleise: what iterations? 2012-10-09T10:12:11 it solves all the input puzzles 50 times in a row 2012-10-09T10:12:13 why is that an input parameter? 2012-10-09T10:12:16 ah 2012-10-09T10:12:17 ok 2012-10-09T10:15:51 that dropbox client app keeps the files in sync in ~/Dropbox, which is quite nice 2012-10-09T10:17:04 mleise: haha, my latest solver leaves the first one of the hards untouched 2012-10-09T10:17:18 *** epicmonkey has joined #aichallenge 2012-10-09T10:17:30 it knows when to give up :) 2012-10-09T10:18:54 oh, i know why 2012-10-09T10:19:09 i put in place a stupid condition, that obviously doesnt hold 2012-10-09T10:19:15 for sparse enough puzzles 2012-10-09T10:20:31 *** thestinger has quit IRC (Ping timeout: 246 seconds) 2012-10-09T10:24:34 I've tried removing givens from one of the puzzles. It quickly reaches a point where the runtime goes through the roof, but then again there are millions of solutions 2012-10-09T10:39:34 *** thestinger has joined #aichallenge 2012-10-09T10:45:38 *** InsaneMalkavian has joined #aichallenge 2012-10-09T10:55:56 mleise: "Neither he nor I cannot prove this" 2012-10-09T10:56:51 I read that section 2012-10-09T10:57:32 oh look our condition holds for 1000 puzzles [with exactly 1 solution], it must be correct 2012-10-09T10:58:10 mleise: i meant, he wanted to write 'can', probably 2012-10-09T10:58:36 hehe, that typo ... i must have skipped it visually 2012-10-09T10:58:39 *** asdfsfaf has joined #aichallenge 2012-10-09T10:58:47 mleise: i solved the 20 hard ones 2012-10-09T10:58:57 hang on to something 2012-10-09T10:59:03 me, too. looks like the comments killed my parser the first time. 2012-10-09T10:59:16 it took 9150 seconds 2012-10-09T10:59:25 O.o 2012-10-09T10:59:27 366/2*50 2012-10-09T10:59:51 div 2 ??? 2012-10-09T10:59:57 1ghz 2012-10-09T11:00:31 *** mceier has quit IRC (Quit: leaving) 2012-10-09T11:00:57 well the positive side to this is: you are better than the worst ever possible sudoku solver in the world: Sudoku_6l 2012-10-09T11:01:12 thanks 2012-10-09T11:01:21 :S 2012-10-09T11:01:50 is that your 'new' solver or the old one ? 2012-10-09T11:01:56 new 2012-10-09T11:02:11 mleise: it has 1 table, that it updates destructively 2012-10-09T11:02:27 and a list of changes, on which it can backtrack 2012-10-09T11:02:29 thats it 2012-10-09T11:02:29 what's wrong with that? 2012-10-09T11:02:52 mleise: the problem, is that its too slow? 2012-10-09T11:02:57 well my list of changes is a recursive function call to solve(), but otherwise... 2012-10-09T11:03:13 *** thestinger has quit IRC (Quit: WeeChat 0.3.9) 2012-10-09T11:03:29 so you reduce the memory footprint by keeping a list of changes instead of copying the whole state ? 2012-10-09T11:04:04 *** asdfsfaf has quit IRC (Quit: Page closed) 2012-10-09T11:04:16 you could say that 2012-10-09T11:04:19 you should use more mutable state 2012-10-09T11:04:31 im using enough 2012-10-09T11:04:41 there would be no benefit from more 2012-10-09T11:04:45 hehe, and are all your lists dynamic? 2012-10-09T11:04:51 i have 90%+ productivity 2012-10-09T11:04:56 the gc is sleeping 2012-10-09T11:05:10 a list is a list 2012-10-09T11:05:17 what do you mean by dynamic? 2012-10-09T11:06:01 For example my stack of "known cells" has a fixed length of 81 2012-10-09T11:06:39 i have a 2d array with 2^(n-1) numbers 2012-10-09T11:06:43 I never need to copy that stack memory around, since I just overwrite in push() 2012-10-09T11:07:09 argh, with 81 numbers, but the mapping is n -> 2^(n-1) 2012-10-09T11:07:46 by that stack I mean the one where I place the initial givens and later on any other fixed value I find or "make up" when entering a recursion. 2012-10-09T11:08:29 2^^80 ? 2012-10-09T11:10:49 i dont use fixed values so to speak 2012-10-09T11:10:57 the changes are on the stack 2012-10-09T11:11:01 it can be unwound 2012-10-09T11:11:37 that means every state change can be rolled back ? 2012-10-09T11:11:49 > the worst ever possible sudoku solver I'm gonna to make one too :) 2012-10-09T11:12:19 mleise: yeah 2012-10-09T11:12:19 your use of wanna and gonna is still puzzling enough :p 2012-10-09T11:13:10 I thought gonna = going, wanna = want :D 2012-10-09T11:13:19 remember, there can only be ONE slowes sudoku solver in the world! FIGHT! 2012-10-09T11:13:24 slowest* 2012-10-09T11:13:49 UncleVasya: i am going to => im gonna 2012-10-09T11:13:58 you dont need that other 'to' 2012-10-09T11:14:16 ok, ty 2012-10-09T11:24:13 mleise: i play a couple of games, with ksudoku, maybe ill figure out what am i missing 2012-10-09T11:26:25 e.g. you try to find a new strategy by manually solving puzzles ? 2012-10-09T11:26:59 i just havent played it in a long time 2012-10-09T11:27:12 and there is some triviality that im doing wrong in my code 2012-10-09T11:27:16 it is waay too slow 2012-10-09T11:27:30 yes it is ... brute force like 2012-10-09T11:27:46 mleise: what does it exactly mean here? 2012-10-09T11:28:14 plugging in all the possible values for all the squares and branching on that? 2012-10-09T11:28:22 yes 2012-10-09T11:28:31 so, you call a deep first search bruteforce? 2012-10-09T11:28:36 depth* 2012-10-09T11:28:41 um, i guess so, yes 2012-10-09T11:28:46 ok 2012-10-09T11:29:07 i dont know what is the non-bruteforce version then :) 2012-10-09T11:29:16 there may be alterations, like branching on the cell with fewest possibilities firs 2012-10-09T11:29:27 yeah, but i have that 2012-10-09T11:29:54 non-brute force is eliminating obviously wrong candidates, like two adjacent '2's 2012-10-09T11:30:39 it cannot happen in my case 2012-10-09T11:30:49 it is eliminated automatically 2012-10-09T11:30:59 I keep 4 tables updated and in sync to find such invalid options 2012-10-09T11:31:10 i dont understand 2012-10-09T11:31:27 or rather to eliminate them autimatically 2012-10-09T11:31:29 i mean, my algorithm doesnt even think about doing that 2012-10-09T11:32:04 mleise: when i pick an empty square, i check the row/column/block to only choose from allowed numbers 2012-10-09T11:32:19 i fetch a known cell from the stack (which holds exactly one entry when I enter a recursion), and eliminate possiblilities from the 4 different tables 2012-10-09T11:32:23 i stop, and backtrack, if for a en empty square there is no possible numbr 2012-10-09T11:32:44 right, that's what I do too. those are 3 of my tables 2012-10-09T11:33:08 and then I have another one which holds for _each cell_ which digits are available there. 2012-10-09T11:33:25 e.g. cell[0]: 1,4,7,8 2012-10-09T11:33:27 i dont store such things 2012-10-09T11:33:36 everything is computed when needed 2012-10-09T11:33:47 1 table + 1 stack 2012-10-09T11:33:54 I considered dropping that table, but the algorithm got twice as slow 2012-10-09T11:34:09 but mine is crazy slow! 2012-10-09T11:34:15 like crazzzy 2012-10-09T11:34:24 craaaazy 2012-10-09T11:35:25 you reiterate the block, col and row for every cell you check ? store that in a table! 2012-10-09T11:35:55 Make your code longer 2012-10-09T11:36:03 i refuse to do that! 2012-10-09T11:36:31 Caching is not the root of all evil. 2012-10-09T11:36:45 lol 2012-10-09T11:36:50 i cant even solve a real sodoku 2012-10-09T11:37:00 It will be at least 4 times as fast with that optimization 2012-10-09T11:37:01 ksudoku highlight a square in red 2012-10-09T11:37:08 and i dont see why 2012-10-09T11:37:23 mleise: i want 400 2012-10-09T11:37:31 or more 2012-10-09T11:37:42 I said "at least" ^^ 2012-10-09T11:38:08 just to clarify, what does your one table contain ? 2012-10-09T11:38:24 powers of 2 2012-10-09T11:38:37 basically the input numbers 2012-10-09T11:38:51 in the format 2^(n-1) 2012-10-09T11:39:18 so that i can calculate the allowed numbers for a square without using a set or hashtable or whatever 2012-10-09T11:39:27 im just ORing numbers together 2012-10-09T11:39:29 ah, ok. so it is a bitmask 2012-10-09T11:40:39 "input numbers" in this case means, the table contains numbers with exectly 1 set bit for every cell in the grid that has a known value ? 2012-10-09T11:41:26 do you update the table when you 'fix' a cell to a value ? 2012-10-09T11:41:51 i update a square from the list of possibilities 2012-10-09T11:42:06 and i store the choices on the stack 2012-10-09T11:43:13 so by oring the values in the table for a row/cell/block you get a mask where a 0 bit means, that this digit is still free to use, right? 2012-10-09T11:43:38 yes 2012-10-09T11:43:52 im XORing that with a full of 1s 2012-10-09T11:43:53 and cells with multiple options are 0 2012-10-09T11:44:02 and split those to individual numbers 2012-10-09T11:44:11 yes 2012-10-09T11:45:05 alright, now what about storing the result of this calculation instead ? 2012-10-09T11:45:17 e.g. each cell contains the bits of possible values 2012-10-09T11:45:49 mleise: but this changes 2012-10-09T11:46:05 and the backtracking saves the non-changing part 2012-10-09T11:46:15 :-/ 2012-10-09T11:46:22 let me illustrate 2012-10-09T11:46:38 ((r,c),[1,2,3,4]) 2012-10-09T11:46:44 thats one entry on the stack 2012-10-09T11:46:49 *** thestinger has joined #aichallenge 2012-10-09T11:46:50 it means i set r,c to 1 2012-10-09T11:47:00 now i go, and find another empty site 2012-10-09T11:47:29 if by doing the smae thing, i hit no alternatives situation i backtrack 2012-10-09T11:47:37 if i backtrack to the value that i showed 2012-10-09T11:47:44 ill store this next: 2012-10-09T11:47:50 ((r,c),[2,3,4]) 2012-10-09T11:47:57 so now, i set (r,c) to 2 2012-10-09T11:48:14 do this until i only have 1 element in the list 2012-10-09T11:48:18 ((r,c),[4]) 2012-10-09T11:48:24 *** Eibwen_ has joined #aichallenge 2012-10-09T11:48:28 that triggers another backtracking 2012-10-09T11:49:40 ok I think I get the picture. that's a nice solution to write short code. 2012-10-09T11:49:56 as you can see, it is not really short 2012-10-09T11:49:57 *** mlp has quit IRC (Quit: Page closed) 2012-10-09T11:50:01 more like huge! 2012-10-09T11:50:30 *** Eibwen has quit IRC (Ping timeout: 245 seconds) 2012-10-09T11:50:34 *** Eibwen_ is now known as Eibwen 2012-10-09T11:51:19 I haven't looked at what tables others use, but mine are all like your table: they store bit flags 2012-10-09T11:52:05 one stores bits for 1..9 (the values) others store possible occurance of a certain value inside a block,row or column. 2012-10-09T11:52:33 When I update all 4 of them, they have one thing in common: 0 bits in a table cell means: backtrack 2012-10-09T11:52:48 1 bit left means: I have another cell in my sudoku solved 2012-10-09T11:53:45 e.g. in row 2 there may be two cells that can hold the '6': the 1st and the 6th. 2012-10-09T11:54:39 now I know that in the 6th cell there is a '3', so I update the 'row' table, and remove the option of '6' for the 6th cell. 2012-10-09T11:55:16 That leaves me with one bit in that row for the value '6': It must be placed in the 1st cell. 2012-10-09T11:56:44 [6?, , , , ,6?, , , ] -> [6?, , , , ,3, , , ] -> [6!, , , , ,3, , , ] 2012-10-09T11:58:07 That's where my code got longer and longer. This immediate updating of the tables turned out to have quite a few cases. 2012-10-09T12:00:09 mleise: i think i should just fix my alg. from yesterday 2012-10-09T12:07:55 mcstar: I think you need a way to reduce the branching factor before you go into recursion 2012-10-09T12:08:17 dont we all want that? XD 2012-10-09T12:08:36 mleise: and i dont 'go into recursion' 2012-10-09T12:08:51 my recursion is an iteration 2012-10-09T12:09:27 mleise: the problem is, that i want to avoid writing code, that keeps track of stuff, like you did 2012-10-09T12:09:31 it is too tedious to my taste 2012-10-09T12:09:49 yes, it was tedious. i hated it. 2012-10-09T12:10:12 it was like copy&paste, but with subtle changes between the row, col and block tables 2012-10-09T12:10:29 mleise: how good is it yours, on that benchmark? 2012-10-09T12:10:39 4 secs? 2012-10-09T12:11:00 yes, if I compare that fast_solv_... thing on his and my computer 2012-10-09T12:11:28 16x slower than the best 2012-10-09T12:11:30 still 16 times slower than the top entry. that's just crazy 2012-10-09T12:11:32 thats very good 2012-10-09T12:11:49 mleise: i think that guy didnt come up with that program overnight 2012-10-09T12:11:54 I don't want to know what algorithm that guy used 2012-10-09T12:13:15 UncleVasya: Are you still hacking ? 2012-10-09T12:14:59 by 'I'm gonna' I meant in few weeks :) 2012-10-09T12:15:29 mcstar: the fact alone that there is a Java implementation, that's faster is a thorn in my eyes :D 2012-10-09T12:15:47 hehe 2012-10-09T12:16:07 and JavaScript... only a little slower 2012-10-09T12:17:49 with these things, algorithm matter smost 2012-10-09T12:18:06 mleise: but even then, java would beat D 2012-10-09T12:18:19 fact of life 2012-10-09T12:18:28 XD 2012-10-09T12:41:39 *** mleise has quit IRC (Quit: Leaving.) 2012-10-09T12:42:18 *** mleise has joined #aichallenge 2012-10-09T12:44:22 *** epicmonkey has quit IRC (Ping timeout: 246 seconds) 2012-10-09T12:45:09 *** thestinger has quit IRC (Read error: Connection reset by peer) 2012-10-09T12:49:00 *** mleise has quit IRC (Quit: Leaving.) 2012-10-09T13:09:15 *** smjm has joined #aichallenge 2012-10-09T13:09:15 *** smjm has joined #aichallenge 2012-10-09T13:17:24 *** thestinger has joined #aichallenge 2012-10-09T13:23:29 *** jacob_strauss has joined #aichallenge 2012-10-09T13:36:57 *** mceier has joined #aichallenge 2012-10-09T13:48:46 *** epicmonkey has joined #aichallenge 2012-10-09T13:49:55 *** mleise has joined #aichallenge 2012-10-09T13:51:55 *** foRei has joined #aichallenge 2012-10-09T14:29:44 *** insanemalkavian_ has joined #aichallenge 2012-10-09T14:33:42 *** pairofdice has quit IRC (Quit: In girum imus nocte et consumimur igni.) 2012-10-09T14:37:35 mleise: :) 2012-10-09T14:37:46 mleise: i might have written something interesting 2012-10-09T14:38:01 define interesting 2012-10-09T14:38:58 let me run the tests 2012-10-09T14:42:27 mleise: 85ms for the easy 50 2012-10-09T14:42:55 hey, not bad at all. what did you do? 2012-10-09T14:43:10 lol 2012-10-09T14:43:13 wait wtf 2012-10-09T14:43:19 the hard 20 took almost no time 2012-10-09T14:43:34 40ms 2012-10-09T14:43:59 mleise: i just perfected my immutable algorithm from yesterday 2012-10-09T14:44:07 *** iglo has joined #aichallenge 2012-10-09T14:44:31 ill run the hard 20 for 50 times 2012-10-09T14:45:53 *** dici has joined #aichallenge 2012-10-09T14:46:08 hi guys, UncleVasya told me you work on sudoku solver. 2012-10-09T14:46:27 mleise: 3.14/2=1.57 ! 2012-10-09T14:46:36 insanemalkavian_: yes, and mcstar is just about to beat my version on 'hard' difficulty setting 2012-10-09T14:46:36 the hard 20 repeated 50 times 2012-10-09T14:47:07 mleise: 86 lines 2012-10-09T14:47:38 this makes me sad :-( what is your secret ? 2012-10-09T14:47:42 http://sprunge.us/RdME?haskell 2012-10-09T14:47:47 do you have a binary so I can compare it to my solver? I did it several years ago. 2012-10-09T14:48:07 insanemalkavian_: hi, welcome back 2012-10-09T14:48:28 hi mcstar 2012-10-09T14:48:35 *windows binary 2012-10-09T14:49:14 exactly! 2012-10-09T14:49:37 mcstar: I've uploaded benchmark.txt to the Dropbox, how does my program compare to yours on your computer right now ? 2012-10-09T14:49:53 benchmark.txt is the 20 puzzles repeated 50 times 2012-10-09T14:54:16 mleise: omg, i thought i fucked up something 2012-10-09T14:54:27 since yours gives different result 2012-10-09T14:54:35 turns out, my output is transposed :) 2012-10-09T14:54:45 the matrix is rotated 2012-10-09T14:57:25 mleise: also, it DOES find a different solution for hard#1 for example 2012-10-09T14:57:54 that's odd. they are supposed to have exactly 1 solution 2012-10-09T14:57:57 this requires further testing 2012-10-09T14:58:26 did you feed the puzzle to mine in interactive mode ? 2012-10-09T14:58:48 mcstar: and it found only 1 solution ? 2012-10-09T14:59:24 mleise: i have a duplicate number 2012-10-09T14:59:57 a duplicate solution or an invalid solution ? 2012-10-09T15:00:17 duplicate number->invalid solution->non-solution 2012-10-09T15:11:45 *** InsaneMalkavian has quit IRC (Ping timeout: 245 seconds) 2012-10-09T15:12:59 jfyi, http://rghost.ru/40820481 win x86/x64 load -> solve 2012-10-09T15:14:42 *** Accoun has quit IRC () 2012-10-09T15:30:59 *** UncleVasya has quit IRC (Ping timeout: 246 seconds) 2012-10-09T15:40:43 *** Accoun has joined #aichallenge 2012-10-09T15:46:22 *** FireFly has quit IRC (Changing host) 2012-10-09T15:46:22 *** FireFly has joined #aichallenge 2012-10-09T15:46:23 *** epicmonkey has quit IRC (Ping timeout: 246 seconds) 2012-10-09T16:05:27 *** jacob_strauss has quit IRC (Quit: jacob_strauss) 2012-10-09T16:12:31 mcstar: my attempt at a short solver in 17 lines: http://dpaste.dzfl.pl/c76b9423 2012-10-09T16:13:03 whoa 2012-10-09T16:13:10 how fast is it? 2012-10-09T16:13:21 not fast ^^ 2012-10-09T16:14:13 7,4 seconds for hardest.txt 2012-10-09T16:17:06 still pretty good 2012-10-09T16:17:43 mleise: or, put another way, that super fast, only 2x slower than your 500loc one? 2012-10-09T16:18:23 I don't understand 2012-10-09T16:19:18 mleise: whats in hardest.txt? the 20 hard puzzle repeated 50 times? 2012-10-09T16:21:23 that google guy's 11 hardest puzzles 2012-10-09T16:22:54 now 11 2012-10-09T16:23:01 anyway 2012-10-09T16:23:09 for me thats fast and short 2012-10-09T16:23:39 the 20x50 benchmark would run for 4 hours with that program 2012-10-09T16:24:07 oh 2012-10-09T16:24:37 mleise: so, only a little slower than my mutable haskell one 2012-10-09T16:24:48 ;) 2012-10-09T16:24:55 thast 2.5hours 2012-10-09T16:25:12 mleise: i fixed the bug in my newest version 2012-10-09T16:32:06 *** amstan_ has joined #aichallenge 2012-10-09T16:32:06 *** ChanServ sets mode: +o amstan_ 2012-10-09T16:32:17 *** amstan has quit IRC (Read error: Connection reset by peer) 2012-10-09T16:32:36 mleise: this new version is 2x faster than the previous, would do the big test in 4200s 2012-10-09T16:38:04 mleise: from 4200s with one modification it runs now in 316.5s 2012-10-09T16:39:16 and it is still short ? 2012-10-09T16:39:33 not like your last one 2012-10-09T16:39:40 mine is the same as before 2012-10-09T16:39:55 ~80 lines 2012-10-09T16:40:12 i have 10 lines of imports too 2012-10-09T16:43:21 the code itself is ~46 lines 2012-10-09T16:43:55 mleise: http://sprunge.us/UALN?haskell this gives correct results i believe, same as yours 2012-10-09T16:51:05 *** amstan_ has quit IRC (Quit: Konversation terminated!) 2012-10-09T16:52:28 *** iglo has quit IRC (Remote host closed the connection) 2012-10-09T17:15:37 so is this the fastest correct solver you have and it takes 316.5 seconds ? 2012-10-09T17:15:56 mcstar: ^ 2012-10-09T17:16:12 yeah, 20 hard problems, 50 times 2012-10-09T17:16:31 mleise: im trying to fit in a priority-map 2012-10-09T17:16:46 to remove a costly sort 2012-10-09T17:17:34 mcstar: a single sort is faster than storing the values in a sorted container first 2012-10-09T17:17:36 mcstar: and when you're done micro-optimizing you may actually want to *reduce your branching* ;) 2012-10-09T17:18:01 thestinger: thank you for your input 2012-10-09T17:18:19 mleise: i dont think i can 2012-10-09T17:18:22 mcstar: do you build the whole map in advance? 2012-10-09T17:18:41 before accessing it 2012-10-09T17:18:53 im just keeping track of an element that is minimal in a sense, and update that if necessary with every insert 2012-10-09T17:19:20 so do you just have a value, or actually key-value pairs? 2012-10-09T17:19:23 *** foRei has quit IRC (Read error: Connection reset by peer) 2012-10-09T17:19:26 yes 2012-10-09T17:19:30 haha 2012-10-09T17:19:32 to which :P 2012-10-09T17:19:36 i have a map 2012-10-09T17:19:40 key->value 2012-10-09T17:19:43 what else is a map 2012-10-09T17:21:01 *** antimatroidl has quit IRC (Read error: No route to host) 2012-10-09T17:21:09 *** antimatroidl has joined #aichallenge 2012-10-09T17:22:10 it sounds very much like a priority queue 2012-10-09T17:22:52 but there is about dozen data structures for that 2012-10-09T17:23:12 heaps of them :P 2012-10-09T17:23:19 :D 2012-10-09T17:23:47 no 2012-10-09T17:23:54 i need only the tip 2012-10-09T17:24:01 that's what she said 2012-10-09T17:24:11 funny 2012-10-09T17:24:24 mcstar: the min value? 2012-10-09T17:24:30 why do you need a data structure at all then :P 2012-10-09T17:24:33 but that's what a priority queue does 2012-10-09T17:24:34 yeah 2012-10-09T17:24:48 no, it keeps all the elements sorted 2012-10-09T17:24:50 it gives you the top priority item at all times 2012-10-09T17:25:16 that's an implementation detail 2012-10-09T17:26:15 e.g. look at this implementation: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.3635 2012-10-09T17:26:21 now come on 2012-10-09T17:26:35 we are not talking about the same thing 2012-10-09T17:26:45 this element is like a watermark 2012-10-09T17:26:50 or this: http://howtovideo.eu/lazy-fixed-sized-priority-queue-implementation/ 2012-10-09T17:26:53 not a priority queue 2012-10-09T17:27:00 and i can use google too 2012-10-09T17:27:10 and i dont want to read about priority queues 2012-10-09T17:27:16 but you wouldn't have thought google yields results 2012-10-09T17:27:22 i read all about them when i was doing Ants 2012-10-09T17:27:29 A* 2012-10-09T17:27:49 alright then, do your watermark data structure 2012-10-09T17:27:57 :( 2012-10-09T17:28:54 is this just a 'current best' item ? 2012-10-09T17:30:18 what do you mean? 2012-10-09T17:30:41 do you only need to remember one best item + an unsorted list ? 2012-10-09T17:30:59 one best + the map, coordiantes to sets 2012-10-09T17:31:07 then what about comparing that with every new item you come across and updating it conditionally, while keeping a separate unsorted list ? 2012-10-09T17:31:33 mleise: thats exactly how i want to do it 2012-10-09T17:31:38 except that list part 2012-10-09T17:31:48 actually its all done for a while now 2012-10-09T17:31:58 i just have to refactor because i changed data strcture 2012-10-09T17:33:04 mleise: this can work, since im passing immutable data around, i.e. i can rewind, and this property(the possible numbers for a square) can only get lower, as i travel depth first 2012-10-09T17:34:31 right, cool. I'll copy that idea 2012-10-09T17:36:41 *** Scooper has quit IRC (Quit: Leaving) 2012-10-09T17:44:44 mcstar: there are still a few cases, where the 'current best' is invalid, because it's cell was already solved at the time of recursion/iteration 2012-10-09T17:45:21 yeah 2012-10-09T17:45:32 as soon as you solve it, its gone 2012-10-09T17:45:45 im thinking about just that 2012-10-09T17:45:47 alright, that was another 100ms, thx! 2012-10-09T17:46:21 (I'm just falling back to a search if the current best is invalid) 2012-10-09T17:46:23 mleise: am i the only one who doesnt benefit from his own ideas? 2012-10-09T17:47:37 i don't know. don't you get that delicious 6% speed improvement ? 2012-10-09T17:48:47 *** amstan has joined #aichallenge 2012-10-09T17:48:47 *** ChanServ sets mode: +o amstan 2012-10-09T17:50:51 *** coeus has joined #aichallenge 2012-10-09T17:52:12 *** insanemalkavian_ has quit IRC (Ping timeout: 245 seconds) 2012-10-09T17:56:12 *** cyphase has quit IRC (Ping timeout: 264 seconds) 2012-10-09T17:59:31 no 2012-10-09T18:00:21 thats it 2012-10-09T18:00:23 good night 2012-10-09T18:00:25 *** mcstar has quit IRC (Quit: mcstar) 2012-10-09T18:03:58 *** antimatroidl has quit IRC (Quit: Leaving.) 2012-10-09T18:09:26 *** cyphase has joined #aichallenge 2012-10-09T18:11:01 *** sigh has joined #aichallenge 2012-10-09T18:38:32 *** sigh has quit IRC (Remote host closed the connection) 2012-10-09T18:44:00 *** antimatroidl has joined #aichallenge 2012-10-09T18:55:01 *** dici has quit IRC (Read error: Connection reset by peer) 2012-10-09T19:00:18 *** antimatroidl has quit IRC (Quit: Leaving.) 2012-10-09T19:47:55 *** thestinger has quit IRC (Quit: WeeChat 0.3.9) 2012-10-09T19:49:37 *** aarossig has quit IRC (Remote host closed the connection) 2012-10-09T21:24:59 *** Apophis_ has quit IRC (Read error: Connection reset by peer) 2012-10-09T21:25:25 *** Apophis_ has joined #aichallenge 2012-10-09T21:27:21 *** smjm has quit IRC (Ping timeout: 268 seconds) 2012-10-09T22:06:48 *** mleise has quit IRC (Quit: Leaving.)