Fork me on BitBucket
Filter:
2013-01-30

Facebook Hacker Cup 2013

Hacker Cup kicked off this weekend with a 72 hour qualification round. The grand prize is 10K and cash prizes go down to 25th place! (+ flights for the top 25 to FBHQ). With over 10,000 competitors there were many interesting solutions and pitfalls people ran into. The qualification round ran smoothly although people (including myself) are "disgruntled" with how long it takes facebook to confirm results. (People expect instant gratification these days :P )

The least solved problem was Find The Min. A lot of people couldn't get the solution within the 6 minute time limit because they tried using a O(n) solution or an O(k^2) solution. Below is my O(K) solution that many will be interested to see. It uses c[num] to keep track of which numbers have been used recently and are unavailable. Any number that is "freed" is appended as the next min if it is smaller than the previously found min, otherwise the next smallest available number is found and appended. We only need to find the first few minimums because they start repeating after a while.

__author__ = 'robert'

from itertools import count
from collections import Counter

data = open("in3b.txt")
cases = int(next(data))

for case in range(1, cases + 1):
    n, k = map(int, next(data).split())
    a, b, c, r = map(int, next(data).split())
    known = [a]
    for i in range(k - 1):
        known.append((b * known[-1] + c) % r)
    c = Counter(known)
    finder = (i for i in count(0) if not c[i])
    found = next(finder)
    known.append(found)
    c[found] += 1
    for j in range(k + 1):
        freed = known[j]
        c[freed] -= 1
        if c[freed] == 0 and freed < found:
            known.append(freed)
            c[freed] += 1
        else:
            found = next(finder)
            c[found] += 1
            known.append(found)
    remainder = n % (k + 1)
    if n < len(known):
        ans = known[n - 1]
    else:
        ans = known[(k + 1) + remainder - 1]
    print "Case #{0}: {1}".format(case, ans)



page divider
2011-11-05

linear programming

Another Project Euler problem:

Given a matrix (15 by 15 grid of numbers), what is the maximum sum of numbers achievable with the restriction that.. You may only pick one number from each row. Also none of the numbers picked are allowed to be in the same column!

After looking at the problem I decided I could use either integer programming or dynamic programming (or perhaps even backtracking with pruning).

I'd been told how easy it is to use pythons PULP linear programming library so thought i'd give it a shot and it did turn out to be remarkably simple to use, here is the solution in fact:

__author__ = 'Robert'
import pulp

def get_lp_problem(matrix):
    prob = pulp.LpProblem("pe345", pulp.LpMaximize)
    cols = [[] for i in range(15)]
    rows = [[] for j in range(15)]
    objective = []
    for i in range(15):
        for j in range(15):
            var = pulp.LpVariable('{i}_{j}'.format(i=i, j=j),
                lowBound=0, upBound=1,
                cat=pulp.LpInteger)
            cols[i].append(var)
            rows[j].append(var)
            profit = matrix[i][j]
            objective.append(profit * var)
    for col in cols:
        prob += sum(col) <= 1 #1 value per col
    for row in rows:
        prob += sum(row) <= 1 #1 value per row
    prob += sum(objective) #objective function
    return prob

def solve():
    matrix = \
