title: Is my barcode valid?

text:
# Question
Title: Is my barcode valid?
An EAN-8 barcode includes 7 digits of information and an 8th checksum digit.

The checksum is calculated by multiplying the digits by 3 and 1 alternately, adding the results, and subtracting from the next multiple of 10.

For example, given the digits `2103498`:

```
Digit:        2   1   0   3   4   9   8
Multiplier:   3   1   3   1   3   1   3
Result:       6   1   0   3  12   9  24

```

The sum of these resulting digits is **55**, so the checksum digit is **60 - 55 = 5**

---

# The Challenge

Your task is to, given an 8 digit barcode, verify if it is valid - returning a truthy value if the checksum is valid, and falsy otherwise.

* You may take input in any of the following forms:
    + A string, 8 characters in length, representing the barcode digits
    + A list of 8 integers, the barcode's digits
    + A non-negative integer (you can either assume leading zeroes where none are given, i.e. `1` = `00000001`, or request input with the zeroes given)
* Builtins that compute the EAN-8 checksum (i.e, take the first 7 digits and calculate the last) are banned.
* This is , so the shortest program (in bytes) wins!

---

# Test Cases

```
20378240 -> True
33765129 -> True
77234575 -> True
00000000 -> True

21034984 -> False
69165430 -> False
11965421 -> False
12345678 -> False

```

# Answer
> 5 votes
# Jelly, 7 bytes

```
s2Sḅ3⁵ḍ

```

Try it online!

### How it works

```
s2Sḅ3⁵ḍ  Main link. Argument: [a,b,c,d,e,f,g,h] (digit array)

s2       Split into chunks of length 2, yielding [[a,b], [c,d], [e,f], [g,h]].
  S      Take the sum of the pairs, yielding [a+c+e+g, b+d+f+h].
   ḅ3    Convert from ternary to integer, yielding 3(a+c+e+g) + (b+d+f+h).
     ⁵ḍ  Test if the result is divisible by 10.

```

# Answer
> 13 votes
# JavaScript (ES6), ~~41~~ ~~40~~ 38 bytes

*Saved 2 bytes thanks to @ETHProductions and 1 byte thanks to @Craig Ayre.*

```
s=>s.map(e=>t+=e*(i^=2),t=i=1)|t%10==1

```

Takes input as a list of digits.

Determines the sum of all digits, including the checksum.

If the sum is a multiple of 10, then it's a valid barcode.

**Test Cases**

```
let f=

s=>s.map(e=>t+=e*(i^=2),t=i=1)|t%10==1

console.log(f([2,0,3,7,8,2,4,0]));
console.log(f([3,3,7,6,5,1,2,9]));
console.log(f([7,7,2,3,4,5,7,5]));
console.log(f([0,0,0,0,0,0,0,0]));

console.log(f([2,1,0,3,4,9,8,4]));
console.log(f([6,9,1,6,5,4,3,0]));
console.log(f([1,1,9,6,5,4,2,1]));
console.log(f([1,2,3,4,5,6,7,8]));
```

# Answer
> 10 votes
# Python 2, 64 48 35 29 bytes

mypetlion saved 19 bytes

```
lambda x:sum(x[::2]*2+x)%10<1

```

Try it online!

# Answer
> 8 votes
# Jelly, 8 bytes

```
m2Ḥ+µS⁵ḍ

```

**Try the test suite.**

# Jelly, 9 bytes

```
JḂḤ‘×µS⁵ḍ

```

**Try it online** or **Try the test suite.**

## How this works

```
m2Ḥ+µS⁵ḍ ~ Full program.

m2       ~ Modular 2. Return every second element of the input.
  Ḥ      ~ Double each.
   +µ    ~ Append the input and start a new monadic chain.
     S   ~ Sum.
      ⁵ḍ ~ Is divisible by 10?

```

```
JḂḤ‘×µS⁵ḍ  ~ Full program (monadic).

J          ~ 1-indexed length range.
 Ḃ         ~ Bit; Modulo each number in the range above by 2.
  Ḥ        ~ Double each.
   ‘       ~ Increment each.
    ×      ~ Pairwise multiplication with the input.
     µ     ~ Starts a new monadic chain.
      S    ~ Sum.
       ⁵ḍ  ~ Is the sum divisible by 10?

```

The result for the first 7 digits of the barcode and the checksum digit **must** add to a multiple of **10** for it to be valid. Thus, the checksum is valid iff the algorithm applied to the *whole* list is divisible by **10**.

# Answer
> 7 votes
# MATL, 10 bytes

*Thanks to @Zgarb for pointing out a mistake, now corrected.*

```
IlhY"s10\~

```

Try it online! Or verify all test cases.

### Explanation

```
Ilh     % Push [1 3]
Y"      % Implicit input. Run-length decoding. For each entry in the
        % first input, this produces as many copies as indicated by
        % the corresponding entry of the second input. Entries of
        % the second input are reused cyclically
s       % Sum of array
10\     % Modulo 10
~       % Logical negate. Implicit display

```

# Answer
> 7 votes
# Befunge-98 (PyFunge), ~~16~~ 14 bytes

Saved 2 bytes by skipping the second part using `j` instead of `;`s, as well as swapping a `~` and `+` in the first part to get rid of a `+` in the second.

```
~3*+~+6jq!%a+2

```

Input is in 8 digits (with leading 0s if applicable) and nothing else.

Outputs via exit code (open the debug dropdown on TIO), where 1 is true and 0 is false.

Try it online!

## Explanation

This program uses a variety of tricks.

First of all, it takes the digits in one by one through their ASCII values. Normally, this would require subtracting 48 from each value as we read it from the input. However, if we don't modify it, we are left with 16 (3+1+3+1+3+1+3+1) extra copies of 48 in our sum, meaning our total is going to be 768 greater than what it "should" be. Since we are only concerned with the sum mod 10, we can just add 2 to the sum later. Thus, we can take in raw ASCII values, saving 6 bytes or so.

Secondly, this code only checks if every other character is an EOF, because the input is guaranteed to be only 8 characters long.

~~Thirdly, the `#` at the end of the line doesn't skip the first character, but will skip the `;` if coming from the other direction. This is better than putting a `#;` at the front instead.~~

Because the second part of our program is only run once, we don't have to set it up so that it would skip the first half when running backwards. This lets us use the jump command to jump over the second half, as we exit before executing it going backwards.

### Step by step

Note: "Odd" and "Even" characters are based on a 0-indexed system. The first character is an even one, with index 0.

```
~3*+~+      Main loop - sum the digits (with multiplication)
~           If we've reached EOF, reverse; otherwise take char input. This will always
                be evenly indexed values, as we take in 2 characters every loop.
 3*+        Multiply the even character by 3 and add it to the sum.
    ~       Then, take an odd digit - we don't have to worry about EOF because
                the input is always 8 characters.
     +      And add it to the sum.
      6j    Jump over the second part - We only want to run it going backwards.

        q!%a+2    The aftermath (get it? after-MATH?)
            +2    Add 2 to the sum to make up for the offset due to reading ASCII
          %a      Mods the result by 10 - only 0 if the bar code is valid
         !        Logical not the result, turning 0s into 1s and anything else into 0s
        q         Prints the top via exit code and exits

```

# Answer
> 6 votes
# C,  ~~78~~  77 bytes

```
i,s,c,d=10;f(b){for(i=s=0,c=b%d;b/=d;)s+=b%d*(3-i++%2*2);return(d-s%d)%d==c;}

```

Try it online!

# C (gcc), 72 bytes

```
i,s,c,d=10;f(b){for(i=s=0,c=b%d;b/=d;)s+=b%d*(i++%2?:3);b=(d-s%d)%d==c;}

```

Try it online!

# Answer
> 6 votes
# Wolfram Language (Mathematica), ~~26~~ 21 bytes

```
10∣(2-9^Range@8).#&

```

Try it online!

Takes input as a list of 8 digits.

## How it works

`2-9^Range@8` is congruent modulo 10 to `2-(-1)^Range@8`, which is `{3,1,3,1,3,1,3,1}`. We take the dot product of this list with the input, and check if the result is divisible by 10.

