title: AoCG2021 Day 20: Wonky license check

text:
# Question
Title: AoCG2021 Day 20: Wonky license check
Part of **Advent of Code Golf 2021** event. See the linked meta post for details.

Related to AoC2018 Day 8.

---

The license file for an imaginary software system is defined as follows:

* The entire file is a sequence of non-negative integers.
* The entire file defines a *tree* of nodes.
* Each node in the tree has the following fields in the order:
    + Header, a single number indicating the number of child nodes.
    + Zero or more child nodes, as specified in the header.
    + Zero or more metadata entries (each being a single integer), as specified in the footer.
    + Footer, a single number indicating the number of metadata entries.

Hmm, does it really work? It should, because it is your job to validate the given license file!

An example of a valid license file:

```
2 0 10 11 12 3 1 0 99 1 2 1 1 1 2 3
A----------------------------------
  B----------- C-----------
                 D-----

```

A has two children (B, C) and three metadata entries. B has no children and three metadata entries. C has one child and one metadata entry, and so on. It is well-formed, so it is valid.

How about this?

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

```

The root node has 2 children and 0 metadata. Then we need to divide `1 0 0 1 1 0 0 1 1` into two nodes. But:

* `1 0 0` is not a valid node: it has 1 child and 0 metadata, but single 0 is not a valid node.
* `1 0 0 1` is not valid either: it has 1 child and 1 metadata, but again we are left with single 0.
* `1 0 0 1 1` is valid (1 child, 1 metadata, `0 0` being the child), but the rest `0 0 1 1` is not a valid node.
* `1 0 0 1 1 0` is not a valid node because `0 0 1 1` isn't.
* The first child cannot be longer than that because the second must have 1 metadata.

Therefore, the second example is not a valid license file.

Given a license file as an array of non-negative integers, determine if it is valid. You can choose to

* output truthy/falsy using your language's convention (swapping is allowed), or
* use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard rules apply. The shortest code in bytes wins.

## Test cases

Truthy:

```
[0, 0]
[1, 0, 0, 0]
[0, 99, 99, 99, 3]
[2, 0, 10, 11, 12, 3, 1, 0, 99, 1, 2, 1, 1, 1, 2, 3]

```

Falsy:

```
[]
[0]
[0, 1]
[1, 1]
[0, 0, 0, 0]
[1, 0, 2, 3, 2]
[3, 0, 1, 0, 0, 1, 0, 0, 1, 2, 3, 2]
[2, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0]

```

# Answer
# Ruby, ~~85~~ 80 bytes

```
f=->l{a,*l,b=l;q=l.size;a==0?b==q:(1..q).any?{|x|f[l[0,x]]&&f[[a-1,*l[x,q],b]]}}

```

Try it online!

### Let me explain:

The license is valid if:

* the first element is zero and the last element is the length of the list minus 2

or

* we can create 2 valid licenses by splitting the list in 2, removing the head from the first part and prepending it (minus 1) to the second part. A license in the format `a x x x x x x y y y y y y y` is valid if both `x x x x x x` and `a-1 y y y y y y y` are.
> 7 votes

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

```
f=lambda a,l=1:any(f(a[:i])*f(a[i:],l-1)for i in range(len(a)))if l>1else[[]==a,a>[]<(s:=a[:~a[-1]])and f(s,s.pop(0))][l]

```

Try it online!
> 3 votes

# Answer
# Curry (PAKCS), 49 bytes

```
f(0:x++[l])|length x==l=1
f(a:x++y)|a>0=f$a-f x:y

```

Try it online!

A port of @G B's answer.

This returns `1` if the license is valid, and nothing otherwise.

Though Curry has a Haskell-like syntax, its pattern matching is so powerful that this answer looks more similar to the Mathematica answer than the Haskell one.
> 3 votes

# Answer
# Pari/GP, 81 bytes

```
f(a)=#a&&if(a[1],sum(i=2,#a,f(a[2..i])*f(concat(a[1]-1,a[i+1..#a]))),a[#a]+2==#a)

```

Try it online!

A port of @G B's answer.
> 1 votes

# Answer
# JavaScript (ES6),  ~~94~~  92 bytes

This is using GB's great insight.

Returns **0** or **1**.

```
f=a=>a[a[n=a.length,0]+n-!!n]==n-2|a.some((_,i)=>f(a.slice(1,i))&&f([a[0]-1,...a.slice(i)]))

```

Try it online!
> 1 votes

# Answer
# Charcoal, 67 bytes

```
⊞υ⟦θ⟧Ｆυ¿ι«≔⊟ιη¿η«≔§η⁰ζ¿‹ζ⁼§η±¹⁻Ｌη²⊞υι¿ζＦ…³Ｌη⊞υ⁺ι⟦✂η¹κ¹⁺⟦⊖ζ⟧✂ηκ⟧»»Ｐ¹

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` if the licence is valid, nothing if not. Explanation:

```
⊞υ⟦θ⟧

```

Start by checking the whole licence as a list of one sublicence.

```
Ｆυ

```

Loop over the lists of sublicences.

```
¿ι«

```

If there are still sublicences to check:

```
≔⊟ιη

```

Remove one sublicence.

```
¿η«

```

If this sublicence is not trivially illegal, then:

```
≔§η⁰ζ

```

Get the number of its sublicences.

```
¿‹ζ⁼§η±¹⁻Ｌη²

```

If this is a valid licence with no sublicences, then...

```
⊞υι

```

... push the remaining sublicences to the list to scan.

```
¿ζ

```

Otherwise if this licence has sublicences, then:

```
Ｆ…³Ｌη

```

For each potential first sublicence:

```
⊞υ⁺ι⟦✂η¹κ¹⁺⟦⊖ζ⟧✂ηκ⟧

```

Append the first sublicence and the licence adjusted for the removal of the first sublicence to the list of licences to scan.

```
»»Ｐ¹

```

Otherwise, all sublicences validated and so this licence is valid.
> 1 votes

# Answer
# TypeScript Types, 378 bytes

```
//@ts-ignore
type a<T,N,C=[],P=[],Q=[...P,C]>=T extends[infer A,...infer R]?a<R,N,[...C,A],P>|a<R,N,[A],Q>:N extends Q["length"]?Q:[N,Q]extends[0,[[]]]?T:never;type b<D,N,M=[]>=N extends M["length"]?D:D extends[...infer D,{}]?b<D,N,[...M,0]>:never;type c<C>=C extends(infer C)[]?0 extends M<C>?0:1:0;type M<D>=D extends[infer C,...infer I,infer M]?1 extends c<a<b<I,M>,C>>?1:0:0