"""7  53 183 439 863 497 383 563  79 973 287  63 343 169 583
627 343 773 959 943 767 473 103 699 303 957 703 583 639 913
447 283 463  29  23 487 463 993 119 883 327 493 423 159 743
217 623   3 399 853 407 103 983  89 463 290 516 212 462 350
960 376 682 962 300 780 486 502 912 800 250 346 172 812 350
870 456 192 162 593 473 915  45 989 873 823 965 425 329 803
973 965 905 919 133 673 665 235 509 613 673 815 165 992 326
322 148 972 962 286 255 941 541 265 323 925 281 601  95 973
445 721  11 525 473  65 511 164 138 672  18 428 154 448 848
414 456 310 312 798 104 566 520 302 248 694 976 430 392 198
184 829 373 181 631 101 969 613 840 740 778 458 284 760 390
821 461 843 513  17 901 711 993 293 157 274  94 192 156 574
34 124   4 878 450 476 712 914 838 669 875 299 823 329 699
815 559 813 459 522 788 168 586 966 232 308 833 251 631 107
813 883 451 509 615  77 281 613 459 205 380 274 302  35 805"""\
    .splitlines()
    matrix = [map(int, line.split()) for line in matrix]
    lp_prob = get_lp_problem(matrix)
    lp_prob.solve()
    print lp_prob.solutionTime #0.04 seconds
    ans = 0
    for var in lp_prob.variables():
        if var.varValue > 0:
            i, j = map(int, var.name.split('_'))
            ans += matrix[i][j]
            #I don't know how to evaluate lp_prob.objective,
            # so add them manually
    return ans

print solve()

Integer Programming always seems the lazy option for solving many problems. For more Details on Linear Programming or PULP I suggest you check out this awesome example

In fact I just solved another PE problem using almost exactly the same code as above: With Problem 185 one must try to guess a number. Each guess we are told how many digits of our guess are in the correct place e.g. for
90342 ;2 correct
70794 ;0 correct
39458 ;2 correct
34109 ;1 correct
51545 ;2 correct
12531 ;1 correct
we have an answer of 39542

Here is my code that solves the larger system:

__author__ = 'Robert'
import pulp

def get_lp_problem(constraints):
    prob = pulp.LpProblem("pe345", pulp.LpMaximize)
    objective = []
    vars = {}
    for j in range(len(constraints[0][0])):
        position_restriction = []
        for i in range(10):
            var = pulp.LpVariable('{i}_{j}'.format(i=i, j=j),
                lowBound=0, upBound=1,
                cat=pulp.LpInteger)
            vars[(i, j)] = var
            #var controls if digit i occurs at position j
            objective.append(var)
            position_restriction.append(var)
        #1 digit in position j:
        prob += sum(position_restriction) <= 1

    for guess, num_correct in constraints:
        guess_constraint = []
        for j, i in enumerate(guess):
            i = int(i)
            var = vars[(i, j)]
            guess_constraint.append(var)
        prob += sum(guess_constraint) == num_correct
    prob += sum(objective) #objective function
    return prob

def solve():
    data =\
    """5616185650518293 ;2 correct
3847439647293047 ;1 correct
5855462940810587 ;3 correct
9742855507068353 ;3 correct
4296849643607543 ;3 correct
3174248439465858 ;1 correct
4513559094146117 ;2 correct
7890971548908067 ;3 correct
8157356344118483 ;1 correct
2615250744386899 ;2 correct
8690095851526254 ;3 correct
6375711915077050 ;1 correct
6913859173121360 ;1 correct
6442889055042768 ;2 correct
2321386104303845 ;0 correct
2326509471271448 ;2 correct
5251583379644322 ;2 correct
1748270476758276 ;3 correct
4895722652190306 ;1 correct
3041631117224635 ;3 correct
1841236454324589 ;3 correct
2659862637316867 ;2 correct"""
    data = data.replace(" correct", "")
    data = data.replace(";", "")
    constraints = []
    for line in data.splitlines():
        guess, num_correct = line.split()
        num_correct = int(num_correct)
        constraints.append((guess, num_correct))
    lp_prob = get_lp_problem(constraints)
    lp_prob.solve()
    print lp_prob.solutionTime #0.2 seconds
    solution = ['?'] * len(constraints[0][0])
    for var in lp_prob.variables():
        if var.varValue > 0:
            i, j = map(int, var.name.split("_"))
            solution[j] = str(i)
    return "".join(solution)

print solve()

As you can see, Once again the PULP library proved very simple to use, The code took less than ten minutes to write.




page divider
2011-11-03

grid tours

Problem:

Here is a 4x10 board with a "tour" which visits every square exactly once.

