Google Foobar - Please Pass the Coded Messages

This week I got around to closing out Level 2 Part 2 of the Google Foobar Challenge - "Please Pass the Coded Messages"

Given a list of digits, our job is to find the order of those digits that yields the maximum number that is divisible by 3.

So a list like [3, 1, 4, 1, 5, 9] would yield 94311, and the list [3, 1, 4, 1] gives us 4311. 

Here’s something to keep in mind that will make our job easier: a number is divisible by 3 if and only if the sum of its digits is also divisible by 3. 

So we could have the following numbers: 375, 753, 357, and 735, and they’d all be divisible by 3, because the sum of their digits is divisible by 3.

If we were to rearrange the digits in the number ‘892’, they will never be divisible by 3, because the sum of their digits will always be 19, and 19 isn’t divisible by 3. We’re left with a non zero remainder each time:

298 / 3 = 99.33333333

829 / 3 = 276.3333333

289 / 3 = 96.33333333

892 / 3 = 297.3333333

This helps a lot. We just need to sort the list once in descending order: so [3, 1, 4, 1, 5, 9] becomes [9, 5, 4, 3, 1, 1], and then we just need to determine the digits to exclude from this sequence while still making it divisible by 3.

Let’s try with our first sequence of digits: [3, 1, 4, 1, 5, 9].

We’ll sort in descending order to yield: [9, 5, 4, 3, 1, 1]. Stringing these digits together we get 954311.

In this case, 954311 is not divisible by 3, so let’s try removing 4 from that series to get us the next largest number: 95311.

Well, 95311 is also not divisible by 3, so let’s take the 5 out and this time try with the same number of digits but keeping the 4 in there: 94311. 94311 is divisible by 3 (since 94311 / 3 = 31437) and so we stop. The answer is 94311.

The next list is easier: [3, 1, 4, 1]. After sorting we get 4311, and 4311 is divisible by 3 (4311 / 3 = 1437), so we end right there.

Pay attention to this tidbit in the instructions : “L will contain anywhere from 1 to 9 digits.”  We’re only going to be given short sequences to work with. Therefore, we can exploit bit masking to represent the combinations of digits that we’ll include/exclude from our number. 

We can start with a bit mask of 1 shifted left by the length of the list (6 in the case of [9, 5, 4, 3, 1, 1]) which yields the binary value 1000000 (or 64 in decimal). We then start counting backwards starting from mask - 1 (63 in decimal or 111111). For each bit position, 1 means we’ll include the digit from that position in the list, and 0 means we don’t include it:

111111 means we include all digits — which would be 954311. 

111110 would be every digit except the last one: 95431.

101010 would yield: 941.

If a combination is divisible by 3 and it’s the max number we’ve encountered, we’ll record it as the max value we have so far. We’ll return whatever that value is at the end. Sometimes it won’t be possible to create any number that is divisible by 3 from a sequence of digits, and in those cases we return 0.

Here’s my full answer in python, which passed all the test cases:

def solution(l):

    lLen = len(l)

    max = 1 << lLen

    l.sort(reverse=True)

    maxAttempt = 0

    for mask in reversed(range(max)):

        attempt = ""

        for index in range(mask.bit_length()):

            attempt += str(l[index]) if (mask >> index) & 1 == 1 else ''

        if attempt == '':

            attempt = 0

        attempt = int(attempt)

        if attempt % 3 == 0:

            if attempt > maxAttempt:

                maxAttempt = attempt

    return maxAttempt

And with that, it’s time to move on to level 3!

Introduction to Genetic Algorithms

If you are interested in learning genetic algorithms and are looking for a quick introduction - watch this 10 minute tutorial I put together. It introduces you to the basics you'll need to start coding genetic algorithms from scratch. 

Share your questions/feedback/thoughts in the comments!

The 7 programming languages every coder should know

New programming languages seem to emerge constantly in the tech industry. How do you prioritize the ones to learn without spending the rest of your life bouncing from one new language to the next? Regardless of what languages you’re currently coding in, these 7 languages below are must learn for any coder hoping to stay competitive in the job market.

