title: Find the unique twins

text:
# Question
Title: Find the unique twins
You will be given two Arrays / Lists / Vectors of non-negative integers **A** and **B**. Your task is to output the highest integer **N** that appears in both **A** and **B**, and is also unique in both **A** and **B**.

---

Test Cases:

```
A, B -> Output

[6], [1, 6] -> 6
[1, 2, 3, 4], [4, 5, 6, 7] -> 4
[0, 73, 38, 29], [38, 29, 73, 0] -> 73
[1, 3, 4, 6, 6, 9], [8, 7, 6, 3, 4, 3] -> 4
[2, 2, 2, 6, 3, 5, 8, 2], [8, 7, 5, 8] -> 5
[12, 19, 18, 289, 19, 17], [12, 19, 18, 17, 17, 289] -> 289
[17, 29, 39, 29, 29, 39, 18], [19, 19, 18, 20, 17, 18] -> 17
[17, 29, 39, 29, 29, 39, 18, 18], [19, 19, 18, 20, 17, 18] -> 17

```

# Answer
> 7 votes
# Python 3, 61 56 54 bytes

Saved 7 bytes thanks to @Mr.Xcoder, @pizzapants184 and @ovs

```
lambda a,b:max(f*(a.count(f)==b.count(f)<2)for f in a)

```

Try it online!

# Answer
> 7 votes
# Jelly, 7 bytes

```
fċ@ÐṂ;Ṁ

```

Try it online!

### How it works

```
fċ@ÐṂ;Ṁ  Main link. Left argument: A. Right argument: B

f        Filter; keep those elements of A that appear in B.
   ÐṂ    Yield all elements of the result for which the link to left yields a
         minimal value (2).
 ċ@        Count the occurrences of the element...
     ;     in the concatenation of A and B.
      Ṁ  Take the maximum.

```

# Answer
> 7 votes
# Bash \+ coreutils, 49 bytes

```
U()(sort -rn|uniq -u$1)
(U<<<$1;U<<<$2)|U D|sed q

```

*Thanks to @seshoumara for golfing off 1 byte!*

Try it online!

### How it works

*uniq* takes sorted input and performs one or several actions, depending on the command-line flags.

`U<<<$1` and `U<<<$2` call the function `U` with the first and second command-line argument as input. For each one, `sort -rn|uniq -u` is executed, sorting the input numerically (`-n`) and in descending order (`-r`) for *uniq*, which will print only unique lines (`-u`).

The output of both (unique elements of each array) is concatenated and piped to `U D`, i.e.,
`sort -rn|uniq -uD`. This time, *uniq* will only print duplicate lines (`-D`), and only the first repetition of each.

While the man page says it will print all repetitions, the added `-u` causes `-D` to print only the first occurrence of duplicated lines. This behavior is normally achieved with `uniq -d`.

Finally, `sed q` quits immediately, reducing its input (unique elements of both arrays) to its first line. Since the output was sorted in descending order, this is the maximum.

# Answer
> 6 votes
# Pyth, ~~12~~ 9 bytes

Try it

```
eS@Fm.m/d

```

Saved 3 bytes thanks to Mr. Xcoder.

### Explanation

```
eS@Fm.m/d
    m  /d   Count the occurrences of each element.
     .m     Take only those that appear the minimum number of times.
  @F        Apply the above to A and B and take the intersection.
eS          Take the largest.

```

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

-1 byte thanks to Erik the Outgolfer

```
εÐ¢Ï}`Ãà

```

Try it online!

```
ε   }    # For each input
 Ð¢Ï     #   Get the unique elements
     `Ã  # Keep only the elements that appear in both lists
       à # Keep the greatest element
         # Implicit print

```

# Answer
> 5 votes
# Husk, 7 bytes

```
→►≠OfEΠ

```

Takes input as a list of two lists, works for any number of lists as well (returning the highest number that occurs exactly once in each, if possible). Try it online!

## Explanation

This is the first Husk answer to (ab)use the new "maximum by" function .

```
→►≠OfEΠ  Implicit input, say [[3,2,1,3],[1,2,3,4]]
      Π  Cartesian product: [[3,1],[2,1],[3,2],[2,2],[1,1],[3,3],[1,2],[3,1],[3,4],[2,3],[1,3],[3,2],[2,4],[3,3],[1,4],[3,4]]
    fE   Keep those that have equal elements: [[2,2],[1,1],[3,3],[3,3]]
   O     Sort: [[1,1],[2,2],[3,3],[3,3]]
 ►≠      Find rightmost element that maximizes number of other elements that are not equal to it: [2,2]
→        Take last element: 2

```

# Answer
> 4 votes
# Bash + coreutils, 60 bytes

```
f()(sort -rn<<<"$1"|uniq -u);grep -m1 -wf<(f "$1") <(f "$2")

```

Try It Online

# Bash, 89 bytes

```
c()(for e;{((e^$1||r++,2^r));});for x in $1 $2;{((x<r))||c $x $1||c $x $2||r=$x;};echo $r

```

TIO

# Answer
> 3 votes
# Jelly, 11 bytes

```
ċ@Ị¥Ðf`€f/Ṁ

