[kw-pm] Last Wednesday's meeting

[Max]

The reasonably minimalistic python version (87 bytes), with input in a 
file named 'x':
import random as r
n,s=0,''
for l in open('x'):
 n+=1
 if r.random()<1.0/n:s=l
print s



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
>
>   
> ------------------------------------------------------------------------
>
> _______________________________________________
> kw-pm mailing list
> kw-pm at pm.org
> http://mail.pm.org/mailman/listinfo/kw-pm