Count the number of triangles Given a list of positive integers, find the number of triangles we can form such that their side lengths are represented by three distinct entries of the input list.
(Inspiration comes from CR.)
Details

A triangle can be formed if all permutations of the three side lengths \$a,b,c\$ satisfy the strict triangle inequality $$a + b > c.$$ (This means \$a+b > c\$, \$a+c>b\$ and \$b+c>a\$ must all hold.)
The three side lengths \$a,b,c\$ must appear at distinct positions in the list, but do not necessarily have to be pairwise distinct.
The order of the three numbers in the input list does not matter. If we consider a list a and the three numbers a[i], a[j], a[k] (where i,j,k are pairwise different), then (a[i],a[j],a[k]), (a[i],a[k],a[j]), (a[j], a[i], a[k]) etc. all are considered as the same triangle.
The input list can assumed to contain at least 3 entries.
You can assume that the input list is sorted in ascending order.

Examples
A small test program can be found here on Try it online!
Input, Output:
[1,2,3]  0
[1,1,1]  1
[1,1,1,1] 4
[1,2,3,4] 1
[3,4,5,7] 3
[1,42,69,666,1000000] 0
[12,23,34,45,56,67,78,89] 34
[1,2,3,4,5,6,7,8,9,10] 50

For the input of [1,2,3,...,n-1,n] this is A002623.
For the input of [1,1,...,1] (length n) this is A000292.
For the input of the first n Fibonacci numbers (A000045) this is A000004.

R, 62 52 40 34 bytes

sum(c(1,1,-1)%*%combn(scan(),3)>0)

Try it online!

Port of Luis Mendo's Octave solution

Since a<=b<=c, the triangle condition is equivalent to a+b-c>0. The a+b-c is succinctly captured by the matrix product [1,1,-1] * X, where X is the 3-combinations of the input array.

There were a lot of suggestions for improvements made by 3 different people in the comments:

Robert S. for suggesting scan.
Robin Ryder for suggesting improvements to the triangle inequality and this odd one which requires the input to be in descending order (which just goes to show how important a flexible input format is).
and finally Nick Kennedy for the following:

R, 40 bytes

y=combn(scan(),3);sum(y[3,]<y[1,]+y[2,])

Try it online!


Wind me a number snake! Given an input integer n, draw a number snake, that is, a grid measuring n x n consisting of the numbers 1 through n^2 that are wound around each other in the following fashion:

Input n = 3:

7 8 9
6 1 2
5 4 3

Input n = 4:

 7  8  9 10
 6  1  2 11
 5  4  3 12
16 15 14 13

Input n = 5:

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

(Inspired by this problem from Project Euler.)

This is code-golf, the shortest answer in bytes wins!

MATL, 3 bytes

1YL

Try it online!

Explanation

Built-in... ¯\_(ツ)_/¯


Generate code in another language Write a program in language A which outputs a program in language B where:

  Language A != Language B
  The output is itself a solution to this question.

This is a popularity contest. If you want to define your own BNFs/grammars for this, feel free, but try not to make it too boring by doing so.

EDIT: The more languages it ends up generating code in, the better (in my opinion).

EDIT2: Try to use languages that are not similar (I.e. generate the code in a different family of languages). (E.g. C to Scheme)

php --> asp --> html --> xhtml .......
 Hello

Infinite languages


String to Bit Transition Task
Given an input string of one or more ASCII characters which codepoints are between 0 and 128 (exclusive), do the following:

Convert each character into its 7-bit ASCII code (if the ASCII code is less than 7 bits, put leading zero bits)
Concatenate all bits (this results in 7*n bits where n is the number of characters)
For each bit in this bitstream, print 1 if it is different from the previous bit, and print 0 otherwise. The first output bit is always 1.

Example
Input:
Hi

Output:
11011001011101

Explanation:

The string "Hi" has the ASCII codes
72 105
which in bits are:
1001000 1101001
And the transition bits indicators:
11011001011101

This is code golf. Lowest byte count wins.
Test Cases
Test case 1:
Hello World!
110110010101110011010101101010110001110000111110000110000001011101101010101100110001

Test case 2:
%% COMMENT %%
1110111111011111100001100010010100001010110101011010011101010011111110011000001101111110111

Test case 3 (credit to Luis Mendo):
##
11100101110010

Congrats to Luis Mendo for the shortest solution with 9 bytes in MATL!

Python 2, 58 bytes

n=1
for c in input():n=n<<7|ord(c)
print'1'+bin(n^n/2)[4:]

Try it online!


When's the nearest special common year? A common year is a year that is not a leap year and where the first and last day of the year are on the same day. A special common year is one that starts on a Monday and so ends on a Monday as well.

Your challenge is to create a program/function that when given a year as input finds the nearest special common year, outputting itself if it is a common year. If the year is as close to the one before it as the one next to it output the larger one.

Input

An integer representing the year to test against in the range 1600 <= x <= 2100.

Output

An integer representing the nearest special common year.

Test cases

2017 -> 2018
2018 -> 2018
1992 -> 1990
1600 -> 1601
2100 -> 2103
1728 -> 1731 (lies between 1725 and 1731)

Notes

All 54 years in the given range are already shown in the linked Wikipedia article. I will also provide them here for reference:

1601, 1607, 1618, 1629, 1635, 1646, 1657, 1663, 1674, 1685, 1691
1703, 1714, 1725, 1731, 1742, 1753, 1759, 1770, 1781, 1787, 1798
1810, 1821, 1827, 1838, 1849, 1855, 1866, 1877, 1883, 1894, 1900
1906, 1917, 1923, 1934, 1945, 1951, 1962, 1973, 1979, 1990
2001, 2007, 2018, 2029, 2035, 2046, 2057, 2063, 2074, 2085, 2091
2103 (Needed for 2097 to 2100)

PHP, 67 Bytes

for(;date(LN,mktime(0,0,0,1,1,$y=$argn+$i))>1;)$i=($i<1)-$i;echo$y;

Try it online!

or

for(;date(LN,strtotime("1/1/".$y=$argn+$i))>1;)$i=($i<1)-$i;echo$y;

Try it online!

Expanded

for(;
date(LN,mktime(0,0,0,1,1,$y=$argn+$i)) # N is 1 for Monday and L is 0 for Non leap year
>1;) # loop so long as expression is not 1
  $i=($i<1)-$i; # set $i 0,1,-1,2,-2 ...
echo$y; # Output Year

date


