Bisakah wadah ini menampung cairan sebanyak ini?

8

Bisakah wadah ini menampung cairan sebanyak ini?

Tantang Sinopsis

Seperti yang kemungkinan besar Anda ketahui, cairan memiliki bentuk yang tidak terbatas dan volume yang pasti. Karena itu, mereka selalu mengambil bentuk wadah mereka. Namun, mereka tidak dapat memperluas untuk mengisi wadah mereka.

Tugas Anda hari ini adalah menentukan apakah cairan dalam jumlah tertentu (diwakili oleh sejumlah Lkarakter atau angka yang mewakili volume bagian, sesuai saran) dapat masuk ke dalam wadah dengan ukuran tertentu (diwakili oleh matriks dari Ckarakter) dengan sejumlah ruang kosong (diwakili oleh karakter spasi) di dalamnya. Wadah akan selalu memiliki Ckarakter di sekelilingnya.

Program Anda akan mengembalikan nilai kebenaran / kepalsuan berdasarkan apakah cairan tersebut akan masuk ke dalam wadah. Ini hanya akan cocok jika ada area ruang kosong yang terhubung (terdiri dari ruang yang berdekatan satu sama lain secara horizontal, diagonal, atau vertikal) di dalam wadah untuk setiap bagian cairan yang dipisahkan dari yang lain (baik oleh ruang atau oleh dua karakter baris baru).

Uji Kasus

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

Jangan ragu untuk menyarankan uji kasus!

Aturan

  • Ini adalah , jadi jawaban tersingkat dalam byte menang.
  • Celah standar tidak diijinkan.
Gabriel Mills
sumber
1
Saya sarankan menambahkan test case seperti L\n\nL, CCCCC\nCCCCC\nC..CC\nCCCCC( .mewakili spasi, \nmewakili baris baru).
Erik the Outgolfer
1
Bisakah kita mengambil Lteks sebagai daftar volume (yaitu daftar jumlah Ls di setiap jumlah)? Karena mengurai ruang dan menggandakan baris baru tampaknya tidak berhubungan dengan inti tantangan. Bisakah kita mengambil Cteks sebagai matriks dari dua nilai berbeda bukan karena alasan yang sama?
Jonathan Allan
1
Test case yang disarankan 3 Ldan satu LLdengan ruang ukuran 3 dan 2 (sebuah algoritma yang hanya mengisi ruang terkecil terlebih dahulu dengan potongan cairan terkecil yang masih akan digunakan akan menghasilkan Falsey). Mungkin sama tetapi dengan 2 Ldan satu LLLjuga, untuk melayani ke arah lain.
Jonathan Allan
1
Pertanyaan ini tampaknya menjadi 3 pertanyaan berbeda bagi saya. Yang pertama adalah mem-parsing input Lke daftar integer. Yang kedua adalah parsing input Cmatrix ke daftar integer. Dan yang ketiga adalah pertanyaan menentukan untuk diberikan tas integer A dan B, jika ada partisi di A, ketika menjumlahkan semua bilangan bulat di setiap partisi untuk mendapatkan tas A ', setiap angka terbesar ke-n dalam A' lebih kecil ( <=) dari angka ke-n terbesar di B '.
tsh
1
Saya percaya bahwa bentuk karakter akan menjadi format input yang disukai untuk Siput. Persyaratan IO yang longgar secara umum lebih disukai di PPCG, tetapi itu pasti terserah Anda.
Jonathan Allan

Jawaban:

4

Siput, 58 byte

Input diambil persis seperti dalam contoh.

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

Versi 4 byte lebih lama cukup cepat untuk menyelesaikan kasus uji secara instan ( Coba versi ini secara online ):

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

Format lekukan dari yang terakhir:

?^
    t\ 
    t\L
    {
        t\L`?
        t\ 
        z!.
        o=(\ ,\C
    },
    !(tz(
         \L!.!~
         |
         \ !.o=(\ ,\C
},
!(t\L
feersum
sumber
2
Bisakah Anda menambahkan penjelasan ke versi indentasi? Atau apakah Anda masih bermain golf lebih jauh sebelum menambahkannya?
Kevin Cruijssen
1

Bersih , 313 byte

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

Cobalah online!

Menentukan fungsi $ :: [Int] [[Char]] -> Bool. TIO link termasuk pembungkus di sekitar STDIN.

? :: [Int] -> [[Int]] adalah penolong untuk menghasilkan berbagai cara volume dapat digabungkan.

Diperluas:

$ 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
            )
        )
    ]
Suram
sumber