adb: (Default)

Having lived in Boston for around 30 years, I've noticed now and then that many people there are confused about what a city is. Since every two-bit hamlet in New England that has outgrown the "town meeting" system of government sees fit to call itself a city, this is understandable.

city, n.: a more-or-less contiguous region served by a 24-hour public transit system and possessing at least one walkable district containing 24-hour restaurants, food markets, bars, and coffee shops

New York, London, Tokyo; Chicago, Seattle, even (as I'm discovering) New Orleans: these are cities; Boston, by contrast, is an agglomeration of college towns. Boston hasn't yet even managed to annex most of its major neighborhoods: if it were a city, Brookline, Cambridge, and Somerville would all be part of it for sure, as probably would Malden, Revere, Arlington, Medford, Dedham, Chelsea, Waltham, and so on. As it is, not a single subway line stays within the "city".

Since Boston has abdicated its seemingly natural leadership role in the region, there is something of a power vacuum crying to be filled. Of the various neighborhoods served by subway lines and calling themselves "city", I continue to believe that Somerville has the strongest natural claim, not least because we are free of major ties to any of the local degree-granting institutions, allowing us to act as a neutral arbiter rather than a captive government like our neighbors to the north and south. Write to your mayor, councillor, or selectbeing today and tell them you want to merge with Somerville.

Car

Oct. 25th, 2010 10:22 am
adb: (Default)
So I spent the last 5 weekends fixing the car (with much help from the Miss and the patience of my family, whose garage I left it in). It's finally done: I drove it home and no fluids are coming out that weren't before.

I set out to change the timing belt (which was fine, but per mileage was due for a change) and the crankcase breather tube (which was shattered into a million pieces, leaving the engine stinking of burning oil and plastic). Because most of the trouble in changing the timing belt is getting at it, and you get at a lot of other things along the way, we added on a lot of "while you're in there"s: the serpentine belt, the power steering belt, the AC condenser belt, the water pump, and the water pump thermostat.

Where the weekends went, to the best of my recollection:

1. Taking stuff off (bumper, AC condenser, radiator, radiator support (the thing with headlights on it), various tubes and covers and air guides); unsticking stuck bolt #1. Decided not to fix the breather tube this time because it was inaccessible without removing the intake manifold, which we could do later.
2. Taking stuff off (old belts, viscous fan clutch, old water pump and thermostat); unsticking stuck bolts #2 and #3, including removing the water pump housing, which was a much bigger pain than the water pump per se.
3. Putting the water pump housing and water pump back in. Fixed the breather tube after all because we found that it was accessible after getting the water pump housing out of the way.
4. Actual belt changes, closing up, water pump thermostat installation.
5. More closing up, redoing the thermostat installation because coolant was leaking out because I had used Allen-head bolts instead of big fat hex bolts tightened with a torque wrench.

All of this together really ads up to a long day of work; but for each hour of that day, I added on maybe

- 2 hours of being lazy in the mornings because I didn't want to deal with this crap
- 2 hours of commuting to my parents' house
- 2 hours of research/"learning experience"
- 2 hours of tool/hardware shopping (e.g., various kinds of bolt extractors, a torque wrench, stainless steel bolts; much slower on a Sunday than, say, on a weekday).

On the bright side, I now have the knowledge and tools acquired during the course of all this pain, and the confidence and muscle memories allowing me to proceed faster next time.

Automotive enthusiasts will notice I did nothing to the engine per se, just stuff that bolts on to the engine.
adb: (Default)
For philosophical and zombie-apocalypse-preparedness reasons, one ought to understand one's essential tools well enough to fix them. Consequently, the Miss and I have undertaken to change the timing belt on our car, and while we're in there also change the water pump and thermostat and the serpentine and power steering belts.

What is supposed to happen goes like this. Now, I'm not a seasoned mechanic or anything, but a Certain Incident a few years back1 and some electrical work on my motorcycle have served to set firmly in my mind the idea that vehicle manufacturers and mechanics are lazy cheap bastards.

If you skim over the instructions, you will find that they actually seem like a pretty reasonable undertaking: take this off, take that off, etc., until you're at the bottom, then put this on, put that on, etc. until the car is back together. If you're enough of a nerd to have put together your own computer at some point, this basically seems like that except with more tools, more physical effort, and more fluids; and despite prior experience, that is more or less the attitude with which I went into this.

Looking over the instructions, I figured we could do it in 4 hours if we had enough hands and did everything right and encountered no trouble. So 8 hours in the real world, right?

Right? )

Moral: friends don't let friends abuse threaded fasteners.

footnotes! )
adb: (Default)
Pursuant to the previous entry (deliberately omitting some keywords), today I wrote a thing to find the nth permutation of a list in lexicographic order. I started by thinking about how to enumerate all the permutations. In Knuth's fascicle on the topic (7.2.1.2), there's a multiparagraph description of a procedural algorithm, and it feels really clunky, as procedural algorithms often do. Trying to squeeze this into Haskell (or indeed write it at all) hurt my brain until I took a moment to experiment with a naive recursive approach, which was correct immediately and didn't hurt at all.

