Print a Pentomino Rectangle Write a program or function that takes no input but prints or returns a constant textual depiction of a rectangle made of the 12 distinct pentominoes:

The rectangle may have any dimensions and be in any orientation, but all 12 pentominoes must be used exactly once, so it will have area 60. Each different pentomino must be composed of a different printable ASCII character (you don't need to use the letters from above).

For example, if you chose to output this 20×3 pentomino rectangle solution:

Your program's output might look something like this:

00.@@@ccccF111//=---
0...@@c))FFF1//8===-
00.ttttt)))F1/8888=-

Alternatively, you might find it easier to golf this 6×10 solution:

000111
203331
203431
22 444
2   46
57 666
57769!
58779!
58899!
5889!!

Any rectangle solution will do, your program only needs to print one. (A trailing newline in the output is fine.)

This great website has loads of solutions for various rectangle dimensions and it's probably worth browsing them to make sure your solution is as short as possible. This is code-golf, the shortest answer in bytes wins.

Bash + common Linux utils, 50

xxd -s20 -p -c2 $0
#<30 bytes of binary data>

To recreate this from encoded base64:
base64 -d <<< eHhkIC1zMjAgLXAgLWMyICQwCiMiImaSaZlmkDAAMwSjRKNEqoGogYhRVVF7UXu7d3s= > pent.sh

Since there are 12 pentominoes, their colours are easily encoded in hex nybbles.
Output:
$ ./pent.sh
2222
6692
6999
6690
3000
3304
a344
a344
aa81
a881
8851
5551
7b51
7bbb
777b
$


Olympic game scoring The challenge is to write a golf-code program that, given n positive real numbers from 0 to 10 (format x.y, y only can be 0 or 5: 0, 0.5, 1, 1.5, 2, 2.5 … 9.5 and 10), discard the lowest and highest values (only one, even though they are repeated) and shows the average of the remaining, in x.y format (y can be 0 or 5, rounded to closest), similar to some Olympic Games scoring.

Examples:
Input -> Output

6 -> 6

6.5, 9 -> 8

9, 7, 8 -> 8

6, 5, 7, 8, 9 -> 7

5, 6.5, 9, 8, 7 -> 7

6.5, 6.5, 9.5, 8, 7 -> 7

5, 6.5, 7.5, 8.5, 9.5 -> 7.5

Notes: If the input is only two numbers, do not discard any, just average them. If the input is one number, the output is the same.

Clarifying the rounding rule (sorry, little confuse):

x.01 to x.25 round to x.0

x.26 to x.75 round to x.5

x.76 to x.99 round to x+1.0

Jelly, 12 bytes

ṢṖḊȯµÆmḤær0H

Try it online!

    µ           Take
Ṣ               the input sorted,
 Ṗ              without its last
  Ḋ             or first element,
   ȯ            or the unchanged input if that's empty,
     Æm         then calculate the mean,
       Ḥ        double it,
        ær      round it to the nearest multiple of
          0     10^-0 (= 1),
           H    and halve it.

A version which rounds halves down, in accordance with the spec at the expense of the second test case:

Jelly, 12 bytes

ṢṖḊȯµÆmḤ_.ĊH

Try it online!

The rounding method here is closer to Jonathan Allan's:

Ḥ        Double,
 _       subtract
  .      one half,
   Ċ     round up,
    H    and halve.


Number of transformations until repeat Given a sequence of integers or to be more specific a permutation of 0..N
transform this sequence as following:

output[x] = reverse(input[input[x]])
repeat

For example: [2,1,0] becomes [0,1,2] and reversed is [2,1,0]. [0,2,1] becomes [0,1,2] and reversed [2,1,0].

Example 1

In:   0 1 2
S#1:  2 1 0
S#2:  2 1 0
Output: 1

Example 2

In:   2 1 0
S#1:  2 1 0
Output: 0

Example 3

In:   3 0 1 2
S#1:  1 0 3 2
S#2:  3 2 1 0
S#3:  3 2 1 0
Output: 2

Example 4

In:   3 0 2 1
S#1:  0 2 3 1
S#2:  2 1 3 0
S#3:  2 0 1 3
S#4:  3 0 2 1
Output: 3

Your task is to define a function (or program) that takes a permutation of
integers 0..N and returns (or outputs) the number of steps until a permutation occurs that has already occured. If X transforms to X then the output should be zero, If X transforms to Y and Y to X (or Y) then the output should be 1.

Y -> Y: 0 steps
Y -> X -> X: 1 step
Y -> X -> Y: 1 step
A -> B -> C -> D -> C: 3 steps
A -> B -> C -> D -> A: 3 steps
A -> B -> C -> A: 2 steps
A -> B -> C -> C: 2 steps
A -> B -> C -> B: also 2 steps

Testcases:

4 3 0 1 2 -> 0 3 4 1 2 -> 4 3 2 1 0 -> 4 3 2 1 0: 2 steps
4 3 2 1 0 -> 4 3 2 1 0: 0 steps
4 3 1 2 0 -> 4 1 3 2 0 -> 4 3 2 1 0 -> 4 3 2 1 0: 2 steps
1 2 3 0 4 -> 4 1 0 3 2 -> 0 3 4 1 2 -> 4 3 2 1 0 -> 4 3 2 1 0: 3 steps
5 1 2 3 0 4 -> 0 5 3 2 1 4 -> 1 5 3 2 4 0 -> 1 4 3 2 0 5 ->
  5 1 3 2 0 4 -> 0 5 3 2 1 4: 4 steps

If your language doesn't support "functions" you may assume that the sequence is given as whitespace seperated list of integers such as 0 1 2 or 3 1 0 2 on a single line.

Fun facts:

the sequence 0,1,2,3,..,N will always transform to N,...,3,2,1,0
the sequence N,..,3,2,1,0 will always transform to N,..,3,2,1,0
the sequence 0,1,3,2,...,N+1,N will always transform to N,...,3,2,1,0

Bonus task:
Figure out a mathematical formula.

Optional rules:

If your language's first index is 1 instead of 0 you can use permutations 1..N (you can just add one to every integer in the example and testcases).

JavaScript (ES6), 54 bytes

a=>~(g=a=>g[a]||~-g(g[a]=a.map(i=>a[i]).reverse()))(a)

Try it online!


Can I Slide Apart The Puzzle? Write a program or function that takes in a rectangular grid of text where every cell is either an A or a B. All the A cells will form a simply-connected shape, i.e. they will all be orthogonally connected with no holes (diagonally neighboring letters do not count as connected). Likewise, all the B cells will form another simply-connected shape. The grid will always contain at least one A and at least one B.

Imagine the grid is actually two blocky-shaped pieces of thin plastic, represented by the A and B portions. If it were placed flat on a table, could the two pieces be slid apart while keeping both completely flat on the table?

Print or return a truthy value if the two A and B shapes could be separated like this by simply pulling them apart. If not, print or return a falsy value.

For example, the input

AAA
ABB
AAA

is truthy because the BB section can be slid to the right, separating it from the A's:

AAA
A    BB
AAA

However, the input

AAAA
ABBA
ABAA

is falsy because there's no way to slide the A and B portions apart without having them overlap.

The shortest code in bytes wins. If desired, you may use any two distict printable ASCII characters in place of A and B.

Truthy Examples (separated by empty lines)

BBB
BAA
BBB

BA

A
B

AB
AB

AAA
BBB

AAAAB
ABBBB

ABBA
ABBA
AAAA

AAAAAABBBBBBBBB
AABBBBBBBBBBBBB
AAAAAAAAAABBBBB
AABBBBBBBBBBBBB
AAAAAAAAAAAAAAB

AAAAAAAAAAAA
ABABABABABAB
BBBBBBBBBBBB

BAAAAABB
BBAAABBB
BBBABBBB
BBBABBBB
BBBABBBB
BBBBBBBB
BBBBBBBB

AAA
BAA
AAA

Falsy Examples

BBBB
BAAB
BABB

BBBB
BAAB
AABB

BBBBBBB
BBBBBAB
AAAAAAB
BBBBBBB

BAAA
BABA
BBBA
AABA
AAAA

AAAAAAA
ABBBBBA
AAAAABA
BBBBBBA

BAAAAABB
BBAAABBB
BBBABBBB
BBBABBBB
BBBAABBB
BBBBBBBB
BBBBBBBB

AAA
ABA
BBA
ABA
AAA

CJam, 33 32 20 19 17 bytes

Revised version, with massive support from @Sp3000 and @MartinBüttner:

qN/_z]{:e`z,3<}/|

Try it online

Contributions

@Sp3000 suggested a critical simplification to my original algorithm.
@MartinBüttner applied his mad golfing skills to the revised approach, which almost certainly resulted in shorter code than I would have come up with even after considering the simplification.

Algorithm and Proof

The following explains the criteria for the puzzle sliding apart horizontally. The vertical case can be determined by looking at columns instead of rows, or transposing the character matrix and looking at the rows again.

I'll use the term "stretch" for a maximum sequence of the same letters. For example, the following rows have 1, 2, and 3 stretches respectively:

AAAAAAAA
BBBAAAAA
AABBBAAA

I'll also use the term "interlocked" for a row/puzzle that cannot slide apart.

The key observation is that the puzzle can slide apart if and only if all rows have at most 2 stretches. Or reversed, it is interlocked if and only if there is any row with more than 2 stretches.

The following might not qualify as a strict mathematical proof, but I believe that it makes for a convincing explanation why this has to be the case.

It is easy to see that the puzzle is interlocked if it has rows of more than 2 stretches. Looking at a row with 3 stretches:

BBBAAB

it is clear that it prevents the puzzle from sliding apart because the A stretch is locked between the B stretches. This means that the row is interlocked, which in turn makes the whole puzzle interlocked.

The opposite direction of the proof is not quite as obvious. We need to show that there are no interlocked puzzles where all rows have only 1 or 2 stretches. Starting with a couple of observations:

Rows with only 1 stretch do not contribute to a puzzle being interlocked, since they can slide in either direction without any collisions.
If all rows with 2 stretches have the same order of A and B, the puzzle is clearly not interlocked. In this case, all A cells are left of all B cells, or vice versa, and there are no collisions when sliding the two pieces apart.

The only tricky case would be puzzles where we have rows with 2 stretches of different order. I'm going to show that such puzzles do not exist under the given specifications. To show this, let's look at a partial puzzle that does have this configuration, where . are wildcards:

.......
AAABBBB
.......
BBAAAAA
.......

Now, the specification says that both the A and B cells are simply connected in all valid puzzles. To make the A cells connected in the partial puzzle above, we have two options:

We loop around one of the stretches of B, for example:

..AAAAAA
AAABBBBA
.......A
BBAAAAAA
........

To do this, we unavoidably extend one of the rows to have 3 stretches, so this will never give us a valid puzzle where all rows have at most 2 stretches.
We connect them on a direct path:

.......
AAABBBB
..A....
BBAAAAA
.......

The A cells are now simply connected, and there are still no rows with more than 2 stretches. However, the B cells also need to be simply connected. The direct path is now blocked by the connected A cells, and the only way to connect the B cells is to loop around one of the stretches of A cells. This leads back to case 1, where we can't do that without creating rows of 3 stretches.

To count the stretches, the implementation uses the CJam RLE operator.

Explanation of Code

qN/     Get input and split at newlines.
_z      Make a transposed copy.
]       Wrap the original and transposed puzzle in an array so that we can
        loop over the two.
{       Start of loop over original and transposed puzzle.
  :e`     Apply RLE to all rows.
  z,      Transpose the matrix with the RLE rows, and take the element count of the
          result. Or in other words, take the column count. This will be the length
          of the longest row after RLE.
  3<      Check the length for less than 3.
}/      End of loop over original and transposed puzzle.
|       Or the results of the two.


Graphical Representation of Koch Snowflake Generate a Koch Snowflake
A Koch snowflake is a triangle that for each n, another equilateral point is added in the middle of each side: http://en.wikipedia.org/wiki/Koch_snowflake#Properties
We already had a kolmogrov-complexity  Koch Snowflake challenge for n=4.  The new challenge is to draw a Koch snowflake with any n between 1 and 10.
Rules

The snowflakes may not be hardcoded in the program or in files - they must be generated by your program.
Your program must support all sized n between 1 and 10.
The number of sides must be input by the user through std-in.
You must print a graphical representation of the snowflake to the screen.

Sample Koch Snowflakes with n equaling 1, 2, 3, and 4 (green lines for clarity only, do not reproduce them):

In the event of a tie-breaker, the program with the highest number of upvotes wins (pop-contest).

