21
\$\begingroup\$

You work in a kitchen which has a peculiar rule. When you mix something into a pot you must always add at least one new ingredient.

So you can add pasta, oil, salt then pesto, but not pasta, pesto, salt and oil since pesto already contains salt and oil. You only have one pot per dish, so you can't mix ingredients in one pot and then dump that into another.

So we can say that mixing is an associative partial binary operation \$\otimes\$, which takes the union of two sets of ingredients, but only operates on pairs where the second set contains some element not in the first, so

\$ \{1,2\}\otimes\{6,2\} = \{6,1,2\} \$

but

\$ \{1,2,3\}\otimes\{1,3\} \$

is undefined.

Now this rule is annoying because it means you have to be careful about the order you combine things. Sometimes there are even recipes can't be followed because there's no way to mix all the parts without breaking the rule.

A recipe can be followed if there is a way to order the parts so that each part contains an ingredient not found in prior parts.

So if the parts of the recipe are:

\$ \{1,2,3,5\},\,\{5\},\,\{2,5,6\},\,\{1,2,4,5\},\,\{3,5\} \$

then they can be ordered:

\$ \{5\}\otimes\{3,5\}\otimes\{1,2,3,5\}\otimes\{2,5,6\}\otimes\{1,2,4,5\} \$

However

\$ \{1,2,3,5\},\,\{5\},\,\{2,4,5\},\,\{1,2,4,5\},\,\{3,5\} \$

cannot be ordered without breaking the kitchen's rule.

Task

Take as input sets of positive integers representing parts of a recipe. Output one of two distinct consistent values depending on whether the input represents a possible or impossible recipe.

You may assume there is at least one part in the input, and at least one ingredient in every part.

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

Test cases

{9,2,3} -> True
{5},{5} -> False
{2},{9} -> True
{5},{3,5},{2,5,6},{1,2,4,5},{1,2,3,5} -> True
{1,2,3,5},{5},{2,4,5},{1,2,4,5},{3,5} -> False
{5},{5},{9,5} -> False
{1,2,3,5},{5},{2,4,5},{1,2,4,5},{3,5},{9,5} -> False
\$\endgroup\$
7
  • \$\begingroup\$ I don't think it's an associative operation. ({1} x {2}) x {1} = {1, 2} x {1} which is undefined. But {1} x ({2} x {1}) = {1} x {1, 2} = {1, 2} \$\endgroup\$
    – Kroppeb
    Mar 8 at 23:18
  • \$\begingroup\$ @Kroppeb It's associative on its domain. \$\endgroup\$
    – Wheat Wizard
    Mar 8 at 23:30
  • \$\begingroup\$ That doesn't make sense. Associativity means that a x b x c is not ambigue because (a x b) x c is the same as a x (b x c). I might conclude that a x (b x c) has an answer for a specific a, b and c, and just write down a x b x c = ... and someone comes along and get confused because (a x b) x c is undefined. \$\endgroup\$
    – Kroppeb
    Mar 9 at 0:15
  • \$\begingroup\$ @Kroppeb You are considering "undefined" as an output value. But it is outside of the function's domain. \$\endgroup\$
    – Wheat Wizard
    Mar 9 at 1:01
  • \$\begingroup\$ @WheatWizard please consider saying that your operation is a partial binary operation, because binary operations are, generally speaking, expected to have a well-defined result given any pair of operands. \$\endgroup\$ Mar 9 at 1:23

15 Answers 15

7
\$\begingroup\$

Jelly,  11  10 bytes

-1 using Jonathan Allan's observation that we can check if a new ingredient is added each step by seeing if the cumulative ingredient sets are unique (by checking invariance over deduplication), , instead of check if the length is increasing (3 bytes).

Œ!œ|\QƑ$€Ẹ

Try It Online!


Original, 11 bytes

Œ!œ|\ẈIẠƲ€Ẹ

Try It Online!

Explanation

You can find a video explanation of this solution as well here!

Œ!œ|\ẈIẠƲ€Ẹ    Main Link
Œ!             all permutations
         €     for each (permutation)
        Ʋ      last three links:
    \          - cumulative reduce on:
  œ|             - set union
     Ẉ         - length of each (ingredient set at each step)
      I        - increments
       Ạ       - is any non-zero?
          Ẹ    any?
\$\endgroup\$
0
6
\$\begingroup\$

Python, 72 bytes

f=lambda x,s={0}:len(x)==len({*x})*any(f({*x}-{i},s|i)for i in x if i-s)

Attempt This Online!

Takes input as a list of frozensets


Original, 80 bytes

