2012-10-11T00:16:37 *** thestinger has quit IRC (Ping timeout: 246 seconds) 2012-10-11T00:21:51 *** Garf has joined #aichallenge 2012-10-11T00:27:55 *** scribble has joined #aichallenge 2012-10-11T00:28:17 *** Garf has quit IRC (Quit: Make a new plan, Stan!) 2012-10-11T00:35:10 *** Garf has joined #aichallenge 2012-10-11T01:12:03 *** mceier has quit IRC (Quit: leaving) 2012-10-11T01:24:46 *** Areks has joined #aichallenge 2012-10-11T02:01:57 *** janzert has quit IRC (Read error: Connection reset by peer) 2012-10-11T02:25:52 *** mceier has joined #aichallenge 2012-10-11T02:52:29 *** epicmonkey has joined #aichallenge 2012-10-11T03:25:44 *** epicmonkey has quit IRC (Ping timeout: 272 seconds) 2012-10-11T03:30:15 *** mlp has joined #aichallenge 2012-10-11T03:40:12 *** antimatroidl has joined #aichallenge 2012-10-11T04:08:57 *** loglog has joined #aichallenge 2012-10-11T04:17:29 *** antimatroidl has quit IRC (Read error: No route to host) 2012-10-11T04:17:43 *** antimatroidl has joined #aichallenge 2012-10-11T04:31:01 *** epicmonkey has joined #aichallenge 2012-10-11T04:50:38 *** mcstar has joined #aichallenge 2012-10-11T04:52:22 *** janzert has joined #aichallenge 2012-10-11T05:34:49 *** smjm has joined #aichallenge 2012-10-11T05:34:49 *** smjm has joined #aichallenge 2012-10-11T05:49:33 *** mceier has quit IRC (Quit: leaving) 2012-10-11T06:50:59 *** Garf has quit IRC (Quit: Make a new plan, Stan!) 2012-10-11T06:56:23 *** sigh has joined #aichallenge 2012-10-11T07:00:49 *** antimatroidl1 has joined #aichallenge 2012-10-11T07:00:49 *** antimatroidl has quit IRC (Read error: Connection reset by peer) 2012-10-11T07:12:25 one more week of classes :D 2012-10-11T07:24:22 *** Scooper has joined #aichallenge 2012-10-11T07:43:10 *** antimatroidl1 has quit IRC (Ping timeout: 248 seconds) 2012-10-11T07:49:50 *** thestinger has joined #aichallenge 2012-10-11T07:50:09 *** epicmonkey has quit IRC (Ping timeout: 260 seconds) 2012-10-11T07:52:44 *** antimatroidl has joined #aichallenge 2012-10-11T07:59:12 *** alehorst has quit IRC (Ping timeout: 240 seconds) 2012-10-11T08:02:11 *** epicmonkey has joined #aichallenge 2012-10-11T08:08:31 *** alehorst has joined #aichallenge 2012-10-11T08:15:10 *** alehorst has quit IRC (Remote host closed the connection) 2012-10-11T08:33:47 *** epicmonkey has quit IRC (Read error: Operation timed out) 2012-10-11T08:35:08 *** sigh has quit IRC (Remote host closed the connection) 2012-10-11T08:50:37 *** epicmonkey has joined #aichallenge 2012-10-11T09:29:49 *** pairofdice has joined #aichallenge 2012-10-11T09:58:45 *** mceier has joined #aichallenge 2012-10-11T10:11:07 *** Areks has quit IRC () 2012-10-11T10:28:42 *** Areks has joined #aichallenge 2012-10-11T10:45:51 *** mleise has joined #aichallenge 2012-10-11T10:56:54 *** sh4wn has joined #aichallenge 2012-10-11T11:20:11 *** antimatroidl has quit IRC (Ping timeout: 255 seconds) 2012-10-11T11:51:00 *** mlp has quit IRC (Quit: Page closed) 2012-10-11T12:16:59 *** dici has joined #aichallenge 2012-10-11T12:21:24 *** amstan has joined #aichallenge 2012-10-11T12:21:24 *** ChanServ sets mode: +o amstan 2012-10-11T12:31:02 mleise: im around 95 seconds on the board 2012-10-11T12:37:37 the last one was somewhere in the 300, right ? 2012-10-11T12:38:30 no 2012-10-11T12:38:33 500 2012-10-11T12:38:44 and i worked on the one that did it in 300 2012-10-11T12:38:51 that went down to 95 2012-10-11T12:39:21 mleise: i wrote a totally new version, that had a bug, that i couldnt fix 2012-10-11T12:39:44 the code got too complicated... 2012-10-11T12:40:20 http://sprunge.us/ORDc?haskell 2012-10-11T12:40:27 this is the faulty one XD 2012-10-11T12:41:13 i set up maps for the 3 kinds of units 2012-10-11T12:42:27 oh no 100s of lines of code ^^ 2012-10-11T12:42:29 mleise: are you sub-second by now? 2012-10-11T12:42:42 no, I'm writing an interactive shell frontend :p 2012-10-11T12:42:51 for what? 2012-10-11T12:42:56 REPL for D? 2012-10-11T12:43:10 So I can visually follow the changes when I set a cell to a value. 2012-10-11T12:43:23 hm 2012-10-11T12:43:31 why is that important? 2012-10-11T12:43:43 anyway, i wouldnt do that in D 2012-10-11T12:43:44 for debugging and for fun 2012-10-11T12:44:03 what ? a regular expression language or a frontend? 2012-10-11T12:44:24 frontend 2012-10-11T12:44:38 thats something visual 2012-10-11T12:44:41 it's just a simple readln() command thingy 2012-10-11T12:44:48 oh 2012-10-11T12:44:55 i thought you'd follow the changes 2012-10-11T12:44:57 highlight stuff 2012-10-11T12:44:58 but I thought about using GtkD otherwise 2012-10-11T12:44:59 whatever 2012-10-11T12:45:29 no, I just want to print the actions taken and the final solver state (e.g which cell has which options left) 2012-10-11T12:56:52 *** dici has quit IRC (Quit: ( www.nnscript.com :: NoNameScript 4.22 :: www.esnation.com )) 2012-10-11T12:57:31 *** dici has joined #aichallenge 2012-10-11T12:58:20 mcstar: A REPL in LISP is one line of code. Very nice. But you are right, that's somthing for interpreted languages. 2012-10-11T12:58:45 (loop (print (eval (read)))) 2012-10-11T12:59:11 I _could_ use the interpreter in the compiler and read from a file instead of stdin through ;) 2012-10-11T12:59:44 that would look funny I think, because it's so _not_ what it was meant for 2012-10-11T13:08:01 *** foRei has joined #aichallenge 2012-10-11T13:12:56 mleise: you can have a REPL for a static language, it just has to use a JIT compiler 2012-10-11T13:13:02 or it has to compile as it goes 2012-10-11T13:13:10 (or an interpreter) 2012-10-11T13:13:21 ghci and cling (C++) do exist :P 2012-10-11T13:13:56 when D has taken over the world, it will get a JIT compiler 2012-10-11T13:14:11 igcc is just a hack that recompiles the whole thing you've input 2012-10-11T13:14:46 so doesn't handle errors well... 2012-10-11T13:17:49 by the time D gets a JIT it will be an outdated technology 2012-10-11T13:18:17 the next generation languages wont need a compiler 2012-10-11T13:18:43 Asm with type inference! 2012-10-11T13:18:47 wut? 2012-10-11T13:18:56 j/k 2012-10-11T13:19:39 rofl, I am about to kill the interpreter. I'm generating functions for every combination of grid cell and values ^^ 2012-10-11T13:20:27 *** epicmonkey has quit IRC (Ping timeout: 272 seconds) 2012-10-11T13:53:35 *** jacob_strauss has joined #aichallenge 2012-10-11T14:27:24 *** epicmonkey has joined #aichallenge 2012-10-11T14:51:51 *** amstan has quit IRC (Read error: Connection reset by peer) 2012-10-11T14:52:05 *** amstan has joined #aichallenge 2012-10-11T14:52:05 *** ChanServ sets mode: +o amstan 2012-10-11T15:02:58 *** thestinger has quit IRC (Quit: WeeChat 0.3.9) 2012-10-11T15:09:20 mleise: omg, using a priority queue to have access the element with the smallest number of possibilities is 2x SLOWER than just sorting my map of coordinates->sets on the set size 2012-10-11T15:09:54 *** Accoun has quit IRC () 2012-10-11T15:14:36 the problem is "a priority queue". as i said earlier different implementations exist for every purpose. funny enough Java uses a simple array as the "backend". 2012-10-11T15:15:02 (but uses it in a binary heap fashion) 2012-10-11T15:16:19 mcstar: you have exactly 81 elements. a priority queue implementation with a fixed size array is probably faster than the general purpose priority queue in Haskell 2012-10-11T15:16:57 bullshit 2012-10-11T15:17:10 not that 2012-10-11T15:17:13 the situation 2012-10-11T15:17:31 that priqueue is based on some map 2012-10-11T15:17:46 and im using the same kind of map, otherwise 2012-10-11T15:18:00 it cannot be slower 2012-10-11T15:18:03 cannot be 2012-10-11T15:18:06 no 2012-10-11T15:18:08 cannot 2012-10-11T15:20:02 does the _whole_ program slow down by a factor of 2 ?! 2012-10-11T15:20:43 yes 2012-10-11T15:20:43 mcstar: then it probably doesn't work correctly at all 2012-10-11T15:21:18 but if it wouldnt, then it would slow down more considerably 2012-10-11T15:21:27 hmm 2012-10-11T15:21:54 the depth of the search depends greatly on the order you select squares 2012-10-11T15:22:28 mleise: now, i plugged in another priqueue, based on finger trees, 8x slowdown 2012-10-11T15:22:30 I'm afraid, I know too little of how Haskell data structures work. Maybe there are more indirections 2012-10-11T15:22:44 wow, and that are the only two options in base haskel 2012-10-11T15:23:02 but what was wrong with you implementation anyway ? 2012-10-11T15:23:21 as you said, you don't need a sorted list of everything 2012-10-11T15:23:56 let me guess, you wanted to save a line of code? ^^ 2012-10-11T15:24:03 no 2012-10-11T15:24:21 i just want to pick the square with the lowest number of numbers 2012-10-11T15:25:08 Yes, and isn't that probably the cause of the slowdown? A 'normal' priority queue eagerly sorts all the entries. 2012-10-11T15:25:37 mleise: but that cannot be slower then a map -> list -> sort -> pick first element 2012-10-11T15:25:39 but maybe haskell is more lazy. I really lack the understanding 2012-10-11T15:25:56 oh right, you said that 2012-10-11T15:26:22 unless you sort *way* less than you update the priority queue 2012-10-11T15:26:37 i sort on every recursion 2012-10-11T15:26:47 and update the queue ? 2012-10-11T15:26:52 on every... ? 2012-10-11T15:27:18 when i fix a square 2012-10-11T15:27:18 *** Accoun has joined #aichallenge 2012-10-11T15:27:35 O.o 2012-10-11T15:27:47 shouldn't that be "when I remove an option from a square" ? 2012-10-11T15:28:01 thats the same 2012-10-11T15:28:09 i fix it to something 2012-10-11T15:28:37 maybe, it is inefficient to copy that psqueue around 2012-10-11T15:28:47 so that happens more often than an iteration/recursion, or not? 2012-10-11T15:28:51 and if i dont read from it, it remains unevaluated 2012-10-11T15:29:02 mleise: that depends on the branching factor 2012-10-11T15:29:11 1-9 2012-10-11T15:29:15 usually 1-2 2012-10-11T15:29:21 hmm, I don't know about this 'unevaluated' thing 2012-10-11T15:29:58 even haskell has to store the stuff you put into the queue somewhere 2012-10-11T15:30:31 yeah, on the heap 2012-10-11T15:30:35 in thunks 2012-10-11T15:30:43 which remains unevaluated 2012-10-11T15:31:00 the data structure will be a linear list of the constructor operations 2012-10-11T15:31:08 so it really just says "on evaluation, make sure these values on the heap get into the list" ? 2012-10-11T15:31:11 it will never form the real data structure in memory 2012-10-11T15:31:24 you explode by brain 2012-10-11T15:31:31 my* 2012-10-11T15:31:39 see 2012-10-11T15:32:58 but once you evaluate the list, it has to be in some usable form 2012-10-11T15:33:23 so you can call "get first element" on it 2012-10-11T15:35:26 anyway keeping just an updated "least branching square" is the fastest option no matter what. 2012-10-11T15:36:27 the lazy part here is that once you go into the iteration, you check if it is still valid and find a new one if not 2012-10-11T15:36:51 but i deal immediately with the smallest one 2012-10-11T15:37:03 i have to recompute on every recursion 2012-10-11T15:37:28 let me try another priqueue implementation 2012-10-11T15:37:38 this one is based on binomial heaps 2012-10-11T15:38:13 does it also sort the whole list before returning the smallest element ? 2012-10-11T15:40:18 what list? 2012-10-11T15:42:13 *** thestinger has joined #aichallenge 2012-10-11T15:42:52 the sequence 2012-10-11T15:43:05 whatever you call it, the list of squares 2012-10-11T15:44:38 mcstar: you know what? I'm gonna refactor some more. I think I should abstract from the notion of "row", "column" and "block". They all are just rectangular shapes with 9 squares 2012-10-11T15:45:03 I have way to many rowDoX and blockDoY functions 2012-10-11T15:46:23 *** epicmonkey has quit IRC (Ping timeout: 246 seconds) 2012-10-11T15:47:52 there are only a couple relations, that are different for blocks if I'm not mistaken. e.g. a block overlaps 3 rows and 3 columns, whereas a row/column overlaps 3 block, but 9 columns/rows 2012-10-11T15:52:28 why does that matter? 2012-10-11T15:53:34 I hope to generalize a lot of code, but I need to keep in mind where potential traps are. 2012-10-11T15:54:49 something basic: CellToShapeIdx(int cell, Shape shape) instead of seperate functions for every shape 2012-10-11T15:58:48 still sudoku? 2012-10-11T15:58:59 different variants now? :P 2012-10-11T16:02:51 this is crazy 2012-10-11T16:04:15 mleise: 136sec vs 12 2012-10-11T16:04:28 with the newest priqueue 2012-10-11T16:04:51 admittedly, i have to do a little more work with this one, since it doesnt support deletion 2012-10-11T16:05:17 mcstar: 10x faster ?! 2012-10-11T16:05:26 no 2012-10-11T16:05:30 11x? 2012-10-11T16:05:30 10x slower 2012-10-11T16:05:34 oh shit 2012-10-11T16:05:43 2x,8x,10x 2012-10-11T16:05:53 3 different priqueues :) 2012-10-11T16:06:56 ill just write a getMin for my map 2012-10-11T16:07:18 thestinger: Sudoku is nice, because the constraints are so clear. You can relatively easily find better algorithms. Unlike with like PlanetWars 2012-10-11T16:07:37 *-like 2012-10-11T16:08:06 you like not unlike planet like war kind of like? 2012-10-11T16:08:09 Now I just wonder when the compiler will eat up all my memory for my compile time stuff ^^ 2012-10-11T16:14:21 *** thestinger has quit IRC (Read error: Connection reset by peer) 2012-10-11T16:21:06 mleise: down to 9s from 12s with a custom findMin 2012-10-11T16:22:48 mcstar: ok, I think that's pretty good for haskell. 2012-10-11T16:23:00 don't try to beat JavaScript 2012-10-11T16:23:14 mleise: but this is only recursive searching, i havent yet turned on my reducer 2012-10-11T16:23:34 mcstar: what ? is that from the benchmark ? 2012-10-11T16:23:57 I mean you did the benchmark with brute force only and it took 9 seconds ? 2012-10-11T16:24:10 mleise: on that benchmark this would run in 230s 2012-10-11T16:24:17 oh thank god 2012-10-11T16:24:59 but with a slower version of this, + the reducer, i reached 95s on the benchmark 2012-10-11T16:24:59 because I'm so busy refactoring that I cannot improve the actual algorithm 2012-10-11T16:25:18 Isn't this cute ? : Cell!cell.ToShapeIdx!shape 2012-10-11T16:26:00 no 2012-10-11T16:26:58 but it is replaced by the compiler with the index of the row/column/block of that cell at compile time :-( 2012-10-11T16:27:16 no more lookup tables and calculations 2012-10-11T16:27:27 not possible! 2012-10-11T16:27:32 witchcraft!!! 2012-10-11T16:27:34 just ... 320 MB of executable or so... dunno yet 2012-10-11T16:27:44 :p 2012-10-11T16:27:48 mleise: stop metaprogramming immediately 2012-10-11T16:30:27 mcstar: let me have a little fun. I don't even know if a) the compiler will survive this abuse b) the cost of cache misses in the code cache make it run slow 2012-10-11T16:30:42 sure 2012-10-11T16:30:45 but I'm optimistic 2012-10-11T16:30:53 mleise: only i benefit from that 2012-10-11T16:31:14 have I mentioned that the compiler _never_ releases memory ? 2012-10-11T16:31:22 hehe 2012-10-11T16:31:38 thats the first thing the D committe agreed on 2012-10-11T16:32:01 right, because it memory management was considered difficult 2012-10-11T16:32:06 they left it out 2012-10-11T16:35:13 mcstar: did you know that the fastest regexp is currently the compile time metaprogramming one in D ? 2012-10-11T16:35:34 i hardly know what regexp is 2012-10-11T16:35:43 at least for simple tasks, where it doesn't crash the compiler 2012-10-11T16:35:59 mcstar: you never wrote javascript 2012-10-11T16:36:06 no 2012-10-11T16:36:17 I used it for parsing text in Ants 2012-10-11T16:36:39 it's way faster to use one regexp call than a dozen JS functions to parse text 2012-10-11T16:41:35 *** antimatroidl has joined #aichallenge 2012-10-11T16:41:52 *** pairofdice has quit IRC (Quit: In girum imus nocte et consumimur igni.) 2012-10-11T16:42:13 went to far: "the value of 'this' is not known at compile time" :D 2012-10-11T16:46:28 noway, this is not known? 2012-10-11T16:49:50 *** amstan has quit IRC (Ping timeout: 248 seconds) 2012-10-11T17:04:38 *** foRei has quit IRC (Quit: Bye) 2012-10-11T17:29:25 *** Elderwolf has quit IRC (Quit: Lost terminal) 2012-10-11T17:31:03 *** Scooper has quit IRC (Quit: Leaving) 2012-10-11T17:42:56 mleise: ~100 lines, 4.3s, thats ~108 on the benchmark 2012-10-11T17:43:10 *** thestinger has joined #aichallenge 2012-10-11T17:43:27 how do you always manage to reduce your code so much after it bloats ? 2012-10-11T17:43:43 mcstar: I've already crossed the 1000 lines 2012-10-11T17:43:56 but with long comment texts 2012-10-11T17:44:37 jesus 2012-10-11T17:44:44 you write comments?? 2012-10-11T17:45:10 mleise: will you make it a D tutorial? 2012-10-11T17:47:10 mcstar: no, but I will otherwise look at this code next week and wonder what it does. 2012-10-11T17:47:40 It's easier when the code is only a couple houndred lines 2012-10-11T17:48:15 and, well, i was taught to always comment my code -.- 2012-10-11T17:48:57 omg, the compiler already uses a few 100 MBs :-/ 2012-10-11T17:49:09 this isn't going to scale well 2012-10-11T17:49:29 I'll have to close all other programs at some point :p 2012-10-11T17:51:17 fallocate -l 128GB swap 2012-10-11T17:51:20 mkswap swap 2012-10-11T17:51:22 swapon swap 2012-10-11T17:51:25 :P 2012-10-11T18:02:27 *** dici has quit IRC (Read error: Connection reset by peer) 2012-10-11T18:16:22 oh... i forgot something 2012-10-11T18:18:25 no, i didnt 2012-10-11T18:24:23 *** sigh has joined #aichallenge 2012-10-11T18:28:53 *** alehorst has joined #aichallenge 2012-10-11T18:33:39 uh... 2012-10-11T18:33:40 Error: template instance UniqueSorted!(Iota!(FirstCellInShape!(Shape.row),FirstCellInShape!(Shape.row) + 9),Iota!(FirstCellInShape!(Shape.column),81,9),Iota!(FirstCellInShape!(Shape.block),FirstCellInShape!(Shape.block) + 3),Iota!(FirstCellInShape!(Shape.block) + 9,FirstCellInShape!(Shape.block) + 12),Iota!(FirstCellInShape!(Shape.block) + 18,FirstCellInShape!(Shape.block) + 21)) template 'UniqueSorted' is not defined, did you me 2012-10-11T18:38:00 1.1g RAM, 2 minutes compile time, ... I think it wasn't that great an idea 2012-10-11T18:39:24 mleise: https://github.com/liquid-phynix/cl-ants-engine/blob/master/gen-indices.lisp 2012-10-11T18:39:35 i did that with mathematica 2012-10-11T18:41:58 :-/ 2012-10-11T18:49:09 *** sigh has quit IRC (Remote host closed the connection) 2012-10-11T18:59:25 *** antimatroidl has quit IRC (Quit: Leaving.) 2012-10-11T19:48:51 71s 2012-10-11T19:49:40 me too... for compilation 2012-10-11T20:00:23 I swear tomorrow, I'll have something working. 0.1 ms for the benchmark :p 2012-10-11T20:00:42 ...wishful thinking 2012-10-11T20:00:57 what's the CPU cycle minimum anyway ? 2012-10-11T20:04:11 *** smjm has quit IRC (Remote host closed the connection) 2012-10-11T20:04:57 *** bobby0qwd12 has joined #aichallenge 2012-10-11T20:11:43 *** bobby0qwd12 has quit IRC (Quit: Page closed) 2012-10-11T20:16:44 this blows my mind 2012-10-11T20:28:14 *** chris__0076 has joined #aichallenge 2012-10-11T20:31:43 *** Chris_0076 has quit IRC (Ping timeout: 248 seconds) 2012-10-11T20:33:08 *** thestinger has quit IRC (Quit: WeeChat 0.3.9) 2012-10-11T20:50:14 *** chris___0076 has joined #aichallenge 2012-10-11T20:53:24 *** chris__0076 has quit IRC (Ping timeout: 246 seconds) 2012-10-11T20:54:03 *** Chris_0076 has joined #aichallenge 2012-10-11T20:56:39 *** chris___0076 has quit IRC (Ping timeout: 255 seconds) 2012-10-11T21:02:55 *** mcstar has quit IRC (Ping timeout: 252 seconds) 2012-10-11T21:19:37 *** jacob_strauss has quit IRC (Quit: jacob_strauss) 2012-10-11T23:44:46 *** mleise has quit IRC (Ping timeout: 244 seconds) 2012-10-11T23:50:10 *** antimatroidl has joined #aichallenge