```

Try It Online!

## Ungolfed / Explanation

<pre><code>// Returns all the ways an array can be chunked into Count subarrays
type Chunkify<Unchunked, Count, CurChunk=[], PrevChunks=[], AllChunks=[...PrevChunks,CurChunk]> =
  // Get the first element of Unchunked
  Unchunked extends [infer El, ...infer Rest]
    // Return a union of:
    ?
      // Continue this chunk
      | Chunkify<Rest, Count, [...CurChunk, El], PrevChunks>
      // Start a new chunk
      | Chunkify<Rest, Count, [El], AllChunks>
    // Unchunked is empty.
    // If AllChunks.length == Count,
    : Count extends AllChunks["length"]
      // Return AllChunks
      ? AllChunks
      // Otherwise, if Count == 0 and AllChunks == [[]],
      : [Count, AllChunks] extends [0, [[]]]
          // Return []
        ? Unchunked
        // Invalid chunking
        : never

type RemoveMetadata<
  Data,
  MetadataCount,
  RemovedCount=[]
> =
  // If RemovedCount == MetadataCount,
  MetadataCount extends RemovedCount["length"]
    // Return Data
    ? Data
    // Otherwise, pop the last element off of Data
    : Data extends [...infer Initial, {}]
      // Recurse, incrementing RemovedCount
      ? RemoveMetadata<Initial, MetadataCount, [...RemovedCount, 0]>
      // Data is empty, but we still need to strip more metadata; return never
      : never

type ValidateLicenses<Chunkifications> =
  // Map over Chunkifications, extracting the chunks as a union
  Chunkifications extends (infer Chunks)[]
    // Return 0 if any of Chunks are invalid licenses
    ? 0 extends ValidateLicense<Chunks> ? 0 : 1
    // Invalid
    : 0

type ValidateLicense<Data> =
  Data extends [infer ChildCount, ...infer InnerData, infer MetadataCount]
    // Return 1 if any of the ways to chunk RemoveMetadata<InnerData, MetadataCount> into ChildCount chunks are valid lists of licenses
    ? 1 extends ValidateLicenses<Chunkify<RemoveMetadata<InnerData, MetadataCount>, ChildCount>> ? 1 : 0
    // Invalid
    : 0

type T0 = ValidateLicense<[0, 0]>
//   ^?
type T1 = ValidateLicense<[1, 0, 0, 0]>
//   ^?
type T2 = ValidateLicense<[0, 99, 99, 99, 3]>
//   ^?
type T3 = ValidateLicense<[2, 0, 10, 11, 12, 3, 1, 0, 99, 1, 2, 1, 1, 1, 2, 3]>
//   ^?
```
</code></pre>
> 1 votes

# Answer
# Rust, 156 bytes

```
fn f(a:&[usize])->bool{let l=a.len();l>1&&((a[0]<1&&a[l-1]==l-2)||a[0]>0&&(2..l).any(|i|f(&a[1..i])&&f(&{let mut z=a[i..].to_vec();z.insert(0,a[0]-1);z})))}

```

Try it online!

Making use of @G B's approach.
> 1 votes

# Answer
# Haskell, ~~101~~ 93 bytes

This uses G B's observation.

```
h(x:y)|x>0=or[h$take n y|n<-[0..l y],h$x-1:drop n y]
h y@(0:_)=last y==l y-2
h _=1<0
l=length

```

-8 bytes thanks to alephalpha

Try it Online!
> 1 votes

# Answer
# Wolfram Language (Mathematica), 62 bytes

-3 bytes thanks to @att.

```
_f=1<0
f[0,x___,l_]:=l==Tr[1^{x}]
f[a_,x__/;f@x,y__]:=f[a-1,y]

```

Try it online!

A port of @G B's answer.
> 0 votes

# Answer
# 05AB1E, ~~44~~ 41 bytes

```
"ćUX_iRćsgQë.œ2ùεεNiX<š}}}εε®.V}0ìP}à"©.V

```

Port of *@GB*'s Ruby answer.

Results in `1` for truthy and `0`/`""` for falsey (only `1` is truthy in 05AB1E).

Try it online or verify (almost) all test cases (the largest truthy test case times out because of ).

**Explanation:**

```
"..."          # Push the string below
     ©         # Store it in variable `®` (without popping)
      .V       # Execute it as 05AB1E code
               # (after which the result is output implicitly)

```

```
ć              # Head extracted; pop and push remainder-list and first item separately
 U             # Pop and store this first item in variable `X`
X_i            # If `X` is 0:
   R           #  Reverse the remainder-list
    ć          #  Extract head again (or extract tail actually)
     s         #  Swap so the remainder-list is at the top
      g        #  Pop and push the length of this remainder-list
       Q       #  Check if it's equal to the extracted tail
  ë            # Else:
   .œ          #  Get all possible partitions of the remainder-list
     2ù        #  And only keep those consisting of two partition-parts
       ε       #  Map over each partition:
        ε      #   Inner map over both partition-parts:
         Ni    #    If it's the second part:
           X<  #     Push `X` and decrease it by 1
             š #     Prepend it in front of the partition-part
          }    #    Close the if-statement
        }      #   Close the inner map
       }       #  Close the outer map
        ε      #  Map over the partitions again:
         ε     #   Inner map over both partition-parts again:
          ®    #    Push string `®`
           .V  #    And execute it as 05AB1E code as recursive call
         }     #   After the inner map:
          0ì   #   Prepend a 0 in front of each result
            P  #   Get the product of this result to check if all were truthy
        }      #  After the outer map:
         à     #  Get the maximum to check if any were truthy

```

Some notes:

* 05AB1E lacks any recursive methods, but with `"..."©.V` and `®.V` we can mimic this behavior.
* You may be wondering why we first close the maps and then do the exact same maps again at `}}εε`? We do this to first create the correct partitions, before we do the recursive calls, otherwise variable `X` will be incorrectly overwritten by the inner recursive call. In *@GB*'s Ruby answer, the variables `a` and `b` are within scope of the function, whereas in my full program, the `X` (which is basically variable `a`) would be overwritten in the inner calls.
* `ć` results in an empty string if the list is empty, which is why we use the  before the `P` to convert all empty strings to `0`, while keeping all other integers the same.
> 0 votes

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


title: Simplify ijk-string

text:
# Question
Title: Simplify ijk-string
Related: Multiply Quaternions

## Challenge

Given a string made of `ijk`, interpret it as the product of imaginary units of **quaternion** and simplify it into one of the eight possible values `1`, `-1`, `i`, `-i`, `j`, `-j`, `k`, `-k`.

The evaluation rules are as follows:

$$ ii = jj = kk = -1 \\ ij = k, \quad jk = i, \quad ki = j \\ ji = -k, \quad kj = -i, \quad ik = -j $$

The multiplication of quaternions is associative but not commutative. This means that you may do the simplification in any order, but you cannot reorder the items.

For the I/O format, function parameter and return from a function should be done as a string (list of chars or list of codepoints is also OK). You may assume the input is not empty. You may output any amount of leading and trailing whitespace (spaces, tabs, newlines).

## Test cases

```
i -> i
j -> j
k -> k
ij -> k
ji -> -k
kk -> -1
ijkj -> -j
iikkkkkjj -> k
kikjkikjk -> -k
kjijkjikijkjiki -> 1
jikjjikjikjikjjjj -> j

```

# Answer
# Charcoal, ~~32~~ ~~29~~ 27 bytes

```
≔⁰θＦＳ≔⁺×θＸ³℅ι℅ιθ‹³﹪θ⁸§1ijkθ

```

Try it online! Link is to verbose version of code. Explanation: The values are encoded to integers equivalent to `0..7` (modulo `8`) in the order `1`, `i`, `j`, `k`, `-1`, `-i`, `-j`, `-k`. The multiplications by `i`, `j` and `k` have the following effect on the integer:

* Multiplying by `i` is equivalent to tripling the integer and adding `1`.
* Multiplying by `j` is equivalent to adding `2` to the integer.
* Multiplying by `k` is equivalent to tripling the integer and adding `3`.

Edit: Thanks to @NickKennedy for saving 3 bytes by pointing out that the ordinals of `i`, `j` and `k` are equivalent (mod 8) to `1`, `2` and `3` respectively. This means that the integer needs to be tripled if the ordinal is odd, and then the ordinal can be added to it.

Edit: Furthermore, tripling the integer (mod 8) if the ordinal is odd is equivalent to multiplying the integer by 3 to the power of the ordinal, for a further 2 byte saving.

