text:
Grid Based Digital Logic (Duodyadic Tiles)
Duodyadic tiles are kinds of square function blocks that take two inputs, one from their top side and one from their left side, and have two outputs, one on their right side and one on their bottom side. Each of their outputs is a separate function of both of their inputs.
For example, if # represents a generic tile, the right output R is a function f of inputs T and L, and the bottom output B is another function g of T and L:
 T
L#R         R = f(T, L)
 B          B = g(T, L)

(The tiles are termed "duo" since there are two functions, and "dyadic" since both functions have two arguments.)
Tiles can then be composed together on a grid, the outputs of one tile going directly into the inputs of the tiles it neighbors. Here for example, the right output of the left # goes into the left input of the right #:
 AB         D = f(f(A, C), B)
C##D        E = g(A, C)
 EF         F = g(f(A, C), B)

You can imagine that given a set of duodyadic tiles, each with specific functionality, complex (and potentially useful) compositions could be made.
In this challenge, we'll only be concerned with the traditional set of ten logic based duodyadic tiles, where all the inputs and outputs are single-bit binary numbers (zeros or ones). We'll use a separate ASCII character to denote each type of tile.
The tile characters and their input-output relations are as follows:
(T is for top input, L for left input, R for right output, B for bottom output.)

Zero: 0 or   (space) → R = 0, B = 0
One: 1 → R = 1, B = 1
Cross: + → R = L, B = T
Mirror: \ → R = T, B = L
Top only: U → R = T, B = T
Left only: ) → R = L, B = L
Not: ! → R = not L, B = not T
And: & → R = L and T, B = L and T
Or: | → R = L or T, B = L or T
Xor: ^ → R = L xor T, B = L xor T

Challenge
Write a program or function that takes in a rectangular grid of the characters 0 1+\U)!&|^ that represents a "circuit" made using the ten logic based duodyadic tiles. You also need to take in two strings of 0's and 1's; one will be the left input column and one will be the top input row. Your program/function needs to print/return the bottom output row and the right output column (also in 0's and 1's).
For example, in this grid
+++
+++

all the inputs flow straight across the grid to the outputs
 ABC
D+++D
E+++E
 ABC

so an input of 010/01 would have output 010/01:
 010
0+++0
1+++1
 010

The exact output of your program would be [bottom output row]\n[right output column] or [bottom output row]/[right output column]:
010
01

or
010/01

If you wrote a function, you could return the two strings in a tuple or list (or still print them).
Details

Take the three inputs as strings in any reasonable manner (preferably in the order grid, top row, left column): command line, text file, sdtin, function arg.
You can assume the input row and column lengths will match the grid dimensions and will only contain 0's and 1's.
Your grid must use the proper characters (0 1+\U)!&|^). Remember that 0 and   mean the same thing.

Test Cases
(Read I/O as top/left → bottom/right.)
Nand:
&!

00/0 → 01/1
00/1 → 01/1
10/0 → 01/1
10/1 → 11/0
All ones:
1111
1\+\
1+\+
1\+\

Any input should result in 1111/1111.
Xor from Nand: (note the column of trailing spaces)
\)+\
U&!&
+! !
\&!&
   !

00000/00000 → 00000/00000
00000/10000 → 00010/00000
10000/00000 → 00010/00000
10000/10000 → 00000/00000
Zig zag:
+++\00000000
000\!!!!\000
00000000\+++

The first bit of the left input becomes the last bit of the right output. Everything else is 0.
000000000000/000 → 000000000000/000
000000000000/100 → 000000000000/001
Propagation:
)))
UUU
U+U
U+U
UUU

The first bit of the left input goes to all the outputs.
000/00000 → 000/00000
000/10000 → 111/11111
Here's a pastebin of all 1×1 grid test cases.
Scoring
The shortest submission in bytes wins.
Bonus: What cool "circuits" can you make?
P.S. Don't bother Googling "duodyadic tiles". I made them up yesterday ;D
If you want to discuss expanding this idea into a full-fledged programming language, come to this chatroom.

+1 for a cool challenge but also because you invented duodyadic tiles, which is REALLY cool.

+1 It really is completely useless to google this: http://goo.gl/zuqfdW. Nice challenge!

I'm with them. I'm much more interested in your tiles as a programming language than in this particular golf challenge. PS: There are 16 possible tiles, so coming up with letters/names for the other six would be neat.

It'd be interesting to have blocks which output/input from different directions, because otherwise you can't make a latch since everything flows in a down-right direction.

@Sp3000/Sparr I agree. I was trying to keep things simple for the challenge but modifying this idea to be a kind pf programming language would be cool. I suppose they could still be "duodyadic" if they had 2 inputs and 2 outputs in any directions, allowing loops/memory. It'd also be more useful as a language if things weren't all binary.

@Sparr, there are 256 possible tiles, because there are 16 possible binary functions on 2 variables.

It would be good to have a test case for a board which is much wider than it is high, and one for a board which is much higher than it is wide.

You could change T/B to U(p)/D(own), so that we could have F/B in an analogous way to Rubik's Cube notation, and then . . . tritriadic cubes?

I stand corrected.

Pyth, 122
Kind of a monster. Uses simply recursion, nothing fancy like dynamic programming.
D:NGHR@Cm+d[1HG&GH|GHxGH0),[GH!G)[HG!H)x"+\\!1U)&|^"N#aYw)M:@@YGH?hgGtHHv@eYG?egtGHGv@ePYHjkm+0egtleYklePYjkm+0hgbtlePYleY

Online demonstration.
Input is in the following way: First the grid (no escaping, no extra symbols) and then the two lines of input, e.g. (Zig zag)
+++\00000000
000\!!!!\000
00000000\+++
000000000000
100

C, 332 309 272 270 266 259 247 225 bytes
#define C(x)*c-x?
i,k,T,L,m;f(c,t,l)char*c,*t,*l;{while(L=l[i]){for(k=0;T=t[k];c++)L=C(49)C(43)C(92)C(85)C(41)C(33)C(38)C('|')C(94)T=48:(T^=L-48):(T|=L):(T&=L):(T^=1,L^1):(T=L):T:(m=T,T=L,m):L:(T=49),t[k++]=T;c++;l[i++]=L;}}

View results online here!
This defines a function void f(char*, char*, char*), which should take the board as its first input, then the top row of input, and then the left row of input.
Here's what I used to test it:
#include "stdio.h"
int main() {
    char buf[1024],top[33],left[33];
    /* Copy and paste an example circuit as the first input,
       and put a 'Q' immediately after it.
       Note that the Q is never touched by the function f, and is used
       solely as a delimiter for input. */
    scanf("%[^Q]Q ",buf);
    /* Then enter your top inputs */
    scanf("%[01]%*[^01]", top);
    /* Then your left ones */
    scanf("%[01]", left);
    /* OUTPUT: Bottom\nRight */
    f(buf, top, left);
    return 0;
}

Thus, by inputting Sp3000's 2-bit multiplier:
UUUU))))
UU++)))&
UUU+)  U
UU++&))U
U++&+)^U
U)&\&)UU
   U+^UU
   \&UUUQ
11110000
00000000

We get:
00001001
11111111

On another note, with Sp3000's half adder in mind, I'd like to see a full adder... One of you guys did it! I don't think the system stands on its own as a programming language, but it's been very interesting. This seems like an excellent target for metagolf, though!
A Short Explanation:
Here's the unraveled, commented code:
/* We define the first half of the ?: conditional operator because, well,
   it appears over and over again. */
#define C(x)*c-x?
/* i,k are counting variables
   T,L are *current* top and left inputs */
i,k,T,L,m;
f(c,t,l)char*c,*t,*l;{
    /* The outer loop iterates from top to bottom over l and c */
    while(L=l[i]){
        /* Inner loop iterates from left to right over t and c */
        for(k=0;T=t[k];c++)
            /* This line looks awful, but it's just a bunch of character
            comparisons, and sets T and L to the output of the current c */
            L=C(49)C(43)C(92)C(85)C(41)C(33)C(38)C('|')C(94)T=48:(T^=L-48):(T|=L):(T&=L):(T^=1,L^1):(T=L):T:(m=T,T=L,m):L:(T=49),
            /* Write our output to our input, it will be used for the next row */
            t[k++]=T;
        c++; /*Absorbs the newline at the end of every row */
        /* Keep track of our right-most outputs,
        and store them in the handy string passed to the function. */
        l[i++]=L;
    }
    /* Bottom output is now stored entirely in t, as is right output in l */
}

We iterate over c, left to right (then top to bottom), rewriting the t inputs each time and pushing out a right-most output which is shoved into the l string. We can imagine this as replacing the top row of c with 1's and 0's iteratively, and keeping track of the bits that are pushed out at the right.
Here's a more visual sequence, row by row:
 111
1&+^  =>  110 ->0  =>     ->0  =>     0 Thus, "01" has been written to l,
1+&+     1+&+         110 ->1         1
                                  110   And "110" is stored currently in t.

This obviously gets more complicated with different symbols and sizes, but the central idea holds. This works only because data never flows up or left.

