title: The GolfScript Meta Par Hole

text:
# Question
Title: The GolfScript Meta Par Hole
Seem like GolfScript wins all of these. So you can't beat them, join them.

**Write an Self-Contained Golfscript Interpreter**

I'm using the definition of self-contained to mean, a single program:- So no passing the buck to some external program to do the work for you.

**Test Cases:**

Strings and blocks are represented as lists of ASCII codes. Types are not checked with these tests, but should be right anyway.

```
test("[50] [60]+", [[50, 60]]);
test("{a} {b}+", [[97, 32, 98]]);
test("'a' 'b'+", [[97, 98]]);

test("' ' 0+", [[32, 48]]);
test("' ' [50]+", [[32, 50]]);

test("{a} 0+", [[97, 32, 48]]);
test("{a} [50]+", [[97, 32, 53, 48]]);

test("5 ~", [-6]);
test('"1 2+"~', [3]);
test('{1 2+}~', [3]);
test('[1 2 3]~', [1, 2, 3]);

test('1`', [[49]]);
test("[1 [2] 'asdf']`", [[91, 49, 32, 91, 50, 93, 32, 34, 97, 115, 100, 102, 34, 93]]);
test('"1"`', [[34, 49, 34]]);
test("{1}`", [[123, 49, 125]]);

test("0!", [1]);
test("[]!", [1]);
test("{}!", [1]);
test("''!", [1]);

test("5!", [0]);
test("[[]]!", [0]);
test("{{}}!", [0]);
test("'asdf'!", [0]);

test("1 2 3 4 @", [1, 3, 4, 2]);

test("1 # 2", [1]);

test("1 2 3 4 5 1 $", [1, 2, 3, 4, 5, 4]);
test("'asdf' $", [[97, 100, 102, 115]]);
test("[5 4 3 1 2]{-1*}$", [[5, 4, 3, 2, 1]]);

test("5 7 +", [12]);
test("'a'{b}+", [[97, 32, 98]]);
test("[1 2 3][4 5]+", [[1, 2, 3, 4, 5]]);

test("1 2-3+", [1, -1]);
test("1 2 -3+", [1, -1]);
test("1 2- 3+", [2]);
test("[5 2 5 4 1 1][1 2]-", [[5, 5, 4]]);

test("2 4*", [8]);
test("2 {2*} 5*", [64]);
test("[1 2 3]2*", [[1, 2, 3, 1, 2, 3]]);
test("3'asdf'*", [[97,115,100,102,97,115,100,102,97,115,100,102]]);

test("[1 2 3]' '*", [[49, 32, 50, 32, 51]]);
test("[1 2 3][4]*", [[1,4,2,4,3]]);
test("'asdf'' '*", [[97,32,115,32,100,32,102]]);
test("[1 [2] [3 [4 [5]]]]' '*", [[49, 32, 2, 32, 3, 4, 5]]);
test("[1 [2] [3 [4 [5]]]][6 7]*", [[1, 6, 7, 2, 6, 7, 3, [4, [5]]]]);

test("[1 2 3 4]{+}*", [10]);
test("'asdf'{+}*", [414]);

test("7 3 /", [2]);
test("[1 2 3 4 2 3 5][2 3]/", [[[1], [4], [5]]]);
test("[1 2 3 4 5] 2/", [[[1, 2], [3, 4], [5]]]);

test("0 1 {10<} { .@+ } /", [8, [1, 1, 2, 3, 5, 8]]);
test("[1 2 3]{1+}/", [2, 3, 4]);

test("7 3 %", [1]);

test("'assdfs' 's'%", [[[97], [100, 102]]]);
test("'assdfs' 's'/", [[[97], [], [100, 102], []]]);

test("[1 2 3 4 5] 2%", [[1, 3, 5]]);
test("[1 2 3 4 5] -1%", [[5, 4, 3, 2, 1]]);
test("[1 2 3] {1+}%", [[2, 3, 4]]);

test("5 3 |", [7]);
test("[5 5 1] [1 3] |", [[5, 1, 3]]);

test("5 3 &", [1]);
test("[1 1 2 2][1 3]&", [[1]]);

test("5 3 ^", [6]);
test("[1 1 2 2][1 3]^", [[2, 3]]);

test("1 2 [\\]", [[2, 1]]);

test("1 2 3 \\", [1, 3, 2]);
test("1 2 3; ", [1, 2]);

test("3 4 <", [1]);
test('"asdf" "asdg" <', [1]);
test("[1 2 3] 2 <", [[1, 2]]);
test("{asdf} -1 <", [[97, 115, 100]]);

test("3 4 >", [0]);
test('"asdf" "asdg" >', [0]);
test("[1 2 3] 2 >", [[3]]);
test("{asdf} -1 >", [[102]]);

test("3 4 =", [0]);
test('"asdf" "asdg" =', [0]);
test("[1 2 3] 2 =", [3]);
test("{asdf} -1 =", [102]);

test("3,", [[0,1,2]]);
test("10,,", [10]);
test("10,{3%},", [[1, 2, 4, 5, 7, 8]]);

test("1 2 .", [1,2,2]);

test("2 8?", [256]);
test(" 5 [4 3 5 1] ?", [2]);
test(" 6 [4 3 5 1] ?", [-1]);

test("[1 2 3 4 5 6] {.* 20>} ?", [5]);

test("5(", [4]);
test("[1 2 3](", [[2, 3], 1]);

test("5)", [6]);
test("[1 2 3])", [[1, 2], 3]);

test("5 {1 0/} or", [5]);
test("5 {1 1+} and", [2]);
test("0 [3] xor", [[3]]);
test("2 [3] xor", [0]);

test("5{1-..}do", [4, 3, 2, 1, 0, 0]);
test("5{.}{1-.}while", [4, 3, 2, 1, 0, 0]);
test("5{.}{1-.}until", [5]);

test("1 2 3 if", [2]);
test("0 2 {1.} if", [1, 1]);

test("[[1 2 3][4 5 6][7 8 9]]zip", [[[1, 4, 7], [2, 5, 8], [3, 6, 9]]]);

test("[1 1 0] 2 base", [6]);
test("6 2 base", [[1, 1, 0]]);

