Adrià Garriga's blog

Writing feels like outputting words until you approximate your thoughts.

Embarbussaments

Posted in Language

Attention! For those of you who do not understand Catalan, There is an English translation below!

La meva germana i jo vam començar a fer la primera d’aquestes frases. No em semblen especialment difícils de dir, però això potser és perquè els he escrit jo. Vaig gaudir del procés i el resultat, i per això vaig escriure les altres tres. Aquí van! Prova de dir-les!

  • La mangosta Agustina i la llagosta Gustau, vaguistes, gasten en gustos a l’Agost.

  • Manca de xancles, xanques blanques i tanques de branques fan que tanquin encara la banca.

  • La rara barana que el pare i la mare preparen fa cara la vara on para la Sara i s’encara al sarau i gatzara.

  • Fa poc que moc el soc del lloc al foc i toco un roc. Jo sóc un cóc de mocs que xoca al boc.

Estan creades de forma que tenen una seqüència concreta de sons repetida moltes vegades. Excepte la primera, també alternen síl·labes tòniques i àtones, per donar ritme. Noteu també la diferència entre “o”s obertes [IPA ɔ] i tancades [o] en l’última.

Traduir aquesta entrada m’ha fet adonar-me que, sí, les llengües romàniques i l’anglès tenen gairebé la mateixa gramàtica. Que fort.

In English

Title: Tongue Twisters

My sister and I started composing the first of these sentences. They don’t seem hard to say to me, but that may be because I wrote them. I enjoyed the process and results, so I wrote the other three. Here they go! Try to read them out loud!

  • La mangosta Agustina i la llagosta Gustau, vaguistes, gasten en gustos a l’Agost. (Augustine (female) the mongoose and Gustaf the lobster, strikers, spend on pleasures during August.)

  • Manca de xancles, xanques blanques i tanques de branques fan que tanquin encara la banca. (Lack of flipflops, white stilts and fences made of branches make the bank still be closing.)

  • La rara barana que el pare i la mare preparen fa cara la vara on para la Sara i s’encara al sarau i gatzara. (The rare railing that father and mother prepare makes expensive the rod where Sara stops and turns to face the party and rejoicing.)

  • Fa poc que moc el soc del lloc al foc i toco un roc. Jo sóc un cóc de mocs que xoca al boc. (For a short time, I have been moving the stump from the place to the fire and touching a rock. I am a snot pie that shocks the buck.)

They are created to have a certain sequence of sounds repeated many times. Except for the first one, they also alternate stressed and unstressed syllables, to give rhythm. Note also the difference between open [IPA ɔ] and closed [o] “o”s in the last one.

Translating this post made me realize that yes, latin-derived languages and English have almost the same grammar. Damn.

Comments

Frictionless OS X screenshot sharing with Nyazo

Posted in Tutorials

OS X has a nice screenshot feature. It’s fast and easy to use: just press Cmd-Shift-4 and select your shot, which will appear in the desktop. By pressing space, you can switch to window shot.

The problems come when you want to share your screenshot on, say, IRC. Direct transfer (DCC) is usually too much hassle for that, and some clients do not support it. What you usually do is upload the picture to the web, and link it.

You could just manually upload the file the screenshot feature produces. But I’m spoiled by the use of Nyazo on Linux, and I wanted better.

So in a few minutes you can tweak Nyazo’s Linux script and end up with this:

#!/bin/sh
screencapture $1 /tmp/nyazo.png
link=`curl -s http://nyazo.ru/upload.php -F "id=''" -F "imagedata=@/tmp/nyazo.png"`
rm /tmp/nyazo.png
open $link
echo $link | pbcopy

Save it as something like /usr/local/bin/nyazo and make it executable (chmod +x <file>). Then open Automator and create a new Service. Add the “Run Shell Script” action to it, write /usr/local/bin/nyazo -i to it, and save it.

Click the “Run” button at the top right of the window to test the service works as intended. A coordinates selecting cursor should appear. If you select a region, it should be uploaded to Nyazo.

Now open “Keyboard” in “System Preferences”. Go to the “Shortcuts” tab, and select “Services” on the left. At the end of everything, you can bind the interactive Nyazo Service you just created. I have it bound to Option-Cmd-Shift-4.

Of course, you can also bind the fullscreen screenshot Nyazo to keyboard. Just repeat the same steps, removing the “-i” option from the service, and binding to something else.

Happy shooting!

Comments

Contest writeup: Murcia qualifiers 2015

Posted in Problem Writeup

