title: Monotone sequence beatitude

text:
# Question
Title: Monotone sequence beatitude
Provided that the input is a **monotone** sequence of three or more integers:

* Output -2 if the sequence strictly decreases. Example: `[7,4,3,2]`
* Output -1 if the sequence monotone decreases but is neither strict nor constant. Example: `[6,5,5]`
* Output 0 if the sequence is constant. Example: `[0,0,0]`
* Output +1 if the sequence monotone increases but is neither strict nor constant. Example: `[-1,2,2,2,4]`
* Output +2 if the sequence strictly increases. Example: `[0,1,2]`

I/O format is flexible. Standard loopholes apply.

# Answer
> 2 votes
# Vyxal `g`, 29 bitsv2, 3.625 bytes

```
¯±:G+

```

Try it Online!

Bitstring:

```
11001100111100010001111111001

```

Port of the 05ab1e answer

# Answer
> 10 votes
# 05AB1E, ~~8 7~~ 6 bytes

```
¥.±Z+W

```

Attempt This Online!

```
¥      deltas
.±     sign
Z      maximum without popping
+      add (vectorized)
W      minimum

```

# Answer
> 7 votes
# Jelly, 6 bytes

```
IṠQ.ịS

```

Try it online!

Port of Command Master's 05AB1E answer. A monadic link taking a list of integers and returning an integer.

## Explanation

```
I      | Increments
 Ṡ     | Signs
  Q    | Uniquify
   .ị  | Last and first
     S | Sum

```

# Answer
> 6 votes
# Uiua, 11 bytes

```
⊢+⇌.⊝±≡/-◫2

```

Try it!

Port of Command Master's 05AB1E answer.

```
⊢+⇌.⊝±≡/-◫2
      ≡/-◫2  # deltas
     ±       # sign
    ⊝        # deduplicate
   .         # duplicate
  ⇌          # reverse
 +           # add
⊢            # first

```

# Answer
> 6 votes
# Scala 3, ~~71~~ 63 bytes

Saved 8 bytes thanks to the comment of @corvus\_192

---

```
x=>x zip x.tail map{case(a,b)=>b compare a}pipe(x=>x.min+x.max)

```

Attempt This Online!

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

```
a=>(a.reduce((p,v)=>(a|=p<v?5:p>v?-2:3,v)),a%3)

```

Try it online!

### Method

Because the input array `a` contains at least 3 elements, it is guaranteed to be evaluated to \\$0\\$ when coerced to an integer. So we can safely re-use it as a signed 32-bit mask.

For each pair of consecutive elements \\$(p,\\:v)\\$ in the input array, we apply to `a` a bitwise OR with:

* \\$5\\$ if \\$p\<v\\$
* \\$-2\\$ if \\$p\>v\\$
* \\$3\\$ if \\$p=v\\$

These values were chosen such that the expected output in \\$\[-2\dots2\]\\$ is obtained by reducing the final bitmask modulo \\$3\\$.

### List of cases

Because the sequence is monotone, there are only 5 possible cases:

| \\$p\<v\\$ | \\$p\>v\\$ | \\$p=v\\$ | operations | final bitmask | modulo 3 |
| --- | --- | --- | --- | --- | --- |
| no | no | yes | 0 | 3 | 3 | **0** |
| no | yes | no | 0 | -2 | -2 | **-2** |
| no | yes | yes | 0 | -2 | 3 | -1 | **-1** |
| yes | no | no | 0 | 5 | 5 | **2** |
| yes | no | yes | 0 | 5 | 3 | 7 | **1** |

# Answer
> 5 votes
# Python, 55 bytes

```
lambda S,*s:min(x:={(S<t)-(S>(S:=t))for t in s})+max(x)

```

Attempt This Online!

# Python 2, 53 bytes

```
def f(s):t=map(cmp,s[1:],s[:-1]);return min(t)+max(t)

```

Attempt This Online!

# Answer
> 5 votes
# Python 2, 43 bytes

```
lambda s:cmp(s[::-1],s)<<len(set(s))/len(s)

```

Attempt This Online!

Logs:

* My original answer (49 bytes):

```
lambda s:cmp(s[-1],s[0])*(2-(len(set(s))<len(s)))

```
* Neil's suggestion: `*(2-(len(set(s))<len(s)))` -\> `-~(len(set(s))==len(s))`
* xnor's suggestion: `*(2-(len(set(s))<len(s)))` -\> `<<(len(set(s))==len(s))` ; `cmp(s[-1],s[0])` -\> `cmp(s[::-1],s)`
* Albert.Lang's suggestion: `*(2-(len(set(s))<len(s)))` -\> `<<len(set(s))/len(s)`

Thank for amazing suggestions!

# Answer
> 5 votes
# Nekomata, 5 bytes

```
∆±uÄµ

```

Attempt This Online!

```
∆±uÄµ
∆       Delta
 ±      Sign
  u     Uniquify
   Ä    Multiply by 2
    µ   Mean

```

# Answer
> 5 votes
# K (ngn/k), 14 bytes

```
+/2#?0 1'1_-':

```

Try it online!

A slight variation on Nick Kennedy's Jelly answer. `0 1'` is from coltim's comment on another K answer.

```
+/2#?0 1'1_-':
         1_-':    differences
     0 1'         binary search into 0 1; negative -> -1, 0 -> 0, positive -> 1
    ?             keep unique elements
  2#              cycle the elements to length 2
+/                sum

```

# Answer
> 4 votes
# , ~~32~~ 29 bytes

```
\(x)sum(range(sign(diff(x))))

```

Attempt This Online!

A function taking a vector and returning the relevant result. Based on Command Master's 05AB1E answer.

*Thanks to @pajonk for saving three bytes!*

# Answer
> 4 votes
# K (ngn/k), ~~21~~ 16 bytes

Port of 05AB1E answer

-5 thanks to @coltim

```
&/+/|/\0 1'1_-':

```

Try it online!

```
           1_-': deltas
       0 1'      sign
  +/|/\          add maximum
&/               minimum

```

# Answer
> 3 votes
# Retina, ~~57~~ 51 bytes

```
\d+
*
Lv`\b_+,_+
+`_,_
,
O^`
,,G`
^_
-_
/[^-]+/_`_+

```

Try it online! Link includes test cases. Only accepts positive integer lists, but will output `-2` to `2` as required. Explanation:

```
\d+
*

```

Convert to unary.

```
Lv`\b_+,_+
+`_,_
,

```

For each overlapping pair of integers, get a substring representing the delta: `_+,` for negative, `,` for `0` and `,_+` for positive.

```
O^`

```

Group identical substrings together and sort `_,` first.

```
,,G`

```

Keep only one of each group, but if there is only one group, keep two of it.

```
^_
-_

```

If there was a `_,` then prefix a `-` sign.

```
/[^-]+/_`_+

```

Count the runs of `_`s.

Edit: Saved 6 bytes by porting my answer to Retina 0.8.2 for 61 bytes and then backporting the golfs:

```
\d+
$*
M!&`\b1+,1+
+`1,1
,
O^`
+`¶.+¶
¶
^1
-1
((1+)|,|¶)+
$#2

```

Try it online! Link includes test cases. Only accepts positive integer lists, but will output `-2` to `2` as required. Explanation: Retina 0.8.2 uses `$*` (which produces `1`s) instead of `*` (which produces `_`s) for unary, needs to use `M!&` instead of `Lv`, and doesn't have an equivalent of `,,G` or `_` (as a command), so I had to emulate those.

# Answer
> 3 votes
# JavaScript (Node.js), 50 bytes

```
a=>~!a.some(p=x=>p==(p=x))*Math.sign(a[0]-a.pop())

```

Try it online!

Use begin and end to detect direction

# Answer
> 3 votes
# sclin, 23 bytes

```
_"-"2%map0<=>"|/"Q + &/

```

Try it on scline! Port of Command Master's answer.

## Explanation

Prettified:

```
_ \- 2%map 0<=> \|/ Q + &/

```
* `_ \- 2%map` negated delta (via pairwise difference)
* `0<=>` sign (i.e. compare to 0)
* `\|/ Q` dup and get max
* `+ &/` vectorized-add and get min

# Answer
> 3 votes
# Desmos, 33 bytes

```
f(L)=D.max+D.min
D=sgn(L[2...]-L)

```

Port of 05AB1E.

Try It On Desmos!

Try It On Desmos! - Prettified

# Answer
> 2 votes
# Charcoal, 23 bytes

```
≔ＥΦθκ⁻›ι§θκ‹ι§θκθＩ⁺⌊θ⌈θ

```

Try it online! Link is to verbose version of code. Explanation: Port of @Albert.Lang's Python answer.

```
≔ＥΦθκ⁻›ι§θκ‹ι§θκθ

```

Get the signs of the deltas.

```
Ｉ⁺⌊θ⌈θ

```

Add the minimum and maximum of them.

# Answer
> 2 votes
# JavaScript (Node.js), 54 bytes

```
a=>a.map(n=p=o=v=>[n|=a>v,p|=a<v,o|=a==v,a=v])|p-n<<!o

```

Try it online!

# Answer
> 1 votes
# C (gcc), 63 bytes

Port of my JS answer.

```
m,p;f(a,n)int*a;{for(m=0;p=*a++,--n;)m|=p<*a?5:p>*a?-2:3;m%=3;}

```

Try it online!

# Answer
> 1 votes
# APL+WIN, 52 bytes

Prompts for vector:

```
+/2 1 0×(×n)×(s=⍴v),((s<⍴v)^s>0),0=s←1+|n←+/×-2-/v←⎕

```

Try it online! Thanks to Dyalog Classic

# Answer
> 1 votes
# Go, ~~193~~ 183 bytes

---

Saved 10 bytes thanks to the comment of @corvus\_192

---

Golfed version. Attempt this online!

```
func c(a,b int)int{if a<b{return 1};if a>b{return -1};return 0}
func f(n[]int)int{z:=math.MaxInt64;Z:=^z;for i:=0;i<len(n)-1;i++{r:=c(n[i],n[i+1]);if r<z{z=r};if r>Z{Z=r}};return z+Z}

```

Ungolfed version. Attempt This Online!

```
package main

import (
	"fmt"
	"math"
)

func compare(a, b int) int {
	if a < b {
		return 1
	}
	if a > b {
		return -1
	}
	return 0
}

func f(nums []int) int {
	min, max := math.MaxInt64, math.MinInt64
	for i := 0; i < len(nums)-1; i++ {
		result := compare(nums[i], nums[i+1])
		if result < min {
			min = result
		}
		if result > max {
			max = result
		}
	}
	return min + max
}

func main() {
	fmt.Println(f([]int{1, 2, 3, 5, 9}))
	fmt.Println(f([]int{1, 2, 3, 5, 5}))
	fmt.Println(f([]int{1, 1, 1, 1, 1}))
	fmt.Println(f([]int{1, 1, -3, -5, -9}))
	fmt.Println(f([]int{-1, -2, -3, -5, -9}))
}

```

# Answer
> 1 votes
# Swift, 175 bytes

Short version:

```
func m(_ n:[Int])->Int{var r=0,s=0>1;for i in 0..<n.count-1{let(y,x)=(n[i+1],n[i]);if y>x{r=r>0 && !s ?2:1}else if y<x{r=r<0 && !s ? -2:-1}else{r=r.signum();s=0<1}};return r}

```

Verbose version:

Basically update the return value to be 2 or -2 as long as the elements differ from each other and "clamp" it to -1,0,+1 as soon as two same elements are found.

```
func m(_ n:[Int])->Int{
    var r=0,
        s=0>1
    for i in 0..<n.count-1{
        let(y,x)=(n[i+1],n[i]);
        if y>x{
            r=r>0 && !s ?2:1
        }else if y<x{
            r=r<0 && !s ? -2:-1
        }else{
            r=r.signum();
            s=0<1
        }
    };
    return r
}

```

# Answer
> 1 votes
# Perl 5 `-p`, 53 bytes

```
s/\S+/$'&&$'-$&/ge;$_=2*(/^(\S+ )\1+$/?$1<=>0:.5-/-/)

```

Try it online!

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


title: Determine ranges from a list of values

text:
# Question
Title: Determine ranges from a list of values
Given an unsorted list of unique, positive integers, output the shortest list of the longest possible ranges of sequential integers.

# INPUT

* An unsorted list of unique, positive integers
    + e.g. `9 13 3 11 8 4 10 15`
* Input can be taken from any one of the following:
    + `stdin`
    + command-line arguments
    + function arguments

# OUTPUT

* An ordered list of ranges or individual values printed on one line to stdout or your language's closest similar output.
    + If two or more sequential integers (sequential by value, not by location in the list) are present, they will be denoted as an inclusive range using -, e.g. `8-11`
    + All other integers are simply printed with no other notation
    + A single space will delimit the output
* Numbers not present in the input should not be in the output, e.g. `3 5 6` cannot be shortened to `3-6` because `4` is not present

# EXAMPLES

**Successful:**

```
 IN> 9 13 3 11 8 4 10 15 6
OUT> 3-4 6 8-11 13 15

 IN> 11 10 6 9 13 8 3 4 15
OUT> 3-4 6 8-11 13 15

 IN> 5 8 3 2 6 4 7 1
OUT> 1-8

 IN> 5 3 7 1 9
OUT> 1 3 5 7 9

```

**Wrong:**

```
 IN> 9 13 3 11 8 4 10 15
OUT> 3-15

```

Range contains values not in the input

```
 IN> 9 13 3 11 8 4 10 15
OUT> 3 4 8 9 10 11 13 15

```

All sequential values should be represented as a range

```
 IN> 9 13 3 11 8 4 10 15
OUT> 3-4 8-9 10-11 13 15

```

Divided range, `8-9` and `10-11` should be `8-11`

```
 IN> 9 13 3 11 8 4 10 15
OUT> 8-9 13 10-11 3-4 15

```

Output not ordered correctly

# RULES

* Standard loopholes are disallowed
* If your language has a function to do this it's not allowed
* You may write a full program, or a function
* trailing whitespace doesn't matter

# SCORING

* Least bytes wins

# Answer
> 9 votes
# Python 2, ~~123~~ 120 bytes

```
N=sorted(map(int,raw_input().split(' ')));print(''.join((''if n+1in N else'-'+`n`)if n-1in N else' '+`n`for n in N)[1:])