```
≔⁰θ

```

Start with `0`.

```
ＦＳ

```

Loop over the input...

```
≔⁺×θＸ³℅ι℅ιθ

```

... multiply the current value by 3 to the power of the ordinal, then add the ordinal.

```
‹³﹪θ⁸

```

Output a `-` sign if the result (mod `8`) is greater than 3. (There are other ways to express this in Charcoal but sadly I couldn't do better than 5 bytes.)

```
§1ijkθ

```

Output `1`, `i`, `j`, or `k`, depending on the result (mod `4`).
> 21 votes

# Answer
# sed -r 4.2.2, 71

Using @Neil's Retina 0.8.2 approach:

```
:
s/k/ij/
s/ii|jj/-/
s/ji/-ij/
s/(\w)-/-\1/
s/--//
t
s/ij/k/
s/^-?$/&1/

```

Try it online!

---

Previous answer:

# sed -r 4.2.2, 97

Saved 3 bytes thanks to @FryAmTheEggman.

```
:
s/(\w)\1/-/
s/(\w)-/-\1/
s/--//
s/ij/k/
s/jk/i/
s/ki/j/
s/ji/-k/
s/kj/-i/
s/ik/-j/
t
s/^-?$/&1/

```

Try it online!
> 11 votes

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

```
e=>e.map(q=>p=+p?q:o[i=o.search(p+q),s^=i<5,i+2],p=s=1,o=' 1jikjijkij')&&'- '[s]+p

```

Try it online!

Input array of chars, output string.

---

# JavaScript (Node.js), 66 bytes

```
e=>e.map(q=>p=p<99?q:(s^=(~p+q)%3&&36,p^=q)?104|p:49,p=s=9)&&[s,p]

```

Try it online!

Input array of codepoints, output array of codepoints.
> 7 votes

# Answer
# Retina, 43 bytes

```
3{`\bii
-
ij
k
\bik
-j
}T`ijk`jki
--

\B$
1

```

Try it online! Link includes test cases. Explanation:

```
3{`

```

Loop three times.

```
\bii
-
ij
k
\bik
-j

```

Perform some simplifications.

```
T`ijk`jki

```

Rotate by 120° along the `i=j=k` axis.

```
}`

```

Repeat the above loop until the output converges. (Since the inner loop iterates three times, the rotations will cancel out.)

```
--

\B$
1

```

Tidy up the result.
> 7 votes

# Answer
# JavaScript (ES6),  ~~60 55 53~~  52 bytes

Expects an array of ASCII codes. Returns a string.

This is based on @Neil's excellent insight.

```
a=>["-"[a.map(y=>x+=y%2*2*x+y,x=4),x&4]]+"1ijk"[x&3]

```

Try it online!

### How?

According to Neil:

> at each step if the input is `i` or `k` then the integer is tripled and incremented, and if the input is `j` or `k` then 2 is added to it

In JS at least, it is shorter to express the above as follows:

$$x \gets x + (y \bmod 2)\times 2\times x+(y \bmod 4)$$

where \\$x\\$ is the sum and \\$y\\$ is the ASCII code of the next input character.

@NickKennedy noticed that it may actually be optimized one step further (thanks to Neil as well for pointing that out):

$$x \gets x + (y \bmod 2)\times 2\times x+y$$

We end up with the following encoding for \\$x\\$:

```
… x x 2 1 0
\___/ | \_/
  |   |  |
  |   |  +---> 00 = 1, 01 = i, 10 = j, 11 = k
  |   +------> sign bit, set for positive
  |            (which is why we start with x = 4)
  +----------> upper bits are ignored

```
> 6 votes

# Answer
# 05AB1E, ~~40~~ 37 bytes

```
ΔJ2ôεDg<iËi¼õë…ijkyмyC3%<½]J1«н¾É'-×ì

```

Try it online! or Try all cases!

```
Δ                # until the output doesn't change:
 J2ô             #   split the string into groups of 2
                 #   (last one might be a single character)
 ε               #   for each group y:
  Dg<i           #     if the length of y is 2:
      Ëi         #       if all characters are the same:
        ¼õ       #         increment the '-'-counter and return empty string
       ë         #       else:
        …ijkyм   #         remove the two characters from "ijk"
        yC3%<½   #         increment the '-'-counter if y converted from binary ...
                 #         ... is equal to 2 modulo 3
]                # close all loops and if statements
J1«              # append a 1
   н             # take the first character
    ¾É'-×ì       # if the '-'-counter is odd, prepend a '-'

```

---

# 05AB1E, ~~44~~ 43 bytes

```
Δ…ijk©Dâ•KĀ ‰9Ï•„ -®«ÅвJ#:Σ'-Ê]„--KD'-såi1«

```

Try it online! or Try all cases!

```
Δ                    # Until the output doesn't change:
…ijk©Dâ              #   = ii ij ik ji jj jk ki kj kk
•KĀ ‰9Ï•" -®«ÅвJ#    #   =  -  k -j -k  -  i  j -i  -
:                    #   Replace
Σ'-Ê                 #   Sort "-" to the front
„--K                 # Remove all non-overlapping occurences of "--"
'-såi                # If the result is a substring of "-":
1«                   #   Append a 1

```
> 5 votes

# Answer
# Ruby, ~~72 67 66~~ 64 bytes

```
->s{w=k=0;s.bytes{|x|k>0&&w^=13[k+2-x&3];k^=x&3};?-*w+"1ijk"[k]}

```

Try it online!

Thanks dingledooper for -2 bytes.
> 5 votes

# Answer
# K (ngn/k), ~~71~~ 63 bytes

-8 bytes thanks to @coltim!

```
(r,"-",'r:"1ijk")@((8!A,4+A:a,'4+a:4 4#0,8\5717110953644).,)/4!

```

Try it online!
> 4 votes

# Answer
# Retina 0.8.2, 44 bytes

```
k
ij
ii|jj
-
ji
-ij
--

}`.-
-$&-
ij
k
\B$
1

```

Try it online! Link includes test cases. Explanation:

```
k
ij

```

Replace `k` with `ij` as an interim measure.

```
ii|jj
-

```

Substitute `-1` for `ii` and `jj`.

```
ji
-ij

```

Substitute `-ij` for `ji`.

```
--

.-
-$&-

```

Propagate `-`s to the left.

```
}`

```

Repeat until no more changes can be made.

```
ij
k

```

Convert `ij` back into `k`.

```
\B$
1

```

Output `1` if there is no `i`, `j` or `k`.

My original idea unfortunately turned out to be as long as the naïve approach which has since been golfed anyway:

```
^(..)+$
-ijk$&
+`^(.*)((\w)\3|(j|k)(i|j))
-$1$5$4
ijk
-
--

\B$
1

```

Try it online! Link includes test cases. Explanation:

```
^(..)+$
-ijk$&

```

Prepend `-ijk` if there are an even number of letters, because the next stage doesn't affect the parity and we want to end up with a single letter if possible.

```
+`^(.*)((\w)\3|(j|k)(i|j))
-$1$5$4

```

Repeatedly delete two identical letters or exchange two unsorted letters. These operations both negate the final result.

```
ijk
-

```

Reduce any remaining `ijk` to `-1`.

```
--

\B$
1

```

Tidy up the result.
> 4 votes

# Answer
# Jelly, ~~23~~ 20 bytes

```
3*żæ.ƒ0%8ṃ“ijk1””--¦

