Explaining 2016 Codejam round 1A

This post is going to explain how I got my answers for codejam round 1A. Hopefully, I will be able to continue writing these posts as the 2016 codejam competition furthers. But that have to depend on whether I will be able to answer the questions.

Yes, I know that Google does provide its own question analysis (it’s available here). So why do I write it, repeat it again?

Google’s answers are writtne by expert coders who have a wealth of experience writing algorithms, thinking of solutions. Most that are stuck on the problem are probably not. The little hints given might not be sufficient, hence, the tutorial.

Also partly for myself, in case I have forgotten how to solve it have couldn’t understand the analysis by Google.

Problem A

This problem is a very simple “step-by-step” problem, as long as you can figure out the method of generating the string, you can get the answer by adding characters to the string one by one.

The method goes like this: to get the largest possible string (alphabetically), process the characters one by one, if the character is larger than the character at the start of the answer, add it to the front, if not, add it to the back.

There really is not much in this, it is a pattern questions, as long as you can figure it out, the solution is easy to write.

Submission for small input

N = input()
for n in range(N):
    chars = raw_input()

    ans = chars[0]
    chars = chars[1:]

    for c in chars:
        if c>=ans[0]:
            ans = c+ans
        else:
            ans += c

    print 'Case #%d: %s'%(n+1, ans)

Problem B

The second problem is actually very simple, but it is the question where I found that I am deeply dissapointed in myself. This is the problem where you have to determine the values of a missing row from a grid.

When I first started on the problem, I jumped in immediately and started working on the algorithm to find the correct order of the grid from the different pieces of information. But there was one part I overlooked — because of a few rules that are placed in the problem, there is a much much simpler answer to it.

This is the key rule: “all the row and columns must be in ascending order, from left to right, from top to bottom, with no repetition in each row or column”. From this rule, we can use the existing information from the grid to determine the missing numbers and the order it is in.

When you are in a grid, and you are required to record the sequence of the rows and columns, there a case of double counting, where each person is counted exactly twice. Since only one strip (either row or column) is missing, whatever number only appears an odd number of times, must be one of the missing number.

What if one of the row/columns have two of the same number? Doesn’t that mean that there will be an even number of occurance for that value? Well, that’s covered by the rules, “there is not repeated number in each row”.

What if we got the numbers, how do we arrange them? No problem, it’s also covered by the rules — “all sequences of the rows and columns must be in ascending order”.

success for small input

T = input()
for t in range(T):
    N = input()

    all = []
    for n in range(N*2 - 1):
        all += map(int, raw_input().strip().split())

    line = []
    for i in set(all):
        if all.count(i)%2: line.append(i)

    s = ' '.join(map(str, sorted(line)))
    print 'Case #%d: %s'%(t+1, s)

Problem C

This is one of the more classical problems, using graph as a model for the problem. To do this question, we will have to refer to a diagram for explaination. This is the diagram taken from Google’s codejam answer.

graph diagram

Try drawing a few graphs on your own. And you probably see how the friendship circle will work out. As explained in the analysis, the way to form the longest chain of amiable students sitting together is to make use of the students who mutually like each other.

But if the chain using the mutual liking students are too short, the only are option in forming a circle is to find the cycle with the longest cycle length. (eg. biggest loop), like in the first example.

So there is 2 parts to the solution. One, find the cycles in the graph. Two, Find the longest tail from the cycles with length of 2, 2 kids liking each other, then add up all of them together to form one big circle (just like in the picture, with the 2nd and 3rd part combined).

Okay, my solution for finding all the cycles in the graph might not be the most efficient, but it is definitely a method that works, and it works well within the time limit.

As for the second part when we need to find the tail, it is a depth first search for the longest link. Don’t get it? Basically we follow the data and start tracking back each chain, starting of the kid in the length-2 cycle. We will try all the combinations and then return the length of the tail which goes the deepest.

success

# current, data, not-to-be-counted
def longest(current, data, nocount): 
    nodes = [n for n in data[current[-1]] if nnocount]    
    if not nodes:
        return current

    max_line = []
    for n in nodes:
        temp = longest(current+[n], data, nocount)
        if len(max_line)<len(temp):
            max_line = temp
    return max_line

T = input()
for t in range(T):
    N = input()
    d = [int(i)-1 for i in raw_input().split()]

    c2 = []

    # normal cycle counting
    c_max = 0
    mv = range(N)
    while mv:
        c = [mv[0]]
        mv = mv[1:]

        while len(c)1][0]
        idx = c.index(start)
        c.remove(start)
        c_len = c.index(start) - idx + 1

        if c_max  m: m= c_max

    print 'Case #%d: %d'%(t+1, m)

Conclusion

The problems are solvable, but I do need sometime to write the solution and really think about the edge cases. I hope that 1B will be more lenient (although it is unlikely). And if I do understand and manage to get a solution, I will share them again when I get the writeup written.

Explaning the codejam qualification round

