Google Code Jam Round 1C 2010: Rope Intranet

I think this problem should be easy to everyone. When I started to solve this problem, I have switched to Python 3 from 2, so there were several technical difficulties, including:

1. in python 3, next() is no longer generator’s method. Instead, you should do next(generator)
2. in python 3, print “blah” is no longer possible. print(“blah”) is correct.

 

def get_stream(file):
    for line in file:
        for token in line.strip().split():
            yield token

def get_int(stream):
    return int( next(stream) )

def open_file(file):
    return open(file, "r")


s = get_stream( open_file("A-large-practice.in") )
o = open("A-large-practice.out", "w")

num_of_cases = get_int(s)
for i in range(0, num_of_cases):
    num_of_pairs = get_int(s)
    pairs = []
    for pair in range(0, num_of_pairs):
        pairs.append( (get_int(s), get_int(s)) )
    pairs = sorted( pairs, key=lambda x: x[0], reverse=True)
    crossing = 0
    for k in range(0, num_of_pairs-1):
        crossing += len( list( filter(lambda x: x[1] > pairs[k][1], pairs[k+1:]) ) )
    o.write("Case #{}: {}\n".format(i+1, crossing))
        
o.close()

Received certification of Coursera course, “Software Defined Networking”

 

Today, I have received the certification of completion for Coursera course, “Software Defined Networking“, which is my second accomplishment in Coursera. As all these course were very refreshing and encouraging, I have started a new course, “Algorithmic Thinking” which is very easy comparing to “Algorithms, Design and Analysis Part I”. But I think that this course is also very interesting and helpful (most of all, to learn Python).

“Algorithms: Design and Analysis, Part 1” week 3 finished

After finishing the programming homework, I found out that the implementation can be more improved, by giving more chances to be selected to edges whose end nodes have greater pan-outs than others.

However, after solving some problems for this week, I concluded that I need more firm background on Mathematics, especially on Probabilities. My mind is used to think in procedural ways, and that’s not good for understanding randomized algorithms. 

From yesterday, I’m solving exercises from Lehman lecture note. After finishing the lecture note, I think I should look through the proofs of the randomized algorithms again. 

Two Computer Science Lecture Notes worth to read

There is a lecture note called “Mathematics for Computer Science” by Eric Lehman, F. Tompson Leighton, and Albert R. Meyer. There two versions: old, and new. Both are good, but the older version is much more easy-to-read. The new one is full of exercises. So, if someone is trying to learn discrete mathematics, I personally recommend to read old one first, and check the fluency using the new one, by solving the exercise problems. 

Google Code Jam Round 1A 2008: Milkshake

This question was really frustrating, took 9 hours to come up with a solution. Yes, I’m old.

Hint:
This question is about changing ‘menu’ until that every customer’s order is satisfied. As one of the goal is to minimize the number of malted batches, we only add a malted favor to the menu when there is a customer who might be able to find satisfaction by that.

def get_stream(file):
    for line in file:
        for token in line.strip().split():
            yield token

def get_int(stream):
    return int(stream.next())

def get_solution(stream):
    
    # initialize flavors vector
    nf = get_int(stream)
    malted = [0] * nf
    
    # number of customers
    nc = get_int(stream)
    orders = []
    for i in range(0, nc):
        samples = get_int(stream)
        s = []
        for j in range(0, samples):
            f = get_int(stream)
            m = get_int(stream)
            # should put f-1 because we use array index
            # starts from zero
            s.append( (f-1, m) )
        orders.append( s )

    # now, orders have all the orders from customers.
    # orders[0] is orders from customer 0,
    # orders[1] is orders from customer 1, ...

    everyone_satisfied = False
    escape = False
    while not everyone_satisfied and not escape:
        everyone_satisfied = True
        for customer_order in orders:
            # customer order is a list.
            this_customer_satisfied = False
            change_to_try = -1
            for f, m in customer_order:
                if m == malted[f]:
                    this_customer_satisfied = True
                    break
                if m == 1:
                    change_to_try = f
            if not this_customer_satisfied:
                everyone_satisfied = False
                if change_to_try == -1:
                    # no more trials to make
                    escape = True
                else:
                    malted[change_to_try] = 1
            
    if everyone_satisfied:
        return ' '.join(map(str, malted)).strip()
    else:
        return 'IMPOSSIBLE'