# Wolfram Language (Mathematica), 33 bytes and non-competing

```
Check[#~BarcodeImage~"EAN8";1,0]&

```

Try it online!

Takes input as a string. Returns `1` for valid barcodes and `0` for invalid ones.

## How it works

The best thing I could find in the way of a built-in (since Mathematica is all about those).

The inside bit, `#~BarcodeImage~"EAN8";1`, generates an image of the EAN8 barcode, then ignores it entirely and evaluates to 1. However, if the barcode is invalid, then `BarcodeImage` generates a warning, which `Check` catches, returning 0 in that case.

# Answer
> 5 votes
# Haskell, 40 38 bytes

```
a=3:1:a
f x=mod(sum$zipWith(*)a x)10<1

```

Try it online!

Takes input as a list of 8 integers. A practical example of using infinite lists.

Edit: Saved 2 bytes thanks to GolfWolf

# Answer
> 5 votes
# Java 8, ~~58~~ ~~56~~ 55 bytes

```
a->{int r=0,m=1;for(int i:a)r+=(m^=2)*i;return r%10<1;}

```

-2 bytes indirectly thanks to *@RickHitchcock*, by using `(m=4-m)*i` instead of `m++%2*2*i+i` after seeing it in his JavaScript answer.
-1 byte indirectly thanks to *@ETHProductions* (and *@RickHitchcock*), by using `(m^=2)*i` instead of `(m=4-m)*i`.

**Explanation:**

Try it here.

```
a->{              // Method with integer-array parameter and boolean return-type
  int r=0,        //  Result-sum
      m=1;        //  Multiplier
  for(int i:a)    //  Loop over the input-array
    r+=           //   Add to the result-sum:
       (m^=2)     //    Either 3 or 1,
       *i;        //    multiplied by the digit
                  //  End of loop (implicit / single-line body)
  return r%10<1;  //  Return if the trailing digit is a 0
}                 // End of method

```

# Answer
> 4 votes
# 05AB1E, 14 bytes

```
θ¹¨3X‚7∍*O(T%Q

```

Try it online!

Needs leading `0`s, takes list of digits.

# Answer
> 4 votes
# Pyth, 8 bytes

```
!es+*2%2

```

**Verify all the test cases!**

# Pyth, 13 bytes

If we can assume the input always has exactly 8 digits:

```
!es.e*bhy%hk2

```

**Verify all the test cases!**

---

# How does this work?

```
!es+*2%2 ~ Full program.

      %2 ~ Input[::2]. Every second element of the input.
    *2   ~ Double (repeat list twice).
   +     ~ Append the input.
  s      ~ Sum.
 e       ~ Last digit.
!        ~ Logical NOT.

```

```
!es.e*sbhy%hk2 ~ Full program.

               ~ Convert the input to a String.
   .e          ~ Enumerated map, storing the current value in b and the index in k.
          %hk2 ~ Inverted parity of the index. (k + 1) % 2.
        hy     ~ Double, increment. This maps odd integers to 1 and even ones to 3.
      b        ~ The current digit.
     *         ~ Multiply.
  s            ~ Sum.
 e             ~ Last digit.
!              ~ Logical negation.

```

If the sum of the first 7 digit after being applied the algorithm is subtracted from **10** and then compared to the last digit, this is equivalent to checking whether the sum of all the digits, after the algorithm is applied is a multiple of **10**.

# Answer
> 4 votes
# Retina, ~~23~~ 22 bytes

*-1 byte thanks to Martin Ender!*

```
(.).
$1$1$&
.
$*
M`
1$

```

Try it online!

### Explanation

Example input: `20378240`

```
(.).
$1$1$&

```

Replace each couple of digits with the first digit repeated twice followed by the couple itself. We get `2220333788824440`

```
.
$*

```

Convert each digit to unary. With parentheses added for clarity, we get `(11)(11)(11)()(111)(111)...`

```
M`

```

Count the number of matches of the empty string, which is one more than the number of ones in the string. (With the last two steps we have basically taken the sum of each digit +1) Result: `60`

```
1$

```

Match a `1` at the end of the string. We have multiplied digits by 3 and 1 alternately and summed them, for a valid barcode this should be divisible by 10 (last digit 0); but we also added 1 in the last step, so we want the last digit to be 1. Final result: `1`.

# Answer
> 3 votes
# Jelly, 16 bytes

```
ż3,1ṁ$P€SN%⁵
Ṫ=Ç

```

Try it online!

takes input as a list of digits

# Answer
> 3 votes
# PowerShell, 85 bytes

```
param($a)(10-(("$a"[0..6]|%{+"$_"*(3,1)[$i++%2]})-join'+'|iex)%10)%10-eq+"$("$a"[7])"

```

Try it online! or Verify all test cases

Implements the algorithm as defined. Takes input `$a`, pulls out each digit with `"$a"[0..6]` and loops through them with `|%{...}`. Each iteration, we take the digit, cast it as a string `"$_"` then cast it as an int `+` before multiplying it by either `3` or `1` (chosen by incrementing `$i` modulo `2`).

Those results are all gathered together and summed `-join'+'|iex`. We take that result mod `10`, subtract that from `10`, and again take the result mod `10` (this second mod is necessary to account for the `00000000` test case). We then check whether that's `-eq`ual to the last digit. That Boolean result is left on the pipeline and output is implicit.

# Answer
> 3 votes
# J, 17 bytes

*-10 bytes thanks to cole*

```
0=10|1#.(8$3 1)*]

```

Try it online!

This uses multiplication of equal sized lists to avoid the zip/multiply combo of the original solution, as well as the "base 1 trick" `1#.` to add the products together. The high level approach is similar to the original explanation.

## original, 27 bytes

```
0=10|{:+[:+/[:*/(7$3 1),:}:

```

Try it online!

## explained

```
0 =                                        is 0 equal to...
    10 |                                   the remainder when 10 divides...
         {: +                              the last input item plus...
              [: +/                        the sum of...
                    [: */                  the pairwise product of...
                          7$(3 1) ,:       3 1 3 1 3 1 3 zipped with...
                                     }:    all but the last item of the input

```

# Answer
> 3 votes
# C (gcc), ~~84~~ ~~82~~ ~~72~~ ~~61~~ 54 bytes

```
c;i;f(x){for(i=c=0;x;x/=10)c+=(1+2*i++%4)*x;c=c%10<1;}

```

-21 bytes from Neil

-7 bytes from Nahuel Fouilleul

Try it online!

Developed independently of Steadybox's answer

'f' is a function that takes the barcode as an `int`, and returns `1` for True and `0` for False.

* `f` stores the last digit of `x` in `s` (`s=x%10`),
* Then calculates the sum in `c` (`for(i=c=0;x;x/=10)c+=(1+2*i++%4)*x;`)

+ `c` is the sum, `i` is a counter
    + for each digit including the first, add `1+2*i%4` times the digit (`x%10`) to the checksum and increment `i` (the `i++` in `3-2*i++%4`)

    - `1+2*i%4` is 1 when `i` is even and 0 when `i` is odd
* Then returns whether the sum is a multiple of ten, and since we added the last digit (multiplied by 1), the sum will be a multiple of ten iff the barcode is valid. (uses GCC-dependent undefined behavior to omit `return`).

# Answer
> 3 votes
# APL (Dyalog), 14 bytes

Equivalent with streetster's solution.

Full program body. Prompts for list of numbers from STDIN.

```
0=10|+/⎕×8⍴3 1

```

Try it online!

***Is…***

`0=` zero equal to

`10|` the mod-10 of

`+/` the sum of

`⎕×` the input times

`8⍴3 1` eight elements cyclically taken from `[3,1]`

***?***

# Answer
> 3 votes
# 05AB1E, 9 bytes

```
3X‚7∍*OTÖ

```

Try it online!

```
3X‚7∍*OTÖ    # Argument a
3X‚          # Push [3, 1]
   7∍        # Extend to length 7
     *       # Multiply elements with elements at same index in a
      O      # Total sum
       TÖ    # Divisible by 10

```