```

If the input can be a list as a function argument then (thanks mbomb007 and xnor for the conditionals)

# ~~93~~ ~~90~~ 81 bytes

```
def f(N):print''.join((' '+`n`,`-n`*-~-(n+1in N))[n-1in N]for n in sorted(N))[1:]

```

(77 bytes if leading whitespace is acceptable - drop the final `[1:]`)

# Answer
> 7 votes
# JavaScript (ES6): ~~171~~ ~~154~~ 140 ~~137~~ bytes

Thanks edc65 and vihan1086 for the tips! ~~`[...n]` is very nice~~ but it doesn't work in these cases due to multi-digit numbers.

```
f=n=>{s=e=o='';n.split` `.map(Number).sort((a,b)=>a-b).map(v=>{s=s||v;if(e&&v>e+1){o+=`${s<e?s+'-'+e:s} `;s=v}e=v});return o+(s<e?s+'-'+e:e)}

```

## ES5 variant, ~~198~~ ~~184~~ ~~183~~ 174 bytes

```
f=function(n){s=e=o='';n.split(' ').map(Number).sort(function(a,b){return a-b}).map(function(v){s=s||v;if(e&&v>e+1){o+=(s<e?s+'-'+e:s)+' ';s=v}e=v});return o+(s<e?s+'-'+e:e)}

```

```
f = function (n) {
    s = e = 0, o = '';
    n.split(' ').map(Number).sort(function (a, b) {
        return a - b
    }).map(function (v) {
        s = s || v;
        if (e && v > e + 1) {
            o += (s < e ? s + '-' + e : s) + ' ';
            s = v
        }
        e = v
    });
    return o + (s < e ? s + '-' + e : e)
}

// Demonstration
document.body.innerHTML = f('1 2');
document.body.innerHTML += '<p>' + f('9 13 3 11 8 4 10 15 6');
document.body.innerHTML += '<p>' + f('11 10 6 9 13 8 3 4 15');
document.body.innerHTML += '<p>' + f('5 8 3 2 6 4 7 1');
document.body.innerHTML += '<p>' + f('5 3 7 1 9');
```

# Answer
> 5 votes
# SWI-Prolog, ~~165~~ ~~162~~ 159 bytes

```
b(Z,C,[D|E]):-Z=[A|B],(A=:=D+1,(B=[],put(45),print(A);b(B,C,[A,D|E]));(E=[],tab(1),print(A);writef('-%t %t',[D,A])),b(B,A,[A]));!.
a(A):-sort(A,B),b(B,_,[-1]).

```

Pretty bad but then again Prolog is a terrible golfing language

Example: `a([9,13,3,11,8,4,10,15,6]).` outputs `3-4 6 8-11 13 15`

# Answer
> 5 votes
# Ruby, 70 bytes

Problems like these tend to make me check the Ruby API for suitable methods, and today I discovered a new one: `Array#slice_when`, newly introduced in Ruby v2.2 and seemingly intended for this exact situation :)

```
f=->a{puts a.sort.slice_when{|i,j|j-i>1}.map{|x|x.minmax.uniq*?-}*' '}

```

After sorting and appropriately slicing the array, it takes each sub-array and creates a string out of the highest and lowest element, and then joins this whole array into a string.

Example:

`f.call [9,13,3,11,8,4,10,15,6]` prints `3-4 6 8-11 13 15`

# Answer
> 4 votes
# Ruby, ~~86~~ 84 bytes

```
s=->*a{puts a.sort.slice_when{|i,j|i+1!=j}.map{|e|e.size<2?e:[e[0],e[-1]]*"-"}*" "}

# demo
s[9, 13, 3, 11, 8, 4, 10, 15, 6]
# => 3-4 6 8-11 13 15

```

This is a slightly golfed version from an example in the docs for slice\_when.

# Answer
> 4 votes
# CJam, 35 bytes

```
l~${__0=f-ee::=0+0#/((oW>Wf*S+oe_}h

```

Try it online in the CJam interpreter.

### How it works

```
l~$     e# Read a line from STDIN, evaluate it and sort the result.
{       e# Do:
  _     e#   Push a copy of the array.
  _0=f- e#   Subtract the first element from all array elements.
  ee    e#   Enumerate the differences: [0 1 4] -> [[0 0] [1 1] [2 4]]
  ::=   e#   Vectorized quality: [i j] -> (i == j)
  0+    e#   Append a zero.
  0#    e#   Push the first index of 0.
  /     e#   Split the array into chunks of that size.
  (     e#   Shift out the first chunk.
  (o    e#   Print its first element.
  W>    e#   Discard all remaining elements (if any) except the last.
  Wf*   e#   Multiply all elements of the remainder by -1.
  S+o   e#   Append a space and print.
  e_    e#   Flatten the rest of the array.
}h      e# Repeat while the array is non-empty.

```

# Answer
> 3 votes
# CJam, ~~38~~ 33 bytes

New version, using ideas and code fragments suggested by @Dennis:

```
l~$_,,.-e`{~T+\_T+:T;(_2$+W*Q?S}/

```

Try it online

The input format is a CJam array in square brackets.

The basic idea here is that I subtract a monotonic sequence from the sorted input sequence first:

```
3  4  8  9 10 11 13 15
0  1  2  3  4  5  6  7  (-)
----------------------
3  3  6  6  6  6  7  8

```

In this difference, values that are part of the same interval have the same value. Applying the CJam RLE operator to this difference directly enumerates the intervals.

The subtracted sequential values need to be added back during output. I'm not entirely happy with how that's done in my code. I suspect that I could save a few bytes with a more elegant way of handing that.

For generating the output of the intervals, this uses Dennis' idea of generating a negative number for the end value, which takes care of producing a `-`, and also simplifies the logic because only one value needs to be added/omitted depending on the interval size.

Explanation:

```
l~    Get input.
$     Sort it.
_,,   Create monotonic sequence of same length.
.-    Calculate vector difference between the two.
e`    Calculate RLE of difference vector.
{     Loop over entries in RLE.
  ~     Unpack the RLE entry, now have length/value on stack.
  T+    Add position to get original value for start of interval.
  \     Bring length of interval to top of stack.
  _T+:T;  Add length of interval to variable T, which tracks position.
  (     Decrement interval length.
  _     Copy it, we need it once for calculating end value, once for ternary if condition.
  2$    Copy interval start value to top...
  +     ... and add interval length - 1 to get end value.
  W*    Negate end value.
  Q?    Output end value if interval length was > 1, empty string otherwise.
  S     Add a space.
}%    End loop.

```

# Answer
> 3 votes
# Jelly, 16 bytes

```
ṢI’kƊ.ịⱮUQ€j€”-K

```

Try it online!

## How it works

```
ṢI’kƊ.ịⱮUQ€j€”-K - Main link. Takes an array L on the left
Ṣ                - Sort L; Call this A
    Ɗ            - Monad. Link the previous three links together f(A):
 I               -   Forward differences
  ’              -   Decrement
   k             -   Partition
                   This groups consecutive runs
                   Take A = [3, 4, 6, 8, 9, 10, 11, 13, 15]
                   I: [1, 2, 2, 1, 1, 1, 2, 2]
                   ’: [0, 1, 1, 0, 0, 0, 1, 1]
                   k then partitions A at truthy elements in I’
                   [[3, 4], [6], [8, 9, 10, 11], [13], [15]
       Ɱ         - For each:
     .ị          -   Take the 0.5th element

                   For non-integer left argument, x, Jelly's ị atom takes
                   floor(x) and ceil(x) and returns [floor(x)ịy, ceil(x)ịy]
                   As Jelly's indexing is 1-based and modular:
                     0ị returns the last element
                     1ị returns the first element
                     .ị returns [0ị, 1ị]

        U        - Reverse each
         Q€      - Deduplicate each
           j€”-  - Join each with "-"
               K - Join by spaces

```

# Answer
> 3 votes
# Husk, ~~21~~ 20 bytes

```
;moJ'-?I§e←→ε†sġ·=←O

```

Try it online!

A bit lacking in the strings department, but does well.

No matter what I tried, it somehow stubbornly stayed at 21.

-1 byte from Dominic Van Essen.

## Explanation

```
;moJ'-?I§e←→ε†sġ§=…eO
                    O order the list
               ġ      group the list by the following:
                   e  elements paired
                §=    equal
                  …   the range between them?
             †s       convert all the numbers to strings
 mo                   map each group to the following:
      ?     ε         if it's a single element:
       I              leave as is
        §e←→          otherwise, move the first and last elements to a list
   J'-                join with '-'
;                     nest to display in one line

```

# Answer
> 2 votes
## CoffeeScript, ~~178~~ 161 bytes

Just like my JavaScript answer. I need to figure out if using comprehensions will result in shorter code.

```
f=(n)->s=e=o='';n.split(' ').map(Number).sort((a,b)->a-b).map((v)->s=s||v;(o+=s+(if s<e then'-'+e else'')+' ';s=v)if(e&&v>e+1);e=v);o+(if s<e then s+'-'else'')+e

```

---

Original:

```
f=(n)->o='';s=e=0;n.split(' ').map(Number).sort((a,b)->a-b).forEach((v,i)->if!i then s=v else(o+=s+(if s<e then'-'+e else'')+' ';s=v)if(v!=e+1);e=v);o+(if s<e then s+'-'else'')+e

```

# Answer
> 1 votes
# Python 2, ~~126~~ ~~122~~ 121 Bytes

I know this can get shorter, just don't know where.. Requires input in form `[#, #, #, #, ..., #]`.

```
l=sorted(input());s=`l[0]`;c=0;x=1
while x<len(l):y,z=l[x],l[x-1];s+=(('-'+`z`)*c+' '+`y`)*(y-z>1);c=(y-z<2);x+=1
print s

```

# Answer
> 1 votes
# Java, 191 bytes

```
void f(int[]a){java.util.Arrays.sort(a);for(int b=a.length,c=b-1,i=0,j=a[0],l=j;++i<b;){if(a[i]!=++j||i==c){System.out.print((l+1==j?l+(i==c?" "+a[c]:""):l+"-"+(i==c?j:j-1))+" ");l=j=a[i];}}}

```

Checks for ranges and prints them accordingly. Unfortunately I had to make a special case for the last element in the array since the program would terminate without printing the last number or range.

# Answer
> 1 votes
# Java, ~~171~~ 162 bytes

```
String s(int[] n){Arrays.sort(n);int p=0,b=0;String r="",d="";for(int c:n){if(c==++p)b=1;else{if(b==1){r+="-"+--p+d+c;p=c;b=0;}else{r+=d+c;p=c;}d=" ";}}return r;}

```

Takes input as an int array, returns output as a space-separated String list

# Answer
> 1 votes
# Japt `-S`, ~~17~~ 16 bytes

```
ÍòÈnYÉÃ®é ¯2 Ôq-

```

Try it

# Answer
> 1 votes
# Vyxal `S`, 120 bitsv1, 15 bytes

```
s:¯Ǐ⁽ṅḋ•ꜝƛ₍htU\-j

```

Try it Online!

## Explained

```
s:¯Ǐ⁽ṅḋ•ꜝƛ₍htU\-j
s:                 # Push two copies of the input list but sorted
  ¯Ǐ               # Forward differences of items with the first item appended - this is for making sure the length of the deltas matches the length of the input
    ⁽ṅḋ            # Grouped by whether they are <= 1
       •           # Reshape the sorted input to that shape
        ꜝ          # and remove the 0
                   # the top of the stack will be a list of lists of numbers that are ranges
         ƛ         # to each range
          ₍htU     #   either get the first and last item or just the first
              \-j  #   join on "-"
# S flag joins the result on spaces

```

# Answer
> 1 votes
# Scala, 204 bytes

Modified from @steenslag's Ruby answer.

---

Golfed version. Try it online!

```
def s(a:Int*):Seq[String]={val s=a.sorted;(Seq[Seq[Int]](Seq(s(0)))/:s.sliding(2)){(c,p)=>if(p(0)+1==p(1))c.init:+(c.last:+p(1))else c:+Seq(p(1))}.map(r=>if(r.size<2)r.mkString else s"${r(0)}-${r.last}")}

```

Ungolfed version. Try it online!

```
object Main {
  def s(a: Int*): Unit = {
    val sorted = a.sorted
    val sortedRanges = sorted.sliding(2).foldLeft(List[List[Int]](List(sorted.head))) { (acc, pair) =>
      if (pair(0) + 1 == pair(1)) acc.init :+ (acc.last :+ pair(1))
      else acc :+ List(pair(1))
    }
    val ranges = sortedRanges.map(range => if (range.size < 2) range.mkString else s"${range.head}-${range.last}")
    println(ranges.mkString(" "))
  }

  def main(args: Array[String]): Unit = {
    s(9, 13, 3, 11, 8, 4, 10, 15, 6)
  }
}

```

# Answer
> 1 votes
# Haskell, 187 bytes

```
import Data.List
g p[x]=[[x]]
g p(a:b:c)|let(d:e)=g p(b:c)=if p a b then(a:d):e else[a]:(d:e)
p[x]=show x++" "
p x=show(head x)++"-"++show(last x)++" "
f=concatMap p.g(((-1==).).(-)).sort

```

Try it online!

# Answer
> 0 votes
# Ly, 35 bytes

```
a0r[r0Ir::u[ps`=]pl~!['-olu!]p' o];

```

Try it online!

This is pretty brute force. It sorts the numbers then iterates until all the numbers have been consumed. After printing the "current" number on the stack, an inner loop consumes all the entries after that which are consequitive. Then it either appends a `-#` string or not before printing a space and iterating again.

```
# prep work... created sorted list of numbers with trailing "0"
a0r
a    - read numbers from STDIN, sort stack
 0   - push a "0"
  r  - reverse stack

# loop over all numbers, then exit
[                             ];
[                             ]   - iterate while top of stack not "0"
                               ;  - exit to avoid dumping junk on stack

# remember the current number for comparison later
r0Ir
r     - reverse stack
 0I   - copy bottom of stack entry to the top
   r  - reverse the stack

# print the current number, loop/consume all sequential nums on stack
::u[ps`=]p
::          - duplicate top of stack twice
  u         - print current number
   [    ]p  - loop until top of stack is "0"
    p       - delete previous number
     s      - save the current number
      `=    - increment current number, compare to next num on stack

# print "-X"  if needed to cover delete numbers, then print space
l~!['-olu!]p' o
l                - load saved num (last number deleted)
 ~               - search stack for that number
  !              - negate result
   [      ]p     - "then" code block
    '-o          - print "-"
       lu        - load last num in sequence (last deleted)
         !       - flip top of stack to "0" to exit loop
            ' o  - print " "

```

