Happy Ladybugs

See the original problem on HackerRank.

Solutions

This problem can be solved by considering a few things:

  1. if a ladybug’s color is unique in the set, the ladybug will never be happy (the solution is “NO”)
  2. if 1) does not occur and if there is at least one empty cell, then the solution is always “YES” since it’s always possible to rearrange the ladybugs in the best position
  3. if 2) does not occur then the solution is “YES” only if all the ladybugs are already happy (because they cannot be moved)

The first two properties are easy to check by using a frequency table (can be implemented with a map/dictionary or with a statically-sized array, since the number of letters is known - \(|A-Z|\)|).

The last property is a linear scan through the array. Basically, we check for each element if it is different from either the previous or the next one.

C++ and unordered_map for frequency table

Here is a possible implementation in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

string happyLadybugs(string s)
{
    unordered_map<char, int> occ;
    for (auto c : s)
        occ[c]++;

    if (count_if(begin(occ), end(occ), [](auto p) { return p.second == 1 && p.first != '_'; }))
        return "NO";

    if (occ['_'] != 0)
        return "YES";

    for (auto i=0; i<s.size(); ++i)
    {
        if ( (i==0 && s[i] != s[i+1]) ||
             (i==s.size()-1 && s[i] != s[i-1]) ||
             (s[i] != s[i-1] && s[i] != s[i+1])
           )
        {
            return "NO";
        }
    }
    return "YES";
}

Python, imperative

Here is the same approach in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def happyLadybugs(n,b):
    hasEmpty = b.count('_') > 0
    for x in b:
        if x != '_' and b.count(x) == 1:
            return "NO"
    if hasEmpty:
        return "YES"
    for i in range(0,n):
        if (i == 0 and b[i] != b[i+1]) or (i == n-1 and b[i] != b[i-1]) or (b[i] != b[i-1] and b[i] != b[i+1]):
            return "NO"
    return "YES"

Python, functional

Simple variation coded by applying some functional ideas:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def happyLadybugs(s):
    hasEmpty = b.count('_') > 0
    for x in b:
        if x != '_' and b.count(x) == 1:
            return "NO"
    if hasEmpty:
        return "YES"

    flag = len(s)==1 or (s[0]==s[1] and s[len(s)-2] == s[len(s)-1])
    zipped = zip(s, s[1:], s[2:])
    return "YES" if flag and all(map(lambda (x1,x2,x3): x2==x1 or x2==x3,  zipped)) else "NO"

Python, add leading and trailing character to simplify code

Just for fun, the code above can be simplified by adding a fake character both at the beginning and at the end of the string:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def happyLadybugs(s):
    hasEmpty = b.count('_') > 0
    for x in b:
        if x != '_' and b.count(x) == 1:
            return "NO"
    if hasEmpty:
        return "YES"

    s = '*' + s + '*' # <- fake
    zipped = zip(s, s[1:], s[2:])
    return "YES" if all(map(lambda (x1,x2,x3): x2==x1 or x2==x3,  zipped)) else "NO"

This way, the boundary conditions are automatically handled in the zip | map | reduce part of the solution.

Haskell, groupBy and sort to avoid frequency table

A pure functional approach with haskell. Note that here we use sort with groupBy to get the occurrences of each value, so the complexity is more than linear.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import Data.List

groupsLength = fmap length . groupBy (==)
isAlreadyHappy = all (> 1) . groupsLength
hasEmptySlots = any (== '_')
noUniqueValues = all (> 1) . groupsLength . sort . filter (/= '_')

happyLadybug b = isAlreadyHappy b || (hasEmptySlots b  && noUniqueValues b)

parseInput = (\xs -> [x | (x,i) <- zip xs [0..], odd i]) . tail . lines

yesNo True = "YES"
yesNo False = "NO"
serializeOutput = unlines . fmap yesNo

main = interact $ serializeOutput . (fmap happyLadybug) . parseInput

Haskell, frequency table

This can be improved by finding all occurrences of ‘A’..‘Z’ characters, lowering the complexity to linear.

1
2
3
4
5
6
7
8
9

import Data.List

isAlreadyHappy = all (> 1) . fmap length . groupBy (==)
hasEmptySlots = any (== '_')
count x = length . filter (== x)
occurrences b = fmap (\c -> count c b) ['A'..'Z']
noUniqueValues = all (/= 1) . occurrences

happyLadybug b = isAlreadyHappy b || (hasEmptySlots b  && noUniqueValues b)

C, low level code

This is a low level C implementation which uses only primitives, without the help of any standard library function. Note that here we rely on the prerequisite that only characters from A to Z and _ can be in the input. Any other character causes undefined behavior because d is accessed with an invalid index.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

