[kw-pm] Last night's meeting

abez abez at abez.ca
Fri Jun 19 09:37:34 PDT 2009


On Fri, 19 Jun 2009, John Macdonald wrote:

>>
>>
>> So, that's down to 18 chars, with no supporting cheats of any kind.
>
> However, I haven't seen the original challenge - does it require
> that the program handle input that is too large to fit in memory?

The purpose of the original challenge was for members to implement the
randomized algorithm, that I presented, which allows for O(1) memory use, in
terms of lines while ensuring the result was uniformly random (with some
assumptions of course).

This algorithm needs O(N) calls to rand but rand is pretty fast compared to
I/O, thus this algorithm will work very well on huge inputs.

Perhaps the golf should've been written more clearly but it was given a full
presentation in the meeting :)

abram


More information about the kw-pm mailing list