text:
Calculating Collatz Cousins
Define the function f(n) for a positive integer n as follows:

n / 2, if n is even
3 * n + 1, if n is odd

If you repeatedly apply this function to any n greater than 0, the result always seems to converge to 1 (though nobody's been able to prove that yet). This property is known as the Collatz Conjecture.
Define an integer's stopping time as the number of times you have to pass it through the Collatz function f before it reaches 1. Here are the stopping times of the first 15 integers:
1  0
2  1
3  7
4  2
5  5
6  8
7  16
8  3
9  19
10 6
11 14
12 9
13 9
14 17
15 17

Let's call any set of numbers with the same stopping time Collatz cousins. For example, 5 and 32 are Collatz cousins, with a stopping time of 5.
Your task: write a program or function that takes a nonnegative integer and generates the set of Collatz cousins whose stopping time is equal to that integer.
Input
A nonnegative integer S, given via STDIN, ARGV, or function argument.
Output
A list of all numbers whose stopping time is S, sorted in ascending order. The list may be output by your program, or returned or output by your function. Output format is flexible: space-separated, newline-separated, or any standard list format of your language is fine, as long as the numbers are easily distinguishable from one another.
Requirements
Your submission must give correct results for any S ≤ 30. It should finish in seconds or minutes, not hours or days.
Examples
0  -> 1
1  -> 2
5  -> 5, 32
9  -> 12, 13, 80, 84, 85, 512
15 -> 22, 23, 136, 138, 140, 141, 150, 151, 768, 832, 848, 852, 853, 904, 906, 908, 909, 5120, 5376, 5440, 5456, 5460, 5461, 32768

Here is a Gist of the output for S = 30.
This is code-golf: shortest program in bytes wins. Good luck!

What of cycles? I did not see a mention of cycle avoidance. Because for S=5, there are 3 values [4, 5, 32] because you can go "1 - 2 - 4 - 1 - 2- 4"

@JPMC Cycle avoidance is implied by the definition of stopping time.  The stopping time of 4 is 2, not 5, because 2 is "the number of times you have to pass it through the Collatz function before it reaches 1."

Ah, forgive me. I was thinking that a number could have multiple stopping times, since multiple paths can lead to it. But that was with respect to building up from 1, not working from N. Sorry about that.

I have a solution that can do S=27 in about 2 minutes on my machine, but runs out of memory on S>=28. Is it valid?

@isaacg Based on what I told FryAmTheEggman earlier, if you can't find some computer that it runs on, I'm going to say no.  But if you want to post it and see if someone else has enough memory to test S=30, you could do that.  What language is it in?

@DLosc Pyth, of course.

Related, but not golfed: http://math.stackexchange.com/q/470782/20792 and http://math.stackexchange.com/q/1243841/20792

Pyth, 26 24 21 bytes
Su+yMG-/R3fq4%T6G1Q]1

This code runs instantly for S=30. Try it out yourself: Demonstration
Thanks to @isaacg for saving 5 bytes.
Explanation
My code starts with 1 and undos the Collatz function. It maps all numbers d of the S-1 step to 2*d and (d-1)/3. The last one in not always valid though.
                        implicit: Q = input number
                   ]1   start with G = [1]
 u                Q     apply the following function Q-times to G:
                          update G by
   yMG                      each number in G doubled
  +                       +
          fq4%T6G           filter G for numbers T, which satisfy 4==T%6
       /R3                  and divide them by 3
      -          1          and remove 1, if it is in the list
                            (to avoid jumping from 4 to 1)
S                       sort the result and print

That's a beautiful use of -F.

If you put a - ... 1 around the sum inside the reduce, you don't need the reduce to be a .u, nor the -F outside. Saves 2 characters.

@isaacg Thanks. I actually had this in a previous version, but removed it during debugging an error.

I've borrowed @isaacg's for my own answer. I've spent hours trying to find the shortest code for removing duplicates, but this is by far the most elegant solution. Also, I really like the youe use of a tuple to discard invalid quotients. Sadly, CJam doesn't have tuples, but I did manage to map invalid quotients to 1.

@Jakube q4%d6 is equivalent to !%hhd6, but 1 character shorter.

Also, I think you can shorten the code by separating the 2 possibilities, and just using maps and filters.

@isaacg Thanks, down to 21 now.

Mathematica, 98 92 89 bytes
This solution solves S = 30 immediately:
(p={0};l={1};Do[l=Complement[##&@@{2#,Mod[a=#-1,2]#~Mod~3~Mod~2a/3}&/@l,p=p⋃l],{#}];l)&

This is an unnamed function taking S as its only parameter and returning a list of the Collatz cousins.
The algorithm is a simple breadth-first search. The Collatz cousins for a given S are all the integers that can be reached from the Collatz cousins for S-1 via 2*n or odd numbers that can be reached via (n-1)/3. We also need to ensure that we only produce those integers which were reached for the first time after S steps, so we keep track of all previous cousins in p and remove those from the result. Since we're doing that anyway, we can save a few bytes by computing the steps from all previous cousins (not just those from S-1) to save a few bytes (that makes it slightly slower, but not noticeably for the required S).
Here is a slightly more readable version:
(
  p = {0};
  l = {1};
  Do[
    l = Complement[
      ## & @@ {2 #, Mod[a = # - 1, 2] #~Mod~3~Mod~2 a/3} & /@ l,
      p = p ⋃ l
    ]~Cases~_Integer,
    {#}
  ];
  l
) &

CJam, 29 26 bytes
Xari{{2*_Cmd8=*2*)}%1-}*$p

Credit goes to @isaacg for his idea to remove 1's after each iteration, which saved me two bytes directly and another one indirectly.
Try it online in the CJam interpreter (should finish in less than a second).
How it works
Xa       e# Push A := [1].
ri{      e# Read an integer from STDIN and do the following that many times:
  {      e# For each N in A:
    2*   e#     Push I := (N * 2) twice.
    _Cmd e#     Push (I / 12) and (I % 12).
     8=  e#     Push K := (I % 12 == 8).

         e#     (K == 1) if and only if the division ((N - 1) / 3) is exact and
         e#     yields an odd integer. In this case we can compute the quotient
         e#     as (I / 12) * 2 + 1.

    *2*) e#     Push J := (I / 12) * K * 2 + 1.

         e#     This yields ((N - 1) / 3) when appropriate and 1 otherwise.
  }%     e# Replace N with I and J.
  1-     e# Remove all 1's from A.

         e# This serves three purposes:

         e# 1. Ones have been added as dummy values for inappropriate quotients.

         e# 2. Not allowing 1's in A avoids integers that have already stopped
         e#    from beginning a new cycle. Since looping around has been prevented,
         e#    A now contains all integers of a fixed stopping time.

         e# 3. If A does not contain duplicates, since the maps N -> I and N -> J
         e#      are inyective (exluding image 1) and yield integers of different
         e#      parities, the updated A won't contain duplicates either.

}*       e#
$p       e# print(sort(C))

Python 2, 86 83 75 73 71 bytes
f=lambda n,k=1:sorted([k][n:]or(k>4==k%6and f(n-1,k/3)or[])+f(n-1,k*2))

Call like f(30). n = 30 is pretty much instant.
(Thanks to @DLosc for the idea of recursing by k being a number rather than a list of cousins, and a few bytes. Thank to @isaacg for dropping ~-.)
This variant is much shorter, but unfortunately takes too long due to exponential branching:
f=lambda n,k=1:sorted([k][n:]or(k>4==k%6)*f(n-1,k/3)+f(n-1,k*2))

Interesting--my original solution is very similar, but (taking a couple optimizations from yours) comes out 2 bytes shorter: f=lambda d,n=1:d and sorted(sum((c(d-1,x)for x in[n*2]+[~-n/3][:n>4==n%6]),[]))or[n].  It's less efficient with the function calls but still does n = 30 in under a second.

@DLosc I liked your idea and made it one better :)

Nice!  Here's 2 more bytes off: f=lambda n,k=1:sorted([k][n:]or(k>4==k%6and f(n-1,~-k/3)or[])+f(n-1,k*2))

@DLosc Ahaha thanks. I still swear there's got to be a better short-circuiting way though...

I think the ~- is unnecessary because you're using integer division.

@isaacg Oh wow, I'm slightly ashamed I didn't notice that :P

CJam, 35 bytes
1]ri{_"(Z/Y*"3/m*:s:~\L+:L-_&0-}*$p

Explanation coming soon. This is a much faster version than the "pretty straight forward" approach (see it in edit history).
Try it online here for N = 30 which runs in seconds on the online version and instantly in the Java Compiler

How long will this take for the larger inputs?  It should finish in seconds or minutes, not hours or days.

Ah, I see.  The Python version I wrote looked to take about 5 hours for N = 30.

Latest version runs almost instantly.

There's a bug in your code. The test-case S=15 doesn't work.

Java 8, 123
x->java.util.stream.LongStream.range(1,(1<<x)+1).filter(i->{int n=0;for(;i>1;n++)i=i%2<1?i/2:3*i+1;return n==x;}).toArray()

When x is 30, the program takes 15 minutes and 29 seconds.
Expanded
class Collatz {
    static IntFunction<long[]> f =
            x -> java.util.stream.LongStream.range(1, (1 << x) + 1).filter(i -> {
                int n = 0;
                for (; i > 1; n++)
                    i = i % 2 < 1 ? i / 2 : 3 * i + 1;
                return n == x;
            }).toArray();

    public static void main(String[] args) {
        System.out.println(Arrays.toString(f.apply(15)));
    }
}

Just curious, how long does this take for S=30?

This only works in Java 8, correct?  Using javac 1.7.0_79 on Ubuntu gave me lots of syntax errors.

@DLosc Correct; I'll mention that in the post.

Restricting the loop terminal condition to i > 1 && ++n <= x (you can drop n++ too) seems to be even faster for just 5 more characters... about 3 minutes for S=30 for me. That gets shaved to safely under a minute if I include .parallel() too, but since this is code-golf...

Python 2, 118 bytes
Well, I figured that I wouldn't reach the best Python score after seeing @Sp3000's solution. But it looked like a fun little problem, so I wanted to try an independent solution anyway:
s={1}
for k in range(input()):
 p,s=s,set()
 for t in p:s.add(2*t);t>4and(t-1)%6==3and s.add((t-1)/3)
print sorted(s)

Same thing before stripping whitespace:
s={1}
for k in range(input()):
    p,s=s,set()
    for t in p:
        s.add(2 * t)
        t > 4 and (t - 1) % 6 == 3 and s.add((t - 1) / 3)
print sorted(s)

This is a very direct implementation of a breadth first search. In each step, we have the set with stopping time k, and derive the set with stopping time k + 1 by adding the possible predecessors of each value t in the set from step k:

2 * t is always a possible predecessor.
If t can be written as 3 * u + 1, where u is an odd number that is not 1, then u is a predecessor as well.

Takes about 0.02 seconds to run for N = 30 on my MacBook Pro.

In general, s.add(x) is unnecessary in a golf since you can usually do s|={x} instead. Also, using ~-x instead of (x+1) saves on brackets. But otherwise, good job :)

@Sp3000 Thanks. I can't easily replace the second s.add() because it becomes an assignment, and can't be part of the expression anymore. It does work for the first one. The for loops based on counters are always kind of verbose as well. I thought I could shorten it by using a while loop, but it turned out to be exactly the same the same length.

Instead of a for loop, since you don't use the input in any other way you can probably do exec"..."*input() instead :)

PHP 5.4+, 178 bytes
The function
function c($s,$v=1,$p=[],&$r=[]){$p[]=$v;if(!$s--){return$r[$v][]=$p;}c($s,$v*2,$p,$r);is_int($b=($v-1)/3)&!in_array($b,$p)&$b%2?c($s,$b,$p,$r):0;ksort($r);return array_keys($r);}

