title: Detect Mongolian vowel harmony

text:
# Question
Title: Detect Mongolian vowel harmony
The Mongolian language has "vowel harmony". In short the vowel harmony means that certain vowels are not allowed to be placed next to each other in a word. This means that suffixes of words have to care about the vowels present in the words they attach to and need to resolve to a vowel that matches the harmony of the word.

## Vowels

Mongolian harmony compares about 3 binary properties that vowels can have.

* A vowel can be **round**
* A vowel can be **high**
* A vowel can be **ATR** (advanced tongue root)

If a vowel has a property, we indicate that with a `+` and square brackets if it does not we indicate that with a `-` and square brackets. e.g. **\[-ATR\]** indicates that the vowel does not have the **ATR** property.

There are thus 8 combinations of these properties that can be made. Mongolian has exactly 1 vowel for each combination except **\[+high\]\[-ATR\]\[-round\]** which is missing a vowel.

The 7 vowels and their values can be given in the table below:

|  |  | \[+ATR\] | \[-ATR\] |
| --- | --- | --- | --- |
| **\[+round\]** | **\[+high\]** | `u` (u) | `U` (ʊ) |
| **\[+round\]** | **\[-high\]** | `o` (o) | `O` (ɔ) |
| **\[-round\]** | **\[+high\]** | `i` (i) | *(Absent)* |
| **\[-round\]** | **\[-high\]** | `e` (e) | `a` (a) |

This table gives both the XSAMPA (code block) and IPA (parentheses) values for each vowel, but we will care about the XSAMPA values for this challenge.

## Harmony

### \[ATR\] harmony

Every word in Mongolian is either **\[+ATR\]** or **\[-ATR\]** with only vowels of the corresponding **\[ATR\]** value appearing in that word. The once exception is `i` which is "transparent" for **\[ATR\]** harmony. Meaning it acts as if it is in *both* categories even though it is **\[+ATR\]**. Meaning that `i` can appear in words with any vowels.

This can be illustrated with the following Venn diagram:

Modified with permission from Mongolian vowel harmony Venn diagram by wikimedia commons user AquitaneHungerForce. Liscensed under the Creative Commons Attribution-Share Alike 4.0 International license. See link for full attribution.

### \[round\] harmony

Mongolian also has **\[round\]** harmony which only affects **\[-high\]** vowels. At its simplest under **\[round\]** harmony if a **\[-high\]** vowel is the next vowel after a **\[-high\]** vowel, it must have the same **\[round\]** value.

`i` is also transparent for roundness harmony so we skip over `i` when looking for the last vowel.

## Task

Given a sequence of Mongolian vowels determine if they follow the rules of vowel harmony. Input can be either a list of XSAMPA vowels, or a string of XSAMPA vowels. Input will always be non-empty.

You should output one of two distinct values, the first if it is a valid sequence the second if it is not.

This is so your goal is to minimize the size of your source code as measured in bytes.

## Test cases

### Valid

```
iiiiiii
oi
Oi
ui
Ui
ei
ai
UO
oiou
uie
ouie
OUia

```

### Invalid

```
uU
oO
eia
oiie
OUie
eieio

```

# Reading

This post is based off of the description from:

* Godfrey, Ross (2012). "Opaque Intervention in Khalkha Mongolian Vowel Harmony: A Contrastive Account" pdf.

# Answer
# JavaScript (Node.js), 45 bytes

*Saved 1 byte thanks to @dingledooper*

Expects a string. Returns *false* for valid or *true* for invalid.

```
s=>Buffer(s).some(n=>n%7&&s*((s^(s=n))%18%8))

```

Try it online!

### How?

In this version, we work directly on the ASCII codes of the characters:

```
 char |  O  |  U  |  a  |  e  |  i  |  o  |  u
------+-----+-----+-----+-----+-----+-----+-----
 code |  79 |  85 |  97 | 101 | 105 | 111 | 117

```

Conveniently, `i` is the only character whose ASCII code is congruent to \\$0\\$ modulo \\$7\\$.

Once the `i`'s have been filtered out using the above property, a pair of consecutive ASCII codes \\$(x,y)\\$ is valid if and only if:

$$\big((x\operatorname{XOR}y)\bmod 18\big)\bmod 8 = 0$$

Below is a summary of all possible outcomes (using the same order as in my first version for easier comparison):

```
   | e u O o U a
---+-------------
 e | 0 0 6 2 4 4
 u | 0 0 4 0 6 2
 O | 6 4 0 6 0 2
 o | 2 0 6 0 4 6
 U | 4 6 0 4 0 0
 a | 4 2 2 6 0 0

```

---

# JavaScript (ES6), 54 bytes

Expects an array of characters. Returns *false* for valid or *true* for invalid.

```
a=>a.some(c=>(n="ieuOoUa".search(c))&&a*((a^(a=n))%3))

```

Try it online!

### How?

We map `"ieuOoUa"` to \\$\[0,1,2,3,4,5,6\]\\$.

We ignore the `i`'s and consider each pair of indices \\$(x,y)\\$ for the remaining consecutive characters.

The pair is valid if and only if:

$$(x\operatorname{XOR}y)\bmod 3=0$$

Below is a summary of all possible outcomes:

```
   | e u O o U a
---+-------------
 e | 0 0 2 2 1 1
 u | 0 0 1 0 1 1
 O | 2 1 0 1 0 2
 o | 2 0 1 0 1 2
 U | 1 1 0 1 0 0
 a | 1 1 2 2 0 0

```
> 9 votes

# Answer
# Jelly, 19 bytes

```
ḟ”iOµPƝ+⁽D§ẒẸ^+4ẒEƊ

```

A monadic Link that accepts a list of characters and yields `1` if valid and `0` otherwise.

**Try it online!** Or see the test-suite.

### How?

Removes the `i`s and then takes the exclusive-or of these two checks using the remaining character's ordinal values:

1. (`PƝ+⁽D§ẒẸ`) whether any neighbouring pair are from the same **\[ATR\]**, both **\[-high\]**, but with different **\[round\]** values. That is `oe`, `eo`, `Oa`, or `aO`.
2. (`+4ẒE`) whether all are from the same **\[ATR\]**

```
ḟ”iOµPƝ+⁽D§ẒẸ^+4ẒEƊ - Link: list of characters, S (from 'aeoiuOU')
 ”i                 - an 'i' character
ḟ                   - S filter-discard 'i's
   O                - ordinal values
    µ               - start a new monadic chain, call that V
      Ɲ             - for neighbours in V:
     P              -   product
        ⁽D§         - 18226
       +            - add (vectorises)
           Ẓ        - is prime? -> 1 if the neighbours are oe, eo, Oa, or aO
                                     else 0
            Ẹ       - any? -> X1
                  Ɗ - last three links as a monad - f(V):
               4    -   four
              +     -   V add 4 (vectorises)
                Ẓ   -   is prime?
                 E  -   all equal? -> X2
             ^      - X1 XOR X2

```

That is:

1. Identifying those neighbours with the same **\[ATR\]** where both are **\[-high\]** but with different **\[round\]** values makes use of this table of ordinal products plus \\$18226\\$ with primes in bold:

| x×y+18226 | u | e | o | U | a | O |
| --- | --- | --- | --- | --- | --- | --- |
| **u** | 31915 | 30043 | 31213 | 28171 | 29575 | 27469 |
| **e** | 30043 | 28427 | **29437** | 26811 | 28023 | 26205 |
| **o** | 31213 | **29437** | 30547 | 27661 | 28993 | 26995 |
| **U** | 28171 | 26811 | 27661 | 25451 | 26471 | 24941 |
| **a** | 29575 | 28023 | 28993 | 26471 | 27635 | **25889** |
| **O** | 27469 | 26205 | 26995 | 24941 | **25889** | 24467 |

2. **\[ATR\]** groups identified by whether four more than the ordinal is a prime:

|  | ordinal+4 | prime? |
| --- | --- | --- |
| u | 121 | no |
| e | 105 | no |
| o | 115 | no |
| U | 89 | yes |
| a | 101 | yes |
| O | 83 | yes |
> 4 votes

# Answer
# Retina, 32 bytes

```
A`[oue]i*[OUa]|oi*e|Oi*a
2}V`
.+

```

Try it online! or Verify all test cases

### Explanation

```
A`[oue]i*[OUa]|oi*e|Oi*a
2}V`

```

Do the following twice:

* `A`ntiGrep -- Remove lines containing a match for the regex `[oue]i*[OUa]|oi*e|Oi*a`
* Re`V`erse the input string

If the input contains any of the invalid combinations, this process will result in an empty string.

```
.+

```

Count matches of the regex `.+`. Outputs 1 if the line is non-empty, 0 otherwise.
> 3 votes

# Answer
# Vyxal, 15 bytes

Returns `0` for valid or `1` for invalid.

```
\ioC¨pλ꘍∑8%7%;a

```

Try it Online!

This currently fails for the case `iiiiiii` due to a bug, but it should work after that gets fixed.

## How?

Ignoring `i`s, the digit sum of the xor of pairwise codepoints is good if it's one of `0`, `7`, or `8`.

```
   O  U  a  e  o  u
O  0  8 10  6  5 13
U  8  0  7 12 13  5
a 10  7  0  4  5  2
e  6 12  4  0  1  7
o  5 13  5  1  0  8
u 13  5  2  7  8  0

```

```
\ioC¨pλ꘍∑8%7%;a
\i              # literal i
  o             # remove is
   C            # to codepoints
    ¨pλ      ;  # pairwise map
       ꘍        # xor
        ∑       # digit sum
         %8     # mod 8
           %7   # mod 7
              a # are any truthy?

```
> 3 votes

# Answer
# Python, 239 bytes

```
def f(x):
 x=x.replace('i','')
 if not x:return 1
 a='ueoi';b='UaOi';m='oOea';v='oO'
 for c in x:
  if(x[0] in a)^(c in a):return-1
 r=2
 for c in x:
  if r!=2:
   if(c in m)&r^(c in v):return-1
   else:r=2
  elif c in m:r=c in v
 return 1
```

Attempt This Online!

A very boring solution, using the most obvious application of the rules.
> 2 votes

# Answer
# Python3, 177 bytes:

```
lambda s:(S:=set)()in[S(T:=s.replace('i',''))-S('uoe'),S(T)-S('UOa')]and all(T[i:i+2]in'oo,oO,Oo,OO,ee,ea,ae,aa'.split(',')for i in range(len(T)-1)if S()==S(T[i:i+2])-S('oOea'))

```

Try it online!
> 1 votes

# Answer
# Python, ~~98~~ ~~97~~ 96 bytes

```
lambda s:len(t:=s.replace("i",""))>1and(y:=ord(t[0]))and any((y^(y:=ord(x)))%18%8for x in t[1:])
```

Attempt This Online!

Port of @Arnauld's Node.js answer.
-1 byte from @Arnauld altering their answer
-1 byte thanks to @mathjunkie

---

# Python, ~~116~~ 115 bytes

```
lambda s:4in[len({*s}|{*g})for g in["ueoi","UaOi"]]and not any(t in s.replace("i","")for t in["eo","oe","aO","Oa"])
```

Attempt This Online!

Checks if the set of the characters in the string matches the two valid options (from the Venn diagram) and that none of the illegal combinations (`"eo","oe","aO","Oa"`) are in the `"i"`-stripped string.

-1 byte thanks to @mathjunkie
> 1 votes

# Answer
# Jelly, 15 bytes

```
ḟ”iṢƝ“E“¬(’ḥⱮḂẸ

```

A monadic Link that accepts a list of characters from `aeiouOU` and yields `0` if valid and `1` otherwise.

**Try it online!**

### How?

Beats my other one, but I kind of prefer that one :)

```
ḟ”iṢƝ“E“¬(’ḥⱮḂẸ - Link: list of characters, S
 ”i             - an 'i' character
ḟ               - S filter-discard 'i's
    Ɲ           - for each neighbouring pair:
   Ṣ            -   sort
            Ɱ   - for each sorted pair of neighbours:
           ḥ    -   hash using [salt, domain]:
     “E“¬(’     -     list of base 250 integers [70, 2041]
             Ḃ  - modulo two
              Ẹ - any?

```
> 1 votes

# Answer
# Charcoal, 28 bytes

```
≔⁺c⁻Ｓiθ›№⁺⌊θ⌈θc⊙⪪oeOa²№⁺⮌θθι

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` if the input is harmonic, nothing if not. Explanation:

```
≔⁺c⁻Ｓiθ

```

Remove `i`s from the input, but also prefix a `c`.

```
›№⁺⌊θ⌈θc...

```

Check that `c` is now either the minimum or maximum of the string, and...

```
⊙⪪oeOa²№⁺⮌θθι

```

... that neither the string nor its reversal contain either `oe` or `Oa`.
> 1 votes

# Answer
# , 83 bytes

```
\(x,g=\(p)grepl(p,x,perl=TRUE))!(g('[ueo]')&g('[UaO]'))&!(g('oi*e|ei*o|Oi*a|ai*O'))
```

Attempt This Online!

Very straightforward regular expression solution - can't have both sets of vowels, can't have o/e or O/a adjacent with any number of intervening is. (The other combinations are ruled out by \[ATR\] harmony.)
> 1 votes

# Answer
# Retina 0.8.2, 38 bytes

```
i

1`[oue][OUa]|[OUa][oue]|oe|eo|Oa|aO

```

Try it online! Link includes test cases. Outputs `0` for harmonic, `1` if not. Explanation: Retina 0.8.2 doesn't have any handy reversal operations so I have to test for all six non-harmonic vowel combinations.
> 0 votes

# Answer
# 05AB1E, 12 bytes

```
'iKÇü^18%8ÖP

