Заполните список, основываясь на конкретном состоянии

Question

У меня было интервью, и интервьюер дал мне проблему с списком.

Например, первоначальный список был бы как [0,1,0,0,2,0,0,1], то 2 должен заполнить список, насколько это возможно, если он не встречает 1. Таким образом, выход будет [0,1,2,2,2,2,2,1].

Один пример:

[0,2,1,0,1,2,0,0] 

выход:

[2,2,1,0,1,2,2,2] 

Другой пример:

[2,0,0,0,1,1,0,1] 

выход:

[2,2,2,2,1,1,0,1] 

Как решить эту проблему?

Answer 1

Вы можете использовать Deterministic Finite Automaton с двумя состояниями s_fill и s_keep следующим образом:

fill2 :: [Int] -> [Int] 
fill2 xs = s_keep xs [] 
    where s_keep []  w = reverse w 
     s_keep (c:cs) w = if c == 2 then s_fill cs (c:w) else s_keep cs (c:w) 
     s_fill []  w = reverse w 
     s_fill (c:cs) w = if c == 1 then s_keep cs (c:w) 
          else s_fill cs (2:w) 

В состоянии s_fill, функция fill2 держит заполнения 2 на голову аккумулятора, пока 1 не будет выполнено, в котором если DFA переходит в состояние s_keep.

В s_keep, fill2 толкает каждый элемент сам обратно к аккумулятору w до 2 не встречается, и в этом случае DFA перескакивает на s_fill.

Рекурсия завершается, когда список остатков (первый параметр s_ {keep, fill}) пуст. В этом случае функция возвращает обратную сторону аккумулятора, так как элементы, расположенные рядом с головой, толкнут глубже около хвоста аккумулятора.

Пока функция fill2 заполняет 2 слева направо. Остальная часть работы должна заполнить справа налево от результата (fill2 xs), который можно легко получить на обратной стороне (fill2 xs) следующим образом:

fill2' xs = reverse $ fill2 $reverse $fill2 xs 

Выход:

*Main> fill2' [0,1,0,0,2,0,0,1] 
[0,1,2,2,2,2,2,1] 
*Main> fill2' [0,2,1,0,1,2,0,0] 
[2,2,1,0,1,2,2,2] 
*Main> fill2' [2,0,0,0,1,1,0,1] 
[2,2,2,2,1,1,0,1] 

и

*Main> fill2' [0,0,1,0,2,0,1] 
[0,0,1,2,2,2,1] 

--- Оригинальная версия кодекса ---

(Спасибо @ ØrjanJohansen за то, что он указал на исходную версию кода ниже с начальным состоянием и направлением заполнения).

fill2 :: [Int] -> [Int] 
fill2 str = s_fill str [] 
    where s_keep []  w = reverse w 
     s_keep (c:cs) w = if c == 2 then s_fill cs (c:w) else s_keep cs (c:w) 
     s_fill []  w = reverse w 
     s_fill (c:cs) w = if c == 1 then s_keep cs (c:w) 
          else s_fill cs (2:w) 

Answer 2

Если мы можем получить функцию fillRight, которая заполняет вправо, т.е.

fillRight [0,2,1,0,1,2,0,0] = [0,2,1,0,1,2,2,2] 

то можно легко добиться полного решения:

fillLeft = reverse . fillRight . reverse 
fill = fillLeft . fillRight 

поэтому мы можем потратить свою энергию на fillRight. Как уже отмечалось, это простое состояние машины, которые я хотел бы написать следующим образом, проясняет переходы состояний (обратите внимание, как я добавил параметр для отслеживания состояния):

fillRight' :: Bool -> [Int] -> [Int] 
fillRight' _  []  = [] 
fillRight' True (0:xs) = 2 : fillRight' True xs 
fillRight' False (0:xs) = 0 : fillRight' False xs 
fillRight' _  (1:xs) = 1 : fillRight' False xs 
fillRight' _  (2:xs) = 2 : fillRight' True xs 

затем закрыть он выключен путем установки исходного состояния

fillRight = fillRight' False 

Answer 3

это легче решить эту проблему, если вы думаете о 1 как пробельных и 0 и 2 как буквы в словах

import Data.List 

words'::[Int]->[[Int]] 
words' [] = [[]] 
words' x = 
    case rest of 
    (1:after) -> first:words' after 
    _ -> [first] 
    where (first, rest) = break (== 1) x 

fill::[Int]->[Int] 
fill x = intercalate [1] $ 
    map (\x -> replicate (length x) (if 2 `elem` x then 2 else 0)) $ 
    words' x 

Сначала разделите входящие данные на «слова», а затем просто сопоставьте слова всем 2, если один из двух слов находится внутри слова.

Это будет работать с O (n) в размере ввода и может обрабатывать бесконечный поток ввода.

---

примеры

main = do 
    print $ fill [1,0,0,0] 
    print $ fill [1,0,0] 
    print $ fill [0,0,1,0,2,0,1] 
    print $ fill [0,1,0,0,2,0,0,1,0,1,2,0,1] 
    print $ fill [0,1,0,0,2,0,0,1,0,0,1,2,0,1] 
    print $ fill [0,2,1,0,1,2,0,0] 
    print $ fill [2,0,0,0,1,1,0,1] 
    print $ fill [0,1,0,0,0,0,0,1] 

выход

[1,0,0,0] 
[1,0,0] 
[0,0,1,2,2,2,1] 
[0,1,2,2,2,2,2,1,0,1,2,2,1] 
[0,1,2,2,2,2,2,1,0,0,1,2,2,1] 
[2,2,1,0,1,2,2,2] 
[2,2,2,2,1,1,0,1] 
[0,1,0,0,0,0,0,1] 

Answer 4

Вот код-гольф решение:

fill xs = foldr step replicate xs 0 0 where 
    step 0 r l m = r (l + 1) m 
    step 1 r l m = replicate l m ++ 1 : r 0 0 
    step 2 r l m = r (l + 1) 2 

main = do 
    print $ fill [1,0,0,0] 
    print $ fill [1,0,0] 
    print $ fill [0,0,1,0,2,0,1] 
    print $ fill [0,1,0,0,2,0,0,1,0,1,2,0,1] 
    print $ fill [0,1,0,0,2,0,0,1,0,0,1,2,0,1] 
    print $ fill [0,2,1,0,1,2,0,0] 
    print $ fill [2,0,0,0,1,1,0,1] 
    print $ fill [0,1,0,0,0,0,0,1] 

Результаты в

[1,0,0,0] 
[1,0,0] 
[0,0,1,2,2,2,1] 
[0,1,2,2,2,2,2,1,0,1,2,2,1] 
[0,1,2,2,2,2,2,1,0,0,1,2,2,1] 
[2,2,1,0,1,2,2,2] 
[2,2,2,2,1,1,0,1] 
[0,1,0,0,0,0,0,1]