Showing posts with label fun. Show all posts
Showing posts with label fun. Show all posts

Friday, September 18, 2015

Mercurial koans

A young acolyte approached Master Hg.  "Master Hg, what is the nature of Mercurial Branches?"

Master Hg replied, "Branches are markers attached to every commit, indelible and eternal."

The acolyte nodded.  "Master, if we use branches for tracking new features in our product, how are we to avoid namespace pollution?"

Master Hg regarded the acolyte coolly.  "Mu.  Branches are lines of development, forgettable and ephemeral."

At once, the acolyte was enlightened.

A student was working under Master Hg.  "Master, yesterday I discovered a seven-headed hydra in our history."

Master Hg nodded, saying nothing.

"I did not wish to fight the beast, but I noticed it resided entirely on a separate branch.  So I closed the branch, and thought it dealt with.  But today I looked again and saw the hydra still lived.  Why was the branch not closed?"

"The branch was indeed closed," replied Master Hg, "leaving six branches open."


Ed. note: This koan is obsolescent and has no successor.

One day, a traveler from a faraway land sought Master Hg's guidance.  "Master Hg, I wish to alter history."

Master Hg nodded, smiling warmly.  "What you seek is easily attainable.  History is supple and easily rewritten."

Excitedly, the traveler began researching in Master Hg's veritable library and shared his work with others.  After many days, he returned.  "Master, when I tried to share my changes with my friends, as I have done in my homeland, the DAG became extremely confused and I had to re-clone the server.  Why does Mercurial not work correctly?"

Anger flashed across Master Hg's face.  "What you seek is impossible.  History is unyielding and changing it the domain of the gods."

"But mere days ago," the traveler protested, "you told me otherwise."

"I find it curious you remember events which did not occur," replied Master Hg.

The traveler stormed out angrily.  It was many hours before enlightenment struck him.

Friday, February 20, 2015

NBTParse

For quite some time, now, I've been working on a Python library called NBTParse.  It's designed to manipulate Minecraft worlds.  It's been languishing in a not-ready-for-prime-time state for the longest time, but I've finally decided to start working towards a 1.0 release.  As a motivator for that, I've begun rapid releases of 0.x.0 versions.

Each new 0.x.0 release will happen on the first Thursday of the month.  0.2.0 dropped on the 5th, but I didn't think to blog about it until now.  It can be had from PyPI under the name nbtparse (that is, you can run pip install nbtparse as usual).  If you don't have a C compiler, you may have difficulty with this.

