title: Choose Your Own Adventure

text:
# Question
Title: Choose Your Own Adventure
Choose Your Own Adventure books are a form of interactive literature where the reader must make decisions that affect the outcome of the story. At certain points in the story, the reader has multiple options that can be chosen, each sending the reader to a different page in the book.

For example, in a fantasy setting, one might have to decide on page 14 whether to venture into a mysterious cave by "jumping" to page 22, or to explore the nearby forest by jumping to page 8. These "jumps" can be expressed as pairs of page numbers, like so:

```
14 22
14 8

```

In most cases, there are many endings to the story but only a few good ones. The goal is to navigate the story to reach a good ending.

**Task:**

Given a list of "jumps" for a given book, your task is to determine a route that will lead to a specific ending. Since this is fairly easy, the true challenge is to do it in as few characters as possible.

This is **code golf**.

**Sample input (where 1 is the start and 100 is the goal):**

```
1 10
10 5
10 13
5 12
5 19
13 15
12 20
15 100

```

**Sample output:**

```
1 10 13 15 100

```

**Sample input:**

```
15 2
1 4
2 12
1 9
3 1
1 15
9 3
12 64
4 10
2 6
80 100
5 10
6 24
12 80
6 150
120 9
150 120

```

**Sample output:**

```
1 15 2 12 80 100

```

**Notes:**

* The list of jumps will be input by the user, either from a file or stdin. You may choose whichever is most convenient.
* The input will contain 1 jump per line, with the origin and destination separated by a single space.
* The lines in the input are not guaranteed to be in any specific order.
* A successful path will start at page 1 and end at page 100.
* You may assume there is at least 1 path to the goal. You do not need to find all paths, nor do you need to find the shortest. Just find at least one.
* The smallest page number will be 1. There is no limit to the largest page number. (You can assume that it will fit in the range of an int.)
* Loops may exist. For example, the list may have jumps from page 5 to 10, 10 to 19, and 19 to 5.
* There may be dead-ends. That is, a destination page might not have anywhere to jump to.
* Conversely, there may be unreachable pages. That is, an origin page might not be the destination of any jumps.
* Not all page numbers between 1 and 100 are guaranteed to be used.
* Your output should consist of a valid route of page numbers, starting with 1 and ending at 100, separated by spaces.

Remember, this is code golf, so the shortest solution wins!

**EDIT:** Added another sample for testing.

# Answer
### Golfscript, 58 57 chars

```
~]2/.,{:A{){=}+{0=}\+A\,\`{\+}+/}/]A+}*{)100=\0=1=*}?' '*

```

**Warning**: this is super-inefficient. It works by repeatedly squaring the adjacency matrix and then looking for a route; if there are `E` edges in the graph then it will find every path of length up to 2E (and the shorter ones it will find lots of times). It should give you a result for the first test case in a reasonable time, but if you want to try the second one make sure that you've got a few gigs of memory free and go for a long walk.

If you want a reasonably efficient solution then I offer at 67 chars:

```
~]2/:A,[1]]({A{{{?)}+1$\,,}%~!*},{({\-1==}+2$?\[+]+}/}*{100?)}?' '*

```
> 7 votes

# Answer
## Python, 232 213 157 143 135 132 chars (shortest path)

This implementation can handle all of the edge cases described (loops, dead ends, orphan pages etc.) and guarantees that it will find the shortest route to the ending. It is based on Djikstra's shortest path algorithm.

```
import sys
l=[k.split()for k in sys.stdin]
s={"100":"100"}
while"1"not in s:
 for i,j in l:
    if j in s:s[i]=i+" "+s[j]
print s["1"]

```
> 14 votes

# Answer
## Javascript: 189 Characters

This is a recursive solution that finds the shortest path through the adventure.

**Code-Golfed:**

```
a=prompt().split('\\n');b=0;while(!(d=c(b++,1)));function c(e,f,i,g){if(e>0)for(i=0;h=a[i++];){g=h.split(' ');if(g[0]==f){if(g[1]==100)return h;if(j=c(e-1,g[1]))return g[0]+' '+j}}}alert(d)

```

To test (**WARNING: infinite loop for bad input!**):

1. Copy one of the following input strings (or use a similar format to choose your own choose your own adventure):

* `1 10\n10 5\n10 13\n5 12\n5 19\n13 15\n12 20\n15 100`
    * `15 2\n1 4\n2 12\n1 9\n3 1\n1 15\n9 3\n12 64\n4 10\n2 6\n80 100\n5
    10\n6 24\n12 80\n6 150\n120 9\n150 120`
2. Paste that into the test fiddle's prompt.

**Formatted and Commented code:**

```
//Get Input from user
inputLines = prompt().split('\\n');

//Starting at 0, check for solutions with more moves
moves = 0;
while (!(solution = getSolution(moves++, 1)));

/**
 * Recursive function that returns the moves string or nothing if no
 * solution is available.
 *
 * @param numMoves - number of moves to check
 * @param startPage - the starting page to check
 * @param i - A counter.  Only included to make this a local variable.
 * @param line - The line being tested.  Only included to make this a local variable.
 */
function getSolution(numMoves, startPage, i, line) {
    //Only check for solutions if there are more than one moves left
    if (numMoves > 0) {
        //Iterate through all the lines
        for (i=0; text = inputLines[i++];) {
            line = text.split(' ');
            //If the line's start page matches the current start page
            if (line[0] == startPage) {
                //If the goal page is the to page return the step
                if (line[1] == 100) {
                    return text;
                }
                //If there is a solution in less moves from the to page, return that
                if (partialSolution = getSolution(numMoves - 1, line[1])) {
                    return line[0] + ' ' + partialSolution;
                }
            }
        }
    }
}

//Output the solution
alert(solution);

```

To test (**WARNING: infinite loop for bad input!**):

1. Copy one of the following input strings (or use a similar format to choose your own choose your own adventure):

* `1 10\n10 5\n10 13\n5 12\n5 19\n13 15\n12 20\n15 100`
    * `15 2\n1 4\n2 12\n1 9\n3 1\n1 15\n9 3\n12 64\n4 10\n2 6\n80 100\n5
    10\n6 24\n12 80\n6 150\n120 9\n150 120`
2. Paste that into the test fiddle's prompt.
> 3 votes

# Answer
## Ruby 1.9, 98

```
j=$<.map &:split
f=->*p,c{c=='100'?abort(p*' '):j.map{|a,b|a==c&&!p.index(b)&&f[*p,b,b]}}
f[?1,?1]

```

Ungolfed:

```
$lines = $<.map &:split
def f (*path)
    if path[-1] == '100' # story is over
        abort path.join ' ' # print out the path and exit
    else
        # for each jump from the current page
        $lines.each do |from, to|
            if from == path[-1] && !path.include?(to) # avoid loops
                # jump to the second page in the line
                f *path, to
            end
        end
    end
end

```
> 3 votes

# Answer
## Perl, 88 chars

basically a perlized version of Clueless' entry; pre-matches and post-matches are fun :)

```
@t=<>;%s=(100,100);until($s{1}){for(@t){chomp;/ /;$s{$`}="$` $s{$'}"if$s{$'}}}print$s{1}

```
> 3 votes

# Answer
# Python - ~~239~~ ~~237~~ 236

```
import sys
global d
d={}
for i in sys.stdin:
 a,b=[int(c) for c in i.split(' ')]
 try: d[b]+=[a]
 except: d[b]=[a]
def f(x,h):
 j=h+[x]
 if x==1:
  print ''.join([str(a)+" " for a in j[::-1]])
  exit()
 for i in d[x]:
  f(i,j)
f(100,[])

```

unfortunately, this tail-recursive solution is vulnerable to loops in the "story"...

**Usage**: cat ./test0 | ./sol.py Output for test case 1:

```
1 10 13 15 100

```

Output for test case 2:

```
1 15 2 12 80 100

```
> 1 votes

# Answer
## Scala 2.9, 260 256 254 252 248 247 241 239 234 227 225 212 205 characters

```
object C extends App{var i=io.Source.stdin.getLines.toList.map(_.split(" "))
def m(c:String):String=(for(b<-i)yield if(b(1)==c)if(b(0)!="1")m(b(0))+" "+b(0)).filter(()!=).mkString
print(1+m("100")+" 100")}

```

Ungolfed:

```
object Choose extends App
{
    var input=io.Source.stdin.getLines.toList.map(_.split(" "))
    def findroute(current:String):String=
    (
        for(branch<-input)
        yield
        if(branch(1)==current)
            if(branch(0)!="1")findroute(branch(0))+" "+branch(0)
    ).filter(()!=).mkString
    print(1+findroute("100")+" 100")
}

```

Usage:

Compile with `scalac filename` and run with `scala C`. Input is taken via `STDIN`.
To run on ideone.com, change `object C extends App` to `object Main extends Application` to run it as Scala 2.8.
> 0 votes

# Answer
## PHP, 166 146 138 chars

```
$a[]=100;while(1<$c=$a[0])for($i=1;$i<$argc;$i++){list($p,$q)=explode(' ',$argv[$i]);if($q==$c)array_unshift($a,$p);}echo implode(' ',$a);

```

Ungolfed :

```
$a[]=100;
while(1<$c=$a[0])
    for($i=1;$i<$argc;$i++){
        list($p,$q)=explode(' ',$argv[$i]);
        if($q==$c)array_unshift($a,$p);
    }
echo implode(' ',$a);

```

Usage :

```
php golf.php "1 10" "10 5" "10 13" "5 12" "5 19" "13 15" "12 20" "15 100"

```
> 0 votes

# Answer
I would put all of them into a 2d array and search all items with multiple loop, if they can reach the last item then I would collect related items in order into another results array, and from results I would choose an array which one is smaller.

EDIT =\> JAVA:I have also used recursive function, full code below;

```
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
public class Jumper {
    static int x = 0;
    public static ArrayList<ArrayList<String>> c = new ArrayList<ArrayList<String>>();
    public static void main(String[] args) throws IOException {
       //Read from line and parse into array
        BufferedReader in = new BufferedReader(new FileReader("list.txt"));
        ArrayList<String> s = new ArrayList<String>();
        String line = null;
        while ((line = in.readLine()) != null){s.add(line);}
        c.add(new ArrayList<String>());
            //When you get all items forward to method
        checkPages(0, s,Integer.parseInt(s.get(0).split(" ")[0]),Integer.parseInt(s.get(s.size()-1).split(" ")[1]));
    }

    public static void checkPages (int level,ArrayList<String> list,int from, int dest){
        if(level <= list.size()){
            for(int i=level;i<list.size();i++){
                int a = Integer.parseInt(list.get(i).split(" ")[0]);
                int b = Integer.parseInt(list.get(i).split(" ")[1]);
                if(a == from){
                    c.get(x).add(list.get(i));
                    if(b==dest){
                        c.add(new ArrayList<String>());
                        x++;
                    }else{
                        checkPages(i, list, b,dest);
                        c.get(x).remove(list.get(i));
                    }
                }

            }

        }
    }

}

```
> -1 votes

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


title: Creative Programming

text:
# Question
Title: Creative Programming
Make a story out of your programming. Example in JavaScript:

```
self.book = {
    "story": function() {
        var once = "upon",
            aTime = setTimeout(function() {
                // Code would continue...
            }, 1000)
    }
};

self.book.story();

```

**Stipulations:**

* Must run error-free before, during, and after it's compiled.
* You can only use up to two words for the story per String/name.
    + JavaScript Example:
    `var story = "Once upon a"; // Wrong (Using more than two words)`
    `var story = "Onceupona"; // Wrong (Using more than two "words")`
    `var onceUponA = "time"; // Wrong (more than two words as a variable name)`
    `var onceUpon = "a time"; // This is fine`
    `var story = "Once upon"; // This is fine`
* The story must be a complete sentence (at least).
* Having some sort of output (such as "printing" the story itself) is not necessary, but it's a plus.
* Bring some creativity into it.

Since there are no length rules, the answer with the most votes / best creativity will win. :)

# Answer
# JavaScript

Not sure how historically accurate this, but it's a mini-history of ECMAScript. Please feel free to suggest improvements.

