title: Solving Mastermind in 6 or less moves

text:
# Question
Title: Solving Mastermind in 6 or less moves
Your goal is to write a program that will solve any Mastermind puzzle in 6 or less moves.

### Background

Mastermind is a board game. The goal of the game is to exactly guess the combination (colours and order) of 4 coloured pegs hidden by the other player. When a guess is made, the other player responds with between 0 and 4 white and or red pegs. A red peg is where the colour and location are correct. A white peg is where the colour is represented in the remaining pieces, but is in the incorrect location. If there are duplicate colours in the guess, there will only be one peg awarded per corresponding colour in the secret. (So - if the secret contained 1 Blue, and the guess had 2 blues with one in the correct location, there would be one red peg given). There are 6 different colors, and duplicates may be used.

So for instance, a game might go as follows: (Assuming the solution is Red Green Green Blue)

```
1:  Blue Purple Black Green - 2 white pegs
2:  Green Red Black Blue    - 2 white pegs, 1 red peg
3:  Green Green Green Blue  - 3 red pegs
4:  Red Green Green Blue    - 4 red pegs

```

The rules are expanded on Wikipedia

### Requirements

* The program must read from stdin, and write to stdout
* I will be using numbers for simplicity instead of colors. The combination to guess will be 4 numbers between 1 and 6
* They must output their guesses as a series of 4 space separated numbers from 1 to 6 concluding with a newline. For instance:

1 5 2 2 \n
* The program will subsequently receive as input after its guess 2 integers between 0 and 4 separated by a space and concluding with a newline. The first will be the amount of white pegs, the second the amount of red pegs.
* On an input of "0 4" (4 red pegs), the program must terminate
* The program must be able to solve any puzzle in less then 6 turns (your program giving output, followed by the response input is 1 turn). There is no bonus (due to complexity of proof) for being able to solve it in less.
* The solution must be completely internal and included in the source. Standard Libraries only are permitted. The solution may therefore not rely on any other files (such as dictionaries), or the internet.

### Example Input/Output

```
> is your programs output
< is the responding input
Solution is 1 5 6 6

> 1 2 3 4
< 0 1
> 4 1 6 6
< 1 2
> 1 6 5 6
< 2 2
> 1 5 6 6
< 0 4

```

### Scoring

* This is pure and simple **Code Golf**. The shortest solution **in bytes** wins.

This is my first Code Golf question. My apologies if I have done something wrong, but I've attempted as well as possible to ensure that there is absolutely no ambiguity, and prevent as much rules lawyering as possible. If I have been ambiguous or unclear, please feel free to ask questions.

# Answer
# Python 2 Python 3, 359 365 338 chars

```
from itertools import*
from collections import*
m=h=set(product(*['123456']*4))
def f(g,k):b=sum(x==y for x,y in zip(g,k));return'%s %s'%(sum(min(g.count(c),k.count(c))for c in set(g))-b,b)
while len(m)>1:g=min(h,key=lambda g:max(Counter(f(g,k)for k in m).values()));print(*g);s=input();m=set(x for x in m if s==f(g,x))
print(*(m.pop()))

```

Funny, it took me many edits to realize I had a five character variable name.

I do not like the long imports. It feels like I should be able to implement a replacement for `collections.Counter` that would save the import.

I also do not like the `print(*(m.pop()))` at the end. It feels like it should disappear into the while loop, but I can't find a way to do it without making it longer.
> 8 votes

# Answer
## Haskell, 317 304

```
q[0,4]_=error""
q[n,m]l=(\s->all(==4-m)[g s,n+g(u(foldr((u((.drop 1).(++)).).break.(==)))$unzip s)]).c(u(/=)).zip l
u=uncurry;m=map;g=length;c=filter
f a=[head.c(($(zipWith q(take n a)$f a)).all.flip($)).sequence$replicate 4[1..6]|n<-[0..]]
main=interact$unlines.m(unwords.m show).f.m(m read.words).lines

```

I love writing purely functional interactive programs! But of course this style has certain limitations: it terminates now with an error, but you didn't specify that this is not ok. I'd need to refactor the whole thing into the `IO` monad to get a non-error exit.
> 7 votes

# Answer
## Python, 385 357 chars, Solves in 5 moves

The more I change it, it grows more and more like Steven Rumbalski's... The main difference is that he works with strings rather than integers.
Implemented Knuth's algorithm (correctly now, I hope).
Borrowed the scoring function from Steven Rumbalski.
It takes a long time to generate the first guess, gets better later.
Hard-coding it (`g=len(A)==1296 and [1,1,2,2] or ...`) makes life easier if you want to test it.
I don't count 4 newlines+tab pairs, which can be replaced by semicolons.

```
from collections import*
from itertools import*
a=B=A=list(product(*[range(1,7)]*4))
r=lambda g,k:(sum(x==y for x,y in zip(g,k)),sum(min(g.count(c),k.count(c))for c in set(g)))
while a!=4:
    g=A[1:]and min(B,key=lambda x:max(Counter(r(x,i)for i in A).values()))or A[0]
    print"%d "*4%tuple(g)
    b,a=map(int,raw_input().split())
    A=[x for x in A if r(g,x)==(a,a+b)]

```
> 5 votes

---
Tags: code-golf
---


# Question
Title: Generate number in reverse polish notation
Your task is to write a function which accepts a number N and creates a string of Reverse Polish Notation which will generate that number. Valid operations are:

```
1-9: Push number onto stack. Only 1-9 are allowed.
+-*/%: take two numbers from top of stack and apply arithmetic operation,
    pushing the result.
d: duplicate - push a copy of the top of the stack

```

That's all. For - / and % which are order dependent, the operand which was pushed first goes first. ie `63/ = 2` `63- = 3` and `64% = 2`

Entries are judged not by brevity of code, but by the size of the generated strings. The smaller the better. I also want to encourage pushing smaller numbers rather than bigger ones. The score for a number is calculated like so:

```
For any number pushed, add that number to the score.
For every operand (+-*/%d) add 1.

```

Your final score is the sum of your score for all numbers 0 to 10,000 inclusive. Lets go ahead and limit total running time to two minutes for all 10k, on a reasonable machine, to avoid too much brute forcing.

If you can do it only pushing 1s, go ahead and subtract 10% from your score.

# Answer
### Score 199503, Java solution

```
import java.util.HashMap;
import java.util.HashSet;

public class RPN {

    public static void main(String[] args) {
        // Loop to calculate total over all 10001 numbers as defined in puzzle
        int total = 0;
        System.out.println("n\tscore\trpn");
        for (int k = 0; k <= 10000; k++) {
            final String rpn = findRPN(k);
            final int scr = calcScore(rpn);
            System.out.println(k + "\t" + scr + "\t" + rpn);
            total += scr;
        }
        System.out.println("TOTAL: " + total);
    }

    // simple scoring calculator for a given rpn representation (ignores 10% bonus)
    private static int calcScore(String rpn) {
        int score = 0;
        for (char ch : rpn.toCharArray()) {
            if (Character.isDigit(ch)) {
                score += ch - '0';
            } else {
                score++;
            }
        }
        return score;
    }

    // hashmap caching intermediate results and all results for 0<=n<=10000
    final static int max = 6000000;
    final static HashMap<Integer, String> rpns = new HashMap<Integer, String>();

    // maximum score expected for numbers 0<=n<=10000
    final static int maxScore = 26;

    private static void preCalculate() {
        // hashmap which contains all numbers with a given score
        final HashMap<Integer, HashSet<Integer>> perScore = new HashMap<Integer, HashSet<Integer>>();

        // numbers are build by combining those with lower score
        for (int sc = 1; sc <= maxScore; sc++) {
            final HashSet<Integer> currentScore = new HashSet<Integer>();
            perScore.put(sc, currentScore);

            // 1-9 can be reached directly by pushing
            if (sc < 10 && !rpns.containsKey(sc)) {
                rpns.put(sc, Integer.toString(sc));
                currentScore.add(sc);
            }

            if (sc > 2) {
                // score is increased by 2 if appending "d+" or "d*" to an existing rpn
                for (int n : perScore.get(sc - 2)) {
                    String rpn_n = rpns.get(n);
                    consider(n * 2, currentScore, rpn_n, "d+");
                    consider(n * (long)n, currentScore, rpn_n, "d*");
                }
            }

            // another possibility to get score sc is to take two operands
            // with scores sc1 and sc2 and add another operator
            // with the requirement that sc1 + sc2 + 1 = sc
            for (int sc2 = 1; sc2 <= sc - 2; sc2++) {
                int sc1 = sc - sc2 - 1;
                HashSet<Integer> l1 = perScore.get(sc1);
                HashSet<Integer> l2 = perScore.get(sc2);

                // try all combinations of operators from list 1 and list 2
                // with each operator + - * / and %
                for (int n : l1) {
                    String rpn_n = rpns.get(n);
                    for (int m : l2) {
                        String prefix = rpn_n + rpns.get(m);

                        // Commutative operators - only need to consider them once
                        if (n < m) {
                            consider(n + m, currentScore, prefix, "+");
                            consider(n * (long)m, currentScore, prefix, "*");
                        }

                        // Non-commutative operators.
                        consider(n - m, currentScore, prefix, "-");
                        // div and mod only possible if m!=0
                        if (m != 0) {
                            consider(n / m, currentScore, prefix, "/");
                            consider(n % m, currentScore, prefix, "%");
                        }
                    }
                }
            }
        }
    }

    private static void consider(long value, HashSet<Integer> currentScore, String prefix, String suffix) {
        if (value < -max || value > max) return;
        Integer r = Integer.valueOf((int)value);
        if (!rpns.containsKey(r)) {
            rpns.put(r, prefix + suffix);
            currentScore.add(r);
        }
    }

    private static String findRPN(int number) {
        if (rpns.isEmpty()) {
            preCalculate();
        }

        // if number is negative try 1(-n+1)-
        if (number < 0) {
            return "1" + findRPN(-number + 1) + "-";
        }

        // if number not in precalculated list try number/2
        if (!rpns.containsKey(number)) {
            if (number % 2 == 0) {
                return findRPN(number / 2) + "d+";
            } else {
                return findRPN(number / 2) + "d+1+";
            }
        }

        // otherwise use cached result
        return rpns.get(number);
    }
}

```

The solution is pretty much optimized to get a good score within the defined range of numbers (i.e. 0 to 10000). It sacrifices non-optimal solutions outside the range for (hopefully) optimal representations within. Nevertheless it will still work for other numbers too.

I think the score given by that solution is very close to optimal although I'm not able to prove it.

**Output:**

```
n   score   rpn
0   3   11-
1   1   1
2   2   2
3   3   3
4   4   4
5   5   5
6   5   3d+
7   7   7
8   6   4d+
9   5   3d*
10  7   5d+
11  8   3d*2+
12  7   3d+d+
...
9990    19  5d+d*d*3d*-1-
9991    17  5d+d*d*3d*-
9992    18  5d*d+d*2-d+d+
9993    19  5d+d*d*3d+-1-
9994    17  5d+d*d*3d+-
9995    17  5d+d*d*5-
9996    16  5d+d*d*4-
9997    15  5d+d*d*3-
9998    14  5d+d*d*2-
9999    13  5d+d*d*1-
10000   11  5d+d*d*
TOTAL: 199503

```
> 4 votes

# Answer
## JavaScript, 217597

