## Thursday, December 24, 2009

### Controlling the touchpad for EeePC in Debian

The oversensitive touchpad on the EeePC is a real nuisance. Whenever I'm typing, my thumb brushes it ever so slightly, and the pointer jumps all over the place. There are two solutions to this, but both involve setting the modifying that blasted xorg.conf file. Here's a snippet from mine:

Section "InputDevice"
Driver    "synaptics"
Option    "SendCoreEvents" "true"
Option    "SHMConfig" "on"
EndSection

Section "ServerLayout"
Identifier "Default Server Layout"
Screen "Default Screen"
InputDevice "Generic Keyboard" "CoreKeyboard"
EndSection


Make sure to set the SHMConfig option and to register the touchpad in the ServerLayout section.

Next trying typing synclient -l to see if you get a list of options; if you do, it worked. Otherwise you'll get an error about SHMConfig being disabled, meaning you did something wrong.

Now you have two choices.

Simply running syndaemon -d will disable the touchpad for 2 seconds after you start typing. Awesome! But since I hate the touchpad and normally have a bluetooth mouse attached, you can also...

Running synclient TouchpadOff=1 will do the trick. You can even write a little script to toggle it on and off for your convenience.

## Wednesday, December 16, 2009

### Getters and setters in Javascript 1.7

This is how you define getters and setters in Javascript 1.7 (Firefox 3.6):

let Foo = function () {
this._x = "hello";
};

Foo.prototype.__defineGetter__("x", function () {
return this._x;
});

Foo.prototype.__defineSetter__("x", function (x) {
this._x = x;
});


Holy crap! That's a mouthful! There is, as MDC says, another way to define getters and setters on object literals:

let foo = {
_x: "hello",
get x() {
return this._x;
},
set x(x) {
this._x = x;
}
};


It's much more concise than the previous way to define getters and setters, but there's one problem: it only works with object literals. This totally messes you up if you want to exploit Javascript's prototypical object system. For example, if you do this:

let Foo = function () {
this._x = "hello";
};

Foo.prototype = {
get x() {
return this._x;
},
set x(x) {
this._x = x;
}
};


...then you cannot defer property lookups to objects higher on the prototype chain of Foo instances in the natural way. Normally, you would do this if you wanted an instance of Bar in the prototype chain:

Foo.prototype = new Bar();


Bar could in turn contain, say, Baz, in its prototype chain (all the way up until null, as all prototype chains are terminated by null). However, there is no standard way to reference an object literal's prototype. Despite the fact that the ECMAScript spec does guarantee that every object contains a [[prototype]] property, it is hidden. You could try looking up the constructor of an object literal and changing it's prototype, but even if that worked, it would cause all object literals to have the same prototype (see below):

let foo = { a: 0, b: 1, c: 2 };
let bar = { x: 0, y: 1, z: 2 };
foo.constructor.prototype = bar;

foo.constructor.prototype === bar; // Evaluates to false
foo.x === undefined;               // Evaluates to true

// Even if foo.constructor.prototype === bar, this would be the case:
let bar = {};
bar.x === 0;                       // Would evaluate to true


However, if you don't mind that you are writing Javascript for Firefox anyways, you can set the hidden prototype property by setting the __proto__ property:

let Foo = function () {
this._x = "hello";
};

let Bar = function () {
this.y = "goodbye";
};

Foo.prototype = {
get x() { return this._x; },
set x(x) { this._x = x; }
};

Foo.prototype.__proto__ = new Bar();

let foo = new Foo();
foo.x === "hello";   // Evaluates to true
foo.y === "goodbye"; // Evaluates to true


Intuitively odd, and perhaps dangerous? Yes, but also much less visually abhorrent than __defineGetter__ or __defineSetter. For the meek, this will work as well:

let Foo = function () {
this._x = "hello";
};

let p = Foo.prototype;
p.get = p.__defineGetter__;
p.set = p.__defineSetter__;

p.get("x", function () {
return this._x;
});

p.set("x", function (x) {
this._x = x;
});


## Monday, August 24, 2009

### Serendipity 1.4.1 and blank post content fixed by voodoo!

After upgrading to Serendipity 1.4.1 (the software this blog used to run on), I noticed that sometimes a really lengthy post would get blanked out for no apparent reason. So, I rolled up my sleeves and futzed around with some PHP, and didn't come up with anything substantial. However, I noticed that when the nl2br plugin was enabled, my post would be blank. This prompted me to attempt some voodoo magic (read: trial and error).

I went to Administration -> Appearance -> Configure Plugins -> NL2BR, and looked for "A list of HTML-tags where no breaks shall be converted". This text field contained data like this:

