title: A Cat’s Game to Claim

text:
# Question
Title: A Cat’s Game to Claim
## Intro

You like cats. Naturally, you like cat’s games in tic-tac-toe. So, you’ve come up with a little party trick.

You ask someone what square on the board they want you to make a move in. And you ask someone else on which turn they want you to make that move. You also let that person decide whether you play Xs or Os. And with that, you’re off to the races.

You play your sidekick with the side they chose for you. And sure enough, when the turn they chose comes around, you move just in the spot they chose. And from there, you're able to secure a cat's game with your sidekick. (Your sidekick could take advantage of your forced move and beat you, or God forbid they could take the square first, but they're your trusty sidekick after all.) Et voila!

You’re convinced that you can end in a cat’s game no matter what they give you, but you want to make sure. Let’s give you a hand!

## Challenge

Given a move on the tic-tac-toe board and a turn to make the move on, output a tied game where that move was played. A cat's game!

Any input/output to represent the given info and the resulting game is accepted. But here is the convention I’ll use in the examples:

There are 9 squares on a tic-tac-toe boards, and there are 9 turns in a drawn game, because every square must be filled. So my input examples will take a pair of integers 1-9. The first number will represent the turn number and the second number the square on the board to move in. Whether the turn number is even or odd tells you whether you’re playing X or O. My outputs will be the numbers 1-9 printed in a 3×3, representing the placement of the nth move. And the input is marked in parentheses, for easy reading.

Again, you may change the I/O scheme. Your output can, for example, flatten the grid and just return a simple list. This is what almost everyone has chosen, maybe you have another idea! Perhaps a list of numbers indicating the nth move made. And your input can switch the turn and move numbers, or do it entirely differently.

So with this particular I/O scheme, `3 5` represents moving in the 5th square, which is the center, on your 3rd turn. And your turn is odd, so you’re playing as X who is the first/odd player.

This is code-golf, so the shortest code in bytes wins.

## Equivalently

One can frame the problem equivalently: Arrange the numbers 1-9 in a square such that you have no three evens or odds in a row. (With one number’s placement given by the input.) The fact that this can be solved by playing Tic Tac Toe means that this problem can be solved with a greedy algorithm!

## Test Cases

```
>> 3 5

  8  5  7
  9 (3) 2
  6  4  1

```

```
>> 5 3

  9  8 (5)
  2  3  1
  4  7  6

```

```
>> 7 4

  5  4  1
 (7) 6  2
  8  9  3

```

```
>> 1 1

 (1) 2  4
  6  3  5
  7  9  8

```

```
>> 9 9

  4  5  1
  7  6  2
  3  8 (9)

```

P.S. For those wondering about the title, I don’t know how widespread this is, but we always called a draw “a cat’s game”: Wiktionary & Etymology

# Answer
# Jelly, 33 bytes

```
;s3ZFƊ;92149ṃ$s3EƇ
9Œ!ḂÇ$Ðḟ³ị=⁴ƲƇ

```

Try it online!

Outputs *all* valid boards. This is really slow - I can't guarantee it'll complete on TIO; it seems to depend on how lucky I get with CPU allocation. I am also pretty confident this is solvable in like half the bytes.

```
;s3ZFƊ;92149ṃ$s3EƇ  Helper Link; determine if a board is not tied (given a flat list of 0s and 1s)
;                   Append:
 ----Ɗ              - The list,
 s3                 - Sliced into sublists of size 3,
   Z                - Transposed,
    F               - Flattened
      ;             Append:
       92149ṃ$      92149, base decompressed into the list (index 1, 5, 0, 3, 5, 7 - where 0 is the last element)
              s3    Slice into sublists of size 3 (this now has each row, column, and diagonal)
                EƇ  Filter to keep sublists that are all equal (and thus indicate a win)
9Œ!ḂÇ$Ðḟ³ị=⁴ƲƇ      Main Link (dyad); accept x (index) and y (turn)
9Œ!                 All permutations of 9 (implicit range)
     $Ðḟ            Filter; remove all boards where
   Ḃ                % 2 (convert turn numbers to X/O)
    Ç               Call helper link (remove boards that aren't ties)
            ƲƇ      Filter to keep boards where
        ³ị          The element at index (x)
          =⁴        Equals (y)

```
> 5 votes

# Answer
# 05AB1E, 27 bytes

Takes the 0-based index as the first input and the number to place as the second input.

```
9Lœʒ¹èQ}3δôʒyø«yÂ‚€Å\«É€Ëà≠

```

Try it online!

```
9Lœ               # all permutations of [1 .. 9]
   ʒ¹èQ}          # keep a if a[¹] == ²
        3δô       # split each permutation in groups of 3

ʒ                 # keep grids where:
 yø«              #   concatencate the transpose to the grid
    yÂ‚           #   pair the grid and its reverse
       €Å\        #   for each: take the main diagonal; this is the main and anti-diagonal
          «       #   concatenate the diagonals to rows and columns
           É      #   each integer modulo 2
            €Ë    #   for each sublist: are all values equal
              à   #   take the maximum / is any 1?
               ≠  #   boolean negate (!= 1)

```
> 5 votes

# Answer
# JavaScript (ES6),  ~~85~~  82 bytes

Expects `(square)(turn)` and returns a flat array of 9 values. Everything is 0-indexed.

```
s=>n=>[...a=2135+[s-6?408:804]+67].map(x=>s--?((x+=q=n-v&1)%9-n?x:v+q)%9:n,v=a[s])

```

Try it online!

### How?

We are given a target square \\$s\\$ and a turn \\$n\\$, both 0-indexed.

We use the following template by default:

$$\begin{pmatrix}2&1&3\\5&4&0\\8&6&7\end{pmatrix}$$

whose flattened representation is \\$\[2,1,3,5,4,0,8,6,7\]\\$.

But if \\$s=6\\$, we use this one instead where the \\$8\\$ and the \\$4\\$ are swapped:

$$\begin{pmatrix}2&1&3\\5&\color{red}8&0\\\color{red}4&6&7\end{pmatrix}$$

Both templates encode the same mark configuration. Assuming \\$\text{X}\\$ play first, this gives:

$$\begin{pmatrix}\text{X}&\text{O}&\text{O}\\\text{O}&\text{X}&\text{X}\\\text{X}&\text{X}&\text{O}\end{pmatrix}$$

Let \\$v\\$ be the original value stored on the target square.

If \\$n-v\\$ is odd, we increment all squares modulo \\$9\\$ \[1\]. This means that all parities are inverted, except \\$8\\$ which is turned into \\$0\\$ and remains even. That's why we need a slightly different board if the target square is the bottom left one.

Below are the mark configurations after the parity transformation for the default template (left) and the alternate template (right):

$$\begin{pmatrix}\text{O}&\text{X}&\text{X}\\\text{X}&\text{O}&\text{O}\\\text{X}&\text{O}&\text{X}\end{pmatrix} \begin{pmatrix}\text{O}&\text{X}&\text{X}\\\text{X}&\text{X}&\text{O}\\\text{O}&\text{O}&\text{X}\end{pmatrix} $$

At this point, it is guaranteed that:

* the board is valid (i.e. there are five \\$\text{X}\\$ and four \\$\text{O}\\$ and the game is a draw)
* the target square has the correct parity

We can now swap the values of the target square and the square holding \\$n\\$.

---

*\[1\]: Because the board is described as an array of digit characters, the code `(x += q = n - v & 1) % 9` is actually concatenating either \\$0\\$ or \\$1\\$ to `x` and reduces the result modulo \\$9\\$. This gives the expected result because \\$(x \times 10 + k) \bmod 9\\$ = \\$(x + k) \bmod 9\\$ (with \\$k=0\\$ or \\$k=1\\$).*

### Example

For \\$s=1\\$ and \\$n=6\\$:

* we have \\$s\neq 6\\$, so we use the default template
* we have \\$v=1\\$ and \\$n-v=5\\$, so the squares are incremented modulo \\$9\\$
* the square at index \\$3\\$ holds \\$n\\$ after the transformation, so that's the one that is exchanged with the target square

$$\begin{pmatrix}2&1&3\\5&4&0\\8&6&7\end{pmatrix} \rightarrow \begin{pmatrix}3&2&4\\6&5&1\\0&7&8\end{pmatrix} \rightarrow \begin{pmatrix}3&\color{red}6&4\\\color{red}2&5&1\\0&7&8\end{pmatrix} $$
> 5 votes

# Answer
# Jelly, ~~30~~ 27 bytes

```
,UŒDḢ€;;ZḂE€Ẹ
9Œ!aƑ@Ƈs€3ÇÐḟ

```

Try it online!

A pair of links that takes a mask for the answer and returns all possible solutions matching the mask as a list of lists of lists of integers.

## Explanation

### Helper link

Takes a 3x3 grid and checks if any row, column or diagonal has all odd or all even numbers

```
,U            | Pair with copy of grid with each row reversed
  ŒDḢ€        | Main diagonal of each
      ;       | Concatenate to rows
       ;Z     | Concatenate to columns
         Ḃ    | Mod 2
          E€  | Check if each is all equal
            Ẹ | Any

```

### Main link

```
9Œ!           | Permutations of 1..9
   aƑ@Ƈ       | Keep those where the mask AND the permutation equals the mask
       s€3    | Split each into lists length 3
          ÇÐḟ | Keep those where the helper link is false

```
> 4 votes

# Answer
# Charcoal, 56 bytes

```
ＮθＮη⪪⁺1234⁺§⪪657576³θ98³Ｗ﹪⁻§ＫＡηθ²⟲Ｗ⁻§ＫＡηθＵＭＫＡＩ⎇‹κ3⁻χκ⁻κ²

```

Try it online! Link is to verbose version of code. Takes the square number as 0-indexed but the turn number as 1-indexed (could readily be made 0-indexed though). Explanation: Excluding rotations and reflections, and assuming `X` goes first, there are only three final positions:

```
XOX XOX XXO
OXX OOX OOX
OXO XXO XXO

```

It just remains to number and/or rotate and/or reflect one of these positions in such a way that the desired play appears on the desired turn.

```
ＮθＮη

```

Input the 0-indexed square and the 1-indexed turn.

```
⪪⁺1234⁺§⪪657576³θ98³

```

If the turn number is even then build up the string `123465798` (corresponding to the first pattern) otherwise build up the string `123457698` (corresponding to the second pattern; I don't use the third pattern). Split it into a 3×3 square.

```
Ｗ﹪⁻§ＫＡηθ²⟲

```

Rotate the square until the number under the desired square has the same parity as the desired turn.

```
Ｗ⁻§ＫＡηθ

```

Repeat until the number under the desired square is the desired turn...

```
ＵＭＫＡＩ⎇‹κ3⁻χκ⁻κ²

```

... cyclically shuffle `X`'s turns and (separately) `O`'s turns.
> 4 votes

# Answer
# , 71 bytes

```
[:(([:*/3>1#.2|],|:,#:@273 84#,)"2#])a 3 3&$"1@#~]=[{"1 a=:(i.@!A.i.)@9

```

Try it online!

Method is straightforward and similar to other answers: Generate all 9! boards, then filter by those that have the move in the required position, then filter by cats games.
> 2 votes

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

```
s=>t=>(g=n=>n[1]?n.flatMap(e=>g(n.filter(h=>h!=e)).map(l=>[e,...l])):n)([...'123456789']).filter(e=>e[s-1]==t&'012A345A678A048A246A036A147A258'.split`A`.every(T=>[...T].some(j=>e[j]%2!=e[T[0]]%2)))

```

Try it online!

Outputs **all valid boards**. Although, on TIO, I have only `console.log`ged the first 100 boards in a human-readable format. I have also, of course, displayed the number of valid boards using `.length`, 4608 in the case of the sample input.

Feels too long.

## How?

The helper `g` outputs all permutations of a list. Initial call is with the list `[...'123456789']` which spreads the string out. What `g` does is self-explanatory: if n has a second element, map each element of `n` to that element plus a recursive call to `g` with the remaining elements, and otherwise return `n`.

Then filters based on whether the input move is at the right spot and if, for every three-character string in the split string, no three odds or evens are in a row.
> 1 votes

---
Tags: code-golf, array, grid, game
---


title: Implement Fix2 combinator

text:
# Question
Title: Implement Fix2 combinator
## Background

The fixed-point combinator \\$\textsf{fix}\\$ is a higher-order function that computes the fixed point of the given function.

$$\textsf{fix}\ f = f\ (\textsf{fix}\ f)$$

In terms of programming, it is used to implement recursion in lambda calculus, where the function body does not normally have access to its own name. A common example is recursive factorial (written in Haskell-like syntax). Observe how the use of `fix` "unknots" the recursive call of `fac`.

```
fix f = f (fix f)
fac = fix facFix where
  facFix fac' n =
    if n == 0
    then 1
    else fac' (n - 1) * n
-- which is equivalent to the following recursive function:
fac n =
  if n == 0
  then 1
  else fac (n - 1) * n

```

Now, have you ever thought about how you would do the same for *mutually* recursive functions? This article describes the fully general \\$\textsf{Y}^\*\\$ combinator, which takes a list (or equivalent) of unknotted definitions and returns the list of mutually recursive ("knotted") functions. This challenge will focus on a simpler situation with exactly 2 mutually recursive functions; the respective combinator will be called `fix2` throughout this challenge.

A common example of mutual recursion is `even` and `odd` defined like this:

```
even n =
  if n == 0
  then true
  else odd (n - 1)
odd n =
  if n == 0
  then false
  else even (n - 1)

```

The unknotted version of these would look like this (note that mutually recursive definitions should have access to *every single function* being defined):

```
evenFix (even, odd) n =
  if n == 0
  then true
  else odd (n - 1)
oddFix (even, odd) n =
  if n == 0
  then false
  else even (n - 1)

```

Then we can knot the two definitions using `fix2` to get the recursive `even` and `odd` back:

```
fix2 (a, b) = fix (\self -> (a self, b self))
  where fix f = f (fix f)
let (even, odd) = fix2 (evenFix, oddFix)

```

## Challenge

Implement `fix2`. To be more precise, write a function or program that takes two unknotted black-box functions `fFix` and `gFix` and a non-negative integer `n`, and outputs the two results `(f(n), g(n))` of the knotted equivalents `f` and `g`. Each `f` and `g` is guaranteed to be a function that takes and returns a non-negative integer.

You can choose how `fFix` and `gFix` (and also `fix2`) will take their arguments (curried or not). It is recommended to demonstrate how the even-odd example works with your implementation of `fix2`.

Standard rules apply. The shortest code in bytes wins.

# Answer
# Haskell, 14 bytes

```
f l=map($f l)l

```

Takes a two-element list of functions that take two-element lists, and returns a two-element list.

Try it online!
> 7 votes

# Answer
# Java (JDK), 137 bytes

```
interface L{C g();}interface C{int a(int x);}interface P{C a(L[]l);static L[]z(P[]p){return new L[]{()->p[0].a(z(p)),()->p[1].a(z(p))};}}

```

Try it online!

I was actually hoping this would turn out longer so it'd be a better shitpost.

The method to call is `P::z`, which takes two-element array of `P`s and returns a two-element array of `L`'s. To obtain a completed function (`C`) from an `L`, one has to call `L::g` on it. `P` represents a function to be fixed, and its `a` method takes a two-element array of `L`s to prevent evaluation immediately, returning a `C` that represents a complete function that an `int` `n` can be applied to.
> 3 votes

# Answer
# Scala, 82 bytes

```
type R=Int=>Int
type T=(=>Stream[R])=>R
def>(f:Stream[T]):Stream[R]=f.map(_(>(f)))

```

Try it in Scastie!

This is very similar to Anders Kaseorg's answer, but it takes a lot more effort to avoid stack overflows and infinite recursion in Scala because it doesn't have lazy evaluation by default.

```
//The result type, a complete function
type R=Int=>Int
//A function that needs to be fixed. Takes a by-name parameter, a lazily evaluated
//list that contains complete functions, and returns a complete function
type T=(=>Stream[R])=>R
//The meat of the answer. This is practically the same as the Haskell answer.
def>(f:Stream[T]): Stream[R] =
  f.map(    //For every incomplete function in f
   _(       //apply it to
    >(f)))  //the result of applying > on f again (not immediately evaluated)

```

A possible implementation of `evenFix` and `oddFix`:

```
val evenFix: T = fns => n => if (n == 0) 1 else fns(1)(n - 1)
val oddFix: T = fns => n => if (n == 0) 0 else fns(0)(n - 1)

```

Note that since `fns` is a by-name parameter, using it more than once causes it to be evaluated again. It can also not be pattern-matched on, since that causes it to be evaluated.
> 2 votes

---
Tags: code-golf, functional-programming, lambda-calculus
---


title: Visualize a Risky program

text:
# Question
Title: Visualize a Risky program
Risky is a new language of mine, which features an interesting form of tacit programming. In this challenge, you'll take a Risky program as input, and visualize the parsing.

No knowledge of Risky is needed for this challenge, but it's a pretty interesting language so I'd recommend trying it :p.

## Task

Risky's parsing is based purely on the length of the program. It follows three rules:

1. If the program consists of one operator, it is parsed as a nilad
2. If the program consists of an even number of operators, the first operator is parsed as a monad and the rest is parsed as its argument
3. Otherwise, the middle operator is parsed as a dyad, and both sides are parsed as arguments

This is recursive; the argument(s) to a monad or dyad are parsed as if they are their own programs.

This forms a tree of operators. For example, the program `-1+!2` would look roughly like this:

```
  +
 / \
-   !
|   |
1   2

```

Your task will be to represent this by offsetting the operators lower in the tree, showing the structure of the program. For example:

```
  +
-  !
 1  2

```

All of the operators stay in order, but are vertically offset in order to show the structure.

## Input

Input will consist of a string of operators. If you want, you can assume the input doesn't contain any invalid Risky operators, though it would not affect the parsing.

## Output

You can output a visualization of the program in one of four ways:

**Top-to-bottom:**

```
      +
-      [
   +      ?
 !  !   2  0
  1  }   ]  [

```

**Bottom-to-top:**

```
  1  }   ]  [
 !  !   2  0
   +      ?
-      [
      +

```

**Left-to-right:**

(Using a shorter program for the next two to save space)

```
   2
  ?
 +
   1
  [
!

```

**Right-to-left:**

```
   !
 [
1
  +
 ?
2

```

Both LTR are RTL can be flipped upside down if you prefer.

## Test cases

Note that the above examples can be used as more complicated test cases. For the top/bottom ones, `-!1+!}+[2]?0[` is the program shown. For the rest, it's `![1+?2`.

**Program:** `1`

```
1

```

**Program:** `-1`

```
-
 1

```

(Top-to-bottom)

**Program:** `1+1`

```
1 1
 +

```

(Bottom-to-top)

**Progam:** `-1+2`

```
  1
 +
  2
-

```

(Left-to-right)

**Program:** `!!!!!`

```
 !
!
  !
 !
!

```

(Right-to-left)

## Other

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

# Answer
# APL (Dyalog Extended), 35 bytes

```
↑{⊃{0~⍨⍺-1-∊1⍵0⍵}/-⌽⍬⊂⍛,1↓⊤1+≢⍵}↑¨⊢

```

Try it online!

Takes a string and puts each command on its own line top to bottom, indenting from left to right.

## The algorithm

Given the length of the input `n`, the indentation pattern (the length of each line) looks like the following:

```
f(1) = [1]
f(2n + 2) = let prev = f(n) in [1] ++ (2+prev) ++ [2] ++ (2+prev)
f(2n + 1) = let prev = f(n) in (1+prev) ++ [1] ++ (1+prev)

```

If we add 1 to the input, the recursive formula becomes nicer (with adjusting the base case):

```
g(1) = []
g(2n + 1) = let prev = g(n) in [1] ++ (2+prev) ++ [2] ++ (2+prev)
g(2n) = let prev = g(n) in (1+prev) ++ [1] ++ (1+prev)

```

which means we can use single reduction on the binary representation to get the job done.

## The code

```
↑{⊃{0~⍨⍺-1-∊1⍵0⍵}/-⌽⍬⊂⍛,1↓⊤1+≢⍵}↑¨⊢  Input: s

⊤1+≢⍵    Binary representation of 1+n
⌽⍬⊂⍛,1↓  Remove leading 1, prepend an empty list, and reverse
-        Negate the bits (for golfing purposes)
⊃{...}/  Reduce from right to left... (⍵: prev list, ⍺: next bit)
  ∊1⍵0⍵    Shorthand for 1,⍵,0,⍵
  ⍺-1-     Add ⍺-1 (-1 if zero bit, -2 if one bit)
  0~⍨      Remove zero if present
           which gives -1,(⍵-2),-2,(⍵-2) for 1 bit and
           (⍵-1),-1,(⍵-1) for 0 bit

 {...}     Compute negative padded lengths
↑     ↑¨⊢  Pad each char on the left side and rectify

```
> 10 votes

# Answer
# , 67 bytes

```
g=:(0,1+$:@<:)`([:(,0,])1+$:@<.@-:)`0:@.(=&1+2&|)
f=:' '&,.#"1~1,.~g@#

```

Try it online!

This produces an upside-down left-to-right tree, which should be valid per the comments. For example, `f '-1+!2'` produces:

```
 -
  1
+
 !
  2

```

## the idea

* First notice the numerical pattern in the number of space indents:

```
1 -> 0
2 -> 0 1
3 -> 1 0 1
4 -> 0 2 1 2
5 -> 1 2 0 1 2
6 -> 0 2 3 1 2 3
7 -> 2 1 2 0 2 1 2

```
* Then notice that all the heavy lifting can be put into a recursive function that does nothing but implement the function described by the above table, since it's easier to work with integers than strings. This is `g`.
* Zip a space and the input like so:

```
 -
 1
 +
 !
 2

```
* Finally, use the output of `g` and J's copy verb `#` to expand the spaces of that zip as needed.
> 8 votes

# Answer
# Jelly, 32 bytes

```
⁹ð:2ß‘},`j⁹ð’ß‘}⁹;ðḂ?Ị?
Lç0⁶ẋż¹Y

```

Try it online!

-2 bytes thanks to caird coinheringaahing

This uses essentially the same approach as Jonah, so upvote their answer as well. I came up with this solution independently, but Jonah's answer helped me consolidate a similar idea (to generate the indent array and convert that to indentation), and although I pretty much knew how I wanted to do it already, it helped me see that it was the correct approach and how to go about it.

```
⁹ð:2ß‘},`j⁹ð’ß‘}⁹;ðḂ?Ị?   Helper Link (dyad); given x and y, return the length x indentation array with minimum indentation y
                     Ị?   If x is insignificant (abs(x) <= 1)
⁹                         Return just y
                   Ḃ?     Otherwise, if x is odd (x % 2)
 ð:2ß‘},`j⁹ð              Dyadic chain for odd case:
  :2                      - floor divide by 2
    ß‘}                   - recursively apply this function to floor(x / 2) and (y + 1)
       ,`                 - pair that result with itself (exploit symmetry)
         j⁹               - join on y
           ð’ß‘}⁹;ð       Otherwise, if x is even, then dyadic chain for even case:
            ’             - decrement x
             ß‘}          - apply this link to (x - 1) and (y + 1)
                ⁹;        - prepend y
Lç0⁶ẋż¹Y                  Main Link (monad)
L                         Length of the input
 ç0                       Apply the helper link to that (x) and 0 (y)
   ⁶ẋ                     Return a list of whitespace, each row having number of spaces equal to the indentation level
     ż                    Zip with / interleave
      ¹                   (identity is applied to the right argument of the above to prevent the 2,1 chain with `Y`)
       Y                  Join on newlines

```
> 6 votes

