text:
Compact coding of integer into bitstring
I want to compactly code positive integers x into bits, in a manner allowing decoding back into the original integers for a stateless decoder knowing the maximum value m of each x; it shall be possible to uniquely decode the concatenation of encodings, as is the case in Huffman coding.
[The above introduction motivates the rest, but is not part of the formal definition]
Notation: for any non-negative integer i, let n(i) be the number of bits necessary to represent i in binary; that is the smallest non-negative integer k such that i>>k == 0
  i :   0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  ..
n(i):   0   1   2   2   3   3   3   3   4   4   4   4   4   4   4   4   5   5   5   ..

I want a function F(x,m) defined for 0<x and x<=m, with output a string of '0' or '1', having these properties:

F(x,m) has length less than 2*n(x) or 2*n(m)-1, whichever is smaller.
If x<y then:

F(x,m) is no longer than F(y,m);
F(x,m) and F(y,m) differ at some position over the length of F(x,m);
there's a 0 in F(x,m) at the first such position.

When for a certain m properties 1 and 2 do not uniquely define F(x,m) for all positive x at most m, we reject any encoding giving a longer F(x,m) than some otherwise acceptable encoding, for the smallest x for which the length do not match.

Note: In the above, implicitly, 0<x, 0<y, 0<m, x<=m, and y<=m, so that F(x,m) and F(y,m) are defined.
It is asked the shortest program that, given any x and m meeting the above constraints and up to 9 decimal digits, outputs an F(x,m) consistent with the above rules. The following C framework (or its equivalent in other languages) is not counted:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define C(c) putchar((c)?'1':'0') // output '0' or '1'
#define S(s) fputs((s),stdout)    // output a string
typedef unsigned long t;          // at least 32 bits
void F(t x,t m);                  // prototype for F
int main(int argc,char *argv[]){
 if(argc==3)F((t)atol(argv[1]),(t)atol(argv[2]));
 return 0;}
void F(t x,t m) {   // counting starts on next line
}                   // counting ends before this line

Comment: Property 1 aggressively bounds the encoded length; property 2 formalizes that unambiguous decoding is possible, and canonicalizes the encoding; I assert (without proof) this is enough to uniquely define the output of F when m+1 is a power of two, and that property 3 is enough to uniquely define F for other m.
Here is a partial table (handmade; the first version posted was riddled with errors, sorry):
  x     :   1       2       3       4       5       6       7       8       9       10      11      12      13      14      15
F(x,1)  : empty
F(x,2)  :   0       1
F(x,3)  :   0       10      11
F(x,4)  :   0       10      110     111
F(x,5)  :   0       10      110     1110    1111
F(x,6)  :   0       100     101     110     1110    1111
F(x,7)  :   0       100     101     1100    1101    1110    1111
F(x,8)  :   0       100     101     110     11100   11101   11110   11111

F(x,15) :   0       100     101     11000   11001   11010   11011   111000  111001  111010  111011  111100  111101  111110  111111

"Compact coding?" How is this more compact than the canonical base-2 representation of the integer? :)

@m.buettner: Problem with the canonical representation in base 2 is that 3 then 7, 7 then 3, 1 then 15, and a number of other things, all encode as 11111, making decoding impossble. With the proposed coding, the concatenation of several outputs can be uniquely decoded (including with the maximum m changing dynamically). I tried to clarify that.

Ah, I see. That's neat. +1

I disagree with your table. For F(x,5) you have 0,100,101,110,111. But, the encoding 0,10,110,1110,1111 satisfies (1) and (2), and because 10 is shorter than 100, it causes your encoding for F(x,5) to be rejected.

@nneonneo: you clearly are right! I chose to keep the statement, which seems to make the table falsifiable. I reduced the table and hope what remains is now correct. Thanks!

@fgrieu: I think the table is still wrong. For F(x,6) and F(x,7) there's a better solution: 0,10,110,11100,11101,11110,11111. Then, for F(x,8) your own table violates property (1) because F(5,8) is 6 digits, which is not less than 2*n(5)=6.

@nneonneo: For F(x,7) your proposal 0,10,110,11100,11101,11110,11111 is not acceptable, because property 1 states the length of all entries should be less than 2*n(m)-1, that is less than 5. Yes my new F(x,8) was wrong, unfixed it!

Yeah, you're right on that. I forgot it was 2*n(m)-1.

Oh but for F(x,8) your table is still wrong. 0,100,101,110,11100,11101,11110,11111 is better for F(4,8) (110 vs 1100).

@nneonneo: Yes; further, F(x,8) of 0, 100, 101, 110, 1110, 11110, 111110, 111111 is even better.

Nope. That's illegal because F(7,8) must be less than 6 digits.

Python 3, 163 bytes
n=int.bit_length
R=range
def F(x,m,c=0):
 for i in R(x):L=2*n(m)-2;D=1<<L;r=n(D-c-sum(D>>min(2*n(x+1)-1,L)for x in R(i+1,m)))-1;v=c;c+=1<<r
 return bin(v)[2:L+2-r]

Ignore the c=0 parameter, that's a golf trick.
This greedily chooses the shortest possible representation for each number, subject to the condition that the remaining numbers are still representable. Therefore, by construction, it exactly satisfies the desired properties. It is actually not that hard to modify this code to support a different set of coding rules, as a result.
For example, here are the outputs up to m=15:
m\x |   1       2       3       4       5       6       7       8       9       10      11      12      13      14      15
----+----------------------------------------------------------------------------------------------------------------------------
1   |
2   |   0       1
3   |   0       10      11
4   |   0       10      110     111
5   |   0       10      110     1110    1111
6   |   0       100     101     110     1110    1111
7   |   0       100     101     1100    1101    1110    1111
8   |   0       100     101     110     11100   11101   11110   11111
9   |   0       100     101     110     11100   11101   11110   111110  111111
10  |   0       100     101     1100    1101    11100   11101   11110   111110  111111
11  |   0       100     101     1100    1101    11100   11101   111100  111101  111110  111111
12  |   0       100     101     1100    11010   11011   11100   11101   111100  111101  111110  111111
13  |   0       100     101     1100    11010   11011   11100   111010  111011  111100  111101  111110  111111
14  |   0       100     101     11000   11001   11010   11011   11100   111010  111011  111100  111101  111110  111111
15  |   0       100     101     11000   11001   11010   11011   111000  111001  111010  111011  111100  111101  111110  111111

Python, 171
def F(x,m):
 a=0;b=[9]
 while len(b)<m:
    if 4**len(bin(len(b)))*2>64*a<4**len(bin(m)):
     if(a&a+1)**a:b+=[a];a+=1
     else:a*=2
    else:a=b.pop()*2
 return bin((b+[a])[x])[2:]

Note that lines that appear to begin with 4 spaces actually begin with a tab.
Testing, with bitpwner's test script:
         1        2        3        4        5        6        7        8        9        10       11       12       13       14       15
F(x,1)   0
F(x,2)   0        1
F(x,3)   0        10       11
F(x,4)   0        10       110      111
F(x,5)   0        10       110      1110     1111
F(x,6)   0        100      101      110      1110     1111
F(x,7)   0        100      101      1100     1101     1110     1111
F(x,8)   0        100      101      110      11100    11101    11110    11111
F(x,9)   0        100      101      110      11100    11101    11110    111110   111111
F(x,10)  0        100      101      1100     1101     11100    11101    11110    111110   111111
F(x,11)  0        100      101      1100     1101     11100    11101    111100   111101   111110   111111
F(x,12)  0        100      101      1100     11010    11011    11100    11101    111100   111101   111110   111111
F(x,13)  0        100      101      1100     11010    11011    11100    111010   111011   111100   111101   111110   111111
F(x,14)  0        100      101      11000    11001    11010    11011    11100    111010   111011   111100   111101   111110   111111
F(x,15)  0        100      101      11000    11001    11010    11011    111000   111001   111010   111011   111100   111101   111110   111111