```

Try it online!

Try all examples

A full program taking a list of code points and printing to STDOUT.

Uses Neil’s clever observation about the effect of multiplication by I, j and k in his Charcoal answer so be sure to upvote that one too! Thanks also to Neil for saving a byte with the observation that \\$3 ^ x \mod 8\\$ is 3 for all odd \\$x\\$ and 1 for all even \\$x\\$.

Thanks to @cairdcoinheringaahing for saving a byte by pointing out that I could remove the trailing . Thanks to @JonathanAllan for a neat 1 byte save using .

## Explanation (outdated)

```
 3*                    | 3 to the power of each codepoint
   ż                   | Zip with original list of codepoints
    æ.ƒ0               | Starting with zero, reduce the list using dot product (extending the shorter argument with ones)
        %8             | Mod 8
          d4           | Divmod 4
            ị"“- “ijk1 | Index into zipped "- ", "ijk1"

```
> 4 votes

# Answer
# Python 3, 89 bytes

```
a=0
for c in input():a=b'147223453614'[ord(c)%3*4+a%4]^(a&4)
print('-'[:a&4]+'1ijk'[a%4])

```

Try it online!

It encodes the unit quaternions 1, i, j, k, -1, -i, -j, -k as the numbers 0..7 respectively, so that `a%4` represents one of 1, i, j, k, and `a&4` represents whether the value is negated.

The loop works by accumulating a result in the variable `a`, multiplying one quaternion from the input on each iteration, much like you'd write `a = 1; for x in numbers: a *= x` to compute a product normally.

The byte-string `b'147223453614'` encodes a multiplication table for i, j, k multiplied by 1, i, j, k. Indexing a byte-string gives the ASCII values as integers, but we only care about the lowest 3 bits and, conveniently, the ASCII value of each digit 0..7 has the correct lowest 3 bits, so this is practically like indexing a list of integers. The table is 3x4 instead of 8x8 because one operand (from the user input) can only be i, j or k, and we can ignore the sign from the other operand (the accumulator variable) and deal with the sign afterwards.

The expression `ord(c)%3` converts the ASCII characters i, j, k into 0, 1, 2 respectively; the ASCII values of i, j and k are correct for this modulo 3. (If they weren't, the multiplication table could be changed.) The `^(a&4)` part XORs the result with the third bit of `a`, swapping the sign of the result from the multiplication table if this operand was negative, since we ignored the sign before.

The output uses string slicing to conditionally print the minus sign (`'-'[:4]` conveniently isn't an error in Python).
> 4 votes

# Answer
# Jelly, 61 bytes

```
,ḅ8‘ị“;CAĖ*VÆSȮṀƒḳẹ²^÷d5ñYƭẏ§O’b8¤
_ȷ2ç/ị“1“-i“-j“-k“i“j“k“-1

```

Try it online!

-2 bytes thanks to caird coinheringaahing

---

Takes input as a list of codepoints, outputs as a string.

The indexing to get the final answer is terrible. Looking for a way to improve that.

This is very unclever. The first link just encodes the entire multiplication table into a size-64 list, converts the left and right arguments from base 8, and indexes into that. The main link takes the input as codepoints, subtracts 100 (which makes `ijk` equal to `567` and thus I put `-1, 1, -i, -j, -k` into `01234`), reduces the list from the left by the helper link, and then indexes the answer into a valid output format.
> 3 votes

# Answer
# C (gcc), ~~104~~ ~~103~~ 101 bytes

```
a,z,n,h='h';f(s,d)int*s,*d;{for(a=n=9;z=*s++;n^=(~a+z)%3&&a>h?0:36)a=a>h?a^z^h:z;*d++=n;*d=a>h?a:49;}

```

Try it online!

Apparently I had basically the same idea as tsh, using xor.

It still needs some optimization, considering how tsh's is like half the size in calculations.

* -1 byte for using tab (9) instead of space (32)
* -2 bytes for making a temp for `'h'`

Input is a null terminated array of codepoints, output is stored to a pointer to a bunch of codepoints.

```
void f(const int *src, int dst[2])
{
    int acc, tmp, sign;
    for (acc = sign = '\t'; (tmp = *src++); ) {
        // My XOR math will end up with less than 'i' for 1.
        // TODO: fix this efficiently and I can remove some checks.
        if (acc < 'i') {
            acc = tmp;
        } else {
            // Xoring all of them together will result in the result or 'h'
            acc = acc ^ tmp ^'h';
        }
        // Magic for testing when we need to negate
        if ((acc - tmp + 1) % 3 == 0 && acc > 'h') {
             // Switches between tab and '-'
             sign ^= 36;
         }
     }
     // Output sign
     dst[0] = sign;
     // Correct our xor math
     dst[1] = a < 'i' ? '1' : a;
}

```
> 3 votes

# Answer
# APL(Dyalog Unicode), ~~33~~ 26 bytes SBCS

A port of Nick Kennedy's Jelly answer.

```
' -' '1ijk'⌷⍨¨2 4⊤⊢⊥⍨3*2|⊢

```

Try it on APLgolf!

A train submission which takes a list of codepoints as the right argument.

APL has *mixed radix decode* () which makes the calculation part quite short:

```
       2|⊢  ⍝ each value in the input modulo 2
     3*     ⍝ raise 3 to this power
  ⊢⊥⍨       ⍝ use the resulting numbers as a mixed radix to decode the input

```

Technically the `2|` is not needed, but without it even the test cases with 2 characters start to fail because of very large numbers.

`2 4⊤` calculates `4|⊢` and `2|4÷⍨⊢`, and both resulting integers are used to index into one string.
> 3 votes

# Answer
# Retina, ~~65~~ 58 bytes

```
(\w)\1
-
ij
k
jk
i
ki
j
ji|kj|ik
-$^$&
--

}`.-
-$&-
\B$
1

```

Try it online!

Saved 7 bytes thanks to Neil!

The main tricks deal with handling negative signs and the negative products. Negative signs are "bubbled" towards the beginning of the string to prevent needing to account for them in the other rules. The products that produce a negative such as `ji` are all reversed and then negated, to avoid dealing with them specifically. At the end, if there is no letter, we add a 1.
> 2 votes

# Answer
# Vyxal,~~95 91~~ 55 bytes

```
λ2ẇ«½∇«:Ẋ«∨uOŻN€bMċ∇Dk«⌈Ŀṅ\e/:L‹\e*$ṅ+;Ẋ‛eeo:\erß›\e\-V

```

Try it Online!

Partially ported ovs. Do I win 'Most improved'?

Makes a lot more sense now.

```
λ                                     ;                 # Lambda
 2ẇ                                                     # Chunks of 2
   «½∇«                                                 # Compressed `ijk`
       :Ẋ                                               # Cartesian square
         «∨uOŻN€bMċ∇Dk«                                 # Compressed string `e k ej ek e i j ei e`
                       ⌈                                # Split by spaces
                        Ŀ                               # Transliterate
                         ṅ                              # Join
                          \e/                           # Split by `e`
                             :                          # Duplicate
                              L‹\e*                     # (Length - 1) es
                                   $ṅ+                  # Prepended (so es are bubbled to start
                                       Ẋ                # Repeat on input until result doesn't change
                                        ‛eeo            # Get rid of double es
                                            :\erß       # If result is a substring of 'e'
                                                 ›      # Append a 1
                                                  \e\-V # Replace es with -s

```
> 2 votes

# Answer
# Python 3, ~~199~~ \\$\cdots\\$ ~~182~~ 173 bytes