A lot of potential for golfing! Start by changing the header of f to f(c,t,l)char*c,*t,*l (don't give a shit about the return type).

@FUZxxl Someone mentioned this in chat, but I couldn't get it to work. Is this behavior standard? LLVM throws at least 2 errors with that line.

Sorry. Should have been f(c,t,l)char*c,*t,*l;. Do not compile in C11 mode, as the implicit int rule which allows us to drop the return type has been dropped in that revision.

@FUZxxl It seems to fail in C99, as well. In fact, every mode I've set the compiler in has rejected that code.

Did you add the semicolon right after *l? It compiles in C99 mode on my machine.

@FUZxxl Yeah, I tried that. My compiler seems to throw errors where others throw warnings. It halts compilation for the lack of a return.

What kind of weird compiler are you using? Throw that shit away, it is useless.

@FUZxxl Aha! After an embarrassing amount of searching, I found that dumb setting. I think I accidentally flipped it, or it was a default for a different language/architecture.

199 bytes

Mathematica, 331 276 270 267 264 262 252 250 bytes
Print@@@{#[[2;;,-1,2]],#[[-1,2;;,1]]}&@MapIndexed[h=Characters;({r@#2,b@#2}=<|##|>&@@Thread[h@"0 1+\\)U!&|^"->{0,0,1,i={##},{#2,#},##,1-i,1##,Max@i,(#-#2)^2}]&[r[#2-{1,0}],b[#2-{0,1}]]@#{1,1})&,Join[h@{"0"<>#3},h@StringSplit[#2<>"
"<>#,"
"]],{2}]&

The  is a private-use Unicode character which Mathematica uses as a superscript T, i.e. it's the transposition operator.
Here is a more readable version:
Print @@@ {#[[2 ;;, -1, 2]], #[[-1, 2 ;;, 1]]} &@
  MapIndexed[h = Characters;
   (
     {r@#2, b@#2} = <|##|> & @@ Thread[
            h@"0 1+\\)U!&|^" -> {
              0,
              0,
              1,
              i = {##},
              {#2, #},
              ##,
              1 - i,
              1 ##,
              Max@i,
              (# - #2)^2
              }] & [
          r[#2 - {1, 0}],
          b[#2 - {0, 1}]
          ] @ # {1, 1}
     ) &,
   Join[
    h@{"0" <> #3},
    h@StringSplit[#2 <> "\n" <> #, "\n"]\[Transpose]
   ],
   {2}] &

This is an unnamed function which takes the three strings for grid, top and left inputs and prints the bottom and right outputs.
Explanation
Let's go through this step by step (I'll try not to assume any Mathematica knowledge). You sort of need to read the code back to front. The basic algorithm just sweeps through the lines computing each function and storing the results in f to be accessed by subsequent tiles.
Input processing
That's this bit:
Join[
  h@{"0" <> #3},
  h@StringSplit[#2 <> "\n" <> #, "\n"]\[Transpose]
]

This merely splits the grid into a nested list of characters (note that I defined h as an alias for Character somewhere in the code) and then prepends a row and a column with the inputs. This works, because 1 and 0 are also the names of the constant-function tiles, so actually putting them on the has the same effect as feeding the inputs in manually. Since these are functions they will technically take their input from outside the grid, but since they are constant functions that doesn't matter. The top left corner gets a 0 but this is fairly arbitrary since the results of that tile are never used.
Also note the transposition. Adding columns takes more characters than adding rows, so I transpose the grid after adding the top row. This means that top/bottom and left/right are swapped for the main part of the program, but they're completely exchangeable so it doesn't matter. I just need to make sure to return the results in the correct order.
Solving the grid
(This section is slightly outdated. Will fix once I'm really sure I'm done golfing.)
Next up, we run MapIndexed over the inner level of this nested list. This calls the anonymous function provided as the first argument for each character in the grid, also giving it a list with the current two coordinates. The grid is traversed in order, so we can safely calculate each cell based on the previous ones.
We use the variables r(ight) and b(ottom) as lookup tables for the results of each cell. Our anonymous function has the current coordinates in #2, so we get the inputs to any cell with
r[#2 - {1, 0}],
b[#2 - {0, 1}]

Note that in the first row and column this will access undefined values of r and b. Mathematica doesn't really have a problem with that and will just give you back your coordinates instead, but we discard this result anyway, since all tiles in that row/column are constant functions.
Now this thing:
<|##|> & @@ Thread[
  h@"0 1+\\U)!&|^" -> {
     z = {0, 0}, z, o = 1 + z, {##}, ...
  }] &

Is a golfed form of
<|"0" -> (z = {0, 0}), " " -> z, "1" -> (o = 1 + z), "+" -> {##}, ... |> &

Which in turn is a function which, given the two tile inputs, returns an Association (you'd call it a hashmap or a table in other languages), that contains all the possible tile results for these two inputs. To understand, how all the functions are implemented, you need to know that the first argument of such a function can be accessed with # and the second with #2. Furthermore, ## gives you a sequence of both arguments which can be used to "splat" the arguments.

0: is straightforward, we just return a constant {0, 0} and also assign this to z for future use (e.g. in the space tile).
1: is essentially just {1,1}, but having z this is shortened to 1+z. We also save this in o, because it'll come in handy for all the tiles where both outputs are identical.
+: Here we make use of the sequence. {##} is the same as {#,#2} and passes both inputs through unchanged.
\: We swap the two arguments, {#2,#}.
U: Now we can make use of o. o#2 means {1,1}*#2 so we just put the top argument into both outputs.
): Analogously for the left argument: o#.
!: Bitwise not is annoying in Mathematica, but since we only ever have 0 and 1, we can simply subtract both inputs from 1 (thereby inverting them) and pass them on: 1-{##}.
&: This one is quite nifty. First we notice that bitwise and for 0 and 1 is identical to multiplication. Furthermore, o## is the same as o*#*#2.
|: Again, we use an equivalent function. Bitwise or is the same as Max in this case, so we apply Max to the input arguments and multiply the result into {1,1}.
^: The shortest I've found for xor is to take the difference and square it (to ensure positivity), so we've got o(#-#2)^2.

After this function completes and returns the full association we use the current cell's character to pull out the element we're interested in and store it in r and b. Note that this is also the return value of the anonymous function used in MapIndexed, so the mapping will actually give me a grid of all the results.
Output processing
MapIndexed returns a 3D grid, where the first dimension corresponds to the horizontal grid coordinate (remember the earlier transposition), the second dimension corresponds to the vertical grid coordinate and the third indicates whether we've got a bottom or a left output. Note that this also contains the input row and column which we need to get rid of. So we access the bottom row's bottom output with
#[[2;;,-1,2]]

and the final column's right output with
#[[-1,2;;,1]]

Note that 2;; is a range from the second to the last element.
Lastly, we apply Print to both of those (using @@@ as the syntactic sugar for second-level Apply), which just prints all of its arguments back-to-back (and since it's applied to two separate expressions, there will be a newline between bottom and right output).

Python 2, 384 338 325 bytes
def f(G,T,L):
 def g(x,y):
  if x>-1<y:l=g(x-1,y)[1];t=g(x,y-1)[0];r=l,t,1-l,0,0,1,t,l,l&t,l|t,l^t;i="+\\!0 1U)&|^".index(G[y*-~W+x]);return((t,l,1-t)+r[3:])[i],r[i]
  return(int((y<0)*T[x]or L[y]),)*2
 H=G.count("\n")+1;W=len(G)/H;return eval('"".join(map(str,[g(%s]for _ in range(%s)])),'*2%('_,H-1)[0','W','W-1,_)[1','H'))

Seriously CH, if this isn't a toy already you should start ringing up some toy factories.
More golfed and much less efficient now, but still haven't caught up to CarpetPython. Input like f("1111\n1\\+\\\n1+\\+\n1\\+\\","0101","1010"), output is a tuple of two strings. Make sure the board doesn't have a trailing newline though, which will break things.
Test program
def f(G,T,L):
 def g(x,y):
  if x>-1<y:l=g(x-1,y)[1];t=g(x,y-1)[0];r=l,t,1-l,0,0,1,t,l,l&t,l|t,l^t;i="+\\!0 1U)&|^".index(G[y*-~W+x]);return((t,l,1-t)+r[3:])[i],r[i]
  return(int((y<0)*T[x]or L[y]),)*2
 H=G.count("\n")+1;W=len(G)/H;return eval('"".join(map(str,[g(%s]for _ in range(%s)])),'*2%('_,H-1)[0','W','W-1,_)[1','H'))

import itertools

G = r"""
+))
U&+
U+^
""".strip("\n")

def test(T, L):
    print f(G, T, L)

def test_all():
    W = len(G[0])
    H = len(G)

    for T in itertools.product([0, 1], repeat=len(G.split("\n")[0])):
        T = "".join(map(str, T))

        for L in itertools.product([0, 1], repeat=len(G.split("\n"))):
            L = "".join(map(str, L))

            print "[T = %s; L = %s]" % (T, L)
            test(T, L)
            print ""

test("000", "000")
test("000", "100")
test("100", "000")
test("100", "100")

You can also test all possible cases with test_all().
Extra test cases
Half adder
Here's a half adder which adds the top left bits, outputting <input bit> <carry> <sum>:
+))
U&+
U+^

Tests:
000 / 000  ->  000 / 000
000 / 100  ->  001 / 101
100 / 000  ->  101 / 001
100 / 100  ->  110 / 110

Output should be the same even if the second/third bits of the inputs are changed.
Right shift
Given abc / def, this outputs fab / cde:
\\\
\++
\++

Tests:
001 / 110 -> 000 / 111
010 / 101 -> 101 / 010
101 / 100 -> 010 / 110

3-bit sorter
Sorts the first three bits of top into the last three bits of bottom. Right output is junk.
UUU)))
UU)U U
U&UU U
U+|&)U
\UU++|
 \)&UU
  \+|U
   UUU

Tests:
000000 / 00000000 -> 000000 / 00000000
001000 / 00000000 -> 000001 / 11111111
010000 / 00000000 -> 000001 / 00001111
011000 / 00000000 -> 000011 / 11111111
100000 / 00000000 -> 000001 / 00001111
101000 / 00000000 -> 000011 / 11111111
110000 / 00000000 -> 000011 / 00001111
111000 / 00000000 -> 000111 / 11111111

2-bit by 2-bit multiplier
Takes the 1st/2nd bits of top as the first number, and the 3rd/4th bits of top as the second number. Outputs to the last four bits of bottom. Right output is junk.
UUUU))))
UU++)))&
UUU+)  U
UU++&))U
U++&+)^U
U)&\&)UU
   U+^UU
   \&UUU

Edit: Golfed out a column and two rows.
Tests:
00000000 / 00000000 -> 00000000 / 00000000
00010000 / 00000000 -> 00000000 / 10000000
00100000 / 00000000 -> 00000000 / 00000000
00110000 / 00000000 -> 00000000 / 10000000
01000000 / 00000000 -> 00000000 / 00000000
01010000 / 00000000 -> 00000001 / 11111111
01100000 / 00000000 -> 00000010 / 00000000
01110000 / 00000000 -> 00000011 / 11111111
10000000 / 00000000 -> 00000000 / 00000000
10010000 / 00000000 -> 00000010 / 10000000
10100000 / 00000000 -> 00000100 / 00000000
10110000 / 00000000 -> 00000110 / 10000000
11000000 / 00000000 -> 00000000 / 00000000
11010000 / 00000000 -> 00000011 / 11111111
11100000 / 00000000 -> 00000110 / 00000000
11110000 / 00000000 -> 00001001 / 11111111

Python 2, 316 bytes
This function builds 10 tile lambda functions, then iterates though the grid, updating logic states. The final vertical and horizontal logic states are then printed.
def b(d,j,g):
 h=enumerate;e=dict((s[0],eval('lambda T,L:('+s[1:]+')'))for s in' 0,0#00,0#11,1#+L,T#\\T,L#UT,T#)L,L#!1-L,1-T#&T&L,T&L#|T|L,T|L#^T^L,T^L'.split('#'));j=list(j+'\n');g=list(g)
 for y,k in h(d.split('\n')):
  L=g[y]
  for x,c in h(k):T=j[x];L,B=e[c](int(T),int(L));j[x]=`B`
  g[y]=`L`
 print''.join(j+g)

The ungolfed code including tests:
def logic(grid, top, left):
    loop = enumerate;
    func = dict((s[0], eval('lambda T,L:('+s[1:]+')')) for s in ' 0,0#00,0#11,1#+L,T#\\T,L#UT,T#)L,L#!1-L,1-T#&T&L,T&L#|T|L,T|L#^T^L,T^L'.split('#'));
    top = list(top+'\n');
    left = list(left)
    for y,row in loop(grid.split('\n')):
        L = left[y]
        for x,cell in loop(row) :
            T = top[x];
            L, B = func[cell](int(T), int(L));
            top[x] = `B`
        left[y] = `L`
    print ''.join(top + left)

import re
testset = open('test.txt', 'rt').read().strip()
for test in testset.split('\n\n'):
    if test.endswith(':'):
        print '------------------\n'+test
    elif re.match('^[01/\n]+$', test, re.S):
        for run in test.split():
            top, left = run.split('/')
            print 'test', top, left
            logic(grid, top, left)
    else:
        grid = test

The test.txt file (including 2 other tests by Sp3000):
Nand:

&!

00/0
00/1
10/0
10/1

All ones:

1111
1\+\
1+\+
1\+\

1001/1100

Xor from Nand (note the column of trailing spaces):

\)+\
U&!&
+! !
\&!&
   !

00000/00000
00000/10000
10000/00000
10000/10000

Half adder:

+))
U&+
U+^

000/000
000/100
100/000
100/100

Right shift:

\\\
\++
\++

001/110
010/101
101/100

The test output:
------------------
Nand:
test 00 0
01
1
test 00 1
01
1
test 10 0
01
1
test 10 1
11
0
------------------
All ones:
test 1001 1100
1111
1111
------------------
Xor from Nand (note the column of trailing spaces):
test 00000 00000
00000
00000
test 00000 10000
00010
00000
test 10000 00000
00010
00000
test 10000 10000
00000
00000
------------------
Half adder:
test 000 000
000
000
test 000 100
001
101
test 100 000
101
001
test 100 100
110
110
------------------
Right shift:
test 001 110
000
111
test 010 101
101
010
test 101 100
010
110

R, 524 517
Probably lots of room to reduce this at the moment, but this has been really interesting to do.  There are two functions.  Function d is the worker and f is the comparer.
The function d is called with 3 strings, Gates, Top and Left.  The Gates are put into a matrix determined by the width.
I=strtoi;S=strsplit;m=matrix;f=function(L,T,G){O=I(c(0,1,L,T,!L,!T,L&T,L|T,xor(L,T)));X=which(S(' 01+\\U)!&|^','')[[1]]==G);M=m(c(1,1,1,2,1,1,3,2,2,4,3,4,5,4,3,6,4,4,7,3,3,8,5,6,9,7,7,10,8,8,11,9,9),nrow=3);return(c(O[M[2,X]],O[M[3,X]]))};d=function(G,U,L){W=nchar(U);H=nchar(L);U=c(list(I(S(U,'')[[1]])),rep(NA,H));L=c(list(I(S(L,'')[[1]])),rep(NA,W));G=m((S(G,'')[[1]]),nrow=W);for(i in 1:H)for(n in 1:W){X=f(L[[n]][i],U[[i]][n],G[n,i]);L[[n+1]][i]=X[1];U[[i+1]][n]=X[2]};cat(U[[H+1]],' / ',L[[W+1]],sep='',fill=T)}