def main(path): 
   file = open(path, 'r')
   outfile = open(path + '.out', 'w')
   stream = get_stream(file)
 
   cases = get_int(stream)
 
   for case in range(0, cases):
     solution = get_solution(stream)
     outfile.write( "Case #" + str(case+1) + ": " + solution + "\n" )

   outfile.close()

main("B-large-practice.in")

Finding a median value

While doing homework for the Week 2 ‘Quick Sort’ assignment, I found a very interesting code example. It finds an index of a median value of three array items: array[start],array[end-1], array[(end-1 – start)/2 + start].

def pivot_median2(array, start, end):
    m = (end-1 - start) / 2 + start
    l = start
    r = end-1

    max_index = max(l, m, r, key=lambda x: array[x])
    min_index = min(l, m, r, key=lambda x: array[x])

    median_index = l ^ m ^ r ^ min_index ^ max_index
    swap(array, start, median_index)

The beauty of this code lines in the way of using the XOR(^) operator to find the median index.

Principle of Computing: Statement of Accomplishment (with distinction)

Today, I have received a completion statement of the Coursera course ‘Principle of Computing’: [click here]

As the course was very refreshing, I think I will subscribe another companion class ‘Algorithmic Thinking’. 🙂

Finding Inversions in the Array

Problem Definition:

find the number of inversions in the list (or, array). That is, find all the index pairs (i, j) where i < j and  a[i] > a[j]. (Assuming the increasing order, the violation of that order is considered as an inversion).

Hint:

This is a simple tweak of Merge Sort. When two sorted arrays are merged into one, you can count the number of inversion – when an item of the second array is copied into the result array, the number of left items in the first array is the number of inversions.

Implementation (Answer):

import sys

def count_cross(ix, iy):
    '''
    do some merging
    '''
    ret = []
    count = 0
    for i in range(0, len(ix)+len(iy)):
        if len(iy) == 0:
            ret.append( ix.pop(0) )
        elif len(ix) == 0:
            ret.append( iy.pop(0) )
        elif ix[0] <= iy[0]:
            ret.append( ix.pop(0) )
        else:
            ret.append( iy.pop(0) )
            count += len(ix)
        return ret, count

def count_inversion(input):
    if len(input) == 1:
        return input, 0
    center = len(input) / 2
    sorted_x, cx = count_inversion( input[:center] )
    sorted_y, cy = count_inversion( input[center:] )
    sorted_z, cz = count_cross(sorted_x, sorted_y)

    return sorted_z, (cx + cy + cz)

def main():
    file = open(sys.argv[1], 'r')

    # make input array
    input = []
    for line in file:
        input.append( int(line.strip()) )

    result, num = count_inversion(input)
    print num

main()

Selecting the next Coursera Course

For the next Coursera course, I have considered several Algorithm classes. Among them, I have chosen this one: https://www.coursera.org/course/algo. Though the course is already finished, I have no option to find other courses because this course is well organized and I have many things to prepare for fitting in to my next job.

I want to train my brain as hard as possible before the new dawn is coming, but the time that I can spare is almost always limited.

So the basic strategy is…

1. Cover the one-week course only by ppt files.
2. If difficult to understand, use video lecture files.
3. Solve quiz and Programming Assignments.

And sometimes, exercise using Codejam problems and Stackoverflow questions.

If possible, I’d like to finish the Part I course in one month. Otherwise, I think I cannot try Part II.

Google Code Jam Round 1A 2008: Minimum Scalar Product

I think this question https://code.google.com/codejam/contest/32016/dashboard#s=p0 was just an warming up: solvable less than 10 minutes.

#!/usr/bin/python

import sys

def get_stream(file):
    for line in file:
        for token in line.strip().split():
            yield token

def get_number(stream):
    return int( stream.next() )

def get_string(stream):
    return stream.next()

def get_vector(stream, len):
    ret = []
    for _ in range(0, len):
        ret.append( get_number(stream) )
    return ret

def scalar_product(v1, v2):
    sum = 0
    for idx in range(0, len(v1)):
        sum += v1[idx] * v2[idx]
    return sum

#
# main
#

file = open(sys.argv[1], 'r')

stream = get_stream(file)

test_cases = get_number(stream)

for case in range(0, test_cases):
    vector_len = get_number(stream)
    # read two vectors
    vector1 = get_vector(stream, vector_len)
    vector2 = get_vector(stream, vector_len)
    # sort first vector in ascending order
    vector1.sort()
    # sort second vector in reverse order
    vector2.sort(reverse=True)
    # now, create a final scalar product.
    print "Case #"+str(case+1)+":", scalar_product(vector1, vector2)