# Question
Title: To raise \$ e \$ to the power of a matrix
Inspired by this 3Blue1Brown video

Given a square matrix \\$ M \\$, compute its matrix exponential \\$ \exp(M) \\$, which is defined, using an extension of the Maclaurin series for \\$ e^x \\$, as

$$ \exp(M) = \sum\_{r=0}^\infty \frac {M^r} {r!} = M^0 + M^1 + \frac 1 2 M^2 + \frac 1 6 M^3 + \cdots + \frac 1 {n!} M^n + \cdots $$

where \\$ n! \\$ represents the factorial of \\$ n \\$, and \\$ M^0 \\$ is the identity matrix for the dimensions of \\$ M \\$.

There are other ways to compute this, which you may use, as long as the result is sufficiently precise (see the rules below).

## Test cases

| Input | Output |
| --- | --- |
| ``` 0 0<br>0 0 ``` | ``` 1.0 0.0<br>0.0 1.0 ``` |
| ``` 1 2<br>3 4 ``` | ``` 51.968956198705044 74.73656456700328<br>112.10484685050491 164.07380304920997 ``` |
| ``` 1 0<br>0 1 ``` | ``` 2.718281828459045 0.0<br>0.0 2.718281828459045 ``` |
| ``` -10 -7<br>6 3 ``` | ``` -0.17051293798604472 -0.22030000635390898<br>0.18882857687477908 0.23861564524264348 ``` |
| ``` -2 16<br>0 7 ``` | ``` 0.1353352832366127 1949.3294633692833<br>0.0 1096.6331584284585 ``` |
| ``` 12 18 -5<br>-13 13 17<br>13 -6 2 ``` | ``` 951375.2972757841 1955306.8594829023 2179360.8077694285<br>376625.60116007976 774976.2125979062 863826.1366984685<br>773311.8986313189 1589134.8925863737 1771827.68268726 ``` |
| ``` 8 19 20 19<br>19 -18 8 -11<br>7 -16 17 -11<br>13 -15 -14 2 ``` | ``` -809927951.1659397 682837927.821331 -2875315029.426385 166307199.77734298<br>-114105964.84866604 423320553.28643256 -1532090815.2105286 379540651.37782615<br>666012827.4455533 256623519.77362177 -454247177.983024 753881172.0779059<br>-849659694.5821244 -147765559.4347415 -39332769.14778117 -766216945.8367432 ``` |
| ``` 15 -17 7 -1 18 5<br>-20 1 -11 -11 -2 16<br>14 -4 -6 -8 -4 5<br>-18 2 -14 5 1 -11<br>-16 18 19 -10 -17 13<br>10 20 7 19 14 0 ``` | ``` -84820410929.4261 -16367909783.470901 -68656483749.58916 3885773007.51203 -53912756108.37766 -68894112255.13809<br>190335662933.039 -38645269722.440834 127312405236.2376 -13585633716.898304 90603945063.00284 75004079839.71536<br>-68036952943.18438 -7733451697.302282 -53156358259.70866 3465229815.7224665 -41070570134.5761 -49564275538.3475<br>60712557398.76749 30529410698.827442 55820038060.925934 -1566782789.1900578 46171305388.15615 69179468777.9944<br>123964494616.41298 -39882807512.560074 77695806070.41081 -9798106385.28041 53080430956.84853 33312855054.34455<br>202240615797.98032 -49846425749.36303 132157848306.15779 -15002452609.223932 92731071983.4513 70419737049.6608 ``` |
| ``` -3 3 9 -14 13 3 -19 11<br>-3 16 -3 -2 -16 17 -7 14<br>-16 -13 -19 -4 -19 -12 -19 4<br>-19 2 -1 -13 -1 20 -18 20<br>-15 -14 -17 4 -16 -7 -13 10<br>-1 3 -2 -18 -13 -20 -18 8<br>-6 5 17 4 -11 0 4 1<br>-7 14 4 5 -10 1 11 -1 ``` | ``` -961464430.42625 -3955535120.8927402 -458113493.1060377 1262316775.4449253 1876774239.173575 -1179776408.054209 710474104.2845823 -1223811014.5581887<br>28955217908.989292 119124631307.93314 13796523822.599554 -38015726498.96707 -56520887984.67961 35530121226.97329 -21396437283.72946 36856280546.42262<br>-8410889774.023839 -34603239307.789085 -4007607155.9532456 11042781096.475042 16418151308.196218 -10320764772.97249 6215219812.505076 -10705984738.665106<br>10215509474.424953 42027619363.9107 4867469315.8131275 -13412092189.39047 -19940786719.11994 12535160455.72014 -7548741937.235227 13003031639.209038<br>-1859396787.0195892 -7649733581.4828005 -885954562.2162387 2441226246.193038 3629550445.402215 -2281610372.751828 1374002295.125188 -2366775855.5699253<br>449955718.5164527 1851164998.6281173 214390574.08290553 -590752899.2082579 -878315768.622139 552129374.7322844 -332495739.50407004 572740581.3608516<br>4056736597.835622 16689783857.791903 1932941125.9578402 -5326143353.840331 -7918773134.746702 4977893918.896973 -2997723598.294145 5163693248.841862<br>18572197375.577248 76407841992.77576 8849246673.162008 -24383706828.81331 -36253120255.06763 22789406560.399803 -13723910211.58447 23640014943.24763 ``` |

## Rules

* Your outputs must be within \\$ \pm 1 \\% \\$ of the outputs given in the test cases above
* If you use a boring builtin to do most of the computation, you should add it to the Community Wiki answer, or post another more interesting method as well
* You may assume \\$ M \\$ will be square and have side length in \\$ \[2, 8\] \\$
* The elements of \\$ M \\$ will all be integers in \\$ \[-20, 20\] \\$
* You may take \\$ M \\$ as a nested array, a built-in matrix type, a flat array which is a square-number in length, or any other sensible format
* Standard loopholes are forbidden
* Standard I/O rules apply
* This is , so the shortest code in bytes wins

# Answer
> 6 votes
# Trivial built-in answers

If your solution uses a built-in function to perform the core of the challenge, please edit it in to this answer.

# Wolfram Language (Mathematica), 9 bytes

```
MatrixExp

```

# MATL, 2 bytes

```
Ye

```

Try it online!

# MATLAB/Octave, 5 bytes

```
@expm

```

Try it online!

# Python 3, 30 bytes

```
from scipy.linalg import*
expm

```

Try it online!

# , 12 bytes

```
Matrix::expm

```

Try it online!

# Julia, 3 bytes

```
exp

```

Try it online!

# Answer
> 4 votes
# Jelly, 18 bytes

```
-©‘+³æ*‘ɼ¤÷®!¤¤$ÐL

```

Try it online!

-5 bytes thanks to caird coinheringaahing