```

Try it online!

# Answer
> 3 votes
# J, 23 bytes

```
>./@([-.-.)&(-.-.@~:#])

```

`(-.-.@~:#])` removes from a list any repeated elements

`&` do this to both args

`([-.-.)` We want A intersect B. This is the equivalent phrase: "A minus (A minus B)"

`>./` Take the max

Try it online!

# Answer
> 2 votes
# PowerShell, 94 bytes

```
param($a,$b)filter f($x){$x|group|?{$_.count-eq1}}
(f($a|sort|?{$_-in((f $b).Name)}))[-1].Name

```

Try it online!

Takes input `$a` and `$b` as arrays. Constructs a `filter` that `group`s the input array elements together and pulls out only those with a `count` `-eq`ual to `1` (i.e., only those that are unique in the input array).

The next line then constructs the algorithm. First we `sort` `$a`, then pull out those that are `-in` the unique items of `$b`. Those are then themselves unique-ified, the largest `[-1]` is chosen, and we take the `.Name` thereof. That's left on the pipeline and output is implicit.

# Answer
> 2 votes
# Javascript (ES6), 102 86 75 71 bytes

```
a=>b=>Math.max(...a.map(e=>(g=x=>x.map(y=>y-e||x--,x=1)|!x)(a)*g(b)*e))

```

Thanks @justinMariner for getting from 102 to 86

Thanks @tsh for getting from 86 to 75

Thanks @Arnauld for getting from 75 to 71

Try it online!

# Answer
> 2 votes
# Java 8, 133 bytes

```
a->b->{long r;for(java.util.Collections c=null;;a.remove(r))if(b.contains(r=c.max(a))&c.frequency(a,r)*c.frequency(b,r)==1)return r;}

```

**Explanation:**

Try it here.

```
a->b->{                  // Method with two ArrayList<Long> parameters and long return-type
  long r;                //  Result-long
  for(java.util.Collections c=null;
                         //  Create a java.util.Collections to save bytes
      ;                  //  Loop indefinitely
       a.remove(r))      //    After every iteration, remove the current item
    if(b.contains(r=c.max(a))
                         //   If the maximum value in `a` is present in `b`,
       &c.frequency(a,r)*c.frequency(b,r)==1)
                         //   and this maximum value is unique in both Lists:
      return r;          //    Return this value
                         //  End of loop (implicit / single-line body)
}                        // End of method

```

# Answer
> 2 votes
# Haskell, ~~57~~ 53 bytes

```
x?y|let v!x=filter(==v)x==[v]=maximum[a|a<-x,a!x,a!y]

```

Try it online!

**UPD:** Thanks @Laikoni

# Answer
> 2 votes
# C# (.NET Core), ~~85~~ 84 bytes

```
x=>y=>x.Where(a=>x.Count(b=>b==a)<2).Intersect(y.Where(a=>y.Count(b=>b==a)<2)).Max()

```

Try it online!

Naive solution with LINQ (`using System;using System.Linq;` +31chars so 116 bytes with header)

84! I forgot currying!

# Answer
> 2 votes
# F# (.NET Core), ~~117~~ ~~115~~ ~~114~~ ~~111~~ 108 bytes

## ~~115~~ 114 bytes

Another solution with `countBy` this time:

```
let u x=x|>Seq.countBy id|>Seq.filter(fun a->snd a=1)|>Seq.map fst|>set
let f x y=Set.intersect(u x)(u y)|>Seq.max

```

Try it online!

## ~~117~~ 111 bytes

```
let u x=x|>Seq.filter(fun a->x|>Seq.filter((=)a)|>Seq.length=1)|>set
let f x y=Set.intersect(u x)(u y)|>Seq.max

```

Try it online!

100% F#! Any help is welcome!

6 byte won thanks to prefix notation!

## 108 bytes

```
let f a b=Set.intersect(set a)(set b)|>Seq.filter(fun x->a@b|>Seq.filter(fun y->y=x)|>Seq.length<3)|>Seq.max

```

`@` is the concat function! Thank you @Ayb4btu for this algorithm.

Try it online!

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

```
Max@Cases[Tally@#⋂Tally@#2,{x_,1}:>x]&

```

Try it online!

# How it works

`Tally@#` gives a list of the unique elements of the first input, together with their counts: e.g., `Tally[{2,2,2,6,3,5,8,2}]` yields `{{2,4},{6,1},{3,1},{5,1},{8,1}}`.

`Tally@#2` does the same for the second list, and  finds pairs present in both. Then we pick out (with `Cases`) pairs ending in `1`, taking the first element of each result, which gives us a list of all the unique twins. Finally, `Max` returns the largest unique twin.

# Answer
> 2 votes
# SQLite, 118 bytes

```
SELECT MAX(x)FROM(SELECT X FROM A GROUP BY X HAVING COUNT(X)=1
INTERSECT
SELECT X FROM B GROUP BY X HAVING COUNT(X)=1)

```

Try it online!

First time in SQL, any help is welcome!

# Answer
> 2 votes
# Röda, 48 bytes

```
{m={|n|sort|count|[_]if[_=n]};[_()|m 1]|m 2|max}

```

Try it online!

Inspired by jq170727's jq answer.

Explanation:

```
{ /* Anonymous function, takes input from the stream */
  m={|n|        /* Local function m with parameter n: */
    sort|count| /*   Count unique values in the stream */
    [_]if[_=n]  /*   For each value, push it to the stream if its count is n */
  };
  [      /* For each list in the stream: */
    _()| /*   Flat it (push its values to the stream) */
    m 1  /*   Push values that appear only once to the stream */
  ]|
  m 2|   /* Push values that appear twice to the stream */
  max    /* Find the max value in the stream */
}

```

# Answer
> 2 votes
# Pip, ~~17~~ 16 bytes

```
MX{_Na=_Nb=1FIa}

```

This is a function that takes two lists as arguments. Try it online!

### Explanation

```
  {            }  Define function, args are a & b:
            FIa    Filter elements of a on this function:
   _Na              Count of element in a
      =_Nb          equals count of element in b
          =1        equals 1
                  This gives a function that returns a list of unique twins
MX                Modify it to take the max and return that instead

```

# Answer
> 2 votes
# APL (Dyalog), 18 chars = 23 bytes\*

A full program body. Prompts for list of lists from STDIN. Works with any number of lists. Outputs to STDOUT.

```
⌈/∊∩/{⊂⍺⍴⍨1=≢⍵}⌸¨⎕

```

Try it online!

prompt for evaluated input from STDIN

`{``}⌸¨` for each list, call the following function for each unique element in that list, using the unique element as left argument () and the list of indices of its occurrence as right argument ():

`≢⍵` the tally of indices (i.e. the number of occurrences)

`1=` equal to 1

`⍺⍴⍨` use that to reshape the specific element (i.e. gives empty list if non-unique)

Now we have two lists of unique elements for each input list (although each element is a list, and there are empty lists as residue from the non-unique elements).

`∩/` intersection (reduction)

**ϵ**nlist (flatten)

`⌈/` max (reduction)

---

* in Classic, counting  as `⎕U2338`.

# Answer
> 1 votes
# MATL, 13 bytes

```
,iSY'1=)]X&X>

```

Try it online! Or Verify all test cases.

### Explanation

```
,      % Do twice
  i    %   Take input: array
  S    %   Sort array
  Y'   %   Run-length encode: pushes array of values and array of run lengths
  1=   %   Compare each run length with 1
  )    %   Use as logical index. This keeps only values that have appeared once
]      % End
X&     % Intersection of the two arrays
X>     % Maximum of array. Implicitly display

```

# Answer
> 1 votes
# PHP, 98 bytes

```
<?foreach(($c=array_count_values)($_GET[a])as$a=>$n)$n-1||$c($_GET[b])[$a]-1||$a<$r||$r=$a;echo$r;

```

Provide arrays as GET parameters `a` and `b`.

# Answer
> 1 votes
# , 73 bytes

```
function(A,B)max(setdiff(intersect(A,B),c(A[(d=duplicated)(A)],B[d(B)])))

```

Try it online!

Computes `A` intersect `B`, then the maximum of the difference between that and the duplicated elements of `A` and `B`.

# Answer
> 1 votes
# JavaScript ES5, ~~122~~ ~~121~~ 114 bytes

```
function f(a,b){for(i=a.sort().length;--i+1;)if(a[i]!=a[i+1]&&a[i]!=a[i-1]&&!(b.split(a[i]).length-2))return a[i]}

```

I'm new here, so I don't really know if I can remove the function definition and just put its contents (which would save me 17 bytes)

Here's the working example: ~~122~~ ~~121~~ 114

122 to 121 bytes: Wrapping initialization in a for

121 to 114 bytes: `b` has to be a string

# Answer
> 1 votes
# C# (.NET Core), 66+31=97 65+31=96 bytes

```
a=>b=>a.Intersect(b).Where(x=>a.Concat(b).Count(y=>y==x)<3).Max()

```

Try it online!

+31 bytes for `using System;using System.Linq;`

I took inspiration from @aloisdg's answer. However, instead of searching for unique values in both arrays, I inverted the order of operations so that `intersect` is first, and then find the max value of the items that occur twice when the arrays are concatenated and are in their intersect. I can use `<3` as `Count` will be at least 2 for any value, as it will be in both arrays.

### Acknowledgements

-1 byte thanks to @aloisdg and his suggestion to use `Func` currying.

# Answer
> 1 votes
# Jq 1.5, 76 bytes

```
def m(n):[.[indices(.[])|select(length==n)[]]]|unique[];[map(m(1))|m(2)]|max

```

Expanded

```
def m(n): # function to emit elements of multiplicity n
  [
    .[                         # select elements with
         indices(.[])          # number of indices in the array
       | select(length==n)[]   # equal to specified multiplicity
    ]
  ] | unique[]                 # emit deduped values
;

[
    map(m(1))   # collect multiplicity 1 elements from each array
  | m(2)        # collect multiplicity 2 elements
] | max         # choose largest of these elements

```

Try it online!

Here is another solution which is the same length:

```
def u:[keys[]as$k|[.[$k]]-(.[:$k]+.[$k+1:])]|add;map(u)|.[0]-(.[0]-.[1])|max

```

Expanded

```
def u: # compute unique elements of input array
  [
      keys[] as $k                   # for each index k
    | [.[$k]] - (.[:$k]+.[$k+1:])    # subtract other elements from [ .[k] ]
  ]                                  # resulting in [] if .[k] is a duplicate
  | add                              # collect remaining [ .[k] ] arrays
;
  map(u)                             # discard duplicates from each input array
| .[0]-(.[0]-.[1])                   # find common elements using set difference
| max                                # kepp largest element

```

Try it online!

# Answer
> 1 votes
# APL, 47 bytes

```
{1↑R[⍒R←((1={+/⍵=A}¨A)/A←⍺)∩(1={+/⍵=B}¨B)/B←⍵]}

```

Declares an anonymous function that takes two vectors, eliminates duplicate elements, then finds the biggest element in the intersection of the results.

`A←⍺` and `B←⍵` store the arguments passed to the function in `A` and `B`.

`a=b` returns a vector with 1 in each index in which `a` is equal to `b`. If `a` is a scalar (i.e. single quantity and not a vector) this returns a vector with 1 wherever the element in `b` is `a` and 0 when it is not. For example:

```
Input: 1=1 2 3
Output: 1 0 0

```

`{+/⍵=A}`: nested anonymous function; find the occurrences of the argument in vector `A` and add them up i.e. find the number of occurrences of the argument in `A`

`1={+/⍵=A}¨A`: apply the nested anonymous function to each element in A and find the ones that equal 1 i.e. unique elements

`((1={+/⍵=A}¨A)/A←⍺)`: having found the *location* of the unique elements, select just these elements in the original vector (`/` selects from the right argument elements whose locations correspond to 1 in the left argument)

`R←((1={+/⍵=A}¨A)/A←⍺)∩(1={+/⍵=B}¨B)/B←⍵`: repeat the process for the second argument; now that we have just the unique elements, find the intersection i.e. common elements and store this in vector `R`

`R[⍒R]`: access the elements of `R` in decreasing order

`1↑R[⍒R]`: take the first element of `R` when it's sorted in decreasing order

Test case:

```
Input: 17 29 39 29 29 39 18 18 {1↑R[⍒R←((1={+/⍵=A}¨A)/A←⍺)∩(1={+/⍵=B}¨B)/B←⍵]} 19 19 18 20 17 18
Output: 17

```

# Answer
> 1 votes
# , 30 bytes

```
[:>./@,[*([*+/"1(1=*/)+/)@(=/)

```

How it works:

I start with testing where the two list overlap by `=/` (inserts equality test between all the members of the lists:

```
   a =. 1 3 4 6 6 9
   b =. 8 7 6 3 4 3
   ]c=. a =/ b
0 0 0 0 0 0
0 0 0 1 0 1
0 0 0 0 1 0
0 0 1 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0

```

More than one 1 in the same column means that the number is not unique for the left argument (6 in this case); in the row - for the right argument (3)

Then I sum up all rows and all columns to find where are the duplicates:

```
   +/ c
0 0 2 1 1 1
   +/"1 c
0 2 1 1 1 0

```

I find the cartesian product of the above lists and set the members greater than 1 to 0.

```
    m =. (+/"1 c) (1=*/) +/c
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 1 1 1
0 0 0 1 1 1
0 0 0 1 1 1
0 0 0 0 0 0

```

I mask the equality matrix c with m to find the unique elements that are common to both lists and multiply the left argument by this.

```
]l =. a * m * c
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 4 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

```

Then I flatten the list and find the max element:

```
 >./,l
4

```

Try it online!

# Answer
> 0 votes
# Octave, ~~57~~ 56 bytes

```
@(x)max(intersect(cellfun(@(x){x(sum(x'==x)==1)},x){:}))

```

Anonymous function that takes as input a cell array of two numerical arrays.

**Try it online!**

### Explanation

For each (`cellfun(@(x)...)`) of the two input arrays, this creates a matrix of pairwise equality comparisons between its entries (`x.'==x`); keeps (`x(...)`) only the entries for which the column sum is `1` (`sum(...)==1`); and packs the result in a cell (`{...}`). The intersection (`intersect`) of the two results (`{:}`) is computed, and the maximum (`max(...)`) is taken.

# Answer
> 0 votes
# Wolfram Language (Mathematica), 49 bytes

```
Last@Select[a=Join@##;Sort[#⋂#2],a~Count~#<3&]&

```

Try it online!

# Answer
> 0 votes
# Perl 5, 71 +2 (-ap) bytes

```
$F{$_}++for@F;map$\=$F{$_}^1||$L{$_}>1||$_<$\?$\:$_,keys%L;(%L,%F)=%F}{

```

Try It Online

# Answer
> 0 votes
# Java 8, ~~134~~ 132 bytes

Both args are `List<Integer>`

```
a->b->a.stream().filter(i->b.stream().filter(j->i-j==0).count()*a.stream().filter(j->i-j==0).count()==1).max(Integer::compare).get()

```

# Answer
> 0 votes
# Axiom,~~126~~ ~~74~~ ~~68~~ 58 bytes

```
q(a,b)==reduce(max,[x for x in a|count(x,a)*count(x,b)=1])

```

And with this I have less characters of JavaScript solutions and in general easier to read too (at last now...)

In mathematical words it would "find the max element of the list of the x in a, that are present 1 time only in a and 1 time only in b". This suppose that exist one element of the List \[x for x in a|count(x,a)=1 and count(x,b)=1\] as the question require. The other solution of 126 bytes

```
f(a,b)==(c:=reverse(sort(setIntersection(a,b)));for i in 1..#c repeat if count(c.i,a)=1 and count(c.i,b)=1 then return c.i;-1)

```

Results:

```
(6) -> q([1,2,3], [1,2,2,3])
   (6)  3
                                                    Type: PositiveInteger
(7) -> q([6], [1,6])
   (7)  6
                                                    Type: PositiveInteger
(8) -> q([1,2,3,4], [4,5,6,7])
   (8)  4
                                                    Type: PositiveInteger
(9) -> q([0,73,38,29], [38,29,73,0])
   (9)  73
                                                    Type: PositiveInteger
(10) -> q([1,3,4,6,6,9], [8,7,6,3,4,3])
   (10)  4
                                                    Type: PositiveInteger

```

# Answer
> 0 votes
# Ruby, ~~56~~ 49 bytes

```
->a,b{((r=a+b).select{|e|r.count(e)==2}&a&b).max}

```

Try it online!

# Answer
> 0 votes
# PHP, 95 bytes

```
<?=max(array_intersect(e(A),e(B)));function e($a){return array_keys(array_count_values($a),1);}

```

Given A and B are defined constants holding each array.

# Answer
> 0 votes
# APL NARS ~~40~~ 28 chars

```
{⌈/g⍺∩(g←{⍵/⍨⊃1=+/(⊂⍵)=⍵})⍵}

```

g(⍵) return one list of elments of list ⍵ that appear in ⍵ 1 time only.

To the function for the question is assigned the name 'f' as (⍺)f(⍵) see below.

```
  f←{⌈/g⍺∩(g←{⍵/⍨⊃1=+/(⊂⍵)=⍵})⍵}
  1 2 3 f 1 2 2 3
3
  6 f 1 6
6
  1 2 3 4 f 4 5 6 7
4
  0 73 38 29 f 38 29 73 0
73
  1 3 4 6 6 9 f 8 7 6 3 4 3
4

```

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


title: Communistic Substring Normalization

text:
# Question
Title: Communistic Substring Normalization
If a string **T** of length **K** appears **K** or more times in a string **S**, then it is *potentially communistic*. For example, `10` in `10/10` is potentially communistic, for it appears *2* times and is of length *2*. Note that these substrings cannot overlap.

A *communistic transformation* is one that takes this string **T** and moves each character **t**<sub>*i*</sub> of **T** to the *i* occurrence of **T** in **S**. So, for the previous example, the communistic transformation would yield `1/0`; the first char of `10` replaces `10` the first time `10` is found, and `0` the second time.

A *communistic normalization* is a function that takes all such strings **T** with **K** ≥ 2 and performs a *communistic transformation* on them.

Some specifics on the algorithm:

1. Perform communistic transformations on the longest valid strings **T** *first*. Favor the first occurrences of **T**.
2. Then, perform communistic transformations on the next-longest strings, then the next-next-longest... etc.
3. Repeat until no such strings exist in the string.

Note that some strings, such as the "Hello, Hello" example in the test cases, can be interpreted two different ways. You can use `ell` for **T**, but you can also use `llo`. In this case, your code can choose either option. The shown test case uses `llo`, but you may get a different and equally valid output.

---

Your task is to implement communistic normalization. The input will only ever consist of printable ASCII characters (0x20 to 0x7E, space to tilde). You may write a program or function to solve this task; the input may be taken as a line from STDIN, string/character array argument, argument from ARGV, etc.

## Test cases

```
'123' -> '123'
'111' -> '111'
'1111' -> '11'
'ABAB' -> 'AB'
'111111111' -> '111'
'asdasdasd' -> 'asd'
'10/10' -> '1/0'
'100/100+100' -> '1/0+0'
'   +   +   ' -> ' + '
'Hello, hello, dear fellow!' -> 'Hel he, dear feow!' OR 'Heo hl, dear flow!'
'11122333/11122333/11122333' -> '112/13' OR '132/23'

'ababab1ababab' -> 'a1bab'
'1ab2ab3ab4ab5ab6' -> '1a2b3a4b5ab6'

```

## Worked out test case

Format is `'string', 'substring'`, at each step of replacement. Replaced bits are bracketed.

```
'11[122]333/11[122]333/11[122]333', '122'
'111[333]/112[333]/112[333]', '333'
'1113/11[23]/11[23]', '23'
'11[13]/112/1[13]', '13'
'1[11]/[11]2/13', '11'
'1[/1]12[/1]3', '/1'
'112/13', ''

```

Another test case:

```
'Hello, hello, dear fellow!', 'llo'
'Hel, hel, dear feow!', 'l,'
'Hel he, dear feow!', ''

```

## Reference code (Python)

You may find this useful to visualize the algorithm.

```
#!/usr/bin/env python

import re

def repeater(string):
    def repeating_substring(substring):
        return (string.count(substring) == len(substring)) and string.count(substring) > 1

    return repeating_substring

def get_substrings(string):
    j = 1
    a = set()
    while True:
        for i in range(len(string) - j+1):
            a.add(string[i:i+j])
        if j == len(string):
            break
        j += 1
    return list(a)

def replace_each_instance(string, substring):
    assert `string`+',', `substring`
    for i in substring:
        string = re.sub(re.escape(substring), i, string, 1)

    return string

def main(s):
    repeats = repeater(s)
    repeating_substr = filter(repeater(s), get_substrings(s))

    while repeating_substr:
        repeating_substr.sort(lambda x,y: cmp(len(y), len(x)))
        s = replace_each_instance(s, repeating_substr[0])
        repeating_substr = filter(repeater(s), get_substrings(s))

    return s

assert main('123') == '123'
assert main('111') == '111'
assert main('1111') == '11'
assert main('ABAB') == 'AB'
assert main('111111111') == '111'
assert main('asdasdasd') == 'asd'
assert main('10/10') == '1/0'
assert main('100/100+100') == '1/0+0'
assert main('   +   +   ') == ' + '
assert main('Hello, hello, dear fellow!') == 'Hel he, dear feow!'
assert main('11122333/11122333/11122333') == '112/13'

```

Thanks to @ConorO'Brien for posting the original idea of this challenge.

# Answer
# Pyth, 22 bytes

```
u.xse.iLcGdf>cGTlTt#.:

```

Test suite

To actually see what the program is doing, check out this:

Internals

In particular, the program always uses the final-occuring replacement of the longest replacements.

Explanation:

```
u.xse.iLcGdf>cGTlTt#.:
u.xse.iLcGdf>cGTlTt#.:G)GQ    Implicit
u                        Q    Starting with the input, repeat the following
                              until a fixed point is reached.
                    .:G)      Construct all substrings of the current value
                              ordered smallest to largest, front to back.
                  t#          Filter on having more than 1 element.
                              These are the eligible substrings.
           f                  Filter these substrings on
             cGT              Chop the current value on the substring,
            >   lT            Then remove the first len(substring) pieces.
                              The result is nonempty if the substring is
                              one we're looking for.
                              Chopping gives nonoverlapping occurrences.
     .iL                      Interlace the substrings with
        cGd                   Chop the current value on that substring
   se                         Take the final result, make it a string.
 .x                     G     If there weren't any, the above throws an error,
                              So keep the current value to halt.

```
> 2 votes

# Answer
# JavaScript (ES6), 121 bytes

```
f=(s,j=2,o,m=s.match(`(.{${j}})(.*\\1){${(j-1)}}`))=>m?f(s,j+1,s.split(m[1]).map((e,i)=>e+(m[1][i]||'')).join``):o?f(o):s

```

Recursively matches the pattern:

```
(.{2})(.*\1){1}  //2 characters, repeated 1 time
(.{3})(.*\1){2}  //3 characters, repeated 2 times
(.{4})(.*\1){3}  //4 characters, repeated 3 times
etc.

```

… until the pattern isn't found. (This guarantees that the longest string is handled first.)

It then performs the "communistic transformations" on the last-found pattern, by splitting on the match, and joining on each of the match's characters. (`map` is used for this purpose. Too bad `join` doesn't take a callback.)

It finally recurses on this new string until it is no longer *communistic*.

**Test cases:**

```
f=(s,j=2,o,m=s.match(`(.{${j}})(.*\\1){${(j-1)}}`))=>m?f(s,j+1,s.split(m[1]).map((e,i)=>e+(m[1][i]||'')).join``):o?f(o):s

console.log(f('123'));  //123
console.log(f('111'));  //111
console.log(f('1111')); //11
console.log(f('ABAB')); //AB
console.log(f('111111111')); //111
console.log(f('asdasdasd')); //asd
console.log(f('10/10')); //1/0
console.log(f('100/100+100')); //1/0+0
console.log(f('   +   +   ')); // +
console.log(f('Hello, hello, dear fellow!')); //Heo hl, dear flow!
console.log(f('11122333/11122333/11122333')); //132/23
```
> 4 votes

# Answer
# Clean, ~~420~~ ... 368 bytes

```
import StdEnv,StdLib
l=length
%q=any((==)q)
?_[]=[]
?a[(y,x):b]|isPrefixOf a[x:map snd b]=[y: ?a(drop(l a-1)b)]= ?a b
$s=sortBy(\a b=l a>l b)(flatten[[b: $a]\\(a,b)<-map((flip splitAt)s)[0..l s-1]])
f s#i=zip2[0..]s
#r=filter(\b=l(?b i)>=l b&&l b>1)($s)
|r>[]#h=hd r
#t=take(l h)(?h i)
=f[if(%n t)(h!!hd(elemIndices n t))c\\(n,c)<-i|not(%n[u+v\\u<-t,v<-[1..l h-1]])]=s

```

Try it online!
> 1 votes

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


title: Help me with my chemistry homework!

text:
# Question
Title: Help me with my chemistry homework!
Near the middle of the semester in chemistry, we get problems like:

> Convert 1.283850057 to Scientific Notation

and

> Convert 3.583✕106 to Standard Notation

This is just stupid busy work for people who already know how to do this. So…

## The Challenge

Given an input in any reasonable, convenient format, in either standard notation or scientific notation, output the same number in the other notation. However, note that `e` will not be accepted in place of `*10^`, as this gives a significant advantage to languages with builtins with `e`.

***If not otherwise specified,*** standard notation will take this format:

```
x             (an integer)
xxxxxxxxxx    (a large integer with no more than 10 digits)
x.xxxx        (a float)
x.xxxxxxxxxx  (a float with no more than 10 x's after the decimal point)

```

While scientific notation will take this format:

```
x*10^x
x.zzzz*10^z (x will be >= 1)
x*10^-x
x.zz*10^-xx (x will be >= 1)

```

## I/O

Input will never contain more than 10 leading+10 trailing digits, and you may decide how to deal with trailing zeroes after the decimal point. The exponent will never be so large as to max out your language's allowance for large numbers. You should only need to handle up to about 1010.

```
input => output

---scientific to standard---

4.5*10^7 => 45000000
1*10^0 => 1
8.9*10^-2 => 0.089
1.0001*10^5 => 100010
9.999999*10^9 => 9999999000
4.00038*10^2 => 400.038

---standard to scientific---

7354 = 7.354*10^3
385.43 => 3.8543*10^2
0.32 = 3.2*10^-1
0.00044 => 4.4*10^-4
0.053 => 5.3*10^-2

```

As always, standard loopholes are disallowed. This is , so shortest bytes wins!

# Answer
# , 70 bytes

```
function(s)sub("e","*10^",format(eval(parse(t=s)),sc=!grepl("\\^",s)))

```

Try it online!

An anonymous function. Takes input as a string and outputs as a string.

This function evaluates the string `eval(parse(t=s))`, then `format`s it, with the flag `scientific` set to whether the string contains a `^` or not. Then it replaces `e` with `*10^` to match the right output spec.
> 5 votes

# Answer
# Python 3, 100 bytes

```
lambda a:eval(a.replace("*10^","e+"))if type(a)==str else re.sub("0*e\+?0*","*10^","%e"%a)
import re

```

Try it online!
> 2 votes

# Answer
## JavaScript (ES6), ~~83~~ 80 bytes

```
a=>(r=a.split(N='*10^'))[1]?+r.join`e`+'':(+a).toExponential().replace(/e\+?/,N)

```

An anonymous function. Takes input as a string and outputs as a string.
> 1 votes

# Answer
# Python 2, 87 bytes

```
lambda s:eval(s.replace('^','**'))if'^'in`s`else re.sub('e\+?','*10^','%e'%s)
import re

```

Try it online!
> 1 votes

# Answer
# Excel VBA, 80 Bytes

Anonymous VBE immediate window function that takes input from cell `[A1]` and outputs to the VBE immediate window.

```
v=Evaluate("="&[A1]):e=Int(Log(v)/2.3):?IIf(Instr([A1],"^"),v,v*10^-e &"*10^"&e)

''  Or

v=Evaluate("="&[A1]):e=Int(Log(v)/2.3):?IIf(Instr([A1],"^"),v,v/(10^e)&"*10^"&e)

''  Or

[B1]="="&[A1]:v=[B1]:e=Int(Log(v)/2.3):?IIf(Instr([A1],"^"),v,v*10^-e &"*10^"&e)

''  Or

[B1]="="&[A1]:e=[Int(Log10(B1))]:?IIf(Instr([A1],"^"),[B1],[B1]/(10^e)&"*10^"&e)

```
> 1 votes

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


title: Parse the Parcel

text:
# Question
Title: Parse the Parcel
Thanks to your help in the Mark My Mail challenge, PPCG-Post has successfully stamped all of its parcels with the generated barcodes!

Now, it's time to decode them.

In this challenge your program will, given a barcode generated from the Mark My Mail challenge, decode it and return the encoded integer.

But watch out! The barcode might be upside down...

---

## 4-state barcodes

In the case you missed the encoding challenge you'll need to know what kind of barcodes we're talking about. A 4-state barcode is a row of bars with four possible states, each representing a base-4 integer:

```
            |       |
Bar:    |   |   |   |
                |   |

Digit:  0   1   2   3

```

Rendered in ASCII, the barcodes will take up three lines of text, using the pipe (`|`) character to represent part of a bar, and a space () to represent an empty section. There will be a single space in between each bar. An example barcode may look like this:

```
|   | |   | | | |   |     |   |
| | | | | | | | | | | | | | | | |
    | |   |   | | |   |     |

```

To convert a barcode back to the integer it encodes, map each bar to its corresponding base-4 digit, concatenate these, and convert it to decimal.

As each barcode will also represent a different barcode when upside down, we implement a start/stop sequence so the orienation can be calculated. For the purpose of this challenge, we will be using the start/stop sequence specified by Australia Post: **each barcode begins and ends with a `1 0` sequence.**

---

# The Challenge

Your task is to, given an ASCII 4-state barcode, parse it and return the integer it encodes - essentially the reverse of Mark My Mail.

But to spice things up, there's a catch - **the barcode may be given upside down.** As in the real world, it will be left to the barcode reader (your program) to **determine the correct orientation** using the start/stop sequence.

### Example:

Given the following barcode:

```
    | |   |     |
| | | | | | | | | | |
  | |     |   |     |

```

We can clearly see that the first and last pairs of digits are `0, 2` and not `1, 0`. This means that the barcode is upside down - so we must **rotate it by 180 degrees** (not just flip each bar) to achieve the correct orientation:

```
|     |   |     | |
| | | | | | | | | | |
    |     |   | |

```

Now, we can begin the decoding. We map each bar to its corresponding base-4 digit, ignoring the start/stop sequences as they do not encode the data.

```
|     |   |     | |
| | | | | | | | | | |
    |     |   | |

- - 2 1 0 3 0 2 3 - -

```

We concatenate this to the base-4 integer `2103023`, then convert it to its decimal representation `9419` for the final result.

---

# Rules

* The input will always be a valid, 4-state barcode, rendered in ASCII as set out above, with the described start/stop sequence.
    + You may request trailing spaces, or stripped lines, as well as a trailing newline - whichever format suits your golfing.
    + It may or may not be in the correct orientation - your program must determine whether to read it upside down, by using the start/stop sequence.
    + It will not encode leading zero-digits in the base-4 integer.
* You may take the input as a list of lines, or a string with newlines.
* The output should be an integer in your language's standard integer base, representing the data that was encoded by the barcode.
* As postage stamps are small and can fit very little code on them, your code will need to be as short as possible: this is a - so the shortest program (in bytes) wins!

---

# Test Cases

```

| | | | | | | | | | |
  |             |   |

```

**= 4096** (flipped)

```
      | | | |     | | | |
| | | | | | | | | | | | | | | |
  | |   | |   | |   | |   |   |

```

**= 7313145** (flipped)

```
    | |   |     |
| | | | | | | | | | |
  | |     |   |     |

```

**= 9419** (flipped)

```
|   | | | |   |
| | | | | | | | |
    | |   | |

```

**= 990** (not flipped)

```
|   |       |   | |
| | | | | | | | | | |
    |       | |

```

**= 12345** (not flipped)

# Answer
> 6 votes
# Jelly, 18 bytes

```
>⁶m2Zm2UFUi¡1ṫ4Ḅ:⁴

```

Try it online!

# Answer
> 5 votes
# Husk, 16 bytes

```
ḋṁẊ=hhttĊ2T§▼↔m↔

```

Try it online!

Input is a list of lines (the TIO link uses a multiline string for clarity). The lines must have equal lengths, and there must not be extra trailing spaces.

## Explanation

```
ḋṁẊ=hhttĊ2T§▼↔m↔  Input is a list of strings x.
           §▼     Lexicographic minimum of
             ↔    x reversed and
              m↔  x with each line reversed.
          T       Transpose. Now we have a list of columns.
        Ċ2        Get every second column, removing the blank ones.
    hhtt          Remove first 2 and last 2 (the orientation markers).
 ṁ                Map and concatenate
  Ẋ=              equality of adjacent pairs.
                  This turns a column like "|| " into [1,0], and these pairs are concatenated.
ḋ                 Convert from binary to integer.

```

# Answer
> 4 votes
# SOGL V0.12, ~~40~~ 32 bytes

```
K@=«I⁷G@Κ¹;⌡I2n{j_{@≠}«+}¹jkjk4│

```

Try it Here!

# Answer
> 3 votes
# Python 2, ~~113~~ 105 bytes

```
lambda x:int(''.join([`2*(c>'#')+(a>'#')`for a,b,c in zip(*x[::1-2*(x[-1]>'#')].split('\n'))][4:-4:2]),4)

```

Try it online!

# Answer
> 2 votes
# Pip, ~~46~~ ~~43~~ 42 bytes

```
IsQ@@gg:RV*RVgY^gR'|1(J@UW2*y@2+@y)TM2FB:4

```

Takes the lines of the barcode as three command-line arguments. The first and third lines must be padded to the length of the second line with spaces. Try it online!

### Explanation

First some prepwork:

```
IsQ@@gg:RV*RVg Y^gR'|1

                        g is cmdline args; s is space (implicit)
IsQ                     If space equals
   @@g                  the first character of the first line, then:
           RVg           Reverse the order of the rows in g
        RV*              then reverse the characters in each row
      g:                 and assign the result back to g
                 gR'|1  In g, replace pipe character with 1
                ^       Split each row into a list of characters
               Y        Yank the result into y

```

Now observe that if we ignore the middle row and treat `|` as 1 and  as 0, each bar is just a 2-bit binary number:

```
(J@UW2*y@2+@y)TM2FB:4

       y@2             Third row
     2*                Multiply by 2, turning 1 into 2 and space into 0
           @y          First row
          +            Add
   UW                  Unweave: creates a list of two lists, the first containing all
                       even-indexed elements (in our case, the actual data), the second
                       containing all odd-indexed elements (the space separators)
  @                    First item of that list
 J                     Join the list of digits into a string
(            )TM2      Trim 2 characters from the beginning and end
                 FB:4  Convert from base 4 (: makes the precedence lower than TM)
                       Autoprint

```

# Answer
> 2 votes
# Python 2, 96 bytes

```
lambda a:int(`[2*(r==q)+(p==q)for p,q,r in zip(*a[::(a>'|')*2-1].split('\n'))[4:-4:2]]`[1::3],4)

```

Try it online!

# Answer
> 2 votes
# Retina, 71 bytes

```
(.).
$1
sO$^`^\|.*|.

^..|..¶.*¶..|..$
¶
\|
 |
+`\|
 ||||
.*¶$
$&$&
\|

```

Try it online! Link includes smaller test cases. Requires the first and last lines to be space-padded to the length of the middle line. Explanation:

```
(.).
$1

```

Delete the unnecessary spaces.

```
sO$^`^\|.*|.

```

Reverse the characters in the code, but if the bar code begins with a `|`, then select the entire code, otherwise split it in to characters. Then, reverse them. This flips the code if it begins with a `0`.

```
^..|..¶.*¶..|..$
¶

```

Delete the start/stop sequence and the middle row (which is of no use to us).

```
\|
 |
+`\|
 ||||

```

Convert the spaces and `|`s from base 4 to unary.

```
.*¶$
$&$&

```

Double the last line.

```
\|

```

Convert to decimal.

# Answer
> 2 votes
# Clean, ~~191~~ ... ~~161~~ 144 bytes

```
import StdEnv
?' '=0;?_=1
r=reverse
$a b|hd a<'|'= $(r b)(r a)=[?(b!!n)*2+ ?(a!!n)\\n<-[4,6..length b-4]]
@[a,_,b]=sum[d*4^p\\d<- $a b&p<-[0..]]

```

Try it online!

# Answer
> 2 votes
# Java 8, ~~208~~ ~~166~~ ~~157~~ 151 bytes

Trying it, probably can be better, reduced 42 due unnecessary checks, -9 removing variables, -6 thanks to Luke Stevens

Input is a `char[][3]`

```
(a)->{int i=2,c,s=0;c=(a[0][0]>32)?1:-1;for(;i<a.length-2;i++){s+=((a[i][1-c]>32?1:0)+(a[i][1+c]>32?2:0))*Math.pow(4,c==1?a.length-i-3:i-2);}return s;}

```

ungolfed:

```
int b(char[][] a) {
    int i=2,c,s=0;                      //i for looping, c to check if it's reversed, s is the sum, n the number
    c=(a[0][0]>32)?1:-1; //Check if must be reversed

    for(;i<a.length-2;i++){         //Looping elements

            //(Checking value for 1 + Checking value for 2) * Power, if reversed increasing, else decreasing
        s+=((a[i][1-c]>32?1:0)+(a[i][1+c]>32?2:0))*Math.pow(4,c==1?a.length-i-3:i-2);
    }
    return s;
}

```

# Answer
> 2 votes
# Java (OpenJDK 8), 181 160 bytes

Not too shabby for a java solution, I'm sure there are optimisations I can make, but I've already been staring at this for too long.

Cut down a few bytes by shortening the loop rather than using substring.

Golfed

```
c->{String r="";Integer i,j,l=c[0].length;for(i=4;i<l-4;i+=2){j=c[0][0]>32?i:l-1-i;r+=c[0][j]%8/4*(j==i?1:2)+c[2][j]%8/4*(j==i?2:1)+"";}return l.parseInt(r,4);}

```

Try it online!

Ungolfed

```
String r = "";
Integer i, j, l = c[0].length;
for(i=4; i<l-4; i+=2){
    j = c[0][0]>32 ? i : l-1-i;
    r += c[0][j]%8/4 * (j==i?1:2) + c[2][j]%8/4 * (j==i?2:1) + "";
}
return l.parseInt(r, 4);

```

# Answer
> 1 votes
# Husk, ~~39~~ 38 bytes

```
B4ththmȯ%4+3%5f≠192Ḟz+zṀ·*cN?↔m↔(='|←←

```

Takes input as a list of strings: Try it online or try the test-suite!

### Explanation

```
B4ththm(%4+3%5)f≠192Ḟz+zṀ·*cN?↔m↔(='|←←)
                             ?   (='|←←)  -- if the very first character == '|'
                              ↔           --   reverse the lines
                                          -- else
                               m↔         --   reverse each line
                       zṀ·*cN             -- zip the lines with [1,2,3..] under..
                        Ṁ·*c              --   convert each character to its codepoint and multiply by one of [1,2,3]
                    Ḟz+                   -- reduce the lines under zipWith(+) (this sums the columns)

               f≠192                      -- only keep elements ≠ 192 (gets rid of the separating lines)

-- for the example from the challenge we would now have:
--   [652,376,468,652,376,744,376,468,744,652,376]

      m(      )                           -- map the following function
        %4+3%5                            --   λx . ((x % 5) + 3) % 4
-- this gives us: [1,0,2,1,0,3,0,2,3,1,0]
    th                                    -- remove first & last element
  th                                      -- remove first & last element
B4                                        -- interpret as base4 number

```

# Answer
> 1 votes
# Perl 5, 152 + 2 (`-F`) bytes

```
push@a,[@F]}{for$i(0..$#{$a[1]}){$_.=($a[0][$i]eq'|')+2*($a[2][$i]eq'|')}$_=reverse y/12/21/r if/^0/;s/^0*1000|10*$//g;s/.\K0//g;$\=$_+$\*4for/./g;say$\

```

Try it online!

# Answer
> 0 votes
# Octave, ~~80~~ ~~75~~ 68 bytes

```
@(b)bi2de({rot90(t=~~(b-32)([3,1],[1:2:end]),2),t}{2-t(2)}(5:end-4))

```

Try it online!

Curiously, `bi2de` is default MSB on the right rather than the left, leading to some headaches while I made this... I think I should have the optimal way of flipping the array before indexing it, but there are *extremely* many ways to do it (either in the first indexing, or with `flipud`, `fliplr`, `rot90`, `'` (transpose), the final indexing...). Takes a rectangular array with spaces and `|`s (so, trailing spaces required)

```
@(b)                    % Define anonymous function taking input b

t=                      % Inline-define t,
~~(b-32)                % which is the input, converted to 1's and 0's,
([3 1],[1:2:end])       % but only keep the relevant rows (1 and 3 flipped vertically) and columns (only odd)

{rot90(t,2),t}          % Flip 180 degrees
{2-t(2)                 % depending on whether the second element of t is 1 or 0.}

(5:end-4)               % Flatten array, discarding control bits
bi2de( ... )            % and convert from binary to decimal,

```

# Answer
> 0 votes
# JavaScript (ES6), ~~184~~ 181 bytes

I'm not an experienced golfer - I'm sure this can be improved, but I loved this challenge! I've always wondered about those marks.

Function `f` takes a list of strings with required trailing spaces. Newlines added to the code below for clarity (not included in byte count).

```
f=t=>((o=[[...t[0]],[...t[2]]])[0][0]=='|'?o:(z=a=>a.reverse())(o.map(z)))
.map((a,r)=>a.filter((_,i)=>~i%2).map(e=>(1+r)*(e=='|')).slice(2,-2))
.reduce((a,b)=>a+parseInt(b.join``,4),0)

```

## Usage

```
t=['                     ','| | | | | | | | | | |','  |             |   |']
console.log(f(t)) // 4096

```

## Ungolfed version with explanation

```
// take list of strings, t, as input:
f = t => (

  // create output variable o, discard middle row, turn other rows into lists:
  ( o = [ [...t[0]], [...t[2]] ] )

  // if top-left position isn't a pipe, rotate 180 degrees.
  // Alias [].reverse to save 3 bytes :D
  [0][0] == '|' ? o : ( z = a=> a.reverse() )( o.map(z) )

).map( (a,r) =>

  // remove even-numbered positions (non-encoding spaces):
  a.filter( (_,i) => ~i%2 )

  // convert non-pipes into zeros, and pipes into 1 or 2;
  // top row becomes the base4 1-component, bottom row is 2:
  .map( e => (1+r) * (e=='|') ).slice(2,-2)

// convert rows to base4 component strings, then decimal, then sum them:
).reduce( (a,b) => a + parseInt(b.join``,4),0)

```

---
Tags: code-golf, string, ascii-art, parsing, base-conversion
---


title: The Missing Number - Version 2

text:
# Question
Title: The Missing Number - Version 2
**Background:**

This question is a remix of the one that I made previously on this forum. The only difference with this one is: the range is significantly larger, AND dynamic. Details below!

Also, I'm typing this question incredibly quickly, so if there are any grammatical errors, I do apologize and ask if anyone would edit the question to clear any vagueness. Nonetheless, the original question is posted here: The Missing Number Revised

**Question:**

Given a minimum bound M, a maximum bound N, and a String of randomly concatenated integers \[min, max), min (M) to max (N) exclusive, there is a number missing in the sequence. Your job is to write a program that will calculate this missing number.

Doing this problem by hand on smaller Strings, such as examples 1 and 2 below are obviously very easy. Conversely, computing a missing number on incredibly large datasets involving three-digit, four-digit, or more numbers would be incredibly difficult. The idea behind this problem is to construct a program that will do this process FOR you.

**Important Information:**

One thing that appeared as rather confusing when I posted this problem last night was: what exactly a missing number is defined as. A missing number is the number INSIDE of the range specified above; NOT necessarily the digit. In example 3, you will see that the missing number is 7, even though it appears in the sequence. There are 3 places the DIGIT 7 will appear in a series of \[0, 30): “7”, “17”, and “27”. Your objective is to differentiate between these, and discover that 7 is the missing NUMBER (inside of example 3). In other words, the tricky part lies in finding out which sequences of digits are complete and which belong to other numbers.

Another very important factor in this: there are some input situations where there are *multiple solutions*! Your job will be to print out ALL numbers that are missing in the sequence. I cannot provide insight as to WHY they have multiple solutions; I only know they may exist.

**Input:**

The input is a single Integer T: the amount of test cases.

For each test case, there is an Integer M: the minimum number in the sequence, another Integer N: the maximum number in the sequence (thus M \< N at ALL times), a String S, containing integers from M to N - 1 inclusive, or M to N exclusive (in other words, \[M, N)). These integers, as stated above, are scrambled up to create a random sequence. There are NO delimiters (“42, 31, 23, 44”), or padding 0’s (003076244029002); the problems are exactly as described in the examples.

As stated above, M is ALWAYS lower than N, and the maximum range of numbers is \< 100,000. |N - M|.

**Winning Criteria:**

Whoever has the fastest, and lowest memory usage will be the winner. In the miraculous event that a time ties, lower memory will be used for the time breaker. Please list Big O if you can!

**Examples:**

(Examples 1-6 are just for demonstration. Your program needn't to handle them.)

Here is a pastebin link of the examples.

**TEST DATA**

Please keep in mind the way you're to read in the data: Digit D represents how MANY test cases there are, the next lines will follow with integers M and N, then String S. I just wanted to clear it up. I also apologize for the incredibly large pastebin. Good luck!

Data: Test Data - Github repository

# Answer
# Clean - Complexity Unknown

*Currently works, explanation and further optimization in progress*

```
module main
import StdEnv, StdLib, System.IO

:: Position :== [Int]
:: Positions :== [Position]
:: Digit :== (Char, Int)
:: Digits :== [Digit]
:: Number :== ([Char], Positions)
:: Numbers :== [Number]
:: Complete :== (Numbers, Positions)

decouple =: snd o unzip

//lcouple :: (.a -> .b) (.a, .c) -> (.b, .c)
lcouple fn (arg, oth) :== (fn arg, oth)

getCases :: Int *World -> ([(String, [[Char]])], *World)
getCases n world
    # (range, world)
        = evalIO getLine world
    # range
        = fromString range
    # spacePos
        = elemIndex ' ' range
    | isNothing spacePos
        = abort "invalid input, expected space in range\n"
    # (a, b)
        = splitAt (fromJust spacePos) range
    # (a, b)
        = (toInt (toString a), toInt (toString (tl b)))
    # numbers
        = [(fromString o toString) number \\ number <- [a..(b-1)]]
    # (string, world)
        = evalIO getLine world
    | n > 1
        # (cases, world)
            = getCases (n - 1) world
        = ([(string, numbers) : cases], world)
    = ([(string, numbers)], world)

singletonSieve :: Complete -> Complete
singletonSieve (list, sequence)
    | sequence_ == sequence
        = reverseSieve (list, sequence)
    = (list_, sequence_)
where
    singles :: Positions
    singles
        = [hd pos \\ (_, pos) <- list | length pos == 1]
    list_ :: Numbers
    list_
        = map (app2 (id, filter notInOtherSingle)) list
    where
        notInOtherSingle :: Position -> Bool
        notInOtherSingle pos
            = not (isAnyMember pos (flatten (filter ((<>) pos) singles)))
    sequence_ :: Positions
    sequence_
        = foldr splitSequence sequence singles

reverseSieve :: Complete -> Complete
reverseSieve (list, sequence)
    | sequence_ == sequence
        = (list, sequence)
    = (list_, sequence_)
where
    singles :: Positions
    singles
        = [hd pos \\ pos <- [[subSeq \\ subSeq <- sequence | isMember subSeq p] \\ (_, p) <- list] | length pos == 1]
        //= [hd pos \\ pos <- | length pos == 1]
    list_ :: Numbers
    list_
        = map (app2 (id, filter (\b_ = (notInOtherSingle b_) && (hasContiguousRun b_)))) list
    where
        notInOtherSingle :: Position -> Bool
        notInOtherSingle pos
            = not (isAnyMember pos (flatten (filter ((<>) pos) singles)))
        hasContiguousRun :: Position -> Bool
        hasContiguousRun pos
            //= any (any (isPrefixOf pos) o tails) sequence_
            = and [isMember p (flatten sequence_) \\ p <- pos]

    sequence_ :: Positions
    sequence_
        = foldr splitSequence sequence singles

splitSequence :: Position Positions -> Positions
splitSequence split sequence
    = flatten (map newSplit (map (span (not o ((flip isMember) split))) sequence))
where
    newSplit :: (Position, Position) -> Positions
    newSplit ([], b)
        # b
            = drop (length split) b
        | b > []
            = [b]
        = []
    newSplit (a, b)
        # b
            = drop (length split) b
        | b > []
            = [a, b]
        = [a]

indexSubSeq :: [Char] Digits -> Positions
indexSubSeq _ []
    = []
indexSubSeq a b
    # remainder
        = indexSubSeq a (tl b)
    | isPrefixOf a (map fst b)
        = [[i \\ (_, i) <- take (length a) b] : remainder]
        //= [[i \\ _ <- a & (_, i) <- b] : remainder]
    = remainder

missingNumber :: String [[Char]] -> [[Char]]
missingNumber string numbers
    # string
        = [(c, i) \\ c <-: string & i <- [0..]]
    # locations
        = [(number, indexSubSeq number string) \\ number <- numbers]
    # digits
        = [length (indexSubSeq [digit] [(c, i) \\ c <- (flatten numbers) & i <- [0..]]) \\ digit <-: "0123456789-"]
    # missing
        = flatten [repeatn (n - length i) c \\ n <- digits & (c, i) <- [(digit, indexSubSeq [digit] string) \\ digit <-: "0123456789-"]]
    # (answers, _)
        = until (\e = e == singletonSieve e || length [(a, b) \\ (a, b) <- fst e | length b == 0 && isMember a (candidates missing)] > 0) singletonSieve (locations, [indexList string])
    # answers
        = filter (\(_, i) = length i == 0) answers
    = filter ((flip isMember)(candidates missing)) ((fst o unzip) answers)
where
    candidates :: [Char] -> [[Char]]
    candidates chars
        = moreCandidates chars []
    where
        moreCandidates :: [Char] [[Char]] -> [[Char]]
        moreCandidates [] nums
            = removeDup (filter (\num = isMember num numbers) nums)
        moreCandidates chars []
            = flatten [moreCandidates (removeAt i chars) [[c]] \\ c <- chars & i <- [0..]]
        moreCandidates chars nums
            = flatten [flatten [moreCandidates (removeAt i chars) [ [c : num] \\ num <- nums ]] \\  c <- chars & i <- [0..]]

Start world
    # (number, world)
        = evalIO getLine world
    # (cases, world)
        = getCases (toInt number) world
    =  flatlines[flatten(intersperse [', '] (missingNumber string numbers)) \\ (string, numbers) <- cases]

```

Try it online!
> 2 votes

# Answer
# C++: A naive brute-force solution

Try to split the string in any possible way where all number are within the range and do not repeat. If there is only one number missing, add it to the set of answers.

While I tried to optimise the code, I did not put any heuristics or optimisations to the algorithm. The solution is so slow, that it can only handle the 1st and the 3rd test case. It can be used as a baseline when comparing "speed" and to show how a better algorithm implemented in a slower language can beat a worse solution in a faster language.

```
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

class missing_number_solver
{
	static constexpr int max_digit_len = 6;

	long int n, m;
	std::vector<long int> digits;

	std::vector<long int> used;
	long int used_count = 0;

	std::set<long int> results;

	void f(size_t pos)
	{
		if (pos == digits.size())
		{
			if (used_count == m - n - 1)
			{
				auto idx = std::find(used.begin(), used.end(), false) - used.begin();
				results.insert(n + idx);
			}
			return;
		}

		bool negate = false;
		if (digits[pos] < 0)
		{
			negate = true;
			pos++;
		}

		long int acc = 0;
		for (int i = 0; i < max_digit_len && pos + i < digits.size(); i++)
		{
			if (digits[pos + i] < 0)
			{
				// Minus sign. Stop.
				break;
			}

			acc = 10 * acc + digits[pos + i];
			auto number = negate ? -acc : acc;

			if (number < n || number >= m)
			{
				continue;
			}
			if (used[number - n])
			{
				continue;
			}

			used[number - n] = true;
			used_count++;

			f(pos + i + 1);

			used[number - n] = false;
			used_count--;

			if (i == 0 && digits[pos] == 0)
			{
				// Leading zero. Do not consume more digits.
				break;
			}
		}
	}

public:
	missing_number_solver(long int n, long int m, std::string str) :
			n(n), m(m)
	{
		for (char c : str)
		{
			digits.push_back(c == '-' ? -1 : c - '0');
		}
	}

	std::set<long int> solve()
	{
		used = std::vector<long int>(m - n, false);
		f(0);
		return results;
	}
};

int main()
{
	int t;

	std::cin >> t;

	for (int i = 0; i < t; i++)
	{
		long int n, m;
		std::string s;

		std::cin >> n >> m;
		std::cin >> s;

		auto results = missing_number_solver(n, m, s).solve();

		for (auto result : results)
		{
			std::cout << result << ' ';
		}
		std::cout << std::endl;
	}
}

```

Try it online!

In addition, this is how a test case with multiple solutions looks like:

```
1 22
1212345678910111314151617181920

```

As I understand, the output should be:

```
12 21

```

as the original sequence must be one of:

```
[1, 2, 12, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20] # missing 21
[1, 21, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20] # missing 12
[12, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20] # missing 21

```
> 0 votes

# Answer
# JavaScript (ES6)

Quite slow, but I think it can solve the test cases. Not all test cases present at the moment, I'll try to put all of them later.

```
Time=fun=>{
  var t0 = performance.now(), t1=t0, t2
  console.log(fun(msg=>console.log(msg, (t2=t1,t1=performance.now(),t1-t2))))
  var t = performance.now()-t0
  return t<1e3 ? t+' ms':t/1000+' sec'
}

function Missing(str, ll,hl)
{
  var can, seq, num, i1, i2, s1, s2

  var rec = span =>
  {
    var num
    if (!seq[span]) return 1
    if (seq[span] == '_') ++span
    if (seq[span] == '-')
    {
      ++span
      num = -seq[span++]
      while (num < hl && num >= ll)
      {
        if (!values[num])
        {
          values[num] = 1
          if (rec(span)) return 1
          values[num] = 0
        }
        if (!num) return;
        if (seq[span] == '_' || seq[span] == '-') return;
        num = -seq[span++] +num*10
      }
    }
    else
    {
      num = +seq[span++]

      while (num < hl && num >= ll)
      {
        if (!values[num])
        {
          values[num] = 1
          if (rec(span)) return 1
          values[num] = 0
        }
        if (!num) return;
        if (seq[span] == '_' || seq[span] == '-') return;
        num = +seq[span++] +num*10
      }
    }
  }

  find=num=>{
    var i1,i2
    if (num < 0)
    {
      i1 = seq.indexOf(num)
      if (i1<0) return i1
      i2 = seq.lastIndexOf(num)
      return i2 == i1 ? i1 : -1;
    }
    else
    {
      // take care of false positives when there is a '-' before the number
      // so much slower respect to the other branch
      var rx = new RegExp('[^-]'+num)
      i1 = (' '+seq).search(rx)
      if (i1 < 0) return i1
      i2 = seq.slice(i1).search(rx)
      return i2 < 0 ? i1 : -1;
    }
  }

  for (can = ll; can < hl; ++can)
  {
    if (str.indexOf(can) < 0) return can;
    values = {}
    values[can] = 1
    seq = str
    for (num = ll; num < hl; ++num)
    {
      if (!values[num])
      {
        i1 = find(num)
        if (i1 >= 0)
        {
          i2 = i1+(''+num).length
          if (seq[i1-1] == '_') --i1;
          if (seq[i2] == '_') ++i2;
          s1 = seq.slice(0,i1), s2 = seq.slice(i2)
          seq = s1 ? s2 ? s1+'_'+s2 : s1 : s2
          values[num] = 1
          num = ll-1
        }
      }
    }
    // console.log('REC',can,seq)
    if (rec(0)) return can
  }

}

Test = [["229272120623131992528240518810426223161211471711",0,30],
["11395591741893085201244471432361149120556162127165124233106210135320813701207315110246262072142253419410247129611737243218190203156364518617019864222241772384813041175126193134141008211877147192451101968789181153241861671712710899168232150138131195104411520078178584419739178522066640145139388863199146248518022492149187962968112157173132551631441367921221229161208324623423922615218321511111211121975723721911614865611197515810239015418422813742128176166949324015823124214033541416719143625021276351260183210916421672722015510117218224913320919223553222021036912321791591225112512304920418584216981883128105227213107223142169741601798025",0,250],
["1342319526198176611201701741948297621621214122224383105148103846820718319098731271611601912137231471099223812820157162671720663139410066179891663131117186249133125172622813593129302325881203242806043154161082051916986441859042111711241041590221248711516546521992257224020174102234138991752117924457143653945184113781031116471120421331506424717816813220023315511422019520918114070163152106248236222396919620277541101222101232171732231122301511263822375920856142187182152451585137352921848164219492411071228936130762461191564196185114910118922611881888513917712153146227193235347537229322521516718014542248813617191531972142714505519240144",0,250],
["80901062173445953196186301456692487427529429993285787069831233591227347952858217788973393434655233831877642815971961376506739541125150847218402660459824663618793744638964202557497582411568",0,100],
["1302797101187197126231292239133232171515415180252611104191857114450179111134201662662932221381232833721819553193151235255288382951611921896841051718124164119345781124629128526219276169113296142414667176120182159236229724224516532275167119911243329243153024688191841282382655120729228164986223079108216327276103148145142108302692092566328429021116692173174253143279251205351277329821214010060691392141981836583611522942572022622786840551472342675428024419426414125827112277297170168186160110274722278115694901142861021820190220247252137158289448121233277249250155149270135481781852131754322187701628221622313210925442210224106118208268228260259299563117313621524812441579558157591322615020323724028718891772125199273808916247116862811074974204225999613626323152211312397519621734172206200",0,300],
["201-1382843613319717171212-193-175-591897023633-61234-11828-6108969023295-104-18916914-36-893-23126175-85-9611811654113-158-198208-250126-95143166-65160215-70-44-202-194158-16324475-2011514516537-90-358511742-211-97-139162219-29221-18135-12-60-22516-222-312288-217-102137-2092095274-190-87249-105-249157-6916430-116-15360225100-178-218-129-141248-111-224220224159237-128-137-79-38-18798-51-238-173-203109532429200223625180188-226112-142216-242150-1231038-228-887379154-210101130-5323115199-15623180-20710425-245-186-147102-247240233194168-112228148592144964-149-100-52193129152-34-1134043128123-172110-6363144-21922746-151-174-140-19299-206161-12268141-214-805067206-46-5195-237-5813-40-130-170122-229-16558213-184-47174-161190-13487115-115-23-235-143-201078382222-57-67205-18-81-427278-179-11-162-244-86-83-8421-11927-120204-71-50138-136-1991359165-126173-76448-62206229-99179-164-110-220-146-17697-22376146-49184-236-37-91-43-419671127-54-23269-480-451313817023821721015322617613-3224286-182186-144-233-216-24016313977-98-230192155-101182183-14889-19714018581-166-114-1502189-27-212-17-92121-1-23918732-132-215-205-21-33-15961-1275-15-196-39-56-154-243-6820256-89191239145-191178-55-208-9347-16-41-221-152-2839-18310-241-117-169-75-103-73-16716744241-248125-64119-30120-94-177-234-195-13-21324734198-14571569255-26149-107-13111-121-125-171-77-204-157-25-168-66127-19-200172-78105147-7213212466177-155-135-185-24-109181230-227-7424619-106142111-246-22074111494-7-160-9106-10-133-18024531-145211-124-3-188-82136-22235-10818203134",-250,250],
["-615-631-765-659-699-748-714-554-451-569-898-462-676-721-459-578-522-493-668-686-728-603-455-587-815-537-492-639-842-485-747-832-768-899-471-900-893-598-626-757-682-501-620-614-549-770-824-527-539-755-596-452-821-591-572-857-895-776-836-503-773-590-575-568-633-737-702-514-510-724-592-739-790-846-732-536-579-775-479-688-687-740-794-650-637-636-518-791-611-473-497-675-758-697-548-655-559-534-736-677-860-543-733-723-805-831-670-608-883-502-600-583-467-867-613-612-621-861-731-866-793-460-798-505-595-771-769-486-718-570-813-749-685-496-630-819-886-785-870-807-516-744-680-653-719-859-717-681-880-476-674-582-667-489-865-876-695-495-703-841-707-711-777-760-848-837-517-532-784-465-693-894-520-678-862-818-487-743-782-597-477-562-519-586-839-700-538-710-566-746-565-546-466-456-811-599-822-772-602-480-810-494-751-550-640-665-508-809-581-840-560-863-526-454-725-683-632-660-729-594-457-753-759-816-609-706-800-891-877-617-628-715-651-833-547-558-817-734-698-735-647-762-589-855-541-774-792-875-838-574-652-864-482-673-619-799-780-851-783-666-644-742-812-872-641-622-662-535-814-803-856-720-722-498-826-500-524-858-897-512-490-610-808-529-694-528-506-804-701-761-561-679-634-834-738-545-712-605-623-878-588-882-513-461-828-624-509-854-616-823-458-472-705-488-767-556-523-533-779-829-654-849-464-830-499-763-504-585-580-852-730-474-657-557-692-727-801-825-844-542-661-892-820-656-704-835-563-672-690-709-750-689-766-604-553-551-868-577-726-478-663-642-752-463-745-716-483-481-696-671-869-625-618-564-881-648-573-691-606-786-843-788-827-797-888-795-874-584-796-787-778-806-847-593-507-764-879-635-889-521-887-511-713-884-754-873-470-601-646-552-530-845-525-567-627-491-629-669-741-469-484-571-853-850-453-576-708-871-789-885-658-664-643-802-515-684-540-555-896-756-607-638-645-531-468-475-649-781-890",-900, -450],
["183205152228238-164156229248-187-189-207-112-128134-245231568-246-4760213-7266-1961240-141199233138-226-12421763-159125-208239-195225146-51-45105-24794-126-165-37-1456-40143109-75-222-116-70165110-214-11151-127-17411923779-864-720-2031573215875-65190-27187191878218613723286-218176-34-90-123182-153-38218-7618-173-205227198-25010710624430148-25-198-14824778-239-215597-21749206-121-1681627711456-35-101-18201-235-88-19124171200-194-78-125-138127216168-248174128153181-41299117811-146-171212850-20615021-1301189-69-152-117-23422367-43-6823-23273140-231195-220-44-197-211-64219121185-134-96-2217076-58-107-80222117-14-119-111111-102-7735197169-99-1324817326-163-223113-240-190-7917513957-154-103-66101126-298149145-1764351-28-2291372-135-202-118-175188-42-161975216153-109210172-862202653992132-85-1-1391099-738962-56103-180-97154-131-249-105-93-53-5550-89160-160204-104-114-3946-6374-170-17-18520398-59-36-177-94-238-2345-219177-243-15755-82-20115-149108-200-31-71135220234142844104-1934061-32236-166-6081-137-156180-1675436-182-9270179192-221-20180-120124-2372237-8716243-147-1692731-21-224-83-136-67-199214-49-241235224-212-233-16-210226167195833171-84245-11341-614488-19213014-10619612316312-74211-129133-10813169-155-41-144-133-183-98193-213-57958325-12164-24-230-54-50-142-244-30141249-122-2155-204215-942152990-91194-95100-11017-5-1812893-186-1396-242-140-179-188-236-151-228-216-2093-3147-11511224-48-62207-162-15024634-26-15813647120116208-100-19209242221-178-15-184-33-81159230-172-227-52-61184-225-461024418938122166-143",-250,250],
]

function go() {
  var t, i = 0;
  var Solve = _ => {
    var [s,a,b] = Test[i++]
    console.log(a,b,s)
    setTimeout(_=> {
      t = Time(_ => Missing(s,a,b));
      console.log('Solved in',t);
      if (Test[i]) setTimeout(Solve, 100);
    }, 100)
  }
  setTimeout(Solve, 100)
}
```

```
<button onclick="go()" >Test</button>Expect a total time of less than 3 minutes for all test cases in chrome
```
> 0 votes

---
Tags: string, number, sequence, parsing, fastest-code
---


title: Eigenvalues of a Matrix

text:
# Question
Title: Eigenvalues of a Matrix
Given a square matrix, output the matrix's eigenvalues. Each eigenvalue should be repeated a number of times equal to its algebraic multiplicity.

The eigenvalues of a matrix `A` are scalar values `λ` such that, for some column vector `v`, `A*v = λ*v`. They are also the solutions to the characteristic polynomial of `A`: `det(A - λ*I) = 0` (where `I` is the identity matrix with the same dimensions as `A`).

Outputs must be accurate to 3 significant digits. All inputs and outputs will be within the representable range of numerical values for your chosen language.

Builtins are acceptable, but you are encouraged to include solutions that do not use builtins.

## Test Cases

In these test cases, `I` represents the imaginary unit. Complex numbers are written in the form `a + b*I`. All outputs have 3 significant digits of precision.

```
[[42.0]] -> [42.0]
[[1.0, 0.0], [0.0, 1.0]] -> [1.00, 1.00]
[[1.0, 2.0, 3.0], [4.0, 5.0, 6.0], [7.0, 8.0, 9.0]] -> [16.1, -1.12, -1.24e-15]
[[1.2, 3.4, 5.6, 7.8], [6.3, 0.9, -5.4, -2.3], [-12.0, -9.7, 7.3, 5.9], [-2.5, 7.9, 5.3, 4.4]] -> [7.20 + 5.54*I, 7.20 - 5.54*I, -4.35, 3.75]
[[-3.22 - 9.07*I, 0.193 + 9.11*I, 5.59 + 1.33*I, -3.0 - 6.51*I, -3.73 - 6.42*I], [8.49 - 3.46*I, -1.12 + 6.39*I, -8.25 - 0.455*I, 9.37 - 6.43*I, -6.82 + 8.34*I], [-5.26 + 8.07*I, -6.68 + 3.72*I, -3.21 - 5.63*I, 9.31 + 3.86*I, 4.11 - 8.82*I], [-1.24 + 9.04*I, 8.87 - 0.0352*I, 8.35 + 4.5*I, -9.62 - 2.21*I, 1.76 - 5.72*I], [7.0 - 4.79*I, 9.3 - 2.31*I, -2.41 - 7.3*I, -7.77 - 6.85*I, -9.32 + 2.71*I]] -> [5.18 + 16.7*I, -24.9 - 2.01*I, -5.59 - 13.8*I, 0.0438 - 10.6*I, -1.26 + 1.82*I]
[[-30.6 - 73.3*I, 1.03 - 15.6*I, -83.4 + 72.5*I, 24.1 + 69.6*I, 52.3 + 2.68*I, 23.8 + 98.0*I, 96.8 + 49.7*I, -26.2 - 5.87*I, -52.4 + 98.2*I, 78.1 + 6.69*I], [-59.7 - 66.9*I, -26.3 + 65.0*I, 5.71 + 4.75*I, 91.9 + 82.5*I, -94.6 + 51.8*I, 61.7 + 82.3*I, 54.8 - 27.8*I, 45.7 + 59.2*I, -28.3 + 78.1*I, -59.9 - 54.5*I], [-36.0 + 22.9*I, -51.7 + 10.8*I, -46.6 - 88.0*I, -52.8 - 32.0*I, -75.7 - 23.4*I, 96.2 - 71.2*I, -15.3 - 32.7*I, 26.9 + 6.31*I, -59.2 + 25.8*I, -0.836 - 98.3*I], [-65.2 - 90.6*I, 65.6 - 24.1*I, 72.5 + 33.9*I, 1.47 - 93.8*I, -0.143 + 39.0*I, -3.71 - 30.1*I, 60.1 - 42.4*I, 55.6 + 5.65*I, 48.2 - 53.0*I, -3.9 - 33.0*I], [7.04 + 0.0326*I, -12.8 - 50.4*I, 70.1 - 30.3*I, 42.7 - 76.3*I, -3.24 - 64.1*I, 97.3 + 66.8*I, -11.0 + 16.5*I, -40.6 - 90.7*I, 71.5 - 26.2*I, 83.1 - 49.4*I], [-59.5 + 8.08*I, 74.6 + 29.1*I, -65.8 + 26.3*I, -76.7 - 83.2*I, 26.2 + 99.0*I, -54.8 + 33.3*I, 2.79 - 16.6*I, -85.2 - 3.64*I, 98.4 - 12.4*I, -27.6 - 62.3*I], [82.6 - 95.3*I, 55.8 - 73.6*I, -49.9 + 42.1*I, 53.4 + 16.5*I, 80.2 - 43.6*I, -43.3 - 3.9*I, -2.26 - 58.3*I, -19.9 + 98.1*I, 47.2 + 62.4*I, -63.3 - 54.0*I], [-88.7 + 57.7*I, 55.6 + 70.9*I, 84.1 - 52.8*I, 71.3 - 29.8*I, -3.74 - 19.6*I, 29.7 + 1.18*I, -70.6 - 10.5*I, 37.6 + 99.9*I, 87.0 + 19.0*I, -26.1 - 82.0*I], [69.5 - 47.1*I, 11.3 - 59.0*I, -84.3 - 35.1*I, -3.61 - 35.7*I, 88.0 + 88.1*I, -47.5 + 0.956*I, 14.1 + 89.8*I, 51.3 + 0.14*I, -78.5 - 66.5*I, 2.12 - 53.2*I], [0.599 - 71.2*I, 21.7 + 10.8*I, 19.9 - 97.1*I, 20.5 + 37.4*I, 24.7 + 40.6*I, -82.7 - 29.1*I, 77.9 + 12.5*I, 94.1 - 87.4*I, 78.6 - 89.6*I, 82.6 - 69.6*I]] -> [262. - 180.*I, 179. + 117.*I, 10.3 + 214.*I, 102. - 145.*I, -36.5 + 97.7*I, -82.2 + 89.8*I, -241. - 104.*I, -119. - 26.0*I, -140. - 218.*I, -56.0 - 160.*I]

```

# Answer
# Haskell, ~~576 554 532~~ 507 bytes

No built-ins!

```
import Data.Complex
s=sum
l=length
m=magnitude
i=fromIntegral
(&)=zip
t=zipWith
(x!a)b=x*a+b
a#b=[[s$t(*)x y|y<-foldr(t(:))([]<$b)b]|x<-a]
f a|let c=[1..l a];g(u,d)k|m<-[t(+)a b|(a,b)<-a#u&[[s[d|x==y]|y<-c]|x<-c]]=(m,-s[s[b|(n,b)<-c&a,n==m]|(a,m)<-a#m&c]/i k)=snd<$>scanl g(0<$c<$c,1)c
p?x|let f=foldl1(x!);c=l p-1;n=i c;q p=init$t(*)p$i<$>[c,c-1..];o=f(q p)/f p;a|d<-sqrt$(n-1)*(n*(o^2-f(q$q p)/f p)-o^2)=n/last(o-d:[o+d|m(o-d)<m(o+d)])=last$p?(x-a):[x|m a<1e-9]
z[a,b]=[-b/a]
z p=p?0:z(init$scanl1(p?0!)p)

```

Try it online!

Many thanks @ØrjanJohansen for a total of -47 bytes!

### Explanation

First this computes the characteristic polynomial with the Faddeev–LeVerrier algorithm which is the function `f`. Then the function `z` computes all roots of that polynomial by iterating `g` which implements Laguerre's Method for finding a root, once a root is found it is removed and `g` gets called again until the polynomial has degree 1 which is trivially solved by `z[a,b]=[-b/a]`.

### Ungolfed

I re-inlined the functions `sum`,`length`,`magnitude`, `fromIntegral`, `zipWith` and `(&)` as well as the little helper `(!)`. The function `faddeevLeVerrier` corresponds to `f`, `roots` to `z` and `g` to `laguerre` respectively.

```
-- Transpose a matrix/list
transpose a = foldr (zipWith(:)) (replicate (length a) []) a

-- Straight forward implementation for matrix-matrix multiplication
(#) :: [[Complex Double]] -> [[Complex Double]] -> [[Complex Double]]
a # b = [[sum $ zipWith (*) x y | y <- transpose b]|x<-a]

-- Faddeev-LeVerrier algorithm
faddeevLeVerrier :: [[Complex Double]] -> [Complex Double]
faddeevLeVerrier a = snd <$> scanl go (zero,1) [1..n]
  where n = length a
        zero = replicate n (replicate n 0)
        trace m = sum [sum [b|(n,b)<-zip [1..n] a,n==m]|(m,a)<-zip [1..n] m]
        diag d = [[sum[d|x==y]|y<-[1..n]]|x<-[1..n]]
        add as bs = [[x+y | (x,y) <- zip a b] | (b,a) <- zip as bs]
        go (u,d) k = (m, -trace (a#m) / fromIntegral k)
          where m = add (diag d) (a#u)

-- Compute roots by succesively removing newly computed roots
roots :: [Complex Double] -> [Complex Double]
roots [a,b] = [-b/a]
roots   p   = root : roots (removeRoot p)
  where root = laguerre p 0
        removeRoot = init . scanl1 (\a b -> root*a + b)

-- Compute a root of a polynomial p with an initial guess x
laguerre :: [Complex Double] -> Complex Double -> Complex Double
laguerre p x = if magnitude a < 1e-9 then x else laguerre p new_x
  where evaluate = foldl1 (\a b -> x*a+b)
        order' = length p - 1
        order  = fromIntegral $ length p - 1
        derivative p = init $ zipWith (*) p $ map fromIntegral [order',order'-1..]
        g  = evaluate (derivative p) / evaluate p
        h  = (g ** 2 - evaluate (derivative (derivative p)) / evaluate p)
        d  = sqrt $ (order-1) * (order*h - g**2)
        ga = g - d
        gb = g + d
        s = if magnitude ga < magnitude gb then gb else ga
        a = order /s
        new_x = x - a

```
> 14 votes

# Answer
# Octave, 4 bytes

```
@eig

```

Try it online!

Only two bytes more than the MATL golfing language equivalent!

Defines an anonymous function handle to the `eig` built-in. Interestingly, the MATLAB design philosophy goes against many high-end languages, which like to use `DescripteFunctionNamesTakingArguments()`, whereas MATLAB and consequently Octave tend to get the shortest unambiguous function name possible. For example, to get a **s**ubset of eigenvalues (e.g., the smallest `n` in absolute magnitude), you use `eigs`.

As a bonus, here's a function (works in MATLAB, and in theory could work in Octave but their `solve` is not really up to the task) that doesn't use built-ins, but instead symbolically solves the eigenvalue problem, `det(A-λI)=0`, and converts it to numerical form using `vpa`

```
@(A)vpa(solve(det(A-sym('l')*eye(size(A)))))

```
> 5 votes

# Answer
# MATL, 2 bytes

```
Yv

```

Try it online!

### Explanation

I followed the usual advice in numerical linear algebra: instead of writing your own function, use a built-in that is specifically designed to avoid numerical instabilities.

Incidentally, it's shorter. ¯\\\_(ツ)\_/¯
> 3 votes

# Answer
# Mathematica, 11 bytes

```
Eigenvalues

```

Try it online!
> 1 votes

# Answer
# , 22 bytes

```
function(m)eigen(m)$va

```

Try it online!

Takes `m` as a matrix. Frustratingly, the `eigen` function in R returns an object of class `eigen`, which has two fields: `values`, the eigenvalues, and `vectors`, the eigenvectors.

However, more annoyingly, the optional argument `only.values` returns a `list` with two fields, `values`, containing the eigenvalues, and `vectors`, set to `NULL`, but since `eigen(m,,T)` is also 22 bytes, it's a wash.
> 1 votes

# Answer
# Julia 0.6, 12 bytes

```
n->eig(n)[1]

```

Try it online!

Unfortunately, `eig` returns both the eigenvalues and eigenvectors, as a tuple, so we waste another 9 bytes to lambdify it and grab the first item.
> 0 votes

# Answer
# Python + numpy, 33 bytes

```
from numpy.linalg import*
eigvals

```
> 0 votes

# Answer
# Pari/GP, 19 bytes

```
m->mateigen(m,1)[1]

```

Try it online!

---

# Pari/GP, 24 bytes

It seems that someone downvoted every answer that uses a built-in. OK, if you don't like built-in:

```
m->polroots(matdet(x-m))

```

Try it online!
> 0 votes

---
Tags: code-golf, matrix, linear-algebra, complex-numbers
---


title: Convert a TIO answer to a CMC answer

text:
# Question
Title: Convert a TIO answer to a CMC answer
Let's for once do something useful.

Given the text from a Try It Online codegolf submission, produce the equivalent Chat Mini Challenge submission, which is of the form

```
Language, N bytes: [`code`](URL)

```

or (if submission is a single byte – TIO will add a trailing s on the first line only if needed)

```
Language, 1 byte: [`code`](URL)

```

You may assume that the submission

* has only one line
* does not contain backticks (```)
* has no leading whitespace
* has a regular format like in the examples below; the code line is indented with four spaces (), not with HTML tags (`<pre><code>``</code></pre>`), i.e. no trailing whitespace.

**Note that the submission may have a syntax highlighting tag. See last example.**

You may optionally include the title text, i.e. `…url "Language - Try It Online"`.

### Examples

Given

```
# [05AB1E], 1 byte

    Ô

[Try it online!][TIO-j3v72bss]

[05AB1E]: https://github.com/Adriandmen/05AB1E
[TIO-j3v72bss]: https://tio.run/##MzBNTDJM/f//8JT//zNSgSAnJycfDAA "05AB1E – Try It Online"

```

return

```
05AB1E, 1 byte: [`Ô`](https://tio.run/##MzBNTDJM/f//8JT//zNSgSAnJycfDAA)

```

or

```
05AB1E, 1 byte: [`Ô`](https://tio.run/##MzBNTDJM/f//8JT//zNSgSAnJycfDAA "05AB1E – Try It Online")

```

Given

```
# [Brachylog], 4 bytes

    ḅhᵐc

[Try it online!][TIO-j3v75978]

[Brachylog]: https://github.com/JCumin/Brachylog
[TIO-j3v75978]: https://tio.run/##SypKTM6ozMlPN/r//@GO1oyHWyck//@vlJGampOTDwZK/6MA "Brachylog – Try It Online"

```

return

```
Brachylog, 4 bytes: [`ḅhᵐc`](https://tio.run/##SypKTM6ozMlPN/r//@GO1oyHWyck//@vlJGampOTDwZK/6MA)

```

Given

```
# [APL (Dyalog Unicode)], 15 bytes

<!-- language-all: lang-apl -->

    ⍴⍨¨⍳

[Try it online!][TIO-j44jgrps]

[APL (Dyalog Unicode)]: https://www.dyalog.com/
[TIO-j44jgrps]: https://tio.run/##AScA2P9hcGwtZHlhbG9n//9m4oaQ4o204o2owqjijbP//zcxNjDijLZmIDQ "APL (Dyalog Unicode) – Try It Online"

```

return

```
APL (Dyalog Unicode), 15 bytes: [`⍴⍨¨⍳`](https://tio.run/##AScA2P9hcGwtZHlhbG9n//9m4oaQ4o204o2owqjijbP//zcxNjDijLZmIDQ)

```

# Answer
# , ~~37~~, 35 bytes

```
ç^</dj
H3xf]x3Ji[`A`]Jd2/:
xr(A)

```

Try it online!
> 6 votes

# Answer
# Python 3, ~~113~~ ~~103~~ ~~98~~ 91 bytes

*-1 byte thanks to Value Ink.*

If you can, I could totally use some help with the regex. \>\<

```
lambda s:re.sub('(?s)# .(.*)](.*?)\n.* {4}(.*?)\n.+: (.*)',r'\1\2: [`\3`](\4)',s)
import re

```

Try it online!
> 4 votes

# Answer
# Retina, ~~54~~ ~~48~~ ~~52~~ ~~57~~ 48 bytes

*Saved 1 byte thanks to @MartinEnder, 1 byte thanks to @Riley*

```
...(.+)[^@]+    (.+)[^@]+:
$1: [`$2`](
1`]

$
)

```

Try it online! This assumes there won't be an `@` in the language name, which should be fine...
> 3 votes

# Answer
# 05AB1E, 50 bytes

```
']¡J¦¦¦|J|`‚ʒнðQ}`ðÛ|D`θ'"Êi\|ë\}θ#1èr"ÿ: [`ÿ`](ÿ)

```

Try it online!

*Now supports syntax highlighting too!*

`н` is replaced by  and `θ` is replaced by `®è` since those aren't pulled to TIO yet.

I just wonder how to shorten `¦¦¦`...
> 3 votes

# Answer
## JavaScript (ES6), 73 bytes

```
f=
s=>s.replace(/...(.*)](.*)[^]+    (.*)[^]+: (.*) ".*/,"$1$2: [`$3`]($4)")
```

```
<textarea rows=8 cols=75 oninput=o.textContent=this.value==f(this.value)?``:f(this.value)></textarea><pre id=o>
```
> 3 votes

# Answer
# MATLAB/Octave, ~~120~~ 126 bytes

```
@(a)strjoin(regexprep(strsplit(a,'\n'),{'\[.+\]: (.+) ".+','^[\[<].+','# \[(.+)\](.+)','^ +'},{'`]($1)','','$1$2: [`',''}),'')

```

This should work. For MATLAB it won't work with Unicode characters though I don't think, mostly because MATLAB sucks when it comes to odd characters. However it will work with Unicode for Octave, or at least TIO seems to be able to cope.

It should also handle submissions both with and without the `<-- -->` syntax highlighting.

*Updates*:

1. Added 4 bytes as I missed the `@(a)` when copying over
2. Added 2 bytes to add back ticks around the code in the output

Try it online!
> 2 votes

# Answer
# Ruby, 85 bytes

```
->s{s[/.*/].gsub(/# .|\]/){}+": [`#{s[/(?<=  )\S.*/]}`](#{s=~/TIO-\w+.: (\S+)/;$1})"}

```

Try it online!
> 2 votes

# Answer
# Python 2, 101 bytes

```
a=input().split('\n')
print'%s%s: [`%s`](%s)'%tuple(a[0][3:].split(']')+[a[-6][4:],a[-1].split()[1]])

```

Try it online! or Try all test cases
> 1 votes

# Answer
# PHP, 92 bytes

```
<?=preg_filter("<...(.+)\](, \d+ \w+).* {4}(\S+).*: (\S+).*>s","$1$2: [`$3`]($4)",$_GET[0]);

```

Try it online!
> 1 votes

# Answer
# Pip, ~~43~~ ~~39~~ 38 bytes

```
[a@>3DC']": [`"g@-6|>s"`]("(g@v^s1)')]

```

Try it online!

Takes the lines as separate command-line arguments. An example invocation could look like:

```
> pip.py -f convert.pip "# [05AB1E], 1 byte" "" "    Ô" "" "[Try it online!][TIO-j3v72bss]" "" "[05AB1E]: https://github.com/Adriandmen/05AB1E" "[TIO-j3v72bss]: https://tio.run/##MzBNTDJM/f//8JT//zNSgSAnJycfDAA \"05AB1E – Try It Online\""

```

<sup>though actually this doesn't work for me because Windows `cmd` complains about the `Ô`... \[inarticulate muttering\]</sup>

--At any rate, it works on TIO. Or, use the `-r` flag and take input from lines of stdin instead.

Assumes that the language name will not contain `]` (which would break the markdown anyway).

### Explanation

```
                                        g is list of cmdline args; a is 1st arg;
                                        s is space; v is -1 (implicit)
[                                    ]  Build a list with these elements:
 a@>3                                    1st line, sans first three characters,
     DC']                                 with the ] character deleted
         ": [`"                          This string
               g@-6                      6th line from the end (the code)
                   |>s                    with leading spaces stripped
                      "`]("              This string
                            g@v          Last line (containing the URL)
                               ^s         split on spaces
                           (     1)       get element at index 1
                                   ')    This character
                                        By default, the list is concatenated and printed

```
> 1 votes

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


title: Foam Bath Letters

text:
# Question
Title: Foam Bath Letters
If you have a small child in your house, you may have come across foam bath letters. These can be moistened and stuck to flat surfaces such as tiles and the side of the bath to make words and messages.

The range of words and messages is somewhat limited if you only have one set though, since you only get 36 characters: uppercase letters A-Z, and digits 0-9: `ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789`. However, you can be cunning and abuse some of the letters and digits to form extra copies of other letters:

```
3: E
1: I
7: L (when rotated)
M: W (when rotated)
0: O
2: S (when flipped)
5: S
W: M (when rotated)
2: Z
5: Z (when flipped)
O: 0
6: 9 (when rotated)
L: 7 (when rotated)
9: 6 (when rotated)

```

Note that these are not all bi-directional, since it tends to be easier to read a digit as part of a word than a letter as part of a number.

Each set also comes in a range of colours, where each letter is coloured in sequence. For example, if your set has 3 colours, Red, Yellow and Blue, your set would be like:

* Red: `ADGJMPSVY147`
* Yellow: `BEHKNQTWZ258`
* Blue: `CFILORUX0369`

Your task, therefore, is to take three parameters (in any suitable way) indicating a word or phrase, the number of colours to be used, and the number of sets you have, then to output a representation of the word or phrase, in a set of suitable colours, making use of substitutions if required. If it is not possible to make the word or phrase given the number of sets, instead output "Nope", in the appropriate colours.

## Examples

In all of these, the first parameter is the word or phrase, the second is the number of colours, and the third is the number of sets available.

```
["bath", 3, 1]

```

```
["programming", 3, 2]

```

```
["puzzles", 3, 1]

```

```
["code golf", 5, 1]

```

```
["willow tree", 1, 1]

```

```
["impossible phrase", 8, 1]

```

\- there is only 1 P in a set, and no valid substitutions

## Notes

* You can default to 1 set if this helps (e.g. a default parameter value of 1), but you must support multiple sets if requested. The number of sets you have will always be a positive non-zero integer.
* If you have multiple sets, they are all coloured in the same way: if A is red in the first set, it will be red in the second set too. The colours are applied per set, not to all sets in a given invocation
* You must support 1 to 36 colours - 1 means all characters are the same colour, 36 means they are all distinct. There will only be integer numbers of colours.
* You can use any colours, as long as they are visually distinct - if you are outputting to terminal, you can use a combination of foreground and background as a "colour", although you must not use the same colour for foreground and background
* Your output must use the characters that you actually use, not the characters from the input. For example, if you had \["willow", 1, 1\] as input, you could output `WIL7OM` with 7 and M rotated 180 degrees
* You should use the correct letters first, then substitute: `MI7LOW` is incorrect for \["willow", 1, 1\]
* You can use any substitution for a given character: `SO5` and `SO2` with a flipped 2 are both valid for "SOS"
* Multiple invocations of your code for the same input do not have to produce identical output
* Output should be in uppercase, but input can be in any mix of upper and lower case
* It should be obvious, but a space does not have a colour

## Rules

* This is code golf, but with semi-graphical output (I'm not sure if you can do flipped text in a terminal, but am interested to see if Pyth has a built in for it)
* Standard loopholes apply
* There are no bonuses for functions, but please vote up interesting answers
* Include some screenshots of your output in your answers

### Related Challenges

# Answer
# HTML/JavaScript (with jQuery)/CSS - non-competing/non-golfed

Just to get the ball rolling, and show that it's not impossible, here is a non-golfed, non-competing implementation that takes a naive approach to the task.

It first creates a string of all the possible characters (`tempalph`), by joining as many copies of the alphabet as there are sets. Then it iterates through the phrase, putting each letter of the phrase into an output variable, and blanking the first instance of that letter from `tempalph`. If it can't (the letter doesn't exist), it checks if the letter is replaceable with something left in the string. If that also fails, it outputs a pre-defined "NOPE" output. Assuming it doesn't hit the "NOPE" case, it returns the output string and puts it into a DIV on the page.

It then loops through the base alphabet string, and if a letter has been used, assigns it an appropriate CSS class, each of which has a pre-defined colour set.

It uses HTML inputs for input, and updates on keyup in them.

Try it at JSFiddle

Example for `["BATH", 3, 1]`:

JS:

```
var alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

function getPhrase(phrase, sets){
    var modphrase = "";
  var nope = 'NOPE';
  var re = /^[A-Z0-9 ]+$/;
  if (re.test(phrase)){
    // might be valid - need to check there are enough characters available
    // At this point, need to look at specifically what characters are needed

    var tempalph = "";
    for ( var i=0; i'+char+'';
        if (tempalph.indexOf(char) != -1){
        tempalph = tempalph.replace(char, "#");
      } else {
        switch(char){
            case "E":
            if (tempalph.indexOf("3") != -1){
                    tempalph = tempalph.replace("3", "#");
              modchar = '3';
                } else {
                return nope;
            }
            break;
          case "I":
            if (tempalph.indexOf("1") != -1){
                    tempalph = tempalph.replace("1", "#");
              modchar = '1';
                } else {
              return nope;
            }
            break;
          case "L":
            if (tempalph.indexOf("7") != -1){
                    tempalph = tempalph.replace("7", "#");
              modchar = '7';
                } else {
              return nope;
            }
            break;
          case "M":
            if (tempalph.indexOf("W") != -1){
                    tempalph = tempalph.replace("W", "#");
              modchar = 'W';
                } else {
              return nope;
            }
            break;
          case "O":
            if (tempalph.indexOf("0") != -1){
                    tempalph = tempalph.replace("0", "#");
              modchar = '0';
                } else {
              return nope;
            }
            break;
          case "W":
            if (tempalph.indexOf("M") != -1){
                    tempalph = tempalph.replace("M", "#");
              modchar = 'M';
                } else {
              return nope;
            }
            break;
          case "0":
            if (tempalph.indexOf("O") != -1){
                    tempalph = tempalph.replace("O", "#");
              modchar = 'O';
                } else {
              return nope;
            }
            break;
          case "6":
            if (tempalph.indexOf("9") != -1){
                    tempalph = tempalph.replace("9", "#");
              modchar = '9';
                } else {
              return nope;
            }
            break;
          case "7":
            if (tempalph.indexOf("L") != -1){
                    tempalph = tempalph.replace("L", "#");
              modchar = 'L';
                } else {
              return nope;
            }
            break;
          case "9":
            if (tempalph.indexOf("6") != -1){
                    tempalph = tempalph.replace("6", "#");
              modchar = '6';
                } else {
              return nope;
            }
            break;

          case "S":
            if (tempalph.indexOf("5") != -1){
                    tempalph = tempalph.replace("5", "#");
              modchar = '5';
                } else if (tempalph.indexOf("2") != -1){
                    tempalph = tempalph.replace("2", "#");
              modchar = '2';
                } else {
              return nope;
            }
            break;
                    case "Z":
            if (tempalph.indexOf("2") != -1){
                    tempalph = tempalph.replace("2", "#");
              modchar = '2';
                } else if (tempalph.indexOf("5") != -1){
                    tempalph = tempalph.replace("5", "#");
              modchar = '5';
                } else {
              return nope;
            }
            break;
          case " ":
            break;
          default:
            return nope;
          }

      }
        modphrase += modchar;
    }

    return modphrase;
  } else {
    // contains some other characters, so definitely isn't valid
    return nope;
  }
}

function addColors(colcount){
  var i = 0;
  for (let char of alphabet){
    exclass = "."+char;
    newclass = "col"+i;
    if ($(exclass).length>0){
      $(exclass).addClass(newclass);
    }
    i++;
    if (i==colcount){
        i=0;
    }
  }
}

$("#phrase,#sets,#colours").on("keyup", function(){
    var phrase = $("#phrase").val().toUpperCase();
  phrase = getPhrase(phrase, $("#sets").val());
    $("#output").html(phrase);
  addColors($("#colours").val());
})

```

HTML:

```
<label>Phrase<input type="text" id="phrase"/></label>
<label>Colours<input type="text" id="colours" value="3"/></label>
<label>Sets<input type="text" id="sets" value="1"/></label>

<div id="output">

</div>

```

CSS:

```
.col0{ color: #f00 }
.col1{ color: #0f0 }
.col2{ color: #00f }
.col3{ color: #66CDAA }
.col4{ color: #EE82EE }
.col5{ color: #7FFFD4 }
.col6{ color: #7FFFD4 }
.col7{ color: #FFDEAD }
.col8{ color: #D8BFD8 }
.col9{ color: #FF6347 }
.col10{color: #8B4513 }
.col11{color: #800000 }
.col12{color: #00FFFF }
.col13{color: #32CD32 }
.col14{color: #191970 }
.col15{color: #1E90FF }
.col16{color: #A0522D }
.col17{color: #808000 }
.col18{color: #DC143C }
.col19{color: #90EE90 }
.col20{color: #D2691E }
.col21{color: #48D1CC }
.col22{color: #008000 }
.col23{color: #8B008B }
.col24{color: #6495ED }
.col25{color: #800080 }
.col26{color: #000080 }
.col27{color: #DB7093 }
.col28{color: #7FFF00 }
.col29{color: #00FA9A }
.col30{color: #0000FF }
.col31{color: #BC8F8F }
.col32{color: #A52A2A }
.col33{color: #4169E1 }
.col34{color: #FFFF00 }
.col35{color: #FFA07A }

.rot{ display: inline-block; transform: rotate(0.5turn);}
.flip{ display: inline-block; transform: rotateY(0.5turn);}

div{
  font-family: sans-serif;
  font-size: 3em;
  background-color: #000;
  padding: 10px;
}

```
> 1 votes

---
Tags: code-golf, graphical-output, alphabet
---


title: Numbering Hierarchical Outlines

text:
# Question
Title: Numbering Hierarchical Outlines
Write a program that takes in a string where every line consists of the character `0` indented by some number of spaces. The top line is not indented and every other line will be indented by at most one more space than the line just before it.

No lines will have trailing spaces but you may optionally assume there is a single trailing newline.

For example, the input might look something like this:

```
0
 0
  0
  0
 0
0
 0
 0
 0
  0
0
 0
  0
  0

```

Your task is to number it like a hierarchical outline, using increasing positive integers as the line headers. This would be the output for the example:

```
1
 1
  1
  2
 2
2
 1
 2
 3
  1
3
 1
  1
  2

```

Note how every hierarchical indentation level has its own set of increasing numbers, even if they only go up to one.

In the output, there should be no trailing spaces, but there may optionally be a single trailing newline.

Write a full program that takes the input string via stdin or command line, or write a function that takes the string in as an argument. Print the result or return it as a string.

**The shortest code in bytes wins.**

### Examples

If the empty string is input, the empty string should be output.

The next most trivial example is the input

```
0

```

which should become

```
1

```

Large example - Input:

```
0
 0
  0
 0
  0
 0
  0
  0
   0
   0
    0
     0
     0
     0
     0
    0
   0
    0
    0
  0
0
 0
  0
 0
  0
  0
  0
  0
  0
  0
  0
  0
  0
  0
  0
   0
    0
     0
  0
   0
0
0
0
 0
  0
   0
    0
     0
      0
      0
     0
    0
   0
  0
 0
  0
  0
   0
   0
0
0

```

Output:

```
1
 1
  1
 2
  1
 3
  1
  2
   1
   2
    1
     1
     2
     3
     4
    2
   3
    1
    2
  3
2
 1
  1
 2
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
   1
    1
     1
  12
   1
3
4
5
 1
  1
   1
    1
     1
      1
      2
     2
    2
   2
  2
 2
  1
  2
   1
   2
6
7

```

# Answer
> 2 votes
# Pyth, 18 bytes

```
V.z+PNhX0=Y>lN+0Y1

```

This is an exact translation of @Sp3000's answer. I tried many different approaches and variations, but I couldn't shorten it, so I am marking this CW.

Demonstration.

# Answer
> 8 votes
# Python 2, 77

```
S={'0':0}
for w in input().split('\n'):S[w]+=1;S[' '+w]=0;print w[:-1]+`S[w]`

```

Like Sp3000's answer, but with a dictionary. The dict `S` stores the current number for each nesting level `'0', ' 0', ' 0'` and so on. For each line in the input, increment the corresponding nesting level, and reset the nesting level one higher to 0.

# Answer
> 6 votes
# Python 2, ~~86~~ ~~85~~ 81 bytes

```
S=[]
for r in input().split("\n"):S=([0]+S)[-len(r):];S[0]+=1;print r[:-1]+`S[0]`

```

*(-5 bytes thanks to @xnor)*

Takes input as a string via STDIN, e.g.

```
'0\n 0\n  0\n  0\n 0\n0\n 0\n 0\n 0\n  0\n0\n 0\n  0\n  0'

```

Alternatively, here's a function for 5 extra bytes:

```
def f(I,S=[]):
 for r in I.split("\n"):S=([0]+S)[-len(r):];S[0]+=1;print r[:-1]+`S[0]`

```

# Answer
> 4 votes
# CJam, 25 bytes

```
LqN/{0+I,<))_IW@toNo+}fI;

```

Like my Python answer, this uses an array to store which number each indentation level is up to. One difference, however, is that this uses `t` (array set) to replace the 0 on each line with the number we want.

Try it online.

# Answer
> 3 votes
# JavaScript ES6, ~~83~~ 81 bytes

```
f=(z,a=[])=>z.replace(/ *0/g,e=>e.replace(0,a.fill(0,l=e.length)[--l]=a[l]+1||1))

```

This uses an array that holds the current number for each indentation level. Everything past that level is reset to 0 using `fill()`. EDIT: 2 bytes saved thanks to vihan1086's tip.

The Stack Snippet below can be used for testing because it is ungolfed slightly and uses better-supported ES5 syntax. The second function is a polyfill for `fill()` as there is not a short way to do it without ES6.

```
f=function(z){
  a=[]
  return z.replace(/ *0/g,function(e){
    return e.replace(0,a.fill(0,l=e.length)[--l]=a[l]+1||1)
  })
}

if(!Array.prototype.fill){
  Array.prototype.fill = function(val, start){
    var res = this;
    for(var i = start; i<this.length; i++){
      res[i] = val;
    }
    return res;
  };
}

run=function(){document.getElementById('output').innerText=f(document.getElementById('input').value)};document.getElementById('run').onclick=run;run()
```

```
<textarea id="input" rows="15" cols="10">
0
 0
  0
  0
 0
0
 0
 0
 0
  0
0
 0
  0
  0</textarea>
<pre id="output" style="display:inline-block; vertical-align:top; margin:0"></pre><br />
<button id="run">Run</button>
```

# Answer
> 1 votes
# Python - 191

```
def p(s,i,v,n=1):
    while i<len(s)and s[i]and'0'not in s[i][:v]:
        if s[i][v]=='0':s[i]=' '*v+str(n);n+=1;i+=1
        else:i=p(s,i,v+1)
    return(s,i)[v!=0]
z=lambda r:'\n'.join(p(r.split('\n'),0,0))

```

The function is `z`.

# Answer
> 0 votes
# Pip `-rn`, ~~31~~ 27 bytes

```
{Wl#<alPU0l@>:-#aaR0++@l}Mg

```

Input from stdin. Try it online!

### Explanation

```
                             g is list of lines of stdin (-r flag); l is []
                             Note that l is a global variable
{                       }Mg  Map this function to each a in g:
 Wl#<a                        While l is less in length than a:
      lPU0                     Push a 0 to (the front of) l
                              (This handles increasing the indent)
          l@>:                Slice and assign back to l...
              -#a              ... its last len(a) elements
                              (This handles decreasing the indent)
                 aR0          In a, replace 0 with
                      @l       the first element of l
                    ++         incremented in-place
                              The function returns the above expression
                             The resulting list from map is printed, newline-separated
                              (-n flag)

```

---
Tags: code-golf, string, data-structures, whitespace
---