Test & Output
echo "0 - ".implode(',',c(0)).PHP_EOL;
// 0 - 1
echo "1 - ".implode(',',c(1)).PHP_EOL;
// 1 - 2
echo "5 - ".implode(',',c(5)).PHP_EOL;
// 5 - 5,32
echo "9 - ".implode(',',c(9)).PHP_EOL;
// 9 - 12,13,80,84,85,512
echo "15 - ".implode(',',c(15)).PHP_EOL;
// 15 - 22,23,136,138,140,141,150,151,768,832,848,852,853,904,906,908,909,5120,5376,5440,5456,5460,5461,32768

S(30) runs in 0.24 seconds*, returns 732 elements. A couple are
86,87,89,520,522,524,525,528, [ ... ] ,178956928,178956960,178956968,178956970,1073741824

*To save on bytes, I had to add ksort and array_keys at every step. The only other choice I had was to make a small wrapper function that calls c() and then calls array_keys and ksort on the result once. But due to the time still being decently snappy, I decided to take the performance hit for low byte count. Without the proper sorting & processing, the time is 0.07 seconds on average for S(30).
If anyone has any clever ways of getting the proper processing only once without too many additional bytes, please let me know!  (I store my numbers as array keys, hence the use of array_keys and ksort)

C Language
#include <stdio.h>
#include <limits.h>
const int s = 30;

bool f(long i)
{
    int r = 0;
    for(;;)
        if (i < 0 || r > s) return false;
        else if (i == 1) break;
        else{r ++;i = i % 2 ? 3*i + 1 : i/2;}
    return (r==s);
}

void main(){
    for(long i = 1; i < LONG_MAX; i++) if (f(i)) printf("%ld ", i);
}

Hello and welcome to PPCG! Since this is a [tag:code-golf] competition, you'll want to make your code as short as possible. Also, please include the name of the language in your post.

You can hit the {} button to format your code, which I've done for you. But as Alex says, please add the language name (C?) and try golfing it :) But welcome!

@Sp3000 thanks for helping format the code

Function f is not behaving properly. With s=5, I get a bunch of incorrect results. if (r == s)return true; should be return (r==s), since f won't return anytging meaninful when (r < s). Also, I think you should declare i in f as long, since it will overflow pretty quickly for some values.

@Dennis thanks:) it should be return (r==s);


text:
Matchstick Equations
Your task in this challenge is to analyize a given "Matchstick Equation" like this one...

... and to find out whether it can be turned into a valid equation by rearranging the matches. If so, you are to output the least number of moves to do so and the resulting equation.
Input
The input is a String that can be read from STDIN, taken as a function argument or even be stored in a file. It is an equation that represents a matchstick arrangement and can be described using the following EBNF:
input = term, "=", term ;
term = number | (term, ("+" | "-"), term) ;
number = "0" | (numeralExceptZero , {numeral}) ;
numeralExceptZero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
numeral = "0" | numeralExceptZero ;

An example for a valid input would be 3+6-201=0+0+8.
Task
Consider the following illustration where each matchstick has a number assigned:

We now map each input symbol to the corresponding matchstick positions as follows:
0 ↦ 1,2,3,4,5,6
1 ↦ 4,5
2 ↦ 2,3,5,6,8
3 ↦ 3,4,5,6,8
4 ↦ 1,4,5,8
5 ↦ 1,3,4,6,8
6 ↦ 1,2,3,4,6,8
7 ↦ 4,5,6
8 ↦ 1,2,3,4,5,6,8
9 ↦ 1,3,4,5,6,8
- ↦ 8
+ ↦ 8,10
= ↦ 7,9

Each input formula can be turned into a matchstick arrangement. For example, the equation "45+6=92" becomes

where unused matchsticks are greyed out.
Your task is to find out the least number of matchsticks that have to be rearranged in order to make the equation valid.
Output
We distinguish between three possible cases:

