title: Generating guitar tabs?

text:
# Question
Title: Generating guitar tabs?
**Write the shortest program that generates guitar tabs for the chords given as input.**

So that the guitarists among you don't have an advantage, and to make it deterministic (and probably easier to code), here are the **only** forms of the chords authorized:

```
Major chords:

  E   F   F#  G   G#  A   A#  B   C   C#  D   D#
e 0---1---2---3---4---0---1---2---3---4---5---6---
B 0---1---2---3---4---2---3---4---5---6---7---8---
G 1---2---3---4---5---2---3---4---5---6---7---8---
D 2---3---4---5---6---2---3---4---5---6---7---8---
A 2---3---4---5---6---0---1---2---3---4---5---6---
E 0---1---2---3---4---0---1---2---3---4---5---6---

Minor chords:

  Em  Fm  F#m Gm  G#m Am  A#m Bm  Cm  C#m Dm  D#m
e 0---1---2---3---4---0---1---2---3---4---5---6---
B 0---1---2---3---4---1---2---3---4---5---6---7---
G 0---1---2---3---4---2---3---4---5---6---7---8---
D 2---3---4---5---6---2---3---4---5---6---7---8---
A 2---3---4---5---6---0---1---2---3---4---5---6---
E 0---1---2---3---4---0---1---2---3---4---5---6---

```

Note that the 5 first chords and the 7 last chords of each series have different forms.

All the chords are simple major or minor chords (no 7th or other variations).

You should take care of flats too. Reminder:

```
A# = Bb
C# = Db
D# = Eb
F# = Gb
G# = Ab

B#, Cb, E# and Fb are not used

```

Output **must** include the first column with the cord names, as shown above. It does **not** have to include the chord name on top. Chords must be separated by 3 `-` as shown above. The final 3 `-` are optional.

Input is a string consisting of chord names, separated by spaces.

An example input is:

```
Bm Gb A E G D Em F#

```

and the corresponding output is:

```
e 2---2---0---0---3---5---0---2---
B 3---2---2---0---3---7---0---2---
G 4---3---2---1---4---7---0---3---
D 4---4---2---2---5---7---2---4---
A 2---4---0---2---5---5---2---4---
E 2---2---0---0---3---5---0---2---

```

# Answer
> 9 votes
## JavaScript, 297 277 262 235 223 chars

No carriage returns in the golfed version are significant; they are there only to make the answer readable. Semicolons are significant.

*Edit:* Replaced the outer `map` with a while loop and other edits. Finally inside of 2× the size of the Golfscript version (for now)!

*Edit:* Replaced the `indexOf` with math, broke down the lookup table, other small improvements.

*Edit:* Another `map` to `for` and put in a final `\n` I had been unnecessarily eating. Finally inside of Jules's Python version.

```
i=prompt(o='').split(' ');for(r=6;o+=' EADGBe'[r]+' ',r--;o+='\n')
for(j=0;n=i[j++];o+=(([84,13,52,5][2*/m/.test(n)+x]*8>>2*r&3)+y-7*x)+'---')
y=n.charCodeAt(0),y=(2*y-(y>66)-(y>69)+(n[1]<'$')-(n[1]=='b')+2)%12,x=y>6;alert(o)

```

Output no longer takes advantage of the trailing `---` being optional as:

```
e 2---2---0---0---3---5---0---2---
B 3---2---2---0---3---7---0---2---
G 4---3---2---1---4---7---0---3---
D 4---4---2---2---5---7---2---4---
A 2---4---0---2---5---5---2---4---
E 2---2---0---0---3---5---0---2---

```

# Answer
> 7 votes
## Golfscript, 136 chars

```
[["eBGDAE"{[]+" "+}/]]\" "/{.-2\{"bm#A B C D E F G"?.)!!*(+}/14%.3>-.8>-.7/@109?0>2*+[963 780 882 753]{3base(;}%=\7%{+'---'+}+%}%+zip n*

```

Fully 23 chars (17.5%) deal with those two characters at the start of each output row.

Sample output, testing the edge cases:

```
$ golfscript.rb tabs.gs <<<"E G# Ab A Db D# Em G#m Abm Am D#m"
e 0---4---4---0---4---6---0---4---4---0---5---
B 0---4---4---2---6---8---0---4---4---1---6---
G 1---5---5---2---6---8---0---4---4---2---7---
D 2---6---6---2---6---8---2---6---6---2---7---
A 2---6---6---0---4---6---2---6---6---0---5---
E 0---4---4---0---4---6---0---4---4---0---5---

```

I've only spent about an hour on this, so it can probably be reduced by 5 to 10 chars at least. Conceptually it turns out to be quite similar to DocMax's solution: lookup table for four cases, then increment by an offset and join the strings in the right order.

# Answer
> 4 votes
After coding this up, I realized I could have done this a lot smarter...maybe I'll make another entry. Hopefully I'll just get points for being the quickest!

Anyway, there is 962 characters of Perl.

```
%c =(B=>{E=>0,F=>1,Gb=>2,G=>3,Ab=>4,A=>2,Bb=>3,B=>4,C=>5,Db=>6,D=>7,Eb=>8,Em=>0,Fm=>1,Gbm=>2,Gm=>3,Abm=>0,Am=>1,Bbm=>2,Bm=>3,Cm=>4,Dbm=>5,Dm=>6,Ebm=>7},G=>{E=>1,F=>2,Gb=>3,G=>4,Ab=>5,A=>2,Bb=>3,B=>4,C=>5,Db=>6,D=>7,Eb=>8,Em=>0,Fm=>1,Gbm=>2,Gm=>3,Abm=>4,Am=>2,Bbm=>3,Bm=>4,Cm=>5,Dbm=>6,Dm=>7,Ebm=>8},D=>{E=>2,F=>3,Gb=>4,G=>5,Ab=>6,A=>2,Bb=>3,B=>4,C=>5,Db=>6,D=>7,Eb=>8,Em=>2,Fm=>3,Gbm=>4,Gm=>5,Abm=>6,Am=>2,Bbm=>3,Bm=>4,Cm=>5,Dbm=>6,Dm=>7,Ebm=>8},A=>{E=>2,F=>3,Gb=>4,G=>5,Ab=>6,A=>0,Bb=>1,B=>2,C=>3,Db=>4,D=>5,Eb=>6,Em=>2,Fm=>3,Gbm=>4,Gm=>5,Abm=>6,Am=>0,Bbm=>1,Bm=>2,Cm=>3,Dbm=>4,Dm=>5,Ebm=>6},E=>{E=>0,F=>1,Gb=>2,G=>3,Ab=>4,A=>0,Bb=>1,B=>2,C=>3,Db=>4,D=>5,Eb=>6,Em=>0,Fm=>1,Gbm=>2,Gm=>3,Abm=>4,Am=>0,Bbm=>1,Bm=>2,Cm=>3,Dbm=>4,Dm=>5,Ebm=>6});
%b=('A#'=>'Bb','C#'=>'Db','D#'=>'Eb','F#'=>'Gb','G#'=>'Ab');
foreach(qw(e B G D A E)){p($_,@ARGV)}
sub p{$s = shift;print "$s ";$s = uc($s);foreach(@_){while(($h,$f)=each(%b)){s/$h/$f/}print "$c{$s}->{$_}---"}print "\n"}

```

Here is the corresponding output.

```
dhrasmus:Desktop standage$ perl guitar Bm Gb A E G D Em F#
e 2---2---0---0---3---5---0---2---
B 3---2---2---0---3---7---0---2---
G 4---3---2---1---4---7---0---3---
D 4---4---2---2---5---7---2---4---
A 2---4---0---2---5---5---2---4---
E 2---2---0---0---3---5---0---2---

```

# Answer
> 4 votes
Since shorter solutions have been given already (damn you GolfScript!), here is mine:

## Python, 229 chars

```
s=[("E EmF FmF#GbG GmG#AbA AmA#BbB BmC CmC#DbD DmD#Eb".find("%-02s"%s[:2])/4,s[-1]!='m')for s in raw_input().split()]
for c in range(6):
 l='eBGDAE'[c]+' '
 for(i,M)in s:x=i>4;l+=`i-5*x+2*(2<c+x<5)+(M+x)*(c==2-x)`+"---"
 print l

```

Output:

```
> echo "Bm Gb A E G D Em F#" | python guitar.py
e 2---2---0---0---3---5---0---2---
B 3---2---2---0---3---7---0---2---
G 4---3---2---1---4---7---0---3---
D 4---4---2---2---5---7---2---4---
A 2---4---0---2---5---5---2---4---
E 2---2---0---0---3---5---0---2---

```

# Answer
> 3 votes
**Python, 449 chars**

```
z=int
f=str
r=range
j=''.join
n='E F F# G G# A A# B C C# D D#'.split()
n+=[x+'m'for x in n]
c=[j([f(z(x)+i)for x in'001220'])for i in r(5)]+[j([f(z(x)+i)for x in'022200'])for i in r(7)]
c+=[x[:2]+f(z(x[2])-1)+x[3:]for x in c[:5]]+[x[0]+f(z(x[1])-1)+x[2:]for x in c[5:]]
a=[c[n.index((chr(ord(i[0])-1)+'#'+i[2:]).replace('@','G')if len(i)-1 and i[1]=='b'else i)]for i in raw_input().split()]
for i in r(6):print'eBGDAE'[i],j([x[i]+'-'*3 for x in a])

```

# Answer
> 3 votes
# C99 - 231 characters

The chords are given on the command line, one argument per chord, and of course there is no input validation of any kind.

```
#include<stdio.h>
int main(int c,char**v){for(char*o="e0)B2)G2*D2+A0+E0)",i,m;*o;o+=3,v-=c,puts(""))for(printf("%c ",*o);*++v;printf("%c---",i-(i>2)-i/9+o[1+i/8]-(*o-66-i/8*5?0:m?m+2[*v]>99:0)))m=1[*v],i=(**v*2-4+m/35-m/98*3)%14;}

```

Sample run:

```
$ ./a.out Bm Gb A E G D Em F#
e 2---2---0---0---3---5---0---2---
B 3---2---2---0---3---7---0---2---
G 4---3---2---1---4---7---0---3---
D 4---4---2---2---5---7---2---4---
A 2---4---0---2---5---5---2---4---
E 2---2---0---0---3---5---0---2---

```

## Un-golfed

```
#include<stdio.h>
int main(int c,char**v){
     // o points to three characters per output line:
     //   string name, number for A, adjusted number for E (ASCII code minus 7)
     char* o="e0)B2)G2*D2+A0+E0)",
          i, // chord: A=0, A#=1, ..., G#=13, allowing also 3="E#" and 9="B#"
          m; // second character in chord name
     for (; *o; o+=3) {
          printf("%c ", *o);
          for (; *++v; ) {
               m = 1[*v],
               i = (**v*2-4+m/35-m/98*3)%14; // parse & adjust for sharp, flat
               printf("%c---",
                      i-(i>2)-i/9 // eliminate "E#", "B#"
                      +o[1+i/8] // get the number for a major chord
                      // adjust for minor...
                      -(*o-66-i/8*5
                        ? 0
                        : m ? m+2[*v]>99 : 0));
          }
          v -= c; // rewind argument pointer
          puts("");
     }
}

```

## Nonstandard C - 206 characters

If we don't care about language specifications, GCC can compile the following one-liner into a functional binary, even though it mixes C99 variable declarations with a K&R style argument declaration (and an implicit declaration of printf).

```
main(c,v)char**v;{for(char*o="e0)B2)G2*D2+A0+E0)",i,m;*o;o+=3,v-=c,puts(""))for(printf("%c ",*o);*++v;printf("%c---",i-(i>2)-i/9+o[1+i/8]-(*o-66-i/8*5?0:m?m+2[*v]>99:0)))m=1[*v],i=(**v*2-4+m/35-m/98*3)%14;}

```

# Answer
> 2 votes
**C++, 432**

```
#include <cmath>
#include <iostream>
F(int c){c-=65;return c*1.6+sin(c/5.+.3);}
T(int a,int s){if(s)return(a=(T(a,s-1)+2)%3)-=(a==1&s>2);return(a<7)*2;}
#define c(a,b) while(*(++j)==a)b;--j;
#define O std::cout<<
main(int a,char*p[]){
int P=2;for(int i=-1;++i<6;P=2){O p[1][i];O" ";while(P<a){char*j=p[P++];
int f=F(*j);c('#',++f)c('b',--f)
int t=T(f,i)*3.5;if(*(++j)!='m'){--j;t+=(t==3);}
O(f-F(p[1][i])+t+24)%12;O"---";
}O'\n';}}

```

