# Question
Title: Chop off the matrix to get the desired sum
## Definition

Given a matrix \\$M\\$ of non-negative integers and a non-negative integer \\$k\\$, we define \\$F\_k\\$ as the "chop-off" function that removes all rows and all columns in \\$M\\$ that contain \\$k\\$.

*Example:*

$$\begin{align}M=\pmatrix{\color{red}6&\color{red}1&\color{white}{\bbox\[red,1pt\]{5}}\\1&2&\color{red}8\\\color{red}9&\color{red}8&\color{white}{\bbox\[red,1pt\]{5}}\\6&0&\color{red}4}\\\\F\_5(M)=\pmatrix{1&2\\6&0}\end{align}$$

## Your task

Given \\$M\\$ and a target sum \\$S\\$, your task is to find all possible values of \\$k\\$ such that the sum of the remaining elements in \\$F\_k(M)\\$ is equal to \\$S\\$.

*Example:*

Given the above matrix \\$M\\$ and \\$S=9\\$:

* \\$k=5\\$ is a solution, because \\$F\_5(M)=\pmatrix{1&2\\6&0}\\$ and \\$1+2+6+0=9\\$
* \\$k=1\\$ is the only other possible solution: \\$F\_1(M)=\pmatrix{5\\4}\\$ and \\$5+4=9\\$

So the expected output would be \\$\\{1,5\\}\\$.

## Clarifications and rules

* The input is guaranteed to admit at least one solution.
* The sum of the elements in the original matrix is guaranteed to be greater than \\$S\\$.
* You may assume \\$S\>0\\$. It means that an empty matrix will never lead to a solution.
* The values of \\$k\\$ may be printed or returned in any order and in any reasonable, unambiguous format.
* You are allowed not to deduplicate the output (e.g. \\$\[1,1,5,5\]\\$ or \\$\[1,5,1,5\]\\$ are considered valid answers for the above example).
* This is .

## Test cases

```
M = [[6,1,5],[1,2,8],[9,8,5],[6,0,4]]
S = 9
Solution = {1,5}

M = [[7,2],[1,4]]
S = 7
Solution = {4}

M = [[12,5,2,3],[17,11,18,8]]
S = 43
Solution = {5}

M = [[7,12],[10,5],[0,13]]
S = 17
Solution = {0,13}

M = [[1,1,0,1],[2,0,0,2],[2,0,1,0]]
S = 1
Solution = {2}

M = [[57,8,33,84],[84,78,19,14],[43,14,81,30]]
S = 236
Solution = {19,43,57}

M = [[2,5,8],[3,5,8],[10,8,5],[10,6,7],[10,6,4]]
S = 49
Solution = {2,3,4,7}

M = [[5,4,0],[3,0,4],[8,2,2]]
S = 8
Solution = {0,2,3,4,5,8}

```

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

```
{a@&y=x{+//x*(&/'b)&\:&/b:~x=y}/:a:,/x}

```

Try it online!

*thanks @Adám for this explanation*:

`{``}` function, `x` is *M* and `y` is *S*

`,/x` flatten *M* (these are the *k* candidates)

`a:` assign to `a`

`x{``}/:` apply the following function to each while using *M* as fixed left argument (`x`):

`x=y` Boolean matrix indicating where elements of *M* equal the current *k* candidate

`~` negate that

`b:` assign that to `b`

`&/` AND reduction (finds columns without that *k*)

`(``)&\:` AND that with each of the following:

`&/'b` AND reduction of each (finds rows without that *k*)

`x*` multiply *M* by that

`+//` grand sum

`y=` list of Booleans indicating where *S* equals those sums

`&` indices of Trues

`a@` use that to index into the elements (the *k* candidates)
> 10 votes

# Answer
# APL (Dyalog Unicode), ~~35~~ ~~33~~ 28 bytesSBCS

-7 thanks to ngn.

Anonymous infix lambda. Takes *S* as left argument and *M* as right argument.

```
{⍵[⍸⍺=(+/∘,⍵×∧/∘.∧∧⌿)¨⍵≠⊂⍵]}

```

Try it online!

`{``}` "dfn",  and  are left and right arguments (*S* and *M*) respectively:

`⍵[``]` index *M* with the following coordinates:

`⊂⍵` enclose *M* to treat it as a single element

`⍵=` compare each element (i.e. *k* candidate) of *M* to that entire *M*

`(` apply the following tacit function to each:

`∧⌿` vertical AND reduction (finds columns without that *k* candidate)

`∘.∧` Cartesian Boolean product with:

`∧/` horizontal AND reduction (finds rows without that *k* candidate)

`⍵×` multiply *M* with that mask

`+/∘,` sum the flattened matrix

`⍺=` Boolean indicating where *S* equals those sums

indices where that's true
> 6 votes

# Answer
# , ~~78~~ 73 bytes

```
function(m,s)m[Map(function(y)sum(m[(w=-which(m==y,T))[,1],w[,2]]),m)==s]

```

Try it online!

Does not sort or deduplicate the output.

Credit to J.Doe & Giuseppe for -5 bytes.
> 6 votes

# Answer
# Pyth,  ~~27 23 22 21~~  20 bytes

```
fqvzss.DRsxLTQ-I#TQs

```

**Test suite!**

Does not deduplicate.

### How it works?

```
fqvzss.DRsxLTQ-I#TQs     Full program.
f                  s     Flatten M and keep only those elements T which satisfy:
 qvzss.DRsxLTQ-I#TQ      The filtering function. Breakdown:
              -I#TQ      Discard the rows that contain T. More elaborate explanation:
                # Q         |-> In M, keep only those elements that are...
               I            |-> Invariant under (equal to themselves after...)
              -  T          |-> Removing T.
                         Let's call the result of this expression CR (chopped rows).
          xLTQ           Map over the rows M and retrieve all indices of T.
         s               Collect indices in 1D list (flatten). Call this I.
      .DR                For each row left in CR, remove the elements at indices in I.
    ss                   Sum all the elements of this matrix flattened.
 qvz                     And then finally check whether they equal S.

```
> 5 votes

# Answer
# Haskell, ~~88~~ ~~86~~ ~~84~~ 77 bytes

```
m!s=[k|k<-m>>=id,s==sum[x|r<-m,all(/=k)r,(i,x)<-zip[0..]r,all((/=k).(!!i))m]]

```

Verify all testcases.

## Explanation

```
m ! s =                                         -- function !, taking m and s as input
    [k |                                        -- the list of all k's such that
        k <- m >>= id,                          -- * k is an entry of m
        s == sum                                -- * s equals the sum of
            [x |                                --     the list of x's such that
                r <- m,                         --     * r is a row of m
                all (/= k) r,                   --     * r does not contain k
                (i, x) <- zip [0 ..] r,         --     * i is a valid column index; also let x = r[i]
                all ((/= k) . (!! i)) m         --     * none of the rows contain k at index i
            ]
    ]

```
> 5 votes

# Answer
# Jelly, ~~20~~ ~~19~~ ~~17~~ ~~15~~ 14 bytes

```
pZnⱮFȦ€€ḋFẹƓịF

```

This is a monadic link that takes **M** as argument and reads **S** from STDIN.

Try it online!

### How it works

```
pZnⱮFȦ€€ḋFẹƓịF  Main link. Argument: M

 Z              Zip; transpose the rows and columns of M.
p               Take the Cartesian product of M and its transpose, yielding all pairs
                (r, c) of rows and columns of M.
    F           Flatten; yield the elements of M.
  nⱮ            Not equal map; for each element e of M, compare the elements of the
                pairs (r, c) with e.
     Ȧ€€        All each each; for each array of Booleans corresponding to an (r, c)
                pair, test if all of them are true.
         F      Flatten; yield the elements of M.
        ḋ       Take the dot product of each list of resulting Booleans and the
                elements of M.
           Ɠ    Read an integer S from STDIN.
          ẹ     Find all indices of S in the dot products.
             F  Flatten; yield the elements of M.
            ị   Retrieve the elements of the right at the indices from the left.

```
> 5 votes

# Answer
# Python 2, ~~114~~ 108 bytes

```
lambda m,s:{a for a in sum(m,[])if s==sum(v for l in m for i,v in enumerate(l)if{a}-set(l)-set(zip(*m)[i]))}

```

Try it online!
> 4 votes

# Answer
# Perl 6, ~~80~~ 74 bytes

```
->\m,\s{grep {s==sum m[m.$_;[[Z](m).$_]]}o{*.grep(:k,!*.grep($_))},m[*;*]}

```

Try it online!

### Explanation

```
->\m,\s{...}  # Anonymous block taking arguments m and s
  grep {...}o{...},m[*;*]   # Filter matrix elements
                            # with combination of two functions
    *.grep(:k,!*.grep($_))  # (1) Whatever code returning matching rows
    s==sum m[               # (2) s equals sum of elements
      m.$_;                 #     in matched rows
      [                     #     (array supporting multiple iterations)
       [Z](m).$_            #     and matched columns (matched rows
                            #     of m transposed with [Z])
      ]
    ]

```
> 4 votes

# Answer
# 05AB1E, 21 bytes

```
²˜ʒQεZ+}øεZ<~}ø_*OO¹Q

```

Try it online!

Only after I've written this answer have I seen Kevin's. I believe this is substantially different, so I am posting it separately. My intuition says that the optimal byte count is around 18, so I'll have to revisit this and see what else I can do. With the current code, it is impossible to write a test suite but I have verified all test cases myself and the results are correct.

### Cropping Algorithm

To better illustrate the technique used, let's grab an example, with the element to crop \\$k=5\\$:

$$M=\left(\begin{matrix}6&1&\bbox\[green,1pt\]{\color{white}{5}}\\1&2&8\\9&8&\bbox\[green,1pt\]{\color{white}{5}}\\6&0&4\end{matrix}\right)$$

It first generates the matrix of equality with \\$k\\$:

$$\left(\begin{matrix}0&0&1\\0&0&0\\0&0&1\\0&0&0\end{matrix}\right)$$

Then, it goes through \\$M\\$ and for each row \\$R\\$, it adds \\$\max(R)\\$ to each element in \\$R\\$, highlighting the necessary rows while still preserving the uniqueness of the horizontal positions of the searched element:

$$\left(\begin{matrix}\color{green}{1}&\color{green}{1}&\bbox\[green,1pt\]{\color{white}{2}}\\0&0&0\\\color{green}{1}&\color{green}{1}&\bbox\[green,1pt\]{\color{white}{2}}\\0&0&0\end{matrix}\right)$$

