GolfChallenge


Golf Challenge


17 June 2009-

Problem definition:

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.

^^ Abram went through the induction on the board, with minimal hand-waving...

awk/bash:

Here's Abram's 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 }" $*

Perl:

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

Python:

And Max's python version, for 87 chars.

import random as r
n,s=0,''
for l in open('x'):
 n+=1
 if r.random()<1.0/n:s=l
print s

Further Discussion is found at: http://mail.pm.org/pipermail/kw-pm/2009-June/001209.html

Thread: [kw-pm] Last Wednesday's meeting


Abram's suggestions (good for future challenges):

  • Knight's Cover also called Knight's Tour

Given a board of dimensions N x M can you move a knight around the board in such a way to cover all squares at least once? Assume the knight starts at 0x0. Simple version: print yes or no if it can cover those squares. Better version: print the list of moves it can take to cover all of those spaces at least once.

e.g.

> perl knights.pl 4 4
0 0
1 2
0 0
2 1

If you need help check out: http://www.ktn.freeuk.com/index.htm

  • Knight's Cover validator

Take a list of moves (string of integer pairs seperated by a space, 1 pair per line e.g. "1 1\n2 2") and validate that each move follows the rules that a knight has to follow AND that the set of moves covers all spaces.

  • Farmer, Fox, Hen, Lettuce

Make a program which solves and describes the Farmer, Fox, Hen and Lettuce problem. The farmer has to move a fox, hen and lettuce across a river with a boat, the boat can accommodate one farmer and one item. If the Hen is left alone on one side of the river with the fox, the fox will eat the hen. If the hen is left alone with the lettuce, it will eat the lettuce, the fox is disinterested in all things lettuce. The boat can take multiple trips across the river and can accommodate 1 item in the boat per trip.

Your perl program is supposed to print tuples of items taken across each way qw(NONE Farmer Fox Hen Lettuce). The first element is the item taken across, and the second item is the item returned back to the original shore.

e.g.

Fox NONE
Hen NONE

  • 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.

  • Prime Finder

Find all the primes of an input number.

  • Markov Model

Given a string, break it into tokens seperated by whitespace and make a transition model (a Markov model) of word to word transitions and the count of the number of times this occured.

e.g.

input: max and abram bought a cat. abram and max bought a car.
output:
max -> and 1
and -> abram 1
abram -> bought 1
bought -> a 1
a -> cat 1
cat -> abram 1
abram -> and 1
and -> max 1 
max -> bought 1
bought -> a 1
a -> car 1

  • Word Box

Given a word, produce a matrix of the word which matches this output: e.g.

word
oord
rrrd
dddd

  • Shuffle

Without using List::Util make an array shuffler.

  • Text Box

Take an input string, a number, and hard-word-wrap the string to fit in a box of that width.

e.g. input of 3 string of 1234567890

123
456
789
0

  • ASCII Art Join

Given 2 filenames, pad the first file with whitespace so each line is equal width and then concat the lines of the second file e.g. input of cat.txt and dog.txt

cat.txt

 ^_^   (\   
(';')--_)>  
 \      /   
  ii""ii    
  ^^  ^^    

dog.txt

  .--_      
 _ooi |     
('_,(_)     
  )=(__     
(_(__(__|); 

output:

 ^_^   (\     .--_      
(';')--_)>   _ooi |     
 \      /   ('_,(_)     
  ii""ii      )=(__     
  ^^  ^^    (_(__(__|);