Output the Goodstein sequence (This might be quite classic but this is my first post here, so I'm not ready for the fancy stuff yet)

The Goodstein sequence is defined for an input number as follows:

Pick a starting number n, let b=2 and repeat:

write n in heriditary base b notation
substitute all the (b)s to (b+1)s in n and substract 1
output the new decimal evaluation of n
increment b

Hereditary Base notation is a decomposition of a number where the basis is the bigger number to appear. Examples:

83 in HB3: 3^(3+1)+2
226 in HB2: 2^(2^(2+1))+2^(2+1)+2

Goodstein sequences always end up at 0, but they tend to first get quite big quite fast so it is not asked to output the complete sequence.

Task:

Given an input number in any reasonable format, your job is to output the Goodstein sequence for this number at least until it reaches 10^25 or 0

Examples:

Input: 3
Output: 3, 3, 3, 2, 1, 0
Input: 13
Output: 13, 108, 1279, 16092, 280711, 5765998, 134219479, 3486786855, 100000003325, 3138428381103, 106993205384715, 3937376385706415, 155568095557821073, 6568408355712901455, 295147905179352838943, 14063084452067725006646, 708235345355337676376131, 37589973457545958193377292
Input: 38
Output: 38, 22876792454990

Details:

Input number can be an array, a string, an integer, as long as it is in decimal base
Output follows the same rule
Separation of the terms in the output can be spaces, new-lines, or any reasonable separation
As soon as the sequence becomes larger than 10^25, your program may exit normally, throw an error/exception, or continue (no restriction)
This is code-golf, so the shortest answer (in bytes) wins
Of course, standard loopholes are forbidden
Python ungolfed working example here

Haskell, 77 bytes

(&2) is an anonymous function taking an Integer and returning a (potentially very long) list of Integers, use as (&2) 13.

(&2)
n&b|n<0=[]|let _?0=0;e?n=(e+1)?div n b+mod n b*(b+1)^0?e=n:(0?n-1)&(b+1)

Try it online! (cuts off at 10^25.)

How it works

(&2) starts the sequence with base 2.
n&b calculates the subsequence starting with the number n and base b.

It halts with an empty list if n<0, which generally happens the step after n==0.
Otherwise, it prepends n to the list returned recursively by the expression (0?n-1)&(b+1).

? is a local function operator. 0?n gives the result of converting n to hereditary base b, then incrementing the base everywhere.

The conversion recurses with the variable e keeping track of the current exponent. e?n converts the number n*b^e.
The recursion halts with 0 when n==0.
Otherwise, it divides n by the base b.

(e+1)?div n b handles the recursion for the quotient and next higher exponent.
mod n b*(b+1)^0?e handles the remainder (which is the digit corresponding to the current exponent e), the increment of base, and converting the current exponent hereditarily with 0?e.


Computer Generated Cracked Soil Write a program that takes in an integer from 0 to 65535 (216-1) and generates a unique 500×500 pixel image that looks as similar as possible to these 6 real life images of cracked soil:

These are thumbnails, click them to see the full-size 500×500 images.
The goal here is to make your computer generated images as photorealistic as possible. So ideally, if any of the images output by your program were mixed in with the 6 images above, someone seeing the images for the first time would not be able to tell the computer generated ones apart from the real ones.
Perfect photorealism is tricky however, so just do the best you can. This is a popularity-contest so the answers that have more realistic outputs will be upvoted more and be more likely to win.
Rules

You may use image processing functions or libraries.

You may base your algorithm on information gathered from the 6 sample images, but your 65536 (216) possible output images should be visually distinct from each other and the sample images, especially with regard to the arrangement of the cracks. You must truly generate your images, don't just rotate and translate a selection from a preexisting photo.

You should not otherwise hardcode your outputs. A generic algorithm should be used and numbers larger than 65535 should theoretically produce valid outputs. (I've restricted it merely to accommodate small-maximum integer types.)

The input integer can be thought of as a seed that results in a random cracked soil output image. It should be deterministic though, so the same input should always result in the same output.

The output images must be exactly 500×500 pixels.

The output images may be saved in any common image file format, or simply displayed.

Be sure to include a few example output images in your answer, and their corresponding input numbers.

The answer with the most votes wins. Voters should of course upvote answers that attempt to produce images similar to the 6 samples, and downvote answers that break rules or give inconsistent results.

The 6 sample images were taken from texturelib.com. 1000×1000 pixel area selections were taken from two larger images of cracked soil and then resized to 500×500. You may use analysis from these larger images in your program but the output should specifically imitate the 6 chosen sample images.

Mathematica
A Voronoi diagram looks like this drawing, from Wikipedia, showing 19 cells, each containing a single seed point.   A cell consists of the subregion of points which the respective generating point is closer to than any of the other seed points.

The code below generates a diagram from 80 random points (in the square region bound by (-1,-1) and (1,1)).
It uses the polygon primitives (in 2D) in the diagram to build polyhedra (in 3D).  Imagine that each polygon has, just under it, a translation (-.08 in z) of itself. Think of the two polygons as the upper and lower face of a polyhedron.  "Side faces" are then added to complete the polyhedron.
Each polyhedron is then translated outwards, from the center of the image, on the xy plane; it moves away from the middle. The magnitude of the translation varies directly with the distance between the polyhedron's original generating random point and the center of the screen. This "spreading out" of the polyhedra in the xy plane results in crevices.
crackedMud[1]

crackedMud[65535]

Code
ClearAll[polyhedronFromPolygon, voronoiPolygons, generatingPointFromPolygon, crackedMud]

(* polyhedronFromPolygon returns a single polyhedron from a polygon *)

polyhedronFromPolygon[polygon_] :=
 Module[{twoPolygons, verticesOfUpperPolygonCell, nVertices, n = 1},
 verticesOfUpperPolygonCell = Join @@ (polygon[[1]] /. {x_, y_} :> {{x, y, 0}, {x, y, -.08}});
 (* number of vertices in a single *Voronoi* cell *)
 nVertices = Length[verticesOfUpperPolygonCell]/2;

(*vertex indices of the upper and lower polygon faces *)
twoPolygons = Select[Range@(2*nVertices), #] & /@ {OddQ, EvenQ};

(*vertex indices of a rectangular face of the polyhedron *)
While[n < nVertices + 1, AppendTo[twoPolygons,
    {twoPolygons[[1, n]], twoPolygons[[2, n]],
     twoPolygons[[2, If[n + 1 < nVertices + 1, n + 1, 1]]],
     twoPolygons[[1, If[n + 1 < nVertices + 1, n + 1, 1]]]}]; n++];
(*the graphics complex returned is a polyhedron, even though it says Polygon *)
 GraphicsComplex[verticesOfUpperPolygonCell, Polygon[twoPolygons]] ]

(* takes two dimensional coordinates and returns all of the cells of a Voronoi diagram *)

voronoiPolygons[pts_] :=
Module[{voronoiRegion, data},
  voronoiRegion = VoronoiMesh[pts, ImageSize -> Medium,
  PlotTheme -> "Lines", Axes -> True, AxesOrigin -> {0, 0}];
  data = Join @@ (MeshPrimitives[voronoiRegion, 2][[All, 1]] /. {x_, y_} :> {{x, y, 0}, {x, y, .04}});
 (* the mesh primitives are the polygons *)
  MeshPrimitives[voronoiRegion, 2]]

(* Returns, in 3D, the point which was used to generate the nth Voronoi cell. *)
generatingPointFromPolygon[n_, points_, pgons_] :=
 FirstCase[points, {x_, y_} /; RegionMember[pgons[[n]], {x, y}] :> {x,y,0}]

crackedMud[seedNumber_] :-
 Module[{pts, pts3D, geometricImage, nPts, polygons, polyhedra, centerPtinImage},
  SeedRandom[seedNumber];
  nPts = 80;
  pts = RandomReal[{-1, 1}, {nPts, 2}];
  pts3D = pts /. {x_, y_} :> {x, y, .0};
  polygons = voronoiPolygons[pts];
  polyhedra = polyhedronFromPolygon /@ polygons;
  centerPtinImage =   (Mean /@ (PlotRange /.
        AbsoluteOptions[
         Graphics3D[{polyhedra, Blue, Point@pts3D}, Axes -> False,
         Boxed -> False]])) /. {x_Real, y_, _} :> {x, y, 0};
  geometricImage =
  Graphics3D[{RGBColor[0.75, 0.75, 0.8], EdgeForm[Darker@Gray],
        (* # is the nth polygon which yields the nth polyhedron *)
        (* generatingPointFromPolygon returns the point the generated the #th polygon *)

     GeometricTransformation[{polyhedronFromPolygon[polygons[[#]]]},
        TranslationTransform[(generatingPointFromPolygon[#, pts, polygons] - centerPtinImage)/5]] & /@ Range@nPts},
         Axes -> False,  Boxed -> False, ViewPoint -> {0., -1, 1.5},
         Background -> Black, ImageSize -> 1200];

     (*ImageTrim returns a 500 by 500 pixel clip from the center of the image *)
     ImageTrim[
        (*ImageEffect speckles the image *)
        ImageEffect[Rasterize[geometricImage], {"Noise", 1/5}],
     {{250, 250}, {750, 750}}]
  ]


Palindromic numbers with a binary twist Warning : this is NOT a "hey, let's draw a cake in ASCII-art" challenge! Please keep reading ;)

Some time ago it was my birthday, I'm 33 now.

So there is this awkward social tradition consisting in inviting family and friends, putting number-like candles on a cake, sing songs and open gifts.

   33
--------

Instead of numbers, I can use the binary system to put standard candles: I place 6 of them on the cake and light two of them.

 100001
--------

I can see that both decimal and binary numbers of my age are palindromic!

Challenge

I want to know if any other number can be put on a cake with candles and be palindromic, decimal and binary.

Write a program/function to test if a number is palindromic in both decimal and binary. But wait, there's more : in binary, leading zeros count for the test!

Input

A decimal number x that I want to test if it is birthday palindromic with 0 < x < 232-1 (yes, the people in my dimension live very long)

Output

Truthy if it meets exactly these two conditions, Falsey else:

The decimal representation of the number is a standard palindrome
The binary representation of the number is a standard palindrome, and adding leading zeros may help with this

Test cases

1 > 1 => Truthy
6 > 110 (0110) => Truthy
9 > 1001 => Truthy
10 > 1010 (01010) => Falsey, 10 is not palindromic
12 => 1100 (001100) => Falsey, 12 is not palindromic
13 => 1101 (...01101) => Falsey, neither 13 nor 1101 are palindromic
14 => 1110 (01110) => Falsey, 14 is not palindromic
33 > 100001 => Truthy
44 > 101100 (..0101100) => Falsey, 101100 is not palindromic
1342177280 > 1010000000000000000000000000000 (00000000000000000000000000001010000000000000000000000000000) => Falsey, 1342177280 is not palindromic (but the binary representation is)
297515792 > 10001101110111011101100010000 (000010001101110111011101100010000) => Truthy

Rules

Standard loopholes are disallowed
Built-in library conversions and tests are allowed
This is code-golf, the shortest code win!

Good luck, and eventually happy birthday!

05AB1E, 7 bytes

b0Ü‚DíQ

Try it online!
or as a Test Suite

Explanation

b         # convert input to binary
 0Ü       # remove trailing zeroes
   ‚      # pair with input
    D     # duplicate
     í    # reverse each (in the copy)
      Q   # check for equality


Code Golf Christmas Edition: How to print out a Christmas tree of height N Given a number N, how can I print out a Christmas tree of height N using the least number of code characters?  N is assumed constrained to a minimum value of 3, and a maximum value of 30 (bounds and error checking are not necessary). N is given as the one and only command line argument to your program or script.

All languages appreciated, if you see a language already implemented and you can make it shorter, edit if possible - comment otherwise and hope someone cleans up the mess.  Include newlines and White Spaces for clarity, but don't include them in the character count.

A Christmas tree is generated as such, with its "trunk" consisting of only a centered "*"

N = 3:

   *
  ***
 *****
   *

N = 4:

    *
   ***
  *****
 *******
    *

N = 5:

     *
    ***
   *****
  *******
 *********
     *

N defines the height of the branches not including the one line trunk.

Merry Christmas PPCG!

Brainfuck, 240 characters

              ,
             >++
            +++++
           +[-<---
          --->],[>+
         +++++++[-<-
        ----->]<<[->+
       +++++++++<]>>]<
      [->+>+>>>>>>>+<<<
     <<<<<<]>>>>++++++++
    [-<++++>]>++++++[-<++
   +++++>]+>>>++[-<+++++>]
  <<<<<<[-[>.<-]<[-<+>>+<]<
 [->+<]>>>>>[-<.>>+<]>[-<+>]
>.<<++<<<-<->]>>>>>>>-[-<<<<<
           <.>>>
           >>>]<
           <<<<.

Not yet done.  It works, but only with single-digit numbers.

EDIT: Done!  Works for interpreters using 0 as EOF.  See NOTEs in commented source for those with -1.

EDIT again: I should note that because Brainfuck lacks a standard method for reading command line arguments, I used stdin (standard input) instead.  ASCII, of course.

EDIT a third time: Oh dear, it seems I stripped . (output) characters when condensing the code.  Fixed...

Here's the basic memory management of the main loop.  I'm sure it can be heavily optimized to reduce the character count by 30 or so.

Temporary
Copy of counter
Counter (counts to 0)
Space character (decimal 32)
Asterisk character (decimal 42)
Number of asterisks on current line (1 + 2*counter)
Temporary
New line character
Temporary?
Total number of lines (i.e. input value; stored until the very end, when printing the trunk)

Condensed version:

,>++++++++[-<------>],[>++++++++[-<------>]<<[->++++++++++<]>>]<[->+>+>>>>>>>+<<<<<<<<<]>>>>++++++++[-<++++>]>++++++[-<+++++++>]+>>>++[-<+++++>]<<<<<<[-[>.<-]<[-<+>>+<]<[->+<]>>>>>[-<.>>+<]>[-<+>]>.<<++<<<-<->]>>>>>>>-[-<<<<<<.>>>>>>]<<<<<.

And the pretty version:

ASCII to number
,>
++++++++[-<------>]  = 48 ('0')

Second digit (may be NULL)
,
NOTE:   Add plus sign here if your interpreter uses negative one for EOF
[ NOTE: Then add minus sign here
 >++++++++[-<------>]
 <<[->++++++++++<]>>  Add first digit by tens
]

Duplicate number
<[->+>+>>>>>>>+<<<<<<<<<]>>

Space char
>>++++++++[-<++++>]

Asterisk char
>++++++[-<+++++++>]

Star count
+

New line char
>>>++[-<+++++>]<<<

<<<

Main loop
[
Print leading spaces
-[>.<-]

Undo delete
<[-<+>>+<]
<[->+<]
>>

Print stars
>>>[-<.>>+<]

Add stars and print new line
>[-<+>]
>.<
<++

<<<

-<->
End main loop
]

Print the trunk
>>>>>>>
-[-<<<<<<.>>>>>>]
<<<<<.

Merry Christmas =)


Group the Numbers With the Same Sum Your task is, given a square grid of digits (0-9), output one of the ways that the digits can be grouped such that:

Each digit is part of exactly one group
All groups have the same number of digits
All groups are bounded by one polygon-like shape (this means that every digit in the group is next to [left, right, up, down] at least one other digit of the same group, unless each group has 1 element).
All groups have the same sum

The input grid will always be a square:
You may choose any input method you would like (including supplying arguments to a function or method). In addition, the input will supply the number of groups that your program should group the digits into.

Example input:

Suppose your input format is stringOfDigits numberOfGroups.

An example input would be:

156790809 3

which would translate to (a grid of sqrt(9) * sqrt(9))

1 5 6
7 9 0
8 0 9

which you would have to divide into 3 groups, each of which should have 9 / 3 = 3 elements with the same sum.

Output:
Output should be the string of digits, with optional spaces and newlines for formatting, with each digit followed by a letter a-z indicating its group. There should be exactly numberOfTotalDigits / numberOfGroups elements in each group. You will never have to divide something into more than 26 groups.

Example output:

1a 5a 6b
7c 9a 0b
8c 0c 9b

Note that replacing all as with bs and bs with as is equally valid. As long as each group is denoted by a distinct letter, the output is valid.

In addition, I expect most programs to output something along the lines of this, because newlines/spaces are optional:

1a5a6b7c9a0b8c0c9b

In this case, adding all digits of group a, b, or c makes 15. In addition, all groups are bound by some polygon.

Invalid outputs:

1a 5a 6b
7c 9a 0c
8c 0b 9b

because the groups do not form polygons (specifically, the 6b is isolated and 0c is also lonely).

1a 5a 6b
7c 9a 0b
8c 0b 9b

because the group b has 4 elements while c only has 2.

Etc.

If there is no valid solution, your program may do anything (i.e. stop, crash, run forever) but if your program prints None when there is no valid solution, -15 to your score.

If there is more than one solution, you only have to print one, but -20 if your program prints all of them separated by some delimiter.

This is code golf, so shortest code (with bonuses) wins!

Pyth, 122 - 20 - 15 = 87
=Z/lzQ=ks^lz.5Jm]dUzL[-bk+bk?tb%bkb?hb%hbkb)FNJIgNZB~Jm+NksmybN;|jbS{msm+@zk@S*Z<GQxsdkUzfqSsTUz^fqsmv@*ZzbY/smvdzQJQ"None

Changes:

130 -> 120: Switched to newline separated input.

120 -> 134: Fixed a bug involving groups not of size equal to the side length of the matrix.

134 -> 120: Prints all solutions, including ones equivalent under group renaming.

120 -> 122: Fixed a bug where only paths would be generated, instead of all legal groups.

Test run:
pyth programs/sum_group.pyth <<< '156790809
3'
1a5a6b7c9a0b8c0c9b
1a5a6c7b9a0c8b0b9c
1b5b6a7c9b0a8c0c9a
1b5b6c7a9b0c8a0a9c
1c5c6a7b9c0a8b0b9a
1c5c6b7a9c0b8a0a9b

pyth programs/sum_group.pyth <<< '156790808
3'
None

pyth programs/sum_group.pyth <<< '1111
2'
1a1a1b1b
1a1b1a1b
1b1a1b1a
1b1b1a1a

Explanation:
Pyth code           (Pseudo)-Python code              Comments

(implicit)          z = input()                       z is the digit string
(implicit)          Q = eval(input())                 S is the number of groups
(implicit)          G = 'abcdefghijklmnopqrstuvwxyz'
=Z/lzQ              Z = len(z)/Q                      Z is the size of each group.
=ks^lz.5            k = int(len(z) ** .5)             k is the side length of the matrix.
Jm]dUz              J = map(lambda d:[d], range(len(z))) Locations are encoded as numbers.
L                   def y(b): return                  y will be the transition function.
 [-bQ                         [b-k,                   Move up - the row above is k less.
  +bQ                          b+k,                   Move down - the row below is k more.
  ?tb%bkb                      b-1 if b%k else b      Move left, unless at the left edge.
  ?hb%hbkb)                    b+1 if (b+1)%k else b] Move right, unless at right edge.
FNJ                 for N in J:                       This constructs the list of all
   IgNZB                       if N[Z-1]: break       Z-length connected groups.
   ~Jm+Nk                      J+=map(lambda k: N+[k],  Append to J the group of N +
      smybN                          sum(map(lambda b:  anything reachable from
                                     y(b),N)))        anywhere in N.
   ;                (end for)
|                   or                                Print first truthy thing between
 S{                 sorted(set(                       Unique elements in sorted order of
   ms               map(lambda b:sum(                 Map+sum over allowable combinations
     m+@zd          map(lambda d:z[d]+                Character in original digit string
       @S*Z<GQ      sorted(G[:Q]*Z)[                  Repeated and sorted early alphabet
        xsbd        sum(b).index(d)],                 At index of number in sum of groups
      Uz                range(len(z)))                Over possible indexes.
   f                filter(lambda T:                  To generate allowable combinations,
                                                      we will filter all groups of Q paths.
    qSsTUz          sorted(sum(T)) == range(len(z))   Ensure all locations are visited.
    ^                                                 Combinations of
     f              filter(lambda Y:                  Filter over connected Z-length groups
      qsm           equal(sum(map(lambda k:           Sum of the values of the group
         v@*ZzkY    eval((z*Z)[k]),Y)                 In the original digit string
       /smvbzQ      sum(map(lambda b:eval(b),z))/Q    must equal the sum of all values in z
                                                      divided by the number of groups.
      J             J                                 Filter over connected Z-length groups
     Q              Q                                 Combinations of length Q
 "None              "None"                            If the above was empty, print "None"


Working on my Knight moves Hexagonal chess describes a family of chess variants played on a board where the cells are hexagons instead of the traditional squares. There are many such variants; in this challenge we'll be focusing on Gliński's variant, which is the most common.

The board is composed of three colors (so that the same color doesn't share an edge), with the edges of the hexagons facing the players. The board has 11 files, marked by letters a through l (letter j is not used), and 11 ranks (which bend 60° at file f). Ranks 1 through 6 each contain 11 cells, rank 7 has 9 cells, rank 8 has 7, and so on. Rank 11 contains exactly one cell: f11. (If it helps, think of each rank as making a very wide "V" shape.)

Here is an example picture of the board, with the knight on the center cell. The cells marked with a dot are the legal moves of this particular knight. The knight moves in a similar fashion to "normal" chess, two-down-and-one-over. In hexagonal chess terms, it's an orthogonal move (across an edge), then a diagonal move in the same direction (the closest move to the same color). For example with the knight below, an orthogonal move "up" to the light brown is then accompanied by a diagonal move "up and right" or "up and left" to the nearest light brown.

From the public domain via https://commons.wikimedia.org/wiki/File:Glinski_Chess_Knight.svg

This knight is positioned at f6 and the legal moves are thus

c4, c5, d3, d7, e3, e8, g3, g8, h3, h7, i4, i5

Input

A single input giving the starting cell of our knight. This can be as a single string "b6", as two strings, "b", "6", etc., in any convenient format. The input letters can be uppercase or lowercase -- your choice.

Output

A list of the valid moves that a knight on that location can make. This can be as an array of strings, a single string with an unambiguous and consistent delimiter, separate strings by newlines, etc., whatever is most convenient. The output does not necessarily need to be in sorted order, and can be in either uppercase or lowercase -- your choice.

Rules

Assume no other pieces are on the board or interfere with the moves. We're focusing on just the knight.
Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
If possible, please include a link to an online testing environment so other people can try out your code!
Standard loopholes are forbidden.
This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

Examples

b6
a3, c4, d5, d9, e7, e8

f6
c4, c5, d3, d7, e3, e8, g3, g8, h3, h7, i4, i5

f11
d8, e8, g8, h8

i1
f2, f3, g4, h4, l2, k3

JavaScript (ES6), 184 bytes

Takes the file F as a character and the rank R as an integer in currying syntax (F)(R). Returns an array of strings.

F=>R=>[...'100124566542'].map((X,i)=>(X-=3-(x=(s='abcdefghikl').search(F)))-7<(Y=('9641001469'[i]||10)-(A=Math.abs)(x-5)+17-2*R)&X+Y>3&X+16>Y&X+Y<27&&s[X]+(22-Y-A(X-5))/2).filter(n=>n)

How?

Step #1: convert file/rank to Cartesian coordinates

We convert the hexagonal chess coordinates to Cartesian coordinates (x, y) with x in [0 .. 10] and y in [0 .. 20]:

      00 01 02 03 04 05 06 07 08 09 10
   +----------------------------------
00 |                f11                     F = file (letter)
01 |             e10   g10                  R = rank in [1 .. 11]
02 |          d09   f10   h09
03 |       c08   e09   g09   i08            F | a b c d e f g h i k l
04 |    b07   d08   f09   h08   k07         --+-----------------------
05 | a06   c07   e08   g08   i07   l06      x | 0 1 2 3 4 5 6 7 8 9 10
06 |    b06   d07   f08   h07   k06
07 | a05   c06   e07   g07   i06   l05      y = 22 - |x - 5| - 2R
08 |    b05   d06   f07   h06   k05
09 | a04   c05   e06   g06   i05   l04
10 |    b04   d05   f06   h05   k04
11 | a03   c04   e05   g05   i04   l03
12 |    b03   d04   f05   h04   k03
13 | a02   c03   e04   g04   i03   l02
14 |    b02   d03   f04   h03   k02
15 | a01   c02   e03   g03   i02   l01
16 |    b01   d02   f03   h02   k01
17 |       c01   e02   g02   i01
18 |          d01   f02   h01
19 |             e01   g01
20 |                f01

Step #2: apply the move vectors

Below is the list of the move vectors in the Cartesian system:

(-2, +4), (-1, -5), (+3, +1),
(-3, +1), (+1, -5), (+2, +4),
(-3, -1), (+2, -4), (+1, +5),
(-2, -4), (+3, -1), (-1, +5)

We apply each of them to the source coordinates (x, y) and get a list of target coordinates (X, Y).

Step #3: test the target coordinates

We now need to check which target coordinates are actually located inside the board. This is done by testing X + Y and X - Y:

The coordinates are valid if all the following comparisons are true:

X + Y > 3
X + Y < 27
X - Y < 7
X - Y > -17

We should also verify that X is in [0 .. 10]. This is not done explicitly because s[X] is undefined if it's not, which eventually results in a falsy value that gets filtered out.

Step #4: convert back to hexagonal chess coordinates

Finally the valid target coordinates are converted back to hexagonal chess coordinates, using the inverse of the formulas described at step #1.

Test cases

let f =

F=>R=>[...'100124566542'].map((X,i)=>(X-=3-(x=(s='abcdefghikl').search(F)))-7<(Y=('9641001469'[i]||10)-(A=Math.abs)(x-5)+17-2*R)&X+Y>3&X+16>Y&X+Y<27&&s[X]+(22-Y-A(X-5))/2).filter(n=>n)

console.log(JSON.stringify(f('b')(6)))
console.log(JSON.stringify(f('f')(6)))
console.log(JSON.stringify(f('f')(11)))
console.log(JSON.stringify(f('i')(1)))


What's that number in Shortlex? Most computers store integers in binary, but output them in decimal. However, decimal is just one representation, we just happen to find it convenient.

This challenge is to write some code to output an integer value in shortlex decimal.

What's that?
http://en.wikipedia.org/wiki/Shortlex_order

Shortlex takes the length of the sequence of digits as the primary signifier of value. The sequence, starting from an empty string representing zero, is...

ε,0,1,...,8,9,00,01,...98,99,000,001,...,998,999,0000,...

(Think of Excel columns, but using only the decimal digits.)

Write a program or function that accepts an integer and returns a string corresponding to the shortlex-decimal representation of that integer as described above.

Test values:

0 → ""  (Empty string)
1 → "0"
10 → "9"
11 → "00"
42 → "31"
100 → "89"
800 → "689"
1060 → "949"
10270 → "9159"
100501 → "89390"

JavaScript (ES6) 42 74
n=>(n-~(n+'').replace(/./g,8)+'').slice(1)

Test in FireFox console
;[0,1,10,11,42,100,800,1060,10270,100501]
.forEach(x => console.log(x +" -> '" + S(x) + "'"))

Output
0 -> ''
1 -> '0'
10 -> '9'
11 -> '00'
42 -> '31'
100 -> '89'
800 -> '689'
1060 -> '949'
10270 -> '9159'
100501 -> '89390'

How did I think of this?
Given a fixed number of digits, the output sequence is simply ascending, so there is a fixed delta between input and output. Have a look:
  1..10 -> 0..9 (delta -1)
 11..110 -> 00..99 (delta -11)
111..1110 -> 000..999 (delta -111) mmm there's a pattern here...

But the leading 0s are difficult to manage, so I have a standard trick, add a first digit and work modulo (that is, cut the first digit in output). Then -1-> +9, -11 -> +89, -111 -> +889 and so on.
Last step: I don't care what the first digit is, so there is no need to check if the iinput number is < or > than 111... (honestly I found this by trial and error)
Test

var F=
n=>(n-~(n+'').replace(/./g,8)+'').slice(1)

function update()
{
  var i=+I.value
  O.textContent = F(i)
}

update()
<input id=I value=99 type=number oninput='update()'>


Find X in a partially sorted Array Your job is to find the location (read index) of a given element X in an array gone through the following transformation process:

Take a fully sorted integer array of size N (N is known implicitly)
Take any random number of mutually exclusive even index pairs (as in that no index appears in more than 1 pair) from the array and swap the elements on those indexes.

A sample array can be like

[5, 2, 3, 4, -1, 6, 90, 80, 70, 100]

formed by

// Take fully sorted integer array
[-1, 2, 3, 4, 5, 6, 70, 80, 90, 100]
// Take some even index pairs : (0, 4) and (6, 8)
// Swap the elements in these indexes. i.e., element at 4th index goes to 0th etc.
// Final array:
[5, 2, 3, 4, -1, 6, 90, 80, 70, 100]

and a sample X to find in this array can be

-1

You should output the index of the element X in the final array (4 in the above example) or -1 if the element is not found in the array.

Rules

In built searching functions are prohibited.
You must write a method/function/program which takes input from STDIN/Command line arguments/Function arguments.
Input must be in <Array> <X> format. Example: [5, 2, 3, 4, 1, 6, 9, 8, 7, 10] 1
The input array may also contain duplicate integers. In such case, any one index can be the output. UPDATE : You may assume that total number of duplicates << (far less than) size of array. For the benefit of the question in general, duplicates are now prohibited to avoid playing a role in time complexity of the searching algorithm.
Output should be the index of the element X in the array or -1 if not present.

Scoring

Being a code-golf and a code-challenge, your score is calculated by <byte count of your program>*<coeff. of complexity>
Coefficient of Complexity is decided based on the worst case time complexity of your code (Big-O) using the mappings given below.
If your code needs to know the length of the array, it can calculate length using inbuilt methods and that won't be added to the time complexity of the searching part of the code.

Time Complexity      Coefficient
--------------------------------
O(1)                 0.25
O(log(n))            0.5
O(n)                 5
O(n*log(n))          8.5
O(n^2)               10
O(greater than n^2)  20

Minimum score wins!

Bonus

Multiply your final score by 0.5 if you can handle a case where the array has gone through the step 2 in the transformation process I times (instead of just 1), where I is passed as the third parameter in input.
Note that while going through step 2, I times, pairs in each step are mutually exclusive, but pairs in different steps can have common indexes.

JavaScript (E6) 97.5 (39*5*0.5)

(O(n), linear search, the array can be scrambled again and again)
The function accepts (and ignores) a third parameter

F=(a,x)=>a.map((e,i)=>e-x?0:j=i,j=-1)|j

or

F=(a,x)=>a.some((e,i)=>(j=i,e==x))?j:-1

or

F=(a,x)=>a.every((e,i)=>(j=i,e-x))?-1:j

Test in FireFox/FireBug console

F([5, 2, 3, 4, -1, 6, 90, 80, 70, 100],-1, 2)

Output

4


How many 14ers did I climb? In mountaineering terminology, a "14er" is any mountain with an elevation of 14 000 feet or more. However, there is another distinction. For a peak to count as a 14er, it must also have a "geographic prominence" of 300 or more feet. This means that to move from one 14er to another, you must first descend at least 300 feet before rising again. Take this example. Line 1 counts as 14 000 feet, and each line counts as 100 feet.

  /\__/\
 /      \
/        \

Now, both of these peaks have enough elevation to count, but there isn't enough drop in elevation between them to count as two separate peaks. Therefore, one of these counts as a 14er, and the other one is just a "partial peak". Here is an example where the two peaks count as two separate 14er:

   /\    /\
  /  \  /  \
 /    \/    \
/            \

There can also be a partial peak on the decline between two 14ers. Here's a slightly modified version of the last mountain range:

   /\      /\
  /  \/\  /  \
 /      \/    \
/              \

This mountain range also counts as two 14ers.

You must write a program or function that takes an ascii-art representation of a mountain range, and return how many 14ers are in the range. You can take input in whatever format is most convenient for you, be it 2D array of characters, a string with newline, or a string with some other delimiter. You can assume that all inputs will only contain the characters /\_, and that the length of each line will be the same (including trailing spaces). You can also assume that the mountain range starts on the bottom left corner with either a / or a _.

If the last section of a mountain is not on the bottom line, you can assume that the mountain only decreases after that, e.g.

  /
 /
/

Counts as a single 14er.

You do not have to handle invalid mountain ranges.

Here is some sample I/O:

         /\___/\_
        /        \    /\
       /          \  /  \
   _/\/            \/    \
  /                       \
 /                         \
/                           \_

2

                  /\    /\
         /\      /  \  /
  /\    /  \    /    \/
 /  \  /    \  /
/    \/      \/

4

       /\
 _/\__/  \
/         \

1

      /\
     /  \   /\
    /    \_/  \
   /           \
  /             \
 /               \
/                 \

1

              /\
    /\_/\    /  \_
   /     \  /     \     /\
  /       \/       \   /
 /                  \_/
/

3

C, 174 bytes
a[99],c,p,j,M,m;main(i){for(i=j=1;c=getchar(),~c;i++)c<11?a[i]=j++,i=0:c&4?a[i]=j:0;for(m=j;c=a[i++];c>a[i-2]?M-m>1&&c-m>1?M=c,m=j,p++:M<c?M=m=c:M:m>c?m=c:0);printf("%d",p);}

Requires a trailing newline in the input, otherwise +4 bytes.


Output the largest number with the fewest digits Given a nonempty list of positive decimal integers, output the largest number from the set of numbers with the fewest digits.

The input list will not be in any particular order and may contain repeated values.

Examples:

[1] -> 1
[9] -> 9
[1729] -> 1729
[1, 1] -> 1
[34, 3] -> 3
[38, 39] -> 39
[409, 12, 13] -> 13
[11, 11, 11, 1] -> 1
[11, 11, 11, 11] -> 11
[78, 99, 620, 1] -> 1
[78, 99, 620, 10] -> 99
[78, 99, 620, 100] -> 99
[1, 5, 9, 12, 63, 102] -> 9
[3451, 29820, 2983, 1223, 1337] -> 3451
[738, 2383, 281, 938, 212, 1010] -> 938

The shortest code in bytes wins.

Pyth, 7 3 6 bytes

eS.ml`

Test Suite

Explanation:

e      Still grab the last element
 S      Still sort
  .ml`   But prefilter the list for those with the (m)inimum length.

7 byte solution:

eSh.gl`

Test Suite

Explanation:

   .g   Group items in (implicit) input by:
     l  The length of
      ` their representation
  h     Get those with the shortest length
 S      Sort the resulting list
e       and grab the last (i.e. largest) element


Print 0 to 100 without 1-9 characters Print 0 to 100 without using characters 1,2,3,4,5,6,7,8,9 in your code.
Seperator of numbers can be comma, whitespace or newline.
Shortest code wins.

R, 9 bytes

F:volcano

Try it online!
The sequence operator : coerces its arguments to integers. F is the boolean FALSE, which gets coerced to 0. volcano is one of the many built-in datasets (it gives topographic information about Maunga Whau in New Zealand); since it is a matrix, : fetches the value at position [1, 1] which is luckily equal to 100. The code is therefore equivalent to 0:100.
This answer was inspired by a conversation with Giuseppe and Kirill L. in the comments under Giuseppe's R answer.


Interpret Befunge-93 The program will be provided as the first argument, stdin should be used for all
read requests by the program and stdout for all write requests.  It can be
assumed that the program is less than 80 characters wide and less than 25 lines
high.

~ should push -1 if there is nothing to read.
Any pop off the bottom of the list should simply return 0, including for any calculations.
For p and g, x and y are 0 based indices.
Input should be fully buffered, i.e. & and ~ block the program until EOF is encountered on stdin then any remaining input is kept to serve future requests.

The following commands must be available:

  0-9
      Push this number on the stack
  +
      Addition: Pop a then b, push a+b
  -
      Subtraction: Pop a then b, push b-a
  *
      Multiplication: Pop a then b, push a*b
  /
      Integer division: Pop a then b, push b/a, rounded down. If a is 0, result is undefined
  %
      Modulo: Pop a then b, push the remainder of the integer division of b/a. If a is 0, result is undefined
  !
      Logical NOT: Pop a value. If the value is 0, push 1; otherwise, push 0.
  `
      Greater than: Pop a then b, push 1 if b>a, otherwise 0.
  >
      Start moving right
  <
      Start moving left
  ^
      Start moving up
  v
      Start moving down
  ?
      Start moving in a random cardinal direction
  _
      Pop a value; move right if value=0, left otherwise
  |
      Pop a value; move down if value=0, up otherwise
  "
      Start string mode: push each character's ASCII value all the way up to the next "
  :
      Duplicate value on top of the stack
  \
      Swap two values on top of the stack
  $
      Pop value from the stack
  .
      Pop value and output as an integer
  ,
      Pop value and output as ASCII character
  #
      Trampoline: Skip next cell
  p
      A "put" call (a way to store a value for later use). Pop y then x then v, change the character at the position (x,y) in the program to the character with ASCII value v
  g
      A "get" call (a way to retrieve data in storage). Pop y then x, push ASCII value of the character at that position in the program
  &
      Input an integer (may be multiple characters and may be negative) and push it
  ~
      Input a single character from stdin and push its ASCII value
  @
      End program

This is a code golf, shortest answer wins.  If there is a tie then the first answer wins.

You may use any language feature not specifically designed for Befunge to implement this, if you want to try and translate Befunge to native code and eval it good luck.

For test cases look at my recent answers.  The reference interpreter I have been using is http://www.quirkster.com/js/befunge.html.

One quick test case of some features from "egnufeB">:#,_@

1-0g:"Z"-#v_$91+"sparw tup/teG">:#,_$               v                          Z
          >:" "-#v_$91+"ecaps snruter teg BOO">:#,_$v
v                >0" snruter teg BOO">:#,_$.91+,    >
>8:+:*11p11g#v_91+"tib 8 dengis"01-11p11g!#v_"nu">" era slleC">:#,_v
vv           >91+"tib 8>"                  >     ^                 >91+"krow " #
 >        >"spmuj egdE">:#,_   91+"krow "04-3%1+#v_        >"sredniamer evitag"v
>"ton od "^                                      >"ton od "^
"eN">:#,_  91+"skrow edomgnirts ni @">:#,_@                                    >

Befunge-93 - 404 371 361 352 339 337 323 bytes
<xyXYvp01<>110vv5_v#`0+1:_v#+!-"g"\<v"<":::<>1v#p03-1_>! g20gp00g1+0v25p
v2g02 < p0 20p<+vp020p01-10$_:"p"-!^>>-!\ v^ <>0p20pv|!*-";"\+1::~p0<
v2-10<^v# ^#<  <<$<       < ^+!-"_"\+!-"?"<>#^_10v4p<:^00 _$20g1+20p^
v21p010>#<40g20v>\%:40p5+g:92p:75*1--00g!\#^_\$0 v   >91+-^
<3+g01g 03p04+g<^++g04g02:*54p03:%\++g03g01:"P"p0<

Try It Online!
Input program must have at most 20 lines. Input can be provided in same file as Befunge program by placing it after a ; character. Yes, it can interpret itself, but the *54 in the bottom line should be replaced by *53 if you do that. And if you ask that interpreted interpreter to interpret itself, change it to *52 etc. If run in a Befunge-97 interpreter, it will also support the a-f commands (but not ' or any new command that affects control flow or wrapping behavior).
Note that it basically asks the interpreter it runs in to handle all the stuff relating to I/O and stack, so its specific behavior is largely dependent on that of the interpreter running it. In other words, it is perfectly compliant if run in a compliant interpreter.
It works by reading in the program from input (until EOF or semicolon) directly into the playfield below it, then simulating the movement of a virtual instruction pointer through that program. It copies each command from the program into its own execution area (at position (9,2) on the grid) and runs its own instruction pointer through it after ensuring all of its own data has been removed from the stack (as all of the interpreted program's stack data is maintained at the bottom of the stack). This is the standard methodology for Befunge self-interpretation since the early 00s, but I don't think it has ever been done in such a small program.
A fuller explanation is in the annotations you can see by clicking the link above.


Arbitrary Randomness (Speed edition) Given integer n, calculate a set of n random unique integers in range 1..n^2 (inclusive) such that the sum of the set is equal to n^2

Random, in this case, means uniformly random between valid outputs. Each valid output for a given n must have a uniform chance of being generated.

For example, n=3 should have a 1/3 chance each of outputting 6, 1, 2, 3, 5, 1, or 4, 3, 2. As this is a set, order is irrelevant, 4, 3, 2 is identical to 3, 2, 4

Scoring

The winner is the program that can compute the highest n in under 60 seconds.
Note: To prevent possible partial hardcoding, all entries must be under 4000 bytes

Testing

All code will be run on my local Windows 10 machine (Razer Blade 15, 16GB RAM, Intel i7-8750H 6 cores, 4.1GHz, GTX 1060 in case you want to abuse the GPU) so please provide detailed instructions to run your code on my machine.
At request, entries can be run either via Debian on WSL, or on a Xubuntu Virtual Machine (both on the same machine as above)

Submissions will be run 50 times in succession, final score will be an average of all 50 results.

Rust, n ≈ 1400

How to run

Build with cargo build --release, and run with target/release/arbitrary-randomness n.

This program runs fastest with lots of memory (as long as it’s not swapping, of course).  You can adjust its memory usage by editing the MAX_BYTES constant, currently set at 8 GiB.

How it works

The set is constructed by a sequence of binary decisions (each number is either inside or outside the set), each of whose probabilities are computed combinatorially by counting the number of possible sets constructible after each choice using dynamic programming.

Memory usage for large n is reduced by using a version of this binomial partitioning strategy.

Cargo.toml

[package]
name = "arbitrary-randomness"
version = "0.1.0"
authors = ["Anders Kaseorg <andersk@mit.edu>"]

[dependencies]
rand = "0.6"

src/main.rs

extern crate rand;

use rand::prelude::*;
use std::env;
use std::f64;
use std::mem;

const MAX_BYTES: usize = 8 << 30; // 8 gibibytes

fn ln_add_exp(a: f64, b: f64) -> f64 {
    if a > b {
        (b - a).exp().ln_1p() + a
    } else {
        (a - b).exp().ln_1p() + b
    }
}

fn split(steps: usize, memory: usize) -> usize {
    if steps == 1 {
        return 0;
    }
    let mut u0 = 0;
    let mut n0 = f64::INFINITY;
    let mut u1 = steps;
    let mut n1 = -f64::INFINITY;
    while u1 - u0 > 1 {
        let u = (u0 + u1) / 2;
        let k = (memory * steps) as f64 / u as f64;
        let n = (0..memory)
            .map(|i| (k - i as f64) / (i as f64 + 1.))
            .product();
        if n > steps as f64 {
            u0 = u;
            n0 = n;
        } else {
            u1 = u;
            n1 = n;
        }
    }
    if n0 - (steps as f64) <= steps as f64 - n1 {
        u0
    } else {
        u1
    }
}

fn gen(n: usize, rng: &mut impl Rng) -> Vec<usize> {
    let s = n * n.wrapping_sub(1) / 2;
    let width = n.min(MAX_BYTES / ((s + 1) * mem::size_of::<f64>()));
    let ix = |m: usize, k: usize| m + k * (s + 1);
    let mut ln_count = vec![-f64::INFINITY; ix(0, width)];
    let mut checkpoints = Vec::with_capacity(width);
    let mut a = Vec::with_capacity(n);
    let mut m = s;
    let mut x = 1;

    for k in (1..=n).rev() {
        let i = loop {
            let i = checkpoints.len();
            let k0 = *checkpoints.last().unwrap_or(&0);
            if k0 == k {
                checkpoints.pop();
                break i - 1;
            }
            if i == 0 {
                ln_count[ix(0, i)] = 0.;
                for m in 1..=s {
                    ln_count[ix(m, i)] = -f64::INFINITY;
                }
            } else {
                for m in 0..=s {
                    ln_count[ix(m, i)] = ln_count[ix(m, i - 1)];
                }
            }
            let k1 = k - split(k - k0, width - 1 - i);
            for step in k0 + 1..=k1 {
                for m in step..=s {
                    ln_count[ix(m, i)] = ln_add_exp(ln_count[ix(m - step, i)], ln_count[ix(m, i)]);
                }
            }
            if k1 == k {
                break i;
            }
            checkpoints.push(k1);
        };

        while m >= k && rng.gen_bool((ln_count[ix(m - k, i)] - ln_count[ix(m, i)]).exp()) {
            m -= k;
            x += 1;
        }
        a.push(x);
        x += 1;
    }
    a
}

fn main() {
    if let [_, n] = &env::args().collect::<Vec<_>>()[..] {
        let n = n.parse().unwrap();
        let mut rng = StdRng::from_entropy();
        println!("{:?}", gen(n, &mut rng));
    } else {
        panic!("expected one argument");
    }
}

Try it online!

(Note: the TIO version has a few modifications.  First, the memory limit is reduced to 1 GiB. Second, since TIO doesn’t let you write a Cargo.toml and depend on external crates like rand, I instead pulled in drand48 from the C library using the FFI.  I didn’t bother to seed it, so the TIO version will produce the same result on every run.  Don’t use the TIO version for official benchmarking.)


Octave, 49 bytes

@(p,x,n)(f=@(r,m){@()p(r(r,m-1)),x}{~m+1}())(f,n)

Try it online!
Or, taking coefficients:
Octave, 75 57 bytes

@(p,x,n)(f=@(f,n){@()polyval(p,f(f,n-1)),x}{~n+1}())(f,n)

Try it online!
A special thanks for Suever over at StackOverflow, for this answer some time ago on a question of mine, proving that a recursive anonymous function is possible.
This defines an anonymous function, which is a wrapper for a recursive anonymous function; something which is not a native Octave concept, and requires some fancy cell array indexing.
As a bonus, the second version is a nice lesson in variable scoping in Octave. All instances of r can legally be replaced by f, which then simply overwrites the existing f in the most local scope (similar for n)
Explanation
@(p,x,n)(f=@(r,m){@()p(r(r,m-1)),x}{~m+1}())(f,n)
@(p,x,n)         .                ..    .  ..   .   % Defines main anonymous function
        (f=@(r,m).                ..    .  ).   .   % Defines recursive anonymous function
                 .                ..    .   .   .   %  r: Handle ('pointer') to recursive function
                 .                ..    .   .   .   %  m: Current recursion depth (counting from n to 0)
                 .                ..    .   (f,n)   % And call it, with
                 .                ..    .           %  r=f (handle to itself)
                 .                ..    .           %  m=n (initial recursion)
                 {                }{    }           % Create and index into cell array
                                    ~m+1            %  Index: for m>0: 1; for m==0: 2.
                                ,x                  %  Index 2: final recursion, just return x.
                  @()                               %  Index 1: define anonymous function, taking no inputs.
                     p(        )                    %   which evaluates the polynomial
                       r(     )                     %    of the recursive function call
                         r,m-1                      %     which is called with r
                                                    %     and recursion depth m-1
                                                    %     (until m=0, see above)
                                         ()         % Evaluate the result of the cell array indexing operation.
                                                    %  which is either the anonymous function
                                                    %  or the constant `x`.

The key to this is that anonymous functions are not evaluated when they are defined. So, the @(), which seems a bit superfluous since it defines an anonymous function which is called with () directly after, is actually strictly necessary. It is not called unless it is selected by the indexing statement.
Octave, 39 bytes (boring way)

function x=f(p,x,n)for i=1:n;o=p(o);end

Just for completeness, the Octave solution with the shortest bytecount.
Yawn..


Accessories after the fact! This challenge is inspired by Mathematics is fact. Programming is not.

The mathematical notation for a factorial, or a fact is an exclamation mark !. The exclamation mark is also a common symbol for not in many programming languages.
Challenge:
Take a string, containing numerals, and the characters: + ! as input and output the following:
Everything in front of an exclamation mark should be evaluated as a mathematical expression, so 2+2 would be 4.
Everything after a single exclamation mark should be appended as accessories to whatever is in front of it, so: 2+2!5 should give 45, because 2+2=4, and 5 is an accessory. 2+2!5+5 should give 410.
Since ! also means not, anything that's not an accessory after the fact should not be appended. So, 2+2!!5 should give 4, since 5 is not an accessory. Now, not(not(true))==true, so 2+2!!!5 should give 45. 2+2!!5!5+5 should give: 410, because 2+2=4, then followed by a factorial and !5!5+5. The first 5 is not a fact, but 5+5 is after another exclamation mark, and is therefore a fact, yet again.
Clarifications:

The exclamation marks will not be adjacent to a + on either side.
There will not be leading + for numbers (it's 5, not +5).
You may optionally include a leading zero if that's the result of the expression in front of the first !. Both 4 and 04 are accepted output for input: 0+0!4

Executive summary: evaluate each sum (treating ! as separators). Then discard all numbers that appear after an even number of ! (counting from the start of the string). Then remove all !.
Test cases:
!
   <- Empty string

5
5

12!
12

!87
87

!!5
   <- Empty string

5+5!2+2
104

5+5!!2+2
10

1!2!3!4!5!6!7!8!9
12468

10+10!!2+2!!3+3!4+4
208

2!!3!5
25

2!!3!5!7
25

10!!!!!!!5
105

This is code-golf so the shortest code in bytes (in each language) wins! Explanations are strongly encouraged!

JavaScript (ES6), 58 56 bytes

Saved two bytes thanks to Martin Ender.

let f =
x=>x.replace(/[^!]+/g,eval).replace(/!(\d*)!?\d*/g,"$1")
<input value="2+2!5+5" oninput="try{O.value=f(value)}catch(e){}"><br>
<input id=O value="410" disabled>

Might be improved somehow...


Help John watch movies! Introduction

So John finally has his holidays! And what better could he do than watching some movies. He indeed has a lot of movies to watch, but he is unable to decide which one to watch first. He has a list of movies, each in the format: <Movie name> (<Year>). So he makes a simple set of rules to decide his order of watching movies.

1) The first preference is given to the release year. If a movie released a year or earlier than others, then he would watch them first.

2) If two or more movies released in the same year, and one of them begins with a number, then he would prefer to watch that movie first.

3) If two or more movies released in the same year begin with a number as well, then the movie which comes first on the original list would be watched first.

4) If two or more movies released in the same year begin with a letter, then the movie beginning with a letter which comes earlier in the English alphabet will be chosen first. If two movies begin with the same letter, then the one containing a lesser number of characters in the movie name(including spaces) will be chosen first.

5) If the number of characters is also same, then the movie which comes later in the original list would be watched first.

Well, what a great set of rules indeed. Now the challenge.

Challenge

The input will be a list of movies, i.e, strings - all following the specified format, and you need to output the sorted list, following the above stated rules. Be case insensitive , i.e, treat both uppercase and lower case characters equally and assume all inputs to be valid, and the list will contain no duplicate elements. Also, every character in the movie name is either a letter, or a number and there are blank spaces only in between. You can assume the release year is 4 digits long.

Examples

Input
Output

['The Town (2010)', 'The Prestige (2006)', 'The Departed (2006)']
['The Departed (2006)', 'The Prestige (2006)', 'The Town (2010)']

['Hello (2001)', '15 minutes (2001)', '25 Minutes (2002)']
['15 minutes (2001)', 'Hello (2001)', '25 Minutes (2002)']

['15 (1960)', '25 days (1960)']
['15 (1960)', '25 days (1960)']

['Jjjj (2004)', 'Hello (2004)']
['Hello (2004)', 'Jjjj (2004)']

['all gone (2018)', 'Be careful (2018)']
['all gone (2018)', 'Be careful (2018)']

['Be careful (2018)', 'all gone (2018)']
['all gone (2018)', 'Be careful (2018)']

Scoring

This is code-golf , so the shortest code wins!

Python 3, 115 bytes

lambda a:sorted(a[::-1],key=lambda s:(s.split()[-1],-("/"<s[0]<":"),a.index(s)*("/"<s[0]<":"),s[0].lower(),len(s)))

Try it online!

-11 bytes thanks to spec change (thanks Jonathan Allan for pointing it out)
-6 bytes thanks to Lynn


Dimensional Analysis Calculate a product or ratio of SI units.

For example, kg m / s s (kilogram-meter per second squared) should return N (newton).

The input will always be either:

A list of symbols for SI units, space-separated (representing a product) or
The above, /, and the above (representing a ratio).

The input will never contain any other characters (such as numeric literals or other punctuation).

You may assume that this will always equal a single SI unit.

Use the following symbols:

Base quantities:
s               # second
m               # meter
kg              # kilogram
A               # ampere

Derived quantities:
N  = kg m / s s # newton
J  = N m        # joule
W  = J / s      # watt
Hz = W / J      # hertz
Pa = N / m m    # pascal
C  = s A        # coulomb
V  = J / C      # volt
F  = C / V      # farad
Ω  = V / A      # ohm      (you may use the O symbol instead, for a penalty of +3 bytes)
S  = A / V      # siemens
Wb = J / A      # weber
T  = Wb / m m   # tesla
H  = Wb / A     # henry

Examples:

m            => m
N m          => J
J / W        => s
A J / W      => C
T m m        => Wb
N / A m      => T
V s / A      => H
J S / F A    => V
s / s s      => Hz
Hz kg m Hz   => N
Hz s / Ω     => S
Wb / H       => A
V Pa S s / C => Pa
N s / m Hz   => kg
V A          => W
s / Ω        => F
J / A s A    => Ω

Shortest code (in bytes) wins.

CJam, 184 105 98 96 bytes

00000000: 22 73 20 6d 20 6b 67 41 20 4e 20 4a 20 57 20 48  "s m kgA N J W H
00000010: 7a 50 61 43 20 56 20 46 20 ce a9 53 20 57 62 54  zPaC V F ..S WbT
00000020: 20 48 22 32 2f 53 66 2d 22 d6 9c 64 c6 a1 24 a4   H"2/Sf-"..d..$.
00000030: 4b f9 1c 4a 57 f4 61 79 31 ed 82 34 22 33 31 38  K..JW.ay1..4"318
00000040: 62 35 62 32 66 6d 34 2f 6c 53 25 32 24 32 24 65  b5b2fm4/lS%2$2$e
00000050: 72 22 2f 22 61 2f 3a 3a 2e 2b 3a 2e 2d 61 23 3d  r"/"a/::.+:.-a#=

The above is a hexdump; it can be reversed with xxd -r.

Verify all test cases at once in the CJam interpreter. 1

Test run

$ LANG=en_US
$ cjam si.cjam <<< 'Hz s / Ω'; echo
S
$ cjam si.cjam <<< 'J / A s A'; echo
Ω

Idea

We can encode each unit u = sa mb kgc Ad as the vector tu = (a + c - d, b, c, d). 2

This way, for the input u1 … un / v1 … vm, we only have to calculate (tu1 + … + tun) - (tv1 + … + tvm) and check which unit it corresponds to.

Code

"s m kgA N J W HzPaC V F Î©S WbT H"

2/     e# Split the string into chunks of length 2.
Sf-    e# Remove all spaces (if any) from each chunk.

"ÖdÆ¡$¤KùJWôay1í4"

318b   e# Convert from base 318 to integer.
5b     e# Convert from integer to base 5.
2fm    e# Subtract 2 from each base-5 digit.
4/     e# Split into chunks of length 4.
lS%    e# Read one line of input sand split it at spaces.
2$2$   e# Copy the unit names and the vector table.
er     e# Perform transliteration.
"/"a/  e# Split at "/".
::.+   e# Add the vectors of numerator and denominator (if any).
:.-    e# Subtract the resulting sums (or leave a single sum untouched).
a#     e# Find the index of the resulting vector in the vector table.
=      e# Retrieve the corresponding unit.

1 Note that, due to limitations of the online interpreter, I cannot use a different encoding for source code and I/O. Therefore, the symbol Ω shows up as its UTF-8 encoding (Î©). The official Java interpreter does not share this limitation.
2 This saves a few bytes over the straightforward mapping to (a, b, c, d), since it shortens the range of the first coordinate.


Take a ride on the Reading, If you pass Go, collect $200 Monopoly Board

For this code-golf challenge we will be building the board game Monopoly.

Rules:

Take no input.
Output a 11x11 board where each ASCII character forming the board is the first letter of each space of the U.S. version of the Monopoly board.
The characters must be separated by spaces.
Go should start in the bottom right.

The exact string to produce is

F K C I I B A V W M G
N                   P
T                   N
C                   C
S                   P
P                   S
V                   C
S                   P
E                   L
S                   B
J C V C O R I B C M G

Note that from bottom right to bottom left the squares are as follows:

G --> Go
M --> Mediterranean Avenue
C --> Community Chest
B --> Baltic Avenue
I --> Income Tax
...
J --> Jail

Edit
Wow! you guys sure liked this one! :)

Retina, 74 bytes

FKCIIBAVWMGN_PT_NC_CS_PP_SV_CS_PE_LS_BJCVCORIBCMG
S_`(._.)
_
9$*
\B

1

The third to last and last lines should contain a single space.

Try it online!

Explanation

FKCIIBAVWMGN_PT_NC_CS_PP_SV_CS_PE_LS_BJCVCORIBCMG

This replaces the (empty) input with the string on the second line.

S_`(._.)

This is split stage, which splits the string around matches of the regex (._.) (that is, any three characters with a _ in the middle). The reason we put the whole regex in a group is that split stages also return the results of capturing groups. E.g. splitting abcd around bc gives [a, d], but splitting it around b(c) gives [a, c, d]. This way we get all the ._. parts on separate lines but also the 11-character parts at the beginning and end. We use the _ option to omit empty results between the individual ._. matches. The result would be this:

FKCIIBAVWMG
N_P
T_N
C_C
S_P
P_S
V_C
S_P
E_L
S_B
JCVCORIBCMG

Next we process the underscores:

_
9$*

This replaces each underscore with nine 1s. The reason we use 1s here instead of spaces immediately is that it makes it easier to insert the padding spaces next.

\B

Remember that there's a space on the second line. This inserts a space in every position that isn't a word boundary, i.e. everywhere except at the beginning and end of the lines.

1

And finally, we replace all those 1s with spaces as well.


Implement a sorting algorithm with no change. In this task, you have to write a program, that reads a string with a length of up to 1024 characters and prints it out sorted. In order to make an interesting task from a boring one, I set a few restrictions:

You must not change the contents of any variable. A variable can be assigned only once and must not be changed afterwards. For instance, all of the following constructs are forbidden:

int a = 0;
a = 1;

a = 10;
for (a-->0);

string[12] = a

and many more. What is changing a variable and what not is judged by me.

Additionally, you must not use any sorting function or any library function, that must be "imported" somehow. The only library functions, that are allowed to import are those to print out the result and read in the string, if they are not available whithout importing them.

Perl, 89 characters

sub t{return if!@_;my$c=shift;t(grep{$_ lt$c}@_),$c,t(grep{$_ ge$c}@_)}print t split//,<>

This exploits the fact that QuickSort is effectively equivalent to the recurrence relation:

sorted x = () if x is empty, otherwise
           sorted (elements in x less than x[0]) :: x[0] ::
           sorted (elements in x greater than or equal to x[0] except for x[0] itself)

Edit

I originally misread the question and thought I had to sort the input strings, not the characters within a string. Hence my solution grows from 80 to 89 characters.


Shortest binary number in range Given two arbitrarily precise decimal numbers 0 ≤ x < y ≤ 1, compute the shortest (in digits) binary number b such that x ≤ b < y.

Output the binary digits of b after the binary point as an array or a string of zeroes and ones. Note that the empty array means 0.0, by virtue of deleting trailing zeroes. This also makes sure that there is a unique correct answer for any range.

If you are unfamiliar with binary fractional numbers, they work just like decimal numbers:

Base 10   0.625 = 0.6 + 0.02 + 0.005 = 6 x 10^-1  +  2 x 10^-2  +  5 x 10^-3
Base  2   0.101 = 0.1 + 0.00 + 0.001 = 1 x  2^-1  +  0 x  2^-2  +  1 x  2^-3
                                          |             |             |
                                          v             v             v
Base 10                        0.625 =   0.5      +     0       +   0.125

Built-ins that trivialize this problem are disallowed.

Examples:

0.0, 1.0 -> ""
0.1, 1.0 -> "1"
0.5, 0.6 -> "1"
0.4, 0.5 -> "0111"

Shortest code wins.


Who will win a Rock, Paper, Scissors, Lizard, Spock game? There are several questions regarding this game, even a king-of-the-hill contest here. But I think all those challenges and contests need a way to automatically determine the winner of a game. So:

Challenge

Given two inputs in the range ["rock", "paper", "scissors", "lizard", "spock"] representing the selections for player 1 and player 2, determine the winner of the match.

Rules

[Winner] [action]    [loser]
-----------------------------
scissors cut         paper
paper    covers      rock
rock     crushes     lizard
lizard   poisons     spock
spock    smashes     scissors
scissors decapitates lizard
lizard   eats        paper
paper    disproves   spock
spock    vaporizes   rock
rock     crushes     scissors

Restrictions

Input will be a pair of strings in the given range (no other strings can be used). You can use arrays of chars if you want, as long as they represent any of the mentioned values.
You can choose whether to use lowercase, uppercase ("ROCK") or camel case ("Rock") for the input strings, as long as the chosen case is the same for all inputs.
Output will be a trio of values that determine the winner, which can be anything you want as long as the answers are consistent. Example: 1 if the first input wins, 2 if the second input wins, 0 if there is a tie. Or maybe A if the first input wins, B if the second input wins, <empty string> if there is a tie.

Goal

This is code-golf, so may the shortest program/method/function/lambda for each language win!

Tests

[Input 1] [Input 2] [Output: 1/2/0]
-----------------------------------
 rock      paper     2
 rock      scissors  1
 lizard    spock     1
 spock     rock      1
 spock     paper     2
 rock      rock      0

Python 3, 68 50 48 bytes

EDIT: Thanks to 3 tricks from Neil, and 2 from Mr. Xcoder

Each input string has a distinct fourth character, so I'm using that to distinguish them. If you arrange the elements in the cycle (scissors, paper, rock, lizard, spock), then each element beats the element directly after it and the element 3 spots to the right, cyclically. So we subtract the inputs' positions in the cycle. If that number is 0, it's a tie. If it's 1 or 3, it's a win for the first player. In my original solution, the cycle difference would index into the string "210100" to distinguish the results of the game. Neil somehow figured out this can be accomplished without indexing by adding 7 and taking the modulus by 3. Edit: Originally I used the second character to identify the string, but if you use the fourth and reverse the cycle, you get cake. And we could all use more cake.

lambda x,y,z="cake".find:(7+z(y[3])-z(x[3]))%5%3

Try it online!

Older version:

lambda x,y,z="caoip".index:(7+z(y[1])-z(x[1]))%5%3

Try it online!

Original version:

b="caoip"
def r(x,y):return"210100"[(b.index(y[1])-b.index(x[1]))%5]

Try it online!


Happy Fibonacci Day! Background
Today (or Yesterday) is (or was) 11/23 or Fibonacci day! What better way to celebrate than to make a Fibonacci cake?

Examples
3

    ii
i_i_ii_i_i

</>
8

              ii
              ii
              ii
              ii
              ii
              ii
              ii
              ii
            i ii i
            i ii i
            i ii i
            i ii i
            i ii i
          i i ii i i
          i i ii i i
          i i ii i i
        i i i ii i i i
        i i i ii i i i
      i i i i ii i i i i
    i i i i i ii i i i i i
i_i_i_i_i_i_i_ii_i_i_i_i_i_i_i

Challenge
You're not really making a cake, just the candles because I can't ascii-art a cake
To make the cake you must first get the first n Fibonacci numbers sorted ascending. The candle (i)'s height is determined by value of the current Fibonacci number. The candles are separated by an underscore (_).
The cake should be symmetrical. So the candles should then be flipped and concatenated.
Example Construction
Input: 6
First 6 Fibonacci Numbers: 1, 1, 2, 3, 5, 8
Candle heights:

          i
          i
          i
        i i
        i i
      i i i
    i i i i
i i i i i i
-----------
1 1 2 3 5 8

Output would be:
          ii
          ii
          ii
        i ii i
        i ii i
      i i ii i i
    i i i ii i i i
i_i_i_i_i_ii_i_i_i_i_i

Reference Fibonacci Numbers
For reference, here are the first 15 Fibonacci numbers. In this challenge, you'll be starting at 1.
1,1,2,3,5,8,13,21,34,55,89,144,233,377,610


Narcissistic array elements Definition
Narcissistic 1 integers of an array think they are better than their neighbours, because they are strictly higher than their arithmetic mean.
Neighbours are defined as follows:

If the integer is at index 0 (the first), then its neighbours are the last and the second elements of the list.

If the integer is not the first nor the last, then its neighbours are the two immediately adjacent elements.

If the integer is at index -1 (the last), then its neighbours are the second-last and the first elements of the list.

Task
Given an array of integers, your task is to discard the narcissistic ones.

The integers can be positive, negative or zero.

You may assume that the array contains at least three elements.

All standard rules apply. This is code-golf, so the shortest code in bytes wins.

Examples
Consider the array [6, 9, 4, 10, 16, 18, 13]. Then we can built the following table:

Element | Neighbours | Neighbours' Mean | Is Narcissistic?
--------+------------+------------------+-----------------
6       | 13, 9      | 11               | False.
9       | 6, 4       | 5                | True.
4       | 9, 10      | 9.5              | False.
10      | 4, 16      | 10               | False.
16      | 10, 18     | 14               | True.
18      | 16, 13     | 14.5             | True.
13      | 18, 6      | 12               | True.

By filtering the Narcissistic ones out, we are left with [6, 4, 10]. And that's it!
Test Cases

Input -> Output

[5, -8, -9]                         -> [-8, -9]
[8, 8, 8, 8]                        -> [8, 8, 8, 8]
[11, 6, 9, 10]                      -> [6, 10]
[1, 2, 0, 1, 2]                     -> [1, 0, 1]
[6, 9, 4, 10, 16, 18, 13]           -> [6, 4, 10]
[6, -5, 3, -4, 38, 29, 82, -44, 12] -> [-5, -4, 29, -44]

 1 - Narcissist does not mean mathematically Narcissistic.

Jelly, 10 bytes

ṙ2+ṙ-<ḤCx@

Try it online!

Explanation:

ṙ2+ṙ-<ḤCx@
ṙ2         Rotate the original list two elements to the left
  +        Add each element to the respective element of the original list
   ṙ-      Rotate the result one element to the right
     <Ḥ    Check if each element is less than the double of its respective element on the original list
       C   Subtract each 1/0 boolean from 1 (logical NOT in this case)
        x@ Repeat each element of the original list as many times as the respective element of the logical NOT (i.e. keep elements of the original list where the respective element from the result is 1)


SQL select number ranges I found it quite hard to achieve a range of numbers as rows in MySQL.

For example the range 1-5 is achieved by:

SELECT 1
UNION
SELECT 2
UNION
SELECT 3
UNION
SELECT 4
UNION
SELECT 5

will result in:

1
2
3
4
5

for 0-99 I can cross join two 0-9 tables:

CREATE TABLE nums as
SELECT 0 as num
UNION
SELECT 1
UNION
SELECT 2
UNION
SELECT 3
UNION
SELECT 4
UNION
SELECT 5
UNION
SELECT 6
UNION
SELECT 7
UNION
SELECT 8
UNION
SELECT 9
;

Select n.num*10+nums.num v
From nums n cross join nums

I'm tired of writing all these UNIONs and looking for a way to shrink the code.

Any ideas how to golf it (for example 0-1,000,000 range) in MySQL or any SQL syntax ?

Extra points are given for:

single statement
no procedures
no variables
no DDL statements
only DQL statements

For SQL dialects that support recursive CTEs like sqlite, you can do something like the following:

WITH RECURSIVE f(x) AS
(
  SELECT 1 UNION ALL SELECT x + 1 FROM f LIMIT 1000000
)
SELECT x
FROM f;

This doesn't depend on any existing table and you can change the LIMIT clause as desired. I originally saw a variant of this on StackOverflow.


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

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

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

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

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

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


Output a Face on a Numbered Cube Assign the numbers 0 through 7 to the 8 vertices of a cube in any way you want. Exactly one number must be assigned to each vertex.
For example, your vertices might be assigned like this:
  3-----1
 /|    /|
4-----2 |
| |   | |
| 5---|-0
|/    |/
6-----7

Write a program that takes in an integer from 0 to 5. Each of these 6 numbers is associated with exactly one face of your cube in any way you like. When one of these numbers is input, the 4 vertex numbers of the associated face must be printed to stdout in a 2×2 square of digits. The face is to be viewed straight on from outside the cube. All 4 face rotations are valid.
For example, if 0 is associated with the front face of the example cube above, then this would be a valid output for input 0:
42
67

The face may be viewed at any 90° rotation, so these are also valid:
27
46
76
24
64
72
This output (and its rotations) are not valid, as they are viewed from the wrong side of the face:
24
76

The same idea applies to all other faces. e.g. if 1 is associated with the back face, then input 1 might produce output 13[newline]05 (and 31[newline]50 would be invalid).
So the real challenge is choosing your vertex numbers and rotations such that translating the input into its 4 vertex numbers is easy and short.
The shortest code in bytes wins. Tiebreaker is earlier post. (Handy byte counter.)
Notes

You may write a function instead of a program. It should take an integer from 0 to 5 and print or return the 2×2 digit grid string.
Take input from stdin, command line, or function arg. You may assume input is  valid.
The output may optionally have a trailing newline.
Be sure to tell us the vertex and face numbers you chose.

CJam, 23 16 bytes

There's probably an elegant mathematical solution to this problem. But I have no clue how to find one, so super compressed hard coding it is!

I found one! Well, it's not a classically elegant mathematical solution as it uses bitwise operations, but it is entirely formulaic.

li_o1^_p_6|o3+6%

Try it online.

Cube layout

  4-----7          4-----7          3-----2
 /|    /|         /  0  /|         /  3  /|
1-----0 |        1-----0 |        6-----5 |
| |   | |        |     |2|        |     |4|
| 5---|-2        |  1  | 2        |  5  | 7
|/    |/         |     |/         |     |/
6-----3          6-----3          1-----4

Explanation

My old answer already laid out the cube such that each face can be described with its first (top-left) vertex number equal to the face number. But I wanted to be able to calculate more vertex numbers using the face number. At some point, I came up with the idea that got my foot in the door, to calculate the second (top-left) vertex number as the face number XOR 1. And after a while of trial and error, I managed to come up with the layout shown above and the formulas below that allow me to to calculate every vertex number for a face n quite succinctly:

Top-left: n
Top-right: n^1
Bottom-left: (n^1)|6
Bottom-right: ((n^1)+3)%6

For reference, I'll reproduce the output for each face in the desired layout here:

Face:      0     1     2     3     4     5

Vertices:  01    10    23    32    45    54
           74    63    70    65    72    61

So the whole program just comes down to reading the input face number and producing these values in order, albeit with slightly different printing logic for different vertices. Note that, because every vertex after the first starts with a base of n^1, I only need to calculate that once, which compacts the logic even further.

For posterity's sake, and because I think it was still a pretty good approach, here's my old answer.

CJam, 23 bytes

There's probably an elegant mathematical solution to this problem. But I have no clue how to find one, so super compressed hard coding it is!

"pÜ×ñè¨"487b8b3/ri_o=~p

Try it online.

Cube layout

  0-----7          0-----7          3-----6
 /|    /|         /  0  /|         /  3  /|
1-----2 |        1-----2 |        4-----5 |
| |   | |        |     |2|        |     |5|
| 5---|-6        |  1  | 6        |  4  | 7
|/    |/         |     |/         |     |/
4-----3          4-----3          1-----0

Explanation

The basic approach employed is to hard code the vertices for each face in as little space as possible. Similarly to Optimizer's base conversion solution, this treats the vertex list as an octal number packed as ASCII character data. But that's about where the similarities end to make way for further optimizations!

Here are the three key optimizations I made to the "naive" solution:

Lay out the cube such that each face can be described with its face number as the first vertex number. Looking at my cube layout as presented above, one can see that the top-left vertex number of each face is equal to the face number. This allows me to encode six fewer vertices at the cost of having to print the input back, which turns out to save a byte.
Pack the vertex data into a string for which each "character" has a maximum larger than 256. As this maximum increases past 256, the length of the string slowly decreases, but it becomes increasingly likely that any one "character" exceeds 256 and is thus no longer part of the 1-byte ASCII character set. So I wrote a program that tries encoding the vertex data in every base from 256 to 1000, with which I found about 10 bases that save one byte of character data compared to base 256. I chose 487, as that also has the nice property that the resulting string consists entirely of printable ASCII.
Mixed with the first optimization, produce the output asymetrically. The usual approach in CJam would be to format the vertex data as a 2-element list of 2-element lists, insert a newline in the middle, and let the output be implicitly printed. But I instead print the first vertex (equal to the input face number) with an operator that doesn't add a newline, retrieve the 3-element list of the other vertices, grab the next vertex and print it with an operator that does add a newline, and let the other two vertices be implicitly printed. This saves a byte.


Count switches in a smallest square root sequence mod \$2^n\$ Definition

For any \$a\equiv1\ (\text{mod }8)\$ and \$n\ge3\$, there are exactly 4 roots to the equation \$x^2\equiv a\ (\text{mod }2^n)\$. Now, let \$x_k(a)\$ be the smallest root to the equation \$x^2\equiv a\ (\text{mod }2^k)\$, then $$\{x_3(a),x_4(a),x_5(a),x_6(a),\cdots\}$$ is a smallest square root sequence (SSRS) of \$a\$ mod \$2^n\$.

John D. Cook published a quick algorithm that calculates such roots in \$O(n)\$ time. Assume \$x_k\$ is a root to the equation \$x^2\equiv a\ (\text{mod }2^k)\$. Then, $$x_{k+1}=\begin{cases}x_k&\text{if }\frac{x_k^2-a}{2^k}\text{ is even}\\x_k+2^{k-1}&\text{otherwise}\end{cases}$$
is a root to the equation \$x^2\equiv a\ (\text{mod }2^{k+1})\$.

Now we define two lists A and B. \$A=\{A_k|k\ge3\}\$ is the list of values generated by the algorithm above with initial values \$A_3=1\$ and \$B=\{B_k|k\ge3\}\$ is the list of values generated with initial values \$B_3=3\$. Each entry in the SSRS \$x_k(a)\$ takes the smallest value among \$A_k\$ and \$B_k\$. We say a switch in SSRS occurs whenever the choice changes from A to B or from B to A.

To illustrate the definition, take \$a=17\$:

The smallest numbers are highlighted. From the picture there are 13 switches up to mod \$2^{24}\$.

Challenge

Write a function or program, that receives 2 integers \$a,\ k\$ as input (where \$a\equiv1\ (\text{mod }8)\$ and \$k\ge3\$) and output how many switches occur in the SSRS of \$a\$ mod \$2^n\$ up to \$n=k\$.

Sample I/O

1, 3 -> 0
9, 4 -> 1
1, 8 -> 0
9, 16 -> 1
17, 24 -> 13
25, 32 -> 2
33, 40 -> 18
41, 48 -> 17
49, 56 -> 1
1048577, 2048 -> 959
1048585, 2048 -> 970

Winning Condition

This is a code-golf challenge, so shortest valid submission of each language wins. Standard loopholes are forbidden by default.

05AB1E, 15 14 bytes

LoεLnαy%0k}üÊO

Try it online!

For each n, this finds the smallest square root of a by brute-force.

05AB1E, 26 23 bytes (fast)

13v¹yλ£DnIαN>o%2÷+]@γg<

Try it online!

This one properly uses Cook's formula.

13                    # literal 13
  v               ]   # for each digit:
   ¹                  #  push the input k
    y             ]   #  push the digit
     λ£               #  recurse k times with base case y:
       Dn             #   square of the current value
         Iα           #   absolute difference with input a
           N>o%       #   modulo 2**(N+1)
               2÷     #   integer divide by 2
                 +    #   add to the current value
@                     # compare the two lists element-wise
 γ                    # group consecutive equal elements
  g                   # length
   <                  # -1


Do two numbers contain unique factorials? Break two numbers up into their factorials; if they share any, return a falsey value. Otherwise, return a truthy value. (inspired by this recent question)

In other words, write each input number as the sum of factorials (of positive integers) in the greediest possible way; return a truthy value if no factorial appears in both representations, a falsey value otherwise.

Example

Given 20 and 49:

20 = 3! + 3! + 3! + 2!
49 = 4! + 4! + 1!

No factorial appears in both representations, so return a truthy value.

Given 32 and 132:

132 = 5! + 3! + 3!
 32 = 4! + 3! + 2!

3! appears in both representations, so return a falsey value.

I/O

Input and output can be through any standard means.

Input will always be two nonnegative integers; no upper bound on these integers other than what your language requires.

Output should be a truthy or falsey value. These values don't necessarily have to be consistent for different inputs, as long as every output is correctly truthy/falsey.

Test Cases

If one input is 0, the answer will always be truthy. Other truthy test cases:

{6, 3}, {4, 61}, {73, 2}, {12, 1}, {240, 2}, {5, 264}, {2, 91}, {673, 18},
 {3, 12}, {72, 10}, {121, 26}, {127, 746}

If both inputs are odd integers, or if both inputs are the same positive integer, then the output will always be falsey. Other falsey test cases:

{8, 5}, {7, 5}, {27, 47}, {53, 11}, {13, 123}, {75, 77}, {163, 160}, {148, 53},
 {225, 178}, {285, 169}, {39, 51}, {207, 334}, {153, 21}, {390, 128}, {506, 584},
 {626, 370}, {819, 354}

This is code-golf, so fewest bytes wins!

Jelly, 7 bytes

Æ!ṠḄ&/¬

Try it online!

How it works

Æ!ṠḄ&/¬  Main link. Argument: (x, y) (pair of integers)

Æ!       Convert x and y to factorial base.
  Ṡ      Apply the sign function to each digit.
   Ḅ     Unbinary; convert each resulting Boolean array from base 2 to integer.
    &/   Reduce the resulting pair of integers by bitwise AND.
      ¬  Take the logical NOT of the result.


Advent Challenge 5: Move the presents to the transport docks! << Prev Next >>

Thanks to the PPCG community, Santa has managed to remanufacture all of his presents and after the assembly line, the presents are now ready to be moved into the transport docks!

Each of Santa's transport docks only holds a range of present sizes because the transport sleighs are specialized for a specific size (any lighter and it would be wasteful, any heavier and the sleigh wouldn't be able to handle the load). Thus, he needs you to help him take his presents and sort them into the correct transport docks.

Challenge

Given a list and the transport dock ranges, stably organize the presents into the correct order.

Let's take this for example: the presents are [5, 3, 8, 6, 2, 7] and the dock ranges are [[1, 5] and [6, 10]].

The presents 5, 3, and 2 go into the first dock and the presents 8, 6, and 7 go into the second dock. This can be shown as [[5, 3, 2], [8, 6, 7]]. This list will be closer to being sorted than the input, but stably means that within each dock, the order of the presents must be the same as the order of the input (otherwise you could just sort the entire list).

Your final output for this case would be [5, 3, 2, 8, 6, 7] (as a flat list).

Formatting Specifications

You will be given input as a flat list of integers and a list of ranges in any reasonable format (for example, the range for the above case could be given as [[1, 5], [6, 10]], [1, 5, 6, 10], or [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]]). Your output should be a flat list of integers in any reasonable format.

The input can contain duplicate values; in this case, you need to return all instances of them. All present sizes will be in exactly one size range, and you can assume that the ranges will never overlap. There can be gaps in the ranges as long as all present sizes are covered.

Rules

Standard Loopholes Apply
This is code-golf, so the shortest answer in bytes wins
No answer will be accepted
You can assume that there will be no empty ranges ([7, 4] would be invalid because ranges go up)

Test Cases

[1, 2, 3, 4, 5, 6, 7] ; [[1, 3], [4, 7]] => [1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7] ; [[4, 7], [1, 3]] => [4, 5, 6, 7, 1, 2, 3]
[7, 3, 5, 4, 6, 1, 2] ; [[1, 3], [4, 5], [6, 7]] => [3, 1, 2, 5, 4, 7, 6]
[4, 7, 6, 3, 5, 2, 1] ; [[1, 4], [5, 7]] => [4, 3, 2, 1, 7, 6, 5]
[1, 1, 3, 3, 6, 4, 7] ; [[1, 4], [6, 7]] => [1, 1, 3, 3, 4, 6, 7]

Note: I drew inspiration for this challenge series from Advent Of Code. I have no affiliation with this site

You can see a list of all challenges in the series by looking at the 'Linked' section of the first challenge here.


The Add-Multiply-Add Sequence (Related)

Given an integer n > 1,
1) Construct the range of numbers n, n-1, n-2, ... 3, 2, 1 and calculate the sum
2) Take the individual digits of that number and calculate the product
3) Take the individual digits of that number and calculate the sum
4) Repeat steps 2 and 3 until you reach a single digit. That digit is the result.

The first twenty terms of the sequence are below:

3, 6, 0, 5, 2, 7, 9, 2, 7, 9, 1, 9, 0, 0, 9, 6, 7, 0, 0, 6

Note: This sequence is NOT in OEIS.

I/O and Rules

Numbers will get very large quickly, so the solution must be able to handle input numbers up to 100,000 without failure (it's fine if your code can handle past that).
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.

Examples

n     output
1234   9
3005   3
5007   5
9854   8
75849  8
100000 0

Python 2, 77 72 71 62 60 bytes

lambda n:reduce(lambda x,c:eval(c.join(`x`)),'*+'*n,-n*~n/2)

Thanks to @xnor for golfing off 2 bytes!

Try it online!


Prelude Syntax-Checker Prelude is an esoteric programming language, which has very few, but unusual, restrictions on what constitutes a valid program. Any block of printable ASCII text ("block" meaning that lines of printable ASCII are separated by newlines - 0x0A) is valid provided that:

Every (vertical) column of text contains at most one of ( and ).
Ignoring their vertical position, the ( and ) are balanced, that is, each ( is paired with exactly one ) to the right of it, and vice versa.

Write a program or function which, given a string containing printable ASCII and newlines, determines if it constitutes a valid Prelude program. You may take input via STDIN (or closest alternative), command-line argument or function argument. The result may be returned or printed to STDOUT, using any two fixed truthy/falsy values of your choice.

You must not assume that the input is rectangular.

This is code golf, so the shortest submission (in bytes) wins.

Examples

The following are valid Prelude programs (in fact, they're even real Prelude programs):

?1-(v  #1)-
1   0v ^(#    0)(1+0)#)!
    (#)  ^#1-(0 #

1(#  1) v #  - 1+)
    vv (##^v^+
? v-(0 # ^   #)
?
  1+              1-!

And here are a number of inputs, all of which are invalid:

#(#(##)##)##(
)##(##(##)#)#

#(#)
)###

#(##
(##)

(##)
(#)#

(##)
(###

#(#)
(##)

#(#)
###)

#()#
()##

#(#)##
###
###(#)

Python 2, 128 119 105 bytes
def F(p):
 v=n=1
 for r in map(None,*p.split("\n")):A,B=map(r.count,"()");n+=B-A;v*=n<2>A+B
 return n*v>0

Did you know that you can map None in Python 2?
Explanation
We want to start by transposing the Prelude so that columns become rows. Usually we would do this with zip, but since zip truncates to the shortest row length and itertools.zip_longest is far too long for code-golf, it seems like there's no short way to do what we want...
Except for mapping None:
>>> print map(None,*[[1,2,3],[4],[5,6]])
[(1, 4, 5), (2, None, 6), (3, None, None)]

Unfortunately (or rather, fortunately for all non-golf purposes), this only works in Python 2.
As for n and v:

n acts like a stack, counting 1 - <number of unmatched '(' remaining>. For every ( we see we subtract 1, and for every ) we see we add 1. Hence if n >= 2 at any point, then we've seen too many )s and the program is invalid. If n doesn't finish on 1, then we have at least one unmatched ( remaining.
v checks validity, and starts at 1. If the program is ever invalid (n >= 2 or A+B >= 2), then v becomes 0 to mark invalidity.

Hence if the program is valid, then by the end we must have n = 1, v = 1. If the program is invalid, then by the end we must either have v = 0, or v = 1, n <= 0. Therefore validity can be succinctly expressed as n*v>0.
(Thanks to @feersum for a multitude of good suggestions which took off 14 bytes!)
Previous, more readable submission:
def F(p):
 p=map(None,*p.split("\n"));v=n=0
 for r in p:R=r.count;A=R("(");B=R(")");n+=A-B;v|=A+B>1or n<0
 return n<1>v