title: How long is it in Roman

text:
# Question
Title: How long is it in Roman
## Or *Fix American Kennel Club's database*

As covered by the recent video by Matt Parker, the American Kennel Club *permits thirty-seven (37) dogs of each breed to be assigned the same name* (source), because of a database restriction for Roman numeral length.

Given an integer, your task is to output the length of its Roman representation.

## Rules

* Your input will be an integer in the range 1-3899.
* Conversion to Roman is performed using the standard subtractive notation (so `4=IV`, `9=IX`, `95=XCV`, `99=XCIX`).
* This is , the usual rules apply.

## Test-cases

```
input  output
1      1
2      2
3      3
4      2
5      1
6      2
9      2
10     1
37     6
38     7
95     3
99     4
288    10
2022   6
3089   9
3899   11

```

# Answer
# Python 2, 44 bytes

```
f=lambda x:x and 5739180/5**(x%10)%5+f(x/10)
```

Attempt This Online!

The magic number `5739180` encodes the list `[2, 4, 3, 2, 1, 2, 3, 2, 1, 0]` in base 5, which correspond to the Roman numeral lengths for the decimal digits 9 to 0. `5**(x%10)%5` extracts the `x%10`th base-5 digit, and the rest is a recursive function to compute the sum per decimal digit of `x`.
> 22 votes

# Answer
# JavaScript (ES6), 37 bytes

```
f=n=>n&&+"0123212342"[n%10]+f(n/10|0)

```

Try it online!

### How?

In standard subtractive notation, the lengths of the digits are the same for units, tens, hundreds and thousands (up to 3000). So we can just recursively compute the total length.

```
   | units | tens | 100's | 1000's | length
---+-------+------+-------+--------+--------
 0 | -     | -    | -     | -      |   0
 1 | I     | X    | C     | M      |   1
 2 | II    | XX   | CC    | MM     |   2
 3 | III   | XXX  | CCC   | MMM    |   3
 4 | IV    | XL   | CD    |        |   2
 5 | V     | L    | D     |        |   1
 6 | VI    | LX   | DC    |        |   2
 7 | VII   | LXX  | DCC   |        |   3
 8 | VIII  | LXXX | DCCC  |        |   4
 9 | IX    | XC   | CM    |        |   2

```

---

# JavaScript (ES6), 40 bytes

This is an attempt to find a short formula instead of a lookup table. But it's still longer.

```
f=n=>n&&f(n/10|0)+(30%(n%=10)&171/n^n%4)

```

Try it online!

### 36 bytes

It does come out shorter if we can take the input as a list of digits:

```
a=>a.map(n=>t+=30%n&171/n^n%4,t=0)|t

```

Try it online!
> 14 votes

# Answer
# Vyxal, 3 bytes

```
øṘL

```

Try it Online!

I love it when there's built-ins for things like this.

## Explained

```
øṘL
øṘ  # Convert input to Roman numerals
  L # and return the length of that.

```
> 10 votes

# Answer
# Python 2, 41 bytes

Uses @Arnauld's idea of computing the length of each decimal digit separately. A magic hash in the form `x**a%b%5` seems to work well.

```
f=lambda n:n and(n%10)**24%8684%5+f(n/10)

```

Try it online!

Other magic:

```
lambda n:sum(7125144/ord(c)%5for c in`n`)   # 41
f=lambda n:n and(n%5+n/5%2>>n%5/4)+f(n/10)  # 42 (has actual strategy)

```

# Python 2, 41 bytes

Alternatively, the same length, but who doesn't love a little magic `hash`?

```
lambda n:sum(hash(c+'WQDE')%5for c in`n`)

```

Try it online!

The little C script below finds all possible 4-byte long suffixes to seed the hash, and takes roughly a second to complete. Interestingly, out of the 12 valid solutions, `'WQDE'` is the only one with all uppercase characters. If you think about it, the chances of this occurrence are only `26^4/127^4 ~ 0.176%`!

```
// https://github.com/python/cpython/blob/v2.7/Objects/stringobject.c#L1263

#include <stdio.h>
#include <time.h>

int py_mod(long long x, int m) { int ret = x % m; return ret >= 0 ? ret : ret + m; }

const long long h[10] = {6144036912055440, 6272037681056595, 6400038450057750, 6528039219058905, 6656039988060060, 6784040757061215, 6912041526062370, 7040042295063525, 7168043064064680, 7296043833065835};
long long h0[10], h1[10], h2[10];

int main() {
    clock_t sclock = clock();
    for (int c0 = 1; c0 < 128; c0++) {
        for (int i0 = 0; i0 < 10; i0++) h0[i0] = (h[i0] ^ c0) * 1000003;
        for (int c1 = 1; c1 < 128; c1++) {
            for (int i1 = 0; i1 < 10; i1++) h1[i1] = (h0[i1] ^ c1) * 1000003;
            for (int c2 = 1; c2 < 128; c2++) {
                for (int i2 = 0; i2 < 10; i2++) h2[i2] = (h1[i2] ^ c2) * 1000003 ^ 5;
                for (int c3 = 1; c3 < 128; c3++) {
                    if (py_mod(h2[0] ^ c3, 5) != 0) continue;
                    if (py_mod(h2[1] ^ c3, 5) != 1) continue;
                    if (py_mod(h2[2] ^ c3, 5) != 2) continue;
                    if (py_mod(h2[3] ^ c3, 5) != 3) continue;
                    if (py_mod(h2[4] ^ c3, 5) != 2) continue;
                    if (py_mod(h2[5] ^ c3, 5) != 1) continue;
                    if (py_mod(h2[6] ^ c3, 5) != 2) continue;
                    if (py_mod(h2[7] ^ c3, 5) != 3) continue;
                    if (py_mod(h2[8] ^ c3, 5) != 4) continue;
                    if (py_mod(h2[9] ^ c3, 5) != 2) continue;
                    printf("found: (%d,%d,%d,%d) [%c%c%c%c]\n",
                        c0, c1, c2, c3, c0, c1, c2, c3);
                }
            }
        }
    }
    printf("Time elapsed: %.3fs\n", (double) (clock() - sclock) / CLOCKS_PER_SEC);
    return 0;
}

```
> 7 votes

# Answer
# Excel, 15 bytes

```
=LEN(ROMAN(A1))

```

It feels like a rare win to use an Excel built-in for a programming challenge.
> 6 votes

# Answer
# Ruby, ~~39~~ 37 bytes

```
->n{n.digits.sum{|x|x%5>3?2:x/5+x%5}}

```

Try it online!

Thanks dingledooper for -2 bytes (pointing out that 37 and 39 are two different numbers, which I didn't realize)
> 5 votes

# Answer
# x86-64 machine code, 27 bytes

```
97 31 C9 67 8D 71 05 99 F7 F6 F6 C2 04 D1 D8 74 02 D1 EA 11 D1 85 C0 75 EE 91 C3

```

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes a number in EDI and returns a number in EAX.

In assembly:

```
f:  xchg edi, eax     # Exchange the input number into EAX.
    xor ecx, ecx      # Set ECX to 0. ECX will hold the running total.
    lea esi, [ecx+5]  # Set ESI to 5.
l:  cdq           # Sign-extend, setting up for the next instruction.
    div esi       # Divide by 5, putting the quotient in EAX and the remainder in EDX.
    test dl, 4    # Set flags based on the bitwise AND of the low byte of EDX with 4.
                  #  This makes the zero flag (ZF) 1 iff the remainder is not 4.
                  #  Also, the carry flag (CF) becomes 0.
    rcr eax, 1    # Rotate EAX together with CF right by 1.
                  #  With CF being 0, this halves EAX, putting the remainder into CF.
                  #  This also leaves ZF unchanged.
    jz s          # Jump, to skip one instruction, if ZF is 1.
    shr edx, 1    # (For remainder 4) Shift EDX right by 1,
                  #  changing it from 4 to 2 and making CF 0.
s:  adc ecx, edx  # Add EDX+CF to the total in ECX.
    test eax, eax # Set flags based on EAX.
    jnz l         # If it's not zero, jump back to repeat.
    xchg ecx, eax # Exchange the total from ECX into EAX.
    ret           # Return.

```
> 5 votes

# Answer
# Jelly, 13 bytes

```
D‘ị“ȤɱȯẎ’DU¤S
```

Attempt This Online!

```
D               digits
 ‘              add 1 to each (because Jelly uses 1-based indexing)
  ị        ¤    index into:
   “ȤɱȯẎ’         compressed integer 2432123210
         D        digits
          U       reversed
            S   sum

```
> 4 votes

# Answer
# , ~~30~~ 29 bytes

```
\(n)nchar(paste(as.roman(n)))
```

Attempt This Online!

Convert to `roman`, use `paste` to convert to `character`, then find the number of characters.

-1 thanks to pajonk.
> 4 votes

# Answer
# Jelly, 10 bytes

```
“Mḅṗʋ’D⁸ṃS

```

A monadic Link that accepts a positive integer and yields the Roman numeral count as a positive integer.

**Try it online!**

### How?

```
“Mḅṗʋ’D⁸ṃS - Link: positive integer, N
“Mḅṗʋ’     - base 250 integer = 1232123420
      D    - to decimal -> X = [1,2,3,2,1,2,3,4,2,0]
       ⁸   - N
        ṃ  - base-decompress using X as the the new digits [1,...,9,0]
         S - sum

```

---

Note that `“Mḅṗʋ’D` saves one byte over using the pattern of the lengths themselves with `3,4R;0j2`
i.e. `[3,4] -> [[1,2,3],[1,2,3,4]] -> [[1,2,3],[1,2,3,4],0] -> [1,2,3,2,1,2,3,4,2,0]`.
> 4 votes

# Answer
# Wolfram Language (Mathematica), 26 bytes

```
StringLength@*RomanNumeral

```

Try it online!

More built-ins.
> 4 votes

# Answer
# Factor \+ `roman`, 17 bytes

```
[ >roman length ]

```

Try it online!

Non-builtin version:

# Factor \+ `math.unicode`, 56 bytes

```
[ >dec 48 v-n [ 5 /mod [ 3 > 2 rot ] keep + ? ] map Σ ]

```

Port of @GB's Ruby answer.
> 3 votes

# Answer
# 05AB1E, 3 bytes

```
.Xg

```

Try it online or verify all test cases.

Without Roman-numeral builtin (**10 bytes**):

```
•’λåK•RÅвO

```

Try it online or verify all test cases.

**Explanation:**

```
.X          # Convert the (implicit) input-integer to a Roman-numeral string
  g         # Pop and push its length
            # (after which the result is output implicitly)

•’λåK•      # Push compressed integer 2432123210
      R     # Reverse it: 0123212342
       Åв   # Convert the (implicit) input-integer to custom-base "0123212342";
            # basically convert the integer to base-length as list (base-10 in
            # this case), and index the base-values into the string
         O  # Sum the list together
            # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `•’λåK•` is `2432123210`.
> 3 votes

# Answer
# Vyxal, 10 bytes

(without roman numeral builtin)

```
»ḣ₈ɖ¢»fṘτ∑

```

Try it Online! or Verify all the test cases

## How?

```
»ḣ₈ɖ¢»fṘτ∑
»ḣ₈ɖ¢»      # Push compressed integer 2432123210
      f     # Convert to list of digits: [2, 4, 3, 2, 1, 2, 3, 2, 1, 0]
       Ṙ    # Reverse
        τ   # Convert the (implicit) input to this custom base
         ∑  # Summate

```
> 3 votes

# Answer
# Retina 0.8.2, 19 bytes

```
T`d`0-321-42
.
$*
1

```

Try it online! Link includes test cases. Explanation:

```
T`d`0-321-42

```

Translate the digits `0-9` into the digits `0123212342`.

```
.
$*

```

Convert to unary.

```
1

```

Take the sum and convert to decimal.
> 2 votes

# Answer
# Charcoal, 14 bytes

```
ＩΣ⭆Ｓ§”)⊞⎚mS”Ｉι

```

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

```
   Ｓ            Input string
  ⭆             Map over characters and join
     ”)⊞⎚mS”    Compressed string `0123212342`
    §           Indexed by
             ι  Current character
            Ｉ   Cast to integer
 Σ              Take the sum
Ｉ               Cast to string
                Implicitly print

```

The `Sum` of a string of digits (as distinct from an array of digit characters) is the sum of all the integer values of the digits, which saves having to cast them back to integer manually.
> 2 votes

# Answer
# Python 3, 49 bytes

Port of @Arnauld's JS answer.

```
f=lambda n:n and int('0123212342'[n%10])+f(n//10)

```

Try it online!
> 2 votes

# Answer
# Pyth, 17 bytes

```
s@L_j5739180 5jQT

```

Test suite

##### Explanation:

```
s@L_j5739180 5jQT | Full program
------------------+------------------------------------
  L           jQT | Map over each digit d of the input:
 @L               |  Get the dth element of the list
   _j5739180 5    |   [0, 1, 2, 3, 2, 1, 2, 3, 4, 2]
s                 | Sum the resulting list

```
> 2 votes

# Answer
# Stax, 10 bytes

```
ì¿≥Θu^Z6ê)

