rangifer’s diary: pt. lxiii

Massive tangent

In “Taxonomising odd jobs, pt. iii: Exploring the space of possible taxonomies. §4”, I talked about weak orderings. I mentioned that weak orderings are enumerated by the ordered Bell numbers (a.k.a. Fubini numbers), that is to say, the total number of possible weak orderings over a set of 𝑛 elements is just the 𝑛^th ordered Bell number. And I asked what the 45^th ordered Bell number is, because at the time of writing, the list of odd jobs on the Oddjobs website had a length of 45. The OEIS entry only lists the ordered Bell numbers up to 𝑛 ≔ 20, so I had to calculate the 45^th element in the sequence myself.

To do this, I looked at two of the formulæ that the relevant English Wikipedia article gives, and wrote some Python functions based on those formulæ. Each of the Python implementations has the same observable behaviour (input a natural number 𝑛, and the function spits out the 𝑛^th ordered Bell number as its output), but they differ in their approaches and in their performance characteristics (time spent computing, memory usage). Although it’s obviously not relevant to what the series is trying to do (taxonomise odd jobs), I did some very informal benchmarking to compare the Python implementations of such a fubini(n) function, because I’m into that kind of thing, I guess. I dunno, I was just curious.

After finishing that entry, I allowed my curiosity to get the better of me, and I continued looking at implementations of this rather simple mathematical function. Out of the Python implementations that I wrote, the implementation that most programmers would likely reach for (for its familiar use of for loops and its predictable performance) would be the straightforward imperative implementation, which I called simply fubini. Knowing that Python, as a characteristically interpreted language, does not optimise programs before executing them (we’re just using CPython here, sorry for any PyPy fans out there^[1]), I wanted to optimise the (-1) ** (k - j) expression that occurs within the definition of fubini. I called this new function fubini_pow:

def fubini_pow(n):
    """
    ``fubini``, but with some optimisations focussed around calculating
    exponents.
    """

    a = 0
    for k in range(0, n + 1):
        for j in range(0, k + 1):
            #   (-1) ** (k - j)
            # = -1 if (k - j) % 2    else 1
            # = -1 if (k - j) & 0x01 else 1
            # = -1 if (k ^ j) & 0x01 else 1
            a += (-choose(k, j) if (k ^ j) & 0x01 else choose(k, j)) * j**n

    return a

Obviously, taking −1 to an integer power returns −1 if the power is odd, and +1 if the power is even. So (-1) ** (k - j) can be optimised to -1 if (k - j) % 2 else 1. But there is actually a better way to check for the parity of k - j: testing the least significant bit (LSB). So we can optimise to -1 if (k - j) & 0x01 else 1. But, because we only care about the LSB of k - j, we don’t really need to perform the full subtraction of j from k. A few napkin-scribbles later, and I figured out that taking the bitwise XOR of k and j will have the same effect on the LSB as subtracting them. So we can optimise to -1 if (k ^ j) & 0x01 else 1. And, instead of multiplying choose(k, j) by this result (which is always either -1 or 1), we can avoid multiplication entirely by inlining choose(k, j) into each branch of the if statement, and using unary numeric negation (-) instead. As we will see, this series of optimisations does indeed speed up the program, although as you’d expect, the performance gain is modest.

I also changed how fubini_rec performs its memoisation. In the previous diary entry, I (somewhat embarrassingly) immediately reached for a hash map, writing memo = {0: 1}. This is perfectly correct, and results in neat-looking code as a result of hash maps being built-in objects in Python. However, it’s kind of a dumb idea, because we know exactly what the set of keys in this map is going to be: {0, 1, 2, ⋯, n - 1, n}. So what we actually want is an array! This changes the code only slightly, resulting in the following implementation:

def fubini_rec(n):
    memo = [None] * (n + 1)
    memo[0] = 1

    def a(m):
        memo_val = memo[m]
        if memo_val is not None:
            return memo_val

        fubini_m = sum((choose(m, i) * a(m - i)) for i in range(1, m + 1))
        memo[m] = fubini_m

        return fubini_m

    return a(n)

And I used timeit to write up a simple — but still more proper than last time — benchmarking program for these Python implementations.

I was curious to see how these functions might perform if they were written using properly-optimised and compiled code, compiled down to some x86-64 machine code to be run natively by my CPU. I’m no expert in numeric computing, so I’m sure some folks can do better, but in my case I just reached for Rust and tried to reasonably translate my Python code into that language. Under my belt, I had the rug crate, allowing me to easily harness the power of GMP to work with arbitrary-precision integers. Arbitrary precision is necessary here, as the ordered Bell numbers are a combinatorial sequence, so they grow really quickly. In Python, we didn’t have to think about it, because Python will automatically switch to using arbitrary-precision integers under the hood, any time that an integer exceeds the capacity of a single word.

In the end, my Rust implementations looked something like:

/// `fubini(n)` is the `n`th Fubini number (a.k.a. the `n`th ordered Bell
/// number).
pub fn fubini(n: u32) -> Integer {
    let mut a = Integer::new();
    for k in 0..=n {
        for j in 0..=k {
            a += (-1i32).pow(k - j)
                * Integer::binomial_u(k, j).complete()
                * Integer::u_pow_u(j, n).complete();
        }
    }

    a
}

/// `fubini`, but with some optimisations focussed around calculating
/// exponents.
pub fn fubini_pow(n: u32) -> Integer {
    let mut a = Integer::new();
    for k in 0..=n {
        for j in 0..=k {
            a += if (k ^ j) & 0x01 == 0 {
                Integer::binomial_u(k, j).complete()
            } else {
                -Integer::binomial_u(k, j).complete()
            } * Integer::u_pow_u(j, n).complete();
        }
    }

    a
}

