text:
Polynomial Interpolation
Write a program that performs Polynomial Interpolation  using true arbitrary precision rational numbers. The input looks like this:

f(1) = 2/3
f(2) = 4/5
f(3) = 6/7
...

You may assume that there's exactly one whitespace before and after the = sign, all the numbers are either fractions or integers. You may also assume, that all fraction in the input are already irreducible.
No error checking is needed, you may assume, that the input is valid and no x is doubled in the f(x).
The output should be in a LaTeX compatible form, the emitted LaTeX code should yield the same graphical representation as the output given here.

f(x) = 123x^2 + \frac{45}{2}x + \frac{7}{4}

The fraction must be reduced as much as possible, eg. something like \frac{2}{4}  is not allowed. If the number is integer, don't use a fraction.
Special rules:
Your program should...

work for polynomials up to degree 12
complete in less then 1 minute for reasonable input
not use any functions that do the whole calculation for you
output the polynomial of smallest possible degree

Testcases:
The given testcases are just for clarification. Your program should yield correct result for all correct inputs.
Input

f(1) = 2/3
f(2) = 4/5
f(3) = 6/7

Output

f(x) = - \frac{4}{105}x^2
       + \frac{26}{105}x
       + \frac{16}{35}

Input

f(-12) = 13/2
f(5/3) = 3/5
f(13) = -6
f(1/5) = -3/4

Output

f(x) = - \frac{2186133}{239455744}x^3
       + \frac{2741731}{149659840}x^2
       + \frac{26720517}{29201920}x
       - \frac{279464297}{299319680}

Input

f(4/3) = 617/81
f(2) = 20/3
f(-8/3) = 6749/81
f(-5) = 7367/12
f(0) = 23/3

Output

f(x) = \frac{1}{2}x^4
     - 2x^3
     + \frac{7}{4}x^2
     + \frac{23}{3}

Input

f(0) = 5
f(1) = 7
f(2) = 9
f(3) = 11
f(4) = 13

Output

f(x) = 2x
     + 5

Input

f(1/2) = -1/2
f(-25) = -1/2
f(-54/12) = -1/2

Output

f(x) = -\frac{1}{2}

Why are you talking about real numbers if all you're ever using are rational numbers?

Sorry. My english is poor. Yes, only use rational numbers. The results have to be exact.

In the first testcase, are dots (...) really part of the input?

@Eelvex: Nope. Fixed.

The output for the third testcase is wrong. The correct answer is -\frac{37745}{14592}x^4 - \frac{853249}{43776}x^3 + \frac{57809}{7296}x^2 + \frac{225205}{2736}x + \frac{23}{3}. I suspect the input was intended to be something different :)

The second testcase is also wrong. The correct answer is f(x) = -\frac{10270401}{1197278720}x^3 + \frac{17890327}{748299200}x^2 + \frac{131825777}{146009600}x - \frac{278804033}{299319680}.

@Timwi: They are not wrong, they are equivalent.

@Eelvex: They are wrong. They are different polynomials, and they don’t interpolate the input points. In what way did you think they could be equivalent?

@Timwi @Elvex:Hm... That's strange. I'm going to write a reference implementation tomorrow. I obtained these values using Wolfram Alpha and ouble checked them using bc. I don't know, where the mistake is.

@Timwi: They correspond to different polynomials that pass through the same given points. eg. if f(x) = 1/2x^4 - 2x^3 + 7/4x^2 + 23/3 then f(0)=23/3, f(-5)=7367/12, etc.

@Eelvex: But they don’t pass through the same points. (That is impossible because there is no degree of freedom.) For the third testcase, f(4/3) = 617/81 instead of the 617/8 given. For the second testcase, f(13) = -6 and not the -12/3 given. (I guess now we know that the test input is probably wrong, rather than the output.)

@Timwi: Ah, you're right.

@Timwi@Eelve: Fied up the testcases

J + sh
J script:
i=:0".(1!:1)3
i=:((-:#i),2)$i
c=:|.(%.(x:((i.#i)^~])"0({."1 i)))(+/ .*)(|:{:"1 i)
(":(-.0=c)#(c,.i.-#c))(1!:2)2

sh script:
echo -n 'f(x) = '
tr -d 'f()=' | tr /\\n- r' '_  | ./polyint.ijs | sed -e 's/^/+/;s/_/-/;s/\([0-9]*\)r\([0-9]*\)/\\frac{\1}{\2}/;s/ \([0-9]*$\)/x^\1/;s/\^1//;s/x^0//;s/+\(.*-.*\)/\1/'

Run the sh script:
./pol-int.sh
f(1/2) = -1/2
f(-25) = -1/2
f(-54/12) = -1/2

f(x) = -\frac{1}{2}

.
./pol-int.sh
f(4/3) = 617/8
f(2) = 20/3
f(-8/3) = 6749/81
f(-5) = 7367/12
f(0) = 23/3

f(x) = -\frac{37745}{14592}x^4
       -\frac{853249}{43776}x^3
     +  \frac{57809}{7296}x^2
     + \frac{225205}{2736}x
     +  \frac{23}{3}

You don't have to create the exact same sourcecode formatting. In the LaTeX output. It should just yield the same graphical representation after running through LaTeX. Feel free to save some chars.

I can’t read J, but from the short length I take it that means J has a built-in function for matrix echelon form?

@Timwi: No, but I use the built-in "inverse matrix". J is very terse though: even if I were to implement "invert matrix" it would be a few characters long.

Perl (569 characters)
use Math'BigInt;sub r{($u,$v)=@_;$v?r($v,$u%$v):$u}sub c{new Math'BigInt$_[0]}$a=@c=<>;for(@c){m!(-?\d+)/?(\d*). = (-?\d+)/?(\d*)!;$j{$_,$i}=$1**c$_,$k{$_,$i|=0}=($2||1)**c$_ for 0..$a;$j{$a,$i}=c$3;$k{$a,$i++}=c$4||1}for$p(0..$a-1){for$y(0..$p-1,$p+1..$a-1){$n=$j{$p,$y}*$k{$p,$p};$o=$k{$p,$y}*$j{$p,$p};$j{$_,$y}=$j{$_,$y}*$k{$_,$p}*$o-$k{$_,$y}*$j{$_,$p}*$n,$k{$_,$y}*=$k{$_,$p}*$o for 0..$a}}print"f(x)=";for(1..$a){$s=r$t=$j{$a,$p=$a-$_}*$k{$p,$p},$w=$k{$a,$p}*$j{$p,$p};$u=abs$t,print$t>0?"$z":'-',($z='+',$w/=$s)-1?"\\frac{$u}{$w}":$u,$p>1?"x^$p":x x$p if$t/=$s}

Detailed explanation:
use Math'BigInt;

# Subroutine to calculate gcd of two numbers
sub r{($u,$v)=@_;$v?r($v,$u%$v):$u}

# Subroutine to create BigInts
sub c{new Math'BigInt$_[0]}

# Read input
# Throughout, $a is the number of equations.
$a=@c=<>;

# Initialises the $a+1 × $a matrix with all the values.
# $j{$x,$y} contains the numerator, $k{$x,$y} the denominator.
for(@c)
{
    m!(-?\d+)/?(\d*). = (-?\d+)/?(\d*)!;

    # Puzzle for the reader: why is $i|=0 in the second one,
    # not the first one? Answer at the bottom!
    $j{$_,$i}=$1**c$_,$k{$_,$i|=0}=($2||1)**c$_ for 0..$a;
    $j{$a,$i}=c$3;
    $k{$a,$i++}=c$4||1
}

# Generates the matrix echelon form.
# Basically, it works like this:
for$p(0..$a-1)
{
    # For each element along the diagonal {$p,$p}, set all the values above and
    # below it to 0 by adding a multiple of row $p to each of the other rows.
    for$y(0..$p-1,$p+1..$a-1)
    {
        # So we need to multiply the row $p by the value of {$p,$y}/{$p,$p}
        # (stored in $n/$o) and then subtract that from row $y.
        $n=$j{$p,$y}*$k{$p,$p};
        $o=$k{$p,$y}*$j{$p,$p};
            $j{$_,$y}=$j{$_,$y}*$k{$_,$p}*$o-$k{$_,$y}*$j{$_,$p}*$n,
            $k{$_,$y}*=$k{$_,$p}*$o
        for 0..$a
    }
}

# Outputs the result
print"f(x)=";
for(1..$a)
{
    # Note this sets $p = $a-$_. $p is the power of x.
    # We need to divide {$a,$p} by {$p,$p}. Store the result in $t/$w.
    # We also need to put the fraction in lowest terms, so calculate the gcd.
    $s=r$t=$j{$a,$p=$a-$_}*$k{$p,$p},$w=$k{$a,$p}*$j{$p,$p};

    # Output this term only if the numerator ($t) is non-zero.
    # Output a plus sign only if this isn’t the first term.
    # Output a fraction only if the denomator ($w) isn’t 1.
        $u=abs$t,print$t>0?"$z":'-',
        ($z='+',$w/=$s)-1?"\\frac{$u}{$w}":$u,$p>1?"x^$p":x x$p
    if$t/=$s
}

# Answer to the puzzle buried in the code above:
# It’s because the second part is passed as a second argument to c,
# hence it is evaluated before the first part.

Comments

I am sure there is a module for matrix manipulation that provides a function for echelon form. I specifically didn’t use that (didn’t even search for one) because I assume it is the point of this contest to do it yourself. It is more interesting that way, too. Of course the same could be said about BigInt, but then I suspect nobody will attempt this challenge...

Edits

(630 → 585) Realised I can do the echelon form in one loop instead of two. Add explanation as comments in code.
(585 → 583) Just discovered the package syntax that lets me use ' instead of ::.
(583 → 573) Some more microgolfing
(573 → 569) Shorter regular expression to parse input

I keep getting compilation errors: http://ideone.com/LoB2T

@FUZxxl: Thanks for pointing that out. There was just a missing space. Fixed now.

Lagrange Method, Python, 199 236 202 bytes
A little late, but...
def lagrange(dp):
    l = lambda i: lambda x: (prod([(x - dp[j][0]) / (dp[i][0] - dp[j][0]) for j in range(len(dp)) if i != j]))
    return lambda x: sum([l(i)(x) * dp[i][1] for i in range(len(dp))])

Edit: To adhere to general rules, we have to remove references to non-builtin functions (at least without importing them). I have rewritten it to only use standard library modules and also included the imports (thanks to @TheFifthMarshal & @Tech-Freak), while deleting extraneous whitespace, bumping it up to 208 bytes. To elaborate, the input d takes the form of a 2D iterable (an nx2 matrix), where each row is a measurement, the first column is \$t\$ and the second column is \$x\$. The output is an anonymous function which can take any floating point or integer number and give the approximate result.
from functools import*
mul=lambda a,b:a*b
def l(d):
 l=lambda i,x:reduce(mul,[(x-d[j][0])/(d[i][0]-d[j][0])for j in range(len(d))if i!=j],1)
 return lambda x:sum([l(i,x)*d[i][1]for i in range(len(d))])

Usage Example:
>>> t = np.arange(0, 5, 0.5)
>>> t2 = np.arange(0, 5, 0.01)
>>> x = t**3
>>> dp = np.vstack((t, x)).T
>>> poly = l(dp)
>>> plt.plot(t2, np.vectorize(poly)(t2), label="output")
>>> plt.scatter(t, x, label="input")
>>> plt.legend()

You probably don't need all that whitespace around the operators, do you?

This answer appears to be invalid for reasons I explained at length in the comments on a golfed version of it

Updating now. @TheFifthMarshal

208 bytes

Awesome. I've updated the answer and added thanks to you & tech-freak.

@fpf3 glad to be of service. You've still got unnecessary spaces. Also A) using enumerate is cheaper than range(len()) + index and B) instead of importing mul, just define it yourself as lambda (should be cheaper).

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


text:
Mathematical Combination
Write a program that takes an input such as:
n,k

which then computes:
$$\binom n k = \frac {n!} {k!(n-k)!}$$
and then prints the result.

A numerical example:
Input:
5,2

Internal computation:
$$\frac {5!} {3!\times2!}$$
Printed Output:
10

I'd like to see an answer that beats my python solution of 65 characters, but all languages are obviously welcome.
Here's my solution:
n,k=input();f=lambda x:+(x<2)or x*f(x-1);print f(n)/(f(k)*f(n-k))

Edit:
I admit that this question is from the codegolf website mathematical combination puzzle.  I know that my answer may look like not much progress can be made on it, but the leaders of this puzzle have solved it in nearly half as many characters.

Function or full program? Your description says function that returns the correct result, but your example is a full program that prints it.

@Ventero You're right I meant program.  Sorry about that.

Generally, basic math concepts aren't great golf questions because J, APL, Maple, Mathematica and many others will have them built in.  Also, be a bit more specific about input and output format, and provide example results - I can't tell if you mean 5 choose 2 or 2 choose 5 here.

@Jesse I got this challenge from another website that only allows major scripting languages, I'll remember this guideline in the future.  I edited my question to try and make the challenge requirements more clear, let me know if its clear enough or not.

I'm new, so we're in much the same boat. However, don't summarize the results; they will just get outdated. Just vote and (if appropriate) accept answers. (Also, you'll make people unhappy if you ignore J and GolfScript answers without a reason.)

@Jesse those aren't the answers from this page, they're the records from the other website and (as far as I know) the lowest possible counts.

@Jesse: Whether it's 5C2 or 2C5 is pretty easy to figure out, though, as you wouldn't normally want the latter ;-)

What about additional output to stderr, will that be ignored?

Even this will work:n,k=input();f=lambda x:x<2or x*f(x-1);print f(n)/(f(k)*f(n-k))

C 96
With I/O (which takes about 34 chars). Added a couple of newlines to make it readable.
main(a,b,c,d){scanf("%d,%d",&a,&b);
d=a-b;for(c=1;a>b;){c*=a--;}for(;d;)
{c/=d--;}printf("%d",c);}

Now if you'll excuse me, I have an ASCII n choose k rocket to catch.
    d;main(a
   ,         b
  ,           c
 )  int        a
 ;   {scanf    (
 (   "%d %d"   )
 ,   &a,  &b   )
 ;   d    =a   -
 b   +     b   -
 b   *     1   ;
 a             -
 a  ;for    (  c
 =  1;a>   b   ;
 )  {c=   c    *
 (  (a-- )     )
 ;  }for(      b
 =  b + 1      ;
 d  ;    )     {
 c  =     c    /
 (  d--    )   ;
  }           {
  }           {
   }         (
  printf("%d",c)
 )      ;       }
/*     *  *   * *\
 * * X   * 8 * * |
|     *      *    \
*/    //       *  */

APL, 3 bytes
⎕!⎕

Or for those whose browser doesn't render the above, in an ASCII rendering:
{Quad}!{Quad}

To be completely conformant to the n,k input, you'd have to do !/⌽⎕.

R (11 Chars)
choose(n,r)

You can save 5 bytes (and make it compliant with modern I/O rules) by removing (n,r)

GolfScript, 17 chars
This solution handles cases like k=0 or k=1 correctly.
~>.,,]{1\{)*}/}//

Factorial-like portion is based off a previous answer.

Ruby 1.9, 52  46 (42) characters
eval"A,B="+gets;i=0;p eval"(A-B+i+=1)/i*"*B+?1

If stderr is ignored:
eval"A,B=I="+gets;p eval"I/(A-I-=1)*"*B+?1

Ruby 1.8, 43 characters, no additional output to stderr:
eval"a,b=i="+gets;p eval"i/(a-i-=1)*"*b+"1"

Edits:

(52 -> 48) Found a shorter way to parse the input
(48 -> 46) Less looping, more eval.

GolfScript 21
~~)>.,,]{{)}%{*}*}%~/

