# Question
Title: Egg, sausage, bacon and spam (lovely spam!)
You are given four integers: \\$e,s,b\in\\{0,1\\}\\$ and \\$S\in \\{0,1,2,4\\}\\$, where \\$e,s,b,S\\$ stand for egg, sausage, bacon and spam respectively.

Your task is to figure out whether the corresponding ingredients match a valid entry in the following menu:

```
 [e]gg | [s]ausage | [b]acon | [S]pam
-------+-----------+---------+--------
   1   |     0     |    1    |   0
   1   |     1     |    1    |   0
   1   |     0     |    0    |   1
   1   |     0     |    1    |   1
   1   |     1     |    1    |   1
   0   |     1     |    1    |   2
   1   |     0     |    1    |   4
   1   |     0     |    0    |   4
   1   |     1     |    0    |   2

```

This is a subset of the menu described in the famous Monty Python's sketch, where dishes based on other ingredients are omitted.

## Rules

* You can take \\$(e,s,b,S)\\$ in any order and any convenient format as long as they are clearly separated into 4 distinct values as described above (e.g. claiming that your code takes a single bitmask with all values packed in there is not allowed).

*Examples:* `[1,0,1,4]`, `"1014"`, or 4 distinct arguments
* Each value is guaranteed to be valid (i.e. you don't have to support \\$e=2\\$ or \\$S=3\\$).
* You may return (or print) either:
    + a truthy value for *matching* and a falsy value for *not-matching*
    + a falsy value for *matching* and a truthy value for *not-matching*
    + 2 distinct, consistent values of your choice (please specify them in your answer)
* This is

## Test cases (all of them)

Format: `[e, s, b, S] --> matching`

```
[ 0, 0, 0, 0 ] --> false
[ 0, 0, 0, 1 ] --> false
[ 0, 0, 0, 2 ] --> false
[ 0, 0, 0, 4 ] --> false
[ 0, 0, 1, 0 ] --> false
[ 0, 0, 1, 1 ] --> false
[ 0, 0, 1, 2 ] --> false
[ 0, 0, 1, 4 ] --> false
[ 0, 1, 0, 0 ] --> false
[ 0, 1, 0, 1 ] --> false
[ 0, 1, 0, 2 ] --> false
[ 0, 1, 0, 4 ] --> false
[ 0, 1, 1, 0 ] --> false
[ 0, 1, 1, 1 ] --> false
[ 0, 1, 1, 2 ] --> true
[ 0, 1, 1, 4 ] --> false
[ 1, 0, 0, 0 ] --> false
[ 1, 0, 0, 1 ] --> true
[ 1, 0, 0, 2 ] --> false
[ 1, 0, 0, 4 ] --> true
[ 1, 0, 1, 0 ] --> true
[ 1, 0, 1, 1 ] --> true
[ 1, 0, 1, 2 ] --> false
[ 1, 0, 1, 4 ] --> true
[ 1, 1, 0, 0 ] --> false
[ 1, 1, 0, 1 ] --> false
[ 1, 1, 0, 2 ] --> true
[ 1, 1, 0, 4 ] --> false
[ 1, 1, 1, 0 ] --> true
[ 1, 1, 1, 1 ] --> true
[ 1, 1, 1, 2 ] --> false
[ 1, 1, 1, 4 ] --> false

```

*Spam spam spam spam. Lovely spam! Wonderful spam!*

# Answer
> 19 votes
# Python, 32 bytes

```
"001111020114001410120110".count

```

Try it online!

Takes input in `'sbeS'` order as a single string, like `'1102'`. Simply checks whether the string appears as a substring of the hardcoded string, using the object method to avoid needing to write out a costly `lambda` to define a function.

The desired strings are squished together as much as possible via overlapping. For example, the part `"001111020114` checks for `0011`, `0111`, `1111`, `1110`, and `1102`. The fact that `2` and `4` can only appear as the counts of spam, which is listed last, lets us append strings directly to their right without false positives. I played with the order of the inputs to try to overlap more, but there might be a better outcome.

I suspect this approach can be beaten with a modulo chain or similar using number inputs.

# Answer
> 8 votes
# Python 3, 31 bytes

```
oct(0x20a00924204c00c048).count

```

Try it online!

Based on @xnor's answer

# Answer
> 8 votes
# Python 2,  ~~29 28~~  25 bytes

-3 bytes thanks to dingledooper! (Suffixing a string as the `hash` input)

```
lambda s:hash(s+'?pB{')%3

```

An unnamed function accepting a string of digit characters, `egg+bacon+spam+sausage` (e.g. `'0040'`) which yields a falsey value (`0`) if on the menu or a truthy value (`1` or `2`) if not.

**Try it online!**

This was found by dingledooper using this code (Try it online, limited to printables, which finds the above).

---

**28 byter...**

```
lambda*i:hash(i)/442%89%22%5

```

An unnamed function accepting four integers, `sausage, bacon, spam, egg` which yields a falsey value (`0`) if on the menu or a truthy value (`1`, `2`, `3`, or `4`) if not.

**Try it online!**

---

**Another 28:**

```
lambda*i:hash(i)/8883%55%8-2

```

Try it here! (accepts `egg, spam, bacon, sausage`)

---

**29 byters...**

```
lambda*i:hash(i)/676%86%9%6-2

```

Try it here! (accepts `egg, spam, sausage, bacon`)

Or one which returns `True` if on the menu or `False` otherwise:

```
lambda*i:hash(i)/64%31%14%8<2

```

Try it here! (accepts `spam, sausage, egg, bacon`)

# Answer
> 7 votes
# 05AB1E, 11 bytes

```
•ʒº-ép•bsCè

```

Try it online!

Inputs as a string `"Sesb"`. Outputs 0 for matching and 1 for non-matching.

```
•ʒº-ép•      # compressed integer 269454360636
       b     # convert to binary: 11111010111100101110110100000000111100
        sC   # convert the input from binary: 8S + 4e + 2s + b
             # (this doesn't error out on digits > 1)
          è  # use this value to index in the above bitstring

```

# Answer
> 7 votes
# x86-16 machine code, 30 bytes

```
D0 E3       SHL  BL, 1              ; e << 1
0A FB       OR   BH, BL             ; BH = e << 1 | s
D0 E7       SHL  BH, 1              ; es << 1
0A C7       OR   AL, BH             ; AL = e << 2 | s << 1 | b
D0 E0 03    SHL  AL, 3              ; AL =<< 3 (80186+ only)
0A C4       OR   AL, AH             ; AL = spam table value
B1 09       MOV  CL, 9              ; search 9 entries
BF 013B     MOV  DI, OFFSET SPAM    ; in SPAM table
F2/ AE      REPNZ SCASB             ; search table - ZF if found, NZ if not
C3          RET                     ; return to caller
SPAM        DB   28H, 38H, 21H, 29H, 39H, 1AH, 2CH, 24H, 32H    ; SPAM table

```

Input as `BL = e`, `BH = s`, `AL = b`, `AH = S`. Output `ZF` if valid entry, `NZ` if not valid

Encodes the input values into a 6-bit binary value (`00esbSSS`), and compares against the table of known valid results.

Here's output from a little test program for PC DOS that takes input from command line:

Note: Due to the use of `SHL AL, imm8`, this won't work on an 8088-based PC/XT. It would be +1 byte to do `MOV CL, 3 / SHL AL, CL`.

# Answer
> 6 votes
# PHP, ~~61~~ ~~59~~ ~~56~~ ~~34~~ ~~32~~ ~~30~~ 27 bytes

```
<?=74958>>33-$argn%95%34&1;

```

Try it online!

Each input (ordered esbS) is read as a decimal value and the modulus buckets them into a smaller range (i.e. a hashing function), which are then looked up in the "bit table" of the constant.

The hashing function has clashing values, but these all coincide when values are either truthy or falsy.

# Answer
> 5 votes
# GolfScript, 24 bytes 21 bytes

This refinement of the solution is thanks to Grimmy, who took my formatting and used stronger stack manipulation to save a bunch of whitespace and variable assignment.

The following is the code (for the first time, newlines are necessary).

```
'\;*
>>
@^*

;>'n/\=~

```

Grimmy's solution at the bottom takes in a string of a list of arrays and applies the following operation to all of them, even though it's not strictly necessary. Golfscript can take input as a header, which is where my TIO references. Grimmy's is much cleaner to see all the outputs.

Input is a stack-dump of four elements: e, s, b, S

For the following explanation, I'm going to use N as a "newline" indicator so you can understand how this works in my formatting.

```
'\;*N>>N@^*NN;>'n/\=~ #Do as instructed
'              '      #String notation
'\;*N          '      #[Index 0] Pop s, then multiply e and b
'    >>N       '      #[Index 1] A trickier operation, will explain at bottom.
'       @^*N   '      #[Index 2] s*(e xor b)
'           N  '      #[Index 3] Can never be called.
'            ;>'      #[Index 4] Ensure e=1, s=0.
'              'n/    #Split the string on newlines (stack is e s b S "x/y/z")
                  \   #Swap the top two elements of the stack (e s b "x/y/z" S)
                   =  #Find the (top element)th element of (second element)
                    ~ #Then evaluate it.

```

So, why do these operations work?

```
m=0
 [e]gg | [s]ausage | [b]acon | spa[m]
-------+-----------+---------+--------
   1   |     0     |    1    |   0
   1   |     1     |    1    |   0
As long as e=1 and b=1, s can be anything. So if m=0, our output can be e*b

We do this in the program with {\;*}

This removes s from the array, then multiplies e and b together. If they're both 1, yay! If not, then we get a 0.

m=1

 [e]gg | [s]ausage | [b]acon | spa[m]
-------+-----------+---------+--------
   1   |     0     |    0    |   1
   1   |     0     |    1    |   1
   1   |     1     |    1    |   1

3/4 binary options. As long as we have e=1, and we DON'T have s=1, b=0, then we're good.
e*NOT(s*NOT(b))
or
e*(NOT(s) + b)

So, why does {>>} work?

It starts by checking that s>b. This should NEVER be true. So we have 0.
Then we check if e>0, which is true if e=1 and the above worked. If the above *didn't* work, then e>1 will never be true.

m=2
 [e]gg | [s]ausage | [b]acon | spa[m]
-------+-----------+---------+--------
   0   |     1     |    1    |   2
   1   |     1     |    0    |   2
As long as s=1, then we have an xor situation!
s*(e xor b)

{@^*} pulls the e to the top of the stack, then xors it with b.
Then the * multiplies that result with s.

m=4
 [e]gg | [s]ausage | [b]acon | spa[m]
-------+-----------+---------+--------
   1   |     0     |    0    |   4
   1   |     0     |    1    |   4
As long as e=1 and s=0, we don't care about b.
e*NOT(s)

We just do this with {;>}, which removes b from the equations, and makes sure e>s, which can only be the case is e is 1 and s is 0.

```

There we go! With brainpower combined, feast your eyes upon this beautiful creation!

Try the 21-byter online!
Try the old 24-byter online!
Try all examples online on the old solution (26 bytes)! (Courtesy Grimmy)

# Answer
> 3 votes
# Python, ~~49~~ 44 bytes

```
lambda S,e,s,b:269454360636>>8*S+4*e+2*s+b&1

```

You can verify all test cases. Outputs 0 for a valid recipe and 1 otherwise.

Hats off to @Arnauld for shaving me 5 bytes :)

