title: Apply at indices

text:
# Question
Title: Apply at indices
Given:

* a blackbox function \\$f : \mathbb N \to \mathbb N\\$,
* a list of positive integers \\$L\\$, and
* a list of indices \\$I\\$,

apply \\$f(x)\\$ to the elements of \\$L\\$ at the indices specified in \\$I\\$.

For example, \\$f(x) = x^2, L = \[7, 6, 3, 9, 1, 5, 2, 8, 4\]\\$ and \\$I = \[3, 5, 8\]\\$ (using 1 indexing), we apply \\$f(x)\\$ to the 3rd, 5th and 8th elements, yielding \\$\[7, 6, 9, 9, 1, 5, 2, 64, 4\]\\$

---

You may use 0 or 1 indexing for \\$I\\$. The elements of \\$I\\$ will be unique (there will be no duplicates), the maximum element of \\$I\\$ will never exceed the length of \\$L\\$ (or the length of \\$L\\$ minus 1, if using 0 indexing) and the minimum will never be below 1 (or 0, for 0 indexing).

Neither \\$I\\$ nor \\$L\\$ will ever be empty. \\$f\\$ will always return a positive integer, and will always take a single positive integer. \\$L\\$ may be in any order, however, you may decide if \\$I\\$ is in any specific order (e.g. sorted ascending).

This is , so the shortest code in bytes

---

## Test cases

```
f(x)
L
I (using 1 indexing)
out

f(x) = x²
[14, 14, 5, 15, 15, 10, 13, 9, 3]
[1, 3, 4, 5, 6, 7]
[196, 14, 25, 225, 225, 100, 169, 9, 3]

f(x) = x+1
[7, 12, 14, 6]
[1, 2, 3, 4]
[8, 13, 15, 7]

f(x) = σ₀(x)+x
[13, 11, 9, 15, 16, 16, 16, 11, 6, 4]
[2, 4, 6, 8, 10]
[13, 13, 9, 19, 16, 21, 16, 13, 6, 7]

```

where \\$\sigma\_0(x)\\$ is the number of divisors function.

This is a builtin in Jelly. This is a program where you can modify the function \\$f\\$ in the Header, and it will generate a random `L`, `I` then `out` on separate lines. The final test case is prefilled into the Header.

# Answer
# Scratch 3, ~~16~~ 13 blocks

Try it online!

Scratch functions can't `return`, so the function `f` must edit variable `x`.
> 8 votes

# Answer
# 05AB1E, 8 bytes

```
ZLåÅÏs.V

```

Try it online! Uses 1-based indexing.

```
ZLåÅÏs.V  # full program
   ÅÏ     # for elements in...
          # implicit input...
   ÅÏ     # where corresponding element in...
  å       # is...
          # (implicit) each element in...
 L        # [1, 2, 3, ...,
Z         # ..., largest element of...
          # implicit input...
 L        # ]...
  å       # in...
Z         # implicit input...
   ÅÏ     # is 1 replace current element in map with...
      .V  # result of running...
     s    # implicit input...
      .V  # as 05AB1E code
          # (implicit) exit map
          # implicit output

```
> 6 votes

# Answer
# Python 3, 38 bytes

```
def f(p,a,i):
	for q in i:a[q]=p(a[q])

```

Try it online!

-16 bytes using in-place thanks to dingledooper

# Python 3, 51 bytes

```
def f(p,a,i):exec("a[i.pop(0)]=p(a[i[0]]);"*len(i))

```

Try it online!

Inlining with `exec` does not make it any shorter. But oh well, it was an idea :P
> 6 votes

# Answer
# Jelly, 6 bytes

```
Çṛ¡"Ṭ}

```

Try it online!

For the sake of not leaving anything too important in the comments, the built-in solution is `Ç€⁹¦`.

```
   "      For each element of the left argument and each corresponding element of
    Ṭ}    a list of ones at the indices in the right argument and zeroes elsewhere,
Ç         apply the given function to the left element
  ¡       a number of times equal to
 ṛ        the right element.
   "      (For elements of the left argument past the end of the right argument, leave them unchanged.)

```
> 6 votes

# Answer
# tinylisp, 104 bytes

```
(d g(q((L I F _)(i L(c(i(e(h I)_)(F(h L))(h L))(g(t L)(i(e(h I)_)(t I)I)F(a _ 1)))L
(q((F L I)(g L I F 0

```

The solution is the unnamed lambda function represented by the second line. Uses 0-indexing. Requires that the list of indexes be sorted ascending. Try it online!

### Explanation

Our approach is to define a helper function `g` that takes a fourth argument representing the current index. Then we walk through the list recursively, incrementing the index each time. If the current index matches the head of the list of indices, we call the function on the head of the list of values and cons the result to the recursive call; otherwise, we cons the value unchanged.

Ungolfed:

```
(load library)
(def _helper
  (lambda (func ls indices index)
    (if ls
      (cons
        (if (equal? (head indices) index)
          (func (head ls))
          (head ls))
        (_helper func
          (tail ls)
          (if (equal? (head indices) index)
            (tail indices)
            indices)
          (add2 index 1)))
      nil)))
(def apply-at-indices
  (lambda (func ls indices) (_helper func ls indices 0)))

```
> 6 votes

# Answer
# JavaScript (V8), 31 bytes

```
(a,g,p)=>p.map(i=>a[i]=g(a[i]))

```

Try it online!

Produces output by modifying the input array in place.
> 6 votes

# Answer
# , 38 bytes

```
function(l,i,f){l[i]=sapply(l[i],f);l}

```

Try it online!

1-based indices.

If we can assume that `f` is vectorized (perhaps by use of `Vectorize()`), then this would be 31 bytes:

```
function(l,i,f){l[i]=f(l[i]);l}

```
> 5 votes

# Answer
# , 13 bytes

```
1 :'u@{`[`]}'

```

Try it online!

An adverb modifying the function, taking the 0-based indexes as left arg and `L` as the right arg. Called like:

```
indexes  black box function
   v     v
0 1 2 3 (>: f) 7 12 14 6
               ^
               list L to transform

```

This is just a very thin wrapper over the gerund form of J's Amend adverb, using `{` to pluck the values we want to transform and then applying our black box function to them `@u`.
> 5 votes

# Answer
# Factor \+ `math.unicode`, 50 bytes

```
[ '[ _ ∈ [ call ] [ drop ] if ] with map-index ]

```

Try it online!

## Explanation:

It's a quotation (anonymous function) that takes a quotation with stack effect `( x -- x )`, a sequence of values, and a sequence of 0-indexed indices (in that order) from the data stack as input and leaves a sequence of results on the data stack as output. Assuming `[ sq ] { 4 5 } { 0 }` is on the data stack when this quotation is called...

* `'[ _ ∈ [ call ] [ drop ] if ]` Place a quotation on the stack for `with` to use later. However, `'` starts a *fried* quotation, which says to slot whatever is on top of the data stack into the `_`. When `_` appears on the left side of a quotation like this, it's just a shorthand for `curry`ing a quotation.

**Stack:** `[ sq ] { 4 5 } [ { 0 } ∈ [ call ] [ drop ] if ]`
* `with` Partial application on the left. It sticks the `[ sq ]` into the quotation in such a way that it comes *before* whatever the following combinator puts on top of the data stack.

**Stack:** `{ 4 5 } [ [ sq ] [ { 0 } ∈ [ call ] [ drop ] if ] swapd call ]`
* `map-index` Apply a quotation to each element of a sequence, collecting the results into a sequence of the same size. However, `map-index` will also place the index of the element being mapped on top of the data stack. Inside the quotation during the first iteration now...

**Stack:** `4 [ sq ] 0 { 0 } ! element, function, index, indices`
* Shorthand for `member?` Returns `t` if the object second from the top is in the sequence on top of the stack.

**Stack:** `4 [ sq ] t`
* `[ call ] [ drop ]` Push some quotations for `if` to use later.

**Stack:** `4 [ sq ] t [ call ] [ drop ]`
* `if` If third from the top is `t`, call the first quotation, otherwise call the second.

**Stack:** `16`
* Now `map-index` collects this result into the sequence it's building and proceeds with the next iteration.

**Stack:** `5 [ sq ] 1 { 0 }`
* This time, the index is not found in the indices, and so `[ sq ]` gets `drop`ped instead of `call`ed.

**Stack:** `{ 16 5 }`
> 5 votes

# Answer
# APL (Dyalog Unicode), 6 bytes

Full program which is just a thin cover for the built-in `@` ("At") operator. Uses whichever indexing APL currently uses (can be 0 or 1).

```
⎕¨@⎕⊢⎕

```

Try it online!

`⊢⎕` on \\$L\\$

`@⎕` at indices \\$I\\$

`⎕¨` apply \\$f\\$ to each

---

Without the built-in:

```
L←⎕
L[I]←⎕¨L[I←⎕]
L

```

Try it online!

`L←⎕` get \\$L\\$

`L[``]` extract the following elements from \\$L\\$:
`I←⎕` get \\$I\\$
`⎕¨` get \\$f\\$ and apply it to each
`L[I]←` let those values replaces the values in \\$L\\$ at indices \\$I\\$

`L` print the updated \\$L\\$
> 5 votes

# Answer
# Husk, 7 bytes

```
z?⁰IM€N

```

Try it online!

Husk probably needs a builtin for this and/or for converting a list of indices into a boolean mask.

### Explanation

```
z?⁰IM€N    Inputs: function, indices, list of values
    M€N    Build a list saying for each natural number if it is present in the indices
z          Pair each element of this list to one of the values and
 ?          if it is truthy
  ⁰          apply the input function
   I        else, apply the identity function (leave the value unchanged)

```
> 4 votes

# Answer
# Raku, 17 bytes

```
{@^h[@^i]».=&^f}

```

Try it online!

0-based indexing. Modifies the input array in-place.
> 4 votes

# Answer
# Ruby, 33 bytes

```
->g,l,i{i.map{|x|l[x]=g[l[x]]};l}

```

Try it online!
> 4 votes

# Answer
# Haskell, ~~46~~ 44 bytes

* -1 byte thanks to Unrelated String, by reminding me that infix is not always better.
* -1 byte thanks to xnor, by suggesting `take`/`drop` instead of `splitAt`.

```
foldl.h
h f l i=take i l++f(l!!i):drop(i+1)l

```

Try it online!

The relevant function is `foldl.h`, which takes as input `f`, `l`, `i`. The list of indices `i` is `0`-indexed.

## How?

```
h f l i=take i l++f(l!!i):drop(i+1)l

```

The function `h` applies `f` to the `i`-th element of the list `l`. Since Haskell is very unappreciative of mutable variables, the only way to do it is concatenating the first `i` elements of `l`, then `f` applied to the `i`-th element, and finally the rest of `l`.

---

```
foldl.h≡\f l i->foldl(h f)l i

```

This repeats the previous function for all the indices in the input list `i`.

---

# Haskell, 33 bytes

```
foldr.adjust
import Data.Sequence

```

Try it online!

Basically the same solution, but uses the `Seq` type from `Data.Sequence` instead of a `List`. The `import` is costly, but the `h` function from the above solution is already implemented as `adjust`.
> 4 votes

# Answer
# BQN, 10 bytes

```
{⌾(⊸⊏)}

```

Try it online!

To show off structual under  which is a little bit more powerful than J's `&.` as I found out yesterday. `{…}` defines a block where we get access (among other things) to  as the right argument,  the left, and  the function that gets modified. So this calls `⌾(⊸⊏)` with .  executes the right part, then the left part, and then the inverse of the right part. But unlike `&.` it also remembers the original array at the inverse step, so it can be used to update the array. So `⊸⊏` takes the elements of  at the indices of . On these elements  gets called. Then the elements get re-inserted into the original arrays at the indices of .
> 4 votes

# Answer
# x86-16 machine code, 11 bytes

```
        I_LOOP:
AD          LODSW                       ; next index into AX
97          XCHG AX, DI                 ; index in DI
8A 01       MOV  AL, BYTE PTR[BX+DI]    ; AL = value of L
FF D5       CALL BP                     ; call BlackBox (tm) function
88 01       MOV  BYTE PTR[BX+DI], AL    ; value of L = AL
E2 F6       LOOP I_LOOP                 ; loop until end of I
C3          RET                         ; return to caller

```

`L` list at `[BX]`, `I` list at `[SI]` (zero indexed), `I` length in `CX`. BlackBox function at `[DS:BP]`, input value/return in `AL`.

Example run with DEBUG. The "interesting" parts have been highlighted for those who don't speak DEBUG.
> 4 votes

# Answer
# Lua, 67 bytes

```
function g(f,l,i)for k,v in pairs(i)do l[v]=f(l[v])end return l end

```

Try it online!

Uses 1-indexing, i always forget lua uses 1 indexed tables
> 3 votes

# Answer
# Stax, 14 bytes

```
Yd{diyI^n_aaMm

```

Run and debug it

The fully manual method, takes args as `block arr arr`. Requires 0-indexed indices.

the final result is put on the top of the stack.

The single byte builtin for this which takes args `arr arr block` is `&`.
> 3 votes

# Answer
# Icon, 43 bytes

```
procedure a(L,I,f)
L[k:=!I]:=f(L[k])&\z
end

```

Try it online!
> 3 votes

# Answer
# C (clang), ~~54~~ \\$\cdots\\$ ~~52~~ 43 bytes

Saved 9 bytes thanks to att!!!

```
f(g(),*L,*I,n){for(;n--;)L[*I++]=g(L[*I]);}

```

Try it online!

Inputs a pointer to a function \\$g\\$ (inputting an `int` parameter and returning an `int`), a pointer to an array of positive integers \\$L\\$, a pointer to an array of \\$0\\$-base indices \\$I\\$, and \\$I\\$'s length \\$n\\$ (since pointers in C carry no length info).
Updates \\$L\\$ in place.

### Explanation

```
f(g(),*L,*I,n)                       // golfed function signature for:
                                     // int f(
                                     //       int (*g)(int),
                                     //       int *L,
                                     //       int *I,
                                     //       int n
                                     //      )
{                                    //
 for(;n--;)                          // loop over I
           L[*I  ]=                  // assign L at current index in I
                   g(     );         // to g's return value of
                     L[*I]           // L at current index in I
               ++                    // bump I to next index

```
> 3 votes

# Answer
# C#, 50 bytes

```
(f,L,I)=>L.Select((v,i)=>I.Contains(i+1)?f(v):v);

```

Online demo: https://dotnetfiddle.net/M4YbOx
> 3 votes

# Answer
# Scala 3, 50 bytes

```
f=>I=>_.zipWithIndex.map((?,i)=>if(I(i))f(?)else?)

```

Try it in Scastie!

Stupid function parameter names ftw! Indexing starts at 0.

```
f=>  //The blackbox function
I=>  //The Set of indices
 _   //The list of integers
 .zipWithIndex //Zip each element with its index
 .map((?,i)=>  //Map each element `?` and its index `i`
   if(I(i))    //If the Set of indices contains i
    f(?)       //apply f to ?
    else ?     //Otherwise, just return ?
 )

```
> 3 votes

# Answer
# Java, ~~42~~ 38 bytes

```
(a,i,f)->{for(int j:i)a[j]=f.f(a[j]);}

```

*Saved 4 bytes thanks to Olivier Grégoire.*

Try it online!
> 3 votes

# Answer
# Wolfram Language (Mathematica), 5 bytes

```
MapAt

```

Try it online!

Takes input in a slightly annoying format: to apply `f` to `{a,b,c,d,e}` at positions `{1,3,5}` and get `{f[a],b,f[c],d,f[e]}`, we write

```
MapAt[f, {a,b,c,d,e}, {{1},{3},{5}}]

```

Some other varyingly built-in solutions:

* **18 bytes:** `MapAt[#,List/@#2]&`. Takes input `[f,I][L]`. The `{{1},{3},{5}}` syntax bothers me a little, so this lets `I` be an actual list.
* **~~20~~ 19 bytes:** `Map@#~SubsetMap~#2&`. Takes input `[f,I][L]`. `SubsetMap` differs from `MapAt` in that it applies the function to all the elements at some indices at the same time.
* **27 bytes:** `(s=#3;s[[#]]=#2/@s[[#]];s)&`. Takes input `[I,f,L]`. Here, we assign the input to a variable, and manually change the values at positions indexed by `I`.
> 3 votes

# Answer
# Zsh, 36 bytes

```
for x;grep -xq $[++i] f&&F $x||<<<$x

```

Try it online!

Expects a function predefined as `F`, the operand array as command-line arguments, and the indeces from the file `f`, each on one line.

`for x;`: for each `$x` in the command-line arguments:

* `$[++i]`: increment `$i` (which starts at 0 implicitly)
* `grep -xq f`: check if `$i` is present in the file `f`
    + `-q`: return success/failure only, don't print matching lines
    + `-x`: require the whole line to match `$i`. Otherwise `14` would erroneously match `4`
* `&&`: if that succeeds:
    + `F $x`: call `F` with the argument `$x`
* `||`: else:
    + `<<<$x`: just print `$x` unaltered
> 2 votes

# Answer
# Julia, 19 bytes

```
f*L*i=L[i]=f.(L[i])

```

with 1-based indexing

changes `L` itself as the output

Try it online!
> 2 votes

# Answer
# MMIX, 44 bytes (11 instrs)

Takes `f`, `L`, `I`, `len(i)`; both `L` and `I` are lists of `uint64_t`. `f` is also necessarily MMIXware argument passing.

(jxd -T)

```
00000000: fe040004 3b030303 27030308 8e050203  “¥¡¥;¤¤¤'¤¤®⁾¦£¤
00000010: 3b050503 8e070105 bf060000 ae060105  ;¦¦¤⁾¬¢¦Ḃ©¡¡Ẹ©¢¦
00000020: 5b03fffa f6040004 f8000000           [¤”«ẇ¥¡¥ẏ¡¡¡

```

Disassembly/explanation:

```
foo GET    $4,rJ
    SLU    $3,$3,3
0H  SUBU   $3,$3,8      // loop: leni--
    LDOU   $5,$2,$3     // j = I[leni]
    SLU    $5,$5,3
    LDOU   $7,$1,$5     // a = L[j]
    PUSHGO $6,$0,0      // b = f(a)
    STOU   $6,$1,$5     // L[j] = b
    PBNZ   $3,0B        // iflikely(leni) goto loop
    PUT    rJ,$4
1H  POP    0,0          // return

```
> 2 votes

# Answer
# Kotlin, 48 bytes

```
{f,L,I->L.mapIndexed{i,v->if(i in I)f(v)else v}}

```

Try it online!

Very straight-forward algorithm. Uses the default rule for submitting lambdas.
> 2 votes

# Answer
# Attache, 2 bytes

```
On

```

Try it online!

There's a Builtin for That™.

Another builtin solution, 8 bytes: `Over@`->`.

## Without builtins, 22 bytes

*-2 bytes after reading other answers, since this modifies the variable in place. Prepend `;z` before the last `}` to have it also return the value.*

```
${{Set[z,_,y!z@_]}=>x}

