# Question
Title: Generate a golfed program to evaluate an arithmetic expression
Your task is to write a program that will take input like this:

```
a + b * c + a / 2

```

and will *generate the source code for a program* that takes user input and then evaluates the expression.

The expression can contain the operators `+`,`-`,`*`,`/`; single-letter lowercase variables; and integers between 0 and 32000. Standard arithmetic precedence must be correctly followed. The expression is limited to 26 unique variables a to z. However, a single variable can appear more than once.

You can assume that the input expression is valid (follows these rules).

The generated program must prompt for user input in this form, prompting only once for each variable:

```
a =

```

User input from 0 to 32000 should be handled correctly. It will then print the expression and the correct result. You can use either integer or floating point arithmetic. The calculations should be performed with at least 32 bit precision. Beyond that, you don't have to worry about overflow or divide by zero.

Example of a non-golfed generated Perl program for the above expression:

```
print "a = ";
my $a = <>;
print "b = ";
my $b = <>;
print "c = ";
my $c = <>;
print "a + b * c + a / 2 = " . ($a + $b * $c + $a / 2);

```

Example input and output of program generated for above expression:

```
a = 1
b = 2
c = 3
a + b * c + a / 2 = 7.5

```

The score is calculated as length of the program + length of the generated program for this expression:

```
1 + a * 4 * b + 2 / d * e - a - 3 + g / h * 32000

```

Lowest score wins.

**Update:** Just to highlight a couple of requirements of the problem, as stated above:

* The output of the program must be *source code for another program* that evaluates the expression.
* The program must *print the original expression*. Perhaps there is some ambiguity in this (one could argue that `a+b` is the same expression as `a + b`), but for clarity let's say that it must be the original expression with white space intact. All valid answers so far have done it that way.

# Answer
> 1 votes
### Perl, 80 + 110 = 190

Directly inspired by another (now deleted) answer in Ruby. Requires Perl ≥ v5.14.

Following the usual rule I've seen of command-line switches counting as one character.

```
#!/usr/bin/perl -n
chomp;print'print $_="',$_,'"," = ",eval(s#\pL#${$&}//=do{print"$& = ";<>}#ger)'

```

### Perl, 80 + 231 = 311

Because eval'ing in the output feels cheap.

```
#!/usr/bin/perl -p
chomp;print"print '$_ = ',";s/\pL/$s{$&}++?"\$$&":"do{print'$& = ';\$$&=<>}"/ge

```

Seems like the output could be shortened by moving the prompting into a sub, but I've run out of enthusiasm.

# Answer
> 1 votes
## Lua, 202 + 166 = 368

File "generate\_code.lua"

```
F=...
C='function G(v)io.write(v.." = ")_G[v]=io.read"*n"end 'V={}for v in F:gmatch'%l'do V[v]=0 end
for v in pairs(V)do C=C..'G"'..v..'"'end
print(C..'F="'..F..'"print(F.." = "..load("return "..F)())')

```

Usage:

```
$ lua generate_code.lua "1 + a * 4 * b + 2 / d * e - a - 3 + g / h * 32000"

```

Code generated (order of variables is not specified):

```
function G(v)io.write(v.." = ")_G[v]=io.read"*n"end G"g"G"e"G"d"G"b"G"a"G"h"F="1 + a * 4 * b + 2 / d * e - a - 3 + g / h * 32000"print(F.." = "..load("return "..F)())

```

Generated code in action:

```
g = 4
e = 3
d = 2
b = 1
a = 6.5
h = 4.3
1 + a * 4 * b + 2 / d * e - a - 3 + g / h * 32000 = 29787.941860465

```

# Answer
> 1 votes
## Tcl 198 + 155 = 352

```
gets stdin i;puts [string map [list @ [lsort -u [regexp -all -inline {[a-z]} $i]] & [regsub -all {[a-z]} [join $i {}] {$\0}] | $i] {foreach va {@} {puts "$va =";gets stdin $va};puts "| = [expr &]"}]

```

generates

```
foreach va {a b d e g h} {puts "$va =";gets stdin $va};puts "1 + a * 4 * b + 2 / d * e - a - 3 + g / h * 32000 = [expr 1+$a*4*$b+2/$d*$e-$a-3+$g/$h*32000]"

```

# Answer
> 0 votes
## Python 125 + 151 = 276

```
>>> t=raw_input();z=sorted(set(filter(str.isalpha,t)));print','.join(z)+'=[input(x+" = ")for x in%r];print"%s =",%s'%(z,t,t[::2])
1 + a * 4 * b + 2 / d * e - a - 3 + g / h * 32000
a,b,d,e,g,h=[input(x+" = ")for x in['a', 'b', 'd', 'e', 'g', 'h']];print"1 + a * 4 * b + 2 / d * e - a - 3 + g / h * 32000 =",1+a*4*b+2/d*e-a-3+g/h*300

```

Now executing it:

```
>>> exec"""a,b,d,e,g,h=[input(x+" = ")for x in['a', 'b', 'd', 'e', 'g', 'h']];print"1 + a * 4 * b + 2 / d * e - a - 3 + g / h * 32000 =",1+a*4*b+2/d*e-a-3+g/h*300"""
a = 1
b = 2
d = 3
e = 4
g = 5
h = 6
1 + a * 4 * b + 2 / d * e - a - 3 + g / h * 32000 = 5

```

---
Tags: code-golf
---


# Question
Title: Win a virtual fencing match (against your fellow stack exchangers)
**WARNING: this is a fairly complex problem, in a king-of-the-hill combat style, with an added randomness to it, the best code may not always win. Please read all rules in full, as it is quite complex!**

# Flavor text

Bill and Steve decided to have a "friendly" duel, however being so rich and smart, decided to let their best programmers try their hand at coming up with the code to beat each other. You are said programmer.

# Objective

In fencing, your goal is to score the most hits on your opponent, while getting hit the least yourself

# Moves

Your code will have the following choices of "moves"

* Attack
* Parry
* Block
* Lunge

**AND**

* Head
* Chest
* Feet

# Scoring

Attacking beats Parrying, *for 1 point*
Lunging beats Blocking, *for 1 point*
Parrying Beats Lunging, *for 1 point*
Blocking beats Attacking, *for 1 point*
Lunging ties Attacking, *with the lunging player unable to block or parry the next round, and the attacking player unable to attack or lunge the next round*
Blocking ties Parrying, *with the parrying player unable to block or parry the next round, and the blocking player unable to attack or lunge the next round*

# Height of action

You will also choose a "height" for your action, whereupon the outcomes above only take place if the heights of both players match the attack height. if the heights do not match, both players may no longer select the same action (height is not restricted) as the previous tying rounds, until a point is scored, or all 4 actions have been filled (once a tie is broken, all actions are available again)

# Code requirements

For each round, it should prompt the move of the opponent the previous round (barring round 1), compare it with its own, determine the outcome of the previous round, then output the next round number, the score, and its choice / position for that round

ex:
INPUT: LC (lunge chest)
OUTPUT: previous round: PM vs LC - PM scores! score is now 2-1, action for next round is AH (attack head)

# Winner

The game ends after 50 rounds, or after 3 points have been scored

# Against other players

The first answer will be given an instant guaranteed win, as long as it functions to actually work/play. Each answer will be evaluated, in order of posting, against the previous winner, and if winning, will be declared the new winner. I ask that while winning, or waiting to compete, that you do NOT change your code. Once being defeated, you may no longer compete for championship status with that same language, you may however submit a different language answer (must be significantly different, no using variations of the same base stuff).

I will attempt to run each challenge and will post the results in the comments of the champion and challenger, as well as declare a new winner - as I may not be able to run every language, especially some of the more obscure ones, I ask any possible help you can give to make sure your answer gets run be taken into consideration.

# Answer
> 6 votes
## Python

En garde!

My warrior combines unpredictability with a keen eye for weakness in his opponent's stance. He's pretty confident he'll be able to dispose of aggressive foes but his trainer (me) may have failed to anticipate certain scenarios or, perhaps more worrying, may have misinterpreted the rules (bugs!!).

Anyway I'm new so hopefully this is an ok format for the code:

```
from random import choice, random

def cleverly_pick_move(me_allowed,op_allowed,opp_last_move=None) :
    """ Behold the genius you're up against!
    Pretty much everything else is just flavour text or match rules
    so you'll probably only want to read this...
    """
    heights = ['head','chest','feet']
    rand_choice = lambda a,h : {'type':choice([t for t in a if a[t]]),
                                'height':choice(h)}

    if opp_last_move is None or feeling_like_a_lucky_punk():
        return rand_choice(me_allowed,heights)

    if sum(1 for x in op_allowed if op_allowed[x]) == 3 :
        for i in op_allowed:
            if not op_allowed[i] :
                weakness = i
                break
        return {'type':exploit_weakness(weakness,me_allowed),
                'height':choice(heights)}
    return rand_choice(me_allowed,heights)

def exploit_weakness(weakness,me_allowed) :
    moves = ['attack','parry','lunge','block']
    for i,move in enumerate(moves) :
        if move == weakness :
            if me_allowed[moves[(i+1) % 4]] :
                return moves[(i+1) % 4]
            break
    if me_allowed[weakness] :
        return weakness
    return choice([x for x in me_allowed if me_allowed[x]])

def feeling_like_a_lucky_punk() :
    return random() > 0.8

def main():

    this_round = 1
    opp_last_move = None
    score   = {'myself':0, 'the blaggard':0}
    quips   = ['blaggard', 'fool', 'scum', 'raggamuffin']
    adverbs = ['deftly', 'skillfully', 'gracefully', 'clumsily']

    me_allowed = {'attack':True,'block':True,'lunge':True,'parry':True}
    op_allowed = {'attack':True,'block':True,'lunge':True,'parry':True}

    while (this_round <= 50 and
           all([points < 3 for points in score.values()])) :

        if this_round == 1 :
            move = cleverly_pick_move(me_allowed,op_allowed)
        else:
            move = cleverly_pick_move(me_allowed,op_allowed,
                                      opp_last_move=opp_last_move)

        print "Our hero %s %ss at the %s's %s" % (
            choice(adverbs),
            move['type'],
            choice(quips),
            move['height']
            )
        print "We await the %s's response..." % choice(quips)
        print "Our hero's move: " + (move['type'][0]+move['height'][0]).upper()

        opp_move = parse_move(raw_input("Opponent's move: "))

        outcome,me_allowed,op_allowed = get_outcome(move,opp_move,me_allowed,
                                                    op_allowed)
        if outcome == 'WIN' :
            print "Our hero pulls off an excellent round!"
            score['myself'] += 1
        elif outcome == 'LOSE' :
            print "Never before have we seen such blatant cheating!"
            score['the blaggard'] += 1
        else :
            print "Our hero is clearly toying with his opponent as he allows \
a drawn round."

        print ("""The score after round %d:\nOur hero:\t%d\nHis opponent:\t%d"""
                % (this_round, score['myself'], score['the blaggard']))
        opp_last_move = opp_move
        this_round += 1

    print "Match over, surely the victory is mine!"
    print """Final score:\n
             Our hero:\t%d\nOpponent:\t%d""" % (score['myself'],
                                                score['the blaggard'])

    if score['myself'] > score['the blaggard'] :
        print "My victory was inevitable!"
    elif score['myself'] == score['the blaggard'] :
        print "An even match! Huzzar!"
    else :
        print ""
    return

def reset_allowed(dictionary) :
    return dict((x,True) for x in dictionary)

def get_outcome(mymove,opmove,me_allowed,op_allowed) :
    result = ''

    if not me_allowed[mymove['type']] :
        print "Whoops, I forgot I couldn't do that..."
        result = 'LOSE'

    if not op_allowed[opmove['type']] :
        print "Haha! What a clutz!"
        result = 'WIN'

    if mymove['height'] != opmove['height'] :
        print "The combatants flail at each other with little effect!"
        print "They'll have to try something else next round!"
        result = 'DRAW'

    if mymove['type'] == opmove['type'] :
        if mymove['type'] in ['attack','lunge']:
            print "The combatants' blades clash dramatically!"
        else :
            print "Both combatants take a moment to practice their \
defensive stance..."
        result = 'DRAW'

    if result :
        me_allowed, op_allowed = (reset_allowed(me_allowed),
                                  reset_allowed(op_allowed))
        if mymove['height'] != opmove['height'] :
            me_allowed[mymove['type']] = op_allowed[opmove['type']] = False
        return (result, me_allowed,op_allowed)
    else :
        return compare_attacks(mymove,opmove,me_allowed,op_allowed)

def compare_attacks(mymove,opmove,me_allowed,op_allowed) :
    """
    0 A > P 1
     ^  x  v
    3 B < L 2
    """
    print "Our hero %ss, his opponent %ss!" % (mymove['type'],opmove['type'])

    move_val = {'attack':0,'parry':1,'lunge':2,'block':3}
    result_num = (move_val[opmove['type']] - move_val[mymove['type']]) % 4
    results = ['DRAW','WIN','DRAW','LOSE']

    me_allowed, op_allowed = (reset_allowed(me_allowed),
                              reset_allowed(op_allowed))
    if result_num == 1 :
        print "Our hero easily outwits his foe! *Huge cheers from crowd*"
        return ('WIN',me_allowed,op_allowed)
    elif result_num == 3 :
        print "Our hero graciously allows his opponent a charity point.\
*A torrent of boos from the crowd*"
        return ('LOSE',me_allowed,op_allowed)
    else:
        # Combatants drew and will have their moves restricted next round.
        if mymove['type'] in ['attack','parry'] :
            me_allowed['attack'] = me_allowed['lunge'] = False
            me_allowed['parry']  = me_allowed['block'] = True
            op_allowed['parry']  = op_allowed['block'] = False
            op_allowed['attack'] = op_allowed['lunge'] = True
        else :
            me_allowed['parry']  = me_allowed['block'] = False
            me_allowed['attack'] = me_allowed['lunge'] = True
            op_allowed['attack'] = me_allowed['lunge'] = False
            op_allowed['parry']  = op_allowed['block'] = True
        return ('DRAW',me_allowed,op_allowed)

def parse_move(move_string) :
    m_types = {'A':'attack','B':'block','L':'lunge','P':'parry'}
    m_heights = {'C':'chest','H':'head','F':'feet'}

    move_string = move_string.strip().upper()
    if not move_string :
        print "Couldn't understand your input: %s" % move_string
        return parse_move(raw_input("Opponent's move: "))

    if move_string[0] not in m_types :
        move_string = move_string[::-1]

    try :
        move = {'type':m_types[move_string[0]],
                'height':m_heights[move_string[1]]}
        return move
    except KeyError :
        print "Couldn't understand your input: %s" % move_string
        return parse_move(raw_input("Opponent's move: "))

if __name__ == '__main__' :
    main()

```