```
function story() {
    var IE = {
        from: "Microsoft"
    },
        Netscape = {
            from: "Mozilla"
        };
    var setUp = {
        oncethere: "were two",
        browsers: IE + Netscape
    };
    var parts = {

        And: function() {
            var theyfought = "to be",
                theBest = "browser";
        },
        oneday: function() {
            var they = {
                added: function() {
                    var add = "scripting languages";
                    Netscape.language = add;
                    IE.language = add;
                    return add;
                },
                thought: function() {
                    if (what(they.added) === good) {
                        they.wouldBeat = "the other";
                    }
                }
            };

        },
        andso: function() {
            function callLanguage(name) { return name };
            Netscape.language = callLanguage("Javascript");
            IE.language = callLanguage("JScript");
        },
        butThen: function() {
            var ECMA = "Standards Committee";
            (function standardized(languages) {
                (function into() {
                    return "ECMAScript";
                })();
            })([IE.language, Netscape.language]);

        },
        theEnd: function() {
            return {
                andWe: "all lived",
                happilyEver: "after..."
            };
        },
        what: function(thing) {
            return thing;
        },
        good: true || false
    };
}
story();

```
> 18 votes

# Answer
Reminds me of LOLCode, everything is sort of a story (or at least a "conversation"):

```
HAI
CAN HAS STDIO?
I HAS A VAR
IM IN YR LOOP
    UPZ VAR!!1
    VISIBLE VAR
    IZ VAR BIGR THAN 10? GTFO. KTHX
KTHX
KTHXBYE

```
> 14 votes

# Answer
# JavaScript

```
'How';do{'computers'^Function}while(0);'they have'|'no power?'

```

The output is: `0` on console :D
> 14 votes

# Answer
It's not so much of a *story*, and what the program does has nothing to do with what the code says, but...

# C++

```
/* Preface (assuming nobody reads it anyway): */
#include <iostream>
#include <fstream>
#include <string>
#include <map>
#include <functional>
#include <time.h>
using namespace std;
int

/*Beginning   the*/ main(){//story:

#define   a   string
ofstream ing___water;   a   river;

#define   the
long   rivers,
each,  is
(a ( river +"of").length() > 4 );
a   normal ( river +"has   the");
a bility;   for ( float ing;  short (~1 - - 2 );){
char coal,  loaded,  ships,  on,  its,  water;
coal = is;  a   lot,   lighter;
if ( lighter  .compare ( normal ))water = 'H'*2+'O'; }

a   heavier,  ship,  may;  do { a   worse,  job;  a nd,  run;
a ground; }while ( "you"&&false)//ly
;try { a nd ( "navigate   through");
a ny, such ( normal.size()==rivers     ?

the  "ship" : may + "then"); }
catch ( exception ally ) { a wful;}} struct ural___damage {
long   before ( the   time_t o)                                                                                const{
return "to" == a( "harbour");
for ( a   rescue ("from   leaking"),
its ("load   or");o<the'r';) {
ofstream ing,  substances;
if ("not"=="even"||substances/*that*/.put( 'a').bad())
double   damage,  to,  both   the ((short) "river"[1]);
a nd   the ("overall   environment[2].");}}

a   sentient,  ship_owner,  should,  h;int //to
the operator<( struct ural___damage   might)                                                                                const{
a lso( "occur"), to( "his   own"),health( "when   not");
using   the ::map;
to  .find(  a ( "river   that's"),long( ~3 ) );
(to+="avoid")+=the "trouble   and";
(to+="cause")+=(less</*r*/ural___damage>()
(*this,/*seems like*/*this)?"is": a( "good   idea"));

return before ( the   time(0))||"is"==to +"late";}};

```

As plain text:

> Beginning the main story:
> define a string ofstreaming water a river;
> define the long rivers, each is a river of length \> 4;
> a normal river has the ability for floating short (~1--2) charcoal-loaded ships on its water; coal is a lot lighter if lighter compare normal water = H2O;
> a heavier ship may do a worse job and run aground while you falsely try and navigate through any such normalsize rivers, the ship may then catch exeptionally awful structural damage long before the time toconst return to a harbour for a rescue from leaking its load or other ofstreaming substances, if not even substances that put a bad double damage to both the short river \[1\] and the overall environment\[2\].
> a sentient ship\_owner should hint to the operator structural damage mightconst also occur to his own health when not using the map to find a river that's long(~3) to avoid the trouble and to cause less rural damage. this seems like this is a good idea. return before the time is to late.
> 13 votes

# Answer
# Brainfuck

```
+++++ +   + +++++ +++++ +++++   +++++ +++++
  +   +   + +     +   + +         +   +
  +   +++++ +++   +++++ +++       +   +++++
  +   +   + +     + ++  +         +       .
  +   +   + +++++ +   + +++++   +++++ +++++

+++++ +   + +     +   +   +++++ +   + +.+++
[   + ]+  + +      + +    +   + ++  + +
+   + + [ + ]       +     +   + + + + +++
+   + +  ++ +       +     +   + +  ++ +
+++++ +   + +++++   +     ++++. +   + +++++

++++  +++++ +++++ +++++  +   +
+   + +   + +   +   +    ++  +
++++  +++++ +++++   +    + + +
+   + + +   +   +   +    +  ++     +
++++  +   + +   + +.[+]  +   +    +

+++++ +   + +++++ +   + +++++ +++++ +++++ .
+     +   + +     +  +  +     +   + +     +
+++   +   + +     +++   +++   +++++ +++++ +
+     +   + +     +  +  +     + ++      +
.     +++++ +++++ +   + +++++ +   + +++++ .

```

I "accidentally" ran this through `bf` and that came out

```
It's Me

```

\*SCNR\* :)
> 12 votes

# Answer
# BASIC

slightly simplistic, but very true for those of us who stay up till 3 AM debugging...

```
On Error GoTo sleep

```
> 10 votes

# Answer
## Python Love

```
def initely(there, were):
    if not None:
        atLeast = not "many"
    who.made("my heart")
    "beat as", you.do(_,_)
    return your.smile
warm = "ly"

try:
    toKeep = "it" + warm
    while walkingHome: pass
    ing(emptyWindows)
except:ionally = "sad"
finally: it = "'s over"

your = not any([1, "to me"]) or "just my toy" and \
type("",(), {"youWere": "more"} )()

your.smile = "kept me"
_ = warm in "these days"

but, you = "were failed by", your #love: me

if _: only(I)
hadKnown, you.were = "innocent as a", lambda \
young, blueEyed: \
[("but ", "the retribution") for myMisdoings #comes
in "time"]

sometimes, you.do = ("make me", #think of who
you.were)
""in "another story"

I, who = "I've been", your#'s
"sit" in "my room"
"look"in"g at" #old photographs
#relentlessly remembering
the, love = you.do, "give to me"
who.made = all #these mistakes

"Had thought" + it + "would go"
on = "inf"+initely(
"Oh!, the", "fool I've")#been
regretting = all("my errors") #today

_, im = "hold" in "paraly","sys"
_ = open; "cans" and "cans of"
_ = _(__import__(#ed beer
im).#in a d
argv[0]#id
).read() #sad poems

love, is_ = the, "thing I" #miss forever
iTake = "my camera"
go = "out to have"
new, photos = "to look", _ #at

print ("them" if 0 #they're dull
else _); "they make" + "me think of", love("lost", "for me")
```

EDIT: This is now a (if cheated) quine.
> 8 votes

# Answer
bash or other shells on Unix or Linux:

```
who am I & whereis edit || eliza && find ada

```
> 3 votes

# Answer
I really can't claim this one to myself, but I think it would be really good for you all to be able to look at it.

This is called PHP Sad Poem, and comes from here.

```
$timeWaiting = 0;
while (!$you->near($me)) {
    $me->thinkAbout($you);
    switch (true) {
        case $timeWaiting < 5:
            $me->wait($you);
            break;
        case $timeWaiting < 10:
            $me->worry();
            break;
        case $timeWaiting < 20:
            $me->lookFor($you);
            break;
        case $timeWaiting < 40:
            $me->worry();
            $me->lookFor($you);
            break;
        case $timeWaiting < 80:
            $me->worry();
            $me->cry();
            $me->lookFor($you);
            $me->lookFor($you);
            $me->lookFor($you);
            break;
        case $timeWaiting < 160:
            $me->worry();
            $me->cry();
            $me->drink();
            $me->lookFor($you);
            $me->lookFor($you);
            $me->lookFor($you);
            $me->thinkAbout($you);
            $me->thinkAbout($you);
            $me->cry();
            $me->lookFor($you);
            $me->lookFor($you);
            $me->drink();
            $me->drink();
            break;
        default:
            throw new CantLiveWithoutYou();
            die(“alone”);
        }
    $timeWaiting++;
}
$me->happy = true;

```
> 2 votes

---
Tags: code-challenge
---


title: Set the chessboard

text:
# Question
Title: Set the chessboard
## Objective

Given an arbitrary chessboard as standard input (in which each piece is on a square), produce as standard output a list of moves needed to regularize, or set up, the chessboard. The moves need not be legal, yet no piece may be placed above another. The program must warn about any missing or additional pieces; in the latter case, the program need not produce a list of moves.

A regular chessboard is a chessboard having sixteen pieces in their initial positions described in the Laws of Chess section of the *FIDE Handbook*. A partially regular board is a chessboard missing at least one of the regular board's sixteen pieces or including one or more additional pieces in ranks 3-6 (consisting of empty squares in the regular board) yet otherwise regular.

## Input format

### Description

Eight lines of eight characters each make up a chessboard. A hyphen (`-`) represents an empty square. The last line's first character represents the regular position of white's king's rook (a1 in algebraic notation) and is always a black square; both its adjacent squares are white squares (see Figure 1).

Each kind of piece has a distinct uppercase or lowercase letter for identification (see Figure 2). No two pieces having the same letter (excepting pawns) are present in a regular board, and white and black have exactly eight pawns each.

### Figure 1: regular board

```
rnbkqbnr
pppppppp
--------
--------
--------
--------
PPPPPPPP
RNBKQBNR

```

### Figure 2: piece names, counts, and letters

```
Piece    Count    White    Black
--------------------------------
King       1        K        k
Queen      1        Q        q
Bishop     2        B        b
Knight     2        N        n
Rook       2        R        r
Pawn       8        P        p

```

## Output format

The program shall output one line per move. Each move follows the format `<source><target>`, where `<source>` is the algebraic notation for an occupied square and `<target>` is the algebraic notation for an unoccupied square. (Note: Algebraic notation is described in Appendix C to the *FIDE Handbook*.) For example, the program shall output `a4a5` to move the piece on square `a4` to square `a5`.

The generated moves shall fully regularize the chessboard if possible. If any pieces are missing from the board, the program shall output the moves necessary to partially regularize the board and then a line containing 'M' followed by the letters of all such pieces. An 'M' line shall not be output unless there is at least one missing piece.

If any additional pieces exist on the board, the program shall either a) leave them in ranks 3-6, partially regularizing the board or b) entirely omit the list of moves from its output, even if pieces are missing. The former option (a) may not be possible in some input cases. The program shall output a line containing 'A' followed by the letters of all additional pieces after all other output (including an 'M' line if present). An 'A' line shall not be output unless there is at least one additional piece.

## Score

The program's score shall be the product of its character count and the total number of moves taken for the ten test cases in `regboards.txt`.

## Test cases

I have posted **regularizable and nonregularizable test cases** on Gist. On jsFiddle, I have posted the **test case generator/move checker** to help you check your solution. Put the board in the first box and the move list in the second box (including neither an 'M' nor an 'A' line) and click "Make Moves" to execute the moves your program has generated. To see examples of valid output, you can run my **ungolfed solution** on the test cases (taking 482 moves).

# Answer
## Python, score 150552 = 306 moves * 492 chars

```
import os,re
B=os.read(0,99)
R='rnbkqbnr-'+8*'p'+37*'-'+8*'P'+'-RNBKQBNR'
def P(x,y):print'%c%d%c%d'%(97+x%9,8-x/9,97+y%9,8-y/9)
F={}
M=''
t=B.find('-',18,56)
for x in range(71):
 if R[x]>'@':
  if R[x]==B[x]:B=B[:x]+'-'+B[x+1:]
  else:
   y=B.find(R[x])
   if y<0:M+=R[x]
   else:F[x]=y;B=B[:y]+'-'+B[y+1:]
A=re.sub(r'[-\n]','',B)
if M:print'M',M
if A:print'A',A
else:
 while F:
  p=[x for x in F if x not in F.values()]
  if p:x=p[0];y=F[x];P(y,x);del F[x]
  else:x=min(F);P(F[x],t);F[x]=t

```

The code records a list of moves `F` which will regularize the board. This list is made by choosing a piece from the input board `B` to go to each location of the final board `R`, and 'crossing it off' of the input board. Any missing or additional pieces are computed as a side effect of this computation. Then the moves from `F` are made, using the temporary location `t` to break any cycles.
> 2 votes

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


title: Organize a tournament

