Create a Roman Numeral calculator Create a basic calculator for Roman numerals.
Requirements

Supports +,-,*,/
Input and output should expect only one subtractor prefix per symbol (i.e. 3 can't be IIV because there are two I's before V)
Handling of the subtraction principle in input and output must at minimum support modern standard conventions, in which only powers of ten are subtracted from larger numbers (e.g. I,X,C are required subtractors but not V,L,D) and subtraction is never done from a number more than 10x the subtractor (e.g. IX must be supported but IC is not required).
Input and output should be left to right in order of value, starting with the largest (i.e. 19 = XIX not IXX, 10 is larger than 9)
Left to right, no operator precedence, as if you were using a hand calculator.
Supports whole positive numbers input/output between 1-4999 (no need for V̅)
No libraries that do roman numeral conversion for you

For you to decide

Case sensitivity
Spaces or no spaces on input
What happens if you get a decimal output. Truncate, no answer, error, etc..
What to do for output that you can't handle. Negatives or numbers to large to be printed.
Whether to support a more liberal use of the subtraction principle than the minimum requirement.

Extra Credit

-50 - Handle up to 99999 or larger. Symbols must include a vinculum

Sample input/output
XIX + LXXX                 (19+80)
XCIX

XCIX + I / L * D + IV      (99+1/50*500+4)
MIV

The shortest code wins.

JavaScript (ES6), 238

c=s=>{X={M:1e3,CM:900,D:500,CD:400,C:100,XC:90,L:50,XL:40,X:10,IX:9,V:5,IV:4,I:1}
n=eval('W='+s.replace(/[\w]+/g,n=>(o=0,n.replace(/[MDLV]|C[MD]?|X[CL]?|I[XV]?/g,d=>o+=X[d]),
o+';W=W')));o='';for(i in X)while(n>=X[i])o+=i,n-=X[i];return o}

Usage:

c("XIX + LXXX")
> "XCIX"
c('XCIX + I / L * D + IV')
> "MIV"

Annotated version:

/**
 * Process basic calculation for roman numerals.
 *
 * @param {String} s The calculation to perform
 * @return {String} The result in roman numerals
 */
c = s => {
  // Create a lookup table.
  X = {
    M: 1e3, CM: 900, D: 500, CD: 400, C: 100, XC: 90,
    L: 50,  XL: 40,  X: 10,  IX: 9,   V: 5,   IV: 4, I: 1
  };
  // Do the calculation.
  //
  // The evaluated string is instrumented to as below:
  //   99+1/50*500+4 -> W=99;W=W+1;W=W/50;W=W*500;W=W+4;W=W
  //                 -> 1004
  n = eval('W=' + s.replace(
    // Match all roman numerals.
    /[\w]+/g,
    // Convert the roman number into an integer.
    n => (
      o = 0,
      n.replace(
        /[MDLV]|C[MD]?|X[CL]?|I[XV]?/g,
        d => o += X[d]
      ),
      // Instrument number to operate left-side operations.
      o + ';W=W'
    )
  ));

  // Convert the result into roman numerals.
  o = '';
  for (i in X)
    while (n >= X[i])
      o += i,
      n -= X[i];

  // Return calculation result.
  return o
}


Count, Replace, Add Up! Definition

Define the nth term of the CRAU sequence as follows.

Begin with the singleton array A = [n].
Do the following n times:

For each integer k in A, replace the entry k with k natural numbers, counting from 1 to k.
Compute the sum of all integers in A.

For example, if n = 3, we start with the list [3].

We replace 3 with 1, 2, 3, yielding [1, 2, 3].

We now replace 1, 2, and 3 with 1, 1, 2 and 1, 2, 3 (resp.), yielding [1, 1, 2, 1, 2, 3].

Finally, we perform the same replacements as in the previous step for all six integers in the array, yielding [1, 1, 1, 2, 1, 1, 2, 1, 2, 3].

The sum of the resulting integers is 15, so this is the third CRAU number.

Task

Write a program of a function that, given a strictly positive integer n as input, computes the nth term of the CRAU sequence.

This is code-golf. May the shortest code in bytes win!

Test cases

 1 ->       1
 2 ->       4
 3 ->      15
 4 ->      56
 5 ->     210
 6 ->     792
 7 ->    3003
 8 ->   11440
 9 ->   43758
10 ->  167960
11 ->  646646
12 -> 2496144
13 -> 9657700

Related

Simplicial polytopic numbers
OEIS A001791: Binomial coefficients C(2n,n-1)

MATL, 5 bytes
EGqXn

Try it online, or verify all test cases!
Explanation:
E       #Double the input
 Gq     #Push "input - 1"
   Xn   #Calculate "nchoosek" on the two numbers


Calculate the bounded cumulative sum of a vector The cumulative sum of a vector is calculated by simply taking the sum of all previous elements. For instance:

vec =     [1  1  1 -1 -1 -1 -1 -1  1  1  1  1 -1]
cum_vec = [1  2  3  2  1  0 -1 -2 -1  0  1  2  1]

Now, impose an upper and a lower limit, meaning that you stop increasing the cumulative sum if it's at the upper limit, and stop decreasing the cumulative sum if it's at the lower limit. A simple example:

upper_lim = 2
lower_lim = -1
vec =     [1  1  1 -1 -1 -1 -1 -1  1  1  1  1 -1]
cum_vec = [1  2  2  1  0 -1 -1 -1  0  1  2  2  1]

The input vector consists of integers, not necessarily only 1 and -1, both positive and negative. Assume that upper_lim >= lower_lim. If the first element of the vector is outside the boundary, jump directly to the boundary (see last example).

Write a function that takes a vector of integers as input, and two integers that represent the upper and lower limits. Output the bounded cumulative vector, as defined above. The input can be as either function arguments or from STDIN.

Standard code golf rules apply.

Examples:

upper_lim = 6
lower_lim = -2
vec =     [1  4  3 -10  3  2  2  5 -4]
cum_vec = [1  5  6  -2  1  3  5  6  2]

upper_lim = 100
lower_lim = -100
vec =     [1  1  1  1  1  1]
cum_vec = [1  2  3  4  5  6]

upper_lim = 5
lower_lim = 0
vec =     [10 -4 -3  2]
cum_vec = [5   1  0  2]

upper_lim = 0
lower_lim = 0
vec =     [3  5 -2  1]
cum_vec = [0  0  0  0]

upper_lim = 10
lower_lim = 5
vec =     [1  4  6]
cum_vec = [5  9 10]
           |
           Note, jumped to 5, because 5 is the lower bound.

CJam, 16 15 bytes

l~f{\T++$1=:T}`

Try it online

This takes the list as first argument, and the pair of upper/lower limit as a second 2-element list. Example input:

[1 4 3 -10 3 2 2 5 -4] [6 -2]

The latest version saves 1 byte by sorting the 3 values, and taking the middle value, instead of using a max and min operation. This was also used in Jakube's solution, as well as suggested by Martin.

Explanation:

l~    Get and parse input. This leaves the value and bounds lists on the stack.
f{    Apply block with value (the bounds list).
  \     Swap new value to top.
  T     Get previous value from variable T (which is default initialized to 0).
  +     Add new value and previous value.
  +     Append new value to bounds list, producing a 3 value list.
  $     Sort it...
  1=    And take the middle value.
  :T    Store in variable T for next iteration.
}     End of apply loop.
`     Convert list to string.


Print the ASCII printable character set Challenge: Print the entire printable ASCII charset (not just a range!) in order.

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

(Of course, replace space with the actual space character.)

Rules: read closely

No other characters allowed in the output.
Program/function does not accept input.
Try not to hardcode/embed the output.
This is code golf, shortest answer wins.

Brainfuck, 30 27 bytes

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

Try it online!

How it works

+ changes the initial cell to 1. After this step, we enter the following, nested loop.

[        While the current cell is non-zero:
  [        While the current cell (C) is non-zero:
    >++      Increment the cell to C's right twice.
    <<+      Increment the cell to C's left.
    >-       Decrement C.
  ]
  >        Advance to the cell to C's right.
]

This computes consecutive powers of 2 until the the value 256 = 0 (mod 256) is reached. When the outer loop finishes, the tape is in the following state.

                                     v
001 002 004 008 016 032 064 128 000 000 000

<<<++ retrocedes three cells and increments twice, leaving the tape as follows.

                         v
001 002 004 008 016 032 066 128 000 000 000

Now we're ready to print the actual output. As a stop condition, we increment the cell above twice each time we print and increment the cell to its left. Since 66 + 95 × 2 = 256 = 0 (mod 256), we stop after printing all 95 printable ASCII characters. We achieve this as follows.

[      While the current cell (C) is non-zero:
  <      Retrocede to the cell to C's left.
  .+     Print its content and increment.
  >++    Increment C twice.
]


Counting valid Binary Sudoku rows Background

Binary Sudoku, also known as Takuzu, Binario, and Tic-Tac-Logic, is a puzzle where the objective is to fill a rectangular grid with two symbols (0s and 1s for this challenge) under the following constraints:

Each row/column cannot have a substring of 000 or 111, i.e. one symbol cannot appear three times in a row, horizontally or vertically.

A row/column of 1 0 0 0 1 1 violates this rule since it contains three copies of 0 in a row.

Each row/column should contain exactly as many 0s as 1s, i.e. the counts of two symbols must be the same.

A row/column of 1 0 1 1 0 1 violates this rule since it has four 1s but only two 0s.
Some examples of rows that meet the first two requirements include:

[1 0 0 1]
[1 1 0 0]
[1 1 0 1 0 0]
[1 1 0 0 1 0 0 1]

(Not relevant to this challenge) The entire grid cannot have two identical rows or columns.

Note that the constraint 2 enforces the grid size to be even in both dimensions.

Here are some examples of completed Binary Sudoku:

(4x4, using 0s and 1s)
1 1 0 0
0 1 1 0
1 0 0 1
0 0 1 1

(6x8, using Os and Xs)
O O X O X O X X
X X O X O X O O
X O X O X X O O
O O X X O O X X
X X O X O O X O
O X O O X X O X

Challenge

Given a positive integer n, calculate the number of distinct valid Binary Sudoku rows of length 2n; that is, the number of permutations of n 0s and n 1s which do not have 000 and 111 as a substring.

The sequence is A177790, leading 1 removed and 1-based.

Test cases

Here are the first 20 terms of this sequence (1-based):

2, 6, 14, 34, 84,
208, 518, 1296, 3254, 8196,
20700, 52404, 132942, 337878, 860142,
2192902, 5598144, 14308378, 36610970, 93770358

Scoring and winning criterion

Standard code-golf rules apply. The shortest submission in bytes wins.

Jelly,  13 12  9 bytes

ŻcṚ$+Ḋ$²S

Try it online! Or see the test-suite.

How?

This code is calculating

$$\sum_{k=\lceil\frac{n}{2}\rceil}^{n}\big(\binom{k}{n-k}+\binom{k+1}{n-(k+1)}\big)^2$$

(where \$k\$ starts at \$0\$ rather than \$\lceil\frac{n}{2}\rceil\$ ...the additional terms are \$0\$ but allows a reversal trick)

ŻcṚ$+Ḋ$²S - Link: integer, n       e.g. 7
Ż         - zero range                  [0,  1,  2,  3,  4,  5,  6,  7]
   $      - last two links as a monad:
  Ṛ       -   reverse                   [7,  6,  5,  4,  3,  2,  1,  0]
 c        -   n-choose-k                [0,  0,  0,  0,  4, 10,  6,  1]
      $   - last two links as a monad:
     Ḋ    -   dequeue                   [0,  0,  0,  4, 10,  6,  1]
    +     -   add                       [0,  0,  0,  4, 14, 16,  7,  1]
       ²  - square                      [0,  0,  0, 16,196,256, 49,  1]
        S - sum                         518


Write a "Hello" interpreter Background
Hello is a language "written" by Anne Veling, which errors if the program does not contain only h, and will print Hello World for every h
Task
You are to write an interpreter/compiler for Hello.
Example in Python
import os
i = input("Program: ")
for a in i:
    if a != 'h':
        print("err")
        quit()
    else:
        print("Hello World")

Details