# Answer
> 0 votes
# Perl 5 `-pa`, 95 bytes

```
$_=join$",sort{$a-$b}@F;$b=$_,s/(\d+)\K (?=(\d+))/$2-$1-1?$":"-"/ge while$_ ne$b;s/(-\d+)+/$1/g

```

Try it online!

---
Tags: code-golf
---


# Question
Title: How many Carlitz compositions are there?
OEIS sequence A003242 comprises the numbers of Carlitz compositions for any given positive integer. This is the number of integer partitions of the integer for which no two adjacent parts are equal.

For example, for 4:

1. Generate the possible integer partitions (and their permutations): `[1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [1,3], [3,1], [2,2], [4]`
2. Filter out those which have adjacent equal parts, leaving: `[1,2,1], [1,3], [3,1], [4]`
3. Count, giving us our result of 4

The first 16 terms, using zero-indexing are:

`1, 1, 1, 3, 4, 7, 14, 23, 39, 71, 124, 214, 378, 661, 1152, 2024`

Pleasingly, the recently arrived year, 2024, is the value of this sequence where \\$n = 15\\$.

This is code golf, so the shortest answer in bytes per language wins. Standard loopholes are forbidden. This is also a sequence challenge, so you may take an integer argument and return the nth term, take an integer argument and return the first n terms, or take no arguments and return the infinite sequence. You may use zero- or one- indexing.

# Answer
> 8 votes
# Maxima, 54 bytes

The G.f.(Generating function) of the sequence is:

$$ \frac{1}{1 - \sum\limits\_{k\>0} \frac{x^k}{(1+x^k)}} $$

---

Golfed version (process-oriented programming, 42 bytes). Try it online!

```
taylor(1/(1-sum(x^k/(1+x^k),k,1,N)),x,0,N)

```

Golfed version (lambda function that returns the first `N` terms, 54 bytes). Try it online!

```
lambda([N],taylor(1/(1-sum(x^k/(1+x^k),k,1,N)),x,0,N))

```

# Answer
> 6 votes
# Nekomata \+ `-n`, 5 bytes

```
řJĉᵐz

```

Attempt This Online!

```
řJĉᵐz   Take input n
ř       Generate a list of n copies of n
            e.g. 3 -> [3,3,3]
 J      Non-deterministically split into a list of sublists
            e.g. [3,3,3] -> [[3],[3],[3]] or [[3],[3,3]] or [[3,3],[3]] or [[3,3,3]]
  ĉ     Split into runs of identical elements
            e.g. [[3],[3],[3]] -> [[[3],[3],[3]]]
                 [[3],[3,3]]   -> [[[3]],[[3,3]]]
                 [[3,3],[3]]   -> [[[3,3]],[[3]]]
                 [[3,3,3]]     -> [[[3,3,3]]]
   ᵐz   Check if each run has length 1
            e.g. [[[3],[3],[3]]] fails, others pass

```

`-n` counts the number of solutions. In the example above, there are 3 solutions that pass the final check, so the output for `3` is `3`.

# Answer
> 4 votes
# Haskell, ~~64~~ 44 bytes

***-20 bytes** thanks to @xnor!*

```
p#0=1
p#n=sum[i#(n-i)|i<-[1..n],i/=p]
f=(0#)

```

Try it online!

# Answer
> 3 votes
# Vyxal, 11 bytes

```
ṄvṖÞfU'¯A;L

```

Try it Online!

```
Ṅ           # Integer partitions
 vṖÞf       # All permutations of each
     U      # Uniquified
      '  ;  # Filtered by
       ¯    # Consecutive differences
        A   # Are all nonzero
          L # Length

```

# Answer
> 3 votes
# Haskell \+ hgl, 13 bytes

```
l<pST(fo<pnq)

```

Attempt This Online!

## Explanation

Does the task as straight forward as possible:

* `l` number of
* `pST` partitions such that
* `fo` all
* `pnq` consecutive elements are non-equal

Notably because `pST` works on any type of free monoid, you can give this a list as well.

# Reflection

I am quite happy with this answer. The one thing I would add is a function which precomposes `l` with `pST`.

# Answer
> 2 votes
# JavaScript (Node.js), 44 bytes

```
f=(n,e,i=n)=>i?f(n,e,i-1)+(i^e&&f(n-i,i)):!n

```

Try it online!

n(input) e(last choice) i(loop)

# Answer
> 2 votes
# Charcoal, 30 bytes

```
⊞υ⟦¹⟧ＦＮ⊞υＥ⁺²ι∧κΣＥ§υ±κ∧⁻νκμＩΣ⊟υ

```

Try it online! Link is to verbose version of code. Explanation: Uses dynamic programming to calculate the number of permutations of `n` that end in each of the values `1` .. `n`.

```
⊞υ⟦¹⟧

```

Start with `1` empty permutation for `n=0`.

```
ＦＮ

```

Repeat `n` times.

```
⊞υＥ⁺²ι∧κΣＥ§υ±κ∧⁻νκμ

```

For each `i` from `1` to `n`, calculate how many of the permutations of `n-i` do not end in `i`.

```
ＩΣ⊟υ

```

Output the total number of permutations for `n`.

# Answer
> 2 votes
# , ~~91~~ 84 bytes

```
\(n)sum(sapply(unique(combn(rep(0:n,n),n,\(x)x[x>0],F)),\(y)sum(y)==n&all(diff(y))))

```

Attempt This Online!

Starts from `1`.

# Answer
> 2 votes
# APL(Dyalog Unicode), ~~34,25~~21 bytes SBCS

```
{≢⍸(∧/2≢/⊂⍨)¨2|⍳2⌊⍳⍵}

```

Try it on APLgolf!

-4 bytes thanks to att.

A function which takes a positive integer on the right and returns the numbers of Carlitz compositions for that number.

### Explanation

```
{≢⍸(∧/2≢/⊂⍨)¨2|⍳2⌊⍳⍵}
                  ⍳⍵   ⍝ 1,2,3,...,input
                2⌊     ⍝ min each with 2
               ⍳       ⍝ range
                       ⍝   on an array, all combinations of ranges
             2|        ⍝ each mod 2
   (       )¨          ⍝ for each:
         ⊂⍨            ⍝ partition itself, splitting on 1s
      2≢/              ⍝ tests if consecutive runs don't match
    ∧/                 ⍝ AND reduce
                       ⍝   tests if all consecutive don't match
  ⍸                    ⍝ locations of 1s
 ≢                     ⍝ count

```

Created with the help of Luminespire.

# Answer
> 2 votes
# 05AB1E, 9 bytes

```
и.œʒÅγP}g

```

Port of *alephalpha*'s Nekomata answer, so make sure to upvote that answer as well!

Try it online or verify all test cases.

A straight-forward approach would be **12 bytes** instead:

```
ÅœεœÙεüÊP]˜O

```

Try it online or verify the first 9 test cases.

**Explanation:**

```
и         # Repeat the (implicit) input the (implicit) input amount of times as list
 .œ       # Get all partitions of this list
   ʒ      # Filter it by:
    Åγ    #  Run-length encode it; pushing a list of values and lengths
      P   #  Take the product of the list of lengths
          #  (only 1 is truthy in 05AB1E)
   }g     # After the filter: pop and push the length
          # (which is output implicitly as result)

```

```
Åœ        # Get all (sorted) lists of positive integers that sum to the (implicit) inpt
  ε       # Map over each inner list:
   œ      #  Get all its permutations
    Ù     #  Uniquify this list of lists
     ε    #  Inner map over each unique permutation-list:
      ü   #   Map over each overlapping pair of values:
       Ê  #    Check that they are NOT the same
        P #   Check that this is truthy for all of them in this permutation
  ]       # Close the nested maps
   ˜      # Flatten the list of lists
    O     # Sum all truthy values together
          # (which is output implicitly as result)

```

# Answer
> 1 votes
# Desmos, ~~106~~ 104 bytes

```
f(k)=1+∑_{n=2}^{k^k}0^{(B.total-k)^2}sgn(BB[2...]-BB)^2.min
B=mod(floor(n/k^{[floor(log_kn)...-1]}),k)

```

Try It On Desmos!

Try It On Desmos! - Prettified

Brute force but horribly inefficient. I tried looking at the other answers for some other methods but I'm too smooth brained to understand any of it so I just decided to do brute force lmfao. This is definitely slower than \\$O(k^k)\\$ time complexity, where \\$k\\$ is input. It can only run inputs \\$0\\$ through \\$7\\$ in a reasonable amount of time, and \\$8\\$ took a couple minutes to run, but still returned the right answer, \\$39\\$ (you can try this yourself if you have a bit of time to kill lol). I would not suggest you try \\$9\\$, unless you got supercomputers or something.

But with that being said, I still like this answer because it involves a bit of ingenuity by combining two conditions into one with `sgn(BB[2...]-BB)^2.min`. I tried to combine the third condition, `0^{(B.total-k)^2}`, into there as well, but couldn't think of a way to make it work. I might post an explanation in the near future to elaborate further on this.

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


title: Name the Dutch ancestor

text:
# Question
Title: Name the Dutch ancestor
The Dutch system for naming one's ancestors is a lot more interesting than the English version. For English, the sequence goes "parent", "grandparent", "great-grandparent", "great-great-grandparent", "great-great-great-grandparent"; and in Dutch those terms are "ouder", "grootouder", "*over*grootouder", "*bet*overgrootouder", "*stam*ouder". And so it continues with a non-positional mixed-radix counting system that produces unique names for up to 513 generations.

To not make this a mere string compression challenge, you can use the initials for each keyword. The pattern is like this:

| Generation | Full Dutch name | Initialism (return this) | Note |
| --- | --- | --- | --- |
| 1 | proband |  | Return nothing (whitespace allowed) |
| 2 | ouder | O |  |
| 3 | grootouder | GO |  |
| 4 | overgrootouder | OGO |  |
| 5 | betovergrootouder | BOGO |  |
| 6 | oudouder | OO | 2 with prefix "oud" |
| 7 | oudgrootouder | OGO | 3 with prefix "oud" |
| 8 | oudovergrootouder | OOGO | 4 with prefix "oud" |
| 9 | oudbetovergrootouder | OBOGO | 5 with prefix "oud" |
| 10 to 17 | stamouder to stamoudbetovergrootouder | SO to SOBOGO | 2 to 9 with prefix "stam" |
| 18 to 33 | edelouder to edelstamoudbetovergrootouder | EO to ESOBOGO | 2 to 17 with prefix "edel" |
| 34 to 65 | voorouder to vooredelstamoudbetovergrootouder | VO to VESOBOGO | 2 to 33 with prefix "voor" |
| 66 to 129 | aartsouder to aartsvooredelstamoudbetovergrootouder | AO to AVESOBOGO | 2 to 65 with prefix "aarts" |
| 130 to 257 | opperouder to opperaartsvooredelstamoudbetovergrootouder | OO to OAVESOBOGO | 2 to 129 with prefix "opper" |
| 258 to 513 | hoogouder to hoogopperaartsvooredelstambetovergrootouder | HO to HOAVESOBOGO | 2 to 257 with prefix "hoog" |

### Challenge

Take a number between 1 and 513 inclusive. Return the appropriate abbreviated Dutch ancestor term; case doesn't matter. It's , the shortest code wins!

### Test cases

```
input;output
1;
2;O
4;OGO
6;OO
9;OBOGO
267;HSGO
513;HOAVESOBOGO

```

# Answer
# Jelly, 29 bytes

```
7ŒPUṢị“OSEVAOH”p“OGOB”UƤ¤⁶;ị@

```

A full program taking an integer argument and outputting a string to STDOUT. When called as a link, will produce a list of two strings (other than for 1); these are implicitly concatenated when run as a full program.

## Explanation

```
7ŒP                            | Power set of 1..7
   U                           | Reverse each list
    Ṣ                          | Sort
     ị“OSEVAOH”                | Index into "OSEVAOH"
               p“OGOB”UƤ¤      | Cartesian product with reversed prefixes of "OGOB"
                         ⁶;    | Prefix with space, to handle the proband case
                           ị@  | Index the original link argument into this

```
> 7 votes

# Answer
# Python, 72 bytes

```
f=lambda i:i>5and"OSEVAOH"[m:=len(bin(i-2))-5]+f(i-(4<<m))or"BOGO"[5-i:]

```

Attempt This Online!
> 5 votes

# Answer
# Jelly, 33 bytes

```
_2d4+Ø.Ub"Ø½U“OGOB“OSEVAOH”x"FUḣ’

```

Try it online!

This is... not good...
> 3 votes

# Answer
# Charcoal, 32 bytes

```
¿⊖θ«⮌ΦOSEVAOH＆⁴÷⁻θ²Ｘ²κ✂BOGO﹪⁻¹θ⁴

```

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

```
¿⊖θ«

```

Do nothing if the input is `1`.

```
⮌ΦOSEVAOH＆⁴÷⁻θ²Ｘ²κ

```

Work out which prefixes to output according to the binary representation of `(n-2)//4`.

```
✂BOGO﹪⁻¹θ⁴

```

Work out how much of betovergrootouder to output.
> 3 votes

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

```
n=>[...'HOAVESOBOGO'].filter(x=>i-->2?n>0&n>>i:n%4>i+1,i=9,n-=2)

```

Try it online!

Returns array

# JavaScript (Node.js), 75 bytes

```
f=(n,i=7)=>i--?n-1>4<<i?'OSEVAOH'[i]+f(n-(4<<i),i):f(n,i):'BOGO '.slice(-n)

```

Try it online!
> 2 votes

# Answer
# Haskell, 78 bytes

```
g n|n<6=drop(5-n)"BOGO"
g n=[p:g(n-2^s)|(p,s)<-zip"HOAVESO"[8,7..],2^s+1<n]!!0

```

Try it online!
> 2 votes

