Xorlothian Paintings

A Microsoft Coding Competition Problem

Posted by Matthew Roach on October 7, 2016

This is the third instalment in the Microsoft Coding Competition Problems series. Today I wrapped up the final 1-point question, so stay tuned for the next few problems as they should be getting more complex. Of the three 1-pointers, this one might have been the easiest and the quickest to code.

The Problem

Xortholians are a proud race and have a rich history of rainbow-inspired art. One Xortholian artist from the last century made a particularly beautiful series of paintings using only the colors in the rainbow.

Each of these paintings consists of two rows of paint.

The first row is a series of equally sized squares, each of them being a primary color or blank, i.e. each is one of the following: "red", "yellow", "blue", "blank". No two neighboring spaces in the first row will ever have the same color (including blank).
For example, a first row could be:

red blank blue yellow

The second row is a series of colors whose length is one more than its corresponding first row. Each color, in order, is a combination of the two colors above it. Red and blue, for example, make purple, while red and blank would make more red.
A second row generated from the above colors would be:

red red blue green yellow

To be clear, possible colors are "red", "orange", "yellow", "green", "blue", and "purple". Xortholians do not recognize indigo or violet.

Your goal as an aspiring young Xortholian Art and Mathematics dual-major is to determine what some paintings' first row is based on the corresponding second row.

Example Input

red purple green orange purple purple orange yellow yellow yellow

Example output

red blue yellow red blue red yellow blank yellow

The Solution

To keep this a bit easier, I will not be reading the input from a file. Instead, I have just copied the input to a list, inList. The list outList is our resulting list (the first row of colours). I have also defined a dictionary that has secondary colours as the key, and the primary colours that make it as the value.

The general steps to this solution are as follows:

  • Loop through each colour in the input, except for the last one.
  • Append the first colour of inList (the input), to outList. The first colour will always be the same.
  • For each colour that's not the first, get the value of inList at i, the value of outList at i-1, and the list from dict where inList[i] is the key.
  • Then compare outColor (outList[i-1]) with the list from our dict where inColor is the key. If they're equal, append the other colour to result, and if they're not equal append that colour.

Additionally, we have to worry about blanks:

  • If outColour is blank, append inColour
  • If inColour is equal to outColour, append blank

Now, it's quite possible that the above explanation didn't make any sense. Luckily this problem is very simple to visualize.

Let's say we are on the second iteration of the loop. We have just appended red to outList. So the temporary variables get set as follows:
  inColour = purple
  outColour = red
  inColor_List = [red, blue]

So with these values we need to fill in X. So we compare inColor_List[0] to outColour and they are equal. Therefore X cannot be red because that would state that red and red make purple. Becuase inColor_List[0] and outColour are equal, X is inColor_List[1] or blue. This is correct since red and blue make purple.

outList ->    red      	X	
inList  -> red   purple   green   orange   purple   purple   orange   yellow   yellow   yellow
				

Let's look at one of the blank colour cases.

outList ->    red     blue    yellow	red     blue      red    yellow      X
inList  -> red   purple   green   orange   purple   purple   orange   yellow   yellow   yellow
				

Here inColour = yellow and outColour = yellow, which gets caught by the elif statement, and the value of X is blank. Yellow and blank make yellow which is correct. On the next iteration, inColour = yellow and outColour = blank, therefore we append inColour to the result, which is correct since blank and yellow make yellow.

And here is the full result.

outList ->    red     blue    yellow	red     blue      red    yellow    blank    yellow
inList  -> red   purple   green   orange   purple   purple   orange   yellow   yellow   yellow
				

Code

"""
Xortholian Paintings
A Problem from Microsoft's Coding Competition

By: Matthew Roach
October 6, 2016
"""

#inList is our input, the second row of colours
inList = ['Red','Purple','Green','Orange','Purple','Purple','Orange','Yellow','Yellow','Yellow']
#outList is the output, the first row of colours that we need to generate
outList = []
"""
dict holds a Key and a Value where:
    -> Key is a secondary colour
    -> Value is a list of two primary colours that make the colour Key
"""
dict = {'Purple': ['Red','Blue'], 'Green': ['Blue','Yellow'], 'Orange': ['Yellow', 'Red']}

#for each element of inList, except for the last
for i in range(len(inList)-1):
    if i == 0:  #the first colour of inList is always the first colour of outList
        outList.append(inList[i])
    else:
        inColor = inList[i]
        outColor = outList[i-1]
        if outColor == 'Blank':
            outList.append(inColor)
        elif inColor == outColor:
            outList.append('Blank')
        else:
            inColor_List = dict.get(inColor)
            if outColor == inColor_List[0]:
                outList.append(inColor_List[1])
            else:
                outList.append(inColor_List[0])
print outList