MATLAB, 119 115
In an unusual turn of events, I found that this program actually worked better as I golfed it. First, it became much faster due to vectorization. Now, it displays a helpful prompt ~n:~ reminding the user of which quantity to enter!
Newlines are not part of the program.
x=exp(i*pi/3);
o='~n:~';
P=x.^o;
for l=2:input(o);
P=[kron(P(1:end-1),~~o)+kron(diff(P)/3,[0 1 1+1/x 2]) 1];
end;
plot(P)

n = 9:

o is an arbitrary string which is equal to [0 2 4 0] modulo 6. eiπ/3 raised to these powers gives the vertices of an equilateral triangle in the complex plane. The first kron is used to make a copy of the list of points with each one duplicated 4 times. ~~o is the convenient way to get a vector of 4 ones. Secondly diff(P) finds the vector between each pair of consecutive points. Multiples of this vector (0, 1/3, (1 + e-iπ/3)/3, and 2/3) are added to each of the old points.


Polyglot "Hello world" in Fortran and Lisp Simple challenge: The code must be both valid Lisp and valid Fortran, and must print out "hello world" in both.

Note: I've sunk about 5 hours into this at this point, I'm not even sure it's possible at this point...

Details:

Must be in a single source file.
Any version of Fortran and any Lisp are allowed (specify which).
Smallest source code (by bytes) satisfying this wins.

Fortran (GFortran) -ffixed-form, 183 53+12=65 bytes

	;print*,"Hello world!"
	;end
*(print "Hello world!")

Try it online!

Common Lisp, 53 bytes

Try it online!


Computing truncated digits sums of powers of pi Given a positive integer n output the sum of the first n decimal digits of the fractional part of πn.

Example input and outputs:

  1 →     1
     2 →    14
     3 →     6
     4 →    13
     5 →    24
    50 →   211
   500 →  2305
  5000 → 22852

Built-in functions computing digits of π or evaluating either power series or continued fractions are not allowed. Standard loopholes apply. Input/output can be in a convenient format (stdin, stdout, function in/output, etc).

Shortest code in bytes wins.

Python - 191 Bytes

t=i=1L;k=n=input();f=2000*20**n;A=range(n+1)
for k in range(2,n):A=[(A[j-1]+A[j+1])*j>>1for j in range(n-k+1)];f*=k
while k:k=(1-~i*n%4)*f/A[1]/i**n;t+=k;i+=2
print sum(map(int,`t`[-n-4:-4]))

~4x faster version - 206 bytes
t=i=1L;k=n=input();f=2000*20**n;A=[0,1]+[0]*n
for k in range(1,n):
 f*=k
 for j in range(-~n/2-k+1):A[j]=j*A[j-1]+A[j+1]*(j+2-n%2)
while k:k=(1-~i*n%4)*f/A[1]/i**n;t+=k;i+=2
print sum(map(int,`t`[-n-4:-4]))

Input is taken from stdin. Output for n = 5000 takes approximately 14s with the second script (or 60s with the first).

Sample usage:
$ echo 1 | python pi-trunc.py
1

$ echo 2 | python pi-trunc.py
14

$ echo 3 | python pi-trunc.py
6

$ echo 4 | python pi-trunc.py
13

$ echo 5 | python pi-trunc.py
24

$ echo 50 | python pi-trunc.py
211

$ echo 500 | python pi-trunc.py
2305

$ echo 5000 | python pi-trunc.py
22852

The formula used is the following:

where An is the nth Alternating Number, which can be formally defined as the number of alternating permutations on a set of size n (see also: A000111). Alternatively, the sequence can be defined as the composition of the Tangent Numbers and Secant Numbers (A2n = Sn, A2n+1 = Tn), more on that later.
The small correction factor cn rapidly converges to 1 as n becomes large, and is given by:

For n = 1, this amounts to evaluating the Leibniz Series. Approximating π as 10½, the number of terms required can be calculated as:

which converges (rounded up) to 17, although smaller values of n require considerably more.
For the calculation of An there are several algorithms, and even an explicit formula, but all of them are quadratic by n. I originally coded an implementation of Seidel's Algorithm, but it turns to be too slow to be practical. Each iteration requires an additional term to be stored, and the terms increase in magnitude very rapidly (the "wrong" kind of O(n2)).
The first script uses an implementation of an algorithm originally given by Knuth and Buckholtz:

Let T1,k = 1 for all k = 1..n
Subsequent values of T are given by the recurrence relation:
Tn+1,k = 1/2 [ (k - 1) Tn,k-1 + (k + 1) Tn,k+1 ]
An is then given by Tn,1
(see also: A185414)

Although not explicitly stated, this algorithm calculates both the Tangent Numbers and the Secant Numbers simultaneously. The second script uses a variation of this algorithm by Brent and Zimmermann, which calculates either T or S, depending on the parity of n. The improvement is quadratic by n/2, hence the ~4x speed improvement.


Automatic box expander Introduction

Sometimes, my boxes are too small to fit anything in it. I need you to make a box expander! So, what makes a box a box in this challenge.

 OOOO
O    O
O    O
O    O
 OOOO

The corners of the box are always spaces. The box itself can be made out of the same character. That character can be any printable ASCII character, except a space. So, that's these characters:

!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

The side lengths of the box above are 4, 3. You may assume that the side length is always positive. That means that this is the smallest box you need to handle:

 #
# #
 #

In order to expand a box, you need to increment each side length. Let's go through this, step by step, with the above example. We first take the upper side of the box, which is:

 OOOO

We expand this by one, so we get:

 OOOOO

This is the upper and lower part of the box now. After that, we do the same with the sides on the left and right:

O
O
O

Becomes:

O
O
O
O

Now we reassemble the box, which results into:

 OOOOO
O     O
O     O
O     O
O     O
 OOOOO

The task

Given a box, expand it by 1. The box can be given in multiple lines, or in an array.

Test cases

 OOOO          OOOOO
O    O    >   O     O
 OOOO         O     O
               OOOOO

 XXXXXX        XXXXXXX
X      X  >   X       X
X      X      X       X
 XXXXXX       X       X
               XXXXXXX

 ~             ~~
~ ~       >   ~  ~
 ~            ~  ~
               ~~

This is code-golf, so the submission with the least amount of bytes wins!

Vim, 7 bytes

♥GYPjYp

where ♥ is Control-V.

           The cursor starts on the first non-whitespace character of the first line.
♥G         Enter visual block mode and go to bottom of document.
  YP       Duplicate this column.
    j      Move down to the second line of the file.
     Yp    Duplicate this line.


Is this ordinal prime? You are given an countable ordinal \$1 < r < \varepsilon_0\$. Determine whether or not it is prime. If not, provide exactly two ordinals \$r_0, r_1 < r\$ such that \$r_0r_1 = r\$, following rules of ordinal multiplication, and furthermore satisfy at least one (not necessarily both) of the following:

\$r_0\$ is a limit ordinal
\$r_0 \le r_1\$

More accurately, an ordinal expressed in Cantor normal form is a list \$[a_1, a_2, a_3, \dots, a_{n-1}, a_n]\$, where when \$1 \le i < n\$, \$a_i\$ is an ordinal expressed in Cantor normal form and \$a_n\$ is an integer. Furthermore, for \$1 < i < n\$, the ordinal inequality \$a_{i-1} \ge a_i\$ holds.

Input

Any input that can provably describe any ordinal also expressible in Cantor normal form is accepted. For input forms deviating greatly from Cantor normal form, please also provide a brief way to convert a Cantor normal form ordinal to input.

Output

If the given ordinal is prime, then a constant result, distinct from non-prime inputs must be returned.
Otherwise, return two ordinals, expressed the same way as the input, representing \$r_0\$ and \$r_1\$, respectively.

Scoring

This is code-golf, so shortest program (in bytes) wins.

Examples

An input of \$\omega^2+1\$, or [2,1] in Cantor normal form, would be marked prime.
On the other hand, an input of \$\omega+2\$, or [1,2] in Cantor normal form, would be composite and the program should return a pair ([2],[1,1]) in whatever form it accepted.
Remember that integers are ordinals too.
You do not need to consider \$r=1\$.

More examples:

[1,100] => [100] * [1, 1]
[2,1] => prime
[3,0] => [2,0] * [1,0]
[[1,1],2] => [2] * [[1,1],1]
[[1,1],0] => [[1,0],0] * [1,0]
[[1,0],0] => prime
[1,1,1] => [1,1] * [2]

Haskell, 1068 1042 1012 bytes

-30, mostly from replacing if/then with guards. I'm sure it can be golfed more.