int happy_ladybug(const char* b) {
  int d[26] = {0};
  int has_empty = 0;
  int already_happy = 1;
  int adj_count = 0;
  int left_c = 0;

  for (; *b != 0; ++b) {
    int c = *b;

    if (c == '_') {
      has_empty = 1;
    } else {
      d[c - 'A'] += 1;

      if (c == left_c) {
        adj_count += 1;
      }

      if ((adj_count < 2) && (left_c != 0)) {
        already_happy = 0;
      }

      if (c != left_c) {
        adj_count = 1;
      }

      left_c = c;
    }
  }

  if ((adj_count < 2) && (left_c != 0)) {
    already_happy = 0;
  }

  if (already_happy) {
    return 1;
  }

  for (int i = 0; i < 26; ++i) {
    if (d[i] == 1) {
      return 0;
    }
  }

  return has_empty;
}

Rust, iterate String, frequency table a BTreeMap

In Rust, a String is not just a collection of charaters, because Rust strings can be unicode. For this reason, we cannot access the nth element of a String. The code below iterate the String with three iterators.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


fn happy_ladybugs(b: &String) -> bool {
    let mut freq_table = std::collections::BTreeMap::new();

    b.chars().for_each(|x| {
        if x != '_' {
            *freq_table.entry(x).or_insert(0) += 1;
        }
    });

    let has_empty = b.chars().any(|x| x == '_');

    let has_unique =
        freq_table.iter().any(|(_, count)| *count == 1);

    let mut is_already_happy = true;

    let mut it = b.chars();

    if let Some(mut l) = it.next() {
        if let Some(mut c) = it.next() {
            // Check if first is alone
            is_already_happy &= l == c;

            for r in it {
                is_already_happy &= (c == l) || (c == r);
                l = c;
                c = r;
            }

            // Check if last is alone
            is_already_happy &= l == c;
        } else {
            // When there is only one element
            is_already_happy &= l == '_';
        }
    }

    is_already_happy || (has_empty && !has_unique)
}

Rust, frequency table as an array and input as slice of bytes

We know that the input can contain only ASCII characters, from A to Z and _. With these constrains, we can access the string data as bytes, so we can access single bytes using their indexes. It is even possible to allcate the frequency table in the stack, as a simple array of size 26.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

fn happy_ladybugs(b: String) -> bool {
    const COLORS_COUNT: usize = (b'Z' - b'A' + 1) as usize;

    // Use string as a slice of bytes, so we can access nth elements with
    // constant complexity.
    let b = b.as_bytes();

    match b.len() {
        0 => true,
        1 => b[0] == b'_',
        2 => b[0] == b[1],
        n => {
            let has_empty = b.contains(&b'_');

            let has_unique = {
                let mut freq_table = [0; COLORS_COUNT];

                for &x in b {
                    if x >= b'A' && x <= b'Z' {
                        let index = (x - b'A') as usize;
                        freq_table[index] += 1;
                    }
                }

                freq_table.contains(&1)
            };

            let is_already_happy = (b[0] == b[1])
                && (1..n - 1).all(|i| {
                    (b[i] == b[i - 1]) || (b[i] == b[i + 1])
                })
                && (b[n - 1] == b[n - 2]);

            is_already_happy || (has_empty && !has_unique)
        }
    }
}

Rust, lazy evaluation

We can slightly modify the code above to gain lazy evaluation, using closures. This is helpful to avoid creating a frequency table when we already know there are no empty cells or ladybugs are already happy.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

fn happy_ladybugs(b: String) -> bool {
    const COLORS_COUNT: usize = (b'Z' - b'A' + 1) as usize;

    // Use string as a slice of bytes, so we can access nth elements with
    // constant complexity.
    let b = b.as_bytes();

    match b.len() {
        0 => true,
        1 => b[0] == b'_',
        2 => b[0] == b[1],
        n => {
            let has_empty = || b.contains(&b'_');

            let has_unique = || {
                let mut freq_table = [0; COLORS_COUNT];

                for &x in b {
                    if x >= b'A' && x <= b'Z' {
                        let index = (x - b'A') as usize;
                        freq_table[index] += 1;
                    }
                }

                freq_table.contains(&1)
            };

            let is_already_happy = || {
                (b[0] == b[1])
                    && (1..n - 1).all(|i| {
                        (b[i] == b[i - 1]) || (b[i] == b[i + 1])
                    })
                    && (b[n - 1] == b[n - 2])
            };

            is_already_happy() || (has_empty() && !has_unique() )
        }
    }
}
strings  frequency table 
We've worked on this challenge in these gyms: modena  padua 
comments powered by Disqus