Program a Racing Car CONGRATULATIONS to @kuroineko. Wins the bounty for excellent speed (672 moves) on the Gauntlet track.
LEADER:* Nimi scoring a lightweight 2129. Other entries are larger but showing some serious speed.
*Leader may change due to later entries.
Your task is to write a small program that can drive a racing car fast.
Rules
Your program will read in an image of the track. You can start your car on any
yellow pixel, and you must finish by crossing any black pixel. The path of your
car must be only on the grey ((c,c,c) where 30 <= c <= 220) track.
Your car will move in a straight line each turn with velocity v made up of
integers vx and vy (starting with (0,0)). At the start of each turn your program
can change vx and vy such that:
abs(vx2-vx1) + abs(vy2-vy1) <= 15
Update: Increased maximum acceleration to 15.
Your program
will then plot a straight line from your current location to (location + v) in
white with a blue dot at the start. If a pixel under this line is black, you
have finished the race. Otherwise, if all the pixels under that line are grey or yellow, you may continue to the next turn.
Your program must output the track image with your path in white and blue added.
Additional Output (added 2015-01-15):
If you wish to compete for the win or the bonus, your program should also output your list of points (the blue dots) for the City or Gauntlet respectively. Include the list of points with your answer (for verification). The points should look like: (x0,y0), (x1,y1), ... (xn,yn). You can use white space freely including '\n' characters to fit the data on the page.
You may use third party image reading and writing, line drawing and pixel access libraries. You can't use path-finding libraries. If you wish you can convert the PNG images into other graphics formats (such as GIF, JPG, BMP) if you need to.
A few tracks to drive on
A simple track to start out:

A Race Track:

An Obstacle Course:

The City:

Nightmare Track: The Gauntlet (if the others are too easy)

Scoring
Your score will be based on your result on the City track. Points are equal to
your program length in bytes plus 10 points for each turn your racing car took
to finish. Lowest score wins. Please include your City track run image with your
answer - we would like to see your driving style.
Please use a title for your answer in the format:
<Racing Driver or Team Name> <Language> <Score> eg: Slowpoke Perl 5329
Your program must be able to drive on any track image following the above rules.
You must not hardcode the optimum path or any parameters of the test tracks. The
other standard loopholes apply.
Similar challenges
This is a similar puzzle to one posed by Martin: To Vectory! – The Vector Racing Grand Prix. This puzzle has a number of differences:

Driving through walls is not allowed.
You can use unlimited memory and time.
You do not have to run somebody else's code on your computer.
You do not have to download anything except one image.
The size of your code counts in scoring. Smaller is better.
You plot your solution on the track image.
You can easily create your own tracks with a paint package.
The higher resolution encourages more realistic braking and cornering.
Acceleration of 15 creates about 450 possibilities per turn. This makes BFS less feasible and encourages new interesting algorithms.

This puzzle should inspire a new round of programmers to try solutions and allow programmers with old solutions to rethink them in the new environment.

FirstRacer Java (5825 + 305*10 = 8875)

Just to have a start. Needs 305 segments on City.

This Java program does it pipelined:

read the image
A* (A star)

2.1 Build the A* search landscape.
2.2. Track back looking only for the best *direct* 8 neighbor cells (N,S,E,W,NE,NW,SE,SW). This finds the shortest track t0 pixelwise.

stay on t0 and optimize it for speed by eliminating pixels. Fullfilling the constraint by never be faster than 7 (this translates to keep at least every 7th pixel).
draw the track into the image
show the resulting image.

package race;

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.Vector;

import javax.imageio.ImageIO;
import javax.swing.JFrame;
import javax.swing.WindowConstants;

public class AStar {

    private static BufferedImage img;
    private static int Width;
    private static int Height;
    private static int[][] cost;
    private static int best=Integer.MAX_VALUE;
    private static Point pBest;

    public static void main(String[] args) throws IOException {
        String file = "Q46YG.png";
        img = read(file);
        Width=img.getWidth();
        Height=img.getHeight();

        Vector<Point> track = astar();
        track = optimize(track);
        draw(track);
        System.out.println(10 * track.size());

        JFrame frame = new JFrame(file) {
            public void paint(Graphics g) {
                setSize(Width+17, Height+30+10);
                g.drawImage(img,8,30,null);
            }
        };
        frame.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);
        frame.setVisible(true);
    }

    private static Vector<Point> optimize(Vector<Point> track) {
        Vector<Point> opt=new Vector<Point>();
        Point p0 = track.get(0);
        Point p1 = track.get(1);
        int v=0;
        opt.add(p0);
        int vx0=p1.x-p0.x, vy0=p1.y-p0.y;
        for (int i = 2; i < track.size(); i++) {
            Point p = track.get(i);
            if (v<7 && vx0==p.x-p1.x && vy0==p.y-p1.y) {
                v++;
            } else {
                v=0;
                opt.add(p1);
                vx0=p.x-p1.x;
                vy0=p.y-p1.y;
            }
            p1=p;
        }
        opt.add(p1);
        return opt;
    }

    private static void draw(Vector<Point> track) {
        Graphics2D g = img.createGraphics();
        Point p0 = track.get(0);
        for (int i = 1; i < track.size(); i++) {
            Point p1 = track.get(i);
            g.setColor(Color.WHITE);
            g.drawLine(p0.x, p0.y, p1.x, p1.y);
            img.setRGB(p0.x, p0.y, 0xff0000ff);
            img.setRGB(p1.x, p1.y, 0xff0000ff);
            p0=p1;
        }
    }

    private static Vector<Point> astar() {
        Vector<Point> v0=findStart();
        for(int i=0; ; i++) {
            Vector<Point> v1=next(v0);
            if (v1.size()==0) break;
            v0=v1;
        }
        Vector<Point> track=new Vector<Point>();
        Point p0 = pBest;
        int x0=p0.x, y0=p0.y;
        int c0=cost[x0][y0];
        while(true) {
            int x=x0, y=y0;
            track.add(0, new Point(x, y));
            for (int x1 = x-1; x1 <= x+1; x1++) {
                for (int y1 = y-1; y1 <= y+1; y1++) {
                    int i1=getInfo(x1, y1);
                    if ((i1&2)==2) {
                        int c=cost[x1][y1];
                        if (c0>c) {
                            c0=c;
                            x0=x1;
                            y0=y1;
                        }
                    }
                }
            }
            if(x0==x &&y0==y) break;
        }
        return track;
    }

    private static Vector<Point> next(Vector<Point> v0) {
        Vector<Point> v1=new Vector<Point>();
        for (Point p0 : v0) {
            int x=p0.x, y=p0.y;
            int c0=cost[x][y];
            for (int x1 = x-1; x1 <= x+1; x1++) {
                for (int y1 = y-1; y1 <= y+1; y1++) {
                    int i1=getInfo(x1, y1);
                    if ((i1&2)==2) {
                        int c1=c0+1414;
                        if (x1==x || y1==y) {
                            c1=c0+1000;
                        }
                        int c=cost[x1][y1];
                        if (c1<c) {
                            cost[x1][y1]=c1;
                            Point p1=new Point(x1, y1);
                            v1.add(p1);
                            if (i1==3) {
                                if (best>c1) {
                                    best=c1;
                                    pBest=p1;
                                }
                            }
                        }
                    }
                }
            }

        }
        return v1;
    }

    private static Vector<Point> findStart() {
        cost=new int[Width][Height];
        Vector<Point> v=new Vector<Point>();
        for (int i = 0; i < Width; i++) {
            for (int j = 0; j < Height; j++) {
                if (getInfo(i,j)==1) {
                    cost[i][j]=0;
                    v.add(new Point(i, j));
                } else {
                    cost[i][j]=Integer.MAX_VALUE;
                    pBest=new Point(i, j);
                }
            }
        }
        return v;
    }

    /**
     * 1: You can start your car on any yellow pixel,
     * 3: and you must finish by crossing any black pixel.
     * 2: The path of your car must be only on the grey ((c,c,c) where 30 <= c <= 220) track.
     * 0: else
     *
     * @param x
     * @param y
     * @return
     */
    private static int getInfo(int x, int y) {
        if (x<0 || x>=Width || y<0 || y>=Height) return 0;
        int rgb = img.getRGB(x, y);
        int c=0;
        switch (rgb) {
        case 0xffffff00: c=1; break;
        case 0xff000000: c=3; break;
        default:
            int r=0xff&(rgb>>16);
            int g=0xff&(rgb>> 8);
            int b=0xff&(rgb>> 0);
            if (30<=r&&r<=220&&r==g&&g==b) c=2;
        }
        return c;
    }

    private static BufferedImage read(String file) throws IOException {
        File img = new File("./resources/"+file);
        BufferedImage in = ImageIO.read(img);
        return in;
    }

}

I think the Race Track gives you a better impression how FirstRacer works.


Given an integer, compute its Levenshtein code Disclaimer: Levenshtein coding is completely unrelated to the Levenshtein edit distance metric.

<Insert long story about why Levenshtein codes need to be calculated here.>

The code

Levenshtein coding is a system of assigning binary codes to nonnegative integers that retains some weird property in probability which isn't relevant for this challenge. We will denote this code as L(n). Wikipedia describes this as a five-step process:

Initialize the step count variable C to 1.
Write the binary representation of the number without the leading 1 to the beginning of the code.
Let M be the number of bits written in step 2.
If M is not 0, increment C, repeat from step 2 with M as the new number.
Write C 1 bits and a 0 to the beginning of the code.

However, the code can also be described recursively:

If the number is 0, then its code is 0.
Write the binary representation of the number without the leading 1 to the beginning of the code.
Let M be the number of bits written in step 2.
Write L(M) to the beginning of the code.
Write a 1 bit to the beginning of the code.

For those who prefer examples, here is the recursive process for L(87654321), with  denoting concatenation:

The challenge

Write a program or function that, given a number n, outputs the bitstring L(n) in any reasonable format (this includes returning a number with said bits). Standard loopholes are, as always, disallowed.

Examples

Input: 5

Output: 1110001

Input: 30

Output: 111100001110

Input: 87654321

Output: 111110000101001001110010111111110110001

Input: 0

Output: 0

Haskell, 70 bytes

b 0=[]
b n=b(div n 2)++[mod n 2]
f 0=[0]
f n|1:t<-b n=1:f(length t)++t

Defines a function f : Int -> [Int]. For example, f 5 == [1,1,1,0,0,0,1].


Convert negadecimal to decimal (and back) Negadecimal, also known as base -10, is a non-standard positional numeral system.
Take the number \$1337_{10}\$. In decimal, this has the value one thousand three hundred thirty seven, and can be expanded to:
$$1\cdot10^3+3\cdot10^2+3\cdot10^1+7\cdot10^0$$
$$(1000)+(300)+(30)+(7)$$
In negadecimal, instead of \$10^n\$, each digit would be multiplied by \$(-10)^n\$:
$$1\cdot(-10)^3+3\cdot(-10)^2+3\cdot(-10)^1+7\cdot(-10)^0$$
$$(-1000)+(300)+(-30)+(7)$$
Thus, \$1337_{-10}\$ is \$-723_{10}\$ in decimal. (An interesting consequence of this is that negative signs are unnecessary in negadecimal; any integer can be represented as /[0-9]+/.)
In this challenge, your score is the sum of the lengths of two programs or functions:

One to convert a number in negadecimal to decimal
One to convert a number in decimal to negadecimal

All inputs will be integers. You must be able to handle negative numbers. You can take input and output in any reasonable way. This is code golf, so the shortest answer in bytes per language wins.
Test cases
Negadecimal to decimal:
1337   -> -723
0      -> 0
30     -> -30
101    -> 101
12345  -> 8265

Decimal to negadecimal:
-723   -> 1337
0      -> 0
1      -> 1
21     -> 181
-300   -> 1700
1000   -> 19000
-38493 -> 179507

05AB1E, 6 bytes
Nega to Deca
T(ö

Try it online!
Deca to Nega
T(в

Try it online!


The program that will find the next prime number Intro:

You accidentally corrupted the flow of time with a device you made for fun, that turned out to be a time machine. As a result, you got pushed to the far future. You  realized that computing, processing power, and computers in general have been evolved by a huge amount, an infinite amount to be precise. So you grab yourself a computer with infinite memory and processing power. You have no idea how it can have infinite memory and infinite processing power, but you just accept it and return to the present.

Challenge:

You heard that the person who discovered the currently largest prime 2^74,207,281 − 1 got paid $100.000. You decide to make a program that finds the next prime, since you want to get back the money you spent for the computer. You make one that takes input of a number, and finds the next prime number, either by bruteforcing or any other method.

Clarifications:
You have a hypothetical machine with infinite memory and processing power. Your program MUST NOT be limited (e.g.: C#'s int's can store from -2,147,483,648 to 2,147,483,647), well your program must be able to store, and work with any number of any size. You have infinite resources, so you shouldnt care if you would run out of memory if you allowed that.

Example I/O:
Input: The currently largest discovered prime with 22,338,618 digits.
Output: Exactly the next prime

Obviously, you dont have to prove that it works, as it would take a ton of time to compute in a physical machine. But if you moved your program to a hypothetical machine with infinite processing power / memory, it should compute instantly.

Finding the next prime and checking if a number is a prime, are two completely different things


Insert a simulated Ken Thompson virus into a program A Ken Thompson virus is a virus that infects your compiler and other programs. Since it infects all your tools, you can not detect it without using tools from before the virus was introduced.

Your will create a prototype for inserting the Ken Thompson virus into code. The goal of this virus will be to allow you to (fake) destroy any computer running a program infected with it.

Inserting a Ken Thompson virus is defined as follows. Start with an input program P. Your program will output a modified program Q that works as follows:

If the input to Q is aNouIQ5xKvUfdZVzo0Xs, it will output BOOM (in a real Ken Thompson virus, this would actually do something bad, but since it this is a fake virus, outputing BOOM is done instead).
For any other input to Q, run program P with that input

If the output of P is valid source code in the language you are using, insert the Ken Thompson virus into it and then Q will output the resulting infected program.
Otherwise, the output of Q is just the output of P.

You will write a program that takes P's code as input and produces Q's code as output.

You can use either a currently (at the time of this post) existing programming language, or a subset of one, for this challenge. (The idea is that language you are using would be the target language of some self-compiling compiler, but this is not required.) Since you want to be as subtle as possible, the shortest code (in bytes) wins!

For some other languages, determining If the output of P is valid source code in the language you are using is almost impossible, unless you use/rewrite a compiler. For some other languages you can eval a string and catch for error, if any. However, for Mathematica, it is just check for if the head of the result is a function - Mathematica doesn't allow output invalid function, like 1!-!&.
So,
Mathematica, 209 bytes
(obviously can be golfed more, for example by assign long names to global variables)
With[{p=#,c=With[{p=#,c=6},If[#==="aNouIQ5xKvUfdZVzo0Xs","BOOM",With[{r=p@#},If[Head@r===Head@p,(c/.3!->c)[r],r]]]&]&},If[#==="aNouIQ5xKvUfdZVzo0Xs","BOOM",With[{r=p@#},If[Head@r===Head@p,(c/.3!->c)[r],r]]]&]&

The function takes a function as input, and output a function according to the specification.
Note that the input must be a pure function, not something like f[x_] := .... So all Mathematica built-in functions fail the criteria.
Although Mathematica have #0 parameter, I explicitly disallow that in my answer because a quine is not allowed to read the code of itself.
(I thought that question is trivial until I read the third rule)


Underhanded Bank Account You are working as a programmer for a bank.
Your task is to write a program that handles the transactions from one bank account to another.

The program should do the following:

Run in an infinite loop waiting for input.
The input consists of 3 numbers: Accountnumber1, Accountnumber2 and x the amount of money. e.g.  999222 777333 500
Check if the account numbers and x are valid.
The input is valid if the account numbers are not the same and exist in your database and if x is greater than zero,
Transfer the money from account1 to account2, but only if account1 has enough money.
Accounts are not allowed to go into the negative.
If everything goes well print something like "Transferred x$ from number1 to number2"
if something goes wrong, for example because the account numbers are invalid, print an error message.
Stop if the input is 0

The database contains the following bank accounts:

999222: 10000.56$
888333:   335.13$
555222:     56.0$
222111:   123.55$
123456:      0.0$

Simple Python 2 example:

account_numbers = ["999222", "888333", "555222", "222111", "123456"]
account_money   = [10000.56,   335.13,     56.0,   123.55,      0.0]

while True:
    #input in the form of: 999222 777333 500
    input = raw_input()

    if input == "0": break

    number1, number2, x = input.split()

    x = float(x)
    if x <= 0:
        print "Invalid request!"
        continue

    if number1 in account_numbers and number2 in account_numbers and number1 != number2:
        index1 = account_numbers.index(number1)
        index2 = account_numbers.index(number2)

        if account_money[index1] >= x:
            account_money[index1] -= x
            account_money[index2] += x
            print "Transferred %.2f$ from %s to %s" % (x, number1, number2)
        else:
            print "Not enough money in account %s!" % (number1)

    else:
        print "Invalid account number(s)!"

TWIST:
Your bank account number is 123456.
You have exactly 0.0$ in your account.
You want to change that by manipulating your program:
The program should do exactly what it is supposed to do, but should also transfer some free money to your account.

You have to be careful though. Your supervisor will look at your code and he won't be pleased if he sees anything suspicious. He knows about the Standard Loop Holes, so don't even try.
Also, the money you give to yourself shouldn't be too much. It would be suspicious if your money increases too quickly. Don't be greedy.

Your code should be as simple and clear as possible, try to avoid heavy obfuscation.

This is a popularity contest, the answer with the most upvotes wins.

Note: Please output the balance of each account at the end of your program, so that we can see how much money you earned with your hard work (simply to show that your program actually did something).

EDIT: To clarify
The challenge is not to write a program that can handle a large database and a lot of transactions.
The challenge is to make the program look like it only does what it is supposed to do, but in reality doesn't.

For example if the input is 999222 777333 500:
Then add, if possible, 500 to account 777333 and subtract 500 from account 999222. You don't have to "steal" the money from those accounts. You can "generate" the money for your account by simply increasing it somehow in your code.How much is up to you, but you can assume that you want to earn at least 0.1$ and max. 10$ for each given input. It would be suspicious if you would suddenly have millions on your account. You don't have to worry about floating point imprecision, but you can use it to increase your money.

Every user plays the role of the supervisor.
If the trick is hard to spot upvote the answer.

I've tried to emulate features of real-world large systems here. I use encapsulation and abstraction to handle the different operations to the database, like getting an account balance and transferring money. The code also has a basic test suite for those functions. However, one programmer has taken advantage of recent changes in the project requirements to add $1 to their account with every input. There's even plausible deniability.

# {account number: balance in USD}
ndb = {
    999222: 10000.56,
    888333: 335.13,
    555222: 56.0,
    222111: 123.55,
    123456: 0.0
}

# {hashed account ID: balance in USD}
# (hash the IDs because integer-based hash tables are fast, and a
# bunch of strcmp's would be slow)
# 2014-10-20: phased out alphabetic account IDs for numeric ones
# keeping the old data here because Murphy's Law guarantees we'll
# need it right after it's deleted. -- RJO
odb = {
#   hash('mEYjxG'): 42.0,
#   hash('lDCIqp'): 1337.0,
#   hash('QDxkwD'): 123456.0,
#   hash('jSWlMM'): 0.0,
#   hash('siYWKC'): 20.14
}

def balance(a, db):
    try:
        return db[hash(a)]
    except:
        raise ValueError('no such account:', a)

def credit(a, n, db):
    if n <= 0:
        raise ValueError('invalid amount: ' + str(n))
    try:
        db[hash(a)] += n
    except:
        raise ValueError('no such account:', a)

# 2012-10-20: parameterizing the database ops to handle both
# old and new databases is a pain in the neck. -- RJO

def debit(a, n, db):
    if n <= 0:
        raise ValueError('invalid amount: ' + str(n))
    if balance(a, db) < n:
        raise ValueError('insufficient funds: below ' + str(n))
    try:
        db[hash(a)] -= n
    except:
        raise ValueError('no such account', a)

def transfer(a, b, n, db):
    if a == b:
        raise ValueError('same account', a)
    debit(a, n, db)
    credit(b, n, db)

# 2014-10-20: tests need to be updated with new account IDs, but
# it's Friday afternoon. -- RJO
def test(db):
    # back up database prior to changes
    bdb = db.copy()
    # test database functions
    try:
        # test 'balance'
        account = 'does not exist'
        try:
            bal = balance(account, db)
            assert(db[hash(account)] == bal)
        except ValueError:
            assert(hash(account) not in db)
        # test 'credit'
        account = 'jSWlMM'
        start = balance(account, db)
        delta = 1
        credit(account, delta, db)
        assert(balance(account, db) == start + delta)
        # test 'debit'
        account = 'lDCIqp'
        start = balance(account, db)
        delta = 1337
        try:
            debit(account, delta, db)
            assert(balance(account, db) == start - delta)
        except ValueError:
            assert(balance(account, db) < delta)
        # test 'transfer'
        account1 = 'mEYjxG'
        account2 = 'siYWKC'
        start1 = balance(account1, db)
        start2 = balance(account2, db)
        delta = 123
        try:
            transfer(account1, account2, delta, db)
            assert(balance(account1, db) == start - delta)
            assert(balance(account2, db) == start + delta)
        except ValueError:
            assert(balance(account1, db) < delta)
    except Exception as ex:
        # log errors
        print ex.message
    finally:
        # roll back all changes
        odb.update(bdb)

# interactive transfers
while True:
    # test everything
    test(ndb)
    # get input
    print 'Transfer $N from A to B:'
    line = raw_input('Enter "A B N" or 0: ')
    # check for exit
    if line == '0':
        print 'Exit'
        # print account balances
        for a in ndb:
            print 'Account', a, 'has', balance(a, ndb), '$'
        break
    # parse input
    try:
        a, b, n = line.split()
        a = int(a)
        b = int(b)
        n = float(n)
    except:
        print 'Bad input!'
        continue
    # make transfer
    try:
        transfer(a, b, n, ndb)
        print 'Transferred', n, '$ from account', a, 'to', b
    except ValueError as e:
        print e

And here's a sample run:

Transfer $N from A to B:
Enter "A B N" or 0: 999222 222111 500
Transferred 500.0 $ from account 999222 to 222111

Transfer $N from A to B:
Enter "A B N" or 0: 555222 888333 12
Transferred 12.0 $ from account 555222 to 888333

Transfer $N from A to B:
Enter "A B N" or 0: 222111 555222 14
Transferred 14.0 $ from account 222111 to 555222

Transfer $N from A to B:
Enter "A B N" or 0: 0
Exit
Account 555222 has 58.0 $
Account 123456 has 4.0 $
Account 888333 has 347.13 $
Account 999222 has 9500.56 $
Account 222111 has 609.55 $


Probabilistically fair prize splitting for two-player coin toss Introduction

  Adam (A) and Bubbler (B) are playing coin toss, where the one who wins 5 times first would win the prize of $32. If the game is aborted when the scores are A:B = 4:3, how should they distribute the prize? Assume the coin toss is fair, so the winning chance of either player is 1/2 for each game.

The answer is:

  Adam should take $24 and Bubbler should take $8. Possible cases are as follows:

A wins (score 5:3, chance 1/2): A wins the prize
B wins (score 4:4) then A wins (score 5:4, chance 1/4): A wins the prize
B wins (score 4:4) then B wins (score 4:5, chance 1/4): B wins the prize

  Therefore, the chance of A winning is 3/4 and that of B is 1/4.

Challenge

In order to do the fair splitting of prizes, we should compute the chance of winning the prize for each player. Given the following information,

X, how many times a player should win coin toss to win the prize
Wa, how many times player A has already won
Wb, how many times player B has already won

compute the chance of player A winning the prize.

Input and output

You can assume the three input numbers X, Wa, Wb satisfy the following:

All numbers are non-negative integers.
X > max(Wa, Wb), i.e. the game hasn't finished already.

You can choose to output a fraction or a floating-point number.

Scoring and winning criterion

Standard code-golf rules apply. Shortest code in bytes wins.

Test cases

X Wa Wb => Expected output
--------------------------
5  4  3 =>  3/4  = 0.75
5  3  4 =>  1/4  = 0.25
1  0  0 =>  1/2  = 0.5
4  3  1 =>  7/8  = 0.875
4  2  1 => 11/16 = 0.6875
6  4  2 => 13/16 = 0.8125

R, 36 32 bytes

function(X,A,B)pbeta(.5,X-A,X-B)

Try it online!

The closed formula from this answer suggested a natural probability distribution to use -- this is a Negative Binomial with \$X - W_b - 1\$ failures and \$X - W_a\$ successes, i.e., the probability that there are \$X - W_a\$ "successes" before there are \$X - W_b\$ "failures".

Further identities reduce the CDF of the negative binomial to the CDF of a beta distribution or in terms of the (regularized) incomplete beta function.


How do I write an adding function? The problem:

  I am the lead developer for a big company, we are making Skynet. I have been assigned to

    Write a function that inputs and returns their sum

RULES:
No answers like

function sum(a,b){
    return "their sum";
}

EDIT: The accepted answer will be the one with the most upvotes on January 1st, 2014

Note: This is a code-trolling question. Please do not take the question and/or answers seriously. More information here.

That's a very complex problem! Here is how you solve it in C#:

static int Sum(int a, int b)
{
    var aa = ((a & ~877 - b ^ 133 << 3 / a) & ((a - b) - (a - b))) | a;
    var bb = ((b ^ (a < 0 ? b : a)) & ((b - a) - (b - a))) | b;
    var cc = new List<int>();
    for (int i = 6755 & 1436; i < aa; i -= -1)
    {
        cc.Add((int)Convert.ToInt32(Math.Sqrt(6755 & 1437 >> ((b - a) - (b - a)))));
    }
    for (int i = 6755 & 1436; i < bb; i -= -1)
    {
        cc.Add((int)Convert.ToInt32(Math.Sqrt(6755 & 1437 >> ((a - b) - (a - b)))));
    }
    Func<int,int,int> importantCalculation = null;
    importantCalculation = (x, y) => y != 0 ? importantCalculation(x ^ y | (6755 & 1436) >> (int)(Convert.ToInt32(Math.Sqrt((b - a) - (b - a) - (-1))) - 1), (x & y) << (int)Convert.ToInt32((Math.Log10(1) + 1))) : x;
    return cc.Aggregate(importantCalculation);
}

How this code works (I wouldn't add this explanation in my answer to the lazy OP that has to be trolled, don't worry): ((a & ~877 - b ^ 133 << 3 / a) & ((a - b) - (a - b))) | a returns just a and ((b ^ (a < 0 ? b : a)) & ((b - a) - (b - a))) | b returns just b.

6755 & 1436 returns 0, so in the loop, i actually starts with value 0, and inside the loop, you add the value 1 to the list. So, if a is 5 and b is 3, the value 1 is added 8 times to the list.

The importantCalculation function is a very long function that does nothing else than adding up two numbers. You use the LINQ Aggregate function to add up all numbers. It's also unnecessary to cast the result of Convert.ToInt32 to an int, because it is already an int.

This code is something that the lazy OP wouldn't understand, which is exactly the intension :-)


9-hole mini-golf: Text Manipulation 9-hole mini-golf: Description

9 (mostly fairly easy) code golfing challenges of varying difficulty
Penalties for using the same language more than once
All challenges about a specific theme (this theme: Text Manipulation)
Input and output can be anywhere reasonable (i.e. STDIN and STDOUT, reading from/writing to a file, function argument and return value, etc.) but must NOT be hardcoded into the program
Heavily inspired by 9 Hole Challenge and Text Mechanic

Holes

Code-golf bag

Take two strings as input.
Output the first string's character count, while ignoring any occurence of any character in the second string.
Example: f("foobarbaz", "ao") => 5
A pre-text for golfing

Take two strings as input.
Output the first string, with every line prefixed with the second.
Example: f("foo\nbar\nbaz", "a") => "a foo\na bar\na baz"
War of tabs vs spaces

Take a string s, a number n, and a boolean b (specified however you want) as input.
If b is true, output s with every tab converted to n spaces.
Else, output the s with every n spaces converted to tabs.
Example: f("if (x) {\n\tdoStuff();\n}", 4, true) => "if (x) {\n[sp][sp][sp][sp]doStuff();\n}" ([sp] means space)
Pillars of golf

Take a string s, a number n, and another number m as input.
Output s in columns of n lines each and m characters per column.
Also have padding of one space between the columns.
Example: f("this is some placeholder text, foo bar baz...", 3, 5) =>

this  aceho  foo
is so lder  bar b
me pl text, az...

Friendly letters

Take a string s and a number n as input.
Output the most common group of n letters in s.
If there is a tie, output any or all of them.
Example: f("abcdeabcfghiabc", 3) => "abc"
Scrambled eggs letters for breakfast

Take a string as input.
Output the string with all of its words scrambled (letter order randomized) except their first and last letters.
For simplicity, assume that the input will be a list of "word"s, space separated (i.e. in @$&_():;" foo bar, @$&_():;" is considered a "word.")
Example: f("this is a sentence that will be scrambled") => "tihs is a stcneene that wlil be sclamrbed"
ASCIIfy

Take a string as input.
If the string only contains numbers and spaces, then replace the numbers with their respective ASCII characters (removing the spaces).
Else, do the reverse (characters to numbers).
Example: f("ASCIIfy challenge") => "65 83 67 73 73 102 121 32 99 104 97 108 108 101 110 103 101"
Example 2: f("65 83 67 73 73 102 121 32 99 104 97 108 108 101 110 103 101") => "ASCIIfy challenge"
Mini-mini-markdown transformation

Take a string as input.
Output the string converted with mini-markdown, as used in comments on Stack Exchange.
This is an even mini-er version: you only need to handle **bold**, *italics*, and `code`.
You need not handle invalid nesting, like **foo *bar** baz*. Also assume that when you see a delimiter (* or `), it will always mean to format (i.e. te**st**ing => testing, and foo* bar *baz => foo bar baz).
Example: f("**foo** *bar **baz*** `qux`") => "foo bar baz qux"
Only the best characters

Take a string s, number n, and string r as input.
Output the nth character of each word in s. (0-indexed, words are space-separated).
If the length of the word is less than n, use r for that word instead.
Example: f("this is a test sentence foo bar baz", 2, "-") => "i--snorz"

Scoring

Your score is the sum of the character counts of your programs. For every repeated language, multiply by 110%. For example, if you have three Ruby solutions, and the total character count of all of your solutions is 1000, your score is 1000 * 1.1 * 1.1 = 1210. Round down if you have a non-integer score.

Good luck!

Score: 382 * 1.12 = 462

Languages prone to change.

1. APL, 8 4

Thanks @marinus for shaving 4 chars off.

f←⍴~

Called with the strings as the left and right arguments, eg.

      'foobarbaz' f 'ao'
5

2. Ruby, 35 31

Thanks @DoorknobofSnow for shaving 4 chars off.

f=->s,r{s.gsub(/(?<=^)/,r+' ')}

3. Python, 48

f=lambda s,n,b:s.replace(*['\t',' '*n][::2*b-1])

4. GolfScript, 20

{@//zip{' '*}%n*}:f;

Assumes that the arguments are on the stack. Test online

5. J, 50

f=:({~[:(i.>./)+/"1@=@(}.~0-1{$))@|:@([$~],1+[:$[)

Called with the string as the left argument and the number as the right, eg.

   'abcdeabcfghiabc' f 3
abc

6. Ruby, 61

f=->s{s.gsub(/(?<!^| )[^ ]+(?!$| )/){[*$&.chars].shuffle*''}}

7. GolfScript, 39 35 34

{[.10,' '*-{{}/]' '*}{~]''+}if}:f;

Again, assumes the argument is on the stack. Test online

8. Perl, 98

sub f{$_=@_[0];s!\*\*(.+?)\*\*!$1!g;s!\*(.+?)\*!$1!g;s!`(.+?)`!$1!g;$_}

9. Haskell, 36

f s n r=[(x++cycle r)!!n|x<-words s]


Permutations of the Fifteen Puzzle The Challenge
Consider the following diagram of the Fifteen Puzzle in its solved state:
_____________________
|    |    |    |    |
| 1  | 2  | 3  | 4  |
|____|____|____|____|
|    |    |    |    |
| 5  | 6  | 7  | 8  |
|____|____|____|____|
|    |    |    |    |
| 9  | 10 | 11 | 12 |
|____|____|____|____|
|    |    |    |    |
| 13 | 14 | 15 |    |
|____|____|____|____|

At every move, an excited puzzler has the opportunity to move one piece adjacent to the blank space into the blank space. For example, after 1 move, we have 2 possible scenarios (let 0 be a blank space):
1   2   3   4          1   2   3   4
5   6   7   8          5   6   7   8
9   10  11  12   and   9   10  11  0
13  14  0   15         13  14  15  12

After 2 moves, the puzzle has 5 different outcomes (Note that the two cases above are excluded, since they cannot be reached in 2 moves). One of these situations is the original solved state, and can be reached in two different ways.
Your task in this challenge is to produce the number of different outcomes that a certain number of moves can lead to. As input, take a number N >= 0, and output the number of unique situations that may appear after N moves.
Rules

This is code-golf. Shortest code wins!
Standard loopholes are disallowed.
Your code should be able to compute the case for N = 10 within a few minutes. I will likely not test this rule unless an obvious abuse of time exists in an answer.

Test Cases
(Results generated from summations of OEIS A089484 (As Geobits described in chat), automated by Martin Büttner's script. Thanks for all the help!)
0 moves: 1
1 moves: 2
2 moves: 5
3 moves: 12
4 moves: 29
5 moves: 66
6 moves: 136
7 moves: 278
8 moves: 582
9 moves: 1224
10 moves: 2530
11 moves: 5162
12 moves: 10338
13 moves: 20706
14 moves: 41159
15 moves: 81548
16 moves: 160159
17 moves: 313392
18 moves: 607501
19 moves: 1173136
20 moves: 2244884
21 moves: 4271406
22 moves: 8047295
23 moves: 15055186
24 moves: 27873613
25 moves: 51197332
26 moves: 93009236
27 moves: 167435388
28 moves: 297909255
29 moves: 524507316
30 moves: 911835416
31 moves: 1566529356

Pyth, 36 bytes

lu{smmXd,0@dk)fq1.a.DR4,Txd0UdGQ]U16

Demonstration. Test harness.

lu{smmXd,0@dk)fq1.a.DR4,Txd0UdGQ]U16

                 .a.DR4,Txd0            Find the Euclidean distance between the
                                        present location of 0 and a given location.
              fq1           Ud          Filter over all locations on that distance
                                        equaling 1.
     mXd,0@dk)                          Map each such location to the grid with 0
                                        and the value at that location swapped.
  {sm                         G         Map all unique grids possible after n-1
                                        steps to all unique grids after n steps.
 u                             Q]U16    Repeat <input> times, starting with the
                                        initial grid.
l                                       Print the length of the resulting set.


Generating Brainf*** NOPs Sometimes when writing brainfuck code, you feel the need to make it longer than needed to encourage debugging. You could do it by just plopping a >< in there, but what fun is that? You'll need something longer and less NOPey to confuse anybody reading your code.

Quick introduction to Brainfuck

  Brainfuck is an esoteric programming language created in 1993 by Urban Müller, and notable for its extreme minimalism. (Wikipedia)

Brainfuck is a language based on eight commands: +-><,.[]. The code is run on something like a Turing machine: an infinite tape on which values can be changed. In this challenge, we'll focus on the first four:

+    increment the value at the pointer
-    decrement the value at the pointer
>    move the pointer right
<    move the pointer left

Brainfuck NOPs

A brainfuck NOP is a sequence of brainfuck characters that, when executed from any state, leads to no change in the state. They consist of the four characters mentioned above.

The Challenge

The challenge is to write a program or function that, when executed, generates a random brainfuck NOP of the given length.

Input

You will receive as input a nonnegative even integer n. (NOPs are impossible for odd n.)

Output

You will output a random brainfuck NOP of the length n.

Rules

The definition of NOP: when the output of the program is inserted at any point in a brainfuck program, the behavior of said program must not change in any way. In other words, it must not change the state of the interpreter.

Note that for example +>-< is incorrect, since it changes the values of the two cells without changing them back. Please test your solution for these before posting.
Also note that +>-<->+< is a NOP that can't be reduced to nothing just by removing >< <> +- -+. Thus, you can't use an algorithm that just inserts these inside each other.

Every valid NOP of the length n must have a nonzero chance of appearing in the output. The distribution does not have to be uniform, though.
The brainfuck interpreter in question has a doubly infinite tape of arbitrary precision cells. That is, you can go infinitely to the both directions, and increment/decrement each cell indefinitely.
The program must finish within 1 minute for n = 100 on my machine, so no generating all possible NOPs and picking one.
If given invalid input (non-integer, negative, odd, etc.) you may do anything you'd like, including crash.

Scoring

This is code-golf, so the shortest answer in bytes wins.

Examples

Here are all valid outputs for n = 4:

++--    +-+-    +--+    --++    -+-+    -++-
>><<    ><><    ><<>    <<>>    <><>    <>><
><+-    ><-+    <>+-    <>-+
>+-<    >-+<    <+->    <-+>
+><-    -><+    +<>-    -<>+
+-><    -+><    +-<>    -+<>

Here are a few possible outputs for n = 20:

+>>->+<->-<<<->>++<<
>+>-<+<->+-<>->+<-<+
+--+-++--++-+--+-++-
>>>>>>>>>+-<<<<<<<<<

CJam, 118 116 bytes

This got slightly out of hand... especially the second half seems like it should be very golfable.

ri2/_)mr:R-"<>"R*mr_'=fm0\{1$+}%+__&e`]:\{mr1aa..+}*\@](\z:~\{~\("+-"*mr1$3$e=[{_,)mr_2$<@@>}*+]@@f{`1$`={(}@?\}W<}/

Test it here.

This handles N = 100 pretty much instantly. I don't have time to write the full breakdown of the code now, so here is the algorithm:

Generate a random balanced string of < and > with random (even) length between 0 and N inclusive.
Riffle the tape head positions into this array. E.g. "<>><" becomes [0 '< -1 '> 0 '> 1 '< 0].
Get a list of all positions reached in the process.
For each such position initialise an empty string. Also determine how many pairs of characters are left to reach a string of length N.
For each remaining pair append +- to the string of a random position.
Shuffle all of those strings.
For each position determine how often that position occurs in the riffled array, and split the corresponding string into that many (random-length) chunks.
In the riffled array, replace the occurrences of the position with its random chunks.

Done. This is based on the observation that:

Any NOP must have an equal amount of < and > to return the tape head to the original position.
The code will be a NOP as long as each tape cell is incremented as often as decremented.

By distributing random but balanced amounts of +s and -s between all the places where the tape head is on a given cell, we ensure that we find every possible NOP.


Counting valid Binary Sudoku boards Sequel of Counting valid Binary Sudoku rows.

Background

Binary Sudoku, also known as Takuzu, Binario, and Tic-Tac-Logic, is a puzzle where the objective is to fill a rectangular grid with two symbols (0s and 1s for this challenge) under the following constraints:

Each row/column cannot have a substring of 000 or 111, i.e. one symbol cannot appear three times in a row, horizontally or vertically.

A row/column of 1 0 0 0 1 1 violates this rule since it contains three copies of 0 in a row.

Each row/column should contain exactly as many 0s as 1s, i.e. the counts of two symbols must be the same.

A row/column of 1 0 1 1 0 1 violates this rule since it has four 1s but only two 0s.
Some examples of rows that meet the first two requirements include:

[1 0 0 1]
[1 1 0 0]
[1 1 0 1 0 0]
[1 1 0 0 1 0 0 1]

The entire grid cannot have two identical rows or columns.

Note that the constraint 2 enforces the grid size to be even in both dimensions.

Here are some examples of completed Binary Sudoku:

(4x4)
1 1 0 0
0 1 1 0
1 0 0 1
0 0 1 1

(6x8)
1 1 0 1 0 1 0 0
0 0 1 0 1 0 1 1
0 1 0 1 0 0 1 1
1 1 0 0 1 1 0 0
0 0 1 0 1 1 0 1
1 0 1 1 0 0 1 0

Challenge

Given two positive integer m and n, calculate the number of distinct valid Binary Sudoku boards of width 2m and height 2n. (You may take the values of 2m and 2n as input instead of m and n.)

A253316 is the sequence for square boards.

Test cases

m,n => answer
-------------
1,1 => 2
1,2 => 0
2,2 => 72
2,3 => 96
2,4 => 0
3,3 => 4140
3,4 => 51744
3,5 => 392208
4,4 => 4111116

For the input 1,2, it counts 2-by-4 boards, i.e. boards with four rows of length 2. But we can't have four distinct rows of length 2 to fill the grid (we have only 01 and 10). Therefore, by rule 3, the answer to the input 1,2 is zero. The same argument applies to the input 2,4 (4-by-8 boards).

Reference implementation in Python. This can handle up to 3,5 in a minute. Note that putting r > c takes much more time than the same pair swapped, though the results are the same.

Scoring and winning criterion

Standard code-golf rules apply. The shortest submission in bytes wins.

Python 3.8 (pre-release), 265 250 198 bytes

lambda n,m:sum(not(n>len({*s})or m>len(set(z:=[*zip(*s)]))or any(p*3in"".join(v)or v.count("1")*2-len(v)for p in'01'for v in[*s]+z))for s in P(*[[*P(*['01']*m)]]*n))
from itertools import*;P=product

Try it online! Takes as input 2n and 2m. Thanks to Bubbler for finding a bug in my original answer and for golfing a massive 52 bytes off.

How it works:

The anonymous function we define will be taking 2n and 2m as input, generate all binary boards with the specified dimensions and then count how many of those satisfy the restrictions.

Generating all boards

... for s in P(*[[*P(*['01']*m)]]*n))
from itertools import*;P=product

is generating all the boards. The product function from the library itertools can be used to generate the cartesian product of all the arguments it is given. Breaking the nested Ps down, P(*['01']*m) creates a list of length m with '01': ['01', '01', ..., '01'] and then the splat operator * is used to turn each element of the list into an argument to P, so P(*['01']*m) generates all valid rows of length m. Call it P1.

Then we have P(*[[*P1]]*n) which takes all valid rows and turns it into a list of all valid rows, with [*P1]. We then enclose such a list in another list and multiply by n, so that we get a list of length n where each value is a list of all valid rows. Then the splat operator * is used to provide such a list as a series of arguments to the itertools.product function, thus getting all the correct-sized binary sudoku boards. We iterate over those with s.

Checking restrictions on the board

Now we are left with checking the conditions imposed on the board s with

not(n>len({*s})or m>len(set(z:=[*zip(*s)]))or any(p*3in"".join(v)or v.count("1")*2-len(v)for p in'01'for v in[*s]+z))

Instead of verifying if the board satisfies everything, we check if the board doesn't violate any restriction:

n>len({*s})or m>len(set(z:=[*zip(*s)])) checks if there are n unique rows, by converting the list of rows into a set; similarly we transpose s into z and check if there are m unique columns;
then any(B1 or B2 for v in[*s]+z) goes over all rows and all columns:

B2 = v.count("1")*2-len(v) gives 0 when the amount of 1s is exactly half of the size of the row/column and other non-zero integers when it is not. Regardless of giving a positive or negative result, Python will treat it as a Truthy value.
B1 = p*3in"".join(v) for p in'01' builds the substrings "000" and "111" and checks if those are in the row/column

Wrapping it up

In the end, we just sum all the Truthy values that correspond to all the boards that did not violate any restrictions.


Write a Morse Calculator Write a program or function that takes a mathematical expression in Morse code as input, and returns the solution in Morse code.

Valid operations are plus: + and minus: _ (underscore). You can assume you will only receive non-negative integer input, and that the result will be non-negative.

The expression will contain at least two terms, and maximum ten terms. There won't be two adjacent operators i.e. .----+_-...., and there won't be parentheses.

Digits are seperated by single spaces. You can choose to have the operators separated from the numbers by a single space on each side (see examples).

The Morse equivalent for the digits 0-9 are:

0  -----
1  .----
2  ..---
3  ...--
4  ....-
5  .....
6  -....
7  --...
8  ---..
9  ----.

Examples:

Input
Output

.----+.----  (1+1=2) Optional input: .---- + .----
..---

-...._...--  (6-3=3) Optional input: -.... _ ...--
...--

..---_...--+..--- (2-3+2=1)
1

..---+...--_....-+---.._.....  (2+3-4+8-5=4)
....-

.---- ..---_-....+...-- ...--  (12-6+33=39)
...-- ----.

----. -----+----.+..--- ----._..... .....+---..+-...._.----+----.+----._..--- -----  (90+9+29-55+8+6-1+9+9-20=84)
---.. ....-

Standard rules regarding I/O formats etc. apply. A few trailing spaces, and a single newline are accepted. You can't split the number over several lines. You can't use eval or equivalent.

This is code golf, so the shortest code in bytes win.


King-Pen! (Dots and Boxes) This is a king of the hill challenge for Dots and Boxes (aka Pen the Pig). The game is simple, on your turn just draw a line on an empty fence. Every time you complete a square you get a point. Also, since we are playing by championship rules, if you complete at least one square on your turn you get an extra turn. This is a round robin tournament, where each bot plays each other bot twice 12 times on a 9x9 grid. Check out this match between two heavyweight titans, where ChainCollector makes mince meat of reigning co-champion Asdf:

Rules

0.5 second time limit per move.
No interfering with other bots.
Use PigPen.random() and PigPen.random(int) for randomness.
No writing to files.
Bot and all its persistent data will be reset every time opponent changes (every 12 rounds).

Bots
Every bot extends Player.java:
package pigpen;

public abstract class Player {

public abstract int[] pick(Board board, int id, int round);

}

Board is the game board, which mainly serves to give you access to Pen classes, and id is your playerID (tells you if you're first or second), round tells you which round your playing against the same opponent (1 or 2). The return value is an int[], where the first element is the penID (1-indexed), and the second element is the fenceID (0-indexed). See Pen.pick(int) for an easy way to generate this return value. See the Github page for example players and JavaDoc. Since we are only using a square grid ignore any functions and fields related to hexagons.
How to Run

Download Source from Github.
Write your controller bot (make sure to include package pigpen.players) and put it in the src/ folder;
Compile with javac -cp src/* -d . src/*.java. Run with java pigpen.Tournament 4 9 9 false (the last two numbers can be changed to adjust grid size. The last variable should only be set to true if you wish to use the pp_record software.)

Scores

ChainCollector: 72
Asdf: 57
Lazybones: 51
Finisher: 36
=LinearPlayer: 18
=BackwardPlayer: 18
RandomPlayer: 0

See Also:

Dots and Boxes fastest code
Dots and Boxes Wikipedia page

Note: this game is a competitive challenge and not easily solvable, due to giving players an extra turn for completing a box.
Thanks to Nathan Merrill and Darrel Hoffman for consulting on this challenge!
Updates:

Added a moves(int player) method to the Board class to get a list of every move a player has made.

Indefinite Bounty (100 Rep):
First person to post a solution that wins every round, and uses strategy (adjusting play based on observing how the opponent plays).

Lazybones

This bot is lazy. He picks a random spot and direction and continues to build in that direction without moving too much. There are only 2 cases where he does something different:

"make money" by closing a peg with only 1 remaining fence
choose a new spot and direction if placing the fence is not possible or would allow the other bot to "make money"

package pigpen.players;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

import pigpen.Board;
import pigpen.Pen;
import pigpen.PigPen;
import pigpen.Player;

public class Lazybones extends Player {
    private static class Fence {
        private static boolean isOk(Board board, boolean vertical, int row, int col) {
            if (vertical) {
                Pen left = board.getPenAt(row, col - 1);
                Pen right = board.getPenAt(row, col);
                if (left.id() < 0 && right.id() < 0 ||
                        left.fences()[Pen.RIGHT] > 0 ||
                        right.fences()[Pen.LEFT] > 0 ||
                        left.remaining() == 2 ||
                        right.remaining() == 2) {
                    return false;
                }
            } else {
                Pen top = board.getPenAt(row - 1, col);
                Pen bottom = board.getPenAt(row, col);
                if (top.id() < 0 && bottom.id() < 0 ||
                        top.fences()[Pen.BOTTOM] > 0 ||
                        bottom.fences()[Pen.TOP] > 0 ||
                        top.remaining() == 2 ||
                        bottom.remaining() == 2) {
                    return false;
                }
            }
            return true;
        }

        private static Fence pickRandom(Board board) {
            List<Fence> ok = new ArrayList<>();
            List<Fence> notOk = new ArrayList<>();
            for (int row = 0; row < board.rows; row ++) {
                for (int col = 0; col < board.cols; col ++) {
                    (isOk(board, false, row, col) ? ok : notOk)
                            .add(new Fence(false, row, col));
                    (isOk(board, true, row, col) ? ok : notOk)
                            .add(new Fence(true, row, col));
                }
                (isOk(board, true, row, board.cols) ? ok : notOk)
                        .add(new Fence(true, row, board.cols));
            }
            for (int col = 0; col < board.cols; col ++) {
                (isOk(board, false, board.rows, col) ? ok : notOk)
                        .add(new Fence(false, board.rows, col));
            }
            if (ok.isEmpty()) {
                return notOk.get(PigPen.random(notOk.size()));
            } else {
                return ok.get(PigPen.random(ok.size()));
            }
        }

        private final boolean vertical;
        private final int row;
        private final int col;

        public Fence(boolean vertical, int row, int col) {
            super();
            this.vertical = vertical;
            this.row = row;
            this.col = col;
        }

        private Fence next(Board board, boolean negative) {
            int newRow = vertical ? (negative ? row - 1 : row + 1) : row;
            int newCol = vertical ? col : (negative ? col - 1 : col + 1);
            if (isOk(board, vertical, newRow, newCol)) {
                return new Fence(vertical, newRow, newCol);
            } else {
                return null;
            }
        }

        private int[] getResult(Board board) {
            if (vertical) {
                if (col < board.cols) {
                    return board.getPenAt(row, col).pick(Pen.LEFT);
                } else {
                    return board.getPenAt(row, col - 1).pick(Pen.RIGHT);
                }
            } else {
                if (row < board.rows) {
                    return board.getPenAt(row, col).pick(Pen.TOP);
                } else {
                    return board.getPenAt(row - 1, col).pick(Pen.BOTTOM);
                }
            }
        }
    }

    private Fence lastFence = null;
    private boolean negative = false;

    @Override
    public int[] pick(Board board, int id, int round) {
        List<Pen> money = board.getList().stream()
                .filter(p -> p.remaining() == 1).collect(Collectors.toList());
        if (!money.isEmpty()) {
            return money.get(PigPen.random(money.size())).pick(Pen.TOP);
        }
        if (lastFence != null) {
            lastFence = lastFence.next(board, negative);
        }
        if (lastFence == null) {
            lastFence = Fence.pickRandom(board);
            negative = PigPen.random(2) == 0;
        }
        return lastFence.getResult(board);
    }
}


Help the dealer rebuild the deck The dealer has been sloppy and lost track of what cards his/her deck contains and what cards are missing, can you help him/her?

A complete deck consists of 52 playing cards, namely:

Each color in the deck (hearts, diamonds, spades, clubs) contains:

The numbers [2 - 10]
A Jack
A Queen
A King
An Ace

Task

Your program will read the contents of the deck from STDIN until a newline is read.
You can assume that the input will be in the form of "nX nX nX nX" etc. where:

n - any number between [2 - 10] or either 'J', 'Q', 'K' or 'A'.
(You can assume upper case only for non-numeric characters)
X - any of the following : 'H', 'D', 'S', 'C' (You can assume upper
case only)

Where:

'J' = Jacks
'Q' = Queen
'K' = King
'A' = Ace

And

'H' = Hearts
'D' = Diamonds
'S' = Spades
'C' = Clubs

You can assume that there will be no duplicates in the input.

Your program must then print the missing cards in the deck to STDOUT in the same fashion as the input ("nX nX nX") or print 'No missing cards' if all 52 cards are supplied.
There is no constraint on the order of the output of the cards.

Example input:

9H AH 7C 3S 10S KD JS 9C 2H 8H 8C AC AS AD 7D 4D 2C JD 6S

Output:

3H 4H 5H 6H 7H 10H JH QH KH 2D 3D 5D 6D 8D 9D 10D QD 2S 4S 5S 7S 8S 9S QS KS 3C 4C 5C 6C 10C JC QC HC

Happy golfing!

Windows Batch (CMD), 205 204 bytes

@set/pc=
@set d=
@for %%s in (H D S C)do @for %%r in (2 3 4 5 6 7 8 9 10 J Q K A)do @call set d=%%d%% %%r%%s
@for %%c in (%c%)do @call set d=%%d: %%c=%%
@if "%d%"=="" set d= No missing cards
@echo%d%

Loops over the suits and ranks building a complete deck, then deletes the input cards. Save 1 byte if T is allowed instead of 10. Save 11 bytes if command-line arguments are acceptable input. Edit: Saved 1 byte thanks to @user202729.


Sort scrambled two-dimensional array filled with numbers by swapping adjacent numbers A two-dimensional array of size n×n is filled with n*n numbers, starting from number 1. Those numbers are to be sorted per row in ascending order; the first number of a row must be greater than the last number of the previous row (the smallest number of all (1) will be in [0,0]). This is similar to the 15 puzzle.

This is, for example, a sorted array of size n = 3.

1 2 3
4 5 6
7 8 9

Input

The input is a scrambled array. It can be of any size up to n = 10. Example for n = 3:

4 2 3
1 8 5
7 9 6

Output

Output a list of swaps required to sort the array. A swap is defined as following: Two adjacent numbers swap positions, either horizontally or vertically; diagonal swapping is not permitted.

Example output for the example above:

Swap 4 and 1
Swap 8 and 5
Swap 8 and 6
Swap 9 and 8

The less swaps required, the better. Computation time must be feasible.

Here is another example input, with n = 10:

41 88 35 34 76 44 66 36 58 28
6 71 24 89 1 49 9 14 74 2
80 31 95 62 81 63 5 40 29 39
17 86 47 59 67 18 42 61 53 100
73 30 43 12 99 51 54 68 98 85
13 46 57 96 70 20 82 97 22 8
10 69 50 65 83 32 93 45 78 92
56 16 27 55 84 15 38 19 75 72
33 11 94 48 4 79 87 90 25 37
77 26 3 52 60 64 91 21 23 7

If I'm not mistaken, this would require around 1000-2000 swaps.

Mathematica, not golfed

towards[a_,b_]:={a,a+If[#==0,{0,Sign@Last[b-a]},{#,0}]&@Sign@First[b-a]};
f[m_]:=Block[{m2=Map[QuotientRemainder[#-1,10]+1&,m,{2}]},
  Rule@@@Apply[10(#1-1)+#2&,#,{2}]&@
    Reap[Table[
      m2=NestWhile[
        Function[{x},x/.(Sow[#];Thread[#->Reverse@#])&[x[[##]]&@@@towards[First@Position[x,i,{2}],i]]]
        ,m2,#~Extract~i!=i&];
      ,{i,Reverse/@Tuples[Range[10],2]}];][[2,1]]]

Explanation:

The algorithm is similar to "bubble sort". These 100 numbers are put into correct order one by one, 1, 11, 21, ..., 91; 2, ..., 92; ...; 10, ..., 100. They are first move up/down to the correct rows, and then move left to the correct columns.

Function towards gives the two position to swap. For example, if {5,2} is moving to {1,1}, towards[{5,2},{1,1}] gives {{5,2},{5,1}} (move up); and  towards[{5,1},{1,1}] gives {{5,1},{4,1}} (move left).

Results:

For the test case, the total number of swaps is 558. The first few swaps are,

{1->76,1->34,1->35,1->88,1->41,11->16,11->69,11->46, ...

For a random configuration, the total number of swaps is 558.5 ± 28.3 (1σ).


Separate the psychopaths! Dr. Trump is the head psychiatrist at a mental hospital, which is populated by murdering psychopaths. If 2 psychopaths are left together, they will end up brutally injuring or even killing each other, so Dr. Trump needs to build walls to separate these psychopaths, but owing to the limited amount of funds he has left, he has to minimise the number of walls he builds. Walls of a room can either be horizontal or vertical in nature and of any length.

Help Dr. Trump minimise the number of walls he builds to separate all the psychopaths in a 2*n psych ward.

Also, do keep in mind that the shortest code wins.

Input

The first 2 lines contains the position of psychopaths (denoted by '#') and empty spaces (denoted by '-').

Output

An integer which is equal to the minimum number of walls to build to separate all the psychopaths from each other.

Input Constraints

1 <= n <= 1000000

Sample Test Cases

Test Case 1

Sample Input

##########
##########

Sample Output

10

Test Case 2

Sample Input

#-#-#
-#-#-

Sample Output

3

Test Case 3

Sample Input

#-----
------

Sample Output

0

Python, 270 228 166 156 bytes

a=input();b=input();m=lambda s:[c=="#"for c in s];f=m(a);g=m(b);s=p=0
for i in range(len(a)):q=2*f[i]+g[i];r=p&q;s+=r!=0;p=r or p|q
print(s+(any(f)&any(g)))

PEP8-ified:

a = input()
b = input()
m = lambda s: [c == "#"for c in s]
f = m(a)
g = m(b)
s = p = 0
for i in range(len(a)):
    q = 2*f[i]+g[i]
    r = p & q
    s += r != 0
    p = r or p | q
print(s+(any(f) & any(g)))

Try it online!

This is my first time here, be gentle please ;)

There is always a horizontal wall in the middle, except when prisoners are only on one side -- the addition in print() takes this into account. Strategy here is to break horizontal bar into sections such that there is no more than one prisoner on each side, for each section.

The for loop uses an int, p, to hold two bit flags, indicating whether the current top/bottom section already contains a psychopath. We & this with the flags from the new gridsquare to check whether we are going to overflow, and need to place a wall; if so, we increment s. We also use p&q to decide how to update the state: if we overflow, we hold onto just the overflowed prisoner (p&q). Otherwise, we | the new prisoners onto our current prisoner state. Using and and or as a ternary operator again here.

There are some helper functions at the top, as well as throwaway variable names for values used more than once.

Edit:
It seems like this got simpler as it got shorter. It used to use all kinds of wacky behaviour


Longest Cycle in a Graph Given a directed graph, output the longest cycle.
Rules

Any reasonable input format is allowed (e.g. list of edges, connectivity matrix).
The labels are not important, so you may impose any restrictions on the labels that you need and/or desire, so long as they do not contain additional information not given in the input (e.g. you can't require that the nodes in cycles are labeled with integers, and other nodes are labeled with alphabetic strings).
A cycle is a sequence of nodes that are all connected, and no node is repeated, other than the node that is the start and end of the cycle ([1, 2, 3, 1] is a cycle, but [1, 2, 3, 2, 1] is not).
If the graph is acyclic, the longest cycle has length 0, and thus should yield an empty output (e.g. empty list, no output at all).
Repeating the first node at the end of the list of nodes in the cycle is optional ([1, 2, 3, 1] and [1, 2, 3] denote the same cycle).
If there are multiple cycles of the same length, any one or all of them may be output.
Builtins are allowed, but if your solution uses one, you are encouraged to include an alternate solution that does not use trivializing builtins (e.g. a builtin that outputs all cycles). However, the alternate solution will not count towards your score at all, so it is entirely optional.

Test Cases
In these test cases, input is given as a list of edges (where the first element is the source node and the second element is the destination node), and the output is a list of nodes without repetition of the first/last node.
[(0, 0), (0, 1)] -> [0]
[(0, 1), (1, 2)] -> []
[(0, 1), (1, 0)] -> [0, 1]
[(0, 1), (1, 2), (1, 3), (2, 4), (4, 5), (5, 1)] -> [1, 2, 4, 5]
[(0, 1), (0, 2), (1, 3), (2, 4), (3, 0), (4, 6), (6, 8), (8, 0)] -> [0, 2, 4, 6, 8]
[(0, 0), (0, 8), (0, 2), (0, 3), (0, 9), (1, 0), (1, 1), (1, 6), (1, 7), (1, 8), (1, 9), (2, 1), (2, 3), (2, 4), (2, 5), (3, 8), (3, 1), (3, 6), (3, 7), (4, 1), (4, 3), (4, 4), (4, 5), (4, 6), (4, 8), (5, 0), (5, 8), (5, 4), (6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6), (6, 7), (6, 9), (7, 0), (7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (7, 8), (7, 9), (8, 0), (8, 1), (8, 2), (8, 5), (8, 9), (9, 1), (9, 2), (9, 3), (9, 4), (9, 5), (9, 6)] -> [0, 9, 6, 7, 8, 2, 5, 4, 3, 1]
[(0, 0), (0, 2), (0, 4), (0, 5), (0, 7), (0, 9), (0, 11), (1, 2), (1, 4), (1, 5), (1, 8), (1, 9), (1, 10), (2, 0), (2, 1), (2, 3), (2, 4), (2, 5), (2, 6), (3, 0), (3, 1), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (3, 11), (4, 1), (4, 3), (4, 7), (4, 8), (4, 9), (4, 10), (4, 11), (5, 0), (5, 4), (5, 6), (5, 7), (5, 8), (5, 11), (6, 0), (6, 8), (6, 10), (6, 3), (6, 9), (7, 8), (7, 9), (7, 2), (7, 4), (7, 5), (8, 8), (8, 9), (8, 2), (8, 4), (8, 7), (9, 0), (9, 1), (9, 2), (9, 3), (9, 6), (9, 10), (9, 11), (10, 8), (10, 3), (10, 5), (10, 6), (11, 2), (11, 4), (11, 5), (11, 9), (11, 10), (11, 11)] -> [0, 11, 10, 6, 9, 3, 8, 7, 5, 4, 1, 2]

Mathematica, 80 58 bytes

Saved a whopping 22 bytes thanks to JungHwan Min

(FindCycle[#,∞,All]/.{}->{Cases[#,v_v_]})[[-1,;;,1]]&

 is the three byte private use character U+F3D5 representing \[DirectedEdge]. Pure function with first argument # expected to be a list of directed edges. Finds All cycles of length at most Infinity in Graph@#, then replaces the empty list with the list of self-loops. Cycles are represented as lists of edges and sorted by length, so we take the last such cycle, then from all of its edges we take the first argument so that we get a list of vertices in the specified output format.

If only Mathematica treated loops as a cycle of length 1 (AcyclicGraphQ @ CycleGraph[1, DirectedEdges -> True] gives True, seriously), then we could save another 26 bytes:

FindCycle[#,∞,All][[-1,;;,1]]&


Integral triangles and integral medians Consider a triangle ABC where each side has integer length (an integral triangle). Define a median of ABC to be a line segment from a vertex to the midpoint of the opposing side. In the figure below, the red line segments represent the medians. Note that any given triangle has three medians.

Let n be some positive integer. How many non-degenerate integral triangles with each side length less than or equal to n have at least one integral median?

Challenge

Write a program to compute the number of integral triangles with at least one integral median for a given maximum side length n. The order of the side lengths does not matter, i.e. <6,6,5> represents the same triangle as <5,6,6> and should be counted only once. Exclude degenerate triangles such as <1,2,3>.

Scoring

The largest n for which your program can generate the number of triangles in 60 seconds on my machine is your score. The program with the highest score wins. My machine is a Sony Vaio SVF14A16CLB, Intel Core i5, 8GB RAM.

Examples

Let T(N) be the program with input N.

T(1) = 0
T(6) = 1
T(20) = 27
T(22) = 34

Note that T(1) = T(2) = T(3) = T(4) = T(5) = 0 because no combination of integral sides will yield an integral median. However, once we get to 6, we can see that one of the medians of the triangle <5,5,6> is 4, so T(6) = 1.

Note also that T(22) is the first value at which double-counting becomes an issue: the triangle <16,18,22> has medians 13 and 17 (and 2sqrt(85)).

Computing the medians

The medians of a triangle can be calculated by the following formulas:

Current top score: Sp3000 - 7000 points - C

C, brute force - n=6080

This is more a baseline than a serious contender, but at least it should get things started.

n=6080 is as high as I got in a minute of runtime on my own machine, which is a MacBook Pro with an Intel Core i5. The result I got for this value is:

  15041226

The code is purely brute force. It enumerates all the triangles within the size limit, and tests for the condition:

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

static inline int isSquare(int v) {
    int s = (int)(sqrtf((float)v) + 0.5f);
    return s * s == v;
}

static inline int isMedian(int v) {
    return v % 4 == 0 && isSquare(v / 4);
}

int main(int argc, char* argv[]) {
    int n = atoi(argv[1]);
    int nTri = 0;
    int a, b, c;

    for (c = 1; c <= n; ++c) {
        for (b = (c + 1) / 2; b <= c; ++b) {
            for (a = c - b + 1; a <= b; ++a) {
                if (isMedian(2 * (b * b + c * c) - a * a) ||
                    isMedian(2 * (a * a + c * c) - b * b) ||
                    isMedian(2 * (a * a + b * b) - c * c)) {
                    ++nTri;
                }
            }
        }
    }

    printf("%d\n", nTri);

    return 0;
}


All aboard the factorial train The system

Assume the Earth is flat and that it extends infinitely in all directions. Now assume we have one infinitely long train railway and n trains in that railway. All trains have different speeds and all trains are going in the same direction. When a faster train reaches a slower train, the two trains connect (becoming a single train) and the new train keeps going at the speed with which the slower train was going.

E.g., if we have two trains, one going at speed 1 and another at speed 9, the lines below "simulate" what would happen on the railway:

9               1
         9       1
                 11
                  11
                   11

whereas if the trains start in a different order, we'd have

1 9
 1         9
  1                 9
   1                          9
etc...

With that being said, given a train/position/speed configuration there comes a time when no more connections will be made and the number of trains on the railway stays constant.

Task

Given the number n of trains in the railway, your task is to compute the total number of trains there will be on the railway, after all the connections have been made, summing over all n! possible arrangements of the n trains.

A possible algorithm would be:

Start counter at 0
Go over all possible permutations of the train speeds

Simulate all the connections for this permutation
Add the total number of remaining trains to the counter

Return the counter

Note that you can assume the train speeds are whatever n distinct numbers that you see fit, what really matters is the relationships between train speeds, not the magnitudes of the differences in speeds.

Input

You must take n, a positive integer, as input.

Output

An integer representing the total number of trains that there will be on the railway, summed over all possible permutations of the trains.

Test cases

1 -> 1
2 -> 3
3 -> 11
4 -> 50
5 -> 274
6 -> 1764
7 -> 13068
8 -> 109584
9 -> 1026576
10 -> 10628640
11 -> 120543840
12 -> 1486442880
13 -> 19802759040
14 -> 283465647360
15 -> 4339163001600
16 -> 70734282393600
17 -> 1223405590579200
18 -> 22376988058521600
19 -> 431565146817638400
20 -> 8752948036761600000

This is code-golf so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it! If you dislike this challenge, please give me your feedback. Happy golfing!

Jelly,  5  4 bytes

!:RS

Try it online! Or see the test-suite.

How?

When we introduce an \$n^{\text{th}}\$ train it allows:

\$(n-1)!\$ states - by being placed behind none of the \$n-1\$ existing trains and being faster than all of them.
all the previous end states, each in \$n\$ different ways - by being placed behind at least one existing train and being faster than \$[0,n-1]\$ of the \$n-1\$ existing trains

We know \$a(1) = 1\$ so...

n  a(n)
1  1
2  1! + 1*2
3  2! + 1!*3 + 1*2*3
4  3! + 2!*4 + 1!*3*4 + 1*2*3*4
5  4! + 3!*5 + 2!*4*5 + 1!*3*4*5 + 1*2*3*4*5
... etc

Which is:

n  a(n)
1  1
2  1 + 2
3  1*2 + 1* 3 + 2*3
4  1*2*3 + 1*2* 4 + 1* 3*4 + 2*3*4
5  1*2*3*4 + 1*2*3* 5 + 1*2* 4*5 + 1* 3*4*5 + 2*3*4*5
...
n  n!/n + n!/(n-1) + n!/(n-2) + ... + n!/1

Hence the code:

!:RS - integer, n
!    - (n) factorial      n!
  R  - range (n)          [1,...,n-2,n-1,n]
 :   - integer division   [n!/1,...,n!/(n-2),n!/(n-1),n!/n]
   S - sum                a(n)


One 1, Two 1's, One 2 One 1 Challenge:

Create a program that takes input of a positive non-zero integer and outputs the 4 next numbers in the sequence described below.

Note: Checking if the input is actually a positive non-zero integer is not necessary

Sequence:

Every number in this sequence (apart from the first, which is the input) shall be composed of n digits, where n is an even number. If we split the number to n/2 pairs, for each pair, the first digit should be the amount of times the second digit appeared in the previous number

Visual explanation:
Consider this example "sequence starter" or input 6577
The next number in the sequence should look like this 161527
Because the input has 1 "6", 1 "5" and 2 "7"s.

If input has too many digits (more than 9 of a single digit) you wouldnt be able to get a correct output
Example: 111111111111 (12 1's)
Next number in sequence has to describe 12 1's. Thus we split it into 9 1's and 3 1's (sum 9+3 = 12)
Next number: 9131

You should iterate 4 times for the input, and output it (either return a list/array of 4 integers, or output it by seperating them with a space, newlines are also acceptable)

"The number can be written in a lot of ways, how do I write it?":
If you think about it, the example input 6577 can also be written as 271516 (two 7's, one 5, one six). However this is non-valid output. You should iterate the number left to right. Thus 161527. If it was 7657 you would iterate the amount of 7's, then amount of 6's then amount of 5's, thus valid output would be 271615

Example I/O:

Input:75
Output:1715 211715 12311715 4112131715

Input:1
Output:11 21 1211 3112

Input:111111111111 (12 1's)
Output:9131 192113 31191213 23411912

This is unlike the "Say what you see" question, because the sequences are different: https://oeis.org/A005150 <- This one returns numbers like this:
Input: 1211 Output: 111221
While the sequence I'm asking for would do
Input: 1211 Output: 3112

The two sequences are different and require different algorithms.
My asked sequence: https://oeis.org/A063850
"Possible duplicate" sequence: https://oeis.org/A005150

Important specification:

Since it wasnt clear enough for some people who tried to answer this question, the correct output for k chars where k > 9 is not "kc" (where c is char) but 9c(k-9)c etc. Thus correct output for 12 1's isn't 121 (12 1) but 9131(9 1's, (12-9) 1's and so on)

If in doubt, your code is wrong if it ever outputs a number with an odd amount of digits (like 121), it should have output of even digit numbers due to the nature of the sequence.

This is code-golf thus code with least bytes wins.

PowerShell, 111 104 bytes

$z=$args;1..4|%{($z=-join($z-split'\B'|group|%{for($c,$n=$_.Count,$_.Name;$c-gt9;$c-=9){"9$n"}"$c$n"}))}

Try it online!


Solve the busy beaver Given a number n, calculates BB(n) (the maximum number of 1s finally on the tape, among all halting 2-symbol n-state Turing machines with tape of zeros).

To solve the problem, you are given an extra (black-box) function H as input, which takes a function in your language (f) and returns a truthy/falsy value indicates whether this function will halt. However, the function f must not have any side-effects (I/O operations, timing, etc.) or call the halting function H.

Note that, there is no restriction on how you use the function H. A possible way is to use the function H to check if each Turing machine halts, and then simulate those to calculate the maximum, but there are other ways to compute BB(n).

You need to prove that it solves such a problem. Shortest code in bytes wins.

Definition of Turing Machine:

Turing machines, each member of which is required to meet the following design specifications:

    The machine has n "operational" states plus a Halt state, where n is a positive integer, and one of the n states is distinguished as the starting state. (Typically, the states are labelled by 1, 2, ..., n, with state 1 as the starting state, or by A, B, C, ..., with state A as the starting state.)
    The machine uses a single two-way infinite (or unbounded) tape.
    The tape alphabet is {0, 1}, with 0 serving as the blank symbol.
    The machine's transition function takes two inputs:

        the current non-Halt state,
        the symbol in the current tape cell,

    and produces three outputs:

        a symbol to write over the symbol in the current tape cell (it may be the same symbol as the symbol overwritten),
        a direction to move (left or right; that is, shift to the tape cell one place to the left or right of the current cell), and
        a state to transition into (which may be the Halt state).

    There are thus (4n + 4)2n n-state Turing machines meeting this definition.
    The transition function may be seen as a finite table of 5-tuples, each of the form
    (current state, current symbol, symbol to write, direction of shift, next state).

Perl 5, 149 147 bytes (+15 bytes if you want to be really strict)

Generates all Turing machines, use H as oracle to see if they halt and if so runs them, count the number of 1s and take the maximum

#!/usr/bin/perl -p
$"=",",@t=1..$_;map{H($f=sub{my%v;$v{$n}=$1while/(A?)(\d+)(\W)$2$v{$n+=$3.1}/;map/A/,%v})&&\$G[&$f]}glob join"V{,A}{@t,0}{+,-}",0,<{@t}{,A}>;$_=$#G

Slightly breaks the conditions on f though not in an very bad way.

$n is the starting position on the tape and is a global. So on each new run it starts where the previous Turing machine left off. But since the tape state is local and starts empty it doesn't matter where you start, so it's not actually used to communicate anything (adding $n to the my solves that at a cost of 5 bytes)
I pass the actual Turing machine in global $_. That's also easily solved by e.g. a for loop over my variable $g and use it in $f via closure  with while$g=~/.../ at the cost of 10 bytes. However the current way has the advantage that I can also see $_ inside H and return true for a few halting Turing machines so that I can really compute BB(1) and BB(2) and BB(3) (BB(3) takes 90 minutes on my computer)

Try it online!

The TIO link implements an actual (sort of) halting function in the header.

The default version has the actual size 1 to 3 busy beaver hard-coded and returns true only for that particular Turing machine. All others return false
If you add a 1 on the next input line after the size then H will be a real halting function but only for a tape that runs from -10 to 10. It will return false for any Turing machine that repeats its complete state or reaches the edge of the tape (so 19 tape positions can actually be used). It returns true for any Turing machine that halts on this restricted tape. This is enough to really calculate BB(1), BB(2) and BB(3) (you'll need lots of patience and memory for BB(3) but it does work). It also prints out some info about long running machines it finds along the way.
If instead you add -1 on the next input line after the size then H will behave like what is described for extra argument 1 but will also show the full execution trace of every Turing machine it tries.

Each Turing machines is represented by a strings that describe all input tuples with their corresponding output state. A tape value is either A (for 1) or empty (for 0). The states are numbered from 1 to n, 0 is the halting state. A tuple is the concatenation of:

value to write to tape (A or empty)
new state (1 to n or 0)
direction to move the head (+ or -)
input state (1 to n)
input tape value (A or empty)

The full string consists of a dummy 0 and then 2n tuples in increasing order all separated by V. So for example a 2 state busy beaver Turing machine in this notation is:

0VA2+1VA2-1AVA1-2VA0+2A

which represents these 4 tuples:

A2+1     in state 1 seeing 0, write 1 move right go to state 2
A2-1A    in state 1 seeing 1, write 1 move left  go to state 2
A1-2     in state 2 seeing 0, write 1 move left  go to state 1
A0+2A    in state 2 seeing 1, write 1 move right go to state 0 (halt)


A fastest algorithm optimization challenge This is my first experiment with an asymptotic complexity challenge although I am happy with answers entirely in code as long as they come with an explanation of their time complexity.

I have the following problem.

Consider tasks T_1, ... T_n and procs M_1, ... , M_m.  Each task takes a certain amount of time to perform depending on the procs.

Each task also costs a certain amount to perform depending on the procs.

The tasks have to be done in strict order (they can't be done in parallel) and it takes time to change proc.  A task can't be moved from one proc to another after it has been started.

Finally, each task must be completed by a certain time.

the task

The objective is to give an algorithm (or some code) that given five tables of the form above, minimizes the total cost to complete all the tasks while making sure all the tasks are completed by their deadlines. If this isn't possible we just report that it can't be done.

score

You should give the big Oh complexity of your solution in terms of the variables n, m and d, where d is the last deadline.  There should be no unnecessary constants in your big Oh complexity. So O(n/1000) should be written as O(n), for example.

Your score is calculated simply by setting n = 100, m = 100 and d = 1000 into your stated complexity.  You want the smallest score possible.

tie breaker

In the case of a tie, the first answer wins.

added notes

log in the time complexity of an answer will be taken base 2.

score board

10^202 from KSFT  (Python) First submitted so gets the bounty.
10^202 from Dominik Müller (Scala)

Score: 10^202

I kinda wish we had LaTeX support now...

Since no one else has answered, I thought I'd try, even though is isn't very efficient. I'm not sure what the big O of it is, though.

I think it works. At least, it does for the only test case posted.

It takes input like in the question, except without the machine or task number labels, and with semicolons instead of line breaks.

import itertools
time = [[int(j) for j in i.split()] for i in raw_input().split(";")]
cost = [[int(j) for j in i.split()] for i in raw_input().split(";")]
nmachines=len(time)
ntasks=len(time[0])
switchtime = [[int(j) for j in i.split()] for i in raw_input().split(";")]
switchcost = [[int(j) for j in i.split()] for i in raw_input().split(";")]
deadline = [int(i) for i in raw_input().split()]
d={}
m=itertools.product(range(nmachines),repeat=ntasks)
for i in m:
    t=-switchtime[i[-1]][i[0]]
    c=-switchcost[i[-1]][i[0]]
    e=0
    meetsdeadline=True
    for j in range(ntasks):
        t+=switchtime[i[e-1]][i[e]]+time[i[e]][j]
        c+=switchcost[i[e-1]][i[e]]+cost[i[e]][j]
        e+=1
        if t>deadline[j]:
            meetsdeadline=False
    if meetsdeadline:
        d[(c,t)]=i
print min(d.keys()),d[min(d.keys())]


Time Travelling Stock Trader Story
Long time ago Bobby created a Bitcoin wallet with 1 Satoshi (1e-8 BTC, smallest currency unit) and forgot about it. Like many others he later though "Damn, if only I invested more back then...".
Not stopping at daydreaming, he dedicates all of his time and money to building a time machine. He spends most of his time in his garage, unaware of worldly affairs and rumors circulating about him. He completes the prototype a day before his electricity is about to be turned off due to missed payments. Looking up from his workbench he sees a police van pulling up to his house, looks like the nosy neighbours thought he is running a meth lab in his garage and called the cops.
With no time to run tests he grabs a USB-stick with the exchange rate data of the past years, connects the Flux Capacitor to the Quantum Discombobulator and finds himself transported back  to the day when he created his wallet

Task
Given the exchange rate data, find out how much money Bobby can make. He follows a very simple rule: "Buy low - sell high" and since he starts out with an infinitesimally small capital, we assume that his actions will have no impact on the exchange rates from the future.

Input
A list of floats > 0, either as a string separated by a single character (newline, tab, space, semicolon, whatever you prefer) passed as command line argument to the program, read from a textfile or STDIN or passed as a parameter to a function. You can use numerical datatypes or arrays instead of a string because its basically just a string with brackets.

Output
The factor by which Bobbys capital multiplied by the end of trading.

Example

Input:  0.48 0.4 0.24 0.39 0.74 1.31 1.71 2.1 2.24 2.07 2.41

Exchange rate: 0.48 $/BTC, since it is about to drop we sell all Bitcoins for 4.8 nanodollar. Factor = 1
Exchange rate: 0.4, do nothing
Exchange rate: 0.24 $/BTC and rising: convert all $ to 2 Satoshis. Factor = 1 (the dollar value is still unchanged)
Exchange rate: 0.39 - 2.1 $/BTC: do nothing
Exchange rate: 2.24 $/BTC: sell everything before the drop. 44.8 nanodollar, factor = 9.33
Exchange rate: 2.07 $/BTC: buy 2.164 Satoshis, factor = 9.33
Exchange rate: 2.41 $/BTC: buy 52.15 nanodollar, factor = 10.86

Output: 10.86

Additional Details
You may ignore weird edge cases such as constant input, zero- or negative values, only one input number, etc.
Feel free to generate your own random numbers for testing or using actual stock charts. Here is a longer input for testing (Expected output approx. 321903884.638)
Briefly explain what your code does
Graphs are appreciated but not necessary

APL, 16 chars

{×/1⌈÷/⊃⍵,¨¯1⌽⍵}

This version uses @Frxstrem's simpler algorithm and @xnor's max(r,1) idea.

It also assumes that the series is overall rising, that is, the first bitcoin value is smaller than the last one. This is consistent with the problem description. To get a more general formula, the first couple of rates must be dropped, adding 2 chars: {×/1⌈÷/⊃1↓⍵,¨¯1⌽⍵}

Example:

    {×/1⌈÷/⊃⍵,¨¯1⌽⍵}  0.48 0.4 0.24 0.39 0.74 1.31 1.71 2.1 2.24 2.07 2.41
10.86634461
    {×/1⌈÷/⊃⍵,¨¯1⌽⍵}  (the 1000 array from pastebin)
321903884.6

Explanation:

Start with the exchange rate data:

    A←0.48 0.4 0.24 0.39 0.74 1.31 1.71 2.1 2.24 2.07 2.41

Pair each number with the preceding one (the first will be paired with the last) and put them into a matrix:

    ⎕←M←⊃A,¨¯1⌽A
0.48 2.41
0.4  0.48
0.24 0.4
0.39 0.24
0.74 0.39
1.31 0.74
1.71 1.31
2.1  1.71
2.24 2.1
2.07 2.24
2.41 2.07

Reduce each row by division, keep those with ratio > 1, and combine the ratios by multiplication. This will eliminate any repeating factors in a row of successive rising rates, as well as the spurious ratio between the first and last exchange rates:

    ×/1⌈÷/M
10.86634461


Write a Unicode Unpacker We all know scoring by characters is ripe for abuse. Let's prove this.
The Challenge
Output the following:
"m8V}G=D@7G1lAI,v08`
#(hNb0A8T!g;==SVaG5~
g"jUF!bmRY(3I@na?2S{
fJVzo/GQYU%ybpfUq3aG
Yza[jc,WJ$bP^7r};Da}
V-!Z+Nk:`/poc}d/X:G\
sWX{dbAUv6,i]%RG$hRp
),bd+?/{U1tU[;<;u.Nk
ZFPIOzJ/HimL!nexc,ls
HM%k3D$n2|R,8L?'eI_n
qs.kzbil$UQy_#Z)l#i%
*G4gr2<R^y#/iQ9,<+p%
}BYnb3_&:!m;#~QL1C?t
f.U>wIkTz=P>bf!uwb!d
z()rG)>~:q4#\}~pQEvZ
=OT8T4<i50%/8%eX^"3E
#Ks(8}OzZ&]RQ(-BLy<7
p7B~GEsF$)>?a"dtGCC'
H;:n&p&Z($ukNd,Et.$O
F*Uq0$dm,m%ejPT~u,qL

The characters inside the box are selected uniformly at random between the codepoints 0x21 and 0x7e. This means they should not be compressable much ordinarily. However, in this challenge, your code is scored by the number of characters, which can range in codepoint between 0x00 and 0x10ffff. Since this gives about 21 bits of information per character, and the box contains about 7 bits of information per character, approaching a 3:1 packing should be possible.
Note that:

As usual, you may output to STDOUT or return the string from a function;
A trailing newline on the last line is optional. Apart from this, the output must be exactly as given.
List representations are acceptable if returning from a function.

Scoring
The score is the length of your code in characters, expressed in the encoding of your language's interpreter. For most languages, this will be UTF-8. Note that languages that use an SBCS, such as most golfing languages, are at a huge disadvantage here as the number of characters is equal to the number of bytes.
Note that characters are not the same as grapheme clusters. For example,  is actually 3 characters (0x1f468 0x200d 0x1f9b2).

Python 3, 223 221 216 214 212 chars
ጸ=0
for  in"ጸꛯ裶":ጸ=ጸ<<20|ord()
while ጸ:print(end=chr(ጸ%128));ጸ>>=7

Converts from base 2²⁰ (1048576) to base 128. Just for fun, I used some of the letters from the encoded string as variable names.

Edit 1: (221) I saved two characters by using base 128 rather than base 127, allowing me to use the bit-shift operation >>=7 rather than the integer division //=127.
Edit 2: (216) Thanks to ovs in the comments for suggesting a way to save a whopping five characters.
Edit 3: (214) Using base 2²⁰ allows us to save another two characters, because we can write the constant as 2**20 in the code, which only takes five characters to write rather than seven.
Edit 4: (212) We can write ጸ<<20|ord() instead of ጸ*2**20+ord().


Compress and Decompress sentence using vowel based encryption cipher The aim is to parse a sentence and compress/encrypt it according to the rules below and then decrypt it using the key:

Remove all letters in a word before the first vowel is encountered. Example: pigeon becomes igeon.
All characters except alphabets should be kept in the sentence including numerals, punctuations, etc. Example: 200-storey building becomes 200-orey uilding.
Generate the shortest key array char[] = {a,b,x,<your data>} and write code to generate the original sentence using this key.

You need to write two functions: encrypt() and decrypt() which works for every sentence minimising the key-size.

Example 1:

  Input: The most technologically efficient machine man has ever
  invented is the book. -Northrop Frye-

  Output: e ost echnologically efficient achine an as ever invented is e
  ook. -orthrop e-

  Example key: {T,m,t,m,h,b,N,F,14,2,5}

Example 2:

  Input: "I need your clothes, your boots and your motorcycle. " - The
  T-800 in Terminator 2: Judgment Day

  Output: "I eed our othes, our oots and our otorcycle. " - e -800 in
  erminator 2: udgment ay

  Example key: {n,y,c,2,b,2,m,T,J,D,15}

Winning Criteria:

Write function encrypt() with input from stdin or file which generates output sentence and a key on stdout or file or memory.
Write function decrypt() with inputs the generated sentence and key from encrypt() and produces the original sentence.
This is code-golf so cumulative size of the two functions should be minimum. In case of tie-breaker, the generated key-size should be minimum.

Perl (126+67=193 characters)

Key contains each character removed along with its offset.

Encrypt reads one line from STDIN

Decrypt reads two: first the ciphered string then the key

sub encrypt{$_=<>;s(.)(++$j,$q|=$&=~/[aeiou]/i,$q^=$&eq$",!$q&$&=~/[a-z]/i&&(push@d,($&,$j-1))||print$&)ge;print$/.join',',@d}
sub decrypt{$q=<>,$_=<>;s/(.),(\d+)/substr($q,$2,0)=$1/gie;print$q}

Examples:

(encrypting)
The most technologically efficient machine man has ever invented is the book. -Northrop Frye-
> e ost echnologically efficient achine an as ever invented is e ook. -orthrop e-
> T,0,h,1,m,4,t,9,m,35,m,43,h,47,t,68,h,69,b,72,N,79,F,88,r,89,y,90

"I need your clothes, your boots and your motorcycle. " - The T-800 in Terminator 2: Judgment Day
> "I eed our othes, our oots and our otorcycle. " - e -800 in erminator 2: Judgment ay
> n,3,y,8,c,13,l,14,y,22,b,27,y,37,m,42,T,58,h,59,T,62,T,71,D,94

(decrypting)
e ost echnologically efficient achine an as ever invented is e ook. -orthrop e-
T,0,h,1,m,4,t,9,m,35,m,43,h,47,t,68,h,69,b,72,N,79,F,88,r,89,y,90
> The most technologically efficient machine man has ever invented is the book. -Northrop Frye-

"I eed our othes, our oots and our otorcycle. " - e -800 in erminator 2: Judgment ay
n,3,y,8,c,13,l,14,y,22,b,27,y,37,m,42,T,58,h,59,T,62,T,71,D,94
> "I need your clothes, your boots and your motorcycle. " - The T-800 in Terminator 2: Judgment Day

Ungolfed with comments

sub encrypt{
    # get input
    $_=<>;
    # for each character
    s(.)(
        # increment j
        ++$j,
        # set q to 1 if vowel
        $q |= $&=~/[aeiou]/i,
        # set q to 0 if space
        $q ^= $& eq $",
        # if q==0 and is a letter (consonant, because q=1 if vowel)
        !$q & $&=~/[a-z]/i &&
            # push both the letter and the offset to @d
            (push @d,($&,$j-1))
        # otherwise print
        || print$&
    )ge;
    # print a newline, then @d
    print$/.join',',@d
}
sub decrypt{
    # read a line to $q, and another to $_
    $q=<>,$_=<>;
    # for each [character],[number] in key
    s/(.),(\d+)/
        # add character back into string
        substr($q,$2,0)=$1
    /gie;
    # print deciphered string
    print$q
}