data W=W[W]Int deriving Show
f EQ y=y
f x _=x
m=1<0
k=1>0
[]#[]=EQ
[]#_=LT
_#[]=GT
(W x y:z)#(W a b:d)=f(x#a)$f(compare y b)$z#d
x?y=x#y>EQ
b x=break(\(W y _)->y#x/=GT)
x&[]=x
d&(x@(W v w):u)=case b v d of(y,W f m:_)|f#v>LT->y++(W v$m+w):u;(y,_)->y++x:u
x![]=x
d!(W v w:u)=case b v d of(_:_,_)->d;(_,W f m:g)->if w<m then(W f$m-w):g else g!u
[]%_=([],k)
x@(W g h:d)%b@(W e f:_)|b?x=([],m)|g!e?[]=(\(q,r)->([W(g!e)h]&q,r))$d%b|k=(\q->(q,(foldl(&)[]$t b<$>q)#x==EQ))[W[]$div h f]
t(W x y:z)(W[]n)=(W x$y*n):z
t(W x _:_)(W b n)=[W(x&b)n]
l=all(\(W e _)->e?[])
q=max
o[]=0
o(W e n:u)=q n$q(o e)$o u
v[]=0
v(W e n:u)=q(1+length u)$q(v e)$v u
d[]=0
d(W e n:u)=q(1+d e)$d u
e(W x _:[])(W y _:_)=x?y
e(_:x)y=e x y
g _ 0_ n=[[W[]x]|x<-[1..n]]
g m d s n|p<-g m(d-1)s n=fst$h s$filter(m?)$p++[[W x y]|x<-p,y<-[1..n]]
h 1z=(z,z)
h n z|(a,p)<-h(n-1)z,n<-[x++y|x<-z,y<-p,e x y]=(a++n,n)
r x=p x$g x(d x)(v x)$o x
p _[]="p"
p x(y:z)|(q,r)<-x%y,x?y&&x?q&&r&&(l y||not(l y&&l q||d y<2&&d q<2)||y#q<GT)=show y++"*"++show q|k=p x z

Try it online!

Or try a version that pretty-prints the inputs and outputs.

Input Format

The input format is Cantor normal form, written as \$\omega ^{\beta _{1}}c_{1}+\omega ^{\beta _{2}}c_{2}+\cdots+\omega ^{\beta _{k}}c_{k}\$, where \$k\$ is a natural number, \$ c_{1},c_{2},\ldots ,c_{k}\$ are positive integers, and \$ \beta _{1}>\beta _{2}>\ldots >\beta _{k}\geq 0 \$ are ordinal numbers.

Each term \$\omega ^{b}c\$ is written as W b c and terms are written as a list in [] separated by commas.

Examples:

[]\$ = 0\$

[W[]1]\$ = 1\$

[W[W[]1]1]\$ = \omega\$

[W[W[]1]1,W[]1]\$ = \omega + 1\$

[W[W[]2]3,W[]4] \$=\omega^2\cdot 3 + 4\$

[W[W[W[]2]1]1,W[]4] \$=\omega^{\omega^2} + 4\$

[W[W[W[]1]1,W[]1]1,W[]1]\$ = \omega^{\omega+1} + 1\$

Test Cases

Output from the main version:

[W [W [] 2] 1,W [] 1] => p
[W [W [W [] 1] 1] 1] => p
[W [W [W [W [] 1] 1] 1] 1] => p
[W [W [] 1] 1,W [] 100] => [W [] 2]*[W [W [] 1] 1,W [] 50]
[W [W [] 3] 1] => [W [W [] 1] 1]*[W [W [] 2] 1]
[W [W [W [] 1] 1,W [] 1] 1,W [] 2] => [W [] 2]*[W [W [W [] 1] 1,W [] 1] 1,W [] 1]
[W [W [W [] 1] 1,W [] 1] 1] => [W [W [W [] 1] 1] 1]*[W [W [] 1] 1]
[W [W [] 1] 2,W [] 1] => [W [W [] 1] 1,W [] 1]*[W [] 2]
[W [] 2903591] => [W [] 1699]*[W [] 1709]

Output from the pretty-print version:

[W [W [] 2] 1,W [] 1] == w^2 + 1 => p
[W [W [W [] 1] 1] 1] == w^w => p
[W [W [W [W [] 1] 1] 1] 1] == w^(w^w) => p
[W [W [] 1] 1,W [] 100] == w + 100 => (2)*(w + 50)
[W [W [] 3] 1] == w^3 => (w)*(w^2)
[W [W [W [] 1] 1,W [] 1] 1,W [] 2] == w^(w + 1) + 2 => (2)*(w^(w + 1) + 1)
[W [W [W [] 1] 1,W [] 1] 1] == w^(w + 1) => (w^w)*(w)
[W [W [] 1] 2,W [] 1] == w*2 + 1 => (w + 1)*(2)
[W [] 2903591] == 2903591 => (1699)*(1709)

Strategy

This is probably not the fastest solution, but I thought it might be relatively short for code golf. It works for all of the test cases and works well for natural numbers. For ordinals with many terms, this may take a very long time to run.

Generate a sequence of ordinals which may divide the input.
Test each ordinal in the sequence to determine whether it divides the input and meets the additional criteria. If it does, return a formatted string containing the divisor and quotient.
If the sequence was exhausted, return "p" for prime.

Implementation

I started with code I found online that implements ordinal addition and multiplication and uses the QuickCheck library to test that properties (theorems) are true for a large number of inputs.

I implemented left subtraction and then left division with remainder and verified that the operations were consistent with the following theorems.

Left subtraction: Let \$x\$ and \$y\$ be ordinals such that \$x \geq y\$. Then there exists a unique ordinal \$z\$ such that \$x = y + z\$.

Left division: Let \$x\$ and \$y\$ be ordinals. Suppose \$y\neq0\$. Then there exist unique ordinals \$z\$ and \$w\$ such that \$x=y\cdot z+w\$ and \$w < y\$.

Generated Sequences

To test whether an ordinal is prime, I generate a list of potential divisors. This would be easy for natural numbers, but infinite ordinals are greater than infinitely many ordinals.

I check the given ordinal to determine the depth, maximum number of terms (at each depth), and maximum coefficient.

I then recursively generate ordinals that are less than the given one and up to the given depth, term count, maximum coefficient. I don't have a proof that this is sufficient, but intuitively it seems like it would be.

Here are some examples.

Example 1: \$\omega^2\cdot 3 + 4\$. Depth: 2, Max term count: 2, Max coefficient: 4. Generated list of potential divisors, length 26: \$1, 2, \omega, \omega + 1, \omega + 2, \omega\cdot2, \omega\cdot2 + 1, \omega\cdot2 + 2, \omega^2, \omega^2 + 1, \omega^2 + 2, \omega^2 + \omega, \omega^2 + \omega + 1, \omega^2 + \omega + 2, \omega^2 + \omega\cdot2, \omega^2 + \omega\cdot2 + 1, \omega^2 + \omega\cdot2 + 2, \omega^2\cdot2, \omega^2\cdot2 + 1, \omega^2\cdot2 + 2, \omega^2\cdot2 + \omega, \omega^2\cdot2 + \omega + 1, \omega^2\cdot2 + \omega + 2, \omega^2\cdot2 + \omega\cdot2, \omega^2\cdot2 + \omega\cdot2 + 1, \omega^2\cdot2 + \omega\cdot2 + 2\$

Example 2: \$\omega^\omega\cdot3+4\$. Depth: 3, Max term count: 2, Max coefficient: 4. Generated terms list length: 151,994.
Since that list is generated lazily, the program still gives a fast answer.

As the depth and maximum term count increase, the lengths of the generated sequences increase very quickly.

Note

For the last given test case, \$\omega\cdot2+1=(\omega+1)\cdot2\$, I was unable to satisfy either of the two given additional criteria (\$_0\$ is a limit ordinal, \$_0 \leq r_1\$). However, I was able to satisfy the following criteria stated on Wikipedia, which is a slight variation of the given criteria:

Every limit prime occurs before every successor prime
If two consecutive primes of the prime factorization are both limits or both finite, then the second one is at most the first one.

If anyone is interested, I could provide a less golfed version of this code.


Visualize Church numerals Background

Visualizing λ-calculus terms

Famous lambda-juggler (and code golfer) John Tromp devised an interesting visualization of terms in the λ-calculus. In his words:

  abstractions (lambdas) are represented by horizontal lines, variables by vertical lines emanating down from their binding lambda, and applications by horizontal links connecting the leftmost variables.

For example, the lambda term λf.λx.f (f (f (f x))) corresponds to the visualization:

-------------------
 |   |   |   |
-------------------
 |   |   |   |   |
 |   |   |   |----
 |   |   |----
 |   |----
 |----
 |

Read it from top to bottom:

The first horizontal line represents the first λ.
The four lines descending from it represent the fs in the body.
Similarly, the second horizontal line represents the second λ, and the single new line descending from it represents the x in the body.
The rightmost f line and the x line are connected by a horizontal line representing an application (f x).
The next application is (f (f x)), et cetera.

Church numerals

The Church numerals are a specific sequence of terms in the λ-calculus, taking on the following pattern:

0 = λf. λx. x
1 = λf. λx. f x
2 = λf. λx. f (f x)
3 = λf. λx. f (f (f x))
...

Task

Given an input number n, print some ASCII art that visualizes the nth Church numeral. For instance, the example above is your target output when given n = 4. For n = 0, print:

---

---
 |
 |

Test cases

Your answer must output exactly the same text (modulo trailing newlines) as this stack snippet for all integer inputs n ≥ 0:

function visualize() {
  var vin = document.getElementById('visualize-in');
  var vout = document.getElementById('visualize-out');
  var n = Number(vin.value);
  if (n < 0) n = 0;
  var line = '-'.repeat(4 * n + 3);
  var bars = function(k) { return '   |'.repeat(k).substr(2); };
  var img = [line, bars(n), line, bars(n + 1)];
  for (var i = n; i > 0; --i) img.push(bars(i) + '----');
  vout.innerHTML = img.join('\n') + '\n |';
}
n&nbsp;<input style="width:50px;" type="number" id="visualize-in" name="visualize-in" onchange="visualize()"/>

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

Retina, 74 67 63 bytes

Byte count assumes ISO 8859-1 encoding.

.
 |
^
$.'$*----¶
\z
¶$` |
+`(.+\|) .+$
$&¶$1----
$
¶ |
  ¶
¶

Input is in unary, using any character except linefeeds as the digit.

Try it online!

Explanation

.
 |

We start by turning each unary digit into  |   (note the trailing spaces). This gives us the second line of the output (plus two trailing spaces if the input is at least 1).

^
$.'$*----¶

We match the beginning of the string in order to prepend the first line. This is done using some Retina-specific substitution features. $* repeats the character on the right as many times as its left arugment. $.' evaluates the number of characters to the right of the match. Since the match is only the beginning of the string this gives as many - as there are characters in the string and --- appends three more. The ¶ is an alias for a linefeed. So now we've got the first two lines.

\z
¶$` |

Now we append the next two lines. We do this by matching the end of the string and appending a linefeed, the entire string again and then  | to get the fourth line right.

+`(.+\|) .+$
$&¶$1----

Time for the applications. The leading + makes Retina repeat this stage until the output stops changing (in this case because the regex no long matches). The regex matches the entire last line, provided it contains a | follows by a space. We capture everything up to the | (which will be the second to last) in group 1. We write the line back with $&, a linefeed, then group 1 (thereby dropping the last |) and then ----.

$
¶ |

This just adds the final line containing only a single |.

  ¶
¶

Finally we need to get rid of the trailing spaces on the second line.


Encode Images into Tweets (Extreme Image Compression Edition) Based on the very successful Twitter image encoding challenge at Stack Overflow.

If an image is worth 1000 words, how much of an image can you fit in 114.97 bytes?

I challenge you to come up with a general-purpose method to compress images into a standard Twitter comment that contains only printable ASCII text.

Rules:

You must write a program that can take an image and output the encoded text.
The text created by the program must be at most 140 characters long and must only contain characters whose code points are in the range of 32-126, inclusive.
You must write a program (possibly the same program) that can take the encoded text and output a decoded version of the photograph.
Your program can use external libraries and files, but cannot require an internet connection or a connection to other computers.
The decoding process cannot access or contain the original images in any way.
Your program must accept images in at least one of these formats (not necessarily more): Bitmap, JPEG, GIF, TIFF, PNG. If some or all of the sample images are not in the correct format, you can convert them yourself prior to compression by your program.

Judging:

This is a somewhat subjective challenge, so the winner will (eventually) be judged by me. I will focus my judgment on a couple of important factors, listed below in decreasing importance:

Ability to do a reasonable job of compressing a wide variety of images, including those not listed as a sample image
Ability to preserve the outlines of the major elements in an image
Ability to compress the colors of the major elements in an image
Ability to preserve outlines and colors of the minor details in an image
Compression time. Although not as important as how well an image is compressed, faster programs are better than slower programs that do the same thing.

Your submission should include the resulting images after decompression, along with the Twitter comment generated.  If possible, you could also give a link to the source code.

Sample images:

The Hindenburg,
Mountainous Landscape,
Mona Lisa,
2D Shapes

I've improved my method by adding actual compression. It now operates by iteratively doing the following:

Convert the image to YUV
Downsize the image preserving the aspect ratio (if the image is color, the chroma is sampled at 1/3 the width & height of the luminance)
Reduce the bit depth to 4 bits per sample
Apply median prediction to the image, making the sample distribution more uniform
Apply adaptive range compression to the image.
See if the size of the compressed image is <= 112

The largest image that fits in the 112 bytes is then used as the final image, with the remaining two bytes used to store the width & height of the compressed image, plus a flag indicating if the image is in color. For decoding, the process is reversed, and the image scaled up so the smaller dimension is 128.

There is some room for improvement, namely not all the available bytes are used typically, but I feel I'm at the point of significantly diminishing returns for downsampling + lossless compression.

Quick & dirty C++ source

Windows exe

Mona Lisa (13x20 luminance, 4x6 chroma)

&Jhmi8(,x6})Y"f!JC1jTzRh}$A7ca%/B~jZ?[_I17+91j;0q';|58yvX}YN426@"97W8qob?VB'_Ps`x%VR=H&3h8K=],4Bp=$K=#"v{thTV8^~lm vMVnTYT3rw N%I

Hindenburg (21x13 luminance)

GmL<B&ep^m40dPs%V[4&"~F[Yt-sNceB6L>Cs#/bv`\4{TB_P Rr7Pjdk7}<*<{2=gssBkR$>!['ROG6Xs{AEtnP=OWDP6&h{^l+LbLr4%R{15Zc<D?J6<'#E.(W*?"d9wdJ'

Mountains (19x14 luminance, 6x4 chroma)

Y\Twg]~KC((s_P>,*cePOTM_X7ZNMHhI,WeN(m>"dVT{+cXc?8n,&m$TUT&g9%fXjy"A-fvc 3Y#Yl-P![lk~;.uX?a,pcU(7j?=HW2%i6fo@Po DtT't'(a@b;sC7"/J

2D Shapes (21x15 luminance, 7x5 chroma)

n@|~c[#w<Fv8mD}2LL!g_(~CO&MG+u><-jT#{KXJy/``#S@m26CQ=[zejo,gFk0}A%i4kE]N ?R~^8!Ki*KM52u,M(his+BxqDCgU>ul*N9tNb\lfg}}n@HhX77S@TZf{k<CO69!


Convert to camelCase The Challenge

I was reading Google's Java Style Guide the other day and stumbled over their algorithm to convert any arbitrary string into camelCase notation. In this challenge you have to implement this algorithm since you dont want to do all this stuff in your head when you are writing your super competitive Java submissions to code-golf challenges.

Note: I made some small adjustments to the algorithm. You need to use the one specified below.

The algorithm

You start with an arbitrary input string and apply the following operations to it:

Remove all apostrophes `'
Split the result into words by splitting at

characters that are not alphanumerical and not a digit [^a-zA-Z0-9]
Uppercase letters which are surrounded by lowercase letters on both sides. abcDefGhI jk for example yields abc Def Ghi jk

Lowercase every word.
Uppercase the first character of every but the first word.
Join all words back together.

Additional notes

The input will only contain printable ASCII.
If a digit is the first letter in a word, leave it as it is and don't capalize something else in this word.
The input will always have at least one character.

Rules

Function or full program allowed.
Default rules for input/output.
Standard loopholes apply.
This is code-golf, so lowest byte-count wins. Tiebreaker is earlier submission.

Test cases

"Programming Puzzles & Code Golf" -> "programmingPuzzlesCodeGolf"
"XML HTTP request" -> "xmlHttpRequest"
"supports IPv6 on iOS?" -> "supportsIpv6OnIos"
"SomeThing w1th, apo'strophe's and' punc]tuation" -> "someThingW1thApostrophesAndPuncTuation"
"nothing special" -> "nothingSpecial"
"5pecial ca5e" -> "5pecialCa5e"
"1337" -> "1337"
"1337-spEAk" -> "1337Speak"
"whatA mess" -> "whataMess"
"abcD" -> "abcd"
"a" -> "a"
"B" -> "b"

Happy Coding!

Retina, 56 bytes

Byte count assumes ISO 8859-1 encoding.

T`'\`
S_`\W|_|(?<=[a-z])(?=[A-Z][a-z])
T`L`l
T`l`L`¶.
¶

Try it online!

Explanation

This implements the specification quite literally:

T`'\`

Remove apostrophes and backticks.

S_`\W|_|(?<=[a-z])(?=[A-Z][a-z])

Split the string around non-word characters (in regex this also excludes digits and underscores), or underscores or positions that have a lower case letter on the left and and upper case, lower case on the right. This would create some empty segments when there are two non-letter, non-digit characters in a row, or more important at the beginning of the string. We get rid of those with the _ option. Here, "splitting" means put each remaining part on its own line.

T`L`l

Convert everything to lower case.

T`l`L`¶.

Convert each character that occurs after the linefeed to upper case. This will conveniently skip the first word because there's no linefeed in front of it.

¶

Get rid of the linefeeds to join everything back together.


Determine which of two ImageMagick .TXT images is more saturated You have two images (64x64 pixels each):

Your program must take the file names of each of them as command line arguments and determine which has more average saturation among their pixels.

The images are in ImageMagick .txt format.  You can download and convert these images using convert pic.png pic.txt or download the raw text (saturated, desaturated)

Ignore the first line of the file (required).

Solutions in Assembly get 50% of their characters for free.  Brainfuck, whitespace, and close variants, get 25% of their characters for free.  (e.g. if it takes 200 characters in Brainfuck; mark it as 200-50=150.)

Describe your output.  It could be the name of the more saturated image; the index of it (0 for first, 1 for second); true for the first, false for the second, etc.  Just let us know.

It should be able to take either the saturated or desaturated image first, and accurately report the more saturated (test both ways).  The filenames shouldn't be considered when evaluating saturation (e.g. no if filename contains 'desaturated'...)

Shortest answer wins.  Happy coding :-)

bash etc. and Image Magick (136 chars)

for x in "$@";do convert "$x" -colorspace HSL -channel G -separate -scale 1x1 t.txt
echo `sed "1d;s%.*#\(..\).*%\1%" t.txt` $x;done|sort

The way I see it, the easiest way to deal with the complexities of the Image Magick file format is to let Image Magick do it. t.txt seems to be the shortest possible filename which guarantees the correct output file format. The first 4 " could arguably be removed, but that would decrease robustness in the face of filenames with spaces in.

Sample output:

$ ./cmpsat.sh img-sat.txt img-desat.txt rose:
24 img-desat.txt
69 rose:
FE img-sat.txt


Shortest python A + B program with input and output Some of you may say that I am wasting my time, but this task does not give me peace for more than 500 days. It is required to write a program in Python 3.x that takes two numbers as input and displays their sum. The numbers are given in the following format:

a b

Some example test cases:

100 500 -> 600
3 4     -> 7

The length of the code is calculated with the formula max(code length without spaces or tabs or newlines, code length / 4). I know only 2 solutions, each of them has a length of 36 characters:

print(sum(map(int, input().split())))

and:

print(eval(input().replace(' ', '+')))

Also I know, that the exists solution with length of 34 symbols. You can check it on this website.

Given the right hint toward the solution in the comment to the same question asked on stackoverflow ( see here ), I have got it right down to 34 and without any limitations on the input number or other tricks necessary:
print(eval(input().replace(*' +')))
Here a short summary of currently known different solutions:

print(eval(input().replace(' ','+')))  # 36
print(sum(map(int,input().split())))   # 36
print(eval(input().replace(*' +')))    # 34
print(sum(map(int,input()[::2])))      # 33 (limited to numbers between 0 and 9)

Maybe it could be considered cheating, but maybe not. At least there is no rule for this defined yet so let's include it into the collection of possible solutions:

import f;f.f()                         # 13

Required for this solution to work is a script f.py available in a search directory for modules of Python with following content:
def f():
    print(sum(map(int,input().split())))


Evaluate Index of Multidimensional Coordinates A collection of N dimensional coordinates are provided. An example is below:

{2,3,4}

This can be thought of as a 3 dimensional array with 2x's, 3y's and 4z's; there may be any number of dimensions. In the example, there are 24 total nodes. Each node can be indexed using {x,y,z}. To access the 5th node, the provided indices would be {0, 1, 0} based on the table below.

## | x y z
     0 1 2
-----------
0  | 0 0 0
1  | 0 0 1
2  | 0 0 2
3  | 0 0 3
4  | 0 1 0
5  | 0 1 1
6  | 0 1 2
7  | 0 1 3
8  | 0 2 0
...
23 | 1 2 3

The purpose of this application is to work backwards to determine an index if given a node number.

If asked for the "y" index of the 8th node, the program should print "2".

With the following input provided:

{2,3,4}|8|1
<List of Coordinates>|<Node>|<Index>

The following should be printed:

2

You can assume that the input will be provided in some convenient manner in your language of choice and does not require bounds checking. For example you may assume that the provided index of choice ("y" in the example) is valid with respect to the provided coordinates. You may use 0 or 1 based indexing; the example presumes 0 based.

This is sort of the reverse of this question:
Index of a multidimensional array

MATL, 8 bytes

PiX[vPi)

This uses 1-based indexing for the node and for the dimensions. So the first nodes are 1, 2 etc; and the "x" dimension is 1, "y" is 2 etc.

Try it online!

Explanation

The key is to use function X[ (corresponding to ind2sub in Matlab or Octave), which converts a linear index into multidimensional indices. However, the order of dimensions if the opposite as defined in the challenge, so P (flip) is needed before calling the function, and again after concatenating (v) its ouputs.

P    % Implicit input: size as a row vector. Flip
i    % Input: node (linear) index
X[   % Convert from linear index to multidimensional indices. Produces
     % as many outputs as entries there are in the size vector
v    % Concatenate all outputs into a column vector
P    % Flip
i    % Input: dimension
)    % Index: select result for that dimension. Implicitly display


Steganographic Squares Steganographic Squares
Your job is to take in a string, and generate an NxN image that represents this string. You must also write the algorithm that takes in the image and turns it back into a string as well. The scoring will be will include the byte count of both algorithms:
"Encryption" Algorithm + "Decryption" Algorithm.
You should post each separately, with byte-counts for both the encryption and decryption algorithms displayed individually.

Example Algorithm
For instance, here's the "Programming Puzzles and Code Golf" using a simple ASCII based steganographic algorithm in the Blue channel:
#2e7250,#6ea972,#04eb6f,#0fc767,#74ab72,#ee6161
#b73b6d,#1aae6d,#f37169,#bda56e,#1fe367,#e99620
#706450,#0d3575,#146b7a,#4ea47a,#2a856c,#95d065
#3f2d73,#cef720,#bab661,#d1b86e,#f22564,#12b820
#0f3d43,#c86e6f,#1ee864,#a66565,#247c20,#c3bb47
#0e296f,#89d46c,#585b66,#c08f20,#455c20,#136f20

Actual Image (  )

You can see the blue channel simply holds the ascii values for this image:
50 =  80(P) 72 = 114(r) 6f = 111(o) 67 = 103(g) 72 = 114(r) 61 =  97(a)
6d = 109(m) 6d = 109(m) 69 = 105(i) 6e = 110(n) 67 = 103(g) 20 =  32( )
50 =  80(P) 75 = 117(u) 7a = 122(z) 7a = 122(z) 6c = 108(l) 65 = 101(e)
73 = 115(s) 20 =  32( ) 61 =  97(a) 6e = 110(n) 64 = 100(d) 20 =  32( )
43 =  67(C) 6f = 111(o) 64 = 100(d) 65 = 101(e) 20 =  32( ) 47 =  71(G)
6f = 111(o) 6c = 108(l) 66 = 102(f) 20 =  32( ) 20 =  32( ) 20 =  32( )

While the rest of the channels hold randomly generated values to "spice up" the variety of colors in the image. When pulling the message back out of the image, we can just simply ignore the other channel values, and pull the hex bit in the blue channel, reconstructing the string:
"Programming Puzzles and Code Golf"

Notice the spaces that were used to pad the string in the square are not included in the final decrypted output. While you must pad the string in the image, you may assume that the input string will not end with spaces.

Rules

You must encode 1 character per pixel, the channel chosen to encode the char is arbitrary.
The channels of the other RGB colors must be randomized, other than the one you're choosing to encode the string into; this means your final non-encoded channels would need to be between 0x0000-0xFFFF (randomly chosen).
Expressing the final result as a 2D array of RGB color values is fine 0x000000-0xFFFFFF, no need to use image creation unless you want to have fun with it or if it's less bytes. If you choose to output as hex strings, prefix the hex string with # E.G. #FFFFFF or #05AB1E. You may separate with tabs, commas, or anything else that would be horizontally sensible, but it must maintain the square pattern; in other words, you must use appropriate newline separation.
The output must be in a square, and the string must be padded with spaces at the end to accomodate this. This means that N≈SQRT(Input#Length()). If the input length is not a perfect square, you should round up on N and pad with spaces.
As stated previously, if you are padding with spaces in the image, you must not include the padded characters in the final "decrypted" output.
You can assume that:

The input string will not end with spaces.
The input string will only use printable ASCII characters.

This is code-golf, lowest byte count wins.

C, 201 (Encoding) + 175 (Decoding) = 376 bytes
To Encode:
E(char*J){size_t L=ceil(sqrt(strlen(J)));int U;srand(time(NULL));for(int i=0;i<L;i++){for(int f=0;f<L;f++){printf("#%02X%02X%02X ",rand()%256,(U<strlen(J))?(int)J[U]:32,rand()%256);U+=1;}printf("\n");}}

Encodes each character of the input string in the green channel of the RGB spectrum while setting the two other channels as random hex values. Takes input through STDIN as a string and outputs to STDOUT a multiline string of hex color code in the shape of a square. Assuming you have Python 3 and ImageMagick installed, and the above file is compiled into a file named a.out in the current working directory (CWD), you can directly get the resulting image, named Output.png, to the CWD from the textual output using the following command:
./a.out "<Multiline Input>"|python3 -c "import sys,subprocess;Input=sys.stdin.read();print('# ImageMagick pixel enumeration: {0},{0},255,rgb\n'.format(len(Input.split('\n')[1].split()))+'\n'.join(['%d,%d:(%d,%d,%d)'%(g,i,int(j[1:][:2],16),int(j[1:][2:4],16),int(j[1:][4:6],16))for g,h in enumerate(Input.split('\n'))for i,j in enumerate(h.split())]))"|convert - -scale 1000% Output.png

Here is a sample output image created by the above commamd using Programming Puzzles and Code Golf as the input string:

To Decode:
D(int c,char**U){char T[c];for(int Y=1;Y<c;Y++){char G[2]={U[Y][3],U[Y][4]};T[Y-1]=(char)strtol(G,NULL,16);}int C=c-1;T[C]='\0';while(T[C]==' '){T[C]='\0';C-=1;}printf("%s\n",T);}

Takes input through STDIN a sequence of space-separated hex color code strings with each one enclosed in double quotes (") (char** argv in main) and also, when called in main, int argc for the integer input. Outputs to STDOUT a single/multi-line string representing the decoded message.
I will try to golf these more over time whenever and wherever I can.

Also, if you same both of the methods into the same file, you can use the following main method to put it all together with each function getting the correct inputs:
int main(int argc,char**argv){if(strcmp(argv[1],"E")==0){Encode(argv[2]);}else{Decode(argc,argv);}}

and using this, for encoding you must provide E as the first argument to call the encoding method followed by the single string argument, whereas for decoding, all you need to provide is the sequence of space-separated hex color code strings with each one enclosed in double-quotes (").

Finally, if you want, you can get the fully prepared, ready-to-use version here, although it is not golfed, but also does not output any warnings or errors upon compilation.


Counting Abelian groups of a given size Background
Last time, we counted groups of a given size, which is a non-trivial problem.
This time, we'll only count Abelian groups, i.e., groups with a commutative operation. Formally, a group (G, ∗) is Abelian if x ∗ y = y ∗ x for for all x, y in G.
The problem becomes much simpler this way, so we're going to count them efficiently.
Task
Write a program or function that accepts a non-negative integer n as input and prints or returns the number of non-isomorphic Abelian groups of order n.
One way of calculating the number of groups – which we'll denote by A(n) – is by observing the following:

A(0) = 0

If p is a prime, A(pk) is equal to the number of integer partitions of k. (cfr. OEIS A000041)

If n = mk, and m and k are co-prime, A(n) = A(m)A(k).

You may use this or any other method of calculating A(n).
Test cases
Input               Output
0                   0
1                   1
2                   1
3                   1
4                   2
5                   1
6                   1
7                   1
8                   3
9                   2
10                  1
11                  1
12                  2
13                  1
14                  1
15                  1
16                  5
17                  1
18                  2
19                  1
20                  2
4611686018427387904 1300156
5587736968198167552 155232
9223371994482243049 2

(taken from OEIS A000688)
Additional rules

Given enough time, RAM and a register size that can hold the input, your code should work (in theory) for arbitrarily large integers.

Your code must work for all integers between 0 and 263 - 1 and finish in under 10 minutes on my machine (Intel i7-3770, 16 GiB RAM, Fedora 21).
Please make sure you time your code for the last three test cases before submitting your answer.

Built-ins that trivialize this task, such as Mathematica's FiniteAbelianGroupCount, are not allowed.

Built-ins that return or count the integer partitions of a number or the partitions of a list are not allowed.

Standard code-golf rules apply.

CJam, 50 49 47 43 bytes

ri_mF{1=_L{1$0>{,f{):X-Xj}:+}{;!}?}2j}%:*e&

Uses CJam's builtin mF factorisation and a memoised port of this Python partition number function:

p=lambda n,x:n==0 or n>0and sum(p(n+~a,a+1)for a in range(x))

or ungolfed:

def p(n, x): # Call like p(n, n). n is number remaining, x is max part size
  if n > 0:
    return sum(p(n-a-1,a+1)for a in range(x))
  else:
    return (n==0)

Like @RetoKoradi's answer, the last case takes about 17 seconds on the offline interpreter because that's how long it takes CJam to factorise the number. Hence I've left it out of this online test suite.

Full explanation

[Main body]
ri                                Read input and convert to int
  _          e&                   Logical AND input with final result to special case 0
   mF                             Factorise input into [base, exponent] pairs
     {...}%                       Map, converting each pair to a partition number
           :*                     Take product

[Pair -> partition]
1=_                               Get exponent and copy (n,x in above Python)
   L                              Initialise empty cache
    {                       }2j   Memoise with 2 arguments
     1$0>                         Check if n > 0
         {            }{  }?      Execute first block if yes, else second block
                        ;!        Return (n == 0)
          ,f{      }              For each a in range(x) ...
             ):X-Xj               Call p(n-a-1,a+1) recursively
                    :+            Sum the results


Polynomial extrapolation Task

Given a list of integers a1, a2, …, ak (k ≥ 2) and a positive integer m, write a function or a complete program that calculates the next m numbers of the list. Assume that ai = P(i) where
P(x) = bk-1 xk-1 + bk-2 xk-2 + … + b0
is the unique polynomial of minimum order which fits the points.

Description
Input
If the code is a function, input is given by an integer k, an array a1, a2, …, ak and an integer m.
If the code is a program, input (through stdin) is given by space-separated k a1 a2 … ak m.
You can assume that k ≥ 2 and m > 0.
Calculation
(Of course, the code can calculate the result in different way, but the result should be same.)
Find the polynomial P(x) which satisfies ai = P(i) for all 1 ≤ i ≤ k and has a degree of (no more than) k - 1. For example, if a list is 1,2,3,4,5, then P(x) = x. If a list is 1,4,9,16,25, then P(x) = x2.
Then, calculate ak+1 = P(k+1), ak+2 = P(k+2), …, ak+m = P(k+m). These are the results.
Output
If the code is a function, return an array [ak+1, ak+2, …, ak+m].
If the code is a full program, print those numbers to stdout, separated by an any character you want.

Golfscript, 46 42 40 38 chars

~])\({[{.@-\}*])\}*;]-1%){0\{+.}/p]}*;

This uses a simple difference table approach, which is described in more detail on my GolfScript blog.


Render "Digital Clock Style" Numbers Write the shortest program which will take a string of numbers (of up to at least 20 length) as input, and display the output using the standard digital clock style numbers.  For instance for input 81, a solution with ascii output would give:

 _
|_|  |
|_|  |

Graphical output is also acceptable, if it helps.

Funciton

Not really a language suitable for golfing... but regardless, I tried to keep the code size as small as I could — quite a different challenge than in “usual” languages. This is 1555 characters or 3110  bytes (if encoded as UTF-16; UTF-8 is larger).

Here’s a screenshot of the program running. It really works :)

Since this looks ugly in StackExchange due to the extra line spacing, consider running the following code in your browser’s JavaScript console to fix that: $('pre').css('line-height',1)

     ╓─╖ ╔╗┌─╖   ┌─╖
     ║ʜ║ ║╟┤↔╟┐ ┌┤‼╟┐
     ╙┬╜ ╚╝╘═╝│ │╘╤╝│
╔═╗  ┌┴────┐  │┌┴╖ ┌┴╖
║0║ ┌┴─┐  ┌┴─┐└┤ʜ╟─┤·╟┐
╚╤╝┌┴╖┌┴╖┌┴╖┌┴╖╘╤╝ ╘╤╝│
┌┘┌┤·╟┤ɦ╟┤·╟┤?╟ │  ┌┴╖│
│ │╘╤╝╘╤╝╘╤╝╘╤╝ └──┤‼╟┘
│┌┴╖│ ┌┴╖┌┘╔═╧╗    ╘═╝
└┤?╟┘┌┤?╟┘┌╢10║    ┌─────────┐
 ╘╤╝ │╘╤╝┌┘╚══╝ ┌─┬┘╔══╗┌──╖┌┴╖ ╓─╖
  ┘  └───┘╔════╗│┌┴┐║21╟┤>>╟┤·╟┐║ɦ║
╔════════╗║1005╟┘└┬┘╚══╝╘═╤╝╘╤╝│╙┬╜        ┌─┐
║14073768║╚════╝ ┌┴╖ ┌─╖ ┌┴╖┌┴╖└─┴─────────┘┌┴╖
║7584800 ╟───────┤?╟─┤‼╟─┤ʜ╟┤·╟─────────────┤·╟┐╔═══════╗╔══╗
╚════════╝       ╘╤╝ ╘╤╝ ╘╤╝╘╤╝    ╔══╗┌─╖┌┐╘╤╝│║2097151║║21╟┐
 ╔═══════════════╗│   ┘   │  │     ║48╟┤−╟┤├─┤┌┘╚══╤════╝╚══╝│
 ║140737555464224╟┘  ┌────┘┌┬┘     ╚══╝╘╤╝└┘┌┘│╓─╖ │┌┐┌─╖┌─╖┌┴─╖
 ╚═══════════════╝   │ ┌───┘└─────────┐┌┴─╖ │┌┘║↔║ ├┤├┤‼╟┤↔╟┤>>║
┌────────────┐┌────┐┌┴╖│┌────────────┐├┤<<║ ││ ╙┬╜┌┘└┘╘╤╝╘═╝╘╤═╝
│   ╔══╗╔═══╗├┘╓─╖ └┤·╟┘│   ╔══╗╔═══╗├┘╘╤═╝ │└─┐└─┤╔═╗┌┴╖ ┌──┘
│   ║95║║892║│┌╢‡╟┐ ╘╤╝ │   ║95║║877║│ ┌┘╔══╧═╗│  │║0╟┤?╟┬┘
│   ╚═╤╝╚═╤═╝││╙─╜│  │  │   ╚═╤╝╚═╤═╝│╔╧╗║2097║│  │╚═╝╘╤╝│
│╔══╗┌┴╖┌┐│  ││┌─╖│ ┌┴╖ │╔══╗┌┴╖┌┐│  │║1║║151 ║│  └──────┘
│║32╟┤?╟┤├┤  │└┤‼╟┘┌┤‡║ │║32╟┤?╟┤├┤  │╚═╝╚════╝│
│╚══╝╘╤╝└┘└──┴┐╘╤╝ │╘╤╝ │╚╤═╝╘╤╝└┘└──┴┐      ┌─┘
│    ┌┴╖     ┌┴╖┌─╖│ │ ┌┴╖│  ┌┴╖     ┌┴╖ ┌─╖┌┴╖
│    │‼╟─────┤·╟┤‼╟┘ │┌┤·╟┘  │‼╟─────┤·╟─┤‼╟┤‡║
└┐┌┐ ╘╤╝     ╘╤╝╘╤╝  ││╘╤╝┌┐ ╘╤╝     ╘╤╝ ╘╤╝╘╤╝
 ├┤├┐┌┴╖╔══╗  └──┐┌┐ │└┐├─┤├┐┌┴╖╔══╗  ├──┐└  │
 │└┘└┤?╟╢32║╔═══╗├┤│┌┴╖││ └┘└┤?╟╢32║╔═╧═╗│┌┐┌┴╖╔══╗
╔╧══╗╘╤╝╚══╝║881╟┘│├┤?╟┘│    ╘╤╝╚══╝║325║└┤├┤?╟╢32║
║927║╔╧══╗  ╚═══╝ └┘╘╤╝╔╧═══╗╔╧══╗  ╚═══╝ └┘╘╤╝╚══╝
╚═══╝║124╟───────────┘ ║1019║║124╟───────────┘
     ╚═══╝             ╚════╝╚═══╝

It could probably be smaller if I hadn’t made a mistake due to which the output was back to front; I fixed that by adding an extra function to reverse the input. Otherwise I would probably have to rewrite all of it.

I also made another mistake (swapping the operands in two calls to ‼) which made it necessary to declare the extra ‡ function, but this one is so small it fits inside the main function and thus doesn’t add any characters!


Dutch Burgerservicenummer (BSN) eleven-test Introduction:
A Dutch BSN (BurgerServiceNummer) is valid when it complies to the following rules:

It only contains digits.
The length should be either 8 or 9 in length.
When the digits are indexed as A through I, the result of the following sum: 9xA + 8xB + 7xC + 6xD + 5xE + 4xF + 3xG + 2xH + -1xI (NOTE the -1 instead of 1!) should be divisible by 11, and should not be 0.

Challenge:
Input: A string or char-array representing the BSN.
Output: A truthy or falsey result whether the input is a valid BSN.
Challenge Rules:

The input format should be a string or char-array. You are not allowed to use an int-array of digits, or a (possibly octal) number. (You are allowed to convert it to an int-array of digits yourself, though, but not directly as argument.)
Despite the restriction on the input above, you can assume all test cases will contain one or more digits ([0-9]+)
Regarding the BSN with length 8 instead of 9, the Dutch Wikipedia states the following: "For the eleven-test and for other practical uses, a leading zero is added to make the number of length 9." (source)

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, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters, full programs. Your call.
Default Loopholes are forbidden.
If possible, please add a link with a test for your code.
Also, please add an explanation if necessary.

Test cases:
// Truthy test cases:
111222333
123456782
232262536
010464554
10464554
44016773

// Falsey test cases:
000000000
192837465
247594057
88888888
73
3112223342
000000012


Shortest code in your language to persist a string across a reboot Your Programs:

You'll write two programs (both in the same language). The storage program takes a string from STDIN and stores it somewhere persistent (see below) and then exits without error. The retrieval program takes no input, retrieves the string that was stored, and prints it to STDOUT.

Objective test of Persistence:

You should be able to run the storage program on your local machine, then power-cycle your local machine, then call the retrieval program on your local machine. You can stash the string however you want (even on the web) as long as you pass this reboot test.

Test Cases:

Storage then retrieval:

echo foo | Store
Retrieve
foo

Repeated Stores should overwrite (like a set() method):

echo foo | Store
echo bar | Store
Retrieve
bar

Repeated Retrieval is non-destructive (like a get() method):

echo foo | Store
Retrieve
foo
Retrieve
foo

Retrieval before any invocation of Storage:

You don't need to worry about this. Your retrieval program can assume that the storage program has been run at some point in the past.

Input/Output flexibility.

People have asked me to expand this from strict STDIN/STDOUT to the standard IO rules. I can't because it would introduce too many loopholes. Some standard IO options already have the input stored in a persistent way, eg "programs may take input from a file". I'd like to be more flexible than just strict STDIN and STDOUT, but without opening the floodgates.

From the standard IO rules thread I'm cherry-picking the ones that don't break the challenge:

Programs may take input via GUI prompts and command-line prompts if you want
Programs may output by displaying it on screen This includes GUI dialogs
Programs may take input via command-line arguments
Programs may output to STDERR but still can't actually throw errors.

If you use an alternate it must be user-interactive. The user shouldn't have to do any other work besides piping their input to your program, typing it into a prompt your program provides, or typing input as a command-line-arg of your program. The user shouldn't have to do anything other than running your retrieve program to see the output displayed on screen or sent to STDOUT or STDERR.

Allowed assumptions:

Your two programs will be run in the same directory
Your programs have read-write permissions for that directory
Files you create will survive the reboot (not in a temp dir)
One trailing newline that wasn't part of the string is allowed. No other trailing whitespace

This is code-golf, and your score is the sum of bytes from both programs.

zsh, 4 bytes

Store: >f (reads from STDIN and writes to a file called f)
Retrieve: <f (writes the contents of f to STDOUT)


Implement an encoder for RFC 1924 IPv6 Addresses Introduction

Everyone should know IPv6 by now. IPv6 has very long, cumbersome addresses.
In 1996 some very intelligent people created a scheme to encode them much better in RFC 1924. For reasons I cannot understand, this hasn't been widely adopted. To help adoption, it is your task to implement a converter in the language of your choice.
Because storage is very expensive, especially in source code repositories, you obviously have to use as little of it as possible.

Challenge

Write an encoder for the address format specified in RFC1924. The input is a IPv6 address in the boring standard format.

Stolen from Wikipedia this is:

  An IPv6 address is represented as eight groups of four hexadecimal digits, each group representing 16 bits (two octets). The groups are separated by colons (:). An example of an IPv6 address is:

2001:0db8:85a3:0000:0000:8a2e:0370:7334

  The hexadecimal digits are case-insensitive, but IETF recommendations suggest the use of lower case letters. The full representation of eight 4-digit groups may be simplified by several techniques, eliminating parts of the representation.

  Leading zeroes

  Leading zeroes in a group may be omitted. Thus, the example address may be written as:

2001:db8:85a3:0:0:8a2e:370:7334

  Groups of zeroes

  One or more consecutive groups of zero value may be replaced with a single empty group using two consecutive colons (::). Thus, the example address can be further simplified:

2001:db8:85a3::8a2e:370:7334

  The localhost (loopback) address, 0:0:0:0:0:0:0:1, and the IPv6 unspecified address, 0:0:0:0:0:0:0:0, are reduced to ::1 and ::, respectively. This two-colon replacement may only be applied once in an address, because multiple occurrences would create an ambiguous representation.

You must handle omitted zeroes in the representation correctly!

The output is a IPv6 address in the superior RFC1924 format.

As in the RFC this is:

  The new standard way of writing IPv6 addresses is to treat them as a
     128 bit integer, encode that in base 85 notation, then encode that
     using 85 ASCII characters.
   The character set to encode the 85 base85 digits, is defined to be,
     in ascending order:

         '0'..'9', 'A'..'Z', 'a'..'z', '!', '#', '$', '%', '&', '(',
         ')', '*', '+', '-', ';', '<', '=', '>', '?', '@', '^', '_',
         '`', '{', '|', '}', and '~'.

  The conversion process is a simple one of division, taking the
     remainders at each step, and dividing the quotient again, then
     reading up the page, as is done for any other base conversion.

You can use the suggested conversion algorithm in the RFC or any other you can think of. It just has to result in the correct output!

Example Input and Output

Here is the one from the RFC:

Input:

  1080:0:0:0:8:800:200C:417A
  or
  1080::8:800:200C:417A

Output:

  4)+k&C#VzJ4br>0wv%Yp

Your program can take input and return the output in any standard way. So it is ok to read from stdin and output to stdout or you can implement your code as a function that takes the input as argument and returns the output.

Winning criteria

As always standard loopholes are disallowed

This is code-golf so shortest correct code in bytes wins!

This is my first challenge, so please do notify me about any problems/ambiguities in the description.

Pyth, 93 91 bytes

Ks[jkUTrG1G"!#$%&()*+-;<=>?@^_`{|}~")$from ipaddress import*;z=int(ip_address(z))$sm@Kdjz85

Second submission in Pyth!

Can't try online because $ is unsafe.

When tested against the example, produces the expected result:

$ pyth -c 'Ks[jkUTrG1G"!#$%&()*+-;<=>?@^_`{|}~")$from ipaddress import *$$z=int(ip_address(z))$sm@Kdjz85'
1080::8:800:200C:417A
4)+k&C#VzJ4br>0wv%Yp

Edits:

Saved two bytes by replacing $$ with ; and removing space before *

Explanation

First part creates the mapping string and assigns it to K:

0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz!#$%&()*+-;<=>?@^_`{|}~

This is done as follows:

Ks[jkUTrG1G"!#$%&()*+-;<=>?@^_`{|}~")
K                                       implicitly assign to K
 s[                                 )   the string joined from the following list
     UT                                 range [0..9]
   jk                                   joined with the empty string: 0123456789
       rG1                              capitalized version of the string G (whole alphabet)
          G                             G itself
           "!#$%&()*+-;<=>?@^_`{|}~"    all other symbols (shorter to declare than generate)

Then, the second part is two pieces of normal python amounting to 47 bytes, to convert the input ipv6 address to a number (because z is accessed later in the code, it is first implicitly assigned to any input value before running the Python code)

*from ipaddress import *$$z=int(ip_address(z))$

Then, the last part converts the resulting number to base 85 as a list and maps every value to the mapping string K:

sm@Kdjz85
     jz85  convert z to base 85
 m         map over the converted number with lambda d:
  @Kd      K[d]
s          join as a string and implicitly print

Pure Pyth, 100 bytes

Ks[jkUTrG1G"!#$%&()*+-;<=>?@^_`{|}~")IgJx=zcz\:kZ=z-z]k=z.n++<zJ]*-8lz]\0>zJ)=zimid16z65536sm@Kdjz85

You can try it here

In order to support leading/middle/trailing ::, I must insert a list of missing zeroes in the correct position in the ip once converted to a list of hex numbers, which takes up more space than the inline Python version. There's room for improvement but I doubt it can beat the other version!

63 bytes version

Doesn't support the :: notation to skip zeroes:

Ks[jkUTrG1G"!#$%&()*+-;<=>?@^_`{|}~")=zimid16cz\:65536sm@Kdjz85

You can try it here

The different part here is converting the ipv6 to a number using base conversions:

=zimid16cz\:65536
         z          read string from input and assign it to z
        c \:        split it at columns
   m                map over the split list with lambda d:
    id16            convert d from base 16 to 10
  i         65536   convert list of ints from base 65536 to 10
=z                  assign result back to z


New Order #6: Easter Egg Introduction (may be ignored)

Putting all positive integers in its regular order (1, 2, 3, ...) is a bit boring, isn't it? So here is a series of challenges around permutations (reshuffelings) of all positive integers. This is the sixth challenge in this series (links to the first, second, third, fourth and fifth challenge).

This challenge has a mild Easter theme (because it's Easter). I took my inspiration from this highly decorated (and in my personal opinion rather ugly) goose egg.

It reminded me of the Ulam spiral, where all positive integers are placed in a counter-clockwise spiral. This spiral has some interesting features related to prime numbers, but that's not relevant for this challenge.

We get to this challenge's permutation of positive integers if we take the numbers in the Ulam spiral and trace all integers in a clockwise turning spiral, starting at 1. This way, we get:

1, 6, 5, 4, 3, 2, 9, 8, 7, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 25, 24, 23, etc.

If you would draw both of the spirals, you'd get some sort of an infinite mesh of (egg shell) spirals (note the New Order reference there).

This sequence is present in the OEIS under number A090861. Since this is a "pure sequence" challenge, the task is to output \$a(n)\$ for a given \$n\$ as input, where \$a(n)\$ is A090861.

Task

Given an integer input \$n\$, output \$a(n)\$ in integer format, where \$a(n)\$ is A090861.

Note: 1-based indexing is assumed here; you may use 0-based indexing, so \$a(0) = 1; a(1) = 6\$, etc. Please mention this in your answer if you choose to use this.

Test cases

Input | Output
---------------
1     |  1
5     |  3
20    |  10
50    |  72
78    |  76
123   |  155
1234  |  1324
3000  |  2996
9999  |  9903
29890 |  29796

Rules

Input and output are integers.
Your program should at least support input in the range of 1 up to 32767).
Invalid input (0, floats, strings, negative values, etc.) may lead to unpredicted output, errors or (un)defined behaviour.
Default I/O rules apply.
Default loopholes are forbidden.
This is code-golf, so the shortest answers in bytes wins

Jelly,  16 14 11 10 9  8 bytes

-1 thanks to Lynn (mod-2; logical NOT; add to self: Ḃ¬+ -> bitwise OR with 1:|1)

|1×r)ẎQi