/// `fubini` defined by `sum`ming iterators, instead of using explicit loops.
pub fn fubini_gen(n: u32) -> Integer {
    (0..=n)
        .map(|k| (0..=k).map(move |j| (k, j)))
        .flatten()
        .map(|(k, j)| {
            (-1i32).pow(k - j)
                * Integer::binomial_u(k, j).complete()
                * Integer::u_pow_u(j, n).complete()
        })
        .sum()
}

/// `fubini_gen`, but MOAR THREDZ!!!
pub fn fubini_par(n: u32) -> Integer {
    (0..=n)
        .into_par_iter()
        .map(|k| (0..=k).into_par_iter().map(move |j| (k, j)))
        .flatten()
        .map(|(k, j)| {
            (-1i32).pow(k - j)
                * Integer::binomial_u(k, j).complete()
                * Integer::u_pow_u(j, n).complete()
        })
        .sum()
}

/// `fubini_par`, but I re-implement `sum`?
pub fn fubini_par_hack(n: u32) -> Integer {
    (0..=n)
        .into_par_iter()
        .map(|k| (0..=k).into_par_iter().map(move |j| (k, j)))
        .flatten()
        .map(|(k, j)| {
            (-1i32).pow(k - j)
                * Integer::binomial_u(k, j).complete()
                * Integer::u_pow_u(j, n).complete()
        })
        .reduce(|| Integer::new(), |acc, x| acc + x)
}

/// Do **not** use this function. It is only here for illustrative purposes,
/// and is completely useless for any significantly large values of `n`.
///
/// Implements `fubini` using a naïve recursive method. I think the runtime is
/// Ω(n!).
pub fn fubini_rec_naive(n: u32) -> Integer {
    if n == 0 {
        1.into()
    } else {
        let mut a = Integer::new();
        for i in 1..=n {
            a += Integer::binomial_u(n, i).complete() * fubini_rec_naive(n - i)
        }

        a
    }
}

/// Implements `fubini` using recursion, but memoises, in order to make the
/// performance (read: asymptotic runtime behaviour) reasonable.
///
/// <https://en.wikipedia.org/wiki/Dynamic_programming>
pub fn fubini_rec(n: u32) -> Integer {
    let mut memo = vec![Integer::new(); (n + 1) as usize];
    memo[0].assign(1);

    fn a(m: u32, memo: &mut [Integer]) -> Integer {
        let memo_val = &memo[m as usize];
        if memo_val != &0 {
            return memo_val.clone();
        }

        let mut fubini_m = Integer::new();
        for i in 1..=m {
            fubini_m += Integer::binomial_u(m, i).complete() * a(m - i, memo);
        }

        memo[m as usize] = fubini_m.clone();

        fubini_m
    }

    return a(n, &mut memo);
}

Naturally, the Rust implementations look a good deal noisier than their corresponding Python implementations, as we now have essentially total control over memory management. One thing that we can immediately note is that the Rust implementation of fubini_pow isn’t very useful. It’s left there for reference, but in reality, optimising “−1 to an integer power” is a trivial task for any optimising compiler (LLVM, in our case). The manual optimisation that we did with Python is done here for us automatically, making the Rust versions of fubini and fubini_pow effectively identical, after code generation.

Everything else is pretty self-explanatory here, considering that they are more or less one-to-one translations of the Python implementations. I did, however, add the fubini_par and fubini_par_hack functions, which make use of rayon to turn fubini_gen into a multithreaded version of the same thing, with very minimal changes to the code. The low effort required to make fubini_gen parallel by slapping rayon on it was enough to tempt me to do it. So I did. That’s not to say that rayon produces a good and reasonably-close-to-optimal parallel computation of ordered Bell numbers here… again, I was just goofing off. I also realised just now (oops) that the cloning occuring in return memo_val.clone(); (within fubini_rec) is probably not necessary. Oh well.

In any case, I benchmarked these functions. As mentioned before, timeit was used for benchmarking the Python code, and for the Rust code, criterion was used. This probably skews the results in favour of Python a bit, as criterion will spit out its best estimation of a “representative” timing (criterion uses fairly rigourous statistical methodology), whereas our Python benchmarking just takes the best time of five trials (each trial being the arithmetic mean of usually a few hundred iterations). That being said, the results are at least reasonably comparable. The benchmarking was done on an Intel i7-4510U CPU running at 2.00 GHz; this is a laptop processor, although I did not have anything else of significance (not even any display server whatsoever — completely headless and accessed only via SSH) running concurrently with the benchmarks.

Without comparing all of the numbers here, we can compare the two implementations (Python vs. Rust) of fubini_rec (the fastest version within either language) at n = 250 to get a vague idea of how much time (not to mention memory) we save by switching from Python to Rust: a factor of roughly ≈21.9. Whew!

Alright, enough useless software engineering nonsense for now.

Footnotes for “Massive tangent”

1. [↑] Testing with PyPy does (as expected) give faster results across the board. Interestingly enough, the performance gains are considerably higher for fubini_rec in particular, for smaller values of n. It seems PyPy finds some good optimisation that ends up being dominated by the bulk of the arithmetic computation, as n gets larger. Maybe some inlining to reduce function call overhead, or better implementation of the cache array. Who knows! As it turns out, PyPy is roughly ≈1.33 times faster than CPython for fubini_rec(250). For fubini_rec(50), this factor is ≈3.33!

Taxonomising odd jobs, pt. iii: Exploring the space of possible taxonomies. §5

In the previous section (§4) of this part (pt. iii), I talked about weak orderings, and had this to justify it:

The reason for considering weak orderings is that when we hand-craft our “phylogenetic tree(s)”, we may want to start with the most skeletal structure possible: ordering our objects (our odd jobs) in roughly “chronological order” (or rather, some notion of “primitiveness”). This will certainly end up being a weak ordering, as there should be many pairs of objects where we just don’t know if one “came first”, the other one “came first”, or they emerged at “the same time”. If 𝑂 is our set of odd jobs, and we had such a pair of objects (𝑎, 𝑏) ∈ 𝑂 × 𝑂, then under our weak ordering (𝑂, ≤), it would be true that 𝑎 ≤ 𝑏 ∧ 𝑏 ≤ 𝑎. We can then impose this ordering, later, onto our tree… or whatever it is. We shall investigate this next time, I guess.