text:
# Question
Title: Organize a tournament
Here is a real question somebody asked me. Suppose you have `n` teams, one terrain.

* Each team must play each other team exactly once.
* The number of times a team plays two matches in a row should be minimized.

The problem is hard if not optimized. Your program should be able to answer this question for up to 6 teams (at least) in a reasonable time (say less than an hour). For 5 teams I have a working program which works in less than a minute.

Here is an example for 5 teams.

```
$ organize_for 5
[(3,5),(1,2),(4,5),(1,3),(2,4),(1,5),(2,3),(1,4),(2,5),(3,4)]

```

And another for 6 teams.

```
$ organize_for 6
[(2,4),(1,5),(2,3),(1,6),(3,5),(1,4),(2,5),(1,3),(4,6),(1,2),(3,6),(4,5),(2,6),(3,4),(5,6)]

```

NB for 3 and 4 teams, you'll have at least two occurrences of a team playing two matches in a row.

To win: make the shortest program to answer this problem fast enough to give you a correct answer for 6 teams.

**Bonuses**:

1. The median of the median of the waiting time between two matches for all teams should be maximized. Example: from organize\_for 5 ; nb match between the next one (sorted, median is the one in the center)

```
team 1 -> 1, 1, 1 (sorted => 1, 1, 1, median => 1)
team 2 -> 2, 1, 1 (sorted => 1, 1, 2, median => 1)
team 3 -> 2, 2, 2 (sorted => 2, 2, 2, median => 2)
team 4 -> 1, 2, 1 (sorted => 1, 1, 2, median => 1)
team 5 -> 1, 2, 2 (sorted => 1, 2, 2, median => 2)

medians: (1, 1, 2, 1, 2), sorted => (1, 1, 1, 2, 2)
median of the medians = 1.

```
2. Generalize for `k` terrains. All match have the same duration.

* The most important rules remains a team shouldn't do a match just after another.
    * The global time for all matches should be minimized

# Answer
Haskell: **291** chars

Another solution which terminate only if there is a solution without any collision (5 and 6). It is also very fast:

```
import System.Environment
import Data.List
a n=[(x,y)|x<-[1..n],y<-[1..n],x<y]
s []=[[]]
s (m:[])=[[m]]
s ((x,y):(x',y'):xs )
 |(x==x')||(x==y')||(y==x')||(y==y')=s((x,y):xs++[(x',y')])
 |0<1=[(x,y):ys|ys<-s((x',y'):xs)]
main=do
 args <- getArgs
 print $ head $ s $ a (read(head args)::Int)

```
> 1 votes

# Answer
## Python 282 247 chars

```
import sys
n=int(sys.argv[1])+1
r=range
l=[(i,j)for i in r(1,n)for j in r(i+1,n)]
m=[(),()]
while l:
 o,p=h=l.pop(0);v=[]
 for k in r(len(m)-1):g=m[k]+m[k+1];v+=[o in g or p in g]
 m.insert(v.index(0)+1,h)if min(v)<1 else l.append(h)
print m[1:-1]

```

UPD: working for n\>4, for testing add:

```
lst = m[1:-1]
conflicts = 0
for i in range(len(lst)-1):
    if lst[i][0] in lst[i+1] or lst[i][1] in lst[i+1]:
        conflicts += 1

print 'Conflicts: {}'.format(conflicts)

```
> 1 votes

# Answer
Haskell **585** chars

```
import System.Environment
import Data.Ord
import Data.List
a::Int->[(Int,Int)]
a n=[(x,y)|x<-[1..n],y<-[1..n],x<y]
b::[(Int,Int)]->Int
b ((x,y):((z,t):rest))|x==z=1+b ((z,t):rest)
 |x==t=1+b ((z,t):rest)
 |y==z=1+b ((z,t):rest)
 |y==t=1+b ((z,t):rest)
 |otherwise=b ((z,t):rest)
b _=0
c l=(b l,l)
d [] _=[[]]
d l minimal=[x:s|x<-l,s<-take 10 $ filter (\ts->b ts<minimal) (d (delete x l) minimal)]
e n minimal=take 1 $ sortBy (comparing fst) $ map c (d (a n) minimal)
f []=False
f _=True
g n=head $ filter f $ map (e n) [0..]
main = do
 args<-getArgs
 print $ g (read (head args)::Int)

```

Here is the non code golfed version:

```
import System.Environment
import Data.Ord
import Data.List

all_matches :: Int -> [(Int,Int)]
all_matches n = [ (x,y) | x <- [1..n], y <- [1..n], x < y ]

price :: [(Int,Int)] -> Int
price ((x,y):((z,t):rest))
    | x==z = 1 + price ((z,t):rest)
    | x==t = 1 + price ((z,t):rest)
    | y==z = 1 + price ((z,t):rest)
    | y==t = 1 + price ((z,t):rest)
    | otherwise = price ((z,t):rest)
price _ = 0

addPrices xs = (price xs, xs)

myPerm [] _ = [[]]
myPerm xs minimal = [x:ys | x <- xs,
                    ys <- take 10 $ filter (\ts -> price ts < minimal) (myPerm (delete x xs) minimal)]

find_best_under n minimal = take 1 $ sortBy (comparing fst) $ map addPrices ( myPerm (all_matches n) minimal)

isNonEmpty [] = False
isNonEmpty _ = True

find_best n = head $ filter isNonEmpty $ map (find_best_under n) [0..]

main = do
    args <- getArgs
    putStrLn $ show $ find_best (read (head args)::Int)

```

It only search for local optima. But in this case, local optima are also global one up to 6 teams.
> 0 votes

---
Tags: code-golf, optimization, combinatorics
---


title: Optimize matrix chain multiplication

text:
# Question
Title: Optimize matrix chain multiplication
This challenge is to compute the most efficient multiplication order for a product of several matrices.

The size of the matrices is specified on a single line of standard input. You should print to standard output a list of integers indicating the order in which to do the multiplications to minimize the total multiplication cost.

## example 1

### input

```
5x6 6x12 12x100 100x7

```

## output

```
3 2 1

```

The input line will be a space-separated list of matrix sizes, each of which is the number of rows, followed by an `x`, followed by the number of columns. For the example, there are 4 matrices to multiply together (so 3 total multiplications), and since matrix multiplication is associative they can be done in any order.

The output should be the order in which to perform the multiplications to minimize total cost. This should be a space-separated list of integers representing the index of the multiplication to perform next. For N matrices, this list should contain the numbers 1 through N-1, inclusive. For example 1, the output `3 2 1` means you should do the `12x100 * 100x7` multiplication first, then the `6x12 * 12x7` multiplication (the second matrix times the result of the previous step), then finally the resulting `5x6 * 6x7` multiplication.

The matrix multiplications will always be compatible, i.e. the number of columns of a matrix will match the number of rows of the subsequent matrix. Assume the cost of multiplying two matrices `AxB * BxC` is `A*B*C`.

Your code must handle lists of up to 100 matrices, each of dimension up to 999, and do so in a reasonable time.

## example 2

### input

```
5x10 10x5 5x15 15x5

```

### output

```
1 3 2

```

or

```
3 1 2

```

## example 3

### input

```
22x11 11x78 78x123 123x666 666x35 35x97 97x111 111x20 20x50

```

### output

```
2 3 4 5 6 7 8 1

```

Note: for verification, the best total cost for the three examples is 9114, 750, and 1466344.

Shortest code wins!

# Answer
### Ruby, 176 172 205 characters

Here is another version (several chars longer) which will also run for large input in reasonable time.

```
q=(gets.split<<$_[/\d+$/]).map &:to_i
r=Hash.new{|h,i|h[i]=Hash.new{|h,j|h[j]=1e12;h[j]=i==j ?[0,[]]:(i...j).map{|k|a,c=r[i][k];b,d=r[k+1][j];[a+b+q[i-1]*q[k]*q[j],c+d+[k]]}.min}}
$><<r[1][q.size-1][1]*' '

```

First version: straight recursive implementation in Ruby. It does a complete search and thus might be slow on large inputs.

```
k=->m{m[2]?(1..m.size-2).map{|l|s=k[m[0,l]+m[l+1..-1]];[m[l-1]*m[l]*m[l+1]+s[0],[l]+s[1].map{|u|u<l ?u:u+1}]}.min: [0,[]]}
$><<k[(gets.split<<$_[/\d+$/]).map &:to_i][1]*' '

```
> 1 votes

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


title: Airplane Navigation

text:
# Question
Title: Airplane Navigation
You are tasked with planning a flying route for a local airplane delivery company. You need to route an airplane from point A to point B. You just can't start at A, point the airplane at B, and go, however, as the prevailing winds will blow you off course. Instead you need to figure out which direction you should point the airplane so that it will fly directly to B, taking the wind into account.

**input**

7 floating-point numbers, encoding A\_x, A\_y, B\_x, B\_y, S, W\_x, W\_y. These are the coordinates of your start and destination, the airspeed of your airplane, and the strength of the wind along the x and y axes (the direction the wind blows *to*, not from).

**output**

You should print the angle in degrees (rotating counterclockwise from the positive x axis) that the plane should point to reach B in a straight line. Print `GROUNDED` if the wind is so strong as to make the trip impossible.

You may round to the nearest degree, and do so with any method you would like (up/down/nearest/...).

**examples**

inputs

```
0 0 10 0 100 0 -50
0 0 10 0 50 -55 0
3.3 9.1 -2.7 1.1 95.0 8.8 1.7

```

outputs

```
30
GROUNDED
229

```

Shortest code wins.

# Answer
### J - 155 chars

```
h=:3 :0
'c w s'=.(([:j./[:-~/2 2$4{.]),([:j./5 6{]),4{])0".y
'T X'=.+.w*+c%|c
C=.-_1 o.X%s
>((s>|w)*.(-T)<s*2 o.C){'GROUNDED';360|<.360+(C+{:*.c)*180%o.1
)

```

For example:

```
   h '0 0 10 0 100 0 -50'
30
   h '0 0 10 0 50 -55 0'
GROUNDED
   h '3.3 9.1 -2.7 1.1 95.0 8.8 1.7'
229

```

Remove the `0".` ahead of `y` if you don't mind J numeric syntax (`_` for unary negation):

```
   h 0 0 10 0 100 0 _50
30

```

As I mentioned in my Perl answer, I'm only learning J, but liking its power.
> 1 votes

# Answer
### Perl - 222 chars

```
use Math::Trig;($A,$a,$B,$b,$s,$W,$w)=split' ',<>;$c=atan2($b-$a,$B-$A);$A=atan2($w,$W);$S=sqrt($W*$W+$w*$w);$X=$S*sin($A-$c);$T=$S*cos($A-$c);$C=asin($X/$s);print((-$T>$s*cos($C))?"GROUNDED":(360+rad2deg($c-$C))%360,"\n")

```

Straighforward algorithm, and really only golfed by squeezing whitespace and variable name length, but I thought we needed a first answer here. I've been learning some J for golfing; I suspect simply translating to J (or Ruby) will readily beat this. Off to try those.

`$X` = crosswind component, `$T` = tailwind component. We're grounded if the tailwind is actually a headwind (i.e., negative) and stronger than our airspeed. Otherwise, `$C` is the wind correction angle that we subtract from our course `$c` to get our heading. We need to turn far enough to balance the crosswind with the cross-track component of our velocity.
> 2 votes

# Answer
# Perl: 193

Admittedly this is (mostly) DCharness's Perl code: but who doesn't like self-rewriting source?

```
use Math::Trig;$/=' ';@i=<>;$_='1=atan2(3-1,2-0);0=atan2(6,5);2=sqrt(6*6+5*5);5=2*sin(0-1);3=2*cos(0-1);6=asin(5/4);print-3>4*cos 6?GROUNDED:int rad2deg(1-6),"\n"';s/((?<!\w)\d)/\$i[$1]/g;eval

```

Also it will output degrees out of spec (i.e. \<0 or \>360), but did I mention self-rewriting source?
> 0 votes

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


# Question
Title: Shana tova umetuka! (Happy Jewish New Year!)
Write the shortest program, in the language of your choice, that takes as input a year on the Hebrew calendar, and outputs the corresponding Gregorian date for Rosh Hashana, in YYYY-MM-DD format.

```
~$ rh 5771
2010-09-09
~$ rh 5772
2011-09-29
~$ rh 5773
2012-09-17

```
* The input may come from either the command line or from stdin, whichever is more convenient.
* You may assume that the year will be between 5600 (1839) and 6000 (2239), inclusive.

# Answer
> 1 votes
## CPAN 5.10, 109