# Answer
> 2 votes
I claim the hill!

This includes a framework which takes care of the match, input and output. All you have to do is define your own versions of two functions in the "A.I.h" header which define the first move and every other move.

This compiles in VS2012 (free version). To the best of my knowledge it will compile in any standards-compliant compiler.

I call this A.I. "Unsophisticated Barbarian." I'm sure it won't take long for someone to beat it.

```
// A.I.h
    #pragma once

    #include "Fencer.h"

    #include <algorithm>

    Move Fencer::chooseFirstMove() const
    {
        // Choose first move here.
        return Move( Action::Attack , Height::Head );
    }

    Move Fencer::chooseNextMove() const
    {
        using namespace std;

        // Implement A.I. here.
        auto legalActions = match.legalActions();
        auto isLegal = [&legalActions]( Action a ) {
            return find( begin(legalActions) , end(legalActions) , a ) == end(legalActions);
        };

        if( isLegal( Action::Attack ) )
            return Move( Action::Attack , Height::Head );
        if( isLegal( Action::Lunge ) )
            return Move( Action::Lunge , Height::Head );
        if( isLegal( Action::Block ) )
            return Move( Action::Lunge , Height::Head );
        if( isLegal( Action::Parry ) )
            return Move( Action::Parry , Height::Head );

    }

    // Fencer.h
    #pragma once

    #include "Match.h"

    class Fencer
    {
    public:
        std::string nextRound( const std::string& oppsMove );
        std::string getNextMove() const { return nextMove.toStr(); }
        bool matchInProgress() const { return match.inProgress(); }
        Fencer( unsigned int targetScore = 3 , unsigned int match_rounds = 50 );
    private:
        Move chooseNextMove() const;
        Move chooseFirstMove() const;
        Move nextMove;
        Match match;
    };

    // Match.h
    #pragma once

    #include <vector>
    #include <string>

    enum class Action : char
    {
        Attack,
        Parry,
        Block,
        Lunge,
        UNITIALIZED
    };

    enum class Height : char
    {
        Head,
        Chest,
        Feet,
        UNITIALIZED
    };

    enum class Result : char
    {
        Win,
        Tie,
        Lose,
        UNITIALIZED
    };

    struct Move
    {
        Action action;
        Height height;
        Move( Action a , Height h )
            : action(a) , height(h) {}
        std::string toStr() const;

        // For the STL. Please don't use these.
        Move() : action( Action::UNITIALIZED ) , height( Height::UNITIALIZED ) {}
        Move operator=( const Move& );
    };

    Result scoreRound( Move me , Move opp );

    struct Round
    {
        Move myMove;
        Move oppsMove;
        Result result;
        Round( Move me , Move opp )
            : myMove(me) , oppsMove(opp) , result(scoreRound(me,opp)) {}

        // For the STL. Please don't use these.
        Round() : myMove() , oppsMove() , result( Result::UNITIALIZED ) {}
        Round operator=( const Round& );
    };

    class Match
    {
    public:
        // Constructor.
        Match( unsigned int winningScore, unsigned int rounds );

        // Generate a list of legal actions.
        std::vector<Action> legalActions() const;

        // Get a copy of all previous rounds.
        std::vector<Round> getHistory() const { return results; }

        // Gets the scores
        unsigned int myScore() const;
        unsigned int oppsScore() const;
        bool inProgress() const { return in_progress; }

        // Perform next round. Returns the TTY for the round.
        std::string nextRound( const std::string& myMove , const std::string& oppsMove );
    private:
        const unsigned int winning_score;
        const unsigned int n_rounds;
        std::vector<Round> results;
        bool in_progress;
    };

    // Fencer.cpp
    #include "AI.h"

    #include <algorithm>

    using namespace std;

    Fencer::Fencer( unsigned int target , unsigned int rounds ) :
        match( target , rounds ) , nextMove( chooseFirstMove() )
    {}

    string Fencer::nextRound( const string& oppsMove )
    {
        string output = match.nextRound( nextMove.toStr() , oppsMove );
        if( match.inProgress() ) {
            nextMove = chooseNextMove();
            vector<Action> legalActions = match.legalActions();
            auto it = find( legalActions.begin() , legalActions.end() , nextMove.action );
            auto it2 = legalActions.end();
            if( legalActions.end() == it ) {
                output += "\n\nWARNING! Chosen move is illegal!\n\n";
            }
            output += " Action for next round is " + getNextMove() + ".";
        }
        return output;
    }

    // Match.cpp
    #include "Match.h"

    #include <algorithm>
    #include <sstream>
    #include <cassert>
    #include <functional>

    using namespace std;

    string Move::toStr() const
    {
        string str;
        switch( action )
        {
        case Action::Attack:
            str.push_back( 'A' );
            break;
        case Action::Block:
            str.push_back( 'B' );
            break;
        case Action::Lunge:
            str.push_back( 'L' );
            break;
        case Action::Parry:
            str.push_back( 'P' );
            break;
        default:
            assert( false );
            break;
        }
        switch( height )
        {
        case Height::Head:
            str.push_back( 'H' );
            break;
        case Height::Chest:
            str.push_back( 'C' );
            break;
        case Height::Feet:
            str.push_back( 'F' );
            break;
        default:
            assert( false );
            break;
        }
        return str;
    }

    Move Move::operator=( const Move& rhs )
    {
        action = rhs.action;
        height = rhs.height;
        return *this;
    }

    Result scoreRound( Move me , Move opp )
    {
        if( me.height != opp.height ) {
            return Result::Tie;
        }
        if( me.action == opp.action ) {
            return Result::Tie;
        }
        switch ( me.action ) {
        case Action::Attack:
            switch( opp.action ) {
            case Action::Parry:
                return Result::Win;
            case Action::Lunge:
                return Result::Tie;
            case Action::Block:
                return Result::Lose;
            default:
                assert( false );
            }
        case Action::Lunge:
            switch( opp.action ) {
            case Action::Block:
                return Result::Win;
            case Action::Attack:
                return Result::Tie;
            case Action::Parry:
                return Result::Lose;
            default:
                assert( false );
            }
        case Action::Parry:
            switch( opp.action ) {
            case Action::Lunge:
                return Result::Win;
            case Action::Block:
                return Result::Tie;
            case Action::Attack:
                return Result::Lose;
            default:
                assert( false );
            }
        case Action::Block:
            switch( opp.action ) {
            case Action::Attack:
                return Result::Win;
            case Action::Parry:
                return Result::Tie;
            case Action::Lunge:
                return Result::Lose;
            default:
                assert( false );
            }
        default:
            assert( false );
        }
        return Result::Tie;
    }

    Round Round::operator=( const Round& rhs )
    {
        myMove = rhs.myMove;
        oppsMove = rhs.oppsMove;
        result = rhs.result;
        return *this;
    }

    Match::Match( unsigned int targetScore , unsigned int rounds ) :
        winning_score( targetScore ) , n_rounds( rounds) , results() , in_progress( true )
    {
        results.reserve( rounds );
    }

    vector<Action> Match::legalActions() const
    {
        typedef unsigned int ActionBits;

        // Make a bitfield representing the four legal actions.
        const ActionBits ATTACK = 0x1;
        const ActionBits PARRY = 0x2;
        const ActionBits BLOCK = 0x4;
        const ActionBits LUNGE = 0x8;

        const auto actionBitsToVector = [=](ActionBits ab) -> vector<Action> {
            vector<Action> vec;
            if( ab == 0 ) // Nothing is allowed
                ab = ATTACK | PARRY | BLOCK | LUNGE; // So allow all actions
            if( (ATTACK & ab) == ATTACK )
                vec.push_back( Action::Attack );
            if( (PARRY & ab) == PARRY )
                vec.push_back( Action::Parry );
            if( (BLOCK & ab) == BLOCK )
                vec.push_back( Action::Block );
            if( (LUNGE & ab) == LUNGE )
                vec.push_back( Action::Lunge );
            return vec;
        };

        auto availableActions = ATTACK | PARRY | BLOCK | LUNGE;

        const auto lastResult = *results.rbegin();

        // If a point was scored in the last round all actions are available.
        if( lastResult.result != Result::Tie ) {
            return actionBitsToVector( availableActions );
        }

        // If the heights do not match, both players may no longer
        // select the same action (height is not restricted)
        // as the previous tying rounds, until a point is scored,
        // or all 4 actions have been filled.
        if( lastResult.myMove.height != lastResult.oppsMove.height ) {
            for( auto it = results.rbegin() ; it!= results.rend() ; ++it ) {
                if( it->result != Result::Tie )
                    break;
                else {
                    switch( it->myMove.action )
                    {
                    case Action::Attack:
                        availableActions &= ~ATTACK;
                        break;
                    case Action::Parry:
                        availableActions &= ~PARRY;
                        break;
                    case Action::Block:
                        availableActions &= ~BLOCK;
                        break;
                    case Action::Lunge:
                        availableActions &= ~LUNGE;
                        break;
                    default:
                        break;
                    }
                }
            }
            return actionBitsToVector( availableActions );
        }

        // Attack vs. Lunge
        if( lastResult.myMove.action == Action::Attack &&
            lastResult.oppsMove.action == Action::Lunge ) {
                return actionBitsToVector( PARRY | BLOCK );
        }
        if( lastResult.myMove.action == Action::Lunge &&
            lastResult.oppsMove.action == Action::Attack ) {
                return actionBitsToVector( ATTACK | LUNGE );
        }

        // Block vs Parry
        if( lastResult.myMove.action == Action::Block &&
            lastResult.oppsMove.action == Action::Parry ) {
                return actionBitsToVector( ATTACK | LUNGE );
        }
        if( lastResult.myMove.action == Action::Parry &&
            lastResult.oppsMove.action == Action::Block ) {
                return actionBitsToVector( BLOCK | PARRY );
        }
        return actionBitsToVector( availableActions );
    }

    unsigned int Match::myScore() const
    {
        return count_if( begin(results) , end(results) ,
            [=](const Round& r) {
                return r.result == Result::Win;
        });
    }

    unsigned int Match::oppsScore() const
    {
        return count_if( begin(results) , end(results) ,
            [=](const Round& r) {
                return r.result == Result::Lose;
        });
    }

    string Match::nextRound( const string& myMove , const string& oppsMove )
    {
        if( !in_progress )
            return "Match has already finished.\n";

        stringstream output;
        output << "Round " << results.size()+1 << ": ";
        bool parseSuccessful = true;
        auto getMove = [&]( const string& s ) {
            if( s.length() < 2 ) {
                output << "\nError: Move " << s << " does not have enough characters.";
                return Move();
            }
            Action a = Action::UNITIALIZED;
            switch( s[0] )
            {
            case 'a':
            case 'A':
                a = Action::Attack;
                break;
            case 'b':
            case 'B':
                a = Action::Block;
                break;
            case 'l':
            case 'L':
                a = Action::Lunge;
                break;
            case 'p':
            case 'P':
                a = Action::Parry;
                break;
            default:
                parseSuccessful = false;
                output << "\nFailed to parse action part (" << s[0] << ") of " << s;
                break;
            }

            Height h = Height::UNITIALIZED;
            switch( s[1] )
            {
            case 'h':
            case 'H':
                h = Height::Head;
                break;
            case 'c':
            case 'C':
                h = Height::Chest;
                break;
            case 'f':
            case 'F':
                h = Height::Feet;
                break;
            default:
                parseSuccessful = false;
                output << "\nFailed to parse height part (" << s[1] << ") of " << s;
                break;
            }

            if( a == Action::UNITIALIZED || h == Height::UNITIALIZED )
                return Move();
            else
                return Move( a , h );
            };

        Round thisRound( getMove( myMove ),  getMove( oppsMove ) );

        if ( parseSuccessful ) {
            output << "Previous round: " << myMove << " vs " << oppsMove << " - ";
            switch( thisRound.result )
            {
            case Result::Win:
                output << myMove + " Wins! ";
                break;
            case Result::Lose:
                output << oppsMove + " Wins! ";
                break;
            case Result::Tie:
                output << "Tie! ";
                break;
            default:
                assert( false );
                break;
            }

            results.push_back( thisRound );
            const auto score_me = myScore();
            const auto score_opp = oppsScore();
            output << "Score is now " << score_me << "-" << score_opp << ".";

            if( score_me >= winning_score ) {
                output << "\n\tI win! ";
                in_progress = false;
            }
            if( score_opp >= winning_score ) {
                output << "\n\tI lose. ";
                in_progress = false;
            }
            if( results.size() >= n_rounds ) {
                output << "\n\tTime's up. ";
                if( score_me == score_opp )
                    output << "Match drawn. ";
                else
                    output << "I " << (score_me > score_opp ? "win! " : "lose. " );
                in_progress = false;
            }

            if (!in_progress ) {
                output << "Final score: " << score_me << "-" << score_opp << endl;
            }
        }
        return output.str();
    }

```