This is a writeup of the problems my team solved in the Murcia contest, which we were participating in as preparation for SWERC. Those people are way better than us, but we will not give up!

The problems are given the UVa numbers that will soon appear.

12962 Average Reuse Distance

At first read this problem seems easier than it really is. But it’s not a hard problem, it’s actually a fairly straightforward simulation.

The Problem

Given a sequence of memory accesses to different addresses (represented by the characters 'a' to 'z'), give its Average Reuse Distance. The Reuse Distance of a memory access to address $x$ is the number of other addresses accessed since the last access of $x$. First accesses to any given position do not count towards the average.

The solution

The core of this problem was keeping track of the different memory accesses since the last access of each address, and then counting them in an efficient way. We solved this by storing which addresses had been accessed as a bitmask. You can very easily reset the bitmask by setting it to 0, and count the number of ones in the bitmask with GCC and Clang’s __builtin_popcount.

The algorithm is the following:

  • Total sum = 0
  • For each character $c$ of input read:
  • If $c$ hasn’t been encountered before, mark it as encountered.
  • Otherwise, add the number of ones in the bitmask to the total sum and add 1 to the number to divide the sum by.
  • For all characters a-z, set their mask’s th bit to 1.
  • Reset $c$’s bitmask to 0

In the end, you output the mean from the sum you gathered, or NaN if the divider is 0.

Here is the code.

12963 Astragalus Nitidiflorus

We technically did not solve this problem within the contest, but came very close. The night after the contest, when sitting down to look at the problems again, we found what was wrong in 5 minutes.

The problem

You are given a grid with characters on it. You have to find the horizontal instances of the word “GARBANCILLOS” and the vertical instances of the word “ASTRAGALUS”. Whenever they intersect is a possible location, but each word instance can only be used once. Determine the number of locations.

The grid is at most 150x150.

The solution

You need to do two things here. First, find the strings’ locations and where they intersect. Then, compute the maximum matching of vertical and horizontal strings.

To find the strings’ location in $\Theta(n^2)$, we used a rolling hash. The longest of the strings is 12 characters, $12 \cdot 5 = 60 < 64$, so a hash with 5 bits per character can be used without collisions. We discard all the characters outside of the range from 'A' to 'Z', and give them the mask 0x1f.

First we look at the character matrix horizontally, and store the position of the found “GARBANCILLOS” in a sorted vector, one for each row. We also store its future index in the graph of intersecting strings in an std::map. Then we look at the character matrix vertically, and when we find a match we binary search for the possible horizontal matches in each row. If one is find, the edge is added to the maximum-matching matrix.

Finally, we output the maximum matching of the matrix we built.

Here is the code.

12965 Angry Bids

Nice pun.

The problem

You have some product’s producers, and some consumers. Each of them has an ideal price. The consumers will get angry if the price is higher than their ideal price. The producers will get angry if the price is lower than their ideal price. Find the price such that the number of angry people is minimal, and how many angry people there are.

The prices range from $0$ to $10^9$. There are up to $10^4$ producers and $10^4$ consumers.

The solution

It’s amazing how many problems are solved this way. If we check every possible price in order (unfeasible), we will have more consumers progressively getting angry, and more producers progressively getting happy.

Thus, we assign producers the number 1, and consumers the number -1. We create pairs of <price, assigned number> for each of them, and sort those pairs. We increase the price of the consumers in the pairs by 1 because that is when the consumer will start being unhappy. We sort this sequence and then iterate over it, keeping a sum of all the assigned numbers we have found. The point where this sum is maximum is the optimal point.

Here is the code

12967 Spay Graphs

However, the name of the problem in the contest is “Spray Graphs”. And the page’s title is “Spary graphs”. Haha.

The problem

You are given the graph structure in the picture. In this picture, each “level” of the graph has an assigned letter. We can build more levels by branching every node in right angles as shown in the figure.

Spray graph of size 4

Spray graph of size 4 Problem by Facultad de Informática, Universidad de Murcia

Given a number of levels, compute how many paths there are to get to any of the leaves. The levels range from 1 to 30.

The solution

Notice two things about this graph. First, it has four-way symmetry around the central node, so we can just compute the paths of a quarter of the graph and then multiply by 4, we can get the answer.

Radial symmetry in spray graphs

Radial symmetry in spray graphs

It is also very much like a grid, each node’s paths come only from the nodes to the left and up.

We can then build a grid with the number of paths for each node. The grid’s top row will be counting $1, 2, 3, …$ since the nodes in the top row of the separated portions in the previous picture have that number of paths. The first column will be all $1$s, since there is only one straight path down there. Then, we can compute each node’s number of paths as the paths coming from the left plus the paths coming from the top.

