2012-01-09T00:00:00 *** lhb__ has joined #aichallenge 2012-01-09T00:03:36 *** raemde_ has quit IRC (Ping timeout: 240 seconds) 2012-01-09T00:04:59 *** srgpqt has quit IRC (Quit: Lost terminal) 2012-01-09T00:29:22 *** u_ has quit IRC (Quit: u_) 2012-01-09T00:44:53 *** Fandekasp has joined #aichallenge 2012-01-09T00:47:22 *** dorisabayon has quit IRC (Ping timeout: 240 seconds) 2012-01-09T00:54:31 #357 looks interesting 2012-01-09T01:10:01 *** TheLinker has quit IRC (Read error: Connection reset by peer) 2012-01-09T01:16:49 *** amstan has quit IRC (Quit: Konversation terminated!) 2012-01-09T01:37:58 *** lhb__ has quit IRC (Read error: Connection reset by peer) 2012-01-09T01:38:22 *** Garf has joined #aichallenge 2012-01-09T01:38:55 *** Elderwol1 has joined #aichallenge 2012-01-09T01:42:01 *** pairofdice has joined #aichallenge 2012-01-09T01:43:27 *** Clex_ has joined #aichallenge 2012-01-09T01:46:16 *** Elderwolf has quit IRC (Ping timeout: 240 seconds) 2012-01-09T01:46:16 *** welterde has quit IRC (Ping timeout: 240 seconds) 2012-01-09T01:46:16 *** mleise has quit IRC (*.net *.split) 2012-01-09T01:46:16 *** dmj111 has quit IRC (*.net *.split) 2012-01-09T01:46:17 *** cyphase has quit IRC (*.net *.split) 2012-01-09T01:46:18 *** Wraithan has quit IRC (*.net *.split) 2012-01-09T01:46:18 *** jmcarthur has quit IRC (*.net *.split) 2012-01-09T01:46:18 *** ivan`` has quit IRC (*.net *.split) 2012-01-09T01:46:18 *** ztfw has quit IRC (*.net *.split) 2012-01-09T01:46:19 *** klutometis has quit IRC (*.net *.split) 2012-01-09T01:46:19 *** Clex has quit IRC (*.net *.split) 2012-01-09T01:46:19 *** jbroman has quit IRC (*.net *.split) 2012-01-09T01:46:19 *** artart78 has quit IRC (*.net *.split) 2012-01-09T01:49:41 *** mleise has joined #aichallenge 2012-01-09T01:49:41 *** dmj111 has joined #aichallenge 2012-01-09T01:49:41 *** cyphase has joined #aichallenge 2012-01-09T01:49:41 *** Wraithan has joined #aichallenge 2012-01-09T01:49:41 *** jmcarthur has joined #aichallenge 2012-01-09T01:49:41 *** ivan`` has joined #aichallenge 2012-01-09T01:49:41 *** ztfw has joined #aichallenge 2012-01-09T01:49:41 *** klutometis has joined #aichallenge 2012-01-09T01:49:41 *** jbroman has joined #aichallenge 2012-01-09T01:49:41 *** artart78 has joined #aichallenge 2012-01-09T01:55:04 *** Jak_o_Shadows has joined #aichallenge 2012-01-09T02:00:42 Oh man, PE #24 fits into a oneliner aswell 2012-01-09T02:07:49 *** CowTipperVirus has quit IRC (Ping timeout: 258 seconds) 2012-01-09T02:17:58 I'm trying to solve #345 now 2012-01-09T02:21:35 *** mleise has quit IRC (Ping timeout: 240 seconds) 2012-01-09T02:24:20 I'm just on my way to level 2 2012-01-09T02:32:04 Oh...I've not even finished level 1 yet. I'm just trying to find some interesting problems. 2012-01-09T02:35:00 ahh 2012-01-09T02:35:33 I love oneliners, but I'm forcing myself to do it the hard way. 2012-01-09T02:50:35 *** Palmik has joined #aichallenge 2012-01-09T02:55:07 *** epicmonkey has joined #aichallenge 2012-01-09T03:10:55 *** epicmonkey has quit IRC (Ping timeout: 240 seconds) 2012-01-09T03:39:54 *** Blkt has joined #aichallenge 2012-01-09T03:43:40 *** raemde has joined #aichallenge 2012-01-09T03:45:20 *** dorisabayon has joined #aichallenge 2012-01-09T03:48:21 *** Fandekasp has quit IRC (Ping timeout: 248 seconds) 2012-01-09T03:57:04 *** mviel_ has joined #aichallenge 2012-01-09T04:01:01 *** mviel__ has joined #aichallenge 2012-01-09T04:04:39 *** mviel_ has quit IRC (Ping timeout: 260 seconds) 2012-01-09T04:13:48 *** welterde has joined #aichallenge 2012-01-09T04:19:29 *** Jak_o_Shadows1 has joined #aichallenge 2012-01-09T04:21:42 *** Jak_o_Shadows has quit IRC (Ping timeout: 240 seconds) 2012-01-09T04:29:19 *** Cyndre_ has joined #aichallenge 2012-01-09T04:31:50 *** mcstar has joined #aichallenge 2012-01-09T04:32:22 *** Cyndre has quit IRC (Ping timeout: 240 seconds) 2012-01-09T04:36:05 Harr, #24 in 70ms 2012-01-09T04:36:21 *** Blkt` has joined #aichallenge 2012-01-09T04:36:22 *** Blkt has quit IRC (Quit: ERC Version 5.3 (IRC client for Emacs)) 2012-01-09T04:36:32 *** Blkt` has quit IRC (Remote host closed the connection) 2012-01-09T04:36:53 *** Blkt has joined #aichallenge 2012-01-09T04:40:41 *** sashaSochka has joined #aichallenge 2012-01-09T04:46:13 i couldnt even read it in that time, i measured 2012-01-09T04:55:07 Funny! 2012-01-09T04:57:45 pairofdice: 35ms 2012-01-09T04:58:58 truth is my alg. runs in 370ms, but using c++'s next_permutation its only 35ms 2012-01-09T04:59:35 but i wrote a similar function 2012-01-09T04:59:47 i forgot if its in c++ 2012-01-09T05:00:50 iterating through permutations is surprisingly easy 2012-01-09T05:01:13 iterating through subgroups i found a bit messier 2012-01-09T05:01:19 but doable 2012-01-09T05:02:12 i only have a haskell version of next_permutation, probably i thought why bother if its in the standard libs 2012-01-09T05:03:19 good (late) morning everyone 2012-01-09T05:04:09 hah, he has a late morning automatic message too 2012-01-09T05:04:16 he is prepared 2012-01-09T05:05:59 https://gist.github.com/1582289 2012-01-09T05:06:16 that's my basic bijection/permutation implementation, ++ being the relevant code snippet, i assume you did it like that? 2012-01-09T05:07:09 http://pastebin.com/WFUNgi5X 2012-01-09T05:07:20 that's the grossest ++ iterator i have for a type of bijection 2012-01-09T05:07:25 its elaborate but yes 2012-01-09T05:07:47 gross 2012-01-09T05:08:19 uh oh 2012-01-09T05:09:12 it's for bijections between two different games, so you need to partition both player sets up so players in the same set have the same number of strategies, then iterating through the game bijections for these partitions 2012-01-09T05:09:16 where is the dollar sign??? 2012-01-09T05:09:32 ?><":L":{}_+ 2012-01-09T05:09:37 ||+_))((*&*&&^^%$#$#$ 2012-01-09T05:09:38 $ 2012-01-09T05:09:40 thanks 2012-01-09T05:09:44 * pairofdice covers his eyes 2012-01-09T05:11:23 i switch to en layout 2012-01-09T05:11:25 ed 2012-01-09T05:13:24 the number of bijections one has to iterate through explodes pretty quickly obviously though 2012-01-09T05:13:38 so checking for equality of games by iterating through all strategy combinations is not very efficient 2012-01-09T05:13:59 there is a nice way to do it which i haven't fully fleshed out 2012-01-09T05:14:28 the running time gets worse the further players preferences over the pure strategy space are from a total order rather than a weak order 2012-01-09T05:14:43 towards* a weaker order 2012-01-09T05:15:40 errr, sorry, checking for equality of games by iterating through all game bijections 2012-01-09T05:15:52 and for each game bijection all pure strategies 2012-01-09T05:16:08 * antimatroid stops ranting 2012-01-09T05:17:01 my haskell one runs in 430 ms, too bad 2012-01-09T05:18:00 c++ is so fast because it can mutably update elements 2012-01-09T05:18:23 once i have learned monads im gonna try to do that too 2012-01-09T05:18:52 antimatroid: isnt there some clever way of doing that? 2012-01-09T05:18:53 lol, :{} is a sweet smiley 2012-01-09T05:18:59 to do what? 2012-01-09T05:19:36 checking for equivalence 2012-01-09T05:19:47 depends on how you define equivalence 2012-01-09T05:20:05 antimatroid: for your pleasure, and to motivate you towards haskell: http://codepad.org/RZAS2wgn 2012-01-09T05:20:39 lol cnt 2012-01-09T05:20:39 cunt 2012-01-09T05:20:43 i'm so australian 2012-01-09T05:20:54 i read count for cunt too 2012-01-09T05:21:49 not gonna lie, that looks gross :p 2012-01-09T05:22:09 yeah, similar to your c++ code 2012-01-09T05:22:20 *** X-Scale has quit IRC (Remote host closed the connection) 2012-01-09T05:22:25 yeah but i wrote it, so i sort of know what's going on :P 2012-01-09T05:22:36 im kidding 2012-01-09T05:22:49 in the c++ one, its apparent whats going on 2012-01-09T05:23:02 if i didnt write this one, i couldnt figure it out 2012-01-09T05:23:25 * pairofdice hugs itertools 2012-01-09T05:23:42 snake lover 2012-01-09T05:24:07 print(next(itertools.islice(itertools.permutations('0123456789'), 999999, None))) 2012-01-09T05:25:27 i dont get it 2012-01-09T05:25:43 fuck 2012-01-09T05:25:47 i read it isSlice 2012-01-09T05:26:16 pairofdice: so it returns a generator< 2012-01-09T05:26:18 ? 2012-01-09T05:26:34 yes 2012-01-09T05:26:57 whoa 2012-01-09T05:27:00 that was fast 2012-01-09T05:27:38 pairofdice: it is way slower in pypy wtf? 2012-01-09T05:27:50 I haven't tried it in pypy 2012-01-09T05:28:07 it seems faster in python3 2012-01-09T05:28:13 but i cant measure it 2012-01-09T05:28:31 (afaik profiling is idiotic in pytohn) 2012-01-09T05:28:55 *** replore has quit IRC (Remote host closed the connection) 2012-01-09T05:30:47 Though because of python I don't know how to do some stuff 'the hard way' 2012-01-09T05:33:16 *** sigh has joined #aichallenge 2012-01-09T05:37:36 * antimatroid would really love to see someone upload a contest winning bot as a v1 on the last day before entries close without publicly claiming ownership 2012-01-09T05:37:59 obviously i can't do that myself anymore :P 2012-01-09T05:38:30 huh_ 2012-01-09T05:38:33 ? 2012-01-09T05:38:49 why is that? 2012-01-09T05:38:57 because it would be mysterious :P 2012-01-09T05:39:05 :) 2012-01-09T05:39:22 myterious->annoying an aggrevating 2012-01-09T05:39:29 if you hadn't noticed i'm a fan of the last day upload :P 2012-01-09T05:39:39 i wasn't quite as bad for planet wars but pretty much the same 2012-01-09T05:39:52 why annoying and aggrevating? 2012-01-09T05:40:00 antimatroid: you played on tcp before the end 2012-01-09T05:40:01 they still have to have spent the time needed to write the bot 2012-01-09T05:40:04 yeah 2012-01-09T05:40:04 so it doesnt count 2012-01-09T05:40:12 i think it doe 2012-01-09T05:40:20 it could be the mysterious tcp bot 2012-01-09T05:40:21 you shouldtn not give ANY indication that you exist 2012-01-09T05:40:24 and then uploa 2012-01-09T05:40:25 d 2012-01-09T05:40:27 everyone would think it's someone in the top x 2012-01-09T05:40:56 why annoying? because it means that you cant see the source of the winning bot 2012-01-09T05:41:04 and mysteries are annoying 2012-01-09T05:41:06 they could release it anonymously? 2012-01-09T05:41:14 you didnt say they would 2012-01-09T05:41:23 i didn't say they wouldn't either :p 2012-01-09T05:41:50 bonus points if it's written in brainfuck 2012-01-09T05:41:55 (converted to) 2012-01-09T05:42:08 or follows a theme different to the actual game with variable names 2012-01-09T05:46:17 dont smoke that whole joint, man 2012-01-09T05:49:25 heh 2012-01-09T05:49:31 i applied for a job 2012-01-09T05:49:47 some firm needs c++/qt developer 2012-01-09T05:57:09 what kind of firms? 2012-01-09T05:57:19 i think i'm going to try and get into algo trading after phd 2012-01-09T05:57:33 sounds fun and lucrative 2012-01-09T05:58:18 well, the offer came to a physicists' mailing list, some company needs a user interface for their measuring equipment 2012-01-09T05:58:41 job would take couple of months 2012-01-09T05:58:52 and i could do it fro home 2012-01-09T05:59:03 so, theres nothing to lose 2012-01-09T05:59:42 i was speaking to some guys from morgan stanley 2012-01-09T05:59:56 when there was a job-market somthing at out uni 2012-01-09T06:00:04 what do you call it? 2012-01-09T06:00:14 our* 2012-01-09T06:00:59 not sure but i think i know what you mean 2012-01-09T06:01:03 working from home would be awesome 2012-01-09T06:01:17 aka working whilst travelling imo 2012-01-09T06:01:45 so one guy was a mathematician, the other was an engineer 2012-01-09T06:01:53 software ofc 2012-01-09T06:02:24 ms is heavy on the functional and distributed side of computing 2012-01-09T06:02:47 the software guy did really open up when i asked details though 2012-01-09T06:03:00 im not sure of he was just bullshitting me or didt want to leak trade secrets 2012-01-09T06:03:16 (i think he was a bit incompetent to the area i was asking him about) 2012-01-09T06:03:50 the mathematician said there are challenges 2012-01-09T06:03:58 and everything would be fine and great 2012-01-09T06:04:21 and they have some programs that you could there before graduation 2012-01-09T06:04:32 (means 5 years here) 2012-01-09T06:04:42 could do/participate 2012-01-09T06:04:52 and you get dough 2012-01-09T06:05:13 but probably after graduation, they happily take a mathematician/physicist 2012-01-09T06:05:25 ofc there must be some tests 2012-01-09T06:06:28 damn 2012-01-09T06:06:34 first did -> didnt 2012-01-09T06:06:58 i hate when my typo turns the sentence into the exact opposite of what im trying to say 2012-01-09T06:13:15 yeah 2012-01-09T06:13:17 sounds fun though 2012-01-09T06:13:24 that's all i really want, something fun to do 2012-01-09T06:13:39 after that i'll try and optimise monetary compensation for my efforts 2012-01-09T06:13:51 well, whilst surviving 2012-01-09T06:14:57 from what i heard these financial firms make you bleed bad 2012-01-09T06:15:02 long hours 2012-01-09T06:15:05 and all 2012-01-09T06:15:15 but they give away money generously 2012-01-09T06:15:47 probably you do a couple of years at one of these, and go to hawaii afterwards 2012-01-09T06:15:52 or to tasmania in your case 2012-01-09T06:16:05 yeah, not sure i'd do it as a career 2012-01-09T06:16:15 but go in to make some money and set myself up 2012-01-09T06:16:21 then work out what to do from there 2012-01-09T06:16:41 although i'm already a slave to learning 2012-01-09T06:17:49 i'm $35k in debt atm, but that's to the government, no interest (except inflation) and i don't actually have to start paying it off until i'm earning like $50k a year 2012-01-09T06:17:55 or never if i don't earn that much 2012-01-09T06:17:58 *** dabino has joined #aichallenge 2012-01-09T06:18:37 i have some dept too 2012-01-09T06:18:40 we might not have free uni, but at least there are sane ways to access money 2012-01-09T06:19:21 and there are government caps on how much an undergrad can pay each year 2012-01-09T06:19:32 to try and limit fees 2012-01-09T06:20:03 that's not phrased right, a cap on how much a uni can charge an undergrad for a full time load 2012-01-09T06:20:08 probably excepting medicine 2012-01-09T06:32:33 *** Blkt has quit IRC (Remote host closed the connection) 2012-01-09T06:34:14 *** GarfTop has joined #aichallenge 2012-01-09T06:35:54 *** Blkt has joined #aichallenge 2012-01-09T06:37:42 *** Garf has quit IRC (Ping timeout: 240 seconds) 2012-01-09T06:42:37 *** raemde has quit IRC (Ping timeout: 252 seconds) 2012-01-09T06:45:12 *** Fandekasp has joined #aichallenge 2012-01-09T06:48:30 *** dorisabayon has quit IRC (Ping timeout: 248 seconds) 2012-01-09T06:58:52 darmok and jalad at tanagra 2012-01-09T07:04:10 shaka, when the wall fell 2012-01-09T07:07:35 *** sashaSochka has quit IRC (Ping timeout: 258 seconds) 2012-01-09T07:09:48 with sails unfurled 2012-01-09T07:13:13 sokath, his eyes uncovered! 2012-01-09T07:16:19 the beast at tanagra: #47 2012-01-09T07:22:32 *** Jak_o_Shadows1 has quit IRC (Remote host closed the connection) 2012-01-09T07:36:20 shaka... 2012-01-09T07:40:41 SOKATH 47$ 2012-01-09T07:40:51 #47 2012-01-09T07:44:36 lol 2012-01-09T07:44:44 i like the wording of 33 2012-01-09T07:45:15 "an inexperienced mathematician in attempting to simplify" 49/98 to 4/8 2012-01-09T07:45:51 i woudlnt say inexperienced.... 2012-01-09T07:49:29 I don't get it 2012-01-09T07:50:27 which part< 2012-01-09T07:50:29 ? 2012-01-09T07:50:43 The part from start to end 2012-01-09T07:51:00 that part... 2012-01-09T07:51:07 seems easy enough 2012-01-09T08:07:50 *** ikaros has joined #aichallenge 2012-01-09T08:08:03 *** raemde has joined #aichallenge 2012-01-09T08:11:48 hm 2012-01-09T08:11:52 sucky problem 2012-01-09T08:20:48 *** dabino has quit IRC (Quit: Page closed) 2012-01-09T08:21:02 ah ok 2012-01-09T08:22:32 sokath! 2012-01-09T08:27:08 *** raemde has quit IRC (Remote host closed the connection) 2012-01-09T08:32:21 34 was easy 2012-01-09T08:36:25 *** dici has joined #aichallenge 2012-01-09T08:42:54 35 too 2012-01-09T08:43:50 *** amstan has joined #aichallenge 2012-01-09T08:43:50 *** ChanServ sets mode: +o amstan 2012-01-09T08:47:01 *** raemde has joined #aichallenge 2012-01-09T08:54:35 36 2012-01-09T08:55:35 *** raemde has quit IRC (Read error: Connection reset by peer) 2012-01-09T08:55:57 *** raemde has joined #aichallenge 2012-01-09T09:03:06 *** sigh has quit IRC (Remote host closed the connection) 2012-01-09T09:10:13 *** u_ has joined #aichallenge 2012-01-09T09:18:10 mcstar: no! 42! 2012-01-09T09:18:34 hey 2012-01-09T09:18:52 im getting there 2012-01-09T09:32:40 37 check 2012-01-09T09:37:41 *** foRei has joined #aichallenge 2012-01-09T09:39:05 *** Kurnevsky has joined #aichallenge 2012-01-09T09:45:23 *** dorisabayon has joined #aichallenge 2012-01-09T09:49:28 *** Fandekasp has quit IRC (Ping timeout: 276 seconds) 2012-01-09T09:52:08 *** amstan has quit IRC (Ping timeout: 240 seconds) 2012-01-09T09:56:51 *** Anilm3 has joined #aichallenge 2012-01-09T10:02:26 *** mleise has joined #aichallenge 2012-01-09T10:21:35 *** dorisabayon has quit IRC (Ping timeout: 255 seconds) 2012-01-09T10:27:29 *** Dici_ has joined #aichallenge 2012-01-09T10:27:29 *** dici has quit IRC (Disconnected by services) 2012-01-09T10:27:33 *** Dici_ is now known as dici 2012-01-09T10:29:14 *** Anilm3 has quit IRC (Quit: Lost terminal) 2012-01-09T10:41:00 *** AlliedEnvy_ has quit IRC (Ping timeout: 268 seconds) 2012-01-09T10:44:19 *** dapplegate has joined #aichallenge 2012-01-09T10:58:45 *** Palmik has quit IRC (Read error: Connection reset by peer) 2012-01-09T10:59:30 *** Palmik has joined #aichallenge 2012-01-09T11:21:41 *** amstan has joined #aichallenge 2012-01-09T11:21:41 *** ChanServ sets mode: +o amstan 2012-01-09T11:29:04 *** dapplegate_ has joined #aichallenge 2012-01-09T11:29:08 *** dapplegate has quit IRC (Quit: Ex-Chat) 2012-01-09T11:38:14 *** JorgeB has joined #aichallenge 2012-01-09T11:43:04 *** dr- has joined #aichallenge 2012-01-09T11:47:02 *** mikewintermute has joined #aichallenge 2012-01-09T11:49:04 *** alehorst has quit IRC (Ping timeout: 276 seconds) 2012-01-09T11:58:50 *** raemde_ has joined #aichallenge 2012-01-09T12:01:44 *** raemde has quit IRC (Ping timeout: 240 seconds) 2012-01-09T12:15:23 *** Blkt has quit IRC (Quit: ERC Version 5.3 (IRC client for Emacs)) 2012-01-09T12:31:26 mcstar: I see somebody has been doing problems over the weekend 2012-01-09T12:31:39 who? 2012-01-09T12:31:48 :) 2012-01-09T12:32:40 rwest: i did 6 in 2 hours today 2012-01-09T12:32:55 nice 2012-01-09T12:33:10 they were pretty easy 2012-01-09T12:33:18 and boring 2012-01-09T12:33:31 heh 2012-01-09T12:33:36 probably im not doing any more pe for a couple of days 2012-01-09T12:33:42 I been making the mother of all spreadsheets this weekend 2012-01-09T12:33:48 student loans are the devil 2012-01-09T12:34:48 managing your finances? 2012-01-09T12:35:10 yea 2012-01-09T12:35:21 my student loans cost almost as much as my rent 2012-01-09T12:35:22 lol 2012-01-09T12:35:50 trying to work on the fastest way to pay them off 2012-01-09T12:35:55 real world problems lol 2012-01-09T12:36:03 i applied for a job today, c++/qt, i need it for tuition 2012-01-09T12:36:05 fee 2012-01-09T12:36:37 these thinks suck soo much 2012-01-09T12:36:42 g 2012-01-09T12:37:01 id be a great millionare 2012-01-09T12:37:52 rwest: you dont have to worry much with this new job, do you? 2012-01-09T12:38:22 mcstar: it's not that big of a pay raise from my previous job, but it does help 2012-01-09T12:39:38 rwest: what percent is the tax? 2012-01-09T12:39:51 was the amount you told me taxed or not? 2012-01-09T12:39:57 not 2012-01-09T12:40:07 I am at about 28% 2012-01-09T12:47:24 My solution to EP#23 is super fast now: http://projecteuler.net/thread=23;page=8 (bottom) 2012-01-09T12:49:01 *** dapplegate_ has quit IRC (Remote host closed the connection) 2012-01-09T12:49:41 you all have to give me kudos points, nao 2012-01-09T12:49:51 how fast? 2012-01-09T12:49:58 ~30 ms 2012-01-09T12:50:14 2Ghz Core 2 Duo mobile cpu 2012-01-09T12:50:17 ncie 2012-01-09T12:50:24 those are fast processors man 2012-01-09T12:50:31 XD 2012-01-09T12:50:44 there are slower ones at least 2012-01-09T12:50:46 *** McLeopold has left #aichallenge 2012-01-09T12:50:56 man 2012-01-09T12:51:01 thats like 300 lines 2012-01-09T12:51:24 now calculate how much mone you would have earned for that 2012-01-09T12:51:28 y 2012-01-09T12:52:05 if the execution speed = money, a lot towards my first implementation that ran in 1 minute 40 seconds 2012-01-09T12:52:20 no, sloc is money 2012-01-09T12:52:27 cause THAT equals time 2012-01-09T12:52:32 but the returns were dimishing once i reached 100ms or so 2012-01-09T12:52:50 hours of work for only a little speed-up 2012-01-09T12:52:55 heh 2012-01-09T12:52:57 exactly 2012-01-09T12:53:01 still, you rock 2012-01-09T12:53:30 (mostly genuine from my part, tiny bit sarcastic) 2012-01-09T12:53:40 sloc = money? I have just earned 172 credits 2012-01-09T12:53:54 since it is not 300 lines 2012-01-09T12:53:54 oh 2012-01-09T12:54:02 170? 2012-01-09T12:54:41 then again the asm solution is only 90 loc :) 2012-01-09T12:55:03 mine run in 1.3 secs 2012-01-09T12:55:18 and was based on a faulty paste of conor's 2012-01-09T12:55:37 (i had a haskell solution before that) 2012-01-09T12:55:54 but that one, runs in 8 secs 2012-01-09T12:57:41 mleise: check out mine 2012-01-09T12:57:55 you like it, i expect a kudos from you 2012-01-09T12:58:59 updated 2012-01-09T12:59:07 that foldl' wasnt necessary 2012-01-09T12:59:21 kudos is not an accepted currency 2012-01-09T13:00:00 mcstar: where is all the code necessary to do the computations? 2012-01-09T13:00:08 ? 2012-01-09T13:00:12 joke? 2012-01-09T13:00:22 if it is, good one 2012-01-09T13:00:39 *** JorgeB has quit IRC (Quit: Textual IRC Client: http://www.textualapp.com/) 2012-01-09T13:00:56 *** JorgeB has joined #aichallenge 2012-01-09T13:01:29 thx 2012-01-09T13:01:50 you get the shortness price 2012-01-09T13:02:28 *prize 2012-01-09T13:03:28 *** asloane has joined #aichallenge 2012-01-09T13:04:35 *** mikewintermute has quit IRC (Quit: mikewintermute) 2012-01-09T13:06:58 pairofdice: wanna share your friend key> 2012-01-09T13:07:00 ? 2012-01-09T13:07:13 mleise: you too 2012-01-09T13:07:23 wtf i thought i ha dyou 2012-01-09T13:08:19 43250423120960_68ebd6d0d3ba722a45ac44a4cc18e4bd 2012-01-09T13:08:41 thx 2012-01-09T13:15:55 *** Israfel has quit IRC (Ping timeout: 260 seconds) 2012-01-09T13:28:11 *** Israfel has joined #aichallenge 2012-01-09T13:36:52 my puzzle solve rate is rather low 2012-01-09T13:37:13 seems you just startrd 2012-01-09T13:37:37 *** thestinger has joined #aichallenge 2012-01-09T13:37:55 *** cyphase has quit IRC (Ping timeout: 240 seconds) 2012-01-09T13:39:34 *** amstan_ has joined #aichallenge 2012-01-09T13:39:34 *** ChanServ sets mode: +o amstan_ 2012-01-09T13:39:44 yes, when thestinger acted up about milliseconds yesterday I joined ^^ 2012-01-09T13:40:32 :) 2012-01-09T13:41:26 mcstar: lol, were you here when I had that speed problem with string conversion yesterday? 2012-01-09T13:41:46 i dont recall string conversions 2012-01-09T13:42:15 http://sprunge.us/DMbT well, I was using a function like this 2012-01-09T13:42:22 which is the method suggested everywhere 2012-01-09T13:42:32 it's slower than cpython 2012-01-09T13:42:39 that might not seem bad, since it's just a silly string conversion 2012-01-09T13:42:50 but it made one of my solutions take 5 minutes 2012-01-09T13:42:57 I switched to boost::lexical_cast and it takes 23ms 2012-01-09T13:43:07 lol 2012-01-09T13:43:21 wtf 2012-01-09T13:43:48 why dont they overloa d the >> operator? 2012-01-09T13:44:43 a stringstream is a heavy object i think 2012-01-09T13:44:55 i wouldnt use for a casual thing 2012-01-09T13:45:01 i mean id reuse it as much as possible 2012-01-09T13:45:09 you can clear it and such 2012-01-09T13:45:15 maybe make it static 2012-01-09T13:45:52 i dont know what a lexical cast is 2012-01-09T13:48:24 mcstar: well, I tried making it static 2012-01-09T13:48:38 then you have to also clear it, etc. 2012-01-09T13:48:45 it was a lot faster but still slower than python... 2012-01-09T13:48:59 mcstar: lexical_cast is a template basically 2012-01-09T13:49:20 lexical_cast(5533) 2012-01-09T13:49:30 lexical_cast("55") 2012-01-09T13:49:41 they have it specialized for certain types like an int 2012-01-09T13:50:26 i think in your example there are too much copying going on] 2012-01-09T13:50:31 well 2012-01-09T13:50:37 stringstream is dynamically allocated 2012-01-09T13:50:43 *** cyphase has joined #aichallenge 2012-01-09T13:50:50 and then you send chars into it, one by one 2012-01-09T13:50:54 when you do << 2012-01-09T13:51:02 then you copy the data out of it (the string) 2012-01-09T13:51:22 and it does like 3 dynamic allocations for each 'ss << t' 2012-01-09T13:51:53 for an int, you know the maximum number of digits 2012-01-09T13:52:01 anyway since you do ss << t 2012-01-09T13:52:13 T already has a method to stringify itslef 2012-01-09T13:52:30 yeah, but they don't expose it :( 2012-01-09T13:53:13 anyway, boost::lexical_cast is great 2012-01-09T13:53:14 what is t? 2012-01-09T13:53:16 T 2012-01-09T13:53:23 was an it? 2012-01-09T13:53:26 int? 2012-01-09T13:53:27 an int 2012-01-09T13:53:29 so lexical_cast(U) is where to!T(U) comes from in D 2012-01-09T13:53:30 yeah 2012-01-09T13:53:53 *** Redgis has joined #aichallenge 2012-01-09T13:54:03 lexical_cast is not in the standard 2012-01-09T13:54:23 yeah, but boost is header-only and written by people in the standards committee anyway 2012-01-09T13:54:27 D probably existed before boost 2012-01-09T13:54:43 no 2012-01-09T13:55:09 mleise: boost::array is from 2001 2012-01-09T13:55:10 it copied boost, or at least Alexandrei did 2012-01-09T13:55:16 oops, meant to respond to mcstar 2012-01-09T13:55:33 thats old 2012-01-09T13:55:48 and it became std::array 2012-01-09T13:56:00 lots of the standard just gets taken from boost 2012-01-09T13:56:22 thestinger: but whats the problem with c int-string conversion? 2012-01-09T13:56:27 was that slow too? 2012-01-09T13:56:27 and then gcc often just starts by using the boost implementation 2012-01-09T13:56:48 sprintf? 2012-01-09T13:57:05 that's pretty slow, but not nearly as slow 2012-01-09T13:57:13 but then I would have to make a function for each built-in int type 2012-01-09T13:57:13 you need a fixed size buffer for that. 2012-01-09T13:57:18 because they need different buffer sizes 2012-01-09T13:57:19 thats ok 2012-01-09T13:57:24 and it wouldn't work for something like a gmp int 2012-01-09T13:57:28 etc 2012-01-09T13:57:35 gmp has their own conversions 2012-01-09T13:57:42 yeah, silly example 2012-01-09T13:57:50 i dont expect that to be especially fast 2012-01-09T13:57:59 but I wanted a generic to_string function, and specializing it for 100 cases would be annoying 2012-01-09T13:58:03 it it run ok, when i did conversionsin some example 2012-01-09T13:58:15 it's the type of stuff that should be in the standard 2012-01-09T13:58:16 thestinger: what problem was that? 2012-01-09T13:58:26 mcstar: you would increase the holy LOC with printf 2012-01-09T13:58:43 huh? 2012-01-09T13:59:00 I could just add specializations with sprintf etc. 2012-01-09T13:59:11 when you have to write specialisation and privide it with a buffer etc 2012-01-09T13:59:12 I was actually starting to do it 2012-01-09T13:59:17 and then I found lexical_cast 2012-01-09T13:59:27 well, if i want my matrix printed 2012-01-09T13:59:34 i probabl do it with c functions 2012-01-09T13:59:37 not iostream 2012-01-09T13:59:42 what matrix? 2012-01-09T13:59:46 just an exmaple 2012-01-09T13:59:49 is it an euler problem? 2012-01-09T13:59:51 i liek The Matrix 2012-01-09T14:00:08 thestinger: what problem was that? 2012-01-09T14:00:11 well, there's atoi 2012-01-09T14:00:16 this matrix requires unicode symbols and terminal colors (green) 2012-01-09T14:00:28 mcstar: I've needed string <-> number for many of them 2012-01-09T14:00:40 itoa isn't standard though 2012-01-09T14:00:48 yeah 2012-01-09T14:00:49 *** Redgis has quit IRC (Quit: ... mains libres) 2012-01-09T14:01:00 stupid name 2012-01-09T14:01:05 atoi=argument to int 2012-01-09T14:01:09 itoa?? 2012-01-09T14:01:15 array to int 2012-01-09T14:01:16 integer to argument? 2012-01-09T14:01:19 hehe 2012-01-09T14:01:31 since C strings are just null-terminated char arrays 2012-01-09T14:01:34 itoa isn't needed though 2012-01-09T14:01:38 sprintf 2012-01-09T14:01:49 you can also try and hash 0-999 and use % 1000 and / 1000 to subdivide the number you want to turn into a string, how does that sound? 2012-01-09T14:01:56 rwest: what's the maximum number of digits for an 'int'? 2012-01-09T14:02:02 won't vary per platform? 2012-01-09T14:02:06 that's an annoying thing to deal with 2012-01-09T14:02:32 unless you work with embedded devices, I assume it is always 32-bit 2012-01-09T14:02:33 thestinger: jumped in at the end of this, guess i should scroll up for the initial issue heh 2012-01-09T14:02:33 *** Redgis has joined #aichallenge 2012-01-09T14:02:42 theres always sizeof 2012-01-09T14:03:25 I don't think you can write a portable itoa without special cases 2012-01-09T14:03:34 I was reading about it and the freebsd implementation is broken on many platforms 2012-01-09T14:03:48 since you need to deal with signed ints 2012-01-09T14:04:24 I have never had an issue using sprintf to convert 2012-01-09T14:04:54 I don't get why the size of the int matters? 2012-01-09T14:05:04 well, the number of digits 2012-01-09T14:05:07 he is talking about implementing sprintf 2012-01-09T14:05:10 oh 2012-01-09T14:05:10 sort of 2012-01-09T14:05:11 so you can make an appropriately sized buffer 2012-01-09T14:05:21 or not 2012-01-09T14:05:27 why would you want to implement sprintf? 2012-01-09T14:05:31 when it's there"? 2012-01-09T14:05:34 I don't... 2012-01-09T14:05:39 :) 2012-01-09T14:05:45 you need to use a buffer with sprintf 2012-01-09T14:06:01 you can get the size you need with std::numeric_limits in C++ 2012-01-09T14:06:12 anyway 2012-01-09T14:06:18 snprintf! 2012-01-09T14:06:18 this is a tangent from the real conversation :P 2012-01-09T14:06:27 no 2012-01-09T14:06:28 *** McLeopold_ has joined #aichallenge 2012-01-09T14:06:29 that doesn't help 2012-01-09T14:06:40 you still need to know how big you need the buffer if you want it to actually convert properly 2012-01-09T14:06:48 you know what the max number of chaarcters you need 2012-01-09T14:07:05 snprintf(str, sizeof(int), ... 2012-01-09T14:07:11 snprintf stops you from having a buffer overflow, you'll still have a bug if it's too small 2012-01-09T14:07:13 thestinger, you made me solve euler problems to keep ahead of you :P 2012-01-09T14:07:18 McLeopold_: lol 2012-01-09T14:07:45 rwest: anyway, the original topic: 2012-01-09T14:07:48 rwest: i dont understand that 2012-01-09T14:07:57 I want a generic to_string function 2012-01-09T14:08:02 you copy 4 byte? 2012-01-09T14:08:18 so I was going to specialize it for each built-in type, and use stringstreams for other types 2012-01-09T14:08:19 mcstar: whoops fail 2012-01-09T14:08:30 but I found boost::lexical_cast and it already does that for me 2012-01-09T14:08:46 I should try doing it anyway 2012-01-09T14:09:02 can probably do it faster than them since I want from_string and to_string 2012-01-09T14:09:13 lexical_cast is more general 2012-01-09T14:09:16 pow(2,(sizeof(int)*8-1)) 2012-01-09T14:09:30 it goes type -> string representation -> type 2012-01-09T14:09:38 not just type -> string or string -> type 2012-01-09T14:09:58 *** McLeopold_ has quit IRC (Remote host closed the connection) 2012-01-09T14:09:59 the max size 2012-01-09T14:10:02 then go from there 2012-01-09T14:11:11 *** McLeopold has joined #aichallenge 2012-01-09T14:11:31 thestinger: I just use tcl or php for any of the problems on PE that require many conversions 2012-01-09T14:12:08 rwest: well, I don't just want it for euler :P 2012-01-09T14:12:14 anyway, I discovered something great 2012-01-09T14:12:21 C++11 has std::to_string :) 2012-01-09T14:12:34 http://en.cppreference.com/w/cpp/string/basic_string/to_string 2012-01-09T14:12:54 nice 2012-01-09T14:13:02 I should really get better at C++ 2012-01-09T14:13:10 maybe for the next challenge I will use it 2012-01-09T14:15:53 *** Paradoxial has joined #aichallenge 2012-01-09T14:16:24 *** g0llum has joined #aichallenge 2012-01-09T14:17:13 can someone message me with my nick so I can test xchat-gnome? 2012-01-09T14:17:29 rwest: try with log_10 +/- something 2012-01-09T14:17:41 *** Paradoxial has quit IRC (Client Quit) 2012-01-09T14:17:54 McLeopold 2012-01-09T14:17:55 oops 2012-01-09T14:18:03 wait, it kinda worked... 2012-01-09T14:18:07 *** conor_f has joined #aichallenge 2012-01-09T14:18:10 do it in this main window again 2012-01-09T14:18:14 McLeopold: 2012-01-09T14:18:15 McLeopold: ! 2012-01-09T14:18:30 thx 2012-01-09T14:18:43 I see the popup, but when I mouse over, it blurs, that's weird 2012-01-09T14:18:48 20 bytes = sufficient for a 64-bit int 2012-01-09T14:18:56 yeah, std::to_string is perfect 2012-01-09T14:19:43 well not really but whatever 2012-01-09T14:19:55 stringstream: ./string 8.24s user 0.00s system 99% cpu 8.246 total 2012-01-09T14:20:02 std::to_string: ./string 1.78s user 0.00s system 99% cpu 1.779 total 2012-01-09T14:20:07 boost::lexical_cast: g++ -std=c++0x -O3 -s -Wall -Wextra -o string string.cc 2012-01-09T14:20:11 oops, what 2012-01-09T14:20:19 ./string 1.08s user 0.00s system 99% cpu 1.087 total 2012-01-09T14:20:22 * 2012-01-09T14:22:50 ./string 1.25s user 0.00s system 99% cpu 1.251 total 2012-01-09T14:22:53 that's sprintf 2012-01-09T14:24:53 might as well just use boost 2012-01-09T14:26:43 McLeopold: I'll have to catch up to you again now :) 2012-01-09T14:27:37 I intend to stay ahead :P 2012-01-09T14:30:13 If I do more Eulers, I'll probably want to share some code. Maybe even make it one project in Eclipse. How do you organize your code? All in one directory? Copy&Paste? 2012-01-09T14:31:19 I just have an euler directory with subdirs for all the problems 2012-01-09T14:31:27 and then multiple solutions in each 2012-01-09T14:31:56 mkdir {1..100} 2012-01-09T14:31:58 :P 2012-01-09T14:32:08 oh well... :p 2012-01-09T14:32:22 I did build a package in python to generate prime numbers, but I lost it :( 2012-01-09T14:32:36 I think I made a euler package 2012-01-09T14:33:09 McLeopold: sounds reasonable to me, since many problems evolve around primes or other clearly defined ranges of numbers 2012-01-09T14:33:22 I have a fast sieve but I can't efficiently extend it if it ends up not being large enough 2012-01-09T14:33:44 yeah, I had a function that would generate blocks in millions, and save it pickled to the filesystem 2012-01-09T14:33:56 so, it was slow to load, but I didn't have to process 2012-01-09T14:34:15 well, save it in /dev/shm (or /tmp if you have a sane distro :P) 2012-01-09T14:34:38 I usually favor time over space in all my algorithms 2012-01-09T14:35:09 McLeopold: loading a file with numbers ... isn't that cheating? 2012-01-09T14:35:24 It's like hardcoding part of the solution 2012-01-09T14:35:32 it's memozation 2012-01-09T14:36:25 Sure, I can let the compiler generate the result of an Euler problem and then execute writeln("134133"); and be done ^^ 2012-01-09T14:36:43 i just memoized the result of the problem at hand 2012-01-09T14:37:01 well, I'm memorizing things like prime numbers or other functions, then use them in problems 2012-01-09T14:37:15 I wrote the code to generate the numbers, so I don't feel it's cheating 2012-01-09T14:38:00 primes_below(10**7) is probably faster than reading them from the disk anyway 2012-01-09T14:38:16 probably not 2012-01-09T14:38:22 it depends on how you load it 2012-01-09T14:38:22 thestinger: then again they are in the FS cache 2012-01-09T14:38:45 you could to memory mapped files 2012-01-09T14:39:17 primes_below(10**7) takes under a second in python 2012-01-09T14:39:48 I'm just using eratosthenes sieve with the easy optimizations 2012-01-09T14:42:12 so I only check odd numbers, and only up to sqrt(limit) (but written as i * i < n + 1 because it's faster to multiply with each iteration than do a single sqrt call) 2012-01-09T14:42:29 oh wow 2012-01-09T14:42:30 lol 2012-01-09T14:42:46 and then you only need to cancel out certain multiples of i 2012-01-09T14:43:03 well, certain multiples of i* 2012-01-09T14:43:28 that's rather fishy though 2012-01-09T14:43:34 http://sprunge.us/OZhU anyway that's the relevant code in C++, in python I used a slice and it's hard to understand 2012-01-09T14:43:38 amstan_: why? 2012-01-09T14:43:42 the sqrt call taking longer than 10**7 calls to i*i 2012-01-09T14:43:49 well, in C++ 2012-01-09T14:43:51 nvm, less 2012-01-09T14:44:04 the i*i gets optimized away to nothing 2012-01-09T14:44:10 the time is lost in the noise of the for loop 2012-01-09T14:44:19 how does i*i get optimized? 2012-01-09T14:44:27 it's a single opcode 2012-01-09T14:44:30 it doesn't matter 2012-01-09T14:44:36 oh, cool 2012-01-09T14:44:38 i didn't know that 2012-01-09T14:44:43 i = 5; is probably slower 2012-01-09T14:44:49 lol 2012-01-09T14:45:01 probably 2012-01-09T14:45:38 i guess it depends on the arch though, not sure if i would do that on avr 2012-01-09T14:46:12 sqrt() is probably even slower (relatively) on a crappier processor where they don't have an FPU 2012-01-09T14:47:15 anyway I think it's bottlenecked by memory bandwidth 2012-01-09T14:47:54 in python the trick is to do stuff with slices, but I find it hard to read 2012-01-09T14:51:08 *** amstan_ has quit IRC (Ping timeout: 240 seconds) 2012-01-09T14:52:49 *** Accoun has quit IRC () 2012-01-09T15:08:20 *** Accoun has joined #aichallenge 2012-01-09T15:19:11 *** alehorst has joined #aichallenge 2012-01-09T15:28:19 *** dapplegate has joined #aichallenge 2012-01-09T15:33:38 http://projecteuler.net/problem=78 ugh 2012-01-09T15:33:40 I'm an idiot 2012-01-09T15:33:47 this is just an integer partition question 2012-01-09T15:34:50 hummm 2012-01-09T15:35:07 there are 5 coins 2012-01-09T15:35:12 so your target is 5 2012-01-09T15:35:21 and the integers you're using are [1..5] 2012-01-09T15:35:37 I have n_partitions written already 2012-01-09T15:35:59 I actually looked for more partition problems but somehow this one didn't register in my brain... 2012-01-09T15:38:18 ugh... too slow in python 2012-01-09T15:38:24 C++ it is... 2012-01-09T15:44:04 oh 2012-01-09T15:44:13 and my n_partitions uses dynamic programming :) 2012-01-09T15:44:35 I can just make a special function for this that reuses the data structure 2012-01-09T15:44:37 hm 2012-01-09T15:49:29 *** dvladim has joined #aichallenge 2012-01-09T15:51:13 *** Kurnevsky has quit IRC (Quit: Instantbird 1.0) 2012-01-09T15:58:47 *** epicmonkey has joined #aichallenge 2012-01-09T16:00:51 *** dvladim has quit IRC (Ping timeout: 252 seconds) 2012-01-09T16:03:55 Facebook Hacker Cup 2012: https://www.facebook.com/hackercup 2012-01-09T16:07:09 real address :( 2012-01-09T16:07:19 Any idea what the challenges would be like? 2012-01-09T16:07:34 I'm not clicking any urls with facebook in it :) 2012-01-09T16:10:55 *** rwest_ has quit IRC (Quit: Lost terminal) 2012-01-09T16:14:00 heh 2012-01-09T16:14:17 I'm considering it because of the possibility of a free tshirt lol 2012-01-09T16:14:35 I'm prepared to give away my privacy for the price of a tshirt, yes, I know 2012-01-09T16:22:15 *** choas has joined #aichallenge 2012-01-09T16:24:50 *** sigh has joined #aichallenge 2012-01-09T16:34:16 okay, this attempt was hopeless 2012-01-09T16:36:56 *** Palmik has quit IRC (Remote host closed the connection) 2012-01-09T16:38:03 *** magiik has quit IRC (Ping timeout: 268 seconds) 2012-01-09T16:38:19 *** conor_f has quit IRC (Ping timeout: 276 seconds) 2012-01-09T16:38:28 thestinger: theres some new addition> http://en.cppreference.com/w/cpp/string/basic_string/to_string 2012-01-09T16:38:50 can i see one of yours when you are testing performance? 2012-01-09T16:39:17 one of your code* 2012-01-09T16:39:18 s 2012-01-09T16:39:20 damn 2012-01-09T16:39:32 I was just going in a loop and converting an int to a string 2012-01-09T16:39:40 and making sure it wasn't optimized out 2012-01-09T16:39:52 changin i character? 2012-01-09T16:39:56 1 2012-01-09T16:40:02 *** magiik has joined #aichallenge 2012-01-09T16:40:05 well, int to string 2012-01-09T16:40:18 but different ints always? 2012-01-09T16:40:23 yes 2012-01-09T16:40:25 ok 2012-01-09T16:40:45 for (unsigned i = 0; i < 10000000; i++) { volatile std::string s = whatever(i); } basically 2012-01-09T16:40:49 i just try to put the stringstream and iostream class into place in my head 2012-01-09T16:41:07 well 2012-01-09T16:41:19 it always calls its constructor/destructor 2012-01-09T16:41:24 boost::lexical_cast is faster than sprintf, even if I use a char array with sprintf instead of a std::string 2012-01-09T16:41:30 i dont think the compiler can optimize that away 2012-01-09T16:41:46 mcstar: volatile says "you can't optimize this" anyway iirc 2012-01-09T16:41:55 yes 2012-01-09T16:42:04 im just saying 2012-01-09T16:42:15 it might not create a new object on the stack 2012-01-09T16:42:22 *** X-Scale has joined #aichallenge 2012-01-09T16:42:26 but it still needs to call its constructors and destructors 2012-01-09T16:42:31 ah 2012-01-09T16:42:33 (not plulars) 2012-01-09T16:43:16 maybe 2012-01-09T16:43:18 gcc is pretty smart 2012-01-09T16:43:46 yes, idk, just a thoguht 2012-01-09T16:43:50 reducing the scope of variables results in the same performance (or better), even with a constructor/destructor to worry about 2012-01-09T16:44:16 anyway, stringstreams are slow 2012-01-09T16:44:30 i used them in my bot 2012-01-09T16:44:40 to_string is a bit slower than sprintf (which makes sense, it uses std::string) 2012-01-09T16:44:47 but somehow boost::lexical_cast is faster than both 2012-01-09T16:44:58 so yeah, just going to use that everywhere :P 2012-01-09T16:45:19 far more generic/powerful than std::to_string anyway 2012-01-09T16:50:18 anyway, trying to do 78 2012-01-09T16:50:26 running n_partitions for each n is too slow 2012-01-09T16:51:16 but I'm just going to make a version which goes forever 2012-01-09T16:52:04 DONT share your solution 2012-01-09T16:52:09 I won't 2012-01-09T16:52:11 lol 2012-01-09T16:52:13 I haven't solved it at all 2012-01-09T16:52:29 mcstar: have you written n_partitions yet? 2012-01-09T16:52:33 for the other partition problems 2012-01-09T16:52:39 *** conor_f has joined #aichallenge 2012-01-09T16:52:41 31 and 76 2012-01-09T16:52:48 take a look at my solved problems 2012-01-09T16:52:52 oh 2012-01-09T16:52:58 ill check 31 2012-01-09T16:53:15 oh 2012-01-09T16:53:18 you could solve 31 other ways 2012-01-09T16:53:20 that one was fun 2012-01-09T16:53:25 That's some sort of knapsack problem? 2012-01-09T16:53:31 pairofdice: integer partition problem 2012-01-09T16:53:38 Yeah, exactly 2012-01-09T16:53:41 ah 2012-01-09T16:53:51 anyway, I wrote two n_partition functions 2012-01-09T16:53:56 T n_partitions(T target) { 2012-01-09T16:54:11 that one assumes that [1..target] are all used 2012-01-09T16:54:13 T n_partitions(T target, Iter begin, Iter end) { 2012-01-09T16:54:15 thestinger: its in the forum 2012-01-09T16:54:20 and then that for 36/76 2012-01-09T16:54:27 78 is kicking my butt 2012-01-09T16:54:36 well 2012-01-09T16:54:36 http://projecteuler.net/thread=31;page=8 2012-01-09T16:54:50 I can solve 31 and 76 in like 6ms 2012-01-09T16:55:07 but 78 requires a new function 2012-01-09T16:55:20 my solution is still very concise i think 2012-01-09T16:55:24 I've 11224 as divisible my 100,000 2012-01-09T16:55:30 i know it takes ages but ... 2012-01-09T16:56:19 mcstar: none of those things in the forums look like a generic solution 2012-01-09T16:56:49 *** pairofdice has quit IRC (Quit: When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl.) 2012-01-09T16:57:07 thestinger: when i encounter a problem that needs a general one be sure ill write one 2012-01-09T16:57:18 76 and 78 :) 2012-01-09T16:57:29 far ahead 2012-01-09T16:57:31 they are 2012-01-09T16:58:04 McLeopold: do you have a fast function to solve integer partitions? 2012-01-09T16:58:15 it's kinda fast 2012-01-09T16:58:17 even with that I can't solve 78 in C++ without taking forever 2012-01-09T16:58:31 McLeopold: how long to solve 31 and 76? 2012-01-09T16:58:40 76 was instant 2012-01-09T16:58:41 ah 2012-01-09T16:58:44 ive seen that one 2012-01-09T16:58:52 31 was 3 years ago :P 2012-01-09T16:59:00 *** JorgeB has quit IRC (Quit: Textual IRC Client: http://www.textualapp.com/) 2012-01-09T16:59:09 McLeopold: so did it halt? 2012-01-09T16:59:11 yeah 76 is instant in python :P 2012-01-09T16:59:14 *** JorgeB has joined #aichallenge 2012-01-09T16:59:52 I'm building up a matrix to solve 2012-01-09T17:00:05 kinda link in the 76 forum 2012-01-09T17:00:07 like 2012-01-09T17:01:46 is there any special relationship between partition numbers? 2012-01-09T17:02:11 well 2012-01-09T17:02:17 I'm building up an array 2012-01-09T17:02:30 so I just need to modify it to use realloc basically (or .resize with a vector) 2012-01-09T17:02:36 so you have to solve all the smaller numbers first? 2012-01-09T17:02:42 yes 2012-01-09T17:02:45 me too 2012-01-09T17:02:50 but it takes forever 2012-01-09T17:02:58 hm 2012-01-09T17:03:01 well 2012-01-09T17:03:03 I haven't actually tried yet 2012-01-09T17:03:25 I can get 1000 solved in about 1 second, but then it just gets really slow after that 2012-01-09T17:04:04 *** glibc detected *** ./solution: realloc(): invalid next size: 0x0000000002546010 *** 2012-01-09T17:04:07 ugh 2012-01-09T17:05:45 *** JorgeB has quit IRC (Ping timeout: 252 seconds) 2012-01-09T17:08:16 haha you guys are doing project euler now? 2012-01-09T17:08:42 yeah :) 2012-01-09T17:08:48 i got hooked on that several years ago. last one i did was tetronimoes 2012-01-09T17:09:14 ok, not going to use malloc/realloc/free 2012-01-09T17:09:18 vector it is :P 2012-01-09T17:09:37 asloane: is it i or l ?(the 1) 2012-01-09T17:13:15 now he is hooked on the problems again 2012-01-09T17:15:12 i 2012-01-09T17:15:42 it's a stupid handle but the domain was open 2012-01-09T17:15:43 i suspected so 2012-01-09T17:15:54 but ive seen on some blog referred to you as alkon 2012-01-09T17:16:06 whatever 2012-01-09T17:16:18 i should have picked something like.. xkcd 2012-01-09T17:16:28 its cool.. 2012-01-09T17:16:42 i havent read your code yet, tbh 2012-01-09T17:16:50 just perused some of it 2012-01-09T17:18:27 asloane: congrats, you ranked very well 2012-01-09T17:18:36 thanks. i'm kind of surprised by that. 2012-01-09T17:20:22 thestinger: whats your baseline? 2012-01-09T17:20:31 time/iterations 2012-01-09T17:20:39 for which? 2012-01-09T17:20:42 string problem 2012-01-09T17:20:47 oh 2012-01-09T17:20:53 let me code it again, sec 2012-01-09T17:20:59 :) 2012-01-09T17:21:00 ha, i wonder who http://tcpants.com/player/A1k0n_dub is 2012-01-09T17:21:13 mcstar: i'm totally blanking on what you called your entry 2012-01-09T17:21:37 it was the best AgentSmith around 2012-01-09T17:21:42 oh yeah 2012-01-09T17:21:43 or any kind of agent 2012-01-09T17:22:15 ah, those guys couldnt deal with defeat, and they are still developing? 2012-01-09T17:22:16 #2 in hungary 2012-01-09T17:22:26 yeah, denes got better 2012-01-09T17:22:29 and mine worse 2012-01-09T17:22:40 i suspect in the last 2 days i added better global startegy 2012-01-09T17:22:49 but had a bad impact on my battle 2012-01-09T17:22:51 surprisingly i beat pguillory right at the end. the choice of opponents really shook up the ranking 2012-01-09T17:22:58 and i ended up losing too much ants unnecessarily 2012-01-09T17:23:06 bummer 2012-01-09T17:23:19 i was afraid to touch it by the end 2012-01-09T17:23:51 seeing the results, i suspect i woudlnt end up in top100 anyway, so im not that disappointed 2012-01-09T17:23:56 ./string 1.12s user 0.01s system 99% cpu 1.125 total 2012-01-09T17:24:06 mcstar: http://sprunge.us/QABE 2012-01-09T17:24:12 thanks 2012-01-09T17:24:34 constexpr is actually pretty need 2012-01-09T17:25:10 neat* 2012-01-09T17:25:29 omg aerique's multiplayer asteroids looks sweet 2012-01-09T17:27:28 *** ikaros has quit IRC (Quit: Ex-Chat) 2012-01-09T17:27:49 thestinger: 4.1s unopt. 1.7 -O3 2012-01-09T17:29:03 gcc 4.6? 2012-01-09T17:29:17 4 6 2 2012-01-09T17:29:32 it seems the boost one can be optimized much agresively 2012-01-09T17:29:39 *** conor_f has quit IRC (Quit: leaving) 2012-01-09T17:29:50 4.7s -> 3.7 in the to_string case 2012-01-09T17:30:02 try sprintf 2012-01-09T17:30:08 even with a static char buffer 2012-01-09T17:30:19 slower than boost here, faster than to_string though 2012-01-09T17:31:12 aw, PGO didn't help :( 2012-01-09T17:32:14 oh, it speeds up to_string a tiny bit 2012-01-09T17:32:45 sprintf: 2012-01-09T17:32:49 2.5->2.5 2012-01-09T17:33:21 with a char buffer? 2012-01-09T17:33:26 zep 2012-01-09T17:33:35 yeah, that surprises me 2012-01-09T17:33:45 boost optimized more than glibc 2012-01-09T17:33:48 *** sigh has quit IRC (Remote host closed the connection) 2012-01-09T17:35:25 thestinger: 2.667s 2012-01-09T17:35:28 with boost 2012-01-09T17:35:32 hehe 2012-01-09T17:35:33 o3 2012-01-09T17:35:39 whats the trick you might ask 2012-01-09T17:35:53 wait, sprintf was faster? 2012-01-09T17:36:00 in this case 2012-01-09T17:36:04 what did i change? 2012-01-09T17:36:20 std::string -> char a[]? 2012-01-09T17:36:23 not sure 2012-01-09T17:36:42 s[0]=count; 2012-01-09T17:36:56 i added this, actually changing the content of the stirng 2012-01-09T17:36:57 *** choas has quit IRC (Ping timeout: 240 seconds) 2012-01-09T17:37:16 hm, what? 2012-01-09T17:37:56 string s=boost::lexical_cast(count); 2012-01-09T17:38:00 s[0]=count; 2012-01-09T17:38:10 oh, I think gcc uses copy-on-write strings 2012-01-09T17:38:15 anyway the trcik is here 2012-01-09T17:38:20 count is an int 2012-01-09T17:38:26 so it cant do some optimization 2012-01-09T17:38:33 maybe it is related to see? 2012-01-09T17:38:44 sse 2012-01-09T17:39:04 mcstar: well, I think gcc uses reference counted copy-on-write strings 2012-01-09T17:39:06 not sure 2012-01-09T17:39:13 so it has to copy the string and make a new one when you change it 2012-01-09T17:39:21 really? 2012-01-09T17:39:23 nfw 2012-01-09T17:39:29 i maen if you say so 2012-01-09T17:39:49 i thought its just a managed vector 2012-01-09T17:39:51 yes 2012-01-09T17:39:57 libstdc++ uses COW for std::string 2012-01-09T17:40:07 so you're forcing a copy 2012-01-09T17:40:32 mcstar: are you compiling with -std=c++0x? 2012-01-09T17:40:36 yes 2012-01-09T17:40:44 I think COW for std::string is forbidden by C++11, but they may not respect it yet 2012-01-09T17:41:48 I'll test with clang 2012-01-09T17:41:54 libc++ doesn't use COW strings 2012-01-09T17:42:40 ./string 1.07s user 0.00s system 99% cpu 1.076 total 2012-01-09T17:42:44 with boost 2012-01-09T17:42:50 clang++ -O3 -std=c++11 -o string string.cc 2012-01-09T17:42:57 compiled like that (so still using libstdc++) 2012-01-09T17:43:24 oh, weird 2012-01-09T17:43:32 Arch doesn't ship libc++ with clang apparently 2012-01-09T17:43:56 i wanted to compile xmonad from darcs and i couldnt 2012-01-09T17:43:59 :( 2012-01-09T17:44:07 why? 2012-01-09T17:44:12 does it need ghc 7.2? 2012-01-09T17:44:14 some weird error 2012-01-09T17:44:20 i dont remmeber 2012-01-09T17:44:32 that was ok 2012-01-09T17:45:47 I got the pattern for 78, finally 2012-01-09T17:45:55 actually xmonad was ok, the problem was with xmonad-contrib-darcs 2012-01-09T17:46:06 i wanna to it alone 2012-01-09T17:46:09 dontellmle 2012-01-09T17:46:27 (too late, im getting typoid) 2012-01-09T17:46:31 gn 2012-01-09T17:46:34 n8 2012-01-09T17:46:37 *** mcstar has left #aichallenge 2012-01-09T17:48:52 *** foRei has quit IRC (Quit: Bye) 2012-01-09T17:49:01 there 2012-01-09T17:49:50 mleise: I guess I've found the pattern too, but I'm still not totally convinced. 2012-01-09T17:51:15 It looks crazy, but I'll just trial and error with the result 2012-01-09T17:51:29 oh, I figured it out now 2012-01-09T17:51:54 There is always the issue of counting too many or too few outcomes. 2012-01-09T17:52:00 oh come on, you can't all figure it out at the same time ^^ 2012-01-09T17:52:07 heh 2012-01-09T17:52:17 well 2012-01-09T17:52:24 I was benchmarking string stuff with mcstar 2012-01-09T17:52:24 Let me code a simple solution to see if it makes sense 2012-01-09T17:52:26 lol 2012-01-09T17:52:29 I had the solution all along 2012-01-09T17:52:43 I just needed to add a thing to print it and stop when I get the right answer :) 2012-01-09T17:53:14 *** Jak_o_Shadows has joined #aichallenge 2012-01-09T17:53:45 also, I need to set a maximum to go up to atm... 2012-01-09T17:54:01 I could just keep resizing the vector but that would take more code 2012-01-09T17:54:50 meh, maybe I didn't solve it 2012-01-09T17:59:52 got an answer but it was apparently wrong... 2012-01-09T18:00:29 me too 2012-01-09T18:00:30 oh, I printed p(n) and not n 2012-01-09T18:00:38 77180 is not right :(# 2012-01-09T18:00:46 I just coded 78 in c, segmentation fault :( 2012-01-09T18:00:53 McLeopold: lol 2012-01-09T18:01:02 McLeopold: I figured out how to do it 2012-01-09T18:01:03 too bad I don't know C :) 2012-01-09T18:01:20 Sorry, but the answer you gave appears to be incorrect. :( 2012-01-09T18:01:23 nope 2012-01-09T18:01:25 apparently not 2012-01-09T18:02:16 so int m[1500][1500] is bad? 2012-01-09T18:02:19 yes 2012-01-09T18:02:22 that's on the stack 2012-01-09T18:02:33 how should I do it? 2012-01-09T18:02:34 use malloc or calloc 2012-01-09T18:02:40 or use C++ and save yourself a lot of pain 2012-01-09T18:03:54 McLeopold: unsigned *a = malloc(1500 * 1500 * sizeof (unsigned)) and then index with a[row * 1500 + col] 2012-01-09T18:04:45 or you can an array with pointers to arrays (which is what std::vector> in C++ will do) 2012-01-09T18:04:49 can make* 2012-01-09T18:05:01 Or make it an array of pointer to arrays of ints...that will allow you the simpler a[row][col] notation. 2012-01-09T18:05:40 annoying to allocate and deallocate though in C 2012-01-09T18:05:49 vector > m(1500, vector(1500, 0)); :P 2012-01-09T18:05:52 how do I check for a null pointer return? 2012-01-09T18:05:54 c++ <3 2012-01-09T18:06:57 McLeopold: if (!a) { // out of memory } 2012-01-09T18:07:02 or if (a == NULL) { } 2012-01-09T18:07:23 and you have to free(a) afterwards ofc :) 2012-01-09T18:07:34 anyway C++ makes it easier :P 2012-01-09T18:09:18 so... my code thinks the answer is 158128 but it isn't 2012-01-09T18:09:21 :( 2012-01-09T18:10:15 *** g0llum has quit IRC (Read error: Connection reset by peer) 2012-01-09T18:10:30 oh wait ... integer overflow ! 2012-01-09T18:10:32 oh, it overflows 2012-01-09T18:10:37 gmp time 2012-01-09T18:10:52 copycat -.- 2012-01-09T18:11:39 gmp is really easy to use in C++ which is nice 2012-01-09T18:12:22 yay, template errors 2012-01-09T18:12:40 ../../c++/util.hh:113:13: error: no match for ‘operator[]’ in ‘combinations[n]’ 2012-01-09T18:12:43 .. 2012-01-09T18:12:51 im not sure if I really want to do what I do anymore 2012-01-09T18:12:59 std::vector has no operator[] apparently... 2012-01-09T18:13:02 which problem are you doing? 2012-01-09T18:13:06 78 2012-01-09T18:13:21 yes 2012-01-09T18:13:36 oh nvm silly typo 2012-01-09T18:13:55 i mean... these numbers can grow large really quick 2012-01-09T18:14:07 gmp in C is awful 2012-01-09T18:14:11 dang, still segfaulting... 2012-01-09T18:14:48 mpz_class a = 5, b = 10; std::cout << a * b << std::endl; etc. is really not that part in comparison 2012-01-09T18:14:56 not that bad* 2012-01-09T18:15:02 I really can't type at all when I'm tired :) 2012-01-09T18:16:29 omg this is longer than PI 2012-01-09T18:16:33 π 2012-01-09T18:16:37 you're.. not.. bruteforcing that are you? 2012-01-09T18:16:41 asloane: no 2012-01-09T18:16:43 well 2012-01-09T18:16:46 almost 2012-01-09T18:16:53 https://oeis.org/A000041 2012-01-09T18:16:59 ^ essential for project euler 2012-01-09T18:17:03 I have an n_partitions function which can do 76 in less than 1ms 2012-01-09T18:17:08 (in general) 2012-01-09T18:17:31 it uses dynamic programming (each consecutive answer ends up in a vector), so I'm just doing it with a massive limit 2012-01-09T18:17:36 asloane: that's cheating :P 2012-01-09T18:17:40 BigInt is not optimized well in D 2012-01-09T18:17:53 jeez... this takes ages to compute 2012-01-09T18:18:06 even with DP you need to find p(n) = 1e6*k 2012-01-09T18:18:20 hmm 2012-01-09T18:18:47 ew, even more errors now 2012-01-09T18:19:55 http://pastebin.com/n6f8C2Lf can I has help? 2012-01-09T18:20:18 nooo this can't be incorrect! 2012-01-09T18:20:40 McLeopold: try using libmudflap 2012-01-09T18:20:47 -fmudflap -lmudflap in your gcc command 2012-01-09T18:20:55 what does that do? 2012-01-09T18:20:56 it will tell you when you do an out-of-bounds array write/read 2012-01-09T18:22:08 oh, nice 2012-01-09T18:22:30 not to mention that D has that on default ;) 2012-01-09T18:23:09 what the hell? I apparently can't make a std::vector 2012-01-09T18:23:12 stupid gmp... 2012-01-09T18:23:31 oh, I can 2012-01-09T18:23:35 just can't use a constructor... 2012-01-09T18:24:03 nvm, fixed everything 2012-01-09T18:25:15 well, time to see how long this takes with gmp :) 2012-01-09T18:26:23 anyways you don't need bignums for this 2012-01-09T18:26:27 *** dici has quit IRC (Read error: Connection reset by peer) 2012-01-09T18:26:42 asloane: do I need to use 64-bit ints though? 2012-01-09T18:26:45 since + and * are closed under % 2012-01-09T18:26:52 no, you need numbers between 0 and 999999 2012-01-09T18:27:57 asloane: what's your level on PE ? 2012-01-09T18:28:57 uh, i've solved 59 out of 366 2012-01-09T18:28:58 asloane: my code thinks n_partitions(159128u) is 2409000000 2012-01-09T18:29:01 haven't looked at this in years 2012-01-09T18:29:13 which is the first I find where % 1000000 is 0 2012-01-09T18:29:19 thestinger: and is that the answer? 2012-01-09T18:29:23 no... apparently not 2012-01-09T18:29:28 huh 2012-01-09T18:29:33 I even checked +/- 1 2012-01-09T18:29:35 it's def not <= 100000 2012-01-09T18:29:44 I just use only BigInts now, just to be sure there is no overflow happening anywhere 2012-01-09T18:29:59 well, unsigned ints just wrap 2012-01-09T18:30:13 lol the numbers are several screen pages long... i do something wrong 2012-01-09T18:30:18 mleise: :) 2012-01-09T18:30:29 dammit you're going to draw me into this now 2012-01-09T18:30:58 meh 2012-01-09T18:31:05 I don't think my n_partitions function is wrong 2012-01-09T18:31:16 I somehow missed an earlier number 2012-01-09T18:31:23 im faster brute forcing on the submit button in PE :/ 2012-01-09T18:32:07 strcat@arch i ~/projects/euler/78 % time ./solution 2012-01-09T18:32:10 2409000000 2012-01-09T18:32:11 ./solution 16.32s user 0.00s system 99% cpu 16.330 total 2012-01-09T18:32:13 :( 2012-01-09T18:32:31 anyway, that's not the code for actually solving the question 2012-01-09T18:32:44 thestinger, undefined reference to `__mf_lc_mask' :( 2012-01-09T18:33:02 McLeopold: huh? post your code 2012-01-09T18:33:08 same code 2012-01-09T18:33:16 oh 2012-01-09T18:33:17 I just added the mudflap stuff 2012-01-09T18:33:30 now it highlights a bunch of code as bad 2012-01-09T18:33:36 I'm in eclipse, btw 2012-01-09T18:33:55 gcc -fmudflap -o test test.c -lmudflap 2012-01-09T18:34:08 you have to put -l after what uses it now 2012-01-09T18:34:20 especially if you have -Wl,--as-needed on 2012-01-09T18:34:27 do I need an include ? 2012-01-09T18:34:33 no 2012-01-09T18:34:54 McLeopold: are you running gcc yourself, or eclipse is doing it? 2012-01-09T18:35:02 eclipse 2012-01-09T18:35:11 try doing it yourself from the command-line 2012-01-09T18:35:25 gcc -O0 -g3 -Wall -c -fmessage-length=0 -fmudflap -lmudflap -std=c99 -MMD -MP -MF"src/EulerC.d" -MT"src/EulerC.d" -o "src/EulerC.o" "../src/EulerC.c" 2012-01-09T18:35:36 -lmudflap should be last 2012-01-09T18:37:25 I fear my calculations are wrong :-( I'll never solve this problem. 2012-01-09T18:37:43 mleise: can you solve 76 with the same code? 2012-01-09T18:37:46 I only verified the result for 1 to 10 2012-01-09T18:37:55 76 requires you to be off-by-one 2012-01-09T18:38:00 it's not actually p(n) 2012-01-09T18:38:03 it's p(n) - 1 2012-01-09T18:38:19 thestinger: it is the same problem from the looks of it 2012-01-09T18:38:31 yeah 2012-01-09T18:38:31 *** Fandekasp has joined #aichallenge 2012-01-09T18:38:32 so is 31 2012-01-09T18:39:10 lol, I'm printing out n every 10k so I know something is happening 2012-01-09T18:39:13 anyway, this fails 2012-01-09T18:41:30 5: 7 2012-01-09T18:41:33 100: 190569292 2012-01-09T18:41:35 159128: 2409000000 2012-01-09T18:41:46 thestinger: btw, n_partitions(159128u) has a looooooooooot more digits than that 2012-01-09T18:41:55 asloane: yeah, it overflows 2012-01-09T18:42:09 maybe I should try mpz_class again 2012-01-09T18:42:24 just do all your computations mod 1000000 and save yourself the trouble 2012-01-09T18:42:31 ^ that 2012-01-09T18:42:52 43 seconds for the wrong result :( this sucks 2012-01-09T18:47:30 asloane: I use *2 in my calculations... I don't think I can modulo this without losing information 2012-01-09T18:47:51 I just use + 2012-01-09T18:47:54 well, += 2012-01-09T18:48:01 that doesn't matter though 2012-01-09T18:48:43 nice, my code is incredibly slow with gmp 2012-01-09T18:49:16 *** AlliedEnvy has joined #aichallenge 2012-01-09T18:49:39 thestinger, eclipse breaks the build into compile and link, should I split the mudflag stuff between them? also, simple gcc command in terminal works 2012-01-09T18:50:00 well, imo you should just use a Makefile and ignore eclipse's crap :P 2012-01-09T18:50:26 maybe, but I'd like to understand 2012-01-09T18:50:26 anyway yeah 2012-01-09T18:50:34 -fmudflap in compile, -lmudflap in link 2012-01-09T18:50:55 http://pastebin.com/kAkbdRfD 2012-01-09T18:51:13 mudflap* :P 2012-01-09T18:51:58 lol, problem 78 is evil 2012-01-09T18:52:55 http://pastebin.com/sLmvJKEq 2012-01-09T18:55:00 m[n1 * N + i1] += m[x-1 * N + j]; 2012-01-09T18:55:14 heh...I'm loving actually. 2012-01-09T18:55:35 loving it, that is 2012-01-09T18:55:39 check up to 50k with gmp 2012-01-09T18:55:42 taking forever 2012-01-09T18:55:44 ... 2012-01-09T18:57:51 ok, that's it. 2012-01-09T18:57:54 need to use opencl somehow 2012-01-09T18:58:57 oooh, nice catch 2012-01-09T18:59:05 McLeopold: well, that's what mudflap said 2012-01-09T18:59:09 it gives a line number 2012-01-09T18:59:14 where? 2012-01-09T18:59:20 pc=0x40711e location=`../src/EulerC.c:36:25 (main)' 2012-01-09T18:59:23 line 36 2012-01-09T18:59:26 wow this takes a while to compute 2012-01-09T18:59:27 I guess 25 is the column 2012-01-09T18:59:52 i think i ran out of RAM 2012-01-09T19:00:06 asloane: lol 2012-01-09T19:00:11 stuck at 46300 2012-01-09T19:00:30 well, mine goes fast with gmp 2012-01-09T19:00:33 but then it overflows 2012-01-09T19:00:52 are you saving the whole p(k,n) matrix? 2012-01-09T19:00:55 *** Redgis has quit IRC (Ping timeout: 240 seconds) 2012-01-09T19:00:59 want to see my code? 2012-01-09T19:01:22 asloane: well, I just have a massive array 2012-01-09T19:01:35 so combinations[1] is p(1), combinations[100] is p(100) 2012-01-09T19:01:40 and I calculate the next one based on the last 2012-01-09T19:01:46 can you do that? 2012-01-09T19:02:05 it's more complicated than that; see wikipedia 2012-01-09T19:02:11 well, it works for 76 2012-01-09T19:02:20 http://en.wikipedia.org/wiki/Partition_function_(number_theory)#Partition_function 2012-01-09T19:02:24 I have to go over the whole array, there's a nested loop 2012-01-09T19:04:21 asloane: I'm just using the recursive definition basically 2012-01-09T19:04:25 but without recursion 2012-01-09T19:04:31 what recursive definition? 2012-01-09T19:04:55 p(k, n) = 0 if k > n 2012-01-09T19:04:58 p(k, n) = 1 if k = n 2012-01-09T19:05:00 p(k, n) = p(k+1, n) + p(k, n − k) otherwise. 2012-01-09T19:05:11 okay, my code thinks it found the answer 2012-01-09T19:05:13 oh. yeah, but you need to keep track of the p(k,n) table for that 2012-01-09T19:05:30 yeah, I make a std::vector up to target+1 2012-01-09T19:05:38 and then return combinations[target]; 2012-01-09T19:05:57 Congratulations, the answer you gave to problem 78 is correct. !!!! :D 2012-01-09T19:06:07 is it >100000? 2012-01-09T19:06:09 asloane: I just added a check in my loop 2012-01-09T19:06:14 no, it's under 100k 2012-01-09T19:06:19 the overflow screwed it up 2012-01-09T19:06:37 How long does it take to find the solution, thestinger ? 2012-01-09T19:06:51 a _long_ time because I hacked something together 2012-01-09T19:06:55 I thought it was above 100k 2012-01-09T19:07:07 I can tell you how long n_partitions(right_answer) takes 2012-01-09T19:08:00 std::cout << n_partitions(55374) << std::endl; 2012-01-09T19:08:03 running that now 2012-01-09T19:08:12 well thanks for the answer 2012-01-09T19:08:13 gmp makes it slow as hell 2012-01-09T19:08:16 aw crap 2012-01-09T19:08:18 :( 2012-01-09T19:08:32 well, just pretend you didn't see that 2012-01-09T19:09:11 well, that was stupid of me... sorry about that 2012-01-09T19:09:26 i don't see how you compute that without 1.5 billion*sizeof(number) entries in a table 2012-01-09T19:09:35 36325300925435785930832331577396761646715836173633893227071086460709268608053489541731404543537668438991170680745272159154493740615385823202158167635276250554555342115855424598920159035413044811245082197335097953570911884252410730174907784762924663654000000 2012-01-09T19:09:42 that's the answer 2012-01-09T19:09:44 well 2012-01-09T19:09:52 for some reason I thought that was the answer 2012-01-09T19:09:57 I forgot I reversed the function call 2012-01-09T19:10:01 ./solution 84.37s user 0.01s system 99% cpu 1:24.40 total 2012-01-09T19:10:05 takes 1 minute and 24 secs 2012-01-09T19:10:56 asloane: do you want to see the actual code? 2012-01-09T19:11:00 sure 2012-01-09T19:11:05 asloane: http://sprunge.us/NBZC 2012-01-09T19:11:20 http://sprunge.us/jIhe and I used that for 31 2012-01-09T19:11:26 I did 31 and 76 in python though 2012-01-09T19:11:38 whaat that works? 2012-01-09T19:11:43 yes 2012-01-09T19:12:00 I just added a std::cout << combinations[i] << std::endl; to the outer loop 2012-01-09T19:12:06 and then called it with n_partitions(200000) 2012-01-09T19:12:21 ./solution 919.06s user 0.03s system 99% cpu 15:19.17 total 2012-01-09T19:12:46 15 mins with 200k as the target, but stopping at 55374 2012-01-09T19:12:58 huh. so you can't reuse partial results from that for another n_partitions(n+1) 2012-01-09T19:13:20 well 2012-01-09T19:13:24 at the end, the whole array is valid 2012-01-09T19:13:31 combinations[100], combinations[200], etc. 2012-01-09T19:13:41 but I couldn't figure out how to do it in a way where it would have an arbitrary limit 2012-01-09T19:14:08 so I had to make guesses at the maximum 2012-01-09T19:14:20 the whole overflow thing made it harder than it should have been... 2012-01-09T19:14:58 dang that's slow 2012-01-09T19:15:46 fast for 76 :P 2012-01-09T19:16:22 i can verify your solution in 3.6 seconds 2012-01-09T19:16:32 but still, that would take a long time to reach from 0 2012-01-09T19:17:21 yeah... especially since I overestimated and used 200k as the cap 2012-01-09T19:17:48 asloane: http://sprunge.us/SDZJ I just brute forced like that 2012-01-09T19:18:21 can't you just mod 1000000? 2012-01-09T19:18:42 yeah i mean, just add this to your n_partitions and get rid of gmp: 2012-01-09T19:18:42 combinations[n] %= 1000000; 2012-01-09T19:19:27 still really slow :P 2012-01-09T19:19:33 yes 2012-01-09T19:19:41 ./solution 18.27s user 0.00s system 99% cpu 18.272 total 2012-01-09T19:19:50 with 100k as the target 2012-01-09T19:19:53 arg, malloc had an interger overflow >:( 2012-01-09T19:20:20 1500*1500*4? :\ 2012-01-09T19:20:27 60000^2 2012-01-09T19:20:39 asloane: ./solution 3.82s user 0.00s system 99% cpu 3.826 total 2012-01-09T19:20:45 yeah, that's how long it takes to verify 2012-01-09T19:21:42 maybe some random gcc optimization switch will make it faster 2012-01-09T19:23:56 clang v3 optimizes it a lot better 2012-01-09T19:24:12 the gcc binary is 50% slower 2012-01-09T19:25:11 I'm still struggling to get the algo right. 2012-01-09T19:25:39 It's simple, but the limit cases make it a bit difficult 2012-01-09T19:26:04 i don't understand thestinger's algorithm but it seems to be correct 2012-01-09T19:26:26 i guess you're just enumerating them as shown in the description 2012-01-09T19:27:34 well, I did 76 first and then had to adapt it for 31 2012-01-09T19:27:48 there's a way to generate these with pentagonal numbers 2012-01-09T19:28:32 asloane: my way makes sense if you do it for low numbers 2012-01-09T19:29:04 asloane: no a1k0n anyome? 2012-01-09T19:29:29 w/e 2012-01-09T19:29:30 *** asloane is now known as a1k0n 2012-01-09T19:29:47 recursion in python blows up the stack really fast 2012-01-09T19:29:57 dude, the triangle number solution would definitely work 2012-01-09T19:30:15 er, pentagonal 2012-01-09T19:31:15 I think I could somehow make my code work for an arbitrary limit but I can't figure it out 2012-01-09T19:33:08 oh yeah, it looks like some people posted the pentagonal number solution in the forums 2012-01-09T19:35:36 https://en.wikipedia.org/wiki/Euler%27s_function 2012-01-09T19:41:18 *** deltree_ has joined #aichallenge 2012-01-09T19:43:26 thestinger, http://pastebin.com/zHeCrGSk is this the same as your cpp code? 2012-01-09T19:45:21 N is the number you're checking? 2012-01-09T19:45:27 yes, it's target 2012-01-09T19:45:38 yeah, that's basically the same I think 2012-01-09T19:45:41 but I'm just printing all the results 2012-01-09T19:45:47 and they are wrong :) 2012-01-09T19:47:38 oops, found it 2012-01-09T19:49:25 oh, yeah 2012-01-09T19:49:29 it's n-i, not n-1 2012-01-09T19:50:02 I still can't figure out how to give it an arbitrary limit 2012-01-09T19:50:27 I coded it like a year ago in python so I don't really understand what the hell I was doing 2012-01-09T19:50:59 well, I know how it works but not why anymore 2012-01-09T19:52:17 I think I understand how it works now 2012-01-09T19:52:33 you build the matrix like I do, but in such a way that you don't need to remember it 2012-01-09T19:52:36 I thought I did...but now some details are not fitting together. 2012-01-09T19:52:57 that's clever 2012-01-09T19:54:34 McLeopold: I think I was attempting to do 78 in python but never finished 2012-01-09T19:54:56 I don't think you can have an arbitrary target with that method 2012-01-09T19:55:17 if you wanted to calc target + 1, you would need a bunch of numbers that already where incremented 2012-01-09T19:55:26 yeah, that's the problem 2012-01-09T19:55:56 pentagonal numbers method is the answer 2012-01-09T19:56:00 but it's a bitch to implement 2012-01-09T19:56:22 *** GarfTop has quit IRC (Quit: Make a new plan, Stan!) 2012-01-09T19:56:28 McLeopold: I think the reason I ended up with this method is because it works for problems like 31 2012-01-09T19:56:43 so i would be an index over an array of coins or whatever 2012-01-09T19:56:53 I already solved 44, it was just too long ago 2012-01-09T19:58:09 oh, 79 is fun 2012-01-09T19:58:15 I did it on paper though 2012-01-09T19:59:49 problem 80 is basically a 1 liner in python and then 81 to 83 are easy graph search ones 2012-01-09T19:59:53 are you talking about project euler? 2012-01-09T19:59:55 so you'll get further ahead of me :) 2012-01-09T19:59:58 cyphase: yeah 2012-01-09T20:08:37 *** epicmonkey has quit IRC (Ping timeout: 248 seconds) 2012-01-09T20:11:03 holy crap 2012-01-09T20:11:04 woot! 2012-01-09T20:11:14 got the pentagonal method implemented... and it solves it in 0.147s 2012-01-09T20:11:18 wow, nice 2012-01-09T20:11:18 and i have a bug where i compute some of them twice 2012-01-09T20:11:36 now i don't feel ashamed submitting :) 2012-01-09T20:12:25 *** dapplegate has quit IRC (Quit: Ex-Chat) 2012-01-09T20:12:43 a1k0n: I felt bad because I couldn't figure out the trick for some of them and just used brute force 2012-01-09T20:13:32 for example for question 40 2012-01-09T20:13:56 ./solution 0.02s user 0.00s system 91% cpu 0.025 total 2012-01-09T20:13:59 "brute force" 2012-01-09T20:16:49 *** Apophis has quit IRC (Read error: Connection reset by peer) 2012-01-09T20:17:09 *** Apophis has joined #aichallenge 2012-01-09T20:44:34 After generating a longer list of "partitions_n" by brute force, I no longer see any consistent pattern. 2012-01-09T20:44:58 I guess I have to let my computer run for a week :) 2012-01-09T20:45:28 unless the number in question is very big 2012-01-09T20:45:56 less than 100k 2012-01-09T20:46:18 oh wonderful, that can be managed, im at 3200 already 2012-01-09T20:46:50 trying to speed up my python factorize and divisors functions atm 2012-01-09T20:46:52 then again I could have an off-by-one in the brute-force function somewhere... 2012-01-09T20:47:19 *** srgpqt has joined #aichallenge 2012-01-09T20:48:15 for primes I guess it is nice to have two functions. One that give a certain fixed number of primes and one that is a generator that spits out the next one on demand (in case you don't know how many you need in advance) 2012-01-09T20:48:38 you don't usually need very many primes though 2012-01-09T20:48:57 you can make a fast is_prime function using a prime sieve 2012-01-09T20:49:09 so you can use primes up to n to check if numbers up to n*n are prime 2012-01-09T20:50:38 right, in #32 only about a few of them were needed, when you took care of the limits 2012-01-09T20:50:55 80 or 360 i think 2012-01-09T20:51:15 if you like primes you should like this too: https://github.com/sigh/Python-Math/blob/master/primes.py 2012-01-09T20:51:20 ok, so I can get divisors for a big number in a way that's faster than the brute force trial division (up to sqrt(n)) 2012-01-09T20:53:02 is_prime(n, prime_list) would be my choice, so the function doesn't have to create its own list internally 2012-01-09T20:53:08 yeah 2012-01-09T20:53:14 my functions take an optional argument for that 2012-01-09T20:53:24 def factorize(n, candidates=None): 2012-01-09T20:54:20 are you guys golfing a problem? 2012-01-09T20:54:39 or racing languages? 2012-01-09T20:55:14 jmcarthur: project euler 2012-01-09T20:55:15 oh it sounds like euler now 2012-01-09T20:55:18 bah 2012-01-09T20:59:20 well, the way I get divisors is really stupid lol 2012-01-09T20:59:22 need to fix that 2012-01-09T21:00:19 cpu load applet still painted blue? ah yes ... ok 2012-01-09T21:01:56 alias memoize!partitions_n partitions_n_memo; // <- when you lack the brains use memoize 2012-01-09T21:02:24 it makes recursive functions way faster 2012-01-09T21:02:53 oh, you used a recursive function 2012-01-09T21:02:56 mleise: computation time goes as O(n^2) for those 2012-01-09T21:03:35 mleise: are you actually checking the n_partitions for each n? 2012-01-09T21:03:38 you'll never finish :P 2012-01-09T21:04:06 i apparently already solved 31 but don't have the code for it 2012-01-09T21:04:08 uh... what else would i do? I try every possible way to partition each and every n 2012-01-09T21:04:39 I just count the number of possibilities (which you can do recursively) 2012-01-09T21:04:55 but a year ago I was trying to make it fast in python, and recursion wasn't an option 2012-01-09T21:05:04 so I ended up with a pretty damn good way of doing it with 2 for loops 2012-01-09T21:05:24 anyway, that was still not fast enough for 78 2012-01-09T21:05:26 I have that loop construct in the solution to 78 2012-01-09T21:05:58 had to add a check with each iteration of the outer loop so I could just run it once (up to some arbitrary limit) 2012-01-09T21:06:07 uh 23 i meant 2012-01-09T21:06:45 but the solution to 78 is really below 10,000 ? 2012-01-09T21:06:54 below 100,000 2012-01-09T21:06:57 not 10k 2012-01-09T21:07:04 omg 2012-01-09T21:07:09 I'll never finish 2012-01-09T21:07:51 use the pentagonal solution 2012-01-09T21:08:03 a(n) - a(n-1) - a(n-2) + a(n-5) + a(n-7) - a(n-12) - a(n-15) + ... = 0, where the sum is over n-k and k is a generalized pentagonal number (A001318) <= n and the sign of the k-th term is (-1)^([(k+1)/2]). 2012-01-09T21:08:07 the what? where did you read about that? 2012-01-09T21:08:15 oeis.org 2012-01-09T21:08:25 can't do projecteuler without OEIS 2012-01-09T21:08:47 I've managed so far, but I haven't gotten very far yet :P 2012-01-09T21:09:02 with that method it takes 0.14s to solve searching frtom 0 2012-01-09T21:09:22 I should just do what McLeopold suggested and make a massive file with all the primes 2012-01-09T21:09:53 I guess seeking to lines is pretty fast so I could use line numbers as the index 2012-01-09T21:10:00 McLeopold is a cheater 2012-01-09T21:10:29 thestinger: do you need primes > 64-bit? 2012-01-09T21:10:35 and I'll put the file in /tmp, which is a ramdisk :) 2012-01-09T21:10:43 mleise: not sure 2012-01-09T21:11:11 if the answer is no you should use a binary format that you can index even faster than a text file with lines 2012-01-09T21:12:30 I did a lot of questions with python, so I'm not sure if I ended up relying on bigints 2012-01-09T21:14:07 anyway I'm doing them all with C++ now because it's easier than trying to get python fast enough 2012-01-09T21:14:54 a1k0n: Solving these problems by always looking up the algorithms somewhere is boring :p 2012-01-09T21:15:05 with pypy it's only around 5x-8x slower than C for these questions if you write them well 2012-01-09T21:15:12 but that 5x to 8x can be a _lot_ of wasted time 2012-01-09T21:15:43 so there are questions that have no fast solution? 2012-01-09T21:16:11 I'm sure you _can_ do them all with python 2012-01-09T21:16:54 but I would have to do research to find a good mathematical solution, which ruins the fun 2012-01-09T21:17:12 optimizing python is pretty counterintuitive 2012-01-09T21:17:24 less so with pypy 2012-01-09T21:24:25 *** dorisabayon has joined #aichallenge 2012-01-09T21:25:03 mleise: yeah, i guess, but it's more like looking up some bizarre number theory facts and stringing them together to form an efficient solution to the particular problem 2012-01-09T21:26:55 *** Fandekasp has quit IRC (Ping timeout: 240 seconds) 2012-01-09T21:27:05 bizarre is a good word. i start to think of euler as a hardcore nerd 2012-01-09T21:27:57 i bought a book about generating functions once as a result of projecteuler 2012-01-09T21:28:02 but then again number of partitions is something that I can imagine to be actually useful 2012-01-09T21:28:44 i never solved p41 but i can already tell it has 7 digits 2012-01-09T21:29:13 hehe 2012-01-09T21:29:18 but i pretty much doubt pandigital numbers are useful anywhere 2012-01-09T21:29:59 ok, I'll have to get this generator function right now 2012-01-09T21:31:29 a1k0n: 41 is one of the questions I basically just brute forced 2012-01-09T21:32:16 less than a second in python so it's not really that bad 2012-01-09T21:34:53 I guess I'm missing something on n=7. p(7)=15 but I can only find 14 cases: 7 ; 6/1 ; 5/2 ; 5/1/1 ; 4/3 ; 4/2/1 ; 4/1/1/1 ; 3/3/1 ; 3/2/1/1 ; 3/1/1/1/1 ; 2/2/2/1 ; 2/2/1/1/1 ; 2/1/1/1/1/1 ; 1/1/1/1/1/1/1 2012-01-09T21:48:54 3/2/2 2012-01-09T21:50:43 ah...interesting 2012-01-09T22:00:43 *** Chris_0076 has quit IRC (Quit: Leaving) 2012-01-09T22:10:00 contestbot: seen janzert 2012-01-09T22:10:00 amstan: janzert was last seen in #aichallenge 22 hours, 42 minutes, and 40 seconds ago: it is displayed for games where the player ended with 'crashed', 'timeout' or 'invalid' 2012-01-09T22:10:34 janzert: i got an email about forum activations, i have a feeling email on the archive server isn't working 2012-01-09T22:10:47 see staff 2012-01-09T22:41:34 *** dvladim has joined #aichallenge 2012-01-09T23:07:11 thestinger: #78 is blazing fast without BigInts. I wouldn't have removed them though if I wasn't hinted to the fact that there is only addition and subtraction, that is more or less uninfluenced by the modulo operator 2012-01-09T23:13:59 *** dvladim has quit IRC (Read error: Operation timed out) 2012-01-09T23:23:30 mleise: yeah, it's 2.4s now without gmp and over a minute when using it 2012-01-09T23:23:41 and gmp is fast 2012-01-09T23:23:58 oh... you are slow, someone claimed to do 70ms in Java 2012-01-09T23:24:13 well, not using the smart pentagonal number method 2012-01-09T23:25:06 I end up calculating p(n) for each n until it's the answer 2012-01-09T23:25:45 that's what I do as well. 2012-01-09T23:26:02 but I use the pentagonal numbers to calculate p(n) of course 2012-01-09T23:26:07 ah 2012-01-09T23:28:27 I don't know any other methods to be honest, that don't take ages 2012-01-09T23:29:39 49ms and not optimized to total obfuscation: http://codepad.org/lx74QNcJ 2012-01-09T23:30:48 I'm also starting to share code between the problems and make it so I can build an executable with all solved problems included 2012-01-09T23:36:14 *** lhb__ has joined #aichallenge 2012-01-09T23:40:14 *** raemde_ has quit IRC (Ping timeout: 252 seconds) 2012-01-09T23:56:34 *** u_ has quit IRC (Quit: u_)