Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
Community Proposals
Community Proposals
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
Challenges

Can I follow this recipe?

+2
−0

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 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\},\,\{\},\,\{2,6\},\,\{1,2,4\},\,\{3\} $$

then they can be ordered:

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

However

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

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.

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

Test cases

{},{} -> False
{2},{9} -> True
{},{3},{2,6},{1,2,4},{1,2,3} -> True
{1,2,3},{},{2,4},{1,2,4},{3} -> False
History
Why does this post require attention from curators or moderators?
You might want to add some details to your flag.
Why should this post be closed?

0 comment threads

1 answer

+1
−0

Pyth, 15 bytes

!f.A-VtTsM._T.p

Try it online!

Outputs True if no valid recipe exists, False if one does. If truthy/falsy outputs are allowed, the ! can be removed, to just output all valid permutations. Takes input as lists, not sets.

!f.A-VtTsM._T.p
             .p  All permutations of parts
 f               Filter permutations
          ._T    All prefixes of parts
        sM       Sum prefixes
    -VtT         Filter each part for ingredients
                 not contained in previous part
  .A             Check all parts had something new
!                Check whether no permutations remain
History
Why does this post require attention from curators or moderators?
You might want to add some details to your flag.

0 comment threads

Sign up to answer this question »