# Answer
# Scala 3, 121 bytes

A port of @mousetail's Python answer in Scala.

---

```
def f(i:Int):String={if(i>5){val m=Integer.toBinaryString(i-2).size-3;"OSEVAOH"(m)+f(i-(4<<m))}else"BOGO".substring(5-i)}

```

Attempt This Online!
> 2 votes

# Answer
# 05AB1E, ~~30~~ 29 bytes

```
.•1<P“Ï•6Ýæíè"ogob"ηíâ€S¯šI<è

```

Port of *@NickKennedy*'s Jelly answer, so make sure to upvote that answer as well.

Output as a list of lowercase characters.

Try it online or verify all test cases.

A port of *@Neil*'s Charcoal answer would be 1 byte longer:

```
≠.•1<P“Ï•IÍ4÷bRÏR.•ÇF•$-4%.$«×

```

Outputs as a lowercase string.

Try it online or verify all test cases.

**Explanation:**

```
        6Ý       # Push list [0,1,2,3,4,5,6]
          æ      # Pop and push the powerset of this
           í     # Reverse each inner list
.•1<P“Ï•    è    # Index each inner value into compressed string "osevaoh"
"ogob"           # Push this string
      η          # Pop and push its prefixes
       í         # Reverse each prefix
â                # Cartesian power of the two lists to get all possible pairs
 €               # Map over each pair:
  S              #  Convert the pair of strings to a flattened list of characters
   ¯š            # Prepend an empty list
     I           # Push the input
      <          # Decrease it by 1 to make it 0-based
       è         # Index it into the list of lists of characters
                 # (after which it is output implicitly)

```

```
≠                # Check if the (implicit) input is NOT 1
                 # (0 if input=1, 1 otherwise
.•1<P“Ï•         # Push compressed string "osevaoh"
        IÍ       # Push the input, and decrease it by 2
          4÷     # Integer-divide it by 4
            b    # Convert it to a binary string
             R   # Revert it
              Ï  # Keep the characters in "osevaoh" at the truthy bits
               R # Reverse that string
.•ÇF•            # Push compressed string "bogo"
     $           # Push 1 and the input
      -          # Subtract the input from the 1
       4%        # Modulo 4
         .$      # Remove that many leading characters from "bogo"
«                # Append the two substrings together
×                # Repeat this string the input==1 check amount of times
                 # (so input=1 becomes an empty string)
                 # (which is output implicitly as result)

```

See this 05AB1E tip of mine (section *How to compress strings not part of the dictionary?*) to understand why `.•1<P“Ï•` is `"osevaoh"` and `.•ÇF•` is `"bogo"` (Minor note: `"ogob"` and `.•4ā:•` are the same length, so no use compressing it.)
> 2 votes

# Answer
# Retina 0.8.2, ~~85~~ 70 bytes

```
.+
$*G
G$

G$
O
G{8}
S
GGGG
O
SS
E
EE
V
VV
A
AAAA
H
AA
O
GGG
BOG
GG
OG

```

Try it online! Link includes test cases. Explanation:

```
.+
$*G
G$

G$
O

```

Convert to unary using `G`s, subtract 1 to correct for the input being 1-indexed, then replace any last `G` with `O`, so it doesn't accidentally get converted below.

```
G{8}
S
GGGG
O
SS
E
EE
V
VV
A
AAAA
H
AA
O

```

Handle the `HOAVESO` prefixes, starting with `S` and working back to `H`, then finish with the `O`s (because `134` should become `OOO` and not `OS` or `HO`). Edit: Saved 15 bytes thanks to @Ausername.

```
GGG
BOG
GG
OG

```

Fix up any remaining multiple `G`s.

I tried this in Retina 1 but unfortunately cyclic transliteration just crashes out if the input is empty which is a shame as that's a legal output.

132 bytes to translate into Dutch: Try it online! Link includes test cases. Note: Based on my previous 85-byte solution.
> 1 votes

# Answer
# Retina, 54 bytes

```
11$
O
1(1)(?<1>\1\1)+
$#1
Y^`11d`G\O_B\OS\E\VA\O\H
G$

```

Attempt This Online!

Input in unary

## Explanation

So, given input \\$n\\$, this challenge is mostly to convert \\$n-2\\$ to binary.

---

```
11$
O

```

Replace the last two `1`s with an `O`. So we have \\$n-2\\$ (in unary) followed by `O`. (There will be a special case for input 1)

---

```
1(1)(?<1>\1\1)+
$#1

```

The regex matches any power of 2 that is ≥ 4, then we replace those with their log2.

This results in a list of digits 8~2 corresponding to the binary representation of \\$n-2\\$, followed by 0~3 `1`s representing the remainder of \\$(n-2) \div 4\\$ , followed by `O`.

For example if \\$n = 269\\$ (i.e. \\$n-2 = 267 = 100001011\_2 = 2^8 + 2^3 + 3\\$), the result is `83111O`

---

```
Y^`11d`G\O_B\OS\E\VA\O\H

```

From right to left, process each character as follows:

| Character | Output |
| --- | --- |
| First occurrence of `1` | `G` |
| Second occurrence of `1` | `O` |
| `0` (won't happen, but removing this mapping costs 1 byte so...) | Remove |
| Third occurrence of `1` | `B` |
| `2` | `O` |
| `3` | `S` |
| `4` | `E` |
| `5` | `V` |
| `6` | `A` |
| `7` | `O` |
| `8` | `H` |
| Other | Unchanged |

---

```
G$

```

The only thing left to do is to deal with \\$n=1\\$, which end up as a single `G`. Since any other valid input ends with an `O`, we can special case \\$n=1\\$ by "removing the last character if it is `G`"
> 1 votes

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

```
say+(map{(O,S,E,V,A,O,H)[--$i]x$_}(sprintf"%07b",$_/4)=~/./g),substr BOGO,3-($_&3)if($_-=2)+1

```

Try it online!
> 1 votes

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


title: Bloons TD 6 Ordered Upgrade Paths

text:
# Question
Title: Bloons TD 6 Ordered Upgrade Paths
# Background

The monkeys need your help again organizing their defense and have asked you, Benjamin the code monkey, to create a program that will list all tower upgrade options as they appear in your insta-monkey collection. Each tower has three unique upgrade "paths", called "top", "middle", and "bottom", each having a tier represented by a number between 0 and 5 inclusive (0 meaning no upgrade). Up to two paths may be chosen for upgrading, that is contain an upgrade tier 1 or greater. Additionally, only one "main" path can contain a tier 3 or greater, with the other upgrade path (if it exists) becoming the "crosspath".

Original question: Bloons TD 6 Upgrade Paths

# Task

Output in some reasonable format all valid upgrade path triples in *the given order* (the triples themselves are ordered). Triples can be represented in any reasonable way, such as 025 or 0-2-5. The triples must be distinguishable from each other in some way, so a flat list of numbers without triple delimiters is not allowed.

Here is the list of all 64 possible triples, as they appear in-game for your insta-monkey collection. The 5th tier (main path) monkeys are listed first, then 4th tier, etc. descending. For each main path position (top, middle, or bottom), the second tier crosspaths are listed, with the crosspath having the leftmost position listed first. Then the first tier crosspaths are listed, then no crosspath. For tier 1 and tier 0 monkeys, the same logic is followed, except duplicates are not listed.

```
5-2-0
5-0-2
5-1-0
5-0-1
5-0-0
2-5-0
0-5-2
1-5-0
0-5-1
0-5-0
2-0-5
0-2-5
1-0-5
0-1-5
0-0-5
4-2-0
4-0-2
4-1-0
4-0-1
4-0-0
2-4-0
0-4-2
1-4-0
0-4-1
0-4-0
2-0-4
0-2-4
1-0-4
0-1-4
0-0-4
3-2-0
3-0-2
3-1-0
3-0-1
3-0-0
2-3-0
0-3-2
1-3-0
0-3-1
0-3-0
2-0-3
0-2-3
1-0-3
0-1-3
0-0-3
2-2-0
2-0-2
2-1-0
2-0-1
2-0-0
0-2-2
1-2-0
0-2-1
0-2-0
1-0-2
0-1-2
0-0-2
1-1-0
1-0-1
1-0-0
0-1-1
0-1-0
0-0-1
0-0-0

```

# Answer
# Jelly, 18 bytes

```
6p3’Ż€Œ!€ẎQMNṭṀƲÞṚ

```

A niladic link taking no arguments and returning a list of triples.

## Explanation

```
6p3                | Cartesian product of 1..6 and 1..3
   ’               | Subtract 1
    Ż€             | Prefix each with zero
      Œ!€          | Permutations of each
         Ẏ         | Join outer lists
          Q        | Uniquify
           MNṭṀƲÞ  | Sort by negated maximal indices tagged onto maximum
                 Ṛ | Reverse

```
> 6 votes

# Answer
# Retina 0.8.2, 97 bytes

```

520$*¶

00$.`
.*(...)
$1,$1
%O^`\G\d
(.)(..,.*?\1(.)*)
$1$#3$2
O^`
.+,

G`0
A`[3-5].*[3-5]|[6-9]

```

Try it online! Link includes footer that prettifies the output. Explanation: Based on my answer to the linked question.

```

520$*¶

00$.`
.*(...)
$1,$1

```

List all the integers from `0` to `520` inclusive, padded to `3` digits, with each integer duplicated, the duplicates separated with a comma.

```
%O^`\G\d

```

Sort the first duplicate of each integer in descending order of digit.

```
(.)(..,.*?\1(.)*)
$1$#3$2

```

For each integer, after the largest digit in the sorted digits, insert another digit that is the number of digits appearing after the first occurrence of that digit in the original integer.

```
O^`

```

Sort the integers in reverse by this sort key.

```
.+,

```

Delete the sort key.

```
G`0

```

Only keep those integers with at least one `0` digit.

```
A`[3-5].*[3-5]|[6-9]

```

Discard those with more than one digit greater than `2` or with a digit greater than `5`.
> 3 votes

# Answer
# Python 3, 119 bytes

```
t=(0,1,2)
print(*{(*(x*(i==j)+y*(i==k)for i in t),):0for x in(5,4,3,2,1,0)for j in t for y in(2,1,0)for k in t if j-k})

```

A full program that takes no input and prints the ordered upgrade paths as Python tuples with a space separator.

**Try it online!**

### How?

Go through from a "big choice" of five through to zero placing this digit left-right, placing a "small choice" of two through to zero in each of the other positions in turn, each time placing a zero in the remaining position, then deduplicate the results while maintaining order.

```
  t=(0,1,2)                                # create "indices" tuple t = (0,1,2)
  for x in(5,4,3,2,1,0)                    # for "big choice" x=5..0
    for j in t                             # for index j (where we want to try to place x)
      for y in(2,1,0)                      # for "small choice" y=2..0
        for k in t                         # for index k (where we want to try to place y)
          if j-k                           # if these indices differ
            for i in t                     # go through the indices, i
              x*(i==j)+y*(i==k)            # and assign a value (x, y or 0)
           (                   )           # each triple (across i) as a generator
         (*                     ,)         # ...splat to a tuple
        {                         :0 ...}  # ...as the keys of a dictionary (to deduplicate keys)
 print(*                                 ) # ...splat to print function

```

Perhaps the `print(*{...})` could be `print({...})` it will then print the `dict` representation, which is in order of its keys (the upgrade path triples), but will also show the dummy values `: 0` along with each key.
> 2 votes

# Answer
# Charcoal, 57 bytes

```
≔ＥΦＥφ﹪%03dι∧№ι0∧›6⌈ι›²ΣＥι‹2λ⟦⌈ι±⌕ι⌈ι⁻ΣιΣ⌈ιι⟧θＷ⁻θυ⊞υ⌈ιＥυ⊟ι

```

Try it online! Link is to verbose version of code. Explanation: Based on my answer to the linked question.

```
≔ＥΦＥφ﹪%03dι∧№ι0∧›6⌈ι›²ΣＥι‹2λ⟦⌈ι±⌕ι⌈ι⁻ΣιΣ⌈ιι⟧θ

```

Generate all the valid triples, but then create a sort key of the maximum digit, the negated index of that digit in the triple, the other non-zero digit if any, and the triple.

```
Ｗ⁻θυ⊞υ⌈ι

```

Sort the triples in descending order by the keys.

```
Ｅυ⊟ι

```

Output just the triples. (This could be `Ｅυ⪫⊟ι-` to prettify the output at a cost of 2 bytes.)
> 1 votes

# Answer
# Haskell, 154 bytes

```
import Data.List
x=unlines[intersperse '-'s|s<-reverse$sortOn(\x->(maximum$zip x[1,0..],sort x))$mapM id$['0'..'5']<$[1..3],elem '0's,sum[1|x<-s,x>'2']<2]

```

Try it online!
> 1 votes

# Answer
# , 114 bytes

```
r=rowSums
a=apply
(b=(x=expand.grid(0:5,0:5,0:5))[r(x>2)<2&r(x>0)<3,])[order(-a(b,1,max),a(b,1,which.max),-r(b)),]

```

Attempt This Online!

A full program that prints a data frame with the relevant triples in rows. It also prints some redundant row and column names - hopefully that’s permissible.

The footer verifies that the data frame is correct when compared to the canonical answer.
> 1 votes

# Answer
# Python 3.8 (pre-release), 234 bytes

```
from itertools import*
s,r=sorted,range;[print('-'.join(map(str,p)))for p in s(set(chain.from_iterable(permutations(list(x)+[0])for x in s(product(r(6),r(3))))),key=lambda x:(max(x),-x.index(max(x)),sum(x),x,-x.index(s(x)[1])))[::-1]]

```

Try it online!
> 1 votes

---
Tags: code-golf, number, kolmogorov-complexity
---


title: Move to Right and left

text:
# Question
Title: Move to Right and left
## Task

Your task is to take an array of numbers as input, and produce a new one where each number has been shifted both right and left, leaving `0`s if no number fills a spot. This process can be represented graphically like this:

```
   [x]
  / | \
[x, 0, x]

```

This is done with every number in the list, with overlapping numbers being added. A list with two numbers would look like this:

```
   [x, y]
   / \/ \
  /  /\  \
[x, y, x, y]

```

With three numbers, you start to get overlaps, and addition:

```
   [x,  y,  z]
   / \/   \/ \
  /  /\   /\  \
[x, y, x+z, y, z]

```

## Example

A simple example is `[1]` gives `[1, 0, 1]` because

```
  [1]
  / \
 /   \
[1, 0, 1]

```

Another example

```
   [1, 2]
   /\ /\
  /  X  \
 /  / \  \
[1, 2, 1, 2]

```

Another example

```
   [1, 2, 3]
   /\ /\ /\
  /  X  X  \
 /  / \/ \ /\
[1, 2, 4, 2, 3]

```

## Image:

## Test cases

```
[1,2,3] => [1,2,4,2,3]
[4,2] => [4,2,4,2]
[1] => [1,0,1]
[7,4,5,6] => [7,4,12,10,5,6]
[1,2,4,2,1] => [1,2,5,4,5,2,1]
[1,0,1] => [1,0,2,0,1]
[1,0,2,0,1] => [1,0,3,0,3,0,1]
[8,7,6,5,4] => [8,7,14,12,10,5,4]
[1,4,9,16] => [1,4,10,20,9,16]
[1,2] => [1,2,1,2]

```

# Answer
> 11 votes
# Jelly, 3 bytes

```
ŻŻ+

```

Try it online!

Using hyper's oberservation

## How it works

```
ŻŻ+ - Main link. Takes a list L
ŻŻ  - Prepend two zeros
  + - Add elementwise

```

# Answer
> 6 votes
# Python 3, 38 bytes

```
lambda l:map(sum,zip(l+[0,0],[0,0]+l))

```

Try it online!

Also works in Python 2

# Answer
> 5 votes
# Factor \+ `pair-rocket`, 34 bytes

```
[ 0 => 0 prepend dup 2 rotate v+ ]

```

Try it online!

## Explanation

Infix syntax? In my Factor? You bet. `0 => 0` is 1 byte shorter than `{ 0 0 }` and does the same thing.

```
           ! { 1 2 3 }
0 => 0     ! { 1 2 3 } { 0 0 }
prepend    ! { 0 0 1 2 3 }
dup        ! { 0 0 1 2 3 } { 0 0 1 2 3 }
2 rotate   ! { 0 0 1 2 3 } { 1 2 3 0 0 }
v+         ! { 1 2 4 2 3 }

```

# Answer
> 4 votes
# , 28 bytes

```
function(x)c(0,0,x)+c(x,0,0)

```

Try it online!

Updates the related challenge.

Thanks to alephalpha for pointing out a bug.

# \>= 4.1, 21 bytes

```
\(x)c(0,0,x)+c(x,0,0)

```

Try it online!

# Answer
> 4 votes
# Haskell + hgl, 12 bytes

```
zdm~<ao[i,i]

```

## Explanation

`zdm` takes a `SemiAlign` of `Semigroup` elements and combines them with the semigroup action defaulting to the present value if only one is present.

That's a bit of a mouthful. In this case `zdm` takes two lists of numbers and zips them together with addition. In places where there is only one number to add (i.e. the longer end of a list) it just adds zero.

`ao` concats two lists so `ao[i,i]` adds two copies of `i` to the front. For integers `i=0` so this is the same as adding zero twice. With that we combine it with a monad operator `~<` and we get something that takes a list and `zdm`s it with a version of it with two zeros on the front.

I use `i` here because the result is a nice function which can work on more than just lists. For example it will also combine lists or strings in the natural way.

```
ghci> zdm~<ao[i,i]$[1,2,3]
[1,2,4,2,1]
ghci> zdm~<ao[i,i]$["a","b","c"]
["a","b","ca","b","c"]

```

## Reflections

`[i,i]` is pretty long. If I made an alias `Ki` for `K i` (or `K0` for `K 0`) this could be `zdm~<Ki<Ki` saving two bytes overall.

# Answer
> 4 votes
# convey, ~~14~~ 13 bytes

```
0+}
^,<<0
0"{

```

Try it online!

# Answer
> 3 votes
# , 10 bytes

```
0 0&(,+,~)

```

Try it online!

Obligatory nod to Iverson's favorite expression, as noted in comments by Bgil Midol.

Or, for one extra byte, in the prettier symmetric form:

```
0 0&,+,&0 0

```

# Answer
> 3 votes
# Desmos, 28 bytes

```
f(l)=join(l,0,0)+join(0,0,l)

```

Can't get much shorter than this as far as I'm aware.

Try It On Desmos!

Try It On Desmos! - Prettified

# Answer
> 3 votes
# Wolfram Mathematica, 18 bytes

```
{##,0,0}+{0,0,##}&

```

Just a Mathematica port of what other posters have done: Create two lists, where two zeros are appended to the input in one, and prepended to the input in the other, and add them.

Sample usage:

```
{##,0,0}+{0,0,##}&@@{8,7,6,5,4}

```

> {8, 7, 14, 12, 10, 5, 4}

# Answer
> 3 votes
# Ruby, 34 bytes

```
->a{(r=0,0,*a).zip(a+r).map &:sum}

```

Try it online!

# Answer
> 2 votes
# JavaScript (ES6), 34 bytes

*Saved 2 bytes thanks to @tsh*

```
a=>[0,0,...a].map((v,i)=>v+~~a[i])

```

Try it online!

# Answer
> 2 votes
# Octave, 19 bytes

```
@(a)conv(a,[1,0,1])

```

Try it online!

---

# Octave, 19 bytes

```
@(a)[a,0,0]+[0,0,a]

```

Try it online!

# Answer
> 2 votes
# 05AB1E (legacy), 5 bytes

```
2Å0ì+

```

Try it online or verify all test cases.

Uses the legacy version of 05AB1E, because the `+` will keep trailing items when lists are of different lengths, whereas the new 05AB1E version would ignore/remove them. In the new version of 05AB1E, this therefore would have been 7 bytes instead:

```
2Å0ì0ζO

```

Try it online or verify all test cases.

**Explanation:**

```
2Å0     # Push list [0,0]
   ì    # Prepend it front of the (implicit) input-list
    +   # Add the values at the same positions to the input-list,
        # keeping the additional trailing items
        # (after which the result is output implicitly)

2Å0ì    # Same as above
     ζ  # Zip/transpose with the (implicit) input-list, creating pairs,
    0   # using 0 as filler-item when lists are different in length
      O # Sum each inner pair
        # (after which the result is output implicitly)

```

# Answer
> 2 votes
# T-SQL, 94 bytes

```
SELECT sum(x)FROM(SELECT*FROM @
UNION SELECT x,i+2FROM @
UNION SELECT 0,i+1FROM @)y
GROUP BY i

```

**Try it online**

# Answer
> 1 votes
# Charcoal, 15 bytes

```
Ｆ²⊞θ⁰ＩＥθ⁺ι§θ⁻κ²

```

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

```
Ｆ²⊞θ⁰

```

Append two zeros to the input array.

```
ＩＥθ⁺ι§θ⁻κ²

```

Add the last but one element to each element of the array and output the result.

# Answer
> 1 votes
# x86-64 machine code, 16 bytes

```
89 d1 31 c0 99 03 06 ab ad 92 e2 f9 ab 92 ab c3

```

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes in RDI an address at which to place the result, as an array of 32-bit integers; the address of the given array in RSI; and the length of the given array in RDX.

In assembly:

```
f:
    mov ecx, edx    # Put the length in ECX.
    xor eax, eax    #  | Set EAX and EDX to 0.
    cdq             #  | These will hold the two previous numbers in that order,
repeat:             #  |  or 0 if nonexistent.
    add eax, [rsi]  # Add the current number to the twice-previous number.
    stosd           # Write the sum to the result array, advancing the pointer.
    lodsd           # Load the current number into EAX, advancing the pointer.
    xchg edx, eax   # Exchange EDX and EAX, putting the previous number into EAX
                    #                            and the current number into EDX.
    loop repeat     # Loop, counting down from the length in ECX.
    stosd           # Write the penultimate number to the result array,
                    #  advancing the pointer.
    xchg edx, eax   # Switch the last number into EAX.
    stosd           # Write the last number to the result array, advancing the pointer.
    ret             # Return.

```

# Answer
> 1 votes
# Husk, 5 bytes

```
Sż+‼Θ

```

Try it online!

Zips by addition the input together with itself after prepending two zeros:

```
Sż+‼Θ
S       # hook: Sfgx means f(x,g(x))
 ż      # f = zip together (keeping trailing elements)
  +     #     by addition:
   ‼    # g = apply twice
    Θ   #     prepend zero

```

(one byte (‼) longer than Ken Iverson’s Favourite Expression)

# Answer
> 1 votes
# BQN, ~~14~~ ~~12~~ 10 bytes

*Edit: -2 bytes (and a BQN lesson) thanks to ovs & Razetime*

```
2⊸⌽⊸+0‿0∾⊢

```

Try it at BQN online REPL

# Answer
> 1 votes
# TI-Basic, 17 bytes

```
augment({0,0},Ans)+augment(Ans,{0,0

```

Takes input in `Ans`.

# Answer
> 1 votes
# Zsh, ~~48~~ 42 bytes

```
a=(0 0 $@);for i ($@ 0 0)echo $[i+$a[++j]]

```

Try it Online!
~~48bytes~~ \- zip & add arrays

# Answer
> 1 votes
# Nekomata, 3 bytes

```
çç+

```

Attempt This Online!

```
çç+
ç       Prepend zero
 ç      Prepend zero
  +     Add

```

---

# Nekomata, 3 bytes

```
5Ƃ×

```

Attempt This Online!

```
5Ƃ×
5Ƃ      Binary digits of 5
  ×     Convolve

```

# Answer
> 0 votes
# Arturo, 34 bytes

```
$[a][map couple++a<=[0,0]++a=>sum]

```

```
$[a][                ; a function taking an argument a
    map ... =>sum    ; map over a block and take the sum of each element
    couple           ; aka zip
    ++a<=[0,0]       ; input ++ [0, 0]
    [0,0]++a         ; [0, 0] ++ input
]                    ; end function

```

# Answer
> 0 votes
# Uiua SBCS, 7 bytes

```
+↻2.⊂⊚2

```

Try it!

```
+↻2.⊂⊚2
     ⊚2  # a list with two zeros
    ⊂    # prepend
   .     # duplicate
 ↻2      # rotate by two elements
+        # add

```

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


title: Smashing Dominoes

text:
# Question
Title: Smashing Dominoes
# Challenge

This challenge is based on the domino effect:

**Initially, each domino is located on one straight line and is in a vertical state. It can be dropped either to the left along the same straight line, or to the right. Then this domino will knock down the next one, and that one, perhaps, the other.**

**The dominoes are each of different heights, and they are located at different distances.**

**Your task is to find the minimum number of dominoes that need to be knocked down manually.**

# Input

* The first line of the input data contains one integer `n (1≤n≤1000)` — the number of dominoes.
* The second line of the input contains `n` integers `x (1≤x≤10**9)` — the coordinates of dominoes. *It is sorted!*
* The third line of the input data contains `n` integers `h (1≤h<10**9)` — the heights of the dominoes.

# Output

* Output one number - the minimum number of dominoes that need to be knocked down manually.

# Tests

```
Input:
10
10 20 30 40 50 60 70 80 90 100
19 19 8 19 19 19 1 10 20 30

Output: 3

Input:
6
10 20 30 40 50 60
17 9 13 21 7 3

Output: 2

Input:
10
10 20 30 40 50 60 70 80 90 100
15 16 11 17 18 19 1 9 18 30

Output: 2

```

(Geogebra visualisation. "P" means pass, -\> or \<- : demolition directions)

# Scoring

This is , so the fastest algorithm scores the most. Here are the points based on your algorithm's complexity:

```
5 points for O(n!),

25 for O(x^n),

50 for O(n^x) where x≥3,

75 for O(n^x) where 2≤x<3,

80 for O(n*log(n)),

90 for O(n),

100 for O(n^x) where x<1, or O(log^x(n))

```

The first solution gets a 1.1 coefficient (already expired); a solution with an explanation may get extra points.

# Answer
> 1 votes
# Python 3 + Google OR-Tools, unknown complexity (probably exponential)

Uses a slightly modified set cover formulation.

```

from ortools.sat.python import cp_model

def min_push(positions, heights):
    model = cp_model.CpModel()
    push = [{} for _ in positions]
    for i, (p, h) in enumerate(zip(positions, heights)):
        for d in (-1, 1):
            j = i + d
            while 0 <= j < len(positions):
                if abs(positions[j] - p) > h:
                    break
                push[i][j] = model.NewIntVar(0, 1, f'push_{(i,j)}')
                j += d
    push_t = [{} for _ in positions]
    for i, d in enumerate(push):
        for j, v in d.items():
            push_t[j][i] = v
    for d in push_t:
        model.Add(sum(d.values()) <= 1)
    for i, d_i in enumerate(push):
        for j, v_ij in d_i.items():
            for k, v_jk in push[j].items():
                if ((j - i) > 0) != ((k - j) > 0):
                    model.Add(v_ij + v_jk <= 1)
    model.Maximize(sum(v for d in push for v in d.values()))
    solver = cp_model.CpSolver()
    solver.Solve(model)
    return int(len(positions) - solver.ObjectiveValue())

```

# Answer
> 0 votes
# MATLAB

I was trying to rewrite @user1502040's Python 3 + Google OR-Tools Answer in MATLAB.

\\$ \color{red}{\text{But there are some mistakes in my MATLAB code. Any help would be appreciated.}} \\$

```
clear all;close all;clc;

positions = [10 20 30 40 50 60 70 80 90 100];
heights = [19 19 8 19 19 19 1 10 20 30];
minPushes = min_push(positions, heights);
disp(minPushes);

positions = [10 20 30 40 50 60];
heights = [17 9 13 21 7 3];
minPushes = min_push(positions, heights);
disp(minPushes);

positions = [10 20 30 40 50 60 70 80 90 100];
heights = [15 16 11 17 18 19 1 9 18 30];
minPushes = min_push(positions, heights);
disp(minPushes);

function minPushes = min_push(positions, heights)
    % Number of dominoes
    numDominoes = length(positions);

    % Decision variables: push(i,j) is 1 if domino i pushes domino j, otherwise 0
    push = optimvar('push', numDominoes, numDominoes, 'Type', 'integer', 'LowerBound', 0, 'UpperBound', 1);

    % Create an optimization problem
    problem = optimproblem('ObjectiveSense', 'maximize');

    % Constraints for reachable pushes
    for i = 1:numDominoes
        for j = 1:numDominoes
            if i ~= j
                % Domino i can push domino j only if it's within reach
                distance = abs(positions(j) - positions(i));
                if distance <= heights(i)
                    % Constraint is satisfied implicitly by the definition of push variable
                else
                    % Domino i cannot push domino j because it's out of reach
                    problem.Constraints.(['outOfReach_' num2str(i) '_' num2str(j)]) = push(i, j) == 0;
                end
            end
        end
    end

    % Each domino is pushed at most once
    for j = 1:numDominoes
        problem.Constraints.(['pushOnce_' num2str(j)]) = sum(push(:, j)) <= 1;
    end

    % Prevent cycles in pushes
    for i = 1:numDominoes
        for j = 1:numDominoes
            if i ~= j
                for k = 1:numDominoes
                    if j ~= k && i ~= k
                        if ((j - i) > 0) ~= ((k - j) > 0)
                            problem.Constraints.(['noCycle_' num2str(i) '_' num2str(j) '_' num2str(k)]) = push(i, j) + push(j, k) <= 1;
                        end
                    end
                end
            end
        end
    end

    % Objective: maximize the number of pushes
    problem.Objective = sum(sum(push));

    % Solve the problem using an integer linear programming solver
    options = optimoptions('intlinprog','Display','off');
    [sol, fval, exitflag, output] = solve(problem,'Options',options);

    % Calculate the minimum number of dominoes that need to be pushed manually
    minPushes = numDominoes - fval;
end

```

---
Tags: optimization, fastest-algorithm
---


# Question
Title: Forward foo, reverse bar, but avoid dead code
So simple: Provide some code that outputs `foo` and with the reversed source outputs `bar`. But before you come up with something like this boring python 2:

```
print "foo"#"rab" tnirp

```

you should know the **score: You multiply the number of bytes with (1 + dead bytes)**, where dead bytes are bytes that can be changed to most other characters without changing the behaviour in the current execution direction (in the sense that more can be changed than not). This is valid for comments or labels or code after some exit statement or such workarounds (you know what I mean, so don't feel a hero because your language has some feature with a different name to ignore code). I want to see your creativity in reusing code depending on the direction!

**Examples** for score count

* In the example above, the `#` is no dead code, because you cannot simply replace it, but the following 11 bytes are dead code, thus we get a score of 23 * (1+11) = **276**! Valid, but not so nice anymore.
* A `sh` answer like `echo foo # rab ohce` would score a slightly better **190**.
* An `sed` answer `s:^:foo:;:rab:^:s` misuses the `:` label to hide code, but the label is still dead code, resulting in a score of **136**.
* `foo//rab` in `///` has the open `//` as valid exit, so this would have only three bytes of dead code, reaching a score of **32**.

**Rules**

* Dead code can be different for both directions, so **for scoring, the number of dead bytes for the worse direction is counted**: If you have three deads bytes forward, but 7 backwards, your multiplier will be 8.
* Your code must not output anything visible after the `foo` or `bar`, just something like whitespaces or newlines.
* `foo` and `bar` can be lowercase or uppercase, as you like
* Your program has to end execution by itself, so don't try to loophole through some infinite loop after output!
* Don't use any non-empty input, of course.
* Why do I add +1 to the dead bytes? Because I don't want a zero score for living-code-only answers like this `///` solution (actual score 65):
`foo/./::://:/\//:f.o.b.a.r::/\// //\/::r.a.b.o.f://\/://:::/./rab`
* Did I mention the **smallest score wins**?

# Answer
# Charcoal, 8 bytes, score 32

```
bar←←oof

```

Try it online! Outputs `foo`. Explanation: The first word is overprinted in reverse by the reversed second word. The second  is needed to overprint and the first  is needed to overprint in the correct location, but the first word can be e.g. any three ASCII characters.

```
foo←←rab

```

Try it online! Outputs `bar`.
> 4 votes

# Answer
# Vyxal 3, ~~11 * 6 = 66~~, 10 * 5 = 50

```
"rab""foo"

```

Forwards

```
"oof""bar"

```

Backwards
> 3 votes

---
Tags: code-challenge, kolmogorov-complexity
---


title: Triangular Dependencies

text:
# Question
Title: Triangular Dependencies
A triangular number is a number that is the sum of `n` natural numbers from 1 to `n`. For example `1 + 2 + 3 + 4 = 10` so `10` is a triangular number.

Given a positive integer (`0 < n <= 10000`) as input (can be taken as an integer, or as a string), return the smallest possible triangular number that can be added to the input to create another triangular number.

For example given input `26`, adding `10` results in `36`, which is also a triangular number. There are no triangular numbers smaller than `10` that can be added to `26` to create another triangular number, so `10` is the correct result in this case.

`0` is a triangular number, therefore if the input is itself a triangular number, the output should be `0`

## Testcases

Cases are given in the format `input -> output (resulting triangular number)`

```
0     -> 0   (0)
4     -> 6   (10)
5     -> 1   (6)
7     -> 3   (10)
8     -> 28  (36)
10    -> 0   (10)
24    -> 21  (45)
25    -> 3   (28)
26    -> 10  (36)
34    -> 21  (55)
10000 -> 153 (10153)

```

## Scoring

This is so fewest bytes **in each language** wins!

# Answer
# Java 8, 58 57 bytes

```
n->{int i=0,m=0;while(n!=0)n+=n<0?++i:--m;return-~i*i/2;}

```

Online test suite

Thanks to Dennis for a 1-byte saving.
> 21 votes

# Answer
# Java (OpenJDK 8), 83 bytes

```
n->{int m=0,a=n,b;for(;a-->0;)for(b=0;b<=n;)m=2*n+b*~b++==a*~a?a*a+a:m;return m/2;}

```

Try it online!

## Credits
> 7 votes

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

*1 byte removed using an idea (set intersection) from Emigna's 05AB1E answer*

```
Q:qYstG-X&X<

```

**Try it online!**

### Explanation

Let `t(n) = 1 + 2 + ··· + n` denote the `n`-th triangular number.

The code exploits the fact that, given `n`, the solution is upper-bounded by `t(n-1)`. To see this, observe that `t(n-1) + n` equals `t(n)` and so it is a triangular number.

Consider input `8` as an example.

```
Q:q   % Input n implicitly. Push [0 1 2 ... n]
      % STACK: [0 1 2 3 4 5 6 7 8]
Ys    % Cumulative sum
      % STACK: [0 1 3 6 10 15 21 28 36]
t     % Duplicate
      % STACK: [0 1 3 6 10 15 21 28 36], [0 1 3 6 10 15 21 28 36]
G-    % Subtract input, element-wise
      % STACK: [0 1 3 6 10 15 21 28 36], [-8 -7 -5 -2  2  7 13 20 28]
X&    % Set intersection
      % STACK: 28
X<    % Minimum of array (in case there are several solutions). Implicit display
      % STACK: 28

```
> 7 votes

# Answer
# Mathematica, 46 bytes

```
Min[Select[(d=Divisors[2#])-2#/d,OddQ]^2-1]/8&

```
> 6 votes

# Answer
# Neim, ~~12~~ 9 bytes

```
tSΛt)0

```

This takes too long to compute (but works given infinite time and memory), so in the link I only generate the first 143 triangular numbers - using `£`, which is enough to handle an input of 10,000, but not enough to time out.

Warning: this may not work in future versions. If so, substitute £ for 143

Explanation:

```
t                 Infinite list of triangular numbers
 [ ]             Select the first  v  numbers
 [£ ]                              143
     S           Subtract the input from each element
       Λ  )       Only keep elements that are
        t          triangular
           0     Get the value closest to 0 - prioritising the higher number if tie

```

Try it!
> 4 votes

# Answer
# PHP, 45 bytes

```
for(;!$$t;$t+=++$i)${$argn+$t}=~+$t;echo~$$t;

```

Try it online!

Is the shorter variant of `for(;!$r[$t];$t+=++$i)$r[$argn+$t]=~+$t;echo~$r[$t];`

Expanded

```
for(;!$$t;  # stop if a triangular number exists where input plus triangular number is a triangular number
$t+=++$i) # make the next triangular number
  ${$argn+$t}=~+$t; # build variable $4,$5,$7,$10,... for input 4
echo~$$t; # Output result

```

# PHP, 53 bytes

```
for(;$d=$t<=>$n+$argn;)~$d?$n+=++$k:$t+=++$i;echo+$n;

```

Try it online!

Use the new spaceship operator in PHP 7

Expanded

```
for(;$d=$t<=>$n+$argn;) # stop if triangular number is equal to input plus triangular number
  ~$d
    ?$n+=++$k  # raise additional triangular number
    :$t+=++$i; # raise triangular number sum
echo+$n; # Output and cast variable to integer in case of zero

```

# PHP, 55 bytes

```
for(;fmod(sqrt(8*($t+$argn)+1),2)!=1;)$t+=++$i;echo+$t;

```

Try it online!
> 4 votes

# Answer
# Java 8, ~~110~~ ~~102~~ ~~100~~ ~~93~~ 92 bytes

```
n->{int r=0;for(;t(r)<-t(n+r);r++);return r;}int t(int n){for(int j=0;n>0;n-=++j);return n;}

```

-2 bytes thanks to *@PeterTaylor*.
-7 bytes thanks to *@JollyJoker*.
-1 byte thanks to *@ceilingcat*.

**Explanation:**

Try it online.

```
n->{                  // Method with integer as parameter and return-type
  int r=0;            //  Result-integer (starting at 0)
  for(;t(r)<-t(n+r);  //  Loop as long as neither `r` nor `n+r` is a triangular number
    r++);             //   And increase `r` by 1 after every iteration
  return r;}          //  Return the result of the loop

int t(int n){         // Separate method with integer as parameter and return-type
                      // This method will return 0 if the input is a triangular number
  for(int i=0;n>0;)   //  Loop as long as the input `n` is larger than 0
    n-=++j;           //   Decrease `n` by `j` every iteration, after we've raised `j` by 1
  return n;}          //  Return `n`, which is now either 0 or below 0

```
> 4 votes

# Answer
# Brachylog, ~~17~~ 15 bytes

```
⟦{a₀+}ᶠ⊇Ċ-ṅ?∧Ċh

```

Try it online!

### Explanation

```
⟦                  [0, …, Input]
 {   }ᶠ            Find all…
  a₀+                …Sums of prefixes (i.e. triangular numbers)
       ⊇Ċ          Take an ordered subset of two elements
         -ṅ?       Subtracting those elements results in -(Input)
            ∧Ċh    Output is the first element of that subset

```
> 3 votes

# Answer
# Japt, ~~24~~ ~~23~~ ~~16~~ ~~15~~ 13 bytes

```
ò å+
m-N æ@øX

```

1 byte saved thanks to ETH.

Try it

```
ò å+\nm-N æ@øX     :Implicit input of integer U
ò                  :Range [0,U]
  å+               :Cumulatively reduce by addition
    \n             :Reassign to U
      m-           :Map and subtract
        N          :  The array of inputs (i.e., the original value of U)
         æ         :Get the first element that return true when
          @        :Passed through the following function as X
           øX      :  Does U contain X

```
> 3 votes

# Answer
# Octave, ~~38~~ 36 bytes

*2 bytes off thanks to @Giuseppe!*

```
@(n)(x=cumsum(0:n))(any(x+n==x'))(1)

```

Anonymous function that uses almost the same approach as my MATL answer.

**Try it online!**
> 3 votes

# Answer
# Jelly, 8 bytes

```
0r+\ðf_Ḣ

```

Try it online!

### How it works

```
0r+\ðf_Ḣ  Main link. Argument: n

0r        Build [0, ..., n].
  +\      Take the cumulative sum, generating A := [T(0), ..., T(n)].
    ð     Begin a dyadic chain with left argument A and right argument n.
      _   Compute A - n, i.e., subtract n from each number in A.
     f    Filter; keep only numbers of A that appear in A - n.
       Ḣ  Head; take the first result.

```
> 3 votes

# Answer
# Python 2, 59 bytes

```
lambda n:min((r-2*n/r)**2/8for r in range(1,2*n,2)if n%r<1)

```

Try it online!

This uses the following characterization of the triangular numbers `t` than can be added to `n` to get a triangular number:

> `8*t+1 = (r-2*s)^2` for divisor pairs `(r,s)` with `r*s==n` and `r` odd.

The code takes the minimum of all such triangular numbers.
> 3 votes

# Answer
# C (GCC), ~~58 55 54~~ 52 bytes

```
i;s;f(n){for(i=s=0;n;)n+=n<0?++i:--s;return-~i*i/2;}

```

Attempt This Online!

**EDIT**: *-3 bytes* by removing `!=0`

**EDIT**: *-1 byte* by moving variable declarations to a `for`

**EDIT**: *-2 bytes* by moving variable declarations outside the function, thanks to ceilingcat

# Explanation

```
i;s;f(n){for(i=s=0;n;)n+=n<0?++i:--s;return-~i*i/2;}
i;s;                                                  // Declare i and s
    f(n){                                          }  // Declare function:
             i=s=0;                                   // * Set i and s to 0
         for(      n;)                                // * While n not 0:
                      n+=n<0?++i:--s;                 // * * Increment i and add to n if n < 0
                                                      //     Otherwise, decrement s and add to n
                                     return-~i*i/2;   // * Return i*(i+1)/2

```

Created with the help of Luminespire.
> 3 votes

# Answer
# Mathematica, 62 bytes

```
(s=Min@Abs[m/.Solve[2#==(n-m)(n+m+1),{n,m},Integers]])(s+1)/2&

```
> 2 votes

# Answer
# JavaScript (ES7), ~~46~~ 44 bytes

```
f=(n,x=r=0)=>(8*(n+x)+1)**.5%1?f(n,x+=++r):x

```

---

## Try it

```
o.innerText=(
f=(n,x=r=0)=>(8*(n+x)+1)**.5%1?f(n,x+=++r):x
)(i.value=8);oninput=_=>o.innerText=f(+i.value)
```

```
<input id=i type=number><pre id=o>
```
> 2 votes

# Answer
# Python 2, ~~78~~ ~~71~~ 70 bytes

Seven bytes saved, thanx to ovs and theespinosa

One more byte saved due to the remark of neil, `x+9` is suffisant and checked for all natural numbers `0 <= n <= 10000`. It was also verified for `x+1` instead of `x+9`, it works also.

```
x=input()
I={n*-~n/2for n in range(x+1)}
print min(I&{i-x for i in I})

```

Try it online!
> 2 votes

# Answer
# 05AB1E, 12 bytes

```
ÝηOãD€Æ¹QÏ¬¤

```

Uses the **05AB1E** encoding. Try it online!
> 2 votes

# Answer
## JavaScript (ES6), ~~43~~ 42 bytes

```
f=(n,a=s=0)=>n?f(n+=n>0?--s:++a,a):a*++a/2
```

```
<input type=number min=0 value=0 oninput=o.textContent=f(+this.value)><pre id=o>0
```

Edit: Saved 1 byte thanks to @PeterTaylor.
> 2 votes

# Answer
# 05AB1E, 8 bytes

```
ÝηODI-Ãн

```

Try it online! or as a Test suite

**Explanation**

```
Ý          # range [0 ... input]
 η         # prefixes
  O        # sum each
   D       # duplicate
    I-     # subtract input from each
      Ã    # keep only the elements in the first list that also exist in the second list
       н   # get the first (smallest)

```
> 2 votes

# Answer
# Python 3, ~~60~~ 44 bytes

```
f=lambda n,k=1:(8*n+1)**.5%1and f(n+k,k+1)+k

```

*Thanks to @xnor for a suggestion that saved 16 bytes!*

Try it online!

### Background

Let **n** be a non-negative integer. If **n** is the **k**th triangular number, we have

which means there will be a natural solution if and only if **1 + 8n** is an odd, perfect square. Clearly, checking the parity of **1 + 8n** is not required.

### How it works

The recursive function **n** accepts a single, non-negative integer as argument. When called with a single argument, **k** defaults to **1**.

First, `(8*n+1)**.5%1` tests if **n** is a triangular number: if (and only if) it is, `(8*n+1)**.5` will yield an integer, so the residue from the division by **1** will yield **0**.

If the modulus is **0**, the `and` condition will fail, causing **f** to return **0**. If this happens in the initial call to **f**, note that this is the correct output since **n** is already triangular.

If the modulus is positive, the `and` condition holds and `f(n+k,k+1)+k` gets executed. This calls **f** again, incrementing **n** by **k** and **k** by **1**, then adds **k** to the result.

When **f(n0, k0)** finally returns **0**, we back out of the recursion. The first argument in the first call was **n**, the second one **n + 1**, the third one **n + 1 + 2**, until finally **n0 = n + 1 + … k0-1**. Note that **n0 \- n** is a triangular number.

Likewise, all these integers will be added to the innermost return value (**0**), so the result of the intial call **f(n)** is **n0 \- n**, as desired.
> 2 votes

# Answer
# C# (.NET Core), ~~291~~ 281 bytes

```
class p{static int Main(string[]I){string d="0",s=I[0];int c=1,j,k;for(;;){j=k=0;string[]D=d.Split(' '),S=s.Split(' ');for(;j<D.Length;j++)for(;k<S.Length;k++)if(D[j]==S[k])return int.Parse(D[k]);j=int.Parse(D[0])+c++;d=d.Insert(0,$"{j} ");s=s.Insert(0,$"{j+int.Parse(I[0])} ");}}}

```

Try it online! Program that takes a string as input and outputs through Exit Code.

Saved 10 Bytes thanks to Kevin Cruijssen
> 2 votes

# Answer
# Husk, 10 bytes

```
`ḟ∫ΘNo£∫N+

```

Try it online!
> 2 votes

# Answer
# Dyalog APL, 19 bytes

*6 bytes saved thanks to @KritixiLithos*

```
{⊃o/⍨o∊⍨⍵+o←0,+\⍳⍵}

```

Try it online!

**How?**

`o←0,+\⍳⍵` \- assign `o` the first  triangular numbers

`o/⍨` \- filter `o` by

`o∊⍨⍵+o` \- triangular numbers that summed with  produce triangulars

\- and take the first
> 1 votes

# Answer
# Pari/GP, 54 bytes

```
n->vecmin([y^2-1|y<-[2*n/d-d|d<-divisors(2*n)],y%2])/8

```

Try it online!
> 1 votes

# Answer
# , ~~46~~ ~~44~~ ~~43~~ 41 bytes

```
function(x,y=cumsum(0:x))y[(x+y)%in%y][1]

```

Try it online!

An anonymous function with one mandatory argument, `x`; computes first `x+1` triangular numbers as an optional argument to golf out a few curly braces. I used `choose` before I saw Luis Mendo's Octave answer.

I shaved off a few bytes of Luis Mendo's answer but forgot to use the same idea in my answer.
> 1 votes

# Answer
# Add++, 68 bytes

```
L,RBFEREsECAAx$pBcB_B]VARBFEREsB]GEi$pGBcB*A8*1+.5^1%!!@A!@*b]EZBF#@

