CODEWITHSUNDEEP
haskell
CSnerd
CSnerd

Reputation: 2239

Fill the list based on specific condition

I had an interview, and interviewer gave me a problem about list.

For example, the original list would be like [0,1,0,0,2,0,0,1], the 2 should fill the list as far as it can unless it encounters 1. So the output would be [0,1,2,2,2,2,2,1].

One example:

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

output:

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

Another example:

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

output:

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

How to solve this problem?

Upvotes: 2

Views: 255

Answers (4)

effectfully
effectfully

Reputation: 12715

Here is code-golf solution:

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]

Results in

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

Upvotes: 1

thor
thor

Reputation: 22520

You can use a Deterministic Finite Automaton with two states s_fill and s_keep as follows:

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)

In the state s_fill, the function fill2 keeps filling 2 onto the head of an accumulator, until 1 is met, in which case the DFA jumps to state s_keep.

In s_keep, fill2 pushes each element itself back to the accumulator w until 2 is encountered, in which case the DFA jumps to s_fill.

The recursion terminates when the remainder list (the first parameter of s_{keep,fill}) is empty. In this case, the function return the reverse of the accumulator as elements near head were pushed deeper near the tail of the accumulator.

So far, the function fill2 fills 2 from left to right. The rest of the job is to fill from right to left on the result of (fill2 xs), which can be easily obtained on the reverse of (fill2 xs) as follows:

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

Output:

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

and 

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

--- Original Version of Code ---

(Thanks to @ØrjanJohansen for pointing out the issue of the original version of the code below with the initial state and direction of fill).

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)

Upvotes: 4

jamshidh
jamshidh

Reputation: 12070

It is easier to solve this problem if you think of 1 as whitespace, and 0 and 2 as letters in words

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

First split the incoming data into "words", then simply map words to all 2s if a single 2 is inside of a word.

This will work O(n) in the input size, and can even handle an infinite input stream.

examples

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]

output

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

Upvotes: 3

luqui
luqui

Reputation: 60503

If we can get a function fillRight that fills to the right, i.e.

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

then we can easily achieve the full solution:

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

so we can spend our energy on fillRight. As others have pointed out, this is a simple state machine, which I would write in the following way which elucidates the state transitions (note how I added a parameter to keep track of the state):

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

then close it off by setting an initial state

fillRight = fillRight' False

Upvotes: 3

Related Questions