---
Tags: king-of-the-hill
---


title: Bouncing ball simulation

text:
# Question
Title: Bouncing ball simulation
Print, on STDOUT, a pattern which shows in what direction a bouncing ball will take.

The following assumptions are made:

* The ball starts at the top left corner: `0, 0` with zero initial velocity.
* Gravity is `9.8ms^-2` exactly, towards the floor (y positive.)
* The ball weighs `500g` exactly.
* The ball bounces at 45 or 135 degrees to the floor *unless* you want to add the appropriate calculations to add variable trajectories. (Bonus arbitrary points!)
* The ball has a spring constant coefficient of restitution/bouncyness constant of `0.8` exactly.
* The ball is perfectly spherical and does not deform when it bounces.
* The room is 25 characters high, 130 characters wide. Each x and y is 1 metre and each ball position represents a discrete sample -- the exact time period is deliberately unspecified, but the display should make the ball's path sufficiently clear. The output should show the path of the ball, not just the final position.
* The floor and ball should be indicated using characters on STDOUT, which may be the same. The presence of no ball or floor surface shall be indicated with a space character.
* You are allowed to assume rounding to three decimal places in any calculations. (Solutions using purely integers may be particularly interested in this rule.)
* The simulation stops when either the ball does not move from the floor or it leaves the room (`x > width of area`.)
* The program must simulate the ball's path, not simply load it from a file or have it encoded somehow in the program. The test for this will be to optionally change one of the constants. If the program does not calculate a new, correct result, then it does not qualify.

Example output:

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

```

**Determination of winner.** I will accept the answer which:

1. Meets the rules as defined above.
2. Bonus featureness will be considered.
3. Is the shortest and most elegant (subjective decision.)

# Answer
## Python 143 bytes

```
u=v=x=y=0
a=[[s]*130for s in' '*24+'*']
while x<129:
 if y+v>24:v*=-.8;u=-v
 v+=98e-4;x+=u;y+=v;a[int(y)][int(x)]=s
for r in a:print''.join(r)

```

The resulting curve is slightly different than the example, but this is because the velocity is adjusted before the ball goes into the floor, instead of after it already has.

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

```

---

## Python 132 bytes

A more realistic version, that starts with a constant *x* velocity:

```
v=x=y=0
a=[[s]*130for s in' '*24+'*']
while x<129:v=(y+v<24or-.8)*v+98e-4;x+=.3;y+=v;a[int(y)][int(x)]=s
for r in a:print''.join(r)

```

Produces:

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

```
> 5 votes

# Answer
I'll submit my own solution in Python. Only slightly simplified; I'm sure there are much better ways of doing it! **282 280 characters.** The example output in the question post was generated using this program.

```
import sys;o=sys.stdout.write
py=px=vy=vx=0;g=98e-4;h=25;w=130;k=.8;p=[]
while 1:
 vy+=g;py+=vy;px+=vx
 if py>h:vy=-vy*k;vx=-vy
 if px>w:break
 p.append([int(px),int(py)])
py=0
while py<=h:
 px=0
 while px<w:
  if [px,py] in p or py==h:o('*')
  else:o(' ')
  px+=1
 o('\n');py+=1

```
> 1 votes

---
Tags: code-challenge
---


title: minigolf - display anything 3d

text:
# Question
Title: minigolf - display anything 3d
The goal is to write the smallest program in any language which displays any three dimensional output. It might be graphics, it might be ASCII art, but any reasonable person should immediately and unambiguously recognize it as "something 3d".

Opening external files or other resources is not allowed. All output has to be generated by your program.

The shortest code with a score higher than 1 wins.

# Answer
> 14 votes
## HTML, 1 character

This will appear as:

There are several other characters that look three dimensional (at least to me) if you don't like that one:

# ❒ ❍ ✰ ✞ ➫ ➮ ➪ ♨ ✐ ✏

# Answer
> 18 votes
## QBASIC 211 bytes

```
SCREEN 13
WINDOW(-160,-100)-(159,99)
FOR x=0TO 63
 PALETTE x,x*65793
NEXT
FOR i=16TO-16STEP-.1
 FOR j=16TO-16STEP-.05
  s=SQR(i*i/2+j*j/2)
  PSET(i*10,j*5+17.32*COS(s)),18.2*(COS(s)-SIN(s)*j/s)+31+RND
 NEXT
NEXT

```

The color for each pixel is chosen by adding the *z* value on the curve with the partial derivative with respect to *y*, generating a 'fake' lighting effect. The added random value helps to smooth the borders between regions. Produces something similar to the following:

# Answer
> 7 votes
## PHP, 23 characters

```
<?=" __\n/_/|\n|_|/\n";

```

Outputs:

```
 __
/_/|
|_|/

```

# Answer
> 7 votes
## Logo, 31 characters

My Logo is a bit rusty, but this should draw a torus:

```
repeat 180[rt 2 circle 45 fw 3]

```

Run it online: http://logo.twentygototen.org/9NxYy2Pw.

# Answer
> 6 votes
## Lua, 12 characters

```
print'(.Y.)'

```

# Answer
> 6 votes
## Python, 11 characters

```
print'()))'

```

Prints:

```
()))

```

It's a tube an overturned barrel.

# Answer
> 6 votes
# Mathematica 19

```
Graphics3D@Cuboid[]

```

# Answer
> 5 votes
# Perl, 7 characters

```
print A

```

Prints a road (which has a line painted across it) receding into the distance.

# Answer
> 4 votes
## Python 337 bytes

```
from pygame import*
from math import*
init();d=display;s=d.set_mode((640,480));a=0
def R(x,y,z,a):c,s=cos(a),sin(a);y,z=y*c-z*s,y*s+z*c;z,x=x*s-z*c-8,z*s+x*c;f=1e3/z;return-f*x+320,f*y+240
while s.fill(time.wait(5)):event.get();t=[R(x,y,z,a)for x in-1,1for y in-1,1for z in-1,1];[draw.line(s,-1,i,j)for i in t for j in t];a+=.01;d.flip()

```

A basic cube spinner.

# Answer
> 3 votes
## R - 73 characters

Way longer than the previous answer but i like it:

```
t=seq(0,2*pi,.01);r=1e3:1;plot(r%o%cos(t),r%o%sin(t),col=grey(1:1e3/1e3))

```

Basically draw a thousand circles of decreasing radius and shade of grey. Because of the default aspect ratio the result is more an ellipsoid than a sphere however.

# Answer
> 3 votes
# Python, 0 characters

Output:

```
>>>

```

Which can only reasonably be interpreted as some sort of angled surface :). I prefer to think of it as a jagged, concave cliff face.

---
Tags: code-golf
---


title: Implementing Binary Arithmetic

text:
# Question
Title: Implementing Binary Arithmetic
Given two binary numbers (strings containing 0s and 1s), perform operations on them, with one problem: **You must keep them in binary.** That means no going `binary(integer(n1)+integer(n2))` or anything like that.

**Input:** Two binary numbers, `n1` and `n2`, and a number between 0 and 3, `o`, defining the operator. The two binary numbers will be the same length.

**Output:** If `o` is 0, return `n1+n2` as a binary number.
If `o` is 1, return `n1-n2` as a binary number.
If `o` is 2, return `n1*n2` as a binary number.
If `o` is 3, return `n1/n2` as a binary number, using floor division.
**The output will not be the same length as the input. Please truncate all leading zeros.**

If you implement Two's Complement, subtract 10% off your character count, up to a limit of 50. Truncate to `length(n1)+length(n2)` digits.

**Test Cases:**
`n1=01010, n2=10101, o=0: 11111`
`n1=11110, n2=01010, o=1: 10100`
`n1=0010, n2=1000, o=2: 10000`
`n1=1011010, n2=0010001, o=3: 101`

Shortest code wins. Good luck!

# Answer
> 4 votes
## Python, 429 chars - 10% bonus = 386.1

Numbers are kept in little endian order, which is stretching the rules a bit but makes for easier processing. Maximum number size is 32 bits. Addition is standard, subtraction is implemented by x-y = x+~y+1 (throwing away the carry out of the 32 bits), multiplication is done using the Russian Peasant algorithm, and division is done with repeated subtraction.

```
z,i='01'
P=z*32
def A(x,y):
 r='';c=z
 for a,b in zip(x+P,y+P):k=(a+b+c).count(i);r+='0101'[k];c='0011'[k]
 return r[:32]
S=lambda x,y:A(A(x,''.join(chr(ord(c)^1)for c in y+P)),i)
def M(x,y):
 r=''
 while y:
  if y[0]==i:r=A(r,x)
  x=z+x;y=y[1:]
 return r
def D(x,y):
 x=(x+P)[:32];y=(y+P)[:32];r=''
 while x[::-1]>=y[::-1]:r=A(r,i);x=S(x,y)
 return r
def B(x,y,o):r=[A,S,M,D][o](x,y).rstrip(z)[:len(x)+len(y)];return[r,z][r=='']

```

`B` is the function of interest, here is its result on the test cases:

```
print B('01010','10101',0)
11111
print B('01111','01010',1)
00101
print B('0100','0001',2)
00001
print B('0101101','1000100',3)
101

```

# Answer
> 3 votes
### Scala 785:

Let's start with a famous quote of Bjarne Stroustrup, the inventor of C++, which in his great wisdom told us:

> Don't divide without necessity!

To make a submission to this fine question, we not only have to perform division - we have to implement it! Well - let's not talk about that.

```
object B{
val(l,o)=('1',"0")
type S=String
def n(v:S,c:S)=o*(c.size-v.size)+v
def g(n:S,m:S)=((n zip m)find(a=>a._1!=a._2)).getOrElse((l,'0'))._1==l
def a(x:S,y:S)=(((x zip y):\o)((n,m)=>{val s=Seq(m(0),n._1,n._2).filter(_==l).size
Seq("00","01","10","11")(s)}+m.tail))
def P(x:S,y:S)=t(a(n(x,y),n(y,x)))
def m(a:S,b:S)=(o/:a.zipWithIndex.filter(_._1==l).map(x=>b+o*(a.size-x._2-1)))(P)
def x(x:S,y:S)=t(s(x,y))
def s(x:S,y:S)=((x zip y):\o)((n,m)=>{val s=Seq(if(n._1==l)'0'else l,m(0),n._2).filter(_==l).size
Seq("01","00","11","10")(s)}+m.tail)
def M(a:S,b:S)=if(b==o)a else t(x(n(a,b),n(b,a)))
def d(n:S,m:S):S=if(g(n,m))P(D(M(n,m),m),"1")else o
def D(a:S,b:S)=t(d(n(a,b),n(b,a)))
def t(s:S)={val r=(s.substring(s.size-math.min(s.size,32))).replaceAll("^0*","")
if(r=="")o else r}
}

```

As usual, I have a less golfed version too, to explain 1 or 2 points (and this thread has much space left):

```
object BinArithmetic {
  def normalize (v: String, cmp: String) = "0" * (cmp.size - v.size) + v
  def ge(n:String, m:String)=((n zip m)find(a=>a._1!=a._2)).getOrElse(('1','0'))._1=='1'
  def greaterEqual (a:String, b:String): Boolean = ge (normalize (a, b), normalize (b, a))
  def i(s:String)=if(s=="0")"0"else trim32(j(s))
  def j(s:String):String=if(s.size==0)""else{if(s(0)=='1')'0'else'1'}+j(s.tail)
  def add (x:String, y: String): String =
   (((x zip y) :\ "0")((b, a) => {
       List (a(0), b._1, b._2).filter (_ == '1').size match {
        case 0 => "00"
        case 1 => "01"
        case 2 => "10"
        case 3 => "11"
        }
    }+a.tail))
  def plus (a:String, b:String): String = {
    trim32 (add (normalize (a, b), normalize (b, a)))
  }
  def mul (a:String, b: String): String =("0" /: a.zipWithIndex.filter (_._1 == '1').map (x=> b+ "0" * (a.size - x._2 - 1)))(plus)
  def sub(x:String, y: String): String = trim32(s(x,y))
  def s(x:String, y: String): String =
   ((x zip y) :\ "0")((b, ü) => {
       List (if(b._1=='1')'0' else '1', ü(0), b._2).filter (_ == '1').size match {
        case 0 => "01"
        case 1 => "00"
        case 2 => "11"
        case 3 => "10"
        }
    }+ü.tail)
  def minus (a:String, b:String): String = if (b=="0") a else {
    trim32 (sub (normalize (a, b), normalize (b, a)))
  }
  def d(n:String,m:String):String=if(ge(n,m))plus(div(minus(n,m),m),"1")else "0"
  def div (a:String, b:String): String = {
    trim32 (d (normalize (a, b), normalize (b, a)))
  }
  def trim32 (s: String): String = {
    val res = (s.substring (s.length - math.min (s.length, 32))).replaceAll ("^0*", "")
    if (res == "") "0" else res
  }
}