Well, it is now “next time”, so I want to cover this, at least somewhat.

Trees are for treehouses

What is a tree? Well, a tree is a perennial plant with an elongated stem/trunk, supporting branches, and — in most species — leaves.

Just kidding. A tree is actually a connected acyclic undirected graph. Unfortunately (or fortunately…?), this means that we are going to end up in “graph theory 101” territory before we can talk about our leafy friends. So let’s break this down a bit:

A graph is, informally, a bunch of vertices (which are basically just… objects) that may or may not be joined to one another. Two vertices are joined when there is an edge joining them. Usually, when we visually represent graphs, we represent a vertex with a circle, and we represent an edge with a line that connects two circles. But graphs are really abstract, so they can represent a lot of things, not just circles and lines. Formally, a graph 𝐺 is a pair 𝐺 ≝ (𝑉, 𝐸), where 𝑉 is a set of objects called vertices, and 𝐸 is a set whose members are sets of cardinality exactly 2, where each member of such a 2-set is also a member of 𝑉. These 2-sets are called edges.

An undirected graph is the same thing as what I defined as a “graph” above. The reason for specifying that a graph is “undirected” is to clearly distinguish from a directed graph, which is a graph whose edges have a specified direction, from one vertex to the other. When we visually represent directed graphs, we usually show the direction of an edge by adding an arrowhead to the corresponding one of its ends (so it looks like “→” or “←”). Formally, a directed graph is defined similarly to an undirected graph, except that instead of defining 𝐸 in terms of 2-sets, 𝐸 ⊆ {(𝑥, 𝑦) ∈ 𝑉 × 𝑉 | 𝑥 ≠ 𝑦}.

An acyclic graph is a graph that has no cycles. If you have a vertex 𝑥, and you can walk from 𝑥 back to 𝑥 along one or more edges of the graph, without walking along any given edge more than once, that’s called a cycle. So if you’re walking along an acyclic graph, then you cannot leave your current vertex, and then return back to that vertex, without re-treading any edges. Formally, a walk on a graph 𝐺 ≝ (𝑉, 𝐸) is a sequence of edges ⟨𝑒₁, 𝑒₂, ⋯, 𝑒_𝑛−2, 𝑒_𝑛−1⟩ (where 𝑒_𝑖 ∈ 𝐸) such that there exists a sequence of vertices ⟨𝑣₁, 𝑣₂, ⋯, 𝑣_𝑛−1, 𝑣_𝑛⟩ (where 𝑣_𝑖 ∈ 𝑉), so that for all 𝑖 < 𝑛, 𝑒_𝑖 = {𝑣_𝑖, 𝑣_𝑖+1}. (For directed graphs, we can just change that last equality to 𝑒_𝑖 = (𝑣_𝑖, 𝑣_𝑖+1).) A trail is a walk where 𝑖 ≠ 𝑗 → 𝑒_𝑖 ≠ 𝑒_𝑗. A circuit is a nonempty trail where 𝑣₁ = 𝑣_𝑛. A cycle is a circuit where 𝑣_𝑖 = 𝑣_𝑗 iff 𝑣_𝑖 = 𝑣_𝑗 = 𝑣₁ = 𝑣_𝑛. And, since we’re talking about trails, a path is a trail where 𝑖 ≠ 𝑗 → 𝑣_𝑖 ≠ 𝑣_𝑗.

A connected graph is a graph in which every vertex is connected to every other vertex. A pair of vertices is connected if you can walk, along edges, from one to the other. If a graph has one or more pairs of vertices that are not connected (that are disconnected), then the graph is a disconnected graph. Every graph is either connected, or else disconnected. Formally, two vertices (𝑣_𝑖, 𝑣_𝑗) ∈ 𝑉 × 𝑉 of a graph 𝐺 ≝ (𝑉, 𝐸) are connected when there exists a walk on 𝐺 whose vertex sequence is ⟨𝑣_𝑖, ⋯, 𝑣_𝑗⟩. Two vertices (𝑣_𝑖, 𝑣_𝑗) ∈ 𝑉 × 𝑉 of a graph 𝐺 ≝ (𝑉, 𝐸) are disconnected iff they are not connected. A graph 𝐺 ≝ (𝑉, 𝐸) is a connected graph when, for all (𝑣_𝑖, 𝑣_𝑗) ∈ 𝑉 × 𝑉, (𝑣_𝑖, 𝑣_𝑗) is connected. A graph is a disconnected graph iff it is not a connected graph. For directed graphs, we can define a weaker version of connectivity, weakly connected, which describes two vertices that would be connected if all edges in the graph became undirected (via a function that maps any edge (𝑣_𝑖, 𝑣_𝑗) ↦ {𝑣_𝑖, 𝑣_𝑗}).