Explanation:
This is all based on the observation that between two consecutive elements of the code, F(x,m) and F(x+1,m), we always add one to the binary number, then multiply by two some number of times. If these steps are followed, then it is a valid code. The rest simply tests to make sure it is short enough.
Golfs:
175 -> 171: changed 2**(2*... to 4**

Nit: F(1,1) should be the empty string.

Python - 370
Creates a huffman tree, balances it to fit the rules, then does a walk through the tree to get the final values.
def w(n,m,c,p=""):
    try:[w(n[y],m,c,p+`y`)for y in 1,0]
    except:c[n[0]]=p
d=lambda x:len(x)>1and 1+d(x[1])
v=lambda x,y:v(x[1],y-1)if y else x
def F(x,m):
    r=[m];i=j=0
    for y in range(1,m):r=[[m-y],r]
    while d(r)>len(bin(m))*2-6-(m==8):g=v(r,i);g[1],g[1][0]=g[1][1],[g[1][0],g[1][1][0]];i,j=[[i+1+(d(g)%2<1&(1<i<5)&(m%7<1)),j],[j+1]*2][d(g)<5]
    c={};w(r,m,c);return c[x]

For a more succinct solution that is based on the emergent pattern, look at isaacg's answer.
It's a good example of how a completely different approach can solve the problem.
Test:
chars = 8
maxM = 15
print " "*chars,
for m in range(1,maxM+1):
    p = `m`
    print p+" "*(chars-len(p)),
print
for m in range(1,maxM+1):
    p = "F(x,"+`m`+")"
    print p+" "*(chars-len(p)),
    for x in range(1,maxM+1):
        try:
            q = `F(x,m)`[1:-1]
            print q+" "*(chars-len(q)),
        except:
            print
            break

Results:
         1        2        3        4        5        6        7        8        9        10       11       12       13       14       15
F(x,1)
F(x,2)   0        1
F(x,3)   0        10       11
F(x,4)   0        10       110      111
F(x,5)   0        10       110      1110     1111
F(x,6)   0        100      101      110      1110     1111
F(x,7)   0        100      101      1100     1101     1110     1111
F(x,8)   0        100      101      1100     1101     1110     11110    11111
F(x,9)   0        100      101      1100     1101     1110     11110    111110   111111
F(x,10)  0        100      101      1100     1101     11100    11101    11110    111110   111111
F(x,11)  0        100      101      1100     1101     11100    11101    111100   111101   111110   111111
F(x,12)  0        100      101      11000    11001    11010    11011    11100    11101    11110    111110   111111
F(x,13)  0        100      101      11000    11001    11010    11011    11100    11101    111100   111101   111110   111111
F(x,14)  0        100      101      11000    11001    11010    11011    11100    111010   111011   111100   111101   111110   111111
F(x,15)  0        100      101      11000    11001    11010    11011    111000   111001   111010   111011   111100   111101   111110   111111

As pointed by nneonneo, F(7,8) of 111110 is wrong, for that has length 6, and "less than 2*n(x)" implies less than 6.

source: Stack Exchange

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

sort: votes


text:
Write a domino effect
Using the fewest Unicode characters, write a function that accepts three parameters:

Total number of dominoes
nth affected domino
Topple direction of the affected domino (0 or L for left, 1 or R for right)

Once a domino is toppled, it must also topple the remaining dominoes in the same direction.
You should output the dominoes with | representing a standing domino and \ and / representing a domino toppled to the left and right respectively.
Examples
10, 5, 1 should return ||||//////
6, 3, 0 should return \\\|||

Should the third parameter be a string or will a bool/int do like 0:left , 1:right?

Your example suggests that if there are 10 dominoes, and 5 are knocked right, we should display six of the ten dominoes knocked over.

@algorithmshark I think we should show the result if the fifth domino is knocked right.

@rybo111 Can you allow the third parameter to be an int as that can make comparison operations shorter. Simply if(third_parameter) instead of if(third_paramter=='l')

Can we choose the order of the parameters?

Alright, use whichever parameter order and the direction can be an int or a string

And my example is correct: if you knock over the 5th domino, to the right, it also knocks over the remaining dominos to the right.

Shouldn't right make //////|||| ? Your example doesnt start at the beginning...

@Martijn The example parameters are 10, 5, 'r' - this translates to: There are 10 dominos. Knock the 5th one to the right. This means the 5th domino becomes knocked over (/) as does everything after it. However, if you change the r to an l, the output would be \\\\\||||| because when you knock a domino left it would knock over everything before it instead.

IMO a bit weird principle for dominos. I Interpreted it as 10 dominos, 5 have allready fallen in the direction R. Guess I'll have to update my code

@Martijn Well, the principle of the domino effect is that one change causes others to change. I'd rather specify one change than specify all the changes

Mine was assuming the items where still falling, more like s snapshot. But updated my code

@Martijn if it's any consolation, I interpreted as you did as first as well ^.^

Ruby, 38 (46) characters
e=->n,k,r{k-=r;'\|'[r]*k+'|/'[r]*n-=k}

This function takes the direction as an integer (1 for right, 0 for left). A function that takes a string is 8 characters longer:
d=->n,k,r{n-=k;r<?r??\\*k+?|*n :?|*~-k+?/*-~n}

Usage examples:
puts e[10, 5, 1] # or d[10, 5, 'r']
||||//////
puts e[10, 5, 0] # or d[10, 5, 'l']
\\\\\|||||

why are there only 5 dominoes knocked left in the second example?

@ClydeLobo Because you start at position 5 and knock the domino to the left, which in turn knocks over the 4 dominoes to its left, for a total of 5. In the first example, starting at position 5 knocks over 6 dominoes: The one at position 5 plus the 5 to its right.

J - 32 26 char
J can't handle more than two arguments without using a list, and it can't handle non-homogenous lists without boxing. So having the input as a list of three integers is ideal. The parameter order is the reverse of the standard one: 0 for left or 1 for right, then position, then total number of dominoes.
The reason for this is because J will end up going through them right-to-left.
{`(('|/\'{~-@>:,:<:)1+i.)/

Here's what's going on. F`G/ applied to a list x,y,z will evaluate x F (y G z). y G z constructs both possible ways the dominoes could have toppled, and then  F uses x to select which of the two to use.
Below is a back-and-forth with the J REPL that explains how the function is built together: indented lines are input to the REPL, and responses are flush with the left margin. Recall that J evaluates strictly right to left unless there are parens:
   1 ] 3 (]) 10            NB. ] ignores the left argument and returns the right
10
   1 ] 3 (] 1+i.) 10       NB. hook: x (F G) y  is  x F (G y)
1 2 3 4 5 6 7 8 9 10
   1 ] 3 (>: 1+i.) 10      NB. "greater than or equal to" bitmask
1 1 1 0 0 0 0 0 0 0
   1 ] 3 (-@>: 1+i.) 10    NB. negate
_1 _1 _1 0 0 0 0 0 0 0
   1 ] 3 (<: 1+i.) 10      NB. "less than or equal to"
0 0 1 1 1 1 1 1 1 1
   1 ] 3 ((-@>:,:<:)1+i.) 10          NB. laminate together
_1 _1 _1 0 0 0 0 0 0 0
 0  0  1 1 1 1 1 1 1 1
   1 ] 3 (('|/\'{~-@>:,:<:)1+i.) 10   NB. turn into characters
\\\|||||||
||////////
   1 { 3 (('|/\'{~-@>:,:<:)1+i.) 10   NB. select left or right version
||////////
   {`(('|/\'{~-@>:,:<:)1+i.)/ 1 3 10  NB. refactor
||////////
   {`(('|/\'{~-@>:,:<:)1+i.)/ 0 3 10
\\\|||||||

At the expense of a few characters, we can make the order the standard order: just append @|. to the end of the function:
   |. 10 3 1
1 3 10
   {`(('|/\'{~-@>:,:<:)1+i.)/@|. 10 3 1
||////////

Adapting this to work with a string argument for direction would be much more costly, however.

I know it's been a while since you wrote this answer, but the way it is structured is very cool. I really like how you made use of gerunds and / and also the way you build two outputs and select the desired one. I guess I feel like this lacks the recognition it deserves.

What @cole said, I was awed.

Haskell, 70
f R i l=(i-1)#'|'++(l-i+1)#'/'
f L i l=i#'\\'++(l-i)#'|'
(#)=replicate

assuming there is a type Direction, which has constructors R and L.

PowerShell, 66
filter d($n,$k,$d){"$('\|'[$d])"*($k-$d)+"$('|/'[$d])"*($n-$k+$d)}

Probably the same idea every one else had.

Takes either 0 or 1 as the direction parameter (for left and right, respectively)

Golfscript (44 53)
My first ever Golfscript program. Took me way longer than it should have and can probably be done in a smarter, more concise way (I'm sure someone will prove that :) ):
:d;:j;:^,{:x j<d&'\\'{x^j)->d!&'/''|'if}if}%

A sample input is 10 5 0.
Ungolfed:
:d;:j;:^      # save input in variables and discard from stack, except total length ^
,             # create an array of numbers of length ^
{             # start block for map call
  :x          # save current element (= index) in variable
  j<          # check whether we are left of the first knocked over domino
  d           # check whether the direction is to the left
  &           # AND both results
  '\\'        # if true, push a backslash (escaped)
  {           # if false, start a new block
    x^j)->    # check whether we are on the right of the knocked over domino
    d!        # check whether the direction is to the right
    &         # AND both results
    '/'       # if true, push a slash
    '|'       # if false, push a non-knocked over domino
    if
  }
  if
}%            # close block and call map

Proof done ;-) although I am not happy with my solution yet.

Some tips: you may choose d to be 0/1 instead of 'l'/'r' which gives you some shorter code. Otherwise, if you store d'l'= in a variable oyu may use it instead of the second comparison with d. In the term x i j you can save both whitespaces if you use a non-alphanumeric variable name instead of i.

@Howard Thanks for the tips! I chose 'l'/'r' because at the time I didn't see yet that we are free to use integers. The non-alphanumeric trick is slick, thanks! Maybe I'll update the answer later.

JS (ES6) - 79 74 72 65 62
thanks to @nderscore!
The 3rd param is a boolean (0: left / 1: right)
d=(a,b,c)=>"\\|"[a-=--b,c].repeat(c?b:a)+"|/"[c].repeat(c?a:b)

// Test
d(10,3,1); // => "||////////"
d(10,3,0); // => "\\\\\\\\||"

this entry could be a reference card for ECMAScript 6 :D

@bebe haha, and it's not even its final form. ES6 can be very dirty.

65: d=(a,b,c)=>"\\"[r="repeat"](!c&&a-b+1)+"|"[r](--b)+"/"[r](c&&a-b)

great! I also found this crazy thing but it's longer (67):  d=(a,b,c,d=a-b+1)=>"\|"[c].repeat(c?b-1:d)+"|/"[c].repeat(c?d:b-1)

I don't think repeat aliasing is worth. [r='repeat'][r] 15 chars. .repeat.repeat 14 chars

@edc65 but .repeat is used three times in the first function. That's why I made the alias

62: d=(a,b,c)=>"\\|"[a-=--b,c].repeat(c?b:a)+"|/"[c].repeat(c?a:b)

@nderscore hey. you beat me once again. Stop that. lol :) thanks, it's awesome.

Python - 45 52
This requires 1 for right and 0 for left.
x=lambda n,k,d:'\\|'[d]*(k-d)+"|/"[d]*(n-k+d)

Here's a version that takes r and l correctly, at 58:
def x(n,k,d):d=d=='r';return'\\|'[d]*(k-d)+"|/"[d]*(n-k+d)

Some usage examples...
>>> print(x(10,3,0))
\\\|||||||
>>> print(x(10,3,1))
||////////
>>> print(x(10,5,1))
||||//////
>>> print(x(10,5,0))
\\\\\|||||
>>> print(x(10,3,0))
\\\|||||||

GolfScript, 28 23 characters
'\\'@*2$'|/'*$-1%1>+@/=

Arguments on top of stack, try online:
> 10 5 1
||||//////

> 10 5 0
\\\\\|||||

Amazing. Love to learn from all these golfscript solutions :)

Python2/3 - 54
That last added on rule was quite nice (the 0/1 instead of 'l'/'r'). Made mine actually smaller than the existing python solution. 0 is left, 1 is right
def f(a,b,c):d,e='\|/'[c:2+c];h=b-c;return d*h+e*(a-h)

# Usage:
print(f(10,5,1)) # => ||||//////
print(f(10,5,0)) # => \\\\\|||||

Haskell, 42 bytes
(n%k)b=["\\|/"!!(b-div(k-b-c)n)|c<-[1..n]]

Try it online!
Takes input like (%) n k b for n dominos, k'th domino toppled, direction b.
Finds the character at each position c ranging from 1 to n by using an arithmetic expression to compute the character index 0, 1, or 2.
Test cases taken from here.

Haskell, 44 bytes
(n%k)b=take n$drop(n+n*b+b-k)$"\\|/"<*[1..n]

Try it online!
An interesting strategy that turned out a bit longer. Generates the string "\\|/"<*[1..n] with n consecutive copies of each symbol, then takes a slice of n contiguous characters with start position determined arithmetically.

Python 2.7, 68 65 61 59 58 chars
Use d=1 for left and d=0 for right

f=lambda a,p,d:['|'*(p-1)+'/'*(a-p+1),'\\'*p+'|'*(a-p)][d]

Note: Thanks to @TheRare for further golfing it.

Why not d and'\\'...or'/'...?

You could also do ('\\'...,'/'...)[d]

@TheRare I would need two of those lists.

I don't think so. f=lambda a,p,d:('|'*(p-1)+'/'*(a-p+1),'\\'*p+'|'*(a-p))[d]

@TheRare  Also, I don't think your code works when falling left. Could you give a test case to prove?

Perl, 67 65 Characters
sub l{($t,$p,$d)=@_;$p-=$d;($d?'|':'\\')x$p.($d?'/':'|')x($t-$p)}

Assign the first three params (total, position, direction as an integer [0 left, 1 right]). Extras go into the ether.
Subtract 1 from the position if we're headed right so the domino in position X is flipped, too.

replace $p--if$d with $p-=$d to lose two characters :)

JavaScript (ES6) 61 63
Edit It was buggy - shame on me.
Not so different from @xem, but found it myself and it's shorter. Parameter d is 0/1 for left/right
F=(a,p,d,u='|'.repeat(--p),v='\\/'[d].repeat(a-p))=>d?u+v:v+u

Test In Firefox console
for(i=1;i<11;i+=3) console.log('L'+i+' '+F(10,i,0) + ' R'+i+' '+ F(10,i,1))

Output
L1 \\\\\\\\\\ R1 //////////
L4 \\\\\\\||| R4 |||///////
L7 \\\\|||||| R7 ||||||////
L10 \||||||||| R10 |||||||||/

Should it be --p?

@nderscore yes it should, got parameters wrong, silly me.

Javascript, 46 characters
Seems like cheating to do 0=l and 1=r but there is is.  Shrunk it with a little recursion.
f=(a,p,d)=>a?'\\|/'[(p-d<1)+d]+f(a-1,p-1,d):''

edit: missed an obvious character

Haskell, 57 bytes
4 bytes saved thanks to this tip
f 0 b _=[]
f a b c=last("|/":["\\|"|b>c])!!c:f(a-1)(b-1)c

Try it online!
Haskell, 69 61 60 58 bytes
(0!b)_=[]
(a!b)c|b==c=a!b$c+1|1>0="\\|/"!!c:((a-1)!(b-1))c

Try it online!
Not a very complex answer but it beats both of the existing Haskell answers.

R, 75 68 61 57 bytes
An anonymous function. I'll post a fuller explanation if there is interest.
function(t,n,d)cat(c("\\","|","/")[(1:t>n-d)+1+d],sep="")

Try it online!

Haskell, 51 bytes
f a b c=("\\|"!!c<$[1..b-c])++("|/"!!c<$[b-c..a-1])

a = number of dominoes, b = 1-based index of the touched one, c = direction (0 is left and 1 is right).
Try it online!

Defining an infix operator also works for more than two inputs: (a#b)c= ....

PHP, 89 Characters
function o($a,$p,$d){for($i=0;$i<$a;$i++)echo$d==0?($i+1>$p)?'|':'\\':($i+1<$p?'|':'/');}

Just because I love PHP.
EDIT: The following code does the same.
function dominoes ($number, $position, $direction) {
    for ($i=0; $i<$number; $i++){
        if ($direction==0) {
            if (($i+1) > $position) {
                echo '|';
            } else {
                echo '\\';
            }
        } else {
            if (($i+1) < $position) {
                echo '|';
            } else {
                echo '/';
            }
        }
    }
}

Got a more detailed version?

@Martijn , I edited my post to include one.

Now I can see what it does. Nothing too fancy, but +1 :)

Thanks! @NPlay 's solution(s) look fancy though!

a couple of golfing tips: 1) Unnecessary parentheses at ($i+1>$p). 2) Rewriting your ternary expression to $d?($i+1<$p?'|':'/'):$i+1>$p?'|':'\\' saves another 3 bytes. Or just remove ==0 and invert directions. 3) With $i++<$a you can remove $i++ from the post condition and use $i instead of $i+1 (-6 bytes). 4) $i=0 is not necessary; but you´d have to suppress notices (option --n)  if you remove it (-4 bytes).

@Titus thank you, feel free to edit and claim credit!

PHP - 64
function f($a,$b,$c){for($w='\|/';++$i<=$a;)echo$w[$c+($i>$b)];}

A simple loop, and echo-ing the character.
Generates a Notice: Undefined variable: i, here's another version silenting the error (65 characters) :
function f($a,$b,$c){for($w='\|/';@++$i<=$a;)echo$w[$c+($i>$b)];}

And a version withtout any error (69 characters) :
function f($a,$b,$c){for($w='\|/',$i=0;++$i<=$a;)echo$w[$c+($i>$b)];}

Other functions in PHP :
sprintf / printf padding
function f($a,$b,$c){printf("%'{${0*${0}=$c?'|':'\\'}}{$a}s",sprintf("%'{${0*${0}=$c?'/':'|'}}{${0*${0}=$a-$b+$c}}s",''));}

padding via str_pad / str_repeat functions
function f($a,$b,$c){$f='str_repeat';echo$f($c?'|':'\\',$b-$c).$f($c?'/':'|',$a-$b+$c);}
function f($a,$b,$c){echo str_pad(str_repeat($c?'|':'\\',$b-$c),$a,$c?'/':'|');}

using both printf and str_repeat functions
function f($a,$b,$c){printf("%'{${0*${0}=$c?'|':'\\'}}{$a}s",str_repeat($c?'/':'|',$a-$b+$c));}
function f($a,$b,$c){$w='\|/';printf("%'$w[$c]{$a}s",str_repeat($w[$c+1],$a-$b+$c));}

Scala 75 characters
def f(l:Int,p:Int,t:Char)=if(t=='l')"\\"*p++"|"*(l-p) else "|"*(l-p):+"/"*p

CJam - 20
q~
:X-_"\|"X=*o-"|/"X=*

The main code is on the second line, the first line is just for getting the parameters from the standard input (otherwise you need to put the parameters in the code).
Try it at http://cjam.aditsu.net/
Examples:
12 4 1
|||/////////

8 5 0
\\\\\|||

Explanation:
:X stores the last parameter (0/1 direction) in variable X
- subtracts X from the knock-over position, obtaining the length of the first sequence of characters (let's call it L)
_ makes a copy of L
"\|"X= gets the character to use first: \ for X=0 and | for X=1
* repeats that character L times
o prints out the string, removing it from the stack
- subtracts L from the number of dominoes, obtaining the length of the second sequence of characters (let's call it R)
"|/"X= gets the character to use next: | for X=0 and / for X=1
* repeats that character R times

Common Lisp
This won't win in a code golf, but it highlights Common Lisp's justification format directive:
(lambda (n p d &aux (x "\\|/"))
   (format t "~v,,,v<~v,,,v<~>~>" n (aref x d) (+ d (- n p)) (aref x (1+ d))))

The arithmetic isn't bad:  n is the total number of dominoes; p is the position of the first toppled domino; d is either 0 or 1, representing left and right (as allowed in the comments), and is used as an index into x;  x is a string of \, |, and /.  The format string uses two (nested) justification directives, each of which allows for a padding character.  Thus:
(dotimes (d 2)
  (dotimes (i 10)
    ((lambda (n p d &aux (x "\\|/"))
       (format t "~v,,,v<~v,,,v<~>~>" n (aref x d) (+ d (- n p)) (aref x (1+ d))))
     10 (1+ i) d)
    (terpri)))

\|||||||||
\\||||||||
\\\|||||||
\\\\||||||
\\\\\|||||
\\\\\\||||
\\\\\\\|||
\\\\\\\\||
\\\\\\\\\|
\\\\\\\\\\
//////////
|/////////
||////////
|||///////
||||//////
|||||/////
||||||////
|||||||///
||||||||//
|||||||||/

J, 23 21 19 bytes
'|/\'{~{:-(>i.)~`-/

Try it online!
Input is a list of integers in the standard order.

05AB1E, 19 bytes
αα©„\|³è×¹®-„|/³è×J

I still have the feeling it's a bit long, but it works.. And better than the initial 23 bytes solution I had with if-else construction, which I quickly dropped..
Input order is the same as in the challenge: total length, index, 1/0 for left/right respectively.
Try it online or verify both test cases.
Explanation:
α                     # Take the absolute difference of the first two (implicit) inputs
                      #  i.e. 10 and 5 → 5
                      #  i.e. 6 and 3 → 3
 α                    # Then take the absolute difference with the third (implicit) input
                      #  i.e. 5 and 1 → 4
                      #  i.e. 3 and 0 → 3
  ©                   # Store this number in the register (without popping)
   „\|                # Push "\|"
      ³è              # Use the third input to index into this string
                      #  i.e. 1 → "|"
                      #  i.e. 0 → "\"
        ×             # Repeat the character the value amount of times
                      #  i.e. 4 and "|" → "||||"
                      #  i.e. 3 and "\" → "\\\"
         ¹®-          # Then take the first input, and subtract the value from the register
                      #  i.e. 10 and 4 → 6
                      #  i.e. 6 and 3 → 3
            „|/       # Push "|/"
               ³è     # Index the third input also in it
                      #  i.e. 1 → "/"
                      #  i.e. 0 → "|"
                 ×    # Repeat the character the length-value amount of times
                      #  i.e. 6 and "/" → "//////"
                      #  i.e. 3 and "|" → "|||"
                  J   # Join the strings together (and output implicitly)
                      #  i.e. "||||" and "//////" → "||||//////"
                      #  i.e. "///" and "|||" → "///|||"

Vyxal, 23 bytes
[-‹\|*₴+\/*,|-\\*₴+\|*,

Try it Online!

C - 62 64 ('l':left, 'r':right)
f(a,b,c){for(b=a-b;a--;)putchar(c&2?a<b?47:124:a>b-2?92:124);}

C - 58 (0:left,1:right)
f(a,b,c){for(b=a-b;a--;)putchar(124-(a<b-!c?c*77:!c*32));}

recursive approach, but still, same length
f(a,b,c){a&&f(a-1,b,c)+putchar(124-(a<=b+!c?!c*32:c*77));}

awfully long (75) but most complex one (repeat function integrated into it)
f(a,b,c){c>1?a&&f(a-1,putchar(b),2):f(b+c,c?92:124,2)+f(a-b-c,c?124:47,2);}

This segfaults for me, probably because printf expects a const char* instead of an int (using putchar instead works). It also looks like this always knocks the dominoes over towards the right (i.e. for 10,5,'l' it prints something like ||||\\\\\\  instead of \\\\\|||||).

PowerShell (107 95)
filter d($a,$b,$c){-join(1..$a|%{if($_-ge$b-and$c){'/'}elseif($_-le$b-and!$c){'\'}else{'|'}})}

If we're allowed to treat the third parameter as an integer (0=l,1=r), then I can shave a little off here.
Test input:
d 10 5 r
||||//////
d 10 5 l
\\\\\|||||

Update:
d 10 5 1
||||//////
d 10 5 0
\\\\\|||||

If anyone by chance wants an explanation I will gladly add one. And as always I'm open to suggestions.
Original:
function d($a,$b,$c){-join(1..$a|%{if($_-ge$b-and$c-eq'r'){'/'}elseif($_-le$b-and$c-eq'l'){'\'}else{'|'}})}

C++ 181
#define C(x) cin>>x;
#define P(x) cout<<x;
int n,k,i;char p;
int main(){C(n)C(k)C(p)
for(;i<n;i++){if(p=='r'&&i>=k-1)P('/')else if(p=='l'&&i<=k-1)P('\\')else P('|')}
return 0;}

You don't actually need to explicitly return 0 from main.

It doesn't compile for me because cin and cout are not in the global namespace - what compiler are you using?  Also, C(n)>>k>>p would be shorted than C(n)C(k)C(p) wouldn't it? And if the define for P() could stringify the argument wouldn't that save characters for all the quotes?  And when you compare p to 'l' and 'r': 0 and 1 would be shorter - specifically >0 instead of =='r' and <1 instead of =='l' (assuming you are ok using numbers instead of r/l - if not <'r' is still shorter than =='l' and >'l' is still shorter than =='r')

@JerryJeremiah for cin and cout need "using namespace std".

I know but since it is only used twice it is shorter to qualify the functions.  Neither way works on my compiler without the include.

VBScript 101 95 74
Edit: Looks like a lot of answers accept bool directions. For char directions, replace -d with +(d="r") for a score increase of 6.
function f(a,p,d):for x=1to a:f=f+mid("/|\",3-d+(x>p),1):next:end function

This doesn't work.

@JesterBLUE Thanks for pointing that out. I re-coded and shortened it a bit, too.

That looks a lot nicer but it still isn't producing the right results.  Try Mid("|/",1-d-(x>p+d),1).  (Also note that d is never explicitly converted to a boolean, so running f(10,4,1) will give funky results because the function relies on an implicit boolean to integer conversion.   Putting in a d=d<>0 would lock d down to 'true' or 'false'. It's not a problem here, though, because this is golf.)

@JesterBLUE I had to flip the symbol order to get this to work correctly. I didn't realize I broke the code when I allowed for "bool" directions.

C# 92('\':left, '/':right)
String d(int c, int p, char d){ String r="";for(int i=0;i<c;i++)r+=(i>=c-p)?d:'|';return r;}

Would be even shorter if you rename result and get rid of the additional whitespaces.

AWK, 76 61
{ORS="";for(i=1;i<$2;i++)print"|";for(i=$2;i<=$1;i++)print($3=="r"?"/":"\\")}

Usage:
echo 10 5 r | awk '{ORS="";for(i=1;i<$2;i++)print"|";for(i=$2;i<=$1;i++)print($3=="r"?"/":"\\")}'

Although I'm wondering if I can nest ternary operators to make this shorter (although I'm playing around in bash right now and it doesn't seem like you can).
edit -- shorter version:
{ORS="";for(i=0;i<$1;i++)print i<$2?"|":($3=="r"?"/":"\\");}

What about {ORS="";for(i=0;i<$1;i++)print i<$2?"|":($3=="r"?"/":"\\");}

That's exactly what I didn't think was possible. Thanks.

PHP - 105,97, 96
 function a($r,$l,$f){$a=str_repeat('|',$l-$f);$b=str_repeat($r?'/':'\\',$f);echo$r?$a.$b:$b.$a;}

Example results:
a(true,10,4);  -> \\\\||||||
a(false,10,5); -> |||||/////
a(false,10,2); -> ||||||||//

Javascript, 81 85 characters

function e(a,b,c){l='repeat';d='|'[l](--a-b++);return c>'q'?d+"/"[l](b):"\\"[l](b)+d}

First time trying codegolf, was fun thanks :)

Might as well modify the function to be an ES6 function, as string repeat is ES6 (doesn;t work in Chrome).

JavaScript - 85 chars
function d(a,b,c){for(r=c?"\\":"/",p="",b=a-b;a--;)p+=c?a<b?"|":r:a>b?"|":r;return p}

1 = Left, 0 = Right
d(10,3,1)
\\\|||||||
d(10,3,0)
||////////
d(10,7,1)
\\\\\\\|||
d(10,7,0)
||||||////

vb.net (~75c)
Dim f=Function(l,p,d)(If(d="l",StrDup(p,"\"),"")& StrDup(l-p-If(d="l",1,0),"|")).PadRight(l,"/")

Clojure, 81 chars
(defn g[a,p,d](apply str(map #(nth "\\|/"(+(if(>= % (- p d)) 1 0) d))(range a))))

JavaScript (ES5) - 86 chars
function f(a,p,d){r='';while(a-->p+1)r+='|';while(a-->=0)r=d>'q'?r+'/':'\\'+r;return r}

Autoit 245 Bytes
Local $1 = "",$dir = "l",$amout = 100,$pos = 33
for $i=1 to $pos
    if $dir = "r" then
    $1 = $1 & "|"
Else
    $1 = $1 & "\"

EndIf
next
for $i=1 to $amout-$pos
    if $dir = "r" then
    $1 = $1 & "/"
Else
    $1 = $1 & "|"
EndIf
next
ConsoleWrite($1 & @cr)

Python 71 59
def k(n,p,d):c,r='\/'[d],n-p;return[c*p+'|'*r,'|'*p+c*r][d]

Haskell (72)
Using guards and the characters 'r' and 'l' as directions:
r=replicate;k a o d|d=='r'=r(a-o)'|'++r o '/'|d=='l'=r o '\\'++r(a-o)'|'

Perl : 66 characters
My first code golf submission! Thanks for the fun challenge.
sub k{($n,$p,$r)=@_;$n-=$p;$d=$r?"|"x--$p.'/'x++$n:'\\'x$p.'|'x$n}

Explanation with whitespace:
sub k{
  ($n,$p,$r) = @_;      # get function arguments: <# dominos> <position> <0=left, 1=right>
  $n -= $p;             # total number of dominos - position
  $d = $r ? "|"x--$p . '/'x++$n : '\\'x$p . '|'x$n
                        # if direction = 1, make pos - 1 '|'s and (total - position  + 1) '/'s
                        # if direction = 0, make pos '\'s and (total - position) '|'s
                        # return is the last action of the function, it returns the string in $d.
                        # Semicolon at end of line can be left off, as it is the last statement of the function
}

Example usage and output:
my $result = k(10,5,1); print "$result\n";
||||//////
my $result = k(10,5,0); print "$result\n";
\\\\\|||||

Python, 69
My first code golf submission, with Python in 69 characters:
def d(a,b,c):print "|"*(b-1)+"/"*((a+1)-b) if c else "\\"*b+"|"*(a-b)

Usage: d(10,5,1)

I know it's been 4 years since this was posted but you have a lot of extra whitespace involved in this answer.  White space is generally not required on the borders of quotes or parentheses.  Here is your code without the extra whitespace def d(a,b,c):print"|"*(b-1)+"/"*(a+1-b)if c else"\\"*b+"|"*(a-b).  You could also use a lambda to make this shorter lambda a,b,c:"|"*(b-1)+"/"*(a+1-b)if c else"\\"*b+"|"*(a-b).

Ooooookkkkkkkkk

PHP, 55 bytes
for([,$c,$n,$d]=$argv;$c--;)echo"\|/"[$d+(++$i+$d>$n)];

requires PHP 7.1 or later
replace [...]=$argv with list(...)=$argv for PHP 5.5 or later
for older PHP, insert $s="\|/", before that and replace the other "\|/" with $s.

Run with php -nr '<code>' <total> <N> <numeric direction> or try it online.

Japt, 15 bytes
I'm sure this could probably be shorter but it's been a long day. Uses 0 & 1 for left and right.
ç| hW*VVçWg"\\/

Try it
ç| hW*VVçWg"\\/     :Implicit input of integers U=total, V=n & W=direction
ç|                  :Repeat "|" U times
   h                :Replace the characters starting at 0-based index ...
    W*V             :W times V with ...
       Vç           :V times repeat ...
         Wg"\\/     :Index W into "\/"

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/


text:
Create an autocorrect program
People sometimes make spelling eorrors. A lto. Your challenge is to write a program that can take a string with certain spelling errors, such as the switching of I and E, and correct those mistakes. This has to be able to make changes to any combination of characters in any string, and fix the spelling errors. This is a popularity-contest, the winner will be chosen in three days. If I need to clarify any additional details, please do say, and I will add it to my challenge. Good luck!
Rules

You may read correctly-spelled words from a file.
You will read the string from standard input.
You need only correct basic spelling errors.
It's ok if your program makes a few errors.

Is it OK if we read correctly spelled words from a file? And are we reading from stdin?

@golfer9338 Yes and yes.

Yes, there are some things which you need to clarify. What do you mean by "has to be able to make changes to any combination of characters in any string"? Which errors does it need to correct? What about overcorrection? What about other languages?

@PeterTaylor It needs to be able to fix basic spelling errors. Such as the swapping of I and E. Like misspelling their. It doesn't matter what language you make it in. In the case of overcorrecting, that's okay if it makes a few mistakes, even advanced autocorrect like the one on my iphone makes mistakes.

You need a set of production rules like "If you see this, it should be replaced with this." Making it a popularity contest is not an excuse for completely leaving out the details of the task you have asked us to do. Btw, golfer9338 added a neat idea: read correctly spelled words from a file. His edit was not perfect, but I approved it anyway because I think that his idea could salvage this challenge.

It's still completely opaque what you mean by "has to be able to make changes to any combination of characters in any string".

for a real "good" correction, we need to know the set of words which are "reasonable". In a program editor, this depends on the word before the cursor. This may be either a class or variable name, or the name of the function to be called (some syntax awareness required here). In a general text editor, this would be a list of words from a dictionary.
In the following code, I assume that the list of "good" words is found in "candidates", in Smalltalk this would be one of:
Smalltalk allClasses collect:[:cls | cls name]

for class names, or
Smalltalk allClasses collectAll:[:cls | cls methodDictionary keys] as:Set

for the names of all methods.
Of course, in a real world corrector, this would take into account the current scope to restrict the set of possible candidates.
The code then selects the best candidate by its editing distance,
which is the distance between two strings based on the weighted number of  insert, delete and replace operations required to change one string onto another. All Smalltalks provide a "spellAgainst:" method in their String class, which is based on levenshtein or a similar algorithm.
"the following is of course very Smalltalk dialect specific,
 as the GUI frameworks are slightly different.
 It assumes there is an editor object, which represents the code edit
 window."

candidates := <one of the above>.
wordToFix := editor wordBeforeCursor.

best := candidates detectMax:[:each | each spellAgainst: wordToFix].

editor selectWordBeforeCursor.
editor replaceSelectionBy:best.

PS: one of the coolest features of Smalltalk is that the IDE is part of your program and vice versa (they are the same), so you can actually add the above code fragment to your editor's keyPress method and have it work immediately!

Python
This uses Levenshtein distance, but doesn't account for non-alpha characters and case. Corrects single misspelled words. Enter a string on stdin, output on stdout, and have a newline separated list of words in a file called words.txt in the same directory.
Code
# Open list of correcly-spelled words.
wordFile = open("words.txt")
threshold = 8
listOfWords = input().split()
index = 0

def lev(a, b):
    if min(len(a), len(b)) == 0:
        return max(len(a), len(b))
    else:
        return min(lev(a[:-1], b) + 1, lev(a, b[:-1]) + 1,
            lev(a[:-1], b[:-1]) + int(not a[-1] == b[-1]))

for x in listOfWords:
    replacement = (x, threshold + 1)

    for word in wordFile:
        x = x.lower()
        word = word[:-1].lower()

        if x == word:
            replacement = (x, 0)
            break # Some words may actually be spelled correctly!

        d = lev(x, word)
        if (d < threshold) and (replacement[1] > d):
            replacement = (word, d)

    listOfWords[index] = replacement[0]
    index += 1
    wordFile.seek(0)

print(*listOfWords)

Bugfix
All words are corrected now.

Python3, I take it?

@DatEpicCoderGuyWhoPrograms Yes.


text:
Basic Algebraic Expansion
Problem
I've got a GREAT new program that will change the way we think about math in computing, taking in strings of algebraic functions and doing AMAZING things with them! The only problem, is that I am only able to parse specific algebra, otherwise the universe folds into itself, which is bad. Fortunately, I only need a few basic operations in this amazing new program's input, but I still need it expanded!
Rules

An answer must be able to simplify the following expressions

2+2 should reduce to 4
(5+x)+6 should reduce to x+11
(x+2)^2 should reduce to x^2+4*x+4
(x-5)*(3+7*x) should reduce to 7*x^2-32*x-15
5*x+9*x should reduce to 14*x
(2*x^2)*x^3 should reduce to 2*x^5

Answers must be able to COMPLETELY remove parenthesis, which implies that all distribution must take place.
Answers should be able to handle all of the following operators and standard tokens:

+ (The addition function)
- (The subtraction function)
* (The multiplication function)
( (The left parenthesis, used to indicate a group)
) (The right parenthesis, used to indicate the end of the last started group)
x (The standard variable)
[0-9]+ (literal nonnegative numbers)

Answers must be capable of at least squaring, using the notation expr^2, including (expr)^2 recursively, since (expr) is itself an expression ;)
A solution must be in a standard infix notation, none of the RPN nonsense!
No library functions such as Mathematica's Simplify to do this for you.
Solution should be a function that takes in a single argument and return the expanded version

As this is code-golf, the answer with the fewest (key)strokes wins, 1 week from OP.
Notes
There are no spaces in this world of math, of course! Only parenthesis.
So no division is required to save from factoring
Standard order of operations apply.
I'm aware that some of what I'm asking is simplification (e.g. 2+2=4) where other parts are actually the opposite, such as expanding (x+1)^2 to be x^2+2x+1. This is intentional. :)
-25 strokes for a solution that can do (expr)^n instead of just (expr)^2
-15 strokes for a solution able to evaluate juxtaposed multiplication, such as 4x+5x == 9x, or 4(x+1) = 4x+4
-5 strokes for a solution able to handle multiple variables (A variable being exactly one lowercase alphabet character)
-5 strokes for a solution able to remove leading 0's (007 to just 7 [Not today, Bond!] [Jeez now I feel like I'm writing Lisp])

I do believe that
(x-5)(3+7x)
is
(1x + -5)(7x + 3)
is
7x^2 + (3-35)x + -15
or
7x^2-32*x-15

How should input be provided? Command line arguments? Standard input? Should probably be specified.

@JeffGrigg This is why I need the program ;) Hehe I actually added the 7*x to display more complexity and forgot to update the solution. Thanks! And I could have sworn I included that they should be taken as an argument to a function

You sholud add literal number in the tokens list. And what kind of numbers? With decimal point or just integers?

Having to deal with one letters variables, I propose to use a more canonical form for algebraic expression and avoid '*'. The expressions could be better looking: (x-5)*(3+7*x) => (x-5)(3+7x) or 7*x^2-32*x-15 => 7x^2-32x-15

@edc65 this is already handled in the question where it talks about juxtaposed multiplication. Its -15 strokes for handling.

I nearly have a working solution for this in J, I just need to parse negative numbers correctly. It's probably the ugliest, hackiest thing I've ever written, but thankfully it's almost over.

@algorithmshark how's that solution coming? ;)

No division? Or is that just part of the expr^n bonus (i.e. with n=-1)?

@ssdecontrol without division, we are speaking of polynomials. Add the division and it's a very different thing

do we count chars or bytes?

JavaScript (EcmaScript 6) 698 (748-50 bonus) 725 780 1951
To be golfed. But I'm proud it works.
(Edit: bug fix, problems with brackets and minus)
(Edit2: golfed more, fixed bug in output)
(Edit3: golfed once more, last time I promise)
Comment
Basically, function X is an infix calculator that operates on literal polynomials.
Each polynomial is stored as a js object, the key being the term (x^3y^2) and the value being the numeric coefficient. Function A,M and E are add, multiply and exponent.
Golfed Code
(It cannot probably be golfed more...)
Note: not counting newlines added for (ehm...) readability
K=x=>Object.keys(x).sort(),
A=(p,q,s,t,c)=>[(c=(s+1)*q[t]+~~p[t])?p[t]=c:delete(p[t])for(t in q)],
M=(p,q,t,c,o,u,f,r,v={})=>([A(v,(r={},[(c=p[f]*q[t])&&(r[o={},(u=f+t)&&(u.match(/[a-z]\^?\d*/ig).map(x=>o[x[0]]=~~o[x[0]]+(~~x.slice(2)||1)),K(o,u=k).map(i=>u+=o[i]>1?i+'^'+o[i]:i)),u]=c)for(f in p)],r),k)for(t in q)],v),
E=(p,n)=>--n?M(p,E(p,n)):p,
O=n=>{for(l=0;h(o=s.pop())>=h(n);)a=w.pop(b=w.pop()),o=='*'?a=M(a,b):o>d?a=E(a,b[k]):A(a,b,o),w.push(a);s.push(o,n)},
X=e=>(l=k='',w=[],s=[d='@'],h=o=>'@)+-*^('.indexOf(o),
(e+')').match(/\D|\d+/g).map(t=>(u=h(t))>5?(l&&O('*'),s.push(d)):u>1?O(t):~u?s.pop(s.pop(O(t)),l=1):(l&&O('*'),l=1,w.push(v={}),t<d?v[k]=t|0:v[t]=1)),
K(p=w.pop()).map(i=>(k+=(c=p[i])>1?s+c+i:c<-1?c+i:(c-1?'-':s)+(i||1),s='+')),k||0)