This is probably the least Jelly-like Jelly answer ever. Goes for unbounded precision, even though 1/256! (which is what caird coinheringaahing's solution does) is definitely enough in practice.

This only terminates due to limited precision. If we had infinite/unbounded precision, this would never stop running. It basically just keeps adding terms until the result stops changing, which means we've hit the precision limit.

Or actually, this is more cursed:

# Jelly, 34 bytes

```
ŒṘ“çm(<ÇƤMʂƲṬVḅċñ!żŒȥu¢iİẠẈ“œ4»jŒV

```

Try it online!

-3 bytes thanks to Unrelated String.

# Answer
> 3 votes
# Jelly, 11 bytes

```
æ*÷!}ɗⱮ⁹Ḷ¤S

```

Try it online!

## How it works

Basically, we calculate $$\sum\_{r=0}^{255} \frac {M^r} {r!}$$ which is large enough to not have to worry about precision. For one additional byte, we can instead calculate $$\sum\_{r=0}^{10^9} \frac {M^r} {r!}$$, which is, for all intents and purposes, equal to $$\sum\_{r=0}^\infty \frac {M^r} {r!}$$

```
æ*÷!}ɗⱮ⁹Ḷ¤S - Main link. Takes M on the left
         ¤  - Group the previous links into a constant:
       ⁹    -   256
        Ḷ   -   Lowered range; [0, 1, ..., 255]
     ɗ      - Group the previous 3 links into a dyad f(M, i):
æ*          -   Raise M to the i'th power
    }       -   To i:
   !        -     Factorial
  ÷         -   Divide each element of Mⁱ by i!
      Ɱ     - Over each i in [0, 1, ..., 255], calculate f(M, i)
          S - Sum

```

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

This iterates until \\$1/n!\\$ becomes \\$0\\$ because of IEEE 754 underflow.

```
f=(m,M=m,S=m.map(r=>r.map(_=>j=0)),q=1)=>q?f(m,M.map((r,y)=>r.map((_,x)=>(S[y][x]+=(v=j?r.reduce((t,v,i)=>t+v*m[i][x],0):x==y)*q,v))),S,q/++j):S

```

Try it online!

# Answer
> 3 votes
# , ~~85~~ ~~81~~ ~~63~~ ~~61~~ 59 bytes

*Edit: -18 bytes & new approach thanks to xnor's comment, and then -2 more bytes thanks to ovs*

```
function(m){k=diag(nrow(m))+m/2^25;for(i in 1:25)k=k%*%k;k}

```

Try it online!

Non-builtin solution (see here to save ~~69~~ 47 bytes...).

# Answer
> 3 votes
# Pari/GP, 16 bytes

Based on xnor's comment:

> An observation I don't see any answers using so far -- \\$e^M\approx(I+M/n)^n\\$ for large \\$n\\$.

~~It seems that \\$n = 9!\\$ is enough for the \\$ \pm1 \\%\\$ requirement of the testcases.~~

Sorry. It turns out that \\$n = 9!\\$ is not good enough. It exceed the \\$ \pm1 \\%\\$ requirement in exactly one value: the `-39332769.14778117` in the 7th testcase, where \\$n = 9!\\$ gives `-38882430.43811763`. So I have to use \\$n = 99!\\$.

```
m->(1+m/99!)^99!

```

Try it online!

# Answer
> 3 votes
# Wolfram Language (Mathematica), ~~54~~ 53 bytes

I'm still not excellent at golfing, so additions are very welcome. Originally I tried to use only `Sum[MatrixPower[#,n],{n,0,∞}]&`, but that doesn't work for a matrix of only zeros as `MatrixPower` doesn't work on singular matrices.

```
IdentityMatrix@Tr[1^#]+Sum[#~MatrixPower~n/n!,{n,∞}]&

```

It can respond with symbolic results for all inputs, so `{{1,0},{0,1}}` gives an answer of `{{E,0},{0,E}}`, and `{{-2, 16}, {0, 7}}` returns `{{1+(1-E)^2/E^2, 16(E^9-1)/(9E^2)}, {0, E^7}}`. If floating point answers are wanted `N@` can be added in front of `IdentityMatrix`.

-1 byte, thanks @att.

Try it online!

# Answer
> 2 votes
# , 31 bytes

```
[:+/!@i.@99%~]+/ .*^:(<99)[:=#\

```

Try it online!

Just implements the formula up to 99 terms, which seems to be good enough to be within 1% of the test cases.

# Answer
> 1 votes
# Charcoal, 49 bytes

```
≔ＥθＥι⁼κμη≔ηζＦφ«≔Ｅη∕ＥκΣＥκ×ξ§§θπν⊕ιηＵＭζＥκ⁺μ§§ηλν»Ｉζ

```

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

```
≔ＥθＥι⁼κμη≔ηζ

```

Create an identity matrix and save it as the last power series term and also the running total.

```
Ｆφ«

```

Loop 1,000 times.

```
≔Ｅη∕ＥκΣＥκ×ξ§§θπν⊕ιη

```

Multiply the last power series term by the input and divide by the 1-indexed loop index to create the next term.

```
ＵＭζＥκ⁺μ§§ηλν

```

Add the term to the running total in-place, as the term is now a separate array and no longer shared with the running total.

```
»Ｉζ

```

Print the final total.

# Answer
> 1 votes
# Raku, ~~118~~ 113 bytes

```
{[»+«] (flat((1,0 xx$_)xx$_).rotor($_)[^$_],{cross(with=>(*Z* *).sum,@^x
»/»++$,[Z] $_).rotor($_)}...*)[^99]}

```

Try it online!

* `[»+«]` reduces the following sequence of 99 matrices (each a list-of-lists) with elementwise addition. (99 seems like more than enough terms for any practical purpose.)
* `flat((1, 0 xx $_) xx $_).rotor($_)[^$_]` is the starting identity matrix.

I found a somewhat concise way to do matrix multiplication on lists-of-lists `@m1` and `@m2` in Raku:

```
cross(with => (* Z* *).sum, @m1, [Z] @m2).rotor(@m1)

```

`cross` here is the cross product operation. `(* Z* *).sum` is an anonymous function applied to each combination of rows from `@m1` and columns from `@m2`, zipping them with multiplication and then summing. `[Z] @m2` is a tricky way to get the transpose of the right-hand matrix `@m2`. That gives just a flat list of numbers, which `.rotor(@m1)` turns back into a square matrix.

`@^x` is the previous matrix in the series, which I divide elementwise by a steadily increasing anonymous state variable with `»/» ++$` before multiplying by the input matrix `$_` to get the same effect as dividing by the factorial in the original formula.

---
Tags: code-golf, math, matrix
---


title: Ungolf my tinylisp code

text:
# Question
Title: Ungolf my tinylisp code
I like golfing in tinylisp:

```
(d M(q((x)(i x(i(disp x)0(M x))0

```

But I also like posting explanations with nicely formatted code:

```
(d M
 (q
  ((x)
   (i x
    (i (disp x) 0 (M x))
    0))))

```

Can you help me generate the ungolfed code for my explanations?

## The task

Given a line of tinylisp code, return or output the same code, formatted to the following specifications:

### Input syntax

Tokens in tinylisp are `(`, `)`, or any string of one or more printable ASCII characters excluding parentheses or space. (I.e. the following regex: `[()]|[^() ]+`.) A non-parenthesis token is called an *atom*. Spaces are ignored, except insofar as they separate tokens.

For this challenge, the input code will consist of a single parenthesized list containing 0 or more items. The items in the list may be either (arbitrarily deeply nested) lists or single-token atoms (or a mixture). Two items may be separated by a single space; the space may also be omitted, unless it is necessary to separate two adjacent atoms. There will not be spaces anywhere else in the input; in particular, there will never be spaces immediately after an opening parenthesis or immediately before a closing parenthesis. Closing parentheses at the end of the expression may be omitted.

Some examples:

```
()
(1 2 3)
(1 2 3
(1 (2))
(1(2))
(1(2
(1((2 3))4
(((((xyz)))))
(((((

```

### Nesting levels

We define a *nesting level* for a tinylisp expression as follows:

* Atoms and the empty list `()` have a nesting level of 0.
* A nonempty list has nesting level N+1, where N is the maximum nesting level of its items.

Some examples:

```
Expression   Nesting level
()           0
(1 2 3)      1
(1 2 ())     1
(1 (2))      2
(1 ((2)) 3)  3
((((()))))   4

```

### How to ungolf

To ungolf a tinylisp expression, first **supply any missing closing parentheses**. Then, **add newlines and whitespace** according to the following rules:

* For an expression of nesting level 0, do not add any whitespace.
* For a list of nesting level 1 or 2, make sure the elements of the list are separated by a single space.
* Lists of nesting level 3 or higher must be broken across multiple lines:
    + The first element of the list should be on the same line as the opening parenthesis, with no whitespace in between.
        - More specifically, the first element should *begin* on the same line. If the first item itself has nesting level 3 or higher, it will of course be spread over multiple lines itself.
    + IF the second element of the list has nesting level 0 or 1, place it on the same line as the first, with a space in between; otherwise, if its nesting level is 2 or higher, place it on its own line.
    + The third and subsequent elements of the list must each be on their own line.
* Elements on their own line must be indented by a number of spaces equal to how deeply they are nested in the expression. The top-level list should be indented 0 spaces, its elements 1 space, their elements 2 spaces, etc.
* The closing parenthesis at the end of a list should immediately follow the last element of the list, with no whitespace in between.

### A worked example

Suppose this is our input:

```
(d E(q((n)(i(l n 2)(s 1 n)(E(s n 2

```

First, supply missing close-parens:

```
(d E(q((n)(i(l n 2)(s 1 n)(E(s n 2))))))

```

The outermost list has nesting level 6, so it must be split over multiple lines. Its second element is `E` (nesting level 0), so we keep that on the same line. We place the third element on its own line, indented by one space.

```
(d E
 (q((n)(i(l n 2)(s 1 n)(E(s n 2))))))

```

The next list has nesting level 5. Its second element has nesting level 4, so it goes on its own line, indented by two spaces.

```
(d E
 (q
  ((n)(i(l n 2)(s 1 n)(E(s n 2))))))

```

The next list has nesting level 4. Its second element has nesting level 3, so it goes on its own line, indented by three spaces.

```
(d E
 (q
  ((n)
   (i(l n 2)(s 1 n)(E(s n 2))))))

```

The next list has nesting level 3. Its second element has nesting level 1, so it goes on the same line as the first element, separated by a space. We place the third and fourth elements on their own lines, indented by four spaces.

```
(d E
 (q
  ((n)
   (i (l n 2)
    (s 1 n)
    (E(s n 2))))))

```

The list `(s 1 n)` has nesting level 1 and thus goes on one line. It has spaces between its elements, so it is already ungolfed.

The list `(E(s n 2))` has nesting level 2 and thus goes on one line. It needs spaces between its elements.

Final result:

```
(d E
 (q
  ((n)
   (i (l n 2)
    (s 1 n)
    (E (s n 2))))))

```

## I/O requirements and clarifications

Your solution may be a program or function. You may use any of the default I/O methods.

Input must be a string, a list of characters, or the nearest equivalent in your language. You may not take input as a nested list; parsing the input is part of the challenge.

Output may be a multiline string; it may also be a list of strings, each string representing one line. It may optionally contain trailing spaces and/or leading or trailing newlines. It may not contain extra leading spaces.

The input will always represent a single (possibly nested) list. Thus, it will always start with `(`, never an atom. The number of opening parentheses will be greater than or equal to the number of closing parentheses. The input will not have any leading or trailing whitespace. The input will consist only of printable ASCII characters; in particular, it will not contain newlines or tabs.

## Reference solution

Here's a reference solution in Python 3: Try it online!

## Test cases

```
()
=>
()

(load library
=>
(load library)

(q(1 2
=>
(q (1 2))

(q((1)(2
=>
(q
 ((1) (2)))

(q '"""\
=>
(q '"""\)

(((((
=>
((((()))))

(d C(q((Q V)(i Q(i(l Q 0)0(i V(a(C(s Q(h V))V)(C Q(t V)))0))1
=>
(d C
 (q
  ((Q V)
   (i Q
    (i (l Q 0)
     0
     (i V
      (a
       (C
        (s Q (h V))
        V)
       (C Q (t V)))
      0))
    1))))

((q (g (c (c (q q) g) (c (c (q q) g) ())))) (q (g (c (c (q q) g) (c (c (q q) g) ())))))
=>
((q
  (g
   (c
    (c (q q) g)
    (c
     (c (q q) g)
     ()))))
 (q
  (g
   (c
    (c (q q) g)
    (c
     (c (q q) g)
     ())))))

(d f(q((x y z p)(i p(i(l p 0)(f(s x p)y(a z p)0)(i x(f(s x 1)(a y 1)z(s p 1))(i y(f x(s y 1)(a z 1)(s p 1))(f x y z 0))))(c x(c y(c z(
=>
(d f
 (q
  ((x y z p)
   (i p
    (i (l p 0)
     (f (s x p) y (a z p) 0)
     (i x
      (f (s x 1) (a y 1) z (s p 1))
      (i y
       (f x (s y 1) (a z 1) (s p 1))
       (f x y z 0))))
    (c x
     (c y (c z ())))))))

(def even? (lambda (num) (divides? 2 num)))
=>
(def even?
 (lambda (num) (divides? 2 num)))

(def odd? (lambda (num) (not (divides? 2 num))))
=>
(def odd?
 (lambda (num)
  (not (divides? 2 num))))

(def divides? (lambda (divisor multiple) (if (negative? divisor) (divides? (neg divisor) multiple) (if (negative? multiple) (divides? divisor (neg multiple)) (if (less? multiple divisor) (zero? multiple) (divides? divisor (sub2 multiple divisor)))))))
=>
(def divides?
 (lambda (divisor multiple)
  (if (negative? divisor)
   (divides? (neg divisor) multiple)
   (if (negative? multiple)
    (divides? divisor (neg multiple))
    (if (less? multiple divisor)
     (zero? multiple)
     (divides? divisor (sub2 multiple divisor)))))))

```

This is code-golf; the shortest answer in each language (in bytes) wins.

# Answer
> 22 votes
# tinylisp, 1022 bytes

```
(load library
(d ? contains?
(d r reverse
(d O last
(d _(q((S T C)(i S(i(e(h S)32)(_(t S)(i C(c(r C)T)T)())(i(?(q(40 41))(h S))(_(t S)(c(h S)(i C(c(r C)T)T))())(_(t S)T(c(h S)C))))(r(i C(c(r C)T)T
(d @(q((T A D)(i T(@(t T)(c(+(w T)D)A)(+(w T)D))(r(c(+(w T)D)A
(d w(q((T)(-(e(h T)40)(e(h T)41
(d #(q((T A)(i A(#(c 41 T)(- A 1))(r T
(d E(q((T)(max(@ T()0
(d p(q((L A)(i A(p(c 32 L)(- A 1))L
(d n(q((D T A)(i(l 0(h D))(n(t D)(t T)(c(h T)A))(r(c(h T)A
(d N(q((T)(n(@ T()0)T(
(d H(q((T A)(i T(i(*(e(h T)40)(e(cadr T)41))(H(t(t T))(c(q(40 41))A))(H(t T)(c(h T)A)))(r A
(d W(q((L)(i(c()L)L(c L(
(d :(q((I L)(i I(:(- I 1)(t L))L
(d ;(q((L)(:(s(last-index(r(@(r L)()0))1)1)L
(d }(q((D T)(i(l 0(h D))(}(t D)(t T))(t T
(d f(q((T S P)(i T(f(t T)(concat S(i(e(h T)41)(c 41())(i(+(l(E(N(concat(; P)T)))3)(*(not((q((T)(}(@ T()0)T)))(t(; P))))(l(E(N T))2)))(p(W(h T))(- 1(?(q(()40))(O P))))(i(e(O P)40)(W(h T))(c 10(p(W(h T))(O(@ P()0))))))))(insert-end(h T)P))S
(d F(q((S)(string(f(H((q((T)(#(r T)(last(@ T()0)))))(_(chars S)()()))())()(

```

Try it online!

This took several ~~hours~~ days, but now it actually works.

This emits a couple of errors, which I think are unavoidable, and now a lot more which are avoidable.

-18 thanks to DLosc.

Because tinylisp doesn't have string literals, you'll need to pass your input through this python script.

Ungolfed.

I only sorta understand this, but here's the basic algorithm the code follows:

* Convert the string to a list of characters for easier manipulation.
* Parse the string into a list of tokens

+ Parentheses are left on their own, other tokens are grouped into lists.
* Iterate through the string, keeping a list of the previous tokens:

+ If it's a `)`, immediately append it. Else:
    + If:
        - Backtrack through the previous tokens to the start of the parent expression.
        - Use this index to get the depth of the parent expression, is it less than 3?
    + *or*:
        - Backtrack to the parent expression
        - Remove the first parenthesis and remove the first expression after that.
        - Is it empty?
        - *and*:
            * is the current expression depth less than 2?
    + If so, this token should go on the same line, possibly with a space.
    + Else, it should be on a new line - get the depth of the current expression and indent by that.
* Finally, return the string.

# Answer
> 7 votes
# Python3, 629 bytes:

```
import re
d=lambda x,c=0:c if type(x)!=list or not x else max(d(i,c+1)for i in x)
def p(s):
 r=[];S=str.lstrip
 while s:
  if(c:=s[0])==')':s=S(s[1:]);break
  if c=='(':s=(l:=p(s[1:]))[1];r+=[l[0]]
  else:r+=[l:=re.findall('[^() ]+',s)[0]];s=S(s[len(l):])
 return r,S(s)
def f(r,t=0):
 j=lambda x:x if type(x)!=list else'()'
 k,s=[],0
 if all(d(i)<2 for i in r):k=[f(i,t+1)if d(i)else j(i)for i in r]
 else:
  for i,a in enumerate(r):
   D=d(a);F=f(a,t+1)if D else j(a)
   if not i:k+=[F]
   elif i==1 and D<2:k+=[F]
   else:k+=['\n'+' '*(t+1)+F]
 return'('+' '.join(k)+')'
g=lambda x:f(p(x+')'*((c:=x.count)('(')-c(')')))[0][0])

```

Try it online!

# Answer
> 6 votes
# Python 3, 388 bytes

Basically a golfed version of the reference solution @DLosc gave

```
import re
k=" "
def p(e,*t,l=0):
 for n in e:
  if")"==n:break
  if")">n:z=p(e);l=max(l,z[0]+1);t+=z,
  else:l=max(l,1);t+=n,
 return[l,*t]
t=p(iter(re.findall("[^() ]+|\S",input())[1:]))
def f(t,d=k):
 if[*t]==t:
  r="(";s=[f(i,d+k)for i in t[1:]]
  if t[0]>2:
   if len(t)>2and""in t[2]or t[2][0]<2:r+=s[0]+k;s=s[1:]
   q="\n"+d
  else:q=k
  return r+q.join(s)+")"
 return t
print(f(t))

```

Try it online!

The regex used in the code `[^() ]+|\S` is the a shorter way of writing the regex `[()]|[^() ]+` given in the question by 2 bytes

`[*t]==t` is a sneaky trick to cut back 6 bytes instead of `type(t)==list`

`""in t[2]` is another trick to cut down 7 bytes instead of `type(t[2])!=list`

-3 thx to @pxeger

-1 thx to @aidenchow

# Answer
> 4 votes
# Retina 0.8.2, 330 bytes

```
^((\()|(?<-2>\))|[^()])+
$&$#2$*)
[^ (](?=\()|\)(?=[^) ])
$&
{%`^(( *)\(+?([^() ]+ |((\()|(?<-5>\))|[^()])+(?(5)^) )+)(\(([^() ]+ |\(\) )*\([^)])
$1¶$2 $6
 ¶
¶
%+`^(( *)\(([^() ]+|((\()|(?<-5>\))|[^()])+(?(5)^))( [^() ]+| \([^()]+\))+)( [^() ]+| \([^()]+\))+$
$1¶$2$7
%+`^(( *)\(([^() ]+|((\()|(?<-5>\))|[^()])+(?(5)^))\))
$1¶$2

```

Try it online! Link includes test cases. Explanation:

```
^((\()|(?<-2>\))|[^()])+
$&$#2$*)

```

Use a .NET balancing group to count how many extra `(`s there are and append that many trailing `)`s.

```
[^ (](?=\()|\)(?=[^) ])
$&

```

Insert spaces before `(`s and after `)`s where necessary.

```
{`

```

Repeat until no more transforms can be made.

```
%`^(( *)\(+?([^() ]+ |((\()|(?<-5>\))|[^()])+(?(5)^) )+)(\(([^() ]+ |\(\) )*\([^)])
$1¶$2 $6
 ¶
¶

```

Split lists of nesting level 3 or more.

```
%+`^(( *)\(([^() ]+|((\()|(?<-5>\))|[^()])+(?(5)^))( [^() ]+| \([^()]+\))+)( [^() ]+| \([^()]+\))+$
$1¶$2$7

```

For those lists, where there are only lists of nesting level 0 or 1 left, put all but the first on their own line. (We need to check explicitly to ensure that the list was in fact split in the first place.)

```
%+`^(( *)\(([^() ]+|((\()|(?<-5>\))|[^()])+(?(5)^))\))
$1¶$2

```

Lists of nesting level 0 or 1 after a list of nesting level 2 or more also need to go on their own line. (We know they can't have also nesting level 2 or more because they would have been split off earlier, so we don't actually need to check their nesting level.)

# Answer
> 2 votes
# Charcoal, 166 bytes

```
⊞υ⟦⟧≔ωηＦ⁺θ×)⁻№θ(№θ)«Ｆ№( )ιＦ›ηω«⊞§υ±¹⟦η¹⟧≔ωη»≡ι ω(⊞υ⟦⟧)«≔∨⊟υ⟦⟦ω⁰⟧⟧ι≔∧⊖Ｌι›³§§ι¹±¹δ≔⌈Ｅι⊕⊟κζＦ›⁴ζ≔⊖Ｌιδ≔Ｅ§ι⁰⁺§ (¬λκεＦδ⊞ε⁺⁺⊟ε ⊟§ι⊕κＦΦι›λδＦκ⊞ε⁺ λ⊞ε⁺⊟ε)⊞εζ⊞§υ±¹ε»≔⁺ηιη»✂⊟⊟υ⁰±¹

```

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

```
⊞υ⟦⟧

```

Add a dummy container to the predefined empty list to hold the final result.

```
≔ωη

```

Start off with no atom.

```
Ｆ⁺θ×)⁻№θ(№θ)«

```

Append enough trailing `)`s to balance the input and loop over its characters.

```
Ｆ№( )ιＦ›ηω«⊞§υ±¹⟦η¹⟧≔ωη»

```

If the current character is one of `( )` then push any current token to the most recent expression. (Note that my nesting levels are one greater than those used by the question, because the nesting level of `()` evaluates to `1`.)

```
≡ι ω

```

If the current character is a space then do nothing more at this point.

```
(⊞υ⟦⟧

```

If the current character is a `(` then start a new subexpression.

If the current character is a `)`:

```
≔∨⊟υ⟦⟦ω⁰⟧⟧ι

```

Get the latest expression, or an empty token if there wasn't one. (Since this makes `()` contain an empty token with a nesting level of `0`, its nesting level evaluates to `1`.)

```
≔∧⊖Ｌι›³§§ι¹±¹δ

```

Calculate whether the second term should be concatenated to the end of the first.

```
≔⌈Ｅι⊕⊟κζ

```

Calculate the depth of this term.

```
Ｆ›⁴ζ≔⊖Ｌιδ

```

If this term is shallow enough then concatenate all the terms together.

```
≔Ｅ§ι⁰⁺§ (¬λκε

```

Indent the first term, except for the first line, which is prefixed with a leading `(` instead.

```
Ｆδ⊞ε⁺⁺⊟ε ⊟§ι⊕κ

```

Concatenate the desired number of terms to the first term.

```
ＦΦι›λδＦκ⊞ε⁺ λ

```

Indent and append any remaining terms.

```
⊞ε⁺⊟ε)

```

Append a final `)` to the last line.

```
⊞εζ

```

Append the nesting level to this term.

```
⊞§υ±¹ε

```

Append this term to its parent expression.

```
»≔⁺ηιη

```

For any other character, append it to the current token.

```
»✂⊟⊟υ⁰±¹

```

Output the pretty-printed expression, excluding its nesting depth.

---
Tags: code-golf, parsing, balanced-string, whitespace, lisp
---


# Question
Title: Compute the Digit Difference Sum of a Number
Consider taking some non-negative integer such as 8675309 and computing the absolute values of the differences between all the pairs of neighboring digits.

For \\$8675309\\$ we get \\$|8-6| = 2\\$, \\$|6-7| = 1\\$, \\$|7-5| = 2\\$, \\$|5-3| = 2\\$, \\$|3-0| = 3\\$, \\$|0-9| = 9\\$. Stringing these results together yields another, smaller non-negative integer: \\$212239\\$. Repeating the process gives \\$11016\\$, then \\$0115\\$, which by the convention that leading zeros are not written simplifies as \\$115\\$, which becomes \\$04\\$ or \\$4\\$, which can't be reduced any further. Summing all these values up we get \\$8675309 + 212239 + 11016 + 115 + 4 = 8898683\\$.

Let's define the Digit Difference Sum (or DDS) as this operation of repeatedly taking the digit differences of a number to form a new number, then adding all the resulting numbers to the original.

Here are the first 20 values in the corresponding DDS sequence:

```
N   DDS(N)
0   0
1   1
2   2
3   3
4   4
5   5
6   6
7   7
8   8
9   9
10  11
11  11
12  13
13  15
14  17
15  19
16  21
17  23
18  25
19  27

```

Here are the first 10000 values, the graph for which is quite curious:

Especially since it looks the same when you plot it to 1000 or even 100:

(I'd call it the dentist's staircase...)

# Challenge

Write a program or function that takes in a non-negative integer and prints or returns its DDS value. For example, if the input was `8675309`, the output should be `8898683`.

**The shortest code in bytes wins.**

# Answer
# Pyth, 17

```
s.ui.aM-VJjNTtJTQ

```

Try it here or run the Test Suite

### Explanation:

```
s.u            Q   # Cumulative reduce, i.e. getting the intermediate values of each reduce
                     step and returning them as a list, then sum the list
   i ... T         # Convert the resulting list of numbers into a base 10 number
   .aM             # Get the absolute value of each element of ...
      -VJjNTtJ     # Perform vector subtraction on the lists given by
        JjNT       # assign J the number we currently have converted to its base 10 digits
            tJ     # and J[1:]. e.x. for 123 we get J = [1,2,3] then we do
                   # zip(J,J[1:]) which gives [[1,2],[2,3]] then element wise subtract
                   # to get [-1, -1]

```
> 11 votes

# Answer
# Python 2, 73

Luckily, I managed to avoid any string operations.

```
t=lambda n:n>9and abs(n%10-n/10%10)+10*t(n/10)
g=lambda n:n and n+g(t(n))

```

`g` is the function that computes the answer.
> 17 votes

# Answer
# Matlab, 101 ~~105~~ bytes

Thanks a lot to @beaker for his suggestion to use `polyval` instead if `base2dec`. That allowed me to

* save 4 bytes;
* greatly simplify the generalization to arbitrary base (see below) and save 22 bytes there; and most of all,
* helped me realize that the code for the general case was wrong (leading zeros were not being removed). The code and the graphs are correct now.

Code:

```
function y=f(y)
x=+num2str(y);while numel(x)>1
x=polyval(abs(diff(x)),10);y=y+x;x=+dec2base(x,10);end

```

Example:

```
>> f(8675309)
ans =
     8898683

```

## Bonus: arbitrary base

A small generalization allows one to use an arbitrary number base, not necessarily decimal:

* Arbitrary base from 2 to 10, **~~108~~ 104 bytes**

```
function y=f(y,b)
x=+dec2base(y,b);while numel(x)>1
x=polyval(abs(diff(x)),b);y=y+x;x=+dec2base(x,b);end

```

The reason why this works only for base up to `10` is that Matlab's `dec2base` function uses digits `0`, `1`, ..., `9`, `A`, `B`, ..., and there's a jump in character (ASCII) codes from `9` to `A`.
* Arbitrary base from 2 to 36, **124 ~~146~~ bytes**

The jump from `9` to `A` referred to above needs special treatment. The maximum base is `36` as per Matlab's `dec2base` function.

```
function y=f(y,b)
x=+dec2base(y,b);x(x>57)=x(x>57)-7;while numel(x)>1
x=abs(diff(x));x=x(find(x,1):end);y=y+polyval(x,b);end

```

This is how the dentist's staircases look for different bases:
> 16 votes

# Answer
# CJam, ~~22~~ 21 bytes

```
ri_{\s2ew::-:zsi_@+}h

```

Note that this program exits with an error, which is allowed by default.

With the Java interpreter, errors can be suppressed by closing STDERR. If you try this code online in the CJam interpreter, ignore all output before the last line.

*Thanks to @Sp3000 for pointing out an error in the original revision.*

*Thanks to @MartinBüttner for golfing off 1 byte.*

### Example run

```
$ cjam digit-difference.cjam 2>&- <<< 8675309
8898683

```

### How it works

```
ri_   e# Read an integer (I) from STDIN and push a copy (A).
{     e# Do:
  \   e#   Swap I on top of A.
  s   e#   Cast I to string.
      e#   For example, 123 -> "123".
  2ew e#   Push the overlapping slices of length 2 (pair of adjacent digits).
  ::- e#   Replace each pair by its difference.
  :z  e#   Apply absolute value to each difference.
  si  e#   Cast to string, then to integer. This is the new I.
      e#   For example, [1 2 3] -> "123" -> 123.
  _   e#   Push a copy of I.
  @   e#   Rotate A on top of the copy of I.
  +   e#   Add I to A, updating A.
}h    e# While A is truthy, repeat the loop.

```

**A** will always be truthy when checked by `h`. However, once **I** is a single-digit integer, `2ew` will fail with an error after consuming the array it was called on. This leaves only the desired result on the stack, which is printed before exiting.
> 11 votes

# Answer
# Labyrinth, ~~176~~ ~~134~~ ~~127~~ ~~119~~ ~~103~~ ~~97~~ ~~88~~ ~~82~~ ~~79~~ ~~76~~ 72 bytes

*Thanks to Sp3000 for saving 1 byte and paving the way for 2 more.*

This could probably still be shortened, but hey, it beats ~~Java~~ ~~Matlab~~ Python...

```
?
_
)/:}+{:`};!
9       "
_ :}-"" :_10
;;{: `" "  :
  {  (_:/=%}
  0+;`"

```

Try it online.

This terminates with an error but the error message is written to STDERR (which is why you don't see it in TIO).

The implementation is fairly straight-forward. We add the current value to a running total. If the current value was greater than `9`, we compute its base-10 digits (via repeated div-mod), and form a new number from the absolute differences. If we get to `9` or less, we print the running total.

The digits of the current number are collected on the auxiliary stack with the most significant digit on top.

Well, the fancy implementation of `abs(...)` I had here turned out to be ridiculously complicated compared to the new solution... I'll add an updated explanation when I'm done golfing this further.
> 11 votes

# Answer
# Julia 0.4, ~~81~~ 60 bytes

```
n->(s=n;while n>9 s+=n=int(join(abs(diff(["$n"...]))))end;s)

```

Ungolfed:

```
function f(n::Int)
    # Initialize a sum to the input
    s = n

    while n > 9
        # Get absolute values of the pairwise differences of the
        # digits of n, join as a string, convert it to an integer,
        # and reassign n
        n = int(join(abs(diff(["$n"...]))))

        # ["$n"...] actually splits n as a string into a vector
        # of its characters, but the difference between ASCII
        # codes is the same as the difference between the numbers
        # so it works as expected

        # Add the new n to the running sum
        s += n
    end

    # Return the sum
    return s
end

```

Try it online!

Saved 21 bytes thanks to feersum and Glen O!
> 6 votes

# Answer
## Java - 300 bytes

Golfed Version

```
static Long t=new Scanner(System.in).nextLong();static char[]c=t.toString().toCharArray();public static void main(String[]z){while(c.length>1)s();System.out.print(t);}static void s(){String s="";for(int i=0;i<c.length-1;)s+=Math.abs(c[i]-c[++i]);Long a=new Long(s);t+=a;c=a.toString().toCharArray();}

```

Ungolfed / Full version

```
import java.util.Scanner;

public class DigitDifference {

    static Long t = new Scanner(System.in).nextLong();
    static char[] c = t.toString().toCharArray();

    public static void main(String[] args){
        while( c.length > 1 )
            s();
        System.out.print(t);
    }

    static void s(){
        String s="";
        for(int i = 0; i < c.length-1;)
            s += Math.abs(c[i]-c[++i]);
        Long a = new Long(s);
        t += a;
        c = a.toString().toCharArray();
    }
}

```
> 5 votes

# Answer
# oK, ~~37~~ ~~32~~ ~~24~~ 23 bytes

```
+/(10/{%x*x}1_-':.:'$)\

```

In action:

```
  +/(10/{%x*x}1_-':.:'$)\8675309
8898683

  (+/(10/{%x*x}1_-':.:'$)\)'!20
0 1 2 3 4 5 6 7 8 9 11 11 13 15 17 19 21 23 25 27

```

K5 has a few features which are well suited to this- "encode" and "decode" can perform base conversion, each-pair (`':`) pairs up sequential elements in a list and fixed point scan (`\`) can produce the iterated sequence until it stops changing. The lack of a primitive `abs()` leads to some unsightly bulk in the form of `{(x;-x)x<0}'`, though.

## Edit:

Instead of `{(x;-x)x<0}'`, I can (somewhat wastefully) take the square root of the square of the sequence (`{%x*x}`, saving 5 bytes.

## Edit 2:

Inspired by @maurinus' APL solution, I can replace the "decode" (`((#$x)#10)\x`) with evaluating each character of the string representation of the number- `.:'$x`! This also lets me use a tacit form of the whole expression, saving additional characters.
> 5 votes

# Answer
## Python 2, 87 bytes

```
f=lambda n:n and n+f(int('0'+''.join(`abs(int(a)-int(b))`for a,b in zip(`n`,`n`[1:]))))

```

Recursively adds the current number and takes the digits differences. Lots of converting between numbers and strings. Probably can be improved.
> 4 votes

# Answer
# Mathematica, ~~72~~ ~~69~~ 65 bytes

```
Tr@FixedPointList[FromDigits@*Abs@*Differences@*IntegerDigits,#]&

```

I'm open to suggestions here.
> 4 votes

# Answer
# Julia, ~~55~~ 48 bytes

```
h=n->(n>9&&h(int(join(abs(diff(["$n"...]))))))+n

```

Ungolfed:

```
function h(n)
  if n>9
    # If multiple digits, find the digit difference...
    digitdiff=int(join(abs(diff(["$n"...]))))
    # ... recurse the function...
    downsum=h(digitdiff)
    # ... and return the sum so far (working up from the bottom)
    return downsum+n
  else
    # If single digit, no further recursion, return the current number
    return n
  end
end

```

Essentially, this recurses down to the single-digit level (where no digit difference can be performed), then sums back up as it exits the recursion, level by level.
> 4 votes

# Answer
# APL (22)

```
{⍵≤9:⍵⋄⍵+∇10⊥|2-/⍎¨⍕⍵}

```

Explanation:

* `⍵≤9:⍵`: if ⍵ ≤ 9, return ⍵ unchanged.
* `⍎¨⍕⍵`: convert ⍵ to a string, then evaluate each character
* `2-/`: subtract every two adjacent numbers
* `|`: take the absolute values
* `10⊥`: turn the array into a base-10 number
* `⍵+∇`: call the function recursively with this new value, and add the result to the input
> 4 votes

# Answer
# Haskell, 140 bytes

`d` does the job.

```
import Data.Char
d n=sum.m(read.m intToDigit).fst.span(/=[]).iterate s.m digitToInt.show$n
s l@(h:t)=snd$span(==0)$m abs$zipWith(-)l t
m=map

```

Does anyone know how to avoid importing the long conversion functions?
> 3 votes

# Answer
# K5, 50 bytes

```
+/{(r;x)@~r:.,/"0",{$(0;-r;r)@(~^r)+0<r:x-y}':$x}\

```
> 3 votes

# Answer
# Python 3, 125 bytes

I used to like the shortness of regex until I tried to use it for this challenge...`re.findall('\d\d',s,overlapped=True)` is *not* on ;)

```
s=input()
p=int
x=p(s)
while p(s)>9:g=str(s);s=p(''.join(str(abs(p(g[i])-p(g[i+1])))for i in range(len(g)-1)));x+=s
print(x)

```

Cheers @Todd :)
> 2 votes

# Answer
# JavaScript ES6, 73 bytes

```
t=n=>(b=10,M=Math).ceil(n&&n+t((j=n=>n>9&&M.abs(n%b-n/b%b)+b*j(n/b))(n)))

```

This isn't getting any shorter :/ I'll try more approaches but this is the shortest one so far
> 2 votes

# Answer
# JavaScript (ES6), 69

Test running the snippet below in an EcmaScript 6 compliant browser (but not Chrome as it still does not support the spread operator `...`) MS Edge maybe?

```
f=n=>n&&(n+=r='',[...n].map(d=>(r+=d>p?d-p:p-d,p=d),p=n[0]),+n+f(+r))

function test()
{
  var i=+I.value
  O.innerHTML = i+' -> '+f(i) + '\n' + O.innerHTML
}
```

```
<input id=I value=8675309><button onclick=test()>-></button>
<pre id=O></pre>
```

Alternative, using *array comprehension* that is now targeted EcmaScript 2016 (ES7), 67 bytes:

```
f=n=>n&&(n+=r='',p=n[0],[for(d of n)(r+=d>p?d-p:p-d,p=d)],+n+f(+r))

```
> 2 votes

# Answer
# Vyxal, ~~12~~ 7 bytes

```
≬¯ṅ⌊İ∑+

```

Try it Online!

*-5 bytes thanks to allxy*

## How?

```
≬¯ṅ⌊İ∑+ # full program
≬¯ṅ⌊    # Three element lambda
 ¯      # Deltas (consecutive differences of digits)
  ṅ     # Join by nothing
   ⌊    # Convert to integer
    İ   # Apply this lambda on the (implicit) input and collect unique values
     ∑  # Summate
      + # Add to (implicit) input

```
> 2 votes

# Answer
# Perl 5 `-p`, 49 bytes

```
$\+=$_;s/.(?=(.))/abs$&-$1/ge;s/^0+|.$//g&&redo}{

```

Try it online!
> 2 votes

# Answer
# J, 70 bytes

```
 +/([:10&#.[:(2|@:-/\])[:10&(]#:~[#~[:>.[^.])])`]@.(11&>)^:a:".(1!:1)3

```
> 1 votes

# Answer
## MATLAB ~~(141)~~(137)

> **EDIT:** 4 bytes less, thanks to @Andras

```
function[s j]=n(T,b,c),if(T/b>9),u=fix(T/10);[x e]=n(T,b*10,0);y=n(u,b,0);[w z]=n(u,b,c);s=abs(x-y);j=s+e+10*c*z;else,s=mod(T,10);j=s;end

```
* This doest beat @LuisMendo 's answer but atleast I could reduce execution time, which by, I would have just tried to diversify ways of tackling this problem.
* I could reduce it more but as I go for less time, i waste more bytes, so here is the principle:

The program is summing up digits of same row before inlined digits , it does mean it used integer division "n/10" log\_10(n) times only, complexity is O(N).

If `n= a b c d`

```
a          b           c           d
   |a-b|       |b-c|       |c-d|
    ||a-b|-|b-c|| ||b-c|-|c-d||
   ....

```

My program calculates:

```
a+|a-b| + | |a-b|-|b-c| |  +  |  | |a-b|-|b-c| | - | |b-c|-|c-d| |  |
+10*(
b+|b-c| + | |b-c|-|c-d| |
+10*(
c+|c-d|
+10*(
d
)
)
)

```

## Usage:

```
  [a b]=n(13652,1,1)

```

a =

1

```
 b =

   16098

```
> 1 votes

# Answer
# Prolog, 143 bytes

**Code:**

```
q(X,N):-X<9,N=0;A is abs(X mod 10-X//10 mod 10),Y is X//10,q(Y,M),N is A+M*10.
r(X,N):-X<9,N=X;q(X,Y),r(Y,M),N is X+M.
p(X):-r(X,N),write(N).

```

**Explained:**

```
q(X,N):-X<9,N=0;                                                         % If only one digit, the difference is 0
        A is abs(X mod 10-X//10 mod 10),Y is X//10,q(Y,M),N is A+M*10.   % Else, the difference is the difference between the last 2 digits + the recursive difference of the number without the last digit
r(X,N):-X<9,N=X;                                                         % If we only have 1 digit the final answer is that digit
        q(X,Y),r(Y,M),N is X+M.                                          % Else, the final answer is the current number + the recursive difference of that number
p(X):-r(X,N),write(N).

```

**q** does the calculations that convert a number into it's Digit Difference.
**r** recursively calls **q** and sums up the results to find the Digit Difference Sum.
**p** is the entry point. Takes a number, calls **r** and prints the answer.
**Example:**

```
>p(8675309).
8898683

```

Try it online here.
> 1 votes

# Answer
# PHP - 198 bytes

```
<?$x=$t=$_GET['V'];function z($x){global$t;for($i=0;$i<strlen($x)-1;$i++){$z=str_split($x);$r.=str_replace('-','',$z[$i]-$z[$i+1]);}$r=ltrim($r,'0');$t+=$r;return strlen($r)>1?z($r):0;}z($x);echo$t;

```

Ungolfed

```
<?
$x=$t=$_GET['V']; // Gets the value from input
function z($x){
    global$t;
    for($i=0;$i<strlen($x)-1;$i++){
        $z=str_split($x); //Turns the string into an array
        $r.=str_replace('-','',$z[$i]-$z[$i+1]); // Sums the two values and removes the minus signal
    }
    $r=ltrim($r,'0'); // Remove trailing zeroes
    $t+=$r; // Adds to global var
    return strlen($r)>1?z($r):0; // Checks the size of the string. If >1, calls the function again
}

z($x);
echo$t;

```
> 1 votes

# Answer
## Perl 6, 56 bytes

```
{[+] $_,{+.comb.rotor(2=>-1)».map((*-*).abs).join}…0} # 56 bytes

```

usage:

```
my &code = {...} # insert code from above

(180..190).map: &code;
# (259 258 259 260 261 262 263 264 265 266 280)

say code 8675309; # 8898683

```
> 1 votes

# Answer
# Jelly, 6 bytes

```
ạƝḌ$ƬS

```

Try it online!

## How it works

```
ạƝḌ$ƬS - Main link. Takes an integer n on the left
   $Ƭ  - Repeat the following until a repeated value, collected intermediate results:
 Ɲ     -   Convert an integer to digits, and on overlapping pairs:
ạ      -     Take the absolute difference
  Ḍ    -   Convert from digits to an integer
     S - Take the sum of these values

```
> 1 votes

# Answer
# Husk, 8 bytes

```
ΣU¡ȯdẊ≠d

```

Try it online!
> 1 votes

# Answer
# Japt `-x`, ~~9~~ 8 bytes

```
Èìä'a}hN

```

Try it
> 1 votes

# Answer
# Factor \+ `math.extras project-euler.common`, ~~83~~ 81 bytes

```
[ 0 swap [ [ + ] keep number>digits differences vabs digits>number ] until-zero ]

```

Attempt This Online!

* `0 swap` Initialize the sum.
* `[ ... ] until-zero` Call a quotation until its result is 0, dropping the 0 from the stack.
* `[ + ] keep` Add the current summand to our sum.
* `number>digits differences vabs digits>number` Get the next summand.
> 1 votes

# Answer
# C 162 bytes

golfed:

```
main(int argc,char **argv){char *c=argv[1];int u=atoi(c),d;do{while(c[1]!=0){*c=abs(*c-*(c+1))+48;c++;}*c=0;c=argv[1];d=atoi(c);u+=d;}while(d>9);printf("%d",u);}

```

ungolfed:

```
main(int argc, char **argv)
{
    char *c=argv[1];
    int u=atoi(c),d;

    do
    {
        while(c[1]!=0)
        {
            *c=abs(*c-*(c+1))+48;
            c++;
        }

        *c=0;
        c=argv[1];
        d=atoi(c);
        u+=d;
    }
    while(d>9);

    printf("%d\n",u);
}

```
> 0 votes

# Answer
# R, 134 Bytes

### Code

```
f=function(x){z=x;while(z>9){n=seq(nchar(z));z=abs(diff(strtoi(substring(z,n,n))));z=sum(z*10**(rev(seq(length(z)))-1));x=x+z};cat(k)}

```

Test it online.

### Ungolfed

```
f=function(x){
  z=x;
  while(z>9){
    n=seq(nchar(z));
    z=abs(diff(strtoi(substring(z,n,n))));
    z=sum(z*10**(rev(seq(length(z)))-1));
    x=x+z
  };
  cat(x)
}

```

Here is the plot of the difference of the "Digit Difference Sum of a Number" series from f(1) to f(1m). Just because I love to diff.

### Plot code

```
s <- seq(1,100000)
serie <- sapply(s,f)
plot(diff(ts(serie)),xlab="",ylab="")

```
> 0 votes

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

```
λ£üαJï}þO

```

Try it online or verify the first 1001 test cases.

**Explanation:**

Unfortunately the *Cumulative fixed-point* builtin  (to reduce until the result no longer changes and collecting all intermediate results) won't include the starting value. In addition, we'll have to remove the trailing empty string value. So it would be 10 bytes: `.ΓüαJï}¨O+` \- try it online.

So using this unorthodox method with the recursive environment saves a byte in the end:

```
λ      # Start a recursive environment,
 £     # to calculate the values in the range [a(0),a(implicit input)]
       # Starting with a(0) = (implicit) input
       # Where every following a(n) is calculated as:
       #  (implicitly push a(n-1))
  ü    #  For each overlapping digit:
   α   #   Get the absolute difference
    J  #  Join these differences together to a string
     ï #  Remove potential leading 0s (by casting to an integer)
}      # After the recursive environment
 þ     # Remove all empty trailing strings by only keeping numbers
  O    # Sum those numbers together
       # (which is output implicitly as result)

```
> 0 votes

# Answer
# Julia 1.4, 47 bytes

```
!n=n+(n>9&&!evalpoly(10,abs.(diff(digits(n)))))
```

Attempt This Online!
> 0 votes

---
Tags: code-golf, arithmetic, sequence
---


title: 1D Hopping Array Maze

text:
# Question
Title: 1D Hopping Array Maze
*Inspired by We do tower hopping and related to 2D Maze Minus 1D*

# Introduction

Your task is to find the shortest path to get out of an array maze following specified rules.

# Challenge

A 1D array *a* with *n* elements can be regarded as a maze composed of *n* points, where point with index *k* is connected to the points with *k*+*a*\[*k*\] and *k*-*a*\[*k*\] in a one-way manner. In other words, you can jump forward or backward exactly *a*\[*k*\] steps from the point with index *k*. Points with an index outside the bounds of the array are considered outside the maze.

To illustrate this, consider the following array,

```
[0,8,5,9,4,1,1,1,2,1,2]

```

If we are at the 5th element right now, since the element is 4, we can hop 4 steps forward to the 9th element, or 4 steps backward to the 1st element. If we do the latter, we end up with the element 0, which indicates no further moves are possible. If we do the former, since the 9th element is 2, we can choose to hop to the 11th element, which is again a 2, and then we can hop again to the "13th element", which is out of the bounds of the array and considered an exit to the maze.

So if we start from the element in the middle, one way to get out of the maze is hopping 1 step back, 4 steps forward, 2 steps forward and again 2 steps forward, which can be expressed as the array `[-1,4,2,2]`. Alternatively you can express it with the array `[4,8,10,12]` which records the zero-based index of all intermediate and final points (1-based index is also fine), or just the signs, `[-1,1,1,1]`.

Escaping the maze from the low-index end is also OK.

Using the first notation and starting from the same element, `[1,1,1,2,2]` is also a solution but it is not optimal since there are 5 steps instead of 4.

The task is to find out the shortest path to get out of the array maze and output the path. If there are more than one optimal paths, you can output any or all of them. If there are no solution, you should output a falsy value chosen by you that is discernible from a valid path (producing no output at all is also OK).

For simplicity, the number of elements in the array is always an odd number and we always start from the element in the middle.

# Test cases

The test cases illustrates various forms of output, but you are not limited to these.

```
Input
Output

[0,8,5,9,4,1,1,1,2,1,2]
[-1,4,2,2]

[2,3,7,1,2,0,2,8,9]
[2,9] (or [2,-5] or [[2,9],[2,-5]])

[0,1,2,2,3,4,4,4,3,2,2,3,0]
[1,-1,1,1]

[0,1,2,2,4,4,6,6,6,6,6,4,2,1,2,2,0]
[]

```

# Specs

* You may write a function or a full program.
* The array only contains nonnegative integers.
* You can take input and output through any standard form, but please specify in your answer which form you are using.
* This is , the lowest number of bytes wins.
* As usual, default loopholes apply here.

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

Returns an array of 0-indexed intermediate and final points, or an empty array if no solution exists.

```
a=>(g=(x,p,d=a[x])=>1/d?[d,-d].map(d=>p.includes(X=x+d)||g(X,[...p,X])):o=o==''|o[p.length]?p:o)(a.length>>1,o=[])&&o

```

Try it online!

### Commented

```
a =>                        // given the maze a[]
(g = (                      // g = recursive function taking:
  x,                        //   x = current position
  p,                        //   p[] = list of visited cells
  d = a[x]                  //   d = value of current cell
) =>                        //
  1 / d ?                   // if d is defined:
    [d, -d].map(d =>        //   for d and -d:
      p.includes(X = x + d) //     if the cell at X=x+d was not yet visited,
      || g(X, [...p, X])    //     do a recursive call to g at this position
    )                       //   end of map()
  :                         // else:
    o =                     //   update o:
      o == '' |             //     if o was empty
      o[p.length] ?         //     or p is shorter than o:
        p                   //       set o to p
      :                     //     else:
        o                   //       let o unchanged
)(a.length >> 1, o = [])    // initial call to g(), starting in the middle
&& o                        // return o

```

# Answer
> 3 votes
# Husk, 22 bytes

```
ḟȯ¬€ŀ¹FS+o*!¹⌈½L¹ṁπṡ1ŀ

```

Returns a list of signs, or an empty list if a solution does not exist. Try it online!

## Explanation

This is a brute-force solution that checks lists over `-1,0,1` of increasing length, and returns the first one that results in a jump out of the array. Since it is of minimal length, it will not contain 0s.

```
ḟȯ¬€ŀ¹FS+o*!¹⌈½L¹ṁπṡ1ŀ  Implicit input, say A = [0,1,1]
                     ŀ  Indices of A: [1,2,3]
                 ṁ      Map over them and concatenate:
                  π      Cartesian power
                   ṡ1    of the symmetric range [-1,0,1].
                        Result is B = [[-1],[0],[1],[-1,-1],...,[1,1,1]]
ḟ                       Find the first element of B that satisfies this:
                         Argument is a list, say C = [1,-1].
      F                  Reduce C from the left
             ⌈½L¹        using ceil(length(A)/2) as the initial value
       S+o*!¹            with this function:
                          Arguments are an index of A, say I = 2, and a sign, say S = 1.
           !¹             The element of A at I: 1
         o*               Multiply by S: 1
       S+                 Add to I: 2
                         At the end of the reduction, we have a number I, here 2.
   €ŀ¹                   Is it an element of the indices of A: Yes.
 ȯ¬                      Negate: No.
                        The result is the shortest list C for which I is outside of A.

```

# Answer
> 2 votes
# Python 3, 195 188 179 bytes

```
def f(a):
 v=len(a);x,*s={v//2},[v//2]
 while all(v>b>-1for*c,b in s)*s:s=[x.add(u)or c+[b,u]for*c,b in s for u in[b+a[b],b-a[b]]if{u}-x]
 return[b[1:]for b in s if not-1<b[-1]<v]

```

Try it online!

**Edit:**

* Saved 9 bytes by `all(..)and s => all(..)*s`, `if u not in x => if{u}-x`
The former exploits `boolean * list == int * list`, the latter uses set difference (empty set is also falsy).

Output format: Nested array of all optimal answers, given as zero-based indices of intermediate and final points.

For example: `f([0,8,5,9,4,1,1,1,2,1,2]) == [[4, 8, 10, 12]]`.

The algorithm is simple BFS. `s` records all possible `i`-length paths on `i`th iteration, excluding the indices already visited. Note that the extended star notation is (ab)used because repeated array access is expensive. I found that such a notation can also reduce some whitespace if used correctly.

I also made a recursive (but longer) version out of the above solution. Both `s and` and `or s` are needed, otherwise it doesn't work.

# Python 3, 210 bytes

```
lambda a:[b[1:]for b in g(a,[[len(a)//2]],{len(a)//2})if not-1<b[-1]<len(a)]
g=lambda a,s,x:s and all(-1<b<len(a)for*c,b in s)and g(a,[x.add(u)or c+[b,u]for*c,b in s for u in[b+a[b],b-a[b]]if u not in x],x)or s

```

Try it online!

# Answer
> 2 votes
# Haskell, ~~207~~ 202 bytes

5 bytes saved thanks to BMO.

```
l=length
x!p|i<-h p,d<-x!!i=[p++[x]|x<-[(-d,i-d),(d,i+d)],x`notElem`p]
x?p|i<-h p=i<0||i>=l x
h=snd.last
x#[]=[]
x#p|l(x%p)<1=x#(p>>=(x!))|1>0=x%p
(%)=filter.(?)
f x=(tail.map fst)<$>x#[[(0,l x`div`2)]]

```

Try it online!

This is a function that takes a list of `Int` as a parameter and returns a list of paths where each path is a list of relative jumps taken to get out of the array.

The ungolfed version:

```
move :: [Int] -> [(Int, Int)] -> [Path]
move xs path = map(\x->path++[x]) $ filter (\s -> s`notElem`path) $ [(-delta, i-delta), (delta, i+delta)]
  where (_,i) = last path
        delta = xs!!i :: Int

outside :: [Int] -> Path -> Bool
outside xs paths = i < 0 || i >= length xs
  where (_,i) = last paths

shortest' :: [Path] -> [Int] -> [Path]
shortest' paths xs | null paths       = []
                   | not (null ready) = ready
                   | otherwise        = shortest' paths' xs
                   where ready  = filter (outside xs) paths
                         paths' = concatMap (move xs) paths

shortest xs = map tail $ map (map fst) $ shortest' [[(0,length xs`div`2)]] xs

```

# Answer
> 2 votes
# C (gcc), 269 bytes

```
#define A n){for(printf("%d,",n);i^l[i];i=l[i])printf("%d,",x[i]);break;}if(!u[n]){u[n]=x[m]=n;l[m++]=i;
#define M calloc(r,sizeof(s))
*x,*u,*l,s,m=1,i,j,n,w;main(r,v)char**v;{s=r-1;x=M;u=M;l=M;for(*x=1+s/2;i<m;i++){j=x[i];if(w=atoi(v[j])){n=j+w;if(s<A}n=j-w;if(1>A}}}}

```

Try it online!

Initially tried a recursive backtracking search, because using `main` for recursion is always fun. In the end though a straightforward non-recursive breadth-first search was able to be made smaller, which is what this version is. This program takes the input array as command-line arguments, with no braces, e.g. `0 8 5 9 4 1 1 1 2 1 2` for the first provided example. The program outputs on stdout a list of *1-indexed*, comma-delimited array indices in reverse order, starting from the final, out-of-bounds/'escaped' index and working back through the intermediate indices reached (it does not output the center, starting index). The program does not output braces around the array and leaves a trailing comma because separate `printf` statements take a lot of characters. The output corresponding to the first test example above is `13,11,9,5,`, for example.

If there is no escape route from the array maze, the program does not output anything.

Degolfed and explained it is below (heavily degolfed with some changes for readability):

```
int *x, *u, *l, s, m = 1, i, j, n, w;                        //Declare all the state we'll need
int main(r, v) char** v;{
    s = r - 1;                                               //s is our actual array size, since v[0] is the program name.
    x = calloc(r, sizeof(int));                              //x is an array that will form our BFS queue. Since it is a BFS we've no need to visit any elements more than once (first visit will have been on a shortest route to it), so the amount of space we have here should suffice.
    u = calloc(r, sizeof(int));                              //u is an array that will be used to flag when an array index has been visited; only reason it's int* is for ease of declaration
    l = calloc(r, sizeof(int));                              //l is an array that will be used parallel to x and stores backpointers in the form of indexes into x, which will be used to construct the actual path once it is found.
    x[0] = 1 + (s/2);                                        //Init the first element in the queue to our center index of the array, adding one because of the program name in v/argv.
    for(; i < m; i++) {                                      //m is the number of elements in our BFS queue. It starts at 1 and grows during iteration; if this loop terminates before finding a path there is none.
        j = x[i];                                            //Current index in the array we are examining
        if (w = atoi(v[j])) {                                //Set w to be the actual array value at the current index (and check that it's nonzero since if it isn't we can't get anywhere from here)
            n = j + w;                                       //Try a move in the positive direction
            if (n > s) {                                     //If the move escapes the array
                for(printf("%d,", n); i ^ l[i]; i = l[i]) {  //Print the location escaped to and then loop back through the backpointers to reconstruct the path. The only backpointer that will point to its own queue index is the starting one, so terminate there.
                    printf("%d,", x[i]);                     //Print each intermediate array index
                }
                break;                                       //Then break the outer for loop and exit.
            }
            if(!u[n]) {                                      //If the jump didn't take us out of the array and we haven't visited where it goes to, add it to the queue.
                u[n] = x[m] = n;                             //m is the current tail of the queue, so put this new location there. Since we're 1-indexed and if n was zero we'd have escaped, we know it isn't so can use it to mark this index as visited also.
                l[m++] = i;                                  //Also set the backpointer for this new queue element to point back to the current index, then increment the tail of the queue.
            }
            n = j - w;                                       //Now the backwards move
            if (n < 1) {                                     //Repeat analogous to the forward case.
                for(printf("%d,", n); i ^ l[i]; i = l[i]) {
                    printf("%d,", x[i]);
                }
                break;
            }
            if (!u[n]) {
                u[n] = x[m] = n;
                l[m++] = i;
            }
        }
    }
}

```

As usual for golfed C code, compilation output will of course include a friendly wall of warnings and notes.

# Answer
> 1 votes
# Perl 5, -a: 73 bytes

(old style counting: 75 bytes, `+1` for `a` and `+1` for replacing `-//` by `-/$/` and using `$`` for `$'`)

```
#!/usr/bin/perl -a
use 5.10.0;
@;=$#F/2;$v{$^H=$_}//=push@;,map$'+$_*($F[$^H]//1/!say$').$".$',-//,1for@

```

Give the input array as one line on STDIN e.g. `0 8 5 9 4 1 1 1 2 1 2`

prints the visited positions in reverse order including the starting point, then crashes

Prints nothing if there is no solution

Try it online!

# Answer
> 1 votes
# Ruby, 102 bytes

```
->a{b=[[a.size>>1]];b.map{|x|(v=a[w=x[0]])&&w>=0?[w-v,w+v].map{|j|x.index(j)?0:b<<[j]+x}:(break p x)}}

```

Try it online!

Takes input maze as an array, outputs by printing the escape path in reverse, from the exit to the starting point (inclusive). Prints nothing if there is no escape.

This approach misuses the map method to iterate through a temporary array storing the history of paths, which is constantly extended on the fly whenever there is another possible step to take.

In principle, I could save another byte by using `return x` instead of `break p x`, but that would mean claiming that my falsy value is equal to all the monstrous rubbish stored in `b`. Probably, this would be too much, even considering the allowed flexibility of the output...

## Walkthrough

```
->a{
  b=[[a.size>>1]] #Initialize an array of paths with our starting point index
  b.map{|x|       #Iterate through this array
    (v=a[w=x[0]]) #w is the current point in the path, v is its array value
    &&w>=0        #Ruby's support for negative indexing costs us 6 bytes :(
    ?             #If we are still within the bounds of the maze
      [w-v,w+v].map{|j| #Try moving in both directions
        x.index(j)? #If we have been there before, or stuck on zero
        0         #This is a dead-end, just assign a throwaway value
        :b<<[j]+x #Otherwise push the elongated path on top of our iterator
      }
    :(break p x)  #Escaped! Exit the loop and report the path
  }
}

```

# Answer
> 0 votes
# Python 3, 133 bytes

```
def f(k,*s):*p,x=len(k)//2,*s;return{x}-{*p}and min([a for a in(f(k,*s,x-k[x]),f(k,*s,x+k[x]))if a]or[()],key=len)if~0<x<len(k)else s

```

Try it online!

Outputs the shortest list of all visited indices.

Port of my answer to Find the shortest route on an ASCII road.

---
Tags: code-golf, array, optimization, maze
---