Not particularly short, GolfScript lacks a real factorial function, however this has got to be the most wicked data manipulation that I have ever done, this calls for a stack trace:
"5,2" Data on the stack from input.
~ Eval command, note that , is an operator that turns a number into an array.
[0 1 2 3 4] 2
~ Binary not.
[0 1 2 3 4] -3
) Increment.
[0 1 2 3 4] -2
> Take end of array, -2 as parameter to get the last 2 elements.
[3 4]
. Duplicate element.
[3 4] [3 4]
, Array length.
[3 4] 2
, Turn number to array.
[3 4] [0 1]
] Create array.
[[3 4] [0 1]]
{{)}%{*}*} Block of code.
[[3 4] [0 1]] {{)}%{*}*}
% Execute block once for each element of the array. The following part only demonstrate the first loop.
[3 4]
{)}% Increment each array element.
[4 5]
{*} Block containing a multiply command.
[4 5] {*}
* "Fold" the array using the block command, that is in this case make the product of all elements.
20
After the big loop has finished it returns an array with the results.
[20 2]
~ Deconstruct the array.
20 2
/ Division.
10

Python (56)
f=lambda n,k:k<1and 1or f(n-1,k-1)*n/k;print f(*input())

Ungolfed code and some explanation of a shortcut for calculating the binomial coefficient.  (Note: There is some insight that I just haven't figured out in order to get down to the 39 char version; I don't think this approach will get you there.)
# Since choose(n,k) =
#
#     n!/((n-k)!k!)
#
#          [n(n-1)...(n-k+1)][(n-k)...(1)]
#        = -------------------------------
#            [(n-k)...(1)][k(k-1)...(1)]
#
# We can cancel the terms:
#
#     [(n-k)...(1)]
#
# as they appear both on top and bottom, leaving:
#
#    n (n-1)     (n-k+1)
#    - ----- ... -------
#    k (k-1)       (1)
#
# which we might write as:
#
#      choose(n,k) = 1,                      if k = 0
#                  = (n/k)*choose(n-1, k-1), otherwise
#
def choose(n,k):
    if k < 1:
        return 1
    else:
        return choose(n-1, k-1) * n/k

# input() evaluates the string it reads from stdin, so "5,2" becomes
# (5,2) with no further action required on our part.
#
# In the golfed version, we make use of the `*` unpacking operator,
# to unpack the tuple returned by input() directly into the arguments
# of f(), without the need for intermediate variables n, k at all.
#
n, k = input()

# This line is left as an exercise to the reader.
print choose(n, k)

Could you provide an ungolfed example of your script?

Can we use * for parsing inputs of the form 4545 78?

Unfortunately, no, but it's not * that's the issue. 4545 78 isn't a valid Python expression, so input() will raise a SyntaxError.  This trick depends entirely on the problem asking for x,y.  If you had a function that read x y and returned a tuple, then you could use * with that just fine.

RPL (4)
(using built-in function)
COMB

Windows PowerShell, 57
$a,$b=iex $input
$p=1
for($a-=$b;$a-ge1){$p*=1+$b/$a--}$p

J, 33 36
(":!~/".;._1}:toJ',',1!:1(3))1!:2(4)

35 characters are input, parsing and output. The other character, !, is n choose k.
I don't have Windows around for testing this at the moment, but I believe it should work there.

Q, 32 chars
{f:{1*/1.+(!)x};f[x]%f[y]*f x-y}

Python 2, 39 bytes
n,k=input()
B=2<<n
print(B+1)**n/B**k%B

Try it online!
A full program, as the challenge asks for. The method is explained in this tip.

Perl 6 (55)
my ($a,$b)=lines;$_=1;for 1..$a-$b {$_+=$_*$b/$^a};.say

RPL (22)
(not using built-in COMB function)
→ n k 'n!/(k!*(n-k)!)'

Q (50 45)
 f:{(prd 1.+til x)%((prd 1.+til y)*prd 1.+til x-y)}

You can shave a few characters off the above by removing redundant brackets and using 1*/ instead of prd.
f:{(1*/1.+til x)%(1*/1.+til y)*1*/1.+til x-y}

Mathematica 12
Straightforward, built-in function.
n~Binomial~k

Perl 6, 25 16 bytes
-9 bytes thanks to nwellnhof
+*o&combinations

Try it online!
Anonymous function that takes two numbers and returns an int. This uses the built-in combinations and converts the returned list to an int.

16 bytes

@nwellnhof Ah, I didn't realise combinations could take an number instead of a list

PHP (71 79)
<?$a=fgetcsv(STDIN);$x=1;while($a[1]-$i)$x=$x*($a[0]-++$i+1)/$i;echo$x;

<?php $a=fgetcsv(STDIN);$x=1;while(++$i<=$a[1])$x=$x*($a[0]-$i+1)/$i;echo $x?>

Python (54)
f=lambda n,k:k<1or f(n-1,k-1)*n/k;print 1*f(*input())

Essentially the same as the Python one above, but I shave off four bytes by dropping the
and 1

from the function definition. However, this results in the function returning True instead of 1 if k=0, but this can be fixed by multiplying with 1 before printing, since 1*True=1, thus adding two bytes.

J, 11 characters
!~/".1!:1[1

Takes input from the keyboard.
    !~/".1!:1[1
5,2
10

Python 3.8 (pre-release), 21 bytes
import math
math.comb

Try it online!

Jelly, 1 byte
c

Try it online!
2 bytes to take input as n,k

Rust, 53 bytes
fn f(n:i32,k:i32)->i32{if k<1{1}else{f(n-1,k-1)*n/k}}

This is essentially the same as the Python code in some of the previous answers, and computes the binomial coefficient through recursion.
Try it online!

Go, 58 bytes
func b(n,k int)int{if k<1{return 1}
return b(n-1,k-1)*n/k}

Attempt This Online!
Alternative using math.Gamma(), 82 bytes
import."math"
func b(n,k float64)float64{g:=Gamma
return g(n+1)/(g(k+1)*g(n-k+1))}

Attempt This Online!

Haskell (80)
f(_,0)=1
f(n,k)=n/k*f(n-1,k-1)
main=getLine>>=putStr.show.f.read.(++")").('(':)

But, if input in the format x y is allowed instead of in the format x,y, it's 74 chars:
f[_,0]=1
f[n,k]=n/k*f[n-1,k-1]
main=interact$show.f.map read.take 2.words

Scala 54
val n,k=readInt
((k+1)to n product)/(1 to(n-k)product)

Python (52)
 f=lambda n,k:k<1or f(n-1,k-1)*n/k;print+f(*input())

Improved from the other two by using print+ to convert the result of f from boolean to int in case k==0.
Still have no idea how to shrink it to 39, I wonder whether they are using lambda at all.

(The OP only loosely specified the input & output method/format, so the following seems acceptable.)
Sage Notebook (39 41 40)
In the current cell,
f=lambda n,k:k<1or f(n-1,k-1)*n/k;+f(*_)

where the input in the form n,k is entered & evaluated in the preceding cell. This simulates "command-line input" by assigning it to _ (similar to command-line arguments).
Sage Notebook (42 44 43)
Alternatively, using "in-source input" (with only the x= and newline characters adding to the score), e.g.,
x=5,2
f=lambda n,k:k<1or f(n-1,k-1)*n/k;+f(*x)

Both of these approaches are obviously spin-offs from earlier answers by others.

Tcl, 80 bytes
proc C n\ k {proc f n {expr $n?($n)*\[f $n-1]:1}
expr [f $n]/([f $k]*[f $n-$k])}

Try it online!

Very ungolfy approach, 165 bytes: https://tio.run/##Tc5LCsMgEAbgvaf4Fy7aQikUeoK4E7xA6qKIC2u0YgwUgme3xhrIbIbRbx5JTaWE@FEY4J@wWI1XEYIk4zTWWScIjPobIqi4jO3TSJlBPWkFP0i@S97lu0n7l@wg2S5Zl26T/c1fqZWk77yd6jTKzrlM7hX6jeSBO8k1o0ZY0oxxqH3Y@nL5AQ

Javascript, 27 bytes
First my own 35-byte solutions:
f=(n,k)=>n-k&&k?f(--n,k)+f(n,k-1):1

Or, alternatively,
f=(n,k,i=k)=>i?f(n-1,k-1,i-1)*n/k:1

The first working recursively, with the simple (n,k) = (n-1,k) + (n-1,k-1) rule. The second using that (n,k) = (n-1,k-1) * n/k.
EDIT
I just noticed the solution by Arnould in a duplicate of this:
f=(n,k)=>k?n*f(n-1,k-1)/k:1

Which is a whopping 8 bytes less (27 bytes)

