# Question
Title: Print a conversion table for (un)signed bytes
Your task: Print or return a conversion table with every byte from `00` to `ff`'s value as an unsigned integer, to its value as a signed one (using two's complement).

For example:

```
0     0
1     1
2     2
3     3
4     4
5     5
6     6
7     7
8     8
9     9
10    10
11    11
12    12
13    13
14    14
15    15
16    16
17    17
18    18
19    19
20    20
21    21
22    22
23    23
24    24
25    25
26    26
27    27
28    28
29    29
30    30
31    31
32    32
33    33
34    34
35    35
36    36
37    37
38    38
39    39
40    40
41    41
42    42
43    43
44    44
45    45
46    46
47    47
48    48
49    49
50    50
51    51
52    52
53    53
54    54
55    55
56    56
57    57
58    58
59    59
60    60
61    61
62    62
63    63
64    64
65    65
66    66
67    67
68    68
69    69
70    70
71    71
72    72
73    73
74    74
75    75
76    76
77    77
78    78
79    79
80    80
81    81
82    82
83    83
84    84
85    85
86    86
87    87
88    88
89    89
90    90
91    91
92    92
93    93
94    94
95    95
96    96
97    97
98    98
99    99
100   100
101   101
102   102
103   103
104   104
105   105
106   106
107   107
108   108
109   109
110   110
111   111
112   112
113   113
114   114
115   115
116   116
117   117
118   118
119   119
120   120
121   121
122   122
123   123
124   124
125   125
126   126
127   127
128   -128
129   -127
130   -126
131   -125
132   -124
133   -123
134   -122
135   -121
136   -120
137   -119
138   -118
139   -117
140   -116
141   -115
142   -114
143   -113
144   -112
145   -111
146   -110
147   -109
148   -108
149   -107
150   -106
151   -105
152   -104
153   -103
154   -102
155   -101
156   -100
157   -99
158   -98
159   -97
160   -96
161   -95
162   -94
163   -93
164   -92
165   -91
166   -90
167   -89
168   -88
169   -87
170   -86
171   -85
172   -84
173   -83
174   -82
175   -81
176   -80
177   -79
178   -78
179   -77
180   -76
181   -75
182   -74
183   -73
184   -72
185   -71
186   -70
187   -69
188   -68
189   -67
190   -66
191   -65
192   -64
193   -63
194   -62
195   -61
196   -60
197   -59
198   -58
199   -57
200   -56
201   -55
202   -54
203   -53
204   -52
205   -51
206   -50
207   -49
208   -48
209   -47
210   -46
211   -45
212   -44
213   -43
214   -42
215   -41
216   -40
217   -39
218   -38
219   -37
220   -36
221   -35
222   -34
223   -33
224   -32
225   -31
226   -30
227   -29
228   -28
229   -27
230   -26
231   -25
232   -24
233   -23
234   -22
235   -21
236   -20
237   -19
238   -18
239   -17
240   -16
241   -15
242   -14
243   -13
244   -12
245   -11
246   -10
247   -9
248   -8
249   -7
250   -6
251   -5
252   -4
253   -3
254   -2
255   -1

```

**Formatting:**

* The output doesn't have to be padded to nicely line up like it does above (just a space in between would be fine)
* The separators can be any two strings which can't be confused for the data or each other
* Any base can be used (but if using binary, `-1` would be `-00000001`, not `11111111`)
* Trailing (and/or leading) whitespace and separators are allowed
* The output must be in the correct order
* **The output must be textual; returning arrays/lists/dictionaries is not allowed**

**Valid outputs:**

(using `...` to skip over some repetitive chunks)

Zero-padded hexadecimal:

```
00 00
01 01
...
7f 7f
80 -80
81 -7f
...
fe -02
ff -01

```

Binary with `,` and `;` for separators:

```
0,0;1,1;10,10;11,11;...;01111111,01111111;10000000,-10000000;10000001,-01111111;...;11111110,-00000010,11111111,00000001

```

Negadecimal with custom separators:

```
0 The HORSE is a noble animal. 0

1 The HORSE is a noble animal. 1

...

287 The HORSE is a noble animal. 287

288 The HORSE is a noble animal. 1932

289 The HORSE is a noble animal. 1933

...

354 The HORSE is a noble animal. 18

355 The HORSE is a noble animal. 19

```

Good luck!

# Answer
# Bash \+ coreutils, 30

```
(seq 0 127;seq -128 -1)|nl -v0

```

Try it online!
> 9 votes

# Answer
# C (gcc), ~~54~~ ~~50~~ 47 bytes

```
i;main(){for(;i<256;printf("%u,%hhd ",i++,i));}

```

Try it online!

## Explanation

```
i;                      // Static variable initialized to 0
main() {
    for(;i<256;         // While the variable is <= 255:
        printf("%u,%hhd ",i++,i));
                        //     Output the original, then the char-coerced
                        //     value. Increment after use.
}

```

# C (gcc), 45 bytes

Non-portable, but 2 bytes shorter.

```
f(i){for(i=-1;i++<255;printf("%u,%hhd ",i));}

```

Try it online!
> 8 votes

# Answer
# APL (Dyalog Extended), 18 bytes

Full program printing to stdout with `¯` as negative symbol. Requires 0-based indexing.

```
(⍳∘≢,⍪)…127,-128…1

```

Try it online!

`128…1` integers 128 through 1

`-` negate those

`127,` prepend 127

fill integers from 0 until the first element of that (127)

`(``)` apply the tacit function:

`,⍪` columnify and prepend \[a column consisting of\]…

`⍳⍤≢` the **ɩ**ndices of the tally
> 5 votes

# Answer
# Jelly, 11 10 bytes

```
⁹Ḷ_H%⁹żƊṢG

```

Try it online!

*-1 byte thanks to Jonathan Allan*

## Explanation

```
⁹Ḷ_H%⁹żƊṢG   Main niladic link
⁹             256
 Ḷ            [0..255]
  _           Subtract
   H          half (of 256) = 128 => [-128..127]
       Ɗ      (
    %           Modulo
     ⁹          256
      ż         Zip with the list at the beginning of this inner link
       Ɗ      )
         Ṣ    Sort
          G   Format as a grid

```
> 5 votes

# Answer
# Julia 1.0, ~~31~~ 28 bytes

```
r=0:255
@.println(r=>r%Int8)

```

Try it online!

Output format:

```
0 => 0
1 => 1...

```
> 4 votes

# Answer
# Python 2, 37 bytes

```
for i in range(256):print i,127-i^127

```

Try it online!
> 4 votes

# Answer
# JavaScript (ES6),  ~~41~~ 40 bytes

*Saved 1 byte thanks to @ovs*

Output format: `0,0 1,1 ... 255,-1`.

```
f=n=>n>>8?'':[~~n,128+~n^127]+' '+f(-~n)

```

Try it online!

