title: Is it a prefix normal word?

text:
# Question
Title: Is it a prefix normal word?
Prefix normal words arise in the context of binary jumbled pattern matching. A binary word \\$w\\$ consisting of \\$0\\$s and \\$1\\$s is said to be *prefix normal* * if, among all of its substrings, none contains more \\$1\\$s than the prefix of \\$w\\$ of the same length does. In other words, if \\$w\\$ contains \\$n\\$ \\$1\\$s then it is prefix normal if, for all \\$m\le n\\$, the shortest (or equal shortest) substring containing \\$m\\$ \\$1\\$s is a prefix.

For example, \\$w=\color{red}{11010}\color{blue}{11011}00100\\$ is not prefix normal because it has a substring of length 5 (highlighted in blue) that contains four \\$1\\$s, whereas its prefix of length 5 (red) only contains three \\$1\\$s. If we flip the first \\$0\\$ to \\$1\\$, however, then the resulting word (\\$111101101100100\\$) is prefix normal.

### Task

Your task in this challenge is to write a program or function that decides whether a binary word is prefix normal.

You may take input in any sensible format (e.g. string, numeric, list of characters/digits), which extends to using any pair of characters/digits instead of \\$0\\$ and \\$1\\$ if you wish.

Output/return a consistent value for every input that is prefix normal and another consistent value for every input that is not.

### Test cases

**Prefix normal**

```
00000
1101010110
111101101100100
11101010110110011000
1110010110100111001000011

```

**Not prefix normal**

```
00001
1011011000
110101101100100
11010100001100001101
1110100100110101010010111

```

---

* Strictly, *prefix normal with respect to \\$1\\$*.

# Answer
# Jelly, ~~9~~ 7 bytes

```
ṡJ§Ṁ€⁼Ä

```

Try It Online!

-2 bytes thanks to Unrelated String

```
ṡJ§Ṁ€⁼Ä  Main Link
ṡ        Take overlapping slices of length(s)
 J       [1, 2, ..., length]
  §      Take the sum of each slice of each length
   Ṁ€    Is the maximum sum for each length
     ⁼   Equal to
      Ä  The cumulative sum of the original list?

```
> 7 votes

# Answer
# Wolfram Language (Mathematica), ~~54...44~~ 41 bytes

```
(l=Most@l+#-(t={##2})&@@t)&/@(t=l=#)0&

```

Try it online!

is `VectorGreaterEqual`.

```
(l=Most@l+#-(t={##2})&@@t)&/@(t=l=#)        get all prefix differences by:
                             (t=l=#)          l: difference list, t: input list
                           /@                 over input length:
(l=Most@l                )&                     drop last element of l
         +#-   {##2} &@@t                       foreach, add next in prefix, subtract next in substring
                                                      e.g. (a+b+c)-(b+c+d) -> (a+b+c)-(b+c+d)+d-e
            (t=     )                           shift t left
                                    0      all nonnegative?

```

\*strictly speaking, each element of `l` is also offset by corresponding input element . I suspect this doesn't matter - a brute force test of strings up to length 17 showed no differences - but I don't have a proof as to why.
If it does make a difference, +1 byte using `(l=Most@l+#-{t=##2}&@t)&/@(l=0{t=##})0&` instead. Try it online!
> 5 votes

# Answer
# Haskell, 57 bytes

```
g x=x!x
p!s=p==[]||sum p>=sum s&&init p!tail s&&g(init p)

```

Try it online!

---

# Haskell, 66 bytes

A bit longer, but actually runs in reasonable time.

```
g x|k<-[1..length x]=and[h x>=h(drop n x)|h<-(sum.).take<$>k,n<-k]

```

Try it online!
> 5 votes

# Answer
# JavaScript (ES6), 57 bytes

Expects an array of binary digits. Returns *false* for prefix normal, or *true* for not prefix normal.

```
a=>a.map(v=>a=v-~a).some((p,i,a)=>a.some(q=>q-a[~i--]>p))

```

Try it online!

### How?

We first compute the cumulative sums of the incremented input values:

```
a.map(v => a = v - ~a)

```

(Using `a = v - ~a` allows us to re-use `a[]` to compute the sum, which is two bytes shorter than allocating a specific variable. That's the only reason why the values are incremented.)

For instance:

```
   1, 0, 1, 1, 0, 1, 1, 0, 0, 0
=> 2, 1, 2, 2, 1, 2, 2, 1, 1, 1
=> 2, 3, 5, 7, 8,10,12,13,14,15

```

We then test whether there's some pair \\$(i,j)\\$ with \\$j\>i\\$ such that \\$a\_j-a\_{j-i-1}\>a\_i\\$.

```
.some((p, i, a) => a.some(q => q - a[~i--] > p))
//                             ^      ^      ^
//                           a[j]  a[j-i-1]  a[i]

```
> 5 votes

# Answer
# Jelly, ~~9~~ 8 bytes

```
ẆẈṀƙ§Ɗ⁼Ä

```

Try it online!

It feels like something less naive should be shorter yet, but I haven't had any luck.

```
Ẇ           Get every substring of the input.
    §       Sum each substring,
   ƙ Ɗ      group the sums by
 Ẉ          the lengths of the corresponding substrings,
  Ṁ         and take the largest element of each group.
      ⁼Ä    Is the resulting list equal to the cumulative sums of the input?

```
> 4 votes

# Answer
# Risky, 31 bytes

```
*00_{?*_1_+!?{_?+0_{?*_1_+_?*_1__[___{_0*__1*_1:____{_0{__1*_1

```

Input is a single argument which is a list of 0's and 1's; output is 1 if prefix normal, 0 if not. Try it online!

### Explanation

This is a bit long, so I'll explain it in two halves.

```
00_{?*_1_+!?{_?+0_{?*_1_+_?*_1
    ?                           Input list
   {                            List of all sublists
     *_1                        Repeat once (no-op)
  _                             Same value (no-op)
        _                       Map this function to each of the sublists
                                (first arg is each sublist, second arg is original input):
          !?                     Length of first arg
            {                    Take prefix of that length from
             _?                  Second arg
         +                       Sum
 0                              Transpose (adds a level of nesting to a flat list)
               +                Concatenate that list with the following:
                  {?             List of all sublists of input list
                    *_1          Repeat once (no-op)
                 _               Same value (no-op)
                       _         Map this function to each sublist:
                         _?       First arg
                           *_1    Repeat 1 time (no-op)
                        +         Sum
0                               Transpose

```

At this point, we have a list of pairs \\$(n\_l^0, n\_l^i)\\$, where \\$n\_l^i\\$ is the number of ones in the \\$i^{th}\\$ sublist of length \\$l\\$ and \\$n\_l^0\\$ is the number of ones in the first sublist of length \\$l\\$. We now want to check if for every pair, \\$n\_l^0 \geq n\_l^i\\$. Equivalently, \\$min(n\_l^0, n\_l^i) = n\_l^i\\$.

```
__[___{_0*__1*_1:____{_0{__1*_1
_                                Map this function to each pair (first arg is each pair,
                                 second arg is original input):
    __                            List of both args
      {_0                         Get 0th element (the pair)
   _                              Same value (no-op)
         *__1*_1                  Repeat 1 time (no-op)
  [                               Minimum
                :                 Equals
                   __              List of both args
                     {_0           Get 0th element (the pair)
                  _                Same value (no-op)
                        {          Get element of the pair at index
                         __1*_1    1 (the second element)
                 _                 Same value (no-op)
 _                                Same value (no-op)

```

We now have a list containing 0 for every sublist with more ones than the equal-length prefix, and 1 for every other sublist. The `*` at the beginning of the code takes the product of this list, yielding 0 for inputs with any such substrings and 1 for inputs without any.
> 4 votes

# Answer
# Retina 0.8.2, 49 bytes

```
((1)|0)+(?<=(?!(?>(?<-1>(?<-2>1)|0)*)(?(2)^))^.*)

```

Try it online! Outputs `0` for prefix normal, `1` for not normal. Explanation:

```
((1)|0)+

```

Match some `1`s and `0`s, keeping count of the `1`s and the total number of digits (very slightly golfier as we need a group for the `+`), ...

```
(?<=...^.*)

```

... then, at the beginning of the string, ...

```
(?>(?<-1>(?<-2>1)|0)*)

```

... try to consume all of the `1`s, matching up to the same number of digits...

```
(?!...(?(2)^))

```

... and fail if there were enough `1`s, showing that the prefix is normal.

Note that if there are two disjoint substrings with too many `1`s then I think the substring containing both substrings will also have too many `1`s and will therefore be found first, but I can't prove that.
> 3 votes

# Answer
# 05AB1E, 9 bytes

```
Œε∍OyO@}P

```

Input as a list of 0s/1s.

Try it online or verify all test cases.

**Explanation:**

```
Œ        # Get all sublists of the (implicit) input-list
 ε       # Map over each sublist:
  ∍      #  Shorten the (implicit) input-list to a length equal to this sublist-length
   O     #  Sum this prefix
    yO   #  Sum the sublist as well
      @  #  Check that the prefix-sum is larger than or equal to the sublist-sum
 }P      # After the map: pop and take the product to check if all were truthy
         # (after which it is output implicitly as result)

```
> 3 votes

# Answer
# APL (Dyalog Unicode), 14 bytes

```
∧/∘∊+\≥⍳∘≢+/¨⊂

```

Try it online!

A tacit function taking a vector of `0`'s and `1`'s

The input vector enclosed in a singleton list.
`⍳∘≢` indices of the input (1 .. length input)
`¨` For each of the numbers on the left and the input vector on the right:
`+/` sums of all sublists of the right argument of the length given by the left argument.
`+\` sums of prefixes of the input.
for each prefix sum, is it larger or equal than each of the sublist sum of sublists of the same size.
flatten nested list.
`∧/` reduce with boolean *and*.

Example with input `1 0 0 1 1`:

```
┌──┬─────────┬──────────┐
│+\│⍳∘≢+/¨⊂  │+\≥⍳∘≢+/¨⊂│
├──┼─────────┼──────────┤
│1 │1 0 0 1 1│1 1 1 1 1 │
├──┼─────────┼──────────┤
│1 │1 0 1 2  │1 1 1 0   │
├──┼─────────┼──────────┤
│1 │1 1 2    │1 1 0     │
├──┼─────────┼──────────┤
│2 │2 2      │1 1       │
├──┼─────────┼──────────┤
│3 │3        │1         │
└──┴─────────┴──────────┘

```
> 2 votes

# Answer
# Ruby, ~~70~~ 60 bytes

```
->s,r=0..s.size{r.any?{|i|r.any?{|j|s[j,i].sum>s[0,i].sum}}}

```

Try it online!

* Saved 9 Bytes thanks to @Dingus suggestions !
any? replaces first map
We reuse entire range L=0..s.size instead of just the length
* Saved another 1 again by @Dingus
Compares directly the sums of prefix and current range being checked
* Takes an array `s` of 0/1 and return `false` if it is prefix normal, `true` if not.

```
(1..L=s.size).map{|i|  - every length by*
(X= ... )        - we save in X:
  (0..L).map{|j|   * every index: all substrings of same length
  s[j,i].sum}      * sum 1's in slice of length i at j
.max>X[0]     - any > of 1st element?
}.any?}          - any true?

```
> 2 votes

# Answer
# Scala, 74 bytes

```
s=>1 to s.size forall(l=>s.sliding(l).map(_.sum).forall(_<=s.take(l).sum))

```

Try it online!

Strategy is as follows:

* for all possible prefix lengths (`1 to s.size forall{...}`) check the following
    + compute the number of 1's within each sliding window of current prefix length (`s.sliding(l).map(_.sum)`)
    + check whether all these sliding windows contain no more 1's than the first window/initial prefix (`.forall(_<=s.take(l).sum)`)
> 2 votes

# Answer
# Charcoal, ~~19~~ 18 bytes

```
⊙θΦκ‹Σ…θ⁻⊕κλΣ✂θλ⊕κ

```

Try it online! Link is to verbose version of code. Outputs `-` for not normal, nothing for prefix normal. Explanation:

```
 θ                  Input string
⊙ Φκ                Any substring satisfies
      …θ⁻⊕κλ        Leading prefix
     Σ              Sum of digits
    ‹               Less than
             ✂θλ⊕κ  Current substring
            Σ       Sum of digits
                   Implicitly print

```
> 1 votes

# Answer
# , 92 bytes

Or **\>=4.1, 78 bytes** by replacing two `function` appearances with `\`s.

```
function(s,n=sum(s|1)){for(i in 1:n)F=F|which.max(sapply(0:n,function(j)sum(s[1:i+j])))-1;F}