Formatted a bit
I=strtoi;S=strsplit;m=matrix;
f=function(L,T,G){
    O=I(c(0,1,L,T,!L,!T,L&T,L|T,xor(L,T)));
    X=which(S(' 01+\\U)!&|^','')[[1]]==G);
    M=m(c(1,1,1,2,1,1,3,2,2,4,3,4,5,4,3,6,4,4,7,3,3,8,5,6,9,7,7,10,8,8,11,9,9),nrow=3);
    return(c(O[M[2,X]],O[M[3,X]]))
};
d=function(G,U,L){
    W=nchar(U);H=nchar(L);
    U=c(list(I(S(U,'')[[1]])),rep(NA,H));
    L=c(list(I(S(L,'')[[1]])),rep(NA,W));
    G=m((S(G,'')[[1]]),nrow=W);
    for(i in 1:H)
        for(n in 1:W){
            X=f(L[[n]][i],U[[i]][n],G[n,i]);
            L[[n+1]][i]=X[1];
            U[[i+1]][n]=X[2]
        };
    cat(U[[H+1]],' / ',L[[W+1]],sep='',fill=T)
}

Some tests
> d('&!','00','0')
01 / 1
> d('&!','00','1')
01 / 1
> d('&!','10','0')
01 / 1
> d('&!','10','1')
11 / 0
> d('\\)+\\ U&!& +! ! \\&!&    ! ','00000','00000')
00000 / 00000
> d('\\)+\\ U&!& +! ! \\&!&    ! ','00000','10000')
00010 / 00000
> d('\\)+\\ U&!& +! ! \\&!&    ! ','10000','00000')
00010 / 00000
> d('\\)+\\ U&!& +! ! \\&!&    ! ','10000','10000')
00000 / 00000
> d('+++\\00000000000\\!!!!\\00000000000\\+++','000000000000','100')
000000000000 / 001
> d('+++\\00000000000\\!!!!\\00000000000\\+++','000000000000','000')
000000000000 / 000
> d('+))U&+U+^','000','000')
000 / 000
> d('+))U&+U+^','000','100')
001 / 101
> d('+))U&+U+^','100','000')
101 / 001
> d('+))U&+U+^','100','100')
110 / 110


text:
Discrete Baker's Map
Introduction
The Baker's map is an important dynamical system that exhibits chaotic behavior.
It is a function from the unit square to itself defined intuitively as follows.

Cut the square vertically in half, resulting in two rectangles of size 0.5×1.
Stack the right half on top of the left, resulting in one rectangle of size 0.5×2
Compress the rectangle back into a 1×1 square.

In this challenge, you'll implement a discrete version of this transformation.
Input and Output
Your input is a 2D array of printable ASCII characters and whitespace of size 2m×2n for some m, n > 0.
Your output is a similar array obtained as follows, using the 6×4 array
ABCDEF
GHIJKL
MNOPQR
STUVWX

as an example.
First, stack the right half of the array on top of the left half:
DEF
JKL
PQR
VWX
ABC
GHI
MNO
STU

Then, split the columns into pairs of characters, and independently turn each pair 90 degrees clockwise, "compressing" the tall rectangle back to the original shape:
JDKELF
VPWQXR
GAHBIC
SMTNUO

This is the correct output for the above array.
Rules
The input and output formats are flexible.
You can use newline-delimited strings, lists of strings, or 2D arrays of characters.
However, the input and output must have the exact same format: you must be able to iterate your submission an arbitrary number of times on any valid input.
You can write either a full program or a function.
The lowest byte count wins, and standard loopholes are disallowed.
Test Cases
Input:
12
34

Output:
42
31

Input:
Hell
!  o
d  -
lroW

Output:
 lol
o W-
!H e
ldr

Input:
ABCDEF
GHIJKL
MNOPQR
STUVWX

Output:
JDKELF
VPWQXR
GAHBIC
SMTNUO

Input:
*___  ___  o
o|__) |__) *
*|    |    o
o __   __  *
*|    | _  o
o|__  |__| *

Output:
|_____)   *o
 |_ _     *o
||_ __|   *o
o*|_____)
o* |_ _
o*||_ _

Pyth, 25 19 18 bytes
msC_dcs_Cmck/lk2Q2

Online demonstration. It uses an 2D-array of chars.
Array of strings is one char longer (19 bytes). Online demonstration
Explanation:
         m      Q    map each string k in input:
            /lk2        calculate half the line-length: len(k)/2
          ck/lk2        chop k into pieces of length len(k)/2
                        results in two pieces
        C            zip the resulting list
                     results in a tuple ([first half of strings], [second half of strings])
       _             invert the order ([second half of strings], [first half of strings])
      s              sum (combine the two lists to a big one
     c           2   chop them into tuples
m                          for each tuple of strings:
 sC_d                        invert, zip, and sum

The last part is a bit confusing at first. Let's assume we have the tuple ['DEF', 'JKL'] (I use the example from the OP).
    d  (('D', 'E', 'F'), ('J', 'K', 'L'))   just the pair of strings
   _d  (('J', 'K', 'L'), ('D', 'E', 'F'))   invert the order
  C_d  [('J', 'D'), ('K', 'E'), ('L', 'F')] zipped
 sC_d  ('J', 'D', 'K', 'E', 'L', 'F')       sum (combine tuples)

I'm not kidding you, I just independantly wrote the exact same solution as you did. I did gloss over all answers to get an idea, but nothing detailed.

@orlp Yeah, it's quite often that the straightforward approach in Pyth is the shortest. So multiple people find it easily.

@orlp Btw, just made a pull request to the Pyth repo (not accepted yet). In the future you can simply do c2k instead of ck/lk2. c2k splits the string into two equal parts.

Julia, 136 bytes
A very straightforward implementation. Not a particularly competitive entry, but it was fun!
A->(s=size(A);w=s[2];u=w÷2;C=vcat(A[:,u+1:w],A[:,1:u]);D=cell(s);j=1;for i=1:2:size(C,1) D[j,:]=vec(flipdim(C[i:i+1,:],1));j+=1end;D)

This creates a lambda function that accepts a 2-dimensional array as input and returns a transformed 2-dimensional array.
Ungolfed + explanation:
function f(A)

    # Determine bounds
    s = size(A)          # Store the array dimensions
    w = s[2]             # Get the number of columns
    u = w ÷ 2            # Integer division, equivalent to div(w, 2)

    # Stack the right half of A atop the left
    C = vcat(A[:, u+1:w], A[:, 1:u])

    # Initialize the output array with the appropriate dimensions
    D = cell(s)

    # Initialize a row counter for D
    j = 1

    # Loop through all pairs of rows in C
    for i = 1:2:size(C, 1)

        # Flip the rows so that each column is a flipped pair
        # Collapse columns into a vector and store in D
        D[j, :] = vec(flipdim(C[i:i+1, :], 1))

        j += 1
    end

    return D
end

To call it, give the function a name, e.g. f=A->(...).
Example output:
julia> A = ["A" "B" "C" "D" "E" "F";
            "G" "H" "I" "J" "K" "L";
            "M" "N" "O" "P" "Q" "R";
            "S" "T" "U" "V" "W" "X"]
julia> f(A)

4x6 Array{Any,2}:
 "J"  "D"  "K"  "E"  "L"  "F"
 "V"  "P"  "W"  "Q"  "X"  "R"
 "G"  "A"  "H"  "B"  "I"  "C"
 "S"  "M"  "T"  "N"  "U"  "O"

julia> B = ["H" "e" "l" "l";
            "!" " " " " "o";
            "d" " " " " "-";
            "l" "r" "o" "W"]
julia> f(B)

4x4 Array{Any,2}:
 " "  "l"  "o"  "l"
 "o"  " "  "W"  "-"
 "!"  "H"  " "  "e"
 "l"  "d"  "r"  " "

And proof that it can be arbitrarily chained:
julia> f(f(B))

4x4 Array{Any,2}:
 "W"  "o"  "-"  "l"
 "r"  " "  " "  "e"
 "o"  " "  " "  "l"
 "l"  "!"  "d"  "H"

Suggestions are welcome as always, and I'll happy provide any further explanation.

CJam, 25 24 bytes
qN/_0=,2/f/z~\+2/Wf%:zN*

Straight forward spec implementation. Explanation:
qN/                       "Split input by rows";
   _0=,2/                 "Get half of length of each row";
         f/               "Divide each row into two parts";
           z              "Convert array of row parts to array of half columns parts";
            ~\+           "Put the second half of columns before the first half and join";
               2/         "Group adjacent rows";
                 Wf%      "Flip the row pairs to help in CW rotation";
                    :z    "Rotate pairwise column elements CW";
                      N*  "Join by new line";

Try it online here

JavaScript (ES6), 104  141
Edit Reviewing the spec, I found that the number of rows must be even (I missed this before). So it's not too complicated find the correct source position for each char in output in a single step.
F=a=>a.map((r,i)=>
  [...r].map((c,k)=>
     a[l=i+i]?a[(j=l+1)-k%2][(k+r.length)>>1]:a[l-j-k%2][k>>1]
  ).join('')
)

Test In Firefox/FireBug console
;[["ABCDEF","GHIJKL","MNOPQR","STUVWX"]
 ,["12","34"], ["Hell","!  o","d  -","lroW"]
 ,["*___  ___  o","o|__) |__) *","*|    |    o","o __   __  *","*|    | _  o","o|__  |__| *"]
].forEach(v=>console.log(v.join('\n')+'\n\n'+F(v).join('\n')))

Output
ABCDEF
GHIJKL
MNOPQR
STUVWX

JDKELF
VPWQXR
GAHBIC
SMTNUO

12
34

42
31

Hell
!  o
d  -
lroW

 lol
o W-
!H e
ldr

*___  ___  o
o|__) |__) *
*|    |    o
o __   __  *
*|    | _  o
o|__  |__| *

|_____)   *o
 |_ _     *o
||_ __|   *o
o*|_____)
o* |_ _
o*||_ _

J, 45 39 bytes
   $$[:,@;@|.@|:([:,:~2,2%~1{$)<@|:@|.;.3]

J has a tessellation function (cut ;.) which helps a lot.
   ]input=.4 6$97}.a.