```

Run and debug it
> 1 votes

---
Tags: code-golf, roman-numerals
---


title: ro1000an nu1000era50 en100o501ng

text:
# Question
Title: ro1000an nu1000era50 en100o501ng
In the hovertext of this xkcd:

There's an "encoding" based on replacing runs of roman numerals with their sums. To do this:

* Find all runs of at least 1 roman numeral (`IVXLCDM`)
* Replace them with their sums, as numbers

The Roman Numerals are `IVXLCDM`, corresponding respectively to `1, 5, 10, 50, 100, 500, 1000`. You should match them in either case.

For example, if we take `encoding`, `c` is the roman numeral 100, so it gets replaced with 100, leaving `en100oding`. Then, `di` are both roman numerals, respectively 500 and 1, so it gets replaced with their sum, 501, leaving `en100o501ng`.

Your challenge is to implement this, given a string. This is , shortest wins!

Note: the xkcd implements some more complex rules regarding consecutive characters like `iv`. This can create some ambiguities so I'm going with this simpler version.

## Testcases

```
xkcd -> 10k600
encodingish -> en100o501ng1sh
Hello, World! -> He100o, Wor550!
Potatoes are green -> Potatoes are green
Divide -> 1007e
bacillicidic -> ba904

```

# Answer
> 12 votes
# Vyxal `s`, 9 bytes

```
ƛøṘ∨;⁽-ḊṠ

```

Try it online or run a test suite.

```
ƛøṘ∨;⁽-ḊṠ
ƛ          # Map, and for each character:
 øṘ        #  Convert from roman numeral to a number, or 0 if invalid
   ∨       #  Logical OR with the character: if it's 0, then use the character instead
    ;      # Close map
       Ḋ   # Group results where the same result appears consecutively...
     ⁽-    # ...with subtracting it by itself. Subtracting a number by itself is 0,
           # but subtracting a string by itself is "". These are two different values, so it works as a type check.
        Ṡ  # Sum each. Summing a list of characters will turn it into a string, but lists of numbers will simply sum.
           # The s flag joins the list together into a string before outputting.

```

# Answer
> 4 votes
# Factor \+ `grouping.extras math.unicode roman`, ~~100~~ 99 bytes

```
[ 1 group [ [ roman> ] try ] map [ real? ] group-by values [ [ Σ >dec ] try ] map flatten concat ]

```

Needs modern Factor for \>dec. Here's a version that runs on TIO for 3 more bytes, though: Try it online!

#### How?

This answer relies on `try` in order to process heterogeneous arrays relatively succinctly, as `roman>` blows up on non- roman numbers and `sum` blows up on arrays of strings.

```
                          ! "encodingish"
1 group                   ! { "e" "n" "c" "o" "d" "i" "n" "g" "i" "s" "h" }
[ [ roman> ] try ] map    ! { "e" "n" 100 "o" 500 1 "n" "g" 1 "s" "h" }
[ real? ] group-by values ! { V{ "e" "n" } V{ 100 } V{ "o" } V{ 500 1 } V{ "n" "g" } V{ 1 } V{ "s" "h" } }
[ [ Σ >dec ] try ] map    ! { V{ "e" "n" } "100" V{ "o" } "501" V{ "n" "g" } "1" V{ "s" "h" } }
flatten                   ! { "e" "n" "100" "o" "501" "n" "g" "1" "s" "h" }
concat                    ! "en100o501ng1sh"

```

# Answer
> 4 votes
# JavaScript (Node.js), 91 bytes

```
s=>s.replace(/[ivxlcdm]+/gi,s=>Buffer(s).map(c=>t-=~[9,4,,99,499,49,999][c%32%24%7],t=0)|t)

```

Try it online!

# Answer
> 4 votes
# , 146 bytes

```
\(s){`!`=is.na
T=tapply
r=as.roman(t<-el(strsplit(s,"")))
a=T(r,i<-rep(seq(a=x<-rle(!r)$l),x),sum)
a[!a]<-T(t,i,g<-\(x)Reduce(paste0,x))[!a]
g(a)}
```

Attempt This Online!

Definitely not the best tool for the job, despite built-in `roman` numerals.

### Explanation outline:

1. Split string to characters (stored in `t`; this part could be omitted if we took input as a vector of characters).
2. Convert to type `roman` \- successful for Roman digits, otherwise `NA` (stored in `r`).
3. Build index `i` for spitting on consecutive runs of `NA`s or not `NA`s.
4. Tapply (`split`+`sapply`) sum on Roman numerals.
5. Fill `NA`s with chunks from original string.
6. Collapse vector to one string.

# Answer
> 3 votes
# Ret1na 0.8.2, 45 bytes

```
i(`m
dd
d
5$*c
c
ll
l
5$*x
x
vv
v
5$*i
i+
$.&

```

Try 1t on51ne! 51nk 1n150u500es test 100ases. E10p50anat1on:

```
i(`

```

Run the who50e s100r1pt 100ase-1nsens1t6e50y.

```
m
dd

```

1000 = 2 * 500.

```
d
5$*c

```

500 = 5 * 100.

```
c
ll

```

100 = 2 * 50.

```
l
5$*x

```

50 = 5 * 10.

```
x
vv

```

10 = 2 * 5.

```
v
5$*i

```

5 = 5 * 1.

```
i+
$.&

```

100on5ert to 500e1101a50.

# Answer
> 2 votes
# 05AB1E, 21 bytes

```
.γu.vd}εDSu.v©àdi®O]J

```

Try it online or verify all test cases.

Or alternatively, with I/O as character array:

```
u.vøεΣa}н}.γd}ε¤diO]S

```

Try it online or verify all test cases.

Can definitely be golfed a bit. But despite having a Roman Number builtin, the functionality of some builtins are nowhere near as versatile as the Vyxal answer.. Why you might ask?

1. The Roman Number builtin only works on uppercase letters (probably a bug..), so preserving the casing costs quite a few bytes.
2. Sum given an error on letters in the new 05AB1E version, so explicit checks before summing are unfortunately necessary.

**Explanation:**

```
.γ             # Adjacent group by the (implicit) input-string:
  u            #  Convert to uppercase
   .v          #  Convert from letter to Roman Number
     d         #  Check if this is a (non-negative) integer
 }ε            # After the adjacent group-by: map over each group:
   D           #  Duplicate the current group
    S          #  Convert it to a list of characters
     u         #  Uppercase each
      .v       #  Convert it to a Roman Number
               #  (it will remain an uppercase character if invalid)
        ©      #  Store this list in variable `®` (without popping)
         àdi   #  If this list contains an integer:
            ®O #   Push and sum list `®`
  ]            # Close the if-statement and map
   J           # Join everything together to a single string
               # (which is output implicitly as result)

```

```
u              # Uppercase each character in the (implicit) input-list
 .v            # Convert each to a Roman Number
               # (it will remain an uppercase character if invalid)
   ø           # Pair each with the characters of (implicit) input-list
    ε          # Map over each pair:
     Σ         #  (Stable) sort the pair by:
      a        #   Check if it's a letter (0 if number; 1 if letter)
     }н        #  After the sort-by: pop and push the first character
    }.γ        # After the map: adjacent group by:
       d       #  Is it a (non-negative) integer
      }ε       # After the adjacent group-by: map over each group:
        ¤      #  Push the first item (without popping the group list)
         di    #  If it's a (non-negative) integer:
           O   #   Sum the group together
       ]       # Close the if-statement and map
        S      # Convert the numbers and remaining groups to a flattened list
               # of characters
               # (which is output implicitly as result)

```

# Answer
> 2 votes
# Charcoal, 52 bytes

```
≔⁰θＦ⊞Ｏ⪪Ｓ¹ω«≔⌕⪪IVXLCDM¹↥ιη¿⊕η≧⁺×Ｘχ÷η²⊕×⁴﹪η²θ«⁺∨θωι≔⁰θ

```

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

```
≔⁰θ

```

Start with a running total of `0`.

```
Ｆ⊞Ｏ⪪Ｓ¹ω«

```

Loop over the input characters, but include a trailing empty string.

```
≔⌕⪪IVXLCDM¹↥ιη

```

Get the index of the uppercase character in the list of Roman numerals.

```
¿⊕η

```

If this is a Roman numeral, then...

```
≧⁺×Ｘχ÷η²⊕×⁴﹪η²θ«

```

... use the index to convert it to decimal and add it to the running total, otherwise:

```
⁺∨θωι

```

Prefix the running total, if any, to the character before printing it.

```
≔⁰θ

```

Clear the running total.

# Answer
> 2 votes
# Python, ~~130~~ ~~122~~ 117 bytes

*-8 bytes by porting Arnauld's formula*

*-5 bytes thanks to movatica*

```
lambda s:re.sub('[ivxlcdm]+',lambda M:str(sum(1+[9,4,0,99,499,49,999][ord(i)%32%24%7]for i in M[0])),s,0,2)
import re

```

Try it online!

Matches runs of roman numerals and replaces them with their sum. The `2` at the end is equivalent to `re.IGNORECASE`.

# Answer
> 1 votes
# C (gcc), ~~150~~ ~~159~~ ~~152~~ ~~137~~ ~~133~~ 126 bytes

* +9 to handle either case
* -7 thanks to emanresu A
* -22 thanks to ceilingcat
* -4 thanks to Neil

Processes a string, looking for Roman numerals. If it finds one, the value is added to the total consecutive run. Once a non-numeral is found, the total is printed if it is greater than zero (and the total is reset), then the non-numeral is printed. Finally, the total is printed if the end of string is encountered in case the final character was a Roman numeral.

```
char*n="ivxlcdm",*d;t;f(char*s){for(t=0;t=!(d=index(n,*s|32))?t&&printf("%d",t),*s&&!putchar(*s):t+L"\1\5\n2dǴϨ"[d-n],*s++;);}

```

Try it online!

---
Tags: code-golf, string, encoding, roman-numerals
---


title: Not-Roman-Numeral Addition

text:
# Question
Title: Not-Roman-Numeral Addition
Write the shortest program or function that mimics the addition in this XKCD strip:

## Input

Two positive decimal integers containing only the digits `150`.

## Output

The positive decimal integer result of adding the two inputs together in the manner shown above. This output should also only have the digits `150`.

## Specification

### Input and Output

Input and output are numbers only containing digits `150`.

### Roman Numerals

This challenge will use Standard Form numerals:

|  | Thousands | Hundreds | Tens | Units |
| --- | --- | --- | --- | --- |
| 1 | M | C | X | I |
| 2 | MM | CC | XX | II |
| 3 | MMM | CCC | XXX | III |
| 4 | MMMM | CD | XL | IV |
| 5 | MMMMM | D | L | V |
| 6 | MMMMMM | DC | LX | VI |
| 7 | MMMMMMM | DCC | LXX | VII |
| 8 | MMMMMMMM | DCCC | LXXX | VIII |
| 9 | MMMMMMMMM | CM | XC | IX |

Note the subtractive notation on multiples of `40` and `90`, and additive notation on multiples of `1000`.

## Worked Example

Consider a test case below, `1010111 + 101051 = 1050110 (23 + 26 = 49)`.

Convert the inputs to Roman numerals, then to Arabic numerals:

```
1010111 => XXIII => 23
101051  => XXVI  => 26

```

Perform the addition:

```
23 + 26 => 49

```

Convert the output back to Roman numerals, then for each Roman numeral substitute its Arabic numeral value:

```
49 => XLIX => 10 50 1 10 => 1050110

```

## Test Cases

```
A + B = C (explanation)
=========
1 + 1 = 11 (1 + 1 = 2)
11 + 11 = 15 (2 + 2 = 4 == IV)
15 + 5 = 110 (4 + 5 = 9 == IX)
101010 + 1 = 1010101 (30 + 1 = 31)
1010 + 111 = 1010111 (20 + 3 = 23)
1010 + 15 = 101015 (20 + 4 = 24)
1010 + 5 = 10105 (20 + 5 = 25)
1010111 + 101051 = 1050110 (23 + 26 = 49)
101015 + 51 = 101010 (24 + 6 = 30)
1010015 + 15 = 101005111 (94 + 4 = 98)
100010010010101015 + 1000100010010010010505 = 100010001000500501010110 (1234 + 2345 = 3579)
100010010010101015 + 1000100010001000100010001000100050010010050105 = 100010001000100010001000100010001000100100010100110 (1234 + 8765 = 9999)

```

## Other Notes

As seen in the comic, Randall is doing a simple substitution of Roman numerals with their decimal equivalents:

* `I => 1`
* `V => 5`
* `X => 10`

Presumably, this will be extended for all Roman numerals (up to 1000):

* `L => 50`
* `C => 100`
* `D => 500`
* `M => 1000`

For more information, see the ExplainXKCD wiki page.

This is , so shortest code wins!

# Answer
# Vyxal, 21 bytes

```
ƛ`.0*`Ẏ⌊øṘṅøṘ;∑øṘvøṘṅ

```

Try it Online!

## How?

```
ƛ`.0*`Ẏ⌊øṘṅøṘ;∑øṘvøṘṅ
ƛ                      # Map, and for both strings:
 `.0*`Ẏ                #  Get all regex matches ".0*"
       ⌊               #  Convert each to integers
        øṘ             #  Convert each to their roman numeral
          ṅ            #  Join together to a single string
           øṘ          #  Convert from roman numeral to number
             ;         # Close map
              ∑        # Sum
               øṘ      # Convert to roman numeral
                 vøṘ   # Convert each character from roman numeral to number
                    ṅ  # Join together to a string

```
> 3 votes

# Answer
# Factor \+ `roman`, ~~117~~ 114 bytes

```
[ [ R/ .0*/ all-matching-subseqs [ dec> >roman ] f map-as concat ] bi@
roman+ 1 group [ roman> >dec ] map-concat ]

