Combination bike lock The scenario

After a long day's work slogging in the office and browsing stackexchange.com, I finally walk out the door at 16:58, already weary with the day. Because I am still only an intern, my current mode of transportation is on bicycle. I head over to my trusty Peugeot Reynolds 501, but before I can sail away on it, I need to unlock it. The lock is a standard four digit combination lock (0-9), through the frame and the front wheel. As I try to stay awake, I pull my hand up to enter in the combination.

The challenge

Because my fingers are so weary, I want to turn the lock to the correct combination with the fewest movements. One movement is defined as a rotation by one position (36 degrees), for example there is one movement from 5737 to 5738. However, I am able to grasp up to any three consecutive rings at the same time, and rotate them as one, which only counts as a single movement. For example there is also only one movement from 5737 to 6837 or to 5626. Moving from 5737 to 6838 is not one movement, as digits number 1,2 and 4 have moved in the same direction, but independently of digit number 3.

Therefore, for a given combination I can see on the bike lock (any 4-digit integer), what is the lowest number of movements I can make to get it unlocked, and yes, I can rotate in either direction at any time. By this I mean that I can turn some digits in one direction and other digits in the other direction: not all of my movements will be anitclockwise or clockwise for each unlock.

Because I am lazy, my unlock code is 0000.

This is code golf I can't be bothered writing much code, so the shortest program in number of bytes wins.

Input is from stdin, and your code should output the combinations I can see at each step after each movement, including the 0000 at the end. Each of the combinations output should be separated by a space/newline/comma/period/ampersand.

Examples

Input: 1210
0100
0000

Input: 9871
9870
0980
0090
0000

Input: 5555
4445&3335&2225&1115&0005&0006&0007&0008&0009&0000

Input: 1234
0124 0013 0002 0001 0000

I tried posting this on http://bicycles.stackexchange.com, but they didn't like it...

Disclaimer: First golf, so anything that is broken/any missing information let me know! Also I did all the examples by hand, so there may be solutions which involve less movements!

EDIT: For answers which have multiple solution paths with equal number of movements (practically all of them), there is no preferred solution.

Matlab, 412 327 bytes
Golfed (Thanks to @AndrasDeak for golfing s!):
s=dec2bin('iecbmgdoh'.'-97)-48;s=[s;-s];T=1e4;D=Inf(1,T);P=D;I=NaN(T,4);for i=1:T;I(i,:)=sprintf('%04d',i-1)-'0';end;G=input('');D(G+1)=0;for k=0:12;for n=find(D==k);for i=1:18;m=1+mod(I(n,:)+s(i,:),10)*10.^(3:-1:0)';if D(m)==Inf;D(m)=k+1;P(m)=n-1;end;end;end;end;n=0;X='0000';while n-G;n=P(n+1);X=[I(n+1,:)+48;X];end;disp(X)

This codes uses some dynamic programming for finding the shortest 'path' from the given number to 0000 using only the possible steps. The challenge is basically a shortest path prioblem (alternatively you could perhaps consider the steps as a commutatuve group.) but the difficulty was coming up with an efficient implementation. The basic structures are two 10000-element arrays, one for storing the number of steps to get to that index, the other one to store a pointer to the previous 'node' in our graph. It simultaneously calculates the 'paths' to all other possible numbers.
Examples:
9871
0981
0091
0001
0000

1210
0100
0000

Examples by @noisyass:

7478
8578
9678
0788
0899
0900
0000

3737
2627
1517
0407
0307
0207
0107
0007
0008
0009
0000

Own Example (longest sequence, shared with 6284)

4826
3826
2826
1826
0826
0926
0026
0015
0004
0003
0002
0001
0000

Full Code (inlcuding some comments):
%steps
s=[eye(4);1,1,0,0;0,1,1,0;0,0,1,1;1,1,1,0;0,1,1,1];
s=[s;-s];

D=NaN(1,10000);%D(n+1) = number of steps to get to n
P=NaN(1,10000);%P(n+1) was last one before n

I=NaN(10000,4);%integer representation as array
for i=0:9999;
    I(i+1,:)=sprintf('%04d',i)-'0';
end

G=9871; % define the current number (for the golfed version replaced with input('');
D(G+1)=0;
B=10.^(3:-1:0); %base for each digit

for k=0:100; %upper bound on number of steps;
    L=find(D==k)-1;
    for n=L; %iterate all new steps
        for i=1:18; %search all new steps
            m=sum(mod(I(n+1,:)+s(i,:),10) .* [1000,100,10,1]);
            if isnan(D(m+1))
                D(m+1) = k+1;
                P(m+1)=n;
            end
        end
    end
end
n=0;%we start here
X=[];
while n~=G
    X=[I(n+1,:)+'0';X];
    n=P(n+1);
end
disp([I(G+1,:)+'0';X,''])


Fun With Permutations Who doesn't absolutely love permutations, right? I know, they are amazing––so much fun!

Well, why not take this fun and make it funner?

Here's the challenge:

Given an input in the exact form: nPr, where n is the pool taken from and r is the number of selections from that pool (and n and r are integers), output/return the exact number of  permutations. For those of you that are a bit rusty with the terminology: Permutation, def. 2a.

However, this is where the challenge comes into play (makes it not too easy):

  You may not use any built in library, framework, or method for your permutation function. You may not use a factorial method, permutation method, or anything of the sort; you must write everything yourself.

If further clarification is needed, please, do not hesitate to tell me in the comments and I will promptly act accordingly.

Here is an I/O example:

Sample function is permute(String) -> int

Input:

permute("3P2")

Output:

6

This is code-golf, so shortest code wins!

CJam, 15 14 bytes

r~\;~\),>UXt:*

Try it online in the CJam interpreter.

How it works

r              e# Read a token ("nPr") from STDIN.
 ~             e# Evaluate. This pushes the numbers n, Pi and r on the stack.
  \;           e# Discard Pi.
    ~          e# Take the bitwise NOT of r. Pushes -(r+1).
     \)        e# Increment n.
       ,       e# Turn n+1 into [0 ... n].
        >      e# Keep only the last r+1 elements.
         UXt   e# Replace the first element with 1.
               e# This avoid dealing with the egde case nP0 separately.
            :* e# Compute their product.


A subset of Verbal arithmetic Implement a verbal arithmetic solver of several same sequence of numbers added together:

  TWO
+ TWO
-----
 FOUR

  REPEAT
  REPEAT
  REPEAT
+ REPEAT
--------
 ANDSTOP

  SPEED
+ SPEED
-------
  KILLS

There are some restrictions: each letter should represent different digits, and no letter can be zero.

Implement the solver as a function of the operands, the sum and number of repetitions returns a list of solutions (solution: the tuple of resulting operand and sum). For example:

f(['T','W','O'], ['F','O','U','R'], 2) == [(734, 1468)]

You do not need to represent variables as letters, and you do not need to use a hash in the solution.
Brute-force search allowed.

Shortest code wins.


The (Easy) Road to Code Input:

An integer \$n\$, which is guaranteed to be \$\ge3\$.
An integer \$d\$, which is one of \$[-1,0,1]\$.

Output:

