text:
Hot Potato Salesman

Given a list of points, find the shortest path that visits all points and returns to the starting point.

The Travelling Salesman Problem is well-known in the computer science field, as are many ways to calculate/approximate it. It's been solved for very large groups of points, but some of the largest take many CPU-years to finish.

Don't get burned by the potato.

Hot Potato is a game where 2+ players pass a "potato" around in a circle while music plays. The object is to pass it to the next player quickly. If you are holding the potato when the music stops, you're out.

The object of Hot Potato Salesman is:

Given a set of 100 unique points, return those points in a better order (shorter total distance as defined further down). This will "pass" the problem to the next player. They have to improve it and pass it to the next, etc. If a player cannot improve it, they are out and play continues until one player is left.

To keep this from being a "brute-force-me-a-path" competition, there are these stipulations:

You cannot take more than one minute to pass the potato. If you haven't found and passed a shorter solution by the time one minute is up, you're out.

You cannot change the position of more than 25 points. To be exact, >= 75 points must be in the same position as you received them. It does not matter which ones you decide to change, just the amount you change.

When only one player is left, he is the winner of that game, and receives one point. A tourney consists of 5*n games, where n is the number of players. Each game, the starting player will be rotated, and the remaining player order will be shuffled. The player with the most points at the end is the winner of the tourney. If the tourney ends with a tie for first place, a new tourney will be played with only those contestants. This will continue until there is no tie.
The starting player for each game will receive a set of pseudorandomly selected points in no particular order.
Points are defined as a pair of integer x,y coordinates on a cartesian grid. Distance is measured using Manhattan distance, |x1-x2| + |y1-y2|. All coordinates will lie in the [0..199] range.
Input
Input is given with a single string argument. It will consist of 201 comma-separated integers representing the number of current players(m) and 100 points:
m,x0,y0,x1,y1,x2,y2,...,x99,y99

The order of these points is the current path. The total distance is obtained by adding the distance from each point to the next (dist(0,1) + dist(1,2) + ... + dist(99,0)). Don't forget to return to start when calculating total distance!
Note that m is not the number of players that started the game, it is the number that are still in.
Output
Output is given in the same way as input, minus m; a single string containing comma-separated integers representing the points in their new order.
x0,y0,x1,y1,x2,y2,...,x99,y99

The control program will wait for output for one minute only. When output is received, it will verify that:

the output is well-formed
the output consists of only and all the 100 points present in the input
>=75 points are in their original positions
the path length is less than the previous path

If any of these checks fail (or there is no output), you are out and the game will proceed to the next player.
Control Program
You can find the control program at this link. The control program itself is deterministic, and is posted with a dummy seed of 1. The seed used during scoring will be different, so don't bother trying to analyze the turn order/point lists it spits out.
The main class is Tourney. Running this will do a full tournament with contestants given as arguments. It spits out the winner of each game and a tally at the end. A sample tourney with two SwapBots looks like:
Starting tournament with seed 1

(0) SwapBot wins a game! Current score: 1
(1) SwapBot wins a game! Current score: 1
(1) SwapBot wins a game! Current score: 2
(1) SwapBot wins a game! Current score: 3
(0) SwapBot wins a game! Current score: 2
(1) SwapBot wins a game! Current score: 4
(1) SwapBot wins a game! Current score: 5
(1) SwapBot wins a game! Current score: 6
(1) SwapBot wins a game! Current score: 7
(1) SwapBot wins a game! Current score: 8

Final Results:

Wins        Contestant
2       (0) SwapBot
8       (1) SwapBot

If you want to test just one game at a time, you can run the Game class instead. This will run one game with players in the order given as arguments. By default, it will also print a play-by-play showing the current player and path length.
Also included are a few test players: SwapBot, BlockPermuter, and TwoSwapBot. The first two will not be included in scoring runs, so feel free to use and abuse them during testing. TwoSwapBot will be included in judging, and he's no slouch, so bring your A-game.
Miscellany

You cannot save state information, and each turn is a separate run of your program. The only information you will receive each turn is the set of points.

You cannot use external resources. This includes network calls and file access.

You cannot use library functions designed to solve/assist with the TSP problem or its variants.

You cannot manipulate or interfere with other players in any way.

You cannot manipulate or interfere with the control program or any included classes or files in any way.

Multi-threading is allowed.

One submission per user. If you submit more than one entry, I will only enter the first one submitted. If you want to change your submission, edit/delete the original.

The tournament will be running on Ubuntu 13.04, on a computer with an i7-3770K CPU and 16GB RAM. It will not be run in a VM. Anything I perceive as malicious will immediately disqualify the current and any future entry you submit.

All entries must be runnable from the command line with free (as in beer) software. If I have problems compiling/running your entry, I will request aid in the comments. If you do not respond or I cannot ultimately get it running, it will be disqualified.

Results (22 May 2014)
New results are in! UntangleBot has beaten the competition quite soundly. TwoSwapBot managed seven wins, and SANNbot snuck a victory in as well. Here's a scoreboard, and a link to the raw output:
Wins        Contestant
22      (2) ./UntangleBot
7       (0) TwoSwapBot
1       (5) SANNbot.R
0       (1) BozoBot
0       (3) Threader
0       (4) DivideAndConquer

As it stands now, UntangleBot has won the checkmark. Don't let that discourage you from entering, though, since I'll run the tournament as more contestants appear and change the accepted answer accordingly.

Comments purged. Please notify me for any possible lost information.

Man why did this challenge have to be during my final exams (finally, done with school yeay). You sure are a bad planner Geobits ;) Weird/sadly enough at that time there were tons of king-of-the-hill questions and now there aren't any (maybe it works better if there is only one at a time, hint hint) ...

@Herjan Feel free to try to tackle the current champ. I'll run the tourney again as new contestants appear, so the contest isn't over or anything. Beat SirDarius and it may spur him or someone else to beat yours, breathing life back into it ;)

@Herjan Please do submit an entry ! I believe there is a lot of room for improvement here. Most of the solutions here, including mine, do not rely on clever algorithms specific to this problem.

I think there is a problem with modification limitation. As some times it will take to modify the entire set of data to get better solution.

UntangleBot (formerly NiceBot)
A C++11 bot that uses two strategies.
At first it will try to "untangle" the path if possible, by detecting intersections between paths that are closer than 25 points (since untangling implies modifying all points in-between).
If the first strategy fails, it randomly swaps points to find better distances until a better path has been found.
This bot consistently beats TwoSwapBot with an approximate ratio of five victories for one loss in my test tourneys.
// g++ -std=c++11 -O3 -o UntangleBot UntangleBot.cpp
#include <algorithm>
#include <chrono>
#include <cmath>
#include <iostream>
#include <iterator>
#include <random>
#include <set>
#include <sstream>

const int NPOINTS = 100;

struct Point {
    int x, y;

    Point():x(0),y(0) {}
    Point(int x, int y):x(x),y(y) {}

    int distance_to(const Point & pt) const {
        return std::abs(x - pt.x) + std::abs(y - pt.y);
    }
};

std::ostream & operator<<(std::ostream & out, const Point & point) {
    return out << point.x << ',' << point.y;
}

int total_distance(const Point points[NPOINTS]) {
    int distance = 0;
    for (int i = 0; i < NPOINTS; ++i) {
        distance += points[i].distance_to(points[(i+1)%NPOINTS]);
    }
    return distance;
}

bool intersects(const Point & p1, const Point & p2, const Point & p3, const Point & p4) {
    double s1_x, s1_y, s2_x, s2_y;
    s1_x = p2.x - p1.x;
    s1_y = p2.y - p1.y;
    s2_x = p4.x - p3.x;
    s2_y = p4.y - p3.y;

    double s, t;
    s = (-s1_y * (p1.x - p3.x) + s1_x * (p1.y - p3.y)) / (-s2_x * s1_y + s1_x * s2_y);
    t = ( s2_x * (p1.y - p3.y) - s2_y * (p1.x - p3.x)) / (-s2_x * s1_y + s1_x * s2_y);

    return s >= 0 && s <= 1 && t >= 0 && t <= 1;
}

int main(int argc, char ** argv) {
    Point points[NPOINTS];

    using Clock = std::chrono::system_clock;
    const Clock::time_point start_time = Clock::now();

    // initialize points
    if (argc < 2) {
        std::cerr << "Point list is missing" << std::endl;
        return 1;
    }
    std::stringstream in(argv[1]);
    int players;
    char v;
    in >> players >> v;
    for (int i = 0; i < NPOINTS; ++i) {
        in >> points[i].x >> v >> points[i].y >> v;
    }

    int original_distance = total_distance(points);

    // detect intersection between any 4 points
    for (int i = 0; i < NPOINTS; ++i) {
        for (int j = i+1; j < NPOINTS; ++j) {
            Point & p1 = points[i];
            Point & p2 = points[(i+1)%NPOINTS];
            Point & p3 = points[j];
            Point & p4 = points[(j+1)%NPOINTS];

            // points must all be distinct
            if (p1.distance_to(p3) == 0 || p1.distance_to(p4) == 0 || p2.distance_to(p3) == 0 || p2.distance_to(p4) == 0) {
                continue;
            }

            // do they intersect ?
            if (!intersects(p1, p2, p3, p4)) {
                continue;
            }

            // can modify less than 25 points ?
            if (std::abs(j-i) > 25) {
                continue;
            }

            // swap points
            for (int m = 0; m < std::abs(j-i)/2; ++m) {
                if (i+1+m != j-m) {
                    std::swap(points[i+1+m], points[j-m]);
                    //std::cerr << "untangle " << i+1+m << " <=> " << j-m << '\n';
                }
            }

            int new_distance = total_distance(points);
            if (new_distance < original_distance) {
                std::copy(std::begin(points), std::end(points)-1, std::ostream_iterator<Point>(std::cout, ","));
                std::cout << points[NPOINTS-1];
                return 0;
            }
            else {
                // swap points back
                for (int m = 0; m < std::abs(j-i)/2; m++) {
                    if (i+1+m != j-m) {
                        std::swap(points[i+1+m], points[j-m]);
                    }
                }
            }
        }
    }

    // more traditional approach if the first fails
    std::mt19937 rng(std::chrono::duration_cast<std::chrono::seconds>(start_time.time_since_epoch()).count());
    std::uniform_int_distribution<> distr(0, NPOINTS-1);
    while (true) {
        // try all possible swaps from a random permutation
        int p1 = distr(rng);
        int p2 = distr(rng);
        std::swap(points[p1], points[p2]);

        for (int i = 0; i < NPOINTS; ++i) {
            for (int j = i+1; j < NPOINTS; ++j) {
                std::swap(points[i], points[j]);
                if (total_distance(points) < original_distance) {
                    std::copy(std::begin(points), std::end(points)-1, std::ostream_iterator<Point>(std::cout, ","));
                    std::cout << points[NPOINTS-1];
                    return 0;
                }
                else {
                    std::swap(points[i], points[j]);
                }
            }
        }

        // they didn't yield a shorter path, swap the points back and try again
        std::swap(points[p1], points[p2]);
    }
    return 0;
}

You beat me by 19 minutes!

This should have more upvotes, judging from today's results.

@Geobits I'm still surprised the simplest thing I came up with performs so well. Hoping more challenging contestants will enter !

@SirDarius Okay, fine. Have a bit of challenge.

SANNbot
(a simulated annealing bot in R)
Should be called with Rscript SANNbot.R.
input <- strsplit(commandArgs(TRUE),split=",")[[1]]
n <- as.integer(input[1])                            # Number of players
init_s <- s <- matrix(as.integer(input[-1]),ncol=2,byrow=TRUE) # Sequence of points
totdist <- function(s){                              # Distance function
    d <- 0
    for(i in 1:99){d <- d + (abs(s[i,1]-s[i+1,1])+abs(s[i,2]-s[i+1,2]))}
    d
    }
gr <- function(s){                                   # Permutation function
    changepoints <- sample(1:100,size=2, replace=FALSE)
    tmp <- s[changepoints[1],]
    s[changepoints[1],] <- s[changepoints[2],]
    s[changepoints[2],] <- tmp
    s
    }
