title: Implement a bag without replacement

text:
# Question
Title: Implement a bag without replacement
## Intro

The Tetris Guidelines specify what RNG is needed for the piece selection to be called a Tetris game, called the Random Generator. Yes, that's the actual name ("Random Generator"). In essence, it acts like a bag without replacement: You can draw pieces out of the bag, but you cannot draw the same piece from the bag until the bag is refilled.

Write a full program, function, or data structure that simulates such a bag without replacement.

## Specification

Your program/function/data structure must be able to do the following:

* Represent a bag containing 7 distinct integers.
* Draw 1 piece from the bag, removing it from the pool of possible pieces. Output the drawn piece.
* Each piece drawn is picked uniformly and randomly from the pool of existing pieces.
* When the bag is empty, refill the bag.

## Other Rules

### "Bonuses"

These bonuses aren't worth anything, but imaginary internet cookies if you are able to do them in your solution.

* Your bag can hold an arbitrary `n` distinct items.
* Your bag can hold any type of piece (a generic bag).
* Your bag can draw an arbitrary `n` number of pieces at once, refilling as needed.

# Answer
# Vyxal, 5 bytes

Inspired by Kevin Cruijssen's 05AB1E answer
6 bytes without the bonus:

```
{7Þ℅⟑,

```

Try it Online!

**Explanation**

```
{7Þ℅⟑,
{         Loop forever
 7Þ℅      Random permutaton of range(7)
    ⟑,    Lazily evaluated lambda, print each item

```

Bonuses:

* 5 bytes for *Arbitrary n items*: `{Þ℅⟑,`. Implicitly takes an integer as the input.
* 5 bytes for *Generic bag*: `{Þ℅⟑,`. Implicitly takes a list as the input. Same program as above :P
* 8 bytes for *Draw n items*: `{7Þ℅?Ẏ⟑,`. Slices the list until the input before applying it to the lambda.
> 9 votes

# Answer
# , ~~50~~ 40 bytes

*-10 bytes thanks to inspiration from Giuseppe*

```
{b=n=1;\()(b<<-c(b,sample(7)))[n<<-n+1]}

```

Attempt This Online!

A reuseable function that on each call returns a single random nunber in the range `1..7`, sampled across calls using the 'tetris' distribution.
This is how I interpret the intent of the challenge.

A 62-byte recursive variant of this satisfies all 3 bonuses (try it here):

```
f={b=n=1;\(m,p)if(m)c((b<<-c(b,sample(p)))[n<<-n+1],f(m-1,p))}

```

---

# , 24 bytes

```
repeat cat(sample(7),"")

```

Attempt This Online!

Alternative: a full program that outputs an infinite sequence of random permutations of `1..7`.
This probably satisfies the letter of the challenge, and other answers have used this approach, although it does seem rather trivial.
> 8 votes

# Answer
# JavaScript (ES6), 50 bytes

A function that draws one piece at a time.

```
m=f=_=>m^(m|=1<<(i=Math.random()*7))?-~i:f(m%=127)

```

Try it online!

### Commented

```
m =               // m (aka "the bag") is a global bitmask holding
                  // drawn pieces, initialized to a zero'ish value
f = _ =>          // f is a recursive function ignoring its argument
m ^ (             // if m is modified when ...
  m |= 1 << (     //   ... the floor(i)-th bit of m is set
    i =           //   where i is uniformly chosen
    Math.random() //   in [0, 7[
    * 7           //
  )               //
) ?               // then:
  -~i             //   return floor(i + 1)
:                 // else:
  f(              //   try again
    m %= 127      //   and reset m to 0 if it's 127 (0b1111111),
  )               //   meaning that the bag is empty

```
> 8 votes

# Answer
# Raku, 23 bytes

```
{grab $||=SetHash(^7):}

```

Try it online!

Ungolfed:

```
{
  state $bag ||= SetHash(0..6);
  $bag.grab;
}

```

This is a function which, when called repeatedly, will return the integers 0-6 in a random order, then the same integers in a (likely) different random order, and so on, *ad infinitum*.

Raku has a built-in data type `SetHash` which stores a set of objects, and has a `grab` method that chooses one of them randomly, removes it from the set, and returns it. All that's left to do for this challenge is the refilling. A state variable (`$` in the golfed version, `$bag` in the ungolfed one) stores the `SetHash`, which is reset to a new object with full contents (using `||`) when the variable is undefined, as on the first call to the function, or has become empty, as after every seventh call.
> 7 votes

# Answer
# 05AB1E, 9 bytes

```
[7L.r)˜ć,

```

Uses a bag with integers `[1,2,3,4,5,6,7]`. Outputs the random piece indefinitely on separated newlines.

Try it online.