# Answer
> 3 votes
# C, 63 bytes

```
i;s=0;c(int*v){for(i=0;i<8;i++){s+=v[i]*3+v[++i];}return s%10;}

```

Assumes that `0` is `true` and any other value is `false`.

## +3 bytes for better return value

```
i;s=0;c(int*v){for(i=0;i<8;i++){s+=v[i]*3+v[++i];}return s%10==0;}

```

Add `==0` to the `return` statement.

## Ungolfed

```
int check(int* values)
{
    int result = 0;
    for (int index = 0; index < 8; index++)
    {
        result += v[i] * 3 + v[++i]; // adds this digit times 3 plus the next digit times 1 to the result
    }
    return result % 10 == 0; // returns true if the result is a multiple of 10
}

```

This uses the alternative definition of EAN checksums where the check digit is chosen such that the checksum of the entire barcode including the check digit is a multiple of 10. Mathematically this works out the same but it's a lot simpler to write.

## Initialising variables inside loop as suggested by Steadybox, 63 bytes

```
i;s;c(int*v){for(i=s=0;i<8;i++){s+=v[i]*3+v[++i];}return s%10;}

```

## Removing curly brackets as suggested by Steadybox, 61 bytes

```
i;s;c(int*v){for(i=s=0;i<8;i++)s+=v[i]*3+v[++i];return s%10;}

```

## Using `<1` rather than `==0` for better return value as suggested by Kevin Cruijssen

```
i;s=0;c(int*v){for(i=0;i<8;i++){s+=v[i]*3+v[++i];}return s%10<1;}

```

Add `<1` to the `return` statement, this adds only 2 bytes rather than adding `==0` which adds 3 bytes.

# Answer
> 2 votes
# JavaScript (Node.js), 47 bytes

```
e=>eval(e.map((a,i)=>(3-i%2*2)*a).join`+`)%10<1

```

Although there is a much shorter answer already, this is my first attempt of golfing in JavaScript so I'd like to hear golfing recommendations :-)

### Testing

```
let f=

e=>eval(e.map((a,i)=>(3-i%2*2)*a).join`+`)%10<1

console.log(f([2,0,3,7,8,2,4,0]));
console.log(f([3,3,7,6,5,1,2,9]));
console.log(f([7,7,2,3,4,5,7,5]));
console.log(f([0,0,0,0,0,0,0,0]));

console.log(f([2,1,0,3,4,9,8,4]));
console.log(f([6,9,1,6,5,4,3,0]));
console.log(f([1,1,9,6,5,4,2,1]));
console.log(f([1,2,3,4,5,6,7,8]));
```

Alternatively, you can **Try it online!**

# Answer
> 2 votes
# K (oK), ~~16~~ 15 bytes

**Solution:**

```
{~10!+/x*8#3 1}

```

Try it online!

**Examples:**

```
{~10!+/x*8#3 1}2 1 0 3 4 9 8 5
1
{~10!+/x*8#3 1}2 1 0 3 4 9 8 4
0
{~10!+/x*8#3 1}2 0 3 7 8 2 4 0
1

```

**Explanation:**

K is interpreted right-to-left:

```
{~10!+/x*8#3 1} / the solution
{             } / lambda with x as implicit input
           3 1  / the list [3,1]
         8#     / 8 take this list = [3,1,3,1,3,1,3,1]
       x*       / multiply input by this
     +/         / sum over the list
  10!           / 10 mod this sum
 ~              / not, 0 => 1, anything else => 0

```

# Answer
> 2 votes
# Perl 5, ~~37~~ 32 + 1 (-p) bytes

```
s/./$-+=$&*(--$|*2+1)/ge;$_=/0$/

```

-5 bytes thanks to Dom Hastings. 37 +1 bytes was

```
$s+=$_*(++$i%2*2+1)for/./g;$_=!!$s%10

```

try it online

# Answer
> 2 votes
# Brainfuck, 228 Bytes

```
>>>>++++[<++>-]<[[>],>>++++++[<++++++++>-]<--[<->-]+[<]>-]>[->]<<<<[[<+>->+<]<[>+>+<<-]>>[<+>-]<<<<<]>>>>[>>[<<[>>+<<-]]>>]<<<++++[<---->-]+++++[<++<+++>>-]<<[<[>>[<<->>-]]>[>>]++[<+++++>-]<<-]<[[+]-<]<++++++[>++[>++++<-]<-]>>+.

```

Can probably be improved a fair bit. Input is taken 1 digit at a time, outputs 1 for true, 0 for false.

## How it works:

```
>>>>++++[<++>-]<

```

Put 8 at position 3.

```
[[>],>>++++++[<++++++++>-]<--[<->-]+[<]>-]

```

Takes input 8 times, changing it from the ascii value to the actual value +2 each time. Inputs are spaced out by ones, which will be removed, to allow for easier multiplication later.

```
>[->]

```

Subtract one from each item. Our tape now looks something like

```
0 0 0 0 4 0 4 0 8 0 7 0 6 0 2 0 3 0 10 0 0
                                         ^

```

With each value 1 more than it should be. This is because zeros will mess up our multiplication process.

Now we're ready to start multiplying.

```
<<<<

```

Go to the second to last item.

```
[[<+>->+<]<[>+>+<<-]>>[<+>-]<<<<<]

```

While zero, multiply the item it's at by three, then move two items to the left. Now we've multiplied everything we needed to by three, and we're at the very first position on the tape.

```
>>>>[>>[<<[>>+<<-]]>>]

```

Sum the entire list.

```
<<<++++[<---->-]

```

The value we have is 16 more than the actual value. Fix this by subtracting 16.

```
+++++[<++<+++>>-]

```

We need to test whether the sum is a multiple of 10. The maximum sum is with all 9s, which is 144. Since no sum will be greater than 10\*15, put 15 and 10 on the tape, in that order and right to the right of the sum.

```
<<[<[>>[<<->>-]]>[>>]++[<+++++>-]<<-]

```

Move to where 15 is. While it's non-zero, test if the sum is non-zero. If it is, subtract 10 from it. Now we're either on the (empty) sum position, or on the (also empty) ten position. Move one right. If we were on the sum position, we're now on the non-zero 15 position. If so, move right twice. Now we're in the same position in both cases. Add ten to the ten position, and subtract one from the 15 position.

The rest is for output:

```
<[[+]-<]<++++++[>++[>++++<-]<-]>>+.

```

Move to the sum position. If it is non-zero (negative), the barcode is invalid; set the position to -1. Now add 49 to get the correct ascii value: 1 if it's valid, 0 if it's invalid.

# Answer
> 2 votes
# Java 8, 53 bytes

Golfed:

```
b->(3*(b[0]+b[2]+b[4]+b[6])+b[1]+b[3]+b[5]+b[7])%10<1

```

Direct calculation in the lambda appears to the shortest solution. It fits in a single expression, minimizing the lambda overhead and removing extraneous variable declarations and semicolons.

```
public class IsMyBarcodeValid {

  public static void main(String[] args) {
    int[][] barcodes = new int[][] { //
        { 2, 0, 3, 7, 8, 2, 4, 0 }, //
        { 3, 3, 7, 6, 5, 1, 2, 9 }, //
        { 7, 7, 2, 3, 4, 5, 7, 5 }, //
        { 0, 0, 0, 0, 0, 0, 0, 0 }, //
        { 2, 1, 0, 3, 4, 9, 8, 4 }, //
        { 6, 9, 1, 6, 5, 4, 3, 0 }, //
        { 1, 1, 9, 6, 5, 4, 2, 1 }, //
        { 1, 2, 3, 4, 5, 6, 7, 8 } };
    for (int[] barcode : barcodes) {
      boolean result = f(b -> (3 * (b[0] + b[2] + b[4] + b[6]) + b[1] + b[3] + b[5] + b[7]) % 10 < 1, barcode);
      System.out.println(java.util.Arrays.toString(barcode) + " = " + result);
    }
  }

  private static boolean f(java.util.function.Function<int[], Boolean> f, int[] n) {
    return f.apply(n);
  }
}

```