```

Try it online!, or see the test suite!

Even *Java* is beating me. I really need to add some set commands to Add++

## How it works

```
L,    - Create a lambda function
      - Example argument:  8
  R   - Range;     STACK = [[1 2 3 4 5 6 7 8]]
  BF  - Flatten;   STACK = [1 2 3 4 5 6 7 8]
  ER  - Range;     STACK = [[1] [1 2] ... [1 2 3 4 5 6 7 8]
  Es  - Sum;       STACK = [1 3 6 10 15 21 28 36]
  EC  - Collect;   STACK = [[1 3 6 10 15 21 28 36]]
  A   - Argument;  STACK = [[1 3 6 10 15 21 28 36] 8]
  A   - Argument;  STACK = [[1 3 6 10 15 21 28 36] 8 8]
  x   - Repeat;    STACK = [[1 3 6 10 15 21 28 36] 8 [8 8 8 8 8 8 8 8]]
  $p  - Remove;    STACK = [[1 3 6 10 15 21 28 36] [8 8 8 8 8 8 8 8]]
  Bc  - Zip;       STACK = [[1 8] [3 8] [6 8] [10 8] [15 8] [21 8] [28 8] [36 8]]
  B_  - Deltas;    STACK = [-7 -5 -2 2 7 13 20 28]
  B]  - Wrap;      STACK = [[-7 -5 -2 2 7 13 20 28]]
  V   - Save;      STACK = []
  A   - Argument;  STACK = [8]
  R   - Range;     STACK = [[1 2 3 4 5 6 7 8]]
  BF  - Flatten;   STACK = [1 2 3 4 5 6 7 8]
  ER  - Range;     STACK = [[1] [1 2] ... [1 2 3 4 5 6 7 8]]
  Es  - Sum;       STACK = [1 3 6 10 15 21 28 36]
  B]  - Wrap;      STACK = [[1 3 6 10 15 21 28 36]]
  G   - Retrieve;  STACK = [[1 3 6 10 15 21 28 36] [-7 -5 -2 2 7 13 20 28]]
  Ei  - Contains;  STACK = [[1 3 6 10 15 21 28 36] [0 0 0 0 0 0 0 1]]
  $p  - Remove;    STACK = [[0 0 0 0 0 0 0 1]]
  G   - Retrieve;  STACK = [[0 0 0 0 0 0 0 1] [-7 -5 -2 2 7 13 20 28]]
  Bc  - Zip;       STACK = [[0 -7] [0 -5] [0 -2] [0 2] [0 7] [0 13] [0 20] [1 28]]
  B*  - Products;  STACK = [0 0 0 0 0 0 0 28]
  A   - Argument;  STACK = [0 0 0 0 0 0 0 28 8]
  8*  - Times 8;   STACK = [0 0 0 0 0 0 0 28 64]
  1+  - Increment; STACK = [0 0 0 0 0 0 0 28 65]
  .5^ - Root;      STACK = [0 0 0 0 0 0 0 28 8.1]
  1%  - Frac part; STACK = [0 0 0 0 0 0 0 28 0.1]
  !!  - To bool;   STACK = [0 0 0 0 0 0 0 28 1]
  @   - Reverse;   STACK = [1 28 0 0 0 0 0 0 0]
  A   - Argument;  STACK = [1 28 0 0 0 0 0 0 0 8]
  !   - Not;       STACK = [1 28 0 0 0 0 0 0 0 0]
  @   - Reverse;   STACK = [0 0 0 0 0 0 0 0 28 1]
  *   - Multiply;  STACK = [0 0 0 0 0 0 0 0 28]
  b]  - Wrap;      STACK = [0 0 0 0 0 0 0 0 [28]]
  EZ  - Unzero;    STACK = [[28]]
  BF  - Flatten;   STACK = [28]
  #   - Sort;      STACK = [28]
  @   - Reverse;   STACK = [28]