```

Try it online!

**23 bytes:** `${z&Set&>Tr![x,z[x]|y]}`

**23 bytes:** `${&@(z&Set)![x,z[x]|y]}`

**31 bytes:** `${{[_,y@_][_2in x]}&>@V#Iota!z}`

**32 bytes:** `${{If[_2in x,y@_,_]}&>@V#Iota!z}`

**33 bytes:** `${{[_,_|y][_2in x]}&>Enumerate@z}`

**33 bytes:** `${{[Id,y][_2]!z@_}#x&Has=>Iota@z}`

**34 bytes:** `${{z@_|If[_2,y,Id]}#x&Has=>Iota@z}`

**34 bytes:** `${{If[x&Has!_2,y@_,_]}&>@V#Iota!z}`

**34 bytes:** `${{[Id,y][x&Has!_2]!_}&>@V#Iota!z}`
> 2 votes

# Answer
# Elm, 62 bytes

```
a f i=List.indexedMap(\n->if List.member n i then f else\x->x)

```

Fairly simple implementation of the function. `List.indexedMap` expects a function which takes 2 `Int`s (in this case), but we can also write a function that takes 1 `Int` and returns an `Int -> Int` function to save ~~3 bytes~~ 1 byte over the more straightforward implementation function `\n e->if List.member n i then f e else e`.

At the cost of 1 byte, the inner function can be written as `List.member>>\h->if h i then f else\x->x`, and the right operand to `>>` *seems* golfable, but I can't quite figure out if that's really the case.

## Test Program

Try it here!

```
import Html exposing (text)

a : (Int -> Int) -> List Int -> List Int -> List Int
a f i=List.indexedMap(\n->if List.member n i then f else\x->x)

main =
  a
    (\x -> x ^ 2)
    [0, 2, 3, 4, 5, 6]
    [14, 14, 5, 15, 15, 10, 13, 9, 3]
  |> List.map String.fromInt
  |> String.join ", "
  |> (\x -> "[" ++ x ++ "]")
  |> text

```
> 2 votes

# Answer
# Racket, 97 bytes

```
(define(a L I f[n 1])(if(null? L)'()(cons(if(member n I)(f(car L))(car L))(a(cdr L)I f(+ 1 n)))))

```

Try it online!
> 1 votes

# Answer
# Clojure, 36 bytes

```
#(reduce(fn[l i](update l i %))%2%3)

```

Try it online!

Takes input in the order or \\$f, L, I\\$.

The variation of this task with only a single index rather than a list is exactly what the built-in function `update` does, but wrapping in a `reduce` is necessary to update at multiple indices.
> 1 votes

# Answer
# C++, 59 bytes

```
[](int*a,int*i,auto f,int l){while(l--)a[i[l]]=f(a[i[l]]);}

```

Try it online!

# 50 bytes

```
[](int*a,auto i,auto f){for(int x:i)a[x]=f(a[x]);}

```

Uses a `vector` instead of an array for the indices.

Try it online!
> 1 votes

# Answer
# Japt `-m`, ~~5~~ 4 bytes

Takes `I` as the first input, `L` as the second and `f` is preassigned to variable `W` (3rd line of the header), as allowed by consensus. The first line of the header just subtracts `1` from each value in `I` to make them 0-indexed 'cause I was too lazy to manually change them all.

Modifies the original input `L` in place and the footer outputs the modified version.

Could be 3 bytes (`gVW`, with reversed arguments and no flag) if `A.g()` could take the indices to be modified as an array instead of as individual arguments.

```
VgUW

```

Try it
> 1 votes

# Answer
# Vyxal, 1 byte

```
V

```

Try it Online!

Builtin. Vyxal can't take a function as an input, so just leave the function on the stack.

# Vyxal, 8 bytes

```
£Þǔ¨£[¥†

```

Try it Online!

Without builtin.
> 1 votes

# Answer
# Go, 80 bytes

```
func(f func(int)int,L[]int,I[]int)[]int{for _,i:=range I{L[i]=f(L[i])}
return L}

```

Attempt This Online!
> 1 votes

# Answer
# POSIX Shell + Utilities, 63 bytes

```
for i
do
printf %s\\n "$i r !f `sed -n ${i}p L`" -d w
done|ed L

```

If only ed had a way to inject the contents of the current line into a `!` substitution... Alas.

List \\$L\\$ is a text file per POSIX, and list \\$I\\$ is the argument vector. Function \\$f\\$ is, well, `f` in the PATH.

Trivially, this generates an ed program in the form (for the example):

```
3 r !f 3
-d
w
5 r !f 1
-d
w
8 r !f 8
-d
w

```

Which appends the result of `sh -c 'f N[i]'` to the `i`th line, then deletes the original. This seems to me to minimise the motions.

Example + test case transcript:

```
$ cat cg; echo; wc -c cg
for i
do
printf %s\\n "$i r !f `sed -n ${i}p L`" -d w
done|ed L
63 cg

$ printf '%s\n' 7 6 3 9 1 5 2 8 4 > L
$ printf '%s\n' 'expr $1 \* $1' > f; chmod +x f
$ ./cg 3 5 8
18
2
18
2
18
3
19
$ paste -s L
7   6   9   9   1   5   2   64  4

$ printf '%s\n' 14 14 5 15 15 10 13 9 3 > L
$ ./cg 1 3 4 5 6 7
24
4
25
3
26
4
27
4
28
4
29
4
30
$ paste -s L
196 14  25  225 225 100 169 9   3

$ printf '%s\n' 7 12 14 6 > L
$ printf '%s\n' 'expr $1 + 1' > f
$ ./cg 1 2 3 4
10
2
10
3
10
3
10
2
10
$ paste -s L
8   13  15  7

$ printf '%s\n' 13 11 9 15 16 16 16 11 6 4 > L
$ cat f
i=$1
while [ $i -gt 0 ]; do
        [ $(( $1 % i )) -eq 0 ] && n=$(( n + 1 ))
        i=$(( i - 1 ))
done
expr $n + $1
$ ./cg 2 4 6 8 10
27
3
27
3
27
3
27
3
27
2
27
$ paste -s L
13  13  9   19  16  21  16  13  6   7

```
> 1 votes

# Answer
# Uiua, 4 bytes

```
⍜⊏^1

```

Try it!

0-indexed.
> 1 votes

# Answer
# Arturo, 34 bytes

```
$[f,a,i][loop i'x->a\[x]:f a\[x]a]

```

Try it
> 0 votes

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


title: Finding the power sandwich version 2

text:
# Question
Title: Finding the power sandwich version 2
# Introduction

This question is inspired by this great question.

# Challenge

Given a number \\$N\>0\\$, output the largest integer \\$a^b\\$ that is smaller or equal to \\$N\\$, and the smallest integer \\$c^d\\$ that is greater or equal to \\$N\\$, where \\$b\>1\\$ and \\$d\>1\\$.

Output should be a list of two integers, the first being smaller or equal to \\$N\\$, the second being greater or equal to \\$N\\$, and both being a perfect power. The two outputs can be in any order.

If \\$N\\$ is a perfect power already, the output should be the list \[N, N\].

This is , so the shortest code (as measured in bytes) wins.

# Example Input and Output

Input:

> 30

Output:

> \[27, 32\]

Explanation: \\$27=3^3\\$ is the largest perfect power less than or equal to \\$30\\$ and \\$32=2^5\\$ is the smallest perfect power greater or equal to \\$30\\$. Note that exponents b and d are not the same in this case.

# Test cases

```
2 -> [1, 4]
30 -> [27, 32]
50 -> [49, 64]
100 -> [100, 100]. 100 is already a perfect power.
126 -> [125, 128]
200 -> [196, 216]
500 -> [484, 512]
5000 -> [4913, 5041]
39485 -> [39304, 39601]
823473 -> [822649, 823543]
23890748 -> [23887872, 23892544]

```

# Answer
> 7 votes
# , ~~62~~ 60 bytes

```
function(n,y=outer(1:n,2:n,"^"))c(max(y[y<=n]),min(y[y>=n]))

```

Try it online!

Brute force approach: generate all powers of `1..n` raised to `2..n` and find and return least upper bound and greatest lower bound.

# Answer
> 6 votes
# Jelly, 14 bytes

```
ÆEŻg/’
ÇƇṪ;Ç1#

```

A monadic Link that accepts a positive integer and yields the sandwich of perfect powers.

**Try it online!** (Excluded the three largest test cases since the implementation is inefficient.)

### How?

```
ÆEŻg/’ - Link 1, perfect power?: positive integer, X
ÆE     - prime factor exponents of X (e.g.: 1 -> [], 8 -> [3], 63 -> [0,2,0,1])
  Ż    - prefix a zero (to allow the following reduction when X=1)
    /  - reduce by:
   g   -   greatest common divisor (Note that 0 GCD N = N GGD 0 = N)
          - non-perfect powers will result in 1
            perfect powers will result in an integer greater than 1, except X=1 -> 0
     ’ - decrement -> non-zero (truthy) iff X is a perfect power

ÇƇṪ;Ç1# - Main Link: positive integer, N
 Ƈ      - filter {[1..N]} keeping those for which:
Ç       -   call Link 1
  Ṫ     - tail
           -> perfect power less than or equal to N
     1# - starting with k=N find the first integer k for which:
    Ç   -   call Link 1
           -> perfect power greater than or equal to N
   ;    - concatenate

```

### How?

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

```
n=>eval("for(M=[m=1,x=p=2];(x*=p)>n|x<m?0:m=x,x<n?1:x>M?(x=++p)<n:M=x;)[m,M]")

```

Try it online!

---

# JavaScript (ES6), 79 bytes

A faster version without `eval()`, also easier to comment.

```
n=>{for(M=[m=1,x=p=2];(x*=p)>n|x<m?0:m=x,x<n?1:x>M?(x=++p)<n:M=x;);return[m,M]}

```

Try it online!

```
n => {            // n = input
  for(            // loop:
    M = [         //   M = high bound
      m = 1,      //   m = low bound
      x =         //   x = current result
      p = 2       //   p = current multiplier
    ];            //
    (x *= p)      //   multiply x by p
    > n |         //   if x is greater than n
    x < m ?       //   or less than m:
      0           //     do nothing
    :             //   else:
      m = x,      //     set m to x
    x < n ?       //   if x is less than n:
      1           //     continue
    :             //   else:
      x > M ?     //     if x is greater than M:
        (x = ++p) //       increment p and set x to p
        < n       //       continue if x < n
      :           //     else:
        M = x;    //       set M to x and continue
  );              // end of loop
  return [m, M]   // return the final bounds
}                 //

```

# Answer
> 5 votes
# Desmos, 55 bytes

```
f(n)=[floor(L)^I.max,ceil(L)^I.min]
L=n^{1/I}
I=[2...n]

```

Try It On Desmos!

Try It On Desmos! - Prettified

Eh, pretty sure this can be golfed.

# Answer
> 4 votes
# Python, 85 bytes

*This solution is designed to solve all test-cases in less than 1 second, for a slightly shorter but slower approach see corvus\_192's solution*

*-21 bytes thanks to xnor's suggestion on corvus\_192's solution*

```
lambda n:[i*max(i*int(n**(1/p)//i*i)**p for p in range(2,len(bin(n))))for i in(1,-1)]

```

Attempt This Online!

Goes through floor/ceil of p-th root to power of p for all possible powers p and picks the highest lower and lowest upper bound

---

# Python, 115 bytes

*solves all test cases in less than a minute*

```
lambda n:[next(q for q in x for b in r(2,len(bin(q)))if q==round(q**(1/b))**b)for x in[r(n,0,-1),r(n,3*n)]]
r=range

```

Attempt This Online!

## Explanation

*uses a less golfed version of the same approach*

```
# check if a given number is a perfect power
p=lambda q:any(q==round(q**(1/b))**b for b in r(2,len(bin(q))))
# brute-force: check for all exponents b if q is a power of b
# due to rounding errors: q**(1/b)%1==0 and q==int(q**(1/b))**b) give the wrong result for the last two test-cases
# checking all numbers takes to much time
# only check up to log2(q)+2 with is larger than the largest possible power p for which 2**p <= q

# find the power sandwich
lambda n:[next(filter(p,x))for x in[r(n,0,-1),r(n,3*n)]]
# find the first number x less/greater than or equal to n that satisfies p(x)
# use 3*n as upper bound for the next perfect power: if n is not a square number then the next square number is less than 3*n
# (clear for n <9=3², if m=k*k for k >= 3 then (k+1)²=k²+2*k+1 <= k²+3*k <= 2*k² <= 2*m < 3*m)

```

# Answer
> 3 votes
# Jelly, 16 bytes

```
2r⁸*þFfȯ_İ¥Þɗ⁸.ị

```

Try it online!

A monadic link taking an integer argument and returning a list of two integers. Will time out for large n, since internally a table of all powers of \\$a^b\\$ where \\$a\\$ is from 1 to n and \\$b\\$ is from 2 to n.

## Explanation

```
2r                | Range from 2 to the input
  ⁸*þ             | Table of powers from 1 to the input raised to the power of from 2 to the input
     F            | Flatten
            ɗ⁸    | Following as a dyad, using the input as the right argument and the power table as the left:
      f           | - Filter (keep the input if present in the power table)
       ȯ  ¥       | - Or the following as a dyad
        _         |   - Subtract the input
         İ        |   - Invert
              .ị  | Take the last (power above or equal) and first (power below or equal) elements of this list

```

# Answer
> 3 votes
# Retina 0.8.2, 120 bytes

```
.+
$*
((1+)((\2(1+))(?=(\4*)\2*$)\4*(?=\5$\6))+)?1$
$&¶$&
O`
+`¶(?!((1+)((\2(1+))(?=(\4*)\2*$)\4*(?=\5$\6))+)?1$)
¶1
%`1

```

Try it online! Link includes faster test cases. Explanation:

```
.+
$*

```

Convert to unary.

```
((1+)((\2(1+))(?=(\4*)\2*$)\4*(?=\5$\6))+)?1$
$&¶$&

```

Find the largest perfect power that does not exceed `N`. This is based on my answer to What's next, Achilles? but also allowing `N=1`, which that question didn't have to handle.

```
O`

```

Sort the numbers back into order. (This is shorter than trying to get the above stage to output the numbers in ascending order.)

```
¶(?!((1+)((\2(1+))(?=(\4*)\2*$)\4*(?=\5$\6))+)?1$)
¶1

```

If `N` is not a perfect power then increment it.

```
+`

```

Repeat until a perfect power is reached.

```
%`1

```

Convert to decimal.

# Answer
> 3 votes
# Python, 77 bytes

```
lambda n:[i*max(i*int(n**(1/p)//i*i)**p for p in range(2,n+2))for i in(-1,1)]

```

Attempt This Online!

-16 bytes thanks to xnor and bsoelch

## Previous version, 93 bytes

```
lambda n:[(g:=lambda f,i:f(int(abs(n**(1/p)//i))**p for p in range(2,n+1)))(max,1),g(min,-1)]

```

The core algorithm is from bsoelch: https://codegolf.stackexchange.com/a/266303\> I just spent around 2 hours optimizing.

This version with a helper function is actually 2 bytes shorter than my alternative eval hack:

```
lambda n:eval(f"%s(int(abs({n}**(1/p)//%d))**p for p in range(2,{n}+1)),"*2%("max",1,"min",-1))

```

Attempt This Online!

# Answer
> 3 votes
# 05AB1E, ~~16~~ 14 bytes

```
LÂZ+‚εR.ΔÓ0š¿≠

```

-2 bytes porting *@JonathanAllan*'s Jelly answer instead.

Try it online or verify all test cases. (Times out for the largest two test cases, so those are omitted.)

**Original 16 bytes answer:**

```
L¦©zmDï®màsî®mß‚

```

Port of *@AidenChow*'s Desmos answer.

Try it online or verify all test cases. (Times out for the largest four test cases, so those are omitted.)

**Explanation:**

```
L              # Push a list in the range [1, (implicit) input]
 Â             # Bifurcate it; short for Duplicate & Reverse copy
  Z+           # Add the input to each value in the reversed copy
    ‚          # Pair them together: [[1,2,...,n-1,n],[2n,2n-1,...,n+2,n+1]]
     ε         # Map over both inner lists:
      R        #  Reverse the list
       .Δ      #  Pop and find the first value that's truthy for:
         Ó     #   Push the exponents of its prime factorization
          0š   #   Prepend a 0 (edge case for value=1)
            ¿  #   Pop this list, and push its Greatest Common Divisor (GCD)
             ≠ #   Check that it's NOT equal to 1
               # (after which the pair is output implicitly as result)

```

```
L              # Push a list in the range [1, (implicit) input]
 ¦             # Remove the leading 1 to make the range [2,input]
  ©            # Store this list in variable `®` (without popping)
   z           # Pop and convert each value in the list to 1/value
    m          # Take the (implicit) input to the power of each of these 1/value
     D         # Duplicate this list
      ï        # Floor each to an integer
       ®m      # Take each to the power [2,input] (at the same positions)
         à     # Pop and leave its maximum
     s         # Swap so the list is at the top again
      î        # Ceil
       ®m      # To the power [2,input]
         ß     # Pop and leave its minimum
          ‚    # Pair this maximum and minimum together
               # (which is output implicitly as result)

```

# Answer
> 3 votes
# C (gcc), 98 bytes

*-1 thanks to ceilingcat*

Adapted from my JS answer. Prints the bounds separated by a space.

```
m,M,x,p;f(n){for(M=n*n,m=1,x=p=2;m=(x*=p)>n|x<m?m:x,x<n?:x<M?M=x:(x=++p)<n;);printf("%d %d",m,M);}

```

Try it online!

# Answer
> 2 votes
# Vyxal, 91 bitsv2, 11.375 bytes

```
⇧ḢĖe:⌊>g)₍<>

```

Try it Online!

Bitstring:

```
1101001100110001001011011110000101000101000100101011000010000101000011011110111001000110010

```

## Explained

```
⇧ḢĖe:⌊>g)₍<>
        )₍<>  # Find the first numbers >= and <= the input where:
       g      #   The minimum of
      >       #   comparing whether
     ⌊        #   the floor of:
   e          #     the number to the power of each item in
  Ė           #     the reciprocals of items in
⇧Ḣ            #     the range [2, number + 2]
    : >       #   is greater than the original list
       g      #   is 0

```

Created with the help of Luminespire.

# Answer
> 2 votes
# Charcoal, 30 bytes

```
ＮθＦθＦθ⊞υＸ⊕ι⁺²κＩ⟦⌈Φυ¬›ιθ⌊Φυ¬‹ιθ

```

Try it online! Link is to verbose version of code. Explanation: Port of @Guiseppe's R answer.

```
Ｎθ

```

Input `n`.

```
ＦθＦθ⊞υＸ⊕ι⁺²κ

```

Generate a list of perfect powers from  to `nⁿ⁺¹`.

```
Ｉ⟦⌈Φυ¬›ιθ⌊Φυ¬‹ιθ

```

Find the largest one not greater than `n` and the smallest one not less than `n`.

42 bytes for a less inefficient version:

```
ＮθＦＥ⊕₂θＸ⊕ι…·²⎇ιＬ↨θ⊕ι²Ｆι⊞υκＩ⟦⌈Φυ¬›ιθ⌊Φυ¬‹ιθ

```

Try it online! Link is to verbose version of code. Explanation: As above but only loops up to `⌊√n⌋` and only powers up to `1+⌊logᵢn⌋` (or `2` if `i=1`).

33 bytes for a more efficient version that can suffer from floating-point inaccuracy:

```
ＮθＩＥ⟦¹±¹⟧×ι⌈Ｅ₂θ×ιＸ×ι⌊×ιＸθ∕¹⁺²λ⁺²λ

```

Try it online! Link is to verbose version of code. Explanation: Port of @bsolech's golf to @corvus\_192's Python answer.

```
Ｎθ                                  Input `N` as a number
     ¹                              Literal integer `1`
       ¹                            Literal integer `1`
      ±                             Negated
    ⟦   ⟧                           Make into list
   Ｅ                                Map over units
              θ                     Input `N`
             ₂                      Square root
            Ｅ                       Map over implicit range
                        θ           Input `N`
                       Ｘ            Raised to power
                          ¹         Literal integer `1`
                         ∕          Divided by
                             λ      Current value
                           ⁺        Plus
                            ²       Literal integer `2`
                     ×              Multiplied by
                      ι             Current unit
                    ⌊               Floored to integer
                  ×                 Multiplied by
                   ι                Current unit
                 Ｘ                  Raised to power
                                λ   Current value
                              ⁺     Plus
                               ²    Literal integer `2`
               ×                    Multiplied by
                ι                   Current unit
           ⌈                        Take the maximum
         ×                          Multiplied by
          ι                         Current unit
  Ｉ                                 Cast to string
                                    Implicitly print

```

# Answer
> 2 votes
# Scala, 149 bytes

A port of @Giuseppe's R answer in Scala.

---

Golfed version. Try it online!

```
n=>{val y=for{i<-1 to n;j<-2 to n}yield math.pow(i,j);val(a,b)=y.partition(_<=n);(if(a.nonEmpty)a.max.toInt else 0,if(b.nonEmpty)b.min.toInt else 0)}

```

Ungolfed version. Try it online!

```
object Main {
  def main(args: Array[String]): Unit = {
    println(f(1))
    println(f(2))
    println(f(4))
    println(f(30))
    println(f(50))
    println(f(100))
    println(f(126))
  }

  def f(n: Int): (Int, Int) = {
    val y = for {
      i <- 1 to n
      j <- 2 to n
    } yield math.pow(i, j)

    val yFilteredBelow = y.filter(_ <= n)
    val yFilteredAbove = y.filter(_ >= n)

    val maxBelow = if (yFilteredBelow.nonEmpty) yFilteredBelow.max.toInt else 0
    val minAbove = if (yFilteredAbove.nonEmpty) yFilteredAbove.min.toInt else 0

    (maxBelow, minAbove)
  }
}

```

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

Prompts for integer:

```
(↑(n=⌊/n←|m-i)/m←(⌊i*÷p)*p),↑(n=⌊/n←|m-i)/m←(⌈(i←⎕)*÷p)*p←1↓⍳30

```

Increase the 30 at the end of the code to handle higher integers than the examples.

Try it online! Thanks to Dyalog Classic

---
Tags: code-golf, math, integer
---


title: Compute the conjugate of a partition

text:
# Question
Title: Compute the conjugate of a partition
We will think of a partition as a sequence of non-increasing integers. For a given partition into \\$n\_1, n\_2, \dots, n\_k\\$ with \\$n\_1 \geq n\_2 \dots n\_{k-1} \geq n\_k = n\\$ we write it out with \\$n\_i\\$ dots on row \\$i\\$. So for \\$6, 1, 1\\$ we would write six dots on the first row, one on the second and one on the third

# Task

Given a partition, you should output its conjugate. That is you should output how many dots there are in each column of the dot diagram. For the input \\$6, 1, 1\\$ the output should be \\$3, 1, 1, 1, 1, 1\\$.

# Examples

```
5, 2, 1 gives output 3, 2, 1, 1, 1
4, 3, 1 gives output 3, 2, 2, 1
4, 2, 2 gives output 3, 3, 1, 1
3, 3, 2 gives output 3, 3, 2
4 gives output 1, 1, 1, 1

```

# Answer
> 11 votes
# BQN, 3 bytes

```
⊒⌾/

```

Try it here.

Explanation via example:

```
   / 4‿3‿1         # use each element as a count to replicate its index
⟨ 0 0 0 0 1 1 1 2 ⟩

   ⊒/ 4‿3‿1        # take a running occurrence count
⟨ 0 1 2 3 0 1 2 0 ⟩

   /⁼⊒/ 4‿3‿1      # the inverse of /, applied via ⌾, counts occurrences
⟨ 3 2 2 1 ⟩

```

# Answer
> 8 votes
# 05AB1E, 5 bytes

```
L˜{Åγ

```

Attempt This Online!

```
L        # range, so [6,1,1] is [[1,2,3,4,5,6],[1],[1]]
˜        # flatten, [1,2,3,4,5,6,1,1]
{        # sort, [1,1,1,2,3,4,5,6]
Åγ       # run length encode, [3, 1, 1, 1, 1, 1]

```

If we can have extraneous zeros in the output, then by porting @frasiyav's great BQN answer we have:

# 05AB1E, 4 bytes

```
L˜ā¢

```

Attempt This Online!

```
L˜        # same as previously
ā         # length range, [1, 2, 3, ..., len(arr)] (without popping)
¢         # count each

```

# Answer
> 7 votes
# Octave / MATLAB, 17 bytes

```
@(x)sum(1:x<=x,1)

```

Anonymous function that inputs a column vector and outputs a row vector.

Try it online!

### Explanation

```
@(x)              % Define anynomous function of x: column vector
        1:x       % Range from 1 to (first entry of) x. Gives a row vector
           <=x    % Less than/equal to x? Element-wise with broadcast. Gives a matrix
    sum(      ,1) % Sum of each column

```

# Answer
> 6 votes
# , ~~28~~ 22 bytes

*Edit: -6 bytes thanks to @Giuseppe.*

```
\(x)table(sequence(x))

```

Attempt This Online!

~~Port of~~ Based on @Command Master's 05AB1E answer.

# Answer
> 6 votes
# Jelly, 3 bytes

```
b1S

```

Try it online!

For some reason, I almost feel like I've seen this even shorter as part of a different solution...

```
b1     Convert each element of the input to base 1.
  S    Sum across columns.

```

# Answer
> 6 votes
# 05AB1E (legacy), 4 bytes

```
Å1ζO

```

Try it online or verify all test cases.

Doesn't work in the new version of 05AB1E, unless we add `0` or `¾` before the `ζ`.

**Explanation:**

```
Å1    # Convert each value in the (implicit) input-list into a list of that many 1s
  ζ   # Zip/transpose; swapping rows/columns,
      # implicitly using a space " " as filler for unequal length rows
   O  # Sum each inner list, which ignores the spaces in the legacy version of 05AB1E
      # (after which the resulting list is output implicitly)

```

# Answer
> 6 votes
# , 26 bytes

```
\(x)Map(\(z)sum(x>=z),1:x)

```

Attempt This Online!

A function taking a vector of integers and returning a list of integers.

# Answer
> 5 votes
# Python, ~~52~~ 50 bytes

-2 thanks to @mousetail

```
lambda a:[sum(i<x for x in a)for i in range(a[0])]

```

Attempt This Online!

# Answer
> 5 votes
# , 7 bytes

```
I.i.@{.

```

Attempt This Online!

* `I.` What is the "insert before" index when inserting into the input...
* `i.@{.` Of each of the numbers 0 through n-1, where n is the first input element.

## , straightforward alternate, 9 bytes

```
[:+/#"0&1

```

Attempt This Online!

# Answer
> 5 votes
# Python, 45 bytes

```
def f(a,j=0):
 for c in-1,*a:a[:c]=c*[j];j+=1

```

Attempt This Online!

Takes a list and modifies it in place.

# Python, 34 bytes

```
lambda a:sum(a[:,1>0]>range(a[0]))

```

Attempt This Online!

### -4 thanks to @att.

Expects a NumPy array.

Ports @Command Master's pure Python.

# Answer
> 4 votes
# , 30 bytes

```
\(l)rowSums(outer(1:l,l,"<="))

```

Attempt This Online!

Slightly longer compared to pajonk's, based on this other answer of mine.

# Answer
> 4 votes
# sclin, 18 bytes

```
1X>b tpose \+/ map

```

Try it on scline!

1 repeated by n, transpose, sum each.

# Answer
> 4 votes
# Haskell, 35 bytes

```
f a=[sum[1|j<-a,i<=j]|i<-[1..a!!0]]

```

Attempt This Online!

-1 byte thanks to matteo\_c

Basically a port of Command Master's python answer

# Answer
> 4 votes
# JavaScript (ES6), 44 bytes

```
a=>a.map(g=v=>v&&g(--v,b[v]=-~b[v]),b=[])&&b

```

Try it online!

### Commented

```
a =>              // a[] = input array
a.map(g = v =>    // for each value v in a[], using a recursive
                  // callback function g:
  v &&            //   stop if v = 0
  g(              //   otherwise do a recursive call:
    --v,          //     decrement v
    b[v] = -~b[v] //     increment b[v] (set it to 1 if undefined)
  ),              //   end of recursive call
  b = []          //   start with b = []
) && b            // end of map(); return b[]

```

# Answer
> 4 votes
# Uiua, 8 bytes

```
⍘⊚⊐/⊂⊐∵⇡

```

Try it!

```
⍘⊚⊐/⊂⊐∵⇡  # [5 2 1]
     ⊐∵⇡  # [⟦0 1 2 3 4⟧ ⟦0 1⟧ ⟦0⟧] range of each
  ⊐/⊂     # [0 1 2 3 4 0 1 0]       join
⍘⊚        # [3 2 1 1 1]             occurrences

```

# Answer
> 3 votes
# Japt v2.0a0 `-Q`, 5 bytes

*-2 bytes from @AZTECCO*

```
mo yl

```

## Try it

---

# Japt v2.0a0 `-Q`, 7 bytes

There must be a shorter way

```
co ü ml

```

Try it

# Answer
> 3 votes
# Google Sheets, ~~92~~ 86 bytes

`=join(",",byrow(map(split(A1,","),lambda(n,sequence(n,1,,))),lambda(r,len(join(,r)))))`

Put the input in as a text string in cell `A1` and the formula in `B1`.

# Answer
> 3 votes
# Rust, 58 bytes

```
|a|(0..a[0]).map(move|i|a.iter().filter(|x|i<**x).count())

```

Attempt This Online!

Basically a port of Command Master's python answer

# Answer
> 3 votes
# Wolfram Language (Mathematica), 26 bytes

```
Plus@@PadRight[1^Range@#]&

```

Try it online!

-12 bytes from @att

# Answer
> 3 votes
# PARI/GP, 37 bytes

```
a->Vecrev(vecsum([x^i-1|i<-a])/(x-1))

```

Attempt This Online!

---

# PARI/GP, 37 bytes

```
a->[vecsum([t>=n|t<-a])|n<-[1..a[1]]]

```

Attempt This Online!

# Answer
> 2 votes
# Vyxal, 3 bytes

```
ẋ∩@

```

Try it Online!

```
ẋ    Repeat (each value in list times value)
 ∩   Transpose list
  @  Length of each item in list

```

# Answer
> 2 votes
# Charcoal, 10 bytes

```
ＩＥ⌈θΣＸ⁰÷ιθ

```

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

```
   θ        Input list
  ⌈         Maximum
 Ｅ          Map over implicit range
      ⁰     Literal integer `0`
     Ｘ      Vectorised raise to power
        ι   Current value
       ÷    Vectorised integer divided by
         θ  Input list
    Σ       Take the sum
Ｉ           Cast to string
            Implicitly print

```

# Answer
> 2 votes
# Retina 0.8.2, 44 bytes

```
\d+
$*_
\G_(?<=(?=(\2_*,?)+)(_+))
$#1,
\D+$

```

Try it online! Takes I/O as comma-separated integers but test cases removes and reinserts spaces for convenience. Explanation:

```
\d+
$*_

```

Convert to unary.

```
\G_(?<=(?=(\2_*,?)+)(_+))
$#1,

```

For `1` up to the first array entry, count how many entries are less than or equal the value.

```
\D+$

```

Remove the trailing junk.

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

```
+⌿≤⌸∘⍸

```

Try it on APLgolf!

# Answer
> 2 votes
# Ruby, 37 bytes

```
->l{l[0].times.map{|x|l-=[x];l.size}}

```

Try it online!

# Answer
> 2 votes
# C (clang), ~~59~~ 53 bytes

```
i;f(*a,z){for(i=0;z;i+=i<a[--z]&&printf("%d ",++z));}

```

Try it online!

* -1 thanks to @ceilingcat
`i<=*a;` -\> `*a/i`
* Golfed another 5 Bytes by @att.

`for(i=1;i<=*a;)` loops until we print a\[0\] times

`i>a[z-1]?` check i against last value in input

`z--` move to previous position in input if greater

`:printf("%d ",z` else print position in input `,i++)` and increment printed count

I think there can be a way to iterate i backwards.. e.g. `for(i=*a;i..` but my brains are cooking.

# Answer
> 2 votes
# Desmos, 36 bytes

```
f(l)=[l[l>=i].lengthfori=[1...l[1]]]

```

Try It On Desmos!

Try It On Desmos! - Prettified

This works because we can assume that the input is always in descending order as per OP's comment.

# Answer
> 2 votes
# Pip, 9 bytes

```
#*<|ZJ1Xg

```

Try It Online!

# Answer
> 2 votes
# K (ngn/k), 9 bytes

```
.#'=,/!:'

```

Try it online!

# Answer
> 2 votes
# Scala 3, 41 bytes

Saved some bytes thanks to the comment of @Kjetil S

---

```
a=>(1to a(0)).map{i=>a.count(_>=i)}.toSeq

```

Attempt This Online!

# Answer
> 1 votes
# Nekomata, 3 bytes

```
1D∑

```

Attempt This Online!

A port of @Unrelated String's Jelly answer.

```
1D∑
1D      Convert to base 1
  ∑     Sum

```

---

# Nekomata, 3 bytes

```
rjŢ

```

Attempt This Online!

A port of @Command Master's 05AB1E answer.

```
rjŢ
r       Range
 j      Join
  Ţ     Count occurrences of each unique element

```

# Answer
> 1 votes
# AWK, 53 bytes

```
i=split($0,p){for($0=j="";i;i--)while(j<p[i])$++j=i}1

```

Try it online!

# Answer
> 1 votes
# PowerShell Core, 37 bytes

```
1..($a=$args)[0]|%{($a-ge++$i).Count}

```

Try it online!

Takes a list of integers, returns a list of integers

```
1..($a=$args)[0]|%{($a-ge++$i).Count}
1..($a=$args)[0]|%{                 }  From 1 to the value of the first element number
                   ($a-ge++$i).Count   Return the number of numbers greater than the current iteration count

```

# Answer
> 1 votes
# Perl 5, 36 bytes

```
sub{map{//;0+grep$_>=$',@_}1..$_[0]}

```

Try it online!

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

Prompts for input:

```
+⌿⊃,⎕⍴¨1

```

Try it online! Thanks to Dyalog Classic

---
Tags: code-golf
---


title: Positional Bathroom Etiquette

text:
# Question
Title: Positional Bathroom Etiquette
### Background

Bathroom Etiquette, when pertaining to the available urinals, states that the next urinal to be filled in should be the one that minimizes the total discomfort. The total discomfort equation is given by the following set of equations:

```
**dist(x,y)** = linear distance between person x and person y in Urinal Units
**discomfort(x)** = sum(1/(dist(x,y)*dist(x,y))) for all persons y excluding person x
**total_Discomfort** = sum(discomfort(x)) for all x

```

A more in depth paper dealing with a similar (not the exact same) problem can be found here: (Thanks to @Lembik for alerting me to this amazing whitepaper!)

---

### Input/Output

Given an input of a empty and full urinals, output the resulting set of urinals with the addition of one person. If there is a tie for a position the urinals should fill in left to right. The output should be in the same format as the input.

* If given a case with full urinals, return the input.
* The input will always have at least one urinal defined.

---

### Test Cases

```
**INPUT     -> OUTPUT**
1000001   -> 1001001
101010101 -> 111010101
100       -> 101
00000     -> 10000
1111111   -> 1111111
0100      -> 0101
101000    -> 101001

```

---

### Rules

This is , so shortest code in bytes wins. Standard loop-holes are forbidden.

# Answer
> 4 votes
# Jelly, ~~13~~ 12 bytes

```
J_þTİ²SiṂ$Ṭo

```

Try it online! or Verify all test cases.

## Explanation

```
J_þTİ²SiṂ$Ṭo  Input: boolean array A
J             Indices, returns [1, 2, ..., len(A)]
   T          Truthy indices, returns the indices which have a truthy value
 _þ           Form the subtraction (_) table (þ) between them
    İ         Inverse, find the reciprocal of each
     ²        Square each
      S       Sum the sublists column-wise
         $    Monadic chain
        Ṃ       Minimum
       i        Find the first index of that
          Ṭ   Untruth indices, returns a boolean array with 1's at those indices
           o  Logical OR between that and A, and return

```

# Answer
> 11 votes
# MATL, ~~19~~ ~~18~~ 17 bytes

```
lyf!Gn:-H_^Xs&X<(

```

Try it online! Or verify all test cases (slightly modified code).

### Explanation

It suffices to compute the distance from each potential new position to the already occupied ones. The remaining distances are do not depend on the potential new position, and so constitute a constant term, which can be ignored.

Let's take input `[1 0 0 0 0 0 1]` as an example.

```
l      % Push 1
       % STACK: 1
y      % Take input implicitly. Duplicate from below
       % STACK: [1 0 0 0 0 0 1], 1, [1 0 0 0 0 0 1]
f!     % Indices of nonzero elements, as a column array
       % STACK: [1 0 0 0 0 0 1], 1, [1 7]
Gn:    % Push [1 2 ... n], where n is input size (array of possible positions)
       % STACK: [1 0 0 0 0 0 1], 1, [1; 7], [1 2 3 4 5 6 7]
-      % Matrix with all pairs of differences
       % STACK: [1 0 0 0 0 0 1], 1, [1; 7], [0 -1 -2 -3 -4 -5 -6;
                                             6  5  4  3  2  1  0]
H_^    % Raise each entry to -2
       % STACK: [1 0 0 0 0 0 1], 1, [   Inf 1.0000 0.2500 0.1111 0.0625 0.0400 0.0278;
                                     0.0278 0.0400 0.0625 0.1111 0.2500 1.0000    Inf]
Xs     % Sum of each column
       % STACK: [1 0 0 0 0 0 1], 1, [Inf 1.04 0.3125 0.2222 0.3125 1.04 Inf]
&X<    % Index of minimum. Takes the first if there is a tie
       % STACK: [1 0 0 0 0 0 1], 1, 4
(      % Assign: write 1 at the position of the minimizer
       % STACK: [1 0 0 1 0 0 1]
       % Implicitly display

```

# Answer
> 4 votes
## JavaScript (ES6), 89 bytes

```
a=>a[a.map((e,i)=>!e&&(t=0,a.map((e,j)=>t+=(j-=i)&&e/j/j),t<m&&(m=t,k=i)),k=0,m=1/0),k]=1

```

Outputs by modifying the input array.

# Answer
> 4 votes
# R, ~~83~~ ~~76~~ 67 bytes

Just realized that I can save several bytes by not bothering to check if the candidate urinals are empty. Non-empty urinals will always return an `Inf` discomfort value, so they're excluded in the course of the calculation. Also, just using direct indexing rather than `replace`, so it's shorter but less elegant.

```
x=scan()
x[which.min(rowSums(outer(seq(x),which(!!x),`-`)^-2))]=1
x

```

### Explanation

```
x=scan()

```

We read the current state from stdin and call it `x`. We assume that the input is a sequence of `1`s and `0`s separated by spaces or newlines. For the purposes of the explanation, let's say we input `1 0 0 0 0 0 1`.

```
x[which.min(rowSums(outer(seq(x),which(!!x),`-`)^-2))]=1

```

We replace a value of `x` at a particular index with 1. Everything between the `[ ]` is figuring out what the best index is.

Since the existing urinals are immutable, we don't need to consider the distances between them. We only need to consider the distances between the occupied urinals and the possible new one. So we determine the indices of the occupied urinals. We use `which`, a function to return the indices of a logical vector which are `TRUE`. All numbers in R, when coerced to type `logical`, are `TRUE` if nonzero and `FALSE` if zero. Simply doing `which(x)` will result in a type error, `argument to 'which' is not logical`, as `x` is a numeric vector. We therefore have to coerce it to logical. `!` is R's logical negation function, which automatically coerces to logical. Applying it twice, `!!x`, yields a vector of `TRUE` and `FALSE` indicating which urinals are occupied. (Alternative byte-equivalent coercions to logical involve the logical operators `&` and `|` and the builtins `T` and `F`, e.g. `F|x` or `T&x` and so on. `!!x` looks more exclamatory so we'll use that.)

```
                                 which(!!x)

```

This is paired with `seq(x)`, which returns the integer sequence from `1` to the length of `x`, i.e. all urinal locations (and thus all possible locations to consider).

```
                          seq(x)

```

Now we have the indices of our occupied urinals: `1 7` and our empty urinals `1 2 3 4 5 6 7`. We pass ``-``, the subtraction function, to the `outer` function to get the "outer subtraction", which is the following matrix of distances between all urinals and the occupied urinals:

> \[,1\] \[,2\]
>
> \[1,\] 0 -6
>
> \[2,\] 1 -5
>
> \[3,\] 2 -4
>
> \[4,\] 3 -3
>
> \[5,\] 4 -2
>
> \[6,\] 5 -1
>
> \[7,\] 6 0

```
                    outer(seq(x),which(!!x),`-`)

```

We raise this to the `-2`th power. (For those who are a little lost, in the OP, "discomfort" is defined as `1 / (distance(x, y) * distance(x, y))`, which simplifies to `1/d(x,y)^2`, i.e. `d(x,y)^-2`.)

```
                    outer(seq(x),which(!!x),`-`)^-2

```

Take the sum of each row in the matrix.

```
            rowSums(outer(seq(x),which(!!x),`-`)^-2)

```

Get the index of the smallest value, i.e. the optimal urinal. In the case of multiple smallest values, the first (i.e. leftmost) one is returned.

```
  which.min(rowSums(outer(seq(x),which(!!x),`-`)^-2))

```

And voilà, we have the index of the optimal urinal. We replace the value at this index in `x` with `1`. In the case of `1111` as input, it doesn't matter which one we replace, we'll still have a valid output.

```
x[which.min(rowSums(outer(seq(x),which(!!x),`-`)^-2))]=1

```

Return the modified input.

```
x

```

# Answer
> 2 votes
# Python 3 ~~223~~ ~~222~~ 165 Bytes

Okay, I know this isn't the prettiest answer out there, and I'm sure it can be golfed down quite a bit, but I was just messing around and seeing what I could do

Shout out to mbomb007 for the tips on whitespace and comparators Also, I saw my online character counter was taking all the tabs and turning them into spaces, so the count is a lot less than I originally had

```
def u(a):
 m,r,x=9,0,len(a)
 for i in range(x):
    d=0
    if a[i]<'1':
     for j in range(x):
        if a[j]>'0':d+=float((j-i)**-2)
     if d<m:r=i;m=d
 return a[:r]+'1'+a[r+1:]

```

Showing revised whitespace:

```
def u(a):
<sp> m,r,x=9,0,len(a)
<sp> for i in range(x):
<tab> d=0
<tab> if a[i]<'1':
<tab><sp> for j in range(x):
<tab><tab> if a[j]>'0':d+=float((j-i)**-2)
<tab><sp> if d<m:r=i;m=d
<sp> return a[:r]+'1'+a[r+1:]

```

Original:

```
def u(a):
    m,r,x=9,0,len(a)
    for i in range(x):
        d=0
        if a[i]!='1':
            for j in range(x):
                if a[j]=='1':d+=float(1/(j-i)**2)
            if d<m:r=i;m=d
    return a[:r]+'1'+a[r+1:]

```

This expects a string passed to it of 1's and 0's like `"10001"` and returns a string `"10101"`

Edit: Changed `1/float((j-i)**2)` to `float((j-i)**-2)`

# Answer
> 2 votes
## PHP, 135 bytes

```
$a=explode(1,$argv[1]);$b=0;foreach($a as$c=>$d){$l=strlen($d);if($l>$b){$b=$l;$e=$c;}}if($b)$a[$e][intval($b/2)]=1;echo implode(1,$a);

```

I'm sure there's a considerably quicker way of doing it, but I've got a fuzzy head and can't think of one!

### Old code

The code without minification:

```
$a=explode(1,$argv[1]);
$b=0;
foreach($a as $c=>$d){
    $l=strlen($d);
    if($l>$b){
        $b=$l;
        $e=$c;
    }
}
if($b){
    $a[$e][intval($b/2)]=1;
}
echo implode(1,$a);

```

# Answer
> 2 votes
# Python 3, ~~574~~ ~~471~~ 347 bytes

I'll probably work on this some more, considering the other Python solution is like a fifth of this one :\[.

```
def a(I):
 D,l,r={},len(I),range
 for i in r(l):
  if I[i]<1:
   n,t,n[i]=I[:],[],1
   for j in r(l):
    if n[j]>0:
     q,Q=[],0
     for k in r(l):
      if k!=j and n[k]>0:q.append((k-j,j-k)[k<j])
     for i in q:Q+=1/(i**2)
    t.append(Q)
   T=sum(t)
   if T not in D.keys():D[T]=i
 if len(D)>0:I[D[min(D.keys())]]=1
 print(I)

```

Well that's much better now that I've learned you can use single spaces.

# Answer
> 1 votes
# Python, ~~165~~ ~~163~~ ~~158~~ ~~147~~ ~~141~~ ~~140~~ 139 bytes

```
def u(p):e=enumerate;a=[(sum((i-j)**-2for j,y in e(p)if"0"<y),i)for i,x in e(p)if"1">x];return a and p[:min(a)[1]]+"1"+p[min(a)[1]+1:] or p

```

# Answer
> 1 votes
# 05AB1E, 18 bytes

```
$āsƶ0Kδ-znD_°+OWkǝ

```

I/O as a list.

Port of *@miles*' Jelly answer, so make sure to upvote that answer as well!
Unfortunately, dividing by 0 won't result in `INF` in 05AB1E like it does in Jelly and MATL, but instead in `0`. So 4 bytes (`D_°+`) are to account for that..

Try it online or verify all test cases.

**Explanation:**

```
$                  # Push 1 and the input-list
 ā                 # Push a list in the range [1,length] (without popping the list)
  s                # Swap so the input-list is at the top again
   ƶ               # Multiply each value by its 1-based index
    0K             # Remove all 0s
      δ-           # Pop both lists, and create a subtraction table
        z          # Convert each inner value to 1/value
         n         # Square each inner value
          D        # Duplicate this list
           _       # Check for each inner value whether it equals 0 (1 if 0; 0 otherwise)
            °      # Take 10 to the power this (10 if 0; 1 otherwise)
             +     # Add it to each value at the same positions
              O    # Sum each inner list
               W   # Push the minimum (without popping the list)
                k  # Pop both, and push the (first) (0-based) index of this minimum
                 ǝ # Insert the 1 at this index into the (implicit) input-list
                   # (after which the result is output implicitly)

```

# Answer
> 0 votes
# Scala, 173 bytes

Golfed version. Try it online!

```
a=>{var(m,r,x,d)=(9d,0,a.size,0d);for(i<-0 to x-1)if(a(i)=='0'){d=0;for(j<-0 to x-1)if(a(j)=='1')d+=math.pow(j-i,-2);if(d<m){r=i;m=d}};a.substring(0,r)+'1'+a.substring(r+1)}

```

Ungolfed version. Try it online!

```
object Main {
  def u(a: String): String = {
    var m = 9.0
    var r = 0
    val x = a.length
    for (i <- 0 until x) {
      var d = 0.0
      if (a(i) == '0') {
        for (j <- 0 until x) {
          if (a(j) == '1') {
            d += math.pow(j - i, -2)
          }
        }
        if (d < m) {
          r = i
          m = d
        }
      }
    }
    a.substring(0, r) + '1' + a.substring(r + 1)
  }

  def main(args: Array[String]): Unit = {
    println(u("1000001"))    // should print: 1001001
    println(u("101010101"))  // should print: 111010101
    println(u("100"))        // should print: 101
    println(u("00000"))      // should print: 10000
    println(u("1111111"))    // should print: 1111111
    println(u("0100"))       // should print: 0101
    println(u("101000"))     // should print: 101001
  }
}

```

---
Tags: code-golf
---


title: Implement grambulation

text:
# Question
Title: Implement grambulation
Consider the following spiral of positive integers:

We now define grambulation as a binary operation \\$\lozenge : \mathbb N \times \mathbb N \to \mathbb N\\$, using this grid. Some example inputs and outputs for grambulation are:

\begin{align\*} 1 & \lozenge 9 = 25 \\ 1 & \lozenge 2 = 11 \\ 11 & \lozenge 10 = 25 \\ 9 & \lozenge 1 = 5 \\ 19 & \lozenge 4 = 13 \\ 76 & \lozenge 6 = 62 \\ 17 & \lozenge 17 = 17 \\ 62 & \lozenge 55 = 298 \end{align\*}

Feel free to try to figure out the pattern before continuing.

---

### How to grambulate \\$x\\$ and \\$y\\$

The two coordinates of the inputs, \\$x \lozenge y\\$, in the spiral grid above are found, where \\$1\\$ is located at \\$(0, 0)\\$, \\$2\\$ at \\$(1, 0)\\$ and so on. For \\$x \lozenge y\\$, call these coordinates \\$x'\\$ and \\$y'\\$. You then find the vector from \\$x'\\$ to \\$y'\\$, and calculate the coordinates found by applying this vector to \\$y'\\$.

A worked example: \\$3 \lozenge 11 = 27\\$. First, we calculate our coordinates: $$x' = (1, 1), y' = (2, 0).$$ Next, we see that the vector from \\$x'\\$ to \\$y'\\$ is \\$\vec v = (+1, -1)\\$. Finally, we add this to \\$y'\\$ to get the coordinate \\$(3, -1)\\$, which is the coordinates of \\$27\\$.

Alternatively, a visual demonstration:

Note from the \\$62 \lozenge 55 = 298\\$ example above, our spiral is not limited to integers below \\$121\\$, and in fact, this binary operation is well defined for all pairs of positive integers.

Some properties of grambulation:

* \\$x \lozenge x = x\\$
* \\$x \lozenge y = z \iff z \lozenge y = x\\$
* It is non-associative and non-commutative
* It is non-injective but is surjective
* \\$x^2 \lozenge y^2 = z^2\\$ where \\$x \< y\\$ and \\$x, y, z\\$ all have the same parity

Additionally, \\$x^2 \lozenge y^2 = z^2 - 1\\$ where \\$x\\$ and \\$y\\$ have different parities

Further, \\$x^2 \lozenge (x + 2c)^2 = (x + 4c)^2\\$ for \\$x, c \in \mathbb N\\$.

---

Given two positive integers \\$x, y \in \mathbb N\\$, output \\$x \lozenge y\\$. You may take input and output in any reasonable format or method, and this is , so the shortest code in bytes wins.

Note that the order of inputs does matter (\\$x \lozenge y \ne y \lozenge x\\$ for most \\$x, y \in \mathbb N\\$), but you may take input in either consistent order.

### Test cases

```
  x   y   x◊y
  1   9    25
  1   2    11
 11   2     1
 11  10    25
  9   1     5
 19   4    13
 76   6    62
 17  17    17
 62  55   298
  3  11    27
 16 400  1296
182 240   306
249   1   281
281   1   249
 32  98   196
 88  16   202
 60  41   210
 59  85   227

```

And, a visual guide for the last few, on a larger grid:

# Answer
# MATL, 22 bytes

```
sQ1YLXIG"I@=&fh]Ew-X{)

```

**Try it online!**

As a **bonus**, see the beautiful pattern of the function for all pairs of inputs from 1 to *L*. MATL Online times out for *L* moderately large, but here's the result for *L*=100 (click here for a view with better resolution):

### How it works

```
        % Implicit input: row vector of two numbers.
sQ      % Sum, add 1. This is enough for the size of the spiral
1YL     % Matrix with spiral of that size
XI      % Copy into clipboard I
G"      % For each number in the input
  I     %   Push the spiral again
  @=    %   True for the entri that equals the number
  &fh   %   Row and column indices of that entry as a vector of two numbers
]       % End
E       % Multiply by two, element-wise
w-      % Swap, subtract. Gives the coordinates of the result
X{      % Convert to cell array, for indexing
)       % Index into the spiral
        % Implcit display

```

The version with graphical input is as above but replaces the input by a loop over all pairs of values from 1 to *L*. The results are concatenated and reshaped as a square matrix, which is displayed with the `autumn` colormap.
> 11 votes

# Answer
# Pyth, ~~49~~ ~~32~~ 31 bytes

```
@Jsua_MCG+LheeGUGysQ]]1s-MPBxLJ

```

Try it online!

Takes input as `[y, x]`.

* `Jsua_MCG+LheeGUGysQ]]1`: Generate the spiral to a sufficient size, then collapse it to a flat list and save it in `J`.
* `xLJ`: Find the index in J of the two inputs.
* `s-MPB`: Convert to the target index.
* `@`: Index into `J` to get the target number.
> 6 votes

# Answer
# Wolfram Language (Mathematica), 187 bytes

```
(t=(n=#;{1,-1}(Sum[#[.5π⌊(4k-3)^.5⌋],{k,n-1}]&/@{Sin,Cos}))&;(x=#1;y=#2;s=#1+#2;Which[x>y&&x>-y,(2x-1)^2+s,x<=y&&x>-y,4y^2-s+1,x<=y&&x<=-y,4x^2-s+1,True,(2y-1)^2+s])&@@(2t@#2-t@#1))&

```

Try it online!

Ungolfed self-explained:

```
Clear[toXY, fromXY, main];
toXY[n_] := {
   Sum[
     Sin[.5 π ⌊Sqrt[4 k - 3]⌋], {k,
      n - 1}],
  -Sum[
      Cos[-.5 π ⌊Sqrt[4 k - 3]⌋], {k,
       n - 1}]};

fromXY[{x_, y_}] := Which[
   x > y && x > -y, (x*2 - 1)^2 + (x + y),
   x <= y && x > -y, (y*2)^2 - (x + y) + 1,
   x <= y && x <= -y, (x*2)^2 - (x + y) + 1,
   True, (y*2 - 1)^2 + (x + y)
   ];

main[n1_, n2_] := fromXY[2 toXY@n2 - toXY@n1];

```
> 5 votes

# Answer
# JavaScript (ES6), 132 bytes

Expects `(p)(q)` and returns \\$p\lozenge q\\$.

```
p=>q=>((g=(t,h=o=[1],v=n=x=y=0)=>n==t|x+[,y]==t?x:g(t,(i=o[o[[x-=h,y-=v]]=++n,[x-v,y+h]])?h:v,i?v:-h))(q),Y=2*y,g([2*x-g(p),Y-y]),n)

```

Try it online!

### How?

The helper function \\$g\\$ expects a target \\$t\\$ which is either the index *or* the coordinates of an element in the spiral.

Whenever \\$g\\$ is called, it starts at the origin and walks through the spiral until the target is reached, keeping track of its index \\$n\\$ and its position \\$(x,y)\\$ (all these variables being available in the global scope).

We first invoke \\$g(q)\\$ to get the coordinates \\$(X,Y)\\$ of the 2nd element, then \\$g(p)\\$ to get the coordinates \\$(x,y)\\$ of the 1st element, and finally \\$g(\[2X-x,2Y-y\])\\$ to get the index of \\$p\lozenge q\\$.
> 4 votes

# Answer
# Pyth, ~~65~~ ~~47~~ ~~45~~ ~~38~~ ~~34~~ ~~31~~ 30 bytes

*-18 bytes by changing the loop structure*
*-2 bytes by altering some assignment*
*-7 bytes by switching to integer coordinates*
*-1 byte from swapping input order, -3 bytes from better list construction*
*-3 bytes by switching to imaginary coordinates*
*-1 byte from better representation of i*

```
xJ+bm=+Z^.j).Ey@d2^sQ3_i@LJQ_2

```

Try it online!

Takes input as a list of integers `[y,x]`. Generates a list `J` of spiral coordinates in the imaginary plane, then gets the index in `J` for `2*J[y] - J[x]`. To generate this list, we take advantage of the fact that `ceil(2*sqrt(x))` stays the same values for increasingly long intervals, in the exact same way that the direction of travel when traversing this kind of spiral does.

### Explanation

```
                                  # implicitly assign Z = 0 and Q = eval(input())
 J                                # assign J to
    m             ^sQ3            # map range(sum(Q)**3) over lambda d
     =+Z                          #   add and assign to Z
        ^.j)                      #   i to the power of
            .E                    #   ceiling
              y@d2                #   2 * sqrt(d)
  +b                              # prepend a char (to offset list)
xJ                                # find the index in J of
                        @LJQ      # map x and y to their coordinates in J
                      _i    _2    # double the first and subtract the second

```
> 4 votes

# Answer
# Wolfram Language (Mathematica), ~~60~~ ~~59~~ 58 bytes

```
1//.i_/;{1,-2,1}.Tr/@+I^⌈2√Range[{##,i}-1]⌉!=0:>i+1&

```

Try it online!

Input `[x, y]`.
> 4 votes

# Answer
# Raku, 74 bytes

```
{.first(2*.[$^b]-.[$^a]):k given ½,0,|[\+] flat (1,*i...*)Zxx(1,1.5...*)}

```

Try it online!

* `{ expr1 given expr2 }` is the function body. It evaluates `expr1` after assigning the value of `expr2` to the `$_` topic variable. `expr2` here is an expression for the lazy infinite sequence of spiral coordinates, in the form of complex numbers.
* `(1, *i ... *)` is the sequence of `1`, `i`, `-1`, and `-i`, repeated infinitely.
* `(1, 1.5 ... *)` is the infinite arithmetic sequence 1, 1.5, 2, 2.5, 3, 3.5, ....
* `Zxx` `Z`ips the two preceding sequences together using the `xx` replication operator: `1 xx 1`, `i xx 1.5`, `-1 xx 2`, `-i xx 2.5`, .... The half-integer replication numbers are rounded down, producing `(1)`, `(i)`, `(-1, -1)`, `(-i, -i)`, `(1, 1, 1)`, `(i, i, i)`, ....
* `flat` flattens that list of lists.
* `[\+]` scans that list with the addition operator `+`, producing the infinite list of partial sums. This is the spiral, except that it lacks the first origin element `0`.
* `½, 0, |...` pastes the origin `0` onto the front of the spiral, as well as another leading element `½` to make the whole thing 1-indexed instead of 0-indexed.
* `.[$^a]` and `.[$^b]` are the coordinates in the spiral of the first and second arguments to the function, respectively.
* `2 * .[$^b] - .[$^a]` are the coordinates of the grambulated output.
* `.first(...):k` finds the first index (thanks to the `:k`ey adverb) within the spiral where the value is the coordinates found in the previous step.
> 4 votes

# Answer
# Charcoal, 68 bytes

```
ＮθＮη≔⁰ζ≔⁰εＷ¬ε«⊞υ⟦ⅈⅉ⟧≧⁺⊗¬ΣＫＤ²✳⁺²ζζ✳ζ¹¿›Ｌυ⌈⟦θη⟧≔⊕⌕υＥ§υ⊖η⁻⊗κ§§υ⊖θλε»⎚Ｉε

```

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

```
ＮθＮη

```

Input `x` and `y`.

```
≔⁰ζ

```

Start in an arbitrary direction.

```
≔⁰ε

```

Start not knowing `x◊y`.

```
Ｗ¬ε«

```

Repeat until `x◊y` is known.

```
⊞υ⟦ⅈⅉ⟧

```

Save the current position.

```
≧⁺⊗¬ΣＫＤ²✳⁺²ζζ

```

Turn if this is a corner.

```
✳ζ¹

```

Take one step.

```
¿›Ｌυ⌈⟦θη⟧

```

If we know `x'` and `y'`, then...

```
≔⊕⌕υＥ§υ⊖η⁻⊗κ§§υ⊖θλε

```

... see if we can find `x◊y`.

```
»⎚Ｉε

```

Output `x◊y`.

I tried using complex numbers but that also took 68 bytes:

```
ＮθＮη≔⁰ζ≔⁰ε≔¹δＷ¬ζ«⊞υεＦ¬№υ⁺ε×δＩ1j≧×Ｉ1jδ≧⁺δε¿›Ｌυ⌈⟦θη⟧≔⊕⌕υ⁻⊗§υ⊖η§υ⊖θζ»Ｉζ

```

Attempt This Online! Link is to verbose version of code. Explanation:

```
ＮθＮη

```

Input `x` and `y`.

```
≔⁰ζ

```

Start not knowing `x◊y`.

```
≔⁰ε≔¹δ

```

Start at the origin in an arbitrary direction.

```
Ｗ¬ζ«

```

Repeat until `x◊y` is known.

```
⊞υε

```

Save the current position.

```
Ｆ¬№υ⁺ε×δＩ1j

```

If this is a corner, then...

```
≧×Ｉ1jδ

```

... rotate the direction.

```
≧⁺δε

```

Take one step.

```
¿›Ｌυ⌈⟦θη⟧

```

If we know `x'` and `y'`, then...

```
≔⊕⌕υ⁻⊗§υ⊖η§υ⊖θζ

```

... see whether we know `x◊y`.

```
»Ｉζ

```

Output `x◊y`.
> 2 votes

# Answer
# Uiua, 47 chars

```
f←⁅≡/+○[¯+η.÷2×π⌊√-3×4↘1⇡]
+1⊗-∶×2⊃∩f(∵f↘1⇡ⁿ3+)

```

Try It Online!

takes input as y,x on the stack
> 2 votes

# Answer
# Scala, 395 bytes

395 bytes, it can be golfed much more. Golfed version. Try it online!

```
import scala.math._
type D=Double
def t(n:D)=(1 to n.toInt-1).map(k=>sin(.5*Pi*floor(sqrt(4*k-3)))).sum-> -(1 to n.toInt-1).map(k=>cos(-.5*Pi*floor(sqrt(4*k-3)))).sum
def f(p:(D,D))={val(x,y)=p
if(x>y&&x> -y)pow(2*x-1,2)+(x+y)else if(x<=y&&x> -y)pow(2*y,2)-(x+y)+1 else if(x<=y&&x<= -y)pow(2*x,2)-(x+y)+1 else pow(2*y-1,2)+(x+y)}
def m(n1:D,n2:D)={val(x,y)=t(n2);val(a,b)=t(n1);f((2*x-a,2*y-b))}

```

Ungolfed version. Try it online!

```
import scala.math._

object Main {
  def toXY(n: Double): (Double, Double) = {
    val x = (1 until n.toInt).map(k => sin(.5 * Pi * floor(sqrt(4 * k - 3)))).sum
    val y = -(1 until n.toInt).map(k => cos(-.5 * Pi * floor(sqrt(4 * k - 3)))).sum
    (x, y)
  }

  def fromXY(point: (Double, Double)): Double = {
    val (x, y) = point
    if(x > y && x > -y) pow(2*x - 1, 2) + (x + y)
    else if(x <= y && x > -y) pow(2*y, 2) - (x + y) + 1
    else if(x <= y && x <= -y) pow(2*x, 2) - (x + y) + 1
    else pow(2*y - 1, 2) + (x + y)
  }

  def main(n1: Double, n2: Double): Double = {
    val (x, y) = toXY(n2)
    val (a, b) = toXY(n1)
    fromXY((2*x - a, 2*y - b))
  }

  def main(args: Array[String]): Unit = {
    println(main(182, 240))
  }
}

```
> 0 votes

---
Tags: code-golf, integer, grid
---


title: Sliding Capitals

text:
# Question
Title: Sliding Capitals
### The Background

Imagine the English alphabet written out in a row in capital letters -- `ABCDEFGHIJKLMNOPQRSTUVWXYZ`. Suppose we have a special variable-width lens such that, when placed over the row, it shows a certain "window" of the alphabet, with letters outside the lens hidden from view. Additionally, this lens has a warping characteristic, so that the first letter inside the lens, and every second letter thereafter, is lower-cased, but the remaining letters still show capitalized.

For example, we could have a lens of length 5 placed somewhere in the middle of the alphabet and we would only see `. jKlMn` (leading period here to ensure whitespace shows) -- note the `K` and `M` are still capitalized, while the `j`, `l`, and `n` are all lower-cased. As we slide this lens from left-to-right along the alphabet, different letters would be shown and different letters capitalized. The task here is to output the resultant letters as the lens slides along the alphabet.

### The Challenge

Write a program or function that takes an input integer `0 < n < 27` and outputs or returns the string(s) that are visible as the lens described above slides across the alphabet.

For values of `n` larger than `1`, the lens begins by "hanging" off the left side of the alphabet, so only the `A` is shown in the right-most slot of the lens. The first line of any output will thus be a single `A`, either capital or lowercase depending upon the length of the lens.

Similarly, the lens finishes sliding when the `Z` is in the left-most slot of the lens (meaning that the very last line in any output will always be 25 spaces followed by a lowercase `z`).

### The Examples

Input: `1`

Output:

```
a
 b
  c
   d
    e
     f
      g
       h
        i
         j
          k
           l
            m
             n
              o
               p
                q
                 r
                  s
                   t
                    u
                     v
                      w
                       x
                        y
                         z

```

Input: `4`

Output:

```
A
aB
AbC
aBcD
 bCdE
  cDeF
   dEfG
    eFgH
     fGhI
      gHiJ
       hIjK
        iJkL
         jKlM
          kLmN
           lMnO
            mNoP
             nOpQ
              oPqR
               pQrS
                qRsT
                 rStU
                  sTuV
                   tUvW
                    uVwX
                     vWxY
                      wXyZ
                       xYz
                        yZ
                         z

```

Input: `26`

Output:

```
A
aB
AbC
aBcD
AbCdE
aBcDeF
AbCdEfG
aBcDeFgH
AbCdEfGhI
aBcDeFgHiJ
AbCdEfGhIjK
aBcDeFgHiJkL
AbCdEfGhIjKlM
aBcDeFgHiJkLmN
AbCdEfGhIjKlMnO
aBcDeFgHiJkLmNoP
AbCdEfGhIjKlMnOpQ
aBcDeFgHiJkLmNoPqR
AbCdEfGhIjKlMnOpQrS
aBcDeFgHiJkLmNoPqRsT
AbCdEfGhIjKlMnOpQrStU
aBcDeFgHiJkLmNoPqRsTuV
AbCdEfGhIjKlMnOpQrStUvW
aBcDeFgHiJkLmNoPqRsTuVwX
AbCdEfGhIjKlMnOpQrStUvWxY
aBcDeFgHiJkLmNoPqRsTuVwXyZ
 bCdEfGhIjKlMnOpQrStUvWxYz
  cDeFgHiJkLmNoPqRsTuVwXyZ
   dEfGhIjKlMnOpQrStUvWxYz
    eFgHiJkLmNoPqRsTuVwXyZ
     fGhIjKlMnOpQrStUvWxYz
      gHiJkLmNoPqRsTuVwXyZ
       hIjKlMnOpQrStUvWxYz
        iJkLmNoPqRsTuVwXyZ
         jKlMnOpQrStUvWxYz
          kLmNoPqRsTuVwXyZ
           lMnOpQrStUvWxYz
            mNoPqRsTuVwXyZ
             nOpQrStUvWxYz
              oPqRsTuVwXyZ
               pQrStUvWxYz
                qRsTuVwXyZ
                 rStUvWxYz
                  sTuVwXyZ
                   tUvWxYz
                    uVwXyZ
                     vWxYz
                      wXyZ
                       xYz
                        yZ
                         z

```

### The Rules

* Standard input/output rules apply
* Standard loopholes disallowed
* Standard code-golf rules apply
* The leading whitespace as shown is required, so that we know where we're at in the alphabet.
* **Each line cannot have trailing whitespace** (as shown - the output is not a rectangle).
* A single trailing newline is optional.

# Answer
# Pyth, 31 bytes

```
Vr_tQ26s.erb%+Nk2+*Nd:GeS,0N+NQ

```

Try it online. Test suite.

Quick and dirty.
> 2 votes

# Answer
# AWK, ~~160~~ 141 bytes

```
{d=-$1
for(m=25;i++<m+$1;print""){f="%"(++d<0?0:d<m?d:m)"s"
c=u=65
printf f,""
for(j=++E-$1;j<E&&j<26;printf(j<0?"":"%c",c+j++))c=c==u?97:u}}

```

Try it online!

Thanks to @ceilingcat, code rearranging helped to remove a `continue` statement and a total of 19 bytes
> 2 votes

# Answer
## JavaScript (ES6), 130 bytes

```
n=>[...Array(n+25)].map(_=>[...Array(26)].map(_=>String.fromCharCode(j++<i|i+n<j?32:j+(j-i)%2*32),++i,j=64).join``,i=64-n).join`\n`

```

Where `\n` represents the literal newline character. Works by looping over the output rectangle and outputting spaces outside the diagonal while adding 32 to the character code to lower case it in alternate squares. Using `replace` appears to be 1 byte longer:

```
n=>[...Array(n+25)].map(_=>' '.repeat(26).replace(/./g,s=>j++<i|i+n<j?s:String.fromCharCode(j+(j-i)%2*32),++i,j=64),i=64-n).join`\n`

```
> 2 votes

# Answer
# Jelly, 21 bytes

```
ØAżØaU¡ṁ€µJR;"z⁶Ḋḣ"JY

```

Try it online!

## How it works

```
ØAżØaU¡ṁ€µJR;"z⁶Ḋḣ"JY - Main link. Takes an integer n on the left
ØA                    - Uppercase alphabet
   Øa                 - Lowercase alphabet
  ż                   - Zip; [['A', 'a'], ['B', 'b'], ...]
      ¡               - Do n times:
     U                -   Reverse each pair
                        This means we have a leading capital for even n,
                        or a trailing capital for odd n
        €             - Over each pair:
       ṁ              -   Mold it to length n
         µ            - Begin a new link with this list of characters C
          J           - Yield [1, 2, ..., 26]
           R          - Yield [[1], [1, 2], ..., [1, 2, ..., 26]]
            ;"        - Concatenate each of these ranges with the lists in C
              z⁶      - Transpose, filling with spaces
                Ḋ     - Remove the first line
                 ḣ"J  - Remove the trailing integers from each line
                    Y - Join with newlines

```
> 1 votes

# Answer
# Python 3, 105 bytes

```
lambda n:[(i-n)*' '+''.join(chr(97+j-(j^i^n)%2*32)[:-1<j<26]for j in range(i-n,i))for i in range(1,26+n)]

```

Try it online!
> 1 votes

# Answer
# Japt `-R`, ~~21~~ 20 bytes

```
;B¬£îXpv éU)iYçÃÕmx1

```

Try it or run all test cases

```
;B¬£îXpv éU)iYçÃÕmx1     :Implicit input of integer U
;B                       :Uppercase alphabet
  ¬                      :Split
   £                     :Map each X at 0-based index Y
    î                    :  Repeat and slice to length U
     Xp                  :    Append to X
       v                 :      Its lowercase
         éU              :    Rotate right U times
           )             :  End repeat
            i            :  Prepend
             Yç          :    Y spaces
               Ã         :End map
                Õ        :Transpose
                 m       :Map
                  x1     :  Trim right
                         :Implicit output joined with newlines

```
> 1 votes

# Answer
# Charcoal, 14 bytes

```
ＵＴＦＮ«Ｐ↘⎇﹪ι²αβ↑

```

Try it online (verbose) or try it online (pure).

**Explanation:**

Toggle trim so the output won't contain any trailing spaces to comply to the challenge rules. Charcoal will make the output a rectangle by default:

```
ToggleTrim();
ＵＴ

```

Loop the input amount of times:

```
For(InputNumber()){ ... }
ＦＮ«

```

Print in a down-right diagonal direction without moving the cursor:

```
Multiprint(:DownRight, ...);
Ｐ↘

```

Print the uppercase alphabet if the loop index is odd, or the lowercase alphabet if it's even (`b`/`β` is a variable that contains the lowercase alphabet by default and `a`/`α` is a variable that contains the uppercase alphabet by default):

```
Ternary(Modulo(i, 2), a, b)
⎇﹪ι²αβ

```

And then move the cursor one position up for the next iteration:

```
Move(:Up);
↑

```
> 1 votes

# Answer
# 05AB1E, 22 bytes

```
₂Iи2.ýžpA«RŽR‘S.Λ„
¶:

```

Try it online.

Or alternatively:

```
₂2‚Iи¨ARÂu«ŽR‘S.Λ„
¶:

```

Try it online.

**Explanation:**

This program uses the Canvas builtin `Λ` to draw the output. This builtin takes three arguments:

1. Length of the lines we'll draw: the list `[26,2,26,2,...,26]` in this case:

```
        #(alternative 1)
₂       # Push 26
 Iи     # Repeat it the input amount of times as list
   2.ý  # Intersperse it with 2
        #(alternative 2)
₂2‚     # Pair 26 with 2: [26,2]
   Iи   # Repeat this list the input amount of times
     ¨  # And remove the trailing 2

```
2. Character/string to draw: the string `"zyxwvutsrqponmlkjihgfedcbaABCDEFGHIJKLMNOPQRSTUVWXYZ"` in this case:

```
        #(alternative 1)
žp      # Push builtin string "ZYXWVUTSRQPONMLKJIHGFEDCBA"
  A«    # Append builtin string "abcdefghijklmnopqrstuvwxyz"
    R   # Reverse this string to "zyxwvutsrqponmlkjihgfedcbaABCDEFGHIJKLMNOPQRSTUVWXYZ"
        #(alternative 2)
A       # Push builtin "abcdefghijklmnopqrstuvwxyz"
 R      # Reverse it: "zyxwvutsrqponmlkjihgfedcba"
  Â     # Bifurcate it (short for Duplicate & Reverse copy)
   u    # Uppercase the reversed copy "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    «   # Append it: "zyxwvutsrqponmlkjihgfedcbaABCDEFGHIJKLMNOPQRSTUVWXYZ"

```
3. The direction to draw in: `[7,0,3,0]`. The digits in the range `[0,7]` each represent a certain direction:

```
7   0   1
  ↖ ↑ ↗
6 ← X → 2
  ↙ ↓ ↘
5   4   3

```

So the `[7,0,3,0]` in this case translates to the directions \\$\[↖,↑,↘,↑\]\\$:

```
ŽR‘     # Push compressed integer 7030
   S    # Convert it to a list of digits: [7,0,3,0]

     Λ  # Use the Canvas builtin with the three pushed arguments,
        # after which the result is implicitly output immediately afterwards

```

Unfortunately, the Canvas builtin adds trailing spaces to make it a rectangle by default, so we'll have to remove those to comply to the challenge rules:

```
   .Λ   # Use the modifiable Canvas builtin instead
„ \n    # Push the string " \n"
    ¶   # Push the builtin string "\n"
     :  # And keep repeating " \n" with "\n" until there are no longer any left
        # (after which the result is output implicitly)

```

Here a step-by-step explanation of the output for input \\$n=3\\$:

Step 1: Draw 26 characters (`"zyxwvutsrqponmlkjihgfedcba"`) in direction `7↖`:

```
a
 b
  c
   d
    e
     f
      g
       h
        i
         j
          k
           l
            m
             n
              o
               p
                q
                 r
                  s
                   t
                    u
                     v
                      w
                       x
                        y
                         z

```

Step 2: Draw 2-1 characters (`A`) in direction `0↑`:

```
A
a
 b
  c
   d
    e
     f
      g
       h
        i
         j
          k
           l
            m
             n
              o
               p
                q
                 r
                  s
                   t
                    u
                     v
                      w
                       x
                        y
                         z

```

Step 3: Draw 26-1 characters (`"BCDEFGHIJKLMNOPQRSTUVWXYZ"`) in direction `3↘`:

```
A
aB
 bC
  cD
   dE
    eF
     fG
      gH
       hI
        iJ
         jK
          kL
           lM
            mN
             nO
              oP
               pQ
                qR
                 rS
                  sT
                   tU
                    uV
                     vW
                      wX
                       xY
                        yZ
                         z

```

Step 4: Draw 2-1 characters (`"z"`) in direction `0↑`:

```
A
aB
 bC
  cD
   dE
    eF
     fG
      gH
       hI
        iJ
         jK
          kL
           lM
            mN
             nO
              oP
               pQ
                qR
                 rS
                  sT
                   tU
                    uV
                     vW
                      wX
                       xYz
                        yZ
                         z

```

Step 5: Draw 26-1 characters (`"yxwvutsrqponmlkjihgfedcba"`) in direction `7↖`:

```
a
Ab
aBc
 bCd
  cDe
   dEf
    eFg
     fGh
      gHi
       hIj
        iJk
         jKl
          kLm
           lMn
            mNo
             nOp
              oPq
               pQr
                qRs
                 rSt
                  sTu
                   tUv
                    uVw
                     vWx
                      wXy
                       xYz
                        yZ
                         z

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `ŽR‘` is `7030`.

See this 05AB1E tip of mine for an in-depth explanation of the Canvas builtin.
> 1 votes

# Answer
# Scala, 137 bytes

Golfed version. Try it online!

```
n=>(1 to 25+n).map{i=>(" "*(i-n))+((i-n to i-1).map{j=>val c=97+j-((j^i^n)%2)*32;if(j>=0&&j<26)c.toChar.toString else""}.mkString)}.toSeq

```

Ungolfed version. Try it online!

```
object Main {
  def main(args: Array[String]): Unit = {
    for(n <- List(1, 4, 26)) {
      f(n).foreach(println)
      println()
    }
  }

  def f(n: Int): List[String] = {
    (1 until 26 + n).map { i =>
      (" " * (i - n)) + ((i - n until i).map { j =>
        val c = 97 + j - ((j ^ i ^ n) % 2) * 32
        if (j >= 0 && j < 26) (c).toChar.toString else ""
      }.mkString)
    }.toList
  }
}

```
> 0 votes

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


title: Seat gangs as far as possible

text:
# Question
Title: Seat gangs as far as possible
Imagine there are \\$n\\$ people \\$\\{a\_1, a\_2, \ldots, a\_n\\}\\$ who enter a room in order and sit down in \\$n\\$ seats, arranged in a row. Each of these people belong to some gang, indicated by an integer \\$\\{1, 2, \ldots, k\\}\\$. These gangs hate the members of the other gangs, so they want to sit as far away from those people as possible; specifically, they sit in the set which maximizes the minimum distance from anyone *in a different gang* who is already seated. They break ties by sitting in the seat furthest to the left.1

For example, suppose \\$n=6\\$, and there are \\$k=3\\$ gangs \\$\\{1, 2, 3\\}\\$. Now imagine that the first person that enters is in gang 1, the next two are in gang 2, the next two are in gang 3, and the final person is in gang 1 again -- i.e. the order is `[1, 2, 2, 3, 3, 1]`. Then the people will sit down in the following order:

```
   _ _ _ _ _ _
1: 1 _ _ _ _ _
2: 1 _ _ _ _ 2
2: 1 _ _ _ 2 2
3: 1 _ 3 _ 2 2
3: 1 3 3 _ 2 2
1: 1 3 3 1 2 2

```

Your challenge is, given a sequence of numbers \\$\\{a\_1, a\_2, \ldots, a\_n\\}\\$, where each \\$a\_i \in \\{1, 2, \ldots, k\\}\\$ is some positive integer representing a person in some gang, output the final arrangement of the \\$n\\$ people in \\$n\\$ seats as described above. (If useful, you can take \\$n\\$ and \\$k\\$ as extra inputs.) You can assume that no gang number will be skipped - e.g. \\$\\{1, 2, 4\\}\\$ would not be a valid input.

### Test Cases

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

```

Standard loopholes are forbidden. As this is , shortest program wins.

1 This is a variation of the "urinal protocol".

# Answer
> 5 votes
# Uiua, 32 bytes

```
∧⋄∸(⍜⊏+⊢⍏×-1,/↧⌵∺-⇡⊃⧻⊚×⊃±≠,,)≠..

```

Try it online!

```
∧⋄∸(⍜⊏+⊢⍏×-1,/↧⌵∺-⇡⊃⧻⊚×⊃±≠,,)≠..  input: array of gang ids
∧⋄∸(  )≠..  fold over the input, using [0 ... 0] as the initial accumulator
  (   )      inner function: placed gang ids, next gang id -> placed gang ids
  ⊃±≠       sign (is occupied?), not equal (is not the current gang?)
  ×          multiply (has a person under a different gang?)
  ⇡⊃⧻⊚     all indices (all positions), indices of ones (positions of enemies)
  /↧⌵∺-     for each position, minimum distance from enemies
             (infinity if no enemies)
  ×-1,       multiply (placed gang ids - 1) to make valid distances negative
             infinity * 0 is NaN, whose sort order is after infinities
  ⊢⍏        first index of minimum (the index of maximum distance from enemies)
  ⍜⊏+  ,,   add the new gang id at the found index

```

# Answer
> 4 votes
# Python3, 218 bytes

```
def f(g):
 R=[0]*len(g)
 for i in g:
  d=[[],[]]
  for j,k in enumerate(R):
   if k!=i:d[k==0]+=[j]
  if d[0]:R[max([(j,min(abs(j-J)for J in d[0]))for j in d[1]],key=lambda x:x[1])[0]]=i
  else:R[min(d[1])]=i
 return R

```

Try it online!

# Answer
> 4 votes
# Jelly, ~~22~~ 20 bytes

```
¬,an¥T€ạṂNɗÞ/Ḣ
+ç¦ƒ¬

```

Try it online!

A pair of links which is called with a single argument of a list of integers and returns a list of integers.

## Explanation

```
¬,an¥T€ạṂNɗÞ/Ḣ  # Helper link: take a current list of seated people as the left argument and the next person to seat; returns the index of the best available seat
¬               # Not (vectorises)
 ,  ¥           # Pair with:
  an            # - The result of anding the current seating plan with the result of checking which ones don’t equal the new person
     T€         # For each of these, generate a vector of truthy indices
          ɗÞ/   # Reduce this list of lists; generate a sorted version of the first list (the indices of empty seats) sorted by the following:
       ạ        # - Absolute difference between a given index of an empty seat and the indices of all of the seats filled with rival gang members
        Ṃ       # - Minimum
         N      # - Negate
             Ḣ  # Head (I.e. the index of the best available seat)

+ç¦ƒ¬           # Main link: takes a list of people to seat and returns the seating plan
   ƒ¬           # Reduce the list of people to seat, using a list of zeros of the same length as the starting left argument and the following:
+               # - Add the new person
 ç¦             #  - Specifically just at the index given by using the helper link

```

Created with the help of Luminespire.

# Answer
> 4 votes
# , ~~94~~ 84 bytes

```
\(x,y=!x){for(z in x)y[which.max(sapply(v<-seq(y),\(w)min((w-v[y-z&y])^2))*!y)]=z;y}

```

Attempt This Online!

A function that takes an integer vector and returns an integer vector. Works similarly to my Jelly answer, but golfed differently to reflect the differences in language.

*Thanks to @pajonk for saving three bytes!*

## Ungolfed version

```
find_closest_distance <- function(seat_index, current_seats, next_person) {
 distances <- abs(seat_index - seq(current_seats)[current_seats & current_seats != next_person])
 min(distances)
}

find_best_seat_and_allocate <- function(current_seats, next_person) {
 closest_distances <- sapply(seq(current_seats), find_closest_distance, current_seats = current_seats, next_person = next_person)
 best_seat <- which.max(closest_distances * !current_seats)
 current_seats[best_seat] <- next_person
 current_seats
}

f <- function(people) {
 Reduce(find_best_seat_and_allocate, people, init = !people)
}

```

Attempt This Online!

# Answer
> 3 votes
# JavaScript (V8), 102 bytes

```
x=>x.map(c=>s[x.map((_,k)=>x.some((_,i)=>s.some((v,j)=>(i-j)**2<k*k&v!=c|i==j)?0:[A=i])),A]=c,s=[])&&s

```

Try it online!

Seems quite unpolished

pseudo-code:

```
s = []
for c in x:
  for k in range(len(x)):
    for i in range(len(x)):
      if at position i distance k:
        A = i
        break
  s[A] = c

```

# Answer
> 2 votes
# , 49 bytes

```
0"0]F..([`(0{&\:~:*[:<./@(I.|@-/i.@#)~:**@])`]})]

```

Attempt This Online!

* `0"0]F..(fold verb)` A single forward fold that we seed with a list of zeros as long as the input
* To find the new position of each person in line, we...
    + `~:**@]` First create an array which is 1 only in positions of rival gang members, and 0 elsewhere
    + `I.|@-/i.@#` Create a table of absolute differences between the indexes of those ones and all indexes
    + `<./@` And min the resulting rows of that table. This gives us a list showing the distance to the closest rival gang member at each position.
    + `~:*` Zero out any position holding one of our own gang members.
    + `0{&\:` Take the first element of the grade down. This gives us the first of all the "farthest" positions, as needed.
* `[` Update that position with the value we're folding.

# Answer
> 2 votes
# Charcoal, 41 bytes

```
Ｆθ⊞υ⁰Ｆθ«≔Ｅυ∧¬κ⌊Ｅυ⎇∧μ⁻ιμ↔⁻νλＬθη§≔υ⌕η⌈ηι»Ｉυ

```

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

```
Ｆθ⊞υ⁰

```

Create an array of empty seats of the same length as the input.

```
Ｆθ«

```

Loop over the input.

```
≔Ｅυ∧¬κ⌊Ｅυ⎇∧μ⁻ιμ↔⁻νλＬθη

```

For each seat, if it is empty, calculate the distance to the nearest rival.

```
§≔υ⌕η⌈ηι

```

Place this person in the seat furthest away from any rival.

```
»Ｉυ

```

Output the resulting seating arrangement.

# Answer
> 2 votes
# 05AB1E, 31 bytes

```
_IvÐĀUyÊX*āsƶ0KδαεIgªß}X<*Wkysǝ

```

Port of *@Bubbler*'s Uiua's answer, so make sure to upvote that answer as well!

Try it online or verify all test cases.

**Explanation:**

```
_               # Convert each value in the (implicit) input-list to 0
 Iv             # Push the input-list again, and loop over its items `y`:
   Ð            #  Triplicate the current list
    Ā           #  Pop one, and check which positions are occupied
     U          #  Pop and store this list in variable `X`
    yÊ          #  Pop another copy, and check all positions NOT filled with gang `y`
      X*        #  Multiply it to list `X`, so we have a list with 1s at enemy positions
        ā       #  Push a list in the range [1,length] (without popping)
         s      #  Swap so the earlier enemy positions list is at the top again
          ƶ     #  Multiply each value by its 1-based index
           0K   #  Remove all 0s
             δα #  Pop both lists, and create an absolute difference table
    ε    }      #  Map over this list of lists
     Igª        #   Append the input-length to the list (edge case for empty lists)
        ß       #   Pop and push the minimum
          X     #  Push list `X` again
           <    #  Subtract each value by 1 (0s for enemy positions; -1 otherwise)
            *   #  Multiply it to the values of the mapped list
    W           #  Push the minimum (without popping the list)
     k          #  Pop both, and push the (first) (0-based) index of this minimum
      ys        #  Push the current gang `y`, and swap
        ǝ       #  Insert the current gang `y` at this index into the list
                # (after the loop, the resulting list is output implicitly)

```

# Answer
> 2 votes
# Scala, 207 bytes

207 bytes, it can be golfed much more. Golfed version. Try it online!

```
(c,n)=>{val d=c.indices.map{i=>if(c(i)==0){val d=c.indices.collect{case j if c(j)!=0&&c(j)!=n=>Math.abs(i-j)};if(d.isEmpty)Int.MaxValue else d.min}else -1};c.updated(d.zipWithIndex.maxBy{case(d,_)=>d}._2,n)}

```

Ungolfed version. Try it online!

```
object Main {
  def main(args: Array[String]): Unit = {
    val inputData = List(
      List(1),
      List(1, 2),
      List(1, 1, 1),
      List(1, 2, 1, 2, 1),
      List(1, 2, 2, 3, 3, 1),
      List(1, 2, 4, 3, 2, 1, 4),
      List(4, 4, 4, 3, 3, 2, 1),
      List(1, 2, 3, 4, 5, 6, 7)
    )

    inputData.foreach { people =>
      val result = people.foldLeft(List.fill(people.size)(0)) { (currentSeats, nextPerson) =>
        findBestSeatAndAllocate(currentSeats, nextPerson)
      }
      println(s"${people.mkString(", ")} -> ${result.mkString(", ")}")
    }
  }

  def findClosestDistance(seatIndex: Int, currentSeats: List[Int], nextPerson: Int): Int = {
    val distances = currentSeats.indices.collect {
      case idx if currentSeats(idx) != 0 && currentSeats(idx) != nextPerson => Math.abs(seatIndex - idx)
    }
    if (distances.isEmpty) Int.MaxValue else distances.min
  }

  def findBestSeatAndAllocate(currentSeats: List[Int], nextPerson: Int): List[Int] = {
    val closestDistances = currentSeats.indices.map { idx =>
      if (currentSeats(idx) == 0) findClosestDistance(idx, currentSeats, nextPerson) else -1
    }
    val bestSeat = closestDistances.zipWithIndex.maxBy { case (distance, _) => distance }._2
    currentSeats.updated(bestSeat, nextPerson)
  }
}

```

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