Output:

```
[2, 0, 3, 7, 8, 2, 4, 0] = true
[3, 3, 7, 6, 5, 1, 2, 9] = true
[7, 7, 2, 3, 4, 5, 7, 5] = true
[0, 0, 0, 0, 0, 0, 0, 0] = true
[2, 1, 0, 3, 4, 9, 8, 4] = false
[6, 9, 1, 6, 5, 4, 3, 0] = false
[1, 1, 9, 6, 5, 4, 2, 1] = false
[1, 2, 3, 4, 5, 6, 7, 8] = false

```

# Answer
> 2 votes
# C# (.NET Core), 65 62 bytes

```
b=>{int s=0,i=0,t=1;while(i<8)s+=b[i++]*(t^=2);return s%10<1;}

```

Try it online!

### Acknowledgements

-3 bytes thanks to @KevinCruijssen and the neat trick using the exclusive-or operator.

### DeGolfed

```
b=>{
    int s=0,i=0,t=1;

    while(i<8)
        s+=b[i++]*(t^=2); // exclusive-or operator alternates t between 3 and 1.

    return s%10<1;
}

```

# C# (.NET Core), 53 bytes

```
b=>(3*(b[0]+b[2]+b[4]+b[6])+b[1]+b[3]+b[5]+b[7])%10<1

```

Try it online!

A direct port of @Snowman's answer.

# Answer
> 2 votes
# QBasic, ~~54~~ 52 bytes

Ugh, the boring answer turned out to be the shortest:

```
INPUT a,b,c,d,e,f,g,h
?(3*a+b+3*c+d+3*e+f+3*g+h)MOD 10=0

```

This inputs the digits comma-separated. My original 54-byte solution, which inputs one digit at a time, uses a "nicer" approach:

```
m=3
FOR i=1TO 8
INPUT d
s=s+d*m
m=4-m
NEXT
?s MOD 10=0

```

# Answer
> 2 votes
# Vyxal, 8 bytes

```
y$3*J∑₀Ḋ

```

Try it Online!

```
y        # Uninterleave
 $       # Swap
  3*     # Multiply by 3 (vectorised)
    J    # Join
     ∑   # Sum
      ₀Ḋ # Is divisible by 10?

```

# Answer
> 1 votes
# Ruby, 41 Bytes

Takes an array of integers. -6 bytes thanks to Jordan.

```
->n{n.zip([3,1]*4){|x,y|$.+=x*y};$.%10<1}

```

# Answer
> 1 votes
# MATLAB/Octave, 32 bytes

```
@(x)~mod(sum([2*x(1:2:7),x]),10)

```

Try it online!

I'm going to post this despite the other Octave answer as I developed this code and approach without looking at the other answers.

Here we have an anonymous function which takes the input as an array of 8 values, and return true if a valid barcode, false otherwise..

The result is calculated as follows.

```
              2*x(1:2:7)
             [          ,x]
         sum(              )
     mod(                   ,10)
@(x)~

```
1. Odd digits (one indexed) are multiplied by 2.
2. The result is prepended to the input array, giving an array whose sum will contain the odd digits three times, and the even digits once.
3. We do the sum which will also include the supplied checksum within our sum.
4. Next the modulo 10 is performed. If the checksum supplied was valid, the sum of all multiplied digits including the checksum value would end up being a multiple of 10. Therefore only a valid barcode would return 0.
5. The result is inverted to get a logical output of true if valid.

# Answer
> 1 votes
# Japt, ~~12~~ 11 bytes

Takes input as an array of digits, outputs `1` or `0`.

```
xÈ*31sgYÃvA

```

Try it

# Answer
> 1 votes
# Excel, 37 bytes

Interpreting "A list of 8 integers" as allowing 8 separate cells in Excel:

```
=MOD(SUM(A1:H1)+2*(A1+C1+E1+G1),10)=0

```

# Answer
> 1 votes
# TI-Basic (83 series), 18 bytes

```
not(fPart(.1sum(2Ans-Ans9^cumSum(binomcdf(7,0

```

Takes input as a list in `Ans`. Returns `1` for valid barcodes and `0` for invalid ones.

A port of my Mathematica answer. Includes screenshot, in lieu of an online testing environment:

Notable feature: `binomcdf(7,0` is used to generate the list `{1,1,1,1,1,1,1,1}` (the list of probabilities that from 7 trials with success probability 0, there will be at most N successes, for N=0,1,...,7). Then, `cumSum(` turns this into `{1,2,3,4,5,6,7,8}`.

This is one byte shorter than using the `seq(` command, though historically the point was that it's also significantly faster.

# Answer
> 1 votes
# \>\<\>, ~~89~~ 84 Bytes

```
8>i$1\
/\?:-/
\8+  \
/1-:?v~r3*+\
\ } \$>3*+v<
/++-/f}   l
\+3ff/\?-4/
/a+++/
\%0=n;

```

Can ~~probably~~ certainly be improved (this is my second \>\<\> program)

## How it works:

```
8>i$1\
 \?:-/

```

Gets user input, 8 times. Note that since i pushes -1 if the input stack is empty, this may not always return false for inputs shorter than 8 digits.

```
/
\8+  \
/1-:?v
\ } \$
/++-/f
\+3ff/

```

Converts the ascii values to their actual values.

```
      ~r3*+\
      >3*+v<
      }   l
      \?-4/

```

Remove the counter, and reverse the stack. Then, while the stack is longer than 4, multiply the top value by three, add it to the digit below it, and move the result to the bottom of the stack.

```
     /
/a+++/
\%0=n;

```

Sum the values on the stack. If the answer is divisible by 10, the code is valid. If so, print 1, otherwise, 0.

# Answer
> 1 votes
# Julia 29 bytes

```
~x=[3,1,3,1,3,1,3,1]⋅x%10<1

```

golfing away that long literal array would be nice.

⋅ is a 3 byte character. But it is shorter than calling `dot(...,x)`. and shorter that anything that handles everything as arrays and then grabs the only element.

# Answer
> 1 votes
# *Acc!!*, ~~60~~ 45 bytes

```
3*N+N+3*N+N+3*N+N+3*N+N-8
Write 1/(1+_%10)+48

```

Try it online!

### Explanation

We read eight digits, multiplying the appropriate ones by 3, and add. It's not quite that simple, because what we're actually reading is ASCII codes, and so each digit has 48 added to it. Thus, the resulting sum is too big by 3\*48\*4 + 48\*4 = 768. We only care about the 1's digit, so subtracting 8 is sufficient to get the correct result.

We want to print `1` if the accumulator mod 10 is 0, and `0` otherwise. *Acc!!* doesn't have comparison operators, so we have to use integer division:

```
_%10        0  1  9
1+_%10      1  2  10
1/(1+_%10)  1  0  0

```

Then we add 48 to get an ASCII value and `Write` it.

---

Original 60-byte solution with a loop:

```
Count i while 8-i {
_+(N-48)*(3-i%2*2)
}
Write 1/(1+_%10)+48

```

# Answer
> 1 votes
# C 98, 118 bytes

Ive edited this now to instead of echoing F or T it will return 0 or 1 to the pipe.

```
int i,j,k;int main(int,char**v){for(;i<7;(j+=(v[1][i]-48)*(i++%2?1:3)));for(;(k+=10)<j;);return v[1][7]-48==(k-j)%10;}

```

usage:

```
./a.out XXXXXXXX

```

where XXXXXXXX is a zero padded string, it will return either a 0 or a 1 as an exit code

this is 118 chars long in total. and the the compiled program is

```
   text    data     bss     dec     hex filename
   1307     544      16    1867     74b a.out

```

# Answer
> 1 votes
# Husk, 10 bytes

```
¬→dB3mΣTC2

```

Try it online!

# Husk, 10 bytes

```
¦10B3mΣTC2

```

Try it online!

# Answer
> 1 votes
# Perl 6, 23 bytes

```
{:1[$_ «*»(3,1)]%%10}

```

Try it online!

Takes a list of digits.