```
f=lambda s,n=0:s<'.'and f(s[1:],1-n)or len(s)>1and f(s<'2'and s[1:]or(s[0]==s[1]and'-1'or{'ij':'k','jk':'i','ki':'j','ji':'-k','kj':'-i','ik':'-j'}[s[:2]])+s[2:],n)or'-'*n+s

```

Try it online!

Slightly longer version without direct mappings of \\$i\\$, \\$j\\$, and \\$k\\$ inter-multiplications:

# Python 3.8, 174 bytes

```
f=lambda s,n=0,o='ijkijki':s<'.'and f(s[1:],1-n)or len(s)>1and f(s<'2'and s[1:]or(s[0]==s[1]and'-1'or((b:=o.find(s[1],(a:=o.find(s[0]))))-a-1)*'-'+o[2*b-a])+s[2:],n)or'-'*n+s

```

Try it online!
> 2 votes

# Answer
# Factor \+ `math.matrices math.quaternions`, 125 bytes

```
[ "1ijk"4 identity-matrix zip tuck substitute 1 n>q [ q* ] reduce dup sum 0 < 45 32 ? -rot vabs swap assoc-invert at 2array ]

```

Try it online!

On TIO it's 129 bytes; this is because Factor on TIO is ancient and doesn't have tuck which is the same as `dup -rot`.

## Explanation:

It's a quotation (anonymous function) that takes an array of code points as input from the data stack and leaves an array of code points as output on the data stack.

* `"1ijk"4 identity-matrix zip tuck substitute` Convert the input to quaternions that Factor can do arithmetic on. For example, `"ijkj"` -\> `{ { 0 1 0 0 } { 0 0 1 0 } { 0 0 0 1 } { 0 0 1 0 } }`
* `1 n>q [ q* ] reduce` Take the product.
* `dup sum 0 < 45 32 ? -rot` Place the code point for the sign on the data stack.
* `vabs swap assoc-invert at` Convert the product quaternion to a code point.
* `2array` Make an array out of the code points that are on the stack.
> 2 votes

# Answer
# Haskell, ~~135~~ 84 bytes

```
x#'i'=x*3+1
x#'j'=x+2
x#'k'=x*3+3
t=(cycle([pure,('-':).pure]<*>"1ijk")!!).foldl(#)0

```

Try it online!

Had a lot of trouble doing this efficiently in Haskell. Hopefully this will inspire someone to create a better Haskell answer.
> 2 votes

# Answer
# PowerShell, 55 bytes

Port of the Arnauld's solution.

Expects an array of ASCII codes. Returns a string.

```
,4+$args|%{$x+=$_%2*2*$x+$_}
'-'[$x-band4]+'1ijk'[$x%4]

```

Try it online!

---

# PowerShell, ~~122~~ 120 bytes

Thanks @Neil for the `k -> ij` simplification.

```
for($s="$args";$p-ne($p=$s)){'k ij9ii|jj -9ji -ij9--9.- -$0-9ij k'-split9|%{$s=$s-replace-split$_}}
$p+'1'*($p-in'','-')

```

Try it online!
> 1 votes

# Answer
# Haskell, 58 bytes

```
(\m->['-'|m 8>3]++["1ijk"!!m 4]).mod.foldl(\x y->3^y*x+y)0

```

Try it online!

A port of Neil's Charcoal answer that takes a list of codepoints as input.
> 1 votes

# Answer
# Shue, 46 bytes

```
1
i
j
k
-1
-i
-j
-k
=1
--=
ii=-
jk=i
k=ij
j=ki

```

Try it online!

It's... beautiful.

Uses an `i`-dominated internal representation. Basically, the number of `j` and `k` characters is decreasing. The last two rules allow the movement of `j` and `k` between `i`s.

Due to the rule `=1`, this is a bit slow. If you want to test this answer, I suggest you use This equivalent program.
> 1 votes

# Answer
# Lexurgy, 108 bytes

```
a propagate:
``=>*
{ii,jj,kk,ij,jk,ki,ji,kj,ik}=>{`,`,`,k,i,j,`k,`i,`j}
[]$1 `=>` $1
b:
*=>\1/{$,`} _ $
`=>\-

```

Explanation:

```
# while the input changed last iteration...
a propagate:
# cancel out negatives
``=>*
# ijk conversion
{ii,jj,kk,ij,jk,ki,ji,kj,ik}=>{`,`,`,k,i,j,`k,`i,`j}
# move negative signs to the front
[]$1 `=>` $1

# cleanup
b:
# put in 1s on empty string or leading `
*=>\1/{$,`} _ $
# ` to minus
`=>\-

```
> 1 votes

# Answer
# , 41 bytes

```
'1ijk -'&([({~4&|,~4+3&<)(8|]+[*3^])/@i.)

```

Try it online!

Neil's excellent idea applied to J.
> 0 votes

# Answer
# Python 3, 289 bytes

```
R={"ii":"-","jj":"-","kk":"-","ij":"k","jk":"i","ki":"j","ji":"-k","kj":"-i","ik":"-j"}
def f(x):
    if x=="-":return"-1"
    if len(x)==1:return x
    if len(x)==2and x[0]=="-":return x
    for s,e in R.items():x=x.replace(s,e)
    return f(("-"if x.count("-")%2else"")+"".join(c for c in x if c!="-"))

```

Try it online! Takes input as a string.
> 0 votes

# Answer
# Python 3, 132 bytes

Function that iterates over the characters of the expression, evaluating step by step the product of a pair of characters.

```
def f(e,s=0):
 while e[1:]:p,e=e[:2],e[2:];a=set('ijk')-set(p);e=a.pop()[len(a):]+e;s^=p not in'ijki'
 return'-'[:s]+['1',e][len(e)]

```

Try it online!

---

*Code explanation:*

* `def f(e, s=0):`
function definition: takes the expression to be evaluated as input `e`; the 2nd parameter `s` is the sign, passed as optional parameter to be initialized (0 =\> +, 1 =\> -).
* `while e[1:]:`
main loop: iterates over the characters in the expression, while there are at least 2 characters left (the empty string evaluates to False).
* `p, e = e[:2], e[2:];`
take the first two characters `p` (to evaluate their product), and the remaining part of the expression.
* `a = set('ijk') - set(p);`
evaluates the set `a` as difference between the set of 3 chars {i, j, k} and the set of 2 chars in `p`. This can be used to distinguish the different cases: if `p` is a mixed product (ij, jk, ...) then the difference set will contain the char resulting from their product; otherwise, the difference set will have `len==2`.
* `e = a.pop()[len(a):] + e;`
prepend to the remaining expression the char resulting from the product. This exploits the set `a` built before: `pop()` will return the correct char only if we have a mixed product: the difference set will contain only the resulting char. It is taken by slicing the single char string with `len`: actually `len=0` accounts for the fact that `a.pop` is evaluated before `len`.
* `s ^= p not in 'ijki'`
evaluates the sign: the product will have negative sign for {ii, jj, kk} and {ji, kj, ik}, all of them are not contained in the string `'ijki'`. The boolean evaluates to integer to compute the xor function: sign xor (1, 0) follows the sign multiplication rules.
* `return '-'[:s] + ['1', e][len(e)]`
finally, the function returns the results of the expression: first the sign `-` only if `s==1`. Then the results of the expression: `e` if it contains the remaining single char (exit from loop), otherwise `1`.
> 0 votes

# Answer
# x86-64 machine code, 36 bytes

```
30 C1 74 06 28 C8 04 02 7B 05 35 31 C9 31 C0 AC 24 03 75 EC 9E 79 03 B0 2D AA 8D 41 31 E3 02 04 37 66 AB C3

```

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes in RDI an address at which to place the result, as a null-terminated byte string; and the address of the input, as a null-terminated byte string, in RSI. The starting point is after the first 11 bytes.

In assembly:

```
# ECX holds 0 for 1, 1 for i, 2 for j, or 3 for k.
# The high bit of AH holds a sign: 1 to negate or 0 to not negate.

multiply:       # Here, AL is 1, 2, or 3 for the current input letter (as above).
    xor cl, al  # Exclusive-or CL (the low byte of ECX) with that value.
                    # This produces the correct new value.
    jz flipsign # If the result is 0 (i*i, j*j, k*k), jump to flip the sign.
    sub al, cl  # Subtract CL from AL.
    add al, 2   # Add 2 to AL. The possibilities based on the original CL and AL are:
                #  0: j*i=-k
                #  1: k*i=j  i*j=k
                #  2: 1*i=i  1*j=j  1*k=k
                #  3: k*j=-i i*k=-j
                #  4: j*k=i
    jpo next    # Jump if the sum of the low 8 bits is odd, to skip the sign flipping.
                #  It is odd for 1, 2, and 4, so the sign is flipped for 0 and 3.
flipsign:
    .byte 0x35  # This byte combines with the next two instructions to form
                #  'xor eax, 0xC031C931', which in particular flips the high bit of AH.
f:
    xor ecx, ecx    # (Start here) Set ECX to 0.
    xor eax, eax    # Set EAX to 0.
next:
    lodsb           # Load a byte from the input string into AL, advancing the pointer.
    and al, 3       # AND that byte with 3, converting i,j,k to 1,2,3 respectively.
    jnz multiply    # Jump if the result is not 0. It is 0 for the null byte.
    sahf            # Set flags from AH. In particular, the high bit of AH goes into SF.
    jns skipminus   # Jump if SF=0 to skip the minus sign.
    mov al, 0x2D    # Set AL to the ASCII code of HYPHEN-MINUS.
    stosb           # Add that to the output string, advancing the pointer.
skipminus:
    lea eax, [rcx+0x31] # Set EAX to ECX+0x31. 0x31 is the ASCII code of 1.
    jrcxz oneskip       # Jump if ECX is 0.
    add al, 0x37        # (Otherwise) Add 0x37 to AL, for a net addition of 0x68,
                        #  which makes 1,2,3 into the ASCII codes of i,j,k respectively.
oneskip:
    stosw   # Add AL and AH (which is 0) to the output string, advancing the pointer.
    ret     # Return.

```
> 0 votes

---
Tags: code-golf, string, math, complex-numbers
---


title: Convert prefix to infix

text:
# Question
Title: Convert prefix to infix
Infix notation is a method of printing mathematical expressions where each operator sits between its two arguments, such as \\$ \left(5 \cdot 4\right) + 3 \\$.

Prefix notation is a method of printing expressions where operators sit before their arguments. The equivalent of the above is `+*543`. It's a bit harder to understand than infix, but here's a sort of explanation:

```
+*543 # Expression
+     # Adding
 *54  # Expression
 *    # The product of
  5   # 5 and
   4  # 4
    3 # And 3

```

Your challenge is to, given an expression in prefix, convert it to infix notation.

You may take input as a string, character array, array of charcodes, etc.

The input will contain lowercase letters and digits, and can be assumed to be a valid expression - that is, each operator (letter) has exactly two operands and there is only one value left at the end

The output should be a valid expression in infix - that is, it should be an expression in the following recursive grammar:

```
digit := 0-9
operator := a-z
expression := digit | (expression operator expression)

```

That is, each expression should be a digit, or two expressions joined by an operator and wrapped in parentheses for unambiguity.

## Example

Note: Spaces are for clarity and are optional in the input and output.

```
Expression: x 3 u f 4 3 h 5 9
You could read this as x(3, u(f(4, 3), h(5, 9))) or something.

The x is taking 3 and the expression with a u as operands:

Result: (3 x ...)
Expression: u f 4 3 h 5 9

The u is taking the expression with a f and the expression with an h as operands.

Result: (3 x ((...) u (...)))
Expression: f 4 3

The f is taking 4 and 3 as operands.

Result: (3 x ((4 f 3) u (...)))
Expression: h 5 9

The h is taking 5 and 9 as operands.

Expression: (3 x ((4 f 3) u (5 h 9)))

And that's the result! Spaces are optional.

```

## Testcases

As usual, these are manually created, so comment if I've stuffed these up.

```
a34 -> (3a4)
ba567 -> ((5a6)b7)
cba1234 -> (((1a2)b3)c4)
a1b23 -> (1a(2b3))
a1fcb46d4e95ig6h42kj32l68 -> (1a(((4b6)c(4d(9e5)))f((6g(4h2))i((3j2)k(6l8)))))

```

Standard rules apply.

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

```
f=lambda S:(s:=next(S:=iter(S)))[:s<"a"]or"("+f(S)+s+f(S)+")"

```

Try it online!

This does the conversion in a single linear pass over the input. The tree structure is captured by a recursive scheme where each branch corresponds to an instance of the function. The function logic is then as simple as: Read the next character and return it if it is a numeral. Else store it, then output opening braces call yourself for the first operand, output the stored infix call yourself for the second operand and add the closing braces.

To keep track of the position within the input string across all the recursive function calls we convert the input to an iterator. Applying `iter` to an iterator returns the object itself, so it does no harm doing it multiple times. As all copies of the recursive function use the self-same single instance of the iterator the bookkeeping becomes trivial.
> 9 votes

# Answer
# TypeScript Types, ~~234~~ 206 bytes

Saved 28 bytes thanks to tjjfvi!

```
//@ts-ignore
type F<E>=E extends`${infer H}${infer T}`?(H extends`${number}`?[H,T]:F<T>extends[infer I,infer U]?F<U>extends[infer J,infer V]?[`(${I}${H}${J})`,V]:0:0):0
type G<E>=F<E>extends[infer H,""]?H:0

```

Try it online!

Thanks to @tjjfvi for helping me get started with abusing TypeScript's surprisingly powerful type system. This is pretty much the same approach as my Scala answer, just at compile time. At each step, `F` returns one expression and the remainder of the input. First it deconstructs the input into the first character `H` and the rest `T` using `E extends `${infer H}${infer T}`` . Then it checks if the first character of `E` is a digit (`H extends'0'|...|'9'`). If it is, it just returns that first character (a valid infix expression) and `T` in a list (or is it a tuple type?). Otherwise, it finds the next two expressions `I` and `J` and returns the infix expression `(IHJ)` along with the remaining text `V`. `G` exists simply to match on `F`'s output and return the valid expression, as the second part of the output of `F` is an empty string by the end.
> 7 votes

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

```
s=>(i=0,g=(c=s[i++])=>c>=0?c:'('+g()+c+g()+')')()

```

Try it online!
> 6 votes

# Answer
# x86-16 machine code, ~~23~~ 21 bytes

```
00000000: ac3c 617c 0e50 b028 aae8 f4ff 58aa e8ef  .<a|.P.(....X...
00000010: ffb0 29aa c3                             ..)..

```

Listing:

```
        P2I:
AC          LODSB               ; AL = next char, SI++
3C 61       CMP  AL, 'a'        ; is alpha?
7C 0E       JL   IS_ARG         ; if not, it's an argument
50          PUSH AX             ; save operator to stack
B0 28       MOV  AL, '('        ; load left paren
AA          STOSB               ; write to output
E8 0100     CALL P2I            ; recursive call for next char
58          POP  AX             ; restore operator from this call stack
AA          STOSB               ; write to output
E8 0100     CALL P2I            ; recursive call for next char
B0 29       MOV  AL, ')'        ; load right paren
        IS_ARG:
AA          STOSB               ; write to output
C3          RET                 ; return to caller

```

Input string at `[SI]`, output to `[DI]`.
> 6 votes

# Answer
# Haskell, 70 bytes

```
g(a:b)|a<'a'=([a],b)|(c,d)<-g b,(e,f)<-g d=('(':c++a:e++")",f)
f=fst.g

```

Try it online!
> 4 votes

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

Or **\>=4.1, 62 bytes** by replacing the word `function` with `\`.

*-many bytes by changing I/O to vector of char codes.*
*-another some bytes thanks to @Dominic van Essen.*
*+7 bytes costed converting from not-so-self-contained function to a program.*
*-3 bytes thanks to @Dominic van Essen \- converting back to one (reusable) function.*

```
`/`=function(s,t=0)"if"((a=s[i<<-t*i+1])<58,a,c(40,s/1,a,s/1,41));i=9

```

Try it online!

Port of @loopy walt's answer.

**Explanation**

A function takes string `s` and `t` defaulting to `0` (for resetting global variable).
The recursive function (named `/` overriding division) takes one character at a time (`a`) incrementing the global counter each time. If the character char code is less then 58, then it's a digit and needs to be returned as is. Otherwise, we surround the character with braces (char codes `40,41`) and recursive calls to our function (with `t=1` to keep `i` as is between calls).
The code at the end initiates global counter `i` to a digit (`9` chosen for demonstration purposes).

---

Solution shorter for \>=4.1:

### , 74 bytes

Or **\>=4.1, 60 bytes** by replacing two `function` occurrences with `\`s.

```
function(s,i=0,f=function(a=s[i<<-i+1])"if"(a<58,a,c(40,f(),a,f(),41)))f()

```

Try it online!

Same as above, but here `i` is "local" for the main function, but "global" for the recursive one.
> 4 votes

# Answer
# Prolog (SWI), ~~95~~ 81 bytes

Haven't programmed in Prolog for a while, so this was a fun challenge to do.

Prologs ability to handle strings and atoms do not make it easy. Probably suboptimal, but here we go:

```
f(R,[H|T]):-T=[],H<97,R=[H];append(X,Y,T),f(C,X),f(D,Y),flatten([40,C,H,D,41],R).

```

Input and output are both codepoint lists.

Try it online!
> 4 votes

# Answer
# Retina, 74 bytes

```
+`([a-z])((([a-z])|(?<-4>\d))*\d)((([a-z])|(?<-7>\d))*\d)
($2$U$1$5)
T`L`l

```

Try it online! Link includes test cases. Explanation:

```
([a-z])((([a-z])|(?<-4>\d))*\d)((([a-z])|(?<-7>\d))*\d)

```

Match a letter followed by two prefix expressions. A prefix expression is readily identified as being a substring that contains exactly one more digit than letter.

```
($2$U$1$5)

```

Convert this letter to infix and upper case it to show that it has been converted.

```
+`

```

Keep making replacements until all of the letters have been upper cased.

```
T`L`l

```

Change all the letter back to lower case again.
> 3 votes

# Answer
# Perl 5 -p, 51 bytes

```
s/(\D) (\S+) (\S+)/ ($2$1$3)/||s/.\b/ $&/ until/^ /

```

Try it online!

Uses regexp substitutions and treat the $\_ string as an array where the first element is the input, or what is left of it while processing, and the rest of the array elements is the working stack. Commands to see it's behavior on the last test case:

```
INP=a1fcb46d4e95ig6h42kj32l68      #which is the last test case
echo $INP|perl -plE'say,s/(\D) (\S+) (\S+)/ ($2$1$3)/||s/.\b/ $&/ until/^ /'
a1fcb46d4e95ig6h42kj32l68
a1fcb46d4e95ig6h42kj32l6 8
a1fcb46d4e95ig6h42kj32l 6 8
a1fcb46d4e95ig6h42kj32 (6l8)
a1fcb46d4e95ig6h42kj3 2 (6l8)
a1fcb46d4e95ig6h42kj 3 2 (6l8)
a1fcb46d4e95ig6h42k (3j2) (6l8)
a1fcb46d4e95ig6h42 ((3j2)k(6l8))
a1fcb46d4e95ig6h4 2 ((3j2)k(6l8))
a1fcb46d4e95ig6h 4 2 ((3j2)k(6l8))
a1fcb46d4e95ig6 (4h2) ((3j2)k(6l8))
a1fcb46d4e95ig 6 (4h2) ((3j2)k(6l8))
a1fcb46d4e95i (6g(4h2)) ((3j2)k(6l8))
a1fcb46d4e95 ((6g(4h2))i((3j2)k(6l8)))
a1fcb46d4e9 5 ((6g(4h2))i((3j2)k(6l8)))
a1fcb46d4e 9 5 ((6g(4h2))i((3j2)k(6l8)))
a1fcb46d4 (9e5) ((6g(4h2))i((3j2)k(6l8)))
a1fcb46d 4 (9e5) ((6g(4h2))i((3j2)k(6l8)))
a1fcb46 (4d(9e5)) ((6g(4h2))i((3j2)k(6l8)))
a1fcb4 6 (4d(9e5)) ((6g(4h2))i((3j2)k(6l8)))
a1fcb 4 6 (4d(9e5)) ((6g(4h2))i((3j2)k(6l8)))
a1fc (4b6) (4d(9e5)) ((6g(4h2))i((3j2)k(6l8)))
a1f ((4b6)c(4d(9e5))) ((6g(4h2))i((3j2)k(6l8)))
a1 (((4b6)c(4d(9e5)))f((6g(4h2))i((3j2)k(6l8))))
a 1 (((4b6)c(4d(9e5)))f((6g(4h2))i((3j2)k(6l8))))
 (1a(((4b6)c(4d(9e5)))f((6g(4h2))i((3j2)k(6l8)))))

```
> 3 votes

# Answer
# Ruby, ~~62~~ ~~60~~ 54 bytes

```
->e,i=-1{(f=->c=e[i+=1]{c=~/\d/?c:?(+f[]+c+f[]+?)})[]}

```

Saved 6 more bytes by removing parenthesis and using ternary operator by the hint from Dingus.

Try it online!
> 3 votes

# Answer
# Rust, 117 bytes

```
fn f(s:&mut std::str::Chars)->String{let c=s.next().unwrap();if c<'a'{c.into()}else{format!("({}{}{})",f(s),c,f(s))}}

```

Takes a mutable reference to a character iterator and returns a string. Requires Rust 1.46+.

Rust Playground

### Ungolfed

```
fn f(iterator: &mut std::str::Chars) -> String
{
    // Get next character
    let c = iterator.next().unwrap();

    // If it's a digit
    if c < 'a' {
        c.into() // convert the sole digit character into a string
    }
    // Otherwise
    else {
        // Build infix string with two recursive calls for the operands
        format!("({}{}{})", f(iterator), c, f(iterator))
    }
}

```
> 3 votes

# Answer
# Curry (PAKCS), 44 bytes

```
f(a:b++c)|a>'9'='(':f b++a:f c++")"
f[a]=[a]

```

Try it online!
> 3 votes

# Answer
# Lexurgy, 164 bytes

```
class d {\0,\1,\2,\3,\4,\5,\6,\7,\8,\9}
a propagate:
{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}$1 {(\( []+ \)),@d}$2 {(\( []+ \)),@d}$3=>\( $2 $1 $3 \)

```

Explanation:

```
class d {\0,\1,\2,\3,\4,\5,\6,\7,\8,\9} # define digits
a propagate: # while the input changed last iteration...
# match an op
{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}$1
# match left expr
    {(\( []+ \)),@d}$2
# match right expr
        {(\( []+ \)),@d}$3
# put parens, swap op and left
            =>\( $2 $1 $3 \)

```
> 3 votes

# Answer
# C (gcc), ~~71~~ 70 bytes

-1 thanks to AZTECCO

```
f(char*s){s=putchar(*s+!(*s++>60?f("("),s=f(s):1))>60?f(s)+!f(")"):s;}

```

Try it online!

Relies on summands evaluating from left to right. Outputs to stdout.
> 2 votes

# Answer
# Java (JDK), 91 bytes

```
Object f(java.util.Iterator<Character>s){var c=s.next();return c<97?c:"("+f(s)+c+f(s)+")";}

```

Try it online!
> 2 votes

# Answer
# Wolfram Language (Mathematica), 40 bytes

```
If[t=##2;#>60,##&[40,#0@t,#,#0@t,41],#]&

```

Try it online!

Input and output a sequence of character codes.

### Wolfram Language (Mathematica), 37 bytes

```
If[t=##2;#>60,40 .#0@t.#.#0@t. 41,#]&

```

Try it online!

Outputs a `Dot` of character codes instead.
> 2 votes

# Answer
# Scala, 57 bytes

```
s=>{def g:Any={val n=s.next;if(n>58)s"($g$n$g)"else n};g}

```

Try it online!

Takes an iterator of characters instead of a string so it can save its position.

## Without an iterator, 118 bytes

```
f(_)._1
def f(s:String):(Any,String)=if(s(0)<58)s.splitAt(1)else{val(a,t)=f(s.tail);val(b,u)=f(t);s"($a${s(0)}$b)"->u}

```

Try it online!
> 2 votes

# Answer
# Haskell, 63 bytes (or 69\*)

Below, `a` is Haskell's IO monad computation of type `IO ()` which, when executed, reads the expression from `stdin` and outputs the result to `stdout`.

```
a=getChar>>=(putStr#)
p#c|c<'a'=p[c]|1<2=p"(">>a>>p[c]>>a>>p")"

```

Try it online!

### Ungolfed code

```
main = a >> putStrLn ""

a :: IO ()
a = do
  c <- getChar -- read a character c
  putStr # c   -- if c is an operator, process its arguments

(#) :: (String -> IO ()) -> Char -> IO ()
p # c
  | c < 'a' = p[c] -- the character is a number
  | otherwise = do -- the character is an operator
    p "(" -- print "(" to stdout
    a     -- read the left subexpression and output it in the required format
    p [c] -- print the operator to stdout
    a     -- read the right subexpression and output it in the required format
    p ")" -- print ")" to stdout

```

### \*Disclaimer

I am not sure if the standard code golf rules permit answers being Haskell's IO monads of type `IO ()`. In this meta answer, it was stated that computations of type `IO a` which read `stdin` and produce a value of type `a` are allowed. Should the `IO ()` type be unacceptable, I shall replace my answer with this 69 byte entry with computation of type `IO String`try it online!.

I asked for a clarification in this comment.
> 2 votes

# Answer
# Python, ~~146~~ ~~139~~ 84 bytes

```
lambda x,s=[]:[(s:=s+[n if n<":"else"("+s.pop()+n+s.pop()+")"])for n in x[::-1]][-1]
```

Attempt This Online!

*¯55 thanks to @emanresuA*
> 2 votes

# Answer
# Charcoal, 54 bytes

```
⊞υ⟦⟧ＦＳ¿№βι⊞υ⟦ι⟧«⊞§υ±¹ιＷ⁼³Ｌ§υ±¹⊞§υ±²⪫()⪫⮌⁺⟦⊟§υ±¹⟧⊟υω»⊟υ

```

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

```
⊞υ⟦⟧

```

Start with no expression.

```
ＦＳ

```

Loop over the input characters.

```
¿№βι⊞υ⟦ι⟧

```

If it's a letter then begin a new operation.

```
«

```

Otherwise:

```
⊞§υ±¹ι

```

Push this operand to the current operation.

```
Ｗ⁼³Ｌ§υ±¹

```

While the current operation has both of its operands, ...

```
⊞§υ±²⪫()⪫⮌⁺⟦⊟§υ±¹⟧⊟υω

```

Convert it to infix and push it to its parent operation, which becomes the new current operation.

```
»⊟υ

```

Output the final infix code.
> 1 votes

# Answer
# Pip, 34 bytes

```
c:POacGT9?pJ J[b:REacREa@>#:bDCp]c

```

Takes the prefix expression as a command-line argument. Replit! Here's the closest I can get with TIO: Try it online!

### Explanation

Recursive program; parses the first prefix expression from its input and returns its infix representation. If the input starts with a digit, the expression is just that single digit. Otherwise, the first character is an operator and its operands are the results of recursively parsing twice.

```
c:POacGT9?pJ J[b:REacREa@>#:bDCp]c
    a                               Current prefix expression, possibly including
                                    some extra trailing characters
  PO                                Pop the first character
c:                                  and store it in local variable c
     cGT9                           Is c greater than "9" (string comparison)?
         ?                          If so, it's a letter:
              [                 ]    Make a list containing the following:
                                      1)
                 REa                   Call the program recursively on the portion of
                                       the input after the (popped) first character
               b:                      and assign the result to local variable b
                                      2)
                    c                  The popped first character (the operator)
                                      3)
                     RE                Call the program recursively on
                       a@>             the portion of the input after this index...
                          #:           Length of
                            bDCp       b from earlier with all parentheses deleted
             J                       Join that list into a single string
          pJ                         Join "()" on that string
                                    Otherwise, c is a number:
                                 c   Return the number

```
> 1 votes

# Answer
# Stax, 17 bytes

```
è▼2╖X!ú▬Ie╓ƒû≈²O┬

```

Run and debug it
> 1 votes

# Answer
# BQN, 38 36 bytes

```
{{'9'(1⌽")("∾∾˜∾⊢)⍟<⊑˜i+↩1}i←¯1}

```

Try it here.

How it works:

The outer function simply makes a counter `i` and passes the input  to the inner function as .

```
{'9'(1⌽")("∾∾˜∾⊢)⍟<⊑˜i+↩1} # Inner function
                        i+↩1  # Increment i,
                     ⊑˜      # and use it to index into the input
 '9'(             )⍟<         # if the code point is greater than '9'
               ∾⊢            # recurse and prepend the result
            ∾˜               # recurse and append the result
     1⌽")("∾                  # wrap with parentheses

```
> 1 votes

# Answer
# Pyth, 33 bytes

```
V_Q?-1/GN=Y+YN=Y+YjN[+\(.)Y+.)Y\)

```

Try it online!

```
                                     # Q = eval(input())
                                     # G = "abcdefghijklmnopqrstuvwxyz"
                                     # Y = []
V_Q                                  # for N in reversed(Q):
   ?-1/GN                            #   if N in G:
         =Y+YN                       #     Y.append(N)
                                     #   else:
                   jN[+\(.)Y+.)Y\)   #     X = N.join(['(' + Y.pop(), Y.pop() + ')'])
              =Y+Y                   #     Y.append(X)

```
> 1 votes

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