First, some utility functions. Given a list, the "breaks" function does a break at each possible place, and the "plucks" function uses that to shove each possible element to the front of the list in order.
import List
breaks list = zip (inits list) (tails list)
plucks      = map (\(a,(b:bs)) -> (b:a++bs)) . filter (not.null.snd) . breaks

Once we have plucks, the recursive permutation generator is (almost) a one-liner:
lexPerm [] = [[]]
lexPerm list = concatMap (\(a:as) -> map (a:) $ lexPerm as) $ plucks list

nthLexPermNaive list n = (lexPerm list) !! n

(With "nth" counting from 0, of course.) For purposes of the problem at hand, this is plenty fast enough: I'm supposed to solve the problem in a minute, and I can get the millionth permutation in 10 seconds on my Mac. But 10 seconds is on the order of 10 billion operations with today's computers, which makes that pretty cheesy in the absolute sense, so I took a walk to grab some coffee and thought about it.

Of course we don't have to create the Library of Babel; we just want to index it. (Literally) exponentially better is, rather than generating all the permutations before the one we want, counting our way down to it:

facs              = scanl (*) 1 [1..]
nthLexPerm []   _ = []
nthLexPerm list n = (a : nthLexPerm as r) where                       
                       (q, r) = divMod n $ facs !! (length list - 1)
                       (a:as) = (plucks list) !! (fromIntegral q)

That is, we divide the permutations into buckets according to which list element goes first, count the size of the buckets with the factorial function, and figure out which bucket n is in; that tells us which list element is first (or next), and then we do it again with the rest of the list.

Here any reasonable-sized problem is done in a quarter of a second, and we can find the 2913-digit random number )th permutation of the first paragraph of Moby-Dick in two seconds.

(If we wanted to permute the whole text of Moby-Dick, this might run into trouble: in the process of figuring out the first letter, we have to spend at least quadratic time computing the factorial of the length of the remaining part of the list. For the earlier permutations, we could trim this down a bit by doing the factorial mod n.)
adb: (Default)
I'm currently spending my spare nerd time on Project Euler, a series of math exercises. The neat thing about them is that they don't require any math knowledge beyond what is taught in middle school in the US, nor do they require any programming knowledge beyond the willingness to experiment.

I've really appreciated Haskell in the course of this effort: for many of the Euler problems, you can just describe the problem recursively and Haskell will solve it for you; the only effort is looking up what you want in the "dictionary" (e.g., to discover that "nub" is Haskell for "uniq", and "words" Haskell for "split") and figuring out how you misdescribed the corner cases of the algorithm.

It would be nice, though, if there were a language where something this simple:

sum $ zipWith (*) (map (sum . catMaybes . map ((flip elemIndex) letters)) names) [0..]

didn't involve obnoxious quirks like:

- dollars signs for precedence
- "elemIndex": there should be either sugar or a nicer name for something this basic
- "flip": this is only here because elemIndex takes its arguments in the wrong order
- "Maybe" is a substitute for being able to put "nil" in place of anything and having stuff throw an exception if it doesn't like it. When hacking, I want the latter behavior, and the latter behavior is what is familiar from every dynamic language in the universe.
- Though you don't see it here, there is a separate zipWith for every arity. Haskell fans will defend this behavior to your face, with every appearance of sincerity.

That's a lot of quirks for one line, but then again, Haskell is a pretty dense language.

(Seriously, I blasted through a lot of these problems in way less time than it would have taken in a less declarative language. But seriously, it badly needs the warts planed off and the name changed so enough users will use it that it will get enough libraries that enough users will be able to use it to make it good.)
adb: (Default)
I'm posting to dreamWIDTH in hand-built OS X Chromium while taking a break from hacking Haskell!

Somebody get a tourniquet. You know, for the edge. Because it's bleeding.

A thing I'm noticing in Haskell is that it is badly short of whipuptitude. I ditched Perl a long time ago because Ruby had pulled ahead of it in that respect. Haskell is great for manipulexity, but it fails at whipuptitude for exactly one reason, which is the IO monad. If you walk up to Haskell with a simple task (say, writing "du", so that you can later develop a massively parallel memoizing map/foldr-based extension of du for efficient filesystem accounting on heterogenous multi-petabyte storage systems), you're inevitably going to run into the fact that all interacting with the world outside your program (e.g., the filesystem, the user) goes through the IO monad, and so you have to either borrow some cargo-cult gibberish and hope it works or sit down for a serious grokking session to internalize this particular paradigm shift for real, and in the meantime, you're not Getting Things Done.

I thought strong types were going to piss me off, but it's true, they're implicit until you need them not to be, and so I have learned to love Haskell's type system. IO, though, I haven't learned to love; I have just learned to get it out of my way as quickly as possible.

Languages shouldn't hurt.

Profile

adb: (Default)
Aaron D. Ball

December 2010

S M T W T F S
   1234
567891011
12131415161718
192021 22232425
262728293031 

Syndicate

RSS Atom

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 20th, 2017 11:14 am
Powered by Dreamwidth Studios