title: Calculating Resistance (Nerd Sniping)

text:
# Question
Title: Calculating Resistance (Nerd Sniping)
Good Afternoon Golfers,

Our challenge for today is inspired by XKCD comics 356 and 370. We're going to write a program to calculate the resistance of a group of resistors. A forewarning that this is nearly tough enough to warrant being a code challenge, however I think that there is a certain art to writing slightly more complex programs in a golfed format. The lowest amount of characters wins.

Calculating the resistance relies on the following two formulas:

* If the resistors are in series, the resistance is the sum of the each resistor's resistance
* If the resistors are in parallel, the resistance is the inverse of the sum of the inverse of the resistance of each resistor

So - for example:

Your challenge is to, in the least amount of characters possible, calculate the resistance of a group of up to 64 resistors. My apologies for the complexity, particularly of the input rules. I've attempted to define them in such a way that every language will be usable.

* Each resistor will be connected to 2 or more other resistors.
* The input is guaranteed to be valid, with only one entry and one exit point, which will connect
* The network will be series-parallel to prevent requiring more maths then what is presented
* Input will be via file, argument or stdin, depending on what is appropriate for your language.
* Input will consist of a series of newline or forward slashed separated statements consisting of an integer of the resistance of the resistor, and spaces separating the IDs of the resistors that one side of the resistor is connected to.
* The ID of the first resistor will be 1, incrementing by one for each successive resistor
* The start will always have an ID of 0
* The final resistor will always have a resistance of 0 ohms, and only have the connections defined in its line

For example:

Could be represented as

```
3 0
6 1
1 0
5 0
0 2 3 4

```
* Output can be to stdout or file. It may be represented in one of the following ways:
    + A number with a minimum of 2 decimal places, followed by a newline
    + A fraction consisting of an integer (the numerator), a forward slash and another integer (the denominator), followed by a newline. The fraction does not need to be the to be in its lowest form - 4/4 or 10/8 are, for instance acceptable. The fraction must be accurate within 1/100. There is no bonus for being perfectly accurate - this is provided is a crutch to enable languages without fixed or floating point operations to compete.

I hope that covers all the points. Good luck!

# Answer
> 6 votes
## Python, 329 chars

```
import sys
N=[[1]]+[map(int,x.split())for x in sys.stdin]
N[-1][0]=1
n=len(N)
S=[set([i])for i in range(2*n)]
for x in range(n):
 C=S[2*x]
 for y in N[x][1:]:C|=S[2*y+1]
 for x in C:S[x]|=C
V=[0]*(2*n-1)+[1]
for k in range(999):
 for i in range(1,2*n-1):V[i]+=sum((V[j^1]-V[i])/N[j/2][0]for j in S[i])/9./len(S[i])
print 1/V[1]-2

```

Calculates the resistance by doing a voltage relaxation on the circuit. First it tacks on a 1 ohm resistor to the start and changes the last resistor from 0 ohm to 1 ohm. Then it sets the input voltage to 0 and the output voltage to 1 volt. After simulating current flow through the network, the network resistance is calculated using the voltage drop across the first 1 ohm resistor.

Each resistor is given two numbers, the number for its left terminal and the number for its right terminal. Resistor r's left terminal is 2\*r and its right terminal is 2\*r+1. The input is used to calculate `S`, the sets of terminals that are connected together. Each terminal is given a voltage `V[t]` and a relaxation is done by raising the voltage if current is net flowing into a terminal set and lowering the voltage if current is net flowing out.

# Answer
> 6 votes
## APL 190

Index origin 1. First loop (s) combines all resistors wired in series, second (p) those wired in parallel and the repeat to first loop to combine any parallel resistors now in series. The specification of the final zero resistor appears to be redundant.

```
r←¯1↓⍎¨(c≠'/')⊂c
o←⊃↑¨r
r←⊃1↓¨r
s:→(0=+/n←1=+/×r)/p
n←↑n/i←⍳↑⍴r
o[n-1]←+/o[n-0 1]
o←(i←n≠i)/o
r←i⌿r
r←r-r≥n
→s
p:n←1⍪2≠/r[;1]
r←((⍴r),1)⍴r←¯1++\n~0
o←∊1÷¨+/¨1÷¨n⎕penclose o
→(1<⍴o)/s
3⍕o
' '

```

Tested over the examples in the question plus a slightly more complicated one:

```
      Input: '5 0/3 1/1 2/0 2'
 9.000

      Input: '3 0/1 0/5 0/0 1 2 3'
 0.652

      Input: '3 0/6 1/1 0/5 0/0 2 3 4'
 0.763

      Input: '2 0/2 1/2 0/2 0/2 4/2 5/2 2 3 6/2 7/2 2 3 6/0 8 9'
 2.424

```

---
Tags: code-golf, math, rational-numbers, electrical-engineering
---


# Question
Title: Matlab/Octave Eratosieve using minimal big-O iterations
I'm trying to come up with ways to write Sieve of Eratosthenes in Octave that vectorize as much as possible (ie minimizing the number of times iterating over the for-loop/while-loop/recursive call)

I found one that requires only O(log(log(n))) iterations inside the for-loop, but the big-O running time (and also space) is O(n^(5/4)/log(n)) so it's arguably not the Sieve of Eratosthenes

Now I think I have one with the usual running time O(nlog(log(n))) and only O(log(n)) iterations, but I want to see if someone else comes up with a better solution.

# Answer
Here's my solution The loop clearly runs O(logn) times and it's easy to see that the number of operations is bounded above by the normal number of operations for SOE(2n) so it's within O(nlog(logn)) big-O running time

```
function [primes] = eratosieve(n)
    isprime = ones(n, 1);
    isprime(1) = false;
    m = 1;
    while(m ^ 2 < n)
        nprimes = find(isprime(m + 1 : m * 2)) + m;
        mult = (m + 1) : (n/(m + 1));
        a = nprimes * mult;
        isprime(a(a<=n)) = false;
        m *= 2;
    end
    primes = find(isprime);
endfunction

```
> 0 votes

---
Tags: matlab
---


title: Build a program with one simple GOTO