Test In FireFox console
['2+2','(5+x)+6','(x+2)^2','(a+b)(a-b)','(a+b)*(a-b)','(a-b)(a-b)', '(x-5)*(3+7*x)','5*x+9*x','(2*x^2)*x^3','(2*x+3)^(2+3)*2^3']
.map(x => x + ' => ' + X(x)).join('\n')

Output
2+2 => 4
(5+x)+6 => 11+x
(x+2)^2 => 4+4x+x^2
(a+b)(a-b) => a^2-b^2
(a+b)*(a-b) => a^2-b^2
(a-b)(a-b) => a^2-2ab+b^2
(x-5)*(3+7*x) => -15-32x+7x^2
5*x+9*x => 14x
(2*x^2)*x^3 => 2x^5
(2*x+3)^(2+3)*2^3 => 1944+6480x+8640x^2+5760x^3+1920x^4+256x^5

Bonuses
25: 2*x+3)^(2+3)*2^3 => 1944+6480x+8640x^2+5760x^3+1920x^4+256x^5
15: 4x+5x => 9x
5: 007x+05x^(06+2) => 7x+5x^8
5: (a+b)(a-b) => a^2-b^2

Ungolfed Code
Show=(p)=>(
  Object.keys(p).sort().map(i=>(c=p[i])-1?c+1?c+i:'-'+i:i).join('+').replace(/\+-/g,'-')
)
AddMonoTo=(poly, term, coeff, c)=>(
  (c = coeff + ~~poly[term]) ? poly[term]= c : delete(poly[term])
)
AddPolyTo=(p1, p2, s, t)=>(
  [ AddMonoTo(p1, t, (s+1)*p2[t]) for (t in p2)]
)
MulTerm=(t1, t2, o={})=>(
  (t1+=t2)&&
  (t1.match(/[a-z](\^\d+)?/g).every(x=>o[x[0]]=(~~x.slice(2)||1)+(~~o[x[0]])),
  Object.keys(o,t1='').sort().every(i=>t1+=o[i]>1?i+'^'+o[i]:i)),
  t1
)
MulMono=(poly, term, coeff, c, r={}, t)=>(
  [(c = poly[p]*coeff) && (r[MulTerm(p,term)] = c) for (p in poly) ],r
)
MulPoly=(p1, p2, r={}, p)=>(
  [AddPolyTo(r,MulMono(p2, p, p1[p]),'') for (p in p1)],r
)
ExpPoly=(p,n,r=p)=>{
  for(;--n;)r=MulPoly(r,p);
  return r
}
Expand=ex=>
{
  var tokens = ex.match(/\D|\d+/g).push(')')
  var t,a,b,v,LastV=0
  var vstack=[]
  var ostack=['_']
  var op={ '+': 3, '-':3, '*':4, '^':6, '(':8, _: 1, ')':2}
  var OPush=o=>ostack.push(o)
  var OPop=_=>ostack.pop()
  var VPush=v=>vstack.push(v)
  var VPop=v=>vstack.pop()

  var Scan=i=>
  {
    LastV=0 ;
    for (; (t=tokens[i++]) && (t != ')'); )
    {
      if (t == '(')
      {
        if (LastV) CalcOp('*')
        OPush('_'), i=Scan(i)
      }
      else if (op[t])
        LastV=0, CalcOp(t)
      else
      {
        if (LastV) CalcOp('*')
        LastV = 1
        VPush(v={})
        t < 'a' ? v[''] = t|0 : v[t] = 1
      }
    }
    CalcOp(t);
    OPop();
    OPop();
    LastV=1;
    return i;
  }
  var CalcOp=nop=>
  {
    for (; op[po = OPop()] >= op[nop];)
      b=VPop(), a=VPop(), CalcV(a,b,po);
    OPush(po), OPush(nop);
  }
  var CalcV=(a,b,o)=>
  {
    if (op[o] < 4)
      AddPolyTo(a,b,o)
    else if (o == '*')
      a=MulPoly(a,b)
    else // ^
      a=ExpPoly(a,b['']) // only use constant term for exp
    VPush(a)
  }
  Scan(0)

  return Show(vstack.pop())
}