The question is: How many "tours" (paths that visit every single square exactly once) are there in a 4x10^12 grid under the condition the tour must start in the top left square and finish in the bottom left square. (Credit to the guys at projecteuler.net for thinking up another great problem)

If we let T(n) be the formula for the number of tours in a 4xn grid, we need to find T(10^12). One approach is to find a recurrence relation. A trick is to realize there are only two possible ending columns. Try follow my working if you can, sorry It's messy :)

Final code:



page divider
2011-04-30

Syntax highlighting and self replicating machines

So the other day I went to the Auckland Makers-Space. There they had a 3d printer printing out replacement parts for itself. The guy told me that in fact all the parts of his 3d printer had been created by his friends 3d printer. Talk about exponential growth of 3d printers. (Check out ponoko to access one)

Anyway I decided to write a how-to article on how I style my python code snippets. firstly easy_install Pygments, then:

from pygments import highlight
from pygments.lexers import PythonLexer
from pygments.formatters import HtmlFormatter

code = open(__file__).read()
print highlight(code, PythonLexer(), HtmlFormatter())
#print HtmlFormatter().get_style_defs('.highlight')

The above code snippet, through the use of __file__, prints the following html source which in turn produces the above code snippet:

<div class="highlight"><pre><span class="kn">from</span> <span class="nn">pygments</span> <span class="kn">import</span> <span class="n">highlight</span> <span class="kn">from</span> <span class="nn">pygments.lexers</span> <span class="kn">import</span> <span class="n">PythonLexer</span> <span class="kn">from</span> <span class="nn">pygments.formatters</span> <span class="kn">import</span> <span class="n">HtmlFormatter</span> <span class="n">code</span> <span class="o">=</span> <span class="nb">open</span><span class="p">(</span><span class="n">__file__</span><span class="p">)</span><span class="o">.</span><span class="n">read</span><span class="p">()</span> <span class="k">print</span> <span class="n">highlight</span><span class="p">(</span><span class="n">code</span><span class="p">,</span> <span class="n">PythonLexer</span><span class="p">(),</span> <span class="n">HtmlFormatter</span><span class="p">())</span> <span class="c">#print HtmlFormatter().get_style_defs(&#39;.highlight&#39;)</span> </pre></div>

of course relevant css is required which you can see in my blogs css file.

On another level, pypy does something similar with its translator (and i'm not talking about lexing).. Watch the few minutes leading up to 29min,50 seconds




page divider
2011-04-29

From Ray Tracer to Gif Animation

So one of my first python projects when I was younger was to create a raytracer. My raytracer creates a .png image pixel by pixel. To decide what colour to colour a pixel, It sends rays out (in my mathematical model, think of it as a x,y,z grid with equations for a torus, sphere etc). Using basic vector calculus and linear algebra, we bounce the ray around in the grid until it hits the light source (if it doesn't hit the light source after a few reflections we make the pixel a shadow point). Each reflection the ray gains some colour from the object it hits.



To make an animation I generated several .png images (moving the light source a few cm each time). These images were then put into a gif animation with the following code:

__author__ = 'Robert'
from images2gif import writeGif
from PIL import Image
import os

file_names = sorted(
    (fn for fn in os.listdir('.') if fn.endswith('.png'))
    )
#['animation_a.png', 'animation_b.png', ...] "

images = [Image.open(fn) for fn in file_names]

size = (150,150)
for im in images:
    im.thumbnail(size, Image.ANTIALIAS)

print writeGif.__doc__
# writeGif(filename, images, duration=0.1, loops=0, dither=1)
#    Write an animated gif from the specified images.
#    images should be a list of numpy arrays of PIL images.
#    ...
#    ...

filename = "my_gif.GIF"
writeGif(filename, images, duration=0.2)
#54 frames written
#
#Process finished with exit code 0

Output, a 150x150 8bit GIF:



unfortunately to keep the file size down I had to reduce the quality.




page divider

Random Quote