# Answer
> 1 votes
# Ruby, 37 bytes

```
->n{(n+n.scan(/.(.)/)*''*2).sum%10<1}

```

Try it online!

# Answer
> 0 votes
## Batch, 88 bytes

```
@set/as=0,n=%1
@for %%i in (1 2 3 4)do @set/as+=n+n/10*3,n/=100
@if %s:~-1%==0 echo 1

```

N.B. Leading zeros are not acceptable as they will cause the input to be treated as octal. As the numbers are always 8 digits the loop size can be hardcoded which saves 2 bytes.

# Answer
> 0 votes
# Java (OpenJDK 8), ~~104~~ 99 bytes

```
s->{int y=0,i=0;for(;i<7;y+=(3-i%2*2)*(s.charAt(i++)-48));return 58-(y%10<1?10:y%10)==s.charAt(7);}

```

Try it online!

# Answer
> 0 votes
# Pyke, ~~14~~ ~~13~~ ~~12~~ 9 bytes

```
2%2*+sT%!

```

Try it here!

```
2%        -      input[::2]
  2*      -     ^ * 2
    +     -    input + ^
     s    -   sum(^)
      T%  -  ^ % 10
        ! - not ^

```

Thanks Mr. Xcoder for saving 3 bytes!

# Answer
> 0 votes
# Octave, 40 bytes

```
@(a)9-mod(a*("31313130"'-48)-1,10)==a(8)

```

Accepts an array of integers as input and returns true/false.

Try it online!

# Answer
> 0 votes
# QBIC, 23 bytes

```
[4|_!_!p=p+b*3+c]?p%z=0

```

## Explanation

```
[4|          DO four times
_!           Ask the user for a digit, save as 'b' ('a' is taken by [4| )
_!           Ask the user for a digit, save as 'c'
p=p          Add to running total p
+b*3         the first digit times 3
+c           and the second digit
]            NEXT
?p%z=0       PRINT -1 if the seven digits + checksum MOD 10 == 0

```

# Answer
> 0 votes
# Perl 5, 54 + 1 (`-F`) = 55bytes

```
$r=pop@F;map$s+=$_*(($.+=2)%4),@F;say$r==(10-$s%10)%10

```

Try it online!

# Answer
> 0 votes
# PHP, 82 bytes

```
<?for(;$i<strlen($p=$argv[1])-1;)$t+=($i%2?1:3)*$p[$i++];echo(10-$t%10)%10==$p[7];

```

Try it online!

Input as a string; prints 1 for valid, nothing for invalid.

# Answer
> 0 votes
## Clojure, 41 bytes

```
#(=(mod(apply +(map *(cycle[3 1])%))10)0)

```

# Answer
> 0 votes
# GolfScript \- ~~54~~ 52 bytes

```
1/[{~}/][):a;[3 1]3*[3]+]zip 0\{{*}*+}/10%10\- 10%a=

```
* Input: `33765129`
* Output: `1`

**If the input is an array the code can be modified to:**

```
~[):a;[3 1]3*[3]+]zip 0\{{*}*+}/10%10\- 10%a=     # 45 bytes

```
* Input: `[3 3 7 6 5 1 2 9]`
* Output: `1`

### Explanation

```
1/[{~}/]     # Parse input
[):a;        # Gets last digit
[3 1]3*[3]+  # Generates the vector [3 1 3 1 3 1 3]
]zip         # Transposes the vector [[input] [3 1s]]
0\{{*}*+}/   # Vector dot product
10%10\- 10%  # (10-ans mod10)mod10
a=           # Compare

```

# Answer
> 0 votes
# C (gcc), ~~54 by pizzapants184~~ 51 bytes

```
c;i;f(x){for(i=3,c=0;x;x/=10)c+=(i^=2)*x;c=c%10<1;}

```

Try it online!

This answer heavily builds upon the answer of pizzapants184, but improves the bytecount by 3. i would have commented, but rep is below 50. The 3 bytes are removed, by replacing `i=0 (...) (1+2*i++%4)` with `i=3 (...) (i^=2)`.

# Answer
> 0 votes
# , ~~45 bytes~~ 42 bytes

```
x=scan();(140-sum(x[-8]*c(3,1)))%%10==x[8]

```

Try it online!

Explanation:

```
140-         #the largest value possible is 135 (all 9's)
sum(
  x[-8]      #drop last value from input vector
     *c(3,1) #multiply by a automatically replicating vector of 3,1
)
  %%10       #modulo 10
== x[8]      #compare to the checksum

```

# Answer
> 0 votes
# GolfScript, 16 bytes

```
0\~{\3*++}4*10%!

```

Try it online!

**Example Input**

```
2 0 3 7 8 2 4 0

```

Output:

```
1

```

**How it Works**

Takes a string of 8 digits separated by spaces. For convenience I have included a header which automatically adds spaces to the input.

```
0\                          - Add zero to stack and place under input
  ~                         - Dump digits in input string onto stack
   {     }4*                - Loop 4 times.
    \                       - Swap top two indices of stack
     3*                     - Multiply by three
       ++                   - Add twice
            10%             - Modulo 10
               !            - Logical(?) not

```

# Answer
> 0 votes
# PHP, 50 bytes

```
while($c++<8)$s+=$argv[$c]*($c&1?3:1);echo$s%10<1;

```

Run with `-nr`, provide digits as separate command line arguments or try it online.

# Answer
> 0 votes
# Z80 Assembly, 22 bytes

```
; INPUT:
;   HL = a memory location storing barcode as a sequence of integers
; OUTPUT:
;   flag Z signals that barcode is valid, NZ signals invalid barcode

CheckBarcode:
        xor a : ld bc,7*256+%10101010       ; B is the number of loop iterations
                                            ; bits of C say when factor 3 is to be used
AddLoop:
        sub (hl) : rl c : jr nc,Times1      ; negative checksum computation
Times3: sub (hl) : sub (hl)
Times1: inc hl : djnz AddLoop

        jr z,Check                          ; the ugly line to deal with 00000000

Rem:    add 10 : jr nc,Rem                  ; add 10s until the answer is non-negative...

Check:  cp (hl) : ret                       ; ...and compare it with 8th digit!

```

This task fits into 8-bit assembly quite well.

# Answer
> 0 votes
# APL (Dyalog Unicode), 36 bytes

```
f←{0=10∣+/⍵+2×+/⍵×8⍴0 1}

```

Try it online!

I just copy and modify (because that formula it seems wrong) the above Excel solution....

# Answer
> 0 votes
# Tcl, 89 bytes

```
proc C L {lmap c $L {incr t [expr [incr i]%8?$i%2?3*$c:$c:0]}
expr [lindex $L 7]==-$t%10}

```

Try it online!

# Answer
> 0 votes
# Tcl, 93 bytes

```
proc C s {expr ([regsub -all (.)(.) [string repl $s 7 7 0] {-3*\1-\2}])%10==[string in $s 7]}

```

Try it online!

**Will golf it more later!**

# Answer
> 0 votes
# Jelly, 17 bytes

```
Ṗµ3,1ṁ×⁸S⁵a%⁵⁼³Ṫ¤

```

Try it online!

Explanation:

```
Ṗµ                 take off the last element
  3,1ṁ             repeat [3, 1] to the same length as the input without the last element
      ×⁸           multiply together
        S          sum
         ⁵a        abs(10 - sum)
           %⁵      mod 10
              ³Ṫ¤  the last element of the original input
             ⁼     are they equal?

```

# Answer
> 0 votes
# 05AB1E, 6 bytes

```
ιO3βTÖ

```

Try it online! Beats all other answers. Takes input as a list of digits with leading zeros.

```
ιO3βTÖ  # full program
     Ö  # is...
        # (implicit) list of...
 O      # sum...
        # (implicit) s...
 O      # of...
        # (implicit) each element of...
   β    # list of base-10 values of base...
  3     # literal...
   β    # digits of...
        # implicit input...
ι       # split into pieces of...
        # (implicit) 2...
ι       # with each digit of each element concatenated with digits in corresponding indices in other elements...
   β    # in decimal...
     Ö  # divisible by...
    T   # 10...
     Ö  # ?
        # implicit output

```