Borrows Grimmy's approach so be sure to upvote that one as well!

# Answer
> 3 votes
# Python 3, ~~52~~ \\$\cdots\\$ ~~48~~ 44 bytes

```
lambda e,s,b,S:206163194016>>8*S+e*4+s*2+b&1

```

Try it online!

Ouputs Truthy for true and Falsy otherwise.

# Answer
> 3 votes
# Jelly, ~~13~~ 11 bytes

```
“BƑṗ©N’Bị@Ḅ

```

You can try all the test cases!

Thank you, @Nick, for saving me 2 bytes. I'm currently tied with the shortest 05AB1E answer :)

# Answer
> 3 votes
# C (clang), 49 bytes

```
f(e,s,b,S){return 206163194016>>8*S+e*4+s*2+b&1;}

```

Try it online!

Ouputs `1` for true and `O` otherwise.

# Answer
> 2 votes
# Ruby, ~~51 41~~ 36 bytes

```
->*x{"J36:;>'-."[""<<x.join.oct%77]}

```

Try it online!

Returns `nil` (falsy) or a string (truthy).

# Answer
> 2 votes
# Japt, 17 bytes

```
"~ "øUn5 d

```

Try it

```
"~ "øUn5 d     Program taking U, the string in "esbS" form
"~ "           String with values 130,155,126,131,156,32,134,129,152
              ø          Does it contain
               Un5       The input converted from Base-5 string to a number
                   d     And converted to a char?

```

# Answer
> 2 votes
# APL+WIN, 23 bytes

```
×+/'é¢~â£ ≠ü⌹'=⎕av[5⊥⎕]

```

Index origin = 0

Prompts for a vector 4 integers and returns 1 for true zero for false.

Explanation:

Converts input vector from base 5 to an integer used to index into APL+WIN's atomic character vector (extended ASCII) and checks if it is in the menu which has similarly been converted to characters.

# Answer
> 1 votes
# 05AB1E, 18 bytes

```
•ÿŸ»¢•bŽ9“«S4äøJIå

```

Input as a concatenated string of \\$e||s||b||S\\$. If this is not allowed, a single byte has to be added for an explicit `J`oin.

Pretty straight-forward approach, so will golf it down from here.

Try it online or verify all test cases.

**Explanation:**

```
•ÿŸ»¢•              # Push compressed integer 4221990791
      b             # Convert it to binary: 11111011101001100111011110000111
       Ž9“          # Push compressed integer 2442
          «         # Merge them together: 111110111010011001110111100001112442
           S        # Convert it to a list of digits
            4ä      # Split it into 4 equal-sized parts
              ø     # Zip/transpose; swapping rows and columns, to create quartets
               J    # Join those together
                Iå  # And check if the input-string is in this list
                    # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `•ÿŸ»¢•` is `4221990791` and `Ž9“` is `2442`.

# Answer
> 1 votes
# Charcoal, 15 bytes

```
№%')-/36AE§γ↨θ²

```

Try it online! Link is to verbose version of code. Takes input ingredients as a list in reverse order and outputs a Charcoal boolean i.e. `-` for matching and nothing for non-matching. Explanation:

```
             θ  Input list
            ↨ ² Convert from "base 2"
          §γ    Index into printable ASCII
№%')-/36AE      Is the result contained in the given literal?
                Implicitly print.

```

One of my rare answers that don't use any characters with unusual widths meaning that the explanation lines up nicely for once.

# Answer
> 1 votes
# cQuents, 38 bytes

```
?112,1001,Z+3,Z+6,Z+1,Z+3,1102,Z+8,Z+1

```

Try it online!

Builds a list of all of the possible inputs (in integer form) and returns True if they are in the list.

# Answer
> 1 votes
# Excel, 67 bytes

```
=CHOOSE(D1+1,A1*C1,AND(A1,B1<=C1),AND(B1,A1+C1=1),,AND(A1,NOT(B1)))

```

Follows similar logic to that used by @Mathgeek

# Answer
> 1 votes
# Jelly, 9 bytes

```
“ṚE⁾’,3ḥỊ

```

A monadic Link accepting a list of integers, `[egg, sausage, bacon, spam]`, which yields a truthy value (`1`) if on the menu or a falsey value (`0`) if not.

**Try it online!** Or see the test-suite.

There may well be an 8 or 7 out there using a similar method, it's just a mater of finding them!

### How?

```
“ṚE⁾’,3ḥỊ - Link: list of integers
“ṚE⁾’     - base 250 number = 11455143
      3   - three
     ,    - pair = [11455143, 3]
       ḥ  - Jelly's hash: use 11455143 as a salt and [1,2,3] as a domain
        Ị - insignificant? (effectively "equals one?")

```

---

**Another 9** which takes `[egg, sausage, bacon, spam]` and yields `2` when on-menu or `1` when not:

```
“Ḋẏƭ¢’,2ḥ

```

# Answer
> 1 votes
# JavaScript (V8), 35 34 30 bytes

```
(e,s,b,S)=>s<S?5/S-s&e+b*s:e&b

```

Try it online!

I wrote a random expression generator and left it running for a few hours to generate the expression following the `=>`. In this answer I am only posting unedited outputs from the generator.

# Answer
> 1 votes
**RUST, 98 Bytes**

```
fn f(e:u8,s:u8,b:u8,x:u8)->bool{match x|s<<3|e<<4|b<<5{17|20|26|42|48|49|52|56|57=>true,_=>false}}

```

Try it here

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


title: Can I join the music box?

text:
# Question
Title: Can I join the music box?
# The magic music box (MMB)

*This explains the motivation for the challenge, feel free to ignore.*

The magic music box is a word game played by a group of people, where one is the owner of the magic music box and the other people are trying to put words inside the magic music box.

Rules for the game with humans: the game goes in turns, one person at a time. In your turn, you have to say a word you want to put in the MMB and the MMB owner says if your word can get in or not, depending on the game criterion. If you are the MMB owner, you have to say a word that can go in the MMB.

# The task

You have to code a function/program that receives a word as input (in any sensible format) and outputs Truthy or Falsy. Truthy if the word can go in the MMB and Falsy otherwise.

For a word to be able to go in the MMB, it has to contain at least one of the following seven strings:

* `do`
* `re`
* `mi`
* `fa`
* `sol`
* `la`
* `si`

# Input

A lowercase "word" in any sensible format, for example:

* a string
* a list of characters
* a list of ASCII values of the characters

# Test cases

(Edited test cases to include `obsolete`, `also`, some answers may not have it yet)

```
far -> Truthy
solace -> Truthy
boat -> Falsy
shrimp -> Falsy
fire -> Truthy
summit -> Truthy
biscuit -> Falsy
bullet -> Falsy
doctor -> Truthy
blast -> Truthy
college -> Falsy
subsidiary -> Truthy
obsolete -> Truthy
also -> Falsy

```

# Answer
> 16 votes
# 05AB1E, ~~15~~ 14 bytes

```
’ïêo‡Åefa’7äåà

```

Try it online!

```
’ïêo‡Åefa’        # dictionary string "soldosimilarefa" (using the words sold and similar)
          7ä      # split in 7 parts of almost-equal length (excess length goes to the first parts)
            å     # for each part, check if it’s in the input
             à    # maximum

```

# Answer
> 10 votes
# Jelly,  ~~18~~  14 bytes

-4 thanks to Nick Kennedy & Grimmy's 05AB1E answer

```
7“Ẉ|nŻUḋ}»œsfẆ

```

A monadic Link accepting a list of characters which yields a, possibly empty, list of lists.

**Try it online!**

### How?

Note that in Jelly an empty list is falsey, while a non-empty list is truthy (as employed by the if-else, `”T”FÇ?`, in the footer of the Try it online link, above).

```
7“Ẉ|nŻUḋ}»œsfẆ - Link: list of characters, w
7              - seven
 “Ẉ|nŻUḋ}»     - "solfa"+"similar"+"edo"
          œs   - split into (seven) equal chunks
                  -> ["sol","fa","si","mi","la","re","do"]
             Ẇ - all sublists (w)
            f  - filter keep

```

Aside: solfa is a name of a solfège method, where tones are given single syllable names, and was when `si` first became `ti`.

# Answer
> 9 votes
# Python, 52 bytes

```
import re
re.compile('do|re|mi|fa|sol|la|si').search

```

Try it online!

Yup, a regex. A match produces a Truthy match object, and a non-match produces a Falsey None. Using `re.compile` to make an compiled pattern as a function is a bit shorter than a direct `lambda`:

**55 bytes**

```
lambda w:re.search('do|re|mi|fa|sol|la|si',w)
import re

```

Try it online!

For comparison, without regex:

**58 bytes**

```
lambda w:any(map(w.count,'do re mi fa sol la si'.split()))

