Older blog entries for bi (starting at number 70)

I slapped together a silly text game. It probably can't be counted as open source, but the code that was used to garble the JavaScript can be.

UNLEASHING THE ENABLING COMPETITIVE SYNERGY OF THE AJAX EVENTWEB!!!!!!!!!111

In other words, I just whipped up Yet Another VT100 Emulator for JavaScript (now showing Rybolt's "Shamus the Fish"). Pretty useless as it stands... but it's buzzword-compliant!

1 Jun 2007 (updated 1 Jun 2007 at 19:38 UTC) »
Data per manum nostram in prato

fzort:

Run GNU/Linux? Be a real man and write your own OS. :)

(OK, I read that the Cassiopeia E-11 has 8Mb of memory... probably already more than enough to run Linux. Running GNU/Linux is another matter though.)

Res ipsa loquitur sed quid in infernos dicit

wlach totally boggles my mind. So is he saying that the oil companies are raising prices because they, out of the goodness of their hearts, suddenly decide they want to make people moderate their oil consumption in order to save the earth's climate?

3 Apr 2007 (updated 4 Apr 2007 at 18:20 UTC) »
Oh great, now everyone's a geek

berend is normally a raving wingnut, but he's right on the money when he says,

The drive-by media previously reported that one of the definitions of a geek was someone who couldn't get a girlfriend. Now a geek is someone with a stripper as girlfriend:

Preliminary results from the research show so-called computer geeks are becoming the new schoolyard bullies.

In related news, Jacqueline Passey says she's a geek because she watches cheesy TV shows. Geek geek geek!

Edit:

  • Woohoo, I'm Journeyer again!
  • Is stanx a spammer, lurker, or free software spelunker? You decide.
Shoot first, don't ask later. That is the Way of the Wikipedia.

kelly: What? What? It reads below the Citizendium page:

Photo by Magnus Manske. From [1] on Wikimedia Commons. Licensed under GFDL 1.2 or later, or CC-by 1.0.
10 Mar 2007 (updated 10 Mar 2007 at 15:06 UTC) »
Image Hosted by ImageShack.us

Call for Spoof Papers!

I figured this is as good a place as any other to repeat my call to submit spoof papers on global warming to the AEI. If you're a global warming researcher, or you know someone who is, or you know someone who knows someone who is, etc. etc., then do help spread the message!

6 Mar 2007 (updated 4 Apr 2007 at 18:37 UTC) »
Dang it, Ward Cunningham, look what you started...

 fzort: man, that's pure evil.

So, IOCCC 2006 and Bitwise 2007 are both over. This leaves the ICFP Contest.

