<mark_weaver>well, I suppose if you're not confident in your solution approach for B, maybe you should do A instead. dunno. <mark_weaver>it's possible that both of you will do *head-desk* when you see my solution to B. <cky>mark_weaver: I am confident of my solution approach to B. <cky>And it is really simple. <cky>But maybe yours is even simpler. <cky>I want to use math/array in Racket because it has some nice sequences for working with arrays, but unfortunately Debian does not have a Racket 5.3.2 package (and math/array did not exist in 5.3.1). <cky>Well, I suppose I must do without. The code will be slightly uglier, but so be it. <cky>Or maybe I should just graft the module from Racket git into my current Racket installation. <mark_weaver>if your solution is simple, and you confident it is correct, that sounds like you're on the right track. <cky>I will just use vectors of vectors, rather than arrays, it seems. <cky>Or maybe I'll just use srfi-25 arrays. <cky>All right! Let's test my solution for B. <cky>mark_weaver: I have B-small correct. <cky>That sounds a lot like my solution will generalise for B-large. <cky>Submitted. Now for problem A. <cky>mark_weaver: The solution approach for B is indeed simple, but it's such a pain to write in Scheme. I can probably write a much shorter version in Ruby. <ijp>well, only an hour left ***ijp` is now known as ijp
<cky>mark_weaver: Makes sense (I wonder if Racket has srfi-42). <cky>Oh well, I've submitted already. ;-) <cky>I have done A as well. Though only in Scheme. <cky>Can't be bothered to do it it assembly now. <mark_weaver>wow, I'm glad I submitted my solutions when I did. it made a big difference in my ranking. <mark_weaver>I could have submitted my C solutions much earlier, but I was waiting until I knew how to solve C part 3, and then spent a bunch of time thinking about D before going back to C. <mark_weaver>I didn't realize there would be such a big spread among those who solved all of A through C. <ijp>well, we'll know the final scores in half an hour or so, but it looks like I went down from last year <ijp>I'm surprised so few people did them all <cky>In the real rounds, the ranking counts for a lot (since they top-skim to decide whom to pass through to the next round), and it definitely favours the quick thinkers. *cky is at rank #759 (and mark_weaver is at #445). Good job, all. :-) <cky>mark_weaver: You and I both got C-large correct. <cky>(Well, we both got all the large submissions correct.) <ijp>okay, so I did at least get all the ones I submitted right <ijp>congrats cky mark_weaver <ijp>so, tell me. How do you do C so fast? <ijp>I was only able to get down to 30 seconds for the middle one <mark_weaver>you have to compute the list of fair-and-square numbers only once, and then select from that list for each test case. <mark_weaver>that was the key to getting C part 2 running fast enough. <ijp>Actually, my solution didn't do that, but it would have been a simple matter to fix that <mark_weaver>I think I will describe C part 3 in private, in case someone here doesn't want it spoiled. <ijp>I did originally when I had tried to do it with streams <ijp>which gave a beautiful implemenation, but it was not performant <cky>mark_weaver: Just describe in it #gcj2 so we can all hear about it. :-) <cky>ijp: You should join #gcj2 too. :-) <ijp>B was just a comparison against the row and column maximums, right? <cky>ijp: I'll answer that in #gcj2 too. <mark_weaver>cky: nice code for B. it looks a lot like mine, but I used SRFI-42, which results in similar code but is more portable. <cky>Thanks, and that makes sense. :-) <cky>Sure, but I do miss solving A in assembly. ;-) *cky goes and downloads mark_weaver's solutions now. <cky>mark_weaver: I can safely assume you're using the same solutions for small and large, right? <mark_weaver>cky: for all but problem C. I used very different code for C part 3. <mark_weaver>it's the first time I've used different code for the large solutions. in the past I've always just gone right to the large problem. <cky>Some of us play this game where, for the qualification round (since we have 25 hours), we use a different language for each solution. <cky>So for this year, you can use up to 9 languages. <cky>Obviously, I haven't really participated in that. <ijp>are there language stats? <mark_weaver>go-hero.net highlights competitors who used the most languages. <mark_weaver>It's an interesting idea, but right now I'd rather promote Scheme, and Guile in particular. <ijp>ah, I vaguely remembered there was a site from last year, but I couldn't remember it <taylanub>Huh .. is Scheme a thing in Japan or what ? :P <mark_weaver>ijp: you have to use 'exact-integer-sqrt' for large numbers. <ijp>mark_weaver: I couldn't remember if it was rnrs only <ijp>right, but it was just a question of if it was worth it for one use <ijp>anyway, I don't even remember which version I uploaded for C <ijp>I went through at least 4 variants <mark_weaver>ijp: you could make the code a lot faster by iterating only on half the digits of the root. *ijp downloads his own solution <ijp>yeah, that was just the quick 'n' easy one for the small version <mark_weaver>e.g. for the small input, that means only iterating over only about 10^(7/2) numbers instead of 10^7 <ijp>it isn't really algorithmically better, but it was quite a bit faster <ijp>as you can see, I didn't precompute. Which meant I did that ugly, save and restart code. <ijp>quite silly in hindsight <ijp>I'm pretty sure it is buggy as well <mark_weaver>seems like a reasonable effort. it was a hard problem; the first code jam problem where I abandoned my usual policy of "just concentrate on solving the largest input" <mark_weaver>I also abandoned my usual policy of "don't submit a solution unless I'm confident it will work and be fast enough". <ijp>mark_weaver: did you carry on to next rounds last year? <ijp>or did you just do the qualifiers <ijp>ah, I see you got to round 2 <mark_weaver>yeah. I have trouble working under such time pressure. 1B is the only one I did well at after the qualifier. <ijp>yeah, I know the feeling <mark_weaver>Being able to do well at a contest like this requires a totally different set of talents than what it takes to write good maintainable code, IMO. <ijp>mark_weaver: out of interest, do you know of any better way of testing that a number is a palindrome, other than to convert it to a string first? <ijp>right, I guessed as much <mark_weaver>the alternative is to do what 'number->string' does anyway. but built-in number->string is probably faster than whatever you'd do. <ijp>well, you could take the source for number->string and strip out all the parts not related to integers, but sure <ijp>I doubt it would save you much though <mark_weaver>for bignums, it uses a routine in libgmp. good luck beating that. <mark_weaver>and for fixnums there's a little C routine to do the conversion. <mark_weaver>see 'scm_number_to_string' and 'scm_iuint2str' in numbers.c. <cky>ijp: Did you see my solution? <cky>ijp: I did use a non-string approach for testing for palindrome. <cky>But from what mark_weaver said, probably the sting approach is faster. <cky>But, Racket may or may not use libgmp, so who knows. <ijp>yeah, I'm looking at it right now <ijp>well, it isn't too surprising <ijp>it has more entrants, and more time for people to mess around :) <mark_weaver>I find it rather disturbing how many people used PHP. <ijp><ijp> ,php <fsbot> [4] a geometric wonder: all corners, no sides, <cky>mark_weaver: Most of the final round contestants used C++, I noticed. <cky>That's pretty hardcore in iself. <ijp>I like that someone did a solution in Coq <mark_weaver>almost half of the top 20% ranked contestants in the qualification round used C++ too. <mark_weaver>I find that kind of disturbing also, but I guess it's not nearly as bad as PHP. <ijp>PHP is the drunken early-20s tattoo of the programming world <ijp>which is facebook using haskell to change their PHP <ijp>they do some strange things over there <ijp>'hiphop' was weird enough <mark_weaver>ijp: I'm sorry, I missed your reply to my suggestion to use 'exact-integer-sqrt' before. You wrote: <ijp> right, but it was just a question of if it was worth it for one use <mark_weaver>what do you mean "worth it"? 'sqrt' will in general give an answer that is very far from the correct answer, when used on large numbers. this can affect the correctness of your code. <mark_weaver>in particular, 'fair-and-square?' will return false when it should return true. <mark_weaver>well, actually, I guess you would have been saved by the fact that 'sqrt' now returns an exact result when the input is an exact perfect square. <mark_weaver>and the fact that if the answer is imprecise, the low digit will be 0 and thus the root won't be a palindrome. <mark_weaver>no, I take that back.... the low binary digit will be 0, but not necessarily the low decimal digit.. <mark_weaver>more generally, whenever you find yourself using 'inexact->exact', it's probably a bug :) <ijp>mark_weaver: well, in the end I ended up removing the call to sqrt anyway <ijp>squaring is in general cheaper that sqrting <mark_weaver>I used it only to discover the highest root I'd have to look for. <mark_weaver>(I took the 'exact-integer-sqrt' of the largest B value found in the input) <mark_weaver>but I guess you could also simply iterate until the sqrt of your root is larger than the largest B. <cky>.oO(I wonder if exact-integer-sqrt is identical to Racket's integer-sqrt/remainder. 'cuz that's what I used in the first iteration of my solution, though it was no longer used in the final version.) <cky>Hehehe, it actually is. <cky>collects/rnrs/base-6.rkt contains this export: (rename-out [integer-sqrt/remainder exact-integer-sqrt]) <mark_weaver>except that 'exact-integer-sqrt' is in both the R6RS and the R7RS draft, whereas integer-sqrt/remainder is presumably racket specific. <mark_weaver>I really ought to start writing portable R6RS code whenever feasible. <mark_weaver>I realize that it bugs me when people use racket-specific bindings unnecessarily, and yet I also realize that it's hypocritical of me to be annoyed at that, since I do the same with Guile-specific bindings. <cky>mark_weaver: True (re Racket-specific). <cky>mark_weaver: Yeah, I think at the moment, implementation-specific code is an unfortunate reality. <cky>I think part of the answer to portability is to have SRFIs cover more things that people currently use non-portable code for. <cky>I wrote in a Stack Overflow post a while ago, that even something as simple as making a circular list, cannot be done portably without SRFI 1. <cky>It is for that reason that, with Phil Bewig's avoidance of most any external dependencies, including other SRFIs, that the reference implementation of stream-constant uses an O(n)-per-iteration implementation approach, whereas with use of SRFI 1, a more direct implementation using circular-list is possible. <ijp>well, even that isn't enough. You need portable srfi implementations, and portable ways of using external libraries. <cky>ijp: Yes, true, different implementatations have different import syntaxes. :-( <ijp>and even when you have them, people still use implementation specific extensions <mark_weaver>I agree that SRFIs are a very important part of the answer. I've found that 'require-extension' works on some implementations at least. <mark_weaver>cky: I think you can make circular lists portably by mutating a cdr, no? <cky>mark_weaver: Racket doesn't have mutable conses. <mark_weaver>well, you can do it in R5RS, or for that matter R4RS or R3RS. <cky>(Racket's implementation of circular-list uses make-reader-graph, which is a Racket-specific thing for making cyclic structures out of immutable conses.) <mark_weaver>racket is really an outlier on the mutable cons thing... (though I happen to think it was a good thing) <mark_weaver>I forget, does Racket have a separate mutable pair type? (with distinct accessors?) <cky>And indeed, there's mcar, mcdr, set-mcar!, and set-mcdr!. <mark_weaver>well, "great" might be a bit much. of course it's painful in some ways, but necessary to reap the advantages they were aiming for. <mark_weaver>but I'm glad that there's still a simple mutable pair type for those who still prefer to create data structures in the old tradition, using pairs. <cky>Yes, choices can be a good thing. <cky>Of course, there's also mlist, made of mcons cells, thus distinct from lists (except that both use the same empty list object). <cky>The usual recommendation is to use the neil/sicp module. <cky>which overrides a bunch of stuff, IIRC. <cky>s/module/language/ (#lang planet neil/sicp) <mark_weaver>right, I'm just wondering how they cope with the fact that SICP assumes mutable conses, and that those conses can be used by all the usual procedures that manipulate lists. <cky>Browsing through the PLaneT catalogue, one package caught my eye: dvantorn/tetris <cky>*dvanhorn/tetris, even <ijp>Mike Gran (I think) wrote a tetris.scm for the one year anniversary <ijp>this define-peg-string-patterns is very unsettling to me <ijp>if you have a bad string pattern, you don't get an error, and you will have unbound identifiers in your module <ijp>I haven't looked into the implementation, but I assume it does something like (module-define! (current-module) (pattern-name) (compile-matcher (pattern-body))) *tupi` should borrow Mike's code and rewrite tetris using guile-clutter <tupi````>if i do: cp -a /home/houston texas manually in a terminal as root, it works fine. but if i ru a bash script which contains cp -a $RUDIR $UNAME [which echos correctly as cp -a /home/houston texas] bash creates a texas directory and then copy houston inside hy is that ? <mark_weaver>tupi````: "cp -a houston texas" will put houston inside texas if texas/ already exists. My guess is that's what happening. <tupi````>mark_weaver: just understood my mistake! i was creating the user with useradd [in the script and not when trying manually] then of course texas exists and ... <fbs>civodul: you wrote guile-tls right? <civodul>(i did not downgrade it to LGPLv2.1, BTW, but that may have happened in spite of me) <fbs>civodul: nope, no bugs. I wanted to add ssl support to my irc lib thingy. add^ submitted a patch but i think its anonymous stuff <fbs>I was reading the gnutls & gnutls guile docs but couldnt really figure out how to improve it <fbs>I think I need some x509 stuff, <civodul>the idea of 'tls-wrap' here is that you pass it a socket, and it returns a TLS record port <civodul>there are example of OpenPGP and X.509 credentials in the test suite <fbs>this looks like the anon auth in the manual <fbs>Yea I took a look at that and copied some code from it but couldnt get it to work :p <fbs>Guess I need to read the whole tls doc once <civodul>you'll have to provide more details then :-) <civodul>often, if you don't use the right priority string, nothing happens <civodul>because you lack the correct ciphersuite <civodul>so you need to enable GnuTLS debugging output to see what happens <fbs>the test code uses a cert/key file for the client I thought it should be possible to do it without <civodul>(set-log-level! and set-log-procedure!) <civodul>ah yes, you don't need to do mutual auth <fbs>hmm debugging, i was messing iwth my code and socat openssl-listen a bit and had some cipher mismatches <civodul>usually (as in HTTPS), it's just the client that authenticates the server, not the opposite <fbs>before that I had some cert errors <fbs>i _hate_ network stuff :p