# Multiply elements of the dihedral group

This is a copy cat question of Simplify ijk string applied to the other nonabelian group of order 8. See also Dihedral group composition with custom labels.

## Challenge

Given a string made of r and s interpret it as the product of elements of the dihedral group $$\D_8\$$ and simplify it into one of the eight possible values "", "r", "rr", "rrr", "s", "rs", "rrs", and "rrrs". The empty string denotes the identity element $$\1\$$.

The evaluation rules are as follows: $$rrrr = 1\\ ss = 1\\ sr = rrrs$$ The multiplication on the dihedral group 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 or list. You may output any amount of leading and trailing whitespace (spaces, tabs, newlines). You may use any other pair of distinct characters for r and s except for a tab, space, or newline. (If you really want to you can pick r or s to be whitespace, you can as long as you don't have leading or trailing whitespace.) It's also fine to use numbers for r and s, for example if you take 0 for r and 1 for s, it would be okay to do I/O like [1, 0] ==> [0, 0, 0, 1].

## Test cases

"" -> ""
"r" -> "r"
"rrr" -> "rrr"
"s" -> "s"
"rs" -> "rs"
"rrs" -> "rrs"
"rrrr" -> ""
"rrrrrr" -> "rr"
"sr" -> "rrrs"
"rsr" -> "s"
"srsr" -> ""
"srr" -> "rrs"
"srs" -> "rrr"
"rsrsr" -> "r"
"sssrrr" -> "rs"


## Reference implementation

Here is a Javascript reference implementation.

function f(x) {
let lastx;
while(lastx !== x){
lastx = x;
x = x.replace("rrrr", "");
x = x.replace("sr", "rrrs");
x = x.replace("ss", "");
}
return x;
}

• Can I/O be taken using different characters? May 27, 2021 at 22:42
• Surprisingly no one asked about different characters on "ijk". I think it is okay, I will add that.
– Hood
May 27, 2021 at 22:52
• Can we use 1/0 for r and s? May 27, 2021 at 22:54
• 1 and 0 for r and s is fine. I think doing I/O as a list of 1 and 0 rather than strings / characters is also fine. I am not sure what the ideal wording for this is.
– Hood
May 27, 2021 at 22:56
• Can I use an output format that is different from the input format? May 28, 2021 at 4:41

# J, 23 bytes

~:/I.@,~4|[:-/1#;._1@,]


Try it online!

Takes a boolean vector where 0 represents r and 1 represents s, and returns the result in the same encoding.

### How it works

Imagine evaluating the chunks of $$\r^n s r^m s\$$ from the start. If we evaluate $$\sr\$$ in the middle $$\m\$$ times, we get $$\r^{n+3m}s^2 = r^{n+3m}\$$. We can repeat the process to the end. Let's represent the input as a sequence of integers which represent the number of $$\r\$$'s when separated by $$\s\$$'s, like sssrrr -> [0, 0, 0, 3]. Then the following holds:

• The alternating sum ([a, b, c, d, ...] -> a - b + c - d + ...) modulo 4 is the final number of $$\r\$$'s.
• The length plus 1 modulo 2 is the final number of $$\s\$$'s.
~:/I.@,~4|[:-/1#;._1@,]  NB. Input: a boolean vector
1#;._1@,]  NB. Get the lengths of runs of r's between s's
4|[:-/  NB. Alternating sum modulo 4 = the number of final r's
~:/             NB. Reduction by unequal on the original input,
NB. i.e. the number of s's in the input mod 2
NB. = the number of final s's
I.@,~        NB. Reverse concat and generate that many 0's and 1's


# Jelly, 15 bytes

ṣ1ẈṚḅ3%4,SḂ$Ø.x  Try it online! Same algorithm as above. Doesn't feel well golfed to me though; maybe I missed some good alternative built-ins. ṣ1ẈṚḅ3%4,SḂ$Ø.x  Input: a list of zeros and ones
s1Ẉ              Split at ones, then get length of each chunk
Ṛḅ3%4         Reverse, evaluate in base 3, modulo 4
,        Pair with...
SḂ$Sum % 2 Ø.x Generate that many zeros and ones respectively  • Ṛḅ- is a-b+c-..., not that it saves any bytes. May 28, 2021 at 4:04 # perl -p, 31 bytes 1while s/rrrr|ss//||s/sr/rrrs/;  Takes advantage of substitution returning truthy iff anything was substituted. # Retina 0.8.2, 18 bytes {rrrr|ss sr rrrs  Try it online! Straightforward port of the reference implementation. # Python 2, 58 bytes • @dingledooper saves 12 bytes by switch to Python 2 and finding out some bit-wise operators expression which I cannot understand! p=q=0 for b in input():p^=b;q+=~p/~b^p print q%4*[0]+p*[1]  Try it online! I/O as an array of integers, r = 0, s = 1. JavaScript needs too many bytes to repeat some strings. • Following your method, I can shorten it to 58 bytes, by switching to Python 2 and taking input as a list of 0 and 1 instead of a string. May 28, 2021 at 4:19 • A slightly-less-crazy looking variant of dingledooper's magic ~p/~b^p is 1+p-b^p (which gives -1 instead of 3 but it's the same mod 4). There's also (b==p)-p which is longer is Python but might be shorter in other langs. – xnor May 28, 2021 at 21:46 # 05AB1E, 16141312 10 bytes -3 thanks to ovs. -2 thanks to Kevin Cruijssen. Δ48bγKT₄R:  Try it online! Beats all other answers. Uses 0 for r and 1 for s. Δ48bγKT₄R: # full program Δ # while top of stack changes: : # replace all instances of... T # 10... : # in... # implicit input... # (implicit) or top of stack if not first iteration... K # with none of the elements of... 48 # literal... b # in binary... γ # split into chunks of consecutive equal elements... : # with... ₄ # 1000... R # in reverse # implicit output  • õ: can be replaced by K, which puts this back in the lead ;) – ovs May 27, 2021 at 23:21 • 8b is the same as ₄ (1000). – ovs May 28, 2021 at 14:00 • @ovs Oh my god how could I forget xD May 28, 2021 at 15:52 • -2 bytes: Δ48bγKT₄R:, it combines the removal of 0000 and 11 into 48bγK. Jul 27, 2021 at 14:21 # JavaScript (ES6), 54 53 bytes Expects a string with 1 for s and 2 for r. Returns another string in the same format. f=s=>s-(S=s.replace(/2222|1./,s=>s%3?"":2221))?f(S):s  Try it online! ### Commented f = s => // f is a recursive function taking the input string s s - ( // test whether s is different from the updated string S S = s.replace( // which is obtained by looking for the 1st occurrence /2222|1./, // of either "2222", "11" or "12" s => // and replacing it with s % 3 ? "" // an empty string for "2222" and "11" : 2221 // or "2221" for "12" ) // end of replace() ) ? // if s is not equal to S: f(S) // repeat the process with S : // else: s // we're done: return s  # J, 29 27 bytes rplc&(srrrrs,,.rrrrss)^:_  Try it online! • rplc&(srrrrs,,.rrrrss) Keep doing the needed replacements... • ^:_ Until it stops changing # Jelly, 24 bytes œṣØ0Fœṣ1x4¤FœṣØ.j14BFµÐL  Try it online! Uses 1 for r and 0 for s ## How it works Jelly does not have a good time with replacements. Its translate atom, y, only handles replacing specific, individual values (such as integers) with others, and cannot work with replacing groups of items. Instead, we split on the values we want to replace, and join with their replacements œṣØ0Fœṣ1x4¤FœṣØ.j14BFµÐL - Main link. Takes a list of bits B on the left µÐL - Apply the chain to the left on B until it reaches a fixed point Ø0 - Yield [0, 0] œṣ - Split around 0,0 F - Flatten 1x4¤ - Yield [1,1,1,1] œṣ - Split around 1,1,1,1 F - Flatten Ø. - Yield [0, 1] œṣ - Split around 0,1 j14 - Join with 14 B - Convert to binary F - Flatten  # Factor, 69 65 bytes [ [ "sr""rrrs""rrrr""" "ss"""[ replace ] 2tri@ ] to-fixed-point ]  Try it online! -4 thanks to @Bubbler • Abuse the fact that strings don't require trailing whitespace in the version of Factor TIO uses. • 2tri@ Call a quotation on three pairs of objects. e.g. 1 2 3 4 5 6 [ + ] 2tri@ -> 3 7 11. • to-fixed-point Call a quotation until its input stops changing. • May 28, 2021 at 0:37 • @Bubbler Thanks! And here I thought I had found a legitimate use of ALIAS:! May 28, 2021 at 0:47 # Charcoal, 2521 20 bytes ⁻⭆⪪θs×ι⊕⊗κ×r⁴×s﹪№θs²  Try it online! Link is to verbose version of code. Based on a method @Bubbler mentioned in chat. Explanation: ⁻⭆⪪θs×ι⊕⊗κ×r⁴  Split the input on ss, repeat alternate segments thrice, then use string substitution to reduce the length modulo 4. ×s﹪№θs²  Output an s if there were an odd number of ss in the input. ⁻⁻θr¦ss also works for the same byte count, but I can't find anything shorter. 20 19 bytes by taking I/O as strings of 0s and 1s: ⁻⭆⪪θ1×ι⊕⊗κ×0⁴×1﹪Σθ²  Try it online! Link is to verbose version of code. Explanation: As above but counts 1s by taking the digital sum of the input. Previous 25-byte string substitution answer: Ｗ№θsr≔⪫⪪θsr¦rsssθ⁻⁻θ×r⁴ss  Try it online! Link is to verbose version of code. Explanation: Ｗ№θsr  While the input contains sr... ≔⪫⪪θsr¦rsssθ  ... replace all occurrences of sr with rsss. ⁻⁻θ×r⁴ss  Remove rrrr and ss and output the result. I tried a numeric approach but it turned out to be slightly longer at 29 bytes: ≔⁰θＦＳ¿Σι≦⁻³θ≦⁺²θ§⪪”)∨'✂/Ｏ;”2θ  Try it online! Link is to verbose version of code. I/O is as strings of 0s and 1s. Explanation: The values are encoded to integers equivalent to 0..7 (modulo 8) in the order , 01, 0, 1, 00, 0001, 000, 001. A 1 subtracts the integer from 3 while a 0 adds 2 to the integer. ≔⁰θ  Start with 0. ＦＳ  Loop over the input. ¿Σι  If the digit is nonzero, ... ≦⁻³θ  ... then subtract the integer from 3, ... ≦⁺²θ  ... otherwise add 2 to it. §⪪”)∨'✂/Ｏ;”2θ  Index into a look-up table to find the final result. (The number of zeros is actually given by (x>>1)^(x&1) and the number of ones by x&1 but Charcoal has no bitwise XOR operator, so the best I could do was this look-up table.) I was able to save a byte by using two variables: ≔⁰θ≔⁰ηＦＳ¿Σι≦¬θ≦⁺⊕⊗θη×0﹪η⁴×1θ  Try it online! Link is to verbose version of code. I/O is as strings of 0s and 1s. Explanation: The two variables track the number of 1s and 0s. If there are an odd number of 1s so far then each input 0 adds 3 otherwise it adds 1. ≔⁰θ≔⁰η  Start with 0 1s and 0 0s. ＦＳ  Loop over the input. ¿Σι  If the digit is nonzero, ... ≦¬θ  ... then invert the parity of the 1s, ... ≦⁺⊕⊗θη  ... otherwise add 1 or 3 0s as appropriate. ×0﹪η⁴  Output the number of 0s (mod 4). ×1θ  Output a 1 if appropriate. # Vyxal, 17 16 bytes λ88ok2‹o89k2⇩V;Ẋ  Try it Online! Creative input abuse. Takes r as 9 and s as 8. λ ;Ẋ # Repeat until input doesn't change 88o # Get rid of 88s (ss) k2‹ # 10000 - 1 = 9999 (=rrrr) o # Get rid of those as well 89 # 89 (sr) k2⇩ # 10000 - 2 = 9998 (rrrs) V # Replace (sr with rrrs)  # 05AB1E, 15 bytes Uses 0 and 1 for r and s. Δ•BƵ?ù•₂вb€¦ι:  Try it online! Δ # Until the output doesn't change: •BƵ?ù•₂в # Compressed integer list [16, 1, 7, 1, 6, 17] b€¦ # Convert to binary and remove most significant digit ["0000", "", "11", "", "10", "0001"] ι # Split into two separate lists by alternating the values ["0000", "11", "10"], ["", "", "0001"] : # Replace  # Java, 76 bytes s->{for(;s!=(s=s.replaceAll("rrrr|ss","").replace("sr","rrrs")););return s;}  Try it online! # Red, 82 bytes func[s][while[parse s[some thru[remove["rrrr"|"ss"]| change"sr""rrrs"]to end]][]s]  Try it online! # Bash with sed, 86 84 bytes Saved 2 bytes thanks to Digital Trauma!!! until [[$a = $1 ]];do a=$1
set -- sed 's/sr/rrrs/;s/rrrr\|ss//'<<<$a done echo$a


Try it online!

• Shave a couple of bytes off. But is much shorter if you just use sed and no bash. May 28, 2021 at 15:47
• @DigitalTrauma sed and no bash doesn't make sense, since you already have a sed answer, but bash without sed is possible,
– Neil
May 28, 2021 at 15:52
• @DigitalTrauma Nice ones - thanks! :D May 28, 2021 at 16:53

# Jelly,  21  18 bytes

Not Jelly's forté! Perhaps There is a clever way to do it though?.

2“Ð¡©¡¦Ñ‘ḃœṣjƭƒµÐL


A monadic Link that accepts a list of 1s (r) and 2s (s), and yields the same.

Try it online! (The footer translates from an rs string, calls the link and translates back.)
Or see the test-suite.

### How?

2“Ð¡©¡¦Ñ‘ḃœṣjƭƒµÐL - Link: list of integers (in [1,2]): S
µÐL - loop until no change f(X=S)->X:
2                  -   two
“Ð¡©¡¦Ñ‘          -   code-page indices = [15,0,6,0,5,16]
ḃ         -   to bijective base (2) -> [[1,1,1,1],[],[2,2],[],[2,1],[1,1,1,2]]
ƭ     -     tie (call each of these two links in turn):
œṣ       -       split (left) at sublists equal to (right)
j      -       join (left) with (right)
}...i.e:
split at [1,1,1,1], join with []
split at [2,2], join with []
split at [2,1], join with [1,1,1,2]


# R, 68 66 bytes

function(x){while(x!=(x=sub("rrrr|ss","",sub("sr","rrrs",x))))0;x}


Try it online!

-2 bytes thanks to iota

Applies reference implementation.

• 66 bytes by using the same approach as my Java answer. May 28, 2021 at 22:47
• @iota thanks! I had that idea and recall testing it without success, but looks like my memory is failing me... May 29, 2021 at 8:03

# Python 3.8, 86 bytes

f=lambda s,r=str.replace:f(s)if s!=(s:=r(r(r(s,"rrrr",""),"ss",""),"sr","rrrs"))else s


Try it online!

# Python 3, 90 bytes

f=lambda x,s=str.replace:f(s(s(s(x,"r"*4,""),"ss",""),"sr","rrrs"))if x not in"rrrs"else x


Try it online!

# Stax, 19 bytes

╚ò/i»┬⌐ÇÑ ╒‼î┐╟▌z¥²


Run and debug it

Plain Regex.

Bubbler's method is a bit long in Stax since zeroes get converted to spaces.

# sed 4.2.2, 26

:
s/rrrr|ss//
s/sr/rrrs/
t


Try it online!

# ///, 21 bytes

/sr/rrrs//rrrr///ss//


Try it online!

Input is appended to the end of the code.

A straightforward implementation of the three evaluation rules. Note that after every sr is replaced by rrrs recursively, the resulting string is of the form $$\r^xs^y\$$, and neither of the remaining rules will change this fact. Thus, we do not need to revisit sr -> rrrs after applying the other two rules.

# Pure Bash, 75 bytes

a=${1//sr/rrrs};a=${a//rrrr/};a=${a//ss/};[ "$a" = "$1" ]&&echo$1||. $0$a


Try it online! Why use sed when you don't need to?

# Core Maude, 81 bytes

mod D is inc LIST{Nat}. eq 0 0 0 0 = nil . eq 1 1 = nil . eq 1 0 = 0 0 0 1 . endm


### Example Session

             \||||||||||||||||||/
--- Welcome to Maude ---
/||||||||||||||||||\
Maude 3.1 built: Oct 12 2020 20:12:31
Fri May 28 22:50:23 2021
Maude> mod D is inc LIST{Nat}. eq 0 0 0 0 = nil . eq 1 1 = nil . eq 1 0 = 0 0 0 1 . endm
Maude> red nil .
reduce in D : nil .
rewrites: 0 in 0ms cpu (0ms real) (~ rewrites/second)
result List{Nat}: nil
Maude> red 0 .
reduce in D : 0 .
rewrites: 0 in 0ms cpu (0ms real) (~ rewrites/second)
result Zero: 0
Maude> red 0 0 0 .
reduce in D : 0 0 0 .
rewrites: 0 in 0ms cpu (0ms real) (~ rewrites/second)
result NeList{Nat}: 0 0 0
Maude> red 1 .
reduce in D : 1 .
rewrites: 0 in 0ms cpu (0ms real) (~ rewrites/second)
result NzNat: 1
Maude> red 0 1 .
reduce in D : 0 1 .
rewrites: 0 in 0ms cpu (0ms real) (~ rewrites/second)
result NeList{Nat}: 0 1
Maude> red 0 0 1 .
reduce in D : 0 0 1 .
rewrites: 0 in 0ms cpu (0ms real) (~ rewrites/second)
result NeList{Nat}: 0 0 1
Maude> red 0 0 0 0 .
reduce in D : 0 0 0 0 .
rewrites: 1 in 0ms cpu (0ms real) (~ rewrites/second)
result List{Nat}: nil
Maude> red 0 0 0 0 0 0 .
reduce in D : 0 0 0 0 0 0 .
rewrites: 1 in 0ms cpu (0ms real) (~ rewrites/second)
result NeList{Nat}: 0 0
Maude> red 1 0 .
reduce in D : 1 0 .
rewrites: 1 in 0ms cpu (0ms real) (~ rewrites/second)
result NeList{Nat}: 0 0 0 1
Maude> red 0 1 0 .
reduce in D : 0 1 0 .
rewrites: 2 in 0ms cpu (0ms real) (~ rewrites/second)
result NzNat: 1
Maude> red 1 0 1 0 .
reduce in D : 1 0 1 0 .
rewrites: 3 in 0ms cpu (0ms real) (~ rewrites/second)
result List{Nat}: nil
Maude> red 1 0 0 .
reduce in D : 1 0 0 .
rewrites: 3 in 0ms cpu (0ms real) (~ rewrites/second)
result NeList{Nat}: 0 0 1
Maude> red 1 0 1 .
reduce in D : 1 0 1 .
rewrites: 2 in 0ms cpu (0ms real) (~ rewrites/second)
result NeList{Nat}: 0 0 0
Maude> red 0 1 0 1 0 .
reduce in D : 0 1 0 1 0 .
rewrites: 3 in 0ms cpu (0ms real) (~ rewrites/second)
result Zero: 0
Maude> red 0 0 1 1 1 .
reduce in D : 0 0 1 1 1 .
rewrites: 1 in 0ms cpu (0ms real) (~ rewrites/second)
result NeList{Nat}: 0 0 1
Maude> red 1 1 1 0 0 0 .
reduce in D : 1 1 1 0 0 0 .
rewrites: 12 in 0ms cpu (0ms real) (~ rewrites/second)
result NeList{Nat}: 0 1


### Ungolfed

mod D is
inc LIST{Nat} .

eq 0 0 0 0 = nil .
eq 1 1 = nil .
eq 1 0 = 0 0 0 1 .
endm


I chose to encode r as 0 and s as 1. (It would cost 19 more bytes to use r and s directly instead.)

I am shocked and thrilled that Core Maude is actually competitive in this question! Maude's built-in list module implements lists using the __ operator (juxtaposition), which is associative and has nil as its identity. This means an equation can match any sublist. Since this is just "reduce until done", we don't even need our own function symbol to separate input from output.

We could probably get away with shaving off one byte, but it would not technically be a correct Core Maude program anymore. The existing Maude interpreter does not differentiate between protecting (pr) and including (inc) modules, but according to the spec our equations would not be valid with protecting.

# C (gcc), 118 $$\\cdots\$$ 96 95 bytes

i;b;p;q;f(char*s){for(;s[i];q+=~p/~b^p)p^=b=s[i++]-48;for(i=p+q%4;i--;*s++=48^i<p);i=p=q=*s=0;}


Try it online!

Uses '0' for 'r', '1' for 's'`, and dingledooper's formula for tsh's Python answer.