In other news, I see that the Tubes of the Internet are now filled with the latest antics of the wikiclowns:

  • To counter the evil left-wing bias of Wikipedia, Andrew Schlafly founded Conservapedia, an encyclopedia which looks like a bunch of articles written by screaming teenagers (perhaps because... that's what it is?).

  • Meanwhile, at Wikipedia, there's the "Essjay" scandal. To be honest, I think Jimmy Wales' behaviour just screams "C-Y-A" in big bold letters.

I hope both projects will soon collapse under the sheer weight of their own stupidity, and we can have something better.

16 Feb 2007 (updated 17 Feb 2007 at 06:51 UTC) »
Lumos Kelmin pesso desmar lon emposo

I see the solutions for Bitwise 2007 are up. Well, fzort and myself took part, and we got into the top 50... but I still wanted to know how well my solutions compare against the `official' solutions. So... (long-winded stuff ahead)

And, an old blog post on googlejuice:

One of the great ironies of my recent mistake here was that it actually increased this blog's Googlejuice. Between those who linked to complain, my responses in apology, and those who followed up on my explanation saying they hadn't seen my apology, the incoming link traffic here actually rose 50%. If some of those people stick around (maybe wondering when I'll fall on my face next) it's actually a good thing.

Update: I was Journeyer before, but after OpenSpecies gave me an additional certification, I'm now Observer. Weird.

1 Feb 2007 (updated 17 Feb 2007 at 06:50 UTC) »
Golbasto Momarem Evlame Gurdilo Shefin Mully Ully Gue

Update:

Update #2: I see the solutions for Bitwise 2007 are up. Well, fzort and myself took part, and we got into the top 50... but I still wanted to know how well my solutions compare against the `official' solutions. So...

Problem 1

My approach:
Remove the outer layer of leaves, and repeat until the number of nodes ≤ 2; then the remaining node(s) will be the answer.

This will be O(n) except that in one place (marked /* ugh */) I do a linear search in the adjacency list for a node.

My code:

#include <stdio.h>

int main()
{
        unsigned test_cases, n, e, i, j, k, frog, lvi;
        static unsigned deg[1000], adjl[1000][1000], lv[2][1000], nlv[2];
        scanf("%u", &test_cases);
        while (test_cases--) {
                scanf("%u", &n);
                e = n - 1;
                for (i = 0; i < n; ++i)
                        deg[i] = 0;
                while (e--) {
                        scanf("%u %u", &i, &j);
                        adjl[i][deg[i]++] = j;
                        adjl[j][deg[j]++] = i;
                }
                nlv[0] = 0;
                for (i = 0; i < n; ++i)
                        if (deg[i] < 2)
                                lv[0][nlv[0]++] = i;
                frog = 0;
                while (n > 2) {
                        nlv[!frog] = 0;
                        for (lvi = 0; lvi < nlv[frog]; ++lvi) {
                                --n;
                                i = lv[frog][lvi];
                                if (deg[i] == 0)
                                        continue;
                                j = adjl[i][0];
                                /* ugh */
                                for (k = 0; adjl[j][k] != i; ++k);
                                adjl[j][k] = adjl[j][--deg[j]];
                                if (deg[j] == 1)
                                        lv[!frog][nlv[!frog]++] = j;
                        }
                        frog = !frog;
                }
                for (lvi = 0; lvi < nlv[frog]; ++lvi)
                        printf("%u ", lv[frog][lvi]);
                putchar('\n');
        }
        return 0;
}

Official solution:

Step 1: Identify any leaf of the tree.
Step 2: Find one of the farthest leaves from that leaf (and name it L1).
Step 3: Find one of the farthest leaves from L1, and name it L2.
Step 4: The middle point(s) of the path L1-L2 is the ‘center’ of the graph and the ideal location for Spiderman to buy a house for Mary-Jane.

Conclusion: my code seems to work, but I think the official solution makes more sense.

Problem 2

My approach:
For each denomination a[i], maintain 2 arrays, one for when a[i] is used, one for when a[i] is not used. Once each a[i] is processed, throw it away. In other words, successively find the number of coins needed to achieve a sum of 0, 1, 2, ..., S, using only { a[1] }, { a[1], a[2] }, { a[1], a[2], a[3] }, ...

(The "frog" thing in the code is totally unneeded, but I can't be bothered to clean it up.)

My code:

#include <limits.h>
#include <stdio.h>

int main()
{
        unsigned test_cases, s, d, a, b, t, c1, c2, frog;
        static unsigned coins[2][10001];
        scanf("%u", &test_cases);
        while (test_cases--) {
                scanf("%u %u", &s, &d);
                frog = 0;
                coins[frog][0] = 0;
                for (t = 1; t <= s; ++t)
                        coins[frog][t] = UINT_MAX;
                while (d--) {
                        scanf("%u %u", &a, &b);
                        if (b == 0)
                                b = 1;
                        for (t = 0; t < a * b && t <= s; ++t)
                                coins[!frog][t] = UINT_MAX;
                        for (; t <= s; ++t) {
                                if (coins[frog][t - a * b] == UINT_MAX)
                                        c1 = UINT_MAX;
                                else
                                        c1 = coins[frog][t - a * b] + b;
                                if (coins[!frog][t - a] == UINT_MAX)
                                        c2 = UINT_MAX;
                                else
                                        c2 = coins[!frog][t - a] + 1;
                                coins[!frog][t] = c1 < c2 ? c1 : c2;
                        }
                        for (t = 0; t <= s; ++t)
                                if (coins[frog][t] < coins[!frog][t])
                                        coins[!frog][t] = coins[frog][t];
                        frog = !frog;
                }
                if (coins[frog][s] == UINT_MAX)
                        printf("-1\n");
                else
                        printf("%u\n", coins[frog][s]);
        }
        return 0;
}

Official solution:

n(S) = min(∀i, V[i])
where, V[i] = min { n(S - a[i] * (b[i] + j)) + (b[i] + j) }, ∀j, j ∈ [0, b[i])

Initialization Step:
n(x) = 0, if x = 0
n(x) = ∞, if x != 0

Conclusion: I don't know what the official solution is saying. :|

Problem 5

My approach:
Consider powers g, g^2, g^3, ..., of a generator g of the multiplicative group A = { 1, 2, ..., p - 1 }. For each possible order d | p - 1 of a group element, there are φ(d) elements with this order -- all the g^i(p/d) where i is coprime with d. Thus
S = Σ[d|p-1] dφ(d)

To efficiently compute this function, factorize p - 1 into powers of distinct primes: p - 1 = q[1]^k[1] q[2]^k[2] ... q[m]^k[m], where all q[.] are distinct and k[.] > 0. Then any factor of p - 1 can be represented uniquely as q[1]^i[1] q[2]^i[2] ... q[m]^i[m] where 0 ≤ i[v] ≤ k[v] for all v. Now φ(q[1]^i[1] q[2]^i[2] ... q[m]^i[m]) = φ(q[1]^i[1])φ(q[2]^i[2])...φ(q[m]^i[m]), so after playing some games with the distributive law,

S
= Π[1≤vm] Σ[0≤i[v]≤k[v]] q[v]^i[v]φ(q[v]^i[v])
= Π[1≤vm] (1 + Σ[1≤ik[v]] q[v]^i . (q[v]^(i-1)) . (q[v] - 1))

(The function prime_power_order(.) probably needs a renaming.)

My code:

#include <limits.h>
#include <stdio.h>

static unsigned long long prime_power_order(unsigned q, unsigned k)
{
        /* find sum of orders for a cyclic group of order q^k */
        unsigned i;
        unsigned long long qq = 1, s = 1;
        for (i = 1; i <= k; ++i) {
                s += qq * q * qq * (q - 1);
                qq *= q;
        }
        return s;
}

int main()
{
        unsigned test_cases;
        unsigned long p, pp, w, k;
        unsigned long long s;
        scanf("%u", &test_cases);
        while (test_cases--) {
                scanf("%lu", &p);
                s = 1;
                pp = p - 1;
                for (w = 2; (unsigned long long)w * w <= pp; ++w) {
                        if (pp % w != 0)
                                continue;
                        k = 0;
                        while (pp % w == 0) {
                                pp /= w;
                                ++k;
                        }
                        s *= prime_power_order(w, k);
                }
                if (pp > 1)
                        s *= prime_power_order(pp, 1);
                printf("%qu\n", s);
        }
        return 0;
}

Official solution:

Note that if n=Π[p|n] p^a then the sum is
Π[p|n] {1+p(p-1)+p^2(p^2-p)+p^3(p^3-p^2)+...+p^a(p^a-p^(a-1))}
which can be also written as
Π[p|n] (1-p+p^2-p^3+...-p^(2a-1)+p^(2a))

Conclusion: really the same solution, except it didn't occur to me to do the final simplification 1 + Σ[1≤ik] q^i . q^(i-1) . (q - 1) = 1 - q + q^2 - q^3 + ... + q^(2k).

Problem 6

fzort solved this problem.

Problem 9

My approach:
I was intending to cast the problem as one of finding the maximum matching in a bipartite graph, but I was too exhausted. :/

Official solution:

The problem reduces to finding maximum cadinality matching in bipartite graphs.

Conclusion: boom.

61 older entries...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!