Constructing a simple graph using Tikz

We start by creating a vertex s and then we add the new vertices using their relative position (east (EA), south (SO), north (NO), west (WE)). The relative positions can also be combined (NOEA for instance). Then, we draw the edges.

\usepackage{tkz-graph}

\begin{figure}[b]
   \centering
    \begin{tikzpicture}
	 \SetUpEdge[lw         = 1pt,
	            color      = black,
	            labelcolor = white]
	  \SetVertexNoLabel
	  \GraphInit[vstyle=Normal]
	  \SetGraphUnit{3}
	  \tikzset{VertexStyle/.append  style={fill}}
	  \Vertex{s}
	  \EA(s){a}  \NO(a){aa} \EA(aa){b} \SO(b){c}
	  \EA(c){d}
	  \Edge[label={$\{g_2\}$}, labelstyle={above}](s)(a)
	  \Edge[label={$\{g_1, g_2\}$}, labelstyle={left}](a)(aa)
	  \Edge[label={$\{g_1, g_2, g_3\}$}, labelstyle={above}](aa)(b)
	  \Edge[label={$\{g_2\}$}, labelstyle={sloped, above}](a)(b)
	  \Edge[label={$\{g_1,g_2,g_3\}$}, labelstyle={right}](b)(c)
	  \Edge[label={$\{g_3\}$}, labelstyle={above}](c)(d)
	\end{tikzpicture}
\caption{Integrated Graph after inserting  $g_3$ \label{fig:igraph_3}}
\end{figure}

Code jam: 1st problem

I found particularly nice the first problem of the CodeJam competition. You can find the description of the problem Safety in Numbers here. The solution is very elegant if you think about it and I wonder why the time limit was so high (8 minutes).

Starting from the worse player, we count how many votes he needs in order to cover his distance with the second player worst player. Now, all the votes are split between these two until they meet the third one and so on…

Before exposing my solution, here are some useful excerpts of code that I didn’t find somewhere else.

Assume a list which contains a permutation.

For instance a random permutation can be derived by

a = list(range(10))
shuffle(a)

Invert a permutation.

def invert_list(l):
    """ Assuming list l contains a permutation, return the inverse. """
    l2 = [True] * len(l)
    for i, j in enumerate(l):
        l2[j] = i

    return l2

Sort the list but instead of returning the sorted values, return the corresponding mapping of the keys.

def sorted_keys(s):
    """ Return a list with the indices sorted. """
    index_score = list(zip(list(range(len(s))), s))
    index_score.sort(key=lambda t: t[1])
    sorted_index, sorted_s = zip(*index_score)
    sorted_index = list(sorted_index)
    return invert_list(sorted_index)

The rest of my solution

def how_many_votes(s):
    votes = compute_needed_votes(s)
    total = sum(s)
    sorted_index = sorted_keys(s)
    percentage = []
    for i in range(len(s)):
        j = sorted_index[i]
        try:
            a = sum(votes[j:])
        except IndexError:
            a = 0
        percentage.append(100 *a/total)

    return percentage

def compute_needed_votes(s):
    remaining_points = sum(s)
    previous_p = 0
    difference = []

    sorted_s = sorted(s)
    for i, p in enumerate(sorted_s):
        # warning: i is 0 based
        if remaining_points <= 0:
            break
        if i == 0: # first player
            previous_p = p
            continue
        if i*(p - previous_p) > remaining_points:
            difference.append(remaining_points/i)
            remaining_points = 0
            break
        difference.append(p - previous_p)
        remaining_points -= i*(p - previous_p)
        previous_p = p

    if remaining_points > 0:
        difference.append(remaining_points/len(s))

    return difference

def main():
    testcases = int(input())
    for i in range(1, testcases + 1):
        a = [int(x) for x in input().split()]
        N, s = a[0], a[1:]
        print('Case #' + str(i) + ': ', end='')
        votes = how_many_votes(s)
        for v in votes:
            print(str(v), end=' ')
        print()

if __name__ == '__main__':
    main()

Subset sum

Subset sum as a decision problem in Python.

def bruteforce(x_list, target):
    for x in almost_powerset(x_list):
    	if sum(x) == target:
    		return True
    return False

def almost_powerset(iterable):
    '''powerset([1,2,3]) --> (1,2) (1,3) (2,3) (1,2,3)

       http://docs.python.org/library/itertools.html#recipes
    '''
    s = list(iterable)
    return itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(2, len(s) + 1))

.hgignore for LaTeX projects

# use glob syntax.
syntax: glob
*.aux
*.glo
*.idx
*.log
*.toc
*.ist
*.acn
*.acr
*.alg
*.bbl
*.blg
*.dvi
*.glg
*.gls
*.ilg
*.ind
*.lof
*.lot
*.maf
*.mtc
*.mtc1
*.out
*.synctex.gz
*.thm
*.nav
*.snm

What .hgignore is. It is easy to modify it to obtain the corresponding gitignore file. Just remove the first two lines.

Caching functions in Python

def cached(func):
    @wraps(func)
    def cached_func(*args):
        if args in cache:
            return cache[args]
        cache[args] = func(*args)
        return cache[args]
    return cached_func

Excerpt from gepa for the fourth problem of Google Code Jam.

Google Code Jam — Solutions to two practice problems in Python

Since Code Jam contest starts in one day, I thought of solving some problems for practice.

Minimum Scalar Product

