问:
Map a list of indefinite size to a number!
It is well known, in the field of Mathematics studying infinity, that the Cartesian product of any finite amount of countable sets is also countable.

Your task is to write two programs to implement this, one to map from list to integer, one to map from integer to list.

Your function must be bijective and deterministic, meaning that 1 will always map to a certain list, and 2 will always map to another certain list, etc...

Earlier, we mapped integers to a list consisting only of 0 and 1.

However, now the list will consist of non-negative numbers.

Specs

Program/function, reasonable input/output format.

Whether the mapped integers start from 1 or starts from 0 is your choice, meaning that 0 doesn't have to (but may) map to anything.

The empty array [] must be encoded.

Input/output may be in any base.

Sharing code between the two functions is allowed.

Scoring

This is code-golf. Lowest score wins.

Score is the sum of lengths (in bytes) of the two programs/functions.

答:
Jelly, <s>18</s> 16 bytes

List to integer, <s>10</s> 8 bytes

```<code>TṪạL;³ÆẸ
</code>```

Maps lists of non-negative integers to positive integers. Try it online!

Integer to list, 8 bytes

```<code>ÆE©Ḣ0ẋ®;
</code>```

Maps positive integers to lists of non-negative integers . Try it online!

Background

Let p0, p1, p2, ⋯ be the sequence of prime numbers in ascending order.

For each list of non-negative integers A := [a1, ⋯, an], we map A to p0z(A)p1a1⋯pnan, where z(A) is the number of trailing zeroes of A.

Reversing the above map in straightforward. For a positive integer k, we factorize it uniquely as the product of consecutive prime powers n = p0α0p1α1⋯pnαn, where αn > 0, then reconstruct the list as [α1, ⋯, αn], appending α0 zeroes.

How it works

List to integer

```<code>TṪạL;³ÆẸ  Main link. Argument: A (list of non-negative integers)

T         Yield all indices of A that correspond to truthy (i.e., non-zero) items.
 Ṫ        Tail; select the last truthy index.
          This returns 0 if the list is empty.
   L      Yield the length of A.
  ạ       Compute the absolute difference of the last truthy index and the length.
          This yields the amount of trailing zeroes of A.
    ;³    Prepend the difference to A.
      ÆẸ  Convert the list from prime exponents to integer.
</code>```

Integer to list

```<code>ÆE©Ḣ0ẋ®;  Main link. Input: k (positive integer)

ÆE        Convert k to the list of its prime exponents.
  ©       Save the list of prime exponents in the register.
   Ḣ      Head; pop the first exponent.
          If the list is empty, this yields 0.
    0ẋ    Construct a list of that many zeroes.
      ®;  Concatenate the popped list of exponents with the list of zeroes.
</code>```

Example output

The first one hundred positive integers map to the following lists.

```<code>  1: []
  2: [0]
  3: [1]
  4: [0, 0]
  5: [0, 1]
  6: [1, 0]
  7: [0, 0, 1]
  8: [0, 0, 0]
  9: [2]
 10: [0, 1, 0]
 11: [0, 0, 0, 1]
 12: [1, 0, 0]
 13: [0, 0, 0, 0, 1]
 14: [0, 0, 1, 0]
 15: [1, 1]
 16: [0, 0, 0, 0]
 17: [0, 0, 0, 0, 0, 1]
 18: [2, 0]
 19: [0, 0, 0, 0, 0, 0, 1]
 20: [0, 1, 0, 0]
 21: [1, 0, 1]
 22: [0, 0, 0, 1, 0]
 23: [0, 0, 0, 0, 0, 0, 0, 1]
 24: [1, 0, 0, 0]
 25: [0, 2]
 26: [0, 0, 0, 0, 1, 0]
 27: [3]
 28: [0, 0, 1, 0, 0]
 29: [0, 0, 0, 0, 0, 0, 0, 0, 1]
 30: [1, 1, 0]
 31: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 32: [0, 0, 0, 0, 0]
 33: [1, 0, 0, 1]
 34: [0, 0, 0, 0, 0, 1, 0]
 35: [0, 1, 1]
 36: [2, 0, 0]
 37: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 38: [0, 0, 0, 0, 0, 0, 1, 0]
 39: [1, 0, 0, 0, 1]
 40: [0, 1, 0, 0, 0]
 41: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 42: [1, 0, 1, 0]
 43: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 44: [0, 0, 0, 1, 0, 0]
 45: [2, 1]
 46: [0, 0, 0, 0, 0, 0, 0, 1, 0]
 47: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 48: [1, 0, 0, 0, 0]
 49: [0, 0, 2]
 50: [0, 2, 0]
 51: [1, 0, 0, 0, 0, 1]
 52: [0, 0, 0, 0, 1, 0, 0]
 53: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 54: [3, 0]
 55: [0, 1, 0, 1]
 56: [0, 0, 1, 0, 0, 0]
 57: [1, 0, 0, 0, 0, 0, 1]
 58: [0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 59: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 60: [1, 1, 0, 0]
 61: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 62: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 63: [2, 0, 1]
 64: [0, 0, 0, 0, 0, 0]
 65: [0, 1, 0, 0, 1]
 66: [1, 0, 0, 1, 0]
 67: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 68: [0, 0, 0, 0, 0, 1, 0, 0]
 69: [1, 0, 0, 0, 0, 0, 0, 1]
 70: [0, 1, 1, 0]
 71: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 72: [2, 0, 0, 0]
 73: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 74: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 75: [1, 2]
 76: [0, 0, 0, 0, 0, 0, 1, 0, 0]
 77: [0, 0, 1, 1]
 78: [1, 0, 0, 0, 1, 0]
 79: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 80: [0, 1, 0, 0, 0, 0]
 81: [4]
 82: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 83: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 84: [1, 0, 1, 0, 0]
 85: [0, 1, 0, 0, 0, 1]
 86: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 87: [1, 0, 0, 0, 0, 0, 0, 0, 1]
 88: [0, 0, 0, 1, 0, 0, 0]
 89: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 90: [2, 1, 0]
 91: [0, 0, 1, 0, 1]
 92: [0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
 93: [1, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 94: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 95: [0, 1, 0, 0, 0, 0, 1]
 96: [1, 0, 0, 0, 0, 0]
 97: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 98: [0, 0, 2, 0]
 99: [2, 0, 0, 1]
100: [0, 2, 0, 0]
</code>```

Body:
Jelly, <s>18</s> 16 bytes

List to integer, <s>10</s> 8 bytes

TṪạL;³ÆẸ

Maps lists of non-negative integers to positive integers. Try it online!

Integer to list, 8 bytes

ÆE©Ḣ0ẋ®;

Maps positive integers to lists of non-negative integers . Try it online!

Background

Let p0, p1, p2, ⋯ be the sequence of prime numbers in ascending order.

For each list of non-negative integers A := [a1, ⋯, an], we map A to p0z(A)p1a1⋯pnan, where z(A) is the number of trailing zeroes of A.

Reversing the above map in straightforward. For a positive integer k, we factorize it uniquely as the product of consecutive prime powers n = p0α0p1α1⋯pnαn, where αn > 0, then reconstruct the list as [α1, ⋯, αn], appending α0 zeroes.

How it works

List to integer

TṪạL;³ÆẸ  Main link. Argument: A (list of non-negative integers)

T         Yield all indices of A that correspond to truthy (i.e., non-zero) items.
 Ṫ        Tail; select the last truthy index.
          This returns 0 if the list is empty.
   L      Yield the length of A.
  ạ       Compute the absolute difference of the last truthy index and the length.
          This yields the amount of trailing zeroes of A.
    ;³    Prepend the difference to A.
      ÆẸ  Convert the list from prime exponents to integer.

Integer to list

ÆE©Ḣ0ẋ®;  Main link. Input: k (positive integer)

ÆE        Convert k to the list of its prime exponents.
  ©       Save the list of prime exponents in the register.
   Ḣ      Head; pop the first exponent.
          If the list is empty, this yields 0.
    0ẋ    Construct a list of that many zeroes.
      ®;  Concatenate the popped list of exponents with the list of zeroes.

Example output