1. (9 bytes) Replace `7` with `I` for the first bonus, where `n` is given as input-integer: try it online.
2. (8 bytes) Replace `7L` with `I` for the second bonus, where the bag is given as input-list: try it online.
3. (11 bytes) Add  after `˜` for the third bonus, where `n` is given as input-integer and it'll output those `n` items as a list each iteration: try it online. Will use a combination of the existing list and a new shuffled list if the bag doesn't hold enough items anymore (e.g. let's say \\$n=3\\$ and the first two iterations where `[4,2,5]` and `[1,7,3]`, then the third iteration will be `[6,a,b]`, where the `6` is from the existing bag, and `a,b` are two random integers from a new bag).

**Explanation:**

```
[          # Loop indefinitely:
 7L        #  Push a list in the range [1,7]
   .r      #  Randomly shuffle it
     )     #  Wrap the entire stack into a list
      ˜    #  Flatten it to a single list
       ć   #  Extract head; pop and push remainder-list and first item separately
        ,  #  Pop and output this first item

```
> 6 votes

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

```
f=_=>x.match(i=Math.random()*7|0)?f(x=x[6]?'':x):(x+=i,i);x=''

```

Try it online!

I hope I understood question correctly
> 5 votes

# Answer
# Excel (ms365), 121 bytes

Formula in `A1`:

```
=LET(p,7,n,8,DROP(TAKE(REDUCE(0,SEQUENCE(ROUNDUP(n/p,0)),LAMBDA(a,b,VSTACK(a,SORTBY(SEQUENCE(p),RANDARRAY(p))))),n+1),1))

```

Idea here is that:

* 'p' - Represents the amount of distinct items in our bag;
* 'n' - Represents the amount of tokens we take out of the bag at once (with refilling it offcourse). You may change this to any reasonable integer;
* 'SEQUENCE(p)' - Represents our array. In this specific case we create an array of integers, but `SORTBY()` can take any array of any type. This however will start changing byte-count!

Below another sample where 'n' == 14 and another one where 'n' == 14 and 'p' == 3:
> 5 votes

# Answer
# Jelly, ~~6~~ 5 bytes

```
ẊÐḶFY

```

Implements the first bonus

Runs until a pattern is repeated

-1 byte thanks to Jonathan Allan!

How?

```
ẊÐḶFY  : Main Link, One arg(Number of pieces)
Ẋ      : Shuffle; return a random permutation
 ÐḶ    : Loop; Repeat until the results are no longer unique
   F   : Flatten list
    Y  : Join z, separating by linefeeds

```

Attempt This Online!
> 5 votes

# Answer
# Go, 182 bytes

```
import(."math/rand";."golang.org/x/exp/slices")
func f()func()int{b:=[]int{}
return func()int{n:=Intn(7)
for;Contains(b,n);n=Intn(7){}
b=append(b,n)
if len(b)>6{b=[]int{}}
return n}}

```

Attempt This Online!

A generator function that returns a function. When the returned function is called, it returns an int in the range `[0,7)`.

### "Bonuses"

#### Arbitrary `n` distinct items, 204 bytes

```
import(."math/rand";."golang.org/x/exp/slices")
func f(I[]int)func()int{b,l:=[]int{},len(I)
return func()int{e:=I[Intn(l)]
for;Contains(b,e);e=I[Intn(l)]{}
b=append(b,e)
if len(b)>=l{b=[]int{}}
return e}}

```

Attempt This Online!

Generator function now takes a list of elements to choose from.

#### Arbitrary `n` items + generic (`comparable`), 208 bytes

```
import(."math/rand";."golang.org/x/exp/slices")
func f[T comparable](I[]T)func()T{b,l:=[]T{},len(I)
return func()T{e:=I[Intn(l)]
for;Contains(b,e);e=I[Intn(l)]{}
b=append(b,e)
if len(b)>=l{b=[]T{}}
return e}}

```

Attempt This Online!

Works for any `comparable` type (bool, int, float, string, pointer, channel, struct of comparables, array of comparables, typeset of comparable).

#### Arbitrary `n` items + generic (`comparable`) + `k` items at a time, 288 bytes

```
import(."math/rand";."golang.org/x/exp/slices")
func f[T comparable](I[]T)(func()T,func(int)[]T){b,l:=[]T{},len(I)
A:=func()T{e:=I[Intn(l)]
for;Contains(b,e);e=I[Intn(l)]{}
b=append(b,e)
if len(b)>=l{b=[]T{}}
return e}
return A,func(n int)(N[]T){for i:=0;i<n;i++{N=append(N,A())};return}}

```

Attempt This Online!

A function that returns 2 functions. The first function takes 1 item, the second function takes `k` items.
> 4 votes

# Answer
# Factor, ~~63~~ 62 bytes

```
[ 0 get [ 7 iota 7 sample >vector dup 0 set ] when-empty pop ]

```

Try it online!

A quotation (anonymous function) that takes no arguments and outputs one piece each time it is called. You can look in the bag in between function calls with `0 get`.
> 4 votes

# Answer
# Pip, ~~11~~ 8 bytes

```
LhP*SH,a

```

Implements the first bonus

-3 bytes thanks to DLosc!

How?

```
LhP*SH,a  : One arg(Number of items)
       a  : First arg
L         : Loop x times;
 h        : Literal for 100
      ,   : Range zero to a
    SH    : Shuffle: random permutation of iterable
   *      : Map
  P       : Print

```

Try It Online!
> 3 votes

# Answer
# Jelly, (4) 5 bytes

```
7ẊṄ€ß

```

A full program that prints forever.

**Try it online!**

\\$4\\$ bytes - `ẊṄ€ß` \- taking either an arbitrary alphabet size TIO or an arbitrary alphabet (as a list) TIO.

### How?

```
7ẊṄ€ß - Main Link: no arguments
7     - seven
 Ẋ    - (implicit range [1..7]) shuffle
   €  - for each:
  Ṅ   -   print with trailing newline
    ß - call this link again with the same arity

```
> 3 votes

# Answer
# Pip, 11 bytes

```
{l|:SHaPOl}

```

This is a function that takes as an argument a list of possible piece values (implementing the first two bonuses) and returns a single piece each time it is called.

Attempt This Online!

### Explanation

We store the current state of the bag in the global variable `l`. Initially, `l` is `[]`.

```
{l|:SHaPOl}
{         }  Define a function:
 l|:          If l is empty, set it to
    SHa       the function argument, randomly shuffled
       POl    Pop the first element from l and return it

```
> 3 votes

# Answer
# PHP, 79 bytes

```
$y=function()use(&$a){$a=$a!=[]?$a:range(0,6);shuffle($a);echo array_pop($a);};

```

Try it online!

### Commented

```
$y = function() use (&$a) {   // anonymous function with use clause by-reference
    $a = $a != []             // equal comparison, if $a is neither null nor empty array
        ? $a                  // then use $a
        : range(0,6);         // else create range array
    shuffle($a);              // shuffle array
    echo array_pop($a);       // splice off and return last element of $a
};

```
> 3 votes

# Answer
# Zsh, 35 bytes

```
exec<<(while shuf -i1-7)
f()read -e

```

Attempt This Online!

Uniquely for zsh, this is a function `f`, not a full program.

If you want to cheat and output infinitely, you only need the `while shuf -i1-7`.

Setup:

* `while shuf -i1-7`: repeatedly output the shuffled range 1 to 7
* `<()`: create a pipe from the output of that loop
* `exec<`: move that pipe to standard input

`f`:

* `read`: read one word from standard input
* `-e`: and print it
> 2 votes

# Answer
# Python 3, 59 bytes

-6 bytes thanks to @att

```
from random import*
while[*map(print,sample(range(7),7))]:1

```

Try it online!

Infinitely prints integers.

I dont know if this is valid: (54 bytes)
Prints all 7 integers of permutation in one line before a newline.

```
from random import*
while 1:print(*sample(range(7),7))

```

Try it online!
> 2 votes

# Answer
# Haskell, 149 bytes

```
import System.IO.Unsafe
import System.Random
import Data.List
d(o,[])=d([],o)
d(o,p)=(\n->(n:o,p\\[n]))$(p!!)$unsafePerformIO$randomRIO(0,length p-1)

```

Try it online!
> 1 votes

# Answer
# Clojure, 56 bytes

```
(run! #(run! println %)(repeatedly #(shuffle(range 7))))

```

Creates an infinite list containing random permutations of 0 to 6 and prints each number.

Try it online!
> 1 votes

# Answer
# Brachylog, 7 bytes

```
7>ℕ≜₁|↰

```

Try it online!

This is a predicates that unifies its output with a random integer between 0 and 6, exhausting each possibility before beginning a new cycle.

Try generating 14 random unifications here!

You can change `7` to any other number to get bigger bags.

### Explanation

```
7>ℕ        Take an unknown integer between 0 and 6
    ≜₁     Assign a value to it, with a random choice
      |    Else
       ↰   Recursive call

```

Since our variable is constrained in `[0..6]`, `≜₁` will randomly unify it with one of those 7 values, leaving a choice point for each one. Brachylog will try each choice point when asked (e.g. with `ᶠ - findall`, failure loops, or by pressing `;` in Prolog’s REPL), so each integer value. `|` creates another choice point that will get called only once all the choice points created by `≜₁` are exhausted.
> 1 votes

# Answer
# Thunno, \\$ 11 \log\_{256}(96) \approx \\$ 9.05 bytes

```
[7R7zPZw{ZK

```

Attempt This Online!

Port of mathcat's Vyxal answer.

#### Explanation

```
[7R7zPZw{ZK
[            # Forever:
         ZK  #   Print
        {    #   Each element of
      Zw     #   A random element of
   7zP       #   The permutations
 7R          #   Of range(7)

```

#### Bonuses

* Arbitrary `n` items: \\$ 13 \log\_{256}(96) \approx \\$ 10.70 bytes, `[z0Rz0zPZw{ZK`
* Generic bag: \\$ 12 \log\_{256}(96) \approx \\$ 9.88 bytes, `[z0DLzPZw{ZK`
> 1 votes

# Answer
# C (gcc), 60 bytes

```
b;f(i,j){b-127||(b=0);for(;b&1<<(i=rand()%7););b|=1<<i;j=i;}

```

Try it online!

## Explanation

```
b; // Bag: initialized with nothing selected
f(i,j){
  b-127||(b=0); // Reset bag when all 7 pieces selected
  for(;b&1<<(i=rand()%7);); // Find a random unselected piece
  b|=1<<i; // Mark it as selected
  j=i; // Return the piece
}

```
> 0 votes

---
Tags: code-golf, random, data-structures
---


title: Painting with Line Filler

text:
# Question
Title: Painting with Line Filler
Given a matrix of positive integers, output whether it's possible to generate it by starting with an empty1 matrix of the same dimensions and repeatedly filling a whole row or a whole column with the same value, overwriting any values already written.

### Example

The following matrix:

$$\begin{pmatrix}1&1&1\\2&3&4\\2&3&4\end{pmatrix}$$

Can be obtained with the following steps:

$$ \begin{pmatrix}2&0&0\\2&0&0\\2&0&0\end{pmatrix}\rightarrow \begin{pmatrix}2&3&0\\2&3&0\\2&3&0\end{pmatrix}\rightarrow \begin{pmatrix}2&3&4\\2&3&4\\2&3&4\end{pmatrix}\rightarrow \begin{pmatrix}1&1&1\\2&3&4\\2&3&4\end{pmatrix} $$

### Test cases

```
[[1,1,1,1,1],
 [2,3,4,5,6],
 [2,3,4,5,6]] => true

[[1,1,1,1,1],
 [2,3,4,1,6],
 [2,3,4,1,6]] => true

[[1,1,1,1,6],
 [2,3,4,1,6],
 [2,3,4,1,6]] => true

[[1,1],
 [1,1]] => true

[[1,2],
 [2,1]] => false

[[1,2],
 [3,4]] => false

[[1,1,2],
 [4,5,2],
 [4,3,3]] => false

[[1,2,4],
 [2,1,4],
 [3,3,3]] => false

```

Shortest code in each languages win.

1 You can assume it is initially filled with zeros

# Answer
> 6 votes
# Haskell + hgl, 21 bytes

```
ø<<yyc$jn m$tx<fn lq

```

Attempt This Online!

## Explanation

The algorithm employed here repeatedly removes all rows of equal elements, removes all columns of equal elements, until we reach a fixed point where additional operations stop changing things.

If that fixed point is the empty list we return `True` otherwise `False`.

* `lq` determines if all elements of a list are equal.
* `fn lq` takes a list of lists and filters out all rows of equal elements.
* `tx` transposes a list.
* `jn m` takes a function and composes it with itself.
* `jn m$tx<fn lq` takes a list of lists removes all constant rows, transposes it to remove all constant columns and transposes back.
* `yyc` repeats an operation until it reaches a fixed point
* `ø` determines if a list is empty

## Alternate version, 21 bytes

```
ø<<yyc$tx<fn lq<.<tx

```

## Reflection

It's really nice to see `yyc` paying off already. The weak point in this answer is really with the glue. We have all the right components, but we waste a couple bytes putting it together.

* `jn` could use an infix. We already have `fjn`, so I don't know why there isn't an infix. Even if it's 3 bytes it would save here if it had the right precedence.
* `jn m` is a really expensive way to compose a function with itself. This should be a built in operator, probably 2 bytes long. It would save 2 bytes here.
* The composition operator we really want is something like `f<|<g=f<g<f<g`, which alternates two functions back and forth. We have the similar "sandwich compose" `<.<` which is useful in the alternate answer, but this other operator is probably worth having. With this we would save 3 bytes.
* It might be worth having a stronger version of `yyc` which stops when there is any repeated value. With this we could do away with the whole double compose and just write `ø<<yyC$tx<fn lq`.
* We have column map with `mC` it might be worthwhile implementing a column filter.
* `tx` could be an `Iso`.

# Answer
> 5 votes
# Nibbles, 6.5 bytes (13 nibbles)

```
/\`.$|`'$>>=~

```

Returns truthy (nonempty list) if the matrix cannot be 'painted with lines', falsy (empty list) if it can.

```
/\`.$|`'$>>=~
  `.            # iterate while unique
    $           # (starting with input):
     |          #   filter
      `'        #   the transpose of
        $       #   the result so far
           =~   #     by groups of its identical elements
         >>     #     without the first group
                #     (so: all elements equal => empty list = falsy
                #          different elements => nonempty list = truthy)
 \              # reverse the list of results
/               # and return the first element
                # (which will be an empty list if the matrix
                # can be 'painted with lines', or nonempty list
                # if it cannot).

```

# Answer
> 4 votes
# Python \+ NumPy, 64 bytes

```
f=lambda A,c=2:f(A[x].T,c-all(x))if c*any(x:=A.ptp(1)>0)else c>0

```

Attempt This Online!

As @TheThonnu points out per meta consensus (thanks @pxeger for sharing the exact link in the comments) this can be **62 bytes**: simply drop the last two characters.

# Answer
> 4 votes
# Rust, ~~436~~ 280 bytes

```
|a:&[&[u8]]|f(&|c,d|a[c][d],a.len(),a[0].len());fn f(a:&dyn Fn(usize,usize)->u8,b:usize,c:usize)->bool{b<1||c<1||h(a,b,c)||h(&|e,f|a(f,e),c,b)}fn h(a:&dyn Fn(usize,usize)->u8,b:usize,c:usize)->bool{(0..b).any(|x|(0..c).all(|y|a(x,y)==a(x,0))&&f(&|d,e|a(d-(d>x)as usize,e),b-1,c))}

```

Attempt This Online!

## Explanation

The basic idea is we check if there is at least one row or column with all elements the same, then recurse over the remaining rows and columns.

Since transposing and editing arrays is a bit tricky in rust instead we pass callback functions that can represent transformations on the original matrix.

```
// This function wraps the main program, converting our array into a function that will return the array position from a coordinate postion
let g = |a: &[&[u8]]| f(&|c, d| a[c][d], a.len(), a[0].len());
// f performs the transposition. Returns true if the array is empty, or if h(a), or h(a) transposed. b and c are the size of the array.
fn f(a: &dyn Fn(usize, usize) -> u8, b: usize, c: usize) -> bool {
    b < 1 || c < 1 || h(a, b, c) || h(&|e, f| a(f, e), c, b)
}
// h is the core of the function. Check if there is at least one row that is all equal and that f(the remaining matrix)
fn h(a: &dyn Fn(usize, usize) -> u8, b: usize, c: usize) -> bool {
    (0..b).any(|x| {
    (0..c).all(|y| a(x, y) == a(x, 0)) && f(&|d, e| a(d - (d > x) as usize, e), b - 1, c)
})

```

# Answer
> 4 votes
# , 71 bytes

```
f=\(m,n=o,o=sum(m|1))`if`(n,f(t(m[,apply(m,2,\(l)any(l-l[1]))]),n-1),o)

```

Attempt This Online!

Returns truthy (nonzero value) if the matrix cannot be 'painted with lines', falsy (zero) if it can.

Performs n (=number of elements of matrix) iterations of removing all-the-same columns and transposing, and outputs the number of elements remaining at the end.
Since at least one row or column of a paintable-with-lines matrix must be all-the-same at the start, this number of iterations is always enough to check paintability.

# Answer
> 3 votes
# Vyxal, 7 bytes

```
≬~≈F∩İ÷

```

Try it Online!

*-1 byte: changed output method (thanks to @emanresuA)*

Outputs an empty list if it's possible or a non-empty list if not.

```
≬        # three element lambda:
 ~≈      #   filter by: are all elements equal
   F     #   remove elements of a that are in b
    ∩    #   transpose
     İ   # apply function while results are unique, collecting results
      ÷  # push each item to stack

```

# Answer
> 3 votes
# Jelly, 7 bytes

```
EÐḟZ$ÐL

```

A monadic Link that accepts a matrix and yields an empty list if possible (falsey) or a non-empty list if not (truthy).

**Try it online!**

### How?

```
EÐḟZ$ÐL - Link: matrix, M
     ÐL - loop while distinct, applying:
    $   -   last two links as a monad - f(current):
 Ðḟ     -     filter discard those for which:
E       -       all equal?
   Z    -     transpose

```

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

```
f(a)=g(a)||g(a~)
g(a,i)=!a||[#Set(c)<=f(a[,^i++])|c<-a]

```

Attempt This Online!

---

# PARI/GP, 59 bytes

```
f(a)=if(a!=b=g(g(a)),f(b),!a)
g(a)=Mat([c|c<-a~,#Set(c)>1])

```

Attempt This Online!

# Answer
> 2 votes
# Haskell, 94 bytes

```
e=[]:e
s(a:b)=all(==a)b
g m=m==[]||any s m&&p(filter(not.s)m)
p m=g m||g(foldr(zipWith(:))e m)

```

Try it online!

# Haskell, 98 bytes

```
import Data.List
s=(<2).length.nub
g m=all s m||any s m&&p(filter(not.s)m)
p m=g m||g(transpose m)

```

Try it online!

# Answer
> 2 votes
# JavaScript (Node.js), ~~89~~ 84 bytes

```
f=m=>m<(m=m.map(u=x=>x.map((y,j)=>x.some(v=>v-y)&m.some(v=>v[j]-y)?u=y:f)))?f(m):u>f

```

Try it online!

Notice that only change is (number) =\> `m=>m<m.ma...`, so the first change makes string larger

# Answer
> 2 votes
# 05AB1E, 10 (or 7) bytes

```
Δ2FøʒË≠]˜P

```

Outputs a 05AB1E truthy/falsey result (`1` if truthy; any other positive integer if falsey).

Try it online or verify all test cases.

Could be 7 bytes by outputting an empty list for truthy and non-empty matrix for falsey, even though both are considered falsey in terms of 05AB1E booleans, by removing the final three bytes:

```
Δ2FøʒË≠

```

Try it online or verify all test cases.

**Explanation:**

```
Δ        # Loop until the result no longer changes:
 2F      #  Inner loop 2 times:
   ø     #   Zip/transpose the matrix; swapping rows/columns
         #   (which will use the implicit input-matrix in the very first iteration)
    ʒ    #   Filter this matrix of rows by:
     Ë≠  #    Check that all values in the row-list are NOT equal
]        # Close the filter, loop, and changes-loop
 ˜       # Flatten the remaining list
  P      # Take the product (1 for an empty list; or a positive integer if not empty†)
         # (after which the result is output implicitly)

```

† Note that the matrix can never contain just `1`s at this point, since it would have been reduced further.

# Answer
> 1 votes
# Charcoal, 38 bytes

```
⊞υθＦυＦ²«≔Ｅ⌊ιＥι§νμι≔Φι⁻⌈λ⌊λκ¿⁻ικ¿κ⊞υκＰ¹

```

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

```
⊞υθＦυ

```

Start a breadth-first search with the original array.

```
Ｆ²«

```

Loop over the transpose as well as the array.

```
≔Ｅ⌊ιＥι§νμι

```

Transpose the array.

```
≔Φι⁻⌈λ⌊λκ

```

Remove rows of identical elements.

```
¿⁻ικ

```

If this results in a smaller array, then:

```
¿κ⊞υκ

```

If this array is not empty then add it to the list of arrays to search.

```
Ｐ¹

```

But if it is empty then output that it can be painted.

# Answer
> 1 votes
# JavaScript (ES6),  ~~112~~  95 bytes

Returns a Boolean value.

```
f=m=>m+''==(m=(g=a=>a.filter((v,x)=>new Set(v.at?v:m.map(r=>r[x])).size>1))(m.map(g)))?m<1:f(m)

```

Attempt This Online!

### Commented

```
f = m =>               // f is a recursive function taking the input matrix m[]
m + '' == (            // compare the current version of m[] with ...
  m = (                // ... the updated one
    g = a =>           // g is a helper function taking an array a[]:
    a.filter((v, x) => //   for each entry v at position x in a[]:
      new Set(         //     turn into a set:
        v.at ?         //       if v is an array:
          v            //         use v directly
        :              //       else:
          m.map(r =>   //         extract the x-th column from m[]
            r[x]       //
          )            //
      ).size > 1       //     remove if there's less than 2 distinct values
    )                  //   end of filter()
  )(m.map(g))          // invoke g on each row of m[] and then on the result
) ?                    // if m[] was not updated:
  m < 1                //   return true if m[] is empty, false otherwise
:                      // else:
  f(m)                 //   try to remove more rows or columns

```

# Answer
> 1 votes
# Factor \+ `combinators.extras`, 62 bytes

```
[ [ [ [ all-eq? ] reject flip ] twice ] to-fixed-point { } = ]

```

Attempt This Online!

* `[ ... ] to-fixed-point` Call `[ ... ]` on the input until it stops changing
* `[ ... ] twice` Call `[ ... ]` twice
* `[ all-eq? ] reject` Remove the rows with numbers that are all equal
* `flip` Transpose
* `{ } =` Is it empty?

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


title: Enumerate an array, grouping duplicates

text:
# Question
Title: Enumerate an array, grouping duplicates
The objective of this challenge is to take an array of positive integers, and enumerate its indices, grouping like elements.

An enumeration without any duplicates is done by just outputting an array of pairs `(value, index)`, for example, `[3, 4, 13, 9, 2]` =\> `[[3,1],[4,2],[13,3],[9,4],[2,5]]`.

However, if a given element appears a second time, it isn't given its own pair, but is instead added to the group of its first occurrence. If in our above example we replaced the 9 with 3, then in the output we would remove `[9,4]` and replace `[3,1]` with `[3,1,4]`.

In the output, groups must be ordered by their first occurrence, and indices must be in ascending order. The element must be first in a group, before its indices. Output may be 0 or 1 indexed. You may assume the array has at least one element.

Test cases:

```
Input           | Output (One-indexed)
[3, 2, 2, 3]    | [[3, 1, 4], [2, 2, 3]]
[17]            | [[17, 1]]
[1, 1]          | [[1, 1, 2]]
[1, 1, 2]       | [[1, 1, 2], [2, 3]]
[1, 2, 3, 4]    | [[1, 1], [2, 2], [3, 3], [4, 4]]
[1, 1, 1, 1]    | [[1, 1, 2, 3, 4]]

```

This is , fewest bytes wins!

# Answer
> 10 votes
# Dyalog APL, 5 bytes

```
(⊂,)⌸

```

Try it online!

`,⌸` for 2 bytes *almost* works, but has trailing zeroes :/

# Answer
> 7 votes
# , 12 bytes

```
~.,&.><@I.@=

```

Zero-indexed.

Try it online!

If you can remove all of the work I'm doing with boxes, you can probably reduce the bytecount by quite a bit. I'm going to see if I can figure that out.

# Explanation

This is probably too early to be explaining (there ought to be more golfs).

```
~. ,&.> <@I.@=
             =  Self-classify (comparison of each unique element to array)
            @   Composed with
          I.    Indices of ones (where it's equal)
         @      Composed with
        <       Boxed (how we deal with arrays of unequal length)
   ,&.>         Joined with
      >          Unbox each
   ,             Concatenate
    &.           Box again
~.              Unique elements

```

# Answer
> 5 votes
# 05AB1E, 10 bytes

```
ÙεDIQƶ0K)˜

```

Try it online!

**Explanation**

```
Ù             # remove duplicates
 ε            # apply to each element
  D           # duplicate
   IQ         # compare for equality with input
     ƶ        # multiply each element by its index (1-based)
      0K      # remove zeroes
        )˜    # wrap in a flattened list

```

# Answer
> 5 votes
# Python 3, ~~83~~ 82 bytes

<sup>-1 byte thanks to Mego</sup>

```
lambda x:[[n]+[j for j,m in enumerate(x)if m==n]for n in sorted({*x},key=x.index)]

```

Try it online!

# Answer
> 5 votes
# Haskell, 48 bytes

```
import Data.List
f l=nub[k:elemIndices k l|k<-l]

```

Try it online!

# Answer
> 5 votes
# Attache, 15 bytes

```
Flat=>Positions

```

Try it online!

This is an interesting case of `=>`, the operator form of `Map`. When given two functional arguments `f` and `g`, `Map` returns a function `f => g[x]` over `x`. That is, the RHS is applied to the input, then the LHS is mapped.

The builtin `Positions` generates an array representing the grouping of entries by indices. By default, when not supplied with a second argument, `Positions` will use the first argument. `Flat` is then mapped over each item, as that is what the question requires.

## Alternative solutions

**31 bytes**

```
MapArgs[Concat#~Indices,Unique]

```

Try it online!

A pretty short, builtin-less alternative. `MapArgs` is a function like `Map`, except you can feed extra arguments into it. For example, `MapArgs[{_1 + _2}, 1..3, 3]` is `[4, 5, 6]`. Like `Map`, it becomes curried when supplied with two functional arguments. The function be mapped is `Concat#~Indices`, which is a fork. This fork is applied to the `Unique` items of the input and the input itself. This translates to `Concat[_, Indices[_2, _]]` (with the arguments of `Indices` swapped through `~`), which pairs the element being mapped (`_`) with the indices of said element `_` in the input array, which is `_2` (as ffed through `MapArgs`).

**43 bytes**

```
{Flat=>Zip[Unique[_],Indices[_,Unique[_]]]}

```

Try it online!

This is really just a more verbose (yet a tad more readable) combination of solutions #1 and #2.

# Answer
> 4 votes
# Jelly, 6 bytes

```
Q;"ĠṢ$

```

Try it online!

Explanation:

```
Q;"ĠṢ$
Q      Keep the first occurrence of each element
     $ Last two links as a monad
   Ġ    Group indices of equal elements, then sort the resulting list of groups by the element they point to
    Ṣ   Sort; used to re-order the list of groups based on first occurrence instead
  "    Vectorize link between two arguments (the first occurrences and the group list)
 ;      Concatenate

```

# Answer
> 4 votes
# Pyth, 7 bytes

0-indexed.

```
{+VQxRQ

```

Try it here! Alternative.

### How?

```
{+VQxRQ – Full program.

     RQ – For each element...
    x   – Get all its indices.
 +V     – And apply vectorised concatenation.
   Q    – With the input.
{       – Deduplicate.

```

# Answer
> 4 votes
# K (oK), 10 bytes

**Solution:**

```
(!x),'.x:=

```

Try it online!

**Examples:**

```
(!x),'.x:=,17
,17 0
(!x),'.x:=1 1
,1 1 2
(!x),'.x:=1 0 1
(1 1 2
2 3)
(!x),'.x:=1 2 3 4
(1 0
2 1
3 2
4 3)

```

**Explanation:**

Evaluation is performed right-to-left. I still think this is golf-able further...

```
(!x),'.x:= / the solution
         = / group input into dictionary, item!indices
       x:  / save as variable x
      .    / value of x (the indices)
    ,'     / concatenate (,) each-both (') with
(  )       / do this together
 !x        / the key of x (i.e. the items)

```

**Notes:**

* **14 bytes** without declaring `x`, `(,/)'+(!;.)@'=`, gave up with this approach...

# Answer
> 4 votes
# MATL, 8 bytes

```
u"@tG=fh

```

Try it at MATL Online

**Explanation**

```
        # Implicitly get the input
u       # Compute the unique values
"       # For each unique value, N
  @     # Push the value N to the stack
  t     # Duplicate N
  G     # Grab the input
  =f    # Get the 1-based indices of the elements that equal N
  h     # Horizontally concatenate N with the indices
        # Implicitly display the result

```

# Answer
> 3 votes
# Actually, 24 bytes

```
;;╗⌠╝╜r⌠╜E╛=⌡░⌡M@Z⌠♂i⌡M╔

```

Try it online!

Explanation:

```
;;╗⌠╝╜r⌠╜E╛=⌡░⌡M@Z⌠♂i⌡M╔
;;                        make two copies of input
  ╗                       save a copy to register 0
   ⌠╝╜r⌠╜E╛=⌡░⌡M          map over input:
    ╝                       save the element in register 1
     ╜r                     indices for input
       ⌠╜E╛=⌡░              filter:
        ╜E                    element in input at index
          ╛=                  equals element for outer map (from register 1)
                @Z        swap, zip input with map result
                  ⌠♂i⌡M   flatten each element in zipped list
                       ╔  uniquify

```

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

Saved a byte thanks to Martin Ender.

```
KeyValueMap[{#,##&@@#2}&]@*PositionIndex

```

Try it online!

# Answer
> 3 votes
# Julia 0.6, 37 bytes

Thanks to Pavel for 1 byte off.

```
y->[[x;findin(y,[x])]for x=unique(y)]

```

Try it online!

# Answer
> 3 votes
# , 56 bytes

```
function(x)lapply(unique(x),function(y)c(y,which(x==y)))

```

Try it online!

---

This is my first attempt at codegolf, so any feedback is welcome!

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

0 indexed

```
a=>a.map((v,i)=>a[-v]?a[-v].push(i):a[-v]=[v,i]).filter(x=>x[0])

```

Note, this assume input numbers being positive, so v \> 0

**Test** slightly modified (1 indexed) to match the test cases

```
var F=
a=>a.map((v,i)=>a[-v]?a[-v].push(i+1):a[-v]=[v,i+1]).filter(x=>x[0])

test = [ // output 1 indexed
  [3, 2, 2, 3],//    | [[3, 1, 4], [2, 2, 3]]
  [17], //           | [[17, 1]]
  [1, 1], //         | [[1, 1, 2]]
  [1, 1, 2], //      | [[1, 1, 2], [2, 3]]
  [1, 2, 3, 4], //   | [[1, 1], [2, 2], [3, 3], [4, 4]]
  [1, 1, 1, 1] //    | [[1, 1, 2, 3, 4]]
]

test.forEach(t => {
  x = F(t)
  console.log(JSON.stringify(t)+ ' -> ' + JSON.stringify(x))
})
```

# Answer
> 3 votes
# APL NARS, 24 bytes, 12 chars

```
{∪⍵,¨⍸¨⍵=⊂⍵}

```

-4 bytes thanks to Adam test:

```
  f←{∪⍵,¨⍸¨⍵=⊂⍵}

  ⎕fmt f 3 2 2 3
┌2────────────────┐
│┌3─────┐ ┌3─────┐│
││ 3 1 4│ │ 2 2 3││
│└~─────┘ └~─────┘2
└∊────────────────┘
  ⎕fmt f 17
┌1──────┐
│┌2────┐│
││ 17 1││
│└~────┘2
└∊──────┘
  ⎕fmt f 1 1
┌1───────┐
│┌3─────┐│
││ 1 1 2││
│└~─────┘2
└∊───────┘
  ⎕fmt f 1 2 3 4
┌4──────────────────────────┐
│┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐│
││ 1 1│ │ 2 2│ │ 3 3│ │ 4 4││
│└~───┘ └~───┘ └~───┘ └~───┘2
└∊──────────────────────────┘
  ⎕fmt f 1 1 1 1
┌1───────────┐
│┌5─────────┐│
││ 1 1 2 3 4││
│└~─────────┘2
└∊───────────┘

```

# Answer
> 3 votes
# SWI-Prolog, ~~165~~ 117 bytes

*-48 bytes thanks to Prolog golfing tips.*

```
h(I):-I+[]-1.
[H|T]+R-N:-(select([H|A],R,[H|L],S),!,append(A,[N],L);append(R,[[H,N]],S)),O is N+1,(T+S-O,!;write(S)).

```

Try it online!

## Explanation

```
% The predicate that prints the grouped duplicates. It's a wrapper because we
% need some extra arguments to keep state:
enumerate_duplicates(Input) :- enumerate(Input, [], 1).

% In the golfed code, operators are used to represent this predicate.
% See https://codegolf.stackexchange.com/a/153160
% Go through the input, build up the result on the way and print it.
enumerate([Head|Tail], Result, Index) :-
    (
        % If our current Result already contains a list that starts with the
        % current first element in our input, Head, NewIndexes will become the
        % new "tail" of that list in our next result list:
        select([Head|OldIndexes], Result, [Head|NewIndexes], NextResult),
        % Don't backtrack before this if goals below this fail:
        !,
        % The as-yet-unknown NewIndexes above should in fact be the same as
        % OldIndexes with our current Index appended:
        append(OldIndexes, [Index], NewIndexes)
    % Use ; instead of separate predicate rules.
    % See https://codegolf.stackexchange.com/a/67032
    ;
        % If our current Result did not already contain Head, append a new list
        % for it with the current index:
        append(Result, [[Head, Index]], NextResult)
    ),
    % Increment our index counter:
    NextIndex is Index + 1,
    (
        % And continue with the rest of our input:
        enumerate(Tail, NextResult, NextIndex),
        % Don't backtrack if the above succeeded:
        !
    ;
        % If Tail is no longer a multi-element list, we're done. Print:
        write(NextResult)
    ).

```

# Answer
> 2 votes
# Japt, ~~14~~ 9 bytes

0-indexed.

```
â £ð¶X iX

```

Try it

```
â £ð¶X iX
â             :Deduplicate
  £           :Map each X
   ð          :  Get 0-based indices of elements in the input
    ¶X        :    That are equal to X
       iX     :  Prepend X

```

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

0-indexed.

```
a=>a.map(p=(x,i)=>1/p[x]?b[p[x]].push(i):b.push([x,p[x]=i]),b=[])&&b

```

### Test cases

```
let f =

a=>a.map(p=(x,i)=>1/p[x]?b[p[x]].push(i):b.push([x,p[x]=i]),b=[])&&b

console.log(JSON.stringify(f([3, 4, 13, 9, 2]))) // [[3,0],[4,1],[13,2],[9,3],[2,4]]
console.log(JSON.stringify(f([3, 4, 13, 3, 2]))) // [[3,0,3],[4,1],[13,2],[2,4]]
console.log(JSON.stringify(f([3, 2, 2, 3]    ))) // [[3,0,3],[2,1,2]]
console.log(JSON.stringify(f([17]            ))) // [[17,0]]
console.log(JSON.stringify(f([1, 1]          ))) // [[1,0,1]]
console.log(JSON.stringify(f([1, 1, 2]       ))) // [[1,0,1],[2,2]]
console.log(JSON.stringify(f([1, 2, 3, 4]    ))) // [[1,0],[2,1],[3,2],[4,3]]
console.log(JSON.stringify(f([1, 1, 1, 1]    ))) // [[1,0,1,2,3]]
```

# Answer
> 2 votes
# PHP 4.1, 88 bytes

Yeah, it is pretty long.

This assumes a **default** `php.ini` file (`short_open_tag = On` and `register_globals = On`).

```
<?foreach($A as$k=>$v){!$b[$v]&&$b[$v]=array($v);$b[$v][]=$k;}print_r(array_values($b));

```

This presents the array in an human-readable way.
The values can be passed by POST, GET and COOKIE, inside the key "A".

---

For a modern version, one can use (90 bytes):

```
<?foreach($_GET[A]as$k=>$v){if(!$b[$v])$b[$v]=[$v];$b[$v][]=$k;}print_r(array_values($b));

```

The result is the same, except all values have to be passed over GET parameters inside the key "A".

# Answer
> 2 votes
# Perl 6,  ~~63~~  61 bytes

```
*.pairs.classify(*.value).map({.key,|.value».key}).sort(*.[1])

```

Test it (0-based)

```
{sort *.[1],map {.key,|.value».key},classify *.value,.pairs}

```

Test it (0-based same algorithm)

## Expanded:

```
# WhateverCode lambda (this is the parameter)
*\                                            # [3,2,2,3]

# get a list of Pairs (zero based index => value)
.pairs                                        # (0=>3,1=>2,2=>2,3=>3)

# classify based on the values (unordered result)
.classify(*.value)                            # {2=>[1=>2,2=>2],3=>[0=>3,3=>3]}

# simplify the structure
.map({
  .key,         # the value
  |.value».key  # slip in the indexes
})                                            # ((3,0,3),(2,1,2))

# sort based on first index
.sort(*.[1])

```

# Answer
> 2 votes
# PHP 7.4+, 71 bytes

\*73 bytes to quote the `$_GET` key and avoid Warnings.

Snippet: (Demo)

```
<?foreach($_GET[A]as$k=>$v){$b[$v][0]=$v;$b[$v][]=$k;}print_r([...$b]);

```

Based on rep, I assume IsmaelMiguel knows the best way to post php code in this community so I am building from his foundation. It is not clear to me if `<?` is to be included/counted in my snippet. As this is my maiden post, I am happy for anyone to explain if there is any unnecessary syntax. p.s. I also read Tips for golfing in PHP which seems to me like a terrific candidate for migration to Meta.

The improvements made to Ismael's snippet are:

1. Unconditional assignment of the first element in each subarray (value overwriting)
2. Splatpacking instead of `array_values()` to reindex the output.

# Answer
> 2 votes
# Husk, 6 bytes

```
mS:¥¹u

```

Try it online!

# Answer
> 1 votes
# Clean, ~~61~~ 60 bytes

```
import StdEnv,StdLib
$l=removeDup[[e:elemIndices e l]\\e<-l]

```

Try it online!

Output is 0-indexed

# Answer
> 1 votes
# Ruby, ~~54~~ 52 bytes

```
->a{a.map{|i|[i]+(0..a.size).select{|j|a[j]==i}}|[]}

```

This version allows nil (53 bytes):

```
->a{a.map{|i|[i]+(0...a.size).select{|j|a[j]==i}}|[]}

```

Try it online!

# Answer
> 1 votes
# Kotlin, 83 bytes

```
{it.mapIndexed{i,c->c to i}.groupBy({(a,b)->a},{(a,b)->b}).map{(a,b)->listOf(a)+b}}

```

## Beautified

```
{
    it.mapIndexed { i, c -> c to i }
        .groupBy({ (a, b) -> a }, { (a, b) -> b })
        .map { (a, b) -> listOf(a) + b }
}

```

## Test

```
var f: (List<Int>) -> List<List<Int>> =
{it.mapIndexed{i,c->c to i}.groupBy({(a,b)->a},{(a,b)->b}).map{(a,b)->listOf(a)+b}}

data class Test(val input: List<Int>, val output: List<List<Int>>)

val tests = listOf(
        Test(listOf(3, 2, 2, 3), listOf(listOf(3, 0, 3), listOf(2, 1, 2))),
        Test(listOf(17), listOf(listOf(17, 0))),
        Test(listOf(1, 1), listOf(listOf(1, 0, 1))),
        Test(listOf(1, 1, 2), listOf(listOf(1, 0, 1), listOf(2, 2))),
        Test(listOf(1, 2, 3, 4), listOf(listOf(1, 0), listOf(2, 1), listOf(3, 2), listOf(4, 3))),
        Test(listOf(1, 1, 1, 1), listOf(listOf(1, 0, 1, 2, 3)))
)

fun main(args: Array<String>) {
    for (c in tests) {
        val o = f(c.input)
        if (o != c.output) {
            throw AssertionError("${c.input} -> $o != ${c.output}")
        }
    }
}

```

## TIO

TryItOnline

# Answer
> 1 votes
# Swift 4, 107 bytes

... Yikes.

```
{a in Dictionary(grouping:a.enumerated()){$0.1}.sorted{$0.1.first!.0<$1.1.first!.0}.map{[$0]+$1.flatMap{$0.0}}}

```

Ungolfed:

```
let f = { (input: [Int]) -> [[Int]] in
    return Dictionary(grouping: input.enumerated(), by: { $0.element })
        .sorted { pairA, pairB in // Sort by order of first appearence (lowest offset)
            return pairA.value.first!.offset < pairB.value.first!.offset
        }.map { element, pairs in
            return [element] + pairs.map{ $0.offset /* +1 */} // add 1 here for 1 based indexing
        }
}

```

It's too bad that dictionary loses ordering, forcing me to waste so many characters on sorting back again. This sort of abuse of implicit closure arguments (`$0`, `$1`, ...) and implicit tuple members (`.0`, `.1`, ...) is uhhhhh not pretty.

# Answer
> 1 votes
# Perl 5, 63 + 1 (`-a`) = 64 bytes

```
map$k{$_}.=$".++$i,@F;say$_.$k{$_}for sort{$k{$a}-$k{$b}}keys%k

```

Try it online!

# Answer
> 1 votes
# Factor, 56 bytes

```
[ dup members swap '[ _ dupd indices swap prefix ] map ]

```

Try it online!

# Answer
> 1 votes
# jq, 31 bytes

```
[unique[]as$b|[$b]+indices($b)]

```

This really just uses a `jq` variable to allow the `indices()` function to reference data that's not readily available otherwise.

```
[                             ] - makes the output valid JSON
 unique[]as$b                   - stores each unique number in var "$b"
             |[$b]              - convert number to an array
                   indices($b)  - get all matching positions in an array
                  +             - combined the arrays

```

Try it online!

# Answer
> 0 votes
# Arturo, 57 bytes

```
$[a][map unique a'x[@[x]++select 1..size a'y->x=a\[y-1]]]

```

Try it

```
$[a][                           ; a function taking an argument a
    map unique a 'x [           ; map over unique numbers in a and assign current number to x
        @[x]                    ; x as a list
        ++                      ; prepended to
        select 1..size a 'y ->  ; the indices in a where...
            x = a\[y-1]         ; x equals the value in a at the current index
    ]                           ; end map
]                               ; end function

```

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


title: Filter out the pseudo-elements!

text:
# Question
Title: Filter out the pseudo-elements!
We define the *hyper-average* of an array / list (of numbers) the arithmetic mean of the sums of its prefixes.

For example, the hyper-average of the list `[1, 4, -3, 10]` is computed in the following manner:

* We get the prefixes: `[1], [1, 4], [1, 4, -3], [1, 4, -3, 10]`.
* Sum each: `[1, 5, 2, 12]`.
* And now get the arithmetic mean of the elements in this list: `(1 + 5 + 2 + 12) / 4 = 5`.

A *pseudo-element* of an array is an element whose value is *strictly* lower than its hyper-average. Hence, the pseudo-elements of our example list are `1`, `4` and `-3`.

---

Given a list of floating-point numbers, your task is to return the list of pseudo-elements.

* You don't have to worry about floating-point inaccuracies.
* The input list will never be empty and it may contain both integers and floats. If mentioned, integers may be taken as floats (with `<integer>.0`)
* You may assume that the numbers fit your language of choice, but please do not abuse that in any way.
* Optionally, you may take the length of the array as input as well.
* This is , so standard rules for the tag apply. The shortest code in bytes (**in each language**) wins!

---

# Test Cases

```
Input -> Output

[10.3] -> []
[5.4, 5.9] -> [5.4, 5.9]
[1, 4, -3, 10] -> [1, 4, -3]
[-300, -20.9, 1000] -> [-300, -20.9]
[3.3, 3.3, 3.3, 3.3] -> [3.3, 3.3, 3.3, 3.3]
[-289.93, 912.3, -819.39, 1000] -> [-289.93, -819.39]

```

# Answer
> 8 votes
# 05AB1E, ~~9~~ 8 bytes

-1 bytes thanks to Magic Octopus Urn

```
ηOO¹g/‹Ï

```

Try it online!

```
η        # Get prefixes
 O       # Sum each
  O¹g/   # Get the mean ( length(prefix list) equals length(original list) )
      ‹Ï # Keep only the value that are less than the mean

```

---

# 05AB1E, 6 bytes

Using the new `ÅA` command.

```
ηOÅA‹Ï

```

Try it online!

```
η      # Get prefixes
 O     # Sum each
  ÅA   # Get the mean
    ‹Ï #  Keep only the value that are less than the mean

```

# Answer
> 7 votes
# MATL, 8 bytes

```
ttYsYm<)

```

Try it online! Or verify all test cases.

### Explanation

```
tt    % Implicitly input array. Duplicate twice
Ys    % Cumulative sum
Ym    % Arithmetic mean
<     % Less than? (element-wise). Gives an array containing true / false
)     % Reference indexing : use that array as a mask to select entries
      % from the input. Implicitly display

```

# Answer
> 7 votes
# Japt v2.0a0 `-f`, ~~12~~ ~~11~~ ~~10~~ 9 bytes

```
<Wå+ x÷Wl

```

Try it

-1 byte thanks to ETH pointing out a redundant character.

```
<Wå+ x÷Wl     :Implicit filter of each element in input array W
<             :Is less than
 Wå+          :  Cumulatively reduce W by addition
     x        :  Reduce by addition
      ÷Wl     :  Divide by length of W

```

# Answer
> 4 votes
# Python 3 with Numpy, 48 bytes

```
lambda x:x[x<mean(cumsum(x))]
from numpy import*

```

Input and output are Numpy arrays. Try it online!

# Answer
> 4 votes
# Husk, ~~10~~ 9 bytes

Thanks @Zgarb for golfing off 1 byte!

```
f</L⁰Σ∫⁰⁰

```

Try it online!

### Ungolfed/Explanation

```
           -- argument is ⁰ (list)
f       ⁰  -- filter the original list with
 <         --   element strictly smaller than
     Σ∫⁰   --   sum of all prefixes
  /L⁰      --   averaged out

```

# Answer
> 4 votes
## Haskell, 39 bytes

```
f l=filter(<sum(scanl1(+)l)/sum(1<$l))l

```

Try it online!

Unfortunately `length` is of type `Int`, so I cannot use it with floating point division `/` and I have to use a workaround: `sum(1<$l)`.

# Answer
> 4 votes
# Java 8, 81 bytes

This lambda expression accepts a `List<Float>` and mutates it. The input list's iterator must support removal (`ArrayList`'s does, for example). Assign to `Consumer<List<Float>>`.

```
a->{float l=0,t=0,u;for(float n:a)t+=n*(a.size()-l++);u=t/l;a.removeIf(n->n>=u);}

```

## Ungolfed lambda

```
a -> {
    float l = 0, t = 0, u;
    for (float n : a)
        t += n * (a.size() - l++);
    u = t / l;
    a.removeIf(n -> n >= u);
}

```

Try It Online

## Acknowledgments

* -3 bytes thanks to *Kevin Cruijssen*
* -17 bytes thanks to *Nevay*

# Answer
> 3 votes
# Jelly, 9 bytes

```
+\S÷L<Ðf@

```

Try it online!

# Answer
> 3 votes
# Python 2, ~~78~~ ~~76~~ ~~71~~ 66 bytes

*-7 bytes thanks to Mr. Xcoder.*

```
lambda l:[x for x in l if x<sum(sum(l[:i])for i in range(len(l)))]

```

Try it online!

# Answer
> 3 votes
# JavaScript (ES6), ~~56~~ ~~55~~ 52 bytes

```
a=>a.filter(x=>x<t/a.length,a.map(x=>t+=s+=x,s=t=0))

```

---

## Test it

```
o.innerText=(f=

a=>a.filter(x=>x<t/a.length,a.map(x=>t+=s+=x,s=t=0))

)(i.value=[1,4,-3,10]);oninput=_=>o.innerText=f(i.value.split`,`.map(eval))
```

```
<input id=i><pre id=o>
```

# Answer
> 3 votes
# Perl 6, 31 bytes

```
{.grep(flat([\,] $_).sum/$_>*)}

```

Try it online!

# Answer
> 3 votes
# , 31 bytes

```
function(l)l[l<mean(cumsum(l))]

```

Try it online!

# Answer
> 2 votes
# C# (Mono), 95 bytes

```
using System.Linq;a=>a.Where(d=>d<new int[a.Length].Select((_,i)=>a.Take(i+1).Sum()).Average())

```

Try it online!

# Answer
> 2 votes
# Python 3, 76 bytes

```
lambda x:[w for w in x if w<sum(u*v+v for u,v in enumerate(x[::-1]))/len(x)]

```

Input and output are lists of numbers. Try it online!

This works in Python 2 too (with the obvious replacement for `print` syntax in the footer).

# Answer
> 2 votes
# Python 3, 72 bytes

```
lambda x:[*filter((sum(-~a*b for a,b in enumerate(x))/len(x)).__gt__,x)]

```

Try it online!

# Answer
> 2 votes
# Pyth - 10 bytes

```
<#.OsM._QQ

```

Try it online here.

# Answer
> 2 votes
# Mathematica, 35 bytes

```
Cases[#,x_/;x<#.Range[#2,1,-1]/#2]&

```

`Function` which expects a list of numbers as the first argument `#` and the length of the list as the second argument `#2`. `#.Range[#2,1,-1]/#2` takes the dot product of the input list `#` and the the list `Range[#2,1,-1] == {#2,#2-1,...,1}`, then divides by the length `#2`. Then we return the `Cases` `x_` in the input list `#` which are less than the hyper-average.

Without the length as a second argument, we need `6` more bytes:

```
Cases[#,x_/;x<#.Range[h=Tr[1^#],1,-1]/h]&

```

# Answer
> 2 votes
# TI-Basic, 9 bytes

```
Ans*(Ans<mean(cumSum(Ans

```

# Answer
> 2 votes
# Factor, 36 bytes

```
[ dup cum-sum mean '[ _ < ] filter ]

```

Try it online!

## Explanation:

It's a quotation (anonymous function) that takes a sequence from the data stack as input and leaves a sequence on the data stack as output. Assuming `{ 1 4 -3 10 }` is on the data stack when this quotation is called...

* `dup` Duplicate an object.

**Stack:** `{ 1 4 -3 10 } { 1 4 -3 10 }`
* `cum-sum` Take the cumulative sum.

**Stack:** `{ 1 4 -3 10 } { 1 5 2 12 }`
* `mean` Take the mean.

**Stack:** `{ 1 4 -3 10 } 5`
* `'[ _ < ] filter` Take the elements from a sequence that are less than the number on top of the stack.

**Stack:** `{ 1 4 -3 }`

# Answer
> 1 votes
# Pyth, 12 11 bytes

```
f<T.OsM._QQ

```

*-1 byte thanks to Mr. Xcoder*

Try it online!

# Answer
> 1 votes
# Perl 5, 51 + 1 (-a) = 52 bytes

```
$a+=$_*(@F-$c++)for@F;for(@F){print$_,$"if$_<$a/@F}

```

Try it online!

# Answer
> 1 votes
# PHP, 84 bytes

```
for($i=--$argc;$i;)$s+=$i--/$argc*$r[]=$argv[++$k];foreach($r as$x)$x<$s&&print$x._;

```

takes input from command line arguments. Run with `-nr` or try it online.

---

summing up the partial lists is the same as summing up each element multiplied with the number of following elements +1 → no need to juggle with bulky array functions. It´s still long, though.

# Answer
> 1 votes
# Röda, ~~46~~ ~~41~~ 39 bytes

```
f l{l|[_]if[_1*#l<seq(1,#l)|l[:_]|sum]}

```

Try it online!

# Answer
> 1 votes
# J, 15 bytes

```
#~[<[:(+/%#)+/\

```

Try it online! Expects a J-style array (negatives represented using `_` instead of `-` and elements separated by spaces -- see the TIO link for examples).

I don't know if there's a way to remove the parentheses around the mean (`+/%#`) but removing that and the cap would be the first thing I'd try to do to golf this further.

# Explanation

Sometimes J reads like (obfuscated) English.

```
#~ [ < [: (+/ % #) +/\
                   +/\  Sum prefixes
                     \   Get prefixes
                   +/    Sum each
          (+/ % #)      Mean
           +/            Sum of array
              %          Divided by
                #        Length of array
   [ <                  Input array is less than?
                         (gives boolean array of pairwise comparisons)
#~                      Filter by

```

# Answer
> 1 votes
# K (oK), 26 bytes

**Solution:**

```
x@&x<(+/+/'x@!:'1+!#x)%#x:

```

Try it online!

**Examples:**

```
> x@&x<(+/+/'x@!:'1+!#x)%#x:1 4 -3 10
1 4 -3
> x@&x<(+/+/'x@!:'1+!#x)%#x:-289.93 912.3 -819.39 1000
-289.93 -819.39

```

**Explanation:**

Interpretted right-to-left. Struggled with a short way to extract prefixes:

```
x@&x<(+/+/'x@!:'1+!#x)%#x: / the solution
                        x: / store input in x, x:1 4 -3 10
                       #   / count, return length of x, #1 4 -3 10 => 4
     (               )     / do everything in the brackets together
                   #x      / count x
                  !        / til, range 0..x, !4 => 0 1 2 3
                1+         / add 1 vectorised, 1+0 1 2 3 => 1 2 3 4
             !:'           / til each, e.g. !1, !2, !3, !4
           x@              / index into x at these indices (now we have the prefixes)
        +/'                / sum (+ over) each, e.g. 1 5 2 12
      +/                   / sum over, e.g. 20
                      %    / right divided by left, 20%4 => 5 (now we have the hyper average)
   x<                      / boolean list where x less than 5
  &                        / indices where true, &0111b => 1 2 3
x@                         / index into x at these indices (now we have the filtered list)

```

**Notes:**

Alternative version taking length of input as parameter (**25** byte solution):

```
> {x@&x<(+/+/'x@!:'1+!y)%y}[1 4 -3 10;4]
1 4 -3

```

# Answer
> 1 votes
# Jelly, 6 bytes

```
<ƇÄS÷ɗ

```

Try it online!

Takes the list on the left and its length on the right, as explicitly permitted.

With newer builtins, Leaky Nun's `+\S÷L<Ðf@` becomes `ÄS÷L<Ƈ@` (which may as well be `ÄS÷L>x@`, using one less piece of the present, but that's besides the point), but taking the length as the right argument trades an `L` and an `@` for one `ɗ`.

```
 Ƈ        Filter the left argument to elements which
<         are less than
   S ɗ    the sum of
  Ä       the cumulative sums of the left argument
    ÷     divided by the right argument.

```

# Answer
> 1 votes
# Arturo, 42 bytes

```
$[a][select a'x[0x<average map a=>[dup+]]]

```

Try it

```
$[a][                      ; a function taking an argument a
    select a 'x [          ; select numbers from a and assign current number to x
        0                  ; push 0 to the stack
        x <                ; is x less than...
        average            ; ...the mean...
        map a => [dup +]   ; ...of the cumulative sum of a?
    ]                      ; end select
]                          ; end function

```

# Answer
> 1 votes
# Julia 0.5, 24 bytes

```
~x=x[x.<mean(cumsum(x))]

```

Try it online!

In modern Julia, `mean` was moved from `Base` to the `Statistics` module:

# Julia 1.0, 33 bytes

```
~x=x[x.<sum(cumsum(x))/length(x)]

```

Try it online!

# Answer
> 1 votes
# Nibbles, 5.5 bytes (11 nibbles)

```
|$-/+`\@+,@

```

Nibbles uses only integers, so I'm "assuming that the numbers fit my language of choice" by omitting decimal points from fractional inputs & padding with zeros where needed. I hope that this is not construed as "abusing" the lenient input rule in any way.

```
|$              # filter input to retain only those that are truthy when:
  -             #   subtracting them from
    +           #     the sum of
     `\@+       #     the cumulative sums of the input
   /            #     divided by
         ,@     #     the length of the input

```

# Answer
> 0 votes
# Pip, 19 bytes

```
_<$+$+*(aH\,b)/bFIa

```

Makes use of the optional length input.

How?

```
_<$+$+*(aH\,b)/bFIa  : -xp; Two args: array and length
        a         a  : First input; array
            b  b     : Second input; length
                FIa  : Filter: keep items from iterable 'a' which return truthy
_                    : Passed element
 <                   : Is less then
        aH           : Get prefix of a that is # elements long
          \,b        : Range from one to length
    $+*              : Sum of each list
  $+                 : Sum list
              /b     : Divide by length

```

Try It Online!

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


title: Make a list flat

text:
# Question
Title: Make a list flat
Lists can contain lists and we have nested lists. But we don't like nested lists and want to flatten them. By flattening I mean create a list which does not contain any list, but elements of lists it contained before. I'll explain it more.

## Input

An arbitrary size list which has the below properties:

* it can contain integers
* it can be empty
* it can contain lists which have the same properties

These are some examples of valid lists:

```
[]
[1, 2, 46]
[[], []]
[[[14], [[5]]], 4, [2]]

```

## Output

The output must be a list, which is empty or only contains numbers. It must not contain lists. The output must be the flattened version of the input.

* all elements (beside empty lists) must be in the flattened version
* the order matters

# Test cases:

```
[[3],[3, [[6]]]] ->  [3, 3, 6]

[] -> []

[[], []] -> []

[[1, 4, 6], [1, [2, 67, [5, 7]]]] -> [1, 4, 6, 1, 2, 67, 5, 7]

```

# Answer
> 16 votes
# Languages with built-ins

HBL, 0.5: `-` \- Try it online!

Fig, ~0.823: `f` \- Try it online!

flax, 1: `F` \- Try it online!

Japt, 1: `c` \- Try it online!

Jelly, 1: `F` \- Try it online!

Vyxal, 1: `f` \- Try it online!

05AB1E, 1: `˜` \- Try it online!

Pyt, 1: `Ƒ` \- Try it online!

, 1: `,` \- Try it online!

Pip, 2: `FA` \- Try it online!

Pyth, 2: `.n` \- Try it online!

Haskell \+ hgl, 3: `rtc`

Attache, 4: `Flat` \- Try it online!

rSNBATWPL, 5: `crush` \- Try it online!

(almost), 6: `unlist` \- Try it online!

Clojure, 7: `flatten` \- Try it online!

jq, 7: `flatten` \- Try it online!

Factor, 7: `flatten` \- Try it online!

Haskell \+ free, 7: `retract` \- Try it online!

Kotlin, 7: `flatten` \- Try it online!

Mathematica, 7: `Flatten` \- Try it online!

Prolog (SWI), 7: `flatten` \- Try it online!

Racket, 7: `flatten` \- Try it online!

Ruby, 7: `flatten` \- Try it online!

Arturo, 7: `flatten` \- Try it

---

Feel free to add to this community wiki. The below is a template to copy the code and links into to add to the above list.

```
[<language>](<language URL>), <byte-count>: `<code>` - [Try it online!](<interpreter url>)

```

# Answer
> 11 votes
# Python 2, 39 bytes

```
f=lambda s:[s]*(s<f)or sum(map(f,s),[])
```

Attempt This Online!

Found independently but very similar to @xnor's answer to the linked question.

# Answer
> 8 votes
# sh + coreutils, 8 bytes

`tr -d []`

# Answer
> 4 votes
# , 22 bytes

```
\(x)as.list(unlist(x))
```

Attempt This Online!

`unlist` is an almost-built-in (see the CW answer) in R, as it doesn't correctly handle the empty lists - it returns `NULL`. Also, it returns a vector of values not a list, so we convert the result to list with `as.list`. Fortunately, `as.list(NULL)` results in an empty list as desired.

---

### , ~~40~~ 38 bytes

*Edit: -2 bytes thanks to @Dominic van Essen.*

```
\(x)`if`(is.null(r<-unlist(x)),1[0],r)
```

Attempt This Online!

Outputs a vector (empty for input without any elements).

# Answer
> 4 votes
# Whython, 31 bytes

```
f=lambda l:sum(map(f,l),[])?[l]

```

### Explanation

```
f=                               # f is
  lambda                         # a function
         l:                      # that takes a single argument l:
               map(f,l)          # First, apply f to every element of l
           sum(        ,[])      # Then concatenate all the resulting lists together
                           ?     # If l is an integer, the map errors, so instead
                            [l]  # just wrap l in a singleton list and return that

```

Attempt This Online!

# Answer
> 3 votes
# , 58 bytes

```
f=\(x,z=0[0]){for(i in x)z=c(z,`if`(is.list(i),f(i),i));z}
```

Attempt This Online!

'Roll your own' `unlist`-like function in R. Returns a vector containing all the elements of the input (nested-)list, or an empty numeric vector if the input doesn't contain any elements.

# Answer
> 3 votes
# C (gcc), 169 166 bytes

```
#include<ctype.h>
#define D isdigit(*c))
#define P putchar(
#define R while(*c&&!D c++;
main(char*c,int**v){c=v[1];P 91);R do{while(D P*c++);R P*c?44:93);}while(*c);}

```

Try it online!

# Answer
> 3 votes
# brainfuck, 350 bytes

```
-[<+>---]<++++++.[-]<,[>+<[>>+>+<<<-]>>>[<<<+>>>-]--[<->++++++]<-[>+>+<<<<[>>>>>+>+<<<<<<-]>>>>>>[<<<<<<+>>>>>>-]-[<->---]<------[<->[-]]<+<<<<[>>>>>+>+<<<<<<-]>>>>>>[<<<<<<+>>>>>>-]-[<->---]<--------[<->[-]]<[[-]<->]<[<<<.[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]----[<-------->+]<[<<<<<[-]+>>>>>[-]]<[-]]<[-]<->]<[<<[>.>>][-]>>[-]]<,]>>-[<+>---]<++++++++.

```

Try it online!

Works by ignoring brackets inside the outermost list. It makes sure not to print a comma after another comma.

Can probably be improved.

# Answer
> 2 votes
# Charcoal, 53 bytes

```
⊞υθＦυＦιＦ⁼κ⁺⟦⟧κ⊞υκＦ⮌υ«≔⟦⟧ηＷι⊞η⊟ιＦ⮌η¿⁼κ⁺⟦⟧κＦκ⊞ιλ⊞ικ»⭆¹θ

```

Try it online! Link is to verbose version of code. Uses the same flattening code as I used in my answer to Inverted ragged list but I'll explain it in slightly more detail here.

```
⊞υθＦυＦιＦ⁼κ⁺⟦⟧κ⊞υκ

```

Push the input list and all of its sublists to the predefined empty list.

```
Ｆ⮌υ«

```

Loop over all of the sublists in reverse order i.e. deepest first.

```
≔⟦⟧ηＷι⊞η⊟ι

```

Remove the elements of the sublist and push them to a temporary list.

```
Ｆ⮌η¿⁼κ⁺⟦⟧κＦκ⊞ιλ⊞ικ

```

Loop over the elements of the temporary list in the order they were in the original sublist. For those elements that are sublists push their elements (which by now are just integers) to the sublist otherwise just push the integer element to the sublist.

```
»⭆¹θ

```

Pretty-print the final list so that you can see that it has been flattened.

# Answer
> 2 votes
# PARI/GP, 34 bytes

```
f(a)=if(#a&&a!=b=concat(a),f(b),a)

```

Attempt This Online!

# Answer
> 2 votes
# Python, ~~58~~ 55 bytes

```
lambda l:[*map(int,re.findall('\d+',str(l)))]
import re
```

Attempt This Online!

Thought it was a bit cheeky using regex to flatten the list

-3 bytes thanks to @Dingus

# Answer
> 2 votes
# Javascript (node), ~~70~~ ~~49~~ 47 Bytes

```
f=(a,c=[])=>a.map(a=>a.map?f(a,c):c.push(a))&&c

```

Try it online!

# Answer
> 2 votes
# Wolfram Language (Mathematica), 13 bytes

```
#~Level~{-1}&

```

Try it online!

Not the built-in. Returns all atomic expressions, in order.

---

### Wolfram Language (Mathematica), 11 bytes

```
##&@@#0/@#&

```

Try it online!

Returns a `Sequence` instead of a `List`.

### Wolfram Language (Mathematica), 6 bytes

```
#<>""&

```

Try it online!

Returns a `StringJoin` instead of a `List`, and an empty string when there are no elements (as `StringJoin[]` evaluates to `""`).

# Answer
> 2 votes
# Javascript, ~~96~~ 83 bytes

```
f=a=>JSON.stringify(a).replace(/[\[\],]/g,' ').split(/\s/).filter(e=>e).map(e=>e-0)

```

Try it online!

# Answer
> 2 votes
# Scala, 75 bytes

```
def f(l:List[_]):List[_]=l.flatMap{case n:Int=>List(n)case p:List[_]=>f(p)}

```

My first Scala answer! With a lot of help from @user.
Try it online!

# Answer
> 2 votes
# BQN, 8 bytes

```
∾⍟(¯1+≡)

```

Try it here!

Thanks to @Razetime for 6 bytes saved!

## Explanation

* `...⍟(¯1+≡)` repeat (depth - 1) times...
* join (same effect as flattening 1 level)

# Answer
> 2 votes
# Prolog (SWI), ~~62~~ 38 bytes

*Thanks @Steffan for a staggering -24 bytes!!!*

```
L+X:-maplist(+,L,M),append(M,X);X=[L].

```

Try it online!

There's probably a builtin out there which flattens lists, but here's a non-builtin way of doing it.

# Answer
> 2 votes
# Prolog (SWI), 45 bytes

```
[A|L]+B:-A+X,L+Y,append(X,Y,B).
[]+[].
A+[A].

```

Try it online!

Uses pattern matching to decompose and recursively call the function on the head and tail of the list.

### Explanation

```
[A|L]+B:-                         # Match on list input with at least one input
         A+X,                     # Recursively call on the head of the list
             L+Y,                 # And on the tail
                 append(X,Y,B).   # And combine the results together
[]+[].  # If the element is just an empty list, return the same
A+[A].  # If it just a single element, return a singleton list

```

# Answer
> 1 votes
# C (clang), ~~114~~ ~~99~~ 89 bytes

* -15 bytes with help from @ceilingcat

```
main(c,v)char**v;{for(;v;c=!printf(v?c?"[%s":",%s":"[]"+!c,v))v=strtok(c?v[1]:0,",[ ]");}

```

Try it online!

# Answer
> 1 votes
# JavaScript (Node.js), 30 bytes

```
a=>eval(`[${a}]`).filter(x=>1)

```

Try it online!

# JavaScript (Node.js), 39 bytes

```
a=>((a+'').match(/\d+/g)||[]).map(eval)

```

Try it online!

Assume no negative input

# Answer
> 0 votes
# APL(Dyalog Unicode), 1 bytes SBCS

Try it on APLgolf!

# Answer
> 0 votes
# Javascript 46 bytes

```
f=a=>(a+'').split(',').filter(x=>x).map(s=>+s)

```

Try it online!

Uses the trick that stringification of arrays unnests all arrays. After that empty elements need to be removed and the result mapped to integers.

---
Tags: code-golf, ragged-list
---


# Question
Title: Better way to read multiple int in C than scanf
I'm trying to read 4 ints in C in a golfing challenge and I'm bothered by the length of the code that I need to solve it:

```
scanf("%d%d%d%d",&w,&x,&y,&z)

```

that's 29 chars, which is huge considering that my total code size is 101 chars. I can rid of the first int since I don't really need it, so I get this code:

```
scanf("%*d%d%d%d",&x,&y,&z)

```

which is 27 chars, but it's still lengthy.

So my question is, is there any other way (tricks, functions, K&R stuff) to read ints that I don't know of that could help me reduce this bit of code?

---

Some users have reported that my question is similar to Tips for golfing in C

While this topic contain a lot of useful information to shorten C codes, it isn't relevant to my actual use case since it doesn't provide a better way to read inputs.

I don't know if there is actually a better way than scanf to read multiple integers (that's why I'm asking the question in the first place), but if there is, I think my question is relevant and is sufficiently different than global tips and tricks.

If there is no better way, my question can still be useful in the near future if someone find a better solution.

I'm looking for a full program (so no function trick) and all libraries possible. It needs to be C, not C++. Currently, my whole program looks like this:

```
main(w,x,y,z){scanf("%*d%d%d%d",&x,&y,&z)}

```

Any tricks are welcome, as long as they shorten the code (this is code golf) and work in C rather than C++.

# Answer
> 8 votes
Thanks to @DialFrost for drawing my attention to this question.

I believe for reading 4 numbers your solution is optimal. However, I found a solution that saves bytes when reading 5 or more numbers at a time.

It will also consume the entire input (i.e. it can't be used in a loop).

Depending on the context it might help you with only 4 variables too

If you define your variables in a sequence like this:

```
a,b,c,d,e;main(){

```

In this case, the variables will be layed out in successive memory addresses, we can abuse that.

```
for(;~scanf("%d",&a+e);e++);

```

Full program:

```
// new
a,b,c,d,e;main(){for(;~scanf("%d",&a+e);e++);}
// original
a,b,c,d;main(e){scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);}

```

This 29 byte segment will paste all the input in successive variables starting in `a`. We re-use `e`, (the last variable) as the index variable. This saves declaring one variable.

## Size comparison

| Number of inputs | Original | New | Original (full program) | new (full program) |
| --- | --- | --- | --- | --- |
| 1 | 14 | 28 | 24 | 38 |
| 2 | 19 | 28 | 31 | 40 |
| 3 | 24 | 28 | 38 | 42 |
| 4 | 29 | 28 | 45 | 44 |
| 5 | 34 | 28 | 52 | 46 |
| 6 | 39 | 28 | 59 | 48 |

Note that the new method gains a 1 byte disadvantage in full programs because you can't use function arguments, however, this doesn't matter if you can use another variable as the argument to `main`.

Note there is also a slot in the initialization portion of the for loop. If you can put another expression there this method can save 1 byte even with only 4 arguments.

Try it online!

@JDT ponted out you can save 1 byte at the cost of having 1 added to `e` at the end:

```
for(;0<scanf("%d",&a+e++););

```

# Answer
> 5 votes
If you want to e.g. print all the inputs then we have this, being 64 bytes long:

```
main(x,y,z){scanf("%*d%d%d%d",&x,&y,&z);printf("%d%d%d",x,y,z);}

```

We can actually shorten this with a loop, bringing the total down to 47 bytes:

```
main(z){for(;scanf("%d",&z)>0;)printf("%d",z);}

```

So the reading part is only 23 bytes long:

```
for(;scanf("%d",&z)>0;)

```

Note that this only works when you don't want to assign a value to a specific variable and only want to **read** the values.

A method that is 29 bytes long:

```
for(;scanf("%d",&a+i)>0;i++);

```

Shout out to @mousetail for helping me out!

# Answer
> 1 votes
# C (gcc),  ~~44~~  43 bytes

```
main(i,a,b,c,d){for(;i+=scanf("%d",i+&i););

```

Try it online!

This frees up an extra integer `i=0`, while mousetail's solution make `i=5`(can't find a compiler that allow reusing `e` as index without adding extra 1)

Need `-m32` maybe because on x64 values are passed via registers

# C (tcc), 44 bytes

```
a,b,c,d,i;main(){for(;i+=scanf("%d",i+&a););

```

Try it online!

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


title: Help me figure out what TeX I can use!

text:
# Question
Title: Help me figure out what TeX I can use!
On TeX.SE the Help Centre says that the following is on topic:

```
Formats like LaTeX, ConTeXt and plain TeX
Engines like pdfTeX, LuaTeX and XeTeX
Distributions like TeX Live, MiKTeX, and MacTeX
Related software and tools, BibTeX, MakeIndex, Lyx, etc.

```

I wanted you to write a program to tell me whether my TeX is in the on-topic types of TeX.

An explicit list of the valid TeX-s is as follows:

* MetaPost
* PostScript
* MetaFUN
* TeX
* LaTeX
* LuaLaTeX
* LuaTeX
* ConTeXt
* BibTeX
* pdfTeX
* Lyx
* MakeIndex
* TeX Live
* XeLaTeX
* XeTeX
* MacTeX
* MiKTeX

## Rules

* You may use any language.
* This is , to the shortest answer wins.
* If you use Regex, you can just match correct ones.
* You only need to match one at a time: no

Lyx BibTeX
* You must check **with capitalization listed here**.

## Tests

```
TeX -> True/1/<match>
pTeX -> False/0/<not-match>
ConTeXt -> True/1/<match>
context -> False/0/<not-match>
MetaFun -> False/0/<not-match>
MetaFUN -> True/1/<match>

```

*P.S. Bonus points for an on-topic TeX answer!*

# Answer
> 1 votes
# JavaScript Regex, ~~99~~ ~~101~~ ~~99~~ 97 + 1 for `g` flag = *98 bytes*

```
^(((Xe|Lua)?(La)?|Bib|MiK|pdf|Mac)TeX|ConTeXt|TeX Live|Meta(FUN|Post)|PostScript|MakeIndex|Lyx)$

```

Test it here. Type into the `Text` box. Alternatively, test it here.

```
var j = $("#dos");
var text;
function abc(){
  text = $('#uno').val();
  j.val(text.match(/^(((Xe|Lua)?(La)?|Bib|MiK|pdf|Mac)TeX|ConTeXt|TeX Live|Meta(FUN|Post)|PostScript|MakeIndex|Lyx)$/g) == text ? "Matches!" : "No match!");
};
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<input id='uno' /><br />
<button id='tres' onclick="javascript:abc()">Test!</button><br/>
<input id='dos' />
```

Test all cases:

```
var j = $("#dos");
var tests = ["TeX", "pTeX", "ConTeXt", "context", "MetaFun", "MetaFUN", "TeX Live"];
function abc(e){
  j.val(j.val() + e + ": " + (e.match(/^(((Xe|Lua)?(La)?|Bib|MiK|pdf|Mac)TeX|ConTeXt|TeX Live|Meta(FUN|Post)|PostScript|MakeIndex|Lyx)$/g) == e ? "Matches!" : "No match!") + "\n");
};

function def(){
  tests.forEach(abc);
}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<button id='tres' onclick="javascript:def()">Test!</button><br/>
<textarea rows=50 cols=200 id='dos'>
</textarea>
```

# Answer
> 0 votes
# Python 3.5, ~~149~~ ~~147~~ ~~137~~ 136 bytes

```
import re;lambda f:re.fullmatch('TeX Live|(La|LuaLa|Lua|Bib|pdf|XeLa|Xe|Mac|MiK)?TeX|Lyx|MakeIndex|Meta(Post|FUN)|PostScript|ConTeXt',f)

```

An anonymous function that uses a regular expression to return a `re` match object (such as `<_sre.SRE_Match object; span=(0, 5), match='LaTeX'>`) as a truthy value and `None` as a falsy value. The actual regular expression is currently **~~102~~ ~~100~~ 99 bytes** in length.

Try It Online! (Ideone)

# Answer
> 0 votes
# Perl 5, 103 bytes

102 bytes, plus 1 for `-pe` instead of `e`. Stdin→stdout.

```
$_=/^(Meta(Post|FUN)|TeX Live|PostScript|((Xe|Lua)?(La)?|Bib|pdf|M(ac|iK))TeX|ConTeXt|Lyx|MakeIndex)$/

```

# Answer
> 0 votes
# Thunno, \\$ 122 \log\_{256}(96) \approx 100.42 \\$ bytes

```
"MetaPost|PostScript|MetaFUN|?|La?|LuaLa?|Lua?|ConTeXt|Bib?|pdf?|Lyx|MakeIndex|? Live|XeLa?|Xe?|Mac?|MiK?"'?"TeX"AR'|ZisAq

```

Attempt This Online!

```
"..."'?"TeX"AR'|ZisAq  # Implicit input
"..."                  # Push the string
            AR         # Replace...
     '?                # ...the character '?'...
       "TeX"           # ...with the string "TeX"
                Zi     # Split the resulting string...
              '|       # By the character '|'
                  sAq  # Is the input in this list?
                       # Implicit output

```

---
Tags: code-golf
---


title: Build a fewest-moves freecell solver

text:
# Question
Title: Build a fewest-moves freecell solver
In the game of Freecell, you are tasked with building four foundation piles in suit from ace to king, on a layout where you build downward in alternating colours. However, you can only build one card at a time, so you are given four "free cells" each of which can contain one card to help you move entire sequences. The idea is that you weave individual cards in and out of the free cells as required to help you solve the game.

Your task is to build a program that will solve these games in the fewest moves possible.

Your program will take as input a sequence of 52 cards, in the following format:

```
2S 9H 10C 6H 4H 7S 2D QD KD QC 10S AC ...

```

Which will be dealt in the initial layout in this order:

```
01 02 03 04 05 06 07 08
09 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52

```

And return a list of moves to solve the game. Each move will be in this format:

* A number representing the pile number (`1` through `8`), or a free cell (`A` to `D`), representing the source pile.
* Another number or letter representing the destination pile or free cell, or `F` for the foundation of that suit.

The output will look something like this:

```
18 28 3A 8B 8C 85 B5 35 4F etc.

```

Once a card is put into the foundation, it cannot be removed. Since only one card is moved at a time, moving a sequence of 3 cards requires 5 moves, and a sequence of 5 cards requires 9 moves.

If a game is unsolvable, your program should indicate as such. However, your program must be able to solve any solvable game.

Your program will be judged on the 32,768 deals found in the original Microsoft FreeCell program. In order to be valid, your program must successfully solve every deal except deal #11,982, which is unsolvable. Your score will be the total number of moves it takes to solve these 32,767 deals, with shorter code being a tie-breaker.

---

A file with all the decks in the format required by the above specification is available for download here (5.00 MB file): https://github.com/joezeng/pcg-se-files/raw/master/freecell\_decks

# Answer
# Haskell, Score: 4.98M, 7564 Bytes

```
{-# LANGUAGE BangPatterns #-}

import Control.Concurrent.Async (race)
import Control.Concurrent.Async.Extra (sequenceConcurrently)
import qualified Data.Vector as V
import qualified Data.List   as L
import qualified Data.IntSet as S

type Deck     = String           -- a line of the input, s.th. like
                                 -- JD 2D 9H JC 5D 7H 7C...
type Card     = (Int , Int)      -- (Suit, Rank)
type Cascade  = [Card]           -- bottom up, i.e. head is the accessible card
type Board    = V.Vector Cascade -- the whole Board: 16 lots of cascades
                                 -- 0..7:tableau, 8..11:cells, 12..15:foundation
type Move     = (Int , Int)      -- 'from' and 'to' board index
type Game     = (Board, [Move])  -- a Board and the Moves to get there
type Strategy = Int

idxTbl, idxFnd, idxTblR, idxFrom :: [Int]
idxTbl  = [ 0.. 7]               -- indices of tableau cascades
idxTblR = [7,6..0]               -- indices of tableau in reverse order
idxFnd  = [12..15]               -- indices of foundations
idxFrom = [ 0..11]               -- all indices where a card can be moved from

(@@) :: Board -> Int -> Cascade  -- return cascade at index i
(@@) = (V.!)

(@!) :: Board -> Int -> Int      -- return the rank of the top card at index i
brd @! i = snd $ head $ brd@@i

(//) :: Board -> [(Int, Cascade)] -> Board
(//) = (V.//)                    -- update from Data.Vector

solved :: Board -> Bool
solved brd = all ((==13).(brd@!)) idxFnd

--
--
--

main :: IO ()
main = print . sum =<< mapM solveDeck . lines =<< getContents

-- applies different strategies and hash functions to a given deck
-- does all the concurreny stuff
solveDeck :: Deck -> IO Int
solveDeck deck = do
  putStrLn $ "Playing Deck: " ++ deck

  mvs <- sequenceConcurrently            -- try fast hash funtions concurrently
         [dfs hsh S.empty s startGame | hsh<-[hashCLS, hashCL], s<-[1..4]]
  let scores = [(length m, reverse m) | m <- mvs, not $ null m]

  if null scores
  then do   -- unsolvable by fast hash functions, retry with slow hash function
    mvs2 <- race' (race' (dfs hashC S.empty 1 startGame)
                         (dfs hashC S.empty 4 startGame))
                  (race' (dfs hashC S.empty 2 startGame)
                         (dfs hashC S.empty 3 startGame))
    let score2 = length mvs2
    putStrLn $ "Solution: " ++ show (score2, reverse mvs2)
    return score2
  else do   -- at least one slow hash function succeeded, return best result
    let winner = minimum scores
    putStrLn $ "Solution: " ++ show winner
    return $ fst winner

  where
  !startGame = [(deal deck, [])]
  race' one two = race one two >>= either return return

-- depth first search with a given strategy and hash function
dfs :: (Board -> Int) -> S.IntSet -> Strategy -> [Game] -> IO [Move]
dfs _ _ _ [] = return []
dfs hashFn seen strat ((brd,mvs):games)
  | S.member hBrd seen = dfs hashFn seen strat games --skip board if seen before
  | solved brd = return mvs                          --solution found
  | otherwise = dfs hashFn (S.insert hBrd seen) strat (newGames++games)
                                                     --descend the search space
  where
  hBrd = hashFn brd
  newGames = nextGames mvs brd strat

-- one step in search
nextGames :: [Move] -> Board -> Strategy -> [Game]
nextGames moves brd strategy
  | mv:_ <- autoMoves = doAuto mv
  | otherwise         = checkMoves $ allMoves strategy

  where

  -- all possible from/to combinations except between freecells and only to
  -- first empty freecell. Based on strategy.
  allMoves 1 = [(f,t) | f<-fList, t<-tList idxTbl,  f<8||f>11||t<8||t>11]
  allMoves 2 = [(f,t) | f<-fList, t<-tList idxTblR, f<8||f>11||t<8||t>11]
  allMoves 3 = [(f,t) | t<-tList idxTbl, f<-fList,  f<8||f>11||t<8||t>11]
  allMoves 4 = [(f,t) | t<-tList idxTblR, f<-fList, f<8||f>11||t<8||t>11]
  allMoves _ = error "allMoves: strategy out of range"

  -- "from" indices are always ordered by minimum rank in respective cascade
  fList = L.sortOn (minimum.map snd.(brd@@)) $ filter (not.null.(brd@@)) idxFrom

  -- order of "to" indices is foundation before freecell before tableau
  -- * only tableau is subject to strategy
  -- * only first empty freecell (if any)
  -- * foundation is "12" for all suits, we'll unravel that later
  tList idxs
    | null $ brd@@ 8 = 12: 8:idxs
    | null $ brd@@ 9 = 12: 9:idxs
    | null $ brd@@10 = 12:10:idxs
    | null $ brd@@11 = 12:11:idxs
    | otherwise      = 12:   idxs

  -- checks which moves from 'allMoves' are actually legal and executes
  -- them returning a list of games
  checkMoves [] = []
  checkMoves (mv@(f,t):mvs)
    | t == 12   = if fitsFnd then doFnd else checkRest  -- to foundation
    | t  <  8   = if fitsTbl then doTbl else checkRest  -- to tableau
    | otherwise = doCell                                -- to cell (alway empty)

    where
    !cscdT = brd@@t
    !cscdF = brd@@f
    !cardF@(suitF,rankF) = head cscdF
    (suitT,rankT) = head cscdT

    fitsTbl = null cscdT || rankT==rankF+1 && odd (suitF+suitT)
    fitsFnd = rankF-1 == brd@!(12+suitF)

    doTbl  = (brd // [(t, cardF:cscdT),  (f, tail cscdF)], mv:moves) : checkRest
    doCell = (brd // [(t, [cardF]),      (f, tail cscdF)], mv:moves) : checkRest
    doFnd  = (brd // [(t+suitF, [cardF]),(f, tail cscdF)], (f,t+suitF):moves)
                                                                     : checkRest
    checkRest = checkMoves mvs

  -- a list of all greedy automoves
  autoMoves =
    [(f,12+s) | f <- idxFrom,                -- keep all 'from' indices
                let cascade = brd@@f,
                not $ null cascade,          -- if there's a card in the cascade
                let (s,r) = head cascade,
                r-1 == brd@!(12+s),          -- and it fits on its foundation
                let (j,k) = if even s then (13,15) else (12,14),
                r-4 <= min(brd@!j)(brd@!k) ] -- and it's not too greedy

  doAuto mv@(f,t)
    | fCrd:fCrds <- brd@@f = [(brd // [(t,[fCrd]),(f,fCrds)], mv:moves)]
    | otherwise            = error "nextGames: automove from empty cascade"

--
-- parsing and dealing decks
--

deal :: Deck -> Board
deal = foldl putCard emptyBoard . zip (cycle idxTbl) . parse

emptyBoard :: Board            -- foundation is initialised with dummy cards
emptyBoard =                   -- of rank 0, so that aces fit on them nicely
  foldl (\b i -> putCard b (i+12, (i,0))) (V.replicate 16 []) [0..3]

putCard :: Board -> (Int,Card) -> Board
putCard brd (i,crd) = brd // [(i, crd : brd@@i)]

parse :: Deck -> [Card]
parse [] = []
parse (' ':cs)       = parse cs
parse ('1':'0':s:cs) = (chrToSuit s , 10) : parse cs
parse (r:s:cs) | Just i <- L.elemIndex r " A23456789 JQK"
                     = (chrToSuit s, i) : parse cs
parse _              = error "parse: invalid deck"

chrToSuit :: Char -> Int       -- parity important: reds are even, blacks odd
chrToSuit c | Just i <- L.elemIndex c "DSHC" = i
chrToSuit _ = error "chrToSuit: invalid char"

--
-- hash functions
--

hashCLS, hashCL, hashC :: Board -> Int

hashCLS brd = foldl (\h r -> h*16+r)  c $ map (brd@!) idxFnd
  where c   = foldl (\h l -> h*32+l)  0 $ L.sort $ map (length.(brd@@)) idxTbl

hashCL  brd = foldl (\h r -> h*16+r)  c $ map (brd@!) idxFnd
  where c   = foldl (\h l -> h*32+l)  0 $          map (length.(brd@@)) idxTbl

hashC   brd = foldl (\h r -> h*16+r)  c $ map (brd@!) idxFnd
  where c   = foldl (\h s->h*26633+s) 0 $ L.sort $ map (hCscd.(brd@@)) idxTbl
        hCscd cList = foldl (\v (s,r) -> (v*26633+s)*94291+r) 0 cList

```

The list of games is read via stdin. For each game the output is a pair of the number of moves and a list of moves as (from,to) pairs, where both 'from' and 'to' are indices of board positions. 0 to 7 are the eight cascades, 8 to 11 the four free cells and 12 to 15 the four foundations. E.g.

```
Playing Deck: KS 8S 3C 9D QS 4D JD QH 5C 10H 5D 10C 4H 3D 7H AD KC 6S 2S 8D AH 7C QD 6C 7S KH 8C 6H 2C 9C JH KD 4S 5S AC 10S JS 3S 9S 5H AS 4C 8H QC 6D 2H JC 10D 7D 2D 3H 9H
Solution: (85,[(0,8),(0,13),(2,9),(2,10),(2,15),(4,11),(7,6),(2,3),(2,13),(9,0),(4,9),(4,15),(4,14),(5,14),(0,14),(4,14),(5,13),(0,13),(7,14),(5,6),(11,5),(1,11),(5,0),(1,2),(0,5),(1,13),(5,0),(8,3),(7,8),(7,3),(7,12),(11,12),(2,11),(2,3),(2,15),(11,15),(5,11),(5,12),(5,12),(3,12),(0,12),(0,5),(0,2),(0,15),(3,15),(3,12),(11,15),(3,15),(6,15),(1,11),(1,13),(5,13),(3,5),(9,7),(3,9),(6,7),(1,6),(1,13),(3,1),(3,14),(3,12),(3,15),(3,12),(7,12),(6,7),(6,15),(6,13),(1,13),(6,4),(6,3),(6,14),(6,12),(3,12),(8,12),(10,14),(5,14),(7,14),(4,14),(7,13),(4,13),(0,13),(7,14),(9,15),(2,15),(11,14)])

```

At the end the total number of moves is printed.

How it works: The basic approach is a depth first search. As the quality of the search (both number of moves and search time) heavily depends on the search order, I try several orders concurrently and pick the result that finishes first:

* two different nested loops

+ for each available card look where it can be placed
    + for each position look if a card from elsewhere fits on it
* when looping over the destination try in order

+ foundation before free cell before tableau from left to right
    + foundation before free cell before tableau from right to left

That's four different orders (or strategies as I call them) in combination. Source order is the same for all strategies: sorted by minimum rank of all cards in the respective cascade/freecell. There's also autoplay, i.e. if a card can safely be placed in the foundation it's the only move in this situation. It turns out that a greedy autoplay leads to slightly better results, so I autoplay up to two additional ranks (e.g. autoplay 8s even if 5s of opposite color are still around).

However, all this is not good enough (5 games do not finish within reasonable time; about 14.7M moves for the rest), but I had a lucky find: somehow you have to keep track of the boards visited so far to prevent infinite loops during the search. The above method uses a hash which is calculated by rolling through the cascades and including suit and rank of all the cards along the way. Now we are just hashing the length of each cascade plus the top foundation cards (i.e. two boards result in the same hash if (and only if) the foundations are equal and all cascades in order have pairwise the same length). Yes, we do get a lot of collisions but they restrict the search space at pretty good spots and lead to far fewer moves in far less time. In fact, the search is so fast that we can afford to finish all four strategies and pick the best result. A similar hash function where for collision the matching length of a cascade can be anywhere in the tableau and not necessarily at the same index produces even better results - at least on average. Now we can try 8 variants (2 fast hash function with 4 strategies each) and pick the best result. Note: not all variants can solve every game but just one success is enough to get a result. There are 11 games (including the unsolvable #11982) which none of the variants can solve. In these cases I switch back to the slow hash function and pick the fastest result.

Using 4 cores on my laptop this solves all games in about 1.5h and a total of 4.98M moves.

Remarks

* The total number of moves can vary by a few hundred, because the result of the games with the slow hash function depends on how the OS assigns CPU time to the strategies and in different a run a different strategy might finish first. But that's just for 10 games.
* If I let all 12 variants (3 hash functions with 4 strategies each) race agains each other and pick the fastest result I get 7.25M moves in 250 sec.
* The source code is not golfed at all. Removing unnecessary things like comments, types, type annotations, whitespace, error handling and switching to single letter names easily brings the byte count to a third and then we can still apply the usual golfing tricks.
> 5 votes

# Answer
# C 64,643 bytes, Score: ~6.5 million

The following Stack Snippet (courtesy of Mego) outputs all of the code as a single standalone C file:

```
$("#a").text(pako.inflate(atob('[encoded data, 7512 characters]'), {to: 'string'}));
```

```
<script src="https://cdn.rawgit.com/nodeca/pako/master/dist/pako.min.js"></script>
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<pre id="a">

</pre>
```

Download the original source here. Use GCC and run `make` then using the guideline in the readme.

My formatting is bad (all the different files are in one code block) and this could be golfed more (12k bytes tho). Any help would be loved!

Some of the code is not mine. I used it from a un-copyrighted source. I however fixed the input/output method to be within the challenge (a long task since I am horrible at C (5ish hours)). I also had to re-write much of the code and debug everything. Many thanks to my Dad for helping out and being a rubber duck (and pointing out my memory management errors) and for everyone on TNB who dealt with my angry rants about segfaults and C.
> 21 votes

---
Tags: code-challenge, game, test-battery, ai-player
---


# Question
Title: Find the length of the longest substring with all different characters in O(n) time
Let's solve the same task as in this challenge but faster!

**Input**: a non-empty string containing letters a-z

**Output**: the length of a longest (contiguous) substring in which all letters are different

**Time and space complexity**: O(n).

The number of letters in the alphabet is 26, or O(1). Make sure you understand how your language works - e.g. if it can't "extract a substring" in O(1) time, you probably can't use substrings in your implementation - use indices instead.

The solution doesn't need to say at which position it found the longest substring, and whether there is more than one. So, for example, if it found a substring of length 26, it can stop searching (this observation will not help you write your implementation).

### Test Cases

```
abcdefgabc -> 7
aaaaaa -> 1
abecdeababcabaa -> 5
abadac -> 3
abababab -> 2
helloworld -> 5
longest -> 7
nonrepeating -> 7
substring -> 8
herring -> 4
abracadabra -> 4
codegolf -> 6
abczyoxpicdabcde -> 10

```

(I took these directly from the other challenge)

# Answer
# JavaScript (ES6), 62 bytes

Expects an array of characters.

```
a=>a.map((c,i)=>a[m=(d=i-a[c],d<++j?j=d:j)<m?m:j,c]=i,j=m=0)|m

```

Try it online!

### Commented

```
a =>                // a[] = input array, reused as an object to keep
                    // track of the last position of each character
a.map((c, i) =>     // for each character c at position i in a[]:
  a[                //
    m = (           //   m is the maximum length of a valid substring
      d = i - a[c], //   let d be the difference between the current
                    //   position and the last position of c (NaN if
                    //   c has not been seen so far)
      d < ++j ?     //   increment j; if d is less than j:
        j = d       //     we have to force j to d
      :             //   else:
        j           //     keep the incremented value of j
    ) < m ?         //   if j is less than m:
      m             //     leave m unchanged
    :               //   else:
      j,            //     update m to j
    c               //   update a[c] ...
  ] = i,            //   ... to i
  j = m = 0         //   start with j = m = 0
) | m               // end of map(); return m

```
> 7 votes

# Answer
# Vyxal, ~~10~~ 6 bytes

```
UÞx↔tL

```

Try it Online!

Shorter than the Vyxal answer in the original challenge. \\$O(nk!)\\$ where \\$n\\$ is the length of the string and \\$k\\$ is the number of unique characters so it times out when \\$k\geq 10\\$.

```
U      # uniquify
 Þx    # combinations without replacement
   ↔   # keep only those that are in input
    t  # tail
     L # length

```
> 7 votes

# Answer
# Rust, ~~129~~ 127 bytes

```
|s:&[u8]|{let(mut a,mut d,mut e)=(-1,[-1;128],0);for(i,j)in(0..).zip(s){let f=*j as usize;a=a.max(d[f]);d[f]=i;e=e.max(i-a)}e};

```

Attempt This Online!
> 4 votes

# Answer
# Charcoal, 43 bytes

```
≔⦃⦄θ≔⁰η≔⁰ζＦＳ«→≔⌊⟦⊕ζ⁻ⅈ∨§θι⁰⟧ζ§≔θιⅈ¿›ζη≔ζη»Ｉη

```

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

```
≔⦃⦄θ≔⁰η≔⁰ζ

```

Start with an empty dictionary of previous indices, and zero best and current run length.

```
ＦＳ«

```

Loop over the input string.

Increment the canvas X coordinate. This keeps track of the current index without using another variable.

```
≔⌊⟦⊕ζ⁻ⅈ∨§θι⁰⟧ζ

```

Try to increment the current run length, but reduce it to the difference of the current index with the previous index of the current character (or 0 if the character has not been seen previously).

```
§≔θιⅈ

```

Update the last seen index of the current character.

```
¿›ζη≔ζη

```

Update the best run length. (`≔⌈⟦ηζ⟧η` also works for the same byte count.)

```
»Ｉη

```

Output the final best run length.
> 4 votes

# Answer
# Python, 52 bytes

```
lambda A,b="":max(len(b:=a+b.split(a)[0])for a in A)

```

Storing b back-to-front saves a byte.

Attempt This Online!

### Original Python, 53 bytes

```
lambda A,b="":max(len(b:=b.split(a)[-1]+a)for a in A)

```

Attempt This Online!

I'm not sure there are many methods that are not O(n). This one is

### O(n) because

Main loop is over the input string (~\> n iterations). Body takes linear time in the length of b which never exceeds the (fixed) size of the alphabet (~\> O(1)).

Taken together that gives linear time (in n); taking the max does not change this.
> 4 votes

# Answer
# Excel (ms365), 149 bytes

Formula in `B1`:

```
=LET(x,SEQUENCE(LEN(A1)),MAX(MAP(REDUCE(0,x,LAMBDA(y,z,VSTACK(y,MID(A1,z,x)))),LAMBDA(q,(LEN(q)=COUNTA(UNIQUE(MID(q,SEQUENCE(LEN(q)),1))))*LEN(q)))))

```

---

Thought I'd also chuck in a Python solution though I'm sure someone more proficient with Python will post something much smoother:

```
from itertools import combinations
s = 'abcdefgabc'
print(max([(len(set(z))==len(z))*len(z)for z in[s[x:y]for x,y in combinations(range(len(s)+1),r=2)]]))

```

Or, with regular expressions:

```
import regex as r
s = 'abczyoxpicdabcde'
print(max([len(i[0])for i in r.findall(r'((.)((?!\2)(.)(?<!\2.*\4.*\4))*)',s,overlapped=1)]))

```
> 3 votes

# Answer
# Nibbles, 10 bytes

```
/@~0""]@,;:$/`%_$$

```

Attempt This Online!

Time complexity: \\$\mathcal O(nr)\\$, where \\$r\\$ is the result.

```
/      Right fold
@       each line of input
~ 0 ""  with a starting value of (0, "")
        (ch, accumulator) => (
]        max
@         accumulator.first
,         length of
;          s :=
:           join
$            ch
/            fold
`%            split
_              accumulator.second
$              by ch
$             first
         , s)

```
> 2 votes

# Answer
# Pyth, 12 bytes

```
e.MZml=+eckd

```

Try it online!

Port of @loopy walt's answer. Could replace `.MZ` with `S` but that would *technically* make it \\$O(n\log(n))\\$.

### Explanation

```
e.MZml=+eckddQ    # implicitly add dQ to the end of the program
                  # implicitly assign Q = eval(input())
    m        Q    # map the letters of Q to lambda d
      =+eckdd     #   k = k.split(d)[-1] + d
     l            #   length(k)
e.MZ              # get the maximum

```
> 1 votes

# Answer
# Haskell, 146 bytes

```
import Data.Array
f=snd.foldl(\(l,m)(i,c)->
 (l//[(b,max(l!b)(l!c))|b<-['a'..'z']]//[(c,i)],
 max m(i-l!c)))(accumArray(+)0('a','z')[],0).zip[1..]

```

Try it online!
> 0 votes

---
Tags: code-golf, string, restricted-complexity
---