Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Golf: 3 hole golf game

by theroninwins (Friar)
on Nov 16, 2004 at 07:28 UTC ( #408059=perlmeditation: print w/replies, xml ) Need Help??

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.

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.

    After Compline,
    Zaxo

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

    Update:

    human.pl: 189 strokes shuffle.pl: 33 strokes select.pl: 37 strokes ------------------------ total: 259 strokes
    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

    Update2:

    human.pl: 185 strokes
    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],<>

    Update3:

    human.pl: 159 strokes
    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],<>

    Update3:

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

    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.

Re: Golf: 3 hole golf game
by tilly (Archbishop) on Nov 17, 2004 at 03:05 UTC
    First a random technical note. The implementation of rand guarantees that the same value cannot be returned twice in a very large number of calls. So your note about #2 and #3 is not true. If I'm free to ignore that, I get much smaller entries for those. But I'll submit entries that don't (ab)use that fact about rand.

    Here is my score:

    human.pl: 87 strokes shuffle.pl: 47 strokes select.pl: 52 strokes ------------------------ total: 186 strokes
    Note that you might not accept my human.pl, it does have an artificial (though generous and easy to increase) limit in it. I used no modules. Here are my solutions.
      Cutting 8 strokes from human.pl to 79...

      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.

      "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
        No, that is not a bug in Perl, it is a limitation that comes from fundamental facts of computer science. Perl's rand is a pseudo-random number generator. (That the documentation for rand doesn't make this clear is a bug in the documentation though...) It can't produce really random numbers (producing random numbers by a deterministic algorithm is a neat trick), but it produces something that looks pretty random for a very long time.

        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.

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
    Although my human.pl is (sadly) a complete ripoff of Tilly's... I just changed the arbitrary limit to a silly but not arbitrary one. Also, no modules for #2 or #3.

    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..(@_=<>)

    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]+)/]}<>

    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
      And ripping off dragonchild's improvements on my human.pl, plus adding one improvement on your strategy we get to 94 characters:
      @x=<>;print sort{$x{$a}cmp$x{$b}}map{($x{$_}=lc)=~s/\d+/0 x(length("@x")-length$&).$&/ge;$_}@x
      Incidentally nice work on the select and shuffle problems. Marginally less efficient than my solution, but a lot shorter. (Well technically your solution is quadratic, but the quadratic bit has a small constant.)
        Nice.

        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
      You can get another stroke out of select.pl by changing your elipsis to a comma. That gets you to 36.

      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.

        Oh, yeah, duh. :-D

        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
Re: Golf: 3 hole golf game
by Beechbone (Friar) on Nov 24, 2004 at 15:23 UTC
    Not the shortest for #1, but I like the way:

    Search, Ask, Know

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://408059]
Approved by neilh
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (5)
As of 2019-06-20 19:05 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Is there a future for codeless software?



    Results (91 votes). Check out past polls.

    Notices?