When a graph is acyclic, as defined above, there is at most one path between any given pair of vertices. The reason is that, if there were two distinct paths 𝑝₁ ≠ 𝑝₂ between a pair of vertices (𝑣₁, 𝑣₂), we could take 𝑝₁ from 𝑣₁ to 𝑣₂, and then 𝑝₂ to go from 𝑣₂ to 𝑣₁. And in there somewhere, would be a cycle! A (very) informal proof of this might look like: If the two paths share no edges, then chaining (i.e. connecting end-to-end) the paths would form a cycle (or, if it forms a circuit instead, that’s okay — every circuit contains at least one cycle). If the two paths do share edges, then we can manipulate our graph 𝐺 to produce a new graph 𝐺′ in which all of these shared edges have been contracted. Edge contraction preserves paths in the sense that any path in 𝐺 that connects two of its vertices also exists in 𝐺′, albeit with some edges possibly removed from the sequence — remember that empty (i.e. length 0) paths are perfectly valid. And there are still two distinct paths 𝑝₁′ ≠ 𝑝₂′ that connect our vertices (𝑣₁′, 𝑣₂′), as the paths were distinct before, so they could not possibly have shared all of their edges. But now, thanks to the edge contraction, chaining 𝑝₁′ with 𝑝₂′ definitely forms a cycle — 𝑝₁′ and 𝑝₂′ share no edges. This means that 𝐺′ is cyclic. If 𝐺′ is cyclic, then 𝐺 must be cyclic too, as the only thing that we did to go from 𝐺 to 𝐺′ is contract some edges, which cannot create new cycles, as it does not create new trails (it just shortens them). By contradiction, any acyclic graph must have at most one path between any given pair of vertices.

If a graph is acyclic and connected (i.e. a tree), then we can strengthen “at most one path between any given pair of vertices” to “exactly one path between any given pair of vertices”. Having less than one (i.e. zero) paths between a pair of vertices is impossible, as all such pairs are connected! This stronger condition is, essentially, what it means for a graph to be a tree.

Treerarchy

As they are, trees are a tad bit abstract. We can, however, impose some additional structure.

A rooted tree is a tree in which exactly one of the vertices has been designated as the root. Every rooted tree 𝐺 ≝ (𝑉, 𝐸) has an associated tree-order, which is a partial order over 𝑉 — call it (𝑉, ≤) — such that (let 𝑣, 𝑤 ∈ 𝑉) 𝑣 ≤ 𝑤 iff the path from the root to 𝑤 passes through 𝑣. This path from the root is guaranteed to exist and to be unique, because of the properties of trees discussed above.

Another ordering that we can impose on a rooted tree is that of depth. The depth of a vertex is the length of the path between it and the root. Naturally, this produces a weak ordering ((𝑉, ≲) such that 𝑣 ≲ 𝑤 iff the depth of 𝑣 is less than or equal to the depth of 𝑤), as depth values are natural numbers, and two distinct vertices can possibly have the same depth. In the special case of phylogenetic trees, this ordering can have a special meaning when paired with a molecular clock hypothesis: each depth value (or rather, the equivalence class associated with such a depth value) is essentially an evolutionary generation, and larger values correspond to times that are further in the future. However, in our case (taxonomising odd jobs), this depth-order won’t really have a meaning (especially not for our hand-crafted trees).

Although depth-order may not be quite so useful, the tree-order is what we want to combine with the hypothetical weak ordering of our set of odd jobs that was mentioned in §4 (and was quoted above). Let 𝑂 be our set of odd jobs, and let (𝑂, ≲) be our weak ordering of odd jobs by “primitiveness” (or whatever), where 𝑜 ≲ 𝑝 (𝑜, 𝑝 ∈ 𝑂) is interpreted as “𝑜 is more ‘primitive’ than 𝑝”. Suppose that we produce a single rooted tree 𝑇 = (𝑂, 𝐸), which has a tree-order (𝑂, ≤). Then we want to maintain the following invariant: 𝑜 ≤ 𝑝 → 𝑜 ≲ 𝑝. I should stress that this is a one-way implication, not an iff.

Forestry

We can lift the connectedness requirement on our definition of trees, resulting in simply an acyclic undirected graph (that is not necessarily connected). This is known as a forest, because such a graph can be thought of as the disjoint union of zero or more trees. Formally, the disjoint union of two graphs 𝐺₁ ≝ (𝑉₁, 𝐸₁) and 𝐺₂ ≝ (𝑉₂, 𝐸₂) is another graph 𝐺₁ + 𝐺₂ = (𝑉₁ ⊔ 𝑉₂, 𝐸₁ ⊔ 𝐸₂). Taking the disjoint union of two or more nonempty trees necessarily results in a disconnected graph, despite the fact that each tree is itself, by definition, connected.

Forests could be useful for our case, because they allow for two objects to be well and truly unrelated, by simply being disconnected within the graph representation. This would correspond, in the biological case, to two species who have no common ancestor(s) whatsoever. In the biological case, there is, empirically, apparently no such thing — it is commonly understood that all known lifeforms ultimately decend from a last universal common ancestor, which makes every species part of a colossal phylogenetic tree spanning some 3 to 5 billion years or so. In our case, however, it may very well make sense to have a pair of odd jobs be completely unrelated.

Because we want our trees to be rooted, we will end up with a rooted forest, which is just a disjoint union of zero or more rooted trees. Let 𝑇₁, 𝑇₂, ⋯, 𝑇_𝑛−1, 𝑇_𝑛 be our rooted trees, let ℐ ≔ {𝑖 ∈ ℕ | 1 ≤ 𝑖 ≤ 𝑛} be the index set for our collection of trees, and let 𝐹 ≔ ∑𝑇_𝑖 (for each 𝑖 ∈ ℐ) be our rooted forest. Each rooted tree 𝑇_𝑖 ≝ (𝑂_𝑖, 𝐸_𝑖) has a vertex set 𝑂_𝑖 ⊆ 𝑂, as well as a tree-order (𝑂_𝑖, ≤_𝑖). Then we can generalise the invariant above to: ∀𝑖 ∈ ℐ ∀(𝑜, 𝑝) ∈ 𝑂_𝑖² [𝑜 ≤_𝑖 𝑝 → 𝑜 ≲ 𝑝].

A little card-hunting with capre

As readers of this diary may know, I’ve done the most card-hunting of any of my characters on my woodsmaster, capreolina. Well, I went back to a little more card-hunting where I last left off: Orbis.

I had to take care of the rest of the big cats: Lioners & Grupins.