This is even cheaper than the C# solution, for reasons enumerated below. Code first: (character count as a difference to `perl -E''` as usual)

```
$ perl -E'$_="DateTime::Calendar::Hebrew";/:/;eval"require $_";say$`->from_object(object,$_->new(year,<>,month,7))->ymd'

```
* steals Peter Olson's idea of just outsourcing it to the library
* CPAN's current release of `DateTime::Calendar::Hebrew` doesn't install out of the box, you need to patch it.
* needs Perl 5.10. No earlier, no later.

At least it's short.

# Answer
> 4 votes
### Ruby, 192 181 165 characters

```
require'date'
s=(-6+235*n=gets.to_i)/19*765433+73848;e=s/u=25920
$><<Date.jd(347641+e+([h=s%u/19440,84>>e%7+h&1,v=e%7*(374454>>n%19&1-h&s%u/9923),v,n-5765].count 1))

```

Input is given as a single number on STDIN.

*Edit 1:* Several arithmetic transformations saved quite a few characters.

*Edit 2:* There was some room for improvement.

# Answer
> 3 votes
## C#, 212

This might seem cheap, but here I go:

```
using System;using System.Globalization;class P{static void Main(){int y=int.Parse(Console.ReadLine())-5771;var a=new HebrewCalendar().AddYears(new DateTime(2010,9,9),y);Console.Write(a.ToString("yyyy-MM-dd"));}}

```

with spacing

```
using System;
using System.Globalization;
class P
{
    static void Main()
    {
        int y = int.Parse(Console.ReadLine()) - 5771;
        var a = new HebrewCalendar().AddYears(new DateTime(2010, 9, 9), y);
        Console.Write(a.ToString("yyyy-MM-dd"));
    }
}

```

---
Tags: code-golf
---


title: Markov Chain Beatbox Generator

text:
# Question
Title: Markov Chain Beatbox Generator
Just an idea I had the other day: Making beats following a Markov Chain of predefined sounds.

I remember someone did a beatbox with Google Translate and the German language (follow the link and press listen).

So, the challenge is to build a text input to Google Translate from a given chain. Or you can use musical notes and play it yourself :).

You can make a program reading a line with the number of beats, another with their names and a matrix representation of the probabilities (you can choose the representation).

You may also make a function with those three arguments.

E.g.

\[input\]

```
20
pv zk bschk kkkk
[[.1, .4, .5, 0.],
 [.3, .2, .3, .2],
 [0., .3, .2, .5],
 [.1, .8, .1, 0.]]

```

\[output\] something like:

```
pv zk bschk zk pv bschk zk pv zk bschk kkkk pv bschk zk bschk bschk bschk zk kkkk bschk

```

The starting probability is the same for each beat.

That's not a code-golf challenge because I would like to see some nice solutions (be creative).

Extra points if you invent new beats and/or choose a table of probabilities that gives nice beats most of the time.

If you want, you can use real beats (In many languages it's easy to open `.wav` files, like the `wave` module in Python) and generate music! Here are some free sample beats.

I may post a reference implementation if needed.

# Answer
> 6 votes
I made these tracks:

http://soundcloud.com/belisarius/sets/golf-music

Using the following transition matrix:

```
{{10,  1,  3/2, 2},
 {1/2, 10, 3/2, 2},
 {1/2, 1,  10,  2},
 {1/2, 1,  3/2, 10}}

