2012-09-09T00:41:14 *** antimatroidl has quit IRC (Quit: Leaving.) 2012-09-09T01:02:39 *** McLeopold has joined #aichallenge 2012-09-09T03:23:09 *** antimatroidl has joined #aichallenge 2012-09-09T03:38:21 *** foRei has joined #aichallenge 2012-09-09T03:47:54 *** valydo has joined #aichallenge 2012-09-09T03:49:50 *** loglog has quit IRC (Remote host closed the connection) 2012-09-09T03:50:08 *** loglog has joined #aichallenge 2012-09-09T03:50:43 *** epicmonkey_ has joined #aichallenge 2012-09-09T04:10:59 *** pairofdice has joined #aichallenge 2012-09-09T04:25:34 *** thestinger has quit IRC (Quit: WeeChat 0.3.9-rc1) 2012-09-09T04:25:55 *** thestinger has joined #aichallenge 2012-09-09T04:50:08 *** thestinger has quit IRC (Quit: WeeChat 0.3.9-rc1) 2012-09-09T05:48:41 *** mcstar has joined #aichallenge 2012-09-09T05:56:25 antimatroidl: good evening/morning/afternoon/noon/dawn/dusk or whatever 2012-09-09T05:58:19 evening :) 2012-09-09T05:58:55 and ridiculously windy 2012-09-09T05:59:22 i like wind 2012-09-09T05:59:34 unfortunately, for 2 days, its me whos windy 2012-09-09T05:59:50 up to 95km/h gusts seen recently 2012-09-09T05:59:55 got above 110 yesterday 2012-09-09T06:00:10 good for sailing to the New World, isnt it? 2012-09-09T06:00:19 156 up the mountain actually 2012-09-09T06:00:27 which is visible from my house 2012-09-09T06:01:05 antimatroidl: do you have a benchmark, like taking the product of 2 diagrams a lots of times? 2012-09-09T06:01:25 antimatroidl: i made a complete program out of what i showed you last time 2012-09-09T06:01:47 and id like to compare it performance wise to yours, since it is slower tham my haskell one considerably 2012-09-09T06:01:52 and id like to know the reason 2012-09-09T06:02:00 nope 2012-09-09T06:02:12 generate the dictionary from generators 2012-09-09T06:02:24 that requires lots of multiplication 2012-09-09T06:02:37 i just want to do it on the same 2 diagrams 2012-09-09T06:03:15 antimatroidl: http://hpaste.org/74446 this is the code 2012-09-09T06:05:10 gross :P 2012-09-09T06:05:29 yeah? 2012-09-09T06:05:36 thats means bad? 2012-09-09T06:05:38 -s 2012-09-09T06:05:41 no 2012-09-09T06:05:54 i think that when i look at other people's code 2012-09-09T06:06:03 peoples'* 2012-09-09T06:06:23 i dont understand them either 2012-09-09T06:06:36 c++ usually obscures the logic behind the code 2012-09-09T06:08:28 antimatroidl: have you studied flow networks? 2012-09-09T06:08:45 it is closely related to graph theory, so i thought you might have 2012-09-09T06:09:46 my graph theory background is pretty sketchy 2012-09-09T06:09:56 we covered flow networks but i didn't take any of it in 2012-09-09T06:10:04 i should go through and learn the maths 2012-09-09T06:10:09 but there's so much maths to learn 2012-09-09T06:10:13 and only a finite amount of time 2012-09-09T06:10:36 minimum cost perfect matching has a solution using the ford-fulkerson algorithm 2012-09-09T06:10:50 but they are presented usually in a primal-dual setting 2012-09-09T06:10:59 which im not familiar with, not even the notation 2012-09-09T06:12:56 antimatroidl: then paste me your diagram code, ill put a 'main' around it, and test it myself 2012-09-09T06:14:36 https://gist.github.com/3664627 2012-09-09T06:16:20 stupid github limits the length of the lines 2012-09-09T06:22:58 you should be able to get the raw text 2012-09-09T06:24:03 antimatroidl: ofc, im just saying how stupid is that you have to horizontally scroll the read the code from the gist 2012-09-09T06:24:10 to* 2012-09-09T06:24:35 why limit the viewing area? 2012-09-09T06:27:12 antimatroidl: whats A in the Diagram constructor? 2012-09-09T06:30:39 the number of nodes connected in an apsis for generators 2012-09-09T06:30:43 ie. F_n uses A=3 2012-09-09T06:30:48 i crashed it on the first try... 2012-09-09T06:30:50 it's so i can do others later 2012-09-09T06:31:04 good effort 2012-09-09T06:31:09 :) 2012-09-09T06:31:33 for example if A=3 and N=5 then there's 3 generators 0, 1 and 2 2012-09-09T06:31:57 yeah, and im going for 0 to 100 2012-09-09T06:32:05 and it doesnt take it nicely 2012-09-09T06:32:25 yeah i assume people using my code know what they're doing (no exceptions) 2012-09-09T06:32:55 i just put that exception into my code to illustrate the use of it 2012-09-09T06:36:59 ok, so the first 2 examples you gave were, g=0 and g=2 2012-09-09T06:41:43 8.53s user vs 32.73s user 2012-09-09T06:41:47 antimatroidl: ^^ 2012-09-09T06:45:25 ? 2012-09-09T06:45:36 which one is which? 2012-09-09T06:46:10 mine is the first 2012-09-09T06:46:26 but if im correct, the haskell one is like 10x faster 2012-09-09T06:46:46 but this issue is a bit trickier, with lazyness... 2012-09-09T06:47:11 1e6 times taking the product of g=0 and g=2 2012-09-09T06:47:52 antimatroidl: i didnt optimize for speed though 2012-09-09T06:48:10 its the simplest working implementation of my thinking i tlaked about 2012-09-09T06:48:43 yeah i didn't optimise either 2012-09-09T06:49:04 mine is sufficiently fast, but i'll try to speed it up at some point anyway, cause that's what we do :) 2012-09-09T07:01:18 *** Scooper has joined #aichallenge 2012-09-09T07:11:03 *** AlliedEnvy has quit IRC (Ping timeout: 246 seconds) 2012-09-09T07:17:31 *** antimatroidl has quit IRC (Read error: No route to host) 2012-09-09T07:17:43 *** antimatroidl has joined #aichallenge 2012-09-09T07:23:12 *** AlliedEnvy has joined #aichallenge 2012-09-09T07:58:39 antimatroidl: i see, so you add the edges that bridge the upper and lowe rails, and then add the triple ones 2012-09-09T07:59:09 i think ill this generator-generator, since its simple 2012-09-09T07:59:14 ill add* 2012-09-09T07:59:58 mcstar: :) 2012-09-09T08:00:01 marking assignments 2012-09-09T08:00:12 huh, that must feel good 2012-09-09T08:00:31 being in the role of the feared teacher... 2012-09-09T08:00:37 they're not doing very well :| 2012-09-09T08:17:11 *** smj has joined #aichallenge 2012-09-09T08:17:11 *** smj has joined #aichallenge 2012-09-09T08:27:30 antimatroidl: http://hpaste.org/74473 2012-09-09T08:27:50 it detects wrong input, state of the art, eh? 2012-09-09T08:28:27 actually, g can be equal to n-3 2012-09-09T08:31:15 antimatroidl: what's the n which you calculated the distinct products for? 2012-09-09T08:31:22 for which* 2012-09-09T08:31:37 my grammer sucks today 2012-09-09T08:37:17 largest n? 2012-09-09T08:37:21 11 2012-09-09T08:37:44 |F_n| from n=3 to n=11 goes 1, 4, 18, 73, 319, 1368, 5731, 24552, 104492 2012-09-09T08:39:12 *** Simas_J has joined #aichallenge 2012-09-09T08:43:57 afk, ill try later 2012-09-09T08:53:07 *** antimatroidl has quit IRC (Read error: Connection reset by peer) 2012-09-09T08:53:15 *** antimatroidl has joined #aichallenge 2012-09-09T09:25:48 *** Simas_J has quit IRC (Quit: Leaving) 2012-09-09T09:34:23 lets do it 2012-09-09T09:48:25 antimatroidl: |G_n| = n-2, right? 2012-09-09T09:49:39 (cardinality of the generator set of order n) 2012-09-09T09:51:34 yep 2012-09-09T09:51:39 starting from 0 2012-09-09T09:51:46 yes 2012-09-09T09:51:51 ie. G_3 = {g_0} 2012-09-09T09:52:10 antimatroidl: so, for n=11, you can have at most 9x9 different products 2012-09-09T09:52:22 of which a lot of will be the same, and the result is 60 2012-09-09T09:52:30 what is 104492 then? 2012-09-09T09:52:44 no, i think you misunderstand 2012-09-09T09:52:50 yeah, i think i do 2012-09-09T09:52:54 it's not just products, but also products of products 2012-09-09T09:53:00 and products of products of products 2012-09-09T09:53:05 until you've generated everything possible 2012-09-09T09:53:27 ie. what's the dictionary of words using generators 2012-09-09T09:53:30 so you compute G_n^k? 2012-09-09T09:53:43 damn no 2012-09-09T09:53:49 yeah i just with min k st G_n^k+1 = G_n^k 2012-09-09T09:53:51 2^G_n 2012-09-09T09:53:58 no 2012-09-09T09:54:01 it's not the power set 2012-09-09T09:54:03 ok 2012-09-09T09:54:16 what do you is as follows 2012-09-09T09:54:30 afk, got to eat, but pls, write it down 2012-09-09T09:54:41 add the generators to the dictionary any new words added to the dictionary including the generators are added to a queue 2012-09-09T09:54:55 for each word you take off the queue, multiply it by each of the generators and see if you found a new word 2012-09-09T09:55:33 ie. has that diagram been found yet, if it has, just skip over 2012-09-09T10:10:26 antimatroidl: aha, so you want all the diagrams of order n that are closed under multiplication 2012-09-09T10:13:47 yes 2012-09-09T10:13:51 i want the semigroup generated by them 2012-09-09T10:14:14 that's what the semigroup/monoid/group generated by a set of generators is 2012-09-09T10:14:49 you can also think of it as the smallest semigroup/monoid/group containing the generators when partially ordered by the subset relation 2012-09-09T10:15:01 they're the same thing 2012-09-09T10:17:49 antimatroidl: is G_n minimal, in the sense, that removing any element from it will give a different group? 2012-09-09T10:18:00 it's not a grouo 2012-09-09T10:18:04 it's not even a monoid 2012-09-09T10:18:11 well, F_3 is a monoid 2012-09-09T10:18:12 semigroup 2012-09-09T10:18:25 not sure about the middle generators 2012-09-09T10:18:46 if you removed the first or last generator you'd obviously just get F_n-1 with a line on one end 2012-09-09T10:18:58 and hence a group 2012-09-09T10:19:04 but that's not interesting 2012-09-09T10:19:10 it's the trivial group 2012-09-09T10:19:26 that's F_3 2012-09-09T10:37:44 antimatroidl: did you ever check that G_n x G_n = G_n ? 2012-09-09T10:38:46 mcstar: wut? 2012-09-09T10:39:39 i just want to know, if you ever checked that it holds, for the way you generate that set 2012-09-09T10:39:47 fuck 2012-09-09T10:39:50 not G , F 2012-09-09T10:39:59 F_n x F_n = F_n 2012-09-09T10:40:20 don't use x 2012-09-09T10:40:24 that's for cartesian products 2012-09-09T10:40:33 yeah, on the 2 sets 2012-09-09T10:40:35 just F_n^2 or F_nF_n is fine 2012-09-09T10:40:47 i don't need to check that 2012-09-09T10:40:59 it'd given by the fact that i calculated the semigroup generated 2012-09-09T10:41:00 {a,b} x {c,d} = {a.c,a.d,b.c,b.d} 2012-09-09T10:41:12 where . is what you want it to be 2012-09-09T10:41:42 antimatroidl: im asking, if you actually checked the algorithm 2012-09-09T10:42:01 for some n, at least 2012-09-09T10:42:29 {a,b}x{c,d} = {(a,c), (a,d), (b,c), (b,d)} 2012-09-09T10:42:35 i don't need to 2012-09-09T10:43:05 i have proved the diagrams are no larger than what i have counted up to 319 2012-09-09T10:51:14 wooo marking done 2012-09-09T11:01:27 *** epicmonkey_ has quit IRC (Ping timeout: 245 seconds) 2012-09-09T11:05:32 *** Kingpin13 has joined #aichallenge 2012-09-09T11:07:21 *** epicmonkey has joined #aichallenge 2012-09-09T11:16:34 *** epicmonkey_ has joined #aichallenge 2012-09-09T11:16:40 *** epicmonkey has quit IRC (Read error: No route to host) 2012-09-09T11:31:16 *** Kingpin13 has quit IRC (Ping timeout: 240 seconds) 2012-09-09T11:42:43 *** sigh has quit IRC (Remote host closed the connection) 2012-09-09T11:59:06 *** coeus has quit IRC (Ping timeout: 260 seconds) 2012-09-09T12:01:33 *** coeus has joined #aichallenge 2012-09-09T12:11:03 *** coeus has quit IRC (Read error: Connection reset by peer) 2012-09-09T12:13:54 *** coeus has joined #aichallenge 2012-09-09T12:32:14 *** epicmonkey_ has quit IRC (Remote host closed the connection) 2012-09-09T13:07:57 antimatroidl: still awake? 2012-09-09T13:09:02 ... i hope not, must be around 4am there 2012-09-09T13:31:53 *** jetienne has joined #aichallenge 2012-09-09T13:32:25 *** rezoner has joined #aichallenge 2012-09-09T14:36:44 hm, i see someone here, who hasnt been around much 2012-09-09T14:36:55 do you recognize yourself? 2012-09-09T14:42:12 *** rezoner_ has joined #aichallenge 2012-09-09T14:42:46 *** rezoner has quit IRC (Ping timeout: 244 seconds) 2012-09-09T14:49:24 *** rezoner_ has quit IRC (Quit: Leaving) 2012-09-09T14:49:58 *** valydo has quit IRC (Quit: leaving) 2012-09-09T14:55:29 to recognize himself is a first sign of intelligence :) 2012-09-09T14:56:03 put one animal in front of a mirror and see what happen :) 2012-09-09T14:56:40 then, he is either not intelligent, or idk, what else? 2012-09-09T14:56:47 McLeopold: hello 2012-09-09T15:00:34 *** female has joined #aichallenge 2012-09-09T15:04:12 *** thestinger has joined #aichallenge 2012-09-09T15:12:49 *** female has quit IRC (Quit: Page closed) 2012-09-09T15:15:29 *** Accoun has quit IRC () 2012-09-09T15:20:12 *** jetienne has quit IRC (Quit: jetienne) 2012-09-09T15:21:08 *** jetienne has joined #aichallenge 2012-09-09T15:22:31 *** jetienne has left #aichallenge 2012-09-09T15:30:52 *** pairofdice has quit IRC (Quit: In girum imus nocte et consumimur igni.) 2012-09-09T15:34:06 *** Accoun has joined #aichallenge 2012-09-09T15:59:35 thestinger: for the full problem, ghc runs as fast as the unoptimized c++, with -O3, c++ is 10x faster , all is good again :) 2012-09-09T16:00:01 needs more pgo and lto :P 2012-09-09T16:03:05 thestinger: it needs parallelization 2012-09-09T16:04:03 I wonder if gcc supports c++11 futures yet 2012-09-09T16:07:01 thestinger: in the end this all doesnt matter 2012-09-09T16:07:36 the problem he has is combinatorial, whatever you do, you can only get results for small numbers 2012-09-09T16:08:08 tree-parallelize-loops=2 :P 2012-09-09T16:08:16 -ftree-parallelize-loops=2 * 2012-09-09T16:08:28 whats that> 2012-09-09T16:08:35 and why would that help? 2012-09-09T16:08:39 auto-parallelizes loops 2012-09-09T16:08:48 you cant parallelize something that shares a common resource 2012-09-09T16:08:54 there is? :( 2012-09-09T16:09:00 first you need to get rid of that 2012-09-09T16:09:08 at the very least it would cheat on your benchmark :) 2012-09-09T16:09:11 after that, you can do small tasks in parallel, in synchronize 2012-09-09T16:09:23 in->and 2012-09-09T16:09:48 anyway better to just use tbb 2012-09-09T16:10:02 meaining? 2012-09-09T16:10:06 meaning 2012-09-09T16:10:07 the library 2012-09-09T16:10:27 thestinger: what library? 2012-09-09T16:10:52 tbb. 2012-09-09T16:11:06 intel-tbb 2012-09-09T16:11:20 i recon, tbb stands for something... 2012-09-09T16:11:55 openmp, and mpi is not obsolete either 2012-09-09T16:12:00 thread building blocks (it just has a bunch of concurrent data structures, etc.) 2012-09-09T16:12:08 mcstar: but cilk is way faster 2012-09-09T16:12:20 how? 2012-09-09T16:12:36 it's less stupid 2012-09-09T16:12:41 wait, is cilk that data-graph description stuff? 2012-09-09T16:12:50 from intel also? 2012-09-09T16:13:07 well it's like openmp 2012-09-09T16:14:11 i see 2012-09-09T16:14:24 how do you know it is actually faster? 2012-09-09T16:14:40 im sorry, but i just cant believe that you have actual experience with it 2012-09-09T16:14:49 heh :P 2012-09-09T16:22:01 for n=12, it would take 63 days to run, i better ^c 2012-09-09T16:22:59 but this means, for n=11 antimatroidl run his for more than a week 2012-09-09T16:23:03 do you think there's a better algorithm? 2012-09-09T16:23:15 you can use more brains 2012-09-09T16:23:39 i dont really want to describe the stuff in detail 2012-09-09T16:23:53 but basically, you can exclude stuff, if you study the structure more 2012-09-09T16:24:41 but the result is exponential also, so theres no polynomial algorithm probably 2012-09-09T16:25:18 anyway, it was good to do it, i learned some stuff while doing it 2012-09-09T16:40:30 *** dabino has joined #aichallenge 2012-09-09T16:40:47 *online 2012-09-09T16:41:00 \online 2012-09-09T16:41:56 ? 2012-09-09T16:43:10 bingo 2012-09-09T16:43:12 *** dabino has quit IRC (Client Quit) 2012-09-09T16:43:22 o.O 2012-09-09T16:43:38 you killed him 2012-09-09T16:44:40 trying to part/quit with 'online'? 2012-09-09T16:58:39 "Microsoft was doing well licensing BASIC for 8-bit computers, but the company was convinced the future lay in 16-bit computing." clear clairvoyance 2012-09-09T17:06:41 mcstar: hello back 2012-09-09T17:07:04 hey 2012-09-09T17:07:17 any news with the contest? 2012-09-09T17:07:22 nope 2012-09-09T17:07:36 i thought you might have been conspiring in the background.. 2012-09-09T17:08:01 no, I think jeff has just given up, but I don't know 2012-09-09T17:08:14 sometimes ppl ask, and i dont want to disseminate faulty information :) 2012-09-09T17:08:43 I could probably crank one out it a week or two with the current framework, but we still need money for hosting 2012-09-09T17:09:20 yes, that much we know, you need to get 'organized' 2012-09-09T17:09:30 sry 2012-09-09T17:09:33 incorporated 2012-09-09T17:10:24 deltor was very much on the stand of forking the competition 2012-09-09T17:10:36 but he had moved to switzerland recently, and he hasnt been back since 2012-09-09T17:13:42 we just need someone willing to take care of the money 2012-09-09T17:14:15 and maybe a courtesy email to jeff asking for permission to take over 2012-09-09T17:14:58 mcstar: are you a javascript fan 2012-09-09T17:15:39 i dont speak web technologies 2012-09-09T17:15:58 so, you wouldn't be interested in this? https://github.com/McLeopold/DCPU16 2012-09-09T17:17:03 dcpu sounds familiar 2012-09-09T17:17:19 is it a simulator of a microprocessor? 2012-09-09T17:17:35 yeah, for notch's upcoming game 2012-09-09T17:17:54 thestinger: << he will be interesting i think 2012-09-09T17:21:25 McLeopold: lol, Hard science fiction bullet point is lined out :( 2012-09-09T17:21:44 crossed out, that is 2012-09-09T17:22:19 i think when i visited that page last time, it appealed to me, that the game would feature hard scifi 2012-09-09T17:23:07 McLeopold: are you considering this for possible contest material, or you just mentioned it? 2012-09-09T17:24:16 just mentioned it 2012-09-09T17:24:46 janzert and I, or maybe jmcarthur discussed an ant game where you get a set of instructions with a cycle cost last year 2012-09-09T17:25:01 this brings me closer to thinking that is possible 2012-09-09T17:25:38 mcstar: plus, land the apollo lunar module on the moon with assembler! 2012-09-09T17:27:20 :) 2012-09-09T17:28:08 i dont want to be the grinch, but why would you do that? 2012-09-09T17:28:54 ants was great, you could apply all sorts of strategy, develop algorithms, on which to base them 2012-09-09T17:29:02 it was mildy visual 2012-09-09T17:29:06 mildly* 2012-09-09T17:29:19 it was great 2012-09-09T17:29:34 the lunar lander is in no way being compared to the aichallenge, totaly separate :) 2012-09-09T17:29:39 ok 2012-09-09T17:29:49 but still, im describing a game that appeals to me 2012-09-09T17:29:57 oh hey i was mentioned 2012-09-09T17:30:08 and programming a virtual assemly language isnt for me :) 2012-09-09T17:30:28 i would totally write an assembler dsl though! 2012-09-09T17:30:34 *edsl 2012-09-09T17:30:39 in haskell? 2012-09-09T17:30:43 hellz yeah 2012-09-09T17:30:44 what else? 2012-09-09T17:30:46 :) 2012-09-09T17:30:47 :) 2012-09-09T17:30:58 okay i should read up i guess 2012-09-09T17:32:28 mcstar: "thestinger: for the full problem, ghc runs as fast as the unoptimized c++, with -O3, c++ is 10x faster , all is good again :)" <-- this is just bait for me, isn't it? 2012-09-09T17:32:42 jmcarthur: yes 2012-09-09T17:32:53 jmcarthur: haha 2012-09-09T17:33:21 jmcarthur: it is actually allright, really, the c++ version is highly in-place, and uses a more sophisticated algorithm 2012-09-09T17:33:51 jmcarthur: the haskell one is terser, more comfortable to use... 2012-09-09T17:33:56 the in-place-ness is totally doable via haskell without sacrificing purity, to be clear :P 2012-09-09T17:34:19 well, i wrote some stuff in st, it didnt performan too great 2012-09-09T17:34:26 perform* 2012-09-09T17:34:28 although depending on the nature of the algorithm i may have to qualify that a lot 2012-09-09T17:34:35 i rarely use st 2012-09-09T17:35:34 st is pretty lame without unboxing and such, and *usually* you can avoid it without sacrificing performance at all anyway, but that depends on the algorithm. 2012-09-09T17:36:12 ah money was discussed earlier 2012-09-09T17:37:05 remember i mentioned earlier that i am likely to be able to arrange a sponsor, depending on whether we as a group would want it. it's a more likely deal if the game is trading-related, too. 2012-09-09T17:37:18 that's still on the table 2012-09-09T17:37:38 i thought you said you wanted an in-house trading game 2012-09-09T17:37:43 unrealted to aichallenge 2012-09-09T17:37:56 we have considered that too, but it's not necessarily a preference 2012-09-09T17:38:11 we already have one in-house, if that clears up some confusion 2012-09-09T17:38:42 just a simulated exchange and such. not very well implemented or anything though. 2012-09-09T17:38:52 and probably not as gamified as it could be 2012-09-09T17:38:55 jmcarthur: so how do you do in-place algorithms, without st, or io? 2012-09-09T17:39:04 (for good uses of the word "gamified" rather than stupid ones...) 2012-09-09T17:39:19 mcstar: there are various pure apis that internally use mutation, such as vector 2012-09-09T17:39:30 it depends on the algorithm, whether that's useful 2012-09-09T17:40:18 what is the algorithm? maybe i can nudge in the right direction, if it's doable 2012-09-09T17:40:30 that is semantically equivalent to ST 2012-09-09T17:41:04 that's probably overconstraining 2012-09-09T17:41:26 if i reimplemented my c++ one is haskell, i could tell you how much slower it would be 2012-09-09T17:41:27 if it's semantically equivalent to ST, it's no better or worse than ST anyway 2012-09-09T17:41:32 but im not going to do that 2012-09-09T17:41:45 but what is the algorithm? 2012-09-09T17:41:54 the C++ one 2012-09-09T17:42:02 mcstar: just cheat and use pgo. 2012-09-09T17:42:21 a trading game would require a lot of new framework to be written. 2012-09-09T17:42:28 the fact that you guys are saying it is parallelizable strongly indicates that you don't need ST at all 2012-09-09T17:42:33 McLeopold: yes 2012-09-09T17:42:44 jmcarthur: no, what i meant is, if you can provide a pure interface for some imperative code, that semantically equivalent to ST, in that you could write that alg. in ST and runST it 2012-09-09T17:42:57 sure 2012-09-09T17:43:02 it depends on the algorithm 2012-09-09T17:43:11 the point is that ST is often overly powerful for what you need to do 2012-09-09T17:43:32 there are limited forms of mutation you can get without it 2012-09-09T17:43:38 this is not a well known algorith with a name 2012-09-09T17:43:42 it solved a problem 2012-09-09T17:43:44 solves* 2012-09-09T17:44:02 it is antimatroidl's academic problem 2012-09-09T17:44:26 for example, the various "accum" functions in vector give you random-access writes. you just can't read from the accumulation vector until you're done 2012-09-09T17:45:25 jmcarthur: the core algorithm is like, you are given a set of sets 2012-09-09T17:45:51 you have to cluster the set, meaning, take the union of any, that have common elements 2012-09-09T17:46:46 the haskell one uses actual sets, with the usual set operations 2012-09-09T17:47:07 the c++ has a different approach, i dump the elements of a set to a vector 2012-09-09T17:47:32 while dumping a second set to the vector, if i encounter already present elements, i merge the 2 sets 2012-09-09T17:47:34 etc. 2012-09-09T17:47:43 so you partition the set into sets of sets that contain one or more common elements and then collapse each set of sets into just a set, resulting in a set of sets? 2012-09-09T17:48:11 if you want to state it in a complicated way, yes 2012-09-09T17:48:18 think of it as set-clustering 2012-09-09T17:48:23 i think that describes it well 2012-09-09T17:48:34 i feel like there is more than one way to interpret set clustering 2012-09-09T17:48:43 or is that actually well-defined and i should just google it? 2012-09-09T17:49:07 *** AlliedEnvy has quit IRC (Ping timeout: 246 seconds) 2012-09-09T17:49:22 no 2012-09-09T17:49:34 but it fits imho 2012-09-09T17:49:45 just draw circles on the plane 2012-09-09T17:49:46 "set clustering" sounds like grouping sets into equivalence classes 2012-09-09T17:49:51 merge them if they have any overlap 2012-09-09T17:50:04 ah 2012-09-09T17:50:14 okay, this is a bit different from my first interpretation 2012-09-09T17:51:29 huh, interesting problem, actually. 2012-09-09T17:51:48 jmcarthur: http://hpaste.org/74494 2012-09-09T17:51:55 if you understand code better :) 2012-09-09T17:52:13 code is definitely less ambiguous 2012-09-09T17:52:35 Diagram times(Diagram d1, Diagram d2){ 2012-09-09T17:52:45 this is the function, that does the above algorithm 2012-09-09T17:52:59 in the guise of taking a 'product' of 2 diagrams 2012-09-09T17:53:18 man i haven't read C++ code in a while 2012-09-09T17:53:26 ah 2012-09-09T17:54:33 the real task is then, given a set of generator diagrams, enumerate the semigroup generated by them 2012-09-09T17:54:58 *** AlliedEnvy has joined #aichallenge 2012-09-09T17:56:52 mcstar: heh, scales up in complexity pretty damn fast 2012-09-09T17:57:20 just looking at the valgrind numbers 2012-09-09T17:57:25 the complexity remains the same 2012-09-09T17:57:29 but it is exponential 2012-09-09T17:57:31 mcstar: you know what I mean :P 2012-09-09T17:57:36 20x for each +1 2012-09-09T17:57:50 jmcarthur: http://hpaste.org/74495 if you .hs files better 2012-09-09T17:58:07