Note that this needs the guitar tuning as the first parameter. (Most non-standard-tunings will give you ridiculous fingerbreaking results, but I guess you're content with standard tuning.)

For Hotel California, you can do `$./a.out EBGDAE Cbm Gb Bbb Fb G D Em F# Bm F# G## D## F## C## D##m E##`. Result:

```
E 2---2---0---0---3---5---0---2---2---2---5---0---3---5---0---2---
B 3---2---2---0---3---7---0---2---3---2---5---0---3---7---0---2---
G 4---3---2---1---4---7---0---3---4---3---6---1---4---7---0---3---
D 4---4---2---2---5---7---2---4---4---4---7---2---5---7---2---4---
A 2---4---0---2---5---5---2---4---2---4---7---2---5---5---2---4---
E 2---2---0---0---3---5---0---2---2---2---5---0---3---5---0---2---

```

# Answer
> 2 votes
**390 345 340 Postscript**

Simplified to a guitar-pragmatic approach (the E shape is just a variation of the A shape, shifted down a string, with one finger change). Borrowed the encoded-string idea from the other answers.

```
[/p{print}/x{exch}/e{cvx exec}/d{dup 0
get}/f{forall}(A0#1B2C3D5E7F8G:b;){}forall/m{dup
4 2 copy get 1 sub put}109{m 48}/+{[3 1 roll x{1
index add x}f]}/*{[0 0 2 2 2 0 0]x{load e 48 sub
+}f d 12 gt{-12 +}if d 6 gt{m -7 + 1}{0}ifelse 6
getinterval}>>begin[ARGUMENTS{*}f][(E)(A)(D)(G)(B)(e)]6{[x
e p( )p]x[x{[x e( )cvs p(---)p]}f]x()=}repeat

```

*Previously:*

**450 442 418 Postscript**

I fixed the output format with this one, too. (Previous versions began "E---" rather than "e ".)

```
<</i{index}/a{add}/p{pop}/x{exch}/g{getinterval}/r{print}/f{forall}/e{exec}>>begin<<65[0
2 3 5 -5 -4 -2]{1 i 1 a}f p 35{1 a}98{1 sub}109{x dup
4 20 put x}>>begin[ARGUMENTS{[x[0 5 12 17 21 24 29
0]x{load e}f x{1 i a x}f]dup 0 get 0 ge{0}{1}ifelse 7
g[0 -5 -10 -15 -19 -24 -29]0 1 6{2 copy get 3 i 2 i
get a 3 copy put p p}for x p 0 6
g}f][(E)(A)(D)(G)(B)(e)]6{[x cvx e r( )r]x[x{[x cvx
e( )cvs r(---)r]}f]x(\n)r}repeat

```

How to run it: `gsnd -q -- tab.ps Bm Gb A E G D Em F\#` (hide the sharp from the shell).

The *un-golfed* version was almost more difficult than the golfed one. But I tried to be thorough. *Edit: a few more comments on the tricksy-bits.*

```
%!PS
<<    %axioms and operations
/t{2 2 1}    %major tetrachord
/m{t t 2}    %mixolydian mode
/u{2 1 2}    %minor tetrachord
/a{u u}      %aolian mode
/s{m m t}    %2.5-octave mixolydian intervals
/r{3 1 roll}
/${[exch 0 exch{1 index add}forall]}    %running sum: convert (relative)intervals to (abstract)fretstops
/+{[r exch{1 index add exch}forall pop]}    %scale array by scalar
/@{[r{2 copy get r pop}forall pop]}    %select array elements from array of indices
/&{0 1 3 index length 1 sub{    %array2 += array1
    2 copy get 3 index 2 index get add 3 copy put pop pop}for exch pop}
>>begin<<    %map ascii values to scaling functions
65[a]$    %generate fretstops of the A aolian scale to assign scalars to note names
[0 0 0 0 -12 -12 -12]&    %drop E F and G down an octave
{[exch/+ cvx]cvx 1 index 1 add}forall pop    %generate the pairs 'A'->{0 +}, 'B'->{2 +}
35{1 +}     %'#'-> scale up by one
98{-1 +}    %'b'-> scale down by one
109{dup 4 2 copy get 1 sub put}     %'m'-> tweak the 'third' down by one
%generate chord pattern from (string)
/*{[s]$       %generate fretstops of the E mixolydian scale
  [1 4 8 11 13 15 18]    %A-shape figured bass: IV chord of E mixolydian
  -1 +       %convert scale degrees to array indices
  @       %generate chord template by selecting indices from mixolydian scale
  exch{load exec}forall       %execute ascii values, scaling the pattern
  dup 0 get 0 ge{0}{1}ifelse 6 getinterval    %discard first note if it has fallen off the bottom
  [0 -5 -10 -15 -19 -24]&}    %subtract the string offsets
>>begin    %activate definitions
%(A)* pstack()= clear    %[0 0 2 2 2 0]
%(B)* pstack()= clear    %[2 2 4 4 4 2]
%(F#)* pstack()= clear    %[2 4 4 3 2 2]
%(Abm)* pstack()=    %[4 6 6 4 4 4]
[ARGUMENTS{*}forall]    %convert array of strings to array of patterns
[(E)(A)(D)(G)(B)(e)]    %array of string names
6{    %for each "string"
    [exch cvx exec print( )print]    %pop string name and print with space
    exch       %put names behind numbers
    [exch{     %for each "chord"
        [exch cvx exec( )cvs print(---)print]    %pop number, convert, print with trailing hyphens
    }forall]    %zip up chord array for next iteration
    ()=         %print a newline
    exch        %put numbers behind names
}repeat

```

And how about *House of the Rising Sun* as a test?

```
04:51 PM:~ 0> gsnd -q -- tabb.ps Em G A C Em G B B Em G A C Em B Em B|sed 's/^/    /'
e 0---3---0---3---0---3---2---2---0---3---0---3---0---2---0---2---
B 0---3---2---5---0---3---4---4---0---3---2---5---0---4---0---4---
G 0---4---2---5---0---4---4---4---0---4---2---5---0---4---0---4---
D 2---5---2---5---2---5---4---4---2---5---2---5---2---4---2---4---
A 2---5---0---3---2---5---2---2---2---5---0---3---2---2---2---2---
E 0---3---0---3---0---3---2---2---0---3---0---3---0---2---0---2---

```

---
Tags: code-golf, ascii-art, music
---


# Question
Title: Fastest python implementation of multiplication table
I'd be interested to see who can come up with the fastest function to produce multiplication tables, in the following format:

```
   1   2   3   4   5   6   7   8   9  10  11  12
   2   4   6   8  10  12  14  16  18  20  22  24
   3   6   9  12  15  18  21  24  27  30  33  36
   4   8  12  16  20  24  28  32  36  40  44  48
   5  10  15  20  25  30  35  40  45  50  55  60
   6  12  18  24  30  36  42  48  54  60  66  72
   7  14  21  28  35  42  49  56  63  70  77  84
   8  16  24  32  40  48  56  64  72  80  88  96
   9  18  27  36  45  54  63  72  81  90  99 108
  10  20  30  40  50  60  70  80  90 100 110 120
  11  22  33  44  55  66  77  88  99 110 121 132
  12  24  36  48  60  72  84  96 108 120 132 144

```

Use the following template to benchmark your code using a 12-width table, and post your code and the resulting time here.

```
#!/usr/bin/python
import timeit
cycles = 100000

referencecode = r'''

def multable(width):
  '\n'.join(''.join('{0:4}'.format(x*y) for x in range(1,width+1)) for y in range(1,width+1))

'''

yourcode = r'''

def multable(width):
  pass # Your function here

'''

referencetime = timeit.Timer('multable(12)', setup=referencecode).timeit(number=cycles)
yourtime = timeit.Timer('multable(12)', setup=yourcode).timeit(number=cycles)

print 'Your code completed', referencetime / yourtime, 'times faster than the reference implementation'

```

# Answer
> 2 votes
## About 352 times faster, according to the benchmark code

(on my machine)
Python 2.7

Exactly how much faster it is will vary widely between machines. I tested it on my web server also and there it was only 288 times as fast.

```
import itertools as i, operator as o

def multable(width, m={}):
   if not width in m.keys():
      m[width] = '\n'.join(['%4d'*width]*width)%tuple(i.starmap(o.mul,i.product(range(1,width+1),repeat=2)))
   return m[width]

```

The actual algorithm is only about 1.25 times as fast as the reference one, but if you have a function which is called often, caching the result saves a lot of time.

# Answer
> 1 votes
```
def multable(width):
  R=range(1,width+1)
  M=[i*j for i in R for j in R]
  return(('%4d'*width+'\n')*width)%tuple(M)

```

about 3.3x faster than the reference implementation.

# Answer
> 0 votes
My approach (python2.7):

# 1.63x Faster

```
from itertools import imap, izip, starmap, product
from operator import mul

def multable(width):
  return '\n'.join(imap(''.join, izip(*((imap('{:4}'.format, starmap(mul, product(xrange(1,13), repeat=2))),) * 12))))

```

# 2.32x Faster

```
from itertools import starmap, product
from operator import mul

def multable(width):
  return (('{:4}' * width + '\n') * width).format(*starmap(mul, product(xrange(1,13), repeat=2)))

```

---
Tags: fastest-code, python
---


title: Try to understand this java code

text:
# Question
Title: Try to understand this java code
The students in my high school computer science class were asked to write the game of nim for a simple project. Most of them found it very easy and finished quickly. However, one student came up with this solution. I'll probably make them redo it anyway, but I'm wondering if anyone can understand what's going on.

```
enum $ {

$$;
static int _, $_$, $_, _0_;

{
    {
        {
            {
                _$ $_ = _$.__;
            }
        }
    }
}

enum _$ {

    __(new byte[][]{
        "\nNumber of stones: \0\nPlayer one move: \0Computer takes \0\nComputer wins!\n\0\nPlayer wins!\n".getBytes(),
        new byte[]{(byte) (_ = (int) (Math.random() * (_ = ((_ = -~_) * (_ << -~-~_) + -~-~-~_ + -~ ~ ~-~_)) + _))}},
        null);

    java.io.Console ___ = System.console();
    _$(byte[] _$_[], String $[]) {
        for ($ = new String(_$_[$_$]).split(Character.toString((char) $_$)); _ > 0;) {
            ___.printf($[$_$] + _);
            do _0_ = ___.readLine($[-~$_$]).getBytes()[$_$] - 060;
            while (_0_ > -~-~-~$_$ || _0_ > _);
            _ -= $_$ + _0_ >> $_$;
            if (((!(!(((!((!((_) < -~($_ = $_$))))))))))) break;
            _ -= $_ = Math.min((int) (Math.random() * -~-~-~$_$ + -~$_$), _);
            ___.printf($[-~-~$_$] + $_);
        }
        ___.printf(($_$ = -~-~-~$_$) > _ ? $[$_ > 0 ? -~$_$ : $_$] : $[2]);}}};

```

\`

# Answer
> 3 votes
just cause I have way too much time on my hands:

```
import java.io.*;
import java.util.*;

enum MyEnum {

    $$;

    {
        EnumCalc $_ = EnumCalc.CONSTR;
    }

    enum EnumCalc {

        static int total, $_$, comp, player;
            CONSTR( );

        PrintStream out = System.out;
        Scanner scan = new Scanner(System.in);

        EnumCalc() {

            total = (int) (Math.random() * 20 + 20);
            strings = new String[] { "\nNumber of stones: ",
                    "\nPlayer one move: ", "Computer takes ",
                    "\nComputer wins!\n","\nPlayer wins!\n" };
            while(total > 0) {
                out.printf("\nNumber of stones: " + total);

                do {
                    out.printf("\nPlayer one move: ");
                    player = scan.nextLine().charAt(0) - '0';
                } while (player > 3 || player > total);//input loop

                total -= player;
                comp = 0;
                if (total < 1)
                    break;
                comp = Math.min((int) (Math.random() * 4), total);
                total -= comp;
                out.printf("Computer takes " + comp);
            }
            String string;
            if (3 > total)
                string = comp > 0 ?"\nPlayer wins!\n":"\nComputer wins!\n";
            else
                string = "Computer takes ";
            out.printf(string);
        }

    }
};

```

note that `-~i` is the same as `1+i`

and I replaced the console calls with System.out and Scanner cause eclipse doesn't give me a Console

---
Tags: code-golf, obfuscation
---


title: PCM Wave time stretch

text:
# Question
Title: PCM Wave time stretch
Write the smallest program performs a time stretch operation on a PCM Wave (.wav) file.

Rules:

* Parameter input will by via whatever standard argument mechanism your language comes with, e.g. `argv` in C/C++, `$_GET` in PHP. Hard coded paths are not allowed.
* First parameter will be a decimal value that represents the stretch coefficient. 1 means don't stretch, 2 means twice the length, 0.5 means half the length, 0.333 means one third the length. An example might be `stretch.exe 1.5 c:\sound.wav`
* The time stretch operation does not need to perform pitch correction.
* You must not drop samples to fit a compression (i.e. stretch \< 1). You should use interpolation, weighted mean, or a similar method.
* Assume a WAVE PCM file with a RIFF header.
* Assume 16-bits per sample (bonus if your code works for 8-bit and 24-bit audio)
* You must handle any number of audio channels.
* You must at least handle 11025, 22050 and 44100Hz sample rates, though the ability to handle arbitrary rates would be a bonus! :)
* Your output file must keep the same sample rate, sample size and channel count as the input file.
* The output file must be named "stretch.wav"
* You may not use any 3rd party libraries or built-in functions for audio processing. The parsing of the WAV file and the time stretch operation must be your own code.

On Windows, the `C:\Windows\Media` directory contains plenty of WAV files to test with.

# Answer
### Ruby, 220 characters

```
s,n=$*
w=IO.binread(n).unpack r='s<*'
x=[];t=[g=0]*c=w[11]
w[u=22..-1].each_slice(c){|f|g+=v=1.0/s.to_f
c.times{|h|t[h]+=f[h]*v}
(c.times{|h|x<<=m=t[h]/g;t[h]-=m};g-=1)until 1>g}
w[u]=x;IO.binwrite'stretch.wav',w.pack(r)

```

This version works with ruby 1.9.3 with basic 16 bit files (e.g. no additional chunks) for any sample rate or number of channels.
> 1 votes

---
Tags: code-golf, music, audio
---


# Question
Title: Write a code golf problem in which Java wins
Write a code golf task such that

1. The only input (if any) required by the task is text from standard input, and the only output required by the task is text to standard output.
2. There is exactly one correct output string of characters for every possible legal input as defined by the task.
3. Each possible legal input is less than 10000 characters long.
4. Each correct output is less than 10000 characters long.
5. **The shortest program** (that StackExchange users manage to write) **that successfully completes the task** for every input **is in Java.**

The task with the shortest associated Java program wins.

# Answer
> 34 votes
# 48 characters

**Task:** Ignore any input. Always produce exactly the following output:

```
java.lang.ExceptionInInitializerError
Caused by: java.lang.ArithmeticException: / by zero
    at M.<init>(M.java:1)
    at M.<clinit>(M.java:1)

```

**Solution:**

```
enum M{M;System x;{x.setErr(x.out);int y=1/0;}}

```

Save as `M.java`, compile with `javac M.java` and run with `java M`. It also produces an error message on standard error, but that doesn't violate any of the rules.

---
Tags: code-golf
---


title: Decompose a String

text:
# Question
Title: Decompose a String
## Challenge

You are to write the shortest complete program that takes a string as input from STDIN and decomposes it as far as possible, and prints the composition to STDOUT.

To decompose a string, your program finds a substring (of length greater than 1) within the original string, the repetitions of which take up a much of the string as possible. It then creates several new strings, one of which is that substring and the others are the original, split apart at where the substring occurred. You then repeat this process of finding a substring whose repetitions take up as much of those strings as possible.

The end of input is reached when there is a newline (`/n`).

Output should consist of each substring in the order that it is found, followed by two newlines, followed by everything left at the end of decomposition sorted from longest to shortest, all separated by line breaks.

## Example

**input**

```
Happy birthday to you! Happy birthday to you! Happy birthday to somebody! Happy birthday to you!

```

The longest repeated substring is `Happy birthday to you!`; however, the substring `Happy birthday to` (with a space after the "to") takes up more space because there is one more repetition of it. The `Happy birthday to` is outputted. You then end up with several new strings.

```
Happy birthday to (with space at the end)
you!  (with space)
you!  (with space)
somebody!  (with space)
you!

```

Here, the substring `you!`is repeated the most. Even though it is not repeated within any individual string, it is repeated multiple times throughout all of the strings. The `you!` is outputted. Now you have

```
Happy birthday to (with space)
you!
   (lone space character)
   (lone space)
somebody! (with space)

```

Here, the substring `y`(with space) is repeated the most. The `y` is outputted. Now you have

```
Happ
birthda
to (with space)
y (with space)
you!
   (lone space character)
   (lone space)
somebody! (with space)

```

As far as I can tell, there are no more substrings of length \> 1 (the spaces are only one character). You then output each substring that you found, followed by what is above.

**Total Output**

```
Happy birthday to
you!
y

somebody!
birthda
Happ
you!
to
y

```

There should be two lines of just a space at the end, but those are not being displayed. There should also be a space after that single y.

# Answer
> 2 votes
### Ruby, 232 characters

```
i=[gets.chop]
while l=((0..-2+n=(v=i*'').size).map{|s|(s+1..n).map{|m|c=v[s..m]
u=[i.map{|t|t.split(c)},c].flatten
v.size>(w=(u*'').size)&&[w,c,u]}}.flatten(1)-[false]).sort[0]
puts l[1]
i=l[2]
end
puts
i.sort_by!{|k|-k.size}
puts i

```

This code reflects my first idea towards the problem. Actually it took much more characters than I thought initially. Nevertheless I still hope to find a shorter solution using a different approach.

# Answer
> 1 votes
If you allow for the weak definition of a substring, then here's a trivial solution.

**R, 9 characters (10 with `\n`)**

```
d=scan()
d

```

But I suspect you mean strict substring, in which case parroting back the input string will not suffice :-)

**R, not yet condensed**

```
d <- "Happy birthday to you! Happy birthday to you! Happy birthday to somebody! Happy birthday to you!"
#d=scan()
# Shorten things
l=list
# Break up into consituent parts
e=strsplit(d,"")[[1]]
g=l()
for(i in 1:nchar(d)) g[[i]]=embed(e,i)
g=lapply( g, function(x) apply(x,1,paste,collapse="") )
# Find max coverage (function takes each element of the g list and returns max X its length) (if type=2 then returns the string instead)
m=function(x,t=1) {
  r=rle(sort(x))
  w=which.max(r$l)
  if(all(r$l[w]<2)) return(0)
  v=r$v[w]
  switch(t,r$l[w]*nchar(v),v)
}
m(g[[which.max(sapply(g,m))]],2)

```

Which returns `" ot yadhtrib yppaH !uoy ot yadhtrib yppaH"`.

Easy enough to reverse and to iterate this over the remaining string, but I'm going to hold off pending clarification of whether overlapping substrings are allowed. I suspect not from the example, but this one has more coverage (82 characters) if so.

---
Tags: code-golf, string
---


title: Resolve quadratic equation

text:
# Question
Title: Resolve quadratic equation
**Challenge:**

Write the smallest program (in characters) that resolves quadratic equations i.e. `ax² + bx + c = 0`

**Rules:**

Given 3 numbers in **R** comma-delimited on STDIN: a,b,c (a != 0), print on STDOUT the 2 roots in **C**, one per line.

**R** stands for real numbers, **C** for complex numbers.

**Examples:**

```
Input         Output

1,0,0         r1=0     also accepted: r1=(-0-sqrt(0))/2
              r2=0

1,2,1         r1=-1    also accepted: r1=(-2-sqrt(0))/2
              r2=-1

1,1,1         r1=(-1-isqrt(3))/2  also accepted: r1=(-1-sqrt(-3))/2 or r1=-0.5-0.866i
              r2=(-1+isqrt(3))/2

```

# Answer
**R, 19 chars**

```
polyroot(scan(n=3))

```

or more strictly following the I/O requirements in 58 chars:

```
r=polyroot(rev(scan(sep=",")));cat("r1=",r[1],"\nr2=",r[2])

```

edit: reversed coefficients
> 8 votes

# Answer
# J, 21

J's got a verb to do exactly that: `p.` It does complex to complex, but your problem is a subset of that.

```
echo"0>{:p.|.".1!:1[3

```

As always with J solutions here, I/O and formatting take up 90% of the solution.
> 6 votes

# Answer
## Python 3, 79 chars

```
a,b,c=eval(input())
d=(b*b-4*a*c)**.5/2/a
x=-b/2/a
print('r1=',x+d,'\nr2=',x-d)

```

Python's imaginary unity is `j` and not `i`. I used Python 3 because the power operator works also on negative numbers.

BTW, is it really needed to write `r1= ...` and `r2= ...` ?
> 4 votes

# Answer
## Perl, 96 87 Characters

```
($a,$b,$c)=eval<>;$_=abs($_=$b*$b-4*$a*$c)**.5/2/$a.i x($_<0);$b/=-2*$a;die"r1=$b+$_
r2=$b-$_"

```

The line break is intentional, as is a space.

Edit: By reformatting output, I can shorten this to:

```
($a,$b,$c)=eval<>;$_="sqrt(".($b*$b-4*$a*$c)."))/".2*$a;$b*=-1;die"r1=($b+$_
r2=($b-$_"

```
> 1 votes

# Answer
## Perl, 76 characters (+1 command line switch)

```
perl -pe '($a,$b,$c)=eval;$d=($b/=-$a)**2-4*$c/$a;$_="-+";s!.!r@+=($b$&sqrt($d))/2\n!g'

```

Replacing the `\n` with a literal newline allows a further trivial one-character reduction.

Sample input / output:

```
1,0,0
r1=(0-sqrt(0))/2
r2=(0+sqrt(0))/2
1,2,1
r1=(-2-sqrt(0))/2
r2=(-2+sqrt(0))/2
1,1,1
r1=(-1-sqrt(-3))/2
r2=(-1+sqrt(-3))/2
1,0,-1
r1=(0-sqrt(4))/2
r2=(0+sqrt(4))/2
2,1,1
r1=(-0.5-sqrt(-1.75))/2
r2=(-0.5+sqrt(-1.75))/2

```

Yeah, it's not exactly Wolfram Alpha, but I believe it should qualify as acceptable output.
> 1 votes

# Answer
# Perl, 101 chars

First stab:

```
perl -E 'my($x,$y,$z)=pop=~/\d+/g;printf"r%d=(%+d%ssqrt(%d))/%d\n",++$p,-$y,$_,$y**2-4*$x*$z,2*$x for qw/- +/;' 1,2,1

```
> 0 votes

# Answer
## D (160 chars)

```
import std.complex;import std.stdio;void main(){real a,b,c;readf("%f,%f,%f",&a,&b,&c);Complex!real j=sqrt(b*b-4*a*c)/2/a,i=-b/2/a;write("r1=",i+j,"\nr2=",i-j);}

```
> 0 votes

---
Tags: code-golf, math, complex-numbers
---


title: Implement a Graphing Calculator

text:
# Question
Title: Implement a Graphing Calculator
There have been many questions involving calculators; however, it does not appear that any involve implementing a graphing calculator.

**The Challenge**

You are to write a complete program that takes multiple formulas as input from STDIN and graphs them to STDOUT. Input will take the form `f1(x)=x^2-x-1`. There will be an `f` followed by a number 0-9 (inclusive), followed by `(x)=`, followed by the formula to graph. Your program should be able to take input, graph, take more input, graph, etc.

This is code golf.

Your graph should have the X-axis range from -5 to 5, with a resolution of at least one point every 1/2 unit. Y-axis requirements are the same. This may seem like a small range compared to modern calculators, but it will most likely be trivial in increase this. The graph should have the axis drawn on them, with tick marks in the form of `+` on the integers.

The formula should be evaluated with the normal order of operation. There will not be any vertical asymptotes/undefined regions in these formulas. The variable will always be x. If two formulas are entered with the same equation number, the oldest one should be erased and replaced with the new formula. Blank formulas should evaluate to zero. Since it is likely that the formula will not always give a nice multiple of 1/2, you are to round to the nearest 1/2.

When a formula is graphed, its line should be formed out of the number of the formula. When a line crosses an axis, the axis should be drawn on top. When two lines cross each other, it does not matter which is shown.

**Example Input**

```
f1(x)=x+1

```

**Output**

```
          +       1
          |      1
          +     1
          |    1
          +   1
          |  1
          + 1
          |1
          +
         1|
+-+-+-+-+-+-+-+-+-+-+
       1  |
      1   +
     1    |
    1     +
   1      |
  1       +
 1        |
1         +
          |
          +

```

**Input**

```
f2(x)=(x^2)^0.25

```

**Output**

```
          +       1
          |      1
          +     1
          |    1
          +   1
          |  1
2222      + 1    2222
    222   |1  222
       22 + 22
         2|2
+-+-+-+-+-+-+-+-+-+-+
       1  |
      1   +
     1    |
    1     +
   1      |
  1       +
 1        |
1         +
          |
          +

```

**Input**

```
f1(x)=-x

```

(note, it is acceptable for your program to reject this input and only except 0-x or x\*-1, but this should be documented)

**Output**

```
1         +
 1        |
  1       +
   1      |
    1     +
     1    |
2222  1   +      2222
    2221  |   222
       22 + 22
         2|2
+-+-+-+-+-+-+-+-+-+-+
          |1
          + 1
          |  1
          +   1
          |    1
          +     1
          |      1
          +       1
          |        1
          +         1

```

# Answer
### Perl, 177 characters (+1 command line switch)

```
perl -nE 's!\^!**!g;s!x!(\$k/2-6)!g;s/\d.*=/;/;$f[$&]=$_;my%a;for$k(@x=2..22){$i=0;$a{int 12.5-2*eval}[$k-2]=$i++for@f}$p="|";$$_[10]=$p^=W,$a{12}=[$p."-+"x10],say map$_//$",@$_ for@a{@x}'

```

Per this meta thread, I believe this should count as 178 characters in total.

Like the Ruby solution, I'm also using `eval` and replacing `^` with `**`.

The input parsing is both incredibly fragile and incredibly robust at the same time: `f1(x)=` can be written as `f 1 ( x ) =` or `foo 1 bar =` or even just `1=`, but very strange things could happen if you replaced the `f` with something that isn't a valid, side-effectless Perl statement. You have been warned.

Other details of interest include the way the vertical axis is drawn, which exploits the fact that the bitwise XOR of the characters `+` and `|` is `W`. Obviously, this won't work on EBCDIC systems.

The output is rendered into a hash of arrays, not an array of arrays — it turns out that it takes fewer chars to explicitly truncate the hash keys to integers and then loop over a hash slice than it takes to ensure that an array isn't indexed with negative values. I could shave off two more characters if it weren't for the annoying way Perl's `int` truncates negative values towards zero, which forced me to number the output rows from 2 to 22 instead of 0 to 20 in order to avoid rounding artifacts at the top edge of the output area.

I do make use of Perl's liberal string-to-number conversion in the input parsing, where I use the entire string `1(x)=` as an array index (it gets converted to just 1).

I could also save three more characters (and make the parsing slightly more robust) by replacing `s/\d.*=/;/;$f[$&]=$_` with `/\d.*=/;$f[$&]=$'`, but then I'd have to spend the same number of extra characters to write `$'` as `$'\''` in a single-quoted shell string. I suppose technically I wouldn't have to count those, but it feels sort of like cheating.
> 5 votes

# Answer
### Ruby, 200 characters

```
f={}
r=0..20
(f[gets[1]]=$_[6..-1].gsub /\^/,'**'
s=r.map{' '*21}
f.map{|n,k|r.map{|y|x=y*0.5-5
v=(2*eval(k)).round
v.abs<11&&y!=10&&s[10-v][y]=n
s[y][10]='+|'[y%2]
s[10][y]='+-'[y%2]}}
puts s)while 1

```

A plain ruby implementation using the standard evaluator for expressions (`^` will be replaced so that the examples given above work fine). It is not very robust and assumes the input exactly as specified in the question.
> 6 votes

# Answer
### Python 2: 320 characters

```
N=20
r=range(N+1)
d={}
while(1):
 l=raw_input()
 d[l[1]]=l[6:].replace('^','**')
 g=[[' ']*(N+1) for i in r]
 for n,f in d.items():
  for x in r:
   v=N/2+int(round(2*eval(f.replace('x','(%f)'%(x/2.0-N/4)))))
   if 0<=v<=N:g[N-v][x]=n
 for i in r:
  g[i][N/2]='+|'[i%2]
  g[N/2][i]='+-'[i%2]
 for l in g:print''.join(l)

```

Could probably be made shorter, but I'm a bit of a newbie at this :)

Making `N` a variable wastes 9 chars but I like it better that way.
> 5 votes

---
Tags: code-golf, math, ascii-art
---


title: BWInf 2011, question 5: Twin towns

text:
# Question
Title: BWInf 2011, question 5: Twin towns
This is a challenge that was originally a tas for the German *Bundeswettbewerb Informatik* (federal competition of computer science \[?\]), a competition for highschool students. As opposed to the original question, where you have to find a good solution and write some documentation, I want you to golf this. I try to replicate the question as good as possible:

## Challenge

Many towns in Europe have so-called twin towns. This year, there is a special Jubilee where each pair of twin-towns in the EU organizes a festival to celebrate their partnership. To ensure that no city has to organize too many festivals, each city has a limit of festivals it can organize. Is it possible to distribute the festivals among the twin-towns in a way, such that each pair of twin-towns organizes one festival in one the two towns and no town organizes more festivals than it is allowed to? If yes, explain how.

This is a map of some towns, their partnerships and their limits of festivals.

## Requirements

* Your program must terminate the problem in one minute each for both testcases. (See below)
* Refer to the testcases for the input format.
* The output should be empty iff no solution exists and should have the following format otherwise: One line for each pair of twin towns, `a` if `city1` organizes the festival, `b` otherwise.

```
  <city1>, <city2>, <a/b>

```
* The solution with the least number of characters that satisfies the requirements wins. In case of a tie, the program that was submitted first wins.
* Usual code-golf rules apply.

## Testcases

The original task had two testcases. I have uploaded them on github.

# Answer
## Python, 380 chars

```
import sys
N={};H={};X={}
for L in open(sys.argv[1]):n,x,y=L.split('"');N[x]=int(n);H[x]=0;X[x]=[]
for L in open(sys.argv[2]):s,t=eval(L);X[s]+=[t]
p=1
while p:
 p=0
 for x in N:
  if len(X[x])>N[x]:
   p=1;S=[y for y in X[x]if H[y]<H[x]]
   if S:X[x].remove(S[0]);X[S[0]]+=[x]
   else:H[x]+=1
   if H[x]>2*len(N):sys.exit(0)
for x in N:
 for y in X[x]:print'"%s", "%s", a'%(x,y)

```

This code uses a push-relabel-style maximum flow algorithm. `N[x]` is the number of parties allowed at `x`, `X[x]` is the list of partner cities currently scheduled to host at `x` (which may be longer than `N[x]` during the algorithm), and `H[x]` is the labelled height of `x`. For any oversubscribed city, we either push one of its scheduled parties to a lower partner city, or raise its height.
> 2 votes

# Answer
## C#, 1016 992 916 chars

Takes 4 seconds for me on the large test set; performance can easily be improved a lot by making `X` a `HashSet<s>` rather than a `List<s>`.

```
using System;using System.Collections.Generic;using System.IO;using System.Linq;using
s=System.String;class D<T>:Dictionary<s,T>{}class E:D<int>{static void Main(s[]x){s
S="",T=">",l;s[]b;D<E>R=new D<E>(),P=new D<E>();R[S]=new E();R[T]=new E();foreach(s L in
File.ReadAllLines(x[0])){b=L.Split('"');s f=b[1];R[T][f]=0;R[f]=new E();P[f]=new
E();R[f][T]=int.Parse(b[0].Trim());}foreach(s L in File.ReadAllLines(x[1])){b=L.Split('"');s
f=b[1],t=b[3],v=f+t;R[v]=new
E();R[v][S]=R[f][v]=R[t][v]=0;P[f][t]=R[S][v]=R[v][f]=R[v][t]=1;}for(;;){List<s>X=new
s[]{S}.ToList(),A=X.ToList();w:while((l=A.Last())!=T){foreach(s t in
R[l].Keys){if(!X.Contains(t)&R[l][t]>0){X.Add(t);A.Add(t);goto
w;}}A.RemoveAt(A.Count-1);if(!A.Any())goto q;}l=S;foreach(s n in
A.Skip(1)){R[l][n]--;R[n][l]++;l=n;}}q:if(R[S].Values.Contains(1))return;foreach(s
f in P.Keys)foreach(s t in P[f].Keys)Console.WriteLine(f+", "+t+", "+"ba"[R[f][f+t]]);}}

```

This uses the reduction to max flow which I hinted at earlier in comments. The vertices are

1. A newly generated source `S` and sink `T`.
2. The partnerships.
3. The cities.

The edges are

1. From the source to each partnership with flow capacity 1.
2. From each partnership to each city in the partnership with flow capacity 1.
3. From each city to the sink with flow capacity equal to that city's budget.

The algorithm is Ford-Fulkerson with DFS. It is obvious a priori that each augmenting path will increase the flow by 1, so the golfing optimisation of removing the computation of the path's flow has no negative effect on performance.

There are other possible optimisations by making assumptions such as "The names of the input files will never be the same as the names of the cities", but that's a bit iffy IMO.
> 2 votes

---
Tags: code-golf, graph-theory, restricted-time
---


# Question
Title: write a code the find n-th number of Gray Code list
Write a function that, given N \>= 0, finds the Nth number in a standard Gray code.

Example input:

```
1
2
3
4

```

Example output:

```
1
3
2
6

```

Additional reference

# Answer
> 4 votes
### Perl, 7 chars

```
$_^$_/2

```

This is an expression that returns the Gray code, given the input in `$_`. You can use it on the command line with the `-n` switch:

```
perl -nE 'say $_^$_/2'

```

or use it in a `map`:

```
perl -E 'say for map $_^$_/2, 1 .. 10'
1
3
2
6
7
5
4
12
13
15

```

If you specifically want a *function*, I can do that too (in 20 chars):

```
sub g{$_[0]^$_[0]/2}

```

---

**Edit:** Since this challenge is now tagged , let me include the equivalent C preprocessor macro, which should be about as fast as this can be done:

```
#define g(i) ((i)^(i)>>1)

```

A faster solution, if one exists, is likely to require hand-optimized assembly code. Even then, a good optimizing C compiler may be hard to beat. Looking at the disassembly of the benchmark code below, it seems gcc compiles this into three Intel assembly instructions:

```
 8048428:       89 c2                   mov    %eax,%edx
 804842a:       d1 ea                   shr    %edx
 804842c:       31 c2                   xor    %eax,%edx

```

This (a register copy, a shift and an XOR) is about what I'd expect any decent compiler to produce. Of course, a good compiler might also be able to interleave the operations with surrounding code to improve pipelining. (In the benchmark, the inner loop is tight enough that there's not much room for that.)

Testing just how fast this is can be a bit tricky, since we need to make sure the compiler won't just optimize away the Gray code calculation, or even the entire testing loop. Here's a piece of code that sums up all unsigned 32-bit integers eight times over, either in Gray code order or, if `NOGRAY` is defined, in normal binary order. Obviously, the output should be zero in either case, but at least gcc isn't smart enough to realize that.

```
#include <inttypes.h>
#include <stdio.h>

#ifdef NOGRAY
#  define g(i) (i)
#else
#  define g(i) ((i)^(i)>>1)
#endif

int main (void) {
    uint32_t k, i, n = 0;
    for (k = 0; k < 8; k++) {
        for (i = 1; i != 0; i++) n += g(i);
    }
    printf("%lu\n", (unsigned long) n);
    return 0;
}

```

On my 2.2GHz AMD Athlon 64 X2 CPU, compiled with gcc 4.4.3 with `-O3` for i486-linux-gnu, running this code takes about 46.9 seconds, compared to about 31.2 second with `NOGRAY` defined. That gives about 15.7 seconds for 235−8 Gray code calculations, which comes down to about 0.457 nanoseconds, or almost exactly **one CPU cycle** per calculation.

However, it's worth noting that that's the *marginal* cost of including the Gray code calculation in the loop. The total time to execute the benchmark loop (which includes two adds and a conditional jump in addition to the three lines of assembly I showed above) is about 1.365 nanoseconds, or three cycles per iteration.

# Answer
> 2 votes
### Golfscript, 4 chars

```
.2/^

```

# Answer
> 0 votes
### scala:

## It's not a code-golf!

However - if you like to golf:

```
def g(n:Int)=n^(n/2)

```

20 chars, according to my set of natural numbers.

But since speed matters, I produce a compilable form:

```
object Graycode extends App {

  def graycode (n: Int) = n^(n/2)

  def test (max: Int) {
    var i = 0
    val start = System.nanoTime ()
    while (i < max) {
      graycode (i)
      i += 1
    }
    val stop = System.nanoTime ()

    val diff = (stop-start)*1.0 / (1000*1000*1000)
    println ("Time: " + diff + "s\tn: " + max + "\tspeed: " + max * 1.0/diff + " /s")
  }

  override def main (args: Array[String]) = {
    var max = args(0).toInt
    val graycode = Graycode
    graycode.test (max)
  }
}

```

You can compare it against your solution this way:

```
scala Graycode 1000000000
Time: 23.882410496s n: 1000000000   speed: 4.1871820274066865E7 /s

```

About 4 million ints per second on my machine. If I comment out the call to graycode, I get as speed: 7.683713972447292E8 /s, so it is not mainly the time used to loop, which is measured above.

Of course your absolute times will vary, but you may compare it to measurements of your code. Please provide measurement methods with your solutions too.

---
Tags: code-challenge, fastest-code
---


title: Build a working chessboard

text:
# Question
Title: Build a working chessboard
## The challenge

Create a program that mimics a chessboard.

## The datails

The chessboard must be surrounded by the labels of each row and column, being the columns labeled from 'a' to 'h' and the rows labeled from '1' to '8'. Also, place the default position for each chess piece (blacks are on the top). Each piece is represented by the first letter of his name:

```
King = K
Queen = Q
Rook = R
Bishop = B
Knight = N
Pawn = P

```

Also by his colour

```
W = White
B = Black

```

So any given piece is recognized by his name and colour. E.G: NB = Black Knight. Empty squares are represented by a hyphen (-).

The program must show the chess board with the pieces. Then it should ask the user to make a move with the message "Move". The program must read user input by console or equivalent. We don't care if the move is legal or not. The program must reprint the chess board with the piece moved, deleting any piece it was on that square. The move is represented `origin square destination square`. E.g:

```
2c 5d = Moves the piece in square 2c to square 5d

```

If the program detects there is not piece in the origin square or an invalid input, it must show the message "Invalid move" and ask again for another move. If the program detects the final square is occuped by another piece it must show the message "\[Name of the moving piece\] x \[Name of the captured piece\]". Eg:

```
PB x KW

```

The program is intended to run in a loop, so after each user input the program will ask again for another move. There is no exit clause for the loop.

Example of a initial chessboard and first user's input and program's output:

```
-   a   b   c   d   e   f   g   h   -

8   RB  NB  BB  QB  KB  BB  NB  RB  8

7   PB  PB  PB  PB  PB  PB  PB  PB  7

6   -   -   -   -   -   -   -   -   6

5   -   -   -   -   -   -   -   -   5

4   -   -   -   -   -   -   -   -   4

3   -   -   -   -   -   -   -   -   3

2   PW  PW  PW  PW  PW  PW  PW  PW  2

1   RW  NW  BW  QW  KW  BW  NW  RW  1

-   a   b   c   d   e   f   g   h   -

Move
2a 4a

-   a   b   c   d   e   f   g   h   -

8   RB  NB  BB  QB  KB  BB  NB  RB  8

7   PB  PB  PB  PB  PB  PB  PB  PB  7

6   -   -   -   -   -   -   -   -   6

5   -   -   -   -   -   -   -   -   5

4   PW  -   -   -   -   -   -   -   4

3   -   -   -   -   -   -   -   -   3

2   -   PW  PW  PW  PW  PW  PW  PW  2

1   RW  NW  BW  QW  KW  BW  NW  RW  1

-   a   b   c   d   e   f   g   h   -

Move

```

# Answer
## Perl, 211 characters

```
y/W/B/for@8=@1=map$_.W,split//,RNBQKBNR;@b{$_.1..$_.9}=(@$_,/2/?PW:/7/?PB:"- ")x8for@r=reverse 1..8;$c=join"  ","",a..h;do{y/a-h\n/1-8/d;/ /;@b{$',$`}=@b{$`,19};say$c;say"$_ @b{$_.1..$_.8} $_"for@r;say$c}while<>

```

Nothing very unusual about this first attempt, except maybe the use of a `do`..`while` loop in golf. Uses `say`, so you need to run this with `perl -M5.01`. The input parsing is really klugy and fragile; in particular, excess whitespace will kill it. On the other hand, you're not constrained to use 1-8 for rows and a-h for columns, either will do. End the program with Ctrl-C or by ending the input (Ctrl-D in Unix).

I assumed I don't need to match the whitespace in the sample output exactly — I prefer a more compact board anyway. (I did keep the board orientation, even though flipping it upside down would save me eight chars.) A sample game session might look something like this:

```
  a  b  c  d  e  f  g  h
8 RB NB BB QB KB BB NB RB 8
7 PB PB PB PB PB PB PB PB 7
6 -  -  -  -  -  -  -  -  6
5 -  -  -  -  -  -  -  -  5
4 -  -  -  -  -  -  -  -  4
3 -  -  -  -  -  -  -  -  3
2 PW PW PW PW PW PW PW PW 2
1 RW NW BW QW KW BW NW RW 1
  a  b  c  d  e  f  g  h
2f 3f
  a  b  c  d  e  f  g  h
8 RB NB BB QB KB BB NB RB 8
7 PB PB PB PB PB PB PB PB 7
6 -  -  -  -  -  -  -  -  6
5 -  -  -  -  -  -  -  -  5
4 -  -  -  -  -  -  -  -  4
3 -  -  -  -  -  PW -  -  3
2 PW PW PW PW PW -  PW PW 2
1 RW NW BW QW KW BW NW RW 1
  a  b  c  d  e  f  g  h
7e 5e
  a  b  c  d  e  f  g  h
8 RB NB BB QB KB BB NB RB 8
7 PB PB PB PB -  PB PB PB 7
6 -  -  -  -  -  -  -  -  6
5 -  -  -  -  PB -  -  -  5
4 -  -  -  -  -  -  -  -  4
3 -  -  -  -  -  PW -  -  3
2 PW PW PW PW PW -  PW PW 2
1 RW NW BW QW KW BW NW RW 1
  a  b  c  d  e  f  g  h
2g 4g
  a  b  c  d  e  f  g  h
8 RB NB BB QB KB BB NB RB 8
7 PB PB PB PB -  PB PB PB 7
6 -  -  -  -  -  -  -  -  6
5 -  -  -  -  PB -  -  -  5
4 -  -  -  -  -  -  PW -  4
3 -  -  -  -  -  PW -  -  3
2 PW PW PW PW PW -  -  PW 2
1 RW NW BW QW KW BW NW RW 1
  a  b  c  d  e  f  g  h
8d 4h
  a  b  c  d  e  f  g  h
8 RB NB BB -  KB BB NB RB 8
7 PB PB PB PB -  PB PB PB 7
6 -  -  -  -  -  -  -  -  6
5 -  -  -  -  PB -  -  -  5
4 -  -  -  -  -  -  PW QB 4
3 -  -  -  -  -  PW -  -  3
2 PW PW PW PW PW -  -  PW 2
1 RW NW BW QW KW BW NW RW 1
  a  b  c  d  e  f  g  h
^C

```
> 4 votes

---
Tags: code-golf, chess
---


# Question
Title: using a Markov Chain, because this question itself as input text for example
Create a Markov Chain generator, which generates (and outputs) an Order 4 text chain. It must be able to support all plain text formatting used on this question, so be sure to check for punctuation (parentheses count for example, but HTML doesn't need to be accounted for fortunately)! You could even use this question itself as input if you're so inclined. There must be a defined input variable (or something analogous to such, I am aware certain popular esoteric languages do not really have variables per se.)

Your generator also should start sentences with a capital letter, and end with ".", "!", or "?", according to how often those respective characters appear in the input text.

You must also include a way to change the amount of text which should be output, so the only two things that are really configurable are the amount to output and the input string. It should stick with an Order 4 chain, because those happen to be funniest when it all comes down to it really.

Oh and, if your generators happen to create something particularly funny, please feel free to include it in your post for the lulz.

The title of this question was generated using a Markov Chain.

# Answer
## Perl, 108 chars

What, no answers? Here's a quick Perl solution:

```
$/=$,;$_=<>;push@$1,$2while/(?=(....)(.))/sg;print+($m)=/(....)/s;print while($m.=($_=$$m[rand@$m]))=~s/.//s

```

And this is what I got the first time I fed the question text through it:

> Create a defined. There must also inclined. There must be sure to be according a Markov Chain.

(The average output length should approximately match the input length, so such a short output is quite untypical. On the other hand, the output length is roughly exponentially distributed, so both very short and very long outputs are quite possible.)
> 3 votes

---
Tags: code-golf, markov-chain
---


title: Justify a text by adding spaces

text:
# Question
Title: Justify a text by adding spaces
Given this text

> Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

write the shortest program that produces the same text justified at 80 character. The above text must look exactly as:

```
Lorem ipsum dolor sit amet,  consectetur adipisicing elit, sed do eiusmod tempor
incididunt ut  labore et  dolore magna aliqua.  Ut  enim ad  minim veniam,  quis
nostrud exercitation ullamco laboris nisi ut  aliquip ex  ea  commodo consequat.
Duis aute irure dolor in  reprehenderit in voluptate velit esse cillum dolore eu
fugiat nulla pariatur.  Excepteur sint occaecat cupidatat non proident,  sunt in
culpa qui officia deserunt mollit anim id est laborum.

```

**Rules:**

* words must not be cut
* extra spaces must be added
    + after a dot.
    + after a comma
    + after the shortest word (from left to right)
    + the result must not have more than 2 consecutive spaces
* last line is not justified.
* lines must not begin with comma or dot.
* provide the output of your program

**winner:** The shortest program.

**note:** The input string is provided on STDIN as one line (no line feed or carriage return)

**update:**

The input string can be any text with word length reasonnable (ie. not more than 20~25 char) such as:

> Lorem ipsum dolor sit amet, consectetur adipiscing elit. Sed non risus. Suspendisse lectus tortor, dignissim sit amet, adipiscing nec, ultricies sed, dolor. Cras elementum ultrices diam. Maecenas ligula massa, varius a, semper congue, euismod non, mi. Proin porttitor, orci nec nonummy molestie, enim est eleifend mi, non fermentum diam nisl sit amet erat. Duis semper. Duis arcu massa, scelerisque vitae, consequat in, pretium a, enim. Pellentesque congue. Ut in risus volutpat libero pharetra tempor. Cras vestibulum bibendum augue. Praesent egestas leo in pede. Praesent blandit odio eu enim. Pellentesque sed dui ut augue blandit sodales. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia Curae; Aliquam nibh. Mauris ac mauris sed pede pellentesque fermentum. Maecenas adipiscing ante non diam sodales hendrerit. Ut velit mauris, egestas sed, gravida nec, ornare ut, mi. Aenean ut orci vel massa suscipit pulvinar. Nulla sollicitudin. Fusce varius, ligula non tempus aliquam, nunc turpis ullamcorper nibh, in tempus sapien eros vitae ligula. Pellentesque rhoncus nunc et augue. Integer id felis. Curabitur aliquet pellentesque diam. Integer quis metus vitae elit lobortis egestas. Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Morbi vel erat non mauris convallis vehicula. Nulla et sapien. Integer tortor tellus, aliquam faucibus, convallis id, congue eu, quam. Mauris ullamcorper felis vitae erat. Proin feugiat, augue non elementum posuere, metus purus iaculis lectus, et tristique ligula justo vitae magna. Aliquam convallis sollicitudin purus. Praesent aliquam, enim at fermentum mollis, ligula massa adipiscing nisl, ac euismod nibh nisl eu lectus. Fusce vulputate sem at sapien. Vivamus leo. Aliquam euismod libero eu enim. Nulla nec felis sed leo placerat imperdiet. Aenean suscipit nulla in justo. Suspendisse cursus rutrum augue. Nulla tincidunt tincidunt mi. Curabitur iaculis, lorem vel rhoncus faucibus, felis magna fermentum augue, et ultricies lacus lorem varius purus. Curabitur eu amet.

# Answer
## Perl, 94 chars

```
for(/(.{0,80}\s)/g){$i=1;$i+=!s/^(.*?\.|.*?,|(.*? )??\S{$i}) \b/$1  /until/
|.{81}/;chop;say}

```

Run with `perl -nM5.01`. (The `n` is included in the character count.)

The code above is the shortest I could make that could handle *any* curveballs I threw at it (such as one-letter words at the beginning of a line, input lines exactly 80 chars long, etc.) exactly according to spec:

```
Lorem ipsum dolor sit amet,  consectetur adipisicing elit, sed do eiusmod tempor
incididunt ut  labore et  dolore magna aliqua.  Ut  enim ad  minim veniam,  quis
nostrud exercitation ullamco laboris nisi ut  aliquip ex  ea  commodo consequat.
Duis aute irure dolor in  reprehenderit in voluptate velit esse cillum dolore eu
fugiat nulla pariatur.  Excepteur sint occaecat cupidatat non proident,  sunt in
culpa qui officia deserunt mollit anim id est laborum.

I'm  tempted to  provide a  php  program which consists of  the output text. ;-)
Seriously though,  the spaces on the second line of the output text seem to have
been added to  the spaces at  random? Is  there some pattern to  it that I'm not
seeing,  and if  not,  how can we be expected to produce exactly that output for
the given input?

```

(With apologies to Gareth for using his comment as additional test input.)

The following 75-char version works well enough to produce the sample output from the sample input, but can fail for other inputs. Also, it leaves an extra space character at the end of each the output line.

```
for(/(.{0,80}\s)/g){s/(.*?\.|.*?,|.*? ..) \b/$1  /until/.{81}/||s/
//;say}

```

Both versions will loop forever if they encounter input that they can't justify correctly. (In the longer version, replacing `until` with `until$i>80||` would fix that at the cost of seven extra chars.)
> 6 votes

# Answer
### Ruby, 146 characters

```
$><<gets.gsub(/(.{,80})( |$)/){$2>""?(s=$1+$/;(['\.',?,]+(1..80).map{|l|"\\b\\w{#{l}}"}).any?{|x|s.sub! /#{x} (?=\w)/,'\& '}while s.size<81;s):$1}

```

It prints exactly the desired output (see below) if the given text is fed into STDIN.

```
Lorem ipsum dolor sit amet,  consectetur adipisicing elit, sed do eiusmod tempor
incididunt ut  labore et  dolore magna aliqua.  Ut  enim ad  minim veniam,  quis
nostrud exercitation ullamco laboris nisi ut  aliquip ex  ea  commodo consequat.
Duis aute irure dolor in  reprehenderit in voluptate velit esse cillum dolore eu
fugiat nulla pariatur.  Excepteur sint occaecat cupidatat non proident,  sunt in
culpa qui officia deserunt mollit anim id est laborum.

```

*Edit:* Just after submitting my first solution I saw in the comments that it is required that any input string can be processed. The previous answer was only 95 characters but did not fulfill this requirement:

```
r=gets.split;l=0;'49231227217b6'.chars{|s|r[l+=s.hex]+=' '};(r*' ').gsub(/(.{,80}) ?/){puts $1}

```
> 2 votes

---
Tags: code-golf, typography
---


title: 1P5: Earthquake!

text:
# Question
Title: 1P5: Earthquake!
USGS's seismometers have just detected a major earthquake! Emergency response teams need a quick estimate of the number of people affected. Write a program to compute this estimate.

Your program receives 2 inputs. The first is the details of the earthquake itself. The earthquake modeled as a line segment along which the earth ruptured, along with the critical distance from the fault within which damage could be expected. The second input is a list of the location and population of cities in the area. Your program should compute the number of people living in the affected area, that is the sum of the population of all cities within the critical distance of the fault segment.

## Input

First a line describing the earthquake, containing the x,y coordinates of the start and end points of the fault, plus the critical distance. The format is `A_x A_y B_x B_y D`. For example:

```
3.0 3.0 7.0 4.0 2.5

```

encodes the fault extending from (3.0,3.0) to (7.0,4.0) and a critical distance of 2.5.

Second, one line per city in the area, containing the x,y coordinates of the city and its population. For example:

```
1.0 1.0 2500
5.0 7.0 8000
3.0 4.0 7500
9.0 6.0 3000
4.0 2.0 1000

```

## Output

The number of people living in the affected area. For the above example only the third and fifth cities are in the danger area, so the output would be

```
8500

```

Shortest code wins.

### Example 2

```
0.0 0.0 10.0 0.0 5.0
5.0 4.0 10000
5.0 -4.0 1000
5.0 6.0 100
11.0 2.0 10
-4.0 4.0 1

```

generates

```
11010

```

# Answer
## Ruby, 171 152 155 153

```
u,v,a,b,d=gets.split.map &:to_f
a-=u;b-=v
p eval$<.map{|l|"(x=%f-u;t=(a*x+b*y=%f-v)/(a*a+b*b);d*d<(x-a*t=t<0?0:t>1?1:t)**2+(y-t*b)**2?0:%d)"%l.split}*'+'

```

This is my first ruby submission and my first code-golf at all. Straight forward implementation of the task. Please give me some hints how to improve (there must be a shorter way to read floats...).
> 11 votes

# Answer
### C# - 743 715

```
namespace System{using Linq;using m=Math;class P{public float X,Y;}class E{static void Main(){Func<string,float>p=s=>float.Parse(s);Func<P,P,double>d=(a,b)=>{return a.X*b.X+a.Y*b.Y;},c=(a,b)=>{return a.X*b.Y-a.Y*b.X;};Func<P,P,P>u=(a,b)=>{return new P{X=a.X-b.X,Y=a.Y-b.Y};};Func<P,P,P,double>g=(A,B,C)=>{return d(u(C,B),u(B,A))>0?m.Sqrt(d(u(B,C),u(B,C))):d(u(C,A),u(A,B))>0?m.Sqrt(d(u(A,C),u(A,C))):m.Abs(c(u(B,A),u(C,A))/m.Sqrt(d(u(B,A),u(B,A))));};var n=IO.File.ReadAllLines("i");var i=n[0].Split();var q=new{A=new P{X=p(i[0]),Y=p(i[1])},B=new P{X=p(i[2]),Y=p(i[3])},D=p(i[4])};Console.WriteLine((from l in n.Skip(1)let f=l.Split()let w=new P{X=p(f[0]),Y=p(f[1])}where g(q.A,q.B,w)<q.D select p(f[2])).Sum());}}}

```

Non-Golfed:

```
namespace System
{
    using Linq;
    using m = Math;
    class Point { public float X, Y;}
    class Earthquake
    {
        static void Main()
        {
            Func<string, float> parse = s => float.Parse(s);
            Func<Point, Point, double> dotProduct = (a, b) => { return a.X * b.X + a.Y * b.Y; },
                                       crossProduct = (a, b) => { return a.X * b.Y - a.Y * b.X; };
            Func<Point, Point, Point> subtract = (a, b) => { return new Point { X = a.X - b.X, Y = a.Y - b.Y }; };
            Func<Point, Point, Point, double> getDistance = (A, B, C) => {
                return dotProduct(subtract(C, B), subtract(B, A)) > 0 ?
                        m.Sqrt(dotProduct(subtract(B, C), subtract(B, C))) :
                        dotProduct(subtract(C, A), subtract(A, B)) > 0 ?
                            m.Sqrt(dotProduct(subtract(A, C), subtract(A, C))) :
                            m.Abs(crossProduct(subtract(B, A), subtract(C, A)) / m.Sqrt(dotProduct(subtract(B, A), subtract(B, A))));
            };
            var inputLines = IO.File.ReadAllLines("i");
            var quakeLine = inputLines[0].Split();
            var quake = new {
                PointA = new Point { X = parse(quakeLine[0]), Y = parse(quakeLine[1]) },
                PointB = new Point { X = parse(quakeLine[2]), Y = parse(quakeLine[3]) },
                Distance = parse(quakeLine[4])
            };
            var affectedPopulations = (from line in inputLines.Skip(1)
                                       let fields = line.Split()
                                       let location = new Point { X = parse(fields[0]), Y = parse(fields[1]) }
                                       let population = parse(fields[2])
                                       where getDistance(quake.PointA, quake.PointB, location) < quake.Distance
                                       select population);
            Console.WriteLine(affectedPopulations.Sum());
        }
    }
}

```
> 4 votes

# Answer
## Javascript (437)

This can probably be golfed significantly, but not enough to beat the Ruby solution.

```
p=$("#i").text().split("\n");for(i=0;i<p.length;i++){p[i]=p[i].split(" ")}
z=p[0];a=z[0];b=z[1];c=z[2];d=z[3];e=z[4];o=0;f=[a,b];g=[c,d];
function q(r,s){return Math.sqrt(Math.pow(s[0]-r[0],2)+Math.pow(s[1]-r[1],2))}
for(i=1;i<p.length;i++){w=p[i];u=((w[0]-a)*(c-a)+(w[1]-b)*(d-b))/Math.pow(q(f,g,2),2);
x=[(a*1)+u*(c-a),(b*1)+u*(d-b)];l=e;m=w[2]*1;u=w[0];w=w[1];v=[u,w];
o+=q(v,x)<l&&q(x,g)+q(x,f)==q(f,g)?m:q(v,f)<l?m:q(v,g)<l?m:0}alert(o);

```

You can see it in action here.
> 4 votes

# Answer
## c -- 471 characters

```
#include <stdio.h>
#define F float
#define G getline(&v,&l,stdin)
F a[2],b[2],c[2],d[2],e[2],r,t,y,z;char*v;size_t l,n,p;
F s(F u[2],F v[2]){y=u[0]-v[0];z=u[1]-v[1];return y*y+z*z;}
j(F g[2],F h[2],F i[2]){*i=*g-*h;i[1]=g[1]-h[1];}
int i(){j(b,a,d);j(c,a,e);t=*d**e+d[1]*e[1];
return s(a,c)<=r||s(b,c)<=r||t>0&&t/s(a,b)<=1&&s(a,c)-t*t/s(a,b)<=r;}
int main(){G;sscanf(v,"%f %f %f %f %f",a,a+1,b,b+1,&r);r*=r;
while(G!=-1)sscanf(v,"%f %f %i",c,c+1,&p),n+=p*i();printf("%d\n",n);}

```

It assumes your standard library has `getline`.

The method is clarified a bit in the comment to the ungolfed version:

```
#include <stdio.h>

float a[2],b[2],c[2],d[2],e[2],r,t,y,z;
char*v;
size_t l,n,p;
float s(float u[2],float v[2]){ /* returns the square of the distance
                   between two points */
  y=u[0]-v[0];
  z=u[1]-v[1];
  return y*y+z*z;
}
j(float g[2],float h[2],float i[2]){ /* sets i=g-h */
  i[0]=g[0]-h[0];
  i[1]=g[1]-h[1];
}
int i/*sCLose*/(){
  j(b,a,d); /* d=b-a */
  j(c,a,e); /* e=c-a */
  t=d[0]*e[0]+d[1]*e[1]; /* dot product */
  return
    (s(a,c)<=r) || /* near one end point */
    (s(b,c)<=r) || /* near the other */
    (
     (t>0) && /* C lies more "towards" B than away */
     (t/s(a,b)<=1) && /* Nearest point on AB to C lies between A and B */
     (s(a,c)-t*t/s(a,b)<=r) /* length of the altitude less than R */
       );
}
int main(){
  getline(&v,&l,stdin);
  sscanf(v,"%f %f %f %f %f",a,a+1,b,b+1,&r);
  r*=r; /* r is now r squared, as that is the only way we use it */
  printf("(%f, %f); (%f, %f): %f\n",a[0],a[1],b[0],b[1],r);
  while (getline(&v,&l,stdin) != -1){
    sscanf(v,"%f %f %i",c,c+1,&p);
    printf("\t (%f, %f): %d\n",c[0],c[1],p);
    n+=p*i/*sClose*/();
  }
  printf("%d\n",n);
}

```
> 2 votes

# Answer
### scala: 660 chars:

```
object E extends App{
type I=Int
type D=Double
def b(h:D,i:D,x:I,y:I,d:D)=(x-h)*(x-h)+(y-i)*(y-i)<=d*d
def a(p:java.awt.Polygon,x:I,y:I,h:I,i:I,d:D,r:Array[String])={
val w=r(0).toDouble
val j=r(1).toDouble
val n=r(2).toInt
if (p.contains(w,j)||b(j,w,x,y,d)||b(j,w,i,h,d))n
else 0}
val s=new java.util.Scanner(System.in)
val b=s.nextLine.split(" ")
val c=b.map(_.toDouble)
val e=c.map(_.toInt)
val(x,h,y,i,d)=(e(0),e(2),e(1),e(3),c(4))
val f=List(x,h)
val g=List(y,i)
val p=new java.awt.Polygon((f:::f.reverse).toArray,(g.map(_-e(4)):::g.reverse.map(_+e(4))).toArray,4)
var r=0
while(s.hasNext){
val row=s.nextLine
r+=a(p,x,y,h,i,d,row.split(" "))}
println(r)}

```

ungolfed:

```
object Earthquake extends App {

  def bowContains (h: Double, i: Double, x:Int, y:Int, d: Double) : Boolean = {
    (x-h)*(x-h) + (y-i)*(y-i) <= d*d
  }

  import java.awt._

  def affected (polygon: Polygon, x:Int, y:Int, h: Int, i: Int, d: Double, row: Array[String]) : Int = {
    val w = row (0).toDouble
    val j = row (1).toDouble
    val population = row (2).toInt
    if (polygon.contains (w, j) || bowContains (j, w, x, y, d) || bowContains (j, w, i, h, d))
      population
    else 0
  }
  val sc = new java.util.Scanner (System.in)
  val line = sc.nextLine.split (" ")

  val li = line.map (_.toDouble)
  val ll = li.map (_.toInt)

  val (x, h, y, i, d) = (ll (0), ll (2), ll (1), ll (3), li(4))
  val xs = List (x, h)
  val ys = List (y, i)

  val polygon = new Polygon ((xs ::: xs.reverse).toArray, (ys.map (_ - ll(4)) ::: ys.reverse.map (_ + ll(4))).toArray, 4)
  var res = 0
  while (sc.hasNext) {
    val row = sc.nextLine
    println ("line: " + line)
    res += affected (polygon, x, y, h, i, d, row.split (" "))
  }
  println (res)
}

```
> 0 votes

---
Tags: code-golf, math, 1p5
---


# Question
Title: A small puzzle. Why does this code work the way it does?
This was given to me by a friend of mine, it prints out 0 through 9. We have been quite puzzled over this. Does anyone know why this works?

```
#include <iostream>

using namespace std;

void x(int a)
{
    *(&a-1) += a;
}

int main()
{
    for(int i = 0; i < 10; ++i)
    {
        x(8);
        i = 0;
        cout << i << endl;
    }
}

```

# Answer
> 11 votes
First of all, the line `*(&a-1) += a;` is undefined behavior, so this could do anything depending on compiler version, flags used, alignment of the stars, etc.

That said, the reason why it works in your case is probably because `&a-1` happens to point to the return address of `x`, and incrementing it by `8` causes the `i = 0;` to be skipped.

# Answer
> 4 votes
The reason this works is because your compiler passes the `a` parameter on the stack. Before the parameter, the code pushes the return address of the method onto the stack:

```
004A0008 | 00000008 ; a parameter
004A0004 | 00401200 ; return addr
004A0000 | ...

```

The `&a` part of the expression points to the *address* of the parameter on the stack, in this case I've used `004A0008`. The `a-1` then subtracts `sizeof(int)` from that address, giving you `004A0004`. The `*` dereferences that address, so its value can be edited. This means that when you add 8 to the value at `004A0004`, it alters the return address. When the method returns, it ends up 8 bytes ahead of where it should have been, skipping the `i=0`.

---
Tags: c++
---


# Question
Title: I used to solve code golf puzzles like you, but then I took an arrow in the knee
Getting hit in the knee with arrows seems to be the injury of choice right now. As such, I propose the following golf challenge.

You have an adventurer that looks like this:

```
  O
 /|\
/ | \
  |
  |
 / \
/   \

```

Given a text file that contains one bow (drawn as a `}` symbol), a set of walls (drawn as `#` symbols) and one adventurer, write the smallest code that calculates the angle and initial velocity at which you should fire an arrow in order to hit him in the knee.

Assume the following:

* Each character in the file is 0.5 x 0.5 meters.
* The arrow is fired from the center of the `}`, i.e. an offset of `0.25m, 0.25m`
* Gravity is `10ms^-2`
* Arrow weighs `0.1kg`
* Arrow is a point, i.e. collisions only occur when the arrow's coordinate enters one of the blocks.
* Maximum initial velocity is `50m/s`
* Angle may be between 0 (straight up) and 180 (straight down)
* Hitting any part of the adventurer's leg is considered a hit to the knee.
* A wall (`#` character) takes up one entire 0.5m x 0.5m block.
* The arrow can travel over the "top" of the file, but there's nothing to stop the input from starting with a ceiling of `#` characters.
* You can't penetrate walls with arrows.
* Hitting any other part of the adventurer is not allowed!
* You should display an error if hitting him in the knee is impossible.

Example input:

```
                                 #
}                                                     O
                        #                            /|\
                                                    / | \
            #                                         |
                            #                         |
                                                     / \
                                                    /   \

```

Feel free to ask questions if you need to :)

# Answer
## Python, 599 chars

```
import os,sys
from math import*
I=os.read(0,999)
O=[]
h=v=0
for i in I:
 if'#'==i:O+=[(h,v,h+1,v+1),(h+1,v,h,v+1)]
 if'O'==i:O+=[(h,v+1,h-2,v+3)];T=(h,v+5,h-2,v+7)
 if'}'==i:e=h+.5;c=v+.5
 h+=1
 if'\n'==i:v+=1;h=0

def X(K,L):
 A,B,C=K;p=L[0];q=L[2]-p;r=L[1];s=L[3]-r;A,B,C=A*q*q,2*A*p*q+B*q-s,A*p*p+B*p+C-r;d=B*B-4*A*C
 return 0 if d<0 else any(0<x<1 for x in[(sqrt(d)-B)/2/A,(-sqrt(d)-B)/2/A])

R=range(1,999)
for v in R:
 for z in R:
  z*=pi/999;d=v*sin(z)/10;b=-v*cos(z)/10
  K=20/d/d,b/d-40*e/d/d,c+20*e*e/d/d-b*e/d
  if X(K,T)and not any(X(K,x)for x in O):print v/2,z;sys.exit(0)
print'ERROR'

```

The `X(K,L)` routine takes a parabola `K=(a,b,c)` representing *y=ax^2+bx+c* and a line segment `L=(a,b,c,d)` representing the segment between *(a,b)* and *(c,d)*. Both obstacles (`O`) and the target (`T`) are repesented as line segments. All distances are scaled by a factor of 2.

The example input gives the following trajectory (by default, the minimum velocity one):

```
  --                             #          --
--                                            -       O
                        #                      -     /|\
                                                -   / | \
            #                                    -    |
                            #                     -   |
                                                   - / \
                                                    -   \

```

you can reverse `R` to get the maximum velocity path:

```
                                 #
-------------                                         O
             -----------#                            /|\
                        --------                    / | \
            #                   -------               |
                            #          -----          |
                                            -----    / \
                                                 -----  \

```
> 11 votes

---
Tags: code-golf, path-finding
---


title: Write a better BCS computer ranking

text:
# Question
Title: Write a better BCS computer ranking
# Input

A CSV file, read from standard input, containing the 2011 college football scores with the 4 columns: Winner, Winner Score, Loser, Loser Score. For example,

```
Cincinnati,35,Connecticut,27
Pittsburgh,33,Syracuse,20
Baylor,48,Texas,24

```

This file was generated by a script I have that screen-scrapes rivals.yahoo.com. Teams that played fewer than 3 games were omitted.

# Output

Print to standard output a newline-separated ranking of teams, ordered from "best" to "worst".

It is permitted to output a "truncated" ranking (e.g., Top 25 or Top 50), but this is discouraged.

# Scoring

The ranking produced by your program will be scored on its ability to predict the winners of bowl games.

A victory for Team A over Team B is considered "predicted" by your ranking if either:

* You ranked Team A higher than (i.e., earlier in the output than) Team B.
* You ranked (i.e., listed anywhere in the output) Team A but not Team B.

You get 1 point for each bowl game "predicted" by your ranking.

Highest score gets the accepted answer. In case of a tie, the earliest submission wins.

# Rules

* Deadline for entries is **Friday, December 16**, at 17:00 CST (23:00 UTC).
* You may use the language of your choice.
* You may use third-party open-source math libraries such as SciPy.
* You may submit multiple entries.
* The output must be a pure function of the input. (So if you need an arbitrary tiebreaker in your ranking, don't use `rand()`, use alphabetical order.)

# Scores: It's a tie!

(Based on results from rivals.yahoo.com)

**dan04: 11 points**

* Auburn \> Virginia
* Baylor \> Washington
* Boise St. \> Arizona St.
* Oklahoma \> Iowa
* Oklahoma St. \> Stanford
* Oregon \> Wisconsin
* South Carolina \> Nebraska
* Southern Miss \> Nevada
* TCU \> Louisiana Tech
* Texas \> California
* Texas A&M \> Northwestern

**AShelly: 11 points**

* Arkansas \> Kansas St.
* Baylor \> Washington
* Boise St. \> Arizona St.
* Cincinnati \> Vanderbilt
* Houston \> Penn St.
* Michigan \> Virginia Tech
* Oklahoma St. \> Stanford
* Rutgers \> Iowa St.
* South Carolina \> Nebraska
* Southern Miss \> Nevada
* TCU \> Louisiana Tech

# Answer
I'll give it a shot. Here's some ugly Ruby that bases its ranking on how well each team scored compared to the opponent's average points against. It weights scores based on the opponent's rank in the list, and iterates until it is stable.

```
class Team
  attr_accessor :wins,:loss,:for,:agn,:rank,:old_rank
  attr_reader :beat,:fell, :name
  def initialize nm
    @name = nm
    @wins=0
    @loss=0
    @for = 0
    @agn = 0
    @beat = []
    @fell  = []
  end
  def win pts,opp,opts
    @wins+=1
    @for+=pts
    @agn+=opts
    @beat << [opp,pts,opts]
  end
  def lose pts,opp,opts
    @loss+=1
    @for+=pts
    @agn+=opts
    @fell << [opp,pts,opts]
  end
  def avgPtsFor
    @for.to_f/(@wins+@loss)
  end
  def avgPtsAgn
    @agn.to_f/(@wins+@loss)
  end
  def score teams
    #most points for scoring above opponents average, scaled by opponent's rank.
    x = @beat.inject(0){|sum,game|opp = teams[game[0]]
      sum+(game[1]/opp.avgPtsAgn*(1-(opp.rank/teams.size)))/@beat.size
      }
    y = @fell.inject(0){|sum,game|opp = teams[game[0]];
      sum+(game[1]/opp.avgPtsAgn*(opp.rank/teams.size))/@fell.size
      }
    (x+y)*(@wins/@loss.to_f)++(@rank/teams.size)/8
  end

end

#read the file
teams = Hash.new
ARGF.each_line{|l|
  result = l.split(',')
  team = teams[result[0]]||Team.new(result[0])
  team.win(result[1].to_i,result[2],result[3].to_i)
  teams[result[0]]=team
  team = teams[result[2]]||Team.new(result[2])
  team.lose(result[3].to_i,result[0],result[1].to_i)
  teams[result[2]]=team
}
#initial ranking by w/l,pts for, pts against
rankings = teams.map{|n,t|t}.sort_by{|t|[t.wins.to_f/t.loss,t.for,t.agn]}
rankings.each_with_index{|a,i|a.rank = (i+1.0)}

#loop
stable = false
loops = 0
while !stable and loops < 1000 do
  stable = true
  n = rankings.size.to_f
  rankings = rankings.sort_by{|t|
  t.score(teams)
  }
  rankings = rankings.each_with_index{|t,i|
    t.old_rank = t.rank
    t.rank = (i+1.0)
    stable = false if (t.rank != t.old_rank)
  }
  loops+=1
end

i=0
puts rankings.reverse.map{|t|"#{i+=1}: "+t.name}

```

Here's the output:

```
1: Oklahoma St.
2: LSU
3: Boise St.
4: Houston
5: Stanford
6: Oregon
7: Alabama
8: Arkansas
9: Wisconsin
10: TCU
11: Michigan
12: Georgia
13: South Carolina
14: Arkansas St.
15: Southern Miss
16: Michigan St.
17: West Virginia
18: Baylor
19: USC
20: Georgia Tech
21: Clemson
22: Tulsa
23: BYU
24: Oklahoma
25: Kansas St.
26: Nebraska
27: Virginia Tech
28: Penn St.
29: Notre Dame
30: Cincinnati
31: Northern Illinois
32: LA Lafayette
33: San Diego St.
34: Toledo
35: Florida Intl.
36: Texas A&M
37: Louisiana Tech
38: Ohio
39: Florida St.
40: North Carolina
41: Nevada
42: Iowa
43: Temple
44: Washington
45: West. Kentucky
46: Rutgers
47: Air Force
48: Auburn
49: Wyoming
50: California
51: Texas
52: Ohio St.
53: W. Michigan
54: Virginia
55: Utah St.
56: Florida
57: Missouri
58: Northwestern
59: SMU
60: Vanderbilt
61: Mississippi St.
62: Pittsburgh
63: Ball St.
64: Louisville
65: Purdue
66: East Carolina
67: UCLA
68: Wake Forest
69: Marshall
70: North Texas
71: N.C. State
72: Arizona St.
73: Utah
74: South Florida
75: Hawaii
76: San Jose St.
77: Texas Tech
78: Illinois
79: Kent St.
80: UTEP
81: UCF
82: Tennessee
83: East. Michigan
84: Connecticut
85: Navy
86: Duke
87: Rice
88: New Mexico St.
89: LA Monroe
90: Washington St.
91: Bowling Green
92: Kentucky
93: Syracuse
94: Arizona
95: Fresno St.
96: Troy
97: Oregon St.
98: Army
99: Colorado
100: Iowa St.
101: UNLV
102: UAB
103: Buffalo
104: Middle Tenn. St.
105: Minnesota
106: Boston Coll.
107: Cent. Michigan
108: Colorado St.
109: Mississippi
110: Tulane
111: Florida Atlantic
112: Memphis
113: Idaho
114: Kansas
115: New Mexico
116: Indiana
117: Maryland
118: Akron

```
> 2 votes

# Answer
Here's an example program. It assigns each team a rating equal to the least-squares solution of `winner_rating - loser_rating = 1` across all games:

```
import sys
import csv
from scipy import linalg

def read_csv(input_file):
    """Return a list of (winner, loser) tuples from the CSV file."""
    return [(row[0], row[2]) for row in csv.reader(input_file)]

def lstsq_ratings(data):
    """
    data = a list of (team1, team2, margin) tuples.
    Returns a dictionary of {team: rating}
    """
    # Extract the team names from the data
    teams = set()
    for winner, loser in data:
        teams.add(winner)
        teams.add(loser)
    teams = sorted(teams)
    team_indices = dict(zip(teams, xrange(len(teams))))
    # Construct the matrix equation for the teams
    num_teams = len(teams)
    lhs = []
    rhs = []
    for winner, loser in data:
        rhs.append(1)
        lhs_row = [0] * num_teams
        lhs_row[team_indices[winner]] = 1
        lhs_row[team_indices[loser]] = -1
        lhs.append(lhs_row)
    # Solve equation and return results
    ratings = linalg.lstsq(lhs, rhs)[0]
    return dict((team, rating) for team, rating in zip(teams, ratings))

if __name__ == '__main__':
    ratings = lstsq_ratings(read_csv(sys.stdin))
    output = sorted(ratings.items(), key=lambda x: (-x[1], x[0].lower()))
    for team, rating in output:
        print(team)

```

The output is:

```
Oklahoma St.
LSU
Alabama
Oklahoma
Stanford
Oregon
Baylor
Arkansas
South Carolina
Kansas St.
USC
Georgia
Wisconsin
Virginia Tech
Boise St.
Houston
Michigan
Nebraska
Texas
Texas A&M
Michigan St.
Missouri
Clemson
Penn St.
Auburn
TCU
Notre Dame
West Virginia
Southern Miss
Georgia Tech
Arkansas St.
North Carolina
Iowa
Tulsa
Washington
Cincinnati
California
Mississippi St.
Florida
Rutgers
Utah
BYU
UCLA
Florida St.
LA Lafayette
Northern Illinois
Ohio St.
Louisville
Texas Tech
San Diego St.
Vanderbilt
Arizona St.
Iowa St.
Tennessee
West. Kentucky
Virginia
Louisiana Tech
Illinois
Wyoming
Kentucky
Purdue
Toledo
Marshall
Pittsburgh
Arizona
N.C. State
Florida Intl.
Wake Forest
SMU
Northwestern
Ohio
Nevada
South Florida
Air Force
Utah St.
Oregon St.
Kansas
Syracuse
W. Michigan
North Texas
Temple
East Carolina
Ball St.
Washington St.
Kent St.
Colorado
Minnesota
Connecticut
Rice
Navy
Duke
East. Michigan
San Jose St.
Mississippi
UTEP
UCF
Hawaii
LA Monroe
Fresno St.
Bowling Green
New Mexico St.
Boston Coll.
Troy
UNLV
Army
UAB
Colorado St.
Cent. Michigan
Indiana
New Mexico
Middle Tenn. St.
Buffalo
Florida Atlantic
Maryland
Idaho
Memphis
Tulane
Akron

```
> 1 votes

---
Tags: code-challenge
---


title: ASCII animated snow scene

text:
# Question
Title: ASCII animated snow scene
Write the shortest program to turn any piece of ASCII art into an animated snow scene that begins to form from the falling snow (**non-golfed JavaScript example** last updated 2011-12-19).

**Input specification**: Your program must accept arbitrary combinations of spaces, asterisks, and newlines. The input will contain at most 23 lines and 80 characters per line. There will be no empty lines, yet lines may consist of only whitespace. A single trailing newline will be included and must be ignored.

**Output**: Output ASCII characters (spaces, asterisks) and control codes (carriage returns, linefeeds, ANSI escape codes, etc.) for your operating system's text console or terminal emulator until the user manually terminates the program. You may assume the terminal window is 80x24 characters if your operating system allows that setting.

**Rules**:

* The animation must be smooth and fast (15 fps preferred).
* Snow density must be between 5% and 15%.
* No more than one screen of snow may scroll per second. (That means no more than 24 lines of new snow may be added in any one second time period.)
* The snow must not display any obvious pattern as it enters the top of the screen; it must look random.
* The program must fill all rows of the screen with snow as quickly as possible when it starts; initial filling of the screen's individual rows must not be obvious to the viewer.
* The lower left corner of the input ASCII art must be at the lower left corner of the screen (Figure 1 for further clarification).
* The area inside or under the ASCII art must not be permanently filled with asterisks. However, asterisks may (but are not required to) scroll through this area.
* Snow must not accumulate at the bottom of the screen or on top of existing snow except as shown in the input.
* Lower spaces must be filled before upper ones, as filling spaces in the opposite order makes the Christmas tree animation look very different from my original code's output. (added 2011-12-20)

Happy holidays!

## Figure 1: labeled areas of an 80x24 screen

```
---------------------------New snow added on this line--------------------------
                                                                             |
                                                                             |
----------------------------------------------------------+                  |
                                                    ****  |                  |
    Snow MUST fall  Snow MAY fall ---------------->  **** |                  |
    through this    through these          ****      **** |  Snow MUST fall  |
    area.           areas of a              ****     **** |  through this    |
                    completed   \--------->  ****     ****|  area.           |
        ASCII art   scene.    \     ***        ****   ****|                  |
          area         \       \   *******      ****  ****|                  |
                        \       \    ********     ***  ***|  (ALL CAPS terms |
      (located in        \       \-->   *********  ***    |  have standard   |
       lower left         \     *******     ******  MAY   |     RFC 2119     |
       corner of           \    *************  **   fall  |    meanings.)    |
       screen)              \        ***********    here  |                  |
                         *** +--->          ****  ***     |                  |
                         *** | ****************   ***     |                  |
  | Snow MUST fall       *** | ****************   ***     |                  |
  | through this         *** +--->                ***     |                  |
  | area.                *** | ****************   ***     |                  |
--+---------------------+*** +--->                ***+----+------------------+--
  |   Snow MUST NOT     |****************************|      Snow MUST NOT    |
  V  accumulate here.   |****************************|     accumulate here.  V

```

## Example inputs

### Code Golf Banner

```
 ******   *******  ********  ********     ******    *******  **       ********
**    ** **     ** **     ** **          **    **  **     ** **       **
**       **     ** **     ** **          **        **     ** **       **
**       **     ** **     ** ******      **   **** **     ** **       ******
**       **     ** **     ** **          **    **  **     ** **       **
**    ** **     ** **     ** **          **    **  **     ** **       **
 ******   *******  ********  ********     ******    *******  ******** **

```

### Stack Overflow Logo

```
                                                    ****
                                                     ****
                                           ****      ****
                                            ****     ****
                                             ****     ****
                                    ***        ****   ****
                                   *******      ****  ****
                                     ********     ***  ***
                                        *********  ***
                                *******     ******
                                *************  **
                                     ***********
                         ***                ****  ***
                         ***   ****************   ***
                         ***   ****************   ***
                         ***                      ***
                         ***   ****************   ***
                         ***                      ***
                         ****************************
                         ****************************

```

### Christmas Trees

```
                                        *
                                       ***                           *
                *                     *****                         ***
               ***                   *******           *           *****
              *****                 *********         ***            *
                *                  ***********       *****
                       *          *************     *******
        *             ***        ***************       *               *
       ***           *****      *****************                     ***
      *****         *******    *******************                   *****
     *******           *      *********************                 *******
    *********                           *                          *********
        *                                                              *

```

# Answer
## Perl, 196 / 239 chars

```
chomp(@p=(@f=($"x80)x24,<>)[-24..-1]);{@s=(join("",map rand>.1?$":"*",1..80),@s);if(@s>23){$t=$f[$_],print$_?$/:"\e[H",($f[$_]|=$s[$_]&$p[$_])|($s[$_]&=~$t^$f[$_])for 0..23;select"","","",.1}redo}

```

This solution differs from your JS example in that the pattern is filled from top down rather than from bottom up, but I assume that's OK since you didn't say anything about it in the rules.

A trivial 1-char reduction can be obtained by replacing `\e` with a literal ESC character, but that makes the code much harder to read and edit.

---

**Update:** I *did* manage to come up with a version that fills the pattern from bottom up, and doesn't allow snow to fall through the filled parts of the pattern, as in the example JS implementation, at the cost of 43 extra chars:

```
chomp(@p=(@q=@f=($"x80)x24,<>)[-24..-1]);{@s=(join("",map rand>.1?$":"*",1..80),@s);if(@s>23){my$q;$q[-1-$_]=($q|=$p[-$_]&~$f[-$_])for@a=0..23;print$_?$/:"\e[H",($f[$_]|=$s[$_]&$p[$_]&~$q[$_])|($s[$_]&=~$f[$_])for@a;select"","","",.1}redo}

```

Replacing `($s[$_]&=~$f[$_])` with just `$s[$_]` would save 11 chars by letting falling snow pass through the filled parts of the pattern (which matches the spec, but not the example implementation).

---

OK, since I still seem to be leading the race after a week, I guess I should explain how my solution works to encourage more competition. (Note: This explanation is for the 196-char top-down filling version. I may amend it to include the other version later.)

First of all, the one big trick my solution is based on is that, due to the way ASCII character codes are arranged, the 1-bits in the ASCII code for a space just happen to be a subset of those in the code for an asterisk.

Thus, the following expressions are true: `" " & "*" eq " "` and `" " | "*" eq "*"`. This is what lets me use bitwise string operations for combining the static and moving parts of the scene without having to loop over individual characters.

So, with that out of the way, let's go over the code. Here's a de-golfed version of it:

```
chomp(@p = (@f = ($" x 80) x 24, <ARGV>)[-24..-1]);
{
    @s = (join('', map((rand > 0.1 ? $" : '*'), 1..80)), @s);
    if (@s > 23) {
        foreach (0 .. 23) {
            $t = $f[$_];
            print( $_ ? $/ : "\e[H" );
            print( ($f[$_] |= $s[$_] & $p[$_]) | ($s[$_] &= ~$t ^ $f[$_]) );
        }
        select '', '', '', 0.1;
    }
    redo;
}

```

The first line sets up the arrays `@f` (for "fixed") and `@p` (for "pattern"). `@f` will form the fixed part of the display, and starts out containing nothing but spaces, while `@p`, which is not shown directly, contains the input pattern; as the animation proceeds, we'll add more and more asterisks to `@f` until it eventually looks just like `@p`.

Specifically, `@f = ($" x 80) x 23` sets `@f` to 24 strings of 80 spaces each. (`$"` is a special Perl variable whose default value just happens to be a space.) We then take this list, append the input lines to it using the readline operator `<>`, take the last 24 lines of this combined list and assign it to `@p`: this is a compact way to pad `@p` with blank lines so that the pattern appears where it should. Finally, we `chomp` the input lines in `@p` to remove any trailing newlines so that they won't cause problems later.

Now, let's look at the main loop. It turns out that `{...;redo}` is a shorter way to write an infinite loop than `while(1){...}` or even `for(;;){...}`, especially if we get to omit the semicolon before `redo` because it immediately follows an `if` block.

The first line of the main loop introduces the array `@s` (for "snow", of course), to which it prepends a random 80-character string of 90% spaces and 10% asterisks on every iteration. (To save a few chars, I never actually pop extra lines off the end of the `@s` array, so it keeps getting longer and longer. Eventually that will grind the program to a halt as the array gets too long to fit in memory, but that will take much longer than most people would ever watch this animation for. Adding a `pop@s;` statement before the `select` would fix that at the cost of seven chars.)

The rest of the main loop is wrapped in an `if` block, so that it only runs once the `@s` array contains at least 24 lines. This is a simple way to comply with the spec, which requires the whole display to be filled with falling snow from the start, and also simplifies the bitwise operations a bit.

Next comes a `foreach` loop, which in the golfed version is actually a single statement with a `for 0..23` modifier. Since the content of the loop probably needs some explanation, I'm going to unpack it a bit more below:

```
foreach (0 .. 23) {
    print $_ ? $/ : "\e[H";     # move cursor top left before first line, else print newline
    $t = $f[$_];                # save the previous fixed snowflakes
    $f[$_] |= $s[$_] & $p[$_];  # snowflakes that hit the pattern become fixed
    $s[$_] &= ~$t ^ $f[$_];     # ...and are removed from the moving part
    print $f[$_] | $s[$_];      # print both moving and fixed snowflakes ORed together
}

```

First of all, `$_` is the default loop counter variable in Perl unless another variable is specified. Here it runs from 0 to 23, i.e. over the 24 lines in the display frame. `$foo[$_]` denotes the element indexed by `$_` in the array `@foo`.

On the first line of the de-golfed loop, we print either a newline (conveniently obtained from the `$/` special variable) or, when `$_` equals 0, the string `"\e[H"`, where `\e` denotes an ESC character. This is an ANSI terminal control code that moves the cursor to the top left corner of the screen. Technically, we could omit that if we assumed a specific screen size, but I kept it in this version since it means I don't have to resize my terminal to run the animation.

On the `$t = $f[$_]` line, we just save the current value of `$f[$_]` in a "temporary" variable (hence `$t`) before potentially changing it in the next line, where `$s[$_] & $p[$_]` gives the intersection (bitwise AND) of the falling snow and the input pattern, and the `|=` operator ORs that into the fixed output line `$f[$_]`.

On the line below that, `$t ^ $f[$_]` gives the bitwise XOR of the previous and current values of `$f[$_]`, i.e. a list of the bits we changed in the previous line, if any, and negating either of the input strings with `~` negates the output. Thus, what we get is a bitmask with all bits set to 1 *except* those that we just added to `$f[$_]` on the previous line. ANDing that bitmask onto `$s[$_]` removes those bits from it; in effect, this means that when a falling snowflake fills in a hole in the fixed pattern, it gets removed from the falling snow array.

Finally, `print $f[$_] | $s[$_]` (which in the golfed version is implemented by just ORing the two previous lines together) just prints the union (bitwise OR) of the fixed and moving snowflakes on the current line.

One more thing left to explain is the `select '', '', '', 0.1` below the inner loop. This is just a klugy way to sleep 0.1 seconds in Perl; for some silly historical reason, the standard Perl `sleep` command has one-second resolution, and importing a better `sleep` from the `Time::HiRes` module takes more chars than abusing 4-arg `select`.
> 7 votes

# Answer
## HTML and JavaScript, 436 chars

Prepend it to the input:

```
<body onload="for(a=[],b=[],c=document.body.firstChild,e=c[H='innerHTML'].split(N='\n'),f=e.length-1,g=24,h=g-f;f--;)for(X=80;X--;)b[80*(h+f)+X]='*'==e[f][X];for(setInterval(F='for(y=24;y--;)for(x=80;x--;)if(a[w=80*y+x]){d=1;if(b[w])for(d=0,z=y+1;24>z;++z)b[s=80*z+x]&&!a[s]&&(d=1);d&&(a[w]=0,a[w+80]=1)}for(x=80;x--;).1>Math.random(i=0)&&(a[x]=1);for(t=\'\';1920>i;++i)t+=\'* \'[+!a[i]],79==i%80&&(t+=N);c[H]=t',67);g--;)eval(F)"><pre>

```

See it run for each example: code golf, Stack Overflow logo, Christmas trees. Internet Explorer users need to run version 9 and set the "Document Mode" to "IE9 standards" (using the F12 developer tools) for this submission to correctly work.
> 3 votes

# Answer
## Python, 299 chars

This should conform to the rules, assuming the newline is included in the 80 char limit.

```
import random,sys,time
C=1920
v=_,x=' *'
a=['']*C
f=lambda n:[random.choice(e*9+x)for e in _*n]
for e in sys.stdin:a+="%-80s"%e
a=a[-C:]
s=f(C)
while 1:
 z=0;t=''
 for e in s:
    t+=v[x<a[z]or e>_]
    if(e>_<a[z])>(x in a[z+80::80]):a[z]='+'
    t+=z%80/79*'\n';z+=1
 print t;s=f(80)+s[:-80];time.sleep(.1)

```
> 1 votes

# Answer
## Java, 625 chars

```
import java.io.*;import java.util.*;class s extends TimerTask {int _c,_k;char _i[],_o[];boolean _b[];public s(String f) throws IOException {_i=new char[23*80];_o=new char[80];_b=new boolean [23*80];BufferedReader br = new BufferedReader(new FileReader(f));while (br.read(_i,_c++*80,80)!=-1);} public void run(){_k=--_k<0?_c:_k;for(int i=0;i<80;_b[_k*80+i]=Math.random()>0.9?true:false,i++);for(int m=0;m<_c;m++){for(int n=0;n<80;_o[n]=_b[(_k+m)%_c*80+n]?'*':_i[m*80+n],n++);System.out.println(_o);}}public static void main(String[] a) throws IOException{Timer timer=new Timer();timer.scheduleAtFixedRate(new s(a[0]),0,500);}}

```

A simple solution in Java.
> 0 votes

---
Tags: code-golf, ascii-art, animation
---