ul,ol,li,p,code,textarea


I changed it to this:

pre,ul,ol,li,p,textarea


Now call me a witch doctor, because now my long posts don't get cut off.

## Friday, August 14, 2009

### Project Euler #188: The hyperexponentiation of a number

A friend of mine recently got me interested in problem 188 in Project Euler. I had given it a cursory glance before, but I didn't realize that I already possessed all the tools needed to solve it. In fact, all that's needed is some elementary number theory. I'll get started on a method to solve the problem, but I won't finish it, so the reader may enjoy the experience of solving the problem himself/herself.

To begin with this problem, the concept of order must be defined for two integers a and m where $$gcd(a, m) = 1$$.

$$ord_{m}a$$ is the least positive integer $$e$$ such that $$a^e \equiv 1 \pmod{m}$$.

But just because we have defined $$e$$ like so, it does not mean $$e$$ always exists. That must be proven.

# Proposition 1

If $$gcd(a, m) = 1$$, then $$ord_{m}a$$ always exists.

# Proof

Let $$a$$, $$k$$, $$m$$ be positive integers with $$gcd(a, m) = 1$$. Now let $$E_{m}=\{k\ |\ a^k \equiv 1 \pmod{m}\ \}$$. Since $$gcd(a, m) = 1$$, we have by Euler's theorem that $$a^{\phi(m)} \equiv 1\pmod{m}$$, where $$\phi(m)$$ is Euler's totient function. Since $$\phi(m) \in E_{m}$$, the set is non-empty, and therefore contains a least element by the well ordering principle. This least element is $$ord_{m}a$$.

# Proposition 2

$$a^k \equiv 1 \pmod{m}$$ if and only if $$e|k$$ where $$e = ord_{m}a$$.

# Proof

For the forward direction first suppose $$a^k \equiv 1 \pmod{m}$$. Then $$k=eq+r$$ with $$e > 0$$ and $$0 \le r < e$$ by Euclid's division lemma.

Therefore:

$$a^k \equiv a^{eq+r} \equiv a^{eq}a^r \equiv a^{r}a^{eq} \equiv a^{r}(1)^q \equiv a^r \equiv 1 \pmod{m}$$

Now, since $$e$$ is, by definition, the least positive integer such that $$a^e \equiv 1 \pmod{m}$$, if $$r < e$$ and $$a^r \equiv 1 \pmod{m}$$ as well, it must be the case that $$r = 0$$. Therefore, $$k = eq+r = eq+0 = eq$$, implying $$e|k$$. For the opposite direction, suppose that $$k=eq$$. Then: $$a^k \equiv a^{eq} \equiv (a^e)^q \equiv 1^q \equiv 1 \pmod{m}$$.

# Proposition 3

$$a^i \equiv a^j \pmod{m}$$ if and only if $$i \equiv j \pmod{e}$$, where $$e = ord_{m}a$$.

# Proof

Since $$gcd(a, m) = 1$$, $$gcd(a^k, m) = 1$$ as well. Therefore, $$a^k$$ must have a modular inverse; and in particular, so does $$a^j$$:

$$a^i \equiv a^j \pmod{m}$$
$$a^{i}a^{-j} \equiv a^{j}a^{-j} \pmod{m}$$
$$a^{i-j} \equiv a^0 \pmod{m}$$
$$a^{i-j} \equiv 1 \pmod{m}$$

Since $$a^{i-j} \equiv 1 \pmod{m}$$, it must be the case that $$e|i-j$$ by the proposition #2. Therefore $$i-j = eq$$, or $$i = eq + j$$. It follows that $$i \equiv j \pmod{e}$$.

For the other direction, assume that $$i \equiv j \pmod{e}$$, or that $$e|i-j$$. Then $$eq=i-j$$ and $$a^{eq} \equiv a^{i-j} \equiv 1 \pmod{m}$$. This implies that $$a^i \equiv a^j \pmod{m}$$.

Armed with this information it is much easier to solve #188.

# What is 3 ↑↑ 4 (mod 1000)?

This problem is asking for the last three digits of $$3 \uparrow\uparrow 4$$, and as expected, we don't need to explicitly calculate $$3 \uparrow\uparrow 4$$. Instead, we would rather find some $$j$$ such that $$3 \uparrow\uparrow 4 \equiv 3^j \pmod{1000}$$, where $$j$$ is some much smaller number. Luckily, the last proposition tells us that this $$j$$ satisfies $$j \equiv 3 \uparrow\uparrow 3 \pmod{ord_{1000}3}$$.