```
var minNum = new Uint32Array(10001), minMA = ['11-','1','2'];
minNum[0] = 3;
minNum[1] = 1;
minNum[2] = 2;
for(var tr=2,i=2,sum=0;i<=1e4;i++){
  var minVal=i<10?i:9e9,j,minMethod=i<10?''+i:'';
  if(tr*tr*tr==i){
    if(minNum[tr]+4<minVal) minVal=minNum[tr]+4,minMethod=minMA[tr]+"dd**";
    tr++;
  }
  for(j=1;j<10&&j<i;j++) if(minVal>minNum[i-j]+minNum[j]+1) minVal=minNum[i-j]+minNum[j]+1,minMethod=minMA[i-j]+minMA[j]+'+';
  if(i>2) for(j=2;j<10&&i>j;j++) if(i%j==0){
    if(minVal>minNum[i/j]+minNum[j]+1) minVal=minNum[i/j]+minNum[j]+1,minMethod=minMA[i/j]+minMA[j]+'*';
    if(minVal>minNum[i/j]+2*(j-1)){
      minVal=minNum[i/j]+2*(j-1);
      for(minMethod=minMA[i/j],dd='',pp='',k=j-1;k-->0;dd+='d',pp+='+'); minMethod+=dd+pp;
    }
  }
  for(j=10;j<Math.sqrt(i);j++) if(i%j==0){
    if(minVal>minNum[i/j]+minNum[j]+1) minVal=minNum[i/j]+minNum[j]+1,minMethod=minMA[i/j]+minMA[j]+'*';
    if(minVal>minNum[i/j]+2*(j-1)){
      minVal=minNum[i/j]+2*(j-1);
      for(minMethod=minMA[i/j],dd='',pp='',k=j-1;k-->0;dd+='d',pp+='+'); minMethod+=dd+pp;
    }
  }
  if(Math.sqrt(i)==~~Math.sqrt(i)) if(minVal>minNum[Math.sqrt(i)]+2) minVal=minNum[Math.sqrt(i)]+2,minMethod=minMA[Math.sqrt(i)]+'d*';
  minNum[i] = minVal; minMA[i] = minMethod;
  console.log(i,minVal,minMethod);
}
for(i=0;i<=10000;i++){
  sum+=minNum[i];
}
console.log("Score : "+sum);

```

Quite trivial solution... does not use `-`, `/`, and `%` at all.. :P

I can add the case for n^5, n^7, ..., but that doesn't reduce the score quite well (only ~400).

This problem reminds me of some PE problems... (not saying that this is a part of a PE problem)

```
2 2 "2"
3 3 "3"
4 4 "4"
5 5 "5"
6 5 "3d+"
7 7 "7"
8 6 "2dd**"
9 5 "3d*"
10 7 "3d*1+"
11 8 "3d*2+"
12 7 "3d+d+"
13 9 "3d+d+1+"
...
9990 25 "3d+d*1+3dd***5*d+"
9991 27 "3d+d*1+3dd***5*d+1+"
9992 27 "4d*d*3d+d*3+*2dd**+"
9993 26 "4d*d*3d+d*3+*3d*+"
9994 27 "4d*d*3d++1+3d+d*2+*"
9995 27 "3d+d*1+3dd***d+1+5*"
9996 23 "7d+d*5d*d+1+*"
9997 24 "4d*d*3*1+3d+d+1+*"
9998 26 "4d*d*3*1+3d+d+1+*1+"
9999 25 "3d*1+d*1+7d*d+1+*"
10000 11 "3d*1+d*d*"
Score : 217597

```
> 2 votes

# Answer
Here's my baseline solution in C#:

```
string Make(int n)
{
  if(n < 0) return "1" + Make(-n) + "1+-";
  if(n == 0) return "11-";
  if(n == 1) return "1";
  if(n % 2 == 0) return Make(n / 2) + "d+";
  return Make(n / 2) + "d+1+";
}

public void CalcTotal()
{
  var total = Enumerable.Range(0, 10001).Sum(x => Make(x).Length);
  Console.WriteLine(total);
}

```

Gets a score of `346491 - 10% = 311841.9`
> 0 votes

---
Tags: code-challenge, stack
---


title: Code Golf: Make a Web Crawler

text:
# Question
Title: Code Golf: Make a Web Crawler
A Web Crawler is a program that starts with a small list of websites and gets the source code for all of them. It then finds all the links in those source codes, gets the website it links to then puts them in a list. It then starts again but with the new list of websites.The main reason for a Web Crawler is to find all (or most) of the websites in the internet. Google use this to power their search engine.Wikipedia Page about Web Crawlers

Your task is to create a Web Crawler in any language you wish.

**Rules**

> * Your first list can contain any amount of websites \<= 5 and any websites you wish.
> * Your web crawler can ignore any websites with the HTTP GET request or any other pages other than the home page, e.g. www.somewebsite.com/?anything=1 and www.somewebsite.com/secondpage can be ignored, we are only trying to find the website/domain, e.g. www.somewebsite.com
> * You can use any method you wish to store the list of websites currently being "crawled".
> * Although this is code golf, the highest voted answer/solution will win, and don't forget to have fun!

# Answer
> 4 votes
**Javascript, 491**

Golfed

```
var C=function(c){w=c.length;for(i=0;i<w;i++){var b=new XMLHttpRequest;b.setRequestHeader("Access-Control-Allow-Origin","*");b.setRequestHeader("X-Requested-With","XMLHttpRequest");b.open("GET",c[i],!0);b.send();if(200===b.status){a=b.responseText.match(/\<[(a|img)]+\s[^\>]+[(http|https)]+:\/\/([\w\.])+([.])+.+?[^.]+?./gi);u=c[i].substr(7);re=RegExp(u,"i");for(j=0;j<a.length;j++)if(a[j].match(re)&&(b=a[j].match(/[(http|https)]+:\/\/([\w\.])+([.])/gi))&&!c.indexOf(b))c.push(a[j]),w++}}};

```

Un-Golfed

```
var C = function(s){
  w = s.length;
  for(i = 0; i < w; i++){
    var r = new XMLHttpRequest();
    r.setRequestHeader("Access-Control-Allow-Origin", "*")
    r.setRequestHeader("X-Requested-With", "XMLHttpRequest");
    r.open('GET', s[i], true); r.send();
    if(r.status === 200) {
      a = r.responseText.match(/\<[(a|img)]+\s[^\>]+[(http|https)]+:\/\/([\w\.])+([.])+.+?[^.]+?./gi);
      u = s[i].substr(7),
      re = new RegExp(u,'i');
      for(j = 0; j < a.length; j++){
        if(!a[j].match(re)) continue;
        var uri = a[j].match(/[(http|https)]+:\/\/([\w\.])+([.])/gi);
        if(uri && !s.indexOf(uri)) {
          s.push(a[j]); w++;
        }
      }
    }
  }
}

```

Method

```
var c = new C(['http://www.cnn.com', 'http://www.usatoday.com', 'http://www.huffingtonpost.com', 'http://www.drudgereport.com/', 'http://news.cnet.com']);

```

---
Tags: code-golf
---


title: Fill in the lakes, 2D

text:
# Question
Title: Fill in the lakes, 2D
The one-dimensional version of this problem was pretty easy, so here's a harder 2D version.

You are given a 2D array of land heights on standard input, and you have to figure out where the lakes will form when it rains. The height map is just a rectangular array of the numbers 0-9, inclusive.

```
8888888888
5664303498
6485322898
5675373666
7875555787

```

You must output the same array, replacing all locations that would be underwater with `*`.

```
8888888888
566*****98
6*85***898
5675*7*666
7875555787

```

Water can escape diagonally, so there would be no lake in this configuration:

```
888
838
388

```

shortest code wins. Your code must handle sizes up to 80 wide and 24 high.

Three more examples:

```
77777    77777
75657    7*6*7
75757 => 7*7*7
77677    77677
77477    77477

599999    599999
933339    9****9
936639 => 9*66*9
935539    9*55*9
932109    9****9
999999    999999

88888888    88888888
84482288    8**8**88
84452233 => 8**5**33
84482288    8**8**88
88888888    88888888

```

# Answer
## Haskell, 258 characters

```
a§b|a<b='*'|1<3=a
z=[-1..1]
l m=zipWith(§)m$(iterate(b.q)$b(\_ _->'9'))!!(w*h)where
 w=length m`div`h
 h=length$lines m
 q d i=max$minimum[d!!(i+x+w*y)|x<-z,y<-z]
 b f=zipWith(\n->n`divMod`w¶f n)[0..]m
 (j,i)¶g|0<i&&i<w-2&&0<j&&j<h-1=g|1<3=id
main=interact l

```

Example run:

```
$> runhaskell 2638-Lakes2D.hs <<TEST
> 8888888888
> 5664303498
> 6485322898
> 5675373666
> 7875555787
> TEST
8888888888
566*****98
6*85***898
5675*7*666
7875555787

```

Passes all unit tests. No arbitrary limits on size.

---

* Edit (281 → 258): don't test for stability, just iterate to the upper bound; stop passing constant argument `m`
> 7 votes

# Answer
## Python, ~~483~~ 491 characters

```
a=dict()
def s(n,x,y,R):
 R.add((x,y))
 r=range(-1,2)
 m=set([(x+i,y+j)for i in r for j in r if(i,j)!=(0,0)and(x+i,y+j)not in R])
 z=m-set(a.keys())
 if len(z)>0:return 1
 else:return sum(s(n,k[0],k[1],R)for k in[d for d in m-z if a[(d[0],d[1])]<=n])
i=[list(x)for x in input().strip().split('\n')]
h=len(i)
w=len(i[0])
e=range(0,w)
j=range(0,h)
for c in[(x,y)for x in e for y in j]:a[c]=int(i[c[1]][c[0]])
for y in j:print(''.join([('*',str(a[(x,y)]))[s(a[(x,y)],x,y,set())>0] for x in e]))

```

I'm pretty sure there's a better (and shorter) way of doing this
> 5 votes

# Answer
## Python, 478 471 characters

(Not including comments. 452 450 characters not including the imports.)

```
import sys,itertools
i=[list(x)for x in sys.stdin.read().strip().split('\n')]
h=len(i)
w=len(i[0])
n=h*w
b=n+1
e=range(h)
d=range(w)
# j is, at first, the adjancency matrix of the graph.
# The last vertex in j is the "drain" vertex.
j=[[[b,1][(t-r)**2+(v-c)**2<=1 and i[r][c]>=i[t][v]] for t in e for v in d]+[[b,1][max([r==0,r>h-2,c==0,c>w-2])]]for r in e for c in d]+[[0]*b]
r=range(b)
for k,l,m in itertools.product(r,repeat=3):
    # This is the Floyd-Warshall algorithm
    if j[l][k]+j[k][m]<j[l][m]:
        j[l][m]=j[l][k]+j[k][m]
# j is now the distance matrix for the graph.
for k in r:
    if j[k][-1]>n:
        # This means that vertex k is not connected to the "drain" vertex, and is therefore flooded.
        i[k/w][k-w*(k/w)]='*'
for r in e:print(''.join(i[r]))

```

The idea here is that I construct a directed graph where each grid cell has its own vertex (plus one additional "drain" vertex). There is an edge in the graph from each higher valued cell to its neighboring lower valued cells, plus there is an edge from all exterior cells to the "drain" vertex. I then use Floyd-Warshall to calculate which vertices are connected to the "drain" vertex; any vertices that are *not* connected will be flooded and are drawn with an asterisk.

I don't have much experience with condensing Python code, so there's probably a more succinct way I could have implemented this method.
> 4 votes

# Answer
## Common Lisp, 833

```
(defun drains (terr dm a b)
  (cond
    ((= (aref dm a b) 1) t)
    ((= (aref dm a b) -1) nil)
    ((or (= a 0) (= b 0)
     (= a (1- (array-dimension terr 0)))
     (= b (1- (array-dimension terr 1)))) t)
    (t (loop for x from -1 to 1
       do (loop for y from 0 to 1
           do (if (and (or (> x 0) (> y 0))
                   (drains terr dm (+ a x) (+ b y))
                   (<= (aref terr (+ a x) (+ b y))
                   (aref terr a b)))
              (progn
                (setf (aref dm a b) 1)
                (return-from drains t)))))
    (setf (aref dm a b) -1)
    nil)))

(defun doit (terr)
  (let ((dm (make-array (array-dimensions terr))))
    (loop for x from 0 to (- (array-dimension terr 0) 1)
       do (loop for y from 0 to (- (array-dimension terr 1) 1)
         do (format t "~a"
            (if (drains terr dm x y)
                (aref terr x y)
                "*"))
         finally (format t "~%")))))

```

No attempt has been made to golf this, I just found the problem interesting. Input is the 2D array of the map. The solution checks each square to see if it "drains" -- a square drains if it is on the outer edge or if it is adjacent to an equal or lower height square that drains. To keep from recursing endlessly, the code keeps a "drain map" (dm) where it stores the drainage status of squares that have already been determined.
> 3 votes

# Answer
## Python, 246 chars

```
import os
a=list(os.read(0,2e3))
w=a.index('\n')+1
a+=' '*w
def f(p,t):
    if e<a[p]or p in t:return
    t[p]=1
    return'*'>a[p]or any(f(p+d,t)for d in(~w,-w,-w+1,-1,1,w-1,w,w+1))
z=0
for e in a:
    if(' '<e)*~-f(z,{}):a[z]='*'
    z+=1
print''.join(a[:~w])

```