Here’s the grid for a size 5 graph:

1 2 3 4
1 $2+1=3$ $3+3=6$
1 $3+1=4$
1

Finally, just add up the leaves (the last diagonal), and multiply by 4. Bingo!

Comments

Simple way of proving this series converges?

Posted in Short

Doing my university homework, I came across the following.

Prove that $\sum_{i=0}^n r^i = 1 + r + r^2 + … + r^n$ is $O(1)$ if $0 < r < 1$.

With that range of $r$, $r^a > r^b$ iff $a < b$. Since $0 < 1 < … < n$, $1 > r > r^2 > … > r^n$. Thus, $\sum_{i=0}^n r^i = O(1)$

Equivalently, as $n$ approaches infinite, the series converges to a finite value.

Is this proof even correct? Stay tuned to find out!

Incorrect!

$\sum_{i=0}^n r^i = O(1)$ is not implied by $1 > r > … > r^n$. The correct proof is the following.

This is the geometric series, so its value (only for $r \neq 1$) is $\frac{1-r^{n+1}}{1 - r}$.

If $0 < r < 1$, $r^{n+1}$ approaches $0$ as $n$ tends to infinite, and for no value of $n$ such that $n \geq 0$ this is greater than $r$. Thus, the expression is something with a constant upper bound divided by a constant, which has a constant upper bound.

Since there exists a constant $c$ for which $c \geq \frac{1-r^{n+1}}{1 - r}$ for $n \geq 0$, $\sum_{i=0}^n r^i = O(1)$ . Thus it has been proven.

Comments

How to multiply polynomials in Θ(n log n) time

Posted in Algorithms

The information in this post is taken from the sources listed in the Sources section at the end of it. If you don’t care about understanding the algorithm and need an implementation now, skip to the Implementation subsection.

Why?

Why would anyone want to multiply polynomials in $\Theta (n \log n)$ instead of the naive $\Theta(n^2)$ time? Sometimes happens. I did when I got confronted with the UVa Online Judge 12879 Golf Bot problem. I knew I needed a discrete convolution, but then I got stuck because $200 000^2$ is way too high and the only way to calculate it I knew was quadratic.

If you mean “Why would you write this post?”, well, talking about an algorithm I recently learned to solve a problem is proving to be an easy way to kick-start my blog.

Gathering building blocks

So how do we do it? We are going to have to talk a bit about the representation of polynomials in computer memory first. (Haha get it?)

Coefficient representation

As far as I know, there are two useful ways of doing that. The first, and most obvious, is to store the coefficients of every term in an array, vector, list, you name it. Let $A(x)$ be a polynomial of degree-bound $n$:

$$A(x) = a_0 + a_1x + a_2x^2 + ... + a_{n-1}x^{n-1}$$

The “degree-bound $n$” is any $n$ strictly greater than the degree of the polynomial. We will always be talking about the smallest $n$ that fulfills this condition, that is, the degree plus one. The polynomial’s coefficients are $a_0, a_1, …, a_{n-1}$, and that’s what we store. For example, the polynomial:

$$3 + 2x^2 + 5x^3$$

Has the representation $3, 0, 2, 5$. Notice there is no “$x = x^1$” term, so the coefficient in position 1 is 0.

There is a straightforward way to evaluate the polynomial’s value for any $x_0$ in $\Theta(n)$. We can elevate $x_0$ to the required value for each coefficient, multiply for every coefficient and add all that up. I like Horner’s rule though:

$$A(x_0) = a_0 + x_0(a_1 + x_0(... + x_0(a_n)))$$

Multiplying two polynomials of degree-bound $n$ and $m$ takes $\Theta(nm)$ time. One has to multiply every coefficient of one with every coefficient of the other. The resulting polynomial will be of degree-bound $m + n - 1$. You’ve probably done this by hand countless times when trying to solve or simplify equations.

Point-value representation

To represent a polynomial $A(x)$ of degree-bound $n$, we store $n-1$ point-value pairs:

$$(x_0, A(x_0)), (x_1, A(x_1)), \; …, \; (x_n, A(x_n))$$

The algorithm to multiply polynomials in point-value representation is as follows. Let $A(x)$ and $B(x)$ be polynomials of degree-bound $n$ and $m$ respectively. They are both of degree-bound $n+m-1$ too. (Proof: $n+m-1 \geq n$ and $n+m-1 \geq m$ if $n, m \geq 1$, which is the case with degree-bounds). Represent $A(x)$ and $B(x)$ as vectors of $n+m-1$ point-value pairs, with the same points. Then multiply the values of each corresponding point-value pair.