---
Tags: code-golf, arithmetic, decision-problem, integer, checksum
---


title: Quat. Quine + Cat

text:
# Question
Title: Quat. Quine + Cat
A Quat is a combination of a and the popular esolang cat program.

# Challenge

The challenge is to write a standard cat program. Whatever the user inputs, the program will echo the input to stdout.
However, when the length of the input is greater than 0 **and** a multiple of 4, the program should output its own source code. *Quat* comes from the Portuguese quatro, which translates to 'four'.

# Rules

* Standard loopholes apply
* You may not read the source code from a file
* An empty input should produce an empty output

# Bonus

If your input length is a multiple of 4 you can earn a 25% bonus by printing the quine `length/4` times. Another 5% bonus if you seperate the output by spaces (no trailing space allowed).

# Test cases

The following test cases apply for the program `in%4=0?cat:self` (not a real language).

`<empty input> -> <empty output>`
`input -> input`
`1234 -> in%4=0?cat:self`
`12345678 -> in%4=0?cat:self` **0%** bonus
`12345678 -> in%4=0?cat:selfin%4=0?cat:self` **25%** bonus
`12345678 -> in%4=0?cat:self in%4=0?cat:self` **30%** bonus

# Scoring

This is . Shortest code in bytes wins.

# Answer
## CJam, 23 * 0.75 = 17.25 bytes

Standard generalised quine...

```
{`"_~"+q:Q,4md@@*Q\?}_~

```

or

```
{`"_~"+q_,4md@@]:\*?}_~

```

Test it here.

### Explanation

```
{`"_~"+  e# Generalised quine framework. Leaves the source code on the stack.
  q:Q    e# Read input and store it in Q.
  ,      e# Get its length.
  4md    e# Divmod 4.
  @      e# Pull up the source code.
  @      e# Pull up the div.
  *      e# Repeat the source code that many times.
  Q\     e# Push the input and swap it below the repeated source.
  ?      e# Pick the right output based on the modulo.
}_~

```

The other version avoids the use of a variable by using the stack-rotation trick `]:\`.
> 8 votes

# Answer
# Pyth, 33 * .75 = 24.75

```
?%lz4z*/lz4jN*2]"?%lz4z*/lz4jN*2]

```

Test Suite

Standard Pyth quine using join. This is only a true quine on the online interpreter, which doesn't add a final trailing newline.

Getting the final bonus reults in a score of 39 * .7 = 27.3:

```
?%lz4zjd*/lz4]jN*2]"?%lz4zjd*/lz4]jN*2]

```
> 2 votes

# Answer
# Emacs Lisp (323 * 0.75 = 242.25)

```
((lambda (s) (let* ((a (read-string "")) (l (string-bytes a))) (if (> (% l 4) 0) (message a) (dotimes (v (/ l 4)) (prin1 (list s (list (quote quote) s))))))) (quote (lambda (s) (let* ((a (read-string "")) (l (string-bytes a))) (if (> (% l 4) 0) (message a) (dotimes (v (/ l 4)) (prin1 (list s (list (quote quote) s)))))))))

