Golf: 3 hole golf game

While browsing through the internet I found this and thought it would perfectly fit here for a rainy day or a good challenge:
The object of the Challenge is to solve a few programming tasks using the shortest programs you can think off

All programs must work on current perl (most likely programs you write on another version will be just fine, so don't directly go downloading a different perl)

All programs are filters. They must read input from STDIN, and send output to STDOUT. All input lines are properly newline terminated, and do not contain binary 0. All input files have a total size so that they will fit comfortably in memory and still allow you ample memory to play with.

All output lines must likewise be properly newline terminated. Nothing must appear on STDERR. The average runtime of the program must be finite, but may be arbitrarily long.

You must assume total memory is < 2**32 bytes (this e.g. implies sizes of arbitrary datastructures can be represented in a plain integer, and that you must not try to generate arbitrarily big datastructures).

The program must be written as one or more lines. The score for each hole is the total number of characters you need (smaller is better). If your program is more than one line, you must count the newlines inbetween as one character each. The #! line is not counted. If you use options on the #! line, the options themselves are counted, including the leading space and -

The program may only use the perl executable, no other executables on the system are allowed (in particular, you must not use the programs implementing the other holes. The program may use itself though). You may use any of the current perl standard core modules. Your solution must be portable in the sense that it should work on all versions of current perl everywhere. You may assume ASCII as character set and must not use any of the unicode specific semantics

Current holes:

1.
"Human Sort"
Sort a set of lines, but with a twist.
When sorting a set of lines, humans like to see the numeric parts of a line sorted numerically and the alphabetical parts case insensitive. For the numeric parts you may ignore the possibility of negative numbers, floating point numbers and leading zeros, the numbers however are almost unconstrained in length. In other words, a sequence of one or more digits plays the same sort of role as some kind of single character, and such a sequence sorts before all normal letters, but among themselves they are ordered by numerical value. Example:

1 < A < amstelveen < Amsterdam < Amsterdam5 < Amsterdam40 < Amsterdamned

You are free in how you order e.g. fOo versus FoO or a digit versus space.

Notes:

* watch out, the original version of this question did not request case insensitivity.

* watch out, the original version of this question allowed leading zeros in the number parts, but that made programs substantially more complicated and less fun. While this change won't invalidate any existing solution, maybe you can do better now....

* The strings can also be things like: 57amstel25venn865314457646576532325988watte
* Remember, if your program is going to generate (temporary) strings of size > 2**32, your program will be rejected. So avoid things like

"a865314457646576532325988watte" =~ /(\d+)/; 0 x $1;

2.
"Fair Shuffle"
Outputs some random permutation of the input lines. Each permutation must be equally likely over many runs.

3.
"Select Two"

print 2 lines each randomly chosen from the input, however the two must not come from the same line in the input. You may assume the input is 2 lines or more. each pair of outputlines must be equally likely, and their order itself also random

Some more hints about randomness:

* using non-consistent sort-functions will not be accepted. The results are not random on almost any sort implementation and can even coredump some implementations.

* You must not ignore the fact that two calls to rand can in principle return the exact same number twice.

* You may assume each value returned by rand is equally likely.

Here is a program to pre-screen your entries. (given at the challenge)

Please post scores of each hole and the total

Happy golfing

I have some results but i don't want to post them yet, if someone feels he/she really wants to see them I can give them to him/her. If I would post them, it would only spoil the fun.

Comment on Golf: 3 hole golf game

Replies are listed 'Best First'.

Re: Golf: 3 hole golf game
by Zaxo (Archbishop) on Nov 16, 2004 at 10:09 UTC

36 and 46 strokes for #2 and #3. No solution presented for #1.

Read more... (647 Bytes)

After Compline,
Zaxo

[reply]
[d/l]
[select]

Re: Golf: 3 hole golf game
by dragonchild (Archbishop) on Nov 16, 2004 at 15:45 UTC

human.pl:    204 strokes
shuffle.pl:   51 strokes
select.pl:    55 strokes
------------------------
total:       310 strokes
[download]

human.pl:
print map{$$_[0]}sort{$$b[1]!~/\D/<=>$$a[1]!~/\D/||(grep$_,map{$_>@$b?
+1:($@=($$a
[$_]!~/\D/&&length$$a[$_]<=>length$$b[$_])||$$a[$_]cmp$$b[$_])?$@:0}1.
+.@$a)[0]}s
ort{@$b<=>@$a}map{[$_,split/(\d+|\n)/,lc]}<>

shuffle.pl:
print map{$n=rand@x;@x[$n,-1]=@x[-1,$n];pop@x}@x=<>

select.pl:
@x=<>;print map{$n=rand@x;@x[$n,-1]=@x[-1,$n];pop@x}0,1
[download]

Update:

human.pl:    189 strokes
shuffle.pl:   33 strokes
select.pl:    37 strokes
------------------------
total:       259 strokes
[download]

human.pl: print map{$$_[0]}sort{$$b[1]!~/\D/<=>$$a[1]!~/\D/||(grep$_,map{$,=$$a[ +$_];$_>@$b ||($,!~/\D/&&length$,<=>length$$b[$_])||$,cmp$$b[$_]}1..@$a)[0]}sort{@ +$b<=>@$a} map{[$_,split/(\d+|\n)/,lc]}<> This passes, but doesn't look right. It does cut 15 strokes, though: print map{$$_[0]}sort{$$b[1]!~/\D/<=>$$a[1]!~/\D/||(grep$_,map{$,=$$a[ +$_];$_>@$b ||($,!~/\D/&&length$,<=>length$$b[$_])||$,cmp$$b[$_]}1..@$a)[0]}map{[$ +_,split/(\ d+|\n)/,lc]}<> shuffle.pl: print map{splice@x,rand@x,1}@x=<> select.pl: @x=<>;print map{splice@x,rand@x,1}0,1
[download]

Update2:
human.pl: 185 strokes
[download]

human.pl: print map$$_[0],sort{$$b[1]!~/\D/<=>$$a[1]!~/\D/||(grep$_,map$_>@$b||( +($*=$$a[$_ ])!~/\D/&&length$*<=>length$$b[$_])||$*cmp$$b[$_],1..@$a)[0]}sort{@$b< +=>@$a}map[ $_,split/(\d+|\n)/,lc],<>
[download]

Update3:
human.pl: 159 strokes
[download]

human.pl: print map$$_[0],sort{(grep$_,map$_>@$b||((!grep/\D/,$*=$$a[$_],$_=$$b[ +$_])&&leng th$*<=>length)||$*cmp$_,1..@$a)[0]}sort{@$b<=>@$a}map[$_,split/(\d+|\n +)/,lc],<>
[download]

Update3:
human.pl: 137 strokes
[download]

human.pl: print map$$_[0],sort{(grep$_,map{((!grep/\D/,$*=$$a[$_],$_=$$b[$_])&&l +ength$*<=> length)||$*cmp$_}1..@$a)[0]}map[$_,split/(\d+|\n)/,lc],<>
[download]

Being right, does not endow the right to be rude; politeness costs nothing.
Being unknowing, is not the same as being stupid.
Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

[reply]
[d/l]
[select]

Re: Golf: 3 hole golf game
by tilly (Archbishop) on Nov 17, 2004 at 03:05 UTC

rand

Here is my score:

human.pl:     87 strokes
shuffle.pl:   47 strokes
select.pl:    52 strokes
------------------------
total:       186 strokes
[download]

Read more... (318 Bytes)

Being right, does not endow the right to be rude; politeness costs nothing.
Being unknowing, is not the same as being stupid.
Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

[reply]
[d/l]

Re^2: Golf: 3 hole golf game

by eric256 (Parson) on Nov 24, 2004 at 16:26 UTC

"The implementation of rand guarantees that the same value cannot be returned twice in a very large number of calls"

Wouldn't that be considered a bug in perl? I mean if it guarantees not to return the same number, then that number is no longer equaly likely to be picked. I had assumed that everytime rand was called every possible outcome is equaly likely. Of course I might just be a crazy lunatic.

___________
Eric Hodges

[reply]

Re^3: Golf: 3 hole golf game

by tilly (Archbishop) on Nov 27, 2004 at 08:26 UTC

rand

pseudo

rand

If you want to produce really random numbers, then you need a source of random data to sample. Which can be done, but has its own problems (the call to fetch a random number may take a while if there is no random data in the pool right now). For normal purposes, pseudorandom is fast, easy, and good enough. Plus for some purposes it is very nice to be able to call srand and get a predictable set of numbers out.

But if you really want something more random then see Math::TrulyRandom.

[reply]

Re: Golf: 3 hole golf game
by etcshadow (Priest) on Nov 17, 2004 at 06:31 UTC

human.pl:    103 strokes
shuffle.pl:   37 strokes
select.pl:    37 strokes
------------------------
total:       177 strokes
[download]

Tilly

human.pl :::::::::::::: @x=<>;$z=length"@x";%x=map{($x=lc)=~s/\d+/0 x($z-length$&).$&/ge;$_,$x}@x;print sort{$x{$a}cmp$x{$b}}@x :::::::::::::: select.pl :::::::::::::: @_=<>;print splice@_,rand@_,1for 1..2 :::::::::::::: shuffle.pl :::::::::::::: print splice@_,rand@_,1for 1..(@_=<>)
[download]

Frankly, I feel that this should count as a solution to #1, but it doesn't, because perl's native arithmetic comparison is just broken on ludicrously long numbers:

:::::::::::::: human_shoulda.pl :::::::::::::: print map{@$_}sort{$z=0;{$z>@$a?0:lc$$a[$z]cmp lc$$b[$z++]||$$a[$z]<=> +$$b[$z++]||redo}}map{[split/([\d\n]+)/]}<>
[download]

Oh, well. It's still longer than my cleaned-up version of Tilly's, so I guess it's no real loss.

------------
:Wq
Not an editor command: Wq
[download]

[reply]
[d/l]
[select]

Re^2: Golf: 3 hole golf game

by tilly (Archbishop) on Nov 17, 2004 at 16:04 UTC

dragonchild

@x=<>;print sort{$x{$a}cmp$x{$b}}map{($x{$_}=lc)=~s/\d+/0
x(length("@x")-length$&).$&/ge;$_}@x
[download]

[reply]
[d/l]

Re^3: Golf: 3 hole golf game

by etcshadow (Priest) on Nov 17, 2004 at 21:10 UTC

Was efficiency a requirement? If it was, then oops. Oh, well, I was optimizing for brevity.

P.S. I wasn't able to inline the "@x" when I tried it (must be because I'm using a much older perl). I didn't throw in the $z="@x"; just to waste space. I was actually pretty disapointed at having to do so. Nice. I should really upgrade my perl (or at least have a more up-to-date version around).

------------
:Wq
Not an editor command: Wq
[download]

[reply]
[d/l]

Re^4: Golf: 3 hole golf game

by tilly (Archbishop) on Nov 17, 2004 at 21:46 UTC

Re^2: Golf: 3 hole golf game

by dragonchild (Archbishop) on Nov 17, 2004 at 12:59 UTC

[reply]

Re^3: Golf: 3 hole golf game

by etcshadow (Priest) on Nov 17, 2004 at 21:04 UTC

It should be obvious that my select.pl is just a trivial modification to my shuffle.pl. I obviously didn't spend long enough converting it over. Thanks.

------------
:Wq
Not an editor command: Wq
[download]

[reply]
[d/l]

Re: Golf: 3 hole golf game
by Beechbone (Friar) on Nov 24, 2004 at 15:23 UTC


P is for Practical
	PerlMonks