Intuitively, because the value at each point of the result is the multiplication of the values at each point of the two polynomials we are multiplying, that is exactly what we do!

Let us do an example. We multiply:

$$A(x) = 3x^2 + x$$
$$B(x) = -5x^3 + 2x^2 - x + 4$$

Their minimum degree-bounds are, respectively, $3$ and $4$. Thus, we need $3+4-1=6$ point-value pairs for each:

$x_0$ $A(x_0)$ $B(x_0)$ $C(x_0) = A(x_0) \cdot B(x_0)$
0 $A(0) = 0$ $B(0) = 4$ $C(0) = 0$
1 $A(1) = 4$ $B(1) = 3$ $C(1) = 12$
2 $A(2) = 14$ $B(2) = -6$ $C(2) = -84$
3 $A(3) = 30$ $B(3) = -35$ $C(3) = -1050$
4 $A(4) = 52$ $B(4) = -96$ $C(4) = -4992$
5 $A(5) = 80$ $B(5) = -201$ $C(5) = -16080$

$C(x)$ on the right is the result of $A(x) \cdot B(x)$, and its point-value representation is $(0, 0), (1, 12), (2, -84), (3, -1050), (4, -4992), (5, -16080)$.

“That’s it!”, you may think. “Problem solved, and it’s $\Theta(n)$!“. Not so fast.

To convert from coefficient to point-value representation we need to evaluate $A(x)$ at $n$ points. The time needed to do that with what we know, Horner’s rule, is of course $\Theta(n^2)$.

Cutting time with FFT (Fast Fourier Transform)

FFT is a very important algorithm in signal analysis. It computes the DFT (Discrete Fourier Transform) of a signal in $\Theta(n \log n)$ time. The DFT maps the time domain to the frequency domain, that is; from a sequence of samples it extracts which frequencies are present and in which intensity. It is used, for example, to measure the pitch of an sound input, in applications such as Learn by Music Technology Group or one of those singing games.

But we are more interested in the mathematical definition of the DFT.

$$X_k = \sum_{n=0}^{N-1} x_n \cdot e^{-j2\pi k n / N}$$

Let’s break this definition down and rearrange it to understand why it is relevant to us. We also change the variables $A_k = X_k$, $a = x$, $i = n$, to reflect the correspondences with the naming conventions we used for polynomials.

$$A_k = \sum_{i=0}^{N-1} a_i \cdot \left( e^{-j2\pi k/N} \right)^i$$

For each $k$, the DFT is the sum of all the input coefficients $a_i$ multiplied by $\left(x_k\right)^i = \left( e^{-j2\pi k/N} \right)^i$. By doing this, we are effectively evaluating the polynomial expressed by the coefficients $a_i$ in all the points $x_k$.

We can calculate the coefficient representation from a point-value representation with points $\left(x_k\right)^i = \left( e^{-j2\pi k/N} \right)^i$ by using the inverse DFT. Turns out this is quite the simple reversal:

$$a_i = \frac{1}{N} \sum_{k=0}^{N-1} A_k \cdot \left( e^{j2\pi k/N} \right)^i$$

You can look up the proof elsewhere.

The Algorithm

The building blocks of our algorithm are complete.

Input: $A_v$ and $B_v$, coefficient representation of polynomials $A(x)$ and $B(x)$ respectively.

Output: $C_v$, coefficient representation of polynomial $C(x) = A(x) \cdot B(x)$.

  1. Let $\left| A_v \right|$ be the length of $A_v$, that is, the lowest degree-bound of $A(x)$. Let $\left| B_v \right|$ be the length of $B_v$. Let $\left| C_v \right| = \left| A_v \right| + \left| B_v \right| - 1$ be the lowest degree-bound of the result $C_v$.

  2. Let $n = \min_i 2^i$ subject to $2^i \geq \left| C_v \right|$. That is, the smallest power of two that is greater or equal than $\left| C_v \right|$. To compute it: iterate from $i=0$, increasing by $1$ every time, until $2^i \geq \left| C_v \right|$.

  3. Let $A_v$ be the vector representing $A(x)$ padded with zeroes so that its total length is $n$. Let $B_v$ be the vector representing $B(x)$ padded with zeroes so that its total length is $n$.

  4. Let $A_v’ = FFT(A_v)$ and $B_v’ = FFT(B_v)$.

  5. Let $C_v’ = A_v’ \cdot B_v’$, the dot product of $A_v’$ and $B_v’$. That is, multiplying every element of $A_v’$ with the element in the same position $B_v’$, and assigning that to the same position in $C_v’$.

  6. Let $C_v = FFT^{-1}(C_v’)$. $C_v$ is $C(x)$ in coefficient representation. Terminate.