```

Port of *@Arnauld*'s first JavaScript answer.
I tried to find a -1 byte alternative for the `18%8Ö` using any of 05AB1E's single-byte builtins and constants, but was unable to.

Try it online or verify all test cases.

**Explanation:**

```
'iK          '# Remove all "i" from the (implicit) input-string
   Ç          # Convert the string to a list of codepoint-integers
    ü         # For each overlapping pair:
     ^        #  Bitwise-XOR them together
      18%     # Modulo-18 each integer
         8Ö   # Check for each integer whether it's divisible by 8
            P # Check if all are truthy by taking the product of the list
              # (after which the result is output implicitly)

```
> 0 votes

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


title: Permutations summing to permutations

text:
# Question
Title: Permutations summing to permutations
Given an integer \\$N\\$ consider a permutation \\$p=p\_1,p\_2,p\_3,\ldots\\$ of \\$1,\ldots,N-1\\$. Let \\$P = p\_1 , p\_1+p\_2 \bmod N, p\_1+p\_2+p\_3 \bmod N, \ldots\\$ be its prefix sums modulo \\$N\\$. Sometimes \\$P\\$ will be a permutation of \\$1,\ldots,N-1\\$ itself.

For example, \\$N=4: p=3,2,1 \rightarrow P=3,1,2\\$

Negative examples: \\$p=2,3,1 \rightarrow P=2,1,2\\$ is not a permutation ; \\$p=3,1,2 \rightarrow P=3,0,2\\$ is a permutation but not of \\$1,\ldots,3\\$

Your task is to write a program or function that takes \\$N\\$ and returns the number of permutations \\$p\\$ of \\$1,\ldots,N-1\\$ such that \\$P\\$ is also a permutation of \\$1,\ldots,N-1\\$.

Rules:

You may return integers or integer-valued numbers.

You may return the \\$N\\$-th term, the first \\$N\\$ terms or the entire series.

You may ignore/skip odd \\$N\\$. If you choose to do so you may take \\$N\\$ or \\$N/2\\$ as the input.

Other than that default rules and loopholes for integer sequences apply.

This is code-golf, so shortest code in bytes wins. Different languages compete independently.

First few terms:

\\$ \begin{align} 2 &\rightarrow 1 \\ 4 &\rightarrow 2 \\ 6 &\rightarrow 4 \\ 8 &\rightarrow 24 \\ 10 &\rightarrow 288 \end{align}\\$

OEIS has more.

# Answer
# Wolfram Language (Mathematica), 60 bytes

```
Count[Sort/@Mod[Accumulate/@Permutations[r=Range@#-1],#],r]&

```

Try it online!
> 4 votes

# Answer
# , 24 bytes

```
1#.!(=&#[:=#|+/\)@A.&i.]

```

Try it online!

Straightforward brute force.
> 4 votes

# Answer
# Vyxal, 11 bytes

```
ɽ:Ṗv¦⁰%vs^O

```

Try it Online!

## How?

```
ɽ:Ṗv¦⁰%vs^O
ɽ           # exclusive range from 0; range(1, N)
 :          # duplicate top of stack
  Ṗ         # get permutations
   v¦       # vectorized cumulative sum
     ⁰      # push N to top of stack
      %     # modulo (vectorizes)
       vs   # vectorized sort
         ^  # flip stack (so range(1, N) is now on top)
          O # count number of instances

```
> 4 votes

# Answer
# JavaScript (ES7), 88 bytes

```
f=(n,m=z=2**n-2,p=o=0,x,g=i=>(q=1<<++i)>m?o+=x==z:g(i,m&q&&f(n,m^q,i+=p,x|1<<i%n)))=>g``

```

Try it online!

### How?

We compute the bitmask \\$z=2^n-2\\$ where the bits \\$1\\$ to \\$n-1\\$ are set (e.g. \\$n=4\\$ gives \\$z=14=1110\_2\\$).

We start with \\$m=z\\$ and \\$x=0\\$. We recursively clear the bits of \\$m\\$ in all possible orders while keeping track of the sum of said bit indices in \\$p\\$ and setting the bits \\$p \bmod n\\$ in \\$x\\$. (Note that we do not need to keep track of the permutation itself.)

We have a solution whenever we end up with \\$x=z\\$, in which case the output value \\$o\\$ is incremented.
> 3 votes

# Answer
# Husk, 13 bytes

```
S#omȯOm%¹∫Ptŀ

```

Try it online!

```
           t   # tail: all except the first element of
            ŀ  # the sequence 0..N-1;
S#o            # now, how many times does this occur among
          P    #  get all permutations of this
   mȯ          #  and for each of them
         ∫     #   get the cumulative sums
      m%¹      #   each modulo the input
     O         #   and sort the results

```

---

**Alternative, also 13 bytes**

```
LSnm(†%¹∫)Pḣ←

```

Try it online!

```
            ←  # decrement the input by 1
           ḣ   # get the sequence 1..N
          P    # and get all permutations of this;
 Sn            # now get all common elements between this and
   m(    )     #  for each permutation
        ∫      #   get the cumulative sums
     †%¹       #   each modulo the input
L              # how long is the resulting list of common elements?

```
> 3 votes

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

```
{+/~^a?x!+\'a:?>'+!x#x}

```

Try it online!

`+!x#x` All length x combinations of `0 1 ... x-1`.
`a:?>'` The unique results of grading up each combination. This gives all permutation, assign these to `a:`.
`x!+\'` Cumulative sum of each permutation, modulo x.
`a?` Find each row in the result in the list of permutations. This gives nulls for non-permutations.
`+/~^` Count the non-null values.
> 3 votes

# Answer
# Jelly, 9 bytes

```
’Œ!ðÄ%f⁸L

```

A monadic Link that accepts an integer and yields the count of permutations summing to permutations.

**Try it online!**

### How?

```
’Œ!ðÄ%f⁸L - Link: integer, N
’         - decrement -> N-1
 Œ!       - all permutations of [1..N-1]
   ð      - start a new dyadic chain, f(permutations, N)
    Ä     - cumulative sums (of each of the permutations)
     %    - modulo N
      f⁸  - filter keep if in (the permutations)
        L - length

```
> 2 votes

# Answer
# Factor \+ `math.combinatorics math.unicode`, 71 bytes

```
[| n | n [1,b) <permutations> [ dup cum-sum [ n mod ] map ⊂ ] count ]

```

Try it online!

* `n [1,b) <permutations>` Get all the permutations of \[1..n) as a virtual sequence.
* `[ ... ] count` Count how many of them...
* `dup cum-sum [ n mod ] map ⊂` ...are supersets of their cumulative sum modulo n.
> 2 votes

# Answer
# Burlesque, 30 bytes

```
J-.ror@Jbcjm{q++pa}x/.%q~[Z]++

```

Try it online!

```
J      # Dup
-.     # Decrement
ro     # Range 1..N-1
r@     # Permutations
J      # Dup
bc     # Infinite cycle
j      # Swap
m{     # Map
 q++   # Sum
 pa    # Partial
}
x/     # Reorder stack
.%     # Modulo
q~[Z]  # Zip with contained in permutations
++     # Sum (count)

```
> 2 votes

# Answer
# 05AB1E, 13 bytes

```
L¨œεηOI%{āQ}O

```

Try it online or verify all test cases.

**Explanation:**

```
L           # Push a list in the range [1, (implicit) input]
 ¨          # Remove the last item to make the range [1,input)
  œ         # Get all its permutations
   ʒ        # Filter the permutations by:
    η       #  Get all prefixes of the current permutation
     O      #  Sum each prefix
      I%    #  Modulo the input
        {   #  Sort it
         ā  #  Push a list in the range [1,length] (without popping)
          Q #  Check if both lists are the same
   }g       # After the filter: pop and push the length
            # (which is output implicitly as result)

```
> 2 votes

# Answer
# Python, 116 bytes

```
from itertools import*
f=lambda n:(r:=set(range(1,n)))and sum({sum(x[:i])%n for i in r}==r for x in permutations(r))
```

Attempt This Online!
> 2 votes

# Answer
# Haskell, 102 bytes

```
import Data.List
f n=length$filter((`elem`p).tail.map(`mod`n).scanl(+)0)p where p=permutations[1..n-1]
```

Attempt This Online!
> 1 votes

---
Tags: code-golf, permutations
---


title: Tell me how many there are, in Polish

text:
# Question
Title: Tell me how many there are, in Polish
Today, you're going to be writing Polish. No, not Polish notation—*Polish*, the actual language spoken in Poland.

Given a number and a noun, output a Polish sentence telling me that there are that many of that thing, using the appropriate template below.

The input consists of an integer in the range from 0 to 200, and a string of 1 to 10 lowercase ASCII letters (the "input noun"). You may accept these inputs in any reasonable format.

The output must consist of one of the below output templates, where the number in the template (if any) has been replaced with the input integer, and the word `kot` in the template has been replaced with the input noun.

## Output templates

If the input number is 0, then use the output template

```
Nie ma żadnych kotów.

```

If the input number is 1, then use the output template

```
Jest 1 kot.

```

If the input number ends with 2, 3, or 4, but does **not** end with 12, 13, or 14, then use the output template

```
Są 4 koty.

```

In any other case, use the output template

```
Jest 8 kotów.

```

Note that the special characters used in these templates are:

* ż (in "żadnych") – U+017C Latin small letter Z with dot above (ż)
* ó (in the suffix "-ów") – U+00F3 Latin small letter O with acute (ó)
* ą (in "Są") – U+0105 Latin small letter A with ogonek (ą)

You may output these characters in any reasonably common character encoding (including HTML entities), and you may use combining characters instead of precomposed characters (or even a mixture of the two).

Note that in ISO-8859-2, all ASCII characters as well as the three special characters above are represented with one byte. Therefore, if your program uses no non-ASCII characters besides these three, then you can count each of these three characters as one byte.

## Test cases

```
0 pomidor -> Nie ma żadnych pomidorów.
1 kwiat -> Jest 1 kwiat.
2 dom -> Są 2 domy.
5 wilk -> Jest 5 wilków.
13 komputer -> Jest 13 komputerów.
24 but -> Są 24 buty.
101 kurczak -> Jest 101 kurczaków.
104 wieloryb -> Są 104 wieloryby.
112 post -> Jest 112 postów.
122 balon -> Są 122 balony.

```

## Do plurals in Polish really work that way?

No, plurals in Polish are actually a lot more complicated than this.

This is , so the shortest program in each language wins.

# Answer
> 10 votes
# Retina 0.8.2, 88 bytes

```
.+
Jest $&ów.
Jest 0
Nie ma żadnych
( 1 .+)...
$1.
Jest (.*(?<!1)[2-4] .+)...
Są $1y.

```

Try it online! Link includes test cases. Explanation:

```
.+
Jest $&ów.

```

Assume none of the special cases apply.

```
Jest 0
Nie ma żadnych

```

Fix up if the input was `0`.

```
( 1 .+)...
$1.

```

Fix up if the input was `1`.

```
Jest (.*(?<!1)[2-4] .+)...
Są $1y.

```

Fix up for the `2-4` but not `12-14` endings.

# Answer
> 7 votes
# 05AB1E, ~~105~~ ~~92~~ 89 bytes

*-16 thanks to Kevin Cruijssen.*

```
„ówU’Jî• ’V>iXIŽ1}ç’NíÓ íà ÿ‹¤½Áh ’rJë¹iY…ÿ1 ìë¹Ƶ…S©Å¿O¹®T+Å¿O_*i¹Ƶ¡ç"Sÿ ÿ ÿy"ëY¹ðIXJ]'.J

```

Try it online! Takes input separated by a newline.

# Answer
> 4 votes
# Factor, 160 bytes

```
[| n s | n s t n 0 = n 1 = n present R/ .*(?<!1)[234]/ matches? 3array index ?1+
{ "Jest %d %sów.""Nie ma żadnych %sów.""Jest %d %s.""Są %d %sy."} nth sprintf ]

```

Attempt This Online!

### How?

```
                   ! n = 122, s = "balon"
n                  ! 122
s                  ! 122 "balon"
t                  ! 122 "balon" t
n                  ! 122 "balon" t 122
0                  ! 122 "balon" t 122 0
=                  ! 122 "balon" t f
n                  ! 122 "balon" t f 122
1                  ! 122 "balon" t f 122 1
=                  ! 122 "balon" t f f
n                  ! 122 "balon" t f f 122
present            ! 122 "balon" t f f "122"
R/ .*(?<!1)[234]/  ! 122 "balon" t f f "122" R/ .*(?<!1)[234]/
matches?           ! 122 "balon" t f f t
3array             ! 122 "balon" t { f f t }
index              ! 122 "balon" 2
?1+                ! 122 "balon" 3
{ ... }            ! 122 "balon" 3 { ... }
nth                ! 122 "balon" "Są %d %sy."
sprintf            ! "Są 122 balony."

```

# Answer
> 4 votes
# Python 3, ~~109~~ 106 bytes

```
lambda n,s:[['Nie ma żadnych ','Jest %s '%n][n>0]+s+'ów'*(n!=1),f'Są {n} {s}y'][n//10%10!=1<n%10<5]+'.'

```

Try it online!

# Answer
> 3 votes
# Perl 5 \+ `-pl056`, 79 bytes in ISO-8859-2

```
/ /;$_=/(?<!1)[234] /?"Są ${_}y":$`?"Jest $_"."ów"x($`>1):"Nie ma żadnych $'ów"

```

Try it online!

## Explanation

Match space with `/ /` which stores the number in prematch (`$`` ) and the noun in postmatch (`$'`). Next `$_` (which is automatically output, thanks to `-p`) is set to `"Są ${_}y"` (where `$_` is the implicit input from the implicit `-n` via `-p`) if it matches the regex `/(?<!1)[234] /` (number ends `[234]` but not `1[234]`), otherwise if `$``  is not `0` it's set to `"Jest $_"."ów"x($`\>1)`, where the` "ów"`suffix is added if`$'`is greater than`1`, otherwise, finally for the` 0`case it's set to`"Nie ma żadnych $'ów"\`.

Thanks to @Xcali for saving 9 bytes!

# Answer
> 2 votes
# Python, ~~138~~ ~~123~~ 111 bytes

```
lambda n,s:("Nie ma żadnych ",("Jest","Są")[(z:=n//10%10!=1<n%10<5)]+f' {n} ')[n>0]+s+(n!=1)*"óyw"[z::2]+'.'

```

Attempt This Online!

# Answer
> 2 votes
# JavaScript (ES6), 113 bytes*

** counting each special letter as 1 byte, as allowed by the challenge*

Expects `(integer)(word)`.

```
n=>w=>[`Jest`,`Są`,`Nie ma żadnych`][i=n<2?n+2:28>>n%10&n*9%98%9!=1,i%3]+` ${n?n+' '+w:w}${[[,'y','ów'][i||2]]}.`

```

Try it online!

### How?

To test whether \\$n\\$ ends with \\$2\\$, \\$3\\$ or \\$4\\$ and does not end with \\$12\\$, \\$13\\$ or \\$14\\$, we use the expression:

```
28>>n%10&n*9%98%9!=1   // 20 bytes

```

Explanation:

```
28                     // the bitmask 0b0000011100
>> n % 10              // right-shifted by n mod 10
&                      //
n * 9 % 98 % 9 != 1    // this is false for 12, 13, 14, 112, 113, 114
                       // and true for other values ending with 2, 3, 4
                       // (for anything else, it doesn't matter)

```

This is somewhat convoluted but shorter than using a test with a regular expression (which would also require ES9+ for the negative lookbehind assertion):

```
/(?<!1)[234]$/.test(n) // 22 bytes

```

Try it online!

# Answer
> 2 votes
# Charcoal, 73 bytes

```
≡θ0«Nie ma żadnych ηów»¿›№234§θ±¹⁼1§θ±²«Są θ ηy»«Jest θ η¿⁻1θów».

```

Try it online! Link is to verbose version of code. Explanation:

```
≡θ0«Nie ma żadnych ηów»

```

If the first input (`θ`) is `0`, then print `Nie ma żadnych ηów`, where `η` is the second input.

```
¿›№234§θ±¹⁼1§θ±²«Są θ ηy»

```

If it ends in `2`, `3` or `4` but not `12`, `13` or `14`, then print `Są θ ηy`.

```
«Jest θ η¿⁻1θów»

```

Otherwise print `Jest θ η`, and then print `ów` if the first input is not `1`.

```
.

```

Print the final `.`.

Note that the deverbosifier thinks that `ó` doesn't need to be encoded but it actually takes three bytes to encode. (It calculates the byte count correctly for ż and ą.)

# Answer
> 2 votes
# Vyxal, 74 bytes

```
`J½Ḣ Π Π.`¹ċ[Ṫ£234¹tc¹Ṫtċ∧[⁺żC`SΠ Π Πy.`|⁺ċC¹[¥`ΠΠw.`|⁰`Nie ma \ż…ṅƒ꘍ ΠΠw.

```

Try it Online!

## How?

```
`J½Ḣ Π Π.`¹ċ[Ṫ£234¹tc¹Ṫtċ∧[⁺żC`SΠ Π Πy.`|⁺ċC¹[¥`ΠΠw.`|⁰`Nie ma \ż…ṅƒ꘍ ΠΠw.
`J½Ḣ Π Π.`                   # Push string "Jest {implicit first input} {implicit second input}."
          ¹ċ                 # Is the first input not one?
            [                #  If so:
             Ṫ               #   Remove the last character (the period) from the string
              £              #   Pop and put it in the register.
               234¹tc        #    Is the last digit of the first input one of 2, 3, 4?...
                     ¹Ṫtċ∧   #    ...and is the second last digit of the first input not one?
[                            #     If so:
 ⁺żC                         #      Push "ą"
    `SΠ Π Πy.`               #      Push string "S{'ą'} {implicit first input} {implicit second input}y." (which is implicitly output)
              |              #     Otherwise:
               ⁺ċC           #      Push "ó"
                  ¹          #      Is the first input truthy? (not zero)
                   [         #       If so:
                    ¥`ΠΠw.`  #        Push string "{register}{'ó'}w." (which is implicitly output)
|                            #       Otherwise (the input is zero):
 ⁰`Nie ma \ż…ṅƒ꘍ ΠΠw.        #         Push string "Nie ma żadnych {second input}{'ó'}w." (which is implicitly output)
                             # All strings and if statements implicitly closed.
                             # If the first if statement was falsy (aka the input was one), then the string pushed at the beginning will be implicitly output.

```

# Answer
> 2 votes
# APL(Dyalog Unicode), 105 bytes SBCS

```
{⍺=0:∊'Nie ma żadnych '⍵'ów.'⋄⍺=1:∊'Jest 1 '⍵⋄1 0≡(2 3 4∘+¨0 10)∨/⍤∊¨10 100|⍺:∊'Są'⍺⍵'y.'⋄∊'Jest'⍺⍵'ów.'}

```

Try it on APLgolf!

Ironic.

---
Tags: code-golf, string, natural-language
---


title: Don't touch the walls!

text:
# Question
Title: Don't touch the walls!
Given a multi-dimensional rectangular array of non-negative integers, pad it with the minimal number of zeroes so that only zeroes are "touching the edges" of the array, in every dimension.

The output must remain rectangular, have the same number of dimensions as the input, and be no smaller than the input.

## Example

For the input:

```
[[1, 3, 0],
 [2, 6, 7],
 [4, 0, 2],
 [0, 0, 0]]

```

Here is the array again with the elements which are "touching the edge" ***highlighted***:

```
[[***1***, ***3***, ***0***],
 [***2***, 6, ***7***],
 [***4***, 0, ***2***],
 [***0***, ***0***, ***0***]]

```

The expected output is:

```
[[0, 0, 0, 0, 0],
 [0, 1, 3, 0, 0],
 [0, 2, 6, 7, 0],
 [0, 4, 0, 2, 0],
 [0, 0, 0, 0, 0]]

```

Notice that:

* In the first row, even though there was already a zero on the right, we still had to add an extra zero on the right to keep the array properly rectangular
* The bottom row was already all zeroes, so no extra row needed to be added there

---

For the 1-dimensional array `[3, 4, 9, 0, 0]`, the edges are `[***3***, 4, 9, 0, ***0***]`.

---

For this 3-dimensional array:

```
[[[4, 0, 4, 1],
  [0, 0, 5, 8],
  [6, 0, 0, 0],
  [0, 3, 7, 0]],

 [[4, 9, 8, 5],
  [0, 6, 4, 0],
  [0, 0, 0, 3],
  [0, 9, 6, 1]],

 [[0, 4, 7, 9],
  [0, 2, 0, 6],
  [0, 0, 0, 0],
  [7, 0, 3, 0]],

 [[0, 5, 3, 5],
  [0, 0, 0, 0],
  [6, 5, 3, 0],
  [4, 6, 0, 8]]]

```

the edges are:

```
[[[***4***, ***0***, ***4***, ***1***],
  [***0***, ***0***, ***5***, ***8***],
  [***6***, ***0***, ***0***, ***0***],
  [***0***, ***3***, ***7***, ***0***]],

 [[***4***, ***9***, ***8***, ***5***],
  [***0***, 6, 4, ***0***],
  [***0***, 0, 0, ***3***],
  [***0***, ***9***, ***6***, ***1***]],

 [[***0***, ***4***, ***7***, ***9***],
  [***0***, 2, 0, ***6***],
  [***0***, 0, 0, ***0***],
  [***7***, ***0***, ***3***, ***0***]],

 [[***0***, ***5***, ***3***, ***5***],
  [***0***, ***0***, ***0***, ***0***],
  [***6***, ***5***, ***3***, ***0***],
  [***4***, ***6***, ***0***, ***8***]]]

```

Imagine each inner 2-dimensional array as a cross-section of a 3-dimensional box. The only elements which are not *touching the edges* are the ones on the *inside* of the box.

## Specification

"Touching the edges" is a hopefully fairly intuitive concept, but here is a specification:

Let's use the same example input array as above; its shape is `4, 3`.

Using *one-based indexing*, we can index any element of the array using two integers in the ranges \\$ \[1, 4\] \\$ and \\$ \[1, 3\] \\$.

The elements which are touching the edge are those with coordinates of the form `1, y`, `4, y`, `x, 1`, or `x, 3`.

So, formally, we can say, for an element to be "touching the edge", at least one part of its multidimensional indices is either 1 (the minimum possible coordinate), or the maximum possible coordinate (which is the size of the array in the respective dimension).

## Rules

## Test cases

| Input | Output |
| --- | --- |
| ``` [[[0]]] ``` | ``` [[[0]]] ``` |
| ``` [[1]] ``` | ``` [[0, 0, 0],<br> [0, 1, 0],<br> [0, 0, 0]] ``` |
| ``` [3, 4, 9, 0, 0] ``` | ``` [0, 3, 4, 9, 0, 0] ``` |
| ``` [[1, 3, 0],<br> [2, 6, 7],<br> [4, 0, 2],<br> [0, 0, 0]] ``` | ``` [[0, 0, 0, 0, 0],<br> [0, 1, 3, 0, 0],<br> [0, 2, 6, 7, 0],<br> [0, 4, 0, 2, 0],<br> [0, 0, 0, 0, 0]] ``` |
| ``` [[1, 0],<br> [0, 4]] ``` | ``` [[0, 0, 0, 0],<br> [0, 1, 0, 0],<br> [0, 0, 4, 0],<br> [0, 0, 0, 0]] ``` |
| ``` [[[[0, 0],<br>   [1, 3]],<br><br>  [[0, 6],<br>   [0, 5]]],<br><br><br> [[[0, 0],<br>   [0, 0]],<br><br>  [[1, 0],<br>   [2, 0]]]] ``` | ``` [[[[0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0]],<br><br>  [[0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0]],<br><br>  [[0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0]],<br><br>  [[0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0]]],<br><br><br> [[[0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0]],<br> <br>  [[0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 1, 3, 0],<br>   [0, 0, 0, 0]],<br><br>  [[0, 0, 0, 0],<br>   [0, 0, 6, 0],<br>   [0, 0, 5, 0],<br>   [0, 0, 0, 0]],<br><br>  [[0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0]]],<br><br><br> [[[0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0]],<br><br>  [[0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0]],<br><br>  [[0, 0, 0, 0],<br>   [0, 1, 0, 0],<br>   [0, 2, 0, 0],<br>   [0, 0, 0, 0]],<br><br>  [[0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0]]],<br><br><br> [[[0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0]],<br><br>  [[0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0]],<br><br>  [[0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0]],<br><br>  [[0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0],<br>   [0, 0, 0, 0]]]] ``` |

# Answer
# BQN, 24 bytes

```
(0×⊏)⊸∾⍟(0⊸×⊸≢⊏)∘⌽⍟2∘⍉⍟=

```

Try it!

### Explanation

```
(0×⊏)⊸∾⍟(0⊸×⊸≢⊏)∘⌽⍟2∘⍉⍟=
                         ⍟=  Given an N-dimensional array, do this N times:
                       ∘⍉     Rotate the array's indices (N-dimensional transpose), then
                     ⍟2       Do this twice:
                  ∘⌽           Reverse the array along its first axis, then
        ⍟                      Do X times
         (       )              where X is:
                ⊏               Take the first cell of the array
             ⊸≢                 and return 1 if it is different from
          0⊸×                   itself multiplied by zero
                               (thus, do iff the first cell is not all zeros):
     ⊸∾                         Join to the beginning of the array
(0×⊏)                           the first cell of the array multiplied by zero

```
> 11 votes

# Answer
# Wolfram Language (Mathematica), 71 bytes

```
#~ArrayPad~Sign@Table[Max/@Transpose[#,i<->1][[{1,-1}]],{i,Depth@#-1}]&

```

Try it online!
> 5 votes

# Answer
# Python NumPy, 95 bytes

```
lambda*a:pad(*a,[((a:=any(a,0)+0)[0].max(),a[-1].max())for _ in a[0].shape])
from numpy import*
```

Attempt This Online!
> 5 votes

# Answer
# , (was 296) 292 bytes

```
\(x,d=dim(x),n=length(d),a=array,e=seq(!d),m=e%%n+1,p=\(x)aperm(x,m),s=\(x,u)do.call(`[`,c(list(x),u)),u=lapply(d,\(x)quote(expr=)),r=\(x,y,z){l=dim(z);l[n]=l[n]+1;array(c(x,y),l)}){for(i in e){x=p(x);d=d[m];u[[n]]=d[n];k=s(x,u);if(any(k))x=r(x,k*0,x);u[[n]]=1;if(any(s(x,u)))x=r(k*0,x,x)};x}
```

Attempt This Online!

Similar to the package approach, but R arrays are stored last-dimension-first so we loop through permuting the array each time so we're considering the last dimension, then add faces where needed. Now just using base R and it works in ATO.

# R+abind+rlang, 220 bytes

```
\(x,d=dim(x),b=\(y,z,d)abind::abind(y,z,along=d),s=\(x,u)do.call(`[`,c(list(x),u)),m=lapply(d,\(x)rlang::expr())){for(i in 1:length(d)){u=m;u[i]=d[i];g=s(x,u);if(any(g))x=b(x,g*0,i);u[i]=1;if(any(s(x,u)))x=b(g*0,x,i)};x}
```

Attempt This Online!

Basically loop through the dimensions and add on slices where appropriate after checking the final slice then initial slice. For loop has to use 1:length(d) rather than seq(d) in case d is a scalar.

Doesn't work in ATO but does work in rdrr.io with the following:

```
test1=array(c(0), dim=1)
test2=array(c(1), dim=c(1,1))
test3=array(c(3,4,9,0,0), dim = 5)
test4=array(c(1,3,0,2,6,7,4,0,2,0,0,0), dim = c(3,4))
test5=array(c(1,0,0,4), dim = c(2,2))
test6=array(c(0,0,1,3,0,6,0,5,0,0,0,0,1,0,2,0), dim = c(2,2,4))

f=function(x,d=dim(x),b=function(y,z,d)abind::abind(y,z,along=d),s=function(x,u)do.call(`[`,c(list(x),u)),m=lapply(d,function(x)rlang::expr())){for(i in 1:length(d)){u=m;u[i]=d[i];g=s(x,u);if(any(g))x=b(x,g*0,i);u[i]=1;if(any(s(x,u)))x=b(g*0,x,i)};x}

f(test1)
f(test2)
f(test3)
f(test4)
f(test5)
f(test6)

```
> 3 votes

# Answer
# Python3, 408 bytes:

```
lambda a:[(a:=f(a,a,i))for i in[*range(D(a))][::-1]][-1]
I=lambda x:int==type(x)
S=lambda x:x if I(x)else sum(map(S,x))
K=lambda x,e,d,l=0:S(x[e])if d==l else any(K(i,e,d,l+1)for i in x)
B=lambda x:0 if I(x)else[B(i)for i in x]
U=lambda o,a,d:[B(a[0])]*(K(o,0,d)>0)+a+[B(a[0])]*(K(o,-1,d)>0)
D=lambda x,l=0:l if I(x)else max(D(i,l+1)for i in x)
f=lambda o,a,d,l=0:U(o,a,d)if d==l else[f(o,i,d,l+1)for i in a]

```

Try it online!
> 1 votes

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


title: Give f and g that sometimes commute

text:
# Question
Title: Give f and g that sometimes commute
Let \\$Z\\$ be either the integers, the positive integers, or the non-zero integers; pick whatever's convenient. Give two functions \\$f\\$ and \\$g\\$, each \\$Z \to Z\\$, such that:

* \\$f(g(a)) = g(f(a))\\$, for infinitely many integers \\$a\\$, and
* \\$f(g(b)) \ne g(f(b))\\$, for infinitely many integers \\$b\\$.

## Rules

Many of the rules from f(g(x)) decreases while g(f(x)) increases are stolen here:

* Please provide an argument for why your functions fulfill the requirements.
* Interpret "function" in the mathematical sense. That is, they must be total (defined over all of \\$Z\\$) and pure (given the same input, it must produce the same output).
* You may submit the functions as a single program or two separate ones.
    + A single program must either have two named functions \\$f\\$ and \\$g\\$, or, when run, have output that can be interpreted as a pair of two functions \\$f\\$ and \\$g\\$.
    + Two separate programs must have one give \\$f\\$, and the other give \\$g\\$. The two programs may not refer to each other. In this case, functions may be unnamed.
* Standard submission rules and input/output methods apply, but we require that \\$f\\$ and \\$g\\$ must have identical input and output representations; that is, they can be directly composed without manually converting in between. Conceptually, they must be functions over integers, so you can't cheat by using two different string representations of the same number or anything like that.
* The usual integer overflow rules apply: your solution must be able to work for arbitrarily large integers in a hypothetical (or perhaps real) version of your language in which all integers are unbounded by default, but if your program fails in practice due to the implementation not supporting integers that large, that doesn't invalidate the solution.
* This is . If you submit a single program, your score is the number of bytes of that program. If you submit two programs, your score is the sum of the number of bytes of both programs.

# Answer
# Retina, 0 + 1 = 1 byte

Try it online!

This is a Count stage that matches an empty string at the start, between every two consecutive digits, and at the end. This produces the number of digits plus 1.

---

```
.

```

Try it online!

This is a Count stage that matches every digit, producing the number of digits.

---

Applying these in the two possible orders gives \\$\mathrm{ndigits}(\mathrm{ndigits}(n))+1\\$ and \\$\mathrm{ndigits}(\mathrm{ndigits}(n)+1)\\$, which are equal if and only if \\$\mathrm{ndigits}(n)\\$ is 1 less than a power of 10.
> 13 votes

# Answer
# Python, 3+4 = 7 bytes

`abs`

`hash`

These two builtins commute for most integers.

But not all:

The following depends on an implementation detail of CPython; I didn't find an official spec, below I give my best guess:

`hash` maps integers onto themselves modulo `2**61-1` (which appears to be the 9th Mersenne prime; also, this may depend on the bitness (32/64 etc.) of the C long of the platform) while keeping the sign (so `-4` does not map to `2**61-5` but to `-4`). Therefore `hash(-n)==-hash(n)` for all integers except those which equal `+/-1` modulo `2**61-1` because in the underlying `C` implementation `-1` is used as an error indicator. So, whenever the hash would be `-1`, `-2` is returned instead.

Minimal demo at TIO
> 13 votes

# Answer
# Jelly, 1 + 1 = 2 bytes

\\$f(x) = x \bmod 2\\$ (Try it online!).

\\$g(x) = 2x\\$ (Try it online!). These functions commute only for even input.
> 9 votes

# Answer
# Pascal (FPC), 7 bytes

```
succ

```

```
odd

```

Try it online!

`succ` acted as \\$x \rightarrow x+1\\$; while `odd` acted as \\$x \rightarrow x \bmod 2\\$. So `succ(odd(x)) = odd(succ(x))` iff x is even.
> 9 votes

# Answer
# Brachylog, 1 byte (or 2 bytes if including call modifier)

```
b

```

Try it online!

**I don’t know exactly if that’s bending the rules or not, let me know.**

In this single program, `f(x)` is `b - behead`, with a given input and an unknown output, and `g(x)` is also `b - behead`, but with a given output and an unknown input.

You can run `f(g(x)` with `↰₁~↰₁` in the header, and `g(f(x))` with `~↰₁↰₁`. This is why I’m ok with this being scored as 2 bytes, as you need to use `~` to "reverse" the program’s calling order.

### Explanation

`b` asserts that its output is the input without the first element.

* For all positive integers that begin with a leading `1` (except `1` itself), `f(g(x))` will remove this leading 1, and then add an unknown leading digit back. Since `0` cannot be a leading digit, this leading digit will unify with `1` as the next possibility, and so `f(g(x)) = x`. Similarily, `g(f(x))` will append an unknown leading digit first, and then remove it, so once again `g(f(x)) = x = f(g(x))`.
* For all positive integers that don’t begin with a leading `1` (and `1`), `f(g(x))` will remove the leading digit, and then append an unknown leading digit, which will unify with `1` as it is the first possibility. Since the initial leading digit wasn’t `1`, we have `f(g(x)) ≠ x`. On the other hand, `g(f(x))` will append an unknown leading digit, and then remove it, leaving `x` unchanged. So we have `g(f(x)) = x ≠ f(g(x))`.

Obviously, there are infinitely many positive integers that start with a leading `1`, and infinitely many positive integers that don’t.
> 7 votes

# Answer
# Wolfram Language (Mathematica), 7 bytes

```
Abs

```

```
#+1&

```

Try it online!

\\$(f\circ g)(x)=|x+1|\\$, the distance of \\$x\\$ from \\$-1\\$. \\$(g\circ f)(x)=|x|+1\\$, one more than the distance of \\$x\\$ from \\$0\\$. These are equal when \\$x\ge0\\$, and unequal when \\$x\<0\\$.

I suspect this is minimal. Trig functions such as `Sin` unfortunately are not \\$\mathbb Z\to\mathbb Z\\$.
> 6 votes

# Answer
# Zsh, 6 + 6 = 12 bytes

```
tr 1 2
```

Attempt This Online!

```
tr 2 3
```

Attempt This Online!

The first program replaces `1`s with `2`s; the second replaces `2`s with `3`s. These commute only for numbers not containing the digit `1`.

---

Old answer:

## Zsh, 10 + 10 = 20 bytes

\\$ f(x) = \lfloor \frac x 2 \rfloor \\$

```
<<<$[$1/2]
```

Attempt This Online!

\\$ g(x) = 2x \\$

```
<<<$[$1*2]
```

Attempt This Online!

For even \\$ x \\$, \\$ f(x) = \frac x 2 \\$, so \\$ g(f(x)) = x \\$.

But for odd \\$ x \\$, `/2` rounds downwards, so \\$ f(x) = f(x-1) \\$, so \\$ g(f(x)) = x - 1 \ne x \\$

\\$ g(x) \\$ is always even, so for all \\$ x \\$, \\$ f(g(x)) = x \\$.

Therefore, \\$ f(g(x)) = g(f(x)) \\$ if and only if \\$ x \\$ is even.
> 6 votes

# Answer
# Python, 9 + 3 = 12 bytes

\\$ f(x) = \operatorname{bitwise\\\_or}(x, 1) = \begin{cases} x & x \text{ is odd} \\ x + 1 & x \text{ is even} \end{cases} \\$

```
1 .__or__
```

Attempt This Online!

\\$ g(x) = \lvert x \rvert = \begin{cases} x & x \ge 0 \\ -x & x \le 0 \end{cases} \\$

```
abs
```

Attempt This Online!

Commutes for all \\$ x \\$ except negative even numbers.

If \\$ x \\$ is positive or odd, then at least one of \\$ f \\$ and \\$ g \\$ will act as the identity function \\$ \operatorname{id} \\$ and return \\$ x \\$ unchanged. In that case, clearly, they commute:

$$ h(\operatorname{id}(x)) = h(x) = \operatorname{id}(h(x)) $$
> 6 votes

# Answer
# , 5 + 3 = 8 bytes

```
nchar

```

```
abs

```

Attempt This Online!

Commutative for positive values & zero, non-commutative for negative values (since the minus sign is counted as a character by `nchar`).
> 5 votes

# Answer
# Julia, 17

```
f(n)=n%2;g(n)=n%3

```

consider the numbers of form 6k and 6k+3.

ATO
> 4 votes

# Answer
# K (ngn/k), 2 + 2 = 4 bytes

```
0=
1>

```

Try it online!

* f: `0=`, returns 1 if the input is 0, 0 otherwise.
* g: `1>`, returns 1 if the input is 0 or negative, 0 otherwise.

`g` is boolean negation when the domain is limited to booleans (0 and 1). `f(x)` and `g(x)` are the same for `x>=0` and different otherwise, and the same can be said for `g(f(x))` (negation of `f(x)`) and `f(g(x))` (negation of `g(x)`).

4 bytes is optimal in ngn/k since any monadic function is at least two bytes long.

Czylabson Asa's mod-2 and mod-3 are also the same length in K: `2!` and `3!`.
> 4 votes

# Answer
# , 3 bytes

`|` absolute value

`>:` increment

Try it online!

See att's answer for explanation.
> 4 votes

# Answer
# Octave, 14 bytes

I haven't seen anyone use this one yet, it might work better in another language. (And it is definitely possible to do better in Octave!)

```
@(x)x<0
@(x)x>0

```

The key here is that `true == 1` and `false == 0`. Try it online!
> 4 votes

# Answer
# JavaScript (ES6), 6 + 5 = 11 bytes

These functions commute for odd negative values and for even non-negative values. They do not commute for the other cases.

```
f=
x=>x%2 // 6 bytes
g=
x=>~x  // 5 bytes

```

Try it online!

### Explanation

The sign of the modulo in JS is the sign of the numerator. So the functions are more formally defined as:

$$\begin{align}&f(x)=\cases{0&if $x$ is even\\\-1&if $x\<0$ and $x$ is odd\\1&if $x\>0$ and $x$ is odd}\\ &g(x)=-x-1\end{align}$$

For odd negative values, we have: \\$\cases{g(f(x))=g(-1)=0\\f(g(x))=f(-x-1)=0}\\$

For even negative values, we have: \\$\cases{g(f(x))=g(0)=-1\\f(g(x))=f(-x-1)=1}\\$

For odd non-negative values, we have: \\$\cases{g(f(x))=g(1)=-2\\f(g(x))=f(-x-1)=0}\\$

For even non-negative values, we have: \\$\cases{g(f(x))=g(0)=-1\\f(g(x))=f(-x-1)=-1}\\$

### Generalization

We can actually use any modulo \\$m\>1\\$ for \\$f\\$, making the non-commutative cases more and more sparse as \\$m\\$ increases (but obviously, we'd still get infinitely many of them).

Try it online! (example with \\$m=5\\$)
> 3 votes

# Answer
# APL (Dyalog Unicode), 4 bytes

`|` absolute value

`1∘+` increment (lit. 1 curried to plus)

Try it online!

See att's answer for explanation.
> 2 votes

# Answer
# Retina, 8 + 4 = 12 bytes

```
V`[1-9]+

```

Try it online! Link includes test cases. Explanation: Reverses all runs of non-zero digits.

```
L`.$

```

Try it online! Link includes test cases. Explanation: Outputs the last digit, without a sign.

The functions commute in a lot of cases such as the trivial ones of the input being a multiple of 10 or a repdigit.
> 2 votes

# Answer
# BQN, 3 bytes (SBCS)

```
|¬
|

```

Try it online!

`abs(1-x)` and `abs(x)` respectively. `f(g(x)) = abs(1-abs(x))` and `g(f(x)) = abs(abs(1-x)) = abs(1-x)`. The results differ if and only if `x` is negative.

```
   F←|¬
   G←|
   x←¯10+↕20
   (F G x)≍(G F x)
┌─
╵  9  8 7 6 5 4 3 2 1 0 1 0 1 2 3 4 5 6 7 8
  11 10 9 8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 7 8
                                            ┘

```
> 2 votes

# Answer
# x86 32-bit machine code, 2 + 2 = 4 bytes

```
40 C3
98 C3

```

Try it online!

Uses the `regparm(1)` calling convention – argument in EAX, result in EAX.

In assembly:

`inc eax; ret`\\$f\\$ simply adds 1 to a number.

`cwde; ret`\\$g\\$ sign-extends the low 16 bits of EAX, duplicating bit 15 into all the higher bits.

If the low 15 bits are not all 1, these two functions do not interact, thus they commute.

If the low 16 bits are 1111 1111 1111 1111, either order of functions results in 0.

If the low 16 bits are 0111 1111 1111 1111, applying \\$f\\$ then \\$g\\$ results in -32768, while applying \\$g\\$ then \\$f\\$ results in 32768.
> 2 votes

# Answer
# Husk, 1+1 = 2 bytes

```
ṗ
¬

```

Try it online!

There are several 1+1 bytes pairs that work in Husk (including a port of the absolute-value/offset approach \[`a`/\] that separates `a`/`b` by positive/negative values, and some other interesting approaches).

But I like this one best:  and `¬` are commutative only for prime numbers, and non-commutative for all positive non-prime integers.

```
ṗ    # index of x in the infinite list of primes, or zero if non-prime
D    # logical NOT

```

So:

```
ṗ¬   # outputs zero for all nonzero inputs
¬ṗ   # outputs 1 for non-primes, zero for prime numbers

```
> 2 votes

# Answer
# 22 bytes total

# , 15 bytes

```
\(x)round(x,-2)
```

Attempt This Online!

# , 7 bytes

```
\(x)x^2
```

Attempt This Online!

Commutes for x 0 mod 100, doesn't for x 0 mod 10 but not 0 mod 100.
> 2 votes

# Answer
# Vyxal, 1 + 1 = 2 bytes

f(x) =  and g(x) = `ȧ`.

`ȧ` is absolute value and  is decrement, so \\$f(g(x))\\$ = \\$\left|x-1\right|\\$ and \\$g(f(x))\\$ = \\$ \left|x\right| - 1\\$, which are the same only on positive integers.
> 1 votes

# Answer
# Charcoal, 3 + 3 = 6 bytes

```
Ｉ↔Ｎ

```

Try it online! Link is to verbose version of code.

```
Ｉ⊕Ｎ

```

Try it online! Link is to verbose version of code.

Another port of @att's Mathematica answer.
> 1 votes

# Answer
# Haskell, 3 + 4 bytes

```
abs
(+1)

```

If `x` is non-negative the functions commute, otherwise they do not.

# Haskell, 4 + 8 bytes

```
(*2)
(`div`2)

```

If `x` is even, the functions commute. If `x` is odd, `(``div`` 2) $ (*2) x` is equl to `x`, while `(*2) $ (``div`` 2) x` is equal to `x-1`.
> 1 votes

# Answer
# Factor, 3 + 3 = 6 bytes

```
abs

```

```
?1+

```

Try it online!

Absolute value and increment. (`?1+` is a single word/function that always increments integers by one or changes `f` \[Factor's canonical false value\] to `0`.) Factor does not come with a 'normal' increment word, such as `1+` in Forth.
> 0 votes

# Answer
# sh + coreutils, 16 + 7 bytes

```
(cat;echo +1)|bc
tr -d -

```

The first function adds one to the number given in input; the second function calculates the absolute value. The composition here is intended as piping the output of one into the other, that is:

```
echo -n "-12" | (cat;echo +1)|bc | tr -d -
echo -n "-12" | tr -d - | (cat;echo +1)|bc

```
> 0 votes

---
Tags: code-golf, open-ended-function
---


title: What an Odd Function

text:
# Question
Title: What an Odd Function
Your task here will be to implement a function1 that forms a permutation on the positive integers (A bijection from the positive integers onto themselves). This means that each positive integer should appear exactly once in the permutation. The catch is your function should have a larger probability of outputting an odd number than an even number.

Now this may seem strange or impossible. Surely there are just as many odd numbers as even numbers? And while this intuition is correct for finite sets it actually does not hold for infinite sets. For example take the following permutation:

```
1 3 2 5 7 4 9 11 6 13 15 8 17 19 10 21 23 12 25 27 14 29 31 16 33 35 18 37 39 20 41 43 22 45 47 24 49 51 26 53 55 ...

```

If you take any subsection of the sequence with size greater than \\$1\\$ you will have at least as many odd numbers as even numbers, thus it seems that the probability of any random term being odd is greater than that of being even. You will also note every number odd or even number will eventually appear in the sequence and can only appear once. Thus the sequence is a true permutation.

### Definition of Probability

To avoid confusion or ambiguity I am going to clearly lay out what is meant by probability in this question.

Let us say we have a function \\$f\\$. The probability of a number being odd will be defined as the limit of ratio odd members of the set to the size of the set \\$f\\{1\dots n\\}\\$ as \\$n\\$ tends towards infinity.

$$\lim\_{n\rightarrow \infty}\dfrac{\left|\\{x : x \in \\{1\dots n\\}, \mathrm{odd}(f(x))\\}\right|}{n}$$

For example the aforementioned function would have a probability of being odd of \\$2/3\\$.

---

This is so answers will be scored in bytes with less bytes being better.

---

### Extra Challenges

Here are some fun ideas to play around with and perhaps try to implement. These are just for fun and do not affect scoring in any way. Some of these are not even valid solutions to this challenge, and **an answer which only includes solutions to challenges 2 or 3 is not a valid answer, and is liable to be deleted**.

* Write a permutation with an odd probability of \\$1\\$. (this is possible)
* Write a permutation that has more odd numbers than even numbers in \\$f\\{1\dots n\\}\\$ for any \\$n\\$ but has a odd probability of \\$1/2\\$.
* Write a permutation that has no defined probability (that is there is no limit). (Now a standalone challenge here)

---

1: Here function will mean program or function. It is just a piece of code that takes input and produces output.

# Answer
# Jelly, 7 bytes

```
Æf^<¥4P

```

Swaps **2**s and **3**s in the input's prime factorization. The probability of odds is **2/3**.

Try it online!

### How it works

```
Æf^<¥4P  Main link. Argument: n

Æf       Compute all prime factors of n, with duplicates.
    ¥4   Combine the two links to the left into a dyadic chain and call it with
         right argument 4.
   <       Compare each prime factor with 4. Yields 1 for 2 and 3, 0 otherwise.
  ^        Bitwise XOR the results with the corresponding prime factors.
         This maps 2 to 3, 3 to 2, and all other primes to themselves.
      P  Take the product of the resulting primes.

```
> 31 votes

# Answer
# Husk, ~~11~~ 10 bytes

-1 byte thanks to Leo, and a slightly different function

This has an odd probability of `1`

```
!uΣz:NCNİ1

```

Try it online!

It indexes the sequence:

```
[1,2,3,5,7,9,11,4,13,15,17,19,21,23,25,27,29,6,31,33]
1 odd, 1 even, 5 odd, 1 even, 9 odd, 1 even, 13 odd...

```

### Explanation

```
!               Index the following sequence (1-indexed)
 u              remove duplicates                     [1,2,3,5,7,9,11,4,13,15...]
  Σ              Concatenate                          [1,1,2,3,5,3,7,9,11,4,13..]
   z:            Zipwith append                       [[1,1],[2,3,5],[3,7,9,11]..
     N          Natural numbers
      CNİ1      Odd numbers cut into lists of lengths [[1],[3,5],[7,9,11]...]
                corresponding to the Natural numbers

```
> 15 votes

# Answer
## Haskell, ~~35~~ ~~34~~ 32 bytes

```
f n=n:2*n+1:2*n+3:f(n+2)
(f 0!!)

```

Implements the example sequence `[1,3,2,5,7,4,9,11,6,13,15,8,17,19,10,21,...]`.

Try it online!

For reference: old version, 34 bytes (-1 byte thanks to @xnor):

```
(!!)$do e<-[0,2..];[e,2*e+1,2*e+3]

```

Try it online!
> 8 votes

# Answer
Everybody does Challenge 1, so let's do the other two.

# Perl 6, 26 bytes — Challenge 2

```
{($_==1)+$_-(-1)**($_%%2)}

```

Try it online!

It's just `1 3 2 5 4 7 6...` In an even number of terms, there are always 2 more odd numbers than even. In an odd number, 1 more. However this has clearly limit of `(n+2)/(2n+2) -> ½`.

---

# Perl 6, 70 bytes — Challenge 3

```
{((1,),(2,4),->@a,@ {@(map(@a[*-1]+2*(*+1),^(4*@a)))}...*).flat[$_-1]}

```

Try it online!

Admittedly, this is horribly golfed. It indexes a sequence that contains 2⁰ odd numbers, then 2¹ even, then 2² odd, then 2³ even, and so on.

The probability after n such "blocks", if n is odd, is (2⁰+2²+2⁴+...+2ⁿ⁻¹)/(2ⁿ-1). The sum in the numerator is equal to ⅓(4½(n+1) \- 1) = ⅓(2n+1 \- 1). So the probability after odd number of blocks is ⅔ (in the limit).

If we add one more block (and strike an even count of them n+1), however, we didn't add any odd numbers (numerator stays the same) but there is now (2n+1 \- 1) numbers in total. The parentheses cancel and we get the probability of ⅓ (in the limit).

This is apparently supposed to have 2 different cluster points, ⅓ and ⅔, to make sure that the limit doesn't exist, but this doesn't really prove it. My attempt to do a solid, rigorous proof can be found in this Math.SE answer: https://math.stackexchange.com/a/2416990/174637. Bashing mistakes is welcome.

---

# Perl 6, 39 bytes — The core challenge.

```
{my$l=$_ div 3;$_%3??2*($_-$l)-1!!2*$l}

```

Try it online!

Though I posted this answer because of the challenges 2 and 3 which offered a pleasant little mathy puzzle, there is a strict requirement for all answers to contain a solution to the core challenge. Here it is then.

This is the example sequence.
> 8 votes

# Answer
# Husk, 8 bytes

```
!uΣzeİ1N

```

Try it online!

This implements the example sequence (`1,3,2,5,7,4...`).

### Explanation

```
!uΣzeİ1N
   ze       zip together
     İ1       the odd numbers
       N      with the natural (positive) numbers
  Σ         flatten the resulting list
 u          remove duplicates
!           index into the obtained sequence with the input

```
> 8 votes

# Answer
# Brain-Flak, 120 bytes

```
(({})<{{({}[()]<({}(()[{}]))>)}{}({}[({})]<({}<>{}<({}())>)><>)}>)<>({}[()]){{}((<>{}<>[{}]){}[()])<>}{}{(({}){})<>{}}<>

```

Try it online!

Performs the following function:

This function generates the sequence

```
2 4 1 6 3 5 7 8 9 11 13 15 17 19 21 10 23 25 27 29...

```

The function has an odd probability of `1`
> 6 votes

# Answer
# R, 82 bytes (Extra challenge 1)

```
f<-function(n){if(sqrt(n)==floor(sqrt(n))){2*sqrt(n)}else{2*(n-floor(sqrt(n)))-1}}

```

Try it Online!

If the input is a perfect square, gives an even number. Otherwise, gives an odd number. The perfect squares have natural density 0, which means that this sequence gives odd numbers with probability 1.
> 4 votes

# Answer
# C (gcc), 29 bytes

```
f(n){return n&3?n+n/2|1:n/2;}

```

Try it online!

Every fourth number is even:

```
1 3 5   7 9 11   13 15 17   19 21 23   25 27 29
      2        4          6          8          10

```

# Extra challenge 1, 52 bytes

```
f(n,i){for(i=0;n>>i/2;i+=2);return n&n-1?2*n-i-1:i;}

```

Try it online!

Returns 2\*(x+1) if n equals 2x and consecutive odd numbers otherwise:

```
    1   3 5 7   9 11 13 15 17 19 21    23 25
2 4   6       8                     10

```
> 3 votes

# Answer
# Brain-Flak, ~~140~~ ~~138~~ 136 bytes

```
({}<(((()())()()))((<>[()])[()()])>){({}[()]<(({}(({}({}))[({}[{}])]))[({}[{}])]<>(({}(({}({}))[({}[{}])]))[({}[{}])])<>)>)}{}({}<{}{}>)

```

Try it online!

## Explanation

This performs a similar function to the one suggested in the question.

```
2 3 1 4 7 5 6 11 9 8 15 13 10 17 15 ...

```

It works mostly based on a snippet I made to roll the stack for size 3 stacks.

```
(({}(({}({}))[({}[{}])]))[({}[{}])])

```

We set up two stacks one with accumulator values (two odd one even) and one with the numbers `4 4 2`. Each iteration we roll both stacks and add the top of the left stack to the top of the right stack.

```
(({}(({}({}))[({}[{}])]))[({}[{}])]<>(({}(({}({}))[({}[{}])]))[({}[{}])])<>)

```

This will increment each odd number by 4 and the one even number by 2. As we loop through we get a pattern of 2 odd 1 even, with every positive integer being hit. Thus we just loop `n` times with `n` being the input. This has an asymptotic probability of **2/3**.
> 3 votes

# Answer
# Re:direction, ~~20~~ 19 bytes

```
+++>>
 v>
 +>>
v>
<

```

Try it online!

-1 by rearranging to remove a space.

Here's what happens, based on the input number:

* **3n**: It runs along the first line n times, picking up 2n `>`s, before going down from the first `+`. It then adds a `v`, and hits the bottom `<`, which points to itself to halt, outputting **2n**.
* **3n+1**: It again runs along the first line n times, picking up 2n `>`s, and then it passes the first `+` and goes down on the second one. It then adds a `v`. The loop on the third line doubles the number of `>`s in the queue to 4n before ending by consuming the `v`. On the fourth line, another `>` is added, for 4n+1, before ending in the same way as the previous case, outputting **4n+1**.
* **3n+2**: Mostly the same as the above case, except going down from the third `+` and then adding an extra `>` before joining the same path, making 2n+1, which becomes 4n+2, then 4n+3, and outputting **4n+3**.
> 3 votes

# Answer
# Jelly, 10 bytes

```
ÆE;0ṭ2/FÆẸ

```

The probability of odds is **2/3**.

Try it online!

### How it works

```
ÆE;0ṭ2/FÆẸ  Main link. Argument: n

ÆE          Compute the exponents of n's prime factorization.
  ;0        Append a 0.
     2/     Reduce all pairs by...
    ṭ         tack, appending the left argument to the right one.
            This inverts all non-overlapping pairs of exponents.
       F    Flatten the result.
        ÆẸ  Consider the result a prime factorization and compute the corresponding
            integer.

```
> 2 votes

# Answer
# JavaScript, 23 bytes

```
n=>n/2+n/2%2+(n%4&&n-1)

```

Output: 1, 3, 5, 2, 7, 9, 11, 4, 13, 15, 17, 6, 19, 21, 23, 8...

* For all n = 4k:
    + f(n) = n/2 = 2k
* For all n = 4k + b
    + f(n) = n/2 + b/2 + n - 1 = 3/2 * (4k + b) + 1/2 * b - 1 = 6k + 2b - 1

---

Challenge 2:

```
n=>n^(n>1)

```

Output: 1, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14
> 2 votes

# Answer
# C, 80 bytes

```
#define R if(k++==n)return
i,j,k;f(n){for(i=k=1,j=2;;i+=4,j+=2){R i;R i+2;R j;}}

```

Implementation of the example permutation from the question.

Try it online!
> 1 votes

# Answer
## Batch, 36 bytes

```
@cmd/cset/an=%1*2,(-~n*!!(n%%3)+n)/3

```

Implements the sequence given in the question.
> 1 votes

# Answer
## CJam (21 bytes)

```
{2b_(&!\_,2*\1$~+2b?}

```

Online demo showing the first 32 outputs. This is an anonymous block (function).

This is also a solution to challenge 1: the numbers mapped to even numbers are the powers of 2, so the density of even numbers in the first n outputs is lg(n)/n which tends to zero.

### Dissection

```
{         e# Declare a block; let's call the input x
  2b      e#   Convert to base 2
  _(&     e#   Copy, pull out first digit (1) and set intersection with rest
  !       e#   Boolean not, so empty set (i.e. power of 2) maps to 1 and non-empty
          e#   to 0
  \_,2*   e#   Take another copy, find its length, and double it
  \1$~+   e#   Take the original base 2 array and append ~(2L) = -2L-1
  2b      e#   Convert from base 2, to get 2x-2L-1
  ?       e#   Take the 2L if it was a power of 2, and the 2x-2L-1 otherwise
}

```
> 1 votes

# Answer
# Perl 40 bytes

```
$,=$";$i=4;{say$i-3,$i/2,($i+=4)-5;redo}

```
> 1 votes

# Answer
# Brain-Flueue, 88 bytes

```
({}<(((<>)[()])[()()])>)<>(((()())()()))<>{({})({})({})({}[()]<({}<>({})<>)>)}{}{}({}){}

```

Try it online!

## Explanation

This implements the same function as my last answer but uses Brain-Flueue's FIFO model to cut some corners. Here are the first couple terms it generates.

```
2 3 1 4 7 5 6 11 9 8 15 13 10 17 15 ...

```

The first part of the code is just a bit of setup, we put `0,-1,-3` on the first stack and `2,4,4` on the second stack. The `2,4,4` will be used to cycle through even and odd numbers just as I did in my Brain-Flak answer.

We then loop n times, each time adding the top of the left stack to the right stack. Since Brain-Flueue uses queues as opposed to stacks the values naturally roll as we touch them preventing the need for extra code.
> 1 votes

# Answer
# Lean, 85 bytes

```
import data.nat.prime
λx,list.prod$list.map(λp,if p<4then 5-p else p)$nat.factors x

```

Try it online!

Swaps 2s with 3s in the prime factorization.
> 1 votes

# Answer
# Vyxal, 6 bytes

```
ǐ:4<꘍Π

```

Try it Online! or run it from 1 to 100.

Port of Dennis's Jelly answer. ~~`1J` is needed due to a bug in Vyxal where the product of `[]` returns `0` instead of `1`.~~ Bug fixed.

## How?

```
ǐ:4<꘍Π
ǐ      # Get the prime factors with duplicates
 :     # Duplicate
  4<   # For each item, is it less than 4? (Vectorizes, produces a list of 1s and 0s)
    ꘍  # Bitwise XOR the two arrays (vectorizes)
     Π # Product of resulting array

```
> 1 votes

# Answer
# Vyxal, 8 bytes

```
Þ∞y$:ẇYf

```

Try it Online!

Challenge number 1 - a list with an odd probability 1. Creates an infinite list.

The sequence generated looks like \\$2, \color{red}{1}, \color{black}{4}, \color{red}{3, 5, 7}, \color{black}6, \color{red}{9, 11, 13, 15, 17}, \color{black}{8}\cdots\\$, interleaving the even numbers with the odd numbers in ever-growing chunks.

If we take the first \\$k^2+k\\$ terms for integer \\$k\\$, \\$\sum\_{n=0}^{k}2n+1 = k^2\\$ of them will be odd and \\$k\\$ will be even, so the proportion of odd numbers is \\$\frac{k}{k+1}\\$. As \\$k \to ∞ \\$, \\$ \frac{k}{k+1} \to 1\\$.

```
Þ∞       # Infinite list of positive integers
  y$     # Uninterleave, pushing odds and evens, and swap the odds on top
    :ẇ   # Cut odds into sequences of lengths [1, 3, 5, 7...]
      Yf # Interleave and flatten.

```
> 1 votes

# Answer
# Python 2, ~~46~~ ~~104~~ 55 bytes

```
lambda n:2*((n-int(n**.5))+.5,n**.5-1)[n!=1>0==n**.5%1]

```

Try it online!

Misread the question, now properly implemented a function that can be used to generate a sequence instead of one that generates a sequence. Also excluded `0` from the set of possible outputs.

Probability of finding an odd positive integer now converges to `1`.
> 0 votes

# Answer
## Lua, ~~67~~ 53 bytes

~~Explanation coming when I'm done golfing this :)~~

This program takes an integer via command-line arguments as input and prints out the nth element of the exemple sequence to STDOUT

```
n=...print(n%3<1 and n/3*2or n+math.floor(n/3)+n%3-1)

```

### Explanations

```
n=...                              -- shorthand for the argument
print(                             -- prints out the result of the following ternary
     n%3<1                         -- if n is divisible by 3
       and n/3*2                   -- prints out the corresponding even number
       or n+math.floor(n/3)+n%3-1) -- else prints out the odd number

```

The even numbers of this sequence are both the `n`th even number and the `n` multiple of 3, hence the formula `n%3*2` is sufficient to generate them.

For odd numbers, it's a little bit more tough. Based on the fact that we can find them depending on the current `n`, we have the following table :

```
n       |  1   2   4   5   7   8   10   11
target  |  1   3   5   7   9   11  13   15
target-n|  +0  +1  +1  +2  +2  +3  +3   +4

```

Let's call the value `target-n` `i`, we can see that each time `n%3==2`, `i` is incremented. There goes our formula :

```
n+math.floor(n/3)+n%3-1

```

The odd numbers are based on `n` on which we add `i`.

The value of `i` increments at the same rate as the euclidian division by 3, with an offset. `math.floor(n/3)` gives us the rate of increment and `n%3-1` gives us the offset, making it happens on `n%3==2` instead of `n%3==0`.
> 0 votes

# Answer
# Jelly, 9 bytes

```
Ḥ€’ĖUẎQ⁸ị

```

Try it online!

Implements `1, 3, 2, 5, 7, 4, 9, 11, 6, ...` (probability 2/3).
> 0 votes

# Answer
# 05AB1E, 11 bytes

```
·ÅÉā‚ø˜Ù¹<è

```

Try it online!
> 0 votes

# Answer
# Pyth, 9 bytes

```
*Fmxd<d4P

```

**Try it here!** or **Test more in one go!**

You can use this code to verify the ratio of odd numbers up to a certain point. Substitute `10000` with your desired limit (don't set it much higher, because it memory errors).

```
Km*Fmxk<k4PdS10000clf%T2KlK

```

Try it here.

The above gives roughly **0.667**. The true probability of odd occurrences is **2/3**. This approach is an equivalent implementation of Dennis' answer.

---

# Explanation

```
*Fmxd<d4P   Full program.

        P   Prime factors.
  m         Map over ^.
   x        Bitwise XOR between:
    d          The current prime factor.
     <d4       The integer corresponding to the boolean value of current factor < 4.
*F          Product of the list.

```
> 0 votes

# Answer
# Java 8, 20 bytes

```
n->n%4>0?n+n/2|1:n/2

```

Port of *@nwellnhof*'s C answer.
Some things I tried myself ended up being a few bytes longer or slightly incorrect..

Implements: `1,3,5,2,7,9,11,4,13,15,17,6,19,21,23,8,25,27,29,10,31,33,35,12,37,...`
with a probability of `3/4`.

Try it here.
> 0 votes

# Answer
# 05AB1E, 6 bytes

```
ÒD4‹^P

```

Port of *@Dennis*' Jelly answer, so make sure to upvote him!

The probability of odds is therefore also \\$\frac{2}{3}\\$.

Try it online (outputs an infinite list after timing out) or only output the first \\$n\\$ values instead.

**Explanation:**

```
Ò       # Get the prime factors of the (implicit) input-integer, counting multiplicities
 D      # Duplicate this list
  4‹    # Check for each value whether it's smaller than 4 (1 for 2 and 3; 0 otherwise)
    ^   # Bitwise-XOR the two lists at the same indices
        # (2 becomes 3; 3 becomes 2; everything else remains unchanged)
     P  # And take the product of this
        # (after which the result is output implicitly)

```
> 0 votes

# Answer
# x86 32-bit machine code, 12 bytes

```
a8 03 74 05 8d 04 40 0c 02 d1 e8 c3

```

A port of nwellnhof's C answer. Uses the `regparm(1)` calling convention – argument in EAX, result in EAX.

**Try it online! (contains all five functions)**

Assembly:

```
f:
    test al, 3                  # Take the low two bits of the value.
    jz point0                   # Jump if they are both 0.
    lea eax, [eax + eax * 2]    # Triple the value in EAX.
    or al, 2                    # Set the twos bit in EAX.
point0:
    shr eax, 1                  # Shift EAX right by 1 bit.
    ret                         # Return.

```

## The opposite

I also found an 11-byte function with a 1/4 odd probability:

```
0f bc c8 d3 e8 83 f1 01 d3 e0 c3

```

Assembly:

```
fe:
    bsf ecx, eax    # Set ECX to the position of the lowest 1 bit in EAX.
    shr eax, cl     # Shift EAX right by that quantity, removing all ending 0 bits.
    xor ecx, 1      # Invert the lowest bit of ECX.
    shl eax, cl     # Shift EAX left, introducing a modified number of ending 0 bits.
    ret             # Return.

```

# 1st extra challenge: 18 bytes

```
f3 0f b8 c8 d1 e0 0f bd d0 d1 e2 48 29 d0 e2 01 92 c3

```

Implements a function several other answers have used, mapping powers of 2 to even numbers in ascending order and other numbers to odd numbers in ascending order: \\$ f\_1(2^m) = 2m+2 \\$, and for \\$ n \in \[2^m, 2^{m+1})\\$, \\$ f\_1(n) = 2n - 2m - 3\\$.

Assembly:

```
f1:
    popcnt ecx, eax # Set ECX to the number of 1 bits in EAX.
    shl eax, 1      # Shift EAX left by 1, doubling it to 2n.
    bsr edx, eax    # Set EDX to the position of the highest 1 bit in EAX -- m+1.
    shl edx, 1      # Shift EDX left by 1, doubling it to 2m+2.
    dec eax         # Decrement EAX to 2n-1.
    sub eax, edx    # Subtract EDX from EAX, making it 2m-2n-3.
    loop point1     # Decrement ECX and jump if it's nonzero -- if the value was not a power of 2.
    xchg eax, edx   # Exchange EAX and EDX, making EAX 2m+2.
point1:
    ret             # Return.

```

# 2nd extra challenge: 6 bytes

```
83 f0 01 74 fb c3

```

Produces \\$ 1, 3, 2, 5, 4, 7, 6, ... \\$

Assembly:

```
f2:
    xor eax, 1  # Invert the lowest bit of the value.
    jz f2       # Jump back if that makes it 0 (and it will be flipped back to 1).
    ret         # Return.

```

# 3rd extra challenge: 12 bytes

```
0f bd c8 d3 d8 19 d2 d3 c0 29 d0 c3

```

Rearranges the bits of the value by moving the second-highest bit to the bottom. This produces 1 odd, 1 even, 1 odd, 2 even, 2 odd, 4 even, 4 odd, ...

Assembly:

```
f3:
    bsr ecx, eax    # Set ECX to the position of the highest 1 bit in EAX.
    rcr eax, cl     # Rotate EAX and the carry flag CF together left by that quantity.
# Note that the value of CF after BSR is officially undefined,
#  but it is consistently 0 on at least some systems, which is what this function needs.
# This puts the second-highest bit of the value into CF,
#  while the highest bit goes to the bottom position and the lower bits go to the top.
    sbb edx, edx    # Subtract EDX+CF from EDX, making its value -CF.
    rol eax, cl     # Rotate EAX right by the same value, not including CF in the rotation.
# EAX now contains all the bits of the original value except the second-highest,
#  followed by a single 0 bit; if the original value was 1, EAX is now 1.
    sub eax, edx    # Subtract EDX from EAX, replacing the removed bit at the bottom.
    ret             # Return.

```
> 0 votes

# Answer
# Python 2, 39 bytes

```
lambda n:[n/3*4+1,n/3*4+3,n/3*2+2][n%3]

```

Try it online!

outputs :

```
1, 3, 2, 5, 7, 4, 9, 11, 6, 13, 15, 8, 17, 19, 10, 21, 23, 12, 25, 27, 14, 29, 31, 16 ...

```

Odd probability = 2/3

If generating the sequence without taking an inputs is accepted, I also have:

### Python 2, 34 bytes

```
i=3
while 1:print-~i/2,i-2,i,;i+=4

```

Try it online!

Outputs:

```
2 1 3 4 5 7 6 9 11 8 13 15 10 17 19 12 21 23 14 25 27 16 29 31 18 33 35 20 37 39 22 41 ...

```

Odd probability = 2/3
> 0 votes

# Answer
# Mathematical function, 48 bytes

You said "function", so I'm making a function. Takes an input `x` and returns the `x+1`th term. It does mess up when given a non-integer.

```
       x>=1>(x-1) mod 2:x+2
f(x)={ x>=1>x mod 2:x       }
       x=0:1

```

Excluding non-meaningful whitespace.

Here's a graph:

There are always one or two more odd numbers than even ones.
> -1 votes

---
Tags: code-golf, probability-theory, open-ended-function
---


title: Talk interpreter

text:
# Question
Title: Talk interpreter
"Talk" is a baroquified accumulator-based language that is created in response to Dennis's quote on talk.tryitonline.net.

```
Waiting for someone to create an esolang called talk.

```

. The "Talk" language has 4 commands:

* `00` If the accumulator is 0, set the accumulator to 0.
* `01` If the accumulator is 0, set the accumulator to 1.
* `10` If the accumulator is 1, set the accumulator to 0.
* `11` If the accumulator is 1, set the accumulator to 1.

## Input:

* The input can be taken via any acceptable input method by our standard I/O rules.
* There are two inputs, the initial accumulator value and the program. You can merge these two inputs into one input or split your input into valid commands (e.g. taking them as a list; e.g. `[00, 01, 00]`) if you like.

## Output:

* On the end of a command execution, the accumulator is outputted implicitly.

## Rules:

* The input *can* be a single string or character list.
* As this is , the shortest answer, in bytes, wins.
* We take digits or strings/characters.

## Test cases:

```
0 0001111101 -> 1
0 000100 -> 1
0 11001000 -> 0

```

## Leaderboards

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
# Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the *last* number in the header:

```
# Perl, 43 + 2 (-p flag) = 45 bytes

```

You can also make the language name a link which will then show up in the leaderboard snippet:

```
# [><>](http://esolangs.org/wiki/Fish), 121 bytes

```

```
var QUESTION_ID=190819;
var OVERRIDE_USER=8478;
var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;function answersUrl(d){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+d+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(d,e){return"https://api.stackexchange.com/2.2/answers/"+e.join(";")+"/comments?page="+d+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(d){answers.push.apply(answers,d.items),answers_hash=[],answer_ids=[],d.items.forEach(function(e){e.comments=[];var f=+e.share_link.match(/\d+/);answer_ids.push(f),answers_hash[f]=e}),d.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(d){d.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),d.has_more?getComments():more_answers?getAnswers():process()}})}getAnswers();var SCORE_REG=function(){var d=String.raw`h\d`,e=String.raw`\-?\d+\.?\d*`,f=String.raw`[^\n<>]*`,g=String.raw`<s>${f}</s>|<strike>${f}</strike>|<del>${f}</del>`,h=String.raw`[^\n\d<>]*`,j=String.raw`<[^\n<>]+>`;return new RegExp(String.raw`<${d}>`+String.raw`\s*([^\n,]*[^\s,]),.*?`+String.raw`(${e})`+String.raw`(?=`+String.raw`${h}`+String.raw`(?:(?:${g}|${j})${h})*`+String.raw`</${d}>`+String.raw`)`)}(),OVERRIDE_REG=/^Override\s*header:\s*/i;function getAuthorName(d){return d.owner.display_name}function process(){var d=[];answers.forEach(function(n){var o=n.body;n.comments.forEach(function(q){OVERRIDE_REG.test(q.body)&&(o="<h1>"+q.body.replace(OVERRIDE_REG,"")+"</h1>")});var p=o.match(SCORE_REG);p&&d.push({user:getAuthorName(n),size:+p[2],language:p[1],link:n.share_link})}),d.sort(function(n,o){var p=n.size,q=o.size;return p-q});var e={},f=1,g=null,h=1;d.forEach(function(n){n.size!=g&&(h=f),g=n.size,++f;var o=jQuery("#answer-template").html();o=o.replace("{{PLACE}}",h+".").replace("{{NAME}}",n.user).replace("{{LANGUAGE}}",n.language).replace("{{SIZE}}",n.size).replace("{{LINK}}",n.link),o=jQuery(o),jQuery("#answers").append(o);var p=n.language;p=jQuery("<i>"+n.language+"</i>").text().toLowerCase(),e[p]=e[p]||{lang:n.language,user:n.user,size:n.size,link:n.link,uniq:p}});var j=[];for(var k in e)e.hasOwnProperty(k)&&j.push(e[k]);j.sort(function(n,o){return n.uniq>o.uniq?1:n.uniq<o.uniq?-1:0});for(var l=0;l<j.length;++l){var m=jQuery("#language-template").html(),k=j[l];m=m.replace("{{LANGUAGE}}",k.lang).replace("{{NAME}}",k.user).replace("{{SIZE}}",k.size).replace("{{LINK}}",k.link),m=jQuery(m),jQuery("#languages").append(m)}}
```

```
body{text-align:left!important}#answer-list{padding:10px;float:left}#language-list{padding:10px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
 <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="https://cdn.sstatic.net/Sites/codegolf/primary.css?v=f52df912b654"> <div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td><a href="{{LINK}}">{{SIZE}}</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td><a href="{{LINK}}">{{SIZE}}</a></td></tr></tbody> </table>
```

# Answer
# Jelly, 3 bytes

```
y@/

```

Input is a single list: the accumulator, followed by the pairs.

Try it online!

### How it works

The `y` atom performs transliteration; **\[a,b\]**`y`**c** replaces **a** with **b**, so it returns **b** if **a=c** and **c** if **a≠c**.

`y@/` folds/reduces the input by `y` with swapped arguments, performing one transliteration per pair.
> 26 votes

# Answer
# Python 3, 43 bytes

```
lambda s:re.sub("00|11","",s)[-1]
import re

```

Try it online!

The function takes a single string as input, where the first character is the initial state and the rest of the string represents the commands. This solution can be easily ported to other languages that have better support for regular expressions.

The difficult part is to prove the solution yields the correct outcome. To see this, we need a deep analysis of the commands. Firstly, we can see the commands have the following properties:

* **Property (1)**: commands `00` and `11` retain the accumulator state.
* **Property (2)**: commands `01` and `10` make the accumulator state the same as the second bit regardless of its original state.

Therefore, the final accumulator state is:

* **Case 1**: If no `01` or `10` command exists, the final state is the same as the initial state.
* **Case 2**: Otherwise, the last bit of the last `10` or `01` command.

Next we will show the solution yields the correct outcome in both cases. We will prove the statement for the final state `0` and the final state of `1` can be proved analogously. If the final state is `0` the input is in either of the following forms:

* `^0{2k+1}11(11|00)*`

For **Case 1**, the input string `s` must start with `2k+1` 0s, followed by `11` and `00` commands. Eliminating `00`s and `11`s yields a single `0`, which is the final state.
* `.+10{2k+1}11(11|00)*`

For **Case 2**, the input string ends with a `10` command, followed by zero or more `00` and `11` s. This pattern is equivalent to a `1` followed by `2k+1` 0s, and then zero or more `11`s and `00`s. Eliminating `00`s and `11`s leaves behind the last one of the `2k+1` 0s at the end of the string, which represents the final state.

Based on all the above, after eliminating `00`s and `11`s **simultaneously in one single pass** (`01001` is a counter-example if `00` is eliminated in one pass and then `11` in another pass) from the input `s`, the last character is the final state. Hence the correctness of the solution is proved.
> 23 votes

# Answer
# Perl 6, 17 bytes

```
{m/.)>[(.)$0]*$/}

```

Try it online!

Takes advantage of "You can merge these two inputs into one input if you like" by taking input as the accumulator value concatenated with the commands e.g. `1,[00,11]` is `10011`. If this isn't okay, than it's only 5 extra bytes to take it as `f(accumulator, commands)`. Returns a match object that can be coerced to a string.

### Explanation:

```
{                }  # Anonymous code block
 m/             /   # Find the first match from the input
   .)>              # Capture a number
      [     ]*      # Followed by any number of
       (.)$0        # Pairs of identical characters
              $     # Ending the string

```

Basically this works because the `00` and `11` commands do literally nothing, while the `01` and `10` commands just set the accumulator to the second digit of the command. If there are no commands, then it takes the initial value of the accumulator instead.
> 9 votes

# Answer
# Zsh, 33 bytes

The character list is passed as arguments, the initial value of the accumulator is passed as stdin.

```
read a
for x y;a=$[x^a?a:y]
<<<$a

```

Try it online!

---

**39 bytes**: If the commands must be a single string

Input is `accumulator` `commands` as arguments.

```
for x y (${(s::)2})1=$[x^$1?$1:y]
<<<$1

```

Try it online!

---

For fun, here's a **50 byte** recursive one-liner (TIO):

```
<<<${${2+`f $[$1^${2[1]}?$1:${2[2]}] ${2:2}`}:-$1}

```
> 7 votes

# Answer
# Python 3, 52 bytes

```
f=lambda a,s:s and f([s[1],a][s[0]==s[1]],s[2:])or a

```

Try it online!

*Fixed inconsistent return type thanks to Chas Brown*

Takes input as two strings; the accumulator and the code.
> 6 votes

# Answer
# Brachylog, ~~11~~ 9 bytes

```
tġ₂≠ˢtt|h

```

Try it online!

Since it's been long enough that I've been able to forget the notion of printing the accumulator after each command, I've formulated a significantly less naïve solution with some inspiration from Jo King's Perl answer.

```
       |     The output is
     tt      the last element of the last element of
t            the last element of the input
 ġ₂          split into length-2 slices
   ≠ˢ        with equal pairs removed.
       |     If there is no such element, the input
        h    's first element is the output.

```

Old solution:

# Brachylog, ~~18~~ 16 bytes

```
ġ₂ᵗc{th~h?tt|h}ˡ

```

Try it online!

-2 bytes from changing the input format.
> 5 votes

# Answer
# JavaScript (ES6), 27 bytes

Takes input as `(a)(code)`, where *code* is a is list of 2-bit integers.

```
a=>c=>c.map(x=>a^=x==a+1)|a

```

Try it online!

---

# JavaScript (ES6),  ~~47~~  40 bytes

Takes input as `(a)(code)`, where *code* is a string.

```
a=>c=>c.replace(/../g,x=>a^=x%4==a+1)&&a

```

Try it online!

### How?

All possible cases are summarized below. The only two cases where we need to toggle the accumulator are \\$(a=0,x=01\_2)\\$ and \\$(a=1,x=10\_2)\\$.

```
  a | x (bin) | int(x) % 4 | a + 1 | equal?
----+---------+------------+-------+--------
  0 |   "00"  |  0 % 4 = 0 |   1   |   N
  1 |   "00"  |  0 % 4 = 0 |   2   |   N
  0 |   "01"  |  1 % 4 = 1 |   1   |   Y
  1 |   "01"  |  1 % 4 = 1 |   2   |   N
  0 |   "10"  | 10 % 4 = 2 |   1   |   N
  1 |   "10"  | 10 % 4 = 2 |   2   |   Y
  0 |   "11"  | 11 % 4 = 3 |   1   |   N
  1 |   "11"  | 11 % 4 = 3 |   2   |   N

```
> 5 votes

# Answer
# sed -E, ~~26~~ 19 bytes

*A whopping **-7 bytes** from @Cowsquack by realizing removing all pairs works as well.*

```
s/(.)\1//g
s/.*\B//

```

Takes input concatenated together on stdin. Inspired by Jo King's Perl answer. ~~Strip trailing pairs~~ Remove all pairs, then get last digit.

~~Try it online!~~ Try it online!
> 4 votes

# Answer
# Retina 0.8.2, ~~18~~ 11 bytes

```
(.)\1

!`.$

```

Try it online! Link includes test cases. Takes input concatenated. Saved 6 bytes thanks to @CowsQuack for pointing out that removing all doubled characters and then taking the last remaining character works, although in fact the port of @JoKing's original answer could have been golfed by 3 bytes even without that trick.
> 4 votes

# Answer
# Haskell, 29 bytes

Defines an unnamed function on the first line with type `(Foldable t, Eq b) => b -> t [b] -> b`. For the purposes of this code golf, we can instantiate it as `Char -> [String] -> Char` where the first argument is the accumulator and the second is a list of string with each string being a single command.

```
foldl(#)
a#[x,y]|a==x=y|1>0=a

```

Try it online!
> 4 votes

# Answer
# Python 3, 38 bytes

```
lambda l:[y for*x,y in l if[y]!=x][-1]

```

Try it online!

Based on Joel's solution. Takes input as a list of the initial accumulator value (length-one string) followed by the commands (length-two strings). Finds the last command with two unequal values, and outputs its second character.

To make this fall through to the initial accumulator value when there are no such commands, we make it so that the single-char initial value string passes the test. We do so by checking if a singleton list with the last character is unequal to a list of all preceding characters, which is passed by any length-one string or length-two string with two different characters.
> 4 votes

# Answer
# Perl 5 `-p`, ~~37~~ 33 bytes

```
$\=<>;s/(.)(.)/$\=$2if$\==$1/ge}{

```

Try it online!

Input is two lines: first line is the command sequence, second is the accumulator.
> 3 votes

# Answer
# Jelly, ~~8~~ 6 bytes

```
EÐḟṪṪo

```

Try it online!

-2 bytes thanks to Nick Kennedy informing me of a rules change. (His proposed golf, `EÐḟFȯṪ`, seems somewhat more clever but has the same length as my previous solution minus `s2`.) The input format now takes the commands as a list of two-character strings, but the testing footer translates from the old format for convenience.

Translated from my newer Brachylog solution.

Old version:

# Jelly, 13 bytes

```
ḢẎ⁼⁹a⁸o
s2ç@ƒ

```

Try it online!

I'm not 100% sure this is correct, but it succeeds on all three test cases. Takes the commands as the left argument and the initial accumulator as the right argument.
> 3 votes

# Answer
# Python 2, 56 bytes

```
f=lambda a,c:f([a,1,0,a][int(c[:2],2)],c[2:])if c else a

```

Try it online!
> 3 votes

# Answer
# APL (Dyalog Unicode), 16 bytes

```
(+⌷13⍴0 1,9/⊢)/⌽

```

A tacit function which takes initial accumulator value and the program as a single integer list.

Maps the relevant sums of instruction and accumulator to an array.

Table: `(a→accumulator, i→instruction)`

```
a  i a+i result
00 0 0   0
01 0 1   1
10 1 11  0
11 1 12  1

```

All other cases return the same value, so they are assigned to the preexisting value of `a`.

Try it online!

### Explanation

```
(+⌷13⍴0 1,9/⊢)/⌽ accumulator→a
              /⌽ reduce the reversed array using th following function: (reducing happens from the right)
          9/⊢)   replicate a 9 times
   13⍴0 1,       concatenate with (0,1) and expand to 13 elements → (0 1 a a a a a a a a a 0 1)
(+⌷              sum first two elements and find element at that index in the array

```

### Solution which accepts a string

```
{{(13⍴0 1,9/⍺)[⍺+⍵]}/⌽(⍎¨((⍴⍵)⍴1 0)⊂('0',⍵))}

```

It was pretty ambiguous how the input was supposed to be taken, so I decided I'd leave this one in as well.

This was the original dfn, which was golfed down using Adám and Bubbler's advice.
> 3 votes

# Answer
# Regex (JS flavor), 32 bytes

```
^(0(..)*01|1((..)*01)?)(00|11)*$

```

Try it online!

Matches if output is 1, doesn't if output is 0. Global and multiline flags enabled in link to verify multiple test cases at once, but not necessary for solution. Did I format this submission correctly?
> 3 votes

# Answer
# Python, 111 bytes

```
def f(a,b):
    c=a
    for i in range(0,len(b)-1,2):
        c=(not b[i])*(c or b[i] or b[i+1]) or c*b[i]*b[i+1]
    return c

```

Ungolfed. EDIT: AHHH Someone beat me to it!
> 2 votes

# Answer
# Keg, `-ir`, 16 bytes

```
"(!;½|':"=['_"|_

```

Try it online!

## Explained:

1. Takes the implicit input and right shifts the accumulators value to the bottom
2. Repeat the following (length of stack - 1 divided by 2) times

2.1. Shift the accumulator back to the top

2.2. Compare for equality with the first part of the command

2.2.1. If true, replace the accumulator, otherwise pop the replacement

Input is taken as the initial acc value concatenated with the source. E.g.

```
010011000

```
* First char is acc value
* Rest is program
> 2 votes

# Answer
# Haskell, 36 bytes

```
f(x:y:s)=f s.last.(:[y|x/=y])
f _=id

```

Try it online!

Takes input as `f(string)(char)` where the character is the accumulator and the string is the list of commands.
> 2 votes

# Answer
# 05AB1E, 3 bytes

```
ø`:

```

Try it online!

Zip, dump on the stack, replace.
> 2 votes

# Answer
# Stax, 3 bytes

```
F|t

```

Run and debug it

For each instruction, perform character translation.
> 2 votes

# Answer
# CJam, 8 bytes

```
{{)er}/}

```

Try it online!

Takes input on the stack in the form of `"0" ["00" "01" "11" "11" "01"]`. Does string replacement using every command.
> 2 votes

# Answer
# Headass, 22 bytes

```
U[{N-()]PNE:U(])U[:U;}

```

Try It Online!

```
U[{N-()]PNE:U(])U[:U;} full program

U[                     save initial state of accumulator to storage register
  {        :         } while
   N-()                input remains
            U(])    ;    if input == accumulator state
                U[         set accumulator to next input
                  :      else
                   U       discard next input
       ]P              print final state of accumulator
         NE            go to code block 1
                       block does not exist, exits with error

```

There is room for golfing maybe if I can avoid storing anything in the comparison register (i.e. having it remain 0 for the entirety of the program and never using `(`), but it might not be possible.
> 2 votes

# Answer
# Regex (any flavor), 15 bytes

```
(^|0)1(00|11)*$

```

Try it on regex101!

It was pointed out before that the problem can be simplified:

* `00` and `11` are no-ops. `01` unconditionally sets the value to 1 while `10` sets to 0.
* The output is 1 if and only if the input is 1 and the entire code is no-op or the last non-no-op command is `01`.

The regex precisely does the job: `(00|11)*$` after discarding no-ops at the end, the last thing found is `(^|0)1` the input 1 or a `01` command.

`1(00|11)*$` does not work because the 1 may be part of another no-op command `11`.
> 2 votes

# Answer
# Bash, ~~58~~ 40 bytes

Add one byte for a full program: change `f` to `$0`.

```
(($1=$2-a?a:$3,1))&&f $1 ${@:4}||echo $1

```

~~58 bytes~~ Try it online!

The ternary will return false when `$1` is set to `0`, but the `,1` at the end ensures the whole `((expression))` will return true, *except* a syntax error.

When all the arguments are consumed, a syntax error happens and the recursion ends.

---
> 1 votes

# Answer
# Charcoal, 16 bytes

```
Ｆ⪪η²Ｆ⁼θ§ι⁰≔§ι¹θθ

```

Try it online! Link is to verbose version of code. Takes separate arguments. Explanation:

```
Ｆ⪪η²

```

Split the instructions into pairs of digits and loop over them.

```
Ｆ⁼θ§ι⁰

```

If the accumulator is equal to the first digit...

```
≔§ι¹θ

```

... then assign the second digit to it.

```
θ

```

Print the accumulator at the end of the loop.
> 1 votes

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

```
!dh2Ol4$Ys0)

```

Takes the input as a 2-column matrix where each row is a command, and a number

Try it online! Or verify all test cases
> 1 votes

# Answer
# Jelly, 7 bytes

```
fØ½Ḃ⁹;Ṫ

```

A dyadic Link accepting the program as a list of integers on the left and the initial accumulator on the right which yields an integer.

**Try it online!** Or see a test-suite
> 1 votes

# Answer
# C (gcc), ~~45~~ 41 bytes

```
f(a,i)char*i;{a=*i?f(a^*i?a:i[1],i+2):a;}

```

Try it online!

4 bytes shaved off thanks to @ErikF!
> 1 votes

# Answer
# PHP, 38 bytes

```
<?=strtr($argn,['00'=>'',11=>''])[-1];

```

Try it online!

Basically port of Jo King's idea.
> 1 votes

# Answer
# Runic Enchantments, 28 bytes

```
/~@/i~/i<
/=?/~iR:l}i{l1-=?!

```

Try it online!

Takes input as a series of space separated bytes (Runic does not understand lists). The first byte is the initial state and every other byte is the program. No validation is performed (i.e. it assumes only valid programs are given as input and it doesn't care what value is used to represent `0` and `1`).
> 1 votes

# Answer
# Ruby, 33 bytes

```
->a,s{s[/(00|11)*$/]="";s[-1]||a}

```

Try it online!
> 1 votes

# Answer
# x86 Assembly, 33 Bytes

Takes the initial accumulator state in `CL` (integer `0` or `1`) and the address of the commands as a zero-terminated ASCII String in `ESI`. Leaves the final accumulator state in `CL`.

Point the call instruction at offset `0x1B` (label `interpret` in the Explanation).

```
3C 30 74 03 B0 01 C3 30 C0 C3 E8 F1 FF FF FF 38
C8 AC 75 07 E8 E7 FF FF FF 88 C1 AC 84 C0 75 EA
C3

```

**Explanation** (Using Intel Syntax):

```
; function to convert ASCII '1'/'0' into 0 or 1 int values (from AL to AL)
ctob:
        CMP AL, 0x30 ; '0'
        JE .zero
        MOV AL, 1
        RET
        .zero:
        XOR AL, AL
        RET

; interpreting function
        interp_lp:
                CALL ctob     ; convert to number
                CMP AL, CL    ; compare to current accumulator
                LODSB         ; read the next character of the string
                              ; this doesn't affect any flags and we need to do
                              ; it in both cases anyway
                JNE interpret ; if AL != CL (from above, not the new value of AL), skip forward
                CALL ctob     ; convert AL to number
                MOV CL, AL    ; store AL in CL
interpret:      LODSB         ; read the next character of the string
                TEST AL, AL   ; check if it is a zero byte
                JNZ interp_lp ; if not, jump back into the loop
        RET

```
> 1 votes

# Answer
# APL(Dyalog Unicode), 9 bytes <sup>SBCS</sup>

```
1∊11+\⍤|⌽

```

Try it on APLgolf!

Input format is the same as Razetime's.

```
1∊11+\⍤|⌽
        ⌽  Reverse the input list
  11   |    Modulo 11 (change 11 to 0)
            Now the program outputs 1 iff the list starts with 0 0 ... 0 1
    +\⍤     Cumulative sum
1∊          Test if it contains a 1

```

The proof of the statement

> a list starts with 0 0 ... 0 1 \<=\> its cumulative sum contains 1

is left as an exercise to the reader.
> 1 votes

# Answer
# C (clang), ~~68~~ 62 bytes

```
t(s,e,a)char*s,*e;{for(;s<e;++s)a=*s++-48^a?a:*s-48;puts(&a);}

```

Try it online!

Takes a pointer to the start of the source string, a pointer to the end of the source string (start + strlen(start)), and the initial accumulator value.

Old version (prints ASCII 48/49 for 0/1):

```
t(s,e,a)char*s,*e;{for(;s<e;++s)a=*s++-48^a?a:*s-48;putchar(a+48);}

```
> 0 votes

# Answer
# Crystal, 46 bytes

With commands in an `Array(Tuple(Int32,Int32))`, such as `[{0,0}, {0,1}, {0,0}]`.

`def f(s,i);i.map{|c,v|s+=~(s^c)&(s^v)%2};s;end`

Try it online!

It's pretty simple to understand in a more readable form:

```
def f(state, instructions)
  instructions.map do |check, value|
    state += ~(state ^ check) & (state ^ value) % 2
  end
  state
end

```

The function loops through each command, automatically unpacking the tuple values into `c` and `v`. It then sets the `state` by the formula

```
state = state + NOT(state XOR check) AND (state XOR value) mod 2

```

which I arrived at mostly by trial and error. Once all commands have been processed, it returns the state value.
> 0 votes

# Answer
# Java (JDK), 38 bytes

```
a->p->p.reduce(a,(s,c)->c<1|c>2?s:c%2)

```

Try it online!

The inputs are an `int` and an `IntStream` of `0`, `1`, `2` or `3`, which correspond to `00`, `01`, `10`, `11` from binary.
> 0 votes

---
Tags: code-golf, interpreter
---