Python - Python is one of the most popular programming languages in the world. It’s straightforward, intuitive syntax, coupled with other aspects like its dynamic typing, contribute to its popularity among not just beginners, but all programmers in general. Its vast offering of libraries has fueled its expansion into a never-ending list of domains: data science, machine learning, statistics and analytics, web development, game making, robotics, are all areas python thrives in. Some of the most popular frameworks (i.e: PyTorch for machine learning, Django for web development, Pygame for making video games) are built on top of Python. Python can be used standalone, or used alongside other languages by extending them with python bindings [include link to bindings page]. Put simply, Python is everywhere. Although it’s certainly not the speediest language, its advantages and pervasiveness wins it a top spot on this list. 

Java - The stance on java seems to be polarized - there are those who love it, and those who avoid it at all costs. Regardless of what group you fall into, the fact is is that it’s in high demand and it’s not going anywhere anytime soon. If you’re looking into a company that is building large-scale enterprise class applications, it’s highly likely their tech stack is java-based. Get familiar with Java, practice building a RESTful service with Spring, and you’re already well on your way to landing a back-end development role. 

C# - A primary rival and competitor to Java, you’ll find this object-oriented language arise in a lot of the same use cases. If a company is producing enterprise applications and isn’t a java shop, there’s a very good chance C# is at the heart of its products. Created by Microsoft, C# was original officially supported by Windows only. Eventually it made its way over to linux and OSX via open source compilers like mono, and now is officially supported cross-platform by .NET core. Anything from little desktop apps to high powered web applications and APIs are written in C#. It will allow you to also break ground into some technologies that are predominantly java territory. Want to build mobile apps for Android, but don’t want anything to do with java? You could always use Xamarin with C# (although I personally wouldn’t recommend doing this based on experiences).

C - You might think its pointless to learn C unless you’re going to build an operating system or write firmware for embedded systems. Why bother with such an “old” technology? Although C is certainly a go-to in low level projects, you should still pick it up even if your plan is to stick with higher level languages. Coding in C will give you a newfound appreciation for the benefits that higher level and managed languages bring to the table. In languages like C# and Java, Garbage collection and memory management, for instance, are all handed in the background while you’re blissfully unaware of the work that is involved in those processes. As such, it’s easy for devs to take these features for granted. Just because you can safely ignore these processes doesn’t mean there aren’t opportunities to optimize your programs from a memory perspective, and coding in C will provide you with the skills to think in ways that will allow you to do exactly that.

Assembly (aka ASM) - When you’re making a function call in C — how are the arguments passed to the function? I don’t mean syntactically: spelling out the function name, followed by parentheses and the comma separated arguments, as is the common method in many languages, but I mean…. how are they actually passed? This is but one example of something so low level that you aren’t typically aware of it — even in C. Just like It’s hard to understand all the things that higher level and managed languages get you until you’ve programmed in C, it’s hard to realize the benefits you get with C until you’ve written in Assembly. Assembly is just about as low-level as you can get, second only to literally writing the machine code instructions yourself. Each architecture has its own assembly language. If you were going to assemble a program for Intel and AMD processors, you’d be writing either x86 or x64, (or both depending on if you’re assembling code for 32 or 64bit). Embedded devices (things like digital cameras, mobile phones, portable game systems) commonly run MIPS and ARM architectures, and so for those you’d be writing MIPS assembly and ARM assembly, respectively. All code, no matter how high level, will eventually result in the actual native machine code executing, so it makes a lot of sense to understand the language that boils down to machine code. 

Javascript - Virtually every modern web page you encounter will have some degree of javascript running in the background. Besides being the backbone of front-end frameworks like Rect, it can be used for back-end development as well via runtimes such as node.js, PurpleJS, and RingoJS. It’s also arguably the easiest of this list to get started with. You don’t need much to get started with it — you can start coding client-side javascript right now with the default text editors and browsers that ship with your OS. 

SQL - If you code professionally you’re going to come face to face with a SQL query at some point or another. Unless you’re planning on specifically becoming a SQL developer, you don’t need to master every minute detail and construct. However, every developer should be proficient in the basics: SELECT/INSERT/DELETE/CREATE TABLE statements, joins, views, etc. You should be fine with the basics when you’re a dev working in a codebase using and reading SQL in conjunction with the other primary project language(s).