Or maybe 39 bytes or even 38 bytes by abusing the loose output format. (But it's ugly.)

### Commented

```
f =                  // f is a recursive function
n =>                 // taking a counter n, which is initially undefined
  n >> 8 ?           // if n = 256:
    ''               //   stop the recursion
  :                  // else:
    [                //   build an array consisting of:
      ~~n,           //     the unsigned value (coerced to a number because
                     //     it's undefined on the first iteration)
      128 + ~n ^ 127 //     the signed value, which is (127 - n) XOR 127
                     //                              = (128 + (-n - 1)) XOR 127
    ]                //   end of array
    + ' '            //   coerce the array to a string and append a space
    + f(-~n)         //   append the result of a recursive call with n + 1

```
> 3 votes

# Answer
# 05AB1E, ~~11~~ 10 bytes

```
₅ÝƵQÝÂ±«ø»

```

-1 byte thanks to *@ovs*.

Uses single spaces and newlines as delimiters for the output.

Try it online.

**Explanation:**

```
₅Ý        # Push a list in the range [0,255]
ƵQÝ       # Push a list in the range [0,127]
   Â      # Bifurcate it; short for Duplicate & Reverse copy
    ±     # Get the bitwise-NOT of each (n → -n-1)
     «    # Merge the top two lists together
ø         # Create all possible pairs of the [0..255] and [0..127,-128..-1] lists
 »        # Join each pair by spaces, and then each string by newlines
          # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `ƵQ` is `127`.
> 3 votes

# Answer
# Husk, 16 bytes

```
†szeŀ256Sṙohṡ128

```

Try it online!, Another method, Another method

## Explanation

```
†szeŀ256Sṙohṡ128
            ṡ128 symmetric range of 128 [-128...128]
          oh     remove last element
        Sṙ       rotate 128 spaces
    ŀ256         range [0...255]
  ze             zip the two, creating pairs
†s               convert all the numbers to strings
                 (can also be mw)

```
> 3 votes

# Answer
# Nim `-d:danger`, 33 32 bytes

```
for b in 0..255:b.echo' ',b.int8

```

Try it online!

# Nim, 40 39 bytes

```
for b in 0..255:b.echo' ',cast[int8](b)

```

Try it online!

Probably doesn't work on big-endian architectures.
> 3 votes

# Answer
# , 37 bytes

```
for(i in 0:255)cat(i,i-(i>127)*256,T)

```

Try it online!

Separator between converted numbers is ""; separator between each element of the list of conversions is " `TRUE`". List is appended with a trailing separator (as allowed by the challenge rules).
"`TRUE`" is a pre-defined variable in  that can be specified by a single character, `T`, and that has non-numeric output, so it's used as a convenient golfy separator here.

---

# , 38 bytes

```
cat(paste(0:255,c(0:127,-128:-1),'
'))

```

Try it online!, Another approach

Previous, slightly longer attempt, but with more-conventional separators (space & newline).
> 3 votes

# Answer
# Python 3, ~~47~~ 41 bytes

-6 thanks to @EasyasPi

```
print([(127-i^127,i)for i in range(256)])

```
> 3 votes

# Answer
# Haskell, 54 bytes

```
unlines[show x++' ':show(x-x`div`128*256)|x<-[0..255]]

```

Try it online!

* Sadly `xor` is not in prelude module.
* Table is a string of pairs separated by newlines.
> 3 votes

# Answer
# C#, 61 bytes

Not very creative, but I think the shortest this can get.

```
for(var i=0;i<256;)System.Console.Write(i+$",{(sbyte)i++};");

```

Try it online!

This is a **complete** program thanks to C#9 and top-level statements. SharpLab
> 3 votes

# Answer
# Java, 58 chars

```
void f(){for(int i=0;i<256;out.println(i+" "+(byte)i++));}

```

Try it online!

The `byte` data type is an 8-bit signed two's complement integer. It has a minimum value of -128 and a maximum value of 127 (inclusive).
> 3 votes

# Answer
# Vyxal, `j`, ~~14~~ ~~9~~ 8 bytes

```
₈ʁ₇ʁḂꜝJZ

```

Try it Online!

OP says it's allowable

*-5 bytes due to porting 05AB1E*

## Explained

```
₈ʁ₇ʁḂꜝJZ
₈ʁ         # Push range [0, 256)
  ₇ʁḂ      # Push [0, 128) and (128, 0]
     ꜝ     # Bit-not over that last copy
      JZ   # Merge and zip
           # The j flag joins on newlines

```
> 3 votes

# Answer
# Vyxal `j`, 15 bytes

```
₈‹ʀ₇‹ʀḂN₇NpJZvṄ

```

Try it Online!
> 3 votes

# Answer
# Python 2, <sup>~~49~~ ~~53~~</sup> 51 bytes

Saved 2 bytes taking a peek at ovs's Python answer!!!
Added 8 bytes to fix a rule violation kindly pointed out by ovs.
Saved 2 bytes thanks to ovs!!!

```
f=lambda i=255:i*' 'and'%d '*2%(i,127-i^127)+f(i-1)

```

Try it online!
> 2 votes

# Answer
# PowerShell, 34 bytes

```
0..255|%{"$($_;($_-bxor128)-128)"}

```

Try it online!
> 2 votes

# Answer
# PowerShell, ~~29~~ 33 bytes

+4 bytes: fit to the task rules. Thanks @Zaelin Goodman

```
0..127+-128..-1|%{"$(($i++);$_)"}

```

Try it online!
> 2 votes

# Answer
# Pyth, ~~17~~ 16 bytes

```
V256++Nd-J127xNJ

```

Try it online!

-1 byte thanks to FryAmTheEggman!

---

Python 3.8 translation:

```
for N in range(256):print(str(N)+" "+str((J:=127)-N^J))

```
> 2 votes

# Answer
# Scala, ~~46~~ 45 bytes

```
()=>for(i<-0 to 255)print(s"$i,${i.toByte} ")

```

Output format: `0,0 1,1 2,2 ... 127,127 128,-128 129,-127 ... 253,-3 254,-2 255,-1`  with `,` and  for separators.

Try it online!

**Edit**: Due to conventions, the String Interpolator `f` was changed to `s`. Thanks to user!

---

### 37 bytes

... if ignoring the seperator rule.

```
()=>for(i<-0 to 255)print(i,i.toByte)

```

Output format: `(0,0)(1,1)(2,2)(...)(127,127)(128,-128)(129,-127)(...)(253,-3)(254,-2)(255,-1)` with `,` and `)(` for separators, but unfortunately also with a leading `(` and trailing `)`.

Try it online!
> 2 votes

# Answer
# AWK, ~~48~~ 45 bytes

*Lowered to 45 bytes thanks to Dominic van Essen.*

```
BEGIN{for(;i<256;i++)print +i,i<128?+i:i-256}

```

Try it online!

Had to workaround the fact that bitwise functions in GNU AWK don't accept negative arguments. Anyway, this should work on any AWK implementation.
> 2 votes

# Answer
# Ruby, 36 bytes

```
256.times{|i|puts [i,127-i^127]*' '}

```

Try it online!
> 2 votes

# Answer
# FALSE, 37 bytes

```
0[$$$$256=~][128>[256-]?\.44,.10,1+]#

```

Try it online!
> 2 votes

# Answer
# Python 3, 38 bytes

```
for i in range(256):print(i,127-i^127)

```

Try it online!
> 2 votes

# Answer
# PHP, 64 bytes

```
<?php for($x=0;$x<256;$x++){echo$x.','.($x<128?$x:$x-256).";";}

```

```
<?php for($x = 0; $x < 256; $x++){ #Go through each number
  echo $x . ',' . #Write x, then...
($x < 128 ? $x #if x is less than 128, write x again,
: $x - 256) . ";";  #otherwise write x - 256
}

```

Uses ',' and '.' as separators.
> 2 votes

# Answer
# Factor, 43 bytes

```
256 iota [ dup pprint bl 8 >signed . ] each

```

Try it online!
> 2 votes

# Answer
# jq, 30 bytes

```
range(256)|[.,(128+.)%256-128]

```

Try it online!

output format:

```
[
  0,
  0
]
...
[
  255,
  -1
]

```
> 2 votes

# Answer
# Red, 45 bytes

```
repeat n 256[print[p: n - 1 p xor 128 - 128]]

```

Try it online!

Uses @Arnauld's formula
> 1 votes

# Answer
# Perl 5, 32 bytes

```
say"$_ ",$_-2*($_&128)for 0..255

```

Try it online!
> 1 votes

# Answer
# Rust, 45 bytes

```
||for i in 0..256{print!("{}:{}
",i,i as i8)}

```

Try it online!

Note the newline literal, output format is

```
1:1
2:2
...

```

This prints the loop count as both an `i32` and an `i8`. Note that as casts are not allowed to panic, so they may result in unexpected behavior on overflow.
> 1 votes

# Answer
# Charcoal, 17 bytes

```
ＩＥ⁺…⁰⊗℅@…±⊗℅@⁰⟦κι

```

Try it online! Link is to verbose version of code. Outputs in decimal with single and double newline as separators. Explanation:

```
   …                 Range from
    ⁰                Literal `0` to
       @            Literal string `@`
      ℅             ASCII code i.e. 64
     ⊗              Doubled i.e. 128
  ⁺                 Concatenated with
        …           Range from
            @       Literal string `@`
           ℅        ASCII code
          ⊗         Doubled
         ±          Negated
             ⁰      To literal `0`
 Ｅ                  Map over values
               κ    Current index
                ι   Current value
              ⟦     Wrap in list
Ｉ                   Cast to string
                    Implicitly print

```
> 1 votes

# Answer
# Retina 0.8.2, 43 bytes

```

256$*_¶
_
$.` -$.'¶
128`-.+
$%`

```

Try it online! Uses space and newline as the delimiters, plus adds a variety of trailing spaces and newlines. Explanation:

```

256$*_¶

```

Insert 256 `_`s plus a newline which is used to balance out the number of characters after each `_`.

```
_
$.` -$.'¶

```

Replace each `_` with a line giving the number of preceding and (with a minus sign) following characters.

```
128`-.+
$%`

```

Replace the first 128 minus numbers with the number that precedes it.
> 1 votes

# Answer
# Wolfram Language (Mathematica), ~~38~~ 36 bytes

```
Print@i@Mod[i,256,-128]~Do~{i,0,255}

```

Try it online!
> 1 votes

# Answer
# Perl 5, 32 bytes

An alternative to @KjetilS's solution of the same length.

```
say$_,$",unpack c,chr for 0..255

```

Try it online!
> 1 votes

# Answer
# JavaScript (SpiderMonkey), 35 bytes

```
for(i=0;i<256;)print(i,i++<<24>>24)

```

Try it online!
> 1 votes

# Answer
# Octave, 28 bytes

```
disp([0:255;0:127 -128:-1]')

```

Try it online!

I'm not sure if `disp()` could be removed or not...
> 1 votes

# Answer
# Deadfish~, 15587 bytes

```
{{i}ddddd}ddc{d}ddddddccccc{i}iiiiiic{{d}iiiiii}iic{{i}dddddd}dc{d}{d}iiiccccc{i}{i}dddc{{d}iiiiii}ic{{i}dddddd}c{d}{d}iiccccc{i}{i}ddc{{d}iiiiii}c{{i}dddddd}ic{d}{d}iccccc{i}{i}dc{{d}iiiiii}dc{{i}dddddd}iic{d}{d}ccccc{i}{i}c{{d}iiiiii}ddc{{i}dddddd}iiic{d}{d}dccccc{i}{i}ic{{d}iiiiii}dddc{{i}dddddd}iiiic{d}{d}ddccccc{i}{i}iic{{d}iiiiii}ddddc{{i}dddddd}iiiiic{d}{d}dddccccc{i}{i}iiic{{d}iiiiii}dddddc{{i}dddddd}iiiiiic{d}{d}ddddccccc{i}{i}iiiic{{d}iiiiii}ddddddc{{i}ddddd}dddc{d}{d}dddddccccc{i}{i}iiiiic{{d}iiiii}iiic{{i}dddddd}dcdc{d}ddddddcccc{i}{i}dddcdc{{d}iiiiii}iic{{i}dddddd}dcc{d}{d}iiicccc{i}{i}dddcc{{d}iiiiii}ic{{i}dddddd}dcic{d}{d}iicccc{i}{i}dddcic{{d}iiiiii}c{{i}dddddd}dciic{d}{d}icccc{i}{i}dddciic{{d}iiiiii}dc{{i}dddddd}dciiic{d}{d}cccc{i}{i}dddciiic{{d}iiiiii}ddc{{i}dddddd}dciiiic{d}{d}dcccc{i}{i}dddciiiic{{d}iiiiii}dddc{{i}dddddd}dciiiiic{d}{d}ddcccc{i}{i}dddciiiiic{{d}iiiiii}ddddc{{i}dddddd}dciiiiiic{d}{d}dddcccc{i}{i}dddciiiiiic{{d}iiiiii}dddddc{{i}dddddd}dc{i}dddc{d}{d}ddddcccc{i}{i}dddc{i}dddc{{d}iiiiii}ddddddc{{i}dddddd}dc{i}ddc{d}{d}dddddcccc{i}{i}dddc{i}ddc{{d}iiiii}iiic{{i}dddddd}cddc{d}ddddddcccc{i}{i}ddcddc{{d}iiiiii}iic{{i}dddddd}cdc{d}{d}iiicccc{i}{i}ddcdc{{d}iiiiii}ic{{i}dddddd}cc{d}{d}iicccc{i}{i}ddcc{{d}iiiiii}c{{i}dddddd}cic{d}{d}icccc{i}{i}ddcic{{d}iiiiii}dc{{i}dddddd}ciic{d}{d}cccc{i}{i}ddciic{{d}iiiiii}ddc{{i}dddddd}ciiic{d}{d}dcccc{i}{i}ddciiic{{d}iiiiii}dddc{{i}dddddd}ciiiic{d}{d}ddcccc{i}{i}ddciiiic{{d}iiiiii}ddddc{{i}dddddd}ciiiiic{d}{d}dddcccc{i}{i}ddciiiiic{{d}iiiiii}dddddc{{i}dddddd}ciiiiiic{d}{d}ddddcccc{i}{i}ddciiiiiic{{d}iiiiii}ddddddc{{i}dddddd}c{i}dddc{d}{d}dddddcccc{i}{i}ddc{i}dddc{{d}iiiii}iiic{{i}dddddd}icdddc{d}ddddddcccc{i}{i}dcdddc{{d}iiiiii}iic{{i}dddddd}icddc{d}{d}iiicccc{i}{i}dcddc{{d}iiiiii}ic{{i}dddddd}icdc{d}{d}iicccc{i}{i}dcdc{{d}iiiiii}c{{i}dddddd}icc{d}{d}icccc{i}{i}dcc{{d}iiiiii}dc{{i}dddddd}icic{d}{d}cccc{i}{i}dcic{{d}iiiiii}ddc{{i}dddddd}iciic{d}{d}dcccc{i}{i}dciic{{d}iiiiii}dddc{{i}dddddd}iciiic{d}{d}ddcccc{i}{i}dciiic{{d}iiiiii}ddddc{{i}dddddd}iciiiic{d}{d}dddcccc{i}{i}dciiiic{{d}iiiiii}dddddc{{i}dddddd}iciiiiic{d}{d}ddddcccc{i}{i}dciiiiic{{d}iiiiii}ddddddc{{i}dddddd}iciiiiiic{d}{d}dddddcccc{i}{i}dciiiiiic{{d}iiiii}iiic{{i}dddddd}iicddddc{d}ddddddcccc{i}{i}cddddc{{d}iiiiii}iic{{i}dddddd}iicdddc{d}{d}iiicccc{i}{i}cdddc{{d}iiiiii}ic{{i}dddddd}iicddc{d}{d}iicccc{i}{i}cddc{{d}iiiiii}c{{i}dddddd}iicdc{d}{d}icccc{i}{i}cdc{{d}iiiiii}dc{{i}dddddd}iicc{d}{d}cccc{i}{i}cc{{d}iiiiii}ddc{{i}dddddd}iicic{d}{d}dcccc{i}{i}cic{{d}iiiiii}dddc{{i}dddddd}iiciic{d}{d}ddcccc{i}{i}ciic{{d}iiiiii}ddddc{{i}dddddd}iiciiic{d}{d}dddcccc{i}{i}ciiic{{d}iiiiii}dddddc{{i}dddddd}iiciiiic{d}{d}ddddcccc{i}{i}ciiiic{{d}iiiiii}ddddddc{{i}dddddd}iiciiiiic{d}{d}dddddcccc{i}{i}ciiiiic{{d}iiiii}iiic{{i}dddddd}iiicdddddc{d}ddddddcccc{i}{i}icdddddc{{d}iiiiii}iic{{i}dddddd}iiicddddc{d}{d}iiicccc{i}{i}icddddc{{d}iiiiii}ic{{i}dddddd}iiicdddc{d}{d}iicccc{i}{i}icdddc{{d}iiiiii}c{{i}dddddd}iiicddc{d}{d}icccc{i}{i}icddc{{d}iiiiii}dc{{i}dddddd}iiicdc{d}{d}cccc{i}{i}icdc{{d}iiiiii}ddc{{i}dddddd}iiicc{d}{d}dcccc{i}{i}icc{{d}iiiiii}dddc{{i}dddddd}iiicic{d}{d}ddcccc{i}{i}icic{{d}iiiiii}ddddc{{i}dddddd}iiiciic{d}{d}dddcccc{i}{i}iciic{{d}iiiiii}dddddc{{i}dddddd}iiiciiic{d}{d}ddddcccc{i}{i}iciiic{{d}iiiiii}ddddddc{{i}dddddd}iiiciiiic{d}{d}dddddcccc{i}{i}iciiiic{{d}iiiii}iiic{{i}dddddd}iiiicddddddc{d}ddddddcccc{i}{i}iicddddddc{{d}iiiiii}iic{{i}dddddd}iiiicdddddc{d}{d}iiicccc{i}{i}iicdddddc{{d}iiiiii}ic{{i}dddddd}iiiicddddc{d}{d}iicccc{i}{i}iicddddc{{d}iiiiii}c{{i}dddddd}iiiicdddc{d}{d}icccc{i}{i}iicdddc{{d}iiiiii}dc{{i}dddddd}iiiicddc{d}{d}cccc{i}{i}iicddc{{d}iiiiii}ddc{{i}dddddd}iiiicdc{d}{d}dcccc{i}{i}iicdc{{d}iiiiii}dddc{{i}dddddd}iiiicc{d}{d}ddcccc{i}{i}iicc{{d}iiiiii}ddddc{{i}dddddd}iiiicic{d}{d}dddcccc{i}{i}iicic{{d}iiiiii}dddddc{{i}dddddd}iiiiciic{d}{d}ddddcccc{i}{i}iiciic{{d}iiiiii}ddddddc{{i}dddddd}iiiiciiic{d}{d}dddddcccc{i}{i}iiciiic{{d}iiiii}iiic{{i}dddddd}iiiiic{d}iiic{d}ddddddcccc{i}{i}iiic{d}iiic{{d}iiiiii}iic{{i}dddddd}iiiiicddddddc{d}{d}iiicccc{i}{i}iiicddddddc{{d}iiiiii}ic{{i}dddddd}iiiiicdddddc{d}{d}iicccc{i}{i}iiicdddddc{{d}iiiiii}c{{i}dddddd}iiiiicddddc{d}{d}icccc{i}{i}iiicddddc{{d}iiiiii}dc{{i}dddddd}iiiiicdddc{d}{d}cccc{i}{i}iiicdddc{{d}iiiiii}ddc{{i}dddddd}iiiiicddc{d}{d}dcccc{i}{i}iiicddc{{d}iiiiii}dddc{{i}dddddd}iiiiicdc{d}{d}ddcccc{i}{i}iiicdc{{d}iiiiii}ddddc{{i}dddddd}iiiiicc{d}{d}dddcccc{i}{i}iiicc{{d}iiiiii}dddddc{{i}dddddd}iiiiicic{d}{d}ddddcccc{i}{i}iiicic{{d}iiiiii}ddddddc{{i}dddddd}iiiiiciic{d}{d}dddddcccc{i}{i}iiiciic{{d}iiiii}iiic{{i}dddddd}iiiiiic{d}iic{d}ddddddcccc{i}{i}iiiic{d}iic{{d}iiiiii}iic{{i}dddddd}iiiiiic{d}iiic{d}{d}iiicccc{i}{i}iiiic{d}iiic{{d}iiiiii}ic{{i}dddddd}iiiiiicddddddc{d}{d}iicccc{i}{i}iiiicddddddc{{d}iiiiii}c{{i}dddddd}iiiiiicdddddc{d}{d}icccc{i}{i}iiiicdddddc{{d}iiiiii}dc{{i}dddddd}iiiiiicddddc{d}{d}cccc{i}{i}iiiicddddc{{d}iiiiii}ddc{{i}dddddd}iiiiiicdddc{d}{d}dcccc{i}{i}iiiicdddc{{d}iiiiii}dddc{{i}dddddd}iiiiiicddc{d}{d}ddcccc{i}{i}iiiicddc{{d}iiiiii}ddddc{{i}dddddd}iiiiiicdc{d}{d}dddcccc{i}{i}iiiicdc{{d}iiiiii}dddddc{{i}dddddd}iiiiiicc{d}{d}ddddcccc{i}{i}iiiicc{{d}iiiiii}ddddddc{{i}dddddd}iiiiiicic{d}{d}dddddcccc{i}{i}iiiicic{{d}iiiii}iiic{{i}ddddd}dddc{d}ic{d}ddddddcccc{i}{i}iiiiic{d}ic{{d}iiiiii}iic{{i}ddddd}dddc{d}iic{d}{d}iiicccc{i}{i}iiiiic{d}iic{{d}iiiiii}ic{{i}ddddd}dddc{d}iiic{d}{d}iicccc{i}{i}iiiiic{d}iiic{{d}iiiiii}c{{i}ddddd}dddcddddddc{d}{d}icccc{i}{i}iiiiicddddddc{{d}iiiiii}dc{{i}ddddd}dddcdddddc{d}{d}cccc{i}{i}iiiiicdddddc{{d}iiiiii}ddc{{i}ddddd}dddcddddc{d}{d}dcccc{i}{i}iiiiicddddc{{d}iiiiii}dddc{{i}ddddd}dddcdddc{d}{d}ddcccc{i}{i}iiiiicdddc{{d}iiiiii}ddddc{{i}ddddd}dddcddc{d}{d}dddcccc{i}{i}iiiiicddc{{d}iiiiii}dddddc{{i}ddddd}dddcdc{d}{d}ddddcccc{i}{i}iiiiicdc{{d}iiiiii}ddddddc{{i}ddddd}dddcc{d}{d}dddddcccc{i}{i}iiiiicc{{d}iiiii}iiic{{i}dddddd}dcdcc{d}ddddddccc{i}{i}dddcdcc{{d}iiiiii}iic{{i}dddddd}dcdcic{d}{d}iiiccc{i}{i}dddcdcic{{d}iiiiii}ic{{i}dddddd}dcdciic{d}{d}iiccc{i}{i}dddcdciic{{d}iiiiii}c{{i}dddddd}dcdciiic{d}{d}iccc{i}{i}dddcdciiic{{d}iiiiii}dc{{i}dddddd}dcdciiiic{d}{d}ccc{i}{i}dddcdciiiic{{d}iiiiii}ddc{{i}dddddd}dcdciiiiic{d}{d}dccc{i}{i}dddcdciiiiic{{d}iiiiii}dddc{{i}dddddd}dcdciiiiiic{d}{d}ddccc{i}{i}dddcdciiiiiic{{d}iiiiii}ddddc{{i}dddddd}dcdc{i}dddc{d}{d}dddccc{i}{i}dddcdc{i}dddc{{d}iiiiii}dddddc{{i}dddddd}dcdc{i}ddc{d}{d}ddddccc{i}{i}dddcdc{i}ddc{{d}iiiiii}ddddddc{{i}dddddd}dcdc{i}dc{d}{d}dddddccc{i}{i}dddcdc{i}dc{{d}iiiii}iiic{{i}dddddd}dccdc{d}ddddddccc{i}{i}dddccdc{{d}iiiiii}iic{{i}dddddd}dccc{d}{d}iiiccc{i}{i}dddccc{{d}iiiiii}ic{{i}dddddd}dccic{d}{d}iiccc{i}{i}dddccic{{d}iiiiii}c{{i}dddddd}dcciic{d}{d}iccc{i}{i}dddcciic{{d}iiiiii}dc{{i}dddddd}dcciiic{d}{d}ccc{i}{i}dddcciiic{{d}iiiiii}ddc{{i}dddddd}dcciiiic{d}{d}dccc{i}{i}dddcciiiic{{d}iiiiii}dddc{{i}dddddd}dcciiiiic{d}{d}ddccc{i}{i}dddcciiiiic{{d}iiiiii}ddddc{{i}dddddd}dcciiiiiic{d}{d}dddccc{i}{i}dddcciiiiiic{{d}iiiiii}dddddc{{i}dddddd}dcc{i}dddc{d}{d}ddddccc{i}{i}dddcc{i}dddc{{d}iiiiii}ddddddc{{i}dddddd}dcc{i}ddc{d}{d}dddddccc{i}{i}dddcc{i}ddc{{d}iiiii}iiic{{i}dddddd}dcicddc{d}ddddddccc{i}{i}dddcicddc{{d}iiiiii}iic{{i}dddddd}dcicdc{d}{d}iiiccc{i}{i}dddcicdc{{d}iiiiii}ic{{i}dddddd}dcicc{d}{d}iiccc{i}{i}dddcicc{{d}iiiiii}c{{i}dddddd}dcicic{d}{d}iccc{i}{i}dddcicic{{d}iiiiii}dc{{i}dddddd}dciciic{d}{d}ccc{i}{i}dddciciic{{d}iiiiii}ddc{{i}dddddd}dciciiic{d}{d}dccc{i}{i}dddciciiic{{d}iiiiii}dddc{{i}dddddd}dciciiiic{d}{d}ddccc{i}{i}dddciciiiic{{d}iiiiii}ddddc{{i}dddddd}dciciiiiic{d}{d}dddccc{i}{i}dddciciiiiic{{d}iiiiii}dddddc{{i}dddddd}dciciiiiiic{d}{d}ddddccc{i}iiiciiiiciciiiiiic{{d}iiiiii}ddddddc{{i}dddddd}dcic{i}dddc{d}{d}dddddccc{i}iiiciiiiciciiiiic{{d}iiiiii}dddddc{{i}dddddd}dciicdddc{d}ddddddccc{i}iiiciiiiciciiiic{{d}iiiiii}ddddc{{i}dddddd}dciicddc{d}{d}iiiccc{i}iiiciiiiciciiic{{d}iiiiii}dddc{{i}dddddd}dciicdc{d}{d}iiccc{i}iiiciiiiciciic{{d}iiiiii}ddc{{i}dddddd}dciicc{d}{d}iccc{i}iiiciiiicicic{{d}iiiiii}dc{{i}dddddd}dciicic{d}{d}ccc{i}iiiciiiicicc{{d}iiiiii}c{{i}dddddd}dciiciic{d}{d}dccc{i}iiiciiiicicdc{{d}iiiiii}ic{{i}dddddd}dciiciiic{d}{d}ddccc{i}iiiciiiicicddc{{d}iiiiii}iic{{i}dddddd}dciiciiiic{d}{d}dddccc{i}iiiciiiicc{i}ddc{{d}iiiii}iiic{{i}dddddd}dciiciiiiic{d}{d}ddddccc{i}iiiciiiicc{i}dddc{{d}iiiiii}ddddddc{{i}dddddd}dciiciiiiiic{d}{d}dddddccc{i}iiiciiiicciiiiiic{{d}iiiiii}dddddc{{i}dddddd}dciiicddddc{d}ddddddccc{i}iiiciiiicciiiiic{{d}iiiiii}ddddc{{i}dddddd}dciiicdddc{d}{d}iiiccc{i}iiiciiiicciiiic{{d}iiiiii}dddc{{i}dddddd}dciiicddc{d}{d}iiccc{i}iiiciiiicciiic{{d}iiiiii}ddc{{i}dddddd}dciiicdc{d}{d}iccc{i}iiiciiiicciic{{d}iiiiii}dc{{i}dddddd}dciiicc{d}{d}ccc{i}iiiciiiiccic{{d}iiiiii}c{{i}dddddd}dciiicic{d}{d}dccc{i}iiiciiiiccc{{d}iiiiii}ic{{i}dddddd}dciiiciic{d}{d}ddccc{i}iiiciiiiccdc{{d}iiiiii}iic{{i}dddddd}dciiiciiic{d}{d}dddccc{i}iiiciiiicdc{i}dc{{d}iiiii}iiic{{i}dddddd}dciiiciiiic{d}{d}ddddccc{i}iiiciiiicdc{i}ddc{{d}iiiiii}ddddddc{{i}dddddd}dciiiciiiiic{d}{d}dddddccc{i}iiiciiiicdc{i}dddc{{d}iiiiii}dddddc{{i}dddddd}dciiiicdddddc{d}ddddddccc{i}iiiciiiicdciiiiiic{{d}iiiiii}ddddc{{i}dddddd}dciiiicddddc{d}{d}iiiccc{i}iiiciiiicdciiiiic{{d}iiiiii}dddc{{i}dddddd}dciiiicdddc{d}{d}iiccc{i}iiiciiiicdciiiic{{d}iiiiii}ddc{{i}dddddd}dciiiicddc{d}{d}iccc{i}iiiciiiicdciiic{{d}iiiiii}dc{{i}dddddd}dciiiicdc{d}{d}ccc{i}iiiciiiicdciic{{d}iiiiii}c{{i}dddddd}dciiiicc{d}{d}dccc{i}iiiciiiicdcic{{d}iiiiii}ic{{i}dddddd}dciiiicic{d}{d}ddccc{i}iiiciiiicdcc{{d}iiiiii}iic{{i}dddddd}dciiiiciic{d}{d}dddccc{i}iiic{i}iicc{{d}iiiii}iiic{{i}dddddd}dciiiiciiic{d}{d}ddddccc{i}iiic{i}iicdc{{d}iiiiii}ddddddc{{i}dddddd}dciiiiciiiic{d}{d}dddddccc{i}iiic{i}iicddc{{d}iiiiii}dddddc{{i}dddddd}dciiiiicddddddc{d}ddddddccc{i}iiic{i}iicdddc{{d}iiiiii}ddddc{{i}dddddd}dciiiiicdddddc{d}{d}iiiccc{i}iiic{i}iicddddc{{d}iiiiii}dddc{{i}dddddd}dciiiiicddddc{d}{d}iiccc{i}iiic{i}iicdddddc{{d}iiiiii}ddc{{i}dddddd}dciiiiicdddc{d}{d}iccc{i}iiic{i}iicddddddc{{d}iiiiii}dc{{i}dddddd}dciiiiicddc{d}{d}ccc{i}iiic{i}iic{d}iiic{{d}iiiiii}c{{i}dddddd}dciiiiicdc{d}{d}dccc{i}iiic{i}iic{d}iic{{d}iiiiii}ic{{i}dddddd}dciiiiicc{d}{d}ddccc{i}iiic{i}iic{d}ic{{d}iiiiii}iic{{i}dddddd}dciiiiicic{d}{d}dddccc{i}iiic{i}icic{{d}iiiii}iiic{{i}dddddd}dciiiiiciic{d}{d}ddddccc{i}iiic{i}icc{{d}iiiiii}ddddddc{{i}dddddd}dciiiiiciiic{d}{d}dddddccc{i}iiic{i}icdc{{d}iiiiii}dddddc{{i}dddddd}dciiiiiic{d}iiic{d}ddddddccc{i}iiic{i}icddc{{d}iiiiii}ddddc{{i}dddddd}dciiiiiicddddddc{d}{d}iiiccc{i}iiic{i}icdddc{{d}iiiiii}dddc{{i}dddddd}dciiiiiicdddddc{d}{d}iiccc{i}iiic{i}icddddc{{d}iiiiii}ddc{{i}dddddd}dciiiiiicddddc{d}{d}iccc{i}iiic{i}icdddddc{{d}iiiiii}dc{{i}dddddd}dciiiiiicdddc{d}{d}ccc{i}iiic{i}icddddddc{{d}iiiiii}c{{i}dddddd}dciiiiiicddc{d}{d}dccc{i}iiic{i}ic{d}iiic{{d}iiiiii}ic{{i}dddddd}dciiiiiicdc{d}{d}ddccc{i}iiic{i}ic{d}iic{{d}iiiiii}iic{{i}dddddd}dciiiiiicc{d}{d}dddccc{i}iiic{i}ciic{{d}iiiii}iiic{{i}dddddd}dciiiiiicic{d}{d}ddddccc{i}iiic{i}cic{{d}iiiiii}ddddddc{{i}dddddd}dciiiiiiciic{d}{d}dddddccc{i}iiic{i}cc{{d}iiiiii}dddddc{{i}dddddd}dc{i}dddc{d}iic{d}ddddddccc{i}iiic{i}cdc{{d}iiiiii}ddddc{{i}dddddd}dc{i}dddc{d}iiic{d}{d}iiiccc{i}iiic{i}cddc{{d}iiiiii}dddc{{i}dddddd}dc{i}dddcddddddc{d}{d}iiccc{i}iiic{i}cdddc{{d}iiiiii}ddc{{i}dddddd}dc{i}dddcdddddc{d}{d}iccc{i}iiic{i}cddddc{{d}iiiiii}dc{{i}dddddd}dc{i}dddcddddc{d}{d}ccc{i}iiic{i}cdddddc{{d}iiiiii}c{{i}dddddd}dc{i}dddcdddc{d}{d}dccc{i}iiic{i}cddddddc{{d}iiiiii}ic{{i}dddddd}dc{i}dddcddc{d}{d}ddccc{i}iiic{i}c{d}iiic{{d}iiiiii}iic{{i}dddddd}dc{i}dddcdc{d}{d}dddccc{i}iiic{i}dciiic{{d}iiiii}iiic{{i}dddddd}dc{i}dddcc{d}{d}ddddccc{i}iiic{i}dciic{{d}iiiiii}ddddddc{{i}dddddd}dc{i}dddcic{d}{d}dddddccc{i}iiic{i}dcic{{d}iiiiii}dddddc{{i}dddddd}dc{i}ddc{d}ic{d}ddddddccc{i}iiic{i}dcc{{d}iiiiii}ddddc{{i}dddddd}dc{i}ddc{d}iic{d}{d}iiiccc{i}iiic{i}dcdc{{d}iiiiii}dddc{{i}dddddd}dc{i}ddc{d}iiic{d}{d}iiccc{i}iiic{i}dcddc{{d}iiiiii}ddc{{i}dddddd}dc{i}ddcddddddc{d}{d}iccc{i}iiic{i}dcdddc{{d}iiiiii}dc{{i}dddddd}dc{i}ddcdddddc{d}{d}ccc{i}iiic{i}dcddddc{{d}iiiiii}c{{i}dddddd}dc{i}ddcddddc{d}{d}dccc{i}iiic{i}dcdddddc{{d}iiiiii}ic{{i}dddddd}dc{i}ddcdddc{d}{d}ddccc{i}iiic{i}dcddddddc{{d}iiiiii}iic{{i}dddddd}dc{i}ddcddc{d}{d}dddccc{i}iiic{i}ddciiiic{{d}iiiii}iiic{{i}dddddd}dc{i}ddcdc{d}{d}ddddccc{i}iiic{i}ddciiic{{d}iiiiii}ddddddc{{i}dddddd}dc{i}ddcc{d}{d}dddddccc{i}iiic{i}ddciic{{d}iiiiii}dddddc{{i}dddddd}cddcc{d}ddddddccc{i}iiic{i}ddcic{{d}iiiiii}ddddc{{i}dddddd}cddcic{d}{d}iiiccc{i}iiic{i}ddcc{{d}iiiiii}dddc{{i}dddddd}cddciic{d}{d}iiccc{i}iiic{i}ddcdc{{d}iiiiii}ddc{{i}dddddd}cddciiic{d}{d}iccc{i}iiic{i}ddcddc{{d}iiiiii}dc{{i}dddddd}cddciiiic{d}{d}ccc{i}iiic{i}ddcdddc{{d}iiiiii}c{{i}dddddd}cddciiiiic{d}{d}dccc{i}iiic{i}ddcddddc{{d}iiiiii}ic{{i}dddddd}cddciiiiiic{d}{d}ddccc{i}iiic{i}ddcdddddc{{d}iiiiii}iic{{i}dddddd}cddc{i}dddc{d}{d}dddccc{i}iiic{i}dddciiiiic{{d}iiiii}iiic{{i}dddddd}cddc{i}ddc{d}{d}ddddccc{i}iiic{i}dddciiiic{{d}iiiiii}ddddddc{{i}dddddd}cddc{i}dc{d}{d}dddddccc{i}iiic{i}dddciiic{{d}iiiiii}dddddc{{i}dddddd}cdcdc{d}ddddddccc{i}iiic{i}dddciic{{d}iiiiii}ddddc{{i}dddddd}cdcc{d}{d}iiiccc{i}iiic{i}dddcic{{d}iiiiii}dddc{{i}dddddd}cdcic{d}{d}iiccc{i}iiic{i}dddcc{{d}iiiiii}ddc{{i}dddddd}cdciic{d}{d}iccc{i}iiic{i}dddcdc{{d}iiiiii}dc{{i}dddddd}cdciiic{d}{d}ccc{i}iiic{i}dddcddc{{d}iiiiii}c{{i}dddddd}cdciiiic{d}{d}dccc{i}iiic{i}dddcdddc{{d}iiiiii}ic{{i}dddddd}cdciiiiic{d}{d}ddccc{i}iiic{i}dddcddddc{{d}iiiiii}iic{{i}dddddd}cdciiiiiic{d}{d}dddccc{i}iiiciiiiiiciiiiiic{{d}iiiii}iiic{{i}dddddd}cdc{i}dddc{d}{d}ddddccc{i}iiiciiiiiiciiiiic{{d}iiiiii}ddddddc{{i}dddddd}cdc{i}ddc{d}{d}dddddccc{i}iiiciiiiiiciiiic{{d}iiiiii}dddddc{{i}dddddd}ccddc{d}ddddddccc{i}iiiciiiiiiciiic{{d}iiiiii}ddddc{{i}dddddd}ccdc{d}{d}iiiccc{i}iiiciiiiiiciic{{d}iiiiii}dddc{{i}dddddd}ccc{d}{d}iiccc{i}iiiciiiiiicic{{d}iiiiii}ddc{{i}dddddd}ccic{d}{d}iccc{i}iiiciiiiiicc{{d}iiiiii}dc{{i}dddddd}cciic{d}{d}ccc{i}iiiciiiiiicdc{{d}iiiiii}c{{i}dddddd}cciiic{d}{d}dccc{i}iiiciiiiiicddc{{d}iiiiii}ic{{i}dddddd}cciiiic{d}{d}ddccc{i}iiiciiiiiicdddc{{d}iiiiii}iic{{i}dddddd}cciiiiic{d}{d}dddccc{i}iiiciiiiic{i}dddc{{d}iiiii}iiic{{i}dddddd}cciiiiiic{d}{d}ddddccc{i}iiiciiiiiciiiiiic{{d}iiiiii}ddddddc{{i}dddddd}cc{i}dddc{d}{d}dddddccc{i}iiiciiiiiciiiiic{{d}iiiiii}dddddc{{i}dddddd}cicdddc{d}ddddddccc{i}iiiciiiiiciiiic{{d}iiiiii}ddddc{{i}dddddd}cicddc{d}{d}iiiccc{i}iiiciiiiiciiic{{d}iiiiii}dddc{{i}dddddd}cicdc{d}{d}iiccc{i}iiiciiiiiciic{{d}iiiiii}ddc{{i}dddddd}cicc{d}{d}iccc{i}iiiciiiiicic{{d}iiiiii}dc{{i}dddddd}cicic{d}{d}ccc{i}iiiciiiiicc{{d}iiiiii}c{{i}dddddd}ciciic{d}{d}dccc{i}iiiciiiiicdc{{d}iiiiii}ic{{i}dddddd}ciciiic{d}{d}ddccc{i}iiiciiiiicddc{{d}iiiiii}iic{{i}dddddd}ciciiiic{d}{d}dddccc{i}iiiciiiic{i}ddc{{d}iiiii}iiic{{i}dddddd}ciciiiiic{d}{d}ddddccc{i}iiiciiiic{i}dddc{{d}iiiiii}ddddddc{{i}dddddd}ciciiiiiic{d}{d}dddddccc{i}iiiciiiiciiiiiic{{d}iiiiii}dddddc{{i}dddddd}ciicddddc{d}ddddddccc{i}iiiciiiiciiiiic{{d}iiiiii}ddddc{{i}dddddd}ciicdddc{d}{d}iiiccc{i}iiiciiiiciiiic{{d}iiiiii}dddc{{i}dddddd}ciicddc{d}{d}iiccc{i}iiiciiiiciiic{{d}iiiiii}ddc{{i}dddddd}ciicdc{d}{d}iccc{i}iiiciiiiciic{{d}iiiiii}dc{{i}dddddd}ciicc{d}{d}ccc{i}iiiciiiicic{{d}iiiiii}c{{i}dddddd}ciicic{d}{d}dccc{i}iiiciiiicc{{d}iiiiii}ic{{i}dddddd}ciiciic{d}{d}ddccc{i}iiiciiiicdc{{d}iiiiii}iic{{i}dddddd}ciiciiic{d}{d}dddccc{i}iiic{i}iic{{d}iiiii}iiic{{i}dddddd}ciiciiiic{d}{d}ddddccc{i}iiic{i}ic{{d}iiiiii}ddddddc{{i}dddddd}ciiciiiiic{d}{d}dddddccc{i}iiic{i}c{{d}iiiiii}dddddc{{i}dddddd}ciiicdddddc{d}ddddddccc{i}iiic{i}dc{{d}iiiiii}ddddc{{i}dddddd}ciiicddddc{d}{d}iiiccc{i}iiic{i}ddc{{d}iiiiii}dddc{{i}dddddd}ciiicdddc{d}{d}iiccc{i}iiic{i}dddc{{d}iiiiii}ddc{{i}dddddd}ciiicddc{d}{d}iccc{i}iiiciiiiiic{{d}iiiiii}dc{{i}dddddd}ciiicdc{d}{d}ccc{i}iiiciiiiic{{d}iiiiii}c{{i}dddddd}ciiicc{d}{d}dccc{i}iiiciiiic

```
> 1 votes

---
Tags: code-golf, kolmogorov-complexity, integer
---


title: Reduce a number by its largest digit

text:
# Question
Title: Reduce a number by its largest digit
# Task:

**Given an integer number in decimal number system, reduce it to a single decimal digit as follows:**

1. Convert the number to a list of decimal digits.
2. Find the largest digit, D
3. Remove D from the list. If there is more than one occurrence of D, choose the first from the left (at the most significant position), all others should remain intact.
4. Convert the resulting list to a decimal number and multiply it by D.
5. If the number is bigger than 9 (has more than 1 decimal digit), repeat the whole procedure, feeding the result into it. Stop when you get a single-digit result.
6. Display the result.

Example:

```
26364 ->
1. 2 6 3 6 4
2. The largest digit is 6, so D=6
3. There are two occurrences or 6: at positions 1 and 3 (0-based). We remove the left one,
    at position 1 and get the list 2 3 6 4
4. we convert the list 2 3 6 4 to 2364 and multiply it by D:
   2364 * 6 = 14184
5. 14184 is greater than 9 so we repeat the procedure, feeding 14184 into it.

```

We continue by repeating the procedure for 14184 and so on and we go through the following intermediate results, finally reaching 8:

```
11312
3336
1998
1782
1376
952
468
368
288
224
88
64
24
8

```

So the result for 26364 is 8.

**Input:** An integer / a string representing an integer

**Output:** A single digit, the result of the reduction applied to the number.

**Test cases:**

```
9 -> 9
27 -> 4
757 -> 5
1234 -> 8
26364 -> 8
432969 -> 0
1234584 -> 8
91273716 -> 6

```

This is , so the shortest answers in bytes in each language win.

# Answer
> 18 votes
# 05AB1E, 6 bytes

### Code:

```
[Dg#à*

```

Uses the **05AB1E** encoding. Try it online!

### Explanation

```
[Dg#     # While the length of the number is not 1
    à    # Extract the largest element from the current number
     *   # Multiply it with the leftover number

```

# Answer
> 11 votes
# JavaScript (ES6), 49 bytes

```
f=n=>n>9?f(""+n.replace(m=Math.max(...n),"")*m):n

```

Takes input as a string representation of an integer, like `f("26364")`.

## Test Cases

```
f=n=>n>9?f(""+n.replace(m=Math.max(...n),"")*m):n

;["9", "27", "757", "1234", "26364", "432969", "1234584", "91273716"]
.forEach(num => console.log(num + " -> " + f(num)))
```

```
.as-console-wrapper{max-height:100%!important}
```

# Answer
> 8 votes
# Jelly, 13 bytes

```
œṡṀẎḌ×ṀD
DÇḊ¿

```

Try it online!

-1 thanks to a trick I found in Jonathan Allan's answer.

Full program.

# Answer
> 6 votes
# Pyth, 16 bytes

```
.WtH`*s.-ZKeSZsK

```

Takes input as a String. **Try it here!** (Alternative: `.WtH`*s.-ZeSZseS`)

# Pyth, 18 bytes

```
.WgHT*s.-`ZKeS`ZsK

```

Takes input as an integer. **Try it here!**

### How it works

**16-byter**

```
.WtH`*s.-ZKeSZsK ~ Full program.

.W               ~ Functional while. While A(value) is truthy, value = B(value).
                 ~ The final value is returned.
  tH             ~ A, condition: Is value[1:] truthy?  Is the length ≥ 2?
    `*s.-ZKeSZsK ~ B, setter.
       .-        ~ Bagwise subtraction, used for removing the highest digit, with...
         Z       ~ The current value Z, and...
          KeSZ   ~ The highest digit of Z (as a String). Also assigns to a variable K.
      s          ~ Casted to an integer.
     *           ~ Multiplied by...
              sK ~ The highest digit.
    `            ~ Convert to a String.

```

**18-byter**

```
.WgHT*s.-`ZKeS`ZsK ~ Full program.

.W                 ~ Functional while. While A(value) is truthy, value = B(value).
                   ~ The final value is returned.
  gHT              ~ A, condition: is value (H) ≥ 10?
     *s.-`ZKeS`ZsK ~ B, setter.
       .-          ~ Bagwise substraction (used for removing first occurrence).
         `Z        ~ The string representation of Z.
           KeS`Z   ~ And the highest (lexicographically) character of Z (highest digit).
                     It also assigns it to a variable called K.
      s            ~ Cast to integer.
     *             ~ Multiply by...
                sK ~ K casted to int.

```

Being *that close* to Jelly at such type of challenge is very good for Pyth IMO :-)

# Answer
> 6 votes
# Husk, ~~14~~ ~~13~~ 12 bytes

Thanks Zgarb for saving 1 byte.

```
Ω≤9oṠS*od-▲d

```

Try it online!

### Explanation:

```
Ω≤9            Repeat the following function until the result is ≤ 9
           d     Convert to a list of digits
         -▲      Remove the largest one
       od        Convert back to an integer
   oṠS*          Multiply by the maximum digit

```

# Answer
> 6 votes
# , ~~99~~ 95 bytes

```
f=function(x)"if"(n<-nchar(x)-1,f(10^(n:1-1)%*%(d=x%/%10^(n:0)%%10)[-(M=which.max(d))]*d[M]),x)

```

Try it online!

A recursive function. Adding `f(number)` in the footer can be used to test for other values of `number`. Straightforward implementation, `d` is the list of digits, and `10^(n:2-2)%*%d[-M]` computes the number with the largest digit removed.

# Answer
> 5 votes
# Python 2, 72 bytes

```
f=lambda n:`n`*(n<=9)or f(int(`n`.replace(max(`n`),'',1))*int(max(`n`)))

```

**Try it online!**

# Answer
> 5 votes
# Ruby, 59 bytes

```
f=->n{m=n.digits.max;n>9?f[n.to_s.sub(m.to_s,"").to_i*m]:n}

```

Try it online!

Recursive lambda function called like `f[26364]`.

# Answer
> 4 votes
# Jelly, 15 bytes

```
D×Ṁ$œṡṀ$FḌµ>9µ¿

```

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

### How?

```
D×Ṁ$œṡṀ$FḌµ>9µ¿ - Link: number, n
              ¿ - while:
             µ  - ...condition (monadic):
            9   -    literal 9
           >    -    loop value greater than (9)?
          µ     - ...do (monadic):               e.g. 432969
D               -    convert to a decimal list        [4,3,2,9,6,9]
   $            -    last two links as a monad:
  Ṁ             -      maximum                         9
 ×              -      multiply (vectorises)          [36,27,18,81,54,81]
       $        -    last two links as a monad:
      Ṁ         -      maximum                         81
    œṡ          -      split at first occurrence      [[36,27,18],[54,81]]
        F       -    flatten                          [36,27,18,54,81]
         Ḍ      -    convert from base 10              389421  (i.e. 360000 + 27000 + 1800 + 540 + 81)

```

# Answer
> 4 votes
# Haskell, ~~70~~ ~~67~~ 66 bytes

Saved ~~3~~ 4 bytes thanks to nimi!

```
f x|x<10=x|(a,b:c)<-span=<<(>).maximum$show x=f$read[b]*read(a++c)

```

Try it online!

# Answer
> 4 votes
# APL (Dyalog), ~~36~~ ~~35~~ 33 bytes

-1 due to updated OP specs. -2 thanks to ngn.

Anonymous tacit prefix function. Takes integer as argument.

```
{⍵>9:∇(⌈/×10⊥⊂⌷⍨¨⍳∘≢~⊢⍳⌈/)⍎¨⍕⍵⋄⍵}

```

Try it online!

`{``}`a function where  is the argument:

`⍵>9:` if the argument is greater than 9, then:

`⍕⍵` format (stringify) the argument

`⍎¨` execute (evaluate) each (this gets us the digits as numbers)

`(``)` apply the following tacit function on those

`⌈/` the largest digit

`×` times

`10⊥` the base-10 decoding of (collects digits)

all the digits

`⌷⍨¨` indexed by each of

`⍳∘≢` the **i**ndices of the number of digits

differs from

`⊢⍳⌈/` the largest digit's **i**ndex in the entire list of digits

recurse (i.e. call self) on that

else

return the argument unmodified

# Answer
> 4 votes
# C# (.NET Core), 126 bytes

```
int F(int n){var x=(n+"").ToList();var m=x.Max();x.RemoveAt(x.IndexOf(m));return n>9?F(int.Parse(string.Concat(x))*(m-48)):n;}

```

Try it online!

# Answer
> 3 votes
# Perl 6,  ~~45~~  41 bytes

```
{($_,{$/=.comb.max;S/"$/"//*$/}...10>*).tail}

```

Test it

```
{($_,{S/"{.comb.max}"//*$/}...10>*).tail}

```

Test it

## Expanded:

```
{  # bare block lambda with implicit parameter ｢$_｣

  (  # generate the sequence

      $_,                      # start the sequence with the input

      {                        # generate the rest of the values in the sequence

          S/                   # find and replace (not in-place)
            "{  .comb.max  }"  # find the max digit and match against it
          //                   # replace it with nothing
          *                    # multiply the result with
          $/                   # the digit that was removed
      }

      ...                      # keep generating values until

      10 > *                   # the value is less than 10

  ).tail                       # get the last value from the sequence
}

```

# Answer
> 3 votes
# C# (.NET Core), ~~177~~ 164 + 18 bytes

Saved 13 bytes thanks to @raznagul!

```
int f(int n){string s=n+"",m=s.Max(d=>d)+"";if(n<10)return n;var x=s.ToList();x.RemoveAt(s.IndexOf(m));int y=int.Parse(string.Join("",x))*int.Parse(m);return f(y);}

```

Try it online!

# Answer
> 3 votes
# Retina, 67 bytes

```
{1`(..+)?
1$&;$&
O`\G\d
.+((.);.*?)\2
$1
\d+
$*
1(?=.*;(1+))|.
$1
1

```

Try it online! Link includes the test cases fast enough not to hammer Dennis's server. Explanation:

```
{1`(..+)?
1$&;$&

```

For two digit numbers, this duplicates the number with a `;` separator, prefixing a 1 to the duplicate. For one digit numbers, this prefixes `1;` to the number.

```
O`\G\d

```

Sort the digits of the duplicate. (For one digit numbers, this has no effect.)

```
.+((.);.*?)\2
$1

```

Find the first occurrence of the largest digit, and delete it, and also the other digits in the duplicate, and the extra 1 that was added earlier. (For one digit numbers, the match fails so this does nothing.)

```
\d+
$*
1(?=.*;(1+))|.
$1
1

```

Multiply the number by the digit. For one digit numbers, this results in the original number, and the loop terminates. Otherwise, the program loops until a single digit is reached.

# Answer
> 3 votes
# C ~~103~~ , ~~95~~ , 90 bytes

```
a,b;t,m;f(n){for(t=m=0,a=b=1e9;a/=10;)if((t=n/a%10)>m)m=t,b=a;n=n>9?f(m*=n/b/10*b+n%b):n;}

```

Try it online!

# Answer
> 3 votes
# Java 8, ~~126~~ 104 bytes

```
n->{for(;n>9;n=new Long((n+"").replaceFirst((n=(n+"").chars().max().getAsInt()-48)+"",""))*n);return n;}

```

-22 bytes thanks to *@OlivierGrégoire*.

**Explanation:**

Try it here.

```
n->{         // Method with long as both parameter and return-type
  for(;n>9;  //  Loop as long as the number contains more than 1 digit
    n=       //   Replace the current number with:
      new Long((n+"").replaceFirst((n=(n+"").chars().max().getAsInt()-48)+"",""))
             //    Remove the first largest digit from the number,
      *n     //    and multiply this new number with the removed digit
  );         //  End of loop
  return n;  //  Return the result
}            // End of method

```

# Answer
> 3 votes
# PowerShell, 123 bytes

```
[Collections.ArrayList]$a=[char[]]"$args"
while(9-lt-join$a){$a.remove(($b=($a|sort)[-1]));$a=[char[]]"$(+"$b"*-join$a)"}$a

```

Try it online!

Ooof. PowerShell arrays are immutable, so we need to use the lengthy `[Collections.ArrayList]` casting here so we can call `.remove()` later.

Takes input `$args`, converts it to a string, then a `char`-array, then an `ArrayList`. Stores that into `$a`. Then we `while` loop until we're at or below `9`. Each iteration, we're calling `.remove` on the largest element of `$a` (done by `sort` and taking the last element `[-1]`), storing the largest element into `$b` at the same time. This happens to work because the ASCII values sort in the same fashion as the literal digits.

Next, we recompute `$a`, again as an `char`-array (and `ArrayList` implicitly), by casting our `$b` (which is currently a `char`) to a string, then an int with `+`, and multiplying that to `$a` `-join`ed into a string (implicitly cast to int). This satisfies the "multiply by D" portion of the challenge.

Finally, once we're out of the loop, we put `$a` onto the pipeline and output is implicit.

# Answer
> 3 votes
# Java 8: 115 bytes

-10 bytes thanks to Jo King
Unfortunately you can't call a lambda function recursively, so an extra 11 bytes is needed for the method header. I am aware there is a shorter Java answer that loops instead, but I decided to come up with this on my own.

```
long f(long n){int m=(n+"").chars().max().getAsInt()-48;return n>9?f(new Long((n+"").replaceFirst(""+m,""))*m):n;};

```

Try it online

# Answer
> 2 votes
# Jq 1.5, 86 bytes

```
until(.<10;"\(.)"|(./""|max)as$v|index($v)as$x|.[:$x]+.[1+$x:]|tonumber*($v|tonumber))

```

Expanded

```
until(
    .<10                    # until number is below 10
  ; "\(.)"                  # convert to string
  | (./""|max) as $v        # find largest digit, call it $v
  | index($v) as $x         # find index of digit
  | .[:$x]+.[1+$x:]         # remove digit
  | tonumber*($v|tonumber)  # convert back to number and multiply by $v
)

```

Try it online!

# Answer
> 2 votes
# Perl 5, 41 + 1 (`-p`) = 42 bytes

```
$m=(sort/./g)[-1];s/$m//;($_*=$m)>9&&redo

```

Try it online!

# Answer
> 2 votes
# Lua, ~~137~~ 108 bytes

```
function f(n)while n>9 do b="0"g=b.gsub g(n,".",function(m)b=math.max(m,b)end)n=b*g(n,b,"",1)end print(n)end

```

Thanks to Jonathan S for golfing off 29 bytes.

Try it online!

# Answer
> 2 votes
# , ~~188~~ ~~186~~ 185 bytes

```
import std.conv,std.algorithm;T f(T,U=string)(T u){if(u<10)return u;T[]r;u.text.each!(n=>r~=n.to!T-48);T m=r.maxElement;U s;r.remove(r.maxIndex).each!(n=>s~=n.to!U);return f(m*s.to!T);}

```

Try it online!

I hate lazy evaluation, so much. Any tips are welcome!

# Answer
> 2 votes
## Lua, 154 Bytes

I should have some ways to golf this down, I'm experimenting right now.

```
n=...z=table
while n+0>9 do
t={}T={}n=n..''n:gsub(".",function(c)t[#t+1]=c T[#T+1]=c
end)z.sort(t)x=t[#t]z.remove(T,n:find(x))n=z.concat(T)*x
end
print(n)

```

Try it online!

### Explanations

```
n=...                    -- define n as a shorthand for the argument
z=table                  -- define z as a pointer to the object table
while n+0>9              -- iterate as long as n is greater than 9
do                       -- n+0 ensure that we're using a number to do the comparison
  t={}                   -- intialise two tables, one is used to find the greatest digit
  T={}                   -- the other one is used to remove it from the string
  n=n..''                -- ensure that n is a string (mandatory after the first loop)
  n:gsub(".",function(c) -- apply an anonymous function to each character in n
               t[#t+1]=c -- fill our tables with the digits
               T[#T+1]=c
             end)
  z.sort(t)              -- sort t to put the greatest digit in the last index
  x=t[#t]                -- intialise x to the value of the greatest digit
  z.remove(T,n:find(x))  -- remove the first occurence of x from the table T
                         -- based on its position in the input string
  n=z.concat(T)*x        -- assign the new value to n
end                      -- if it still isn't a single digit, we're looping over again
print(n)                 -- output the answer

```

# Answer
> 2 votes
# Pip, ~~22~~ 21 bytes

```
Wa>9a:aRAa@?YMXax*:ya

```

Takes input as a command-line argument. Verify all test cases: Try it online!

### Explanation

Ungolfed, with comments:

```
                 a is 1st cmdline arg
W a>9 {          While a > 9:
  Y MXa           Yank max(a) into y
  a RA: a@?y ""   Find index of y in a; replace the character at that position with ""
  a *: y          Multiply a by y
}
a                Autoprint a

```

In the golfed version, the loop body is condensed into a single expression:

```
a:aRAa@?YMXax*:y
        YMXa      Yank max(a)
     a@?          Find its index in a
  aRA       x     Replace at that index with x (preinitialized to "")
             *:y  Multiply that result by y (using : meta-operator to lower the precedence)
a:                Assign back to a

```

# Answer
> 2 votes
# Scala, 121 bytes

```
x=>def g(y:Int):Int={if(y>9){val m=y.toString.max.asDigit;g(y.toString.replaceFirst(m.toString,"").toInt*m)}else y}
g(x)}

```

Try it online!

# Answer
> 2 votes
# pure Bash, 116 112 bytes, or 101, or even 97?

Based on answers from iBug and Léa Gris and tips-for-golfing-in-bash (thanks, @AaronMiller and @BrowncatPrograms!):

```
#!/bin/bash

test112()
{
n=$1;shopt -s extglob;while((n>9));do m=0;for x in ${n//?()/ };{ ((m<x))&&m=$x;};n=$[10#${n/$m/}*m];done;echo $n
}

for k in 9 27 757 1234 26364 432969 1234584 91273716; do printf '%d -> ' "$k"; test112 "$k"; done

```

Try it online!

Also there are two shorter variants:

```
#!/bin/bash

f()(shopt -s extglob;(($1>9))||exit $1;m=0;for x in ${1//?()/ };{ ((m<x))&&m=$x;};f $[10#${1/$m/}*m])

for k in 9 27 757 1234 26364 432969 1234584 91273716; do printf '%d -> ' "$k"; f "$k"; echo "$?"; done

```

(Try it online!) with 101 bytes and with 97 bytes (Try it online!):

```
shopt -s extglob;(($1>9))||exit $1;m=0;for x in ${1//?()/ };{ ((m<x))&&m=$x;};$0 $[10#${1/$m/}*m]

```

But I am not entirely sure the last two apply to the rules. The latter even uses `$0` (I neither found a rule allowing that nor denying this) to recurse to itself, so it only works if put into a script (like `golf.sh`), made executable and then is called like `golf.sh 91273716; echo $?`

Output of the scripts:

```
9 -> 9
27 -> 4
757 -> 5
1234 -> 8
26364 -> 8
432969 -> 0
1234584 -> 8
91273716 -> 6

```

Explained first variant (112 bytes):

```
n=$1;                           # (*) get argument n
shopt -s extglob;               # enable ${n//?()/ } below
while((n>9));do                 # loop until number is <=9
  m=0;                          # preset maximum to 0
  for x in ${n//?()/ };{        # loop over the digits
    ((m<x))&&m=$x;              # find max
  };
  n=$[                          # calculate new number
      10#                       # force base 10 as 0N becomes octal
         ${n/$m/}               # remove first occurance of max
                 *m];           # multiply m
done;
echo $n                         # output result

```

Notes:

* Shebang `#!/bin/bash`+`LF` (12 byte) is not included in the count.
    + We are in `bash`, so this is already the default
* AFAICS passing in the number directly as variable `n` (see marked `(*)` above) is not allowed. Hence these 5 bytes are needed.
    + Else `./golf.sh 1234` would look like `n=1234 ./golf.sh`
    + A `read n;` if number is passed in from STDIN is 2 byte longer
* `shopt -s extglob;` can be left away, if this option is given on commandline
    + Like in `n=1234 bash -Oextglob ./golf.sh`
    + But `extglob` is not set by default, hence AFAICS it must be included in the count
* `10#` is needed as `${n/$m/}` can leave a number with a leading `0`
    + Without the `10#` input `91273716` wrongly returns `8`.

Explained shortest variant (97 bytes):

```
shopt -s extglob;                           # see above
(($1>9))||exit $1;                          # stop if goal reached
m=0;for x in ${1//?()/ };{ ((m<x))&&m=$x;}; # max calc, as above
$0 $[10#${1/$m/}*m]                         # recurse to next step

```

Notes:

* Actually the last line is a tail recursion, so bash uses `exec` and does not `fork`

# Answer
> 1 votes
# J, 40 bytes

```
((]*<^:3@i.{[)>./)&.(10&#.inv)^:(9&<)^:_

```

Try it online!

## explanation

```
(      iterate                   )^:(9&<)^:_    NB. keep iterating while the number is > 9
 (     stuff         )&.(10&#.inv)              NB. convert to digits, do stuff, convert back to number
 (           )>./)                              NB. stuff is a hook, with max digit >./  on the right
 (]*<^:3@i.{[)                                  NB. so that in this phrase, ] means "max" and [ means "all digits"
  ]                                             NB. the max digit...
   *                                            NB. times...
    <^:3@                                       NB. triple box...
         i.                                     NB. the first index of the max in the list of all digits
           {                                    NB. "from" -- which because of the triple box means "take all indexes except..."
            [                                   NB. from all the digits of the number

```

# Answer
> 1 votes
# PowerShell, 230 bytes

```
$n="$args";do{$n=$n.ToString();$a=@();0..$n.Length|%{$a+=$n[$_]};$g=[convert]::ToInt32(($a|sort|select -last 1),10);[regex]$p=$g.ToString();[int]$s=$p.replace($n,'',1);if($n.Length-eq1){$n;exit}else{$r=$s*$g}$n=$r}until($r-lt10)$r

```

Try it online!

Wasted too much on all the type casting.

# Answer
> 1 votes
# Kotlin, 109 bytes

```
fun f(n:Int):Int{return if(n>9){val m=(""+n).max()!!;f((""+n).replaceFirst(""+m,"").toInt()*(m-'0'))}else n}

```

# Answer
> 1 votes
# Bash, 80 bytes

Uses packages Core Utilities (for `sort` and `tail`) and `grep`.

```
while((n>9));do m=$(grep -o .<<<$n|sort|tail -n1);n=$((${n/$m/}*m));done;echo $n

```

How does it work?

```
while (( n > 9 )); do  # C-style loop conditional
    grep -o .          # Separate the string into one char per line
              <<< $n   # Use the content of variable `n` as its stdin
    | sort             # Pipe to `sort`, which sorts strings by line
    | tail -n 1        # Take the last line

m=$(                 ) # Assign the output of the command chain to `m`
n=$((          ))      # Assign the result of the evaluation to n
     ${n/$m/}          # Replace the first occurrence of $m with empty
             *m        # ... and multiply it by the value of `m`
done; echo $n          # After loop, print the value of `n`

```

# Answer
> 1 votes
# PHP, ~~82~~ 77+1 bytes

```
for($n=$argn;$n>9;)$n=join("",explode($d=max(str_split($n)),$n,2))*$d;echo$n;

```

Run as pipe with `-nR` or try it online.

# Answer
> 1 votes
# dc, ~~98~~ 85 bytes

```
?dsj[0dsosclj[soIlc^sr0]sn[I~dlo!>nrlc1+scd0<i]dsixljdlr%rlrI*/lr*+lo*dsj9<T]sT9<Tljp

```

*Many thanks to this answer for the idea of utilizing `~` in the extraction of digits from a number, resulting in two saved bytes over the original version of the code.*

This was a rather though one to complete in `dc` with its nonexistent string manipulation capabilities.

Try it online!

# Answer
> 1 votes
# APL NARS ~~42~~ ~~40~~ 36 chars

```
{⍵≤9:⍵⋄∇h⌷v×10⊥v[(⍳⍴v)∼h←1⌷⍒v←⍎¨⍕⍵]}

```

some test, I copied the trick ⍎¨⍕ from Adam solution

```
g←{⍵≤9:⍵⋄∇h⌷v×10⊥v[(⍳⍴v)∼h←1⌷⍒v←⍎¨⍕⍵]}

  g¨9 27 757 1234 26364 432969 1234584 91273716
9 4 5 8 8 0 8 6

{⍵≤9:⍵   if ⍵≤9 return ⍵
 ∇h⌷v×10⊥v[(⍳⍴v)∼h←1⌷⍒v←⍎¨⍕⍵]
                      v←⍎¨⍕⍵] convert ⍵ in the list of integer digits (not chars) in v
                 h←1⌷⍒v       puts in h the index of the first element max that appear in v
           v[(⍳⍴v)∼h           gets from v only the indices for digits different from h
        10⊥                   convert that modify v[]sub array to a number in base 10
 ∇h⌷v×            multiply it with v[h], and recall the same function for this number
}

```

---
Tags: code-golf, arithmetic, integer
---


title: Who is the rightful ruler?

text:
# Question
Title: Who is the rightful ruler?
Who will rule the realm?

You are given a family tree which contains: name, sex, date of birth, date of death and a list of heirs, for each family member. You may use any convenient (nested) list format to represent the tree. The following examples will use JSON. Determine who will rule the realm and in which order. The succession rules are the following:

1. When a king dies the realm goes to its oldest legit male child.
2. If there is none it passes to the oldest legit female child.
3. In case the king had no heirs the realm goes to the oldest legit king's brother
4. If there are no male brothers the realm will go to the oldest legit king's sister
5. If all legit relatives are dead the realm goes to the closest bastard, applying the above rules
6. If no legit nor bastard relatives are alive print `LINE EXTINCT`

We define a legit son as one who has the same "house" name as its father.

Examples:

Input `{}`

Output `LINE EXTINCT`

Input

```
{
    "name" : "Maegor",
    "house" : "Targaryen",
    "birth" : 12,
    "death" : 48,
    "sex" : "male",
    "heirs" : []
}

```

Output `12-48: Maegor, LINE EXTINCT`

Input

```
{
    "name" : "Jaehaerys",
    "house" : "Targaryen",
    "birth" : 34,
    "death" : 103,
    "sex" : "male",
    "heirs" : [
        {
        "name" : "Viserys",
        "house" : "Targaryen",
        "birth" : 77,
        "death" : 129,
        "sex" : "male",
        "heirs" : []
        }
    ]
}

```

Output `34-103: Jaehaerys, 103-129: Viserys, LINE EXTINCT`

Input

```
{
        "name" : "Eddard",
        "house" : "Stark",
        "birth" : 263,
        "death" : 299,
        "sex" : "male",
        "heirs" : [
            {
            "name" : "Robb",
            "house" : "Stark",
            "birth" : 283,
            "death" : 300,
            "sex" : "male",
            "heirs" : []
            },
            {
             "name" : "Jon",
             "house" : "Snow",
             "birth" : 284,
             "death" : 384,
             "sex" : "male",
             "heirs" : []
            },
            {
             "name" : "Sansa",
             "house" : "Stark",
             "birth" : 286,
             "death" : 320,
             "sex" : "female",
             "heirs" : []
            },
            {
             "name" : "Arya",
             "house" : "Stark",
             "birth" : 289,
             "death" : 350,
             "sex" : "female",
             "heirs" : []
            },

            {
             "name" : "Brann",
             "house" : "Stark",
             "birth" : 290,
             "death" : 315,
             "sex" : "male",
             "heirs" : []
            },
            {
             "name" : "Rickon",
             "house" : "Stark",
             "birth" : 295,
             "death" : 319,
             "sex" : "male",
             "heirs" : []
            }

        ]
    }

```

Output: `263-299: Eddard, 299-300: Robb, 300-315: Brann, 315-319: Rickon, 319-320: Sansa, 320-350: Arya, 350-384: Jon, LINE EXTINCT`

Note that the output can be formatted in any way you wish, its only requirements is that it contains the time of reign and the name of the reigning king during those years. I've used kings from the ASOIAF as demonstrative example, however the code needs to be valid for all input.

You may assume that no twins will be born.

This is a code golf challenge, so the shortest code in bytes wins

Good luck!!!

# Answer
## PHP, 664 bytes

I'm not sure if 664 bytes fit for code golfing, but here it is:

```
$k=json_decode($argv[1]);$s=[];$f='array_shift';$r='heirs';$e='death';$y='year';function s
($k,&$e){uasort($e,function($a,$b)use($k){$c=$a->{$h='house'};$d=$b->$h;$e=$k->$h;if($c==$e
&&$d!=$e)return-1;elseif($c!=$e&&$d==$e)return 1;elseif($a->sex<$b->sex)return 1;elseif($a
->sex>$b->sex)return -1;else return$a->birth-$b->birth;});}function d(&$e,$y){foreach($e
as$i=>$h)if($h->death<=$y)unset($e[$i]);};($x=(array)$k)&&$k->$y=$k->birth;$l=[];while($x)
{$l[]=$k;$z=$k->$e;s($k,$k->$r);d($k->$r,$k->$e);if($k->$r){$s=$k->$r;$k=$f($s);}else{s($k
,$s);d($s,$k->$e);$k=$f($s);}if(!$k)break;$k->$y=$z;}foreach($l as$k)
echo"{$k->$y}-{$k->$e}: $k->name, ";echo"LINE EXTINCT";

```

It receives the JSON string input as the first command line argument.

The algorithm follows the steps described in the challenge (starts from the king, then sorts the heirs and then the siblings to find the next king).

Demo
> 6 votes

# Answer
# jq, ~~429..410~~ 392bytes

```
def s(x;y):sort_by(.sex,-.birth)[]|select(.death>x.death and(.house==x.house|y));def i:index([[.[1:][]|select(.!=[])][0]]);def b(z;x;y):[.[i+z][:z+length-1]|s(x;y)];def h(x;y):[x.heirs|s(x;y)];[[],[],[],[],sort_by(-.birth)?]|until(i|not;.[i][-1]as$r|[.[0]+[$r+{t:(.[0][-1].death//$r.birth)}],h($r;.),h($r;not),b(0;$r;.),b(i%2;$r;not)])|[.[0][]|"\(.t)-\(.death):\(.name)"]+["LINE EXTINCT"]|.[]

```

Try it online!

**Explanation:**

```
def s(x;y):sort_by(.sex,-.birth)[]                          #Function: sorts by sex lexicographically, then by birth date in descending order [youngest female -> oldest male]
            |select(                                        and selects those who
                .death > x.death                            did not die before the previous ruler
                and (.house == x.house|y)                   and have the same house (if y := not, selects those with a different house)
            );
def i:index([[.[1:][]|select(.!=[])][0]]);                  #Function: returns index of the first not-empty array (ignoring first array)
def b(z;x;y):[.[i+z][:z+length-1]|s(x;y)];                  #Function: drops the last z (0 or 1) elements of the (i+z)th array and applies s on the resulting array
def h(x;y):[x.heirs|s(x;y)];                                #Function: takes the heirs of x and applies s

[                                                           An array containing five bins:
    [],                                                         0. Result
    [],                                                         1. Heirs from same house
    [],                                                         2. Heirs from another house
    [],                                                         3. Siblings from same house
    sort_by(-.birth)?                                           4. Siblings from another house (initial: sorted input (The ? is necessary for empty inputs))

|until(                                                     Until
        i|not                                               there is no such index i
    ;
        .[i][-1]as$r                                        set the last element of the ith array as the current ruler
        |[                                                  Update the array:
            .[0]+[$r+{t:(.[0][-1].death//$r.birth)}],       Add the current ruler + new attribute (the beginning time of reign) to the result array
            h($r;.),                                        Heirs from same house
            h($r;not),                                      Heirs from another house
            b(0;$r;.),                                      Siblings from same house
            b(i%2;$r;not)                                   If the ruler is heir from the same house as the previous one, store the heirs from a different house here
                                                            else siblings from a different house
        ]
)
|
    [
        .[0][]                                              Takes the result array
        |"\(.t)-\(.death):\(.name)"                         Writes time of reign and ruler
    ]
    +["LINE EXTINCT"]                                       Writes "LINE EXTINCT"
|.[]                                                        Prints on seperated lines

```
> 5 votes

# Answer
# JavaScript (Node.js), ~~294~~ ~~248~~ ~~244~~ 245 bytes

```
t=>{for(s(t),o(t.b,t);t;)o(t.d,t=n(t,0))}
s=(r,p)=>r.c.sort((a,b)=>a.s-b.s||a.b-b.b,r.g=p?(r.u=p.h!=r.h,p.c):[]).map(h=>s(h,r))
n=(k,b,j)=>[...k.c,...k.g].map(h=>j=j||h.u==b&h.d>k.d&&h)&&j||b?j:n(k,1)
o=(f,h)=>alert(h?[f,h.d,h.n]:'LINE EXTINCT')

```

Try it online!

-82 bytes thanks to Shaggy!
> 3 votes

---
Tags: code-golf, json
---


title: Levenshtein Distance

text:
# Question
Title: Levenshtein Distance
While there are many edit distance questions, such as this one, there isn't a simple question to write a program that calculates the Levenshtein distance.

**Some Exposition**

The Levenshtein edit distance between two strings is the minimum possible number of insertions, deletions, or substitutions to convert one word into another word. In this case, each insertion, deletion and substitution has a cost of 1.

For example, the distance between `roll` and `rolling` is 3, because deletions cost 1, and we need to delete 3 characterrs. The distance between `toll` and `tall` is 1, because substitutions cost 1.

**Rules**

* The input will be two strings. You may assume that the strings are lowercase, only contain letters, are non-empty and are a maximum of 100 characters in length.
* The output will be minimum Levenshtein edit distance of the two strings, as defined above.
* Your code must a program or a function. It does not need to be a named function, but it cannot be a built-in function that directly computes the Levenshtein distance. Other built-ins are allowed.
* This is code golf, so the shortest answer wins.

**Some Examples**

```
>>> lev("atoll", "bowl")
3
>>> lev("tar", "tarp")
1
>>> lev("turing", "tarpit")
4
>>> lev("antidisestablishmentarianism", "bulb")
27

```

As always, if the problem is unclear, please let me know. Good luck and good golfing!

## Catalogue

```
var QUESTION_ID=67474;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk";var OVERRIDE_USER=47581;var answers=[],answers_hash,answer_ids,answer_page=1,more_answers=true,comment_page;function answersUrl(index){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(index,answers){return"http://api.stackexchange.com/2.2/answers/"+answers.join(';')+"/comments?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){answers.push.apply(answers,data.items);answers_hash=[];answer_ids=[];data.items.forEach(function(a){a.comments=[];var id=+a.share_link.match(/\d+/);answer_ids.push(id);answers_hash[id]=a});if(!data.has_more)more_answers=false;comment_page=1;getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){data.items.forEach(function(c){if(c.owner.user_id===OVERRIDE_USER)answers_hash[c.post_id].comments.push(c)});if(data.has_more)getComments();else if(more_answers)getAnswers();else process()}})}getAnswers();var SCORE_REG=/<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;var OVERRIDE_REG=/^Override\s*header:\s*/i;function getAuthorName(a){return a.owner.display_name}function process(){var valid=[];answers.forEach(function(a){var body=a.body;a.comments.forEach(function(c){if(OVERRIDE_REG.test(c.body))body='<h1>'+c.body.replace(OVERRIDE_REG,'')+'</h1>'});var match=body.match(SCORE_REG);if(match)valid.push({user:getAuthorName(a),size:+match[2],language:match[1],link:a.share_link,});else console.log(body)});valid.sort(function(a,b){var aB=a.size,bB=b.size;return aB-bB});var languages={};var place=1;var lastSize=null;var lastPlace=1;valid.forEach(function(a){if(a.size!=lastSize)lastPlace=place;lastSize=a.size;++place;var answer=jQuery("#answer-template").html();answer=answer.replace("{{PLACE}}",lastPlace+".").replace("{{NAME}}",a.user).replace("{{LANGUAGE}}",a.language).replace("{{SIZE}}",a.size).replace("{{LINK}}",a.link);answer=jQuery(answer);jQuery("#answers").append(answer);var lang=a.language;lang=jQuery('<a>'+lang+'</a>').text();languages[lang]=languages[lang]||{lang:a.language,lang_raw:lang.toLowerCase(),user:a.user,size:a.size,link:a.link}});var langs=[];for(var lang in languages)if(languages.hasOwnProperty(lang))langs.push(languages[lang]);langs.sort(function(a,b){if(a.lang_raw>b.lang_raw)return 1;if(a.lang_raw<b.lang_raw)return-1;return 0});for(var i=0;i<langs.length;++i){var language=jQuery("#language-template").html();var lang=langs[i];language=language.replace("{{LANGUAGE}}",lang.lang).replace("{{NAME}}",lang.user).replace("{{SIZE}}",lang.size).replace("{{LINK}}",lang.link);language=jQuery(language);jQuery("#languages").append(language)}}
```

```
body{text-align:left!important}#answer-list{padding:10px;width:290px;float:left}#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table>
```

# Answer
# Pyth, 34 bytes

```
J]wf}z=Jsmsm++.DdkXLdkGXLkdGhld-Jk

```

Demonstration

This is not particularly well golfed, and very slow. It can't handle anything past 2 changes in a reasonable period of time.
> 9 votes

# Answer
# Matlab, ~~177~~ 163 bytes

```
function l=c(a,b);m=nnz(a)+1;n=nnz(b)+1;for i=0:m-1;for j=0:n-1;z=max(i,j);try;z=min([l(i,j+1)+1,l(i+1,j)+1,l(i,j)+(a(i)~=b(j))]);end;l(i+1,j+1)=z;end;end;l=l(m,n)

```

This is a straightforward implementation of this formula:

Ungolfed:

```
function l=l(a,b);
m=nnz(a)+1;
n=nnz(b)+1;
for i=0:m-1;
    for j=0:n-1;
        z=max(i,j);
        try;
            z=min([l(i,j+1)+1,l(i+1,j)+1,l(i,j)+(a(i)~=b(j))]);
        end;
        l(i+1,j+1)=z;
    end;
end;
l=l(m,n)

```
> 12 votes

# Answer
# APL (Dyalog Classic), 34 bytes

```
{0∊≢¨⍵:≢∊⍵⋄⌊/(≢.↑+∘∇↓¨)∘⍵¨1↓,⍳2 2}

```

Try it online!
> 9 votes

# Answer
# JavaScript (ES6) 106 ~~113 122~~

**Edit** 16 bytes saved following @Neil suggestions

As an anonymous function.

```
(s,t)=>[...s].map((u,i)=>w=w.map((v,j)=>p=j--?Math.min(p,v,w[j]-(u==t[j]))+1:i+1),w=[...[,...t].keys()])|p

```

This is a golfed implementation of the Wagner–Fischer algorithm exactly as described in the linked wikipedia article, in the section **Iterative with two matrix rows** (even if in fact, just 1 row is used - array *w*)

**Less golfed**

```
(s,t)=>
{
  w = [...[0,...t].keys()];
  for(i = 0; i < s.length; i++)
    w = w.map((v,j)=>
              p = j
              ? Math.min(p+1, v+1, w[j-1] + (s[i]!=t[j-1]))
              : i+1
             );
  return p
}

```

**Test snippet**

```
L=(s,t)=>[...s].map((u,i)=>w=w.map((v,j)=>p=j--?Math.min(p,v,w[j]-(u==t[j]))+1:i+1),w=[...[,...t].keys()])|p

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

[["atoll", "bowl"],["tar", "tarp"]
,["turing", "tarpit"],["antidisestablishmentarianism", "bulb"]]
.forEach(t=>console.log(t+' => '+L(...t)))
```

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

# Answer
# Python 2, ~~151~~ ~~140~~ 138 bytes

Slow recursive implemention of the Levenshtein distance based on Wikipedia (Thanks to @Kenney for shaving of 11 chars and @Sherlock9 for another 2).

```
def l(s,t):
 def f(m,n):
  if m*n<1:return m or n
  return 1+min([f(m-1,n),f(m,n-1),f(m-1,n-1)-(s[m-1]==t[n-1])])
 return f(len(s),len(t))

```

Giving the correct answers for the presented test cases:

```
assert l("tar", "tarp") == 1
assert l("turing", "tarpit") == 4
assert l("antidisestablishmentarianism", "bulb") == 27
assert l("atoll", "bowl") == 3

```
> 8 votes

# Answer
# Python 2, 118 bytes

A golf of this solution, but it doesn't look like Willem's been on for a year, so I'll have to post it myself:

```
def l(s,t):f=lambda m,n:m or n if m*n<1else-~min(f(m-1,n),f(m,n-1),f(m-1,n-1)-(s[m-1]==t[n-1]));print f(len(s),len(t))

```

**Try on repl.it**

Takes two strings and outputs the distance to `STDOUT` (allowed by meta). Please comment suggestions, I'm sure this can be golfed further.
> 6 votes

# Answer
# Haskell, 67 bytes

```
e@(a:r)#f@(b:s)|a==b=r#s|1<3=1+minimum[r#f,e#s,r#s]
x#y=length$x++y

```

Try it online! Example usage: `"turing" # "tarpit"` yields `4`.

This is a recursive solution. Given two strings `e` and `f`, we first compare their first characters `a` and `b`. If they are equal, then the Levenshtein distance of `e` and `f` is the same as the Levenshtein distance of `r` and `s`, the remainder of `e` and `f` after removing the first characters. Otherwise, either `a` or `b` needs to be removed, or one is substituted by the other. `[r#f,e#s,r#s]` recursively computes the Levenshtein for those three cases, `minimum` picks the smallest one, and `1` is added to account for the necessary remove or replace operation.

If one of the strings is empty, we and up on the second line. In this case, the distance is just the length of the non-empty string, or equivalently the length of both strings concatenated together.
> 6 votes

# Answer
# Python 3, ~~267~~ ~~216~~ ~~184~~ 162 bytes

This function calculates the Levenshtein distance using an array that is `2 x len(word_2)+1` in size.

**Edit:** This doesn't get close to the Willem's Python 2 answer, but here is a more golfed answer with many little refinements here and there.

```
def e(p,q):
 m=len(q);r=range;*a,=r(m+1);b=[1]*-~m
 for i in r(len(p)):
  for j in r(m):b[j+1]=1+min(a[j+1],b[j],a[j]-(p[i]==q[j]))
  a,b=b,[i+2]*-~m
 return a[m]

```

Ungolfed:

```
def edit_distance(word_1,word_2):
    len_1 = len(word_1)
    len_2 = len(word_2)
    dist = [[x for x in range(len_2+1)], [1 for y in range(len_2+1)]]
    for i in range(len_1):
        for j in range(len_2):
            if word_1[i] == word_2[j]:
                dist[1][j+1] = dist[0][j]
            else:
                deletion = dist[0][j+1]+1
                insertion = dist[1][j]+1
                substitution = dist[0][j]+1
                dist[1][j+1] = min(deletion, insertion, substitution)
        dist[0], dist[1] = dist[1], [i+2 for m in range(len_2+1)]
    return dist[0][len_2]

```
> 4 votes

# Answer
## Seriously, ~~86~~ ~~82~~ 78 bytes

```
,#,#`k;;;░="+l"£@"│d);)[]oq╜Riu)@d);)@[]oq╜Riu(@)@)@[]oq╜Ri3}@)=Y+km"£@IRi`;╗ƒ

```

Hex Dump:

```
2c232c23606b3b3b3bb03d222b6c229c4022b364293b295b5d6f71bd526975294064293b29405b
5d6f71bd5269752840294029405b5d6f71bd5269337d40293d592b6b6d229c40495269603bbb9f

```

Try It Online

(Note that the link is to a different version because something about the online interpreter breaks with the new, shorter version, even though it works fine with the downloadable interpreter.)

It's about the most straightforward implementation Seriously allows for the recursive definition. It is very slow because it does no memoization at all. Perhaps the tabular method could be shorter (maybe by using the registers as rows), but I'm fairly happy with this, despite how much kludging-my-way-around-the-language's-shortcomings it contains. That one can use

```
[]oq`<code>`Ri

```

as a proper two-argument function call was quite the nice find.

Explanation:

```
,#,#                             Read in two arguments, break them into lists of chars
    `                       `;╗ƒ put the quoted function in reg0 and immediately call it
     k;;;                        put the two lists in a list and make 3 copies
         ░                       replace the latter two with one with empty lists removed
          =                      replace two more with 1 if no empty lists removed, else 0
           "..."£@"..."£@        push the two functions described below, moving
                                 the boolean above them both
                         I       select the correct function based on the condition
                          Ri     call the function, returning the correct distance
                                 for these substrings

   There are two functions that can be called from the main function above. Each expects
   two strings, i and j, to be on the stack. This situation is ensured by putting
   those strings in a list and using R to call the functions with that list as the stack.
   The first is very simple:

+l                             Concatenate the strings and take their length.
                               This is equivalent to the length of the longer
                               string, since one of the strings will be empty.

   The second function is very long and complicated. It will do the "insertion, deletion,
   substitution" part of the recursive definition. Here's what happens in 4 parts:

│d);)                          After this, the stack is top[i-,j,i,j,ci,i-], where i- is
                               list i with its last character, ci, chopped off.
     []oq                      this puts i- and j into a list so that they can be passed
                               as arguments recursively into the main function
         ╜Riu                  this calls the main function (from reg0) with the args
                               which will return a number to which we add 1 to get #d,
                               the min distance if we delete a character
)@d);)@                        After this, the stack is top[i,j-,ci,i-,#d,cj,j-], where
                               j- and cj are the same idea as i- and ci
       []oq╜Riu                listify arguments, recurse and increment to get #i
                               (distance if we insert)
(@)@)@                         After this, the stack is top[i-,j-,#d,cj,#i,ci]
      []oq╜Ri                  listify arguments, recurse to get min distance between
                               them but we still need to add 1 when we'd need to
                               substitute because the chars we chopped off are different
(((@)                          After this, the stack is top[cj,ci,#s,#d,#i]
     =Y                        1 if they are not equal, 0 if they are
       +                       add it to the distance we find to get the distance
                               if we substitute here
        k                      put them all in a list
         m                     push the minimum distance over the three options

```
> 3 votes

# Answer
# AutoIt, 333 bytes

```
Func l($0,$1,$_=StringLen,$z=StringMid)
Dim $2=$_($0),$3=$_($1),$4[$2+1][$3+1]
For $5=0 To $2
$4[$5][0]=$5
Next
For $6=0 To $3
$4[0][$6]=$6
Next
For $5=1 To $2
For $6=1 To $3
$9=$z($0,$5,1)<>$z($1,$6,1)
$7=1+$4[$5][$6-1]
$8=$9+$4[$5-1][$6-1]
$m=1+$4[$5-1][$6]
$m=$m>$7?$7:$m
$4[$5][$6]=$m>$8?$8:$m
Next
Next
Return $4[$2][$3]
EndFunc

```

Sample test code:

```
ConsoleWrite(l("atoll", "bowl") & @LF)
ConsoleWrite(l("tar", "tarp") & @LF)
ConsoleWrite(l("turing", "tarpit") & @LF)
ConsoleWrite(l("antidisestablishmentarianism", "bulb") & @LF)

```

yields

```
3
1
4
27

```
> 3 votes

# Answer
## k4, 66 bytes

```
{$[~#x;#y;~#y;#x;&/.z.s'[-1 0 -1_\:x;0 -1 -1_\:y]+1 1,~(*|x)=*|y]}

```

A boring and basically ungolfed impl of the algo. Ex.:

```
  f:{$[~#x;#y;~#y;#x;&/.z.s'[-1 0 -1_\:x;0 -1 -1_\:y]+1 1,~(*|x)=*|y]}
  f["kitten";"sitting"]
3
  f["atoll";"bowl"]
3
  f["tar";"tarp"]
1
  f["turing";"tarpit"]
4
  f["antidisestablishmentarianism";"bulb"]
27

```
> 3 votes

# Answer
# Retina, ~~78~~ 72 bytes

```
&`(.)*$(?<!(?=((?<-4>\4)|(?<-1>.(?<-4>)?))*,(?(4),))^.*,((.)|(?<-1>.))*)

```

Try it online!

In a way, this is a pure regex solution where the result is the number of positions from which the regex matches. Because why not...

Fair warning, this is super inefficient. The way this works is that it offloads the actual optimisation to the regex engine's backtracker, which simply brute forces all possible alignments, starting with as few alterations as possible and allowing one more until it's possible to match up the strings with additions, deletions and substitutions.

For a slightly more sensible solution, this one does the matching only once and doesn't have any negative lookarounds. Here, the result is the number of captures in group `2`, which you could access with `match.Groups[2].Captures.Count` in C#, for example. It's still horribly inefficient though.

## Explanation

I'm explaining the second version above, because it's conceptually a bit easier (as it's just a single regex match). Here is an ungolfed version I've named the groups (or made them non-capturing) and added comments. Remember that the components in a lookbehind should be read from back to front, but alternatives and lookaheads inside those should be read from front to back. Yeah.

```
.+                      # Ensures backtracking from smallest to largest for next repetition
(?<ops>(?<distance>.))* # This puts the current attempted distances onto two different stacks,
                        # one to work with, and one for the result.
$                       # Make sure the lookbehind starts from the end.
(?<=                    # The basic idea is now to match up the strings character by character,
                        # allowing insertions/deletions/substitutions at the cost of one capture
                        # on <ops>. Remember to read from the bottom up.
  (?=                   # Start matching forwards again. We need to go through the other string
                        # front-to-back due to the nature of the stack (the last character we
                        # remembered from the second string must be the first character we check
                        # against in the first string).
    (?:
      (?<-str>\k<str>)  # Either match the current character against the corresponding one from
                        # the other string.
    |
      (?<-ops>          # Or consume one operation to...
        .               # consume a character without matching it to the other string (a deletion)
        (?<-str>)?      # optionally dropping a character from the other string as well
                        # (a substitution).
      )
    )*                  # Rinse and repeat.
    ,(?(str),)          # Ensure we reached the end of the first string while consuming all of the
                        # second string. This is only possible if the two strings can be matched up
                        # in no more than <distance> operations.
  )
  ^.*,                  # Match the rest of string to get back to the front.
  (?:                   # This remembers the second string from back-to-front.
    (?<str>.)           # Either capture the current character.
  |
    (?<-ops>.)          # Or skip it, consuming an operation. This is an insertion.
  )*
)

```

The only difference to the 72-byte version is that we can drop the leading `.+` (and second group in the beginning) by finding positions at the end where we *don't* have enough `<ops>` and count all of those positions.
> 3 votes

# Answer
# JavaScript (ES6),  ~~95 91~~  89 bytes

Takes input as `(source)(target)`. Essentially a port of @Willem's Python answer (later optimized by @FlipTack).

```
s=>t=>(g=m=>m*n?1+Math.min(g(m,--n),g(--m)-(s[m]==t[n++]),g(m)):m+n)(s.length,n=t.length)

```

Try it online!
> 3 votes

# Answer
# Python 3, ~~105~~ ~~94~~ ~~93~~ 99 bytes

*-11 bytes by xnor*
*+6 bytes to fix equal case*

```
l=lambda a,b:b>""<a and min(l(a[1:],b[1:])+(a[0]!=b[0]),l(a[1:],b)+1,l(a,b[1:])+1)or(a!=b)*len(a+b)

```

Try it online!
> 3 votes

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

```
l=lambda a,b:min(l(A:=a[1:],B:=b[1:])-(a[0]==b[0]),l(A,b),l(a,B))+1if b>""<a else len(a+b)

```

Try it online!
> 3 votes

# Answer
# Haskell, 136 bytes

Call `e`. Bit slow on `antidisestablishmentarianism` etc.

```
l=length
e a b=v a(l a)b(l b)
v a i b j|i*j==0=i+j|0<1=minimum[1+v a(i-1)b j,1+v a i b(j-1),fromEnum(a!!(i-1)/=b!!(j-1))+v a(i-1)b(j-1)]

```
> 2 votes

# Answer
# Jolf, 4 bytes

Try it here!

```
~LiI
~L   calculate the Levenshtein distance of
  i   input string
   I  and another input string

```

I added that builtin yesterday, but saw this challenge today, i.e., just now. Still, this answer is noncompeting.

In a newer version:

```
~Li

```

takes implicit second input.
> 2 votes

# Answer
# GNU Prolog, 133 bytes

```
m([H|A],B):-B=A;B=[H|A].
d([H|A]-[H|B],D):-d(A-B,D).
d(A-B,D):-A=B,D=0;D#=E+1,m(A,X),m(B,Y),d(X-Y,E).
l(W,D):-d(W,D),(E#<D,l(W,E);!).

```

Takes a tuple as argument. Example of usage:

```
| ?- l("turing"-"tarpit",D).

D = 4

yes

```

`m` specifies that `B` is `A` either directly or with its first character removed. `d` uses `m` as a subroutine to calculate *an* edit distance between the tuple elements (i.e. the distance of a series of edits that converts one into the other). Then `l` is a standard trick for finding the minimum of `d` (you take an arbitrary distance, then take an arbitrary smaller distance, repeat until you can't go smaller).
> 2 votes

# Answer
# TI-Basic, ~~194~~ ~~175~~ 174 bytes

```
Prompt Str1,Str2
length(Str1→A
length(Str2→B
{A,B→dim([A]
For(I,1,A
For(J,1,B
3→dim(ʟA
{I-1,J,I,J-1,I-1,J-1→B
For(X,1,3
ʟB(2X-1→Y
ʟB(2X→Z
If YZ:Then
[A](Y,Z
Else
max(Y,Z
End
Ans→ʟA(X
End
min(ʟA+{1,1,sub(Str1,I,1)≠sub(Str2,J,1→[A](I,J
End
End
[A](A,B

```

-19 bytes thanks to MarcMush

-1 byte by combining the 2 Prompts on the same line.

The output is stored in `Ans` and is displayed at the end.
> 2 votes

# Answer
# Perl, ~~168~~ ~~166~~ 163 bytes

```
sub l{my($S,$T,$m)=(@_,100);$S*$T?do{$m=++$_<$m?$_:$m for l($S-1,$T),l($S,--$T),l(--$S,$T)-($a[$S]eq$b[$T]);$m}:$S||$T}print l~~(@a=shift=~/./g),~~(@b=shift=~/./g)

```

Recursive implementation. Save in a `file.pl` and run as `perl file.pl atoll bowl`.

```
sub l {
    my($S,$T,$m)=(@_,100);

    $S*$T
    ? do {
        $m = ++$_ < $m ? $_ : $m
        for
            l($S-1,   $T),
            l($S  , --$T),
            l(--$S,   $T) - ($a[$S] eq $b[$T])
        ;
        $m
    }
    : $S||$T
}
print l~~(@a=shift=~/./g),~~(@b=shift=~/./g)

```

---

The other two implementations are both longer (full matrix: 237 bytes, ~~two~~one-row iterative: 187). * *update 166*: omit `()` in calling `l`.
* *update 163*: eliminate `return` by abusing `do` in trinary.
> 1 votes

# Answer
# C#, ~~215~~ ~~210~~ 198

```
public int L(string s,string t){int c,f,a,i,j;var v=new int[100];for(c=i=0;i<s.Length;i++)for(f=c=i,j=0;j<t.Length;j++){a=c;c=f;f=i==0?j+1:v[j];if(f<a)a=f;v[j]=c=s[i]==t[j]?c:1+(c<a?c:a);}return c;}

```

more readable:

```
public int L(string s,string t){
    int c,f,a,i,j;
    var v=new int[100];
    for(c=i=0;i<s.Length;i++)
        for(f=c=i,j=0;j<t.Length;j++){
            a=c;
            c=f;
            f=(i==0)?j+1:v[j];
            if (f<a) a=f;
            v[j]=c=(s[i]==t[j])?c:1+((c<a)?c:a);
        }
    return c;
}

```
> 0 votes

# Answer
# C, 192 bytes

```
#define m(x,y) (x>y?x:y)
#define r(x,y) l(s,ls-x,t,lt-y)
int l(char*s,int ls,char*t,int lt){if(!ls)return lt;if(!lt)return ls;a=r(1,1);if(s[ls]==t[ls])return a;return m(m(r(0,1),r(1,0)),a)+1;}
---------

```

Detailed

```
#include <stdio.h>

#define m(x,y) (x>y?x:y)
#define f(x) char x[128];fgets(x,100,stdin)
#define r(x,y) l(s,ls-x,t,lt-y)

int l(char*s,int ls,char*t,int lt)
{
    if(!ls) return lt;
    if(!lt) return ls;

    int a = r(1,1);
    if(s[ls]==t[ls]) return a;

    return m(m(r(0,1),r(1,0)),a)+1;
}

int main(void)
{
    f(a);
    f(b);
    printf("%d", l(a,strlen(a),b,strlen(b)));
    return 0;
}

```
> 0 votes

# Answer
## PowerShell v3+, 247 Bytes

```
$c,$d=$args;$e,$f=$c,$d|% le*;$m=[object[,]]::new($f+1,$e+1);0..$e|%{$m[0,$_]=$_};0..$f|%{$m[$_,0]=$_};1..$e|%{$i=$_;1..$f|%{$m[$_,$i]=(($m[($_-1),$i]+1),($m[$_,($i-1)]+1),($m[($_-1),($i-1)]+((1,0)[($c[($i-1)]-eq$d[($_-1)])]))|sort)[0]}};$m[$f,$e]

```

I ended up making this to solve another challenges involving LD's.

### Code explanation with comments.

```
# Get both of the string passed as arguments. $c being the compare string
# and $d being the difference string.
$c,$d=$args

# Save the lengths of these strings. $e is the length of $c and $f is the length of $d
$e,$f=$c,$d|% le*

# Create the multidimentional array $m for recording LD calculations
$m=[object[,]]::new($f+1,$e+1)

# Populate the first column
0..$e|%{$m[0,$_]=$_}

# Populate the first row
0..$f|%{$m[$_,0]=$_}

# Calculate the Levenshtein distance by working through each position in the matrix.
# Working the columns
1..$e|%{
    # Save the column index for use in the next pipeline
    $i=$_

    # Working the rows.
    1..$f|%{
        # Calculate the smallest value between the following values in the matrix relative to this one
        # cell above, cell to the left, cell in the upper left.
        # Upper left also contain the cost calculation for this pass.
        $m[$_,$i]=(($m[($_-1),$i]+1),($m[$_,($i-1)]+1),($m[($_-1),($i-1)]+((1,0)[($c[($i-1)]-eq$d[($_-1)])]))|sort)[0]
    }
}
# Return the last element of the matrix to get LD
$m[$f,$e]

```
> 0 votes

---
Tags: code-golf, string, edit-distance
---


# Question
Title: Bijective mapping from integers to a variable number of trits
## This challenge is a harder version of this one.

A variable number of trits is an array of 0 or more trits (a trit is a ternary digit). So `[0, 2, 2, 1]` is a variable number of trits, but so is `[]`.

Write a function or program that, given an non-negative integer returns a variable number of trits such that every integer has a one-to-one (bijective) mapping with an array.

There are an infinite amount of such mappings, you are free to construct one as you please, but it **must** be one-to-one. Your mapping must *conceptually* be one-to-one for an arbitrarily sized integer, but it's OK if your *implementation* fails for large integers due to numerical limits of types in your preferred language (e.g. C's `int`).

As an example of what is **not** a one-to-one mapping, is simply listing the ternary digits of the integer. In such a system 5 becomes `[1, 2]` (because `1*3^1 + 2*3^0 = 5`), but it's not one-to-one, because `[0, 1, 2]` also means 5 (because `0*3^2 + 1*3^1 + 2*3^0 = 5`).

It should be fairly obvious that a mapping is not one-to-one if it skips an integer (e.g. it doesn't work for 5), but I'd like to make it clear that skipping a variable trit array is also not one-to-one. You must map to every possible variable trit array, including `[]`.

### Bonus challenge

You will be awarded the official Super Smaht® Award™ if your answer includes an algorithm (not necessarily in your golfed program) that not only works for base 2 or 3, but for all bases.

---

Shortest code in bytes wins.

# Answer
# Pyth, 6 bytes

```
tjyhQ3

```

Explanation:

```
    Q    Input number.
   h     Add 1.
  y      Multiply by 2.
 j   3   Convert to base 3 as a list.
t        Remove the first element.

```

Test suite

## Inverse function: Pyth, 14 bytes

```
t/i+-2%sQ2Q3 2

```

Explanation:

```
        Q        Input list.
       s         Sum.
      %  2       Modulo 2.
    -2           Subtract from 2.
   +      Q      Prepend to input list.
  i        3     Convert from base 3.
 /           2   Divide by 2.
t                Subtract 1.

```

Test suite

The bijection looks like this:

```
0: []
1: [1]
2: [0]
3: [2]
4: [0, 1]
5: [1, 0]
6: [1, 2]
7: [2, 1]
8: [0, 0]
9: [0, 2]
10: [1, 1]
11: [2, 0]
12: [2, 2]
13: [0, 0, 1]
14: [0, 1, 0]
15: [0, 1, 2]
16: [0, 2, 1]
17: [1, 0, 0]
18: [1, 0, 2]
19: [1, 1, 1]
⋮

```

# General base

To make this work in any base b, simply replace `3` with b, `2` with (b − 1), and `y` with `*`(b − 1).
> 6 votes

# Answer
# JavaScript, 24 bytes

```
f=n=>n?f(--n/3|0)+n%3:''

```

Try it online!

Implements the standard ternary bijective numeration, except with the digits reduced by 1.

How it works: First, check if `n` is 0, returning the empty string if so. Otherwise, `n` is pre-decremented, and that value is divided by 3 and rounded down (`|0` is a short way to do the rounding) and passed recursively to `f` – the final digit will contribute 1, 2, or 3, while the rest contribute a multiple of 3, so \\$\lfloor\frac{n-1}{3}\rfloor\\$ is the value the non-final digits should represent on their own. Finally, `n%3` appends the final digit, reduced by 1 from the standard (`n` having already been decremented).
> 2 votes

# Answer
# Jelly, 3 bytes

```
ḃ3’

```

Try it online!

```
ḃ3   Convert to bijective base 3
  ’  Decrement all digits

```

## Inverse, 3 bytes

```
‘ḅ3

```

Try it online!

```
‘    Increment all digits
 ḅ3  Convert from base 3

```

Both versions can be made to use an arbitrary base by removing the `3`.
> 1 votes

# Answer
# Jelly, 12 bytes

```
ḤR‘b3Ḣ’$Ðḟị@

```

There is no empty list in Jelly; it is represented as `0` (an integer not a list).

For other bases: change  to `×n` and `b3` to `bn`, where `n` is the intended base.

Try it online!

Test suite.

# For other bases

It only costs **11 bytes** if given base as second input.

Try it online!

Test suite.

# Algorithm

I thought of appending a `1` before the list and then convert it to a ternary.

That way, `[0,0]` will become `100 = 9` while `[0,0,0]` will become `1000 = 27`.

However, a problem arises: that `2011` and `1011` both map to `[0,1,1]`.

I only need numbers whose ternary representation starts with `1`.

Therefore, I generated those whose ternary representation starts with `1`, and then use their **index** instead.

That is, the list begins as `[1, 3, 4, 5, 9, 10, 11, 12, 13, 14, 15, 16, 17, ...]`.

Therefore:

* `1` will be mapped to `1`
* `2` will be mapped to `3`
* `3` will be mapped to `4`
* `4` will be mapped to `5`
* `5` will be mapped to `9`
* `n` will be mapped to `a(n)` where `a` is that list.

There's another problem: both `0` and `1` are mapped to the empty list. Therefore, I removed `1` from the list, making `a = [3, 4, 5, 9, 10, 11, 12, 13, 14, 15, 16, 17, ...]`.

Those are the integers whose ternary representation starts with `1`, **except `1`**.

The same algorithm can be applied to other bases.
> 0 votes

# Answer
# Jelly, 6 bytes

```
‘Ḥb3ṫ2

```

Translation of Kaseorg's answer in Pyth.

Try it online!

Hardcoded base: try it online!

Given base: try it online!
> 0 votes

# Answer
# CJam, 9 bytes

```
ri)_+3b(;

```

Translation of Kaseorg's answer in Pyth.

Try it online!
> 0 votes

# Answer
## JavaScript (ES6), 31 bytes

```
n=>(n*2+2).toString(3).slice(1)

```

Since everyone else is translating @AndreasKaseorg's fine answer. Generic version (36 bytes):

```
b=>n=>(-~n*~-b).toString(b).slice(1)

```
> 0 votes

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


title: Can you pretty-print a tree?

text:
# Question
Title: Can you pretty-print a tree?
# Goal:

A tree can be represented as a nested list: the list elements represent nodes, and a node is a pair of the node name and node children.

Your program takes as input a nested list of pairs, and should output a pretty tree.

# Examples:

Here are four example test cases below

```
["stump",[]]

["trunk",[["branch",[["leaf",[]],["leaf",[]]]],["branch",[]]]]

[".",[["bin",[]],["usr",[["bin",[]],["local",[["bin",[]],["lib",[]]]]]]]]

["kingdom",[["mineral",[]],["animal",[["dog",[["schnauzer",[]],["whippet",[]]]]]],["vegetable",[["cabbage",[]]]]]]

```

And these are the corresponding outputs

1

```
stump

```

2

```
trunk
├── branch
│   ├── leaf
│   └── leaf
└── branch

```

3

```
.
├── bin
└── usr
    ├── bin
    └── local
        ├── bin
        └── lib

```

4

```
kingdom
├── mineral
├── animal
│   └── dog
│       ├── schnauzer
│       └── whippet
└── vegetable
    └── cabbage

```

# Notes:

* If the characters , , ,  are not conveniently available in your language, you may substitute with the ASCII characters `|`, `+`, `L`, `-` respectively.
* You may assume there is one unique root node. You may assume the input will be "nice", it doesn't matter what your program does if the input is not well-formed.
* To avoid unfair advantages to any particular language, some flexibility in the input format is allowed *within reason*. For example, specifying the nesting with parens `()` or braces `{}` is OK. If it's more convenient for the node labels to be integers instead of strings, that's OK. Extra whitespace in the input is OK, as long as it's not being used to define structure. If you take the input as a string literal and parse it directly, that's OK.
* No messing with the underlying structure of the tree! E.g., you may not change how a leaf node is represented.
* **Tip:** the representation used in the examples is valid json, so you can paste it into a json linter to better see the nesting.

# Scoring:

This is code golf, shortest code wins.

# Answer
## Perl 5, 146 bytes

```
sub f{my$r=@_-1;my$p=$r?pop:[];while(my$n=shift){my($t,$c)=@$n;say$r?((map$_?'|   ':$"x4,@$p),@_?'+':L,'-- '):(),$t;f(@$c,[@$p,$r?!!@_:()])if@$c}}

```

Try it online!
> 4 votes

# Answer
# Haskell, 159 bytes

With preprocessing of the input to fit the defined tree datatype (included in score) since trees can't be represented as a nested list.

```
data T=T[Char][T]
r=reverse;z=zipWith;a%b=a:cycle[b]
p(T s b)|k<-r$p<$>b=s:(concat$r$z(z(++))(("└── "%"    ")%("├── "%"│   "))k)
mapM putStrLn.p

```

Usage:

```
> mapM putStrLn.p $ T"kingdom"[T"mineral"[],T"animal"[T"dog"[T"schnauzer"[],T"whippet"[]]],T"vegetable"[T"cabbage"[]]]
kingdom
├── mineral
├── animal
│   └── dog
│       ├── schnauzer
│       └── whippet
└── vegetable
    └── cabbage

```
> 3 votes

# Answer
# JavaScript (ES6), 123 ~~125~~ bytes

Using 5 unicode graphic character, 3 bytes each. The char count is 115.

```
x=>(o=x[0],r=(l,p)=>l[0]&&l.map((x,i)=>r(x[1],p+'│ '[q=+!l[i+1]]+'   ',o+=`
${p+'├└'[q]}── `+x[0])),r(x[1],''),o)

```

*Less golfed*

```
l=>(
  o = l[0],
  r = (l,p)=> // recursive tree printer
      l[0] &&
      l.map((x,i)=>
             (
               q = +!l[i+1],
               o += `\n${p+'├└'[q]}── ` + x[0],
               r(x[1], p+'│ '[q]+'   ')
             )
      ),
  r(l[1],''),
  o
)

```

```
F=
x=>(o=x[0],r=(l,p)=>l[0]&&l.map((x,i)=>r(x[1],p+'│ '[q=+!l[i+1]]+'   ',o+=`
${p+'├└'[q]}── `+x[0])),r(x[1],''),o)

out=x=>O.textContent+=x+'\n\n'

;[["stump",[]]
,["trunk",[["branch",[["leaf",[]],["leaf",[]]]],["branch",[]]]]
,[".",[["bin",[]],["usr",[["bin",[]],["local",[["bin",[]],["lib",[]]]]]]]]
,["kingdom",[["mineral",[]],["animal",[["dog",[["schnauzer",[]],["whippet",[]]]]]],["vegetable",[["cabbage",[]]]]]]
].forEach(t=>out(JSON.stringify(t)+'\n'+F(t)))
```

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

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

```
` 0:4_'{r:o@x,y[1],"   ";(,x,(*y),"-- ",*z),/$[z@1;("+|"r/:-1_z@1),"L "r/:-1#z@1;""]}["";"  ";]@

```

Try it online!

Quite a shame that this took so long, but I'm glad that I stuck with the problem.

Recursive function which prints each line of the tree separately. ngn/k's json parser is used to get the array.

-6 bytes from coltim.

-1 from ngn.
> 3 votes

# Answer
# Python 3, 110 109 bytes

Down to 109 thanks to att

```
def f(l,p='',a=0,o=0):
 x,c=l;print(p+(('+L'[o]+'-- ')*a)+x)
 for i in c:f(i,p+('| '[o]+'   ')*a,1,c[-1]is i)

```

Call as:

```
f(["kingdom",[["mineral",[]],["animal",[["dog",[["schnauzer",[]],["whippet",[]]]]]],["vegetable",[["cabbage",[]]]]]])

```

To get output:

```
kingdom
+-- mineral
+-- animal
|   L-- dog
|       +-- schnauzer
|       L-- whippet
L-- vegetable
    L-- cabbage

```

This is my first `code-golf`, so I welcome any feedback or suggestions. I ended up using flags for the recursive function to know when an element was the root node or when it was the last leaf of a node, allowing it to differentiate the prefix that needed to be applied. I wanted to have the last argument for the recursive call originally be `i==c[-1]`, but ran into an issue with the call

```
f(["trunk",[["branch",[["leaf",[]],["leaf",[]]]],["branch",[]]]])

```

where the two branches are equivalent but not identical, so a `is` call was necessary instead of `==`.
> 3 votes

# Answer
## Python 2, ~~118~~ 119 bytes

```
def f(x,q='',p='',r=''):
 m,w=x;l=len(w);print q+r+m
 for i in range(l):a=l-i>1;f(w[i],q+p,' |'[a]+'   ','L+'[a]+'-- ')

```

Call as:

```
f(["kingdom",[["mineral",[]],["animal",[["dog",[["schnauzer",[]],["whippet",[]]]]]],["vegetable",[["cabbage",[]]]]]])

```

Outputs:

```
kingdom
+-- mineral
+-- animal
|   L-- dog
|       +-- schnauzer
|       L-- whippet
L-- vegetable
    L-- cabbage

```
> 1 votes

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