A monadic Link accepting an integer, n, which yields an integer, a(n).

Try it online! (very inefficient since it goes out to layer \$\lceil\frac n2\rceil\$)

An 11-byte version, ½‘|1×rƲ€ẎQi, completes all but the largest test case in under 30s - Try it at TIO - this limits the layers used to \$\lceil\frac{\lfloor\sqrt n\rfloor+1}2\rceil\$.

How?

The permutation is to take the natural numbers in reversed slices of lengths [1,5,3,11,5,17,7,23,9,29,11,35,13,...] - the odd positive integers interspersed with the positive integers congruent to five modulo six, i.e [1, 2*3-1, 3, 4*3-1, 5, 6*3-1, 7, 8*3-1, 9, ...].

This is the same as concatenating and then deduplicating reversed ranges [1..x] of where x is the cumulative sums of these slice lengths (i.e. the maximum of each slice) - [1,6,9,20,25,42,49,72,81,110,121,156,169,...], which is the odd integers squared interspersed with even numbers multiplied by themselves incremented, i.e. [1*1, 2*3, 3*3, 4*5, 5*5, 6*7, 7*7,...].

Since the differences are all greater than 1 we can save a byte (the reversal) by building ranges [x..k] directly, where k is the 1-indexed index of the slice.

Due to this structure the permutation is a self-conjugate permutation, i.e. we know that \$P(n) = v \iff P(v) = n\$, so rather than finding the value at (1-indexed) index n (|1×r)ẎQị@) we can actually get the (1-indexed) index of the first occurrence of n (|1×r)ẎQi).