By fostering a deep understanding of Python, C#, and Java, you’ve placed yourself in a high sought out position in the job market. Additionally, you’ll have a strong foundation of the OOP paradigm you can translate over to other object-oriented languages like C++ should you need or want to. Although learning lower level languages such as C and Assembly might not align with your immediate goals, they will give you a deeper understanding of the inner workings of software — instilling you with a mindset focused on efficiency and optimization. You’ll leverage this mindset to make wiser and more optimized design decisions, letting you stand out amongst peers who don’t have access to these experiences. 

Google Foobar: Level 2

I finally had time to start Level 2 of the Google Foobar Challenge. This level contains 2 challenges. 

The instructions for challenge 2A ("Lovely Lucky LAMBs") are as follows:

At first glance this seems like this is going to require coding in a bunch of rules — but once you extrapolate the patterns from the hints and test cases they give you, the actual code is a breeze to implement. 

The calculations for determining the max and min # of henchmen are going to have separate formulas, so you might want to break this out into two functions — at least initially, to make it a little easier to work with and test the min/max cases. So a template for the solution might look a little like this: 

def min_henchmen(total_lambs): 

   return count


def max_henchmen(total_lambs):

   return count


def solution(total_lambs):

   return max_henchmen(total_lambs) - min_henchmen(total_lambs)

Let’s address the logic for the ‘stingy’ cases first. When we’re stingy with the LAMB payouts, we’re giving the least amount of lambs to the most amount of henchmen — all the while keeping them all happy and content. As the included test cases states: if you were as stingy as possible with 10 LAMBs, you could pay 4 henchmen with 1, 1, 2, and then 3 LAMBs. This satisfies the requirements because:

- The first most junior henchman receives exactly 1 lamb - (1 lamb like above)

- The 2nd most junior henchman gets at least as many LAMBs as the most junior henchman (1 lamb)

- A henchman will revolt if the share of their next two subordinates combined is > their share (Well, we gave out 2 here which is at least 1+1, so we’re good)

Following this logic then, if we wanted to be as stingy with 12 lambs, we could compensate 5 henchmen: 1, 1, 2, 3,  and then 5 LAMBs.

And so on. Seeing a pattern here? The max # of henchmen that we can give lambs out to can be determined by the Fibonacci sequence. We can handout LAMBs to more henchmen until the sum of all the LAMBs are less than or equal to total_lambs.

Now we just need to work out our min_henchmen() function. The point this time is to be as generous as possible with our LAMB payouts. This means they’ll be fewer henchmen receiving LAMBs, and we’ll have to fulfill all the requirements just like before. 