It has been a while since I worked on writing algorithms, but I joined the 2016 codejam anyways. And the qualification round has just passed.

I took quite a bit of time, but managed to finish some questions. In case I forget how I solved those problems, I am going to walk through how I solved them. For those interested, go ahead and read the questions here before continuing.

Problem A

This is the insomia problem. I read the question and tried a little counting myself. It seemed impossible to not get any of the digits, after all, any N can be used in counting.

Unless that number is zero of course, since it will always be zero. Seems like an easy problem. I should have ko problem. I implememted some sort of counting algorithms, and it is done.

Success for small input

N = input()
for n in range(N):
    x = input()
    if not x:
        print 'Case #%d: INSOMNIA'%(n+1)
    else:
        C = []
        X = 0

        while len(C)<10:
            X += x
            for c in str(X):
                C += [c]
            C = list(set(C))

        print 'Case #%d: %d'%(n+1, X)

Problem B

Oh the pancake problem. I am pretty proud of this one. So the problem goes, there is a stack of pancakes which apparently has only one correct side. Find the minimum number of flips required to make them all right side up.

This, I feel is a slight rehash of the original pancake problem which has different sizing pancake. But just flipping them right side up, shouldnt be a problem.

What is the best way of making them all right side up, I asked myself. I wrote out the plus plus minus minus format that codejam used to represent a stack of pancakes.

I put them left to right, couldnt see anything helpful. Then decided to put them rightway around, top to bottom, just like how pancakes should be. Immediately it struck me, of course, i will have to fix the top pancakes first.

The logic goes these way, I make the first flip to form the largest right side up pancake stack possible. After that, subsequent flips will slowly include the bottom pancakes and finally the whole stack will all face the same side. The final will be the one that turns the whole stack right side up if its all facing the wrong direction.

Talking in terms of plus plus minus minus syntax, we are just trying to count the number of groups in the stack, so ++ can be considered a group, --- is another group, even a single + can be a group.

Success for small input

N = input()
for n in range(N):
    s = raw_input().strip()

    while s.count('--'):
        s = s.replace('--', '-')
    while s.count('++'):
        s = s.replace('++', '+')

    a = len(s)-1 + 1*(s[-1]=='-')

    print 'Case #%d: %d'%(n+1, a) 

Problem C

Yeah, this is the troublesome one, its not really fun though, so I never really wrote out code for it, but I will describe the logic behind it.

So first you need some kind of function that can generate the strings of ones and zeros. In python, there is permutation generator in itertools (those interested, go and take a look). But remember, front and back can only be 1.

Then to convert into different bases, you can write your own function, or you can copy it from somewhere, it doesnt matter, just get the job done.

Primality test, you need not go through the sieve method, I would use Fermat’s Last Theorem for this, its faster.

Then the divisors, since we are picking out only 500 from the potentially many number of choices, I would recommend you just test out the first 30 primes, if nothing, just skip it.

Problem D

The L G L G problem. This is the most brain juice using one out of the rest, but that gave chance for the small input, but first read the question, try to get what the question is about before reading on.

So basically, the problem is just to check if there is any G. One shortcut is to check the orignal sequence, if it does have gold, then the sequence will pass the test.

The is the simple, but not optimal solution for when s==k (the assumption that makes everything easier).

For the small input, this is the logic — as long as we are able to check the starting sequence, we will be able to confirm the presence of gold.

And if the first one is lead, the starting k number of tiles will always be the original sequence. If there is gold, it will be confirmed, if all those tiles turn out to be lead, you can be sure thelat there is no gold to be found.

Success for small input

N = input()
for n in range(N):
    k, c, s = [int(c) for c in raw_input().split(' ')]
    a = ' '.join(range(1,k+1))

    print 'Case #%d: %s'%(n+1, a)

Now, thats just for when the s==k. But what is the optimal number of tiles to check for? How exactly do we go about choosing which tile to check? Now, that is where the fasinating part comes in, hold on your hat as we enter the land of mumbo jumbo.

The basic idea is still the same. We are still going to check through all of the original values to seaech for gold. But because of the complexity layers, when you check one of the tiles in the final layer, you are actually checking for a few of the original tiles.

Simple example to illustrate. The pictorial below will show the different layers of pattern after a few complexity. 1 represent the first symbol of the original pattern,2 represents the second, so on and so forth. We make a different assumption in this drawing, we assume that for each symbol, it is just going to replace it with the orginal sequence. For simplicity sake, let’s assume k==2.

2 3

Do you see it? Let’s take the 3rd number from the last row as an example. It branched out of the 2nd value of the original pattern, which is then branched out from the first. I like to call this the “working backwards” method. See below for pictorial version.

2 3 bolded

Now, if we want to check through all k of the orignal pattern, we will have to come up with a method that can give us the position of the tiles that can check the most number of original tiles. From the example about we probably can see the pattern.

Lets try once more to see if we can finalize the formula. This time k==4 and c==3. Now here is the chart.

