22
\$\begingroup\$

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;
}
\$\endgroup\$
12
  • 1
    \$\begingroup\$ Can I/O be taken using different characters? \$\endgroup\$ – Makonede May 27 at 22:42
  • 1
    \$\begingroup\$ Surprisingly no one asked about different characters on "ijk". I think it is okay, I will add that. \$\endgroup\$ – Hood May 27 at 22:52
  • 1
    \$\begingroup\$ Can we use 1/0 for r and s? \$\endgroup\$ – caird coinheringaahing May 27 at 22:54
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Hood May 27 at 22:56
  • 2
    \$\begingroup\$ Can I use an output format that is different from the input format? \$\endgroup\$ – Bubbler May 28 at 4:41

25 Answers 25

14
\$\begingroup\$

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Ṛḅ- is a-b+c-..., not that it saves any bytes. \$\endgroup\$ – Jonathan Allan May 28 at 4:04
8
\$\begingroup\$

perl -p, 32 bytes

while(s/rrrr|ss//||s/sr/rrrs/){}

Takes advantage of substitution returning truthy iff anything was substituted.

\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
2
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ – dingledooper May 28 at 4:19
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – xnor May 28 at 21:46
6
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

05AB1E, 16 14 13 12 bytes

-3 thanks to ovs.

Δ¾4×KT₄R:11K

Try it online! Beats all other answers. Uses 0 for r and 1 for s.

Δ¾4×KT₄R:11K  # full program
Δ             # while top of stack changes:
    K         # remove all instances of...
 ¾            # variable (predefined to 0)...
   ×          # repeated...
  4           # literal...
   ×          # times...
    K         # from...
              # implicit input...
              # (implicit) or top of stack if not first iteration
        :     # infinitely replace all instancces of...
     T        # 10...
        :     # in top of stack with...
      ₄       # 1000...
       R      # reversed
           K  # remove all instances of...
         11   # literal...
           K  # from top of stack
              # (implicit) end until same
              # implicit output

¾4× can also be 00º and 11 can be with no change in functionality: Try it online!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ õ: can be replaced by K, which puts this back in the lead ;) \$\endgroup\$ – ovs May 27 at 23:21
  • \$\begingroup\$ @ovs Thank you! \$\endgroup\$ – Makonede May 27 at 23:22
  • 1
    \$\begingroup\$ 8b is the same as (1000). \$\endgroup\$ – ovs May 28 at 14:00
  • \$\begingroup\$ @ovs Oh my god how could I forget xD \$\endgroup\$ – Makonede May 28 at 15:52
5
\$\begingroup\$

J, 29 27 bytes

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

Try it online!

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

Retina 0.8.2, 18 bytes

{`rrrr|ss

sr
rrrs

Try it online! Straightforward port of the reference implementation.

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 2tri@ strikes again :) \$\endgroup\$ – Bubbler May 28 at 0:37
  • 1
    \$\begingroup\$ @Bubbler Thanks! And here I thought I had found a legitimate use of ALIAS:! \$\endgroup\$ – chunes May 28 at 0:47
4
\$\begingroup\$

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:

W№θsr≔⪫⪪θsr¦rsssθ⁻⁻θ×r⁴ss

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

W№θ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:

≔⁰θFS¿Σι≦⁻³θ≦⁺²θ§⪪”)∨'✂/O;”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.

FS

Loop over the input.

¿Σι

If the digit is nonzero, ...

≦⁻³θ

... then subtract the integer from 3, ...

≦⁺²θ

... otherwise add 2 to it.

§⪪”)∨'✂/O;”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:

≔⁰θ≔⁰ηFS¿Σι≦¬θ≦⁺⊕⊗θη×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.

FS

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.

\$\endgroup\$
4
\$\begingroup\$

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`)
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

Java, 76 bytes

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

Try it online!

\$\endgroup\$
0
3
\$\begingroup\$

Red, 82 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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!

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

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]
\$\endgroup\$
3
\$\begingroup\$

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.

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

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!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

sed 4.2.2, 26

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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?

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.