# Answer
# 05AB1E, ~~26~~ 25 bytes

A port of Jonah's J answer.

-1 byte thanks to Kevin Cruijssen!

```
S¯¸λNÈi>0šë0N2÷₅>.ø]Igèú»

```

Try it online!

```
S                     # split input into list of characters
 ¯¸                   # push [[]]
   λ          ]       # starting with a(0)=[], calculate a(n) for n=0,1,... according to:
    NÈi               #   if n is even:
       >              #     each value of a(n-1) incremented by 1
        0š            #     prepend a 0
      ë               #   else:
       0              #     push a 0
        N2÷           #     floor(n/2)
           ₅          #     a(floor(n/2))
            .ø        #     surround the 0 with a(floor(n/2))
               Ig     # push the length of the input()
                 è    # index into the infinite list of indentations
                  ú   # pad each character of the input with the right number of spaces
                   »  # join by newlines

```
> 3 votes

# Answer
# Charcoal, ~~34~~ 33 bytes

```
ＦΦ↨⊕Ｌθ²κ≔⁺…⟦¹⟧ι⁺⊕ι⁺⁺υ⟦⁰⟧υυＥυ◧§θκι

```

Try it online! Link is to verbose version of code. Explanation: Based on @Bubbler's answer, so prints downwards indenting from left to right.

```
ＦΦ↨⊕Ｌθ²κ

```

Take the length of the input plus 1, convert to binary, and loop over the bits after the first.

```
≔⁺…⟦¹⟧ι⁺⊕ι⁺⁺υ⟦⁰⟧υυ

```

Concatenate two copies of the current list (predefined to be the empty list) together with `[0]` in between, then add 1 more than the bit to all the elements, then concatenate `[1]` to the beginning of the list if the bit is `1`, and save that as the current list.

```
Ｅυ◧§θκι

```

Pad each element of the input according to the calculated indentation.
> 3 votes

# Answer
# Haskell, 97 bytes

```
f x|n<-length x,odd n,(p,q:r)<-splitAt(n`div`2)x=g p++[q]:g r
f(x:y)=[x]:g y
f[]=[]
g=map(' ':).f

```

Try it online!

Defines `f :: String -> [String]`. Upside-down left-to-right output.
> 2 votes

# Answer
# JavaScript (V8), 223 bytes

```
f=(c,d=(s,x=0,y=0,u=s.substr.bind(s),l=s.length,h=l/2|0)=>l==1?{[x]:y}:l%2==0?{[x]:y,...d(u(1),x+1,y+1)}:{[x+h]:y,...d(u(0,h),x,++y),...d(u(++h),x+h,y)},r=d(c))=>Object.entries(r).map(k=>" ".repeat(k[1])+c[k[0]]).join("\n")

```

Try it online!

---

Maps the input source into a lookup of token index and indentation amount, then transforms it into a proper string in the inverted left-to-right format.

Indented:

```
f = (
    c,
    // Helper method that calculates the indentation.
    d = (s, x = 0, y = 0, u = s.substr.bind(s), l = s.length, h = l / 2 | 0) =>
        l == 1
            // Case 1: Nilad
            ? { [x]: y }
            : l % 2 == 0
                // Case 2: Monad + Arguments
                ? { [x]: y, ...d(u(1), x + 1, y + 1) }
                // Case 3: Dyad
                : {
                    [x + h]: y,
                    ...d(u(0, h), x, y + 1),
                    ...d(u(h + 1), x + h + 1, y + 1),
                },
    r = d(c)
) =>
    // We take advantage of the fact that the object entries are automatically sorted.
    Object.entries(r)
        .map((k) => " ".repeat(k[1]) + c[k[0]])
        .join("\n");

```
> 1 votes

# Answer
# JavaScript (V8), ~~162~~ 157 bytes

```
d=>(j=(r,b="")=>r.map(o=>o.map?j(o,b+" "):b+o).join`
`)((p=(r,x=r.length)=>x>1?x%2?[p(r.slice(0,z=x/2)),r[z|0],p(r.slice(z+1))]:[r[0],p(r.slice(1))]:[r])(d))

```

Try it online!

**Explanation:**

Parses using recursion, and puts arguments into arrays. Then, it takes the result, and recursively indents anything in an array. Left-to-right, upside-down.
> 1 votes

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


title: Is there a left-right connection?

text:
# Question
Title: Is there a left-right connection?
## Task

Given a square array of 0s and 1s, determine whether or not there exists a path of 1s connecting the leftmost and rightmost columns. A path can take steps of one unit up, down, left or right, but not diagonally. Every symbol on the path must be a 1, and it must start somewhere in the first column and end somewhere in the last column.

Shortest code in each language wins.

## Examples

```
000
111   ->  True
111

110
110   ->  False
110

101
010   ->  False
101

0     ->  False

1     ->  True

11110
00010
01110 ->  True
01000
01111

11110
00010
01100 ->  False
01000
01111

```

## Notes

The array may be represented in any reasonable form, such as a list of lists `[[0,0,0],[1,1,1],[1,1,1]]` or a string `'000 111 111'`. Optionally it can be in transposed form (so that the roles of rows and columns are exchanged); equivalently the code can instead determine whether there is a top-bottom connection. Any two distinct symbols can be used in place of 0 and 1. The output can be in any truthy/falsy form.

# Answer
> 13 votes
# MATLAB/Octave, ~~115~~ ~~109~~ 98\* bytes

*-6 bytes thanks to Luis Mendo*
*-7 bytes thanks to Luis Mendo*

```
function p=f(A)
B=A;B(:,2:end)=0;for k=1:nnz(A)
B=conv2(B,mod(magic(3),2),'same').*A;end
p=any(B);

```