```

Try it online!

We can almost save a byte by writing `1in map(...)`, but this doesn't catch the string appearing two or more times.

# Answer
> 8 votes
# CP-1610 assembly (Intellivision), 41 DECLEs1 ≈ 52 bytes

A routine taking a pointer to a NUL-terminated string into **R4** and setting the carry if the test is successful, or clearing it otherwise.

```
**275** |         PSHR    R5
**2A0** | @@read  MVI@    R4,     R0
**338 061** |         SUBI    #'a',   R0
**20B 01B** |         BMI     @@rtn
**04C** |         SLL     R0,     2
**04C** |         SLL     R0,     2
**048** |         SLL     R0
**3E0** |         XOR@    R4,     R0
**2A1** |         MVI@    R4,     R1
**33C 002** |         SUBI    #2,     R4
**001** |         SDBD
**2BD 0C6 048** |         MVII    #@@tbl, R5
**368** | @@loop  CMP@    R5,     R0
**204 00D** |         BEQ     @@rtn
**001** | @@next  SDBD
**37D 0CC 048** |         CMPI    #@@so,  R5
**22C 008** |         BNEQ    @@loop
**368** |         CMP@    R5,     R0
**22C 01B** |         BNEQ    @@read
**379 06C** |         CMPI    #'l',   R1
**22C 01F** |         BNEQ    @@read
**2B7** | @@rtn   PULR    R7
**00F** | @@tbl   DECLE   $00F
**245** |         DECLE   $245
**1E9** |         DECLE   $1E9
**0C1** |         DECLE   $0C1
**101** |         DECLE   $101
**229** |         DECLE   $229
**22F** | @@so    DECLE   $22F

```

### How?

Each note made of the ASCII codes \\$(c\_0,c\_1)\\$ is encoded as a single DECLE with the following formula:

$$((c\_0-97)\times 32) \operatorname{xor} c\_1$$

The edge case *"sol"* is encoded as *"so"* and put at the end of the lookup table. There's an additional test for the *"l"*.

### Full commented test code

```
        ROMW    10                ; use 10-bit ROM width
        ORG     $4800             ; map this program at $4800

        ;; ------------------------------------------------------------- ;;
        ;;  main code                                                    ;;
        ;; ------------------------------------------------------------- ;;
main    PROC

        SDBD                      ; set up an interrupt service routine
        MVII    #isr,   R0        ; to do some minimal STIC initialization
        MVO     R0,     $100
        SWAP    R0
        MVO     R0,     $101

        EIS                       ; enable interrupts

        SDBD                      ; R5 = pointer into the test case index
        MVII    #tc.tbl,R5
        MVII    #$200,  R3        ; R3 = backtab pointer
        MVII    #14,    R1        ; R1 = number of test cases

@@loop  MVI@    R5,     R4        ; R4 = pointer to next string
        SDBD
        ADDI    #tc.00, R4

        PSHR    R5                ; save the test variables
        PSHR    R3
        PSHR    R1
        CALL    mmb               ; invoke our routine
        PULR    R1                ; restore the test variables
        PULR    R3
        PULR    R5

        MVII    #$88,   R0        ; R0 = '1'
        BC      @@draw

        MVII    #$80,   R0        ; or '0' if the carry is not set

@@draw  MVO@    R0,     R3        ; draw this character
        INCR    R3                ; increment the backtab pointer

        DECR    R1                ; next test case
        BNEQ    @@loop

        DECR    R7                ; done: loop forever

        ENDP

        ;; ------------------------------------------------------------- ;;
        ;;  test cases                                                   ;;
        ;; ------------------------------------------------------------- ;;
tc      PROC

@@tbl   DECLE   @@00 - @@00, @@01 - @@00, @@02 - @@00, @@03 - @@00
        DECLE   @@04 - @@00, @@05 - @@00, @@06 - @@00, @@07 - @@00
        DECLE   @@08 - @@00, @@09 - @@00, @@10 - @@00, @@11 - @@00
        DECLE   @@12 - @@00, @@13 - @@00

        ;; truthy
@@00    STRING  "far", 0
@@01    STRING  "solace", 0
@@02    STRING  "fire", 0
@@03    STRING  "summit", 0
@@04    STRING  "doctor", 0
@@05    STRING  "blast", 0
@@06    STRING  "subsidiary", 0
@@07    STRING  "obsolete", 0

        ;; falsy
@@08    STRING  "boat", 0
@@09    STRING  "shrimp", 0
@@10    STRING  "biscuit", 0
@@11    STRING  "bullet", 0
@@12    STRING  "college", 0
@@13    STRING  "also", 0

        ENDP

        ;; ------------------------------------------------------------- ;;
        ;;  ISR                                                          ;;
        ;; ------------------------------------------------------------- ;;
isr     PROC

        MVO     R0,     $0020     ; enable display

        CLRR    R0
        MVO     R0,     $0030     ; no horizontal delay
        MVO     R0,     $0031     ; no vertical delay
        MVO     R0,     $0032     ; no border extension
        MVII    #$D,    R0
        MVO     R0,     $0028     ; light-blue background
        MVO     R0,     $002C     ; light-blue border

        JR      R5                ; return from ISR

        ENDP

        ;; ------------------------------------------------------------- ;;
        ;;  our routine                                                  ;;
        ;; ------------------------------------------------------------- ;;
mmb     PROC

        PSHR    R5                ; save the return address on the stack

@@read  MVI@    R4,     R0        ; R0 = current character
        SUBI    #'a',   R0        ; turn it into an index in [0..25]
        BMI     @@rtn             ; if the result is negative, it means
                                  ; we've reached the end of the string:
                                  ; we return with the carry cleared by SUBI

        SLL     R0,     2         ; multiply R0 by 32
        SLL     R0,     2
        SLL     R0

        XOR@    R4,     R0        ; XOR it with the next character
        MVI@    R4,     R1        ; and load a 3rd character in R1
        SUBI    #2,     R4        ; rewind the pointer by 2 characters

        SDBD                      ; R5 = pointer into the lookup table
        MVII    #@@tbl, R5

@@loop  CMP@    R5,     R0        ; compare the lookup table entry with R0
        BEQ     @@rtn             ; match? (if yes, the carry is set)

@@next  SDBD                      ; if we haven't reached the end of the table,
        CMPI    #@@so,  R5
        BNEQ    @@loop            ; try again with the next entry

        CMP@    R5,     R0        ; last test with 'so'
        BNEQ    @@read            ; abort if it doesn't match

        CMPI    #'l',   R1        ; otherwise, make sure it's followed by a 'l'
        BNEQ    @@read            ; abort if it doesn't match
                                  ; otherwise, the carry is set

@@rtn   PULR    R7                ; return

        ;; lookup table: 'do', 're', 'mi', 'fa', 'la', 'si', 'so'
@@tbl   DECLE   ('d' - 'a') * 32 XOR 'o'
        DECLE   ('r' - 'a') * 32 XOR 'e'
        DECLE   ('m' - 'a') * 32 XOR 'i'
        DECLE   ('f' - 'a') * 32 XOR 'a'
        DECLE   ('l' - 'a') * 32 XOR 'a'
        DECLE   ('s' - 'a') * 32 XOR 'i'
@@so    DECLE   ('s' - 'a') * 32 XOR 'o'

        ENDP

```

### Output

*screenshot from jzIntv*

---

*1. A CP-1610 opcode is encoded with a 10-bit value (0x000 to 0x3FF), known as a 'DECLE'.*

# Answer
> 7 votes
# Perl 6, 26 bytes

```
{?/do|re|mi|fa|sol|la|si/}

```

Try it online!

Boring regex solution that checks for any of the strings.

# Answer
> 6 votes
# C (gcc), 58 characters, 70 bytes

```
c;f(int*s){for(c=7;c&&!strstr(s,L"潤敲業慦慬楳\x6c6f73"+--c););}

```

Creative method required to save bytes/characters.

*-17 thanks to Arnauld!*
*-8 bytes thanks to gastropner!*
*-2 bytes and -12 characters thanks to ceilingcat!*

Try it online!

# Answer
> 4 votes
# AWK, ~~47~~ \\$\cdots\\$ ~~31~~ 30 bytes

```
{print/do|re|mi|fa|sol|la|si/}

```

Try it online!

`awk` automatically compares any regex with `$0` (current line).

# Answer
> 4 votes
# Retina, 21 bytes

```
do|re|mi|fa|sol|la|si

```

Try it online!

Very obvious and boring solution. `0` for false, nonzero for true.

# Answer
> 4 votes
# Java 8, 43 bytes

```
s->s.matches(".*(do|re|mi|fa|sol|la|si).*")

