title: Is this a complete Boolean function?

text:
# Question
Title: Is this a complete Boolean function?
A complete Boolean function is a function such that, an amount of them can be used to express any Boolean function. For example, NAND \\$\left\[\begin{matrix}\text{input1}&0&0&1&1\\\text{input2}&0&1&0&1\\\text{output}&1&1&1&0\end{matrix}\right\]\\$ is complete. Inputs may be reused any number of times, and the functions can be composed arbitrarily.

Some functions, like IMPLY \\$\left\[\begin{matrix}\text{input1}&0&0&1&1\\\text{input2}&0&1&0&1\\\text{output}&1&1&0&1\end{matrix}\right\]\\$, are not individually complete. We can prove this simply by noting that there is no way to output 0 if all inputs are 1. However, if we are allowed to use the constant functions (always 0 and always 1, aka `false` and `true`), then the set of functions becomes complete.

Given a Boolean Function with input, check whether it's complete, not complete, or only complete if constants are allowed.

Flexible IO, shortest code wins.

## Test cases

(2-input)

```
a  0 0 1 1
b  0 1 0 1
#1 1 1 1 0 Complete
#2 0 1 1 0 Not complete
#3 0 0 1 0 Need Constant

```

(3-input)

```
a  0 0 0 0 1 1 1 1
b  0 0 1 1 0 0 1 1
c  0 1 0 1 0 1 0 1
#1 0 0 0 0 0 0 0 1 Not complete
#2 1 0 0 0 0 0 0 0 Complete
#3 1 1 1 1 0 0 0 0 Not complete
#4 1 1 0 1 0 0 1 0 Complete
#5 0 0 1 1 0 1 0 1 Need constant

```

# Answer
> 8 votes
# Python 2, ~~152~~ ~~150~~ ~~147~~ 136 bytes

```
def c(a):E=enumerate;x,y,z=map(min,*[[a[i|c]>=v,c&c-1>=w^a[0]^a[i^c]^v,v^a[~i]>=a[0]-a[-1]]for i,v in E(a)for c,w in E(a)]);print-x|-y|z

```

Try it online! (TIO link outputs through function `return` instead of stdout)

*-15 bytes thanks to @ovs*

Takes input as a list of boolean outputs in the same order as the question, so (for example) a two-argument function is represented by the four-element list `[f(0,0),f(1,0),f(0,1),f(1,1)]`. In general, for an input list `a` of length `2^n`, we must have `a[i] = f(i&1, i&2, ..., i&(1<<n-1))`.

Outputs by printing to STDOUT according to the following table:

```
COMPLETE = -1
NOT_COMPLETE = 1
NEEDS_CONSTANT = -2

```

## Theory

This uses Post's Characterization of Functional Completeness, which describes five terms that can describe a boolean function: monotonic, affine, self-dual, truth-preserving, and falsity-preserving. For a different explanation of what they mean, read the comments in class `Char` in the ungolfed code below.

These five terms completely characterize the answer, as proven by Emil Post. If a term describes every member of a set of boolean expressions, then that set of boolean functions is not functionally complete.

For example, if every function is truth-preserving, then plugging in all inputs as 1 (true) will always return 1 (true), no matter how the functions are arranged. This means that the functions cannot be arranged to take all inputs as 1 and return 0, so that set of functions is not functionally complete. Similar arguments work for the other four terms as well.

The converse (if none of the five terms describe every member of a set of functions, then that set of functions is functionally complete) is harder to prove in the general case, so I'm relying on Emil Post's proof.

## Application

To answer the challenge, we calculate which of the terms describe the given function.

* If none of the terms describe the given function, then it is functionally complete. Return `COMPLETE`.
* Otherwise, if the given function is either monotonic or affine, then adding the two constant functions (`true` and `false`) would cause the new set of functions to still be monotonic or affine (because true and false are both monotonic and affine). Return `NOT_COMPLETE`
* Otherwise, return `NEEDS_CONSTANT`. Neither of the two constant functions are self-dual, so adding either one would cause the set of functions to not all be self-dual. Similarly, the `true` constant is not falsity-preserving, and the `false` constant is not truth-preserving, so adding both handles the case where the given function is truth-preserving, falsity-preserving, or both.

## Ungolfed code

```
from enum import Enum

# BEGIN GOLF
class Completeness(Enum):
    COMPLETE = "COMPLETE"
    NOT_COMPLETE = "NOT_COMPLETE"
    NEEDS_CONSTANT = "NEEDS_CONSTANT"

class Char(Enum):
    # changing any 0 to a 1 does not cause the result to change from 1 to 0
    MONOTONIC = "MONOTONIC"
    # every input variable either always or never affects the truth value
    # i.e. equivalent to the logical XOR or XNOR of the inputs
    AFFINE = "AFFINE"
    # flipping all the 0s to 1s and 1s to 0s flips the result between a 0 and 1
    SELF_DUAL = "SELF_DUAL"
    # if all inputs are 1, then the output is 1
    TRUTH_PRESERVING = "TRUTH_PRESERVING"
    # if all inputs are 0, then the output is 0
    FALSITY_PRESERVING = "FALSITY_PRESERVING"

def is_power_of_two(n):
    return n & n - 1 == 0

def characterize(output):
    chars = set()
    u = len(output)
    mask = u - 1
    powers_of_two = list(filter(is_power_of_two, range(u)))
    if all(output[i | c] >= output[i] for i in range(u) for c in powers_of_two):
        chars.add(Char.MONOTONIC)
    if all(
        all(output[i ^ c] != output[i] for i in range(u))
        or all(output[i ^ c] == output[i] for i in range(u))
        for c in powers_of_two
    ):
        chars.add(Char.AFFINE)
    if all(output[i] != output[mask & (~i)] for i in range(u)):
        chars.add(Char.SELF_DUAL)
    if output[-1] == 1:
        chars.add(Char.TRUTH_PRESERVING)
    if output[0] == 0:
        chars.add(Char.FALSITY_PRESERVING)
    return chars

def completeness(output):
    chars = characterize(output)
    if len(chars) == 0:
        return Completeness.COMPLETE
    elif Char.MONOTONIC in chars or Char.AFFINE in chars:
        return Completeness.NOT_COMPLETE
    else:
        return Completeness.NEEDS_CONSTANT

# END GOLF

tests = [
    # (none)
    ([1, 1, 1, 0], Completeness.COMPLETE),
    # affine, falsity-preserving
    ([0, 1, 1, 0], Completeness.NOT_COMPLETE),
    # falsity-preserving
    ([0, 0, 1, 0], Completeness.NEEDS_CONSTANT),
    # monotonic, truth-preserving
    ([0, 0, 0, 0, 0, 0, 0, 1], Completeness.NOT_COMPLETE),
    # (none)
    ([1, 0, 0, 0, 0, 0, 0, 0], Completeness.COMPLETE),
    # self-dual, affine
    ([1, 1, 1, 1, 0, 0, 0, 0], Completeness.NOT_COMPLETE),
    # (none)
    ([1, 1, 0, 1, 0, 0, 1, 0], Completeness.COMPLETE),
    # falsity-preserving, truth-preserving
    ([0, 0, 1, 1, 0, 1, 0, 1], Completeness.NEEDS_CONSTANT),
]

for output, expected in tests:
    got = completeness(output)
    if got == expected:
        print("PASS")
    else:
        print(f"FAIL on {output}. Expected {expected} but got {got}")
        print(f"  Chars: {', '.join(map(str,list(characterize(output))))}")

```

# Answer
> 1 votes
# Charcoal, 60 bytes

```
≔Ｅ↨⊖Ｌθ²Ｘ²κη✳∧⊙⮌θ⁼§θκι›§θ⁰§θ±¹›⊙η⊙θ‹§θ｜ιμλ⬤ηΦ²⬤θ∨＆ιξ⁼λ⁼§θ｜ιξν

```

Try it online! Link is to verbose version of code. Can take input as a binary string or an array and outputs `/` for complete, `-` if constants are needed, nothing if incomplete. Explanation: Port of @fireflame241's solution.

```
≔Ｅ↨⊖Ｌθ²Ｘ²κη

```

Get the powers of 2 up to the length of the string.

```
✳∧⊙⮌θ⁼§θκι›§θ⁰§θ±¹

```

If any function value matches that of the reverse of the string (meaning that the function is not self-dual), and the first value is greater than the last value (meaning that the function is neither true- or false-preserving), then prepare to print a `/` rather than a `-`.

```
›⊙η⊙θ‹§θ｜ιμλ⬤ηΦ²⬤θ∨＆ιξ⁼λ⁼§θ｜ιξν

```

Don't print anything if the function is monotonic or affine. The function is not monotonic if there exists a set of inputs such that changing one of the inputs to `1` changes the value from `1` to `0`. (Inputs of `1` are also checked, but changing them to `1` obviously has no effect on the value.) The function is affine if for all inputs the values where that input is `1` are either equal to or the exact complement of the values where that input is `0` all at the same time. This was the part that was hardest to golf in Charcoal as it doesn't have the bitwise XOR function, nor does it have a simple way of comparing all the values in an array with each other.

---
Tags: code-golf
---


title: Will the hydra finally die? Part II

text:
# Question
Title: Will the hydra finally die? Part II
### Background

This is a follow up question to the question: Will the Hydra finally die?

As before a dangerous A Medusa have released a dangerous Hydra which is revived unless the exact number of heads it have is removed. The knights can remove a certain number of heads with each type of attack, and each attack causes a specific amount of heads to regrow. This time the knights are more impatient and having seen your previous abilities want you to\** write a program or function that **returns a list of hits which will leave the hydra 1 hit from death**

Note that this is fundamentally different from Become the Hydra Slayer. in 2 aspects. 1: We are not asking for the optimal solution 2: each attack causes a *different* number of heads to grow back. this radically changes the approach needed.

*For example:*

```
input: heads = 2,
       attacks = [1, 25, 62, 67],
       growths = [15, 15, 34, 25],

output: [5, 1, 0, 0]

```

*Explanation:* The Hydra has 10 heads to start with, we have 4 different `attacks` and for each attack, `growth` gives us the number of heads that grows back. `hits` gives us the number of times each attack is applied. So the number of heads the Hydra has after each attack is

```
2 -> 16 -> 30 -> 44 -> 58 -> 72 -> 62

```

Since `62` is a valid attack value (It lies in the attack list), we return `True` since the Hydra will die on the next attack (be left with 0 heads). Note that the order for when the attacks are done is irrelevant.

```
2 -> 16 -> 6 -> 20 -> 34 -> 48 -> 62

```

---

### Input

Input should contain `heads` (an integer), `attacks` (a list of how many heads can be removed), `regrowths` (how many heads grow back per attack)

You may take input in any convenient method. This includes, but is not limited to

* A list of tuples `(1, 15, 5), (25, 15, 1), (62, 34, 0), (67, 25, 0)`
* Lists `2, [1, 25, 62, 67], [15, 15, 34, 25], [5, 1, 0, 0]`
* Reading values from STDIN `1 15 1 15 1 15 1 15 1 15 25 15`
* A file of values

---

### Output

* An array, or some way to easily indicate which hits the knights are to take. Example: `5 1 0 0`

**Note 1** Say that your input is `attacks = [1, 25, 62, 67]` and the hydra has 25 heads left, then you **cannot** output the answer as `[1,0,0,0]`, `[0,0,0,1]` etc. **Your output and input must be sorted similarly**. Otherwise it will be very confusing for the Knights.

**Note 2:** Your program can *never* leave the Hydra with a negative number of heads. Meaning if the Hydra has 15 heads, an attack removes 17 heads and regrows 38. You may not perform this attack.

* You may assume that any input is valid. E.g every input will not overkill the Hydra and either result in a number of heads that is an attack value, or not.

---

### Assumptions

* There will always be as many attacks as regrowths
* Every attack value will always correspond to one regrowth value which never changes. these are not required to be unique
* Every input value will be a non-negative integer
* You may assume that there always exists a solution (note that this is not neccecarily the case, but for our test data it is)
* How you handle non valid inputs is up to you

