title: Compose a Vim quine!

text:
# Question
Title: Compose a Vim quine!
Goal:

Create and save file in Vim containing at least 25 ASCII characters. The *exact keystrokes* used during the creation and saving of this file must also produce identical contents in Windows Notepad (without having to save in Notepad).

Rules:

* For the purposes of this challenge, Vim begins open in command mode.
* The mouse is **not** allowed.
* `Shift` ***is*** allowed. `Ctrl`, `alt`, or any other modifier keys are ***not*** allowed.
* Your solution must work with the **default** "terminal" (non-GUI) Vim shipped with either Ubuntu 11.04 or OS X 10.6.7 (one of the two). Assume this Vim's `.vimrc` contains only `set nocompatible` (with no line break after it), which is itself located at `~/.vimrc`. Pretend your operating system was *just* installed before opening Vim.
* You must not open any *pre-existing* files except for your `.vimrc`. Any files you create while solving this puzzle may be saved and re-opened as many times as necessary.
* Vim cannot be closed!

*Disclosure, and a possible reason to close:* I do not have a solution.

# Answer
> 11 votes
The edited sequence (the first version was mangled).

`2` `A` `2` `A` `Esc` `2` `A` `2` `A` `Esc` `2` `A` `2` `A` `Esc`

`2` `A` `2` `A` `Esc` `2` `A` `2` `A` `Esc` `2` `A` `2` `A` `Esc`

`2` `A` `2` `A` `Esc` `2` `A` `2` `A` `Esc` `A` `:` `w` `q` `Enter`

`Esc` `Backspace` `Backspace` `Backspace` `Backspace` `Backspace` `:` `w` `q` `Enter`

Should do the trick, if I'm counting my keystrokes correctly. No wait, is the escape key allowed?

# Answer
> 4 votes
`I` `Backspace` `H` `E` `L` `L``O` `,` `Space` `W` `O` `R` `L``D`
`Esc` `Shift`+`;` `W` `Enter` `I` `Backspace` `Backspace` `Backspace` `Backspace`.

Produces "hello, world" in both.

# Answer
> 1 votes
34 keystrokes. Produces twenty-two A's followed by :x and a new line.

`i` `Backspace`

`a` `a` `a` `a` `a` `a` `a` `a` `a` `a` `a`

`a` `a` `a` `a` `a` `a` `a` `a` `a` `a` `a`

`:` `x` `Enter` `Esc` `Backspace` `Backspace` `Backspace` `:` `x` `Enter`

---
Tags: quine, vim
---


title: Lottery Ball Problem

text:
# Question
Title: Lottery Ball Problem
A woman works at a lottery ball factory. She's instructed to open up a lottery ball creation kit composed of 1 red rubber ball and *n* strips of digits from 0 through 9.

She's instructed to do the following:

1. Starting with 1, write the current number on the ball using the digits available on the *n* strips.
2. Put unused digits into a bowl where they can be used later for when she runs out of available digits in step 1.
3. Open up another lottery ball creation kit and continue to step 1 for the next number.

The question is, at what number will she arrive at before she runs out of digits to write the number? **Edited**: Given *n* where *n* is the number of digit strips from 0 through 9 provided in each lottery ball creation kit, write a program that can solve this (not trivially) in the least amount of time.

**Edit**: Additional notes - 6 and 9 are different numbers. Assume there are no limits to the number of digits that can be pasted on the ball.

**Hint**: If she counted in base 2 rather than base 10, how would that change the result and would that be easier to calculate? What could you derive from solutions in base 2?

# Answer
> 2 votes
**edit 2: fixed**

General solution for n \> 1:

```
-- lottery2.hs

import System
import Control.Monad
import Data.Maybe

main = mapM_ print . map (solve . read) =<< getArgs

rdigits 0 = []
rdigits n = (n `mod` 10) : rdigits (n `div` 10)

digits = reverse . rdigits

undigits = foldl ((+) . (10*)) 0

c1 = c . digits

c [] = 0
c [0] = 0
c [_] = 1
c (0:xs) = c xs
c (1:xs) = d xs + c xs + undigits xs
c (x:xs) = c xs + x * (d xs - 1) + 10 ^ length xs

d xs = ds !! length xs

ds = map d' [0..]
  where d' n = c1 (10 ^ n - 1) + 1

maxVal n =
  fst . head . filter (uncurry $ (<) . (*n))
  . map (liftM2 (,) undigits c . (1:) . flip replicate 9) $ [0..]

search f p q a b = s f (uncurry p) q (a, f a) (b, f b)
  where
    s f p q a b
      | not (p a) = Nothing
      | fst a + 1 == fst b = guard (not $ p b) >> return (fst a)
      | a >= b = Nothing
      | q a b = maybe (s f p q k b) Just (s f p q a k)
      | otherwise = Nothing
        where k = ((fst a + fst b) `div` 2, f (fst k))

solve n = fromJust $ search c1 ((>=) . (*n)) q 1 m
  where
    m = maxVal n
    q (a, fa) (b, fb) = (a * n) - fa <= fb - fa

```

There seems to be a pattern here:

```
$ ghc -O --make lottery2.hs
Linking lottery2 ...
$ time ./lottery 1 2 3 4 5 6
199990
1999919999999980
19999199999999919999999970
199991999999999199999999919999999960
1999919999999991999999999199999999919999999950
19999199999999919999999991999999999199999999919999999940

real    0m3.580s
user    0m3.508s
sys     0m0.020s
$ time ./lottery 7 8 9 10 11 12
199991999999999199999999919999999991999999999199999999919999999930
1999919999999991999999999199999999919999999991999999999199999999919999999920
19999199999999919999999991999999999199999999919999999991999999999199999999919999999918
199991999999999199999999919999999991999999999199999999919999999991999999999199999999919999999917
1999919999999991999999999199999999919999999991999999999199999999919999999991999999999199999999919999999916
19999199999999919999999991999999999199999999919999999991999999999199999999919999999991999999999199999999919999999915

real    1m10.855s
user    1m3.868s
sys     0m0.324s

```

# Answer
> 2 votes
# awk (109)

brute force solution

```
yes|awk -F "" '{c("0123456789",1);c(NR,-1)}function c(C,m,i){for($0=C;NF-i++;)if((t[$i]+=m)<0){print NR-1;exit}}'

```

The `awk` does not count in the character count if I understand the rules correctly.
The trick with `yes|` \+ `NR` is a shorter way to define a loop counter than a `BEGIN` \+ `while` or `for` clause.
Replace `,1` with `,`\[value of n\]. With 1 it returns `199990`, with 2 it is still trying to find the answer.

Could write it as:

```
yes|awk -F "" -v n=1 '{c("0123456789",n);c(NR,-1)}function c(C,m,i){for($0=C;NF-i++;)if((t[$i]+=m)<0){print NR-1;exit}}'

```