```

# Answer
> 9 votes
# Ruby, 5490 bytes

Well, I can golf the GolfScript interpreter from 8283 bytes down to 5490 ...

```
$m=[];class G;def g;$k<<self;end;def v;@v;end
'+-|&^'.each_byte{|i|eval'def%c(r);if r.class!=self.class
a,b=u(r);a%c b;else;f(@v%c r.v);end;end'%([i]*3)}
def==(r);@v==r.v;end;def eql?(r);@v==r.v;end;def hash
@v.hash;end;def<=>(r);@v<=>r.v;end;end;class H<G;def
initialize(i);@v=case i;when true then 1;when false then 0
else;i;end;end;def f(a);H.new(a);end
def t;J.new(@v.to_s);end;def to_int#for pack
@v;end;def s;t;end;def N;0;end;def u(b);[if b.class==I
I.new([self]);elsif b.class==J;t;else#K
t.to_s.w;end,b];end;def~;H.new(~@v);end;def R;H.new(@v==0)
end;'*/%<>'.each_byte{|i|eval'def%c(r);H.new(@v%c r.v)
end'%[i,i]};def E(r);H.new(@v==r.v);end;def q(b)
H.new(@v**b.v);end;def B(a);if I===a;r=0;a.v.each{|i|r*=@v
r+=i.v};H.new(r);else;i=a.v.abs;r=[];while i!=0;r.unshift
H.new(i%@v);i/=@v;end;I.new(r);end;end;def n;H.new(@v-1);end;def
p;H.new(@v+1);end;end;class I<G;def initialize(a);@v=a;end;def
f(a);I.new(a);end;def t;@v.inject(J.new("")){|s,i|s+i.t};end
def F#maybe name to_a ?
I.new(@v.inject([]){|s,i|s+case i;when J then i.v;when H then[i]
when I then i.F.v;when K then i.v;end});end;def s
J.new('[')+I.new(@v.map{|i|i.s})*J.new(' ')+J.new(']');end;def
g;$k<<self;end;def N;1;end;def u(b);if b.class==H
b.u(self).reverse;elsif b.class==J;[J.new(self),b];else
[(self*J.new(' ')).to_s.w,b];end;end;def n;[f(@v[1..-1]),@v[0]]
end;def p;[f(@v[0..-2]),@v[-1]];end;def*(b);if b.class==H
f(@v*b.v);else;return b*self if self.class==J&&b.class==I;return
self/H.new(1)*b if self.class==J;return;b.f([])if@v.size<1
r=@v.first;r,x=r.u(b)if r.class!=b.class#for size 1
@v[1..-1].each{|i|r=r+b+i};r;end;end;def/(b);if b.class==H
r=[];a=b.v<0 ?@v.reverse: @v;i=-b=b.v.abs
r<<f(a[i,b])while(i+=b)<a.size;I.new(r);else;r=[];i=b.f([])
j=0;while j<@v.size;if@v[j,b.v.size]==b.v;r<<i;i=b.f([])
j+=b.v.size;else;i.v<<@v[j];j+=1;end;end;r<<i;I.new(r);end;end
def%(b);if b.class==H;b=b.v
f((0..(@v.size-1)/b.abs).inject([]){|s,i|s<<@v[b<0 ?i*b-1:i*b]})
else;self/b-I.new([I.new([])]);end;end;def R;H.new(@v.empty?)
end;def q(b);H.new(@v.index(b)||-1);end;def E(b);b.class==H ?
@v[b.v] : H.new(@v==b.v);end;def<(b);b.class==H ? f(@v[0..b.v]):
H.new(@v<b.v);end;def>(b);b.class==H ?
f(@v[[b.v,-@v.size].max..-1]) : H.new(@v>b.v);end;def sort
f(@v.sort);end;def T;r=[];@v.size.times{|x|@v[x].v.size.times{|y|
(r[y]||=@v[0].f([])).v<<@v[x].v[y]}};I.new(r);end;def~;v;end;end
class J<I;def initialize(a);@v=case a;when String then
a.unpack('C*').map{|i|H.new(i)};when Array then a;when I then
a.F.v;end;end;def f(a);J.new(a);end;def t;self;end;def s
f(to_s.inspect);end;def to_s;@v.pack('C*');end;def N;2;end
def u(b);b.class==K ? [to_s.w,b]:b.u(t).reverse;end;def q(b)
if b.class==J;H.new(to_s.index(b.to_s)||-1);elsif b.class==I
b.q(t);else;H.new(@v.index(b)||-1);end;end;def~;to_s.w.g;nil;end
end;class K<I;def initialize(a,b=nil);@v=J.new(b).v
@n=eval("lambda{#{a}}");end;def g;@n.call;end;def f(b)
J.new(b).to_s.w;end;def N;3;end;def t;J.new("{"+J.new(@v).to_s+"}")
end;def s;t;end;def u(b);b.u(self).reverse;end;def+(b);if
b.class!=self.class;a,b=u(b);a+b;else
J.new(@v+J.new(" ").v+b.v).to_s.w;end;end;def*(b);if b.class==H
b.v.times{g};else;z b.v.first;(b.v[1..-1]||[]).each{|i|$k<<i;g}
end;nil;end;def/(b);if b.class==I||b.class==J;b.v.each{|i|z i;g}
nil;else#unfold
r=[];loop{$k<<$k.last;g;break if y.R.v!=0;r<<$k.last;b.g}
y;I.new(r);end;end;def%(b);r=[];b.v.each{|i|m=$k.size
$k<<i;g;r.concat($k.slice!(m..$k.size))};r=I.new(r)
J==b.class ? J.new(r):r;end;def~;g;nil;end
def sort;a=y;a.f(a.v.sort_by{|i|z i;g;y});end
def C(a);a.f(a.v.C{|i|z i;g;y.R.v==0});end
def q(b);b.v.find{|i|z i;g;y.R.v==0};end;end
class NilClass;def g;end;end
class Array;def^(r);self-r|r-self;end;include Comparable;end
e=gets(nil)||'';Q=$stdin;$_=Q.isatty ? '':Q.read;$k=[J.new($_)]
$l={};def x(name,v=nil);eval"#{s="$_#{$l[name]||=$l.size}"}||=v"
s;end;$j=0
class String;def W;K.new(self);end;def X;('a=y;'+self).W;end
def Y;('b=y;a=y;'+self).W;end;def Z;('c=y;b=y;a=y;'+self).W;end
def o;('b=y;a=y;a,b=b,a if a.N<b.N;'+self).W;end;def
w(a=scan(/[a-zA-Z_][a-zA-Z0-9_]*|'(?:\\.|[^'])*'?|"(?:\\.|[^"])*"?|-?[0-9]+|#[^\n\r]*|./m))
b=a.dup;c="";while t=a.slice!(0);c<<case t
when"{"then"$k<<"+x("{#{$j+=1}",w(a));when"}"then break
when":"then x(a.slice!(0))+"=$k.last"
when/^["']/ then x(t,J.new(eval(t)))+".g"
when/^-?[0-9]+/ then x(t,H.new(t.to_i))+".g"
else;x(t)+".g";end+"\n";end
d=b[0,b.size-a.size-(t=="}"?1:0)]*"";K.new(c,d);end;end
def y;($m.size-1).downto(0){|i|break if$m[i]<$k.size;$m[i]-=1}
$k.pop;end;def z a;$k.push(*a)if a;end
x'[','$m<<$k.size'.W;x']','z I.new($k.slice!(($m.pop||0)..-1))'.W
x'~','z~a'.X;x'`','z a.s'.X;x';',''.X;x'.','$k<<a<<a'.X
x'\\','$k<<b<<a'.Y;x'@','$k<<b<<c<<a'.Z;x'+','z a+b'.Y
x'-','z a-b'.Y;x'|','z a|b'.Y;x'&','z a&b'.Y;x'^','z a^b'.Y
x'*','z a*b'.o;x'/','z a/b'.o;x'%','z a%b'.o;x'=','z a.E(b)'.o
x'<','z a<b'.o;x'>','z a>b'.o;x'!','z a.R'.X
x'?','z a.q(b)'.o;x'$','z(a.class==H ? $k[~a.v]:a.sort)'.X
x',','z case a;when H then I.new([*0...a.v].map{|i|H.new(i)})
when K then a.C(y);when I then H.new(a.v.size);end'.X
x')','z a.p'.X;x'(','z a.n'.X
x'rand','z H.new(rand([1,a.v].max))'.X;x'abs','z H.new(a.v.abs)'.X
x'print','print a.t'.X;x'if',"#{x'!'}.g;(y.v==0?a:b).g".Y
x'do',"loop{a.g;#{x'!'}.g;break if y.v!=0}".X
x'while',"loop{a.g;#{x'!'}.g;break if y.v!=0;b.g}".Y
x'until',"loop{a.g;#{x'!'}.g;break if y.v==0;b.g}".Y
x'zip','z a.T'.X;x'base','z b.B(a)'.Y
'"\n":n;{print n print}:puts;{`puts}:p;{1$if}:and;{1$\if}:or;{\!!{!}*}:xor;'.w.g
e.w.g;z I.new($k);'puts'.w.g

```

# Answer
> 11 votes
# Javascript, 2227 bytes

@Peter Taylor: Challenge Accepted!

```
_='S=b9b?b^3?"{"+)+"}":\'"\'+)+\'"\':"["+b6SB" ")+"]":""+b};$=b||!b99b:[b]b6$B""L;M=b9$(bb+""};A=b?(gb.charCodeAt(0)A(b1))v=g,v=3,g,v};C=b9(k=b6Ck=b,kb};a=g,s,O,r=Wj,uX,d,c,i,yPb=(b?$(bb+"").match(/\'(.|[^\'])*\'|"(.|[^"])*"|-?\\d+|\\043[^\\n]*|[a-z_]\\w*|./imgFi=y=0;z=b[i++];)"{"Yz?!y++Zk=iy?"}"Yz!--yZe=A(bk,i-1B""))e=4\'"\'YzQ?A(eval(z.replace("\\n","n")))"\'"YzQ?A(z1,-1).replace(/(|\')/g,"$1"))":"Yz?r[b[i++]]=(d=s[s-1])^4?S(dd:r[z]?r[z]z+"."-0.1?eval(z)eval("//~t;t98?ts=st~t\\140A(S(G)))//[O.uns]JEt,u@`vEuX,v%`I!u)t%u!tPt3?[32]:[]Xu+tV-5!~tc)RcL# q-t/`I!u)Math.floot/u)!tPv=0;j%tY0ZvRvv,vvcdvLu^4Pp=1 ITPFd;\'.\'u;)ds[s-1]tGdL#{D;HL//*7I!t)q*t!uPFd;u--;)T?td=dCUd=8;T||dL8^4P!u8Zu6M)6A)d=dC(j?t:[]cd=8;GdL#{q.)HL//zipt;Fv=c;v--;)!d[v]Zd[v]d[v]c[v]?7IT)HG)Zcu# t9tuMath.pow(uX)$t;u=0;t9(T?(u=t,G)t).sort(uZaua,bubb-a}C(s~t)Q)=`t!9ut)Q:0|$(u)Y$U>N$U|0:t0Xu>t|0V)K()]:[t+1](K.)]:[t-1]&5v;~tc)vc   &t|5dvt |t^5v;k,ut!~tc)^!~kc)vc ^tif`v=?u:t;v^4?A(S(v)v!+!randMath.random()*G)|0)".split("//"+z)[1]L,\'{1$if}:and{1$if}:or{!!{!}*}:xor{..0sZOQ=sFfoGs(HctIif(Js.splice(O.))Kt;s=st9[tXL)}N`q9t9$(u)P){Q[0]RdT8>3U(t)V8//Wfunction(b,X,tY==Z(`;qu';for(Y=0;$='q`ZYXWVUTRQPNLKJIHGFEDB98765#  '[Y++];)with(_.split($))_=join(pop());eval(_)
```

Note: Contains some control characters, nothing outside of ASCII though. Here's a direct link to the file: gs.js. The code provides a function `a` which takes the Golfscript code as a single parameter and returns the resulting stack as an array, with strings and blocks represented as ASCII.

Differences from the official interpreter:

* Numbers have only 53 bits precision
* No exact output and no direct `print` (would be easy to add though)
* Double quoted strings are parsed using Javascript's eval, which might work different than Ruby's. Also no access to Ruby functions via strings
* Undefined behaviour (I tried my very best)

I've also made a bunch of test cases and set up a small form for running Golfscript code: http://copy.sh/golfscript/

Here are some examples:

This is my standard Golfscript library, suggestions are welcome:

```
{1$if}:and
{1$\\if}:or
{\!!{!}*}:xor
{..0<2**-}:abs
{\{!}+\while}:until
{0$}:.
"\n":n
{\.[]*{0{2$*\(@+1$}do@;\;}{[{.@.@\\%@@.@\/.}do;;]-1%}if}:base
];

```

---
Tags: code-golf, golfscript
---


# Question
Title: Create a C program that takes the longest period of time to compile in gcc
Create a short C program that takes an absurdly long time to compile with gcc. Entries will be scored by timing the compilation then subtracting the reference program's compile time.

Rules

* Any C language feature or gcc extension
* gcc 4.2.1

# Answer
> 13 votes
```
#define a "xxxxxxxxxxx"
#define b a a a a a a a
#define c b b b b b b b
#define d c c c c c c c
#define e d d d d d d d
#define f e e e e e e e
#define g f f f f f f f
#define h g g g g g g g
#define i h h h h h h h
#define j i i i i i i i
z=j;

```

# Answer
> 13 votes
Both Charlie's answer and my earlier one work on the principle of letting the pre-processor write a *lot* of code, but they mostly exercise the pre-processor itself, the lexer (good idea as this step has traditionally been slow) and the parser. Mine also attempts to work the optimization and code generation steps, but it is clearly not gaining a lot there.

Thinking about how a typical c compiler works, I realized that we weren't giving the symbol table related code anything to do. This entry is an attempt to remedy that. It is supposed to be reminiscent of basic object-orientation in c implementation, but doesn't do anything interesting: justuses the pre-processor expansion technique to declare and trivially (and incorrectly) initializes a bunch of objects. Object that use complicated types, on many levels of scope, shadowing each other at various removes. It ought to give the symbol table a real work out.

```
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
// Exercise the symbol table mechanism of the compiler in an effort to
// take a unreasonable about of time compiling

#define PTR(T) T*
#define CONST(T) T const
#define FUNC(NAME,RTYPE,ARG) RTYPE NAME(ARG)
#define FPTR(NAME,RTYPE,ARG) FUNC((*NAME),RTYPE,ARG)

// Forward decalration of repeated OO method pointers
typedef void* (*cctor_ptr)(void*this, void*that, ...);
typedef void* (*dtor_ptr)(void*this);

// Assumes three var-args: sizeof(payload type), cctor, dtor
void* default_ctor(void*this, ...){
  // Pull in variadac bits
  va_list list;
  va_start(list,this);
  int size=va_arg(list,int);
  cctor_ptr cctor=va_arg(list,cctor_ptr);
  dtor_ptr dtor=va_arg(list,dtor_ptr);
  va_end(list);
  // process
  if (!this) this = malloc(size);
  if (this) {
    memset(this,size,0);
    /* various dodges to install the cctor and dtor in the write places */
  }
  return this;
}
// Copies the payload from that to this;
void* default_cctor(void*restrict this, void* restrict that, ...){
  // Pull in variadac bits
  va_list list;
  va_start(list,that);
  int size=va_arg(list,int);
  cctor_ptr cctor=va_arg(list,cctor_ptr);
  dtor_ptr dtor=va_arg(list,dtor_ptr);
  va_end(list);
  // process
  if (!this) this = malloc(size);
  if (this) {
    memcpy(this,that,size);
    /* various dodges to install the cctor and dtor in the write places */
  }
  return this;
}
// Assumes that his was allocated with malloc, does not use varargs
void* default_dtor(void*this, ...){
  free(this);
  return NULL;
};

#define DECLARE_STRUCT(N) struct S##N##_s
#define TYPEDEF_ACCESSOR(N,T) typedef FPTR(f##N##_ptr,CONST(PTR(T)),PTR(CONST(struct S##N##_s)))
#define TYPEDEF_STRUCT(N,T) typedef struct S##N##_s {PTR(T)p; cctor_ptr cctor; dtor_ptr dtor; f##N##_ptr f##N;} S##N
#define OO_STRUCT(N,T) DECLARE_STRUCT(N); TYPEDEF_ACCESSOR(N,T); TYPEDEF_STRUCT(N,T)

OO_STRUCT(1,char);
OO_STRUCT(2,int);
OO_STRUCT(3,double*);
OO_STRUCT(4,S3);
OO_STRUCT(5,S4);
OO_STRUCT(6,S5);
OO_STRUCT(7,S6);
OO_STRUCT(8,S7);

#define SUBSCOPE(A) { \
    S1*A##1=default_ctor(NULL,sizeof(char),default_cctor,default_dtor); \
    S2 A##2; default_ctor(&A##2,sizeof(int),default_cctor,default_dtor); \
    S2*A##3=default_ctor(NULL,sizeof(double*),default_cctor,default_dtor); \
    S8 A##5; default_ctor(&A##5,sizeof(S4),default_cctor,default_dtor); \
    S6 A##6; default_ctor(&A##6,sizeof(S5),default_cctor,default_dtor); \
    S8*A##8=default_ctor(NULL,sizeof(S7),default_cctor,default_dtor); \
  }
#define SUBSCOPE2(A,B)  { \
    S2*B##5=default_ctor(NULL,sizeof(S4),default_cctor,default_dtor); \
    S4 A##7; default_ctor(&A##7,sizeof(S6),default_cctor,default_dtor); \
    SUBSCOPE(A) SUBSCOPE(B);                 \
  }
#define SUBSCOPE6(A,B,C)  { \
    S2*A##3=default_ctor(NULL,sizeof(double*),default_cctor,default_dtor); \
    S2 B##2; default_ctor(&B##2,sizeof(int),default_cctor,default_dtor); \
    S4*C##4=NULL;                           \
    SUBSCOPE2(A,C) SUBSCOPE2(B,C) SUBSCOPE2(A,B); \
  }
#define SUBSCOPE24(A,B,C,D) { \
    S1*D##1=default_ctor(NULL,sizeof(char),default_cctor,default_dtor); \
    S2 C##2; default_ctor(&C##2,sizeof(int),default_cctor,default_dtor); \
    S2*B##3=default_ctor(NULL,sizeof(double*),default_cctor,default_dtor); \
    S4 A##4; default_ctor(&A##4,sizeof(S3),default_cctor,default_dtor); \
    SUBSCOPE6(A,B,C) SUBSCOPE6(A,B,D) SUBSCOPE6(A,C,D) SUBSCOPE6(B,C,D); \
  }
#define SUBSCOPE120(A,B,C,D,E) { \
    S5*A##5=default_ctor(NULL,sizeof(S4),default_cctor,default_dtor); \
    S6*A##6=default_ctor(NULL,sizeof(S5),default_cctor,default_dtor); \
    S8 A##8; default_ctor(&A##8,sizeof(S7),default_cctor,default_dtor); \
    SUBSCOPE24(A,B,C,D) SUBSCOPE24(A,B,C,E) SUBSCOPE24(A,B,D,E); \
    SUBSCOPE24(A,C,D,E) SUBSCOPE24(B,C,D,E); \
  }
#define SUBSCOPE720(A,B,C,D,E,F) { \
    S5 A##5; default_ctor(&A##5,sizeof(S4),default_cctor,default_dtor); \
    S6 A##6; default_ctor(&A##6,sizeof(S5),default_cctor,default_dtor); \
    S8*A##8=default_ctor(NULL,sizeof(S7),default_cctor,default_dtor); \
    SUBSCOPE120(A,B,C,D,E) SUBSCOPE120(A,B,C,D,F) SUBSCOPE120(A,B,C,E,F); \
    SUBSCOPE120(A,B,D,E,F) SUBSCOPE120(A,C,D,E,F) SUBSCOPE120(B,C,D,E,F); \
  }

int main(){
  S4 s4;
  SUBSCOPE720(A,B,C,D,E,F)
}

```

Compile time on my machine is in excess of 4 seconds with `-O3` and more than 1 second with no optimization.

---

Obviously the next step would be to finish the OO implementation for a BCD classes and re-do the pi calculations using it so that I get both effects running hard.

# Answer
> 12 votes
Here's a riff of the exponential-preprocessor-expansion theme which does something minimally interesting: computes two approximations to pi by series methods and compares with both the value in `math.h` and the usual incantation.

Ungolfed.

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

// Some random bits we'll need
#define MINUSONODD(n) (n%2?-1:+1)
#define TWON(n) (2*(n))
#define NPLUSONE(n) ((n)+1)
#define TWONPLUSONE(n) NPLUSONE(TWON(n))
#define FACT(n) (tgamma(NPLUSONE(n)))

// The Euler series
//                           2^(2n) * (n!)^2      z^(2n+1)
// atan(z) = \sum_n=0^\infty --------------- * ---------------
//                               (2n+1)!       (1 + z^2)^(n+1)
#define TERMEULER(n,z) (pow(2,TWON(n))*                 \
            FACT(n)*FACT(n)*                \
            pow((z),TWONPLUSONE(n))/            \
            FACT(TWONPLUSONE(n)) /              \
            pow((1+z*z),NPLUSONE(n)) )

// The naive version
//                           (-1)^n * z^(2n+1)
// atan(z) = \sum_n=0^\infty -----------------
//                                2n + 1
#define TERMNAIVE(n,z) (MINUSONODD(n)*pow(z,TWONPLUSONE(n))/TWONPLUSONE(n))

// Define a set of bifruncations of the sum
#define N2TERMS(n,z,ALG)  (TERM##ALG(TWON(n),(z)) + TERM##ALG(TWONPLUSONE(n),(z)))
#define N4TERMS(n,z,ALG)  (N2TERMS(TWON(n),(z),ALG)+N2TERMS(TWONPLUSONE(n),(z),ALG))
#define N8TERMS(n,z,ALG)  (N4TERMS(TWON(n),(z),ALG)+N4TERMS(TWONPLUSONE(n),(z),ALG))
#define N16TERMS(n,z,ALG) (N8TERMS(TWON(n),(z),ALG)+N8TERMS(TWONPLUSONE(n),(z),ALG))
#define N32TERMS(n,z,ALG) (N16TERMS(TWON(n),(z),ALG)+N16TERMS(TWONPLUSONE(n),(z),ALG))

// Sum the fist 32*2+16 = 80 terms of a series...
#define PARTIALSUM(z,ALG) N32TERMS(0,(z),ALG)+N32TERMS(1,(z),ALG)+N16TERMS(4,(z),ALG)

int main(void){
  const double PI_TRAD = 4.0L * atan(1.0);
  const double PI_NAIVE = 4.0L * PARTIALSUM(0.999999L,NAIVE);
  const double PI_EULER = 4.0L * PARTIALSUM(0.999999L,EULER);
  printf("pi (math.h) = %10.8f\n",M_PI);
  printf("pi (trad.)  = %10.8f\n",PI_TRAD);
  printf("pi (NAIVE)  = %10.8f\n",PI_NAIVE);
  printf("pi (EULER)  = %10.8f\n",PI_EULER);
}

```