f=lambda x,s={0}:len(x)==len({*x})*any(f({*x}-{i,()},s|{*i})for i in x if{*i}-s)

Attempt This Online!

This one handles empty parts

\$\endgroup\$
5
\$\begingroup\$

Jelly,  11  10 bytes

-1 using hyper-neutrino's observation that we can use multiset-union, œ| to get the prefix unions mentioned in my original (and there is no need to deduplicate these).

Œ!œ|\QƑ$€Ẹ

Try it online! Or see the test-suite.


Original, 11 bytes

Œ!;\Q€QƑƊ€Ẹ

Try it online! Or see the test-suite.

How?

Any order that works will have a distinct list of prefix unions (since each step adds at least one new ingredient):

Œ!;\Q€QƑƊ€Ẹ - Link: list of lists of ingredients, Recipe
Œ!          - all permutations of {Recipe}
         €  - for each Ordering:
        Ɗ   -   last three links as a monad - f(Ordering):
   \        -     cumulative reduce by:
  ;         -       concatenate
    Q€      -     deduplicate each
      QƑ    -     is invariant under deduplication?
          Ẹ - any?
\$\endgroup\$
5
\$\begingroup\$

Vyxal 3, 6 bytes

ṖḌᶳRᵞu

Try it Online!

Thank you to @lyxal for porting my solution to Vyxal 3, which has some nice features that save us a lot of bytes.

Explanation

ṖḌᶳRᵞu    Full Program
Ṗ         Permutations
 Ḍ        Does any satisfy? (opens a structure, closed by } but can be omitted)
  ᶳR      Cumulative reduce over set union
    ᵞu    Invariant over uniquify

This is the same idea as the original solution (below) which is the same as the joint Jelly solution that Jonathan Allan and I got by combining our approaches.


Vyxal 2, Flagless 9 bytes

Ṗƛɖ∪¨=U;a

Try it Online!

Explanation

You can find a video explanation of this solution as well here!

Ṗƛɖ∪¨=U;a    Full Program
Ṗ            all permutations
 ƛ     ;     for each (permutation):
  ɖ          - cumulatively reduce on:
   ∪           - set union
    ¨=       - is it the same when
      U        - uniquified?
        a    any?

This is the same idea as the 10-byte Jelly solution formed from the merging of my cumulative reduce on union and Jonathan Allan's invariance over uniquification.

Vyxal saves two bytes here by having a one-byte built-in for getting all permutations and for set union, but loses one of those bytes back by requiring two bytes for invariance.


The following also works:

Vyxal G, 7 bytes

Ṗƛɖ∪¨=U

Try it Online!

Here, we shift the use of a to check if any permutation works and instead map the function over all of them to get a list of zeroes (for when the ordering is invalid) and ones (for when it is valid). The G flag returns the maximum value which serves the same purpose. Even if flags are counted 1:1, we save a byte here because now we can remove the ; that was previously required to close the map lambda.

\$\endgroup\$
4
\$\begingroup\$

Brachylog, 11 9 bytes

p{a₀cd}ᶠ≠

Explanation

Brachylog is a terse prolog. So we are defining a constraint and checking if the input matches it.

p{a₀cd}ᶠ≠
p           find a Permutation where
 {    }ᶠ      all the  (Find all)
  a₀          prefixes (Adfix variant 0: prefix)
    cd        when Concatenated and Deduplicated
        ≠     are unique

Old solution

p{h;.≠&cd}ˡ

Explanation

Brachylog is a terse prolog. So we are defining a constraint and checking if the input matches it.

p{h;.≠&cd}ˡ
p              Does there exist a Permutation of the input for which
 {       }ˡ    we can apply the following Left fold:
      &cd      Concatenate the 2 items and Deduplicate them with the additional
  h            constraint that if we take the first item (Head) it
   ;.≠         does not equal our result

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ If u (currently unused) would be set union (short for cd) and there would be a scan reduce (eg ʲ is unused), then you'd get the following 4 byte answer puʲ≠. \$\endgroup\$
    – Kroppeb
    Mar 9 at 0:10
3
\$\begingroup\$

Haskell, 88 85 67 60 bytes

-7 bytes thanks to Wheat Wizard.

import Data.List
any(((==)<*>nub).scanl1 union).permutations

Try it online!

Using Jonathan Allan's observation that cumulative ingredient sets being unique means new ingredients are being added at every step.

\$\endgroup\$
0
2
\$\begingroup\$

JavaScript (Node.js), 82 bytes

f=x=>x+x?x.some((t,i)=>t.some(u=>!i.flat().includes(u),i=x.filter(_=>i--))&f(i)):1

