Google Foobar Challenge level 2 – Elevator Maintenance

TL, DR

Google Foobar is a hidden coding challenge by Google, and Elevator Maintenance is the challenge I solved using Python in order to complete level 2.

This post is part of a series on Google Foobar, with all the challenges I encountered. The full series is available here.

Keeping lifts in order

The third task I got for Foobar was to put order in the documentation for elevator maintenance. Apparently, there was plenty of different version and revisions (it looks like coding…), and they were not kept in good order. The full description of the challenge is the following:

Elevator Maintenance
====================
You've been assigned the onerous task of elevator maintenance -- ugh! It wouldn't be so bad, except that all the elevator documentation has been lying in a disorganized pile at the bottom of a filing cabinet for years, and you don't even know what elevator version numbers you'll be working on.
Elevator versions are represented by a series of numbers, divided up into major, minor and revision integers. New versions of an elevator increase the major number, e.g. 1, 2, 3, and so on. When new features are added to an elevator without being a complete new version, a second number named "minor" can be used to represent those new additions, e.g. 1.0, 1.1, 1.2, etc. Small fixes or maintenance work can be represented by a third number named "revision", e.g. 1.1.1, 1.1.2, 1.2.0, and so on. The number zero can be used as a major for pre-release versions of elevators, e.g. 0.1, 0.5, 0.9.2, etc (Commander Lambda is careful to always beta test her new technology, with her loyal henchmen as subjects!).
Given a list of elevator versions represented as strings, write a function solution(l) that returns the same list sorted in ascending order by major, minor, and revision number so that you can identify the current elevator version. The versions in list l will always contain major numbers, but minor and revision numbers are optional. If the version contains a revision number, then it will also have a minor number.
For example, given the list l as ["1.1.2", "1.0", "1.3.3", "1.0.12", "1.0.2"], the function solution(l) would return the list ["1.0", "1.0.2", "1.0.12", "1.1.2", "1.3.3"]. If two or more versions are equivalent but one version contains more numbers than the others, then these versions must be sorted ascending based on how many numbers they have, e.g ["1", "1.0", "1.0.0"]. The number of elements in the list l will be at least 1 and will not exceed 100.

Tests

The challenge also list a couple of test cases you will need to pass. However, it also indicates that there will be additional hidden tests that you need to pass. But you may not know what those test are about. Nice, uh?

Test cases
==========
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.
-- Python cases --
Input:
solution.solution(["1.11", "2.0.0", "1.2", "2", "0.1", "1.2.1", "1.1.1", "2.0"])
Output:
0.1,1.1.1,1.2,1.2.1,1.11,2,2.0,2.0.0

Input:
solution.solution(["1.1.2", "1.0", "1.3.3", "1.0.12", "1.0.2"])
Output:
1.0,1.0.2,1.0.12,1.1.2,1.3.3

Constraints

You also need to keep in mid a few constraints. They are divided between Java and Python ones.

Python
======
Your code will run inside a Python 2.7.13 sandbox. All tests will be run by calling the solution() function.
Standard libraries are supported except for bz2, crypt, fcntl, mmap, pwd, pyexpat, select, signal, termios, thread, time, unicodedata, zipimport, zlib.
Input/output operations are not allowed.
Your solution must be under 32000 characters in length including new lines and and other non-printing characters.

There are two important caveats to consider:

• Even if in the Python section there is no mention, execution time is limited. They say so in the Java section, but somehow they do not repeat it in the Python one.
• There are additional blacklisted libraries. For instance, I got a “BLACKLISTED CODE” exception when I tried to import the sys library

Putting a solution together

Spoiler alert: you can find a complete working solution below. However I think that just copy-pasting a solution will not do you any good. But maybe looking at the flow and understanding the thinking behind the code may put you in the right direction to solve the challenge and learn something in the doing!

Coming to our challenge, we basically need to put in order versions for elevator maintenance according to major, minor, and revision numbers. A simple lexicographic comparison of the full string would not work, because – just taking one of the test cases – 1.0.2 > 1.0.12 when we compare character by character.

You may put in place your own algorithm that:

• Breaks all string in the three components (major, minor, and revision), taking into account the cases when minor and/or version are missing (you may set them to -1 in this case, to satisfy the requirements).
• Sequentially compares all three items to return a sorted list.

However, at least in Python 2 (and all the way up until 3.11), there is a much simpler solution. Please let me introduce you the distutils package.

Old tools are always useful

The distutils package is the old tool for compiling and distributing Python packages. In time, it has been replaced by setuptools and the plan is to remove distutils from the standard Python library from version 3.12. However, for Google Foobar we are stuck in a Python 2.7 world…so legacy tools are still actual.

Documentation about distutil.version is not abundant nor updated, as it may be the case for any deprecated package. This is the introduction from the Sourceforge page dedicated to the LooseVersion class:

Version numbering for anarchists and software realists.

Sourceforge documentation on distutils.version.LooseVersion

Despite all warnings that distutils is old and broken, and in some corner case could fail, I think it’s more than suitable for the challenge. We have clear indications that versions are composed by dot-separated numbers or just numbers.

This last point is the one that disqualify the sister class StrictVersion, which received an equally amusing introduction on its documentation page:

Version numbering for anal retentives and software idealists.

Sourceforge documentation on distutils.version.StrictVersion

In fact, StrictVersion will fail on version numbers like 1 or 99, that do not have any dot notation.

Getting to the point

A very simple function that helps us sorting all version numbers is the following:

from distutils.version import LooseVersion
def solution(l):
    return ",".join(sorted(l, key=LooseVersion))

It is very simple and elegant in my opinion. in only one line you can indicate your sorting key – the LooseVersion class – sort the list, and return it as a comma-separated string.

Once you are ready, you can check your work by typing:

verify solution.py

If you completed your work correctly, a happy green message like this one will greet you:

You can then submit the solution as indicated. And that’s it for Google Foobar Challenge level 2 – Elevator Maintenance!

Since I graduated to level 3, i received a referral code to invite a friend into the Foobar Challenge. It’s single use, so I hope my friend used it wisely!

I will write about each individual challenge in a dedicated post. You will find the post series via the link at the end of this post, stay tuned for updates!

Related links

• Google Foobar link (it is by invitation only)
• My series of posts on Google Foobar link
• disututil.version.LooseVersion documentation page
• disututil.version.StrictVersion documentation page
• Warning on disututil.version.LooseVersion issues on edge cases page

Do you like our content? Check more of our posts in our blog!