Early Interesting Problems - Happy Ladybugs

We all love interesting problems. The trouble is that it's hard to find suitably interesting problems for students when they're just learning the basics. In the very beginning the problems practically dictate the solution:

• loop over a list and add all the elements or calculate the sum of a list of integers.
• Determine if number is prime
• Convert a word into pig-Latin

It's not that there's no thought involved in solving these but the students already know the mechanics of solving these by hand so it's a direct translation into a program.

This isn't a bad thing and it is important but it's fun when we get to the next level. I've found that a number of the Hacker Rank archived competitions have "easy" problems that can be a good fit for beginners. One that I found and really like is Happy Ladybugs problem.

The problems is basically as follows:

You get a string of letters. Each letter represents a ladybug of a different color. Each letter also represents a location of the ladybug. A space (or underscore in the actual problem) represents a free space. For example "AABC DDA" is a line of 2 A colored ladybugs followed by a B colored one, C colored one, a blank space, 2 D colored and then one more A colored.

You can rearrange the line of ladybugs by swapping any ladybug with a blank space.

A ladybug is happy if it is next to another ladybug of the same color. The challenge is to determine if all the ladybugs can be made happy.

I like this problem because while it is non-trivial it is very approachable.

To me, the key is that while you can rearrange the list you don't have to. You only have to determine if it is possible to make the ladybugs happy. You don't actually have to do so.

The edge cases are pretty easy to deal with - a string of length one or two but then a little thought is required.

The first insight is that if there are no spaces, you can't rearrange the ladybugs so all you have to do is scan through the string to test to see if every ladybug has a neighbor of the same color.

The next insight, and the big one is that if you have at least one space you can arbitrarily re-order the string. You can show this is possible by using a single space to swap any two elements.

space = someletter
someletter = someotherletter
someotherletter = space

The final insight is that since you can arbitrarily re-order the ladybugs as long as you have at least 2 of each color, you can make them all happy.

Since my class is currently just starting dictionaries in Python we solved this with lists and then transitioned to dictionaries.

Here's a dictionary based solution:

def are_happy(s):
    '''
    This might miss some of the real edge cases in the hackerrank
    problem. I haven't read the problem carefully in over a year and 
    forget what it specified for things like lists of only spaces,
    lists with only one bug etc.

    Also, the Hackerrank question uses an underscore (_) instead of a space.
    '''
    # handle a string of less than 2 ladybugs
    if len(s)<2:
	return False

    # handle the string of 2 ladybugs - both must be the same and not a space
    if len(s)==2:
	return s[1]==s[0] and s[1] != ' '


    # handle the case of no spaces 
    if s.count(' ') == 0:
	# no spaces, every item must be next to one of the same color
	# so we loop from 1 to len-1 and for each item
	# check the one before and the one after
	# if we ever have an unhappy bug, we can just return False
	for i in range(1,len(s)-1):
	    if s[i] != s[i+1] and s[i] != s[i-1]:
		return False

	# if we ever get here every bug has at least one neighbor of the same color
	return True

    # if we get here it means there's at least one space so we can rearrange the bugs
    # however we please so as long as there are at least 2 bugs of each color
    # we can make them all happy

    # replace the spaces with "" since we don't want to count them
    # Since we know they were in the string we can rearrange but
    # they're no longer needed
    s = s.replace(" ","")

    # tally up all the bugs to see if there are at least 2 of each
    bugcounts = {}
    for bug in s:
	bugcounts.setdefault(bug,0) # set to 0 the first time we see this key
	bugcounts[bug]=bugcounts[bug]+1


    counts = list(bugcounts.values())

    # if there is any value of 1 in the counts then there's a lone ladybug
    # that can't be made happy
    # so we return True (happy) if there are 0 counts of 1 in our list 
    return counts.count(1) == 0 


bugs="abaccbe ff eggggggg"
print(bugs)
are_happy(bugs)

I love problems like these.

I just wish there was an easy way to find all contest problems of a certain level like "easy" or "medium." If anybody knows please share in the comments.