And replace `n=1` with `n=`\[whatever value\] (now a parameter of the program, for an extra 6 characters plus the number of characters for the value of n. But like I said since it is still trying to compute for n=2, there may be no need to parameterise this version.

I'm sure there must be a much more clever algorithm than plain increment and count. Like a bit of algebra. No time for this... I'll leave that to someone else.

# Answer
> 0 votes
# C

Here's a non-golf brute force solution in C which seems to give the right answer for 1 strip, but I haven't had the patience to let it run long enough to see if it gets to a solution for 2 strips (in fact if I extrapolate the progress output I'm not sure it will finish within my life-time !).

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

int main(int argc, char *argv[])
{
    const int MAX_DIGITS = 24;
    char buff[MAX_DIGITS + 1];
    int num_strips = 1;
    int64_t digits[10] = { 0 };
    int64_t i;

    if (argc > 1)
    {
        num_strips = atoi(argv[1]);
        if (num_strips < 1 || num_strips > 2)
        {
            fprintf(stderr, "num_strips must be 1 or 2\n");
            exit(1);
        }
    }

    memset(buff, ' ', MAX_DIGITS - 1);
    buff[MAX_DIGITS - 1] = '1';
    buff[MAX_DIGITS] = '\0';

    for (i = 1 ; ; ++i)
    {
        int d;

        // add 2 to each remaining digit count

        for (d = 0; d < 10; ++d)
        {
            digits[d] += num_strips;
        }

        // update counts of remaining digits based on current i

        for (d = MAX_DIGITS - 1; d >= 0; --d)
        {
            char ch = buff[d];

            if (ch != ' ')
            {
                int digit = ch - '0';
                digits[digit]--;
            }
            else
            {
                break;
            }
        }

        // check to see whether we found solution

        for (d = 0; d < 10; ++d)
        {
            if (digits[d] < 0)
            {
                printf("Found solution at i = %s, digits = { %24lld %24lld %24lld ... %24lld }\n", buff, digits[0], digits[1], digits[2], digits[9]);
                goto done;
            }
        }

        // log progress when i == 2^n

        if ((i & (i - 1)) == 0)
        {
            printf("i = %s, digits = { %24lld %24lld %24lld ... %24lld }\n", buff, digits[0], digits[1], digits[2], digits[9]);
        }

        // increment "i"

        for (d = MAX_DIGITS - 1; d >= 0; --d)
        {
            char ch = buff[d];

            switch (ch)
            {
                case ' ':
                    buff[d] = '1';
                    break;
                case '9':
                    buff[d] = '0';
                    continue;
                    break;
                default:
                    buff[d] = ch + 1;
                    break;
            }
            break;
        }
    }
done:
    return 0;
}

```

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


title: Implement PCRE in your language.

text:
# Question
Title: Implement PCRE in your language.
> **Note:** After trying this myself, I soon realized what a mistake this was. Therfore, I am modifying the rules a bit.

The minimum required functionality:

* Character classes (`.`, `\w`, `\W`, etc.)
* Multipliers (`+`, `*`, and `?`)
* Simple capture groups

---

Your challenge is to implement PCRE in the language of your choice subject to the following conditions:

* You **may not** use your language's native RegEx facilities in *any way*. You may not use a 3rd party RegEx library either.
* Your entry should implement as much of the PCRE spec. as possible.
* Your program should accept as input, 2 lines:

> + the regular expression
>     + the string input to match against
* Your program should indicate in its output:

> + Whether the RegEx matched anywhere in the input string
>     + The results of any capturing groups
* The winner shall be the entry that implements as much of the spec. as possible. In case of a tie, the winner shall be the most creative entry, as judged by me.

---

**Edit:** to clarify a few things, here are some examples of input and expected output:

---

* **Input:**

```
^\s*(\w+)$
         hello

```
* **Output:**

```
Matches: yes
Group 1: 'hello'

```

---

* **Input:**

```
(\w+)@(\w+)(?:\.com|\.net)
sam@test.net

```
* **Output:**

```
Matches: yes
Group 1: 'sam'
Group 2: 'test'

```

---

# Answer
## Python

Since implementing full PCRE is too much I implemented only an essential subset of it.

Supports `|.\.\w\W\s+*()`. Input regexp must be correct.

## Examples:

```
$ python regexp.py
^\s*(\w+)$
   hello
Matches:     hello
Group 1 hello

$ python regexp.py
(a*)+
infinite loop

$ python regexp.py
(\w+)@(\w+)(\.com|\.net)
sam@test.net
Matches:  sam@test.net
Group 1 sam
Group 2 test
Group 3 .net

```

## How it works:

For detailed theory read this Introduction to Automata Theory, Languages, and Computation.

The idea is to convert the original regular expression into a nondeterminist finite automata (NFA). Actually, PCRE regular expressions are at least context free grammars for which we need push-down automata, but we'll limit ourselves to a subset of PCRE.

Finite automatas are directed graphs in which nodes are states, edges are transitions and each transition has a matching input. Initially you start from a start node, predefined. Whenever you receive an input that matches one of the transition you take that transition to a new state. If you reached a terminal node it is called that automata accepted input. In our case input is a matching function that returns true.

They are called nondeterminist automata because sometimes there are more matching transitions that you can take from the same state. In my implementation all transition to the same state must match the same thing, so I stored the matching function together with the destination state (`states[dest][0]`).

We transform our regexp to a finite automata using building blocks. A building block has a start node (`first`) and an end node (`last`) and matches something from the text (possible empty string).

The simplest examples include

* matching nothing: `True` (`first == last`)
* matching a character: `c == txt[pos]` (`first == last`)
* matching end of string: pos == len(txt)`(`first == last\`)

You will also need the new position in text where to match next token.

More complicated examples are (capital letters stand for blocks).

* matching B+:

+ create nodes: u, v (matching nothing)
    + create transitions: u -\> B.first, B.last -\> v, v -\> u
    + when you get to node v you already matched B. Then you have two options: go further, or try to match B again.
* matching A|B|C:

+ create nodes: u, v (matching nothing)
    + create transitions: u -\> A.first, u -\> C.first, u -\> C.first,
    + create transitions: A-\>last -\> v, B-\>last -\> v, C-\>last -\> v,
    + from u you can go to any block

All regexp operators can be transformed like this. Just give a try for `*`.

The last part is to parse the regexp which requires a very simple grammar:

```
 or: seq ('|' seq)*
 seq: empty
 seq: atom seq
 seq: paran seq
 paran: '(' or ')'

```

Hopefully implementing a simple grammar (I think is LL(1), but correct me if I'm wrong) is much easier than building an NFA.

Once you have the NFA you need to backtrack until you reach terminal node.

## Source code (or here):

```
from functools import *

WORDCHAR = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ01234567890_'

def match_nothing(txt, pos):
  return True, pos

def match_character(c, txt, pos):
  return pos < len(txt) and txt[pos] == c, pos + 1

def match_space(txt, pos):
  return pos < len(txt) and txt[pos].isspace(), pos + 1

def match_word(txt, pos):
  return pos < len(txt) and txt[pos] in WORDCHAR, pos + 1

def match_nonword(txt, pos):
  return pos < len(txt) and txt[pos] not in WORDCHAR, pos + 1

def match_dot(txt, pos):
  return pos < len(txt), pos + 1

def match_start(txt, pos):
  return pos == 0, pos

def match_end(txt, pos):
  return pos == len(txt), pos

def create_state(states, match=None, last=None, next=None, name=None):
  if next is None: next = []
  if match is None: match = match_nothing

  state = len(states)
  states[state] = (match, next, name)
  if last is not None:
    states[last][1].append(state)

  return state

def compile_or(states, last, regexp, pos):
  mfirst = create_state(states, last=last, name='or_first')
  mlast = create_state(states, name='or_last')

  while True:
    pos, first, last = compile_seq(states, mfirst, regexp, pos)
    states[last][1].append(mlast)
    if pos != len(regexp) and regexp[pos] == '|':
      pos += 1
    else:
      assert pos == len(regexp) or regexp[pos] == ')'
      break

  return pos, mfirst, mlast

def compile_paren(states, last, regexp, pos):
  states.setdefault(-2, [])   # stores indexes
  states.setdefault(-1, [])   # stores text

  group = len(states[-1])
  states[-2].append(None)
  states[-1].append(None)

  def match_pfirst(txt, pos):
    states[-2][group] = pos
    return True, pos

  def match_plast(txt, pos):
    old = states[-2][group]
    states[-1][group] = txt[old:pos]
    return True, pos

  mfirst = create_state(states, match=match_pfirst, last=last, name='paren_first')
  mlast = create_state(states, match=match_plast, name='paren_last')

  pos, first, last = compile_or(states, mfirst, regexp, pos)
  assert regexp[pos] == ')'

  states[last][1].append(mlast)
  return pos + 1, mfirst, mlast

def compile_seq(states, last, regexp, pos):
  first = create_state(states, last=last, name='seq')
  last = first

  while pos < len(regexp):
    p = regexp[pos]
    if p == '\\':
      pos += 1
      p += regexp[pos]

    if p in '|)':
      break

    elif p == '(':
      pos, first, last = compile_paren(states, last, regexp, pos + 1)

    elif p in '+*':
      # first -> u ->...-> last -> v -> t
      # v -> first (matches at least once)
      # first -> t (skip on *)
      # u becomes new first
      # first is inserted before u

      u = create_state(states)
      v = create_state(states, next=[first])
      t = create_state(states, last=v)

      states[last][1].append(v)
      states[u] = states[first]
      states[first] = (match_nothing, [[u], [u, t]][p == '*'])

      last = t
      pos += 1

    else:  # simple states
      if p == '^':
    state = create_state(states, match=match_start, last=last, name='begin')
      elif p == '$':
    state = create_state(states, match=match_end, last=last, name='end')
      elif p == '.':
    state = create_state(states, match=match_dot, last=last, name='dot')
      elif p == '\\.':
    state = create_state(states, match=partial(match_character, '.'), last=last, name='dot')
      elif p == '\\s':
    state = create_state(states, match=match_space, last=last, name='space')
      elif p == '\\w':
    state = create_state(states, match=match_word, last=last, name='word')
      elif p == '\\W':
    state = create_state(states, match=match_nonword, last=last, name='nonword')
      elif p.isalnum() or p in '_@':
    state = create_state(states, match=partial(match_character, p), last=last, name='char_' + p)
      else:
    assert False

      first, last = state, state
      pos += 1

  return pos, first, last

def compile(regexp):
  states = {}
  pos, first, last = compile_or(states, create_state(states, name='root'), regexp, 0)
  assert pos == len(regexp)
  return states, last

def backtrack(states, last, string, start=None):
  if start is None:
    for i in range(len(string)):
      if backtrack(states, last, string, i):
    return True
    return False

  stack = [[0, 0, start]]   # state, pos in next, pos in text
  while stack:
    state = stack[-1][0]
    pos = stack[-1][2]
    #print 'in state', state, states[state]

    if state == last:
      print 'Matches: ', string[start:pos]
      for i in xrange(len(states[-1])):
    print 'Group', i + 1, states[-1][i]
      return True

    while stack[-1][1] < len(states[state][1]):
      nstate = states[state][1][stack[-1][1]]
      stack[-1][1] += 1

      ok, npos = states[nstate][0](string, pos)
      if ok:
    stack.append([nstate, 0, npos])
    break
      else:
    pass
    #print 'not matched', states[nstate][2]
    else:
      stack.pop()

  return False

# regexp = '(\\w+)@(\\w+)(\\.com|\\.net)'
# string = 'sam@test.net'
regexp = raw_input()
string = raw_input()

states, last = compile(regexp)
backtrack(states, last, string)

```
> 10 votes

---
Tags: code-challenge, regular-expression
---


title: Is this figure connected?

text:
# Question
Title: Is this figure connected?
You are given a list of `(x,y)` grid coordinates. Your function should decide whether the figure obtained by coloring in the squares of the grid with the given coordinates is connected or not.

Squares adjacent diagonally are not considered connected.

Example input:

```
(0,0),(1,0),(2,0),(3,0),(3,1),(3,2),(2,2),
(1,2),(0,2),(0,3),(0,4),(1,4),(2,4),(3,4)

```

which looks like:

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

```

Output:

```
YES

```

Example input:

```
(0,0),(1,0),(2,0),(0,1),(0,2),(2,2),(3,2),(4,2),(0,3),
(4,3),(0,4),(1,4),(2,4),(4,4),(4,5),(2,6),(3,6),(4,6)

```

which looks like:

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

```

Output:

```
NO

```

Your function must take as input a list of pairs of integers (e.g. in C++, maybe vector\<pair\<int,int\>\>) and return a boolean. You may not assume any particular ordering of the input points. The coordinates will be between 0 and 99 inclusive.

Smallest code wins.

# Answer
> 3 votes
# Ruby - 82

```
c=->s{(a=->x,y{a[x,y-1]&a[x+1,y]&a[x,y+1]&a[x-1,y]if s.delete [x,y];s})[*s[0]][0]}

```

Ungolfed:

```
def c(s)
        a=->x,y{
            if s.delete([x,y])
                a[x,y-1]
                a[x+1,y]
                a[x,y+1]
                a[x-1,y]
            end
        }
        x,y=s.first
        a[x,y]
        s.size != 0
end

```

Usage:

```
print s([ [0,0],[2,0],[3,0],[3,1],[3,2],[2,2],[1,2],
    [0,2],[0,3],[0,4],[1,4],[2,4],[3,4]
]) ? "NO" : "YES"

```

# Answer
> 5 votes
c99 -- 620ish neccessary characters

```
#include <stdlib.h>
#define S return
typedef struct n N;struct n{int x,y;N*n;};
N*I(int x,int y,N*l){if(!l)goto z;N*m=l;do{if((m->x==x)&&(m->y==y))
S m;m=m->n;}while(m!=l);z:S NULL;}N*A(N*n,N*l){if(!l)n->n=n,l=n;
else n->n=l->n,l->n=n;S l;}N*R(N*n,N*l){if(!l||(l==n&&n->n==n))goto z;
N*m=l;do{if(m->n==n){m->n=n->n;S m;}m=m->n;}while(m!=l);z:S NULL;}
int E(N*l){int i=0;if(!l)goto z;N*m=l;do{++i;m=m->n;}while(m!=l);z:S i;}
int C(N*l){N*c=NULL,*n=l,*m=l=R(n,l);c=A(n,c);int a=E(l)*E(l);do{
if(!l)S 1;n=m->n;if(I(m->x-1,m->y,c)||I(m->x+1,m->y,c)||I(m->x,m->y-1,c)
||I(m->x,m->y+1,c))l=R(m,l),c=A(m,c);m=n;}while(--a);S 0;}

```

More than half the bulk is taken up by a minimal implementation of a linked list---c is horribly deficient in that sense.

The code here includes the definition of the nodes and all the list manipulation functions called by `C`, my connectedness checker.

The method is to maintain two lists (one of connected nodes initialized by the first node) and one of yet-to-be-connected nodes (starting with everything else). What follows is an exhaustive cyclic search to find a connection for each node in turn. There is an upper limit on the number of attempts conservatively set to length-of-the-list squared, which marks the end of attempts. Very inefficient, but functional.

It completes several simple cases of my own devising and both of the given test cases correctly.

**Full program with test scaffold and some comments**

```
#include <stdio.h>
#include <stdlib.h>
typedef struct n N;
struct n{
  int x,y;
  N*n;
};
N*I(int x,int y,N*l){ /* Return pointer to node x,y in l or NULL */
  if(!l)goto z;
  N*m=l;
  do{
    if((m->x==x)&&(m->y==y)){
      return m;
    }
    m=m->n;
  }while(m!=l);
 z:return NULL;
};
N*A(N*n,N*l){ /* Add node n to list l. Return the new l */
  if(!l){
    n->n=n;
    l=n;
  }else{
    n->n=l->n;
    l->n=n;
  }
  return l;
};
N*R(N*n,N*l){ /* Remove node n from list l. Return the new l */
  if(!l||(l==n&&n->n==n))goto z;
  N*m=l;
  do{
    if(m->n==n){m->n=n->n; return m;}
    m=m->n;
  }while(m!=l);
 z:return NULL;
}
int E(N*l){ /* Return the Enumberation of nodes in list l */
  int i=0;
  if(!l)goto z;
  N*m=l;
  do{++i;m=m->n;}while(m!=l);
 z:return i;
}
int C(N*l){ /* return true if all nodes in list l are connected */
  N*c=NULL,*n=l,*m=l=R(n,l); /* put the first node in the connected
                            list, and mark the start of the
                            working list */
  c=A(n,c);
  int a=E(l)*E(l); /* maximum number of times to try to place nodes */
  do {
    if (!l) return 1; /* when l is empty: we win! */
    n=m->n;
    if ( I(m->x-1,m->y  ,c) ||
     I(m->x+1,m->y  ,c) ||
     I(m->x  ,m->y-1,c) ||
     I(m->x  ,m->y+1,c) ) l=R(m,l), c=A(m,c);
    m=n;
  } while (--a);
  return 0;
}
void P(N*l){ /* Print the list */
  printf("List: [");
  if(!l)goto z;
  N*m=l;
  do{printf(" (%d, %d)",m->x,m->y);m=m->n;}while(m!=l);
 z:printf(" ]\n");
}
N*G(int x,int y){ /* generate a new node with (x, y) */
  N*n;
  if(n=malloc(sizeof(N)))n->x=x,n->y=y;
  return n;
}
int main(){
  N*n,*l=NULL;

  n=G(0,0); l=A(n,l);
  n=G(1,0); l=A(n,l);
  n=G(2,0); l=A(n,l);
  n=G(0,1); l=A(n,l);
  n=G(0,2); l=A(n,l);
  n=G(2,2); l=A(n,l);
  n=G(3,2); l=A(n,l);
  n=G(4,2); l=A(n,l);
  n=G(0,3); l=A(n,l);

  n=G(4,3); l=A(n,l);
  n=G(0,4); l=A(n,l);
  n=G(1,4); l=A(n,l);
  n=G(2,4); l=A(n,l);
  n=G(4,4); l=A(n,l);
  n=G(4,5); l=A(n,l);
  n=G(2,6); l=A(n,l);
  n=G(3,6); l=A(n,l);
  n=G(4,6); l=A(n,l);

  P(l);
  if (C(l)) {
    printf("Connected!\n");
  } else {
    printf("Not connected.\n");
  };
}

```

# Answer
> 3 votes
My first python version (loosely) translated into golfscript. Urgh. 80 chars.

```
{1$!!1$!!&{(~:v;:u;[1u+v u 1v+u 1- v u v 1-]2/@.@&.@\-\@|g}{;!}if}:g;{([.;]g}:f;

```

test cases:

```
# test cases
[[0 0] [1 0] [2 0] [3 0] [3 1] [3 2] [2 2] [1 2] [0 2] [0 3] [0 4] [1 4] [2 4] [3 4]]:a0;
[[0 0] [1 0] [2 0] [0 1] [0 2] [2 2] [3 2] [4 2] [0 3] [4 3] [0 4] [1 4] [2 4] [4 4] [4 5] [2 6] [3 6] [4 6]]:a1;
a0 f p
a1 f p

```

python 2.6; second attempt

```
def f(a):
    a = set(a)
    e = lambda (x, y) : set([(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)])
    p = lambda k : a.discard(k) or map(p, e(k) & a)
    p(a.pop())
    return not a

```

python 2.6; first attempt

```
def f(a):
    a = set(a)
    e = lambda (x, y) : set([(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)])
    b = set([a.pop()])
    while b and a:
        c = a & e(b.pop())
        a -= c
        b |= c
    return not a

```

usage:

```
a_0 = [
    (0,0),(1,0),(2,0),(3,0),(3,1),(3,2),(2,2),
    (1,2),(0,2),(0,3),(0,4),(1,4),(2,4),(3,4)
]
a_1 = [
    (0,0),(1,0),(2,0),(0,1),(0,2),(2,2),(3,2),(4,2),(0,3),
    (4,3),(0,4),(1,4),(2,4),(4,4),(4,5),(2,6),(3,6),(4,6)
]
for a in (a_0, a_1):
    print 'YES' if f(a) else 'NO'

```

# Answer
> 3 votes
## Perl, 130 ~~133~~

A simple mark-and-sweep depth-first traversal, made much longer than I'd like by Perl sigils.

```
sub g{my($a,$b)=@_;g($a-1,$b),g(
$a+1,$b),g($a,$b-1),g($a,$b+1)if
delete$m{$a,$b}}sub f{($a,$b)=@_;
$m{pop,pop}++while@_;g$a,$b;!%m}

```

Sample use:

```
say f( (0,0),(1,0),(2,0),(3,0),(3,1),(3,2),(2,2),
       (1,2),(0,2),(0,3),(0,4),(1,4),(2,4),(3,4) )
  ? 'YES' : 'NO';
say f( (0,0),(1,0),(2,0),(0,1),(0,2),(2,2),(3,2),(4,2),(0,3),
       (4,3),(0,4),(1,4),(2,4),(4,4),(4,5),(2,6),(3,6),(4,6) )
  ? 'YES' : 'NO';

```

# Answer
> 3 votes
## Prolog - 118

```
c([_]).
c([[X,Y]|L]):-member([A,B],[[X+1,Y],[X-1,Y],[X,Y+1],[X,Y-1]]),C is A,D is B,select([C,D],L,N),c([[C,D]|N]),!.

```

Usage:

```
?- c([[0,0],[1,0],[2,0],[3,0],[3,1],[3,2],[2,2],[1,2],[0,2],[0,3],[0,4],[1,4],[2,4],[3,4]]).
true.

?- c([[0,0],[1,0],[2,0],[0,1],[0,2],[2,2],[3,2],[4,2],[0,3],[4,3],[0,4],[1,4],[2,4],[4,4],[4,5],[2,6],[3,6],[4,6]]).
false.

```

# Answer
> 2 votes
# Perl - 150

```
sub f{$m[pop][pop]++while@_;for$i(0..@m){for$j(0..9){$_.=$m[$i][$j]||0}$_.="3"}s/1/2/;for$n(0..99){s/(?<=2)1|1(?=2)|1(?=.{10}2)|(?<=2.{10})1/2/}!m/1/}

```

Works for 10 columns. For more I'd need another character.

Expands the color of one square a lot of times with one regex. Building the string takes a lot more space than I'd like it to.

Ungolfed:

```
sub f{
    $m[pop][pop]++ while @_;
    for $i (0..@m) {
        for $j (0..9) {
            $_ .= $m[$i][$j] || 0
        }
        $_ .= "3";
    }
    s/1/2/;
    for$n(0..99) {
        s/(?<=2)1|1(?=2)|1(?=.{10}2)|(?<=2.{10})1/2/
    }
    !m/1/
}

print f((0,0),(1,0),(2,0),(3,0),(3,1),(3,2),(2,2), (1,2),(0,2),(0,3),(0,4),(1,4),(2,4),(3,4)) ? YES : NO;

```

# Answer
> 2 votes
## Haskell 98, 98

```
g p@(x,y)z|elem p z=foldr g(filter(/=p)z)[(x-1,y),(x+1,y),(x,y-1),(x,y+1)]|0<1=z
f z=null$g(z!!0)z

```

Sample use:

```
*Main> f [(0,0),(1,0),(2,0),(3,0),(3,1),(3,2),(2,2),
          (1,2),(0,2),(0,3),(0,4),(1,4),(2,4),(3,4)]
True
*Main> f [(0,0),(1,0),(2,0),(0,1),(0,2),(2,2),(3,2),(4,2),(0,3),
          (4,3),(0,4),(1,4),(2,4),(4,4),(4,5),(2,6),(3,6),(4,6)]
False

```

# Answer
> 2 votes
**Sage: 55 53 char**

```
graphs.GridGraph([100]*2).subgraph(x).is_connected()

```

Where x is a list of coordinates,

```
x=[(0,0),(1,0),(2,0),(3,0),(3,1),(3,2),(2,2),(1,2),(0,2),(0,3),(0,4),(1,4),(2,4),(3,4)]

```

---
Tags: code-golf, decision-problem, connected-figure
---


title: Add two vectors modulo 5

text:
# Question
Title: Add two vectors modulo 5
Interpret a triple of 32-bit integers as a vector of 32 integers modulo 5. Write an addition routine for these vectors.

**Example**:

```
def add32((a0,a1,a2),(b0,b1,b2)):
    c0 = c1 = c2 = 0
    m = 1
    for i in range(32):
        a  = ((a0//m)&1) + 2*((a1//m)&1) + 4*((a2//m)&1)
        b  = ((b0//m)&1) + 2*((b1//m)&1) + 4*((b2//m)&1)
        c  = (a+b)%5
        c0+= m*(c&1)
        c1+= m*((c&2)//2)
        c2+= m*((c&4)//4)
        m += m
    return c0,c1,c2

```

**Note**:

You only need to be internally consistent, not consistent with my sample code. If you use a different representation of the integers mod 5, that's fine as long as you provide a translation table of the form:

```
0 = 000 or 101
1 = 001 or 110
2 = 010 or 111
3 = 011
4 = 100

```

**Scoring**:

Characters + number of arithmetic operations required. The sample code takes 331 characters and 34 operations per bit (note that I'm not counting the function call or iteration, nor interpreter overhead); hence gets a score of 331+1056=1686.

**Clarification**:

This is a trick called *bitslicing*. It's natural to pack integers mod 5 directly into words (spaces added for clarity:

```
0 1 2 3 4 -> 000 001 010 001 101

```

but you end up sacrificing a few bits at the end of each word. To keep your data aligned but pack the most in, store the data in *slices*

```
                 0 0 0 0 1 = a2
a = 0 1 2 3 4 -> 0 0 1 1 0 = a1
                 0 1 0 1 0 = a0

```

**Example 2**

A language-agnostic example was requested, so here it is. Suppose we use the representation

```
0 = 100
1 = 001
2 = 010 or 101
3 = 110
4 = 011

```

and `111` and `000` are meaningless. Then, the following sum is valid according to our representation:

```
                  1 0 0 1 1 0 1 0
0 1 2 2 3 4 0 2 = 0 0 1 0 1 1 0 1
                  0 1 0 1 0 1 0 0
+
                  0 1 0 0 1 0 1 1
1 2 1 2 0 1 0 3 = 0 0 0 1 0 0 0 1
                  1 1 1 0 0 1 0 0
---------------------------------
                  0 1 1 0 1 1 1 1
1 3 3 4 3 0 0 0 = 0 1 1 1 1 0 0 0
                  1 0 0 1 0 0 0 0

```

**Remark**

As Keith Randall has demonstrated, this can be done with all bits in parallel using logical operators. We can view such a solution as a circuit with a certain number of gates. Perhaps I should call this "circuit golf". I chose 5 instead of 3 because it's too easy to brute-force (optimal is 6 gates/trit).

# Answer
## Python, score=215 166 (167 118 chars, at most 48 ops)

```
def A(x,y,z,p,q,r):
 u,c=x^p,x&p;v,d=y^q^c,y&q|y&c|q&c;w,e=z^r^d,z&r|z&d|r&d
 if e:u,v,w=A(e,e,0,u,v,w)
 return u,v,w

```

Does addition in bit-parallel. The `c,d,e` are the 32 carries from one position to the next. `e` represents multiples of 8 that carry out of the vector, so if `e` has any bits set in it, we add 8%5=3 back in using a recursive call.

The translation table is the same as the one given in the question.
> 5 votes

---
Tags: code-golf, math, optimization
---


title: Knuth's Power Tree

text:
# Question
Title: Knuth's Power Tree
In The Art of Computer Programming, Knuth describes an algorithm to compute short addition chains. The algorithm works by computing a tree known as the Power Tree. The tree is rooted at 1, and each level is computed from the previous. Suppose we've computed level *k*. Then, for each node (*n*) in level *k*, and each ancestor (or self) *a = 1, 2, ..., n* of *n*, add the node *n+a* to level *k+1* if it is not already in the tree; the parent of *n+a* is *n*.

Three important things to note:

* nodes should be visited in the order that they are created
* levels are to be computed one at a time (not recursively)
* traverse the ancestors from smallest to largest (or you end up a familiar, but less optimal tree)

**A picture of the tree**

Perhaps drawing this tree would be fun to golf? Hmm. At the least, the result would probably be a better-drawn tree. FWIW, `10` has 4 children.

```
             1
             |
             2
            / \
           3   4
          /\    \
         /  \    \
        5    6    8
       / \    \\   \
      /  |     \\   \
     /   |      \\   \
    7    10     9 12  16
   /   / /\ \    \ \   \\
  /   / /  \ \    \ \   \\
14  11 13  15 20  18 24 17 32

```

**Naive Python Implementation**

Since my verbose description of the tree seems to be lacking, here's a naive Python implementation. I store the tree as a dictionary here, `parent(x) := tree[x]`. There's lots of fun optimization to be had here.

```
def chain(tree,x):
    c = [x]
    while x!=1:
        x=tree[x]
        c.append(x)
    return c[::-1]

tree = {1:None}
leaves = [1]
levels = 5
for _ in range(levels):
    newleaves = []
    for m in leaves:
        for i in chain(tree,m):
            if i+m not in tree:
                tree[i+m] = m
                newleaves.append(i+m)
    leaves = newleaves

```

**Requirements**

Your program should take one argument *n*, compute the complete tree with all integer nodes *i* with *0 \<= i \<= n*, and then take input from the user. For each input, print out the path from the root to that input. If an input isn't an integer between 0 and *n* (inclusive), behavior is undefined. Terminate if the user inputs zero.

**Example Session**

```
./yourprogram 1000
?1000
1 2 3 5 10 15 25 50 75 125 250 500 1000
?79
1 2 3 5 7 14 19 38 76 79
?631
1 2 3 6 12 24 48 49 97 194 388 437 631
?512
1 2 4 8 16 32 64 128 256 512
?997
1 2 3 5 7 14 28 31 62 124 248 496 501 997
?0

```

# Answer
### Ruby, 172 148 139 137 characters

```
P={1=>[1]}
a=->k{P[k].map{|t|P[k+t]||=P[k]+[k+t]}}
P.keys.map{|v|a[v]}until(1..$*[0].to_i).all?{|u|P[u]}
STDIN.map{|l|p P[l.to_i]||break}

```

Most of the code is for input and output. Building the tree is only a few chars (lines 1-2). The tree is represented by a hash where key is the node and value its path to root. Since a tree of size `n` may not contain all numbers up to `n` we continuously add more levels until all numbers up to `n` are present in the tree.

For the example given above:

```
>1000
[1, 2, 3, 5, 10, 15, 25, 50, 75, 125, 250, 500, 1000]
>79
[1, 2, 3, 5, 7, 14, 19, 38, 76, 79]
>631
[1, 2, 3, 6, 12, 24, 48, 49, 97, 194, 388, 437, 631]
>512
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
>0

```

*Edit 1:* Now the hash contains the path for each node as value already and therefore there is no need to build the path each time.

*Edit 2:* Changed the break condition for the final loop.

*Edit 3:* Changed the condition for the build-loop.
> 3 votes

# Answer
## Haskell, 174 185 195 characters

```
(%)=lookup
t(n,w)=map(\m->(n+m,n+m:w))w
_#0=return()
k#n=maybe(foldr(\e@(i,_)r->maybe(e:r)(\_->r)$i%r)k(k>>=t)#n)((>>main).print.reverse)$n%k
main=getLine>>=([(1,[1])]#).read

```

This version actually totally ignores the argument, and calculates the tree incrementally on demand.

```
1000
[1,2,3,5,10,15,25,50,75,125,250,500,1000]
79
[1,2,3,5,7,14,19,38,76,79]
631
[1,2,3,6,12,24,48,49,97,194,388,437,631]
512
[1,2,4,8,16,32,64,128,256,512]
997
[1,2,3,5,7,14,28,31,62,124,248,496,501,997]
0

```

Oh look! There wasn't any requirement to output a prompt. So now the code doesn't.

---

* Edit (195 → 185): combined `main` and `i`
* Edit (185 → 174): removed prompt

---

## Ungolf'd

Here is an expanded version of the core computation:

```
type KPTree = [(Int, [Int])]
  -- an association from numbers to their ancester chains
  -- ancester chains are stored biggest to smallest
  -- the associations are ordered as in the tree, reading right to left,
  -- from the lowest level up

kptLevels :: [KPTree]
kptLevels = [(1,[1])] : map expand kptLevels
  -- a list of successive KPTrees, each one level deeper than the last
  where
    expand tree = foldr addIfMissing tree (concatMap nextLeaves tree)
    addIfMissing e@(n,_) tree = maybe (e:tree) (const tree) $ lookup n tree
    nextLeaves (n,w) = map (\m -> (n+m, n+m:w)) w

kptPath :: Int -> [Int]
kptPath n = findIn kptLevels
  -- find the ancestor chain for a given number
  where
    findIn (k:ks) = maybe (findIn ks) id $ lookup n k

```

To illustrate the strangeness of how to apply the pre-computation requirement to a lazy language, consider this version of `main`:

```
kptComputeAllTo :: Int -> [[Int]]
kptComputeAllTo n = map kptPath [1..n]
  -- compute all the paths for the first n integers

main :: IO ()
main = do
    n <- (read . head) `fmap` getArgs
    go $ kptComputeAllTo n
  where
    go preComputedResults = loop
      where
        loop = getLine >>= process . read
        process 0 = return ()
        process i = (print $ reverse $ preComputedResults !! (i - 1)) >> loop

```

Even thought it builds an array of the results for the first `n` integers, only those that are used are ever actually computed! Here's how fast it runs with 50 million as an argument:

```
> (echo 1000; echo 0) | time ./3177-PowerTree 50000000
[1,2,3,5,10,15,25,50,75,125,250,500,1000]
        0.09 real         0.07 user         0.00 sys

```
> 1 votes

---
Tags: code-golf
---


title: Chess endgame: White to Mate In One

text:
# Question
Title: Chess endgame: White to Mate In One
Given an 8x8 grid of letters representing the current state of a game of chess, your program's task is to find a next move for white that results in checkmate (the answer will always be mate in one move).

## Input

Input will be on STDIN - 8 lines of 8 characters each. The meanings of each character are as follows:

```
K/k - king
Q/q - queen
B/b - bishop
N/n - knight
R/r - rook
P/p - pawn
- - empty square

```

Upper case letters represent white pieces, and lower case represents black. The board will be oriented so that white is playing up from the bottom and black is playing down from the top.

## Output

A move for white that results in checkmate, in algebraic notation. You do not need to notate when a piece has been taken, nor do you need to be concerned about disambiguating between two identical pieces which can make the same move.

## Sample input

**Example 1**

Input:

```
------R-
--p-kp-p
-----n--
--PPK---
p----P-r
B-------
--------
--------

```

Output:

```
c6

```

**Example 2**

Input:

```
--b-r--r
ppq-kp-p
-np-pn-B
--------
---N----
--P----P
PP---PP-
R--QRBK-

```

Output:

```
Nf5

```

**Example 3**

Input:

```
---r-nr-
-pqb-p-k
pn--p-p-
R-------
--------
-P-B-N-P
-BP--PP-
---QR-K-

```

Output:

```
Rh5

```

You can assume that the solution will not involve castling or en-passant.

This is code-golf - shortest solution wins.

<sup>(~~Examples taken from mateinone.com - puzzles 81, 82 and 83~~ Website has been replaced with spam)</sup>

# Answer
### Ruby, 589 512 510 499 493 characters

```
R=0..7
a=->b{o=[];R.map{|r|R.map{|c|v=Hash[?K,[6,7,8,11,13,16,17,18],?R,s=[157,161,163,167],?B,t=[156,158,166,168],?Q,s+t,?N,[1,3,5,9,15,19,21,23],?P,[32,181,183]][z=b[r][c]];v&&v.map{|s|k=2!=l=s/25+1;u=r;v=c;l.times{u+=s/5%5-2;v+=s%5-2;R===u&&R===v||break;t=b[u][v];j=t<?.&&l<8;(j||t=~/[a-z]/&&k)&&o<<=(h=b.map &:swapcase;h[u][v]=h[r][c];h[r][c]=?-;[z+"%c%d"%[97+v,8-u],h.reverse]);j&&(k||r==6)||break}}}};o}
a[$<.map{|l|l}].map{|m,b|a[b].any?{|f,x|a[x].all?{|g,y|y*""=~/K/}}||$><<m[/[^P]+/]}

```

Input is given via stdin, e.g.:

```
> ruby mateinone.rb
--------
--------
--------
-k------
b-------
-N-P----
--------
-----K-Q
^Z
Qb7

```

The output is not just one move that forces a mate in one but every move that does so.

*Edit 1:* The function `e` was used only once so I inlined it. Second, the encoding now is based on number 5 instead of 10. And refactoring the cloning of the board saved quite a few chars.

*Edit 2:* Still not as much improvement as I wanted. Changing the hash from `{a=>b,c=>d}` to `Hash[a,b,c,d]`. This costs 4 characters but saves one per key-value pair.

*Edit 3:* Only minor reductions: inlining M (4 characters), `t==?-` -\> `t<?.` (2), removing Pawn in algebraic notation at the end (2), replaced puts (3). The program is now less than 500 characters.

*Edit 4:* It is interesting how much one can still find in such a program. Moved an invariant outside the loop and found another duplicate calculation.
> 8 votes

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


title: Paint that fence

text:
# Question
Title: Paint that fence
You are Tom Sawyer and you have to paint a fence of 102400 m long. Luckily, your friends decided to help you in exchange of various things. Each friend will paint **L** meters, starting from **S** with color **C**. **S**, **L** are integer amount of meters and 1 ≤ **C** ≤ 97. Getting bored you decide to find out how many meters of each color you have.

**Input**

Input is read from standard input. Each line contains three numbers **S**, **L**, **C** as described above.

**Ouput**

Output is written to standard output. For each color that appears on the final fence print the color number and the number of times it appears. Order by colors.

**Examples**

*Input 0*

```
                           ..............
0 3 1                      111...........
2 4 2                      112222........
1 2 3                      133222........
0 4 1                      111122........
7 3 5                      111122.555....

```

*Output 0*

```
1 4
2 2
5 3

```

*Input 1*

```
 0 100 1
 50 150 2

```

*Output 1*

```
 1 50
 2 150

```

*Input 2*

```
 500 1000 1
 0 2000 2

```

*Output 2*

```
 2 2000

```

**More examples**

Here is a small generator:

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

/* From http://en.wikipedia.org/wiki/Random_number_generation */
unsigned m_w;
unsigned m_z;

unsigned get_random()
{
  m_z = 36969 * (m_z & 65535) + (m_z >> 16);
  m_w = 18000 * (m_w & 65535) + (m_w >> 16);
  return (m_z << 16) + m_w;  /* 32-bit result */
}

int main(int argc, char **argv)
{
  int i;

  assert(argc == 2);
  m_w = 0xbabecafe;
  m_z = atoi(argv[1]);

  i = 10;
  while (i--);
    get_random();

  i = atoi(argv[1]);
  while (i--) {
    int s = (int) ((get_random() << 8) % 102397);
    int l = (int) ((get_random() << 8) % (102397 - s));
    int c = (int) ((get_random() << 8) % 97 + 1);
    printf("%d %d %d\n", s, l, c);
  }

  return 0;
}

```

Running examples:

```
$ ./gen 1 | ./paint
6 535
$ ./gen 10 | ./paint
28 82343
36 3476
41 1802
49 4102
82 1656
$ ./gen 100 | ./paint
2 2379
22 17357
24 4097
25 1051
34 55429
42 9028
45 9716
66 1495
71 196
85 640
97 706
$ ./gen 1000 | ./paint
16 719
26 29
28 24
33 1616
55 371
65 35
69 644
74 16
84 10891
86 36896
87 50832
89 19
$ ./gen 10000 | ./paint
3 800
6 5712
14 3022
17 16
26 1
29 18770
31 65372
37 387
44 40
49 37
50 93
55 11
68 278
70 19
71 64
72 170
77 119
78 6509
89 960
97 15
$ ./gen 100000 | ./paint
2 6
8 26
12 272
24 38576
26 1
34 1553
35 8
36 19505
43 2
45 11
46 2
47 9
49 27339
50 139
53 3109
69 11744
92 89
$ ./gen 1000000 | ./paint
1 1
3 4854
6 523
13 1
16 11
18 416
22 7
24 3920
25 96
31 10249
32 241
37 1135
45 10
57 758
62 2348
65 11
66 7422
78 6
85 13361
87 3833
88 187
91 46
93 7524
96 45436

```

Your program must run in reasonable time. My solution runs in a few seconds on the last example.

Shortest code wins.

**Include running time and your output for the last test.**

**EDIT**: This problem is not intended to be brute-forced, so a trivial solution is not acceptable.

# Answer
> 2 votes
## Python, 221 239 chars

```
import sys
F=[]
for L in sys.stdin:s,l,c=map(int,L.split());F=sum([[(a,min(b,s),d)]*(a<s)+[(max(a,s+l),b,d)]*(b>s+l)for a,b,d in F],[(s,s+l,c)])
C=[0]*98
for a,b,c in F:C[c]+=b-a
for c in range(98):
 if C[c]:print c,C[c]

```

Keeps `F` as an unordered list of triples (start of run, end of run, color) representing the current state of the fence. Since the random painting in the generator overpaints larges swathes fairly frequently, this list is never too long (typically in the 15-40 range).

Runs in 37 seconds on the 1M example.

# Answer
> 1 votes
## Haskell, 251 261 269 294 characters

```
import Data.List
w@(y@(f,d,e):z)§x@[a,b,c]|e<=d=z§x|a+b>d=(f,d,e`min`a):((f,a+b,e):z)§x
w§[a,b,c]=(c,a,a+b):w
r(c,a,b)=replicate(b-a)c
f l=shows(l!!0)" "++shows(length l)"\n"
main=interact$(>>=f).group.(>>=r).sort.foldl'(§)[].map(map read.words).lines

```

Something isn't quite right about this as it takes far too much time and stack... But it does produce the right answers:

```
$> ghc -O3 --make -rtsopts -with-rtsopts -K32m 3095-PaintTheFence.hs
Linking 3095-PaintTheFence ...

$> ./3095-gen 1000000 | time ./3095-PaintTheFence
1 1
3 4854
6 523
13 1
16 11
18 416
22 7
24 3920
25 96
31 10249
32 241
37 1135
45 10
57 758
62 2348
65 11
66 7422
78 6
85 13361
87 3833
88 187
91 46
93 7524
96 45436
       43.99 real        43.42 user         0.46 sys

```

---

* Edit (294 → 269) `replicate` and `group` is just as efficient way of counting up the paint, and takes less code than the custom function `s`
* Edit (269 → 261) no need for `max` call
* Edit (261 → 251) no need for to cull paint 0 in `f`

# Answer
> 0 votes
## Perl - 148 bytes

It seems that Perl is the best to play with. easy to code shorter and faster. ;)

**code:**

```
#!perl -n
($a,$b,$c)=split;substr($s,$a,$b,chr($c)x$b)}BEGIN{$s="z"x102400}{$s=~s/([^z])\1*/$H{$1}+=length$&/ge;print ord," $H{$_}
"for sort keys%H

```

**time:**

```
time ./gen 1000000 | perl paint.pl
...
real    0m9.767s
user    0m10.117s
sys 0m0.036s

```

# Answer
> 0 votes
## JavaScript, 183 chars, 1.3 seconds

Sadly, I did have to cut the stdin/out part of the requirement, which JavaScript doesn't support. Instead, I get the input from a file upload `<input>` instead (which I don't count in my char count, although I probably should).

Here is the ungolfed version. It's a function that takes the full input string... all 14MB of it! This is the one that takes 1.3 seconds; the golfed version takes about twice as long -- but it still beats the other solutions! Interestingly, it's twice as fast in Firefox than in Chrome. Live demo here.

```
function Q(input) {

    var c = [];
    var l = input.trim().split(/\s/g);
    input = null
    var length = l.length;

    // Loop through each meter of the wall...
    for (var i = 0; i <= 102400; i++) {

        // ...and loop through each of the friends, finding
        // the last one who painted this meter...
        for (var j = length; j > 0; ) {
            j -= 3;

            // Start = +l[j]
            // Length = +l[j + 1]
            // Color = +l[j + 2]

            var S = +l[j];
            if (S <= i && +l[j + 1] + S > i) {

                // ...and incrementing the color array.
                var C = +l[j + 2];
                if (!++c[C])
                    c[C] = 1;

                break;
            }
        }
    }

    console.log(c.map(function (a,b) {return b + ' ' + a}).filter(function (a) { return a }).join('\n'));
}

```

And here's the golfed version.

```
function G(i){l=i.trim(c=[]).split(/\s/)
for(i=0;i<102401;i++)for(j=l.length;j>0;)if(l[j-=3]<=i&&i-l[j+1]<l[j]){if(!++c[l[j+2]])c[l[j+2]]=1
break}for(k in c)console.log(k+' '+c[k])}

```

# Answer
> -1 votes
```
$ cat input.txt
0 3 1
2 4 2
1 2 3
0 4 1
7 3 5

$ cat input.txt  | perl -anE '@a[$F[0]..$F[0]+$F[1]]=($F[2])x$F[1];END{$i[$_]++for@a;$i[$_]&&say"$_ $i[$_]"for 1..$#i}'
1 4
2 1
5 3

$ cat input2.txt
500 1000 1
0 2000 2

$ cat input2.txt  | perl -anE '@a[$F[0]..$F[0]+$F[1]]=($F[2])x$F[1];END{$i[$_]++for@a;$i[$_]&&say"$_ $i[$_]"for 1..$#i}'
2 2000

```

---
Tags: code-golf
---


title: Session-Saving Quine

text:
# Question
Title: Session-Saving Quine
Inspired by this question.

Create a program that prompts the user to store some data, and when the program is quitting, spit out the program itself, except the session data changed.

The user then open the newly generated program, and can recall the data from the previous program.

Commands

* `KEY VALUE`: sets session variable `KEY` to `VALUE`
* `*`: clear all data
* `! KEY`: delete `KEY`
* `? KEY`: query `KEY` (if not exist: print nothing and move on)
* otherwise, quit the program

Neither key or value cannot contain any spaces. The newly generated program's filename must identify the version of the program, you can use dates or counters.

Example interaction:

```
 name test                    store name = test
                              data is now { name: test }
 0 1                          data is now { name: test, 0: 1 }
 ? name                       output: test
 ! 0                          delete 0
                              data is now { name: test }
 hello good world             data is now { name: test, hello: good }
                              the extra word "world" is ignored
 egiwiwegiuwe                 the "otherwise" case: quit program

```

The user opens the newly generated program

```
 ? name                       output: test
 name retest                  data is now { name: retest }
 *                            clear
                              data is now { }

```

Sample implementation: https://gist.github.com/1128876

Rules

* You do not need to preserve comments or insignificant whitespaces in the quined program: just preserve the functionality and the data
* You cannot use any external storage.
* No cheating quines, like any other quine problems.
* Shortest code wins.

# Answer
> 1 votes
## Ruby 1.9, 159 156

This program generates files named "1", "2", "3" and so on.

```
b={}
I=1
eval T="loop{c,d=gets.split
c==?*?b={}:d ?c==?!?b.delete(d):c==???puts(b[d]):b[c]=d :break}
open(I.to_s,?w){|f|f<<'b=%p
I=%d
eval T=%p'%[b,I+1,T]}"

```

# Answer
> 1 votes
## D (419 chars)

```
enum c=q{string[string] m;import std.stdio;import std.array;void main(){foreach(string s;lines(stdin)){auto a=s.split;if(!a.length)goto e;switch(a[0]){case "*":m.clear;break;case "!":m.remove(a[1]);break;case "?":writeln(m.get(a[1],""));break;default:if(a.length<2){goto e;}m[a[0]]=a[1];}stdout.flush;}e:write("static this(){");foreach(i,v;m)writef("m[`%s`]=`%s`;",i,v);write("}enum c=q{",c,"};mixin(c);");}};mixin(c);

```

formatted:

```
enum c=q{
    string[string] m;
    import std.stdio;
    import std.array;
    void main(){
        foreach(string s;lines(stdin)){
            auto a=s.split;
            if(!a.length)goto e;
            switch(a[0]){
                case "*":m.clear;break;
                case "!":m.remove(a[1]);break;
                case "?":writeln(m.get(a[1],""));break;
                default:if(a.length<2){goto e;}m[a[0]]=a[1];
            }
            stdout.flush;
        }
        e:write("static this(){");
        foreach(i,v;m)writef("m[`%s`]=`%s`;",i,v);
        write("}enum c=q{",c,"};mixin(c);");
    }
};mixin(c);

```

variant of my D quine

the `*` command relies on `m.clear;` to work correctly which it doesn't in dmd 2.52 (bug in the compiler)

the need for `stdout.flush;` depends whether auto flush is enabled (it isn't on my machine)

# Answer
> 1 votes
## JavaScript, 245

```
(function(o,N){while(a=prompt()){a=a.split(' ')
b=a[0]
c=a[1]
if(b=='*')o={}
else if(b=='?'){if(o[c]!=N)alert(o[c])}
else if(b=='!')delete o[a[1]]
else if(c!=N)o[b]=c
else break}alert('('+arguments.callee+')('+JSON.stringify(o)+')')}({}))

```

---
Tags: code-golf, quine
---


# Question
Title: Text Statistics: Return a list/array of the number of occurrences of each character used in a text file, including spaces, tabs, and new lines
Generic Lorem Ipsum:

> Lorem ipsum dolor sit amet, consectetur adipiscing elit. Mauris felis dolor, bibendum at tincidunt vel, imperdiet eget libero. Cras vel felis purus. Phasellus a vestibulum enim. Sed eu orci ac nisl sodales scelerisque in id mi. Duis et nunc et nisl blandit aliquet ornare sed risus. Sed arcu magna, porttitor vel tincidunt quis, placerat non urna. Donec ut dolor eros, et viverra diam. Aliquam luctus, justo sed cursus imperdiet, velit nulla gravida nibh, vel scelerisque neque sem eget enim. Nunc in urna a velit adipiscing fermentum. Donec euismod faucibus purus. Vestibulum pretium, ligula commodo facilisis sollicitudin, nibh dolor adipiscing augue, nec tempus leo lectus eu enim. Vestibulum non erat velit, eget vulputate metus. Praesent at tincidunt elit. Add some stuff to it? !@#$%^&\*()-\_=+\\|\]}\[{'";:/?.\>,\<\`~
>
> Nunc pretium metus sed elit dignissim porta. Cras at dui quam. Mauris at elementum tellus. Sed placerat volutpat enim convallis egestas. Suspendisse consectetur egestas mattis. Proin interdum, lectus a tincidunt sollicitudin, mauris ligula accumsan nisi, et suscipit lectus enim id mi. In est ipsum, cursus nec eleifend id, sollicitudin ac sem. Nam augue felis, dapibus in faucibus sit amet, ultrices eget purus. Etiam suscipit mauris at velit fringilla molestie. Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus. Vivamus faucibus tortor in libero convallis pharetra. Donec eros diam, tincidunt vitae euismod ut, bibendum non orci. Nullam quam tortor, accumsan id malesuada nec, dignissim vitae magna. Suspendisse mi odio, commodo ut tempor porttitor, congue sit amet risus. Praesent feugiat lacus quis orci sodales cursus. Vivamus ac lorem id sem iaculis interdum.

# Answer
## PHP (16) (35) (28)

The default mode of count\_chars() returns "an array with the byte-value as key and the frequency of every byte as value."

Edit: Oops, I just realized it's supposed to read in from a file. That adds 19 characters, so it might be beatable now.

Edit 2: Reduced it by 7 characters.

```
count_chars(join(file($s)));

```
> 4 votes

# Answer
## C: 50 chars (74 chars if done right)

"Return an array" is a pretty rare case when using C, because we can't actually return an array unless it's global or allocated by `malloc()`. So I decided to use a global one. The input is read from STDIN. The function works only on little-endian architectures.

```
n[256],r;*c(){while(read(0,&r,1))n[r]++;return n;}

```

The whole program that uses this function (with indentation added):

```
n[256],r;
*c()
{
    while (read(0,&r,1))
        n[r]++;
    return n;
}
main()
{
    int *num = c();
    int i;
    for (i = 0; i < 256; ++i)
        printf("%d ", num[i]);
}

```

Yeah, I know I won't ever beat anybody with C.

**EDIT:**

There are some rightful remarks in comments, so I've rewritten the code so that it meets all the requirements. Now it's 74 chars long.

```
n[256],r,*f,*s;*z(){f=fopen(s,"r");while(fread(&r,1,1,f))n[r]++;return n;}

```

And the indented code with `main()` added:

```
n[256],r,*f,*s;
*z()
{
    f=fopen(s,"r");
    while(fread(&r,1,1,f))
        n[r]++;
    return n;
}
main(int c,char**a)
{
    int *stat, i;
    s = a[1];
    stat = z();
    for (i = 0; i < 256; ++i)
        printf("%d ", stat[i]);
    printf("\n");
}

```
> 3 votes

# Answer
This one is relatively simple. I chose to do it in Perl (my favorite scripting language). :)

## Perl: 41 characters 63 characters

Might be able to reduce it somewhat but this is what I'm starting with.

```
sub s{open(I,"<$_[0]");while(!eof(I)){read(I,$c,1);$s{$c}++}%s}

```

**EDIT:**
Got it down further:

```
sub s{foreach(split//,$_[0]){$s{$_}++}%s}

```
> 2 votes

# Answer
## D (87 chars)

reads from a passed in file and uses binary reads like migimaru's php function

```
import std.stdio;int[] f(File i){int[256] r;foreach(c;i.byChunk(1))r[c[0]]++;return r;}

```
> 1 votes

# Answer
# Ruby, 41

```
F=->f{h=Hash.new 0
f.chars{|c|h[c]+=1}
h}

```
> 1 votes

# Answer
## J - 26 characters (or perhaps 20)

The 26-character count is for the line that defines the function `f`.

```
NB. f takes a boxed filename,
NB. returns an array of integers counting occurrences of each character
NB. 26 characters

f=.[:<:[:+/"1[:=[:a.&,1!:1

NB. apply f to the file argument in jconsole textstats.ijs filename
A =. f 2{ARGV

NB. set output parameters so none of A gets elided
9!:37]0,~0,2#+:#0":A

NB. output A
exit echo A

```

Along the lines of Harry K.'s commentary, if we interpret the question to be about the function that computes the statistics, not also about I/O, `f` can go down to 20 characters:

```
f=.[:<:[:+/"1[:=a.&,

A =. f 1!:1]2{ARGV

```

`f` (in its shorter form) works like this:

`a.&,` : bond (via `&`) the alphabet `a.` (all characters J knows, in collating order) as the left argument to `,` (append); `f`'s argument is the right argument to append

`=` : "self classify": this gives us a table where each row corresponds to a unique element of the argument (which is the result of "`a. ,` *arg* ") and each column is 1 if that row's element appears in the same column of the argument, otherwise 0. For example, row 65 would have a 1 wherever an A appears at the same offset in the input.

`[:` in the context here lets us use `=` in its monadic (unary) sense, instead of of its dyadic/binary "equals" usage.

`+/"1` : `+/` applies addition between each pair of items, and `"1` makes it do so for the items in each row, instead of using the rows themselves as the items. The result is each row becomes a count from the input of the character corresponding to the row.

`<:` : decrement all those counts, because they include the alphabet itself (`a.`).
> 1 votes

# Answer
Accepting the assumption that the problem doesn't specify how the characters are read (according to Peter Taylor's comment on Alexander Bakulin's C suggestion) and assuming they are already read into a global array s, we can further reduce the C code in a portable way, by defining a function that accepts as an argument an already initialized char frequency table u\[256\], updates it and returns a pointer to it, like this:

# **C - 39 chars (or 24 chars... see Edit below)**

```
*r(int*u){while(*s)u[*s++]++;return u;}

```

And here is a sample, ungolfed program using the above function:

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

// function selector
#define R_MORE_CHARS    0

// globals
int*s, u[256];

// ------------------------------------------------------------------------------------
#if R_MORE_CHARS
    *r(int*u){while(*s)u[*s++]++;return u;}
#else
    r(){while(*s)u[*s++]++;}
#endif
// ------------------------------------------------------------------------------------
int *read_file(char *fname, int maxfsize)
{
    int i, *s_ = calloc(maxfsize, sizeof(int));
    if ( !s_ )
        return NULL;

    FILE *fp = fopen(fname, "r");
    if ( !fp )
        return NULL;

    for (i=0; i < maxfsize && (s_[i]= getc(fp)) != EOF; i++)
        ;
    s_[i] = 0;

    fclose(fp);

    return s_;
}
// ------------------------------------------------------------------------------------
void print_freq( int freq[256] )
{
    int i=0;
    for (; i<256; i++)
        if ( freq[i] )
            printf("ACII(%3d): %3d time(s)\n", i, freq[i]);
    return;
}
// ------------------------------------------------------------------------------------
int main( void )
{
    int *p;                 // for saving address of s
    p = s = read_file("lorem.txt", 2000);   // get file contents into global s
    if ( !s )
        return 1;

#if R_MORE_CHARS
    print_freq( r(u) );         // print updated frequency table
    puts("\tmore chars: *r(int*u){while(*s)u[*s++]++;return u;}");
#else
    r();                    // update frequency table
    print_freq( u );
    puts("\tless chars: r(){while(*s)u[*s++]++;}");
#endif

    free( p );              // free saved s
    return 0;
}

```

**EDIT**: Just thought that if we are to adjust the not so well defined problem to the language features, we could also completely skip the function arguments, working directly on the globals instead. Since in C we don't even need to return anything for the frequency table to get updated, the function can be further reduced down to 24 chars (i have also edited the sample program above, so now it can be used with either of those 2 functions...

# **C - 24 chars**

```
r(){while(*s)u[*s++]++;}

```
> 1 votes

# Answer
## Haskell, 2^6 characters

```
import List
f=fmap(map(\x->(x!!0,length x)).group.sort).readFile

```
> 1 votes

# Answer
### scala 164 156

```
val m=collection.mutable.Map[Char,Int]()
io.Source.fromFile("f").toArray.foreach(c=>m.update(c,m.getOrElseUpdate(c,0)+1))
m.mkString("\n")

```

Result:

```
> -> 1
+ -> 1
_ -> 1
{ -> 1
p -> 29
P -> 4
q -> 10
V -> 4
; -> 1
v -> 20

```

truncated to 10 lines.
> 1 votes

# Answer
**Python 102 54 48 (87 79 78 with I/O)**

As a pretty much newbie at this, and ignoring I/O:

Edit: Finding out about Counter made a difference:

```
from collections import*
r = Counter(s)
print(r)

```

The output is definitely not pretty though:

```
Counter({' ': 258, 'i': 155, 'e': 142, 's': 123,

```

Reading from file (removing a space between open() and "as" shaved one character):

```
from collections import*
with open("f")as f:
 s=f.read()
r=Counter(s)
print(r)

```

which generates the same output as the above example. I don't think I can get it smaller now, but there could be some function I've yet to explore.

Older solution:

```
import collections

d = collections.defaultdict(int)
for c in thestring:
    d[c] += 1

```

The counting itself can probably be made shorter through some function I've not encountered/understood yet. I realize it's pretty much cheating by omitting the I/O part, but I'm going to hide behind my newbie tag for a while longer.
> 1 votes

# Answer
## JavaScript, 55

Since JS can't read files, I'll assume that `file` is a function that returns the file as a string. (Requires Firefox!)

```
Array.reduce(file(),function(A,b)(A[b]=A[b]+1||1,A),{})

```
> 0 votes

---
Tags: code-golf
---


title: Fast line drawing algorithm

text:
# Question
Title: Fast line drawing algorithm
The task is to find a way to draw a horizontal line in an array of 16-bit integers.

We're assuming a 256x192 pixel array with 16 pixels per word. A line is a contiguous run of set (1) bits. Lines can start in the middle of any word, overlap any other words, and end in any word; they may also start and end in the same word. They may not wrap on to the next line. Hint: the middle words are easy - just write 0xffff, but the edges will be tricky, as will handling the case for the start and end in the same word. A function/procedure/routine must take an x0 and x1 coordinate indicating the horizontal start and stop points, as well as a y coordinate.

I exclude myself from this because I designed a nearly identical algorithm myself for an embedded processor but I'm curious how others would go about it. Bonus points for using relatively fast operations (for example, a 64 bit multiply or floating point operation wouldn't be fast on an embedded machine but a simple bit shift would be.)

# Answer
This code assumes that both x0 and x1 are inclusive endpoints, and that words are little endian (i.e. the (0,0) pixel can be set with `array[0][0]|=1`).

```
int line(word *array, int x0, int x1, int y) {
  word *line = array + (y << 4);
  word *start = line + (x0 >> 4);
  word *end = line + (x1 >> 4);
  word start_mask = (word)-1 << (x0 & 15);
  word end_mask = (unsigned word)-1 >> (15 - (x1 & 15));
  if (start == end) {
    *start |= start_mask & end_mask;
  } else {
    *start |= start_mask;
    *end |= end_mask;
    for (word *p = start + 1; p < end; p++) *p = (word)-1;
  }
}

```
> 3 votes

# Answer
## Python

The main trick here is to use a lookup table to store bitmasks of the pixels. This saves a few operations. A 1kB table is not that large even for an embedded platform these days

If space is really tight, for the price of a couple of &0xf the lookup table can be reduced to just 64B

This code is in Python, but would be simple to port to any language that supports bit operations.

If using C, you could consider unwinding the loop using the `switch` from Duff's device. Since the line is maximum of 16 words wide, I would extend the `switch` to 14 lines and dispense with the `while` altogether.

```
T=[65535, 32767, 16383, 8191, 4095, 2047, 1023, 511,
   255, 127, 63, 31, 15, 7, 3, 1]*16
U=[32768, 49152, 57344, 61440, 63488, 64512, 65024, 65280,
   65408, 65472, 65504, 65520, 65528, 65532, 65534, 65535]*16

def drawline(x1,x2,y):
    y_=y<<4
    x1_=y_+(x1>>4)
    x2_=y_+(x2>>4)
    if x1_==x2_:
        buf[x1_]|=T[x1]&U[x2]
        return
    buf[x1_]|=T[x1]
    buf[x2_]|=U[x2]
    x1_+=+1
    while x1_<x2_:
        buf[x1_] = 0xffff
        x1_+=1

#### testing code ####

def clear():
    global buf
    buf=[0]*192*16

def render():
    for y in range(192):
        print "".join(bin(buf[(y<<4)+x])[2:].zfill(16) for x in range(16))

clear()
for y in range(0,192):
    drawline(y/2,y,y)
for x in range(10,200,6):
    drawline(x,x+2,0)
    drawline(x+3,x+5,1)
for y in range(-49,50):
    drawline(200-int((2500-y*y)**.5), 200+int((2500-y*y)**.5), y+60)
render()

```
> 2 votes

# Answer
Here is a C version of my Python answer using the switch statement instead of the while loop and reduced indexing by incrementing a pointer instead of the array index

The size of the lookup table can be substantially reduced by using T\[x1 & 0xf\] and U\[x2 & 0xf\] for a couple of extra instructions

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

unsigned short T[] = {0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001};

unsigned short U[] = {0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff};

unsigned short buf[192*16];

void clear(){
    int i;
    for (i=0; i<192*16; i++) buf[i]==0;
}

void render(){
    int x,y;
    for (y=0; y<192; y++){
        for (x=0; x<256; x++) printf("%d", (buf[(y<<4)+(x>>4)]>>(15-(x&15)))&1);
        printf("\n");
    }
}

void drawline(int x1, int x2, int y){
    int y_ = y<<4;
    int x1_ = y_+(x1>>4);
    int x2_ = y_+(x2>>4);
    unsigned short *p = buf+x1_;

    if (x1_==x2_){
        *p|=T[x1]&U[x2];
        return;
        }

    *p++|=T[x1];
    switch (x2_-x1_){
    case 14: *p++ = 0xffff;
    case 13: *p++ = 0xffff;
    case 12: *p++ = 0xffff;
    case 11: *p++ = 0xffff;
    case 10: *p++ = 0xffff;
    case 9: *p++ = 0xffff;
    case 8: *p++ = 0xffff;
    case 7: *p++ = 0xffff;
    case 6: *p++ = 0xffff;
    case 5: *p++ = 0xffff;
    case 4: *p++ = 0xffff;
    case 3: *p++ = 0xffff;
    case 2: *p++ = 0xffff;
    case 1: *p++ = U[x2];
    }
}

int main(){
    int x,y;
    clear();

    for (y=0; y<192; y++){
        drawline(y/2,y,y);
    }

    for (x=10; x<200; x+=6){
        drawline(x,x+2,0);
        drawline(x+3,x+5,1);
    }

    for (y=-49; y<50; y++){
        x = sqrt(2500-y*y);
        drawline(200-x, 200+x, y+60);
    }
    render();
    return 0;
    }

```
> 1 votes

# Answer
## Scala,  7s / 1M lines 4.1s / 1M lines

```
// declaration and initialisation of an empty field:
val field = Array.ofDim[Short] (192, 16)

```

first implementation:

```
// util-method: set a single Bit:
def setBit (x: Int, y: Int) =
  field (y)(x/16) = (field (y)(x/16) | (1 << (15 - (x % 16)))).toShort
def line (x0: Int, x1: Int, y: Int) =
  (x0 to x1) foreach (setBit (_ , y))

```

After eliminating the inner method call, and replacing the for- with a while-loop, on my 2Ghz Single Core with Scala 2.8 it absolves 1 Mio. Lines in 4.1s sec. instead of initial 7s.

```
  def line (x0: Int, x1: Int, y: Int) = {
    var x = x0
    while (x < x1) {
      field (y)(x/16) = (field (y)(x/16) | (1 << (15 - (x % 16)))).toShort
      x += 1
    }
  }

```

Testcode and invocation:

```
// sample invocation:
line (12, 39, 3)
// verification
def shortprint (s: Short) = s.toBinaryString.length match {
  case 16 => s.toBinaryString
  case 32 => s.toBinaryString.substring (16)
  case x  => ("0000000000000000".substring (x) + s.toBinaryString)}

field (3).take (5).foreach (s=> println (shortprint (s)))
// result:
0000000000001111
1111111111111111
1111111100000000
0000000000000000
0000000000000000

```

Performance testing:

```
  val r = util.Random

  def testrow () {
    val a = r.nextInt (256)
    val b = r.nextInt (256)
    if (a < b)
      line (a, b, r.nextInt (192)) else
        line (b, a, r.nextInt (192))
  }

  def test (count: Int): Unit = {
    for (n <- (0 to count))
      testrow ()
  }

  // 1 mio tests
  test (1000*1000)

```

Tested with the unix tool time, comparing the user-time, including startup-time, compiled code, no JVM-start-up phase.

Increasing the number of lines shows, that for every new million, it needs an extra 3.3s.
> 1 votes

---
Tags: fastest-code
---


title: Generate a JavaDoc comment

text:
# Question
Title: Generate a JavaDoc comment
I'm too lazy to write a JavaDoc comment myself, there's a lot of typing and it is mostly boilerplate. Write a program to generate a JavaDoc comment with `$` as a placeholder given a method specification.

Example input:

```
Integer method(int arg1, String arg2) throws InvalidArgumentException, NullPointerException

```

Example output:

```
/**
    $
@param arg1 $
@param arg2 $
@return $
@throws InvalidArgumentException $
@throws NullPointerException $
*/

```

Some notes:

* There won't be any `static`, `private`, or other qualifier on the method, just the return type.
* There should be no `@return` tag if the return type is `void`.
* It is possible that there won't be any `throws` clause.
* You should accept the one-line method spec on stdin and write the result to stdout.

Shortest code wins.

# Answer
> 1 votes
## Ruby, 177 182 186

```
a,e=gets.split /\bthrows\b/
a=a.split /[\s(),]+/
puts'/**
    $',3.step(a.size,2).map{|i|"@param #{a[i]} $"},a[0]=='void'?[]:'@return $',e ?e.scan(/\w+/).map{|x|"@throws #{x} $"}:[],'*/'

```

# Answer
> 2 votes
### PowerShell, 209 ~~213~~

```
'/**
    $'
($i="$input")-replace'.*\( *| *\).*'-split','-ne''|%{"@param $((-split$_)[1]) $"}
,'@return $'*!($i-clike'void *')
if($i-match'\) *t'){$i-replace'.*\) *throws *'-split' *, *'|%{"@throws $_ $"}}'*/'

```

bash and PowerShell test scripts. but I'm probably missing a few cases still. But 22 tests are better than only one example, I guess :-)

# Answer
> 2 votes
**Perl 5.14 - 192 bytes**

```
#!perl -n
print'/**
    $
';@F=split/\(|\) throws +|\)/;print"\@param $_ \$
"for values{split/[, ]+/,$F[1]};print(($F[0]!~/^void /?'@return $
':''),(map{"\@throws $_ \$
"}$F[2]=~/\w+/g),"*/")

```

# Answer
> 0 votes
### scala 579:

```
import scala.util.parsing.combinator._
object M extends JavaTokenParsers{def i=ident
type P=Parser[Any]
def r:P=n~"("~rep(p)~")"~opt("throws"~rep(t))^^(s=>"\n/**\n    $"+s._1._1._2.mkString("")+s._1._1._1+"\n2:"+(s._2.getOrElse(""))+"\n*/")
def n:P=i~i^^(s=>if(s._1=="void")""else"\nreturn $")
def p:P=i~i~opt(",")^^(s=>("\n@param "+s._1._2+" $"))
def t:P=i~opt(",")^^(s=>("\n@throws "+s._1+" $"))
def main (args:Array[String])={val i=parseAll(r,readLine())
println(i.toString().replaceAll(".:.*","").replaceAll("[~(),]","").replaceAll("^[\\[].*","").replaceAll ("\n\n","\n"))}}

```

I'm sorry, I'm not experienced with TokenParsers. I guess I'm doing it wrong, and there is much room for improvement.

---
Tags: code-golf
---


title: Write Buggy Code

text:
# Question
Title: Write Buggy Code
Now is the time to show off your abilities to write bad code. I am trying out a new sort of programming puzzle, most similar, I think, to the underhanded C contest. The main difference is that this is not nearly as nefarious: it's just some good clean fun. The goal of the puzzle is to pack as many bugs as you can into a program. The winner of this contest is the one who writes the program with the most bugs per character.

To avoid a huge thread of comments asking for clarification, I should define right now what I consider to be qualifying bugs.

First, **a bug is not an error**. If it is a problem that can be detected by the interpreter as an error (e.g. mismatched delimeters, badly-formed syntax, acessing a property of a null object, etc.) or if it prevents the program from executing or continuing, it is not a bug. Otherwise, you could type in four characters and the interpreter could list eight syntax errors and you could claim a bug-character ratio of 2.

Second, **the bug must not be obviously wrong** and **a bug is not an easter egg**. This is certainly a subjective criterion, but I think essential to this sort of contest. This means that you cannot have conditional code that specifically mangles the code in obvious ways. (Read: use a turing pit language, because nobody will know the difference).

Third, **the bug must be plausible**. This is subjective, like the one above, but the bug must look like it could have been written by a less-than-meticulous or perhaps ignorant person, or someone who just made a mistake. This includes, for example, off-by-one errors or syntax that is valid and looks correct but causes undesired behavior (say, using square brackets instead of parentheses).

The bug can cause any sort of undesired behavior to the program, including, but certainly not limited to, undesired output for some exceptional cases, have different behavior based on something that is seemingly unrelated (e.g. output displays differently depending on whether the current time ends with an odd or even number of seconds), memory leaks, loss of data, and so on.

Example Problem:

Make a program that displays all of the ASCII characters in ascending order of their numerical value.

Example answer:

Brainf\***, 5 chars, 1 bug, 0.2 bug-char ratio

```
+[+.]

```

Bug: does not display the ASCII character for 1. Could be fixed by changing to `.+[.+]`.

Ok, I think you should mostly have gotten it by now, here is your puzzle:

## Decode a Caesar Cipher and Sort the Words Alphabetically

A caesar cipher is created by taking a series of letters and shifting them *n* letters over in the alphabet. If it goes all the way to the beginning or end of the alphabet, A comes after Z, and Z comes before A. For example:

```
Mannequin
Nboofrvjo //Shifted over 1 or -25
Wkxxoaesx //Shifted over 10 -16
Ftggxjnbg //Shifted over -7 or 19

```

You will be given two inputs (you can get input however is most convenient for you, within reason). The first input is the words, and the second input is the value it is shifted over. Your task is to output the decoded words, and then output the decoded words after they have been sorted alphabetically.

Example (no offense to bad boys, it's just an example):

> First input: gtdx wjbfwiji. ljy Gfi hfssty
>
> Second input: 5
>
> First output: boys rewarded. get Bad cannot
>
> Second output: Bad boys cannot get rewarded.

Good luck!

# Answer
## Ruby, 136 characters, 7 bugs, ratio = 0.051

```
o=gets[/\d+/].to_i
$,='\s'
a=gets.split(/ /).map{|w|w.gsub(/[^.,:;?!]/){(97+($&.ord-97-o)%26).chr}}
print a.join,a.sort_by{|a|a[0]}.join

```
1. `[/\d+/]`: negative numbers have their sign removed (a seeming attempt at input validation)
2. `'\s'`: backlash escapes are only interpreted within double-quoted strings, so this won't generate a space but rather a literal `\s`
3. `split(/ /)`: unlike a plain `split`, this won't split on newlines (so the last word will keep the newline)
4. `/[^.,:;?!]/`: this regex excludes punctation, but not uppercase characters, digits or underscores, and, most critically, newlines
5. `97`: anything other than punctation or lowercase letters will get garbled
6. `sort_by{|a|a[0]}`: apparently the programmer didn't know about `sort`, and instead used this ridiculous method, which doesn't sort words starting with the same letter
7. `print`: unlike `puts`, doesn't print a newline between each argument (so the strings come out glued together)
> 15 votes

# Answer
I'm not going to accept my own answer, but I thought I would show you the ultimate buggy sorting decipherer. The great thing about it is I didn't even plan most of the bugs.

## Brainf\***: 483 chars, 11 bugs

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

```

Input:

```
5 gtdx wjbfwiji. ljy Gfi hfssty

```

Output:

```
bo_sre]arded)getBadcannot
adbo_scannotgetre]arded)

```

**List of bugs**:

Input/Display bugs:

1. Nonpositive numbers or numbers that are more than one digit break the program.
2. The decipherer does not make Z come before A. It just subtracts the ASCII character value.
3. Spaces appear as the ASCII ESC (27) character.
4. If the input is not terminated by a tab, the program does not continue after the input instructions.
5. The program has to be manually terminated. It will continually display the ESC character until stopped.
6. The program will break if the input file is not ASCII encoded.
7. The program does not display the first character of the sorted output.

Sorting bugs:

I implemented the sorting extremely naively.

5. The program breaks when the number of words does not equal 5.
6. The program breaks if the number of bytes of input exceeds 60.
7. The program can only sort correctly if the alphabetical order is identical to the example input.
8. The program adds extra spaces if any of the words are smaller than the example input and overwrites characters if any of the words are longer.

I have a bug-char ratio of **0.0228**. Admittedly, Joey beat me, but I take pride in the fact I only used 8 different characters in my program, and my bugs are much more critical.
> 9 votes

# Answer
## C - 224 characters, 2 bugs, 7 cases of undefined behavior

**Edit:** My assessment here is incorrect. Overflowing an unsigned integer is, in fact, well-defined in C. Moreover, comparison between signed and unsigned is well-defined too, but the compiler warns because the way it's defined may not be what you think.

```
m(char**a,char**b){return strcmp(*a,*b);}main(int c,char*v[]){unsigned i,j
,o;o=atoi(v[1])+19;for(i=2;i<c;i++)for(j=0;j<=strlen(v[i])-1;j++)v[i][j]=(
tolower(v[i][j])-o)%26+97;qsort(v,c,sizeof(v),m);for(i=2;i<c;puts(v[i++]));}

```

### Usage:

```
$ ./a.out 5 gtdx wjbfwiji ljy Gfi hfssty
bad
boys
cannot
get
rewarded

```

### Breakdown:

```
m(char**a,char**b){return strcmp(*a,*b);}
main(int c,char*v[])
{
    unsigned i,j,o;

    // Undefined behavior if o is assigned negative value.
    o=atoi(v[1])+19;

    // Comparison between signed and unsigned integer.
    for(i=2;i<c;i++)
        // * Bug: if strlen(v[i]) is zero, subtraction will overflow
        //        unsigned value, and loop will have extra iterations.
        // * strlen is implicitly declared.
        //   Undefined behavior if sizeof(void*) != sizeof(int)
        for(j=0;j<=strlen(v[i])-1;j++)
            // tolower expects either an unsigned char casted to an int, or EOF.
            // Thus, undefined behavior if v[i][j] is non-ASCII.
            v[i][j]=(tolower(v[i][j])-o)%26+97;

    // * Bug: Program name and offset are included in the sort.
    //        "./a.out" and "5" both happen to be less than lowercase strings.
    // * qsort is implicitly declared.
    //   Undefined behavior if sizeof(void*) != sizeof(int)
    qsort(v,c,sizeof(v),m);

    // Comparison between signed and unsigned integer.
    for(i=2;i<c;puts(v[i++]));
}

```
> 7 votes

# Answer
## JavaScript: 403 characters, 8 bugs, ratio = 0.0199

Although not as bad as C, JavaScript does have design flaws that can lead to bugs, at least when used by a novice (demo with all bugs unfixed).

```
function W(v){D.write("<input value="+v+">");return D.body.lastChild}function R(J){I=S.indexOf(C=i.value[J]);H=s.value;if(!I){o.value+=C}if(H>0){o.value+=S[I+H]}if(H<0){o.value+=S[I-26-H]}p.value=o.value.split(" ").sort().join(" ");setTimeout("R("+(J+1)+")",99)}D=document;S="ZYXWVUTSRQPONMLKJIHGFEDCBA";S+=S;S+=S.toLowerCase();i=W("input");s=W("shift");W("run type=button onclick=R(0)");o=W("");p=W("")

```

---

```
function W(v) {
    D.write('<input value=' + v + '>');
    return D.body.lastChild;
}

function R(J) {
    I = S.indexOf(C = i.value[J]);
    H = s.value;
    if(!I) o.value += C;
    if(H > 0) o.value += S[I + H];
    if(H < 0) o.value += S[I - 26 - H];
    p.value = o.value.split(' ').sort().join(' ');
    setTimeout('R(' + (J + 1) + ')', 99);
}

D = document;

S = 'ZYXWVUTSRQPONMLKJIHGFEDCBA';
S += S;
S += S.toLowerCase();

i = W('input');
s = W('shift');
W('run type=button onclick=R(0)');
o = W('');
p = W('');

```

---

1. `I + H` is string concatenation, not addition: `undefinedundefinedundefined...`
2. `!I` is not the correct way to check the return value of `.indexOf()`, which returns -1 for a non-match: `boysVrewardedVV...`
3. Missing `else` keywords: `boys Vrewarded.V Vget...`
4. Will not stop at end of input: `...cannotundefinedundefined...`
5. Won't correctly handle zero shift (e.g. just trying to use the program to sort words)
6. Will it handle a negative shift? Not correctly.
7. Double-clicking the button causes a second timeout to start, leading to incorrect output (demo with most of the previous bugs fixed):
`boys rebwoayrsd erde.w agredte dB.a dg ecta nBnaodt cannot`.
8. Output text boxes must be empty when the button is clicked

Also note that this will not work on older versions of IE because it uses an extension to ECMAScript 3 that was only standardized in ES5.
> 5 votes

# Answer
**Python3 184 characters, 4 bugs. Bug ratio 0,0217**

```
import string
d=input()
y=int(input())
print("".join(sorted(d.translate(str.maketrans("".join([chr(x)for x in range(96,123)]),"".join([chr(96+(x+y)%26)for x in range(26)]))).split())))

```

degolfed:

```
data = input() #string to convert
y = int(input()) #value to shift
print("".join(
    sorted(
        data.translate(
            str.maketrans(
                "".join([chr(x) for x in range(96,123)]),
                "".join([chr(96+(x+y)%26) for x in range(26)]))
            ).split()
        )))

```

Example input: gtdx wjbfwiji. ljy Gfi hfssty
Example input: -5
Example output: G`canxrb`mmnsfdsqdv\`qcdc.

Known bugs:

1. Does not convert upper-case characters
2. Includes \` and converts to/from it.
3. Does not convert non-ascii characters (åäö)
4. Does not print spaces.
5. Can handle, but ignores, punctuation -- I choose not to count this, but if I do my ratio goes to 0.027)

I'm not very good at coming up with bugs deliberately.
> 1 votes

---
Tags: code-challenge, cryptography
---


title: Lights Out - Find the solution

text:
# Question
Title: Lights Out - Find the solution
(This code golf task is related to Code-Golf: Lights Off!. The same puzzle is used, but the task is different.)

---

## Introduction

"Lights Out" is a puzzle in which you should switch off all lights in a 5x5 grid. However, when you swap a light from on to off, or from off to on, the four adjacent lights will swap as well!

For example, consider the following grid, in which `1` stands for a light switched on and `0` stands for a light switched off:

```
00000
00000
00110
01000
00101

```

Now, if you try to turn the light at row 4, column 2 off, the resulting map will be:

```
00000
00000
01110
10100
01101

```

The goal of this game is to turn all lights off. You are allowed to switch certain lights on if that helps you to find the solution, as the adjacent ones will swap as well, which makes it possible to switch others off. This is almost always required to find the solution in fact!

## Description

Your task is to find out, given an input grid, which lights should be swapped to switch all lights off. Which ones to swap is enough information to solve the puzzle, because due to the swapping the amount does not matter (you can always do `mod 2` so it will be `0` (effectively, don't swap) or `1` (effectively, do swap)), and the order of swapping does not matter either obviously.

## Input

Input is a two dimensional array of lengths 5 (`5x5`) which represents the grid, in which:

* `0` stands for a light switched off
* `1` stands for a light switched on

## Output

Output is another two dimensional array of lengths 5 (`5x5`) which represents which lights to swap to switch all lights off in the grid, in which:

* `0` stands for 'this light should not be swapped'
* `1` stands for 'this light should be swapped'

## Winning condition

Shortest code wins.

## Hints

There are several algorithms to find the solution. There are mathematical articles about this game available on the Internet.

## Important notice

Sometimes multiple solutions are possible. It depends on the algorithm what solution you'll end up with. If you have different but correct solutions to the examples below, your entry obviously is correct as well.

## Examples

Example 1 (video to illustrate):

```
Input:     Output:

00000      00000
00000      00000
00110      00000
01000      00110
00101      00001

```

Example 2 (video to illustrate):

```
Input:     Output:

11111      11000
11111      11011
11111      00111
11111      01110
11111      01101

```

# Answer
> 4 votes
## Ruby (130) (121) (113) (102)

EDIT: Saved 9 characters, thanks to Howard.

EDIT 2: Another 8 characters, courtesy of Howard.

EDIT 3: Saved 11 more characters after learning how to use Ruby's % operator for sprintf.

```
b=(0..4).map{gets.to_i 2}
32.times{|x|z=0;k=b.map{|i|x=z^i^31&(x<<1^x>>1)^z=x;'%05b'%z}
puts k if x<1}

```

Accepts 5 lines of input from stdin. Outputs all solutions as 5x5 grids as specified, though there are no extra line breaks between solutions (or between the input and the solutions).

Solutions are found by iterating through all 32 possibilities for the top row, since the top row determines the switches that must be flipped in the following rows.

Input:

```
00000
00000
00110
01000
00101

```

Output:

```
00000
00000
00000
00110
00001
01110
10101
11011
10011
01111
10101
10101
00000
10011
10100
11011
00000
11011
00110
11010

```

# Answer
> 1 votes
### Ruby, 133 characters

```
t=->z,v,s{v<0?z&33814345664<1&&s :t[z,v-1,s+?0]||t[z^4321<<(v+v/5),v-1,s+?1]}
puts t[32*$<.read.tr(?\n,?0).to_i(2),24,''].scan /.{5}/

```

This is a brute-force search through all possible on/off combinations. The input must be specified on stdin with exactly five lines of five 0/1 characters each and a newline after each one, e.g.:

```
> ruby lights.rb
11111
11111
11011
11111
11111
^Z
00000
11111
10001
11111
00000

```

# Answer
> 0 votes
## F#

brute-force, will golf later

```
open System;
let a = Array2D.create 5 5 false
let b = Array2D.create 5 5 false

for i = 0 to 4 do
  for j = 0 to 4 do
    a.[i, j] <- if Console.Read() = 49 then true else false
  Console.ReadLine() |> ignore

let r = Random()
while Seq.cast a |> Seq.exists id do
  let x, y = r.Next(5), r.Next(5)
  b.[x, y] <- not b.[x, y]
  for u, v in [ x, y;
                x - 1, y;
                x + 1, y;
                x, y - 1;
                x, y + 1 ] do
    try
      a.[u, v] <- not a.[u, v]
    with
    | _ -> ()

printfn "%s" (let mutable z = ""
              for i = 0 to 4 do
                for j = 0 to 4 do
                  z <- z + (if b.[i, j] then "1" else "0")
                z <- z + "\n"
              z)

```

---
Tags: code-golf, puzzle-solver, grid
---


# Question
Title: How to encode shortest brainf_ck strings
This is an interesting one.

I have written a short program in objective-c to encode a string into a brainf\_ck string, this is what it looks like:

```
NSString *input; // set this to your input string
NSMutableString *output = [[NSMutableString alloc] init];
int currentPosition = 0;
for (int i = 0; i<[input length]; i++) {
    int charPos = [input characterAtIndex:i];
    int amountToGo = charPos-currentPosition;
    if (amountToGo > 0) {
        for (int b = 0; b<amountToGo; b++) {
            [output appendString:@"+"];
        }
    }
    else {
        int posVal = abs(amountToGo);
        for (int b = 0; b<posVal; b++) {
            [output appendString:@"-"];
        }
    }
    currentPosition += amountToGo;
    [output appendString:@"."];
}
NSLog(@"%@", output);
[output release];

```

Now I could ask you to optimize that code.

Or, I could ask you to optimize the bf code it produces?

**EXAMPLE:** Output of 'Hello World!' from my code (**365** chars)

> ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++.+++++++..+++.-------------------------------------------------------------------------------.+++++++++++++++++++++++++++++++++++++++++++++++++++++++.++++++++++++++++++++++++.+++.------.--------.-------------------------------------------------------------------.

**EXAMPLE 2:** Now, looking at that code, I could probably shorten it by putting reset to zeros in, for a start... (**290** chars - **75** improvement)

> ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++.+++++++..+++.\[-\]++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++++++++++++++++++++++++++++.++++++++++++++++++++++++.+++.------.--------.\[-\]+++++++++++++++++++++++++++++++++.

But this takes it a step further... output of 'Hello World!' from some sample code I found on the internet: (**111** chars, **179** on last, **254** on original!)

> ++++++++++\[\>+++++++\>++++++++++\>+++\>+\<\<\<\<-\]\>++.\>+.+++++++..+++.\>++.\<\<+++++++++++++++.\>.+++.------.--------.\>+.\>.

Now, I don't know how that loop works, but it does. My question is this:

1. Explain how the loop in the last example works.
2. Write some code that can turn *any* string into highly optimized brainf\_ck, like the last example.

# Answer
> 1 votes
I can give question number 1. a go:

```
++++++++++

```

The first series of +'s defines first memory cell (cell0) to be a loop counter to 10.

```
[>+++++++>++++++++++>+++>+<<<<-]

```

Above is the loop that executes 10 times. The loop adds 7 to cell1, 10 to cell2, 3 to cell3 and 1 to cell4 for each iteration. After 10 iterations we have the following in the first 5 memory cells: 0, 70, 100, 21, 10

```
>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

```

Above is kind of self explanatory, it just moves the memory pointer to the value that is closest to what is needed, does some minor inc's and dec's and outputs.

---
Tags: brainfuck, metagolf, optimized-output
---


title: Tricky Median Question

text:
# Question
Title: Tricky Median Question
Given n points, choose a point in the given list such that the sum of distances to this point is minimum ,compared to all others.

Distance is measured in the following manner.

For a point (x,y) all 8 adjacent points have distance 1.

```
(x+1,y)(x+1,y+1),(x+1,y-1),(x,y+1),(x,y-1),(x-1,y)(x-1,y+1),(x-1,y-1)

```

**EDIT**

More clearer explanation.

A function foo is defined as

```
foo(point_a,point_b) = max(abs(point_a.x - point_b.x),abs(point_a.y - point_b.y))

```

Find a point x such that sum(\[foo(x,y) for y in list\_of\_points\]) is minimum.

Example

**Input:**

```
0 1
2 5
3 1
4 0

```

**Output**

```
3 1

```

Eg: Distance between (4,5) and 6,7) is 2.

This can be done in O(n^2) time, by checking the sum of each pair. Is there any better algorithm to do it?

# Answer
> 2 votes
I can imagine a scheme better than O(n^2), at least in the common case.

Build a quadtree out of your input points. For each node in the tree, compute the number and average position of the points within that node. Then for each point, you can use the quadtree to compute its distance to all other points in less than O(n) time. If you're computing the distance from a point p to a distant quadtree node v, and v doesn't overlap the 45 degree diagonals from p, then the total distance from p to all the points in v is easy to compute (for v which are more horizontally than vertically separated from p, it is just `v.num_points * |p.x - v.average.x|`, and similarly using y coordinates if v is predominately vertically seperated). If v overlaps one of the 45 degree diagonals, recurse on its components.

That should beat O(n^2), at least when you can find a balanced quadtree to represent your points.

# Answer
> 1 votes
## Python

```
def median(lst):
    """ sort of median of a list """
    return sorted(lst)[len(lst) / 2]

def median_point(points):
    xs = [point[0] for point in points]
    ys = [point[1] for point in points]
    return (median(xs), median(ys))

points = [
    (0, 1),
    (2, 5),
    (3, 1),
    (4, 0),
]

print median_point(points) # (3, 1)

```

It calculates the median of the x and y coordinates separately. I'm not positive that that's correct in all cases, but it kind of seems like it might be. It's O(n log n).

# Answer
> 0 votes
## Scala

```
object Median extends App
{
    var(xMin,yMin,xMax,yMax,a,x)=(100000000,100000000,-100000000,-100000000,"",Array.fill(2)(""))
    var points=Array((100000000,100000000))
    a=readLine
    while(a!=null)
    {
        x=a.split(" ")
        if(x(0).toInt<xMin)xMin=x(0).toInt
        if(x(1).toInt<yMin)yMin=x(1).toInt
        if(x(0).toInt>xMax)xMax=x(0).toInt
        if(x(1).toInt>yMax)yMax=x(1).toInt
        points=points:+((x(0).toInt,x(1).toInt))
        a=readLine
    }
    var middlex=(xMax-xMin)/2
    var middley=(yMax-yMin)/2

    var meanPoint=(100000000,100000000)
    var shortestDistance=100000000

    points.map(x=>
        {
            var s=(math.abs(x._1-middlex).max(math.abs(x._2-middley)))
            if(s<shortestDistance)
            {
                shortestDistance=s
                meanPoint=x
            }
        })

    println(meanPoint)
}

```

Takes in the points, keeping track of the highest and lowest values of `x` and `y`.
Uses those values to find the midpoint of the square defined by `xMin`,`yMin`,`xMax`,`yMax`.
Finds the point with the shortest distance to that midpoint.

Never was very good with that Big O business, so I couldn't tell you what it is for this algorithm.

# Answer
> 0 votes
## Haskell, 136 characters

```
main=interact$show.n.q.map read.words
n x=snd$minimum$map(\p@(a,b)->(sum$map(\(x,y)->max(abs$a-x)$abs$b-y)x,p))x
q[]=[]
q(x:y:z)=(x,y):q z

```

---
Tags: fastest-algorithm
---