Let's talk about the current status of the library.  It's currently very rough, with a number of serious shortcomings.  The biggest is the lack of a lighting engine.  In short, it doesn't adjust lighting information after altering the terrain.  Because of this, terrain manipulation is highly risky at the moment, with great potential to corrupt saves.  In other words, back up your saves before playing with this.  But you knew that already; it's listed as pre-alpha in PyPI, after all.  Work on the lighting engine has not seriously begun yet, so this will likely remain the case for a long time.  On the other hand, I hope to at least have heightmap updating in time for 0.3.0 (this will hopefully prevent any corruption from actually crashing Minecraft, though you'll still experience lighting errors).

Another issue is Minecraft 1.8 compatibility.  In short, there is none.  While 1.8-isms are nominally accessible, they're not particularly fun to work with right now.  Fortunately, this is mostly a matter of sitting down and writing declarative code to describe the new features.  It should be fairly straightforward once I get around to actually doing it.  I hope to have this in 0.3.0.

Finally, the API is not yet stable.  Some aspects of the library may change as we move closer to 1.0, without backwards compatibility.

Friday, September 19, 2014

The Pendulum and the Winch

I often find that explaining computer science to non-computer-scientists is difficult.  It's been said that computer science is like no other field of study.  Well, I think that's a rather strong claim to make.  What follows is a translation of a standard problem in computer science into physics.  It is an analogy, unrealistic but nevertheless interesting.

I have a pendulum, supported by some apparatus ultimately connected to a pillar or pole.  It is possible to move the apparatus up or down, but only by manually detaching and reattaching it by hand.  I have a winch affixed to this apparatus which may raise or lower the pendulum.  It is connected to a coil of rope or string (which, for the purposes of this problem, is infinitely long yet magically takes up a finite volume), and can be remotely controlled at the press of a button.  The winch is also geared discretely; it only turns in units, and then only one at a time.

I wish to carry out a series of experiments involving varying the length of my pendulum.  In particular, I often want to lengthen the pendulum.  Most of the time, this setup suits me quite well.  But sometimes, I find I need a pendulum longer than the apparatus is high off the ground.  In these situations, I need to climb the pillar and move the winch up.  In so doing, I may need to start an entire experiment over again because the pendulum lost energy while I was climbing.  How can I avoid or minimize those climbs in proportion to the maximum length of the pendulum?  We must assume I do not know the maximum length in advance, perhaps because my experiments are highly complex and difficult to predict, or perhaps because they are directed by someone else's instructions, and they did not think to tell me in advance how long a pendulum I would need.

Wednesday, August 27, 2014

The Great Picard Theorem

The great Picard theorem states that, if an analytic function contains an essential singularity, then within any punctured neighborhood of the singularity, the function takes on every value with at most a single exception.

Tuesday, July 16, 2013

Races and names in Mass Effect

I'm a pretty big fan of Mass Effect.  One thing I really like about it is the wide variety of races, differentiated in culture as well as appearance.  Turians, for instance, rarely commit crimes and will, we're told by the all-knowing codex, readily confess to any crimes which they may have committed.  Contrast this with Star Trek, whose Klingons, despite their reputation for "honor" and such, engage in back-room politicking in practically every episode featuring them.

But this isn't about Mass Effect vs Star Trek.  One of the more subtle differences between the Mass Effect races is naming.  Asari names are quite different from turian names, reflecting their greatly differing philosophies on life.  I thought I'd try to collect some rules for constructing these names.

I'm going to be using some rather technical terminology here, which I only know because I've spent some time browsing the relevant Wikipedia articles.  But, since you probably have better things to do, here's a quick reference:
Stop
t (but not th), d, k (and "hard" c), "hard" g, b, and p (there's also another stop which we don't have much in English called the glottal stop; it may be represented as an apostrophe or hyphen but there's no hard-and-fast rule).
Fricative
Lots of things; almost anything that isn't a stop or a sonorant.
Some phonemes (specifically ch and j) begin as stops and end as fricatives. 
Sonorant
All vowels including y, m, n, r (not trilled), l, and w.
These are in alphabetical order, with council races first.
  • Asari: I see lots of sonorants and some fricatives, but very few stops, and most of those are at the beginning or end of names, while the vowels often form diphthongs; this gives the words an elvish feel, which is apropos since the asari are basically space elves.  The names also have a Greek feel; the Asari Republics strongly resemble Ancient Greece, so this is hardly shocking.
  • Drell: We don't meet very many of these, so it's hard to tell.  There do appear to be relatively few fricatives, but I can't really be sure.
  • Elcor: Again, there really aren't a lot of them, but I will note that every stop is voiceless (t, k, and p) rather than voiced (g, d, and b).
  • Hanar: "Blasto" is fictional and looks out of place.  The other names seem to have few fricatives and voiceless stops.
  • Human: Basically modern names, no fancy "smash two names together to make a futuristic-sounding one" shenanigans here.
  • Keeper: Keepers don't have names.
  • Salarian: According to the Mass Effect wiki, salarian names consist of "the name of a salarian's homeworld, nation, city, district, clan name and given name," in that order.  They have a lot of fricatives and some stops.
  • Turian: A lot of turian names end in "[i]us."  Stops and fricatives are relatively plentiful, and stops tend to be voiceless rather than voiced, though this is far from universal.  The "[i]us" thing, combined with what I know of turian culture, makes it apparent that their names are meant to sound Roman.
  • Batarian: These resemble the turians, but with a more even balance of voiced and voiceless stops.
  • Collector: Collectors don't have names.
  • Geth: Geth usually take designations rather than names as-such.  The easiest way to do that is something like "Unit 1234" (side-note: 1025's assertion that the number 1025 is meaningful is bullshit; the significant numbers in that neighborhood are 1024 and 1023.  The explanation it gives is even more wrong since 210 = 1024 has 11 digits in binary, much like 1010 has 11 digits in decimal.).
  • Krogan: Krogan names are composed of a clan name (such as "Urdnot") and a personal name (such as "Wrex").  Mass Effect 3 says that krogan personal names are selected via males having belching contests.  "Bakara" doesn't sound like a belch, so I'm guessing this is only for male names.  A belch-name should consist of an optional stop followed by a series of sonorants and fricatives, possibly terminated with another stop; moreover, it will probably be monosyllabic or nearly so.  This is based on the assumption that a belch consists of a single continuous expulsion of breath; if there are stops in the middle, it isn't continuous (air stopped coming out, hence the name "stop").  "Fortack," "Okeer," and "Skarr" clearly break this rule, but the other names mostly seem consistent with it.  The latter two can be explained as someone cheating, starting to make sounds before the real belch began, but "Fortack" just doesn't seem like it could possibly occur as a belch.  Maybe someone stuck the t in afterwards.
  • Leviathan: We don't really have enough information.
  • Quarian: FirstName'LastName nar/vas ShipName.  The names tend to be monosyllabic, which makes a kind of sense since the population of any given ship is small and the ship's name can be used to disambiguate; there's no need for elaborate names.  Diphthongs are rare; the only one I can see is "Rael."
  • Raoli: We don't see any of them and I only know of them through the wiki.
  • Reaper: "Nazara" and possibly "Harbinger."  That's not enough names to generalize.
  • Virtual Alien: Uh... who are these guys?
  • Vorcha: It's hard to generalize.  Most of the galaxy regards vorcha as vermin, and pays relatively little attention to their individual names.
  • Yahg: We don't know anything about yahg names.

Monday, April 15, 2013

The tragedy of music: part three

In part one, we discussed some issues with Pythagorean tuning, and in part two we continued to quarter-comma meantone.  The logical conclusion is equal temperament, a widely used (though not quite universal) modern system.

Equal temperament is, in a way, simpler than any of the earlier systems.  Instead of building an octave out of some fixed ratio, we start with an octave and subdivide it.  The most natural way to do this is to make a semitone the twelfth root of two.  Note that this is simply "a semitone" rather than a chromatic or diatonic semitone; in equal temperament, those are the same thing.  Everything else can be built rather easily out of this fundamental unit, and we don't have overlapping or separated octaves.  This, in turn, means no wolf fifth.

Still, this fundamental unit can be unwieldy.  Writing out "the twelfth root of two" all the time is annoying, and the mathematical notation for it is rather ugly.  For this purpose, the so-called cent was invented.  There are 1200 cents in an octave; 100 make up a semitone.  It is a logarithmic unit.  Increasing a tone by 1200 cents means doubling its frequency.  700 cents make up a perfect fifth, and 400 cents are a major third.  The cent is a unit of relative measure; it is not meaningful to equate a single note to a given number of cents, except in relation to another note.  That "other note" is often middle A, which, for convenience, is typically tuned to 440 Hz.

This system is very practical, which accounts for its widespread use.  However, this is not a happy story with a happy ending; there is a problem.  The twelfth root of two is an ugly, irrational number, and all of the other intervals are powers of it.  There are no simple integer ratios at all.  While the cent may make the system look nice and clean, it is an artificial unit created to hide the irrational semitone.  In effect, we've taken the sourness of the wolf fifth and extended it over the whole octave, spreading thinly to mask the dissonance.  Practical this may be, but ideal it is not.

This leads me to a stark realization: the Platonist's ideal of "perfect yet unattainable" forms is inapplicable to music.  These problems are not of a physical nature.  Any musical system will suffer from them, except for the trivial system which has one note per octave.  There is a fundamental disconnect between equal temperament and just intonation.  We cannot have both, even in theory.  And that is the tragedy I've been talking about.

Monday, April 8, 2013

The tragedy of music, part two

In part one, we discussed Pythagorean tuning and its failings.  Despite this crucial issue, Pythagorean tuning was highly influential on musical theory.

In the 1500's, a variant of Pythagorean tuning called quarter-comma meantone became popular.  The "comma" in this name is not the Pythagorean comma we saw last time, but an entirely different comma.

A major third is an interval spanning three staff positions and four semitones.  It is not considered "perfect" in the same way as the perfect fifth, but is still regarded as a consonant interval, at least in theory.  Under Pythagorean tuning, the major third was a rather dissonant 81:64.  Quarter-comma meantone flattened this to a nicer 5:4, at the expense of a more dissonant perfect fifth.

Interestingly, we now have irrational intervals: the perfect fifth is the fourth root of 5.  This way, if we move up by four perfect fifths, and down by two octaves, we end up at 5:4, the justly-intoned major third.

This sort of trade-off is debatable, of course, but it was an explicit design goal of quarter-comma meantone; the flatter fifth was viewed as an acceptable price for a just third.

Now, suppose we start at middle C, as we did last time, and move up a major third.  We arrive at middle E at a ratio of 5:4.  Next we move up again to G♯, at a ratio of 25:16.  Finally, we get to C5, at a ratio of 125:64.  This is not an octave, but unlike in Pythagorean tuning, the interval is too flat rather than too sharp.  This means there's a gap between the octaves, unlike the overlapping octaves of Pythagorean tuning.

Like in Pythagorean tuning, one of the fifths must span this gap.  That fifth is sharpened by 128:125, a much larger interval than the Pythagorean comma.  It sounds extremely dissonant, to the point that it became known as the "wolf fifth" because it sounds like a wolf howling at the moon.  This moniker is sometimes also applied to the diminished sixth produced by Pythagorean tuning under the equivalent problem, but note that quarter-comma meantone is much worse in this regard.

Updated: In part three, we discuss modern equal temperament.

Saturday, April 6, 2013

The tragedy of music, part one

Once upon a time, people noticed that certain sounds are pleasant to hear, while others are not.  They began to experiment with it.  The most important early discovery in this vein was the notion that sound is vibration.  This is the fundamental principle of all musical theory, modern or ancient.  The next discovery was that of the octave: If you make two vibrations, one at double the frequency of the other, they sound... the same, in some way.  The faster one is clearly higher pitched, but they're harmonically equivalent.

The Ancient Greeks built upon this discovery, and eventually produced what we now call Pythagorean tuning.  Pythagorean tuning is built around simple frequency ratios; systems like this are called "just intonations."  The most important ratio other than the octave is the so-called "perfect fifth," which describes a gap of five staff positions in modern musical notation.  It spans a gap of seven semitones; there are a total of twelve semitones per octave in "conventional" systems such as Pythagorean tuning.  In Pythagorean tuning, a perfect fifth is a ratio of 3:2, meaning the faster vibration oscillates thrice for every two oscillations of the slower vibration.  So far, this is all very nice, and fits in well with the Pythagorean mathematical ideals of rationality.  But there's a problem.  I told you that a perfect fifth has a ratio of 3:2, is composed of seven semitones, twelve of which make up an octave, and the octave is 2:1.  Suppose we start at middle C (or C4), and move a perfect fifth up.  We arrive at G4, at 3:2 times our original frequency.  We continue to D5, at 9:4.  Next comes A6, at 27:8.  Then E6, at 81:16, B7, at 243:32, F♯7, at 729:64, C♯8, at 2187:128, and finally G♯8 at 6561:256.  Now suppose we go down from C4.  We find ourselves at F3 at 2:3, B♭3 at 4:9, E♭2 at 8:27, and A♭1 at 16:81.  The ratio from C4 to A♭1 is 81:16, and the ratio from G♯8 to C4 is 6561:256.  Multiplying, we see that the ratio from G♯8 to A♭1 is 531441:4096.  But A♭ and G♯ are supposed to be the same note.  Going by octaves, we should get 128:1.  The other ratio is rather large and unwieldy, because we have seven octaves of space, so if we divide those out, we get a ratio from G♯ to A♭ of precisely 531441:524288.  This interval is called the Pythagorean comma.  It's the difference (remember, in music, we never add or subtract frequencies, so this is actually the ratio) between a chromatic and a diatonic semitone, among other things.

So what does this actually mean?  It means Pythagorean octaves overlap, if only a little, since G♯ is a little sharper than A♭.  That's a problem for perfect fifths.  One of the twelve "perfect" fifths is ruined by spanning this overlap, being flattened to a rather dissonant diminished sixth.  So Pythagorean tuning, for all its beauty and simplicity, is not perfect.

Updated: In part two, we discuss quarter-comma meantone, a derivative of Pythagorean tuning.

Friday, January 18, 2013

One-time pads with Python

A one-time pad is a kind of unbreakable encryption.  For most encryption, breaking it is a matter of throwing a lot of computational resources at the problem.  Typically, the amount of resources needed greatly exceeds the amount that is practical to obtain, so most modern cryptography is secure enough.  There are, however, some downsides to modern cryptography, the biggest of which is its complexity.  If we want to use crypto for something like bank transactions, complexity is not that big of a deal, because centralization can hide most of the complexity from end-users.  But if, for instance, you need to implement secure communications without a centralized certificate authority, effectively implementing secure communications becomes a lot harder.

Saturday, July 21, 2012

SpaceChem optimization

SpaceChem is a programming video game disguised as a chemistry video game.  A static description cannot really do it justice, so here's a trailer:


Honestly, the trailer doesn't do it justice either, so maybe you should go grab the demo from Steam.  Anyway, SpaceChem has two types of puzzles: Research and Pipeline puzzles.  Research puzzles are fairly straightforward to work with because an input/output operation always takes exactly one cycle, whereas with a Pipeline puzzle, the tubes pipes can be clogged or empty, making your I/O operations block.  This means that performance problems with one reactor can affect others.  But optimization is not an all-or-nothing affair.  You need to know where to concentrate your work.  That's what this post is about.