Then, it goes through the transpose of \\$M\\$ and for each column \\$C\\$, it performs the operation \\$(\max(C)-1)\space ||\space c\space\forall\space c\in C\\:\\$ (where \\$||\\$ is 05AB1E's bitwise OR – addition should work too, so replace `~` with `+` if you want to test that too), which results in:

$$\left(\begin{matrix}\color{green}{1}&\color{green}{1}&\bbox\[green,1pt\]{\color{white}{3}}\\0&0&\color{green}{1}\\\color{green}{1}&\color{green}{1}&\bbox\[green,1pt\]{\color{white}{3}}\\0&0&\color{green}{1}\end{matrix}\right)$$

Finally, it maps \\$0\\$ to \\$1\\$ and all other integers to \\$0\\$ and performs element-wise multiplication with \\$M\\$:

$$\left(\begin{matrix}\color{green}{0}&\color{green}{0}&\color{green}{0}\\1&1&\color{green}{0}\\\color{green}{0}&\color{green}{0}&\color{green}{0}\\1&1&\color{green}{0}\end{matrix}\right)\\:\longrightarrow\\:\left(\begin{matrix}\color{green}{0}&\color{green}{0}&\color{green}{0}\\1&2&\color{green}{0}\\\color{green}{0}&\color{green}{0}&\color{green}{0}\\6&0&\color{green}{0}\end{matrix}\right)$$

After which the sum of the resulting matrix is computed.
> 3 votes

# Answer
# 05AB1E (legacy), ~~27~~ 26 bytes

```
˜ʒ©¹ε®å_}¹ζʒ®å_}ζ‚ζ€€OPOIQ

```

Does not sort nor uniquify the result.
Only works in the legacy (for now), because sum-each seems to be doing some odd things when part of the inner lists are integers and other are lists..

Try it online or verify all test cases.

**Explanation:**

```
˜              # Flatten the (implicit) matrix-input
               #  i.e. [[6,1,5],[1,2,8],[9,8,5],[6,0,4]] → [6,1,5,1,2,8,9,8,5,6,0,4]
 ʒ             # Filter this list by:
  ©            #  Store the current value in a register-variable
   ¹           #  Take the matrix-input
    ε   }      #  Map it to:
     ®å_       #   0 if the current number is in this row, 1 if not
               #    i.e. [[6,1,5],[1,2,8],[9,8,5],[6,0,4]] and 6 → [0,1,1,0]
   ¹           #  Take the matrix-input again
    ζ          #  Swap its rows and columns
               #   i.e. [[6,1,5],[1,2,8],[9,8,5],[6,0,4]] → [[6,1,9,6],[1,2,8,0],[5,8,5,4]]
     ʒ   }     #  Filter it by:
      ®å_      #   Only keep the inner lists that does not contain the current number
               #    i.e. [[6,1,9,6],[1,2,8,0],[5,8,5,4]] and 6 → [[1,2,8,0],[5,8,5,4]]
               #    i.e. [[1,2,2],[1,0,0],[0,0,1],[1,2,0]] and 1 → []
          ζ    #  After filtering, swap it's rows and columns back again
               #   i.e. [[1,2,8,0],[5,8,5,4]] → [[1,5],[2,8],[8,5],[0,4]]
   ‚ζ          #  Pair both lists together and zip them
               #   i.e. [0,1,1,0] and [[1,5],[2,8],[8,5],[0,4]]
               #    → [[0,[1,5]],[1,[2,8]],[1,[8,5]],[0,[0,4]]]
               #   i.e. [0,1,0] and [] → [[0,' '],[1,' '],[0,' ']]
     €         #  Map each inner list / value to:
      €O       #   Sum each
               #    i.e. [[0,[1,5]],[1,[2,8]],[1,[8,5]],[0,[0,4]]]
               #     → [[0,6],[1,10],[1,13],[0,4]]
               #    i.e. [[0,' '],[1,' '],[0,' ']]
               #     → [[0,0],[1,0],[0,0]]
               #  (NOTE: For most test cases just `O` instead of `€€O` would be enough,
               #   but not if we removed ALL zipped inner lists for a number, like the
               #   second example above with input [[1,1,0,1],[2,0,0,2],[2,0,1,0]] and 1)
        P      #  Now take the product of each inner list
               #   i.e. [[0,6],[1,10],[1,13],[0,4]] → [0,10,13,0]
         O     #  Then take the sum of those
               #   i.e. [0,10,13,0] → 23
          IQ   #  And only keep those that are equal to the number-input
               #   i.e. 23 and 9 → 0 (falsey), so it's removed from the flattened input

```
> 2 votes

# Answer
# Jelly, 22 bytes

```
=+Ṁ$€Z$⁺’¬×⁸FS
F³ç=⁹ƲƇ

```

Try it online!

-6 bytes using the general approach from Mr. Xcoder's 05AB1E answer.
> 1 votes

# Answer
# Charcoal, 33 bytes

```
ＦθＦι⊞υκＩΦυ⁼ηΣＥθ∧¬№λιΣＥλ∧¬№Ｅθ§πξιν

```

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

```
ＦθＦι⊞υκ

```

Flatten the first input array `q` into the predefined list `u`.

```
  υ                          Flattened array
 Φ                           Filter elements
       θ                     Input array
      Ｅ                      Map over rows
            ι                Current element
           λ                 Current row
          №                  Count matching elements
         ¬                   Logical Not
        ∧                    Logical And
               λ             Current row
              Ｅ              Map over columns
                    θ        Input array
                   Ｅ         Map over rows
                      π      Inner row
                       ξ     Column index
                     §       Inner element
                        ι    Current element
                  №          Count matching elements
                 ¬           Logical Not
                ∧            Logical And
                         ν   Current element
             Σ               Sum
     Σ                       Sum
    η                        Second input
   ⁼                         Equals
Ｉ                            Cast to string
                             Implicitly print each result on its own line

```

For each element of the list, sum the array, but if the row contains the element then use `0` instead of its sum, and when summing rows that don't contain the element, if the column contains the element then use `0` instead of the column's value. This is very slightly golfier than filtering the elements out as Charcoal can't sum an empty list.
> 1 votes

# Answer
## MATLAB - 80 bytes

(*Corrected and*) Compacted:

```
function f(M,s);for k=M(:)';if sum(sum(M(~sum(M==k,2),~sum(M==k))))==s;k,end;end

```

And in a fully developped version:

```
function getthesum(M,s)

for k=M(:)'                         % For each element of M
    x = M==k ;                      % Index elements equal to "k"
    N = M( ~sum(x,2) , ~sum(x) ) ;  % New matrix with only the appropriate rows/columns
    if sum(sum(N))==s               % sum rows and columns and compare to "s"
        k                           % display "k" in console if "k" is valid
    end
end

```

---

Thanks to the comments to highlight my initial mistake. Note that this version does not de-duplicate the output.

It is possible to deduplicate the output with 5 more bytes:

```
% This will only cycle through the unique elements of 'M' (85 bytes):

function f(M,s);for k=unique(M)';if sum(sum(M(~sum(M==k,2),~sum(M==k))))==s;k,end;end

```
> 1 votes

# Answer
# Clean, 92 bytes

```
import StdEnv
$m s=[c\\r<-m,c<-r|sum[b\\a<-m|all((<>)c)a,b<-a&x<-[0..]|all(\u=u!!x<>c)m]==s]

```

Try it online!

Explained:

```
$ m s                       // the function $ of `m` and `s`
 = [                        // is equal to
  c                         // the value `c`
  \\ r <- m                 // for every row `r` in `m`
  , c <- r                  // for every value `c` in `r`
  | sum [                   // where the sum of
   b                        // the value `b`
   \\ a <- m                // for every row `a` in `m`
   | all ((<>)c) a          // where `c` isn't in `a`
   , b <- a                 // for every value `b` in `a`
   & x <- [0..]             // with every column index `x` from zero
   | all (\u = u!!x <> c) m // where `c` isn't in column `x`
  ] == s                    // equals `s`
 ]

```
> 1 votes

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


title: A Knotty situation

text:
# Question
Title: A Knotty situation
Given the Dowker notation of a knot and its crossing signs, calculate its bracket polynomial.

Although there are more technical definitions, for this challenge it is enough to think of a **knot** as something made physically by attaching the two ends of a string together. Since knots exist in three dimensions, when we draw them on paper, we use **knot diagrams** \- two-dimensional projections in which the crossings are of exactly two lines, one over and one under.

Here (b) and (c) are different diagrams of the same knot.

How do we represent a knot diagram on paper? Most of us aren't Rembrandt, so we rely on **Dowker notation**, which works as follows:

Pick an arbitrary starting point on the knot. Move in an arbitrary direction along the knot and number the crossings you encounter, starting from 1, with the following modification: if it's an even number and you're currently going *over* the crossing, negate that even number. Finally, pick the even numbers corresponding to 1, 3, 5, etc.

Let's try an example:

Taken with permission from wikimedia user Czupirek

On this knot, we chose "1" as our starting point and proceeded to move up and to the right. Every time we go *over* or *under* another piece of the rope, we assign the crossing point the next natural number. We negate the even numbers corresponding to strands that go over a crossing, for example `[3,-12]` in the diagram. So, this diagram would be represented by `[[1,6],[2,5],[3,-12],[-4,9],[7,8],[-10,11]]`. Listing the buddies of 1, 3, 5, 7, etc gives us `[6,-12,2,8,-4,-10]`.

There are a few things to note here. First, the Dowker notation is *not* unique for a given knot, as we can choose an arbitrary starting point and direction. But, given the notation, one can fully determine the structure of the knot (technically, up to reflection of its prime knot components). While not all Dowker notations can form possible knots, in this problem you can assume that the input represents an actual knot.

To avoid the ambiguity between a knot's reflections, and to make the challenge easier to solve, you will also be given a list of **crossing signs** as input.

In a positive crossing the lower line goes to the left from the point of view of the upper line. In a negative crossing it goes to the right. Note that reversing the direction of going around the knot (i.e. reversing both the *over* line and *under* line) doesn't change the crossing signs. In our example the crossing signs are `[-1,-1,-1,1,-1,1]`. They are given in the same order as the Dowker notation, i.e. for crossings numbered 1, 3, 5, 7, etc.

In this challenge we will be calculating the **bracket polynomial** of a knot. It's an object that is invariant across most transformation of the knot diagram - a concept which makes it supremely useful in knot theory analysis. (Again, most knot theorists compute the bracket polynomial as an intermediate product on their way to computing the Jones polynomial, which is invariant across *all* transformations, but we will not be doing that.) So how does it work? The bracket polynomial is a Laurent polynomial - one in which the variable (traditionally named \\$A\\$) can be raised to negative powers, as well as positive.

For a given knot diagram \\$D\\$, the three rules for the polynomial, represented as \\$\langle D\rangle\\$, are:

1. A sole loop without any crossings has polynomial 1.
2. If we have a diagram consisting of \\$D\\$ and a loop disconnected from \\$D\\$, the polynomial for both is the polynomial for \\$D\\$ times \\$(-A^2-A^{-2})\\$.
3. This rule is the trickiest. It says that if you have a crossing in \\$D\\$ that looks like , then you can use this rule to simplify the knots in two different ways:

In the image above, the outlined crossing in the first diagram, which is of the form , can be transformed into  as in the second figure (a.k.a. **positive smoothing**), or  as in the third figure (**negative smoothing**).

So, the bracket polynomial of the first diagram is the bracket polynomial of the second times \\$A\\$ plus the third times \\$A^{-1}\\$, i.e.,

Confused yet? Let's do an example, trying to find the bracket polynomial of  (Note: this is two knots linked together. This sort of diagram will not be a potential input in this challenge since the inputs will only be single knots, but it may appear as an intermediate result in the algorithm.)

We first use rule 3

We use rule 3 again on both of the new knots

We substitute these 4 new knots into the first equation.

Applying rules 1 and 2 to these 4 tell us

So, this tell us

Congrats on completing your brief intro to knot theory!

# Input

Two lists:

* Dowker notation, e.g. `[6,-12,2,8,-4,-10]`. Numbering of the crossings must start from 1. The corresponding odd numbers `[1,3,5,7,...]` are implicit and must *not* be provided as input.
* Signs (`1`/`-1` or if you prefer `0`/`1` or `false`/`true` or `'+'`/`'-'`) for the crossings corresponding to the Dowker notation, e.g `[-1,-1,-1,1,-1,1]`.

Instead of a pair of lists, you could have a list of pairs, e.g. `[[6,-1],[-12,-1],...`

# Output

Print or return the polynomial, for instance \\$A^{-2}+5+A-A^3\\$, as a list of coefficient-exponent pairs (or exponent-coefficient pairs) in increasing order of the exponents and without any zero coefficients, e.g. `[[1,-2],[5,0],[1,1],[-1,3]]`.

Alternatively, output an odd-length list of coefficients correspondings to exponents \\$-k\ldots k\\$ for some \\$k\in \mathbb{N}\\$, e.g. `[0,1,0,5,1,0,-1]`. The central element is the constant term (coefficient before \\$A^0\\$). The leftmost and rightmost elements must not be both 0.

# Rules

This is a challenge. None of the standard loopholes can be used, and libraries that have tools to calculate either Dowker notations, or Bracket polynomials, cannot be used. (A language that contains these libraries still can be used, just not the libraries/packages).

# Tests

```
// 4-tuples of [dowker_notation, crossing_signs, expected_result, description]
[
 [[],[],[[1,0]],"unknot"],
 [[2],[1],[[-1,3]],"unknot with a half-twist (positive crossing)"],
 [[2],[-1],[[-1,-3]],"unknot with a half-twist (negative crossing)"],
 [[2,4],[1,1],[[1,6]],"unknot with two half-twists (positive crossings)"],
 [[4,6,2],[1,1,1],[[1,-7],[-1,-3],[-1,5]],"right-handed trefoil knot, 3_1"],
 [[4,6,2,8],[-1,1,-1,1],[[1,-8],[-1,-4],[1,0],[-1,4],[1,8]],"figure-eight knot, 4_1"],
 [[6,8,10,2,4],[-1,-1,-1,-1,-1],[[-1,-7],[-1,1],[1,5],[-1,9],[1,13]],"pentafoil knot, 5_1"],
 [[6,8,10,4,2],[-1,-1,-1,-1,-1],[[-1,-11],[1,-7],[-2,-3],[1,1],[-1,5],[1,9]],"three-twist knot, 5_2"],
 [[4,8,10,2,12,6],[1,1,-1,1,-1,-1],[[-1,-12],[2,-8],[-2,-4],[3,0],[-2,4],[2,8],[-1,12]],"6_3"],
 [[4,6,2,10,12,8],[-1,-1,-1,-1,-1,-1],[[1,-10],[2,-2],[-2,2],[1,6],[-2,10],[1,14]],"granny knot (sum of two identical trefoils)"],
 [[4,6,2,-10,-12,-8],[1,1,1,1,1,1],[[1,-14],[-2,-10],[1,-6],[-2,-2],[2,2],[1,10]],"square knot (sum of two mirrored trefoils)"],
 [[6,-12,2,8,-4,-10],[-1,-1,-1,1,-1,1],[[1,-2],[1,6],[-1,10]],"example knot"]
]

```

# External resources

Not necessary for the challenge, but if you are interested:

---

sandbox posts: ,

thanks @ChasBrown and @H.Pwiz for catching a mistake in my definition of Dowker notation

# Answer
# K (ngn/k), ~~196 193 185 177~~ 172 bytes

-2 bytes thanks to @coltim

```
{N::2*n:#x;+/(-m-|/m:#'b)(|0,)/'b:(+/1-2*s){,/(&0|2*x;(#1_?{y[x]&:y@|x;y}[+,/y]/!N){-x+|x,:&4}/1;&0|-2*x)}'N!({(x,'1+|x;x+/:!2)}'(0<x)|:/'+(2*!n;-1+x|-x))@'/:+(0<y)=s:!n#2}

```

Try it online!

ungolfed:

```
f:{                                      /args: x:dowker notation, y:crossing signs
 N::2*n:#x                               /n:number of crossings, N:twice n
 s:1-2*!n#2                              /s:all possible sets of smoothing signs for the crossings (n*(2^n) matrix of -1 1)
 S:{(x,'1+|x;0 1+\:x:(0<x)|:/y,-1+x|-x)} /S:smoothe the crossing numbered x,y in dowker notation (x can be negative)
 a:N!(x S'2*!n)@'/:+~y=s                 /generate all possible smoothed knots (results consist of neighbour pairs that form sets of disjoint unknots)
 u::{#1_?{y[x]&:|y x;y}[+,/x]/!N}        /count number of disjoint unknots in a smoothed knot, minus one
 /       ^^^^^^^^^^^^^^^^^^^^^           /  transitive closure
 g::{-x+|x,:&4}                          /if x=L(A) is a laurent polynomial represented as list of coefficients centred on A^0 (the constant term)
 /                                       /  then g[x] represents (-A^2-A^(-2))*L(A)
 b:(+/s){,/(0<x)|:/(u[y]g/1;&2*x|-x)}'a  /build a laurent polynomials for each set of smoothing signs
 +/(-m-|/m:#'b)(|0,)/'b}                 /centre them and pad them to form a matrix and sum them to get the bracket polynomial

```
> 16 votes

# Answer
# Brain-Flak, 1316 bytes

```
(({})<({()<(({}<>))><>}){(({})[()()]<{([{}]({})<>({}<>))}{}(([({}<>)]<<>({}<>)<>((({})<<>{({}<>)<>}<>>))>)){({}<>)<>}<>{}(({}<{}(({}<{({}<>)<>}>))>))<>{({}<>)<>}>)}<>>){(({}){}()<({}<>)>)<>{}(({}){}<>)<>}<>{}{}(()){(<({}<({}<>)>)>)<>((){[()](<(({})<>){({}[({})]<>({}<>))}{}({}<>({}<{}<>{({}<>)<>}>)[()])<>({}({})[()])(([()]{()(<({}[({})]())>)}{})<{(<{}{}>)}{}><>{()((<({}()[({}<>)])<>>))}{}<{}{}>)((){[()]<({}()<({}<({}<<>({()<({}<>)<>>}<>){({}[()]<(({})<({()<({}<>)<>>})<>>)<>{({}[()]<<>({}<>)>)}{}>)}<>>)<>>)>)((){[()](<{}(({})<<>(({})<(<<>({}<<>({}<(()()){({}[()]<([{}]()<>)<>({}<<>{({}({})<>[({}<>)])}{}{}>){({}<>)<>}<>>)}{}>{})>)>)<>{}{({}<>)<>}<>([({}<>)]<((()))>)(())<>({}<>)<>{}({}[()]){<>({}<<>(()()){({}[()]<({}<<>{({}<>)<>}>){({}[({})]<>({}<>))}{}(({})<<>({}<>)<>([{}])>)>)}{}{}>)<>({}<(({})())>[()]<>)}{}({}<<>{}([{}]()<{({}<>)<>}>){({}({})<>[({}<>)])}{}{}>){({}<>)<>}<>{}{}{}>{})>)>)}{}){(<{}(({})<<>(({}{})<<>(<({}<>)>)<>{}{({}<>)<>}<>>(({}){}){})>)>)}>}{}){(<{}([{}]<({}<<>([{}]()<>)<>({}<<>{({}({})<>[({}<>)])}{}{}>){({}<>)<>}<>>({})({}){})>)>)}{}>)}{}){{}(([{}]){}<>{}{}<<>({}<>{}){([{}]({}()()<{}({}<>)(())<>>))}{}{}{}>{})(())<>{{}({}<>)(())<>}(<>)<>}{}}{}{}<>{}{}({}<{{}({}<>)(())<>}<>{{}{((<(())>))}{}}{}{{}({}<>)(())<>}>)<>{{}({}<(<()>)<>([]){{}({}<>)(())<>([])}{}>)<>{{}({}<>)<>}{}{}({}<>)<>}<>

```

Try it online!

I regret nothing. Input is a flattened list of pairs.

```
# Part 1: extract edges
(({})<

({()<(({}<>))><>}){

(({})[()()]<

{([{}]({})<>({}<>))}{}(([({}<>)]<<>({}<>)<>((({})<<>{({}<>)<>}<>>))>)){({}<>)<>}

<>{}(({}<{}(({}<{({}<>)<>}>))>))<>{({}<>)<>}

>)}

<>>){(({}){}()<({}<>)>)<>{}(({}){}<>)<>}<>

{}{}(())

# Part 2: Compute bracket polynomial
{

  # Move degree/sign to other stack
  (<({}<({}<>)>)>)<>

  # If current shape has crossings:
  ((){[()](<

    # Consider first currently listed edge in set
    # Find the other edge leaving same crossing
    (({})<>){({}[({})]<>({}<>))}{}

    # Move to top of other stack
    # Also check for twist
    ({}<>({}<{}<>{({}<>)<>}>)[()])

    # Check for twist in current edge
    <>({}({})[()])

    (

      # Remove current edge if twist
      ([()]{()(<({}[({})]())>)}{})<{(<{}{}>)}{}>

      # Remove matching edge if twist
      <>{()((<({}()[({}<>)])<>>))}{}<{}{}>

    # Push 1 minus number of twists from current vertex.
    )

    # If number of twists is not 1:
    ((){[()]<

      # While testing whether number of twists is 2:
      ({}()<

        # Keep sign/degree on third stack:
        ({}<({}<

          # Duplicate current configuration
          <>({()<({}<>)<>>}<>){({}[()]<(({})<({()<({}<>)<>>})<>>)<>{({}[()]<<>({}<>)>)}{}>)}

        # Push sign and degree on separate stacks
        <>>)<>>)

      # If number of twists is not 2: (i.e., no twists)
      >)((){[()](<{}

        # Make first copy of sign/degree
        (({})<<>(({})<

          # Make second copy of sign/degree
          (<<>({}<<>({}<

            # Do twice:
            (()()){({}[()]<

              # Prepare search for vertex leading into crossing on other side
              ([{}]()<>)

              # While keeping destination on third stack:
              <>({}<

                # Search for matching edge
                <>{({}({})<>[({}<>)])}{}

              # Replace old destination
              {}>)

              # Move back to original stack
              {({}<>)<>}<>

            >)}{}

          # Add orientation to degree
          >{})>)>)

          # Move duplicate to left stack
          <>{}{({}<>)<>}<>

          # Create "fake" edges from current crossing as termination conditions
          ([({}<>)]<((()))>)(())<>

          # Create representation of "top" new edge
          ({}<>)<>{}({}[()])

          # While didn't reach initial crossing again:
          {

            # Keep destination of new edge on third stack
            <>({}<<>

              # Do twice:
              (()()){({}[()]<

                # Search for crossing
                ({}<<>{({}<>)<>}>){({}[({})]<>({}<>))}{}

                # Reverse orientation of crossing
                (({})<<>({}<>)<>([{}])>)

              >)}{}

              # Remove extraneous search term
              {}

            # Push new destination for edge
            >)

            # Set up next edge
            <>({}<(({})())>[()]<>)

          }

          # Get destination of last edge to link up
          {}({}<

            # Find edge headed toward original crossing
            <>{}([{}]()<{({}<>)<>}>){({}({})<>[({}<>)])}

          # Replace destination
          {}{}>)

          # Move everything to left stack
          {({}<>)<>}

          # Clean up temporary data
          <>{}{}{}

        # Push new sign/degree of negatively smoothed knot
        >{})>)

      # Else (two twists)
      # i.e., crossing is the twist in unknot with one half-twist
      >)}{}){(<{}

        # Copy sign and degree+orientation
        (({})<<>(({}{})<

          # Move sign to left stack
          <>(<({}<>)>)

          # Move copy of configuration to left stack
          <>{}{({}<>)<>}

        # Add an additional 4*orientation to degree
        <>>(({}){}){})>)

      >)}

    # Else (one twist)
    >}{}){(<

      # Invert sign and get degree
      {}([{}]<({}<

        # Search term for other edge leading to this crossing
        <>([{}]()<>)

        # With destination on third stack:
        <>({}<

          # Find matching edge
          <>{({}({})<>[({}<>)])}{}

        # Replace destination
        {}>)

        # Move stuff back to left stack
        {({}<>)<>}<>

      # Add 3*orientation to degree
      >({})({}){})>)

    >)}{}

  # Else (no crossings)
  >)}{}){{}

    # If this came from the 2-twist case, undo splitting.
    # If this came from an initial empty input, use implicit zeros to not join anything
    # New sign = sign - 2 * next entry sign
    (([{}]){}<>{}{}<

      # New degree = average of both degrees
      <>({}<>{})

      # Find coefficient corresponding to degree
      {([{}]({}()()<{}({}<>)(())<>>))}{}{}

    # Add sign to coefficient
    {}>{})

    # Move rest of polynomial back to right stack
    (())<>{{}({}<>)(())<>}

    # Set up next configuration
    (<>)<>

  }{}

}{}{}<>{}

# Step 3: Put polynomial in correct form

# Keeping constant term:
{}({}<

  # Move to other stack to get access to terms of highest absolute degree
  {{}({}<>)(())<>}<>

  # Remove outer zeros
  {{}{((<(())>))}{}}

  # Move back to right stack to get access to lower order terms
  {}{{}({}<>)(())<>}

>)<>

# While terms remain:
{

  # Move term with positive coefficient
  {}({}<(<()>)<>([]){{}({}<>)(())<>([])}{}>)<>{{}({}<>)<>}{}

  # Move term with negative coefficient
  {}({}<>)<>

}<>

```
> 20 votes

---
Tags: code-golf, knot-theory
---


title: Necklace splitting problem

text:
# Question
Title: Necklace splitting problem
## Background

I was inspired by 3Blue1Brown's recent video about the necklace splitting problem (or as he calls it, the stolen necklace problem) and its relationship to the Borsuk-Ulam theorem.

In this problem, two thieves have stolen a valuable necklace consisting of several different types of jewels. There are an even number of each type of jewel and the thieves wish to split each jewel type evenly amongst the two of them. The catch is that they must do so by splitting the necklace into some number of contiguous segments and distribute the segments between the two of them.

Here is an example with four jewel types denoted `S`, `E`, `D`, and `R` (for sapphire, emerald, diamond, and ruby, respectively). Let's say the necklace is as follows:

```
[S,S,S,E,S,D,E,R,S,R,E,S,S,S,D,R,E,E,R,E,D,E,R,R,D,E,E,E]

```

There are `8` sapphires, `10` emeralds, `4` diamonds, and `6` rubies. We can split the necklace as follows:

```
[[S],[S],[S,E,S,D,E,R,S],[R,E,S,S,S,D,R,E,E,R,E,D,E],[R,R,D,E,E,E]]

```

Then if we give the first, third, and fifth segments to one thief and the second and fourth segments to the other thief, each will end up with `4` sapphires, `5` emeralds, `2` diamonds, and `3` rubies:

```
[S],    [S,E,S,D,E,R,S],                            [R,R,D,E,E,E]
    [S],                [R,E,S,S,S,D,R,E,E,R,E,D,E],

```

Using `0`-indexing, these cuts occur at the indices `[1,2,9,22]`.

## Goal

It turns out that such a fair division can always be done using at most `n` cuts, where `n` is the number of jewel types. Your task is to write a complete program or function which takes a necklace as input and outputs a minimal such division (fewest number of cuts).

## Input

Input may be in any convenient format. The necklace should be a sequence of jewels and nothing more; e.g. a list of integers, dictionary with keys representing the jewel types and values being lists of indices. You may optionally include the length of the necklace or the number of distinct jewel types, but you should not take any other input.

You may assume that the input necklace is valid. You do not need to handle the case where there is an odd number of jewels of a given type or the necklace is empty.

## Output

Again, output may be in any convenient format; e.g. a list of segments, a list of cut positions, a dictionary with keys representing the two thieves and values being lists of segments, etc. Segments may be represented by their starting index, ending index, list of consecutive indices, list of jewels, their lengths, etc. You may use `0`\- or `1`\- indexing. If the ordering is not significant to your format, then your output may be in any order. Here is the above output in several different formats:

```
list of segments: [[S],[S],[S,E,S,D,E,R,S],[R,E,S,S,S,D,R,E,E,R,E,D,E],[R,R,D,E,E,E]]
list of cuts:     [1,2,9,22]
list of lengths:  [1,1,7,13,6]
dictionary:       {'thief1' : [(R,R,D,E,E,E),(S),(S,E,S,D,E,R,S)], 'thief2' : [(S),(R,E,S,S,S,D,R,E,E,R,E,D,E)]}

```

Note that order is important in the list of segments (segments alternate between the thieves) and the list of lengths (in order to identify the segments), but not in the list of cuts or the dictionary. *Edit: Greg Martin pointed out that these wouldn't be valid outputs since a fair division can be obtained in two cuts*

## Test cases

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

```

## Notes

1. Standard loopholes are forbidden.
2. This is ; shortest answer (in bytes) wins.

# Answer
# Brachylog, 13 bytes

```
~c.ġ₂z₁Ċcᵐoᵛ∧

```

Try it online!

Note: the metapredicate  is newer than this challenge.

## Explanation

```
~c.ġ₂z₁Ċcᵐoᵛ∧  Input is a list, say L = [1,2,2,2,1,2,3,3]
~c.            Output is a partition of the input: [[1,2,2],[2,1,2],[3],[3]]
  .ġ₂          Split the output into chunks of length 2: [[[1,2,2],[2,1,2]],[[3],[3]]]
     z₁        Zip (transpose) the chunks: [[[1,2,2],[3]],[[2,1,2],[3]]]
       Ċ       This is a 2-element list (forbid the trivial partition).
        cᵐ     Concatenate both: [[1,2,2,3],[2,1,2,3]]
          oᵛ   If you sort both lists, they are equal.
            ∧  Don't unify with the output.

```

The partitions are enumerated in increasing order of the number of blocks, so the result will have as few blocks as possible.
> 3 votes

# Answer
# Jelly, 18 bytes

```
s2ZFṢ$€E¬,L
ŒṖṖÇÞḢ

```

**Try it online!**

Not efficient - the example has **28** jewels which wont work without huge resources since this implementation's first step would be to build a list of the **227** possible partitions.

Returns a list of lists - the segments in the order to dish them out between alternate thieves. (Re the TIO output: when a list only has a single item the implicit print does not bother with the brackets, `[]`)

### How?

```
s2ZFṢ$€E¬,L - Link 1, get (isUnfair, Slices): A possible partition
s2          - split into slices of length 2 (any odd one on it's own at the end)
  Z         - transpose (first item is one thief's slices, second is the others)
     $€     - last two links as a monad for €ach
   F        -     flatten
    Ṣ       -     sort
       E    - equal? (theif1's jewels == theif2's jewels)
        ¬   - not
          L - length (number of slices in the partition)
         ,  - pair

ŒṖṖÇÞḢ - Main link: necklace
ŒṖ     - all partitions
  Ṗ    - pop, we must remove the rightmost one...
              because Link 1 will say it is fair, and it will have length 1!
              (a list of one thing has all entries equal)
    Þ  - sort by
   Ç   -     last link (1) as a monad
     Ḣ - head (get the first one, i.e. minimal isUnfair, then minimal length)

```
> 3 votes

# Answer
# Mathematica, 118 bytes

Almost beat Jelly ... just 1 off ;)

```
SelectFirst[l_±c_:=Append[-#±Most@c,#2]&@@l~TakeDrop~Last@c;l_±{}:={l};i=#;(i±#)&/@Range@#2~Subsets~#3,Tr[Tr/@#]==0&]&

```

Pure function taking three arguments: the necklace, as a list of tokens such as `{A, A, A, A, B, C, D, B, C, D, B, B}`; the length of the necklace; and the number of distinct jewel times. It returns a list of sublists in the form `{{A, A}, {-A, -A, -B, -C, -D, -B}, {C, D, B, B}}`, where the tokens without negative signs go to one thief and the tokens with negative signs go to the other thief. (While this is redundant information, the algorithm leads to this representation, and removing the negative signs would cost several bytes.)

First we have to implement a function that takes a list and a set of `n` cut-places and returns the list of `n+1` sublists obtained by cutting the input list at those `n` cut-places; the binary infix operator `±` is used for this purpose, and defined recursively through `l_±c_:=Append[-#±Most@c,#2]&@@l~TakeDrop~Last@c;l_±{}:={l};`. Because of the negative sign right after `Append`, the result is that the sublists alternately do and do not have negative signs attached to each token.

Then we generate all possible cut-place sets whose length is at most the number of jewel types, using `Range@#2~Subsets~#3`, and use `i=#;(i±#)&/@` to apply the `±` operator (with the input list of jewels) to each of these cut-place sets in turn.

Finally, `SelectFirst[...,Tr[Tr/@#]==0&]&` picks out the first of the resulting necklace divisions that is fair. It does so by literally adding up all of the elements in all of the sublists; Mathematica is wise enough to cancel the positive and negative copies of each token in the obvious way.
> 3 votes

# Answer
# Pyth, 16 bytes

```
hfqFSMsM.TcT2t./

```

Try it online: Demonstration or Test Suite

### Explanation:

```
hfqFSMsM.TcT2t./Q   implicit Q (=input) at the end
              ./Q   create all partitions of the input list
                    (they are already sorted by number of cuts)
             t      remove the partition with zero splits
 f                  filter for partitions T, which satisfy:
          cT2          chop into pieces of length 2
        .T             transpose to get the pieces of each thieve
    SMsM               combine all pieces for each thieve and sort the results
  qF                   check if they got the same jewels
h                   print the first such partition

```
> 3 votes

# Answer
# 05AB1E, 14 bytes

```
.œ¨ʒ2ôζε˜{}Ë}¤

```

Try it online or verify all test cases.

**Explanation:**

```
.œ                # All partitions of the (implicit) input
                  #  i.e. [2,3,2,1,3,1]
                  #   → [[[2],[3],[2],[1],[3],[1]],[[2],[3],[2],[1],[3,1]],
                  #      ...,[[2,3,2,1,3,1]]]
  ¨               # Remove the last one
   ʒ        }     # Filter this list by:
    2ô            # Split it into parts of 2
                  #  i.e. [[2,3],[2],[1],[3,1]] → [[[2,3],[2]],[[1],[3,1]]]
                  #  i.e. [[2,3,2],[1,3],[1]] → [[[2,3,2],[1,3]],[[1]]]
      ζ           # Swap rows and columns (using space as filler if necessary)
                  #  i.e. [[[2,3],[2]],[[1],[3,1]]] → [[[2,3],[1]],[[2],[3,1]]]
                  #  i.e. [[[2,3,2],[1,3]],[[1]]] → [[[2,3,2],[1]],[[1,3]," "]]
       ε  }       # Map each inner list to:
        ˜         # Flatten the list
                  #  i.e. [[2,3],[1]] → [2,3,1]
                  #  i.e. [[1,3]," "] → [1,3," "]
         {        # Sort the list
                  #  i.e. [2,3,1] → [1,2,3]
                  #  i.e. [1,3," "] → [1,3," "]
           Ë      # Check if both sorted lists are equal
                  # (if not, remove them from the partitions)
             ¤    # After filtering, take the last one as result (and output implicitly)
                  #  i.e. [[[2],[3,2],[1,3],[1]],[[2,3],[2],[1],[3,1]]]
                  #   → [[2,3],[2],[1],[3,1]]

```
> 1 votes

---
Tags: code-golf, math, combinatorics
---


title: Check my tunneling arrays

text:
# Question
Title: Check my tunneling arrays
Imagine you have an array of integers, whose non-negative values are pointers to other positions in the same array, only that those values represent tunnels, so if the value in position A is positive and points to position B, then the value in position B must be also positive and point to position A to represent both ends of the tunnel. So:

### Challenge

* Given an array of integers, check if the array complies with the restriction to be a tunneling array and return two distinct, coherent values for truthy and falsey.
* The values in the array will be below zero for non-tunnel positions, and zero or above for tunnel positions. If your array is 1-indexed, then the zero value represents a non-tunnel position. Non-tunnel values do not need to be checked.
* If a positive value in a cell points to itself, that's a falsey. If A points to B, B to C and C to A, that's a falsey. If a positive value points beyond the limits of the array, that's a falsey.

### Examples

The following examples are 0-indexed:

```
[-1, -1, -1, 6, -1, -1, 3, -1, -1]  Truthy (position 3 points to position 6 and vice versa)
[1, 0]                              Truthy (position 0 points to position 1 and vice versa)
[0, 1]                              Falsey (positions 0 and 1 point to themselves)
[4, 2, 1, -1, 0, -1]                Truthy
[2, 3, 0, 1]                        Truthy
[1, 2, 0]                           Falsey (no circular tunnels allowed)
[-1, 2, -1]                         Falsey (tunnel without end)
[]                                  Truthy (no tunnels, that's OK)
[-1, -2, -3]                        Truthy (no tunnels, that's OK)
[1, 0, 3]                           Falsey (tunnel goes beyond limits)
[1]                                 Falsey (tunnel goes beyond limits)
[1, 0, 3, 7]                        Falsey (tunnel goes beyond limits)

```

This is , so may the shortest code for each language win!

# Answer
> 8 votes
# , 47 bytes

```
function(v,a=v[v>0],b=sort(a))all(v[a]==b&a!=b)

```

Try it online!

---

**Unrolled code and explanation :**

```
f=
function(v){          # v vector of tunnel indexes (1-based) or values <= 0

  a = v[v>0]          # get the tunnel positions

  b = sort(a)         # sort the tunnel positions ascending

  c1 = v[a]==b        # get the values of 'v' at positions 'a'
                      # and check if they're equal to the sorted positions 'b'
                      # (element-wise, returns a vector of TRUE/FALSE)

  c2 = a != b         # check if positions 'a' are different from sorted positions 'b'
                      # (to exclude tunnels pointing to themselves, element-wise,
                      #  returns a vector of TRUE/FALSE)

  all(c1 & c2)        # if all logical conditions 'c1' and 'c2' are TRUE then
                      # returns TRUE otherwise FALSE
}

```

# Answer
> 6 votes
# Python 2, ~~66~~ ~~61~~ 60 bytes

```
lambda l:all(len(l)>v!=i==l[v]for i,v in enumerate(l)if-1<v)

```

Try it online!

# Answer
> 5 votes
# APL (Dyalog Unicode), ~~19~~ 24 bytes

```
×/<∘≢⍨×≠∘⍳∘≢⍨×0∘>∨⊢=⊢⍳⍳⍨

```

Try it online!

Prefix anonymous lambda, returning 1 for truthy and 0 for falsy. The TIO link contains a "prettified" version of the output for the test cases.

Shoutouts to @ngn and @Adám for saving approximately a bazillion bytes.

An extra shoutout to @ngn for the help with fixing the answer for some test cases, and with making it a train.

The updated answer uses `⎕IO←0`, setting the **I**ndex **O**rigin to 0.

### How:

```
×/<∘≢⍨×≠∘⍳∘≢⍨×0∘>∨⊢=⊢⍳⍳⍨ ⍝ Prefix lambda, argument ⍵ → 4 2 1 ¯1 0 ¯1.
                       ⍳⍨ ⍝ Index of (⍳) ⍵ in ⍵. ⍵⍳⍵ → 0 1 2 3 4 3
                     ⊢⍳   ⍝ Index of that in ⍵ (returns the vector length if not found).
                          ⍝ ⍵⍳⍵⍳⍵ → 4 2 1 6 0 6
                  ⊢=      ⍝ Compare that with ⍵. ⍵=⍵⍳⍵⍳⍵ → 1 1 1 0 1 0
                          ⍝ This checks if positive indices tunnel back and forth correctly.
                 ∨        ⍝ Logical OR with
              0∘>         ⍝ 0>⍵ → 0 0 0 1 0 1∨1 1 1 0 1 0 → 1 1 1 1 1 1
                          ⍝ Removes the zeroes generated by negative indices
             ×            ⍝ Multiply that vector with
            ⍨             ⍝ (using ⍵ as both arguments)
         ⍳∘≢              ⍝ Generate the range [0..length(⍵)-1]
       ≠∘                 ⍝ And do ⍵≠range; this checks if any
                          ⍝ element in ⍵ is tunneling to itself.
                          ⍝ ⍵≠⍳≢⍵ → 4 2 1 ¯1 0 ¯1≠0 1 2 3 4 5 → 1 1 1 1 1 1
      ×                   ⍝ Multiply that vector with
     ⍨                    ⍝ (using ⍵ as both arguments)
  <∘≢                     ⍝ ⍵ < length(⍵) → 4 2 1 ¯1 0 ¯1 < 6 → 1 1 1 1 1 1
                          ⍝ This checks if any index is out of bounds
×/                        ⍝ Finally, multiply and reduce.
                          ⍝ ×/1 1 1 1 1 1 → 1 (truthy)

```

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

*Saved 1 byte thanks to @Shaggy*

```
a=>a.every((v,i)=>v<0|v!=i&a[v]==i)

```

Try it online!

### Commented

```
a =>                // a[] = input array
  a.every((v, i) => // for each value v at position i in a[]:
    v < 0 |         //   force the test to succeed if v is negative (non-tunnel position)
    v != i &        //   make sure that this cell is not pointing to itself
    a[v] == i       //   check the other end of the tunnel
  )                 // end of every()

```

# Answer
> 3 votes
# Python 2, 65 bytes

```
lambda l:all(l[v:]>[]and v!=i==l[v]or v<0for i,v in enumerate(l))

```

Try it online!

# Answer
> 3 votes
# Jelly, 16 bytes

```
ị=JanJ$>L<$o<1$Ạ

```

Try it online!

1-indexed.

# Answer
> 3 votes
# Japt `-e`, 11 bytes

```
§JªU¦V«aWgU

```

Try it

---

## Original (w/o flag), ~~14~~ 13 bytes

```
eÈ§JªX¦Y«aUgX

```

Try it or run all test cases

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

```
εèNQyNÊ*y0‹~}P

```

-1 byte thanks to *@Dorian*.

Try it online or verify all test cases.

**Explanation:**

```
ε               # Map each value `y` of the (implicit) input-list to:
 è              #   If the current value indexed into the (implicit) input-list
  NQ            #   is equal to the index
       *        #   And
    yNÊ         #   If the current value is not equal to the current index
           ~    #  Or if:
        y0‹     #   The current value is negative
            }P  # After the map: check if everything is truthy
                # (after which the result is output implicitly)

```

# Answer
> 3 votes
# Perl 6, 36 bytes

```
{!.grep:{2-set $++,$^v,.[$v]xx$v+1}}

```

Try it online!

The basic idea is to check whether the set `{ i, a[i], a[a[i]] }` contains exactly two distinct elements for each index `i` with `a[i] >= 0`. If an element points to itself, the set contains only a single distinct element. If the other end doesn't point back to `i`, the set contains three distinct elements. If `a[i] < 0`, the `xx` factor is zero or negative, so the set is `{ i, a[i] }`, also with two distinct elements.

# Answer
> 3 votes
# MATL, ~~19~~ 18 Bytes

-1 Byte thanks to Luis

```
n:G=GGG0>f))7M-|hs

```

Try it online!, for the first one only, because I don't know how to do all of them!

Gives `0` if truthy, a non-zero integer if falsey, eg. for test case 6 gives `4`.

Please remember that like MATLAB, MATL is 1-indexed so 1 must be added to the test cases!

Never golfed in an Esolang before, so advice greatly received!

Explained:

```
n:G=GGG0>f))7M-|hs
                        Implicit - input array
n                       Number of values in array
 :                      Make array 1:n
  G                     Push input
   =                    Equality
n:G=                    Makes non-zero array if any of the tunnels lead to themselves
    GGG                 Push input 3x
       0                Push literal 0
        >               Greater than
      G0>               Makes array of ones where input > 0
         f              Find - returns indeces of non-zero values
                        Implicit - copy this matrix to clipboard
          )             Indeces - returns array of positive integers in order from input
           )            Ditto - Note, implicit non-zero any above maximum
            7M          Paste from clipboard
              -         Subtract
    GGG0>f))7M-         Makes array of zeros if only two-ended tunnels evident
               |        Absolute value (otherwise eg. [3,4,2,1] -> '0')
                h       Horizontal concat (ie. joins check for self tunnels and wrong tunnels)
                 s      Sum; = 0 if truthy, integer otherwise

```

# Answer
> 2 votes
## Python, 112 97 96 86 bytes

```
f=lambda l:sum(i==l[i]or len(l)<=l[i]or 0<=l[i]and i!=l[l[i]]for i in range(len(l)))<1

```

Try it Online!

Returns `True` or `False`.

-10 bytes thanks to @Rod and @TFeld.

# Answer
> 2 votes
# Java (JDK), 89 bytes

```
a->{int l=a.length,i=l;for(;i-->0;)i=a[i]<1||a[i]<l&&a[i]!=i&a[a[i]]==i?i:-2;return-2<i;}

```

Try it online!

## Credits

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

```
{*/(x<0)|(x<#x)&(~x=!#x)&x=x?x?x}

```

Try it online!

# Answer
> 2 votes
# Groovy, 52 bytes

```
{o=!(i=0);it.each{e->o&=e<0||(it[e]==i&&i-e);i++};o}

```

Try it online!

# Answer
> 2 votes
# Haskell, 48 bytes

```
(all=<< \u(x,y)->y<0||x/=y&&elem(y,x)u).zip[0..]

```

Verify all testcases!

## Explanation

Let's first ungolf the code a bit. As `f =<< g` is the same as `\x -> f (g x) x`, the code is equivalent to

```
(\u->all(\(x,y)->y<0||x/=y&&elem(y,x)u)u).zip[0..]

```

which is a bit clearer.

```
(\u ->                                  -- given u, return
    all (\(x, y) ->                     -- whether for all elements (x, y) of u
            y < 0 ||                    -- either y < 0, or
            x /= y && elem (y, x) u     -- (x /= y) and ((y, x) is in u)
        )
    u
) . zip [0..]                           -- given the array a (implicitly via point-free style),
                                        -- return the array augmented with indices (it's the u above)

```

This solution is based on a simple observation: let `a` be the input array, and `u` the list of pairs `(i, a[i])` where `i` is an index. Then `a` is a valid array if and only if for every `(x, y)` in `u` with `y >= 0`, the pair `(y, x)` belongs to `u` as well.

# Answer
> 1 votes
# Charcoal, 22 bytes

```
¬Φθ∨⁼ικ¬∨‹ι⁰∧‹ιＬθ⁼κ§θι

```

Try it online! Link is to verbose version of code. Outputs `-` for truthy and nothing for falsy. Note: Inputting an empty array seems to crash Charcoal, but for now you can enter a space instead, which is near enough. Explanation:

```
  θ                     Input array
 Φ                      Filter elements
     ι                  Current value
    ⁼                   Equals
      κ                 Current index
   ∨                    Or
       ¬                Not
          ι             Current value
         ‹ ⁰            Is less than zero
        ∨               Or
              ι         Current value
             ‹          Is less than
               Ｌ        Length of
                θ       Input array
            ∧           And
                  κ     Current index
                 ⁼      Equals
                   §θι  Indexed value
¬                       Logical Not (i.e. is result empty)
                        Implicitly print

```

# Answer
> 1 votes
# Pascal (FPC), ~~165~~ ~~155~~ 153 bytes

```
function f(a:array of int32):byte;var i:int32;begin f:=1;for i:=0to length(a)-1do if a[i]>-1then if(a[i]=i)or(a[i]>length(a))or(a[a[i]]<>i)then f:=0;end;

```

Try it online!

Made function this time because the input is array. Returns `1` for truthy and `0` for falsey.

# Answer
> 1 votes
# Clean, 60 bytes

```
import StdEnv
@l=and[v<0||l%(v,v)==[i]&&v<>i\\v<-l&i<-[0..]]

```

Try it online!

# Clean, 142 bytes

Vastly over-complicated monster version:

```
import StdEnv,Data.List,Data.Maybe
$l=and[?i(mapMaybe((!?)l)j)j\\i<-l&j<-map((!?)l)l|i>=0]with?a(Just(Just c))(Just b)=a==c&&b<>c;?_ _ _=False

```

Try it online!

Explained:

```
$ l                           // function $ of `l` is
 = and [                      // true when all elements are true
  ?                           // apply ? to
   i                          // the element `i` of `l`
   (mapMaybe                  // and the result of attempting to
    ((!?)l)                   // try gettting an element from `l`
    j)                        // at the potentially invalid index `j`
   j                          // and `j` itself, which may not exist
  \\ i <- l                   // for every element `i` in `l`
  & j <- map                  // and every potential `j` in
    ((!?)l)                   // `l` trying to be indexed by
    l                         // every element in `l`
  | i >= 0                    // where `i` is greater than zero
 ]
with
 ? a (Just (Just c)) (Just b) // function ? when all the arguments exist
  = a==c && b<>c              // `a` equals `c` and not `b`
  ;
 ? _ _ _ = False              // for all other arguments, ? is false

```

# Answer
> 1 votes
# Pyth, ~~17~~ 16 bytes

```
.A.e|>0b&nbkq@Qb

```

Try it online here, or verify all the test cases at once here.

```
.A.e|>0b&nbkq@QbkQ   Implicit: Q=eval(input())
                     Trailing k, Q inferred
  .e             Q   Map the input with b=element, k=index, using:
     >0b               0>b
    |                  OR (
         nbk           b != k
        &              AND
            q@Qbk      Q[b] == k)
.A                   Check if all elements are truthy

```

*Edit: realised that the trailing k was also unnecessary*

# Answer
> 1 votes
# Ruby, 44 bytes

```
->a{a.all?{|x|x<0||(w=a[x])&&x!=w&&a[w]==x}}

```

Try it online!

# Answer
> 1 votes
# Perl 5, 54 bytes

```
{$i=-1;!grep$_>=0*$i++&&($_==$i||$i!=($_[$_]//-1)),@_}

```

Try it online!

# Answer
> 1 votes
# C (gcc), ~~95~~ 94 bytes

```
i(_,o,O,Q,I)int*_;{for(I=O=0;O<o;O++)I|=_[O]>=0&&_[O]>=o|(Q=_[O[_]])<0|Q>=o|O[_]==O|Q!=O;Q=I;}

```

Try it online!

# Answer
> 0 votes
# Mathematica, 42 bytes

```
#=={}||(a=0@@#)[[#]]=!=a&&a[[#]][[#]]===a&

```

Pure function. Takes a 1-indexed list of numbers as input and returns `True` or `False` as output. Just follows the tunnels, ensuring that `0` maps to `0`, no 1-cycles exist, and all cycles are 2-cycles. (I'm not entirely sure if this fails on any edge cases, but it gives the correct results for the examples.)

# Answer
> 0 votes
# This answer does not work. Here for illustration purposes only.

This answer passes all of the (currently) posted test cases. However, it fails (raises an error) on other valid input, such as `[1, 2]` or `[1, 0, 3, 7]`.

How could it pass `[1, 0, 3]` and fail `[1, 0, 3, 7]`? Well, it proceeds through the list, just like you'd expect. When it reads an element `x` of the list `a`, it first checks whether `x` is less than `len(a)`, and immediately returns `False`, if so. So it correctly returns `False` on `[1, 0, 3]`, because `3` is not less than `len(a)`.

But assuming that `x` passes that check, the code will then go on to do some other checks, and at a certain point it happens to evaluate `a[a[x]]`. We've already guaranteed that evaluating `a[x]` will be OK...but not `a[a[x]]`, which resolves to `a[7]` when `x` is `3` in the `[1, 0, 3, 7]` example. At this point Python raises an `IndexError`, rather than returning `False`.

For completeness, here's the answer.

# Python 2, 59 bytes

```
lambda a:all(x<len(a)>-1<a[x]!=x==a[a[x]]for x in a if-1<x)

```

Try it online!

I wanted to do `x<len(a)and-1<a[x]...`, but of course `len(a)` is always `>-1`, so the above is equivalent. This check is a total of 5 chained relations (`<`, `>`, `<`, `!=`, and `==`), plus a separate check `-1<x` in the `if` condition.

Python (conveniently) short-circuits chained relations like this, so for example if `x>=len(a)` then the check returns `False` before it gets to `a[x]` (which would otherwise raise an `IndexError`).

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


title: Print a Quinella Table

text:
# Question
Title: Print a Quinella Table
> **ALERT: IN CASE YOU DOUBT, NO PUN ON "QUINE" IS INTENDED**

In regulated horse-racing for gambling, bets called *Quinella bets* exist and in which a person bet on the first two places of a race. In racecourses, usually there is a display which shows the odds of a specific combination as below:

(This picture is a cropped picture from Hong Kong Jockey Club. QIN stands for Quinella)

## Challenge

Write a program or function, receiving either lines of strings or an array, print or return an ASCII Quinella table with the following format:

```
 QUINELLA  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  | 10  | 11  | 12  | 13  | 14  |
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
     | 8\1 | 162 | 7.2 | 11  | 109 | 4.5 | 6.0 | 11  | 999 | 11  |     |     |     |     |  1
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
  9  | 37  | 9\2 | 11  | 999 | 41  | 350 | 75  | 24  | 999 | 31  |     |     |     |     |  2
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
 10  | 8.2 | 84  |10\3 | 75  | 999 | 85  | 48  | 8.1 | 138 | 191 |     |     |     |     |  3
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
 11  |     |     |     |11\4 | 45  | 6.4 | 999 | 287 | 473 | 60  |     |     |     |     |  4
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
 12  |     |     |     |     |12\5 | 15  | 8.9 | 40  | 175 | 378 |     |     |     |     |  5
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
 13  |     |     |     |     |     |13\6 | 26  | 999 | 15  | 860 |     |     |     |     |  6
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
 14  |     |     |     |     |     |     |14\7 | 727 | 100 | 37  |     |     |     |     |  7
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
     |  8  |  9  | 10  | 11  | 12  | 13  |     |  8  |  9  | 10  | 11  | 12  | 13  | 14  |

```

In this challenge, the numbers in the middle are calculated from the input by a specific algorithm, which will be explained later.

# Specification

**Input**: Your program or function must receive one of the two formats as below:

* **Lines of Strings**: The first line will be `<number of horses> <number of bets>`, following by `<number of bets>` lines of `<horse 1> <horse 2> <amount of bet>`.

Example:

```
10 100
1 2 100
3 4 500
5 6 100
7 8 2000
9 10 10
(... 95 more lines)

```
* **Array**: An array or tuple, with 3 elements, `[<number of horses>, <number of bets>, <bets>]`, where `<bets>` is a 2d array consisting of `<number of bets>` elements, each element consists of 3 elements, `[<horse 1>, <horse 2>, <amount of bet>]`. *As a special rule for functions, passing the tuple as 3 arguments is allowed.*

Example:

```
[10, 100, [
 [1, 2, 100],
 [3, 4, 500],
 [5, 6, 100],
 [7, 8, 2000],
 [9, 10, 10],
 ... 95 more elements
]]

```
* You may assume all inputs are valid.
* You may assume `1 <= <horse 1> < <horse 2> <= <number of horses>` in both cases.
* You may assume `9 <= <number of horses> <= 14` in both cases.

**Processing**: The odds for each quinella pair `<horse 1>, <horse 2>` (unordered, i.e. `1,2` and `2,1` are considered identical) is calculated as follows:

```
Odds = <Total bet amount of all pairs> / <Total bet amount of the pair> / 2
Maximum Odds: 999, Minimum Odds: 1.1

```

In case you doubt, **the odds will be 999** if `<Total bet amount of the pair> == 0`.

The result should be rounded to the nearest 0.1 if `Odds < 9.95` (in this case, the `.0` must be retained if necessary), and to the nearest integer if `Odds >= 9.95`.

**Output**: Replace each ***bold-and-italic number pair*** with the corresponding odds calculated in the previous step. Leave the cell blank if any of the number in the pair is larger than `<number of horses>`.

```
 QUINELLA  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  | 10  | 11  | 12  | 13  | 14  |
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
     | 8\1 | ***1,2*** | ***1,3*** | ***1,4*** | ***1,5*** | ***1,6*** | ***1,7*** | ***1,8*** | ***1,9*** |***1,10*** |***1,11*** |***1,12*** |***1,13*** |***1,14*** |  1
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
  9  | ***8,9*** | 9\2 | ***2,3*** | ***2,4*** | ***2,5*** | ***2,6*** | ***2,7*** | ***2,8*** | ***2,9*** |***2,10*** |***2,11*** |***2,12*** |***2,13*** |***2,14*** |  2
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
 10  |***8,10*** |***9,10*** |10\3 | ***3,4*** | ***3,5*** | ***3,6*** | ***3,7*** | ***3,8*** | ***3,9*** |***3,10*** |***3,11*** |***3,12*** |***3,13*** |***3,14*** |  3
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
 11  |***8,11*** |***9,11*** |***10,11***|11\4 | ***4,5*** | ***4,6*** | ***4,7*** | ***4,8*** | ***4,9*** |***4,10*** |***4,11*** |***4,12*** |***4,13*** |***4,14*** |  4
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
 12  |***8,12*** |***9,12*** |***10,12***|***11,12***|12\5 | ***5,6*** | ***5,7*** | ***5,8*** | ***5,9*** |***5,10*** |***5,11*** |***5,12*** |***5,13*** |***5,14*** |  5
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
 13  |***8,13*** |***9,13*** |***10,13***|***11,13***|***12,13***|13\6 | ***6,7*** | ***6,8*** | ***6,9*** |***6,10*** |***6,11*** |***6,12*** |***6,13*** |***6,14*** |  6
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
 14  |***8,14*** |***9,14*** |***10,14***|***11,14***|***12,14***|***13,14***|14\7 | ***7,8*** | ***7,9*** |***7,10*** |***7,11*** |***7,12*** |***7,13*** |***7,14*** |  7
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
     |  8  |  9  | 10  | 11  | 12  | 13  |     |  8  |  9  | 10  | 11  | 12  | 13  | 14  |

```
* Each cell is 5 characters wide.
* You must center the odds, and if you cannot balance the margins, make left margin 1 character less wider than right margin.

## Test Cases

Here is a TIO driver which generates random test cases. No hard-coded test cases will be provided.

## Winning Criteria

Shortest code in each language wins as per the rules of code-golf challenges. No standard loopholes allowed.

# Answer
# JavaScript (ES8), 321 bytes

Takes input as `(number_of_horses)(bets)`. The number of bets is not taken.

```
n=>b=>' QUINELLA  '+(y=e='',g=(x,y)=>b.map(([X,Y,b])=>k+=X-x|Y-y?0:b,k=-(x>n|y>n))|k,F=x=>y>16?e:`|+
`[x?y&1:2]+(Y=y/2,s=y&1?'-----':(x%15|Y%8?x?Y>7?x>7?x:x<7?x+7:e:x-Y?y?x<15?~g(x>Y?Y:x+7,x>Y?x:Y+7)?(k=.5/k*g())<999?k.toFixed(k<9.95):999:e:Y:x:x+7+'\\'+x:y-2?Y+7:e:e)+e).padStart(s[2]?4:3).padEnd(5)+F(++x<16?x:!++y))(2)

```

Try it online!

## How?

### Main part

```
n => b =>                       // n = number of horses; b[] = bet array
  ' QUINELLA  ' + (             // append header
    y = e = '',                 // e is the empty string; start with y = '', coerced to 0
    F = x =>                    // F = main recursive function, taking x
      y > 16 ?                  //   if y is greater than 16:
        e                       //     return an empty string and stop recursion
      :                         //   else:
        `|+\n`[x ? y & 1 : 2]   //     append a linefeed if we are at the beginning of a row
        + (                     //     or either '|' or '+' depending on the parity of y
          Y = y / 2,            //     define Y = y / 2
          s =                   //     define s:
            y & 1 ?             //       if y is odd:
              '-----'           //         s = 5 hyphens
            :                   //       else:
              [cell content]    //         s is set to the content of the cell
        )                       //
        .padStart(s[2] ? 4 : 3) //   prepend leading spaces
        .padEnd(5) +            //   append trailing spaces
        F(++x < 16 ? x : !++y)  //   append the result of a recursive call
  )(2)                          // initial call to F() with x = 2

```

### Cell content

The cell content is computed with a huge cascade of ternary operators, which is neither easy nor very interesting to detail here.

One key part in there is the formatting of a bet:

```
~g(                             // invoke g():
  x > Y ? Y : x + 7,            //   first horse
  x > Y ? x : Y + 7             //   second horse
) ?                             // if g() didn't return -1:
  (k = .5 / k * g())            //   compute amount_of_all_pairs / amount_of_this_pair / 2
  < 999 ?                       //   if the result is less than 999:
    k.toFixed(k < 9.95)         //     output it with the proper number of decimal places
  :                             //   else:
    999                         //     force result to 999
:                               // else:
  e                             //   output an empty cell

```

### Bet amount processing

The helper function \\$g\\$ computes the total bet amount for a given pair of horses, or the total bet amount of all pairs when invoked with no argument. If at least one of the horses is not valid, it returns \\$-1\\$ instead.

```
g = (x, y) =>                   // x = 1st horse, y = 2nd horse
  b.map(([X, Y, b]) =>          // for each bet of amount b on horses (X, Y):
    k +=                        //   update k:
      X - x | Y - y ?           //     if (x, y) is not matching (X, Y):
        0                       //       add 0 to k
      :                         //     else:
        b,                      //       add b to k
    k = -(x > n | y > n)        //   start with k = 0 if both x and y are valid horses
                                //   otherwise, start with k = -1
  ) | k                         // end of map(); return k

```
> 4 votes

# Answer
# Python 2, ~~500~~ ~~448~~ 444 bytes

```
R=range(1,15)
h,_,b=input()
Q=eval(`[['']*16]*9`)
Q[8][1:6]=R[7:13];Q[8][8:16]=R[7:]
for i in R:
 if i<8:Q[i][i]=`7+i`+'\\'+`i`;Q[i][::15]=[['',7+i][i>1],i]
 for j in R:v=sum(v*((A,B)==(i,j))for A,B,v in b);x=min(999,0**v*999or.5*sum(zip(*b)[2])/v);X,Y=i<j<=h and[i,j-7,j,i-7][i>7::2]or(0,0);Q[X][Y]=x<10and round(x,1)or int(x+.5)
Q[0]=[' QUINELLA  ']+R[1:]+['']
for l in Q:print('-----+'*15+'-----\n')*(l<[' '])+'|'.join(map('{:^5}'.format,l))

```

Try it online!
> 3 votes

# Answer
# Clean, ~~498~~ ... 483 bbytes

Doesn't take the number of bets.

```
import StdEnv,Text
q=""
j=join
$h a=replaceSubString" 0""  "(" QUINELLA"+(j("\n"+j"+"(repeatn 16"-----")+"\n")[j"|"[q<+cjustify 5[c\\c<-: ?h a u v]\\v<-[0..15]]\\u<-[0..8]])%(9,9^9))
?h a u v|u<1=q<+v rem 15|v>14=q<+u rem 8|u>7|v>7=q<+v=q<+(v+7)*sign(v rem 7)
|u==v=u+7<+"\\"<+v|v<1|u>1=q<+u+7=q
#p=sort[k+if(u>=v)7 0\\k<-[u,v]]
#r=sum[z\\(x,y,z)<-a|[x,y]==p]
|r>0.0#r=sum(map thd3 a)/r/2E0
|r<9.95=snd(sort[(abs(e-r),e<+".0")\\e<-[1.1,1.2..1E1]]!!0)%(0,2)=q<+toInt r
|p!!1<h="999"=q

```

Try it online!

Explained:

```
q = ""                  // define `q` as the empty string
j = join                // define `j` as the join function
$ h a                   // function $ of horses `h` and array `a`
 = replaceSubString     // replace all
  " 0"                  // zeroes with spaces before them
  "  "                  // with two spaces
  (                     // (in the string)
   " QUINELLA" +        // " QUINELLA" prepended to
   (                    // (the string created by)
    j                   // joining arg2 with arg1
     (                  // (the separator string)
      "\n" +            // newline prepended to
      j "+"             // joining arg2 with plusses
       (repeatn 16      // a list with 16 of
        "-----")        // string with 5 dashes
      + "\n"            // prepended to a newline
     )
     [                  // (a list made out of)
      j "|"             // joining arg2 with vertical pipes
       [                // (a list made out of)
        q <+            // stringifying
        cjustify 5 [    // center-aligning a list of
         c              // character `c`
         \\ c <-:       // for every `c` in the string
          ? h a u v     // (the thing that goes in the cell)
        ]
        \\ v <- [0..15] // for every `v` from 0 to 15
       ]
       \\ u <- [0..8]   // for every `u` from 0 to 8
     ]
   ) % (9, 9^9)         // drop 9 elements off the front
  )
? h a u v               // function ? of `h` `a` `u` and `v`
 | u < 1                // if `u` is zero
  = q <+ v rem 15       // stringify `v` modulo 15
 | v > 14               // if `v` is 15
  = q <+ u rem 8        // stringify `u` modulo 8
 | u > 7                // if `u` is 8
  | v > 7               // if `v` is more than 7
   = q <+ v             // stringify `v`
  = q <+                // otherwise stringify
  (v+7) *               // `v` plus 7 unless
  sign(v rem 7)         // `v` is 7 or zero
 | u == v               // if `u` equals `v`
  = u + 7 <+            // stringify `u` plus 7 and append
  "\\" <+ v             // a slash and the stringification of v
 | v < 1                // if `v` is zero
  | u > 1               // if `u` is more than 1
   = q <+ u + 7         // stringify `u` + 7
  = q                   // empty string
 # p =                  // define `p` as
  sort                  // the sorted
   [                    // (list of horse numbers)
    k +                 // k plus
    if(u >= v)
     7                  // if u >= v, 7
     0                  // else zero
    \\ k <- [u, v]      // for every `k` in u and v
   ]
 # r =                  // define `r` as
  sum                   // the sum of
   [                    // (the bets on those horses)
    z                   // the bet `z`
    \\ (x, y, z) <- a   // for every subarray
    | [x, y] == p       // where the horse pair matches `p`
   ]
 | r > 0.0              // if `r` is greater than zero
  # r =                 // redefine `r` as
   sum                  // the sum of
    (map thd3 a)        // every bet
   / r                  // divided by the previous `r`
   / 2E0                // divided by two
  | r < 9.95            // if r is less than 9.95
   = snd                // the second element of
    (                   // (the tuple with the closest matching odd)
     sort               // sort the
      [                 // (list of potential odds)
       (                // (tuple with)
        abs(e - r)      // the difference between `r` and the odd `e`
        , e <+ ".0"     // and the stringification of `e`
       )                // for every `e` in the list of odds
       \\ e <- [1.1, 1.2..1E1]
      ] !! 0            // the first element
    ) % (0, 2)          // "round" the number
  = q <+ toInt r        // otherwise stringify and round `r`
 | p!!1 < h             // if the bet was actually zero
  = "999"               // the odds are 999
 = q                    // otherwise there isn't a horse

```
> 1 votes

---
Tags: code-golf, ascii-art, number
---


title: Quine / Reverse Quine

text:
# Question
Title: Quine / Reverse Quine
Write a complete program that takes a boolean or non-negative integer input. It must:

* Output its own source code if the input value is falsy
* Output its own source code in reverse if the input value is truthy

Your program cannot be palindromic, nor can it read its own source code by any means.

This is code golf - shortest code in bytes wins.

# Answer
> 9 votes
# Gol\>\<\>, 9 bytes

```
'rd3*I?rH

```

I feel a little awkward posting this, since we already have \>\<\>, Vitsy and Minkolang answers. The only additions to the standard quine are `I` (read integer input), `?` (execute next if truthy) and `r` (reverse stack).

Try it online.

# Answer
> 18 votes
## CJam, ~~17~~ 16 bytes

```
{`"_~"+Wq~g#%}_~

```

Test it here.

A fairly straight-forward modification of the standard quine. Other solutions for 17 bytes:

```
{`"_~"+q~{W%}&}_~
{`"_~"+q~!2*(%}_~

```

If I can assume that the input is only 0 or 1 (as a stand-in for a boolean, which there is no dedicated type for in CJam), I get 15 by omitting the `g`:

```
{`"_~"+Wq~#%}_~

```

### Explanation

```
{`"_~"+  e# Standard generalised quine framework. Leaves the source code on the stack.
  W      e# Push a -1.
  q~     e# Read and evaluate input.
  g      e# signum, turning truthy values into 1 (leaving 0 unchanged).
  #      e# Power. -1^0 == 1, -1^1 == -1.
  %      e# Select every Nth element: a no-op for 1 and reverses the string for -1.
}_~

```

# Answer
> 9 votes
# Pyth, 17 bytes

```
_WQjN*2]"_WQjN*2]

```

A straightforward modification of the standard Pyth quine.

# Answer
> 7 votes
## \>\<\>, 17 Bytes

Requires the -v flag (+1 byte) for pushing input onto the stack (or for you to put input on the stack beforehand on the online interpreter).

```
'rd3*$?rol?!;70.

```

You could do the below for the same amount of bytes (without the flag) if integer inputs only were allowed (i.e. 0 for falsy, 1 for truthy).

```
'rd3*ic%?rol?!;80.

```

Try it online

Truthy/falsy for \>\<\> are anything not 0 and 0, respectively.

# Answer
> 6 votes
# Vitsy, 15 Bytes

...I'm... I'm beating CJam! (shouts over) *Mom! Look, ma, I deed it!*

```
'rd3*i86*-)rl\O
```

Explanation:

```
'rd3*i86*-(rl\O
Standard quine, but with a twist:

'               Capture the source code as a string
 rd3*           Create the ' character in ASCII
     i86*-      Get the input character as ASCII then subtract 48 from it.
                    If it's zero, it'll the if statement will skip the next instruction.
          (r    If the top item of the stack is zero, do not do the next item.
                    The next item here is reverse.
            l\O Print out the stack.

```

## Newer Version of Vitsy, 11 Bytes

```
v'rd3*}v)rZ
v            Capture the input as a variable.
 '           Capture the source until encountering another '
  r          Reverse the stack.
   d3*       Push ' to the stack.
      }      Rotate the stack to the right one.
       v)    Push the variable (input) to the stack and test if it is not zero.
         r   If so, reverse the stack.
          Z  Output everything in the stack.
```

# Answer
> 3 votes
## Python 2, 51 bytes

```
s="print('s=%r;exec s'%s)[::1-2*0**input()]";exec s

```

# Answer
> 2 votes
# Javascript (ES6), 42 bytes

```
$=_=>'$='+(_?$:[...''+$].reverse().join``)

```

This is a modification of my Bling Quine. It's twice as long, too.

# Answer
> 2 votes
## Haskell, ~~126~~ ~~118~~ 108 bytes

```
main=readLn>>=putStr.([t,reverse t]!!);t=s++show s;s="main=readLn>>=putStr.([t,reverse t]!!);t=s++show s;s="

```

Expects `0` or `1` as input.

# Answer
> 2 votes
## Burlesque, 40 bytes

```
ri#Q2 SH ~- "ri#Q" \/ .+ j "<-" ps if sh

```

**Explanation:**

Burlesque has advanced stack and code manipulation built-ins. In fact, you can't access the source code of the program but you can access the remaining code that is to be executed in the future. This means `#Q` will return all the code that follows it which is why we have to add everything up to `#Q` to that code which is what we're doing with `ri#Q`.

```
blsq ) #Q1 2++
12 -- this is the result of 1 2++
{1 2 ++} -- this is the result of #Q

```

`++1 2` is technically illegal code since it's stack based. But we can manipulate the code to make it execute as `1 2++`:

```
blsq ) #Q<-#q++1 2
12

```

Working with these built-ins is incredibly tricky and nobody has yet used them for anything productive except for quine related things. If you reverse `++1 2` you get `2 1++` which would produce `21` and not `12`. The reason the code above produces `12` is because `#Q` also includes the `<-` so in the end we end up executing a lot more than just `2 1++` :p. We end up executing `2 1++#q<-` which produces `12`.

We can actually replace things in our code for example this code replaces all occurences of `?+` in itself with `?*`

```
blsq ) #Q(?+)(?*)r~5.-#q5 5?+
25

```

**Usage:**

```
$ echo "1" | blsq --stdin 'ri#Q2 SH ~- "ri#Q" \/ .+ j "<-" ps if sh'
hs fi sp "-<" j +. /\ "Q#ir" -~ HS 2Q#ir
$ echo "0" | blsq --stdin 'ri#Q2 SH ~- "ri#Q" \/ .+ j "<-" ps if sh'
ri#Q2 SH ~- "ri#Q" \/ .+ j "<-" ps if sh

```

# Answer
> 2 votes
## Minkolang 0.10, 13 bytes

```
"66*2-n,?r$O.

```

Try it here.

This is exactly like the standard quine except for these four characters: `n,?r`. `n` takes an integer from input, `,` inverts it, so `?` skips `r` if the input is truthy. Otherwise, `r` reverses the stack so that it is output in reverse order.

# Answer
> 0 votes
# Java 10 (full program), 282 bytes

```
interface N{static void main(String[]a){var s="interface N{static void main(String[]a){var s=%c%s%1$c;s=s.format(s,34,s);System.out.print(new Boolean(a[0])?new StringBuffer(s).reverse():s);}}";s=s.format(s,34,s);System.out.print(new Boolean(a[0])?new StringBuffer(s).reverse():s);}}

```

Try it online.

# Java 10 (as lambda function), 154 bytes

```
b->{var s="b->{var s=%c%s%1$c;s=s.format(s,34,s);return b?new StringBuffer(s).reverse():s;}";s=s.format(s,34,s);return b?new StringBuffer(s).reverse():s;}

```

Try it online.

**Explanation:**

```
interface N{                          // Class
  static void main(String[]a){        //  Mandatory main-method
    var s="interface N{static void main(String[]a){var s=%c%s%1$c;s=s.format(s,34,s);System.out.print(new Boolean(a[0])?new StringBuffer(s).reverse():s);}}";
                                      //   Unformatted source code
    s=s.format(s,34,s);               //   Format the source code (the quine-String)
    System.out.print(                 //   Print:
      new Boolean(a[0])?              //    If the input is true:
       new StringBuffer(s).reverse()  //     Print the quine-String reversed
      :                               //    Else:
       s);}}                          //     Print the quine-String as is

```

**explanation:**

* The `var s` contains the unformatted source code
* `%s` is used to put this String into itself with `s.format(...)`
* `%c`, `%1$c`, and `34` are used to format the double-quotes
* `s.format(s,34,s)` puts it all together

And then `new StringBuffer(s).reverse()` is used to reverse the quine-String if necessary based on the input-boolean.

# Answer
> 0 votes
# 05AB1E, 21 bytes

```
0"D34çýÂ‚sè"D34çýÂ‚sè

```

Try it online.

Modification of the default `0"D34çý"D34çý` by adding `Â‚sè`.

**Explanation:**

```
0                        # Push 0 to the stack
                         #  STACK: [0]
 "D34çýÂ‚sè"             # Push the string 'D34çýÂ‚sè' to the stack
                         #  STACK: [0, 'D34çýÂ‚sè']
            D            # Duplicate this string
                         #  STACK: [0, 'D34çýÂ‚sè', 'D34çýÂ‚sè']
             34ç         # Push '"' to the stack
                         #  STACK: [0, 'D34çýÂ‚sè', 'D34çýÂ‚sè', '"']
                ý        # Join the stack with '"' delimiter
                         #  STACK: ['0"D34çýÂ‚sè"D34çýÂ‚sè']
                 Â       # Bifurcate (short for Duplicate & Reverse)
                         #  STACK: ['0"D34çýÂ‚sè"D34çýÂ‚sè', 'ès‚Âýç43D"ès‚Âýç43D"0']
                  ‚      # Pair them up:
                         #  STACK: [['0"D34çýÂ‚sè"D34çýÂ‚sè','ès‚Âýç43D"ès‚Âýç43D"0']]
                   s     # Swap to get the boolean input (0 or 1)
                         #  STACK: [['0"D34çýÂ‚sè"D34çýÂ‚sè','ès‚Âýç43D"ès‚Âýç43D"0'], 1]
                    è    # Index the input into the list
                         #  STACK: ['ès‚Âýç43D"ès‚Âýç43D"0']
                         # (Output the top of the stack implicitly)

```

PS: Automatically prints a trailing newline. If this should be reversed as well, it's 23 bytes instead:

```
0"D34çýÂ‚sè?"D34çýÂ‚sè?

```

Try it online. (`?` is an explicit *Print without new-line*)

---
Tags: code-golf, quine
---


# Question
Title: Throwback Friday: Renumber my ZX spectrum BASIC listing
The first programming language I was exposed to was Sinclair BASIC. Like many BASIC dialects, it requires all source code lines to be numbered.

As a result, use of the `GO TO` command was idiomatic and jumps execution to the given line number (no labels).

Also there is a related `GO SUB` command which can be used as a rudimentary function call. Again, execution jumps to the given line number, but when a `RETURN` command is reached, execution jumps back to the next instruction after the `GO SUB`.

Similarly the `RUN` command will restart program execution at the given line.

Anyone who has spent any time in a line-numbered BASIC interpreter will have learned to use a numbering scheme with gaps in it. This is so that it is easier to insert new lines of code. However even then, you may still find yourself needing to insert new lines in between consecutively numbered lines.

---

Given a line-numbered BASIC listing as input, output the same program but renumbered such that the line numbers start at 10 and increment by steps of 10. The input listing may have `GO TO` or `GO SUB` commands, so the numbers associated with these must also be adjusted.

* `GO TO` and `GO SUB` commands are either on their own lines or at the end of `IF` `THEN` lines. Its safe to say `^(\d+) .*GO (TO|SUB) (\d+)$` is sufficient to match such lines. These commands in quotes should be ignored.
* `RUN` commands will always be on their own lines. In this case a line number is optional. If it is missing, then the interpreter simply starts at the top of the program.
* If a `GO TO`, `GO SUB` or `RUN` command references a non-existent line, then it will instead jump to the next defined line. Your entry needs to deal with this and ensure any such line references are fixed so they point to the correct line. Behaviour may be undefined if a line number after the end of the program is given in one of these commands.
* Line numbers will always be positive integers 1 to 9999 (as per the manual). This means that input programs will never have more than 999 lines.
* Input lines will always be numbered in numerically ascending order.
* For the purposes of this challenge, input listings will only contain printable ASCII. You don't need to worry about the ZX character set. Having said that, if your entry is actually written in ZX BASIC or appropriate z80 assembly/machine code (and there are emulators out there), then you may choose for your input to be encoded in the ZX character set instead.
* You may not use any renumber libraries or utilities that are specifically tailored for this purpose.

### Example Input:

```
1 REM "A rearranged guessing game"
2 INPUT A: CLS
3 INPUT "Guess the number ", B
10 IF A=B THEN PRINT "Correct": STOP
100 IF A<B THEN GO SUB 125
120 IF A>B THEN GO SUB 122
121 GO TO 3
125 PRINT "Try again"
126 RETURN
127 REM "An example of GO TO 7 and GO SUB 13 in quotes"

```

### Example Output:

```
10 REM "A rearranged guessing game"
20 INPUT A: CLS
30 INPUT "Guess the number ", B
40 IF A=B THEN PRINT "Correct": STOP
50 IF A<B THEN GO SUB 80
60 IF A>B THEN GO SUB 80
70 GO TO 30
80 PRINT "Try again"
90 RETURN
100 REM "An example of GO TO 7 and GO SUB 13 in quotes"

```

---

I wanted to link to a ZX BASIC manual. The best I could find seems to be http://www.worldofspectrum.org/ZXBasicManual/index.html but this seems to be a dead link. The wayback machine has a copy though.

# Answer
> 5 votes
# JavaScript (ES6) 177

**Edit** Added the (costly) scan for the next valid line number

```
l=>l.split`
`.map((x,i)=>([,n,t]=x.match(/(\d+)(.*)/),l[n]=10*-~i,t),l=[]).map((x,i)=>10*-~i+x.replace(/(UN |GO TO |UB )(\d+)$/,(a,b,c)=>(l.some((v,i)=>i<c?0:a=b+v),a))).join`
`

```

**TEST**

```
f=l=>
  l.split`\n`
  .map((x,i)=>([,n,t]=x.match(/(\d+)(.*)/),l[n]=10*-~i,t),l=[])
  .map((x,i)=>10*-~i+x.replace(/(UN |GO TO |UB )(\d+)$/,(a,b,c)=>(l.some((v,i)=>i<c?0:a=b+v),a)))
  .join`\n`

//TEST
console.log=x=>O.textContent+=x+'\n'

test=`1 REM "A rearranged guessing game"
2 INPUT A: CLS
3 INPUT "Guess the number ", B
10 IF A=B THEN PRINT "Correct": STOP
100 IF A<B THEN GO SUB 125
120 IF A>B THEN GO SUB 122
121 GO TO 3
125 PRINT "Try again"
126 RETURN`
console.log(test+'\n\n'+f(test))
```

```
<pre id=O></pre>
```

# Answer
> 2 votes
# Perl 6, ~~147~~ ~~145~~ ~~144~~ 142 bytes

```
{my%a;.trans(/^^(\d+)/=>{%a{$0}=$+=10}).trans(/:s<!after \"\N*>(UN |GO TO |UB )(\d+)<!before \N*\">/=>{$0~%a{%a.keys».Num.grep(*>=$1).min}})}

```

This can probably be golfed down a bit more.

**Expanded**

```
my &f = -> $s {
    my %line-map; # This will map the old line numbers to the new ones

    $s.trans(/^^(\d+)/                    # This .trans creates the line number map
             => { %line-map{$0} = $+=10 } # as well as replaces the actual line numbers
            )\
      # This .trans replaces all the line numbers for each GO TO, GO SUB, RUN
      .trans(/:s<!after \"\N*>(UN |GO TO |UB )(\d+)<!before \N*\">/
             => {$0 ~ %line-map{%line-map.keys».Num.grep(*>=$1).min} }
            )
}

```

# Answer
> 1 votes
# Visual Basic for Applications, 288 bytes

I couldn't resist giving a solution in a BASIC dialect. Probably works with Visual Basic 6/.NET or other modern variants with minor changes.

```
Sub n(t,a)
f=Chr(10)
u=Chr(0)
Open t For Input As 1
a=f &Input(LOF(1),1)&f
Close
j=10
For i=1 To 9999
q=f &j &u
g=" GO TO "
w=i &f
m=j &f
a=Replace(Replace(Replace(Replace(a,g &w,g &m),f &i &" ",q),"B "&w,"B "&m),"UN "&w,"UN "&m)
If InStr(1,a,q)Then j=j+10
Next
a=Replace(a,u," ")
End Sub

```

I used a lot of one-letter variables for conciseness. Also, I supressed all unnecessary whitespaces (VBE expands them automatically on import). Byte count is for final .BAS file, with CHR(10) as newline.

The subroutine, that can be invoked from VBE immediate window, opens a Sinclair BASIC program (first parameter is the path to an ASCII file - with CHR(10) as newline - containing the program), renumber lines and write results to a Variant variable (second parameter).

The idea is to iterate on all possible source line numbers, ascending order, and for each one, replace at once all matching line numbers as well as `GO TO`, `GO SUB` and `RUN` references with the next available target line number. Using this approach we do not need any kind of translation table. The target line number is incremented each time a match in source line number is found, so "wrong" line references are adjusted automatically to the next valid number. Newline characters are used as markers of start- and end-of-line, and a CHR(0) - never used in the program as it is not printable - is used as a temporary marker, to avoid renumbering the same line multiple times.

Some remarks:

* For conciseness, we use the smaller possible string for a match with the jumping statements. Using the end-of-line on our search strings we do not run into the risk of including quoted occcurrences or user functions (that always use parenthesis in Sinclair). `GO TO` requires a larger string because of the `FOR ... TO` construct (e.g. compare `50 FOR X=AGO TO 100` and `50 GO TO 100`)
* The code does not support statements in the form `GO TO200` (without whitespace), although the ZX manual implies that it is valid code on several examples (It would cost a dozen more bytes to deal with it).
* The code adds a newline at the beginning and another at the end of the program. I could clean this up in the end (a dozen more bytes) but figure that the ZX would probably ignore blank lines.

Below, a more readable version:

```
Sub Renumber(ByVal ProgramPath As String, ByRef Program As Variant)

    Open ProgramPath For Input As #1
    Program = Chr(10) & Input(LOF(1), 1) & Chr(10)
    Close

    NewNumber = 10
    For OldNumber = 1 To 9999
        Program = Replace(Program, " GO TO" & OldNumber & Chr(10), " GO TO" & NewNumber & Chr(10)) 'self-explaining
        Program = Replace(Program, Chr(10) & OldNumber & " ", Chr(10) & NewNumber & Chr(0)) 'matches line number (and replaces whistespace with Chr(0) to avoid re-replacing
        Program = Replace(Program, "B " & OldNumber & Chr(10), "B " & NewNumber & Chr(10)) 'matches GO SUB
        Program = Replace(Program, "UN " & OldNumber & Chr(10), "UN " & NewNumber & Chr(10)) 'matches RUN
        If InStr(1, Program, Chr(10) & NewNumber & Chr(0)) Then NewNumber = NewNumber + 10 'if there is such a line, increment NewNumber
Next
Program = Replace(Program, Chr(0), " ") 'replace back Chr(0) with whitespace
End Sub

```

# Answer
> 1 votes
# Pip `-rn`, 63 bytes

```
Ygn:#{_<aFIy}*t+tgR`(RUN|GO (SUB|TO)) (\d+)$`{b.s.(nd)}R`^\d+`n

```

Try it online!

## Explanation

### Setup

The `-r` flag reads all of stdin and stores it as a list of lines in the local variable `g`. The global variable `t` is preinitialized to 10, and the global variable `s` is preinitialized to `" "`.

```
Yg

```

Yanks the list of lines `g` into the global variable `y`, so that it's available inside the function we're about to define.

### Line number translation function

We construct a function that maps from any line number in the original numbering scheme (including a non-existent one) to the corresponding line number in the new numbering scheme.

Suppose we have these lines:

```
1 INPUT A
4 PRINT A
9 IF A=1 THEN GO TO 3

```

We want to map 1 to 10, 2-4 to 20, and 5-9 to 30. If we have a list of the original line numbers (`[1; 4; 9]`), we can use a filter operation to find out how many of these numbers are less than the line number we're trying to convert. Multiply that result by 10 and add 10, and we have the desired answer.

For example, when converting 9, there are two line numbers (1 and 4) less than 9. 2\*10+10 gives 30. When converting 3, there is one line number (1) less than 3. 1\*10+10 gives 20.

Here's the code (slightly modified to be easier to read):

```
n:{#(_<aFIy)*t+t}
  {             }  Lambda function with parameter a:
        FIy         Filter y (the list of program lines) for
     _<a             lines that are numerically less than a
                    (In a numeric context, only the first run of digits on the line is considered)
   #(      )        Number of items in the filtered list
            *t+t    Times 10, plus 10
n:                 Assign that function to global variable n

```

### First replacement: `GO TO`, `GO SUB`, and `RUN`

The rest of the program is a single expression that takes `g` and does a couple of regex replacements (which vectorize, applying to each line in `g`).

Here's the first replacement:

```
g R `(RUN|GO (SUB|TO)) (\d+)$` {b.s.(nd)}

```

The regex matches any of `RUN`, `GO SUB` and `GO TO`, followed by a number, followed by end of line. This ensures it doesn't match inside strings, nor does it match `RUN` without a line number.

The order of the capturing groups is important. The first group captures the command (one of `RUN`, `GO SUB`, or `GO TO`). The second group, if used, captures either `SUB` or `TO`. We don't need to capture this part, but a non-capturing group would require extra bytes. Then the third group captures the line number.

We use a callback function for the replacement. With callback functions in Pip, the whole match is the first argument `a`, and the capture groups in order are the subsequent arguments `b`, `c`, `d`, and `e`. So we have the command in the first group, which goes in `b`, and the line number in the third group, which goes in `d`. The only change we need to make is to pass the line number through our conversion function, which is called Lisp-style: `(nd)`. Then we concatenate that together with `b` and a space and return it.

### Second replacement: line numbers

All that's left to convert is the line numbers at the beginnings of lines.

```
(...) R `^\d+` n

```

The regex matches a run of digits at the beginning of a line. Again we use a callback function; this time, the conversion function `n` itself is sufficient, since the whole match (first argument, `a`) is the number we want converted.

Since this is the last expression in the program, Pip autoprints the result. The `-n` flag separates the result list with newlines.

---
Tags: code-golf
---