Try it online!
(`end` keyword is in footer because it's not required when you define the function in a file)

Takes binary array, outputs:

* *truthy* value as vector full of logical ones
* *falsy* value as vector having some logical zeros
Such unconsistent *falsy* was suggested by Luis Mendo and confirmed as valid by as aeh5040.

For consistent true/false logical output replace `any(B)` with `all(any(B))`.

\*for MATLAB it's possible to skim 3 bytes by replacing `'same'` with `'s'`.

#### Ungolfed:

```
function path = f(A)

B = A;                  % copy of A
B(:, 2:end) = 0;        % zero everything besides 1st column

mask = mod(magic(3),2); % mask for making "steps"
                        % equal to: [0 1 0
                        %            1 1 1
                        %            0 1 0];

for k=1:nnz(A)          % max number of necessary steps is amount of 1s in A
  % uses 2D convolution of B with m, takes only central part of size of B
  B = conv2(B,mask,'same');  % makes "step" in every direction
  B = B.*A;                  % filters only valid steps
end

path = any(B); % check if each column has any value != 0
      % if returned vector is full of 1s each column contains nonzero value
      % which mean there is a path between both sides

end

```

#### Explaination

###### How 2D convolution works?

If we have array like so:

```
1 1 0 0 0
0 0 0 1 0
0 0 0 0 0

```

and a mask

```
0 1 0
1 1 1
0 1 0

```

we can imagine convolution of array with mask as taking a mask and placing it on top (so that position of corner is the same) of every cell of array and multiplying it with value of that cell - such operation for one cell gives us one array. And then we sum all of the arrays. In our example:

```
1 0 0 0 0         0 1 0 0 0         0 0 0 0 0         1 1 0 0 0
0 0 0 0 0    +    0 0 0 0 0    +    0 0 0 1 0    =    0 0 0 1 0
0 0 0 0 0         0 0 0 0 0         0 0 0 0 0         0 0 0 0 0
    |                 |                 |                 |
    V                 V                 V                 V
0 1 0 0 0 0 0     0 0 1 0 0 0 0     0 0 0 0 0 0 0     0 1 1 0 0 0 0
1 1 1 0 0 0 0     0 1 1 1 0 0 0     0 0 0 0 1 0 0     1 2 2 1 1 0 0
0 1 0 0 0 0 0  +  0 0 1 0 0 0 0  +  0 0 0 1 1 1 0  =  0 1 1 1 1 1 0
0 0 0 0 0 0 0     0 0 0 0 0 0 0     0 0 0 0 1 0 0     0 0 0 0 1 0 0
0 0 0 0 0 0 0     0 0 0 0 0 0 0     0 0 0 0 0 0 0     0 0 0 0 0 0 0

```

Also, in our case because we were using argument `'same'` we were taking only "central" part of result, so because mask was 3x3 we need to cut off sum of 2 columns and 2 rows from the result. To make it even we're cutting first and last rows and are left with:

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

```

###### How we are making "steps"?

Having our input array:

```
1 1 1 1 0
0 0 0 1 0
0 1 1 1 0
0 1 0 0 0
0 1 1 1 1

```

We're taking first column:

```
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

```

then by convolution with our "step" pattern:

```
0 1 0
1 1 1
0 1 0

```

we're selecting cells where we could make step from all current/past positions:

```
1 1 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

```

but since we only can move where 1s are in input array we filter valid positions by multiplying arrays elementwise:

```
1 1 0 0 0         1 1 1 1 0        1 1 0 0 0
1 0 0 0 0         0 0 0 1 0        0 0 0 0 0
0 0 0 0 0   .*    0 1 1 1 0    =   0 0 0 0 0
0 0 0 0 0         0 1 0 0 0        0 0 0 0 0
0 0 0 0 0         0 1 1 1 1        0 0 0 0 0

```

and so we made 1st "step". Then again - convolution to select positions where we can move and filter out result:

```
1 1 0 0 0             2 2 1 0 0                2 2 1 0 0
0 0 0 0 0 convolution 1 1 0 0 0 multiplication 0 0 0 0 0
0 0 0 0 0     ==>     0 0 0 0 0      ==>       0 0 0 0 0
0 0 0 0 0    steps    0 0 0 0 0    filtering   0 0 0 0 0
0 0 0 0 0             0 0 0 0 0                0 0 0 0 0

```

Notice we're getting values other than 1, but that doesn't matter - positive numbers will produce only more positive numbers, so we care only if something is 0 or something greater. So, we continue, next step:

```
2 2 1 0 0     4 5 3 1 0     4 5 3 1 0
0 0 0 0 0     2 2 1 0 0     0 0 0 0 0
0 0 0 0 0 ==> 0 0 0 0 0 ==> 0 0 0 0 0
0 0 0 0 0     0 0 0 0 0     0 0 0 0 0
0 0 0 0 0     0 0 0 0 0     0 0 0 0 0

```

and so on, we continue making steps, finally reaching such state:

```
15511   26324   29964   27016       0
    0       0       0   20240       0
    0    3080    6853   12804       0
    0    1143       0       0       0
    0     340      77      12       1

```

with 1 in final column, meaning we've reached the right side.

# Answer
> 7 votes
# , 48 bytes

```
_1{0{1([:+./ .*^:_~1>:|@-/~)@($j./@#:I.@,)@,~1,]

```

Try it online!

Takes a binary matrix, and checks for a top-to-bottom path. Hence, the input pre-processor transposes the test cases.

## the idea

* Add a row of ones to the top and bottom.
* Convert all ones to coordinates, encoded as complex numbers.
* Create an adjacency matrix for those points, with adjacency defined as "euclidean distance is \<= 1".
* Self "multiply" that matrix to a fixed point, where the addition part of the matrix multiplication is boolean "or".
* The top row will now be connected to the bottom row iff the upper right entry in the matrix is a 1.
* So return that entry.

# Answer
> 6 votes
# , ~~138...~~ 118 bytes

-9 bytes thanks to Dominic van Essen.

```
function(m,k=nrow(m),r=m,`/`=cbind){r[,-1]=0
for(i in m)r=r|m&r[,-1]/0+0/r[,-k]+t(t(r[-1,])/0+0/t(r[-k,]))
any(r[,k])}

```

Try it online!

At first, the matrix `r` contains only the `1`s of the first column of the input `m`; all other entries are `0`.

At iteration `i` of the loop, entries which are attainable in at most `i` steps become non-0. This is done by incrementing the cells for which both of these conditions hold: (1) the value is 1 in `m` and (2) the value of one of its neighbours is non-0 in `r`. A less golfy but more readable version of the command in the for loop would be

```
r = r | ( m & (cbind(r[,-1],0) | cbind(0,r[,-k]) | rbind(r[-1,],0) | rbind(0,r[-k,])))

```

Note that using `+` instead of some of the `|` allows to omit the brackets, thanks to R's operator precedence (`+` before `&` before `|`).

The length of the path to reach the rightmost column is bounded by `k^2`, where `k` is the side length of the input. After `k^2` iterations (i.e. the number of elements of `m`), we check whether there any non-0 values in the rightmost column of `r`.

# Answer
> 6 votes
# Haskell, 96 bytes

```
e=[]:e
(2:l)%1=2:2:l
l%x=x:l
h a=any(>=[2])$foldl(zipWith(%))e`iterate`map(2:)a!!(sum(2<$a)^2+2)

```

Try it online!

Similarly to other answers, this "flood-fills" the input with `2`s and checks if we reach the right edge.

`l%x` acts like `x:l`, but if `l` starts with a `2` and `x` is `1`, then `x` is replaced by a `2` also.

`foldl(zipWith(%))e` is then a function that rotates a list of rows 90° while making 2s "spread into" 1s, using our infectious flipped-cons operator. This is based on the shorter transpose trick: Using `foldl` instead of `foldr` rotates the array instead of transposing it.

We start from `map(2:)a` (append a column of 2s on the left), and apply `foldl(zipWith(%))e` \\$4\\,\mathrm{length}(a)^2+2\\$ times. This is enough iterations to flood-fill even the twistiest of paths, and also turns the input upside-down. Then we check if any upside-down row starts with a two using `any(>=[2])`.

The \\$4\\,\mathrm{length}(a)\\$ part of the iteration count is computed as \\$\left( \sum\_{x \in a} 2 \right)^2\\$.

Thanks to xnor for contributing lots of good ideas!

# Answer
> 3 votes
# Jelly, 28 bytes

```
+þ2ŒRBU¤ẎQfðƬṪ
ŒṪḷ/Ị$Ƈç$Ḣ€iL

```

Try it online!

-2 bytes thanks to caird coinheringaahing
-2 bytes using transposed form

Returns 0 for falsy and non-zero for truthy

Uses the exact same breadth-first-fill helper link as my answer to "But, Is It Art?"

```
+þ2ŒRBU¤ẎQfðƬṪ     Helper Link; given a list of starting coordinates on the left and a list of accessible coordinates on the right, fill
           ðƬ      Repeat until results are no longer unique
+þ                 Product table by addition of the current coordinates and
  2ŒRBU¤           As a nilad:
  2ŒR              - [-2, -1, 0, 1, 2]
     B             - Binary: [[-1, 0], [-1], [0], [1], [1, 0]]
      U            - Reverse Each: [[0, -1], [-1], [0], [1], [0, 1]]
        Ẏ          Tighten; dump the product table into a flat list of coordinates
         Q         Remove duplicates
          f        Filter to only keep valid coordinates (based on the right side)
             Ṫ     Tail; get the last list (the breadth-first-filled list of coordinates)
ŒṪḷ/Ị$Ƈç$Ḣ€iL      Main Link; take a binary matrix
ŒṪ                 Convert to a list of filled coordinates
        $          Call this monad on this list of coordinates:
       ç           - Call the helper link, with the following on the left:
     $Ƈ              - The list of coordinates, filtered to keep elements where:
  ḷ/                   - The first element (the row coordinate)
    Ị                  - Is insignificant (in inclusive range [-1, 1])
         Ḣ€        Get the row of each filled coordinate
           i       Index of (0 if not found)
             L     The length of the matrix (height)

```

Essentially, this just starts at every position in the top row, fills, and sees if it reaches the bottom row.

# Answer
> 2 votes
# JavaScript (ES7),  ~~103 101~~  94 bytes

Expects a transposed binary matrix. Returns **0** or **1**.

```
f=(m,X,Y=-1)=>!m[Y+1]|m.some((r,y)=>r.some((v,x)=>v&&(X-x)**2+(Y-y)**2<2|!y&&--r[x]|f(m,x,y)))

```

Try it online!

### Commented

```
f = (                  // f is a recursive function taking:
  m,                   //   m[] = input matrix
  X, Y = -1            //   (X, Y) = current position, starting with
) =>                   //            X undefined and Y = -1
!m[Y + 1] |            // success if we've reached the last row
m.some((r, y) =>       // for each row r[] at position y in m[]:
  r.some((v, x) =>     //   for each value v at position x in r[]:
    v &&               //     abort if v = 0
    (X - x) ** 2 +     //     if the squared distance between
    (Y - y) ** 2 < 2 | //     (x, y) and (X, Y) is less than 2
    !y                 //     or y = 0 (see the note below):
    &&                 //
      --r[x] |         //       clear r[x]
      f(m, x, y)       //       do a recursive call
  )                    //   end of inner some()
)                      // end of outer some()

```

**Note**: Any cell at \\$(x,0)\\$ with a \\$1\\$ on it is considered to be a valid destination square, no matter what the current position is, which may result in an invalid move. But if we start a path from \\$(x\_0,0)\\$, suddenly jump to \\$(x\_1,0)\\$ and find an apparently invalid solution, it just means that we could have started from \\$(x\_1,0)\\$ and find a valid solution.

# Answer
> 2 votes
# 05AB1E, ~~42~~ 36 bytes

A slower ~~but maybe golfable?~~ version. After looking at Jonah's J answer I was able to remove 6 bytes.

```
gÅ1¸.øεā*0K€¸<Nδš}€`DδαO2‹DvDδ*O}нθĀ

```

Try it online!

---

# 05AB1E, 42 bytes

A lot of this is similar to this recent answer of mine. Tests for a top-bottom connection.

```
εā*0K€¸<Nδš}D€gU€`DδαO2‹DvDδ*O}Xθ.£øOXн£OĀ

```

Try it online! Header transposes the input to test left-right connections.

This is quite long because of missing builtins for *all indices of* and matrix operations. High-level explanation:

`εā*0K€¸<Nδš}` get all indices of 1's.
`€gU` store the number of 1's in each row in variable `X`.
`DδαO2‹` calculates a adjacency matrix \\$A\\$ of all 1's.
`DvDδ*O}` squares the matrix \\$k=\operatorname{len}(A)\\$ times.
`Xθ.£øOXн£OĀ` checks if there is a positive integer in the top left submatrix of \\$A^{2k}\\$ of size \\$c\_1\times c\_n\\$, where \\$c\_i\\$ is the number of 1's in row \\$i\\$.

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

Uses the same method as Jonah's J answer. Full program that detects top-bottom connections.

```
⊃⌽⌈.×⍣≡⍨2>+/¨|∘.-⍨⍸1⍪⎕⍪1

```

Try it online! Footer transposes inputs.

```
                   1⍪⎕⍪1 ⍝ the input matrix with additional rows of 1's at the top and bottom
                  ⍸      ⍝ get all 2d indices of 1's
             |∘.-⍨       ⍝ table of absoulute element-wise differences
          +/¨            ⍝ sum each pair of absoulte differences
        2>               ⍝ values of 1 or 0 mark adjacent (or same) 1's
  ⌈.×⍣≡⍨                 ⍝ "matrix multiplication" until convergence. Instead of summing values we take the maximum to keep everything as 0 or 1
 ⌽                       ⍝ reverse each row of the matrix
⊃                        ⍝ take the very first number of the matrix

```

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

```
Max[Intersection@@MorphologicalComponents[#,CornerNeighbors->False][[{1,-1}]]]>0&

```

Solves the transpose problem, looking for connections between the top and bottom rows. The long-named overkill builtin `MorphologicalComponents[#,CornerNeighbors->False]` changes the `1`s in the input to different integers shared by connected groupings (where we must override the default that diagonal connections count); then we simply look to see if there's a positive integer in common in the first and last rows. Someone should translate this into Sledgehammer....

# Answer
> 2 votes
# MATL, ~~21~~ ~~20~~ ~~19~~ 18 bytes

*Translation of @elementiro's MATLAB/Octave answer, with small modifications*.

The input is a binary matrix (using `;` as row separator).

The output is either a row vector with all entries eqwual to `1` (which is truthy), or a row vector with at least one entry eqwual to `0` (which is falsy). The footer contains the truthiness/falsihood test.

```
O4LZ(Gz:"2Y6Z+G*]a

```

Try it online! Or verify all test cases.

# Answer
> 2 votes
# Python 3, ~~135 127~~ 123 bytes

Answering my own question since there is no python solution yet. Expects a transposed matrix. Strongly inspired by Lynn's rotation method. I'm sure there is room for improvement!

```
def f(x):
 x+=[[3]*len(x)]
 for _ in x*4*len(x):x=[map(lambda a,b:a|a*2&b,y,(0,*y))for y in zip(*x)][::-1]
 return 3in x[0]

```

Try it online!

# Answer
> 1 votes
# Jelly, 20 bytes

```
ḣ1ŒṪạÆịỊẸʋƇ@ƬŒṪ=LḄỊȦ

```

A monadic Link that accepts a list of the columns (i.e. transposed version of the OP's examples) and yields `1` (no connection) or `0` (connection).

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

### How?

Builds up all coordinates reachable from the first column by repeatedly adding those within a unit circle of any found so far, then checks if any of these coordinates is in the final column by virtue of their column coordinate being equal to the total number of columns.

```
ḣ1ŒṪạÆịỊẸʋƇ@ƬŒṪ=LḄỊȦ - Link: List of lists, Columns
ḣ1                   - head to index 1 (first column wrapped in a list)
  ŒṪ                 - multi-dimensional truthy indices (of that) -> X
             ŒṪ      - multi-dimensional truthy indices (of Columns) -> Y
            Ƭ        - start with X and collect until no change, applying:
           @         -   with swapped arguments:
          Ƈ          -     filter keep those (coordinates, c, in Y) for which:
         ʋ           -       last four links as a dyad - f(c,X):
    ạ                -         (c) absolute diference (X) (vectorises)
     Æị              -         from [Real, imaginary] to complex (vectorises)
       Ị             -         absolute value <= 1? (vectorises)
        Ẹ            -         any?
               =L    - equals length(M)? (vectorises)
                 Ḅ   - convert from binary (vectorises)
                  Ị  - absolute value <= 1? (vectorises)
                   Ȧ - any and all? (0 if 0 present when flattened else 1)

```

# Answer
> 1 votes
# Perl 5 (`-p`), 65 bytes

```
/
/;$,="(.{@-})?";s/^1/#/gm;1while s/#$,\K1|1(?=$,#)/#/s;$_=/#$/m

```

Try it online!

`-00l012` options are just used to run all tests and to print result.

`/\n/` to match first end of line, to get the width

`$,="(.{@-})?";` to define the variable `$,` with expression that matches the line width characters (used to match a character above or below another

`s/^1/#/gm` to replace all `1` in the first column with `#`

`1while s/#$,\K1|1(?=$,#)/#/s` while a `1` is found (below, on the right, on the left or above a `#`, replace with `#`

`$_=/#$/m` result is: is there a `#` in the last column

# Answer
> 1 votes
# Charcoal, 25 bytes

```
ＷＳ⊞υ⭆⪫11ι℅¬Ｉκ⪫υ¶←¤-Ｊ⁰¦⁰Ｔ¹

```

Try it online! Link is to verbose version of code. Takes input as a newline-terminated list of strings (-3 bytes to take a input as a cumbersome array of strings: Try it online!) and outputs a Charcoal boolean, i.e. `-` if a path exists, blank if not. Explanation:

```
ＷＳ⊞υ⭆⪫11ι℅¬Ｉκ

```

Wrap each line in `1`s. This changes the condition to requiring a path from the top left to the bottom right corner. The `1`s and `0`s are then changed to null and non-null bytes.

```
⪫υ¶

```

Print the non-null bytes. (Null bytes erase rather than printing.)

Move to the bottom right corner.

```
¤-

```

Try to fill with `-`s.

```
Ｊ⁰¦⁰Ｔ¹

```

Delete everything except the top right corner, which will have been filled with `-` if there is a path and left erased if not.

# Answer
> 1 votes
# JavaScript, 85 bytes

```
A=>f=(i=0,X=0,Y=-1)=>Y<0||A[Y][X]?(A+0)[i]&&[2,1,0,-1].map(t=>f(i+1,X+t--%2,Y+t%2)):0

```

Slow. Error if possible. Treating all area Y\<0 as solid and try walking enough time, error if it goes Y\>Ymax(`A[Y]` is `undefined`)

Try it online!

# Answer
> 0 votes
# Retina 0.8.2, 61 bytes

```
.+
1$&2
+`(?<=(.)*)(1|2)((?>.*¶(?<-1>.)*))?(?!\2)[12]
2$+2
^2

```

Try it online! Explanation:

```
.+
1$&2

```

Wrap each row between a `1` and a `2`.

```
+`(?<=(.)*)(1|2)((?>.*¶(?<-1>.)*))?(?!\2)[12]
2$+2

```

Repeatedly find pairs of `1`s and `2`s either horizontally or vertically adjacent and replace them both with `2`s. This will hopefully find a path from the right-hand column of `2`s through the input and end up filling the whole left-hand column of `1`s.

```
^2

```

Check whether a path was found.

---
Tags: code-golf, decision-problem, path-finding, binary-matrix
---


title: Longest Sublist with Equal Occurrences

text:
# Question
Title: Longest Sublist with Equal Occurrences
Given a non-empty list of integers between 1 and 9 inclusive, find the longest contiguous sublist such that the number of occurrences of each element (of the sublist) within the sublist is equal (*not* the number of consecutive occurrences, just the total count). You may return any non-empty subset of the solutions.

## Examples

```
Input                         ->  Output

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

```
* this is , so the shortest code in bytes wins
* Standard Loopholes are forbidden, as usual
* I/O may be in any reasonable format. You can do I/O with a string of digits since all inputs will be between 1 and 9, for example (this is mostly to allow regex solutions if anyone can figure that out).

# Answer
# Jelly, ~~8~~ 7 bytes

```
ẆĠẈEƊƇṪ

```

Try it online!

## How it works

```
ẆĠẈEƊƇṪ - Main link. Takes L on the left
Ẇ       - All non-empty contiguous sublists of L, longest last
    ƊƇ  - Keep those sublists S for which the following is true:
 Ġ      -   Group the indices of S by the elements
  Ẉ     -   Length of each
   E    -   All equal?
      Ṫ - Get the last (i.e. the longest) element

```
> 7 votes

# Answer
# Husk, ~~9 7~~ 5 bytes

```
►ṠË#Q

```

Try it online!

-2 using the return value of `Ë` in max by.

-2 from Leo.

## Explanation

```
►ṠË#Q
    Q all sublists (unsorted)
►     max by:
 ṠË       all elements of the list are equal by: (if all equal, returns len+1)
   #      count of occurrences in in the list

```
> 7 votes

# Answer
# Brachylog, 8 7 bytes

```
⊇.ọtᵛ&s

```

Try it online!

`s` generates all sublists of consecutive elements, though not in order of length, but in order of prefix (so `[1,2,3] [1,2] [1] [2,3] [2] [3]`).  on the other hand does generate longer sets first, but only guarantees element order, not that they are consecutive. So we check that later for +1 byte.

```
⊇.ọtᵛ&s  The (implicit) input                        [1,1,2,3]
⊇        has an (ordered) subset                     [1,2,3]
 .       that is the output,
  ọ      which elements grouped&counted by identity  [[1,1],[2,1],[3,1]]
   tᵛ    have the same number of occurences.         1
      &  The input                                   [1,1,2,3]
       s has consecutive elements                    [1,2,3]
         that is the (implicit) output.

```
> 7 votes

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

```
f=(h,...t)=>new Set(c=[],h.map(x=>c[x]=-~c[x])).size<3?h:f(...t,h.slice(1),h.pop()&&h)

```

Try it online!

Use Breadth-First Search, so you may avoid comparing its length.

A terrible \\$O(n\cdot2^n)\\$ time complexity. Luckly we only care about its length.

Codes for checking equal number occurrence is copied from Arnauld's answer.

---

# Python 3, 63 bytes

```
f=lambda l,*t:l*(len({*map(l.count,l)})<2)or f(*t,l[1:],l[:-1])

```

Try it online!

This Python answer is based on att's answer by applying BFS to it.

Comparing to JS, Python is good at creating sets, function auto bind, get length, array slicing when you are golfing.
> 7 votes

# Answer
# Scala, 84 bytes

```
_.tails.flatMap(_.inits)filter(l=>l.map(x=>l.count(_==x)).toSet.size<2)maxBy(_.size)

```

Try it in Scastie!

```
_.tails                //All suffixes
  .flatMap(_.inits)    //All prefixes of those suffixes (all subsequences)
  filter(l=>           //Keep the ones where
    l.map(x=>l.count(_==x))  //The counts of all the elements
      .toSet.size<2          //Has 0 or 1 distinct elements
  )maxBy(_.size)       //Find the biggest such subsequence

```
> 5 votes

# Answer
# 05AB1E, 8 bytes

```
ŒʒD¢Ë}éθ

```

Try it online!

```
Œ          # all sublists of the input
 ʒ   }     # filter by:
   ¢       #   counts of each value
  D        #   in a copy of the sublist
    Ë      #   are all counts equal?
      é    # sort the remaining sublists by length
       θ   # take the last one

```

Alternatively, sort first, reverse and take the first sublist that satisfies the condition:

```
ŒéR.ΔD¢Ë

```

Try it online!
> 5 votes

# Answer
# Japt `-h`, 10 bytes

```
ã kÈü üÊÊÉ

```

Try it

```
ã kÈü üÊÊÉ     :Implicit input of array
ã              :Subsections (sorted by length)
  k            :Remove elements that return falsey (0)
   È           :When passed through the following function
    ü          :  Group by value
      ü        :  Group by
       Ê       :    Length
        Ê      :  Length
         É     :  Minus 1
               :Implicit output of last element in resulting array

```
> 5 votes

# Answer
# Python 3, 73 bytes

```
f=lambda l:l*(len({*map(l.count,l)})<2)or max(f(l[1:]),f(l[:-1]),key=len)

```

Try it online!
> 5 votes

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

```
ŒʒD¢Ë}éθ

```

Try it online!

```
Œ     all sublists
ʒ     keep those such that
D     duplicate
¢     count, vectorizes
Ë     all equal
}
é     sort by length
θ     last

```
> 4 votes

# Answer
# JavaScript (ES6), 108 bytes

Returns the rightmost solution.

```
a=>a.map((_,n)=>a.map((_,i)=>(b=a.slice(i,i-~n))[new Set(b.map(x=>c[x]=-~c[x],c=[])&&c).size-2+n]?o=b:0))&&o

```

Try it online!

### Commented

```
a =>                       // a[] = input array
  a.map((_, n) =>          // for n = 0 to len(a) - 1:
    a.map((_, i) =>        //   for i = 0 to len(a) - 1:
      ( b =                //     define b[] as the sub-array of length
        a.slice(i, i - ~n) //     at most n + 1 starting at index i
      )[                   //
        new Set(           //     build a set consisting of the number of
          b.map(x =>       //     occurrences of each distinct entry in b[],
            c[x] = -~c[x], //     using another array c[] to keep track of
            c = []         //     these counts
          )                //     the set will always include 'undefined'
                           //     because c[0] is never updated
          && c             //
        ).size             //     which is why we expect its size to be 2
        - 2 + n            //     make sure that b[new Set().size - 2 + n]
      ]                    //     is defined (i.e. b[] is long enough and
                           //     the number of occurrences are all equal)
      ?                    //     if so:
        o = b              //       update the output
      :                    //     else:
        0                  //       do nothing
    )                      //   end of inner map()
  )                        // end of outer map()
  && o                     // return o

```
> 4 votes

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

```
lambda x:max((a for i in range(len(x)+1)for j in range(i)if len({*map((a:=x[j:i]).count,a)})<2),key=len)

```

Try it online!

-1 thanks to @ophact

-24 thanks to @pxeger

-10 thanks to @hyper-neutrino
> 4 votes

# Answer
# , ~~104~~ ~~98~~ ~~96~~ 95 bytes

```
function(L,n=seq(!L)){for(i in n)for(j in n)if(!sd(table(a<-L[i:j])+!1:2)&sum(T|1)<j-i+2)T=a;T}

```

Try it online!

Ugly straightforward approach. Can't wait for a nice  solution!

*-6 bytes thanks to @Dominic*
*-1 byte thanks to @Giuseppe*
> 4 votes

# Answer
# Haskell, 92 bytes

```
last.sortOn l.filter((<2).l.nub.map l.group.sort).(>>=tails).inits
l=length
import Data.List

```

Try it online!

Either Haskell is *not* the language for this challenge, or I'm not the Haskeller for this challenge1.

---

1 Yup, I know, it's the latter.
> 3 votes

# Answer
# , 38 33 bytes

```
0{(1=&#[:=#/.~)\\.(\:#&>)@#&,<\\.

```

Try it online!

-5 thanks to xash!
> 3 votes

# Answer
# JavaScript, 122 bytes

```
f=(n,p=t=n.length)=>n.find((e,i)=>i+p<=t&(l=n.slice(i,i+p)).every(x=>(z=m=>l.filter(w=>w==m).length)(x)==z(e)))?l:f(n,p-1)

```

One must marvel at the sheer length of counting the number of occurrences in a list.

A recursive function which checks all lists of length `p` for one satisfying the OP's conditions, and if there exists one, return it, otherwise return `f(n,p-1)`

Suggestions are welcome for golfing.
> 2 votes

# Answer
# Factor, ~~63~~ ~~58~~ 56 bytes

```
[ all-subseqs [ histogram values all-eq? ] filter last ]

```

Try it online!

```
              [                          ] filter last   ! Select the last/largest..
  all-subseqs                                            ! ..subsequence..
                histogram values                         ! ..whose elements occur..
                                 all-eq?                 ! ..the same number of times.

```
> 2 votes

# Answer
# Wolfram Language (Mathematica), 44 bytes

```
Last@*Select[Equal@@Counts@#&]@*Subsequences

```

Try it online!

Get all subsequences (ordered), select the ones with equal occurrences, take the last of those.
> 2 votes

# Answer
# Retina, 71 bytes

```
Lw`.+
%(`$
¶$`
1%O`.
1%L$`(.)\1*
$.&
)L$`^(.+)(¶.+)\2*$
$1
N^$`
$.&
0G`

```

Try it online! Link includes test cases. Takes input as a string of digits. Explanation:

```
Lw`.+

```

Get all substrings of the input.

```
%(`
)`

```

Loop over each substring.

```
$
¶$`

```

Duplicate the substring.

```
1%O`.

```

Sort the duplicate into order.

```
1%L$`(.)\1*
$.&

```

Get the run lengths.

```
L$`^(.+)(¶.+)\2*$
$1

```

If the run lengths are equal, then keep the substring, otherwise keep nothing.

```
N^$`
$.&

```

Sort all of the remaining substrings in descending order of length.

```
0G`

```

Keep only the longest remaining substring.
> 2 votes

# Answer
# Python 2, ~~140~~ 132 bytes

-8 bytes thanks to @hyper-neutrino for space saving and replacing `def` with `lambda`!

I was using python3 to code until I found that it works for Python2 too, not too much, just an iterative solution.

```
lambda n:max([r for r in [n[i:a]for a in range(len(n)+1)for i in range(len(n))if a-i>1]if len(set(r.count(s)for s in r))<2],key=len)

```

Try it online!
> 2 votes

# Answer
# Charcoal, 40 bytes

```
ＦＥθ✂θκＦＥι…ι⊕λＦ⁼⌊Ｅκ№κλ⌈Ｅκ№κλ⊞υκΦυ⁼Ｌι⌈ＥυＬλ

```

Try it online! Link is to verbose version of code. Takes input as a string of digits and outputs all maximal length substrings with the given condition. Explanation:

```
ＦＥθ✂θκ

```

Loop over all nontrivial suffixes of the input.

```
ＦＥι…ι⊕λ

```

Loop over all nontrivial prefixes of the suffix.

```
Ｆ⁼⌊Ｅκ№κλ⌈Ｅκ№κλ

```

Take the frequencies of the elements and check whether they are all the same.

```
⊞υκ

```

Record all substrings that satisfy the condition.

```
Φυ⁼Ｌι⌈ＥυＬλ

```

Output the longest such substrings.
> 1 votes

# Answer
# yuno (abandoned), 7 bytes

```
ッシュフェドゥッキッカ；テ

```

xxd using Jelly's codepage:

```
00000000: 87a0 9a6d 6bfe 0b                        ⁷ɦȤmk“¿

```

Disclaimer: some language features were added after this challenge. However, they weren't really made to be tailored to this challenge, all of these are things I'd planned previously. If I really wanted to, I could've reasonably made built-ins much more suited ot this challenge, but I have those on my wishlist right now as they're a lot more specific.

```
ッシュフェドゥッキッカ；テ   Full Program
ッシュ　　　　　　　　　　   All sublists, in increasing order of length then position
　　　フェ　　　　　　；　   Filter-lambda; keep elements that:
　　　　　ドゥ　　　　　　   (duplicate top of stack)
　　　　　　　ッキ　　　　   special count; if counting occurrences of a list that is not found, but any of its elements are, vectorize (recurses)
　　　　　　　　　ッカ　　   all-equal?
　　　　　　　　　　　　テ   last element

```
> 1 votes

# Answer
# Ruby, 69 bytes

```
->r,*w{r,*w=w<<r[0..-2]<<r[1..-1]while r.map{|x|r.count x}.uniq[1];r}

```

Try it online!
> 1 votes

# Answer
# Python 3.8, 98 bytes

Another not-very-successful python3 attempt

```
f=lambda l,i=0:(a:=l[i%(L:=len(l)):][:L-i//L])*(i%L<=i//L)*(len({*map(a.count,a)})<2)or f(l,i+1)

```

a less condensed version

```
def f(l, i=0):
 L = len(l)
 a = l[i%L:][:L-i//L]
 return a * (i%L<=i//L) * (len({*map(a.count,a)})<2) or f(l,i+1)

```
> 0 votes

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


# Question
Title: Demonstrate some advanced abstract algebra
Consider a binary operator \\$\*\\$ that operates on a set \\$S\\$. For simplicity's sake, we'll assume that \\$\*\\$ is closed, meaning that its inputs and outputs are always members of \\$S\\$. This means that \\$(\*, S)\\$ is a magma

Let's define some basic terms describing the properties of \\$\*\\$. We can say that \\$\*\\$ can have any of these properties, if they hold for all \\$a,b,c \in S\\$:

* **Commutative**: \\$a\*b \equiv b\*a\\$
* **Associative**: \\$(a\*b)\*c \equiv a\*(b\*c)\\$
* **Distributive**: \\$a\*(b+c) \equiv (a\*b)+(a\*c)\\$, for some binary operator \\$+\\$ on \\$S\\$

We can also define 3 related properties, for a unary operation \\$-\\$ on \\$S\\$:

* **Anti-commutative**: \\$a\*b \equiv -(b\*a)\\$
* **Anti-associative**: \\$(a\*b)\*c \equiv -(a\*(b\*c))\\$
* **Anti-distributive**: \\$a\*(b+c) \equiv -((a\*b)+(a\*c))\\$

Finally, we define 3 more, that only describe \\$\*\\$ if the complete statement is true for \\$a,b,c \in S\\$:

* **Non-commutative**: There exists \\$a, b\\$ such that \\$a\*b \not\equiv b\*a\\$ and \\$a\*b \not\equiv -(b\*a)\\$
* **Non-associative**: There exists \\$a, b, c\\$ such that \\$(a\*b)\*c \not\equiv a\*(b\*c)\\$ and \\$(a\*b)\*c \not\equiv -(a\*(b\*c))\\$
* **Non-distributive**: These exists \\$a,b,c\\$ such that \\$a\*(b+c) \not\equiv (a\*b)+(a\*c)\\$ and \\$a\*(b+c) \not\equiv -((a\*b)+(a\*c))\\$

We now have 9 distinct properties a binary operator can have: commutativity, non-commutativity, anti-commutativity, associativity, non-associativity, anti-associativity, distributivity, non-distributivity and anti-distributivity.

This does require two operators (\\$-\\$ and \\$+\\$) to be defined on \\$S\\$ as well. For this challenge we'll use standard integer negation and addition for these two, and will be using \\$S = \mathbb Z\\$.

Obviously, any given binary operator can only meet a maximum of 3 of these 9 properties, as it cannot be e.g. both non-associative and anti-associative. However, it is possible to create a function that is, for example, neither commutative, anti-commutative or non-commutative, by creating an operator \\$\*\\$ such that \\$a\*b = b\*a\\$ for some inputs and \\$a\*b = -b\*a\\$ for others. Therefore, it is possible to create an operator that meets fewer than 3 of these properties.

---

Your task is to write 9 programs (either full programs or functions. You may "mix and match" if you wish).

Each of these 9 programs will:

* take two integers, in any reasonable format and method
* output one integer, in the same format as the input and in any reasonable method
* be a surjection \\$\mathbb Z^2 \to \mathbb Z\\$ (takes two integers as input and outputs one integer). This means that for any distinct output, there is at least one input that yields that output
* uniquely exhibit one of the 9 properties described above.

This means that, of your nine programs, one should be commutative, one associative, one distributive over addition, one anti-commutative, one anti-associative, one anti-distributive, one non-commutative, one non-associative and one non-distributive.

Your programs must each exhibit **exactly** 1 of these 9 behaviours, and violate the other 8. For example, multiplication would be banned, as it is commutative, associative and distributive. However, this also means that 6 of your programs must not be e.g. any of commutative, anti-commutative or non-commutative. How you reconcile this is up to you.

This is ; the combined lengths of all 9 of your programs is your score, and you should aim to minimise this.

Additionally, you should include some form of proof that your programs do indeed have the required properties and do not satisfy the other properties. Answers without these are not considered valid.

Alternatively, your answer may be in the form of a proof of impossibility. If this is the case, you must prove that there are no such operators that are valid answers to this. You do not have to show that all 9 properties are impossible to exhibit - only one - in this proof. In this case, there can only be one answer, which, by default, will be the winner.

# Answer
> 21 votes
# Proof of impossibility

The only anti-distributive operator when \\$S=\mathbb Z\\$ is such that \\$\forall a, \forall b, a\*b=0\\$.

Indeed, suppose that \\$\*\\$ is anti-distributive. Then \\$\*\\$ has the following property, for all \\$ a,b,c\in\mathbb Z\\$:

* (D) \\$a\*(b+c) = - (a\*b+a\*c)\\$

(In my notation, \\$\*\\$ has precedence over \\$+\\$.)

Take \\$a,b \in \mathbb Z\\$. By (D),

\\$a\*(2b) = a\*(b+b) = - (a\*b + a\*b) = -2(a\*b)\\ a\*(3b) = a\*(2b+b) = -(a\*2b + a\*b) = -(-2(a\*b) + a\*b) = a\*b\\ a\*(4b) = a\*(2b+2b) = -(a\*2b + a\*2b) = -(-2(a\*b) -2(a\*b)) = 4(a\*b)\\ a\*(4b) = a\*(3b+b) = -(a\*3b + a\*b) = -(a\*b + a\*b) = -2(a\*b) \\$

Hence \\$4(a\*b) = -2(a\*b)\\$ and \\$a\*b=0\\$.

We thus have that \\$\forall a,\forall b, a\*b=0\\$.

The only anti-distributive operator is therefore always equal to \\$0\\$. In particular, it is commutative, anti-commutative, associative, anti-associative, distributive, anti-distributive, and not a surjection. It is therefore impossible to exhibit an operator which is only anti-distributive.

---
Tags: code-golf, math, abstract-algebra, open-ended-function
---


# Question
Title: Map a list of indefinite size to a number!
It is well known, in the field of Mathematics studying infinity, that the Cartesian product of any finite amount of countable sets is also countable.

Your task is to write two programs to implement this, one to map from list to integer, one to map from integer to list.

Your function must be bijective and deterministic, meaning that `1` will always map to a certain list, and `2` will always map to another certain list, etc...

Earlier, we mapped integers to a list consisting only of `0` and `1`.

**However, now the list will consist of non-negative numbers.**

# Specs

* Program/function, reasonable input/output format.
* Whether the mapped integers start from `1` or starts from `0` is your choice, meaning that `0` doesn't have to (but may) map to anything.
* The empty array `[]` must be encoded.
* Input/output may be in any base.
* Sharing code between the two functions is **allowed**.

# Scoring

This is . Lowest score wins.

Score is the sum of lengths (in bytes) of the two programs/functions.

# Answer
# Jelly, ~~18~~ 16 bytes

### List to integer, ~~10~~ 8 bytes

```
TṪạL;³ÆẸ

```

Maps lists of non-negative integers to positive integers. Try it online!

### Integer to list, 8 bytes

```
ÆE©Ḣ0ẋ®;

```

Maps positive integers to lists of non-negative integers . Try it online!

## Background

Let **p0, p1, p2, ⋯** be the sequence of prime numbers in ascending order.

For each list of non-negative integers **A := \[a1, ⋯, an\]**, we map **A** to **p0z(A)p1a1⋯pnan**, where **z(A)** is the number of trailing zeroes of **A**.

Reversing the above map in straightforward. For a *positive* integer **k**, we factorize it uniquely as the product of consecutive prime powers **n = p0α0p1α1⋯pnαn**, where **αn \> 0**, then reconstruct the list as **1, ⋯, αn\]**, appending **α0** zeroes.

## How it works

### List to integer

```
TṪạL;³ÆẸ  Main link. Argument: A (list of non-negative integers)

T         Yield all indices of A that correspond to truthy (i.e., non-zero) items.
 Ṫ        Tail; select the last truthy index.
          This returns 0 if the list is empty.
   L      Yield the length of A.
  ạ       Compute the absolute difference of the last truthy index and the length.
          This yields the amount of trailing zeroes of A.
    ;³    Prepend the difference to A.
      ÆẸ  Convert the list from prime exponents to integer.

```

### Integer to list

```
ÆE©Ḣ0ẋ®;  Main link. Input: k (positive integer)

ÆE        Convert k to the list of its prime exponents.
  ©       Save the list of prime exponents in the register.
   Ḣ      Head; pop the first exponent.
          If the list is empty, this yields 0.
    0ẋ    Construct a list of that many zeroes.
      ®;  Concatenate the popped list of exponents with the list of zeroes.

```

## Example output

The first one hundred positive integers map to the following lists.

```
  1: []
  2: [0]
  3: [1]
  4: [0, 0]
  5: [0, 1]
  6: [1, 0]
  7: [0, 0, 1]
  8: [0, 0, 0]
  9: [2]
 10: [0, 1, 0]
 11: [0, 0, 0, 1]
 12: [1, 0, 0]
 13: [0, 0, 0, 0, 1]
 14: [0, 0, 1, 0]
 15: [1, 1]
 16: [0, 0, 0, 0]
 17: [0, 0, 0, 0, 0, 1]
 18: [2, 0]
 19: [0, 0, 0, 0, 0, 0, 1]
 20: [0, 1, 0, 0]
 21: [1, 0, 1]
 22: [0, 0, 0, 1, 0]
 23: [0, 0, 0, 0, 0, 0, 0, 1]
 24: [1, 0, 0, 0]
 25: [0, 2]
 26: [0, 0, 0, 0, 1, 0]
 27: [3]
 28: [0, 0, 1, 0, 0]
 29: [0, 0, 0, 0, 0, 0, 0, 0, 1]
 30: [1, 1, 0]
 31: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 32: [0, 0, 0, 0, 0]
 33: [1, 0, 0, 1]
 34: [0, 0, 0, 0, 0, 1, 0]
 35: [0, 1, 1]
 36: [2, 0, 0]
 37: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 38: [0, 0, 0, 0, 0, 0, 1, 0]
 39: [1, 0, 0, 0, 1]
 40: [0, 1, 0, 0, 0]
 41: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 42: [1, 0, 1, 0]
 43: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 44: [0, 0, 0, 1, 0, 0]
 45: [2, 1]
 46: [0, 0, 0, 0, 0, 0, 0, 1, 0]
 47: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 48: [1, 0, 0, 0, 0]
 49: [0, 0, 2]
 50: [0, 2, 0]
 51: [1, 0, 0, 0, 0, 1]
 52: [0, 0, 0, 0, 1, 0, 0]
 53: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 54: [3, 0]
 55: [0, 1, 0, 1]
 56: [0, 0, 1, 0, 0, 0]
 57: [1, 0, 0, 0, 0, 0, 1]
 58: [0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 59: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 60: [1, 1, 0, 0]
 61: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 62: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 63: [2, 0, 1]
 64: [0, 0, 0, 0, 0, 0]
 65: [0, 1, 0, 0, 1]
 66: [1, 0, 0, 1, 0]
 67: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 68: [0, 0, 0, 0, 0, 1, 0, 0]
 69: [1, 0, 0, 0, 0, 0, 0, 1]
 70: [0, 1, 1, 0]
 71: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 72: [2, 0, 0, 0]
 73: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 74: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 75: [1, 2]
 76: [0, 0, 0, 0, 0, 0, 1, 0, 0]
 77: [0, 0, 1, 1]
 78: [1, 0, 0, 0, 1, 0]
 79: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 80: [0, 1, 0, 0, 0, 0]
 81: [4]
 82: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 83: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 84: [1, 0, 1, 0, 0]
 85: [0, 1, 0, 0, 0, 1]
 86: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 87: [1, 0, 0, 0, 0, 0, 0, 0, 1]
 88: [0, 0, 0, 1, 0, 0, 0]
 89: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 90: [2, 1, 0]
 91: [0, 0, 1, 0, 1]
 92: [0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
 93: [1, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 94: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 95: [0, 1, 0, 0, 0, 0, 1]
 96: [1, 0, 0, 0, 0, 0]
 97: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 98: [0, 0, 2, 0]
 99: [2, 0, 0, 1]
100: [0, 2, 0, 0]

```
> 11 votes

# Answer
# Jelly, ~~13~~ 12 bytes

## Encode, ~~7~~ 6 bytes

```
2Bṁx‘Ḅ

```

Try it online!

## Decode, 6 bytes

```
ȯIBŒɠ’

```

Try it online!

Encodes positive integers in the run lengths of the binary representation. Since we may have zeros, we increment all numbers. For example, the list `[0,1,4]` is encoded as 10011111 in binary.

Numbers from 0 to 100 (Try it online!):

```
0                     []
1                     [0]
2                     [0, 0]
3                     [1]
4                     [0, 1]
5                     [0, 0, 0]
6                     [1, 0]
7                     [2]
8                     [0, 2]
9                     [0, 1, 0]
10                    [0, 0, 0, 0]
11                    [0, 0, 1]
12                    [1, 1]
13                    [1, 0, 0]
14                    [2, 0]
15                    [3]
16                    [0, 3]
17                    [0, 2, 0]
18                    [0, 1, 0, 0]
19                    [0, 1, 1]
20                    [0, 0, 0, 1]
21                    [0, 0, 0, 0, 0]
22                    [0, 0, 1, 0]
23                    [0, 0, 2]
24                    [1, 2]
25                    [1, 1, 0]
26                    [1, 0, 0, 0]
27                    [1, 0, 1]
28                    [2, 1]
29                    [2, 0, 0]
30                    [3, 0]
31                    [4]
32                    [0, 4]
33                    [0, 3, 0]
34                    [0, 2, 0, 0]
35                    [0, 2, 1]
36                    [0, 1, 0, 1]
37                    [0, 1, 0, 0, 0]
38                    [0, 1, 1, 0]
39                    [0, 1, 2]
40                    [0, 0, 0, 2]
41                    [0, 0, 0, 1, 0]
42                    [0, 0, 0, 0, 0, 0]
43                    [0, 0, 0, 0, 1]
44                    [0, 0, 1, 1]
45                    [0, 0, 1, 0, 0]
46                    [0, 0, 2, 0]
47                    [0, 0, 3]
48                    [1, 3]
49                    [1, 2, 0]
50                    [1, 1, 0, 0]
51                    [1, 1, 1]
52                    [1, 0, 0, 1]
53                    [1, 0, 0, 0, 0]
54                    [1, 0, 1, 0]
55                    [1, 0, 2]
56                    [2, 2]
57                    [2, 1, 0]
58                    [2, 0, 0, 0]
59                    [2, 0, 1]
60                    [3, 1]
61                    [3, 0, 0]
62                    [4, 0]
63                    [5]
64                    [0, 5]
65                    [0, 4, 0]
66                    [0, 3, 0, 0]
67                    [0, 3, 1]
68                    [0, 2, 0, 1]
69                    [0, 2, 0, 0, 0]
70                    [0, 2, 1, 0]
71                    [0, 2, 2]
72                    [0, 1, 0, 2]
73                    [0, 1, 0, 1, 0]
74                    [0, 1, 0, 0, 0, 0]
75                    [0, 1, 0, 0, 1]
76                    [0, 1, 1, 1]
77                    [0, 1, 1, 0, 0]
78                    [0, 1, 2, 0]
79                    [0, 1, 3]
80                    [0, 0, 0, 3]
81                    [0, 0, 0, 2, 0]
82                    [0, 0, 0, 1, 0, 0]
83                    [0, 0, 0, 1, 1]
84                    [0, 0, 0, 0, 0, 1]
85                    [0, 0, 0, 0, 0, 0, 0]
86                    [0, 0, 0, 0, 1, 0]
87                    [0, 0, 0, 0, 2]
88                    [0, 0, 1, 2]
89                    [0, 0, 1, 1, 0]
90                    [0, 0, 1, 0, 0, 0]
91                    [0, 0, 1, 0, 1]
92                    [0, 0, 2, 1]
93                    [0, 0, 2, 0, 0]
94                    [0, 0, 3, 0]
95                    [0, 0, 4]
96                    [1, 4]
97                    [1, 3, 0]
98                    [1, 2, 0, 0]
99                    [1, 2, 1]
100                   [1, 1, 0, 1]

```
> 7 votes

# Answer
# Python 2, 88 bytes

```
d=lambda n:map(len,bin(n).split('1')[1:])
e=lambda l:int('1'.join(a*'0'for a in[2]+l),2)

```

Demo:

```
>>> for i in range(33):
...     print e(d(i)), d(i)
...
0 []
1 [0]
2 [1]
3 [0, 0]
4 [2]
5 [1, 0]
6 [0, 1]
7 [0, 0, 0]
8 [3]
9 [2, 0]
10 [1, 1]
11 [1, 0, 0]
12 [0, 2]
13 [0, 1, 0]
14 [0, 0, 1]
15 [0, 0, 0, 0]
16 [4]
17 [3, 0]
18 [2, 1]
19 [2, 0, 0]
20 [1, 2]
21 [1, 1, 0]
22 [1, 0, 1]
23 [1, 0, 0, 0]
24 [0, 3]
25 [0, 2, 0]
26 [0, 1, 1]
27 [0, 1, 0, 0]
28 [0, 0, 2]
29 [0, 0, 1, 0]
30 [0, 0, 0, 1]
31 [0, 0, 0, 0, 0]
32 [5]

```

# Python 2, 130 bytes

Here’s a more “efficient” solution where the bit-length of the output is linear in the bit-length of the input rather than exponential.

```
def d(n):m=-(n^-n);return d(n/m/m)+[n/m%m+m-2]if n else[]
e=lambda l:int('0'+''.join(bin(2*a+5<<len(bin(a+2))-4)[3:]for a in l),2)

```
> 3 votes

# Answer
# Python 2, 204 202 bytes

```
p=lambda x,y:(2*y+1<<x)-1
u=lambda n,x=0:-~n%2<1and u(-~n//2-1,x+1)or[x,n//2]
e=lambda l:l and-~reduce(p,l,len(l)-1)or 0
def d(n):
 if n<1:return[]
 r=[];n,l=u(n-1);exec"n,e=u(n);r=[e]+r;"*l;return[n]+r

```

Works by repeatedly applying a Z+ x Z+ \<-\> Z+ bijection, prepended by the list length.

```
0: []
1: [0]
2: [1]
3: [0, 0]
4: [2]
5: [0, 0, 0]
6: [1, 0]
7: [0, 0, 0, 0]
8: [3]
9: [0, 0, 0, 0, 0]
10: [1, 0, 0]
11: [0, 0, 0, 0, 0, 0]
12: [0, 1]
13: [0, 0, 0, 0, 0, 0, 0]
14: [1, 0, 0, 0]
15: [0, 0, 0, 0, 0, 0, 0, 0]
16: [4]
17: [0, 0, 0, 0, 0, 0, 0, 0, 0]
18: [1, 0, 0, 0, 0]
19: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
20: [0, 0, 1]
21: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
22: [1, 0, 0, 0, 0, 0]
23: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
24: [2, 0]
25: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
26: [1, 0, 0, 0, 0, 0, 0]
27: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
28: [0, 0, 0, 1]
29: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
30: [1, 0, 0, 0, 0, 0, 0, 0]
31: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

```
> 1 votes

# Answer
# Retina, 17 + 23 = 40 bytes

From list to integer:

```
\d+
$&$*0
^
1

1

```

Try it online!

From integer to list:

```
^1

S`1
m`^(0*)
$.1
¶
<space>

```

Try it online!

Uses Kaseorg's Algorithm.
> 0 votes

# Answer
# JavaScript, 87 bytes

```
F=n=>n.toString(2).split(1).slice(1).map(_=>_.length)
G=a=>g=(i=0)=>F(i)+''==a?i:g(++i)

```

`G` goes through all inputs since it's shorter
> 0 votes

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


title: Keep PPCG running in Game of Life

text:
# Question
Title: Keep PPCG running in Game of Life
Conways' Game of Life is a well known cellular automaton "played" on an infinite grid, filled with cells that are either alive or dead. Once given an initial state, the board evolves according to rules indefinitely. Those rules are:

* Any live cell with 2 or 3 living neighbours (the 8 cells immediately around it) lives to the next state
* Any dead cell with exactly 3 living neighbours becomes a living cell
* Any other cell becomes a dead cell

Consider the following initial state:

That is, `PPCG` made up of living cells. Each letter is in a \\$4×6\\$ bounding box, with a single empty column of cells between boxes, for a total bounding box of \\$19×6\\$

After 217 generations, it reaches the following states:

From this point onwards, it is a "fixed state". All structures on the board are either still lifes or oscillators, so no meaningful change will occur.

Your task is to improve this.

You may place up to 50 live cells in the \\$5\times10\\$ highlighted area, such that, when run, it takes more than 217 generations to reach a "fixed state". The answer with the highest number of generations wins, with ties being broken by the fewest number of placed living cells.

For the purposes of this challenge, a "fixed state" means that all structures on the board are either still lifes or oscillators. If any spaceships or patterns of infinite growth are generated, the board will never reach a "fixed state" and such cases are invalid submissions.

For example, this initial configuration takes 294 generations to reach a fixed state (this), so is a valid submission with a score of 294:

Preloaded testable version, with the \\$5\times10\\$ box fully filled in.

# Answer
# 3365 generations

```
_#_#_
##__#
_##__
_____
#####
_##__
#____
#_#_#
##___
_#_#_

```

This 5x10 start can be expressed as 379744881760010 in decimal, 159603ec8570a in hex or 01010 11001 01100 00000 11111 01100 10000 10101 11000 01010 in 50-bit binary. Crossing my fingers that nobody starts a new alt-coin based on rewarding many generations in Conway's Game of Life...LifeCoins.
> 3 votes

# Answer
# 2986 ~~2320~~ ~~1228~~ generations

I wrote a rudimentary Python script for Golly to generate random 5x10 patterns until it encountered one whose population was fixed, and whose bounding box was not too large (as would be expected of soups containing spaceships, as spaceships expand the bounding box as they travel). Here was what it came up with after about 50,000 patterns investigated, and I suspect this is not maximal. If anyone wants to continue this search by using my script, it's located below the pattern.

RLE of solution:

```
# 2986 generations
x = 19, y = 20, rule = B3/S23
3o2b3o3b3o2b3o$o2bobo2bobo4bo$o2bobo2bobo4bo$3o2b3o2bo4bob2o$o4bo4bo4b
o2bo$o4bo5b3o2b2o5$7bobobo$7b2ob2o$8bo2bo$11bo$10b2o$7bo2bo2$8b4o$7bo$
7bo3bo!

```

Python script, to be run in Golly from File \> Run Script (not golfed). You will need to paste/draw in the PPCG pattern and select the 5x10 rectangle first.

```
import golly as g
from glife import rect, pattern

g.setrule("B3/S23") #set the rule to Conway's Life
soupcount = 0 #create a counter for # of soups processed

while True:
    pop = 0
    g.randfill(50) #randomly fill the 5x10 selection
    g.run(2400) #run the pattern for 2400 generations
    if g.getrect()[2] * g.getrect()[3] < 40000: #after 2400 generations, if the bounding box is small
        pop = g.getpop() #check to make sure the population is not the same (pattern is not static)
        g.run(120)
        if g.getpop() != pop:
            g.run(9880) #after 9880 more generations, if the bounding box is still small
            if g.getrect()[2] * g.getrect()[3] < 40000: #check to make sure the population is the same (pattern is static)
                pop = g.getpop()
                g.run(120)
                if g.getpop() == pop:
                    g.reset() #if so, break the loop and return the pattern
                    break
    g.reset() #repeat the loop and generate a new pattern if the pattern does not satisfy the conditions
    soupcount += 1
    g.show(str(soupcount)) #continually show the # of soups processed to make sure the program isn't dead

```

**RLEs of old solutions:**

```
#C 2320 generations
x = 19, y = 20, rule = B3/S23
3o2b3o3b3o2b3o$o2bobo2bobo4bo$o2bobo2bobo4bo$3o2b3o2bo4bob2o$o4bo4bo4b
o2bo$o4bo5b3o2b2o5$7bo3bo$7b3o$10bo2$7bo$7bo2bo$7bo$7b2o$7bo3bo$7b2o2b
o!

```

```
#C 1228 generations, found manually with Ctrl+5
#C to continually generate random 5x10 patterns
x = 19, y = 17, rule = B3/S23
3o2b3o3b3o2b3o$o2bobo2bobo4bo$o2bobo2bobo4bo$3o2b3o2bo4bob2o$o4bo4bo4b
o2bo$o4bo5b3o2b2o5$7b5o$7bobobo$7b2obo$8bob2o$8b4o$8bo2bo$7bobo!

```
> 14 votes

# Answer
# 887 generations

# Explanation

…There is no explanation. I just brute-forced it manually and somehow beat ChartZ Belatedly by 90 generations.
> 8 votes

# Answer
# ~~884~~  900 generations

Just some random handcrafted pattern.
> 5 votes

# Answer
# ~~3020~~ 3179 Generations

```

# #
### #
 # #
   ##
##
    #

    #
 # ##
##

```

Found by random search
> 4 votes

---
Tags: code-challenge, cellular-automata, busy-beaver, game-of-life
---


title: Implement a FuzzyFinder

text:
# Question
Title: Implement a FuzzyFinder
Inspired by this link I found on Reddit.

A FuzzyFinder is a feature of many text editors. As you start to type a file path `S`, the FuzzyFinder kicks in and shows you all files in the current directory containing the string you entered, sorted by the position of `S` in the file.

Your task is to implement a fuzzy finder. It should be program or function that takes (via stdin, function argument, or command line) a string `S` and a list of strings `L`, formatted however you wish, and returns or prints the result of running the fuzzy finder. The search should be case-sensitive. Results where `S` is in the same position in multiple strings may be sorted however you wish.

Example:

```
Input: mig, [imig, mig, migd, do, Mig]
Output:
    [mig, migd, imig]
OR
    [migd, mig, imig]

```

This is code golf, so the shortest solution wins.

# Answer
# Pyth, 9 bytes

```
oxNzf}zTQ

```

Try it online: Demonstration

### Explanation:

```
            implicit: z = input string, Q = input list
    f   Q   filter Q for elements T, which satisfy:
     }zT      z is substring of T
o           order the remaining strings N by:
 xNz          the index of z in N

```
> 6 votes

# Answer
# CJam, ~~18~~ 15 bytes

```
{1$#)}q~2$,@$p;

```

Try it online in the CJam interpreter.

### I/O

Input:

```
"mig" ["imig" "mig" "migd" "do" "Mig"]

```

Output:

```
["mig" "migd" "imig"]

```

### How it works

```
      q~        e# Read and evaluate the input from STDIN.
                e# Pushes a needle and an array of haystacks.
{    }          e# Define a code block:
 1$             e#   Copy the needle.
   #            e#   Compute the index of the needle in the haystack.
    )           e#   Add 1 to the index.
        2$      e# Copy the block.
          ,     e# Filter: Keep only haystacks for which the code block
                e#         pushed a non-zero value.
           @    e# Rotate the block on top of the stack.
            $   e# Sort: Arrange the haystacks according to the values
                e#       pushed by the code block.
             p  e# Print the filtered and sorted haystacks.
              ; e# Discard the needle.

```
> 5 votes

# Answer
## Python 2, 65

```
def f(s,l):g=lambda x:x.find(s)+1;print sorted(filter(g,l),key=g)

```

The expression `x.find(s)` returns the position of the first occurrence of `s` in `x`, giving `-1` for no match. We add `1` to the result to that no-match corresponds to `0`, letting us `filter` them out. We then sort by the match position, which is unaffected by shifting by 1.
> 5 votes

# Answer
# GolfScript, 13 bytes

```
~{?)}+\1$,\$`

```

This is one of those rare occasions where GolfScript can beat CJam, by using block concatenation and taking a few liberties with the input which can be *formatted however you wish*.

Try it online in Web GolfScript.

### I/O

Input

```
["imig" "mig" "migd" "do" "Mig"] {"mig"}

```

Output

```
["migd" "mig" "imig"]

```

### How it works

```
~             # Evaluate the input from STDIN.
              # Pushes an array of haystacks and a needle in a block.
 {?)}         # Push a code block that computes an index and increments it.
     +        # Concatenate that block with the needle block.
      \1$     # Swap the block with the arrays of haystacks and copy the block.
         ,    # Filter: Keep only haystacks for which the code block
              #         pushed a non-zero value.
          \   # Swap the array of haystacks with the code block.
           $  # Sort: Arrange the haystacks according to the values
              #       pushed by the code block.
            ` # Inspect: Format the array for pretty printing.

```
> 5 votes

# Answer
# JavaScript ES6, 68 bytes

```
(s,l,f=j=>j.indexOf(s))=>l.filter(w=>~f(w)).sort((a,b)=>f(a)>f(b))

```

This is an anonymous function that takes parameters `s` (file path string) and `l` (array of strings). The Stack Snippet below contains ungolfed code converted to ES5 so more people can test it easily. (If you have Firefox, you can use edc65's prettier test suite found in his answer.)

```
f=function(s,l){
  g=function(j){
    return j.search(s)
  }

  return l.filter(function(w){
    return ~g(w)
  }).sort(function(a,b){
    return g(a)>g(b)
  })
}

id=document.getElementById;run=function(){document.getElementById('output').innerHTML=f(document.getElementById('s').value,document.getElementById('l').value.split(', ')).join(', ')};document.getElementById('run').onclick=run;run()
```

```
<label>File path: <input type="text" id="s" value="mig" /></label><br />
<label>Files: <input type="text" id="l" value="imig, mig, migd, do, Mig" /></label><br />
<button id="run">Run</button><br />
Output: <output id="output"></output>
```
> 3 votes

# Answer
# \[Hold\] Pyth, 24 Bytes

```
JwKcwdVlK=G.)KI}JGaYG))Y

```

Try is here

I'm pretty new at Code Golfing/Pyth so I'm not sure it's optimal, but I'm working on it!

**Update:** I don't think I'm actually sorting correctly, and I can't seem to get it to work. I know that `o` is order-by, and I need to sort by position of S so I am using `.:GlJ` in order to find all the substrings of the length of S for the current element `G` and then `x` in order to find the index of the first occurrence of S, but I can't seem to set lambda correctly.
> 3 votes

# Answer
# Python 2, ~~69~~ ~~68~~ 66 Bytes

I just created a function which takes `s` as the string to match in a list of strings `n`

*Edit 1: Thanks to Jakube for golfing off a byte.*

```
lambda s,n:sorted([x for x in n if s in x],key=lambda x:x.find(s))

```

Check it out here.
> 2 votes

# Answer
# JavaScript (*ES6*), 68

**That's almost the same of @NBM answer (even if it's not copied), so I don't expect upvotes. Enjoy the snippet anyway**

A function with a string and a string array arguments, return a string array. Filter then sort.

Test runnign the snippet below (being EcmaScript 6, Firefox only)

```
f=(s,l,i=t=>t.indexOf(s))=>l.filter(t=>~i(t)).sort((t,u)=>i(t)-i(u))

$(function(){
  $("#S,#L").on("keyup",
   function() {
     $('#O').val(f(S.value,L.value.split('\n')).join('\n'))
   } );
  $("#S").trigger('keyup');
})
```

```
#S,#L,#O { width: 400px }
#L,#O { height: 100px }
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
Input String<br><input id=S value='mig'><br>
Input List<br><textarea id=L>
imig
mig
migd
do
Mig
</textarea><br>
Output List<br><textarea id=O readonly></textarea>
```
> 2 votes

# Answer
# Haskell, ~~129~~ 116

116 (Thanks to Franky):

```
import Data.List
h s=map snd.sort.map(\x->((head[c|c<-[0..length x],isPrefixOf s(drop c x)]),x)).filter(isInfixOf s)

```

---

129:

```
import Data.List
f s n=map snd(sort(map(\x->((head [c|c<-[0..length x],isPrefixOf s(drop c x)]),x))(filter(\x->isInfixOf s x)n)))

```

Well, it's pretty long, maybe I'll find how to short it up a bit...
> 2 votes

# Answer
**ORACLE, 60**

Does this count?

`select * from t where a like '%mig%' order by instr(a,'mig')`
> 2 votes

# Answer
# Vyxal `r`, ~~7~~ 6 bytes

*-1 byte because I is big dumb and forgot about multi-byte lambda thingies.*

```
‡⁰e~Fṡ

```

Try it Online!

Explanation:

```
        # Implicit input - List of strings
‡       # Define lambda:
 ⁰      #   Get last input - Search string
  e     #   Regex span - Returns empty list for no match
   ~F   # Filter list by lambda without popping lambda
     ṡ  # Sort filtered list by lambda
        # Implicit output

```
> 2 votes

# Answer
## Ruby, 63

```
p=->(w,l){l.find_all{|x|x[w]}.sort{|a,b|a.index(w)-b.index(w)}}

```

Run

```
irb(main):022:0> p["mig", ["imig", "mig", "migd", "do", "Mig"]]
=> ["migd", "mig", "imig"]

```

Notes

1. First find all matching words with `find_all`
2. Sort by index position of word to be searched.

Edit (by daneiro)

## Ruby, 49

```
p=->w,l{l.select{|x|x[w]}.sort_by{|e|e.index(w)}}

```
> 1 votes

# Answer
## Pip, 15 bytes

14 bytes of code, +1 for `-p` flag.

```
Yq_@?ySKyN_FIg

```

Takes the list as command-line args and the string from stdin. Try it online!

### Explanation

```
Yq              Yank a line of stdin into y
           FIg  Filter array of cmdline args by this function:
        yN_       Count occurrences of y in arg
      SK        Sort the resulting list using this key function:
  _@?y            Index of y in arg
                Print the Pip representation of the list (implicit, -p flag)

```
> 1 votes

# Answer
# Japt, 7 bytes

```
føV ñbV

```

Try it

```
føV ñbV     :Implicit input of array U and string V
f           :Filter U by
 øV         :  Contains V?
    ñ       :Sort by
     bV     :  First index of V

```
> 1 votes

# Answer
## Racket 46 bytes

```
(for/list((i l)#:when(string-contains? i s))i)

```

Usage:

```
(define (f s l)
 (for/list((i l)#:when(string-contains? i s))i))

```

Testing:

```
(f "mig" '["imig" "mig" "migd" "do" "Mig"])

```

Output:

```
'("imig" "mig" "migd")

```
> 0 votes

# Answer
# Groovy, 32 bytes

```
{a,b->a.findAll{it.contains(b)}}

```
> 0 votes

---
Tags: code-golf
---


title: Trapezoidal Riemann Sum

text:
# Question
Title: Trapezoidal Riemann Sum
Given a list of coordinate pairs, output the Trapezoidal Riemann Sum of the values given between the first and last x-coordinates.

You will be given a sorted list of coordinate pairs, like this:

```
[
  [1,2],
  [3,5],
  [5,11]
]

```

Note that x-coordinates will always be in increasing order, ys may not.

My way to do this is (you might find a different way):

Get pairs of coordinates:

```
[1,2],[3,5] and [3,5],[5,11]

```

For each pair (let's start with the first):

* Take the average of the y-values: (2 + 5) / 2 = 7/2
* Take the difference of the x-values: 3 - 1 = 2
* Multiply the two together to get the area of that section, which is 7/2 * 2 = 7.

Do this for all pairs. Let's quickly go through the next, \[3,5\],\[5,11\].

Average of y values = (5 + 11) / 2 = 8 Difference of x values = (5 - 3) = 2 Product of the two = 2 * 8 = 16

Now take the sum of all the values, resulting in 16+7 = 23.

# Scoring

This is , shortest wins!

# Testcases

```
[ [1,2], [3,5], [5,11] ] => 23
[ [3,4], [4,1], [7,5] ] => 11.5
[ [0,0], [9,9] ] => 40.5
[ [1,1], [2,3], [3,1], [4,3] ] => 6

```

Note that input will always contain *non-negative integers*. Tell me if any of the testcases are wrong as I worked them out by hand.

You may take a flat list, or the list with x and y swapped.

# Answer
# Octave / MATLAB, 6 bytes

```
@trapz

```

Try it online!
> 1 votes

# Answer
# Ruby, ~~54 49~~ 47 bytes

```
->l{(r,=l).sum{|a|x,y,z,w=r+r=a;(y+w)/2r*z-=x}}

```

Try it online!
> 5 votes

# Answer
# Husk, 11 bytes

```
ṁΠTzẊe-o½+T

```

Try it online!

A rare question where you get to use a list of functions!

## Explanation

```
ṁΠTzẊe-o½+T
          T transpose
   z        zipwith
     e      list of 2 functions:
      -      difference
       o½+   average
    Ẋ       using pairwise reduce
  T         transpose back
ṁ           map to and sum:
 Π           product

```
> 4 votes

# Answer
# Jelly, 9 bytes

```
ạ+ƭ"P¥ƝSH

```

Try it online!

```
ạ+ƭ"P¥ƝSH  Main Link
     ¥Ɲ    For each (overlapping) pair
   "       Vectorize; apply to x coordinates then the y coordinates
  ƭ        Tie:
ạ          - for the x coordinates, absolute difference
 +         - for the y coordinates, sum
    P      Product
       S   Sum
        H  Halve

```
> 3 votes

# Answer
# Python 3, 56 bytes

```
lambda p:sum((b+d)*(c-a)/2for(a,b),(c,d)in zip(p,p[1:]))

```

Try it online!
> 3 votes

# Answer
Two more 9-byte answers:

# Jelly, 9 bytes

```
Ḣ€IḋSƝF$H

```

Try it online!

# and Jelly, 9 bytes

```
ZIḋSƝ}ɗ/H

```

Try it online!
> 3 votes

# Answer
# 05AB1E, 9 bytes

I don't think there are as many 9-byters as in Jelly, but here is one:

```
ø`ü+;s¥*O

```

Try it online!

```
          # implicit input                                      [[1,2],[3,5],[5,11]]
ø`        # tranpose and push x and y seperately to the stack   [1,3,5], [2,5,11]
  ü+      # for y coordinates: sum adjacent numbers             [1,3,5], [7,16]
    ;     # halve each value to get means                       [1,3,5], [3.5,8.0]
     s    # swap to x coordinates                               [3.5,8.0], [1,3,5]
      ¥   # get deltas, consecutive differences                 [3.5,8.0], [2,2]
       *  # element-wise multiplication                         [7.0,16.0]
        O # take the sum                                        23.0

```
> 3 votes

# Answer
# , ~~60~~ 52 bytes

```
function(l)diff(l[1,])%*%(c(l[,-1])+l)[2,-ncol(l)]/2

```

Try it online!
> 3 votes

# Answer
# , ~~55~~ 45 bytes

```
function(x,y)diff(x)%*%(y[-sum(x|1)]+y[-1])/2

```

Try it online!

*-6 bytes thanks to @Dominic*

---

For input as matrix:

### , 50 bytes

```
function(a)diff(a[1,])%*%(a[2,-ncol(a)]+a[2,-1])/2

```

Try it online!
> 3 votes

# Answer
# Jelly, 9 bytes

```
×Ø-+PʋƝSH

```

Try it online!

Assumes the second test case is in fact meant to be 11.5. Although I did admit to trying this while it was still in the Sandbox like ten minutes ago, this contains absolutely none of the code I tried while it was there :P
> 2 votes

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

```
n=>n.reduce((z,[a,b],i)=>z+=i--&&(b+n[i][1])*(a-n[i][0])/2,0)

```

Try it online!

Doing it with `map` is just as long:

---

# JavaScript (Node.js), 61 bytes

```
n=>n.map(([a,b],i)=>z+=i--&&(b+n[i][1])*(a-n[i][0])/2,z=0)&&z

```

Try it online!

---

Thanks EliteDaMyth for saving 1 byte off both answers (was a general tip)
> 2 votes

# Answer
# Python 3, 62 bytes

```
lambda l:sum((y[0]-x[0])*(x[1]+y[1])/2for x,y in zip(l,l[1:]))

```

Try it online!

-2 bytes thanks to @NahuelFouilleul
> 2 votes

# Answer
# JavaScript (ES6), 52 bytes

Given \\$n\\$ coordinate pairs, this computes \\$\sum\_{i=0}^{n-2}(y\_i+y\_{i+1})/2\times(x\_{i+1}-x\_i)\\$ recursively.

```
f=([[x,y],...a])=>a+a?([[X,Y]]=a,y+Y)/2*(X-x)+f(a):0

```

Try it online!
> 2 votes

# Answer
# Perl 5 (`-p`), 56 bytes

```
s;(\d+),(\d+)(?= (\d+),(\d+));$\+=($3-$1)*($2+$4)/2;ge}{

```

Try it online!

`-M5.01` option and `say($\),$\=""if$\;` header are needed only to run all tests otherwise the program works for one line.

example: `perl -pe 's;(\d+),(\d+)(?= (\d+),(\d+));$\+=($3-$1)*($2+$4)/2;ge}{' <<< '1,2 3,5 5,11'`

trick: `-p` option with `}{` at the end so that continue block is not executed on each iteration but at the end, and `$_` is empty so only `$\` is printed

deparse: `perl -MO=Deparse -pe 's;(\d+),(\d+)(?= (\d+),(\d+));$\+=($3-$1)*($2+$4)/2;ge}{'`
> 1 votes

# Answer
# Vyxal `s`, 11 bytes

```
ÞT÷2lvṁ$¯ȧ*

```

Try it Online!

```
ÞT          # Transpose
  ÷         # Push each to stack (y is on top
   2l       # Groups of 2
     vṁ     # Averaged
       $    # Swap to get x coords
        ¯ȧ  # Deltas
          * # Multiply the two
            # Sum that.

```

There's probably a better way :p
> 1 votes

# Answer
# Retina, 63 bytes

```
\d+
*
|""L$vm`^(_*),(_*)¶\1(_+),(_*)
$.3*$($2$4
^(__)*
$#1
_
.5

```

Try it online! Takes newline-separated pairs but link is to test suite that splits on semicolons for convenience. Explanation:

```
\d+
*

```

Convert to unary.

```
|""L$vm`^(_*),(_*)¶\1(_+),(_*)

```

Match overlapping sets of four values from two lines.

```
$.3*$($2$4

```

Multiply the difference between the first and third value by the sum of the second and fourth value.

```
^(__)*
$#1
_
.5

```

Divide by 2 and convert to decimal.
> 1 votes

# Answer
# Japt, 16 bytes

```
ÕÌä+ í*UÕÎäa)x÷2

```

Try it

```
ÕÌä+ í*UÕÎäa)x÷2     :Implicit input of array U
Õ                    :Transpose
 Ì                   :Last element
  ä+                 :Consecutive pairs, reduced by addition
     í*              :Interleave with, reducing each pair by multiplication
       UÕÎ           :  Last element of transposed U
          äa         :  Consecutive pairs, reduced by absolute difference
            )        :End interleave
             x       :Reduce by addition
              ÷2     :Divide by 2

```
> 1 votes

# Answer
# C (gcc), ~~74~~ 72 bytes

-2 thanks to @ceilingcat

```
a;r(int*x){for(a=0;~x[2];)a+=(x[2]-*x)*(*++x+x++[2]);printf("%f",a/2.);}

```

Takes input as a flat list terminated with `-1` (e.g. `{x1, y1, x2, y2, ..., -1}`)

Try it online!

---

# C (gcc), ~~78~~ 75 bytes

-3 (indirectly) thanks to @ceilingcat

```
a;r(int*x,int*y){for(a=0;~*++x;)a+=(*x-x[-1])*(*y+++*y);printf("%f",a/2.);}

```

Try it online! Takes input as a list of `x`s and a list of `y`s, terminated with `-1`.
> 0 votes

# Answer
# dc, 70 bytes

```
1k[sysxdly+2/syrdlxr-sxrlxly*lad1+sa:az4!>L]dsLxc[la1-ddsa;ar0<L+]dsLx

```

Try it online!

One decimal place of precision (`1k`) is sufficient because the longest fractional part we can have is 0.5. There could be better ways of twiddling the bits around.
> 0 votes

# Answer
# Charcoal, 24 bytes

```
Ｉ⊘ΣＥΦθκ×⁺§ι¹⊟§θκ⁻§ι⁰⊟§θκ

```

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

```
     θ                      Input array
    Φ                       Filtered on
      κ                     Current index
   Ｅ                        Map over tail
         §ι¹                Current Y-coordinate
        ⁺                   Plus
            ⊟§θκ            Previous Y-coordinate
       ×                    Multiplied by
                 §ι⁰        Current X-coordinate
                ⁻           Minus
                    ⊟§θκ    Previous X-coordinate
  Σ                         Take the sum
 ⊘                          Divide by 2
Ｉ                           Cast to string
                            Implicitly print

```
> 0 votes

---
Tags: code-golf, calculus
---