The solution works by doing a DFS from each position to determine whether or not to fill.

If trailing whitespace on each line is allowed, it may be shortened by using w=80 and padding the input lines with whitespace to 80 chars.
> 1 votes

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


# Question
Title: Create a multi-level 5x5x5 Labyrinth with only one solution
The aim of this challenge is to create the shortest code (in characters) that successfully do the following:

**Specifications**:

* Must create a `5x5x5 labyrinth` with exactly `1 possible solution` (no more, no less)
* ~~The labyrinth must be created `randomly`~~ It must be able to generate every existing solution if left running for years
* The `start` and `finish` must be placed in `*opposite corners`
* The map `output` must in one of the following formats:

**Option output format 1** `strings, printed or alerted`:

```
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx

```

**Option output format 2** `arrays`:

```
[[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx]]

```

**Output Notes:**

* Use `0` for `empty` and `1` for `squares`
* Break lines are *NOT* necessary
* You decide what `index` is what, but just make sure to *explain* it well

---

\*Here is an example of what I mean by opposite corners:

**Clarifications**:

* Can *NOT* move in `diagonal`
* Can *NOT* pass twice on the same path
* Having `inaccessible areas` is allowed
* You can `go up/down` more than one level in a row

**Tips:**

* Don't see them as walls, instead see them as a `5x5x5` stack of squares that some of them are missing and you can go through the missing ones

# Answer
# C++ C, about 1000 670 643 395 297 248 chars

Sample output:

```
00111,10011,10111,00110,11000,
11001,01010,00100,11011,10101,
10111,10101,10001,01010,00101,
11001,11110,11100,11110,10101,
11100,10010,11001,10101,00000,

```

