17
\$\begingroup\$

To be able to challenge the Elite-4 of top programmers, you need to show your badges first, that qualify you as a potential programmer-master. However, there's a twist. Once you show a badge, it is collected, which means you can't re-show it. So better come prepared! There are n badge collectors, each has a known list of accepted_badges. Given a list of your badges, your task is to find out, if you can access elite-four or if you require more badges. You can indicate this by printing a truthy-value for the first case or a falsey-value in the second case.

Example

accepted_badges: [ [a, b, c], [a, b, d], [d, e, f]]

If you have the badges [a, b, d] you can pass. Simply give your a badge to the first collector (accepted_badges[0]), your b badge to the second and your d badge to the last collector. So this is a truthy case.

If you have the badges [a, b, c] you are in bad luck. The last collector doesn't accept any of it.

If you have the badges [b, c, d] you can also pass. Here you will need to give your c badge to the first collector, the b badge to the second and the final collector will get the d badge.

If you have the badges [a, e, f] you will not be admitted, because you would have to use your a badge twice (since the first collector takes it away from you), which is not possible.

Input:

A list* of your badges
A 2Dlist* of badge collectors and their accepted badges

*list can be the following:

1. a list, i.e. [a, b, c, ...] or [[a,b,c],[c,d,e]]
2. a list with first element = number of elements i.e. [3, a, b, c] or [ [2], [3, a, b, c], [1, a]]
2. a string     "abcd..."  
3. a string with leading number of elements i.e. "3abc"  
4. a seperated string i.e. "abc,def,ghi"
5. a separated string with leading numbers of elements i.e. "3abc,2ab,5abcdef"
6. or any other convenient input format you can think of

Assumptions:

You may assume:

  • any list to never be empty
  • input letters to always match [a-z]
  • your number of badges matches the number of badge collectors

You may not assume:

  • that any list is sorted

Test cases (list format):

['a','b','c','d']
[['a','b','c'],['d','e','f'],['b','c','d'], ['c', 'g']]
Truthy

['a', 'a', 'a']  
[['a', 'b', 'c'], ['a', 'd', 'e'], ['a', 'b', 'e', 'f']]
Truthy

['a', 'a', 'f']
[['a', 'c', 'f'], ['a', 'd'], ['b', 'c']]
Falsey

['x', 'y', 'z', 'w']
[['x', 'y'], ['x', 'y'], ['z', 'w'], ['x', 'y']]
Falsey

['p', 'q', 'r', 's', 't']
[['p', 'q', 'r'], ['r', 'q', 'p'], ['r'], ['s', 't'], ['p', 'q', 'r', 's', 't']]
Truthy

['p', 'q', 'r', 's', 't']
[['p', 'q', 'r', 's', 't'], ['p', 'q', 'r', 's'], ['p', 'q', 'r'], ['p', 'q'], ['p']]
Truthy

Test cases (String format):

"abcd"
"abc def bcd cg"
Truthy

"aaa"  
"abc ade abef"
Truthy

"aaf"
"acf ad bc"
Falsey

"xyzw"
"xy xy zw xy"
Falsey

"pqrst"
"pqr rqp r st pqrst"
Truthy

"pqrst"
"pqrst pqrs pqr pq p"
Truthy

Lastly, this is so the answer with the least number of bytes wins. Please refrain from using any standard-loopholes.

\$\endgroup\$
  • \$\begingroup\$ Would've been nice if the list items in the test cases were already strings.... \$\endgroup\$ – RGS Apr 14 at 14:37
  • 2
    \$\begingroup\$ Added string formatted testcases \$\endgroup\$ – infinitezero Apr 14 at 14:41
  • \$\begingroup\$ Thanks but I meant for them to be quoted :) That way I could copy&paste into the code without having to do much input formatting; these new strings still don't solve my problem :( \$\endgroup\$ – RGS Apr 14 at 14:42
  • 2
    \$\begingroup\$ Your first test case has 1 too many badges or 1 too few badge checkers. \$\endgroup\$ – RGS Apr 14 at 14:48
  • 1
    \$\begingroup\$ I suggest adding the case [a, e, f] to the example, so it will cover all of the rules. \$\endgroup\$ – Nitrodon Apr 14 at 15:40

