8
\$\begingroup\$

Can this container hold this much liquid?

Challenge Synopsis

As you most likely know, liquids have an indefinite shape and a definite volume. As such, they always take the shape of their container. They cannot, however, expand to fill their container.

Your job today is to determine whether or not a certain amount of liquid (represented by a certain number of L characters or numbers representing the volume of the part, as per suggestion) can fit into a container of a certain size (represented by a matrix of C characters) with some amount of empty space (represented by space characters) within it. The container will always have C characters all the way around the perimeter.

Your program will return a truthy/falsey value based on whether the liquid will fit into the container. It will only fit if there is an area of connected empty space (made up of spaces adjacent to one another horizontally, diagonally, or vertically) within the container for each part of the liquid that is separated from the rest (either by a space or by two newline characters).

Test Cases

LLL
L
-----    True
CCCCC
C  CC
C  CC
CCCCC

LLL
 LL
------   True
CCCCCC
C C  C
C  CCC
CCCCCC

L L
LLL
-----    False (Not enough space)
CCCCC
CCCCC
C  CC
CCCCC

LL
------   False (Spaces are not connected but liquid is)
CCCCCC
CCCC C
C CCCC
CCCCCC

L L
------   True
CCCCCC
CCCC C
C CCCC
CCCCCC

L L
------   True (There is a pocket of empty space which holds both parts of the liquid)
CCCCCC
CCC  C
CCCCCC
CCCCCC

L

L
------   True (There is a pocket of empty space for each part of the liquid)
CCCCCC
CCCC C
C CCCC
CCCCCC

L L L LL
------   True
CCCCCCCCC
CCCC  C C
C CCCCCCC
CCCCCC CC
CCCCCCCCC

L
L
-----    True
CCCCC
CCCCC
C  CC
CCCCC

Feel free to suggest test cases!

Rules

  • This is , so the shortest answer in bytes wins.
  • Standard loopholes are disallowed.
\$\endgroup\$
11
  • 1
    \$\begingroup\$ I'd suggest adding a test case like L\n\nL, CCCCC\nCCCCC\nC..CC\nCCCCC (. represents a space, \n represents a newline). \$\endgroup\$ Commented Feb 21, 2019 at 19:52
  • 1
    \$\begingroup\$ May we take the L text as a list of volumes (i.e. a list of the number of Ls in each amount)? Since parsing for spaces and double newlines seems unrelated to the core of the challenge. Also may we take the C text as a matrix of two distinct values instead for the same reason? \$\endgroup\$ Commented Feb 21, 2019 at 19:59
  • 1
    \$\begingroup\$ Suggested test case 3 L and one LL with spaces of size 3 and 2 (an algorithm only filling smallest spaces first with smallest pieces of liquid still to use will yield Falsey). Maybe the same but with 2 L and one LLL too, to cater for the other direction. \$\endgroup\$ Commented Feb 21, 2019 at 20:09
  • 1
    \$\begingroup\$ This question seems to be 3 distinct questions to me. The first one is parsing input L to a list of integer. The second one is parsing input C matrix to a list of integer. And the third one is a determine question for given integer bag A and B, if there is a partition in A, when sum all integers in each partition to get a bag A', every n-th greatest number in A' is smaller (<=) than n-th greatest number in B'. \$\endgroup\$
    – tsh
    Commented Feb 22, 2019 at 2:33
  • 1
    \$\begingroup\$ I believe that the character form would be a prefered input format for Snails anyway. Generally loose IO requirements are preferred at PPCG, but it is certainly up to you. \$\endgroup\$ Commented Feb 22, 2019 at 17:05

2 Answers 2

4
\$\begingroup\$

Snails, 58 bytes

Input is taken exactly as in the examples.

t\ t\L{t\L?t\ z!.o=(\ ,\C},!(tz(\L!.!~|\ !.o=(\ ,\C},!(t\L

A 4 bytes longer version is fast enough to instantly complete the test cases (Try this version online):

?^
t\ t\L{t\L`?t\ z!.o=(\ ,\C},!(tz(\L!.!~|\ !.o=(\ ,\C},!(t\L

An indented formatting of the latter:

?^
    t\ 
    t\L
    {
        t\L`?
        t\ 
        z!.
        o=(\ ,\C
    },
    !(tz(
         \L!.!~
         |
         \ !.o=(\ ,\C
},
!(t\L
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Could you add an explanation to the indented version? Or are you still golfing it further before adding one? \$\endgroup\$ Commented Feb 22, 2019 at 8:17
1
\$\begingroup\$

Clean, 313 bytes

import StdEnv,Data.List
?v=nub[v:[[sum s:k]\\s<-subsequences v|s>[],k<- ?(difference v s)]]
$v m#p=[[(x,y)]\\x<-[0..]&l<-m,y<-[0..]&' '<-l]
=or[and(zipWith(>=)(s++[0,0..])r)\\r<- ?v,s<-permutations(map length(foldl(\p _=nub[sort(nub(e++[(x,y)\\(u,v)<-e,x<-[u-1,u,u+1],y<-[v-1,v,v+1]|(m!!x)!!y<'C']))\\e<-p])p p))]

Try it online!

Defines the function $ :: [Int] [[Char]] -> Bool. TIO link includes a wrapper around STDIN.

? :: [Int] -> [[Int]] is a helper to generate the different ways the volumes can be combined.

Expanded:

$ v m // in function $ of v and m
    # p // define p as
        = [ // a list of
            [(x, y)]    // lists of pairs (x, y)
        \\              // for each
            x <- [0..]  // index x
            & l <- m    // at list l in m
        ,               // for each
            y <- [0..]  // index y
            & ' ' <- l  // at spaces in l
        ]
    = or [ // true if any of the list of
        and (               // true if all of
            zipWith         // element-wise application of
                (>=)            // greater than or equal to
                (s ++ [0, 0..]) // permutation s padded with zeroes
                v               // list v of volumes
        )
    \\                      // for each
        s <- permutations ( // permutation s of
            map length (    // the lengths of
                foldl       // a left-fold of
                    (\p _   // function on p discarding second argument
                        = nub [ // the unique elements of the list of
                            sort (          // sorted versions of
                                nub (       // unique lists composed of
                                    e       // list e of points in a region
                                    ++ [    // prepended to the list of
                                        (x, y)      // pairs (x, y)
                                    \\              // for each
                                        (u, v) <- e // pair (u, v) in list e
                                    ,               // for each
                                        x <- [u-1, u, u+1] // x-coordinate adjacent to u
                                    ,               // for each
                                        y <- [v-1, v, v+1] // y-coordinate adjacent to v
                                    |               // where
                                        (m!!x)!!y < 'C' // the character in m at (x, y) is a space
                                    ]
                                )
                            )
                        \\          // for each
                            e <- p  // region e in p
                        ]
                    )
                    p // applied to a starting argument of p
                    p // recursively, for each element in p
            )
        )
    ]
\$\endgroup\$
0

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.