```

Half way through golfing and obfuscating the code I changed the methods *add* and *s(ub)* a bit. Later I recognized that I didn't used the methods *i(nv)* and *j* which handled inversing numbers - my research showed that you can inverse a number as binary string, you can add "1" and so `sub (a, b)` should theoretically be the same as `add (add (a, inv(b)), "1")` but in practice, it isn't. :)

There are 4 sorts of Methods:

* preparation (normalize (a,b)) for example, which takes tow numbers, and makes them equal long
* core calculation methods (add, sub, mul, div)
* wrapping methods, which usually take (a,b) and normalize the call to the calculation methods with similar names (plus, minus)
* finishing methods, which post process the result (trim32)

The root is the add method.

```
def a(x:S, y: S) = (((x zip y) :\ "0")((n, m) => {
  val s=List (m(0), n._1, n._2).filter (_ == '1').size
  List ("00", "01", "10", "11") (s)
  }+m.tail))

```

:\ is the right-fold operator. x zip y produces the list of pairs (10), (01), (11) from "101", "011", combines it with the overrun of the last operation, starting with no such overrun 0, counts the 1s in the result and produces a micro String like "10" from it. The 0 gets the growing part of the output, while 1 is the new overrun. You learned that at elementary school, didn't you? Now you remember!

The mul - method is interesting:

```
def mul (a:String, b: String): String =
  ("0" /: a.zipWithIndex.filter (_._1 == '1').map (x=> b+ "0" * (a.size - x._2 - 1)))(plus)

```

From mul ("1010", "0110"), it takes a and zips with index ("1010"-\>0123 =\> 10, 01, 12, 03) filters those which are 1 in a: (10, 12) takes the b and adds (a.size=4 - (x.\_2=\[0,2\]) - 1) times a literal "0". 4-0-1 = 3, 4-2-1=1 =\> "0110"+"000", "0110"+"0". The result is put into the already defined plus operation, which is a normalized add.

div is just subtraction combined with addition:

```
def d (n:String, m:String):String=
  if (greaterEqual (n,m)) plus (div (minus (n, m), m),"1") else "0"

if (n > m) then n/m = (n-m)/m + 1 else 0
if (8 > 3)      8/3 = (8-3)/3 + 1
if (5 > 3)      8/3 = (5-3)/3 + 1 + 1
since ! (2 > 3) 8/3 =       0 + 1 + 1

```

Sub is just similar implemented like add. Thanks to cyclic nature of ints, it doesn't really matter if the result is positive or negative.

Maybe I try the 2s-complement part later again.

Invocation

```
val ba = B
ba.plus  (  "01010",   "10101") // 11111
res412: String = 11111
ba.minus (  "11110",   "01010") // 10100
res413: String = 10100
ba.mul   (   "0010",    "1000") // 10000
res414: String = 10000
ba.div   ("1011010", "0010001") // 101
res415: String = 101

```

# Answer
> 3 votes
## Smalltalk Squeak 4.x flavour, 570 bytes

**First Try**: define an operator in Object to evaluate any Object:

```
`x^self cull:x

```

We refine the eval message in Character to get the value:

```
`x^value

```

Then define bit ops with binary messages in Character:

```
&x^self class value:(x`1bitAnd:value)

|x^self class value:(x`1bitOr:value)