Once that was over with, I was done with Orbis entirely (minus Eliza, as I refuse to card-hunt area bosses that are required for quests). So I headed to the bottom of the respective tower, to farm some more cards at Aqua Road. I have farmed at the upper regions of Aqua Road before, so I already had quite a few of the sets finished (and some partially finished). But I needed some of the ones to the far west, near the base of the Orbis Tower. So I farmed around there (e.g. in Ocean I.C):

The Poison Poopas were giving me a bit of a hard time, but all I had to do was complain about it in alliance chat, and suddenly they started spitting out more cards than I even needed. Hooray for 6⧸5 Poison Poopas…!

And, while I was hunting, Battlesage (Permanovice, Dreamscapes, Hanger), an F/P gish also of Oddjobs, pulled me aside to show me 3 “bois”:

Three fine-looking gish weapons! And in every colour of the rainbow… that yellow-glowing one is really somethin’ else.

A little questing with alces

I did some more questing in Victoria Island with my undead daggermit alces! I went to wrap up the Icarus questline, so I had to get some Alligator Skin Pouches:

…And Tablecloths:

Oh, and I have to 1v1 some swamp plants to the death, as well. We can’t go around making magical flying pills without some swamp leaves… with seemingly-too-low drop rates:

And there it is; the magical flying cape of legend:

Nice!

Oh, and I prepared the ETC items that I needed for the Sauna Robe questline. I ran around to various NPCs, and lo and behold, a robe of my own:

Stylish.

And I headed to deep Sleepywood to work on Muirhat’s monster-slaying questline. Next up was Drakes and Ice Drakes:

NIce Drake card.

And then, I started Muirhat’s last quest, along with concurrently starting the latter half of A Spell That Seals Up a Critical Danger — both of these quests require at least some Tauromacis kills, although the latter quest is clearly considerably more difficult. A tad ironic, considering how much lower-level it is, and how much worse the reward is…

And, as usual, my suspicion that Taurospears have a much higher card drop rate than Tauromacis is confirmed again and again… I’ll have to finish up this quest later, it’s a real doozy.

Permanovice’s level 100 party

I was honoured to attend the level 100 party of STRginner Permanovice! The first part of the party was to engage in ritualistic snail murder, which Permanovice assured us was a very sacred permabeginner ritual that he needed to undergo in order to achieve level 100 beginner. As it happened, by the time that the party’s scheduled date rolled around, the summer event had started. So the bonus event EXP made it so that the sequence Snail → Blue Snail → Red Snail → Mano would level Permanovice prematurely, before getting to the Mano. Oh well… The party was still on, and starting in Lith Harbour:

Although I had to leave early and didn’t experience the omok tourney, the party went as planned, and we even found a Mano :) Congrats again on the big level 100!!! :D

capre trawling the Phantom Forest w/ NZPally & Yohichi

I teamed up with NZPally again on my woodsmaster capreolina, to kill some more bosses. We also teamed up with bishop Yohichi, an old friend of NZPally’s, who came with us to the Phantom Forest in search of HH’s head and BF’s toe.

With some luck, and with NZPally’s relatively extensive knowledge of the Phantom Forest’s geography (I’m no newb to the forest myself, but I admit that I only go to a few places within it, so my knowledge is not very broad), we found a HH — actually, 2 or 3 of them in total:

And we also found some Bigfeet as well! Here I am, confidently standing just far enough away from the thing that will instantly kill me if it touches me:

All in all, I got quite a bit of EXP this session, and capreolina is now level 123!! Level 9 SE yayy~

Visiting the Temple of Time for the first… time

Believe it or not, I’ve never actually checked out the ol’ ToT. I suppose I never really had any reason to go there, and I wasn’t even aware of how to get there… As it turns out (for anyone not already familiar), ToT is accessible via Leafre — in particular, you go there by going to the same map that you would visit if you were headed to Orbis, but instead of talking to the ticketing guy there to board the ship to Orbis, you go wayyy on up to the tippy-top of the map to talk to Corba. As it turns out, Corba is a retired dragon trainer. What Corba is doing hanging out at the “cabin” from Leafre to Orbis, I’m not sure, but in any case, Corba’s experience with dragon training proves useful to any intrepid Minar Forest explorer. The reason for this is that Corba can not only train dragons, but can simply turn you into one!:

Wowie. Besides being cute, turning into a dragon means that no ship, nor anything like that, is required to fly through the skies — you have your own wings now. While this is generally fun and all, the real purpose is to fly high above the clouds, where amongst the heavens you can find the apparently Ancient-Greek-inspired architecture (think Orbis^[1], but everything looks bigger and more expensive) of the Temple of Time.

Besides its grandiose & ancient-but-pristine architecture, the Temple of Time attempts to invoke themes of… well, time, obviously. Much like time elsewhere, the time in this region of MapleStory appears to march unceasingly and in a single direction — yet, since we are talking about turning into a dragon to fly into the heavens where there’s an inexplicable giant floating palace, why not mess with time itself, as well?

So, this is our task: for vague and unspecified reasons, something is funky — and not in a good way — with the Temple of Time, and it is our job to investigate. But, in order to do so, we must walk down Memory Lane — and not just anyone can do that. In order to uncover these memories that are apparently too old to be our own (and yet, they are), we need permission. So for that, we must prove our strength to the keeper of the Temple. I played as my pure STR bishop cervid, and teamed up with ducklings, Harlez, Gruzz, and xBowtjuhNL to do just that:

The ToT quests are simple: kill 999 monsters, thus completing your current quest, and the next map is then opened up for you. The next quest asks to kill 999 monsters in this new map, and we rinse & repeat.

After Memory Monks (which I know as simply “pointy monks”) come Memory Monk Trainees (which I know as simply “pointy monks w/ babies”):

These guys are no joke: the ones with babies are level 94, with a whopping 45k HP a piece. Everpresent are the Eyes of Time (which I know as simply “flappy hourglasses”), which have 24k HP a piece and some nasty magical attacks… although you are never required (at least, not directly) by the quests to kill them.