But now the problem remains to calculate $$3 \uparrow\uparrow 3 \pmod{ord_{1000}3}$$. But instead of calculating this directly, we would rather find some $$k$$ such that $$3 \uparrow\uparrow 3 \equiv 3^k \pmod{1000}$$, where $$k$$ is some much smaller number. Happily enough, we can apply the last proposition yet again, and discover that $$k$$ satisfies $$k \equiv 3 \uparrow\uparrow 2 \pmod{ord_{1000}3}$$.

But now $$3 \uparrow\uparrow 2 = 3^3$$, and this is rather easy to calculate (actual calculation left to the reader).

# Moving forward

The only thing that stands between the reader and solving problem 188 are the actual implementation. Some questions that remain to be asked include: "how does one calculate the $$ord_{m}a$$?", and "what is a good method for modular exponentiation?", etc. Although, the lazy reader may view this solution in Ruby.

## Sunday, August 2, 2009

### There exists no polynomial with integer coefficients that generates only primes

Thinking back to my post about Project Euler's problem #27, this result popped into my head again. It is somewhat relevant, but the topic escaped my mind before I finished writing the previous post.

Anyways, the proof is very very simple. Assume that, on the contrary, such a polynomial exists. Call it $$f(x)$$:

$$f(x) = a_{k}x^{k}+a_{k-1}x^{k-1}+ \ldots +a_{2}x^{2}+a_{1}x+a_0$$

By assumption, if $$b$$ is an integer, $$f(b)$$ is some prime $$p$$. Let $$t$$ be an integer; then $$b+tp$$ is also an integer, and $$f(b+tp)$$ should also be prime. We can rewrite $$f(b+tp)$$ as:

$$f(b+tp) = a_{k}(b+tp)^{k} + a_{k-1}(b+tp)^{k-1} + \ldots + a_2(b+tp)^2 + a_1(b+tp) + a_0$$
$$\hspace{4em} = a_kb^k + a_{k-1}b^{k-1} + \ldots + a_2b^2 + a_1b + a_0 + p \cdot g(t)$$

...where $$g(t)$$ is some polynomial in $$t$$. The above expression can further be simplified to:

$$f(b+tp) = f(b) + p \cdot g(t)$$
$$\hspace{4em} = p + p \cdot g(t)$$
$$\hspace{4em} = p \cdot (1 + g(t))$$

...giving the result that $$p$$ divides $$f(b+tp)$$. Given that $$f(b+tp)$$ is prime and $$p$$ divides it, we must have that $$p = f(b+tp)$$. Since $$t$$ is an arbitrary integer, it must be the case that $$f(x)$$ generates the prime $$p$$ infinitely many times.

This is a contradiction as $$f(x)$$ is a polynomial of degree $$k$$; it can take on the same value at most $$k$$ times.

## Wednesday, July 8, 2009

### Pop quiz, combinatorics

Continuing on a theme, here is an (easy) combinatorics questions:

n boys and n girls must be seated in 2n chairs. If every boy must only be seated next to a girl, how many possible seating arrangements are there?

Highlight text below for the answer.

First count the ways the boys and girls can be seated if the boys are in the odd numbered chairs and the girls are in the even number chairs. There are n odd numbered chairs, and n boys can be seated in them in $$n!$$ ways. Similarly, $$n$$ girls can be seated in the $$n$$ even numbered chairs in $$n!$$ ways. They can both be seated in $$n!^2$$ ways. Then count the ways where the boys are in even chairs and girls in odd chairs; again, there are $$n!^2$$ ways. So in total, there are $$2(n!^2)$$ ways.

### Probability!

