# 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

• Must the input be taken as a string or may it be a list? – DanTheMan May 26 at 1:20
• @DanTheMan "list of chars or list of codepoints is also OK." – Bubbler May 26 at 1:21
• Since quaternion multiplication is not commutative, I think it would be helpful to clarify in the question text that (-1)i = i(-1) = -i, and similarly for j and k. – DLosc May 27 at 18:18
• @Bubbler I thought about posting this exact challenge around a year ago, but I saw the linked challenge and viewed it as a dupe. :( – Don Thousand May 27 at 19:57

# Charcoal, 3229 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).

• I think you can save three bytes: tio.run/… This works because the code point for i is 1 mod 8. – Nick Kennedy May 27 at 0:30
• @NickKennedy That's a great find! I have to admit I hadn't even twigged the mod 4 relationship, which would already have saved me a byte. – Neil May 27 at 9:08
• Very nifty! I wonder if there's a theoretical reason you can represent the quaternions this way. It looks like the invertible affine functions modulo 8, which have form $f(x) = a x + b$ with $a$ odd form a 32-element group under composition. And the ones you list generate an 8-element subgroup isomorphic to the quaternions, restricted to $a$ being $1$ or $3$, and $b$ being even when $a$ is $1$ and odd otherwise. – xnor May 28 at 1:11
• @Neil I forgot to ask you at the time, did you find this just by playing around, via some higher-level insight, or by some more exhaustive method of search? – Jonah Jun 2 at 1:12
• @Jonah Since there are 8 outputs, I wanted to number the outputs so that I could at the least use a look-up table to multiply. I don't know why I first tried with the order 1ijk-1-i-j-k, but when the look-up table for x=>xj luckily turned out to be 23456701, some playing around quickly turned up my original formulas for i and k. – Neil Jun 2 at 9:37

# 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!

# 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.

• Wow, you had basically the same idea as I did. – EasyasPi May 26 at 3:08

# Retina, 43 bytes

3{\bii
-
ij
k
\bik
-j
}Tijkjki
--

\B$1  Try it online! Link includes test cases. Explanation: 3{  Loop three times. \bii - ij k \bik -j  Perform some simplifications. Tijkjki  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.

# 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.

• Very impressive. Congrats. – Eric Duminil May 26 at 17:12
• -2 bytes – dingledooper May 26 at 19:56

# 05AB1E, 40 37 bytes

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

Δ                # 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«

Δ                    # 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

• -1 byte in your 37 byte solution by changing J1« to 1ª, and -1 in your 43 byte solution by changing Σ'-Ê] to '-†}. – Kevin Cruijssen yesterday

# 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

• As @NickKennedy points out, y&4==0, so you don't need to reduce y mod 4, assuming the intermediate value doesn't exceed the maximum save integer. – Neil May 27 at 9:22

# 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.

# 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!

• I was able to trim 8 bytes by making things more tacit – coltim May 26 at 15:41
• @coltim great! i was expecting you might be able to improve it but not by that many bytes :) – ngn May 26 at 19:24

# 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"

• You can remove the trailing ” to have it as a full program: Try it online! – caird coinheringaahing May 27 at 0:08
• @cairdcoinheringaahing thanks for pointing out! – Nick Kennedy May 27 at 0:16
• You don't need the Ḃ. This works because 3² is 1 mod 8. (I can't believe I got to say that...) – Neil May 27 at 9:13
• I believe 3*żæ.ƒ0%8ṃ“ijk1””--¦ should work for a byte save. When the %8 result is greater than 3 ṃ will be length two, and ¦ will replace the first character with a '-'. – Jonathan Allan May 27 at 12:24

# C (gcc), 104103 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;
}

• Using a different output method gives (string embedded in an int) 93 bytes – rtpax May 27 at 18:13
• Also, I got a 95 byte answer using a modular arithmetic instead of xoring. Thought I'd share – rtpax May 27 at 18:15

# APL(Dyalog Unicode), 33 bytes SBCS

A port of Nick Kennedy's Jelly answer.

4(' -' '1ijk'⌷⍨¨⌊⍤÷⍨,|)8|⊢⊥⍨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
8|          ⍝ modulo 8


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

⌊⍤÷⍨,| is divmod with swapped arguments, and both resulting integers are used to index into one string.

# 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.

• -2 bytes by starting the helper link with , and reducing as ç/ instead of ,Ç¥/, and by removing the trailing ” – caird coinheringaahing May 26 at 1:46

# 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

• You lost to Retina - a lang that doesn't even have addition - but +1 – StackMeter May 27 at 7:47
• @StackMeter Retina's perfect for stuff like this, and I have an idea... – A username May 27 at 8:43
• ok then go ahead – StackMeter May 27 at 9:05

# 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.

• If you double the ( in the header you can change the ) to a } and drop the leading {, saving two bytes. – Neil May 26 at 9:32
• You can use (\w)\1 instead of ii|jj|kk. – Neil May 26 at 9:42
• I think replacing ji|kj|ik with -$^$& works. – Neil May 26 at 9:44
• @Neil Thanks for the tips! The $^ idea is particularly nice. Separately, your answers are quite clever, using the idea of rotating or in getting rid of k early to avoid writing out most of the cases. – FryAmTheEggman May 26 at 16:35 # 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. # 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). # 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! # 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! • The $s-replace-split\$_ is so impressive, good one ! – Julian May 27 at 10:14

# J, 41 bytes

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


Try it online!

Neil's excellent idea applied to J.

# 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.

# 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.

# 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.