10
\$\begingroup\$

We want to go on a night hike with the youth group, but of course not everyone has their torch, even though we told them we planned to split up. What options are there for group formation if n teens have m torches with them, but each group needs at least one torch?

Example: Three teens with torches (X) and two without (x) can be divided up as XXXxx (all together), XX Xxx, XXx Xx, XXxx X, X X Xxx or X Xx Xx.

Input: A list in any form with n elements from two different symbols, e.g. a string as above XXXxx or a list [True, True, True, False, False]. It can be assumed that the input is sorted and only contains valid entries.

Output: A list with all possibilities in a format corresponding to the input in an order of your choice, but without duplicates (Xx is the same as xX).

Test data:

X       --> X
Xxxxxx  --> Xxxxxx
XXxx    --> XXxx,Xx Xx,X Xxx
XXXxx   --> XXXxx,XX Xxx,XXx Xx,XXxx X,X X Xxx,X Xx Xx
XXXXX   --> XXXXX,XXXX X,XXX XX,XXX X X,XX XX X,XX X X X,X X X X X
\$\endgroup\$
4
  • 3
    \$\begingroup\$ Why sorted list of two values rather than two integers? \$\endgroup\$
    – l4m2
    Dec 7, 2023 at 7:36
  • \$\begingroup\$ @l4m2 Because I don't want to exclude languages that don't know about integers (like sed), resulting in boring overhead for teaching it to count. Btw, this is not sandbox anymore. (-; \$\endgroup\$
    – Philippos
    Dec 7, 2023 at 7:43
  • \$\begingroup\$ Is m a typo? (Also, there's no reason you can't explicitly allow both as I/O options.) \$\endgroup\$ Dec 7, 2023 at 20:59
  • \$\begingroup\$ @UnrelatedString You mean m torches? That's a variable, no typo. After six answers, I don't want to change the rules. I wish, such suggestions would have come while this question was in the sandbox. \$\endgroup\$
    – Philippos
    Dec 8, 2023 at 7:42

7 Answers 7

7
\$\begingroup\$

Nekomata, 6 bytes

Ooᵐᵗžũ

Attempt This Online!

Takes input as a sorted list of 1s and 0s, where 1 means with torch and 0 means without torch.

Ooᵐᵗžũ
O       Set partition; split the input into a list of subsets
 o      Sort
  ᵐᵗž   Check that each subset contains at least one nonzero element
     ũ  Remove duplicate solutions
\$\endgroup\$
4
\$\begingroup\$

05AB1E, 16 bytes

œ€.œ€`€€{€{êʒ€àP

I/O as a list of 1s/0s for Xs/xs respectively.

I have the feeling the first part of the code can be substantially shorter and I'm missing some obvious builtin combinations.. :/

Try it online or verify all test cases.

Explanation:"

œ€.œ€`€€{€{ê # Get all unique sorted partitions:
œ            #  Get all permutations of the (implicit) input-list
 €.œ         #  Get all partitions of each permutation
    €`       #  Flatten this list of lists of lists of 1s/0s one level down
      €€{    #  Sort the values inside the parts of partitions
         €{  #  Sort the parts of each partition
           ê #  Sorted-uniquify the list of sorted partitions
ʒ            # Filter this list of partitions by:
 ۈ          #  Get the maximum of each part
   P         #  Take the product to check if all are truthy
             # (after which the filtered list is output implicitly)
\$\endgroup\$
1
  • \$\begingroup\$ Good we don't count the money; otherwise your six-Euro-solution would be too expensive. (-; Using 1 and 0 to check the product for darkness seems to be a good move. \$\endgroup\$
    – Philippos
    Dec 7, 2023 at 8:44
3
\$\begingroup\$

Jelly, 15 bytes

I'm very prepared for a smarter approach to trounce this!

Œ!ŒṖ€ẎṢ€ṢẸƇƊƑƇQ

A monadic Link that accepts a list of zeros (no torch) and ones (has torch) that yields a list of the possible partitions.

Try it online!

How?

Œ!ŒṖ€ẎṢ€ṢẸƇƊƑƇQ - Link: Hikers
Œ!              - all permutations of {Hikers}
  ŒṖ€           - list partitions of each
     Ẏ          - tighten to a single list of hiker partitions
             Ƈ  - keep those for which:
            Ƒ   -   is invariant under?:
           Ɗ    -     last three links as a monad - f(hiker partition):
      Ṣ€        -       sort each group
        Ṣ       -       sort that
          Ƈ     -       keep those for which:
         Ẹ      -         any? (has torch?)
              Q - deduplicate
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 106 bytes

-1 thanks to @l4m2

Expects a string with leading 1's for X's and trailing 0's for x's.

Returns a single string with commas and line breaks as separators.

f=(s,o=O=[],p="1")=>s-(q=s.replace(p,""))?f(q,[...o,p].sort())+f(s,o,p+0)+f(s,o,p+1):O[o]||s?"":O[o]=o+`
`

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Why not \$\endgroup\$
    – l4m2
    Dec 8, 2023 at 3:46
2
\$\begingroup\$

JavaScript (Node.js), 96 bytes

f=(s,o=[],p="1")=>s-(q=s.replace(p,""))&&p<o[0]+f?f(q,[p,...o])+f(s,o,p+0)+f(s,o,p+1):s?"":o+`
`

Try it online!

From Arnauld's

JavaScript (Node.js), 82 bytes, slow

f=(s,o=[],p=s)=>p?(s-(q=s.replace(p,""))?f(q,[p,...o],p):'')+f(s,o,p-1):s?'':o+`
`

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 52 bytes

⊞υ⟦⟧FS«≔υθ≔⟦⟧υFθ«Fκ⊞υEκ⎇⁼ν⌕κλ⁺μιμ¿⁼ιX⊞υ⊞OκX»»Φυ⁼κ⌕υι

Try it online! Link is to verbose version of code. Assumes the input contains Xs optionally followed by xs. Explanation:

⊞υ⟦⟧

Start with all possibilities of 0 elements.

FS«

Loop over the elements.

≔υθ≔⟦⟧υFθ«

Loop over a saved copy of the possibilities and start collecting new possibilities.

Fκ⊞υEκ⎇⁼ν⌕κλ⁺μιμ

Add the current element to each of the unique lists in this possibility. (If there are duplicates then this doesn't prevent them, it just ensures that they are sorted so that they can be identified as duplicate.)

¿⁼ιX⊞υ⊞OκX

If the current element is an X then also add it as a new list.

»»Φυ⁼κ⌕υι

Deduplicate and output the found possibilities.

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

Perl 5 -MList::Util=uniq -F, 114 bytes

$X=y/X//;$x=y/x//;say for uniq grep{s/^ +| +$//g;!/xX|\bx+\b|  /&&$X==y/X//&&$x==y/x//}sort glob"{X,x,' '}"x(@F*3)

Try it online!

It's extremely slow. TIO times out on any input longer than 4 characters.

\$\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.