¿Puede este recipiente contener tanto líquido?

8

¿Puede este recipiente contener tanto líquido?

Sinopsis del desafío

Como probablemente sepa, los líquidos tienen una forma indefinida y un volumen definido. Como tal, siempre toman la forma de su contenedor. Sin embargo, no pueden expandirse para llenar su contenedor.

Su trabajo hoy es determinar si una cierta cantidad de líquido (representada por un cierto número de Lcaracteres o números que representan el volumen de la pieza, según la sugerencia) puede caber en un recipiente de cierto tamaño (representado por una matriz de Ccaracteres) con cierta cantidad de espacio vacío (representado por caracteres de espacio) dentro de él. El contenedor siempre tendrá Ccaracteres en todo el perímetro.

Su programa devolverá un valor verdadero / falso en función de si el líquido encajará en el recipiente. Solo se ajustará si hay un área de espacio vacío conectado (formado por espacios adyacentes entre sí horizontal, diagonal o verticalmente) dentro del recipiente para cada parte del líquido que está separada del resto (ya sea por un espacio o por dos personajes de nueva línea).

Casos de prueba

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

¡No dude en sugerir casos de prueba!

Reglas

  • Este es el , por lo que gana la respuesta más corta en bytes.
  • Las lagunas estándar no están permitidas.
Gabriel Mills
fuente
1
Sugeriría agregar un caso de prueba como L\n\nL, CCCCC\nCCCCC\nC..CC\nCCCCC( .representa un espacio, \nrepresenta una nueva línea).
Erik the Outgolfer
1
¿Podemos tomar el Ltexto como una lista de volúmenes (es decir, una lista del número de Ls en cada cantidad)? Dado que analizar espacios y líneas nuevas dobles parece no tener relación con el núcleo del desafío. ¿También podemos tomar el Ctexto como una matriz de dos valores distintos en su lugar por la misma razón?
Jonathan Allan
1
Caso de prueba sugerido 3 Ly uno LLcon espacios de tamaño 3 y 2 (un algoritmo que solo llena los espacios más pequeños primero con los pedazos más pequeños de líquido aún por usar dará Falsey). Quizás lo mismo pero con 2 Ly uno LLLtambién, para atender a la otra dirección.
Jonathan Allan
1
Esta pregunta parece ser 3 preguntas distintas para mí. El primero es analizar la entrada La una lista de enteros. El segundo analiza la Cmatriz de entrada a una lista de enteros. Y la tercera es una pregunta determinante para la bolsa entera A y B, si hay una partición en A, cuando suma todos los enteros en cada partición para obtener una bolsa A ', cada enésimo número más grande en A' es menor ( <=) que el enésimo número más grande en B '.
tsh
1
Creo que la forma del personaje sería un formato de entrada preferido para Snails de todos modos. En general, se prefieren los requisitos de IO flexibles en PPCG, pero ciertamente depende de usted.
Jonathan Allan

Respuestas:

4

Caracoles, 58 bytes

La entrada se toma exactamente como en los ejemplos.

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

Una versión más larga de 4 bytes es lo suficientemente rápida como para completar instantáneamente los casos de prueba ( Pruebe esta versión en línea ):

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

Un formato sangrado de este último:

?^
    t\ 
    t\L
    {
        t\L`?
        t\ 
        z!.
        o=(\ ,\C
    },
    !(tz(
         \L!.!~
         |
         \ !.o=(\ ,\C
},
!(t\L
Feersum
fuente
2
¿Podría agregar una explicación a la versión con sangría? ¿O todavía estás jugando golf antes de agregar uno?
Kevin Cruijssen
1

Limpio , 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))]

Pruébalo en línea!

Define la función $ :: [Int] [[Char]] -> Bool. El enlace TIO incluye un contenedor alrededor de STDIN.

? :: [Int] -> [[Int]] es una ayuda para generar las diferentes formas en que se pueden combinar los volúmenes.

Expandido:

$ 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
            )
        )
    ]
Οurous
fuente