Multiply elements of the dihedral group

Question

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"
"rrsss" -> "rrs"
"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;
}

Answer 1

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

Answer 2

perl -p, 31 bytes

1while s/rrrr|ss//||s/sr/rrrs/;

Takes advantage of substitution returning truthy iff anything was substituted.

Answer 3

Retina 0.8.2, 18 bytes

{`rrrr|ss

sr
rrrs

Try it online! Straightforward port of the reference implementation.

Answer 4

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.

Answer 5

05AB1E, 16 14 13 12 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

Answer 6

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

Answer 7

J, ²⁹ 27 bytes

rplc&(sr`rrrs,,.rrrr`ss)^:_

Try it online!

• rplc&(sr`rrrs,,.rrrr`ss) Keep doing the needed replacements...
• ^:_ Until it stops changing

Answer 8

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

Answer 9

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.

Answer 10

Charcoal, 25 21 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.

Answer 11

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`)

Answer 12

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

Answer 13

Java, 76 bytes

s->{for(;s!=(s=s.replaceAll("rrrr|ss","").replace("sr","rrrs")););return s;}

Try it online!

Answer 14

Red, 82 bytes

func[s][while[parse s[some thru[remove["rrrr"|"ss"]| change"sr""rrrs"]to end]][]s]

Try it online!

Answer 15

Bash with sed, ⁸⁶ 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!

Answer 16

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]]
              ƒ    -   start with X and reduce using:
             ƭ     -     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]

Answer 17

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.

Answer 18

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!

Answer 19

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!

Answer 20

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.

Answer 21

sed 4.2.2, 26

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

Try it online!

Answer 22

///, 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.

Answer 23

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?

Answer 24

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
         Copyright 1997-2020 SRI International
           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.

Answer 25

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.