---

### Scoring

* This is a you will be scored as follows: the total sum of hits your code produces from the test data + length of answer in bytes
* Note that how you input and parse the test data is not part of your code length. Your code should, as stated above simply take in some a headcount, attacks, regrowth's and return a list/representation of how many hits each attack has to be performed to leave the hydra *exactly* 1 hit from death.

**Lowest score wins!**

---

### Test data

```
       attacks = [1, 25, 62, 67],
       growths = [15, 15, 34, 25],

```

**use every integer from `1` to `200` as the number of heads.** An sample from the first 100 can be found below. Again your program does not have to return these values, it is merely an example of how the scoring would work. As seen below the total sum for each of these hits are `535` meaning my score would be `535 + length of code in bytes` (If we wanted to use 1-100 instead of 1-200 as the number of heads of course)

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

```

# Answer
> 2 votes
# 05AB1E `--no-lazy`, 944 hits + 29 bytes = 973

The `²g∍` part is technically not necessary, but I wanted this to actually finish in seconds rather than years. I think this should return optimal solutions.

```
[NÅœε²gÅ0«²g∍œε³²-*O¹+²såiy,q

```

Try it online!

```
                   # Inputs: ¹ - initial number of heads
                   #         ² - list of attacks
                   #         ³ - list of regrowths
[                  # for N in 0, 1, 2, ...
 NÅœ               # push integer partitions of N
    ε              # for each partition:
     ²gÅ0«         #   append as many 0's as there are attacks
          ²g∍      #   take as many integers as there are attacks from the front
              œ    #   take the permutations of this subset

ε                  # for each permutation y of a subset of the integer partition of N
 ³²-               # regrowths - attacks element-wise
    *              # multiply with y element-wise
     O             # take the sum of this
      ¹+           # and add the initial number of heads
        ²såi       # if this is in the list of attacks:
            y,q    #   print y and exit the program

```

Here is my output for the 200 cases, generated with this test suite (finishes in 70 seconds locally):

```
  1 -> [0, 0, 0, 0]
  2 -> [5, 1, 0, 0]
  3 -> [2, 3, 0, 0]
  4 -> [7, 4, 0, 0]
  5 -> [4, 6, 0, 0]
  6 -> [4, 0, 0, 0]
  7 -> [1, 2, 0, 0]
  8 -> [6, 3, 0, 0]
  9 -> [3, 5, 0, 0]
 10 -> [8, 6, 0, 0]
 11 -> [1, 0, 0, 0]
 12 -> [5, 2, 0, 0]
 13 -> [2, 4, 0, 0]
 14 -> [7, 5, 0, 0]
 15 -> [1, 0, 1, 0]
 16 -> [4, 1, 0, 0]
 17 -> [1, 3, 0, 0]
 18 -> [6, 4, 0, 0]
 19 -> [3, 6, 0, 0]
 20 -> [3, 0, 0, 0]
 21 -> [1, 1, 0, 0]
 22 -> [5, 3, 0, 0]
 23 -> [2, 5, 0, 0]
 24 -> [7, 6, 0, 0]
 25 -> [0, 0, 0, 0]
 26 -> [4, 2, 0, 0]
 27 -> [1, 4, 0, 0]
 28 -> [6, 5, 0, 0]
 29 -> [0, 0, 1, 0]
 30 -> [3, 1, 0, 0]
 31 -> [1, 2, 0, 0]
 32 -> [5, 4, 0, 0]
 33 -> [2, 6, 0, 0]
 34 -> [2, 0, 0, 0]
 35 -> [0, 1, 0, 0]
 36 -> [4, 3, 0, 0]
 37 -> [1, 5, 0, 0]
 38 -> [6, 6, 0, 0]
 39 -> [1, 0, 1, 0]
 40 -> [3, 2, 0, 0]
 41 -> [1, 3, 0, 0]
 42 -> [5, 5, 0, 0]
 43 -> [0, 0, 0, 1]
 44 -> [2, 1, 0, 0]
 45 -> [0, 2, 0, 0]
 46 -> [4, 4, 0, 0]
 47 -> [1, 6, 0, 0]
 48 -> [1, 0, 0, 0]
 49 -> [1, 1, 1, 0]
 50 -> [3, 3, 0, 0]
 51 -> [1, 4, 0, 0]
 52 -> [5, 6, 0, 0]
 53 -> [1, 0, 0, 0]
 54 -> [2, 2, 0, 0]
 55 -> [0, 3, 0, 0]
 56 -> [4, 5, 0, 0]
 57 -> [0, 0, 2, 0]
 58 -> [1, 1, 0, 0]
 59 -> [1, 2, 1, 0]
 60 -> [3, 4, 0, 0]
 61 -> [1, 5, 0, 0]
 62 -> [0, 0, 0, 0]
 63 -> [1, 1, 0, 0]
 64 -> [2, 3, 0, 0]
 65 -> [0, 4, 0, 0]
 66 -> [4, 6, 0, 0]
 67 -> [0, 0, 0, 0]
 68 -> [1, 2, 0, 0]
 69 -> [1, 3, 1, 0]
 70 -> [3, 5, 0, 0]
 71 -> [0, 0, 1, 1]
 72 -> [0, 1, 0, 0]
 73 -> [1, 2, 0, 0]
 74 -> [2, 4, 0, 0]
 75 -> [0, 5, 0, 0]
 76 -> [1, 0, 1, 0]
 77 -> [0, 1, 0, 0]
 78 -> [1, 3, 0, 0]
 79 -> [1, 4, 1, 0]
 80 -> [3, 6, 0, 0]
 81 -> [1, 0, 1, 0]
 82 -> [0, 2, 0, 0]
 83 -> [1, 3, 0, 0]
 84 -> [2, 5, 0, 0]
 85 -> [0, 0, 0, 2]
 86 -> [1, 1, 1, 0]
 87 -> [0, 2, 0, 0]
 88 -> [1, 4, 0, 0]
 89 -> [1, 5, 1, 0]
 90 -> [0, 0, 1, 0]
 91 -> [1, 1, 1, 0]
 92 -> [0, 3, 0, 0]
 93 -> [1, 4, 0, 0]
 94 -> [2, 6, 0, 0]
 95 -> [0, 0, 1, 0]
 96 -> [1, 2, 1, 0]
 97 -> [0, 3, 0, 0]
 98 -> [1, 5, 0, 0]
 99 -> [0, 0, 2, 1]
100 -> [0, 1, 1, 0]
101 -> [1, 2, 1, 0]
102 -> [0, 4, 0, 0]
103 -> [1, 5, 0, 0]
104 -> [0, 0, 0, 1]
105 -> [0, 1, 1, 0]
106 -> [1, 3, 1, 0]
107 -> [0, 4, 0, 0]
108 -> [1, 6, 0, 0]
109 -> [0, 0, 0, 1]
110 -> [0, 2, 1, 0]
111 -> [1, 3, 1, 0]
112 -> [0, 5, 0, 0]
113 -> [0, 0, 1, 2]
114 -> [0, 1, 0, 1]
115 -> [0, 2, 1, 0]
116 -> [1, 4, 1, 0]
117 -> [0, 5, 0, 0]
118 -> [0, 0, 2, 0]
119 -> [0, 1, 0, 1]
120 -> [0, 3, 1, 0]
121 -> [1, 4, 1, 0]
122 -> [0, 6, 0, 0]
123 -> [0, 0, 2, 0]
124 -> [0, 2, 0, 1]
125 -> [0, 3, 1, 0]
126 -> [1, 5, 1, 0]
127 -> [0, 0, 0, 3]
128 -> [0, 1, 2, 0]
129 -> [0, 2, 0, 1]
130 -> [0, 4, 1, 0]
131 -> [1, 5, 1, 0]
132 -> [0, 0, 1, 1]
133 -> [0, 1, 2, 0]
134 -> [0, 3, 0, 1]
135 -> [0, 4, 1, 0]
136 -> [1, 6, 1, 0]
137 -> [0, 0, 1, 1]
138 -> [0, 2, 2, 0]
139 -> [0, 3, 0, 1]
140 -> [0, 5, 1, 0]
141 -> [0, 0, 2, 2]
142 -> [0, 1, 1, 1]
143 -> [0, 2, 2, 0]
144 -> [0, 4, 0, 1]
145 -> [0, 5, 1, 0]
146 -> [0, 0, 0, 2]
147 -> [0, 1, 1, 1]
148 -> [0, 3, 2, 0]
149 -> [0, 4, 0, 1]
150 -> [0, 6, 1, 0]
151 -> [0, 0, 0, 2]
152 -> [0, 2, 1, 1]
153 -> [0, 3, 2, 0]
154 -> [0, 5, 0, 1]
155 -> [0, 0, 1, 3]
156 -> [0, 1, 0, 2]
157 -> [0, 2, 1, 1]
158 -> [0, 4, 2, 0]
159 -> [0, 5, 0, 1]
160 -> [0, 0, 2, 1]
161 -> [0, 1, 0, 2]
162 -> [0, 3, 1, 1]
163 -> [0, 4, 2, 0]
164 -> [0, 6, 0, 1]
165 -> [0, 0, 2, 1]
166 -> [0, 2, 0, 2]
167 -> [0, 3, 1, 1]
168 -> [0, 5, 2, 0]
169 -> [0, 0, 0, 4]
170 -> [0, 1, 2, 1]
171 -> [0, 2, 0, 2]
172 -> [0, 4, 1, 1]
173 -> [0, 5, 2, 0]
174 -> [0, 0, 1, 2]
175 -> [0, 1, 2, 1]
176 -> [0, 3, 0, 2]
177 -> [0, 4, 1, 1]
178 -> [0, 6, 2, 0]
179 -> [0, 0, 1, 2]
180 -> [0, 2, 2, 1]
181 -> [0, 3, 0, 2]
182 -> [0, 5, 1, 1]
183 -> [0, 0, 2, 3]
184 -> [0, 1, 1, 2]
185 -> [0, 2, 2, 1]
186 -> [0, 4, 0, 2]
187 -> [0, 5, 1, 1]
188 -> [0, 0, 0, 3]
189 -> [0, 1, 1, 2]
190 -> [0, 3, 2, 1]
191 -> [0, 4, 0, 2]
192 -> [0, 6, 1, 1]
193 -> [0, 0, 0, 3]
194 -> [0, 2, 1, 2]
195 -> [0, 3, 2, 1]
196 -> [0, 5, 0, 2]
197 -> [0, 0, 1, 4]
198 -> [0, 1, 0, 3]
199 -> [0, 2, 1, 2]
200 -> [0, 4, 2, 1]

Total:  944  hits
```

# Answer
> 2 votes
# Python 3, 944 hits + 178 bytes = 1122

```
def f(t,s):
	q=[[[0]*len(s),t]];f={0}
	for p,t in q:
		if any(x==t for x,_ in s):return p
		for i,(k,y)in enumerate(s):n=t-k+y;q+=[[p[:i]+[p[i]+1]+p[i+1:],n]]*(n not in f);f|={n}

```

Try it online!

I can verify that 944 is the optimal solution; this is guaranteed to be optimal.

`;f={0}`, `n=t-k+y`, `*(n nt in f)`, and `f|={n}` are not necessary for golfing but like with ovs's solution, I have them here just so the solution will run within seconds rather than years.

Trivial BFS solution.

# Answer
> 0 votes
# Jelly, 26 bytes + 944 attacks = 970 score

```
_Ḣ0œċNƭ€Se¥Ƈ/©¥@1#ṛ®ƲḢċⱮḢƲ

```

Try it online!

A monadic link taking `[attack], [regrowth], heads` as its argument and returning a list of counts of attacks.

---
Tags: number, code-challenge, game
---


title: Most Valuable Circle Chords

text:
# Question
Title: Most Valuable Circle Chords
This challenge was inspired by this tweet.

## Idea

Consider a circle with `n` evenly spaced dots around the perimeter, where each dot has a postive integer value:

Now connect the dots with *non-intersecting* chords:

Next consider our score, which is the sum of the products of these pairs. When `n` is odd, the extra orphan dot will not contribute to our score.

Finally we ask: Which pairing of dots gives us the highest score?

## Task

Write a program to solve this puzzle.

### Input

A list of postive integers, in order, representing the values of the dots which are spread evenly around the circumference of a circle.

### Output

A list of pairs of the same integers, representing an optimal solution to the puzzle described above.

That is, the pairs you return must:

1. Produce non-intersecting circle chords when connected by straight lines.
2. Produce a maximal score among all possible solutions that satisfy rule 1.

The score we're maximizing is the sum of the products of the pairs, and for odd-length input does not include the unpaired number.

In some cases, such as `[1, 9, 1, 9]`, the optimal solution will voluntarily leave unpaired numbers. In this example the solution is to pair the two `9`s and leave the two `1`s as singletons.

Additional notes:

* Again, for odd-length input, the unpaired number won't contribute to your score. You may include this singleton in your output or not.
* Same goes for "voluntary" singletons such as the `[1, 9, 1, 9]` described above.
* In addition to the optimal list of pairs, you may include the optimal score value as well, but don't have to.
* If 2 or more solutions tie, you may output any one of them, or all of them.
* The order in which the optimal pairs are given doesn't matter.

## Rules

This is code golf with standard site rules. Both input and output formats are flexible. In particular, output may be:

* An array of arrays, where the inner arrays have length 2.
* An n by 2 or 2 by n matrix.
* A single flat list, so long as all the optimal pairs are adjacent.
* Anything else reasonable.

## Test Cases

I included optimal score for convenience but it's not required in the output.

```
Input: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Output: [[2, 3], [4, 5], [6, 7], [8, 9]]
Score: 140

Input: [1, 2, 3, 4, 5, 6, 7, 8]
Output: [[1, 2], [3, 4], [5, 6], [7, 8]]
Score: 100

Input: [1, 4, 8, 7, 11, 2, 5, 9, 3, 6, 10]
Output: [[4, 3], [6, 10], [8, 7], [11, 9], [2, 5]]
Score: 237

Input: [12, 8, 2, 20, 16, 7]
Output: [[12, 8], [2, 7], [20, 16]]
Score: 430

Input: [29, 27, 23, 22, 14, 13, 21, 7, 26, 27]
Output: [[29, 27], [23, 22], [14, 7], [26, 27], [13, 21]]
Score: 2362

Input: [1, 9, 1, 9]
Output: [[9, 9]]
Score: 81

```

# Answer
> 5 votes
# Jelly, ~~27~~ 26 bytes

```
JŒcŒPŒc_€/ṠÆḊ¬Ʋ€ẠƊƇịZPSɗÐṀ

```

Try it online!

-1 byte thanks to @caird.

Independently arrived at something very similar to Jonathan Allan's solution.

The only difference is `_€/ṠÆḊ¬Ʋ` part, which tests if two pairs of indices are two non-intersecting chords.

Because of how `ŒP` (powerset) and `Œc` (unordered pairs) generate the results, it is sufficient to filter out the pairs of pairs which have the element-wise ordering of `[[1, 3], [2, 4]]`, `[[1, 2], [1, 3]]`, `[[1, 2], [2, 3]]`, or `[[1, 3], [2, 3]]`. The pairs `[[1, 2], [3, 4]]` and `[[1, 4], [2, 3]]` should be kept intact. Test this condition.

```
_€/ṠÆḊ¬Ʋ    Given a 2x2 matrix of values, test if they're valid chords
_€/Ṡ        Sign of cartesian pair-wise difference
    ÆḊ      Determinant
      ¬     1 if zero, 0 otherwise

```

# Answer
> 7 votes
# Jelly, ~~45~~ 43 bytes

```
ṖẎƤṚ+"JpẎ€¥"Ʋṭ@€"J,€¥ɗẎṭḷ
Jçƒ0RWW¤Ẏị¹ZPSƊÐṀ

```

Try it online!

Uses a modified `f(n)`, which is defined as sets of chords containing the vertex `n`.

---

# Jelly, 45 bytes

```
ṖṚ+"JpẎ€¥"Ʋṭ@€"J,€¥ɗẎ;ṛ/{ṭḷ
Jçƒ0RWW¤Ṫị¹ZPSƊÐṀ

```

Try it online!

Painfully long, but runs pretty fast.

Basic algorithm is to compute all the possible sets of chords (as indices) via memoization. Let's define `f(n)` as the list of all possible sets of chords using first `n` nodes, i.e. `1..n`. `f(0)` and `f(1)` contain a single empty set, and `f(2)` is `[[], [[1, 2]]]`. Also, let's define `f(0..n)` to be `[f(0), f(1), ..., f(n)]`. Then the following recurrence holds:

```
f(n+1) = f(n) ++
  cartesian product of f(0) and (1 + f(n-1)), with [1, n+1] added to each set ++
  cartesian product of f(1) and (2 + f(n-2)), with [2, n+1] added to each set ++
  ... ++
  cartesian product of f(n-1) and (n + f(0)), with [n, n+1] added to each set

```

where `++` is list concatenation and `+` is vectorized addition.

```
ṖṚ+"JpẎ€¥"Ʋṭ@€"J,€¥ɗẎ;ṛ/{ṭḷ    Aux. dyadic link: left=f(0..n), right=n+1
Ṗ                              H = f(0..n-1)
 AAAAAAAAAAbbbbccccɗ           A(H) `b` (H `c` n+1)
 Ṛ+"J                          Reverse H and add 1..n (zipped)
     pẎ€¥"                     Cartesian product by concatenation with H
           ṭ@€"                Zipped append the following to each set:
               J,€¥            [1,n+1], ..., [n,n+1]
                    Ẏ          Collect lists of sets into one list of sets
                     ;ṛ/{      Combine with the sets without n+1
                         ṭḷ    Push into f(0..n) to get f(0..n+1)

Jçƒ0RWW¤Ṫị¹ZPSƊÐṀ    Main link: arg=a list
J                    Indices of the list
 çƒ0RWW¤             Reduce over it using the aux link, starting from [[[]]]
        Ṫị¹          Take the last result; convert the indices to actual values
           ZPSƊÐṀ    Find the set of chords with the highest sum of product

```

Probably I can golf it by *not* taking the right argument of the aux link (which is simply the length of the left arg), but I don't want to torture myself further...

# Answer
> 6 votes
# Jelly,  ~~28~~  27 bytes

```
JŒcŒPŒcZFṢƑ<QƑƊƊ€ẠƊƇịZPSɗÐṀ

```

A monadic Link that accepts a list of integers and yields a list of all most valuable lists of chord-end pairs.

**Try it online!** Very inefficient.

### How?

```
JŒcŒPŒcZFṢƑ<QƑƊƊ€ẠƊƇịZPSɗÐṀ - Link: list A
J                           - get indices -> [1,2,...,length(A)]
 Œc                         - pairs
   ŒP                       - powerset
                   Ƈ        - filter keep those for which:
                  Ɗ         -   last three links as a monad:
     Œc                     -     pairs
                €           -     for each:
               Ɗ            -       last three links as a monad:
       Z                    -         transpose
        F                   -         flatten
              Ɗ             -         last three links as a monad:
          Ƒ                 -           is invariant under:
         Ṣ                  -             sort -> x
             Ƒ              -           is invariant under:
            Q               -             deduplicate -> y
           <                -           (x) less than (y)?
                 Ạ          -     all?
                    ị       - index into (A)*
                         ÐṀ - keep those maximal under:
                        ɗ   -   last three links as a dyad* f(entry, A):
                     Z      -     transpose (the entry)
                      P     -     product (vectorised across this transposed entry)
                       S    -     sum (of those products)

                              * Note: ị takes A on the right Implicitly due to the next
                                      link in the chain (ZPSɗÐṀ) being dyadic (which
                                      it does not need to be), this saves a byte.

```

# Answer
> 5 votes
# Wolfram Language (Mathematica), ~~114~~ ~~98~~ ~~88~~ 86 bytes

```
f@r_:=SortBy[f@Drop[r,#]~Append~r[[#]]&/@Subsets[j=0;++j&/@r,{2}],Dot@@-#&]~Last~{}

```

Try it online!

```
j=0;++j&/@r                     range over input
Subsets[ % ,{2}]                get pairs
f@Drop[r,#]                     recurse on values not between indices
           ~Append~r[[#]]        and append chord
                         /@ %    for each pair
SortBy[ % ,Dot@@-#&]~Last~     get the set of chords with the highest sum of products,
                           {}   if there are no chord sets (i.e. len(r)<2), return an empty set

```

Since `-` has lower precedence than  (`Transpose`), `Dot@@-#&` is interpreted as `Dot@@(-(#))&`, which turns out to be equivalent to `Dot@@(#)&` since the negatives cancel out.

Here's a walkthrough for when `f` is called on `{1,8,2,9}`:

```
r                       =   {1, 8, 2, 9}
j=0;++j&/@r             =   {1, 2, 3, 4}
Subsets[ % ,{2}]        =   {1,2}       {1,3}       {1,4}       {2,3}       {2,4}       {3,4}
map:
    Drop[r,#]           =   {    2 9}   {      9}   {       }   {1     9}   {1      }   {1 8    }
    r[[#]]              =   {1 8    }   {1   2  }   {1     9}   {  8 2  }   {  8   9}   {    2 9}
    Append[f@ %2 ,      =   {{2,9}      {           {           {{1,9}      {           {{1,8}
            % ]         =    {1,8}}      {1,2}}      {1,9}}      {8,2}}      {8,9}}      {2,9}}
sorting function:
    Dot@@-#            =   26          2           9           25          72          26
SortBy[ ... ]~Last~{}   =                                                   {{8,9}}

```

# Answer
> 4 votes
# Python 3, ~~135~~ 117 bytes

```
f=lambda x:x and max([[[x[0],v]][:i]+f(x[1:i])+f(x[i+1:])for i,v in enumerate(x)],key=lambda y:sum(a*b for a,b in y))

```

-18 thanks to @ovs and @dingledooper

thanks to @EliteDaMyth for earlier correction

Try it online!

# Answer
> 3 votes
# Jelly, 29 bytes

```
JŒcŒPFQƑ$ƇŒcZFṢƑƊƇƊÐḟị¹P€S$ÐṀ

```

Try it online!

This is a total mess, extremely inefficient, possibly not working correctly and probably very outgolfable.

*-2 bytes thanks to caird*

---
Tags: code-golf
---


title: When integers join the queue

text:
# Question
Title: When integers join the queue
### Introduction

A **queue** is an abstract data type where elements are **added to the front** (enqueue) and **removed from the back** (dequeue). This is also known as the FIFO (First In First Out) principle.

It is best shown with an example:

---

### Challenge

Given a **non-empty** array that contains **positive integers** and **elements that indicate a *dequeue*** (removing an element), output the final list of the queue.

Let's say that `X` denotes a dequeue in this example. Let's take a look at the following list:

```
[45, X, X, 37, 20, X, 97, X, 85]

```

This can be translated to the following queue-pseudo code:

```
                   Queue
Enqueue 45    ->   45
Dequeue       ->
Dequeue       ->              (dequeue on an empty queue is a no-op)
Enqueue 37    ->   37
Enqueue 20    ->   20 37
Dequeue       ->   20
Enqueue 97    ->   97 20
Dequeue       ->   97
Enqueue 85    ->   85 97

```

You can see that in the end, the result is `[85, 97]`, which is the output for this sequence.

---

### Test cases

**Note** that you may choose any other symbol or character for `X`, as long as it's not a positive integer.

```
[1, X, 2, X, 3, X]      ->     []
[1, 2, X]               ->     [2]
[1, 2, 3]               ->     [3, 2, 1]
[1, 2, X, X, X, 3]      ->     [3]
[1, 2, X, 3, X, 4]      ->     [4, 3]

```

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

# Answer
# Jelly, 8 bytes

```
F;@Ṗṛ?¥/

```

Uses any falsy value (**0** or empty iterable) to dequeue.

Try it online!

### How it works

```
F;@Ṗṛ?¥/  Main link. Argument: A (array)

       /  Reduce A by the link to the left.
      ¥     Combine the two links to the left into a dyadic chain.
F             Flatten the left argument.
    ṛ?        If the right argument is truthy:
 ;@             Concatenate the right argument and the flattened left argument.
              Else:
   Ṗ            Pop; remove the last element of the flattened left argument.
                This is why flattening is required, as Ṗ doesn't handle integers
                as intended for this challenge.

```
> 4 votes

# Answer
# Python 2, ~~56~~ ~~53~~ 50 bytes

```
q=[]
for i in input():q=[[i]+q,q[:i]][i<0]
print q

```

Try it Online!

Dequeue is `-1`. This trick allows easy pythonic slicing of the queue.
> 8 votes

# Answer
# Mathematica, 102 bytes

Definitely not the shortest solution, but I couldn't resist because it's kind of perverse.

```
r=Reverse@{##}&
a_~f~b___:=b
f[a_,b___,]:=b
ToExpression[{"r[","f["~Table~StringCount[#,"]"],#}<>"]"]&

```

After some helper functions, this defines a pure function that takes a string as input: in the string, numbers are separated by commas (whitespace is optional); the dequeue character is `"]"`; and the list does not have delimiters in the front or back. For instance, the first example in the OP would be input as the string `"45,],],37,20,],97,],85"`. The output of the function is a list of numbers.

The function counts how many dequeues `"]"` are in the input string, appends that many copies of `"f["` to the front of the string, and then surrounds the whole thing by `"r[...]"`. In the example above, this produces `"r[f[f[f[f[45,],],37,20,],97,],85]"`; notice the brackets are balanced.

Then, `ToExpression` interprets the resulting string as a piece of Mathematica code and executes it. The function `f` is conveniently defined to retain all its arguments except the first (and also ignores trailing commas; this is necessary to handle dequeueing empty queues anyway), and `r` converts the resulting sequence of numbers into a list of numbers in the right order.
> 7 votes

# Answer
# Retina, 30 bytes

```
1+`\d+,(.*?)X,?|^X,
$1
O^$`\d+

```

Try it online!

Repeatedly removes the first number that's (not necessarily immediately) followed by an `X` together with that `X`, or an `X` at the beginning of the string. Then reverses the remaining numbers.
> 4 votes

# Answer
# JavaScript, ~~70~~ ~~63~~ ~~53~~ ~~50~~ 43 bytes

Thanks @Neil for golfing off 10 bytes with x.map instead of for loop and ternary expression

Thanks @Arnauld for golfing off 3 bytes

Thanks @ETHproductions for golfing off 7 bytes

```
x=>(t=[],x.map(a=>+a?t=[a,...t]:t.pop()),t)

```

Try it online!

Dequeue can be any non-numeric value other than true.
> 4 votes

# Answer
## Mathematica, ~~46~~ 45 bytes

*Thanks to ngenisis for saving 1 byte.*

```
Reverse[#//.{_Integer:0,a___,X,b___}:>{a,b}]&

```

Basically the same as my Retina answer, using pattern matching. We repeatedly match the first `X` and remove it along with the first number (if one exists). After we're done, we reverse the list.
> 3 votes

# Answer
# MATL, ~~13~~ 12 bytes

```
vi"@?@wh}IL)

```

Input is an array of numbers, with `0` for "dequeue".

Output is numbers separated by spaces. An empty result is shown as nothing.

Try it online! Or verify all test cases.

### Explanation

```
v        % Concatenate stack contents: gives []. This will grow to represent the queue
i        % Input numeric array
"        % For each entry in the input array
  @?     %   If current entry is non-zero
    @wh  %     Prepend current entry to the queue
  }      %   Else
    IL)  %     Remove last element from the queue
         %   End (implicit)
         % End (implicit)
         % Display (implicit)

```
> 3 votes

# Answer
# Pure Bash, 72

Input given as command-line parameters.

```
for a;{
[ ${a/X} ]&&q=(${a:n++,0} ${q[@]})||((n-=n>0))
}
echo ${q[@]::n}

```

Try it online.
> 3 votes

# Answer
# Haskell, ~~41~~ 40 Bytes

```
l#a|a>0=a:l|l>[]=init l|1>0=l

```

Function is `foldl(#)[]` (Also included in bytecount with a byte of separation in between)

Try it online!

X is any non-positive integer

EDIT: -1 byte thanks to nimi
> 3 votes

# Answer
# Haskell, 41 bytes

```
x&y:z|y<1=init x&z|w<-y:x=w&z
x&y=x
([]&)

```
> 3 votes

# Answer
# Julia, ~~78~~ ~~76~~ ~~73~~ 57 bytes

```
f(a)=(q=[];[x<1?q=q[2:end]:push!(q,x)for x=a];reverse(q))

```

Thanks to Harrison Grodin for some excellent Julia golfing suggestions. Replaced if/else with ternary and for/end with list comprehension for a savings of 16 bytes.

```
f(a)=(q=[];for x in a if x<1 q=q[2:end]else q=[q...,x]end end;reverse(q))

```

Removed some unnecessary spaces for a savings of 3 bytes.

Before negative numbers or zero were allowed:

```
f(a)=(q=[];for x in a if x==:X q=q[2:end] else q=[q...,x] end end;r everse(q))

```

Ungolfed:

```
function dequeue(list)
    queue = []

    for x in list
        if x < 1
            queue = queue[2:end]
        else
            queue = [queue..., x]
        end
    end

    reverse(queue)
end

```

I'm fairly new to Julia; there may be a better way. Uses `:X` for X, which is a Symbol in Julia. Updated: Now that 0 is allowed, uses 0 (or any negative number) for X, saving two characters. Updated again to remove some whitespace that I didn't realize wasn't needed.
> 3 votes

# Answer
# PHP, 85 Bytes

```
<?$r=[];foreach($_GET as$v)is_int($v)?array_unshift($r,$v):array_pop($r);print_r($r);

```

-8 Bytes `$v` instead of `is_int($v)`if every dequeue value belongs to false
> 2 votes

# Answer
# 05AB1E, ~~12~~ 11 bytes

Saved a byte thanks to *Riley*

```
)Evyai¨ëy¸ì

```

Try it online!

**Explanation**

Dequeues are denoted by *any letter*.

```
)             # wrap stack in a list (pushes empty list)
 Ev           # for each y in evaluated input
   yai        # if y is a letter
      ¨       # remove the first element of the list
       ëy¸ì   # else, prepend y to the list

```
> 2 votes

# Answer
# GNU Sed, 43

Score includes +2 for use of the `-r` and `-n` flags.

```
G
s/X\n( *|(.*)\b\S+ *)$/\2/
s/\n/ /
h
$p

```

Try it online.

### Explanation

```
                            # Implicitly read the next line
G                           # append a newline, then the contents of the hold space
s/X\n( *|(.*)\b\S+ *)$/\2/  # If the input was an X, remove it, the newline, and any element at the end
s/\n/ /                     # Otherwise if the input was not an X, it is simply enqueued by removing the newline between it and the rest of the line
h                           # save a copy of the queue to the hold space
$p                          # since we're using -n to suppress output at the end of processing each input line, then this explicit print is required in the last line

```
> 2 votes

# Answer
# Python 3, ~~95~~ 94 bytes

```
def f(x):q=[];[*map(lambda s:exec(("q.pop(0)"if q else"","q+=[s]")[s!="X"]),x)];print(q[::-1])

```

Try it online!

Also 94 bytes:

```
def f(x):q=[];[*map(lambda s:exec((("","q.pop(0)")[q>[]],"q+=[s]")[s!="X"]),x)];print(q[::-1])

```
> 2 votes

# Answer
# Perl 5, 28 + 1 = 29 bytes

28 bytes of code + `-p` flag.

```
/\d/?$\=$_.$\:$\=~s/.*
$//}{

```

Try it online!

It uses a string (`$\`) as the queue: when the input contains an integer (`/\d/?`, we append it at the beginning of `$\` (`$\=$_.$\`), and otherwise, we remove the last one with `s/.*\n$//`. At the end, `$\` is implicitly printed thanks to `-p` flag (and those unmatched `}{`).

---

Other approaches:

* **33 bytes**, using an array as the queue (it's the most natural way to do it in Perl I think, but not the shortest):

```
/X/?pop@F:unshift@F,$_}{$_="@F"

```

Try it online!
* **52 bytes**, using regex and `reverse` (it happens to be quite exactly the same thing as Martin Ender's Retina answer - thanks to whom I saved 2 bytes on it). Reversing the list takes a lot of characters though, because to preserve the integers, I have to convert the string to an array to reverse it, then back to a string to print it. (`say for` instead of `$_=join$",` can save 2 bytes, but it requires `-E` or `-M5.010` and it's not that interesting).

```
s/\d+ (.*?)X ?|^X/$1/&&redo;$_=join$",reverse split

```

Try it online!
> 2 votes

# Answer
## Swift 3, 70 bytes

Assuming we have an array of Ints like `let x = [1, 2,-1,3,-1,4]`

```
print(x.reduce([].prefix(0)){(a,i)in return i>0 ?[i]+a:a.dropLast(1)})

```

Note that `[].prefix(0)` is a sneaky way to get an empty ArraySlice
> 2 votes

# Answer
# C++, ~~122~~ 119 bytes

```
#import<list>
void f(std::list<int>o,std::list<int>&q){for(int i:o)if(i)q.push_front(i);else if(q.size())q.pop_back();}

```

0 indicates a dequeue.

Try it online!
> 1 votes

# Answer
# Python 2, 58 bytes

```
def f(x,r=[]):
 for i in x:r=i and[i]+r or r[:-1]
 print r

```

Try it online!

Uses `0` as a dequeue value

-10 bytes thanks to pxeger
> 1 votes

# Answer
## Batch, 160 bytes

```
@set s=.
@for %%n in (%*)do @if %%n==X (call set s=%%s:* =%%)else call set s=%%s:~,-1%%%%n .
@set t=
@for %%n in (%s:~,-1%)do @call set t= %%n%%t%%
@echo%t%

```

This was harder than it needed to be.

* Although Batch can enumerate the result of splitting a string, it can't easily remove an element from the enumeration.
* It can remove the first item, but only if there is at least one item. Otherwise you get garbage.

This means that I a) need to have an end-of-queue marker, which doesn't get removed, and b) have to manipulate the queue back-to-front, so new items get inserted in just before the end marker, so that old items can be removed from the front, which then means I c) have to reverse the queue before printing it.
> 1 votes

# Answer
# PHP, 70 bytes

```
foreach($argv as$v)+$v?$r[]=$v:array_shift($r);krsort($r);print_r($r);

```
> 1 votes

# Answer
# C#, 115 bytes +33 bytes for using

```
l=>{var r=new List<int>();foreach(var n in l)if(n<0)try{r.RemoveAt(0);}catch{}else r.Add(n);r.Reverse();return r;};

```

Anonymous method which returns a list of integers after performing the en-queuing and dequeuing operations. Negative integers are used for removing elements from the queue.

Full program with ungolfed method and test cases:

```
using System;
using System.Collections.Generic;

public class Program
{
    static void PrintList(List<int> list)
    {
        var s = "{";
        foreach (int element in list)
            s += element + ", ";
        if (s.Length > 1)
            s += "\b\b";
        s += "}";
        Console.WriteLine(s);
    }

    public static void Main()
    {
        Func<List<int>, List<int>> f =
        l =>
        {
            var r = new List<int>();
            foreach (var n in l)
                if (n < 0)
                    try
                    {
                        r.RemoveAt(0);
                    }
                    catch
                    { }
                else
                    r.Add(n);
            r.Reverse();
            return r;
        };

        // test cases:
        var list = new List<int>(new[]{1, -1, 2, -1, 3, -1});   // {}
        PrintList(f(list));

        list = new List<int>(new[]{1, 2, -1});  // {2}
        PrintList(f(list));

        list = new List<int>(new[]{1, 2, 3});   // {3, 2, 1}
        PrintList(f(list));

        list = new List<int>(new[]{1, 2, -1, -1, -1, 3});   // {3}
        PrintList(f(list));

        list = new List<int>(new[]{1, 2, -1, 3, -1, 4});    // {4, 3}
        PrintList(f(list));
    }
}

```
> 1 votes

# Answer
# Scala, 97 bytes

```
type S=Seq[_];def f(a:S,b:S):S=a match{case h::t=>f(t,if(h==0)b dropRight 1 else h+:b);case _=>b}

```

As input, `f` takes a list with `0` as the "dequeue" element. It uses tail-recursion with a second parameter (`b`), acting as an accumulator. Initially, `b` is the empty `Seq` (`Nil`).

**Explanations :**

```
type S=Seq[_]                               // defines a type alias (save 1 byte since Seq[_] is used 3 times)
def f(a: S, b: S): S = {                    // a is the initial list, b is an accumulator
    a match {
        case h::t =>                        // if a is non-empty
            f(t,                            // recursive call to f with 1st parameter as the tail
                if (h==0) b dropRight 1     // if h == 0 (dequeue) then remove last element of b,
                else h+:b                   // otherwise, just add h at the beginning of b in recursive call
            )
        case _ => b                         // when the list is empty, return b (final result)
    }
}

```

*Note :* `b dropRight 1` is used instead of `b.tail` to avoid exception : `tail of empty list`.

**Test cases :**

```
f(Seq(45, 0, 0, 37, 20, 0, 97, 0, 85), Nil)     // List(85, 97)
f(Seq(1, 0, 2, 0, 3, 0), Nil)                   // List()
f(Seq(1, 2, 0), Nil)                            // List(2)
f(Seq(1, 2, 3), Nil)                            // List(3, 2, 1)
f(Seq(1, 2, 0, 0, 0, 3), Nil)                   // List(3)
f(Seq(1, 2, 0, 3, 0, 4), Nil)                   // List(4, 3)

```

`f` can also work with other types (`String`, `char`, ..., even heterogeneous list of those types!) :

```
f(Seq(false, '!', "world", 0, "Hello"), Nil)    // List(Hello, world, !)

```
> 1 votes

# Answer
## REXX, 115 bytes

```
arg n
do while n>''
  parse var n m n
  if m=X then pull
  else queue m
  end
o=
do while queued()>0
  pull a
  o=a o
  end
say o

```

Takes a space-separated string, prints a space separated string
> 1 votes

# Answer
# Ruby, ~~65~~ 54 bytes

```
q=[];(eval$*[0]).each{|i|q=[i]+q;q=q[1..-2]if i<0};p q

```

The separator can be any negative number.
> 1 votes

# Answer
# K (ngn/k), ~~18~~ 17 bytes

-1 byte from @ngn

```
(){$[y;y,;-1_]x}/

```

Try it online!

Uses `0` as the dequeue element.

* `(){...}/` set up a reduction seeded with `()` (an empty list), over the (implicit) input
* `$[...]x` apply `x` (the queue) to the result of `$[]` (cond)
* `$[y;y,;-1_]` depending on the new value (i.e. if it is `0` or isn't), return a function projection either prepending the new value (`y,`), or dequeuing the last element (`-1_`)
> 1 votes

# Answer
# , 18 bytes

```
(*@[;@{}:@];,)/@|.

```

Try it online!

* `(...)/@|.` Reverse and reduce by verb in parens...
* `}:@];,` Create the two options (regular vs deque, represented by `0`) as a boxed pair: left elm is the deque case (ie, accumlator with tail removed `}:@]`) and right elm is the normal case (new elm appended as head `,`).
* `(*@[...{` Pick the correct case, which is the signum of the left argument in the reduction `*@[`, from our boxed pair `{`...
* `;@` And unbox it.
> 1 votes

# Answer
# Zsh, 46 bytes

```
for a (`<&0`)$a&&{shift -p;:}||set $a $@
<<<$@

```

Try it online!
> 0 votes

# Answer
# Julia 0.7, 41 bytes

```
!a=(q=[];a.|>i->q=i>0?[i;q]:q[1:end-1];q)

```

Try it online!
> 0 votes

---
Tags: code-golf, number, array
---


# Question
Title: Tips for golfing in Binary Lambda Calculus
BLC (Binary Lambda Calculus) is a binary encoding of untyped lambda calculus which was created to “provide a very simple and elegant concrete definition of descriptional complexity.”

What are some tips on how to golf down BLC programs/functions?

Please submit only one tip per answer!

# Answer
This is fairly obvious but I'll put it here for completeness sake. It also applies to untyped lambda calculus in general so I'll write it like that for readability.

Anywhere you want reuse a value/function that is at least as long as this expression

$$(\lambda v.p) \space d$$

you can declare it as a variable. Here "p" is the original program with all the original instances of your repeated value replaced by "v". "d" is the definition of the repeated value itself.

**A contrived example**

A program like this

$$(\lambda f.\lambda z.f f f f f z) (\lambda f.\lambda z.f f f f f z)(\lambda f.\lambda z.f f f f f z)$$

can be written as

$$(\lambda v.vvv)(\lambda f.\lambda z.f f f f f z)$$

This is a simple example but it's a neat abstraction because "v" can be used however deeply nested you decide to make "p".
> 2 votes

---
Tags: code-golf, tips, lambda-calculus
---


title: New Order #6: Easter Egg

text:
# Question
Title: New Order #6: Easter Egg
## Introduction *(may be ignored)*

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

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

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

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

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

```

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

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

## Task

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

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

## Test cases

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

```

## Rules

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

# Answer
> 12 votes
# Jelly,  ~~16 14 11 10 9~~  8 bytes

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

```
|1×r)ẎQi

```

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

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

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

### How?

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

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

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

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

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

```

# Answer
> 6 votes
# JavaScript (ES7),  ~~46 45~~  41 bytes

0-indexed.

```
n=>((x=n**.5+1&~1)*2-(n<x*x+x)*4+3)*x+1-n

```

Try it online!

### How?

This is based on the 1-indexed formula used in the example programs of A090861.

\\$x\_n\\$ is the layer index of the spiral, starting with \\$0\\$ for the center square:

$$x\_n=\left\lfloor\frac{\sqrt{n-1}+1}{2}\right\rfloor$$

Try it online!

\\$k\_n\\$ is set to \\$6\\$ for the bottom part of each layer (including the center square), and to \\$-2\\$ everywhere else:

$$k\_n=\begin{cases} -2&\text{if }n\le 4{x\_n}^2+2x\_n\\ 6&\text{otherwise} \end{cases}$$

Try it online!

Then \\$a\_n\\$ is given by:

$$a\_n=8{x\_n}^2+k\_nx\_n+2-n$$

Try it online!

Which can be translated into:

```
n=>8*(x=(n-1)**.5+1>>1)*x+(n<=4*x*x+2*x?-2:6)*x+2-n

```

Making it 0-indexed saves 5 bytes right away:

```
n=>8*(x=n**.5+1>>1)*x+(n<4*x*x+2*x?-2:6)*x+1-n

```

The formula can be further simplified by using:

$${x'}\_n=2\times\left\lfloor\frac{\sqrt{n}+1}{2}\right\rfloor$$

which can be expressed as:

```
x=n**.5+1&~1

```

leading to:

```
n=>2*(x=n**.5+1&~1)*x+(n<x*x+x?-1:3)*x+1-n

```

and finally:

```
n=>((x=n**.5+1&~1)*2-(n<x*x+x)*4+3)*x+1-n

```

# Answer
> 5 votes
# Wolfram Language (Mathematica), 60 bytes

```
8(s=⌊(⌊Sqrt[#-1]⌋+1)/2⌋)^2-#+2+If[#<=4s^2+2s,-2,6]s&

```

Try it online!

# Answer
> 5 votes
# MATL, ~~12~~ 11 bytes

```
Eq1YL!tPG=)

```

Try it online!

Very memory-inefficient. Prepending `X^k` makes it more efficient.

# Answer
> 3 votes
# C# (Visual C# Interactive Compiler), 67 bytes

```
n=>8*(x=(int)Math.Sqrt(--n)+1>>1)*x+(n<4*x*x+2*x?-2:6)*x+1-n;int x;

```

Try it online!

# Answer
> 3 votes
# Python 3.8, ~~104~~ ~~74~~ ~~65~~ ~~60~~ 57 bytes

```
lambda n:(-2,6)[n>4*(x:=(n**.5+1)//2)*x+2*x]*x+2+~n+8*x*x

```

Edit: Thanks to Johnathan Allan for getting it from 74 to 57 bytes!

This solution uses 0-based indexing.

# Answer
> 3 votes
# Python 3.8 (pre-release), 53 bytes

A direct port of Arnauld's JavaScript answer, go upvote that, and/or J42161217's Mathematica answer, and/or Kapocsi's Python answer :)

```
lambda n:((x:=int(n**.5+1)&-2)*2-(n<x*x+x)*4+3)*x+1-n

```

0-indexed.

**Try it online!**

# Answer
> 2 votes
# Befunge, ~~67~~ 57 bytes

This solution assumes 0-based indexing for the input values.

```
p&v-*8p00:+1g00:<
0:<@.-\+1*g00+*<|`
0g6*\`!8*2+00g4^>$:0

```

Try it online!

**Explanation**

We start by calculating the "radius" at which the input *n* is found with a loop:

```
radius = 0
while n > 0
  radius += 1
  n -= radius*8

```

At the end of the loop, the previous value of *n* is the offset into the spiral at that radius:

```
offset = n + radius*8

```

We can then determine if we're on the top or bottom section of the spiral as follows:

```
bottom = offset >= radius*6

```

And once we have all these details, the spiral value is calculated with:

```
value = ((bottom?10:2) + 4*radius)*radius + 1 - offset

```

The radius is the only value that we need to store as a "variable", limiting it to a maximum value of 127 in Befunge-93, so this algorithm can handle inputs up to 65024.

# Answer
> 1 votes
# Japt, 15 bytes

Port of Jonathan's Jelly solution. 1-indexed.

```
gUòÈ²+X*v)õÃcÔâ

```

Try it

```
gUòÈ²+X*v)õÃcÔâ     :Implicit input of integer U
g                   :Index into
 Uò                 :  Range [0,U]
   È                :  Map each X
    ²               :    Square X
     +X*            :    Add X multiplied by
        v           :    1 if X is divisible by 2, 0 otherwise
         )          :    Group result
          õ         :    Range [1,result]
           Ã        :  End map
            c       :  Flatten
             Ô      :    After reversing each
              â     :  Deduplicate

```

# Answer
> 1 votes
# Husk, 11 bytes

```
!uṁS`…S*v1N

```

Try it online!

Instead of creating a range, an infinite list is created and nubbed. Hence, will be be very very slow for larger \\$n\\$

# Answer
> 0 votes
# C++ (gcc), 88 bytes

```
#import<cmath>
int a(int n){int x=(sqrt(n-1)+1)/2;return x*(8*(x+(n>4*x*x+2*x))-2)+2-n;}

```

1-indexed; uses the formula on the OEIS page, but manipulated to save a few bytes.

Try it online!

# Answer
> 0 votes
# Vyxal, 13 bytes

```
ƛ1⋎*›rṘ;fU?‹i

```

Try it Online!

Messy port

---
Tags: code-golf, sequence
---


title: Rejecting invalid IPv4 addresses

text:
# Question
Title: Rejecting invalid IPv4 addresses
I want to avoid responding to illegal or spoofed addresses. One type that's easy to detect is an address that should not exist on a packet received by my router: a special-use address.

## Challenge

Given an IPv4 32-bit address, identify whether it is valid general-use address.

## Challenge rules

* Special-use addresses, as defined by the Internet Engineering Task Force, are considered invalid.
* Special-use addresses are listed at https://en.wikipedia.org/wiki/IPv4#Special-use\_addresses. A copy of the list (omitting explanatory columns) is below.
* Input will be a character sequence in the dot-decimal notation, consisting of four positive decimal numbers (called "octets") each in the range 0–255 separated by periods (e.g., 169.254.0.31). Each octet represents an 8-bit segment of the address.
* Output must indicate true or false, using any two indicators of your choice for true and false.

## General rules:

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

## Test cases:

* 192.0.0.254 false
* 192.0.1.254 true
* 0.255.0.0 false
* 128.2.3.82 true
* 253.8.22.37 false
* 203.0.114.201 true

## Special-use addresses

| Address Block | Address Range |
| --- | --- |
| 0.0.0.0/8 | 0.0.0.0–0.255.255.255 |
| 10.0.0.0/8 | 10.0.0.0–10.255.255.255 |
| 100.64.0.0/10 | 100.64.0.0–100.127.255.255 |
| 127.0.0.0/8 | 127.0.0.0–127.255.255.255 |
| 169.254.0.0/16 | 169.254.0.0–169.254.255.255 |
| 172.16.0.0/12 | 172.16.0.0–172.31.255.255 |
| 192.0.0.0/24 | 192.0.0.0–192.0.0.255 |
| 192.0.2.0/24 | 192.0.2.0–192.0.2.255 |
| 192.88.99.0/24 | 192.88.99.0–192.88.99.255 |
| 192.168.0.0/16 | 192.168.0.0–192.168.255.255 |
| 198.18.0.0/15 | 198.18.0.0–198.19.255.255 |
| 198.51.100.0/24 | 198.51.100.0–198.51.100.255 |
| 203.0.113.0/24 | 203.0.113.0–203.0.113.255 |
| 224.0.0.0/4 | 224.0.0.0–239.255.255.255 |
| 240.0.0.0/4 | 240.0.0.0–255.255.255.255 |

Note on address blocks. This is a shortcut method of listing an address range, called CIDR notation. The notation is four octets followed by a slash and a decimal number. The decimal number is the count of leading 1 bits in the network mask, and indicates how many leading bits in the underlying 32-bit address range are specified as fixed. For example, a mask of 24 indicates that only the last 8 bits of the address range vary. Thus writing 192.0.2.0/24 indicates that only the last octet varies. The range for 192.0.2.0/24 is 192.0.2.0–192.0.2.255.

# Answer
> 7 votes
# JavaScript (ES6),  ~~179~~  178 bytes

*Saved 1 byte thanks to @StackMeter's suggestion of merging the last 2 blocks*

Expects a string and returns a Boolean value.

```
s=>'00000g0chhqo3h65u64ekjyo5w90qw5yu2vg6nq96o6nq98g6o5rvk6ojr486vb4096vgz2871grvk7romqd'.match(/.{6}/g,[a,b,c]=s.split`.`).every(S=>(x=parseInt(S,36))>>5^(a<<16|b<<8|c)&-(1<<x))

```

Try it online!

## How?

### Encoding of address blocks

Our data string encodes all blocks of special-use addresses.

We can notice that the 4th byte is always \\$0\\$ and can be ignored. Given a block in CIDR notation `A.B.C.D/M`, what's actually encoded is:

```
A << 21 | B << 13 | C << 5 | (24 - M)

```

This is a 29-bit value which fits in 6 characters in base 36.

For instance, `169.254.0.0/16` is encoded as:

```
169 << 21 | 254 << 13 | 0 << 5 | (24 - 16) = 356499464

```

which is `5w90qw` in base 36.

## IP test

Given an IP address \\$s\\$, we first extract the first 3 bytes into \\$(a,b,c)\\$ and ignore the 4th one:

```
[a, b, c] = s.split`.`

```

For each 29-bit encoded block address \\$x\\$, we do the following test:

```
x >> 5 ^ (a << 16 | b << 8 | c) & -(1 << x)

```

where `-(1 << x)` is our 24-bit subnet mask.

Conveniently, we can do `1 << x` without isolating the 5 least significant bits of \\$x\\$ because this is done implicitly by the shift operations, by ECMAScript specification.

# Answer
> 2 votes
# Retina 0.8.2, 138 bytes

```
\.
-
2=`\d+
$*
^(0|10|100-1{64,127}|127|169-1{254}|172-1{16,31}|192--[02]|192-1{88}-99|192-1{168}|198-1{51}-100|203--113|22[4-9]|2[3-5].)-

```

Try it online! Link includes test cases. Outputs `1` for special use, `0` for general use. Explanation:

```
\.
-

```

Change the `.`s to `-`s because `.`s are special in regex.

```
2=`\d+
$*

```

Convert the second octet to unary.

```
^(0|10|100-1{64,127}|127|169-1{254}|172-1{16,31}|192--[02]|192-1{88}-99|192-1{168}|198-1{51}-100|203--113|22[4-9]|2[3-5].)-

```

Match the given special use addresses.

# Answer
> 1 votes
# Python 3 - 307 bytes

```
a=input()
f=int
b,c,d,e=a.split(".")
b,c,d,e=f(b),f(c),f(d),f(e)
print(not(not(b==0or b==10or (b==100and 63<c<128)or b==127or(b,c==169,254)or(b==172and 15<c<32)or(b,c,d==192,0,0)or(b,c,d==192,0,2)or(b,c,d==192,88,89)or(b,c==192,168)or(b==198and 17<c<20)or(b,c,d==198,51,100)or(b,c,d==203,0,113)or b>223)))

```

Try it online!

Fun challenge - hooray for conditionals!

Just runs the appropriate tests and gives a value of true or false (the not(not()) was necessary, else it would return a tuple for some reason).

Fairly optimized for the method (I did use b,c,d == instead of b == and c == and d ==, and stripped many spaces), but this could easily be golfed by someone better. (-34 from Razetime)

# Answer
> 1 votes
# JavaScript, 154 bytes

```
s=>[[a,b,c]=s.split`.`,a-10,a%127,a<224,(b|=a<<8)>>6^401,b>>4^2753,b/2^25353,b-43518,b-49320,b-49152|c&-3,d=b-49240<<8|c-99,d-383745,d-698382].some(x=>!x)

```

Try it online!

This answer simply translate the table to a formula.

| Address block | Address range | Formula |
| --- | --- | --- |
| 0.0.0.0/8 | 0.0.0.0 ~ 0.255.255.255 | `[a,b,c]=s.split`.`,a%127` |
| 10.0.0.0/8 | 10.0.0.0 ~ 10.255.255.255 | `a-10` |
| 127.0.0.0/8 | 127.0.0.0 ~ 127.255.255.255 | `a%127` |
| 224.0.0.0/4 | 224.0.0.0 ~ 239.255.255.255 | `a<224` |
| 240.0.0.0/4 | 240.0.0.0 ~ 255.255.255.255 | `a<224` |
| 100.64.0.0/10 | 100.64.0.0 ~ 100.127.255.255 | `(b|=a<<8)>>6^401` |
| 172.16.0.0/12 | 172.16.0.0 ~ 172.31.255.255 | `b>>4^2753` |
| 198.18.0.0/15 | 198.18.0.0 ~ 198.19.255.255 | `b/2^25353` |
| 169.254.0.0/16 | 169.254.0.0 ~ 169.254.255.255 | `b-43518` |
| 192.168.0.0/16 | 192.168.0.0 ~ 192.168.255.255 | `b-49320` |
| 192.0.0.0/24 | 192.0.0.0 ~ 192.0.0.255 | `b-49152|c&-3` |
| 192.0.2.0/24 | 192.0.2.0 ~ 192.0.2.255 | `b-49152|c&-3` |
| 192.88.99.0/24 | 192.88.99.0 ~ 192.88.99.255 | `d=b-49240<<8|c-99` |
| 198.51.100.0/24 | 198.51.100.0 ~ 198.51.100.255 | `d-383745` |
| 203.0.113.0/24 | 203.0.113.0 ~ 203.0.113.255 | `d-698382` |

# Answer
> 0 votes
# Python 3, 248 bytes

```
b,c,d,e=[*map(int,input().split("."))]
a=192
print(not(not(b==0 or b==10or(b==100and 63<c<128)or b==127or(b,c==169,254)or(b==172and 15<c<32)or(b,c,d in[a,0,0],[a,0,2],[a,88,89],[198,51,100],[203,0,113])or(b,c==a,168)or(b==198and 17<c<20)or b>223)))

```

Try it online!

-1 byte thanks to hyper-neutrino

# Answer
> 0 votes
# Python 3, 173 bytes

```
a,b,c,d=map(int,input().split("."))
b|=a<<8
d=b-49240<<8|c-99
print(214>a-10!=0<a%127<b>>6!=401>0<b>>4^2753<25353!=b>>1<43518!=b!=49320>b-49152|c&-3!=0!=d!=383745<698382!=d)

```

Try it online!

Never write `a!=10and a!=127` in python ! try `10!=a!=127` instead!

---
Tags: code-golf, decision-problem
---


title: What's my telephone number?

text:
# Question
Title: What's my telephone number?
# Introduction

The *telephone numbers* or *involution numbers* are a sequence of integers that count the ways \\$n\\$ telephone lines can be connected to each other, where each line can be connected to at most one other line. These were first studied by Heinrich August Rothe in 1800, when he gave a recurrence equation where they may be calculated. It is sequence A000085 in the OEIS.

## Some help

* The first terms of the sequence are \\$1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496\\$
* It can be described by the recurrence relation \\$T(n)=T(n-1)+(n-1)T(n-2)\\$ (starting from \\$n=0\\$)
* It can be expressed exactly by the summation \\$T(n)=\sum\limits\_{k=0}^{\lfloor n/2 \rfloor}{n\choose 2k}(2k-1)!!=\sum\limits\_{k=0}^{\lfloor n/2 \rfloor}\frac{n!}{2^k(n-2k)!k!}\\$ (starting from \\$n=0\\$)
* There are other ways to get the telephone numbers which can be found on the Wikipedia and OEIS pages

# Challenge

Write a program or function which returns the \\$n^{th}\\$ telephone number.

# I/O examples

```
(0 based indexing)
input --> output

0  -->            1
10 -->         9496
16 -->     46206736
22 --> 618884638912

```

# Rules

* Input will be the index of the sequence
* The index origin can be anything
* As the numbers can get very large, you only need to support numbers as large as your language can handle
* Standard I/O rules apply
* No standard loopholes
* This is so shortest code in bytes wins

# Answer
# Oasis, ~~7~~ ~~6~~ 5 bytes

```
àn*+1

```

Try it online!

```
# to compute the nth telephone number f(n):
à      # push the telephone numbers f(n-1) and f(n-2)
 n     # push n
  *    # multiply: n * f(n-2)
   +   # add: n * f(n-2) + f(n-1)

1      # base case: f(0) = 1

```
> 15 votes

# Answer
# Python, 33 bytes

```
f=lambda n:n<2or~-n*f(n-2)+f(n-1)

```

Try it online!

Uses the recursive formula.
> 20 votes

# Answer
# cQuents, 10 bytes

```
=1:Z+Y($-2

```

1-indexed.

Try it online!

## Explanation

```
=1           first term in sequence is 1
  :          given n, output nth term in sequence (1-indexed)
             each term is
   Z+                     (n-1) term +
     Y                                 (n-2) term *
      ($-2                                          (index - 2)

```
> 9 votes

# Answer
# TI-BASIC, ~~28~~ 22 bytes

```
∑((Ans nCr (2K))(2K)!/(2^KK!),K,0,int(.5Ans

```

Input is *n* in Ans.
Output is the *n*th telephone number.

I was going to use the first formula mentioned in the challenge, but testing it resulted in **ERROR: OVERFLOW**s even on smaller numbers because TI-BASIC handles `n!!` as two successive factorials instead of a double factorial.
At least it has a builtin for summation notation!

**Update:**

I found that \\$(2k-1)!!=\frac{(2k)!}{2^kk!}\\$, so i replaced the function i was using to \\${{n}\choose{2k}}\frac{(2k)!}{2^kk!}\\$, which is represented as `(Ans nCr (2K))(2K)!/(2^KK!)` in TI-BASIC.

**Explanation:**

```
∑((Ans nCr (2K))(2K)!/(2^KK!)               ;sum the equation mentioned above
                             ,K             ;using K as the loop variable
                               ,0           ;starting at 0
                                 ,int(.5Ans ;and ending at the floor of half of the input
                                            ;leave the result in Ans
                                            ;implicit print of Ans

```

**Examples:**

```
10:prgmCDGF26
            9496
5:prgmCDGF26
              26

```

**Note:** TI-BASIC is a tokenized language. Character count does *not* equal byte count.
> 8 votes

# Answer
# Jelly, 6 bytes

```
Œ!ỤƑ€S

```

A monadic Link accepting a non-negative integer which yields a positive integer.

**Try it online!** Or see the first 10 (`n=10` is too slow)

### How?

Builds all permutations of `[1...n]` (or if `n=0` just `[[]]`) and counts the number which are involutions.

```
Œ!ỤƑ€S - Link: integer, n     e.g.  0        3
Œ!     - all permutations          [[]]     [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    €  - for each:
   Ƒ   -   is invariant under:
  Ụ    -     grade                ( []       [1,2,3] [1,3,2] [2,1,3] [3,1,2] [2,3,1] [3,2,1] )
       -   }                        [1]     [1,      1,      1,      0,      0,      1]
     S - sum                        1       4

```
> 8 votes

# Answer
# JavaScript (ES6), 25 bytes

0-indexed. Uses the recurrence relation.

```
f=n=>n<2||f(--n)+n*f(n-1)

```

Try it online!
> 7 votes

# Answer
# 05AB1E, ~~12~~ 8 bytes

*-4 bytes by porting Stephen's cQuent answer*

```
1λèsN<*+

```

Try it online!
> 4 votes

# Answer
# Haskell, 29 bytes

```
f n|n<2=1|m<-n-1=f m+m*f(n-2)

```

Try it online!

Implements the recursive formula.
> 4 votes

# Answer
# C (gcc), 40 bytes

```
long f(long n){n=n<2?1:f(--n)+n*f(n-1);}

```

Try it online!

Merely copied from @Arnauld answer
> 4 votes

# Answer
# Python 3, <sup>~~81~~ \\$\cdots\\$ ~~57~~</sup> 56 bytes

```
def f(n):
 a=b=i=1
 while i<n:a,b=a+i*b,a;i+=1
 return a

```

Try it online!

Uses 0 based indexing and implements the recursive formula.
> 3 votes

# Answer
# Perl 6, 26 bytes

```
{{(1,1,++$×*+*...*)[$_]}}

```

Try it online!
> 3 votes

# Answer
# , 25 bytes

```
($:+]*$:@<:)@<:`1:@.(<&2)

```

Try it online!

`$:` is J's recursion operator, so this is a fairly straightforward impl of the recursive def.

I tried a couple other approaches (including using `^:` power of operator) but wasn't able to get shorter than this.

Am curious if anyone can improve it...
> 2 votes

# Answer
# Red, 53 bytes

```
f: func[n][either 1 > n: n - 1[1][n *(f n - 1)+ f n]]

```

Try it online!
> 2 votes

# Answer
# PHP, 48 bytes

```
function f($n){return$n<2?1:f(--$n)+$n*f($n-1);}

```

Try it online!

Implementation of the recursive function.

**Original version: 54 bytes** (port of @Noodle9 answer):

```
for($i=$j=1;++$n<$argn;$j=$k){$k=$i;$i+=$n*$j;}echo$i;

```

Try it online!
> 2 votes

# Answer
# Mathematica ~~46~~ 42 bytes

```
f=2^(#/2)HypergeometricU[-#/2,.5,-.5]I^-#&

```

Try it online!

Thanks to mabel for helping me shave 4 bytes by using what I think is an anonymous function.

As seen in https://www.wolframalpha.com/input/?i=OEIS+A000085 and http://mathworld.wolfram.com/ConfluentHypergeometricFunctionoftheSecondKind.html
> 2 votes

# Answer
# Charcoal, 20 bytes

```
⊞υ¹ＦＮ⊞υ⁺§υι×ι§υ⊖ιＩ⊟υ

```

Try it online! Link is to verbose version of code. Uses the recurrence relation. Explanation:

```
⊞υ¹

```

`T(0)=1`

```
ＦＮ

```

Loop `n` times.

```
⊞υ⁺§υι×ι§υ⊖ι

```

`T(i+1)=T(i)+iT(i-1)`

```
Ｉ⊟υ

```

Output `T(n)`.
> 1 votes

# Answer
# Keg, 21 bytes

```
:1≤[_1|;:@Tƒ^:;@Tƒ*+]

```

Try it online!

Simply implements the formula in a recursive manner. The footer is mainly for testing purposes
> 1 votes

# Answer
# Retina 0.8.2, 80 bytes

```
.+
$*_;;_;
{`^_(_*;)(_*;_+)
$1_$2,$2
+`(,_*)_(;_+;(_*))|,
$3$1$2
^;_*;(_*).*
$.1

```

Try it online! Explanation:

```
.+
$*_;;_;

```

Initialise the work area with `n`, `i=0`, and `T=[1]` (note that the list indices are reversed, so that the first element of `T` is `T[i]` and the last is `T[0]`) converted to unary.

```
{`

```

Loop `n` times (actually until the buffer stops changing, but see below).

```
^_(_*;)(_*;_+)
$1_$2,$2

```

Decrement `n`, increment `i`, and make extra copies of `i` and `T[i]`.

```
+`

```

Repeat `i` times.

```
(,_*)_(;_+;(_*))|,
$3$1$2

```

Decrement the copy of `i` and add `T[i-1]` to the copy of `T[i]`, stopping when the copy reaches zero by deleting the `,` entirely, causing the repeat to terminate. The result is therefore `T[i+1]=T[i]+iT[i-1]`.

```
^;_*;(_*).*
$.1

```

When `n` is zero, replace the work area with `T[i]` converted to decimal. This causes the loop to terminate as the stages can no longer match.
> 1 votes

# Answer
# Japt, ~~28~~ 26 bytes

```
_pZÌ+(ZÊÉ *ZgJÑ}g´U1õ ï)gJ

```

Try it

```
pZÌ+(ZÊÉ *ZgJÑ   make sequence with next element from previous sequence

_    ...  }g´U    repeat input -1 times
  1õ ï)          starting with [[1,1]]
       gJ        implicit output last element of resulting sequence

```
> 1 votes

# Answer
# GolfScript, 16 bytes

This is inspired by the Fibonacci GolfScript program.

```
~,1.@{)*1$+\}/\;

```

Try it online!

## Explanation

```
~,               # Generate exclusive range from input to 0
  1.             # Make 2 copies of 1
    @            # Make the each target on the top
     {      }/   # Foreach over the range
      )          # Increment the current item
       *         # Multiply top by the current item
        1$+      # And add by the second-to-top
           \     # Swap items
              \; # Swap & discard the bottom item

```
> 1 votes

# Answer
# Elm, 45 bytes

```
f n = if n<2 then 1 else (n-1)*f(n-2)+f(n-1)

```

Try it online!

Implementation of the recursive function.
> 1 votes

# Answer
# k4, 53 bytes

```
{+/{*/[1+!x]*%*/[y#2]**/*/'1+(!x-2*y;!y)}[x]'!1+_x%2}

   {                                    }[x]'!1+_x%2 /pass inner lambda 2 args - x and each (') enumerate (!) 1+floor float-div 2
                             (!x-2*y;!y)             /enumerate
                           1+                        /add 1 to both list items
                        */'                          /multiply over each - this gives both denominator factorials
                      */                             /multiply them
              */[y#2]                                /make list of 2s of y-length and multiply over - gives y^2
                     *                               /multiply left and right args
             %                                       /reciprocal
    */[1+!x]                                         /x factorial
 +/                                                  /sum

```

examples:

```
  {+/{*/[1+!x]*%*/*/[y#2],*/'1+(!x-2*y;!y)}[x]'!1+_x%2}'[0 3 10 14]
1 4 9496 2390480f

```
> 1 votes

# Answer
# K (ngn/k), 27 bytes

```
{*|x{x,+/(2#|x)*1,#2_x}/!2}

```

Try it online!

* `x{...}/!2` setup a do-reduction with `x` (the input) as the number of iterations to run, seeded with `0 1` (the first two terms of the sequence)
* `1,#2_x` build list containing how to multiply the previous values (i.e. `T(n-1)` by 1, and `T(n-2)` by n-1). Note that this infers the value of `n` from the length of the sequence so far.
* `(2#|x)*` get the last two values of the reversed sequence (i.e. `(x[n-1];x[n-2])`)
* `x,+/` take their sum, and append to the sequence
* `*|` return the last value of the generated sequence
> 1 votes

# Answer
# Husk, 7 bytes

```
#S=ηÖPḣ

```

Try it online! or Verify first 10 values

Same idea as the Jelly answer, and equally as slow.

0-indexed.

## Explanation

```
#S=ηÖPḣ
      ḣ range 1..n
     P  permutations
#       number of arrays which satisfy:
 S      self
  =     equals
   η    indices of
    Ö   ordered elements?

```
> 0 votes

# Answer
# APL (Dyalog Unicode), 37 bytes

```
{⍵<2:1⋄+/(2⍵-1)×∇¨⍵-⍳2}

```

Try it online!

-1 byte from Adám.
> 0 votes

# Answer
# Stax, 7 bytes

```
öƒ◙─v◙6

```

Run and debug it
> 0 votes

# Answer
# Japt, ~~16~~ ~~12~~ 11 bytes

1-indexed

```
È+T°*ZÔÅÎ}g

```

Try it
> 0 votes

---
Tags: code-golf, sequence
---


title: How many atoms in the hydrocarbon?

text:
# Question
Title: How many atoms in the hydrocarbon?
# How many atoms in the hydrocarbon?

A hydrocarbon is a chemical compound which consists of only hydrogen and carbon atoms. For this challenge, we will only consider the three simplest kinds of hydrocarbons: **alkanes**, **alkenes**, and **alkynes** with no branches.

An **alkane** with \\$n\\$ carbon atoms contains \\$2n+2\\$ hydrogen atoms. An **alkene** with \\$n\\$ carbon atoms contains \\$2n\\$ hydrogen atoms. An **alkyne** with \\$n\\$ carbon atoms contains \\$2n-2\\$ hydrogen atoms.

Each kind of hydrocarbon is named with a prefix indicating the number of carbon atoms it contains, followed by the suffix `ane`, `ene`, or `yne` if it is an alkane, alkene, or alkyne respectively. The numerical prefixes are as follows:

```
1  <-> meth
2  <-> eth
3  <-> prop
4  <-> but
5  <-> pent
6  <-> hex
7  <-> hept
8  <-> oct
9  <-> non
10 <-> dec

```

For example, we can see `propane` has 3 carbon and 8 hydrogen atoms, and `heptyne` has 7 carbon and 12 hydrogen atoms.

## Challenge

Your task is to write a function or program that receives a string or list of characters representing the name of a hydrocarbon, and produces or outputs the number of carbon and hydrogen atoms in a molecule of that hydrocarbon.

For each of the 30 hydrocarbon names, the code must accept at least one possible capitalization of that name. For example, it is fine if your code works for `mEthane` but not `methane`, and `ETHAnE` but not `ETHANE`, and `Propane` but not `propane`. The inputs `methene` and `methyne` may give undefined output since those are not real chemicals.

The input and output can be in any convenient format. You don't need to label which number represents carbon and which represents hydrogen, just keep the order of the numbers consistent.

You may assume the input will correspond to a valid hydrocarbon, and there are at most 10 carbon atoms.

## Examples

```
Possible Input -> Possible Output
Methane        -> 1 4
propane        -> 3 8
Heptyne        -> 7 12
Decene         -> 10 20

```

## Rules

* No standard loopholes.
* Shortest code in bytes wins.

# Answer
> 15 votes
# 05AB1E,  ~~27 26~~  24 bytes

*Saved 1 byte thanks to @KevinCruijssen*
*Saved 2 bytes thanks to @Grimmy*

**Note:** This code was based on my understanding that only the capitalization of the first letter was customizable. It has since been clarified that it applies to *all* letters, leading to this significantly shorter answer by Grimmy.

Expects `mEpBPhHond` for the capitalization of the first letter.

```
ćC•>·¿*•s÷θD>,₂I3(èH÷+·,

```

Try it online!

### How?

We define the following magic constant:

$$M=1902159854$$

The number of carbon atoms is given by:

$$c=\left(\left\lfloor\frac{M}{n}\right\rfloor\bmod 10\right)+1$$

where \\$n\\$ is the first character of the input turned into an 05AB1E code point (0-9, A-Z, a-z, ...).

```
 input |  n  | floor(M/n) | mod 10
-------+-----+------------+--------
 meth- |  48 |   39628330 |   0
 Eth-  |  14 |  135868561 |   1
 prop- |  51 |   37297252 |   2
 But-  |  11 |  172923623 |   3
 Pent- |  25 |   76086394 |   4
 hex-  |  43 |   44236275 |   5
 Hept- |  17 |  111891756 |   6
 oct-  |  50 |   38043197 |   7
 non-  |  49 |   38819588 |   8
 dec-  |  39 |   48773329 |   9

```

### Commented

```
                         # example input: 'Heptyne'
ć                        # extract the first character -> 'H'
 C                       # turn it into an integer -> 17
  •>·¿*•                 # push the magic constant 1902159854
        s÷               # swap + integer division -> 1902159854 / 17 = 111891756
          θ              # keep the last digit (therefore a modulo 10) -> 6
           D>            # duplicate and increment the copy
             ,           # print the number of carbon atoms
              ₂          # push 26
               I         # push the input string
                3(è      # extract the 3rd to last character -> 'y'
                   H     # parse it as base-36 -> 34
                    ÷    # integer division -> 26 / 34 = 0
                     +   # add to the number of carbon atoms - 1 -> 6
                      ·  # double
                       , # print the number of hydrogen atoms

```

# Answer
> 6 votes
# 05AB1E, ~~16~~ ~~12~~ 11 bytes

```
.uJ4ôCx<O1ǝ

```

Try it online!

This takes full advantage of the rule that only one possible capitilization has to be handled for each input. All inputs are at least 6 letters long, so we can store 6 bits of data in the capitilization. 4 of those bits are used to store the carbon count, and the remaining 2 store half of the extra hydrogen count (0 for alkynes, 1 for alkenes, 2 for alkanes).

```
.u             # uppercase? (returns a list of 0s and 1s)
  J            # join that list to a string
   4ô          # split in chunks of 4 digits
     C         # convert each chunk from binary
      x        # double each, without popping the original list
       <       # -1 from each
        O      # sum
         1ǝ    # replace the second element of the list with this sum

```

Alternative 11:

```
.u2β3‰<.¥¦ƶ

```

Try it online!

# Answer
> 5 votes
# , ~~96~~ ~~86~~ ~~82~~ 79 bytes

```
`!`=utf8ToInt;(5-rev(K<-!scan(,""))[3]%%16)/2*0:1+match(K[1],!"mepbPhHond")*1:2

```

Try it online!

Accepts the prefixes with capitalization `mepbPhHond` in order; returns `c(Carbon, Hydrogen)`.

`yea` for this answer.

Thanks to Robin Ryder for golfing down 4 bytes.

# Answer
> 5 votes
# JavaScript (ES6), 62 bytes

Similarly to other answers, expects all names in lowercase, except `Pent-` and `Hept-`. Returns `[carbon, hydrogen]`.

```
s=>[n='epbPhHond'.search(s[0])+2,n+/a/.test(s)-/y/.test(s)<<1]

```

Try it online!

---

# JavaScript (ES6),  ~~84~~  79 bytes

A version where the capitalization doesn't matter. Returns `[carbon, hydrogen]`.

```
s=>[n=-~'519.80.76423'[parseInt(s[0]+s[2],28)%17],n+/a/.test(s)-/y/.test(s)<<1]

```

Try it online!

## How?

### Carbon

We can concatenate the first and third characters of each prefix to build a unique string identifier.

*Example:* `meth``mt`

We can convert this string ID to an integer ID in \\$\[0..11\]\\$ (still unique) by parsing it as base-28 and applying a modulo \\$17\\$ (these values were found with a brute-force search).

Because the character set of base-28 is `'0'` to `'r'`, the parsing stops if a character above `'r'` is encountered.

*Example:* `mt``m`\\$22 \bmod 17=5\\$

The results are summarized in the following table:

```
 input | key  | base 28 -> dec. | mod 17
-------+------+-----------------+--------
 meth- | 'm'  |        22       |    5
 eth-  | 'eh' |       409       |    1
 prop- | 'po' |       724       |   10
 but-  | 'b'  |        11       |   11
 pent- | 'pn' |       723       |    9
 hex-  | 'h'  |        17       |    0
 hept- | 'hp' |       501       |    8
 oct-  | 'o'  |        24       |    7
 non-  | 'nn' |       667       |    4
 dec-  | 'dc' |       376       |    2

```

### Hydrogen

Neither `'a'` nor `'y'` appears in any of the prefixes. Therefore, it is safe to test whether the suffix is `-ane` or `-yne` by looking for these letters in the entire input string.

The following expression:

```
/a/.test(s) - /y/.test(s)

```

evaluates to either \\$-1\\$ for `-yne`, \\$0\\$ for `-ene` or \\$1\\$ for `-ane`.

Given the number \\$n\\$ of carbon atoms, the number of hydrogen atoms is:

```
(n + /a/.test(s) - /y/.test(s)) << 1

```

(and because `<<` has a higher precedence than `+` and `-`, the parentheses can be omitted)

# Answer
> 4 votes
# Pyth, 33 31 bytes

```
Kx"mepbPhHond"hQhKy+K/%CePPQ7 3

```

Try it online!

Uses, as you can see, `mepbPhHond` capitalization. Probably can be golfed much further. Returns carbon, hydrogen on newlines

## How it works

```
Kx"mepbPhHond"hQhKy+K/%CePPQ7 3

 x            hQ    - The index of the first letter of the input
  "mepbPhHond"      - in "mepnPhHond"
K               hK  - Assign to K... and then print K+1

                       CePPQ       - The codepoint of the third last character
                                       in the input (Q[:-1][:-1][-1])
                      /%     7 3    - Modulo 7 divided by 3 (ane, ene, yne -> 2, 1, 0)
                   +K               - ... plus K
                  y                 - ... times 2, and print implicitly

```

# Answer
> 3 votes
# Python 3.8, 60 bytes

As other answers, all the names except for those starting with `Prop-` or `Hept-`, must be lowercase.

```
lambda x:(c:=' mePbphHond'.find(x[0]),c+'ea'.find(x[-3])<<1)

```

-4 bytes thanks to @Arnauld

Try it online!

---

### Fun fact:

Another interesting fact I observerd is the following one:

* \\$ord(a)=97\to9-7=2\\$ which is the number we have to add for alk**a**nes.
* \\$ord(e)=101\to1-0-1=0\\$ which is the number we have to add for alk**e**nes.
* \\$ord(y)=121\to1-2-1=-2\\$ which is the number we have to add for alk**y**nes.

I don't think that I can modify my answer using this way to be less bytes thank it is right now, but I thought it was worth mentioning and maybe another answer can use it effectively!

An implementation of the above idea is the following one:

```
lambda x:(c:=' mePbphHond'.find(x[0]),2*c+reduce(lambda i,j:i-j,map(int,str(ord(x[-3])))))
from functools import reduce

```

which obviously is much more bytes (119).

# Answer
> 2 votes
# Python 2, 66 bytes

```
def f(s):n='mePbpHhond'.find(s[0]);return-~n,2*(n+ord(s[-3])%50%3)

```

Try it online!

Over thinking it a bit. Accepts only lower case, except for 'Prop' and 'Hept' (which must be capitalized). Returns (carbon, hydrogen).

# Python 2, ~~84~~ 82 bytes

```
def f(s):n=int('8702563914'[hash(s[:-3])%876%10]);return n+1,2*(n+ord(s[-3])%50%3)

```

Try it online!

Only accepts lower case.

# Answer
> 2 votes
# Ruby, ~~74~~ 67 bytes

```
->s{z="  etthroutenexepctonec".index s[1,2];[z/2,z-2*(s[-3]<=>?e)]}

```

Try it online!

Thanks @Value Ink for ~~golfing it for me. :-)~~ -7 bytes

# Answer
> 2 votes
# Wolfram Language (Mathematica), ~~26~~ 25 bytes

```
Tally@*AtomList@*Molecule

```

Thanks to att for the byte reduction.

# Answer
> 1 votes
# Python 3, 83 bytes

```
x=input();n=list('_mepbPhHond').index(x[0]);print(n,2*n+{'a':2,'e':0,'y':-2}[x[-3]])

```

Try it online!

-51 bytes thanks to 79037662

# Answer
> 1 votes
# Charcoal, 39 bytes

```
≔⊘⁺³⌕”↶↓>AkQN!{a⁶⟧”…θ⁻Ｌθ⁵ηＩ⟦η⊗⁻⁺η№θa№θy

```

Try it online! Link is to verbose version of code. Takes input in lower case and outputs carbon and hydrogen atoms on separate lines. Explanation:

```
…θ⁻Ｌθ⁵

```

Remove the last 5 characters of the input.

```
⌕”↶↓>AkQN!{a⁶⟧”...

```

Search for the resulting prefix within the compressed string `e prb peh heo n d`. Note that there's a space before the `e`, so that the the prefixes are found at positions `-1` for me(th?ne), `1` for e(th?ne), `3` for pr(op?ne) etc.

```
≔⊘⁺³...η

```

Add 3 to the position, then halve and store the resulting number of carbon atoms.

```
Ｉ⟦η

```

Output the carbon atoms...

```
⊗⁻⁺η№θa№θy

```

... and adjust for whether there is an `a` or `y` in the input, before doubling to give the number of hydrogen atoms.

# Answer
> 1 votes
# C# (Visual C# Interactive Compiler), 65 bytes

```
x=>(l=" mepbPhHond".IndexOf(x[0]),~-l+x[x.Count-3]%7/3<<1);int l;

```

Try it online!

# Answer
> 1 votes
# GolfScript, 32 30 bytes

Thanks to this user for pointing out that I forgot to account for -ane, -ene, -yne

```
.0="mepbPhHond"?).@-3=7%3/(+2*

```

Try it online!

This uses the same concept as in this answer

Explanation:

```
.0=                                 Make a copy of input and select first letter
   "mepbPhHond"?)                   Find index of letter and increase by one for number of carbons
                 .@                 Duplicate for number of hydrogens and bring input to top of stack
                   -3=              Get the a, e, or y in ane, ene, yne
                      7%3/          Ascii value mod 7 integer divide 3
                          (+        Decrement and add to number of carbons
                            2*      Double

```

Uses `mepbPhHond` capitalization.

Example Execution: Input: propene

```
.0=                                 Stack: 'propene' 'p'
   "mepbPhHond"?)                   Stack: 'propene' 3
                 .@                 Stack: 3 3 'propene'
                   -3=              Stack: 3 3 'e'
                      7%3/          Stack: 3 3 1
                          (+        Stack: 3 3
                            2*      Stack: 3 6

```

---
Tags: code-golf, chemistry
---