```

Needs modern Factor for \>dec, but here's a version that works on ATO for 3 more bytes:

Attempt This Online!

-3 bytes thanks to @Steffan
> 2 votes

# Answer
# JavaScript (ES6), 204 bytes

Expects `(a)(b)`, where both arguments are strings.

```
a=>b=>(h=(n,k)=>n?h(n/10|0,k+0)+[k%8?[,k,d=k+k,d+k,k+(x=k*5),x,x+k,x+d,x+d+k,d+0][n%10]:k.repeat(n)]:'')((g=s=>s.replace(p=/.0*/g,s=>s-p?(t+=s<p?n:s-n,p=s<p?n=+s:0/(n=0)):n+=p=+s,t=n=0)&&t+n)(a)+g(b),'1')

```

Try it online!

### Parsing the input strings

```
g = s =>                    // s = input string
s.replace(                  // search in s:
  p = /.0*/g,               //   each non-zero digit followed by some 0's
  s =>                      //   given this substring s:
  s - p ?                   //     if s is not equal to the previous match:
    (                       //
      t +=                  //       add to t:
        s < p ? n           //         either n if s < p
              : s - n,      //         or s - n otherwise (e.g. 1 10 -> 9)
      p =                   //       set p to:
        s < p ? n = +s      //         s (also loaded in n) if s < p
              : 0 / (n = 0) //         or NaN otherwise (and set n to 0)
    )                       //
  :                         //     else:
    n +=                    //       add s to the accumulator n
      p = +s,               //       and copy s in p
  t = n = 0                 //   start with t = n = 0
)                           // end of replace()
&& t + n                    // return the sum of t and the accumulator

```

### Formatting the output

```
h = (n, k) =>               // n = number to convert, k = current prefix
n ?                         // if n is not equal to 0:
  h(                        //   do a recursive call with:
    n / 10 | 0,             //     floor(n / 10)
    k + 0                   //     a '0' appended to k
  ) +                       //   end of recursive call
  [                         //   append:
    k % 8 ?                 //     if k is not equal to '1000':
      [ ,                   //       0 : nothing
        k,                  //       1 : k           --> e.g. '10'
        d = k + k,          //       2 : k+k         --> '1010'
        d + k,              //       3 : k+k+k       --> '101010'
        k + (x = k * 5),    //       4 : k+(5*k)     --> '1050'
        x,                  //       5 : 5*k         --> '50'
        x + k,              //       6 : (5*k)+k     --> '5010'
        x + d,              //       7 : (5*k)+k+k   --> '501010'
        x + d + k,          //       8 : (5*k)+k+k+k --> '50101010'
        d + 0               //       9 : k+k+0       --> '10100'
      ][n % 10]             //       select the correct entry
    :                       //     else:
      k.repeat(n)           //       just repeat '1000' n times
  ]                         //
:                           // else:
  ''                        //   stop the recursion

```
> 1 votes

# Answer
# 05AB1E, ~~24~~ ~~23~~ 20 bytes

```
εDSĀÅ¡J.XJ.v}O.XS.vJ

```

-3 bytes thanks to @CommandMaster

Try it online or verify all test cases.

**Original ~~24~~ 23 bytes answer:**

```
X3FD5*x}r)D.X:.vO.XS.vJ

```

ASCII only. :)

Try it online or verify all test cases.

**Explanation:**

```
ε            # Map over both integers in the (implicit) input-pair:
 D           #  Duplicate the current integer
  S          #  Convert the copy to a list of digits
   Ā         #  Check for each digit that it's NOT 0 (0 if 0; 1 otherwise)
    Å¡       #  Split the number on the truthy (==1) values
      J      #  Join each inner list together
       .X    #  Convert each from an integer to a Roman Numeral
         J   #  Join it together to a single string
          .v # Convert it from a Roman Numeral to an integer
}O           # After the map: sum the two integers together
  .X         # Convert this sum back to a Roman Numeral
    S        # Convert it to a list of characters
     .v      # Convert each character from a Roman Numeral back to an integer
       J     # Join them together
             # (after which the result is output implicitly)

```

```
X3FD5*x}r)   # Push list [1000,500,100,50,10,5,1]:
X            #  Push 1
 3F          #  Loop 3 times:
   D         #   Duplicate the current value
    5*       #   Multiply the copy by 5
      x      #   Double it (without popping)
       }r    #  After the loop: reverse all values on the stack
         )   #  Then wrap the entire stack into a list
D            # Duplicate this list
 .X          # Convert each to a Roman Numeral: ["M","C","D","L","T","V","I"]
   :         # Replace all integers to these characters in the (implicit) input-pair
.v           # Convert both strings from Roman Numerals to integers
  O.XS.vJ    # Same as above

```
> 1 votes

---
Tags: code-golf, math, number, roman-numerals
---


# Question
Title: Help me design an unfair laundry machine
There's a payment machine for laundry in my building which does a few frustrating things. The ones relevant to this challenge are:

* It doesn't make change. So if you pay over the amount then you are not getting that over-payment back.
* It doesn't accept coins smaller than 20c. Meaning the only coins it accepts are 20c, 50c, 1€ and 2€ (1€=100c).
* The price of running one machine is 2.30€

The third item doesn't seem immediately frustrating, however if we take a look at all the ways to make 2.30€ we can see an issue:

| 2€ | 1€ | 50c | 20c |
| --- | --- | --- | --- |
| 0 | 1 | 1 | 4 |
| 0 | 0 | 3 | 4 |
| 0 | 0 | 1 | 9 |

You may notice that in order to pay 2.30€ you *must* have at least a 50c coin and four 20c coins. There's no way to substitute other coins in, if you show up and you don't have that combination of coins (plus extra coins to cover the remainder) you are going to have to overpay.

I'm very suspicious that the designers of the machine set the price this way just to make it look reasonable but force over-payment. I think most people end up paying 2.50€ because it's simpler or because their pocket change doesn't meet the stringent requirements to pay exactly 2.30€

To illustrate this hypothesis I have created a strictness index. To measure it you take all the ways you can make a particular price using the available coin set and for each coin type find the option that uses the least of that coin, record the number of that coin used and sum them all up.

If we use the example above, the strictness index is 0 + 0 + 1 + 4 = 5. In fact there is no possible price with a worse strictness index for this set of coins. 5 is the limit.

Not all prices have a strictness index, for example 1.97€ can't be made with the coins above so this procedure doesn't make sense. We just ignore these values, we only care about prices that are possible to make with the given coins.

## Task

In this challenge you will take a set of positive integers representing coin values and calculate the maximum strictness index a price can have in this coin system.

The input set will always contain at least 2 values, there will never be duplicates and you may assume it is in strictly ascending or descending order.

This is so the goal is to minimize the size of your source code as measured in bytes.

## Test cases

```
2 5 10 20 -> 5
2 3 -> 3
2 3 5 -> 2
1 8 -> 7
2 4 -> 2

```

# Answer
> 4 votes
# Jelly, 19 bytes

```
Œṗf³$ƑƇœ&/¹¡L
P!Ç€Ṁ

```

Try it online!

-1 thanks to Jonathan Allan.

Unlike Vyxal, Jelly's multiset intersection appears to work properly.

This is roughly \\$O\left(2^{\left(\prod{s}\right)!}\right)\\$. I'm pretty sure using caird's fork would save a few bytes but I can't be bothered for now.

```
P!Ç€Ṁ  Main link (takes a list of numbers)
P!     Factorial of product
   €   Map over 1...n
  Ç    Helper (see below)
    Ṁ  Take maximum

Œṗf³$ƑƇœ&/¹¡L  Helper link (takes argument n)
Œṗ             Integer partitions
      Ƈ        Filtered by...
    $Ƒ         Same under
  f³           Remove all but input
         /     Reduce by
       œ&      Multiset union
          ¹¡   N times
            L  Get final length