d <- init_d <- totdist(s)                            # Initial distance
k <- 1                                               # Number of iterations
v <- 0
t <- n*(init_d/12000)                                 # Temperature
repeat{
    si <- gr(s)                                      # New sequence
    di <- totdist(si)                                # New distance
    dd <- di - d                                     # Difference of distances
    if(dd <= 0 | runif(1) < exp(-dd/t)){             # Allow small uphill changes
        d <- di
        s <- si
        v <- v+2
        }
    k <- k+1
    if(k > 10000){break}
    if(d > init_d & v>20){s <- init_s; d <- init_d; v <- 0}
    if(v>23){break}
}
cat(paste(apply(s,1,paste,collapse=","),collapse=","))

The idea is relatively simple: each turn is one "cooling step" of a simulated annealing with the number of players still in the game as "temperature" (modified by the current distance over 12000, i.e. roughly the initial distance). Only difference with a proper simulated annealing is that I checked that i don't permute more than 25 elements and if i used up 20 moves but the resulting sequence is worth than the initial then it start over again.

@Geobits ah sorry deleted the line where init_s was defined by accident (well "accident": i saw the line and thought "why is it here again?" and deleted it :) ). Corrected.

I tried your program using java Tourney "java Swapbot" "Rscript SANNbot.R" and it seemed to work.

Yea, it seems to be working now.