text:
# Question
Title: Build a program with one simple GOTO
Your task is to build the largest program you can that uses exactly one GOTO, without which the entire program (or at least a huge chunk of it) must be completely restructured. The score is counted as the number of statements in your code that *change places* or *are newly introduced* (removing statements doesn't add to your score) when the code is restructured without the GOTO (others are allowed to challenge your restructuring by presenting a more elegant one). As this is code bowling, highest score wins.

Note: I do not claim any liability for velociraptor attacks by attempting this challenge.

# Answer
## C fizzbuzz

This solution runs around the idea of interrupts and label variables (gcc only, sorry). The program sets up a timer which periodically calls main, where we goto whichever place the last execution of our interrupt handler (main) told us we should.

I've never used timers or label variables before, so I think there is much to bowl here.

```
#include <sys/time.h>
#include <signal.h>
#include <stdio.h>

int main(int argc)
{
    static int run = 1;
    static int* gotoloc = &&init;
    static int num = 0;
    static int limit = 50;

    goto *gotoloc;
init:
    signal(SIGVTALRM, (void (*)(int)) main);
    gotoloc = &&loop;

    struct itimerval it_val;

    it_val.it_value.tv_sec = 0;
    it_val.it_value.tv_usec = 100000;
    it_val.it_interval.tv_sec = 0;
    it_val.it_interval.tv_usec = 100000;
    setitimer(ITIMER_VIRTUAL, &it_val, NULL);

    while(run);

loop:
    num = num + 1;
    run = num < limit;
    gotoloc = &&notfizz + (&&fizz - &&notfizz) * !(num % 3);
    return 1;

fizz:
    printf("fizz");
    gotoloc = &&notbuzz + (&&buzz - &&notbuzz) * !(num % 5);
    return 1;

notfizz:
    gotoloc = &&notfizzbuzz + (&&buzz - &&notfizzbuzz) * !(num % 5);
    return 1;

buzz:
    printf("buzz\n");
    gotoloc = &&loop;
    return 1;

notbuzz:
    printf("\n");
    gotoloc = &&loop;
    return 1;

notfizzbuzz:
    printf("%d\n", num);
    gotoloc = &&loop;
    return 1;
}

```
> 11 votes

# Answer
## Perl

I'm not very good at bowling, but I suspect this may interest the OP. This is a Sieve of Eratosthenes using a variable goto. Were this to be 'refactored', I doubt any of it would be reusable, other than perhaps the first few lines. When the sieve ends, all remaining `1`s in the `@primes` array correspond to prime values.

For added fun, no ands, ors, ternaries, conditionals or comparison operators of any kind are used.

```
@primes[2..1e4]=(1)x9999;
$a=2;
Y:
  $b=$a*~-$a;
X:
  $primes[$b+=$a+=$c=$a/100%2+$b/1e4%2]=0;
  goto"$c"^h;
Z:

```
> 5 votes

# Answer
## C

My usage of macros perhaps doesn't make it "one GOTO".
And it's quite short, so "completely restructured" isn't much.
But here's my attempt anyway.

Reads a number from standard input, prints it modulu 3.

```
int main() {
    char s[100], *p, r=0;
    void *pl[] = { &&a, &&b, &&c, &&d, &&e, &&f, &&g, &&h, &&i, &&j, &&a, &&b, &&x, &&y, &&z }, *p1;
    p = gets(s);
    #define N(n) (pl+n)[!*p*60+*p-48];p++;goto *p1
    a: p1=N(0);
    b: p1=N(1);
    c: p1=N(2);
    d: p1=N(0);
    e: p1=N(1);
    f: p1=N(2);
    g: p1=N(0);
    h: p1=N(1);
    i: p1=N(2);
    j: p1=N(0);
    z: r++;
    y: r++;
    x: printf("%d\n", r);

    return 0;
}

```
> 3 votes

---
Tags: code-bowling
---


# Question
Title: "Sorry, young man, but it's Turtles all the way down!"
# Execute a Lindenmayer System

A Lindenmayer System (or L-system) is related to Thue and Post systems, and is used in botanical modeling and fractal generation.

An L-system is described by *string-rewriting* where a symbol from the symbol-alphabet is mapped to a *replacement* sequence of symbols. A collection of these mappings constitutes the L-system proper.

The graphical output method as devised by Prusinkiewicz interprets the resulting sequence after the mappings have been applied to an *initial* sequence for a specified number of *iterations*, as Turtle-Drawing commands: forward, backward, left, right, that kind of stuff. This may require extra code to control the scale of the drawing as different iteration counts may produce drastically differently-sized images.

Your task is to execute an L-system in the fewest number of characters. Your program must be able to render both the Dragon Curve and the Branching Stems from the Wikipedia page by providing appropriate input (file, command-line, but external to the source, please).

This is code golf.

Edit: Here are some examples I've posted around town. answer to SO/rotate-to-north {*Where I first discovered the L-system*}, answer to SO/how-to-program-a-fractal, answer to SO/recursion-in-postscript, comp.lang.postscript discussion/recital, postscript l-system collection, codegolf.SE/draw-a-sierpinski-triangle *{origin of the competition between myself and thomasW}*.

# Answer
## Mathematica ~~200~~ ~~198~~ ~~188~~ ~~171~~ 168

Spaces added for clarity:

```
f[i_, b_, h_, j_, r_, n_] :=
 (a = h; p = j; s = k = {}; t = Flatten;
  (Switch[#,
      6, s = {a, p, s},
      8, {a, p, s} = s,
      _C, k = {k, Line@{p, p += {Cos@a, Sin@a}}}];
     If[# < 9, a += I^# b ]) & /@ t@Nest[# /. r &, i, n];
  Graphics@t@k)

```

Where:

> i : Initial state;
> b : rotation angle
> h : initial angle
> j : initial position
> r : production rules
> n : iterations

Production rules grammar:

> 2 = Turn Left (-);
> 4 = Turn Right (+);
> 6 = Push and Turn Left ("\[");
> 8 = Pop and Turn Right ("\]");
> C\[i\] = Draw (Any number of symbols)
> Any other symbol = Do Nothing, just use it in producing next state (Any number of symbols)

The {2,4,6,8} sequence is there because I'm using `I^n` (`I` = imaginary unit) to make turns.

Examples:

```
f[{C[1], X}, Pi/2, 0, {0, 0}, {X -> {X, 4, Y, C[1]}, Y -> {C[1], X, 2, Y}}, 10]

```

```
f[{C@1}, Pi/2, 0, {0,0}, {C@1->{C@1, 2, C@1, 4, C@1, 4, C@1, 2, C@1}}, 6]

```

```
f[{C[1]}, Pi/4, Pi/2, {0, 0}, {C[2] -> {C[2], C[2]}, C[1] -> {C[2], 6, C[1], 8, C[1]}}, 10]

```

```
f[{C[1]}, Pi/3, 0, {0, 0}, {C@1 -> {C@2, 4, C@1, 4, C@2}, C@2 -> {C@1, 2, C@2, 2, C@1}}, 10]

```

```
f[{X},5/36 Pi, Pi/3, {0,0},{X->{C@1, 4, 6, 6, X, 8, 2, X, 8, 2, C@1, 6, 2, C@1, X, 8, 4, X},
                            C@1->{C@1, C@1}}, 6]

```
> 31 votes

# Answer
# Python, ~~369~~ 294

Not a winner but I'll post what I've tried anyway.

```
from turtle import*
I=open('l').read().split()
s,S,p=I[0],'',[]
for j in range(8):
    for i in s:S+=eval('{'+I[1]+'}')[i]
    s,S=S,''
for k in s:
    if k=='[':p+=[heading(),pos()];continue
    if k==']':pu();goto(p.pop());seth(p.pop());pd();continue
    try:{'f':fd,'F':fd,'+':rt,'-':lt}[k](5)
    except:pass

```

Not good at golfing Python...... Maybe someone else can do it.

## Input

Input is from an external file named "l" (no extension), with the following format:
**Line 1**: Initial state (Axiom)
**Line 2**: Comma-separated rules

**Symbols**
`f` and `F`: Draw forward
`+`: Turn right 5 degrees
`-`: Turn left 5 degrees
`[`: Save position and heading
`]`: Pop position and heading
Other symbols are ignored by the drawing function.

**Rules**
A rule is in the format `"predecessor":"successor(s)"`
Note that the quotes are necessary, whether single or double.
`predecessor` must be a single character.
Also, there are no implicit constants: You must explicitly specify a no-change rule for those.

## Examples

### Branching stems

```
------------------f
'-':'-','+':'+','[':'[',']':']','F':'FF','f':'F[+++++++++f]---------f'

```

**Output**
Note that the source is modified to get this out put ONLY TO SCALE DOWN THE GRAPH TO THE VISIBLE AREA. The console is also used to hide the "turtle".

### Dragon curve

```
fx
'-':'-','+':'+','[':'[',']':']','f':'f','x':'x++++++++++++++++++yf','y':'fx------------------y'

```

**Output**
Again, the console is used to hide the "turtle".

### Sierpinski Triangle

```
f------------------------F------------------------F
'-':'-','+':'+','[':'[',']':']','f':'f------------------------F++++++++++++++++++++++++f++++++++++++++++++++++++F------------------------f','F':'FF'

```

**Output**
Generations reduced to 5 here.
> 9 votes

# Answer
## Javascript (179 bytes)

Not completely sure this qualifies, as the rules object does all of the actual drawing.

**Demo** (Dragon, animated):
-- Expanded: http://jsfiddle.net/SVkMR/9/show/light
-- With Code: http://jsfiddle.net/SVkMR/9/

**Minified:**

```
function L(c,r,n){o=(function g(d,s,o,i){for(o=i='';a=d&&s[i++];)o+=r.r[a]?g(d-1,r.r[a]):a;return o||s;})(n,r.r[r.s]);(function z(i){r[s=o[i]]&&r[s](c)||setTimeout(z,10,i+1)})(0)}

```

**Readable(ish):**

```
function L(c,r,n){
    o=(function g(d,s,o,i){
        for(o=i='';a=d&&s[i++];)o+=r.r[a]?g(d-1,r.r[a]):o+=a
        return o||s
    })(n,r.r[r.s]);

    (function p(i){
        r[s=o[i]]&&r[s](c)||setTimeout(p,10,i+1)
    })(0)
}

```

**Input:**

```
var sierspinski = {
    r:{'A':'B-A-B','B':'A+B+A'},
    '+':function(c){c.rotate(-this.a);c.rotate(this.a-=Math.PI/3)},
    '-':function(c){c.rotate(-this.a);c.rotate(this.a+=Math.PI/3)},
    'A':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    'B':function(c){this['A'](c)},
    s:'A',
    a:0,
    m:1
};

var koch = {
    r: {'F':'F+F-F-F+F'},
    '+':function(c){c.rotate(-this.a);c.rotate(this.a-=Math.PI/2)},
    '-':function(c){c.rotate(-this.a);c.rotate(this.a+=Math.PI/2)},
    'F':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    s:'F',
    a:0,
    m:2
};
var dragon = {
    r: {'X':'X+YF','Y':'FX-Y'},
    '+':function(c){c.rotate(-this.a);c.rotate(this.a-=Math.PI/2)},
    '-':function(c){c.rotate(-this.a);c.rotate(this.a+=Math.PI/2)},
    'F':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    s:'X',
    a:0,
    m:5
};

var algae = {
    r: {'A':'B[A]A','B':'BB'},
    '[':function(c){c.save();c.rotate(Math.PI/4);},  // save/restore will push/pop current state of context.
    ']':function(c){c.restore();c.rotate(-Math.PI/4);},
    'A':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    'B':function(c){this['A'](c);},
    s:'A',
    a:-Math.PI/2,
    m:1
};

var tree = {
    r:{'X':'F-[[X]+X]+F[+FX]-X','F':'FF'},
    '+':function(c){c.rotate(-this.a);c.rotate(this.a+=Math.PI/180*25)},
    '-':function(c){c.rotate(-this.a);c.rotate(this.a-=Math.PI/180*25)},
    '[':function(c){c.save();},
    ']':function(c){c.restore();},
    'F':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    s:'X',
    a:-Math.PI/180*25,
    m:5
};

```

**Usage:**

```
var ctx = document.getElementById('l').getContext('2d'); // grab context
ctx.translate(299.5,199.5); // start drawing from center, fractional pixels because the canvas draws lines centered on the x/y coord specified
L(ctx, dragon, 8); // pass in context, rules object, and recursion cap

```

**Bonus: Golden Spiral** http://jsfiddle.net/SVkMR/35/show/light/

```
var golden = {
    r:{'A':'FT[TT]A','T':'+F'},
    'F':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    '[':function(c){c.save();},
    ']':function(c){
        c.restore();

        c.beginPath();
        c.arc(0,-this.m,this.m,Math.PI/2,Math.PI);
        c.stroke();

        this.m+=this.d;this.d=this.m-this.d
    },
    '+':function(c){c.rotate(-Math.PI/2);},
    s:'A',
    a:-Math.PI/2,
    m:1,
    d:0
};

```
> 7 votes

# Answer
# Postscript ~~264~~ ~~298~~ ~~295~~ 255

Here's my attempt to do it differently. Rather than the macro-expansion that I usually use, this one checks the size of the execution stack to bound the recursion. If the bound is exceeded, it stops recursively examining the procedure and tries to interpret turtle commands (and discards `pop pop` otherwise). An advantage of this method is that it does not require enormous amounts of memory. A disadvantage is the recursion control is rather clumsy, as the stack size grows by more than just 1 from one recursion level to the next.

*Edit:* +34 chars for branching.
*Edit:* -3 chars. Redesigned to use the operand stack for recursion control. This makes the basic system much simpler. But brackets need an independent stack, so I put the saved position in the dictionary stack, and almost paid back all the savings.

Also, redesigned to use strings and integers instead of arrays and names.

*Edit:* -40 chars. Added two procedures for calling system names by number (I can't seem to get *raw* binary tokens to work. But this idiom works for me.)

```
/*{<920>dup 1 4 3 roll put cvx exec}def/${//* 73
*}def[/T[48{}49{}43{A<88>$}45{A<6e88>$}70{R
0<85>$}91{<1e39>$[/.[<286827>$]cvx>><0d0d>$}93{.<9c6b1e39390d>$}>>/S{dup
B eq{T<0d3e>${<643f>$}<4939>$}{exch{<643e>$ 1 add S}73 *}85 * 1 sub}>><0d6b>$
0 S<a7>$

```

Semi-commented binary.

```
/*{<920>dup 1 4 3 roll put cvx exec}def/${//* 73 *}def %73=forall
[/T[70{R 0<85>$}48{}49{} %<85>=rlineto
43{A<88>$}45{A<6e88>$} %<88>=rotate <6e>=neg
91{<1e39>$ %<1e>=currentdict <39>=end
    [/.[<286827>$]cvx>> %<28>=currentpoint <68>=matrix <27>=currentmatrix
        <0d0d>$} %<0d>=begin
93{.<9c6b1e39390d>$}>> %<9c>=setmatrix <6b>=moveto
/S{dup B eq{T<0d3e>${<643f>$}<4939>$} %<3e>=exch <64>=load <3f>=exec <49>=forall
{exch{<643e>$ 1 add S}73 *}85 * 1 sub}>>
<0d6b>$ 0 S<a7>$  % 85=ifelse <a7>=stroke

```

Un-"binary".

```
[/T[70{R 0 rlineto}48{}49{}43{A rotate}45{A neg rotate}91{currentdict
end[/.[currentpoint matrix currentmatrix]cvx>>begin begin}93{. setmatrix
moveto currentdict end end begin}>>/S{dup B eq{T begin exch{load exec}forall
end}{exch{load exch 1 add S}forall}ifelse 1 sub }>>begin moveto 0 S stroke

```

It requires the L-system to be defined in a dictionary on the dictstack, with the initial string and the starting position of the turtle on the operand stack (prepended to the source, eg. `gs dragon.sys lsys.ps`).

Dragon Curve.

```
%!
[                     %begin dictionary construction
    % productions are described by integer-key/string-value pairs
    48(0+1F) %0       %ascii code for '0' defined as the string "0+1F"
    49(F0-1) %1       %  "     "   "  '1'   "     "   "    "    "F0-1"
    43(+) %+          %  "     "   "  '+' defined as itself
    45(-) %-          %  "     "   "  '-'   "     "   "
    70(F) %F          %  "     "   "  'F'   "     "   "
    % parameters
    /A 90 %angle
    /R 2  %radius
    /B 10 %maximum recursion-level
>>begin  % L-system dictionary on top of dictstack
(F0)     % initial string on stack
300 400  % starting position on stack

```

Branching Stems.

```
[
    48(F[+0]-0) %0
    49(F0-1) %1
    43(+) %+
    45(-) %-
    70(FF) %F
    91([) %[
    93(]) %]
    /A 45 %angle
    /R 5  %radius
    /B 3 %recursion
>>begin
(++0)     % initial string
300 400  % starting position

```

Ungolfed and commented.

```
[                                 % begin dictionary construction
    /T[                           % /T is the Turtle dictionary containing
                                  % integer-key/procedure-value pairs
                                  % keyed to ascii values
        70{R 0 rlineto}        %F
        48{}                   %0
        49{}                   %1
        43{A rotate}           %+
        45{A neg rotate}       %-

          % For brackets, create a dictionary containing a single procedure '.' (dot)
          % which holds a saved matrix (orientation+size) and currentpoint.
          % Since this procedure is called while the Turtle dict is on top of the
          % dictstack, the temporary dictionary is placed just under the top.
        91{currentdict end[/.[currentpoint matrix currentmatrix]cvx>>begin begin} %[
          % Right bracket: reset position and orientation,
          % pop the dict just under the top.
        93{. setmatrix moveto currentdict end end begin}    %]
    >>
    /S{ % stack contains: string recursion-level
        dup B eq{ % hit recursion bound, interpret string as turtle commands
            T begin
                exch % level string
                %dup =
                {                      % iterate through string
                    load exec          % execute turtle command by integer code
                } forall % level       % string has been consumed
            end
            %(B)= pstack
        }{ % recurse
            %(A)= pstack
            exch % level string
            { % level char                   iterate through string
                load exch % string level   process production:load string by int code
                1 add S   % string level+1   increase level and call self
            } forall                       % string has been consumed
        }ifelse
        1 sub            % return level-1
        %(C)= pstack
    }
>>begin
moveto 0 S stroke

```

To run it, these 3 blocks can be saved as 3 files: dragon.ps, stems.ps, lsys.ps (any of the above program blocks will work identically). Then run with gs: `gs dragon.ps lsys.ps` or `gs stems.ps lsys.ps`. They can also be concatenated first, if desired: `cat dragon.ps lsys.ps | gs -` or `cat stems.ps lsys.ps | gs -`.

*No stems picture. It doesn't get any more interesting at higher depths.*
> 5 votes

# Answer
# Mathematica 290

This bare-bones implementation focuses on the output rather than the processing. It does not use production rules. So it may not be a suitable response to the challenge.

Branching stems adapted from Theo Gray's demonstration.

**Code**

```
f@{a_, b_} := {{a, #}, {b, #}} &[a + (b - a)/2 + {{0, 1/2}, {-1/2, 0}}.(b - a)]; w = Flatten;
h[s_, g_] :=Graphics[If[s == 0,Line /@ Nest[w[f /@ #, 1] &, {{{0, 0}, {1, 0}}}, g],
 MapIndexed[Line@# &, NestList[w[Map[{{#[[2]], #[[2]] + m.(#[[2]] - #[[1]])}, {#[[2]],
 #[[2]] + ({{1, -1}, {-1,1}} m).(#[[2]] - #[[1]])}} &, #], 1] &, {{{0, -1}, {0, 0}}}, g]]]]

```

**Usage**

The first parameter determines whether the Dragon Curve or Branch Stems will be displayed. The second term refers to the generation.

```
h[0, 5]
h[1, 5]

```

---

**More Examples**

```
GraphicsGrid@Partition[Flatten[Table[h[j, k], {j, 0, 1}, {k, 10}]], 5]

```
> 4 votes

---
Tags: code-golf, interpreter, graphical-output, fractal
---


# Question
Title: How to determine if a number is odd or even without mod -or- bitwise operations?
How to determine if a number is odd or even without mod -or- bitwise operations?

This challenge is grossly inefficient, but challenges your ability to think outside the box for a creative solution.

***EDIT***:

Please create a function. Also, while regex is a fun response, the function should accept *any* valid number.

***BACKGROUND***: This question stems from my earliest programming days. The homework for our first day of class was to write a simple program that printed 'odd' or 'even'. Being the brat I was, I didn't read the book we had for the class where it simply showed us how to use `%` to determine that. I spent about a half hour pacing back in forth in my room trying to think of a way to do this and had remembered from the lecture that numbers can lose and gain precision as they are cast from one primitive type to another. Therefore, if you took the number, divided it by two and then multiplied it back didn't equal the original number, then you would know that the number was odd.

I was stunned the next day, while our instructor was evaluating our programs, that he thought that it was the most original, if inefficient, way of solving the problem.

# Answer
In most programming languages division returns quotient for integers. So you can simply check this

```
(i/2)*2==i

```
> 40 votes

# Answer
## Python

```
print('even' if (-1)**n==1 else 'odd')

```
> 72 votes

# Answer
## Mathematica

```
SawtoothWave[x / 2] == 0
Exp[I Pi x] - 1 == 0
Sin[5 x / Pi] == 0

```
> 21 votes

# Answer
## Brainf\*** (179)

This is one of the more interesting problems involving conditional logic that I have done in BF.

```
+[>,]<--------------------------------------->>+++++[>+++++++
++++++>+++++++++++++++<<-]>++++>++++<<+<+<-[>-<-[>+<-[>-<-[>+<-[>-<-[>
+<-[>-<-[>+<-[>-<[-]]]]]]]]]]>[>>>.<<-<-]>[>.<-]

```

It takes a text input with a number. If the number is even, it outputs `E`, and if it is odd, it outputs `O`.

I'm proud enough of it that I'll show off a more human readable form:

```
+[>,]                                                   steps through input until it reaches eof.
<---------------------------------------                gets the numerical value of the last digit
>>+++++[>+++++++++++++>+++++++++++++++<<-]>++++>++++    store E and O
<<+<+<                                                  store a bit indicating parity, and a temporary bit
-[>-<                                                   !1
  -[>+<                                                 && !2
    -[>-<                                               && !3
      -[>+<                                             && !4
        -[>-<                                           && !5
          -[>+<                                         && !6
            -[>-<                                       && !7
              -[>+<                                     && !8
                -[>-<[-]]                               && !9
              ]
            ]
          ]
        ]
      ]
    ]
  ]
]
>[>>>.<<-<-]>[>.<-]                                     Display E or O based on the value of the parity bit.

```
> 21 votes

# Answer
## C

Multiplied by itself a few times any even number will overflow to 0 given a finite size integer, and any odd number will continue to have at least the least significant bit set.

```
#include "stdio.h"
long long input=123;
int main(){
    int a;
    for(a=6;a;a--){
        input*=input;
    }
    if(input){
        printf("Odd");
    }
    else{
        printf("Even");
    }
    return 0;
}

```

Edit: As a simple function:

```
int isOdd(long long input){
    int a;
    for(a=6;a;a--){
        input*=input;
    }
    return !!input;
}

```
> 16 votes

# Answer
## JavaScript

```
/[02468]$/.test(i)

```

yields `true` for an even number. This only works with reasonably sized integers (e.g. not scientific notation when converted to a string and not having a fractional part.)
> 13 votes

# Answer
**Python** (Slow)

```
n=1234
while n > 1: n -= 2 #slow way of modulus.
print "eovdedn"[n::2]

```
> 13 votes

# Answer
## Python

Since I'm not really sure what the scoring criteria are, here's a bunch of solutions I've come up with for amusement's sake. Most of them use `abs(n)` to support negative numbers. Most, if not all, of them should never be used for real calculation.

This one is kind of boring:

```
from __future__ import division
def parity(n):
    """An even number is divisible by 2 without remainder."""
    return "Even" if n/2 == int(n/2) else "Odd"

```

---

```
def parity(n):
    """In base-10, an odd number's last digit is one of 1, 3, 5, 7, 9."""
    return "Odd" if str(n)[-1] in ('1', '3', '5', '7', '9') else "Even"

```

---

```
def parity(n):
    """An even number can be expressed as the sum of an integer with itself.

    Grossly, even absurdly inefficient.

    """
    n = abs(n)
    for i in range(n):
        if i + i == n:
            return "Even"
    return "Odd"

```

---

```
def parity(n):
    """An even number can be split into two equal groups."
    g1 = []
    g2 = []
    for i in range(abs(n)):
        g1.append(None) if len(g1) == len(g2) else g2.append(None)
    return "Even" if len(g1) == len(g2) else "Odd"

```

---

```
import ent # Download from: http://wstein.org/ent/ent_py
def parity(n):
    """An even number has 2 as a factor."""
    # This also uses modulo indirectly
    return "Even" if ent.factor(n)[0][0] == 2 else "Odd"

```

---

And this is my favorite although it unfortunately doesn't work (as pointed out by March Ho below: just because all even numbers are the sum of two primes, doesn't mean that all odd numbers aren't).

```
import itertools
import ent    # Download from: http://wstein.org/ent/ent_py
def parity(n)
    """Assume Goldbach's Conjecture: all even numbers greater than 2 can
    be expressed as the sum of two primes.

    Not guaranteed to be efficient, or even succeed, for large n.

    """
    # A few quick checks
    if n in (-2, 0, 2): return "Even"
    elif n in (-1, 1): return "Odd"
    if n < 0: n = -n    # a bit faster than abs(n)
    # The primes generator uses the Sieve of Eratosthenes
    # and thus modulo, so this is a little bit cheating
    primes_to_n = ent.primes(n)
    # Still one more easy way out
    if primes_to_n[-1] == n: return "Odd"
    # Brutish!
    elif n in (p1+p2 for (p1, p2) in itertools.product(primes_to_n, primes_to_n)):
        return "Even"
    else:
        return "Odd"

```
> 12 votes

# Answer
## Haskell

This is, of course, in no way the creative, thinking-outside-the-box solution you're looking for, but how many times am I going to get to post a Haskell answer shorter than GolfScript, really? It's really a shame this isn't a code golf.

```
odd

```

But more seriously:

```
data Parity = Even | Odd
            deriving (Show)

parity = p evens odds
  where p (x:xs) (y:ys) i | i == x = Even
                          | i == y = Odd
                          | otherwise = p xs ys i
        evens = interleave [0,2..] [-2,-4..]
        odds = interleave [1,3..] [-1,-3..]
        interleave (x:xs) ys = x : interleave ys xs

```
> 10 votes

# Answer
Using a deliberately perverse reading of the question, "How to determine if a number is odd or even", here's a C implementation (assume `bool` and `true` are defined appropriately):

```
bool is_odd_or_even(int n)
{
    return true;
}

```
> 7 votes

# Answer
What, no randomized algorithms yet??

## C

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

void prt_parity_of(int n){
  int i,j=2;
  char o[]="eovdedn"
     , f[n=abs(n)]; for(i=n;i-->0;f[i]=1);

  while(j>1){
    while((i=rand()%n)
       == (j=rand()%n)
       || (f[i]&f[j]>0)
       && (f[i]=f[j]=0)
    );for(i=j=0; ++i<n; j+=f[i])
  ;}for(;j<7;j+=2)putchar(o[j]);
}

```

Randomly pairs numbers in the range 0..*n*-1 until less than 2 are left. It's quite amazingly inefficient: *O*(*n*3).

---

Completely different:

## Haskell

```
import Data.Complex

ft f = (\ω -> sum[ f(t) * exp(0:+2*pi*ω*t) | t<-[-1,-0.9..1] ] )

data Parity = Even | Odd deriving (Show)

parity n
  | all (\(re:+im) -> abs re > abs im) [ft ((:+0).(^^n)) ω | ω<-[0..20]]  = Even
  | otherwise                                                             = Odd

```

Uses the fact that the Fourier transform of an even function (e.g. `\x->x^^4`) is real, while the Fourier transform of an odd function is imaginary.
> 7 votes

# Answer
## Coq, 103

```
Fixpoint even n:=match n with O=>true|S n=>odd n end with odd n:=match n with O=>false|S n=>even n end.

```

As far as I can tell this is the first coq entry on codegolf.

Even shorter (59):

```
Fixpoint even n:=match n with O=>true|S n=>negb(even n)end.

```
> 6 votes

# Answer
## Windows PowerShell

```
function OddOrEven([long]$n) {
  if (0,2,4,6,8 -contains "$n"[-1]-48) {
    "Even"
  } else {
    "Odd"
  }
}

```
1. Convert to string
2. Pick last letter (digit) (essentially a mod 10).
3. Check if it is 0, 2, 4, 6 or 8.

No bitwise operators, no modulus, as requested.
> 5 votes

# Answer
## Ruby

```
n.odd?

```

If you want to print out the result:

```
f[n] = ->(n){puts n.odd?? 'odd' : 'even'}

```
> 4 votes

# Answer
## Unlambda

The world needs more Unlambda.

Unlambda has a killer advantage here: its default (*ahem*) representation for numbers are Church numerals, so all that's needed is to apply them to function binary-not to function true. Easy!

PS: Markdown and Unlambda are definitely not made for one another.

```
true  = i
false = `ki
not   = ``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki
even? = ``s``si`k``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki`ki

```

Verification for the first few integers:

```s``si`k``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki`ki`ki                   => i
```s``si`k``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki`kii                     => `ki
```s``si`k``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki`ki``s``s`kski           => i
```s``si`k``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki`ki``s``s`ksk``s``s`kski =>`ki

> 4 votes

# Answer
## Golfscript

```
~,2/),1=\;

```
> 3 votes

# Answer
## Python

```
print (["even"] + (["odd", "even"] * abs(n)))[abs(n)]

```

Similar performance to the earlier version. Works for 0 now.

**Incorrect Earlier version:**

```
print ((["odd", "even"] * abs(n))[:abs(n)])[-1]

```

Not particularly efficient; time and memory both obviously O(n): 32 msec for 1,000,000; 2.3 msec for 100000; 3.2 usec for 100. Works with negative numbers. Throws an error for 0, because 0 is neither even nor odd.
> 3 votes

# Answer
### Fractran

```
[65/42,7/13,1/21,17/7,57/85,17/19,7/17,1/3]

```

applied to

```
63*2^abs(n)

```

yields either `5` if `n` is odd or `1` if `n` is even.

**Update**: Much shorter but not so interesting:

```
[1/4](2^abs(n))

```

is `2` for odd `n` and `1` for even `n`.
> 3 votes

# Answer
## Perl

What about

```
use Math::Trig;
print(cos(pi*@ARGV[0])>0?"even":"odd")

```
> 3 votes

# Answer
## MMIX (4 Bytes)

This is kind of cheating. I use neither mod nor bit fiddling operations. It's rather that testing for odd / even numbers is builtin. Assuming that `$3` contains the number to test and the result goes into `$2`:

```
ZSEV $2,$3,1

```

sets `$2` to `1` if `$3` is even and to `0` if not. The mnemnoric `ZSEV` means *zero-set even* and has the following semantics:

```
ZSEV a,b,c: if (even b) a = c; else a = 0;

```

For the above line, `mmixal` generates these four bytes of assembly:

```
7F 02 03 01

```
> 3 votes

# Answer
# Scheme

This is the most inefficient solution I know of.

```
(letrec ([even? (lambda (n)
                 (if (zero? n) "even"
                     (odd? (- n 2))))]
         [odd? (lambda (n)
                 (if (= n 1) "odd"
                     (even? (- n 2))))])
  (even? (read)))

```
> 3 votes

# Answer
## JavaScript, 36

```
function(i){while(i>0)i-=2;return!i}

```

Returns `true` if even, `false` if not.
> 2 votes

# Answer
## Perl

```
$n x '0' =~ /^(00)*$/

```
> 2 votes

# Answer
## Python

```
zip((False, True)*(i*i), range(i*i))[-1][0]

```

testing the square of i, so it works for negative numbers too
> 2 votes

# Answer
# F#

Mutual recursion for the win.

A number n is even if it is zero or (n-1) is odd.

A number n is odd if it is unequal to zero and (n-1) is even.

(abs added in case anyone's interested in the parity of negative numbers)

```
let rec even n = n = 0 || odd (abs n - 1)
    and odd n = n <> 0 && even (abs n - 1)

```
> 2 votes

# Answer
# Clojure

```
  (defmacro even?[n]
  `(= 1 ~(concat (list *) (repeat n -1))))

```
> 2 votes

# Answer
What qualifies as bitwise operations? Under the hood, integer division by 2 is likely to be implemented as a bit-shift.

Assuming bitshifts aren't out:

# C/C++

```
(unsigned char)((unsigned char)(n > 0 ? n : -n) << 7) > 0 ? "odd" : "even"

```

*edit* Missed some parentheses, and ultimately changed to remove a shift to make it do less. You can test this with the following (in \*nix):

```
echo 'main(){ std::cout<< (unsigned char)((unsigned char)(n > 0 ? n : -n) << 7) > 0 \
        ? "odd\n" : "even\n";}' \
  | gcc --include iostream -x c++ -o blah -
./blah

```

... though in Linux/tcsh, I had to escape the backslash on `\n` even though it was in single-quotes. I tested in little & big-endian, it works correctly in both. Also, I hand-copied this; the computer I'm posting with doesn't have a compiler, so it may have mistakes.

# x86 asm

```
            mov eax, n          # Get the value
            cmp eax,0           # Is it zero?
            jge pos_label       # If >= 0, skip the next part
            neg eax
pos_label:

```

.

```
            imul al, 128

```

or

```
            shl  al, 7

```

or

```
            lea  eax, [eax*8]    # Multiply by 2^3 (left-shift by 3 bits)
            lea  eax, [eax*8]    # ... now it's n*2^6
            lea  eax, [eax*2]    # ... 2^7, or left-shift by 7 bits

```

... followed by:

```
            cmp al,  0          # Check whether the low byte in the low word is zero or not
            jz  even_label      # If it's zero, then it was an even number
            odd_label           # ... otherwise it wasn't

```

Alternatively, the shift & compare stuff could be done this way as well:

```
            sar al,1            # signed integer division by 2 on least-significant byte
            jc  odd_label       # jump if carry flag is set

```
> 2 votes

# Answer
On a 68000 processor you could move a word value from the address defined by the value to test:

```
 move.l <number to test>,a0
 move.w (a0),d0
 ; it's even if the next instruction is executed

```

and let the hardware trap for address error determine the odd/even nature of the value - if the exception is raised, the value was odd, if not, the value was even:

```
 <set up address error trap handler>
 move.l <pointer to even string>,d1
 move.l <number to test>,a0
 move.w (a0),d0
 <reset address error trap handler>
 <print string at d1>
 <end>

 address_error_trap_handler:
 move.l <pointer to odd string>,d1
 rte

```

Doesn't work on Intel x86 CPUs as those are more flexible about data access.
> 2 votes

# Answer
# Python

I decided to try for the ugliest, most confusing solution I could think of:

```
n=input();r=range(n+1)
print [j for i in zip(map(lambda x:str(bool(x))[4],[8&7for i in r]),
map(lambda x:str(x)[1],[[].sort()for x in r])) for j in i][n]

```

Prints e if even, o if odd.
> 2 votes

# Answer
# Q

Keep subtracting 2 until x\<2 then convert to bool

```
{1b$-[;2]/[2<=;abs x]}

```
> 2 votes

# Answer
# Mathematica

**Edit**: This is the unimaginative check that many folks, including me, use. If an integer ends in 0,2,4, 6,or 8, it is even, otherwise odd.

```
f[n_?IntegerQ] := Print[n, " is ",
If[MemberQ[{0, 2, 4, 6, 8}, IntegerDigits[n][[-1]]], "even.", "odd."]]

```

**Original solution**:

The following is even more unimaginative and uselessly slow for "large" integers, but in principle, it works.

If an integer has 2 is its lowest prime factor, it is even.

```
f[n_?IntegerQ]:= Print[n, " is ", If[FactorInteger[n][[1, 1]] == 2, "Even", "Odd"]

```
> 2 votes

# Answer
### scala:

```
scala> def evenOrOdd (n:Int) : Unit = n match {
     | case 0 => println ("even")
     | case 1 => println ("odd")
     | case _ => evenOrOdd (n-2) }
evenOrOdd: (n: Int)Unit

scala> evenOrOdd (123456789)
odd

```

(less than one second)
> 1 votes

# Answer
Are we allowed to submit utterly terrible ways to do this? If so...

# C

```
#include <stdio>

void oddOrEven(int number)
{
   char test[128];
   sprintf(test, "%d", number);

   int index = strlen(test) - 1;

   if((test[index]=='0')||(test[index]=='2')||(test[index]=='4')||
        (test[index]=='6')||(test[index]=='8'))
   {
      printf("Even.");
   } else {
      printf("Odd.");
   }
}

```

I apologize for any errors, I don't have a chance to compile or test this. Fixed one bug, per comment by Joey Adams.

This answer is similar to the one posted by idealmachine
> 1 votes

# Answer
# Perl

`sub is_odd {$#{[split/\./,$_[0]/2]}}`
> 1 votes

# Answer
## C++ (63)

Token absurd recursive solution. Even golfed!

```
#include <math.h>
bool o(int v){return v==0?false:!o(abs(v)-1);}

```
> 1 votes

# Answer
For C or C++, easy enough:

```
int Temp = 20
double Temp2 = ((double)Temp/2);
Temp2 = Temp2 - ((int)Temp/2);
if(Temp2 != 0.0)
{
    printf("It's odd!\n");
}
else
{
    printf("It's even!\n");
}

```
> 1 votes

# Answer
# C#

Sorry for my previous response, I'm totally messed up today.

```
bool Even(int i){return i==0||!Even(i-1);}

```
> 1 votes

# Answer
```
function isEven(i) {
    return i == 0 || !isEven(i - (i > 0 ? 1 : -1));
}

```
> 1 votes

# Answer
return exp(sqrt(-1)\*x\*pi)==1?"even":"odd";
> 1 votes

# Answer
# C++11

(for C++03, replace `long long` with `long` and `-2ull` with `-2ul`)

Yet another solution which takes advantage of the fact that integers have finite size, together with the fact that unsigned arithmetic is defined as modulo arithmetic. It also uses the fact that conversion of integer types to `bool` gives `true` iff the converted number is nonzero.

```
bool odd(unsigned long long n) // note: signed->unsigned conversion preserves oddity
{
  return n * (1 + -2ull / 2);
}

```
> 1 votes

# Answer
# Perl

```
if ((int(($number/2)) * 2) == $number) { print ("even"); }

```
> 1 votes

# Answer
# Bash

This script asks Wolfram|Alpha whether a number is even or odd:

```
#!/bin/bash

curl -s "http://www.wolframalpha.com/input/?i=even($1)" | grep 'is even' > /dev/null

if [ $? -eq 0 ]
then
    echo Yes
else
    echo No
fi

```
> 1 votes

# Answer
## Haskell, Recduction from Towers of Hanoi

When moving `n` pegs from `A` to `B`, then for even `n`, the first move is `A->C`.
Doesn't work for n=0.

```
data Peg = A|B|C deriving Eq
third :: Peg -> Peg -> Peg
third x y
    | x/=A && y/=A = A
    | x/=B && y/=B = B
    | x/=C && y/=C = C

data Move = Move Peg Peg deriving Eq

-- Move n pegs from a to b
hanoi :: Int -> Peg -> Peg -> [ Move ]
hanoi 0 _ _ = []
hanoi n a b = (hanoi (n-1) a c) ++ [Move a b] ++ (hanoi (n-1) c b) where
    c = third a b

-- n is even if the first step in moving n discs from A to B is A->C.
iseven :: Int -> Bool
iseven n = (head $ hanoi n A B) == Move A C

```
> 1 votes

# Answer
# Perl

This always returns a `.` when the number is odd, and either an integer or nothing when it is even.

```
chop($_=<>/2);print chop

```

If you want it to actually print the word "odd" or "even" then it needs to be expanded to the following:

```
chop($_=<>/2);if(chop=='.'){print"Odd"}else{print"Even"}

```

OR, if you want the program to exit once it gives a result, this can be written as:

```
chop($_=<>/2);if(chop=='.'){die"Odd"}die"Even"

```
> 0 votes

# Answer
# VB.Net

```
return (i\2)*2=i

```

Notice the use of the backslash operator `\` that performs a integer division and discards any reminders. The usage of a forvard slash operator `/` would not work for this solution.
> 0 votes

# Answer
## Haskell

```
odd = (<)0.(^)(-1)
even = (>)0.(^)(-1)

```

##

```
odd =: 0>_1&^
even =: 0<_1&^

```

If (-1)*n*\<0, *n* is odd; if (-1)*n*\>0, *n* is even.

```
odd =: [:|[:{:@+.0j1&^
even =: [:|[:{.@+.0j1&^

```

Taking the imaginary/real part of *i**n* would be a neat way to do it too, but needs better thresholding than this.
> 0 votes

# Answer
use queue and push pop, if element remains at last, it's odd, else is even:

```
var q = new Queue<int>();
for (int i=0;i<n;i++)
{
   if (q.Count > 0)
     q.Pop();
   else q.Push(0);
}

if (q.Count != 0)
  return "Odd";
return "Even";

```
> 0 votes

# Answer
# Python

Somebody already used this idea, but this implementation is more concise:

```
def even(n):return str(n)[-1]in'02468'

```
> 0 votes

# Answer
**Squeak Smalltalk**

Since printing in base 2 would be too obvious and a big waste of time because only the last digit counts

```
odd
    ^(self printStringBase: 2) last = $1

```

I decided to rather print in base 3 to at least scan all the digits

```
odd
    ^self ~= 0 and: [self = 1 or: [((self printStringBase: 3) occurrencesOf: $1) odd]]

```

Of course, if we have more CPU to waste, we can just enumerate

```
odd
    ^(1 to: self abs) inject: false into: [:odd :int | odd not]

```

Finally, if we are impatient, this might be a bit faster

```
odd
    (0 to: self abs by: 2) size - (1 to: self abs by: 2) size = 0

```
> 0 votes

# Answer
## R

```
is.even<-function(n){
    options(warn=-1)
    res<-ifelse(sum(matrix(1:abs(n),nrow=2)==1)!=1, "Odd", "Even")
    options(warn=0)
    res
    }

```

The idea is to build a 2-rows matrix with the sequence 1 to the absolute value of n (to allow negative numbers). If the number is odd, the sequence has to be recycled to fill the 2 rows, so the matrix contains twice the number 1. Due to the method, it doesn't work with large numbers but it works with zero.

```
> is.even(0)
[1] "Even"
> is.even(467)
[1] "Odd"
> is.even(-46798)
[1] "Even"
> is.even(9999999999)
Error in 1:abs(n) : result would be too long a vector

```
> 0 votes

---
Tags: code-challenge
---


title: IPv4 "in subnet" function

text:
# Question
Title: IPv4 "in subnet" function
Implement the following JavaScript method as short as possible:

```
function same_subnet(ip_a,ip_b,sn_mask)
{

}

```

It should get 2 IP addresses and a subnet mask. It should return `true` if `ip_a` and `ip_b` are in the same subnet.

Example calls:

1. `same_subnet("192.168.0.1","192.168.0.15","255.255.255.0")``true`
2. `same_subnet("192.168.0.1","192.168.1.15","255.255.0.0")``true`
3. `same_subnet("192.168.0.1","192.168.1.15","255.255.255.0")``false`

# Answer
# 126

Fits into a tweet and doesn't even leak globals.

```
function same_subnet(a,b,c){function x(n){return n=n.split("."),n[0]<<24|n[1]<<16|n[2]<<8|n[3]}return(x(a)&x(c))==(x(b)&x(c))}

```
> 1 votes

---
Tags: javascript
---


title: Create a GUI Piano

text:
# Question
Title: Create a GUI Piano
## Challenge

Create a GUI Keyboard with as few characters as possible.

## Example

Because this was an assignment in one of my courses, I can't show the source code. However, here is a screen shot of my keyboard.

In this example, my keys were of type `JButton` and I used a Midi Synthesizer to produce the sound (with the default ADSR envelope values).

## Rules

* You **are allowed** to use standard external libraries.
* Be creative with your sound. You can use 8-bit, a sitar, etc.
* For simplicities sake, you may have five keys; black and white, from C to E (the first five keys on my keyboard).
* Most importantly... showcase your work!

**NOTICE**: Depending on what language you choose to work with, this may be a rather large task.

This is my first question on SE Code Golf. If anything is unclear, please ask for further details.

---

**EDIT**: The due date for this challenge will be 9/22/12. If you post an answer after this date, I will look over it regardless (and possibly +1 it).

# Answer
> 11 votes
# Mathematica 319 259 255

---

Edit: Keys now depress (as buttons) when clicked.

---

This will play the grand piano notes {"C","C#","D","D#","E"}, where "C" is middle C. `z[n_]` plays the note.

```
z@n_ := EmitSound@Sound[SoundNote[n, .3, 1]]; w = {10, 300}; b = {35, 180};
Graphics[Inset[Button["", z[#[[1]]], Background -> If[#[[2]] == w, None, Black],
ImageSize -> #〚2〛], #〚3〛] & /@ {{"C", w, {-.4, 0}}, {"D", w, {0, 0}}, {"E", w, {.4, 0}},
{"C#", b, {-.2, 0.31}}, {"D#", b, {.2, 0.31}}}, PlotRange -> 1]

```

---

The keyboard can be extended to 18-keys by using fewer than double the characters:

```
z@n_ := EmitSound@Sound@SoundNote[n, .3, 1];
w = {"C", "D", "E", "F", "G", "A", "B", "C5", "D5", "E5", "F5"};
b = {"C#", "D#", "", "F#", "G#", "A#", "", "C#5", "D#5"}; i = ImageSize; t = Thread;
l = List; s = Inset; m = Table; u = Button;
Graphics[Join[t[s[u @@@ t[l["", y /@ w, i -> {5, 350}]] /. y -> z, m[{90 k, 0}, {k, -5, 5}]]],
Delete[t[s[u @@@ t[l["", y /@ b, Background -> Black, i -> {28, 212}]] /.
  y -> z, m[{90 k + 45, 220}, {k, -5, 3}]]], {{3}, {7}}]],
AspectRatio -> .45, PlotRange -> {{-500, 500}, {-610, 610}}, i -> {800, 430}]

```

# Answer
> 10 votes
## Web page (840/796 characters)

\>\>\> **Start playing** (Internet Explorer is not supported for multiple reasons; Google Chrome and Opera work best.)

I probably could make this a bit shorter, yet it is a good start. The lower score is after replacing all occurrences of ` ` with the character itself and removing the keyword `new`, the latter change breaking Google Chrome compatibility.

```
<style>table{border-collapse:collapse;border-width:1 0;border-style:solid;font-size:64;line-height:2}td{border-style:solid;border-width:0 1}</style><table><td colspan=3 title=0> <td bgcolor=black colspan=2 title=1> <td colspan=2 title=2> <td bgcolor=black colspan=2 title=3> <td colspan=3 title=4> <tr><td colspan=4 title=0> <td colspan=4 title=2> <td colspan=4 title=4> </table><script>for(A=[y=5];y--;){for(s=x=64e3;x--;)s+="~ "[x*(268+17*y)>>13&1];A[y]=new Audio("data:audio/wav;base64,UklGRiXuAgBXQVZFZm10IBAAAAABAAEAQB8AAEAfAAABAAgAZGF0YQHuAgCA"+btoa(s))}setInterval("for(y=5;y--;)with(A[y])volume=volume&&Math.exp(-currentTime)",99);onmousedown=function(e){if(z=e.target.title)with(A[z])play(currentTime=0,volume=1)};onmouseup=function(e){if(z=e.target.title)with(A[z])pause(volume=0)}</script>

```

Save this code as a text file with a name ending in .htm or .html and open it in Chrome or Opera (Safari might also work), or just open the solution's JSBin page to start playing. I reused the WAV file header from my solution to the Twinkle Twinkle Little Star code golf problem.

An important feature is that the sound diminishes as time passes. To observe this behavior, try holding down a key for a few seconds and listening to what happens.

Here is a more readable version of the code:

```
<style>
    table {
        border-collapse: collapse;
        border-width: 1 0;
        border-style: solid;
        font-size: 64;
        line-height: 2;
    }

    td {
        border-style: solid;
        border-width: 0 1;
    }
</style>

<table>
        <td colspan=3 title=0>
        <td bgcolor=black colspan=2 title=1>
        <td colspan=2 title=2>
        <td bgcolor=black colspan=2 title=3>
        <td colspan=3 title=4>
    <tr>
        <td colspan=4 title=0>
        <td colspan=4 title=2>
        <td colspan=4 title=4>
</table>

<script>
    for (A = [y = 5]; y--;) {

        for (s = x = 64e3; x--;)
            s += "~ "[x * (268 + 17 * y) >> 13 & 1];

        A[y] = new Audio("data:audio/wav;base64,UklGRiXuAgBXQVZFZm10IBAAAAABAAEAQB8AAEAfAAABAAgAZGF0YQHuAgCA" + btoa(s));
    }

    setInterval(function() {
        for (y = 5; y--;)
            with (A[y])
                volume = volume && Math.exp(-currentTime);
    }, 99);

    onmousedown = function(e) {
        if (z = e.target.title)
            with (A[z])
                play(currentTime = 0, volume = 1);
    };

    onmouseup = function(e) {
        if (z = e.target.title)
            with (A[z])
                pause(volume = 0);
    };
</script>

```

# Answer
> 6 votes
## Groovy: 577 (703 with whitespaces)

The first 5 notes. Others could be added easily, it's somewhat dynamic.

Damn swing. Probably with a swing lib it would be better.

Plays through JFugue.

On github: https://github.com/wpiasecki/glissando/blob/master/src/br/glissando/Piano.groovy

On groovy 2.0.2

```
import java.awt.event.*
class Note { def n; boolean s; def p() { new org.jfugue.Player().with {play n;close()}} }
notes=['C','C#','D','D#','E'].inject([]){ l,n -> l<< Note[n:n,s:n=~/#/]}
h=300
l=0
w=60
x=0
new groovy.swing.SwingBuilder().edt {
  frame size:[notes.size()*30+30,h],
    show:true,
    defaultCloseOperation:javax.swing.JFrame.EXIT_ON_CLOSE,
    { l = layeredPane() }
  notes.each { n ->
    C=java.awt.Color
    s=n.s
    p=panel bounds:(s ? [x-15,0,w-30,h-100] : [x,0,w,h]),
      background: s ? C.BLACK : C.WHITE,
      border: lineBorder(1, color: C.BLACK)
    p.addMouseListener({ if(it.id==MouseEvent.MOUSE_CLICKED)n.p() }as MouseListener)
    if(!s)x+=w
    l.add p,s?0:1
  }
}

```

# Answer
> 1 votes
## R - 491 characters

I'm a little late but I just saw this post yesterday.

Works on a Mac, uses playRWave and packages `tuneR` and `splancs`.

```
a=array
x=c(7,2)
y=c(5,2)
z=c(1,1,3,3)
par(mar=rep(0,4))
plot(NA,xli=c(0,9),yli=c(0,3))
N=list(a(c(0,3,3,2,2,0,0,0,0,z,0),x),a(c(3,6,6,5,5,4,4,3,3,0,0,z,1,1,0),c(9,2)),a(c(6,6,7,7,9,9,6,0,z,0,0),x),a(c(2,4,4,2,2,z,1),y),a(c(5,7,7,5,5,z,1),y))
c=c(NA,NA,NA,1,1)
for(i in 1:5){polygon(N[[i]],c=c[i])}
h=c(261.63,293.66,329.63,277.18,311.13)
library(tuneR)
setWavPlayer("~/Library/Audio/playRwave")
repeat{P=data.frame(locator(1));play(sine(h[sapply(N,function(x)splancs::inout(P,x))],bit=16))}

```

Ungolfed:

```
par(mar=rep(0,4))
plot(NA,xlim=c(0,9),ylim=c(0,3)) #Create empty plot: due to fuzzy matching of arguments, xlim can be reduced to xli
N=list(array(c(0,3,3,2,2,0,0,0,0,1,1,3,3,0),dim=c(7,2)), #C polygon
       array(c(3,6,6,5,5,4,4,3,3,0,0,1,1,3,3,1,1,0),dim=c(9,2)), #D polygon
       array(c(6,6,7,7,9,9,6,0,1,1,3,3,0,0),dim=c(7,2)), #E polygon
       array(c(2,4,4,2,2,1,1,3,3,1),dim=(5,2)), #Db polygon
       array(c(5,7,7,5,5,1,1,3,3,1),dim=(5,2)))  #Eb polygon
c=c(NA,NA,NA,1,1) #Colors: by default 1 is "black"
for(i in 1:5){polygon(N[[i]],color=c[i])}
h=c(261.63,293.66,329.63,277.18,311.13) #Notes frequency in hertz: C4, D4, E4, Db4 and Eb4
library(tuneR)
setWavPlayer("~/Library/Audio/playRwave") #This can be change to other wav player I think
repeat{
    P=data.frame(locator(1)) #Grab coordinates of selected point
    H=h[sapply(N,function(x)splancs::inout(P,x))] #In which polygon does the selected point belong to, then map it to its ferquency
    s=sine(H,bit=16) #By default create a 1sec note at the given frequency with 44100 sampling rate
    play(s)
    }

```

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


title: Solve Rubik's cube

text:
# Question
Title: Solve Rubik's cube
Write the shortest program that solves Rubik's cube (3\*3\*3) within a reasonable amount of time and moves (say, max. 5 seconds on your machine and less than 1000 moves).

The input is in the format:

```
UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR

```

(this particular input represents the solved cube).
First 12 2-character strings are the edges in the UF, UR, ... BL positions (U=up, F=front, R=right, B=back, L=left, D=down), then the next 8 3-character strings are the corners in the UFR, URB, ... DBR positions.

The output should give a sequence of moves in this format:

```
D+ L2 U+ F+ D+ L+ D+ F+ U- F+

```

Where D1 or D+ represents turning the D (down) face clockwise 90 degrees, L2 is turning the L face 180 degrees, U3 or U- represents turning the U face counterclockwise 90 degrees.
Letters are case-insensitive and spaces are optional.

For example, the output above is correct for the following input:

```
RU LF UB DR DL BL UL FU BD RF BR FD LDF LBD FUL RFD UFR RDB UBL RBU

```

For more details, please refer to Tomas Rokicki's cube contest, except scoring will be done directly by file size like a normal code golfing problem. An online tester is included too.

For reference, the shortest solution already written is the last entry in the list of cube contest winners

---

For those struggling to visualise the layout format:

```
0-1 2-3 4-5 6-7 8-9 10-11 12-13 14-15 16-17 18-19 20-21 22-23 24-25-26 27-28-29 30-31-32 33-34-35 36-37-38 39-40-41 42-43-44 45-46-47
UF  UR  UB  UL  DF   DR    DB   DL    FR    FL     BR    BL     UFR      URB      UBL      ULF      DRF      DFL      DLB      DBR

Front:

                 +-------+-------+-------+
                /       /       /       /|
               /  30   /   4   /  27   / |
              +-------+-------+-------+  |
             /       /       /       /|28+
            /   6   /       /   2   / | /|
           +-------+-------+-------+  |/ |
          /       /       /       /|3 +  |
         /  33   /   0   /  24   / | /|21+
        +-------+-------+-------+  |/ | /|
        |       |       |       |26+  |/ |
        |  35   |   1   |   25  | /|  +  |
        |       |       |       |/ | /|47+
        +-------+-------+-------+  |/ | /
        |       |       |       |17+  |/
        |  18   |       |  16   | /|11+
        |       |       |       |/ | /
        +-------+-------+-------+  |/
        |       |       |       |37+
        |  40   |   9   |  38   | /
        |       |       |       |/
        +-------+-------+-------+

Hidden faces:

                 +-------+-------+-------+
                /|       |       |       |
               / |  31   |   5   |  29   |
              +  |       |       |       |
             /|32+-------+-------+-------+
            / | /|       |       |       |
           +  |/ |  22   |       |  20   |
          /|7 +  |       |       |       |
         / | /|23+-------+-------+-------+
        +  |/ | /|       |       |       |
        |34+  |/ |  44   |  13   |  46   |
        | /|  +  |       |       |       |
        |/ | /|43+-------+-------+-------+
        +  |/ | /       /       /       /
        |19+  |/  42   /  12   /  45   /
        | /|15+-------+-------+-------+
        |/ | /       /       /       /
        +  |/  14   /       /  10   /
        |41+-------+-------+-------+
        | /       /       /       /
        |/  39   /   8   /   36  /
        +-------+-------+-------+

```

# Answer
> 26 votes
# C++ - 1123

Since nobody posted any answer so far, I decided to simplify and golf my 2004 solution. It's still far behind the shortest one I mentioned in the question.

```
#include<iostream>
#include<vector>
#define G(i,x,y)for(int i=x;i^y;i++)
#define h(x)s[a[x]/q*q+(a[x]+j)%q-42]
#define B(x)D=x;E=O.substr(j*3,3);G(i,0,3)E+=F[5-F.find(E[2-i])];G(i,0,D.length())D[i]=E[F.find(D[i++])];m.push_back(D);
#define P(a,b)G(i,0,6)G(k,49,52){e[0]=F[i];e[1]=k;m.push_back(e);}G(j,0,24){B(a)B(b)}
#define T C();z=m.size();for(b=c;b;){d=s;G(i,o=w=1,4){w*=z;if(o)G(j,0,w)if(o){s=d;u=j;G(k,0,i){f=m[u%z];G(x,0,f.length()){a=M[F.find(f[x++])];G(i,0,f[x]-48)G(l,0,2){q=3-l;p=4*l;G(j,0,q){t=h(p+3);G(k,-3,0)h(p-k)=h(p-1-k);h(p)=t;}}}u/=z;}C();if(c<b){u=j;G(k,0,i){std::cout<<m[u%z];u/=z;}b=c;o=0;}}}}
std::string s,a,D,E,d,f,e="  ",S="UFURUBULDFDRDBDLFRFLBRBLUFRURBUBLULFDRFDFLDLBDBR",F="ULFBRD",M[]={"KHEB*0.,","KRTI0<8@","KDNS*;2=","IVXG/@7>","BGWP,>4:","QNWT2468"},O=S.substr(24)+"FDRFRUFULFLDRDBRBURUFRFDBDLBLUBURBRDLDFLFULUBLBD";std::vector<std::string>m;int
w,X=8,Y=16,o,c,u,b,z,p,q,t;void C(){c=0;G(i,X,Y)c+=s[i]!=S[i];}main(int
g,char**v){G(i,1,g)s+=v[i];P("U2F1R1L3U2L1R3F1U2","L3R1F3L1R3D2L3R1F3L1R3");T;Y=24;T;X=0;T;m.clear();P("R3D3R1D3R3D2R1L1D1L3D1L1D2L3","R1F3L3F1R3F3L1F1");G(I,5,9){Y=I*6;T}}

```

It's not random, but it also doesn't proceed straightforwardly. It solves the edges first, then the corners. At each step, it tries various combinations of up to 4 algorithms and simple face turns (sequentially, not randomly), till it finds an improvement in the number of solved pieces, then repeats until solved. It uses 2 algorithms for edges and 2 for corners, translated to all cube positions.

Example output for `RU LF UB DR DL BL UL FU BD RF BR FD LDF LBD FUL RFD UFR RDB UBL RBU`:

L2F3B2F3B1U3F1B3R2F3B1U3F1B3D2F2L3D2L1U2B1L1R3U2R1L3B1U2R1U2L1F1B3U2B1F3L1U2L3R1D3L1R3B2L3R1D3L1R3L3R1D3L1R3B2L3R1D3L1R3B3F1D3B1F3R2B3F1D3B1F3U2F3L3R1B3L1R3U2L3R1B3L1R3F1D2F1L1R3D2R1L3F1D2F3L2U1B1F3L2F1B3U1L2R3L1F3R1L3U2R3L1F3R1L3U1F2U1L1R3F2R1L3U1F2U3L3U3L1U3L3U2L1R1U1R3U1R1U2R3F3U3F1U3F3U2F1B1U1B3U1B1U2B3L1B3R3B1L3B3R1B1B3D3B1D3B3D2B1F1D1F3D1F1D2F3R1F3L3F1R3F3L1F1R3B3R1B3R3B2R1L1B1L3B1L1B2L3R1D3L3D1R3D3L1D1B3D3B1D3B3D2B1F1D1F3D1F1D2F3U3R3U1R3U3R2U1D1R1D3R1D1R2D3

(234 moves, 0.3 sec here)

# Answer
> 25 votes
## Python 1166 bytes

*A considerable amount of whitespace has been left for the sake of readability. Size is measured after removing this whitespace, and changing various indentation levels to `Tab`, `Tab` `Space`, `Tab` `Tab`, etc. I've also avoided any golfing which affected the performance too drastically.*

```
T=[]
S=[0]*20,'QTRXadbhEIFJUVZYeijf',0
I='FBRLUD'

G=[(~i%8,i/8-4)for i in map(ord,'ouf|/[bPcU`Dkqbx-Y:(+=P4cyrh=I;-(:R6')]
R=range

def M(o,s,p):
 z=~p/2%-3;k=1
 for i,j in G[p::6]:i*=k;j*=k;o[i],o[j]=o[j]-z,o[i]+z;s[i],s[j]=s[j],s[i];k=-k

N=lambda p:sum([i<<i for i in R(4)for j in R(i)if p[j]<p[i]])

def H(i,t,s,n=0,d=()):
 if i>4:n=N(s[2-i::2]+s[7+i::2])*84+N(s[i&1::2])*6+divmod(N(s[8:]),24)[i&1]
 elif i>3:
  for j in s:l='UZifVYje'.find(j);t[l]=i;d+=(l-4,)[l<4:];n-=~i<<i;i+=l<4
  n+=N([t[j]^t[d[3]]for j in d])
 elif i>1:
  for j in s:n+=n+[j<'K',j in'QRab'][i&1]
 for j in t[13*i:][:11]:n+=j%(2+i)-n*~i
 return n

def P(i,m,t,s,l=''):
 for j in~-i,i:
  if T[j][H(j,t,s)]<m:return
 if~m<0:print l;return t,s
 for p in R(6):
  u=t[:];v=s[:]
  for n in 1,2,3:
   M(u,v,p);r=p<n%2*i or P(i,m+1,u,v,l+I[p]+`n`)
   if r>1:return r

s=raw_input().split()
o=[-(p[-1]in'UD')or p[0]in'RL'or p[1]in'UD'for p in s]
s=[chr(64+sum(1<<I.find(a)for a in x))for x in s]

for i in R(7):
 m=0;C={};T+=C,;x=[S]
 for j,k,d in x:
  h=H(i,j,k)
  for p in R(C.get(h,6)):
   C[h]=d;u=j[:];v=list(k)
   for n in i,0,i:M(u,v,p);x+=[(u[:],v[:],d-1)]*(p|1>n)
 if~i&1:
  while[]>d:d=P(i,m,o,s);m-=1
  o,s=d

```

Sample usage:

```
$ more in.dat
RU LF UB DR DL BL UL FU BD RF BR FD LDF LBD FUL RFD UFR RDB UBL RBU

$ pypy rubiks.py < in.dat
F3R1U3D3B1
F2R1F2R3F2U1R1L1
R2U3F2U3F2U1R2U3R2U1
F2L2B2R2U2L2D2L2F2

```

This is an implementation of Thistlethwaite's Algorithm, using an IDA\* search to solve for each step. Because all of the heuristic tables need to be calculated on the fly, several compromises have been made, usually breaking a heuristic into two or more fairly equal size parts. This makes the computation of the heuristic tables many hundreds of times faster, while slowing down the search phase, usually only slightly, but it can be significant depending on the initial cube state.

### Variable Index

* `T` \- the main heuristic table.
* `S` \- a solved cube state. Each individual piece is stored as a bit mask, represented as a character. A solved orientation vector is defined as the zero vector.
* `I` \- the various twists, in the order that they are eliminated from the search space.
* `G` \- the groups for twist permutations, stored as pairs to be swapped. Each byte in the compressed string encodes for one pair. Each twist needs six swaps: three for the edge cycle, and three for the corner cycle. The compressed string contains only printable ascii (char 32 to 126).
* `M` \- a function that performs a move, given by G.
* `N` \- converts a permutation of four objects to a number, for encoding purposes.
* `H` \- calculates the heuristic value for the given cube state, used to lookup move depth from T.
* `P` \- perform a search at a single depth of a single phase of the algorithm.
* `s` \- the input cube's permutation state.
* `o` \- the input cube's orientation vector.

---

## Performance

Using Tomas Rokicki's data set, this script averaged 16.02 twists per solve (maximum 35), with an average time of 472ms (i5-3330 CPU @ 3.0 Ghz, PyPy 1.9.0). Minimum solve time was 233ms with a maximum of 2.97s, standard deviation 0.488. Using the scoring guidelines from the contest (white space is not counted, keywords and identifiers count as one byte for a length of 870), the overall score would have been 13,549.

For the last 46 cases (the random states), it averaged 30.83 twists per solve, with an average time of 721ms.

---

## Notes on Thistlethwaite's Algorithm

For the benefit of anyone who might want to attempt an implementation of Thistlethwaite's Algorithm, here is a brief explanation.

The algorithm works on a very simple solution space reduction principle. That is, reduce the cube to a state in which a subset of twists are not necessary to solve it, reduce it to a smaller solution space, and then solve the remainder using only the few twists remaining.

Thistlethwaite originally suggested `<L,R,F,B,U,D>``<L,R,F,B,U2,D2>``<L,R,F2,B2,U2,D2>``<L2,R2,F2,B2,U2,D2>`. However, given the input format, I think it is easier to first reduce to `<L,R,F2,B2,U,D>` (no quarter turn `F` or `B`), and then `<L2,R2,F2,B2,U,D>` before finally reaching the half turn state. Instead of explaining exactly why this is, I think it will be evident after defining the criteria for each state.

### `<L,R,F,B,U,D>``<L,R,F2,B2,U,D>`

In order to eliminate `F` and `B` quarter turns, only the edges must be oriented correctly. Gilles Roux has a very good explanation on his site of what 'correct' and 'incorrect' orientation is, so I'll leave the explaining to him. But basically, (and this is why this input format is so condusive to `F` and `B` elimination), an edge cubie is correctly oriented if it matches the following regex: `[^RL][^UD]`. A correct orientation is typically signified with a `0` and incorrect with `1`. Basically `U` and `D` stickers may not appear on the `R` or `L` faces, or on the edges of the any `U` or `D` edge cubies, or they cannot be moved into place without requiring an `F` or `B` quarter twist.

### `<L,R,F2,B2,U,D>``<L2,R2,F2,B2,U,D>`

Two criteria here. First, all corners must be oriented correctly, and second, each of the for middle layer cubies (`FR`, `FL`, `BR`, `BL`) must be somewhere in the middle layer. A corner orientation is very simply defined given the input format: the position of the first `U` or `D`. For example, `URB` has orientation `0` (correctly oriented), `LDF` has orientation `1`, and `LFU` has orientation `2`.

### `<L2,R2,F2,B2,U,D>``<L2,R2,F2,B2,U2,D2>`

The criteria here is as follows: each face may only contain stickers from its face, or from the face directly opposite it. For example, on the `U` face there may only be `U` and `D` stickers, on the `R` face there may only be `R` and `L` stickers, on the `F` face there may only be `F` and `B` stickers, etc. The easiest way to ensure this is to check if each edge piece is in its 'slice', and each corner piece in its 'orbit'. Additionally, one needs to pay attention to edge-corner parity. Although, if you check only for corner parity, edge parity is also guaranteed, and vice versa.

### How twists affect orientation

`U` and `D` twists affect neither the edge orientation, nor the corner orientation. The pieces may be swapped directly without updating the orientation vector.

`R` and `L` twists do not affect the edge orientation, but they do affect the corner orientation. Depending on how you define your cycle, the change in corner orientation will either be `+1, +2, +1, +2` or `+2, +1, +2, +1`, all modulo `3`. Note that `R2` and `L2` twists do not affect the corner orientation, as `+1+2` is zero modulo `3`, as is `+2+1`.

`F` and `B` affect both the edge orientations and corner orientations. Edge orientations become `+1, +1, +1, +1` (mod 2), and corner orientations are the same as for `R` and `L`. Note that `F2` and `B2` affect neither the edge orientations, nor corner orientations.

# Answer
> 12 votes
### Ruby, 742 characters

```
r=->y{y.split.map{|x|[*x.chars]}}
G=r['UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR']
o=r[gets]
x=[];[[%w{U UU UUU L LL LLL}+D=%w{D DD DDD},0],[%w{FDFFF RFDFFFRRR}+D,12],[%w{DDDRRRDRDFDDDFFF DLDDDLLLDDDFFFDF}+D,8],[%w{DFLDLLLDDDFFF RDUUUFDUUULDUUUBDUUU}+D,4],[%w{LDDDRRRDLLLDDDRD RRRDLDDDRDLLLDDD LFFFLLLFLFFFLLLF},16]].map{|q,y|x+=[*y..y+3]
3.times{q.map{|e|q|=[e.tr('LFRB','FRBL')]}}
w=->u{x.count{|t|u[t]!=G[t]}}
s=w[o]
(c=(0..rand(12)).map{q.sample}*''
z=o
c.chars{|m|z="=$'*:036\".?BOHKVGRWZ!$@*-0C69<4(E\\INQTMX!$'B-03<9*?6EHYLQPUZ!9'*-?360<$BSFKN[TWJ$'*!-0369<?BHKNEQTWZ!$'*6-039<?BEHKNTWZQ"[20*('FBLRUD'=~/#{m}/),20].bytes.map{|e|z[e/3-11].rotate e%3}}
t=w[z]
(c.chars{|e|$><<e<<'1 '};o=z;s=t)if s>t
)until s<1}

```

The above ruby code is not yet golfed fully. There are still possibilities to improve the code further (but its already enough as a starter).

It solves the cube layer by layer but uses no specific algorithm but instead performs random sequences of moves until the cube is solved.

Due to the probabilistic nature it may sometimes take longer than 5 seconds to solve the cube and in rare cases take more than 1000 moves.

Example output (for input 'RU LF UB DR DL BL UL FU BD RF BR FD LDF LBD FUL RFD UFR RDB UBL RBU') is 757 moves:

```
F1 R1 R1 F1 F1 F1 R1 R1 R1 L1 L1 L1 F1 D1 L1 L1 D1 D1 D1 D1 L1 B1 D1
B1 B1 B1 L1 L1 L1 F1 D1 F1 F1 F1 L1 D1 L1 L1 L1 B1 D1 B1 B1 B1 R1 D1
R1 R1 R1 L1 B1 D1 B1 B1 B1 L1 L1 L1 D1 D1 B1 D1 B1 B1 B1 B1 D1 B1 B1
B1 L1 D1 L1 L1 L1 D1 D1 D1 D1 D1 R1 D1 R1 R1 R1 R1 F1 D1 F1 F1 F1 R1
R1 R1 R1 D1 R1 R1 R1 F1 L1 D1 L1 L1 L1 F1 F1 F1 D1 D1 D1 D1 L1 D1 L1
L1 L1 F1 L1 D1 L1 L1 L1 F1 F1 F1 D1 D1 L1 D1 L1 L1 L1 D1 L1 D1 L1 L1
L1 L1 D1 L1 L1 L1 D1 R1 D1 D1 D1 R1 R1 R1 D1 D1 D1 B1 B1 B1 D1 B1 D1
L1 D1 D1 D1 L1 L1 L1 D1 D1 D1 F1 F1 F1 D1 F1 D1 D1 D1 B1 B1 B1 D1 B1
D1 R1 D1 D1 D1 R1 R1 R1 D1 D1 D1 B1 B1 B1 D1 B1 D1 R1 D1 D1 D1 R1 R1
R1 D1 B1 D1 D1 D1 B1 B1 B1 D1 D1 D1 L1 L1 L1 D1 L1 D1 B1 D1 D1 D1 B1
B1 B1 D1 D1 D1 L1 L1 L1 D1 L1 D1 D1 F1 D1 D1 D1 F1 F1 F1 D1 D1 D1 R1
R1 R1 D1 R1 D1 D1 D1 R1 R1 R1 D1 R1 D1 F1 D1 D1 D1 F1 F1 F1 D1 B1 D1
D1 D1 B1 B1 B1 D1 D1 D1 L1 L1 L1 D1 L1 D1 D1 D1 F1 F1 F1 D1 F1 D1 L1
D1 D1 D1 L1 L1 L1 D1 D1 D1 D1 D1 D1 F1 F1 F1 D1 F1 D1 L1 D1 D1 D1 L1
L1 L1 D1 D1 D1 F1 F1 F1 D1 F1 D1 L1 D1 D1 D1 L1 L1 L1 D1 F1 D1 D1 D1
F1 F1 F1 D1 D1 D1 R1 R1 R1 D1 R1 D1 D1 D1 F1 F1 F1 D1 F1 D1 L1 D1 D1
D1 L1 L1 L1 D1 D1 D1 F1 F1 F1 D1 F1 D1 L1 D1 D1 D1 L1 L1 L1 D1 D1 D1
D1 D1 F1 F1 F1 D1 F1 D1 L1 D1 D1 D1 L1 L1 L1 D1 D1 D1 D1 D1 D1 R1 F1
D1 F1 F1 F1 D1 D1 D1 R1 R1 R1 D1 F1 L1 D1 L1 L1 L1 D1 D1 D1 F1 F1 F1
D1 B1 R1 D1 R1 R1 R1 D1 D1 D1 B1 B1 B1 D1 B1 R1 D1 R1 R1 R1 D1 D1 D1
B1 B1 B1 D1 D1 D1 D1 B1 R1 D1 R1 R1 R1 D1 D1 D1 B1 B1 B1 D1 D1 D1 D1
D1 D1 B1 B1 B1 D1 F1 D1 D1 D1 B1 D1 F1 F1 F1 D1 D1 D1 R1 R1 R1 D1 L1
D1 D1 D1 R1 D1 L1 L1 L1 D1 D1 D1 B1 D1 D1 D1 F1 F1 F1 D1 B1 B1 B1 D1
D1 D1 F1 D1 B1 B1 B1 D1 F1 D1 D1 D1 B1 D1 F1 F1 F1 D1 D1 D1 L1 D1 D1
D1 R1 R1 R1 D1 L1 L1 L1 D1 D1 D1 R1 D1 F1 R1 R1 R1 F1 F1 F1 R1 F1 R1
R1 R1 F1 F1 F1 R1 R1 R1 R1 D1 L1 D1 D1 D1 R1 D1 L1 L1 L1 D1 D1 D1 B1
B1 B1 D1 F1 D1 D1 D1 B1 D1 F1 F1 F1 D1 D1 D1 F1 R1 R1 R1 F1 F1 F1 R1
F1 R1 R1 R1 F1 F1 F1 R1 F1 D1 D1 D1 B1 B1 B1 D1 F1 F1 F1 D1 D1 D1 B1
D1 F1 R1 R1 R1 F1 F1 F1 R1 F1 R1 R1 R1 F1 F1 F1 R1 F1 F1 F1 D1 B1 D1
D1 D1 F1 D1 B1 B1 B1 D1 D1 D1 R1 D1 D1 D1 L1 L1 L1 D1 R1 R1 R1 D1 D1
D1 L1 D1 R1 R1 R1 D1 L1 D1 D1 D1 R1 D1 L1 L1 L1 D1 D1 D1 R1 D1 D1 D1
L1 L1 L1 D1 R1 R1 R1 D1 D1 D1 L1 D1 F1 F1 F1 D1 B1 D1 D1 D1 F1 D1 B1
B1 B1 D1 D1 D1 L1 L1 L1 D1 R1 D1 D1 D1 L1 D1 R1 R1 R1 D1 D1 D1

```

It is possible to reduce the move-count considerably if same moves are grouped together. Therefore, one can replace the output like

```
(c.gsub(/(.)\1*/){j=$&.size%4;$><<$1<<j<<' 'if j>0};o=z;s=t)if s>t

```

---
Tags: code-golf, puzzle-solver, rubiks-cube, restricted-time
---


# Question
Title: shortest possible python pascal triangle code
the contest is already finished, so I don't think it's cheating to ask: I am trying to optimize this small contest: pascal triangle I started with 4.72 and worked myself up to 7.48. The best made a 9.05 but in perl, python2 best score is 8.25. Unfortunately they don't let you look at what others did. My current solution is the following:

```
l=[1]
print 1
while(len(l)<31):
 print' '.join(map(str,l+[1]))
 l=[1]+map(lambda x,y:x+y,l,l[1:]+[1])

```

Now I tried to get rid of the loop in using list comprehension, but I am too new to python to get this done. Can anyone give me a hint for nested list comprehension shortening this code further down?

Thank you for your audience.

# Answer
> 3 votes
This is a bit shorter, but still no good:

```
l=[1]
while(len(l)<32):
 print' '.join(map(str,l))
 l=[1]+map(int.__add__,l,l[1:]+[0])

```

And this one comes in at a score of 8.28 (credit to @primo):

```
l=[1];exec"print' '.join(map(str,l));l=map(sum,zip([0]+l,l+[0]));"*31

```

---
Tags: python
---


# Question
Title: Generate regular expressions for matching natural numbers between `m` and `n`
The type of regular expression is PCRE.

Write a program that output a valid PCRE such that it matches all natural numbers between `m` and `n` and does not match anything else. No leading zeros are allowed.

For example, let `m` and `n` be `123` and `4321`, then the program might output `1(2[3-9]|[3-9]\d)|[2-9]\d\d|[123]\d\d\d|4([012]\d\d|3([01]\d|2[01]))`.

This matches the exact string, so `^` and `$` anchors are implicit.

One should try to balance the two:

1. The regular expression should have a reasonable size.
2. The code should be short.

Let's optimize for

`code length in characters` \+ 2\*`regular expression length for input 123456 and 7654321`

Side Note: It be interesting if we can prove the shortest PCRE regular expression is of the size O(log n log log n) or something.

# Answer
> 7 votes
# **Perl, score 455**

**191 chars, 132 regex length**

```
sub b{my$a=shift;$_=(@_>0&&$a.b(@_).($a-->0&&'|')).($a>=0&&($a>1
?"[0-$a]":$a));/\|/?"($_)":$_}sub a{b(@a=split//,<>-1+$x++).(@a>
1&&"|.{1,$#a}")}print'(?!0|('.a.')$)(?=('.a.'$))^\d{1,'.@a.'}$'

```

Input: `123456, 7654321`

```
(?!0|((1(2(3(4(5[0-5]|[0-4])|[0-3])|[0-2])|1)|0)|.{1,5})$)(?=((7(6(5(4(3(21|1)|[0-2])|[0-3])|[0-4])|[0-5])|[0-6])|.{1,6}$))^\d{1,7}$

```

**Update:** I was able to further simplify this when I realized that most of the patterns ended with things like `\d{3}`. These were doing nothing more than enforcing a string length--and doing so very repetitively, since they occurred on every term. I eliminated this by using another lookahead to enforce the "less than" condition, only checking that either: 1) the first part of the number does not exceed the input or 2) the number is fewer digits than the input. Then the main regex just verifies that it is not too many digits.

I also incorporated Peter Taylor's idea of negative look-ahead for checking the "greater than" condition.

The key to simplifying this problem (at least for me) was to break the regex in two: a look-ahead makes sure the number is not less than the minimum, then the main part of the regex checks that it is not greater than the maximum. It is a little bit silly for small input, but it is not so bad for large input.

Note: the `0|` at the beginning is to exclude anything that starts with a zero from matching. This is required because of the recursive nature of the regex function: inner parts of the match can start with zero, but the entire number cannot. The regex function can't tell the difference, so I excluded any number starting with zero as a special case.

Input: `1, 4`

```
(?!0|(0)$)(?=([0-4]$))^\d{1,1}$

```

Unreasonably Long Regex Version, 29 chars:

```
print'^',join('|',<>..<>),'$'

```

# Answer
> 3 votes
## Javascript, score 118740839

```
function makere(m,n){r='(';for(i=m;i<n;)r+=i+++'|';return (r+i)+')';}

```

I suppose whether or not you like this depends on how you define 'a reasonable size.' :-)

# Answer
> 2 votes
**Haskell 2063+2\*151=2365**

It's guaranteed the generated regex has length O(log n log log n).

`matchIntRange 12345 7654321`

`1(2(3(4(5[6-9]|[6-9]\d)|[5-9]\d\d)|[4-9]\d{3})|[3-9]\d{4})|[2-9]\d{5}|[1-6]\d{6}|7([0-5]\d{5}|6([0-4]\d{4}|5([0-3]\d{3}|4([012]\d\d|3([01]\d|2[01])))))`

```
import Data.Digits

data RegEx = Range Int Int | MatchNone | All Int
            | Or RegEx RegEx | Concat [RegEx]

alphabet = "\\d"

instance Show RegEx where
  show (Range i j)
   | i == j    = show i
   | i+1 == j  = concat ["[",show i,show j,"]"]
   | i+2 == j  = concat ["[",show i,show (i+1), show (i+2),"]"]
   | otherwise = concat ["[",show i,"-",show j,"]"]
  show (Or a b)  = show a ++ "|" ++ show b
  show MatchNone = "^$"
  show (All n)
   | n < 3     = concat $ replicate n alphabet
   | otherwise = concat [alphabet,"{",show n,"}"]
  show e@(Concat xs)
   | atomic e  = concatMap show xs
   | otherwise = concatMap show' xs
   where show' (Or a b) = "("++show (Or a b)++")"
         show' x = show x
         atomic (Concat xs) = all atomic xs
         atomic (Or _ _)    = False
         atomic _           = True

-- Match integers in a certain range
matchIntRange :: Int->Int->RegEx
matchIntRange a b
 | 0 > min a b = error "Negative input"
 | a > b       = MatchNone
 | otherwise = build (d a) (d b)
 where build :: [Int]->[Int]->RegEx
       build [] [] = Concat []
       build (a@(x:xs)) (b@(y:ys))
         | sl && x == y       = Concat [Range x x, build xs ys]
         | sl && all9 && all0 = Concat [Range x y, All n]
         | sl && all0         = Or (Concat [Range x (y-1), All n]) upper
         | sl && all9         = Or lower (Concat [Range (x+1) y, All n])
         | sl && x+1 <= y-1   = Or (Or lower middle) upper
         | sl                 = Or lower upper
         | otherwise          = Or (build a (nines la)) (build (1:zeros la) b)
         where (la,lb) = (length a, length b)
               sl      = la == lb
               n       = length xs
               upper   = Concat [Range y y, build (zeros n) ys]
               lower   = Concat [Range x x, build xs (nines n)]
               middle  = Concat [Range (x+1) (y-1), All n]
               all9    = all (==9) ys
               all0    = all (==0) xs
       zeros n   = replicate n 0
       nines n   = replicate n 9
       d 0 = [0]
       d n = digits 10 n

```

The code below is a simple version that helps with understanding the algorithm, but it doesn't do any optimization to improve the regex size.

`matchIntRange 123 4321`

```
(((1((2((3|[4-8])|9)|[3-8]((0|[1-8])|9))|9((0|[1-8])|9))|[2-8]((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|9((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|((1((0((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9))|[1-8]((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|9((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|[2-3]((0((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9))|[1-8]((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|9((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9))))|4((0((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9))|[1-2]((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|3((0((0|[1-8])|9)|1((0|[1-8])|9))|2(0|1)))))

```

The regular expression has 680 characters. Here is the code

```
import Data.Digits

data RegEx = Range Int Int | MatchNone | Or RegEx RegEx | Concat [RegEx]

alphabet = "\\d"

instance Show RegEx where
  show (Range i j)
   | i == j    = show i
   | otherwise = concat ["[",show i,"-",show j,"]"]
  show (Or a b)  = concat ["(",show a,"|",show b,")"]
  show MatchNone = "^$"
  show (Concat xs) = concatMap show xs

matchIntRange :: Int->Int->RegEx
matchIntRange a b
 | 0 > min a b = error "Negative input"
 | a > b       = MatchNone
 | otherwise = build (d a) (d b)
 where build :: [Int]->[Int]->RegEx
       build [] [] = Concat []
       build (a@(x:xs)) (b@(y:ys))
         | sl && x == y     = Concat [Range x x, build xs ys]
         | sl && x+1 <= y-1 = Or (Or lower middle) upper
         | sl               = Or lower upper
         | otherwise        = Or (build a (nines la)) (build (1:zeros la) b)
         where (la,lb) = (length a, length b)
               sl      = la == lb
               n       = length xs
               upper   = Concat [Range y y, build (zeros n) ys]
               lower   = Concat [Range x x, build xs (nines n)]
               middle  = Concat [Range (x+1) (y-1), build (zeros n) (nines n)]
       zeros n = replicate n 0
       nines n = replicate n 9
       d 0 = [0]
       d n = digits 10 n

```

# Answer
> 2 votes
## GolfScript (126 + 2\*170 = 466)

```
~)]{`:&,:_,{:i'('\_(<:/i&=48-:D 2<{D^i!!D*|1,*}{'['\i>2D<'-'*D(']?'3$)<}if/D!!*{'\d{'/i>'1,'*_(i-'}|'D}*}%_')'*]}%'(?!'\~'$)'\

```

For the given values it gives

```
(?!(\d{1,5}|1([01]\d{4}|2([0-2]\d{3}|3([0-3]\d{2}|4([0-4]\d{1}|5([0-5]))))))$)([1-6]?\d{1,6}|7([0-5]\d{5}|6([0-4]\d{4}|5([0-3]\d{3}|4([0-2]\d{2}|3([01]\d{1}|2([01])))))))

```

Dissection to follow, but the basic idea is to define a block of code which maps a single natural number to a regex matching any smaller natural number, and then turn the inputs `lb` and `ub` into a negative lookahead for (natural number smaller than `lb`) combined with the regex for (natural number smaller than `ub+1`).

The logic is quite complicated, so even by GolfScript standards it's cryptic. Until I get round to writing a detailed dissection, here's a list of variables:

```
&  the whole number string
i  the current idx
D  the current digit
/  not-the-last-digit
_  total number of digits

```

---
Tags: code-golf, regular-expression
---


title: Crossword grid verification

text:
# Question
Title: Crossword grid verification
Validate a proposed crossword grid.

Entries should be full programs that simply test a proposed grid to determine if it meets a set of conditions for making crossword solvers happy.

## Input

The input will be the name of a file representing the crossword grid. The input filename may be passed as an argument, on the standard input, or by other conventional means other than hardcoding.

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

## Output

The program should produce no output on valid grids and exit with normal termination state. If the proposed grid fails, the program should produce a diagnostic error message and exit with a abnormal termination state (i.e. not 0 on unix) if this is supported by your execution environment. The error message should indicate both which condition for validity is violated and the location of the offending square; you are free to chose the means of conveying these facts.

## Conditions for validity

Valid grids will have no answers (across or down) that are only 1 character long (extra credit for making the minimum length a input parameter), and will exhibit the usual symmetry. The usual symmetry means the crossword remains the same after (three equivalent descriptions of the same operation):

* reflection through it's own center
* reflection both vertically and horizontally
* 180 degree rotation

## Test input and expected output

Passes:

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

```

Fails on short answer:

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

```

Fails on symmetry:

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

```

## Aside

This is the second 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. For instance a subsequent puzzle will call for printing a ASCII version of the crossword based on the input and output of this puzzle.

Previous challenges in this series:

# Answer
> 4 votes
# Ruby - ~~215~~ 207

```
t,*d=$<.map &:chop;n,d,e=t.size+1,(d*S=?#).gsub(/[^#]/,W=" "),->c,i{puts [c,i/n+1,i%n+1]*" ";exit 1}
0.upto(d.size-1){|i|d[i]==d[-i-1]||e[?R,i];d[i]==W&&(d[i-1]!=W&&d[i+1]!=W||d[i-n]!=W&&d[i+n]!=W)&&e[?L,i]}

```

Ungolfed:

```
h, *g = $<.map &:chop
w = h.size+1
g = (g*?#).gsub(/[^#]/," ")
error = ->c,i{ puts [c,i/w+1,i% w+1]*" "; exit 1 }
0.upto(size-1) { |i|
        error[?R, i] if g[i] != g[-i-1]
        error[?L,i] if g[i]==" " && (g[i-1]!=" " && g[i+1]!=" " || g[i-w]!=" " && g[i+w] != " ")
}

```

.

```
h, *g = $<.map &:chop

```

This basically removes the last char (line break) of each input line by calling the `chop` method on them, and returning an array of the results.

`h` takes the first element of this array and `*g` takes the rest. So we end up with the first line in `h` and the crossword grid lines in `g`.

```
g = (g*?#).gsub(/[^#]/," ")

```

`g*?#` joins (`*`) the array `g` with the `"#"` (`?#` is a character literal). This is the same as `g.*("#")`, or `g.join("#")`. Then every non `#` is replaced by a space.

For the symmetry check we just have to check if the char at every index is equals to the char at the opposite index in the string:

```
0.upto(g.size-1) { |i| if g[i] != g[g.size - i - 1]; error() }

```

In Ruby we can index strings from the end using negative indexes (starting from `-1` instead of `0`), so that `g[-i-1]` is the opposite of `g[i]` in the string. This saves a few chars:

```
0.upto(g.size-1) { |i| if g[i] != g[-i-1]; error() }

```

We can save a `;` by using a conditional statement:

```
0.upto(g.size-1) { |i| error() if g[i] != g[-i-1] }

```

In the golfed version we can save a few more chars:

```
0.upto(g.size-1){|i|g[i]==g[-i-1]||error()}

```

In a previous version I used recursion for iterating over the string:

```
(f=->i{g[i]&&f[i+1]&&g[i]!=g[-i-1]&&error()})[0]

```

An out of bound access to `g` returns nil, so once `g[i]` returns `nil`, this stops the iteration.

Output format:

```
{ L | R } line-number column-number

```

L for length errors, and R for rotation error (so `L 1 2` means length error at line 1, column 2)

# Answer
> 1 votes
## Reference implementation

**c99**

```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void readgrid(FILE *f, int m, int n, char grid[m][n]){
  int i = 0;
  int j = 0;
  int c = 0;
  while ( (c = fgetc(f)) != EOF) {
    if (c == '\n') {
      if (j != n) fprintf(stderr,"Short input line (%d)\n",i);
      i++;
      j=0;
    } else {
      grid[i][j++] = c;
    }
  }
}

int isSymmetric(int m, int n, char g[m][n]){
  for (int i=0; i<m; ++i)
    for (int j=0; j<n; ++j)
      if ( (g[i][j]=='#') != (g[m-i-1][n-j-1]=='#') )
    return j*m+i;
  return -1;
}

int isLongEnough(int m, int n, char g[m][n], int min){
  /* Check the rows */
  for (int i=0; i<m; ++i) {
    int lo=-(min+1); /* last open square */
    int lb=-1;       /* last blocked square */
    for (int j=0; j<n; ++j) {
      if ( g[i][j] == '#' ) {
    /* blocked square */
    if ( (lo == j-1) && (j-lb <= min+1) ) return lo*m+i;
    lb=j;
      } else {
    /* In-play square */
    lo=j;
      }
    }
  }

  /* Check the columns */
  for (int j=0; j<n; ++j) {
    int lo=-(min+1); /* last open square */
    int lb=-1;       /* last blocked square */
    for (int i=0; i<m; ++i) {
      if ( g[i][j] == '#' ) {
    /* blocked square */
    if ( (lo == i-1) && (i-lb <= min+1) ) return lo*m+i;
    lb=i;
      } else {
    /* In-play square */
    lo=i;
      }
    }
  }

  /* Passed */
  return -1;
}

int main(int argc, char** argv){
  const char *infname;
  FILE *inf=NULL;
  FILE *outf=stdout;
  int min=1;

  /* deal with the command line */
  switch (argc) {
  case 3: /* two or more arguments. Take the second to be the minium
         answer length */
    if ( (min=atoi(argv[2]))<1 ) {
      fprintf(stderr,"%s: Minimum length '%s' too short. Exiting.",
          argv[0],argv[2]);
      return 2;
    }
    /* FALLTHROUGH */
  case 2: /* exactly one argument */
    infname = argv[1];
    if (!(inf = fopen(infname,"r"))) {
      fprintf(stderr,"%s: Couldn't open file '%s'. Exiting.",
          argv[0],argv[1]);
      return 1;
    };
    break;
  default:
    printf("%s: Verify crossword grid.\n\t%s <grid file> [<minimum length>]\n",
       argv[0],argv[0]);
    return 0;
  }

  /* Read the grid size from the first line */
  int m=0,n=0,e=-1;
  char lbuf[81];
  fgets(lbuf,81,inf);
  sscanf(lbuf,"%d %d",&m,&n);

  /* Intialize the grid */
  char grid[m][n];
  for(int i=0; i<m; ++i) {
    for(int j=0; j<n; ++j) {
      grid[i][j]='#';
    }
  }

  readgrid(inf,m,n,grid);

  if ((e=isSymmetric(m,n,grid))>=0) {
    fprintf(stderr,"Symmetry violation at %d,%d.\n",e/m+1,e%m+1);
    return 4;
  } else if ((e=isLongEnough(m,n,grid,min))>=0) {
    fprintf(stderr,"Short answer at %d,%d.\n",e/m+1,e%m+1);
    return 8;
  }
  return 0;
}

```

# Answer
> 1 votes
## C, 278 chars

```
char*f,g[999],*r=g;i,j,h,w;main(e){
for(fscanf(f=fopen(gets(g),"r"),"%*d%d%*[\n]",&w);fgets(g+h*w,99,f);++h);
for(;j++<h;)for(i=0;i++<w;++r)if(e=*r==35^g[g+w*h-r-1]==35?83:
*r==35||i>1&r[-1]!=35|i<w&r[1]!=35&&j>1&r[-w]!=35|j<h&r[w]!=35?0:76)
exit(printf("%d%c%d\n",j,e,i));exit(0);}

```

As you might expect, the error messages have themselves been golfed. They take the following form:

`11L8` \- indicates a length error at row 11 column 8

`4S10` \- indicates a symmetry error at row 4 column 10

# Answer
> 1 votes
## APL (115)

```
{∨/,k←⍵≠⌽⊖⍵:'⍉',(,k×⍳⍴k)~⊂2/0⋄×⍴d←(,⊃,/(g(⍉g←⍳⍴⍵))×{k↑1⌽1⊖0 1 0⍷¯1⌽¯1⊖⍵↑⍨2+k←⍴⍵}¨⍵(⍉⍵))~⊂2/0:'∘',d}d↑↑{'#'≠⍞}¨⍳⊃d←⎕

```

If the grid is not symmetrical, it outputs  followed by the coordinates, i.e. for the example it gives

```
⍉ 2 5  4 1
```
If the grid has short answers, it outputs  followed by the coordinates, i.e. for the example it gives
```
∘ 1 2  5 2
```

Explanation:

* `d↑↑{'#'≠⍞}¨⍳⊃d←⎕`: read the first line as a list of numbers and store in `d`, then read as many lines as the first number, and reshape as a matrix of size `d`. 'Closed' squares are stored as 0 and 'open' squares as 1.
* `∨/,k←⍵≠⌽⊖⍵`: store in `k` the places where the grid is asymmetrical. If there is such a place...
* `'⍉',(,k×⍳⍴k)~⊂2/0`: output a ⍉ followed by the offending coordinates
* : otherwise...
* `~⊂2/0`: remove the zero coordinates from the following list:
* `¨⍵(⍉⍵)`: for both the grid and its transpose...
* `¯1⌽¯1⊖⍵↑⍨2+k←⍴⍵`: surround the grid with zeros (i.e. closed squares)
* `0 1 0⍷`: see where it contains an 'open' square enclosed by two 'closed' squares (= too short)
* `k↑1⌽1⊖`: remove the ring of extra zeros again
* `,⊃,/(g(⍉g←⍳⍴⍵))×`: multiply by coordinates and transposed coordinates, and join together, to form a list of offending coordinates (and a lot of zeros which we remove).
* `×⍴d←`: store the offending coordinates in `d`, and if there are any...
* `:'∘',d`: output a ∘ followed by the coordinates.

---
Tags: code-golf, crossword
---


title: codegolf.com: Saving Time

text:
# Question
Title: codegolf.com: Saving Time
From codegolf.com (not loading as of Sept 15, 2011) was one that was driving me crazy. Print to STDOUT a clock of an exacting form, reading time from STDIN and marking an `h` at the hour and `m` at minute (rounded down to a multiple of 5) and an `x` if they overlap, unused ticks are marked with an `o`, so that

```
echo "23:13" | perl script.pl

```

yields

```
        o
    h       o

 o             m

o               o

 o             o

    o       o
        o

```

Mine is:

```
$/=':';($h,$m)=<>;printf'%9s
%5s%8s

%2s%14s

%s%16s

%2s%14s

%5s%8s
%9s',map{qw'o h m x'[2*($_==int$m/5)^$_==$h%12]}map{$_,11-$_}0..5

```

for 136 characters, using Perl. I wish I could get on the site, but I seem to recall that the leaders were under 100, also using Perl. Can someone else beat it?

# Answer
## Golfscript, 75 bytes

Inspired by the article linked in the comments.

```
':'/{~}/5/:m;12%:h;"XXXXXXXXXXXX"{..318\%9/' '*@12%.h=2*\m=+'omhx'=@85/n*}%

```

The `XXXXXXXXXXXX` part represents 12 bytes of data, some of them unprintable, and should be replaced with the byte sequence `120 47 253 22 194 9 183 44 196 55 125 246`.

For convenience, here is a base64 encoded version:

```
JzonL3t+fS81LzptOzEyJTpoOyJ4L/0Wwgm3LMQ3ffYiey4uMzE4XCU5LycgJypAMTIlLmg9Mipc
bT0rJ29taHgnPUA4NS9uKn0l

```

**Example run:**

```
$ echo -n "JzonL3t+fS81LzptOzEyJTpoOyJ4L/0Wwgm3LMQ3ffYiey4uMzE4XCU5LycgJypAMTIlLmg9MipcbT0rJ29taHgnPUA4NS9uKn0l" | base64 -d > saving-time.gs
$ ls -l saving-time.gs
-rw-r--r-- 1 ahammar ahammar 75 2012-01-29 17:31 saving-time.gs
$ ruby golfscript.rb saving-time.gs <<< "15:37"
        o
    o       o

 o             o

o               h

 o             o

    m       o
        o

```
> 3 votes

# Answer
## C, 259 244 163 chars

Replaced command line argument with stdin (as required, also ends up shorter).
Removed support for minutes above 59 - a waste of 3 characters.
The code is shown with line breaks and indentation, but characters were counted without them.

```
main(i,h,m,x){
    scanf("%d:%d",&h,&m);
    for(i=0;i<12;
        printf("%*c","IEHBNAPBNEHI"[i++]-64,"ohmx"[(x==h%12)+2*(x==m/5)]))
        x=i%2?puts("\n"+(i%10==1)),11-i/2:i/2;
    puts("");
}

```

Older attempt (using ANSI escape codes), 244 chars:

```
f(x,y)char*y;{printf("\033[%d%c",x>0?x:-x,y[x<0]);}
main(i,h,m,x){
    char*v="HIJJJJIGFFFFPKJHFDCCDFHJ";
    f(i=f(scanf("%d:%d",&h,&m),"J")*0,v);
    for(;i<12;i++)
        (x=v[i+12]-72)&&f(x,"CD"),
        f(v[i]-72,"BA"),
        putchar("omhx"[2*(i==h%12)+(i==m%60/5)]);
    f(i,"B");
}

```
> 2 votes

# Answer
## Python, 175 chars

```
h,m=map(int,raw_input().split(':'))
S=([' ']*17+['\n'])*11
for i in range(12):p=1j**(i/3.);S[98+int(8.5*p.imag)-18*int(5*p.real)]='ohmx'[2*(i==m/5)+(i==h%12)]
print''.join(S),

```

Doesn't beat your Perl code, but maybe a more concise language with built in complex numbers (or trig functions) could use this idea to do better.
> 1 votes

# Answer
# Python, 226 chars

```
h,p,s=raw_input().split(':'),['o']*12,[0,11,1,10,2,9,3,8,4,7,5,6]
a,b=int(h[0])%12,int(h[1])/5
p[a],p[b]='h','m' if a!=b else 'x'
print '%9s\n%5s%8s\n\n %s%14s\n\n%s%16s\n\n %s%14s\n\n%5s%8s\n%9s'%tuple([p[i] for i in s])

```

Usage: run 'python script.py' then type the required time. (Ex: 09:45)

Output:

```
        o
    o       o

 o             o

x               o

 o             o

    o       o
        o

```
> 1 votes

# Answer
My perl solution:

```
use POSIX;$/=':';@ss=(8,4,1,0,1,4,8);@sn=(0,7,13,15,13,7,0);$h=<stdin>;
$m=<stdin>;if($h>12){$h=$h-12;}$m=floor($m/5);
for($c=0;$c<7;$c++){for($s=0;$s<$ss[$c];$s++){printf(" ");}
$ac='o';if($h>5&&$h-6==6-$c){$ac='h';}if((($m>5)&&$m-6==6-$c)||($m==$c)&&($c==0)){
if($h>5&&$h-6==6-$c){$ac='x';}else{$ac='m';}}
print($ac);for($s=0;$s<$sn[$c];$s++){printf(" ");}$bc='o';if($h<6&&$h==$c){$bc='h';}
if($m<6&&$m==$c){if($h<6&&$h==$c){$bc='x';}else{$bc='m';}}
if($sn[$c]){print($bc);}printf("\n");if($c&&($c!=5)){printf("\n");}}

```

## 527 bytes

My C solution:

```
main(){int x[]={8,4,1,0,1,4,8},y[]={0,7,13,15,13,7,0}
,h,m,z,c,s;scanf("%d:%d",&h,&m);h>12?h-=12:h;m/=5;
for(c=0;c<7;c++){for(s=0;s<x[c];s++){printf(" ");}z='o';
if(h>5&h-6==6-c){z='h';}if((m>5&m-6==6-c)|(m==c)&!c){
z='m';if(h>5&h-6==6-c){z='x';}}printf("%c",z);
for(s=0;s<y[c];s++){printf(" ");}z='o';if(h<6&h==c){
z='h';}if(m<6&m==c){z='m';if(h<6&h==c){z='x';}}
if(y[c]){printf("%c",z);}printf("\n");if(c&&(c!=5)){printf("\n");}}}

```

440 bytes
> 0 votes

# Answer
## Scala 327 chars

```
object C extends App{
val R=List(2,4,6,8,10)
val r=1::R:::11::R.reverse
val C=List(3,6,12,18,21)
val c=1::C:::21::C.reverse
def p(n:Int,i:Char){
val z=r(n)
val s=c((n+3)%12)
printf("[%d;%dH"+i,z,s)}
val t=readLine.split(":")
val h=t(0).toInt%12
val m=t(1).toInt/5
(0 to 11).map(x=>p(x,'o'))
p(h,'h')
p(m,'m')
if(h==m)p(h,'x')}

```

### in use with a proper circle shape, not your lemon-XXXX:

```
clear  && echo 5:43 | scala C
           o
     o           o

  o                 o

o                    o

  m                 o

     o           h
           o

```

### ungolfed:

```
object Clock {
 val R = List (2,4,6,8,10)
 val r = 1 :: R ::: 11 :: R.reverse
 val C = List (3,6,12,18,21)
 val c = 1 :: C ::: 22 :: C.reverse

 def pos (n: Int, i: Char)={
   val z = r (n)
   val s = c ((n+3) % 12)
   printf ("[%d;%dH" + i, z, s)
 }

 def main (args: Array [String]) {
   val t = args (0).split (":")
   val h = t (0).toInt % 12
   val m = t (1).toInt /  5
   (0 to 11).map (x=> pos (x, 'o'))
   pos (h, 'h')
   pos (m, 'm')
   if (h == m) pos (h, 'x')
  }
}

```

Uses Ansi-Code for output at pos(y,x). Since we only need 5 Minutes accuracy, precalculated values for x and y seem to be shorter than handling sin and cos functions with their import.
> 0 votes

# Answer
# Python, 176 characters

```
o=map(ord,' .@Set~lWC2&!/0ABTUfgu')
h,m=map(int,raw_input().split(':'))
print''.join([' ',['\n','ohmx'[2*(i==o[m/5])+(i==o[h%12])]][i in o[:12]]][i in o]for i in range(24,127))

```
> 0 votes

# Answer
**Perl 131 characters**

```
<>=~/:/;$h=$`%12;$m=$'/5;printf'%9s
%12$5s%8s

%11$2s%14s

%10$s%16s

%9$2s%14s

%8$5s%8s
%9s',map$_^$h?$_^$m?o:'m':$h^$m?h:x,0..11

```
> 0 votes

---
Tags: code-golf
---