The solution is based on the fact that the maximum area of a rectangle is when it is square and generalizing to R. It can be proved by taking the derivative of f(x) = (x – a)(x – b). f’(x) = 0 x = (a + b)/2. Therefore, if we have two numbers with a constant sum, their product is maximized when they are as close as possible. My failure to explain it simply should not make it look hard. Intuitively, if we select the number, say 8, 4 * 4 is bigger than 5 * 3 or 6 * 2 or 7 * 1 and so on…

EDIT: Simpler explanation: We want to maximize . We know that and (the measure of the vectors) are the same no matter how we rearrange the coordinates.

testcases = int(input())
for t in range(1, testcases + 1):
    n1 = int(input())
    num1 = [int(n) for n in input().split()]
    num2 = [int(n) for n in input().split()]
    num1.sort()
    num2.sort(reverse=True)
    res = 0
    for i in range(n1):
        res += num1[i] * num2[i]
    print('Case #' + str(t) + ': ', end='')
    print(res)

As we see in this solution, I sort twice. Since addition is commutative, it should be enough to sort only one of the lists but I could not find a smart way of doing so.

Rope Intranet

This problem attends a solution using dynamic programming. We sort according to the numbers on the first building. Then, we start from the lowest window in this building. We check how many ropes from lower windows go higher than the rope from the current window in respect to the other building. And the answer is the sum of the number of ropes that go higher for every window. My solution emulates the way insertion sort works. Probably, there is a better solution.

from bisect import bisect

testcases = int(input())
for t in range(1, testcases + 1):
    n1 = int(input())
    
    wires = []
    for k in range(n1):
        w1 = input().split()
        w1 = (int(w1[0]), int(w1[1]))
        wires.append(w1)
    
    wires.sort(key=lambda wir: wir[0])
    other_building = []
    crossings = 0
    for a, b in wires:
        i = bisect(other_building, b)
        crossings += len(other_building) - i
        other_building.insert(i, b)
    
    print('Case #' + str(t) + ': ', end='')
    print(crossings)

Ideology to consume

Our environment creates ideological predispositions. In a society which demands order, the rule is above people. A society which lives for pleasure can forgive almost anything which undermines its future. We have several recent examples on how people adjust themselves to their social environment. Morals are subjects to circumstances. Examples are laid out throughout our history. If we limit ourselves to politics, that is what happens now in Greece and happened a few years ago with the war against terrorism in US. Sometimes, this adjustment is necessary (see the ongoing war for the copyright laws or academic publishing). Sometimes, this is just another mean to justify our options as consumers.

In Matrix, Neo had to choose between the red pill and the blue one only once. He chose the red one and he was shown the truth. I guess the movie would be boring if he had to choose almost everyday until he gave in. What we believe can now come in a convenient form. We have the freedom to choose our misunderstanding.

Technology changes the status quo. The power yielded by countries is compared to the power yielded by companies. There are no rigorous borders on these entities. People rule them both. Democracy, in its current form, is becoming obsolete just like flame wars between Windows and Linux. Who cares if they don’t apply anymore? People abstract their dependencies from their direct environment. USA is a net exporter of gas, even though it has to import the oil. Agriculture is slowly moving away from the fields. Territory is of less importance due to the huge advances in transportation means. Direct environment and influences are from all over the world. We live at the beginning of an educational experiment. Our pop culture is globalised. You don’t believe me still? What would you say about a country which, despite being in the middle of a very harsh economical recession, is still the largest buyer of weapons in Europe? Yes, that is Greece.

We are not much more clever in average than people in 18th or 19th century. But we are more informed. Our destructive power can not be guided using our ignorance, but our selective knowledge. We can celebrate ourselves as free people. Free people who (maybe unconsciously) choose their intellectual barriers and stick to them. It is pointless, nowadays, to fight the World War III. Why kill people who could be consumers? It is bad for business.

A few generations back, our world was divided between capitalism and socialism. Their main proponents were countries. Now, the chessboard has changed dramatically. We should check who are the richest people in the world. We don’t vote only once per few years, but almost daily, with our consumer choices. Where we put our money determines and some policies, or sometimes, even how we live. Check the current stereotypes around the overpriced iPhones and the cheap Android phones. Companies are trying to buy our personal data and lure us with their best baits.

Internet just passed its adolescence. Is it going to vote? Of course! Check the pirate parties and how they try to bridge this gap. But even before voting, it has elected some of the most powerful and richest people, it makes obsolete newspapers, it transforms education and research and revolutionize many other aspects of our life. Is this bad? Of course not. We are bad. We are bad at anticipating these changes. Our current laws concerning the web are a projection of a system which addresses a completely different domain.

Our problem is that we can not apply anymore the results of thoughts of previous generations of thinkers. We have to reverse engineer their thoughts, modernize them or even reject them. The challenges of our world can not be met by traditional means. What was the opinion of Socrates about the Internet? Was Plato against copyright? As a society, how do we organize ourselves? Many years ago, we decided it does not make huge difference if someone resides in a nearby city if you more or less speak the same language and have the same religion. Now, English are almost the de facto lingua franca. As for religion, it does not polarize people in the same degree. Terrorist attack is more convincing than the freedom of the holy places.

If we still care about happiness, the core of our principles does not have to change. Nevertheless, it is high time we changed how we interpret these principles. Otherwise, besides the fast food, we will be buying our ideologies. And then, sell them again for the new shiny potatoes.

Sometimes, it is better to not give a definite answer, since that steals the question. So, the question remains. In a fast changing world, what defines you? I think I have my answer, but it is subject to changes. Do you?