Next are the Memory Guardians (which I know as simply “gassy armour”), level 98 with 53k HP a piece:

The EXP so far has been fairly decent, which is great for cervid. I suspect that these quests are reasonably doable by cervid when soloing (at least, the first few ones that I’ve seen), although in that case the EPH would be much less useful… and it would make an already tedious questline even more so!

Now, on to complete the pointy armour quest…

Footnotes for “Visiting the Temple of Time for the first… time”

1. [↑] Funnily enough, it seems that, like Orbis, the Temple of Time has its own “Goddess” (who is also often referred to simply as “Goddess”) who is, again like the Goddess of Orbis, mysteriously MIA. In the case of Orbis, reviving Minerva the Goddess (and thus, presumably, relieving her from being a broken stone statue for all eternity) is the crux of the Orbis Party Quest. In the case of ToT, the Goddess’s name is Rhinne, and as the Goddess of time itself, she exists in an eternal state of slumber. What exactly this is ultimately supposed to mean, I’m not sure. But, then again, I’m also not sure exactly what else I’d expect the personification of time to be doing…

Outland BPQ w/ woosa

I also, with much the same crew, hit up the PQ that comes with the current summer event: Boss (Rush) Party Quest, or BPQ for short. I hopped onto my darksterity knight rusa and was transported back to MPQ, with the same folks with whom I MPQ’d originally!:

Although, this time we didn’t have to save Romeo, and Franken Lloyd really went down like a chump…

Oh, and also in BPQ, we had the chance to fight our favourite apocryphal sea lizard:

And this was about as far as we went, usually. The first time, we tried killing Papu Clock and were able to defeat it, and make it to Pianus… but with only 90 seconds or so on the clock, and with xBowtjuhNL having used an Onyx Apple. >.<

Vic island questing w/ d34r

I wrapped up what are essentially my last few (sadly) quests on my Vicloc dagger spearwoman d34r. The first order of business was two of the same quests mentioned earlier in this entry: Muirhat’s final quest, and A Spell That Seals Up a Critical Danger.

Now, doing these quests was really not easy. Tauros have gobs of HP, and Taurospears in particular pose a problem: level 75, 18k HP, 550 WDEF, 390 MATK, and 30 AVOID… yowza. Combine this with their rather… difficult spawn rates, and yanking the Spirit Rocks out of these fuzzy bull-headed bastards was like pulling teeth.

But, I did get two card sets out of it!

Oh, and I found this weird book?:

I asked Manji about it, but he didn’t seem to know anything about it…

Eventually, the Tauros relented and let me have my Spirit Rocks. So I carried on to do the easier part of that quest: collecting Wild Kargo’s Spirit Rocks.

And with 33 of those also under my belt, I was able to claim my… mildly underwhelming prize:

With that out of the way, I went to do another quest that also involves Tauros (somewhat): “Luke the Security Man’s Wish to Travel”. This level 50 quest is for warriors only — there are corresponding Victoria Island quests for other archetypes as well, although they differ considerably from one another. This one is a real doozy:

Luke is not kidding about how ridiculous the necessary materials are. In total, I had to collect:

• 3 Taurospear Horns,
• 50 Dragon Skins,
• 11 Orihalcon Plates,
• 1 Flaming Feather,
• 1 Black Crystal,
• 1 Bronze Plate,
• 1 Steel Plate,
• 1 Mithril Plate,
• 1 Adamantium Plate,
• 1 Silver Plate,
• 1 Gold Plate,
• & 40 Screws.

Nevertheless, I was determined to complete this quest. So I had to hunt for another Flaming Feather. Readers of this diary will know just how much fun I find it to hunt Flaming Feathers on Victoria Island… Thankfully, after a while of grinding Red Drakes, xXCrookXx wished me luck, and it seemed to do the trick!:

Wowee. That could have been a lot worse. Now that I had this rare item out of the way, it was time to do some crafting:

Geez. Thankfully, I was well rewarded for my efforts: an insignificant amount of EXP, and a beat-up warrior helmet that I sold to an NPC within 90 seconds of acquiring it! Thanks Luke.

And I wanted to wrap up just one last quest: Mrs. Ming Ming’s Second Worry. I had this one nearly finished for a long time, and just needed to get around to farming a few more Pig’s Heads. So I did:

And this one, although it may require a whopping 20 Pig’s Heads, does pay pretty well, with none other than our good old friend the Ribboned Pig Headband:

50 MAXHP and 12 WDEF! An excellent secondary helmet for the squishier among us.

d34r & xXCrookXx leave Victoria Island in search of better PQs

Now, being a Victoria Islander is great and all, but there’s just one issue: the PQs. I’m too high level for KPQ, I’m not a huge fan of HPQ (not that the EXP would be very rewarding at level 73), APQ sounds great but has some nasty time limits that prevent me from entering my normal state of existence (24⧸7 PQing), and SGQ just ain’t never gonna happen, let’s be real. So it seems that there is only one solution: escaping the island we know as Victoria.

I tried to elope with fellow viclocker xXCrookXx, but our first attempt didn’t pan out…:

R.I.P.… It seems that Ossyria really is a hoax designed to feed the Crogs.

But we didn’t give up. After some effort, we made it all the way to Magatia, where we were just the right level to participate in the Magatia Party Quest:

Just kidding. Both of the above screenshots are actually from BPQ. Speaking of Vicloc BPQ, some of the non-boss monsters that are summoned by the bosses in BPQ actually drop cards. Take Kimera for example, who is capable of summoning Roids that drop Roid Cards. We found this out first-hand, when xXCrookXx looted one of these sacred Roid cards:

Of course, these exotic BPQ cards actually are perfectly Vicloc-legal, so no one was banned. :P

Oh, and also, we went to Mu Lung Gardens to participate in MLGPQ (Mu Lung Gardens Party Quest) with STRginner Outside…:

d34r is stronk!!!

d34r has been using a 6 WATK, 4 STR Dark Knuckle as her main (read: greedy damage) glove for a while now. As I’ve started to accumulate GFA60s, I’ve considered scrolling another glove to try to beat that. I struggled for a while, trying to decide on how greedy I should be: be extra greedy and scroll a nice warrior glove that has lots of STR/DEX/WACC/WDEF on it, or be less greedy and scroll a Work Glove of some kind, so that I can give it to a fellow Viclocker in need of WATK gloves when I likely fail to make a very good glove? In the end, I decided to be a little less greedy and use some of my scrolls on an RWG:

o_o Holy moly!! The first ≥10 WATK vicloc glove!!! Who ever said I was no good at scrolling????

Now that I had a nice new pair of gloves, I wanted to upgrade my rather sad cape situation. For almost the entirety of d34r’s career, she has been using an ORC with 3 DEX and 2 LUK (owie), or more likely, a (+0) Icarus Cape (2) with 4 slots left… for the SPEED…

I had already “boomed” 2 or 3 other nice capes in an attempt to just pass a single cape STR 60%, but it seemed that the 60% figure was lying to me. I tried once again on a random RMC that dropped from a Wild Kargo that I killed, and lo and behold, I actually managed to pass a 60% on it. Not just one, either — three in total:

Not bad!

But we’re saving the best for last, here. I have been hunting Balrog Junior for… weeks, months, decades. Millenia. The number of Mana Elixirs that I’ve seen this beast drop would be enough to feed a smol village for a year. Eventually, I came to believe that, perhaps, Jr. Rog doesn’t drop Golden Rivers at all. Perhaps the Golden River is listed in Jr. Rog’s droptable on the MapleLegends library specifically to mess with Viclocked dagger warriors. Perhaps, Jr. Rog can read my mind, and knows what I want — and that is why he will not drop it. So, you could almost imagine the sensation that I felt when I saw this happen:

Actually seeing this impossible item flying into the air was enough to make my stomach drop. It took me a minute or two before I actually had the courage to look at the thing and see its WATK value:

Three above average!!!!!!!! That’s eight better than what I was expecting! I admit to taking another few minutes before I had the courage to scroll it, even though I already had 10 dagger WATK 60%s in my inventory. But, again much to my pleasant surprise, it went quite well:

Few times have I ever been so thrilled to have a MapleStory item in my life… My character finally feels complete.

And I got to test out this sleek little dagger when GM buffs were announced, and xXCrookXx and I did an intense 60-minute GM buffs TfoG session:

Oh my. GM buffs are wild…

Getting that T2 before the big day

There are a total of 69 card sets natively available to Viclockers, which means that the tier 2 Monster Book Ring is the highest tier that can be achieved. So, it was time for d34r to get to that 60^th set and finish off her card-hunting career for good!

The first order of business was actually just to finish off that red tab — I had 5⧸5 on all of those monsters, except for Bubblings, of which I had no cards at all:

And, while I was in the Kerning City subway, I went to do the Stirge set:

These slippery batty bois prove to be somewhat difficult to efficiently kill with nothing other than a dagger… Nevertheless, I was able to finish the set and continue on further into the subway:

Wraiths proved to be perhaps the easiest of them all, as I already had two or three of their cards, and they readily gave up the rest that I needed. With that, I moved to the Excavation Site in Perion:

The Ghost Stumps appear to have more favourable card drop rates than their masked friends, but eventually, I was able to squeeze 5⧸5 out of all of them.

I wasn’t quite sure where to go next, but I decided it would be a good idea to take care of the iron-clad swine card sets:

Iron Boars are kind of similar to Red Drakes: both only spawn in a single map in the entire game, both of their respective maps are relatively hidden, and both of their respective maps are in Perion.

With the armoured pigs out of the way, I headed over to Dyle’s map to hunt the Croco cards (and maybe a Dyle or two…):

And now, with 59 full sets done, it was time to get that 60^th set. For this, I headed to Lorang Lorang Lorang (Lorang Lorang…):

Lorangs are kinda funny-looking. They have a single big claw. Although the six appendages of the Lorang are not necessarily accurate to real-life crabs (Brachyura), which generally have ten appendages, there is a very real family of crabs whose members possess a single oversized claw: fiddler crabs (Ocypodidae). Only the males have the strangely large claw, and the crabs themselves are somewhat small (5 cm across, at most).

After a while, I got the Lorangs to cough up the last two cards that I needed to finish their set. And there it was: 60 finished sets overall.

Yay!!! Now d34r feels even more complete! And just in time.

My first mushroom marriage

Just in time for what? Why, my first MapleStory marriage, of course! :)

Although Vicloc is, in the grand scheme of things, a quite restrictive mode of playing MapleStory, it is not so devoid of content as it might seem at first blush. One aspect of this is the simple fact that Amoria is a part of Victoria Island.^[1] Amoria opens the door to a number of things, including:

• Sakura Cellions, which drop some special items that are difficult or impossible to find elsewhere;
• Some extra quests, including “Beauty or Beast!”, “About the Amorian Challenge!”, and “Red Dahlia”;
• Some additional grinding/farming maps that are good for parties of ≥2, including PP1 (for low-level characters and for farming items that drop from any monster), PWF1 (for medium-level characters), and PWF2 (also for medium-level characters);
• Some additional hair/face styles that would otherwise be unavailable to Viclockers;
• HP warrior clothing;
• APQ;
• and of course, marriage itself, which comes with a large number of its own goodies.