Analysis

We show, as formally as I can, why this algorithm is $\Theta(n \log n)$. You may skip this section if it’s obvious to you, or try and figuring out yourself before reading it.

  1. is $\Theta(1)$ if we know the length of the inputs. It may be up to $O(n)$ if we have to measure them, for example by iterating until we find a sentinel at the end.

  2. is $\Theta(\log n)$. Proof: $n = 2^i$, $i = \log n$.

  3. is $\Theta(n)$. We have to add $\left( n - \left| A_v \right| \right) + \left( n - \left| B_v \right| \right)$, which a linear function of $n$.

  4. is $\Theta (n \log n)$, because the FFT is too.

  5. is $\Theta(n)$, because we iterate once for each elemnt of $C_v’$.

  6. is $\Theta (n \log n)$. The inverse FFT is like a regular FFT, with then dividing every element by $N$. Thus, it’s $\Theta(n \log n + n) = \Theta(n \log n)$

Thus, the whole algorithm is:

$$\Theta(n + \log n + n + n \log n + n + n \log n) = \Theta(n \log n)$$

Isn’t it easy to simplify expressions in asymptotic notation?

Implementation

If you are writing an application that needs an FFT of any form, I suggest using a library. Numerous smart people have spent their time making said library bug-free and performant, and you can greatly profit from their effort. I only know of one FFT library, the Fastest Fourier Transform in the West, but there are probably others that are just as fast, or bindings for this one to other languages.

However, if you must embed the routine in your program, for instance in a programming contest, you have to “implement it yourself”. The algorithm is not very complicated, but time spent debugging it is time wasted. I suggest copying Stanford University ACM Team’s Notebook. I endorse copying many things from there, actually. At the very least, their implementation is clear enough that you can base yours off of it.

Assuming we have included Stanford’s implementation earlier in the C++ file:

// Assume we have at most 2^18 = 262144 coefficients
const int MAX_LEN = 262144 * 2;

// For those of you who don't want to read the Stanford source:
// "cpx" represents a complex number.
// FFT(input, output, internal=1, size of input, direction)
// Direction is 1 for FFT, -1 for inverse FFT

cpx A[MAX_LEN], B[MAX_LEN], C[MAX_LEN];
int A_len, B_len, C_len;

/* set the appropriate coefficients in the inputs A and B's real-valued part,
 * and their length in A_len and B_len.
 */

// find the immediately greatest power of two
for(C_len = 1; !(C_len > A_len + B_len - 1); C_len *= 2);

// This is assumed in the 12879 Golf Bot problem
assert(C_len < MAX_LEN); 

// pad A and B with zeroes
memset(A + A_len, 0, (C_len - A_len) * sizeof(cpx));
memset(B + B_len, 0, (C_len - B_len) * sizeof(cpx));

// fill C with A's point-value
FFT(A, C, 1, C_len, 1);

// fill A with B's point-value
FFT(B, A, 1, C_len, 1);

// Multiply the polynomials in point-value
for(int i=0; i<C_len; i++)
    A[i] = A[i] * C[i];

// Convert back to coefficient representation
FFT(C, A, 1, C_len, -1);
for(int i=0; i<C_len; i++)
    C[i].a /= C_len;

// now C[i].a (the real-valued parts) contain the result

Solving 12879 Golf Bot

To solve 12879 Golf Bot, what we need to do is: have a vector that is 1 at the distances which the golf bot can shoot and 0 at the distances which it cannot. We need to add that vector to a vector of zeroes itself starting from every 1 it itself has. This is the operation called discrete convolution, and it’s the equivalent of multiplying two polynomials in coefficient form. So you do that, but you don’t need to divide by C_len at the end, because we only need to know if a given position is $>0$.

It’s a very quick explanation, but the problem isn’t the focus of this post :)

Final thoughts

Hope this post was enjoyable, easy to read, and useful.

Don’t use this in production over the simple naive quadratic algorithm if you do not handle big enough inputs. How big is big enough? Measure.

Sources

This pdf from Portland State University’s Algorithm Design and Analysis class. Contains more information about operations, properties and algorithms related to polynomials.

Wikipedia’s definition of the DFT and inverse DFT.

A Stack Exchange answer with an example of this algorithm. Helped me understand this a lot.

Comments