|1×r)ẎQi - Link: integer, n       e.g. 10
    )    - for each k in [1..n]:  vs = [ 1, 2, 3, 4, 5, 6, 7, 8, 9,10]
|1       -   bitwise-OR (k) with 1     [ 1, 3, 3, 5, 5, 7, 7, 9, 9,11]
  ×      -   multiply (by k)           [ 1, 6, 9,20,25,42,49,72,81,110]
   r     -   inclusive range (to k)    [[1],[6..2],[9..3],[20..4],...,[110..10]]
     Ẏ   - tighten                     [1,6,5,4,3,2,9,8,7,6,5,4,3,20,...,4,......,110,...,10]
      Q  - de-duplicate                [1,6,5,4,3,2,9,8,7,20,...,10,......,110,...82]
       i - first index with value (n)  20


The Practice of Programming At 1998, Brian Kernighan, while working on the book "The Practice of Programming", wanted to demonstrate realisation of regular expression engine. But struggled to find small engine, that cod could fit in the book.

So Brian Kernighan asked Rob Pike to write one for him, and Rob did it gracefully. Here is original source:

    /* match: search for regexp anywhere in text */
    int match(char *regexp, char *text)
    {
        if (regexp[0] == '^')
            return matchhere(regexp+1, text);
        do {    /* must look even if string is empty */
            if (matchhere(regexp, text))
                return 1;
        } while (*text++ != '\0');
        return 0;
    }

    /* matchhere: search for regexp at beginning of text */
    int matchhere(char *regexp, char *text)
    {
        if (regexp[0] == '\0')
            return 1;
        if (regexp[1] == '*')
            return matchstar(regexp[0], regexp+2, text);
        if (regexp[0] == '$' && regexp[1] == '\0')
            return *text == '\0';
        if (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text))
            return matchhere(regexp+1, text+1);
        return 0;
    }

    /* matchstar: search for c*regexp at beginning of text */
    int matchstar(int c, char *regexp, char *text)
    {
        do {    /* a * matches zero or more instances */
            if (matchhere(regexp, text))
                return 1;
        } while (*text != '\0' && (*text++ == c || c == '.'));
        return 0;
    }