TI-BASIC, 16 chars (8 bytes)
Ans(1) nCr Ans(2

Input is a list of length 2 in Ans.
Output is the result of the formula defined here.
If the above solution doesn't suffice, then the following 35 chars (24 bytes) solution also works:
Ans(2)!⁻¹(Ans(1)-Ans(2))!⁻¹Ans(1)!

Note: TI-BASIC is a tokenized language.  Character count does not equal byte count.

05AB1E, 1 (or 5?) bytes
c

Builtins ftw ¯\_(ツ)_/¯
Takes two loose inputs, \$k\$ as first and \$n\$ as second.
Try it online.
If the "n,k" format is mandatory, it would be 5 bytes instead:
',¡`c

Try it online.
This will split the (implicit) input on the ","; pop and push both values separated to the stack; and than uses the a choose b builtin.

Excel, 13 chars
=COMBIN(A1,B1

A1 is n, B1 is r. Surprised this wasn't restricted, honestly.

CJam, 19 bytes
l~\_m!@@\_m!@@-m!*/

Try it online!

Japt, 2 bytes
àV

Try it out here

Thunno 2, 1 byte
c

Try it online!
Built-in.
Thunno 2, 9 bytes
w$w÷$$-w÷

Try it online!
Non-built-in.

source: Stack Exchange

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

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

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

sort: votes


text:
What is a good way to deal with tasks that require arrays using Haskell?
Often a task requires real arrays. Take for instance the task to implement Befunge or ><>. I tried to use the Array module for this, but it's really cumbersome, as it feels like I'm coding much too verbose. Can anybody help me how to solve such code-golf tasks less verbose and more functional?

AFAIK, this site is only for code golf itself, not for related questions. I'm guessing that this belongs on Stackoverflow.

@Jesse Millikan: Please also see this question and read the faq. It doesn't states, that you're not allowed to ask any questions about how to golf. This kind of questions were also a big part of the "on topic" question in the definition phase of this site. Please double-think your downvote and remove it if you understand why I'm asking this here.

Hmm, my bad I guess.

@Jesse Millikan: Errare humanum est.

The FAQ is not very clear about it, though.

Yes it is. I'm going to open a meta-question on this issue now.

I've made the question CW, in line with similar "golfing tips in XXX"-type questions. Once we have more consensus with what to do, then more can happen (or not).

For me, this question is ok here, but if this is on Stack Overflow, this wouldn't need to make it CW, and answerers could earn reps at least.

First of all, I recommend looking at Data.Vector, a nicer alternative to Data.Array in some cases.
Array and Vector are ideal for some memoization cases, as demonstrated in my answer to "Finding maximum paths".  However, some problems simply aren't easy to express in a functional style.  For example, Problem 28 in Project Euler calls for summing the numbers on the diagonals of a spiral.  Sure, it should be pretty easy to find a formula for these numbers, but constructing the spiral is more challenging.
Data.Array.ST provides a mutable array type.  However, the type situation is a mess: it uses a class MArray to overload every single one of its methods except for runSTArray.  So, unless you plan on returning an immutable array from a mutable array action, you'll have to add one or more type signatures:
import Control.Monad.ST
import Data.Array.ST

foo :: Int -> [Int]
foo n = runST $ do
    a <- newArray (1,n) 123 :: ST s (STArray s Int Int) -- this type signature is required
    sequence [readArray a i | i <- [1..n]]

main = print $ foo 5

Nevertheless, my solution to Euler 28 turned out pretty nicely, and did not require that type signature because I used runSTArray.
Using Data.Map as a "mutable array"
If you're looking to implement a mutable array algorithm, another option is to use Data.Map .  When you use an array, you kind of wish you had a function like this, which changes a single element of an array:
writeArray :: Ix i => i -> e -> Array i e -> Array i e

Unfortunately, this would require copying the entire array, unless the implementation used a copy-on-write strategy to avoid it when possible.
The good news is, Data.Map has a function like this, insert:
insert :: Ord k => k -> a -> Map k a -> Map k a

Because Map is implemented internally as a balanced binary tree, insert only takes O(log n) time and space, and preserves the original copy.  Hence, Map not only provides a somewhat-efficient "mutable array" that is compatible with the functional programming model, but it even lets you "go back in time" if you so please.
Here is a solution to Euler 28 using Data.Map :
{-# LANGUAGE BangPatterns #-}

import Data.Map hiding (map)
import Data.List (intercalate, foldl')

data Spiral = Spiral Int (Map (Int,Int) Int)

build :: Int -> [(Int,Int)] -> Map (Int,Int) Int
build size = snd . foldl' move ((start,start,1), empty) where
    start = (size-1) `div` 2
    move ((!x,!y,!n), !m) (dx,dy) = ((x+dx,y+dy,n+1), insert (x,y) n m)

spiral :: Int -> Spiral
spiral size
    | size < 1  = error "spiral: size < 1"
    | otherwise = Spiral size (build size moves) where
        right   = (1,0)
        down    = (0,1)
        left    = (-1,0)
        up      = (0,-1)
        over n  = replicate n up ++ replicate (n+1) right
        under n = replicate n down ++ replicate (n+1) left
        moves   = concat $ take size $ zipWith ($) (cycle [over, under]) [0..]

spiralSize :: Spiral -> Int
spiralSize (Spiral s m) = s

printSpiral :: Spiral -> IO ()
printSpiral (Spiral s m) = do
    let items = [[m ! (i,j) | j <- [0..s-1]] | i <- [0..s-1]]
    mapM_ (putStrLn . intercalate "\t" . map show) items

sumDiagonals :: Spiral -> Int
sumDiagonals (Spiral s m) =
    let total = sum [m ! (i,i) + m ! (s-i-1, i) | i <- [0..s-1]]
     in total-1 -- subtract 1 to undo counting the middle twice

main = print $ sumDiagonals $ spiral 1001

The bang patterns prevent a stack overflow caused by the accumulator items (cursor, number, and Map) not being used until the very end.  For most code golfs, input cases should not be big enough to need this provision.

The glib answer is: Don't use arrays. The not-so-glib answer is: Try to rethink your problem so that it doesn't need arrays.
Often, a problem with some thought can be done without any array like structure at all. For example, here's my answer to Euler 28:
-- | What is the sum of both diagonals in a 1001 by 1001 spiral?
euler28 = spiralDiagonalSum 1001

spiralDiagonalSum n
    | n < 0 || even n = error "spiralDiagonalSum needs a positive, odd number"
    | otherwise = sum $ scanl (+) 1 $ concatMap (replicate 4) [2,4..n]

What gets expressed in the code here is the pattern of the sequence of numbers as they grow around the rectangular spiral. There was no need to actually represent the matrix of numbers itself.
The key to thinking beyond arrays is to think about what the problem at hand actually means, not how you might represent it as bytes in RAM. This just comes with practice (perhaps a reason I code-golf so much!)
Another example is how I solved the finding maximal paths code-golf. There, the method of passing the partial solutions as a wave through the matrix, row by row, is expressed directly by the fold operation. Remember: On most CPUs, you can't deal with the array as a whole at once: The program is going to have to operate through it over time. It may not need the whole array at once at any time.
Of course, some problems are stated in such a way that they are inherently array based. Languages like ><>, Befunge, or Brainfuck have arrays at their heart. However, even there, arrays can often be dispensed with. For example, see my solution to interpreting Brainfuck, the real core of its semantics is a zipper. To start thinking this way, focus on the patterns of access, and the structure closer to the meaning of problem. Often this needn't be forced into a mutable array.
When all else fails, and you do need to use an array - @Joey's tips are a good start.

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


text:
Implement Two-Layer Perceptron Algorithm
Train a two-layer perceptron.  You will find the Wikipedia article and these lecture slides useful.
Use a sigmoid activation function for both the hidden and output layers, $$\sigma(x) = \frac{1}{1 + e^{-x}}$$
Your function should take in a list or array of input/output pairs and an integer specifying how many training passes through the input set to make.  Both the input and output will be vectors of any convenient representation in your language.  You should output or otherwise initialize a classifier function or object.
Initialize the weights randomly and to prevent overflow/underflow, normalize the weight vectors after each update.
You should handle input data vectors up to 1000 dimensions and at least 10 output dimensions.  The classifier function should return a vector of the activation levels of each of the outputs.
You may assume access to implementations of all of the BLAS routines.
The MNIST database has a very large training and test set you might find useful for testing purposes.
EDIT: Example dataset.
Input and output vectors (input).

Input  Output
[0,0]   [0]
[0,1]   [1]
[1,0]   [1]
[1,1]   [0]

Your program should produce a classifier that takes in a vector of two elements and returns a vector of one element that has similar behavior as the input.

Which learning algorithm? What about examples or testcases? (We should just search the MNIST? :-/)

The backpropagation algorithm.  Minimize the MSE of the classifier output against the training data by gradient descent.  I admit MNIST database is a bit (okay, very) large, but you should be able to solve a version of the XOR problem.

This seems far too open ended to be a code-golf problem. It would be very hard to compare solutions in terms of source-code character count when they could be doing very different things. I would suggest narrowing this down to a particular training set, and and quantifiable, and testable measure of success on a given test set. Input and output formats should be rigidly defined, and hence enable testability. This would level the field significantly, and better allow code size comparisons to be meaningful.

I'm going to cheat here, hence community wiki: instead of logistic sigmoid, I'll use the hyperbolic tangent and instead of backprop, I'll use ELM to train the perceptron. Here's the version for XOR, in Python, using BLAS via SciPy.
import numpy as np
from scipy.linalg import pinv2

n_hidden = 10  # hyperparameter

# Training set
X_train = np.array([[0,0], [0,1], [1,0], [1,1]])
y_train = [0, 1, 1, 0]

# set hidden layer parameters randomly
w = np.random.randn(X_train.shape[1], n_hidden)
b = np.random.randn(n_hidden)

# compute hidden layer activation
H = np.tanh(np.dot(X_train, w) + b)

# fit output layer parameters
beta = np.dot(pinv2(H), np.atleast_2d(y_train).T)

# prediction and evaluation
pred_train = (np.dot(H, beta) > .5).ravel()
print "Training set accuracy:", np.mean(pred_train == y_train)

I previously published a digits classification script using this algorithm. After removing comments, this is 11 lines of code @ 425 characters.

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


text:
Program that runs when rows and columns are transposed
I posted this to The Daily WTF coder challenge forum a few years ago but only got one response. I figure CodeGolf stack exchange might generate more interest!
Description
Write a program that runs when the rows and columns of the source code are transposed.
In other words, imagine each character on each line is a cell in a matrix (pad out shorter lines as necessary to make the matrix rectangular). Write a functioning program that still functions even if its "matrix" is transposed.
This is just a creative puzzle, not a golf.
Details

The program must execute without error and do something interesting*
The transpose of the program must execute without error and do something interesting, although not necessarily the same thing as the original.
Any language.
No shebang required.
Single row/single column entries disallowed.

*Interesting is the subjective opinion of the CodeGolf community.
Deadline April 15 2011
Trivial Example
Here's a really stupid example, but it illustrates the rules pretty well. Of course, any "symmetric" program will meet this challenge, but I encourage you to try non-symmetric programs.
# #####################
 print "hello,world\n";
#r
#i
#n
#t
#
#"
#h
#e
#l
#l
#o
#,
#w
#o
#r
#l
#d
#\
#n
#"
#;

Transposer Reference Implementation
Here's a perl snippet that does the type of transposing that I am talking about. This is not the objective of the puzzle, it is just a helper tool.
#!/usr/bin/perl
my @matrix;
open('SOURCE', $ARGV[0]);
my $matrixwidth = -1;
my $matrixheight = 0;
foreach (<SOURCE>) {
  chomp;
  if ($matrixwidth < length $_) {$matrixwidth = length $_}
  my @row = split(//, $_);
  push @matrix, \@row;
  $matrixheight++;
}
foreach my $x (0 .. ($matrixwidth-1)) {
  foreach my $y (0 .. ($matrixheight-1)) {
    print(defined $matrix[$y]->[$x] ? $matrix[$y]->[$x] : ' ');
  }
  print "\n";
}

Uninteresting set of solutions: Any program in a  whitespace-insensitive language with single character operators and keywords (like APL, J, GoldScript, Jack Chrenshaw's TINY...) can qualify simply my writing it on one line.

I can just put 1 into a source file and have a quine that still works when transposing the lines ...

Correction: any such program that only involves single character literals.

@Joey, I don't think that would meet the first requirement (interesting behavior).

@Joey I added a rule that submissions need to be more than 1 row or 1 column in size. @dmckee I am not familiar with those languages. Can you clarify your issue? Assuming that the operators have operands, then transposing the program will modify the order of the operator and operands, potentially separating the two in a way that's not syntactically correct. Hence the challenge. Unless I'm being naive?

mehaase: That's unfortunately a purely subjective criterion and very hard to judge. So generally you don't like quines, apparently :-). Still, what dmckee said holds true, I can just take nearly any Golfscript program fitting into a single line and call that a transposable program.

@mehaase: Your edit disallowing single column/line solutions solves the problem. They are just languages where everything is one character long and newlines are not significant.

Anyone up for doing this in a Befunge-type language?

c
Not-quite-trivial, not-quite-symmetric solution that prints it's command line arguments, one per line. As shown it prints them in order, as transposed in reverse order.
/*******ipcc;m(acaw-{aa)
********nuohiairhrh-prr;
********ttnaningagiaugg}
******** ssrtntcrvlrtvc}
******** (t*   ,*)egs[]
********   s    *{(c(
********   )       )
*******/
int
puts(
const
char*s)
;int
main
(int
argc,
char**
argv){
int i;
for(i=1;
i<argc;
i++)
{puts(
argv[i]
);}}

Haha! Very interesting approach! +1

I like the starry blob in the upper-left corner ;)

@mehaase: Frankly I didn't think it was philosophically different than your "trivial" example. I just thought the trick with the block comment was cute. In principle it is extensible to any two complete programs.

Well, april 15 came and went with no other submissions :( But congrats, you win the mini-contest!

Here's one I came up with when I originally wrote the challenge a few years back. It's a perl script that can transpose other scripts. You can run it on itself, save the output as a new script, then run that new script on itself to get the original.
#######       p           $f f   ]'
#      ofm    u        $  ho o   -
#      poy    s        w  +r r  p>'
#      er ####h########=##+ #   r[}
    open   'M' , $ARGV[ 0]  ; # i$p
  for(;   <M>  ; ){         #   nxr
      #((@             $  }( (  t]i
      #';r             #   $ $   ?n
      #M<=    @        r   x y   $t
      #'M     m        +   = =   m
      # >     ,        1   0 0   ["
my @r=   $_ =~ /./g;#  >   ; ;   $\
      #  _ /  \                # yn
push @m,     \@r;              # ]"
      # ;=    r            $ $   -}
      #  ~    ;        $   x y   >
$w=($#r   + 1>        $w)      # [
?$#r+1:     $w ;$h++}# ?   < <   $
for (     $x=0 ;$x<$w;         # x
          $x++ ){              # ]
for (     $y=0 ;$y<$h;
          $y++ ){           #$
  print               #$   $ h  d:
defined                #   w ;  e
      #$)/    #        r   ; $  f
      #A{.             +   $ y  i
      #R#/             1   x +  n
      #G g             :   + +  e
      #V ;                 + )  d
     $m[  $y]->[$x]
      #0 #                 ) {  $
 ?$m[$y]->[$x]:' '}          #  m
      #)               $   {    [
      #;               w        $
  print "\n"} #        ;        y

Look! Line noise in a sparse matrix!


text:
Squares in Movement Range
There are two inputs, the first input is a map in 2D array, where 2 represents an obstacle and 0 represents a regular ground, and 1 represents the player's location (implies that the player is standing on ground), the second input is the player's movement range.
A player can move on the map (horizontally, vertically, but not diagonally) within the movement range (0 to movement range inclusive), and the player can travel through an obstacle, but only one at a time. At last, a player cannot stand on an obstacle.
The program outputs an 2D array of booleans, showing all possible squares the player can move to.
Here are some examples:
Input
________
_____#__
___+__#_
#__#____
________, range=2
(_ = 0, + = 1, # = 2)

Output
___+____
__+++___
_+++++__
__+_+___
___+____ (+ = true, _ = false)

Input
__________
__________
______#___
__#_+##___
__________
____#_____
__________, range=4

Output
___+++____
__+++++___
_+++++_+__
++_++_____
_+++++++__
__++_++___
___+++____

There will be two winners: shortest brute-force and shortest efficient algorithm (the map and the movement range can get arbitrarily large)

Python, 284 characters
def M(A,R):
 X,Y=range(len(A[0])),range(len(A))
 G,P,H=[set(x+1j*y for x in X for y in Y if A[y][x]>=z) for z in(0,1,2)]
 P-=H
 for i in' '*R:P|=G&reduce(lambda x,y:x|y,[set(p+d for p in P)-(H&set(p+d for p in H))for d in(1,1j,-1,-1j)])
 return[[x+1j*y in P-H for x in X]for y in Y]

def display(A):print'\n'.join(''.join('_+'[c]for c in r)for r in A)

A=[[0,0,0,0,0,0,0,0],
   [0,0,0,0,0,2,0,0],
   [0,0,0,1,0,0,2,0],
   [2,0,0,2,0,0,0,0],
   [0,0,0,0,0,0,0,0]]
display(M(A,2))

A=[[0,0,0,0,0,0,0,0,0,0],
   [0,0,0,0,0,0,0,0,0,0],
   [0,0,0,0,0,0,2,0,0,0],
   [0,0,2,0,1,2,2,0,0,0],
   [0,0,0,0,0,0,0,0,0,0],
   [0,0,0,0,2,0,0,0,0,0],
   [0,0,0,0,0,0,0,0,0,0]]
display(M(A,4))

The main M routine takes the 2D array containing the map and the range, and returns the 2D array of booleans.
G is the set of all indexes of (in-bounds) squares, encoded as complex numbers.  H is the same but for the obstacles, and P is the same for the player.  The main loop updates P by moving P in each of the 4 cardinal directions, filtered by the obstacles and the bounds of the array.


text:
Additive Persistence
The shortest code to pass all possibilities wins.
In mathematics, the persistence of a number measures how many times a certain operation must be applied to its digits until some certain fixed condition is reached.  You can determine the additive persistence of a positive integer by adding the digits of the integer and repeating.  You would keep adding the digits of the sum until a single digit number is found.  The number of repetitions it took to reach that single digit number is the additive persistence of that number.
Example using 84523:
84523
8 + 4 + 5 + 2 + 3 = 22
2 + 2 = 4

It took two repetitions to find the single digit number.
So the additive persistence of 84523 is 2.

You will be given a sequence of positive integers that you have to calculate the additive persistence of.  Each line will contain a different integer to process.  Input may be in any standard I/O methods.
For each integer, you must output the integer, followed by a single space, followed by its additive persistence.  Each integer processed must be on its own line.
Test Cases

Input Output
99999999999 3
10 1
8 0
19999999999999999999999 4
6234 2
74621 2
39 2
2677889 3
0 0

Your test cases include some values which are over 2^64, and your spec says that the program only has to handle values up to 2^32. Might be worth clearing that up.

@Peter Taylor, forgot to remove those limits.  If a program can handle the input I have provided, it shouldn't have an issue with limits.

Isn't 999999999999's persistence 2 instead of 3?

@Evelex, that was an incorrect last minute change I guess. Fixed.

Several answers here aren't doing output on stdout but rather use J's "interactive" output by returning results after taking command line input. (This includes 2 other J answers and, I'm guessing, the K answer.) Is this considered legit? Because I can shed 18-ish characters if so.

@Jesse Millikan, the problem doesn't state it must output to stdout.

It does state "followed by a single space," and, "on it's own line", which seems to imply at least some kind of string output. Also, interactive J doesn't format them as stated if there are inputs of different lengths.

"Also, interactive J doesn't format them as stated if there are inputs of different lengths."  What do you mean by that?

I meant outputs of different lenghts,  though it's  irrelevant... I was hallucinating or something. Both of the J answers are doing the output as given.

@Jesse Millikan, The K answer outputs a formatted string to stdout and not to the interactive prompt.

K - 29 Chars
Input is a filename passed as an argument, 29 chars not including filename.
`0:{5:x,-1+#(+/10_vs)\x}'.:'0:"file"

35 -> 31: Remove outside function.
31 -> 29: Remove parens.

-1+# => #1_

Python 84 Chars
while 1:
 m=n=int(raw_input());c=0
 while n>9:c+=1;n=sum(map(int,str(n)))
 print m,c

Challenge case:06234 .. result successful challenge :-)

Python (93 bytes)
f=lambda n,c:n>9and f(sum(map(int,str(n))),c+1)or c
while 1:n=int(raw_input());print n,f(n,0)

i think you can remove the space between 9 and err...and

and input() instead of int(raw_input())....

@st0le:Try this input with that modification:06234.

Haskell, 100 characters
p[d]=0
p d=1+(p.show.sum$map((-48+).fromEnum)d)
f n=n++' ':shows(p n)"\n"
main=interact$(f=<<).lines

You can save 6 bytes by using read.pure instead of (-48+).fromEnum, try it online!

Husk, 10 15 bytes
+5 bytes for horrible I/O requirement
m(wΓ·,LU¡oΣdr)¶

Try it online!
Explanation
To support multiple inputs, we need to use m(₁r)¶ (where ₁ is the function doing the interesting computation):
m(₁r)¶  -- expects newline-separated inputs: "x₁␤x₂␤…␤xₙ"
     ¶  -- split on newlines: ["x₁","x₂",…,"xₙ"]
m(  )   -- map over each string
 ( r)   -- | read integer: [x₁,x₂,…,xₙ]
 (₁ )   -- | apply the function described below

The function ₁ does the following:
wΓ·,LU¡(Σd)  -- input is an integer, eg: 1234
      ¡(  )  -- iterate the following forever and collect results in list:
       ( d)  -- | digits: [1,2,3,4]
       (Σ )  -- | sum: 10
             -- : [1234,10,1,1,1,…
     U       -- keep longest prefix until repetition: [1234,10,1]
 Γ           -- pattern match (x = first element (1234), xs = tail ([10,1])) with:
  · L        -- | length of xs: 2
   ,         -- | construct tuple: (1234,2)
w            -- join with space: "1234 2"

bash, 105 chars
while read x
do
for((i=0,z=x;x>9;i++))do
for((y=0;x>0;y+=x%10,x/=10))do :
done
x=$y
done
echo $z $i
done

Hardly any golfing actually involved, but I can't see how to improve it.

Haskell - 114
s t n|n>9=s(t+1)$sum$map(read.(:[]))$show n|1>0=show t
f n=show n++" "++s 0n++"\n"
main=interact$(f.read=<<).lines

You can save 4 bytes by using pure over (:[]) and defining an operator instead of s, try it online!

Ruby, 85 Chars
puts $<.map{|n|v=n.chop!;c=0;[c+=1,n="#{n.sum-n.size*48}"] while n[1];[v,c]*' '}*"\n"

I had to borrow the "sum-size*48" idea from Alex, because it's just too neat to miss (in Ruby at least).

Golfscript, 40 chars
n%{.:${;${48-}%{+}*`:$,}%.,1>\1?+' '\n}%

J - 45 Chars
Reads from stdin
(,' ',[:":@<:@#+/&.:("."0)^:a:)&><;._2(1!:1)3

I was trying to use ^:a: myself but I couldn't find some proper documentation... any hints?

The dictionary entry for u^:n has info on its usage but it is a bit dense. ^:a: is like any other call to power but it collects the results and ends when the argument to consecutive calls is the same(converges).

@Eelvex FWIW I discovered a: through the ^:a: trick in the J Reference Card[PDF]

@JB: That's the only reference on ^:a: that I knew :D

@Eelvex Oh. I had the opposite experience then. I discovered the functionality in the dictionary, and used it as some variant of ^:(<'') at first (probably for Kaprekar), until I spotted it in the card, and learned about a: for the occasion.

c -- 519
(or 137 if you credit me for the framework...)
Rather than solving just this one operation, I decided to produce a framework for solving all persistence problems.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char*(*O)(char*);
char*b(char*s){long long int v=0,i,l=0;char*t=0;l=strlen(s);t=malloc(l+2);
for(i=0;i<l;i++)v+=s[i]-'0';snprintf(t,l+2,"%lld",v);return t;}
int a(char**s,O o){int r;char*n;n=o(*s);r=!strcmp(*s,n);free(*s);
*s=n;return r;}
int main(int c, char**v){size_t l, m=0;char *d,*n=0;O o=b;FILE*f=stdin;
while(((l=getline(&n,&m,f))>1)&&!feof(f)){int i=0;n=strsep(&n,"\n");
d=strdup(n);while(!a(&n,o))i++;printf("%s %d\n",d,i);free(d);free(n);n=0;m=0;}}

Only the two lines starting from char*b are unique to this problem.
It treats the input as strings, meaning that leading "0"s are not strip before the output stage.
The above has had comments, error checking and reporting, and file reading (input must come from the standard input) striped out of:
/* persistence.c
 *
 * A general framework for finding the "persistence" of input strings
 * on opperations.
 *
 * Persistence is defined as the number of times we must apply
 *
 *    value_n+1 <-- Opperation(value_n)
 *
 * before we first reach a fixed point.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "../getline.h"

/* A function pointer type for operations */
typedef char*(op_func)(char*);
typedef op_func* op_ptr;
/* Op functions must
 * + Accept the signature above
 * + return a point to a newly allocated buffer containing the updated str
 */

char* addop(char*s){
  int i,l=0;
  long long int v=0;
  char *t=NULL;
  /* protect against bad input */
  if (NULL==s) return s;
  /* allocate the new buffer */
  l = strlen(s);
  t = malloc(l+2);
  if (NULL==t) return t;
  /* walk the characters of the original adding as we go */
  for (i=0; i<l; i++) v += s[i]-'0';
  //fprintf(stderr,"   '%s' (%d) yields %lld\n",s,l,v);
  snprintf(t,l+2,"%lld",v);
  //fprintf(stderr,"   %lld is converted to '%s'\n",v,t);
  return t;
}

/* Apply op(str), return true if the argument is a fixed point fo
 * falsse otherwise,
 */
int apply(char**str, op_ptr op){
  int r;
  char*nstr;
  /* protect against bad input */
  if ( NULL==op ) exit(1);
  if ( NULL==*str ) exit(4);
  /* apply */
  nstr = op(*str);
  /* test for bad output */
  if ( NULL==nstr ) exit(2);
  r = !strcmp(*str,nstr);
  /* free previous buffer, and reasign the new one */
  free(*str);
  *str = nstr;
  return r;
}

int main(int argc, char**argv){
  size_t len, llen=0;
  char *c,*line=NULL;
  op_ptr op=addop;
  FILE *f=stdin;
  if (argc > 1) f = fopen(argv[1],"r");
  while( ((len=getline(&line,&llen,f))>1) && line!=NULL && !feof(f) ){
    int i=0;
    line=strsep(&line,"\n"); // Strip the ending newline
    /* keep a copy for later */
    c = strdup(line);
    /* count necessary applications */
    while(!apply(&line,op)) i++;
    printf("%s %d\n",c,i);
    /* memory management */
    free(c);
    free(line);
    line=NULL;
    llen=0;
  }
}

A little more could be saved if we were willing to leak memory like a sieve. Likewise by #defineing return and the like, but at this point I don't care to make it any uglier.

273 bytes

APL (Dyalog Unicode), 21 17 bytes
{⍵≤9:0⋄1+∇+/⍎¨⍕⍵}

-4 bytes from Jo King.
Try it online!
{s←+/⍎¨⍕⍵⋄⍵≤9:0⋄1+∇s}

Try it online!
Explanation
{s←+/⍎¨⍕⍵⋄⍵≤9:0⋄1+∇s} ⍵ → input
       ⍕⍵             convert ⍵ to string
     ⍎¨               execute each character(getting digits)
   +/                 reduce to sum of digits
 s←                   assign to s
          ⍵≤9:        if number is single digit
              0       return 0, stop recursion
                1+∇s  Otherwise return 1+f(sum)

Bad habits.....

J, 74 chars
i=:<;._2(1!:1)3
i&((],' ',":@(0 i.~9<[:".([:":[:+/"."0)^:(i.9)))@>@{~)i.#i

Edits

(86 → 83)  Some Caps [: to Ats @
(83 → 79)  Unneeded parentheses
(79 → 75)  Changing 0". to ". simplifies things
(75 → 74)  Better Cutting

E.g
i=:<;._2(1!:1)3
74621
39
2677889
0
i&((],' ',":@(0 i.~9<[:".([:":[:+/"."0)^:(i.9)))@>@{~)i.#i
74621 2
39 2
2677889 3
0 0

Output  is formatted wrong for multiple inputs. See "single space"

@Jesse: I see nothing wrong. Could you write an example please?

I have no idea, I'm seeing things I guess.

K (ngn/k), 16 bytes
Solution:
{x,#1_(+/10\)\x}

Try it online!
Explanation:
{x,#1_(+/10\)\x} / the solution
{              } / lambda taking implicit x
      (     )\x  / iterate until convergence
         10\     / split into base-10 (123 => 1 2 3)
       +/        / sum
    1_           / drop first result (iterate returns input as first result)
   #             / count length of result
 x,              / prepend x (original input)

Jelly, 12 bytes
żDS$Ƭ€Ẉ’ƊK€Y

Try it online!
Takes input as a list of integers. +3 bytes to input as a multiline string.
+3 bytes (or +6) for restrictive I/O formats, yay
How it works
żDS$Ƭ€Ẉ’ƊK€Y - Main link. Takes a list l on the left
        Ɗ    - To l:
   $         -   Group the previous 2 links into a monad f(n):
 D           -     Digits
  S          -     Sum
    Ƭ€       -   Over each n in l, repeatedly apply f(n) until a fixed point,
                  yielding [n, f(n), f(f(n)), ...]
      Ẉ      -   Get the length of each loop
       ’     -   Decrement each
ż            - Zip the loop lengths with l
         K€  - Join each by spaces
           Y - Join by newlines

Vyxal aj, 9 8 bytes
ƛ⁽∑↔L‹"Ṅ

Try it Online!
Explanation:
          # Treat all the inputs as a list (`a` flag)
ƛ         # On each item (n) in that list
 ⁽        # Create a single element lambda
  ∑       # That sums the digits of a number
   ↔      # Apply that function on n until it doesn't change
          # and return the intermediate values in a list
    L     # Get the length of that list
     ‹    # Decrement it to ignore the last time the function is called
      "   # Pair that with n
       Ṅ  # Join the pair by a space
          # Join the mapped inputs by new lines (`j` flag)
          # Implicitly print

@Steffan Dammit, I misread those rules.

@Steffan I don't think the İ approach works, for 8 it outputs 1 but it should be 0

Steffan's approach works with the A flag.

@emanresuA Hmm, can you show me?

Wait nvm, that separates by  =>

I think this is about the best I can come up with.
Ruby 101 Chars
f=->(n){n.sum-n.size*48}
$<.each{|l|i=0;i+=1 while(i+=1;n=f[(n||l.chop!).to_s])>10
puts "#{l} #{i}"}

Actually, chop! instead of chomp! gives me a one character savings. 97 chars.

Just did some more golfing at it - 91 chars.

PARI/GP 101 Chars
s(n)=r=0;while(n>0,r+=n%10;n\=10);r
f(n)=c=0;while(n>9,c++;n=s(n));c
while(n=input(),print(n," ",f(n)))

Unfortunately, there's no input function for GP, so i guess this lacks the IO part. :(
Fixed: Thanks Eelvex! :)

Sure there is: input() :)

@Eelvex, done. :)

Javascript - 95
i=prompt();while(i>9){i=''+i;t=0;for(j=0;j<i.length;j++)t+=parseInt(i.charAt(j));i=t;}alert(t);

EDIT: Whoops does'nt do the multi-lines

Just noticed this doesn't output it correctly.

J, 78
f=:[:+/"."0&":
r=:>:@$:@f`0:@.(=f)
(4(1!:2)~LF,~[:":@([,r)".@,&'x');._2(1!:1)3

Recursive solution. Reads from stdin. Writes to stdout, so cut me some slack - it does take an extra 18-ish characters.

Perl - 77 characters
sub'_{split//,shift;@_<2?0:1+_(eval join'+',@_)}chop,print$_,$",(_$_),$/for<>

scala 173:
def s(n:BigInt):BigInt=if(n<=9)n else n%10+s(n/10)
def d(n:BigInt):Int=if(n<10)0 else 1+d(s(n))
Iterator.continually(readInt).takeWhile(_>0).foreach(i=>println(i+" "+d(i)))

JavaScript, 57 47 bytes
-10 bytes thanks to @l4m2!
f=(s,c=0)=>s>9?f(eval([...s+""].join`+`),++c):c

Try it online!

f=(s,c=0)=>s>9?f([...s+""].reduce((x,y)=>x*1+y*1),++c):c

f=(s,c=0)=>s>9?f([...s+""].reduce((x,y)=>x- -y),++c):c

f=(s,c=0)=>s>9?f(eval([...s+""].join`+`)),++c):c

@l4m2 Thanks! s>9 and eval were great ideas. I think you had an extra paren in there, making it a total of 10 bytes you saved me :-)

Note the strict I/O ;)

Japt -R, 21 19 bytes
Ë+S+(DsÊÉ ÆD=ìxÃâ Ê

Try it

05AB1E, 13 10 bytes
ε.ΓSO}g}ø»

-3 bytes thanks to @Steffan
Input as a list of integers.
Try it online.
Explanation:
ε      # Map each integer in the (implicit) input to:
 .Γ    #  Loop until the integer no longer changes,
       #  keeping all intermediate steps in a list:
   S   #   Convert the integer to a list of digits
    O  #   Sum those digits together
  }g   #  After the inner loop: pop and push the length
}ø     # After the outer map: zip/transpose it with the (implicit) input to create a
       # list of pairs
  »    # Join each pair by a space, and then the list of strings by newlines
       # (after which the result is output implicitly)

10 bytes: ε.ΓSO}g}ø»

MathGolf, 11 bytes
hÅ_Σ]▀£(k ?

Try it online!
Incredibly inefficient, but we don't care about that. Basically, using the fact that the additive persistence of a number is smaller than or equal to the number itself.
Uses the fact that the additive persistence is less than or equal to the number of digits of the number. Passes all test cases with ease now.
The input format, while suboptimal for some languages, is actually the standard method of taking multiple test cases as input in MathGolf. Each line of the input is processed as its own program execution, and output is separated by a single newline for each execution.
Explanation (using n = 6234)
h             push length of number without popping (6234, 4)
 Å            loop 4 times using next 2 operators
  _           duplicate TOS
   Σ          get the digit sum
    ]         wrap stack in array
              this gives the array [6234, 15, 6, 6, 6]
     ▀        unique elements of string/list ([6234, 15, 6])
      £       length of array/string with pop (3)
       (      decrement (2)
        k ?   push input, space, and rotate top 3 elements to produce output (6234 2)

Julia, 92 (29) bytes
f(n)=n>9&&(f∘sum∘digits)(n)+1

Edit:
With correct printing it's 92:
f(n)=n>9&&(f∘sum∘digits)(n)+1
while(n=parse(Int128,readline()))≢π
println("$n ",f(n)%Int)end

Stax, 8 11 bytes
ªwæMε∞ö?îm⌐

Run and debug it
+3 bytes thanks to  @Khuldraeseth (the first answer didn't have compliant output)

I reached the same solution, but with i in place of u. Adhering to the draconian IO specifications, this becomes 11 bytes.

Oops.  I guess I didn't read the IO requirements very well.  I'll update my answer.

Jq -r, 52 bytes
[while(length>1;explode|map(.-48)|add|@text)]|length

-r                    # take one number per line, converting it to a string

                explode                              # the character codes
                       |map(.-48)                    # subtract ascii zero from each
                                 |add                # sum the elements
                                     |@text          # back to text, (shorter than
                                                     # tostring and tojson)
 while(length>1;                           )         # produces *all* the intermediate
                                                     # results while the string length>1
[                                           ]        # collected into an array
                                             |length # the length of these results

Not answering the multiplicative persistence now because jq doesn't have a product builtin :)
Jq play it!

Knight, 54 bytes
;=iP;=r 0;W<1Li;=s 0;Wi;=s+sA Ai=iGi 1Li;=i+""s=r+1rOr

Try it online!

Ly, 21 bytes
0s+1[pSy,![lu;]&+l`s]

Try it online!
A pretty straight forward interpretation of the challenge rules this time.
0s+1[pSy,![lu;]ç]
0s                    - initialize the backup cell to 0 (iteration count)
  +                   - load input number, absorbing the 0 on the stack
   1                  - push a truthy value to enter loop
    [p              ] - infinite loop
      S               - convert number on top of stack to digits
       y              - push the number of digit (stack size)
        `!            - decrement and convert truthiness
          [   ]       - if/then, executes is number is a single digit
           lu;        - load backup cell, print as number, end program
               &+     - sum the digits on the stack
                 l`s  - load backup cell (iterations) increment and save

Tcl, 95 bytes
proc P {v n\ 0} {set V $v
while \$v>9 {set v [expr [join [split $v ""] +]]
incr n}
puts $V\ $n}

Try it online!

Because the next newest answer is a full 6 years old, which i think is before TIO existed

C (gcc), 87 85 bytes

Saved two bytes thanks to ceilingcat; pulling the t=s assignment forward and using (t=s)[1] ~ *((t=s)+1) ~ *(1+(t=s)) ~ 1[t=s].

f(n,p){char*t,s[99];for(p=0;sprintf(s,"%d",n),1[t=s];p++)for(n=0;*t;n+=*t++-48);n=p;}

Try it online!

@ceilingcat That is quite neat.

Perl 5, 65 bytes
$b=0;$q=s/\n//r;$_=eval s/./+$&/gr while y///c>1&&++$b;say"$q $b"

Try it online!

Java (OpenJDK 8), 79 bytes
a->{int d=0;while(a/10>0){int c=0;d++;while(a>0){c+=a%10;a/=10;}a=c;}return d;}

Try it online!
There's probable potential to golf it further, but I'll look into that in the future, but for now, I'm pretty happy with this little result.

70 bytes.

Building on @JonathanFrech 67 bytes

Python 3, 82 bytes
while 1:f=lambda n:n//10and 1+f(sum(map(int,str(n))));i=input();print(i,f(int(i)))

Japt, 28 bytes
Ë+S+(@D=X©A<D©ì x ªD D<AÃaÃ·
Ë                            // Map over the inputs and return each, followed by
 +S+                         // a space, followed by the number's persistence.
      D=     ©ì x            // To find it, fold the number up
        X©A<D     ªD         // if we can (handles unfoldable cases),
    (@               D<AÃa   // until it can't be folded up any further.
                          Ã· // Then, join everything up with newlines.

Try it online!

PHP, 72+1 bytes
+1 for -R flag.
for($i=0,$a=$argn;$a>9;$i++)$a=array_sum(str_split($a));echo"$argn $i
";

Run as pipe with -R.

running PHP as pipe will execute the code once for every input line
but it does not unset variables inbetween; so $i must be initialized.
(Also, it would print nothing instead of 0 for single digits without the initialization.)

Bash+coreutils, 83 bytes
[ $1 -le 9 ]&&exit $2
let x=$2+1
for z in `fold -w1<<<$1`
do let y+=$z
done
a $y $x

Try it online!
Should be saved to a script called a and placed in the system's PATH, as it calls itself recursively. Takes input from command line, like a 1999. Returns by exit code.
TIO has some limitations on what you can do with a script, so there's some boilerplate code to make this run in the header.
Prints an error to stderr for input larger than bash integers can handle, but since the actual computation is done with strings, it still gives the right result anyway.

Python 3, 76 bytes
def f(n,i=0,p=0):p=p or n;f(sum(map(int,str(n))),i+1,p)if n>9else print(p,i)

Try it online!

Without I/O restrictions:
Python 3, 54 bytes
f=lambda n,i=0:f(sum(map(int,str(n))),i+1)if n>9else i

Try it online!

Swift 5, 106 bytes
func a(_ s:S,_ i:I)->(S,I){if s.count<=1{return(s,i)};return a(S(s.compactMap{I(S($0))}.reduce(0,+)),i+1)}

Try it online!

Python 2, 62 bytes
f=lambda x,i=0:f(`sum(int(i)for i in x)`,i+1)if len(x)>1else i

Python 3, 50 bytes
f=lambda n:0if n<10else-~f(eval('+'.join(str(n))))

Recursive function. Takes an integer, returns an integer.
Explanation:
# create a lambda function which takes one argument, and assign it to f
f=lambda n:\
    # if n is 0-9, it's persistence 0
    0if n<10\
        # otherwise, add one to the running total and recursively call f
        # ( ~ will invert the returned number, equivalent to -n-1)
        # (negating that gives you -(-n-1) = n+1)
        else-~f(
            # convert integet to string, join each character with a '+'
            # gives a string like '1+2+3+4+...+n'
            # evaluate the string as an expression, giving a new integer
            # pass that integer back into f
            eval('+'.join(str(n)))
        )

Pyth, 17 bytes
FG.Qs[Gdtl.usjNTG

Try it online!
If I can instead of values on different lines, take a list of numbers (in the format [9999999999, 10, 8, etc.]), then -1 byte by replacing .Q with Q
F                  # For
 G.Q               #   G in the complete input (split by newlines)
    s[             #     join the list as string, create list from the following values:
      Gd           #       G, " " (for output formatting),
        tl         #       decrement length of
          .u    G  #          List of all intermediate results until there's a returning result, with starting value G
            s      #            reduce on + (add all list elements) the list:
             j     #              convert to integer as list:
              N    #                The current value (implicit input to .u)
               T   #                in base 10 (T=10)

><>, 36 bytes
0{:a(7$.0}\~1+!
~n
1:,a}+{%a:/?(1:-%

Try it online!

Nibbles, 7 bytes (14 nibbles)
:$,>>`.$/`@~$+

                    # (implicitly map over input):
:$                  # prepend input onto
  ,                 # length
   >>               # (without first item) of
     `.             # iterate while unique
       $            # starting with input number:
         `@~$       #   convert to base-10 digits
        /           #   and fold over this list
             +      #     adding its elements

Go, 77 bytes
func f(n int)int{s:=0
if n<10{return 0}
for;n>0;n/=10{s+=n%10}
return 1+f(s)}

Attempt This Online!


text:
Last k digits of Powers of 2

For any integer \$r\$, there exists a
power of 2 each of whose last \$r\$ digits
are either 1 or 2.

Given \$r\$, find the smallest \$x\$ such that \$2^x\bmod{10^r}\$ consists of only 1 or 2.
For \$r=2\$, \$x=9\$, since \$2^9=5\color{blue}{\textrm{12}}\$
For \$r=3\$, \$x=89\$, since \$2^{89}=618970019642690137449562\color{blue}{\textrm{112}}\$
Note: for \$r=4\$, \$x\$ is \$=89\$ (again)
Input : \$r \leq 100\$
Output : \$x\$
Eg.

Input : 2
Ouput : 9
Input : 3
Ouput : 89

The program should run in a reasonable amount of time.
EDIT: The oeis sequence for this challenge is A147884.

The OEIS for this task is A147884

@Debanjan, yes true. @S.Mark, powers of 2, not 3.

I have a paper, which describes an efficient algorithm. i'll post it if someone can't get move forward with it.

@st0le:Complexity?

@whacko_Cracko, err, i'm pretty sure it's linear (not sure though)...there's a pattern to be found.

Python, 166 chars
k,f,g=1,4,16
i=j=2
n=input()
m=10**n
a=lambda c:c('')-1-i or c('1')+c('2')-c('')+1
while i<=n:
 while a(str(j)[-i:].count):j,k=j*g%m,k+f
 i,g,f=i+1,g**5%m,f*5
print k

Great job, Mark :) I guess you found it :)

You can save a few bytes using semicolons: 161 bytes

Wolfram Language (Mathematica), 78 76 57 55 bytes
(x=0;While[Max@Abs[2IntegerDigits[2^++x,10,#]-3]>1];x)&

Try it online!
IntegerDigits[a,10,r] generates a list of the r last decimal digits of a. Subtract 3/2 and check that they are all either -1/2 or +1/2.
Timing check: 20 seconds on TIO for r = 1 .. 10.
Wolfram Language (Mathematica), 102 95 91 89 bytes
k/.FindInstance[Mod[n=0;Nest[#+10^n(2-Mod[#/2^n++,2])&,0,#]-2^k,5^#]==0,k,Integers][[1]]&

Try it online!
This solution is much longer but much faster. By taking the path suggested in OEIS A147884 to go via OEIS A053312, as well as using FindInstance magic, TIO manages to compute r = 1 .. 12 in less than a minute.

Ruby - 118 chars
k,f,g,m=1,4,16
i=j=2
m=10**(n=gets.to_i)
((k+=f;j=j*g%m)until j.to_s=~%r{[12]{#{i}}$};i+=1;f*=5;g=g**5%m)until n<i
p k

Haskell, 115 characters
import List
main=readLn>>=print. \r->head$findIndices(all(`elem`"12").take r.(++cycle"0").reverse.show)$iterate(*2)1

Python 3, 63 bytes
f=lambda i,c=2:f(i,c+1)if{*str(2**c)[-i:]}-{*'12'}else c**(i>1)

Try it online!

05AB1E, 18 15 bytes
∞.Δo©‹®I.£2X:`P

Try it online or verify the first 8 test cases (any more times out).
Explanation:
Uses the fact that \$2^x > r\$ for all possible results, to ensure we have enough digits to get the last \$r\$ digits of \$2^x\$.
∞.Δ            # Find the first positive integer x which is truthy (==1) for:
   o           #  Take 2 to the power the integer: 2^x
    ©          #  Store it in variable `®` (without popping)
     ‹         #  Check that it's larger than the (implicit) input: r < 2^x
               #  (1 if truhy; 0 if falsey)
    ®          #  Push variable `®` again: 2^x
     I.£       #  Only leave the last input amount of digits
        2X:    #  Replace all 2s with 1s
           `   #  Push all digits separated to the stack
    P          #  Take the product of all digits on the stack (including the earlier check)
               #  (NOTE: Only 1 is truthy in 05AB1E)

CSharp - 111 chars
int a(int r){int x=1;a:x++;foreach(var c in Math.Pow(2,x)%Math.Pow(10,r)+"")if(c!='1'&&c!='2')goto a;return x;}

Perl 5 -Mbigint -p, 33 bytes
1while($a=2**++$\)!~/[12]{$_}$/}{

Try it online!

Julia 133 122 (51) bytes
Inspired by YOU's answer:
n->(k=1;f=4;g=big(16);i=j=2;m=10^n;while i<=n;while digits!(fill(0,i),j)⊈1:2;j,k=j*g%m,k+f;end;i,g,f=i+1,g^5%m,f*5end;k)

Try it online!
The following is much shorter, but it crashes for r > 8, like some of the other answers:
f(r,x=big(1))=digits!(fill(0,r),x)⊈1:2&&f(r,2x)+1

Try it online!


text:
The last digit in an exponentation
In this task you will be given A (less than 10000 digits long) and B (less than 2^64), and you will need to compute the last digit of (A · A · A · ... · A (B times)).
The inputs A and B are given in a single line separated by a blank; the inputs are terminated by EOF.
Input
34543232321323243242434544533445343432434311112223454323232132324324243454453344534343243431111222345432323213232432424345445334453434324343111122234543232321323243242434544533445343432434311112223454323232132324324243454453344534343243431111222345432323213232432424345445334453434324343111122234543232321323243242434544533445343432434311112223454323232132324324243454453344534343243431111222 22337254775808
38758436543765743875437656358764347568437658743658743454354645645543532487548758475847684756897548758457843758437584758478574857438758436587436587436587643875643856783478743658743658764387564387564378658437658743658743687564387564387564765746576475647564756475465746574675647654765476547534587545689475689748574385743765874585743857843765893748643587438957458754376543265874387564384764367584375874758943267632487564357 54545454123
6777744348435743587643756438765436574587564354375674365645643675 23232
3875843654376574357 54545454

Output
6
3
5
9

Constraints

Don't use any inbuilt function or overloaded operators to compute AB (you don't really need to compute that at all).
Shortest solution wins!

Is it allowed to use the exponentiation operator to compute things other than A**B?

I presume that both A and B are non-negative?

J - 52 characters
wd,.10|(^12+12&|)/"1(".@{:`".;._2@,&'x ');._2(1!:1)3

Passes all tests given, though only if the trailing spaces on the third input are removed (I'm guessing this was unintentional).
Solution will work in j602 in console mode (e.g. in terminal, emacs j-shell, etc.). It will not work in j701 (no wd).
Explanation & Mathiness:
The 'magic number' 12 is the LCM of the lengths of the "last digit" tables found in the other answers. All digits repeat with periods 1,2,3 or 4 so they will also repeat with period 12. Adding twelve to that fixes cases where b mod 12 = 0. My solution computes (Last digit of A)^(12+(B mod 12)), giving a number with the same last digit. (I considered a sneaky broken solution eliminating the three characters '12+' by using e.g. B mod 96 where no examples were likely to collide...)

Python 125 107 Chars
O(1) solution
while 1:a,b=map(int,raw_input().split());d=1;exec"d*=a;"*(b%4);c=a%5and d%5;print b/~b+1or c+[0,5][c%2-a%2]

Nice +1.

GolfScript 21
~]2/{~.(4%)and?10%n}/

This basically calculate A^C mod 10 where C is in the range [1,4] and C mod 4 = B mod 4, except if B is 0, then C is also 0.
This shortcut is possible because A^(B+4) mod 10 = A^B mod 10 for any non-negative integer A and positive integer B.

Ruby, 97 93 72 71 67 61 60
Also handles the case where b == 0.
#!ruby -nl
~/ /
p eval"#$`%10*"*($'>?0?($'.to_i-1)%4+1:0)+?1

Guess it's actually worse to use a lookup table.

It gives 1 as output on giving 2 5 as input and does not even give correct output for sample cases above. http://www.ideone.com/2cOPy

@fR0DDY: It works perfectly on my system, with 1.9.2 too.

J, 79
,._2(4 :'10|x^(+y&(|~))x{10$1 1 4 4 2')/\x:".(]_1&{.`];._2~(' ',LF)e.~])(1!:1)3

Wow that's ugly! Remind me not to learn this language. +1 for putting up with it.

Windows PowerShell, 85
O(1) solution. Taken a hint from Lowjacker's Ruby solution ;-)
$input|%{$a,$b=-split$_
'0000111162481397646455556666179368421919'[4*$a[-1]%48+$b%4]}

Python (119 134 109)
I trust the prohibition against built-in functions doesn't apply to I/O.

import sys
p=lambda b,e:e and p(b*b%10,e/2)*(~e&1or b)%10or 1
for l in sys.stdin:print p(*map(int,l.split()))

Edit: remove use of Python's exponentiation operator.
Edit: Replaced ternary operators with short-circuited boolean operators.

Yes you can/must use I/O functions for taking the inputs but you are not supposed to use '**' for this task.

This would work though but I don't really intend this task for a brute-forced modular exponentiation solution,actually there is an O(1) algorithm and it's very short too :-)

Python 149 Chars
p=[[0],[1],[6,2,4,8],[1,3,9],[6,4],[5],[6],[1,7,9,3],[6,8,4,2],[1,9]]
while 1:a,b=map(int,raw_input().split());print b/~b+1or p[a%10][b%len(p[a%10])]

Vyxal, 4 bytes
t$et

Try it Online!
No one said it had to be efficient, and the rules forbid only calculating \$A^B\$, not \$A[-1]^B\$.
   t # Last digit of...
t    # Last digit of A
  e  # To the power of
 ?   # B

More efficient version

Python 3k 121 Chars
def p(a,b):
  if b<1:return 1
  return p(a*a%10,b//2)*[1,a][b%2]%10
while 1:
  a,b=map(int,input().split())
  print(p(a%10,b))

The (a*a)%10 is not necessary but it speeds it up, so decided to keep it.
Edit: Apparently, the parentheses are not required.
Meanwhile, thinking about the O(1) Solution. :)

Won't the loop error after the EOF?

Javascript ( 117   84  79 60 chars)
Reached 60 chars with the suggested improvements from @JiminP and @NoOneIsHere. Thank you!
d=function(s,n){a=Math.pow(s[s.length-1],n%4==0?1:n%4)+'';return a[a.length-1]}

d=(s,n)=>{return(Math.pow(s.slice(-1),n%4||1)+'').slice(-1)}

To test:
console.log(d('243242434544533445343432434311112223454323232132324324243454453344534343243431111222345432323213232432424345445334453434324343111122234543232321323243242434544533445343432434311112223454323232132324324243454453344534343243431111222345432323213232432424345445334453434324343111122234543232321323243242434544533445343432434311112223454323232132324324243454453344534343243431111222', 22337254775808));
console.log(d('38758436543765743875437656358764347568437658743658743454354645645543532487548758475847684756897548758457843758437584758478574857438758436587436587436587643875643856783478743658743658764387564387564378658437658743658743687564387564387564765746576475647564756475465746574675647654765476547534587545689475689748574385743765874585743857843765893748643587438957458754376543265874387564384764367584375874758943267632487564357', 54545454123));
console.log(d('6777744348435743587643756438765436574587564354375674365645643675', 23232));
console.log(d('3875843654376574357', 54545454));

Results:
2
3
5
9

d=function(s,n){return(Math.pow(s.slice(-1),n%4||1)+'').slice(-1)} :P

I don't use JavaScript much, but couldn't you use d=s,n=>(Math.pow(s.slice(-1),n%4||1)+'').slice(-1) or use => at all?


text:
Code-Golf: Farey sequence (I)
Challenge

In this task you would be given an integer N
  (less than 10^5), output the Farey
  sequence of order N.

The input N is given in a single line,the inputs are terminated by EOF.
Input
4
3
1
2

Output
F4 = {0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1}
F3 = {0/1, 1/3, 1/2, 2/3, 1/1}
F1 = {0/1, 1/1}
F2 = {0/1, 1/2, 1/1}

Constraints

The number of inputs would not exceed 10^6 values
You can use any language of your choice
Shortest solution wins!

This will get loooong.....the output i mean.

Is N=0 permitted?

What's with the »(I)« in the title?

I think you should reconsider the input limitations, the 10^5 order Farey sequence consist of approximately 3 billion numbers, and one million inputs is way too much.

@Joey: Hmm. there's a Farey Sequence (II) now.  Must be first edition! :-)

@mellamokb: Well, that one's a code challenge, though, so no title clash in any case. But yes, that sort of answers my question.

J, 96
('F',],' = {0/1',', 1/1}',~('r';'/')rplc~', ',"1":"0@(3 :'}./:~~.,(%~}:\)i.1x+y')&".);._2(1!:1)3

( /:~~.,(%~}:\)i.>:x:y gives the list; the rest is I/O and formatting (with bad style))
E.g:
4
3
1
2
F4 = {0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1}
F3 = {0/1, 1/3, 1/2, 2/3, 1/1}
F1 = {0/1, 1/1}
F2 = {0/1, 1/2, 1/1}

Edits

(114 → 106)  Clearer appending ,
(106 → 105)  Cap [: to At @
(105 → 101)  Delete superfluous ": conversion
(101 → 99)  Use infix \ for the list
(99 → 96)

I get |value error: rplc. Are you sure you didn't load 'strings' earlier in the session and forget about it?

@Jesse: absolutely. I (almost) never use 'strings'. I just use the default linux-j-7.01 environment.

Ugh... I switched to j602 for wd and now I may need to switch back. :)

Python, 186 Chars
import sys
p=sys.stdout.write
while 1:
 a=0;b=c=x=1;d=y=N=input();p("F%d = {%d/%d, %d/%d"%(d,a,b,c,d))
 while y-1:x=(b+N)/d*c-a;y=(b+N)/d*d-b;p(", %d/%d"%(x,y));a=c;c=x;b=d;d=y
 p("}\n")

+1,but are you sure this will be fast for 10^6 number of inputs?

@Debanjan No. It would be really slow for 10^6 inputs. It is linear in complexity (in terms of the number of terms), though.

Common Lisp, 156
(do((l()()))((not(set'n(read()()))))(dotimes(j n)(dotimes(i(1+ j))(push(/(1+ i
)(1+ j))l)))(format t"~&F~D = {0/1~{, ~A~}/1}"n(sort(delete-duplicates l)'<)))

(newlines not necessary)
Very brutal, but languages with native rationals are an invitation to that.
Ungolfed with comments:
                                        ; at each iteration:
(do ((l()()))                           ; - reset l to nil
    ((not (set 'n (read()()))))         ; - read a term (nil for eof)
                                        ;   assign it to n
                                        ;   stop looping if nil
  (dotimes (j n)                        ; for j in 0..n-1
    (dotimes (i (1+ j))                 ;   for i in 0..j
      (push (/ (1+ i) (1+ j)) l)))      ;     prepend i+1/j+1 to l
  (format t "~&F~D = {0/1~{, ~A~}/1}"   ; on a new line, including 0/1,
                                        ; forcing the format for 1
          n                             ; print sequence index, and
          (sort                         ; sorted sequence of
           (delete-duplicates l)        ;   unique fractions
           '<)))                        ; (in ascending order)

Ruby, 110 108 102 97 94 92 91 89
#!ruby -lp
$_="F#$_ = {#{a=[];1.upto(eval$_){|d|a|=(0..d).map{|n|n.quo d}};a.sort*', '}}"

I think you should output "0/1" and "1/1" instead of "0" and "1" respectively. Also, does this only work for ruby 1.9?

@Eelvex: It does output 0/1 and 1/1 on my system. And yes, it requires 1.9 (because of the character literals).

J, 156 135 117 112
d=:3 :0
wd;'F';(":y);' = {';(}.,(', ';2|.'/';|.)"1(<@":)"0(2)x:/:~~.,(-.@>*%)"0/~i.x:>:y),<'}'
)
d@".;._2(1!:1)3

j602 or similar (wd). Input on stdin, output on stdout.
Still puzzling over how to golf the output code, which is 100 characters or so.
Edit: (156->135) Tacit->explicit for long monadic verb chains, less braindead list generation
Edit: (135->117) Found raze. Took me long enough. Switched string handling around.
Edit: (117->112) Slightly less braindead way to exclude fractions above 1. Unnecessary open.

Maybe you can omit one of your two x:s?

@Eelvex: The left one is 2&x:, e.g. split a rational number into numerator and denominator.

oic. Pity ... :(

Golfscript (101)
~:c[,{){.}c(*}%.c/zip{+}*]zip{~{.@\%.}do;1=},{~<},{~\10c?*\/}${'/'*}%', '*'F'c`+' = {0/1, '+\', 1/1}'

Haskell, 145 bytes
f(!)(%)n|p<-product[1..n]='F':n!" = {"++unwords[i%g!"/"++p%g![",}"!!(i%p)]|i<-[0..p],g<-[gcd i p],p<=n*g]
m@main=readLn>>=putStrLn.f shows div>>m

Try it online!
This reduces all of \$\left\{\frac{0}{n!}, \frac{1}{n!}, \dots, \frac{n!}{n!}\right\}\$ and selects the ones with denominator \$\leq n\$.
(The byte count went up a little again because I noticed the problem asks to handle multiple lines of input.)
The other Haskell answer is missing some imports and is missing 1/1 in the output. It also doesn't take multiple lines of input. When fixed, it comes out to 188 bytes:
import GHC.Real
import Data.List
f n="F"++show n++" = {"++(intercalate", ".("0/1":).map(\(i:%d)->show i++"/"++show d).sort.nub$[i%d|d<-[1..n],i<-[1..d]])++"}"
m@main=readLn>>=putStrLn.f>>m

Haskell, 148
f n="F"++show n++" = {"++(intercalate", ".("0/1":).map(\(i:%d)->show i++"/"++show d).sort.nub$[i%d|d<-[1..n],i<-[1..d-1]])++"}"
main=interact$f.read

Husk, 55 bytes
mλ:'F+s¹+" = "σ"1]""1/1}"σ"[0""{0/1"sOutfεmF/π2ŀ→)fImi¶

Try it online!
It was interesting messing with strings in Husk.
This gives the exact required output for the given test case.
There's a strange husk-ism in the mi¶ function that gives intermediate 0's in the output. Hence, those are filtered out. Here's an explanation from Zgarb.
Explanation
mλ:'F+s¹+" = "σ"1]""1/1}"σ"[0""{0/1"sOutfεmF/π2ŀ→)fImi¶
                                                      ¶ split input on newlines
                                                    mi  map to integers
                                                  fI    filter out zeroes
mλ                                               )      map each number through this function:
                                               ŀ→       range (0..n)
                                             π2         all possible pairs
                                          mF/           map each to it's fraction
                                        fε              keep elements ≤ 1
                                       t                remove first value (Any)
                                     Ou                 uniquify, sort ascending
                                    s                   convert to string
                         σ"[0""{0/1"                    change 0 → 0/1
              σ"1]""1/1}"                               change 1 → 1/1
        +" = "                                          add an equal sign
  :'F+s¹                                                prepend "F{N}"

Jelly, 44 bytes
ƓµŻœċ2g/’$Ðḟ÷/Þj€”/j⁾, ,⁸Ø<,y“F> = {<}”Ṅ
Ç1¿

Try it online!
Could probably be improved if someone told me how to read and write multiline input properly in Jelly. I couldn't find any documentation on it, so I just have a while(true) loop that errors out when it reaches EOF.

Python 3, 89 bytes
lambda n:[*zip(*sorted({j/i:(j,i)for i in range(n,0,-1)for j in range(i+1)}.items()))][1]

Try it online!
Basically generating all possible fractions and then using a dictionary comprehension to filter out the duplicates.

Python 3, 142 bytes
while 1:n=input();print('F%s = {'%n+', '.join([*zip(*sorted({j/i:f'{j}/{i}'for i in range(int(n),0,-1)for j in range(i+1)}.items()))][1])+'}')

Try it online!
Abiding by all of the I/O requirements

CJam, 73 bytes
'Fqi:T" = {"[[T1]Y,{_'\*',+\W%@_@_2$+2%Ta.+:/@f*\.-_1=T)<@W%\}g'\*\;]S*'}

Try it online!
Uses an algorithm to generate the terms in traditional order. A lot of maps and vector functions were used here. If anyone wants a write-up then I'll make one, unless I can figure out a better algorithm.

Mathematica 13 78 bytes
Column[Row@{"F",#," = ",FareySequence[ToExpression@#]}&/@StringSplit[#,"\n"]]&

Example
Column[Row@{#," = ",FareySequence[ToExpression@#]}&/@StringSplit[#,"\n"]]&["5\n4\n3"]

It's nice that you have a builtin, but the spec asks for a specific formatting and handling multiple queries.

Kindly explain what you mean by "specific formatting and handling multiple queries".

Per the specification, you have to find Farey sequences for multiple integers separated by newlines and output them in the format "F3 = {0/1, 1/3, 1/2, 2/3, 1/1}". Your code takes only one integer and has a different output format.

@xigoi, I think I've now addressed your comments. Thanks.

05AB1E, 40 bytes
|εÝ2.Æ2Å1ª.¡`/}€нΣ`/}'/ý„, ýy"Fÿ = {ÿ}",

Try it online.
Explanation:
|                     # Get all input-lines as a list
 ε                    # Map over each input-integer:
  Ý                   #  Pop and push a list in the range [0,n]
   2.Æ                #  Get all 2-element combinations of this list
      2Å1ª            #  Append pair [1,1]
  .¡                  #  Group the pairs by:
    `                 #   Pop and push both values separated to the stack
     /                #   Divide them
   }€                 #  After the group-by: map over each group
     н                #   Only leave the first pair of each group
      Σ  }            #  Then sort the pairs by:
       `/             #   Similar as above: dump and divide
  '/ý                '#  Then join each inner pair with "/"-delimiter
     „, ý             #  Join these strings with ", "-delimiter
         y            #  Push the current map-integer
          "Fÿ = {ÿ}"  #  Push this string, where the `ÿ` are automatically filled with
                      #  the integer and formatted list
                    , #  Pop and output it with trailing newline

Japt -R, 18 38 bytes
Stupid old challenges and their stupid & unnecessarily strict I/O requirements costing me 20 bytes!
N£"F{X} = \{{Xõ c_ô+'/+ZÃü!xO mÎqSi,}}

Try it
N£"F{X} = \{{Xõ c_ô+'/+ZÃü!xO mÎqSi,}}
N                                          :Array of all inputs
 £                                         :Map each X
  "F   = \{                          }     :  Build a string
    {X}                                    :  Interpolate X
           {                               :  Interpolate
            Xõ                             :    Range [1,X]
                c                          :    Flat map by
                 _                         :    Passing each Z through the following function
                  ô                        :      Range [0,Z]
                   +'/+Z                   :      Append "/" followed by Z to each
                        Ã                  :    End map
                         ü                 :    Group & sort by
                          !xO              :      Evaluating each as JavaScript
                              m            :    Map
                               Î           :      First element
                                q          :    Join with
                                 S         :      Space
                                  i,       :      Prepend comma
                                    }      :  End interpolation
                                           :Implicit output joined with new lines

"OK, what am I missing?" There are multiple inputs, separated by newlines from STDIN. And the STDOUT output format you see in the challenge description is mandatory, with the F# = {comma_and_space_separated_results}.

Thanks, @KevinCruijssen. Stupid old challenges and their stupid & unnecessarily strict I/O requirements!

Ikr.. :/ Ah well, you're still the shortest. ;p Group-and-sort by is way too long in 05AB1E (2 separated builtins)..


text:
Palindromic palindrome checker
Write a program to test if a string is palindromic, with the added condition that the program be palindromic itself.

If the language has till-the-end-of-the-line comments this is trivial so I guess those should be disallowed.

@Joey I'd happily discourage use of such comments, but disallowing them after posing the question is harsh on those who have already answered. @Ventero's answer (the only one not using them) is way ahead on vote count, so everyone seems to agree.

Well, to weed out such problems earlier (this also occurred in a similar task on SO) you could use the sandbox or the Puzzle lab ;-)

How about imposing that the program should be a palindromic quine itself evil grin ;-)

If someone find a way, he instantly wins because of the characters saved.

I know this is an old question, but I think it needs an arbitrary winning criterion, such as popularity contest or code-golf. The question specifies none.

Ruby
z=gets;puts *z.reverse==z&&1||0||1&&z==esrever.z* stup;steg=z

Prints 1 if the input is a palindrome, 0 if it isn't. Input without linebreak.
Doesn't use any comments, instead it uses 2 tricks:

Short-circuiting: 0 is true-ish in Ruby (only nil and false evaluate to false), so 1&&z==esrever.z* stup isn't evaluated and thus can't raise a runtime exception
The splat/multiplication operator (*): To avoid a syntax error in z=esrever.z stup, we force the parser to parse this as z=esrever.z()*stup by adding a *. On the other side, the * is parsed as a splat operator, which in a function call splits an array in a series of parameters. If there's only one element instead of an array, it basically does nothing, so puts *foo is equivalent to puts foo.

Obvious solution using comments (prints true/false):
puts gets.reverse==$_#_$==esrever.steg stup

Can you explain how this works. I don't know ruby.

@mellamokb: I added a short explanation. Let me know if it's still not clear.

Python without comment
"a\";w=]1-::[w trinp;)(tupni_war=w;";w=raw_input();print w[::-1]==w;"\a"

I'm surprised that no one found that trick yet, it should work in most languages!

Very Clever, I like the escaping quote.

Nice solution, you could even drop the print statement and if you allow the input to specified enclosed in quotes raw_input() can be shortened to input(). Missing an extra '=' at the start.

removed trailing output after True or False: "a\"#;w==]1-::[w;)(tupni_war=w;";w=raw_input();w[::-1]==w;#"\a"

@Willem Replace ;# with != and you've got a comment-free solution again, assuming printable input.

Perl
perl -nle "$s=$_ eq+reverse;print$s;s$tnirp;esrever+qe _$=s$"
no comment tricks, just cleverly abusing the substitution operator (hey, perl variables start with a $ too, so what?)

Python 2.7
s=raw_input();print'YNEOS'[s!=s[::-1]::2]#]2::]1-::[s=!s['SOENY'tnirp;)(tupni_war=s

C
#include <stdio.h>                   //
#include <string.h>                  //
int main() {                         //
  char str[1024];                    //
  fgets(str, sizeof(str), stdin);    //
  int i = 0, j = strlen(str) - 2;    //
  for (; i < j; i++, j--)            //
    if (str[i] != str[j]) {          //
      printf("no\n");                //
      return 0;                      //
    }                                //
  printf("yes\n");                   //
}                                    //
//                                    }
//                   ;)"n\sey"(ftnirp
//                                }
//                      ;0 nruter
//                ;)"n\on"(ftnirp
//          { )]j[rts =! ]i[rts( fi
//            )--j ,++i ;j < i ;( rof
//    ;2 - )rts(nelrts = j ,0 = i tni
//    ;)nidts ,)rts(foezis ,rts(stegf
//                    ;]4201[rts rahc
//                         { )(niam tni
//                  >h.gnirts< edulcni#
//                   >h.oidts< edulcni#

Running example:
$ gcc -std=c99 c.c && ./a.out
blahalb
yes

won't win for brevity, but I'm impressed

lol, clever-lvl 11/10.

Golfscript
.-1%=#=%1-.

just with comment trick
input without \n at the end
perform matching char by char (even for punctuation)
returns 1 for success, 0 for failure

PHP
echo strrev($z)==$z;#;z$==)z$(verrts ohce

Facts:

$z string, the input string to check
$t boolean, TRUE if the input string $z is palindrome, FALSE otherwise
Using comments to help me make the code palindrome.
Outputs $t
Source itself is a palindrome

The reason why it will not be possible to implement palindromic palindrome checker in PHP it's because PHP variables are named starting with a $. You cannot end an identifier name with $ in PHP.

PHP
<?php eval/*/*/(';{$i=fgets(STDIN,2e9);};{$a="strrev";}{var_dump("{$i}"=="{$a($i)}");}/*}{*\{;("{(tupni$)a$}"=="{putni$}")ohce}{;"verrts"==a$};{;(9e2,NIDTS)stegf=i$);');/*\*\eval php?>

Uses some odd tricks to avoid the $ issue, technically isnt a palindrome as I had to sneak a ; in at the end.
 <?php $i = fgets(STDIN,2e9); echo $i == strrev($i);/*\;(i$)verrts == i$ ohce ;(9e2, NIDTS)stegf = $i php?>

This is a working one that uses PHP's /* */ comments and the fact that you don't need the end for them.

In the end first code, eval should be lave.

Fuzzy Octo Guacamole, 17 bytes
^Cz.=i_;@;_i=.zC^

Not exactly sure how the win is defined, but I put the byte count up top.
^ gets the input and pushes it to the first stack.
C copies the first stack to the second.
z reverse the top of the stack, so "as" becomes "sa".
. shifts the active stack, so the active stack has the input, and the inactive one has the reversed input.
= checks for equality, returning 0 for equality.
i inverts the ToS, so 0 becomes 1, and anything else pretty much becomes False.
_ pops and sets the temp variable which the ; then prints.
@ ends the program manually, so it doesn't hit the reversed part.  This makes the palindrome.

CoffeeScript
I actually struggled with the reverse spellings of 'split', 'reverse' and 'join' :\
p=(s)->s.split('').reverse().join('')==s#s==)''(nioj.)(esrever.)''(tilps.s>-)s(=p

Groovy
print args[0]==args[0].reverse()?1:0//0:1?)(esrever.]0[sgra==]0[sgra tnirp

You have used comments over here!

Python 3, 55 bytes
Uses a comment, but is shorter than the other Python one that uses comments.
s=input();print(s==s[::-1])#)]1-::[s==s(tnirp;)(tupni=s

Javascript
function a(b){return b==b.split('').reverse().join('')}//})''(nioj.)(esrever.)''(tilps.b==b nruter{)b(a noitcnuf

Hard to do it without comments...