It's time to get mathy! If you're just a programmer, these questions might seem a bit tricky for you (even if you are a math major, I hope I can get you with at least one of them). Most of them involve usage of Bayes Formula, although I will not use it, preferring a more combinatorial approach (since I'm a programmer).

# Hints

Here are a few hints for you to review:
• If event A can occur in a ways, and event B can occur in b ways, and both events are mutually exclusive, A or B can occur in a+b ways.
• If event A can occur in a ways, and event B can occur in b ways, and both events are independent, A and B can occur in a*b ways.

# Question 1

A couple has two children; the first one of them is a boy. What is the probability that the other is a boy?

The probability is 1/2.

There are four ways for a couple to have two children. With G representing a girl and B representing a boy, they are: BB, BG, GB, GG. They could have a boy first, and then a girl, or a girl first, and then a boy. Of course, there are only two scenarios where a boy is the first child: BB and BG. However, in only one of those scenarios is the other child also a boy. Hence the answer is 1/2.

# Question 2

A couple has two children; one of them is a boy. What is the probability that the other is a boy?

The probability is 1/3.

Proceeding as above, there are three ways for a couple two have two children, one of them being a boy: BB, BG, and GB. However, in only one of those scenarios is the other child also a boy. Hence the answer is 1/3.

# Question 3

(Monty Hall) On a game show, you may open one of three doors and keep what is behind it. Behind one door is one million dollars, and behind the other doors are goats. You select a door to open, and the game show host randomly opens one of the other doors, revealing a goat. What is the probability that the million dollars is behind the door you didn't select?

The probability is 1/2.

Did you think this was the standard Monty Hall question? Nope! I caught you if you weren't paying attention. Read on for a solution to this question:

It's easy to enumerate all of the possible scenarios. Suppose we have the following configuration in the game show:

• Door A has one million dollars behind it
• Door B has a goat behind it
• Door C has a goat behind it

There are only six possible ways the game show could turn out:

1. You pick door A (money), and the host randomly opens door B (goat)
2. You pick door A (money), and the host randomly opens door C (goat)
3. You pick door B (goat), and the host randomly opens door A (money)
4. You pick door B (goat), and the host randomly opens door C (goat)
5. You pick door C (goat), and the host randomly opens door A (money)
6. You pick door C (goat), and the host randomly opens door B (goat)

You are given that the game show host has randomly opened a door with a goat. This means there are four events: 1, 2, 4, or 6 that could have occurred. The question asks for the probability of the door you did not choose containing the money. In events 1 and 2, there is no possible way for the money to be in the door you did not choose. But there are 2 events (events 4 and 6) where the money is in the door you did not choose. So the probability is 2/4 = 1/2.

# Question 4

Q (Monty Hall): On a game show, you may open one of three doors and keep what is behind it. Behind one door is one million dollars, and behind the other doors are goats. You select a door to open, and the game show host opens one of the other doors known not to contain the prize, revealing a goat. What is the probability that the million dollars is behind the door you didn't select?

The probability is 2/3.

The probability that the door you chose has the money behind it is 1/3. The probability that the money was behind the door that the host opened is 0. Since the probability that the money is behind one of the three doors is 1, it follows that the probability of the money being behind the door you did not choose must be 1-1/3 = 2/3.

If this is your first time hearing this, you may not be convinced. Just imagine if I divided a deck of 52 playing cards up, giving you 1 card, and keeping the rest for myself. I now ask what the probability of my holding the ace of spades is, and you reply (correctly) that it is 51/52. I then proceed to reveal 50 cards to you that I have, none of which are the ace of spades, so that we are now both holding one card each. At this point, you should surely not assume that there is only a 50% chance of my holding the ace of spades!

# Question 5

7 people are passengers in a single elevator on a building with 9 floors. The elevator stops at all floors and each passenger eventually departs on some floor in the building, with no new passengers getting on. What is the probability that no passengers depart on the same floor?

Trick question! This problem has no solution.

I'm sorry if you spent some time trying to come up with a numerical answer to this question, as there are none. The key issue is that it is never mentioned whether or not each passenger is equally likely to depart on any given floor, or if any given floor is equally likely to have any number of departing passengers. See the next two questions to see what the difference is.

# Question 6

7 people are passengers in a single elevator on a building with 9 floors. The elevator stops at all floors and each passenger eventually departs on some floor in the building, with no new passengers getting on. If each passenger is equally likely to depart on any floor, what is the probability that no passengers depart on the same floor?

The probability is 560 / 59049:

$$9 \cdot 8 \cdot 7 \cdot 6 \cdot 5\cdot 4\cdot 2 / {9^7} = {560} / {59049}$$

If nobody is to leave on the same floor, then the 1st passenger has any of 9 floors to depart on, the 2nd passenger has any of 8 floors to depart on (he can't pick the floor of the first passenger), the 3rd passenger has any of 7 floors (he can't pick either of the floors chosen by passengers 1 or 2), and so on. Therefore, there are (9*8*7*6*5*4*2) ways the 7 passengers can depart. However, if there are no restrictions on how passengers depart, there must be (9*9*9*9*9*9*9) = 9^7 different ways for the passengers to depart.

# Question 7

7 people are passengers in a single elevator on a building with 9 floors. The elevator stops at all floors and each passenger eventually departs on some floor in the building, with no new passengers getting on. If each floor is equally likely to have any number of departing passengers, what is the probability that no passengers depart on the same floor?

The probability is 1 / 429.

In question 6, these two events are distinct:
A = "Passenger one departs on floor one, then passenger two departs on floor one"
B = "Passenger two departs on floor one, then passenger one departs on floor one"
However, in this scenario, we do not care about the order of departure; we only care about the number of passengers on any floor at the end of the process. We can model this problem in the following way:

Represent people with the number 0 and let 1 be a floor divider. Assuming there are only 3 people and 4 floors, this would be a possible way that nobody gets off on the same floor: 010101. As you can see, each passenger is on a different floor, and the last floor is unoccupied. Here's the other way 3 people can exit on 4 floors: 101010. The total number of ways passengers can depart is a multi-permutation: (3+3)!/(3!3!) = 5. Since there are only 2 ways that nobody can depart on the same floor, the probability for this smaller example is 2/5.

Extending to 7 people and 9 floors, we have a total of (7+8)!/(7!8!) = 1307674368000 ways for people to depart, and we can enumerate easily the number of ways that nobody departs on the same floors with our 1's and 0's:
101010101010101
011010101010101
010110101010101
010101101010101
...
010101010101011
110101010101010
101101010101010
101011010101010
...
101010101010110
Giving a total of 15 ways. Hence the probability is 15 / 6435 = 1 / 429.

## Monday, February 23, 2009

### Command line PHP with PEAR on a shared host

On a shared host, you must install PEAR locally, like so (for PEAR 1.4 and above):

pear config-create ~/.php ~/.pearrc


This will create a pear directory in ~/.php, but since you aren't the administrator, you can't just edit the php.ini file and add that to the include path. For php scripts executed by the web server, I don't see any way around it besides a set_include_path at the beginning of every script. For the CLI though, you can copy the php.ini to ~/.php and set the include path there. After creating a wrapper like so:

#!/bin/bash
/usr/bin/php -c ~/.php/php.ini \$@


...you can have PEAR modules included automatically.

### Using maven deploy:deploy-file with wagon-ftp (it's complicated!)

I recently tried to set up a Maven repository in an environment without a servlet engine (if I had one, I'd just use Nexus instead). If you want to upload an artifact that you are managing with Maven, that's one thing; however, if you are trying to use maven deploy:deploy-file with wagon-ftp, it is inexplicably difficult. Given that a Maven repository is simply a collection of directories and files with a standardized naming scheme, I can't fathom why it's so tricky.

Well anyways, I got it working, so I figured I may as well put it here. You must be using Maven 2.0.10, the version I tested this method on. If you use other versions, you'll get weird exceptions that are geared toward making you cry instead of cluing you in that you have a version mismatch.

1. The obvious first step is to set up an FTP server.


<settings>
<servers>
<server>
<id>your.server.com</id>
</server>
</servers>
</settings>

3. Search Google for the following jars on repo1.maven.org:
It must be these specific versions for Maven 2.0.10; wagon-ftp-1.0-beta-x.jar will not work, and you'll get some cryptic stack trace if you try it. Come Maven 2.1.x, you'll be able to use the beta versions of wagon-ftp.
4. Type the ridiculously long command found on this page. Here's an example:

mvn deploy:deploy-file \
-DrepositoryId=your.server.com \
-DgroupId=mygroup \
-DartifactId=myartifact \
-Dversion=1.0 \
-Dpackaging=jar \
-DgeneratePom=true \
-Durl=ftp://your.server.com \
-Dfile=somejar.jar


Make sure the repositoryId matches the id you have set in your settings.xml or you will get a NullPointerException (instead of some sort of authentication error, of course).
5. Pray to various gods.
6. Hopefully, it worked!

# Update

I recently had to deal with this scenario again. As it turns out, Maven 2.0.9 from the Debian repositories worked fine; I didn't have to grab any extra jars or whatnot, and I used scp instead of ftp in my settings.xml too:

<mirrors>
<mirror>
<id>maven.lousycoder.com</id>
<name>LousyCoder Maven Repository</name>
<url>scp://maven@lousycoder.com:/var/www/maven.lousycoder.com/</url>
<mirrorOf>maven.lousycoder.com</mirrorOf>
</mirror>
</mirrors>


On top of that, I also made a little deployment script to avoid having to type that really really long arse command.

## Saturday, February 14, 2009

### Getting StarCraft to work with Wine

Here's how to update StarCraft Anthology (or any version of StarCraft) via Battle.net. Open up wine configuration by typing winecfg, navigate to the Graphics tab, and uncheck "Allow the window manager to control the windows". If this is checked, StarCraft's version is reported incorrectly as 0.0.0.0, causing updates to fail.