However, so far, no one in Vicloc has actually married (or even attended a wedding, for that matter). In order to marry, though, the one who is making the engagement ring has to acquire 20 Soft Feathers (assuming that they are Vicloc; outlanders have other options). In GMS, Sakura Cellions dropped Soft Feathers. However, in MapleLegends, for some reason, Sakura Cellions don’t drop them. Indeed, they aren’t available on Victoria Island at all. So we have a special exception in da roolz that allows for Viclockers to acquire Soft Feathers without ever leaving Victoria Island. When xXCrookXx (Level1Crook, Lv1Crook) and I (d34r) were at The Cursed Sanctuary killing Jrogs together, and we had killed the last of the eight channels, xXCrookXx told me that he had gathered up 20 Soft Feathers. He asked if I wanted to marry him, and I said yes.

Although the proposal was not exactly supposed to be theatrical, it was at least in an appropriate place: Jr. Balrog’s lair (plus, Sleepywood maps are some of the most beautiful maps in the game, in my opinion). Now, it was time to put together an engagement ring so that we could get engaged, in preparation for marrying on the next day!

We decided on the most expensive of the four engagement ring types: the Moonstone ring. So we paid a visit to Chris in Kerning City to refine some ores:

And I gave xXCrookXx the rest of the ETCs necessary for all four Proofs of Love:

And now, with a fully-crafted Moonstone Engagement Ring, we got engaged:

Now we had to figure out our outfits for the wedding, so we paid a visit to Vivian Boutique:

In the end, I went with the Red Bridesmaid’s Dress combined with my usual long boots (Antique Demon Long Boots). And we collectively decided on both wielding Field Daggers.

As the planned time for our wedding approached, xXCrookXx was at the Sanctuary Entrance fighting Taurospears/macis for their associated quests, and I asked him to check for Jrog. As it happened, all of the Jrogs were up at that time, so I zoomed over there and we hurriedly tried to kill all of them before the wedding:

We were able to make it to the cathedral just about on time — at least, certainly before anyone else got there. And luckily for us, many people were able to attend: Viclockers Thinks (OmokTeacher, Slime, Slimu), LoveIslander (NZPally, NZIslander), SeaThief, and xXcorticalXx/SussyBaka (Phoneme, Cortical, moonchild47), as well as Permanovice and kookiechan, who brought with them a whole host of other lovely people, including (but not limited to) Buqaneer (IceGrinder), kleene, and Bretticuss (xBrett).

Unfortunately for us, however, xXCrookXx and I were both total wedding newbs. Because xXCrookXx had already purchased the wedding ticket from the Cash Shop, and we had already made the engagement ring and gotten engaged, I thought that all we had to do was go inside. As it turns out, this is not sufficient.

When he tried to go inside the cathedral, xXCrookXx informed me that I needed to get permission from my parents. So I headed through HHGII to Meet the Parents. Much to our collective dismay, Mom & Dad had nothing to say to me, other than to tell me to see High Priest John… So back to Amoria I went. But again, no dice. High Priest John had nothing useful to say to me. After an embarrassingly long string of running back and forth between Meet the Parents and Amoria proper, we found out that I needed two Proofs of Love, which I would give to my parents in exchange for wedding permission. So I made haste to Perion and Kerning City, to turn in some Firewood and Horny Mushroom Caps, respectively. Then back to Meet the Parents… then back to Amoria…

And finally, after a little more scrambling about with the NPCs in Amoria, and some more flustered apologies to our guests, we managed to get into the damn cathedral.

It took two tries, as not everyone was actually ready to go in yet — we sent out a bunch of invitations, but not everyone joined within the first ten minutes, so we got kicked out. But, eventually, everyone was in, and we could actually begin the wedding:

Beautiful. Who needs the Smoochies emote when you have the Queasy emote?

And Phoneme, as the Vicloc “boss” (read: non-Vicloc guild leader mule), took this opportunity to give a classic drunken-wedding-speech. Phoneme let everyone in attendance know that Victoria is a Victoria-Island-based crime syndicate (of which, Phoneme presumably assumes the role of kingpin), and that Victoria Islanders own the island and all area bosses within it.

And with that, it was time for the cake photos:

This entire time, we had been hoping that someone would get a Heart Wand or Heart Staff so that my Vicloc clericlet d33r would have something to look forward to at level 54 (Heart Wand/Staff is endgame for Vicloc magelets). I even put it on my wedding gift wishlist! And much to my pleasant surprise, LoveIslander was lucky enough to get a Heart Wand from his Onyx Chest, for which I exchanged a perfect (29 WATK, 5 LUK, 4 AVOID, 7 slot) Dark Slain!!:

Yayy!! And from my Onyx Chests, I received a Yellow Chair (on d34r) and a Moon Rock (on d33r). xXCrookXx got, from his Onyx Chest, the sacred Amorian Relaxer.

Later, xXCrookXx and I went to TfoG for some honeymoon grinding, and on a whim, he gave me a single helm DEX 10% (only available from Dyle) to try on my helmet:

Holy moly!!! It looks like this helmet is never leaving my head; it doesn’t get much better than that. :D

Looking forward to some APQ in the future, hehe!

Footnotes for “My first mushroom marriage”

1. [↑] See the “Is Amoria part of the Victorian Archipelago?” section of pt. ci of this diary.

Hunting Jrog w/ KaleBeer

xXCrookXx and I also went back to the Cursed Sanctuary to kill some more Jrogs. After killing them, we sat in the sanctuary to chit-chat, and a little over two hours later, KaleBeer came along looking for some Jrogs. We told KaleBeer that none of them could be up right now, as we have timers for all eight channels. After xXCrookXx said goodnight, I chatted with KaleBeer and explained why I was there at the Cursed Sanctuary. KaleBeer was intrigued, and I agreed to help him get Jrog cards (as I, of course, got 5⧸5 cards long ago)! KaleBeer buddied me, and we went on a Jrog hunt as my timers came around.

We were able to finish KaleBeer’s Jrog card set!:

And KaleBeer even helped me out with some other area bosses that he needed cards from (Faust, ZMM), letting me kill them! Unfortunately, no shield STR 60%s to be found… x)

<3