Beberapa bulan yang lalu, sebuah artikel muncul di blog Yandex yang membahas bagian dari bagian algoritme wawancara. Antara lain, dalam artikel ini, tautan diberikan ke kontes khusus yang berisi tugas-tugas yang serupa dengan yang ditawarkan oleh Yandex kepada kandidat mereka.
Setelah mendaftar di sistem, perhatian saya langsung tertarik oleh kemampuan untuk memecahkan masalah pada Haskell. Faktanya adalah bahwa meskipun saya suka pemrograman dalam bahasa ini, saya belum mengalami kemajuan lebih jauh daripada pelaksanaan tugas dari berbagai kursus platform online pendidikan. Setelah memutuskan bahwa solusi mereka dapat menjadi tantangan yang menarik dan akan meningkatkan level saya sebagai pengembang, saya melanjutkan untuk menyelesaikannya.
Siapa yang peduli apa yang akhirnya datang, selamat datang ke kucing.
A. Batu dan perhiasan
Dua baris huruf Latin kecil diberikan: string J dan string S. Karakter yang termasuk dalam string J adalah "perhiasan" dan termasuk dalam string S adalah "batu". Penting untuk menentukan berapa banyak karakter dari S yang secara bersamaan "permata". Sederhananya, Anda perlu memeriksa berapa banyak karakter dari S dalam J.
Tugas pertama adalah pemanasan, kita akan menyelesaikannya "di dahi". Kami mendefinisikan fungsi jeweleryCount :: String -> String -> Int , yang, menggunakan lilitan daftar yang dilewati oleh argumen kedua, merangkum semua kasus item yang sedang diproses dalam daftar pertama. Untuk keperluan ini, kita mendefinisikan fungsi elemInt berdasarkan pada fungsi elem , yang, tidak seperti yang terakhir, akan mengembalikan bukan Benar atau Salah, tetapi angka 0 atau 1. Dalam fungsi utama, Anda hanya perlu membaca dua baris, meneruskannya ke fungsi yang sesuai dan mencetak hasilnya. Putusan sistem pengujian OK, kami lolos ke tugas kedua.
jeweleryCount :: String -> String -> Int jeweleryCount j = foldr ((+).(elemInt j)) 0 where elemInt sx = fromEnum $ elem xs main :: IO () main = do j <- getLine s <- getLine print $ jeweleryCount js
Kode sumber untuk menyelesaikan ini dan tugas-tugas lain juga tersedia di repositori github.
B. Unit yang berurutan
Diperlukan untuk menemukan urutan unit terpanjang dalam vektor biner dan mencetak panjangnya.
Untuk mengatasi masalah ini, kami menerapkan fungsi rekursif yang akan melalui daftar yang ditransfer dan menghitung panjang urutan yang diperlukan. Dengan argumen fungsi, selain daftar itu sendiri, kami akan melewati panjang maksimum saat ini dan jumlah unit berturut-turut pada panggilan saat ini. Pertama, kita mendefinisikan basis rekursi pada daftar kosong, dan kemudian langkah rekursi itu sendiri.
Untuk membaca data input, kita mendefinisikan fungsi getUserInputs :: IO [Char] , di mana kita pertama kali membaca angka n - ukuran daftar, dan kemudian menggunakan kombinator, kita mendapatkan fungsi yang akan memanggil fungsi <<dapatkan> dapatkanLini n kali dan gabungkan hasilnya ke dalam daftar .
import Control.Monad (replicateM) onesCount :: [Char] -> Int onesCount xs = onesCount' xs 0 0 where onesCount' "" max curr | max > curr = max | otherwise = curr onesCount' (x:xs) max curr | x == '1' = onesCount' xs max $ curr + 1 | curr > max = onesCount' xs curr 0 | otherwise = onesCount' xs max 0 getUserInputs :: IO [Char] getUserInputs = do n <- read <$> getLine :: IO Int replicateM n $ head <$> getLine main :: IO () main = do xs <- getUserInputs print $ onesCount xs
Kami mengirim keputusan, putusannya OK. Kami melanjutkan.
C. Penghapusan Duplikat
Array bilangan bulat 32-bit dipesan dalam urutan yang tidak menurun. Diperlukan untuk menghapus semua pengulangan dari itu.
Mari kita mulai dengan implementasi sederhana. Kami mendefinisikan fungsi awal yang membaca angka, mencetaknya, dan mengembalikannya terbungkus dalam IO monad. Kami juga mendefinisikan fungsi deleteDoubles :: Int -> Int -> IO () , yang membaca angka dan mencetaknya hanya jika tidak sama dengan argumen kedua (kami akan meneruskan angka yang dibaca pada langkah sebelumnya di sana). Setelah itu, fungsi secara rekursif memanggil dirinya sendiri dan dengan demikian melanjutkan ke nomor berikutnya dalam aliran input. Basis rekursi adalah jumlah angka yang harus dibaca, kita akan memberikan argumen pertama.
import Control.Monad initial :: IO Int initial = do a <- read <$> getLine print a return a deleteDoubles :: Int -> Int -> IO() deleteDoubles 0 _ = return () deleteDoubles ta = do b <- read <$> getLine unless (a == b) $ print b deleteDoubles (t-1) b main :: IO () main = do t <- read <$> getLine unless (t < 1) $ initial >>= deleteDoubles (t-1)
Kami mengirim solusinya, melewati semua tes, dan sepertinya kami dapat beralih ke tugas berikutnya, tetapi menurut saya panggilan rekursif dari fungsi yang bekerja di monad IO lebih membingungkan daripada ringkas. Mari kita coba memperbaikinya.
Perhatikan bahwa, secara umum, Anda dapat terlebih dahulu membaca seluruh daftar angka (kami akan menggunakan kombinator replicateM yang sudah akrab dengan tugas kedua), kemudian meneruskannya ke fungsi murni yang menyaring semua pengulangan, dan akhirnya mencetak hasilnya.
import Control.Monad deleteDoubles' _ [] = [] deleteDoubles' prev (x:xs) | prev /= x = x:(deleteDoubles' x xs) | otherwise = deleteDoubles' x xs deleteDoubles (x:xs) = x:deleteDoubles' x xs getUserInputs :: Int -> IO [Int] getUserInputs t = replicateM t $ read <$> getLine main :: IO () main = do t <- read <$> getLine unless (t < 1) $ (deleteDoubles <$> getUserInputs t) >>= mapM_ print
Saya mengirim solusi, dan kekecewaan pertama adalah bahwa program ini tidak lulus tes 193 karena melebihi batas memori yang digunakan. Kesalahan utama adalah membaca seluruh daftar menjadi memori secara keseluruhan. Kami akan mencoba menghindari ini dan akan mengimplementasikan hibrida tertentu dari versi pertama dan kedua.
Perhatikan bahwa tugas untuk menghapus duplikat agak mengingatkan pada konvolusi asosiatif kiri: pada setiap langkah kita menghitung fungsi yang, tergantung pada item saat ini yang dibaca dan beberapa hasilnya, pada langkah sebelumnya memutuskan untuk mencetak, dan kemudian melanjutkan ke pasangan nilai berikutnya.
Fungsi yang mencetak atau tidak mencetak hasilnya tergantung pada argumennya, setelah itu mengembalikan argumen keduanya, yang dibungkus dengan IO monad, cukup sederhana, mari kita sebut saja langkah:
step :: Int -> Int -> IO Int step fst snd = unless (fst == snd) (print snd) >> return snd
Kami mengetahui apakah akan mencetak atau tidak, tergantung pada nilai yang diteruskan, tetapi bagaimana cara mengatur bacaan? Untuk melakukan ini, kita menggunakan fungsi konvolusi monad foldm :: (Lipat t, Monad m) => (b -> a -> mb) -> b -> ta -> mb , yang berlaku untuk daftar fungsi membaca.
Berdasarkan jenis fungsi foldM, kami mencatat bahwa pada setiap langkah "membongkar" hasil dari aplikasi fungsi sebelumnya terjadi di bawah tenda foldM itu sendiri. Jadi, pada setiap langkah kita hanya perlu memulai perhitungan monadik dari item daftar saat ini (pada kenyataannya, baca nomor berikutnya) menggunakan operator bind ( >> = ) dan berikan bersama dengan nomor sebelumnya untuk melangkah. Hasilnya, kami mendapatkan program berikut
step :: Int -> Int -> IO Int step fst snd = unless (fst == snd) (print snd) >> return snd initial :: IO Int initial = do a <- read <$> getLine print a return a getUserInputs t = replicate t $ read <$> getLine main :: IO () main = do t <- read <$> getLine unless (t < 1) $ do init <- initial foldM_ ((=<<) . step) init $ getUserInputs (t-1)
D. Generasi urutan braket
Diberikan bilangan bulat n. Diperlukan untuk mendapatkan semua urutan braket yang benar dengan panjang 2 ⋅ n, dipesan secara leksikografis (lihat https://ru.wikipedia.org/wiki/Lexographic_order ).
Hanya tanda kurung yang digunakan dalam tugas.
Dianjurkan untuk mendapatkan solusi yang bekerja dalam waktu yang sebanding dengan jumlah total urutan braket yang benar dalam respons, dan pada saat yang sama menggunakan kapasitas memori yang sebanding dengan n.
Tugas ini, seperti banyak tugas lainnya, di mana perlu untuk mendapatkan urutan yang memenuhi persyaratan tertentu (misalnya, tugas pertukaran koin, mengatur delapan ratu dan lain-lain, dapat dibaca secara lebih rinci di sini ), diselesaikan secara ringkas menggunakan daftar monad. Singkatnya, pendekatan ini didasarkan pada pengikatan monadik untuk daftar, yang artinya bergabung bersama dengan serangkaian operasi yang dilakukan pada setiap elemen daftar.
Tentukan fungsi rekursif menghasilkan ':: Int -> Int -> [[Char]] , yang mengambil jumlah tanda kurung untuk dimasukkan sebagai argumen kedua, dan jumlah tanda kurung buka tertutup sudah ditetapkan. Untuk langkah rekursi, kita membutuhkan dua fungsi bantu: mungkin - mengembalikan daftar tanda kurung yang dapat ditempatkan di langkah berikutnya, dan langkah - membuat panggilan rekursif ke fungsi generator dengan parameter yang diperlukan.
import Control.Monad(mapM_) generate :: Int -> [String] generate = generate' 0 where generate' _ 0 = [[]] generate' an = [x:xs | x <- possible, xs <- step x] where step '(' = generate' (a + 1) (n - 1) step ')' = generate' (a - 1) (n - 1) possible | n == a = ")" | a == 0 = "(" | otherwise = "()" main :: IO () main = do n <- read <$> getLine let result = generate $ n * 2 mapM_ putStrLn result
Kami mengirim solusi, dan kami memahami bahwa kami tidak memperhitungkan batasan yang dikenakan pada jumlah memori yang digunakan oleh program - solusi tidak lulus tes ke-14 karena melebihi batas memori yang digunakan.
Kami memodifikasi fungsi menghasilkan sehingga alih-alih menyusun seluruh daftar urutan braket yang benar, ia segera menampilkannya di layar. Untuk melakukan ini, kita harus menambahkan argumen ketiga ke fungsi - sebuah fragmen dari urutan yang dibangun untuk langkah saat ini. Saya perhatikan bahwa dalam implementasi ini kita akan membangun urutan dalam urutan terbalik - ini akan memungkinkan kita untuk menggunakan konstruktor daftar ( :) daripada operator concatenation yang lebih mahal ( ++ ).
import Control.Monad(mapM_) generate :: Int -> IO() generate = generate' "" 0 where generate' xs _ 0 = putStrLn $ reverse xs generate' xs an | n == a = step ')' | a == 0 = step '(' | otherwise = step '(' >> step ')' where step '(' = generate' ('(':xs) (a + 1) (n - 1) step ')' = generate' (')':xs) (a - 1) (n - 1) main :: IO () main = do n <- read <$> getLine generate $ n * 2
E. Anagram
Dua baris diberikan, terdiri dari huruf Latin huruf kecil. Diperlukan untuk menentukan apakah garis-garis ini adalah anagram, yaitu apakah mereka hanya berbeda dalam urutan karakter.
Untuk mengatasi masalah ini, kami akan menghitung berapa kali sebuah huruf muncul di setiap baris dan membandingkan hasilnya. Kami segera memahami bahwa daftar standar tidak cocok untuk kami, dan perlu menggunakan struktur data yang memungkinkan kami mengakses elemen secara efektif dengan indeksnya. Ada beberapa jenis data yang akan memenuhi kondisi kami, tetapi kami akan menggunakan standar array Data abadi. Array (masih ada setidaknya berbagai array yang dapat berubah, serta Data.Vektor ).
Untuk membangun array yang diperlukan, kita menggunakan fungsi hist :: (Ix a, Num b) => (a, a) -> [a] -> Array ab , yang, sesuai dengan daftar elemen yang ditransfer dan rentang di mana elemen-elemen ini seharusnya berada, membentuk sebuah array, yang menyimpan jumlah pengulangan elemen dari daftar. Fungsi ini, meskipun tidak termasuk dalam modul Data.Array, sering diberikan sebagai contoh menggunakan fungsi lain yang sudah ada di perpustakaan, accArray. Kami hanya dapat menyalin implementasinya dan menulis utama - manfaat perbandingan untuk kesetaraan untuk Array Char Int sudah ditentukan. Saya menarik perhatian Anda ke satu fitur yang bagus - sebagai indeks kita bisa menggunakan tidak hanya bilangan bulat, tetapi setiap perwakilan dari kelas Ix . Dalam kasus kami, Char memainkan peran alami dalam peran ini.
import Data.Array hist :: (Ix a, Num b) => (a,a) -> [a] -> Array ab hist bnds is = accumArray (+) 0 bnds [(i, 1) | i<-is, inRange bnds i] main = do arr1 <- hist ('a','z') <$> getLine arr2 <- hist ('a','z') <$> getLine if (arr1 == arr2) then print 1 else print 0
F. Menggabungkan daftar yang diurutkan
Diberikan k array bilangan bulat non-negatif yang diurutkan dalam urutan non-menurun, yang masing-masing tidak melebihi 100. Hal ini diperlukan untuk membangun hasil merger mereka: sebuah array yang diurutkan dalam urutan tidak menurun yang mengandung semua elemen dari array k asli.
Panjang setiap larik tidak melebihi 10 ⋅ k.
Cobalah untuk membuat solusi bekerja untuk waktu k ⋅ log (k) ⋅ n, jika kita mengasumsikan bahwa array input memiliki panjang n.
Menggabungkan dua daftar yang diurutkan adalah tugas daftar klasik dan dibahas dalam banyak kursus tentang pemrograman Haskell. Sebagai contoh, itu bisa diselesaikan sebagai berikut.
merge :: [Int] -> [Int] -> [Int] merge [] ys = ys merge xs [] = xs merge (x:xs) (y:ys) | x < y = x:merge xs (y:ys) | otherwise = y:merge (x:xs) ys
Kita bisa menggabungkan dua daftar. Dan apa yang harus kita lakukan dengan daftar daftar itu? Libatkan dengan fungsi ini! Dengan demikian, kita akan menggabungkan semua daftar menjadi satu, dan kita hanya perlu mencetaknya.
Solusi import Control.Monad merge :: [Int] -> [Int] -> [Int] merge [] ys = ys merge xs [] = xs merge (x:xs) (y:ys) | x < y = x:merge xs (y:ys) | otherwise = y:merge (x:xs) ys mergeLists :: [[Int]] -> [Int] mergeLists = foldl merge [] getUserInputs :: Int -> IO [[Int]] getUserInputs t = replicateM t $ do n <- getLine return $ tail $ read <$> words n main :: IO () main = do k <- read <$> getLine lists <- getUserInputs k let res = mergeLists lists mapM_ (putStrLn . show) res
Namun, solusi ini memiliki dua masalah serius - kompleksitas komputasi lebih tinggi daripada yang dibutuhkan - O (k ^ 2 ⋅ n) daripada O (k ⋅ log (k) ⋅ n) , ditambah lagi menggunakan banyak memori tambahan. Akibatnya, solusi ini gagal tes nomor 17 karena melebihi batas memori yang digunakan - 17,27Mb bukannya 10Mb yang diizinkan.
Meskipun kami tidak akan memperhatikan fakta bahwa angka yang dipasok ke input termasuk dalam rentang nilai yang terbatas, dan kami terus mencari solusi untuk kasus yang lebih umum.
Langkah selanjutnya adalah mencoba menerapkan pendekatan yang diusulkan dalam artikel asli dengan analisis tugas-tugas ini. Biarkan saya mengingatkan Anda bahwa itu didasarkan pada penggunaan struktur data yang menyediakan cara yang efisien untuk mengekstrak elemen minimum. Sebagai struktur seperti itu, pilih Data . Set . Kami menginisialisasi Set dengan daftar elemen pertama, maka pada setiap langkah kami akan mengekstrak dan mencetak elemen minimum, dan kemudian menambahkan elemen berikutnya dari daftar yang sesuai. Selain itu, kita akan memerlukan struktur Data.Sequence untuk menyimpan daftar itu sendiri. Itu dipilih karena alasan bahwa pada setiap langkah perlu baik untuk memiliki akses cepat ke daftar dengan indeksnya (yang daftar tidak dapat berikan), dan untuk mengubah elemen elemen ini tanpa perlu menyalin seluruh struktur (yang secara umum tidak dapat memberikan data yang tidak dapat diubah . Array ).
Dengan demikian, kami memiliki program berikut:
Solusi import qualified Data.Sequence as Seq import qualified Data.Set as Set import Control.Monad import Data.Foldable mergeLists :: Set.Set (Int, Int) -> Seq.Seq [Int] -> IO () mergeLists set seq | Set.null set = return () | otherwise = do let ((val, idx), set') = Set.deleteFindMin set print val if null (Seq.index seq idx) then mergeLists set' seq else mergeLists (Set.insert (head (Seq.index seq idx), idx) set') (Seq.adjust tail idx seq) getUserInputs :: Int -> IO [[Int]] getUserInputs t = replicateM t $ do n <- getLine return $ tail $ read <$> words n main :: IO () main = do t <- read <$> getLine lists <- getUserInputs t let init_seq = Seq.fromList (filter (not . null) lists) let init_heap = Set.fromList (zipWith (,) (toList (fmap head init_seq)) [0..]) mergeLists init_heap $ tail <$> init_seq
Kami mengirim solusinya dan mengetahui bahwa meskipun program tersebut mulai mengkonsumsi lebih sedikit memori (10.26Mb, bukannya 17.27Mb pada tes ke-17), itu masih belum memenuhi batas. Alasan untuk ini terletak pada kenyataan bahwa dengan keputusan ini, dengan satu atau lain cara, kita harus membaca seluruh data input ke dalam memori. Mari kita coba menghindari ini dengan bantuan solusi ketiga untuk masalah ini - mengurutkan dengan menghitung.
Kami telah melakukan penghitungan jumlah karakter yang masuk saat menyelesaikan masalah anagram sebelumnya. Juga, seperti dalam menyelesaikannya, kita akan menggunakan Data.Array . Pertama, kita mengimplementasikan fungsi addToArray :: Array Int Int -> [Int] -> Array Int Int , yang membentuk array berdasarkan yang sudah ada dengan meningkatkan nilai pada indeks yang sesuai dengan nilai-nilai dari daftar.
addToArray :: Array Int Int -> [Int] -> Array Int Int addToArray acc elems = accum (+) acc [(i, 1) | i<-elems]
Kemudian, kita akan menggunakan pendekatan yang kita kenal dalam masalah menghapus pengulangan - menggunakan konvolusi monadik, secara berurutan menerapkan fungsi addToArray ke array sumber k . Dan ... kami mendapatkan hasil yang sama dari 10,26Mb pada tes ke-17. Dan sekarang saatnya untuk mengingat bahwa foldl (yang analognya adalah foldM ) sesuai dengan urutan reduksi yang diterima pertama-tama akan memperluas seluruh rantai ekspresi bersarang dan baru kemudian melanjutkan ke perhitungan aktifnya. Seperti yang Anda ketahui, untuk mengatasi fakta ini, modul Data.List mengimplementasikan fungsi foldl ' , yang menggunakan fungsi seq :: a -> b -> b , yang pertama melemparkan argumen pertama ke bentuk normal head lemah, yaitu, menguranginya ke bagian luar - nilai fungsi atau konstruktor, dan kemudian mengembalikan yang kedua ( https://www.ibm.com/developerworks/ru/library/l-haskell4/index.html ). Kami tidak punya pilihan selain menerapkan fungsi foldM secara mandiri .
foldM' :: (Monad m) => (a -> b -> ma) -> a -> [b] -> ma foldM' _ z [] = return z foldM' fz (x:xs) = do z' <- fzx z' `seq` foldM' fz' xs
Akibatnya, jumlah memori yang digunakan pada tes ke-17 hampir separuh dan berjumlah 5.64Mb! Meskipun tes ke-17 dan ke-18 berhasil dilewati, implementasi ini tidak lulus tes ke-19 karena alasan yang sama bahwa batas memori terlampaui - 10,25Mb.
Oke, lanjutkan - kami belum mencoba Data.Array.Unboxed belum. Jenis array ini patut diperhatikan karena, tidak seperti standar, ia dapat menyimpan nilai-nilai itu sendiri, bukan petunjuk ke mereka ( https://wiki.haskell.org/Arrays#Unboxed_arrays ). Karena itu, array seperti ini memakan lebih sedikit ruang memori dan lebih efisien. Untuk menggunakannya, kita hanya perlu mengubah impor dan tipe fungsi, karena Data.Array dan Data.Array.Unboxed mengimplementasikan satu antarmuka array IArray yang tidak dapat diubah .
Kami mengirim solusi - konsumsi memori menurun 4,5 kali menjadi 2,26 MB, tetapi belum melewati batas waktu - waktu eksekusi adalah 1,09 detik. Dengan apa ini bisa dihubungkan? Dilihat oleh fakta bahwa waktu pelaksanaan tes yang tersisa tetap sama, saya pikir alasannya bukan karena array yang tidak kotak ternyata lebih lambat daripada yang kotak, tetapi khususnya sistem pengujian. Tampaknya tugas itu terputus segera setelah salah satu batasan dilanggar. Namun, dalam kasus yang sangat jarang, implementasi ini masih melewati tes ke-19 dengan hasil 0,98 detik, tetapi gagal tes nomor 20 juga karena melebihi batas waktu.
Setelah itu saya mencoba menggunakan analog yang tidak aman dari fungsi akum, yang secara teori seharusnya lebih cepat, berbagai metode buffering ( hSetBuffering :: Handle -> BufferMode -> IO () function), array IOArray yang dapat diubah , tetapi tidak satupun dari metode ini membawa hasil apa pun .
Saya tidak cenderung percaya bahwa batas untuk Haskell ditetapkan terlalu ketat, dan saya berharap masih ada solusi yang akan lulus semua tes. Dalam repositori proyek, saya memposting beberapa versi kode yang berbeda untuk menyelesaikan masalah ini (dengan Array dan IOArray), mungkin ini akan menjadi titik awal untuk solusi yang akan lulus semua tes.
Kesimpulan
Meskipun fakta bahwa hanya lima dari enam tugas yang menyerah kepada saya, saya menyelesaikan tugas utama saya - untuk mempraktikkan pemrograman fungsional. Tidak sedikit peran yang dimainkan oleh pembatasan parah pada sumber daya yang dikonsumsi oleh program, yang memaksa kami untuk mencari lebih banyak dan lebih banyak pendekatan baru untuk menyelesaikan masalah. Saya harap deskripsi mereka akan bermanfaat bagi mereka yang baru memulai perjalanan mereka dalam pemrograman fungsional
Apakah pendekatan fungsional nyaman untuk menyelesaikan masalah seperti itu? Jujur, saya punya kesan ganda. Di satu sisi, solusi untuk sebagian besar masalah ternyata sangat ringkas, dan alat-alat ekspresif Haskell sendiri, serta perpustakaan standarnya yang kaya, memainkan peran penting dalam hal ini. Di sisi lain, orang tidak bisa tidak mengakui bahwa dalam kebanyakan kasus pengelolaan sumber daya yang dikonsumsi dapat menjadi masalah tertentu, yang tidak akan memungkinkan penyelesaian masalah dalam pembatasan yang diberikan.