15 Answers 15

1
\$\begingroup\$

05AB1E, 8 bytes

.»â€˜JIå

Try it online!

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

Python 2, 68 bytes

One of the few cases where itertools is useful.

lambda b,a:s(b)in map(s,product(*a))
s=sorted
from itertools import*

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Why do you have `f=` in some separate header? \$\endgroup\$ – CrabMan Apr 15 at 23:10
  • \$\begingroup\$ To call a lambda function, we have to assign a name to it. However in CGCC, we apparently don't need to include the f=. The only time you need to specify its name is in a recursive call. \$\endgroup\$ – dingledooper Apr 15 at 23:42
  • \$\begingroup\$ You know that there's a bounty for this? \$\endgroup\$ – user92069 Apr 29 at 5:18
  • \$\begingroup\$ Yes, I am in fact aware of that bounty. Unfortunately, it expired long ago, so I doubt that I'm eligible for it. \$\endgroup\$ – dingledooper Apr 29 at 5:31
6
\$\begingroup\$

Python 2, 70 bytes

f=lambda s,l:l and any(f(s.replace(x,'',1),l[1:])for x in l[0])or''==s

Try it online!

Tries every possible character from each list entry in turn, removing it from the target string s if present, and checking if we end up with the empty string. The s.replace(x,'',1) removes at most one copy of x in the string s.

An annoying issue is that in the base case where l==[], we get an error when we try to read l[0] even if the result doesn't matter, making it hard to cut the l and. It "almost" works to save a byte as below, but we get an error when l becomes empty because the l[0] is evaluated before the if l is tested and fails.

f=lambda s,l:s==''or any(f(s.replace(x,'',1),l[1:])for x in l[0]if l)

Try it online!

69 bytes

f=lambda s,l:any(f(s.replace(x,'',1),l[1:]+[[]])for x in l[0])or''==s

Try it online!

Pad l to the right with empty lists.

69 bytes

f=lambda s,h,*t:t and any(f(s.replace(x,'',1),*t)for x in h)or s in h

Try it online!

Takes input as the target string, followed by a splatted list of lists.


69 bytes

f=lambda s,l:any(f(s.replace(x,'',1),l[x in l[0]:])for x in s)or[]==l

Try it online!

A "dual" method based on ovs' solution, iterating over characters in the target string and removing from the list.

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

Haskell, 54 bytes

import Data.List
(.permutations).any.flip elem.mapM id

Try it online!

Without imports, 85 bytes