So again let’s consider our first case. If we have 10 LAMBs in total, fulfill all the requirements to keep the henchmen happy, and be as generous as possible, we’d be able to pay just 3 henchmen: 1, 2, and 4 LAMBs, respectively. In this scenario, we wouldn’t be able to pay a fourth henchman with only 3 remaining lambs without causing a revolt. In order to pay 4 henchman, we would need at least 15 lambs. So the payouts would go like this: 1, 2, 4, 8, etc (respectively). In a nutshell, calculating the minimum amount of henchman (while maximizing the # of LAMBs each henchman receives) is be found by a basic geometrics series.

And then our solution function is easy - we simply return the difference by whatever was returned from the max_henchmen() function - min_henchmen().

This is my complete implementation in python:

I didn’t test the code extensively, but it passed all the test cases. 

On to the second challenge of level 2!

Google's Secret Foobar Challenge

The other day while googling around I came across this message: 

“Curious developers are known to seek interesting problems. Solve one from Google?” Sure, why not?  Upon accepting the challenge I was logged into foobar and presented with a greeting that told me I had managed to infiltrate “Commander Lambda’s” sinister organization.

I did some quick searching around to find other people who had encountered this, and what their experiences were with it. Turns out this has been around for quite some time —but can be quite elusive. Getting into foobar can be tricky, and there’s no guarantee you will. Luck is a major contributor to stumbling upon this, and it’s highly dependent on searching for the right programming related keyword(s). When you’re lucky enough to search for the right topic though, the page will slant a little and the banner with the foobar invite will appear at the top of Google like the one I got.

There are five levels in total. Each level contains a number of challenges. The amount of challenges increases per level along with complexity. There’s some randomness to the content prepared for each foobar invite: your level 1 might not be the same as someone else’s level 1, your level 2 may or may not be the same as someone else’s level 2 content, etc. Each challenge goes like this: you are presented with a puzzle, and you have to code up a solution that will solve that puzzle. Once you start a level, a timer starts counting down and you have until the timer ends to complete and submit a solution. You navigate through the foobar console using basic *nix like commands — if you have any experience with any of these the interface will be pretty intuitive for you. You have the choice of submitting a java or python solution for each challenge.

It seems that in its earlier days foobar was utilized as a secret hiring tool for Google to spot talented coders. It seems that it is no longer actively utilized for that purpose, however. Still, it's a fun exercise to try, and even if you don't end up getting a prize out of it, the challenges can help to sharpen your algorithmic thinking skills and get prepare you for any future coding tests and challenges you might face. 

As I get around to it, I'll post my code and walkthroughs for each level of the challenge.

Level 1: Prison Labor Dodgers

This was the first challenge I encountered and the premise of it was pretty simple:

Two lists are given to you, named ‘x’ and ‘y’, that might look like this:

x: [13, 5, 6, 2, 5], y: [5, 2, 5, 13]

Or this: x: [14, 27, 1, 4, 2, 50, 3, 1], y:[2, 4, -4, 3, 1, 1, 14, 27, 50]

In any case, the goal is to identify the unique id, or basically the number that is present in one of those lists but not the other. In the case of the two lists above, the solutions (unique IDs) would be 6, and -4, respectively.

One thing to keep in mind is that there won’t be any inherit ordering or sorting of the numbers in each list, so you can’t count on this in your solution if you intend on taking any shortcuts.

This is what I came up with for a quick & dirty solution:

def solution(x, y):

    first = x

    second = y

    if len(x) > len(y):

        second = x

        first = y

    exists = {}

    for ID in first:

        exists[ID] = True

    for ID in second:

        if ID not in exists.keys():

            return ID

First I make sure the lists are ordered and processed accordingly based on their size (larger list gets scanned first to ensure we look at all possible values). We then iterate through the second list, and check whether that number exists in our dictionary; if not then that’s our unique ID and we return that. 

I decided to roll my own implementation rather than use any of python’s features (you could, for instance, convert both lists to sets and then compute the symmetric difference of them). There are many ways you could go about this. Make sure to verify your code solution for each challenge prior to submitting it! This will indicate whether there are any test cases your code hasn’t passed — so you can go back and try to find what part isn’t working. If you wait to submit a solution only to find out it fails a couple cases, you will fail that challenge. I’ve only done 1 challenge so far and passed all the test cases… so I don’t even know yet what happens if you fail a level.

Another note: Google has test cases prepared in the background - but you don’t actually know what these are, so your solution actually has to work. Expect that google has thought of the various edge cases that could occur from your code, because they typically have, and have built those in to the tests.

The Factory Design Pattern

One of the reoccurring topics that will be covered on everythingdev will be design patterns. Having a solid understanding of design pattern methodologies will not only lead to becoming more proficient in the OOP paradigm, it can also just make your life much easier when implementing certain modules within a software project.

Right now we’ll be covering the Factory Design Pattern.

Let’s say we’re writing a paint program which allows the user to draw some shapes. Right now we can draw rectangles and circles. We’ll create a ‘Shape’ class that can handle rectangles and circles:

public class Shape {

     private int width = 0;
     private int height = 0;
     private double radius = 0.0D;
     private Boolean isRectangle = false;
     private Point[] hexagonPoints = null;  

     public Shape(int width, int height) {    
          this.isRectangle = true;
          this.width = width;  
          this.height = height;
     } 

     public Shape(double radius) {
          this.radius = radius;
     }

     public void draw() {

         if(isRectangle)

               // handle drawing the rectangle on screen...

          } else {

               // otherwise it’s a circle, and handle drawing the circle on screen….
          }
      }

}

