# 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
• 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!

• Can we take input as a string like "4101", or does that fail the "clearly separated" rule? Commented Feb 17, 2020 at 15:12
• @Grimmy I assume that it stands for "Sesb", which is fine. Commented Feb 17, 2020 at 15:18
• The new title is much better
– RGS
Commented Feb 17, 2020 at 18:22
• Bloody vikings... Commented Feb 19, 2020 at 23:05
• May we take a decimal representation of the four values (e.g. [ 0, 1, 1, 2 ] as 112)? Commented Feb 22, 2020 at 20:15

# 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.

• -1 Byte Commented Feb 18, 2020 at 18:22
• How did you compute the overlaps? Did you do this by hand? :o
– RGS
Commented Feb 18, 2020 at 21:55
• @wilkben A nice idea! Post an answer and collect your bounty!
– xnor
Commented Feb 18, 2020 at 22:32
• @RGS Kind of. I wrote code to count and list the overlaps for each permutation. But I was too lazy to code up the graph algorithm to split them into paths, so I did a couple of the promising-looking ones by hand.
– xnor
Commented Feb 18, 2020 at 22:33
• @xnor I added an answer but I'm unable to edit the post you linked to claim the bounty. Commented Feb 19, 2020 at 14:23

# Python 3, 31 bytes

oct(0x20a00924204c00c048).count


Try it online!

• Congrats! I've posted a bounty and will wait the week before awarding it to draw more visibility to your answer. And if you're interested in more, I have plenty of answers to be beaten.
– xnor
Commented Feb 22, 2020 at 10:14

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

• A nice idea and well-executed. I'm curious how you found these chains. I'll post your bounty after wilkben's, since I can only have one on this question.
– xnor
Commented Feb 22, 2020 at 10:16
• I wonder, since the challenge allows input to be taken as a decimal number like 1102, whether this could be used for a mod chain on the number directly that saves on writing hash(). I expected because theses number are less well-distributed, they'll be harder separate with a mod chain, but it does give 6 more bytes to work with.
– xnor
Commented Feb 22, 2020 at 10:21
• I found chains by reducing the two sets in nested for loops continue-ing on intersection, only showing progressively shorter or equal length code, along with the sets (I spotted a {0, 1} along the way to give the <2 solution). I'm not sure we can take an integer due to "as long as they are clearly separated into 4 distinct values" and that 0112 is not 112 in Python. If we could then one trick might be something like lambda n:a**n/b%c%d. Commented Feb 22, 2020 at 14:53
• ...the exponentiation trick might lead to much shorter solutions with the hash too but the numbers are too big to make a naive search possible - maybe there is some maths that could be used to aid us there? Commented Feb 22, 2020 at 14:57
• (EDIT ^) $a^b\mod c=((a\mod c)^b)\mod c$ and $a^{d+e}=a^d\times a^e$ I guess... Commented Feb 22, 2020 at 15:06

# 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

• Really nice solution :D +1
– RGS
Commented Feb 17, 2020 at 18:16
• I don't know 05AB1E at all, but from the description, it sounds like something like 1101 would match even though it's not on the menu. How does the solution prevent that? Commented Feb 18, 2020 at 13:54
• @MichaelMior 1101 is on the menu. As explained in my answer, I take input as "Sesb", so 1101 stands for spam, eggs, and bacon, which is the fourth entry in the menu. Commented Feb 18, 2020 at 14:10
• Whoops, my mistake :) Does this mean there aren't any substrings which are not on the menu which appear when the menu is given in this order? Commented Feb 18, 2020 at 14:35
• @MichaelMior What do you mean by substrings? My answer doesn't have anything to do with substrings. Are you thinking of xnor's answer? Commented Feb 18, 2020 at 14:39

# 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
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.

# PHP, 615956343230 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.

# 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!

• It's funny because I thought about doing it in this way, and I thought about the string-array-splicing thing, but for some reason I never thought about doing both! I'll edit that in :) Commented Feb 17, 2020 at 17:46
• Down to 23 bytes. Commented Feb 17, 2020 at 18:02
• 21 bytes by using header-input. This is a very clever solution! using line-break comma-notation. I do try to avoid using newlines in Golfscript as a rule since it messes with my explanation block, but I can probably find an equivalent. Commented Feb 17, 2020 at 18:19
• What IO rule allows Golfscript to take hard coded input? I'm pretty sure there isn't one
– Jo King
Commented Feb 18, 2020 at 0:51
• @JoKing There is. Commented Feb 18, 2020 at 2:10

# 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!

• @Arnauld really nice, this essentially slices the end of the binary repr of this integer and then gets the least significant bit with &1. Right?
– RGS
Commented Feb 17, 2020 at 18:52
• Yes, that's correct. Commented Feb 17, 2020 at 18:58
• I've ended with the same answer as you! Mine does the opposite: 1 for valid and 0 otherwise. :-) Commented Feb 17, 2020 at 23:03

# 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.

• Nice golfing going here!!
– RGS
Commented Feb 17, 2020 at 23:04
• @RGS Great minds think alike! :D Commented Feb 17, 2020 at 23:08

# 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.

# 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 :)

• Here’s your 11. You could also have moved the first link in place of the ¢ and put a ¤ for 12 bytes. Commented Feb 18, 2020 at 0:26
• @NickKennedy thanks for the tip! I see you have encoded a different integer. How did you get it?
– RGS
Commented Feb 18, 2020 at 7:55
• I converted to binary with B left rotated the binary digits 1 place with ṙ1 converted back from binary with Ḅ and then converted to a base-250 integer with ḃØ⁵ịOJ. Commented Feb 18, 2020 at 7:57

# 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?

• Looks like some special characters are missing from your code. Commented Feb 17, 2020 at 17:45
• @Grimmy the unprintable characters don't show up Commented Feb 17, 2020 at 17:47
• Then please give an explanation of your code, since it's illegible otherwise. Commented Feb 17, 2020 at 20:20
• Does Japt's code page really include various unprintable characters or are you using a different one?
– Jo King
Commented Feb 18, 2020 at 0:48
• @JoKing Japt uses Latin-1, so 0x00 - 0x1F and 0x7F - 0x9F are all unprintables Commented Feb 18, 2020 at 3:42

# 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.

# Ruby, 51 41 36 bytes

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


Try it online!

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

# 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 Join.

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

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.

# 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.

# 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.

# 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

# 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ḥ


# JavaScript (V8), 3534 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.

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