```

And the following program in Mathematica:

```
musicGen[n_, notes_, transMatrix_] :=
 Module[{
          im := IdentityMatrix[Length@notes],
          a  := Array[2^(# - 1) &, Length@notes],
          soundLength = .1  n,
          which
          },
  which[x_] := Position[x, 1][[1, 1]];
  Sound[Join[
    (SoundNote /@ notes[[
        which[#] & /@
         NestList[
          RandomChoice[transMatrix[[which@#]] -> im] &,
          RandomChoice@im,
          n - 1]
        ]]
     )
    ],
   soundLength]
  ]
tm = {{10, 1, 3/2, 2}, {1/2, 10, 3/2, 2}, {1/2, 1, 10, 2}, {1/2, 1, 3/2, 10}}
notesSet = {"Snare", {"Slap", "Shaker"}, {"OpenTriangle", "Maracas"}, "RideBell"};
m = Array[If[#2 == 5 || #2 == #1, 10, #2/2] &, {Length@notesSet,Length@notesSet}];
mg = musicGen[100, notesSet, tm]

```

# Answer
> 3 votes
Being German, I was almost falling off my chair laughing at this creative abuse of our language. :-)

Here is some Scala. I am encoding the probabilities in a map that maps the beat to a list of successor beats in which the beats occure with a frequency proportional to their probability. An infinite lazy evaluated stream of beats is created, whose first 10 beats are skipped to get the appropriate randomness of the first output beat. We return the appropriate number of beats from the beginning of that stream. I use the type parameter T to be shorter and generic.

```
def markovChain[T](length : Int, nodes : Seq[T], probabilities : Map[T, Seq[T]]) : Seq[T] = {
  def randomElement(seq : Seq[T]) = seq(Random.nextInt(seq.length))
  def chain(node: T): Stream[T] =
    Stream.cons(node, chain(randomElement(probabilities(node))))
  return chain(randomElement(nodes)) drop(10) take(length)
}

```

which can be called like this:

```
val nodes = List("pv", "zk", "bschk", "kkkk")

val probabilities = Map(
  "pv" -> List("pv", "zk", "zk", "zk", "zk", "bschk", "bschk", "bschk", "bschk", "bschk"),
  "zk" -> List("pv", "pv", "pv", "zk", "zk", "bschk", "bschk", "bschk", "kkkk", "kkkk") ,
  "bschk" -> List("zk", "zk", "zk", "bschk", "bschk", "kkkk", "kkkk", "kkkk", "kkkk", "kkkk"),
  "kkkk" -> List("pv", "zk", "zk", "zk", "zk", "zk", "zk", "zk", "zk", "bschk"))

markovChain(20, nodes, probabilities) foreach (s => print (s + " "))

```

# Answer
> 1 votes
I wrote a Javascript function. However, it have begun beatboxing itself...

```
function bschk(jk,pv,kkkk){jkjk='pv jk bschk kkkk'.split(' ');boom='indexOf';eval(
function(jkpv){for(pvpv=0,bschkpv='';pvpv<jkpv.length;jkpvpv=jkpv[pvpv++].split(' '),
bschkpv+=String.fromCharCode(jkjk[boom](jkpvpv[0])+jkjk[boom](jkpvpv[1])*4+jkjk[
boom](jkpvpv[2])*16+jkjk[boom](jkpvpv[3])*64));return bschkpv}((
'bschk jk bschk jk  kkkk kkkk bschk jk  bschk pv kkkk jk  pv bschk bschk pv  bschk '
+'jk kkkk jk  jk pv bschk jk  bschk pv kkkk jk  pv pv bschk pv  jk jk bschk jk  jk '
+'kkkk kkkk pv  bschk kkkk kkkk jk  bschk kkkk kkkk jk  pv bschk bschk pv  jk kkkk '
+'pv jk  jk pv bschk jk  pv jk kkkk jk  pv bschk bschk jk  bschk kkkk bschk pv  bsc'
+'hk pv kkkk jk  jk pv bschk jk  bschk kkkk bschk jk  pv jk bschk jk  kkkk kkkk bsc'
+'hk jk  jk kkkk bschk jk  pv bschk bschk pv  jk bschk bschk pv  bschk bschk bschk '
+'pv  pv pv kkkk jk  bschk jk kkkk jk  bschk kkkk bschk pv  pv kkkk bschk jk  jk jk'
+' bschk jk  bschk kkkk bschk jk  kkkk jk bschk jk  pv jk kkkk jk  pv bschk bschk j'
+'k  jk bschk bschk pv  pv kkkk bschk pv  jk bschk bschk jk  jk kkkk kkkk pv  pv pv'
+' kkkk pv  pv kkkk bschk pv  bschk jk bschk jk  pv kkkk bschk pv  kkkk jk bschk jk'
+'  pv kkkk bschk pv  kkkk pv bschk jk  kkkk bschk bschk jk  kkkk pv bschk jk  kkkk'
+' bschk bschk jk  bschk pv bschk jk  kkkk kkkk bschk jk  kkkk kkkk bschk jk  jk kk'
+'kk bschk jk  jk kkkk kkkk pv  kkkk jk bschk pv  kkkk jk bschk pv  kkkk bschk kkkk'
+' pv  jk bschk bschk jk  pv kkkk kkkk pv  bschk bschk bschk jk  kkkk bschk bschk j'
+'k  kkkk bschk kkkk pv  jk bschk bschk jk  kkkk bschk bschk pv  kkkk bschk bschk p'
+'v  jk bschk bschk pv  kkkk bschk kkkk jk  kkkk pv bschk jk  kkkk bschk bschk jk  '
+'kkkk pv bschk jk  kkkk bschk bschk jk  bschk pv bschk jk  kkkk kkkk bschk jk  kkk'
+'k kkkk bschk jk  jk kkkk bschk jk  kkkk bschk bschk pv  jk kkkk kkkk pv  pv pv kk'
+'kk jk  bschk jk kkkk jk  kkkk bschk jk jk  jk jk bschk jk  jk kkkk jk jk  kkkk bs'
+'chk bschk pv  kkkk jk bschk pv  pv pv bschk pv  kkkk jk bschk pv  kkkk bschk kkkk'
+' pv  kkkk jk bschk jk  jk kkkk kkkk pv  jk kkkk pv jk  jk pv bschk jk  pv jk kkkk'
+' jk  pv bschk bschk jk  bschk kkkk bschk pv  bschk pv kkkk jk  jk pv bschk jk  bs'
+'chk kkkk bschk jk  pv jk bschk jk  kkkk kkkk bschk jk  jk kkkk bschk jk  pv bschk'
+' bschk pv  jk bschk bschk pv  kkkk bschk kkkk pv  bschk jk bschk jk  jk kkkk kkkk'
+' pv  jk kkkk bschk pv  jk pv kkkk pv  kkkk bschk kkkk pv  kkkk jk kkkk jk  pv bsc'
+'hk bschk jk  jk bschk bschk jk  pv kkkk bschk jk  jk jk bschk jk  pv bschk bschk '
+'pv  kkkk jk bschk jk  bschk kkkk kkkk pv  jk kkkk kkkk pv  pv pv kkkk pv  jk bsch'
+'k bschk pv  kkkk jk bschk jk  jk kkkk bschk pv  jk kkkk kkkk pv  kkkk bschk bschk'
+' jk  kkkk bschk bschk jk  kkkk bschk bschk jk  kkkk bschk bschk jk  kkkk bschk jk'
+' jk  jk jk bschk jk  jk kkkk jk jk  kkkk bschk jk jk  kkkk bschk bschk pv  kkkk b'
+'schk bschk pv  bschk jk bschk jk  jk kkkk jk jk  kkkk bschk kkkk pv  jk jk bschk '
+'jk  jk kkkk kkkk pv  bschk jk bschk jk  kkkk bschk kkkk pv  jk kkkk kkkk jk').split
('  ')));return ckckboom;}

```

Usage example : `bschk(20,'pv jk bschk kkkk'.split(' '),[[.1,.4,.5,0],[.3,.2,.3,.2],[0,.3,.2,.5],[.1,.8,.1,0]])`

# Answer
> 0 votes
Just a reference implementation in Python:

```
from random import random

def find(num, pdf):
    ''' Find position of number in CDF from PDF (must sum 100%) '''
    cdf = (sum(pdf[:i+1]) for i in range(len(pdf)))
    for i,j in enumerate(cdf):
        if num < j:
            return i

def build(t, beats, table):
    node = int(random()*len(table))
    nodes = [node]
    for i in range(t-1):
        node = find(random(), table[node])
        nodes.append(node)
    return ' '.join(beats[i] for i in nodes)

```

And a test program:

```
table = [[.1, .4, .5, 0.],
         [.3, .2, .3, .2],
         [0., .3, .2, .5],
         [.1, .8, .1, 0.]]

print(build(20, 'pv zk bschk kkkk'.split(), table))

```

And some outputs:

```
pv zk bschk zk kkkk zk bschk kkkk zk zk zk bschk kkkk zk bschk zk pv bschk kkkk zk
zk bschk kkkk zk zk kkkk zk bschk kkkk zk bschk zk pv zk pv zk zk bschk kkkk bschk
kkkk zk zk pv bschk bschk zk zk kkkk zk kkkk zk zk kkkk zk pv zk bschk kkkk zk

```

But none of them makes a really good beatbox because there's too much `kkkk` :).

---
Tags: code-challenge, word-puzzle, markov-chain, music
---


title: Illuminate a Mirrored Room

text:
# Question
Title: Illuminate a Mirrored Room
## Goal

In this competition, you are given a random room with one candle inside. The goal is to write the shortest program (this is golf) that determines what parts of the room are illuminated by the candle, by replacing the dark spots with `@`'s. The program should take a room from STDIN, with the output printed to STDOUT.

## Example Input/Room

```
+------+
|  C   |
|      +--+
|  \      |
+---------+

```

The candle is represented with a `C`, and the walls/mirrors are represented with `|`,`-`,`/`, or `\`. The walls themselves are mirrors. The corners of the room are represented with a `+`.

Rooms will never have diagonal walls, and light will never be able to escape out of the room.

Also, the first character on a line is always going to be part of the wall off the room. The absolute last character on each line is going to be the opposite wall of the room. No characters between these two are going to be outside of the room.

## Light and Reflection

The candle emits eight (laser-like) beams of light in eight basic directions: N, S, E, W, NE, SE, SW, and NW. These rays of light bounce off of the mirrors as described below:

```
Old Direction of Travel | Mirror | New Direction
N S E W NE SE SW NW       /        E W N S -- -- -- --
N S E W NE SE SW NW       \        W E S N -- -- -- --
N S E W NE SE SW NW       |        - - - - NW SW NE SW
N S E W NE SE SW NW       -        - - - - SE NE SW NE

```

A `-` represents the light being absorbed. Light is always absorbed by C's or +'s. It is important to note that the lights reflects off of a mirror only when it is occupying the same space as the mirror. These rules are much easier to understand when you draw the reflection out on paper.

## Example Output

As output, the program should print an image of the illuminated room, with dark spots written as an `@`, light spots left blank, and mirrors unaffected. For the above example, the output would be:

```
+------+
|  C   |
|@   @ +--+
| @\      |
+---------+

```

This means that, if you drew out the beams of light, they will never reach the spaces marked with `@`.

## More examples

```
Input:
+-----+
|     |
|     |
|  C  |
|     |
|     |
+-----+
Output:
+-----+
| @ @ |
|@   @|
|  C  |
|@   @|
| @ @ |
+-----+

Input:
+-----+
|  \  |
|/ C \+-+
|       |
|  \ - ++
+------+
Output:
+-----+
|  \ @|
|/ C \+-+
|      @|
| @\ -@++
+------+

```

# Answer
> 2 votes
## Python, 292 chars

```
import sys
R=''
for x in sys.stdin:R+='%-97s\n'%x[:-1].replace(' ','@')
M={'/':'-98/d','\\':'98/d'}
for d in(-98,-1,1,98,99,97,-97,-99):
 if d>98:M={'|':'d^2','-':'-d^2'}
 p=R.find('C')
 while 1:
  p+=d
  if R[p]in' @':R=R[:p]+' '+R[p+1:]
  elif R[p]in M:d=eval(M[R[p]])
  else:break
print R,

```

Reads in the room, makes it rectangular, then walks out from the candle in all directions. M contains the active mirror characters and their effect (`/\` for the cardinal directions, `|-` for the others)

Can handle rooms up to 97 characters wide.

# Answer
> 2 votes
## c -- 504

Relies on K&R default function calling semantics. Very straight forward implementation except for the fiddle stuff with bouncing the rays.

```
#define N M[x+y*97]
#define Y abs(y)
#define O M[c]==
#define E else break;
int j[]={-98,-97,-96,-1,1,96,97,98},c,x,y,p,s,M[9409];main(){for(;
(c=getchar())!=-1;){if(c==10)x=0,++y;else{if(c==67)p=x+y*97;if(c==32)
c=64;N=c;++x;}}for(x=0;x<8;++x){y=j[x];c=p;do{c+=y;if(O'@')M[c]=32;s=y/Y;
if(O 92)if(y%2){y=s*(98-Y);}E if(O'/')if(y%2){y=s*-(98-Y);}E if(O'|')
if(~y%2){y=s*(97+(97-Y));}E if(O'-')if(~y%2){y=s*-(97+(97-Y));}E}while
(!(O'+')&&!(O'C'));}for(y=0;x=0,N!=0;++y){for(;N!=0;++x)putchar(N);
putchar(10);}}

```

## Ungolfed

```
//#include <stdio.h>
int j[]={ -98, -97, -96, /* Increments to move around the array */
           -1,       1,
           96,  97,  98},
  c, x, y, p, s, /* take advantage of static initialization to zero */
  M[9409]; /* treat as 97*97 */

main(){
  /* read the map */
  while((c=getchar())!=-1/*Assume the deffinition of EOF*/){
    /* putchar(c);  */
    if (c=='\n')
      x=0,++y;
    else {
      if (c=='C') p=x+y*97; /* set start position */
      if (c==' ') c='@'; /* The room starts dark */
      M[x+y*97]=c; ++x;
    }
  }
  /* printf("Start position is %d (%d, %d)\n",p,p%97,p/97); */
  /* Now loop through all the direction clearing '@' cells as we
   * encounter them
   */
  for(x=0;x<8;++x){
    y=j[x];c=p; /* y the increment, c the position */
    /* printf("\tposition %d (%d, %d) '%c'\n",c,c%97,c/97,M[c]); */
    /* printf("\tdirection = %d (%d, %d)\n",y,-(abs(y)-97),(y+98)/97-1); */
    do {
      c+=y;
      /* printf("\t\tposition %d (%d, %d) '%c'\n",c,c%97,c/97,M[c]); */
      /* We ought to do bounds checking here, but we rely on  *
       * the guarantee that the room will be bounded instead. */
      if(M[c]=='@') M[c]=' ';
      /* The reflections are handles
       *   + Stop or not stop based on the even/oddness of the increment
       *   + New direction is a little fiddly, look for yourself
       */
      s=y/abs(y); /* sign of y (need for some reflections) */
      if (M[c]=='\\') if (y%2){ y=s* (98-abs(y));     }else break;
      if (M[c]=='/')  if (y%2){ y=s*-(98-abs(y));     }else break;
      if (M[c]=='|')  if (~y%2){y=s* (97+(97-abs(y)));}else break;
      if (M[c]=='-')  if (~y%2){y=s*-(97+(97-abs(y)));}else break;
      /* printf("\t\t\tdirection = %d (%d, %d)\n",y,97-abs(y),(y+98)/97-1); */
    } while (!(M[c]=='+')&&!(M[c]=='C'));
    /* printf("\t...hit a %c. Done\n",M[c]); */
  }
  /* print the result */
  for(y=0;x=0,M[x+y*97]!=0;++y){
    for(;M[x+y*97]!=0;++x)
      putchar(M[x+y*97]);
    putchar('\n');
  }
}

```

## Validation

```
$ gcc -g -o candle candle_golfed.c
$ for f in candle_room*; do (./candle < $f) ; done
+------+
|  C   |
|@   @ +--+
| @\      |
+---------+
+------+
|  C   |
|@   @ +--+
|  /@ @ @ |
+---------+
+------+
| @/   |
|@   @ +--+
|  C      |
+---------+
+------+
|  \@ @|
|@   @ +--+
|  C      |
+---------+
+-----+
| @ @ |
|@   @|
|  C  |
|@   @|
| @ @ |
+-----+

```

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


# Question
Title: Interpreter for a 99 Bottles of Beer program
Write a program (in a first language A) that interprets a "99 Bottles of Beer" program and a FizzBuzz program (both in a second language B) on its standard input. The output should go to standard output; you may implement the interpreter as a function in languages lacking standardized I/O interfaces.

## Constraints

The 99-Bottles program must come from either this site's problem or from http://99-bottles-of-beer.net/. Link to (do not copy and paste) the 99-Bottles program in your answer. The specific output is not important; what matters is whether the interpreter produces exactly the same output as a more complete one does.

You may write the FizzBuzz program yourself, or you may obtain it from the Internet or another source. Do not copy and paste the program into your answer in the latter case.

Both languages (and the 99-Bottles program) must have existed prior to September 22, 2011 (when this challenge was first posted). Specifically, you may not invent your own language for the specific purpose.

Any interpreter that hardcodes a non-whitespace character or string to be sent to the output (or that accesses the Internet) is cheating and not permissible. For example, an interpreter that contains "beer", "Buzz", or even "b" as a string or character literal is not acceptable, but looping from 1 to 99 is acceptable if a corresponding print statement is not hardcoded.

Both languages' names must not begin with the same letter and must not have any three character substring in common. For example:

* APL and AWK begin with the same letter, and so do C, C++, and C#.
* JavaScript and VBScript have SCR in common.

Additionally, the 99-Bottles and FizzBuzz programs must not be valid in language A or any other language that the interpreter depends on – the *direct* use of eval, exec, or similar language features or methods to compile and execute them is expressly forbidden.

## Scoring

The score is the sum of:

* **Ten** times the interpreter's character count
* **Ten** times the FizzBuzz program's character count.
* The 99-Bottles program's **actual** character count (because it should not be a golfed program). This excludes any leading and trailing whitespace but includes whitespace used for indentation. Each newline counts as one character.

For verification, include the code of everything you have written yourself, and link to any published sources you have used.

# Answer
> 3 votes
## JavaScript interpreter for C (3834)

### Interpreter (180 * 10 = 1800)

f() is the function to be called.

```
function prvarf(x){a=arguments;i=0;s+=(t=x.replace(/%./g,function(){return a[++i]}));return t}function f(x){Function(x.replace(/int/g,'var').replace(/#|ma/g,'f//'))(s='');return s}

```

### 99-Bottles (1074)

http://99-bottles-of-beer.net/language-c-844.html

### FizzBuzz (96 * 10 = 960)

Adapted from one of the programs at http://perl.guru.org/scott/misc/golf.html:

```
main()
{int b=0;for(;++b<101;)printf(printf("%s%s",b%3?"":"Fizz",b%5?"":"Buzz")?"\n":"%d\n",b);}

```

# Answer
> 1 votes
A fun one. I don't think it broke any of the rules you laid out, but it might be considered cheating.

VB.NET (2010, needs inline `Action(Of t1, t2)`), running on Windows, 362:

```
Imports System.Windows.Forms
Module A
Sub Main()
Dim b As New WebBrowser
IO.File.WriteAllText("C:\t.htm","<body></body><script>"&Console.In.ReadToEnd&"</script>")
b.Navigate("file:///C:/t.htm")
AddHandler b.DocumentCompleted,Sub(sender,e)
Console.Write(b.Document.GetElementsByTagName("body")(0).InnerHtml)
End Sub
Do
Application.DoEvents
Loop
End Sub
End Module

```

It interprets JavaScript. If you run this, you'll need to go into the Task Manager and stop the process because I just looped infinitely to save characters. You'll also need to make sure there's a reference to System.Windows.Forms in the project.

I haven't tested it yet, but I will as soon as I can.

99 Bottles of Beer, *2134 characters*:

http://99-bottles-of-beer.net/language-javascript-1079.html

FizzBuzz, ~~117~~ 113:

```
for(b=document.body,i=0;++i<=100;)b.appendChild(document.createTextNode(i%3?i%5?i:'Buzz':i%5?'Fizz':'FizzBuzz'));

```

For a total score of 3620 + 1130 + 2134 =

# ~~6,924~~ 6,884

Oh well...

---
Tags: code-challenge, interpreter
---


# Question
Title: Change a non-floating point number the largest step
Declare a numeric variable that is **not** floating point and do an operation that changes the value with the largest amount of difference so the result of the variable is far from the original value.

Solutions will be scored based on the magnitude of the difference between initial value and the value after changed, and shortness of code.

**Edit:**
I realize that this was a bit vague - sorry about that, it's my first try on code golf...

I want to also emphasize that the result must not cause overflow. So once the variable is declared with a specific type (which must not be floating point), the result would have to be valid within that type.

# Answer
## Java (55 26 19 chars, Diff: 2^64-1 = 18446744073709551615)

Given a very unclear spec on what we're supposed to be doing, here's a best try :-) Obviously I will easily be beat out by languages that have arbitrary precision integers like Python or APL/J.

```
long o=Long.MIN_VALUE;o+=Long.MAX_VALUE+Long.MAX_VALUE;

```

Demo: http://www.ideone.com/7HyCW

**EDIT**: Shorter version, making use of Long underflow to wrap around from `MIN_VALUE` to `MAX_VALUE` (26 chars):

```
long o=Long.MIN_VALUE;o--;

```

Demo: http://www.ideone.com/Qfao7

**EDIT 2:** Shortest yet taking into account `@ratchet freak`'s suggestions:

```
long o=1L<<63;o=~o;

```

Demo: http://www.ideone.com/2M9oa
> 3 votes

# Answer
## D (15 chars 2^64-1 difference)

```
ulong o=0;o=~o;

```

uses unsigned long and logical NOT to get max value

note that using `ucent` would get me to 2^128-1 difference (if it were to be implemented at least)
> 2 votes

# Answer
## Haskell - 8 characters (Infinite difference)

`f=f.(+1)`

Use `f` on `Integer`.
> 1 votes

# Answer
## C with SSE2 (79 chars, Difference: 2^128-1 = 3.4e38)

```
#include<emmintrin.h>
main(){__m128i v=_mm_set1_epi8(-1);v=_mm_xor_si128(v,v);}

```

This initially sets the 128 bit unsigned int `v` to its maximum value, and then changes this value to 0 by XORing `v` with itself.
> 1 votes

# Answer
### Golfscript

```
2{.?}9*

```

7 chars, unimaginably large difference. (The loop executes 9 times. The first time maps 2 -\> 2^2 = 4. The second time maps 4 -\> 4^4 = 256. The third time maps 256 -\> 256^256 ~= 3.23 * 10^616. The fourth time overflows memory, but not the datatype...)
> 1 votes

# Answer
# J - 16 characters

```
a=.<.<:(a=.2)^31

```

The value of a changes from 2 to 2147483647. The calculation makes the value become float, but the final result is integer.

There are also extended integers, but I don't know if they would be acceptable.

```
a=.(a=.0)+!100000x

```

Yes, that really spells out mathematically as !100000. J can crunch it (in a few minutes), brute force.
> 1 votes

# Answer
## Python (13 chars, Difference: 9^(9^9) (369,693,100 *digits*!))

```
a=0;a=9**9**9

```

I believe that the result of this operation is not a float, isn't it?

If that's problem because it doesn't yield the result...

## Mathematica (11 chars, Difference: only 15,151,335 digits)

If it's still a problem because this value is not the maximum *possible*, then, `a=2^1073741696;a*=-1` (20 chars) will do the work.
> 0 votes

# Answer
### bc 15chars:

On my system I can go until 8^8^8 without error, but 6^6^6 would already be too long to report it here, so take 5^5^5 as an example; 7^7^7 is in the range of one minute on a single core 2Ghz machine. With 8 you should have some time left.

```
echo "k=8^8^8;k*=-1;k" | bc

```

printable result for one page:

```
echo "k=5^5^5;k*=-1;k" | bc

```

-1911012597945477520356404559703964599198081048990094337139512789246\ 52053024261580301205938651973985026558644015579446223535921278867380\ 69722884101469159866020879618967571957018392816603380476112259755336\ 26101001482651123413147768252411493094447176965282756285196737514395\ 35754247909321920664188301178716912255242107005070906467438287085144\ 99502565861944615431835113798491336917799281274338404315492368555267\ 83596374102105331546031353725325748636909159778690328266459182983815\ 23028693657287369142264813129174376213632573032164528297948686257624\ 53622180176732249405676428193600787207138370723553054463561539464011\ 85348493792719514594505508232749221605848912910945189959948686199543\ 14766693801303717616359259447974616422005088507946980448713320513316\ 07391342305401988725700383298012460501970134673971759090273894939238\ 17315786996845899794781068042822436093783946335265422815704302832442\ 38551508231649096728571217170812323279048181726832751011274678231741\ 09858886837085220007117334922539133223007561471804290075276777933523\ 06200618286012455254243061006894805446584704820650982664319360960388\ 73625851074707434063628697657670269925864995355797631817390255089133\ 12232947439303439561613283340728316634982581452268620043077990846881\ 03804187368324800903873596212919633602583120781673673742533322879296\ 90720549059562140688882599124458184237959786347648431567376092362509\ 03715117989414242622702200662864868678687101829808728025606931019492\ 80830825044198424796792058908817112327192301455582916746795197430548\ 02640464685400273399386079859446596150175258696581144756851004156868\ 77309037124825353438392853975987494584970500382250124892840018265900\ 56251286187629938044407340142347062055785305325034918189589707199305\ 66218851296318750174353596028220103821161604854512103931331225633226\ 07664362366882968502088394961428304847391139916696226499485636852347\ 12873294796680884509405893951104650944137909502276545653133018670633\ 52132302846051943438139981056140065259530073179077271106578349417464\ 26847209561346473277485842382748996687550525043942182321913572230540\ 66715373374248543645663782045701654593218154053548393614250664498585\ 40330746646854189014813434771465031503795417577862281177658587694168\ 0908203125
> 0 votes

# Answer
## BrainF\***, 3 characters, theoretically unlimited difference

```
[+]

```

Some implementations of BF wrap. "True" BF allows for unlimited integers. This has a difference of whatever you want it to be, plus it's only 3 characters long :)
> 0 votes

---
Tags: code-golf
---


# Question
Title: Simulate a (gravity-based) billiard-ball-type computer
## The Machine

A billiard-ball type machine is composed of only the symbols `\` `_` `/` along with upper- and lower-case letters, spaces, and the number `1`.

`\` and `/` are ramps. A ball coming from above will be deflected to either the right or left side, respectively. For both ramps, if a ball comes from either side, it will be deflected downward.

`_` is a logic element. The logic performed by it is the most un-billiard-like part of the computer. First, a ball coming from the left or right continues in the same direction. A ball coming from above will be stopped. Then, after the end of its execution (see Running the Machine below), if the number of balls crossing/landing on it is positive even number, then a single ball is released from the bottom of the element.

A space does nothing. Any balls coming from any direction fall straight down due to gravity.

Lowercase letters are inputs. All inputs will either be a single 1 or 0.

Uppercase letters are outputs. The number outputted will be the number of billiard balls that hit its location.

The number `1` releases a extra billiard-ball at that location. It represents a logical 1.

All characters besides `\_/` cause any ball coming from any direction to fall straight down due to gravity.

Balls never combine, split, or collide. They are only created when released from an input, a `_`, or a `1`. They are only destroyed when they fall straight down onto a `_`.

Example machine-

```
1 a
\_/ b
  \_/
 \/
 /\ /
_  _
A  B

```

There will never be any blank lines in a machine, but the `_`'s may make it appear that there is a blank line.

## Running the Machine

A machine is run in layers, or rows. All billiard-ball movement on the top layer is performed before anything happens on the second layer.

The machine

```
ab
\_A
 C

```

is run as follows:

First, it prompts for the input `a` in the form `a:`. The user will then input a 1 or 0 (followed by enter). It repeats this for the input `b`. This is the end of the first layer. I am going to assume that the user entered a 1 for both inputs.

It then traces out the path of the first ball (from `a`), which goes along the `\`, across the `_`, into the `A`, and falls down to the spot under the `A`. It then traces out the path for the second ball (from `b`), which goes straight down onto the `_` and terminates. This is the end of the second layer.

Now, before the third layer, since the `_` has had two balls cross over it, it releases one ball. The output `A` has had one ball cross over it, so it outputs `A:1`.

For the third layer, it traces the path of the first ball (from the `_`), which goes though the `C` and falls straight down. The second ball (which fell through the `A`) also falls straight down.

Now, before the fourth layer, since the output `C` had one ball travel over it, it outputs `C:1`.

Since the fourth layer is blank, the program terminates.

The total result should look like

```
a:1     (the user entered the one)
b:1     (same here)
A:1
C:1

```

## The Goal

Your goal is to take a machine from STDIN and simulate it by taking inputs and printing output as needed to STDOUT. The first part of the input to your program will consist of the machine to be run, followed by a blank line. Any input letters encountered should cause your program to prompt for input in the form of the input name followed by a colon. Any output should be shown in the form of the output name, followed by a colon, followed by the number of balls passing over that spot.

This is golf.

## Examples

A wire crossing

```
ab
\/
AB

```

An XOR gate

```
ab1
\_/
 C

```

A full adder

```
1 a
\_/ b
  \_/
 \/
 /\
_ __/
 \_/
  \/c
 \\_/
  _S1
\  \/
 __/
  /
 _
\__
 C

```

# Answer
> 2 votes
## JavaScript (392 423)

Assumes machine is set in a variable called `m`, then alerts the final output.

```
l=m.split(q='\n');o='';for(r=Array(z=l[i=0].length);i<l.length;i++){L=l[i];n=Array(z);for(c=0;c<z;n[c]=N,r[c++]=R){C=L[c];N=~~n[c];R=~~r[c];if(C>'`'){N+=x=~~prompt(C);R+=x;o+=C+': '+x+q}else if(C=='\\'||C=='/'){for(d=c+(g=C=='/'?-1:1);L[d]=='_';r[d]+=R,d+=g);if(L[d]>'@'&L[d]<'[')r[d]+=r[c];n[d]=~~n[d]+R}else if(C<'2')N+=R+=~~C;else if(C!='_')o+=C+': '+R+q}for(c=0;c<z;c++)if(L[c]=='_')n[c]+=(r[c]%2)?0:r[c]>0;r=n}alert(o)

```

Sample source (runs adder machine, see history for less golfed sources): http://jsfiddle.net/96yLj/12/

**Spoilers:**

> \- `r` tracks the # of balls across current row, `n` tracks # of balls across next row.
> \- Algorithm: process each row character by character, but process `_`'s last.
> \- Algorithm: `\` -\> follow `_` and increase `r` until non-`_`. Same for `/` but in reverse direction. At the end increase `n` for gravity pulling balls down. `g` holds direction.
> \- `if(L[d]>'@'&L[d]<'[')r[d]+=r[c];` is for the bug mentioned in **Edit 1**. The reason we can't just say `r[d]+=r[c];` is because `\_/` will double-count balls when processing `/`
> \- `else if(C<'2')` handles both cases `'1'` and `' '`, which `~~C` turns into 1 and 0, respectively.

---

**Edit 1:** Fix bug with ball running over `_` not included in `A` for sample code.

---
Tags: code-golf, simulation
---


# Question
Title: Implement Shamir's Secret Sharing reconstruction
Shamir's secret sharing scheme is a simple way of protecting a secret by splitting it into several parts needed to reconstruct it.

Your task is to implement Shamir's Secret Sharing reconstruction over the Finite Field defined by the prime `1928049029`. If you have any doubts about what this means, just ask or see Finite Field & Finite Field Arithmetic in wikipedia (more resources below).

## Input

Input is done using stdin. First comes an integer `k`, then k lines follow. Each of these lines contains a pair of integers `x y` that represent a secret. In other words `f(x) = y` in the original polynomial that was used to construct the secrets.

The number of secrets given is always enough to construct the corresponding secret.

## Output

Output to stdout the reconstructed secret.

## Examples

**Input:**

```
5
1 564797566
2 804114535
4 1354242660
6 1818201132
7 503769263

```

**Output:**

```
1234

```

**Input:**

```
7
1 819016192
2 1888749673
3 1737609270
4 365594983
5 1628804870
6 1671140873
7 492602992

```

**Output:**

```
456457856

```

## Resources

Wikipedia article

Paper

Finite field Source: Wikipedia

Finite field arithmetic Source: Wikipedia

Lagrange polynomial Source: Wikipedia

Chapter on Finite field arithmetic

# Answer
### bash, 271 chars

```
r(){
[ ${1/0/} ]&&{ r $(($2%$1)) $1;((t=u,u=v-$2/$1*u,v=t));}
}
read
((N=1928049029,n=0))
while read x[$n] y[$n]
do((n++))
done
for((i=n;z=(z+l)%N,i--;))do
for((j=n,l=y[i];j--;))do
((u=0,v=1,d=x[j]-x[i],M=N+d))
r M N
[ ${d/0/} ]&&((l=l*x[j]%N*(u+N)%N))
done
done
echo $z
```

The newlines could be replaced in most cases with semicolons, but I don't think there's any unnecessary whitespace.

(I hadn't realised before today that bash's integers are 64-bit - very helpful).

For bash the recursive GCD (exploiting global state) seems to be more compactible than the iterative one. This is mostly straightforward; the interesting trick is `[ ${d/0/} ]&&foo` which is effectively `if [ $d -ne 0 ];then foo;fi`
> 5 votes

# Answer
199 characters in Octave:

```
m=@(x)mod(x,1928049029);[d,l]=scanf('%d');c=d(1);e=repmat(int64(d(2:2:l)),1,c);[_,b]=gcd(e-e',1928049029*ones(c));b=eye(c)+m(e.*b);x=b(1,:);for i=2:c;x=m(x.*b(i,:));end;disp(m(sum(m(x'.*d(3:2:l)))))

```
> 3 votes

# Answer
### Golfscript, 114 112 111 110 109 65 (86) chars

If you don't care about getting results this week, 65 chars suffice:

```
~](;2/0\:X{~\.X{0=}%^\{\.@- 1928049029:P.,\@{@*\%(!}++?**}+/+P%}/

```

But if you're looking for efficiency, it's slightly longer at 86 chars:

```
~](;2/0\:X{~\.X{0=}%^\{\[.0](@-[1928049029:P%P]{.~/{\.(;@@~@*-+\}+2*.1=}do;0=*}+/+P%}/

```

This is dissected in far more detail than I want to repeat here on my blog.

---

Mainly not my work, but cribbing heavily from Nabb gives 47 chars:

```
n%(!\:A{~A{~;.3$- 1928049029:N((?1or**}/\/+N%}/

```

Note: I've only reasoned about this code: trying to run it would be pointless given the length of time and amount of memory it would use.
> 3 votes

# Answer
## Golfscript - ~~52~~ 46 (67)

A brute force approach for modular inverses in 46 characters. Repeatedly computes a^(N-2) with arbitrary precision integers.

```
n%(!\:A{~A{~;.3$-.!+1928049029:N((?**}/\/+N%}/

```

Implementing the extended Euclidean algorithm only costs us an additional 15 characters.

```
n%(!\:A{~A{~;.3$-:|!1\1928049029:N{@2$|3$/*-\|\:|%.}do;;**}/\/+N%}/

```

This code is fully detailed on my blog post, including some alternatives for computing the modular multiplicative inverse.
> 3 votes

# Answer
**Lua 444 Chars**

Works for the example on the wiki page

```
3
2 1942
4 3402
5 4414

```

But somehow does not work for the examples here on this page. If anyone can find the error?

Non-golfed version:

```
-- Reconstruct shamir secret
-- convention, poly = {[0]=a0,a1,...,an}
i=io.read
f=math.fmod
w=1928049029
k=i():match"%d+"
x={} -- Will contain X values
y={} -- Will contain Y values
p={} -- will contain lagrange polynomials

-- Read data
for j=0,k-1 do
    x[j],y[j]=i():match("(%d+) (%d+)")
    print(j,x[j],y[j])
end
-- Multiplication and scaling function
function mul(p,q,s)
    -- multiply polies
    r={} -- poly to be returned
    for k=0,#p do
        for l=0,#q do
            r[l+k]=r[l+k] or 0 -- if the coeff for degree l+k of x doesn't exist, put 0
            p[k]=p[k] or 0 -- if p hasn't got a coeff for x^k
            q[l]=q[l] or 0 -- idem for q
            r[l+k]=(r[l+k]+s*p[k]*q[l]%w -- calculate increment for coeff for x^(l+k)
        end
    end
    -- Debugging
    io.write"Multiplied "
    printPoly(p)
    io.write"With       "
    printPoly(q)
    io.write("And scaling factor ",tostring(s),"\n")
    io.write"Yielding   "
    printPoly(r)
    return r
end

function printPoly(p) -- "Pretty" printing of the polynomial
    for k=#p,1,-1 do
        io.write(tostring(p[k] or 0),"x^",tostring(k),"+")
    end
    io.write(p[0])
    io.write"\n"
end
function egcd(a,b)
    if a == 0 then
        return b, 0, 1
    else
        local g, y, x = egcd(b % a, a)
        return g, x - math.floor(b / a) * y, y
    end
end

function inv(a,m)
    a=a>=0 and a or a+m
    local g,x,y = egcd(a,m)
    if g== 1 then
        return x%m
    else
        print(a,"has no inverse mod",m)
    end
end

-- generate lagrange polynomials
for j=0,#x do
    print("j=",j,"*********")
    for m=0,k-1 do
        if m~=j then -- if m==j, continue
            p[j]=p[j]or{[0]=1} -- if this poly doesn't exist, take 1
            p[j]=mul( p[j], {[0]=-x[m],1},inv(x[j]-x[m],w))-- multiply with (x-x_m)/(x_j-x_m)
            io.write"---------------------------------\n"
        end
    end
end
r=0 -- Result for x^0
for k=0,#p do
    print("l_"..k)
    printPoly(p[k]) -- print l_k
    r=r+f(y[k]*p[k][0],w) -- add coeff for x^0 to result
end
print("Secret was",f(r,w)) -- display result

```

Golfed (not using finite field), 444 chars:

```
i=io.read f=math.fmod w=1928049029 k=i():match"%d+"x={}y={}p={}for j=0,k-1 do x[j],y[j]=i():match("(%d+) (%d+)")end
function mul(p,q,s)r={}for k=0,#p do for l=0,#q do r[l+k]=r[l+k]or 0 p[k]=p[k]or 0 q[l]=q[l]or 0 r[l+k]=f(r[l+k]+s*p[k]*q[l],w)end end return r end
for j=0,#x do for m=0,k-1 do if m~=j then p[j]=p[j]or{[0]=1}p[j]=mul(p[j],{[0]=-x[m],1},1/(x[j]-x[m]))end end end r=0 for k=0,#p do r=r+f(y[k]*p[k][0],w)end
print(f(r,w))

```
> 2 votes

# Answer
### Java, 435 407 chars

```
import java.util.*;public class G{public static void main(String[]args){Scanner s=new Scanner(System.in);int i,k,n=s.nextInt();long N=1928049029L,x[]=new long[n],y[]=new long[n],z=0,l,c;for(i=n;i-->0;){x[i]=s.nextInt();y[i]=s.nextInt();}for(i=n;i-->0;){l=y[i];for(long j:x)if(x[i]!=j){c=1;for(long a=N+j-x[i],b=N,d=0,t;b>0;){t=d;d=c-a/b*d;c=t;t=b;b=a%b;a=t;}l=l*j%N*(c+N)%N;}z+=l;}System.out.println(z%N);}}

```

Ungolfed:

```
import java.util.*;
public class G {
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        int i,k,n=s.nextInt();
        long N=1928049029L,x[]=new long[n],y[]=new long[n],z=0,l,c;
        for (i=n; i-->0;) {
            x[i]=s.nextInt();
            y[i]=s.nextInt();
        }
        for (i=n; i-->0;) {
            l=y[i];
            for (long j:x)
                if (x[i]!=j) {
                    // Extended Euclid algorithm - iterative version -
                    // to find the reciprocal of j-x[i] (mod N)
                    c=1;
                    for (long a=N+j-x[i], b=N, d=0, t; b>0;) {
                        t=d; d=c-a/b*d; c=t;
                        t=b; b=a%b; a=t;
                    }
                    l = l*j%N;
                    l = l*(c+N)%N;
                }
                z+=l;
        }
        System.out.println(z%N);
    }
}

```
> 2 votes

# Answer
# Haskell, 183

```
p=1928049029
a#0=(1,0)
a#b=let(s,t)=b#mod a b in(t,s-div a b*t)
s d=sum[y*product[z*fst((z-x)#p)|[z,_]<-d,z/=x]|[x,y]<-d]
main=interact$show.(`mod`p).s.map(map read.words).tail.lines

```
> 2 votes

---
Tags: code-golf, cryptography, polynomials
---


title: fizz buzz in TMP

text:
# Question
Title: fizz buzz in TMP
The Fizz Buzz problem is a very basic problem to solve that is used by some to weed out interviewees that don't know how to program. The problem is:

```
Set N = [0,100]
Set F = x in N where x % 3 == 0
Set B = x in N where x % 5 == 0
Set FB = F intersect B

For all N:
  if x in F: print fizz
  if x in B: print buzz
  if x in FB: print fizzbuzz
  if x not in F|B|FB print x

```

The object of this modification of the Fizz Buzz problem is to perform the above algorithm using C++ templates such that as few runtime operations are necessary as can be done.

You can reduce N to a smaller range if you need to in order to fit within TMP objects where necessary.

This isn't expected to be a "golf".

# Answer
> 3 votes
Here's my attempt (had it lying around for a day or so, because I was unsure whether it was fit as a solution). Surprisingly the only bit I incorporated from @Chris was changing `template<int N, int m3, int m5>` to `template<int N, int m3=N%3, int m5=N%5>`

```
#include <iostream>

using namespace std;

template<int N, int m3=N%3, int m5=N%5>
struct fizzbuzz_print {
  static void print() {
    cout << N << '\n';
  }
};

template<int N, int m5>
struct fizzbuzz_print<N, 0, m5> {
  static void print() {
    cout << "fizz\n";
  }
};

template<int N, int m3>
struct fizzbuzz_print<N, m3, 0> {
  static void print() {
    cout << "buzz\n";
  }
};

template<int N>
struct fizzbuzz_print<N, 0, 0> {
  static void print() {
    cout << "fizzbuzz\n";
  }
};

template<int N>
struct fizzbuzz:public fizzbuzz<N-1> {
  fizzbuzz<N>() {
    fizzbuzz_print<N>::print();
  }
};

template<>
struct fizzbuzz<1> {
  fizzbuzz<1>() {
    fizzbuzz_print<1>::print();
  }
};

int main() {
  fizzbuzz<100> t;
}

```

Additionally, since this is my first attempt at TMP, any suggestions on improving my code would be appreciated.

# Answer
> 2 votes
Totally non-golfed solution:

```
template <int n, int m3 = n % 3, int m5 = n % 5>
struct FizzBuzz {
    static int value() {return n;}
};

template <int n, int m5>
struct FizzBuzz<n, 0, m5> {
    static char const* value() {return "Fizz";}
};

template <int n, int m3>
struct FizzBuzz<n, m3, 0> {
    static char const* value() {return "Buzz";}
};

template <int n>
struct FizzBuzz<n, 0, 0> {
    static char const* value() {return "FizzBuzz";}
};

```

Sample test code:

```
#include <iostream>

int
main()
{
    std::cout << FizzBuzz<1>::value() << '\n'
              << FizzBuzz<2>::value() << '\n'
              << FizzBuzz<3>::value() << '\n'
              << FizzBuzz<4>::value() << '\n'
              << FizzBuzz<5>::value() << '\n'
              << FizzBuzz<13>::value() << '\n'
              << FizzBuzz<14>::value() << '\n'
              << FizzBuzz<15>::value() << '\n'
              << FizzBuzz<16>::value() << '\n';
}

```

# Answer
> 1 votes
Okay, I finally got around to taking a shot at this. Unlike the previous solutions my solution builds the entire output string at compile time and the only run-time call is a single call to `cout`'s `<<` operator. I'm using `boost::mpl` to keep the code somewhat manageable.

```
#include <boost/mpl/string.hpp>
#include <boost/mpl/bool.hpp>
#include <boost/mpl/char.hpp>
#include <boost/mpl/if.hpp>

using namespace boost::mpl;
using std::cout;

template<int n> struct IntToString {
    typedef typename push_back<typename IntToString<n/10>::str, char_<'0'+n%10> >::type str;
};

template<> struct IntToString<0> {
    typedef string<> str;
};

template<int n> struct FizzBuzzHelper {
    typedef typename push_back<typename IntToString<n>::str, char_<'\n'> >::type intstring;
    typedef typename if_< bool_<n%15==0>, string<'fizz','buzz','\n'>,
                          typename if_< bool_<n%5==0>, string<'buzz','\n'>,
                                        typename if_< bool_<n%3==0>, string<'fizz','\n'>,
                                                      intstring>::type >::type >::type str;
};

template<int n> struct FizzBuzz {
    typedef typename insert_range<typename FizzBuzz<n-1>::str,
                                  typename end<typename FizzBuzz<n-1>::str>::type,
                                  typename FizzBuzzHelper<n>::str>::type str;
};

template<> struct FizzBuzz<0> {
    typedef string<> str;
};

#include <iostream>

int main() {
    cout << c_str<FizzBuzz<9>::str>::value;
    return 0;
}

```

Sadly the code will blow up with `boost::mpl::string` complaining about too-large strings when using any `n` greater than 9.

# Answer
> 1 votes
362 characters.

```
#include <iostream>
#include <string>

using namespace std;

template<int N>
struct S {
    static string s, f, l;
};

template<int N>
string S<N>::s =
    N > 9
      ? S<N / 10>::s + S<N % 10>::s
      : string(1, '0' + N);

template<int N>
string S<N>::f =
    N % 15
      ? N % 5
          ? N % 3
              ? s
              : "fizz"
          : "buzz"
      : "fizzbuzz";

template<>
string S<0>::l = f;
template<int N>
string S<N>::l = S<N - 1>::l + "\n" + f;

int main() {
    cout << S<100>::l << endl;
    return 0;
}

```

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


title: Maclaurin series of Black Box Function

text:
# Question
Title: Maclaurin series of Black Box Function
Given a Black Box function `ff` that takes a single floating-point parameter, write a function `M` to generate the Maclaurin series for that function, according to the following specifications:

* take a parameter `n`, and generate all terms from `x^0` to `x^n` where `0 <= n <= 10`
* coefficients for each term should be given to at least 5 decimal places for non-integral values; underflows can simply be ignored or replaced with `0` and left out if you wish, or you can use scientific notation and more decimal places
* assume `ff` is a continuous function and everywhere/infinitely differentiable for `x > -1`, and returns values for input `x` in the range: `-10^9 <= ff(x) <= 10^9`
* programming languages with functions as first-class data types can take `ff` as a parameter; all other languages assume a function called `ff` has already been defined.
* output should be formatted like `# + #x + #x^2 + #x^5 - #x^8 - #x^9 ...`, i.e., terms having `0` coefficient should be left out, and negative coefficients should be written `- #x^i` instead of `+ -#x^i`; if the output terms are all zero, you can output either `0` or null output
* output can be generated either to `stdout` or as a return value of type `string` from the function

Examples (passing `ff` as a first parameter):

```
> M(x => sin(x), 8)
x - 0.16667x^3 + 0.00833x^5 - 0.00020x^7
> M(x => e^x, 4)
1 + x + 0.5x^2 + 0.16667x^3 + 0.04167x^4
> M(x => sqrt(1+x), 4)
1 + 0.5x - 0.125x^2 + 0.0625x^3 - 0.03906x^4
> M(x => sin(x), 0)
0 (or blank is also accepted)

```

# Answer
### Ruby, 173 chars

```
M=->n{r=(-n..n).map{|x|ff(x/2e2)};((0..n).map{|t|u=r[n-t];t<n&&r=r[2..-1].zip(r).map{|x,y|(x-y)*1e2/(t+1)};u.abs<1e-5?'':'%+.5f'%u+(t<2??x[0,t]:'x^%d'%t)}*'').sub(/^\+/,'')}

```

Unfortunately this approach is similar to Keith's solution and thus also numerically unstable for large `n`.

```
def ff(x) Math.sin(x) end
puts M[8]  # 1.00000x-0.16666x^3+0.00833x^5-0.00020x^7

def ff(x) Math.exp(x) end
puts M[4]  # 1.00000+1.00000x+0.50000x^2+0.16667x^3+0.04167x^4

def ff(x) Math.sqrt(1+x) end
puts M[4]  # 1.00000+0.50000x-0.12500x^2+0.06251x^3-0.03907x^4

def ff(x) Math.sin(x) end
puts M[0]  # <empty line>

```
> 3 votes

# Answer
## Python, 188 chars

```
D=lambda f:lambda x:100*(f(x+.005)-f(x-.005))
def M(f,n):
 s="";d=1
 for i in xrange(n+1):
  c=f(0)/d;f=D(f);d*=i+1
  if c:s+='%+.5f'%c+['','x','x^%d'%i][(i>0)+(i>1)]
 print s[s[:1]=='+':]

```

This code takes lots of liberties with accuracy and numerical stability, but it generates something close to the right answer for the given examples.

Running it:

```
import math
M(lambda x:math.sin(x),8)
M(lambda x:math.exp(x),4)
M(lambda x:math.sqrt(x+1),4)
M(lambda x:math.sin(x),0)

```

gives:

```
1.00000x-0.16666x^3+0.00833x^5-0.00020x^7
1.00000+1.00000x+0.50000x^2+0.16667x^3+0.04167x^4
1.00000+0.50000x-0.12500x^2+0.06251x^3-0.03907x^4
<a blank line>

```
> 5 votes

# Answer
## GCC, 549 chars

```
#define f __float128
#define D long double
#define L(v)for(v=0;v<n;v++)
void G(f a[],int n,double d){f m[n][n],s;int
i,j,k;L(i)L(j)m[i][j]=j?m[i][j-1]*d*(i-n/2):1;L(i){s=m[i][i];L(j)m[i][j]/=s;a[i]/=s;L(j)if(j^i){s=m[j][i];L(k)m[j][k]-=s*m[i][k];a[j]-=s*a[i];}}}
#define F(a)L(i)a[i]=(f)ff(d*(i-n/2));G(a,n,d);
void M(int n){f p[++n],q[n];double d=1;int
i,j=1;F(p)while(j){d/=2;F(q)j=0;L(i){j|=(p[i]-q[i])>1E-7;p[i]=q[i];}}L(i)if(p[i]<-5E-6){printf("- %.5Lfx^%d ",(D)-p[i],i);j=1;}else if(p[i]>5E-6){printf("%s%.5Lfx^%d ",j?"+ ":"",(D)p[i],i);j=1;}}

```

Example usage (ungolfed):

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

double ff(double x)
{
    return sin(x);
}

#define f __float128
#define D long double
#define L(v) for(v=0;v<n;v++)
void G(f a[],int n,double d) {
    f m[n][n],s;
    int i,j,k;
    L(i) L(j) m[i][j] = j ? m[i][j-1]*d*(i-n/2) : 1;
    L(i) {
        s=m[i][i]; L(j) m[i][j]/=s; a[i]/=s;
        L(j) if(j^i) {
            s=m[j][i]; L(k) m[j][k]-=s*m[i][k]; a[j]-=s*a[i];
        }
    }
}
#define F(a) L(i) a[i]=(f)ff(d*(i-n/2)); G(a,n,d);
void M(int n) {
    f p[++n],q[n];
    double d=1;
    int i,j=1;

    F(p)
    while(j) {
        d/=2;
        F(q)
        j=0;
        L(i) {
            j|=(p[i]-q[i])>1E-7;
            p[i]=q[i];
        }
    }

    L(i)
        if (p[i]<-5E-6) { printf("- %.5Lfx^%d ",(D)-p[i],i); j=1; }
        else if (p[i]>5E-6) { printf("%s%.5Lfx^%d ",j?"+ ":"",(D)p[i],i); j=1; }
}

void main()
{
    M(8);
}

```

Compiles with just `gcc maclaurin.c -lm`

I'm sure that someone who actually knows C can shave at least 10% off, but if nothing else it gets the ball rolling.

With a bit of playing with matrix inverses I've discovered a shorter, but less numerically stable, method which exploits the particular structure of the matrices to special-case the Gaussian elimination:

### Alternate, 536 chars

```
#define f __float128
#define D long double
#define L(v)for(v=0;v<n;v++)
void G(f a[],int n,double d){int i,t;f F[n];L(i)F[i]=i?i*F[i-1]:1;while(--n>0){f c=0;t=2*(n&1)-1;for(i=0;i<=n;i++){t=-t;c+=t*a[i]/F[i]/F[n-i];}L(i)a[i]-=c*pow(i,n);L(i)c/=d;a[n]=c;}}
#define F(a)L(i)a[i]=(f)ff(d*i);G(a,n,d);
void M(int n){f p[++n],q[n];double d=.5;int i,j=1;F(p)while(j){d/=2;F(q)j=0;L(i){j|=(p[i]-q[i])>1E-7;p[i]=q[i];}}L(i)if(p[i]<-5E-6){printf("- %.5Lfx^%d ",(D)-p[i],i);j=1;}else if(p[i]>5E-6){printf("%s%.5Lfx^%d ",j?"+ ":"",(D)p[i],i);j=1;}}

```

However, this really needs a better error check, so that when it hits the point at which the largest term in the polynomial starts blowing out of control it will quit the loop.
> 2 votes

# Answer
## Mathematica, 39 chars

```
InputForm@N@Normal@Series[#1,{x,0,#2}]&

```

Usage

```
%[Sin[x], 8]

```

Output

```
x - 0.16666666666666666*x^3 + 0.008333333333333333*x^5 - 0.0001984126984126984*x^7

```
> 2 votes

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


title: Simulate a Minsky Register Machine (II)

text:
# Question
Title: Simulate a Minsky Register Machine (II)
This is an extension of Simulate a Minsky Register Machine (I). I'm not going to repeat all of the description there, so please read that problem description first.

The grammar in part (I) was as simple as possible, but results in rather long programs. Since this is a code golf site, we'd rather have a golfed grammar, wouldn't we?

At a high level, the changes from the original grammar are as follows:

* The label on the first line is optional
* Whitespace is optional except where required to separate two adjacent identifiers
* States can be inlined. To ensure non-ambiguous parsing, if the first state of a decrement operation is an inlined state, it must be enclosed in parentheses. This means that any program can be golfed into a one-liner.

For example, in the original test cases we had:

b+=a, t=0

```
init : t - init d0
d0 : a - d1 a0
d1 : b + d2
d2 : t + d0
a0 : t - a1 "Ok"
a1 : a + a0
a=3 b=4

```

In the golfed grammar this could be shortened to:

```
init:t-init d
d:a-(b+t+d)a
a:t-(a+a)"Ok"
a=3 b=4

```

or even:

```
init:t-init d:a-(b+t+d)a:t-(a+a)"Ok"
a=3 b=4

```

The new BNF for the "program" lines (as opposed to the final line, which is data) is:

```
program    ::= first_line (newline line)*
first_line ::= cmd
line       ::= named_cmd
state      ::= state_name
             | cmd
             | '"' message '"'
delim_state::= '(' cmd ')'
             | '"' message '"'
cmd        ::= raw_cmd
             | named_cmd
named_cmd  ::= state_name ' '* ':' ' '* raw_cmd
raw_cmd    ::= inc_cmd
             | dec_cmd
inc_cmd    ::= reg_name ' '* '+' ' '* state
dec_cmd    ::= reg_name ' '* '-' ' '* delim_state ' '* state
             | reg_name ' '* '-' ' '* state_name ' '* delim_state
             | reg_name ' '* '-' ' '* state_name ' '+ state
state_name ::= identifier
reg_name   ::= identifier

```

Identifiers and messages are flexible as in the previous challenge.

---

All of the test cases from the previous challenge are still applicable. In addition, the following golfed Josephus solution should exercise most of the grammar:

```
in:k-(r+t+in)in2:t-(k+in2)r-(i+n-0"ERROR n is 0")"ERROR k is 0"
0:n-(i+2:k-(r+t+2)5:t-(k+5)7:i-(r-(t+7)c:t-(i+r+c)i+0)a:t-(i+a)7)"Ok"
n=40 k=3

```

Expected output:

```
Ok
i=40 k=3 n=0 r=27 t=0

```

And I think this covers the remaining case:

```
k+k-"nop""assert false"
k=3

```

Expected output:

```
nop
k=3

```

---

You may assume that all programs will have sensible semantics. In particular, they will have at least one state and will not redefine a state. However, as before, a state may be used before it is defined.

The scoring is a variant on code-golf. You can write a self-contained program and it will score as the length of the program in bytes after UTF-8-encoding. Alternatively, because code reuse is a Good Thing, if you have implemented part (I) in `n1` bytes, you can write a program which turns a part (II) program into a part (I) program, ready for piping to the original. Your score will then be the length of your transformation program plus `ceil(n1 / 2)`.

NB If you opt for the transformation, you will need to generate names for the anonymous states in such a way that you guarantee that they don't clash with named states.

# Answer
> 6 votes
# Haskell, ~~552~~ ~~499~~ 493 characters

```
import Control.Monad.RWS
import Data.Map
main=interact$z.lines
z x=let(s:_,w)=evalRWS(mapM(q.t)x)w[]in s.f.i.t$last x
p=get>>=q
q(l:":":x)=x%do a<-p;tell$f[(l,a)];r a
q(v:"+":x)=x%fmap(.a v 1)p
q(v:"-":x)=x%liftM2(d v)p p
q(('"':s):x)=x%r(\w->unlines[init s,do(v,x)<-assocs w;v++'=':show x++" "])
q(n:x)|n<"*"=x%p|1<3=x%asks(!n)
d v p n w|member v w&&w!v>0=p$a v(-1)w|1<3=n w
t[]=[];t x=lex x>>= \(y,x)->y:t x
i(v:_:x:t)=(v,read x):i t;i[]=[]
x%m=put x>>m;r=return;a=insertWith(+);f=fromList

```

Did more or less a full rewrite. Replaced CPS with a RWS monad which reads its own output to look up states it hasn't parsed yet (yay for laziness!), plus some other tweaks.

---
Tags: code-challenge, interpreter
---