Assumes that you are using `gcc` and `glibc` and may or may not work with other arrangements. It takes about 1.0-1.1 seconds of processor time (evaluated with `time (1)`) to compile on with `-03`1 on my 2.4 GHz Intel Core 2 Duo MacBook. A default compile takes about 0.4 seconds of processor time.

Alas, I can't get gcc to evaluate either `pow` or `tgamma` at compiler time, which would really help.

When you run it the output is:

```
pi (math.h) = 3.14159265
pi (trad.)  = 3.14159265
pi (NAIVE)  = 3.11503599
pi (EULER)  = 3.14159065

```

which shows just how slowly the naive series converges.

---

1 To get as much constant folding and sub-expression elimination as possible.

---
Tags: code-challenge, c
---


title: Output a playable crossword grid

text:
# Question
Title: Output a playable crossword grid
Write a program to produce a file containing a crossword grid that the user can print out and work the puzzle on.

## Input

A filename representing a crossword grid file and optionally a second filename representing a crossword numbering file. The input should be accepted by a conventional means for your programming environment: command line arguments, the standard input, web forms, etc..

You may assume that the crossword has been validated, and if using a numbering file that is corresponds to the grid provided.

**Grid file format:** The first line consists of two white-space separated integer constants M and N. Following that line are M lines each consisting of N characters (plus a new line) selected from `[#A-Z ]`. These characters are interpreted such that `'#'` indicates a blocked square, `' '` a open square in the puzzle with no known contents and any letter an open square whose containing that letter.

**Numbering file format** Lines starting with '#' are ignored and may be used for comments. All other lines contain a tab separated triplet `i`, `m`, `n` where `i` represents a number to be printed on the grid, and `m` and `n` represent the row and column of the square where it should be printed. The number of both rows and columns starts at 1.

## Output

The output will be a file that the user can print out and work a crossword on. ASCII, postscript, pdf, png, and any other reasonable format will be accepted, but all must abide by these rules:

1. There must be a rule around the entire puzzle and between every pair of squares.
2. Blocked squares must be filled in darkly.
3. In play square that represent the start of a numbered (across or down) clue must be provided with a number in the upper, left corner of the square, while leaving most of the square blank for the play to write in. Note that typical grid published in the papers will have many tens of clues and may have more than 100.

The output will be of the grid alone, without the list of clues.

Output should be sent to a conventional destination (a file whose name is derived from the input filename, produced as a web page, etc..)

## Test case

Given a input of

```
5   5
#  ##
#
  #
    #
##  #

```

the starting corner of an acceptable ASCII output might look like this

```
+-----+-----+-----+---
|#####|1    |2    |###
|#####|     |     |###
|#####|     |     |###
+-----+-----+-----+---
|#####|3    |     |4
|#####|     |     |
|#####|     |     |
+-----+-----+-----+---
|6    |     |#####|
|     |     |#####|

```

Those using graphical formats should take their inspiration from the usual printed sources.

## Numbering scheme

A correctly numbered grid has the following properties:

1. Numbering begins at 1.
2. No column or span of open squares is unnumbered.
3. Numbers will be encountered in counting order by scanning from top row to the bottom taking each row from left to right.

## Aside

This is the third of several crossword related challenges. I plan to use a consistent set of file-formats throughout and to build up a respectable suite of crossword related utilities in the process.

Previous challenges in this series:

# Answer
> 4 votes
## Python, 379 characters

```
import sys
A=sys.argv
f=open(A[1])
V,H=map(int,f.readline().split())
M={}
if A[2:]:
 for r in open(A[2]).readlines():n,y,x=map(int,r.split());M[y*H+y+x]=n
R='+-----'*H+'+'
n,v,s='\n| '
x=y=z=''
p=V+1
for c in n+''.join(f):
 if c==n:print x+n+y+n+z+n+R;x=y=z=''
 elif'@'>c:x+=5*c;y+=5*c;z+=5*c
 else:x+=5*s;y+=s+s+c+s+s;z+=5*s
 if p in M:x=x[:-5]+"%-5d"%M[p]
 x+=v;y+=v;z+=v;p+=1

```

# Answer
> 10 votes
# Postscript ~~905 797 677 675 629 608 330 320~~ 308

```
{G N}/Times-Roman .3 2 22 1 30/.{<920>dup 1 4 3 roll put cvx
exec}def/${//. 73 .}def[/R{99<a51f3e7d75>$}/G{<1fab75>$
R(uN)${0 R{1(X)$ 0 1 -1 5 4 roll 35 eq{4<1980>$}if<81>$
1 add}(I)$(u)$ 0 -1<ad>$}<834d>$}/X{{exit}if}/N{-.9
.7<ad>${<1fab70>$ X}loop{{(>nk)$(  )<31a0>$}<a3>$
X}loop}>><0d38388b369bad8e3f>$

```

This program is written as a "protocol prolog" so you just cat it together with the grid and number files (in that order, separated by blank lines) and pipe the whole mess to ghostscript or Distiller or a PS printer. Appended to the reference version below is a NYT puzzle (From Nov. 5, 2011) with numbers and one answer I'm pretty sure of (Saturdays is hard!).

The new revision uses these two procedures to execute binary-encoded system names from strings.

```
/.{
    <920>  % two-byte binary-encoded name template with 0x92 prefix
    dup 1 4 3 roll put  % insert number into string
    cvx exec  % and execute it
}def
/${
    //.   %the /. procedure body defined above
    73 .  %"forall" (by code number)
}def

```

Indented and (somewhat) commented.

```
/Times-Roman .3 2 22 1 30
/.{<920>dup 1 4 3 roll put cvx exec}def/${//. 73 .}def
[
/R{99<a51f3e7d75>$}    %currentfile 99 string readline pop
/G{<1fab75>$ %currentfile token pop
    R (uN)$ %<754e>$ %pop gsave
    {
        0 R {
            1 (X)$ %index
            0 1 -1 5 4 roll
            35 eq{
                4<1980>$ %copy rectfill
            }if
            <81>$ %rectstroke
            1 add
        }(I)$
        (u)$ % 73 . %forall pop
        0 -1<ad>$ %translate
    }<834d>$ %repeat grestore
}
/X{{exit}if}
/N{
    -.9 .7<ad>$ %translate
    %{ currentfile token not {exit} if } loop
    {<1fab70>$
        X %{exit}if
    }loop
    {
        %dup type/integertype ne{exit}if
        {
            (>nk)$ %<3e6e6b>$ %exch neg moveto
            (  )<31a0>$ %cvs show
        }<a3>$ %stopped
        X %{exit}if
    }loop
}
>>
<0d38388b369bad8e>$
%begin dup dup scale div setlinewidth translate selectfont
{G N}exec

```

Data files.

```
15 15
     #   #

       #     ##
##   #   #
    #     #
   #    #
       #
      #    #
    #     #
    K#   #   ##
##  I  #
    L
    N
    S#   #

#i m n   figure(number), row, col
1 1 1
2 1 2
3 1 3
4 1 4
5 1 5
6 1 7
7 1 8
8 1 9
9 1 11
10 1 12
11 1 13
12 1 14
13 1 15
14 2 1
15 2 6
16 2 10
17 3 1
18 4 1
19 4 9
20 5 3
21 5 7
22 5 8
23 5 11
24 5 14
25 5 15
26 6 1
27 6 2
28 6 6
29 6 10
30 6 12
31 7 1
32 7 5
33 7 10
34 7 11
35 8 1
36 8 4
37 8 9
38 9 1
39 9 8
40 9 13
41 10 1
42 10 6
43 10 7
44 10 12
45 11 1
46 11 5
47 11 7
48 11 11
49 12 3
50 12 6
51 12 9
52 12 10
53 12 14
54 12 15
55 13 1
56 13 2
57 13 8
58 14 1
59 15 1
60 15 7
60 15 11

```

It should look okay from a printer, but on-screen it needs a little help. This 19-char procedure and 9 chars to invoke it on all user-space points, helps make evenly-spaced lines look more even. So 308 + 19 + 9 = 337, used to generate this image.

```
/F{<ac893e893e5f>$} % transform round exch round exch itransform

```

## Postscript 608

This earlier version (from revision 8) uses a completely different approach, reusing the main-line code as a "lexicon" from which longer tokens can be indexed using strings.

```
<<-1{{30 700 translate 0 0 moveto
currentfile 2{(@A1*)*}repeat exch string
3 2 roll{('BO1)*{( )(@#)*
4(,.N:;<%)*<<( ){p}/#{(1:;>%)*}0{(;,'.)*
6 -26(CE%)*}>>(IJ'B)* known not{p
0}if(LG #C)*}forall(#;*1 D%)*}repeat
p/Times-Roman 8 selectfont 99
string{('BO)*{(@)* length(#=)*{p}{(@#L)*
35(=)*{p}{cvx(GID ?'H*ID ?KHF%)*(   )cvs(E)*}e}e}{showpage
exit}e}loop exit{( @#M# FMF#M)*
closepath}currentpoint stroke eq fill
mul dup token copy rmoveto sub show
neg exec add 1 index 9 get rlineto
put readline}loop}0 1 index 0 get{1
index 1 add}forall pop/*{{32 sub load
exec}forall}/e{ifelse}/p{pop}>>begin(23,?4)*<1f>*

```

It was written using this commented version which illustrates the encoding of the lexicon. The first token `30` is commented `space` therefore `( )*` is a synonym for `30`. Not very beneficial for `30`, but for longer tokens this is(was) a big win (until deeper encoding possibilities are(were) discovered).

```
<<-1{{
%space  !    "         # $ %      &           '(        )     %*    +      , - .   %/
 30     700  translate 0 0 moveto currentfile 2{(@A1*)*}repeat exch string 3 2 roll
{('BO1)*{( )(@#)* 4(,.N:;<%)*<<( ){p}/#{(1:;>%)*}0{(;,'.)* 6 -26(CE%)*}>>(IJ'B)*
known not{p 0}if(LG #C)*}forall(#;*1 D%)*}
%0      1   2          3 4          5  6     7
 repeat p /Times-Roman 8 selectfont 99 string{('BO)*{(@)* length(#=)*{p}{
(@#L)* 35(=)*{p}{cvx(GID ?'H*ID ?KHF%)*(   )cvs(E)*}e}e}{showpage clear exit}e}
%8    9   :                         %;            <      =    >    ?
 loop exit{( @#M# FMF#M)* closepath} currentpoint stroke eq fill mul
%@   A     B    C       D   E    F   G    H   I J     K L   M       N   O
 dup token copy rmoveto sub show neg exec add 1 index 9 get rlineto put readline
}loop}0 1 index 0 get{1 index 1 add}forall
pop/*{{32 sub load exec}forall}/e{ifelse}/p{pop}>>begin(23,?4)*<1f>*

```

# Answer
> 4 votes
## C (output to SVG), 553 chars

I know, the code is huge, but this problem is just crying out for an SVG answer.

```
char*f,b[99];h,w;main(i){fscanf(f=fopen(gets(b),"r"),"%d%d%*[\n]",&h,&w);for(
printf("<svg xmlns='http://www.w3.org/2000/svg' viewBox='.9 .9 %d.2 %d.2'><path d='M1 1",
i=w,h);i--;)printf("v%dv-%dh1",h,h);for(;h--;)printf("v1h-%dh%d",w,w);for(
puts("' style='fill:none;stroke:#000;stroke-width:.04'/><path d='");
fgets(b,99,f);++h)for(i=0;i<w;)b[i++]-35||printf("M%d %dh1v1h-1Z",i,h+2);puts("'/>");
for(f=fopen(gets(b),"r");fgets(b,99,f);)sscanf(b,"%d%d%d",&i,&h,&w)>2&&
printf("<text x='%d.1' y='%d.3' style='font-size:.3px'>%d</text>",w,h,i);puts("</svg>");}

```

When run it gets the two filenames on two separate lines of standard input; first the grid file, then the numbers file.

The logic in this one is actually quite simple. The format of the SVG allows it to create all the elements in any order (instead of going from top to bottom as with the ASCII output solution). The size is due almost entirely to SVG boilerplate.

But the resulting image looks great!

**Edited to add:** Here's a shorter version (517 chars) that output to a specific resolution. This allows the code to use more default settings, but at the (to my mind) prohibitive cost that the SVG no longer auto-resizes in your web browser.

```
char*f,b[99];h,w;main(i){fscanf(f=fopen(gets(b),"r"),"%d%d%*[\n]",&h,&w);for(
printf("<svg xmlns='http://www.w3.org/2000/svg'><path d='M1 1",i=w,h);i--;)
printf("v%d0v-%d0h50",h*5,h*5);for(;h--;)printf("v50h-%d0h%d0",w*5,w*5);for(
puts("' style='fill:none;stroke:#000'/><path d='");fgets(b,99,f);++h)
for(i=-1;++i<w;)b[i]-35||printf("M%d1 %d1h50v50h-50Z",i*5,h*5+5);puts("'/>");
for(f=fopen(gets(b),"r");fgets(b,99,f);)sscanf(b,"%d%d%d",&i,&h,&w)>2&&
printf("<text x='%d3' y='%d5'>%d</text>",w*5-5,h*5-4,i);puts("</svg>");}

```

# Answer
> 3 votes
# Haskell, 328 characters