If the input is not valid (i.e. it doesn't satisfy the above EBNF), output whatever you want.
Otherwise, if there are ways to turn the equation into a valid one by rearranging the matchsticks, you have to output both the minimum number of rearrangements and the corresponding equation. Just as the input, the outputted equation must also satisfy the given EBNF. In the above example, the correct output would be
1 and 46+6=52. If there are multiple possibilities for the resulting equation, output any of them.
Otherwise (so if the input is valid but there is no way to make the equation true), you have to output -1.

Details

You are not allowed to remove or to add matches. That means, if the input is built of n matchsticks, the output must also consist of exactly n matchsticks.
"Empty" matchstick-blocks are only allowed at the end and the beginning of an equation, not in the middle. So, for example, turning 7-1=6 into 7  =6-1 by simply removing -1 from the left side and adding it on the right side with just 3 matchstick rearrangements is not allowed.
Since I don't really see the mapping from numbers to matchstick positions as an interesting part of this challenge, for a plus of 20 bytes, you may either

access a file in which the mapping (number/operation ↦ matchstick positions) is stored in any reasonable way, or
if your programming language supports a Map datatype, assume that you have access to a map that is preinitialized with the (number/operation ↦ matchstick positions)-mapping. This map may for example look like that: {(0,{1,2,3,4,5,6}),(1,{4,5}),(2,{2,3,5,6,8}),(3,{3,4,5,6,8}), ..., (-,{8}),(+,{8,10}),(=,{7,9})}

Examples
Input: 1+1=3 ↦ Output: 1 and 1+1=2
Input: 15+6=21 ↦ Output: 0 and 15+6=21
Input: 1=7 ↦ Output: -1
Input: 950-250=750 ↦ Output: 2 and 990-240=750
Input: 1-2=9 ↦ Output: 1 and 1+2=3
Input: 20 + 3=04 ↦ Output: anything
Winner
This is code-golf, so the shortest correct answer (in bytes) wins. The winner will be chosen one week after the first correct answer is posted.

Please add 0: 1, 2, 3, 4, 5, 6 for consistency

Oh thanks, totally forgot about that somehow!

@vauge Hey should '2=1-1' -> '2-1=1' return 3 or 14 moves since the 2 technically has to be moved left?

@Cieric it should return 3, simply because you can switch the position of = (2 matchsticks) and - (1 matchstick) and leave all the numbers where they are. If, however, the 2 had to be moved left, you would also have to count the required moves.

Is there a limitation on number of operations? Can the input be like 1+1+2=3-6+10? And same question about output.

@Qwertiy For both input and output, the number of operations is not limited, so 1+1+2=3-6+10 is a perfectly valid input.

Javascript, 1069 Bytes
I've tested it with quite a few test equations and it seems to work all of the time now...
function w(t){function B(c,f){d=(c.length>f.length?f:c).split("");e=(c.length>f.length?c:f).split("");longer=Math.max(d.length,e.length);if(0!==d.length&&0!==e.length){c=[];for(x in d)for(y in c[x]=[],e)c[x][y]=1<y-x?-1:function(c,n){r=0;for(j in n)-1<c.indexOf(n[j])&&r++;return c.length+n.length-2*r}(a[d[x]],a[e[y]]);return v=function(f,n){for(var h=f.length-2;0<=h;h--)c[n.length-1][h]+=c[n.length-1][h+1];for(h=f.length-2;0<=h;h--)for(var q=0;q<n.length-1;q++)1>=h-q&&(c[q][h]+=-1==c[q][h+1]?c[q+1][h+1]:Math.min(c[q+1][h+1],c[q][h+1]));return c[0][0]/2}(e,d)}return-1}a=[[1,2,3,4,5,6],[4,5],[2,3,5,6,8],[3,4,5,6,8],[1,4,5,8],[1,3,4,6,8],[1,2,3,4,6,8],[4,5,6],[1,2,3,4,5,6,8],[1,3,4,5,6,8]];a["+"]=[8,0];a["-"]=[8];a["="]=[7,9];a[" "]=[];l=0;p=[];u=[];r=/^([1-9]\d*|0)([+-]([1-9]\d*|0))*=([1-9]\d*|0)([+-]([1-9]\d*|0))*$/;b=/(=.*=|[+=-]{2,}|^[+=-])/;if(!t.match(r))return-1;g=function(c,f,t){if(0===t&&f.match(r)&&eval(f.replace("=","==")))c.push(f);else for(var n in a)t>=a[n].length&&" "!=n&&!(f+n).match(b)&&g(c,f+n,t-a[n].length)};g(p,"",function(c){m=0;for(var f in c)m+=a[c[f]].length;return m}(t.split("")));for(var z in p)k=B(t,p[z]),u[k]||(u[k]=[]),u[k].push(p[z]);for(var A in u)return[A,u[A]];return-1}

Well this is my first time ever submitting an answer, so I don't see myself winning. This is basically a brute force method to figure out all answers and then it grabs and returns the smallest ones in an array. with the first argument being the length and the second being an array with the outputs.
if the input is "1-2=9" the output is [1,["1+2=3","7-2=5"]]
and here is the uncompressed code:
function ms(s) {
a=[[1,2,3,4,5,6],[4,5],[2,3,5,6,8],[3,4,5,6,8],[1,4,5,8],[1,3,4,6,8],[1,2,3,4,6,8],[4,5,6],[1,2,3,4,5,6,8],[1,3,4,5,6,8]];
a["+"] = [8, 0];
a["-"] = [8];
a["="] = [7, 9];
a[" "] = [];
l = 0;
p = [];
u = [];
r = /^([1-9]\d*|0)([+-]([1-9]\d*|0))*=([1-9]\d*|0)([+-]([1-9]\d*|0))*$/;
b = /(=.*=|[+=-]{2,}|^[+=-])/;
if (!s.match(r)) return -1;
function f(g,h)
{
    d=(g.length>h.length?h:g).split('');
    e=(g.length>h.length?g:h).split('');
    longer=Math.max(d.length, e.length);
    if(0!==d.length&&0!==e.length)
    {
        g=[];
        for(x in d)
        {
            g[x]=[];
            for(y in e)
            {
                g[x][y]=(y-x>1)?-1:function(g, h){r=0;for(j in h)if(g.indexOf(h[j])>-1)r++;return g.length+h.length-2*r;}(a[d[x]],a[e[y]]);
            }
        }
        v=function(d,e)
        {
        for(var y=d.length-2;y>=0;y--) g[e.length-1][y]+=g[e.length-1][y+1];
        for(var y=d.length-2;y>=0;y--)
            for(var x=0;x<e.length-1;x++)
                if(y-x<=1)
                    g[x][y]+=g[x][y+1]==-1?g[x+1][y+1]:Math.min(g[x+1][y+1], g[x][y+1]);
        return g[0][0]/2}(e,d)
        return v
    }
    return -1;
}
g=function(n, s, i){if (i===0 && s.match(r) && eval(s.replace('=','=='))){n.push(s);return;}for (var c in a) if(i>=a[c].length && c!=" " && !(s+c).match(b)) g(n, s+c, i-a[c].length);};
g(p, "", function(q){m=0;for(var t in q)m+=a[q[t]].length;return m}(s.split('')));
for (var i in p)
{
    k=f(s, p[i]);
    if (!u[k]) u[k] = [];
    u[k].push(p[i]);
}
for (var q in u) return [q, u[q]];
return -1;
}

Warning: Don't do equations like 950-250=750 it uses ~45 Matchsticks and because this code uses brute force it will cause javascript to hang.

I believe you can declare the variables you use such as var k in the loops as unused parameters to the function, saving 3 bytes for each declaration.

I think I'm going to go learn a few more programming languages and figure out a not so brute force way to try and really knock that byte count down.

I think your solution is not correct, as when you are calculating the distance you always align the equals characters. In some cases it is not the optimal way. For example '2=1-1' can be transformed in 3 moves into '2-1=1', while aligning the '=' signs gives 14 moves. Also I don't see how you avoid leading zeroes. For example 08=8 for 80=8 is incorrect.

@nutki Yeah, I think I can change that. I was thinking that'd be wrong though due to you technically having to move over the 2 to make room for the -1

@nutki okay, yeah. Sorry I see what you mean now. Well I'm going to fix the regex and see if I can change the code around for the edit distance.

Did you take into account the 20 point hit for your 185-char initialization of a?

@NotthatCharles Oh no I didn't. Thanks for bringing that up would that put me at 984? or what?

@Cieric Correct. As the question states, "for a plus of 20 bytes, you may [...] assume that you have access to a map that is preinitialized with the (number/operation ↦ matchstick positions)-mapping". So you may assume that a is already defined. So your code is 1149 - 185 + 20 = 984 Bytes long.

@vauge Okay thanks, I think it might turn out to be longer still after I'm done fixing it.

@Cieric The resulting equations seem perfectly correct now, however, if I run your code on 11=4, it returns 6.5 as the number of required moves.

@vauge yea I noticed and I'm trying to fix it... It sucks that I have to make it even longer though. I noticed with 1+1=3 which gave 2 moves...

@vauge first, do i have to include the output to console code or will the function alone work? and can you test this function with all you have to make sure it has no faults I've tested it with all the ones i can think of.

Perl, 334
Fairly fast as long as the solution is reachable in 1 or 2 moves. When there is no solution you are up for a long wait even in the smallest case of 1=7.
#!perl -p
@y=map{sprintf"%010b",$_}63,24,118,124,89,109,111,56,127,125,64,192,768;
$y{$z{$y[$c++]}=$_}=$y[$c]for 0..9,qw(- + =);
$"="|";$l=s/./$y{$&}/g;$x{$_}=1;for$m(0..y/1//){
last if$_=(map"$m $_",grep{s/@y/$z{$&}/g==$l&&/^\d.*\d$/&!/\D\D/&!/\b0\d/&y/=//==1&&eval s/=/==/r}keys%x)[0];
$_=-1;s/0/"$`1$'"=~s!1!$x{"$`0$'"}=1!ger/eg for keys%x}

Example:
$ time perl ~/matchstick.pl <<<950-250=750
2 990-250=740

real    0m39.835s
user    0m39.414s
sys 0m0.380s

This will not find solutions that change the length of the equasion like 11=4 -> 2 11=11, but I am not sure it this would be allowed.

Solutions that change the length of the equation are allowed as long as they follow the EBNF mentioned in the question. Therefore, they should also be found by your function.

@vauge, yeah I can see that it could be inferred from "empty machsticks blocks" section in the details. I will not add it to this solution though as while it could work, it would make it even slower.

@vauge I don't want to sound rude, but if the code isn't fixed will it still count?

@Cieric If there is no other solution that handles all those cases then yes, it will count. However, if there are any fully working answers by the end of this challenge, I will accept the shortest of them.

@vauge okay just checking I only have to make sure the number of move is correct so far it always displays the correct output equation.

source: Stack Exchange

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

sort: votes


text:
Where should I put my restaurant?
You are the owner of a restaurant. You are opening in a new area in Cartesia where there is only one main road, known as the y-axis. You want to place your restaurant such that you minimize the total distance from your restaurant and each of the houses in that area.
Input:
The input will be
n, the number of houses
house1
house2
house3
...
houseN

where each house is a coordinate in the form x y. Each unit represents one kilometer.
You can take input as a string or provide a function that takes the input, in whatever format you choose, as its arguments.
Output:
The y-coordinate of your restaurant (remember, it will be located on the y-axis). Actually, it will be located on the side of the road, but the difference is negligible.
Essentially, if nth house is h_n and D is the distance function, then you want to find k such that D(h_0, (0, k)) + D(h_1, (0, k)) + D(h_2, (0, k)) + ... + D(h_n, (0, k)) is minimized.
Note that distance is calculated as though the customer travels in an exactly straight line from their house to the restaurant. That is the distance from (x, y) to your restaurant is sqrt(x^2 + (y - k)^2).
The output should be accurate to at least 2 decimal places.
Output can be printed as a string or can be returned from the function.
Example input/output:
Input:
2
5.7 3.2
8.9 8.1
Output:
5.113013698630137

The total distance in this example is about 15.4003 kilometers.
This is code golf -- shortest code wins.
P.S. I'm also interested in a mathematical solution that isn't just brute force. It won't win the code golf but it'll get some upvotes. Here is how I did the example problem:
Let point A be located at A(5.7, 3.2) and B at B(8.9, 8.1). Let the solution point at (0, k) be C. Reflect A over the y-axis to make A' at (-5.7, 3.2). The distance from A' to C is equal to the distance from A to C. Therefore, the problem can be reduced to the point C such that A'C + CB is minimized. Obviously, this would be the point C that lies on the line A'B.
I don't know if this would generalize well to 3 or more points.

What metric is used for the distance function D? Euclidean?

Even though there is only one main road, do we assume that a customer travels in a straight line from their house to the restaurant? Or do they travel directly to the y axis first? (Or in other words, do we use Euclidean or Manhattan distance for D?)

(This can be worked out from the example but it would be nice to have it stated explicitly.)

@trichoplax Euclidean? Does Euclidean mean sqrt(diffX^2 + diffY^2)? Then Euclidean. I know it doesn't fit the scenario perfectly but assume that the customer travels in a straight line somehow from his/her house.

Can the input be taken in our language's preferred form from STDIN?

@isaacg sure but as long as you don't do anything absurd as in "for my program, the input should also include the output or the program won't work"

Is taking input as a list of complex numbers representing houses' positions on the complex plane acceptable?

@ThomasKwa I think that's fine

C, 315 302 bytes
t,i;double o,w,h,x,y,k,a,b,c;double g(N,S)double N,S[][2];{for(t=0;t<N;t++)k+=S[t][1];k/=N;for(i=0;i<9;i++){o=w=h=0;for(t=0;t<N;t++)x=S[t][0],y=S[t][1],a=y-k,c=k*k-2*k*y+x*x+y*y,o+=-a/sqrt(x*x+a*a),w+=x*x/pow(c,1.5),h+=3*x*x*a/pow(c,2.5);a=h/2;b=w-h*k;c=o-w*k+a*k*k;k=(-b+sqrt(b*b-4*a*c))/h;}return k;}

This is far from pretty, and it's not short either. I figured since I'm not going to win the length contest, I can try to win the (theoretical) accuracy contest! The code is probably an order of magnitude or two faster than the bruteforce solution, and relies on a bit of mathematical tomfoolery.
We define a function g(N,S) which takes as input the number of houses, N, and an array of houses S[][2].
Here it is unraveled, with a test case:
t,i;
double o,w,h,x,y,k,a,b,c;
double g(N,S)double N,S[][2];{
    /* Initially, let k hold the geometric mean of given y-values */
    for(t=0;t<N;t++)
        k+=S[t][1];
    k/=N;

    /* We approximate 9 times to ensure accuracy */
    for(i=0;i<9;i++){
        o=w=h=0;
        for(t=0;t<N;t++)
            /* Here, we are making running totals of partial derivatives */
            /* o is the first, w the second, and h the third*/
            x=S[t][0],
            y=S[t][1],
            a=y-k,
            c=k*k-2*k*y+x*x+y*y,
            o+=-a/sqrt(x*x+a*a),
            w+=x*x/pow(c,1.5),
            h+=3*x*x*a/pow(c,2.5);
        /* We now use these derivatives to find a (hopefully) closer k */
        a=h/2;
        b=w-h*k;
        c=o-w*k+a*k*k;
        k=(-b+sqrt(b*b-4*a*c))/h;
    }
    return k;
}
/* Our testing code */
int main(int argc, char** argv) {
    double test[2][2] = {
        {5.7, 3.2},
        {8.9, 8.1}
    };
    printf("%.20lf\n", g(2, test));
    return 0;
}

Which outputs:
5.11301369863013732697

Warning: Knowledge of some calculus may be required for a complete understanding!
So, let's talk about the math.
We know the distance from our desired point (0, k) and a house i:

And thus the total distance D from n houses can be defined as follows:

What we would like to do is minimize this function by taking a derivative with respect to k and setting it equal to 0. Let's try it. We know that the derivatives of D can be described as follows:

But the first partial derivative of each Di is pretty bad...

Unfortunately, even with n == 2, setting these derivatives to 0 and solving for k becomes disastrous very quickly. We need a more robust method, even if it requires some approximation.
Enter Taylor Polynomials.
If we know the value of D(k0) as well as all of D's derivatives at k0, we can rewrite D as a Taylor Series:

Now, this formula's got a bunch of stuff in it, and its derivatives can get pretty unwieldy, but we now have a polynomial approximation of D!
Doing a little bit of calculus, we find the next two derivatives of D by evaluating the derivatives of Di, just as before:

By truncation and evaluating the derivatives, we may now approximate D as a 3rd degree polynomial of the form:

Where A, B, C, D are simply real numbers.
Now this we can minimize. When we take a derivative and set it equal to 0, we will end up with an equation of the form:

Doing the calculus and substitutions, we come up with these formulas for a, b, and c:

Now our problem gives us 2 solutions given by the quadratic formula:

The entire formula for k would be a massive burden to write out, so we do it in pieces here and in the code.
Since we know that the higher k will always result in the minimum distance of our approximate D (I have a truly marvelous proof of this, which the margin of this paper is insufficient to contain...) we do not even have to consider the smaller of the solutions.
One final problem remains. For accuracy purposes, it is necessary that we begin with a k0 that is at least in the ballpark of where we expect the answer to be. For this purpose, my code chooses the geometric mean of the y-values of every house.
As a fail-safe, we repeat the entire problem again 9 times, replacing k0 with k at every iteration, to ensure accuracy.
I haven't done the math about how many iterations and how many derivatives are truly necessary, but I've opted to err on the side of caution until I can confirm accuracy.
If you made it through that with me, thank you so much! I hope you understood, and if you spot any mistakes (of which there are likely many, I'm very tired), please let me know!

I, for one, would love to see the explanation of your math.

@DLosc Your wish is my command.

That's truly marvelous.  I considered trying Newton's Method, but didn't think of Taylor series.

I wish I could upvote this more.

@AlexA. I wish you could upvote me more too ;D Within a day or so, I'll remove the Fermat's last theorem reference and replace it with a proof. Just as soon as I find one.

@BrainSteel: This guy may be able to help.

TI-BASIC, 20
fMin(sum(abs(iX-Ans)),X,~E99,E99

Takes input on the homescreen of your TI-83 or 84 series calculator in this form (You can type a 2: first, which would be ignored):
{5.7+3.2i,8.9+8.1i}:[program name]

If the houses are always less than a billion km away from the origin, E99 can be replaced with E9 for a size of 18 bytes.
Were there a golfing language based on Mathematica, it could win this challenge in 10-14 bytes.

Mathematica, 42 bytes
k/.Last@Minimize[Tr[Norm[#-{0,k}]&/@#],k]&

This is an anonymous function taking a list of pairs as the house coordinates and returning the desired y coordinate.
It's a fairly straightforward implementation. We map Norm[#-{0,k}]& onto each house coordinate (which computes the distance to an undetermined point {0,k} on the y axis) and sum them all up with Tr[...] (for trace, which is equivalent to Total for 1-d lists). Then we use the convenient Minimize to find the minimum of this sum in k. This gives a result of the form {distance, {k -> position}, so we need k/.Last@ to extract the position we're looking for.

Pyth, 33 bytes
hosm.a,d,0NQcR^T3rhKSms*^T3ekQheK

This is the brute force solution: It orders all possible locations of the restaurant, with a resolution of .001 km, by their total distance from the houses, then selects the one with the least total distance. It takes the house locations as a list of 2 entry lists of floats on STDIN.
Demonstration.
The resolution could be set anywhere from 1e-2 km to 1e-10 km at the same code length, but with exponential slowdowns in runtime.
I feel like this could be golfed some more, I'll look at it again later.

Lol! Did you copy my solution? ;-)

@Jakube The matching ^T3 is especially impressive.

We really need a float range.

Python 2, 312
from math import*;A,L,p=[map(float,raw_input().split()) for i in range(input())],lambda a:a[1],0.001
def R(m,M,s):
 while m<=M:yield m;m+=s
m=min(A,key=L)[1];M=max(A,key=L)[1];r=(m+M)/2;s=r-m
while s>p:D={y:sum([sqrt(X*X+(Y-y)**2)for X,Y in A])for y in R(r-s,r+s,s*p)};r=min(D,key=D.get);s*=p;m=r-s;M=r+s
print r

R, 145 143 126
Lots of golfing room left on this I suspect.  Pretty much a brute force method.  I would like to find a nicer way to do this.  I though Geometric Means might help, but alas no.
r=sapply(seq(min((p=matrix(scan(),nr=2))),max(p),.001),function(X,p)c(X,sum((p[1,]^2+(p[2,]-X)^2)^.5)),p);r[1,order(r[2,])[1]]

Test run
> r=sapply(seq(min((p=matrix(scan(),nr=2))),max(p),.001),function(X,p)c(X,sum((p[1,]^2+(p[2,]-X)^2)^.5)),p);r[1,order(r[2,])[1]]
1: 5.7 3.2
3: 8.9 8.1
5:
Read 4 items
[1] 5.113
>

As a matter of interest, if there is just two houses to consider the following will return an acceptable result.  However it falls over on three.  I can't take it any further at the moment, but I thought some of the brains here might be able to do something with it.
p=matrix(scan(),nr=2);weighted.mean(p[2,],sum(p[1,])-p[1,])

MATLAB, 42
If it is OK to take input as
I=[5.7 3.2
    8.9 8.1]

then this statement
fminunc(@(y)sum(hypot(I(:,1),I(:,2)-y)),0)

returns 5.113014445748538.
Shamelessly stealing Thomas Kwa's method, you could get it down to 30 at least:
I=[5.7+3.2i 8.9+8.1i];
fminunc(@(y)sum(abs(I-i*y)),0)

Can it be extended to work with n number of house? Since it is what the question is asking for.

Yeah it works with any number of rows in I.

authors: n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳

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


text:
Clarence the Slow Typist
Introduction
Clarence is a data entry clerk who works at an internet service provider. His job is to manually enter the IP addresses of all of the ISP's customers into the database. He does this using a keypad which has the following layout:
123
456
789
.0
The distance between the centre of horizontally or vertically adjacent keys is exactly one centimetre. For instance, the distance between the centres of 3 and 9 would be two centimetres. The distance between the centres of 3 and 5 would be √2cm. The Pythagoras theorem is sufficient to calculate the distance between any two keys.
Clarence, as you might expect from one who works in an ISP, uses a very slow and inefficient system of typing. He uses a single finger and searches for the key, and then moves his finger to the key, then presses it, and repeats for all of the digits in the number. You might know of this style as the "eagle search system" since the finger searches above the keyboard for the correct key before plunging down for the keypress, like an eagle plunging down for a kill.
For example, here is how Clarence would type out the number 7851:

He starts his finger at 7 and pushes the key.
He moves his finger to the right 1cm to 8 and pushes the key.
He moves his finger upwards 1cm to 5 and pushes the key.
He moves his finger diagonally upwards and left √2cm to 1 and pushes the key.

Therefore the total distance that Clarence moved his finger to type in 7851 is 1 + 1 + √2 which is about 3.41cm.
Your task is to write a program that calculates the distance Clarence must move his finger to type in arbitrary IP addresses.
Input Description
Input is a string that will be in the form
().().().()
where each () is an integer in the range 0 - 999. This represents the IP address that Clarence must type in. An example input might be:
219.45.143.143
I would also like to point out that inputs such as 0.42.42.42 or 999.999.999.999 are still valid inputs, despite the fact that they are invalid IP addresses. So you don't need to include any IP address verification code in your program.
Output Description
Output the distance that Clarence must move his finger in order to type in the specified IP address. Round answers to two decimal places where needed, and use the cm unit in your output. The output for the example input is 27.38cm (1 + √8 + √5 + 2 + 1 + √5 + 3 + 1 + √5 + √13 + 3 + 1 + √5).

Man, ISPs have weird keyboards...

I wonder if anyone's entry will actually make use of the dotted quad format, or if most/all will just accept any arbitrary string of [0-9.]+

@Sparr: At least it excludes the possibility of a one- character input, which would be real pain in CJam.

Can you clarify what forms of input are allowed? Since you say "program", does this imply that you expect a full program that takes input from stdin or command line arguments? Or is a function that takes a string as argument also acceptable?

@RetoKoradi I expect a program, yes. stdin, command line arguments, or user input functions are acceptable.

@dacapoaria - 'eagle search' is also known as 'hunt and peck' or 'search and destroy' for the more heavy-handed typists.

@MathiasFoster Search and Destroy typing gives me an interesting mental image. Thanks for telling me these different terms.

Why 0-999 when IPs can only be 0-255?

@ArtofCode Clarence works at an ISP, and sometimes the ISP sends him the invalid data to type into the database. Clarence types the data in anyway. That's the canonical reason anyway. The actual reason is because I overlooked that when writing the spec.

Considering only the valid range (0-255) IP Addresses, which should be the optimum arrangement of the keyboard to type all that addresses in the shortest path?

@IsraelMorales Hmmm... my hunch would be that you'd have the . in the middle, 2, 5, 1, and 3 adjacent, 9 and 8 outside of the square and the remaining ones in the corners. That's just my guess though.

CJam, 46 44 43 38 37 34 bytes
rA,sd`f#3fmd2/2ew::.-::mh:+2mO"cm"

Thanks to @user23013 for suggesting mh, which made it possible to save 5 bytes.
Try it online in the CJam interpreter.
How it works
r     e# Read a token from STDIN.
A,    e# Push [0 1 2 3 4 5 6 7 8 9].
s     e# Stringify: [0 1 2 3 4 5 6 7 8 9] -> "0123456789"
d     e# Cast to Double: "0123456789" -> 123456789.0
`     e# Inspect: 123456789.0 -> "123456789.0"
f#    e# Push the index of each character from the input in "123456789.0".
3fmd  e# Push the quotient and residue of each index divided by 3.
2/    e# Split the resulting array into pairs.
2ew   e# Convert the array of pairs in the array of all overlapping pairs of pair.
::.-  e# Reduce each pair using vectorized difference: [[a b][c d]] -> [a-b c-d]
::mh  e# Reduce each reduced pair to its 2-norm distance: [a b] -> sqrt(aa + bb)
:+    e# Sum all distances.
2mO   e# Round to two decimal places.
"cm"  e# Push "cm".

{3fmd~@-@@-mh}%.

@user23013: Thanks. I had no idea mh even existed.

Pyth, 38 35 34 bytes
+.Rs.aM-M.:m.jF.Dx`ciUTT1b3z2 2"cm

Demonstration.
Indexing into the string of a float idea thanks to @Dennis.
Explanation, on the phony input 15.0:

First, we take the input. It is implicitly stored in z. '15.0'
We map this list as follows: m.jF.Dx`ciUTT1k3z.

UT: We generate the list [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].
iUTT: Next, we treat this list as a base 10 number giving us 123456789.
ciUTT1: Next, we convert this number to a float by floating point dividing it by 1, giving 123456789.0.
`: Convert to a string. '123456789.0'
x    k: Take the index of the input character in that string. [0, 4, 9, 10].
.D    3: .D is the divmod function, outputing its first input divided and modulo'd by the second input. The second input is 3, here. This gives the physical location of the character on the numpad. [(0, 0), (1, 1), (3, 0), (3, 1)].
.jF: .j is the complex number constructor. F applies it to the tuple. [0j, (1+1j), (3+0j), (3+1j)].

.:    2: Now, we take the 2 entry substrings of this list so we can find the pairwise distances. [[0j, (1+1j)], [(1+1j), (3+0j)], [(3+0j), (3+1j)]].
-M: Takes the difference of the two complex numbers. [(-1-1j), (-2+1j), -1j].
.aM: Takes the absolute value of the result. This is the distance between the keypad locations. [1.4142135623730951, 2.23606797749979, 1.0]
s: Sum the distances. 4.650281539872885.
.R    2: Round to 2 decimal places. 4.65.
+    "cm: Add 'cm' to the end and print. 4.65cm.

PHP - 108 Bytes
<?for(;$v=strpos(-.987654321,fgetc(STDIN));$l=$v)$l&&$t+=hypot($l/3%4-$v/3%4,$l%3-$v%3);printf('%.2fcm',$t);

Input is taken from stdin. The -.987654321 sent to the strpos function evaluates to '-0.987654321' in a string context.

Sample usage:
$ echo 219.45.143.143 | php isp.php
27.38cm

C, 192 177 159 bytes
Updated version, now complete program using command line argument. At the same time, improved to still be shorter than previous version:
#define G c=*a[1]++,c=c>48?c-49:c/2-14,u=c%3,v=c/3
float r;c,u,v,p,q;main(int n,char**a){for(G;*a[1];)p=u,q=v,G,p-=u,q-=v,r+=sqrt(p*p+q*q);printf("%.2fcm",r);}

Ungolfed:
#include <stdio.h>
#include <math.h>

float r;
int c, u, v, p, q;

int main(int n, char** a) {
    c = *a[1]++;
    c = c > 48 ? c - 49 : c / 2 - 14;
    u = c % 3;
    v = c / 3;
    for ( ; *a[1]; ) {
        p = u;
        q = v;
        c = *a[1]++;
        c = c > 48 ? c - 49 : c / 2 - 14;
        u = c % 3;
        v = c / 3;
        p -= u;
        q -= v;
        r += sqrt(p * p + q * q);
    }

    printf("%.2fcm",r);

    return 0;
}

The golfed version uses a preprocessor #define to shorten some of the repeated code in the full version.

Your golfed version is missing a semicolon at the end. 2. Your golfed version is producing incorrect results, since you increment s before checking that *s is non-zero. 3. The OP said program in his post. I'm not sure if a function is accepted. 4. With GCC, you don't need the include. 5. sqrt is shorter than sqrtf. 6. pow(u-p,2) is shorter than (u-p)*(u-p). 7. I'm not sure, but I think storing both coordinates in a single string and setting u=x[c]/3 and v=x[c]%3 should be shorter.

Fixed the correctness problem. Turns out that I kept compiling an earlier version while doing fine tuning. Sorry about that. 1, 2. Fixed. I was actually surprised that I could leave them away. The broken testing would explain it... 3. Based on what I saw on wiki/meta, it sounded like taking the input as function arguments is an allowed option if the input is not explicitly specified. I'll change it if my interpretation is incorrect. 4. I always thought that only functions that return int could be used undeclared. But indeed, clang also accepts it with a warning, so I got rid of it.

The wiki states that functions are allowed by the default, yes, but the OP wrote your task is to write a program... You don't need the brackets you introduced if you write the loop as p=u,q=v,G,r+=....

I asked the OP for clarification on the input requirements. On the code, I rolled it back to a slightly older version before I optimized it into incorrectness. I'll take another shot at tuning it tomorrow, but I didn't want to leave a broken version standing for too long. Thanks for the pointers.

@Dennis Ok, updated version should be better in every way. Now a complete program, and still shorter thanks to some optimizations. Thanks again for letting me know about the problems with the initial version.

JavaScript (ES6), 132
I/O via popup. Run the snippet to test (Firefox only)

[for(a of prompt(d=''))[p,q,d]=[x=(a=a<'0'?9:-a?a-1:10)%3,y=a/3|0,d!==''?d+Math.sqrt((p-=x)*p+(q-=y)*q):0]],alert(d.toFixed(2)+'cm')

Python 3, 108 bytes
L=[x//3*1j+x%3for x in map("123456789.0".find,input())]
print("%.2fcm"%sum(abs(a-b)for a,b in zip(L,L[1:])))

Admittedly not very well golfed, but at least it ties with PHP.

Ruby 135 139
s=0
gets.chars.each_cons(2).map{|a|i,j=a.map{|e|'123456789.0'.index e}
i&&j&&s+=((i%3-j%3)**2+(i/3-j/3)**2)**0.5}
print s.round(2),'cm'

Test it online: http://ideone.com/2CIQa5

Python 199  171 166
There's a shorter Python code (108) for this by SP3000:
https://codegolf.stackexchange.com/a/50854/41163

import sys
p=r=0
for i in sys.argv[1]:
 c=3,0
 if i!=".":c=divmod(int(i)-1,3)
 if i<1:c=3,1
 if p:r+=((p[1]-c[1])**2+(p[0]-c[0])**2)**0.5
 p=c
print"%.2fcm"%r

Sample usage:
$ python isp.py 219.45.143.143
27.38cm

Run online: http://codepad.org/h9CWCBNO
Commented code
import sys

# p - last position as (y,x) tuple - initialized with 0, because "if 0" -> equals to "False"
p = 0
# r - result of adding all distances - ini with 0, because not moved any distances on start
r = 0

# Loop over chars
for char in sys.argv[1]:
   # c - current position of typist as (y,x) tuple

   # Always set c to position of "." key
   c = 3,0 # lazy for c=(3,0)

   # Check if char is not the "." key
   if char !=".":

      # Get position of char on keypad
      c=divmod(int(char)-1,3)

      if char<1:
         c=3,1

   # If this is the first char,
   # then STORE_OPERATION has not been executed,
   # so p is still p=0 from original initialization
   # calling "if 0" evaluates to False,
   # so we jump this code block, for the first char
   if p:
      # calculate delta of x, y from current and last position,
      # then add both deltas squared (**2),
      # then get square root of it (**0.5 = **1/2)
      # add to r (+=)
      r+=( (p[1]-c[1])**2 + (p[0]-c[0])**2 )**0.5

   # STORE_OPERATION - Store current position as last position
   p = c

# .2f returns r with 2 trailing digits
print"%.2fcm"%r

You can save some bytes by defining if clauses on one line, like if i<1:c=3,1

You can add syntax highlighting by putting this comment at the top of your post: <!-- language: lang-python -->


text:
What is the Probability that a Knight Stays on Chessboard?
Given the size of the chess board and initial position of the knight, calculate the probability that after k moves the knight will be inside the chess board.
Note:

The knight makes its all 8 possible moves with equal probability.
Once the knight is outside the chess board it cannot come back inside.

Input
Inputs are comma separated in the form:
l,k,x,y

where l is the length and width of the chess board, k is the number of moves the knight will make, x is the x-position of the initial position of the knight, and y is the y-position of the initial position of the knight. Note that 0,0 is the bottom-left corner of the board and l-1,l-1 is the top-right corner of the board.
Algorithm:
Start with the initial coordinates of the knight. Make all possible moves for this position and multiply these moves with their probability, for each move recursively call the function continue this process till the terminating condition is met. Terminating condition is if the knight is outside the chess board, in this case return 0, or the desired number of moves is exhausted, in this case return 1.
As we can see that the current state of the recursion is dependent only on the current coordinates and number of steps done so far. Therefore we can memorize this information in a tabular form.
Credit
This challenge is originally from a blog post of crazyforcode.com published under the CC BY-NC-ND 2.5 IN licence. It was slightly modified to make it a bit more challenging.

@Edi - Can you clarify the input format and parameters a bit more ? Everything else looks okay imo.

Why do you prescribe an exact algorithm? I'm not sure if there actually is a more elegant alternative, but requiring a specific algorithm could potentially prevent other clever approaches. Also, I don't think you need to specify the coordinate system in so much detail - it doesn't affect the probability at all.

@MartinBüttner I actually edited in the entire Input section. I specified the coordinate system since I figured someone might ask about it if I left it missing.

"Inputs are comma separated in the form: l,k,x,y" - so the input is a string that we have to parse? Is it not acceptable to write a function that takes 4 parameters?

@Edi Don't mark an answer as 'accepted' if there has been no time for other people to give it a try - marking something as accepted so is basically saying 'The challenge is over' - while most of the world has probably not even had time to look at it!

@w0lf that's what the currently accepted answer does. So it is 'yes'

The title and first paragraph imply that we should be calculating probability, but the Algorithm section says to return either 0 or 1. Could you make it a bit more clear as to what we're supposed to end up with?

@M.I.Wright when stopping recursion you return 1 or 0, but the returned values are summed and multiplied by their probability (that is 1/8). You end up with a probability value between 0 and 1 indeed

Can the knight leave the board, and come back on?

@JNF  No: Once the knight is outside the chess board it cannot come back inside.

In the 5x5 square shown there are just 6 different positions, equivalent by symmetry. In a k x k square the number is ..... Each position has a probability of switching to one of the other positions. So there is a simple recursive formula. Or have I missed something?

@JohnBibby Nope, that's correct. Like it's written in the challenge post, there's a simple recursive algorithm. Your job is to implement the recursion in the least amount of chars.

@sanchises okay.

@Edi Please stop posting random challenges you find on the web. Plagiarism is frowned on by our community. Challenges from ongoing programming competitions have no business here at all, since they may help someone winning this competition. And are challenges, which are discussed in a blog post, like this chess challenge (original source), will not be well-received here. One reason is, that the original source may have some sort of copyright.

@Edi For instance the source of this challenge allows copying and redistributing, but only if you give appropriate credit.

Pyth, 38 bytes
M?smcgtGd8fq5sm^-Fk2C,TH^UhQ2G1g@Q1>Q2

Try it online: Demonstration
Explanation:
                                        implicit: Q = evaluated input
M                                       define a function g(G,H): //G=depth, H=current cell
                         UhQ              the list [0,1,...,Q[0]-1]
                        ^   2             Cartesian product, gives all cells
          f                               filter for numbers numbers T, which satisfy:
                    C,TH                    zip(T,H)
              m                             map the two pairs k to:
                -Fk                           their difference
               ^   2                          squared
             s                              sum (distance squared)
           q5                               == 5
   m                                      map each valid cell d to:
     gtHd                                   g(G-1,d)
    c    8                                  divided by 8
  s                                       return sum
 ?                           G          if G > 0 else
                              1           return 1

                               g@Q1>Q2  call g(Q[1],Q[2:]) and print

Seems to me that if we're going to create super-concise languages for the sole purpose of golfing, we might as well implement the required algorithm as a primitive.

@mc0e No, that would be a standard forbidden loophole. See here.

can we get the non-golfed code pls ?

@YaShChaudhary Do you mean the version with 39 bytes, or the version with 40 bytes. :-P
I'm afraid there never existed a truly non-golfed version. I wrote this code directly in Pyth, and Pyth programs are always short.

@Jakube ohk np :)

Ruby 134
->l,m,x,y{!((r=0...l)===x&&r===y)?0:m<1?1:(0..7).map{|i|a,b=[1,2].rotate i[2]
P[l,m-1,x+a*(i[0]*2-1),y+b*(i[1]*2-1)]/8.0}.inject(:+)}

Try it online: http://ideone.com/ZIjOmP
The equivalent non-golfed code:
def probability_to_stay_on_board(board_size, move_count, x, y)
  range = 0...board_size
  return 0 unless range===x && range===y
  return 1 if move_count < 1

  possible_new_locations = (0..7).map do |i|
    dx, dy = [1,2].rotate i[2]
    dx *= i[0]*2-1
    dy *= i[1]*2-1

    [x+dx, y+dy]
  end

  possible_new_locations.map do |new_x, new_y|
    probability_to_stay_on_board(board_size, move_count-1, new_x, new_y) / 8.0
  end.inject :+
end

Matlab, 124 119
Exactly implements the described algorithm.
I was able to shorten it by 5 bytes with some help of @sanchises, thanks!
function s=c(l,k,x,y);m=zeros(5);m([2,4,10,20])=1/8;s(l,l)=0;s(l-y,x+1)=1;for i=1:k;s=conv2(s,m+m','s');end;s=sum(s(:))

Expanded:
function s=c(l,k,x,y);
    m=zeros(5);
    m([2,4,10,20])=1/8;
    s(l,l)=0;s(l-y,x+1)=1;
    for i=1:k;
        s=conv2(s,m+m','s');
    end;
    s=sum(s(:))

Old version
function s=c(l,k,x,y);
    m =zeros(5);m([1:3,5,8,10:12]*2)=1/8;
    s=zeros(l);
    s(l-y,x+1)=1;
    for i=1:k
        s=conv2(s,m,'s');
    end
    s=sum(s(:));

One hint: s is initialized by MATLAB, so you can just do s(l,l)=0; Too bad MATLAB does not have fibonnaci as a built-in function, that would be a great optimization for m.

That is a super awesome trick, thanks! I am still tryting to find a shorter way of creating m by a matrix decomposition...

Yeah, I was looking at it for a while too. Perhaps some smart logical indexing, but I can't think of anything. m+m'+fliplr(m+m') seems to be an increase in bytecount, and so are all my other options.

Haskell - 235
Implements a function f with parameters l k x y
import Data.List
g[]=[]
g((a,b):r)=[(a+c,b+d)|(c,d)<-zip[-2,-1,1,2,-2,-1,1,2][1,2,-2,-1,-1,-2,2,1]]++g r
h _ 0 a=a
h l a b=h l(a-1)$filter(\(a,b)->(elem a[0..l])&&(elem b[0..l]))$g b
f l k x y=(sum$map(\x->1.0) (h l k [(x,y)]))/(8**k)

Mathematica - 137
q = # {1, 2} & /@ Tuples[{-1, 1}, 2]
q = Reverse /@ q~Union~q
g[l_, k_, x_, y_] :=

 Which[
  k < 1,
  1,

  !0 <= x < l || ! 0 <= y < l,
  0,

  0<1,
  Mean[g[l, k - 1, x + #[[1]], y + #[[2]]] & /@ q]
]

Usage:
g[5,5,1,2]

Output:
9/64

MATLAB - 106
function s=c(l,k,x,y);m(5,5)=0;m([2,4,10,20])=1/8;s=ones(l);for i=1:k;s=conv2(s,m+m','s');end;s=s(l-y,x+1)

Improves on @flawr's solution by being more MATLAB-y.
Expanded:
function s=c(l,k,x,y)
    m(5,5)=0;
    m([2,4,10,20])=1/8;
    s=ones(l);
    for i=1:k
        s=conv2(s,m+m','s');
    end
    s=s(l-y,x+1)

><> - 620 (not counting whitespace)
Initial stack should be l,k,x,y
{:a2*0p   v
vp0*3a*}:{<
>{1+&a3*0g}v                   >          >       >          >~~01-01-v             >          >       >          >~~01-01-v             >          >       >          >~~01-01-v             >          >       >          >~~01-01-v
           >&1-:&?!v>:@@:@@:0(?^:a2*0g1-)?^2-$:0(?^:a2*0g1-)?^1-      >}}$:@@:@@:0(?^:a2*0g1-)?^2-$:0(?^:a2*0g1-)?^1+      >}}$:@@:@@:0(?^:a2*0g1-)?^2+$:0(?^:a2*0g1-)?^1-      >}}$:@@:@@:0(?^:a2*0g1-)?^2+$:0(?^:a2*0g1-)?^1+      >}}$:@@:@v
v1         ^}       ^!?=g0*3a:~~}}<      +2v?)-1g0*2a:v?(0:$+1v?)-1g0*2a:v?(0:@@:@@:$}}<      -2v?)-1g0*2a:v?(0:$+1v?)-1g0*2a:v?(0:@@:@@:$}}<      +2v?)-1g0*2a:v?(0:$-1v?)-1g0*2a:v?(0:@@:@@:$}}<-2      v?)-1g0*2a:v?(0:$-1v?)-1g0*2a:v?(0:@<
>a3*0g=   ?^\      &              ^-10-10~~<          <       <          <             ^-10-10~~<          <       <          <             ^-10-10~~<          <       <          <             ^-10-10~~<          <       <          <
\         :{/
v                  >~{~l2,&0
>@:0(?v:a2*0g1-)?v$:0(?v:a2*0g1-)?v1>@~~+l1=?v
      >          >     >          >0^        >&,n;

Test it out


text:
Number of ways to sum [1..n] with [n+1..2n] such that each sum is prime
Let \$n > 0\$. Let \$X = 1, 2,...,n\$ and \$Y = n+1, n+2, ..., 2n\$. Define \$a(n)\$ as the number of permutations \$p\$ of \$Y\$ such that every element of \$X + p(Y)\$ is prime. For example:
n = 2
X = [1,2]
Y = [3,4]
p_0(Y) = [3,4] => X + p0(Y) = [4,6] => No
p_1(Y) = [4,3] => X + p1(Y) = [5,5] => Yes
a(2) = 1

In as few bytes as possible, write a program or function which produces this sequence (A070897), either as an infinite list on STDOUT, or in your interpreter of choice.
The output should start at \$n=1\$, and each entry should be on a newline and undecorated, i.e.:
1
1
1
1
2
...

Examples
\$a(1)=1\$ because each list [1], [2] has only 1 element
\$a(5)=2\$ because there are two permutations: [(1,10),(2,9),(3,8),(4,7),(5,6)] and [(1,6),(2,9),(3,10),(4,7),(5,8)]
Rules
No built-in primality tests. No lookup table ;). No standard loopholes.

So we have to output an infinite list ? All programs will be non-terminating then and for most of them, you won't be even able to see the output as the output will be provided on program termination only.

I'd suggest first N elements of the list...

I like non-terminating in this case, it's a little different to normal.

Do we have to print the results as we calculate them ? Or we are good if we can print them in one shot at the end of the program .. (which is most probably due to crashing by out of memory error)

They should be printed as they are calculated.

Is using built in prime factorization methods allowed ? (I thought they are automatically disallowed when you say no built in prime tests)

I'd say a prime factorisation method is a prime test...

Pyth - 35 32 27 bytes
The obvious approach. The while loop logic is taking a lot of bytes. Thanks to @Jakube for telling me about .V and saving a lot of bytes. Explanation coming soon.
.V1lf!sm%h.!J++hbd@TdhJb.pb

Try first n here online

@Optimizer if you run it locally. Instant and infinite output are both obviously impossible online.

@Optimizer nope, its a built-in prime factorization function. :)

@Optimizer ok, i'll change it.

@Jakube shoot, Pyth has an infinite map, did not realize that. I'm feeling pretty stupid now.

@Jakube the .V really helped, but yours seems not to be working. You seem to be doing permutations on a urange instead of n+1...2n.

@Jakube oh, sorry.

CJam, 38 35 32 bytes
0{)_e!{ee{1b1$+)_m!)\)%},!},,p}h

This is an infinite list version. If you run it using the Java compiler, you will keep on getting result for increasing n on each line until the program crashes (if it does. Did not test).
For sanity, run the finite version using this link. You can change the number in the input to see a longer list.
How it works:
0{                            }h  e# This acts as an infinite do-while loop here
  )_                              e# Starting from 0, increment the number and copy it
                                  e# Lets call this number at each iteration as N
    e!                            e# Get all possible permutations of the array 0..N-1
      {                   },      e# Filter the list of permutations based on this code block
       ee                         e# Convert the permutation array into an [index value]
                                  e# pair array. For ex. [5 2]ee gives [[0 5] [1 2]]
         {             },         e# Pass each index value pair through this filter
          1b1$+)                  e# Sum the index and value and add current N + 1 to it
                                  e# At this point, we have something equivalent to
                                  e# pairwise addition of [1 .. n] and [n .. 2n - 1]
                _m!)\)%           e# Now we do ((N - 1)! + 1)%N to see if N is prime
                                  e# This is Wilson's theorem and will give 0 for primes
                         !        e# Now we have a filtered index-value pairs which all
                                  e# correspond to non-prime numbers. If the list is empty,
                                  e# Then all numbers are prime. Thus we do a ! on empty list
                                  e# to get truthy.
                            ,p    e# Take the total permutations where X + pN(Y) are all
                                  e# primes and print the number to STDOUT immediately
                                  e# We are left with the initial incremented N on stack
                                  e# which is always non-zero, so the loop continues
                                  e# infinitely

UPDATE: 2 bytes saved, thanks to Martin!

Upvote for sanity. I think that time will end before you get an integer overflow though ;)

Python 2, 147 bytes
from itertools import*
n=1;R=range
while n:print sum(all(x%d for x in map(sum,zip(R(n),c))for d in R(2,x))for c in permutations(R(n+2,2*n+2)));n+=1

The import itertools rule of thumb tells me there's probably a better way...
A few bytes are saved by summing [0 ... n-1] with [n+2 ... 2n+1] instead.

Jelly, 20 bytes
+RŒ!+€RÆḍỊP€SṄ¬
1Ç1#

Try it online!
This gets exponentially slower for each new \$n\$ it calculates, so times out on TIO after having printed \$a(9) = 40\$. Given enough time/memory however, it will eventually print all the elements in the sequence.
How it works
1Ç1# - Main link. No arguments
1    - Starting from n = 1...
   # - ...count up n = 1, 2, ...
  1  - ...until 1 n returns true when...
 Ç   - ...run over the helper link.
       As the helper link ends with ¬ (logical NOT), no n will return true

+RŒ!+€RÆḍỊP€SṄ¬ - Helper link. Takes n on the left
 R              - [1, 2, ..., n]
+               - [n+1, n+2, ..., 2n]
  Œ!            - All permutations
      R         - [1, 2, ..., n]
     €          - For each perumation:
    +           -   Add [1, 2, ..., n] elementwise
       Æḍ       - Proper divisor counts
         Ị      - Equal to 1?
           €    - For each:
          P     -   All true?
            S   - Count the true permutations
             Ṅ  - Print
              ¬ - Logical NOT to continue the infinite loop

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


text:
Temperature Converter
This is a byte sized challenge where you have to convert an input temperature in one of the three units (Celsius, Kelvin and Fahrenheit) to the other two.
Input
You would be provided with a temperature as a number followed by a unit (separated by space). The temperature can be an integer or a floating point number (23 vs 23.0 or 23.678).
You can submit a function or a full program that reads the space separated string from STDIN/ARGV/function argument or the closest equivalent and prints the output to STDOUT or closest equivalent.
Output
Your output should be the temperature converted to the other two formats, separated by a newline and followed by the corresponding unit character on each line (optionally separated by a space). The order of the two units does not matter.
Output precision

The converted number should be accurate to at least 4 decimal places without rounding.
Trailing zeroes or decimal places are optional as long as first 4 decimal places (without rounding) are precise. You can also skip the 4 zeroes and/or the decimal point in case the actual answer has 4 zeroes after the decimal point.
There should not be any leading zeroes
Any number format is acceptable as long as it fulfills the above three requirements.

Unit representation
Unit of temperature can only be one of the following:

C for Celsius
K for Kelvin
F for Fahrenheit

Examples
Input:
23 C

Output:
73.4 F
296.15 K

Input:
86.987 F

Output:
303.6983 K
30.5483 C

Input:
56.99999999 K

Output:
-216.1500 C
-357.0700 F

This is code-golf so shortest entry in bytes wins! Happy Golfing!
Leaderboard

I assume the outputs can be in any order. Is it acceptable for all three formats to be output, for example 23C\n73.4F\n296.15K ? or must the input format be supressed?

@steveverrill the order bit is mentioned in the output section. You have to only output the other two formats.

About output precision: 2/3 => 0.666666666666 is accurate to the 4th digits? (I'd say YES). Or should it be 0.6667?

@edc65 0.666666666666 is correct. I am enforcing a no-rounding based precision. so 0.6666 is the alternative.

@edc65 infact, if you actually need rounding, 0.66667 is correct as well as rounded for you.

Another minor point I think it would be useful to specify in the question the formulas to be used. I've checked and it seems the formulas you are using are correct according to modern definitions. The strange thing is that VSMOW ("standard" water of a specific isotopic composition) does not freeze at exactly 0C or boil at exactly 100C. http://en.wikipedia.org/wiki/Celsius

mmm I dont'get the no-rounding part. 0.6667 is a better approximation than 0.6666 to the actual rational number 2/3. It's not a rounding

@edc65 Better in terms of closeness - yes, but here, I am just bothered about correctness to first 4 decimal places. Keeping that in mind, 0.66667 is an even better approximation, right ?

@steveverrill Nice point, but I actually want to avoid providing the formulas as well in the question, as then it would be simply "Program this formula" question. Too much spoon feeding.

No validation of less than absolute zero?

One of the answers does not print a space between temperature and unit. The output rules don't seem to require it, but all the examples say otherwise. Could you clarify?

@Dennis in the output, there is no rule to print the space or not. But it will be present in the input.

CJam, 77 65 60 59 55 54 52 bytes
l~2|"459.67+1.8/'K 273.15-'C 1.8*32+'F"S/m<{~N2$}%6<

Try it online in the CJam interpreter.
How it works
l~    e# Read and evaluate the input: F, K, C -> 15, 20, 12
2|    e# Bitwise OR with 2: F, K, C -> 15, 22, 14 = 0, 1, 2 (mod 3)

"459.67+1.8/'K 273.15-'C 1.8*32+'F"S/

      e# Push ["459.67+1.8/K" "273.15-C" "1.8*32+F"].
      e# These commands convert from F to K, K to C and C to F.

m<    e# Rotate the array of commands by 15, 22 or 14 units to the left.
{     e# For each command:
  ~   e#     Execute it.
  N   e#     Push a linefeed.
  2$  e#     Copy the temperature for the next iteration.
}%    e# Collect all results in an array.
6<    e# Keep only the first 8 elements.

Python 3, 118 116 bytes
I=input()
t=eval(I[:-1])
u=ord(I[-1])%7
exec("u=-~u%3;t=[t*1.8-459.67,(t-32)/1.8,t+273.15][u];print(t,'FCK'[u]);"*2)

Performs the conversions in a rotary order K -> F -> C -> K twice.

Gotta love 'FCK'[u].

Haha what the heck, guys. Upvote the question and answers, not my dumb comment. :P

JavaScript (ES6), 127  130 132 bytes
Waiting for some amazing esolanguage answer, I did not find much to golf here.
Using template string, the  3 newlines are significant and counted.
Run snippet in Firefox to test.

F=x=>([t,u]=x.split(' '),z=273.15,y=9/5,u<'F'?`${t*y+32} F
${+t+z} K`:u<'K'?`${t=(t-32)/y} C
${t+z} K`:`${t-=z} C
${t*y+32} F`)

// Predefined tests

;['23 C','86.987 F','56.99999999 K']
.forEach(v=>O.innerHTML += v+' ->\n'+F(v)+'\n\n')
<input id=I><button onclick='O.innerHTML=F(I.value)'>-></button>

Pip, 58 57 bytes
Ft"CFK"RMbP(a-(o:[32i273.15]Ab%7))*$/95@A[tb]+(oAt%7).s.t

Takes input from command-line arguments.
Formatted and slightly ungolfed:
o:[32 0 273.15]
F t ("CFK" RM b)
  P (a - o@(Ab % 7))
    * "95"@At / "95"@Ab
    + o@(At%7)
    . s . t

Explanation:
The general conversion formula between unit 1 and unit 2 is temp2 = (temp1 - offset1) * mult2 / mult1 + offset2. The offsets could be to absolute zero or to any other convenient temperature; let's use 0 °C.

Unit Mult Offset
C    5    0
K    5    273.15
F    9    32

We'll build lists of these values and index into them based on which unit we're dealing with. Pip doesn't have associative arrays/hashes/dictionaries, so we need to convert the characters into integer indices. Maybe there will be helpful patterns with the ASCII values.

Unit Asc A%2 Mult A%7 A%7%3 Offset
C    67  1   5    4   1     0
K    75  1   5    5   2     273.15
F    70  0   9    0   0     32

This looks promising. One more useful fact: indices in Pip wrap around. So we don't actually need the %3 as long as we're indexing into something of length 3. Defining o:[32 0 273.15] and using (o (Ab)%7) will do the trick. (A gets the ASCII value of a character. The (l i) syntax is used for indexing into iterables, as well as for function calls.)
For the multipliers, we only need the two numbers 9 and 5. Since numbers are the same as strings in Pip, and thus are indexable, getting the multiplier is as simple as 95@Ab (using the other method of indexing, the @ operator).
Using Pip's array-programming features, we can save a character over the naive method:
95@At/95@Ab
$/95@A[tb]    Make a list of t and b, apply 95@A(...) to each item, and fold on /

Finally, add the offset for the new unit, concatenate a space and the new unit's symbol onto the end, and print.
We do this for each t in "CFK" RM b, thus converting to each unit except the original.
Sample invocation:
C:\Golf> pip.py tempConv.pip 86.987 F
30.548333333333332 C
303.6983333333333 K

(For more on Pip, see the repository.)

dc, 102 bytes
I'm pretty sure this can be golfed more, but here's a start:
4k[9*5/32+dn[ F
]n]sf[459.67+5*9/dn[ K
]n]sk[273.15-1/dn[ C
]n]sc[rlfxlkxq]sC[lkxlcxq]sF?dC=CF=Flcxlfx

dc barely makes the grade on this one.  Specifically dc string handling isn't really up to the job.  But all we need to do is differentiate between "C", "F" and "K".  Fortunately dc parses "C" and "F" as hex numerals 12 and 15.  And fo "K" it just leaves 0 on the stack.
Output:
$ dc -f tempconv.dc <<< "23 C"
73.4000 F
296.1500 K
$ dc -f tempconv.dc <<< "86.987 F"
303.6983 K
30.5483 C
$ dc -f tempconv.dc <<< "56.99999999 K"
-216.1500 C
-357.0700 F
$

C, 160 bytes
float v,f[]={1,1.8,1},d[]={0,32,273.15};u,t,j;main(){scanf("%f %c",&v,&u);for(u=u/5-13,v=(v-d[u])/f[u];j<2;)t=(++j+u)%3,printf("%f %c\n",f[t]*v+d[t],"CFK"[t]);}

This reads from stdin. No output precision is specified, so it prints whatever printf() feels like printing, which is mostly more than 4 digits.
Ungolfed version:
#include <stdio.h>

float v, f[] = {1.0f, 1.8f, 1.0f}, d[] = {0.0f, 32.0f, 273.15f};
char u;
int t, j;

int main() {
    scanf("%f %c", &v, &u);
    u = u / 5 - 13;
    v = (v - d[u]) / f[u];
    for( ; j < 2; ) {
        t = (++j + u) % 3;
        printf("%f %c\n", f[t] * v + d[t], "CFK"[t]);
    }

    return 0;
}

Some explanations/remarks:

This is based on lookup tables f and d that contains the multiplication factors and offsets to convert Celsius to any other unit (including Celsius itself, to avoid special cases).
If u is the input unit, u / 5 - 13 maps C to 0, F to 1, and K to 2.
Input is always converted to Celsius.
Loop iterates over the two units that are not the input, and converts the Celsius value to that unit.
The golfed version uses an int variable instead of a char variable to receive the scanf() input. This is a type mismatch, which will only produce correct results on little endian machines (which is almost all of them these days).

Shortened to 152: float v,f[]={1,1.8,1,0,32,273.15};u;main(j){scanf("%f %c",&v,&u);for(u=u/4&3,v-=f[u+3],v/=f[u];j++<3;printf("%f %c\n",f[u]*v+f[u+3],"CFK"[u]))u++,u%=3;}. Gained a bit with fewer variables, moving code around. New assumption is argc=1 (j=1). u = u/4 & 3.

Python 2, 168 Bytes
I saw the Python 3 solution just as I was about to post this, but whatever, I'm just practicing golfing.
s=raw_input().split();v=eval(s[0]);c,t=(v-32)/1.8,v-273.15
print[["%fC\n%fF"%(t,t*1.8+32),"%fK\n%fC"%(c+273.15,c)][s[1]=="F"],"%fK\n%fF"%(v+273.15,v*1.8+32)][s[1]=="C"]

Ungolfed:
def conv(s):
    s = s.split()
    v = float(s[0])
    if s[1]=="C":
        print "%f K\n%f F"%(v+273.15,v*1.8+32)
    elif s[1]=="F":
        v = (v-32)/1.8
        print "%f K\n%f C"%(v+274.15,v)
    else:
        c = v-273.15
        print "%f C\n%f F"%(c,c*1.8+32)

Perl, 85 80 76
#!perl -nl
print$_=/C/?$_+273.15." K":/K/?$_*9/5-459.67." F":5/9*($_-32)." C"for$_,$_

Test me.

PHP, 161 153
function f($i){list($v,$u)=split(" ",$i);$u==C||print($v=$u==K?$v-273.15:($v-32)*5/9)."C\n";$u!=K&&print $v+273.15 ."K\n";$u!=F&&print $v*9/5+32 ."F\n";}

http://3v4l.org/CpvG7
Would be nice to golf out two more characters to get in the top ten...

Well technically, based on the rules, there doesn't need to be spaces between the unit and it's temperature in the output. By my calculation that saves 3 bytes.

Good point :-)  I also found a way to reuse a variable, which saves another handful.

135 byte long solution: http://sandbox.onlinephpfunctions.com/code/303e4c29d9f50e4a5af6e72fff9a39ad7041d454. Basically: removed the \n and changed into real newlines, converted into a full program (receiving the data over GET, eg: http://localhost/my_file.php?t=<temperature>) and replaced $u!=K with $u^K and $u!=F with $u^F. If $u is K, running $u^K will return an empty string, which is a falsy value. Also, your space inside the split was converted into C^c (Just to look cool).

Python 2, 167
s=raw_input();i=eval(s.split()[0]);d={"C":"%f K\n%f F"%(i+273,32+i*1.8),"K":"%f C\n%f F"%(i-273,i*1.8-459.4),"F":"%f C\n%f K"%(i/1.8-17.78,i/1.8+255.2)};print d[s[-1]]`

This is my first try on CodeGolf.

Welcome to PPCG. This is a nice attempt for the very first golf! I have added some sugar to your post by correcting formatting and stuff.

Pyth, 126 bytes
AYZczdJvY=Y*JK1.8
?%"%f F\n%f K",+32Y+J273.15qZ"C"?%"%f F\n%f C",-Y459.67-J273.15qZ"K"?%"%f C\n%f K",c-J32K*+J459.67c5 9qZ"F"

This feels really long to me...oh well.

There's a Python solution shorter than this :P

@orlp I know, I know...

R, 150 144 141 bytes
a=scan(,"");U=c("C","K","F");i=which(U==a[2]);Z=273.15;x=scan(t=a[1]);cat(paste(c(C<-c(x,x-Z,5*(x-32)/9)[i],C+Z,32+C*9/5)[-i],U[-i]),sep="\n")

Indented, with new lines:
a=scan(,"")
U=c("C","K","F")
i=which(U==a[2])
Z=273.15
x=as.double(a[1])
cat(paste(c(C<-c(x,x-Z,5*(x-32)/9)[i],C+Z,32+C*9/5)[-i],
            U[-i]),
    sep="\n")

Usage:
> a=scan(,"");U=c("C","K","F");i=which(U==a[2]);Z=273.15;x=scan(t=a[1]);cat(paste(c(C<-c(x,x-Z,5*(x-32)/9)[i],C+Z,32+C*9/5)[-i],U[-i]),sep="\n")
1: 23 C
3:
Read 2 items
Read 1 item
296.15 K
73.4 F
> a=scan(,"");U=c("C","K","F");i=which(U==a[2]);Z=273.15;x=scan(t=a[1]);cat(paste(c(C<-c(x,x-Z,5*(x-32)/9)[i],C+Z,32+C*9/5)[-i],U[-i]),sep="\n")
1: 56.9999999 K
3:
Read 2 items
Read 1 item
-216.1500001 C
-357.07000018 F
> a=scan(,"");U=c("C","K","F");i=which(U==a[2]);Z=273.15;x=scan(t=a[1]);cat(paste(c(C<-c(x,x-Z,5*(x-32)/9)[i],C+Z,32+C*9/5)[-i],U[-i]),sep="\n")
1: 86.987 F
3:
Read 2 items
Read 1 item
30.5483333333333 C
303.698333333333 K

Thanks to @AlexA. & @MickyT. !

Nice work. You can save a byte using as.double() rather than as.numeric().

I think the switch statement can be done with c(x,x-273.15,5*(x-32)/9)[i] for 4 characters

Thanks! Actually, prior to version 3.0, I could have shorten it more with as.real() instead of as.numeric(), but the function is defunct now.

Another saving would be replacing as.double(a[1]) with scan(t=a[1]).

Javascript, 206 193 187 175 162 159 156
e=273.15,a=prompt(f=1.8).split(" "),b=+a[0],X=b-32,c=a[1];alert(c=="F"&&(X/f+"C\n"+(X/f+e+"K"))||(c=="C"?b*f+32+"F\n"+(b+e+"K"):b*f-459.67+"F\n"+(b-e+"C")))

Thanks goes to Optimizer and Ismael Miguel for helping me golf it a little further.

You can save a few bytes by converting the if else to ?:

You could save a few more by combining your if ... return; return ?: to a return ?: ?:

You can save 1 byte replacing a=prompt().split(" "),e=273.15,f=1.8;alert([...] with a=prompt(e=273.15,f=1.8).split(" "),alert([...]. Also, you can remove the spaces after the unit. Also, removing the return and moving the alert inside the function reduced a lot! And instead of setting a, just use the apply() method with the split. But here you go: (function(b,c){alert(c=="F"&&((b-32)/f+"C\n"+((b-32)/f+e+"K"))||(c=="C"?b*f+32+"F\n"+(b+e+"K"):b*f-459.67+"F\n"+(b-e+"C")))}).apply(e=273.15,prompt(f=1.8).split(" "))! 166 bytes (-21 bytes). Ping me in the chat if you have doubts.

@IsmaelMiguel: a[0] needs to be cast to a number, it doesn't work right otherwise. I'll look into the other stuff you suggested though.

You can add b+=0; inside the function, before the alert.

That wouldn't work, but I found a solution that does.

This one works for me: (function(b,c){b/=1;alert(c=="F"&&((b-32)/f+"C\n"+((b-32)/f+e+"K"))||(c=="C"?b*f+32+"F\n"+(b+e)+"K":b*f-459.67+"F\n"+(b-e)+"C"))}).apply(e=273.15,prompt(f=1.8).split(" ")) (171 bytes).

And this one too: (function(b,c){alert(c=="F"&&((b-32)/f+"C\n"+((b-32)/f+e+"K"))||(c=="C"?b*f+32+"F\n"+(+b+e)+"K":b*f-459.67+"F\n"+(b-e)+"C"))}).apply(e=273.15,prompt(f=1.8).split(" ")) (167 bytes).

I just got it down to 162 anyway.

You can chop it down to 159 if you remove the spaces after the units.

You're right, I missed some of the spaces. Thank you for pointing that out.

154 bytes: e=273.15,a=prompt(f=1.8).split(" "),b=+a[0],X=b-32/f,c=a[1];alert(c=="F"&&(X+"C\n"+(X+e+"K"))||(c=="C"?b*f+32+"F\n"+(b+e+"K"):b*f-459.67+"F\n"+(b-e+"C")))

Sorry, edited my comment on the wrong time. But I've reduced it a little bit

Your last edit doesn't work right.

You are right. But Now I can't edit it.

Mathematica, 66
Hopefully correct this time.
Print[1##]&@@@Reduce[F==1.8K-459.67&&C==K-273.15&&#==#2,,#2];&@@#&

Example
%[37 C]   (* % represents the function above *)

310.15 K
98.6 F

The OP said in a comment that "You have to only output the other two formats."

@Thomas That and other problems (hopefully) fixed.  Not very good but I am losing interest.

Excel, 239 bytes
=IF(RIGHT(A1,1)="C",LEFT(A1,LEN(A1)-2)+273.15&"K
"&9*LEFT(A1,LEN(A1)-2)/5+32&"F",IF(RIGHT(A1,1)="K",LEFT(A1,LEN(A1)-2)-273.15&"C
"&(LEFT(A1,LEN(A1)-2)*9/5-459.67&"F",(LEFT(A1,LEN(A1)-2)+459.67)*5/9&"K
"&(LEFT(A1,LEN(A1)-2)-32)*5/9&"C"))

112 bytes of which are used to seperate Value and Unit.  Anybody know a better solution?


text:
Multiplication by Self-Modification
...at least for some definition of "self-modification".
The Task
In this challenge, your task is to write three strings A, B and C that satisfy the following properties.

The string B has length at least 1.
For every n ≥ 0, the string ABnC is a valid program (meaning full runnable program or function definition) in your programming language of choice. The superscript denotes repetition, so this means the strings AC, ABC, ABBC, ABBBC etc. Each program takes one string as input, and returns one string as output.
For any m, n ≥ 0, if the program ABmC is run with input ABnC, it returns ABm*n+1C. For inputs not of this form, the program may do anything, including crash.

Some examples in the format program(input) -> output:
AC(AC) -> ABC
ABC(AC) -> ABC
ABBBBBC(AC) -> ABC
AC(ABC) -> ABC
AC(ABBBBC) -> ABC
ABC(ABC) -> ABBC
ABBC(ABC) -> ABBBC
ABBBBC(ABBBC) -> ABBBBBBBBBBBBBC
ABBBC(ABBBBBBC) -> ABBBBBBBBBBBBBBBBBBBC

Rules and Scoring
Your score is the total length of A and C, lower score being better.
Note that while B is not counted toward the score, it must be produced by A and C as in the first example.
Standard loopholes are disallowed.
The programs are not allowed to directly or indirectly access their own source code (except when they are given it as input).
You are required to identify the strings A, B and C in your answer in some way, and encouraged to explain your solution.

CJam, 9 8 bytes
A: 1
B: 0
C:  r,(#0q

Try it online in the CJam interpreter.
How it works
(ABcode) e# Push the integer 10 ** len(Bcode).
<SP>     e# Noop. Separates (AB) and C for input reading.
r        e# Read the first whitespace-separated token from STDIN (ABinput).
,(       e# Push the string length minus 1: len(Binput)
#        e# Power operator: 10 ** len(Bcode) len(Binput) # ->
         e#   (10 ** len(Bcode)) ** len(Binput) = 10 ** (len(Bcode) * len(Binput))
0        e# Push an additional 0 to complete len(Bcode) * len(Binput) + 1 zeroes.
q        e# Read the remaining input (C).

CJam, 15 13 11 bytes
A: rl"
B: <SP>
C: <LF>",(*SNq

Try it online in the CJam interpreter.
How it works
e# A

r     e# Read a whitespace-separated token from STDIN.
      e# This reads the input up to the first space, but does not consume it.
l     e# Read the rest of the first line from STDIN.
      e# This reads up to the first linefeed and consumes it.

"     e# Initiate a string.

e# B

<SP>  e# Fill the string with as many spaces as there are copies of B.

e# C

<LF>" e# Terminate the string with a linefeed.
      e# This serves as a delimiter for the `l' command.
,(    e# Compute the length of the string minus 1 (to account for the LF).
*     e# Repeat the string read by `l' that many times.
SN    e# Push a space and a linefeed.
q     e# Read the remaining input (i.e., the second line) from STDIN.

At the end, the stack contains the token read by r, the space produced by *, the space and linefeed pushed by SN and the line read by q. CJam prints all these automatically.

Hah, nice use of quotes there :D

Pyth, 10
A: w*\0hl*w[<newline>
B: 0
C: <empty>

We split the source in two lines. The first line is A, the second line are the Bs. Since A is on the first line, the first w just prints A - easy, done.
In Pyth leading zeroes are seperate tokens, so [00) actually is [0, 0]. Note that the first line ends in l[, and the second line consists of 0000.... So l[ actually counts the number of Bs in this program. The second w reads in the second line of the input - this is the number of Bs of the input. From here it's a simple multiply, increment and outputting that many zeroes.

Retina, 25 19 bytes
A: ]\]<LF>
B: ]]
C: <LF>m`^]*$<LF>]$0]

<LF> stands for newline

Example ABC code:
]\]
]]
m`^]*$
]$0]

The code has two substitute steps:

change the input AB^mC into AB^(m*n)C by changing every B to B^n:

]\] matches every B in the input and nothing else thanks to escaping in the pattern lines
]]...]] is B^n

change B^(m*n) to B^(m*n+1) by

m`^]*$ taking the line with only ]'s
]$0] adding an extra pair of ]] to it in a way that this line doesn't match the first regex

I've added 3 bytes to the score for the -s multi-line flag which is needed so the whole Retina code could be in one file.
2 bytes saved thanks to @MartinBüttner.

Python 3, 51 bytes
A: lambda s:s[:28]+"x"*(1+len("
B: x
C: ")*(len(s)-51))+s[-23:]

Example usage:
>>> f=lambda s:s[:28]+"x"*(1+len("xx")*(len(s)-51))+s[-23:]
>>> f('lambda s:s[:28]+"x"*(1+len("xxx")*(len(s)-51))+s[-23:]')
'lambda s:s[:28]+"x"*(1+len("xxxxxxx")*(len(s)-51))+s[-23:]'

The function computes n*m+1 with (1+len("xxx")*(len(s)-51)) where there are m x's in the string (xxx part is the B^m). Multiplying the string "x" with this number gives B^(n*m+1) and the function takes A and C out of the input and concatenates all of these to get AB^(n*m+1)C.
The same approach in J:
J, 35 bytes
A: (19{.]),('x'#~1+(#'
B: x
C: ')*35-~#),_16{.]

CJam, 22
A:<empty>
B:{])`\,q,K/(*))*"_~"}
C:{])`\,q,K/(*))*"_~"}_~

Example run:
ABBC(ABC) -> ABBBC

which translates to
{])`\,q,K/(*))*"_~"}{])`\,q,K/(*))*"_~"}{])`\,q,K/(*))*"_~"}_~