A road of size \$n\$, which will be in a north-west direction if \$d=-1\$; a north direction if \$d=0\$; or a north-east direction if \$d=1\$. The road will always be three spaces wide (or five in general if we'd include the outer borders). In addition, there will be a road separator line on the bottom section, and after that alternating while going upwards.

Some examples:

Input: \$n=7, d=1\$
Output:

      / / /
     /   /
    / / /
   /   /
  / / /
 /   /
/ / /

Input: \$n=4, d=-1\$
Output:

\   \
 \ \ \
  \   \
   \ \ \

Challenge rules:

Any amount of leading/trailing spaces and/or newlines are acceptable, as long as it prints the required road somewhere on the screen.
Instead of the options \$[-1,0,1]\$ you are also allowed to use the options \$[0,1,2]\$ or \$[1,2,3]\$ instead. Also, you can choose which of the three options map to which of the three directions. (Make sure to mention which options you've used if it differs from the \$[-1,0,1]\$ for [north-west, north, north-east] respectively that is used in this challenge description!)
Any reasonable output format is acceptable. The most common is of course to print it to STDOUT, but returning it as a string or 2D character list is fine as well.

General rules:

This is code-golf, so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
Default Loopholes are forbidden.
If possible, please add a link with a test for your code (i.e. TIO).
Also, adding an explanation for your answer is highly recommended.

Test cases:

The two examples above, and:

Input: \$n=10, d=0\$
Output:

|   |
| | |
|   |
| | |
|   |
| | |
|   |
| | |
|   |
| | |

Python 2, 79 78 73 72 bytes

n,d=input()
c='|\/'[d]
i=n
while i:print' '*(n-i*d)+c,i%2*c or' ',c;i-=1

Try it online!

Takes [1,0,-1] for [north-west, north, north-east]

-1 byte, thanks to Neil


Efficient Bytewise FizzBuzz Given the following Python "reference implementation" of non-terminating FizzBuzz:
i=1
while True:
    if i%15 == 0:
        print("FizzBuzz")
    elif i%3 == 0:
        print("Fizz")
    elif i%5 == 0:
        print("Buzz")
    else:
        print(i)
    i += 1

We can represent its output as an infinite array of chars/bytes (assuming \n line terminators) that looks like the following:
['1', '\n', '2', '\n', 'F', 'i', 'z', 'z', '\n', '4', '\n', 'B', 'u', 'z', 'z', '\n', 'F', 'i', 'z', 'z', ...]

Your task is to write the shortest function or program that returns the character at the Nth index of this array.
Sounds easy? Your code should also work for extremely large values of N, for example 1e100.
It is possible to calculate the Nth byte of this output array in O(log(n)) time (or possibly better) - how is left as an exercise for the reader.
Your solution must run in O(poly(log(n))) time (or better). There is no hard execution time limit, but as a rough guideline you should be able to solve the N=1e100 case almost instantaneously.
This is code-golf: the shortest code in bytes wins.
Test cases:
f(0)      == '1'
f(1)      == '\n'
f(2)      == '2'
f(10)     == '\n'
f(100)    == '\n'
f(1000)   == 'z'
f(100000) == 'F'
f(1e10)   == '5'
f(1e100)  == '0'

Some more, randomly generated testcases: https://gist.github.com/DavidBuchanan314/65eccad5032c427218eb9c269b55e869
Note: these test cases are correct to the best of my knowledge. If you have contradictory findings, I am open to discussion.

JavaScript (Node.js), 145 bytes
Saved 2 bytes thanks to @user202729
Expects a BigInt. Outputs # instead of \n for readability.
f=(n,k=0n,p=10n**k,x=55n+8n*k,q=p*3n/5n*x||30n)=>n<q?(g=p=>j--&&([["Fizz"][p%3n]]+[["Buzz"][p%5n]]||p)+'#'+g(++p))(p+n/x*(j=15n))[n%x]:f(n-q,-~k)

Try it online!
How?
Method
We use a recursive function that quickly computes the number of characters required to build all blocks of 15 terms using numbers of \$1\$, \$2\$, ..., \$N\$ digits. This takes \$\approx \log(n)\$ iterations, where \$n\$ is the input.
The only block that is explicitly generated is the last one, which contains the character we're looking for.
Formulae
Below is the template of a block of 15 terms of the sequence, where # is the separator and @ is a placeholder for a full number. (Note that the leading term modulo \$15\$ can be anything between \$0\$ and \$14\$. The length of the block doesn't depend on that.)
        <--------- 55 characters and 8 full numbers ---------->
        FizzBuzz#@#@#Fizz#@#Buzz#Fizz#@#@#Fizz#Buzz#@#Fizz#@#@#
        ^        ^ ^ ^    ^ ^    ^    ^ ^ ^    ^    ^ ^    ^ ^
mod 15: 0        1 2 3    4 5    6    7 8 9    10  11 12  13 14

All terms in such a block are meant to have the same number of digits \$k+1\$. For \$k>0\$, the length of the block is \$55+8k\$ characters. For \$k=0\$, we can only build a partial block of 9 terms whose length is \$30\$ characters:
<------ 30 characters ------->
1#2#Fizz#4#Buzz#Fizz#7#8#Fizz#

The number of terms with \$k+1\$ digits is \$9\times 10^k\$.
The number of blocks with \$k+1\$ digits is:
$$\left\lceil10^k\times\dfrac{9}{15}\right\rceil=\left\lceil10^k\times\dfrac{3}{5}\right\rceil$$
(where the ceiling is only needed for \$k=0\$)
And the number of characters is:
$$\cases{
30&k=0\\
10^k\times\dfrac{3}{5}\times (55+8k)&k>0
}$$
Commented
f = (                      // f is a recursive function taking:
  n,                       //   n = input
  k = 0n,                  //   k = exponent
  p = 10n ** k,            //   p = 10 ** k
  x = 55n + 8n * k,        //   x = length of a block of 15 terms, using numbers of
                           //       k + 1 digits
  q = p * 3n / 5n * x      //   q = number of characters added when all numbers of
      || 30n               //       k + 1 digits are used (p = 1 is an edge case)
) =>                       //
n < q ?                    // if n is less than q:
  ( g = p =>               //   g is a recursive function that builds the block of 15
                           //   terms in which lies the character we're looking for
    j-- &&                 //     abort if j = 0 (decrement it afterwards)
    (                      //     otherwise:
      [["Fizz"][p % 3n]] + //       append 'Fizz' if p is a multiple of 3
      [["Buzz"][p % 5n]]   //       append 'Buzz' if p is a multiple of 5
      || p                 //       append p if it's neither a multiple of 3 or 5
    ) + '#' +              //       append the separator
    g(++p)                 //       append the result of a recursive call to g
  )(p + n / x * (j = 15n)) //   initial call to g: we set j to 15 and add to p the
                           //   number of terms that can be generated with n
                           //   characters, using only full blocks of 15 terms
  [n % x]                  //   extract the character at n modulo x
:                          // else:
  f(n - q, -~k)            //   recursive call to f with n - q and k + 1


Schedule a 4-way stop A bunch of cars are lined up at a 4-way stop sign waiting to proceed.  Everyone is confused about who gets to go next, who is going which way, etc.  Clearly suboptimal.

Your job is to schedule the traffic at the stop sign in an optimal fashion.

You receive as input 4 strings of turn requests, one for each of the four cardinal directions.  Each request is either L for left, S for straight, or R for right.

LLSLRLS
SSSRRSRLLR
LLRLSR
RRRLLLL

The first row is the lineup at the North entrance to the intersection.  The first car in line wishes to turn left (that is, exit East).  The subsequent rows are for the incoming East, South, and West entrances.  So the first car coming from the West wishes to exit South.

Traffic moves in a series of steps.  At each step, you must choose a subset of the cars at the head of their lines to proceed.  The cars chosen must not interfere with each other.  Two cars interfere if they exit the same direction or if they must cross each other's path (given standard right-hand driving rules).  So two opposite cars both wishing to go straight may go at the same step.  So may 4 cars all wishing to turn right.  Two opposite cars can both turn left simultaneously.

Your job is to schedule the intersection in a minimum series of steps.  For each step, output a line with the incoming cars' compass direction(s) listed.  For the example above, the minimal schedule is 14 steps.  One minimal schedule is:

N    [L from North]
E    [S from East]
E    [S from East]
E    [S from East]
NESW [L from North, R from East, L from South, R from West]
NE   [S from North]
EW   [R from East]
NESW [L from North, R from East, L from South, R from West]
W    [L from West]
EW   [L from East, L from West]
NESW [R from North, L from East, R from South, L from West]
NES  [L from North, R from East, L from West]
NS   [S from North, S from South]
SW   [R from South, L from West]

Your program should be able to handle 50 cars in each line in under 1 minute.  Input of the 4 strings and output of the schedule may be in any convenient manner for your language.

Shortest program wins.

A larger example:

RRLLSSRLSLLSSLRSLR
RLSLRLSLSSRLRLRRLLSSRLR
RLSLRLRRLSSLSLLRLSSL
LLLRRRSSRSLRSSSSLLRRRR

which requires a minimum of 38 rounds.  One possible solution:

E
EW
E
ESW
S
NS
ES
NESW
NSW
ESW
ES
NSW
NS
NS
NW
EW
NSW
NS
EW
NES
EW
NSW
NE
E
NE
EW
E
E
EW
EW
EW
W
ESW
NSW
NSW
NS
NSW
NEW

Python, 1219 Bytes

I didn't spend very much time/effort trying to golf this, but I might improve it if other answers start popping up.  I use A* search with an admissible heuristic, guaranteeing optimality.  I am pretty sure (although I haven't bothered to confirm) that the heuristic is also consistent, meaning that it is O(dynamic programming).

The program reads in four lines from STDIN in the format you have specified, and prints the result to STDOUT, also in the format you specified.

from heapq import heappush,heappop
from itertools import combinations
N,E,S,W=range(4)
L="L"
R="R"
T="S"
d=[{L:E,R:W,T:S},{L:S,R:N,T:W},{L:W,R:E,T:N},{L:N,R:S,T:E}]
b=set([(N,S,W,E),(N,S,E,W),(S,N,W,E),(S,N,E,W),(E,W,N,E),(N,S,W,N),(S,N,E,S),(W,E,S,W)])
for x in list(b):b.add(x[2:]+x[:2])
def v(*a):return a[1]!=a[3] and a not in b
i=lambda:raw_input()+'\n'
i=map(lambda l:map(lambda e:("NESW"[l[0]],d[l[0]][e]), l[1]),enumerate((i()+i()+i()+i()).split()))
q=[]
heappush(q,(0,[],i))
while q:
    h,a,n=heappop(q)
    m=sum(map(bool,n))
    if m==0:
        print "\n".join(a)
        break
    for r in range(4,0,-1):
        f=False
        for c in combinations(range(4),r):
            l=True
            for i in c:
                if not n[i]:
                    l=False
                    break
            if not l:continue
            l=True
            for x,y in combinations(c,2):
                if not v(x,n[x][0][1],y,n[y][0][1]):
                    l = False
                    break
            if l==False:continue
            f=True
            e=list(n)
            for i in c:e[i]=e[i][1:]
            heappush(q,(m-r+min(map(len,e)),a+["".join([n[x][0][0] for x in c])],e))
        if f:break

Example usage:

$ time echo "RRLLSSRLSLLSSLRSLR\nRLSLRLSLSSRLRLRRLLSSRLR\nRLSLRLRRLSSLSLLRLSSL\nLLLRRRSSRSLRSSSSLLRRRR" | python 4way.py
NES
NEW
NSW
NS
NS
ESW
NS
NES
NEW
NS
NES
NSW
NS
NS
NSW
NW
NS
NS
NS
EW
ES
SW
EW
EW
SW
ES
EW
EW
EW
EW
E
EW
EW
EW
EW
EW
E
EW
echo   0.00s user 0.00s system 38% cpu 0.002 total
python 4way.py  0.02s user 0.01s system 90% cpu 0.030 total


Convert Fractran into Brainfuck Background

Fractran is an esoteric Turing-complete programming language invented by John Conway. A Fractran program consists of an ordered list of fractions. The program starts by taking a single integer as input. Each iteration of the program, it searches the list for the first fraction such that multiplying the number by that fraction produces another integer. It then repeats this process with the new number, starting back at the beginning of the list. When there is no fraction on the list that can be multiplied with the number, the program terminates and gives the number as the output.

The reason that Fractran is Turing-complete is because it simulates a register machine. The number's prime factorization stores the contents of the registers, while the division and multiplication is a way to conditionally add and subtract from the registers. I would recommend reading the Wikipedia article (linked to above).

The Challenge

Your task is to write the shortest program possible that can take a valid Fractran program from STDIN as its only input and generates a valid BF program to STDOUT that simulates the Fractran program. There are two ways that you could simulate a Fractran program with BF.

NOTE: Your answer is not a BF program. Your answer is the code that generates the BF program from any given Fractran program. The goal is to get the BF program to be the equivalent of the Fractran program. (technically you could do the competition in BF, but it would be hard)

Option 1

Your program should output a BF program that does the following:

Takes exactly 1 number from STDIN in the form of the corresponding ASCII character (due to the way that BF input works), which is the input to the Fractran program.
Prints exactly 1 number to STDOUT in the form of the corresponding ASCII character, which is the output to from the Fractran program.

This option is meant to represent the exact input and output from a Fractran virtual machine.

Option 2

The BF code that your program produces should do the following:

Take input by having the prime factorization of the number already encoded in memory (prior to running the program). If the input is 28 (2*2*7), then there will be a value of 2 in the second cell and a value of 1 in the seventh cell (the pointer starts on cell 0). All other cells will be zero.
Give output by having the prime factorization of the output encoded in memory when the program terminates. If the output is 10, then there must be a value of 1 in each of cells 2 and 5. All other prime-numbered cells must have a value of zero. The content of other cells do not matter.

This option represents the computing model behind the Fractran language.

Rules and Requirements

Input (top your program) will be a list of fractions on STDIN. There will be one fraction per line with a comma between the numerator and denominator. An empty line represents the end of input. The fractions will always be reduced to lowest terms.
Your program's output should be a single-line, valid BF program to STDOUT. This program should be able to simulate that particular Fractran program according to one of the two options. For any input, the BF program generated should be able to produce the same output as the Fractran program.
You must state which option you chose.
You can choose the bounds on the BF memory and tape, and whether they are wrapping
CODE GOLF.  Also, the size of the outputted BF programs does not matter, only the size of the program that is doing the converting.
Programs should only consist of printable ASCII

If I am ambiguous anywhere, do not hesitate to ask. This is a very complicated challenge to describe.

In addition, please post your program's generated BF code for the following input, as to provide an easy way to check if your program is working:

33,20
5,11
13,10
1,5
2,3
10,7
7,2

This program calculates the number of 1s in the binary expansion of a number. However, the input and output are formatted strangely (as with all Fractran programs). Input is of the form 2^A, while output is of the form 13^B.


Solve a reverse arrow maze This is an "arrow maze":

  v      <
>     v
      >  ^
>         v
^ <       *

The * marks the spot where you will finish. Your goal is to find where the maze starts (hence, reverse maze). In this case, it's the first > on the second line.

  v------<
S-+---v  |
  |   >--^
>-+-------v
^ <       *

Note that all arrows must be used. Also note that you can assume the lines will be padded with spaces to equal length.

Your program must input the maze in any reasonable way (stdin, from a file, message box, etc.), however the maze must be completely intact. For example, you can't input the lines separated by commas; the input must be exactly the maze.

You must output the start of the maze in any reasonable way. For example, you could

output the coordinates of the start
output the entire maze with the start arrow replaced with an S
output the entire maze with all arrows except the start arrow removed (whitespace intact!)
etc.

As long as you can tell by your output which arrow is the start arrow, then it's okay. For example, an output of

"0"
"2"

is alright, regardless of the newlines and quotes, because you can still tell where the start was.

This is code-golf, so the shortest code in bytes will win.

GolfScript (101 100 bytes)

n/:g,,{:&g=:r,,{&1$r='^v<>*'?70429 3base 2/=++}/}%{,4=},.{2<}%:&\{2/~\{[~2$~@+(@@+(\]&1$?)!}do\;}%^`

Output is in the form [[x y]] where the co-ordinates are both 0-based.

Online demo

Processing is in two phases: the first phase turns the maze into an array of [x y dx dy] tuples; the second phase maps each arrow / asterisk to the arrow / asterisk it points to. (Asterisks are considered to point to themselves). By the definition of the problem, there is exactly one arrow which isn't in the result of this map, and that is the solution.


Extendable Train Swapping Problem Extended Train Swapping Problem

Part 1: Normal Train Swapping Problem

In the 1996 CCC (Canadian Computing Competition), the first Stage 2 problem was a Train Swapping Problem. You can visit the link here. Essentially, you have a bunch of numbered trains, and you want to find out how many train swaps you need to get them in order, and each train swap operation allows you to swap two adjacent trains. Since train carriages can run either way, nobody cares about the fact that the train carriages face the other way when swapped. This is pretty easy; all you need to do is:

   Find the number of steps to bubble-sort it; it's the most efficient sorting algorithm when you can only make adjacent element swaps

So, I made a harder one.

Part 2: How this challenge works

Essentially, you can now swap more than just adjacent trains. With a longer rotating platform, you can swap the position of multiple trains. For example, with a rotating platform of length 4, you can swap both the inner and outer pairs at the same time, so 1 2 3 4 becomes 4 3 2 1. Here are some examples for different rotating platform sizes:

Length 2:
1 2 3 4 5
  ---
1 3 2 4 5

Length 3:
1 2 3 4 5
  -----
1 4 3 2 5

Length 4:
1 2 3 4 5
-------
4 3 2 1 5

Essentially, you're just inverting a sublist of the entire train. To clarify, in each move, you can only swap exactly N trains.

Part 3: Specifications

Input

Your input must take in two things: the length of the rotating platform, and the order of the train carriages. You may also require the number of train carriages if you wish. The order of the train carriages is given by an ordered list of numbers (each number representing a train carriage), so you can read the input as space-separated integers, newline-separated integers, an array, etc.

Output

You must output the optimal (minimum) number of swaps needed to get the carriages all into the order 1 2 3 ... N. If there is no solution, output -1, No solution, or some other consistent message. You may not output to stderr.

Scoring

This is a code-golf challenge, so scoring is in bytes. The solution with the lowest number of bytes as of September 1st, 2016 will be the accepted one.

Examples

Problem 1
Input

4
2
1 3 2 4

Output

1

Explanation
This is pretty trivial; with a rotating platform of length 2, it's the same as the normal train swapping problem. Swap the 2 and the 3.

Problem 2
Input

4
3
1 3 2 4

Output

No solution (or an equivalent consistent message).

Problem 3
Input

9
3
1 4 5 6 3 8 7 2 9

Output

4

Explanation

1 4 5 6 3 8 7 2 9
          -----
1 4 5 6 3 2 7 8 9
      -----
1 4 5 2 3 6 7 8 9
    -----
1 4 3 2 5 6 7 8 9
  -----
1 2 3 4 5 6 7 8 9

Standard loopholes apply

Good luck!

EDIT 1: Made the input format more flexible. Thanks to @Mego!
EDIT 2: Clarified that a rotating platform of length 4 swaps both the inner and outer pairs. Thanks to @TimmyD!
EDIT 3: Clarified that you must make permutations of length N exactly, not at most. Thanks to @Zgarb!

Perl, 120 bytes

Includes +6 for -Xapi (- and space are counted too because both the -i and the $' in the code make it impossible to combine the options with -e)

Run with the input on STDIN and the platform length after the -i option, e.g.

perl -Xapi3 trains.pl <<< "1 4 5 6 3 8 7 2 9"

Prints -2 if there is no solution

trains.pl:

1until$_=$n++*$z{pack"W*",@F}||-!grep!$z{$_}++&&/.{$^I}(??{!\$z{$`.reverse($&).$'}})$/s,keys%z,pack"W*",1..@F;$_--

if N <= 9 then you can gain 5 more bytes:

1until$_=$n++*$z{join"",@F}||-!grep!$z{$_}++&&/.{$^I}(??{!\$z{$`.reverse($&).$'}})$/,keys%z,join"",1..@F;$_--


Emotion, 17 bytes

Explanation
 Push literal 280
 Enter an iteration block over the first stack value and push the iteration element register at the begining of each loop.
 Push literal 1
 Push the sum of the second and first stack values.
 Push literal 1114112
 Swap the top two stack values.
 Push the first stack value to the power of the second stack value.
 Push the sum of the second and first stack values.
 Ends a control flow structure.

Try it online!


Composing fill in the blanks Let us say that we have a particular set of functions on strings.  These functions are kind of like fill in the blanks or madlibs, except that they only take one input and use that to fill in all of their blanks.  For example we might have a function that looks like

I went to the ____ store and bought ____ today.

If we applied this function to the string cheese the result would be:

I went to the cheese store and bought cheese today.

We can represent these functions as a non-empty list of strings, where the blanks are simply the gaps in between strings.  For example our function above would be:

["I went to the ", " store and bought ", " today."]

With this representation there is only one representation for every function of this sort and only one function for each representation.

A really neat thing is that the set of such functions is closed under composition.  That is to say composition of two of our functions is always another one of these functions.  For example if I compose our function above with

["blue ", ""]

(the function that prepends blue to the input)
We get the function:

["I went to the blue ", " store and bought blue ", " today."]

These can get a little more complex though.  For example if we compose the first function with

["big ", " and ", ""]

The result is

["I went to the big ", " and ", " store and bought big ", "and", " today."]

Task

Your task is to take two functions as described as non-empty lists of strings and output their composition as a non-empty list of strings.

For the purpose of this challenge a list can be any ordered container that permits
duplicates and a string may be a native string type, a list of characters or a list of integers.

This is code-golf answers will be scored in bytes with fewer bytes being better.

Test cases

["","xy"] ["ab",""] -> ["ab","xy"]
["x","y","z"] ["a","b"] -> ["xa","bya","bz"]
["xy"] ["ab"] -> ["xy"]
["","",""] ["a",""] -> ["a","a",""]
["x",""] ["","",""] -> ["x","",""]
["x","y","z"] ["a","b","c"] -> ["xa","b","cya","b","cz"]
["x","x","x"] ["a"] -> ["xaxax"]
["w","x","y","z"] ["ab","cd","e"] -> ["wab","cd","exab","cd","eyab","cd","ez"]

Jelly, 6 bytes

j0j@ṣ0

A dyadic Link accepting the first function representation on the right and the second function representation on the left which yields the resulting function representation. Each function representation is a list of lists of characters (Jelly has no other strings).

Try it online! (the full-program arguments are given in Python notation; strings become lists. The footer shows a Python representation of the Link's output.)

Here is a test-suite which reformats the Link's output like the inputs.

How?

Takes advantage of Jelly's mixed type lists to allow the entire domain of representations (any list of lists of characters) by using the integer zero as a place-holder:

j0j@ṣ0 - Link: b, a        e.g.    b = [['a','b'],['c','d'],['e']]
       -                   ...and  a = [['w'],['x'],['y'],['z']]
                             (i.e. test-case ["w","x","y","z"] ["ab","cd","e"])
j0     - join b with zeros         ['a','b',0,'c','d',0,'e']
  j@   - join a with that          ['w','a','b',0,'c','d',0,'e','x','a','b',0,'c','d',0,'e','y','a','b',0,'c','d',0,'e','z']
    ṣ0 - split at zeros            [['w','a','b'],['c','d'],['e','x','a','b'],['c','d'],['e','y','a','b'],['c','d'],['e','z']
                             (i.e.: ["wab","cd","exab","cd","eyab","cd","ez"])

If we needed to deal with any of Jelly's mixed lists (including those of any depth or shape) we could use this eight byter: j,©⁹jœṣ® which uses the paired arguments as the place-holder.


Turn me 22.5 with a rose Given a string that is one of the directions on a 16-point compass rose

output the two directions that are immediately adjacent to the input direction, in clockwise order.

Specifically, you need to handle these (and only these) input/output pairs:

Input  Output
N      NNW NNE
NNE    N NE
NE     NNE ENE
ENE    NE E
E      ENE ESE
ESE    E SE
SE     ESE SSE
SSE    SE S
S      SSE SSW
SSW    S SW
SW     SSW WSW
WSW    SW W
W      WSW WNW
WNW    W NW
NW     WNW NNW
NNW    NW N

The output may be a string with some delimiter (not nothing) between the directions or a two-element list. The direction immediately counterclockwise to the input must appear first. You may use lowercase letters for the directions instead of uppercase but keep all input and output in one case or the other.

For example, for input N (or n if you're using lowercase) some valid outputs are:

NNW NNE
NNW-NNE
["NNW", "NNE"]
nnw-nne (if using lowercase)

Some invalid outputs are:

NNWNNE
NNE NNW
nnwNNE
NNw NNe

The shortest code in bytes wins.

Jelly, 37 34 bytes

“¢ ¬9£Hæz¥{çb¤S®!‘ṃ€“¡&¦»
¢iµ’,‘ị¢

Try it online!

Takes lowercase input.

-2 thanks to Jonathan Allan.
-1 since it turns out this is valid as a function :)

Thanks to Jonathan Allan (and Dennis), now you can remove the €. Unfortunately, that would be non-competing here.

Detailed algorithm explanation:

We usually start explaining from the bottom (main) link, going down, but here I feel like it's more appropriate to explain from the top.

First, we simply load up the list [1, 32, 7, 57, 2, 67, 17, 92, 3, 94, 19, 119, 4, 109, 9, 34]. This looks like random numbers huh? Well, this is actually a list of base-5-compressed numbers, so we base-5-decompress it. Now it looks like [[1], [1, 1, 2], [1, 2], [2, 1, 2], [2], [2, 3, 2], [3, 2], [3, 3, 2], [3], [3, 3, 4], [3, 4], [4, 3, 4], [4], [4, 1, 4], [1, 4], [1, 1, 4]]. Still random-looking stuff, but this is actually an NESW-mapped list of the sixteen coordinates, so we're not far away from completing the list (Jelly is 1-indexed). Doing the final mapping, we get [['N'], ['N', 'N', 'E'], ['N', 'E'], ['E', 'N', 'E'], ['E'], ['E', 'S', 'E'], ['S', 'E'], ['S', 'S', 'E'], ['S'], ['S', 'S', 'W'], ['S', 'W'], ['W', 'S', 'W'], ['W'], ['W', 'N', 'W'], ['N', 'W'], ['N', 'N', 'W']], which is the complete list we want (Jelly strings are in the form [char1, char2, char3, ...].)

Since we've now built the coordinate list, we work with it. The main link comes into play. First, we load up the list we've built, and then take the index that the input (as command-line argument) coordinate resides in. Then, we pair its predecessor and its successor into a list, and we use them as modular indices into the same list of coordinates to take the coordinate to the left and right of the input respectively. You'd now think we're finally done, but there's in fact one more thing, the separator. This is valid as a function, since 1) You can call it using <integer>Ŀ 2) You're allowed to define other functions as well (like importing modules). Now, we are done. As a full program, this doesn't have a separator, but that's OK, since it works as a function.

Link-by-link code explanation:

¢iµ’,‘ị¢K Main link. Arguments: z = cmd0
¢         Run the helper link niladically (i.e. load the coordinate list).
 i        Find the index of z in the list.
  µ       Start a new monadic chain. Arguments: z = list_index.
   ’      Decrement z.
     ‘    Increment z.
    ,     Pair x and y into [x, y].
       ¢  Run the helper link niladically.
      ị   Take the elements of y at the indices in x.

“¢ ¬9£Hæz¥{çb¤S®!‘ṃ€“¡&¦» Helper link. Arguments: [1, 32, 7, 57, 2, 67, 17, 92, 3, 94, 19, 119, 4, 109, 9, 34]
“¢ ¬9£Hæz¥{çb¤S®!‘        Generate the integer list (the argument).
                    “¡&¦» Literal "newsy".
                  ṃ€      Base-length(y)-decompress every integer in x, then index into y.


Shuffle Up and Deal! It is Friday and I am tired, so let's do a quick one! Take no input, however you should output all thirteen different numbered cards in a standard deck of cards. You should output 2 through Ace (Suit agnostic).

Each card has a top that is denoted with a space   and ten _ and another space .

The second row from the top is denoted with a / and ten spaces   and a \

The third row is the same as all the middle-ish rows excepts the character(s) denoting the card value appear two spaces to right (if at the top) or two space to the left (if at the bottom) of the edge.

Each middle-ish row is a simple | and ten spaces   and one more |

Finally the last line is a \ and ten _ and finally a /

If the value is multi-digit the overall width by height of the card should not change. (i.e. the 10 will not make the card's sides wider)

King Example:

 __________
/          \
| K        |
|          |
|          |
|          |
|          |
|          |
|        K |
\__________/

9 Example

 __________
/          \
| 9        |
|          |
|          |
|          |
|          |
|          |
|        9 |
\__________/

10 Example

 __________
/          \
| 10       |
|          |
|          |
|          |
|          |
|          |
|       10 |
\__________/

Output them in order from least to greatest (Aces are high!).

This is code-golf so the shortest code wins.

Have fun and have a fun weekend!

PowerShell v2+, 120 116 114 108 bytes

2..10+[char[]]'JQKA'|%{$z=' '*(8-!($_-10));$x='_'*10;$y=' '*10;" $x
/$y\
| $_$z|";,"|$y|"*5;"|$z$_ |
\$x/"}

Constructs a range 2..10 and does array concatenation with char-array JQKA. Feeds that into a loop |%{...}. Each iteration, we set $z equal to an appropriate number of spaces (based on whether we're at card 10 or not), set $x to 10 underscores, and set $y to 10 spaces.

Then, we begin our placements. We're going to leverage the default Write-Output to insert a newline between pipeline elements, so we just need to get the stuff on the pipeline. Note that in most places, we're using a literal newline rather than closing and reopening our strings to save a couple bytes.

The first is just $x with two spaces, then $y with two slashes, then the | $_$z|" the pipe, a space, the appropriate number of spaces, and another pipe. This forms the top of the cards up to and including the value line.

We have to semicolon here, since the next uses an array. The ,"|$y|"*5 constructs a string-array, with the comma-operator, of the pipe with spaces - on output, each element of this array gets a newline for free.

Then, the "|$z$_ | for the bottom value marking, and finally $x with slashes for the bottom of the card.

Output Snippet

PS C:\Tools\Scripts\golfing> 2..10+[char[]]'JQKA'|%{$z=' '*(8,7)[$_-eq10];" $(($x='_'*10)) ";"/$(($y=' '*10))\";"| $_$z|";,"|$y|"*5;"|$z$_ |";"\$x/"}
 __________
/          \
| 2        |
|          |
|          |
|          |
|          |
|          |
|        2 |
\__________/
 __________
/          \
| 3        |
|          |
|          |
|          |
|          |
|          |
|        3 |
\__________/
 __________
/          \
| 4        |
...


Finding your partner Challenge

Given an arbitrary list of 2-tuples, and a single element in one of those tuples, output its "partner", i.e. given a and [(i,j),...,(a,b),...,(l,m)], output b. You can assume all tuples are unique, and that all elements in tuples are strings. Further assume you do not have both (x,y) and (y,x).

Test cases

Input                                                           Output

[("(", ")"), ("{", "}"), ("[", "]")], "}"                       "{"
[("I'm", "So"), ("Meta", "Even"), ("This", "Acronym")], "Even"  "Meta"
[("I", "S"), ("M", "E"), ("T", "A")], "A"                       "T"
[("test", "cases"), ("are", "fun")], "test"                     "cases"
[("sad", "beep"), ("boop", "boop")], "boop"                     "boop"

Fewest bytes wins!

Japt, 6 bytes
Works with strings or integers.
æøV kV

Test it

Explanation
Implicit input of array U and string/integer V.
æ

Get the first element (subarray) in U that ...
øV

Contains V.
kV

Remove V and implicitly return the resulting single-element array.


Solve a Linear Equation This challenge but with a better spec.

Spec

Your program will take a linear equation containing a single variable x and output the value of x.

Input / Parsing

The input will only contain numbers, operators, parenthesis (()), x, and an = sign (this means no whitespace).
Parenthesis will always be balanced.
There will always be at least 1 x. An x may be preceded by a number.
All equations will exactly have one result.

A number can be defined by following these steps. A number can be defined by the regex: -?(\d+(\.\d+)?|\.\d+).

If you don't speak regex: A digit is defined as 0-9

It may have a - at the beginning of it signifying negative
Then there may be some digits. If they aren't any digits there will be a decimal point
If a decimal point exists, at least one digit will follow it

The biggest a number / value will be is defined by your language's capabilities.

An operator is any of: +-*/, they will always appear between numbers, and or parenthesis

this means (5)(5) is not a valid input for the sake of simplicity.

Parenthesis will always contain a valid expression (a valid combination of numbers and/or operators) inside them. "Balanced" parenthesis is defined as every ( will have an associated closing )

Evaluation

Order of operations should be followed and the precedences are (highest to lowest):

Parenthesis (most deeply nested first)
Multiplication & Division
Addition & Subtraction

If two operators with the same precedence are occurred you should prefer going left -> right

Output

You should output the result in some way. If you don't output just number result, clarify in your answer how the output is outputted. Your output format should be consistent. Output may be a decimal, but it will always be rational, the precision is limited to your language's precision. Only if your language does not support floating point arithmetic, you do not need to support it.

Rules

Built-ins trivializing this task are allowed but, you must clearly add [uses built-in] clearly to the header of the answer. This exempts your answer from winning
A "Built-ins trivializing this task" is any of:

Something which takes in an equation and outputs the value for a/the variable
Something which will completely simplify an equation
Using eval or a related function to do a significant amount of the parsing.  Use of eval and related functions are disallowed if they are used to (with minimal modification to the input) solve linear equations.
If you're in doubt, just ask in a comment.

Built-ins which parse the equation are allowed

Examples

3+4=x
7

4+x=5
1

3+3*3=x
12

3x-4=7+2x
11

3--1=x
4

3*(2+4x)=7x-4
-2

1.2+2.3x=5.8
2

10=4x
2.5

INVALID Inputs:

(5)(4)=x  no operator between (5) and (4)
5(x+3)=2  no operator 5 and (...)
x=y       the only variable is x
4=3       there is no x
x+3=x-7   no solution
x=x       infinite solutions
+5=x      + is not an unary operator. -5=x would be valid though
1/(x-3)=5 Nonlinear
3/x       Nonlinear

JavaScript ES6, 246 bytes

Still some golfing to be done, but at least it's a solution!

C=a=>new Function("x","return "+a.replace(/(\d)x/g,"$1*x"));n=>{n=n.split("=");t=Math.abs,r=C(n[0]),c=C(n[1]),a=0,i=r(a)-c(a);a++;v=r(a)-c(a);o=t(i)<t(v)?-1:1;for(u=1/0;r(a)!==c(a);)a+=o,e=t(r(a)-c(a)),e>u&&(u=1/0,o/=10),u=Math.min(e,u);return a}

Name the function n=>{n=n.split("=")... to use it.

Hyper-ungolfed:

function solveLinear(equation){
    equation = equation.split("=");
    var abs = Math.abs;
    var LHS = convertToFunction(equation[0]), RHS = convertToFunction(equation[1]);
    var pivot = 0;
    var dir;
    var dir1 = LHS(pivot) - RHS(pivot);
    pivot++;
    var dir2 = LHS(pivot) - RHS(pivot);
    if(abs(dir1)<abs(dir2)) dir = -1;
    else dir = 1;
    var dif, minDif = Infinity;
    while(LHS(pivot) !== RHS(pivot)){
        pivot += dir;
        dif = abs(LHS(pivot) - RHS(pivot));
        if(dif > minDif){
            minDif = Infinity;
            dir /= 10;
        }
        minDif = Math.min(dif, minDif);
        console.log(pivot,dir,dif,minDif);
    }
    return {
        x: pivot,
        LHS: LHS,
        RHS: RHS
    };
}

This uses a pivot approach. (I'm not sure if this is what the algorithm is called, just a name I invented.) It first gathers which direction to search for from zero (i.e., which way the slopes of the two sides of the equations will intersect) and looks for the value. Once it finds a point of minimal difference, it goes to that point and decreases the search increment. This eventually yields as precise of a solution we need.


Define map in the fewest tokens map is a very basic yet important function in functional programming.

All FP programming languages have it built-in but it is always fun to see how shortly you can define it yourself.

This will be scored in AST nodes, not bytes.

A token is the second-smallest building block of a program, over characters.

A token is:

  anything that would be a distinct node if you drew a tree representing the source code

This scoring gives no benefit to single letter AST nodes names, and values succinctness as Paul Graham likes (this definition of AST nodes is his).

Haskell has this super cool definition:

zipWith ($) . repeat

And my lisp-ish AST of it (not required in your answer, just to show it visually)

   Apply (Apply (Var ".") (Apply (Var "zipWith") (Var "$"))) (Var "repeat")

That is 7 tokens. (Var x counts as 1)

I did not write it, so I do not post it as an answer.

Example:

(zipWith ($) . repeat) (* 3) [1, 2, 3] -- [3, 6, 9]

map should be defined as a (named or unnamed) function taking two arguments, the function and the list.

May the most AST nodes-succint code win!

Mathematica, 36 11 nodes

Thread@#@#2&

The FullForm of this program is:

Function[Thread[Slot[1][Slot[2]]]]

which has 4 symbols, 2 numbers, and 5 function applications.


Build a Calculus Interpreter I A struggling manufacturer named Tennessee Instrumental is desperate to get into the calculator business.  Problem is, they don't have any software engineers on payroll, and the deadline is coming up fast.

It's your job to help TI configure a basic calculus-ready calculator that can simplify expressions input as strings, and as a bonus (since they're on such a tight schedule), they don't care what language you use to get there!  They do, however, care about how much space you take up.  Not very good with hardware, it seems.  Keep it brief, fewest bytes gets you hired.

Goal

Create a function which can simplify a basic calculus expression

Your calculator must be able to perform the following operations:

+ Addition
- Subtraction and Negation
* Multiplication
/ Division
^ Exponentiation
() Parenthetical Reduction
()' Derivation (first order)

Your calculator must also be able to use x as a placeholder variable.  Do not solve for x.  That will come in time.

Input

Input is a string containing the plaintext version of the expression you're looking to simplify.  The only valid input characters are 0-9, x, +, -, *, /, ^, (), ', and .  Some examples of valid inputs are listed below:

"1"
"5 + 8"
"(5x + 3)(4x + 2)"
"4x - 9x + 15"
"24x / 6"
"5x^2 + 14x - 3"  // Use ^ for exponentiation
"(20x^2)'"        // Use ()' for derivation

Output

Output is a string containing the plaintext version of the expression after simplification.

The only acceptable operators left over are +,  -, /, and ^.  Multiples of variables should be indicated as 2x, -5x, etc.  Fractions should be reduced as far as possible, and parentheses and derivations must be completely eliminated, with the exception of cases such as ln(x) which syntactically cannot be made to make sense without them.

The input examples from above should output as follows:

"1"                => "1"
"5 + 8"            => "13"
"(5x + 3)(4x + 2)" => "20x^2 + 22x + 6"
"4x - 9x + 15"     => "-5x + 15"
"24x / 6"          => "4x"
"5x^2 + 14x - 3"   => "5x^2 + 14x - 3"
"(20x^2)'"         => "40x"

Last but not least, if a derivation function exists in your language, you may not use it.  Derivations must be done as manually as possible.  Whitespace around the basic four operators and lack of whitespace around ^ and within () is preferred.

Mathematica, 159 Bytes
ToString@Expand@ToExpression[StringReplace[#,"("~~a__~~")'"->"d["~~ a ~~"]"]<>"//.{d[a_ x^n->a n x^(n-1),d[x]->1,d[a__]/;a~FreeQ~x->0,d[a__+b__]->d[a]+d[b]}"]&

NOTE: While this works on all the examples it won't currently work on all sensible differentiable input because it doesn't balance brackets when looking for derivatives. I'll change this once I've had the time to think of a sufficiently concise way of doing it. I'm sure there's some other stuff that goes wrong too, so please let me know if you spot something! There are a few bytes that are easily golfed off too, I'll get to those..


Random without Time-Basis Computers do not out-of-nowhere create random numbers without basis, as most likely, time is the universal basis of randomness.

I want you to create a code that creates random numbers with these rules:

Time is not allowed to be the basis, at any point of the program.
Predefined random/pseudo-random functions are not allowed.
Numbers generated can be within any range. Well at least two different integers :D
Numbers are echoed.

JavaScript

That was fun!

arr = []
index = 0

function init(seed) {
    index = 0
    arr[0] = seed
    for (var i = 1; i < 624; i ++) {
        arr[i] = (1812433253 * (arr[i-1] ^ (arr[i-1] >>> 30)) + i) | 0
    }
 }

function getNumber() {
    if (index == 0) generateNumbers()

    var y = arr[index]
    y ^= (y >>> 11)
    y ^= ((y << 7) & 2636928640)
    y ^= ((y << 15) & 4022730752)
    y ^= (y >>> 18)

    index = (index + 1) % 624
    return y
}

function generateNumbers() {
    for (var i = 0; i < 624; i ++) {
        var y = (arr[i] & 0x80000000) + (arr[(i+1) % 624] & 0x7fffffff)
        arr[i] = arr[(i + 397) % 624] ^ (y >>> 1)
        if (y % 2 != 0) arr[i] ^= 2567483615
    }
}

// let's get our seed now from the SE API
var x = new XMLHttpRequest()
x.open('GET', 'http://api.stackexchange.com/2.2/answers?pagesize=10&order=desc&sort=activity&site=stackoverflow&filter=!Sri2UzKb5mTfr.XgjE', false)
x.send(null)
// we've got the answer data, now just add up all the numbers.
// only 4 digits at a time to prevent too big of a number.
var seed = 0
var numbers = x.responseText.match(/\d{0,4}/g)
for (var i = 0; i < numbers.length; i++) seed += +numbers[i]

init(seed)
for (var i = 0; i < 10; i++) console.log(getNumber())

I wrote up the Mersenne Twister in JS. Then, I realized I had to get a seed from somewhere.

So, I decided I would get it from the Stack Exchange API! (I could use localStorage and increment a counter, but that's no fun.) So, I grabbed the 10 most recently active answers, and then I just took every 4 or less consecutive digits in the response and added them up.

These seeds are always different, since Stack Overflow is constantly updating (and my quota keeps going down!) The numbers include answer IDs, question IDs, scores, up/downvote counts, owner rep/IDs, and the wrapper data (quota and such). On one run I got 256845, then 270495, and then 256048, etc....

This logs 10 random 32-bit two's-complement numbers to the console. Sample output:

247701962
-601555287
1363363842
-1184801866
1761791937
-163544156
2021774189
2140443959
1764173996
-1176627822


Greet according to the time of day Challenge
Write a program that greets a user depending on what time of day (GMT) it is.

Output
A string (printed or returned) according to these rules:

If the time is 06:00 to 11:59 the greeting has to be "Good morning"
If the time is 12:00 to 17:59 the greeting has to be "Good afternoon"
If the time is 18:00 to 19:59 the greeting has to be "Good evening"
If the time is 20:00 to 05:59 the greeting has to be "Zzz"

Clarifications

There is no input
The times and greetings must be exactly as shown
The time zone is +0 GMT

Examples
Time: 14:45 -> Good afternoon

Time: 05:59 -> Zzz

Time: 9:23 -> Good morning

Time: 18:00 -> Good evening

JavaScript (ES6), 87 bytes

As noticed by TFeld, my original formula was overcomplicated. We can just do:

_=>['Zzz','Good morning','Good afternoon','Good evening'][new Date().getHours()%20/6|0]

Try it online!

Or test this version that takes the hour as parameter.

JavaScript (ES6), 90 bytes

_=>['Zzz','Good morning','Good afternoon','Good evening'][new Date().getHours()*7%20%7>>1]

Try it online!

Or test this version that takes the hour as parameter.

Formula

Given the current hour \$h\$, we find the appropriate greeting index \$i\$ with:

$$i=\left\lfloor\frac{((7\times h) \bmod 20) \bmod 7}{2}\right\rfloor$$

A good thing about this formula is that it does not require any parenthesis once converted to JS:

h * 7 % 20 % 7 >> 1

Table

 Hour |  *7 | mod 20 | mod 7 | >> 1
------+-----+--------+-------+------
   0  |   0 |    0   |   0   |   0
   1  |   7 |    7   |   0   |   0
   2  |  14 |   14   |   0   |   0
   3  |  21 |    1   |   1   |   0
   4  |  28 |    8   |   1   |   0
   5  |  35 |   15   |   1   |   0
   6  |  42 |    2   |   2   |   1
   7  |  49 |    9   |   2   |   1
   8  |  56 |   16   |   2   |   1
   9  |  63 |    3   |   3   |   1
  10  |  70 |   10   |   3   |   1
  11  |  77 |   17   |   3   |   1
  12  |  84 |    4   |   4   |   2
  13  |  91 |   11   |   4   |   2
  14  |  98 |   18   |   4   |   2
  15  | 105 |    5   |   5   |   2
  16  | 112 |   12   |   5   |   2
  17  | 119 |   19   |   5   |   2
  18  | 126 |    6   |   6   |   3
  19  | 133 |   13   |   6   |   3
  20  | 140 |    0   |   0   |   0
  21  | 147 |    7   |   0   |   0
  22  | 154 |   14   |   0   |   0
  23  | 161 |    1   |   1   |   0


Tell me how many math problems I have to do! My teacher always gives me the most complicated set of math problems for homework. Like: pg. 546: 17-19, 22, 26, pg. 548: 35-67 odd, 79, 80-86 even. And I want to know in advance how much time to set aside for my homework, but I don't want to have to figure all that out. That's why its your task to program it for me.
Specifications

You will get a string detailing the problems that I have to complete as args, stdio, etc.
They will be comma separated (possibly comma-space separated)
It will include single problems in the form of just a number (e.g. 79)
And ranges in the form 17-18 (again, you have to deal with optional spaces)
The ranges are inclusive of both ends
The ranges will optionally be suffixed by odd or even, which you have to take into account.
A set of ranges/pages will be prepended by a page number in the form pg. 545: , again having to deal with optional spaces. You can safely ignore these, as you need to get the problems over all the pages
The text may be in uppercase or lowercase, but will not be both.
Return, stdout, etc. the number of problems I have to do for homework.
Since this is code-golf, shortest code in bytes wins!

Test Cases
pg. 546: 17-19, 22, 26, pg. 548: 35-67 odd, 79, 80-86 even   ->    27
pg. 34: 1                                                    ->    1
PG. 565: 2-5,PG.345:7                                        ->    5
pg. 343: 5,8,13 - 56 even,pg. 345: 34 - 78,80                ->    70
pg.492: 2-4 odd,7-9 even                                     ->    2

CJam, 61 58 51 48 46 43 41 38 bytes

leuS-',/{':/W>:~_2*2<~z),>1f&\,5--~}%,

Verify the test cases in the CJam interpreter.

How it works

leuS-      e# Read a line from STDIN, convert to uppercase and remove spaces.
',/        e# Split at commas.
{          e# For each chunk:
  ':/W>    e#   Split at colons and only keep the last chunk.
  :~       e#   Evaluate the string inside the array.
  _2*      e#   Copy the array, repeated twice.
  2<       e#   Keep only the first two elements.

           e#   In all possible cases, the array now contains exactly two
           e#   integers, which are equal in case of a single problem.

  ~        e#   Dump the array on the stack.
  z),      e#   Push [0 ... -N], where N is the second integer.
  >        e#   Discard the first M elements, where M is the first integer.
  1f&      e#   Replace each element by its parity.
  \,       e#   Push L, the length of the original array.

           e#   EVEN and ODD all push elements, so L is 1 for single problems,
           e#   2 for simple ranges, 5 for odd ranges and 6 for even ranges.

  5--      e#   Discard all elements equal to L - 5 from the array of parities.

           e#   This removes 0's for odd ranges, 1's for even ranges, -3's for
           e#   other ranges and -4's for single problems, thus counting only
           e#   problems of the desired parities.

  ~        e#   Dump the resulting array on the stack.
}%         e# Collect the results in an array.
,          e# Compute its length.


Five Character ASCII Map Note: In this post, the terms 'character' and 'color' mean essentially the same thing

This image:

can be represented as

....'''333
.eeee'''3e
..dddd33ee
%%%dd####e

(mapping colors to ascii characters)

The four color theorem states that
"given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color. Two regions are called adjacent if they share a common boundary that is not a corner, where corners are the points shared by three or more regions." - Wikipedia (link)

This means that it should be possible to color a map using four colors so that no two parts which share an edge share a color.

The algorithm to color a map using only four colors is complicated so in this challenge your program only needs to color the map using five or less colors.

The previous map recolored could look like this:

which could be represented as

....'''333
.eeee'''3e
..dddd33ee
333dd....e

or equivalently

@@@@$$$!!!
@^^^^$$$!^
@@<<<<!!^^
!!!<<@@@@^

Challenge:

Given a "map" made of ascii characters (where each character represents a different color), "recolor" the map (represent the map using different ascii characters) so that it only uses five or less colors.

Example:

Input:

%%%%%%%%%%%%##########$$$$$$$$%%
*****%%%####!!!!!!!%%%%%%%%%#^^^
(((((((***>>>>??????????%%%%%%%%
&&&&&&&&$$$$$$$^^^^^^^))@@@%%%%%
^^^^^^%%%%%%%%%%%%##############

Possible output:

11111111111122222222223333333311
44444111222255555551111111112444
22222224441111444444444411111111
55555555222222255555553355511111
22222211111111111122222222222222

Clarifications:

The input map will always use six or more characters
You may use any five different characters in the output
You can use less than different five characters in the output
You may take the input in any reasonable format (including an array of arrays, or an array of strings)
This is code-golf so the shortest answer wins.

Sandbox link

Python 2, 375 361 359 357 355 353 350 347 bytes

e=enumerate
C=set('12345')
def f(s):
 s=[map(ord,l)for l in s]
 for i,v in e(s):
	for j,w in e(v):
	 if{w}-C:
		F,N=g([],s,i,j,w)
		for y,x in F:s[y][x]=min(C-N)
 return s
def g(m,s,i,j,c):
 n={s[i][j]}
 if(n^{c}or(i,j)in m)<1:
	m+=(i,j),
	for x,y in(0,1),(0,-1),(1,0),(-1,0):
	 if len(s)>i+x>-1<j+y<len(s[0]):m,N=g(m,s,i+x,j+y,c);n|=N
 return m,n

Try it online!

Takes input as a list of strings, and returns a list of lists

f takes the map input and colors it, g returns all connected characters and the set of their neighbors, to the area can be colored with a distinct color.


Check for occurences of string in other string Challenge

I'm sure you read the title, and came in to farm your rep, thinking its kids' stuff, but think again! You have to challenge each other in the shortest code to count the occurences of a string in another. For example, given the following input:

  aaaabbbbsssffhd

as a string, and the string

  s

should output

  3

Rules

Just before you smile and say, "Hey, I'll use ----," read this:

No use of external libraries, or your language's API. You have to implement it manually. Which means you can't use your language's built-in function or method for counting occurences
No file I/O
No connecting with a server, website, et cetera
In a case of `ababa`, where it starts with `aba` and if you read the last 3 letters it's also `aba`, you only count one*

Thank you @ProgramFOX for that (the last rule)!

*Hint: When you count occurences, you can remove the ones you counted to avoid disobeying this rule

I think the last 2 rules are just for rule benders!

Winning Criterion

As previously stated the winner is the code with the less bytes used. The winner will be announced five days later (15 June 2014)

My Small Answer

Here's my C++ answer, where it assumes that the li variable holds the string to check occurences in, and l is the string to look for in f:

Ungolfed

int c = 0;
while (li.find(lf) != string::npos)
{
    int p = li.find(lf);
    int l = p + lf.length() - 1;
    for (p = p; p <= l; p++)
    {
        li[p] = static_cast<char>(8);
    }
    ++c;
}

Of course, to use std::string, you have to include the string header file!

Golfed

int c=0;while(li.find(lf)!=string::npos){int p=li.find(lf);int l=p+lf.length()-1;for(p=p;p<=l;p++){li[p]=static_cast<char>(8);}++c;}

Result

The variable c is going to be the value of how many times the string was found

                                                                          Enjoy!

Winner

After a long wait @Dennis answer wins with only 3 bytes, written in GolfScript

JavaScript 32

Nothing really interesting here...

(p=prompt)().split(p()).length-1

split main purpose is to create an array from a string using the delimiter in argument.


Print the last answerer's first submission In this challenge, your past self comes back to help or hurt someone else!
The task is simple: write a full program, not a function, that prints the first code submission on this site submitted by the previous user, in the language of your first answer. (In the case that your first answer was purely prose, for example pxeger's first answer to a "Tips for Golfing" thread, use the first code-based answer.)
My first answer was

*/```

That's a newline followed by */```. Suppose that Doorknob was the first to answer this question. His first answer was in JavaScript, so he might respond to this challenge
alert("\n*/```")

And the next answerer here would have to print his first answer,
s='';c=5;r=Math.random;while(c--)s+='bcdfghjklmnpqrstvwxz'[r()*20|0]+'aeiouy'[r()*6|0]

Only accounts that submitted an answer before this question was posted are eligible to participate. Each user may submit only one answer.
This is code golf, so the shortest answer wins. The fun is that who can win depends on who answers!

user, Java (OpenJDK 8), 75 bytes

interface T{static void main(String[]a){System.out.print("print(\"N\")");}}

Try it online!
My first language was Java, lol. This is my first answer. It's 1055 bytes. Have fun.
interface T{static void main(String[]a){System.out.print("The basic idea of a [tag:kolmogorov-complexity] challenge is to print a set output in the shortest code (though that meaning has changed now). We have had many of them, from [Borromean Rings](_%s/53417/ascii-borromean-rings) to [The Gettysburg Address_%s/15395/how-random-is-the-gettysburg-address). \n##Your Task\nThis % is similar, except that it requires printing of a special text - the text of this %. Specifically, the very Markdown code that I am typing right now. \nTo prevent an infinite recursion in the %, the exact text you have to print can be found [here_revisions/1f731ea3-0950-4b03-ae95-24fa812a9a28/view-source). \n##Clarifications\n- You are not allowed to use any external sources like the internet. \n- This means that the purpose of this % is not to download this % text and parse it, but instead to store it in you program. \n- This is [tag:code-golf], so shortest code in **bytes** wins!".replaceAll("_","])http://codegolf.stackexchange.com/").replaceAll("%","question"));}}


Magic email transformation! Or: help the NSA extract your metadata from your email address Given an email address, the result of a transformation applied to that email address, and a second email address, return the output of the same transformation applied to the second email address.

The email addresses will all have the following structure:

A string of positive length containing alphanumeric characters and at most one . (the local part), followed by an @ symbol, followed by a string of positive length containing alphanumeric sumbols (the domain), followed by a . symbol, and a final string of positive length containing alphanumeric characters (the TLD).

There are four allowed transformations:

Identity (no change). (a.b@c.d -> a.b@c.d)
Returning just the local part (everything before the @) unmodified (a.b@c.d -> a.b).
Returning the local part split on the . if present, with the first symbol of each half capitalised. (a.b@c.d -> A B).
Returning just the domain (everything between the @ and the final .) unmodified. (a.b@c.d -> c).

When more than one transformation is possible, you can give the output of any of the possibilities. Whitespace at the start and end of output don't matter, but in the middle does (i.e. if you split a.b to A B there should be just one space in the middle [and any number at the start and end of output], but if you split a., then A with any number of spaces on either side are all acceptable).

Examples (input | output):

john.doe@gmail.com, John Doe, phillip.maini@gmail.com         | Phillip Maini
John.Doe@gmail.com, John Doe, Phillip.Maini@gmail.com         | Phillip Maini
foo.bar@hotmail.com, foo.bar, gee.whizz@outlook.com           | gee.whizz
foo.bar@hotmail.com, foo.bar, gEe.Whizz@outlook.com           | gEe.Whizz
rodney.dangerfield@comedy.net, comedy, michael.scott@office.0 | office
.jones@x.1, Jones, a.@3.z                                     | A
.jones@x.1, .jones@x.1, a.@3.z                                | a.@3.z
.jones@x.1, .jones, a.@3.z                                    | a.
.jones@x.1, x, a.@3.z                                         | 3
.@b.c, .@b.c, 1@2.3                                           | 1@2.3
john.jones@f.f, John Jones, 1in.thehand@2inthe.bush           | 1in Thehand
chicken.soup@q.z, Chicken Soup, fab@ulou.s                    | Fab
lange@haare.0, lange, fat.so@fat.net                          | fat.so
Lange@haare.0, Lange, fat.so@fat.net                          | {fat.so, Fat So} # either acceptable
chicken@chicken.chicken, chicken, horse@pig.farm              | {horse, pig} # either acceptable

Usual rules and loopholes apply.

Java 8, 254 240 236 bytes

(a,b,c)->{String A[]=a.split("@"),C[]=c.split("@"),x="";for(String p:C[0].split("\\."))x+=(p.charAt(0)+"").toUpperCase()+p.substring(1)+" ";return a.equals(b)?c:A[0].equals(b)?C[0]:A[1].split("\\.")[0].equals(b)?C[1].split("\\.")[0]:x;}

-4 bytes thanks to @LukeStevens.
Explanation:
Try it here.
(a,b,c)->{                  // Method with three String parameters and String return-type
  String A[]=a.split("@"),  //  Split `a` by "@" into two parts
         C[]=c.split("@"),  //  Split `c` by "@" into two parts
         x="";              //  Temp-String
  for(String p:C[0].split("\\."))
                            //  Loop over the first part of `c`, split by dots
    x+=                     //   Append String `x` with:
       (p.charAt(0)+"").toUpperCase()
                            //    The first character as uppercase
       +p.substring(1)      //    + the rest of the String
       +" ";                //    + a space
                            //  End of loop (implicit / single-line body)
  return a.equals(b)?       //  If input `a` and `b` are exactly the same:
    c                       //   Return `c`
   :A[0].equals(b)?         //  Else-if the first part of `a` equals `b`:
    C[0]                    //   Return the first part of `c`
   :A[1].split("\\.)[0].equals(b)?
                            //  Else-if the domain of `a` equals `b`
    C[1].split("\\.)[0]     //   Return the domain of `c`
   :                        //  Else:
    x;                      //   Return String `x`
}                           // End of method


Anti-golfscript anti-golf: create a task where GolfScript or J is outgolfed by your (conventional) lang You need to make three things:

Statement of a task, T.
Solution of the task in language not typically used for golfing, A.
Solution of the task in language typically used for golfing, B. Don't try to just bloat up B to pump up the score, instead think as if B was written by your competitor.

Use common sense in defining typically used for golfing, try to maximize fun for other users.

Other users may propose better Bs (maybe including in other "golfy" languages).

Scoring is (length_in_bytes(B)+5)/(length_in_bytes(A)+5), more is better. (Maybe the scoring formula should be changed?..)

The main idea is to invent a task where languages that typically perform well in codegolf meet a problem. It can be sudden strength of a usual language in the given task or sudden weakness of some golflang.

Avoid tasks that mention specific programming languages, like Input a string and execute it as a Scheme code.

My previous question, Print a sinusoidal wave (vertically), qualifies at this moment. I'm posting it here as a solution, also hoping that you guys can come up with some shorter solutions to my original question.

As required by Vi., I will post a summary of the question.

Print a continuous sinusoidal wave scrolling vertically on a terminal. The program should not terminate and should continuously scroll down the wave (except until SIGINT). You may assume overflow is not a problem (i.e. you may use infinite loops with incrementing counters, or infinite recursion).

The wave should satisfy the following properties:

Amplitude = 20 chars (peak amplitude)
Period = 60 to 65 lines (inclusive)
The output should only consist of spaces, newline and |
After each line of output, pause for 50ms

There is a sample output on my original question, but I'm not posting it here, because this will make my answer ridiculously long. My original question can be seen here: Print a sinusoidal wave (vertically)

Shortest A currently: a Perl solution with 48 chars:
https://codegolf.stackexchange.com/a/18655/12205

print$"x(25+20*sin).'|
';$_+=.1;`sleep .05`;do$0

Shortest B currently: a J solution with 54 chars: https://codegolf.stackexchange.com/a/18649/12205

($:+&0.1[6!:3@]&0.05[2:1!:2~' |'#~1,~[:<.20*1+1&o.)0

Currently, the score of this answer is 1.113 (an awfully low score)


Change the innermost element type of a jagged array — any .NET language: C#, F#, VB.NET, MSIL, C++/CLI, etc Write a class containing a method with the signature

System.Array ChangeElementType(System.Array jaggedArray)

(you may rename identifiers ChangeElementType, jaggedArray and shorten the type System.Array with using directives). The class may contain any additional members if needed.

You may assume the following preconditions (and do not need to validate them):

The argument jaggedArray is not null.
The argument jaggedArray is an array instance whose type can be represented in C# notation as int[...]..., i.e. the type int followed by 1 or more rank specifiers [...] where each rank specifier is a pair or square brackets with 0 or more commas between them. For example, it could be an array of type int[], int[,][][,,,], etc.
No element at any level of the jaggedArray is null.
All elements at any level of the jaggedArray are distinct w.r.t. reference equality (i.e. the same array instance does not appear at several different positions).
The lower bound of any array dimension is 0.
The length of any dimension and the total number of elements of any array fits into the type int.

The method must create and return an array of type long[...]... which is obtained from the type of jaggedArray by replacing int with long and keeping all rank specifiers the same. The result must have the same shape as jaggedArray, i.e. all array dimensions at any level must be the same. All elements at the innermost level must have the same numeric values (cast from int to long). The method must not mutate the argument jaggedArray or any its elements at any level.

The solution may be implemented in any language for the .NET platform: C#, F#, VB.NET, MSIL, C++/CLI, etc. All necessary using, open or imports directives or fully qualified names must be explicitly specified (do not rely on IDE defaults). The only referenced assembly must be mscorlib, no P/Invoke or COM Interop allowed. The solution cannot access any Internet services to get the result, intermediate data or to download parts of an algorithm.

It is a golf — try to minimize the number of bytes in the source.

C# - 396 440 595

I'm not entirely sure why I did this, and I can't help but feel I'm missing something. Rewrote the old c (for copy) method as a for-loop in the ChangeElementType method (f). Unless I find something substantial, I think I'll not be making this any shorter.

Golfed code:

using A=System.Array;using T=System.Type;class P{T g(T o){return o.IsArray?g(o.GetElementType()).MakeArrayType(o.GetArrayRank()):typeof(long);}A f(A a){var R=a;int i,r;for(var x=new int[i=r=a.Rank];;){if(i<1){if(a!=R)return R;R=A.CreateInstance(g(a.GetType().GetElementType()),x);i=1;}if(--i<r)if(x[i]-->0)i+=2;else x[i]=a.GetLength(i);else{var o=a.GetValue(x);R.SetValue(o is A?f((A)o):o,x);}}}}

Readable code with an excuse for a test:

using A=System.Array;
using T=System.Type;

class P
{
    // turns a type like "int[,][]" into "long[,][]"
    T g(T o)
    {
        return o.IsArray?g(o.GetElementType()).MakeArrayType(o.GetArrayRank()):typeof(long);
    }

    // ChangeElementType
    A f(A a)
    {
        var R=a; // R is the result, a gives us the type and a nice default value
        int i,r; // i is a counter, r is the rank

        // this loop first counts backwards filling the x array with the dimension lengths
        // then it does a tree traversal and copies things about
        for(var x=new int[i=r=a.Rank];;) // create the x array, and sets i and r
        {
            if(i<1)
            { // gone off start
                if(a!=R) // been here before
                    return R; // return the result
                R=A.CreateInstance(g(a.GetType().GetElementType()),x); // create the array to fill
                i=1; // move to start of x
            }

            if(--i<r) // move back
                if(x[i]-->0) // decrement index
                    i+=2; // move forward instead
                else
                    x[i]=a.GetLength(i); // reset index
            else
            {
                var o=a.GetValue(x); // get the int/array
                R.SetValue(o is A?f((A)o):o,x); // if it's an array, Change it, if not, pass it directly (the int)
            }
        }
    }

    // test method (prints True if the code works, might print False if it doesn't)
    static void Main()
    {
        string old = "";

        var a = new int[10][,];

        for (int i = 0; i < 10; i++)
        {
            a[i] = new int[3,5];

            for (int j = 0; j < 3; j++)
            {
                for (int k = 0; k < 5; k++)
                {
                    int v = i * j * k;
                    a[i][j,k] = v;
                    old += v.ToString();
                }
            }
        }

        long[][,] l = (long[][,])(new P().f(a));

        string nwe = "";

        for (int i = 0; i < 10; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                for (int k = 0; k < 5; k++)
                {
                    nwe += l[i][j,k].ToString();
                }
            }
        }

        System.Console.WriteLine(old == nwe);

        System.Console.ReadKey(true);
    }
}


Know a sequence by its subsequences Introduction

Suppose you and your friend are playing a game.
Your friend thinks of some particular sequence of n bits, and your task is to deduce the sequence by asking them questions.
However, the only type of question you're allowed to ask is "How long is the longest common subsequence of your sequence and S", where S is any sequence of bits.
The fewer questions you need, the better.

The task

Your task is to write a program or function that takes as input a positive integer n, and a binary sequence R of length n.
The sequence may be an array of integers, a string, or some other reasonable type of your choice.
Your program shall output the sequence R.

Your program is not allowed to access the sequence R directly.
The only thing it's allowed to do to R is to give it as input to the function len_lcs along with another binary sequence S.
The function len_lcs(R, S) returns the length of the longest common subsequence of R and S.
This means the longest sequence of bits which occurs as a (not necessarily contiguous) subsequence in both R and S.
The inputs of len_lcs which may be of different lengths.
The program should call this function on R and other sequences some number of times, and then reconstruct the sequence R based on that information.

Example

Consider the inputs n = 4 and R = "1010".
First, we might evaluate len_lcs(R, "110"), which gives 3, since "110" is the longest common subsequence of "1010" and "110".
Then we know that R is obtained from "110" by inserting one bit at some position.
Next, we might try len_lcs(R, "0110"), which returns 3 since the longest common subsequences are "110" and "010", so "0110" is not correct.
Then we try len_lcs(R, "1010"), which returns 4.
Now we know that R == "1010", so we can return that sequence as the correct output.
This required 3 calls to len_lcs.

Rules and scoring

In this repository, you'll find a file called subsequence_data.txt containing 100 random binary sequences of lengths between 75 and 124.
They were generated by taking three random floats between 0 and 1, taking their average as a, and then flipping an a-biased coin n times.
You score is the average number of calls to len_lcs on these sequences, lower score being better.
Your submission should record the number of calls.
There are no time limits, except that you should run your program on the file before submitting it.

Your submission shall be deterministic.
PRNGs are permitted, but they must use today's date, 200116 (or closest equivalent), as the random seed.
You are not allowed to optimize your submission against these particular test cases.
If I suspect this is happening, I will generate a new batch.

This is not code golf, so you're encouraged to write readable code.
Rosetta Code has a page on the longest common subsequence; you may use that to implement len_lcs in your language of choice.

Java, 99.04 98.46 97.66 lcs() calls

How it works

Exaple: Our line that is to be reconstructed is 00101.
First we find out how many zeros there are, by comparing (here comparing = computing lcs with the original string) by a zeros only string 00000. Then we go through each position, flip the 0 to a 1 and check if we now have a longer common substring. If yes, accept and go to next position, if no, flip the current 1 back to a 0 and go to next position:

For our example of "00101" we get following steps:
input  lcs  prev.'best'
00000  3    0           //number of zeros
̲10000  3    3           //reject
0̲1000  3    3           //reject
00̲100  4    3           //accept
001̲10  4    4           //reject
0010̲1  5    4           //accept

Optimizations

This is just a "naive" implementation, perhaps it would be possible to find a more sophisticated alogrithm checking multiple positions at once. But I am not sure if there really is a better one (e.g. based on the calculation of parity bits similar to the Hamming code), as you can always just evaluate the length of the common substring.

For one given line of digits, this algorithm needs exactly #ofDigitsUntilTheLastOccurenceOf1 + 1 checks. (Substract one if the last digits is an 1.)

EDIT: One small optimization: If we just checked the 2nd last digit and we still need to insert a 1, we know for sure that it must be in the very last position, and can omit the corresponding check.

EDIT2: I just noticed you can apply above idea to the last k ones.

It might of course be possible to achieve a slightly lower score with the this optimization, by reordering the all lines first, because it could be, that you get more lines with ones at the very end but that would obviously be and optimization for the current test cases which is no longer funny.

Runtime

The upper limit is O(#NumberOfBits).

Full code

Here the full code:

package jcodegolf;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

// http://codegolf.stackexchange.com/questions/69799/know-a-sequence-by-its-subsequences

public class SequenceReconstructor {
    public static int counter = 0;
    public static int lcs(String a, String b) { //stolen from http://rosettacode.org/wiki/Longest_common_subsequence#Java
        int[][] lengths = new int[a.length()+1][b.length()+1];

        // row 0 and column 0 are initialized to 0 already

        for (int i = 0; i < a.length(); i++)
            for (int j = 0; j < b.length(); j++)
                if (a.charAt(i) == b.charAt(j))
                    lengths[i+1][j+1] = lengths[i][j] + 1;
                else
                    lengths[i+1][j+1] =
                        Math.max(lengths[i+1][j], lengths[i][j+1]);

        // read the substring out from the matrix
        StringBuffer sb = new StringBuffer();
        for (int x = a.length(), y = b.length();
             x != 0 && y != 0; ) {
            if (lengths[x][y] == lengths[x-1][y])
                x--;
            else if (lengths[x][y] == lengths[x][y-1])
                y--;
            else {
                assert a.charAt(x-1) == b.charAt(y-1);
                sb.append(a.charAt(x-1));
                x--;
                y--;
            }
        }

        counter ++;
        return sb.reverse().toString().length();
    }

    public static String reconstruct(String secretLine, int lineLength){
        int current_lcs = 0;
        int previous_lcs = 0;
        char [] myGuess = new char[lineLength];
        for (int k=0; k<lineLength; k++){
            myGuess[k] = '0';
        }

        //find the number of zeros:
        int numberOfZeros = lcs(secretLine, String.valueOf(myGuess));
        current_lcs = numberOfZeros;
        previous_lcs = numberOfZeros;

        if(current_lcs == lineLength){ //were done
            return String.valueOf(myGuess);
        }

        int numberOfOnes = lineLength - numberOfZeros;
        //try to greedily insert ones at the positions where they maximize the common substring length
        int onesCounter = 0;
        for(int n=0; n < lineLength && onesCounter < numberOfOnes; n++){

            myGuess[n] = '1';
            current_lcs = lcs(secretLine, String.valueOf(myGuess));

            if(current_lcs > previous_lcs){ //accept

                previous_lcs = current_lcs;
                onesCounter ++;

            } else { // do not accept
                myGuess[n]='0';
            }

            if(n == lineLength-(numberOfOnes-onesCounter)-1 && onesCounter < numberOfOnes){ //lets test if we have as many locations left as we have ones to insert
                                                                // then we know that the rest are ones
                for(int k=n+1;k<lineLength;k++){
                    myGuess[k] = '1';
                }
                break;
            }

        }

        return String.valueOf(myGuess);
    }

    public static void main(String[] args) {
        try {

            //read the file
            BufferedReader br;

            br = new BufferedReader(new FileReader("PATH/TO/YOUR/FILE/LOCATION/subsequence_data.txt"));

            String line;

            //iterate over each line
            while ( (line = br.readLine()) != null){

                String r = reconstruct(line, line.length());
                System.out.println(line);     //print original line
                System.out.println(r);        //print current line
                System.out.println(counter/100.0);  //print current number of calls
                if (! line.equals(r)){
                    System.out.println("SOMETHING WENT HORRIBLY WRONG!!!");
                    System.exit(1);
                }

            }

        } catch(Exception e){
            e.printStackTrace();;
        }

    }

}


Reverse-Engineer the N-Bonacci sequence[s] EDIT: I will be accepting an answer Monday, 2/15/2016. May the bytes be ever in your favor!

In his "Print the N-Bonacci Sequence" challenge, @DJMcGoathem describes the N-bonacci sequences, wherein the previous N numbers are summed, instead of the traditional 2 of the Fibonacci sequence (said to be the "duonacci sequence"). He then asked to take two inputs, X and N, then output the Xth N-nacci number.

I propose the opposite.
Given a sequence, output which N-nacci sequence it is a subset of. I say "subset of" because:

A) these sequences are infinite
B) if given the start of the sequence, you could just count the number of leading 1s

In the case that it could belong to multiple N-nacci sequences, chose the lowest one.
In the case that it does not belong to any N-nacci sequence, then your program may do anything other than print something that could be mistaken for output. These behaviors include (but are not limited to): infinite loop, error, crash, delete itself (*cough cough* vigil *cough cough*), or create a black hole (as long as this black hole does not produce anything that could be mistaken for valid output).
For the sake of this challenge, these sequences start with 1. This means any N-nacci sequence starts with N ones. Furthermore, N must be a positive integer. So no -1-nacci, etc.

Test cases:

1,1,1 -> 1
49, 97 -> 7
55, 89, 144 -> 2
1 -> 1
6765 -> 2
12, 23, 45, 89 -> 12
100, 199 -> 100

Ruby, 94
I'm quite surprised how far I've been able to golf this within the same algorithm!  I started with over 200!
->a{1.step.find{|s|x=[1]*(s+z=a.size)
x<<x[-s,s].inject(:+)while x.max<a.max&&s>1
x[-z,z]==a}}

Ungolfed:
l=->a{
    # ooh! a built-in infinite incrementer!
    1.step.find{|s|
        # if n == 1, z is important, otherwise s.
        x=[1]*(s+z=a.size)
        ## add the next nacci number until we hit or overshot max.
        ## if s == 1, we don't increment, so don't bother
        x<<x[-s,s].inject(:+)while x.max<g&&s>1
        # eval to true if there's a match, false if not
        x[-z,z]==a
    }
}


Determine stability of a system using the Routh-Hurwitz stability criterion The Routh-Hurwitz is a criteria which serves to prove or disprove the stability of an electric control system.

Idea

Given a system which has an equation of the form P(s)/Q(s) where P(s) and Q(s) are polynomials of any degree, it is said to be stable if all the roots of the polynomial Q(s) are in the left half of the complex plane, which means the real part of the root is negative.

For polynomials of degree less than or equal to 2, it is trivial to determine the roots and notice whether or not the system is stable. For polynomials Q(s) of higher degrees, the Routh–Hurwitz theorem can be useful to determine whether the system is Hurwitz-stable or not.

Process

One of the methods to apply this theorem for any degree is described on Wikipedia that consists of performing operations on rows of a table, then counting the number of sign changes in the first column of the table. It goes as follows:

Fill the first two rows with the coefficients of the polynomial, in the following pattern: 1st row consists of the even coefficients s^n, s^n-2, ..., s^2, s^0; 2nd row consists of the odd coefficients s^n-1, s^n-3, ..., s^3, s^1;
Keep calculating the following rows by calculating the determinant of the matrix (last 2 rows of the first column, last 2 rows of the next column) divided by (the value of the first column on the row above); it is detailed in this part of the Wikipedia article.
If you encounter a row full of zeros, set it to the derivative of the polynomial that the row above it represents. Depending on the row it is on, the number on each cell represents a coefficient. It is illustrated in the example later.
If you encounter a zero with other non-zero values, the system is not stable: you can stop there. (You could continue but you'll get the same result). A zero on the first column would mean a root of real value 0, which renders the system unstable.
Otherwise, continue until the end. Then, if not all the values in the first column are of the same sign, the system is not stable.

Examples

Here are some examples of that process:

# Polynomial: 1 3 6 12 8.00

s^4  1 6  8
s^3  3 12 0
s^2  2 8  0
s^1--0-0--0-- < Row of zero - replace it by:
s^1  4 0  0   < Derivative 2*s^2 + 8*s^0 = 4*s^1
                 (between each 2 columns the power of s is lowered by 2)
s^0  8 0  0   < Continue normally

# Sign Changes: 0 (equivalent to no root in the right half plane)
# Stable: Yes

Another one:

s^2   1  -2
s^1   1   0
s^0  -2   0

# Sign Changes: 1 (equivalent to 1 root in the right half plane)
# Stable: No

Rules

The program will keep reading polynomials from standard input until a blank line, and output 0/1 for stable/non-stable respectively for each polynomial on a new line.
The program can read the polynomial coefficients in any form. It could be 1 3 6 12 8 for the first example (it suits this problem better, but it doesn't really matter in the end).
It has to handle cases where 0 in the first column, or 0 in the following columns, or a row full of 0 is encountered properly. (Note: just in case, no need to see how many roots are in rhp/lhp/jw axis).
It can short-circuit the process at any time if a condition is met, there is no need to show the RH table in the end.
You do not have to use this method. Any method which will determine whether or not a system is Hurwitz-stable can do the job.
It doesn't matter which language you chose to do it with, as long as it's not done in one single built-in function call. I did mine in Python, I'll post it soon.
This is a code golf. The shortest code wins.

Here's a sample input/output (given in the above mentioned way) to test your program with:

#input:
1 12 6 10 10 6 14
1 1 -2
1 2 1 2
1 3 1 3 16
1 2 3 6 2 1
1 2 14 88 200 800
1 2 3 6 2 1
1 3 6 12 8
1 4 5 2 4 16 20 8

#output:
0
0
1
0
0
0
0
1
0

If you need more clarifications, let me know, I'll do my best to clarify.

Haskell - 264 bytes

p(a:b:s)=(a,b):p s
p[a]=[(a,0)]
p[]=[]
s((a:w),m@(b:v))=a:s(m,m%zipWith(\c d->(b*c-a*d)/b)w v)
s((a:_),_)=[a]
m%(0:v)|all(==0)v=fst$foldr(\b(d,p)->(b*p:d,2+p))([],0)m
m%v=v
q(a:s)|all((>0).(a*))s="1\n"
q _="0\n"
main=interact$(>>=q.s.unzip.p.map read.words).lines

Running the sample inputs:

& runhaskell 11847-Stability.hs
1 12 6 10 10 6 14
1 1 -2
1 2 1 2
1 3 1 3 16
1 2 3 6 2 1
1 2 14 88 200 800
1 2 3 6 2 1
1 3 6 12 8
1 4 5 2 4 16 20 8
0
0
1
0
0
0
0
1
0

(The output is interleaved with the input if you type it one line at a time, as per spec. If you bulk paste, you see all the output after the input.)


Tips for King of the Hill bots What general tips do you have for creating a bot to participate in a King of the Hill challenge? What strategies do you use to go from considering the challenge to creating your bot? What data structures do you find most useful?

Please post one tip per answer.

Finding Nash Equilibria

This is a very important concept when the KOTH involves a relatively simple set of decisions, involves only a few players (typically 2), and is deterministic.  A Nash equilibrium describes a "gridlock" position: if the two players have decided upon their two strategies, then the two players are effectively locked in those positions: either player changing their strategy simply creates additional vulnerabilities.

Examples of games where Nash equilibria are important are:

Rock-Paper-Scissors(-Lizard-Spock), in which an "unbeatable" strategy is random play
Morra, which has a "spectrum" of equilibria. Peter Taylor wrote a good example in his answer here.
Prisoner's Dilemma, a cooperative game notable for having an "everybody loses" gridlock

How to find an equilibrium

Finding an equilibrium actually is actually pretty simple for most simple games, and is often pretty intuitive.  A ton of detail about the various methods can be found on the internet.  The basic concept, which is normally applicable, is to create a list of possible strategies that the two players can use (the options provided by the game).  If one strategy is "dominated" by another, then that strategy can be removed from the list, and the process is repeated. By "domination," I mean that if strategy A always gives an equal-or-better result than strategy B, against all of the remaining opponent strategies, then strategy B can be removed from the list.

Example: Rock-Paper-Scissors

RPS has something called a "mixed" equilibrium, meaning that a distribution is involved.  Rather than playing the same move repeatedly (which will lead to quick defeat), the equilibrium is to play 1/3 rock, 1/3 paper, and 1/3 scissors in a random distribution.  If I play randomly, there is nothing my opponent can do to get an edge on me, period.  If my opponent chooses not to play randomly, then that only creates a vulnerability on his part.

Games with mixed equilibrium are probably the most common on PPCG, since they can take many forms (the only interesting game I can think of with a pure equilibrium is prisoner's dilemma).  I should note that the mixed equilibrium doesn't have to be uniformly random, simply something other than playing the same move every time.

Using this information

The Nash equilibrium of a game often represents the "baseline" from which you should try to operate.  In RPS, playing randomly guarantees a finishing spot around the middle of the pack.  In order to move to the top, you have to start identifying other player's weaknesses.

To do this, you should stick to the equilibrium when unsure of the opponent's weaknesses.  Once those weaknesses have been identified (you have detected that your opponent is not in equilibrium), then you need to gently shift out of equilibrium to take advantage of your opponent.  This action, in turn, creates weaknesses on your own part.  You must then detect when your opponent is changing his strategy, so that you can then stop the attack and resume random play.

Detecting variation from equilibrium

This is pretty difficult, and I am not an expert.  Variations can come in many forms:

Favoring some options above/below others for no reason, like an RPS player that plays rock twice as often as scissors, or one that avoids playing paper.  Some relatively simple statistics can detect this.
Basing a current move off past moves, in some predictable pattern.  This includes copy-cats, "beats what beats your last move" bots, or "cycling" bots.  This takes additional logic to detect, since the overall move distribution can be evenly-distributed, even though the moves aren't random.  You should attempt to take the record of moves and find correlations like "the move I made 2 turns ago and the move my opponent made now" and "the move he made 1 turn ago, and the move he made now", etc.
Bots whose move distribution is based off of yours.  The vulnerability in these bots is often not created (in a measurable quantity) until after you have yourself varied from a random distribution.  Generally, your own bot falls into this category.


Write self-validating code Write code that takes a string as input, and outputs a truthy or falsey value depending on whether or not the string follows these rules:

If you stack each character on top of each other, convert to binary and sums each column, then all the sums should be identical. You may assume the input string contains only printable ASCII-characters (code points 32 - 126).

As an example:

The input O5vy_+~ should return a truthy value, since its binary representation is:

1001111  | O
0110101  | 5
1110110  | v
1111001  | y
1011111  | _
0101011  | +
1111110  | ~
-------
5555555  <- Sum of bits in each column. Should give a truthy value.

The input PPCG should return a falsey value, since its binary representation is:

1010000  | P
1010000  | P
1000011  | C
1000111  | G
-------
4020122  <- Should give a falsey value

The twist is: Your code should return a truthy value if it's used as input to your function / program. I.e. the code must adhere to the same rules as above (your code can contain characters that are not ASCII 32-126).

Your program/function only needs to handle printable ASCII as input. If your code contains something else, 8 bit, 16 bit encoding, Unicode, a custom made character set (or something else), then the binary representation of it should adhere to the same rules, but your code doesn't need to handle it as input.

This is code-golf, so standard rules apply.


Is it an integer, a string, or a decimal? Your challenge is to determine whether the given input is an integer, a string, or a decimal.

Rules

A string is any input that is not an integer or a float
An integer must contain only numeric characters and must not start with a zero
A decimal is any input that contains the period (.) and the period is surrounded by numeric characters.

Note: .01 is not considered a valid decimal.

The program should output a raw string either "string", "integer", or "decimal".
You may assume only printable ASCII characters are used

Cases:

asdf -> string
asdf3.4 -> string
2 -> integer
2.0 -> decimal
02 -> string
40. -> string
. -> string
.01 -> string
0.0 -> decimal
.9.9.9 -> string
[empty space] -> string

EDIT: Fixed the typo. I meant .01 without the leading zero, not with. If that made it unclear, its fixed now!

This is code-golf, so shortest answer wins.

Pyth, 33 bytes (39 without packed string)

@_c."at%¸Ã`9hàãáÊ"7.x/`MsB+vz0z0

Some bytes are stripped due to Markdown. Official code and test suite.

Without packed string:

@_c"integerdecimalstring"7.x/`MsB+vz0z0

It passes all of above test cases. Basically, to check if a string is a integer or decimal, it checks whether the string can be evaluated as a python literal (v), and if so, if you can add 0 to it and covert it back to its string representation, and get the input string. If so, it's an integer or a decimal. If you can also cast it to an int and still get the original string back, it's an integer.