Rules

Write regex engine that supports the same operations, as Rob's:

Any char (as symbol)
. to match any char
^ to match start of the string
$ to match end of the string
* to match any count of char from zero

Auxiliary code do not count (to accept input, for example)
Make the shortest solution and beat Rob Pike!

Input

Two strings: one for regex, one for match.

Output

True (in your language), if regex matches string
False (in your language), if regex do not match string

Perl 6, 39 bytes

->\a{&{?/<{a}>/}}o{S:g/<-[.*$^]>/'$/'/}

Try it online!

Simply evaluates the input as a regex, adding quotes to avoid any special characters Perl 6 uses. This takes input curried, as f(regex)(string), though it could be a lot shorter if I can just return a regex object.


Implement a zipwith function zipwith is a functional construct that takes three arguments: one binary function and two lists of the same length, and returns a single list where each element is constructed by applying the binary function to each pair of elements from the two lists:
zipwith (a+b) [1,2,3] [4,5,6] = [5,7,9]

You are to take a black-box function which takes exactly two arguments and two non-empty arrays of the same length consisting of positive integers, and output the result of applying zipwith to this function and arrays.
For the sake of simplicity, you can assume that the black-box function will always input and output integers within your language's integer domain.
If your answer consists solely of a builtin which does this (for example Haskell's zipWith), please edit into this Community Wiki answer. You may input and output in any convenient method.
This is code-golf so the shortest code in bytes wins
Test Cases
function, array, array -> output
a = b, [1, 2, 3], [3, 2, 1] -> [0, 1, 0]
a - b, [8, 3], [3, 8] -> [5, -5]
a² + b/2, [6, 8, 1, 3], [5, 3, 6, 2] -> [38, 65, 4, 10]
a × φ(b), [4, 2, 5, 8, 3], [7, 6, 10, 2, 1] -> [24, 4, 20, 8, 3]

The third test case uses integer (floor) division. The fourth uses the Euler Totient function

Haskell, 22 bytes

(.zip).(.).map.uncurry

Try it online!
Not particularly interesting, just a reimplementation of zipWith converted to pointfree form:
\f x y -> map (uncurry f) (zip x y)
\f x -> map (uncurry f) . zip x
\f x -> (map (uncurry f) .) zip x
\f -> (map (uncurry f) .) . zip
\f -> (. zip) (map (uncurry f) .)
\f -> (. zip) ((.) (map (uncurry f)))
\f -> (. zip) ((.) ((map . uncurry) f))
\f -> (. zip) ((.) . (map . uncurry) $ f)
\f -> (. zip) . ((.) . (map . uncurry)) $ f
(. zip) . ((.) . (map . uncurry))


Maximum run between identical elements This is a overhaul of this now deleted question by ar kang. If the OP of that question would like to reclaim this question or has a problem with me posting this I'd be happy to accommodate

Given a list of integers as input find the maximum possible sum of a continuous sublist that starts and ends with the same value.  The sublists must be of length at least 2.  For example for the list

[1, 2, -2, 4, 1, 4]

There are 2 different continuous sublists start and end with the same value

[1,2,-2,4,1] -> 6
[4,1,4]      -> 9

The bigger sum is 9 so you output 9.

You may assume every input contains at least 1 duplicate.

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

Test cases

[1,2,-2,4,1,4]  -> 9
[1,2,1,2]       -> 5
[-1,-2,-1,-2]   -> -4
[1,1,1,8,-1,8]  -> 15
[1,1,1,-1,6,-1] -> 4
[2,8,2,-3,2]    -> 12
[1,1,80]        -> 2
[2,8,2,3,2]     -> 17

Haskell, 62 bytes

f takes a list of integers and returns an integer.

f l=maximum[x+sum m-sum n|x:m<-t l,y:n<-t m,x==y]
t=scanr(:)[]

Try it online!

How it works

t is the standard "get all suffixes of a list without importing Data.List.tails" function.
In f l, the list comprehension iterates through all the non-empty suffixes of the argument list l, with first element x and remainder m.
For each, it does the same for all nonempty suffixes of m, selecting first element y and remainder n.
If x and y are equal, the list comprehension includes the sum of the elements between them. This sublist is the same as x:m with its suffix n stripped off, so the sum can be calculated as x+sum m-sum n.


exponential without exponential Your goal is to calculate the exponential of a float (e**x) up to 2 decimal places for any float within 1 to 10. The accepted error range is 0.01.

However, you must not use the built-in exponential function or the logarithm function.

In fact, attempts to circumvent this by (2**x)**(1/ln(2)) are prohibited, even if you hardcode the ln(2).

Basically, the power function is fine, as long as the index is not derived from the input.

Shortest solution in bytes wins.

(You may include an extra solution which uses the built-in, but which does not affect the score in any way.)

Specs

Program or function
Any reasonable input/output format

Testcases

1 -> 2.71 or 2.72 or 2.73


Simple Geometric problem This problem (see below) has been given as a High School Programming League code golf challenge. The shortest codes submitted during the contest were: 177 bytes in Ruby, 212 bytes in Python 2.5, 265 bytes in C. Can anyone make it shorter? Other programming languages are also allowed.

Problem formulation: Given 8 integers: -1000 < x1, y1, x2, y2, x3, y3, x4, y4 < 1000. Check what is the shape of the intersection of two axis-aligned rectangles: P1 = (x1, y1), (x1, y2), (x2, y2), (x2, y1) and P2 = (x3, y3), (x3, y4), (x4, y4), (x4, y3).

* If the rectangles do not intersect print *nothing*.
* If there is exactly one point in common print *point*.
* If the intersections of P1 and P2 is a line segment print *line*.
* If they have a rectangular area in common print *rectangle*.

Input data specification: The first line contains the number of test cases t (1<=t<1000). Each of the following t lines contains 8 integers: x1, y1, x2, y2, x3, y3, x4, y4 (The area of both rectangles is greater than 0).

You can test your solution here.

Python, 200 characters

f=lambda a,b,c,d:min(2,sum((x-c)*(x-d)<=0for x in range(min(a,b),max(a,b)+1)))
for i in' '*input():z=map(int,raw_input().split());print('nothing','point','line',0,'rectangle')[f(*z[::2])*f(*z[1::2])]

f returns:

0 if the intervals [a,b] and [c,d] don't overlap
1 if the intervals [a,b] and [c,d] overlap in only one point
2 if the intervals [a,b] and [c,d] overlap in a range of points


Confused badminton players Introduction

Jim and Bob are playing badminton doubles against two other players, but mid-game they face a dilemma:
After a fast-paced rally they have no idea who has to serve next and where they have to stand for the next serve.
Bad enough they only know the scores in order.

Rules:

To help them out, you have to know the rules:

If the serving team has an even score, serving is done by the player on the right side (relatively facing towards the net)
If the serving team has an odd score, serving is done by the left player.
If the serving team changes, the players' position remains.
If one team keeps the right to serve the ball, the two players of that team swap places, so the same player serves again.
The team, that scored last, serves next.

This is where you come to help them out.

Your task:

Your task is to take the scores in order and return the position for all four players according to the rules as well as the player, who has to serve next.

Specification:

Input:

Input is a string / array / set / whatever you like containing all scores in the order they are scored.
Example: "0:0, 0:1, 0:2, 1:2, 1:3" or ["0:0", "0:1", "0:2", "1:2", "1:3"]
You may assume team 1 (the left part of the score) served first in the beginning.

The input is not secured to be valid!

Output:

Your program / function / script has to output an ASCII-art style badminton court (don't care about orientation) with the position of the players and some representation of the player serving next (a single line saying Next to serve is >Player1< is enough).

Example output of the example given above ("0:0, 0:1, 0:2, 1:2, 1:3"):

|-----|-----|
|-Jim-|-Bob-| //Team 1
|###########|
|-P4--|-P3--| //Team 2
|-----|-----|
Player P4 of team 2 serves next.

The players are named Jim, Bob, P3 and P4. P3 and P4 swap their places after scoring "0:2" and keeping the right to serve. Jim and Bob never scored two times in a row and thus never swap places.

Last notes about input and output:

Input is assumed to be always in order with the first (left) score to be team 1, which may be assumed to have served first.
The names of the players are irrelevant as long as it is documented which player belongs to which team.
Team 1 is always the upper/left team in your output.
Even though a usual badminton round ends when one team scores 21 (without overtime), you may assume the game to be as long as the two teams want to play.
Sometimes the input may be incomplete (missing a score). Then your program has to output an error message indicating invalid input (E for Error! is enough for golfing reasons).

Scoring:

This is code-golf, so the least amount of bytes wins.
There are bonuses to claim though:

-20% if you output the court and server for every single serve.
-10% if your program allows to choose the serving team.
-15% if the user can choose the names for the players.

The bonus percentages are first added and then applied to the byte count, resulting in a maximum bonus of 45%!

Test cases (so you don't have to come up with your own):

(Strings only, including output and validation):
Example1:

0:0, 1:0, 2:0, 3:0, 3:1, 3:2, 4:2, 4:3, 5:3, 6:3, 6:4, 7:4, 7:5, 7:6, 8:6, 8:7, 9:7, 10:7, 11:7, 12:7, 12:8, 12:9, 13:9

Output:

|-----|-----|
|-Bob-|-Jim-| //Team 1
|###########|
|-P4--|-P3--| //Team 2
|-----|-----|
Player Jim of team 1 serves next.

Example2:

0:0, 0:1, 0:2, 1:2, 2:2, 3:3, 4:3, 4:4 -> Invalid
                          /\              Both teams can't score at the same time/missing intermediate score

Output:

Invalid input! Please check input and try again.

In case you have questions or need clarification, please ask so I can improve the challenge.


Priming a Pristine World Heavily inspired by Programming a Pristine World. Also closely related to this challenge.

Let's define a pristine prime as a number which is itself prime, but will no longer be prime if you remove any contiguous substring of N base 10 digits, where 0 < N < digits in number.

For example, 409 is a pristine prime because 409 itself is prime, but all numbers resulting from removing a substring of 1 digit are not prime:

40
49
09 = 9

and all numbers resulting from removing substrings of length 2 are not prime:

4
9

On the other hand, the prime number 439 is not pristine. Removing the different substrings results in:

43
49
39
4
9

While 49, 39, 4, and 9 are all non-prime, 43 is prime; thus, 439 is not pristine.

2, 3, 5, and 7 are trivially pristine, since they cannot have any substrings removed.

Challenge

Your challenge is to create a program or function that takes in a positive integer N and outputs the Nth pristine prime. The code should finish in under 1 minute on any modern PC for any input up to 50.

The shortest code in bytes wins.

As a reference, here are the first 20 pristine primes:

N    Pristine prime
1    2
2    3
3    5
4    7
5    11
6    19
7    41
8    61
9    89
10   409
11   449
12   499
13   821
14   881
15   991
16   6299
17   6469
18   6869
19   6899
20   6949

Here is a full list of pristine primes up to 1e7, or N = 376.

Finally, here are two related OEIS entries:

A033274: very similar, but generated by keeping substrings instead of removing them.
A071062: oddly similar, but generated in a much different manner.

Pyth, 29 bytes

e.f>}ZPZsmq1lPs.D`Z}Fd.CU`Z2Q

Golfing, explanation, etc. to follow.


Digit Product Sequences Here's an interesting sequence discovered by Paul Loomis, a mathematician at Bloomsburg University. From his page on this sequence:

Define
f(n) = f(n-1) + (the product of the nonzero digits of f(n-1))
f(0) = x, with x as any positive integer, written in base 10.

So, starting with f(0)=1, you get the following sequence
1, 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, ...

So far, so standard. The interesting property comes into play when you take any other integer as the starting point, eventually the sequence converges into a point along the above x=1 sequence. For example, starting with x=3 yields
3, 6, 12, 14, 18, 26, 38, 62, 74, 102, ...

Here are some more sequences, each shown only until they reach 102:

5, 10, 11, 12, 14, 18, 26, 38, 62, 74, 102, ...
7, 14, 18, 26, 38, 62, 74, 102, ...
9, 18, 26, 38, 62, 74, 102, ...
13, 16, 22, 26, 38, 62, 74, 102, ...
15, 20, 22, 26, 38, 62, 74, 102, ...
17, 24, 32, 38, 62, 74, 102, ...
19, 28, 44, 60, 66, 102, ...

He conjectured, and empirically proved up to x=1,000,000, that this property (i.e., that all input numbers converge to the same sequence) holds true.

The Challenge

Given a positive input integer 0 < x < 1,000,000, output the number where the f(x) sequence converges to the f(1) sequence. For example, for x=5, this would be 26, since that's the first number in common to both sequences.

 x output
 1 1
 5 26
19 102
63 150056

Rules

If applicable, you can assume that the input/output will fit in your language's native Integer type.
The input and output can be given by any convenient method.
Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
Standard loopholes are forbidden.
This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

JavaScript (ES6), 81 67 bytes
Saved 1 byte thanks to @l4m2

f=(n,x=1)=>x<n?f(x,n):x>n?f(+[...n+''].reduce((p,i)=>p*i||p)+n,x):n

Try it online!
Commented
f = (n,                   // n = current value for the 1st sequence, initialized to input
        x = 1) =>         // x = current value for the 2nd sequence, initialized to 1
  x < n ?                 // if x is less than n:
    f(x, n)               //   swap the sequences by doing a recursive call to f(x, n)
  :                       // else:
    x > n ?               //   if x is greater than n:
      f(                  //     do a recursive call with the next term of the 1st sequence:
        +[...n + '']      //       coerce n to a string and split it
        .reduce((p, i) => //       for each digit i in n:
          p * i || p      //         multiply p by i, or let p unchanged if i is zero
        ) + n,            //       end of reduce(); add n to the result
        x                 //       let x unchanged
      )                   //     end of recursive call
    :                     //   else:
      n                   //     return n


Loop Detection - not that kind! The goal of this challenge is to find the direction and area enclosed by a loop.
Input:
A rectangular grid consisting entirely of these characters: ^v<>
(Optionally, you may also be given the dimensions of the grid before the grid itself in decimal with a prefix, suffix, and separator character of your choice.)
A loop in the grid is a set of the aforementioned characters such that one points to the next, pointing to the next, eventually pointing back at the first character. For example:
<>>v>     >>v
^^<>v     ^ >v
>^<<<     ^<<<
>^<v>

The left grid is the sample input; the right grid is the loop isolated.
The input grid will contain either no loops at all or one loop; you do not have to worry about any cases in which the grid contains more than one loop.
Output:
If the grid contains no loop, output X.
If the grid contains two arrows pointing at each other, output 0.
If the grid contains a counterclockwise loop, count the characters enclosed by the loop, including the border. Output that number.
If the grid contains a clockwise loop, follow the same process for the counterclockwise loop, but output the negative of that number. For instance, the above input grid would have an output of -11: 10 come from the loop itself, and 1 from the character enclosed by the loop.
This is code-golf. Shortest code wins.
Test cases:
<<^
^>v
^v<

Output X.
<<<<
><<<
>>^>

Output 0.
<>^^<
>>>v>
<^^>v
<^>>v
>^<<<

Output -15.
v<<<<
>v>>^
v<^<<
>>>>^

Output 20.

C#, 604 bytes

Complete program, accepts input (line-delimitated layout, no dimensions) from STDIN, outputs to STDOUT.

using C=System.Console;class P{static void Main(){int w=0,W,i,j,t,k,l,c;string D="",L;for(;(L=C.ReadLine())!=null;D+=L)w=L.Length;var R=new[]{-1,0,1,w,-w};L="X";for(W=i=D.Length;i-->0;){var M=new int[W];for(k=j=i;i>0;){M[j]=++k;t=j+R[c=D[j]%5];if(t<0|t>=W|c<3&t/w!=j/w|c>2&t%w!=j%w)break;j=t;if((l=M[j])>0){var J=new int[W+1];System.Func<int,int>B=null,A=s=>J[s]<0?0:J[k=B(s)]=k==W?k:i;B=x=>J[x]==x?x:B(J[x]);for(i=J[W]=W;i>0;)J[--i]=M[i]<l?i%w<1|i%w>w-2|i<w|i>W-w?W:i:-1;for(;i<W;)if(J[++i]<0)l=D[i]%5/2-1;else{A(i-1);if(i>w)A(i-w);}for(c=W;i-->0;L=""+(c>2?c:0)*l)c-=J[i]<0?0:B(i)/W;}}}C.WriteLine(L);}}

The program works by first reading in the layout, needless to say, and then iterating over every cell. We then run a 'snake' from each cell, which follows the arrows until it runs off the edge, or runs into itself. If it runs into itself, then we know we have found a loop (or one of those "><" things), and it also knows how much of the snake is in the loop.

Once we know we have a loop, we know which cells are on the loop, and we create a map from each cell (+1, for reasons) to either itself, -1 (means it's on the loop), or W (the whole width) if it's on the edge (or the +1 (which is at index W) to simplify things further one).

While we do this, we also find the direction that the 'last' element of the loop has (that is, the last element of the loop on the last row that has elements from the loop on it). This element must be a "<" or an "^", and this tells us the clockness (CW/CCW) of the loop (translated to -1/+1).

We then perform a disjoin set pass, which assigns all the elements that are outside the loop to the W set. We then subtract how many of these there are from W to get the number contained on and in the loop. If this number is less than 3, we replace it with 0. We multiply this by the clockness, set it as the result, and somehow escape from the for loops, where the result is output.

If, however, most of the above never happens (because no snake ever finds itself), then the result remains as "X", and that is outputted.

using C=System.Console;

class P
{
    static void Main()
    {
        int w=0, // width
        W, // full length
        i, // used for iterating over all the cells
        j, // keeps track of where the snake as got to
        t, // t is next j
        k, // how far along the snake we are, kind of
        // later on, k is used as temp for A
        l, // stores a threshold for how far along the snake the loop starts
        // later on, l stores the last seen pointer - this tells us the clockness
        c; // the translated direction
        // later on, c is a backwards-count

        string D="", // D is the map
        L; // used for reading lines, and then storing the result

        // might not be the best yay of doing this
        for(;(L=C.ReadLine())!=null; // read a line, while we can
            D+=L) // add the line to the map
            w=L.Length; // record the width

        var R=new[]{-1,0,1,w,-w}; // direction table (char%5) - might be able to replace this array with some bit bashing/ternary

        L="X"; // can't seem to fit this in anywhere... (don't strictly need to re-use L)
        for(W=i=D.Length;i-->0;) // for each cell, we send a 'snake' to try to find the loop from that cell
        {
            var M=new int[W]; // stores how far along the snake this point is

            for(k=j=i; // k's value doesn't really matter, as long as it's not stupidly big
                i>0;) // the i>0 check is just for when we return (see comment at the end of the code)
            {
                M[j]=++k; // store snake point and advance distance

                t=j+R[c=D[j]%5]; // t is position after move (translate <>v^ to 0234 (c is direction))
                //c=D[j]%5; // translate <>v^ to 0234 (c is direction)
                //t=j+R[c]; // t is position after move
                if(t<0|t>=W|c<3&t/w!=j/w|c>2&t%w!=j%w)
                    break; // hit an edge - will always happen if we don't find a loop - give up on this snake
                j=t; // move to new position

                if((l=M[j])>0) // we've been here before...
                {
                    // disjoint sets (assign all the edges to one set, assign all the ones on the line to another set, do adjacent disjoint, return size-outteredge (minus if necessary)
                    var J=new int[W+1]; // looks like we can reuse M for this

                    System.Func<int,int>B=null,
                    // whatever s points at should point to i, unless s points to W, in which case it should keep point to W
                    A=s=>J[s]<0?0:J[k=B(s)]=k==W?k:i;
                    // read the value this points to
                    B=x=>J[x]==x?x:B(J[x]);

                    for(i=J[W]=W;i>0;)
                        J[--i]=M[i]<l? // if we are not part of the loop
                            i%w<1|i%w>w-2|i<w|i>W-w? // if we are on the edge
                                W: // on the edge
                                i: // not on the edge
                             -1; // this is on the loop

                    // now fill in
                    // we don't have to worry about wrapping, the important bit being an un-wrapping closed loop
                    // i = 0
                    for(;i<W;)
                        if(J[++i]<0) // we are on the loop
                            l=D[i]%5/2-1; // last one must be ^(4) or <(0)
                        else{ // can probably crush this into an l returning l assigning term (with if above)
                            A(i-1);
                            if(i>w)
                                A(i-w);
                        }

                    // now count the number of non-edges
                    for(c=W; // assume everything is a non-edge
                        i-->0;
                        L=""+(c>2?c:0)*l) // set output to be number of non-edges * clockness (or 0 if too few)
                        c-=J[i]<0?0:B(i)/W; // subtract 1 if an edge (B(i) is W), othewise 0

                    // at this point, i is 0, so we will fall out of all the loops
                }
            }
        }

        C.WriteLine(L); // output result
    }
}


Traceless Busy Beaver All those busy beavers made quite a mess. They wrote all over the tape. At this rate, our neighbour will stop lending us unbounded tapes.

We need a new way to play the busy beaver game, one that doesn't ruin every tape we use.

The Rules

Brainfuck only. Memory tape is unbounded both ways. Input instruction will always read \$0\$, so it can be used to clear a value.

50 bytes source limit.

At the end of execution, memory must be all \$0\$s.

Score is distance between the memory pointer's starting location and final location - if it takes \$n\$ move instructions to go between them, your score is \$n\$. Higher is better. Provide an exact value if you can, otherwise provide an estimate.

Example

32 bytes, \$2^{255}-1\$

-[-[[>]+>+[<]>-[[>]<+<+[<]>-]]>]

Explanation

-                                Initialize the list to [255].
 [                             ] Repeat as long as the list is not empty.
 [-                            ] Decrement the left end. We need to shrink the numbers so it ends eventually.
 [ [                         ] ] Skip if 0 already.
 [ [[>]                      ] ] Move to the cell past the right end.
 [ [   +                     ] ] Make this cell 1.
 [ [    >                    ] ] Go right again.
 [ [     +                   ] ] Make this cell 1. We've now appended [1, 1].
 [ [      [<]>               ] ] Go back to the first nonzero cell on the left.
 [ [          -              ] ] And decrement it.
 [ [           [            ]] ] We will need to transfer the rest of the number from the left to the right, so keep looping.
 [ [           [[>]<        ]] ] Go to the last nonzero cell on the right.
 [ [           [    +<+     ]] ] Increment this and the one on the left. These are the cells we appended earlier. We transfer to them.
 [ [           [       [<]> ]] ] Go back to the first nonzero cell on the left, which we are transferring from.
 [ [           [           -]] ] Decrement here on the left to balance out the incrementing on the right.
 [                            >] We end the iteration on a now empty cell. Move right, the new left end is there.

We begin with the list \$[255]\$. At each iteration, we consume the value \$n\$ on the left of the list, and if \$n>1\$, we append \$[n-1, n-1]\$ to the right. The numbers appended \$(n-1)\$ are lower than the original \$(n)\$, so they will get smaller until they are \$1\$, at which point they are consumed without expanding. Thus, the process ends eventually, with all \$0\$s in memory. However, at each step, the number of copies of the number doubles. The score of this program initialized with the list \$[n]\$ is \$2^n-1\$.

This example is meant to show some of the techniques used in creating a submission. It's not competitive for its size.

Score: \$ A(255, 2) - 1 = (2 \uparrow^{253} 5) - 4 \$

+<+<<++>-[-[<+>>[-<[->+<]+>>]+<-]>[>]+[<]+<]>[->]

\$ A \$ here is the Péter-Ackermann formulation of the Ackermann function, while the other score expression uses Knuth up-arrow notation. The 35-byte main loop [-[<+>>[-<[->+<]+>>]+<-]>[>]+[<]+<] can be used to compute \$ A(m,n) \$ by placing on the tape the values 1 - m, m, 1 <n times> and entering the loop with the pointer on the m cell. After the loop terminates, the nonzero tape contents are \$ A(m,n) \$ ones starting immediately to the right of the pointer.

I used the following Python program for modeling the behavior of the program:

def a(M, N):
    assert M > 0
    m = [-M + 1, M]
    n = N
    while m[-1]:
        while m[-1] > 1:
            m[-1] -= 1
            m[-2] += 1
            while n:
                m.insert(-1, 1)
                n -= 1
            n = 1
        n += 2
        m.pop()
    return n