```
> 1 votes

# Answer
# Haskell, 56 bytes

```
f x|e<-(`elem`scanl1(+)[0..x])=[n|n<-[0..],e n,e$x+n]!!0

```

Try it online!
> 1 votes

# Answer
# Python 2, ~~83~~ 81 bytes

* @Felipe Nardi Batista saved 2 bytes.

```
lambda n:min(x for x in i(n)if n+x in i(n))
i=lambda n:[i*-~i/2for i in range(n)]

```

Try it online!
> 0 votes

# Answer
# Jelly, 18 bytes

```
0rRS$€ċ
0ð,+Ç€Ạð1#

```

Try it online!
> 0 votes

# Answer
# APL (Dyalog Classic), ~~16~~ 14 bytes

```
(⊃0∘,∩⊢-≢)+\∘⍳

```

Try it online!
> 0 votes

# Answer
## Clojure, 74 bytes

```
#(nth(for[t[(reductions +(range))]i t :when((set(take 1e5 t))(+ i %))]i)0)
#(nth(for[R[reductions]i(R + %(range)):when((set(R - i(range 1e5)))0)]i)0)

```

Pick your favourite :) Loops might be shorter...
> 0 votes

# Answer
# Python 2, 82 bytes

```
f=lambda n,R=[1]:n-sum(R)and f(n,[R+[R[-1]+1],R[1:]][sum(R)>n])or sum(range(R[0]))

```

**Try it online**

This was created by modifying this answer from the related question.
> 0 votes

# Answer
# Retina, 70 bytes

```
.+
$*
1+
$&;$&;
{`^(1+);(?=(\b1|1\2)+;)\1(1*);1*
$3
}`;(1*)$
1$1;1$1
1

```

Try it online! Link includes test suite. Explanation: The algorithm works with three numbers, the input number, the sum of the input number and the current triangular number, and the index of the current triangular number. If the sum is triangular (using @MartinEnder's excellent algorithm) then the whole thing is replaced by the difference of the sum and the original number, thus achieving the desired result. Otherwise, the index is incremented and added to the sum, until the sum becomes triangular. Note that if the input number is zero then all of this is simply ignored as the result is zero anyway.
> 0 votes

# Answer
## Swift 3.0,97 bytes

```
let n=4
var o=0,s=0.0;for i in 0...n{o=i*(i+1)/2;s=sqrt(Double(8*(n+o)+1))
if floor(s)==s{break}}

```

To see output use print(o)

Try it online!
> 0 votes

# Answer
# Ruby, 44 bytes

```
->n{*r=a=b=0;r<<a+=b+=1until r-[a-n]!=r;a-n}

```

Try it online!
> 0 votes

# Answer
# Scala 3, 79 bytes

```
n=>{var i,m,N=0L;N=n;while(N!=0){if(N<0){i+=1;N+=i}else{m+=1L;N-=m}};i*(i+1)/2}

```

Attempt This Online!
> 0 votes

# Answer
# APL(NARS), 51 chars

```
r←B w;n;k
n←¯1
n+←1⋄r←2÷⍨n×n+1⋄→2×⍳k≠2*⍨⌊√k←1+8×w+r

```

9+4+36+2=51

test:

```
      {'B(',(⍕⍵),')=',⍕B⍵}¨0 4 5 7 8 10 24 25 26 34 10000
 B(0)=0 B(4)=6 B(5)=1 B(7)=3 B(8)=28 B(10)=0 B(24)=21 B(25)=3 B(26)=10 B(34)=21 B(10000)=153

```
> 0 votes

---
Tags: code-golf, number, integer
---


title: Extend a matrix in all directions

text:
# Question
Title: Extend a matrix in all directions
Given a multidimensional, rectangular array and a list of dimensions, such as:

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

[3, 4]

```

Your challenge is to extend the matrix to the dimensions given in the list.

To extend an array to a length in a single direction, simply repeat its elements; for example, if we want to extend `[1, 2, 3]` to length 7, the result would be `[1, 2, 3, 1, 2, 3, 1]`.

For example, with the above, we can extend it to length 3:

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

```

Then extend each row to length 4:

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

```

However, your code should work for arrays with arbitrary dimensions. For example, if we take the 3D array

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

```

And dimensions `[3, 3, 5]`, the result is:

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

```

You can assume that the dimensions will be strictly greater than the corresponding dimensions of the array, and that there will be the same amount as the list has dimensions. You may take dimensions in reverse.

This is , shortest wins!

## Testcases

```
[[1, 2], [3, 4]], [3, 4] -> [[1,2,1,2],[3,4,3,4],[1,2,1,2]]
[[[1,2],[3,4]],[[5,6],[7,8]]], [3, 3, 5] -> see above
[1, 2, 3], [5] -> [1, 2, 3, 1, 2]
[[4], [3], [2]], [4,3] -> [[4,4,4],[3,3,3],[2,2,2],[4,4,4]]

```

# Answer
> 11 votes
# BQN, ~~13~~ 8 bytesSBCS

A bit closer to 4 bytes. Takes the array as left argument and the shape vector on the right.

```
(⍉⁼⥊⎉1)´

```

Run online! \<- This uses the new array notation using `[]`.

The reduction `´` iterates over the shape vector from right to left, using the large array as a starting value. `⥊⎉1` resizes the trailing axis by cycling elements, then `⍉⁼` rotates this axis to the front.

# Answer
> 7 votes
# Wolfram Language (Mathematica), 14 bytes

```
##~PadRight~#&

```

Try it online!

# Answer
> 5 votes
# Factor \+ `sequences.repeating`, ~~65~~ 63 bytes

```
[ [ swap '[ _ cycle ] [ '[ _ map ] ] repeat call ] each-index ]

```

Try it online!

This is very unlike how my Factor golfs usually turn out (what with constructing multiple functions and calling them in turn). I noticed that every solution follows this pattern:

* `[[1, 2], [3, 4]], [3, 4]` -\>

`3 cycle [ 4 cycle ] map`
* `[[[1,2],[3,4]],[[5,6],[7,8]]], [3, 3, 5]` -\>

`3 cycle [ 3 cycle ] map [ [ 5 cycle ] map ] map`

So curry each dimension into the innermost quotation with `cycle`, then build up the nested map quotations around it based on its index in the list of dimensions and call it. Since recursion is extremely verbose in Factor, this iterative approach is all but guaranteed to be shorter.

# Answer
> 4 votes
# Python 3, 51 bytes

```
f=lambda m,d:d and[*map(f,m*d[0],d[0]*[d[1:]])]or m

```

Try it online!

# Answer
> 4 votes
# 05AB1E, 7 bytes

```
„∍ε«J.V

```

First input is the list of lengths; second the matrix.

Try it online or verify all test cases.

**Explanation:**

```
„∍ε        # Push string "∍ε"
   «       # Append it to each integer of the first (implicit) input-list
    J      # Join this list together to a single string
     .V    # Evaluate and execute it as 05AB1E code
           # (after which the result is output implicitly)

```

is the extend buildin, which does exactly what this challenges asks: given a list and integer arguments, extend the list to the given integer's length. `ε` is the map builtin, which stays open until we close it with `}` or `]` (which we don't want to do in this challenge).