x#[]=[[x]]
x#(a:b)=(x:a:b):map(a:)(x#b)
(.foldr((=<<).(#))[[]]).any.flip elem.mapM id

Try it online!

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

Python 2, 79 bytes

f=lambda a,b:a==[]or any(f(a[x in a[0]:],b[:i]+b[i+1:])for i,x in enumerate(b))

Try it online!

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

05AB1E, 9 bytes

-1 byte thanks to @KevinCruijssen

œεøε`¢]PZ

Try it online!

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Can't really think of a better method either thus far. But you can save a byte by changing the }P}Z to ]PZ: 9 bytes. \$\endgroup\$ – Kevin Cruijssen Apr 14 at 15:54
3
\$\begingroup\$

Erlang (escript), 138 bytes

Aaargh! Erlang's cartesian product is eeeeevil! (It saved 20 bytes anyway.)

f(A,B)->lists:member(lists:sort(A),[lists:sort(tuple_to_list(C))||C<-sofs:to_external(sofs:product(list_to_tuple([sofs:set(I)||I<-B])))]).

Try it online!

Explanation

Here ... stands for nest the previous line inside this position.

f(A,B)-> % Take 2 items.
[sofs:set(I)||I<-B] % Convert every item of B into a sofs set

list_to_tuple(...) % Convert the input list into a tuple

sofs:product(...)  % Cartesian product of this set tuple

sofs:to_external(...) % Pick the value of the cartesian product

C<-...            % Assign it to the variable C

[lists:sort(tuple_to_list(C))||...] % For every item, convert the tuple to a list
                                    % And then sort that list

lists:member(lists:sort(A),...).    % Is argument 1 a member of the processed list?
```
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Haskell, 66 65 bytes

Port of my Python answer.

-1 byte thanks to @AdHocGarfHunter.

b#(a:s)=or[x!b#s|x<-a,elem x b]
b#x=1>0
x!(a:b)|a==x=b|w<-x!b=a:w

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ , is shorter than && by a byte. \$\endgroup\$ – Ad Hoc Garf Hunter Apr 15 at 0:30
  • \$\begingroup\$ @AdHocGarfHunter this fails with parse error on input ‘|’. I think replacing && with , only works in guards? \$\endgroup\$ – ovs Apr 15 at 5:55
  • \$\begingroup\$ ? \$\endgroup\$ – Ad Hoc Garf Hunter Apr 15 at 12:42
  • \$\begingroup\$ @AdHocGarfHunter thanks for helping me out. I was literally replacing && with ,, which obviously didn't work. \$\endgroup\$ – ovs Apr 15 at 19:55
3
\$\begingroup\$

C (gcc), 170 168 bytes

Edited: Switched to returning 1 from inner main calls to save a byte not needing to negate the return value when assigning into u. Also another byte saved thanks to @ceilingcat for reminding me about index instead of strchr.

f;char*l,*u;main(n,x)char**x;{if(f++){if(n){for(int i=0;l[i];i++)if(u[i]&&index(*x,l[i])){u[i]=0;u[i]=main(n-1,x+1);}return 1;}exit(1);}u=strdup(l=x[1]);main(n-2,x+2);}

Try it online!

A relatively straightforward recursive backtracking search. Takes input as command-line arguments, the first being the list of badges you have in a single character string (e.g. abcd) and each other argument being the list of badges accepted by each station in similar format. Contrary to traditional exit code logic the program's exit code is 0 when you cannot pass and 1 when you can pass, mainly because the return value of main is used in the program and it works out better that way. There is no output on stdout.

Originally I'd written a subroutine for the search part after initializing some state in main but when I abstracted the globals and saw the function signature was int (int, char**) I couldn't resist pulling it all back in and recursing on main.

Degolfed somewhat for viewing pleasure:

f;char*l,*u;                                                // Declare some storage. f is a counter used to only run the setup code on the original call to main. l gets assigned to be a pointer to the list of badges held. u is used as a buffer to track which badges are currently still available to be used.
main(n,x)char**x;{                                          // Typical golfed main declaration.
       if(f++){                                             // Only run the code in the if statement on subsequent calls to main (as a global f defaults to being initialized to 0).
               if(n){                                       // Catch the recursion base case (if n == 0 there are no stations left to pass).
                       for(int i=0;l[i];i++){               // Iterate over the badges we have available. i needs to be declared here since each recursive call needs to iterate over badges separately.
                               if(u[i]&&index(*x,l[i])){   // If the badge is available to be used (the entry in u for the badge is nonzero), and the badge is accepted by the next station...
                                       u[i]=0;              // Mark the badge as unavailable for the recursive call
                                       u[i]=main(n-1,x+1); // Recursively call main with the current station removed. If a sequence passing all stations is found the program exits immediately, so if main returns on an inner call it will always return 1; by assigning this into u we mark the badge as available again afterwards if we backtrack out of this call to continue searching.
                               }
                       }
                       return 1;                            // If we went over all our badges and couldn't get through this station, we need to backtrack the search so return 0 and continue.
               }
               exit(1);                                     // If there are no stations left we passed through all of them so immediately exit with code 1.
       }
       u=strdup(l=x[1]);                                    // Initialize storage for u. Initially I used calloc here, but since the needed length of u is the length of the list of badges held, strdup gets the job done while saving on bytecount (Just with the parity of the usage checks inverted since strdup means all the entries we care about are initialized to nonzero values).
       main(n-2,x+2);                                       // Make the first recursive call, with our new args starting at the first station's accepted badge list.
}                                                           // If we made it to the end without exiting the program, main will default to returning 0 since no return call was specified.
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I hoped for a C solution! Great job. I would have never dared to call main() recursively :o \$\endgroup\$ – infinitezero Apr 17 at 7:19
  • \$\begingroup\$ The switch to the ternary operator introduces a bug since setting u[i] to 0 is removed in order to have one statement. Consider the input abcd, ac, def, cd, a; it incorrectly indicates you can pass even though this would require using badge a twice. \$\endgroup\$ – SevenStarConstellation Apr 21 at 19:04
  • \$\begingroup\$ 162 bytes \$\endgroup\$ – ceilingcat Apr 22 at 1:29
2
\$\begingroup\$

Python 3, 85 84 bytes

f=lambda b,r:b==""or any(B in r[0]and f(b[:i]+b[i+1:],r[1:])for i,B in enumerate(b))

Try it online! Golfed 1 byte by switching to an explicit enumeration.

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

Charcoal, 37 bytes

Sθ⊞υθFθ«Sι≔υη≔⟦⟧υFηFΦκ№ιλ⊞υΦκ¬⁼λμ»¿υ¹

Try it online! Link is to verbose version of code. Outputs - if you can challenge the Elite Four. Explanation:

Sθ

Read the badges.

⊞υθ

Start with a single entry with all badges remaining.

Fθ«

Loop over each guard.

Sι

Input the badges he accepts.

≔υη≔⟦⟧υFη

Save the list of badges remaining so that we can clear it and still loop over the list.

FΦκ№ιλ

See whether this guard will accept any of these badges.

⊞υΦκ¬⁼λμ

If so then push the possible sets of remaining badges to the list. (If e.g. two guards both accept the same two badges then this could create duplicates depending on which badge you give to which guard but this does not affect the final result.)

»¿υ¹

If it was possible to give all the guards a badge then print a -.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ @Arnauld Usually I remember to paste in the succinct byte count, yes... \$\endgroup\$ – Neil Apr 14 at 23:23
2
\$\begingroup\$

JavaScript (ES6),  69  68 bytes

Takes input as (b)(a), where \$b[\:]\$ are the collector badges as a list of sets and \$a[\:]\$ is our list of badges.

b=>g=a=>1/a||a.some((v,i)=>b[a.length-1].has(v)*g(a.filter(_=>i--)))

Try it online!

Commented

b =>                       // b[] = collector badges as a list of sets
  g = a =>                 // g is a recursive function taking our list of badges
    1 / a ||               // yield +Infinity if a[] is empty
    a.some((v, i) =>       // otherwise, for each badge v at position i in a[]:
      b[a.length - 1]      //   test whether the collector at index a.length - 1
      .has(v) *            //   accepts the badge v
      g(                   //   multiply by the result of a recursive call where:
        a.filter(_ => i--) //     the i-th badge is removed from a[]
      )                    //   end of recursive call
    )                      // end of some()
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Perl 5 -lpa, 86 79 bytes

$"="}{";@a=<>;chomp@a;map{$b=$F[0];$\|=!grep!$_,map$b=~s/$_//,/./g}glob"{@a}"}{

Try it online!

First line of input is the badges you hold. Subsequent lines are the ones needed. On each line, badges are comma separated.

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

Perl 6, 40 bytes

{@^a.permutations.map(*Z∈@^b).max.min}

Try it online!

Explanation

Basic approach is to work out every possible combination of our collectors badges against the other collectors badges and see if any combination is possible.

@^a.permutations computes all permutations of the list of your badges [abcd] -> [[abcd],[abdc]...]

.map(*Z∈@^b) For each of these permutations, zip each element of the resulting list (*Z) with whether each item is present in the corresponding other badge collector's badges (@^b). [abcd],[[abc][def][bcd][cg]] -> ((True False True False) (True False True True) ...)

.max Return the highest element in the list, i.e. the one with the most Trues.

.min Return the lowest element in this list, i.e. true if all the elements are true, else false.

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

Python 3, 86 bytes

lambda a,b:any(all(map(str.count,b,c))for c in permutations(a))
from itertools import*

Try it online!

-7 bytes thanks to xnor

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ It looks like you can use str.count in place of str.__contains__. \$\endgroup\$ – xnor Apr 14 at 15:11

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.