/x^self class value:((x`1bitXor:value)bitXor:$0`1)

```

/ is xor operator, because it looks like the truth table

```
01
10

```

Then add two more messages in Character for repeating in a String and concatanating

```
*n^String new:n withAll:self

,s^(String with:self),s

```

Or my favourite hack to gain 2 chars:

```
,s^'',(self`1+#[0]),s

```

Now create a new notation for accessing Array elements because `(x at:i)` costs two much. The operator @ could be used for at: and \<@ would then means that it starts from the right (0-based) because our bit-Strings are big-endian.

That would be

```
Object subclass:#At instanceVariableNames:'a i'classVariableNames:''poolDictionaries:''category:''

```

In At, we would define two methods for initializing and accessing:

```
a:b i:j a:=b.i:=j

`x^(a atWrap:0-i)`x

```

Since this costs to much, we will replace this nice thing by using Association. So we define the accessor message in String (or in SequenceableCollection)

```
<@i^self->i

```

And just define \` to retrieve the At value in Association:

```
`x^(key atWrap:0-value)`x

```

Now we are ready to implement the operations in String first, strip the $0 left:

```
\~c |x|(x:=self)size>1or:[^x].c=(x at:1)or:[^x].^x allButFirst\~c

```

Then the awfull bit sum +| (just a naive xor with carry)

```
+|y|x z c m n|(m:=(x:=self)size)<=(n:=y size)or:[^y+|x].c:=$0.z:=''.0to:m-1do:[:i|z:=c/(x<@i)/(y<@i),z.c:=c|(y<@i)&(x<@i)|(c&(y<@i))].m to:n-1do:[:i|z:=c/(y<@i),z.c:=c&(y<@i)].c=$0or:[^c,z].^z

```

Then the bit multiply \*| :

```
*|y|x z|x:=self.z:='0'.0to:y size-1do:[:i|$0/(y<@i)=$0or:[z:=z+|x].x:=x,$0].^z

```

Then the bit subtraction -| is using two complement. Result is truncated to receiver length, so it must not be negative:

```
-|y|n x|n:=(x:=self\~$0)size.^(x+|'1'+|($1*n,(y collect:[:c|c/$1])))last:n

```

Then a test \<| for bit less than:

```
<|y|m n|m:=self size.n:=y size.^m<n or:[m=n and:[self<y]]

```

Then the bit division /| (by subtraction) - this will also raise a zero divide exception when appropriate:

```
/|z| x y q t n|y:=z\~$0.x:=self\~$0.y='0'and:[1/0].n:=0max:x size-y size.q:=''.[n>=0]whileTrue:[t:=y,($0*n).n:=n-1.q:=q,(x<|t ifTrue:[$0]ifFalse:[x:=x-|t\~$0.$1])].^q

```

And finally the operation encoding - we reuse \<@ to access right to left 0-based:

```
y:y o:o|x|x:=self.^({[x/|y].[x*|y].[x-|y].[x+|y]}<@o)`1\~$0

```

The small test suite:

```
self assert: ('01010' y:'10101' o:0) = '11111'.
self assert:('11110' y:'01010' o:1) = '10100'.
self assert:('0010' y:'1000' o:2) = '10000'.
self assert:('1011010' y:'0010001' o:3) = '101'.

```

The longer test suite:

```
| n |
n := 100.
0 to: n do: [:i|0 to:n do:[:j |
    self assert:  (i printStringBase:2)+|(j printStringBase:2)\~$0=(i+j printStringBase:2)]].
0 to: n do: [:i|0 to:n do:[:j |
    self assert:  (i printStringBase:2)*|(j printStringBase:2)\~$0=(i*j printStringBase:2)]].
0 to: n do: [:i|0 to:i do:[:j |
    self assert:  (i printStringBase:2)-|(j printStringBase:2)\~$0=(i-j printStringBase:2)]].
0 to: n do: [:i|1 to:n do:[:j |
    self assert:  (i printStringBase:2)/|(j printStringBase:2)\~$0=(i//j printStringBase:2)]].

```

And the score is given by:

```
{Object>>#`. SequenceableCollection>>#<@. Association>>#`}
    , ({#`. #*. #&. #|. #/. #,} collect:[:selector | Character>>selector])
    , ({#\~. #+|. #-|. #*|. #/|. #<|. #y:o:} collect:[:selector | String>>selector])
    detectSum: [:method | method getSource size].

```

Which is 921 chars...

---

We can do much better if we use Boolean instead of Integer. They can be easily transformed in character:

Implement in True:

```
c^$1

```

And in False:

```
c^$0

```

Now transform a binary Character in Boolean, implement in Character:

```
b^self=$1

```

Now logical operations are expressed much simply in Character:

```
&x^(x b&self b)c

|x^(x b|self b)c

/x^(x b xor:self b)c

```

Plus the two operations to repeat and concatenate:

```
*n^String new:n withAll:self

,s^self*1,s

```

Now, the message size is long, let's create a shorter binary message in String:

```
\n^self size-n

```

We shorten the message for stripping leading chars in String:

```
~c|x|(x:=self)\1<1or:[c~=(x at:1)or:[^(x last:x\1)~c]]

```

Now we'd better implement binary \>= rather than \< for division, let's call it \>~ in String:

```
>~y^self\0>(y\0)or:[self\0=(y\0)and:[self>=y]]

```

Now back to the operations, we will call them + - * / even if we have to override existing methods in String (they are presumably not used):

```
y:y o:o|x|x:=self.^({[x/y].[x*y].[x-y].[x+y]}<@o)value~$0

+y|x z c m n|(m:=(x:=self)\1)<=(n:=y\1)or:[^y+x].c:=$0.z:=''.0to:m do:[:i|z:=c/(x<@i)/(y<@i),z.c:=c|(y<@i)&(x<@i)|(c&(y<@i))].m+1to:n do:[:i|z:=c/(y<@i),z.c:=c&(y<@i)].c=$0or:[^c,z].^z

-y|n x|n:=(x:=self~$0)\0.^(x+'1'+($1*n,(y collect:[:c|c/$1])))last:n

*y|z|z:='0'.0to:y\1do:[:i|(y<@i)b and:[z:=self,($0*i)+z]].^z

/z| x y q t|y:=z~$0.x:=self~$0.y='0'and:[1/0].q:=''.(0max:x\0-(y\0))to:0by:-1do:[:n|t:=y,($0*n).q:=q,(x>~t and:[x:=x-t~$0.$1b])c].^q

```

The score is now

```
methods := {SequenceableCollection>>#<@. True>>#c. False>>#c}
    , ({#b. #*. #&. #|. #/. #,} collect:[:selector | Character>>selector])
    , ({#\. #~. #+. #-. #*. #/. #>~. #y:o:} collect:[:selector | String>>selector]).
methods detectSum: [:method | method getSource size].

```

That is 742 chars

Another snippet to browse our code alltogether:

```
methods do: [:e | e methodClass organization classify: e selector under: '*CodeGolfBinaryArithmetic'].
SystemNavigation default
    browseMessageList:
        (methods collect: [:e | MethodReference class: e methodClass selector: e selector])
    name: 'CodeGolfBinaryArithmetic'

```

We can further reduce the division to repeated subtraction (slower):

```
/z|x y|y:=z~$0.x:=self~$0.y='0'and:[1/0].x>~y or:[^'0'].^x-y/y+'1'

```

We can also omit 1/0 for ZeroDivide exception, anyway the result will be infinite on a computer with infinite memory after an infinite time:

```
/z|x y|y:=z~$0.x:=self~$0.x>~y or:[^'0'].^x-y/y+'1'

```

We can also reduce addition to a recursive form:

```
+y|x|(x:=self)\0>0or:[^y].y\0>0or:[^x].^x<@0&(y<@0)*1+(x first:x\1)+(y first:y\1),(x<@0/(y<@0))

```

And we now are at 570 chars... Not bad for Smalltalk.

---
Tags: code-golf, number, arithmetic, binary
---


title: Alien Name Generator

text:
# Question
Title: Alien Name Generator
**Task**

Write a function to generate names of aliens and their worlds, so that the output is of the form:

```
Greetings Earthfolk, I am ____ of the planet _____.

```

**"Rules"**

Best space-sounding-ness to code length wins.

The more diversity the better.

Dictionaries/look-up tables count towards code length.

Random number generators definitely allowed, other libraries less so.

Provide examples of the output.

# Answer
> 3 votes
# PHP - 283 with line breaks.

Here's my code for alien sounding words. My goal was to make it sound like a legitimate language without difficult pronunciation. The apostrophe's suffix the preceding letter with the 'yeh' sound (e.g. GYEH, DYEH, FYEH, etc.). All vowels are of the long-vowel sound, with the exception of A and E, which are short. Granted, this sounds like a single language rather than many diverse languages, but I don't care.

```
<?$a=$z="";function w(){$k=array("B","D","F","G","J","K","L","M","N","P","T","V","W","Z");$v=array("A","E","O","U","'");return$k[rand(0,13)].$v[rand(0,4)];}for($i=0;$i<rand(3,8);$i++){$a.=w();}for($i=0;$i<rand(3,8);$i++){$z.=w();}echo"Greetings Earthfolk, I am $a of the planet $z.";

```

Here's the ungolfed version:

```
<?php

$a=$z="";

function rk() {
    $k = array("B","D","F","G","J","K","L","M","N","P","T","V","W","Z");
    return $k[rand(0,13)];
}
function rv() {
    $v = array("A","E","O","U","'");
    return $v[rand(0,4)];
}
function rp() { return rk().rv(); }

for ($i=0; $i < rand(3,8); $i++) { $a .= rp(); }
for ($i=0; $i < rand(3,8); $i++) { $z .= rp(); }

echo "Greetings Earthfolk, I am $a of the planet $z.";

?>

```

Sample outputs:

* Greetings Earthfolk, I am **NEMEWEJU** of the planet **N'VUMELULOFU**.
* Greetings Earthfolk, I am **FUM'FELE** of the planet **WUW'JEDUG'GELA**.
* Greetings Earthfolk, I am **ZUDEWEGUPOGE** of the planet **LUNOT'ZEJALOTU**.
* Greetings Earthfolk, I am **M'DOMAMO** of the planet **WUWAGUBU**.

# Answer
> 25 votes
## APL (72)

Not entirely serious, but I couldn't resist. The names are generated from a subset of the APL charset. The names are between 5 and 14 characters long.

```
{'Greetings Earthfolk, I am'⍺'of the planet'⍵}/{⎕AV[186+{?25}¨⍳4+?9]}¨⍬⍬

```

Example output:

```
Greetings Earthfolk, I am  ⌹⍒|⍟∩⊤∩⍉⊂⊥⌽  of the planet  ∩⌹⍱⍎∪≢⊂∩
Greetings Earthfolk, I am  ⍕≡|⍕⍋!⍟⌹  of the planet  ⊂⊤⊤⌽⍟⊖⍱⊤⊤⍟⊥
Greetings Earthfolk, I am  ≢⍉⊂⍫⊂  of the planet  ⍋⌽!⍟⍉⊂∪≢

```

# Answer
> 12 votes
# Perl, 51 characters

```
print"Greetings Earthfolk, I am ~ of the planet ~."

```

The aliens communicate using a special space language that is not translatable in human text or speech. It is customary to use the character `~` to represent any word in the aliens' native tongue. Thus this answer is very space-sounding and also contains a great deal of diversity, which, unfortunately, is not able to be adequately represented using a standard character set.

# Answer
> 10 votes
### GolfScript, 85 characters

```
26,{97+}%{9,{;..,rand=}%@@}2*;;"Greetings Earthfolk, I am "\+" of the planet "+\+"."+

```

(online test version)

```
Greetings Earthfolk, I am mfevurnoh of the planet pclqvbpcu.
Greetings Earthfolk, I am niuzigmuu of the planet wdkosibdb.
Greetings Earthfolk, I am tvihxsxhd of the planet depkxwcto.

```

Pclqvbpcuans and wdkosibdbeans apologise for having chosen such a difficult name for us to pronounce for their planet. Tvihxsxhd's first parent also apologises for the double "x" in tvihxsxhd's name. He said he would never expect their child to travel to Earth.

longer version, but more pronounceable names:

### GolfScript, 105 characters

```
"aeiouy".26,{97+}%\-{5,{;..,rand=2$.,rand=}%@@}2*;;"Greetings Earthfolk, I am "\+" of the planet "+\+"."+

```

(online test version)

Sample output:

```
Greetings Earthfolk, I am nirexahuji of the planet hulabasesa.
Greetings Earthfolk, I am xepozidylo of the planet wuxasidape.
Greetings Earthfolk, I am jypakivixy of the planet lutegujyxo.

```

For those who are claiming that they wrote us a letter, not spoke to us (and thus capitalisation is important), this can be fixed in as few as six characters:

```
26,{97+}%{9,{;..,rand=}%(32-\+@@}2*;;"Greetings Earthfolk, I am "\+" of the planet "+\+"."+

```

(test)

```
"aeiouy".26,{97+}%\-{5,{;..,rand=2$.,rand=}%(32-\+@@}2*;;"Greetings Earthfolk, I am "\+" of the planet "+\+"."+

```

(test)

# Answer
> 5 votes
Javascript

golfed ( 186 bytes )

```
function f(){for(c=[],b=0;new Date%30+2>b;)c[++b]=String.fromCharCode(Math.random()*25|0+(b<2?65:97));return c.join('')}alert('Greetings Earthfolk, I am '+f()+' of the planet '+f()+'.')

```

Example Output:

> Greetings Earthfolk, I am Kugwegoysuseq of the planet Esagqwsakeges.
> Greetings Earthfolk, I am Ui of the planet Oq.
> Greetings Earthfolk, I am Qeuseoswwusk of the planet Gsyuemaeqqwa.
> Greetings Earthfolk, I am Usyssacemsiiokk of the planet Mgscemkaooaggku.
> Greetings Earthfolk, I am Egugskkgmk of the planet Ecakmkayys.

Keep in mind without the bulky text in the output, the function alone is 121 bytes.

Also the names and the planet names are the same character len so I can save a few characters and use `new Date%30+2` however if this is an issue just run them a ~hundred ms apart.

# Answer
> 3 votes
Python Code :

This code will generate random words of random length .

```
from random import *;t=range;l=map(chr,t(97,123));k=m="";r=randint
for i in t(r(1,100)):k+=l[r(0,25)]
for i in t(r(1,100)):m+=l[r(0,25)]
print "Greetings Earthfolk, I am",k," of the planet",m

```

Sample output:

```
Greetings Earthfolk, I am ixpygrfoswpkby  of the planet kanhkcg
Greetings Earthfolk, I am ijojukgjfxcbdt  of the planet zvllqgtqihkxy
Greetings Earthfolk, I am svbwsgrwgedfshw  of the planet inepzkdzerbkscy
Greetings Earthfolk, I am srixnnlqendbnbcqbghpdfotvxhfjidpdypzhkoddtbfhbjneaagnxtfqlbikfmrfrjwkwjoordvmks  of the planet qxyrvaxwnktqffbwcloeznkzuhkwzbwusksaychspjedtvrwxzjeoxtymrgfhqelqrwhquxrlvjbnbghiml

```

The last one is most "aliener" among the random outputs :D ..

We can even shorten the code more by adding the restriction of having the length of the planet's and alien's name of same length

```
from random import *;t=range;l=map(chr,t(97,123));k=m="";r=randint
for i in t(r(1,100)):k+=l[r(0,25)];m+=l[r(0,25)]
print "Greetings Earthfolk, I am",k," of the planet",m

```

Sample outputs :

```
Greetings Earthfolk, I am grtmsmjxbcvfcqfrvnmxuburprkgofstzemaflrbwtxabpdmmkhohntmvgkwcntjhefvrbcuzbdkrrgbxgsbwkrevi  of the planet mzuykipozdfhzalajaarqlrcoebmalrmfdvevieldqmuojwsfjbcfxdwwxakilcpwprdyedzplhxyafstcbpwdfzor
Greetings Earthfolk, I am rltfsxhaiybpqthmkwprepkchbeprxnkiaoyaujwehgsbafxwikenohviyxnj  of the planet qdgoyjqcwlopfgciethfqfaffhloqbmjkkonwutabozgbmzpyrsftiunucnse
Greetings Earthfolk, I am ynyhetukywsfgllbzejrmqygbzerhbrnorflri  of the planet qgihkeymaujjgltgzaeyfhnbqyzjtlpsnpnmbl

```

# Answer
> 1 votes
# Lua, 211

```
m,c=math.random,("").char print(((" "):rep(9):gsub(".",function()return c(("aeiouy"):byte(m(1,6)))end):gsub(".-",function()return c(m(97,122))end):gsub("^.......","Greetings Earthfolk, I am %1 of the planet ")))

```

> Greetings Earthfolk, I am toqujor of the planet aeilywyvuief
>
> Greetings Earthfolk, I am kyvirux of the planet ymofoyyxidyw
>
> Greetings Earthfolk, I am hooikoe of the planet exucedimetez
>
> Greetings Earthfolk, I am dytudiu of the planet ueitebeyoben
>
> Greetings Earthfolk, I am denecub of the planet ufolyvooutab

---
Tags: code-golf, string
---


title: Display a bézier curve in the browser

text:
# Question
Title: Display a bézier curve in the browser
The goal is to display a bézier curve in any classical browser (except maybe old IE versions, because... are they really browsers?) **client side**.

**Rules:**

* You must provide one or more files (or their content). These files must contain all the code.
* The code must work offline, no imports from a remote source. No installation should be needed on the computer (except a vanilla browser).
* This is a Javascript contest. A very simple way would be to use `SVG` files that can be read with browsers. Don't!
* No need to pass the W3C validator test, you can omit the doctype and the surrounding tags (`html`, `head`, `body`, ...)
* The input can take any form: GET, POST, written in the code, etc.
* The quadratic bézier must be implemented. (2nd degree bézier: starting point, ending point and 1 intermediate point). It means 3 points (= 6 coordinates) must be given in whatever format you prefer (XML, JSON, ...).
* If you don't know what a bézier curve is, you should! Check on **Wikipedia** to know about it.

**Scoring:**

* In his great kindness, OP offers you 10'000 point just by posting a valid answer.
* The sum of the sizes of the files in bytes will give negative points. 1 byte = -1 point\*.
* Implementing the cubic bézier curve **instead of** the quadratic multiplies your points by 120%.
* Implementing n-th degree bézier curve **instead of** the quadratic or cubic double your points. (Which means implementing both the cubic and the n-th degree is useless, pointless and very dumb).
* Implementing filled bézier (with inner color) will double your points again.
* There is no limit in the number of files or libraries you use, just remember adding jQuery, for example, already gives you about -26'000 points.

The contestant with the highest score wins. *(duh!)*

\*A 10'000 characters answer gives you 0 points.

# Answer
> 7 votes
## 39240 points (190 chars)

```
<script>P='<svg><path stroke=red d=M'+X[n]+','+Y[n]
for(t=N=99;t--;P+='L'+x+','+y)for(x=y=i=0,z=Math.pow(1-t/N,n);i<=n;z*=t/(N-t)*(n-i)/++i)x+=z*X[i],y+=z*Y[i]
document.write(P+'>')</script>

```

Input is supplied in three variables: `X` and `Y` hold the coordinates, and `n` holds the degree of the polynomial. If more coordinates are supplied than are needed, the surplus ones are ignored. The line is stroked in red and filled in black.

This example draws substantially from the existing ones, but with an improvement of 40% in character count over the current best character count I think it's worth a separate answer.

Demo: http://jsfiddle.net/MBCGJ/7/

This is stretching the flexibility of the rules too far IMO, but three characters can be saved by making `N` a "fineness" parameter which must be initialised along with the input coordinates and degree.

Also, Chrome at least doesn't care about closing the `path` element at all, which allows saving the 4 chars `+'>'`, so if that works cross-platform and the fineness parameter abuse is allowed this can go down to 183 chars.

---

The preferred way of rendering Bézier curves is, of course, adaptive subdivision using the de Casteljau algorithm. Unfortunately this uses more characters because it's necessary to do a test to decide whether to subdivide and then to do a moderate amount of work for the subdivision itself. Currently I'm at **371 chars**, although I think this could be reduced with an explicit stack.

```
<script>P='<svg><path stroke=red d=M'+X[0]+','+Y[0]
function Z(A,B,E,F){function d(p,q){return(t=A[p]-A[q])*t+(t=B[p]-B[q])*t}for(e=i=0;++i<n;e|=b+c-d(n,0)+Math.sqrt(3.9*b*c)>0)b=d(i,0),c=d(n,i)
for(E=[],F=[i=-1];e?i++<n||Z(E,F)|Z(A,B):0;)for(E[i]=A[0],F[i]=B[j=0];j<n-i;B[j]=(B[j]+B[++j])/2)A[j]=(A[j]+A[j+1])/2
P+='L'+A[n]+','+B[n]}Z(X,Y)
document.write(P+'>')</script>

```

The figure 3.9 in the middle there is the quality parameter, which must be less than 4 to avoid infinite recursion. The closer it gets to 4, the better the quality.

http://jsfiddle.net/FrJLn/2/

# Answer
> 6 votes
### 38,716 points (321 chars)

```
<canvas id="c"></canvas><script>function c(n,k){return k<1||c(n-1,k-1)*n/k}function b(p,f){d=document.getElementById('c').getContext('2d')
for(t=0;t<1.009;t+=0.01){n=p.length-1
x=y=i=0
e=Math.pow
for(;i<=n;z=c(n,i)*e(1-t,n-i)*e(t,i),x+=z*p[i][0],y+=z*p[i][1],i++);d.lineTo(x,y)}d.stroke()
d.fillStyle=f
d.fill()}</script>

```

Given an array of points and the desired fill colour, the `b` function draws an n-th degree bézier curve onto the canvas. It uses the binomial theorem to calculate the location of 101 different points along the curve, and then joins them together with straight lines.

Example

# Answer
> 4 votes
# 716 Chars - 37136 points

```
<script>function f(n){return n<1||n*f(n-1)}function c(n,k){return f(n)/(f(k)*f(n-k))}U=")*Math.pow(",G="createElementNS",$="setAttribute",d=document,w="appendChild",y=["",j=""];window.onload=function(){v=d.getElementById("s");q=prompt().split(" ");e=q.length-1;for(z=0;z<=e;z++){q[z]=q[z].split(",");p=q[z]={x:q[z][0],y:q[z][1]};_=d[G]("http://www.w3.org/2000/svg","circle");_[$]("cx",p.x);_[$]("cy",p.y);_[$]("r",5);_[$]("fill","red");v[w](_);for(u=0;u<2;u++)y[u]+="(c("+e+","+z+U+"1-t,"+(e-z)+U+"t,"+z+")*q["+z+"]."+"xy"[u]+")"+(z^e?"+":"")}for(t=0;t<=1.01;t+=0.01)j+=eval(y[0])+","+eval(y[1])+" ";l=d[G]("http://www.w3.org/2000/svg","polyline");l[$]("points",j);l[$]("stroke","red");v[w](l)}</script><svg id="s"/>

```

Try it in this JFiddle

You will be prompted to provide your points in the following format:

`x1,y1 x2,y2 x3,y3 x4,y4 x5,y5`

## Check list

* n-degree handled
* beziers are filled
* no external libraries
* plots control points

An example output of a 34th degree curve (non filled):

# 441 Chars - 38236 points

This doesn't plot the control points and it, shamelessly, uses grc's n-choose-k function. so it's not my real submission

```
<script>function c(n,k){return k<1||c(n-1,k-1)*n/k}V=Math.pow,$="setAttribute",d=document,window.onload=function(){A=prompt().split(" ");e=A.length-1,j="";for(t=0;t<=1.01;t+=0.01){x=y=0;for(z=0;z<=e;z++)p=A[z].split(","),f=c(e,z)*V(1-t,e-z)*V(t,z),x+=f*p[0],y+=f*p[1];j+=x+","+y+" "}l=d.createElementNS("http://www.w3.org/2000/svg","polyline");l[$]("points",j);l[$]("stroke","red");d.getElementById("s").appendChild(l)}</script><svg id="s"/>

```

# Answer
> 1 votes
# 186 bytes (39256 points?)

```
<script>function m(a,j,l){return l?m(a,j,--l)*(1-i)+m(a,j+1,l)*i:a[j]}P='<svg><path stroke=red d='
for(i=0;i<=1;i+=1/64)P+='ML'[i&&1]+m(X,0,n)+','+m(Y,0,n)
document.write(P+'>')</script>

```

Usage is exactly the same as Peter Taylor's solution. Also credits to Peter for the svg path approach (I wanted to use a canvas but it turns out to be longer). I would normally delete the "stroke=red" part (to get 175 bytes) but I kept it for having a fair comparison.

---
Tags: code-challenge, math, javascript
---


# Question
Title: Challenge: take ciphered text and decipher, also print out if it was offset to the left or right
Problem:

Take input text like this: (all input should be considered strings)

```
 Upi djpi;f ytu yu[omh pmr yp yjr ;rgy.

```

And figure out if it was offset left or offset right (on a standard qwerty keyboard as pictured below).

Also only keys that output something to the screen are considered valid, so these keys: caps, shift, tab, enter, delete(backspace), should not be considered when doing this challenge.

Once you have figured out what the offset is, print out the offset and the correct text.

For example the above input would have this output

```
 text: You should try typing one to the left.
 offset: right

```

Your program has to *'know'* that the sentence is correct before it prints out. (so no asking for user verification). Also no using libraries (should be a given).

All input will begin with a capital and end in a period (the period will not be offset left or right so you won't be able to use it to determine the offset.)

Another example:

```
U kujw oeife'nnubf xibrwara.

I like programming contests.

```

Some input samples to use:

```
 X'ra 'bs sifa 'ew ai o'aaw.
 Yjod vpmysod sm stnoysto;u ;pmh eptf.
 Rgw x'r ;b rgw g'r qwbr iyr ri v'r.
 Og upi vtrsyr s d,s;; fovyopmstu pg yjr ,pdy vp,,pm rmh;odj eptfd yjrm upi vsm vjrvl upit piy[iy gpt yjpdr eptfd' yjr eptf ayjra smf yjr eptf asmfa str imowir ejrm pggdry ;rgy smf pggdry tohjy. //<< don't put this deciphered text in your answers.

```

And **bonus** option: write your program to be able to handle the input switching offsets.

Example above with switching offset:

```
Upi djpi;f ytu yu[omh ibw ri rgw kwdr.

text: You should try typing one to the left.
offset: right -> index[21], then left.

```

Winning criterion:

* Faster code gets more points (out of 10) so O(logn) would score more then O(n^2) solutions (obviously).
* Elegance (out of 20) There is a very elegant and simple solution to this problem. The closer you get to the simple solution the higher your score. (bonus +5 if you think of something simpler then my solution).
* This is not a code golf, but concise readable code will be scored (out of 10).
* Bonus is all or nothing for 5 extra points.

So A perfect score would be 40 but you could score up to 50 if you get both bonuses.

bonus +2 if you read *all* instructions

# Answer
## Python

The original version didn't deal with punctuation too well, so here's a revised version.

```
r = dict(zip('\\qwertyuio\'asdfghjkl;/zxcvbnm|:"?', 'qwertyuiopasdfghjkl;\'zxcvbnm,Q"AZ'))
l = dict(zip('wertyuiop[\'asdfghjkl;xcvbnm,.{:"<', 'qwertyuiop;\'asdfghjklzxcvbnm,PL:M'))
shifts = {'right': r, 'left': l}

def shift(ciphered):
    letters = set(ciphered)
    if letters & set('p[{,<') or any(i in ciphered for i in ('yjr', 'smf')):
        return 'left'
    elif letters & set('qz\\|/?') or any(i in ciphered for i in ('rgw', '\'bs')):
        return 'right'
    else:
        return 'right' if ciphered.count('w') > ciphered.count('y') else 'left'

def decipher(ciphered):
    ciphered = ciphered.split('.', 1)[0].lower()
    shift_ = shift(ciphered)
    text = ''.join(shifts[shift_].get(i, i) for i in ciphered).capitalize()
    print 'text:', text + '.'
    print 'offset:', 'left' if shift_ == 'right' else 'right'

decipher(raw_input())

```

This is how it works:

* If any of the characters `p[{,<` are in the ciphered string, or `yjr` or `smf` (`the` and `and` shifted right respectively) are in the string, then the string must have been shifted right.
* If any of the characters `qz\|/?` are in the ciphered string, or `rgw` or `'bs` (`the` and `and` shifted left respectively) are in the string, then the string must have been shifted left.
* If neither of the above are true, then we compare the counts of `'w'` and `'y'` in the string. If there are more `'w'`s, then it is most likely to have been shifted left, because `'e'` is more common than `'u'` in English. If not, then it probably would have been shifted right, since `'t'` is much more common than `'q'` in English.
    + The original function used `'w'` and `'s'`, however using `e/u` and `q/t` will theoretically produce much stabler results, as the frequency differences between the letter pairs are higher than those of the original `e/d` and `q/a`.
    + This will work for most strings, however theoretically there might be some strings who will give the wrong output. (If you find one, post the offender in the comments and I will try to make the test more stable)
* We reverse-shift the string accordingly, to produce the output.

Note that if there is a comma in a string that has been shifted right (ie there is a `.` in the ciphered string excluding the one at the end), then this will not work, as the function only deciphers the part before the first period in the string.

Here are some sample test results.
> 4 votes

# Answer
## Tcl

```
set right {q w w e e r r t t y y u u i i o o p p {[} {[} \] \] q Q W W E E R R T T Y Y U U I I O O P P {[} {[} \] \] Q a s s d d f f g g h h j j k k l l {;} {;} ' ' a A S S D D F F G G H H J J K K L L {;} {;} ' ' A \\ z z x x c c v v b b n n m m , , \\ \\ Z Z X X C C V V B B N N M M , , \\}
set left {q \] w q e w r e t r y t u y i u o i p o {[} p \] {[} Q \] W Q E W R E T R Y T U Y I U O I P O {[} P \] {[} a ' s a d s f d g f h g j h k j l k {;} l ' {;} A ' S A D S F D G F H G J H K J L K {;} L ' {;} \\ , z \\ x z c x v c b v n b m n , m \\ , Z \\ X Z C X V C B V N B M N , M}
gets stdin data
set len [string length $data]
set min 0
set res {}
foreach {d} {left right} {
   set trans [string map [set $d] $data]
   if {[string first " and " $trans] > 0 || [string first " the " $trans] > 0} {set v 1} {
       if {[regexp {[\]\[]} $trans]} {continue}
       set vocals [regexp -all -nocase {[aeiou]} $trans]
       set v [expr {($vocals * 1. / $len)}]
   }
   if {$v > $min} {
       set res "$trans\noffset: $d"
       set min $v
   }
}
puts $res

```

I build a map to replace the characters with the next.
If there are strange characters in the output, I'll reject it.
As last chance I take the highest vocal/length count.

I claim the +2
> 2 votes

# Answer
## Lua

The idea is to determine which group of letters is prevailing: ABIUW or JOPY.
The former has frequent letters on next key to the right on the keyboard, the latter - to the left.

```
local strings = [[
Upi djpi;f ytu yu[omh pmr yp yjr ;rgy.
U kujw oeife'nnubf xibrwara.
X'ra 'bs sifa 'ew ai o'aaw.
Yjod vpmysod sm stnoysto;u ;pmh eptf.
Rgw x'r ub rgw g'r qwbr iyr ri v'r.
Og upi vtrsyr s d,s;; fovyopmstu pg yjr ,pdy vp,,pm rmh;odj eptfd yjrm upi vsm vjrvl upit piy[iy gpt yjpdr eptfd' yjr eptf ayjra smf yjr eptf asmfa str imowir ejrm pggdry ;rgy smf pggdry tohjy.
]]
for str in strings:gmatch'%C+' do
   str = str:lower()
   -- compare total counters of letters ABIUW and JOPY
   local _, left_ctr  = str:gsub('[abiuw]','')
   local _, right_ctr = str:gsub('[jopy]','')
   local offset = left_ctr - right_ctr
   offset = offset / math.abs(offset)  -- offset == (+1) or (-1)
   -- restore original string
   local original = ''
   local keyboard = "asdfghjkl;'?zxcvbnm,'qwertyuiop['"
   for c in str:gmatch'.' do
      local pos = keyboard:find(c, 1, true)
      c = pos and keyboard:sub(pos + offset, pos + offset) or c
      original = original..c
   end
   print('text: '..original:sub(1,1):upper()..original:sub(2))
   print('offset: '..({[-1]='right', 'left'})[offset])
   print()
end

```

---

Output:

```
text: You should try typing one to the left.
offset: right

text: I like progr?mming contests.
offset: left

text: C?ts ?nd dogs ?re so p?sse.
offset: left

text: This contais an arbitarily long word.
offset: right

text: The c?t in the h?t went out to b?t.
offset: left

text: If you create a small dictionary of the most common english words then you can check your output for those words; the word the and the word and are unique when offset left and offset right.
offset: right

```
> 1 votes

# Answer
# Haskell

Certainly not the fastest or smallest one, but at least now there is a Haskell solution!

## The idea

1. Write in the code the configuration of the `keyboard`, one string per keyboard line
2. Generate `left` and `right` shifted keyboard and build dictionaries of keys correspondences
3. Create a `ShiftString` method that convert a string with `right` or `left` dictionary
4. Write an `englishProb` function that compute the *least square* between frequency of a given string and the english language frequencies
5. Implement a method `chooseShift` that convert a string to `left` and `right` shifted sentences, compute the englishProb on them and return the dictionary minimizing the least square error
6. Write a `solve` method that take a string, choose the best dictionary, convert the sentence with it, and format the output as desired
7. Create the `main` function that use `solve` on input

## The code

```
import Data.Char
import Data.List

main :: IO()
main = do
    content <- getContents
    putStr . unlines . map solve . lines $ content

solve :: String -> String
solve s = "text:" ++ shiftString shift sc ++ ".\noffset: " ++ offset shift
    where sc = takeWhile (/='.') s
          shift = chooseShift sc
          offset sh | sh == left = "left"
                    | sh == right = "right"
                    | otherwise = "unknown"

chooseShift :: String -> [(Char, Char)]
chooseShift s = if (englishProb lefted >= englishProb righted) then left else right
    where lefted = shiftString left $ map toLower s
          righted = shiftString right $ map toLower s

englishProb :: String -> Double
englishProb s = squaredDiff stats
    where stats = map (\a@(x:_) -> (x,normalize $ length a)) . group . sort $ s
          normalize a = (fromIntegral a) / (fromIntegral $ length s)
          squaredDiff p = sum . map ((\x -> x*x) .  diff) . filter isAlpha $ p
          diff (c,v) = abs . (v-) $ lookup' c letterFreq
          isAlpha (a,_) = ord(a) >= 97 && ord(a) <= 122

keyboard :: [String]
keyboard = ["qwertyuiop[]\\", "asdfghjkl;'","zxcvbnm,./"," "]

right :: [(Char,Char)]
right = shiftKeyboardWith shiftR
    where shiftR l = (tail l)++[(head l)]

left :: [(Char,Char)]
left = shiftKeyboardWith shiftL
    where shiftL l = (last l):(init l)

shiftString :: [(Char,Char)] -> String -> String
shiftString m s = map (\c -> shiftChar c m) s

shiftChar :: Char -> [(Char, Char)] -> Char
shiftChar k d = reCast $ (\(Just b) -> b) $ lookup (toLower k) d
    where reCast = if (isUpper k) then toUpper else id

shiftKeyboardWith :: ([Char] -> [Char]) -> [(Char,Char)]
shiftKeyboardWith f = zip (concat keyboard) . concat $ map f keyboard

lookup' :: (Eq a) => a -> [(a,b)] -> b
lookup' k d = (\(Just b) -> b) $ lookup k d

letterFreq :: [(Char, Double)]
letterFreq = [ ('a',8.167)
             , ('b',1.492)
             , ('c',2.782)
             , ('d',4.253)
             , ('e',12.702)
             , ('f',2.228)
             , ('g',2.015)
             , ('h',6.094)
             , ('i',6.966)
             , ('j',0.153)
             , ('k',0.772)
             , ('l',4.025)
             , ('m',2.406)
             , ('n',6.749)
             , ('o',7.507)
             , ('p',1.929)
             , ('q',0.095)
             , ('r',5.987)
             , ('s',6.327)
             , ('t',9.056)
             , ('u',2.758)
             , ('v',0.978)
             , ('w',2.360)
             , ('x',0.150)
             , ('y',1.974)
             , ('z',0.074) ]

```

## Compilation

```
ghc shift.hs
./shift.hs < inputs

```

## Output

```
text: You should try typing one to the left.
offset: left
text: I like programming contests.
offset: right
text: Cats and dogs are so passe.
offset: right
text: This contais an arbitarily long word.
offset: left
text: The cat 'n the hat went out to bat.
offset: right
text: If you create a small dictionary of the most common english words then you can check your output for those words; the word 'the' and the word 'and' are unique when offset left and offset right.
offset: left

```
> 1 votes

# Answer
## Python 2.6 390 430 410 408 355 347 354 346 300 chars

**Updates**:

1. (Hopefully) fixed a bug with semicolons.
2. Horrible hack to make the middle row work properly :(
3. Golfed the hack a bit better
4. Fixed stupid printing
5. Realised I can assume left if not right!
6. Now deals with the whitespace in a much neater way. (after breaking it!)
7. Trimmed a bit all over
8. Changed the key condition for left or rightness
9. Changed some variable names and pruned the `lambda`
10. **Thanks to Volatility for some much neater ways to do things, and a general golf overhaul (see comments).**
11. Changed the letters it searches for to avoid redundancy (for instance the character `r` is likely to appear in all shifted sentences).

Golfed with help from Volatility. Algorithm compares the number of times the characters `'awg` and `mp;[y` appear in the text. The first set corresponds to `aoseh` shifted left, the second to `anolpt` shifted right. These unshifed letters are highly likely to appear in any sentence (each set should account for ~40% of the letters in a normal sentence) and are indicative of which shift occurred (the shifted letters are unlikely/forbidden to appear in the same sentence when shifted the other way).

To help with choosing which letters to use, I used the frequency of each letter to find the corresponding frequency of characters which appear in shifted sentences using this (slightly golfed for practice) program.

I don't think it handles punctuation very well for instance (commas?). Please leave comments with failure cases and I'll try to make it more robust :)

Usage

```
$ program.py
'Put text here with any escape characters if it\'s necessary.'

```

Code:

```
s=''.join(dict(zip('|{"?:<',"\['/;,")).get(x,x)for x in input().lower())
h=lambda b:sum(x in b for x in s)
i=h('mpsy;[')>h("'aiwg")
f="  \qwertyuiop[asdfghjkl;'/zxcvbnm,. "
t=''
for x in s:t+=f[f.find(x)+(1,-10)[x=="'a"[i]]*(-1)**i]
print'offset:',('righ','lef')[i]+'t\ntext:',t[:-1].capitalize()+'.'

```

**Explanation:**

* Ignore uppercase and replace "uppercase" symbols (ie capital "Q" shifted left is "|")
* Choose right if any characters from that small set, else right (this actually is sufficient for all the test cases!). Compare number of indicative 'left' and 'right' characters and chose left or right from this
* the shift string is as reduced as possible and as a result doesn't deal with the middle line wrapping around. 2 spaces at the start and 1 at the end deals with the whitespace
* deal with `'` if shifted left or `a` if shifted right by offsetting by 10 in the other direction. whitespace is found at index 0 in `s` so -1 or +1 match either 2nd or last character in s (both whitespace)
* print

**Failures:**
There are failure cases but the code will work with a very high probability if the sentence hasn't been specifically engineered to break it :)

> Boo proper nouns: `"\"b 'ookw dwkk ib Bwqrib;a gw's."`
> Right-shifted sentences without the letters `anoplt` but with some `'fqu`
> `"Wirrmd wirrg ypp."` fails whereas `"Wirrmd wirrg ypp upi lmpe."` succeeds (apologies) Left-shifted sentences without the letters `aeosh`
> 1 votes

---
Tags: code-challenge
---


title: Mozart golf - mini "Rondo"

text:
# Question
Title: Mozart golf - mini "Rondo"
Output "Mozart - Alla Turca" to stdout (see the sample for "reference implementation")

Try to find how to pack both synthesizer and the music into minimal size.

Requirements:

* Format suitable for feeding into `aplay -f cd` (signed 16-bit little endian, 2 channels);
* Entire music should be played (no skipped notes or parts, at least not less than in sample program), polyphony is not required though;
* Can't just call `/usr/bin/timidity`, `/usr/bin/sox` or something like that (e.g. require to install a special music module);
* Can't access network or assume that the music is available locally;

"Reference implementation" with parsable score: https://gist.github.com/vi/5478693
(Old sample Perl program: https://gist.github.com/vi/5447962)

# Answer
## Polyphonic, Haskell, ~~2826~~ ~~3177~~ 4719

Audio output: https://www.dropbox.com/s/nba6489tfet740r/hs-golf-turca.ogg

Features:

* All notes ~~from the *right hand*. I could of course add the left hand, too~~ (done that).
* Proper articulation of the staccato notes etc.
* Reasonably nice sound with dynamics. Not just simple volume modulation, but proper morphing of the attack character and overtone content, ~~like you get on a real piano~~ actually, rather more... hey this piece is supposed to be imitating Turkish Janissary bands, right?
* Reverb. Doesn't sound amazingly great, but not too bad, either.
* Dynamic compression. Don't ask...
* Dithering of the output. This is kind of ridiculous: with proper 16-bit resolution, hardly anybody would hear the quantisation artifacts, but to avoid including the binary library, I effectively use only 7-bits resolution, which I can cover with ASCII output. The dither itself is rather loud, no noise-shaping...
* Multithreaded calculation of polyphonic chords.

---

```
import Control.Parallel
main=mapM_ (\(d,s)->(\p->p>>p>>p>>p).putChar.toEnum.round.(+d).(*62).min 2.abs$s+1).zip(dθ 1).lim.rev.hgp 9. pl 9e6 (\_->0) . ä
 $[mT%8.1,t2%16.1,t3(∡7)%8,t4%8,t5%16,t3(∡7)%8,mT%8.1,t2%16.1,t3(tev arp8)%8,cdT%99] >>= \e->[e,e]
mM=ä[2-^8,1-^8,0-^8,1-^8,3-^4]
cM=ä[7-^20,8-^20,9.^4,F[(7,0),(6,1)](map((∡2).(.^4))[6,5,6])%0.75]
cMv=ä[10-^2,8.^4,9.^4,hom(.^4)[[24,5],[23,8,12],[22,4],[21,6,9],[22,3],[19,5,8],[20,4],[18,6,9],[17]]#7&(-14)%2.5,tr 2%0.4,1-^9,2-^12,1-^1]%4.5
 ⋎(ä[6-^4,lp(8.^4∡3)%(3/4),sil%2,lp(5.^4∡3)%h,lp(5.^4∡2)%h,1-^1∡7]&(-14)#7#4%5)
mMa f=ä[(1-3*f).^4,lp(5.^4∡(-2-f))%0.75,mMa f%1.5,mMa(f*2)%h,mMa f%1]#7
mTm=ä[mM%1,mM&2%1,mM#4&4%h,mM&7%h,mM&7%1,8.^4,ä[10.^4]%0.2,cM%1,cM%1,cM%0.85,ä[4.^4∡2,5.^2]#6#4%2]#7
mT=p$ä[mTm%8.1⋎(ä[sil%h,mMa 0%4,mMa 1%2.75,2.^4,(-2)-^2]&(-7)%8)]
m2=ä[ä(map((∡2).(.^4))[1,2,3,3]++[es[6,5,4,3]%h]++[0-^2∡2])%2
 ⋎(ä[sil%h,1.^4,8.^4,3.^4,10.^4,5-^2]⊿1.3&(-14)%2)]
t2=p$ä[m2&2%1.8,0-^5,m2&2%2,m2#7%1.8,(-2)-^5,m2#7%2,mT%3.5,cMv]
m3=ä$[3-^4,4-^4,5-^2]++map(-^4)[3,4,5,4,3,2,1,2,3,4,2,0]
m3a=ä[(ä[sil%(1/8),lp(8.^4)%1]:zw(\d n->ä[sil%(d/24),n-^1]⊿cos d)[0..][1,3,5],s),m3a%1]
m3ra=(map((%1). \[a,b,c]->es[a,c,b,c,a,c,b,c])[[1,3,5],[1,4,6],[-2,0,5]]!!)
t3 o=ä[ä[o$ḋ[m3%4,m3%2.5,1-^4,4-^4,2-^4,0-^4]&(-2)%7.5,1-^2∡7]%8
 ⋎(ḋ[sil%(3/8),m3a&4%2,m3a%h,m3a#4%h,m3a&1%1,m3a&4%2,m3a%h,m3a&1%(5/8),5-^2]&(-18)%8)]
mQ=es[2,1,0,2]
m4=mM⇆4
i4 e=ḋ[m4⇅11%h,m4⇅9%h,mQ⇆4⇅8%h,F[(5,e),(4,1)][mQ⇅7%h,mQ⇅5%h,m4&5%h,m4&7%h]%2,es[10,9,10,9]#2%h ]
mla[b,c,d]=ä[b-^4,lp(c-^4⋎(d-^4))%1]%1
i4a=ḋ[sil%h,ä(map mla[[1,3,5],[2,4,5],[1,3,5],[0,2,5]])#5%4,ä(map mla[[1,3,5],[2,5,7],[2,6,8]])#4%3,5-^2⋎(7-^2)]
t4=p$ä[ḋ[i4 1%4,i4 0%2.5,ä[mQ⇅6%h,mQ⇅4%h]#4#2%1,3-^2]%8⋎(i4a&(-9)%8)]
mlaa=mla[1,3,5]
m5=ä$map(-^8)[1..4]
i5=ḋ[m5⇅6%h,m5%h,m5&4%h,m5⇅9%h]
i5d=hom(-^4)[[2],[4,5],[0],[4,5]]%1
i5a=ḋ[sil%h,mlaa,i5d,mlaa,mla[-2,0,4],mlaa,i5d,sq 4[1,-1,-3,-2,-6,1]%2]&(-7)
t5=ḋ[ḋ[i5%2,i5%1.5,ä[8-^4,9-^4]#1%h,i5%2,ḋ[es[5,4,3,2,3,5,1,3,2,4,0,2]%2]%1.5,1-^2]%8⋎(i5a%8)
 ,p(ä[ä[i4 1%4,es[3,2,3,1,4,3,4,3,4,3,4,3]#2#1&7%1.5,m5⇅13%h,mQ⇅8%h,m5&7%(3/8),6-^8,mQ⇅7#5%h,6-^2]%8
 ⋎(ä[i4a%3.5,F[(1,-1),(7,0),(6,1)][hom(-^4)[[-2],[3,5],[2,5],[1,5]]%1]%1,mla[-3,1,4],mla[-3,2,4],hom(-^4)[[-2],[1,3],[-2],[2,4],[1,3]]%1.5]&(-9)%8)])%8]⊿0.8
am d=3-^d∡2∡5
amf=1-^υ∡2⋎(5-^1∡3)
vh v(c,d)=lp(ä[v-^12]:map(\t->ä[t⊿0%0.04,t%d])c,d)
aam=vh 11.am
aar=ä[1-^10,4-^10,6-^1]&4
eam=vh 10.em
dm=6-^1∡2⋎(11-^1)
em d=5-^d∡2⋎(9-^1)
cdM=ḋ[4-^8,3-^8,2.^8,3.^8,cdM%1]
cdT=ḋ[ä[3-^(8/3)∡7,10-^6,am 1,am 1,cdM&7%1,dm,aam 4.05%1,em(4/3),12-^4,am 1,am 1,cdM&7%1,dm,aam 1%1,eam 4%1]%12.5⋎(ä(sil%(11/24) : map((%1).(m3a&))[4,4,4,0,4,1,4,4,4,0,4,1])&(-18)%13.1)
 ,p(ä[ä[ä[8-^2]⊿2%h,aar%(3/8),10-^8,aar%1,aar%1,cdM&7%1,11-^1,vh 11(10-^4)%1,9-^(4/3)]%7⋎(ä(map m3ra[0,0,0,0,1,0,2])&(-7)%7)])%6.75
 ,ä[p(ä[12-^4])%(1/4),am 1,am 1,cdM&7%1,dm,aam 1%1,eam 4%1,amf,ä[3-^4,1-^υ,5-^4,1-^υ,3-^4,1-^4,3-^4,1-^4,5-^4,1-^2]%3.75∡7,ä[amf∡(-14)]%0.56,ä[amf∡(-14)]⊿0.8%1]%12⋎(ä(sil%(1/8):map((%1).(m3a&))[4,4,4,0,4,1,4,4,4]++[m3a&4%h,m3a&4%h,5-^(8/5)])&(-18)%12)]
type D=Double
data F=N Int D|F[(Int,D)][([F],D)]
φ⇸F a fs=F a$map(\(f,d)->(map φ f,d))fs
_⇸N i d=N i d
i##c
 |i<1=(i+7)##c/2
 |i>7=(i-7)##c*2
 |1>0=1.06**(c i+case i of{1->0;3->3;4->5;5->7;6->8;7->10;_->fri i})
pl dur acc(N n v)=(\ω η->map(sin.(\x->x+τ x^2/η). \i->v*exp(-i*η/s)*τ(i*v)*(0.8-τ((i-dur)/90))*sin(i*ω))[1..dur])(n##acc/15.5).exp$fri n/9
pl dur acc(F accm fs)=pl' dur (foldr(\(q,m)f i->if q==i then m else f i)acc accm) fs
pl' dur _ _|dur<=0 = []
pl' dur _ []=map(\_->0)[1..dur]
pl' dur acc((f,dr):fs)|n<-min dr dur=trans(round n)(foldr1(\a b->sum a`par`sum b`pseq`zw(+)a b)(map(pl(n+99)acc)f))$pl'(dur-dr)acc fs
trans n a b|(f,ol)<-splitAt n a,(or,l)<-splitAt 99 b=f++zw(+)ol or++l
fri=fromIntegral
F a fs#q=F((q,1):a)fs
N i d&n=N(n+i)d
f&n=(&n)⇸f
N i d⇅n=N(n-i)d
f⇅n=(⇅n)⇸f
N i d⇆_=N i d
F a fs⇆n=F a.reverse$take n fs
N i d⊿v=N i$d*v
f⊿v=(⊿v)⇸f
p=(⊿0.3)
n.^q=([F[][([N n 1],s/2/q)]],s/q)
n-^q=([N n 1],s/q)
(l,d)⋎(r,_)=(l++r,d)
(l,d)∡j=(l++map(\h->ä[h⊿0%0.01,h&j%100])l,d)
f%t=([f],s*t)
tr n=F[]$cycle[n-^15,(n+1)-^20]
ä=F[];ḋ=F$zip[6,3,7][1,1,1]
lp=ä.repeat
sil=N 0 0
tev f(l,d)=(map f l,d)
h=1/2
υ=4/3
s=4e+4
sq d=ä.map(-^d)
es=sq 8
arp8 n@(N i v)=F[][([n,ä[n⊿0%(1/8),n&7⊿(v/υ)%100]],s)]
arp8 f=arp8⇸f
hom q=ä.map(foldr((⋎).q)$sil%1)
dθ l=2*asin l/pi:dθ(abs.sin$l*1e+9)
rev ls=(\z->z id(foldr(\m sg->(\v->z(*v)(map(*0)[0..m*14349]++sg)sg)$abs(cos$(m*3)^2)-0.6)ls.take 9$dθ 1)ls)$(.lwp 3 0).zw.((+).)
lwp ω c(x:l)=c:lwp ω((x+c*ω)/(ω+1))l
lwp _ _ _=[]
hgp ω l=zw(-)l$lwp ω 0 l
lime e(x:l)
 |abs(e*x)>1,e'<-((e*8+abs(1/x))/9)=e':lime e' l
 |1>0=e:lime((e*49999+1)/5e4)l
lime _[]=[]
lim ls=zw(\a u->τ$a/9+max(-2)(min 2$a*u)/6)(map(*0)[0..500]++ls).lwp 9 0.lime 1$hgp 9 ls
zw=zipWith
τ=tanh

```

---

> $ make
> ghc -o bin/def0-hs def0.hs -O2 -fllvm -threaded
> \[1 of 1\] Compiling Main ( def0.hs, def0.o )
> Linking bin/def0-hs ...
> time sh -c 'bin/def0-hs +RTS -N4 \> hsoutp.pcm'
> 189.39user 138.41system 2:06.62elapsed 258%CPU (0avgtext+0avgdata 6440240maxresident)k
> 0inputs+0outputs (0major+403037minor)pagefaults 0swaps
> ffmpeg -loglevel panic -y -f s16le -ar 44.1k -ac 2 -i hsoutp.pcm hsoutp.ogg

---

Here's a partially ungolfed and commented version: https://gist.github.com/leftaroundabout/5517198.
> 12 votes

# Answer
## Python, 331+286 = 617 (0.548 bytes per note)

My solution uses a data file and a python script. The data file should be used as input to the script. I don't have aplay, but it works when I import it as raw data in Audacity with signed 16-bit PCM, little-endian, and 2 channels.

The data file is 331 bytes. Here's a python script which outputs it:

```
import sys
sys.stdout.write('\x08\x1c\x9d\xb9"\xc7\xea\xf0\xb7)\xc0D!u\x0bB~\'\x91S\xb2\x0c\xe9\xf8T;\xfd\xc13\xcf\xb9\xa6r>\xbc\xc5\xb4\xbb\xf8\xa4\x9a\x05H\xa0\x1d\x0eIq\t\\+\t\xdbn\x03\xc3&\x98\xa0\x11\xc5\xaa\xef\xbcSR^\x13\xe7\xc7\x0e\xc0\xa9^\x91Z\xfc\x02\x11\xb9\x1bE\xfc/=\xb8\xaf5<\x12\xa2\xc4\x02\xec\xdcO\xc2a\x04<Q\xfd\xe9L\xbc\xab%\xf5wX1F\xa6\x88\xddP\xfec(_#\xb4\x0bN\xba&m\xe3\xa4\x08Q\xdb\xd9\xf3<Q\xc6\xf6\x0e\xd7\xacd\x1f"g\xce\xae.\xb0\x90{|\x04\xc5X\xe6x>\xefE\xc8\xb0\xd2?N\x83?\x04\x86"a\xcc\x9b\x8fq\x9c\xce\xa2\xb6f\x9ab\x92\x9e:\xc0S\xcd\th\xb1\x87\xecT\x9d\xf4\n\xaf\xc9$`E5\xcc\xc5\xa0m\xcc\n8\xf8:\x03\xf5\x02H\xf3k\xe5\x86\xa64\x90\xa2\xc2w\xfa\xb7\xc0\x1e*2\x93\xca\x12\xe3^!\xd5yQ,LXW\xb4\x96D\x8dB\x9c`\xbf\x96`s;\xb7}\xeb\x8c\xebI\xa0o\x00\x08\xfe\xf1\xd2M3}\x8e\xd0\xda\x97\'\xca\x83-\x14\xda\xa1ET\n\xe8\xc7@\x1c\xa2a\xbb\xa7\x1b\x014\xdcz\xc7\xa6\xc4\x1d\x18\x04\r\xb1\x9e\xe3\xd0\x18<\x98`N?a\xe4\x8e\x9d\xd5\r\xe7Z[\xf4\xed\xf1PQ')

```

Here's the python script:

```
import sys
k=0
m=185
p=[]
q=[]
for c in sys.stdin.read():k=k*256+ord(c)
while k:
    v=k%m;k/=m
    if v<184:q+=[v]
    elif v-m+1:q+=p[v-184]
    else:m+=1;p+=[q];q=[]
for n in q:r=[1,2,3,4,6,8,12,15,16][n%9]*2000;sys.stdout.write(''.join(chr(int(i*1.06**(n/9)/4.3)%99)for i in range(r*3))+'\0'*r)

```

Note: If you're running Windows, use the `-u` switch for both scripts since stdin and stdout are dealing with binary data.
> 7 votes

# Answer
## GolfScript (129 + 369 = 498 bytes)

Both program and data file include unprintable characters, so I'm going to give Base64 and xxd representations.

Program (129 bytes):

```
MjU2YmFzZSA2OWJhc2VbMDpOXS8oNDMse1xbMSQpXS9cMiQ9Kn0vXCwpey19KyUuLDIvL3ppcHt+
TisyNSU6Tid7goqSm6SuuMPP2+j2/0FFSU1SV1xcYWdtdCc9OmY7MTc2MCosey41MD4qZioxNy8u
Li59JScnOm4rcHV0c30v

0000000: 3235 3662 6173 6520 3639 6261 7365 5b30  256base 69base[0
0000010: 3a4e 5d2f 2834 332c 7b5c 5b31 2429 5d2f  :N]/(43,{\[1$)]/
0000020: 5c32 243d 2a7d 2f5c 2c29 7b2d 7d2b 252e  \2$=*}/\,){-}+%.
0000030: 2c32 2f2f 7a69 707b 7e4e 2b32 3525 3a4e  ,2//zip{~N+25%:N
0000040: 277b 828a 929b a4ae b8c3 cfdb e8f6 ff41  '{.............A
0000050: 4549 4d52 575c 5c61 676d 7427 3d3a 663b  EIMRW\\agmt'=:f;
0000060: 3137 3630 2a2c 7b2e 3530 3e2a 662a 3137  1760*,{.50>*f*17
0000070: 2f2e 2e2e 7d25 2727 3a6e 2b70 7574 737d  /...}%'':n+puts}
0000080: 2f                                       /

```

Data (369 bytes):

```
LoDJFvCRQqNdL7+JDvjtSkX4HBS2FwgvjfdxAHrF1/DcMIBtG/g7QZBLLYHpzgaWaM1TaHwbtxG+
l1lqsL3A8nuprtpPI20YbHm3lf7NxmYNdEIMTlhwTG+TlSn802DzN3YgIwbcKbtty9gWmF2nVS55
iJHQZd4HCcokoLRwH1g2XqP8Yo5xj5/YQm9DH85obUv47mii5n+PwsoJZ6yaz4eSpGps6dQMl+Pa
YP/WC6cVDBBGs3vq5cGe51H2u7oVArFuHrsI2sHkGNYHlhWudKn5RRvJhe3sxfrtQE/MekKRuZBt
f4B9qdyss66vFipSi1zf2MXF9A/CzwvMQ/t9PEtxw8kzxxikp2Ek3kc9TiamLl+iG2vjdWp84JzY
Mg6cE+3bFI4kVdn+d1NEnBR/S9HMnksgEc9sdAcyWsbSaGjwetwGTr7UXkpKO9aHF01D2i5pCO40
/keR0+a+NsBEOXZfatpXav44AJjalywtLeWu

0000000: 2e80 c916 f091 42a3 5d2f bf89 0ef8 ed4a  ......B.]/.....J
0000010: 45f8 1c14 b617 082f 8df7 7100 7ac5 d7f0  E....../..q.z...
0000020: dc30 806d 1bf8 3b41 904b 2d81 e9ce 0696  .0.m..;A.K-.....
0000030: 68cd 5368 7c1b b711 be97 596a b0bd c0f2  h.Sh|.....Yj....
0000040: 7ba9 aeda 4f23 6d18 6c79 b795 fecd c666  {...O#m.ly.....f
0000050: 0d74 420c 4e58 704c 6f93 9529 fcd3 60f3  .tB.NXpLo..)..`.
0000060: 3776 2023 06dc 29bb 6dcb d816 985d a755  7v #..).m....].U
0000070: 2e79 8891 d065 de07 09ca 24a0 b470 1f58  .y...e....$..p.X
0000080: 365e a3fc 628e 718f 9fd8 426f 431f ce68  6^..b.q...BoC..h
0000090: 6d4b f8ee 68a2 e67f 8fc2 ca09 67ac 9acf  mK..h.......g...
00000a0: 8792 a46a 6ce9 d40c 97e3 da60 ffd6 0ba7  ...jl......`....
00000b0: 150c 1046 b37b eae5 c19e e751 f6bb ba15  ...F.{.....Q....
00000c0: 02b1 6e1e bb08 dac1 e418 d607 9615 ae74  ..n............t
00000d0: a9f9 451b c985 edec c5fa ed40 4fcc 7a42  ..E........@O.zB
00000e0: 91b9 906d 7f80 7da9 dcac b3ae af16 2a52  ...m..}.......*R
00000f0: 8b5c dfd8 c5c5 f40f c2cf 0bcc 43fb 7d3c  .\..........C.}<
0000100: 4b71 c3c9 33c7 18a4 a761 24de 473d 4e26  Kq..3....a$.G=N&
0000110: a62e 5fa2 1b6b e375 6a7c e09c d832 0e9c  .._..k.uj|...2..
0000120: 13ed db14 8e24 55d9 fe77 5344 9c14 7f4b  .....$U..wSD...K
0000130: d1cc 9e4b 2011 cf6c 7407 325a c6d2 6868  ...K ..lt.2Z..hh
0000140: f07a dc06 4ebe d45e 4a4a 3bd6 8717 4d43  .z..N..^JJ;...MC
0000150: da2e 6908 ee34 fe47 91d3 e6be 36c0 4439  ..i..4.G....6.D9
0000160: 765f 6ada 576a fe38 0098 da97 2c2d 2de5  v_j.Wj.8....,--.
0000170: ae                                       .

```

---

### Explanation

I've mangled the (updated) supplied score (more on that later) into a single string containing bytes with values from 0 to 24. The note lengths come first; then the note values, represented mod 25 and difference-encoded. The reason for the difference encoding is so that passages which are repeated in transposition will be reduced to the same sequence and can be compressed.

I then ran this through a string-to-GolfScript compression program which I've mentioned before (and which I improved in order to be competitive in this golf) to get the data file, which is decompressed by the first part of the program:

```
256base 69base[0:N]/(43,{\[1$)]/\2$=*}/\,){-}+%

```

It's a simple grammar expansion of a type which is familiar to anyone who's looked at many questions tagged .

I then split this string into pairs `[length note]` and iterate through the pairs. The non-printable characters come from a magic string which contains frequency parameters for the notes: I'm using GolfScript's implicit truncation mod 256 of integer arrays which are converted to strings to produce a triangle wave\*, so the base frequency is 22050/256 Hz. I wrote a program to find integer ratios which give a good tuning; the magic string contains numerators, and the denominator 17 is the same for all notes. The average tuning error is about 3.4 cents.

The note lengths are represented as is, and are much more plausible than the previous version of the score. As I suspected, the rounding has increased the redundancy in the string and shortened the compressed data file by 30 bytes, not to mention saving the lookup array. However, there are still some passages which I find suspicious:

```
72 13

```

or

```
71 9
69 2
71 2

```

give bars which are a sixth of a crochet longer than the rest of the bars in the score, and

```
85 9
85 4
85 24
85 23

```

or

```
83 18
88 7
85 24
85 23

```

are an integral number of bars, but with some dubious offsets.

The program could be slightly shorter. I have deliberately chosen to trade in shortness for execution time. With some speed improvements to the GolfScript interpreter which I've submitted to Darren Smith and which I believe he plans to publish at some point, the current version runs in less than 15 minutes on my computer. If I don't `puts` each note after generating it then it runs much slower.

* I hereby confess that my comment about everyone using square waves was wrong.
> 4 votes

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