Try it online!

Base case [] or [[]]

Find element t that contains a new element and x\t is possible, then append t

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 75 bytes

-3 thanks to @tsh

Returns a Boolean value.

f=(a,m)=>a<1||a.some(b=>b.map(v=>M|=1<<v,M=m)&&M!=m&f(a.filter(c=>c!=b),M))

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Maybe you can omit the parameter i, and use _!=b instead of i--: f=(a,m)=>a<1||a.some(b=>b.map(v=>M|=1<<v,M=m)&&M!=m&f(a.filter(c=>c!=b),M)) \$\endgroup\$
    – tsh
    Mar 5 at 5:20
2
\$\begingroup\$

05AB1E, 13 bytes

œεηε˜Ùg}¥ĀP}à

Try it online or verify all test cases.

Explanation:

œ        # Get all permutations of the (implicit) input-list of lists
 ε       # Map over each inner permutation
  η      #  Get all prefixes of this permutation
   ε     #  Map over each prefix:
    ˜    #   Flatten this list of lists
     Ù   #   Uniquify it
      g  #   Pop and push its length
   }¥    #  After the inner map: get the forward-differences
     Ā   #  Check for each whether it's NOT 0
      P  #  Check that all are truthy
 }à      # After the outer map: check if any is truthy
         # (which is output implicitly as result)
\$\endgroup\$
2
\$\begingroup\$

Nekomata + -e, 7 bytes

ᶦ{ĕ~f}z

Attempt This Online!

ᶦ{ĕ~f}z
ᶦ{   }      Repeat the following arbitrarily many times:
  ĕ             Take an item out from the list
                e.g. [[],[3],[2,6],[1,2,4],[1,2,3]] -> [[],[3],[1,2,4],[1,2,3]], [2,6]
   ~            Choose an element from the item
                e.g. [2,6] -> 6
    f           Check that the remaining (nested) list does not contain the element
                If so, return the list
                e.g. [[],[3],[1,2,4],[1,2,3]] 6 -> [[],[3],[1,2,4],[1,2,3]]
      z     Check that the result contains only one element
\$\endgroup\$
2
\$\begingroup\$

AWK, 65 64 bytes

{for(i=NF;i;i--)r=_[$i]++?1:r}!NF{r=_[""]++?1:r}END{print r?0:1}

Try it online!

Will print 0 for false and 1 for true.

\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 59 45 bytes

Or@@UnsameQ@@@FoldList@Union/@Permutations@#&

-14 thanks to @att
Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ 45 bytes \$\endgroup\$
    – att
    Mar 9 at 8:17
  • \$\begingroup\$ @att This way of avoiding DuplicatesFreeQ should be posted at "Tips for golfing in Mathematica" \$\endgroup\$
    – lesobrod
    Mar 9 at 8:34
1
\$\begingroup\$

Ruby, 59 bytes

f=->l{l==[[]]||l==l|l&&(l-=[[]]).any?{|x|f[l.map{|z|z-x}]}}

Try it online!

Why?

  • If the list only contains an empty set, then it's true.
  • If the list contains duplicates, then it's false.
  • In any other case, we can remove the empty set from the list and check if there is a set that we can subtract from all the other sets in the list to produce a valid list.
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 23 bytes

⊞υθF⊖Lθ≔ΣEθEΦυ⁻κμ⁺μκυ¬υ

Attempt This Online! Link is to verbose version of code. Outputs an inverted Charcoal boolean, i.e. - if the recipe is impossible, nothing if it is impossible. Explanation:

⊞υθ

Start with recipes with each part as their ingredient.

F⊖Lθ

Loop over the remaining number of parts.

≔ΣEθEΦυ⁻κμ⁺μκυ

For each part, find the recipes for which that part includes a new ingredient, add the part to the recipe, and create a new list of augmented recipes.

¬υ

Output whether the recipe was impossible.

22 bytes if the empty part is disallowed:

⊞υ⟦⟧Fθ≔ΣEθEΦυ⁻κμ⁺μκυ¬υ

Attempt This Online! Link is to verbose version of code. Explanation: As above but starts with a recipe with no parts and then loops for the given number of parts.

\$\endgroup\$
0
\$\begingroup\$

APL(Dyalog Unicode), 45 bytes SBCS

{⍺←⍬⋄0=⍴⍵:1⋄(⍵≡∪⍵)∧∨/((⍺≢⍺∪⊢)∧(⍺∪⊢)∇⍵~⊂∘⊢)¨⍵}

Try it on APLgolf!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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