For example: `„∍ε«J` will convert the list of lengths `[3,3,5]` from the example of the challenge to string `"3∍ε3∍ε5∍ε"`. Evaluated and executed as 05AB1E code, this will:

```
3∍         # Extend the (implicit) 3D input-matrix to 3 inner matrices
  ε        # Map over each inner matrix:
   3∍      #  Extend the matrix to 3 inner rows
     ε     #  Map over each inner row:
      5∍   #   Extend the row to 5 values
        ε  #   No-op map

```

Luckily `'∍ε` isn't a dictionary word, otherwise the `„∍ε` would had to be `"∍ε"` instead.

# Answer
> 3 votes
# Python 3 with numpy, ~~59~~ ~~57~~ 56 bytes

```
lambda m,d:tile(m,d)[[*map(slice,d)]]
from numpy import*

```

Try it online!

−2 thanks to loopy walt, and another −1 by changing back to the deprecated use of a list for indexing.

# Answer
> 3 votes
# Charcoal, 36 bytes

```
⊞υθＦη«≔⟦⟧ζＦυ«≔⁺ζκζＦ…κ⁻ιＬκ⊞κλ»≔ζυ»⭆¹θ

```

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

```
⊞υθ

```

Start by considering the first dimension.

```
Ｆη«

```

Loop over the new dimensions.

```
≔⟦⟧ζ

```

Start collecting the elements of that dimension.

```
Ｆυ«

```

Loop over all of the lists of that dimension.

```
≔⁺ζκζ

```

Collect the elements of the list.

```
Ｆ…κ⁻ιＬκ⊞κλ

```

Cyclically append sufficient elements to reach the desired length.

```
»≔ζυ

```

Save the elements as the list of lists of the next dimension.

```
»⭆¹θ

```

Pretty-print the expanded array.

# Answer
> 3 votes
# , ~~62~~ ~~55~~ 51 bytes

*Edit: -7 bytes thanks to Giuseppe, and -4 bytes thanks to pajonk*

```
\(a,d,`*`=array)a[t(t(which(T*d,T)-1)%%dim(a)+1)]*d
```

Attempt This Online!

---

# , 49 bytes

```
\(a,d)array(a[t(t(which(!a*0,T)-1)%%dim(a)+1)],d)
```

Attempt This Online!

Works with arrays of finite numbers. In this case, we don't need to create a new array of `TRUE` elements to get the indices, as we can just multiply the elements by zero and take the logical NOT.

# Answer
> 2 votes
# BQN, 22 bytesSBCS

```
{⟨⟩:;(1↓)⊸¨⥊˜⊑}

```

Run online!

recursive is shorter `¯\_(⌾‿⌾)_/¯`

# BQN, 26 bytesSBCS

```
{{a‿b:a⥊⚇b}´⋈¨⌽1+↕≠}

```

Run online!

# Answer
> 2 votes
# Brev, 99 bytes

```
(define(j l . m)(j((over(apply j x(cdr m)))l)(car m)))
(define(j l k)(take(apply circular-list l)k))

```

(Displayed with one unnessecary newline for clarity.)

Example usage:

```
(pp (j '(((1 2) (3 4)) ((5 6) (7 8))) 3 3 5))

```

# Answer
> 2 votes
# jq, 58 bytes

```
def r($r):[.[range($r[0])%length]|r($r[1:])? //.];r(input)

```

Try it online! ~ Attempt This Online! ~ jqplay.org

# Answer
> 1 votes
# Pip `-xp`, 20 bytes

```
aH:PObb?fMZa[b]RL#aa

```

Attempt This Online!

### Explanation

Kinda ugly, too bad Pip doesn't have any way to do currying or partial application.

```
aH:PObb?fMZa[b]RL#aa
     b                ; Second argument, the list of dimensions
   PO                 ; Pop the first element (call it N)
a                     ; First argument, the matrix
 H:                   ; Take the first N elements (cyclically) and assign back to a
      b?              ; Is b still nonempty?
                      ; If so:
           a          ;   Take the array
            [b]       ;   and a list containing b
               RL#a   ;   repeated len(a) times
         MZ           ;   Zip together and map to each pair
        f             ;   a recursive call to the main function
                   a  ; If not, just return a

```

# Answer
> 1 votes
# Uiua SBCS, 8 bytes

```
∧(⍉↙⊃∘▽)

```

Try it!

Pretty much the same thing as ovs' BQN answer.

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


title: Unnecessary Fluff

text:
# Question
Title: Unnecessary Fluff
Following the great advice (what do you mean *it's not advice*?!) on Adding unnecessary fluff we can devise the following task:

* Take a list of positive integers and a positive integer \\$m\\$ as input.
* Only keep the prime values from the list.
* Define \\$f(n) = F\_{n^2 + 1}\\$ (the \\$n^2+1\\$-th element in the Fibonacci sequence, starting from \\$F\_0=0, F\_1=1\\$), \\$g(n) = \underbrace{f(f(\cdots f(n)\cdots))}\_{m\text{ applications of }f}\\$, and \\$h(n) = \begin{cases}h(g(n) \mod n) + 1&n\neq0\\0&n=0\end{cases}\\$.
* Apply \\$h\\$ to each element on the list.
* Return the median (you can assume the input contained an odd number of primes).

## Test cases

```
[2,7,11,10,14,4,9], 1 -> 2
[2,7,11,5,13,10,14,4,9], 1 -> 2
[5,5,11,5,13,93,94,95,9], 1 -> 3
[5,7,11], 2 -> 2
[5,5,11], 2 -> 1
[5,43,67], 2 -> 3
[5,43,67], 2 -> 3
[977], 2 -> 5
[719, 727, 733, 739, 743], 2 -> 4
[967], 10 -> 4
[977], 10 -> 3
[5], 10 -> 1

```

Standard loopholes are forbidden. You can use any reasonable I/O format.

This is code golf, so the shortest answer in each language wins.

# Answer
# 05AB1E, 28 bytes

```
DpÏε"ÐĀiIFn>Åf}s%®.V>"©.V}Åm

```

Times out for the \\$m\geq2\\$ test cases, but works in theory.

Try it online or verify all `m=1` test cases.

**Explanation:**

```
DpÏ          # Only keep the primes of the first (implicit) input-list
   ε         # Map over each prime:
    "..."    #  Define recursive string `h` explained below
         ©   #  Store this string in variable `®` (without popping)
          .V #  Execute it as 05AB1E code, with the current prime as argument
   }Åm       # After the map: Pop and push its median
             # (which is output implicitly as result)

Ð            # Triplicate the current value
 Āi          # Pop one, and if it's NOT 0:
   IF        #  Loop the second input-integer `m` amount of times:
     n>      #   Square the current value, and then increase it by 1
       Åf    #   Pop and push the 0-based Fibonacci number
    }s       #  After the loop: swap so a copy of the triplicated number is at the top
      %      #  Modulo
       ®.V   #  Then do a recursive call to `®`
          >  #  And increase it by 1
             # (implicit else:)
             #  (implicitly use the triplicated 0)

```
> 4 votes

# Answer
# Jelly, 20 bytes

```
²‘ÆḞƊ⁴¡%⁸ßẸ¡‘
ẒƇÇ€Æṁ

```

Try it online!

A full program taking the list of integers as the first argument and \\$m\\$ as the second. Prints the result to STDOUT. The TIO link includes a footer that evaluates the first three examples. Times out where \\$m \ge 2\\$.

## Alternative approach Jelly, 36 bytes

```
ẒƇµØ.;S$%ḊɗƬLƊ⁹Ð¡ḊU²‘%ÆḞʋƒ%µ¹Ð¿)ẈÆṁ’

```

Try it online!

A dyadic link taking the list of integers as its left argument and \\$m\\$ as its right, and returning the result. Works for all of the examples in under two seconds total. Full explanation to follow, but in brief:

1. For a given integer \\$n\\$:
    1. Generate \\$\pi(n)\\$, \\$\pi(\pi(n))\\$, \\$\pi(\pi(\pi(n)))\\$ … so we have \\$m\\$ levels of this. Here \\$\pi(n)\\$ is the Pisano period which is the period of the Fibonacci sequence \\$\mod n\\$.
    2. Reverse these. So for example where \\$n = 977\\$ and \\$m = 5\\$, we have a list of `[120, 120, 120, 984, 652]`.
    3. Starting with \\$n\\$, reduce using each member of the list with the following dyadic function: \\$ F((x ^ 2 + 1) \bmod y) \\$ where \\$F(z)\\$ is the zth Fibonacci sequence member.
    4. Take the result of this reduction \\$ \bmod n\\$
2. If the result is non-zero, repeat the above using the result as the new \\$n\\$.
3. Count how many steps it takes to get to zero.
4. Repeat for all of the other prime integers, and take the median.

### Line by line explanation

```
ẒƇµØ.;S$%ḊɗƬLƊ⁹Ð¡ḊU²‘%ÆḞʋƒ%µ¹Ð¿)ẈÆṁ’
ẒƇ                                    # Keep primes
  µ                            )      # Start a new monadic chain and apply it to each of the primes:
                           µ¹Ð¿       # - Repeat until zero, collecting up intermediate results:
             Ɗ⁹Ð¡                     #   - Do the following the number of times indicated by the link’s right argument, collecting up intermediate results (argument starts as one of the primes):
   Ø.     ɗƬ                          #     - Do the following starting with [0, 1] and with the current value of n as the right argument until no new values are seen (I.e. we’ve reached [0, 1] again):
     ;S$                              #       - Concatenate the sum to the end
        %                             #       - Mod n
         Ḋ                            #       - Remove first value
            L                         #     - Length (which will be Pisano period)
                 Ḋ                    #   - Remove first value
                  U                   #   - Reverse order
                        ʋƒ            #   - Reduce this list using the following, and starting with the current n
                   ²                  #     - Squared
                    ‘                 #     - Increment by 1
                     %                #     - Mod the current Pisano period
                      ÆḞ              #     - Fibonacci number
                          %           #   - Mod n
                                Ẉ     # Lengths
                                 Æṁ   # Median
                                   ’  # Decrement by 1

```

Created with the help of Luminespire.
> 4 votes

# Answer
# Raku, 107 bytes

```
->\v,\m{v.grep(&is-prime).map(->\n{n&&&?BLOCK(([o] &{(0,1,*+*...*)[$^n**2+1]} xx m)(n)%n)+1}).sort[*div 2]}

```

Attempt This Online!

* `.grep(&is-prime)` filters the prime numbers (&is-prime is a built-in function)
* `(0, 1, * + * ... *)` constructs the Fibonacci sequence
* `&?BLOCK` is a compile-time variable referring to the current block, so we can recurse with even anonymous functions
* `o` is the function composition operator; `[o]` says "reduce with `o`", so we can compose `m` functions with it
* `[* div 2]` as an array subscript passes the array length to `*` there, effectively getting the middle element without hussle (`div` is doing floor division)
> 2 votes

# Answer
# , 241 bytes

```
\(x,m,`~`=sapply,`&`=c,f=`for`,`-`=sum)median(x[x~\(z)2>-!z%%(2:z)]~\(n){while(n){p=n
f(i,1:m,{x=1&1
j=2
while(-((x=x[2]&-x%%p[1])>0:1))j=j+1
p=j&p})
f(i,1:m,n<-`if`((n=(n^2+1)%%p[i])<2,n,{x=0:1
f(l,2:n,x<-x[2]&-x%%p[i+1])
x[2]}))
F=F+1}
F})

```

Attempt This Online!

A function taking the vector of integers as its first argument and \\$m\\$ as its second. Returns an integer.

This uses the same methodology described in my second Jelly answer, but uses no built-ins for checking primes or the Fibonacci sequence.
> 2 votes

# Answer
# Wolfram Language(Mathematica), 132 bytes

132 bytes, it can be golfed much more.

```
g[0,n_]:=n
g[m_,n_]:=g[m-1,Fibonacci[n*n+1]]
h[m_,0]=0
h[m_,n_]:=h[m,g[m,n]~Mod~n]+1
F[l_,m_]:=Median[Map[h[m,#]&,Select[l,PrimeQ]]]

```

Try it online!
> 2 votes

# Answer
# Python 3, 252 bytes

```
from statistics import*
f=lambda n:f(n-1)+f(n-2)if n>1else n
g=lambda m,n:g(m-1,f(n*n+1))if m>0else n
h=lambda m,n:h(m,g(m,n)%n)+1if n>0else 0
F=lambda l,m:median(map(lambda n:h(m,n),filter(lambda n:0not in map(lambda m:n%(m+2),range(n-2))and n!=1,l)))

```

Try it online!
> 1 votes

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