```

Try it online!

Takes a vector of integers. Outputs `FALSE` for prefix normal and `TRUE` for non-prefix normal word.

---

Solution shorter in \>=4.1:

# , 98 bytes

Or **\>=4.1, 77 bytes** by replacing three `function` appearances with `\`s.

```
function(s,n=sum(s|1),g=sapply)any(g(1:n,function(i)which.max(g(0:n,function(j)sum(s[1:i+j])))-1))

```

Try it online!
> 1 votes

# Answer
# Python 3, ~~91~~ 79 bytes

```
lambda s:any(sum(s[:i-j])<sum(s[j:i])for i in range(len(s)+1)for j in range(i))

```

Take as input a list of integers.

Return `False` for prefix normal and `True` for prefix not normal

Thanks `@UnrelatedString` for -12 bytes using list of integers instead of strings

Try it online!
> 1 votes

# Answer
# Core Maude, 186 bytes

```
mod P is pr NAT-LIST . var L P F X Y Z :[Nat]. ops n c : Nat ~> Nat . ceq
n(L)= F if P X 2 Y F Z := L 2 L /\ size(P)= size(F)/\ c(F)> c(P). eq c(X 1 Y)=
s c(X Y). eq c(L)= 0[owise]. endm

```

The answer is obtained by reducing the `n` function with the input bitstring as a Maude `NatList` of `0`s and `1`s. If the term is irreducible (result is an “error expression” of kind `[NatList]`), then the bitstring is prefix normal, otherwise (result of sort `NeNatList`, `Nat`, etc.) it is not.

### Example Session

```
             \||||||||||||||||||/
           --- Welcome to Maude ---
             /||||||||||||||||||\
         Maude 3.1 built: Oct 12 2020 20:12:31
         Copyright 1997-2020 SRI International
           Sun Oct 17 22:18:44 2021
Maude> mod P is pr NAT-LIST . var L P F X Y Z :[Nat]. ops n c : Nat ~> Nat . ceq
> n(L)= F if P X 2 Y F Z := L 2 L /\ size(P)= size(F)/\ c(F)> c(P). eq c(X 1 Y)=
> s c(X Y). eq c(L)= 0[owise]. endm
Maude> red n(0 0 0 0) .
result [NatList]: n(0 0 0 0)
Maude> red n(1 1 0 1 0 1 0 1 1 0) .
result [NatList]: n(1 1 0 1 0 1 0 1 1 0)
Maude> red n(1 1 1 1 0 1 1 0 1 1 0 0 1 0 0) .
result [NatList]: n(1 1 1 1 0 1 1 0 1 1 0 0 1 0 0)
Maude> red n(1 1 1 0 1 0 1 0 1 1 0 1 1 0 0 1 1 0 0 0) .
result [NatList]: n(1 1 1 0 1 0 1 0 1 1 0 1 1 0 0 1 1 0 0 0)
Maude> red n(1 1 1 0 0 1 0 1 1 0 1 0 0 1 1 1 0 0 1 0 0 0 0 1 1) .
result [NatList]: n(1 1 1 0 0 1 0 1 1 0 1 0 0 1 1 1 0 0 1 0 0 0 0 1 1)
Maude> red n(0 0 0 0 1) .
result NzNat: 1
Maude> red n(1 0 1 1 0 1 1 0 0 0) .
result NeNatList: 1 1
Maude> red n(1 1 0 1 0 1 1 0 1 1 0 0 1 0 0) .
result NeNatList: 1 1 0 1 1
Maude> red n(1 1 0 1 0 1 0 0 0 0 1 1 0 0 0 0 1 1 0 1) .
result NeNatList: 1 1 0 0 0 0 1 1 0 1
Maude> red n(1 1 1 0 1 0 0 1 0 0 1 1 0 1 0 1 0 1 0 0 1 0 1 1 1) .
result NeNatList: 1 0 1 0 0 1 0 1 1 1
Maude> quit
Bye.

```

### Ungolfed

```
mod P is
    pr NAT-LIST .
    var L P F X Y Z : [Nat] .
    ops n c : Nat ~> Nat .
    ceq n(L) = F if P X 2 Y F Z := L 2 L /\ size(P) = size(F) /\ c(F) > c(P) .
    eq c(X 1 Y) = s c(X Y) .
    eq c(L) = 0 [owise] .
endm

```

We use Maude's strong pattern matching and conditional equations to try every possible prefix and sublist. The `c` function counts the number of `1`s in a list.

Interesting note: If the input term is reducible, the result will be a witness sublist with more `1`s than the prefix of the same length. It did not cost any extra bytes to do so.

The `[owise]` attribute does not *seem* to be needed in the current Maude 3.1 interpreter (the interpreter seems to prefer earlier equations over later ones), but Maude's definition of an “admissible functional module” requires it. Otherwise we could save 6 bytes by omitting it.
> 1 votes

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


title: Calculate A190810

text:
# Question
Title: Calculate A190810
Your task is pretty simple, calculate the n-th element of A190810.

Elements of A190810 are calculated according to these rules:

1. The first element is 1
2. The sequence is increasing
3. If `x` occurs in the sequence, then `2x+1` and `3x-1` also do

You can use 1-based or 0-based indexing, but if you use 0-based indexing, please say it in the answer.

Test cases

```
a(1) = 1
a(2) = 2
a(3) = 3
a(4) = 5
a(5) = 7
a(10) = 17
a(20) = 50
a(30) = 95
a(55) = 255

```

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

# Answer
# Jelly, 16 bytes

```
×3’;Ḥ‘$;
1Ç¡ṢQ³ị

```

*Very* inefficient. Try it online!

### How it works

```
1Ç¡ṢQ³ị   Main link. Argument: n (integer)

1         Set the return value to 1.
 Ç¡       Execute the helper link n times.
   Ṣ      Sort the resulting array.
    Q     Unique; deduplicate the sorted array.
     ³ị   Retrieve its n-th element.

×3’;Ḥ‘$;  Helper link. Argument: A (array)

×3        Multiply all elements of A by 3.
  ’       Decrement the resulting products.
      $   Combine the two links to the left into a monadic chain.
    Ḥ     Unhalve; multiply all elements of A by 2.
     ‘    Increment the resulting products.
   ;      Concatenate 3A-1 and 2A+1.
       ;  Concatenate the result with A.

```
> 10 votes

# Answer
# Python 2, ~~88~~ ~~83~~ 72 bytes

You may want to read the programs in this answer in reverse order...

Slower and shorter still, thanks to Dennis:

```
L=1,;exec'L+=2*L[0]+1,3*L[0]-1;L=sorted(set(L))[1:];'*input()
print L[0]

```

**Try it online**

---

This doesn't run as fast, but is shorter (**83 bytes**.) By sorting and removing duplicates each iteration, as well as removing the first element, I remove the need for an index into the list. The result is simply the first element after `n` iterations.

I may have out-golfed Dennis. :D

```
L=[1]
n=input()
while n:L+=[2*L[0]+1,3*L[0]-1];n-=1;L=sorted(set(L))[1:]
print L[0]

```

**Try it online**

---

This version below (**88 bytes**) runs really fast, finding the 500000th element in about two seconds.

It's pretty simple. Compute elements of the list until there are three times more elements than `n`, since every element added may add at most 2 more unique elements. Then remove duplicates, sort, and print the `n`th element (zero-indexed.)

```
L=[1]
i=0
n=input()
while len(L)<3*n:L+=[2*L[i]+1,3*L[i]-1];i+=1
print sorted(set(L))[n]

```

**Try it online**
> 14 votes

# Answer
# Python 2, 59 bytes

```
t={1}
exec'm=min(t);t=t-{m}|{2*m+1,3*m-1};'*input()
print m

```

Based on @mbomb007's Python answer. Test it on Ideone.
> 8 votes

# Answer
## Haskell, ~~76~~ ~~73~~ 69 bytes

```
a#b=mod a b<1&&t(div a b)
t x=x<2||(x-1)#2||(x+1)#3
(filter t[1..]!!)

```

Uses a 0-based index. Usage example: `(filter t[1..]!!) 54` -\> `255`.

Instead of building the list by repeatedly inserting `2x+1` and `3x-1` as seen in most other answers, I go through all integers and check if they can reduced to `1` by repeatedly applying `(x-1) / 2` or `(x+1) / 3` if divisible.
> 8 votes

# Answer
# Haskell, ~~77~~ 74 bytes

```
import Data.List
i=insert
f(x:y)=x:f(i(2*x+1)$i(3*x-1)y)
a=(!!)(nub$f[1])

```

This provides a function `a` for the n-th entry. It's zero indexed. Alternatively, `a=nub$f[1]` will create the whole list (lazily).

It's a list-variant of Reinhard Zumkeller's `Set` code.
> 7 votes

# Answer
# Pyth, ~~20~~ 19 bytes

```
hutS{+G,hyhGt*3hGQ0

```

Try it online. Test suite.

Uses zero-based indexing.
> 6 votes

# Answer
# Python 2, ~~88~~ 84 bytes

```
g=lambda k:g(k%2*k/2)|g(k%3/2*-~k/3)if k>1else k
f=lambda n,k=1:n and-~f(n-g(k),k+1)

```

Test it on Ideone.
> 6 votes

# Answer
# Brachylog, 45 bytes

```
:1-I,?:?*:1ydo:Im.
1.|:1-:1&I(:3*:1-.;I*:1+.)

```

Computes `N = 1000` in about 6 seconds on my machine.

This is 1-indexed, e.g.

```
run_from_file('code.brachylog',1000,Z).
Z = 13961 .

```

### Explanation

* Main predicate:

```
:1-I,               I = Input - 1
     ?:?*           Square the Input
         :1y        Find the first Input*Input valid outputs of predicate 1
            do      Remove duplicates and order
              :Im.  Output is the Ith element

```
* Predicate 1:

```
1.                  Input = Output = 1
|                   Or
:1-:1&I             I is the output of predicate 1 called with Input - 1 as input
       (
         :3*:1-.      Output is 3*I-1
       ;            Or
         I*:1+.       Output is 2*I+1
       )

```

You may note that we don't pass any input to predicate 1 when we call `y - Yield`. Because of constraint propagation, it will find the right input once reaching the `1.` clause which will propagate the correct input values.
> 5 votes

# Answer
## 05AB1E, ~~18~~ 17 bytes

Uses CP-1252 encoding.

```
$FÐ·>s3*<)˜Ù}ï{¹è

```

**Explanation**

```
$                  # initialize with 1
 F          }      # input number of times do
  Ð                # triplicate current list/number
   ·>              # double one copy and add 1
     s3*<          # multiply one copy by 3 and subtract 1
         )˜Ù       # combine the 3 lists to 1 list and remove duplicates
             ï{    # convert list to int and sort
               ¹è  # take the element from the list at index input

```

Try it online for small numbers

Very slow.
Uses 0-based indexing.
> 5 votes

# Answer
## JavaScript (ES6), 63 bytes

```
f=(n,a=[1],i=0)=>a[i++]?--n?f(n,a,a[i*2]=a[i*3-2]=1):i:f(n,a,i)

```

Probably gives up quickly due to the recursion.
> 5 votes

# Answer
# MATL, ~~19, 18~~ 17 bytes

```
1w:"tEQy3*qvSu]G)

```

This is an *extremely* inefficient algorithm. The online interpreter runs out of memory for inputs greater than 13.

*One byte saved, thanks to Luis Mendo!*

Try it online!

This version is longer, but more efficient (21 bytes)

```
1`tEQy3*qvSutnG3*<]G)

```

Try it online

Explanation:

The logical way to do it, is to add elements to the array until it is long enough to grab the i'th element. That's how the efficient one works. The *golfy* (and inefficient) way to do it, is to just increase the array size *i* times.

So first, we define the start array: `1`. Then we swap the top two elements, so that input is on top. `w`. Now, we loop through the input with `:"`. So *i* times:

```
t             %Duplicate our starting (or current) array.
 EQ           %Double it and increment
   y          %Push our starting array again
    3*q       %Multiply by 3 and decrement
       v      %Concatenate these two arrays and the starting array
        Su    %Sort them and remove all duplicate elements.

```

Now, we have a *gigantic* array of the sequence. (Way more than is needed to calculate) So we stop looping, `]`, and grab the i'th number from this array with `G)` (1-indexed)
> 4 votes

# Answer
## Clojure, 114 108 bytes

```
#(loop[a(sorted-set 1)n 1](let[x(first a)](if(= n %)x(recur(conj(disj a x)(+(* 2 x)1)(-(* 3 x)1))(inc n)))))

```

I wouldn't be surprised if this could be golfed/reduced by a significant amount but `set`'s not supporting nth really hurt my train of thought.

Try the online

Version with spaces:

```
#(loop [a (sorted-set 1)
        n 1]
  (let [x (first a)]
    (if (= n %)
      x
      (recur (conj (disj a x) (+ (* 2 x) 1) (- (* 3 x) 1)) (inc n))
      )))

```
> 4 votes

# Answer
## Retina, 57

```
^.+
$*¶¶1
¶¶(1(1*))
¶1$1$1¶$2$1$1
O`
}`(¶1+)\1\b
$1
G2`
1