```

This uses Lisp's quoting mechanic to give the source code as input to itself.

**Old cheating version**

```
:; exec emacs -Q -script $0
(find-file(nth 2 command-line-args))(set'b(buffer-string))(set's(read-string""))(set'l(string-bytes s))(if(>(% l 4)0)(message s)(dotimes(v(/ l 4))(message"%s"b)))

```

Ungolfed:

```
:; exec emacs -Q -script $0
(find-file(nth 2 command-line-args)) ; open self
(set'b(buffer-string))               ; read own code to string
(set's(read-string""))               ; read input
(set'l(string-bytes s))              ; length of input
(if(>(% l 4)0)                       ; l % 4 > 0 ?
    (message s)                      ; output input
  (dotimes(v(/ l 4))                 ; (implicit else) repeat l/4 times
    (message"%s"b)))                 ; output own code

```
> 2 votes

# Answer
## Seriously, ~~8~~ 9 bytes

```
Q,ó;l4@%I

```

Try it Online

(Hit enter once in the input box to test empty input.)

The first bonus can be done in 12 bytes (16\*.75):

```
Q,ó;l;4@\(*)4@%I

```

Explanation:

```
Q                   Push program source to stack
 ,ó                 Push input string, and terminate if it's empty
   ;l               Push length of input
     4@%            Take the length mod 4.
        I           Pick the next stack element (input) if nonzero,
                    else the next next (program source)

```

Since some people don't like the use of Seriously's quining built-in, I provide this 22 byte version that doesn't use `Q` for reference:

```
`è";ƒ"(+,ó;l4@%I`;ƒ

```

If you are one of those people, consider this the definitive version (for now) and then go start a meta thread about the use of built-ins in quines.
> 2 votes

# Answer
# Vitsy, ~~18~~ 17 bytes

~~*So close*.~~ Yus. I am now winning amongst non-built in quiners! *glares at Seriously*

```
zl4M([&'rd3*8\}]Z
z                 Grab ALL THE INPUT! :D
 l4M([         ]  If the input is a multiple of four, do the stuff in brackets.
      &           Generate a new stack and move to it.
       'rd3*      Standard quine.
            8\}   Push the bottom 8 items of the stack to the top.
                Z Output the current stack.
```

There's no reason for me to go after the bonuses - they'd chuck on a lot more bytes.

## Cheating quine version, 12 bytes:

```
zl4M([&iG`]Z
zl4M([&   ]Z  Same as above.
       i      Push -1.
        G     Get the name of the file with this index of use (-1 is self)
         `    Read the file with the given name and push its contents to the stack.
```
> 2 votes

# Answer
# Perl, ~~68~~ 65 * 0.75 = 48.75 bytes

```
perl -e'$_=q{print+($l=($~=<>)=~y///c)%4?$~:"\$_=q{$_};eval"x($l/4)};eval'

```

See the online test suite here.

## Broken down

```
perl -e'
    $_=q{                      # store source code in $_
        print+(
            $l=($~=<>)=~ y///c # read STDIN into $~, assign length to $l
        )%4 ?                  # if length is a multiple of 4
             $~ :              # print $~
             "\$_=q{$_};eval"  # otherwise, print source code
             x($l/4)           # length/4 times
    };
    eval'                      # eval $_ to execute its contents

```
> 1 votes

# Answer
# JavaScript, ~~57~~ ~~56~~ 72 bytes * 0.75 = 54

Thanks to @Neil for a one byte savings!

```
(f=_=>alert(!(p=prompt())||(l=p.length)%4?p:`(f=${f})()`.repeat(l/4)))()

```

The shortest solution I could find was pretty straight-forward.

So, here's a couple bonus (more interesting) solutions:

### JavaScript, ~~82~~ 81 bytes * 0.75 = 60.75

```
f=_=>{try{p=prompt();a=`f=${f};f()`.repeat(p.length/4)}catch(e){a=p}alert(a)};f()

```

This one abuses `repeat`'s functionality of throwing an exception if passed a non-integer.

### JavaScript, 83 bytes * 0.70 = 58.1

```
(f=_=>alert((a=(p=prompt()).split(/.{4}/)).pop()?p:a.fill(`(f=${f})()`).join` `))()

```

This last one is definitely my favorite, splitting the input on every four characters using the regex `/.{4}/`. If there are any characters left at the end of the string when we `pop`, it isn't divisible by 4, so alert the input. Otherwise, the `pop` reduced the array's length by one, so at this point the array's length is equal to the input length / 4. In this case, just `fill` it with the quine and `join` with spaces.
> 1 votes

# Answer
# Python 3.8 (pre-release), 71 bytes -30% = 49.7

```
exec(a:="s=len(t:=input());print(*s%4and[t]or s//4*['exec(a:=%r)'%a])")

```

Try it online!
> 1 votes

# Answer
## Mathematica, 229 bytes

```
($RecursionLimit = Infinity; WriteString[$Output, If[Mod[StringLength[a = (If[(a = InputString[]) === EndOfFile, "", StringJoin["\n", a, #0[]]] & )[]], 4] == 1, ToString[#0, InputForm][], If[a == "", "", StringDrop[a, 1]]]]) & []

```

All of the whitespace is for the `InputForm` of the program to match its actual code.
> 0 votes

# Answer
# Javascript ES6, 45 bytes

```
$=(_=prompt())=>_.length%4?_:`$=${$};$()`;$()

```

Extension of my 21-byte Bling Quine. Hope that mixing `prompt` and function output is allowed.
> 0 votes

# Answer
# JavaScript, 33 bytes

```
f=(i,l=i.length)=>l%4?i:("f="+f).repeat(l/4)

```
* **+44** bytes
* **-25%** bonus

Other solutions:

## ~~44~~ 36 bytes

~~```
f=(i,l=i.length)=>l%4?i:("f="+f).repeat(!!l)

```~~
```
f=(i,l=i.length)=>l%4?i:l?("f="+f):i

```

## 38.5 bytes

```
f=(i,l=i.length)=>l%4?i:Array(l/4).fill("f="+f).join` `

```
* **+55** bytes
* **-25%** bonus
* **-5%** bonus
> 0 votes

# Answer
# Zsh, 78 bytes

```
s='s=\47%s\47
0()printf $s $s
$[$#1&3]||<<<$1'
0()printf $s $s
$[$#1&3]||<<<$1

```

Try it online!

Uses `&3` instead of `%4` so the `%` doesn't get interpreted by `printf`.

The bonus could be added with `repeat $[$#1/4]`  before the `printf` in both places, but unfortunately it gives a higher score (\\$ 75\\% \times 110 = 82.5 \\$).
> 0 votes

# Answer
# Vyxal, 38 - 25% = 28.5 bytes

```
`?DL4%[|[$:q$+$L4/*`?DL4%[|[$:q$+$L4/*

```

Try it Online!

```
`...`                      # Source code in string
     ?                     # Grab input
      D                    # Triple
       L4%                 # If length is (not) divisible by 4
          [|               # Do nothing, otherwise
            L0>[           # If length is positive
                $          # Swap (to get source-code string)
                 :q$+      # Standard quine - duplicate, uneval, swap, concatenate
                     $     # Swap to get original input
                      L4/  # Length / 4
                         * # (Source code) that many times

```

Trying to get the bonus is sadly longer.
> 0 votes

# Answer
# Excel, 204 bytes - 30% = 142.8 score

```
=LET(a,LEN(A1),c,CHAR(34),q,"=LET(a,LEN(A1),c,CHAR(34),q,#,IF(MOD(a,4)=0,TRIM(REPT(SUBSTITUTE(q,CHAR(35),c&q&c),a/4)),LEFT(A1,1))) ",IF(MOD(a,4)=0,TRIM(REPT(SUBSTITUTE(q,CHAR(35),c&q&c),a/4)),LEFT(A1,1)))

```

Link to Spreadsheet

## 2nd Place, 191 bytes - 25% = 143.25 score

```
=LET(a,LEN(A1),c,CHAR(34),q,"=LET(a,LEN(A1),c,CHAR(34),q,#,IF(MOD(a,4)=0,REPT(SUBSTITUTE(q,CHAR(35),c&q&c),a/4),LEFT(A1,1)))",IF(MOD(a,4)=0,REPT(SUBSTITUTE(q,CHAR(35),c&q&c),a/4),LEFT(A1,1)))

```

## 3rd Place, 179 bytes

```
=LET(a,LEN(A1),c,CHAR(34),q,"=LET(a,LEN(A1),c,CHAR(34),q,#,IF(a*(MOD(a,4)=0),SUBSTITUTE(q,CHAR(35),c&q&c),left(A1,1)))",IF(a*(MOD(a,4)=0),SUBSTITUTE(q,CHAR(35),c&q&c),LEFT(A1,1)))

```

## Best Cheesy Answer, 59 byte - 25% = 44.25 score

```
=LET(a,LEN(A1),IF(MOD(a,4)=0,REPT(FORMULATEXT(B8),a/4),A1))

```
> 0 votes

---
Tags: code-golf, quine
---


# Question
Title: Solve a Diagonal Burrows-Wheeler transform
# Introduction

In this challenge you will be solving diagonal Burrows-Wheeler transforms. Here is a general overview of what a diagonal Burrows-Wheeler transform is. To encode a message, you first must guarantee that it is odd in length (i.e. 5, 7, 9, etc.). Then you make a grid, `n` by `n`, where `n` is the length of the message. The first row is the original message. Each row after that is the row above it, but shifted 1 character left with the first character moving to the back. For example:

```
Hello World
ello WorldH
llo WorldHe
lo WorldHel
o WorldHell
 WorldHello
WorldHello
orldHello W
rldHello Wo
ldHello Wor
dHello Worl

```

Then you take each letter on the NW to SE diagonal and put that into a new string:

```
Hello World  H
ello WorldH  l
llo WorldHe  o
lo WorldHel  W
o WorldHell  r
 WorldHello  d
WorldHello   e
orldHello W  l
rldHello Wo  (space)
ldHello Wor  o
dHello Worl  l

```

Your encoded message is `HloWrdel ol`. To decode, first take the length of the encoded message, add 1, and divide by 2. Lets call this number `x`. Now that we know `x`, starting at the first letter, each letter is `x` after the last, looping around. For example:

```
H   l   o   W   r   d   e   l     o   l
1

Then...

H   l   o   W   r   d   e   l     o   l
1                       2

And again...

H   l   o   W   r   d   e   l     o   l
1   3                   2

Until you get...

H   l   o   W   r   d   e   l       o   l
1   3   5   7   9  11   2   4   6   8  10

```

Now just rearrange the letters in the correct order to get `Hello World`!

# Challenge

Your challenge is to write either two programs, functions, or one of each. However, both must use the same language. The first program will accept a string as input via STDIN, program arguments, or function parameters and *encode* it using this method. The second program will accept a string as input via STDIN, program arguments, or function parameters and *decode* it using this method.

# Requirements

### First Program/Function

* A single string input using any method listed above.
* Must encode the string using a diagonal Burrows-Wheeler transform style.

### Second Program/Function

* A single string input using any method listed above.
* Must decode the string using a diagonal Burrows-Wheeler transform style.

# Constraints

* You cannot use any built-in or external functions that accomplish this task.
* Standard loopholes are not allowed.
* Both programs/functions must be in the same language.

# Scoring

This is code golf, so shortest program in *bytes* wins.

If I need to add more information, leave a comment!

# Answer
# CJam, (4 + 8 = ) 12 bytes

Encoding program:

```
q2/z

```

Try it online here

Decoding program:

```
q_,2/)/z

```

Try it online here

**How (or rather, why) they work**:

The Diagonal Burrows-Wheeler transform is basically every other character of the string, with wrapping from the end. If we treat the String as a 2D matrix of 2 columns, it simply boils down to taking the transform of the matrix. Example:

```
Hello World

```

Is represented as 2D matrix as

```
He
ll
o
Wo
rl
d

```

Now, simply reading it column wise, give:

```
HloWrdel ol

```

Which is the Burrows-Wheeler transform.

Decoding is simply reverse of the process, write the string as a 2 row 2D matrix and read column wise.

**Code expansion**:

Encoder:

```
q          "Read the input";
 2/        "divide it into sub arrays of 2 characters";
   z       "Take transform";

```

Decoder:

```
q_,        "Read the input, take copy and get length of copy";
   2/      "Divide the length by 2";
     )/    "Increment and split the input into two rows";
       z   "Take transform";

```
> 12 votes

# Answer
# Python 2, 57 bytes

```
E=lambda x:(x+x)[::2]
D=lambda y:(-~len(y)/2*y)[::len(y)/2+1]

```

Try it online!

*Thanks to l4m2 for 4 bytes.*

`E` encrypts and `D` decrypts. I'm not counting the `E=` and `D=` for the score.

The decryption takes every `n`'th character wrapping around, where `n` is half the string length round up. The reason this inverts is that `2` and `n` are inverses modulo the length of the string, so taking every `n`th character inverts taking every `2`nd one.

If using a single function were allowed, I could do 44 bytes

```
def F(x,b):n=1+len(x)**b>>b;return(n*x)[::n]

```

The encrypts when `b` is `False` and decrypts when `b` is `True`. The expression `1+len(x)**b>>b` is equal to `[2,len(x)/2+1][b]`.
> 7 votes

# Answer
# J, 10 + 10 = 20

```
   ({~#|2*i.@#) 'Hello World'
HloWrdel ol

   (/:#|2*i.@#) 'HloWrdel ol'
Hello World

```

(Surrounding braces are not counted into the score as they are not part of the function definition.)

Thanks for FUZxxl for a 3-byte improvement.

Now it is nicely shown that the two functions are inverses as the first one takes characters from positions defined by the list `#|2*i.@#` and the second function arranges back the characters using the same list as ordering.

Try it online here.
> 4 votes

# Answer
# Pyth - 5 + 11 = 16 bytes

I noticed a pattern! ~Does happy dance~ The transform is just really just looping through the string picking every other elements. It only works on odd since otherwise it would never get half the elements. This is equivalent to rotating a 2 wide matrix.

### Encoder:

```
%2*2z

```

Python's step slicing doesn't loop around so I repeated the string.

```
%2      Take every other elements
 *2z    Double input string

```

### Decoder:

```
K/hlz2%K*Kz

```

Again no wrap-around for step-slicing.

```
K/hlz2       K=length of (input+1)/2
%K           Every kth element
 *Kz         From K*the input

```
> 3 votes

# Answer
# JavaScript ES6, 41 + 49 = 90 bytes

### Encoder

```
(t=>t.replace(/./g,(_,o)=>t[o*2%t.length]))('Hello World')

```

### Decoder

```
(t=>t.replace(/./g,(_,o)=>t[-~(l=t.length)/2*o%l]))('HloWrdel ol')

```

These are anonymous functions, so I only counting the code inside the parentheses because that is the whole function definition. Try it out with the snippet below: (modified to use ES5)

```
E=function(t){
  return t.replace(/./g,function(_,o){
    return t[o*2%t.length]
  })
}
D=function(t){
  return t.replace(/./g,function(_,o){
    return t[-~(l=t.length)/2*o%l]
  })
}
i=prompt();
alert('Encoded: '+E(i)+'\nDecoded: '+D(i))
```
> 2 votes

# Answer
# GNU sed -r, (20 + 104 + 1) = 125

The extra +1 in the score is for the -r option to sed. Odd length input strings are assumed.

### Encoder:

```
s/.*/&&/
s/(.)./\1/g

```
* Double up the input string
* Drop every odd (counting from 1) character

### Decoder:

The decoder makes use of `:` as a temporary marker character, so if it appears in the input string, you'll get undefined behaviour. If the input string is restricted to the 95 ASCII characters, then these markers can be replaced with something outside the ASCII range (e.g. BEL 0x7) to fix this.

```
s/.*/:&:/
:l;s/:(.)(.+)(.):/\1:\2:\3/;tl
s/:(.*)/\1:/
:m;s/(.)(.*):(.?)(.*):(.*)/\2:\4:\5\1\3/;tm
s/://g

```
* Put `:` markers at the start and end of the input string
* Shuffle the first `:` forward and second `:` backward one character at a time until the `:` markers are either side of the middle character
* Remove the first `:` and add another `:` to the end leaving "A:B:", where A is the string composed of odd characters from the plaintext input and B is the string composed of the even characters
* Riffle the characters of A and B together after the last `:` to reassemble the plaintext input
* Remove the remaining `:` markers
> 2 votes

# Answer
# Python 3 - 34 + ~~176~~ 167 + ~~11~~ 16(math) = ~~221~~ 217

Messy, but I coded it all by myself:
```
import math as m
def a(x):
  return x[::2] + x[1::2]
def b(x):
  if len(x) % 2 == 0:
    x += " "
  c=""
  for i in range(m.floor(len(x)/2)):
    c+=x[i]
    c+=x[i+m.floor((len(x)+1)/2)]
  c+=x[m.floor((len(x)-1)/2)]
  return c

```

Edit 1: (*literally as I write this, I realised how to shave off 4 bytes*)

The encoder just takes every other character and combines them, and the decoder is the inverse of that (takes every n/2th character) in the most messy way possible. (Also formatted)
> 1 votes

# Answer
# Python 3, 58 bytes

```
A=lambda x:(x+x)[::2]
def B(x):t=1+len(x)>>1;return(x*t)[::t]

```

Try it online!
> 1 votes

# Answer
# V (vim), 18 + 51 = 69 bytes

## Encoder, 18 bytes

```
o<esc>kqqlxjpkl@qq@qgJ

```

Try it online!

Moves every other character to the next line, and joins the two.

## Decoder, 51 bytes

```
YpC<c-r>=strlen('<c-r>"')/2+1
<esc>Dk@"li
<esc>jdd{qqld$}o<esc>pk0@qq@q

```

Try it online!

Uses a recursive macro to delete till the end and use it as a flatten-transpose. This took a while to figure out.
> 1 votes

# Answer
# Jelly, 2 + 3 = 5 bytes

## Encoder

```
Œœ

```

Try it online!

Split the input into odd and even indices. The two strings are then implicitly concatenated.

## Decoder

```
ŒHZ

```

Try it online!

Split into two halves, transpose, implicitly concatenate.
> 0 votes

# Answer
# Vyxal, 2+7=9 bytes

## Encoder

```
y+

```

Try it Online!

## Decoder

```
:½h$½tY

```

Try it Online!
> 0 votes

---
Tags: code-golf, cryptography
---


title: Multiply elements of the dihedral group

text:
# Question
Title: 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"
"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
> 14 votes
# , 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
> 8 votes
# perl -p, 31 bytes

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

```

Takes advantage of substitution returning truthy iff anything was substituted.

# Answer
> 7 votes
# 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
> 7 votes
# Retina 0.8.2, 18 bytes

```
{`rrrr|ss

sr
rrrs

```

Try it online! Straightforward port of the reference implementation.

# Answer
> 7 votes
# 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
> 6 votes
# 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
> 5 votes
# 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
> 5 votes
# , 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

# Answer
> 4 votes
# 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 `s`s, 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 `s`s 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 `0`s and `1`s:

```
⁻⭆⪪θ1×ι⊕⊗κ×0⁴×1﹪Σθ²

```

Try it online! Link is to verbose version of code. Explanation: As above but counts `1`s 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 `0`s and `1`s. 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 `0`s and `1`s. Explanation: The two variables track the number of `1`s and `0`s. If there are an odd number of `1`s so far then each input `0` adds `3` otherwise it adds `1`.

```
≔⁰θ≔⁰η

```

Start with `0` `1`s and `0` `0`s.

```
ＦＳ

```

Loop over the input.

```
¿Σι

```

If the digit is nonzero, ...

```
≦¬θ

```

... then invert the parity of the `1`s, ...

```
≦⁺⊕⊗θη

```

... otherwise add `1` or `3` `0`s as appropriate.

```
×0﹪η⁴

```

Output the number of `0`s (mod 4).

```
×1θ

```

Output a `1` if appropriate.

# Answer
> 4 votes
# 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
> 4 votes
# 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
> 3 votes
# 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
> 3 votes
# Java, 76 bytes

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

```

Try it online!

# Answer
> 3 votes
# 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 `1`s (`r`) and `2`s (`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
> 3 votes
# Red, 82 bytes

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

```

Try it online!

# Answer
> 3 votes
# 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!

# Answer
> 3 votes
# , ~~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
> 2 votes
# 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
> 2 votes
# 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
> 2 votes
# 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
> 2 votes
# sed 4.2.2, 26

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

```

Try it online!

# Answer
> 2 votes
# ///, 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
> 2 votes
# 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
> 2 votes
# 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
> 1 votes
# 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.

---
Tags: code-golf, string, math, abstract-algebra
---