The first one hundred positive integers map to the following lists.

  1: []
  2: [0]
  3: [1]
  4: [0, 0]
  5: [0, 1]
  6: [1, 0]
  7: [0, 0, 1]
  8: [0, 0, 0]
  9: [2]
 10: [0, 1, 0]
 11: [0, 0, 0, 1]
 12: [1, 0, 0]
 13: [0, 0, 0, 0, 1]
 14: [0, 0, 1, 0]
 15: [1, 1]
 16: [0, 0, 0, 0]
 17: [0, 0, 0, 0, 0, 1]
 18: [2, 0]
 19: [0, 0, 0, 0, 0, 0, 1]
 20: [0, 1, 0, 0]
 21: [1, 0, 1]
 22: [0, 0, 0, 1, 0]
 23: [0, 0, 0, 0, 0, 0, 0, 1]
 24: [1, 0, 0, 0]
 25: [0, 2]
 26: [0, 0, 0, 0, 1, 0]
 27: [3]
 28: [0, 0, 1, 0, 0]
 29: [0, 0, 0, 0, 0, 0, 0, 0, 1]
 30: [1, 1, 0]
 31: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 32: [0, 0, 0, 0, 0]
 33: [1, 0, 0, 1]
 34: [0, 0, 0, 0, 0, 1, 0]
 35: [0, 1, 1]
 36: [2, 0, 0]
 37: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 38: [0, 0, 0, 0, 0, 0, 1, 0]
 39: [1, 0, 0, 0, 1]
 40: [0, 1, 0, 0, 0]
 41: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 42: [1, 0, 1, 0]
 43: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 44: [0, 0, 0, 1, 0, 0]
 45: [2, 1]
 46: [0, 0, 0, 0, 0, 0, 0, 1, 0]
 47: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 48: [1, 0, 0, 0, 0]
 49: [0, 0, 2]
 50: [0, 2, 0]
 51: [1, 0, 0, 0, 0, 1]
 52: [0, 0, 0, 0, 1, 0, 0]
 53: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 54: [3, 0]
 55: [0, 1, 0, 1]
 56: [0, 0, 1, 0, 0, 0]
 57: [1, 0, 0, 0, 0, 0, 1]
 58: [0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 59: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 60: [1, 1, 0, 0]
 61: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 62: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 63: [2, 0, 1]
 64: [0, 0, 0, 0, 0, 0]
 65: [0, 1, 0, 0, 1]
 66: [1, 0, 0, 1, 0]
 67: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 68: [0, 0, 0, 0, 0, 1, 0, 0]
 69: [1, 0, 0, 0, 0, 0, 0, 1]
 70: [0, 1, 1, 0]
 71: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 72: [2, 0, 0, 0]
 73: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 74: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 75: [1, 2]
 76: [0, 0, 0, 0, 0, 0, 1, 0, 0]
 77: [0, 0, 1, 1]
 78: [1, 0, 0, 0, 1, 0]
 79: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 80: [0, 1, 0, 0, 0, 0]
 81: [4]
 82: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 83: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 84: [1, 0, 1, 0, 0]
 85: [0, 1, 0, 0, 0, 1]
 86: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 87: [1, 0, 0, 0, 0, 0, 0, 0, 1]
 88: [0, 0, 0, 1, 0, 0, 0]
 89: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 90: [2, 1, 0]
 91: [0, 0, 1, 0, 1]
 92: [0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
 93: [1, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 94: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 95: [0, 1, 0, 0, 0, 0, 1]
 96: [1, 0, 0, 0, 0, 0]
 97: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 98: [0, 0, 2, 0]
 99: [2, 0, 0, 1]
100: [0, 2, 0, 0]


问:
Expand roots into a polynomial

Challenge

Given the roots of a polynomial separated by spaces as input, output the expanded form of the polynomial.

For example, the input

```<code>1 2
</code>```

represents this equation:

```<code>(x-1)(x-2)
</code>```

And should output:

```<code>x^2-3x+2
</code>```

The exact format of output is not important, it can be:

```<code>1x^2+-3x^1+2x^0
</code>```

or:

```<code>0 0 0
1x^3+0x^2+0x^1+0
</code>```

or:

```<code>3 14 15 92
1x^4+-124x^3+3241x^2+-27954x^1+57960
</code>```

Scoring/Rules

eval and likes are disallowed.

You may use any version of Python or any other language.

答:
Sage, 38 bytes

lambda N:prod(x-t for t in N).expand()
```

Try it online

This defines an unnamed lambda that takes an iterable of roots as input and computes the product (x-x_n) for x_n in roots, then expands it.

ContentLicense: CC BY-SA 3.0

Title: Expand roots into a polynomial

Body:
Sage, 38 bytes

lambda N:prod(x-t for t in N).expand()

Try it online

This defines an unnamed lambda that takes an iterable of roots as input and computes the product (x-x_n) for x_n in roots, then expands it.


答:
Mathematica, 26 bytes

```<code>Expand@Product[x-k,{k,#}]&
</code>```

Mathematica has powerful polynomial builtins.

Usage

```<code>  f = Expand@Product[x-k,{k,#}]&
  f@{3, 14, 15, 92}
x^4 - 124 x^3 + 3241 x^2 - 27954 x + 57960
</code>```

Title: Expand roots into a polynomial

Body:
Challenge

Given the roots of a polynomial separated by spaces as input, output the expanded form of the polynomial.

For example, the input

```<code>1 2
</code>```

represents this equation:

```<code>(x-1)(x-2)
</code>```

And should output:

```<code>x^2-3x+2
</code>```

The exact format of output is not important, it can be:

```<code>1x^2+-3x^1+2x^0
</code>```

or:

```<code>0 0 0
1x^3+0x^2+0x^1+0
</code>```

or:

```<code>3 14 15 92
1x^4+-124x^3+3241x^2+-27954x^1+57960
</code>```

Scoring/Rules

eval and likes are disallowed.

You may use any version of Python or any other language.

Body:
Mathematica, 26 bytes

Expand@Product[x-k,{k,#}]&

Mathematica has powerful polynomial builtins.

Usage

  f = Expand@Product[x-k,{k,#}]&
  f@{3, 14, 15, 92}
x^4 - 124 x^3 + 3241 x^2 - 27954 x + 57960


问:
Decompose a number!
Your task is to decompose a number using the format below.

This is similar to base conversion, except that instead of listing the digits in the base, you list the values, such that the list adds up to the input.

If the given base is \$n\$, then each number in the list must be in the form of \$k\times n^m\$, where \$0\le k<n\$ and \$m\$ is unique throughout the list.

Specs

Any reasonable input/output format. Your program/function takes 2 inputs and outputs a list.

Output list can be in any order.

0 can be excluded or included.

Leading 0s are allowed.

Built-ins are allowed.

Testcases

```<code>number base   converted list
input1 input2 output
123456 10     [100000,20000,3000,400,50,6] or [6,50,400,3000,20000,100000]
11     2      [8,2,1] or [0,0,0,0,8,0,2,1]
727    20     [400,320,7]
101    10     [100,1] or [100,0,1]
</code>```

Scoring

This is code-golf. Shortest solution in bytes wins.

答:
JavaScript (ES7), 68 bytes

n=>b=>(c=[...n.toString(b)]).map(d=>b**--p*parseInt(d,b),p=c.length)
```

<h2>Test</h2>

<p>Test uses <code>Math.pow</code> for browser compatibility.</p>

<p><div class="snippet" data-lang="js" data-hide="false">
<div class="snippet-code">
<pre class="snippet-code-js lang-js prettyprint-override"><code>f=n=>b=>(c=[...n.toString(b)]).map(d=>Math.pow(b,--p)*parseInt(d,b),p=c.length)
document.write("```"+
[ [ 123456, 10 ], [ 11, 2 ], [ 727, 20 ], [ 101, 10 ] ]
.map(c=>c+" => "+f(c[0])(c[1])).join`\n`)```

ContentLicense: CC BY-SA 4.0

Title: Decompose a number!

Body:
JavaScript (ES7), 68 bytes

n=>b=>(c=[...n.toString(b)]).map(d=>b**--p*parseInt(d,b),p=c.length)

Test

Test uses Math.pow for browser compatibility.

f=n=>b=>(c=[...n.toString(b)]).map(d=>Math.pow(b,--p)*parseInt(d,b),p=c.length)
document.write("<pre>"+
[ [ 123456, 10 ], [ 11, 2 ], [ 727, 20 ], [ 101, 10 ] ]
.map(c=>c+" => "+f(c[0])(c[1])).join`\n`)


Title: Map a list of indefinite size to a number!

Body:
It is well known, in the field of Mathematics studying infinity, that the Cartesian product of any finite amount of countable sets is also countable.

Your task is to write two programs to implement this, one to map from list to integer, one to map from integer to list.

Your function must be bijective and deterministic, meaning that 1 will always map to a certain list, and 2 will always map to another certain list, etc...

Earlier, we mapped integers to a list consisting only of 0 and 1.

However, now the list will consist of non-negative numbers.

Specs

Program/function, reasonable input/output format.

Whether the mapped integers start from 1 or starts from 0 is your choice, meaning that 0 doesn't have to (but may) map to anything.

The empty array [] must be encoded.

Input/output may be in any base.

Sharing code between the two functions is allowed.

Scoring

This is code-golf. Lowest score wins.

Score is the sum of lengths (in bytes) of the two programs/functions.

Body:
Python 2, 204 202 bytes

p=lambda x,y:(2*y+1<<x)-1
u=lambda n,x=0:-~n%2<1and u(-~n//2-1,x+1)or[x,n//2]
e=lambda l:l and-~reduce(p,l,len(l)-1)or 0
def d(n):
 if n<1:return[]
 r=[];n,l=u(n-1);exec"n,e=u(n);r=[e]+r;"*l;return[n]+r

Works by repeatedly applying a Z+ x Z+ <-> Z+ bijection, prepended by the list length.

0: []
1: [0]
2: [1]
3: [0, 0]
4: [2]
5: [0, 0, 0]
6: [1, 0]
7: [0, 0, 0, 0]
8: [3]
9: [0, 0, 0, 0, 0]
10: [1, 0, 0]
11: [0, 0, 0, 0, 0, 0]
12: [0, 1]
13: [0, 0, 0, 0, 0, 0, 0]
14: [1, 0, 0, 0]
15: [0, 0, 0, 0, 0, 0, 0, 0]
16: [4]
17: [0, 0, 0, 0, 0, 0, 0, 0, 0]
18: [1, 0, 0, 0, 0]
19: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
20: [0, 0, 1]
21: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
22: [1, 0, 0, 0, 0, 0]
23: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
24: [2, 0]
25: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
26: [1, 0, 0, 0, 0, 0, 0]
27: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
28: [0, 0, 0, 1]
29: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
30: [1, 0, 0, 0, 0, 0, 0, 0]
31: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]


问:
Build a word generator!
Your task is to create a program/function to replicate this word generator.

Details

Your program/function take two input. One input is the categories. The other input is the syllable types.

Categories

categories will consist of classes of letters.

For example, V=aeiou means that the letters a, e, i, o, and u will be classified under the category V.

Each category will have a 1-letter name in UPPERCASE.

The letters it contains will all be in lowercase.

Syllable types

For example CV would mean that the syllable will consist of a letter in category C and then a letter in category V.

For example, if C=bcd and V=ae, then the syllable can be ba, be, ca, ce, da, or de.

Your task

Your task is to generate 100 random words, each with a random length of 1-5 syllables, each chosen randomly in the syllable types, with the letter in each category chosen also randomly.

Specs

Any reasonable input/output format. I don't care how you input the list.

All inputs will be valid.

Scoring

This is code-golf. Shortest solution in bytes wins.

Testcase

```<code>input1          input2    output
"C=st;V=aeiou"  "CV/CVC"  tasiti tese tossi tesis titi sese saset su sosastesisat sisosis sissa sata to sisas sese satetot sisuta tatote sa tetsesuti sossut ti seso tese tostutsasussi tutiset sasates tasa ta sa satso tastitta tetti sesita setetat tatsi tisetot sassu sessiso satessase sas ses totasta si tetsit titse sase totas sa ta sasesa tasa sostat sesi sissa tato tos tate sustosussatta sustas sassatote tesas sutat tatetatossos testisot tatta tissisisa sasese sesatus tito sisa satas sasisi so sasatustu sosses tetsa tese sestit sestu tisot sutastot sesu tet sotte sisute setotitsesi tita
</code>```

答:
JavaScript (ES6), 136 bytes

document.write("```"+(

c=>s=>eval("for(r=Math.random,i=100,o=``;i--;o+=` `)for(j=r()*5;j-->0;)for(t=s[r(k=0)*s.length|0];l=t[k++];)o+=c[l][r()*c[l].length|0]")

)({ C: "st", V: "aeiou" })([ "CV", "CVC" ]))</code>```

Takes an object for the categories and an array for the syllable types.

Title: Build a word generator!

Body:
JavaScript (ES6), 136 bytes

document.write("<pre>"+(

c=>s=>eval("for(r=Math.random,i=100,o=``;i--;o+=` `)for(j=r()*5;j-->0;)for(t=s[r(k=0)*s.length|0];l=t[k++];)o+=c[l][r()*c[l].length|0]")

)({ C: "st", V: "aeiou" })([ "CV", "CVC" ]))

Takes an object for the categories and an array for the syllable types.


问:
Find the positive divisors!

Definition

A number is positive if it is greater than zero.

A number (A) is the divisor of another number (B) if A can divide B with no remainder.

For example, 2 is a divisor of 6 because 2 can divide 6 with no remainder.

Goal

Your task is to write a program/function that takes a positive number and then find all of its divisors.

Restriction

You may not use any built-in related to prime or factorization.

The complexity of your algorithm must not exceed O(sqrt(n)).

Freedom

The output list may contain duplicates.

The output list does not need to be sorted.

Scoring

This is code-golf. Shortest solution in bytes wins.

Testcases

```<code>input    output
1        1
2        1,2
6        1,2,3,6
9        1,3,9
</code>```

Title: Find the positive divisors!

Body:
Matlab, 48 bytes

n=input('');a=1:n^.5;b=mod(n,a)<1;[a(b),n./a(b)]


Title: Decompose a number!

Body:
Your task is to decompose a number using the format below.

This is similar to base conversion, except that instead of listing the digits in the base, you list the values, such that the list adds up to the input.

If the given base is \$n\$, then each number in the list must be in the form of \$k\times n^m\$, where \$0\le k<n\$ and \$m\$ is unique throughout the list.

Specs

Any reasonable input/output format. Your program/function takes 2 inputs and outputs a list.

Output list can be in any order.

0 can be excluded or included.

Leading 0s are allowed.

Built-ins are allowed.

Testcases

```<code>number base   converted list
input1 input2 output
123456 10     [100000,20000,3000,400,50,6] or [6,50,400,3000,20000,100000]
11     2      [8,2,1] or [0,0,0,0,8,0,2,1]
727    20     [400,320,7]
101    10     [100,1] or [100,0,1]
</code>```

Scoring

This is code-golf. Shortest solution in bytes wins.

Body:
JavaScript (ES6), 47 bytes

f=(n,b,p=1,q=b*p)=>[...n<q?[]:f(n,b,q),n%q-n%p]
document.write("<pre>"+
[ [ 123456, 10 ], [ 11, 2 ], [ 727, 20 ], [ 101, 10 ] ]
.map(c=>c+" => "+f(...c)).join`\n`)


答:
Mathematica, 50 bytes

Similar to @flawr's solution.

Performs trail division for x from 1 up to the square root of n and if divisible, saves it to a list as x and n / x.

```<code>(#2/#)~Join~#&@@{Cases[Range@Sqrt@#,x_/;x∣#],#}&
</code>```

Note that ∣ requires 3 bytes to represent in UTF-8, making the 48 character string require 50 bytes in UTF-8 representation.

Usage

```<code>  f = (#2/#)~Join~#&@@{Cases[Range@Sqrt@#,x_/;x∣#],#}&
  f[1]
{1, 1}
  f[2]
{2, 1}
  f[6]
{6, 3, 1, 2}
  f[9]
{9, 3, 1, 3}
</code>```

Title: Find the positive divisors!

Body:
Definition

A number is positive if it is greater than zero.

A number (A) is the divisor of another number (B) if A can divide B with no remainder.

For example, 2 is a divisor of 6 because 2 can divide 6 with no remainder.

Goal

Your task is to write a program/function that takes a positive number and then find all of its divisors.

Restriction

You may not use any built-in related to prime or factorization.

The complexity of your algorithm must not exceed O(sqrt(n)).

Freedom

The output list may contain duplicates.

The output list does not need to be sorted.

Scoring

This is code-golf. Shortest solution in bytes wins.

Testcases

```<code>input    output
1        1
2        1,2
6        1,2,3,6
9        1,3,9
</code>```

Body:
Mathematica, 50 bytes

Similar to @flawr's solution.

Performs trail division for x from 1 up to the square root of n and if divisible, saves it to a list as x and n / x.

(#2/#)~Join~#&@@{Cases[Range@Sqrt@#,x_/;x∣#],#}&

Note that ∣ requires 3 bytes to represent in UTF-8, making the 48 character string require 50 bytes in UTF-8 representation.

Usage

  f = (#2/#)~Join~#&@@{Cases[Range@Sqrt@#,x_/;x∣#],#}&
  f[1]
{1, 1}
  f[2]
{2, 1}
  f[6]
{6, 3, 1, 2}
  f[9]
{9, 3, 1, 3}


答:
JavaScript (ES6), 134 bytes

```<code>(c,s,r=s=>s[Math.random()*s.length|0],t="01234")=>[...Array(100)].map(_=>t.slice(r(t)).replace(/./g,_=>r(s)).replace(/./g,s=>r(c[s])))
</code>```

Explanation:

```<code>(c,s,                               // Parameters
 r=s=>s[Math.random()*s.length|0],  // Select random character
 t="01234"                          // Number of syllables to skip
)=>[...Array(100)].map(_=>          // Generate 100 words
 t.slice(r(t))                      // Skip random number of syllables
  .replace(/./g,_=>r(s))            // Select syllables randomly
  .replace(/./g,s=>r(c[s])))        // Select letters randomly
</code>```

Title: Build a word generator!

Body:
Your task is to create a program/function to replicate this word generator.

Details

Your program/function take two input. One input is the categories. The other input is the syllable types.

Categories

categories will consist of classes of letters.

For example, V=aeiou means that the letters a, e, i, o, and u will be classified under the category V.

Each category will have a 1-letter name in UPPERCASE.

The letters it contains will all be in lowercase.

Syllable types

For example CV would mean that the syllable will consist of a letter in category C and then a letter in category V.

For example, if C=bcd and V=ae, then the syllable can be ba, be, ca, ce, da, or de.

Your task

Your task is to generate 100 random words, each with a random length of 1-5 syllables, each chosen randomly in the syllable types, with the letter in each category chosen also randomly.

Specs

Any reasonable input/output format. I don't care how you input the list.

All inputs will be valid.

Scoring

This is code-golf. Shortest solution in bytes wins.

Testcase

```<code>input1          input2    output
"C=st;V=aeiou"  "CV/CVC"  tasiti tese tossi tesis titi sese saset su sosastesisat sisosis sissa sata to sisas sese satetot sisuta tatote sa tetsesuti sossut ti seso tese tostutsasussi tutiset sasates tasa ta sa satso tastitta tetti sesita setetat tatsi tisetot sassu sessiso satessase sas ses totasta si tetsit titse sase totas sa ta sasesa tasa sostat sesi sissa tato tos tate sustosussatta sustas sassatote tesas sutat tatetatossos testisot tatta tissisisa sasese sesatus tito sisa satas sasisi so sasatustu sosses tetsa tese sestit sestu tisot sutastot sesu tet sotte sisute setotitsesi tita
</code>```

Body:
JavaScript (ES6), 134 bytes

(c,s,r=s=>s[Math.random()*s.length|0],t="01234")=>[...Array(100)].map(_=>t.slice(r(t)).replace(/./g,_=>r(s)).replace(/./g,s=>r(c[s])))

Explanation:

(c,s,                               // Parameters
 r=s=>s[Math.random()*s.length|0],  // Select random character
 t="01234"                          // Number of syllables to skip
)=>[...Array(100)].map(_=>          // Generate 100 words
 t.slice(r(t))                      // Skip random number of syllables
  .replace(/./g,_=>r(s))            // Select syllables randomly
  .replace(/./g,s=>r(c[s])))        // Select letters randomly


Body:
Python 2, 88 bytes

d=lambda n:map(len,bin(n).split('1')[1:])
e=lambda l:int('1'.join(a*'0'for a in[2]+l),2)

Demo:

>>> for i in range(33):
...     print e(d(i)), d(i)
...
0 []
1 [0]
2 [1]
3 [0, 0]
4 [2]
5 [1, 0]
6 [0, 1]
7 [0, 0, 0]
8 [3]
9 [2, 0]
10 [1, 1]
11 [1, 0, 0]
12 [0, 2]
13 [0, 1, 0]
14 [0, 0, 1]
15 [0, 0, 0, 0]
16 [4]
17 [3, 0]
18 [2, 1]
19 [2, 0, 0]
20 [1, 2]
21 [1, 1, 0]
22 [1, 0, 1]
23 [1, 0, 0, 0]
24 [0, 3]
25 [0, 2, 0]
26 [0, 1, 1]
27 [0, 1, 0, 0]
28 [0, 0, 2]
29 [0, 0, 1, 0]
30 [0, 0, 0, 1]
31 [0, 0, 0, 0, 0]
32 [5]

Python 2, 130 bytes

Here’s a more “efficient” solution where the bit-length of the output is linear in the bit-length of the input rather than exponential.

def d(n):m=-(n^-n);return d(n/m/m)+[n/m%m+m-2]if n else[]
e=lambda l:int('0'+''.join(bin(2*a+5<<len(bin(a+2))-4)[3:]for a in l),2)


答:
JavaScript (ES6), <s>66</s> 62 bytes

```<code>f=(n,d=1)=>d*d>n?[]:d*d-n?n%d?f(n,d+1):[d,...f(n,d+1),n/d]:[d]
</code>```

I thought I'd write a version that returned a sorted deduplicated list, and it actually turned out to be 4 bytes shorter...

Title: Find the positive divisors!

Body:
JavaScript (ES6), <s>66</s> 62 bytes

f=(n,d=1)=>d*d>n?[]:d*d-n?n%d?f(n,d+1):[d,...f(n,d+1),n/d]:[d]

I thought I'd write a version that returned a sorted deduplicated list, and it actually turned out to be 4 bytes shorter...


问:
Find the n-th perfect power!
A perfect power is a number of the form \$a^b\$, where \$a>0\$ and \$b>1\$.

For example, \$125\$ is a perfect power because it can be expressed as \$5^3\$.

Goal

Your task is to write  a program/function that finds the \$n\$-th perfect power, given a positive integer \$n\$.

Specs

The first perfect power is \$1\$ (which is \$1^2\$).

Input/output in any reasonable format.

Built-ins are allowed.

Further information

OEIS A001597

Scoring

This is code-golf. Shortest solution in bytes wins.

Testcases

```<code>input  output
1      1
2      4
3      8
4      9
5      16
6      25
7      27
8      32
9      36
10     49
</code>```

答:
Mathematica, 34 bytes

```<code>(Union@@Array[#^#2#&,{#,#}])[[#]]&
</code>```

Generates an \$n\times n\$ array \$A_{ij} = i^{1+j}\$, flattens it, and returns the \$n\$th element.

Title: Find the n-th perfect power!

Body:
Mathematica, 34 bytes

(Union@@Array[#^#2#&,{#,#}])[[#]]&

Generates an \$n\times n\$ array \$A_{ij} = i^{1+j}\$, flattens it, and returns the \$n\$th element.


答:
Octave, <s>57</s> <s>31</s> 30 bytes

```<code>@(n)unique((1:n)'.^(2:n+1))(n)
</code>```

I just noticed again that Octave does not need ndgrid (while Matlab does)=)

Title: Find the n-th perfect power!

Body:
A perfect power is a number of the form \$a^b\$, where \$a>0\$ and \$b>1\$.

For example, \$125\$ is a perfect power because it can be expressed as \$5^3\$.

Goal

Your task is to write  a program/function that finds the \$n\$-th perfect power, given a positive integer \$n\$.

Specs

The first perfect power is \$1\$ (which is \$1^2\$).

Input/output in any reasonable format.

Built-ins are allowed.

Further information

OEIS A001597

Scoring

This is code-golf. Shortest solution in bytes wins.

Testcases

```<code>input  output
1      1
2      4
3      8
4      9
5      16
6      25
7      27
8      32
9      36
10     49
</code>```

Body:
Octave, <s>57</s> <s>31</s> 30 bytes

@(n)unique((1:n)'.^(2:n+1))(n)

I just noticed again that Octave does not need ndgrid (while Matlab does)=)


问:
Bijective mapping from integers to a variable number of trits

This challenge is a harder version of this one.

A variable number of trits is an array of 0 or more trits (a trit is a ternary digit). So [0, 2, 2, 1] is a variable number of trits, but so is [].

Write a function or program that, given an non-negative integer returns a variable number of trits such that every integer has a one-to-one (bijective) mapping with an array.

There are an infinite amount of such mappings, you are free to construct one as you please, but it must be one-to-one. Your mapping must conceptually be one-to-one for an arbitrarily sized integer, but it's OK if your implementation fails for large integers due to numerical limits of types in your preferred language (e.g. C's int).

As an example of what is not a one-to-one mapping, is simply listing the ternary digits of the integer. In such a system 5 becomes [1, 2] (because 1*3^1 + 2*3^0 = 5), but it's not one-to-one, because [0, 1, 2] also means 5 (because 0*3^2 + 1*3^1 + 2*3^0 = 5).

It should be fairly obvious that a mapping is not one-to-one if it skips an integer (e.g. it doesn't work for 5), but I'd like to make it clear that skipping a variable trit array is also not one-to-one. You must map to every possible variable trit array, including [].

Bonus challenge

You will be awarded the official Super Smaht® Award™ if your answer includes an algorithm (not necessarily in your golfed program) that not only works for base 2 or 3, but for all bases.

Shortest code in bytes wins.

答:
Jelly, 12 bytes

```<code>ḤR‘b3Ḣ’$Ðḟị@
</code>```

There is no empty list in Jelly; it is represented as 0 (an integer not a list).

For other bases: change Ḥ to ×n and b3 to bn, where n is the intended base.

Try it online!

Test suite.

For other bases

It only costs 11 bytes if given base as second input.

Try it online!

Test suite.

Algorithm

I thought of appending a 1 before the list and then convert it to a ternary.

That way, [0,0] will become 100 = 9 while [0,0,0] will become 1000 = 27.

However, a problem arises: that 2011 and 1011 both map to [0,1,1].

I only need numbers whose ternary representation starts with 1.

Therefore, I generated those whose ternary representation starts with 1, and then use their index instead.

That is, the list begins as [1, 3, 4, 5, 9, 10, 11, 12, 13, 14, 15, 16, 17, ...].

Therefore:

1 will be mapped to 1

2 will be mapped to 3

3 will be mapped to 4

4 will be mapped to 5

5 will be mapped to 9

n will be mapped to a(n) where a is that list.

There's another problem: both 0 and 1 are mapped to the empty list. Therefore, I removed 1 from the list, making a = [3, 4, 5, 9, 10, 11, 12, 13, 14, 15, 16, 17, ...].

Those are the integers whose ternary representation starts with 1, except 1.

The same algorithm can be applied to other bases.

Body:
Jelly, 12 bytes

ḤR‘b3Ḣ’$Ðḟị@

There is no empty list in Jelly; it is represented as 0 (an integer not a list).

For other bases: change Ḥ to ×n and b3 to bn, where n is the intended base.

Try it online!

Test suite.

For other bases

It only costs 11 bytes if given base as second input.

Try it online!

Test suite.

Algorithm

I thought of appending a 1 before the list and then convert it to a ternary.

That way, [0,0] will become 100 = 9 while [0,0,0] will become 1000 = 27.

However, a problem arises: that 2011 and 1011 both map to [0,1,1].

I only need numbers whose ternary representation starts with 1.

Therefore, I generated those whose ternary representation starts with 1, and then use their index instead.

That is, the list begins as [1, 3, 4, 5, 9, 10, 11, 12, 13, 14, 15, 16, 17, ...].

Therefore:

1 will be mapped to 1

2 will be mapped to 3

3 will be mapped to 4

4 will be mapped to 5

5 will be mapped to 9

n will be mapped to a(n) where a is that list.

There's another problem: both 0 and 1 are mapped to the empty list. Therefore, I removed 1 from the list, making a = [3, 4, 5, 9, 10, 11, 12, 13, 14, 15, 16, 17, ...].

Those are the integers whose ternary representation starts with 1, except 1.

The same algorithm can be applied to other bases.


答:
05AB1E, <s>14</s> 12 bytes

Code:

```<code>ÐtLDŠÖÏDŠ/ï«
</code>```

Explanation:

```<code>Ð             # Triplicate input.
 tL           # Push the list [1, ..., sqrt(input)].
   D          # Duplicate that list.
    Š         # Pop a,b,c and push c,a,b.
     Ö        # Check for each if a % b == 0.
      Ï       # Only keep the truthy elements.
       D      # Duplicate the list.
        Š     # Pop a,b,c and push c,a,b
         /ï   # Integer divide
           «  # Concatenate to the initial array and implicitly print.
</code>```

Uses CP-1252 encoding. Try it online!.

Title: Find the positive divisors!

Body:
05AB1E, <s>14</s> 12 bytes

Code:

ÐtLDŠÖÏDŠ/ï«

Explanation:

Ð             # Triplicate input.
 tL           # Push the list [1, ..., sqrt(input)].
   D          # Duplicate that list.
    Š         # Pop a,b,c and push c,a,b.
     Ö        # Check for each if a % b == 0.
      Ï       # Only keep the truthy elements.
       D      # Duplicate the list.
        Š     # Pop a,b,c and push c,a,b
         /ï   # Integer divide
           «  # Concatenate to the initial array and implicitly print.

Uses CP-1252 encoding. Try it online!.


答:
CJam, 16 bytes

```<code>ri_),_2f+ff#:|$=
</code>```

Test it here.

Explanation

This uses a similar idea to LegionMammal's Mathematica answer.

```<code>ri    e# Read input and convert to integer N.
_),   e# Duplicate, increment and turn into range [0 1 ... N].
_2f+  e# Duplicate and add two to each element to get [2 3 ... N+2].
ff#   e# Compute the outer product between both lists over exponentiation.
      e# This gives a bunch of perfect powers a^b for a ≥ 0, b > 1.
:|    e# Fold set union over the list, getting all unique powers generated this way.
$     e# Sort them.
=     e# Retrieve the N+1'th power (because input is 1-based, but CJam's array access
      e# is 0-based, which is why we included 0 in the list of perfect powers.
</code>```

Title: Find the n-th perfect power!

Body:
CJam, 16 bytes

ri_),_2f+ff#:|$=

Test it here.

Explanation

This uses a similar idea to LegionMammal's Mathematica answer.

ri    e# Read input and convert to integer N.
_),   e# Duplicate, increment and turn into range [0 1 ... N].
_2f+  e# Duplicate and add two to each element to get [2 3 ... N+2].
ff#   e# Compute the outer product between both lists over exponentiation.
      e# This gives a bunch of perfect powers a^b for a ≥ 0, b > 1.
:|    e# Fold set union over the list, getting all unique powers generated this way.
$     e# Sort them.
=     e# Retrieve the N+1'th power (because input is 1-based, but CJam's array access
      e# is 0-based, which is why we included 0 in the list of perfect powers.


答:
J, 29 bytes

Based on the @LegionMammal978's method.

```<code><:{[:/:~@~.[:,/[:(^/>:)~>:@i.
</code>```

Usage

```<code>   f =: <:{[:/:~@~.[:,/[:(^/>:)~>:@i.
   f " 0 (1 2 3 4 5 6 7 8 9 10)
1 4 8 9 16 25 27 32 36 49
</code>```

Explanation

```<code><:{[:/:~@~.[:,/[:(^/>:)~>:@i.
                           i.  Create range from 0 to n-1
                        >:     Increments each in that range, now is 1 to n
               [:              Cap, Ignores input n
                    >:         New range, increment from previous range to be 2 to n+1 now
                  ^/           Forms table using exponentation between 1..n and 2..n+1
             ,/                Flattens table to a list
         ~.                    Takes only distinct items
     /:~                       Sorts the list
<:                             Decrements the input n (since list is zero-based index)
  {                            Selects value from resulting list at index n-1
</code>```

Title: Find the n-th perfect power!

Body:
J, 29 bytes

Based on the @LegionMammal978's method.

<:{[:/:~@~.[:,/[:(^/>:)~>:@i.

Usage

   f =: <:{[:/:~@~.[:,/[:(^/>:)~>:@i.
   f " 0 (1 2 3 4 5 6 7 8 9 10)
1 4 8 9 16 25 27 32 36 49

Explanation

<:{[:/:~@~.[:,/[:(^/>:)~>:@i.
                           i.  Create range from 0 to n-1
                        >:     Increments each in that range, now is 1 to n
               [:              Cap, Ignores input n
                    >:         New range, increment from previous range to be 2 to n+1 now
                  ^/           Forms table using exponentation between 1..n and 2..n+1
             ,/                Flattens table to a list
         ~.                    Takes only distinct items
     /:~                       Sorts the list
<:                             Decrements the input n (since list is zero-based index)
  {                            Selects value from resulting list at index n-1


答:
Pyth, 6 bytes

```<code>tjyhQ3
</code>```

Explanation:

```<code>    Q    Input number.
   h     Add 1.
  y      Multiply by 2.
 j   3   Convert to base 3 as a list.
t        Remove the first element.
</code>```

Test suite

Inverse function: Pyth, 14 bytes

```<code>t/i+-2%sQ2Q3 2
</code>```

Explanation:

```<code>        Q        Input list.
       s         Sum.
      %  2       Modulo 2.
    -2           Subtract from 2.
   +      Q      Prepend to input list.
  i        3     Convert from base 3.
 /           2   Divide by 2.
t                Subtract 1.
</code>```

Test suite

The bijection looks like this:

```<code>0: []
1: [1]
2: [0]
3: [2]
4: [0, 1]
5: [1, 0]
6: [1, 2]
7: [2, 1]
8: [0, 0]
9: [0, 2]
10: [1, 1]
11: [2, 0]
12: [2, 2]
13: [0, 0, 1]
14: [0, 1, 0]
15: [0, 1, 2]
16: [0, 2, 1]
17: [1, 0, 0]
18: [1, 0, 2]
19: [1, 1, 1]
⋮
</code>```

General base

To make this work in any base b, simply replace 3 with b, 2 with (b − 1), and y with *(b − 1).

Title: Bijective mapping from integers to a variable number of trits

Body:
This challenge is a harder version of this one.

A variable number of trits is an array of 0 or more trits (a trit is a ternary digit). So [0, 2, 2, 1] is a variable number of trits, but so is [].

Write a function or program that, given an non-negative integer returns a variable number of trits such that every integer has a one-to-one (bijective) mapping with an array.

There are an infinite amount of such mappings, you are free to construct one as you please, but it must be one-to-one. Your mapping must conceptually be one-to-one for an arbitrarily sized integer, but it's OK if your implementation fails for large integers due to numerical limits of types in your preferred language (e.g. C's int).

As an example of what is not a one-to-one mapping, is simply listing the ternary digits of the integer. In such a system 5 becomes [1, 2] (because 1*3^1 + 2*3^0 = 5), but it's not one-to-one, because [0, 1, 2] also means 5 (because 0*3^2 + 1*3^1 + 2*3^0 = 5).

It should be fairly obvious that a mapping is not one-to-one if it skips an integer (e.g. it doesn't work for 5), but I'd like to make it clear that skipping a variable trit array is also not one-to-one. You must map to every possible variable trit array, including [].

Bonus challenge

You will be awarded the official Super Smaht® Award™ if your answer includes an algorithm (not necessarily in your golfed program) that not only works for base 2 or 3, but for all bases.

Shortest code in bytes wins.

Body:
Pyth, 6 bytes

tjyhQ3

Explanation:

    Q    Input number.
   h     Add 1.
  y      Multiply by 2.
 j   3   Convert to base 3 as a list.
t        Remove the first element.

Test suite

Inverse function: Pyth, 14 bytes

t/i+-2%sQ2Q3 2

Explanation:

        Q        Input list.
       s         Sum.
      %  2       Modulo 2.
    -2           Subtract from 2.
   +      Q      Prepend to input list.
  i        3     Convert from base 3.
 /           2   Divide by 2.
t                Subtract 1.

Test suite

The bijection looks like this:

0: []
1: [1]
2: [0]
3: [2]
4: [0, 1]
5: [1, 0]
6: [1, 2]
7: [2, 1]
8: [0, 0]
9: [0, 2]
10: [1, 1]
11: [2, 0]
12: [2, 2]
13: [0, 0, 1]
14: [0, 1, 0]
15: [0, 1, 2]
16: [0, 2, 1]
17: [1, 0, 0]
18: [1, 0, 2]
19: [1, 1, 1]
⋮

General base

To make this work in any base b, simply replace 3 with b, 2 with (b − 1), and y with *(b − 1).


答:
CJam, 16 bytes

```<code>{1$b\1$,,f#W%.*}
</code>```

An unnamed block that expects the base and the number on top of the stack (in that order) and replaces them with the digit list (including internal zeros, without leading zeros).

Test it here.

Explanation

```<code>1$  e# Copy base b.
b   e# Compute base-b digits of input number.
\   e# Swap digit list with other copy of b.
1$  e# Copy digit list.
,   e# Get number of digits M.
,   e# Turn into range [0 1 ... M-1].
f#  e# Map b^() over this range, computing all necessary powers of b.
W%  e# Reverse the list of powers.
.*  e# Multiply each digit by the corresponding power.
</code>```

Title: Decompose a number!

Body:
Your task is to decompose a number using the format below.

This is similar to base conversion, except that instead of listing the digits in the base, you list the values, such that the list adds up to the input.

If the given base is \$n\$, then each number in the list must be in the form of \$k\times n^m\$, where \$0\le k<n\$ and \$m\$ is unique throughout the list.

Specs

Any reasonable input/output format. Your program/function takes 2 inputs and outputs a list.

Output list can be in any order.

0 can be excluded or included.

Leading 0s are allowed.

Built-ins are allowed.

Testcases

```<code>number base   converted list
input1 input2 output
123456 10     [100000,20000,3000,400,50,6] or [6,50,400,3000,20000,100000]
11     2      [8,2,1] or [0,0,0,0,8,0,2,1]
727    20     [400,320,7]
101    10     [100,1] or [100,0,1]
</code>```

Scoring

This is code-golf. Shortest solution in bytes wins.

Body:
CJam, 16 bytes

{1$b\1$,,f#W%.*}

An unnamed block that expects the base and the number on top of the stack (in that order) and replaces them with the digit list (including internal zeros, without leading zeros).

Test it here.

Explanation

1$  e# Copy base b.
b   e# Compute base-b digits of input number.
\   e# Swap digit list with other copy of b.
1$  e# Copy digit list.
,   e# Get number of digits M.
,   e# Turn into range [0 1 ... M-1].
f#  e# Map b^() over this range, computing all necessary powers of b.
W%  e# Reverse the list of powers.
.*  e# Multiply each digit by the corresponding power.


问:
Calculate ISBN-13 check digit
Write a function which, given the first 12 digits of an ISBN-13 code, will calculate the entire ISBN via calculating and appending an appropriate check digit.

Your function's input is a string containing the first 12 digits of the ISBN. Its output is a string containing all 13 digits.

Formal specification

Write a function which, when given a string s consisting entirely of exactly 12 decimal digits (and no other characters), returns a string t with the following properties:

t consists of exactly 13 decimal digits (and no other characters);

s is a prefix of t;

the sum of all digits in odd positions in t (i.e. the first, third, fifth, etc.), plus three times the sum of all digits in even positions in t (i.e. the second, fourth, sixth, etc), is a multiple of 10.

Example / test case

Input

978030640615

Output

9780306406157

Victory condition

As a code-golf challenge, the shortest answer wins.

答:
Java - 161 Characters :(

```<code>int b[]=new int[a.length];
int d=0,n=0,j=1;
for(char c:a.toCharArray())b[d++]=Integer.valueOf(c+"");
for(int i:b)n+=(j++%2==0)?(i*3):(i*1);
return a+(10-(n%10));
</code>```

Title: Calculate ISBN-13 check digit

Body:
Java - 161 Characters :(

int b[]=new int[a.length];
int d=0,n=0,j=1;
for(char c:a.toCharArray())b[d++]=Integer.valueOf(c+"");
for(int i:b)n+=(j++%2==0)?(i*3):(i*1);
return a+(10-(n%10));


答:
MATL, 12 bytes

```<code>tX^:\~ftGw/h
</code>```

The approach is similar to that in @flawr's answer.

Try it online!

Explanation

```<code>t      % take input N. Duplicate.
X^:    % Generate range from 1 to sqrt(N)
\      % modulo (remainder of division)
~f     % indices of zero values: array of divisors up to sqrt(N)
tGw/   % element-wise divide input by those divisors, to produce rest of divisors
h      % concatenate both arrays horizontally
</code>```

Title: Find the positive divisors!

Body:
Definition

A number is positive if it is greater than zero.

A number (A) is the divisor of another number (B) if A can divide B with no remainder.

For example, 2 is a divisor of 6 because 2 can divide 6 with no remainder.

Goal

Your task is to write a program/function that takes a positive number and then find all of its divisors.

Restriction

You may not use any built-in related to prime or factorization.

The complexity of your algorithm must not exceed O(sqrt(n)).

Freedom

The output list may contain duplicates.

The output list does not need to be sorted.

Scoring

This is code-golf. Shortest solution in bytes wins.

Testcases

```<code>input    output
1        1
2        1,2
6        1,2,3,6
9        1,3,9
</code>```

Body:
MATL, 12 bytes

tX^:\~ftGw/h

The approach is similar to that in @flawr's answer.

Try it online!

Explanation

t      % take input N. Duplicate.
X^:    % Generate range from 1 to sqrt(N)
\      % modulo (remainder of division)
~f     % indices of zero values: array of divisors up to sqrt(N)
tGw/   % element-wise divide input by those divisors, to produce rest of divisors
h      % concatenate both arrays horizontally


答:
C#, 87 bytes

Golfed

String m(int v){var o="1";int i=1;while(++i<=v/2)if(v%i==0)o+=","+i;o+=","+v;return o;}
```
<hr />
<p><strong>Ungolfed</strong></p>
<pre class="lang-cs prettyprint-override"><code>String m( Int32 v ) {
    String o = "1";
    Int32 i = 1;

    while (++i <= v / 2)
        if (v % i == 0)
            o += "," + i;

    o += "," + v;

    return o;
}
</code>```

Full code

using System;
using System.Collections.Generic;

namespace N {
    class P {
        static void Main( string[] args ) {
            List<Int32> li = new List<Int32>() {
                1, 2, 6, 9,
            };

            foreach (Int32 i in li) {
                Console.WriteLine( i + " »> " + m( i ) );
            }

            Console.ReadLine();
        }

        static String m( Int32 v ) {
            String o = "1";
            Int32 i = 1;

            while (++i <= v / 2)
                if (v % i == 0)
                    o += "," + i;

            o += "," + v;

            return o;
        }
    }
}
```

Releases

v1.0 - 87 bytes - Initial solution.

Notes

In the Golfed code, I use var's and int's instead of String's and Int32's to make the code shorter, while in the Ungolfed Code and Full Code I use String's and Int32's to make the code more readable.

Title: Find the positive divisors!

Body:
C#, 87 bytes

Golfed

String m(int v){var o="1";int i=1;while(++i<=v/2)if(v%i==0)o+=","+i;o+=","+v;return o;}

Ungolfed

String m( Int32 v ) {
    String o = "1";
    Int32 i = 1;

    while (++i <= v / 2)
        if (v % i == 0)
            o += "," + i;

    o += "," + v;

    return o;
}

Full code

using System;
using System.Collections.Generic;

namespace N {
    class P {
        static void Main( string[] args ) {
            List<Int32> li = new List<Int32>() {
                1, 2, 6, 9,
            };

            foreach (Int32 i in li) {
                Console.WriteLine( i + " »> " + m( i ) );
            }

            Console.ReadLine();
        }

        static String m( Int32 v ) {
            String o = "1";
            Int32 i = 1;

            while (++i <= v / 2)
                if (v % i == 0)
                    o += "," + i;

            o += "," + v;

            return o;
        }
    }
}

Releases

v1.0 - 87 bytes - Initial solution.

Notes

In the Golfed code, I use var's and int's instead of String's and Int32's to make the code shorter, while in the Ungolfed Code and Full Code I use String's and Int32's to make the code more readable.


答:
Jelly, 6 bytes

```<code>‘Ḥb3ṫ2
</code>```

Translation of Kaseorg's answer in Pyth.

Try it online!

Hardcoded base: try it online!

Given base: try it online!

Body:
Jelly, 6 bytes

‘Ḥb3ṫ2

Translation of Kaseorg's answer in Pyth.

Try it online!

Hardcoded base: try it online!

Given base: try it online!


问:
Compute CRC32 Hash

Credits

This challenge originated from @miles.

Create a function that computes the CRC32 hash of an input string. The input will be an ASCII string of any length. The output will be the CRC32 hash of that input string.

Explanation

The algorithm of CRC32 and other CRC are essentially the same, so only CRC3 will be demonstrated here.

Firstly, you have the generator polynomial, which is actually a 4-bit [n+1] integer (would be 33-bit in CRC32).

In this example, the generator polynomial is 1101.

Then, you will have the string to be hashed, which in this example would be 00010010111100101011001101.

```<code>00010010111100101011001101|000 (1)    append three [n] "0"s
   1101                        (2)    align with highest bit
00001000111100101011001101|000 (3)    XOR (1) and (2)
    1101                       (4)    align with highest bit
00000101111100101011001101|000 (5)    XOR (3) and (4)
     1101                      (6)    align with highest bit
00000011011100101011001101|000 (7)    XOR (5) and (6)
      1101                     (8)    align with highest bit
00000000001100101011001101|000 (9)    XOR (7) and (8)
          1101                 (10)   align with highest bit
00000000000001101011001101|000 (11)   XOR (9) and (10)
             1101              (12)   align with highest bit
00000000000000000011001101|000 (13)   XOR (11) and (12)
                  1101         (14)   align with highest bit
00000000000000000000011101|000 (15)   XOR (13) and (14)
                     1101      (16)   align with highest bit
00000000000000000000000111|000 (17)   XOR (15) and (16)
                       110 1   (18)   align with highest bit
00000000000000000000000001|100 (19)   XOR (17) and (18)
                         1 101 (20)   align with highest bit
00000000000000000000000000|001 (21)   XOR (19) and (20)
^--------REGION 1--------^ ^2^
</code>```

The remainder obtained at (21), when region 1 is zero, which is 001, would be the result of the CRC3 hash.

Specs

The generator polynomial is 0x104C11DB7, or 0b100000100110000010001110110110111, or 4374732215.

Input can be a string or a list of integers, or any other reasonable format.

Output be a hex string or just an integer, or any other reasonable format.

Built-ins that compute the CRC32 hash are not allowed.

Goal

Standard rules for code-golf apply.

The shortest code wins.

Test cases

```<code>input         output      (hex)
"code-golf"   147743960   08CE64D8
"jelly"       1699969158  65537886
""            0           00000000
</code>```

答:
CJam, <s>37</s> 36 bytes

```<code>q256b32m<{Yb4374732215Yb.^Yb_Yb32>}g
</code>```

Test it here.

Explanation

```<code>q               e# Read input.
256b            e# Convert to single number by treating the character codes
                e# as base-256 digits.
32m<            e# Left-shift the number by 32 bits, effectively appending 32
                e# zeros to the binary representation.
{               e# While the condition on top of the stack is truthy...
  Yb            e#   Convert the number to base 2.
  4374732215Yb  e#   Convert the polynomial to base 2.
  .^            e#   Take the bitwise XOR. If the number is longer than the
                e#   polynomial, the remaining bits will be left unchanged.
  Yb            e#   Convert the list back from base 2, effectively stripping
                e#   leading zeros for the next iteration.
  _             e#   Duplicate the result.
  Yb            e#   Convert back to base 2.
  32>           e#   Remove the first 32 bits. If any are left, continue the loop.
}g
</code>```

Title: Compute CRC32 Hash

Body:
CJam, <s>37</s> 36 bytes

q256b32m<{Yb4374732215Yb.^Yb_Yb32>}g

Test it here.

Explanation

q               e# Read input.
256b            e# Convert to single number by treating the character codes
                e# as base-256 digits.
32m<            e# Left-shift the number by 32 bits, effectively appending 32
                e# zeros to the binary representation.
{               e# While the condition on top of the stack is truthy...
  Yb            e#   Convert the number to base 2.
  4374732215Yb  e#   Convert the polynomial to base 2.
  .^            e#   Take the bitwise XOR. If the number is longer than the
                e#   polynomial, the remaining bits will be left unchanged.
  Yb            e#   Convert the list back from base 2, effectively stripping
                e#   leading zeros for the next iteration.
  _             e#   Duplicate the result.
  Yb            e#   Convert back to base 2.
  32>           e#   Remove the first 32 bits. If any are left, continue the loop.
}g


答:
CJam, 9 bytes

```<code>ri)_+3b(;
</code>```

Translation of Kaseorg's answer in Pyth.

Try it online!

Body:
CJam, 9 bytes

ri)_+3b(;

Translation of Kaseorg's answer in Pyth.

Try it online!


答:
Pyth, 28 bytes

```<code>uhS+GmxG.<C"Á·"dlhG.<Cz32
</code>```

Try it online: Demonstration or Test Suite

Explanation:

```<code>uhS+GmxG.<C"..."dlhG.<Cz32   implicit: z = input string
                      Cz     convert to number
                    .<  32   shift it by 32 bits
u                            apply the following expression to G = ^,
                             until it get stuck in a loop:
     m           lhG            map each d in range(0, log2(G+1)) to:
          C"..."                   convert this string to a number (4374732215)
        .<      d                  shift it by d bits
      xG                           xor with G
   +G                           add G to this list
 hS                             take the minimum as new G
</code>```

Title: Compute CRC32 Hash

Body:
Credits

This challenge originated from @miles.

Create a function that computes the CRC32 hash of an input string. The input will be an ASCII string of any length. The output will be the CRC32 hash of that input string.

Explanation

The algorithm of CRC32 and other CRC are essentially the same, so only CRC3 will be demonstrated here.

Firstly, you have the generator polynomial, which is actually a 4-bit [n+1] integer (would be 33-bit in CRC32).

In this example, the generator polynomial is 1101.

Then, you will have the string to be hashed, which in this example would be 00010010111100101011001101.

```<code>00010010111100101011001101|000 (1)    append three [n] "0"s
   1101                        (2)    align with highest bit
00001000111100101011001101|000 (3)    XOR (1) and (2)
    1101                       (4)    align with highest bit
00000101111100101011001101|000 (5)    XOR (3) and (4)
     1101                      (6)    align with highest bit
00000011011100101011001101|000 (7)    XOR (5) and (6)
      1101                     (8)    align with highest bit
00000000001100101011001101|000 (9)    XOR (7) and (8)
          1101                 (10)   align with highest bit
00000000000001101011001101|000 (11)   XOR (9) and (10)
             1101              (12)   align with highest bit
00000000000000000011001101|000 (13)   XOR (11) and (12)
                  1101         (14)   align with highest bit
00000000000000000000011101|000 (15)   XOR (13) and (14)
                     1101      (16)   align with highest bit
00000000000000000000000111|000 (17)   XOR (15) and (16)
                       110 1   (18)   align with highest bit
00000000000000000000000001|100 (19)   XOR (17) and (18)
                         1 101 (20)   align with highest bit
00000000000000000000000000|001 (21)   XOR (19) and (20)
^--------REGION 1--------^ ^2^
</code>```

The remainder obtained at (21), when region 1 is zero, which is 001, would be the result of the CRC3 hash.

Specs

The generator polynomial is 0x104C11DB7, or 0b100000100110000010001110110110111, or 4374732215.

Input can be a string or a list of integers, or any other reasonable format.

Output be a hex string or just an integer, or any other reasonable format.

Built-ins that compute the CRC32 hash are not allowed.

Goal

Standard rules for code-golf apply.

The shortest code wins.

Test cases

```<code>input         output      (hex)
"code-golf"   147743960   08CE64D8
"jelly"       1699969158  65537886
""            0           00000000
</code>```

Body:
Pyth, 28 bytes

uhS+GmxG.<C"Á·"dlhG.<Cz32

Try it online: Demonstration or Test Suite

Explanation:

uhS+GmxG.<C"..."dlhG.<Cz32   implicit: z = input string
                      Cz     convert to number
                    .<  32   shift it by 32 bits
u                            apply the following expression to G = ^,
                             until it get stuck in a loop:
     m           lhG            map each d in range(0, log2(G+1)) to:
          C"..."                   convert this string to a number (4374732215)
        .<      d                  shift it by d bits
      xG                           xor with G
   +G                           add G to this list
 hS                             take the minimum as new G


答:
Retina, 17 + 23 = 40 bytes

From list to integer:

```<code>\d+
$&$*0
^
1

1
</code>```

Try it online!

From integer to list:

```<code>^1

S`1
m`^(0*)
$.1
¶
<space>
</code>```

Try it online!

Uses Kaseorg's Algorithm.

Body:
It is well known, in the field of Mathematics studying infinity, that the Cartesian product of any finite amount of countable sets is also countable.

Your task is to write two programs to implement this, one to map from list to integer, one to map from integer to list.

Your function must be bijective and deterministic, meaning that 1 will always map to a certain list, and 2 will always map to another certain list, etc...

Earlier, we mapped integers to a list consisting only of 0 and 1.

However, now the list will consist of non-negative numbers.

Specs

Program/function, reasonable input/output format.

Whether the mapped integers start from 1 or starts from 0 is your choice, meaning that 0 doesn't have to (but may) map to anything.

The empty array [] must be encoded.

Input/output may be in any base.

Sharing code between the two functions is allowed.

Scoring

This is code-golf. Lowest score wins.

Score is the sum of lengths (in bytes) of the two programs/functions.

Body:
Retina, 17 + 23 = 40 bytes

From list to integer:

\d+
$&$*0
^
1

1

Try it online!

From integer to list:

^1

S`1
m`^(0*)
$.1
¶
<space>

Try it online!

Uses Kaseorg's Algorithm.


问:
Compute the Adler-32 checksum

Background

Adler-32 is a 32-bit checksum invented by Mark Adler in 1995 which is part of the widely used zlib library (also developed by Adler). Adler-32 is not as reliable as a 32-bit cyclic redundancy check, but – at least in software  – it is much faster and easier to implement.

Definition

Let B = [b1, ⋯, bn] be a byte array.

The Adler-32 checksum of B is defined as the result of low + 65536 × high, where:

low := ((1 + b1 + ⋯ + bn) mod 65521)

high := (((1 + b1) + (1 + b1 + b2) + ⋯ (1 + b1 + ⋯ + bn)) mod 65521)

Task

Given a byte array as input, compute and return its Adler-32 checksum, abiding to the following.

You can take the input as an array of bytes or integers, or as a string.

In both cases, only bytes corresponding to printable ASCII characters will occur in the input.

You may assume that the length of the input will satisfy 0 < length ≤ 4096.

If you choose to print the output, you may use any positive base up to and including 256.

If you choose unary, make sure interpreter can handle up to 232 - 983056 bytes of output on a machine with 16 GiB of RAM.

Built-ins that compute the Adler-32 checksum are forbidden.

Standard code-golf rules apply.

Test cases

```<code>String:     "Eagles are great!"
Byte array: [69, 97, 103, 108, 101, 115, 32, 97, 114, 101, 32, 103, 114, 101, 97, 116, 33]
Checksum:   918816254

String:     "Programming Puzzles & Code Golf"
Byte array: [80, 114, 111, 103, 114, 97, 109, 109, 105, 110, 103, 32, 80, 117, 122, 122, 108, 101, 115, 32, 38, 32, 67, 111, 100, 101, 32, 71, 111, 108, 102]
Checksum:   3133147946

String:     "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
Byte array: [126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126]
Checksum:   68095937

String:     <1040 question marks>
Byte array: <1040 copies of 63>
Checksum:   2181038080
</code>```

答:
Scala, 94 Bytes

```<code>(s:String)=>{
val t=((1L,0L)/:s){(r,c)=>val a=(c+r._1)%65521
(a,(a+r._2)%65521)};t._1+(t._2<<16)
}
</code>```

Performs Adler-32 Checksum on Strings, using the alternate for foldLeft, /:

Title: Compute the Adler-32 checksum

Body:
Scala, 94 Bytes

(s:String)=>{
val t=((1L,0L)/:s){(r,c)=>val a=(c+r._1)%65521
(a,(a+r._2)%65521)};t._1+(t._2<<16)
}

Performs Adler-32 Checksum on Strings, using the alternate for foldLeft, /:


答:
Lua, 83 bytes

```<code>s=''x=io.read()for i=1,x do if x%i==0 then s=s..i..', 'end end print(s:sub(1,#s-2))
</code>```

I couldn't do better, unfortunately

Title: Find the positive divisors!

Body:
Lua, 83 bytes

s=''x=io.read()for i=1,x do if x%i==0 then s=s..i..', 'end end print(s:sub(1,#s-2))

I couldn't do better, unfortunately


问:
Find the number of ways to choose `n` objects from `r` objects with repetition so that every object has a matching neighbour
For example, if n is 5 and r is 2, it would mean the number of lists below:

```<code>[1,1,1,1,1]
[1,1,1,2,2]
[1,1,2,2,2]
[2,2,1,1,1]
[2,2,2,1,1]
[2,2,2,2,2]
</code>```

which is 6.

If n is 4 and r is 3:

```<code>[1,1,1,1]
[1,1,2,2]
[1,1,3,3]
[2,2,1,1]
...
[3,3,3,3]
</code>```

which is 9.

where each item has a neighbour whose value is the same.

For example, [1,2,1,1,2] is not counted, because both 2 are alone.

Goal

Your task is to write a program/function which takes two inputs in any order, and which produces the required output.

Detail

You can assume that r≥2.

Scoring

This is code-golf. Shortest solution in bytes wins.

Bonus

Multiply your score by 0.3 if the complexity of your program is below O(e^n).

For example, 10 bytes becomes 3 bytes.

Testcases

Can be generated from this Pyth test suite.

Usage: two lines per testcase, n on top, r below.

```<code>n r output
2 5 5
4 4 16
6 3 33
8 2 26
</code>```

Additional information

When r=2: OEIS A006355.

答:
Pyth, 14 bytes * 0.3 = 4.2 bytes

```<code>*Quh*~+ZGtQtE0
</code>```

Try it online: Demonstration. Input r on the first line and n on the second line.

Complexity is O(n).

Explanation:

Let f(n, r) be the number of ways to create such a list with the last number being 0. Obviously it doesn't matter if we take 0 or any other number.

It's easy to see, that the following recursion holds:

```<code>f(n, r) = 0                                  ... if n < 2
f(n, r) = sum(f(i, r), i <= n-2) * (r-1) + 1 ... otherwise
</code>```

If n == 0, than the list cannot end with the number 0. If n == 1, than the only number in the list has no neighbor. Therefore both cases have the value zero.

If n >= 2, than it could end in 2, 3, ... n zeros. The digit before the last zero can be any of the number 1, 2, ..., r-1. These are r-1 possibilities. Therefore I'll add up all f(i,n) and multiply by r-1. At the end I'll have to add 1 (for the case that all digits are zeros).

The result to the question than is: r * f(n, r), since the list can end in any of the r numbers.

In my code I make use of the predefined variable Z = 0. It will contain the last computed sum so far.

```<code>*Quh*~+ZGtQtE0   implicit: Q = first input number (r)
  u        tE0   start with G=0, do the following input-1 (n-1) times:
     ~+ZG           add G to Z
   h*~ Z tQ         and update G to the value Z*(Q-1) + 1
                    (using the old value of Z)
*Q               multiply the result with Q
</code>```

Body:
Pyth, 14 bytes * 0.3 = 4.2 bytes

*Quh*~+ZGtQtE0

Try it online: Demonstration. Input r on the first line and n on the second line.

Complexity is O(n).

Explanation:

Let f(n, r) be the number of ways to create such a list with the last number being 0. Obviously it doesn't matter if we take 0 or any other number.

It's easy to see, that the following recursion holds:

f(n, r) = 0                                  ... if n < 2
f(n, r) = sum(f(i, r), i <= n-2) * (r-1) + 1 ... otherwise

If n == 0, than the list cannot end with the number 0. If n == 1, than the only number in the list has no neighbor. Therefore both cases have the value zero.

If n >= 2, than it could end in 2, 3, ... n zeros. The digit before the last zero can be any of the number 1, 2, ..., r-1. These are r-1 possibilities. Therefore I'll add up all f(i,n) and multiply by r-1. At the end I'll have to add 1 (for the case that all digits are zeros).

The result to the question than is: r * f(n, r), since the list can end in any of the r numbers.

In my code I make use of the predefined variable Z = 0. It will contain the last computed sum so far.

*Quh*~+ZGtQtE0   implicit: Q = first input number (r)
  u        tE0   start with G=0, do the following input-1 (n-1) times:
     ~+ZG           add G to Z
   h*~ Z tQ         and update G to the value Z*(Q-1) + 1
                    (using the old value of Z)
*Q               multiply the result with Q


问:
Counting triangles with integer perimeter
Mary has given John two sticks of lengths a and b respectively, where a and b are positive integers.

John is very curious.

He would like to know how many triangles with integer perimeter can be formed, by having one additional side.

Please help him find it out.

(This is my first time composing this kind of stupid stories in coding problems, so forgive me if it is too stupid.)

Specs

Given two integers a and b, find the number of triangles with integer perimeter that can be formed, by having one additional side.

Details

Congruent triangles are congruent.

Flat triangles are flat out uncounted.

Zero-sided triangles are counted zero times.

Scoring

This is code-golf. Shortest solution in bytes wins.

Testcases

```<code>a b output
1 2 1
3 3 5
9 7 13
</code>```

答:
Javascript full program <s>88</s> 42 bytes

```<code>a=prompt();b=prompt();alert((a<b?a:b)*2-1)
</code>```

I hate prompts, even java is better in that aspect.

Javascript function <s>73</s> <s>31</s> 21 bytes

```<code>(a,b)=>(a<b?a:b)*2-1
</code>```

Testable version:

c=(a,b)=>(a<b?a:b)*2-1

var d = prompt("enter first number");
var e = prompt("enter second number");
alert(c(d, e));```

Thanks to @Neil for saving 8 bytes.
Thanks goes to @MartinBüttner for the algorithm and for saving 1 byte.

Body:
Javascript full program <s>88</s> 42 bytes

a=prompt();b=prompt();alert((a<b?a:b)*2-1)

I hate prompts, even java is better in that aspect.

Javascript function <s>73</s> <s>31</s> 21 bytes

(a,b)=>(a<b?a:b)*2-1

Testable version:

c=(a,b)=>(a<b?a:b)*2-1

var d = prompt("enter first number");
var e = prompt("enter second number");
alert(c(d, e));

Thanks to @Neil for saving 8 bytes.
Thanks goes to @MartinBüttner for the algorithm and for saving 1 byte.


答:
CJam, 7 bytes

```<code>l~e<2*(
</code>```

Test it here.

Explanation

```<code>l~  e# Read and evaluate input.
e<  e# min(a,b).
2*  e# Double.
(   e# Decrement.
</code>```

For a proof of correctness, see my Jelly answer which uses the same algorithm.

Title: Counting triangles with integer perimeter

Body:
Mary has given John two sticks of lengths a and b respectively, where a and b are positive integers.

John is very curious.

He would like to know how many triangles with integer perimeter can be formed, by having one additional side.

Please help him find it out.

(This is my first time composing this kind of stupid stories in coding problems, so forgive me if it is too stupid.)

Specs

Given two integers a and b, find the number of triangles with integer perimeter that can be formed, by having one additional side.

Details

Congruent triangles are congruent.

Flat triangles are flat out uncounted.

Zero-sided triangles are counted zero times.

Scoring

This is code-golf. Shortest solution in bytes wins.

Testcases

```<code>a b output
1 2 1
3 3 5
9 7 13
</code>```

Body:
CJam, 7 bytes

l~e<2*(

Test it here.

Explanation

l~  e# Read and evaluate input.
e<  e# min(a,b).
2*  e# Double.
(   e# Decrement.

For a proof of correctness, see my Jelly answer which uses the same algorithm.


答:
Jelly, 3 bytes

```<code>«Ḥ’
</code>```

Try it online!

Explanation

```<code>«   min(a,b)
 Ḥ          *2
  ’           -1
</code>```

(Not quite rigorous) proof of correctness:

Let x = min(a,b) and y = max(a,b), and let z be a potential third side.

We can't have z ≤ y-x, because for z < y-x the triangle can't be closed and for z = y-x it would be degenerate. See triangle inequality.

We can't have z ≥ y+x, for the same reasons.

Every integer z in between is valid and gives a different triangle. That means we've got (y+x) - (y-x) - 1 = 2x - 1 different triangles.

Body:
Jelly, 3 bytes

«Ḥ’

Try it online!

Explanation

«   min(a,b)
 Ḥ          *2
  ’           -1

(Not quite rigorous) proof of correctness:

Let x = min(a,b) and y = max(a,b), and let z be a potential third side.

We can't have z ≤ y-x, because for z < y-x the triangle can't be closed and for z = y-x it would be degenerate. See triangle inequality.

We can't have z ≥ y+x, for the same reasons.

Every integer z in between is valid and gives a different triangle. That means we've got (y+x) - (y-x) - 1 = 2x - 1 different triangles.


答:
05AB1E, 3 bytes

Using @MartinBüttner's algorithm. Code:

```<code>·<ß
</code>```

Explanation:

```<code>·    # Double the input.
 <   # Decrement by 1.
  ß  # Take the smallest value.
</code>```

Uses CP-1252 encoding. Try it online!.

Body:
05AB1E, 3 bytes

Using @MartinBüttner's algorithm. Code:

·<ß

Explanation:

·    # Double the input.
 <   # Decrement by 1.
  ß  # Take the smallest value.

Uses CP-1252 encoding. Try it online!.


答:
PHP 36 bytes

```<code>function($a,$b){echo min($a,$b)*2-1}
</code>```

Thanks goes to @MartinBüttner for the algorithm

Body:
PHP 36 bytes

function($a,$b){echo min($a,$b)*2-1}

Thanks goes to @MartinBüttner for the algorithm


答:
Retina, 14 bytes

```<code>M!`(1+) \1
 1

</code>```

Input and output in unary.

Try it online! (Modified to run multiple decimal test cases at once.)

Explanation

Still the same approach as my CJam and Jelly answers (the latter contains a proof of correctness), but this time using string processing of unary representations.

```<code>M!`(1+) \1
</code>```

This finds min(a,b) by matching the first string of 1s that can be found in both of them. This being a match stage and using the ! the result is actually min(a,b) min(a,b) since the entire match is written back.

```<code> 1

</code>```

This simply matches the separating a space and a single 1 and removes them. This leaves a string of 2*min(a,b) - 1 characters, which is the desired result.

Body:
Retina, 14 bytes

M!`(1+) \1
 1

Input and output in unary.

Try it online! (Modified to run multiple decimal test cases at once.)

Explanation

Still the same approach as my CJam and Jelly answers (the latter contains a proof of correctness), but this time using string processing of unary representations.

M!`(1+) \1

This finds min(a,b) by matching the first string of 1s that can be found in both of them. This being a match stage and using the ! the result is actually min(a,b) min(a,b) since the entire match is written back.

 1

This simply matches the separating a space and a single 1 and removes them. This leaves a string of 2*min(a,b) - 1 characters, which is the desired result.


答:
k (8 bytes)

Using the Jelly/CJam algorithm

```<code>-1+2*min
</code>```

e.g.

```<code>k)-1+2*(&). 10 10
19
</code>```

Body:
k (8 bytes)

Using the Jelly/CJam algorithm

-1+2*min

e.g.

k)-1+2*(&). 10 10
19


答:
Java <s>55</s> 42 bytes

```<code>int c(int a,int b){return (a<b?a:b)*2-1);}
</code>```

Body:
Java <s>55</s> 42 bytes

int c(int a,int b){return (a<b?a:b)*2-1);}


问:
Am I happy or sad?
You are trying to guess my emotion.

I will give you an adjective, as the input to the function/program.

Your task is to output my emotion, either :) for happy, or :( for sad.

Details

For these adjectives, you must output the happy face :)

```<code>contented
delighted
merry
overjoyed
pleased
blessed
chipper
content
convivial
gleeful
gratified
intoxicated
jolly
light
peppy
perky
playful
sparkling
sunny
</code>```

For these adjectives, you must output the sad face :(

```<code>melancholy
bitter
somber
dismal
mournful
blue
dejected
despairing
despondent
disconsolate
distressed
down
downcast
gloomy
glum
heavyhearted
lugubrious
morbid
morose
troubled
bereaved
</code>```

Other adjectives are undefined. You may output whatever you want for other adjectives.

Specs

All in lowercase. All matches regex ^[a-z]+$.

Scoring

This is code-golf. Shortest solution in bytes wins.

Tips

There is a trick.

答:
CJam, 9 bytes

```<code>':q,"()"=
</code>```

The "trick" is the parity of the word lengths.

Test it here.

Explanation

```<code>':     e# Push character ':'.
q,     e# Get length of input.
"()"=  e# Using length as cyclic index into "()", giving '(' for even lengths
       e# and ')' for odd lengths.
</code>```

Title: Am I happy or sad?

Body:
CJam, 9 bytes

':q,"()"=

The "trick" is the parity of the word lengths.

<a href="http://cjam.aditsu.net/#code=qN%2F%7B%3AQ%3B%0A%0A'%3AQ%2C%22()%22%3D%0A%0A%5DoNo%7D%2F&input=contented%0Adelighted%0Amerry%0Aoverjoyed%0Apleased%0Ablessed%0Achipper%0Acontent%0Aconvivial%0Agleeful%0Agratified%0Aintoxicated%0Ajolly%0Alight%0Apeppy%0Aperky%0Aplayful%0Asparkling%0Asunny%0Amelancholy%0Abitter%0Asomber%0Adismal%0Amournful%0Ablue%0Adejected%0Adespairing%0Adespondent%0Adisconsolate%0Adistressed%0Adown%0Adowncast%0Agloomy%0Aglum%0Aheavyhearted%0Alugubrious%0Amorbid%0Amorose%0Atroubled%0Abereaved" rel="nofollow">Test it here.

Explanation

':     e# Push character ':'.
q,     e# Get length of input.
"()"=  e# Using length as cyclic index into "()", giving '(' for even lengths
       e# and ')' for odd lengths.


答:
Fuzzy Octo Guacamole, 22 bytes

```<code>^!_2rm{':('0}i{':)'1}_
</code>```

Gets input, finds length%2, prints :) vs :( for on a remainder of 1 or 0.

Title: Am I happy or sad?

Body:
You are trying to guess my emotion.

I will give you an adjective, as the input to the function/program.

Your task is to output my emotion, either :) for happy, or :( for sad.

Details

For these adjectives, you must output the happy face :)

```<code>contented
delighted
merry
overjoyed
pleased
blessed
chipper
content
convivial
gleeful
gratified
intoxicated
jolly
light
peppy
perky
playful
sparkling
sunny
</code>```

For these adjectives, you must output the sad face :(

```<code>melancholy
bitter
somber
dismal
mournful
blue
dejected
despairing
despondent
disconsolate
distressed
down
downcast
gloomy
glum
heavyhearted
lugubrious
morbid
morose
troubled
bereaved
</code>```

Other adjectives are undefined. You may output whatever you want for other adjectives.

Specs

All in lowercase. All matches regex ^[a-z]+$.

Scoring

This is code-golf. Shortest solution in bytes wins.

Tips

There is a trick.

Body:
Fuzzy Octo Guacamole, 22 bytes

^!_2rm{':('0}i{':)'1}_

Gets input, finds length%2, prints :) vs :( for on a remainder of 1 or 0.


答:
Python 2, <s>60</s> 58 bytes

H=h=65521
l=1
for n in input():l+=n;h+=l
print h%H<<16|l%H
```

A pretty straightforward approach. This is a full program which takes a list of integers via STDIN, e.g. [72, 105, 33].

(Thanks to @xnor for the amazing aliasing/initialisation tip)

Title: Compute the Adler-32 checksum

Body:
Background

Adler-32 is a 32-bit checksum invented by Mark Adler in 1995 which is part of the widely used zlib library (also developed by Adler). Adler-32 is not as reliable as a 32-bit cyclic redundancy check, but – at least in software  – it is much faster and easier to implement.

Definition

Let B = [b1, ⋯, bn] be a byte array.

The Adler-32 checksum of B is defined as the result of low + 65536 × high, where:

low := ((1 + b1 + ⋯ + bn) mod 65521)

high := (((1 + b1) + (1 + b1 + b2) + ⋯ (1 + b1 + ⋯ + bn)) mod 65521)

Task

Given a byte array as input, compute and return its Adler-32 checksum, abiding to the following.

You can take the input as an array of bytes or integers, or as a string.

In both cases, only bytes corresponding to printable ASCII characters will occur in the input.

You may assume that the length of the input will satisfy 0 < length ≤ 4096.

If you choose to print the output, you may use any positive base up to and including 256.

If you choose unary, make sure interpreter can handle up to 232 - 983056 bytes of output on a machine with 16 GiB of RAM.

Built-ins that compute the Adler-32 checksum are forbidden.

Standard code-golf rules apply.

Test cases

```<code>String:     "Eagles are great!"
Byte array: [69, 97, 103, 108, 101, 115, 32, 97, 114, 101, 32, 103, 114, 101, 97, 116, 33]
Checksum:   918816254

String:     "Programming Puzzles & Code Golf"
Byte array: [80, 114, 111, 103, 114, 97, 109, 109, 105, 110, 103, 32, 80, 117, 122, 122, 108, 101, 115, 32, 38, 32, 67, 111, 100, 101, 32, 71, 111, 108, 102]
Checksum:   3133147946

String:     "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
Byte array: [126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126]
Checksum:   68095937

String:     <1040 question marks>
Byte array: <1040 copies of 63>
Checksum:   2181038080
</code>```

Body:
Python 2, <s>60</s> 58 bytes

H=h=65521
l=1
for n in input():l+=n;h+=l
print h%H<<16|l%H

A pretty straightforward approach. This is a full program which takes a list of integers via STDIN, e.g. [72, 105, 33].

(Thanks to @xnor for the amazing aliasing/initialisation tip)


Title: Find the number of ways to choose `n` objects from `r` objects with repetition so that every object has a matching neighbour

Body:
For example, if n is 5 and r is 2, it would mean the number of lists below:

```<code>[1,1,1,1,1]
[1,1,1,2,2]
[1,1,2,2,2]
[2,2,1,1,1]
[2,2,2,1,1]
[2,2,2,2,2]
</code>```

which is 6.

If n is 4 and r is 3:

```<code>[1,1,1,1]
[1,1,2,2]
[1,1,3,3]
[2,2,1,1]
...
[3,3,3,3]
</code>```

which is 9.

where each item has a neighbour whose value is the same.

For example, [1,2,1,1,2] is not counted, because both 2 are alone.

Goal

Your task is to write a program/function which takes two inputs in any order, and which produces the required output.

Detail

You can assume that r≥2.

Scoring

This is code-golf. Shortest solution in bytes wins.

Bonus

Multiply your score by 0.3 if the complexity of your program is below O(e^n).

For example, 10 bytes becomes 3 bytes.

Testcases

Can be generated from this Pyth test suite.

Usage: two lines per testcase, n on top, r below.

```<code>n r output
2 5 5
4 4 16
6 3 33
8 2 26
</code>```

Additional information

When r=2: OEIS A006355.

Body:
JavaScript (ES6), 64 (70 * 0.3 = 21) bytes

(n,r)=>[...Array(n)].map((m,i,a)=>a[i+2]=(s=s+m|0)*~-r+r).slice(-2)[0]

Now runs in linear time!


答:
JavaScript, 75 bytes

```<code>(a,b)=>[...a.toString(b)].reverse().map(($,_)=>Math.pow(b,_)*parseInt($,b))
</code>```

Just for fun :)
It could be golfed more, but I'm not too sure how.

ES7, 66 bytes

If ES7 is allowed then:

```<code>(a,b)=>[...a.toString(b)].reverse().map(($,_)=>b**_*parseInt($,b))
</code>```

Title: Decompose a number!

Body:
Your task is to decompose a number using the format below.

This is similar to base conversion, except that instead of listing the digits in the base, you list the values, such that the list adds up to the input.

If the given base is \$n\$, then each number in the list must be in the form of \$k\times n^m\$, where \$0\le k<n\$ and \$m\$ is unique throughout the list.

Specs

Any reasonable input/output format. Your program/function takes 2 inputs and outputs a list.

Output list can be in any order.

0 can be excluded or included.

Leading 0s are allowed.

Built-ins are allowed.

Testcases

```<code>number base   converted list
input1 input2 output
123456 10     [100000,20000,3000,400,50,6] or [6,50,400,3000,20000,100000]
11     2      [8,2,1] or [0,0,0,0,8,0,2,1]
727    20     [400,320,7]
101    10     [100,1] or [100,0,1]
</code>```

Scoring

This is code-golf. Shortest solution in bytes wins.

Body:
JavaScript, 75 bytes

(a,b)=>[...a.toString(b)].reverse().map(($,_)=>Math.pow(b,_)*parseInt($,b))

Just for fun :)
It could be golfed more, but I'm not too sure how.

ES7, 66 bytes

If ES7 is allowed then:

(a,b)=>[...a.toString(b)].reverse().map(($,_)=>b**_*parseInt($,b))


答:
Retina, <s>21</s> <s>18</s> 14 bytes

```<code>(..)+
:(
\(.
)
</code>```

3 bytes saved thanks to Martin Büttner. Another 4 saved thanks to Kenny Lau.

Try it online! (The first line is just to make it run for all test cases).

Uses the same approach as Martins answer.

Title: Am I happy or sad?

Body:
Retina, <s>21</s> <s>18</s> 14 bytes

(..)+
:(
\(.
)

3 bytes saved thanks to Martin Büttner. Another 4 saved thanks to Kenny Lau.

<a href="http://retina.tryitonline.net/#code=JShHYAooLi4pKwo6KApcKC4KKQ&input=Y29udGVudGVkCmRlbGlnaHRlZAptZXJyeQpvdmVyam95ZWQKcGxlYXNlZApibGVzc2VkCmNoaXBwZXIKY29udGVudApjb252aXZpYWwKZ2xlZWZ1bApncmF0aWZpZWQKaW50b3hpY2F0ZWQKam9sbHkKbGlnaHQKcGVwcHkKcGVya3kKcGxheWZ1bApzcGFya2xpbmcKc3VubnkKbWVsYW5jaG9seQpiaXR0ZXIKc29tYmVyCmRpc21hbAptb3VybmZ1bApibHVlCmRlamVjdGVkCmRlc3BhaXJpbmcKZGVzcG9uZGVudApkaXNjb25zb2xhdGUKZGlzdHJlc3NlZApkb3duCmRvd25jYXN0Cmdsb29teQpnbHVtCmhlYXZ5aGVhcnRlZApsdWd1YnJpb3VzCm1vcmJpZAptb3Jvc2UKdHJvdWJsZWQKYmVyZWF2ZWQ" rel="nofollow noreferrer">Try it online! (The first line is just to make it run for all test cases).

Uses the same approach as Martins answer.


Title: Am I happy or sad?

Body:
Lua, <s>35</s> <s>34</s> 30 bytes

print(#(...)%2>0 and":)"or":(")


问:
Polygonal numbers
A polygonal number is the number of dots in a k-gon of size n.

You will be given n and k, and your task is to write a program/function that outputs/prints the corresponding number.

Scoring

This is code-golf. Shortest solution in bytes wins.

Example

The 3rd hexagon number (k=6, n=3) is 28 because there are 28 dots above.

Testcases

Can be generated from this Pyth test suite.

Usage: two lines per testcase, n above, k below.

```<code>n    k  output
10   3  55
10   5  145
100  3  5050
1000 24 10990000
</code>```

Further information

In Wikipedia: https://en.wikipedia.org/wiki/Polygonal_number

In Wolfram Mathworld: http://mathworld.wolfram.com/PolygonalNumber.html

In OEIS Wiki: http://oeis.org/wiki/Polygonal_numbers

OEIS sequences for n-gonal numbers for various n: 3 (A000217), 4 (A000290), 5 (A000326), 6 (A000384), 7 (A000566), 8 (A000567), 9 (A001106), 10 (A001107), 11 (A051682), 12 (A051624), 13 (A051865), 14 (A051866), 15 (A051867), 16 (A051868), 17 (A051869), 18 (A051870), 19 (A051871), 20 (A051872), 21 (A051873), 22 (A051874), 23 (A051875), 24 (A051876)

答:
JavaScript (ES6), <s>24</s> 22 bytes

```<code>(k,n)=>n+n*--n*(k-2)/2
</code>```

Explanation: Each n-gon can be considered to be n points along one side plus k-2 triangles of size n-1, i.e. n+n(n-1)(k-2)/2.

Title: Polygonal numbers

Body:
JavaScript (ES6), <s>24</s> 22 bytes

(k,n)=>n+n*--n*(k-2)/2

Explanation: Each n-gon can be considered to be n points along one side plus k-2 triangles of size n-1, i.e. n+n(n-1)(k-2)/2.


答:
Javascript 30 bytes

```<code>a=>alert(a.length%2?":)":":(")
</code>```

Javascript return version 23 bytes

```<code>a=>a.length%2?":)":":("
</code>```

Try it out:

b=a=>a.length%2?":)":":("
alert(b(prompt("Please enter how you feel!")));```

Title: Am I happy or sad?

Body:
Javascript 30 bytes

a=>alert(a.length%2?":)":":(")

Javascript return version 23 bytes

a=>a.length%2?":)":":("

Try it out:

b=a=>a.length%2?":)":":("
alert(b(prompt("Please enter how you feel!")));


答:
Brainfuck, 71 bytes

```<code>+[--------->+<]>+.>,+[[-]>[->+<]+>[<->-]<<,+]>[<<+>>-]<+++[<------>-]<.
</code>```

Assumes that EOF = -1.

Explaination:

The first part, +[--------->+<]>+., prints : and stores its ascii value (58) in cell #2.

The second part, >,+[[-]>[->+<]+>[<->-]<<,+], is a bit more complicated. For each character in the input, it moves the value in cell #4 into cell #5, it adds one to cell #4, and sets cell #4 = cell #4 - cell #5. Basically, what this does is it changes cell #4 into 1 - cell #4. When every character has been read, cell #4 is length of input % 2.

The third part, >[<<+>>-] adds the value of cell #4 to cell #2.

The last part, >,+[[-]>[->+<]+>[<->-]<<,+] subtracts 18, which is the difference in the ascii table from the colon and the left parentesens  from cell #2 and prints it.

Title: Am I happy or sad?

Body:
Brainfuck, 71 bytes

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

Assumes that EOF = -1.

Explaination:

The first part, +[--------->+<]>+., prints : and stores its ascii value (58) in cell #2.

The second part, >,+[[-]>[->+<]+>[<->-]<<,+], is a bit more complicated. For each character in the input, it moves the value in cell #4 into cell #5, it adds one to cell #4, and sets cell #4 = cell #4 - cell #5. Basically, what this does is it changes cell #4 into 1 - cell #4. When every character has been read, cell #4 is length of input % 2.

The third part, >[<<+>>-] adds the value of cell #4 to cell #2.

The last part, >,+[[-]>[->+<]+>[<->-]<<,+] subtracts 18, which is the difference in the ascii table from the colon and the left parentesens  from cell #2 and prints it.


答:
MATL,  <s>11</s> 10 bytes

```<code>58')('jn)h
</code>```

1 byte saved thanks to @Luis's tip to just rely upon modular indexing rather than an explicit modulus.

Try it Online!

Explanation

```<code>58      % Number literal (ASCII for ':')
')('    % String literal
j       % Explicitly grab input as string
n       % Compute the length of the input string
)       % Index into ')(' using modular indexing
h       % Horizontally concatenate ':' with the result
        % Implicitly display resulting string
</code>```

Title: Am I happy or sad?

Body:
MATL,  <s>11</s> 10 bytes

58')('jn)h

1 byte saved thanks to @Luis's tip to just rely upon modular indexing rather than an explicit modulus.

Try it Online!

Explanation

58      % Number literal (ASCII for ':')
')('    % String literal
j       % Explicitly grab input as string
n       % Compute the length of the input string
)       % Index into ')(' using modular indexing
h       % Horizontally concatenate ':' with the result
        % Implicitly display resulting string


答:
Haskell, 16.5 (55 bytes)

```<code>r#n=l!!(n-1)where l=0:r:r:w l;w(x:y:s)=r*(x+y)-x:w(y:s)
</code>```

It uses this recursive definition:

```<code>f(n,r) = r*f(n-2,r) + (r-1)*f(n-3,r)
</code>```

and uses O(n) time.
Usage: evaluate r#n

Body:
Haskell, 16.5 (55 bytes)

r#n=l!!(n-1)where l=0:r:r:w l;w(x:y:s)=r*(x+y)-x:w(y:s)

It uses this recursive definition:

f(n,r) = r*f(n-2,r) + (r-1)*f(n-3,r)

and uses O(n) time.
Usage: evaluate r#n


问:
Smallest groups in an array

Introduction

Let's observe the following array:

```<code>[1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1]
</code>```

A group consists of the same digits next to each other. In the above array, there are 5 different groups:

```<code>[1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1]

 1, 1, 1
          2, 2
                1, 1, 1, 1
                            2, 2, 2
                                     1, 1, 1
</code>```

The smallest group of these is [2, 2], so we output [2, 2].

Let's take another example:

```<code>[3, 3, 3, 4, 4, 4, 4, 5, 5, 4, 4, 3, 3, 4, 4]

 3, 3, 3
          4, 4, 4, 4
                      5, 5
                            4, 4
                                  3, 3
                                        4, 4
</code>```

You can see that there are multiple groups with the same length. The smallest groups are:

```<code>[3, 3], [4, 4], [4, 4] and [5, 5].
</code>```

So we just output [3, 3], [4, 4], [4, 4], [5, 5] in any reasonable format. You may output these in any order.

The Task

Given an array consisting of only positive integers, output the smallest group(s) from the array. You can assume that the array will contain at least 1 integer.

Test cases

```<code>Input: [1, 1, 2, 2, 3, 3, 4]
Output: [4]

Input: [1]
Output: [1]

Input: [1, 1, 10, 10, 10, 100, 100]
Output: [1, 1], [100, 100]
</code>```

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

答:
Mathematica, 24 bytes

```<code>MinimalBy[Length]@*Split
</code>```

This is a composition of two functions that can be applied to a list. Split takes all groups of consecutive numbers, and MinimalBy[Length] selects those with minimal length.

Title: Smallest groups in an array

Body:
Mathematica, 24 bytes

MinimalBy[Length]@*Split

This is a composition of two functions that can be applied to a list. Split takes all groups of consecutive numbers, and MinimalBy[Length] selects those with minimal length.


答:
Jolf, <s>12</s> 11 bytes

```<code>+':."()"mρl
</code>```

I <s>might (might) be</s> was able to golf it down a byte by joining the faces. Try it here!

Explanation

```<code>+':."()"mρl
+':          ":" +
   ."()"     the member from "()"
        mρl  that is the parity of the length of the implicit input
</code>```

Title: Am I happy or sad?

Body:
Jolf, <s>12</s> 11 bytes

+':."()"mρl

I <s>might (might) be</s> was able to golf it down a byte by joining the faces. Try it here!

Explanation

+':."()"mρl
+':          ":" +
   ."()"     the member from "()"
        mρl  that is the parity of the length of the implicit input


答:
Jelly, <s>22</s> <s>17</s> 16 bytes

```<code>I0;œṗ¹L=¥ÐfL€Ṃ$$
</code>```

Try it online!

```<code>I0;œṗ¹L=¥ÐfL€Ṃ$$     Main link. List: z = [a,b,c,...]

I                    Compute [b-a, c-b, d-c, ...]
 0;                  Concatenate 0 in front: [0, b-a, c-b, d-c, ...]
   œṗ                Split z where the corresponding item in the above array is not zero.
      L=¥Ðf          Filter sublists whose length equal:
           L€Ṃ$      the minimum length throughout the list.

     ¹         $     (grammar stuffs)
</code>```

Title: Smallest groups in an array

Body:
Introduction

Let's observe the following array:

```<code>[1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1]
</code>```

A group consists of the same digits next to each other. In the above array, there are 5 different groups:

```<code>[1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1]

 1, 1, 1
          2, 2
                1, 1, 1, 1
                            2, 2, 2
                                     1, 1, 1
</code>```

The smallest group of these is [2, 2], so we output [2, 2].

Let's take another example:

```<code>[3, 3, 3, 4, 4, 4, 4, 5, 5, 4, 4, 3, 3, 4, 4]

 3, 3, 3
          4, 4, 4, 4
                      5, 5
                            4, 4
                                  3, 3
                                        4, 4
</code>```

You can see that there are multiple groups with the same length. The smallest groups are:

```<code>[3, 3], [4, 4], [4, 4] and [5, 5].
</code>```

So we just output [3, 3], [4, 4], [4, 4], [5, 5] in any reasonable format. You may output these in any order.

The Task

Given an array consisting of only positive integers, output the smallest group(s) from the array. You can assume that the array will contain at least 1 integer.

Test cases

```<code>Input: [1, 1, 2, 2, 3, 3, 4]
Output: [4]

Input: [1]
Output: [1]

Input: [1, 1, 10, 10, 10, 100, 100]
Output: [1, 1], [100, 100]
</code>```

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

Body:
Jelly, <s>22</s> <s>17</s> 16 bytes

I0;œṗ¹L=¥ÐfL€Ṃ$$

Try it online!

I0;œṗ¹L=¥ÐfL€Ṃ$$     Main link. List: z = [a,b,c,...]

I                    Compute [b-a, c-b, d-c, ...]
 0;                  Concatenate 0 in front: [0, b-a, c-b, d-c, ...]
   œṗ                Split z where the corresponding item in the above array is not zero.
      L=¥Ðf          Filter sublists whose length equal:
           L€Ṃ$      the minimum length throughout the list.

     ¹         $     (grammar stuffs)


答:
Jelly, 11 bytes

```<code>µÆE;¬g/’µ#Ṫ
</code>```

Try it online!.

Background

Every positive integer \$k\$ can be factorized uniquely as the product of powers of the first \$m\$ primes, i.e., \$k=p_1^{\alpha_1}\cdots p_m^{\alpha_m}\$, where \$\alpha_m>0\$.

We have that \$a^b\$ (\$b>1\$) for some positive integer \$a\$ if and only if \$b\$ is a divisor of all exponents \$\alpha_j\$.

Thus, an integer \$k > 1\$ is a perfect power if and only if \$\gcd(α_1, ⋯, α_m) ≠ 1\$.

How it works

```<code>µÆE;¬g/’µ#Ṫ  Main link. No arguments.

µ            Make the chain monadic, setting the left argument to 0.
        µ#   Find the first n integers k, greater or equal to 0, for which the
             preceding chain returns a truthy value.
             In the absence of CLAs, n is read implicitly from STDIN.
 ÆE          Compute the exponents of the prime factorization of k.
   ;¬        Append the logical NOT of k, i.e., 0 if k > 0 and 1 otherwise.
             This maps 1 -> [0] and [0] -> [1].
     g/      Reduce the list of exponents by GCD.
             In particular, we achieved that 1 -> 0 and 0 -> 1.
       ’     Decrement; subtract 1 from the GCD.
             This maps 1 to 0 (falsy) and all other integers to a truthy value.
          Ṫ  Tail; extract the last k.
</code>```

Title: Find the n-th perfect power!

Body:
A perfect power is a number of the form \$a^b\$, where \$a>0\$ and \$b>1\$.

For example, \$125\$ is a perfect power because it can be expressed as \$5^3\$.

Goal

Your task is to write  a program/function that finds the \$n\$-th perfect power, given a positive integer \$n\$.

Specs

The first perfect power is \$1\$ (which is \$1^2\$).

Input/output in any reasonable format.

Built-ins are allowed.

Further information

OEIS A001597

Scoring

This is code-golf. Shortest solution in bytes wins.

Testcases

```<code>input  output
1      1
2      4
3      8
4      9
5      16
6      25
7      27
8      32
9      36
10     49
</code>```

Body:
Jelly, 11 bytes

µÆE;¬g/’µ#Ṫ

Try it online!.

Background

Every positive integer \$k\$ can be factorized uniquely as the product of powers of the first \$m\$ primes, i.e., \$k=p_1^{\alpha_1}\cdots p_m^{\alpha_m}\$, where \$\alpha_m>0\$.

We have that \$a^b\$ (\$b>1\$) for some positive integer \$a\$ if and only if \$b\$ is a divisor of all exponents \$\alpha_j\$.

Thus, an integer \$k > 1\$ is a perfect power if and only if \$\gcd(α_1, ⋯, α_m) ≠ 1\$.

How it works

µÆE;¬g/’µ#Ṫ  Main link. No arguments.

µ            Make the chain monadic, setting the left argument to 0.
        µ#   Find the first n integers k, greater or equal to 0, for which the
             preceding chain returns a truthy value.
             In the absence of CLAs, n is read implicitly from STDIN.
 ÆE          Compute the exponents of the prime factorization of k.
   ;¬        Append the logical NOT of k, i.e., 0 if k > 0 and 1 otherwise.
             This maps 1 -> [0] and [0] -> [1].
     g/      Reduce the list of exponents by GCD.
             In particular, we achieved that 1 -> 0 and 0 -> 1.
       ’     Decrement; subtract 1 from the GCD.
             This maps 1 to 0 (falsy) and all other integers to a truthy value.
          Ṫ  Tail; extract the last k.


答:
Pyth, 14 12 11

```<code>mM_MmhbrQ8
</code>```

Test Suite

2 bytes thanks to Jakube! And 1 byte thanks to isaacg!

Unfortunately, run length decoding doesn't quite do what we want it to do, but it will work with a minor workaround, but that makes it slightly longer than the manual implementation:

```<code>mr]d9.mhbrQ8
</code>```

Credit to Jakube for finding this out.

Title: Smallest groups in an array

Body:
Pyth, 14 12 11

mM_MmhbrQ8

Test Suite

2 bytes thanks to Jakube! And 1 byte thanks to isaacg!

Unfortunately, run length decoding doesn't quite do what we want it to do, but it will work with a minor workaround, but that makes it slightly longer than the manual implementation:

mr]d9.mhbrQ8

Credit to Jakube for finding this out.


答:
05AB1E, 12 bytes

Code:

```<code>LD>m€`{Ú`¹<@
</code>```

Uses CP-1252 encoding. Try it online!.

Title: Find the n-th perfect power!

Body:
05AB1E, 12 bytes

Code:

LD>m€`{Ú`¹<@

Uses CP-1252 encoding. Try it online!.


答:
J, 15 bytes

```<code>':',"0'()'{~2|#
</code>```

':',"0 concats ':' with the 0-cells of the string '()', making an array of :( and :). {~ is get with switched argument order, 2| is the parity of the length # of the RHS.

```<code>  p =: ':',"0'()'{~2|#
  p 'happy'
:)
  p 'somber'
:(
</code>```

Use (>;p)"0 to test a list of words and compare their output.

Title: Am I happy or sad?

Body:
You are trying to guess my emotion.

I will give you an adjective, as the input to the function/program.

Your task is to output my emotion, either :) for happy, or :( for sad.

Details

For these adjectives, you must output the happy face :)

```<code>contented
delighted
merry
overjoyed
pleased
blessed
chipper
content
convivial
gleeful
gratified
intoxicated
jolly
light
peppy
perky
playful
sparkling
sunny
</code>```

For these adjectives, you must output the sad face :(

```<code>melancholy
bitter
somber
dismal
mournful
blue
dejected
despairing
despondent
disconsolate
distressed
down
downcast
gloomy
glum
heavyhearted
lugubrious
morbid
morose
troubled
bereaved
</code>```

Other adjectives are undefined. You may output whatever you want for other adjectives.

Specs

All in lowercase. All matches regex ^[a-z]+$.

Scoring

This is code-golf. Shortest solution in bytes wins.

Tips

There is a trick.

Body:
J, 15 bytes

':',"0'()'{~2|#

':',"0 concats ':' with the 0-cells of the string '()', making an array of :( and :). {~ is get with switched argument order, 2| is the parity of the length # of the RHS.

  p =: ':',"0'()'{~2|#
  p 'happy'
:)
  p 'somber'
:(

Use (>;p)"0 to test a list of words and compare their output.