abcdef
ghijkl
mnopqr
stuvwx

   ($$[:,@;@|.@|:([:,:~2,2%~1{$)<@|:@|.;.3]) input
jdkelf
vpwqxr
gahbic
smtnuo

See my answer for another way to solve the challenge in J.

Haskell, 128 127 bytes
import Control.Monad
f=g.ap((++).map snd)(map fst).map(splitAt=<<(`div`2).length)
g(a:b:c)=(h=<<zip b a):g c
g x=x
h(a,b)=[a,b]

Usage: f ["12", "34"] -> ["42","31"]
How it works:
                                 input list:
                                   ["abcdef", "ghijkl", "mnopqr", "stuvwx"]
==========================================================================

map(splitAt=<<(`div`2).length)   split every line into pairs of halves:
                                   -> [("abc","def"),("ghi","jkl"),("mno","pqr"),("stu","vwx")]
ap((++).map snd)(map fst)        take all 2nd elements of the pairs and
                                 put it in front of the 1st elements:
                                   -> ["def","jkl","pqr","vwx","abc","ghi","mno","stu"]
(    zip b a) : g c              via g: take 2 elements from the list and
                                 zip it into pairs (reverse order),
                                 recur until the end of the list:
                                   -> [[('j','d'),('k','e'),('l','f')],[('v','p'),('w','q'),('x','r')],[('g','a'),('h','b'),('i','c')],[('s','m'),('t','n'),('u','o')]]
h=<<                             convert all pairs into a two element list
                                 and concatenate:
                                   -> ["jdkelf","vpwqxr","gahbic","smtnuo"]

Edit: @Zgarb found a byte to save.

Nice! You can save 1 byte by doing g x=x for the empty list case.

J, 33 32 characters
A monadic verb.
0 2,.@|:_2|.\"1-:@#@{.(}.,.{.)|:

Explanation
Let's begin by defining Y to be our sample input.
   ] Y =. a. {~ 65 + i. 4 6          NB. sample input
ABCDEF
GHIJKL
MNOPQR
STUVWX

The first part (-:@#@{. (}. ,. {.) |:) splits Y in half and appends then ends:
   # {. Y                            NB. number of columns in Y
6
   -: # {. Y                         NB. half of that
3
   |: Y                              NB. Y transposed
AGMS
BHNT
CIOU
DJPV
EKQW
FLRX
   3 {. |: Y                         NB. take three rows
AGMS
BHNT
CIOU
   3 }. |: Y                         NB. drop three rows
DJPV
EKQW
FLRX
   3 (}. ,. {.) |: Y                 NB. stitch take to drop
DJPVAGMS
EKQWBHNT
FLRXCIOU

In the second part (_2 |.\"1) we split this into pairs of two and reverse them:
   R =. (-:@#@{. (}. ,. {.) |:) Y    NB. previous result
   _2 <\"1 R                         NB. pairs put into boxes
┌──┬──┬──┬──┐
│DJ│PV│AG│MS│
├──┼──┼──┼──┤
│EK│QW│BH│NT│
├──┼──┼──┼──┤
│FL│RX│CI│OU│
└──┴──┴──┴──┘
   _2 <@|.\"1 R                      NB. reversed pairs
┌──┬──┬──┬──┐
│JD│VP│GA│SM│
├──┼──┼──┼──┤
│KE│WQ│HB│TN│
├──┼──┼──┼──┤
│LF│XR│IC│UO│
└──┴──┴──┴──┘

Finally (0 2 ,.@|:), we transpose the matrix as needed and discard the trailing axis:
   ] RR =. _2 |.\"1 R                NB. previous result
JD
VP
GA
SM

KE
WQ
HB
TN

LF
XR
IC
UO
   0 2 |: RR                         NB. transpose axes
JD
KE
LF

VP
WQ
XR

GA
HB
IC

SM
TN
UO
   ($ RR) ; ($ 0 2 |: RR)            NB. comparison of shapes
┌─────┬─────┐
│3 4 2│4 3 2│
└─────┴─────┘
   ,. 0 2 |: RR                      NB. discard trailing axis
JDKELF
VPWQXR
GAHBIC
SMTNUO

The whole expression with whitespace inserted:
0 2 ,.@|: _2 |.\"1 -:@#@{. (}. ,. {.) |:

And as an explicit verb:
3 : ',. 0 2 |: _2 |.\"1 (-: # {. y) (}. ,. {.) |: y'

GNU sed -r, 179 bytes
Score includes +1 for the -r arg to sed.
It took me a while to figure out how to do this in sed, but I think I have it now:
# Insert : markers at start and end of each row
s/  /:  :/g
s/(^|$)/:/g
# Loop to find middle of each row
:a
# Move row start and end markers in, one char at a time
s/:([^  :])([^  :]*)([^ :]):/\1:\2:\3/g
ta
# Loop to move left half of each row to end of pattern buffer
:b
s/([^   :]+)::(.*)/\2   \1/
tb
# remove end marker
s/$/:/
# double loop to merge odd and even rows
:c
# move 1st char of rows 2 and 1 to end of pattern buffer
s/^([^  :])([^  ]*) ([^ ])(.*)/\2   \4\3\1/
tc
# end of row; remove leading tab and add trailing tab
s/^ +(.*)/\1    /
tc
# remove markers and trailing tab
s/(:|   $)//g

Note all the whitespace above should be single tab characters.  Comments are not included in the golf score.
Note also that this makes extensive use of : marker characters.  If the input stream contains :, then undefined behaviour will ensue.  This can be mitigated by replacing all : with some non-printing character (e.g. BEL) at no cost to the golf score.
Input and output is a tab-separated list of strings:
$ echo 'Hell
!  o
d  -
lroW' | paste -s - | sed -rf baker.sed | tr '\t' '\n'
 lol
o W-
!H e
ldr
$

Husk, 18 bytes
mΣmm↔TmC2T§+m→m←m½

Try it online!
Gaming

source: Stack Exchange

license: 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:
Prime polynomials
Given a polynomial, determine whether it's prime.
A polynomial is ax^n + bx^(n-1) + ... + dx^3 + ex^2 + fx + g, where each term is a constant number (the coefficient) multiplied by a nonnegative integer power of x. The highest power with a nonzero coefficient is called the degree. For this challenge, we only consider polynomials of at least degree 1. That is, each polynomial contains some x. Also, we only use polynomials with integer coefficients.
Polynomials can be multiplied. For example, (x+3)(2x^2-2x+3) equals 2x^3+4x^2-3x+9. Thus, 2x^3+4x^2-3x+9 can be factored into x+3 and 2x^2-2x+3, so it is composite.
Other polynomials can not be factored. For example, 2x^2-2x+3 is not the product of any two polynomials (ignoring constant polynomials or those with non-integer coefficients). Hence, it is prime (also known as irreducible).
Rules

Input and output can be through any standard way.
Input can be a string like 2x^2-2x+3, a list of coeffecients like {2,-2,3}, or any similar means.
Output is either a truthy value if it's prime, or a falsey value if it's composite. You must yield the same truthy value for all primes, and the same falsey value for all composite polynomials.
The input will be of at least degree 1 and at most degree 10.
You may not use built-in tools for factorization (of integers or expressions) or equation solving.

Examples
True - prime
x+3
-2x
x^2+x+1
x^3-3x-1
-2x^6-3x^4+2
3x^9-8x^8-3x^7+2x^3-10

False - composite
x^2
x^2+2x+1
x^4+2x^3+3x^2+2x+1
-3x^7+5x^6-2x
x^9-8x^8+7x^7+19x^6-10x^5-35x^4-14x^3+36x^2+16x-12

From some quick googling this is a hard problem regardless of golfing.

So, given a list of 3 coefficients, we determine whether or not it can be factored?

@kirbyfan64sos given a list of all coeficients of a polynomial of degree from one to ten (inclusive), so anywhere between two to eleven coeficients.
I personally think that up to ten is silly if we are talking about a golfing problem. I suggest degree one to degree five for a moderate dificulity but still golfable approach.

Am I correct in thinking that by prime you mean irreducible? If so then this is basically a variant on this question about factoring polynomials, and I suspect that it won't attract any answers which don't factor.

@PeterTaylor Correct. Is there really no easier way?

According to this recent paper, "We are interested in the question of deciding whether a given polynomial is irreducible or not. Consequently, a simple test or criterion which would give this information is desirable. Unfortunately, no such criterion which will apply to all the classes of polynomials has yet been devised".

cough Rational Root Theorem cough Edit: this won't actually solve the problem if the polynomial is divisible, by, say, x^2 + x + 1 and another irreducible quadratic.

@AlexA., there are many many "if" tests which work for some polynomials, but the question is asking for an "if and only if" test which works for all polynomials.

This is a nice problem! Note that usually polynomials are only prime relative to a base ring (or field). In particular, if the field is the complex numbers, then no polynomial of degree greater than 2 is prime. So I would specify whether you want Rational (probably the most straightforward) Integer (this will involve some integer factoring as well), or modulo some number m. If m is prime, then there are rather easy algorithms. Otherwise things are a bit more tricky...(but feasible)

@cody OP specified integers.

Shouldn't input be something along the lines of {[2, 2], [3, 1], [a, b]} as in ax^b?

@ASCIIThenANSI You can accept input like that, if you want.

We are testing irreducibility over what field/ring? The integers? The rationals? The reals? The complex numbers? If it's one of the latter two, it's rather trivial due to the Fundamental Theorem of Algebra, so I'd assume either the integers or the rationals, but it's crucial that you specify which.

@Justin It's the integers: "ignoring constant polynomials or those with non-integer coefficients".

If not is allowed to use 'solve' for factoring polynomial my solution is out.  factor can not be used on polynomial, factor can be used on integers? Thanks

Mathematica, 224 bytes
f@p_:=(e=p~Exponent~x;r=Range[⌈e/-4⌉,(e+2)/4];e<2||FreeQ[PolynomialRemainder[p,Thread@{r,#}~InterpolatingPolynomial~x,x]&/@Tuples[#~Join~-#&[Join@@Position[#/Range@Abs@#,_Integer]]&/@#]~DeleteCases~{(a_)..},0|{}]&[p/.x->r])

Explanation:
Kronecker's method is used here. This method generates certain lower degree polynomials and tests whether there exists a factor of the original polynomial.
Test cases:
f/@{x+3, -2x, x^2+x+1, x^3-3x-1, -2x^6-3x^4+2, 3x^9-8x^8-3x^7+2x^3-10}
(* {True, True, True, True, True, True} *)

f/@{x^2, x^2+2x+1, x^4+2x^3+3x^2+2x+1, -3x^7+5x^6-2x, x^9-8x^8+7x^7+19x^6-10x^5-35x^4-14x^3+36x^2+16x-12}
(* {False, False, False, False, False} *)

It takes 14s on my laptop to conclude that 3x^9-8x^8-3x^7+2x^3-10 is prime.

PARI/GP, 16 bytes, cheap as hell
For some reason this wasn't disallowed (noting that the command doesn't factor or equation-solve):
polisirreducible

Test case
%(x^2+x+1)

returns 1 (true). The other examples work similarly.
But to show that this is solvable the hard way, here's a full solution.
Less cheap, but sloooooooooow
There's really no point golfing this.
Beauzamy(P)=
{
  my(d=poldegree(P),s,c);
  s=sum(i=0,d,polcoeff(P,i)^2/binomial(d,i));
  c = 3^(3/2 + d);
  c *= s / (4*d*Pi);
  abs(c * pollead(P))
}
factorpol(P)=
{
  my(B=Beauzamy(P)\1, t=B*2+1, d=poldegree(P)\2, Q);
  for(i=0,t^(d+1)-1,
    Q=Pol(apply(n->n-B, digits(i,t)));
    if(Q && poldegree(Q) && P%Q==0, return(Q))
  );
  0
}
irr(P)=
{
  factorpol(P)==0
}

Edit: Commenters have pointed out that the first method may be disallowed by good taste, the spirit of the rules, the Geneva Convention, standard loophole rules, etc. I don't agree, but in any case I posted the second version along with the first and certainly it seems acceptable.

Hmmmm... I'm pretty sure that this command does factor and/or solve equations under the hood. (Also, if a challenge disallows certain built-ins is kinda implied that a built-in that just solves the problem is also not in the spirit of the challenge.)

@MartinBüttner: I think that the first answer fits the letter, but not the spirit, of the challenge's rules. That's why I wrote the second version, which is a legitimate solution. It can check that x^4+1 (which is famously reducible mod any prime) is irreducible in 86 milliseconds. If nothing else others can adapt and golf this version.

The first answer falls in a loophole which is banned by default: Using built-in functions to do the work. Please remove it from your answer, or at least indicate that it is not a valid solution.

@isaacg That is not currently a valid standard loophole (due to the vote breakdown +44/-29). Charles, if you agree that only the second answer is really legitimate, then you should include its byte count instead.

@MartinBüttner: I don't -- I think both are legitimate by the rules of this question and the general loopholes thread. But I added a comment to point out the issue.

-1. The second answer (which is arguably the only valid one) is not golfed and doesn't have its byte count listed. You may not use built-in tools for factorization (of integers or expressions) or equation solving.

@mbomb007 If the original question poser edits to clarify that polisirreducible is disallowed, I will remove the first version and golf the second.

polisirreducible uses factoring in its implementation, and is therefore disallowed. According to a code search, its C-Name is gisirreducible. The definition of that function can be seen here (Ctrl+F, search for gisirreducible). You can see that the definition of the function contains a call to factor. The  definition for that can also be seen, and it does factor polynomials.

@MartinEnder The comment above shows that you are correct. It factors polynomials under the hood.

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


text:
How do I craft that?
There are 21 items in Minecraft that you can craft using only wood and items crafted from wood:

axe
boat
bowl
button
chest
crafting table
door
fence
gate
hoe
ladder
pickaxe
planks
pressure plate
shovel
sign
slab
stairs
stick
sword
trapdoor

This list assumes that the 6 different types of wooden planks/slabs/doors/etc. all count as the same item. Another way to think of it is to assume you only have access to one type of wood.
Each of these 21 items has a different crafting recipe. We'll represent each of these recipes as a 2×2 or 3×3 grid of the characters .WPS. The . is an empty crafting slot, W is for wood, P is for wood planks, and S is for sticks. No other characters are needed for these particular items.
For example, this is the recipe for a chest:
PPP
P.P
PPP

Challenge
Write a program that takes in the name of one of our 21 items, exactly as it appears above, and prints a valid crafting recipe for that item.
Crafting recipes are translation invariant, so if the input is fence, both of these are valid:
PSP
PSP
...
...
PSP
PSP
If a recipe fits in a 2×2 grid, you can output it in a 2×2 or 3×3 grid. e.g. stick:
.P
.P
...
.P.
.P.
Recipes can also be mirrored horizontally (around a vertical line of symmetry), though this only makes a difference for the axe, hoe, and stairs. e.g. hoe:
.PP
.S.
.S.
PP.
.S.
.S.
So outputting any recipe that fits in the grid and has the correct shape (ignoring translation and mirroring) is what your program needs to do. These are all the recipes that the official game will recognize. (Note that recipes cannot be rotated or mirrored vertically.)
Details

Take input from stdin or the command line. You can assume the input is always valid. Requiring quotes around input (e.g. "chest") is fine.
Output to stdout (or closest alternative) with an optional trailing newline.
The shortest submission in bytes wins.

Example
Here's a list of all inputs and sample outputs:
axe
PP.
SP.
S..

boat
P.P
PPP
...

bowl
P.P
.P.
...

button
P.
..

chest
PPP
P.P
PPP

crafting table
PP
PP

door
PP.
PP.
PP.

fence
PSP
PSP
...

gate
SPS
SPS
...

hoe
PP.
S..
S..

ladder
S.S
SSS
S.S

pickaxe
PPP
.S.
.S.

planks
W.
..

pressure plate
PP
..

shovel
P..
S..
S..

sign
PPP
PPP
.S.

slab
PPP
...
...

stairs
P..
PP.
PPP

stick
P.
P.

sword
P..
P..
S..

trapdoor
PPP
PPP
...

Given your output samples, I don't see any exception. All can be mirrored, but most are symmetric.

Since "in bytes" links to the UTF-8 counter, does that mean we have to count bytes in UTF-8?

Full programs only? No functions?

@Alex A. Right.

@MartinBüttner Make that no. (You know why, though it probably doesn't matter anymore. :P )

CJam, 100 96 94 91 bytes
"+WcbKF AQH;_{GM8Lyf=_tmTn"141bDb3/l72b970%={Z"O>HVa=4a"98bZb+"P.SW"f=3/=}%N*

StackExchange mangles unprintables, so rather than copying and pasting here is the permalink. Additionally, here's the test program.
(Thanks to @Optimizer for telling me about f and @MartinBüttner for telling me about CJam's modulo indexing.)
Cygwin's hexdump:
0000000 0122 2b1e 571a 6308 621f 4b05 2046 5141
0000010 1608 1848 5f3b 1115 1d7b 4d47 4c38 6679
0000020 5f3d 6d74 0c54 226e 3431 6231 6244 2f33
0000030 376c 6232 3739 2530 7b3d 225a 1b4f 483e
0000040 6156 343d 2261 3839 5a62 2b62 5022 532e
0000050 2257 3d66 2f33 7d3d 4e25 002a
000005b

Explanation
To construct the recipes, we use 13 different rows (also listed are explanations why this is minimal):
0    W..    (required by planks)
1    ...    (required by many)
2    .PP    (required by many)
3    PPP    (required by chest)
4    .P.    (required by bowl)
5    ..P    (required by stairs)
6    S.S    (required by ladder)
7    SSS    (required by ladder)
8    .S.    (required by sign)
9    .SP    (required by axe)
10   P.P    (required by bowl)
11   PSP    (required by fence)
12   SPS    (required by gate)

We encode the rows via Z"O>HVa=4a"98bZb+"P.SW"f=3/, which gives
["W.." "..." ".PP" "PPP" ".P." "..P" "S.S" "SSS" ".S." ".SP" "P.P" "PSP" "SPS"]

The first bit "+WcbKF AQH;_{GM8Lyf=_tmTn"141bDb3/ encodes the recipes, giving
[[3 3 8] [1 0 0] [1 0 0] [3 8 8] [1 3 3] [2 8 8] [6 7 6] [1 0 0] [1 10 3] [1 1 2] [2 2 2] [1 11 11] [1 1 4] [1 0 1] [1 10 4] [2 9 8] [3 10 3] [1 2 2] [4 8 8] [1 4 4] [1 1 3] [1 12 12] [4 4 8] [5 2 3]]

Note how the first entry is [3 3 8], which is the recipe for sign.
l72b970%= reads in the input, then applies some magic to work out which recipe to take from the list. Even though we only have 21 recipes there are 24 in the list — the extra few spots correspond to the [1 0 0]s.
After reading the input, picking the recipe and converting the recipe to rows, we put in some newlines N* and auto-print.

CJam, 89 86 83 bytes
'W"9=!%)S@*m:@DQzk?V$%qyR55AmVEpPNW}"132b3b"P.S"f=+3/3/l57b5342%24%(=N*

... it turns out that hardcoding all the outputs does a bit better in CJam. I'm pretty disappointed.
Once again we have some unprintables so here's the permalink and test program.
Cygwin's hexdump:
0000000 5727 0222 3d39 1021 2925 531e 2a40 6d0b
0000010 403a 1844 7a51 3f6b 2456 7125 5279 3506
0000020 4135 046d 1a56 7045 1550 164e 1057 7d01
0000030 3122 3233 3362 2262 2e50 2253 3d66 332b
0000040 332f 6c2f 3735 3562 3433 2532 3432 2825
0000050 4e3d 002a
0000053

Explanation
The outputs are encoded using base 3, with the lone W being tacked onto the front before the string is split into 3s to give rows, and the rows are split into groups of 3s to give recipes.
Like above, base converting and modulo magic is used to select the recipe. There are 22 recipes (one unused) but we need to take modulo 24, so we actually need to explicitly specify 24% this time rather than relying on modulo indexing.

Can you post a hexdump with xxd? The permalinks doesn't work on Firefox.

@n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Unfortunately I'm on Windows, so I've put up the next best thing I could manage for now.

JavaScript (ES6), 235 241 262
Edit Abusing even more of the rule that input is always valid: there is just 1 item that requires W, and that can be special cased. So the output grid is encoded as 9 digit base 3 numbers.
235 bytes with I/O via popup.
w=prompt();
"926a722boa182bo2b19520ch224c6056d644f448g764h7651l2294pi8pr758sh2915si26sl19172sta56st785s728t"
.replace(/(\d+)(\D+)/g,(c,p,m)=>w.search(m+z)||[for(c of'11\n11\n111')z+='.SP'[~~p%3]+(p/=3,-c?'':c)],z='');
alert(&&z||'W.\n..')

221 bytes as a testable function.
F=w=>"926a722boa182bo2b19520ch224c6056d644f448g764h7651l2294pi8pr758sh2915si26sl19172sta56st785s728t"
.replace(/(\d+)(\D+)/g,(c,p,m)=>w.search(m+z)||[for(c of'11\n11\n111')z+='.SP'[~~p%3]+(p/=3,-c?'':c)],z='')&&z||'W.\n..'

Output always as 3x3 grid. With 4 available output symobols, the grid is encoded as a 3x3x2 (18) bit number. And as the input have to be always valid, the string are stored truncated to the bare minimum.
Test In Firefox/FireBug console
;["axe", "boat", "bowl", "button", "chest", "crafting table", "door",
 "fence", "gate", "hoe", "ladder", "pickaxe", "planks", "pressure plate",
 "shovel", "sign", "slab", "stairs", "stick", "sword", "trapdoor"]
.forEach(v=>console.log(v+'\n'+F(v)))

Output
axe
PP.
SP.
S..

boat
P.P
PPP
...

bowl
P.P
.P.
...

button
P..
...
...

chest
PPP
P.P
PPP

crafting table
PP.
PP.
...

door
PP.
PP.
PP.

fence
PSP
PSP
...

gate
SPS
SPS
...

hoe
PP.
S..
S..

ladder
S.S
SSS
S.S

pickaxe
PPP
.S.
.S.

planks
W.
..

pressure plate
PP.
...
...

shovel
P..
S..
S..

sign
PPP
PPP
.S.

slab
PPP
...
...

stairs
P..
PP.
PPP

stick
P..
P..
...

sword
P..
P..
S..

trapdoor
PPP
PPP
...

Python, 305 bytes
n=2**(23-hash(raw_input())/535366%24);print "W..\n...\n..." if n==1024 else "\n".join(["".join(['P' if [16706041,9740732,7635081,7399784,5267501,7372808,57344,57344,49152][j+i*3]&n==n else 'S' if [6,2097152,6,131078,10748162,6,131138,9699584,2][j+i*3]&n==n else '.' for j in range(3)]) for i in range(3)])

Explanation
# Compute a unique number for each item.
# 535366 and 24 are precalculated values that were bruteforced.
n = 23 - hash(raw_input()) / 535366 % 24

# Use precalculated tables that represent which ingredient in this recipe of
# an item. The nth bit of p[0] will be set if the first ingredient of the item
# associated with the unique number n is some planks. It works the same for s.
p = [16706041,9740732,7635081,7399784,5267501,7372808,57344,57344,49152]
s = [6,2097152,6,131078,10748162,6,131138,9699584,2]

# Handle planks differently, as it is the only one using wood.
if n == 10:
    print "W..\n...\n..."
else:
    for i in xrange(3):
        line = ""
        for j in xrange(3):
            # Now we can check if the ingredient is some planks...
            if p[j + i * 3] & 1 << n == 1 << n:
                line += 'P'
            # ...or if it is some sticks...
            elif s[j + i * 3] & 1 << n == 1 << n:
                line += 'S'
            # ...or if it is simply empty.
            else:
                line += '.'
        print line

Comment
This code surely isn't the tiniest but it works just fine. I'm satisfied. :)
Python, 282 bytes
n=hash(raw_input())/808789215%21;print "\n".join(["P.PPPP...P..S..S..PP.......PP.PP....P........SPSSPS...PPPPPP.S.PP.PS..S.W........PPPPPP...PP..S..S.P..PP.PPPS.SSSSS.SPPP.S..S.PPP......P..P..S..PPPP.PPPPPSPPSP...PP.PP.PP.P..P.....P.P.P...."[9*n+i*3:9*n+(i+1)*3] for i in range(3)])

Using the same technique to generate an unique identifier but directly looking up the recipe in an array. It is a lot simpler and a little more compact than my first code.

Having a special case for 'planks' you can shorten the string to W.\n..

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


text:
Decrypting a block of AES
Today your goal is to decrypt a secret message using AES. Given a ciphertext and key you will decrypt and print the message.

Your program may be in any language. It will be run with input on stdin, and its output on stdout will be checked for correctness.
The first line of input on stdin will be the 16 byte key, encoded in hexadecimal. The second line of input on stdin will be the 16 byte ciphertext, encoded in hexadecimal.
The output of the program must be the 16 byte message after decrypting the ciphertext using AES-128 with the given key. You must output the result interpreted as ASCII octets. You may assume that any result is valid ASCII after decrypting.
You may not use any library/built-in features that implement AES. You may use such features to convert between hex/binary/ASCII encodings.

Shortest code in bytes wins.
Example input and output:
bd8ab53f10b3d38576a1b9a15cf03834
02c0ee126cae50ba938a8b16f0e04d23

 Attack tomorrow.

And another:
f4af804ad097ba832906db0deb7569e3
38794338dafcb09d6b32b04357f64d4d

 Congratulations.

...What is AES?

@AlexA. Advanced Encryption Standard.

Related

Python, 661 chars
R=range
I=lambda x:[int(x[2*i:2*i+2],16)for i in R(16)]
k=I(raw_input())
c=I(raw_input())
P=[]
x=1
for i in R(512):P+=[x];x^=x*2^(x>>7)*0x11b
S=[255&(99^j^(j>>4)^(j>>5)^(j>>6)^(j>>7))for i in R(256)for j in[(P[255-P.index(i)]if i else 0)*257]]
for r in R(10):
 for i in R(4):k+=[k[-16]^S[k[-3-(i>2)*4]]]
 k[-4]^=[1,2,4,8,16,32,64,128,27,54][r]
 for i in R(12):k+=[k[-16]^k[-4]]
for r in R(11):
 c=[x^y for x,y in zip(k[160-16*r:],c)]
 if r>9:break
 for i in[0,4,8,12]*(r>0):c[i:i+4]=[x^y^z^w for j in R(4)for x,y,z,w in[[P[a+P.index(v)]if v else 0 for a,v in zip((2*[104,238,199,223])[3-j:],c[i:i+4])]]]
 c=(c*13)[::13];c=map(S.index,c)
print''.join(map(chr,c))

k is the key, c is the ciphertext.  I build P, the powers of 3 in the field, then S, the sbox.  Then k is extended with the key schedule.  Finally we do the AES decryption.  Mixcolumns is the hard phase, all the other phases are pretty straightforward.

Maybe you should also do one in Pyth, otherwise I'll guarantee you someone will sweep along and translate it, beating you :)

As a quick test I generated another testcase, but your solution fails for it. I added the second testcase to the question so you can debug.

@orip: fixed.  It was a bug in multiplying by zero.


text:
Chinese Remainder Theorem
The Chinese Remainder Theorem tells us that we can always find a number that produces any required remainders under different prime moduli. Your goal is to write code to output such a number in polynomial time. Shortest code wins.
For example, say we're given these constraints:

\$n \equiv 2 \mod 7\$
\$n \equiv 4 \mod 5\$
\$n \equiv 0 \mod 11\$

One solution is \$n=44\$. The first constraint is satisfied because \$44 = 6\times7 + 2\$, and so \$44\$ has remainder \$2\$ when divided by \$7\$, and thus \$44 \equiv 2 \mod 7\$. The other two constraints are met as well. There exist other solutions, such as \$n=814\$ and \$n=-341\$.
Input
A non-empty list of pairs \$(p_i,a_i)\$, where each modulus \$p_i\$ is a distinct prime and each target \$a_i\$ is a natural number in the range \$0 \le a_i < p_i\$. You can take input in whatever form is convenient; it doesn't have to actually be a list of pairs. You may not assume the input is sorted.
Output
An integer \$n\$ such that \$n \equiv a_i \mod p_i\$ for each index \$i\$. It doesn't have to be the smallest such value, and may be negative.
Polynomial time restriction
To prevent cheap solutions that just try \$n=0, 1, 2, \dots\$, and so on, your code must run in polynomial time in the length of the input. Note that a number \$m\$ in the input has length \$Θ(\log m)\$, so \$m\$ itself is not polynomial in its length. This means that you can't count up to \$m\$ or do an operation \$m\$ times, but you can compute arithmetic operations on the values.
You may not use an inefficient input format like unary to get around this.
Other bans
Built-ins to do the following are not allowed: Implement the Chinese Remainder theorem, solve equations, or factor numbers.
You may use built-ins to find mods and do modular addition, subtraction, multiplication, and exponentiation (with natural-number exponent). You may not use other built-in modular operations, including modular inverse, division, and order-finding.
Test cases
These give the smallest non-negative solution. Your answer may be different. It's probably better if you check directly that your output satisfies each constraint.
[(5, 3)]
3

[(7, 2), (5, 4), (11, 0)]
44

[(5, 1), (73, 4), (59, 30), (701, 53), (139, 112)]
1770977011

[(982451653, 778102454), (452930477, 133039003)]
68121500720666070

Why no division?

@user23013 No modular division, since it's basically modular inverse.

Does matrix inversion count as solving equations?

@flawr: I would think so.

@xnor: What do you think? And how about optimization functions?

@flawr Both matrix inversion and optimization functions would count as equation solving. Also, if your matrix inversion is mod n, that would be modular inversion.

In retrospect, allowing modular exponentiation gave too much advantage to languages with built-in power-mod, since a poly-time version takes code to implement on your own. Sorry about that.

@xnor, I was just thinking of a question very similar to this. I'm gonna give you +1 for breathing me to it!

@cairdcoinheringaahing Thanks a lot for editing the equations!

Mathematica, 55 51 45
Modular inverse is banned, but modular exponentiation is allowed. By Fermat's little theorem, n^(-1) % p == n^(p-2) % p.
(PowerMod[x=1##&@@#/#,#-2,#]x).#2&@@Thread@#&

Example:
In[1]:= f = (PowerMod[x=1##&@@#/#,#-2,#]x).#2&@@Thread@#&;

In[2]:= f[{{5, 3}}]

Out[2]= 3

In[3]:= f[{{7, 2}, {5, 4}, {11, 0}}]

Out[3]= 1584

In[4]:= f[{{5, 1}, {73, 4}, {59, 30}, {701, 53}, {139, 112}}]

Out[4]= 142360350966

Just for fun:
ChineseRemainder@@Reverse@Thread@#&

You can save one byte by swapping the order of the arguments of the innermost function, such that you can use PowerMod[#2,#-2,#] and I also don't think there's a requirement for the function to be named, bringing it down to 48.

Yes,  unnamed functions are OK.

Python 2, 165 101 99 98 85 bytes
Using Fermat's little theorem like the other answers. Doesn't bother with keeping final sum within modular range, since we're not interested in the smallest solution. Thanks Volatility for saving 13 bytes.
l=input();x=reduce(lambda a,b:a*b[0],l,1)
print sum(x/a*b*pow(x/a,a-2,a)for a,b in l)

[(5, 3)]
3
[(7, 2), (5, 4), (11, 0)]
1584
[(5, 1), (73, 4), (59, 30), (701, 53), (139, 112)]
142360350966

You can remove the space before for.

x/a*b*pow(x/a,a-2,a)for a,b in l should work.

Excellent point! I was trying to get rid of the obvious redundancy there but forgot that I could just unpack.

Pyth, 40 37 36 29
M*G.^G-H2Hsm*edg/u*GhHQ1hdhdQ

Uses Fermat's little theorem, thanks to alephalpha. Computes using this formula.

Ruby, 129
Well, comrades, it seems Ruby solutions must be longer because modular exponentiation is not available without loading openssl library and doing conversions to OpenSSL::BN. Still, had fun writing it:
require("openssl")
z=eval(gets)
x=1
z.map{|a,b|x*=a}
s=0
z.map{|a,b|e=a.to_bn;s+=(x/a).to_bn.mod_exp(e-2,e).to_i*b*x/a}
puts(s)

You don't need the parens when calling require, eval, or puts.

Python 2, 61
n=P=1
for p,a in input():n+=P*(a-n)*pow(P,p-2,p);P*=p
print n

This employs a variation of the product construction that other answers use.
The idea is to loop over the constraints and update the solution n to meet the current constraint without messing up the prior ones. To do so, we track the product P of the primes seen up to now, and observe that adding a multiple of P has no effect modulo any already-seen prime.
So, we just need to change n to satisfy n%p == a by adding the right multiple of P. We solve for the coefficient c:
(n + P*c) % p == a
This requires that c = (a-n) * P^(-1), where the inverse is taken modulo p. As others note, the inverse can be computed by Fermat's Little Theorem as P^(-1) = pow(P,p-2,p). So, c = (a-n) * pow(P,p-2,p), and we update n by n+= P * (a-n) * pow(P,p-2,p).

Haskell, 68 100 bytes
f l=sum[p#(m-2)*n*p|(m,n)<-l,let a#0=1;a#n=(a#div n 2)^2*a^mod n 2`mod`m;p=product(map fst l)`div`m]

Usage: f [(5,1), (73,4), (59,30), (701,53), (139,112)] -> 142360350966.
Edit: now with a fast "power/mod" function. Old version (68 bytes) with inbuilt power function:
f l=sum[l#m^(m-2)`mod`m*n*l#m|(m,n)<-l]
l#m=product(map fst l)`div`m

I suspect your implementation of power-mod is not polynomial-time since the exponent produces a huge number before the mod. Have you tried the last test case?

@xnor: the last test case runs out of memory after a few seconds on my 2GB machine. I've added a fast power/mod function.

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


text:
Generate a random floating point number between 2 limits
This challenge is to generate a random floating-point number between 2 limits.
You may use any language so long as it can be called from the command line, and runs on linux. It must also be able to work with negative numbers.
Due to the comment below: You may use fixed point math to come up with a result in-fact fixed point math is preferable in this case.
Input Requirements
Accept a lower and upper limit, no verification required.
Output Requirements

Must be between the 2 specified limits
Print it out to the console
or come up with a way to return it to the shell.

Example
$ prog -1 1
-.445

The program would not spit out a result that is not between those 2 limits.
And it would be inclusive of the 2 limits
Win Condition
As with all of these challenges the smallest number of bytes wins.

Can the first input be greater than the second?

@Zgarb so long as the output remains between the 2 limits

Does the random number have to be uniformly distributed between those limits, or will a non-uniform distribution do? And must every floating point number between those limits be a possible output? (If yes, that technically excludes most standard random number generator APIs, and will require considerable knowledge of the internals of the floating-point format to implement correctly. On the other hand, an unqualified "no" would seem to allow e.g. a solution that only ever returns one of the two limits, never anything in between.)

In particular, notably, due to the fact that floating-point numbers themselves are not uniformly distributed on the real number line, an RNG cannot satisfy more than two of the following three properties: 1) The distribution of the generated numbers approximates a continuous uniform distribution on the target interval. 2) Every floating-point number within the target interval is generated with a non-zero probability. 3) Every floating-point number that can be generated is generated with the same probability. Thus, you really should specify which (if any) of those properties you require.

Cjam, 9 bytes
q~1$-dmr+

Assumes that the first input number is the lower limit and the second one is the upper limit.
Pretty straight forward code:
q~          "Read the input as a string and evaluate it. This puts the two input";
            "integers on stack";
  1$        "Copy the first smaller integer and put it on top of stack";
    -       "Take difference of smaller and larger integer";
     d      "Convert the integer to double";
      mr    "Get a random double float from 0 to the difference of two integers";
        +   "Add the random double to the smaller integer to get random in range";

Try it online here

Ruby, 34 bytes
a,b=$*.map &:to_f
$><<a+(b-a)*rand

Takes inputs via command-line argument as in the usage example.

Pyth -  9 bytes
Works the obvious way like all the others.
+*-vzQOZQ

Pyth's random range function when called with zero as the argument acts as a [0, 1) floating point generator.
+          Add and implicitly print
 *         Times
  -        Difference
   vz      Input 1
   Q       Input 2
  OZ       Float RNG
 Q         Input 2

Try it here.

Nice. Completely missed, that random floats were added last week.

R, 34
Setup for running from command-line
i=scan('stdin');runif(1,i[1],i[2])

Takes input from STDIN
Example on windows
C:\Program Files\R\R-3.1.3\bin\x64>rscript -e "i=scan('stdin');runif(1,i[1],i[2])"
1
2
^Z
Read 2 items
[1] 1.249665

C:\Program Files\R\R-3.1.3\bin\x64>

As a note to the OP: When running an R script which reads from stdin on the command line, you have to submit Ctrl+Z (or Cmd+Z on Mac) to get it to stop reading from stdin.

C#, 142 141 bytes
C# has too much boilerplate...
Anyways, it is the only language I know and am sure can be compiled and run in Linux.
using System;class A{static void Main(string[]a){var b=double.Parse(a[0]);Console.Write(new Random().NextDouble()*(double.Parse(a[1])-b)+b);}

Ungolfed:
using System;
class A
{
    static void Main(string[] a)
    {
        var b = double.Parse(a[0]);
        Console.Write(new Random().NextDouble() * (double.Parse(a[1]) - b) + b);
    }
}

Also, I just noticed that every example's input was integral. In that case...
C#, 135 bytes, integral input
using System;class A{static void Main(string[]a){int b=int.Parse(a[0]);Console.Write(new Random().NextDouble()*(int.Parse(a[1])-b)+b);}

Ungolfed:
using System;
class A
{
    static void Main(string[] a)
    {
        int b = int.Parse(a[0]);
        Console.Write(new Random().NextDouble() * (int.Parse(a[1]) - b) + b);
    }
}

Just FYI, yes, C# can be compiled and run on Linux, but it requires Mono.


text:
Generate the galaxies of elite
Introduction
Elite was the first space trading video game, written and developed by David Braben and Ian Bell and published by Acornsoft for the BBC Micro and Acorn Electron computers in in September of 1984.

The Elite universe contains eight galaxies, each with 256 planets to explore. Due to the limited capabilities of 8-bit computers at the time, these worlds were procedurally generated. A single seed number is run through a fixed algorithm the appropriate number of times and creates a sequence of numbers determining each planet's complete composition (position in the galaxy, prices of commodities, and name and local details; text strings are chosen numerically from a lookup table and assembled to produce unique descriptions, such as a planet with "carnivorous arts graduates"). This means that no extra memory is needed to store the characteristics of each planet, yet each is unique and has fixed properties. Read more about this here: Elite random number generator

Challenge
Like the Elite game did, write a script which can procedurally generate a list of 8 galaxies each of which contains 256 planets. (You need to generate a total of 2048 planet names).
The 8 galaxy names can be defined before hand or procedurally generated. This is your choice.
Output

Please post your script here and perhaps use paste bin or an equivalent to host your output.

Rules

At a minimum your script must generate 2048 planet names and 8 galaxy names.
Each 256 planets should be nested within the array of a galaxy.
This is a popularity-contest! Try to make your code clever, interesting, slick or retro.
This is not code-golf. As such, readable code is appreciated. Still, try to keep size low remember the original programmers only had 32Kb or memory to work within for the whole game.
Repeats of planet names of more than 3 in a row is not allowed and a single planet name must not appear more than 5 times in the total 2048 planets.
Input is optional and not required.
Standard Loopholes apply.

How to get kudos

If your script also generates economy, government, tech level, population, gross productivity, average radius and comments about each planet.
If your planet names look organic (doesn't have to be in English) but for example 'Lave' looks better and is easier to read than 'Esdqzfjp'.
If your planet names don't contain profanity such "Arse". I only mention this because the original programmers had to do this.
If you do this challenge in BBC Basic.

I'm a little confused about the goal. Is it "produce 2056 random names"?

The goal is to produce 8 galaxies, each of which contains 256 planet names. Like the game did. That equals 2048 planet names to generate.

This reminds me of Oolite.

@TheBestOne Oolite is a copy of Elite.

I don't quite understand why this got put on hold? TheBestOne has come up with a pretty good solution. Let me know if I need to clarify anything. Seems quite straight forward to me.

I voted to close because, as Ypnypn said, the question asks to generate 2056 random names without any constraints, plus optionally "economy, government, tech level, population, gross productivity, average radius and comments about each planet." This is why closed as too broad. Please read the description of the close vote reason. This has nothing to do with the challenge being unclear. "There are either too many possible answers, or good answers would be too long for this format." (mostly the former.) Also getting a good answer doesn't mean the question isn't still too broad.

If the OP edits the question to be more specific, I'd be up for reopening.

The name generation by itself is close enough to http://codegolf.stackexchange.com/q/40682/194 to be a duplicate.

Java
I just though I would start out this contest with something :). The names are organic and are generated on the fly. Run with any arguments to use interactive mode.
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class Main {

    private final static int[][] frequencies = new int[][]{   //Generated with names from http://www.minorplanetcenter.net/iau/lists/MPNames.html
            {96, 323, 512, 445, 222, 113, 407, 249, 514, 134, 740, 1287, 975, 3188, 212, 235, 13, 2131, 997, 909, 501, 398, 226, 50, 355, 165, 3223},
            {626, 61, 8, 8, 877, 3, 3, 28, 322, 5, 7, 114, 9, 8, 425, 4, 0, 396, 44, 6, 260, 0, 7, 0, 51, 3, 40},
            {607, 4, 129, 16, 287, 9, 14, 1728, 248, 4, 364, 139, 9, 8, 518, 7, 18, 99, 27, 41, 94, 2, 0, 0, 49, 42, 102},
            {842, 49, 13, 46, 784, 17, 38, 45, 425, 18, 21, 65, 56, 31, 503, 10, 2, 224, 90, 70, 169, 13, 50, 0, 86, 37, 421},
            {326, 203, 264, 375, 284, 128, 231, 143, 513, 67, 261, 1436, 399, 1874, 159, 179, 9, 2873, 940, 680, 206, 402, 180, 64, 317, 125, 1527},
            {161, 7, 3, 1, 246, 170, 6, 6, 128, 5, 2, 61, 16, 5, 122, 3, 0, 253, 16, 28, 105, 3, 3, 0, 4, 0, 122},
            {596, 16, 27, 27, 595, 8, 62, 150, 250, 17, 16, 134, 32, 100, 319, 11, 6, 272, 53, 28, 258, 3, 18, 10, 46, 18, 507},
            {1360, 24, 33, 16, 1001, 2, 9, 14, 1219, 9, 55, 123, 93, 204, 683, 8, 0, 178, 55, 88, 383, 21, 50, 0, 96, 0, 453},
            {1104, 148, 802, 362, 646, 85, 333, 97, 47, 160, 477, 789, 486, 2022, 309, 149, 15, 501, 1007, 614, 137, 142, 65, 43, 146, 147, 1598},
            {309, 5, 6, 13, 183, 1, 2, 2, 224, 1, 15, 2, 4, 11, 354, 1, 0, 3, 15, 6, 132, 2, 0, 0, 8, 2, 103},
            {1094, 15, 10, 9, 614, 6, 7, 166, 718, 9, 39, 133, 32, 36, 737, 9, 0, 137, 92, 20, 343, 17, 25, 1, 153, 2, 494},
            {1219, 105, 66, 280, 1319, 87, 73, 55, 1259, 17, 77, 1034, 142, 35, 622, 80, 4, 38, 209, 146, 271, 67, 21, 0, 224, 33, 612},
            {1790, 139, 135, 14, 591, 6, 6, 21, 859, 9, 16, 16, 120, 23, 599, 121, 5, 24, 87, 11, 252, 3, 12, 0, 78, 7, 249},
            {1139, 159, 291, 744, 1103, 55, 881, 124, 1014, 72, 298, 80, 108, 519, 735, 52, 12, 110, 543, 495, 140, 27, 59, 10, 203, 120, 2308},
            {72, 299, 215, 258, 167, 138, 150, 288, 124, 62, 282, 824, 456, 1643, 200, 199, 5, 1054, 815, 457, 408, 698, 201, 26, 145, 96, 1181},
            {517, 9, 5, 2, 474, 17, 3, 204, 263, 0, 16, 95, 10, 6, 311, 131, 0, 147, 45, 34, 87, 0, 1, 0, 24, 2, 66},
            {1, 0, 0, 0, 1, 0, 0, 0, 30, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 116, 2, 1, 0, 0, 0, 5},
            {1518, 162, 175, 366, 1113, 44, 325, 86, 1469, 18, 204, 176, 211, 294, 1196, 58, 11, 294, 331, 505, 439, 57, 37, 4, 311, 44, 1349},
            {904, 66, 452, 26, 770, 22, 17, 935, 522, 13, 439, 132, 109, 56, 570, 131, 10, 28, 442, 932, 437, 46, 44, 0, 68, 50, 1616},
            {1009, 24, 60, 13, 1026, 20, 21, 607, 618, 29, 47, 74, 52, 35, 862, 12, 0, 399, 365, 481, 180, 18, 30, 1, 90, 125, 657},
            {164, 191, 273, 207, 233, 51, 186, 75, 170, 55, 238, 344, 292, 555, 55, 72, 5, 694, 672, 274, 13, 35, 23, 32, 76, 82, 421},
            {535, 3, 4, 4, 441, 0, 10, 3, 577, 1, 16, 28, 1, 12, 153, 4, 0, 26, 91, 4, 12, 1, 0, 0, 30, 1, 475},
            {516, 5, 2, 5, 289, 4, 2, 43, 290, 0, 17, 32, 11, 26, 109, 2, 0, 25, 57, 1, 33, 0, 1, 0, 13, 0, 49},
            {35, 2, 7, 2, 25, 2, 2, 3, 63, 1, 3, 5, 0, 0, 9, 1, 0, 4, 3, 5, 26, 1, 3, 0, 0, 0, 82},
            {557, 38, 55, 46, 138, 22, 26, 31, 72, 18, 44, 126, 75, 143, 238, 31, 1, 81, 108, 57, 214, 9, 27, 9, 6, 8, 706},
            {241, 12, 4, 22, 196, 0, 8, 146, 142, 0, 17, 11, 16, 15, 87, 2, 1, 11, 23, 11, 122, 10, 13, 0, 19, 49, 206},
            {1282, 1246, 1014, 818, 540, 466, 757, 928, 351, 680, 1207, 835, 1479, 552, 375, 957, 40, 795, 1710, 952, 150, 455, 435, 34, 288, 226, 0}
    };

    private final static int MIN_NAME_LENGTH = 4;

    private final static String INFO = "Type \"galaxy x\" to change galaxy. Type a number to get the name of that planet. Type \"exit\" or any invalid input to exit.";

    private final static Scanner in = new Scanner(System.in);
    private final static PrintStream out = System.out;

    public static void main(String[] args) throws Exception {

        if (args.length == 0){

            long seed = hash(System.nanoTime());

            for (int i = 0; i < 8; i++){

                long galaxySeed = (hash(i) ^ seed) + 1;
                out.println("Galaxy " + generateName(new Random(galaxySeed)));

                for (int j = 0; j < 256; j++){

                    long planetSeed = (hash(j) ^ galaxySeed) + 1;
                    out.println(generateName(new Random(planetSeed)));

                }
            }
            return;
        }

        out.println(INFO);

        out.println("Seed?");
        long seed = hash(in.nextLong());

        out.println("Galaxy?");
        long galaxySeed = hash(in.nextInt()) ^ seed;
        in.nextLine();//Get rid of rest of line.

        String galaxyName = generateName(new Random(galaxySeed));
        out.println("The name of your galaxy is " + galaxyName + ".");

        while (true){

            String input = in.nextLine().trim().toLowerCase();

            try {
                if (input.startsWith("galaxy")) {

                    int galaxy = Integer.parseInt(input.substring(6).trim());
                    galaxySeed = (hash(galaxy) ^ seed) + 1;

                    galaxyName = generateName(new Random(galaxySeed));
                    out.println("The name of your galaxy is " + galaxyName + ".");

                } else if (input.startsWith("exit")){
                    return;
                } else {

                    int planet = Integer.parseInt(input);
                    long planetSeed = (hash(planet) ^ galaxySeed) + 1;

                    String planetName = generateName(new Random(planetSeed));
                    out.println("The name of your planet is " + planetName + ".");

                }
            } catch (Exception e){
                return;
            }
        }

    }

    private static String generateName(Random rand) {

        int previousChar = randomIndex(frequencies[26], rand);
        String name = "" + (char)(previousChar + 'A');

        for (;;){

            int[] frequency = frequencies[previousChar].clone();

            frequency[26] *= Math.max(name.length() - (MIN_NAME_LENGTH - 1), 0) ; //Hack, reduces name lengths.

            int nextChar = randomIndex(frequency, rand);

            if (nextChar == 26){
                return name;
            }

            previousChar = nextChar;

            name += (char) (nextChar + 'a');
        }
    }

    private static int randomIndex(int[] frequencies, Random rand) {

        int total = Arrays.stream(frequencies).sum();

        int n = rand.nextInt(total);
        int i = 0;

        for (int frequency : frequencies){
            n -= frequency;
            if (n < 0){
                return i;
            }
            i++;
        }

        throw new IllegalStateException();
    }

    private static long hash(long i) {
        return (int) ((131111L*i)^i^(1973*i)%7919); //http://stackoverflow.com/a/9640543/4230423
    }
}

It uses the same code to generate galaxy names as planet names. Here are some example names:
Kanipeso
Danlerg
Deigaji
Kanialu
Fulla
Tirr
Smanger
Anikuraba
Dotia

For full output of 8 galaxies look here.


text:
Reconstruct a Permutation
Introduction
Suppose that you are handed a random permutation of n objects.
The permutation is sealed in a box, so you have no idea which of the n! possible ones it is.
If you managed to apply the permutation to n distinct objects, you could immediately deduce its identity.
However, you are only allowed to apply the permutation to length-n binary vectors, which means you'll have to apply it several times in order to recognize it.
Clearly, applying it to the n vectors with only one 1 does the job, but if you're clever, you can do it with log(n) applications.
The code for that method will be longer, though...
This is an experimental challenge where your score is a combination of code length and query complexity, meaning the number of calls to an auxiliary procedure.
The spec is a little long, so bear with me.
The Task
Your task is to write a named function (or closest equivalent) f that takes as inputs a positive integer n, and a permutation p of the first n integers, using either 0-based or 1-based indexing.
Its output is the permutation p.
However, you are not allowed to access the permutation p directly.
The only thing you can do with it is to apply it to any vector of n bits.
For this purpose, you shall use an auxiliary function P that takes in a permutation p and a vector of bits v, and returns the permuted vector whose p[i]th coordinate contains the bit v[i].
For example:
P([1,2,3,4,0], [1,1,0,0,0]) == [0,1,1,0,0]

You can replace "bits" with any two distinct values, such as 3 and -4, or 'a' and 'b', and they need not be fixed, so you can call P with both [-4,3,3,-4] and [2,2,2,1] in the same call to f.
The definition of P is not counted toward your score.
Scoring
The query complexity of your solution on a given input is the number of calls it makes to the auxiliary function P.
To make this measure unambiguous, your solution must be deterministic.
You can use pseudo-randomly generated numbers, but then you must also fix an initial seed for the generator.
In this repository you'll find a file called permutations.txt that contains 505 permutations, 5 of each length between 50 and 150 inclusive, using 0-based indexing (increment each number in the 1-based case).
Each permutation is on its own line, and its numbers are separated by spaces.
Your score is byte count of f + average query complexity on these inputs.
Lowest score wins.
Extra Rules
Code with explanations is preferred, and standard loopholes are disallowed.
In particular, individual bits are indistinguishable (so you can't give a vector of Integer objects to P and compare their identities), and the function P always returns a new vector instead of re-arranging its input.
You can freely change the names of f and P, and the order in which they take their arguments.
If you are the first person to answer in your programming language, you are strongly encouraged to include a test harness, including an implementation of the function P that also counts the number of times it was called.
As an example, here's the harness for Python 3.
def f(n,p):
    pass # Your submission goes here

num_calls = 0

def P(permutation, bit_vector):
    global num_calls
    num_calls += 1
    permuted_vector = [0]*len(bit_vector)
    for i in range(len(bit_vector)):
        permuted_vector[permutation[i]] = bit_vector[i]
    return permuted_vector

num_lines = 0
file_stream = open("permutations.txt")
for line in file_stream:
    num_lines += 1
    perm = [int(n) for n in line.split()]
    guess = f(len(perm), perm)
    if guess != perm:
        print("Wrong output\n %s\n given for input\n %s"%(str(guess), str(perm)))
        break
else:
    print("Done. Average query complexity: %g"%(num_calls/num_lines,))
file_stream.close()

In some languages, it is impossible to write such a harness.
Most notably, Haskell does not allow the pure function P to record the number of times it is called.
For this reason, you are allowed to re-implement your solution in such a way that it also calculates its query complexity, and use that in the harness.

Can we interpret “vector of bits” as “vector of two distinct items”, for instance, under this definition both abaaabababaa and -4 3 3 3 -4 3 would be a vector of bits.

@FUZxxl Yes, as long as the individual items are indistinguishable.

They are numbers in the implementation approach I have.

@FUZxxl I edited the spec.

J, 44.0693 22.0693 = 37 15 + 7.06931
If we can't call P on i. n, we can at least call P on each bit of i. n separately. The number of invocations of P is >. 2 ^. n (⌈log2 n⌉). I believe this is optimal.
f=:P&.|:&.#:@i.

Here is an implementation of the function P which uses the permutation vector p and saves the number of invocations into Pinv.
P =: 3 : 0"1
 Pinv =: Pinv + 1
 assert 3 > # ~. y    NB. make sure y is binary
 p { y
)

Here is a testing harness that receives a permutation and returns the number of invocations of p:
harness =: 3 : 0
 Pinv =: 0
 p =: y
 assert y = f # y     NB. make sure f computed the right permutation
 Pinv
)

And here is how you can use it on the file permutations.txt:
NB. average P invocation count
(+/ % #) harness@".;._2 fread 'permutations.txt'

Explanation
The short explanation is already provided above, but here is a more detailed one. First, f with spaces inserted and as an explicit function:
f =: P&.|:&.#:@i.
f =: 3 : 'P&.|:&.#: i. y'

Read:

Let f be P under transposition under base-2 representation of the first y integers.

where y is the formal parameter to f. in J, the parameters to a  (function) are called x and y if the verb is dyadic (has two parameters) and y if it is monadic (has one parameter).
Instead of invoking P on i. n (i.e. 0 1 2 ... (n - 1)), we invoke P on each bit position of the numbers in i. n. Since all permutations permute in the same way, we can reassemble the permutated bits into numbers to get a permutation vector:

i. y – integers from 0 to y - 1.
#: y – y represented in base 2. This is extended to vectors of numbers in the natural way. For instance, #: i. 16 yields:
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

#. y – y interpreted as a base 2 number. Notably, this is the inverse to #:; y ~: #. #: always holds.
|: y – y transposed.
u&.v y – u under v, that is vinv u v y where vinv is the inverse to v. Notice that |: is its own inverse.
P y – the function P applied to each vector in y by definition.

Pyth 32 + 7.06931 = 37.06931
I found the following algorithm completely independent. But it's more or less the same thing as FUZxxl very short J solution (as far as I understand it).
First the definition of the function P, which permutes an bit-array according to an unknown permutation.
D%GHJHVJ XJ@HN@GN)RJ

And then the code, that determines the permutation.
Mmxmi_mbk2Cm%dHCm+_jk2*sltG]0GdG

This defines a function g, that takes two arguments. You can call it by g5[4 2 1 3 0. Here's an online demonstration. Never used so many (5) nested maps.
Btw I haven't actually made a test harness. Neither does the function P count how many times I call it. I have spend way to much time already figuring out the algorithm. But if you read my explanation, it's quite obvious that it uses int(log2(n-1)) + 1 calls (= ceil(log2(n))). And sum(int(log2(n-1)) + 1 for n in range(50, 151)) / 101.0 = 7.069306930693069.
Explanation:
I actually had quite a hard time finding this algorithm. It was not clear to me at all, how to achieve log(n). So I started doing some experiments with small n.
First note: A bit-array gathers the same information as the complement bit-array. Therefore all bit-arrays in my solution have at most n/2 active bit.
n = 3:
Since we can only use bit-array with 1 active bit, the optimal solution depends of two calls. E.g. P([1, 0, 0]) and P([0, 1, 0]). The results tell us the first and second number of the permutation, indirectly we get the third one.
n = 4:
Here it get's a little bit interesting. We now can use two kinds of bit-array. Those with 1 active bit and those with 2 active bits. If we use a bit-array with one active bit, we only gather information about one number of the permutation, and fall back to n = 3, resulting in 1 + 2 = 3 calls of P. The interesting part is that we can do the same thing with only 2 calls, if we use bit-arrays with 2 active bits. E.g. P([1, 1, 0, 0]) and P([1, 0, 1, 0]).
Let's say we get the outputs [1, 0, 0, 1] and [0, 0, 1, 1]. We see, that the bit number 4 is active in both output arrays. The only bit that was active in both input arrays was bit number 1, so clearly the permutation starts with 4. Now it's easy to see, that bit 2 was moved to bit 1 (first output), and bit 3 was moved to bit 3 (second output). Therefore the permutation must be [4, 1, 3, 2].
n = 7:
Now something bigger. I'll show the calls of P immediately. They are the once, that I came up with after a little thinking and experimenting. (Notice these are not the ones, that I use in my code.)
P([1, 1, 1, 0, 0, 0, 0])
P([1, 0, 0, 1, 1, 0, 0])
P([0, 0, 1, 1, 0, 1, 0])

If in the first two output arrays (and not in the third) the bit 2 is active, we know that the permutation moves bit 1 to bit 2, since bit one is the only bit that is active in the first two input arrays.
The important thing is, that (interpreting the inputs as matrix) each of the columns are unique. This remembered me on Hamming codes, where the same thing is accomplished. They simply take the numbers 1 to 7, and use their bit-representation as columns. I'll use the numbers 0 to 6. Now the nice part, we can interpret the outputs (again the columns) as numbers again. These tell us the result of the permutation applied to [0, 1, 2, 3, 4, 5, 6].
   0  1  2  3  4  5  6      1  3  6  4  5  0  2
P([0, 1, 0, 1, 0, 1, 0]) = [1, 1, 0, 0, 1, 0, 0]
P([0, 0, 1, 1, 0, 0, 1]) = [0, 1, 1, 0, 0, 0, 1]
P([0, 0, 0, 0, 1, 1, 1]) = [0, 0, 1, 1, 1, 0, 0]

So we only have to trace back the numbers. Bit 0 ended up in bit 5, bit 1 ended up in bit 0, bit 2 ended up in bit 6, ... So the permutation was [5, 0, 6, 1, 3, 4, 2].
Mmxmi_mbk2Cm%dHCm+_jk2*sltG]0GdG
M                                 define a function g(G, H), that will return
                                  the result of the following computation:
                                  G is n, and H is the permutation.
                m            G     map each k in [0, 1, ..., Q-1] to:
                  _                   their inverse
                   jk2                binary representation (list of 1s and 0s)
                 +                    extended with
                      *sltG]0         int(log2(Q - 1)) zeros
               C                   transpose matrix # rows that are longer
                                                   # than others are shortened
           m%dH                    map each row (former column) d of
                                   the matrix to the function P (here %)
          C                        transpose back
   m                              map each row k to:
    i    2                           the decimal number of the
     _mbk                            inverse list(k) # C returns tuple :-(
Let's call the result X.
 m                             G   map each d in [0, 1, ..., Q - 1] to:
  x         X                 d       the index of d in X

And the code for the permutation function:
D%GHJHVJ XJ@HN@GN)RJ
D%GH                     def %(G, H):  # the function is called %
    JH                     J = copy(H)
      VJ         )        for N in [0, 1, ..., len(J) - 1]:
         XJ@HN@GN            J[H[N]] = G[N]
                  RJ      return J

If you replace *sltQ]0 with m0sltQ, you could have 6 nested maps at the same length.

You should, in accordance with the challenge, assign your code that solves the challenge to a function ideally named f although other names are permitted. The assignment counts towards your score.

@FUZxxl updated my code. Now defines a function g instead of reading from STDIN.

Mathematica, 63 + 100 = 163
I'm using one-based permutations, since that's how indexing works in Mathematica.
First, the test harness. This is the query function p (user-defined names shouldn't be upper-case in Mathematica):
p[perm_, vec_] := (
   i += 1;
   vec[[Ordering@perm]]
   );

And input preparation along with the test loop:
permutations =
  ToExpression@StringSplit@# + 1 & /@
   StringSplit[Import[
     "https://raw.githubusercontent.com/iatorm/permutations/master/permutations.txt"
   ], "\n"];
total = 0;
(
    i = 0;
    result = f@#;
    If[# != result,
      Print["Wrong result for ", #, ". Returned ," result ", instead."]
    ];
    total += i;
    ) & /@ permutations;
N[total/Length@permutations]

And finally, my actual submission which uses the naive algorithm for now:
f=(v=0q;v[[#]]=1;Position[q~p~v,1][[1,1]])&/@Range@Length[q=#]&

Or with indentation:
f = (
     v = 0 q;
     v[[#]] = 1;
     Position[q~p~v, 1][[1, 1]]
) & /@ Range@Length[q = #] &