```

Try it online!

0-indexed. Follows the frequently used algorithm: remove the minimum value from the current set, call it `x`, and add `2x+1` and `3x-1` to the set a number of times equal to the input, then the leading number is the result. The "set" in Retina is just a list that is repeatedly sorted and made to contain only unique elements. There are some sneaky bits added to the algorithm for golf, which I will explain once I've had some more time.

Big thanks to Martin for golfing off around 20 bytes!
> 4 votes

# Answer
# C++, 102 bytes

```
[](int i){int t;map<int,int>k;for(k[1];i--;k.erase(t))t=k.begin()->first,k[t*2+1],k[t*3-1];return t;};

```

This lambda function requires `#include <map>` and `using std::map`.

The `map` here is just a collection of keys; their values are ignored. I use `map` in order to benefit from the terse code for insertion:

```
k[1]; // inserts the key 1 into the map

```

Thanks to the sorted order of `map`, the smallest element is extracted by `k.begin()->first`.
> 3 votes

# Answer
## Actually, 27 bytes

```
╗1#╜`;;2*1+)3*1@-#++╔S`n╜@E

```

Try it online!

This program uses 0-based indexing. The approach is very brute-force, so don't expect it to work in the online interpreter for larger inputs.

Explanation:

```
╗1#╜`;;2*1+)3*1@-#++╔S`n╜@E
╗                            save input (n) in register 0
 1#                          push [1]
   ╜                         push n
    `;;2*1+)3*1@-#++╔S`n     do the following n times:
     ;;                        make two copies of the list
       2*1+                    apply 2x+1 to each element in one copy
           )3*1@-              and 3x-1 to each element in the other copy
                 #             workaround for a weird list bug
                  ++           append those two lists to the original list
                    ╔S         uniquify and sort
                        ╜@E  get the nth element (0-indexed)

```
> 3 votes

# Answer
# Ruby, 70 bytes

```
->n{a=*1
n.times{a<<a.map{|i|([2*i+1,3*i-1]-a).min||1.0/0}.min}
a[-2]}

```

## Explanation

```
->n{
    # Magical, golfy way of initializing an array. Equivalent to a = [1].
    a=*1
    n.times{
        # Generate the next element in the sequence, by...
        a<<
            # ... finding the minimal term that will appear at some point.
            a.map{|i|
                ([2*i+1,3*i-1]-a).min||1.0/0
            }.min
    }
    # We generated n+1 elements, so we'll take the *second* to last one.
    a[-2]
}

```
> 3 votes

# Answer
## CJam (25 bytes)

```
ri1a1${{_2*)1$3*(}%_&}*$=

```

Online demo. Note that this uses zero-based indexing.

This uses a similar approach to most: apply the transforms `n` times and then sort and extract the `n`th item. As a nod to efficiency the deduplication is applied inside the loop and the sorting is applied outside the loop.
> 2 votes

# Answer
## Retina, 48 bytes

```
.+
$*
+1`^(((!*)!(!|\3)(?=\3!1))*!)1|\b
!$1
-2`.

```

Try it online!

Inspired by nimi's answer I thought I'd try a different approach for Retina, making use of the regex engine's backtracking to figure out if any given (unary) number is in the sequence or not. It turns out this can be determined with a 27 byte regex, but making use of it costs a few more, but it still ends up shorter than the generative approach.

Here's an alternative 48-byte solution:

```
.+
$*
{`1\b
1!
}T`1``1((!*)!(!|\2)(?=!\2$))*!$
!

```

And using unary I/O we can do 42 bytes, but I'm trying to avoid that and the other Retina answer uses decimal as well:

```
1\b
1!
}T`1``1((!*)!(!|\2)(?=!\2$))*!$
!
1

```
> 2 votes

# Answer
# Perl, ~~173~~ 132 bytes +1 for -n = 133

```
sub c{my$a=pop;return($a==1||($a%2&&c(($a-1)/2))?1:$a%3!=2?0:$a%3==2?c(($a+1)/3):1)}while($#b<$_){$i++;@b=(@b,$i)if c$i}say$b[$_-1];

```

Ungolfed:

```
my @array = ();
my $n = <>;
sub chk {
    my $a = shift;
    return 1 if ($a == 1);
    if ($a % 2 == 0) {
        if ($a % 3 != 2) {
            return 0;
        } else {
            return chk(($a + 1) / 3);
        }
    } else {
        if (chk(($a - 1) / 2) == 0) {
            if ($a % 3 != 2) {
                return 0;
            } else {
                return chk(($a + 1) / 3);
            }
        } else {
            return 1
        }
    }
}
my $i = 1;
while ($#array < $n-1) {
    push(@array,$i) if (chk($i) == 1);
    $i++;
}
print $array[$n];

```

I can probably do better if I thought more about it, but this is what I came up with after just a few minutes. My first time golfing, so this was pretty fun!

Thanks to @Dada and @TùxCräftîñg (and a bunch of minor byte-optimizations) for -40 bytes
> 2 votes

# Answer
# Factor, 73 bytes

```
[ { } 1 rot [ { 2 3 } n*v { 1 -1 } v+ union natural-sort unclip ] times ]

```

Try it online!

Found a hidden golfing gem `unclip` which, given an array, returns `rest first` on the stack. It is especially helpful that `first` is on top of the stack. Using the `unclip`-ed state as the loop invariant, I could save a byte from `swap` vs. `rot` and six bytes from saving `first` at the end.

```
[                          ! anonymous lambda
  { } 1 rot [ ... ] times  ! setup stack as ( rest min ) and call n times...
    { 2 3 } n*v            !   ( rest {2*min,3*min} )
    { 1 -1 } v+            !   ( rest {2*min+1,3*min-1} )
    union natural-sort     !   set union of rest and next two numbers, sorted
    unclip                 !   extract first item (= next min)
]

```
> 2 votes

# Answer
# J, 31 bytes

```
{1(]]/:~@~.@,3&*,&:<:2*>:)^:[~]

```

Uses zero-based indexing. Very memory-inefficient.

## Explanation

```
{1(]]/:~@~.@,3&*,&:<:2*>:)^:[~]  Input: n
                              ]  Identity function, gets n
 1                               The constant 1
  (                      )^:[~   Repeat n times with an initial array a = [1]
                       >:          Increment each in a
                     2*            Multiply by 2 to get 2a+2
             3&*                   Multiply each in a by 3 to get 3a
                 &:<:              Decrement both x and y to get 2a+1 and 3a-1
                ,                  Join them
    ]                              Identity function, gets a
            ,                      Join a with 2a+1 and 3a-1
         ~.@                       Take the distinct values
     /:~@                          Sort up
   ]                               Return the sorted list
{                                Select the value from the list at index n and return it

```
> 1 votes

# Answer
# Octave, 68 bytes

```
function r=a(n)s=1;for(i=1:n)r=s(i);s=union(s,[r*2+1 r*3-1]);end;end

```
> 1 votes

# Answer
# JavaScript (ES6), 58

```
n=>(a=>{for(;n;)a[++i]?a[i-~i]=a[3*i-1]=--n:0})([i=0,1])|i

```

*Less golfed*

```
n=>{
  a=[];
  a[1] = 1;
  for(i = 0; n;)
  {
    ++i
    if (a[i])
    {
      a[2*i+1] = 1;
      a[3*i-1] = 1;
      --n;
    }
  }
  return i
}

```

*Test*

About time and memory: element 500000 in ~20 sec and 300MB used by my FireFox 64 bit alpha

```
F=
n=>(a=>{for(;n;)a[++i]?a[i-~i]=a[3*i-1]=--n:0})([i=0,1])|i

function test() {
  var n=+I.value, t0=+new Date
  O.textContent = F(n)
  console.log((+new Date-t0)/1000,'sec')
}

test()
```

```
#I { width:5em}
```

```
<input id=I type=number value=10 oninput="test()">
<span id=O></span>
```
> 1 votes

# Answer
# Husk, 17 bytes

```
!OuΞ¡ṁ§eo←*3o→D;1

```

Try it online!

There should be a shorter way using set difference.

This answer creates all the possibilities, merges them and deduplicates.
> 1 votes

# Answer
# Perl 5 `-p`, 82 bytes

```
$;{1}++;map@;{$_*2+1,$_*3-1}=1,keys%;while$_*3>keys%;;$_=(sort{$a-$b}keys%;)[$_-1]

```

Try it online!
> 1 votes

# Answer
# TI-Basic, 74 bytes

```
Input N
{1→A
For(I,1,N
1+2ʟA(I
If min(Ans≠ʟA
augment(ʟA,{Ans→A
3ʟA(I)-1
If min(Ans≠ʟA
augment(ʟA,{Ans→A
End
SortA(ʟA
ʟA(N

```

Uses 1-based indexing. Output is stored in `Ans` and is displayed.
> 1 votes

# Answer
# Wolfram Language (Mathematica), 37 bytes

```
Nest[Union[#,2#+1,3#-1]&,{1},#][[#]]&

```

Try it online!
> 0 votes

---
Tags: code-golf, math, number, sequence
---


title: Drop down the numbers

text:
# Question
Title: Drop down the numbers
This was inspired by Apply gravity to this matrix

Your challenge is to input a matrix with non-negative one-digit integers and drop down the 1's down 1 column, the 2's down 2 columns, the 3's down 3 columns, and so on. Once a number has been moved down and there is no number to take its original place, replace that slot with zero.

If the number can't be moved down enough, wrap it around the top. (e. g If there is a 3 in the second-to-last row, it should wrap around to the first row.)

If two numbers map to the same slot, the biggest number takes that slot.

## Test cases:

```
0,1,2,1,0    0,0,0,0,0
0,0,2,0,1    0,1,0,1,0
1,0,2,1,0 => 0,0,2,0,1
0,0,0,1,0    1,0,2,1,0
0,0,0,0,0    0,0,2,1,0

0,0,2,0,1     0,0,2,0,0
0,2,1,1,0  => 3,0,0,0,1
3,0,2,1,0     0,0,2,1,0
0,0,0,0,0     0,2,0,1,0

```

# Rules

# Scoring

This is , so the answer with the least amount of bytes wins.

# Answer
> 9 votes
# , 24 20 bytes

```
[:>./-@,|."0 2,*,=/]

```

Try it online!

-4 thanks to xash!

Solved independently, but seems very similar to ovs's APL solution. This one works for any number, because I didn't notice that the question only required handling 1-9.

The following explanation is slightly out of date, but the high-level concept, which is the interesting part, is still the same.

Consider input:

```
0 0 2 0 1
0 2 1 1 0
3 0 2 1 0
0 0 0 0 0

```
* `~.@, ... ]` \- The `...` part is a verb that takes the unique elements of the input `~.@,` as the left arg and the unaltered input as the right arg:

```
                                0 0 2 0 1
  0 2 1 3  >./@(-@[|."0 2[*=/)  0 2 1 1 0
                                3 0 2 1 0
                                0 0 0 0 0

```
* `=/` Checks if the entire input is equal to each of its unique elements, creating 4 masks, each the size of the original input:

```
  1 1 0 1 0
  1 0 0 0 1
  0 1 0 0 1  --> Locations of 0
  1 1 1 1 1

  0 0 1 0 0
  0 1 0 0 0
  0 0 1 0 0  --> Locations of 2
  0 0 0 0 0

  0 0 0 0 1
  0 0 1 1 0
  0 0 0 1 0  --> Locations of 1
  0 0 0 0 0

  0 0 0 0 0
  0 0 0 0 0
  1 0 0 0 0  --> Locations of 3
  0 0 0 0 0

```
* `[*` Multiply each of those by the unique elements, giving us a "decomposed" version of the original input:

```
  0 0 0 0 0
  0 0 0 0 0
  0 0 0 0 0
  0 0 0 0 0

  0 0 2 0 0
  0 2 0 0 0
  0 0 2 0 0
  0 0 0 0 0
                 Decomposed input
  0 0 0 0 1
  0 0 1 1 0
  0 0 0 1 0
  0 0 0 0 0

  0 0 0 0 0
  0 0 0 0 0
  3 0 0 0 0
  0 0 0 0 0

```
* `-@[|."0 2` Rotate each of those matrices down by the required amount:

```
  0 0 0 0 0
  0 0 0 0 0
  0 0 0 0 0  --> Rotated 0
  0 0 0 0 0

  0 0 2 0 0
  0 0 0 0 0
  0 0 2 0 0  --> Rotated 2
  0 2 0 0 0

  0 0 0 0 0
  0 0 0 0 1
  0 0 1 1 0  --> Rotated 1
  0 0 0 1 0

  0 0 0 0 0
  3 0 0 0 0
  0 0 0 0 0  --> Rotated 3
  0 0 0 0 0

```
* `>./@` Reduce the "planes" by max:

```
0 0 2 0 0
3 0 0 0 1
0 0 2 1 0
0 2 0 1 0

```

# Answer
> 7 votes
# APL(Dyalog Unicode), ~~17~~ ~~16~~ 14 bytes SBCS

-1 byte by looking at Jonah's J answer and another -2 bytes by implementing xash's suggestion on the same answer.

```
⌈/⊂(-⍤⊢⊖⊣×=)¨,

```

Try it on APLgolf!

I initially implemented a lot more "by hand", which ended up more than 3 times longer:

```
{{(⊃⍺)@(⊂1↓⍺)⊢⍵}/((↓⊂∘⍒⌷⊢){k,m|(k←≢⍵)0+⊃⍺}⌸⍸⍵),⊂0⍴⍨m←⍴⍵}

```

Try it on APLgolf!

# Answer
> 6 votes
# Jelly,  ~~16~~  12 bytes

I thought 16 seemed a bit much!

```
Zµ=Ɱ×ṙ"N»/)Z

```

A monadic Link that accepts a list of lists of integers and yields a list of lists of integers.

**Try it online!**

### How?

```
Zµ=Ɱ×ṙ"N»/)Z - Link: matrix, M
Z            - transpose -> columns of M (top to bottom)
 µ        )  - for each (c in columns of M):
   Ɱ         -   map (across v in c) with:
  =          -     (c) equals (v)? (vectorises)
    ×        -   multiply by (c) (vectorises)
                 -> [c with zeroed out non-v's for each v in c] -  call this X
       N     -   negate (c)
      "      -   (X) zip (negated c) with:
     ṙ       -     rotate left by
         /   -   reduce by:
        »    -     maximum (vectorises)
           Z - transpose -> back to rows

```

# Answer
> 6 votes
# JavaScript (ES6), 82 bytes

```
m=>m.map((r,y)=>r.map((_,x)=>m.map(q=(r,Y)=>q=(Y+(v=r[x]))%m.length-y|v<q?q:v)|q))

```

Try it online!

### How?

For each position \\$(x,y)\\$ in the input matrix \\$M\\$ of height \\$h\\$, we look for all values \\$M\_{x,Y}\\$ on the same column such that:

$$Y+M\_{x,Y}\equiv y\pmod h$$

and keep the highest one.

# Answer
> 6 votes
# Python 3 \+ numpy, 91 bytes

```
def f(a):r,c=a.nonzero();v=a[r,c];r+=v;i=v.argsort();a*=0;a[r[i]%len(a),c[i]]=v[i];return a

```

-23 due to @ovs

Try it online!

Much Different from the first solution. Takes a numpy array

(slightly outdated explanation) Assume the array

```
[[0 0 2 0 1]
 [0 2 1 1 0]
 [3 0 2 1 0]
 [0 0 0 0 0]]

```
* `r,c=nonzero(a)` First save the x-indices (rows) to `r` and y-indices (cols) to `c` of nonzero elements

```
r: [0 0 1 1 1 2 2 2]
c: [2 4 1 2 3 0 2 3]

```
* `v=a[r,c]` Then get the nonzero elements into `v`

```
v: [2 1 2 1 1 3 2 1]

```
* `n=(r+v)%len(a)` Then increment the each row (`r`) by respective nonzero elements (`v`) and modulo by matrix length (to wrap) and save to `n`

```
n: [2 1 3 2 2 1 0 3]

```
* `i=v.argsort()` Grade up the nonzero elements (To fix the multiple slots problem)

```
i: [1 3 4 7 0 2 6 5]

```
* `j=a*0` Matrix of zeros of shape of a to `j`

```
j: [[0 0 0 0 0]
    [0 0 0 0 0]
    [0 0 0 0 0]
    [0 0 0 0 0]]

```
* `j[n[i],c[i]]=v[i]` Assign graded up nonzero elements with new rows and old columns. Final result:

```
[[0 0 2 0 0]
 [3 0 0 0 1]
 [0 0 2 1 0]
 [0 2 0 1 0]]

```

# Answer
> 5 votes
# Python 3+numpy, 73 bytes

```
import numpy
def f(A):t=numpy.c_[:len(A)];return(t*(A[t-t.T]==t)).max(1)

```

Try it online!

Note: this probably fails for double wrap around **EDIT** or, more generally, for matrix entries equal to or larger than the matrix height thanks @alephalpha for pointing this out **end EDIT**. I'm just not sure it is a requirement (this is my first post here).

How it works: We first clone the zeroth axis using an auxiliary indexer `t`. `t` is a column, `t.T` a row `t-t.T` is 2D, applied to the zeroth axis of `A` (the input) it creates a new axis. the index `t-t.T` populates this with rotated copies of A taking advantage of broadcasting, advanced indexing and standard python wrap around for negative indices. We then compare with `t` to find the places where the rotated value matches the rotation. This is a boolean array which we multiply with `t` to mark each match explicitly with its value. It remains to pick out the `max` value along the appropriate axis.

# Answer
> 4 votes
# , 82 bytes

Or **\>=4.1, 75 bytes** by replacing the word `function` with `\`.

```
function(m,k=nrow(m),t=0*m){t[((row(m)+m-1)%%k+1+col(m)*k-k)[i]]=m[i<-order(m)];t}

```

Try it online!

Inspired by @wasif's answer.

---

Old solution (shorter for \>=4.1):

## , ~~94~~ ~~92~~ ~~89~~ 88 bytes

Or **\>=4.1, 74 bytes** by replacing two `function` appearances with `\`s.

```
function(m,k=nrow(m))apply(m,2,function(x,t=0*x){t[((x-k:1)%%k+1)[i]]=x[i<-order(x)];t})

```

Try it online!

-2 bytes thanks to some arithmetic and moving \\$nrows-x\\$ up instead of \\$x\\$ down.

-3 bytes taking inspiration from @wasif's `argsort` in his answer (`order` in ).

# Answer
> 3 votes
# Core Maude, ~~248~~ ~~244~~ 236 bytes

```
load linear
mod D is inc MATRIX{Nat0}*(sort Matrix{Nat0}to M). var A B C D : Nat . op d :
Nat M -> M . eq(A,B)|-> C ;(A,B)|-> D =(A,B)|-> max(C,D). eq d(A,(B,C)|-> D ;
X:M)=(B,(C + D)rem A)|-> D ; d(A,X:M). eq d(A,X:M)= X:M[owise]. endm

```

### Example Session

```
             \||||||||||||||||||/
           --- Welcome to Maude ---
             /||||||||||||||||||\
         Maude 3.1 built: Oct 12 2020 20:12:31
         Copyright 1997-2020 SRI International
           Sun Sep 26 21:12:35 2021
Maude> red d(5, (1,0) |-> 1 ; (2,0) |-> 2 ; (3,0) |-> 1 ;
>          (2,1) |-> 2 ; (4,1) |-> 1 ;
>          (0,2) |-> 1 ; (2,2) |-> 2 ; (3,2) |-> 1 ;
>          (3,3) |-> 1 ) .
result M: 0,3 |-> 1 ; 1,1 |-> 1 ; 2,2 |-> 2 ; 2,3 |-> 2 ; 2,4 |-> 2 ; 3,1 |-> 1
    ; 3,3 |-> 1 ; 3,4 |-> 1 ; 4,2 |-> 1
Maude> red d(4, (2,0) |-> 2 ; (4,0) |-> 1 ;
>          (1,1) |-> 2 ; (2,1) |-> 1 ; (3,1) |-> 1 ;
>          (0,2) |-> 3 ; (2,2) |-> 2 ; (3,2) |-> 1 ) .
result M: 0,1 |-> 3 ; 1,3 |-> 2 ; 2,0 |-> 2 ; 2,2 |-> 2 ; 3,2 |-> 1 ; 3,3 |-> 1
    ; 4,1 |-> 1

```

### Ungolfed

```
load linear

mod D is
    inc MATRIX{Nat0} * (sort Matrix{Nat0}to M).
    var A B C D : Nat .
    op d : Nat M -> M .
    eq (A, B) |-> C ; (A, B) |-> D = (A, B) |-> max(C, D) .
    eq d(A, (B, C) |-> D ; X:M) = (B, (C + D) rem A) |-> D ; d(A, X:M) .
    eq d(A, X:M) = X:M [owise] .
endm

```

The answer is obtained by reducing the function `d` with the height of the matrix and the matrix entries. In Maude, matrices are specified as a collection of their non-zero entries.

The height must be passed as a parameter because, in Maude's implementation of matrices, \\$(M)\\$ is indistinguishable from \\$\big(\begin{smallmatrix} M & 0\\ 0 & 0 \end{smallmatrix}\big)\\$ — i.e., all matrices can be infinitely extended with zeroes — but we must know the height to handle wrapping. We can't just assume it's the largest row number seen, because both example inputs have all zeroes for their last row.

One trick we use is to generate the output matrix initially without regard to collisions. It's not an error in Maude for a map to have duplicate keys, as long as you resolve them before you try to access that key from the map. We have a separate equation to resolve those duplicates. (Incidentally, that equation is why we must *include* `MATRIX` rather than *protect* it, which costs an extra byte (`inc` vs. `pr`) — because we're equating matrix terms to resolve collisions.)

---

Saved 4 bytes by dropping the `var` declaration for `X` and using an “on-the-fly” variable `X:M`.

---

Saved 8 bytes because I forgot to replace the module name `DROP-DOWN` with a shorter name before posting.

# Answer
> 3 votes
# Python 3+numpy, 77 bytes

```
import numpy
b=0*a
for i in range(1,a.max()+1):b[numpy.roll(a==i,i,axis=0)]=i

```

Try it online!

the roll function does it all, and i stole the zeros\_like trick from @ovs

# Answer
> 2 votes
# Ruby, 155 bytes

```
->m{r,c,o=m.size,m[0].size,{}
o.default=0
e="r.times{|y|c.times{|x|"
eval e+"v=m[y][x]
v>o[[(y+v)%r,x]]&&o[[(y+v)%r,x]]=v}}"
eval e+"m[y][x]=o[[y,x]]}}"
m}

```

Try it online!

We build an hash object with 2d-index as key.
Then we iterate input and we set the key corresponding to landing position to the value if greater.

# Answer
> 2 votes
# 05AB1E, ~~19~~ ~~18~~ 14 bytes

```
˜εQy*yFÁ]øεø€à

```

-5 bytes thanks to *@ovs*.

Try it online or verify all test cases.

**Explanation:**

```
Z          # Get the flattened maximum of the (implicit) input-matrix
 L         # Pop and push a list in the range [1,max]
˜          # (`ZL` is now `˜`: flatten the (implicit) input-matrix)
  ε        # Map over each:
   Q       #  Check for each integer in the (implicit) input-matrix whether it's equal
           #  to this integer
    y*     #  Multiply each by this integer
      yF   #  Loop `y` amount of times:
        Á  #   And rotate the rows that many times towards the right
  ]        # Close both the inner loop and map
   ø       # Zip/transpose to get a list of lists of rows
    ε      # Map each list of rows to:
     ø     #  Zip/transpose; so the values of each cell are grouped together now
      €à   #  Get the maximum of each list of cell-values
           # (after which the matrix is output implicitly as result)