4 3 bolded
Underscore represent the whole set of “1 2 3 4”

Oh noes, what about the 4th tile? Sadly, only one tile can be checked per layer. This means that when we reach the last layer, the rest of the tiles will have to be checked individually. So here is the correct chart that shows the tiles to check.

4 3 bolded all

All that’s left is to come up with the formula to obtain the position, I will leave that to you, but if you need help, you can refer to the code below.

All the thinking above translated to code

N = input()
for n in range(N):
    k, c, s = [int(c) for c in raw_input().split(' ')]

    x = 1
    for i in range(c):
        p = (i+1)%k or k
        x = ((x-1)*k)+p

    a = [x]
    for i in range(k-c):
        a += [x+i+1] 
    if len(a)>s:
        a = 'IMPOSSIBLE'
    else:
        a = ' '.join([str(i) for i in a])

    print 'Case #%d: %s'%(n+1, a)

Review: How Maths explains the world

This book gives us peek into technical world of mathematics. You get introduced to the whys and hows of elementary math (geometry, for example). Then there is the maths that we don’t even know exist (paradoxes in voting system for example). Below is a summary of the book (at least the parts I found interesting).

JavaScript promises

This is just a basic introduction to javascript promises. This is inspired by this article, which explains the intricacies very well.

javascript callbacks

One of the unique feature of javascript is the use of callback functions. Its extremely essential considering the fact that javascript is a single threaded language.

For those that have no idea what I am talking about, here is how callback functions are usually used.

function getData(callback){
    callback(loadDataFromSomewhere());
}

getData(processData);

When the getData is done, the result is passed into processData.

Callbacks are all well and good, until you start working on some complicated API project and all hell break loose. If you have been working with callbacks for a while now, you would probably have heard the term “pyramid of doom”, where your function calls stretches all the way to the right.

But there are more to [promises] than nice looking code. Using callbacks deprives us of basic programming features such as return and throw. More importantly, when something is wrong, there is no way to track down where that mistake is. All these results in bad code design.

Javascript promises

Promise, as defined by the A+ spec, is like an upgraded version of callback functions.

For most modern browsers, promises are implemented as window.Promise, but for those who are looking good polyfill, is one option you can look at.

Basic functions (then & catch)

If you use promises, there is two things you cannot do without, the functions then and catch. This knowledge should be sufficient to use most promise-based library (eg. pouchdb).

The function then accepts 2 parameters, the first is the function that the data is passed into if everything goes well, the second is triggered when some error has occured.

As for catch, it’s just a shortcut to write then(null, function). So when an error is thrown, the error object is passed into the function.

The promise stack

You can use promises as callback functions, but there is a much nicer way to format your code.

remotedb.allDocs(...).then(function (resultOfAllDocs) {
    return localdb.put(...);
}).then(function (resultOfPut) {
    return localdb.get(...);
}).then(function (resultOfGet) {
    return localdb.put(...);
}).catch(function (err) {
    console.log(err);
});

There is one special feature about promises. If you return a promise in the function, the result is passed into the next then function. This way, you can chain different sections of code together. (The allDocs, then the put, then the get).

The catch function at the end is a good practice. Putting it at the end ensures that whenever an error is thrown, it will be caught. Regardless of which level the error occurs, the error will still be logged.

Advanced functions (resolve & reject)

When you create your own library using promises, you tend to face the need to wrap your synchronous code as asynchronous code. Here is where resolve comes in.

function someAPI(){
    return Promise.resolve().then(function(){
        // some error might be thrown here
        return 'someSynchronousValue';    
    }).then(/* ... */);
}

This way, all your code will be promise-y, even the simple functions. This ensures code design consistency.

Besides, when you use promises this way, you can catch error easily. Gone are the days of slow and inefficient debugging.

So what about reject? The reject function returns a promise that is rejected immediately.

new Promise().resolve('some value').then(function(val){
    // do something to val
});

new Promise().reject(new Error('some error')).then(function(val){
   // do something to val
   // but this function will be skipped
}).catch(function(e){
    // this function is called immediately    
});

Promise.all (The foreach in promises)

There is another use case for promises. Let’s say we have a database query that returns a few rows, and we wanna update those rows. Typically, this is what the code will look like (in the minds of those non-promise ninjas).

getAllRows().then(function(result){
    result.rows.forEach(function(row){
        // update value of row
        row.val += 1;
        updateRow(row);              
    });
}).then(function () {
    // Naively believe all docs have been updated now!
});

But here is the right way to do it, with Promise.all of course.

getAllRows().then(function(result){
    return Promise.all(result.rows.map(function(row){
        //update value of row
        row.val += 1;
        return updateRow(row);
    }));
}).then(function(arrayOfUpdateRowResults){
    // all docs have been updated    
});

End

Well, all these are just the basics of using promises, there are certainly alot more to learn. If you are interested, I implore you to give this article a read. You will learn much much more.