```

# Answer
> 1 votes
# Python3, 551 bytes:

```
from itertools import*
def f(v):
 j,m=[],{}
 for I,n in enumerate(v):
  c=0
  while(c:=c+1):
   F,O=0,[]
   for j in permutations(Y:=[*(set(v)-{n})],len(Y)):
    s=c*n
    for i in j:s-=i*(s//i)
    if s>0:O+=[c];F=1
    else:O+=[0];F=0;break
   m[n]=max(O)if 0 not in O else(m[n]if n in m else 0)
   if F==0:break
 U,V=[],[i for i in m if m[i]]
 for i in range(1,len(V)+1):
  for j in combinations(V,i):
   n=sum(k*m[k]for k in j)
   if 0==any(any(0==(n-(t*(n//t)))%l and t*(n//t)for l in j)for t in {*v}-{*V}):U+=[sum(m[l]for l in j)]
 return max(U)

```

Try it online!

# Answer
> 1 votes
# JavaScript (Node.js), 143 bytes

```
with(Math)f=(a,i=0,t)=>!t&&(g=n=>n>0?min(...a.map(m=>(m==t)+g(n-m))):n&&1/0,g(i,s=0)||a.map(v=>s+=g(i,t=v)),max(s,f(a,i+1,a.map(v=>i/=v*v)|i)))

```

Try it online!

I hope the answer is correct although I cannot verify it by any larger testcases due to its terrible time complexity.

---
Tags: code-golf, number-theory, integer-partitions
---


title: Cheating a multiple choice test

text:
# Question
Title: Cheating a multiple choice test
### Introduction

While studying, I tried to come up with several ways to cheat a multiple choice test. It basically is a compressed version of the multiple choice answers. The method goes as following:

The answers to the test:

```
BCAABABA

```

These can be converted to 3 different arrays, which indicates true or false if the current letter is the answer:

```
    B  C  A  A  B  A  B  A
A: [0, 0, 1, 1, 0, 1, 0, 1]
B: [1, 0, 0, 0, 1, 0, 1, 0]
C: [0, 1, 0, 0, 0, 0, 0, 0]

```

Interpreting these numbers as binary would compress this a lot. But this can actually be compressed a bit more. If you know the positions of A and B, you don't need the positions for C. This can be done with a bitwise NOT operator:

```
A: [0, 0, 1, 1, 0, 1, 0, 1]
B: [1, 0, 0, 0, 1, 0, 1, 0]

A+B: [1, 0, 1, 1, 1, 1, 1, 1]
C:   [0, 1, 0, 0, 0, 0, 0, 0]

```

Converting the arrays A and B to binary numbers would result in:

```
A: 00110101
B: 10001010

```

That means that 8 multiple choice answers can be compressed to two bytes!

---

### Task

Given two numbers in binary, or two arrays consisting of only 0's and 1's with the same length, output the multiple choice answers

---

### Rules

* Input can be in the any form you like, like `[1, 0, 0, 1]` or `1001`.
* You may provide a program or a function.
* You may assume that the input is always valid.
* You may also output as a list, separated with spaces, etc.
* The multiple choice answers only consist of A's, B's and C's. You may however use lower case instead.
* This is , so the submission with the least amount of bytes wins!

---

### Test cases

```
Input: [1, 0, 0, 1, 0, 0, 1] [0, 1, 0, 0, 1, 0, 0]
Output: ABCABCA

Input: [0, 0, 0, 0, 1, 0, 1, 1] [1, 0, 1, 0, 0, 0, 0, 0]
Output: BCBCACAA

Input: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Output: CCCCCCCCCC

```

---

### Leaderboard

```
var QUESTION_ID=69770,OVERRIDE_USER=34388;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important;font-family:Arial}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
> 50 votes
# Jelly, ~~7~~ 6 bytes

```
_/ị“ḃ»

```

~~Typing on phone. Will add description.~~

`(1,0)` goes to `A`, `(0,1)` to `B`, and `(0,0)` to `C`. Arrays in Jelly are 1-based, and the indexing function  works cyclically. Therefore, we can just fold subtraction over the input.

```
_              [vectorized] subtraction
_/             Fold subtraction over the input
   “ḃ»         "ABC" compressed. '»' terminates a compressed string.
  ị            Vectorized cyclic index.

```

Try it here.

# Answer
> 11 votes
# MATL, ~~14~~ 9 bytes

```
2*+ 67w-c

```

Uses current version (10.1.0)

**Try it online!**

## Explanation

**Summary of what the code does**

```
2*       % implicitly input array and multiply it by 2
+        % implicitly input array and add it to the first one
67w-    % subtract from 67
c        % convert to char. Implicitly display

```

**Detailed explanation of how it works**

```
2        % Push number 2 onto the stack
*        % Multiply the top two stack elements. Since there's only one
         % element, this triggers implicit input of a (yet inexistent)
         % element below the existing one. This is the first input array,
         % which will be called "A". Both "A" and number 2 are consumed,
         % and the array 2*A is left on the stack.
+        % Add the top two stack elements. Again, since there's only
         % one element (namely array 2*A) this triggers implicit input
         % of the second array, call it "B". Both 2*A and B are consumed
         % and 2*A+B is left on the stack
         % A blank space is needed after the "+" symbol to prevent it from
         % being interpreted as part of number "+67"
67       % Push number 67 onto the stack. The stack now contains, bottom
         % to top, 2*A+B and 67.
w        % Swap top two elements. The stack now contains 67 and 2*A+B
-        % Subtract top two elements. These are consumed and the result
         % 67-A*B is left on the stack
c        % Convert to char array, interpreting each number as ASCII code.
         % Number 67 corresponds to letter 'C'. Therefore at positions
         % where both arrays A and B were 0 this gives 'C' as result.
         % Where A was 1 and B was 0, i.e. 2*A+B is 2, this gives 'A'.
         % Where A was 0 and B was 1, i.e. 2*A+B is 1, this gives 'B'.
         % The stack contents, namely this char array, are implicitly
         % displayed at the end of the program.

```

# Answer
> 11 votes
# J, 8 bytes

```
'CAB'{~-

```

Usage:

```
   0 0 1 0 0 1 ('CAB'{~-) 0 1 0 1 0 0
CBABCA

```

Try it online here.

# Answer
> 11 votes
## Retina, 44 bytes

```
T`d`BA
B(?=(.)* .*B(?<-1>.)*(?(1)!)$)
C
 .+

```

The trailing linefeed is significant. Input is like

```
001101010 100010100

```

Try it online!

### Explanation

```
T`d`BA

```

Start by turning `0`s into `B` and `1`s into `A`. That makes the first half correct, except that it lists `B` when it should contain `C`. We can identify those erroneous `B`s by checking whether there's a `B` in the same position of the second string:

```
B(?=(.)* .*B(?<-1>.)*(?(1)!)$)
C

```

The lookahead is a classic balancing group counting technique to match up the positions of the two `B`s. The `(.)*` counts the suffix after the first `B` by pushing one capture onto group `1` for each character. Then `(?<-1>.)*` pops from that group again. The `$` ensures that we can reach the end of the string like that, and the `(?(1)!)` ensures that we've actually depleted the entire group.

Finally, we get rid of the separating space and the second string:

```
 .+

```

# Answer
> 11 votes
## Java, 81 bytes

No reputation to comment the already existing Java solution, so here goes:

```
void x(int[]a,int[]b){int j=0;for(int i:a)System.out.printf("%c",67-2*i-b[j++]);}

```

# Answer
> 10 votes
# JavaScript ES6, 36 bytes

```
(a,b)=>a.map((x,y)=>"CBA"[x*2+b[y]])

```

Very simple, and probably obvious enough to understand: Map each item and index in `a` to the char at position (`x*2` \+ item at index `y` in `b`) in `"CBA"`.

# Answer
> 9 votes
# brainfuck, 52 bytes

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

```

Requires an interpreter that lets you go left from cell 0 and has 8-bit wrapping cells. Unlike most of my answers, EOF behaviour doesn't matter.

Takes byte input, with `0xFF` as a delimiter. A stream of bytes representing the first input under "Test cases" would look like this:

```
0x01 0x00 0x00 0x01 0x00 0x00 0x01 0xFF 0x00 0x01 0x00 0x00 0x01 0x00 0x00

```

I could save a couple bytes by having `0x00` as a delimiter and using `0x01` and `0x02` as 0 and 1 respectively, but that felt like cheating :P

Once I figured out my strategy, writing this program was very easy. To find the nth letter to output, start with `0x43` (capital C in ASCII) and subtract ((nth element of first sequence)\*2 + nth element of second sequence)

For what it's worth, here's the 52 byte program split into 3 lines and with some words beside them:

```
Get input until hitting a 255 byte; put a 67 byte to the right of each one
,+[->>----[<--->----],+]

For each 67 byte: Subtract (value to the left)*2 from it
<[<[>--<-]<]

For each byte that used to contain 67: Subtract input and print result
>>[<,[>-<-]>.>>]

```

# Answer
> 9 votes
## Haskell, 29 bytes

```
zipWith(\x y->"BCA"!!(x-y+1))

```

An anonymous function. Use like:

```
>> zipWith(\x y->"BCA"!!(x-y+1)) [1, 0, 0, 1, 0, 0, 1] [0, 1, 0, 0, 1, 0, 0]
"ABCABCA"

```

I tried making the function point-free but got a total mess. *2022 edit: Wheat Wizard found a version for 28 bytes, one shorter than nimi's 29-byte equivalent:*

```
zipWith$(!!).(["CB","AC"]!!)

```

# Answer
> 8 votes
## Pyth, 18 16 10 bytes

**3rd attempt: 10 bytes**

Thank FryAmTheEggman for reminding me of the existence of `G`!

```
VCQ@<G3xN1

```

Input is of the form \[ \[0,0,1,1,0,1,0,1\] , \[1,0,0,0,1,0,1,0\] \], which is essentially a matrix: row for choice and column for question number.

Hand-compiled pythonic pseudocode:

```
              G = "abcdefghijklmnopqrstuvwxyz"    // preinitialized var
VCQ           for N in transpose(Q):    // implicit N as var; C transposes 2D lists
   @<G3           G[:3][                // G[:3] gives me "abc"
       xN1            N.index(1)        // returns -1 if no such element
                  ]

```

---

**2nd attempt: 16 bytes**

```
VCQ?hN\A?.)N\B\C

```

Input is of the form \[ \[0,0,1,1,0,1,0,1\] , \[1,0,0,0,1,0,1,0\] \], which is essentially a matrix: row for choice and column for question number.

This compiles to

```
assign('Q',Pliteral_eval(input()))
for N in num_to_range(Pchr(Q)):
   imp_print(("A" if head(N) else ("B" if N.pop() else "C")))

```

Ok, I know that looks messy, so let's hand-compile to pythonic pseudocode

```
                 Q = eval(input())
VCQ              for N in range transpose(Q): // implicit N as var; transposes 2D lists
   ?hN               if head(N):              // head(N)=1st element of N
      \A                 print("A")           // implicit print for expressions
                     else:
        ?.)N             if pop(N):
            \B               print("B")
                         else:
              \C             print("C")

```

---

**1st attempt: 18 bytes**

```
V8?@QN\A?@Q+8N\B\C

```

With input of the form \[0,0,1,1,0,1,0,1,1,0,0,0,1,0,1,0\], essentially concatenation of two lists. This compiles to

```
assign('Q',Pliteral_eval(input()))
for N in num_to_range(8):
   imp_print(("A" if lookup(Q,N) else ("B" if lookup(Q,plus(8,N)) else "C")))

```

Again, compiling by hand

```
                   Q = eval(input())
V8                 for N in range(8):
  ?@QN                 if Q[N]:
      \A                  print("A")
                       else:
        ?@Q+8N            if Q[N+8]:
              \B              print("B")
                          else:
                \C            print("C")

```

---

And there goes the first codegolf in my life!!! I just learned Pyth yesterday, and this is the first time I ever participated in a code golf.

# Answer
> 7 votes
# Python 3, 39 bytes.

Saved 1 byte thanks to FryAmTheEggman.
Saved 2 bytes thanks to histocrat.

Haven't been able to solve with a one liner in a while!

```
lambda*x:['CBA'[b-a]for a,b in zip(*x)]

```

Here's my test cases. It also shows the way I'm assuming this function is called.

```
assert f([1,0,0,1,0,0,1], [0,1,0,0,1,0,0]) == ['A', 'B', 'C', 'A', 'B', 'C', 'A']
assert f([0, 0, 0, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 0, 0, 0]) == ['B', 'C', 'B', 'C', 'A', 'C', 'A', 'A']
assert f([0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]) == ['C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C']

```

It uses `zip` to iterate through the arrays pairwise, and then indexes into a string to pick the correct letter. This all happens in a list comprehension, so it automagically becomes a list. The core of this solution is that the only possible combinations of `a` and `b` are `[0, 1], [1, 0], [0, 0]`. So if we subtract them, we get one of `-1, 0, 1` which gets us the last, first, middle element respectively.

# Answer
> 7 votes
# Mathematica, ~~30~~ ~~24~~ ~~22~~ 19 bytes

*3 bytes saved due to @alephalpha.*

```
{A,B,C}[[3-2#-#2]]&

```

Quite simple.

# Answer
> 5 votes
# Ruby, 35 bytes

```
->a,b{a.zip(b).map{|x,y|:CAB[x-y]}}

```

Usage:

```
->a,b{a.zip(b).map{|x,y|:CAB[x-y]}}[[1,0,0],[0,1,0]]
=> ["A", "B", "C"]

```

Takes the (x-y)th zero-indexed character of "CAB". (1-0) gives 1, and thus A. (0-0) gives 0, and thus C. (0-1) gives -1, which wraps around to B.

Alternate shorter solution with weirder output:

```
->a,b{a.zip(b){|x,y|p :CAB[x-y]}}

```

Output is quoted strings separated by newlines, which seems a bridge too far somehow.

# Answer
> 4 votes
# Japt, 13 bytes

```
¡#C-X*2-VgY)d

```

Try it online!

### How it works

```
¡#C-X*2-VgY)d  // Implicit: U, V = input lists
¡              // Map each item X and index Y in U to:
 #C-X*2        //  The char code of C (67), minus 2X,
       -VgY)   //  minus the item at index Y in V.
            d  //  Convert to a char code.

```

# Answer
> 4 votes
# TI-BASIC, ~~59~~ ~~57~~ ~~50~~ ~~37~~ 36 bytes

Takes one list from `Ans`, and the other from `Prompt L₁`. Saved 13 bytes thanks to Thomas Kwa's suggestion to switch from branching to `sub(`.

```
Prompt X
For(A,1,dim(∟X
Disp sub("ACB",2+∟X(A)-Ans(A),1
End

```

I'll have to look for what Thomas Kwa said he found in the comments tomorrow. ¯\\\_(ツ)\_/¯

# Answer
> 4 votes
# Rust, 79

Saved 8 bytes thanks to Shepmaster.
Saved 23 bytes thanks to ker.

I'm positive this could be golfed down a lot, but this is my first time writing a full Rust program.

```
fn b(a:&[&[u8]])->Vec<u8>{a[0].iter().zip(a[1]).map(|(c,d)|67-d-c*2).collect()}

```

Here's the ungolfed code and test cases in case anyone wants to try to shrink it.

```
fn b(a:&[&[u8]])->Vec<u8>{
    a[0].iter().zip(a[1]).map(|(c,d)|67-d-c*2).collect()
}
fn main() {
    assert_eq!("ABCABCA", b(&[&[1, 0, 0, 1, 0, 0, 1], &[0, 1, 0, 0, 1, 0, 0]]));
    assert_eq!("BCBCACAA", b(&[&[0, 0, 0, 0, 1, 0, 1, 1], &[1, 0, 1, 0, 0, 0, 0, 0]]));
    assert_eq!("CCCCCCCCCC", b(&[&[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], &[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]));
}

```

The approach is pretty similar to my Python answer. The main difference being that I can't directly index strings, so I can't do the `c-d` trick.

# Answer
> 4 votes
# Octave, 19 bytes

```
@(x,y)[67-y-2*x,'']

```

Test:

```
f([1 0 0 0 1 1],[0 1 0 0 0 0])
ans = ABCCAA

```

I'll add an explanation later when I have a computer in front of me. This was written and tested on octave-online on my cell.

# Answer
> 4 votes
# Vitsy, 40 bytes

*sigh* My baby was not made to do array manipulation.

Expects input through STDIN (something I never do) with a leading `"`.

```
WX&WXl\[68*-1+m]
?68*-2*"C"-i*O?
"B"O?X?
```

Explanation in the (soon available) verbose mode:

```
0:
STDIN;
remove top;
make new stack;
STDIN;
remove top;
push length of stack;
repeat next instruction set top times;
begin recursive area;
push 6;
push 8;
multiply top two;
subtract top two;
push 1;
add top two;
goto top method;
end recursive area;
1:
rotate right a stack;
push 6;
push 8;
multiply top two;
subtract top two;
push 2;
multiply top two;
toggle quote;
push cosine of top; // this is character literal "C"
toggle quote;
subtract top two;
push input item;
multiply top two;
output top as character;
rotate right a stack;
2:
toggle quote;
B;
toggle quote;
output top as character;
rotate right a stack;
remove top;
rotate right a stack;
```

This is getting golfed better real soon, people. I'm so sorry for its current length.

Basically, I treat the input as a string, and then manipulate from there.

Try it online!

# Answer
> 3 votes
## CJam, 10 bytes

```
'Cq~z2fbf-

```

Input as a list of two lists, e.g.

```
[[1 0 0 1 0 0 1] [0 1 0 0 1 0 0]]

```

Test it here.

### Explanation

Treating the pairs as bits of a base-2 number, we get `2` for `A`, `1` for `B` and `0` for `C`.

```
'C  e# Push the character C.
q~  e# Read and evaluate input.
z   e# Transpose the pair of lists to get a list of pairs.
2fb e# Convert each pair from base 2.
f-  e# Subtract each result from the character C.

```

# Answer
> 3 votes
# R ~~29~~ 16 bytes

```
LETTERS[3-2*A-B]

```

removed declaration of function since I saw it's common in other contests.

# Answer
> 3 votes
# Python 3, ~~48~~ 45 bytes

I thought I had an elegant solution, then I saw @Morgan Thrapp's answer...

edit: Saved three bytes thanks to the aforementioned.

```
lambda*x:['A'*a+b*'B'or'C'for a,b in zip(*x)]

```

~~`lambda *x:[a*'A'or b*'B'or'C'for a,b in zip(*x)]`~~

# Answer
> 3 votes
# Java, ~~131~~ ~~122~~ ~~110~~ 90 bytes

EDIT: Thanks to Bifz / FlagAsSpam for the help and inspiration

```
void x(int[]a,int[]b){int j=0;for(int i:a){System.out.print(i>0?"A":b[j]>0?"B":"C");j++;}}

```

~~First submission, naive Java solution. Can almost certainly be improved :)~~

~~```
static String x(int[]a,int[]b){String o="";for(int i=0;i<a.length;i++)o+=a[i]>0?"A":b[i]>0?"B":"C";return(o);}

```~~

# Answer
> 2 votes
## PowerShell, 40 Bytes

```
param($a,$b)$a|%{"CBA"[2*$_+$b[++$d-1]]}

```

Takes input as two explicit arrays, e.g.. `PS C:\Tools\Scripts\golfing> .\cheating-a-multiple-choice-test.ps1 @(1,0,0,1,0,0,1) @(0,1,0,0,1,0,0)`, and stores them in `$a` and `$b`. Next, loop through `$a` with `$a|{...}`. Each loop, we output a character indexed into the string `"CBA"`, with the index decided by twice the current value `$_`, plus the value of `$b` indexed by our helper variable that's been pre-added then subtracted.

As an example, for the first test case, `$a = @(1,0,0,1,0,0,1)` and `$b = @(0,1,0,0,1,0,0)`. The first loop iteration has `$_ = 1`, `$d = $null` (since `$d` hasn't previously been declared). We pre-add to `$d` so now `$_ = 1` and `$d = 1` (in PowerShell, `$null + 1 = 1`), meaning that `$b[1-1] = $b[0] = 0`. Then `2 * 1 + 0 = 2`, so we index `"CBA"[2]`, or `A`.

# Answer
> 2 votes
# R ~~36~~ 34 bytes

```
function(a,b)c('B','C','A')[a-b+2]

```

Two bytes saved removing unnecessary braces

# Answer
> 2 votes
# , 12 chars / 22 bytes

```
Ⓒ…îⓜṃ-$*2-í_

```

`Try it here (Firefox only).`

# Explanation

Translates to Javascript ES6 as

```
String.fromCharCode(...input1.map(($,_)=>67-$*2-input2[_]))

```

# Answer
> 2 votes
# Perl 5 - 47

Already 30 answers and no perl? Here is a naive first attempt then :-) Just the function:

```
sub x{($g,$h)=@_;map{$_?a:$h->[$i++]?b:c}@{$g}}

```

Usage:

```
@f = (0, 0, 0, 0, 1, 0, 1, 1);
@s = (1, 0, 1, 0, 0, 0, 0, 0);

print x(\@f, \@s);

```

I'm pretty sure that something better could be done with regex, but I couldn't find how.

# Answer
> 1 votes
# JavaScript ES6, 75 bytes

I went the extra mile to accept integer arguments instead of array arguments.

```
(a,b)=>[...Array(8)].map((_,n)=>'CBA'[(a&(s=128>>n)*2+b&s)/s]).join('')

```

Explanation:

```
(a,b)=>              // input of two integers representing 8 answers (max value 255 each)
[...Array(8)]        // generates an array with 8 indices that allows .map() to work
.map((_,n)=>         // n is each index 0-7
'CBA'[...]           // reading character from string via index reference
      (...)          // grouping for division
       (a&...)       // AND operator to test if answer is A
          (s=128>>n) // calculating binary index in integer input and storing reference
       *2            // bias index in 'CBA' so truthy is 2 instead of 1
       +(b&s)        // AND operator to test if answer is B
      /s             // divide by binary index to convert AND operators to increments of 1
.join('')            // convert to string without commas

```

Credit to @ETHproductions for string indexing logic.

### Test Here

```
f=(a,b)=>[...Array(8)].map((_,n)=>'CBA'[((a&(s=128>>n))*2+(b&s))/s]).join('');

console.log(f(0b01001001, 0b00100100));
console.log(f(0b00001011, 0b10100000));
console.log(f(0b00000000, 0b00000000));
```

```
<!-- results pane console output; see http://meta.stackexchange.com/a/242491 -->
<script src="http://gh-canon.github.io/stack-snippet-console/console.min.js"></script>
```

### Pssst

For 3 extra bytes, it can display the representation for up to 30 answers:

```
(a,b)=>[...Array(30)].map((_,n)=>'CBA'[((a&(s=1<<30>>n))*2+(b&s))/s]).join('')

```

# Answer
> 1 votes
# Retina, 46 bytes

```
^
%
+`%(.)(.* )(.)
$1$3,%$2
10
A
01
B
00
C
\W
[empty line]

```

Merges the two strings and chooses the letters according to the digit pairs.

Try it online here.

# Answer
> 1 votes
# Lua, 87 Bytes

Simply testing the values in the arrays, and concatenating `A`, `B` or `C`.

```
function f(a,b)s=""for i=1,#a do s=s..(0<a[i]and"A"or 0<b[i]and"B"or"C")end print(s)end

```

# Answer
> 1 votes
## F#, 33 bytes

```
Seq.map2(fun a b->67-a*2-b|>char)

```

That's a partially applied function that takes two int sequences - two arrays work fine - and returns a new sequence of characters representing the correct answers. =)

# Answer
> 1 votes
## Seriously, 14 bytes

```
,,Z`i-"CBA"E`M

```

Try It Online

Probably due to a bug in the safe mode version of the interpreter, you must add an `X` to get it to work right in the online version. Download the local version to get the above program working correctly as-is.

It's too short to warrant a full explanation, so I'll just say: it uses the same algorithm as the Jelly answer.

# Answer
> 1 votes
# PARI/GP, 45 bytes

This uses the multiif support from version 2.6.0.

```
f(u,v)=vector(#v,i,if(u[i],"A",v[i],"B","C"))

```

# Answer
> 1 votes
# C, 52 bytes

```
F(a,b,n){while(n--)putchar(a>>n&1?65:b>>n&1?66:67);}

```

The sequences of bits are interpreted as big-endian (MSB is the first answer), the third parameter `n` indicates the number of answers encoded.

Test main:

```
int main() {
  F(73, 36, 7);
  putchar('\n');
  F(11, 160, 8);
  putchar('\n');
  F(0, 0, 10);
  putchar('\n');
}

```

# Answer
> 1 votes
## Clojure, 41 bytes

**(52 if a sequence of chars is not a permitted output format)**

Finally a semi-cryptic Clojure answer :D Output as a sequence of characters:

```
#(map(fn[a b](or({1\A}a)({1\B}b)\C))% %2)

```

This version outputs a string:

```
#(apply str(map(fn[a b](or({1\A}a)({1\B}b)\C))% %2))

```

`{1 \A}` is a "dictionary" with key `1` and value character `A`. `({1 \A} a)` returns `\A` if `a` is `1` and `nil` otherwise, same logic for `b`. `or` takes the first "truthy" value, which is `\C` if both `a` and `b` are zero.

# Answer
> 1 votes
# Vyxal `d`, 10 bytes

```
~+†W∩vTkAİ

```

Try it Online!

---
Tags: code-golf, array, bitwise
---


title: Is it shuffled FizzBuzz?

text:
# Question
Title: Is it shuffled FizzBuzz?
A twin of this.

FizzBuzz is where a range of positive integers is taken, and numbers divisible by 3 are replaced with "Fizz", divisible by 5 with "Buzz" and divisible by 15 with "FizzBuzz". For example, FizzBuzz from 1 to 10 is `1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz`.

Your challenge is to, given a list of Fizzes, Buzzes, FizzBuzzes and a value representing an integer (I'm going to use Int), determine if it can be arranged into valid FizzBuzz.

For example, `Int, Fizz, Fizz, Buzz` can be arranged into `Fizz, Buzz, Int, Fizz` (for example 9,10,11,12) which is valid. But `Buzz, Fizz, Buzz` cannot, as the two `Buzz` need to be five values apart.

You may choose any four values to represent Fizz, Buzz, FizzBuzz and Int.

This is , shortest wins!

## Truthy

```
Int, Int, Fizz
Fizz, Int, Fizz, Buzz
Fizz, Fizz, Fizz, Int, Int, Int, Buzz
Buzz, Int, Int, Int, Fizz, FizzBuzz
FizzBuzz, Int, Int, Int, Int

```

## Falsy

```
Buzz, FizzBuzz, Fizz
Buzz, Fizz, Buzz
Int, Int, Int
Fizz, Int, Fizz
FizzBuzz, Int, Int, Buzz, Fizz
Int, Int, Fizz, Fizz, Fizz, Buzz, Buzz

```

# Answer
> 4 votes
# Vyxal, 13 bytes

```
L₄+v₍₃₅ÞS?Ṗ↔ḃ

```

Try it Online! Super slow. Uses `[0,0]` for `Int`, `[1,0]` for `Fizz`, `[0,1]` for `Buzz`, and `[1,1]` for `FizzBuzz`.

Test cases, using 14 instead of 26 to make it faster.

```
L₄*v₍₃₅ÞS?Ṗ↔ḃ
L₄+           # Length of input + 26 (14 would be enough, but 26 is one byte)
   v₍₃₅       # For each in range [1, that], calculate [n % 3 == 0, n % 5 == 0]
       ÞS     # All sublists
           ↔  # Keep only lists that are in...
         ?Ṗ   # The permutations of the input
            ḃ # Is this truthy? (does it have at least one element?)

```

# Answer
> 3 votes
# JavaScript (ES6), 72 bytes

Expects `0` for *Int*, `1` for *Fizz*, `2` for *Buzz*, `3` for *FizzBuzz*. Returns `0` or `1`.

This is the same algorithm as in my answer to the other challenge.

```
f=(a,i=k=15)=>k--&&a.sort().map(_=>++i%3<1|2*!(i%5)).sort()+''==a|f(a,k)

```

Try it online!

### Commented

```
f = (             // f is a recursive function taking:
  a,              //   a[] = input array
  i =             //   i = index in the FizzBuzz sequence
  k = 15          //   k = counter
) =>              //
  k-- &&          // decrement k; abort if it was 0
  a.sort()        // normalize a[] by sorting it in lexicographical order
  .map(_ =>       // for each value in a[]:
    ++i % 3 < 1 | //   generate the FizzBuzz sequence,
    2 * !(i % 5)  //   starting at i + 1
  )               // end of map()
  .sort()         // normalize this new array
  + '' == a |     // coerce it to a string and compare it with a[]
  f(a, k)         // recursive call with i set to the new value of k

```

# Answer
> 2 votes
# Python3, 213 bytes:

```
def v(r,l,k=[]):
 if not r:yield k
 for i,a in enumerate(l):
  if r[0]%(a|1)<1:yield from v(r[1:],l[:i]+l[i+1:],k+[a])
def f(l,c=0):
 while(c:=c+1)<sum(i**2for i in l):
  if next(v(range(c,c+len(l)),l),0):return 1

```

Try it online!

# Answer
> 2 votes
# 05AB1E, 15 bytes

```
g°L35SδÖŒεœ€Q}à

```

Inputs as Int=`[0,0]`; Fizz=`[1,0]`; Buzz=`[0,1]`; FizzBuzz=`[1,1]`.
Too slow to output anything on TIO..

(Don't) try it online.
Try a modified version online, with: hard-coded 26  instead of ; find\_first  instead of `ε...}`; outputs the first found list, or -1 if falsey (which still times out for falsey or too long test cases.. -\_-).

**Explanation:**

```
g             # Push the input-length
 °            # 10 to the power this length
  L           # Pop and push a list in the range [1,10**length]
   35S        # Push pair [3,5]
      δ       # Map over the [1,10**length]-list, with [3,5] as argument for each:
       Ö      #  Check if the current integer is divible by [3,5]
        Œ     # Get all sublists of this
         ε    # Map over each sublist:
          œ   #  Get all permutations of it
           €  #  Map over each permutation:
            Q #   Check if it's equal to the (implicit) input-list
         }    # Close the sublists-map
          à   # Flattened maximum to check if any inner permutation was truthy
              # (which is output implicitly as result)

```

# Answer
> 1 votes
# Python 3.8 (pre-release), 109 bytes

```
lambda n:sorted(n)in[sorted([max(a for a in[1,3,5,15]if j%a<1)for j in range(i,i+len(n))])for i in range(15)]

```

Try it online!

Takes `Int` as `1`, `Fizz` as `3`, `Buzz` as `5`, `FizzBuzz` as `15`.

## Explanation

One key observation is that, if we replace all the integers with a single value `Int`, then the FizzBuzz sequence has a period of 15:

```
Int
Int
Fizz
Int
Buzz
Fizz
Int
Int
Fizz
Buzz
Int
Fizz
Int
Int
FizzBuzz

```

It is rather easy to prove that this is in fact the case. *Hint: start by placing the multiples of 3 and 5.*

What we can therefore do is focus on the first 15 numbers. From each of these numbers, we can make a little subsequence of numbers whose length is the same as the length of the input, and determine whether the sorted values (where the integers become `Int`) are the same as the input.

How do we do this? We use a cool trick whereby we get the maximum number out of `[1, 3, 5, 15]` such that the current number is divisible by that number. Since `Int` is `1`, all numbers that are not multiples of 3 or 5 correspond to `Int`. Multiples of 3 but not of 5 correspond to `Fizz`, etc. We can eventually generate this sequence of 1s, 3s, 5s and 15s.

Sorting the input and comparing it against the sorted values of the subsequence will reveal whether the input is shuffled FizzBuzz or not.

*Yay! First answer in... what, two months?*

---
Tags: code-golf, decision-problem, fizzbuzz
---


title: Nest some addition

text:
# Question
Title: Nest some addition
Lambda calculus is a system of computation based on single-argument functions; everything in it is such a function. Due to this functional nature, juxtaposition is commonly used to denote function application, grouped from left to right. For example, \\$(f g) h=f g h\\$ denotes what would conventionally be written \\$(f(g))(h)=f(g)(h)\\$.

Church numerals are a way of encoding the nonnegative integers in this system. They are defined as follows:
\\$\begin{align\*} \overparen{\underparen0} f &= \operatorname{id}\\ \overparen{\underparen 1} f &= f\circ\left(\overparen{\underparen 0} f\right)=f\\ \overparen{\underparen 2} f &= f\circ\left(\overparen{\underparen 1} f\right)=f\circ f\\ \vdots\\ \overparen{\underparen n} f &= f\circ\left(\overparen{\underparen{n-1}} f\right)\\ &=\underbrace{f\circ\cdots\circ f}\_n, \end{align\*}\\$
where \\$\circ\\$ denotes function composition. In other words, the Church numeral \\$\overparen{\underparen n}\\$ can be seen as a unary operator on a function \\$f\\$ that nests that function \\$n\\$ times.

From here, we can define a binary operator (with two curried arguments) that performs addition on two Church numerals:
\\$\begin{align\*} \operatorname{add} \overparen{\underparen a} \overparen{\underparen b} f&= \overparen{\underparen{a+b}} f\\ &= \left(\overparen{\underparen a} f\right)\circ\left(\overparen{\underparen b} f\right). \end{align\*}\\$
That is, we nest \\$f\\$ \\$b\\$ times, then another \\$a\\$ times.

By definition, \\$\operatorname{add} \overparen{\underparen a}\\$ is a unary operator that, when applied to another Church numeral \\$\overparen{\underparen b}\\$, results in \\$\overparen{\underparen{a+b}}\\$. But what happens when we reverse the order, i.e. attempt to evaluate \\$\overparen{\underparen a}\operatorname{add}\\$? This resulting function has arity \\$a+1\\$, needed to expand out all the \\$\operatorname{add}\\$s in \\$\underbrace{\operatorname{add}\circ\cdots\circ\operatorname{add}}\_a\\$.

## Task

Given (optionally) an integer \\$a\ge0\\$, and another \\$a+1\\$ integers \\$x\_0,x\_1,...,x\_a\ge0\\$, compute the integer \\$n\\$ such that \\$\overparen{\underparen n}=\overparen{\underparen a} \operatorname{add} \overparen{\underparen{x\_0}} \overparen{\underparen{x\_1}}...\overparen{\underparen{x\_a}}\\$.

You probably will also need to know the multiplication and exponentiation rules:
\\$\begin{align\*} \overparen{\underparen{a\times b}} f&=\overparen{\underparen a} \left(\overparen{\underparen b} f\right)=\left(\overparen{\underparen a}\circ\overparen{\underparen b}\right)f\\ \overparen{\underparen{a^b}} f &= \overparen{\underparen b} \overparen{\underparen a} f. \end{align\*}\\$

### Example

Take \\$\overparen{\underparen 2} \operatorname{add} \overparen{\underparen 3} \overparen{\underparen 4} \overparen{\underparen 5}\\$:
\\$\begin{align\*} \overparen{\underparen 2}\operatorname{add}\overparen{\underparen 3} \overparen{\underparen 4} \overparen{\underparen 5}&=(\operatorname{add}\circ\operatorname{add})\overparen{\underparen 3} \overparen{\underparen 4} \overparen{\underparen 5}\\ &=\operatorname{add}\left(\operatorname{add}\overparen{\underparen 3}\right)\overparen{\underparen4} \overparen{\underparen5}\\ &=\left(\operatorname{add}\overparen{\underparen 3} \overparen{\underparen 5}\right)\circ\left(\overparen{\underparen 4} \overparen{\underparen 5}\right)\\ &=\overparen{\underparen 8}\circ\overparen{\underparen{5^4}}\\ &=\overparen{\underparen{5000}} \end{align\*}\\$

### Test cases

```
a   x           result
0   9           9
1   2,2         4
2   2,2,2       16
2   3,4,5       5000
2   7,1,8       120
3   1,4,1,5     30
3   2,2,2,2     4608
3   2,3,2,4     281483566645248

3   2,3,4,5     46816763546921983271558494138586765699150233560665204265260447046330870022747987917186358264118274034904607309686036259640294533629299381491887223549021168193900726091626431227545285067292990532905605505220592021942138671875
3   3,3,3,3     3381391913524056622394950585702085919090384901526970
4   2,2,2,2,2   120931970555052596705072928520380169054816261098595838432302087385002992736397576837231683301028432720518046696373830535021607930239430799199583347578199821829289137706033163667583538222249294723965149394901055238385680714904064687557155696189886711792068894677901980746714312178102663014498888837258109481646328187118208967028905569794977286118749919370644924079770214106530314724967825243764408114857106379963213188939126825992308882127905810306415158057997152747438230999039420121058243052691828798875998809865692983579259379718938170860244860482142976716892728044185832972278254093547581276129155886886086258355786711680193754189526351391221273418768272112491370597004152057820972058642174713955967404663467723362969481339278834627772126542657434779627861684834294203455419942997830922805201204107013187024101622800974572717408060065235993384198407691177770220323856866020553151446293957513282729090810520040166215232478427409757129336799823635731192497346452409939098243738098803206142762368603693303505732137119043739898807303126822830794424748280315330250324436290184499770851474706427973859450612731909450625705188122632367615184044521656851538649088840328591879043950831910516712687721046964100635071310295009799499919213218249505904439261442688728313586685099505945191069266179018225279933007599239168

```

# Answer
> 7 votes
# Flurry, 28 bytes

```
({}){{}{}}[{}{<><<>(){}>}]{}

```

A language based on untyped lambda calculus is certainly the right tool here :)

Takes input in the order of `xa xa-1 ... x1 x0 a`, and evaluates to the Church value of the required expression.

```
({})      pop a; evaluate to a; push back a
{{}{}}    \x. x (pop), which takes a function and applies one item from stack
          a (\x. x (pop)) [...] evaluates to [...] x0 x1 ... xa-1
[{}       the expression (a add)
   {<><<>(){}>}  add = \x. S (S . K . x)
]
          so far, the result is (a add x0 x1 ... xa-1)
{}        finally, pop xa and apply to the above

```

Test script:

```
Compare-Object (.\Flurry.exe -nin src.txt 9 0) 9
Compare-Object (.\Flurry.exe -nin src.txt 2 2 1) 4
Compare-Object (.\Flurry.exe -nin src.txt 2 2 2 2) 16
Compare-Object (.\Flurry.exe -nin src.txt 5 4 3 2) 5000
Compare-Object (.\Flurry.exe -nin src.txt 8 1 7 2) 120
Compare-Object (.\Flurry.exe -nin src.txt 5 1 4 1 3) 30
Compare-Object (.\Flurry.exe -nin src.txt 2 2 2 1 3) 4352
Compare-Object (.\Flurry.exe -nin src.txt 2 2 2 0 3) 4096
Compare-Object (.\Flurry.exe -nin src.txt 2 2 2 2 3) 4608

```

# Answer
> 6 votes
# Haskell, 54 bytes

```
x#y|(a,b)<-foldl(\(a,b)c->(c^b,(c^b)^a))(0,1)y=(x+a)*b
```

Attempt This Online!

Takes input as \\$x\_0 \\# \[x\_1,\dots,x\_a\]\\$.

---

Abusing the notation, we have:

\\$0 \operatorname{add} x\_0 = x\_0 = (x\_0 + 0) \times 1\\$.

If we have

\\$(n-1) \operatorname{add} x\_0 \cdots x\_{n-1} = (x\_0 + a\_{n-1}) \times b\_{n-1}\\$,

then:

\\$\begin{align} n \operatorname{add} x\_0 \cdots x\_n &= (n-1) \operatorname{add} (\operatorname{add} x\_0) x\_1 \cdots x\_{n-1} x\_n \\ &= (((\operatorname{add} x\_0) + a\_{n-1}) \times b\_{n-1}) x\_n \\ &= ((\operatorname{add} (\operatorname{add} x\_0) a\_{n-1}) \circ b\_{n-1}) x\_n \\ &= \operatorname{add} (\operatorname{add} x\_0) a\_{n-1} (b\_{n-1} x\_n) \\ &= (\operatorname{add} x\_0 (b\_{n-1} x\_n)) \circ (a\_{n-1} (b\_{n-1} x\_n)) \\ &= (x\_0 + {x\_n}^{b\_{n-1}}) \times ({x\_n}^{b\_{n-1}})^{a\_{n-1}} \\ &= (x\_0 + a\_n) \times b\_n \end{align} \\$

where:

\\$a\_n = {x\_n}^{b\_{n-1}}, b\_n = ({x\_n}^{b\_{n-1}})^{a\_{n-1}}\\$.

# Answer
> 3 votes
# PARI/GP, 47 bytes

```
x->[[a,b]=[t=c^b,t^a]|c<-x[^b=!a=0]];(x[1]+a)*b
```

Attempt This Online!

A port of my Haskell answer. Takes input as \\$\[x\_0,x\_1,\dots,x\_n\]\\$.

# Answer
> 3 votes
# Lambda calculus, 51 characters (or 73 bits)

The function takes two arguments (in curried form as usual): the first argument is `a` as a Church numeral, and the second argument is a list of Church numerals.

```
\a\l l(\h\t\f t(f h))(\f f)(a(\m\n\f\x m f(n f x)))

```

Or in the binary lambda calculus encoding:

```
0000010101100000000111001101110001001110000000000101111101100101111011010

```

In lambda calculus, the standard representation of a list is: e.g. the list \[a, b, c\] is represented by \\$\lambda x . \lambda y . x~a~(x~b~(x~c~y))\\$. (As a mnemonic, I like to think of the case where \\$x = \mathrm{cons}\\$ and \\$y = \mathrm{nil}\\$.) In other words, in lambda calculus, a list *is* its "fold-right" operation.

Now, if we have a list \\$l\\$, the expression \\$l ~ (\lambda h . \lambda t . \lambda f . t ~ (f ~ h)) ~ (\lambda f . f)\\$ builds up an "apply" operation. For example, in the case \\$l = \[a, b, c\]\\$, it evaluates to \\$\lambda f . f ~ a ~ b ~ c\\$. (To see this, for example: $$ \[a, b, c\] (\lambda h . \lambda t . \lambda f . t ~ (f ~ h)) ~ (\lambda f . f) = \\ (\lambda h . \lambda t . \lambda f . t ~ (f ~ h)) ~ a ~ (\[b, c\] (\lambda h . \lambda t. t ~ (f ~ h)) ~ (\lambda f . f)) = \\ (\lambda h . \lambda t . \lambda f . t ~ (f ~ h)) ~ a ~ (\lambda f . f ~ b ~ c) = \\ \lambda f . ((\lambda f . f ~ b ~ c) (f ~ a)) = \\ \lambda f . f ~ a ~ b ~ c$$ where from the second line to the third we applied an inductive hypothesis on the case \\$l = \[b, c\]\\$. For the base case, the empty list is \\$l = \[\] = \lambda x . \lambda y . y\\$, so \\$l ~ (\lambda h . \lambda t . \lambda f . t ~ (f ~ h)) ~ (\lambda f . f) = \lambda f . f\\$. Alternatively, you can see this as a special case of how in general you would write a fold-left operation on lists in terms of the fold-right operation.)

From here, what we want is simply: \\$\lambda a . \lambda l . \mathrm{apply} ~ (a ~ \mathrm{add}) ~ l\\$. Substituting \\$\mathrm{apply} = \lambda f . \lambda l . l (\lambda h . \lambda t . \lambda f . t ~ (f ~ h)) ~ (\lambda f . f) ~ f\\$, and \\$\mathrm{add} = \lambda m . \lambda n . \lambda f . \lambda x . m ~ f ~ (n ~ f ~ x)\\$ gives the final expression above.

# Answer
> 2 votes
# JavaScript (Node.js),  ~~65~~  56 bytes

*Saved 7 bytes thanks to @tsh*

This is really just a port of alephalpha's algorithm.

Expects `(n)(x)`, where `x` is an array of BigInts.

```
x=>x[x.map((v,i)=>[a,b]=i?[v**=b,v**a]:[0n,1n]),0]*b+a*b

```

Try it online!

Or **54 bytes** without BigInts:

```
x=>x[x.map((v,i)=>[a,b]=i?[v**=b,v**a]:[0,1]),0]*b+a*b

```

Try it online!

---
Tags: code-golf, lambda-calculus
---


title: Fix my FizzBuzz

text:
# Question
Title: Fix my FizzBuzz
FizzBuzz is where a range of positive integers is taken, and numbers divisible by 3 are replaced with "Fizz", divisible by 5 with "Buzz" and divisible by 15 with "FizzBuzz".

I've got some FizzBuzz output here. Unfortunately, it's been shuffled:

```
4
Fizz
Fizz
Buzz
2

```

A bit of logic shows us that this is `2, Fizz, 4, Buzz, Fizz` shuffled.

Your challenge is to take a range of FizzBuzz, shuffled, and put it in any order such that it's valid FizzBuzz. For example, given `Fizz, Fizz, Buzz, 11` we can work out that the correct order is `Fizz, Buzz, 11, Fizz` (corresponding to `9, 10, 11, 12`)

Input will always be rearrangeable into valid FizzBuzz.

You may choose any values that cannot appear as integers to represent Fizz, Buzz and FizzBuzz.

This is , shortest wins!

## Testcases

```
1, 2, Fizz, 4, Buzz -> 1, 2, Fizz, 4, Buzz
Fizz, 4, Buzz, 1, 2 -> 1, 2, Fizz, 4, Buzz
Fizz, Fizz, Buzz, 11 -> Fizz, Buzz, 11, Fizz
Fizz, Buzz, 8, Buzz, 7, Fizz -> Buzz, Fizz, 7, 8, Fizz, Buzz
Buzz, Fizz -> either way
29, 31, FizzBuzz -> 29, FizzBuzz, 31
28, Fizz, FizzBuzz, 29 -> Fizz, 28, 29, FizzBuzz
8, 7 -> 7, 8

```

# Answer
> 11 votes
# Vyxal, ~~21~~ 15 bytes

```
ṖÞ∞ƛ₍₃₅T∨;ÞS$↔h

```

Try it Online!

Why use clever mathematics when you can just generate infinite FizzBuzz?

*-6 thanks to Steffan and emanresuA*

## Explained

```
ṖÞ∞ƛ₍₃₅T∨;ÞS$↔h
Ṗ                # All permutations of the input
 Þ∞              # An infinite list of positive integers starting at 1
   ƛ     ;       # To each number n:
    ₍₃₅          #   [n % 3 == 0, n % 5 == 0]
       T         #   Truthy indices of that
        ∨        #   Logical or that with the number. This gets either the indices of where Fizz or Buzz would usually be or n
         ÞS      # Sublists of the infinite fizzbuzz
           $↔    # Remove sublists which don't have everything from the input
             h   # Get the first item of that

```

# Answer
> 6 votes
# , 54 bytes

```
(-:&(/:~)"1#])#]\1((,~{~0=])2-@#.0=5 3|])@+#i.@+9>.>./

```

Try it online!

\_1, \_2, \_3 represent Fizz, Buzz, FizzBuzz.

* Generate all integers from 1 to `<list length>` \+ max(9, `<max value>`)
* Fizz Buzz them
* Sliding window across them of size `<list len>`
* Find ones which set equal the input

# Answer
> 3 votes
# JavaScript (ES6), 82 bytes

*Saved 2 bytes thanks to a suggestion by @emanresuA*

Expects and returns `-1` for *Fizz*, `-2` for *Buzz*, `-3` for *FizzBuzz*.

```
f=(a,i=k=0)=>[...b=a.sort().map(_=>-!(++i%3)-2*!(i%5)||i)].sort()+''==a?b:f(a,++k)

```

Try it online!

The underlying algorithm is the same as in my answer to the twin challenge.

# Answer
> 3 votes
# Charcoal, 55 bytes

```
ＷＳ⊞υι⮌⊟ΦＥ⁷ＥＥυ⁻⁺⌈ＥυΣ⁺ψνκμ∨⁺⎇﹪λ³ωFizz⎇﹪λ⁵ωBuzzＩλ⬤ι⁼№ιλ№υλ

```

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

```
ＷＳ⊞υι

```

Input the shuffled range.

```
⌈ＥυΣ⁺ψν

```

Calculate the largest integer in the range.

```
Ｅυ⁻⁺...κμ

```

Calculate a descending range of integers starting with that integer, but also offset by the outer loop index (see below).

```
Ｅ...∨⁺⎇﹪λ³ωFizz⎇﹪λ⁵ωBuzzＩλ

```

Calculate the FizzBuzz output for that range.

```
⮌⊟ΦＥ⁷...⬤ι⁼№ιλ№υλ

```

Calculate 7 ranges sliding up by 1 each time, and output one which matches the input, reversing it to put it back into order. (7 is needed for the edge case of `Buzz Fizz`.)

37 bytes for a boring numeric version:

```
Ｉ⮌⊟ΦＥ⁷ＥＥθ⁻⁺⌈θκμ∨±⁺¬﹪λ³⊗¬﹪λ⁵λ⬤ι⁼№ιλ№θλ

```

Try it online! Link is to verbose version of code. Uses `-1` for Fizz, `-2` for Buzz and `-3` for Fizzbuzz.

# Answer
> 2 votes
# 05AB1E, 28 bytes

```
∞εD35SÖƶ(O‚0Kθ}Ig„üÿ.V.Δ{I{Q

```

Not too happy about this.. I have the feeling this can be a lot shorter.. :/

Try it online or verify all test cases.

**Explanation:**

```
∞               # Push the infinite positive list: [1,2,3,...]
 ε              # Map each value to:
  D             #  Duplicate the current value
   35S          #  Push pair [3,5]
      Ö         #  Check if the value is divisible by 3 and/or 5
       ƶ        #  Multiply the check by their 1-based index
        (       #  Negate them
         O      #  Sum them (-1 if only divisible by 3; -2 if only 5; -3 if both;
                #  0 if neither)
          ‚     #  Pair it with the current value
           0K   #  Remove all 0s
             θ  #  Pop and keep the last value
 }              # Close the map
  Ig            # Push the length of the input-list
    „üÿ         # Push string "ü<length>"
       .V       # Evaluate and execute it as 05AB1E code,
                # `ün` created overlapping lists of size `n`
         .Δ     # Then find the first which is truthy for:
           {    #  If it's sorted
              Q #  is equal to
            I{  #  the sorted input-list

```

# Answer
> 2 votes
# Python 3.8 (pre-release), 149 bytes

```
lambda a,e=enumerate:{p for p in permutations(a)if all(j in(l:=k+i-n,-(l%3<1)-2*(l%5<1))for k,j in e(p)for n,i in e(p)if i>0)}
from itertools import*

```

Try it online!

Uses `-1` for `Fizz`, `-2` for `Buzz` and `-3` for `FizzBuzz`.

Returns all possible options.

The idea is to try all permutations and then, for each permutation, find the first integer in the list and check if the rest of the list agrees with that one.

# Answer
> 1 votes
# Python3, 276 bytes:

```
def v(r,l,k=[]):
 if any([r,l])==0:yield k;return
 for i,a in enumerate(l):
  if a==r[0]or(type(a)==str and r[0]%{'Fizz':3,'Buzz':5,'FizzBuzz':15}[a]==0):yield from v(r[1:],l[:i]+l[i+1:],k+[a])
def f(l):
 c=0
 while(c:=c+1):
  if(V:=next(v([*range(c,c+len(l))],l),0)):return V

```

Try it online!

---
Tags: code-golf, string, sorting, fizzbuzz
---


title: Which R version is it? It's Peanuts!

text:
# Question
Title: Which R version is it? It's Peanuts!
This challenge will be based on an R language trivia: every release is named and it's a reference to Peanuts comic strips (see here and here).

## Task

Given a release name, output its number.

For reference, use the below list:

```
Great Pumpkin            2.14.0
December Snowflakes      2.14.1
Gift-Getting Season      2.14.2
Easter Beagle            2.15.0
Roasted Marshmallows     2.15.1
Trick or Treat           2.15.2
Security Blanket         2.15.3
Masked Marvel            3.0.0
Good Sport               3.0.1
Frisbee Sailing          3.0.2
Warm Puppy               3.0.3
Spring Dance             3.1.0
Sock it to Me            3.1.1
Pumpkin Helmet           3.1.2
Smooth Sidewalk          3.1.3
Full of Ingredients      3.2.0
World-Famous Astronaut   3.2.1
Fire Safety              3.2.2
Wooden Christmas-Tree    3.2.3
Very Secure Dishes       3.2.4
Very, Very Secure Dishes 3.2.5
Supposedly Educational   3.3.0
Bug in Your Hair         3.3.1
Sincere Pumpkin Patch    3.3.2
Another Canoe            3.3.3
You Stupid Darkness      3.4.0
Single Candle            3.4.1
Short Summer             3.4.2
Kite-Eating Tree         3.4.3
Someone to Lean On       3.4.4
Joy in Playing           3.5.0
Feather Spray            3.5.1
Eggshell Igloo           3.5.2
Great Truth              3.5.3
Planting of a Tree       3.6.0
Action of the Toes       3.6.1
Dark and Stormy Night    3.6.2
Holding the Windsock     3.6.3
Arbor Day                4.0.0
See Things Now           4.0.1
Taking Off Again         4.0.2
Bunny-Wunnies Freak Out  4.0.3
Lost Library Book        4.0.4
Shake and Throw          4.0.5
Camp Pontanezen          4.1.0
Kick Things              4.1.1
Bird Hippie              4.1.2
One Push-Up              4.1.3
Vigorous Calisthenics    4.2.0

```

## Rules

* You may take input and output in any reasonable format (for output this includes a dot delimited string (as above), a string with other delimiter, a 3-element list etc.).
* This is - usual rules apply.

# Answer
> 15 votes
# JavaScript (Node.js), 174 bytes

Returns a triplet \\$\[a,b,c\]\\$.

```
s=>[(n=Buffer("1M1rb2dX~N(jm8+2p~aL2fw[k~_)1F1sT2q3VSGx^~R7H~ue.v/~ytY2U~gl~O1W|6*3I5`2Z".replace(/\d/g,n=>10**n))[parseInt(s[9]+s,36)%901%126]+56)/42|0,n/6%7^13*(n<105),n%6]

```

Try it online!

### Encoding

Here is the uncompressed lookup string.

Each version is encoded as a single character in the printable ASCII ranges \\$\[40\dots48\]\\$ and \\$\[70\dots124\]\\$. The first range is for 2.x.x and the second one for 3.x.x and 4.x.x.

The padding character in the lookup string is `~`. Runs of 2 to 10 consecutive `~` are replaced with `1` to `9`.

**Note**: We actually don't use `~` when decompressing. Each digit \\$k\\$ is instead expanded to \\$10^k\\$ (a `1` followed by \\$k\\$ `0`'s). And that's why the sub-string `R~~~~~0~~H`, which includes a meaningful `0`, can be compressed as `R7H`, saving 2 more bytes.

To summarize:

| ASCII Range | Character range | Meaning |
| --- | --- | --- |
| 40 - 48 | `(` to `0` | version 2.x.x |
| 49 - 57 | `1` to `9` | compressed padding string |
| 70 - 124 | `F` to `|` | version 3.x.x or 4.x.x |
| 126 | `~` | single padding character |

To turn a character \\$C\\$ into the version triplet \\$\[a,b,c\]\\$, we compute \\$n=\operatorname{ord}(C)+56\\$ and then:

$$\begin{align}&a=\lfloor n/42\rfloor\\ &b=\cases{ \lfloor n/6\rfloor\bmod7&if $n\ge105$\\ \left(\lfloor n/6\rfloor\bmod7\right)\operatorname{xor}13&if $n\<105$ }\\ &c=n\bmod6\end{align}$$

---
Tags: code-golf, string, r
---


title: Is it a Giuga number?

text:
# Question
Title: Is it a Giuga number?
Giuga numbers (A007850) are composite numbers \\$n\\$ such that, for each prime factor \\$p\_i\\$ of \\$n\\$, \\$p\_i \mid \left( \frac n {p\_i} -1 \right)\\$. That is, that for each prime factor \\$p\_i\\$, you can divide \\$n\\$ by the factor, decrement it and the result is divisible by \\$p\_i\\$

For example, \\$n = 30\\$ is a Giuga number. The prime factors of \\$30\\$ are \\$2, 3, 5\\$:

* \\$\frac {30} 2 - 1 = 14\\$, which is divisible by \\$2\\$
* \\$\frac {30} 3 - 1 = 9\\$, which is divisible by \\$3\\$
* \\$\frac {30} 5 - 1 = 5\\$, which is divisible by \\$5\\$

However, \\$n = 66\\$ isn't, as \\$\frac {66} {11} - 1 = 5\\$ which is not divisible by \\$11\\$.

The first few Giuga numbers are \\$30, 858, 1722, 66198, 2214408306, ...\\$

---

Given a positive integer \\$n\\$, determine if it is a Giuga number. You can output either:

* Two distinct, consistent values to indicate whether \\$n\\$ is a Giuga number or not (e.g `True`/`False`, `1`/`0`, `5`/`"abc"`)
* Two classes of values, which are naturally interpreted as truthy and falsey values in your language (e.g. `0` and non-zero integers, and empty vs non-empty list etc.)

Additionally, you may choose to take a black box function \\$f(x)\\$ which returns 2 distinct consistent values that indicate if its input \\$x\\$ is prime or not. Again, you may choose these two values.

This is , so the shortest code in bytes wins.

---

## Test cases

```
   1 -> 0
  29 -> 0
  30 -> 1
  66 -> 0
 532 -> 0
 858 -> 1
1722 -> 1
4271 -> 0

```

# Answer
# Jelly, 8 bytes

```
Æfḟɓ÷’ọȦ

```

Try it online!

This version is mostly caird's, and I merged one of my golfs into it. Posted with their permission.

```
Æfḟɓ÷’ọȦ    Main Link
Æf          Take the prime factors
  ḟ         And filter out the original (if x is prime, this list is empty, otherwise, nothing changes)
   ɓ----    Call this chain dyadically with reversed arguments: x on the left, factors on the right
    ÷       Divide x by each factor
     ’      Decrement each quotient
      ọ     Count divisibility of each result by the corresponding factor
       Ȧ    Are any and all truthy? That is, the list is all truthy and is not empty

```

This was my original solution:

# Jelly, 9 bytes

```
:’ọɗÆfȦ>Ẓ

```

Try it online!

Gives `1` for Guiga numbers and `0` otherwise.

```
:’ọɗÆfȦ>Ẓ    Main Link (monadic)
---ɗ         Last three links as a dyad
    Æf       Monad - get array of prime factors
:’ọ          Since this is a 2,1-chain, this dyadic section is called with `x` on the left and the prime factors on the right
:            - divide x by each prime factor
 ’           - decrement each
  ọ          - how many times is each result divisible by its matching prime factor?
      Ȧ      Check if all are true
       >Ẓ    2,1-chain: check if that result is greater than whether or not x is prime (in other words, true if and only the above check was true and it is not a prime)

```
> 10 votes

# Answer
# Zsh `-eo extendedglob` 36 bytes

```
>`factor $1`
for x (<->~$1)$[$1/x%x]
```

Attempt This Online!

Outputs via exit code: zero for Giuga numbers and non-zero otherwise.

This makes *heavy* abuse of the rule

> Additionally, you may choose to take a black box function f(x) which returns 2 distinct consistent values that indicate if its input x is prime or not. Again, you may choose these two values.

The function is assumed to:

* be predefined under the name `1`
* output either `0` or `1` to standard out, for prime and non-prime respectively
* always succeed (exit with a status code of 0)

For each prime factor `x`, `$[$1/x%x]` takes the residue of the input mod `x` and tries to execute it as a command. The only number that's defined as a command is the black-box function `1`, which will succeed; otherwise, the command fails, and because of the `-e` option, Zsh exits with a non-zero status code.

---

If this is cheating, have this:

# Zsh, 40 bytes

```
>`factor $1`
for x (<->~$1)(($1/x%x==1))
```

Attempt This Online!
> 8 votes

# Answer
# Vyxal `r`, 8 bytes

```
Ǐo:?/‹ḊΠ

```

Try it Online!

```
Ǐo       # prime factors excluding x
  :      # Duplicate
   ?/    # Input / n (vectorised)
     ‹   # Decremented (vectorised)
      Ḋ  # Is divisible by corresponding prime factor (vectorised)
       Π # Take the product (0 for empty list)

```
> 7 votes

# Answer
# , 22 19 bytes

```
1<q:(-:*#@[)*:@q:|]

```

Try it online!

-3 after reading Bubbler's analysis.

* `*:@q:|]` Mods input by square of its prime factors (vectorized).
* `-:` Does that match the list of prime factors?
* `*#@[` Times the length of the prime factors.
* `1<` Is that greater than 1?
> 6 votes

# Answer
# Retina 0.8.2, ~~73~~ 62 bytes

```
.+
$*
^((.)*)(?=\1*$)(?<!^\3+(..+))(?!((?<-2>\1)+)(?(2)^)\4*$)

```

Try it online! Link includes test cases. Outputs `0` for a Guiga number, `1` if not. Explanation:

```
.+
$*

```

Convert `n` to unary.

```
^((.)*)

```

Match an integer `p=\1`, but also as a count `\2`, where...

```
(?=\1*$)

```

... `p` must be a factor of `n`, ...

```
(?<!^\3+(..+))

```

... `p` must not have a nontrivial proper factor `\3`, and...

```
(?!((?<-2>\1)+)(?(2)^)\4*$)

```

... `n-p` must be zero (in which case `n` is not composite) or not divisible by , which is calculated by matching `\1` `\2` times, and then captured, so that it can be easily repeated using `\4`.

Edit: Saved 11 bytes thanks to @Deadcode pointing out that I don't need to check that `p` is at least `2`, and in fact also allowing `p=0` means that the program works for `n=0` (although not required by the question) at no extra cost.
> 5 votes

# Answer
# JavaScript (ES6),  ~~59 56~~  53 bytes

Returns a Boolean value.

```
n=>(k=2,g=j=>j%k?k++<j&&g(j):n/k%k-1?g:1+g(j/k))(n)>1

```

Try it online!

### Commented

```
n => (           // n = input
  k = 2,         // k is the prime divisor, starting at 2
  g = j =>       // g is a recursive function taking the quotient j
    j % k ?      //   if k is not a divisor of j:
      k++ < j && //     stop if k is greater than or equal to j
      g(j)       //     otherwise, do a recursive call with j unchanged
                 //     and k + 1
    :            //   else:
      n / k % k  //     if (n / k) modulo k
      - 1 ?      //     is not equal to 1:
        g        //       stop the recursion and yield g, which turns the
                 //       result into a non-numeric string and forces the
                 //       final test to fail, whatever happened before
      :          //     else:
        1 +      //       add 1 to the result
        g(j / k) //       do a recursive call with j = j / k
)(n)             // initial call with j = n
> 1              // return true if there were at least 2 prime divisors
                 // satisfying the Giuga test

```
> 4 votes

# Answer
# Jelly, 9 bytes

```
Æfð_ọḟ>1Ȧ

```

Try it online!

```
Æfḟð_ọḷ’Ȧ

```

Try it online!

I already lost, but figured I'd post them since they're somewhat different 9-byters.

### How these work

The condition \\$p\_i \mid \left( \frac n {p\_i} -1 \right)\\$ can be translated to

$$ \frac{n}{p\_i}-1 \equiv 0 \quad(\operatorname{mod} \ p\_i) \\ \frac{n}{p\_i} \equiv 1 \quad(\operatorname{mod} \ p\_i) \\ n \equiv p\_i \quad(\operatorname{mod} \ p\_i^2) $$

So \\$n-p\_i\\$ (equivalently, \\$p\_i-n\\$) must be divisible by \\$p\_i\\$ at least twice.

```
Æfð_ọḟ>1Ȧ    Monadic link; input = n
Æf           List of prime factors of n (= L)
  ð......    Call ... as a dyadic chain, left = L, right = n
    ọ        How many times each of...
   _         L - n
             ...is divisible by...
     ḟ       Remove any occurrences of n from L
             (missing positions are treated as 0, so ọ gives 0)
      >1Ȧ    Test if the result is nonempty list of all 2s or above

Æfḟð_ọḷ’Ȧ    Monadic link; input = n
Æfḟ          Remove any occurrences of n from prime factors of n (= L)
   ð.....    Call ... as a dyadic chain, left = L, right = n
    _ọḷ      How many times each of L-n is divisible by each of L
       ’Ȧ    Test if the result, decremented, is nonempty with all nonzero

```
> 4 votes

# Answer
# Python 2, 85 bytes

```
e=n=input();k=w=0;i=1
while~-n:
 i+=1
 while n%i<1:k+=(e/i-1)%i;n/=i;w+=1
print k<1<w

```

Try it online!

-14 bytes thanks to @ovs
> 4 votes

# Answer
# Ruby, 50 bytes

```
->n{(2...z=n).all?{|c|z%c>0||n/c%c==1&&z/=c}&&z<n}

```

Try it online!

### So what?

```
->n{(2...z=n).all?

```

Check every number between 2 and n-1, use a temporary variable to skip over composite divisors.

```
{|c|z%c>0

```

If c is divisor of `z` then it's also a prime divisor of `n`, if not we can skip this number.

```
||n/c%c==1

```

Check if `n/c-1` can be divided by `c`

```
&&z/=c}

```

At this point, we must divide `z` by `c` before continuing. Once is enough, because if `n/c-1` can be divided by `c`, then `n` can't be divided by `c` more than once.

```
&&z<n}

```

Final check: did we divide z at least once? If not, then n is a prime number.
> 4 votes

# Answer
# 05AB1E, 9 bytes

```
f©/<0K®Öß

```

Outputs `1` as truthy and either `0`/`""` as falsey.

Try it online or verify some more test cases.

**Explanation:**

```
f          # Get all unique prime factors of the (implicit) input
 ©         # Store this list in variable `®` (without popping)
  /        # Divide the input by each of these
   <       # Decrease it by 1
    0K     # Remove all 0s
      ®Ö   # Check of each if it's divisible by their initial values `®`
        ß  # Pop and push the minimum of this list ("" for empty lists)
           # (after which it is output implicitly as result)

```
> 4 votes

# Answer
# Brachylog, 16 bytes

```
N⁰ḋṀ{;N⁰↔÷;?%}ᵛ1

```

Try it online!
> 4 votes

# Answer
# Regex (ECMAScript 2018 / Python`regex` / .NET), ~~83~~ ~~79~~ ~~64~~ 49 bytes

```
^(x(x*))(?<!^\3+(x+x))(?!(?=\1*(\1\2+$))\4*$)\1*$

```

*-15 bytes (79 → 64) thanks to H.PWiz*
*-8 bytes (64 → 56) by squaring instead of doing division (thanks to H.PWiz for the idea)*
*-7 bytes (56 → 49) thanks to H.PWiz \- now beats the original .NET-only version!*

Returns a non-match for Giuga numbers.

Try it online! \- ECMAScript 2018
Try it online! \- Python `import regex` (very slow)
Try it online! \- .NET

The commented version below is a **54 byte** version that behaves correctly with an input of zero, and returns a match for Giuga numbers. (Its length would be 52 bytes if returning a non-match for Giuga numbers.)

The underlying squaring/multiplication algorithm is explained in this post.

```
^                      # tail = N = input number
(?!                    # Negative lookahead - Assert that this cannot match
    # Cycle \1 through all the prime divisors of N
    (x(x*))            # \1 = conjectured non-composite divisor of N; \2 = \1-1
                       # tail -= \1; head = \1
    (?<!^\3+(x+x))     # Assert head is not composite, i.e. is prime or <2

    # Assert that tail is not divisible by \1 * \1
    (?!                # Negative lookahead - Assert that this cannot match
        # Calculate \4 = \1 * \1; this will fail to match if the result would
        # be greater than tail.
        (?=
            \1*        # We can use this shortcut thanks to tail already being
                       # checked for divisibility by \1 later.
            (\1\2+$)   # \4 = \1 * \1
        )
        \4*$           # Assert that tail is divisible by \4
    )
    \1*$               # Assert N is divisible by \1
)
x                      # Prevent N == 0 from matching

```

## Regex (.NET), ~~57~~ ~~53~~ bytes

Now obsoleted by the ECMAScript 2018 / .NET version above.

## Regex (ECMAScript+`(?^=)`RME), 50 bytes

```
^(x(x*))(?^1!(xx+)\3+$)(?!(?=\1*(\1\2+$))\4*$)\1*$

```

Try it on replit.com \- RegexMathEngine

This is a port using lookinto instead of variable-length lookbehind.

# Regex (ECMAScript+`(?*)`RME / PCRE2 v10.35+), 58 bytes

```
^(?*(x(x*))(\1*$))(?!\3(xx+)\4+$)\1(?!(?=\1*(\1\2+$))\5*$)

```

Try it on replit.com \- RegexMathEngine
Attempt This Online! \- PCRE2 v10.40+

This is a port using molecular lookahead instead of variable-length lookbehind. It is far, far faster, since it does not place a divisibility test after an is-prime test (and to do so would not be better golf, as far as I can tell); on my PC it can test every number from \\$0\\$ to \\$66200\\$ in 5.2 minutes (whereas the ECMAScript 2018 version takes weeks or maybe more) and can even test \\$2214408306\\$ in 6.4 minutes.

```
^                      # tail = N = input number
(?!                    # Negative lookahead - Assert that this cannot match
    # Cycle \1 through all the prime divisors of N
    (?*(x(x*))(\1*$))  # Cycle \1 through all of the divisors of N, including N
                       # itself; \2 = \1-1; \3 = N-\1 == tool to make tail = \1
    (?!\3(xx+)\4+$)    # Assert \1 is prime or \1 < 2.

    \1                 # tail -= \1

    # Assert that tail is not divisible by \1 * \1
    (?!                # Negative lookahead - Assert that this cannot match
        # Calculate \5 = \1 * \1
        (?=
            \1*        # We can use this shortcut thanks to tail already being
                       # checked for divisibility by \1 later.
            (\1\2+$)   # \5 = \1 * \1
        )
        \5*$           # Assert that tail is divisible by \5
    )
)
x                      # Prevent N == 0 from matching

```

### \\$\large\textit{Full programs}\\$

# Retina 0.8.2, ~~63~~ ~~59~~ 55 bytes

```
.+
$*
^(.+)(?<!^\2+(.+.))(\1)*$(?<=(?!\B\1*$)(?>(?<-3>.)*))

```

Takes its input in decimal. Outputs `1` if input is a Guiga number, `0` if not.

Try it online!
> 4 votes

# Answer
# MATL, ~~13~~ 12 bytes

```
YfG-t?6MU\~A

```

Try it online!

1 for Giuga number, either 0 or an empty vector for non-Giuga number - both of which MATL considers falsy.

*(note: had previously posted a 9 byte version which was wrong)*

**Explanation**:

\\$p\_i \mid \left( \frac n {p\_i} -1 \right) \Longrightarrow p\_i^2 \mid \left( n - {p\_i} \right) \Longrightarrow p\_i^2 \mid \left( {p\_i} - n \right)\\$

1. `Yf` \- get the prime factors of the input (if `1` is the input, `Yf` returns an empty vector; primes return themselves)
2. `G-` \- subtract the input from each factor (let's call this S = \\${p\_i} - n \\$)
3. `t?` \- is it truthy? (for `1` this is an empty vector; for primes it's a 0; either way, falsey)
4. `6M` \- If so, bring back a copy of the list of factors
5. `U` \- square each one
6. `\` \- compute the mod of S with respect to these squares
7. `~A` \- And check if that is all 0s

If the check at step 3 failed, that falsy S is left on the stack. If it succeeded, the result of the final step is left on the stack.

---

Alternate 12 byter: `_tYf+t5MU\~*` Try it online!
> 3 votes

# Answer
# Japt, 18 bytes

```
k f<U £/XÉ vXÃâ ¥1

```

Try it

```
k     - prime factors
f<U   - filter out U(input)
£..Ã  - map X-> :
/XÉ     > U/X-1
vX      > divisible by X?
â     - get unique elements
¥1    - is [1] ?

```
> 2 votes

---
Tags: code-golf, number, decision-problem, primes, division
---