```

Here a step-by-step of an input to output; with the old `ZL` (flattened maximum; \[1,max\] ranged list) instead of `˜` (flatten the input-matrix):

```
Z             #  i.e. [[0,0,2,0,1],
              #        [0,2,1,1,0],
              #        [3,0,2,1,0],
              #        [0,0,0,0,0]] → 3
 L            # → [1,2,3]
  εQ          # → [[[0,0,0,0,1],[0,0,1,1,0],[0,0,0,1,0],[0,0,0,0,0]],
              #    [[0,0,1,0,0],[0,1,0,0,0],[0,0,1,0,0],[0,0,0,0,0]],
              #    [[0,0,0,0,0],[0,0,0,0,0],[1,0,0,0,0],[0,0,0,0,0]]]
    y*        # → [[[0,0,0,0,1],[0,0,1,1,0],[0,0,0,1,0],[0,0,0,0,0]],
              #    [[0,0,2,0,0],[0,2,0,0,0],[0,0,2,0,0],[0,0,0,0,0]],
              #    [[0,0,0,0,0],[0,0,0,0,0],[3,0,0,0,0],[0,0,0,0,0]]]
      yFÁ]    # → [[[0,0,0,0,0],[0,0,0,0,1],[0,0,1,1,0],[0,0,0,1,0]],
              #    [[0,0,2,0,0],[0,0,0,0,0],[0,0,2,0,0],[0,2,0,0,0]],
              #    [[0,0,0,0,0],[3,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]]
   ø          # → [[[0,0,0,0,0],[0,0,2,0,0],[0,0,0,0,0]],
              #    [[0,0,0,0,1],[0,0,0,0,0],[3,0,0,0,0]],
              #    [[0,0,1,1,0],[0,0,2,0,0],[0,0,0,0,0]],
              #    [[0,0,0,1,0],[0,2,0,0,0],[0,0,0,0,0]]]
    εø        # → [[[0,0,0],[0,0,0],[0,2,0],[0,0,0],[0,0,0]],
              #    [[0,0,3],[0,0,0],[0,0,0],[0,0,0],[1,0,0]],
              #    [[0,0,0],[0,0,0],[1,2,0],[1,0,0],[0,0,0]],
              #    [[0,0,0],[0,2,0],[0,0,0],[1,0,0],[0,0,0]]]
      €à      # → [[0,0,2,0,0],
              #    [3,0,0,0,1],
              #    [0,0,2,1,0],
              #    [0,2,0,1,0]]

```

# Answer
> 2 votes
# Python 3, 103 bytes

```
r=range
f=lambda A:[*zip(*[[max(i*(c[j-i]==i)for i in r(len(c)))for j in r(len(c))]for c in zip(*A)])]

```

Try it online!

This is more or less a one-to-one translation of my `numpy` answer.

The same explanation and caveat apply.

# Answer
> 1 votes
# Python 2, 157 bytes

```
e=enumerate;l=input();j=[[0]*len(l[0])for _ in l]
for x,y,z in sorted([((n+x)%len(l),m,x)for n,y in e(l)for m,x in e(y)],key=lambda e:e[2]):j[x][y]=z
print j

```

Try it online!

-7 thanks to @ykcul

# Answer
> 1 votes
# Charcoal, 23 bytes

```
ＩＥθＥι⌈Ｅθ∧¬﹪⁻⁺§νμξκＬθ§νμ

```

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

```
  θ                     Input array
 Ｅ                      Map over rows
    ι                   Current row
   Ｅ                    Map over cells
       θ                Input array
      Ｅ                 Map over rows
             §νμ        Inner cell
            ⁺   ξ       Plus inner index
           ⁻     κ      Minus outer index
         ¬﹪             Is divisible by
                  Ｌθ    Height of array
        ∧               Logical And
                    §νμ Inner cell
     ⌈                  Maximum
Ｉ                       Cast to string
                        Implicitly print