The shape class has two constructors: one that accepts width and height parameters, and another which accepts a radius parameter. If the first constructor is called, the object will represent a rectangle, if the second is called it will be a circle. Easy enough. 

 

Soon our software has become a huge hit and we receive a request to add support for another shape type: hexagons. Hexagons will have width and height properties like rectangles. We decide to recycle an existing constructor we have for rectangles, and simply add a Boolean ‘isHexagon’ parameter to distinguish between a rectangle or hexagon, and update our draw() method accordingly.

Now our shape class looks like this:

public class Shape {

     private int width = 0;
     private int height = 0;
     private double radius = 0.0D;
     private Boolean isRectangle = false;
     private Boolean isHexagon = false;
     private Point[] hexagonPoints = null;  

     public Shape(int wfaceidth, int height, Boolean isHexagon) { 
          if(isHexagon) {
                    this.isHexagon = true;
          }
          else {
                    this.isRectangle = true;
          }   

          this.width = width;  
          this.height = height;
     } 

     public Shape(double radius) {
          this.radius = radius;
     }

     public void draw() {

         if(isRectangle)

               // handle drawing the rectangle on screen...

          }
         else if(isHexagon) {
                  // draw hexagon
         }
          else {

               // otherwise it’s a circle, and handle drawing the circle on screen….
          }
      }

}

Couple of emerging problems with our Shape class:

• It’s rapidly becoming messier (imagine what it’s going to look like as we add support for more and more distinct shapes).
• The more functionality we have, the harder debugging specific shape functionality will get.
• The onus is on the developer to juggle all the constructors and initialization parameters in their head to remember how to build each shape.

Here’s another issue: when we changed the first constructor to accommodate hexagons, it forced us to update references to that constructor. So if we have 17 different classes within our codebase that initializes a shape using that constructor, that’s 17 classes that need to be updated along with the change to our Shape class. In other words, those 17 classes are overly reliant on being aware of the underlying implementation details of the shape class. We can also say that these classes are tightly coupled. We’ll solve these problems by implementing a factory class to handle creation of the shape objects instead.

We’ll start by creating a ‘Shape’ interface containing some properties and methods that are common to all Shapes regardless of their specific type:

public interface Shape {

                public void draw();
                public void getShapeType();
                public void setColor();

}

And we’ll refractor the Shape classes so they all implement our Shape interface:

class Rectangle implements Shape

                public void draw() {…….}
                public void getShapeType(){…….}
                public void setColor(){…….}

}

class Circle implements Shape
                public void draw() {…….}
                public void getShapeType(){…….}
                public void setColor(){…….}

}

class Hexagon implements Shape

public void draw() {…….}
            public void getShapeType(){…….}
            public void setColor(){…….}

}

Then we’ll build a Factory class that will handle the creation of the various shapes:

public class ShapeFactory {

                final int TYPE_CIRCLE = 0;
                final int TYPE_OVAL = 2;
                final int TYPE_RECTANGLE = 3;
                final int TYPE_HEXAGON = 4;

                public Shape buildShape(int shapeType) { 

switch(shapeType):

case TYPE_CIRCLE: return new Circle(double radius)
                                // do stuff to make circles…

case TYPE_RECTANGLE: return new Rectangle(int width, int height)
                                // do stuff to make rectangles…

case TYPE_HEXAGON: return new Hexagon(int width, int height)
                                // do stuff to make hexagons…

default: return null;
}

                }

                return null;

}

Our Factory allows the developer (as well as other components within the system) to take a more hands-off approach to requesting certain shapes. Instead of getting caught up in the intricate under the hood details of a class (“It’s a rectangle not a hexagon… so I need to pass this parameter instead…”, or "Which constructor do I use for hexagons again?", etc) we simply make a request to our factory, “We want X type of shape”, pass the relevant information, and get back that type of shape. Then our other components can draw it, drag it, resize it, and do whatever else our program allows the user to do with shapes

The design of a Factory class could get much fancier. Having an enumerator that lists the shape types rather than those hardcoded integers is a good idea, for instance. Even in its current state though, our Factory class has already pushed us in the right direction to having a much cleaner design and loosely coupled system involving classes and objects that aren’t so heavily reliant on knowing each other’s implementation details.