with input as
{])`\,q,K/(*))*"_~"}{])`\,q,K/(*))*"_~"}_~

which gives the following output:
{])`\,q,K/(*))*"_~"}{])`\,q,K/(*))*"_~"}{])`\,q,K/(*))*"_~"}{])`\,q,K/(*))*"_~"}_~

How it works:
Lets take a look at what programs AC and ABC look like:
AC :{])`\,q,K/(*))*"_~"}_~
ABC:{])`\,q,K/(*))*"_~"}{])`\,q,K/(*))*"_~"}_~

We notice that C = B_~
Lets look at what B is doing:
{])`\,q,K/(*))*"_~"}

{                  }    e# This is a code block. Alone, this does nothing except
                        e# pushing this block to stack as is
 ]                      e# Wrap everything on stack in an array
  )`                    e# Take out the last part and convert it to its string representation
    \,                  e# Take length of remaining array
      q,K/              e# Read the input, take its length and int divide by K (i.e. 20)
          (*            e# Decrement and multiply by the array length on stack
            ))          e# Add two to the product
              *         e# Repeat the string representation on stack that many times
               "_~"     e# Put this string on stack

Now lets see what running AC without any input will do:
{])`\,q,K/(*))*"_~"}_~                      e# Copy the block and run it
{])`\,q,K/(*))*"_~"}{])`\,q,K/(*))*"_~"}~   e# Block is copied, run it
{      ...         } ])                     e# Wrapped array has the block in it.
                       `\,                  e# Stringify it and take length of remaining = 0
                          q,K/              e# No input so 0
                              (*))          e# 0 * -1 = 0. 0 + 2 = 2
                                  *         e# Repeat the stringified block 2 times:
                                            e# "{])`\,q,K/(*))*"_~"}{])`\,q,K/(*))*"_~"}"
                                   "_~"     e# Put this string. Program ends, so print stack:
                                            e# {])`\,q,K/(*))*"_~"}{])`\,q,K/(*))*"_~"}_~

Wow, the output is ABC.
We basically count how many B exist in the code. Then how many are in the input (using length). Multiply them, increment twice (since C also has B) and append _~ to get C
Try it online here

Haskell, 50 bytes
f is a function taking and returning a String.
The string B is just a single space, while C starts with one.
A:_:b="
B:
C: ";f s|a:c<-words s=unwords$a:(drop 50s>>b):c

Try it online!

_:b="    " assigns all but the first of the spaces in the string literal to b, making that equal to the program's m B copies.
s is the input string. a:c<-words s splits it into space-separated words, so that a becomes A and c becomes a list of the words comprising C. The B copies are ignored since words squeezes multiple spaces (which the rest of the program avoids).
drop 50s is a string with length equal to the number n of B copies in the input. drop 50s>>b concatenates that many copies of b, giving mn spaces.
unwords$a:(drop 50s>>b):c joins all the strings back together with spaces. Since there is an extra "word" (drop 50s>>b) inserted in the list, there is also an extra joining space, automatically adding the +1 to the multiplication.

Matlab, 85
First time for me to do such an abstract challenge, so for me it was more of a coding challenge than a code-golf challenge!
The three strings are, without the quotation marks:
A:    "X=strsplit(input('','s'));m=0 "
B:    "+1 "
C:    ";[X{1},32,repmat(['+1',32],1,m*(length(X)-2)+1),X{end}]"

How it works: I split the input argument on whitespace, so n can be determined from the number of string parts. B works as a sort of counter to get m. For reconstructing the answer I use A and C from the split, repeat B m*n+1 times and I insert the spaces by using their ASCII value, so that no unwanted splits occur in C.
EDIT: whoops, accidentally counted A+B

C (gcc), 81 bytes
The requirement to identify the strings seems at odds with our being allowed arbitrary behaviour for illegal input, unless we have rather lax standards of what identifying entails. Naturally, I took the interpretation that sheds the most bytes.

Try it online!
A: m;f(char*s){m=strrchr(s+66,32)-s-65;printf("%.66s%*s",s,m*strlen("
B: <SPACE>
C: ")+16,s+m+66);}

By identification I just meant that it should be clear from your answer which code snippets are A, B and C. It's not a requirement for the program.

TI-Basic (83 series), 65 bytes
Segment A (33 bytes):
Input Str1:sub(Str1,1,27:For(I,0,(length(Str1)-55)(length("

Segment B:
X

Segment C (32 bytes):
Y")-1:Ans+"X":End:Ans+sub(Str1,length(Str1)-27,28

I am really excited about finding this quine-like challenge! Most quines don't work in TI-Basic without at least a little cheating, because there is no way to escape the " symbol. (In both senses of the word "escape".) But here, we get an input string via the Input command, and typing in a " there is perfectly fine.
There is still some amount of TI-Basic silliness to work around here: an empty string is invalid, so the naive solution of inserting the string "XXX...XX" in a loop won't work when n=0. Instead, we manually compute the value of mn+1, and insert the string "X" that many times.
The magic constants 27 and 28 in the program are slightly off from the byte counts 33 and 32, because Str1, sub(, and length( are two-byte tokens that only contribute 1 to the length of a string.
If we use newlines instead of :, it looks like when can save a few bytes by leaving off ending quotes, but this doesn't actually work. First of all, you need a hex editor before you can add the newline character into a string: you can't just type it in, because if you press ENTER during an Input command, it submits the input. When I tried the hex editor approach, I ended up getting a weird buffer overflow error that modified the contents of my program, so don't try this at home with your expensive calculator.

Java 11, 135 65+26=91 bytes
A
s->{var p=s.split("\\(\"|\"\\.");return p[0]+"(\"B"+p[1].repeat("

B
B

C
".length())+'"'+'.'+p[2];}

Try it online here (TIO does not have Java 11 yet, so this relies on a helper method instead of String::repeat()).
Ungolfed:
s -> { // lambda taking and returning a String
    var p = s.split("\\(\"|\"\\."); // split input into parts A, B^n, C (where n may be 0) at the "(\"" and "\"."
    return p[0] + "(\"B" + // put it back together: A plus the part the split shaved off, plus an extra B ...
    p[1].repeat("BBB".length()) + // ... plus B^(n*m)
    '"' + '.' + p[2]; // plus C, with the part the split shaved off reattached
}

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