27
\$\begingroup\$

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!

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

21 Answers 21

17
\$\begingroup\$

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.

| improve this answer | | | | |
\$\endgroup\$
  • 7
    \$\begingroup\$ -1 Byte \$\endgroup\$ – wilkben Feb 18 at 18:22
  • \$\begingroup\$ How did you compute the overlaps? Did you do this by hand? :o \$\endgroup\$ – RGS Feb 18 at 21:55
  • 1
    \$\begingroup\$ @wilkben A nice idea! Post an answer and collect your bounty! \$\endgroup\$ – xnor Feb 18 at 22:32
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – xnor Feb 18 at 22:33
  • \$\begingroup\$ @xnor I added an answer but I'm unable to edit the post you linked to claim the bounty. \$\endgroup\$ – wilkben Feb 19 at 14:23
7
\$\begingroup\$

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
| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ Really nice solution :D +1 \$\endgroup\$ – RGS Feb 17 at 18:16
  • \$\begingroup\$ 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? \$\endgroup\$ – Michael Mior Feb 18 at 13:54
  • \$\begingroup\$ @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. \$\endgroup\$ – Grimmy Feb 18 at 14:10
  • \$\begingroup\$ 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? \$\endgroup\$ – Michael Mior Feb 18 at 14:35
  • 1
    \$\begingroup\$ @MichaelMior What do you mean by substrings? My answer doesn't have anything to do with substrings. Are you thinking of xnor's answer? \$\endgroup\$ – Grimmy Feb 18 at 14:39
7
\$\begingroup\$

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:

enter image description here

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.

| improve this answer | | | | |
\$\endgroup\$
7
+100
\$\begingroup\$

Python 3, 31 bytes

oct(0x20a00924204c00c048).count

Try it online!

Based on @xnor's answer

| improve this answer | | | | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – xnor Feb 22 at 10:14
6
+200
\$\begingroup\$

Python 2,  29  28 bytes

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)

| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – xnor Feb 22 at 10:16
  • \$\begingroup\$ 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. \$\endgroup\$ – xnor Feb 22 at 10:21
  • \$\begingroup\$ 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. \$\endgroup\$ – Jonathan Allan Feb 22 at 14:53
  • \$\begingroup\$ ...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? \$\endgroup\$ – Jonathan Allan Feb 22 at 14:57
  • \$\begingroup\$ (EDIT ^) \$a^b\mod c=((a\mod c)^b)\mod c\$ and \$a^{d+e}=a^d\times a^e\$ I guess... \$\endgroup\$ – Jonathan Allan Feb 22 at 15:06
6
\$\begingroup\$

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.

| improve this answer | | | | |
\$\endgroup\$
5
\$\begingroup\$

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)

| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ 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 :) \$\endgroup\$ – Mathgeek Feb 17 at 17:46
  • 1
    \$\begingroup\$ Down to 23 bytes. \$\endgroup\$ – Grimmy Feb 17 at 18:02
  • \$\begingroup\$ 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. \$\endgroup\$ – Mathgeek Feb 17 at 18:19
  • \$\begingroup\$ What IO rule allows Golfscript to take hard coded input? I'm pretty sure there isn't one \$\endgroup\$ – Jo King Feb 18 at 0:51
  • 1
    \$\begingroup\$ @JoKing There is. \$\endgroup\$ – Grimmy Feb 18 at 2:10
3
\$\begingroup\$

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!

| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ @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? \$\endgroup\$ – RGS Feb 17 at 18:52
  • 1
    \$\begingroup\$ Yes, that's correct. \$\endgroup\$ – Arnauld Feb 17 at 18:58
  • 1
    \$\begingroup\$ I've ended with the same answer as you! Mine does the opposite: 1 for valid and 0 otherwise. :-) \$\endgroup\$ – Noodle9 Feb 17 at 23:03
3
\$\begingroup\$

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.

| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ Nice golfing going here!! \$\endgroup\$ – RGS Feb 17 at 23:04
  • 1
    \$\begingroup\$ @RGS Great minds think alike! :D \$\endgroup\$ – Noodle9 Feb 17 at 23:08
3
\$\begingroup\$

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.

| improve this answer | | | | |
\$\endgroup\$
3
\$\begingroup\$

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

| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ Here’s your 11. You could also have moved the first link in place of the ¢ and put a ¤ for 12 bytes. \$\endgroup\$ – Nick Kennedy Feb 18 at 0:26
  • \$\begingroup\$ @NickKennedy thanks for the tip! I see you have encoded a different integer. How did you get it? \$\endgroup\$ – RGS Feb 18 at 7:55
  • \$\begingroup\$ 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. \$\endgroup\$ – Nick Kennedy Feb 18 at 7:57
2
\$\begingroup\$

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?
| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ Looks like some special characters are missing from your code. \$\endgroup\$ – Grimmy Feb 17 at 17:45
  • \$\begingroup\$ @Grimmy the unprintable characters don't show up \$\endgroup\$ – Embodiment of Ignorance Feb 17 at 17:47
  • \$\begingroup\$ Then please give an explanation of your code, since it's illegible otherwise. \$\endgroup\$ – Mathgeek Feb 17 at 20:20
  • 1
    \$\begingroup\$ Does Japt's code page really include various unprintable characters or are you using a different one? \$\endgroup\$ – Jo King Feb 18 at 0:48
  • 2
    \$\begingroup\$ @JoKing Japt uses Latin-1, so 0x00 - 0x1F and 0x7F - 0x9F are all unprintables \$\endgroup\$ – Embodiment of Ignorance Feb 18 at 3:42
2
\$\begingroup\$

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.

| improve this answer | | | | |
\$\endgroup\$
2
\$\begingroup\$

Ruby, 51 41 36 bytes

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

Try it online!

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

| improve this answer | | | | |
\$\endgroup\$
1
\$\begingroup\$

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.

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.

| improve this answer | | | | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | | | | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | | | | |
\$\endgroup\$
1
\$\begingroup\$

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

| improve this answer | | | | |
\$\endgroup\$
1
\$\begingroup\$

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ḥ
| improve this answer | | | | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | | | | |
\$\endgroup\$
1
\$\begingroup\$

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

| improve this answer | | | | |
\$\endgroup\$

Your Answer

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

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