How it works: The program uses Brownian Motion to generate solutions. The start point is set. Then, a random point is selected and repeatedly moved randomly until it touches one and only one point on the start branch. The point is then set, and if it also touches the end point, the program exits and the matrix displayed. Since no point can join two branches, there is only one path through the labyrinth. The program uses the rand function, and a command line integer argument as the seed, so with a sufficient rand function it should be possible to eventually generate all valid labyrinths (this algorithm will not create unconnected areas however, so it won't generate all *possible* labyrinths).

Brownian motion was dropped since it turned out to be unneeded and it's removal simplifies the code significantly. I do think it made nicer labyrinths though. Likewise, the seed argument was dropped, since requiring a stateless random number generator makes more sense to me than a 128-bit seed.

It is possible for the program to get stuck in an infinite loop, since it is possible for situations where any point added to the branches would create multiple paths. This is fixable, but I think that it is rare enough to not be a concern for code golf.

```
#define M m[*p+1][p[1]][p[2]]
#define F(a,b)for(p[a]=5;p[a]--;putchar(b))
#define f for(i=3;i--;p[i]
p[]={4,4,4},h[3],m[7][6][6]={1};
main(i){
    for(M=2;h[1]^1||(M=1)^h[2];){
        f=rand()%5)
            h[i]=0;
        f++)
            p[i]++,
            h[M]++,
            p[i]-=2,
            h[M]++;
    }
    F(0,10)
        F(1,44)
            F(2,48+!M);
}

```

I've added newlines and indentation to the displayed code for readability.
> 10 votes

# Answer
### JavaScript, 874 816 788 686 682 668 637 characters

sample output:

```
00000,10111,10111,01010,11000
01011,01000,01010,01111,00011
00100,11010,00111,10111,11010
01111,10001,01110,01010,01000
00000,11110,00001,10101,10110

```

this one works by starting from point \[0,0,0\] and randomly adding attaching one more 0 next to an 0 wherever allowed (allowed==the new 0 is not next to any other 0s except the originator) until there are no more possible additions.

if any new 0 is next to the exit point (x\*y\*z == 48) then we open up the exit.

golfed

```
b=[]
I=Math.random
for(i=5;i--;)for(j=5,b[i]=[];j--;)b[i][j]=[1,1,1,1,1]
b[0][0][0]=0
k=[[0,0,0]]
function q(x,y,z){J=b[x]
if(x<0||y<0||z<0||x>4||y>4||z>4||!J[y][z])return
n=6-!x||b[x-1][y][z]
n-=!y||J[y-1][z]
n-=!z||J[y][z-1]
n-=x==4||b[x+1][y][z]
n-=y==4||J[y+1][z]
n-=z==4||J[y][z+1]
n==1&&v.push([x,y,z])}while(I){F=k.length
B=k[C=0|I(v=[])*F]
x=B[0]
q(x-1,y=B[1],z=B[2])
q(x,y-1,z)
q(x,y,z-1)
q(x+1,y,z)
q(x,y+1,z)
q(x,y,z+1)
if(D=v.length){k.push(A=v[0|I()*D])
b[A[0]][A[1]][A[2]]=0
if(A[0]*A[1]*A[2]==48)b[4][4][4]=I=0}else{for(E=[];F--;)F^C&&E.push(k[F])
k=E}}for(i=25;i--;)b[H=0|i/5][i%5]=b[H][i%5].join('')
alert(b.join("\n"))

```

original

```
window.map=[];
for (i=0;i<5;++i) {
  map[i]=[];
  for (j=0;j<5;++j) {
    map[i][j]=[1,1,1,1,1];
  }
}
points=[[0,0,0]];
map[0][0][0]=0;
function spaces(x,y,z) {
  var n=6;
  if (x<0 || y<0 || z<0) return 0;
  if (x>4 || y>4 || z>4) return 0;
  if (!map[x][y][z]) return 0;
  if (!x || map[x-1][y][z]) n--;
  if (!y || map[x][y-1][z]) n--;
  if (!z || map[x][y][z-1]) n--;
  if (x==4 || map[x+1][y][z]) n--;
  if (y==4 || map[x][y+1][z]) n--;
  if (z==4 || map[x][y][z+1]) n--;
  return n;
}
do {
  var index=Math.floor(Math.random()*points.length);
  point=points[index];
  v=[];
  x=point[0];
  y=point[1];
  z=point[2];
  spaces(x-1,y,z)==1 && v.push([x-1,y,z]);
  spaces(x,y-1,z)==1 && v.push([x,y-1,z]);
  spaces(x,y,z-1)==1 && v.push([x,y,z-1]);
  spaces(x+1,y,z)==1 && v.push([x+1,y,z]);
  spaces(x,y+1,z)==1 && v.push([x,y+1,z]);
  spaces(x,y,z+1)==1 && v.push([x,y,z+1]);
  if (v.length) {
    var point=v[Math.floor(Math.random()*v.length)];
    points.push(point);
    map[point[0]][point[1]][point[2]]=0;
    if (point[0]*point[1]*point[2]==48) {
      map[4][4][4]=0;
    }
  }
  else {
    var np=[];
    for (var i=0;i<points.length;++i) {
      i!=index && np.push(points[i]);
    }
    points=np;
  }
} while(points.length);
for (i=0;i<5;++i) {
  for (j=0;j<5;++j) {
    map[i][j]=map[i][j].join('');
  }
  map[i]=map[i].join();
}
alert(map.join("\n"));

```
> 5 votes

# Answer
**Mathematica: True Labyrinth (827 chars)**

Originally, I produced a path from {1,1,1} to {5,5,5} but because there were no possible wrong turns to be made, I introduced forks or "decision points" (vertices of degree \>2) where one would need to decide which way to go. The result is a true maze or labyrinth.

The "blind alleys" were far more challenging to solve than finding a simple, direct path. The most challenging thing was to eliminate cycles within the path while allowing cycles off the solution path.

The following two lines of code are only used for rendering the drawn graphs, so the code does not count, as it is not employed in the solution.

```
o = Sequence[VertexLabels -> "Name", ImagePadding -> 10, GraphHighlightStyle -> "Thick",
    ImageSize -> 600];

o2 = Sequence[ImagePadding -> 10, GraphHighlightStyle -> "Thick", ImageSize -> 600];

```

**Code used:**

```
e[c_] := Cases[EdgeList[GridGraph[ConstantArray[5, 3]]], j_ \[UndirectedEdge] k_ /; (MemberQ[c, j] && MemberQ[c, k])]

m[] :=
Module[{d = 5, v = {1, 125}},
   While[\[Not] MatchQ[FindShortestPath[Graph[e[v]], 1, 125], {1, __, 125}],

v = Join[v, RandomSample[Complement[Range[125], v], 1]]];
   Graph[e[Select[ConnectedComponents[Graph[e[v]]], MemberQ[#, 1] &][[1]]]]]

w[gr_, p_] := EdgeDelete[gr, EdgeList[PathGraph[p]]]

y[p_, u_] := Select[Intersection[#, p] & /@ ConnectedComponents[u], Length[#] > 1 &]

g = HighlightGraph[lab = m[],  PathGraph[s = FindShortestPath[lab, 1, 125]],o]
u = w[g, s]
q = y[s, u]

While[y[s, u] != {}, u =  EdgeDelete[u, Take[FindShortestPath[u,  q[[1, r = RandomInteger[Length@q[[1]] - 2] + 1]],
  q[[1, r + 1]]], 2] /. {{a_, b_} :> a \[UndirectedEdge] b}];

q = y[s, u]]

g = EdgeAdd[u, EdgeList@PathGraph[s]];

Partition[StringJoin /@ Partition[ReplacePart[Table["x", {125}],
Transpose[{VertexList[g], Table["o", {Length[VertexList@g]}]}]/. {{a_, b_} :>  a -> b}], {5}], 5]

```

**Sample output**

{{"oxooo", "xxooo", "xoxxo", "xoxxo", "xxoox"}, {"ooxoo", "xoooo", "ooxox", "oooxx", "xooxx"}, {"oooxx", "ooxxo", "ooxox", "xoxoo", "xxxoo"}, {"oxxxx", "oooox", "xooox", "xoxxx", "oooxx"}, {"xxxxx", "ooxox", "oooox", "xoxoo", "oooxo"}}

**Under the hood**

The picture below shows the labyrinth or maze that corresponds to the solution `({{"ooxoo",...}}` displayed above:

Here is the same labyrinth inserted in a 5x5x5 `GridGraph`. The numbered vertices are nodes on the shortest path out of the labyrinth. Note the forks or decision points at 34, 64, and 114. I'll include the code used for rendering the graph even though it is not part of the solution:

```
HighlightGraph[gg = GridGraph[ConstantArray[5, 3]], g,
 GraphHighlightStyle ->"DehighlightFade",
 VertexLabels -> Rule @@@ Transpose[{s, s}] ]

```

And this graph shows only the solution to the labyrinth:

```
HighlightGraph[gg = GridGraph[ConstantArray[5, 3]],
   Join[s, e[s]], GraphHighlightStyle -> "DehighlightFade", VertexLabels -> Rule @@@    Transpose[{s, s}] ]

```

Finally, some definitions that may help reading the code:

---

**Original solution (432 char, Produced a path but not a true maze or labyrinth)**

Imagine a 5x5x5 large solid cube made up of distinct unit cubes. The following begins without unit cubes at {1,1,1} and {5,5,5}, since we know they must be part of the solution. Then it removes random cubes until there is an unimpeded path from {1,1,1} to {5,5,5}.

The "labyrinth" is the shortest path (if more than one is possible) given the unit cubes that have been removed.

```
d=5
v={1,d^3}
edges[g_,c_]:=Cases[g,j_\[UndirectedEdge] k_/;(MemberQ[c,j]&&MemberQ[c,k])]

g:=Graph[v,edges[EdgeList[GridGraph[ConstantArray[d,d]]],v]];

While[\[Not]FindShortestPath[g,1,d^3]!={},
    v=Join[v,RandomSample[Complement[Range[d^3],v],1]]]

Partition[Partition[ReplacePart[
   Table["x",{d^3}],Transpose[{FindShortestPath[g,1,d^3],Table["o",{Length[s]}]}]
      /.{{a_,b_}:>  a->b}],{d}]/.{a_,b_,c_,d_,e_}:>  StringJoin[a,b,c,d,e],5]

```

Example:

```
{{"ooxxx", "xxxxx", "xxxxx", "xxxxx", "xxxxx"},
 {"xoxxx", "xoooo", "xxxxo", "xxxxo", "xxxxo"},
 {"xxxxx", "xxxxx", "xxxxx", "xxxxx", "xxxxo"},
 {"xxxxx", "xxxxx", "xxxxx", "xxxxx", "xxxxo"},
 {"xxxxx", "xxxxx", "xxxxx", "xxxxx", "xxxxo"}}

```

Technically this is not yet a true labyrinth, since there are no wrong turns that one can make. But I thought it interesting as a start since it relies on graph theory.

The routine actually makes a labyrinth but I plugged up all empty locations that could give rise to cycles. If I find a way to remove cycles I will include that code here.
> 4 votes

---
Tags: code-golf, maze, generation
---


title: Underhanded Password Hashing

text:
# Question
Title: Underhanded Password Hashing
In the spirit of the Underhanded C Contest, I'm starting an Underhanded Code Contest. The objective of this contest is to straightforwardly implement some code, while subtly hiding a nefarious bug inside it.

## The contest

You are a secret Russian mole working in the IT department of an American spy agency. Your American boss has just asked you to implement a password hashing algorithm to use for encrypting secret messages.

Your boss wants you to implement the following function:

```
f: String -> byte[16]

```

which converts a password to a 16-byte quantity suitable for use as an AES key. Your boss wants a secure function, which in this context means that different password strings should generate different results with overwhelming probability. For instance, returning the md5 hash of the input would be a simple implementation of `f`.

Of course, your *real* boss in the Russian spy agency would want you to subvert this process. Your task is to implement `f` such that the Russians can decrypt all the secret messages encrypted using keys returned by `f`.

To do so, you must implement `f` so that it returns only a small subset of the 2^128 possible outputs. In particular, your `f` must return at most 2^16 different results so that the Russians can do an easy brute-force search for the correct key for each encrypted message they wish to decrypt.

Keep in mind, however, that espionage carries the death penalty. In order not to get caught, your function `f` must generate at least 2^8 different results, so that a cursory inspection of a few outputs of `f` is unlikely to reveal a duplicate. **And most importantly, the code you introduce to limit the range of `f` must look unintentional, not deliberate.** If you ever get hauled into a courtroom, there must be some reasonable doubt as to whether you introduced the bug deliberately or by accident.

## Judging

I and two others I recruit will judge the entries (email me if you'd like to judge). I'm offering a 200 reputation bounty for the winning entry. Submissions must be uploaded by May 1.

Judging will take into account the following criteria:

* Does `f` adhere to the spec, i.e. does it generate between 2^8 and 2^16 possible outputs. Don't feel that these are hard limits, but we'll deduct points if you're too far out of range.
* Is the bug plausibly the result of an unintentional mistake?
* Do the outputs of `f` look random?
* The shorter your implementation of `f`, the better.
* The clearer your implementation of `f`, the better.

## Notes

You may use any language to implement your code. You're trying to hide a bug in plain sight, so obfuscated code is not suggested.

You might want to take a look at some of the previous Underhanded C contest winners to get a feel for what makes a good submission.

Input strings will be printable ascii (32 through 126, inclusive). You may assume a reasonable max length if you want.

# Answer
> 15 votes
## C

2^16 possible outputs (or 2^8 times the number of used characters).
Uses Linux's MD5 implementation, which is, AFAIK, fine. But this gives the same hash, for example, for "40" and "42".
EDIT: Renamed `bcopy` to `memcpy` (swapped parameters of course).
EDIT: Converted from program to function, to meet requirements better.

```
#include <string.h>
#include <openssl/md5.h>

void f(const unsigned char *input, unsigned char output[16]) {

    /* Put the input in a 32-byte buffer, padded with zeros. */
    unsigned char workbuf[32] = {0};
    strncpy(workbuf, input, sizeof(workbuf));

    unsigned char res[MD5_DIGEST_LENGTH];
    MD5(workbuf, sizeof(workbuf), res);

    /* NOTE: MD5 has known weaknesses, so using it isn't 100% secure.
     * To compensate, prefix the input buffer with its own MD5, and hash again. */
    memcpy(workbuf+1, workbuf, sizeof(workbuf)-1);
    workbuf[0] = res[0];
    MD5(workbuf, sizeof(workbuf), res);

    /* Copy the result to the output buffer */
    memcpy(output, res, 16);
}

/* Some operating systems don't have memcpy(), so include a simple implementation */
void *
memcpy(void *_dest, const void *_src, size_t n)
{
    const unsigned char *src = _src;
    unsigned char *dest = _dest;
    while (n--) *dest++ = *src++;
    return _dest;
}

```

# Answer
> 13 votes
# C

This may not be the flashiest contest entry, but I think the following is the kind of hash function that could have been made by any coder too clever for their own good, with a vague idea of the kind of operations you see in hash functions:

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

void hash(const char* s, uint8_t* r, size_t n)
{
     uint32_t h = 123456789UL;
     for (size_t i = 0; i < n; i++) {
          for (const char* p = s; *p; p++) {
               h = h * 33 + *p;
          }
          *r++ = (h >> 3) & 0xff;
          h = h ^ 987654321UL;
     }
}

int main()
{
     size_t n = 1024;
     char s[n];
     size_t m = 16;
     uint8_t b[m];
     while (fgets(s, n, stdin)) {
          hash(s, b, m);
          for (size_t i = 0; i < m; ++i)
               printf("%02x", b[i]);
          printf("\n");
     }
}

```

In fact the hash function can return no more than L\*2048 different results, where L is the number of different input string lengths that can occur. In practice, I tested the code on 1.85 million unique input lines from manual pages and html documents on my laptop, and got only 85428 different unique hashes.

# Answer
> 0 votes
## Scala:

```
// smaller values for more easy tests:
val len = 16
// make a 16 bytes fingerprint
def to16Bytes (l: BigInt, pos: Int=len) : List[Byte] =
  if (pos == 1) List (l.toByte) else (l % 256L).toByte :: to16Bytes (l / 256L, pos-1)
/** if number isn't prime, take next */
def nextProbPrime (l: BigInt) : BigInt =
  if (l.isProbablePrime (9)) l else nextProbPrime (l + 1)
/** Take every input, shift and add, but take primes */
def codify (s: String): BigInt =
  (BigInt (17) /: s) ((a, b) => nextProbPrime (a * BigInt (257) + b))
/** very, very short Strings - less than 14 bytes - have to be filled, to obscure them a bit: */
def f (s: String) : Array [Byte] = {
  val filled = (if (s.size < 14) s + "secret" + s else s)
  to16Bytes (codify (filled + filled.reverse)).toArray.map (l => nextProbPrime (l).toByte)
}

```

Test, if the result doesn't look similar for similar input:

```
val samples = List ("a", "aa", "b", "", "longer example", "This is a foolish, fishy test")

samples.map (f)

 List[Array[Byte]] = List(
Array (-41, -113, -79, 127, 29, 127, 31, 67, -19, 83, -73, -31, -101, -113, 97, -113),
Array (-19, 7, -43, 89, -97, -113, 47, -53, -113, -127, -31, -113, -67, -23, 127, 127),
Array (-41, -113, -79, 127, 29, 127, 31, 67, -19, 83, -73, -31, -101, -113, 97, -113),
Array (37, -19, -7, 67, -83, 89, 59, -11, -23, -47, 97, 83, 19, 2, 2, 2),
Array (79, 101, -47, -103, 47, -13, 29, -37, -83, -3, -37, 59, 127, 97, -43, -43),
Array (37, 53, -43, -73, -67, 5, 11, -89, -37, -103, 107, 97, 37, -71, 59, 67))

```

The error is using just primes for the encoding. Instead of

```
scala> math.pow (256, 16)
res5: Double = 3.4028236692093846E38

```

values, we end with

```
scala> math.pow (54, 16)
res6: Double = 5.227573613485917E27

```

since there are 54 primes below 256.

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


title: Lorem Ipsum Random Code Generation

text:
# Question
Title: Lorem Ipsum Random Code Generation
An IDE developer has hired you to write a program that generates (by printing to stdout) **n** lines of randomly generated code. They will use your program to create sample code for use in marketing their newest compiler.

**Rules:**

Your randomly generated output code:

* must not be the same each execution (for the same **n** parameter)
* must be written in the same language as your program
* must be able to be successfully compiled without errors or warnings (including "variable not used" messages, if your language includes them)
* should use a variety of the language's built-in features
* should (where appropriate) follow the language's most popular style guide. For example, PEP-8 for Python
* should, if n is larger than 20, have functions. Functions should be limited to a length that follows the language's style guide
* does not have to have comments (but the developer will be impressed if it does!)
* may include a single blank line between code blocks for clarity

You can use an external dictionary to allow generation of function/variable names, and lists of standard functions/libraries for your language. If your program uses these, please include a link (to a pastebin if your dictionary is custom written for this task)

Please include a few sample outputs to demonstrate your program's capabilities.

**Winning:**

The winning program should implement all the above features, and generate realistic code without sacrificing execution time or program length (to a huge degree - this isn't golf).

The winner will be chosen by community vote from entries received before **1st May 2012**. Voting should be based upon realism, variety, creativity and adherence to the criteria above.

Good luck!

# Answer
Did it in Brainfuck! I had a bit of trouble generating random numbers. I hoped something simple like a LFSR could give me a fairly decent looking sequence, but I found it looped too quickly and gave boring output. I resorted to using a RNG found here, which actually takes quite a long time to run. Since BF has no capacity to get any source of entropy from the operating system, I first have the user input any text (I pound on they keyboard) to seed the RNG. After that it takes the number of lines and outputs random BF, using 16 hard-coded subsequences.

```
get random seed input till newline (10)
>>>+[,[<+>>+>>>>>>+++<<<<<<<-]>[<+>-]<----------]
get number of lines
<<<,[->>

Map: n nesting seed lineCount _ _ _ _ _ _ randh randl

mod by 32 to get char count for this line
[>+>+<<-]>>[<<+>>-]>++++[<++++++++>-]<<
[->-[>+>>]>[+[-<+>]>+>>]<<<<<] >[-]>>[-]<[<<+>>-]
loop that many times
<<[-<

generate next 'random' number
>>[-]>[-]>[-]>[-]>[-]>[-]>[<<<<<<+>>>>>>-]>[<<<<<<+>>>>>>-]<<<<+++++++
[<+++++++++++>-]<[<<[>>>>>>+<<<+<<<-]>>>[<<<+>>>-]<<[>>>>>+<<<+>+<<<-]
>>>[<<<+>>>-]<[>>>>+[<<<+>+>>-]<<[>>+<<-]+<[>-<[-]]>[>+<-]<<-]<-]+++++
+[>++++++++<-]>-[<<[>>>>>+<<<<+<-]>[<+>-]>-]<<<[-]>[-]+++++[<+++++>-]<
[>>>>>>>+[<<<<<<+>+>>>>>-]<<<<<[>>>>>+<<<<<-]+<[>-<[-]]>[>>>>+<<<<-]<<
-]++++++[>>>>>>+++++++++<<<<<<-]>>>>>>[<<<<<<<<+>>+>>>>>>-]<<<<<<[>>>>
>>+<<<<<<-]<<
seed is now next number in sequence

copy and mod 16
[>>+>+<<<-]>>>[<<<+>>>-]>++++[<++++>-]<<
[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>[-]>>[-]<
now we have bottom 4 bits of data; pick an output sequence:
#00: +
[<+<+>>-]<[>+<-]+<[>-<[-]]>[-[-]>[-]<
>++++++[<+++++++>-]<+.[-]]>

#01: +
-[<+<+>>-]<[>+<-]+<[>-<[-]]>[-[-]>[-]<
>++++++[<+++++++>-]<+.[-]]>

#02: -
-[<+<+>>-]<[>+<-]+<[>-<[-]]>[-
[-]>[-]<
>+++++[<+++++++++>-]<.[-]]>

#03: [->-[>+>>]>[+[-<+>]>+>>]<<<<<]
-[<+<+>>-]<[>+<-]+<[>-<[-]]>[-[-]>[-]<
>+++++++[<+++++++++++++>-]<.
>+++++[<--------->-]<-.
+++++++++++++++++.
-----------------.
>+++++[<+++++++++>-]<+.
>++++[<------->-]<-.
>+++[<------>-]<-.
>+++[<++++++>-]<+..
>+++++[<++++++>-]<+.
>+++++[<------>-]<-.
>++++[<+++++++>-]<+.
>++++++[<-------->-]<.
>++++++[<++++++++>-]<.
>+++++[<--------->-]<-.
+++++++++++++++.
-----------------.
>+++[<++++++>-]<+.
>+++++[<++++++>-]<+.
>+++++[<------>-]<-.
>+++[<------>-]<-.
>+++[<++++++>-]<+..
>+++++[<++++++>-]<+.
>++++[<-------->-]<-.....>++++[<++++++++>-]<+.[-]]>

#04: <
-[<+<+>>-]<[>+<-]+<[>-<[-]]>[-
[-]>[-]<
>++++++[<++++++++++>-]<.[-]]>

#05: <
-[<+<+>>-]<[>+<-]+<[>-<[-]]>[-
[-]>[-]<
>++++++[<++++++++++>-]<.[-]]>

#06: >
-[<+<+>>-]<[>+<-]+<[>-<[-]]>[- ----[>+<----]>---.[-]<]>

#07: x y z
-[<+<+>>-]<[>+<-]+<[>-<[-]]>[-[-]>[-]<
>++++[<++++++++>-]<.
>++++++++[<+++++++++++>-]<.
>++++++++[<----------->-]<.
>++++++++[<+++++++++++>-]<+.
>++++++++[<----------->-]<-.
>+++++++++[<++++++++++>-]<.[-]]>

#08: [
-[<+<+>>-]<[>+<-]+<[>-<[-]]>[-
[-]>[-]<
>+++++++[<+++++++++++++>-]<.[-]<<<<+>>>>
]>

#09: [
-[<+<+>>-]<[>+<-]+<[>-<[-]]>[-
[-]>[-]<
>+++++++[<+++++++++++++>-]<.[-]<<<<+>>>>
]>

#10: ++[>+<------]>
-[<+<+>>-]<[>+<-]+<[>-<[-]]>[-
 [-]>[-]<
>++++++[<+++++++>-]<+..
>++++++[<++++++++>-]<.
>++++[<------->-]<-.
>+++[<------>-]<-.+++++++++++++++++.
---------------......>++++++[<++++++++>-]<.
>+++++[<------>-]<-.[-]]>

#11: +<->++
-[<+<+>>-]<[>+<-]+<[>-<[-]]>[- [-]>[-]<
>++++++[<+++++++>-]<+.
+++++++++++++++++.
---------------.
+++++++++++++++++.
>+++[<------>-]<-..[-]]>

#12: .
-[<+<+>>-]<[>+<-]+<[>-<[-]]>[-[-]>[-]<
>+++++[<+++++++++>-]<+.[-]]>

#13: ,
-[<+<+>>-]<[>+<-]+<[>-<[-]]>[-[-]>[-]<
>++++[<+++++++++++>-]<.
[-]]>

#14: [<+<+>>-]
-[<+<+>>-]<[>+<-]+<[>-<[-]]>[-
[-]>[-]<
>+++++++[<+++++++++++++>-]<.
>+++++[<------>-]<-.
-----------------.
+++++++++++++++++.
-----------------.
>+++[<++++++>-]<+..-----------------.
>++++++[<++++++++>-]<.[-]]>

#15: [-]
-[<+<+>>-]<[>+<-]+<[>-<[-]]>[-[-]>[-]<
>+++++++[<+++++++++++++>-]<.
>+++++[<--------->-]<-.
>++++++[<++++++++>-]<.[-]]>

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

```

Output for input

```
qqq
10

```

is

```
[<+<+>>-]<[-] x y z.< x y z<.++[>+<------]>[[-]+<. x y z++[>+<------]>.+<->++[->-[>+>>]>[+[-<+>]>+>>]<<<<<][+[<+<+>>-] x y z[<+<+>>-][<+<+>>-][<+<+>>-]++[>+<------]>+<->++]]
-[->-[>+>>]>[+[-<+>]>+>>]<<<<<][<+<+>>-][-][ x y z++[>+<------]>,[-][->-[>+>>]>[+[-<+>]>+>>]<<<<<]-]
<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]
+,++[>+<------]>-[[-]+<->++[[->-[>+>>]>[+[-<+>]>+>>]<<<<<],++[>+<------]>[->-[>+>>]>[+[-<+>]>+>>]<<<<<]++[>+<------]>.[+ x y z+<]]]
++[>+<------]>++-[-]-[-]+,[->-[>+>>]>[+[-<+>]>+>>]<<<<<][->-[>+>>]>[+[-<+>]>+>>]<<<<<][->-[>+>>]>[+[-<+>]>+>>]<<<<<]+,+[<++[>+<------]>,-+<->++]
-[<+<+>>-]-., x y z[ x y z<[<+<+>>-]< x y z<[+<->+++<->++-++[>+<------]>+<->+++[[<-[-][+<->++]]]]]
[<+<+>>-]++[<+<+>>-]-<<[-]+<->++<[]
,[->-[>+>>]>[+[-<+>]>+>>]<<<<<]++[>+<------]>++<->+++<->++[<+<+>>-]<
++[>+<------]>[<+<+>>-][+<->+++<->++[[->-[>+>>]>[+[-<+>]>+>>]<<<<<]<[<+<+>>-]++[>+<------]> x y z x y z<..[[-][<+<+>>-],[<+<+>>-]+,]]]
-, x y z<<[<[->-[>+>>]>[+[-<+>]>+>>]<<<<<].[,<-]]

```

and it runs in about 2 minutes on my box. Output contains entirety of BF syntax, including comments, and it well formed.
> 10 votes

---
Tags: popularity-contest, random, generation
---


# Question
Title: Print the sizes of intervals inside of a piece of music
## Background

In Western music, every single music note has an assigned name. Within each octave, there are twelve unique notes in the following order: "C C#/Db D D#/Eb E F F#/Gb G G#/Ab A A#/Bb B C", where the final C is one octave above the first.

To tell the difference between notes of different octaves, a number (for this challenge restricted to a single digit) is appended to the end of the note name. Thus, C5 is the note that is one octave above C4. Bb6 is above B5.

An important fact is that B5 and C6 are notes that are right next to each other, and that C0 and B9 are the lowest and highest notes.

Between any two notes, there is a distance which is the number of semitones between them. Bb4 is one semitone below B4, which is itself one semitone below C5. There are twelve semitones in an octave, so Bb4 is a distance of 12 from A#3 since it is an octave above it (notice how a single note can have up to two names).

## The Challenge

Your challenge is to write the shortest possible program that can take a list of music notes from STDIN and print the list of interval changes to STDOUT.

Input will be a space-separated list of music notes. Each note will consist of an uppercase letter A-G, an optional b or # sign, and a single digit number. You will not have to deal with E#/Fb or B#/Cb. Example input:

```
C4 D4 E4 F4 G4 A4 B4 C5 C4

```

Output will be a space-separated list of integers which represent the distance between each successive note, always prefixed with an + or - to show whether the note was ascending or descending relative to the one before it. There will always be one less number outputted than notes inputted. Example output for the above input:

```
+2 +2 +1 +2 +2 +2 +1 -12

```

Some more example inputs:

```
E5 D#5 E5 B4 E5 F#5 E5 B4
C0 B0 Bb1 A2 G#3 G4 F#5 F6
G4 Ab4 Gb4 A4 F4 A#4

```

And their corresponding outputs:

```
-1 +1 -5 +5 +2 -2 -5
+11 +11 +11 +11 +11 +11 +11
+1 -2 +3 -4 +5

```

## Rules and Restrictions

1. The winner is determined by the number of characters in the source code
2. Your program should consist of only printable ASCII characters
3. You are not allowed to use any sort of built-in function that is related to music or sound
4. Other than that, standard code golf rules apply

# Answer
### GolfScript, 61

```
" "/{)12*\{"bC#D EF G A B"?(+}/}%(\{.@-.`\0>{"+"\+}*\}/;]" "*

```
> 6 votes

# Answer
## Haskell, 161 characters

```
f(c:r)=maybe(12*read[c])(+f r).lookup c$zip"bC#D.EF.G.A.B"[-1..]
g n|n<0=show n|1<3='+':show n
h x=zipWith(-)(tail x)x
main=interact$unwords.map g.h.map f.words

```
> 4 votes

# Answer
# Perl, 103

```
#!/usr/bin/perl -an
/.((b)|(\D))?/,(($~,$,)=($,,12*$'+ord()%20%7*2+(ord()%7>3)-$-[2]+$-[3]))[0]&&printf'%+d ',$,-$~for@F

```
> 4 votes

# Answer
## C, 123 characters

Based on leftaroundabout's solution, with some improvements.

```
main(c,b,d)
    char*b;
{
    while(d=c,~scanf("%s",b)?c=-~*b*1.6,c%=12,c+=b[~b[1]&16?c+=1-b[1]/40,2:1]*12:0)
        d>1&&printf("%+d ",c-d);
}

```

Some tricks that I think are worth mention:
1. `argv[0]` (here called `b`) is a pointer to the program name, but used here as a scratch buffer. We only need 4 bytes (e.g. `C#2\0`), so we have enough.
2. `c` is the number of arguments, so it starts as 1 (when run without arguments). We use it to prevent printing on the first round.

Possible problem - `c+=b[..c+=..]` is kind-of strange. I don't think it's undefined behavior, because `?:` is a sequence point, but maybe I'm wrong.
> 3 votes

# Answer
## C, ~~241~~ ~~229~~ 183

```
F(c){c-=65;return c*1.6+sin(c/5.+.3)+9;}
#define r if(scanf("%s",b)>0){c=F(*b)%12;c+=b[b[1]<36&&++c||b[1]>97&&c--?2:1]*12
main(e,c,d){char b[4];r;}s:d=c;r;printf("%+d ",c-d);goto s;}}

```
> 2 votes

# Answer
## Factor, 303 characters

```
USING: combinators formatting io kernel math regexp sequences ;
f contents R/ [#-b]+/ all-matching-slices
[ 0 swap [ {
{ [ dup 48 < ] [ drop 1 ] }
{ [ dup 65 < ] [ 48 - 12 * ] }
{ [ dup 98 < ] [ "C-D-EF-G-A-B" index ] }
[ drop -1 ]
} cond + ] each
swap [ over [ - "%+d " printf ] dip ] when* ] each drop

```

With comments,

```
! combinators => cond
! formatting => printf
! io => contents
! kernel => swap dup drop over dip when*
! math => < - * +
! regexp => R/ all-matching-slices
! sequences => each
USING: combinators formatting io kernel math regexp sequences ;

f       ! Push false, no previous note value.

! Find notes (as string slices) in standard input. The golfed regexp
! R/ [#-b]+/ matches all notes and no whitespace.
contents R/ [#-b]+/ all-matching-slices

! For each string slice:
[
    0       ! Push 0, initial note value.
    swap    ! Move note slice to top of stack, above note value.

    ! For each Unicode codepoint in note:
    [
        ! Convert the Unicode codepoint to its value in semitones.
        ! For golf, [ 48 ] is shorter than [ CHAR: A ].
        {
            ! Sharp # {35} has 1 semitone.
            { [ dup 48 < ] [ drop 1 ] }
            ! 0-9 {48-57} has 0 to 9 octaves (1 octave = 12 semitones).
            { [ dup 65 < ] [ 48 - 12 * ] }
            ! A-G {65-71} has 0 to 11 semitones.
            { [ dup 98 < ] [ "C-D-EF-G-A-B" index ] }
            ! Flat b {98} has -1 semitone.
            [ drop -1 ]
        } cond

        +       ! Add semitones to cumulative note value.
    ] each

    swap    ! Move previous note value to top of stack.
    ! When there is a previous note value:
    [
        ! Keep current note on stack.
        over [
            ! Compute and print interval.
            - "%+d " printf
        ] dip
    ] when*
    ! Current note replaces previous note at top of stack.
] each

drop    ! Drop previous note, so stack is empty.

```

For this script, a "space-separated list" can have 1 or more spaces between elements, and 0 or more spaces at the beginning or end. This script does print an extra space at end of output, but it also accepts an extra space (or newline) at end of input.

If I would adopt a stricter definition, where a "space-separated list" has exactly 1 space between elements, and 0 spaces at the beginning or end, then I can shorten `contents R/ [#-b]+/ all-matching-slices` to `contents " " split` (using `splitting`, not `regexp`). However, I would need to add more code to prevent the extra space at end of output.

If I use the deprecated word `dupd`, I can shorten `over [ - "%+d " printf ] dip` to `dupd - "%+d " printf`, saving 8 characters. I am not using deprecated words because they "are intended to be removed soon."
> 1 votes

---
Tags: code-golf, math, music, printable-ascii
---


title: Water-Bucket problem

text:
# Question
Title: Water-Bucket problem
This challenge is to calculate how to measure 4 liters of water with just two unevenly sized buckets, one of 3 liters and another of 5 liters, in minimum number of steps. To extend and generalize this, write a program to evaluate the minimum number of steps to measure “X” liters of water, with “Y” buckets each having a separate denomination.

Assumptions:

1. Each bucket used for measuring water should be unique in denomination and the number of buckets will be \<= 3
2. The target amount to be reached has to finally reside in a single bucket (at the end of the measuring activity).
3. The bucket capacities and target amount will be \<= 99
4. If there are multiple ways to measure the same amount, only one single way, having the minimum number of steps is required.
5. Ties will be broken by the smallest program.

**Examples:**

> 2,3,5,4
> Implies that there are 2 buckets of capacity 3 and 5 each and the target amount desired is 4.
>
> 3,4,6,9,7
> Implies that there are 3 buckets of capacity 4, 6 and 9 each and the target amount desired is 7.

**Answers:**

> 2,3,5,4
> Fill 5
> Move 5 to 3
> Empty 3
> Move 5 to 3
> Fill 5
> Move 5 to 3
>
> 3,4,6,9,7
> Fill 4
> Move 4 to 6
> Fill 9
> Move 9 to 6

# Answer
## Python, 363 chars

Golfed it, not sure if it is golf or not. The map `P` maps a reachable state to the instructions used to get to that state. Keeps enumerating reachable states until it finds one with the target amount of water in it.

```
I=input()
B=I[1:-1]
R=range(I[0])
P={(0,)*I[0]:""}
while P:
 Q={}
 for s in P:
  if I[-1]in s:print P[s];P=Q={};break
  for i in R:
   Q[s[:i]+(0,)+s[i+1:]]=P[s]+"Empty %d "%B[i];Q[s[:i]+(B[i],)+s[i+1:]]=P[s]+"Fill %d "%B[i]
   for d in R:m=min(s[i],B[d]-s[d]);Q[tuple(s[j]-[0,m][j==i]+[0,m][j==d]for j in R)]=P[s]+"Move %d to\
 %d "%(B[i],B[d])
 Q.update(P);P=Q

```
> 4 votes

# Answer
### Ruby

The following code gives a ruby implementation of the task described above. The specification is as follows:

**Input:** A list of integers on STDIN, where the first one is the number *n* of buckets available, followed by *n* distinct bucket denominations, followed by the target amount of water.

**Output:** A list of operations needed to reach the target amount in any bucket or a corresponding message if that is not possible.

**Task:** Start with *n* empty buckets each of different integer denomination. In each step you can do one of the following:

* *Fill X*: fills the bucket with denomination *X* with water such that it contains exactly *X* water
* *Empty Y*: empty the bucket with denomination *Y*, i.e. no water inside after this operation
* *Move A to B*: take any water in bucket with denomination *A* and put it into bucket with denomination *B* up to the point where bucket *B* is full. (Example: Bucket 5 has 4 liters in it and bucket 3 has 2. Then Move 5 to 3 will transfer 1 liter leaving bucket 5 with 3 liters while bucket 3 is full afterwards.)

The algorithm used is quite straightforward. On a list of bucket configurations (i.e. a list of buckets with their corresponding fill levels) perform all possible operations. Each one will lead to a new configuration. Keep those which you didn't had already in previous steps (i.e. those that are really novel). This way we get a list of configurations reachable be 1 step, 2 steps, ... . Whenever we reach a configuration where one bucket is filled with exactly the target amount we are done.

Since we have a constructive algorithm, i.e. we know in each step which operation we perform, we can simultaneously build the list of operations in textual representation for any bucket configuration.

Example: 3 buckets with denominations 7, 9 and 11. Target amount of water is 1.

**Input:**

```
3, 7, 9, 11, 1

```

**Output:**

```
Solution found with 7 steps:
 Fill 7 Move 7 to 11 Fill 7 Move 7 to 11 Move 7 to 9 Fill 7 Move 7 to 9

```

**Code:**

```
# get input as list of integers
input = gets.split(/,/).map{|s| s.to_i}

count = input.shift
start = (1..count).map{[input.shift, 0]}
target = input.shift

# a bucket configuration is a list of buckets, each represented as
# array [denomination, fill level], i.e. initial configurations
# is e.g. [[3, 0], [5, 0]] for empty buckets of size 3 and 5

configurations = {start => ""}
step = 0
solution = nil

current = configurations.keys

while current.size > 0 do

  # debug output (each configuration rechable within step)
  puts "- #{step} ------------------------------------------"
  current.each{|k| puts "#{k.to_s} #{configurations[k]}"}
  puts

  # test current configurations if target amount is included
  solution = current.select{|k| k.any?{|b| b[1] == target}}[0]
  break if solution

  step += 1
  new_configurations = {}

  # for all configurations for all buckets
  current.each{|k|
    k.size.times{|i|

      # do a fill operation on this bucket
      kn = Marshal.load(Marshal.dump(k))   # make deep copy
      # increase fill level to bucket denomination
      kn[i][1] = kn[i][0]
      new_configurations[kn] = "#{configurations[k]} Fill #{kn[i][0]}"

      # do an empty operation on this bucket
      kn = Marshal.load(Marshal.dump(k))   # make deep copy
      # set fill level to zero
      kn[i][1] = 0
      new_configurations[kn] = "#{configurations[k]} Empty #{kn[i][0]}"

      # do a move operation on any other bucket
      k.size.times{|j|
        kn = Marshal.load(Marshal.dump(k))   # make deep copy
        # amount movable is current amount or space left in other bucket
        h = [kn[i][1], kn[j][0]-kn[j][1]].min
        kn[i][1] -= h
        kn[j][1] += h
        new_configurations[kn] = "#{configurations[k]} Move #{kn[i][0]} to #{kn[j][0]}"
      }
    }
  }

  # remove any configuration already reachable with less steps
  new_configurations.keep_if{|conf| !configurations[conf]}

  # merge new configurations
  configurations.merge!(new_configurations)

  current = new_configurations.keys

end

if solution
  puts "Solution found with #{step} steps:"
  puts configurations[solution]
else
  puts "Impossible to reach target"
end

```
> 3 votes

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


title: Did I win the lotto?

text:
# Question
Title: Did I win the lotto?
I just submitted an answer to this question, and then looked about at some news stories about the MegaMillions lottery craze going on right now in the US. This news article stated that an individual purchased $20,000 worth of tickets at one time (that's 20,000 **sets** of numbers to confirm!) to try and test their luck.

That led me to thinking about how one might quickly determine whether or not they'd won any prize, not just a jackpot, on a large lot of tickets that they had purchased.

The challenge then is this:

## Overview:

Write a function or program that will accept a string of numbers as an argument (STDIN, or read in from a file, your choice), and return the numbers of the tickets with at least the minimum payout awarded.

## Code Details:

* The input will consist of a series of lines, one for each ticket purchased. The winning numbers will be prefixed with a 0, while the drawn numbers will be prefixed with an incremented number starting at 1. (see example)
* The input should be a completely random set of numbers each time, including draws and winning numbers.
* The input should accept any number of tickets *n* where 1 \<= *n* \<= 20,000. (Assume no 0 ticket runs.)
* Each line of input will have 7 numbers per line. One for the prefix noted above, 5 for the standard balls, and one additional for the 'match' ball. (see **Lotto Details** below)
* The input can be delimited any way you wish (whitespace, semicolon, etc.)
* The output should be a listing of all winning draws and the winning amount. *(So you know which to turn in.)*
* The output listing should be ordered by win amount. *(Who cares if you won $2 on one ticket if you also won $10,000 on another???)*
* When more than one ticket wins the same amount, the order of those tickets is irrelevant.
* The output should also give a listing of the total amount won.

## Lotto Details:

* Standard rules for the MegaMillions game will apply, since that's what's so hot right now.
* Draws consist of six numbers from two separate pools of numbers - five different numbers from 1 to 56 and one number (the match ball) from 1 to 46.
* The jackpot is won by matching all six winning numbers in a drawing.
* Awards for non-jackpot wins are awarded as follows (see image below).

(Main) + (Match) = (Payout)
5 + 1 = Jackpot
5 + 0 = $250,000
4 + 1 = $10,000
4 + 0 = $150
3 + 1 = $150
3 + 0 = $7
2 + 1 = $10
1 + 1 = $3
0 + 1 = $2
* Assume current jackpot is $1,000,000 (one million).
* Assume only one jackpot winner, unless your random draw pulls the same jackpot pick more than once *(are you cheating?)*.
* Assume **no** multiplier/California rules are in-play.

## Challenge Details:

* This is code golf, so shortest code wins.
* In the event of a tie, I'll take the highest upvoted answer. I know this is somewhat subjective, but the main point is still the score.

## Example:

**Input:**

```
0   2   4   23  38  46  23
1   17  18  22  23  30  40
2   2   5   24  37  45  23
3   4   23  38  40  50  9
4   2   4   23  38  46  17
5   5   16  32  33  56  46

```

**Output:**

```
4 - $250,000
3 - $7
2 - $3
Total Winnings: $250,010

```

# Answer
## Python, 239 chars

```
import sys
a=map(eval,sys.stdin)
w=lambda x:(0,2,0,3,0,10,7,150,150,1e4,25e4,1e6)[2*len(set(x[1:-1])&set(a[0][1:-1]))+(x[6]==a[0][6])]
s=0
for e in sorted(a[1:],cmp,w,1):
    t=w(e);s+=t
    if t:print e[0],"- $%u"%t
print"Total Winnings: $%u"%s

```

Assuming the input numbers are comma separated.
> 3 votes

# Answer
# VBA (660 535 Chars)

Assuming delimiter is a space (`" "`)...

```
Sub a(b)
c=Split(b,vbCr)
Set l=New Collection
Set n=New Collection
d=Split(c(0)," ")
For e=1 To UBound(c)
f=Split(c(e)," ")
p=f(0)
i=1
For g=1 To 5:For h=1 To 5
i=i-(d(g)=f(h))
Next:Next
k=IIf(d(6)=f(6),Choose(i,2,3,10,150,10^4,10^6),Choose(i,0,0,0,7,150,500^2))
If k>0 Then
o=1
For m=1 To l.Count
If k>=l(m) Then l.Add k,p,m:n.Add p,p,m:o=0:m=99999
Next
If o Then l.Add k,p:n.Add p,p
End If
Next
For m=1 To l.Count
r=r & n(m) & ":" & Format(l(m),"$#,##0") & vbCr
q=q+l(m)
Next
MsgBox r & "Total Winnings:" & Format(q,"$#,##0")
End Sub

```
> 2 votes

# Answer
# Javascript, 353 Bytes

```
(function(t){u={"51":1e6,"50":25e4,"41":1e4,"40":150,"31":150,"30":7,"21":10,"11":3,"01":2},a=t.split('\n'),l=a.length-1,m=a[0].split(' '),w=m.slice(1,6),h=0;for(;l--;){s=a[l+1].split(' '),i=s.slice(1,6).filter(function(n){return!!~w.indexOf(n)}),n=i.length+''+(s[6]==m[6]?1:0),v=u[n];if(v){h+=v;console.log(l+'-$'+v)}}console.log('Total Winnings: $'+h)})("0 2 4 23 38 46 23\n" + "1 17 18 22 23 30 40\n" + "2 2 5 24 37 45 23\n" + "3 4 23 38 40 50 9\n" + "4 2 4 23 38 46 17\n" + "5 5 16 32 33 56 46")

```

ungolfed:

```
(function (t) {
    u = {
        "51": 1e6,
        "50": 25,
        "41": 1e4,
        "40": 150,
        "31": 150,
        "30": 7,
        "21": 10,
        "11": 3,
        "01": 2
    },
    a = t.split('\n'),
    l = a.length - 1,
    m = a[0].split(' '),
    w = m.slice(1, 6),
    h = 0;
    for (; l--; ) {
        s = a[l + 1].split(' '),
        i = s.slice(1, 6).filter(function (n) { return !! ~w.indexOf(n) }),
        n = i.length + '' + (s[6] == m[6] ? 1 : 0),
        v = u[n];
        if (v) {
            h += v;
            console.log(l + ' - $' + v)
        }
    }
    console.log('Total Winnings: $' + h)
})("0 2 4 23 38 46 23\n" +
"1 17 18 22 23 30 40\n" +
"2 2 5 24 37 45 23\n" +
"3 4 23 38 40 50 9\n" +
"4 2 4 23 38 46 17\n" +
"5 5 16 32 33 56 46")

```

Could probably knock a few chars off that :D
> 2 votes

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


title: Convert Fractran into Brainfuck

text:
# Question
Title: Convert Fractran into Brainfuck
## Background

Fractran is an esoteric Turing-complete programming language invented by John Conway. A Fractran program consists of an ordered list of fractions. The program starts by taking a single integer as input. Each iteration of the program, it searches the list for the first fraction such that multiplying the number by that fraction produces another integer. It then repeats this process with the new number, starting back at the beginning of the list. When there is no fraction on the list that can be multiplied with the number, the program terminates and gives the number as the output.

The reason that Fractran is Turing-complete is because it simulates a register machine. The number's prime factorization stores the contents of the registers, while the division and multiplication is a way to conditionally add and subtract from the registers. I would recommend reading the Wikipedia article (linked to above).

## The Challenge

Your task is to write the shortest program possible that can take a valid Fractran program from STDIN as its only input and generates a valid BF program to STDOUT that simulates the Fractran program. There are two ways that you could simulate a Fractran program with BF.

*NOTE: Your answer is not a BF program. Your answer is the code that generates the BF program from any given Fractran program. The goal is to get the BF program to be the equivalent of the Fractran program. (technically you could do the competition in BF, but it would be hard)*

**Option 1**

Your program should output a BF program that does the following:

* Takes exactly 1 number from STDIN in the form of the corresponding ASCII character (due to the way that BF input works), which is the input to the Fractran program.
* Prints exactly 1 number to STDOUT in the form of the corresponding ASCII character, which is the output to from the Fractran program.

This option is meant to represent the exact input and output from a Fractran virtual machine.

**Option 2**

The BF code that your program produces should do the following:

* Take input by having the prime factorization of the number already encoded in memory (prior to running the program). If the input is 28 (2\*2\*7), then there will be a value of 2 in the second cell and a value of 1 in the seventh cell (the pointer starts on cell 0). All other cells will be zero.
* Give output by having the prime factorization of the output encoded in memory when the program terminates. If the output is 10, then there must be a value of 1 in each of cells 2 and 5. All other prime-numbered cells must have a value of zero. The content of other cells do not matter.

This option represents the computing model behind the Fractran language.

## Rules and Requirements

1. Input (top your program) will be a list of fractions on STDIN. There will be one fraction per line with a comma between the numerator and denominator. An empty line represents the end of input. The fractions will always be reduced to lowest terms.
2. Your program's output should be a single-line, valid BF program to STDOUT. This program should be able to simulate that particular Fractran program according to one of the two options. For any input, the BF program generated should be able to produce the same output as the Fractran program.
3. You must state which option you chose.
4. You can choose the bounds on the BF memory and tape, and whether they are wrapping
5. CODE GOLF. Also, the size of the outputted BF programs does not matter, only the size of the program that is doing the converting.
6. Programs should only consist of printable ASCII

If I am ambiguous anywhere, do not hesitate to ask. This is a very complicated challenge to describe.

In addition, please post your program's generated BF code for the following input, as to provide an easy way to check if your program is working:

```
33,20
5,11
13,10
1,5
2,3
10,7
7,2

```

This program calculates the number of 1s in the binary expansion of a number. However, the input and output are formatted strangely (as with all Fractran programs). Input is of the form 2^A, while output is of the form 13^B.

# Answer
## Python, 182 chars

Option 1, standard byte cells. There are only 255 possible inputs (0 as an input doesn't really make sense), so I just run a Fractran interpreter 255 times in Python and generate a simple table lookup Brainfuck program encoding the results.

```
import sys
I=map(eval,sys.stdin)
P='+>,'
Q=''
for i in range(1,256):
 while i:j=i;i=([i*x/y for x,y in I if i%y==0]+[0])[0]
 r=j&255;P+='-[';Q=']<[-'+'+'*r+'.'+'-'*r+']>'+Q
print P+Q

```

Output for the example input (`___` = 246 more nested conditions, I can't paste the whole result as it is too large):

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

```
> 8 votes

# Answer
**Python, 420 chars**

This uses a sort of blend of options 1 and 2: It assumes that brainfuck is implemented with big integers (I use a Sage implementation). Input a fractran program, for example, `33/20,5/11,13/10,1/5,2/3,10/7,7/2`. Then, pre-load a number, for example, `2^5`, at the cursor. Then, run the output of this python script. Wait 44 seconds. The result, `13^2` sits where the cursor started. I didn't wait for the answer for `2^7`.

```
s="[->>>+<<<]+["
for l in raw_input().split(','):
 a,b=map(int,l.split('/'))
 s+="[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>["+"[->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]<"*(b-1)+"[->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]<"+"[->+>+<<]>[-<+>]<"*a+"[-]>>[-<<+>>]<<<<<->>>>]<<]<<"
print s+">+<[->-<]>[-<+>]<]>>>[-<<<+>>>]"

```

This is my first brainfuck script. It can certainly be golfed further, but I've got other things to do until later tonight.

edit: rather than golf this further, I'm working on a solution for option 2. also, here's the output for the requested program:

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

```
> 5 votes

# Answer
## Perl, 326 characters

I am going to answer my own question hopefully to stimulate more answers. I am of course not eligible to win. This is option 2 with unbounded memory and cells, although it works on wrapping cells. Each fraction is converted into a single block of code. The newlines are for readability.

```
L:{$A=<>;
if($/eq$A){last L}
($B,$C)=eval$A;
$D=$E=$F=$G=$H=2;
while($C>1){
if($C%$H==0){
$C/=$H;
$R=">"x$H;
$L="<"x$H;
$D.=$R.'[-'.$L;
$E.=$R.'-'.$L;
if($H>2){$R.="+[->+<]]>[-<+>]<"}
else{$R.="+[-<+>]]<[->+<]>"}
$G=$R.$L.$G;
$H--}$H++}
$H=2;while($B>1){
if($B%$H==0){
$B/=$H;
$F.=">"x$H.'+'.'<'x$H;
$H--}$H++}
$I="+[-$I$D$E+$F$G]";
redo L}print$I

```

Here is the example output. This takes advantage of the fact that other characters are ignored as comments. This also appears to be a very short output compared to the other entries, although output size doesn't technically matter.

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

```
> 3 votes

# Answer
**Sage, 431 chars**

This is a completely new solution. I figured out some better ways of doing things in brainfuck, and this properly implements Option 2. Newlines added for clarity. This can probably be golfed further, but it involves rewriting the BF to have a lower loop depth.

```
exec"f=factor;
J=''.join;
Q=L(a,b):Lz:a*z+b*-z;M=Q('<>');
C=Lj,k:(Ll:'[-%s+%s+%s]%s[-%s+%s]%s'%tuple(map(M,[-j,-k,l,-l,l,-l,k])))(j+k);
print '>+[>>>+'+J(map(L(n,m):reduce(Lr,(p,e):'[-%s%s%s[[-]<<+>>]%s<<%s]'%(M(4-p),C(6-p,2),'[-'*(e-1),']'*(e-1),r),f(m),'[-<<<->>>%s]'%J(map(L(p,e):M(4-p)+Q('+-')(e)+M(p-4),f(n/m))))+'<<<'+C(3,2),[map(QQ,x.split('/'))for x in raw_input().split(',')]))+'<<<<+>[-<->]<[->+<]>]'".replace('L','lambda ')

```

Sample output:

Given the input `33/20,5/11,13/10,1/5,2/3,10/7,7/2`

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

```
> 3 votes

---
Tags: code-golf, brainfuck, code-generation
---


# Question
Title: Code Golf: What is the spaceship's fate? [ASCII art version]
# Background

In a galaxy (and possibly a universe) far, far away... there was a spaceship and a bunch of planets. A malfunction on board caused the spaceship to run out of fuel. It is now moving at a dangerously slow speed near a cluster of planets, from which it must escape! What will be the crew's fate?

# The Challenge

You are the lead programmer on the U.S.S. StackExchange. As such, you desire to write a simulator that will reveal whether or not you are doomed to crash land onto a planet, will escape the planetary system, or will be stuck in orbit forever.

The explosion on your spaceship, however, means that there was very limited computational resources. Your program must be as small as possible. Also, this means that the only possible way of inputting simulations to run is through ASCII art.

# The Simulation

In this quadrant of the multiverse, the laws of physics are slightly altered in order to accommodate ASCII art. This means that the cosmos is divided up into cells. Movement will be described in units of cells, and time will be in units of time steps.

The ship itself has momentum. If the ship moved +2 cells on the x axis and -1 cell on the y axis (shorthanded as (2,-1)) in the previous time step, and there is no gravitational field, then the ship will move with the exact same velocity on the next time step.

There will be several planets, all of which exert a gravitational field on the eight cells immediately surrounding it, which will effect the ship's velocity and will pull the ship closer to the planet. Being just "north" of a planet will result in a field pulling the ship one cell to the "south" with a force of (-1,0). Being just "northeast" of a planet will result in a force pulling the ship one cell to the "south" and one unit to the "west" with a force of (-1,-1).

The gravitational fields add a vector to the ship's momentum as it is leaving the cell with the gravity. If a ship just previously moved (2,-1) cells and is now in a gravitational field of (-1,1), then in this next time step it will move (1,0) cells. If the ship is in close proximity to multiple planets, then there will be multiple vectors to add.

# Input

On STDIN, you will receive an ASCII art representation of the planetary system that will show the coordinates of the planets and your ship's current velocity. There will be several planets in the form of @ signs, while there will be one spaceship in the form of a v^\<\> sign. The choice of symbol for the ship indicates the current velocity of the ship (before gravity has been added). For example, a \< means a velocity of one cell to the west, while a ^ means a velocity of one cell to the north. All empty space will consist of periods, which pad every line to be the same width. A blank line represents the end of input. Here is an example of an input:

```
.................
...@.@........v..
......@..@..@@...
..@..............
.......@..@......
.................

```

# Output

Output will be a single word on STDOUT, which will tell whether the ship will escape gravity, will crash land into a planet, or will orbit forever.

Escaping from gravity is defined as the ship moving off of the map. If the ship escapes, then your program must print the word "escape".

Crash landing is when a ship passes directly over a planet or ends up in the same cell during a time step. Note that it is not enough to simply calculate where the ship is every time step. A ship moving at a velocity of (5,5) will crash into a planet located at (1,1) even though straightforward calculation will mean that it will never visit that cell. A ship with a velocity of (5,6) will not crash land into the planet, however. If your spaceship crash lands, then your program must print the word "crash".

Orbiting may be the most difficult to detect. Orbiting occurs whenever the spaceship visits the same cell twiceand with the same velocity. If the ship orbits, then you should print the word "orbit".

Here is the output for the above example:

```
escape

```

## Explanation

Here is a map showing where the spaceship traveled in each time step in the above example:

```
   ^
.................
...@.@........v..
....^.@..@..@@...
..@..<.<<<.<.v...
.......@..@......
.................

```

It went south, turned to the west, travelled down a corridor, turned to the north, and narrowly escaped between to planets with a high velocity, all becuase of gravity.

---

# More cases for examination

```
...
^@.
...
orbit
...........
.>@.@......
.@......@..
....@......
crash (it crashes into the easternmost planet)
...
.@.
.v.
crash (momentum can't overcome gravity)
........
..@.....
..<.....
...@....
........
orbit (it gets trapped in a gravity well between two planets)

```

---

# Rules, Regulations, and Notes

This is code golf. Standard code golf rules apply. Your programs must be written in printable ASCII. You aren't allowed to access any sort of external database.

End Transmission

# Answer
> 6 votes
## C# ~~991~~ 984

```
struct P{public P(int x,int y){X=x;Y=y;}public int X,Y;}
class O:Exception{}
class C:O{}
List<P>p=new List<P>();
List<string>h=new List<string>();
P r,v,u;
void S(){
var i=0;
for(var l=Console.ReadLine();l!="";l=Console.ReadLine())
{u.X=l.Select((c,j)=>
{if(c=='@')p.Add(new P(j,i));else if(c!='.')
{r=new P(j,i);v=(c=='v'?new P(0,1):c=='<'?new P(-1,0):c=='^'?new P(0,-1):new P(1,0));}
return u;}).Count();i++;}
u.Y=i;
var x=new Action<string>(Console.WriteLine);
try{
while(true){
p.ForEach(q=>{var a=q.X-r.X;var b=q.Y-r.Y;
if(a<2&&a>-2&&b<2&&b>-2){v.X+=a;v.Y+=b;}});
var c=string.Join(".",r.X,r.Y,v.X,v.Y);
if(h.Contains(c))throw new O();
h.Add(c);
var z=new P(r.X,r.Y);var k=new[]{v.X,v.Y};var m=k.Min();var M=k.Max();
for(var j=1;j<=M;j++)
if((j*m)%M==0){
if(p.Contains(new P(z.X+(v.X==M?j:j*m/M),z.Y+(v.Y==M?j:j*m/M))))throw new C();}
r.X+=v.X;r.Y+=v.Y;
if(r.X<0||r.X>=u.X||r.Y<0||r.Y>=u.Y)throw new Exception();}}
catch(C){x("crush");}
catch(O){x("orbit");}
catch{x("escape");}}

```

The ungolfed (and slightly refactored) version is available at http://pastebin.com/yAKYvwQf

Running version: https://compilify.net/1n9 This has been slightly modified to be run on complify:

* no implicit array creation - ex: `new[]{1,2}`
* uses `return <string>` instead of `Console.WriteLine`, because that's how compilify.net works

---
Tags: code-golf, ascii-art, path-finding, printable-ascii
---


# Question
Title: Optimal short-hand roman numeral generator
**Goal:**
Write a function that takes a number as input and returns a short-hand roman numeral for that number as output.

**Roman Numeral Symbols:**

```
Symbol  Value
I       1
V       5
X       10
L       50
C       100
D       500
M       1,000

```

For an example of what I mean when I say "short-hand roman numerals", let's consider finding a roman numeral to represent 1983, because that is the year I was born. One option is to do this the normal way (10 letters):

**1983** = **MCMLXXXIII** = (1000 - 100 + 1000 + 50 + 30 + 3)

The other option is to do it the short-hand way (6 characters):

**1983** = **MXVIIM** = (1000 - (10 + 10) + 1000 + 3)

Do you know what this means?!?!!?? If I was roman I could have saved 4 characters every single time I wrote my birth date! Woot Woot!!

However, before I get ahead of myself in excitement, I have a question to write, so I should probably define the short-hand roman numeral rules so we are all on the same page:

**Short-Hand Roman Numeral Rules:**

1. Always consider symbols from left to right until there are no more characters to consider.
2. If there are no higher-valued symbols to the right of the current symbol:
    * Add the value of the current symbol to the running total of this roman numeral.
3. If there are higher-valued symbols to the right of the symbol you are considering:
    * Locate the rightmost highest-valued symbol to the right of the current symbol
    * Consider all the characters up to that symbol as one roman numeral
    * Calculate the value of that roman numeral using these steps
    * Subtract the value of that roman numeral from the running total of this roman numeral.
    * Move to the next symbol after the group you just considered
4. Each roman numeral must have at least 1 symbol in it.
5. That's it! Anything following these rules will be accepted!

**Examples:**

```
IIIIV = (-(1+1+1+1)+5) = 1  //Don't ask me why you'd want to do this!

VVX = (-(5+5) + 10) = 0  //Who said you couldn't represent 0 with roman numerals?!!?

VVXM = (-(-(5+5) + 10) + 1000) = 1000  //Again...don't ask me why you'd want to do this!

MXIIXMI = (1000-(10-(1+1)+10)+1000+1) = 1983  //Ahhh...such a great year :)

```

**Question Rules:**

1. Make a function that takes a single number as input and returns a roman numeral for that number as output using the above rules. Calculate the **codeGolfScore** of this function.

```
example input: 2011
example possible output: MMXI
another possible output: MMVVIVV     //(2000 + 10 - 4 + 5)

```
2. Using your function from rule 1, generate the roman numerals between -1000 (that's right, NEGATIVE one-thousand) and 3000. Then sum up the character length of these roman numerals to get your **totalCharacterCount**. Here's some pseudocode to clarify:

```
totalCharacterCount = 0;
for(currentNumber = -1000; currentNumber <= 3000; currentNumber++){
    totalCharacterCount += getRomanNumeral(currentNumber).length;
}
return totalCharacterCount;

```
3. **finalScore** = **codeGolfScore** \+ **totalCharacterCount**
4. Lowest **finalScore** wins!

Note: As the totalCharacter count will be in the ten-thousands+, the character-length algorithm should be top priority. Code-golf scores are just the tie-breaker in case multiple users find the optimal algorithm or algorithms that are close to each other.

Good luck, and have fun at your MMXII celebrations tomorrow night!!!

# Answer
## C++, 345 characters of code, 25021 roman numeral digits = 25366

```
int N[]={1,5,10,50,100,500,1000};int V(int s,int L){if(!L)return 0;int K=0,B,m=s%7+1;for(int k=1,b=7;k<L;k++,b*=7){if(s/b%7>=m){K=k;B=b;m=s/b%7;}}return K?V(s/B,L-K)-V(s%B,K):N[s%7]+V(s/7,L-1);}char r[99];char*f(int n){for(int L=1,B=7,i,j;1;L++,B*=7){for(i=0;i<B;i++){if(V(i,L)==n){for(j=0;j<L;j++){r[j]="IVXLCDM"[i%7];i/=7;}r[L]=0;return r;}}}}

```

deobfuscated a bit, with a driver:

```
int N[]={1,5,10,50,100,500,1000};
int V(int s,int L){
  if(!L)return 0;
  int K=0,B,m=s%7+1;
  for (int k=1,b=7;k<L;k++,b*=7) {
    if(s/b%7>=m){K=k;B=b;m=s/b%7;}
  }
  return K ? V(s/B,L-K)-V(s%B,K) : N[s%7]+V(s/7,L-1);
}
char r[99];
char *f(int n){
  for(int L=1,B=7;1;L++,B*=7) {
    for(int i=0;i<B;i++) {
      if(V(i,L)==n){
        for(int j=0;j<L;j++) {
          r[j]="IVXLCDM"[i%7];i/=7;
        }
        r[L]=0;
        return r;
      }
    }
  }
}
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
  printf("%s\n", f(atoi(argv[1])));
}

```

`V` computes the numerical value of a given roman numeral string `s` of length `L`. Strings are encoded base 7 (first digit is s%7, second digit is s/7%7, ...). Each digit is encoded with I=0, V=1, ..., M=6. `f` does a brute-force enumeration of possible roman numeral strings to find one that `V` evaluates to `n`.

The total number of roman numeral digits is optimal. The longest roman numeral needed for \[-1000,3000\] is 11 digits (e.g. -827=CMDDMLXXIII), which takes about 5 minutes on my machine.
> 5 votes

# Answer
## Haskell, 25637 (= 268 + 25369) 26045 (= 222+25823)

```
r 0="VVX"
r n=s(zip[1000,500,100,50,10,5]"MDCLXV")n ξ
ξ='ξ'
s[]q f
 |q<0=s[](5-q)f++"V"
 |q<1=""
 |r<-q-1='I':s[]r f
s ω@((v,a):l)q f
 |q>=v,f/=a=a:s ω(q-v)ξ
 |f==a,γ<-'I':a:s l(q-v+1)ξ,η γ<η(s l q ξ)=γ
 |f==ξ,γ<-s ω(v-q)a++[a],η γ<η(s l q ξ)=γ
 |True=s l q ξ
η=length

```

to be used as e.g.

```
GHCi> r 7
"VII"
GHCi> r 39
"XIL"
GHCi> r (-39)
"ICXLC"        --  "LLXILC" in my original version
GHCi> r 1983
"MXVIIM"
GHCi> r 259876
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMCXXIVM"

```

You can evaluate the length sum with the straightforward

```
GHCi> sum . map(length.r) $ [-1000..3000]
25369

```

Which takes something in the order of a minute.
> 5 votes

# Answer
## Ruby, 25987 (= 164 + 25823)

```
h=->i,d,v,k{i==0?'':i<v ?(a=h[v-i,x=d[1..-1],v/k,k^7]+d[0];i<0?a:(b=h[i,x,v/k,k^7];a.size<b.size ? a :b)):d[0]+h[i-v,d,v,k]}
r=->i{i==0?'DDM':h[i,'MDCLXVI',1000,2]}

```

You can call `r` directly to get the results. The sum over the specified range yields

```
> (-1000..3000).map{|i|r[i].size}.reduce &:+
25823

```

which is the optimal sum as with the other solutions.
> 2 votes

# Answer
# C# 23537 (639 characters of code + 22898 characters of output)

```
class M
{
    public static string R(int n, int? s = new int?())
    {
        var r = "";
        var D = new Dictionary<int, string> {{ 1000, "M"}, { 900, "CM"},{ 800, "CCM"},{ 500, "D"}, { 400, "CD"},{ 300, "CCD"},{100, "C"}, {90, "XC"},{80, "XXC"},{50, "L"}, {40, "XL"}, {10, "X"}, {9, "IX"}, {8, "IIX"}, {5, "V"}, {4, "IV"},{1, "I"}};
        if (n == 0) return "VVX";
        if (n == -1) return "IIIIIIV";
        if (n < 0) return N(n * -1);

        foreach(int k in D.Keys)
        {
            if (s.HasValue && k > s) continue;

            while(k <= n)
            {
                n -= k;
                r += D[k];
            }
        }

        return r;
    }

    public static string N(int n)
    {
        var D = new Dictionary<int, string> {{1, "I"}, {5, "V"}, {10, "X"}, {50, "L"}, {100, "C"}, { 500, "D"}, {1000, "M"}};

        int i = D.Keys.First(v => v >= n), m = D.Keys.Where(v => v < i).Max();

        return R(n + i, m) + D[i];
    }
}

```

To Calculate:

`Enumerable.Range(-1000, 3000).Sum(i => M.R(i).Length);`
> 0 votes

---
Tags: code-golf, roman-numerals
---


# Question
Title: How many mesas begin with a given string?
Let's call a non-empty list of strings a ***mesa*** if the following conditions hold:

> 1. Each listed string is non-empty and uses only characters that occur in the first string.
> 2. Each successive string is exactly one character longer than the preceding string.
> 3. No string in the list is a subsequence of any other string in the list.

The term "mesa" is from visualizing like this (where the `x`s are to be various characters):

```
    xx..x
    xx..xx
    xx..xxx
    .
    .
    .
    xx..xxx..x

```

NB: It's a mathematical fact that only finitely many mesas begin with a given string. Note the distinction between *subsequence* vs. *substring*; e.g., 'anna' is a subsequence (but not a substring) of 'banana'.

### Challenge:

* Write the shortest program that takes an arbitrary non-empty alphanumeric input string and outputs the number of mesas that begin with that string.

### Input (stdin):

* Any non-empty alphanumeric string.

### Output (stdout):

* The number of mesas that begin with the input string.

### Scoring:

* The winner is the program with the least number of bytes.

### Example mesas

Only one mesa starts with `a`:

```
a

```

Only one mesa starts with `aa`:

```
aa

```

Many mesas start with `ab`:

```
ab        ab        ab        ab        (and so on)
          baa       aaa       bbb
                    bbba      bbaa
                              baaaa
                              aaaaaa

```

# Answer
## GolfScript (106 103 chars)

```
n-..&1/:Z;]]0,\{.@+\{['']:E+.-2=,)E\{{`{+}+Z/}%}*{:x`{\1,+\{1$(@={\}*;}/0=!}+1$?!{.);[x]+\}*}/;}%.}do;,

```

Somewhere in the heart, of course, is some code from Is string X a subsequence of string Y?
> 2 votes

# Answer
### Ruby, 142 characters

```
m=->l{[*l[0].chars].repeated_permutation(l[-1].size+1).reduce(1){|s,x|l.any?{|y|x*''=~/#{[*y.chars]*'.*'}/}?s:s+m[l+[x*'']]}}
p m[[gets.chop]]

```

This algorithm is constructive, i.e. it builds all possible mesas for the input string and counts them. It makes the program really, really slow - but hey, it is codegolf.

Example runs:

```
> a
1
> aa
1
> ab
43

```
> 2 votes

---
Tags: code-golf
---