y u use semi-colons only in some places? Is it because the lack of frame that you need them? I'm not very EcmaScript compliant with my JS ;)

Commas separate expression, semicolons separate statements. It's clearer in for(i1,i2,i3; c1,c2; s1,s2,s3). I have just a semicolon in golfed colde to close a statement inside a for (function O). Why commas? two stamenents must be grouped with {} while two or more expressions can be simply listed.

J - 350 char - 25 = 325 pts
Forgive me, Roger Hui, for I have sinned.
x=:0 1
f=:(('+_';'-';'_';'-')rplc~' '-.~'+'}.@,@|.@,.s(}.@]`(,&":)@.t'*x'"_`('*x^',":)`(''"_)@.t=.*@<:@[)/"1@#~0~:0{|:@s=.,.i.@#)@p=:(0{::'()'+/@,:&,e'+'@((+/@,:&,-)~e'-')@(*/a e'*')@('^'(*/(a=.+//.@)/@#,:e=:2 :'(<@; ::({:u/&.>{.)/.~i.@#-i.@#(>+>:)(<,v){.@i.~])^:_'))@:(([^:(''-:])". ::])&.>)@([-.~;@]<@(p^:(1<#));.1~1,0=2*/\[:+/\(*0,}:@)1 _1 0{~i.)&;:])

The above monstrosity defines a number of variables, of which the variable f is a function satisfying the constraints in the question above. I claim the "expr^n" bonus for 25 points.
Here's the golf in action at the J REPL.
   x=:0 1
   f=:(('+_';'-';'_';'-')rplc~' '-.~'+'}.@,@|.@,.s(}.@]`(,&":)@.t'*x'"_`('*x^',":)`(''"_)@.t=.*@<:@[)/"1@#~0~:0{|:@s=.,.i.@#)@p=:(0{::'()'+/@,:&,e'+'@((+/@,:&,-)~e'-')@(*/a e'*')@('^'(*/(a=.+//.@)/@#,:e=:2 :'(<@; ::({:u/&.>{.)/.~i.@#-i.@#(>+>:)(<,v){.@i.~])^:_'))@:(([^:(''-:])". ::])&.>)@([-.~;@]<@(p^:(1<#));.1~1,0=2*/\[:+/\(*0,}:@)1 _1 0{~i.)&;:])

   f '2+2'
4
   f '(5+x)+6'
x+11
   f '(x+2)^2'
x^2+4*x+4
   f '(x-5)*(3+7*x)'
7*x^2-32*x-15
   f '5*x+9*x'
14*x
   f '(2*x^2)*x^3'
2*x^5
   f '(2*x+3)^(2+3)*2^3'   NB. bonus
256*x^8+1920*x^7+5760*x^6+8640*x^5+6480*x^4+1944*x^3

Here's the gist of what's going on.

'()'...@([-.~;@]<@(p^:(1<#));.1~1,0=2*/\[:+/\(*0,}:@)1 _1 0{~i.)&;: - Recursively break down the expression based on its parenthesized subexpressions, and evaluate them (the ... bit, to be described below) as they are ready. ;: performs the tokenizing.
(([^:(''-:])". ::])&.>) - Evaluate atoms. If the atom is numeric, it is turned into a scalar number. If the atom is an operator, it is left as-is. If the atom is the variable x, it is turned into the vector 0 1. (That's why we define x=:0 1 at the start.) In general we store the polynomial a*x^n + b*x^(n-1) + ... + c*x + d as the n+1-item list d c ... b a.
e=:2 :'(<@; ::({:u/&.>{.)/.~i.@#([->+>:){.@i.&(<,v))^:_' - This curious conjunction takes a verb on the left and a character on the right. It finds the first instance of that character in its tokenized, paren-less input, and evaluates it with the arguments around it, and repeats until there are no more such characters to find. Thus, we iteratively simplify the expression, with order of operations controlled by order of application of e.
And then all the stuff in the front is just pretty-printing output. rplc is a standard library function for substring replacement. We can save another three chars if we're allowed to put the lowest degree terms first instead of the highest, by removing the @|..

I am honestly uncertain whether I can squeeze any more characters out of this golf. I can't think of any other approach that doesn't require a similar amount of overengineering, but that doesn't mean there isn't one. Either way, I'm pretty sure I've squeezed all the obvious characters out of this version.

Bravo! And you can get rid of the negative number fix, since the - token is only noted as the subtraction function. :)

@ChristopherWirt Didn't catch that. Either way, done.

(2*x+3)^(2+3)*2^3 should give 256x^5+1920x^4+5760x^3+8640x^2+6480x+1944 or I am missing something?

Mathematica: 56 - 25 - 15 - 5 - 5 = 6
Of course no library functions as Expand or Distribute, just pattern replacement. Mathematica does almost everything for us (hax!), what is left are just rules for distribution and power expansion. The only non-trivial examples therefore are (x-5)*(3+7*x) and (x+2)^2.
f=#//.{x_ y_Plus:>(x #&/@y),x_Plus^n_:>(x #&/@x)^(n-1)}&

Examples
(x-5)*(3+7*x) // f
-15 - 32 x + 7 x^2

(x + 2)^2 // f
4 + 4 x + x^2

You have some very strange characters in both your examples. Can you clean it up?

@edc65 M10 acting strange with copy/paste I guess.

I probably should have banned mathematica all tofether ;) good work, though


text:
Calculate the most digits of pi
There are a lot of challenges on this site regarding pi, but none that challenge you to calculate as many digits of pi as possible.
As you all may know, pi in its decimal form goes on for infinity, so calculating it in its entirety is near to impossible. However, I challenge you to write a program in your language of choice that can calculate as many digits of pi as possible, and include an explanation with your code. The winner will be decided by popularity contest.
The only restriction is that your program cannot connect to the internet. The point is not to have your program search the internet for the most digits of pi.
So in summary, the goal is to write a program that computes as many digits of pi as possible (in decimal, so 3.14159....). Your program cannot simply connect to the internet and lookup digits, it needs to calculate it.
Note here that the goal here is to calculate as many digits as possible, but that is not the winning criteria. The winner will be based on popularity (number of upvotes). Remember, we're here to learn just as much as to have fun.
Winner will be decided on July 16 at 10 AM eastern time.
And please, don't be this guy. Let's have fun.

What's stopping me from calculating "all" of them? (It'll take some time, I know, but there's no time constraint in your challenge.)

@m.buettner Forgot to add the time constraint, you have a week to calculate them all! ;)

I don't have time to implement it now but maybe the BBP algorithm? The question doesn't explicitly say you have to use decimal...

In your question, you said "near to impossible". Given the universe has a finite lifespan, it IS impossible :)

print "3.2" I win, it's the law

This can either be "Calculate pi to arbitrary precision" as a popularity contest (pretty boring and not far off a duplicate of http://codegolf.stackexchange.com/q/506/194 ); or "Calculate as many digits of pi as possible in a given time" as [tag:fastest-code]. But at present it seems to be asking for both, which doesn't make sense.

@PeterTaylor I agree for the most part. I think 'fastest time to calculate X digits' (where X is 1M, perhaps) is just about the only variant of 'calculate pi' we haven't yet had.

C
The following is my favourite implementation of a pi calculation program:
#define _ F-->00 || F-OO--;
long F=00,OO=00;
main(){F_OO();printf("%1.3f\n", 4.*-F/OO/OO);}F_OO()
{
            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
       _-_-_-_-_-_-_-_-_
            _-_-_-_
}

Found here with the following explanation:

Pi -- A unique program layout and the most unusual method of calculating pi I have ever seen. The source code is a circle and the program works by calculating its own area and diameter, and then doing a division to approximate pi!! Very bizzare.

I haven't tried this, but I guess you can make the circle larger to calculate more digits of pi.

This is pretty cool! Can you put the language you used as the title though?

It's C, but I can appreciate that might not be immediately obvious. :)

I challenge you to write a program in your language of choice Ok, you referenced a program from an ofuscation contest here. That would have been a neat reference in the comments, but I don't see how this qualifies for an answer.

I agree. This is not an answer, it's a link.

@GregHewgill "I haven't tried this, but I guess you can make the circle larger to calculate more digits of pi." Radius 50 is accurate to 1.3e-4: http://codepad.org/dVM0rwpG

Mathematica
I'm definitely going for the simplicity/golf award here with 5 characters:
π~N~n

Just defined n to be the number of digits you want.
I did a quick test to figure out how many digits that allows me to calculate within a week. I ran this for n from 100 000 to 10 000 000 in steps of 100 000 and measured the time. The plot looks very much linear (apart from a few outliers, because I used my machine during the test), so I got a least squares fit for a linear function, solved it for n and plugged in t = 60*60*24*7. On my 3 year-old laptop, I'd get about 4.5 * 1011 digits, which is 450 billion. Realistically it might be a bit less, as I can't predict whether the algorithm used by Mathematica will at some point slow down, e.g. due to memory or cache constraints.

The plot is definitely not linear. From my experience the time increases exponentially.

Technically the Using built-in functions to do the work no-longer-funny answer is an upvote short of a qualified majority, but it's still not funny.

C - 13 million digits
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#define DIGITS 13000000

int main() {
  uint64_t d=0,h=1e9;
  uint32_t b,c=30*((DIGITS+25)/9),e=0,g;
  uint32_t* f=(uint32_t*)malloc(4*c);
  while(b=c-=30){
    while(--b){
      d=d*b+h*(e?f[b]:2);
      f[b]=d%(g=2*b-1);
      d/=g;
    }
    printf(e?"%09d":"%d.",e+d/h);
    e=d%h;
  }
  free(f);
  return 0;
}

Using only standard libraries, compiled with gcc -O2. The formula used is the following:

This can be derived directly from the Leibniz Series, as can be seen elsewhere. Standard long division is used, in base 1000000000 rather than base 10, storing the remainders for each division in an array.
The algorithm is quadratic: 10000 digits takes ~0.35s, 100000 takes ~35s, etc (10 times as many takes 100 times as long). I estimate that all 13000000 will take approximately 6d 20h 18m, give or take, using a constant 170MB of memory.

What are you talking about?? Your source is only around 300, not THIRTEEN MILLION

@ChristopherWirt This is the number of digits I estimate this program could produce in 7 days time.

C# - 412 394 chars, 3000 digits, 7 seconds
I wrote this program myself, except for the square root function.
It calculates π using the Chudnovsky formula and uses the .Net BigInteger class for fixed-point math.

using B=System.Numerics.BigInteger;class M{static void Main(){B f=B.Pow(10,3000);B z=0;for(int k=0;k<220;k++)z+=f*F(6*k)*(13591409+545140134*new B(k))/(F(3*k)*B.Pow(F(k),3)*B.Pow(-640320,3*k));System.Console.WriteLine(f*f/(12*z*f/S(B.Pow(640320,3)*f*f)));}static B F(B N){return(N.Sign>0)?N*F(N-1):1;}static B S(B N){if(0==N)return 0;B o=(N>>1)+1;for(B a=o+N/o>>1;a>1)o=a;return o;}}

With some extra white space:

using B=System.Numerics.BigInteger;
class M{
static void Main(){
B f=B.Pow(10,3000);
B z=0;
for(int k=0;k<220;k++)
z+=f*F(6*k)*(13591409+545140134*new B(k))/(F(3*k)*B.Pow(F(k),3)*B.Pow(-640320,3*k));
System.Console.WriteLine(f*f/(12*z*f/S(B.Pow(640320,3)*f*f)));
}
static B F(B N){return(N.Sign>0)?N*F(N-1):1;}
static B S(B N){if(0==N)return 0;B o=(N>>1)+1;for(B a=o+N/o>>1;a>1)o=a;return o;}}

The Main function calculates Pi, and the other 2 functions are (respectively) Factorial and Square Root.
The number of digits (3000) can be changed in the Main function, just be sure to change the number of Chudnovsky terms (220) to match, otherwise some digits will be incorrect.
It takes about 7 seconds to run on my computer right now.


text:
Optimal Minesweeper on the Largest Board
Overview:
Your challenge is to write a program that will play minesweeper optimally, giving the best move in any position. Moreover, you must do this on the largest board possible.
Game details: Minesweeper is a one player game, played on a rectangular board. At the beginning of the game, a specified number of mines are randomly distributed over the board, at most one to a cell. Each possible placement of the mines is equally likely. The mines' positions are hidden from the player.
On each of the player's turns, he or she chooses a square on the board to reveal. If the square contains a mine, the player loses the game. Otherwise, the number of mines in Moore neighborhood of the chosen square (orthogonally or diagonally adjacent) is revealed to the player.
The player repeats this until either a mine is revealed, or the number of unrevealed squares is equal to the number of mines. If the latter occurs, the player wins.
Program specification: Your program must take as input a board position, which should specify the locations and values of the revealed and unrevealed squares, as well as the number of mines on the board. It must return at least one move which has a maximal likelihood of winning if followed by optimal play. Returning more moves is allowed, as long as they all have the same, maximal, win rate.
In addition, the program must return the maximal number of possibilities that can be won under optimal play and the total number of possibilities for this revealed board state. From these values, the exact probability of winning under optimal play is known.
Examples:
Input (in any format you prefer):
4 mines
____
____
____
____

Output:
Best moves are [(0, 1), (0, 2), (1, 0), (1, 3), (2, 0), (2, 3), (3, 1), (3, 2)].
961 wins out of 1820 possibilities.

Input:
5 mines
_____
_1___
_3___
_____

Output:
Best moves are [(0, 2)].
285 wins out of 360 possibilities.

Challenge specification: Your challenge is to run your program on the initial position of a board of one of the following types:

n x n board, n mines.
n x n+1 board, n mines.
n x n+1 board, n+1 mines.

Your program must find an optimal move on your machine at least as fast as the reference implementation solves the 4x5 board, 5 mines case on your machine. That case takes 6 minutes on my computer, for reference.
To run that instance of the reference implementation with timing, run python3 Minesweeper-challenge.py <<< "(4,5), 5, '____________________'"
The program that correctly identifies the optimal moves and exact number of possibilities that can be won with perfect play, on the initial position of the largest board of the above type, tiebreaker most mines, in the given time limit, wins the contest.
I will select a winner in two weeks, on July 24th.
Since writing a program like this is a big task, I will be awarding a bounty of 150 reputation, starting tomorrow and ending on the 18th.
Edit/bump: Well, that was a waste of 250 rep.

I think that this is almost a duplicate of http://codegolf.stackexchange.com/questions/24118/minesweeper-solver - at least the only solution there shows what you are asking for.

@Howard I disagree. That's a code golf, this is a code challenge. That's a very important difference. In addition, that challenge merely specified minimal likelihood of immediately hitting a mine, instead of the maximal probability of winning the game, which is a much different challenge.

If you're asking for the perfect solution, why should you have any say in who the winner is? "Oh, Ye110wD*ck solution is more perfect than Howard..." Ludicrous.

@AndoDaan Have you noticed the tags? It's fastest code. I'm a sure that many people will get the optimal solution, it's who can do that faster that matters. I will edit the intro paragraph to make that more clear.

Downvoters: Please comment on what you think is wrong, if you think it can be improved.

Three days to collect the bounty - any answer will win, just submit something!

Python, 4x5 board, 5 mines.
This is the reference implementation, I just thought I'd put it here to help give people ideas.
This implementation uses dynamic programming to prevent duplication of work, exploits mirror symmetries, and maintains a fist of all possible boards with a given revealed square status to check for guaranteed safe squares.
# Minesweeper solver
# Class just contains partially revealed boards that all look the same
# from the outside

# This is a branch, that uses strings.

# Boards have every cell revealed.
# Revealed is partially revealed. Boards must match revealed on every
# cell that is revealed.

# Meanings:
# '0'-'8': Safe square with that # of surrounding mines
# '*'    : Mine
# '_'    : Unrevealed
import copy
import itertools
import time
import pickle
import random
import math
import cProfile
import sys

class Position:
    def __init__(self, dimensions, revealed, boards):
        self.dim_r,self.dim_c=dimensions
        self.rev=revealed
        self.boards=boards
        assert len(revealed)==self.dim_r*self.dim_c

    def click(self,loc):
        # Takes a location, returns all possible revealed positions, with boards
        # split up accordingly
        try:
            assert self.rev[loc]=='_'
        except AssertionError:
            print(self,loc,self.rev)
            assert self.rev[loc]=='_'
        # Create all possible new boards, split up by revealed item.
        board_dict={}
        for board in self.boards:
            clicked_cell=board[loc]
            if clicked_cell in board_dict:
                board_dict[clicked_cell].append(board)
            else:
                board_dict[clicked_cell]=[board]
        new_positions=[]
        for rev_cell in board_dict.keys():
            # Make the new board without copying
            new_rev=''.join([self.rev[:loc],rev_cell,self.rev[loc+1:]])
                new_pos=Position((self.dim_r,self.dim_c),new_rev,board_dict[rev_cell])
            new_positions.append(new_pos)
        return new_positions

    def someBestClick(self):
        click_list=[]
        # Set of boards is all we know when outputting, may be smaller than
        # complete set
        # If we've clicked on a bomb, no way to win, no best click.
        if '*' in self.rev:
            return 0,[]
        unrevealed = [loc for loc in range(len(self.rev)) if self.rev[loc]=='_']
        # If there is only 1 possible board, you're done. The click list is every
        # unrevealed square on the board without a bomb under it.
        if len(self.boards)==1:
            return 1,[loc for loc in unrevealed if self.boards[0][loc]!='*']

        # If there is an unrevaled locaiton on the board that is bomb free in
        # every sub-board, use it.
        for loc in unrevealed:
            if all(board[loc]!='*' for board in self.boards):
                return sum(pos.memoBestClick()[0] for pos in self.click(loc)),[loc]

        # The broadest test - try everywhere.
        click_list=[]
        most_wins=0
        for loc in unrevealed:
            wins=sum(pos.memoBestClick()[0] for pos in self.click(loc) if pos.rev[loc]!='*')
            if wins>=most_wins:
                if wins>most_wins:
                    click_list=[]
                    most_wins=wins
                click_list.append(loc)
        return most_wins,click_list

    def memoBestClick(self):
        global memo
        global memo_counter
        memo_counter +=1
        if not self.rev in memo:
            # These lines check for mirror images of the board being in the memo table

            vert_reversed_memo_str=                                         \
            ''.join([self.rev[y*self.dim_c:(y+1)*self.dim_c]
                     for y in range(self.dim_r)][::-1])

            if vert_reversed_memo_str in memo:
                vert_reversed_output=memo[vert_reversed_memo_str]
                return vert_reversed_output[0],                             \
                        [(self.dim_r-1-loc//self.dim_c)*self.dim_c+loc%self.dim_c
                         for loc in vert_reversed_output[1]]

            horiz_reversed_memo_str=                                        \
            ''.join(self.rev[y*self.dim_c:(y+1)*self.dim_c][::-1]
                    for y in range(self.dim_r))

            if horiz_reversed_memo_str in memo:
                horiz_reversed_output=memo[horiz_reversed_memo_str]
                return horiz_reversed_output[0],                            \
                        [(loc//self.dim_c)*self.dim_c+
            both_reversed_memo_str=self.rev[::-1]
            if both_reversed_memo_str in memo:
                both_reversed_output=memo[both_reversed_memo_str]
                return both_reversed_output[0],                             \
                        [len(self.rev)-1-loc
                         for loc in both_reversed_output[1]]

            global restart_counter
            global restart_memo

            if len(self.rev)-self.rev.count('_') <= restart_max:
                restart_memo[self.rev]=self.someBestClick()
                memo[self.rev]=restart_memo[self.rev]
                return restart_memo[self.rev]
            # Needed because of memory issues
            if len(memo)>5*10**6:
                memo=copy.deepcopy(restart_memo)
                restart_counter+=1
            memo[self.rev]=self.someBestClick()
        return memo[self.rev]

def makeBlankPosition(dimensions,mines):
    dim_r,dim_c=dimensions
    # Makes all locations on the board
    all_loc=itertools.product(range(dim_c),range(dim_r))
    # Makes all possible distributions of mines
    all_mine_layouts=itertools.combinations(all_loc,mines)
    boards=[]
    for mine_layout in all_mine_layouts:
        boards.append(makeBoardFromMines(dimensions,mine_layout))
    return Position(dimensions, '_'*dim_c*dim_r, boards)

def makeBoardFromMines(dimensions,mine_layout):
    dim_r,dim_c=dimensions
    def mineNum(loc):
        if (loc%dim_c,loc//dim_c) in mine_layout:
            return '*'
        return str(sum(((loc%dim_c+dif[0],loc//dim_c+dif[1]) in mine_layout) for dif in
                   [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]))
    return ''.join(map(mineNum,(loc for loc in range(dim_r*dim_c))))

def makePosition(dimensions,mines,revealed):
    blank_pos=makeBlankPosition(dimensions,mines)
    boards_subset=[]
    for board in blank_pos.boards:
        if all(revealed[cell_num]==board[cell_num] or revealed[cell_num]=='_' for cell_num in range(len(board))):
            boards_subset.append(board)
    return Position(dimensions, revealed, boards_subset)

def winRate(dimensions,mines,revealed):
    pos=makePosition(dimensions,mines,revealed)
    global memo
    memo={}
    wins=pos.memoBestClick()
    return wins[0],len(pos.boards),wins[1],memo

global memo_counter
memo_counter=0
global restart_counter
restart_counter=0
global restart_memo
restart_memo={}
global restart_max
restart_max=6
dimensions, mines, revealed = eval(input())
start_time=time.clock()
wins, total_boards, moves, memo = winRate(dimensions, mines, revealed)
move_points=[(move//dimensions[1],move%dimensions[1]) for move in moves]
print("""Best moves are %s.\n%i wins out of %i boards. Ratio of %f. %i
positions searched.\n%f seconds taken."""%(move_points, wins, total_boards,
wins/total_boards, len(memo),time.clock()-start_time))


text:
Introspective Programming: Code that analyzes its source and its output
Write a program that outputs the total number of characters and the frequency of each character in its source and its output. You must follow the format illustrated in the example.
Example
If your code was
abb1

Its output would have to be
My source has 4 characters.
1 is "a"
2 are "b"
1 is "1"
Besides unquoted numbers, my output has 383 characters.
34 are "
"
79 are " "
63 are """
2 are "'"
2 are ","
4 are "."
2 are "1"
2 are "B"
2 are "I"
2 are "M"
39 are "a"
4 are "b"
6 are "c"
4 are "d"
38 are "e"
3 are "g"
5 are "h"
4 are "i"
4 are "m"
3 are "n"
8 are "o"
3 are "p"
2 are "q"
38 are "r"
12 are "s"
8 are "t"
7 are "u"
3 are "y"
It's good to be a program.

(Output must go to stdout.)
Notice, for example, that the output contains two capitalized m's. One for My and one for 2 are "M". This must hold true for all characters so the output does not contradict itself in any way.
Unquoted numbers are ignored in the output to avoid unsatisfiable frequency sets. For example, 1 is "1" is incorrect if both 1's are counted. It should read 2 are "1", but then there is only one 1 again.
Format Clarifications

"is" must be used for single character occurrences.
"are" must be used for multiple character occurrences.
"is" should never appear in the list of output characters because it would be superfluous. 1 is 'Z' refers to the Z in itself, so the entire line can be removed.
The three full-sentence phrases must appear in order with the character frequency lists in between (as the example shows). So your output will start with My source... and end with ...be a program.. Note that there is no newline at the end of the output.
The character frequency lists themselves may be in any order.
Newlines count as one character (in case they are \r\n).

Format Checker
The following Python script takes your code and its output as strings and asserts that the output has no contradictions. It provides a useful error message if something is wrong. You can run it online at http://ideone.com/6H0ldu by forking it, replacing the CODE and OUTPUT strings, then running it. It will never give false positives or negatives (assuming its error free).
#Change the CODE and OUTPUT strings to test your program

CODE = r'''abb1'''

OUTPUT = r'''My source has 4 characters.
1 is "a"
2 are "b"
1 is "1"
Besides unquoted numbers, my output has 383 characters.
34 are "
"
79 are " "
63 are """
2 are "'"
2 are ","
4 are "."
2 are "1"
2 are "B"
2 are "I"
2 are "M"
39 are "a"
4 are "b"
6 are "c"
4 are "d"
38 are "e"
3 are "g"
5 are "h"
4 are "i"
4 are "m"
3 are "n"
8 are "o"
3 are "p"
2 are "q"
38 are "r"
12 are "s"
8 are "t"
7 are "u"
3 are "y"
It's good to be a program.'''

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

import re

amountPattern = r'(\d+) (is|are) "(.)"\n'

class IntrospectionException(Exception):
    pass

def getClaimedAmounts(string, errorOnIs):
    groups = re.findall(amountPattern, string, re.DOTALL)

    for amount, verb, char in groups:
        if verb == 'is':
            if errorOnIs:
                raise IntrospectionException('\'1 is "%s"\' is unnecessary' % char)
            elif amount != '1':
                raise IntrospectionException('At "%s", %s must use "are"' % (char, amount))
        elif verb == 'are' and amount == '1':
            raise IntrospectionException('At "%s", 1 must use "is"' % char)

    amounts = {}
    for amount, verb, char in groups:
        if char in amounts:
            raise IntrospectionException('Duplicate "%s" found' % char)
        amounts[char] = int(amount)
    return amounts

def getActualAmounts(string):
    amounts = {}
    for char in string:
        if char in amounts:
            amounts[char] += 1
        else:
            amounts[char] = 1
    return amounts

def compareAmounts(claimed, actual):
    for char in actual:
        if char not in claimed:
            raise IntrospectionException('The amounts list is missing "%s"' % char)
    for char in actual: #loop separately so missing character errors are all found first
        if claimed[char] != actual[char]:
            raise IntrospectionException('The amount of "%s" characters is %d, not %d' % (char, actual[char], claimed[char]))
    if claimed != actual:
        raise IntrospectionException('The amounts are somehow incorrect')

def isCorrect(code, output):
    p1 = r'^My source has (\d+) characters\.\n'
    p2 = r'Besides unquoted numbers, my output has (\d+) characters\.\n'
    p3 = r"It's good to be a program\.$"
    p4 = '%s(%s)*%s(%s)*%s' % (p1, amountPattern, p2, amountPattern, p3)

    for p in [p1, p2, p3, p4]:
        if re.search(p, output, re.DOTALL) == None:
            raise IntrospectionException('Did not match the regex "%s"' % p)

    claimedCodeSize = int(re.search(p1, output).groups()[0])
    actualCodeSize = len(code)
    if claimedCodeSize != actualCodeSize:
        raise IntrospectionException('The code length is %d, not %d' % (actualCodeSize, claimedCodeSize))

    filteredOutput = re.sub(r'([^"])\d+([^"])', r'\1\2', output)

    claimedOutputSize = int(re.search(p2, output).groups()[0])
    actualOutputSize = len(filteredOutput)
    if claimedOutputSize != actualOutputSize:
        raise IntrospectionException('The output length (excluding unquoted numbers) is %d, not %d' % (actualOutputSize, claimedOutputSize))

    splitIndex = re.search(p2, output).start()

    claimedCodeAmounts = getClaimedAmounts(output[:splitIndex], False)
    actualCodeAmounts = getActualAmounts(code)
    compareAmounts(claimedCodeAmounts, actualCodeAmounts)

    claimedOutputAmounts = getClaimedAmounts(output[splitIndex:], True)
    actualOutputAmounts = getActualAmounts(filteredOutput)
    compareAmounts(claimedOutputAmounts, actualOutputAmounts)

def checkCorrectness():
    try:
        isCorrect(CODE, OUTPUT)
        print 'Everything is correct!'
    except IntrospectionException as e:
        print 'Failed: %s.' % e

checkCorrectness()

Scoring
This is code-golf. The submission with the fewest characters wins. Submissions must pass the format checker to be valid. Standard loopholes apply, though you may read your own source code and/or hardcode your output.

Is reading your own source file allowed?

@MrLore There may be other errors but I just realized that the triple quotes (''') still escapes things with backslash. This may be related to your problem. I'm fixing it now.

@Ventero Definitely!

@MrLore The regexps allow some false positives, yes. To fix the problem with backslashes inside triple quotes, use raw strings (r'''CODE''').

@Calvin'sHobbies Meh. Could've saved a lot of effort then. Since you have tagged this as [tag:quine], I figured the somewhat-standard quine loophole wouldn't be allowed.

Sorry about that. I imagined that even with reading your own source the task is still fairly tricky.

@MrLore Fixed unescaped dots. Thanks for noticing!

"Besides unquoted numbers..." So we're playing on easy mode, huh?

if the program outputs something related to its output, that's recursive. How can we avoid infinite output?

@xem Well for one thing Ventero already proved it was possible. Also, for every unique character in the output (or code) the output can only increase by 10 characters (11 counting the output size going from 95 to 105, for example). There aren't infinitely many unique characters.

Does the program have to analyze its own source and output, or can it just output the right stuff (with some hardcoding)?

@aditsu Hardcoding things is fine.

CJam - 189
{`"_~"+:T;"Besides unquoted numbers, my output has &It's good to be a program.&My source has & characters.
"'&/~_]:X2=T,X3=3i({T_&:B{TI/,(" are ":AM`I*N}fIXK=]o
XBA`N+f+2*+s:T,X3=}fK'q];}_~

Try it at http://cjam.aditsu.net/
Output:
My source has 189 characters.
3 are "{"
3 are "`"
6 are """
4 are "_"
3 are "~"
4 are "+"
5 are ":"
5 are "T"
2 are ";"
3 are "B"
8 are "e"
9 are "s"
2 are "i"
3 are "d"
17 are " "
6 are "u"
2 are "n"
2 are "q"
8 are "o"
6 are "t"
3 are "m"
2 are "b"
7 are "r"
4 are ","
2 are "y"
2 are "p"
3 are "h"
7 are "a"
5 are "&"
4 are "I"
3 are "'"
2 are "g"
2 are "."
2 are "M"
3 are "c"
2 are "
"
2 are "/"
3 are "]"
5 are "X"
2 are "2"
4 are "="
3 are "3"
2 are "("
2 are "A"
2 are "*"
2 are "N"
3 are "}"
3 are "f"
2 are "K"
Besides unquoted numbers, my output has 988 characters.
3 are "B"
108 are "e"
11 are "s"
3 are "i"
5 are "d"
214 are " "
8 are "u"
4 are "n"
3 are "q"
9 are "o"
9 are "t"
5 are "m"
4 are "b"
108 are "r"
3 are ","
4 are "y"
4 are "p"
6 are "h"
108 are "a"
3 are "I"
3 are "'"
4 are "g"
5 are "."
3 are "M"
7 are "c"
102 are "
"
2 are "{"
198 are """
2 are "`"
2 are "_"
2 are "~"
2 are "+"
2 are ":"
2 are "T"
2 are ";"
2 are "&"
2 are "/"
2 are "]"
2 are "X"
2 are "2"
2 are "="
2 are "3"
2 are "("
2 are "A"
2 are "*"
2 are "N"
2 are "}"
2 are "f"
2 are "K"
It's good to be a program.

Ruby, 269 (311, 367) characters
I have three different solutions for this challenge. Each of them uses a different set of tricks:
"Proper" solution, 367 characters:
The longest solution is more or less just a proof of concept that it's possible to solve this challenge without any tricks - and is not nearly fully golfed. It's a true quine (i.e. it generates its own source code instead of reading it from a file) and actually calculates all the numbers it prints (code length, output length, character occurences). Due to the way the quine works, all the code has to be on a single line and inside a string literal.
eval r="S='eval r=%p'%r;O=-~$.;q=\"My source has \#{S.size}\"+(X=' characters.\n')+S.chars.uniq.map{|c|[k=S.count(c),k>O ? :are: :is,?\"+c+?\"]*' '}*$/+'\nBesides unquoted numbers, my output has ';r=(w=q+X+s=\"It's good to be a program.\").scan(D=/\\D/).uniq;$><<q<<(w+v=r.map{|c|j=' are \"\n\"';(-~(w+j*r.size).count(c)).to_s+(j[~O]=c;j)}*$/+$/).scan(D).size<<X+v+s"

Partially hardcoded output, 311 characters:
The next shortest solution uses two tricks, but is still a true quine:
 - No character occurs exactly once in the source code. That way, I don't need to decide whether I should print is or are in the first half of the output. It also makes it a bit easier to calculate the total output size (though I don't actually need to do that).
 - The total output size is hardcoded. Since this only depends on the number of distinct characters in the source code (and in the general case, how many of those characters occur only once), it's easily to calculate it in advance.
Note that the code is preceeded by two very significant newlines, which StackExchange wouldn't show in the code block. For that reason, I have added an additional line in front if those newlines, which is not part of the code.
#

eval R="I=$/+$/+'eval R=%p'%R;?\\4>w='%d are \"%s\"';B=\"My source has \#{I.size}\#{X=\" characters.\n\"}\#{z=(m=I.chars.uniq).map{|x|w%[I.count(x),x]}*$/}\nBesides unquoted numbers, my output has 1114\"+X;$><<B+m.map{|c|w%[(B+z+$M=\"\nIt's good to be a program.\").gsub!(/\\d++(?!\")/,'').count(c),c]}*$/+$M"

Shortest solution, 269 characters:
The shortest solution additionally hardcodes its own source length. By using variable names that are/aren't already part of the source code, it's possible to find a "fixpoint" where all characters in the source code (including the digits from the hardcoded lengths!) occur at least twice.
This solution also saves a few more characters by simply reading its own source code from the code file, instead of generating it. As a nice side effect, this makes the code much more "readable" (but who cares about readable code in a code-golf ...), as now the code doesn't have to be inside a string literal anymore.
U='%d are "%s"'
O=IO.read$0
?\126>B="My source has 269#{X=" characters.
"}#{z=(m=O.chars.uniq).map{|c|U%[O.count(c),c]}*$/}
Besides unquoted numbers, my output has 1096"+X
$><<B+m.map{|c|U%[(B+z+$M="
It's good to be a program.").gsub!(/\d++(?!")/,"").count(c),c]}*$/+$M

I also modified the test script a little bit to reduce the copy-pasting necessary to check the code. By replacing the definitions of CODE and OUTPUT with
import subprocess

CODE = open("packed.rb").read()
OUTPUT = subprocess.check_output(["ruby", "packed.rb"])

print CODE
print len(CODE)

the script now automatically runs my code, reads its output, and grabs the source code from the code file.

Here's the output generated by the shortest code:
My source has 269 characters.
3 are "U"
7 are "="
3 are "'"
4 are "%"
6 are "d"
17 are " "
11 are "a"
9 are "r"
9 are "e"
11 are """
11 are "s"
6 are "
"
4 are "O"
2 are "I"
10 are "."
6 are "$"
2 are "0"
2 are "?"
2 are "\"
2 are "1"
2 are "2"
3 are "6"
2 are ">"
4 are "B"
3 are "M"
2 are "y"
9 are "o"
10 are "u"
12 are "c"
4 are "h"
2 are "9"
2 are "#"
4 are "{"
2 are "X"
8 are "t"
4 are "}"
2 are "z"
6 are "("
7 are "m"
5 are "n"
2 are "i"
2 are "q"
6 are ")"
4 are "p"
4 are "|"
2 are "["
4 are ","
2 are "]"
2 are "*"
4 are "/"
3 are "b"
7 are "+"
2 are "<"
3 are "g"
2 are "!"
Besides unquoted numbers, my output has 1096 characters.
2 are "U"
2 are "="
3 are "'"
2 are "%"
5 are "d"
238 are " "
120 are "a"
120 are "r"
120 are "e"
222 are """
11 are "s"
114 are "
"
2 are "O"
3 are "I"
5 are "."
2 are "$"
2 are "0"
2 are "?"
2 are "\"
2 are "1"
2 are "2"
2 are "6"
2 are ">"
3 are "B"
3 are "M"
4 are "y"
9 are "o"
8 are "u"
7 are "c"
6 are "h"
2 are "9"
2 are "#"
2 are "{"
2 are "X"
9 are "t"
2 are "}"
2 are "z"
2 are "("
5 are "m"
4 are "n"
3 are "i"
3 are "q"
2 are ")"
4 are "p"
2 are "|"
2 are "["
3 are ","
2 are "]"
2 are "*"
2 are "/"
4 are "b"
2 are "+"
2 are "<"
4 are "g"
2 are "!"
It's good to be a program.

Could you post a definitive copy of your code and output so I can easily test it? The code should not output itself and the output should end in a period not a newline.

@Calvin'sHobbies The first code block is my actual code. It does print the output with a final newline though, so give me a few minutes to fix that (this is something that you should definitely mention in the spec).

Sure thing, I just updated the spec.

@Calvin'sHobbies Done. First code block is the actual code which is generated by the second code block (so that I don't have to take care of string escaping and everything while writing the code).


text:
Build a MU puzzle solver
The MU puzzle is a puzzle in which you find out whether you can turn MI into MU given the following operations:

If your string ends in I, you may add a U to the end. (e.g. MI -> MIU)
If your string begins with M, you may append a copy of the part after M to the string.
(e.g. MII -> MIIII)
If your string contains three consecutive I's, you may change them into a U.
(e.g. MIII -> MU)
If your string contains two consecutive U's, you may delete them. (e.g. MUUU -> MU).

Your task is to build a program that determines whether this is doable for any start and finish strings.
Your program will take two strings as input. Each string will consist of the following:

one M.
a string of up to twenty-nine I's and U's.

Your program will then return true (or your programming language's representation thereof/YPLRT) if the second string is reachable from the first string, and false (or YPLRT) if it is not.
Example inputs and outputs:
MI  MII
true

MI  MU
false

MIIIIU  MI
true

The shortest code in any language to do this wins.

I'm currently reading Gödel, Escher, Bach and thought about doing an "18-hole golf course"based on its chapters afterwards. Guess I've got to find a new "hole 1" now. ;)

This is just a graph reachability question whose essence has been asked plenty of times before.

@PeterTaylor I think there's a good chance this won't be solved by an explicit search of the reachability graph. The MIU rules have a lot of structure, and I wouldn't be surprised if there's a direct algorithm to test for reachability without searching for intermediate nodes. For example, the nodes reachable from MI are exactly the M(I|U)* where the number of I isn't a multiple of 3. And such a direct check surely makes for shorter code. Also, I don't know of an a-priori bound on the lengths of strings required for intermediate steps, so direct search might be simply impractical.

@xnor, on the other hand it's an instance of a Turing-complete system, so explicit search of the reachability graph may be the only approach that works in the general case.

@PeterTaylor Oh, it's Turing complete? I don't remember that from GEB. Can you please point me to a proof?

@xnor, I said "an instance of a Turing-complete system". Specifically, it's a Post canonical system.

@PeterTaylor Oh, I see. I guess then the question remains whether there's a problem-specific method. I haven't found one but I hope someone will.

@PeterTaylor I understand what you mean about the reachability graph, but as xnor said, I'm looking to see whether there are any solutions that are shorter that do something else.

I've thought about this problem for a while and haven't gotten close to a solution that isn't brute-force. If nobody bites, I suggest posting an easier version of the question, perhaps to give a derivation starting from MI of a given reachable string.

"The puzzle's solution is no. It is impossible to change the string MI into MU by repeatedly applying the given rules." So the program returns false whatever the input?

No, the program's input isn't just for MI to MU. I could be from MIIIIUIUIUIUUIUIUUIUU to MUIUUUIUIUUUIIIIIUIUI, for instance.

What should the output be if IM is supplied or MUMMI?

You can assume that input will be valid.

Since both start and end strings can be up to 30 characters, is there a limit on the length of a required intermediate string? For example, could a starting string of length 30 require being doubled a couple times right away to reach the ending string (thus reaching length 120)?

No, there shouldn't be a limit on that.

SWI Prolog, 183 characters
m(A,A).
m([i],[i,u]).
m([i,i,i|T],B):-m([u|T],B).
m([u,u|T],B):-m(T,B).
n([m|A],[m|B]):-(m(A,B);append(A,A,X),m(X,B)).
n(A,B):-m(A,B).
s(A,B):-atom_chars(A,X),atom_chars(B,Y),n(X,Y).

How about some Prolog, (since nobody has answered in 6 months).
To run, just use "s(mi,mu)."  The code breaks up atoms into chars, then searches for the solution.

This wrongfully returns false on s(mi,miiii), and in general anything requiring more than one application of rule 2 to prove.