If the program is not only hs, it must print err or error (case-insensitive)
It's okay if you print "Hello World"s before your program discovers a non-h character and errors, however, the program must halt if a non-h
You may throw an error, as long as you print err/error before throwing, or by using a custom error builtin, like raise SyntaxError('err') in python. (basically, you have to purposefully error with err/error
Assume the program will not be empty
Output can have a trailing newline, space, or nothing to separate Hello Worlds
If a program has multiple lines, it should error (due to \n not being an h)
You can assume that input will always be ASCII 33-126 and 10 (decimal)
The hs are case sensitive (so H is not a valid program)
instruction is found
This is code-golf, shortest answer wins

Test cases
Input:

h

Output:

Hello World

Input:

hhhhhh

Output:

Hello WorldHello WorldHello WorldHello WorldHello WorldHello World

(again, it doesn't matter whether it's spaces, newlines, or nothing to separate `Hello World`s

Input:

rubbish

Output:

err

Input:

huh

Output:

Hello Worlderr

Or

err

First challenge so please have mercy

Lenguage, \$1.42 \times 10^{122}\$ bytes
minus a lot of bytes thanks to Kevin Cruijssen and Bubbler
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh...

This is 142099843608359281286315447494338058415442968773543757980908246691462388164856076679905341690709953072132211450166077106439 hs, which also makes it a valid Hello program, though not one you'd want to run. The original brainfuck code is 140 135 bytes:
,[>-[<-->-----]+<--[>]>[[-->-[>>+>-----<<]<--<---]>-.>>>+.>>..+++.>>.>.<<<.+++.------.<<-.[>]>>>>,>]<]<[[>++<+++++]>-.+++++++++++++..>]

Try it online!
This prints Hello World every time it sees a h through a modification of the shortest known Hello, World! program, stopping the loop and printing err if it sees anything other than a h.


Long multiply, 8 bits at a time You are given a 16-bit machine and told to implement multiplication of arbitrary-sized integers.  Your registers can only hold 16-bit numbers, and the biggest multiply instruction takes two 8-bit inputs and generates a 16-bit result.

Your program must take as input two arbitrary-sized positive numbers and output their product.  Each input number is encoded on its own line as a little-endian byte array where each byte is a 2-digit hex number.  The output must be similarly formatted.  Perhaps best explained with an example:

input

1f 4a 07
63 a3

output

fd 66 03 a7 04

which encodes the multiplication 477727*41827=19981887229.

You can assume that the last (most significant) byte of each input number is nonzero, and the last chunk of the number you output must be nonzero.  Both input numbers will be at most 100 bytes long.

Smallest code wins.

Remember, the biggest multiply you are allowed to use is 1 byte * 1 byte, and no integer types bigger than 2 bytes!

Perl, 137 characters

($x,$y)=<>;while($x=~s/.. *//s){$e=hex$&;$i=0;$s=$r[$i]+=$e*hex,$r[$i]&=255,$r[++$i]+=$s>>8 for$y=~/.. */gs;$y="00$y"}printf'%02x 'x@r,@r

Caveats

Sometimes prints an extra 00 byte at the end of the result. Of course the result is still correct even with that extra byte.
Prints an extra space after the last hex byte in the result.

Explanation

The explanation is going to be a bit long, but I think most people here will find it interesting.

First of all, when I was 10 years old, I was taught the following little trick. You can multiply any two positive numbers with this. I will describe this using the example of 13 × 47. You start by writing the first number, 13, and dividing it by 2 (round down each time) until you reach 1:

13
 6
 3
 1

Now, next to the 13 you write the other number, 47, and keep multiplying it by 2 the same number of times:

13     47
 6     94
 3    188
 1    376

Now you cross out all the lines where the number on the left is even. In this case, this is only the 6. (I can’t do strike-through in code, so I’ll just remove it.) Finally, you add all the remaining numbers on the right:

13     47
 3    188
 1    376
     ----
      611

And this is the right answer. 13 × 47 = 611.

Now, since you are all computer geeks, you will have realised that what we’re actually doing in the left and right columns is x >> 1 and y << 1, respectively. Furthermore, we add the y only if x & 1 == 1. This translates directly into an algorithm, which I’ll write here in pseudocode:

input x, y
result = 0
while x > 0:
    if x & 1 == 1:
        result = result + y
    x = x >> 1
    y = y << 1
print result

We can re-write the if to use a multiplication, and then we can easily change this so that it works on a byte-by-byte basis instead of bit-by-bit:

input x, y
result = 0
while x > 0:
    result = result + (y * (x & 255))
    x = x >> 8
    y = y << 8
print result

This still contains a multiplication with y, which is arbitrary-size, so we need to change that into a loop too. We’ll do that in Perl.

Now translate everything to Perl:

$x and $y are the inputs in hex format, so they have the least significant byte first.
Thus, instead of x >> 8 I do $x =~ s/.. *//s. I need the space+star because the last byte might not have a space on it (could use space+? too). This automatically puts the removed byte (x & 255) into $&.
y << 8 is simply $y = "00$y".
The result is actually a numerical array, @r. At the end, each element of @r contains one byte of the answer, but halfway through the calculation it may contain more than one byte. I’ll prove to you below that each value is never more than two bytes (16 bits) and that the result is always one byte at the end.

So here is the Perl code unravelled and commented:

# Input x and y
($x, $y) = <>;

# Do the equivalent of $& = x & 255, x = x >> 8
while ($x =~ s/.. *//s)
{
    # Let e = x & 255
    $e = hex $&;

    # For every byte in y... (notice this sets $_ to each byte)
    $i = 0;
    for ($y =~ /.. */gs)
    {
        # Do the multiplication of two single-byte values.
        $s = $r[$i] += $e*hex,
        # Truncate the value in $r[$i] to one byte. The rest of it is still in $s
        $r[$i] &= 255,
        # Move to the next array item and add the carry there.
        $r[++$i] += $s >> 8
    }

    # Do the equivalent of y = y << 8
    $y = "00$y"
}

# Output the result in hex format.
printf '%02x ' x @r, @r

Now for the proof that this always outputs bytes, and that the calculation never generates values greater than two bytes. I’ll prove this by induction over the while loop:

The empty @r at the beginning clearly has no values greater than 0xFF in it (because it has no values in it at all). This concludes the base case.
Now, given that @r contains only single bytes at the beginning of each while iteration:

The for loop explicitly &=s all values in the result array with 255 except the last one, so we only need to look at that last one.
We know that we always remove only one byte from $x and $y:

Therefore, $e*hex is a multiplication of two single-byte values, which means it’s in the range 0 — 0xFE01.
By the inductive hypothesis, $r[$i] is one byte; therefore, $s = $r[$i] += $e*hex is in the range 0 — 0xFF00.
Therefore, $s >> 8 is always one byte.

$y grows an extra 00 in each iteration of the while loop:

Therefore, in every iteration of the while loop, the inner for loop runs for one more iteration than it did in the previous while iteration.
Therefore, the $r[++$i] += $s >> 8 in the last iteration of the for loop always adds $s >> 8 to 0, and we already established that $s >> 8 is always one byte.

Therefore, the last value stored in @r at the end of the for loop is also a single byte.

This concludes a wonderful and exciting challenge. Thanks a lot for posting it!


Partition of a positive integer N Find the number of partitions of a positive integer n. Hope someone uses the explicit finite formula for the partition function defined in Jan Hendrik Brunier and Ken Ono paper here.
Sample Input
8
Sample Output
22

N is less than or equal to 1000.
Write the complete program. More than anything I would like to see the different approaches.


Small Ramsey Numbers Background: the Ramsey number \$R(r,s)\$ gives the minimum number of vertices \$v\$ in the complete graph \$K_v\$ such that a red/blue edge coloring of \$K_v\$ has at least one red \$K_r\$ or one blue \$K_s\$. Bounds for larger \$r, s\$ are very difficult to establish.

Your task is to output the number \$R(r,s)\$ for \$1 \le r,s \le 5\$.

Input

Two integers \$r, s\$ with \$1 \le r \le 5\$ and \$1 \le s \le 5 \$.

Output

\$R(r,s)\$ as given in this table:

  s   1    2    3    4      5
r +--------------------------
1 |   1    1    1    1      1
2 |   1    2    3    4      5
3 |   1    3    6    9     14
4 |   1    4    9   18     25
5 |   1    5   14   25  43-48

Note that \$r\$ and \$s\$ are interchangeable: \$R(r,s) = R(s,r)\$.

For \$R(5,5)\$ you may output any integer between \$43\$ and \$48\$, inclusive. At the time of this question being posted these are the best known bounds.


Excludivisible numbers Given an integer N, output the Nth positive number K with the following property in decimal base:

For each digit I at position P of K, the number formed from K by removing the Pth digit (i.e. I) is divisible by I.

Example and remarks

324 is such a number:

3 divides 24
2 divides 34
4 divides 32

Note 1: we assume that the empty number is divisible by anything, like 0. Therefore 1, 2, 3, 4, 5, 6, 7, 8 and 9 are valid.

Note 2: K cannot contain the digit 0, since you cannot divide by 0.

Inputs and outputs

You may take the input as a function argument, through STDIN, etc.
You may return the output from a function, through STDOUT, etc.
You may index those numbers starting from 0 (in which case N >= 0) or from 1 (in which case N > 0), whichever suits you more.

Test cases

Those examples are indexed from 0, so if you indexed from 1, then add 1 to the numbers in the N column.

N    Output
0    1
4    5
8    9
15   77
16   88
23   155
42   742
47   1113
121  4244
144  6888
164  9999

Scoring

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

Jelly, 21 19 bytes

DLR©œ^€®ịDḌḍ@DPȧµ#Ṫ

Input is 1-indexed. Try it online!

How it works

DLR©œ^€®ịDḌḍ@DPȧµ#Ṫ  Main link. No arguments.

                µ    Convert the chain to the left into a link.
                 #   Read n from STDIN and execute the link to the left for
                     k = 0, 1, 2, ... until n value return a truthy value.
D                      Convert D to base 10 (digit array).
 LR                    Construct the range from 1 to the length of the digit array.
   ©                   Copy the range to the register.
       ®               Yield the value of the register.
    œ^€                Take the multiset difference of each element of the range
                       and the range itself.
        ịD             Index into the digit array.
          Ḍ            Convert each list of digits to integer.
                       This yields all numbers with one suppressed digit.
           ḍ@D         Test each of these numbers for divisibility by the
                       suppressed digit from the digit array.
              P        Take the product of the resulting Booleans.
               ȧ       Logical AND with k (k would return 1).
                  Ṫ  Tail; extract the last (nth) element.


Does this Foo machine halt? Determining whether a Turing machine halts is well known to be undecidable, but that's not necessarily true for simpler machines.

A Foo machine is a machine with a finite tape, where each cell on the tape has an integer or the halt symbol h, e.g.

2 h 1 -1

The instruction pointer starts by pointing to the first cell:

2 h 1 -1
^

At every step, the instruction pointer moves forward by the number it points to, then negates that number. So, after one step, it would move forward 2 cells, and turn the 2 into a -2:

-2 h 1 -1
     ^

The Foo machine keeps doing this until the instruction pointer is pointing to the halt symbol (h). So, here is the full execution of this program:

2 h 1 -1
^

-2 h 1 -1
     ^

-2 h -1 -1
         ^

-2 h -1 1
      ^

-2 h 1 1
   ^

The tape is also circular, so if the instruction pointer moves off of one side of the tape, it goes to the other side, e.g.:

3 h 1 3
^
-3 h 1 3
       ^
-3 h 1 -3
     ^
-3 h -1 -3
         ^
-3 h -1 3
 ^
3 h -1 3
  ^

One interesting thing about these Foo machines is that some do not halt, e.g.:

1 2 h 2
^
-1 2 h 2
   ^
-1 -2 h 2
        ^
-1 -2 h -2
    ^
-1 2 h -2
        ^
-1 2 h 2
   ^

This program will continue looping in those last four states forever.

So, write a program which determines if a Foo machine halts or not! You can use any (reasonable) input format you like for the Foo machines, and you can choose to use 0 as the halt symbol. You can use any two distinct outputs for the case where it does halt and the case where it doesn't. Your program must, of course, output an answer in a finite amount of time for all valid inputs.

This is code-golf, so try to make your program as short as possible!

Test cases

2 h 1 -1
Halts
3 h 1 3
Halts
h
Halts
1 1 1 1 h
Halts
2 1 3 2 1 2 h
Halts
3 2 1 1 4 h
Halts
1 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 h -20 -21 -22 -23 -24 -25 -26 -27 -28 -29 -30 -31 -32 -33 -34 -35 -36
Halts

2 h
Does not halt
1 2 h 2
Does not halt
8 1 2 3 3 4 8 4 3 2 h
Does not halt
1 2 4 3 h 2 4 5 3
Does not halt
3 1 h 3 1 1
Does not halt
1 2 h 42
Does not halt

C# (Visual C# Interactive Compiler), 71 bytes

x=>{for(int i=0,k=0,f=x.Count;i++<1<<f;k%=f)k-=(x[k]*=-1)%f-f;i/=x[k];}

Try it online!

I don't know if the following is valid, since it requires a custom delegate with a signature of unsafe delegate System.Action<int> D(int* a);
 and has to be wrapped in an unsafe block to be used, but here it is anyways:

C# (.NET Core), 64 bytes

x=>f=>{for(int i=0,k=0;i++<1<<f;k%=f)k-=(x[k]*=-1)%f-f;k/=x[k];}

Try it online!

This function takes in an int* and returns a Action; in other words, it is a curried function. The only reason I use pointers is because of codegolf.meta.stackexchange.com/a/13262/84206, which allows me to save bytes by already having a variable already defined with the length of the array.

Saved 9 bytes thanks to @someone


Shape Identifying Program Your task is to build a program that identifies the shape of the input. The shapes to be identified can be any of the following:

Square

To be identified as a square, the source must have lines of all equal length, and the same number of lines as characters per line (newline characters excluded). An optional trailing newline is acceptable.

$_='
$_="
$_"'
;say

Rectangle

To be identified as a rectangle, the source must have lines of all equal length, but the number of lines does not match the number of characters per line (newline characters excluded). An optional trailing newline is acceptable. This can be either horizontal or vertical.

$_=
"no
t a
squ
are
";#

$_="but it
is still a
consistent
shape!";##

Triangle

To be identified as a triangle, the source must either start with one character, and each subsequent line must have one additional character (including the last), or after the first line, each subsequent line should have one character fewer until the last, which has only one.

$
_=
"So
this
"."".
shape;

$_="or
even,
this
way
!!
"

Mess

Anything that doesn't follow a consistent format as per the above, must be identified as a mess.

Rules

You may return any four consistent printable values to identify each shape.
Your source code must also adhere to one of the above shapes (no, not a mess).
A single trailing newline in your source is acceptable.
You can assume input does not contain any blank lines (including trailing newlines), is not empty, and does not consist only of newlines.
All shapes must have a height and width of >= 2, otherwise this is defined as a mess.
Standard loopholes are forbidden.
The shortest solution in bytes, in each language, wins.

Jelly, 35 bytes

L€ṀR,Ṛ$ċƲȧ3
L€,;¥LE€S+Ç
ỴµZL«L>1ȧÇ

Try it online!

0 = Mess
1 = Rectangle
2 = Square
3 = Triangle


Create a universal two-dimensional cellular automaton cell using two-way universal logic processors In Conway's Game of Life, a cell is in a state of either on or off, depending on the on-and-off state of the eight cells surrounding it.

We can simulate this using a logic gate network with some sort of clock signal that updates every cell all at once. Your task in this problem is to build the logic gate network for a single cell that will update the new state of the cell given the state of its neighbours.

This cell is a logic gate network that takes eight neighbour-cell inputs N1, N2, ..., N8, the current on/off state of its own cell L, and 18 "rule" inputs B0, B1, B2, ..., B8 and S0, S1, S2, ..., S8, and evaluates a new L value (to an output L') as follows:

if L is currently 0 and Bn is on where n is the number of N1, N2, ..., N8 that are currently set at 1, then L' is set to 1. Otherwise, it stays 0.
if L is currently 1 and Sn is off where n is the number of N1, N2, ..., N8 that are currently set at 1, then L' is set to 0. Otherwise, it stays 1.

In the example of Conway's Game of Life, B3, S3, and S2 are on, while the rest of them are all off.

Unlike my previous logic gate tasks, for this task you may use any two-input logic gates you want, not just NAND gates. This includes exotic gates such as if A then B, A or not B, or simply A, a gate that takes two inputs and always returns the first one (although I'm not sure why you'd want to use that one, you are allowed to). You are allowed unlimited constants, splits, and ground wires.

The network to use the fewest logic gates to achieve this wins.

114 107 gates

A diagram of the setup, with example inputs (link to full-sized image):

Created in Logisim

This uses a simple approach; first it counts the number of live neighbouring cells, and then checks if that number fulfills a birth/survival condition.


Sudoku board generator A program that randomly generates a Sudoku game board with varying degrees of difficulty (however you decide to measure difficulty). Sudoku requires that there is only one solution, so your program should too. Input and output can be any form or method of your choosing.

Judging

Fastest code. Tested on a quad-code Windows 7 machine with freely or easily available compiler. Provide link if necessary.

Scheme

Why should I be constrained on the platform used? Especially on such a developer-unfriendly platform as Windows! Anyways... doesn't matter since this code compiles on all Scheme implementations that provide the standard libraries srfi-1, srfi-27 and srfi-43 (that means almost all of them), on virtually (pun intended) every platform. The only non-portable-across-all-implementatons construct I use is "import", but I might as well have used "use" or "require" among others. This minor incompatibility between implementations will be fixed this year, don't worry.

Because of the holy wars pertaining to the Lisp family of languages on the matters of minimalism, the last standard in final status (R6RS) was rejected by most implementors, prefering instead to stick to R5RS until the steering comitee broke up. They came up with the idea to split the language in two, the first being a minimalistic core (assigned to working group 1). The second will be a superset of the first which will better suit daily usage. Both will form R7RS, which will be released this year. This will solve many incompatibilities between implementations.

;; Sudoku generator (v0.2)

;; list ops          randomness     vector ops
(import srfi-1) (import srfi-27) (import srfi-43)

(define rand (random-source-make-integers
                 default-random-source))

(define (shuffle! vec)
  (let swap! ([n (vector-length vec)])
    (let* ([i (rand n)] [n (- n 1)])
      (when (> n 1) (vector-swap! vec n i) (swap! n)))))

(define (make-row)
  (let ([row (vector-unfold (lambda (i) (+ i 1)) 9)])
    (shuffle! row) row))

(define (make-rows)
  (let f ([i 8] [r (make-row)])
    (cons r
      (if (zero? i) (list)
          (f (- i 1) (vector-copy r 1 10 (vector-ref r 0)))))))

(define (split-in ls n)
  (let ([n (quotient (length ls) n)])
    (let f ([ls ls])
      (if (null? ls) ls (cons (take ls n) (f (drop ls n)))))))

(define (make-grid)
  (let ([g (list->vector
              (map list->vector
              (zip (split-in (make-rows) 3))))])
    (shuffle! g) (vector-for-each shuffle! g)
    (vector-concatenate (vector->list g))))

Difficulty: none

I felt the code was too complicated so I rewrote it from scratch. For clue pruning, I am currently working on encoding the board in CNF notation. Since I have access to the original grid, testing for uniqueness is easier. Pruning is done by priority (we prefer to prune cells who maximize the number of possibilities in its surroundings).

So far, this only generates a valid complete grid using only a vector of numbers from 1 to 9 that swaps each index with a random index. This random row is used to derive the other rows by successive rotation. This works because there are only 8 other possible rows, given one sudoku row.

Thus, so far we have ensured there are no row or column conflicts possible. As a matter of fact, the sudoku is based on latin squares which are roman grids of size n*n (a square) which must have unique numbers on every row and column in the range 1 to n. A sudoku is a latin square of size 9*9, with an added constraint: regions.

The next step is to split the list of rows in 3, which now looks like this, given an initial row of (1 2 3 4 5 6 7 8 9):

;; this is a latin square
(((1 2 3 4 5 6 7 8 9)
  (2 3 4 5 6 7 8 9 1)
  (3 4 5 6 7 8 9 1 2))
 ((4 5 6 7 8 9 1 2 3)
  (5 6 7 8 9 1 2 3 4)
  (6 7 8 9 1 2 3 4 5))
 ((7 8 9 1 2 3 4 5 6)
  (8 9 1 2 3 4 5 6 7)
  (9 1 2 3 4 5 6 7 8)))

Given a grid like that, I can "zip" the lists (perform matrix transposition) so that it now looks like this:

;; this is now a sudoku
(((1 2 3 4 5 6 7 8 9)
  (4 5 6 7 8 9 1 2 3)
  (7 8 9 1 2 3 4 5 6))
 ((2 3 4 5 6 7 8 9 1)
  (5 6 7 8 9 1 2 3 4)
  (8 9 1 2 3 4 5 6 7))
 ((3 4 5 6 7 8 9 1 2)
  (6 7 8 9 1 2 3 4 5)
  (9 1 2 3 4 5 6 7 8)))

Magic! No row, column or region conflicts! What needs to be done next is to shuffle the three lists of rows, and the three rows within them. To do that, we convert all lists to vectors, then reuse the same shuffle procedure used with the first row. The last step is to collapse everything back to a grid of 9 rows.

I will post updates later. I am currently more advanced than this, but the rest is still in development (I promise you the cleverness and simplicity of my algorithms will surprise you). This was not done in one day, but with great amounts of research for optimal algorithms.


Reverse Deltas of an Array A continuation of Inverse Deltas of an Array
Your task is to take an array of signed 32 bit integers, recompile it with its deltas reversed.
Example
The List,
18  19  17  20  16

has the deltas:
   1  -2   3  -4

which, when reversed, yields:
  -4   3  -2   1

then when recompiled, using yields:
18  14  17  15  16

which should be your return value.
Recompiling consists of taking the C, which is the first value of the array. In this case, 18, and applying the deltas to it in order.
So 18 + -4 gives 14, 14 + 3 gives 17, and so on.
Input/Output
You will be given a list/array/table/tuple/stack/etc. of signed integers as input through any standard input method.
You must output the modified data once again in any acceptable form, following the above delta reversing method.
You will receive N inputs where 0 < N < 10 where each number falls within the range -1000 < X < 1000
Test Cases
1 2 3 4 5      -> 1 2 3 4 5
18 19 17 20 16 -> 18 14 17 15 16
5 9 1 3 8 7 8  -> 5 6 5 10 12 4 8
6 5 4 1 2 3    -> 6 7 8 5 4 3

Notes

As stated in above, you will always receive at least 1 input, and no more than 9.
The first and last number of your output, will always match that of the input.
Only Standard Input Output is accepted
Standard loopholes apply
This is code-golf, so the lowest byte-count wins!
Have fun!

And the winner is...
Dennis! Who firstly took the first place, then beat himself with a shorter solution, giving himself both the first and second place!
Honorable mention to ais523 with their Jelly, that if not for Dennis getting in just before them, would have held the second place.

Jelly, 6 bytes

I;ḢṚ+\

Try it online!

How it works

I;ḢṚ+\  Main link. Argument: A (array)

I       Increments; compute the deltas of A.
  Ḣ     Head; yield the first element of A.
 ;      Concatenate the results to both sides.
   Ṛ    Reverse the resulting array.
    +\  Compute the cumulative sum of the reversed array.


Golfing Advent of Code 2020, Day 3 I thought it'd be interesting to turn AoC day 3 puzzle into a Golfing Challenge, so here it is.
Task
Find the number of # you'd encounter in an 11x11 grid (consisting of # and .) that repeats itself (to the right side), starting at the top left corner, which is always a .. You will need to check the position that is \$x\$ right, \$y\$ down, then the position that is \$x\$ right, \$y\$ down from there and so on until you reach one of the bottom # or ..
Input
Two arguments:

3,1

..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#

means that you should traverse the grid going 3 right and 1 down. The output should be 7 (see the example in the AoC link above).
Without changing the grid but only the positions, here are some example inputs and outputs:

\$x=1, y=1 \to 2\$.
\$x=5, y=1 \to 3\$.
\$x=7, y=1 \to 4\$.
\$x=1, y=2 \to 2\$.

1,1

.........##
.#.#.......
#.......#..
.........#.
.....#.....
...##...#..
#.#..#....#
........##.
......#....
...####...#
.........#.

means traversing the grid going 1 right, 1 down each time. You'd encounter only 1 # in this example, so the output should be 1.
Rules

\$x\$ (right) and \$y\$ (down) will be positive integers, where \$y < 3\$ (no limits for \$x\$).
The grid can be repeated unlimited times.
You can replace . and # with whatever you like in the grid (e.g. 0/1). Just mention which corresponds to which.
You can receive input through any of the standard IO methods.
This is code-golf, so shortest code in bytes wins!

J, 30 26 23 22 bytes
0{0{[:+/|.^:(<@%&{.~$)

Try it online!
Note: This solution works for any grid
J supports multi-dimensional rotation, which reduces the problem almost to a single summation.  To clarify what's happening, assume the board looks like this:
 0  1  2  3  4
 5  6  7  8  9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
25 26 27 28 29
30 31 32 33 34
35 36 37 38 39

Now we rotate the columns left and the rows up |. by 1 3, iteratively, 3 times:
┌──────────────┬──────────────┬──────────────┐
│ 0  1  2  3  4│ 8  9  5  6  7│11 12 13 14 10│
│ 5  6  7  8  9│13 14 10 11 12│16 17 18 19 15│
│10 11 12 13 14│18 19 15 16 17│21 22 23 24 20│
│15 16 17 18 19│23 24 20 21 22│26 27 28 29 25│
│20 21 22 23 24│28 29 25 26 27│31 32 33 34 30│
│25 26 27 28 29│33 34 30 31 32│36 37 38 39 35│
│30 31 32 33 34│38 39 35 36 37│ 1  2  3  4  0│
│35 36 37 38 39│ 3  4  0  1  2│ 6  7  8  9  5│
└──────────────┴──────────────┴──────────────┘

We are bringing the sled's "new position" to the top-left corner every time, rather than moving a pointer within a fixed grid and adjusting indexes with modular arithmetic.
Once we have every iteration like this, we need only "sum the planes" element-wise [:+/, and then our answer will the number in the top left corner of the resulting matrix 0{0{.
The only piece left is to determine how many times we need to iterate.  This amounts to dividing the first element of our "step" vector (the down part) into the height of the input matrix: %&{.~$.
old approach, 26 bytes
1#.]{~[:;/$@]|"1#\@]*($~#)

Try it online!


Generate Aheui Number Make a Number Expression is related : actually, it is also about Aheui. But it just made number expression, but this made real Aheui code.

Aheui is esolang written in only Korean character. Because of its nature, Aheui can't use Arabic numbers.

But, of course, there is way to generate number.

Brief introduction to Aheui

Reading the link above is best, but put it shortly : Aheui is befunge-like esolang : have cursor, every character is instructor, and using stack.

One instructor, looks like 박, have three part : Initial consonantㅂ, vowelㅏ, final consonantㄱ.

First part, initial consonant, determine what to do.

Here is table of initial consonant that can be useful here:

ㅇ : no operation.
ㅎ : terminate.
ㄷ : pop two number from current stack, than add them, and push to current stack.
ㄸ : same as ㄷ, but multiply instead of add.
ㄴ : pop two number from current stack, push second // first to current stack.
ㅌ : same as ㄴ, but subtract instead of divide.
ㄹ : same as ㄴ, but modulo instead of divide.
ㅂ : push number to current stack. Number is given by final consonant.
ㅃ : duplicate top of current stack.
ㅍ : swap top two value of current stack.

Second part, vowel, determine momentum. Maybe you just need ㅏ, go to next.

Last part, final consonant, determine number to used in ㅂ commend.

Here is list of final consonant and number.

Nothing
ㄱ, ㄴ, ㅅ
ㄷ, ㅈ, ㅋ
ㅁ, ㅂ, ㅊ, ㅌ, ㅋ, ㄲ, ㄳ, ㅆ
ㄹ, ㄵ, ㄶ
ㅄ
ㄺ, ㄽ
ㅀ
ㄻ, ㄼ

Finally, 망 is printing operator. Your code have to print 망희 or 망하 or whatever after calculation, to print and terminate the program.

Korean Character

Every Aheui instructor is Korean character.

As I mentioned above, Korean character has three part : Initial consonant(choseong or 초성), Vowel(jungseong or 중성), Final consonant(jongseong or 종성).

Every character has initial consonant and vowel, but final consonant is option.

Korean character in Unicode is from AC00(가) to D7A3(힣).

For composing Korean character, look at this webpage for help.

Question

Input is an positive integer. Generate aheui code that prints given integer, without hardcode every possibility.

You can test your Aheui code at try it online.

Examples

Input | Output | Discription
1 | 반밧나망희 | Put two 2s in stack, divide, print, and halt.
1 | 반반나망희 | Same as above.
1 | 밪반타망희 | Put 3 then 2 in stack, subtract, print, and halt.
3 | 받망희 | Put 3 in stack, print, halt.
3 | 반밧나빠빠다다망희 | Put two 2s in stack, divide, duplicate two times, add two times, print, halt. This is OK, but won't get good point.
72 | 밢밣따망희 | Put 8 and 9 in stack, multiply, print, and halt.
10 | 박밙따망희 | Put 2 and 5 in stack, multiply, print, and halt.

Scoring

Average length of 101 Aheui codes that prints 100 to 200. If score is same, shorter code wins.

Wolfram Language (Mathematica), score 849/101 = 8.406

g@n_:=f@n<>"망히"
f@n_:=f@n=Switch[n,-1,"밯",1,"반반나",9,"밞",8,"밣",7,"밝",6,"밦",5,"발",4,"밗",3,"받",2,"박",
_,mn@{m@n,a@n,s@n}]
m@n_:=m@n=f@#<>If[# #==n,"빠",f[n/#]]<>"따"&/@Select[Divisors@n,1<# #<=n&]//mn
a@n_:=a@n=f@#<>f[n-#]<>"다"&/@Range[⌈n/2⌉-1]//mn
s@n_:=s@n=m[n+#]<>f@#<>"타"&/@Range[n-1]//mn
mn=First@*MinimalBy[StringLength[""<>#]&]

Try it online!

Builds numbers with 다 (+) 따 (*) 타 (-), and 빠 (duplicate), in addition to literals for 2..9. Doesn't actually make use of 밯=-1.

Paste the tio output (Unicode character codes) into Mathematica to see the result:

100 -> 밗발빠따따망히
101 -> 박밞박밞다따다망히
102 -> 밦밣밞다따망히
103 -> 받밗발빠따따다망히
104 -> 밣밗밞다따망히
105 -> 받발밝따따망히
106 -> 박밗밝빠따다따망히
107 -> 박받발밝따따다망히
108 -> 박밦밞따따망히
109 -> 밗받발밝따따다망히
110 -> 박발박밞다따따망히
111 -> 받박발밝따다따망히
112 -> 박밝밣따따망히
113 -> 발박밦밞따따다망히
114 -> 박받밦밞따다따망히
115 -> 발박받밝따다따망히
116 -> 박박밝밣따다따망히
117 -> 밞밗밞다따망히
118 -> 박받밝밣따다따망히
119 -> 밝밣밞다따망히
120 -> 받발밣따따망히
121 -> 박밞다빠따망히
122 -> 박발밝밣따다따망히
123 -> 받발밗밞따다따망히
124 -> 박밦밝밣따다따망히
125 -> 발발빠따따망히
126 -> 박밝밞따따망히
127 -> 박발발빠따따다망히
128 -> 박밣빠따따망히
129 -> 받받발밣따다따망히
130 -> 박발밗밞다따따망히
131 -> 받박밣빠따따다망히
132 -> 박밦박밞다따따망히
133 -> 밝박밣밞다다따망히
134 -> 박받밣빠따다따망히
135 -> 받발밞따따망히
136 -> 밣밣밞다따망히
137 -> 박받발밞따따다망히
138 -> 박발밣빠따다따망히
139 -> 받밣밣밞다따다망히
140 -> 밗발밝따따망히
141 -> 받박발밞따다따망히
142 -> 박밝밣빠따다따망히
143 -> 박밞다밗밞다따망히
144 -> 박밣밞따따망히
145 -> 발박받밞따다따망히
146 -> 박밞밣빠따다따망히
147 -> 받밝빠따따망히
148 -> 박박밣밞따다따망히
149 -> 박받밝빠따따다망히
150 -> 발발밦따따망히
151 -> 밗받밝빠따따다망히
152 -> 박밗밣밞따다따망히
153 -> 밞밣밞다따망히
154 -> 박밝박밞다따따망히
155 -> 발받밗밝따다따망히
156 -> 박밦밗밞다따따망히
157 -> 밗밞밣밞다따다망히
158 -> 박밝밣밞따다따망히
159 -> 받밗밝빠따다따망히
160 -> 밗발밣따따망히
161 -> 밝박받밝따다따망히
162 -> 박밞빠따따망히
163 -> 받밗발밣따따다망히
164 -> 밗발밗밞따다따망히
165 -> 받발박밞다따따망히
166 -> 박박밞빠따다따망히
167 -> 발박밞빠따따다망히
168 -> 받밝밣따따망히
169 -> 밗밞다빠따망히
170 -> 박발밣밞다따따망히
171 -> 받받밦밞따다따망히
172 -> 박발밞빠따다따망히
173 -> 밗밗밞다빠따다망히
174 -> 박밦밞빠따다따망히
175 -> 발발밝따따망히
176 -> 박밣박밞다따따망히
177 -> 받받밝밣따다따망히
178 -> 박밣밞빠따다따망히
179 -> 밗발발밝따따다망히
180 -> 밗발밞따따망히
181 -> 밦발발밝따따다망히
182 -> 박밝밗밞다따따망히
183 -> 받발밝밣따다따망히
184 -> 밗밗밦밝따다따망히
185 -> 발박발밝따다따망히
186 -> 받밦밝밣따다따망히
187 -> 박밞다밣밞다따망히
188 -> 밗박발밞따다따망히
189 -> 받밝밞따따망히
190 -> 발박밗밞따다따망히
191 -> 박받밝밞따따다망히
192 -> 받밣빠따따망히
193 -> 밗받밝밞따따다망히
194 -> 박받밣빠따따다망히
195 -> 받발밗밞다따따망히
196 -> 밗밝빠따따망히
197 -> 발받밣빠따따다망히
198 -> 박밞박밞다따따망히
199 -> 받밗밝빠따따다망히
200 -> 발발밣따따망히

The lowest number that improves with 타 is 211, with 받밣밞따따발타 (3*8*9-5) beating out 발밠밝따따반반나다 (5*6*7+2/2).

The next lowest, 239 (받밞빠따따밗타=3*9*9-4), didn't require 반반나 in its 다/따-only construction (받밣밞따밝다따박다=3*(8*9+7)+2).

An earlier version of this program generated 다/따-only constructions.

With 밯=-1 (score unchanged)

g@n_:=f@n<>"망히"
f@n_:=f@n=Switch[n,1,"밯",9,"밞",8,"밣",7,"밝",6,"밦",5,"발",4,"밗",3,"받",2,"박",
_,mn@{m@n,a@n,s@n}]
m@n_:=m@n=f@#<>If[# #==n,"빠",f[n/#]]<>"따"&/@Select[Divisors@n,1<# #<=n&]//mn
a@n_:=a@n=f@#<>f[n-#]<>If[#==1,"타","다"]&/@Range[⌈n/2⌉-1]//mn
s@n_:=s@n=m[n+#]<>f@#<>If[#==1,"다","타"]&/@Range[n-1]//mn
mn=First@*MinimalBy[StringLength[""<>#]&]

Try it online!

If the program is given no input, 밯 (read a character from input) returns -1, which allows for a one-character 1 literal.

The lowest number that benefits from this is 269, which improves to 발밦밞따따밯다 (5*6*9+(-1)) from 박받밣밞빠따다따다 (2+3*(8+9*9)).


Two Diehards Make a Glider In Conway's Game of Life, there is an infinite square grid of cells, each of which is alive or dead. The pattern changes each "generation". A dead cell with exactly 3 live neighbors (orthogonal or diagonal) becomes a live cell. A live cell only lives to the next generation if it has 2 or 3 live neighbors. These simple rules lead to very complex behaviors. The most well-known pattern is the glider, a pattern that moves diagonally one cell every 4 generations and looks like this:

The Challenge
Your task is to create two patterns which will eventually result in an empty board when by themselves (a.k.a. a diehard), but when combined in a certain non-bordering and non-overlapping arrangement, eventually spawn a single glider and nothing else.
Rules and Scoring

Each of the lone diehards must fit all live cells within a 100x100 cell box and may not contain more than 100 live cells.
The combination glider synthesizer must contain both diehards such that their bounding boxes surrounding all live cells are separated by at least one dead cell.
It does not matter which direction the single glider is facing
Your score is the sum of the number of generations it takes to reach an empty board from the initial states for the diehards, plus the number of generations it takes to reach a state where there is exactly one glider and nothing else (i.e. there are exactly 5 live cells on the board in a glider pattern) for the combined glider synthesizer. Highest score wins.

Total Score 669 683 753
Pattern 1 (379 steps):
x = 100, y = 94
97b2o$96bo2bo$97bobo$98bo$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$3o$2bo$bo!

Pattern 2 (126 steps):
x = 11, y = 2
o5b2obo$3bo$2b2o2bo2b2o!

Pattern 1 + Pattern 2 (248 steps):
x = 112, y = 94
97b2o$96bo2bo$97bobo$98bo2bo5b2obo$104bo$103b2o2bo2b2o$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$3o$2bo$bo!

Pattern 1 is a self-destructing glider + loaf combination where the glider and loaf are spaced as far apart as possible.
Pattern 2 is the result of searching for random disappearing patterns which can be placed next to pattern 1 to destroy the loaf, giving a valid solution to the puzzle. I generated a large number and took the one with the best score.
I'm sure its possible to do better by adding an independent diehard to the far corner of pattern 2 (or even pattern 1), but I'm done for now.


Output the Partial Products In long multiplication, after multiplying the numbers, you are left with the partial products, in this challenge you will output those partial products.

Because long multiplication is long, to compensate your code will need to be as short as possible.

Examples

34, 53
102, 1700

48, 38
384, 1440

361, 674
1444, 25270, 216600

0, 0
0

1, 8
8

Specifications

Input / Output may be in any reasonable format such as array, comma-separated string (or any other delimiter that's not a digit), list, function arguments, etc.
Partial products must be in increasing order.
If a partial product is 0, you can choose whether you want to output it or not.

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

Pyth, 12 bytes

.e**Qsb^Tk_w

Test suite

Takes input newline separated, e.g.

361
674

Explanation:

.e**Qsb^Tk_w
                Implicit: Q = eval(input()),T = 10
           w    Input the second number as a string.
          _     Reverse it.
.e              Enumerated map, where b is the character and k is the index.
     sb         Convert the character to an int.
   *Q           Multiply by Q.
  *    ^Tk      Multiply by T ^ k. (10 ^ index)


Where is the Arrow Pointing? Where is the Arrow Pointing?

In this challenge, your goal is to follow an arrow and output the character it is pointing to.

Examples

Input:

d  S------+    b
          |
          |
   c      +--->a

Output: a

Input:

S-----+---a->c
      |
      V
      b

Output: b

The arrow is not pointing at c because it is divided by the a, meaning this path never leads to an arrow head.

Input:

a S      s
  |      |
  V      V
  b      c

Output: b

Input:

d s<+S+--V
    |||  Q
    -++

Output: Q

This path starts at the S, goes down, to the right, goes up, to the right, then points down at the Q. Note that the path does not go straight from S to +.

Input:

d s-+   +-S  +--+
    +-->b |  |  |
     |  | +--+  |
     +--+ A<----+

Output: A

Input:

S-----+
|     +-^
+---+->B
    +---^

Output: B

Because the valid line will never lead to a whitespace character. The only line that doesn't lead to a whitespace character leads to a B

Challenge

The input will be a multi-line string in which you need to find the character the arrow is pointing at. There will only be one valid arrow. The valid arrow will only point to alphanumeric characters excluding S. A line will never overlap itself. e.g. -|-

S (capital) represents where the arrow starts.
- represents a horizontal line
+ represents a possible change in axis. A valid arrow will never start with a +.
| represents a vertical line
> < V ^ any of these represent the arrow head. These will never connect to a +.

There will only be one S in the string. The input will also be padded to be a rectangle (not necessarily a square).

JavaScript (ES6), 195 245 231 242 246 250
Edit4 Now, a single recursive function. Probably can't be golfed more
Edit3 Test for straight line and test for arrowhead merged in T function, S  and H functions removed.
Edit2 Revised and longer :( after this this clarification
Edit Small improvements, cutting some char here and there, waiting for CJammers to step in
Test running the snippet below in an EcmaScript 6 compliant browser. (works on Firefox. Chrome still missing the spread operator ...)

f=(s,p=s[I='indexOf']`S`,w=m=[o=~s[I]`
`,1,-o,-1],q,v,r)=>m.some((d,i)=>{for(v=w,q=p;r=s[q+=d],r=='|-'[i&1];)v='+';return r=r==v?f(s,q,v):/\w/.test(r=s[q+m['^>V<'[I](r)]])&&r},s=[...s],s[p]=0)&&r

// Less golfed
// U: recursive scan function
U = (s, // input string or array
     p = s.indexOf`S`, // current position, defult to position of S into string (at first call)
     w = // char to compare looking for a '+', at first call default to garbage as you can't follow '+' near 'S'
       m = [// m, global, offset array form movements.
         o = ~s.indexOf`\n`, // o, global, row line +1 (negated)
         1, -o, -1], // complete the values of m array
     // m and o are assigned again and again at each recursive call, but that is harmless
     // params working as local variables as the function is recursive
     q,v,r) =>
{
   s = [...s]; //convert to array, as I have to modify it while scanning
     //the conversion is done again and again at each recursive call, but that is harmless
   s[p] = 0; // make s[p] invalid to avoid bouncing back and forth

   m.some( // for each direction, stop if endpoint found
      (d,i ) => {
        q = p; // start at current position, then will add the offset relative to current direction
        v = w; // for each direction, assign the starting value that can be '+' or garbage at first call
        // compare char at next position with the expected char based on direction (- for horiz, | for vertical)
        // in m array, values at even positon are vertical movements, odds are horizontal
        while (s[q+=d] == '|-'[i&1]) // while straight direction, follow it until it ends
          v = '+'; // from now on '+' is allowed
        r = s[q];
        if (r == v) // check if found a '+'
          r = U(s, q, v) // recursive call to check all directions from current position
        else
        {
          r = s[q + m['^>V<'.indexOf(r)]], // pointed char in p (if arrowhead, else will return undefined)
          r = /\w/.test(r) && r // if alphanumeric, then we found our result - else r = false
        }
        return r; // returning r to .some; if r is truthy, the .some function will stop
      }
   )
   return r; // result if found, else undefined or null
}

// TEST
out=x=>O.innerHTML+=x.replace(/</g,'&#60;')+'\n'

// Using explicit newlines '\n' to ensure the padding to a rectangle
;[
 ['z<+S-+->a','a']
,['a<-+S>b','b']
,['S-+\n  |\n  V\n  a','a']
,['a S      s\n  |      |\n  V      V\n  b      c  ','b']
,['S-----+  \n|     +-^  \n+---+->B \n    +---^','B']
,['d s<+S+--V\n    |||  Q\n    -++    ','Q']
,['d s-+   +-S  +--+\n    +-->b |  |  |\n     |  | +--+  |\n     +--+ A<----+  ','A']
,['S-----+   \n|     +-^ \n+---+->B  \n    +---^ ','B']
].forEach(t=>{
  r=f(t[0])
  k=t[1]
  out('Test '+(r==k?'OK':'Fail')+'\n'+t[0]+'\nResult: '+ r +'\nCheck: '+k+'\n')
})


Sum of strings without converting You have to take 2 string inputs and output the sum of these two strings without converting them to int or using any numeric data type.

ex.

string one = "123";
string two = "456";
string sum = "579";

Assume the strings won't be larger than 10 digits.

This is code golf and shortest answer in characters wins. An edit to the answer in C#  will make me smile :).

Edit:
Converting to int can be defined as anything of this nature

Int.TryParse, (int), Convert.ToInt etc

80836 Assembly (57 53 bytes)

53 55 89 E5 8B 4D 0C 8B 55 10 B0 0A 30 DB 88 CF 00 C1 00 C2 49 4A 8A 01 8A 22 00 E0 00 D8 2C 30 30 DB 3C 39 7E 04 B3 01 2C 0A 88 01 88 22 38 CF 75 E2 5D 5B C3

This adds, digit by digit, right to left, without converting ascii digits '0'-'9' to the integers 0-9, and carrying over as needed. The bytecode is the code for a function, which may be called in C (see below).

The above bytecode was written by hand, from the following assembly (NASM-style, commented):

; save ebx, ebp
push ebx        ; 53
push ebp        ; 55
; copy esp
mov ebp, esp    ; 8B EC
; load arguments
mov ecx, [ebp+0x0C] ; 8B 4D 0C
mov edx, [ebp+0x10] ; 8B 55 10
; initialize stuff
mov al, 10      ; B0 0A
xor bl, bl      ; 30 DB
mov bh, cl      ; 88 CF
; send edx, ecx to end of string
add cl, al     ; 00 C1
add dl, al     ; 00 C2

; decrement everything
dec ecx         ; 49
dec edx         ; 4A

; get rightmost unprocessed digit of each number
mov al, [ecx]   ; 8A 01
mov ah, [edx]   ; 8A 22

; add two ascii digits
add al, ah      ; 00 E0
; add carry if needed
add al, bl      ; 00 D8
; subtract 0x30 ('0') to get the resulting ascii digit
sub al, 0x30    ; 2C 30

; set bl to 0
xor bl, bl      ; 30 DB

; if greater than '9': must carry over to next place
cmp al, 0x39    ; 3C 39
jle $+6         ; 7E 04
; set bl to 1 if carrying over
mov bl, 1       ; B3 01
; subtract 10 from ascii digit if carrying over
sub al, 0x0A    ; 2C 0A

mov [ecx], al   ; 88 01
mov [edx], ah   ; 88 22

; check if loop has ended
cmp bh, cl      ; 38 CF
jne $-28        ; 75 E2

; restore ebx, ebp
pop ebp         ; 5D
pop ebx         ; 5B
; return
ret             ; C3

To try this in C (gcc, linux, intel processor):

#include <stdio.h>
#include <string.h>
#include <sys/mman.h>

int main(){
    // bytecode from earlier
    char code[] = {
        0x53, 0x55, 0x8B, 0xEC, 0x8B, 0x4D, 0x0C, 0x8B,
        0x55, 0x10, 0x31, 0xC0, 0xB0, 0x09, 0x30, 0xDB,
        0x01, 0xC1, 0x01, 0xC2, 0x40, 0x50, 0x8A, 0x01,
        0x8A, 0x22, 0x00, 0xE0, 0x00, 0xD8, 0x2C, 0x30,
        0x30, 0xDB, 0x3C, 0x39, 0x7E, 0x04, 0xB3, 0x01,
        0x2C, 0x0A, 0x88, 0x01, 0x88, 0x22, 0x58, 0x48,
        0x49, 0x4A, 0x85, 0xC0, 0x75, 0xDF, 0x5D, 0x5B,
        0xC3,
    };
    // allocate executable memory to a function pointer called 'add'
    void __attribute__( (__cdecl__) ) (*add)(char*,char*) = mmap(0,sizeof code,PROT_WRITE|PROT_EXEC,MAP_ANON|MAP_PRIVATE,-1,0);
    memcpy(add, code, sizeof code);

    // test inputs
    char number1[] = "0878295272", number2[] = "8184206821";

    puts(number1);
    puts(number2);

    // call the bytecode as a c function
    add(number1, number2);

    // output is in the first argument
    puts(number1);

    // release allocated memory
    munmap(add, sizeof code);

    return 0;
}


N-uniquely additive sets Remember that a set is unordered without duplicates.

Definition An N-uniquely additive set S whose length is K is a set such that all N-length subsets in S sum to different numbers. In other words, the sums of all the N-length subsets of S are all distinct.

Objective Given an array/set as input and a number N to a function or to a full program in any reasonable format, find and return or output a truthy or falsey value (erroring for falsey is okay) denoting whether or not the input is N-uniquely additive.

You may assume that each element only appears at most once and that each number is within your language's native datatype. If need be, you may also assume that the input is sorted. Last, you may assume that 0 < N <= K.

Examples

Let's consider the set S = {1, 2, 3, 5} and N = 2. Here are all the sums of all unique pairs over S (for the unique ones are the only ones of interest for sums):

1 + 2 = 3
1 + 3 = 4
1 + 5 = 6
2 + 3 = 5
2 + 5 = 7
3 + 5 = 8

We can see that there are no duplicates in output, so S is 2-uniquely additive.

Let's now consider the set T = {12, 17, 44, 80, 82, 90} and N = 4. Here are all the possible sums of length four:

12 + 17 + 44 + 80 = 153
12 + 17 + 44 + 82 = 155
12 + 17 + 44 + 90 = 163
12 + 17 + 80 + 82 = 191
12 + 17 + 80 + 90 = 199
12 + 17 + 82 + 90 = 201
12 + 44 + 80 + 82 = 218
12 + 44 + 80 + 90 = 226
12 + 44 + 82 + 90 = 228
12 + 80 + 82 + 90 = 264
17 + 44 + 80 + 82 = 223
17 + 44 + 80 + 90 = 231
17 + 44 + 82 + 90 = 233
17 + 80 + 82 + 90 = 269
44 + 80 + 82 + 90 = 296

They are all unique, and so T is 4-uniquely additive.

Test Cases

[members], N => output
[1, 4, 8], 1 => true
[1, 10, 42], 1 => true                ; all sets trivially satisfy N = 1
[1, 2, 3, 4], 3 => true
[1, 2, 3, 4, 5], 5 => true
[1, 2, 3, 5, 8], 3 => true
[1, 2, 3, 4, 5], 2 => false           ;  1 +  4       =  5 =        2 + 3
[-2, -1, 0, 1, 2], 3 => false         ; -2 + -1 + 2   = -1 =   -2 + 0 + 1
[1, 2, 3, 5, 8, 13], 3 => false       ;  1 +  2 + 13  = 16 =    3 + 5 + 8
[1, 2, 4, 8, 16, 32], 3 => true
[1, 2, 4, 8, 16, 32], 4 => true
[1, 2, 4, 8, 16, 32], 5 => true
[1, 2, 4, 8, 16, 32], 6 => true
[3, 4, 7, 9, 12, 16, 18], 6 => true
[3, 4, 7, 9, 12, 16, 18], 3 => false  ; 3 + 4 + 12 = 19 = 3 + 7 + 9

Jelly, 7 bytes

œcS€ṢIP

Try it online!

Returns a positive number for truthy and zero for falsey.

œc       find combinations
  S€     sum each combination
    Ṣ    sort the sums
     I   find the difference between each pair of sums
           iff any sums are the same, this returns a list containing 0
      P  product of the elements of the resulting list


Number of steps for a binary search Given an input of a positive integer, output the number of steps it takes to
find the input via a binary search starting at 1.

We are simulating a binary search for the integer that was given as input, in
which the simulated searcher can repeatedly guess an integer and be told
whether it is too high, too low, or correct. The strategy for finding the
integer is as follows:

Let n be the integer given as input that we are trying to find.
Start with a guess of 1. (For every guess, increment the number of steps
(regardless of whether it was correct or not), and immediately stop and
output the total number of steps if the guess was correct.)
Double the guess repeatedly until the guess is greater than n (the target
number). (Or if it is correct, but that's already covered by our
correct-guess rule mentioned above.)
Now, set an upper bound of the first power of 2 that's greater than n (i.e.
the number that was just guessed), and set a lower bound of the power of 2
directly below it.
Repeatedly guess the average (rounded down) of the upper bound and the lower
bound. If it is too high, set it as the upper bound. If it is too low, set it
as the lower bound. This procedure is guaranteed to eventually result in a
correct guess.

Here's an example, for the input of n=21:

1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 24 -> 20 -> 22 -> 21
\__________________________/
   repeated doubling      \________________________/
                             repeated averaging

Since this is code-golf, the shortest code in bytes will win.

Here are all outputs from n=1 to n=100:

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

And here are some larger test cases:

1234 -> 21
1337 -> 22
3808 -> 19
12345 -> 28
32768 -> 16
32769 -> 32
50000 -> 28

Japt, 13 12 bytes
Oh my gosh I was beating both Jelly and Pyth for a time :D
¢a1 ªJ +1+¢l

Test it online!
Here's the strategy I use: let x be the input integer, and let b be x's binary representation. The correct output is 1 + the length of b + the last index of a 1 in b, minus 1 if this index is 0.


Binary tree rotations Balanced binary search trees are essential to guarantee O(log n) lookups (or similar operations). In a dynamic environment where a lot of keys are randomly inserted and/or deleted, trees might degenerate to linked lists which are horrible for lookups. Thus there are various kinds of self-balancing binary trees that counteract this effect (such as AVL trees or splay trees). These trees are based on different kinds of rotations that re-balance the tree.

Rotations

In this challenge we'll only look at single right-rotations, such a rotation (left-rotation would be symmetric) looks like this:

    5            3
   / \          / \
  3   6   =>   1   5
 / \              / \
1   4            4   6

If any of the leaves 1,4 or 6 had left or right sub-trees a rotation would simply keep them there. If this is a subtree of a larger tree, we'd simply "cut it off" at the node 5 and "re-attach" the rotated tree (now node 3) to that node.

Challenge

Given a binary search tree1 and a key right-rotate the tree on that node as described above. The key provided in the above example would be 5.

Rules and I/O

you may use any type for keys as long as there is a bijection between the keys of your choice and those of the test cases
you may choose any representation for binary trees as long there's no ambiguity (eg. [3,[]] is ambiguous unless otherwise specified) and it's natural for your language of choice
since the input will always be a binary search tree there are no duplicate keys
you may assume that the key is contained in the tree
you may assume that node containing the key has a left child
you may not assume a right subtree under the provided key
you may not assume that the tree is unbalanced before the rotation
you may not assume that the tree is balanced after the rotation
you may use any default I/O method
your submission may be a function returning the tree or full program printing the solution

Test cases

These examples represent a tree as follows

if it's a leaf: []
if it's a tree with key x and both subtrees are leaves: [x]
if it's a tree with key x and subtrees left right: [x,left,right]

The first example is the one provided in the section Rotations. If for some reason you need a graphical representation of them, here2 you go.

5 [5,[3,[1],[4]],[6]]  ->  [3,[1],[5,[4],[6]]]
5 [5,[3,[1],[4]],[]]  ->  [3,[1],[5,[4],[]]]
5 [5,[3,[],[4]],[6]]  ->  [3,[],[5,[4],[6]]]
5 [5,[3,[1],[]],[]]  ->  [3,[1],[5]]
4 [8,[4,[2,[1],[3]],[6,[5],[7]]],[12,[10,[9],[11]],[14,[13],[15]]]]  ->  [8,[2,[1],[4,[3],[6,[5],[7]]]],[12,[10,[9],[11]],[14,[13],[15]]]]
8 [10,[8,[6,[4,[2,[],[3]],[5]],[7]],[9]],[11]]  ->  [10,[6,[4,[2,[],[3]],[5]],[8,[7],[9]]],[11]]
10 [10,[8,[6,[4,[2,[],[3]],[5]],[7]],[9]],[11]]  ->  [8,[6,[4,[2,[],[3]],[5]],[7]],[10,[9],[11]]]
9 [6,[3,[2],[5]],[9,[8],[12,[11],[15,[14],[]]]]]  ->  [6,[3,[2],[5]],[8,[],[9,[],[12,[11],[15,[14],[]]]]]]
7 [7,[5,[3,[1],[4]],[6]],[8]]  ->  [5,[3,[1],[4]],[7,[6],[8]]]
15 [17,[9,[5,[2,[0],[4]],[8]],[15,[13,[11,[10],[12]],[14]],[16]]],[40,[27,[21,[19,[18],[20]],[24,[22],[25]]],[28]],[44,[42,[41],[]],[51,[47],[59,[55],[61]]]]]]  ->  [17,[9,[5,[2,[0],[4]],[8]],[13,[11,[10],[12]],[15,[14],[16]]]],[40,[27,[21,[19,[18],[20]],[24,[22],[25]]],[28]],[44,[42,[41],[]],[51,[47],[59,[55],[61]]]]]]
21 [17,[9,[5,[2,[0],[4]],[8]],[15,[13,[11,[10],[12]],[14]],[16]]],[40,[27,[21,[19,[18],[20]],[24,[22],[25]]],[28]],[44,[42,[41],[]],[51,[47],[59,[55],[61]]]]]]  ->  [17,[9,[5,[2,[0],[4]],[8]],[15,[13,[11,[10],[12]],[14]],[16]]],[40,[27,[19,[18],[21,[20],[24,[22],[25]]]],[28]],[44,[42,[41],[]],[51,[47],[59,[55],[61]]]]]]

1: meaning that for any node all the keys in the left subtree will be smaller than that key and all the keys in the right subtree are greater than it

2: to prevent link-rot, I embedded them as a comment

Haskell, 93 92 84 83 82 bytes

data B=B[B]Int|L
k!B[l@(B[x,y]a),r]n|k<n=B[k!l,r]n|k>n=B[l,k!r]n|1>0=B[x,B[y,r]k]a

Thanks to @BMO, @alephalpha and @Laikoni for a byte each and @nimi for eight bytes!

Try it online!


Half, Half Half, and, Half Consider the following number sequence:

  \$ 0, \frac{1}{2}, \frac{1}{4}, \frac{3}{4}, \frac{1}{8}, \frac{3}{8}, \frac{5}{8}, \frac{7}{8}, \frac{1}{16}, \frac{3}{16}, \frac{5}{16}, \frac{7}{16}, \frac{9}{16}, \frac{11}{16}, \frac{13}{16}, \frac{15}{16}, \frac{1}{32}, \frac{3}{32}, \frac{5}{32}, \dots \$

It enumerates all binary fractions in the unit interval \$ [0, 1) \$.

(To make this challenge easier, the first element is optional: You may skip it and consider the sequence starts with 1/2.)

Task

Write a program (complete program or a function) which...

Choose one of these behaviors:

Input n, output nth element of the sequence (0-indexed or 1-indexed);
Input n, output first n elements of the sequence;
Input nothing, output the infinite number sequence which you can take from one by one;

Rule

Your program should at least support first 1000 items;
You may choose to output decimals, or fractions (built-in, integer pair, strings) as you like;

Input / Output as binary digits is not allowed in this question;

This is code-golf, shortest codes win;
Standard loopholes disallowed.

Testcases

input output
1     1/2     0.5
2     1/4     0.25
3     3/4     0.75
4     1/8     0.125
10    5/16    0.3125
100   73/128  0.5703125
511   511/512 0.998046875
512   1/1024  0.0009765625

These examples are based on 0-indexed sequence with the leading 0 included. You would need to adjust the input for fitting your solution.

Read More

OEIS A006257

Josephus problem: \$ a_{2n} = 2a_n-1, a_{2n+1} = 2a_n+1 \$. (Formerly M2216)
0, 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1, 3, 5, ...

OEIS A062383

\$ a_0 = 1 \$: for \$ n>0 \$, \$ a_n = 2^{\lfloor log_2n+1 \rfloor} \$ or \$ a_n = 2a_{\lfloor \frac{n}{2} \rfloor} \$.
1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16, 32, 32, 32, ...

  A006257(n)/A062383(n) = (0, 0.1, 0.01, 0.11, 0.001, ...) enumerates all binary fractions in the unit interval [0, 1). - Fredrik Johansson, Aug 14 2006

Haskell, 25 bytes

pred.until(<2)(/2).(+0.5)

Try it online!

Outputs decimals, one-indexed without the initial zero term.

Adds 0.5 to the input, then halves until the results is below 2, then subtracts 1. Using a pointfree expression saves 1 bytes over

f n=until(<2)(/2)(n+0.5)-1


Hello world! with NO repetition In any programming language that existed before this question was asked, write a program (not a function) that outputs the characters Hello world! followed by a newline. Your program:

should not use any character more than once (including whitespace)
should only use ASCII characters
should not use any built-in libraries
should not get input (user, file, filename, system variable, internet, anything)
should not output anything else

Winner is whoever has the most votes after 14 days and abides to the six rules.

The sixth rule is that you cannot use H9+, HQ9+, HQ9+B, HQ9++, HQ9+2D, Hello, Hello+, Hello++, Hexish, CHIQRSX9+, or Fugue. Also, all answers which require implementations that are newer than this challenge must be marked as non-competing.

Disclaimer: This question was posted with the assumption that Hello world! with limited repetition did not cause any damage to your computer or your brain in the process of coming up with the answers.

Perl 6 (29 28 characters)

This was somewhat annoying, but I finally managed to make a program for this task. Thanks go to the great #perl6 community, for helping me with this task. It took me two hours, hope you enjoy. The output is completely up to specification, including a newline.

say
Q[@A`DO world!]~|<HeLhg>

There are four tokens of interest.

say

This outputs the argument with new line at end. The new line after the command itself is needed as a space replacement.
Q[@A`DO world!]

This is the first string. Q[] is for raw strings (like r"" in Python). It can take any delimiter (or pair of them), in this case []. In this case, I use this for quotes, I don't need raw string behavior.
~|

This is stringwise (~) bitwise or (|) operator.
<HeLhg>

<> is list literal, which takes space separated list of elements. In this case, it has one element, and used as a scalar, it gives a string.


Shortest Gomoku (5 in a row) implementation I suspect Gomoku may be one of the simplest games to implement in code. https://en.wikipedia.org/wiki/Gomoku The game is this: players BLACK and WHITE take turns putting down black and white stones. Black traditionally goes first. If, when a player puts down their stone, they now have 5 in a row of their color, they win. That's it.

A simple way to implement this is to just keep two lists of (x, y) integer coordinates, one for black stones and one for white stones. Players simply specify an integer x,y coordinate, any x,y coordinate at all! The game checks if there is already a stone there of either color, and if not x,y is added to the list, and then the game checks if that stone made them have 5 in a row now.

Notice I have said nothing about board size, or checking if a move is on the board or not. My thought is that specifying board size and determining what to do at edges actually complicates things more! Gomoku can be played on an infinite board, and the game still works actually!

Anyway, to be clear, I believe the specifications are, implement Gomoku on a board of size between or including 15x15 and infinity x infinity (I actually suspect inifinite may be simpler.) Let the user know who's turn it is to play, by alternately printing "b>","w>". If an invalid entry is made, such as playing where there already is a stone there, just keep asking the user who played the invalid move until they play a valid move. To keep things extra short, no need to print the board state, actually! But if on a user's turn, they have completed 5 in a row orthogonaly or diagonally, print, or throw an error, that can simply say "w" or "b", to say who won. Shortest code that does the specified, wins.

If you want to print the board state or make things look nicer or make an AI or whatever, no need to do that, but you can add with or separately to your submission if you feel like it.

I wrote a non-golfed but still shortish implementation in Python, with simple board printing and stuff before. Here it is: https://github.com/jeffkaufman/game-complexity/blob/master/gomoku.py

And here's my entire attempt at a golfed version with the basic IO and move checking, but without board printing. I am quite sure this is not optimal at all, I'm not often a golfer. All I mostly did was make variables one character / remove whitespace and stuff, you guys can *easily* do better, I know.

w,b=[],[]
def o((x,y),s,(v,u)):
 if (x,y) in s:return o((x+v,y+u),s,(v,u))
 if v:return x
 return y
d=((0,1),(1,0),(1,1),(-1,1))
def W(m,s):
 for (x,y) in d:
  if o(m,s,(x,y))-o(m,s,(-x,-y))>5:return 1
 return 0
def t(c,p):
 while 1:
  C=raw_input(c+'>')
  try:
   x,y=C.split()
   m=(int(x),int(y))
  except ValueError:continue
  if m in b+w:continue
  p.append(m)
  if W(m,p):raise Exception(c)
  break
while 1:t("b",b),t("w",w)

an example run from that, which throws a Python error saying who won, at the end:

b>0 0
w>-4 5
b>0 1
w>0 1
w>7 12
b>0 2
w>7 12
w>4 5
b>0 -1
w>4 4
b>0 3

Traceback (most recent call last):
  File "C:/Users/udqbp/OneDrive/Desktop/test.py", line 22, in <module>
    while 1:t("b",b),t("w",w)
  File "C:/Users/udqbp/OneDrive/Desktop/test.py", line 20, in t
    if W(m,p):raise Exception(c)
Exception: b

Jelly, 54 bytes

Ḋ,Z,ŒD$ŒrFs2ḢƇ<5Ȧ
0x⁹s⁴-;N1¦Ṅ©+Ɠœị®Ḋ¤$¿ṪṬṭ0x$Ʋ¹NƭƊƊ$Ç¿

Try it online!

A full program that reads input on stdin. For each loop through it prints the current player (1 or -1) and the 16x16 grid. Moves are input on stdin as a Python array (e.g. [3,2]) with or without the surrounding square brackets. The only validation done is to make sure that the relevant cell is empty. When there are 5 (or more) in a row, the program ends and prints out the winner and final grid.

If checking for a valid move can be omitted, 10 bytes can be saved:

Jelly, 44 bytes

Ḋ,Z,ŒD$ŒrFs2ḢƇ<5Ȧ
0x⁹s⁴-;N1¦Ṅ+ƓṪṬṭ0x$¹Nƭ¤ƲÇ¿

Try it online!

Conversely, if the w/b designation in the spec is strict, that costs 15 bytes:

Jelly, 69 bytes

ị“wb ”Ḣ
Ḋ,Z,ŒD$ŒrFs2ḢƇ<5Ȧ
0x⁹s⁴-;N1¦Ñ;”>ṄṛƲ©+Ɠœị®Ḋ¤$¿ṪṬṭ0x$Ʋ¹NƭƊƊ$Ç¿Ñ

Try it online!


Finish lazy parentheses The parentheses on my keyboard are all worn out, and I want to avoid using them as much as possible. Your challenge is to balance a line containing parentheses by adding them in before and after each line.

This is similar to TI-Basic's automatic parentheses and string closure (i.e. Output(1, 1, "Hello, World!). It also saves precious bytes from a program!

Example input:

This line has no parentheses
alert(Math.max(1, 2
1+1)*2).toString()
function() { alert('Hello, World!'); })(

Example (possible) output:

This line has no parentheses
alert(Math.max(1, 2))
((1+1)*2).toString()
(function() { alert('Hello, World!'); })()

Specification:

For each line of input,

Add as many open parentheses to the beginning and close parentheses to the end of the line as needed to balance the parentheses in the line

The definition of "balance" is:

Same amount of ( and ) in the line
For every substring starting from the beginning of the string, this substring must not have more closing parentheses than opening parentheses

For example, (foo))(bar is not balanced because (foo)) has more closing parentheses than opening parentheses

You may add extra unnecessary parentheses if you want to, if it makes your code shorter
You do not need to worry about string literals or anything like that, assume that all parentheses need balancing

Output each line with parentheses balanced

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

GolfScript, 23 bytes

n/{"()"1/{.2$\-,*}%*n}/

The loophole I'm exploiting is the ruling that:

  You may add extra unnecessary parentheses if you want to, if it makes your code shorter

Basically, for each line, this code counts the number of characters on the line that are not opening parentheses, and prepends that many extra opening parentheses to the line, and then does the same for closing parentheses.  This is incredibly inefficient, but does ensure that all the parentheses on the output line are balanced.

For example, given the input:

This line has no parentheses
alert(Math.max(1, 2
1+1)*2).toString()
function() { alert('Hello, World!'); })(

this program will output:

((((((((((((((((((((((((((((This line has no parentheses))))))))))))))))))))))))))))
(((((((((((((((((alert(Math.max(1, 2)))))))))))))))))))
(((((((((((((((((1+1)*2).toString())))))))))))))))
(((((((((((((((((((((((((((((((((((((function() { alert('Hello, World!'); })()))))))))))))))))))))))))))))))))))))

Ps. You can also test this code online.


Evaluate the binomial theorem! Your mission, even if you don't accept it, is to input three numbers from STDIN or file:

  5 0.5 6

What you must do is evaluate this:

  (5a + 0.5b)^6

This basically means that the first two numbers are the coefficients of a and b and the third is the exponent in a binomial expansion.

Rules:

The first two numbers are either integers or simple terminating fractions.
The third number is a positive integer.
Do not use any inbuilt binomial functions from libs. (thanks to comments)
The shortest code wins!

Go on, do it.


Generate Pascal's Pyramid Pascal's Pyramid is an extension of Pascal's Triangle to the third dimension. Starting with a 1 as the apex, the elements of each successive layer can be determined by summing the three numbers that are above it. The nth layer contains the coefficients of (a + b + c)^(n-1).

You are to create a program that, given an input n, outputs the first n layers of Pascal's Pyramid. There must be two newlines between the different layers, and they must be in order. Within each layer, each row must be on a separate line, with the elements separated by spaces. Apart from that, you may format the pyramid however you like.

Your code should be reasonably fast generating a pyramid with 10 layers.

For example, your program, when given 4 as input, should output something like this:

1

1
1 1

1
2 2
1 2 1

1
3 3
3 6 3
1 3 3 1

May the shortest code win!

Python, 110

l=1
exec"print;n=1;r=0;exec\"c=0;exec'print n,;n*=r-c;c+=1;n/=c;'*r;print n;r+=1;n=n*l/r-n;\"*l;l+=1;"*input()

Original, ungolfed solution:

for layer in range(1, input() + 1):
    print
    n = 1
    for row in range(1, layer + 1):
        for col in range(1, row):
            print n,
            n *= row - col
            n /= col
        print n
        n *= layer - row
        n /= row


Symmetric boolean functions as Zhegalkin polynomials Let \$\mathbb{B} = \mathbb{Z}_2 = \{0, 1\}\$ be the set of booleans. A symmetric boolean function in \$n\$ arguments is a function \$f_S : \mathbb{B}^n \to \mathbb{B}\$ that checks if the number of its true arguments is in \$S\$, i. e. a function \$f_S\$ such that

$$f_S(\alpha_1, \alpha_2, \ldots, \alpha_n) = \left(\sum_{1 \le  i \le n}\alpha_{i}\right) \in S$$

or equivalently

$$f_S(\alpha_1, \alpha_2, \ldots, \alpha_n) = |\{ i : \alpha_i \}| \in S. $$

These functions are called symmetric boolean function because they are all the boolean function that do not depend on argument order.

The set of boolean numbers forms a field, conventionally denoted \$GF(2)\$, where multiplication is logical and (\$\wedge\$) and addition is exclusive or (\$\oplus\$). This field has the properties that \$-\alpha = \alpha\$, \$\alpha / \beta = \alpha \wedge \beta\$ (for all \$\beta \neq 0\$), \$\alpha \oplus \alpha = 0\$ and \$\alpha \wedge \alpha = \alpha\$ for all \$\alpha\$ in addition to the field properties. For convenience, I am going to write \$\oplus\$ as \$+\$ and leave out \$\wedge\$ in the next paragraphs. For example, I will write \$\alpha \oplus \beta \oplus \alpha \wedge \beta\$ as \$\alpha + \beta + \alpha\beta\$.

Every boolean function can be expressed as a polynomial over the field of boolean numbers. Such a polynomial is called a Zhegalkin polynomial, the representation is canonical, i. e. there is exactly one polynomial that represents a given boolean function. Here are some examples for boolean functions and their corresponding Zhegalkin polynomials:

\$\alpha \vee \beta = \alpha + \beta + \alpha\beta\$
\$\alpha \wedge \neg\beta = \alpha + \alpha\beta\$
\$(\alpha \to \beta) \oplus \gamma = 1 + \alpha +  \gamma + \alpha\beta\$
\$\neg(\alpha \wedge \beta) \vee \gamma = 1 + \alpha\beta + \alpha\beta\gamma\$
\$f_{\{1, 4\}}(\alpha, \beta, \gamma, \delta) = \alpha + \beta + \gamma + \delta + \alpha\beta\gamma + \alpha\beta\delta + \alpha\gamma\delta + \beta\gamma\delta + \alpha\beta\gamma\delta\$
where the triple terms \$(\alpha\beta\gamma + \alpha\beta\delta + \alpha\gamma\delta + \beta\gamma\delta)\$ are required because otherwise we would have \$f(1,1,1,0) = 1\$, and \$3 \not\in \{1, 4\}\$.

One observation we can make is that due to symmetry, the Zhegalkin polynomial for a symmetric boolean function always has the form

$$f_S(\alpha_1, \alpha_2, \ldots, \alpha_n) = \sum_{i \in T_{S,n}}t_{n,i}$$

where \$\sum\$ denotes summation with exclusive or and \$t_{n, i}\$ is the sum of all product terms that use \$i\$ out of the \$n\$ arguments to \$f_S\$ and \$T_{S,n} \subseteq \{0, 1, \ldots, n\}\$ is a set describing those \$t_{n, i}\$ we need to construct \$f_S(\alpha_1, \alpha_2, \ldots, \alpha_n)\$. Here are some examples for \$t_{n, i}\$ so you can get an idea what they look like:

\$t_{4, 1} = \alpha + \beta + \gamma + \delta\$
\$t_{3, 2} = \alpha\beta + \alpha\gamma + \beta\gamma\$
\$t_{4, 4} = \alpha\beta\gamma\delta\$
for all \$n\$: \$t_{n, 0} = 1\$

We can thus describe an \$f_S\$ in \$n\$ arguments completely by \$n\$ and \$T_{S, n}\$. Here are some test cases:

\$T_{\{1, 4\}, 4} = \{1, 3, 4\}\$
\$T_{\{2, 3, 4\}, 4} = \{2, 4\}\$
\$T_{\{2\}, 4} = \{2, 3\}\$
\$T_{\{1, 2\}, 2} = \{1, 2\}\$ (logical or)
\$T_{\{2, 3\}, 3} = \{2\}\$ (median function)

The task in this challenge is to compute \$T_{S, n}\$ given \$S\$ and \$n\$. You can choose an appropriate input and output format as you like. This challenge is code-golf, the shortest solution in octets wins. As a special constraint, your solution must run in polynomial time \$O(n^k)\$ where \$n\$ is the \$n\$ from the input.

Dyalog APL, 15 bytes
{2|⍺⌹⍉∘.!⍨0,⍳⍵}

Matrix division, basically. Takes input like 0 0 1 1 1 {2|⍺⌹⍉∘.!⍨0,⍳⍵} 4 for T4({2,3,4}).
{              }        Dyadic function:
              ⍵         Right argument          4
             ⍳          Index vector            1 2 3 4
           0,           Append 0                0 1 2 3 4
      ∘.                Outer product           ——————————
          ⍨             |With itself              1 0 0 0
        !               |By binomial coeff.       2 1 0 0
     ⍉                  Matrix transpose          3 3 1 0
                        Result at this step: ->   4 6 4 1
   ⍺                    Left argument
    ⌹                   Matrix division (A⌹B is A^-1 B, not A B^-1)
                        (implicitly converts ⍺ to column vector)
 2|                     Modulo 2

Since the transposed matrix of binomial coefficients is lower triangular with determinant 1, its inverse will only contain integers. So to matrix-divide over F2 we can just matrix-divide over the reals, then mod by 2.
Matrix division is an O(n^3) operation, and calculating each of the O(N^2) binomial coefficients is well below O(n^3), so this runs in O(N^5).
Try it on TryAPL.


Oreo? No... Lollipop, maybe? Since 2009, Android's version code names have been confectionery-themed. Android 1.5 is Cupcake, Android 1.6 is Donut, Android 2.0 is Eclair, etc.. In fact, the version names are alphabetical!

C -> Cupcake
D -> Donut
E -> Eclair
F -> Froyo
G -> Gingerbread
H -> Honeycomb
I -> Ice Cream Sandwich
J -> Jellybean
K -> Kitkat
L -> Lollipop
M -> Marshmallow
N -> Nougat
O -> Oreo

In order:

Cupcake, Donut, Eclair, Froyo, Gingerbread, Honeycomb, Ice Cream Sandwich, Jellybean, Kitkat, Lollipop, Marshmallow, Nougat, Oreo

Challenge

Write a program/function that takes a letter from C to O and outputs its respective Android version code name.

Specifications

Standard I/O rules apply.
Standard loopholes are forbidden.
You can choose to either support lowercase input or uppercase input or even both.
The output may be in title case (Cupcake) or completely lower case (eclair). Ice cream sandwich may be capitalized however you like. (I didn't expect it to cause so much confusion...)
This challenge is not about finding the shortest approach in all languages, rather, it is about finding the shortest approach in each language.
Your code will be scored in bytes, usually in the encoding UTF-8, unless specified otherwise.
Built-in functions (Mathematica might have one :P) that compute this sequence are allowed but including a solution that doesn't rely on a built-in is encouraged.
Explanations, even for "practical" languages, are encouraged.

Test cases

These are uppercase and title case.

Input   Output

F       Froyo
I       Ice Cream Sandwich
J       Jellybean
N       Nougat
G       Gingerbread
L       Lollipop

In a few better formats:

F, I, J, N, G, L
f, i, j, n, g, l

F I J N G L
f i j n g l

Charcoal, 73 bytes

θ§⪪”%↖↙1¬¢/vy⁵⸿ψＪPP±≔Ｓ×5Jρνξ–Ｇu ◧；Yx³F▶ψ;εB↥:P¹N﹪J$α✂χ✳⦄⟲*±¶Sp:ς↘Ｖ◧◧”x℅θ

Try it online! I/O is in lower case. Based on this verbose version. Explanation:

                Implicitly print:
θ               Input character
                Implicitly print:
   ”...”        Long compressed string "oneycombx...xingerbread"
  ⪪            Split on
        x       The string "x"
 §              Circularly indexed by
          ℅     Character code of
           θ    Input character


Beginners 10x10 multiplication matrix I was looking for a very easy task to look how short of a code can be produced on a beginners exercise.

The goal is to produce a simple table that looks like this common java/c# code is about 4 lines. So get your golfing-languages ready ;) Try to align the matrix in any way it is readable.

1 2 3    .. 10

2 4 6    .. 20

3 6 9    .. 30

. . .    .. .

10 20 30 .. 100

EDIT: The first answer below shows a propper alignment and solution


Vandermonde Determinant Given a vector of \$n\$ values \$(x_1,x_2,x_3,\ldots,x_n)\$ return the determinant of the corresponding Vandermonde matrix
\$V(x_1, x_2, \ldots, x_n) = \begin{bmatrix}1 & x_1 & x_1^2 & x_1^3 & \ldots &x_1^{n-1} \\1 & x_2 & x_2^2 & x_2^3 & \ldots &x_2^{n-1} \\ \vdots & & & \vdots & & \vdots \\ 1 & x_n & x_n^2 & x_n^3 & \ldots & x_n^{n-1}\end{bmatrix}\$.
This determinant can be written as:
\$\det V(x_1, x_2, \ldots x_n) = \prod_\limits{1 \leqslant i < j \leqslant n} (x_j - x_i)\$
Details
Your program/function has to accept a list of floating point numbers in any convenient format that allows for a variable length, and output the specified determinant.
You can assume that the input as well as the output is within the range of the values your language supports. If you language does not support floating point numbers, you may assume integers.
Some test cases
Note that whenever there are two equal entries, the determinant will be 0 as there are two equal rows in the corresponding Vandermonde matrix. Thanks to @randomra for pointing out this missing testcase.
[1,2,2,3]            0
[-13513]             1
[1,2]                1
[2,1]               -1
[1,2,3]              2
[3,2,1]             -2
[1,2,3,4]           12
[1,2,3,4,5]        288
[1,2,4]              6
[1,2,4,8]         1008
[1,2,4,8,16]  20321280
[0, .1, .2,...,1]   6.6586e-028
[1, .5, .25, .125]  0.00384521
[.25, .5, 1, 2, 4]  19.3798828

Jelly, 6 bytes

œc2IFP

œc2 gets all combinations without replacement of length 2. I computes the difference list of each of those pairs, yielding a list like [[1], [2], [3], ..., [1]]. We Flatten and take the Product.

Try it here!


Very Simple Triangles Write a program or function that takes in a positive integer (via stdin, command line, or function arg) and prints or returns a string of that many of these small triangles tiled together, alternating which way they point:

 /\
/__\

This sole triangle is the output if the input is 1.

If the input is 2, the output is

  ____
 /\  /
/__\/

If the input is 3, the output is

  ____
 /\  /\
/__\/__\

If the input is 4, the output is

  ________
 /\  /\  /
/__\/__\/

And so on. Your program must support inputs up to 216 - 1 = 65535.

Details

The leftmost triangle always points upwards.
There may be trailing spaces but there may not be unnecessary leading spaces.
There may be an optional trailing newline.
Note that for 1 the output is two lines long but otherwise it's three. This is required.
The shortest submission in bytes wins.

Pyth, 44 42

ItQpdd*\_*4/Q2)jbms<*dQhQ,c" /\ "2,\/"__\\

The first line:

ItQpdd*\_*4/Q2)
ItQ           )    If the input is not 1
   pdd             Print two spaces
      *\_*4/Q2     Then groups of 4 underscores, repeated input/2 times.

The other two lines are generated by noticing that the second line consists of " /" and "\ " alternating input + 1 times, and the third line consists of "/" and "__\" alternated in the same fashion.


Swap Pairs or Remove Specification

For this challenge you will:

Take an array of positive integers.
For each overlapping pair in the array, calculate the difference of it's integers. If the difference is a common divisor of the integers (they are both divisible by their difference), swap their positions in the array. The values of the next pair are affected by this swap. No integer is divisible by 0.
If an integer was not divisible by the difference of any of it's pairs, remove it from the array.
Repeat the previous two steps until the length of the array will not decrease any further.
Output the length of the resulting array.

Example

Input = [ 4, 5, 2, 4 ].
Difference of first pair [ ( 4, 5, ) 2, 4 ] = 1, (common divisor of 4 and 5)

Swap the pair and the array becomes [ 5, 4, 2, 4 ].

Difference of second pair [ 5, ( 4, 2, ) 4 ] = 2 (common divisor of 4 and 2)

Swap the pair so the array becomes [ 5, 2, 4, 4 ].

Difference of third pair [ 5, 2, ( 4, 4 ) ] = 0 (not a divisor of any integer)

Do not swap the pair so the array remains the same.

The final 4 was never swapped, remove it so the array becomes [ 5, 2, 4 ].
Repeat.
Difference of first pair [ ( 5, 2, ) 4 ] = 3

Do not swap the pair so the array remains the same.

Difference of second pair [ 5, ( 2, 4 ) ] = 2

Swap the pair so the array becomes [ 5, 4, 2 ].

The 5 was never swapped, remove it so the array becomes [ 4, 2 ]
Repeat.
From here the array will endlessly switch between [ 4, 2 ] and [ 2, 4 ], so output the resulting length of 2.

Rules

Input array will always have a length between 2 and 9 inclusive.
Integers will always be between 1 and 999 inclusive.
Input can optionally be in the form of a string delimited by a specific character.
This is code-golf so shortest code in bytes wins.

Test Cases

Format: [ input array ] = result (steps to get result, do not output this)

[ 1, 1 ] = 0                        ([])
[ 1, 2 ] = 2                        ([ 2, 1 ] -> [ 1, 2 ] -> ...)
[ 1, 2, 3 ] = 2                     ([ 2, 1 ] -> [ 1, 2 ] -> ...)
[ 4, 6, 8 ] = 3                     ([ 6, 8, 4 ] -> [ 8, 4, 6 ] -> [ 4, 6, 8 ] -> ...)
[ 99, 1, 3 ] = 0                    ([])
[ 4, 5, 2, 4 ] = 2                  ([ 5, 2, 4 ] -> [ 4, 2 ] -> [ 2, 4 ] -> ...)
[ 12, 4, 6, 3 ] = 3                 ([ 6, 4, 3 ] -> [ 4, 3, 6 ] -> [ 3, 6, 4 ] -> ...)
[ 9, 6, 10, 18 ] = 2                ([ 6, 10, 18, 9 ] -> [ 9, 18 ] -> [ 18, 9 ] -> ...)
[ 55, 218, 654, 703, 948, 960 ] = 2
[ 954, 973, 925, 913, 924, 996, 927, 981, 905 ] = 2

JavaScript (ES6), 133

Recursive function.

F=(m,k=[])=>(k[m]=m,f=m.map((x,i)=>x%(w=x-(y=m[i+1]))==0&y%w==0?m[m[i]=y,i+1]=x:0),k[m=m.filter((x,i)=>f[i-1]|f[i])]?m.length:F(m,k))

Less golfed and not recursive

F=m=>{
  for(k=[];!k[m];) // use k to find a repeated state and exit the loop
  {
    k[m]=1
    console.log(m)
    // loop for swap and mark swap position in array f
    f=m.map((x,i)=>(
      y=m[i+1], // next element
      w=x-y,    // difference
      x%w==0&y%w==0 // if common divisor ...
        ?m[m[i+1]=x,i]=y // swap elements,mark with nonzero
        :0 // no swap, mark with 0
    ))
    m=m.filter((x,i)=>f[i-1]|f[i]) // remove elements not swapped
  }
  return m.length
}

Test

F=(m,k=[])=>(k[m]=m,f=m.map((x,i)=>x%(w=x-(y=m[i+1]))==0&y%w==0?m[m[i]=y,i+1]=x:0),k[m=m.filter((x,i)=>f[i-1]|f[i])]?m.length:F(m,k))

console.log=x=>O.textContent+=x+'\n'

;[[1,1],[1,2],[1,2,3],[4,6,8],[99,1,3],[4,5,2,4],[12,4,6,3],[9,6,10,18]
,[ 55, 218, 654, 703, 948, 960 ],[ 954, 973, 925, 913, 924, 996, 927, 981, 905 ]]
.forEach(t=>console.log(t+' -> '+F(t)))


Golf the K-means algorithm K-means is a standard unsupervised clustering algorithm, which, given a set of "points" and a number of clusters K, will assign each "point" to one of K clusters.

Pseudo-Code of K-means

Note that there are many variants of K-means. You have to implement the algorithm I am describing below. You may have some variation on the algorithm or use built-ins as long as you would get the same result as this algorithm given the same initial points.

In this challenge, all inputs will be points on the 2D plane (each point is represented by its coordinates in x and y).

Inputs: K, the number of clusters
        P, the set of points

Choose K points of P uniformly at random
Each chosen point is the initial centroid of its cluster

Loop:
     For each point in P:
         Assign to the cluster whose centroid is the nearest (Euclidean distance)
         In case of a tie, any of the tied cluster can be chosen

     Recompute the centroid of each cluster:
         Its x coordinate is the average of all x's of the points in the cluster
         Its y coordinate is the average of all y's of the points in the cluster

Until the clusters don't change from one iteration to the next

Output: the set of clusters

Inputs and Outputs

You may take K and P through STDIN, or as a function argument, etc.
P and the points in P can be represented using any structure that is natural for set/lists in your language of choice.
K is a strictly positive integer.
You may assume that inputs are valid.
There will always be at least K points in P.
You may output the clusters to STDOUT, return them from a function, etc.
The ordering of the clusters and the ordering inside the clusters is unimportant.
-You can either return groups of points to represent clusters, or each point labeled with an identifier for the cluster (e.g. an integer).

Test cases

Since the resulting clusters depend on which points were initially chosen, you may not all get the same results (or the same result each time you run your code).

Therefore, only take the output as an example output.

Input:
  K = 1
  P = [[1,2.5]]
Output:
  [[[1,2.5]]]

Input:
  K = 3
  P = [[4,8], [15,16], [23,42], [-13.37,-12.1], [666,-666]]
Output:
  [[[666,-666]],[[-13.37,-12.1],[4,8]],[[15,16],[23,42]]]

Input:
  K = 2
  P = [[1,1], [1,1], [1,1]]
Output:
  [[[1,1]],[[1,1],[1,1]]]

Scoring

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

C++, 479 474 bytes

Only ~20x as much as Matlab!

Golfed

#define V vector

#define f float
struct P{f x,y,i=0;f d(P&p){return(p.x-x)*(p.x-x)+(p.y-y)*(p.y-y);}f n(P&p){return i?x/=i,y/=i,d(p):x=p.x,y=p.y,0;}f a(P&p){x+=p.x,y+=p.y,i++;}};P z;int l(P a,P b){return a.d(z)<b.d(z);}f m(f k,V&p){f s=p.size(),i,j=0,t=1;V c(k),n=c,d;for(random_shuffle(p.begin(),p.end());j<k;c[j].i=j++)c[j]=p[j];for(;t;c=n,n=V(k)){for(i=0;i<s;i++)d=c,z=p[i],sort(d.begin(),d.end(),l),j=d[0].i,p[i].i=j,n[j].a(p[i]);for(j=t=0;j<k;j++)t+=n[j].n(c[j]);}}

The input/output to the algorithm is a set of points (struct P) with x and y; and the output is the same set, with their i's set to indicate the index of the output cluster that the point ends in.

That extra i is also used to identify the clusters. In the main loop, the closest centroid to each point is found by sorting a copy of the current centroids by proximity to that point.

This handles degenerate cases (empty clusters) by keeping the corresponding centroids' previous position (see definition of P::n, which also returns distance-to-previous-centroid). A few chars could be saved by assuming that these will not crop up.

Ungolfed, with main

#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;

#define V vector

#define f float
struct P{
    f x,y,i=0;
    f d(P&p){return(p.x-x)*(p.x-x)+(p.y-y)*(p.y-y);} // distance squared
    f n(P&p){return i?x/=i,y/=i,d(p):x=p.x,y=p.y,0;} // normalize-or-reset
    f a(P&p){x+=p.x,y+=p.y,i++;}                     // add coordinates
};
P z;int l(P a,P b){return a.d(z)<b.d(z);}            // closer-to-z comparator
f m(f k,V&p){
    f s=p.size(),i,j=0,t=1;V c(k),n=c,d;
    for(random_shuffle(p.begin(),p.end());j<k;c[j].i=j++)
        c[j]=p[j];                                // initial random assignment
    for(;t;c=n,n=V(k)){
        for(i=0;i<s;i++)                          // assign to clusters
            d=c,z=p[i],sort(d.begin(),d.end(),l),
            j=d[0].i,p[i].i=j,n[j].a(p[i]);       // and add those coords
        for(j=t=0;j<k;j++)t+=n[j].n(c[j]);        // normalize & count changes
    }
}

int main(int argc, char **argv) {
    srand((unsigned long)time(0));

    int k;
    V p;
    sscanf(argv[1], "%d", &k);
    printf("Input:\n");
    for (int i=2,j=0; i<argc; i+=2, j++) {
        P n;
        sscanf(argv[i], "%f", &(n.x));
        sscanf(argv[i+1], "%f", &(n.y));
        p.push_back(n);
        printf("%d : %f,%f\n", j, p[j].x, p[j].y);
    }

    m(k,p);
    printf("Clusters:\n");
    for (int q=0; q<k; q++) {
        printf("%d\n", q);
        for (unsigned int i=0; i<p.size(); i++) {
            if (p[i].i == q) printf("\t%f,%f (%d)\n", p[i].x, p[i].y, i);
        }
    }
    return 0;
}