```

Try it online.

**Explanation:**

```
s->           // Method with String parameter and boolean return-type
  s.matches(  //  Check if the String matches this regex fully:
    ".*       //   Any amount of optional leading characters
       (do|re|mi|fa|sol|la|si)
              //   Followed by one of our music sounds
     .*")    "//   Followed by any amount of optional trailing characters

```

# Answer
> 3 votes
# Python 3, 60 bytes

```
lambda w:any(i in w for i in'do re mi fa sol la si'.split())

```

Try it online!

# Answer
> 3 votes
# Red, 63 bytes

```
func[s][parse s[to["do"|"re"|"mi"|"fa"|"sol"|"la"|"si"]to end]]

```

Try it online!

# Answer
> 3 votes
# Scratch 3.0, 13 blocks/135 + 21 = 156 bytes

*+21 for having a predefined list `n`. Y'all do that by creating a new list within Scratch and entering each item manually. It took 21 keystrokes to manually create the list.*

*As SB Syntax*:

```
when gf clicked
ask()and wait
set[o v]to(0
set[i v]to(1
repeat(7
change[o v]by<(answer)contains(item(i)of[n v
change[i v]by(1
end
say(o

```

This was a rather simple approach, as thankfully, there were appropriate built-ins. Zero is falsey and anything else is truthy.

I still don't have access to my old account, but y'all can still Try it on~~line~~ Scratch!

# Answer
> 3 votes
# , ~~44~~ 40 bytes

Another simple regex implementation. Fixed stupid mistake, thanks @Giuseppe.

```
grepl("do|re|mi|fa|sol|la|si",scan(,''))

```

Try it online!

One could also save a character by using grep instead of grepl, where integer(0) is falsey and everything else truthy... but that's not a big change and can't process a whole list at once.

# Answer
> 2 votes
# Japt, ~~20~~ 19 bytes

```
`ÎolÌ·nè^`qÍøUã

```

Try it

# Answer
> 2 votes
# Zsh, ~~36~~ 35 bytes

```
[[ $1 =~ 'do|re|mi|fa|sol|la|si' ]]

```

~~Try it online!~~ Try it online!

The `=~` operator enables regex matching with the `zsh/regex` module, which is one byte shorter than glob matching using `=` (see ~~previous answer~~).

---

If truthy-falsy convetions can be swapped, then **35 bytes**:

```
[ ${1:#*(do|re|mi|fa|sol|la|si)*} ]

```

Try it online!

In any case, writing all syllables out is just as short as any combination, such as `(do|re|[ms]i|[fl]a|sol)`.

# Answer
> 2 votes
# GolfScript, 34 bytes

```
:a;7,{a"sdrmflsooeiaail"@>7%/,2=},

```

Try it online!

## Explanation

```
:a;                                # Assign the input to the "accumulator"
   7,                              # Yields [0 1 2 3 4 5 6]
     {                          }, # Keep all that full fill this condition
                                   # Item = current item
                                   # ac = accumulator
      a"sdrmflsooeiaail"           # Stack: <item> <ac> "sdrmflsooeiaail"
                        @          # Stack: <ac> "sdrmflsooeiaail" <item>
                         >         # The slice begins at the current item
                          7%       # With a step of 7
                            /      # Try to split the input by the sliced item
                             ,2=   # Is the slice was successful?

```

# Answer
> 2 votes
# Keg, `-rR` 53 bytes

```
@h2|/÷!1≠:[⑹]øƒ0&᠀®s`do,re,mi,fa,sol,la,si`\,/÷(©s@hƒ

```

Try it online!

A rather regex-less approach for a rather regex-less language. :P

Zero is falsey, any other value is truthy.

## Explained

This program has two parts: the helper function (`h`) and the main part. Here is the extracted function:

```
@h2|/÷!1≠:[⑹]øƒ

```

This function `h` takes 2 parameters from the stack, both of which are going to be strings.

```
@h2|            # Function definition
    /÷          # Split the first string (input) on the second string (note) and push individual items
      !1≠       # Push the length of the item splitted stack and see if it doesn't equal 1
         [⑹]    # If the above comparison results in true, increment the register
            øƒ  # Clear the stack of all remaining items and end the function

```

Now that the function is out of the way, we can get on to the real fun stuff: the body of the program.

```
0&᠀®s`do,re,mi,fa,sol,la,si`\,/÷(©s@hƒ
0&                                      # Store 0 in the register
  ᠀®s                                   # Take the input as a string and store it in var "s"
     `do,re,mi,fa,sol,la,si`\,/÷        # Push the string "do,re,mi,fa,sol,la,si", split on ","s and item split
                                (©s@hƒ  # Apply function "h" to each and every item in that list.
# -rR automatically prints the value stored in the register at End Of Execution

```

# Answer
> 2 votes
# Python 3, 59 bytes

```
lambda w:any('sdrmflsooeiaail'[i::7]in w for i in range(7))

```

Try it online!

# Answer
> 2 votes
# Pyth, 20 bytes

At least it's as long as the regex...

See TIO for the two unprintables in the packed string.

```
:z."a|ê)H·>ÔMv´#°"

```

Try it online!

# Answer
> 2 votes
# Pyth, 17 bytes

```
}#zc7."asÐ@»„¸Ï

```

Try it online!

Makes use of Pyth's string compression feature, `."`, to compress the string `soldosimilarefa`, then chops that string into 7 pieces, extra length in the first one, then filters which of those strings are contained in the input. If there is at least one, the result is truthy.

# Answer
> 2 votes
# , 42 bytes

```
[:>./^:_(;:'do re mi fa sol la si')&=@<\\.

```

There's probably a way to golf the string, but I had a hard enough time coming up with this as is. Fun challenge!

Explanation:

```
[:              NB. Capped fork
  >./^:_        NB. Get the largest value in the resulting array, i.e. 1 or 0
        (;:'do re mi fa sol la si') NB. Array of boxed words
        &       NB. Bind words to
         =@<    NB. Box and compare
            \   NB. With the prefixes
             \. NB. Of the suffixes

```

Try it online!

# Answer
> 1 votes
# C# (Visual C# Interactive Compiler) with `/u:System.Text.RegularExpressions.Regex`-flag, 37 bytes

```
s=>IsMatch(s,"do|re|mi|fa|sol|la|si")

```

Try it online.

**Explanation:**

```
s=>                           // Method with string parameter and bool return-type
  IsMatch(s,                  //  Check if the string contains the following regex-match:
    "do|re|mi|fa|sol|la|si")  //   One of the music sounds

```

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

```
s=>s.match`do|re|mi|fa|sol|la|si`

```

Try it online!

# Answer
> 1 votes
## `d`, ~~24~~ 22 bytes

I finally managed to compress the string!

Take your input in the form `"['your string']"`. Languages without grouping are having a terrible time here.

```
☺¶4∙)╘┐►↔₧uVÿñ☼╠◙╤Γ()¿

```

Uncompressed:

```
1y56WX0y`2,"Wb,R`3,+,ak2=W

```

## Explanation

```
1y56WX0y`2,                # Split "farmiesila" into chunks of 2
           "Wb,R`3,+       # Add "sol" and "do" wrapped into a list into the list
                    ,      # Try to split the input by all these strings
                     ak2=W # Choose all lengths that are equal to 2 (i.e. split successful)

```

# Answer
> 1 votes
# Excel, 155 bytes

```
=ISNUMBER(FIND(0,SUBSTITUTE(SUBSTITUTE(SUBSTITUTE(SUBSTITUTE(SUBSTITUTE(SUBSTITUTE(SUBSTITUTE(A1,"si",0),"la",0),"sol",0),"fa",0),"mi",0),"re",0),"do",0)))

```

A sequence of `SUBSTITUTE`, and then a check to see if any of them found a match.

`FIND` returns error `#VALUE!` if no match is found, so would have to wrap each usage in error handling.

# Answer
> 1 votes
# , 33 bytes

```
[:OR@,do`re`mi`fa`sol`la`si E.&><

```

Try it online!

### How it works

```
[:OR@,do`re`mi`fa`sol`la`si E.&><
      do`re`mi`fa`sol`la`si        NB. 7 enclosed strings to search for
                                <  NB. Enclose the input
                            E.&>   NB. Find matches for each of the 7 strings
[:OR@,                             NB. Flatten and take OR

```

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


title: All roads lead to Rome

text:
# Question
Title: All roads lead to Rome
*"All roads lead to Rome"* is a saying that essentially means there are plenty of different ways of achieving an objective.

# Task

Your task is to write a program that finds a set of link connections from one Wikipedia page to the Wikipedia page about Rome.

Notice that it is not enough to find the word `Rome` with a hyperlink, `Rome` has to be linked to this specific page: `"https://en.wikipedia.org/wiki/Rome"`

## Link connections

The Wikipedia pages are written in HTML, a markup language. With the appropriate syntax, a word or phrase can be annotated and turned into a hyperlink, which allows people to click the word/phrase and open a new Wiki page. You can see a couple of such link in the screenshot below:

Those annotated hyperlinks are what your program should locate and follow. To try and avoid some loopholes, we are going to restrict the links you are allowed to follow to the links within the `div` named `content`, which is roughly this part of the wiki page:

## Loopholes

* You are only allowed to query Wikipedia wiki pages on the internet. Your answer may not communicate with anything else. E.g., you are not allowed to download someone else's answer and run it.
* You may not communicate with any wiki APIs or Wiki "meta" pages, such as the "Category" page.

This community is very clever and imaginative. As more loopholes arise, those may be explicitly disallowed in the challenge. The *spirit* of the challenge is to find a series of links a user could click in the content of wiki pages.

# Input

Your code should take one of the two as input:

* a string that, when appended to `https://en.wikipedia.org/wiki/`, gives a valid link to a valid Wikipedia page;
* a string with the link already built for you.

You may assume there is a valid path between the input page and Rome's page.

# Output

Your program should output the path taken so that the lengths you claim are actually verifiable. It is up to you to output the path in any way that is human readable and understandable. Some suggestions include:

* the successive path links
* the successive page names

# Scoring

This is code-golf, so we care about byte count. You are allowed to define a string literal containing exactly these characters in this order: `"https://en.wikipedia.org/wiki/"` and not count it for the byte count of your program.

# Test cases

At the time of writing, these pages had a 1-link path to Rome:

```
"https://en.wikipedia.org/wiki/Italy"
"https://en.wikipedia.org/wiki/A.S._Roma"
"https://en.wikipedia.org/wiki/Vatican_Hill"
"https://en.wikipedia.org/wiki/Europe"
"https://en.wikipedia.org/wiki/European_Union"

```

And these pages had a path of length at most 2 to Rome:

```
"https://en.wikipedia.org/wiki/Continent"
"https://en.wikipedia.org/wiki/France"

```

(feel free to suggest more!)

Please submit your code with a screenshot or a TIO link showing a path from a Wikipedia page of your choosing to Rome.

# Answer
# JavaScript (Node.js), 335 - 30 = 305 bytes

I'm not very happy with it, but let's get the ball rolling.

Takes input as a page name. Prints a list of page names, separated with linefeeds.

```
u=>(i=0,g=a=>(m=a.find(u=>u=='Rome'))?console.log((h=v=>g[v]==u?u:h(g[v])+`
`+g[v])(m)+`
`+m):require('https').get('https://en.wikipedia.org/wiki/'+(U=a[i++]),r=>r.on('data',s=>h+=s,h="").on("end",_=>g([...new Set([...a,...((h.match(/mw-b.*mw-d/s)||[''])[0].match(/(?<=href=".wiki.).*?(?=")/g)||[]).map(v=>(g[v]=g[v]||U,v))])]))))([u])

```

(Don't) try it online!

### Example I/O

```
f("Commodore_64")

```

Results in:

```
Commodore_64
Christmas
Rome

```
> 4 votes

# Answer
# Python 3 + BeautifulSoup 4, 269 - 30 = 239 bytes

```
import bs4,requests as r
k=l=[(input(),)]
while'Rome'!=k[-1]:k=l.pop(0);l+=[k+(h[6:],)for h in[l.get('href')for l in bs4.BeautifulSoup(r.get('https://en.wikipedia.org/wiki/'+k[-1]).content).find(id='content').find_all('a')]if None!=h>h[:6]=='/wiki/'[':'in h:]]
print(k)

```

Input and output are page titles.

**Example outputs**

`OVS_(company)` =\> `('OVS_(company)', 'Albania', 'Rome')`

`Code_golf` =\> `('Code_golf', 'Source_code', 'Free_speech', 'Rome')`
> 3 votes

# Answer
# Java 10, ~~451~~ 418 - 30 = 388 bytes

```
p->{for(;;)for(var t:p){if(t.endsWith(" Rome"))return t;String w="https://en.wikipedia.org/wiki/",c=t;try{try(var b=new java.io.BufferedReader(new java.io.InputStreamReader(new java.net.URL(w+t.replaceAll(".*?(\\S+)$","$1")).openStream()))){for(;(i=b.readLine())!=null;)c+=i;}for(var h:c.replaceAll(".*ole=.mai(.*)id=.catl.*","$1").split("href=./wiki/"))p.add(t+" "+h.substring(0,h.indexOf('"')));}finally{continue;}}}

```

Extremely slow would be an understatement, but it works..

Takes just the page (wrapped into a `CopyOnWriteArraySet<String>`) as input. Outputs the pages space-delimited as String.

Example run locally:

```
Input:  "Java_(programming_language)"
Output: "Java_(programming_language) Rust_(programming_language) Rome"

```

**Explanation:**

```
p->{                           // Method with Set<String> parameter and String return-type
  for(;;)                      //  Loop indefinitely:
    for(var t:p){              //   Loop over each String `t` in the input-CopyOnWriteArraySet:
                               //   (it's a CopyOnWriteArraySet, since we otherwise wouldn't
                               //    be able to add while iterating)
      if(t.endsWith(" Rome"))  //    If the current String `t` ends with " Rome"
        return t;              //     Return it as result
    String w="https://en.wikipedia.org/wiki/",
                               //    String with the base url of Wikipedia
           c=t;                //    Content-String (starts at `t` instead of "" to save a byte)
    try{try(var b=new java.io.BufferedReader(new java.io.InputStreamReader(new java.net.URL(w
                               //    Go to the Wikipedia website
          +t.replaceAll(".*?(\\S+)$","$1")
                               //    with everything after the last space in `t` as page
            ).openStream()))){ //    And open this website as a try-with-resources BufferedReader
        for(;(i=b.readLine())!=null;)
                               //     Read all lines of the page:
          c+=i;}               //      And append each line to the content-String
      for(var h:c.replaceAll(".*ole=.mai(.*)id=.catl.*","$1")
                               //    Take the content between 'ole="mai' and 'id="catl':
                               //    ('role="main"' and 'id="catlinks"')
                 .split("href=./wiki/"))
                               //    Split it on 'href="/wiki/', and loop over each part:
        p.add(                 //     Add to the input-Set:
           t+" "               //      The current String with an appended space
           +h.substring(0,h.indexOf('"')));
                               //      Appended with the leading part up until the first '"'
    }finally{                  //   If any error occurs accessing the page (i.e. going to "wiki/.")
      continue;}}}             //    Skip it, and go to the next iteration

```
> 2 votes

---
Tags: code-golf, graph-theory, internet, search
---


title: Branch Out - Monkey Edition

text:
# Question
Title: Branch Out - Monkey Edition
### The Monkey has swung home to find his tree all in pieces.

He likes order and scoops up all his 'tree-parts' and sets them out in `3` groups.

The Monkey's `3` nested lists:

```
STEP = [['S', '1', 'B', '3'], ['S', '3', 'B', '11'], ['S', '5', 'B', '12'], ['S', '4', 'B', '13'], ['S', '2', 'B', '14']]

TRANSITION = [['T', '2', 'B', '4'], ['T', '7', 'B', '4'], ['T', '3', 'S', '4'], ['T', '5', 'S', '5'], ['T', '1', 'S', '2'], ['T', '8', 'S', '2'], ['T', '6', 'S', '1'], ['T', '9', 'S', '2'], ['T', '4', 'S', '1'], ['T', '10', 'S', '1']]

BRANCH = [['B', '3', 'T', '1'], ['B', '3', 'T', '7'], ['B', '4', 'S', '3'], ['B', '11', 'T', '3'], ['B', '11', 'T', '5'], ['B', '12', 'T', '6'], ['B', '12', 'T', '8'], ['B', '13', 'T', '4'], ['B', '13', 'T', '9'], ['B', '14', 'T', '2'], ['B', '14', 'T', '10']]

```

Each element holds information as such:

```
# Example

STEP[0]  =  ['S', '1', 'B', '3']

```

*Where:*

* 'S' is the `STEP` type
* '1' is the `STEP` number id
* 'B' is the linked `BRANCH` type
* '3' is the linked `BRANCH` number id

Starting from a `STEP` the data is all linked, so using the linked reference you can find the next element and the next until another `STEP` is reached.

*This is some parameters of the data:*

* `STEPS` are connected to single `BRANCHES`
* `BRANCHES` are connected to one or more `TRANSITIONS`
* `TRANSITIONS` can be connected to a single `BRANCH` or `STEP`

The `BRANCH` data can have a fork where a single `BRANCH` id has one or more options for `TRANSITIONS`.

Re-create this monkey's tree (nested list format is fine) in the shortest way possible (he is not a fan of long instructions):

```
           [S1]
            |
          B3|_________
            |         |
           [T1]     [T7]
            |         |
            |       B4|
            |         |
           [S2]     [S3]

```

And list all the routes on this tree:

```
Routes = [[S1, B3, T1, S2], [S1, B3, T7, B4, S3]]

```

UPDATE: This is Code-golf and from the data given you need to output the display of the tree ( This can be different from my example but requires the same elements to be displayed in any format) and as you cycle through the problem to output all the possible routes as a BONUS.

### Notes:

* This is a single-rooted tree
* You may use a different format for input but please explicitly state the input format in your solution

# Answer
# Java (JDK), 570 bytes

```
t->{return "Routes = "+Arrays.deepToString(Arrays.stream(r(t.get(0).get(0),t,t.get(0).get(0)).split("\\[")).filter(d->d.endsWith("]")).map(d->d.replaceAll("]", "")).map(d->d.split("(?=[A-Z])")).collect(Collectors.toList()).toArray());};String r(String s, List<List<String>>t, String b){List<String>o = t.stream().filter(e->e.get(0).equals(s)).map(e->e.get(1)).collect(Collectors.toList());if(s.matches("^S(?!(?:1)$)\\d+"))return s;if(o.size()>1){String x="";for(String n:o){x+="["+b+r(n,t,b+n)+"]";}return x;}if(o.size()==1)return s+r(o.get(0),t,b+o.get(0));return "]";}

```

As you may notice by my code I´m still learning a lot every day. My answer is neighter pretty nor short and I honestly even hope this works for different testcases even though I tested a couple. But I hope that this question gets the attention it deserves and there will be more answers I can learn from.

## INPUT

```
String[][] STEP = { { "S1", "B3" },  ... ,{ "B14", "T2" }, { "B14", "T10" } };
List<List<String>> tupels = Arrays.stream(STEP).map(Arrays::asList).collect(Collectors.toList());
z(tupels);

```

I converted your given Input into an 2D-Java-Array `String[][]` and converted that into a `List<List<String>>`.

## CODE

The first method calls a recursive method to get all routes and formats the output.

```
t->{
return "Routes ="+Arrays.deepToString(
  Arrays.stream(r(t.get(0).get(0),t,t.get(0).get(0)).split("\\["))
 .filter(d->d.endsWith("]")).map(d->d.replaceAll("]", ""))
 .map(d->d.split("(?=[A-Z])")).collect(Collectors.toList()).toArray());
};

```

The second method is the recursive method which gathers all the possible routes

```
String r(String s, List<List<String>>t, String b){
  List<String>o =t.stream().filter(e->e.get(0).equals(s)).map(e->e.get(1))
  .collect(Collectors.toList());
  if(s.matches("^S(?!(?:1)$)\\d+"))
    return s;
  if(o.size()>1){
    String x="";
    for(String n:o){
      x+="["+b+r(n,t,b+n)+"]";
    }
    return x;
  }
  if(o.size()==1)
    return s+r(o.get(0),t,b+o.get(0));
  return "]";
}

```

Try it online!
> 2 votes

---
Tags: code-golf, recursion, algorithm, tree-traversal
---


# Question
Title: Can this value be made with unique coins and/or notes?
Write a program which calculates if an inputted monetary value, as an integer, can be represented by a unique combination of coins and/or notes, that meaning the same coin/note cannot be used more than once.

Your program should take a value as input, and can take a list of coin/note values either via input or via your language's equivalent of an array. The list of coins/notes should be able to change, so make sure it's clear where this is defined if you're using a constant.

Your program should output any truthy/falsy value respectively.

Please note that outputting the list of coins/notes that make up the value is **not** required.

# **EXAMPLE**

Using the UK pound, (£1.00 = 100 and £420.69 = 42069)

```
coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000]

```

The following will output true:

```
6 (1, 5)
15 (10, 5)
88 (1, 2, 5, 10, 20, 50)
512 (500, 10, 2)
7003 (5000, 2000, 2, 1)

```

The following will output false:

```
4
209
8889
4242424242
[ANYTHING ABOVE 8888]

```

# **ALTERNATIVE TEST DATA (US Dollar)**

```
coins = [1, 5, 10, 25, 50, 100, 200, 500, 1000, 2000, 5000, 10000]

```

Good luck!

# Answer
> 13 votes
# Brachylog 2 (TIO Nexus), 2 bytes

```
⊇+

```

Try it online!

Takes the list of coins either via standard input or via prepending it to the start of the program as an array literal (either will work, so it's up to you as to which you feel is "more legitimate"; the former is allowed by default PPCG rules, the latter specifically allowed by the question); and takes the value to produce as a command-line argument.

## Explanation

This program makes use of implementation details of the way TIO Nexus's wrapper for Brachylog functions; specifically, it lets you give a command-line argument to give input via the Output. (This wasn't envisaged in the original design for Brachylog; however, languages are defined by their implementation on PPCG, and if an implementation comes along that happens to do what I need, I can therefore take advantage of it.) That means the program looks like this:

```
⊇+
⊇   Some subset of {standard input}
 +  sums to {the first command-line argument}

```

As a full program, it returns a boolean value; `true.` if all the assertions in the program can be simultaneously satisfied, or `false.` if they can't be.

(A reminder, or for people who don't already know: Brachylog 2 uses its own character encoding in which  is a single byte long.)

# Answer
> 11 votes
# 05AB1E, 4 bytes

```
æOså

```

Explanation:

```
æ      Calculate the powerset of the first input
 O     Sum each element
  s    Put the second input at the top of the stack
   å   Check whether the input is in the powerset sum.

```

Try it online!

# Answer
> 5 votes
# Mathematica, 25 bytes

```
!FreeQ[Tr/@Subsets@#,#2]&

```

Pure function taking an array of coin-values as the first argument and the target integer as the second argument, and returning `True` or `False`.

# Answer
> 4 votes
# Jelly, 6 bytes

```
ŒPS€e@

```

Try it online!

# Answer
> 3 votes
# Retina, ~~52~~ 31 bytes

```
\d+
$*
^((1+) |1+ )+(?<-2>\2)+$

```

Try it online! Takes input as a space-separated list of coins and notes followed by the desired value. Edit: Saved 18 bytes thanks to @Kobi who debugged my code. Explanation: The first two lines simply convert from decimal to unary. The third line then captures the list of coins and notes. The alternation allows the engine to backtrack and choose not to capture specific coins/notes. The balancing group then matches the value against all suffixes of the the capture list (unnecessary but golfier.)

# Answer
> 3 votes
# Haskell, 28 bytes

The operator function `(#)` takes an integer and a list of integers (or, more generally, any `Traversable` container of numbers) and returns a `Bool`.

Use as `6#[1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000]`.

```
c#l=elem c$sum<$>mapM(:[0])l

```

Try it online!

# How it works

* `c` is the desired value and `l` the list of coin values.
* `mapM(:[0])l` maps `(:[0])` over `l`, pairing each value with 0, and then constructs the cartesian product, giving lists where each element is either its corresponding value in `l`, or 0.
* `sum<$>` sums each combination, and `elem c$` checks if `c` is in the resulting list.

# Answer
> 2 votes
## JavaScript (ES6), ~~81~~ ~~69~~ ~~67~~ 64 bytes

Takes the list of coins `c` and the target amount `a` in currying syntax `(c)(a)`. Returns `0` or `true`.

```
c=>g=(a,m=1)=>c.map((c,i)=>x-=c*(m>>i&1),x=a)&&!x||x-a&&g(a,m+1)

```

### Test cases

```
let f =

c=>g=(a,m=1)=>c.map((c,i)=>x-=c*(m>>i&1),x=a)&&!x||x-a&&g(a,m+1)

const pound = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000];

console.log(f(pound)(6))
console.log(f(pound)(15))
console.log(f(pound)(88))
console.log(f(pound)(512))
console.log(f(pound)(7003))

console.log(f(pound)(4))
console.log(f(pound)(209))
console.log(f(pound)(8889))
console.log(f(pound)(4242424242))
```

# Answer
> 2 votes
# R, ~~88~~ 83 bytes

*-5 bytes thanks to @Jarko Dubbeldam*

returns an anonymous function. It generates all the possible combinations of coins (using `expand.grid` on pairs of `T,F`) and checks if the value(s) are present. `k` is coins since `c` is a reserved word in R. Can check multiple values at once.

```
function(k,v)v%in%apply(expand.grid(Map(function(x)!0:1,k)),1,function(x)sum(k[x]))

```

Try it online!

# Answer
> 2 votes
# Brachylog, 7 bytes

```
tT&h⊇+T

```

Try it online!

## How it works

```
tT&h⊇+T
tT      the second input is T
  &     and
   h    the first input
    ⊇   is a superset of a set
     +  that sums up to
      T T

```

## Including the combination, 9 bytes

```
tT&h⊇.+T∧

```

Try it online!

# Answer
> 2 votes
# Java (OpenJDK 8), 125 bytes

```
boolean f(int[]c,int n){int l=c.length;if(l<1)return n==0;int[]a=java.util.Arrays.copyOf(c,l-1);return f(a,n-c[l-1])|f(a,n);}

```

Try it online!

# Answer
> 2 votes
# Prolog (SWI), 46 bytes

```
a([],0).
a([H|T],X):-Y is X-H,(a(T,Y);a(T,X)).

```

Try it online!

Fork of my Python answer.

# Answer
> 2 votes
# Jelly, 4 bytes

```
ŒP§i

```

Try it online!

Powerset, vector sum, index.

Powerset gets all subsets, sum all the subsets, and check for the occurrence of the second argument

Returns 0 as the falsy value, and anything else otherwise.

# Answer
> 1 votes
# Japt, 7 bytes

```
à mx èN

```

Try it online! Outputs `0` for falsy, a positive integer for truthy.

### Explanation

```
à mx èN
          // Implicit: U = input array, V = input integer, N = array of all inputs
à         // Take all combinations of U.
  mx      // Map each combination to its sum.
     è    // Count the number of items in the result which also exist in
      N   //   the array of inputs.
          // This returns 0 if no combination sums to V, a positive integer otherwise.
          // Implicit: output result of last expression

```

# Answer
> 1 votes
# Python 3, 52 bytes

5 bytes thanks to ovs.

```
f=lambda c,n:c and f(c[1:],n-c[0])|f(c[1:],n)or n==0

```

Try it online!

# Answer
> 1 votes
# Bash + GNU utilities, 56 39

```
printf %$2s|egrep "^ {${1//,/\}? {}}?$"

```

Input denomination list (unsorted) is given as a comma-separated list. Input list and value are given as a command-line parameters.

Output given in the form of the shell return code. Inspect with `echo $?` after running the script. `0` means truthy, `1` means falsy.

Try it online.

* `printf %$2s` outputs a string of `value` spaces
* `"^ {${1//,/\}? {}}?$"` is a shell expansion that expands the denomination list to a regex like `^ {1}? {2}? {5}? {10}? ... $`. It turns out that the `egrep` regex engine is smart enough to correctly match with this, regardless of what order the denominations are in
* `egrep` checks if the string of spaces matches the regex

# Answer
> 1 votes
# Ruby, 39 bytes

Returns `nil` as the falsy value, and the smallest coin value in the list that makes up the number as truthy (all numbers are truthy in Ruby).

```
f=->c,n{n!=0?c.find{|i|f[c-[i],n-i]}:1}

```

Do beware, however, that this algorithm is insanely slow, with `O(C!)` time complexity, where `C` is the length of the coin list. It eventually finishes, but most test cases will time out on most online interpreters, even `f(UK_POUND, 5)`.

Here is a 41-byte version that finishes much faster by adding an extra ending condition, and is much harder to actually time out

```
f=->c,n{n>0?c.find{|i|f[c-[i],n-i]}:n==0}

```

Try it online!

# Answer
> 1 votes
## C, 66 bytes

```
m;v;f(n){for(m=1e5;m/=10;)for(v=5;n-=n<v*m?0:v*m,v/=2;);return!n;}

```

See it work here.

## C, 53 bytes

```
g(c,w,n)int*c;{for(;n-=n<c[--w]?0:c[w],w;);return!n;}

```

This variant takes the coin array, which defeats the purpose of this problem, because it comes down to simple subtraction.

The first argument is the coin array, the second is the coin count, and the third is the value.

## C, 48 bytes

```
g(c,n)int*c;{for(;n-=n<*c?0:*c,*++c;);return!n;}

```

An alternative to the previous variant. It assumes that the coin array can be reversed and zero terminated.

# Answer
> 0 votes
# Pyth, 6 bytes

```
/sMtyE

```

Test suite.

# Answer
> 0 votes
# CJam, ~~18~~ 17 bytes

```
q~_,2\m*\f.*::+#)

```

Try it online!

**Explanation**

```
q~                  e# Read and eval input.
  _,                e# Duplicate the money list and take its length.
    2\m*            e# Take the (length)th Cartesian power of [0 1].
        \f.*        e# Element-wise multiplication of each set of 0's and 1's with the money
                    e#   list. This is essentially the powerset, but with 0s instead of
                    e#   missing elements.
            ::+     e# Sum each set.
               #    e# Find the index of the desired amount in the list. (-1 if not found)
                )   e# Increment. -1 => 0 (falsy), anything else => nonzero (truthy)

```

# Answer
> 0 votes
# C (gcc), 91 bytes

```
i,j,c[]={1,2,5};f(n){for(i=1000;i;i/=10)for(j=2;j>=0;j--)n-=n<i*c[j]?0:i*c[j];return n==0;}

```

Try it online!

# Answer
> 0 votes
# PHP, 70 Bytes

prints 1 for true and nothing for false

```
<?foreach($_GET[1]as$v)$i-=$v*$r[]=($i=&$_GET[0])/$v^0;echo max($r)<2;

```

Try it online!

# Answer
> 0 votes
# Octave, 39 bytes

```
 @(L,n)any(cellfun(@sum,powerset(L))==n)

```

An anonymous function that takes an array of coin-values as the first argument and the target integer as the second argument, and returns true or false.

Try it online!

# Answer
> 0 votes
# Mathematica, 42 bytes

```
ListQ@NumberDecompose[#,Sort[#2,Greater]]&

```

**input**

> \[15,{10,5}\]

---
Tags: code-golf, math
---


title: Is it really a comcoin?

text:
# Question
Title: Is it really a comcoin?
## Very interesting background

Comcoins are a currency like any other. The residents of Multibaseania (an economically robust system of city-states with very few residents in a galaxy far, far away) use Comcoins to conduct transactions between themselves. Comcoins are represented by unique codes on special not-paper slips, and when you pay you give the vendor your slip.

However, just like any currency, there are those villainous types that try to take advantage of the system and inflate the currency because they are bored.

To combat this unquestionably illegal behavior, the Multibaseanian governments came together and devised a way to prove that the money is legitimate. The top idea from the think tank was: whenever a Comcoin is given to a vendor, the vendor runs a program that checks if it is legitimate. How does one know if a Comcoin is legitimate?

> **A legitimate Comcoin is one where:**
>
> When the Comcoin's unique code is converted into the bases 2-10, inclusive, that number is composite (i.e. not prime). Also, all of the unique code's digits in base 10 are either 1 or 0, and its length in base 10 is between 1 and 5 inclusive.

**Very important example:** in base 5, 111 is 421. Even though 111 is not prime, 421 is, so the Comcoin is invalid.

## The challenge

Write a function or program that takes a Comcoin's code (a number), which is in base 10 and is an integer. Then, print or return a truthy or falsy value depending on whether that Comcoin is legitimate (criteria above), respectively.

## I/O examples

```
Input     Output

101         False // because it is prime in base 2
1010        True
10101       True
1010111     False // because it is longer than 5 digits
123         False // because it does not contain *only* 0's and 1's
10111       False // because it is prime in base 6

```

This is code golf, so shortest code in bytes wins!

## Edit

A Comcoin is not a number that is not prime, but is a number that is composite.

Inspiration from qualification round of Google CodeJam 2016.

# Answer
> 3 votes
# MATL, 20 bytes

```
n6<G50<9:Q"G@ZAZp~vA

```

Input is a string.

**Try it online!**

### Explanation

```
n6<    % take input implicitly. Is length less than 6?
G50<   % push input again. Array that contains true for digits less than 2
9:Q    % push array of bases: [2,3,...,10]
"      % for each
  G    %   push input again
  @    %   push current base
  ZA   %   interpret input as if it were in that base, and convert to decimal
  Zp~  %   true for composite numbers
  v    %   concatenate vertically all results up to now
  A    %   true if all results were
       % end for each implicitly
       % display implicitly

```

# Answer
> 10 votes
# Python 2, 62 56 49 bytes

```
lambda n:max(`n`)<"2"and 0x5d75d750>>int(`n`,2)&1

```

Credit to @Sp3000 for the `max` trick to ensure binary digits.

# Answer
> 4 votes
## JavaScript (ES6), ~~38~~ 27 bytes

```
n=>2641714512>>'0b'+n&n<1e5

```

Port of @orlp's Python answer, except that JavaScript's precedence and weak typing allows me to shift the integer even if it's not valid in base 2, and then bitwise and it with the boolean. Returns 0 or 1 as appropriate. Note that I'm not using @orlp's constant any more, instead I'm assuming the following list of comcoins is valid:

> 100
> 110
> 1000
> 1010
> 1011
> 1100
> 1110
> 10000
> 10010
> 10100
> 10101
> 10110
> 11000
> 11010
> 11011
> 11100
> 11111

Edit: Fixed to check the length of the comcoin, since JavaScript's shift operator works modulo 32.

# Answer
> 2 votes
# Julia, ~~83~~ 81 bytes

```
f(x,s="$x")=endof(s)<6&&all(c->c∈"01",s)&&!any(b->isprime(parse(Int,s,b)),2:10)

```

This is a function that accepts an integer and returns a boolean. It's a straightforward check on the conditions of being a Comcoin:

* Length as a string between 1 and 5 inclusive: `endof(s)<6`
* All zeros and ones: `all(c->c∈"01",s)`
* No primes in any base from 2 to 10: `!any(b->isprime(parse(Int,s,b)),2:10)`

Saved 2 bytes thanks to Luis Mendo!

# Answer
> 2 votes
# JavaScript (ES6), 37

~~This should work better than the current ES6 answer~~ Now the other ES6 answer is clearly better

**Edit** 0 and 1 not valid, the magic number changes

```
n=>180006585..toString(2)['0b'+n-4]|0

```

**Test** (see below to see how the magic number is built)

```
F=n=>180006585..toString(2)['0b'+n-4]|0

console.log=(...x)=>O.textContent+=x+'\n'

function test() {
  var x=+I.value
  console.log(x+' '+F(x))
}

test()

// How the mask is built

isPrime=x=>{
  if(x<=2)return x==2
  if(x%2==0)return false
  var i,q=Math.sqrt(x)
  for(i=3;i<=q;i+=2)
    if(x%i==0)return false
  return true;
}

buildMask=_=>{
  var n,m,i,p,mask=''
  for(i=1;i<32;i++)
  {
    n=+i.toString(2)
    for(p=0,b=10;b>1;--b)
    {
      m=+n.toString(b)
      p=m<2 || isPrime(m)
      if(p)
      {
        console.log('N',i,n,m,b)
        break;
      }
    }
    mask+=p?0:1
    if(!p) console.log('Y',i,n)
  }
  console.log(mask, parseInt(mask,2))
  // result
  // 0001010101110101010111010111001,180006585}
}
```

```
<input value='11111' type='number' id=I oninput='test()'><pre id=O></pre>
```

# Answer
> 1 votes
# Ruby, ~~81~~ ~~80~~ 74 bytes

Anonymous function, takes input as a string and returns `true` or a falsy value (`false` if it fails a prime check, `nil` if it contains characters that aren't `0` or `1`)

Uses some regex magic suggested by @QPaysTaxes, which thankfully works (within reasonable time) because of the promise that the coin signature has max 5 characters. Also, I forgot to actually check for the length, so only 1 byte was saved overall.

Since `0` and `1` aren't composite numbers in any base, I could save more bytes by modifying my regex.

```
->n{n=~/^[01]{2,5}$/&&(2..10).map{|b|?1*n.to_i(b)=~/^(..+?)\1+$/}&[p]==[]}

```

Old version using Ruby's built-in prime checker. **85 bytes** after properly checking for length.

```
->n{require'prime';n=~/^[01]{1,5}$/&&(2..10).map{|b|Prime.prime? n.to_i(b)}&[!p]==[]}

```

# Answer
> 1 votes
# Mathematica, 97 bytes

```
#<1*^5&&Tr@DigitCount[#][[2;;-2]]<1&&FromDigits@IntegerDigits[#,a+1]~Table~{a,9}~NoneTrue~PrimeQ&

```

Hey, at least I tried...

```
#<1*^5&&Tr@DigitCount[#][[2;;-2]]<1&&FromDigits@IntegerDigits[#,a+1]~Table~{a,9}~NoneTrue~PrimeQ&
#<1*^5&&                                                                                less than 100000?
        Tr@DigitCount[#][[2;;-2]]<1&&                                                             no digits 2-9?
                                     FromDigits@IntegerDigits[#,a+1]~Table~{a,9}~NoneTrue~PrimeQ& composite in all bases?

```

# Answer
> 1 votes
# 05AB1E, ~~18~~ 17 bytes

```
ΘIg5›ITLBpàI1K`O_

```

-1 byte and bug-fix thanks to *@Grimmy*.

Outputs `1`/`0` for truthy/falsey respectively.

Try it online or verify all test cases or verify the first 40 binary numbers and 100 regular numbers.

**(Now longer) 18 bytes alternative:**

```
46bICèIт@Ig6‹PITм+

```

Outputs `1` for truthy and a non-1 integer for falsey (note: only `1` is truthy in 05AB1E, so this is allowed according to the meta).

Try it online or verify all test cases or verify the first 40 binary numbers and 100 regular numbers.

Both programs also works for edge-case `1`, unlike some other answers.

**Explanation:**

```
Θ       # Check if the (implicit) input is exactly 1 (1 if 1; 0 otherwise)
Ig      # Push the input again, and pop and push its length
  5›    # Check if this length is larger than 5 (1 if length>5; 0 if length<=5)
I       # Push the input again
 TL     # Push a list in the range [1,10]
   B    # Convert the input to each of those bases
    p   # Check for each whether it is a prime (1 if prime; 0 if not)
     à  # Pop and push the maximum to check if any are a prime
I       # Push the input yet again
 1K     # Remove all 1s
   `    # And push all remaining digits separated to the stack
O       # Sum all values on the stack
 _      # And check whether it is exactly 0 (1/truthy if 0; 0/falsey if >0)
        # (after which this result is output implicitly)

46b     # Push 46 as binary: 101110
   IC   # Push the input, and convert it from binary to an integer
        # (NOTE: unfortunately also works for non-binary inputs, so we'll fix those later)
     è  # Use that to index into the 101110 (0-based and with wraparound)
Iт@     # Push the input again, and check that it's >= 10
Ig6‹    # Push the input again, and check that its length is < 6
P       # Take the product of all values on the stack
 I      # Push the input again
  Tм    # Remove all 1s and 0s
    +   # And add any remaining digits to the product
        # (after which the result is output implicitly)

```

# Answer
> 0 votes
# Factor, 128 bytes

```
[ dup [| a | 2 10 [a,b] [ a swap base> prime? not ] all? ] swap [ [ [ 49 = ] [ 48 = ] bi or ] all? ] [ length 6 < ] bi and and ]

```

I'll try to golf this more in a sec.

Well, here's the *less* golfed version I thought might be shorter, but it's 133 bytes...

```
[ [ [let :> a 2 10 [a,b] [ a swap base> prime? not ] all? ] ] [ [ [ [ 49 = ] [ 48 = ] bi or ] all? ] [ length 6 < ] bi ] bi and and ]

```

Actually ungolfed:

```
: comcoin? ( a -- t/f )
  [
    [let :> a
      2 10 [a,b] [ a swap base> prime? not ] all?
    ]
  ] [
    [ [ [ 49 = ] [ 48 = ] bi or ] all? ]
    [ length 6 < ] bi
  ] bi
  and and ;

```

# Answer
> 0 votes
# Python, ~~161~~ 152 bytes

*Sigh*. Assign the lambda to use it.

```
def p(n):
 i=a=n
 while i>2:i-=1;a*=n%i
 return a>1
lambda s:all([all(map(lambda i:not p(int(s,i)),range(2,11))),filter(lambda i:i in"01",s)),len(s)<6])

```

# Answer
> 0 votes
# Python 3, 222 bytes

I wanted to try to do the naive method purely functionally, without looping. Here it is.

```
(lambda A:all([F(A)for F in[lambda r:all(map(lambda s:not(lambda i,b:lambda n:list(filter(lambda i:not n%i,range(2,n)))(int(i,b))(r,s),range(2,11))),lambda r:0!= len(filter(lambda d:d not in"01",r)),lambda r:0<len(r)<6]]))

```

Ungolfed:

```
(lambda A:
    all(
        [F(A) for F in [
            lambda r: all(
                map(
                    lambda s:
                        not(
                            lambda i, b:
                                lambda n:
                                    list(filter(
                                        lambda i: not n % i, range(2, n)))
                            )(int(i, b))(r, s),
                            range(2, 11))),
            lambda r: 0 != len(filter(lambda d: d not in "01", r)),
            lambda r: 0 < len(r) < 6
            ]
        ]
    )
)

```

---
Tags: code-golf, number-theory, primes, base-conversion
---


title: Generate A298757

text:
# Question
Title: Generate A298757
## Miller-Rabin test

Given a base \\$b\\$ and an odd number \\$n\\$:

Write \\$n\\$ as \\$2^{s}\times d + 1\\$ where \\$d\\$ is odd

\\$n\\$ is a *strong probable prime* if either:

* \\$b^d\equiv 1 \pmod n\\$
* \\$b^{d\cdot2^r}\equiv -1 \pmod n\\$

for any non-negative \\$r\\$ strictly less than \\$s\\$.

A *strong probable prime* which is composite is a *pseudoprime*.

See en.wikipedia.org/wiki/Strong\_pseudoprime for more information.

## Challenge

Make a script that generates very good bases (bases, \\$b\\$, for which the first *pseudoprime* is larger than with any smaller base).

## Additional rules

1. Your script should be as fast as possible.
2. Your script should not use a lookup table (for the output, lookup table for primes is fine).
3. You may use external libraries as long as that library is written in the same language.
4. Speed will be measured in terms of how many terms it can generate in 1 min.

## Python implementation of the Miller-Rabin test

```
def miller(n, b):
    if n % 2 == 0:
        return n == 2
    d = n - 1
    s = 0
    while d % 2 == 0:
        d >>= 1
        s += 1
    if pow(b, d, n) == 1:
        return True
    elif any(pow(b, d * 2 ** r, n) == n - 1 for r in range(s)):
        return True
    return False

```

An entry is valid if it will never stop producing better bases and it won't produce a base worse than it has generated before.

Example of a valid python entry:

```
from sympy import isprime
base = 2
record = 2
while True:
    number = 9
    while True:
        while isprime(number):
            number += 2
        if miller(number, base):
            if number > record:
                record = number
                print(base)
            break
        number += 2
    base += 1

```

Little over 20 sec to generate:

```
2
1320
4712
5628
7252
7852
14787
17340
61380
78750

```

My code generates the above in ca. 20 sec on my laptop, and generates one more term in 72 sec. so the score is 10 terms.

Arnauld pointed out that the challenge is just to generate A298757.

Sympy's isprime is not the problem as it runs in less than .5 sec for 700 digit numbers.

Edit: I didn't mean to give advantage to specific languages like C, so I will convert them to python.

# Answer
# Rust, \\$n = 15\\$

```
use std::collections::VecDeque;

fn miller(n: u64, mut b: u64) -> bool {
    let s = (n - 1).trailing_zeros();
    let mut t = n - 1 >> s;
    b %= n;
    let mut a = b;
    while t != 1 {
        b = b * b % n;
        t >>= 1;
        if t & 1 != 0 {
            a = a * b % n;
        }
    }
    if a == 1 || a == n - 1 {
        return true;
    }
    for _ in 1..s {
        a = a * a % n;
        if a == n - 1 {
            return true;
        }
        if a == 1 {
            return false;
        }
    }
    return false;
}

fn main() {
    let mut record = 2;
    let mut factor = VecDeque::new();

    for base in 2.. {
        factor.clear();
        let mut q = 3;
        let mut qq = q * q;
        for n in (9..).step_by(2) {
            let mut p = factor.pop_front().unwrap_or(0);

            if n == qq {
                if p == 0 {
                    p = q;
                }
                q += 2;
                qq = q * q;
            } else if p == 0 {
                continue;
            }

            if miller(n as u64, base) {
                if n > record {
                    println!("{}", base);
                    record = n;
                }
                break;
            }

            let mut m = p - 1;
            while *factor.get(m).unwrap_or(&0) != 0 {
                m += p;
            }
            if factor.len() < m + 1 {
                factor.resize(m + 1, 0);
            }
            factor[m] = p;
        }
    }
}

```

Try it online!
> 2 votes

# Answer
# JavaScript (Node.js), \\$n=15\\$

This is essentially just a port of the example implementation, with an optimized modular exponentiation and a cache for odd composite numbers.

Further optimized by merging `powMod()` and `miller()`, as Anders Kaseorg first did.

```
function miller(n, b) {
  let s = 31 - Math.clz32(n - 1 & 1 - n);
  let t = n - 1 >> s;
  let k = b %= n;

  while(t != 1) {
    b = (b * b) % n;

    if((t >>= 1) & 1) {
      k = (k * b) % n;
    }
  }
  if(k == 1 || k == n - 1) {
    return true;
  }
  while(k != 1 && --s) {
    if((k = (k * k) % n) == n - 1) {
      return true;
    }
  }
  return false;
}

function isPrime(n) {
  let m = n ** 0.5;

  for(let d = 3; d <= m; d += 2) {
    if(!(n % d)) {
      return false;
    }
  }
  return true;
}

function nthOddComposite(n) {
  if(n < oddComposite.length) {
    return oddComposite[n];
  }

  let k;

  for(k = oddComposite[oddComposite.length - 1]; isPrime(k += 2);) {}
  oddComposite.push(k);

  return k;
}

let oddComposite = [ 9 ];
let ts = +new Date();

for(let i = 0, record = base = 2;; base++) {
  for(let j = 0;; j++) {
    number = nthOddComposite(j);

    if(miller(number, base)) {
      if(number > record) {
        record = number;
        console.log(
          ++i + '\tbase = ' + base + '\ttime = ' + ((new Date() - ts) / 1000).toFixed(2)
        );
      }
      break;
    }
  }
}

```

Try it online! (this TIO link has \\$n\le15\\$ as a hard-coded limit)

### Output

```
1       base = 2        time = 0.00
2       base = 1320     time = 0.02
3       base = 4712     time = 0.03
4       base = 5628     time = 0.04
5       base = 7252     time = 0.04
6       base = 7852     time = 0.05
7       base = 14787    time = 0.07
8       base = 17340    time = 0.07
9       base = 61380    time = 0.18
10      base = 78750    time = 0.22
11      base = 254923   time = 0.62
12      base = 486605   time = 1.14
13      base = 1804842  time = 4.05
14      base = 4095086  time = 9.13
15      base = 12772344 time = 28.41
--------------------------------------> time limit
16      base = 42162995 time = 94.23

```
> 1 votes

# Answer
# C++ (clang), \\$n=14\\$

```
#include <iostream>
#include <cmath>
#include <chrono>
#include <iomanip>

template <typename I>
bool isPrime(I n)
{
    if (n < 2) {
        return false;
    }
    if (n == 2 || n == 3) {
        return true;
    }
    if (n % 2 == 0 || n % 3 == 0) {
        return false;
    }
    I srt = std::sqrt(n);
    int inc = 4;
    for (I i = static_cast<I>(5); i <= srt; i += inc)
    {
        if (n % i == 0) {
            return false;
        }
        inc = 6 - inc;
    }
    return true;
}

template <typename I>
I pow(I base, I exp, I mod)
{
    I result = 1;
    for (;;)
    {
        if (exp & 1) {
            result = (result * base) % mod;
        }
        exp >>= 1;
        if (!exp) {
            break;
        }
        base = (base * base) % mod;
    }
    return result;
}

template <typename I>
bool miller(I n, I b)
{
    if (n % 2 == 0) return n == 2;
    I d = n - 1;
    I s = 0;
    while (d % 2 == 0)
    {
        d >>= 1;
        s += 1;
    }
    if (pow<I>(b, d, n) == 1)
    {
        return true;
    }
    else
    {
        for (int r = 0; r < s; ++r) {
            if (pow<I>(b, d * (1 << r), n) == n - 1) {
                return true;
            }
        }
    }
    return false;
}

template <typename I>
void genBase()
{
    auto start = std::chrono::steady_clock::now();
    I base = 2;
    I record = 2;
    int count = 0;
    while (true)
    {
        I number = 9;
        while (true)
        {
            while (isPrime(number))
            {
                number += 2;
            }
            if (miller(number, base))
            {
                if (number > record)
                {
                    record = number;
                    auto now = std::chrono::steady_clock::now();
                    auto diff = now - start;
                    std::cout << std::setw(3) << ++count << ". " << std::setw(10) << base <<
                        " @ " << std::setprecision(4) << std::chrono::duration<double, std::milli>(diff).count()/1000 << " s\n";
                }
                break;
            }
            number += 2;
        }
        base++;
    }
}

int main(){
    genBase<unsigned long long>();
    return 0;
}

```

Try it online!

Basically a port of the OP's Python solution.

### Output:

```
 1.          2 @ 0.001043 s
 2.       1320 @ 0.0234 s
 3.       4712 @ 0.06999 s
 4.       5628 @ 0.08394 s
 5.       7252 @ 0.1051 s
 6.       7852 @ 0.117 s
 7.      14787 @ 0.2111 s
 8.      17340 @ 0.244 s
 9.      61380 @ 0.8129 s
10.      78750 @ 1.022 s
11.     254923 @ 3.133 s
12.     486605 @ 5.843 s
13.    1804842 @ 21.69 s
14.    4095086 @ 48.38 s

```
> 1 votes

---
Tags: primes, fastest-code
---