```
import System
main=do(g:d)<-mapM(fmap lines.readFile)=<<getArgs;mapM_ putStrLn$g% \i k->[t|x<-d,y@(c:_)<-x,c/='#',(t,q)<-lex y,w q==i,k<1]
(s:g)%n=[q|(i,x)<-e g,q<-b s:[c['|':f#n[i,j]k|(j,f)<-e x]++"|"|k<-[0..2]]]++[b s]
'#'#_="#####";_#n=take 5$c n++"     ";b n='+':([1..w n!!1]>>"-----+")
e=zip[1..];c=concat;w=map read.words

```

# Answer
> 2 votes
## C, 375 chars

```
char b[99];g[999],*r=g,*f,i,j,w;main(n){
for(fscanf(f=fopen(gets(b),"r"),"%*d%d%*[\n]",&w);fgets(b,99,f);)
for(i=0;i<w;)*r++=-(b[i++]==35);
for(f=fopen(gets(b),"r");fgets(b,99,f);)
sscanf(b,"%d%d%d",&n,&j,&i)?g[j*w-w+i-1]=n:0;
for(f=g;f<=r;f+=w){for(i=w;i--;)printf(" ----");puts("");
if(f<r)for(j=3;j--;puts("|"))
for(i=0;i<w;printf(~n?n&&j>1?"|%-4d":"|    ":"|////",n))n=f[i++];}}

```

The two input filenames are entered on standard input, each on a separate line. The grid is rendered in ASCII on standard output. Yes, it's a lousy UI, but anything better cost characters. I took to invoking it like so:

```
printf "%s\n%s" grid.txt numbering.txt | ./crosswd-render > render.txt

```

The program should correctly handle things like commented lines in the numbering file.

# Answer
> 2 votes
### Scala 463, output-format: html

```
object H extends App{val z=readLine.split("[ ]+")map(_.toInt-1)
val d="\t\t<td width='50' height='50'"
println("<html><table border='1'><tr>")
val b=(0 to z(0)).map{r=>readLine}
var c=0
(0 to z(0)).map{
y=>(0 to z(1)).map{
x=>if(b(y)(x)==' '&&((x==0||b(y)(x-1)==35)||(y==0||b(y-1)(x)==35))){
c+=1
println(d+"valign='top'>"+c+"</td>")}
else println(d+{if(b(y)(x)!=' ')"bgcolor='#0'>"else"> "}+"</td>")}
println("\t</tr>\n\t<tr>")}
println("</table></html>")
}

```

Sample output

# Answer
> 2 votes
**PostScript ~~(435)~~ (434)**

```
[/r{currentfile 999 string readline pop}/p{pop}/x{exch}/T{translate}/S{scale}/G{gsave}/R{grestore}/_( )>>begin/Courier 1 selectfont
20 20 S
.05 setlinewidth{r token
p x p
dup 3 x 3 add
T
G G{R
0 -1 T
G
_ 0
r{0 0 1 1
4 index 35 eq{rectfill p}{rectstroke
put
.3 .1 moveto
_ show}ifelse
1 0 T _ 0}forall}repeat
R R
1 -1 S -.9 -.7 T{{r
dup 0 get 35 ne{( )search
p 3 2 roll
cvx exec
G
x
T
.4 -.4 S
0 0 moveto show
p
R}if}loop}stopped}exec

```

Un-golfed with data:

```
%!
<<
  /r{currentfile 999 string readline pop}
  /p{pop}
  /x{exch}
  /T{translate}
  /S{scale}
  /G{gsave}
  /R{grestore}
  /_( )
>>begin
/Courier 1 selectfont
% In theory, 20 20 scale isn't needed,
% but it would make the whole thing very tiny when printed
% (on screen it doesn't matter too much, it can be zoomed)
20 20 S
.05 setlinewidth
{ % exec
% Read number of lines
r token                          % restString numberOfLines true
% Discard rest of line (Contains number of columns.
% It becomes clear implicitly from number of letters in a line of grid definition)
p x p                            % numberOfLines
% Move to where the top line starts
dup 3 x 3 add                    % numberOfLines x y
T                                % numberOfLines
G G
{ %repeat
  R
  % Move to next line
  0 -1 T
  G
  _ 0
  r                              % ( ) 0 line
  { %forall                      % ( ) 0 char
    0 0 1 1                      % ( ) 0 char 0 0 x y
    % Check whether char is a hash
    4 index 35 eq{ %ifelse
      4 copy rectfill
    }if
    rectstroke                   % ( ) 0 char
    put                          % -/-
    .3 .1 moveto
    _ show
    1 0 T
    _ 0                          % ( ) 0
  }forall                        %
}repeat
R R
% Now, render the numbers according to the numbering definitions
1 -1 S -.9 -.7 T
{{
  r
  %Check whether this is a comment
  dup 0 get 35 ne{               % line
    % Split at the first tab
    %TODO: Ust tab instead of space
    ( )search                    % (y x) tab number true
    p 3 2 roll                   % tab number (y x)
    cvx exec                     % tab number y x
    G
    x                            % tab number x y
    T                            % tab number
    .4 -.4 S
    0 0 moveto show              % tab
    % This pop can be eliminated in theory to save two characters,
    % but the operand stack will continue to grow
    p
    R
  }if
}loop}stopped
}exec
15 15
     #   #

       #     ##
##   #   #
    #     #
   #    #
       #
      #    #
    #     #
    K#   #   ##
##  I  #
    L
    N
    S#   #
#i m n   figure(number), row, col
1 1 1
2 1 2
3 1 3
4 1 4
5 1 5
6 1 7
7 1 8
8 1 9
9 1 11
10 1 12
11 1 13
12 1 14
13 1 15
14 2 1
15 2 6
16 2 10
17 3 1
18 4 1
19 4 9
20 5 3
21 5 7
22 5 8
23 5 11
24 5 14
25 5 15
26 6 1
27 6 2
28 6 6
29 6 10
30 6 12
31 7 1
32 7 5
33 7 10
34 7 11
35 8 1
36 8 4
37 8 9
38 9 1
39 9 8
40 9 13
41 10 1
42 10 6
43 10 7
44 10 12
45 11 1
46 11 5
47 11 7
48 11 11
49 12 3
50 12 6
51 12 9
52 12 10
53 12 14
54 12 15
55 13 1
56 13 2
57 13 8
58 14 1
59 15 1
60 15 7
60 15 11

```

# Answer
> 1 votes
**Postscript, non-combatant.**

Inspired (yet again) by your related question on SO, I've made a reference version in Postscript using file-IO. It also creates a derived fixed-width font so the grid data is simply passed to `show`.  is an empty box and `#` is a filled box. Any other ascii character is drawn as a small Times-Roman glyph surrounded by a box.

This program makes use of a ghostscript feature which may not be present in all Postscript interpreters. If ghostscript is invoked with the `--` option, it passes command-line arguments to the postscript program in an array of strings named /ARGUMENTS. So you need to invoke the program like this `gs -- xw-io.ps grid-file number-file`.

```
%!

ARGUMENTS{}forall
/numfile exch (r) file def
/gridfile exch (r) file def

/q{0 0 moveto 1 0 lineto 1 1 lineto 0 1 lineto closepath}def
/X<</FontType 3/FontBBox[0 0 1 1]/FontMatrix[1 0 0 1 0 0]
    /Encoding StandardEncoding
    /BuildChar{
        1 0 0 0 1 1 setcachedevice
        .001 setlinewidth
        q stroke
        dup 35 eq { pop
            q fill
        }{
            .3 .1 moveto
            .1 .1 scale
            /Times-Roman 8 selectfont
            (?)dup 0 4 3 roll put show
        }ifelse pop}
>>definefont pop /X 30 selectfont
40 700 moveto {
    gridfile 2{dup token pop exch}repeat pop pop
    {
        gridfile =string readline{
            dup length 0 ne{
                show currentpoint exch pop 30 sub 40 exch moveto
            }{clear exit}ifelse
        }{clear exit}ifelse
    }loop
    /Times-Roman 8 selectfont
    {
        40 700 moveto
        numfile =string readline{
            dup length 0 ne{
                dup 0 get 35 ne{
                    cvx exec
                    1 sub 30 mul 2 add exch
                    1 sub -30 mul 22 add rmoveto
                    (   )cvs show
                }{clear}ifelse
            }{clear}ifelse
        }{clear exit}ifelse
    }loop showpage
}exec

```

---
Tags: code-golf, ascii-art, crossword, graphical-output
---


title: The smallest Chess arbiter

text:
# Question
Title: The smallest Chess arbiter
Write a program, which, upon gazing at a chess table, can say whether there is a check or a checkmate.

**Input**: a chess table in text form, the last line of the input being the first rank (the starting line of White)

The starting position in this input would look like this (space is an empty square, capital letters are White): why aren't the spaces displayed here?

```
rnbqkbnr
pppppppp

PPPPPPPP
RNBQKBNR

```

The program should print one or more of the following (without quotes, of course), depending on the situation:

