[kw-pm] Last night's meeting

Daniel R. Allen daniel at coder.com
Thu Jun 18 09:52:06 PDT 2009


$ cat alpha.html |perl -n -e'$s=$_ if(rand()<1/++$n);END{print $s}'

Which, obviously, has an improvement, I don't know why I left that extra
whitespace in there. For 35:

$ cat alpha.html |perl -n -e'$s=$_ if(rand()<1/++$n);END{print$s}'


Thanks Abram for the excellent challenge.  There are nine other challenges
on GolfChallenge in case we feel like doing this again.

-Daniel

On Thu, 18 Jun 2009, Abram Hindle wrote:

> On the topic of twitter I discussed tircd a tiny bit:
>
> http://github.com/abramhindle/tircd-plus-search/tree/master
> http://code.google.com/p/tircd/
>
> We did a golf challenge from:
> http://kw.pm.org/wiki/index.cgi?GolfChallenge
>
>     * Choose 1 uniformly randomly
>
> Write a perl script to select 1 element from a stream of unknown length
> uniformly randomly. The algorithm usually is read an element in, choose
> a number between 0 and 1, if it is less than 1/n then keep that new
> element, otherwise keep your old one. So first element is 1/1 to keep,
> second element is 1/2 to keep, third element is 1/3 to keep. Via
> induction you can work it out that this algorithm is uniformly random.
>
> ^^ I "proved" this on the board via hand waving.
>
>
> Here's my awk/bash version (bash seeds awk because gawk is bad at
> seeding itself)
> #!/bin/bash
> awk "BEGIN {srand($RANDOM + $RANDOM)} {c = (rand() < (1.0 / FNR))?\$0:c}
> END { print c }" $*
>
> Daniel wrote a tiny perl version (37 chars?) and max wrote a relatively
> small (87 chars?) python version.
>
> If Daniel or Max could share their code with the list that'd be great.
>
> abram
>
>



More information about the kw-pm mailing list