In theory (if I'm not completely mistaken) it should perform better when more players enter the game.

As-is, this program always goes out early due to "too many points changed" in my testing. If I bump the u check limits up, this doesn't happen (and it performs much better). While your code seems pretty straightforward, I don't know the quirks of R so I can't tell if the logic is wrong. (the latest version of the controller will give messages about why a bot goes out when running Game, so that might help pinpoint the problem)

well the u is the number of points which are at the exact same index as in the initial sequence (the one taken as input). Since my permutation function only switch two point at each iteration, it seemed to me that if i checked it was higher than 76 at the beginning of the iteration i was sure it wouldn't be lower than 75 at the end... I'll look into it...

Yea, that's the way it looks to me, too. I figured there was something I just wasn't seeing causing it.

still have no idea why it didn t work but now it seems not to fail because of that anymore (though it loses pretty consistently).

BozoBot
Utilizes the complex logic behind Bozosort to find a better path. It looks like this.

Swap random points
If we improved

Return the answer

Otherwise

Try again

BozoBot has now been improved with Multithreading! Four minions now aimlessly juggle points until they stumble upon an improvement. The first one to find a solution gets a cookie!
Apparently I fail at multithreading.
import java.util.Random;
public class BozoBot {
    public static String[] input;
    public static void main(String[] args) {
        input = args;
        for(int i = 0; i < 4; i++) new Minion().run();
    }
}

class Minion implements Runnable {
    public static boolean completed = false;
    public static synchronized void output(int[] x, int[] y) {
        if(!completed) {
            completed = true;
            String result = x[0]+","+y[0];
            for (int i = 1; i < 100; i++)
                result+=","+x[i]+","+y[i];
            System.out.print(result);
            // receiveCookie(); // Commented out to save money
        }
    }
    public void run() {
        String[] args = BozoBot.input[0].split(",");
        int[] x = new int[100];
        int[] y = new int[100];
        for (int i = 1; i < 201; i+=2) {
            x[(i-1)/2] = Integer.parseInt(args[i]);
            y[i/2] = Integer.parseInt(args[i+1]);
        }
        int startDistance = 0;
        for (int i = 1; i < 100; i++)
            startDistance += Math.abs(x[i-1]-x[i]) + Math.abs(y[i-1]-y[i]);
        int r1, r2, r3, r4, tX, tY, newDistance;
        Random gen = new java.util.Random();
        while (true) {
            r1 = gen.nextInt(100);
            r2 = gen.nextInt(100);
            r3 = gen.nextInt(100);
            r4 = gen.nextInt(100);
            tX = x[r1];
            x[r1] = x[r2];
            x[r2] = tX;
            tY = y[r1];
            y[r1] = y[r2];
            y[r2] = tY;
            tX = x[r3];
            x[r3] = x[r4];
            x[r4] = tX;
            tY = y[r3];
            y[r3] = y[r4];
            y[r4] = tY;
            newDistance = 0;
            for (int i=1; i < 100; i++)
                newDistance += Math.abs(x[i-1]-x[i]) + Math.abs(y[i-1]-y[i]);
            if(newDistance < startDistance)
                break;
            tX = x[r1];
            x[r1] = x[r2];
            x[r2] = tX;
            tY = y[r1];
            y[r1] = y[r2];
            y[r2] = tY;
            tX = x[r3];
            x[r3] = x[r4];
            x[r4] = tX;
            tY = y[r3];
            y[r3] = y[r4];
            y[r4] = tY;
        }
        output(x,y);
    }
}

Ehhmm... Shouldn't you put your minions into a thread instead of calling run()? AFAIK this isn't multithreading...

@Manu You caught me! I tried to learn it on my own and failed. Any pointers?

I think it should be new Thread(new Minion()).start()

@Manu Thanks. Apparently I only read half of this tutorial when I was coding.

TwoSwapBot
An upgrade to SwapBot, this guy checks for every pair of swaps. First, he checks if any single swap will shorten the path. If it does, it returns immediately. If not, he checks each to see if another swap will shorten it. If not, he just dies.
While the path is still semi-random, it normally returns in about 100ms. If he has to check each and every 2-swap (roughly 25M), it takes about 20 seconds.
At the time of submission, this beat all other competitors in test rounds.
public class TwoSwapBot {

    static int numPoints = 100;

    String run(String input){
        String[] tokens = input.split(",");
        if(tokens.length < numPoints*2)
            return "bad input? nope. no way. bye.";

        Point[] points = new Point[numPoints];
        for(int i=0;i<numPoints;i++)
            points[i] = new Point(Integer.valueOf(tokens[i*2+1]), Integer.valueOf(tokens[i*2+2]));
        int startDist = totalDistance(points);

        Point[][] swapped = new Point[(numPoints*(numPoints+1))/2][];
        int idx = 0;
        for(int i=0;i<numPoints;i++){
            for(int j=i+1;j<numPoints;j++){
                Point[] test = copyPoints(points);
                swapPoints(test,i,j);
                int testDist = totalDistance(test);
                if( testDist < startDist)
                    return getPathString(test);
                else
                    swapped[idx++] = test;
            }
        }

        for(int i=0;i<idx;i++){
            for(int k=0;k<numPoints;k++){
                for(int l=k+1;l<numPoints;l++){
                    swapPoints(swapped[i],k,l);
                    if(totalDistance(swapped[i]) < startDist)
                        return getPathString(swapped[i]);
                    swapPoints(swapped[i],k,l);
                }
            }
        }
        return "well damn";
    }

    void swapPoints(Point[] in, int a, int b){
        Point tmp = in[a];
        in[a] = in[b];
        in[b] = tmp;
    }

    String getPathString(Point[] in){
        String path = "";
        for(int i=0;i<numPoints;i++)
            path += in[i].x + "," + in[i].y + ",";
        return path.substring(0,path.length()-1);
    }

    Point[] copyPoints(Point[] in){
        Point[] out = new Point[in.length];
        for(int i=0;i<out.length;i++)
            out[i] = new Point(in[i].x, in[i].y);
        return out;
    }

    static int totalDistance(Point[] in){
        int dist = 0;
        for(int i=0;i<numPoints-1;i++)
            dist += in[i].distance(in[i+1]);
        return dist + in[numPoints-1].distance(in[0]);
    }

    public static void main(String[] args) {
        if(args.length < 1)
            return;
        System.out.print(new TwoSwapBot().run(args[0]));
    }

    class Point{
        final int x; final int y;
        Point(int x, int y){this.x = x; this.y = y;}
        int distance(Point other){return Math.abs(x-other.x) + Math.abs(y-other.y);}
    }
}

Threader
This bot

Splits the 100 points up in 410 pieces of 2510 points
Starts a thread for each piece
In the thread, randomly shuffle the array, while keeping the start- and endpoint fixed
If distance of new array is shorter, keep it
After 59s, the main thread collects the results and prints it out

The idea is to find the best improvement to the path, so that the other bots will fail with their logic.

import java.util.Arrays;
import java.util.Collections;

public class Threader {
    public static final int THREAD_COUNT = 10;
    public static final int DOT_COUNT = 100;
    private final Dot[] startDots = new Dot[THREAD_COUNT];
    private final Dot[] endDots = new Dot[THREAD_COUNT];
    private final Dot[][] middleDots = new Dot[THREAD_COUNT][DOT_COUNT/THREAD_COUNT-2];
    private final Worker worker[] = new Worker[THREAD_COUNT];
    private final static long TIME = 59000;

    public static void main(String[] args) {
        Threader threader = new Threader();
        //remove unnecessary player count to make calculation easier
        threader.letWorkersWork(args[0].replaceFirst("^[0-9]{1,3},", "").split(","));
    }

    public void letWorkersWork(String[] args) {
        readArgs(args);
        startWorkers();
        waitForWorkers();
        printOutput();
    }

    private void readArgs(String[] args) {
        final int magigNumber = DOT_COUNT*2/THREAD_COUNT;
        for (int i = 0; i < args.length; i += 2) {
            Dot dot = new Dot(Integer.parseInt(args[i]), Integer.parseInt(args[i + 1]));
            if (i % magigNumber == 0) {
                startDots[i / magigNumber] = dot;
            } else if (i % magigNumber == magigNumber - 2) {
                endDots[i / magigNumber] = dot;
            } else {
                middleDots[i / magigNumber][(i % magigNumber) / 2 - 1] = dot;
            }
        }
    }

    private void startWorkers() {
        for (int i = 0; i < THREAD_COUNT; i++) {
            worker[i] = new Worker(startDots[i], endDots[i], middleDots[i]);
            Thread thread = new Thread(worker[i]);
            thread.setDaemon(true);
            thread.start();
        }
    }

    private void waitForWorkers() {
        try {
            Thread.sleep(TIME);
        } catch (InterruptedException e) {
        }
    }

    private void printOutput() {
        //get results
        Worker.stopWriting = true;
        int workerOfTheYear = 0;
        int bestDiff = 0;
        for (int i = 0; i < THREAD_COUNT; i++) {
            if (worker[i].diff() > bestDiff) {
                bestDiff = worker[i].diff();
                workerOfTheYear = i;
            }
        }
        //build output
        StringBuilder result = new StringBuilder(1000);
        for (int i = 0; i < THREAD_COUNT; i++) {
            result.append(startDots[i]);
            Dot middle[] = middleDots[i];
            if (i == workerOfTheYear) {
                middle = worker[i].bestMiddle;
            }
            for (int j = 0; j < middle.length; j++) {
                result.append(middle[j]);
            }
            result.append(endDots[i]);
        }
        result.replace(0, 1, ""); //replace first comma
        System.out.print(result);
    }

}

class Worker implements Runnable {

    public Dot start;
    public Dot end;
    private Dot[] middle = new Dot[Threader.DOT_COUNT/Threader.THREAD_COUNT-2];
    public Dot[] bestMiddle = new Dot[Threader.DOT_COUNT/Threader.THREAD_COUNT-2];
    public static boolean stopWriting = false;
    private int bestDist = Integer.MAX_VALUE;
    private final int startDist;

    public Worker(Dot start, Dot end, Dot[] middle) {
        this.start = start;
        this.end = end;
        System.arraycopy(middle, 0, this.middle, 0, middle.length);
        System.arraycopy(middle, 0, this.bestMiddle, 0, middle.length);
        startDist = Dot.totalDist(start, middle, end);
    }

    @Override
    public void run() {
        while (true) {
            shuffleArray(middle);
            int newDist = Dot.totalDist(start, middle, end);
            if (!stopWriting && newDist < bestDist) {
                System.arraycopy(middle, 0, bestMiddle, 0, middle.length);
                bestDist = newDist;
            }
        }
    }

    public int diff() {
        return startDist - bestDist;
    }

    private void shuffleArray(Dot[] ar) {
        Collections.shuffle(Arrays.asList(ar));
    }

}

class Dot {

    public final int x;
    public final int y;

    public Dot(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int distTo(Dot other) {
        return Math.abs(x - other.x) + Math.abs(y - other.y);
    }

    public static int totalDist(Dot start, Dot[] dots, Dot end) {
        int distance = end.distTo(start);
        distance += start.distTo(dots[0]);
        distance += end.distTo(dots[dots.length - 1]);
        for (int i = 1; i < dots.length; i++) {
            distance += dots[i].distTo(dots[i - 1]);
        }
        return distance;
    }

    @Override
    public String toString() {
        return "," + x + "," + y;
    }
}

Note: I changed println to print to get rid of the newline at the end of your output. Otherwise it crashes out.

Changed println to print and made the thread-count dynamic. It now starts with 10 threads...

Divide And Conquer + Greedy Bot
NOTE: I looked at your code for Game which includes the following in Game.parsePath:
for(int i=0;i<numPoints;i++){
        test[i] = new Point(Integer.valueOf(tokens[i*2]), Integer.valueOf(tokens[i*2+1]));
        if(test[i].equals(currentPath[i]))
            same++;

However, there is no catch(NumberFormatException) block, so your program will likely crash when a player program outputs a string (as demonstrated at the end of my program's main method). I advise you fix this, because programs could output exceptions, stack traces, or the like. Otherwise, comment out that line in my program before you run it.
Back to the topic
This implementation (in Java) splits the list of points into chunks of 25, randomly spaced on the list. Then, it creates threads to shorten the path between the points in each chunk (Hence, "Divide and Conquer"). The main thread monitors the others and makes sure to present the shortest solution within the time limit. If a thread dies with or without a solution, it starts another thread off again on a different chunk.
Each thread uses the "greedy" algorithm, which starts off on a random point, goes to the closest point, and repeats until all the points are covered (Hence, "greedy").
Notes

This will run through the full 1 minute (I gave 3 seconds for program startup/shutdown and JVM startup - you never know what the JVM startup routines get caught up on next...)
Even if it has found solutions, it will keep searching and after the 1 minute is up it presents the best solution it found.
I'm not sure if this implementation is actually any good. I had some fun coding it though :)
Since a lot of things are random, this
may not give the same output for the same input.

Just compile and use java DivideAndConquer.class to run.
public class DivideAndConquer extends Thread {
    static LinkedList<Point> original;
    static Solution best;
    static LinkedList<DivideAndConquer> bots;
    static final Object _lock=new Object();

    public static void main(String[] args){
        if(args.length != 1) {
            System.err.println("Bad input!");
            System.exit(-1);
        }
        // make sure we don't sleep too long... get the start time
        long startTime = System.currentTimeMillis();
        // parse input
        String[] input=args[0].split(",");
        int numPlayers=Integer.parseInt(input[0]);
        original=new LinkedList<Point>();
        for(int i=1;i<input.length;i+=2){
            original.add(new Point(Integer.parseInt(input[i]), Integer.parseInt(input[i+1])));
        }
        // start threads
        bots=new LinkedList<DivideAndConquer>();
        for(int i=0;i<6;i++)
            bots.add(new DivideAndConquer(i));
        // sleep
        try {
            Thread.sleep(57000 - (System.currentTimeMillis() - startTime));
        } catch(Exception e){} // should never happen, so ignore
        // time to collect the results!
        Solution best=getBestSolution();
        if(best!=null){
            best.apply(original);
            String printStr="";
            for(int i=0;i<original.size();i++){
                Point printPoint=original.get(i);
                printStr+=printPoint.x+","+printPoint.y+",";
            }
            printStr=printStr.substring(0, printStr.length()-1);
            System.out.print(printStr);
        } else {
            System.out.println("Hey, I wonder if the tournament program crashes on NumberFormatExceptions... Anyway, we failed");
        }
    }

    // check the distance
    public static int calculateDistance(List<Point> points){
        int distance = 0;
        for(int i=0;i<points.size();i++){
            int next=i+1;
            if(next>=points.size())next=0;
            distance+=points.get(i).distance(points.get(next));
        }
        return distance;
    }

    public static void solutionFound(Solution s){
        // thanks to Java for having thread safety features built in
        synchronized(_lock){
            // thanks to Java again for short-circuit evaluation
            // saves lazy programmers lines of code all the time
            if(best==null || best.distDifference < s.distDifference){
                best=s;
            }
        }
    }

    public static Solution getBestSolution(){
        // make sure we don't accidentally return
        // the best Solution before it's even
        // done constructing
        synchronized(_lock){
            return best;
        }
    }

    List<Point> myPoints;
    int start;
    int length;
    int id;

    public DivideAndConquer(int id){
        super("DivideAndConquer-Processor-"+(id));
        this.id=id;
        myPoints=new LinkedList<Point>();
        start=(int) (Math.random()*75);
        length=25;
        for(int i=start;i<start+length;i++){
            myPoints.add(original.get(i));
        }
        start();
    }

    public void run(){
        // copy yet again so we can delete from it
        List<Point> copied=new LinkedList<Point>(myPoints);
        int originalDistance=calculateDistance(copied);
        // this is our solution list
        List<Point> solution=new LinkedList<Point>();
        int randomIdx=new Random().nextInt(copied.size());
        Point prev=copied.get(randomIdx);
        copied.remove(randomIdx);
        solution.add(prev);
        while(copied.size()>0){
           int idx=-1;
           int len = -1;
           for(int i=0;i<copied.size();i++){
               Point currentPoint=copied.get(i);
               int dist=prev.distance(currentPoint);
               if(len==-1 || dist<len){
                   len=dist;
                   idx=i;
               }
           }
           prev=copied.get(idx);
           copied.remove(idx);
           solution.add(prev);
        }
        // aaaand check our distance
        int finalDistance=calculateDistance(solution);
        if(finalDistance<originalDistance){
            // yes! solution
            Solution aSolution=new Solution(start, length, solution, originalDistance-finalDistance);
            solutionFound(aSolution);
        }
        // start over regardless
        bots.set(id, new DivideAndConquer(id));
    }

    // represents a solution
    static class Solution {
        int start;
        int length;
        int distDifference;
        List<Point> region;
        public Solution(int start, int length, List<Point> region, int distDifference){
            this.region=new LinkedList<Point>(region);
            this.start=start;
            this.length=length;
            this.distDifference=distDifference;
        }
        public void apply(List<Point> points){
            for(int i=0;i<length;i++){
                points.set(i+start, region.get(i));
            }
        }
    }

    // copied your Point class, sorry but it's useful...
    // just added public to each method for aesthetics
    static class Point{
        int x;
        int y;
        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
        Point(Point other){
            this.x = other.x;
            this.y = other.y;
        }
        public boolean equals(Point other){
            if(this.x==other.x && this.y==other.y)
                return true;
            return false;
        }

        public int distance(Point other){
            return Math.abs(x-other.x) + Math.abs(y-other.y);
        }
    }
}

Can you believe it? SX asked me for a captcha when I submitted this! Does this look bot-made to you? Seriously?

Fix for NFException pushed. It will now just kill the player instead of killing the program.

For the record, I don't think it would have crashed on your "Hey, I wonder if..." line anyway. It checks if there are <200 tokens before it tries parsing. Still better to check for it anyway.

@Geobits haha didn't realize that

Note: To get this to compile, I had to add a ) on line 19; change substr to substring on 38; initialize idx to something in the run() method.

Whoops I was going to test it (wrote this all on my mobile) but I never got around to it, sorry

Fixed the code, I'll try to get around to testing this today


text:
Play a perfect game of 2048
Your job is to simulate a mathematically perfect game of 2048. The idea is to find the theoretical upper limit of how far a 2048 game can go, and find how to get there.
To get an idea of what this looks like, play with this 2x2 clone and try to score 68 points. If you do, you will end up with a 2, 4, 8, and 16 tile. It's impossible to advance past that point.
Your task is made easier because you can choose where tiles spawn and what their values are, just like this clone.
You must write a program or function that accepts a 2048 board as input, and outputs the board with the spawned tile and the board after collapsing tiles. For example:
Input:
-------
0 0 0 0
0 0 0 0
0 0 0 0
0 0 8 8

Output:
-------
0 0 0 0
0 0 0 0
0 0 0 0
0 4 8 8

0 0 0 0
0 0 0 0
0 0 0 0
0 0 4 16

Your program will be repeatedly fed its own output to simulate an entire game of 2048. The first input of the program will be an empty board. You must spawn one tile on it, unlike the original game's two tiles. At the last step of the game, you will be unable to move, so your two output boards can be identical.
You must of course only output legal moves. Only a 2 or 4 can be spawned, you must move or collapse at least one tile on a move, etc.
I've purposely made the input and output requirements vague. You are free to choose the format of the input and output. You can use matrices, arrays, strings, or whatever you want. As long as you can simulate a 2048 game with them, your inputs and outputs are fine.
The winner will be the one who ends the game with the highest sum of tiles on the board, then by the lowest number of bytes in the source code. The scoring from the original game will not be taken into account. (Hint: use 4's)

@undergroundmonorail This is different from that question. This question allows spawning your own tiles, and is about going as far as mathematically possible, not just to 2048.

68 isn't a power of 2

@TheDoctor 68 is a sum of powers of 2, and is what your score would be if you get 2, 4, 8, 16.

Is this really a duplicate? What more would it take to make it different?

@KendallFrey See http://meta.codegolf.stackexchange.com/a/781/9498 and http://meta.codegolf.stackexchange.com/a/780/9498 . The answers from that question could be copied over here with a few modifications; all they would do is generate 2's in the corner and play the game using the code they already have.

@Quincunx That would really generate a suboptimal game though.

@KendallFrey The point still remains that the answers there can be almost copied here.

I found the heart of this challenge, "Find an optimal solution", to be unique, but admittedly it was a poor choice to enclose it in a duplicate "shell". This one screams, "Oh look, another 2048 Code Golf challenge." With close votes being so subjective, you really have to sell your challenge to the crowd. Sometimes that means generating your own terrible ripoff of 2048.

Is the program required to output a valid move if given an input board that is not in the sequence of its own output starting from a zero board?

@aschepler It's not required. It ideally would output a valid move in all situations, but I don't mind if you rely on it being passed its own output.

Ruby, Into the Corner, Score: 3340
Here is a very simple strategy to kick this off. I do have an idea for a (near) perfect score, but I'm having trouble formalising it, so here is something simple to get things going.
def slide board, dir
    case dir
    when 'U'
        i0 = 0
        i_stride = 1
        i_dist = 4
    when 'D'
        i0 = 15
        i_stride = -1
        i_dist = -4
    when 'L'
        i0 = 0
        i_stride = 4
        i_dist = 1
    when 'R'
        i0 = 15
        i_stride = -4
        i_dist = -1
    end

    4.times do |x|
        column = []
        top_merged = false
        4.times do |y|
            tile = board[i0 + x*i_stride + y*i_dist]
            next if tile == 0
            if top_merged || tile != column.last
                column.push tile
                top_merged = false
            else
                column[-1] *= 2
                top_merged = true
            end
        end

        4.times do |y|
            board[i0 + x*i_stride + y*i_dist] = column[y] || 0
        end
    end

    board
end

def advance board
    if board.reduce(:*) > 0
        return board, board
    end

    16.times do |i|
        if board[15-i] == 0
            board[15-i] = 4
            break
        end
    end

    spawned = board.clone

    # Attention, dirty dirty hand-tweaked edge cases to avoid
    # the inevitable for a bit longer. NSFS!
    if board[11] == 8 && (board[12..15] == [32, 16, 4, 4] ||
                          board[12..15] == [16, 16, 4, 4] && board[8..10] == [256,64,32]) ||
       board[11] == 16 && (board[12..15] == [32, 8, 4, 4] ||
                           board[12..15] == [4, 32, 8, 8] ||
                           board[12..15] == [4, 32, 0, 4])

        dir = 'R'
    elsif board[11] == 16 && board[12..15] == [4, 4, 32, 4] ||
          board[11] == 8 && board[12..15] == [0, 4, 32, 8]
        dir = 'U'
    else
        dir = (board.reduce(:+)/4).even? ? 'U' : 'L'
    end

    board = slide(board, dir)

    if board == spawned
        dir = dir == 'U' ? 'L' : 'U'
        board = slide(board, dir)
    end
    return spawned, board
end

The advance function is the one your asking for. It takes a board as 1d array and returns the board after the tile has been spawned and after the move has been made.
You can test it with this snippet
board = [0]*16
loop do
    spawned, board = advance(board)
    board.each_slice(4) {|row| puts row*' '}
    puts
    break if board[15] > 0
end

puts "Score: #{board.reduce :+}"

The strategy is very simple, and is the one I actually used to skip to the 128 when I was playing 2048 myself: just alternate between up and left. To make this work for as long as possible, new 4s are spawned in the bottom right corner.
EDIT: I've added a hard coded switch to go right a few times at specific steps just before the end, which actually lets me reach 1024. This is getting somewhat out of hand though, so I'll stop with this for now and think about a generally better approach tomorrow. (Honestly, the fact that I can increase my score by a factor of 4 by adding hand-tweaked hacks only tells me that my strategy is crap.)
This is the board you end up with
1024 512 256 128
 512 256 128  16
 256 128  64   8
   8  32   8   4

Just to nitpick, spawning 4's doesn't give you an optimal score because you're not gaining the 4 points each time one is created as opposed to being generated by 2 2's.

@BrunoJ The score for this challenge is simply computed as the total of all tiles at the end, not the score you'd have in the actual game. But if that was the case, you're right of course. ;) ... Although I think with my strategy it wouldn't make a difference, because I'd only get to 128 instead of 256 then.

Oh, didn't catch that the scoring isn't the same, my apologies

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Let the trigonometry begin!
Introduction:
The sine of \$x\$ is given by the formula:
$$\sin(x) = x - \frac {x^3}{3!} + \frac {x^5}{5!} - \frac {x^7}{7!} + \frac {x^9}{9!} - \frac {x^{11}}{11!} + \cdots$$
The cosine of \$x\$ is given by the formula:
$$\cos(x) = 1 - \frac {x^2}{2!} + \frac {x^4}{4!} - \frac {x^6}{6!} + \frac {x^8}{8!} - \frac {x^{10}}{10!} + \cdots$$
Task:
Given the value of \$x\$ and \$n\$, write a program (no functions, etc.) to output the value of \$\sin(x)\$ and \$\cos(x)\$ correct up to \$n\$ terms of the formula above. Assume that \$x\$ is in radians.
Input:
x n

A decimal number \$x\$ (with up to 3 decimal places) and an integer \$n\$. Input must be on stdin or a prompt dialog box (iff your language doesn't support stdin)
Output:
[sin(x)]
[cos(x)]

The value of both \$\sin(x)\$ and \$\cos(x)\$ should be rounded to 6 decimal places. If \$\sin(x)\$ is \$0.5588558855\$ (10 decimal digits), it should be rounded to \$0.558856\$ (6 decimal digits). The rounding must take place to the nearest, as described in the fifth column, "Round to nearest", of the the table in this Wiki article.
Constraints:
1 <= x <= 20
1 <= n <= 20

Samples:
----
5 3

10.208333
14.541667
----
8.555 13

0.765431
-0.641092
----
9.26 10

-3.154677
-8.404354
----
6.54 12

0.253986
0.967147
----
5 1

5.000000
1.000000
----
20 20

-5364.411846
-10898.499385
----

Notes:

Standard loopholes are prohibited.
Built-in math functions and operators of trigonometry (sin, cos, tan, etc.), factorial, and exponentiation cannot be used. You are free to use a built-in rounding function for estimating the result of computing \$\sin(x)\$ and \$\cos(x)\$ to the 6-th decimal digit.
No need to handle wrong inputs.
Only ASCII characters can be used in the program, not the Chinese Unicode ones that allow code compression.
Your program must terminate, and display the output, within 3 seconds of input.
Your answer must accompany the ungolfed code, along with the explanation of the code (compulsory if the code is not immediately obvious to programmers-not-familiar-with-your-language, especially GolfScript, J, etc.).
Please include a link to an online compiler where your program can be tested.

Scoring:
The answer with lowest code length in characters, including white space, tabs, etc.  wins! Winner would be declared on 21 May 2014.
EDIT: 21/05/14
Winner is aditsu using CJam language. Runner up follows jpjacobs with J language, and second runner up is primo with Perl language. Congrats all!

(Mod note: comments nuked. Please ping me for any lost information that you might want; looks like after my warning in advance, everything made its way into the question though.)

In the first paragraph, it should be "sine", not "sin"

Is "Round to nearest" still a requirement, or can we use any built-in rounding facilities? e.g. round towards zero?

Requiring the equivalent of a mod 2pi operation to make the inputs converge faster would be rather useful - it's one of many improvements that the real world uses when dealing with these functions. (actually mod pi and sign awareness).

@Charles Ok, thanks, fixing.

@DigitalTrauma if by Round to nearest, you mean to the nearest 6-th decimal digit, then yes, it is still a requirement.

@Floris I never knew this. Well, we can't do anything now, the rules have already changed much, and I don't want to keep changing them to further annoy the answerers. Thanks for the suggestion though!

You can generally avoid any concern with the use of Unicode Characters by measuring the score in Bytes rather then in Characters. Those require between 2 and 6 bytes per extended character (in UTF-8 - see http://stackoverflow.com/questions/775412/how-does-a-file-with-chinese-characters-know-how-many-bytes-to-use-per-character)

@lochok I choose scoring in characters because that would give a fair advantage (I suppose) to everyone. Consider this meta thread: the TI-BASIC program has 43 chars but just 22 bytes! It was from this thread that I decided to use chars for scoring, rather than bytes.

CJam - 42
rd:X;1_ri2*,1>{_2%2*(*/X*_}/;]2/z{:+6mO}/p

Try it online at http://cjam.aditsu.net
Explanation:
r reads a token from the input
d converts to double
:X assigns to the variable X
; pops the value from the stack
1 puts 1 on the stack (the first term)
_ duplicates the 1
r reads the next token (the n)
i converts to integer
2*,1>{...}/ is a kind of loop from 1 to 2*n - 1:
- 2* multiplies by 2
- , makes an array from 0 to (last value)-1
- 1> removes the first item of the array (0)
- {...}/ executes the block for each item in the array
_ duplicates the "loop variable" (let's call it k)
2%2*( converts from even/odd to -1/1:
- 2% is modulo 2 (-> 0/1)
- 2* multiplies by 2 (-> 0/2)
- ( decrements (-> -1/1)
* multiplies, thus changing the sign every second time
/ divides the term on the stack by k or -k; this is the "/k!" part of the calculation together with the sign change
X* multiplies by X; this is the "X^k" part of the calculation; we obtained the next term in the series
_ duplicates the term to be used for calculating the following term in the next iteration
; (after the loop) pops the last duplicated term
] collects the terms on the stack in an array
At this point we have an array [1 X -X^2/2! -X^3/3! X^4/4! X^5/5! ...] containing exactly all the terms we need for cos(x) and sin(x), interleaved
2/ splits this array into pairs
z transposes the matrix, resulting in the array with the terms for cos(x) and the array with the terms for sin(x), as "matrix rows"
{...}/ again executes the block for each array item (matrix row):
- :+ adds the elements of the matrix row together
- 6mO rounds to 6 decimals
At this point we have the desired cos(x) and sin(x) on the stack
p prints the representation of the last item on the stack (sin(x)) followed by a newline
At the end of the program, the remaining contents of the stack (cos(x)) are printed automatically.

+1 for introducing me to a language I've never heard of and will probably never use.

@Alex thanks, CJam is somewhat like GolfScript on steroids

I don't like changing rules after posting the question, but I have disallowed code-compression-allowing-Unicode characters, as I did not know Unicode characters could be used to compress code. Only ASCII characters can be used now. Please edit your post. Sorry for inconvenience.

@GaurangTandon I don't like that very much either. What else did you think Chinese characters could possibly be used for in this problem? Anyway, edited.

Perl - 72 bytes
$~=<>=~$"+$'*2;$_=1-$_*$`/$~--/$~*$`for($,,$;)x$';printf'%f
%f',$`*$,,$;

Or, counting command line options as 1 byte each, in 70 bytes:
#!perl -n
$-=/ /+$'*2;$_=1-$_*$`/$---/$-*$`for($,,$;)x$';printf'%f
%f',$`*$,,$;

Or, if you'll allow me Perl 5.8, in 63 bytes:
#!perl -p
$.+=$'<</ /;$_=1-$_*$`/$.--/$.*$`for($_=$#='%f
',$\)x$';$_*=$`

but why would you.
Edit: Compliance with the new rules. %f rounds to 6 places by default, how convenient!

Algorithm
Examining the Taylor series for sin(x):

it can be seen that each term evenly divides every successive term. Because of this, it can be transformed rather effortlessly into a nested expression:

cos(x) transforms similarly, without the leading x, and denominator terms one smaller.
Additionally, this nested expression can be reformulated as a reverse recursive expression:

with s∞ = 0 and sin(x) = x·s1, which is ultimately what is used.

Ungolfed
<> =~ m/ /;          # read one line from stdin, match a space
                     # prematch ($`) is now x, postmatch ($') is now n
($x, $n) = ($`, $'); # reassign, for clarity
$i = 2*$n + 1;       # counting variable (denominators)

for (($s, $c)x$n) {  # iterate over $s and $c, n times each
  # compute the next term of the recursive expression
  # note: inside this loop $_ is not the _value_
  # of $s and $c alternately, it _is_ $s and $c

  $_ = 1 - $_ * $x**2 / $i-- / $i;
}

# formated output
printf("%f\n%f", $x*$s, $c);

Sample Usage
$ echo 5 3 | perl sin-cos.pl
10.208333
14.541667

$ echo 8.555 13 | perl sin-cos.pl
0.765431
-0.641092

$ echo 9.26 10 | perl sin-cos.pl
-3.154677
-8.404354

$ echo 6.54 12 | perl sin-cos.pl
0.253986
0.967147

$ echo 5 1 | perl sin-cos.pl
5.000000
1.000000

$ echo 20 20 | perl sin-cos.pl
-5364.411846
-10898.499385

If you want to test this online, I recommend using compileonline.com. Copy-Paste the code into main.pl, and the input into the STDIN box, then Execute Script.

What a devious way to parse the input... can I use that in my solution? :)

@Tal Feel free.

I think perl (and especially your code) counts as "not immediately obvious to programmers-not-familiar-with-your-language"

@aditsu Agreed. I'll add some cleaner code, and an explanation of the algorithm.

I have two questions: 1) Why would I not allow Perl 5.8? Any special reason? 2) What is the #!perl -p and #!perl -n doing there and why doesn't it count in character count ?

Perl 5.8 has been out of use for about ten years. 2) Those are 'shebang' lines, mainly for convenience. The scripts could be run without them, by invoking each as perl -n sin-cos.pl and perl -p sin-cos.pl respectively. Typically, each such command line option is counted as one byte (-na would be counted as 2, -naF as 3, etc.).

@primo Ok, thanks for the input :)

This answer really was extremely educational!

Python 3 (102) / Python 2 (104)
Python 3 (102)
x,n=map(float,input().split())
k=2*n
t=1
while k>1:k-=1;t=1+t*1j*x/k
print('%.6f\n'*2%(t.imag,t.real))

Python 2.7 (104)
x,n=map(float,raw_input().split())
k=2*n
t=1
while k>1:k-=1;t=1+t*1j*x/k
print'%.6f\n'*2%(t.imag,t.real)

Basically the same code. We save two characters from not needing parens for print but lose four from needing raw_input.
Sample run
You can run these here.
>>>
20 20
-5364.411846
-10898.499385

Code explanation
The main idea is to compute 2*n terms of e^(ix), and then take the imaginary and real part to get the sin and cos values approximated to n terms. We use the truncation of the Taylor series:
e^(ix)≈sum_{k=0}^{2n-1} (i*x)^k/k!

This is polynomial in i*x, but rather than compute its value by summing each term, we use  a modified Horner's Method to compute the sequence (defined recursively in reverse)
t_{2n} = 1
t_k = 1 + t_{k+1}*i*x/k,

which gives t_1 equaling the desired value.
Python string formatting operations are used to get the values to display rounded up to 6 decimal digits.
Edit: Changed to round to 6 digits as per new rules. No other changes were needed.

Try ideone for an online py3 interpreter :)

@BritishColour Thanks! I've added it to the post.

Please update your answer. See details in question. Thanks.

J 98 70 69 58
Though this can probably be shortened quite a bit using more fancy functions ... comments are welcome:
exit echo 0j6":,.-/(($%&(*/)1+i.@[)"0~i.@,&_2)/".}:stdin''

note 2: input ends when receiving EOF (ctrl-D in linux).
Edit: join exponentiation and factorial into a nicer, more J-ish whole: ($ %&(*/) >:@i.@[ ). This boils down to take an array of x replications of y and an array of the numbers from 1 to y. Multiply each and divide the result. This gets rid of the duplicate */.
Thanks to algortihmshark, another 7 characters off.
Eliminated cut for getting rid of the trailing newline.
Longer version, for which knowing about forks is a must.
NB. recursive Factorial
f=: */@>:@i.      NB. multiply all from 1 to n
NB. Exponential
e=: */@$          NB. replicate y x times, take the product.
NB. the x t y is the Nth (general) term without sign of the joint series
t=: (e % f@[)"0  NB. pretty straight forward: divide by (x!) on the exponential

NB. Piece the parts together, from right to left:
NB. read from stdin, cut the linefeed off , make the 2 n terms in 2 columns, which
NB. effectively splits out pair and odd terms, put in the minuses, put in rows
NB. instead of columns, echo, exit
exit echo 0j6&": ,. (-/) (i.@(,&_2)@{: t {.) , (". ;. _2) stdin''

There is no online J interpreter, but it's open source since a few years; installation is easy with these instructions:
http://www.jsoftware.com/jwiki/System/Installation/J801
On #jsoftware on irc.freenode.org, there is a J bot too.
stdin works only when ran from a file, from the commandline, else replace stdin '' with 'a b;' where a and b are the numbers that would have been passed on the commandline.

I love that it starts with exit

Please update your answer. See details in question. Thanks.

Updated for the 6 decimal places. If there's something else, please specify. Thanks

You can remove the & from 0j6&": to save a char. Also, (i.@(,&_2)@{:($%&(*/)>:@i.@[)"0{.) can be rewritten (($%&(*/)1+i.@[)"0~i.@,&_2)/ for another 6.

This tasks screams for T. (approximate function by n-term Taylor series), but I think that's verboten as a standard loophole.

The best I could do with T. was exit echo 0j6":(1 f,:2 f=.1 :'(m&o.)T.(+:{:y){.y')".}:stdin'', @FUZxxl. I'm sure it can be shortened, but I was surprised that beating 58 characters using T. wasn't straightforward.

Using T. is circular reasoning I think. You actually use the thing you are trying to approximate, so you might as well use o. all the way :P

Perl, 120 108 104 89 85
<>=~/ /;$c=$t=1;for(1..2*$'-1){$t*=$`/$_;$_%2?$s:$c+=$_&2?-$t:$t}printf"%f\n"x2,$s,$c

Ungolfed:
<> =~ / /;
$cosine = $t = 1;
for (1.. 2*$' - 1){
  $t *= $` / $_;
  ($_%2 ? $sine : $cosine) += $_&2?-$t:$t
}
printf "%.6f\n" x2, $sine, $cosine

The first line reads the input and uses regex to find a space; this automatically puts the value before the space in $` and the value after it in $'.
Now we loop from 1 to 2*n-1. $t is our term, which the loop repeatedly multiplies by x and divides by the loop's index ($_). The loop starts at 1 rather than 0 because the cosine is initialized to 1, which saved me having to deal with dividing by zero.
After updating $t, the trinary operator returns either $sine or $cosine, depending on whether the index is odd or even, and adds $t's value to it. The magic formula $_&2?-$t:$t figures whether to add or subtract this value (basically using a bitwise-and on the index and 2 to generate the repeating sequence of "add, add, subtract, subtract").
You can test-run this code at compileonline.com.

Please correct your output for 20 20.

I think your for loop may need to go from 1..$n*2-1, instead of 1..$n. While I'm here... $s is perfectly fine left uninitialized, as undef evaluates to 0 in a numeric context. Ternary assignment doesn't need parentheses: $_&1?$s:$c+=$t. "%.8f\n%.8f" can be shortened to "%.8f\n"x2, at the consequence of adding a trailing newline.

@Primo Thanks, I didn't know about some of those. And now it even produces the correct result as well.

@Tal My pleasure. Also, slightly better magic: $t*(1-($_&2)) => $_&2?-$t:$t.

Please update your answer. See details in question. Thanks.

@GaurangTandon I hope this is now adequate.

@Tal Yep, it's perfect!

Fortran: 89 109 125 102 101 98 bytes
complex*16::t=1;read*,x,n;do k=2*n-1,1,-1;t=1+t*(0,1)*x/k;enddo;print'(f0.6)',aimag(t),real(t);end

I abuse implicit typing, but unfortunately no such implicit complex type exists, so I had to specify that & the complex i. Gfortran cuts output at 8 decimal places naturally, so we're good on that spec. Unfortunately, my original method of output, print*,t, did not meet specs so I had to add 16 characters to output the imaginary and real components & hit the required 8 decimal places.
Thanks to Ventero, I managed to save 23 bytes between output and the loop. And another character to get correct answers and formatted output. And 3 more on the read statement.
Ungolfed,
complex*16::t=1
read*,x,n
do k=2*n-1,1,-1
   t=1+t*(0,1)*x/k
enddo
print'(f0.6)',aimag(t),real(t)
end

Please update your answer. See details in question. Thanks!

@GaurangTandon: You probably should stop changing the details of the problem.

I know, and I don't want to, but I can't help it. Actually, after testing 5 answers, it turned out that almost all of them were giving different results (this was indeed completely unsuspected). I could have followed some other approach, but that would have requried the complete change of the algorithms of the current answers. This one is the best I could figure out.

Well I know that mine works perfectly, so I should totally get the check :D ;)

C, 120
double s,c,r,x;main(i,n){for(scanf("%lf %d",&x,&n),r=1;i<n*2;s+=r,r*=-x/i++)c+=r,r*=x/i++;printf("%.8lf\n%.8lf\n",s,c);}

To save a byte, the statements that update the sine value are placed inside the for() statement, but are actually executed after the statements following the closing parenthesis that update the cosine value. (I guess I could also save a couple more bytes by removing the final newline character in the program's output.)
The global variables s, c, r and x are implicitly initialized to zero, and i will have a value of 1 as long as there are no arguments provided on the command line. Unfortunately printf() defaults to 6 places of decimals, so the output format is a bit verbose.
Ungolfed:
Here's the code with a bit of rearrangement to make the order in which things are done a bit clearer:
double s,c,r,x;
main(i,n) {
    scanf("%lf %d",&x,&n);
    r=1;
    for(;i<n*2;) {
        c+=r;
        r*=x/i++;
        s+=r;
        r*=-x/i++;
    }
    printf("%.8lf\n%.8lf\n",s,c);
}

Sample output:
$ echo 1.23 4 | ./sincos
0.94247129
0.33410995

Try it online:
http://ideone.com/URZWwo

Python >=2.7.3, 186 184 211 200 182 170 characters
Kinda simple as hell. Uses formula from the question parameterized for sine and cosine.
Online interpreter can be found here here

x,n=map(eval,raw_input().split())
f=lambda n:n<2and 1or n*f(n-1.)
for i in[1,0]:print"%.6f"%sum((1-j%2*2)*reduce(lambda o,p:o*p,[x]*(i+2*j),1)/f(i+2*j)for j in range(n))

Edit: Valid version with all the restrictions
Edit2: Changed online interpreter to ideone.com because of invalid round function output in Python 2.7.1
Edit3: Turned out that I used unnecessary inline lambda + changed rounding to string format (stolen from xnor :) )
Edit4: Replaced join with not functional main for loop

Hello avail, I have recently edited the rules which now do not allow the built-in operators for exponentiation (that is what the ** is doing I suppose). So, I think you will have to edit your answer. Sorry for inconvenience. Please correct me if I am wrong.

I guess further modifications are useless with xnor's answer :)

@avail On 20 20, I get output -5364.4118142500001. Might want to fix it to 8 decimals.

It is because of repl.it Python version 2.7.1. If you run it on ideone.com (Python 2.7.3) it works properly. http://ideone.com/JsYNNK

It works nice now! +1

GNU bc, driven by bash, 128 bytes
Far too many bytes spent setting decimal places and to-nearest rounding.  Oh well, here it is anyway:
bc -l<<<"m=1000000
w=s=$1
c=1
for(p=2;p/2<$2;s+=w){w*=-1*$1/p++
c+=w
w*=$1/p++}
s+=((s>0)-.5)/m
c+=((c>0)-.5)/m
scale=6
s/1
c/1"

Output:

$ ./trig.sh 5 3
10.208333
14.541667
$ ./trig.sh 8.555 13
.765431
-.641092
$ ./trig.sh 9.26 10
-3.154677
-8.404354
$ ./trig.sh 6.54 12
.253986
.967147
$ ./trig.sh 5 1
5.000000
1.000000
$ ./trig.sh 20 20
-5364.411846
-10898.499385
$

Linux command-line tools, 97 unicode characters
Unicode hack answer removed at OP's request.  Look at the edit history if you interested.

I don't like changing rules after posting the question, but I have disallowed code-compression-allowing-Unicode characters, as I did not know Unicode characters could be used to compress code. Only ASCII characters can be used now. Please edit your post. Sorry for inconvenience

@GaurangTandon Its not really compression - the unicode version actually takes more bytes (but less characters).  But I agree with your sentiment - I actually prefer scoring to strictly be done using byte count, but couldn't resist the bit about Chinese characters in your OP.

You use illegal exponential operator

@avall Oops.  That cost me 4 bytes.

JavaScript - 114 chars
y=(z=prompt)().split(' ');for(x=l=s=+y[0],c=d=1;--y[1];c+=l*=-x/++d,s+=l*=x/++d);z(s.toFixed(6)+'\n'+c.toFixed(6))

Based on james' great answer. Same algorithm, first step avoided with initialization of c=1 and s=x. Using 2 vars instead of an array for output simplifies the loop.
Ungolfed
y = ( z = prompt)().split(' ');
for (
    x = l = s = +y[0], /* init to value x, note the plus sign to convert from string to number */
    c = d = 1;
    --y[1]; /* No loop variable, just decrement counter */
    c += (l *= -x / ++d), /* Change sign of multiplier on each loop */
    s += (l *= x / ++d)
); /* for body is empty */
z(s.toFixed(6) + '\n' + c.toFixed(6))

Minor typo: It would be s += (l *= x / ++d) and not s += (l* = x / ++d) in the ungolfed code.

@GaurangTandon fixed

JavaScript (ECMAScript 6 Draft) - 97 96 Characters
A recursive solution:
f=(x,n,m=1,i=0,s=x,c=1)=>i<2*n?f(x,n,m*=-x*x/++i/++i,i,s+m*x/++i,c+m):[s,c].map(x=>x.toFixed(8))

Output:
f(0.3,1)
["0.29550000", "0.95500000"]

f(0.3,24)
["0.29552021", "0.95533649"]

That doesn't meet the spec regarding rounding though.

@m.buettner fixed

It doesn't meet input format and no functions requirement.

Please update your answer. See details in question. Thanks.

C,114
Insufficient reputation to comment, but further to Squeamish Offisrage's C answer, 7 byte reduction by using float for double and removing spaces, and combining declaration and init of 'r' gives
float s,c,r=1,x;main(i,n){for(scanf("%f%d",&x,&n);i<n*2;s+=r,r*=-x/i++)c+=r,r*=x/i++;printf("%.8f\n%.8f\n",s,c);}

try here.

Welcome to programming puzzles and code golf. Well done for acknowledging that your answer is a minor improvement on @squeamishossifrage's (I still managed to spell it wrong in my edit.) Best not to refer to the answer "above" because the order changes every time there is an edit. BTW, I noticed the initialization of r in the declaration. I haven't tested to see if float gives the required precision.

@steveverrill Neither did I think float would give the required precision, but it does work :) And welcome to PPCG, user2702245 !

Is it just me thats getting the wrong answers with float variables then? For x=5 and n=3, I get sin(x)=10.20833206 and cos(x)=14.54166412 :-(  (Intel Core Duo, in case you were wondering)

Would you like me to convert this to a comment on said answer?

@Doorknob May as well leave it now :-)

@Doorknob Convert it into comment, it would be better, I feel
At others, Thanks for the welcome.. I understand I have to change my display name ASAP :D The alphanumeric ID looks real pain to type/read.

Please update your answer. See details in question. Thanks

JavaScript (ES6) - 185 chars
i=(h,n)=>n?h*i(h,n-1):1;q=x=>x?x*q(x-1):1;p=(a,j,n)=>{for(c=b=0,e=1;c++<n;j+=2,e=-e)b+=e*i(a,j)/q(j);return b.toFixed(6)}
_=(y=prompt)().split(" ");y(p(_[0],1,_[1])+"\n"+p(_[0],0,_[1]))

Uses a function q for factorial, i for exponentiation, and p for performing both sin and cos. Run at jsbin.com.
Uses exactly the formula without any modification.
EDIT: Changed 8 decimal places to 6 decimal places. 15/May/14
Ungolfed Code:
/*Note that `name=args=>function_body` is the same as `function name(args){function_body} */

// factorial
function fact(x) {
    return x > 1 ? x * fact(x - 1) : 1
}

// Exponentiation
function expo(number, power){
    return power > 0 ? number * expo(number, power - 1) : 1;
}

function sin_and_cos(number, starter, terms) {
    for (count = sum = 0, negater = 1;
            count++ < terms;
            starter += 2, negater = -negater)

        sum += (negater * expo(number, starter)) / fact(starter);

    // to 6-decimal places
    return sum.toFixed(6);
}

input = (out = prompt)().split(" ");

out(sin_and_cos(input[0], 1,input[1])
        + "\n" +
        sin_and_cos(input[0], 0, input[1]));

Ruby, 336
Probably the longest one here, but I'm sure it could be made shorter :(
def f(n)
n==0 ? 1: 1.upto(n).inject(:*)
end
def p(x,y)
i=1
return 1 if y==0
y.times {i *= x}
i
end
def s(x,n)
a = 0.0
for k in 0...n
a += p(-1,k) * p(x.to_f, 1+2*k)/f(1+2*k)
end
a.round(8)
end
def c(x,n)
a= 0.0
for k in 0...n
a +=p(-1,k) * p(x.to_f, 2*k)/f(2*k)
end
a.round(8)
end
x = gets.chomp
n = gets.chomp.to_i
puts s(x,n), c(x,n)

JavaScript - 133 chars
y=(z=prompt)().split(" "),s=[0,0],l=1;for(i=0;i<y[1]*2;i++){s[i%2]+=i%4>1?-1*l:l;l*=y[0]/(i+1)}z(s[1].toFixed(6));z(s[0].toFixed(6));

Ungolfed
var y = prompt().split(" ");

var out = [0,0]; // out[1] is sin(x), out[0] is cos(x)
var l = 1; // keep track of last term in series
for (var i=0; i < y[1] * 2; i++) {
    out[i % 2] += (i % 4 > 1) ? -1 * l : l;
    l *= y[0] / (i + 1);
}

prompt(out[1].toFixed(6));
prompt(out[0].toFixed(6));

Input has to be two space-separated integers, not in two different dialog boxes. Please fix that.

@GaurangTandon fixed - thanks for pointing it out

Mathematica, 96 chars
{{x,n}}=ImportString[InputString[],"Table"];Column@{Im@#,Re@#}&@Fold[1+I#x/#2&,1,2n-Range[2n-1]]

How is the input format, seems x,n to me ?

@GaurangTandon It is x n.

Ok, thanks for clarifying.

Ruby - 160 152 140 Chars
Using recursion and the fact that for this recursive implementation sin(x, 2n + 1) = 1 + cos(x, 2n - 1), being sin(x, n) and cos(x, n) the series defined above for cos x and sin x.
p=->x,n{n<1?1:x*p[x,n-1]}
f=->n{n<2?1:n*f[n-1]}
c=->x,n{n<1?1:p[x,n]/f[n]-c[x,n-2]}
x,n=gets.split.map &:to_f
n*=2
puts c[x,n-1]+1,c[x,n-2]

Edit: Contributed by commenters (read below).

You can save a lot of characters by using lambdas: p=->x,n{...}, f=->n{...} and so on, and then use square brackets instead of parentheses to call them, like p[x,n-1]. Also, I think collect is just an alias for map, which is much shorter, and since you're only mapping a member call, you can shorten that to gets.split.map &:to_f.

@MartinBüttner Thanks! Will add this! (hope your comment here stated that this solution is not only mine, but collab)
To be honest: I'm also new to ruby (2 month only) :)))

APL(NARS), 109 chars
r←a F w;d;v;m;p
r←d←1+(2≠↑a)×w-1⋄m←w×w×¯1⋄p←2⊃a⋄v←0 1-2=↑a
→0×⍳0≥p-←1⋄r+←d×←m÷×/v+←2⋄→2

⍪{6⍕⍵a[2]F 1⊃a}¨⍳2⊣a←⎕

15+42+28+2+22=109
the last line call the function F that is a sin and cos function depend of first input on the left
(it is ≠2 is sin input =2 is cos). Some test:
      ⍪{6⍕⍵a[2]F 1⊃a}¨⍳2⊣a←⎕
⎕:
      5 3
  10.208333
  14.541667
      ⍪{6⍕⍵a[2]F 1⊃a}¨⍳2⊣a←⎕
⎕:
      8.555 13
  0.765431
  ¯0.641092
      ⍪{6⍕⍵a[2]F 1⊃a}¨⍳2⊣a←⎕
⎕:
      9.26 10
  ¯3.154677
  ¯8.404354

OT it would be possible to calculate the exact answer using rationals and input rational for example of 1r4 (0.25=1/4)
      ⍪{6⍕⍵a[2]F 1⊃a}¨⍳2⊣a←⎕
⎕:
      1r4 10
  0.247404
  0.968912
      {⍵○1r4}¨⍳2
  0.2474039593 0.9689124217
      {⍵○0.25}¨⍳2
  0.2474039593 0.9689124217
      1 10 F 1r4
  8264318085745811128158727r33404146443928530321408000
      2 10 F 1r4
  17051609536099989115458551r17598710837038136237752320

these last 2 numbers both cut would be the decimals 0.2474039592 and 0.9689124217

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Pathological Sorting
Pathological Sorting
Your boss has demanded that you develop a sorting algorithm to improve the performance of your company's application. However, having written the application, you know that you're unlikely to be able to make it significantly faster. Not wanting to disappoint your boss, you've decided to develop a new algorithm that works even better than *sort on certain sets of data. Of course, you can't make it obvious that the algorithm only works on some cases, so you want to make it obscure as possible.
The objective of this contest is to write a sorting routine in the language of your choice that performs better on certain sets of data than others, with repeatable results. The more specific the classification that determines speed, the better. The algorithm must do sorting of some kind, so an algorithm that depends on the data already being completely sorted (as in, an algorithm that does nothing), or an algorithm that depends on the data being completely sorted in reverse, are both invalid. The sorting algorithm must correctly sort any set of data.
After presenting your routine, please include an explanation of why it only works on certain sets of data, and include test runs on at least one set of good (fast) data and one set of bad (slow) data. The point here is to be able to prove to your boss that you've stumbled upon a better way to sort, so more test data is better. Of course, you're only going to show your boss the test results from the good data, so the flaw in the required testing data can't be too obvious. If applicable to your language, please show that your algorithm is faster than your language's built-in sorting algorithm.
For example, one might submit an insertion sort algorithm, with the good data being data that is already nearly sorted, and bad data being completely random data, since insertion sort approaches O(n) on nearly-sorted data. However, this isn't very good, since my boss would probably notice that all of the testing data is nearly sorted to begin with.
This is a popularity-contest, so the answer with the most votes after 7 days (May 21) wins.
If no one beats me to it, I'd like to submit a community wiki answer that takes advantage of uniformly distributed data sets.

Possibly useful/interesting resource for those approaching this question: "Psychic Sorting Algorithms" (Disclaimer: the author of that article and I are very close. :-P)

It's been a pretty long time, but I remember back in Algorithms 101 we were taught some sorting algorithm that used randomization. I wasn't a very good student so I don't really remember how it went or why it worked quickly on average.
Nevertheless, I've decided that this problem calls for a solution that uses randomization, which will hopefully work in my favor on average.
import random

def arrayIsSorted (arr) :
    for i in range(len(arr)-1) :
        if arr[i]>arr[i+1] : return False
    return True

def rSort (arr) :
    random.seed (42)
    counter = 0
    while not arrayIsSorted(arr) :
        random.shuffle (arr)
        counter+=1
    print ("Sorted in %d iterations." % counter)
    return arr

Since true randomization is important, I make sure to seed the RNG with the answer to Life, the Universe and Everything. After a bit of testing it turns out that that was a smart move! Check out how fast these 2 completely arbitrary lists get sorted:
rSort ([6,1,4,2,3,7,5])
rSort ([8,9,6,1,4,7,2,3,5])

Both of these get sorted in only 1 iteration - you couldn't possibly ask for a faster function than that!
Now, admittedly, some other lists produce slightly worse results...
rSort ([5,1,4,2,3,7,6])
rSort ([8,9,6,1,4,7,2,5,3])

These get sorted in 4,176 and 94,523 iterations respectively, which actually takes more than a second... but let's just keep that fact to ourselves so as not to distract anyone from how amazing this algorithm is!
Edit:
I've been asked to prove my algorithm's efficiency on a list of 100 items, so here you go:
rSort ([70, 6, 52, 97, 85, 61, 62, 48, 30, 3, 11, 88, 39, 91, 98, 8, 54, 92, 44, 65, 69, 21, 58, 41, 60, 76, 27, 82, 93, 81, 20, 94, 22, 29, 49, 95, 40, 19, 55, 42, 43, 1, 0, 67, 35, 15, 51, 31, 16, 25, 5, 53, 37, 74, 86, 12, 13, 72, 56, 32, 47, 46, 59, 33, 80, 4, 45, 63, 57, 89, 7, 77, 14, 10, 34, 87, 18, 79, 9, 66, 24, 99, 64, 26, 78, 38, 90, 28, 83, 75, 68, 2, 17, 73, 96, 71, 23, 84, 36, 50])

Even this long and completely arbitrary list gets sorted instantly! Truly I must have stumbled upon the best sorting algorithm in the world!

Can we get some test results on slightly larger datasets? Maybe one with 100 elements? ;)

@Geobits No problem, here it is :)

I just can't upvote: "The sorting algorithm must correctly sort any set of data." This just.... doesn't sort.

@Geobits Yes it does. Eventually.

It's a stretch, but it could be argued that it uses bogosort, which will eventually sort the array, given enough time. I'm willing to bet that 'shuffle and repeat' qualifies as asorting, albeit not good sorting.

If it was true random shuffles, maybe. PRNGs have a cycle, so I can't see how you could guarantee all permutations are tried.

@Geobits I can easily make it use true randomization with a predictable start if you want...

@Tal That would be interesting. Is that even possible?

@Mahesh Sounds possible to me. Just take a proper RNG, and on every iteration use something like the system clock to randomize your seed... but still start with 42 like I did so you know what the first iteration is.

@Tal I still wouldn't call it true randomization, but I get your point. Thanks. :)

You could use a permutation generator instead of a random shuffle, and choose a random index into the list of permutations.

If you can create your own data, then it's pretty straightforward - get data that looks random, but includes a key for faster sorting. All other data uses the original sorting method, so the average times are better.
One easy way is to make sure each data item has a unique key, and then just hash the keys. Take for example a list with the numbers from 1-10,000, all multiplied by 16, and with a random number from 0-15 added to it (see fillArray() below). They will look random, but each one has a unique sequential key. For sorting, divide by 16 (in C the >>4 is very fast) and then just place the number into an array using the resulting key as the index. One pass and you're done. In testing, I found quicksort was 30 times slower on ten million numbers.
void fillArray(int *a,int len)
{
  for (int i=0;i<len;++i)
    a[i]=(i<<4)|(rand()&0xF);
  // shuffle later
}
void sortArray(int *a,int len)
{
  int key=0;
  int *r=new int[len];
  for (int i=0;i<len;++i)
  {
    key=a[i]>>4;
    r[key]=a[i];
  }
  memcpy(a,r,len*sizeof(int));
  delete[] r;
}
void shuffleArray(int *a,int len)
{
  int swap=0, k=0;
  for (int i=0;i<len;++i)
  {
    k=rand()%len;
    swap=a[k];
    a[k]=a[i];
    a[i]=swap;
  }
}
int qCompare(const void*a,const void*b)
{
  int result=*((int*)a)-*((int*)b);
  return result;
}
void main()
{
  int aLen=10000;
  int *a=new int[aLen];
  srand (time(NULL));
  fillArray(a,aLen);
  // time them
  long t0=0, d0=0, d1=0;
  // qsort
  shuffleArray(a,aLen);
  t0=::GetTickCount();
  qsort(a,aLen,sizeof(int),&qCompare);
  d0=::GetTickCount()-t0;
  // oursort
  shuffleArray(a,aLen);
  t0=::GetTickCount();
  sortArray(a,aLen);
  d1=::GetTickCount()-t0;
  delete[] a;
}

Anything that has a unique key can be sorted this way - if you have the memory to store it, of course. For example, many databases use a unique numeric customer id - if the list is small/sequential enough this could be held in memory. Or some other way to translate a record into a unique number. For more info, research Hash Sorts, since that's what this is...


text:
Optimally solve the Flux Puzzle
Flux is very similar to the Fifteen Puzzle.
However, instead of numbers, the squares are colors.

There are 4 colors: Red, Yellow, Blue, and Gray.

There are exactly 4 red squares, 4 yellow squares, 2 blue squares, 1 gray square, and 1 empty square.

The grid has 3 rows and 4 columns
A grid configuration is solved when the top row is exactly the same as the bottom row.
The middle row is not relevant when considering whether the board is solved.
You do not have to handle invalid input. Trust that there will be the correct number of each of the input symbols.

Input

You must accept an input of twelve of these characters that use these symbols to represent a square on the board:

RYGB_

These input characters must be interpreted to go across, then down.
It is your choice whether you require some other character (newline, EOF, whatever) to terminate input, or just go as soon as you've received 12 characters.

Example:
YRGYB_BRRYYR

which corresponds to to the board:
YRGY
B_BR
RYYR

Output

You must output the moves required for an OPTIMAL solution
These will use the characters LRUD for Left, Right, Up, Down. This is considered to be the "piece moves to the left", not the "emptiness moves to the left"

Example:
LURDRDLULDLU

And then print out the resulting board. For the example we've used so far:
RBYR
YYG_
RBYR

Other rules

Your program must run in under 15 seconds or it is disqualified.

Make sure to try it with the following board: RRRRBG_BYYYY
That board, with it's three symmetries, is the "hardest" possible board.

You may not use any external resources, or have any input data files.

Some stats

There are exactly 415,800 possible boards
There are exactly 360 "solution" boards
My program that I wrote to test this out runs in about 2 seconds in Java, without much optimization.

This program, with minimal golfing, is 1364 bytes.

Scoring

This is code-golf, fewest characters that meets the other requirements wins!

Smalltalk 497
|b R M s g a|
b:=Stdin nextLine.R:='D--R-L--U'.
M:=#((6 9)(4 6 9)(4 6 9)(4 9)(1 6 9)(1 4 6 9)(1 4 6 9)(1 4 9)(6 1)(4 6 1)(4 6 1)(4 1)).
s:=Set new.q:=OrderedCollection new.
a:=[:p :m|(s includes:p)ifFalse:[s add:p.q add:p->m]].
a value:b value:''.
[|x i n p|
x:=q removeFirst.p:=x key.i:=(p indexOf:$_).
(M at:i)do:[:m||v|
n:=p copy.n at:i put:(p at:i+m-5);at:i+m-5put:$_.
v:=(x value,(R at:m)).
(n to:4)=(n from:9)ifTrue:[
v printCR.(n splitForSize:4)map:#printCR.^self].
a value:n value:v]]loop.

Input:
YRGYB_BRRYYR

Output:
DLURRULDDLLU
YBYR
RGR_
YBYR

Exec. Time (bytecode, not jitted): 100ms
Input:
RRRRBG_BYYYY

Output:
DRRUULLDLURDDRRULULD
YBRR
GY_Y
YBRR

Exec. Time 2s unjitted; 0.8s jitted (most time spent in collection code)
Here is an ungolfed version for readability:
|b R M s g add|
b:=Stdin nextLine.
R:='D--R-L--U'.
M:=#((6 9)(4 6 9)(4 6 9)(4 9)
     (1 6 9)(1 4 6 9)(1 4 6 9)(1 4 9)
     (6 1)(4 6 1)(4 6 1)(4 1)).
s := Set new.
queue := OrderedCollection new.

add := [:p :m |
  (s includes:p) ifFalse:[
    s add:p.
    queue add:(p->m).
  ]].

add value:b value:''.

[
  |x i n p|

  x := queue removeFirst.
  p := x key.
  i := (p indexOf:$_).
  (M at:i) do:[:m |
    |v|
    n := p copy.
    n at:i put:(p at:i+m-5); at:i+m-5 put:$_.
    v:=(x value,(R at:m)).
    (n to:4)=(n from:9) ifTrue:[
      v printCR.
      (n splitForSize:4) map:#printCR.
      ^ self
    ].
    add value:n value:v]
] loop.

Python 372
This was longer than I expected, I might go back later and see if I can optimize more. It uses a pretty inefficient method of brute-forcing the answer, but it seems to consistently run at no more than 8 seconds on my relatively old laptop.
A=lambda s,i,n:s[:i]+n+s[i+1:]
def M(b):
 i=b.find('_')
 for d,n in([('L',i+1)]if i%4<3 else[])+([('R',i-1)]if i%4>0 else[])+([('D',i-4)]if i>4 else[])+([('U',i+4)]if i<8 else[]):yield d,A(A(b,i,b[n]),n,'_')
def F():
 c=[('',raw_input())]
 while 1:
    for (m,b)in c:
     if b[:4]==b[8:]:return m,b
    c=[(m+d,n)for(m,b)in c for(d,n)in M(b)]
print F()

Have you tried it with RRRRBG_BYYYY? I just tried it on ideone and it said "time limit exceeded"

@durron597 Yeah that seems to take well over the limit (I only tested with your example and some trivial cases :\ ) I will try to optimize it to stay within the limit later. It might help to add some of the longest examples to test in the question. (Off the top of my head I don't really know what these would look like or how many moves they would take)

that is the longest example :)

Java 1364
I golfed this some but I'm sure there's plenty more I could do. For example I close the input stream which is not necessary ;) I just wanted to put something up.
import java.util.*;class F{enum D{R{B b(B i){return i.z==3?null:g(i,1);}},L{B b(B i){return i.z==0?null:g(i,-1);}},D{B b(B i){return i.y==2?null:g(i,4);}},U{B b(B i){return i.y==0?null:g(i,-4);}};abstract B b(B i);B g(B i,int f){f+=4*i.y+i.z;char[]s=i.s.toCharArray();s[i.e]=s[f];s[f]='_';return w.get(new String(s));}}enum C{_,G,B,R,Y;}class B{C[][]a=new C[3][4];String s;int y,z,e,c;B p;D d;B(String p){int i,j,q;for(i=0;i<3;i++){for(j=0;j<4;j++){q=4*i+j;a[i][j]=C.valueOf(p.substring(q,q+1));if(a[i][j]==C._){y=i;z=j;e=q;}}}s=p;}boolean v(){return Arrays.equals(a[0],a[2]);}void p(B b,D n){p=b;d=n;c=p.c+1;}String g(){String u="\n";for(int i=0;i<3;i++,u+="\n")for(int j=0;j<4;j++)u+=a[i][j];return u;}}Set<B>b=new HashSet<B>(),p;static Map<String,B>w=new HashMap<>();void p(String f,String s){int n=s.length();if(n==0){B o=new B(f);w.put(f,o);if(o.v())b.add(o);}else{Set e=new HashSet();for(int i=0;i<n;i++){char c=s.charAt(i);if(!e.contains(c)){p(f+c,s.substring(0,i)+s.substring(i+1,n));e.add(c);}}}}public static void main(String[]a){new F().r();}void r(){Scanner c=new Scanner(System.in);String t=c.nextLine();p("",t);for(int i=0;i<20;i++,b=p){p=new HashSet<>(b);for(B o:b)if(o.c==i)for(D d:D.values()){B n=d.b(o);if(n!=null&&!p.contains(n)){n.p(o,d);p.add(n);}}}B q=w.get(t);while(!q.v()){System.out.print(q.d);q=q.p;}System.out.println(q.g());c.close();}}

Ungolfed:
import java.util.*;

class F {
    enum D {
        R {
            B b(B i) {
                return i.z == 3 ? null : g(i, 1);
            }
        },
        L {
            B b(B i) {
                return i.z == 0 ? null : g(i, -1);
            }
        },
        D {
            B b(B i) {
                return i.y == 2 ? null : g(i, 4);
            }
        },
        U {
            B b(B i) {
                return i.y == 0 ? null : g(i, -4);
            }
        };

        abstract B b(B i);

        B g(B i, int f) {
            f += 4*i.y + i.z;
            char[] s = i.s.toCharArray();
            s[i.e] = s[f];
            s[f] = '_';

            return w.get(new String(s));
        }
    }

    enum C {
        _, G, B, R, Y;
    }

    class B {
        C[][] a = new C[3][4];
        String s;

        int y,z,e,c;

        B p;
        D d;

        B(String p) {
            int i,j,q;
            for(i = 0; i < 3; i++) {
                for(j = 0; j < 4; j++) {
                    q=4*i+j;
                    a[i][j] = C.valueOf(p.substring(q,q+1));
                    if(a[i][j] == C._) {
                        y = i;
                        z = j;
                        e = q;
                    }
                }
            }

            s = p;
        }

        boolean v() {
            return Arrays.equals(a[0], a[2]);
        }

        void p(B b, D n) {
            p = b;
            d = n;
            c = p.c + 1;
        }

        String g() {
            String u = "\n";
            for(int i = 0; i < 3; i++,u+="\n")for(int j = 0; j < 4; j++) u += a[i][j];
            return u;
        }
    }

    Set<B> b = new HashSet<B>(),p;
    static Map<String, B> w = new HashMap<>();

    void p(String f, String s) {
        int n = s.length();
        if (n == 0) {
            B o = new B(f);
            w.put(f, o);
            if(o.v()) b.add(o);
        }
        else {
            Set e = new HashSet();
            for (int i = 0; i < n; i++) {
                char c = s.charAt(i);
                if(!e.contains(c)) {
                    p(f + c, s.substring(0, i) + s.substring(i+1, n));
                    e.add(c);
                }
            }
        }
    }

    public static void main(String[] a) {
        new F().r();
    }

    void r() {
        Scanner c = new Scanner(System.in);
        String t = c.nextLine();

        p("", t);

        for(int i = 0; i < 20; i++, b=p) {
            p = new HashSet<>(b);

            for(B o : b)
                if(o.c == i)
                    for(D d : D.values()) {
                        B n = d.b(o);
                        if(n != null && !p.contains(n)) {
                            n.p(o, d);
                            p.add(n);
                        }
                    }
        }

        B q = w.get(t);
        while(!q.v()) {
            System.out.print(q.d);
            q = q.p;
        }
        System.out.println(q.g());

        c.close();
    }
}

Ungolfing the identifiers would be extremely helpful here...

@AJMansfield If you want to understand this you can read my code review version of the same code: http://codereview.stackexchange.com/questions/50962/solve-the-game-flux


text:
Filter a large file in small memory
The challenge is a follow-up to Filter a large file quickly  which had two submissions where were as fast as wc!  This time the difficulty is that RAM is severely restricted which means that new methods will have to be used.

Input: Each line has three space separated positive integers.
Output: All input lines A B, Tthat satisfy either of the following criterion.

There exists another input line C, D, U where D = A and 0 <= T - U < 100.
There exists another input line C, D, U where B = C and 0 <= U - T < 100.

To make a test file use the following python script which will also be used for testing. It will make a 1.3G file. You can of course reduce nolines for testing.
import random
nolines = 50000000 # 50 million
for i in xrange(nolines):
    print random.randint(0,nolines-1), random.randint(0,nolines-1), random.randint(0,nolines-1)

Rules. Your code must use no more than 200MB of RAM.  I will enforce this using ulimit -v 200000.    Your code must therefore also run on ubuntu using only easily installable and free software.
Score. You can report your unofficial score by testing on your machine as (the time in seconds needed by Keith Randall's submission from Filter a large file quickly divided by the time in seconds taken by your submission )*100 .
Winning criterion. The winner will be the one with the highest score when I test the code on my computer using a file created by the sample python code.  I will first run
sync && sudo bash -c 'echo  3 > /proc/sys/vm/drop_caches'

before each test run.
The deadline is one week from the time of the first correct entry.
My Machine The timings will be run on my machine. This is a standard 8GB RAM ubuntu install on an AMD FX-8350 Eight-Core Processor.  This also means I need to be able to run your code.
Some relevant timing information
largefile.file is a file created using the sample python code.
sync && sudo bash -c 'echo  3 > /proc/sys/vm/drop_caches'

time wc largefile.file

real    0m26.835s
user    0m18.363s
sys     0m0.495s

time sort -n largefile.file  > /dev/null

real    1m32.344s
user    2m9.530s
sys     0m6.543s

So many [fastest-code]s. You could change it to least memory used total in filtering the memory, including variables, code, etc.

@Quincunx Luckily I am not the only person on codegolf.se :) To be fair, fastest-code questions are a) really cool and b) still in the minority on codegolf.se.  It is also important to notice that the winning language has been different each time for my questions and one question had 19 answers. Who would have thought nimrod would win for example? Least memory is an interesting idea but I think you will end up with something so slow you can't test it.  Maybe next time.

@Quincunx I should also add that it's not trivial to write any code that works, let alone is fast, for this problem because of the RAM restriction.  So I don't really look at it as a standard fastest code problem.

The ram restriction is fairly trivial to work with :)

Is there a restriction on disk space?

@Ourous Shhh!  You're giving away ma secrets :P

@Ourous No, although I won't test code that might damage my computer! If you are going to use a lot of disk space, please say how much in your answer.

C, score 55.55
Same as my other implementation, but it does the radix sort using disk files.  Uses ~25MB of memory, mostly for buffers.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>

#define R 3
#define B 9
#define M ((1<<B)-1)
#define BUFSIZE 4096
#define PARSEBUF 65536

typedef struct {
  int a,b,t;
} entry;

typedef struct {
  int fd;
  int lo;
  int hi; // bytes buf[lo]..buf[hi-1] are valid.
  entry e; // scratch
  char buf[PARSEBUF];
} ParseState;

entry *parse(ParseState *s) {
  int n = s->hi - s->lo;

  // if we need to, grab some more data
  if(n < 100 && s->fd != -1) {
    memmove(&s->buf[0], &s->buf[s->lo], n);
    int k = read(s->fd, &s->buf[n], PARSEBUF - n);
    if(k == 0) s->fd = -1;
    n += k;
    s->lo = 0;
    s->hi = n;
  }
  if(n == 0) return NULL;

  // parse line
  char *p = &s->buf[s->lo];
  int a = 0;
  while(*p != ' ') {
    a *= 10;
    a += *p - '0';
    p++;
  }
  p++;
  int b = 0;
  while(*p != ' ') {
    b *= 10;
    b += *p - '0';
    p++;
  }
  p++;
  int t = 0;
  while(*p != '\n') {
    t *= 10;
    t += *p - '0';
    p++;
  }
  p++;
  s->lo += p - &s->buf[s->lo];
  s->e.a = a;
  s->e.b = b;
  s->e.t = t;
  return &s->e;
}

typedef struct {
  int fd;
  int lo;
  int hi;
  entry buf[BUFSIZE];
} ReadBuf;

entry *bread(ReadBuf *b) {
  if(b->lo == b->hi) {
    int k = read(b->fd, &b->buf[0], BUFSIZE*sizeof(entry));
    if(k == 0) return NULL;
    b->lo = 0;
    b->hi = k / sizeof(entry);
  }
  return &b->buf[b->lo++];
}

typedef struct {
  int fd;
  int offset;   // offset in file to write buffer
  int n;        // # of entries
  entry buf[BUFSIZE];
} WriteBuf;

void bflush(WriteBuf *b) {
  int size = b->n * sizeof(entry);
  pwrite(b->fd, &b->buf[0], size, b->offset);
  b->offset += size;
  b->n = 0;
}

void bwrite(WriteBuf *b, entry *e) {
  b->buf[b->n++] = *e;
  if(b->n == BUFSIZE)
    bflush(b);
}

int count[R][1<<B];
int accum[R][1<<B];

unsigned char bcount[16384];

ParseState s;
ReadBuf rd;
WriteBuf wr[1<<B];
entry recent[65536];
char print[65536];

int main(int argc, char *argv[]) {
  int fd = open(argv[1], O_RDONLY);
  int fd1 = open("tmp1", O_RDWR | O_CREAT | O_TRUNC, 0666);
  int fd2 = open("tmp2", O_RDWR | O_CREAT | O_TRUNC, 0666);

  // parse input, write first file, do stats for radix sort
  entry *e;
  s = (ParseState){fd, 0, 0};
  wr[0] = (WriteBuf){fd1, 0, 0};
  while((e = parse(&s)) != NULL) {
    bwrite(&wr[0], e);
    // compute counts for radix sort
    int t = e->t;
    for(int r = 0; r < R; r++) {
      count[r][t&M]++;
      t >>= B;
    }
  }
  bflush(&wr[0]);

  // accumulate count entries
  for(int r = 0; r < R; r++) {
    int sum = 0;
    for(int i = 0; i < 1<<B; i++) {
      accum[r][i] = sum;
      sum += count[r][i];
    }
  }

  // radix sort
  int fda = fd1;
  int fdb = fd2;
  for(int r = 0; r < R; r++) {
    lseek(fda, 0, SEEK_SET);
    rd = (ReadBuf){fda, 0, 0};
    for(int i = 0; i < 1<<B; i++) {
      wr[i] = (WriteBuf){fdb, accum[r][i]*sizeof(entry), 0};
    }
    while((e = bread(&rd)) != NULL) {
      bwrite(&wr[(e->t>>r*B)&M], e);
    }
    for(int i = 0; i < 1<<B; i++) {
      bflush(&wr[i]);
    }
    int t = fda;
    fda = fdb;
    fdb = t;
  }

  // find matches
  lseek(fda, 0, SEEK_SET);
  ReadBuf rd = {fda, 0, 0};
  int lo = 0;
  int hi = 0;
  while((e = bread(&rd)) != NULL) {
    recent[hi] = *e;
    print[hi] = 0;
    while(recent[lo].t <= e->t - 100) {
      int x = recent[lo].b & 16383;
      if(bcount[x] != 255) bcount[x]--;
      if(print[lo])
    printf("%d %d %d\n", recent[lo].a, recent[lo].b, recent[lo].t);
      lo++;
    }
    if(bcount[e->a & 16383] != 0) {
      // somewhere in the window is a b that matches the
      // low 14 bits of a.  Find out if there is a full match.
      for(int k = lo; k < hi; k++) {
    if(e->a == recent[k].b)
      print[k] = print[hi] = 1;
      }
    }
    int x = e->b & 16383;
    if(bcount[x] != 255) bcount[x]++;
    hi++;
    if(hi == 65536) {
      if(lo == 0) {
    printf("recent buffer too small!\n");
    exit(1);
      }
      memmove(&recent[0], &recent[lo], (hi - lo) * sizeof(entry));
      memmove(&print[0], &print[lo], (hi - lo) * sizeof(char));
      hi -= lo;
      lo = 0;
    }
  }
}

That is an amazing score! Do you think it would be even higher if you used closer to 200MB of memory?

@Lembik: no, adding more buffer has almost no effect.

Tcl with SQLite, score less than 0.05
Shove the lines into an SQL database, then make SQLite do the work.  Requires the Tcl bindings for SQLite 3, OpenBSD package sqlite3-tcl, Ubuntu package libsqlite3-tcl.
Usage: tclsh filter.tcl <input.txt >output.txt
package require sqlite3

sqlite3 db ""
db eval {
    begin transaction;
    create table lines(i integer primary key,
               a integer, b integer, t integer);
}
while {[gets stdin line] >= 0} {
    lassign [split $line] a b t
    db eval {insert into lines values(null,$a,$b,$t)}
}
db eval {
    create view pairs as
      select first.i, second.i as j
      from lines as first, lines as second
      where first.a == second.b and
        first.t - second.t between 0 and 99 and
        first.i != second.i;
    select a, b, t from lines
      where i in (select i from pairs union select j from pairs);
} {
    puts "$a $b $t"
}
db close

Comparison of time
The motto of SQLite is, "Small. Fast. Reliable. Choose any three," but my SQL query is not fast. My program took more than six hours with my slow hard disk. I compare times for three programs:

cfilter is the large-memory C program by Keith Randall
hfilter is the large-memory C program by James_pic
filter.tcl is my small-memory Tcl program

With 50 million lines of input, cfilter and hfilter both crash because my data size limit is only 1 GB. (The default limit in OpenBSD is 512 MB.) If I raise my limit to 8 GB with ulimit -Sd 8388608, then I can run both cfilter and hfilter. I also lower my physical memory limit with -m 3000000 so that other programs stay in RAM, not in swap space. I have only 4 GB of RAM.
$ ulimit -Sd 8388608 -m 3000000
$ time ./cfilter input.txt >output.txt
    0m9.03s real     0m5.17s user     0m1.97s system
$ ln -sf input.txt test.file
$ time ./hfilter >output2.txt
    0m25.62s real     0m22.08s user     0m2.04s system
$ time tclsh8.6 filter.tcl <input.txt >output3.txt
^Z  371m19.57s real     0m0.00s user     0m0.00s system
[1] + Suspended            tclsh8.6 filter.tcl < input.txt > output3.txt

I suspended filter.tcl after more than 6 hours. top shows that filter.tcl used less than 15 MB of memory and less than 12 minutes of processor time. Most of the 6 hours went to wait for my slow hard disk (5400 rpm).
For score, 10 seconds for cfilter, divided by more than 6 hours for filter.tcl, times 100, equals less than 0.05.
Comparison of results
The different filters do not select the same lines!  Consider these 6 lines of input:
$ cat example.txt
1 801 33
802 1 33
2 803 499
804 2 400
805 2 400
3 3 555

My filter.tcl outputs five lines, all except 3 3 555.
$ tclsh8.6 filter.tcl <example.txt
1 801 33
802 1 33
2 803 499
804 2 400
805 2 400

But cfilter only outputs three lines:
$ ./cfilter example.txt
804 2 400
805 2 400
2 803 499

cfilter seems to have a bug when T - U == 0. It fails to output the lines 1 801 33 and 802 1 33, though I believe them to be a matching pair.
Now for hfilter and the Scala program by the same author:
$ ln -sf example.txt test.file
$ ./hfilter
804 2 400
2 803 499
805 2 400
2 803 499
3 3 555
3 3 555
$ scala Filterer example.txt /dev/stdout
804 2 400
2 803 499
802 1 33
1 801 33
805 2 400
2 803 499
3 3 555
3 3 555

hfilter also misses the lines 1 801 33 and 802 1 33, but the Scala version finds them. Both programs output 2 803 499 twice (because it is in two matching pairs), but I might ignore such duplication. Both programs also output 3 3 355. This line is in a pair with itself because A = B. This is only correct if the phrase "another input line" includes the same line.
When the input is the random 50 million lines from the Python script, these differences might disappear. The probability that any matching pair has T - U = 0, or any line has A = B, is close to zero when the input has random numbers up to 50 million.

you are right, there is a bug in my code when two lines have a matching T.

This is a great detailed analysis. Thank you!