```

# Answer
> 1 votes
# Wolfram Language (Mathematica), 63 bytes

```
MapThread[Max,RotateRight[#/.x_/;x!=i:>0,i]~Table~{i,Max@#},2]&

```

Try it online!

---
Tags: code-golf, matrix
---


title: Crossing a river with weird animals

text:
# Question
Title: Crossing a river with weird animals
## Background

One kind of river-crossing problems involves two kinds of animals. One such problem reads like this: (all wordings, including animal species, are arbitrary)

> A farmer has to cross a river with three chickens and three dogs. There's a boat which can only fit the farmer and at most two animals. On either side of the river, if both kinds of animals are present and the dogs outnumber the chickens at any moment, the dogs will kill the chickens. Also, for some reason, the farmer can't cross the river alone. Can the farmer safely cross the river with all his animals? (For the sake of the puzzle, assume that all animals land on the destination side before the next turn.)
>
> Bonus: What if the farmer had four of each kind of animals?

whose answer is

> Yes:
>
> ```
>  |          |
>                 ->
>      |          |
>                 <-
>    |          |
>                 ->
>        |          |
>                 <-
>      |          |
>                 ->
>          |          |
>                 <-
>      |          |
>                 ->
>          |          |
>                 <-
>        |          |
>                 ->
>            |          |
>                 <-
>          |          |
>                 ->
>              |          |
> ```
>
> Bonus: No.

One way to solve this puzzle is to construct a grid like this: `O` indicates that the dog-chicken combination is allowed on the initial side (and the rest on the opposite side); `X` means not allowed.

```
\| 0 1 2 3
-----+---------
  0  | O X X O
  1  | O O X O
  2  | O X O O
  3  | O X X O

```

Then the problem is about going from (3,3) to (0,0) with alternating forward-backward moves (using NSEW for one step in each cardinal direction):

* Forward: one of N, W, NN, WW, or NW
* Backward: one of S, E, SS, EE, or SE

The solution in the spoiler box follows the path below:

```
(3,3) NN -> (1,3)
      S  -> (2,3)
      NN -> (0,3)
      S  -> (1,3)
      WW -> (1,1)
      SE -> (2,2)
      WW -> (2,0)
      S  -> (3,0)
      NN -> (1,0)
      S  -> (2,0)
      NN -> (0,0)

```

## Challenge

Given a rectangular grid of valid states as shown above, determine whether the river-crossing puzzle has a solution or not, i.e. a forward-backward alternating path exists between the top left corner and the bottom right corner.

The input has at least two rows and columns, but it may or may not be a square. The O's and X's in the input may be represented using any two distinct constant values (e.g. booleans, numbers, strings). You may assume the start and end corners are both O's.

For output, you can choose to

* output truthy/falsy using your language's convention (swapping is allowed), or
* use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard rules apply. The shortest code in bytes wins.

## Test cases

The test cases use 1 and 0 for O and X respectively.

### Truthy

```
[[1, 0],
 [0, 1]]

[[1, 1, 1],
 [1, 1, 1],
 [1, 1, 1]]

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

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

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

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

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

```

### Falsy

```
[[1, 0, 0],
 [0, 0, 1]]

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

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

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

```

Related: Wolves and Chickens (bonus: can you exploit the strategy to golf the linked challenge further?)

# Answer
> 6 votes
# Wolfram Language (Mathematica), 97 bytes

Saved 6 bytes thanks to @att.

```
FindPath[Pick[e@@#<->#2,0<=Min[d=#2-#]<Tr@d<3]&@@@#~Tuples~2,1~e~1,Last@#]~FreeQ~{}&@*Position[1]

```

Try it online!

# Answer
> 3 votes
# Charcoal, 88 bytes

```
⊞υ⊖⟦⁰ＬθＬ§θ⁰⟧ＦθＦ²⊞ι⁰Ｆ²⊞θＥ§θ⁰¦⁰ＦυＦ³Ｆ³«≔Ｅι⎇ν⁺μ×§ι⁰⎇⊖νλκ±μη¿∧∨κλ∧›³⁺κλ›§§θ§η¹§η²№υη«⊞υη¬⌈Φην

```

Try it online! Link is to verbose version of code. Outputs `-` if a solution exists, nothing if not. Explanation:

```
⊞υ⊖⟦⁰ＬθＬ§θ⁰⟧

```

Start a breadth-first search with the initial position of the next move from the bottom right corner being a "forward" move.

```
ＦθＦ²⊞ι⁰Ｆ²⊞θＥ§θ⁰¦⁰

```

Pad the input with two rows and columns of zeros.

```
ＦυＦ³Ｆ³«

```

Consider all moves from all positions plus some illegal moves at this point.

```
≔Ｅι⎇ν⁺μ×§ι⁰⎇⊖νλκ±μη

```

Calculate the resulting position from this move, adjusted for "forward" and "reverse".

```
¿∧∨κλ∧›³⁺κλ›§§θ§η¹§η²№υη«

```

If the move is legal (i.e. one of NN, NW, N, WW or W for "forward" and equivalently for "reverse"), and the resulting position is legal and as yet unknown, then:

```
⊞υη

```

Add the position to the list of known positions.

```
¬⌈Φην

```

Output a `-` if this position is in fact the top left.

# Answer
> 3 votes
# JavaScript (ES6), 112 bytes

Expects a matrix of 0's and 2's, for `'X'` and `'O'` respectively. Returns 0 or 2.

```
f=(m,x=0,y=0,i=1,r=m[y]||0)=>(r[x]--&&[1,2,4,5,8].some(d=>r[x+1]+1||m[y+1]?f(m,x+i*d%4,y+i*(d>>2),-i):1))*++r[x]

```

Try it online!

### Commented

```
f = (                     // f is a recursive function taking:
  m,                      //   m[]    = input matrix
  x = 0, y = 0,           //   (x, y) = current position
  i = 1,                  //   i      = direction (1 for S/E, -1 for N/W)
  r = m[y] || 0           //   r[]    = current row
) => (                    //
  r[x]--                  // decrement r[x]
  &&                      // abort if it was 0 or undefined
  [1, 2, 4, 5, 8]         // otherwise, for each value d
  .some(d =>              // in [1, 2, 4, 5, 8]:
    r[x + 1] + 1 ||       //   if there's either a cell on our right
    m[y + 1] ?            //   or below us:
      f(                  //     do a recursive call:
        m,                //       pass m[]
        x + i * d % 4,    //       update x to x + i * (d mod 4)
        y + i * (d >> 2), //       update y to y + i * (d >> 2)
        -i                //       invert the direction
      )                   //     end of recursive call
    :                     //   else (we've reached the bottom-right corner):
      1                   //     success
  )                       // end of some()
) * ++r[x]                // restore r[x]

```

---
Tags: code-golf, decision-problem, grid, path-finding, puzzle-solver
---


title: Recursive Stalin Sort

text:
# Question
Title: Recursive Stalin Sort
There is a "sorting" algorithm often called Stalin Sort, where instead of sorting an array, you just remove any items that are out of order. In this challenge, you'll implement part of a sorting algorithm which recursively sorts the removed items, then merges the arrays to form one (properly sorted) array.

## Algorithm

Take this array:

```
[7, 1, 2, 8, 4, 10, 1, 4, 2]

```

There are a few sets of items you could remove to make it increasing. For this challenge, you should keep the first item the same, even if it doesn't result in the longest possible list of sorted items. This gives us `[7, 8, 10]`, with `[1, 2, 4, 1, 4, 2]` as the removed items.

If you also do this with the removed items, you get `[1, 2, 4, 4]`, with `[1, 2]` as the removed items. Because this is also sorted, we're done. This gives us three arrays:

```
[7, 8, 10]
[1, 2, 4, 4]
[1, 2]

```

This is the format of the output.

If you wanted to use this to sort the array, you'd recursively merge the last two arrays to form one sorted list:

```
[1, 1, 2, 2, 4, 4, 7, 8, 10]

```

## Task

Take an array of integers as input. Return all of the arrays of removed items, before they are merged, as shown above.

You can do this by returning a 2d array, or printing any unambiguous representation of the arrays (for example, comma separated numbers and newline separated arrays).

## Test cases

**Input:** `[1, 2]`

```
[1, 2]

```

**Input:** `[2, 1]`

```
[2]
[1]

```

**Input:** `[1, 2, 4, 1, 2]`

```
[1, 2, 4]
[1, 2]

```

**Input:** `[2, 1, 1, 2, 2]`

```
[2, 2, 2]
[1, 1]

```

**Input:** `[1, 2, 4, 8, 4, 2, 1]`

```
[1, 2, 4, 8]
[4]
[2]
[1]

```

**Input:** `[8, 4, 2, 1, 2, 4, 8]`

```
[8, 8]
[4, 4]
[2, 2]
[1]

```

**Input:** `[7, 1, 2, 8, 4, 10, 1, 4, 2]`

```
[7, 8, 10]
[1, 2, 4, 4]
[1, 2]

```

**Input:** `[7, 7, 8, 7, 7]`

```
[7, 7, 8]
[7, 7]

```

## Other

This is , so shortest answer (in bytes) per language wins!

# Answer
# Jelly, 10 bytes

```
»\nx@µƬœ-Ɲ

```

Try It Online!

Pleasantly surprised this works without having to stick any reverses in or anything. `ḟ"»\FµƬœ-Ɲ` also works for the same length. Ultimately the result of trying to replace the `¹` in hyper-neutrino's answer with something else, funnily enough.

```
     µƬ       Repeat while unique, collecting all results including the input:
  n           For each element, is it not equal to
»\            the largest element of the list at that point?
   x@         Keep only the non-equal elements, i.e. the "out of order" elements.
         Ɲ    For each overlapping pair of adjacent results:
       œ-     for each element of the second, remove its last occurrence from the first.

```
> 9 votes

# Answer
# , ~~58~~ 57 bytes

```
f=function(a,b=a<cummax(a)){any(b)&&f(a[b]);print(a[!b])}

```

Try it online!

Prints the arrays in reverse order.

Add one byte to print in the same order as the example (try it here):

```
f=function(a,b=a<cummax(a)){show(a[!b]);if(any(b))f(a[b])}

```
> 6 votes

# Answer
# Haskell, ~~97~~ 90 bytes

```
f(h:t)=g[h]t[]
f[]=[]
g s[]r=reverse s:f r
g(a:b)(h:t)r|h<a=g(a:b)t$r++[h]|1>0=g(h:a:b)t r

```

Try it online!
> 6 votes

# Answer
# Python 3, 88 bytes

```
f=lambda s:s and[[s.pop(i)for i,x in[*enumerate(s)][::-1]if x==max(s[:i+1])][::-1]]+f(s)

```

Try it online!

## How it works :

let say our list is `[7, 1, 2, 8, 4, 10, 1, 4, 2]`.

* we iterate through the list backward, poping the items which are the maximum of the list up to them. Here `10` is equal to max of `[7, 1, 2, 8, 4, 10]`, `8` of `[7, 1, 2, 8]` and `7` of `[7]`. So we have `[10, 8, 7]`
* we reverse it to have `[7, 8, 10]`
* we return it along with the result of the function applied to the remaining items (`[1, 2, 4, 1, 4, 2]`)
* when the list is empty, it returns itself (`[]`)
> 6 votes

# Answer
# APL (Dyalog Unicode), 21 bytes

Anonymous tacit prefix function.

```
{m/⍵⊣⎕←⍵/⍨~m←⍵≠⌈\⍵}⍣≡

```

Try it online!

`{``}⍣≡` apply the following lambda until stable (i.e. the argument is empty

`⌈\⍵` cumulative maximum or argument

`⍵≠` Boolean mask indicating which elements of the argument differ

`m←` assign to `m` (for **m**ask)

`~` invert the mask (lit. logical NOT)

`⍵/⍨` filter the argument using that mask

`⎕←` print that

`⍵⊣` ignore that in favour of the argument

`m/⍵` filter the argument using the mask `m`
> 5 votes

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

```
{x@.=+(x<|\x*)\1}

```

Try it online!

Collaborative effort from @ngn, @Bubbler and @chrispsn at the k tree. Assumes positive numbers.

With 2 more bytes it can handle negatives:

```
{x@.=+~{x*x<|\x}\x}

```

---

My original solution:

# K (ngn/k), 27 bytes

```
f:{{(,x),f y}/x@&'~:\x=|\x}

```

Try it online!

```
 f:{{(,x),f y}/x@&'~:\x=|\x}
                      x=|\x    x equals cumulative max
                   ~:\         append negation
               x@&'            partition x using both boolean masks
    {(,x),f y}                 join first partition with recursive call on second partition
              /                until convergence

```
> 5 votes

# Answer
# BQN, 21 20 bytesSBCS

*-1 byte by omitting  in the header for the base case*

```
{⟨⟩:;⊸∾⟜<´⌈`⊸=⊸⊔}

```

Try it here.

```
{⟨⟩:;⊸∾⟜<´⌈`⊸=⊸⊔}
 ⟨⟩:;               # If the input is an empty list, return the input, otherwise:
            ⌈`⊸=⊸⊔  # Group the input by equality with the max scan.
           ´         # Between the two groups:
      ⊸             # recurse on the left group
        ∾⟜<          # and join to the enclosed right group.

```
> 4 votes

# Answer
# Jelly, 13 bytes

```
»\=¹ƙƊṄṛ¥/µÐL

```

Try It Online!

I think this might be pretty much identical to Adám's answer but I'm not really sure; came up with it independently anyway.

```
»\=¹ƙƊṄṛ¥/µÐL  Main Link
          µÐL  Repeat until the results are no longer unique (which happens when it hits the empty array)
»\             Cumulative maximum; get the largest element so far at each position
  =            Vectorizing equality; basically find which elements should be extracted
   ¹ƙ          Key by identity; separate into groups based on the equality map (the first element will always be included, so we don't have to worry about group ordering)
         /     Reduce; since the list will necessarily have two elements, call last dyad on these two
      Ṅṛ¥      Combined dyad; print out the left element and return the right element

```
> 3 votes

# Answer
# Charcoal, 26 bytes

```
Ｗθ«≔⟦⟧υ≔Φθ∨∧υ‹κ⌈υ¬⊞ＯυκθＩ⟦υ

```

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

```
Ｗθ«

```

Repeat until there is nothing left to sort.

```
≔⟦⟧υ

```

Start each iteration with an empty result.

```
≔Φθ∨∧υ‹κ⌈υ¬⊞Ｏυκθ

```

Push the sorted values to the result while filtering them out from the input list.

```
Ｉ⟦υ

```

Output the sorted values, double-spacing between each sorted list.
> 3 votes

# Answer
# Ruby, 51 bytes

```
f=->a,*b{a[c=0]&&f[a.map{|i|i<c ?i:b<<c=i}-[p(b)]]}

```

Try it online!

### Commented

```
f=->a,*b{     # lambda with a = input array, b = empty array
  a[  0]&&      # if a is not empty
    c=0         # initialise c, the maximum value encountered so far, to 0
  f[            # recursively call f
    a.map{|i|     # map each element i of a to either:
      i<c ?i        # itself, if i<c
      :b<<  i       # the array b with i appended, otherwise
          c=i       # update c
    }             # end of map
    -[    ]       # remove from the call to f all elements equal to...
      p(b)        # print and return b
  ]             # end of recursive call
}             # end of lambda

```
> 3 votes

# Answer
# C (clang), ~~104~~ \\$\cdots\\$ ~~98~~ 96 bytes

```
k;m;*c;*b;f(*a,l){for(;k=l;)for(m=*(c=b=a);k--;++b)*b<m?*c++=*b:printf("\n%d "+(b>a),m=*b,--l);}

```

Try it online!

*Saved 2 bytes thanks to ceilingcat!!!*

Inputs the a pointer to an array of integers and its length (because pointers in C carry no length information).
Prints the recursive stalin sort of the input array to `stdout` as space separated numbers and newline separated arrays.
> 3 votes

# Answer
# Wolfram Language (Mathematica), 99 bytes

```
f=If[#=={},{},Join[{#},f@#2]&@@Fold[Insert[#,#2,{If[#2<#[[1,-1]],2,1],-1}]&,{#[[{1}]],{}},Rest@#]]&

```

Try it online!

```
f=
  If[#=={},{},           # recursive base case
    Join[{#},f@#2]&@@    # append recursive result
      Fold[
        Insert[#,#2,{If[#2<#[[1,-1]],2,1],-1}]&, # insert onto end of 1st or 2nd list
        {#[[{1}]],{}},                           # init 1st list with first input and 2nd list empty
        Rest@#                                   # fold across rest of list
      ]]&

```
> 3 votes

# Answer
# Haskell, 50 bytes

```
import Data.List
f[]=[]
f x|n<-nubBy(>)x=n:f(x\\n)

```

Try it online!

I took the brilliant idea of using `nubBy(>)` to perform a single "Stalin sort" from HPWiz on anagol.
> 3 votes

# Answer
# JavaScript (ES6),  ~~59~~  57 bytes

```
f=a=>a+a?[a.filter(v=>a>v?!b.push(v):a=v,b=[]),...f(b)]:a

```

Try it online!

### Commented

```
f = a =>             // f is a recursive function taking a[]
  a + a ?            // if a[] is not empty:
    [ a.filter(v =>  //   for each value v in a[]:
        a > v ?      //     if v is less than the last kept element:
          !b.push(v) //       discard this value and push it in b[]
        :            //     else:
          a = v,     //       keep this value and save it in a
        b = []       //     start with b[] = empty array
      ),             //   end of filter()
      ...f(b)        //   append the result of a recursive call with b[]
    ]                //
  :                  // else:
    a                //   stop the recursion

```
> 2 votes

# Answer
# TI-Basic, 80 bytes

```
Ans→A
{ʟA(1→B
ʟB→C
For(I,2,dim(ʟA
ʟA(I
If Ans≥ʟB(dim(ʟB
Then
augment(ʟB,{Ans→B
Else
augment(ʟC,{Ans→C
End
End
Disp ʟB
ΔList(cumSum(ʟC
prgmZ

```
* assumes that the program is stored in `prgmZ` to allow recursion
* input is taken as `Ans` to allow recursion
* `ʟA` is used as the input list, `ʟB` the cleansed list and `ʟC` the remaining numbers, with a leading dummy value because TI-Basic can't handle empty lists
* `ΔList(cumSum(ʟC` basically trims `ʟC` from its first value and stores it in `Ans`, to allow calling the program again with this list

this will fail if `ʟC` has a length of 1, so the program stops. Once the error message is ignored, we can see the output:
> 2 votes

# Answer
# Julia 1.0, 60 bytes

```
~v=(!(*,a=0)=v[v.|>i->(a=max(a,i))i];v>[] ? [[!<=];~!>] : v)

```

Try it online!

The helper function `!` is called twice at each step of the stalin sort, once with `<=` for the sorted part and with `>` for the "rest" part.

the comparison operator (`>` or `<=`) takes the place of `*` in `!`, including implicit multiplication: `(a=max(a,i))i``(a=max(a,i))*i``(a=max(a,i))>i`
> 1 votes

# Answer
## Clojure, 133 bytes

```
(fn f[i](let[[x y](reduce(fn[[a b]j](if(>(last a)j)[a(conj b j)][(conj a j)b]))[[(first i)][]](rest i))](if(seq y)(cons x(f y))[x])))

```

I wish this would have been shorter. `f` implements the Stalin Sort which is called recursively as deemed necessary. TIO.
> 1 votes

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


title: Tips for golfing in INTERCAL

text:
# Question
Title: Tips for golfing in INTERCAL
What general tips do you have for golfing in INTERCAL? I'm looking for ideas which can be applied to code golf challenges and are also at least somewhat specific to INTERCAL (i.e. "remove comments" is not a useful answer).

I know exotic languages can be really useful to win golf contests, but I don't see much INTERCAL code around here. Do you have any advice that can help people get competitive code sizes with INTERCAL? Could this language ever be competitive?

*INTERCAL is so underutilized that it doesn't even have a tag. So sad...*

# Answer
> 7 votes
# INTERCAL doesn't specify precedence, but it also doesn't *error* on ambiguous precedence

An expression like

```
#1$#2~#3

```

is ambiguous, and could mean

```
'#1$#2'~#3

```

or

```
#1$'#2~#3'

```

The INTERCAL spec leaves it intentionally unclear which is meant, and in general there's no standard (although C-INTERCAL and CLC-INTERCAL make an effort to match each other in the simpler cases). That said, the original isn't *incorrect*; it's ambiguous and I wouldn't advise using it in production code (but then, I wouldn't advise using INTERCAL itself in production code), but it will have some meaning in the majority of compilers.

In other words, it may be worth just removing grouping characters and hoping your program still works. Most interpreters will parse any given ambiguous expression consistently, so for each pair of grouping characters, there's a 1 in 2 chance it's unnecessary; that can add up to quite some savings. (Unfortunately, INTERCAL parsers tend to be sufficiently confusing that nobody's entirely sure what the rules actually *are*, but it can normally be determined by experiment. In the simplest cases, operators tend to all have equal precedence and to have a consistent associativity.)

# Answer
> 6 votes
# Focus on doing as much work as possible in one statement

INTERCAL's statement identifiers are rather verbose; `DO` is two noise characters on every statement, the statement's name itself also tends to be quite long, and you have to throw in a `PLEASE` every now and then to keep the parser happy. (The best you can do is a ratio of four `DO` to one `PLEASE`, meaning you're using 14 characters in identifiers for every 5 commands.) On the other hand, the expression syntax is fairly terse (ridiculous, but terse). This means that it's often worthwhile fitting part of your program into a single expression even when using multiple statements would be a more "natural" way to do things.

For example, if you want to assign `#1` to `.1` and `#2` to `.2`, instead of doing it in the obvious INTERCAL-72 way:

```
DO.1<-#1DO.2<-#2

```

it's strongly worth considering overloading a random variable to allow you to assign both at once:

```
DO:1<-#1$#2

```

(with `:1/!1$.2'` thrown in somewhere earlier in the program; note that this notation postdates INTERCAL-72 by quite a way, so you'll need to use a modern INTERCAL for this to work). This is only slightly longer even if you take the setup into account, and becomes shorter if you ever need to, or can arrange to, simultaneously assign to `.1` and `.2` more than once.

It's not just calculate commands where this trick works. If you need to stash a variable twice, don't do it like this:

```
DOSTASH.1DOSTASH.1

```

but like this:

```
DOSTASH.1+.1

```

(The `+` notation works for most commands where it could conceptually make sense.)

# Answer
> 5 votes
# Use a single RESUME for all INTERCAL-72-style if consructs

If you need to write the equivalent of an "if" statement, the normal method using INTERCAL-72 code is to `NEXT` twice and then do a computed `RESUME`. (In modern code, often a computed `COME FROM` will be better, but this tip assumes your code prefers `NEXT`.) You almost certainly have to pay the bytes for the first `NEXT`, as it jumps from one branch of the "if" to the other. Sharing the second `NEXT` is also nontrivial, unless you have a lot of "if" statements that go to the same place upon seeing a `#1`. However, the `RESUME` can be anywhere in the program (because control is going to leave it instantly anywhere).

There are two ways to handle this. If you have a lot of "if" statements, then the `RESUME` probably warrants a single-digit line number, so that your second `NEXT` statement can be as short as possible. If possible, try to make it a computed `RESUME` that would naturally occur in your code (admittedly, this is difficult, as it's rare for those to appear in the "normal flow" of code rather than being `NEXT`ed to); then, the only cost is the line number. You'll have to use a single boolean variable for all these `NEXT`s; the universal consensus here is to use `.5`, mostly because it's the variable that the standard library uses for boolean return values.

Alternatively, it's possible to make use of an undocumented (technically underdocumented, because I slipped a hint into the INTERCAL documentation when I noticed) feature of the standard library. Because a central location for a `RESUME` is so useful, the standard library uses one internally. Line numbers in INTERCAL are global (with namespacing conventions, but which can be broken if you know what you're doing), so you can `NEXT` right into the standard library internals if you want to, and in particular, can `NEXT` to *its* central RESUME location. This is sufficiently popular in existing INTERCAL code that standard library replacements tend to have to implement it to avoid breaking existing programs.

The line in question is (either literally or effectively, depending on the implementation):

```
(1001) DO RESUME .5

```

The main reason not to use this is its long line number; if you need to do a lot of INTERCAL-72-style if constructs, it'll be better to use your own to give it a shorter number.

Of course, you can combine the techniques, writing something like

```
(9)DO(1001)NEXT

```

which is only marginally longer than

```
(9)DORESUME.5

```

and has the benefit that the booleans become `#2` and `#3` (which is harder to read, but normally easier to generate). Actually, it might even be worth putting in the extra code to handle `#0` and `#1` if you're going to be iffing a lot (but computed `COME FROM` will probably work better in this case unless your requirements are very weird).

# Answer
> 4 votes
# Whitespace / "noise" removal can go further than you might expect

INTERCAL is a whitespace-insensitive language. Unlike most whitespace-insensitive languages, though, the insensitivity goes much further than you might expect.

For example, `DO NOT` is two tokens, but can be written `DONOT` without the parser complaining (in pretty much any widely used implementation). (Of course, you could also write `DON'T`, but it isn't any terser. It might be easier to read, though. `PLEASEN'T` is probably harder to read than `PLEASE NOT`, though.) Actually, there's some debate as to whether whitespace does anything at all; at least one INTERCAL parser allows it even inside numerical constants (not that that's very useful when golfing). One thing to bear in mind is that removing whitespace from `DO READ OUT` gives `DOREA**DO**UT` which can confuse some older INTERCAL parsers due to the embedded `DO` (although their authors generally consider this a bug, and thus nowadays it typically works in a valid program, it's not advisable to put code like this in the vicinity of a syntax error, as it can be much harder to disambiguate then).

Also remember that you can overpunch characters to save space. In ASCII, you can only really pull this off with `'.``!`, but that's a highly useful trick in its own right. (When you aren't using arrays, there's no possibility of a sparkears ambiguity even when all your grouping characters are the same, so for golfing entries, it's recommended to stick to just `'` unless an array subscript genuinely requires a `"`.) A bookworm can be represented in one byte by using the `?` abbreviation (C-INTERCAL) or Latin-1 for `¥` (CLC-INTERCAL), rather than the three that INTERCAL-72 needs.

# Answer
> 4 votes
# In C-INTERCAL, consider abbreviating code using `CREATE`

The `CREATE` statement allows you to create new syntax. This is particularly useful in golfing because it allows you to give statements shorter names. You can also use it to effectively "define a function" via creating a new operator (which has the huge advantage that it lets you call the function in the middle of an expression).

The setup cost here is fairly high, but if there's a construct that you use a lot, inventing shorter syntax for it is probably going to be a good idea.

# Answer
> 2 votes
# Golfing off GIVE UP statements

1. Trailing GIVE UP statement can be removed, as it will cause E633 error in C-INTERCAL or error 000 or 633 in CLC-INTERCAL to abort.
2. Replace GIVE UP statements with incomplete statements such as DO or D (`D` worked on CLC-INTERCAL but not on C-INTERCAL, if without compiler option.).
3. RETRIVE unSTASHed variable, RESUME #0, and many other runtime errors can also be alternatives.
4. ABSTAINFROM non-existing labels, invalid labels, etc. Same applied for REINSTATE.

# Answer
> 1 votes
# Calculated `COMEFROM`, `NEXTFROM`.

* `COMEFROM(9)` and `COMEFROM#9` are equivalent. This works for C-INTERCAL and CLC-INTERCAL.
* CLC-INTERCAL has `NEXTFROM`, as `DO(XXX)NEXT` to be obsolete (which requires a compiler option). As well as COMEFROM statement, it supports labels to be computed.
* Since label numbers can be calculated, some complicated equations such as `DOCOMEFROM.1~.1` can be available.

# Answer
> 1 votes
# Dividing a variable by two.

```
DONOTe this is very long. Using C-INTERCAL library.
DO.1<-.9DO.2<-#2DO(1040)NEXTDO.9<-.3
DONOTe shorter way.
DONOTe The number can be smaller if you know that
DONOTe .9 shall have smaller value.
DO.9<-.9~#65534

```

Similar goes to dividing by 2^n.

# Answer
> 1 votes
# Golfing newline output in CLC-INTERCAL

```
DO,1<-#1DOREADOUT;1+,1

```

where `;1` is a string to output.

# Answer
> 0 votes
# CLC-INTERCAL (sick) can `ABSTAIN` and/or `REINSTATE` non-existing label.

C-INTERCAL (ick), on the other hand, makes it compiler error.

# Answer
> 0 votes
# CLC-INTERCAL 1.-94 does not check politeness of the program.

So every `PLEASE` and `PLEASEDO` can be replaced with `DO`.

---
Tags: code-golf, tips
---


# Question
Title: God is real . . . unless declared integer
This challenge is inspired by Fortran's idiosyncratic implicit typing rules. Your task will be to determine the data type of the object `GOD` according to the implicit typing rules explained below.

## Background

Fortran 77 has six data types: `CHARACTER`, `COMPLEX`, `DOUBLE PRECISION`, `INTEGER`, `LOGICAL`, and `REAL`. Any object not explicitly declared to have one of these types is *implicitly* assigned a type by the compiler, as determined by the first letter of the object's name. The default implicit types are:

```
----------------------------
First letter | Implicit type
-------------+--------------
    A-H      |     REAL
    I-N      |   INTEGER
    O-Z      |     REAL
----------------------------

```

For example, the object called `NUMBER` (first letter N) has implied type `INTEGER` whereas the object called `DUMBER` (first letter D) has implied type `REAL`. These rules lead to the old joke that `GOD` is `REAL` . . . unless declared `INTEGER`.

The default implicit types can be overridden using `IMPLICIT` statements. For example,

```
IMPLICIT DOUBLE PRECISION (D,X-Z), INTEGER (N-P)

```

means that all objects whose names start with D, X, Y, or Z now have implied type `DOUBLE PRECISION` and those starting with N, O, or P have implied type `INTEGER`. Objects whose names start with any other letter retain their default implied types (in this example, `REAL` for A–C, E–H, and Q–W and `INTEGER` for I–M).

For the purposes of this challenge, we will adopt a more concise syntax: the `IMPLICIT` keyword (redundant here) will be dropped and we will use the single-character identifiers `C`, `D`, `I`, `L`, `R`, and `X` to represent the six data types (`X` represents `COMPLEX`). Thus, the example `IMPLICIT` statement given above becomes

```
D(D,X-Z), I(N-P)

```

i.e. a series of identifier–range pairs.

## The challenge

Assume that the object `GOD` exists in a Fortran 77 program and does not have an explicitly declared type. Write a program or function that returns the implied type of `GOD`, given a compact `IMPLICIT` statement as input. This is : the shortest submission (in bytes) in each language wins.

## Input

* Input is either empty or otherwise consists of 1 to 26 identifier–range pairs.
* Input may be taken in any reasonable format (e.g. one long string, list of identifier–range pairs). If you divide the input into identifier–range pairs, each pair may either be taken as is, e.g. `'D(D,X-Z)'`, or split, e.g. `['D', '(D,X-Z)']`.
* In ranges, letters appear in alphabetical order and are separated either by commas (for single letters) or dashes (indicating a span of letters). One-letter spans, e.g. `G-G`, are valid. The outer parentheses must be included, but may be replaced with other paired delimiters (e.g. `[]` or `{}`) if desired.
* `IMPLICIT` statements are guaranteed not to overlap. That is, no letter has its implied type specified more than once.
* Alphabetic characters must be uppercase.

## Output

The uppercase identifier, `C`, `D`, `I`, `L`, `R`, or `X`, that represents the implied type of the object `GOD`. If the input is empty, your code must return `R` (the default type of `GOD`).

## Test cases

Input -\> Output

```
'' -> R
I(M-Z) -> R
I(A-Z) -> I
I(G) -> I
I(G-G) -> I
L(A,B,D-H,M-X,Z) -> L
D(D,X-Z), I(N-P) -> R
L(B,D,F,H,J,L,N,P,R,T,V,X,Z), C(A,C,E,G,I,K,M,O,Q,S,U,W,Y) -> C
D(S-Z), D(J-Q), D(A-H) -> D
I(I-K,M,R-T), R(N-P,U-Z), D(D-F,H), X(C,G), C(A,B,Q), L(L) -> X
I(F), X(N), R(P-P), I(C-C), C(A-A), I(J-J), R(V), D(H-H), X(O), L(B-B), C(R), L(Q-Q), I(D), L(X), R(S-S), C(Y), L(T-T), L(Z), X(U), D(K-K), R(G), X(W-W), D(I), C(L-L), R(E), I(M) -> R

```

Note: In the first test case, single quotes denote string boundaries.

## Bonus imaginary internet points!

Awarded to answers that only use characters from the standard Fortran 77 character set: the 26 uppercase letters `A-Z`, the 10 digits `0-9`, the space , and the 12 characters `+-*/=().,’:$`

# Answer
# FORTRAN IV (Compiled with gfortran -ffixed-form), ~~309~~ ~~291~~ ~~290~~ ~~280~~ ~~398~~ ~~393~~ ~~392~~ ~~334~~ ~~237~~ 231 bytes + Bonus imaginary Internet points

---

**This should now be a proper FORTRAN IV program, with no anachronisms!**

---

```
	REALS(200)
	DATAG,R,H,A/1HG,1HR,1H-,1H(/
	READ 9,S
    9	FORMAT(200A1)
	DO1 I=1,200
	C=S(I)
	IF(C.NE.A)GOTO2
	T=S(I-1)
	GOTO1
    2	IF(C.LT.G.AND.S(I+1).EQ.H.AND.S(I+2).GE.G.OR.C.EQ.G)GOTO8
    1	CONTINUE
	T=R
    8	PRINT 9,T
	END

```

Try it online!

Here's the same code embedded in a loop that runs through the entire test suite. I don't think this can be done with TIO's header and footer.

---

*18 bytes off thanks to @JonathanAllan, who pointed out that one IF statement wasn't needed.*

*1 more byte off by eliminating a stray space between `CHARACTER` and `S` at the top.*

*And 10 more bytes by rearranging the spaghetti code a bit.*

*Added 118 bytes to put it in proper FORTRAN IV fixed-column punch-card formatting. (This is for historical accuracy -- it isn't necessary for proper functioning under gfortran.)*

*Shaved off 5 more bytes: Cleaned up the GOTOs a bit, and changed the treatment of characters so it's actually correct for FORTRAN IV.*

*1 more byte off from removing an unneeded space in the `DATA` statement.*

*58 bytes off by streamlining the flow of control through the various IF statements.*

*97 more bytes off by: (1) eliminating variable `P`; and (2) replacing the spaces required at the beginning of a line with a tab character, which I found is allowed, according to an old FORTRAN IV manual. (I was thinking of punch card machines, which, as I recall, didn't have a horizontal tab, but I forgot about teletype machines, which did have a tab key.)*

*Thanks to @Dingus for 6 more bytes (from removing the `B` in the `DATA` statement which was no longer needed after `P` was eliminated).*

---

I've limited myself to FORTRAN IV constructs here. This should now be a correct FORTRAN IV program, without such things as the `CHARACTER` data type and quote-delimited strings, which were only introduced later.

Characters in FORTRAN IV needed to be entered as Hollerith constants, and they could be stored in variables of type REAL (and probably other types sometimes too, but there was no CHARACTER type originally). (As I recall, a real could hold 5 ASCII characters from what we now call a string. I think they were padded with spaces if there were fewer than 5 characters in a grouping. The single characters I use are each stored as a real, padded with extra space characters in the real.)

Input is on stdin, on one line, just like the OP's test cases.

Output is on stdout.

---

*FORTRAN IV was my introduction to computer programming -- it was the first programming language I ever learned. When I was a boy, I read through my dad's textbooks when he took a class in it at NYU, which was required by his musicology graduate program. Computer programming (as well as FORTRAN itself) has changed quite a bit since then :) .*

---
> 28 votes

# Answer
# Python 3, 61 bytes

```
lambda i:[a for a,b in i if re.match(b,'G')]or['R']
import re

```

Try it online!

**Input** a list of lists of the form `["<type char>", "[<var letters/ranges separated by commas>]"]` (*eg* `[['D','[D,X-Z]'],['X','[E,A-J]']]`).
**Output** a list of of one string of type char.
> 13 votes

# Answer
# Jelly,  ~~21~~  20 bytes

```
ṪḊṣ”,Om2r/71eƲƇµƇȯ”R

```

A full program accepting a list of pairs as defined in the specification (each being `[type_character, ranges_string]`) which prints the appropriate type character.

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

### How?

```
ṪḊṣ”,Om2r/71eƲƇµƇȯ”R - Main Link: list of pairs, [[type_char, range_str],...]
               µƇ    - filter keep those for which:
Ṫ                    -   tail & yield (removes the range_str which we now process
                         ...leaving [type_char] as what the filter might keep)
 Ḋ                   -   dequeue - remove the leading '('
  ṣ”,                -   split at commas (e.g. 'A,F-H,K-K)' -> ['A', 'F-H', 'K-K)']
     O               -   to ordinal (vectorises)            -> [[65], [70,45,72], [75,45,75]]
              Ƈ      -   filter keep those for which:
             Ʋ       -     last four links as a monad:
      m2             -       modulo-2 slice                 ->  [65]  [70,72]  [75,75]
          /          -       reduce by:
         r           -         inclusive range              ->  [65]  [70,71,72] [75]
           71        -       71
             e       -       exists in?                     ->  0     1          0
                     -   }-->                               -> [[70,45,72]]
                                                               (non-empty is truthy)
                     - }--> [[type_char]] or []
                  ȯ”R - logical or with 'R' (i.e. 'R' if empty)
                      - implicit, smashing print

```
> 6 votes

# Answer
# sed -E, ~~50~~ ~~45~~ 44 bytes

*1 byte off thanks to @user41805.*

```
s/^/R(G/;s/(.)*\([^)]*(G|[A-F]-[H-Z]).*/\1/;

```

Try it online!

This takes input on stdin formatted on one line just as in the OP's test cases, and output is on stdout.
> 4 votes

# Answer
# JavaScript (ES6), 39 bytes

Takes input as an array of `['type','[patterns]']`.

```
a=>(a.find(a=>'G'.match(a[1]))||'R')[0]

```

Try it online!

### Commented

```
a => (              // a[] = input array of [type, pattern]
  a.find(a =>       // find in a[]:
    'G'.match(a[1]) //   an entry whose pattern is matching 'G'
  )                 // end of find()
  || 'R'            // find() returns undefined if nothing is found,
                    // in which case we use the string 'R' instead
)[0]                // extract either the type of the entry that was found
                    // or the first (and only) character of 'R'

```
> 4 votes

# Answer
# Perl 5 `-MList::Util=pairgrep -ap`, ~~53~~ 30 bytes

```
$_=(pairgrep{G=~/$b/}@F)[0]||R

```

Try it online!

**Input**:

A single line, with literal square brackets:

`type [letter|range...] ...`
> 3 votes

# Answer
## Ruby, 37 bytes

```
->x{(x.find{|_,r|/#{r}/=~?G}||?R)[0]}

```

Try it online!

Takes input as pairs with brackets, and interprets the second element of each pair as a regexp.
> 3 votes

# Answer
# Retina 0.8.2, ~~37~~ 36 bytes

```
$
R(G
1!`.(?=\([^)]*(G|[A-F]-[H-Z]))

```

Try it online! Link includes test cases. Edit: Saved 1 byte thanks to @MitchellSpector. Explanation:

```
$
R(G

```

Default to Real.

```
.(?=\([^)]*(G|[A-F]-[H-Z]))

```

Match a letter that's followed by a `(` and then any non-`(` characters including a `G` or a range that includes a `G`.

```
1`

```

Only output the first match, in case the default is a duplicate.

```
!`

```

Print the match rather than the count of matches.
> 2 votes

# Answer
# Ruby `-pl`, 47 bytes

Takes space-separated arguments from STDIN.

```
t=?R
gsub(/(\w)(\S+)/){t=$1if"G".tr!$2,''}
$_=t

```

Try it online!
> 2 votes

# Answer
# Java 10, 63 bytes

```
m->{var r="R";for(var p:m)r="G".matches(p[1])?p[0]:r;return r;}

```

Input as an array of String-pairs in the format `["type", "[declaration]"]`.

Try it online.

**Explanation:**

```
m->{                     // Method with String-matrix as input and String return-type
  var r="R";             //  Result-String, starting at "R" as default
  for(var p:m)           //  Loop over each pair `p`
    r=                   //   Set the result to:
      "G".matches(p[1])? //    If "G" regex-matches the second part of the pair
       p[0]              //     Set the result to the first part of the pair
      :                  //    Else:
       r;                //     Leave the result unchanged
  return r;}             //  After the loop: return the result-String

```
> 2 votes

# Answer
# PowerShell, 38 bytes

`+` to @Noodle9

```
$r=$args|?{'G'-match$_[1]}
"R$r"[!!$r]

```

Expects input via splatting.

Try it online!
> 2 votes

# Answer
# Perl 5 with `-apF'(?=\[)'`, 25 bytes

Accepts input as:

```
A
[A-F,H-M]
B
[N-Z]

```

```
$\||=$_ x"G
"=~<>}{$\||=R

```

Try it online!

Verify all test cases.

*Note*: the empty test case is missing from the verify all link because my test suite is bad and I should feel bad, but it works when tested in isolation.
> 2 votes

# Answer
# Pip, 18 bytes

```
@@Y'G~``.@>_FIg|'R

```

Takes each identifier–range pair as a separate command-line argument, in the format `D[D,X-Z]`. Try it online!

### Explanation

```
              g     The list of cmdline args
            FI      Filter on this function:
         @>_         Everything after the first character
      ``.            Convert to Pattern (regex) by concatenating with an empty Pattern
   'G~               Match against the string "G"
                    We now have either a list containing the pair that matched, or empty list
               |'R  Logical OR with "R": if no pair matched, use "R" instead
  Y                 Yank (to get the operator precedence to cooperate)
 @                  Take first element: the pair that matched, or "R"
@                   First element of that: the identifier from the pair, or "R"
                    Autoprint

```
> 2 votes

# Answer
# Core Maude, 271 bytes

```
mod G is pr LIST{String}+ LEXICAL . op g : String ~> Qid . var A B C D
:[Qid]. var X Y :[String]. ceq g(X Y)= A if A '`( B C D '`) := tokenize(Y)/\
C == 'G or substr(string(C),0,1)< "H" and substr(string(C),2,1)> "F" . eq g(X
S:String)= g(X)[owise]. eq g(nil)= 'R . endm

```

The result is obtained by reducing the `g` function with a Maude list of strings of the form `"A(B,C-D)"`. The result will be a quoted identifier of the letter for the type of `GOD`, e.g., `'R`.

### Example Session

```
             \||||||||||||||||||/
           --- Welcome to Maude ---
             /||||||||||||||||||\
         Maude 3.1 built: Oct 12 2020 20:12:31
         Copyright 1997-2020 SRI International
           Thu Oct 21 00:28:50 2021
Maude> mod G is pr LIST{String}+ LEXICAL . op g : String ~> Qid . var A B C D
> :[Qid]. var X Y :[String]. ceq g(X Y)= A if A '`( B C D '`) := tokenize(Y)/\
> C == 'G or substr(string(C),0,1)< "H" and substr(string(C),2,1)> "F" . eq g(X
> S:String)= g(X)[owise]. eq g(nil)= 'R . endm
Maude> red g(nil) .
result Qid: 'R
Maude> red g("I(M-Z)") .
result Qid: 'R
Maude> red g("I(A-Z)") .
result Qid: 'I
Maude> red g("I(G)") .
result Qid: 'I
Maude> red g("I(G-G)") .
result Qid: 'I
Maude> red g("L(A,B,D-H,M-X,Z)") .
result Qid: 'L
Maude> red g("D(D,X-Z)" "I(N-P)") .
result Qid: 'R
Maude> red g("L(B,D,F,H,J,L,N,P,R,T,V,X,Z)" "C(A,C,E,G,I,K,M,O,Q,S,U,W,Y)") .
result Qid: 'C
Maude> red g("D(S-Z)" "D(J-Q)" "D(A-H)") .
result Qid: 'D
Maude> red g("I(I-K,M,R-T)" "R(N-P,U-Z)" "D(D-F,H)" "X(C,G)" "C(A,B,Q)" "L(L)") .
result Qid: 'X
Maude> red g("I(F)" "X(N)" "R(P-P)" "I(C-C)" "C(A-A)" "I(J-J)" "R(V)" "D(H-H)" "X(O)"
>       "L(B-B)" "C(R)" "L(Q-Q)" "I(D)" "L(X)" "R(S-S)" "C(Y)" "L(T-T)" "L(Z)"
>       "X(U)" "D(K-K)" "R(G)" "X(W-W)" "D(I)" "C(L-L)" "R(E)" "I(M)") .
result Qid: 'R

```

### Ungolfed

```
mod G is
    pr LIST{String} + LEXICAL .

    op g : String ~> Qid .

    var A B C D : [Qid] .
    var X Y : [String] .

    ceq g(X Y) = A
        if A '`( B C D '`) := tokenize(Y)
        /\ C == 'G or substr(string(C), 0, 1) < "H" and substr(string(C), 2, 1) > "F" .
    eq g(X S:String) = g(X) [owise] .
    eq g(nil) = 'R .
endm

```
> 2 votes

# Answer
# Japt `-g`, 12 bytes

```
k@'GrXÌÃÎª'R

```

Try it
> 1 votes

# Answer
# 05AB1E, ~~23~~ ~~21~~ 20 bytes

```
ʒθ',¡εáÇŸ}˜71å}˜'Rªн

```

Input as a list of pairs in the format `["type","(declaration)"]`.

Try it online or verify all test cases.

**Explanation:**

```
ʒ           # Filter the (implicit) list of pairs by:
 θ          #  Pop and push the last value of the pair
            #   i.e. ["I","(I-K,M,R-T)"] → "(I-K,M,R-T)"
  ',¡      '#  Split it by ","
            #   → ["(I-K","M","R-T)"]
     ε      #  Map each inner range to:
      á     #   Remove the "(", "-", and ")" by only leaving the letters
            #    → ["IK","M","RT"]
       Ç    #   Convert each letter to its codepoint integer
            #    → [[73,75],[77],[82,84]]
        Ÿ   #   And then convert it to a range
            #    → [[73,74,75],[77],[82,83,84]]
     }˜     #  After the map: flatten the list of lists of integers
            #   → [73,74,75,77,82,83,84]
       71å  #  Check if 71 is in this list (the codepoint for "G")
            #   → 0 (falsey)
}˜          # After the filter: flatten the remaining list of pairs (potentially empty)
            #  i.e. [["X","(C,G)"]] → ["X","(C,G)"]
  'Rª      '# Append an "R" to this list
            #  → ["X","(C,G)","R"]
     н      # Pop and only leave the first item of this list
            #  → "X"
            # (after which it is output implicitly as result)

```
> 1 votes

# Answer
# PowerShell, ~~38~~ 37 bytes

```
($args+'RG'|?{'G'-like"[$_ ]"})[0][0]

```

Try it online!

Takes strings as is, e.g. `'D(D,X-Z)'`.
> 1 votes

---
Tags: code-golf, string
---