* "The White King is in check!" *(if already in checkmate, don't display this!)*
* "The Black King is in check!" *(if already in checkmate, don't display this!)*
* "The White King is in checkmate!"
* "The Black King is in checkmate!"
* "White is in stalemate!" *(There would be a stalemate if White moved - **optional**)*
* "Black is in stalemate!" *(There would be a stalemate if Black moved - **optional**)*
* "Both kings are safe for now." *(if none of the above apply)*

The input is guaranteed to be correct and be a legal chess position (no two kings of the same color, no two kings in check, etc.).

**Score:**

The score is the character count, lowest wins, not sooner than 10 days after the first valid answer. If the optional stalemate evaluation is implemented, the size will be decreased by 20% (for this situation, assume en-passant cannot be performed).

# Answer
## C, 837-20%=669.6 chars

Based on this answer. You can see some explanations about the implementation there.
The original is golfed quite well, the modifications not so much, so there's room for improvement.
I also wouldn't be surprised to find bugs, my QA wasn't very rigorous.

```
char*r=" KPNBRQ  kpnbrq $ ,&)$wxy()879()8(6:GI(",B[256],*b=B,i,Q,s,*X[]={"Stalemate","Checkmate","","Check"};
e(x,d,m,V,c,r,n,p){
    p=b[x];
    return(m/r?
        n=x+d*r,
        p-2-8*(d<0)&&!(n&136)&&(b[n]?r=8,p&8^b[n]&8&&c&65^64:c&65^65)&&
        ((V?v(n,x):b[n]%8==1&&(s&=~((b[n]>7?8:2)))),e(x,d,m,V,c,r+1))
    :0)||d>0&&e(x,-d,m,V,c,1);
}
d(x,v,m,i)char*m;{
    (i=*m-40)? e(x,i%64,b[x]%8-2?b[x]&4?7:1:(x/16-1)%5|i%2?1:2,v,i,1),d(x,v,m+1):0;
}
v(t,f){
    b[t]%8-1?
        (s&(b[f]>7?8:2))==0?
            bcopy(B,b+=128,128),
            s|=(b[f]>7?8:2),
            b[f]^=b[t]=b[f],
            a(b[t]<8,63),
            b=B
        :0
    :
        (s|=b[f]>7?1:4);
}
a(c,n){
    b[i=n*2-n%8]&&b[i]/8==c?d(i,!Q++,r+r[b[i]%8+15]-10),Q--:0;n--&&a(c,n);
}
p(c,t){
    return(t=c?s%4:s/4)!=2&&printf("%s%s%s is in %s\n",t?"The ":"",c?"White":"Black",t?" king":"",X[t]);
}
main(){
    for(;gets(b);b+=8)for(;*b;b++)*b=strchr(r,*b)-r;b=B;
    a(0,63);
    a(1,63);
    p(0)||p(8)||puts("Both kings are safe for now");
}

```
> 5 votes

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


# Question
Title: Output a shuffled deck using random input
## Input/Output:

**Input**: A uniformly random, infinitely long, string of '0's and '1's, taken from stdin. The string is assumed to be truly random, not pseudo-random. It is uniform in that each character is equally likely to be a '0' or '1'.

Careful! The input is infinitely long, so you can't store it all in memory using a function like raw\_input() in python. If I'm not mistaken, golfscript will fail with infinite input, since it pushes the entire input onto the stack prior to running.

**Output**: A uniformly random shuffled standard deck, without jokers. It is uniform in that all orderings are equally likely.

Each card in the output is it's rank, A, 2-9, T, J, Q or K concatenated with it's suit, c, d, h or s. For example, the 10 of spades is `Ts`

The cards of the deck should be separated by spaces.

You may not use built-in random libraries or functions because they are not truly random, only pseudo-random.

## Example input

You may use the following python script to pipe input into your program:

```
import sys, random
try:
    while True:
        sys.stdout.write(str(random.randint(0,1)))
except IOError:
    pass

```

If you save the script as rand.py, test your program with `python rand.py | your_program`

In python 3 it runs as expected, but in python 2.7 I get an error message after my program's output, but only after everything's done, so just ignore the error message.

## Example output:

Here's how the deck should be printed if it happened to be shuffled into a sorted order:

```
Ac 2c 3c 4c 5c 6c 7c 8c 9c Tc Jc Qc Kc Ad 2d 3d 4d 5d 6d 7d 8d 9d Td Jd Qd Kd Ah 2h 3h 4h 5h 6h 7h 8h 9h Th Jh Qh Kh As 2s 3s 4s 5s 6s 7s 8s 9s Ts Js Qs Ks

```

## Scoring:

This is a code golf. Shortest code wins.

## Example program:

Here is a python 2.7 solution, not golfed.

```
import sys
def next():
    return int(sys.stdin.read(1))==1
def roll(n):
    if n==1:
        return 0
    if n%2==0:
        r=roll(n/2)
        if next():
            r+=n/2
        return r
    else:
        r=n
        while(r==n):
            r=roll(n+1)
        return r
deck = [rank+suit for suit in 'cdhs' for rank in 'A23456789TJQK']
while len(deck)>0:
    print deck.pop(roll(len(deck))),

```

# Answer
> 7 votes
### Ruby, 89 87 characters

```
l=*0..51;l.map{l-=[i=l[gets(6).to_i 2]||redo];$><<'A23456789TJQK'[i/4]+'cdhs'[i%4]+' '}

```

*Edit:* previous version

```
l=*0..51;(l-=[i=l[gets(6).to_i 2]];i&&$><<'A23456789TJQK'[i/4]+'cdhs'[i%4]+' ')while l[0]

```

# Answer
> 3 votes
## Perl, 80 chars

here is another implementation that does not suffer from the bias and is two characters shorter:

```
$/=1x9;$_=A23456789TJQK;s/./$&s$&c$&d$&h/g;%h=map{<>.$_,"$_ "}/../g;say values%h

```

---

### old implementation (82 chars):

```
$/=1x9;$_=A23456789TJQK;s/./$&s$&c$&d$&h/g;say map/..$/&&$&.$",sort map<>.$_,/../g

```

### old implementation description:

```
# set input record separator (how internal readline() delimits lines) to "11111111"
$/ = 1x9;

# constructs a string representation of all 52 cards: "AsAc(...)KdKh"
$_ = A23456789TJQK; s/./$&s$&c$&d$&h/g;

# for each pair of characters (each card) in the string $_
foreach $card (/../g)
{
    # read from STDIN until $/ is found (this may NEVER occur!), which
    # results in a random string of 1s and 0s
    $weight = <>;

    # append the card identifier onto the random string
    $card = $weight . $card;

    # add this new card identifier to a new list
    push @cards, $card;
}

# sort the cards with their random string prefix
sort @cards;

# for each card in the "randomly sorted" list
foreach $card (@cards)
{
    # capture the final two characters from the card (the rank and suit),
    # and append a space onto them
    $card =~ /..$/;
    $card = $card . $";

    print $card;
}

```

# Answer
> 3 votes
## C, 197 178 161 chars

**EDIT**: Using a new random function, which is much shorter - reads a 4-digit integer `s` and uses `s%64`. Each 6-digit decimal number made of 0 and 1 only, taken `%64` results in a unique result, so the randomness is good.
This approach consumes much more random bits, but is significantly shorter.

```
B[52],t,s,i=104;
r(){scanf("%6d",&s);s%=64;s>i&&r();}
main(){
    for(;i--;)B[i%52]=i<52
        ?r(),t=B[s],B[s]=B[i],printf("%c%c\n","23456789ATJQK"[t/4],"cdhs"[t%4]),t
        :i-52;
}

```

The basic logic is simple - initialize an array of 52 ints with 0..51, shuffle (randomally replace element x with another from the range 0..x), print formatted (n/4=rank, n%4=suit).
One loop, that runs 104 times, does initialization (first 52 runs), shuffling and printing (last 52 runs).
A random number is generated by pulling `n` random bits, until `1<<n` is at least the desired maximum. If the result is more than the maximum - retry.

# Answer
> 3 votes
# Python 122

```
import sys
D=[R+S for S in'cdhs'for R in'A23456789TJQK']
while(D):
    x=int(sys.stdin.read(6),2)
    if x<len(D):print D.pop(x)

```

Explanation:

Unused cards are stored in D. This simply gets the next valid random index from the input stream and pops that element from D.

Unless I am missing something, there shouldn't be a bias. The script will throw out any invalid indices \> `len(D)`, but this doesn't result in a bias for lower numbers because each successive pop will reduce the index of each element past than i.

# Answer
> 3 votes
### unix shell ~ 350

This is not short or pretty, nor is it efficient, however I was wondering how hard it would be to do this with standard unix shell utilities.

This answer chops up the infinite binary string into 6 bit lengths and only chooses those that are in the correct range (1-52), here the infinite binary string is simulated by urandom and xxd:

```
</dev/urandom xxd -b | cut -d' ' -f2-7 | tr -d ' \n'

```

The chopping and selection is done with fold, sed and bc:

```
random_source | {echo ibase=2; cat | fold -w6 | sed -r 's/^/if(/; s/([^\(]+)$/\1 <= 110100 \&\& \1 > 0) \1/'}

```

This produces lines such as:

```
if(101010 <= 110100 && 101010 > 0) 101010

```

Which can be directed into bc.

From this stream of numbers, the sequence of the deck is chosen like this (I'm using zsh, but most modern shells should be adaptable to this):

```
deck=({1..52})
seq_of_numbers | while read n; do
  if [[ -n $deck[n] ]]; then
    echo $n; deck[n]=""
    [[ $deck[*] =~ "^ *$" ]] && break
  fi
done

```

The randomized number sequence now needs to be changed into card names. The card name sequence is easily generated with GNU parallel:

```
parallel echo '{2}{1}' ::: c d s h ::: A {2..9} T J Q K

```

Combining the output from the last two commands with paste and sorting on the numbers:

```
paste random_deck card_names | sort -n | cut -f2 | tr '\n' ' '

```

The whole thing as one monstrous one-liner (only tested in zsh):

```
paste \
  <(deck=({1..52}); \
    </dev/urandom xxd -b | cut -d' ' -f2-7 | tr -d ' \n' |
      {echo ibase=2; fold -w6 | sed -r 's/^/if(/; s/([^\(]+)$/\1 <= 110100 \&\& \1 > 0) \1/'} |
      bc |
      while read n; do
        if [[ -n $deck[n] ]]; then
          echo $n; deck[n]=""
          [[ -z ${${deck[*]}%% *} ]] && break
        fi
      done) \
  <(parallel echo '{2}{1}' ::: c d s h ::: A {2..9} T J Q K) |
sort -n | cut -f2 | tr '\n' ' '

```

### Edit - added bash version

Here is a version that works in bash. I removed the in-shell `{ }` and array indexes are zero based. Array emptiness is checked with parameter expansion, slightly more efficient and also adopted in the example above.

```
paste \
  <(deck=($(seq 52)); \
    </dev/urandom xxd -b | cut -d' ' -f2-7 | tr -d ' \n' |
      (echo ibase=2; fold -w6 | sed -r 's/^/if(/; s/([^\(]+)$/\1 <= 110100 \&\& \1 > 0) \1/') |
        bc |
        while read n; do
          if [[ -n ${deck[n-1]} ]]; then
            echo $n
            deck[n-1]=""
            [[ -z ${deck[*]%% *} ]] && break
          fi
        done \
  ) \
  <(parallel echo '{2}{1}' ::: c d s h ::: A {2..9} T J Q K) |
sort -n | cut -f2 | tr '\n' ' '; echo

```

# Answer
> 2 votes
## K&R c -- 275

* **v3** Index into the string literals directly
* **v2** Suggestion from luser droog in the comments to use strings and replaced remaining `char` literals with `int` literals

Golfed:

```
#define F for(i=52;--i;)
#define P putchar
M=1<<9-1,i,j,k,t,v,s,a[52];r(){t=0,j=9;while(--j)t=t<<1|(getchar()==49);
return t;}main(){F a[i]=i;F{k=i+1;do{j=r();}while(j>M/k*k-1);j%=i;t=a[i];
a[i]=a[j];a[j]=t;}F{s=a[i]&3;v=a[i]>>2;P(v>7?"TJQKA"[v-8]:v+50);
P("cdhs"[s]);P(32);}}

```

Pretty much brute force here. I just read nine bits from the input to form a minimal RNG output, and make the usual redraw-if-the-unused-values-at-the-end modulus reduction to get uniform output to power a selection shuffle.

This un-golfed version differs in that it takes the input from `/dev/urandom` rather than from the described input format.

```
#include <stdio.h>
M=1<<8-1, /* RANDMAX */
  i, j, k, /* counters */
  t, /* temporary for swapping, and accumulating */
  a[52]; /* the deck */
r(){ /* limited, low precision rand() that depends on a random stream
    of '0' and '1' from stdin */
  t=0,j=9;
  while(--j)t=t<<1|(getchar()&1);
  return t;
}
main(){
  for(i=52;--i;)a[i]=i;  /* initialize the deck */
  for(i=52;--i;){
    /*  printf("shuffling %d...\n",i); */
    k=i+1;
    do { /* draw *unifromly* with a a-unifrom generator */
      j=r();
      /* printf("\t j=0x%o\n",j); */
    }while(j>M/k*k-1); /* discard values we can't mod into evently */
    j%=i;
    t=a[i];a[i]=a[j];a[j]=t; /* swap */
  }
  for(i=52;--i;){ /* output the deck */
    j=a[i]&3;
    k=a[i]>>2;
    putchar(k>7?"TJQKA"[k-8]:k+'2');
    putchar("cdhs"[j]);
    putchar(' ');
  }
}

```

# Answer
> 0 votes
# PHP, 158 chars

Newlines have been added to stop the code block gaining scrollbars, they can safely be removed.

```
for($i=52,$x='shdcKQJT98765432A';$i--;$c[]=$x[4+$i%13].$x[$i/13]);
while(ord($i=fgetc(STDIN)))$c[$i]^=$c[$a]^=$c[$i]^=$c[$a=2+($a+++$i)%50];
die(join(' ',$c));

```

Before I get told to add a `<?php`, let it be known you can invoke PHP without this tag quite easily, using: `cat golf.php | php -a`

De-golfed and commented:

```
// Abuse of the for construct to save a bit of space, and to make things more obscure looking in general.
for (
    // Card suit and number are reversed because we're using a decrementor to count
    // down from 52, instead of up to 52
    $i = 52,
    $x = 'shdcKQJT98765432A';
    // Condition AND per-loop decrement
    $i--;
    // Add a new element to the array comprising of $i mod 13 + 4 (to skip suit ids)
    // followed by simply $i divided by 13 to pick a suit id.
    $c[] =
        $x[4 + $i % 13] .
        $x[$i / 13]
);

while(

    // Assignment inside the condition, a single character from input.
    ord($i = fgetc(STDIN))
)
    // In-place swap. Shorter than using a single letter temporary variable.
    // This is the pseudo-random shuffle.
    $c[$i] ^=
    $c[$a] ^=
    $c[$i] ^=
    $c[
        // We use the input (0 or 1) to identify one of two swap locations at the
        // start of the array. The input is also added to an accumulator (to make
        // the increments "random") that represents a swap destination.
        $a = 2 + ($a++ + $i) % 50
    ];

// Dramatic way of doing "echo" in the same space.
die(
    join(' ', $c)
);

```

There are two expected errors, that do not affect the output of the program.

The first is because `$a` is not initialised, but the NULL is converted to 0 and the program continues.

The second is because the character stream seems to get a newline from somewhere, even if it's not supplied (good ol' PHP), and that is an undefined index in the array. It's the last character of input, and does not affect output.

---
Tags: code-golf, random
---


# Question
Title: Swap 2 objects, without using a temporary variable
There are two objects:

```
Object1, Object2

```

You can easily swap them by:

```
Object3 = Object1
Object1 = Object2
Object2 = Object3

```

However, you must solve this problem by using no temporary object and Object1 should be changed to Object 2. (and vice versa)

# Answer
> 4 votes
## Python

I'll say it first.

```
object1, object2 = object2, object1

```

# Answer
> 2 votes
If you have access to the memory address of these objects, you can swap them by xor-ing their addresses.

```
// return 0 for success, 1 for error
int swap(void *object1, void *object2, int size)
{
    for (int i = 0; i < size; i++)
    {
        char *x = (char *)(object1 + i);
        char *y = (char *)(object2 + i);
        if (x == y)
            return 1;
        *x ^= *y;
        *y ^= *x;
        *x ^= *y;
    }
    return 0;
}

```

per dmckee suggestion for clarity

# Answer
> 2 votes
## Mathematica

A standard feature:

```
a = 1; b = 2;
Print[a, " ", b];
{a, b} = {b, a};
Print[a, " ", b];

```

Output

```
(*
1 2

2 1
*)

```

# Answer
> 2 votes
**PostScript**

In PostScript, it's common to use the stack instead of named variables, so a simple

```
exch

```

would do the job. But if you have variables, you can do it like

```
/a 1 def
/b 2 def
/a b /b a def def

```

# Answer
> 1 votes
## Perl

```
($object1, $object2) = ($object2, $object1);

```

Using Perl's list assertions feels like cheating, but it's a pretty common feature.

# Answer
> 1 votes
# PHP

Objects / arrays / resources:

```
list($a, $b) = [$b, $a];

```

Integers / booleans / strings of equal length:

```
$a ^= $b ^= $a ^= $b;

```

# Answer
> 1 votes
## Forth

```
swap

```

As i have to include more than 30 characters, here's a link to a Forth primer

---
Tags: code-challenge
---


title: Scale from key and mode

text:
# Question
Title: Scale from key and mode
Most of you probably know the C major scale:

```
C D E F G A B C

```

The major scale is characterised by the intervals between adjacent notes, which measured in semitones are:

```
2 2 1 2 2 2 1

```

From these intervales, we can construct any major scale starting in any note (the key of the scale). The 12 notes in our 12-tone equal temperament tuning system are:

```
C C♯ D D♯ E F F♯ G G♯ A A♯ B

```

equivalently (substituting some enharmonic equivalents):

```
C D♭ D E♭ E F G♭ G Ab A B♭ B

```

with a semitone between each pair of adjacent notes.

Each scale has to have the seven notes in order, starting from the key. Otherwise, you could have two notes in the same line of the pentagram, which would be confusing. So, in G# major/ionian, you have F## instead of G; musicians will just look at where in the pentagram is the note, they already have learned the accidentals for each scale. Indeed, in G# major, F## is represented in the line of F## without accidentals, the accidentals are in the key signature - but since that key signature would require 2 sharps for F, usually this is notated as Ab major.

Shifting the `2 2 1 2 2 2 1` intervals, we arrive at seven different modes of the diatonic scale:

* **Ionian**: `2 2 1 2 2 2 1` \- corresponds to the major scale
* **Dorian**: `2 1 2 2 2 1 2`
* **Phrygian**: `1 2 2 2 1 2 2`
* **Lydian**: `2 2 2 1 2 2 1`
* **Mixolydian**: `2 2 1 2 2 1 2`
* **Aeolian**: `2 1 2 2 1 2 2` \- corresponds to the natural minor scale, and to the melodic minor scale when descending (when ascending, the melodic minor scale has raised 6th and 7th degrees. There is also a harmonic minor scale, with a raised 7th degree compared to the natural minor).
* **Locrian**: `1 2 2 1 2 2 2`

So, the challenge is to write a program that takes as input (via *stdin*) a key and a mode and outputs (via *stdout*) the corresponding scale. Some test cases (*stdin*(`key` `mode`) =\> *stdout*(`scale`)):

```
Input:              Output:
C mixolydian   =>   C D E F G A Bb
F mixolydian   =>   F G A Bb C D Eb
G mixolydian   =>   G A B C D E F
G# ionian      =>   G# A# B# C# D# E# F##
Bb aeolian     =>   Bb C Db Eb F Gb Ab

```

Further references:
How many (major and minor) keys are there? Why?

# Answer
> 7 votes
### GolfScript, 96 characters

```
" "/~5<{+}*7%"v]nwm[{"=2*2base(;\(" #"@?]{.1>))["b""""#"..+]=+\[~@(@+@(7%65+\1$7%4%0>-]}7*;]" "*

```

Golfscript solution which can be tested online.

Note: As in the examples the key has to be upper case while mode has to be given in lower case.

Examples:

```
>C lydian
C D E F# G A B

>C mixolydian
C D E F G A Bb

```

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


title: Match up to 10 in an array

text:
# Question
Title: Match up to 10 in an array
## Challenge

Given an array of single digit number, work out if any 2 of them add up to 10 and print them out

## Example

**Input**

> (1,2,3,4,5,5,6,7)

This returns `((4,6),(5,5),(3,7))`

**Input**

> (1,2,3,4,5)

This returns `()`. as there is only one 5

**Input**

> (5,5,5,5,5)

This returns `((5,5),(5,5))` as there is odd number of 5s and each 5 can be used only once

## Rules

Here are the rules!

* Assume input will only be an unsorted array of positive single digit integers
* Each number will be pair up only once, which means if there are three 5s it only form 1 pair (5,5). If there are (3,3,7) it will only form 1 pair (3,7)
* For the input: You can use any type of parentheses(or lack of) as long as readers can tell that the input is a single array of numbers.
* For the output: It must look like an array of pairs. Where the array is the same form as your input.(If you did not use any parenheses in your input, you have to use some kind of symbols so that any readers can tell they are pairs in an array)

## Test Cases

```
(1,2,3,4,5,5,6,7) =((4,6),(5,5),(3,7))
(1,2,3,4,5) = ()
(5,5,5,5,5) = ((5,5),(5,5))
(1,2,3,3,4,5,6,7)=((3,7),(4,6))
(9,8,7,6,4,4,3,1)=((9,1),(7,3),(6,4))

```

## Good luck!

The `shorter` an answer is, the better!

Edit 1: update the rules and Testcases from comments

Edit 2: update rules to define format of input.

Edit 3: update rules to define format of output. trying to be as accommodating as possible.

# Answer
> 7 votes
### GolfScript, 45 42 37 chars

```
~{([.~11+.])@{1$=.{2$p!\}*!},\;\;.}do

```

The new approach does also take arrays with a single item as input. Moreover, it is several chars shorter.

Previous version:

```
~{$(\)@.2$+10-.{0>{\}*;+}{;[\]p}if.,1>}do;

```

The algorithm used in this code is described as follows:

* Sort the array.
* Take the sum of the first and the last item.
    + If the sum is 10 print both numbers and remove them from the array.
    + If the sum is greater than 10, discard the larger number.
    + If the sum is less than 10, discard the smaller number.
* Loop until the array contains only a single digit or is even empty.

The code expects an array of at least two digits on STDIN.

Examples (see online):

```
>[9 8 7 6 4 4 3 1]
[1 9]
[3 7]
[4 6]

>[5 5 5 5 5]
[5 5]
[5 5]

```

# Answer
> 9 votes
# Python 2.7 (70)

```
y=input()
while y:
 g=10-y.pop()
 if g in y:y.remove(g);print(g,10-g)

```

Testcases:

```
$ echo '[1, 2, 3, 4, 5, 5, 6, 7]' | python p.py
(3, 7)
(4, 6)
(5, 5)

$ echo '[1,2,3,4,5]' | python p.py

$ echo '[5,5,5,5,5]' | python p.py
(5, 5)
(5, 5)

$ echo '[1,2,3,3,4,5,6,7]' | python p.py
(3, 7)
(4, 6)

$ echo '[9,8,7,6,4,4,3,1]' | python p.py
(9, 1)
(7, 3)
(6, 4)

```

One byte extra for the nice parenthesis.

# Answer
> 5 votes
## Javascript, ~~188~~ ~~183~~ ~~181~~ ~~153~~ ~~141~~ ~~121~~ ~~123~~ ~~112~~ *105* ~~98~~ chars

Golfing in JS is somewhat difficult, but I just wanted to have a bash on this problem, so here's the code:

```
for(a=eval(prompt(i=o=[]));k=a[j=++i];)for(;p=a[--j];)k+p-10||(k=a[i]=a[j]=-o.push([p,k]));console.log(o)

```

Input: e.g. `[1,2,3,3,4,5,6,7]`. Output e.g. `[[4,6],[3,7]]` to the console.

~~105-\>98: Used Daniel's awesome algorithm to completely rewrite the code! See his answer for a readable algorithm.~~ Completely messed up stuff so reverted to **105** chars.

112-\>105: Initialised `i` to zero, used output of `o.push` to set `k` (`k=a[i]=a[j]=-o.push...`) and logged output to console instead of alerting to eliminate `"["+` and `+"]"` since the console outputs nicely already.

123-\>112: Now removed outer brackets in output, since golfscript may :) Also finally applied suggestion of removing `|=0`.

121-\>123: Changed `o+="("+p+","+k+"),"` to `o.push("("+[p,k]+")")` (adds 2 chars :( ) and made `o` an array instead of a string (`o=""`-\>`o=[]`). Now output isn't wrong anymore (like `((5,5),(5,5),)`).

141-\>121: From now on assumed that the question meant that we could get input in the language's array format, which in JS's case is `[a,b,c,...]` and made `o`, the output "accumulator" a string instead of an array (`o.push(...),`-\>`o+=...,`).

153-\>141: Reset array entries instead of removing them after usage.

181-\>153: Applied changes to `u=[]`, rearranged loops, `a[i]`&`a[j]`-\>temp vars, converted if logic and converted int logic to `a[i]|=0`.

183-\>181: Replaced `i<=0` with `i+1` and the same for `j`.

188-\>183: Placed `o=[]` inside `prompt()` (~~`;`~~) and replaced `for(j=i;` with `for(j=i-1;` (~~`i==j&&`~~).

*(Thanks mellamokb, Paul Walls and ryan!)*

# Answer
> 3 votes
## J, 54 53 50 46 45 44 characters

```
(>:,.9&-)I.<.4({.,-:@{::)(<.|.)+/|:(1+i.9)=/

```

Usage:

```
   (>:,.9&-)I.<.4({.,-:@{::)(<.|.)+/|:(1+i.9)=/5 5 5 5 5
5 5
5 5
   (>:,.9&-)I.<.4({.,-:@{::)(<.|.)+/|:(1+i.9)=/9 8 7 6 4 4 3 1
1 9
3 7
4 6

```

The algorithm is basically:

* count the instance of each number `+/|:(1+i.9)=/`
* pair the counts of each pair that would add to 10 `(<.|.)` (so 1 and 9, 2 and 8 etc.)
* take the minimum of those counts (so if you have three 9s but only one 1, you'll only have one `1 9` pair) and drop everything after the first five pairs
* the 5s are a special case so divide that by 2 (`<.4({.,-:@{::)` implements both previous steps)
* take the first five items of the list and output the number and 10`-`the number `(>:,.9&-)I.`

# Answer
> 3 votes
## Python (142)

Input should be given with square brackets instead of round brackets. http://ideone.com/p2QR11

```
from itertools import*
a=input()
c=lambda:[i for i in product(a,a[1:])if sum(i)==10]
d=c()
while d:print d[0];[a.remove(j)for j in d[0]];d=c()

```

Algorithm:

```
1. Get input
2. Generate all pairs of input where the sum is 10
3. If there are no pairs, then END PROGRAM
4. Take the first pair's items and remove them from the input
5. Go back to step 2

```

If seriously malformed output is allowed **(90)**: http://ideone.com/GR762f

```
a=input()
c=a.count
for i in range(6):print(`i`+`10-i`+' ')*(min(c(i),c(10-i))/(1+(i==5)))

```

# Answer
> 3 votes
## C, 142,138, 124

```
char*p,*q;
main(int a,char**s){
    for(p=s[1];*p;p++)
        if(q=strchr(p+1,106-*p))a=*q=printf("%c(%c,%c)",38+a,*p,*q);
    puts("()"+a/6);
}

```

Testing:

```
./a.out "(1,2,3,4,5,5,6,7)"
((3,7),(4,6),(5,5))

./a.out "(1,2,3,4,5)"
()

./a.out "(5,5,5,5,5)"
((5,5),(5,5))

./a.out "(1,2,3,3,4,5,6,7)"
((3,7),(4,6))

./a.out "(9,8,7,6,4,4,3,1)"
((9,1),(7,3),(6,4))

```

Implementation notes:

* initially a=2 (program has two args), set to 6 (printf prints 6 chars) once a match occurs
* 106 = '0'+'0'+10, i.e. uses the sum of the ascii codes
* 38+a, is either 44/40, i.e. '(' or ','
* By setting string characters to 6 it ensures they wont add to 106 on other passes
* "()"+a/6, is either "()" or ")"

# Answer
> 3 votes
# Javascript - 131 129 125 chars

```
for(i=eval(prompt(r=[])),k=j=i.length;j--;)for(m=k;m--;)if(m!=j&&i[j]+i[m]==10)r.push([i[j],i[m]]),i[j]=i[m]=0;console.log(r)

```

I assume, the order of and in the nested result arrays is not compulsory :)

Evaluated test cases:

```
[1,2,3,4,5,5,6,7] returns [[7,3],[6,4],[5,5]]
[1,2,3,4,5]       returns []
[5,5,5,5,5]       returns [[5,5],[5,5]]
[1,2,3,3,4,5,6,7] returns [[7,3],[6,4]]
[9,8,7,6,4,4,3,1] returns [[1,9],[3,7],[4,6]]

```

**Edit**: As the problem description says 'Array', we're talking about the language specific notation of an array, right?

# Answer
> 3 votes
# Perl 52

```
perl -ne '$a{$y=9-$_}&&0*$a{$y++}--*print"$y,$_"or$a{$_-1}++'

```

Proof :

```
> cat test
1
2
3
4
5
5
6
7
> perl -ne '$a{$y=9-$_}&&0*$a{$y++}--*print"$y,$_"or$a{$_-1}++' < test
5,5
4,6
3,7

```

And there is an ungolfed commented code :

```
while(<>) {     # made by the -n option

    # We are looking for (P,Q) pairs where P+Q=10
    # Each P entry will come in $_="P\n" (because $_ will not be chopped)
    # We choose to store the number of occurence of P in $a{P-1}
    # (For instance, if there have been five '3's in the input, then $a{2}=5)

    $y=9-$_;        # if Q=P-10, then $y=Q-1
    if ($a{$y}) {   # check if there was a Q (so $a{Q-1} != 0)
        $a{$y++}--;   # If so 'consume' this Q, and let $y=Q
        print"$y,$_"; # ... and output "Q,P\n"
    } else {
        $a{$_-1}++;   # P is not forming a new pair, so 'count it'.
                    # $a{$_} would not work because of the un-chopped \n, thus the '-1'
    }

}

```

Maybe the explanations looks like pidgin French (I'm not a native english writer), so if someone wants to edit it and make it more understandable, please do so.

# Answer
> 2 votes
# Mathematica 70

```
Cases[#//.{x___,n_,y___,d_,z___}/;n+d==10:>{x,y,z,n~f~d},a_~f~b_:>{a,b}]&

```

**Usage**

```
Cases[# //. {x___, n_, y___, d_, z___} /; n + d == 10 :> {x, y, z, n~f~d},
a_~f~b_ :> {a,b}] &[{1, 2, 3, 4, 5, 5, 6, 7}]

```

> {{3, 7}, {4, 6}, {5, 5}}

# Answer
> 2 votes
**PostScript (46)**

This uses hand-coded binary tokens, therefore, here is a hexdump:

```
00000000  7b 7b 92 1a 92 3f 7b 32  92 19 92 01 31 30 92 3d  |{{...?{2....10.=|
00000010  7b 32 92 09 92 0b 3d 3d  5b 92 40 7d 69 66 92 1a  |{2....==[.@}if..|
00000020  31 92 87 7d 92 83 92 75  7d 92 65 7d 92 a3        |1..}...u}.e}..|
0000002e

```

I uploaded the binary file if you want to try it out.

This expects the numbers to be on the stack. They can be prepended to the code or be supplied on the command line, e.g. when using Ghostscript like so:

```
gsnd -c 2 8 5 5 @ 10_golfed.ps

```

If you insist on array syntax for input, then this requires two more tokens (`aload pop`) right at the beginning. In binary tokens, this is four more bytes.

Un-golfed and commented:

```
{ % stopped                   % we use stopped because we want to catch a
                              % stackunderflow when all numbers have been used up
  { % loop                    % repeat until all numbers have been popped off the stack
    % Test for all numbers on the stack whether they add up to 10 with the topmost number
    count{                    % ... nextNumber number currentTestNumber
      exch                    % ... nextNumber currentTestNumber number
      2 copy add 10 eq{       % ... nextNumber currentTestNumber number
        2 array astore ==     % ... nextNumber
        % We push "[" on the stack because we want to pop the topmost object after each iteration.
        % As [ is a one byte self delimiting token, this is nice for golfing.
        [ exit                % ... nextNumber [
      }if                     % ... nextNumber currentTestNumber number
      count 1 roll            % number ... nextNumber currentTestNumber
    }repeat                   % number ... nextNumber currentTestNumber
    pop                       % number ... nextNumber
  }loop
}stopped

```

# Answer
> 2 votes
# PHP 150 149 148 146 142 --\> 140

Use with PHP CLI.

```
<?$a=fgetcsv(STDIN);for($i=0;$i<$c=count($a);$i++){for($j=$i+1;$j<$c;$j++)if($a[$i]+$a[$j]==10){echo"({$a[$i]},{$a[$j]})";$a[$i]=$a[$j]=0;}}

```

Input: `1,2,3,4,5,5,6,7`

Output: `(3,7)(4,6)(5,5)`

Un-golfed:

```
<?php

$a = fgetcsv(STDIN);
$c = count($a);
for ($i = 0; $i < $c; $i++) {
    for ($j = ($i + 1); $j < $c; $j++) {
        if ($a[$i] + $a[$j] == 10) {
            echo "({$a[$i]},{$a[$j]})";
            $a[$i] = 0;
            $a[$j] = 0;
        }
    }
}

?>

```

# Answer
> 2 votes
# Python 84

Requires input in brackets instead of parenthesis.

```
a=input();r=[]
while a:
 n=a.pop(0);m=10-n
 if m in a:a.remove(m);r+=[(n,m)]
print r

```

For roughly the same answer golfed better see Daniel's answer.

# Answer
> 1 votes
# SED, 112 chars

Probably somewhat simpler than the other solutions

```
s/.*/@&;12345678987654321/
:
s/\(@.*\)\(.\)\(.*\)\(.\)\(.*;.*\2.\{7\}\4\)/(\2,\4),\1\3\5/
t
s/^\(.*\),@.*/(\1)/

```

# Answer
> 1 votes
# Perl, 72 with the `-p` flag

```
perl -p -e 's/^/@/;1while s/(@.*)(.)(.*)((??{10-$2}))/($2,$4)$1$3/;s/(.*)@.*/($1)/'

```

---
Tags: code-golf
---


title: Solving triangles with trigonometry

text:
# Question
Title: Solving triangles with trigonometry
Time to dig up your old trigonometry notes from high school! The challenge is to solve the unknown sides and angles of different triangles. And as is customary in code golf, the smallest working code wins.

This is not a trivial problem; my reference implementation in python is currently down to 838 837 characters, but I'm sure you'll be able to golf solutions far smaller.

Additionally, if you're stuck, this section on Wikipedia should get you going: Triangle: Computing the sides and angles.

## Input

The following triangle shows the names of the sides and angles used in this challenge. Note that sides are lowercase and angles are uppercase.

>

Input is given as six space-separated values, either on `stdin` or as command-line arguments (your choice). The six values correspond to the sides `a, b, c` and the angles `A, B, C`. The unknown sides are given as question marks (`?`). Both input and output angles has to be in radians. You may assume that the input values are correct (you don't have to validate anything). You may also assume that the input triangle is non-degenerate, and that all sides and angles are nonzero.

The following example input tells you that side `a` is `8`, side `b` is `12` and angle `A` is `0.5` radians:

```
8 12 ? 0.5 ? ?

```

## Output

Output is given in the same format as the input - six space-separated numbers on `stdout`. The only exception is when it is not possible to solve the input triangle - then the string `"No solution"` must be written to `stdout`. If two solutions are possible, they are both outputted with a newline between them.

Following is the output for the above input:

```
8.0 12.0 16.0899264342 0.5 0.802561439714 1.83903121388
8.0 12.0 4.97205505116 0.5 2.33903121388 0.302561439714

```

Output is not required to have a lot of precision, but at least a couple decimals is required.

## Rules

* Input is read from `stdin` or command-line arguments
* Output is written to `stdout`
* If two solutions are possible with the given input, output both
* If there is too little information to get one or two clear solutions, consider it a `"No solution"` case
* No built-in or pre-existing code may be used (of course you can use trig functions, but not "`solveTriangle`" or such)
* Shortest code wins

## Test cases

**In** `3 4 5 ? ? ?`

**Out** `3.0 4.0 5.0 0.643501108793 0.927295218002 1.57079630572`

---

**In** `? 4 ? 0.64 0.92 1.57`

**Out** `3.00248479301 4.0 5.02764025486 0.64 0.92 1.57`

---

**In** `? ? 5 ? 0.92 ?`

**Out** `No solution`

---

**In** `? ? 5 ? 0.92 1.57`

**Out** `3.03226857833 3.97800936148 5.0 0.65159265359 0.92 1.57`

---

**In** `8 12 ? 0.5 ? ?`

**Out** (two solutions)

```
8.0 12.0 16.0899264342 0.5 0.802561439714 1.83903121388
8.0 12.0 4.97205505116 0.5 2.33903121388 0.302561439714

```

---

**In** `8 12 ? ? .5 ?`

**Out** `8.0 12.0 18.3912222133 0.325325285223 0.5 2.31626736837`

## Good luck!

# Answer
> 7 votes
## Python, 441 chars

```
from math import*
V=[map(float,raw_input().replace('?','0').split())+[0]]
for i in' '*9:
 W=[]
 for a,b,c,A,B,C,R in V:
  if B and C:A=A or pi-B-C
  if a:
   if A:R=R or a/sin(A)
   else:
    if b and c:A=acos((b*b+c*c-a*a)/2/b/c)
    elif R:N=asin(a/R);W+=[(b,c,a,B,C,N,R)];A=pi-N
  else:a=R*sin(A)
  W+=[(b,c,a,B,C,A,R)]
 V=W
V=[T for T in V if all(t>0 for t in T)]
if V:
 for T in V:print' '.join(map(str,T[:-1]))
else:print'No solution'

```

Does your typical trig to compute the answer. The current possible solutions are stored as tuples in V. Any unknown values are recorded as 0. A seventh variable R is the value `a/sin(A)==b/sin(B)==c/sin(C)`.

I use a trick where the a/b/c values are cycled each iteration to avoid lots of redundant logic. The inner loop only needs to compute values of the A side or angle.

# Answer
> 4 votes
# Plain C, 565 555 530 chars

C is not the best language for Code Golf, I guess, so it's just for fun.

```
float t[6],u[6],P=3.1415;x,w,j,k,D,E;
#define y(V) for(V=0;V<6;++V)
#define Y if(p[j]&&p[k]&&
#define A(o,s,a,b,c,A,B,C) z(float*p){y(D)y(E)if(j=D%3,k=E%3,j-k){Y c)w=C=acos((a*a+b*b-c*c)/2/a/b);if(A&&B)w=C=P-A-B;Y C)w=c=sqrt(a*a+b*b-2*a*b*cos(C));if(A&&B&&a)w=b=s(B)*a/s(A);Y A&&!B&&!C)w=B=(x=A<P/2&&a<b&&p==u,1-2*x)*(asin(b*s(A)/a)-x*P);}y(j)k=w&&(p==t||x>0)&&o("%f ",a);o("\n");}main(int l,char*q[]){y(j)sscanf(*++q,"%f",t+j),u[j]=t[j];z(t);z(u);j=w||o("No solution\n");}
A(printf,sin,p[j],p[k],p[3-j-k],p[j+3],p[k+3],p[6-j-k])

```

Compiled with `cc -o trig trig.c -lm`. Reads input as command line args.

# Answer
> 1 votes
## Perl - 412 chars

As a perl one-liner, based off of Keith Randall's Python Solution:

```
use Math::Trig;@V=((map{tr/?/0/;$_}@ARGV),0);map{my@W;while(($a,$b,$c,$A,$B,$C,$R)=splice@V,0,7){$A||=pi-$B-$C if($B*$C);if($a){if($A){$R||=$a/sin$A;}else{if($b*$c){$A=acos(($b*$b+$c*$c-$a*$a)/2/$b/$c);}elsif($R){$N=asin($a/$R);push@W,$b,$c,$a,$B,$C,$N,$R;$A=pi-$N;}}}else{$a=$R*sin$A;}push@W,$b,$c,$a,$B,$C,$A,$R if($a*$b*$c>=0);}@V=@W;}(1..9);print($V[0]?join' ',map{(((6-$i++)%7)?$_:"\n")}@V:"No solution\n");

```

Here in a more readable form:

```
use Math::Trig;
@V = ( ( map { tr/?/0/; $_ } @ARGV ), 0 );
map {
    my @W;
    while ( ( $a, $b, $c, $A, $B, $C, $R ) = splice @V, 0, 7 ) {
        $A ||= pi- $B - $C
             if ( $B * $C );
        if ($a) {
            if ($A) { $R ||= $a / sin $A; }
            else {
                if ( $b * $c ) {
                    $A = acos(
                        ( $b * $b + $c * $c - $a * $a ) / 2 / $b / $c );
                } elsif ($R) {
                    $N = asin( $a / $R );
                    push @W, $b, $c, $a, $B, $C, $N, $R;
                    $A = pi- $N;
                }
            }
        } else {
            $a = $R * sin $A;
        }
        push @W, $b, $c, $a, $B, $C, $A, $R
            if ( $a * $b * $c >= 0 );
    }
    @V = @W;
} ( 1 .. 9 );

print( $V[0]
         ? join ' ', map { ( ( ( 6 - $i++ ) % 7 ) ? $_ : "\n" ) } @V
         : "No solution\n" );

```

---
Tags: code-golf, math, geometry, trigonometry
---


title: Secret Santa Challenge

text:
# Question
Title: Secret Santa Challenge
> **Possible Duplicate:**
> Holiday Gift Exchange

**Background:** Secret Santa is a Western Christmas tradition in which members of a group or community are randomly assigned a person to whom they anonymously give a gift.

http://en.wikipedia.org/wiki/Secret\_Santa

>

Ok, me and my work colleges did this today during our lunch hour - we made a secret algorithm santa pick random gifters and receivers.

Think of this question as a Christmas Programming Challenge to see who can come up with some of the most elegant solutions for this problem.

**Input:** The input should be an array \['Oliver', 'Paul', 'Rowan', 'Darren', 'Nick', 'Atif', 'Kevin'\]

**Output** A representation of something similar to key value pairs for the gifter and receiver. e.g.

```
Oliver -> Darren,
Paul -> Nick,
Rowan -> Kevin
Kevin -> Atif,
Darren -> Paul,
Nick -> Oliver,
Atif -> Rowan

```

**Deadline:** 15th December (for those late christmas shoppers)

**Remember:** you cannot have a person choosing themselves and the program must not spiral off into an infinite loop when gifter == receiver when there is only one person left.

**Rules:**

1. Must not have duplicates
2. Must be random (we all have different views on what is random - but you get my gist)
3. No Language constraints
4. Have fun

Here is mine (not golfed) in ruby:

```
require 'pp'

def move(array, from, to)
  array.insert(to, array.delete_at(from))
end

gifters = ['Oliver', 'Paul', 'Rowan', 'Darren', 'Nick', 'Atif', 'Kevin'].shuffle!
recievers = gifters.dup

move recievers, recievers.count - 1, 0

pp Hash[gifters.zip recievers]

```

which spits out:

```
{"Nick"=>"Darren",
 "Paul"=>"Nick",
 "Kevin"=>"Paul",
 "Rowan"=>"Kevin",
 "Atif"=>"Rowan",
 "Oliver"=>"Atif",
 "Darren"=>"Oliver"}

```

# Answer
# k (~~29~~ 20 chars)

```
{i!(1_i),*i:(-#x)?x}

```

~~{i!@\[i:(-:#x)?x;,/|2 0N#!#x\]}~~

Example

```
k){i!(1_i),*i:(-#x)?x}`person1`person2`person3`person4`person5
person2| person1
person5| person3
person4| person2
person1| person5
person3| person4

```

Explanation - as above, shuffles list and maps to rotation of itself.
> 2 votes

# Answer
## Ruby - 161 42 chars

```
#!/usr/bin/env ruby
require 'csv'

gifters = CSV.read(ARGV[0]).first

receivers = gifters.shuffle!.dup
puts Hash[gifters.zip(receivers << receivers.shift)]

```

Usage

```
./secret_santa path_to_some_csv
=> {"Edward"=>"Alan", "Alan"=>"Charlie", "Charlie"=>"Dave", "Dave"=>"Brett", "Brett"=>"Edward"}

```

## Update

```
r=ARGV.shuffle!.dup;p ARGV.zip(r<<r.shift)

```
> 1 votes

# Answer
```
    NSMutableArray *people =
    [NSMutableArray arrayWithArray:@[@"Oliver", @"Paul", @"Rowan", @"Darren", @"Nick", @"Atif", @"Kevin"]];
    [people sortUsingComparator:^NSComparisonResult(id obj1, id obj2) {
         return (arc4random_uniform(3)-1);
    }];

    for (int i = 0;  i < [people count]; i++)
        NSLog(@"%@ gifts %@", people[i], people[(i+1)%[people count]]);

```
> 1 votes

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


title: Pseudosort a list in 2*n comparisons

text:
# Question
Title: Pseudosort a list in 2*n comparisons
Write a program that takes a list of n space-separated integers, and outputs a permutation of that list using a maximum of 2\*n comparisons.

It should loop this until an empty line is input. Alternatively, it can accept inputs until an empty line is given, then output all the permutations.

Though your program only has to work on integers, it should be possible to implement your algorithm for any comparable data structures. For example, using `sign(a-b)` to get extra comparisons is illegal, because the same algorithm can't be applied to data structures without numerical values.

Example session:

```
>0 1 2 3 4
0 1 2 3 4
>7 9 2 1
1 2 7 9
>6 7 4 5 2 3 0 1
0 2 3 1 4 5 6 7
>

```

or

```
>0 1 2 3 4
>7 9 2 1
>6 7 4 5 2 3 0 1
>
0 1 2 3 4
1 2 7 9
0 2 3 1 4 5 6 7

```

note: `>` shouldn't actually be printed, it's just being used to notate input vs output.

## Scoring

Scoring is based mostly on how well sorted the permutations are, but also favours concise code.

Run your program with this file as input. Use your program's output as input to this python script. This script works under both python 2.7 and 3.3. Other versions weren't tested.

```
import sys
def score(l):
    n = len(l)
    w = n**2 // 2
    s = sum(abs(l[i]-i)for i in range(n))
    return float(s)/w
s = 0.0
for i in range(40000):
    s += score([int(n) for n in sys.stdin.readline().split()])
print (int(s))

```

**Your score is the output of the above script plus the length of your program**

## Explanation of Scoring

In the input file, there are 1000 lists for each length n in the range `10 <= n < 50`. In total, there are 40000 lists. No two elements of a list will be equal.

To score a list, we define the unsortedness of a list as the sum of distances of each element from where it should be. For example, for the list `[0,1,4,3,2]`, the unsortedness is 4, because 4 and 2 are each 2 positions from where they should be, and the rest of the numbers are correct.

The worst case unsortedness of a list of length n is `n^2 / 2`, using integer division.

The score of a list is its unsortednes divided by the maximum unsortedness. This is a number between 0.0 (sorted) and 1.0 (reversed).

Your total score is the sum of all scores in the input rounded down to an integer, plus the length of your program. Because there are 40000 cases, a better pseudo-sort is likely better than shorter code, but if there is some optimal solution, then the shortest implementation of that solution will win.

# Answer
> 2 votes
# Python, 7910 (7704 + 206)

This was inspired by shell sort. I found relatively good coefficients for the gap sequence (`g`) by checking a few hundred alternatives. The number of comparisons is limited by counting explicitly (`n`).

```
s=1
while s:
 s=map(int,raw_input().split());k=len(s);n=2*k;g=13*k/23
 while g:
  for i in range(g,k):
   n-=1
   if n<0:break
   if s[i]<s[i-g]:s[i],s[i-g]=s[i-g],s[i]
  g=3*g/5
 print' '.join(map(str,s))

```

# Answer
> 1 votes
**Ruby, 10140** (9988 + 152)

```
def q a
  p=a.pop
  l,m=a.partition{|x|x<p}
  [l,p,m]
end
while a=gets
  a=a.split.map(&:to_i)
  l,p,m=q a
  puts (q(l)+[p]+q(m)).flatten.join(" ")
end

```

This simply performs two rounds of quicksort. It removes the last element, then divides the remaining array into those less than and those greater than that element (n-1 comparisons). Then it does the same thing to those two (n-3 comparisons) and joins the result in order. Total comparisons are 2\*n - 4 (worst case 2\*n - 2), so there's definitely room for improvement.

---
Tags: code-challenge, sorting
---


title: Musical Score Interpreter

text:
# Question
Title: Musical Score Interpreter
Given an ascii musical score, you must be able to output the note and its corresponding length. The score will contain between 5 and 15 notes inclusive, and is transcribed on a stave. A stave is made up of five horizontal lines comprising of - (minus) characters separated by lines of spaces. The bottom line in the stave is equivalent to the note 'E'. The line of spaces immediately above the bottom line indicates an 'F', and is of a higher pitch that the 'E' below it. This continues as below. Note that notes only go up to 'G' before starting again at 'A'. See below:

```
F ----------
E
D ----------
C
B ----------
A
G ----------
F
E ----------

```

Note that the letters aren't included in the input. The notes are superimposed on top of the stave using a o (lowercase ooh) character to indicate the 'note head'. This note head indicates the frequency of the note, and therefore the alphabetic representation of it as above. For example, a note placed on the score as below indicates an 'A' :

```
----

----

----
o
----

----

```

A note, like the 'A' above, is called a 'whole note' and would be played for one whole beat. Other durations can be indicated by including a 'stem' rising from the note, and between zero and three 'flags'. A stem is made up of three | (pipe, or vertical bar) characters stacked immediately above the note head . A stem with no flags is considered a 'quarter-note', and plays for quarter of a beat. Flags are \ (backslash) characters, and hand on the right hand side of the stem. Each stem halves the time the note is played for. The length of each note will be one of the following: a whole note, a quarter note, an eighth note, a sixteenth note or a thirty-second note. This how each type of note would look for A :

```
--------------------

----|---|\--|\--|\--
    |   |   |\  |\
----|---|---|---|\--
o   o   o   o   o
--------------------

--------------------

```

Putting more than one note together gives you a score. Each note can be considered to be four characters wide, with a note being in the first column of each four-character block. For example :

```
    |\
----|\--|\----------
    |\  |       |\
----o---|---o---|\--
|       o       |
|---------------o---
|
o-------------------

--------------------

```

The example above contains the following notes, in order: a quarter note 'G', a thirty-second note 'D', an eighth note 'C', a whole note 'D' and a sixteenth note 'B'. Each note in your output should be in the format letter/length, where letter is A-G and length is the fraction of the note's length when compared to a whole note. As an exception, the length and / character should not be printed if the note is a whole note. Each note in your output should be separated by a single space. Therefore, for the score above, your code should output the following:

```
G/4 D/32 C/8 D B/16

```
* The notes will be in the following range: E F G A B C D E F. Note that only the letter needs to be printed, the octave is ignored.
* Note that the number of lines of input varies from 9 to 12, since notes with quarter time or less on line D or higher will require more lines to show completely.
* There is no half-note in this case.

Shortest code wins (whitespace doesn't count).

*Edit:* Fixed error in spacing in one input.

Some sample inputs:

```
        |\
----|\--|-------------------
|\  |   |
|---|---o---------------o---
|   o               |\
o---------------|\--|\------
            |\  |\  |\
------------|\--|\--o-------
            |\  o
------------o---------------

```

Output: B/8 C/8 D/8 E/32 F/32 G/32 D

---

```
----------------o-------------------
                                o
------------o-----------------------
                            o
--------o---------------------------
                        o
----o-------------------------------
                    o
o-----------------------------------

```

Output: E G B D F F A C E

---

```
            |\
            |\
            |\
------------o-------|-----------
|               o   |   |\
|---|\--------------|---|\------
|   |               o   |\
o---|---|\--------------o---|\--
    o   |\                  |\
--------|\------------------|---
        o                   o
--------------------------------

```

Output: B/4 A/8 F/32 F/32 E C/4 B/32 F/16

# Answer
# Javascript,284,279,278,225,221,220 Characters (including necessary whitespace)

One-liner (test fiddle):

```
function a(c){b='',d=c.split('\n');for(e=0;d[0][e++];){f=0;for(i=0;g=d[i++];){h=g[e-1];if(h=='o')b+=(b?' ':'')+String.fromCharCode((d.length+4-i)%7+65);if(h=='|')f=f||4;if(g[e]&&g[e]=='\\')f*=2;}if(f)b+='/'+f;}return b;}

```

Readable (test fiddle):

```
function getNotes(input){
    out='',lines=input.split('\n');

    for(col=0;lines[0][col++];){
        time=0;
        for(i=0;line=lines[i++];){
            char=line[col-1];
            if(char=='o')out+=(out?' ':'')+String.fromCharCode((lines.length+4-i)%7+65);
            if(char=='|')time=time||4;
            if(line[col]&&line[col]=='\\')time*=2;
        }
        if(time)out+='/'+time;
    }
    return out;
}

```
> 6 votes

# Answer
## Perl, 103 characters

(108 if you count necessary whitespace characters)

```
$i=0,s/\|\\/h /g,map$b[$i++].=$_,/./g for<>;/o/&&print chr 65+(4+length$')%7,/[h|]/&&"/".4*2**y/h//," "for@b

```

With whitespace for presentation:

```
$i=0,
    s/\|\\/h /g,
    map $b[$i++]. = $_, /./g
  for <>;
/o/ && print chr 65 + (4 + length $') % 7,
             /[h|]/ && "/" . 4*2**y/h//,
             " "
  for @b

```

Note that I assume that all lines have the same length (as per the revised version of the question).

Rearranged version with explanations:

```
#!/usr/bin/env perl
# First transpose the list of lines into a list of columns.
my @b = ();               # @b[$i] will contain the characters in column $i
while (<>) {              # for each input line, do
    my $i = 0;            # start in column 0
    s/\|\\/h /g;          # replace '\|' by 'h ', to keep track of part notes in the first column
    foreach (/./g) {      # for each character, do
        $b[$i++] .= $_;   # append the character to the transposed matrix
    }
}
# Now process each column.
foreach (@b) {            # for each column, do
    if (/o/) {            # if it contains a note, then
        print chr(65 + (4 + length $') % 7);    # print the note pitch
        if (/[h|]/) {                           # if this is a part note (had |\ or just |)
            print "/", 4*2**y/h//;              # print /n where n = 2^(subdivision)
        }
        print " ";
    }
}

```

---

*(old, longer solution, kept because it may be interesting even if it's a little longer)*

## Perl, 147 126 characters

(149 131 if you count necessary whitespace)

```
$c=0,map{/o/?$h[$c]=E:/\\/?$d[$c-1]*=2:/\|/?$d[$c]||=4:++$h[$c];++$c}/./g for<>;print grep{s~$~/$d[$i++] ~;s~/ ~ ~;y/E-M/EFGA-F/}@h

```

With whitespace for presentation:

```
$c = 0,
map { /o/ ? $h[$c]=E :
      /\\/ ? $d[$c-1]*=2 :
      /\|/ ? $d[$c]||=4 :
      ++$h[$c];
      ++$c
    } /./g for <>;
print grep {s~$~/$d[$i++] ~; s~/ ~ ~; y/E-M/EFGA-F/} @h

```

Rearranged a little so as not to abuse the language so much:

```
#!/usr/bin/perl
my @h;          # $h[$c] will contain the note in column $c, if any
my @d;          # $d[$c] will contain the note length (e.g. 4), if any
while (<>) {    # for each input line, do
    my $c = 0;  # column number
    foreach (split //) {   # for each character, do
        if (/o/) { $h[$c] = "E"; }      # o => it's a note; if this is the last line, it's E
        elsif (/\\/) { $d[$c-1] *= 2; } # \ => halve the duration of the note in the previous column
        elsif (/\|/) { $d[$c] ||= 4; }  # | => if this is the first | in the column, we have a quarter note
        else { ++$h[$c]; }              # anything else => bump the note by 1
        ++$c;
     }
}
for (my $i = 0; $i < @h; $i++) { # for each column, do
    $_ = $h[$i];                   # look up the potential note (or garbage if there is no note in this column)
    s~$~/$d[$i++] ~;               # append the duration and a space (or "/ " if there is no duration)
    s~/ ~ ~;                       # remove the spurious "/" if there is no duration
    if (y/E-M/EFGA-F/) {           # if it's a note (i.e. if it contains a letter E-M), then
                                   # fix the letter wraparound and then
        print $_;                    # print the note
    }
}

```

Note that I assume that all lines have the same length. If you want to allow shorter lines, an obvious fix is to add `$_.=1x$c,` at the beginning of the program, at a cost of 9 characters.

I thought of another approach to avoid long words like `split` and `map` and let spaces do more of the work, but the boilerplate and punctuation took their revenge, and I can only get it down to a whooping 130 (144 with necessary whitespace).

```
sub p{$-[0]}
%a=qw(o $h[p]=E \ $d[&p-1]*=2 | $d[p]||=4 - ++$h[p]);
y/ /-/,s~.~$a{$&}~gee for<>;
print grep{s~$~/$d[$i++] ~;s~/ ~ ~;y/E-M/EFGA-F/}@h

```

The patch to cope with unfinished lines is a little weirder this time (what, you thought it couldn't get weirder?). 139 characters, 155 with necessary whitespace.

```
sub p{$-[0]}
%a=qw(o $h[p]=E \ $d[&p-1]*=2 | $d[p]||=4 - ++$h[p]);
$_.=" "x p,y/
 /-/,s~.~$a{$&}~gee for<>;
print grep{s~$~/$d[$i++] ~;s~/ ~ ~;y/E-M/EFGA-F/}@h

```
> 4 votes

# Answer
## Scala(2.9), 352 313 291 294 290 277 274 273 characters

If a function is all that's needed:

```
def m(s:String){var(x,y,z,l)=(0,1,s.count(_=='\n'),Array.fill(99)(0))
var n=l.clone
for(c<-s){if(c=='\n'){x=0;y+=1}
if(c=='\\')l(x-1)+=1
if(c=='|')l(x)+=1
if(c=='o')n(x)="EFGABCDEF"(z-y)
x+=1}
(n,l).zipped.map((x,y)=>if(x>0)print(x.toChar+(if(y>0)"/"+(4<<y-3)else"")+" "))}

```

If a full program is required:

```
object M extends App{def m(s:String){var(x,y,z,l)=(0,1,s.count(_=='\n'),Array.fill(99)(0))
var n=l.clone
for(c<-s){if(c=='\n'){x=0;y+=1}
if(c=='\\')l(x-1)+=1
if(c=='|')l(x)+=1
if(c=='o')n(x)="EFGABCDEF"(z-y)
x+=1}
(n,l).zipped.map((x,y)=>if(x>0)print(x.toChar+(if(y>0)"/"+(4<<y-3)else"")+" "))}
m(io.Source.stdin.mkString)}

```
> 2 votes

# Answer
## J - 108 characters

```
exit echo}.,>,&.>/_4<@((a.{~32,65+7|4+i.&'o'),(>&0#('/',0":2^]))@((+/@(=&'\'))+2*'|'&e.))@;\|:|.[;._2]stdin''

```

Ungolfed:

```
str =: stdin''
lines =: [;._2] str                          NB. split on the last character, the newline
rotated =: |: |. lines                       NB. lines reversed, then transposed
pitch =: 65 + 7 | 4 + i.&'o'                 NB. ord('A') + ( line.index('o') + 4 ) % 7
has_stem =: '|' & e.                         NB. '|' in line?
backslash_count =: (+/ @ (=&'\') )           NB. sum(char = '\\' for char in line)
denom_exp =: backslash_count + 2 * has_stem
fraction =: (>&0 # ('/', 0": 2 ^ ]))         NB. slash + 2^denom_exp, if denom_exp > 0
suffix =: fraction @ denom_exp
note_string =: (a. {~ 32,pitch) , suffix     NB. map(chr, (ord(' '), pitch)) + suffix
boxed_note_string =: < @ note_string @ ;     NB. box the string so it doesn't get padded
each_note_of_the =: boxed_note_string        NB. compute the note for a block of 4 lines
join_to_one_box =: , &. >
exit echo }. , > join_to_one_box / _4 each_note_of_the \ rotated

```
> 2 votes

# Answer
## Python golf, 207 chars.

```
import sys
a=[x[:-1]+' '*99 for x in sys.stdin]
for x in range(0,99,4):
 b=''.join((y[x:x+4] for y in a))+'o'
 c=2**(b.count('\\')+('|'in b)*2)
 print'FEDCBAGFE '[b.index('o')/4-len(a)+9]+('','/'+`c`)[c>1],

```

I've start code golfing with Python for 2 days and I found that things like `import sys`, `sys.stdin.read`, `sys.stdout.write` are expansive.
> 2 votes

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