What's it all about, Alfie?

This morning I was looking into yet another Adium problem with MSN Live, and I opened up the Console.app and noticed a lot of messages like this:

  12/18/14 4:08:22.886 AM com.apple.xpc.launchd[1]:
    (homebrew.mxcl.postgresql[52026]) Service exited with abnormal code: 1

and when I tried to check if Postgres was running:

  $ psql -l
  psql: could not connect to server: No such file or directory
          Is the server running locally and accepting
          connections on Unix domain socket "/tmp/.s.PGSQL.5432"?

so it was clear that something was wrong with postgres on my laptop.

To be fair, I haven't really messed with this since going to Yosemite, so I hit DuckDuckGo and it reported this post on StackOverflow, which says that in the Yosemite upgrade, several empty directories were deleted, and all I needed to do was to re-create them and restart postgres.

So I:

  $ launchctl unload ~/Library/LaunchAgents/homebrew.mxcl.postgresql.plist
  $ cd /usr/local/var/postgres
  $ mkdir pg_tblspc
  $ mkdir pg_twophase
  $ mkdir pg_stat_tmp
  $ chmod 700 pg_tblspc pg_twophase pg_stat_tmp
  $ launchctl load ~/Library/LaunchAgents/homebrew.mxcl.postgresql.plist

and then I could see all the databases on the laptop, and the Console.app showed that things were running just fine.

While I understand that postgres is inefficient as it's running all the time, I still love this database, and it's worth the cycles to have it on my development laptop because it scales to the server room so bloody well.

Problem solved. Whew!

I was talking with my friend today, and he pointed out that the size of the word sets were much smaller when you grouped them by their character pattern as opposed to just their length. The thought is that a significant portion of the execution time is in the filtering of the list of possible words - based solely on their length, and if you can group the possible words by their pattern, then they all have to pass that criteria, and you can skip the filtering.

The code to compute this character pattern isn't all that clear, but it's very effective:

  (defn pattern
    "Function to take a word (as a string) and return a vector that is the
    pattern of that word where the values are the index of the character.
 
      => (pattern \"see\")
        [0 1 1]
      => (pattern \"rabbit\")
        [0 1 2 2 3 4]
    "
    [word]
    (loop [p [] d {} n 0 f (first word) r (rest word)]
      (if f
        (if (contains? d f)
          (recur (conj p (d f)) d n (first r) (rest r))
          (recur (conj p n) (assoc d f n) (inc n) (first r) (rest r)))
        p)))

and then we simply change how the words are organized, from:

  (def words
    "This is the map of all known plaintext words - organized by the length
    of the word to speed up the matching process. The result is a map where
    the key is the length, and the value is a sequence of words."
    (->> (slurp "resources/words")
         (.split #"\n")
         (group-by count)))

to:

  (def words
    "This is the map of all known plaintext words - organized by the length
    of the word to speed up the matching process. The result is a map where
    the key is the length, and the value is a sequence of words."
    (->> (slurp "resources/words")
         (.split #"\n")
         (group-by pattern)))

at this point, we don't need to filter the word list by the pattern because we have already done this - so let's remove that as well.

At this point, the words are grouped by their pattern and not just the length. The difference in the times is really profound:

  [13:01:16.677:main] INFO  cq.block - Finished match-up [8 words] in 39ms.
  [13:01:16.687:main] INFO  cq.block - Finished solve in 49ms.

becomes:

  [13:45:46.967:main] INFO  cq.block - Finished match-up [8 words] in 0ms.
  [13:45:46.981:main] INFO  cq.block - Finished solve in 14ms.

We have simply removed the single most expensive part of the solution, and we get the same solution. Very nice. Very.

UPDATE: I came up with a simpler implementation of pattern that - at least to me - seems to be a lot easier to follow. You make a map of the characters and their position and then uses that as the function on the word itself:

  (defn pattern
    "Function to take a word (as a string) and return a vector that is the
    pattern of that word where the values are the index of the character.
 
      => (pattern \"see\")
        [0 1 1]
      => (pattern \"rabbit\")
        [0 1 2 2 3 4]
    "
    [word]
    (mapv (into {} (map vector (distinct word) (range))) word))

It turns out that this is also a little faster. We're down to 11 msec. Nice!

Carl and I have been talking about this idea for applied machine learning for analyzing Salesforce.com data, and now that I know what is going to happen to me with the new job, I told him in chat that I'd be glad to build him a proof-of-concept for the task. I know he has test data, and he has the algorithms, and what he needs is something to prove that this will work at scale. Sounds like fun.

I'm not at all sure what the algorithms look like, but it's all in Python code, and he's online so I can ask him as I build this - and I don't have to integrate it with Salesforce.com - I just need to hammer out the code into a decent clojure project that can perform the requested analytics on the data and come up with the "right" answers.

This isn't all that different from the CryptoQuip work I've been doing. I really like this stuff. Clojure makes it so easy to piece stuff together, and with the REPL and all that, it's just amazing how nice it is. So it'll be a nice diversion for a while and then maybe a few weekends and then who knows?

I was just looking at my Dropbox usage, and realized that the menu drop-down had actual thumbnails of the images that were uploaded to Dropbox! What a slick trick! I'm sure this is not new, but it's new to me, and while I don't have a huge amount of data on Dropbox, I have been using it for a long time, and when the free space runs out, I will certainly be a paying customer. It's just an amazing tool, and it's been integrated with a lot of really nice apps - like Glui and VoodooPad.

It's when apps add features that sneak up on me that I'm really happy. Getting a new app, you kind of expect it to have the functionality you're getting. But to have an existing app add nice features is really a little bit of joy.

Very nice, Dropbox! Very nice.

While it's no GitHub, I've been working with Bitbucket for a few projects with a friend, and I have to say it's not bad at all. I happen to like the helpful hints GitHub offers on making a new repo, but the help Bitbucket has is very fair, and reasonable. It's got a little different UI, which is fine, and it works pretty much the same so that you don't have to come up to speed with a new workflow if you're switching back and forth from Bitbucket to GitHub.

I looked at Bitbucket a long time ago, and it wasn't nearly as similar to GitHub as it is now, and that makes a lot of sense. It's got Pull Requests, and it's got a very nice source view:

Many will say It's just like GitHub's - which is a good thing. Face it - you copy what's a great design and works well. This is one of those cases.

The thing I like about Bitbucket is the free repos for small teams - up to 5 people. In short, they have a different approach than GitHub - repos are free, people are charged. It's a nice approach because it means that non-Open Source projects that you work on with a friend can be private without a cost. GitHub charges for the first private repo, and I don't begrudge them that - I'm a paying GitHub user. But I like the different approach because it gives small groups a leg up.

I'm not going to stop using GitHub, but it's nice to see that Bitbucket exists and seems every bit as good as GitHub for the task. It's something I'll remember.

Well... I just pushed the commits that added the web server to the CryptoQuip repo with my friend. I have been able to get the speed down to that of the Obj-C code, and it was really interesting to me where the hold-up was. I needed to add some logging with timings so that I could get performance numbers for changes as I ran them over and over. But what I found was that the real bottleneck was in the possible? predicate function that was being used to filter the possible words to those that matched the pattern of each cypherword.

What I needed to do was to switch to pmap to make it efficient on getting the matches:

  (defn possible?
    "Function to see if the cyphertext and plaintext have the same pattern of
    characters such that they could possibly match - given the right legend."
    [ct pt]
    (if (and (string? ct) (string? pt) (= (count ct) (count pt)))
      (let [ctc (count (distinct ct))
            ptc (count (distinct pt))]
        (if (= ctc ptc)
          (= (count (distinct (map str ct pt))) ctc)
          false))
      false))

where I now look at the (distinct) length of the cypher and plaintext before making the map of pairs and counting them. This saves a good bit, but the biggie was in breaking out the creation of the possibles sequence:

  (defn match-up
    "Function to create a sequence of all the cypherwords and the possible
    matches to it in a way that we can easily time this for performance
    tuning."
    [quip]
    (let [qw (vec (distinct (.split quip " ")))
          go (fn [cw] (let [poss (filter #(possible? cw %) (get words (count cw)))]
                        { :cyphertext cw
                          :possibles poss
                          :hits (count poss) }))]
      (sort-by :hits < (pmap go qw))))
 
  (log-execution-time! match-up
    {:msg-fn (fn [ret q] (format "%s words filtered" (count ret)))})

Here, the biggie is splitting up the matching using pmap to make sure that we work on this matching problem as fast as possible. It's all still very functional, as the source lists are immutable, and it's a simple filtering problem.

With this, we're in the 65 msec range for the solution, and that's about where the ARC-based Obj-C code was, and that's pretty nice.

This morning I saw that I got an offer letter from one of the shops I have been interviewing with and it was pretty much exactly what I'd heard from the CTO last night on a phone call. I have to say that I'm pretty impressed with the speed of getting the letter out. I told him there was no rush, but they got it done right away. Nice touch.

I've sent an email to another of the companies I talked to to inform them that I'd gotten the letter. Just to let them know that I'd need to know within a few days if they were interested. Just a courtesy email. I don't expect anything from them, but it's what Ive been told is polite. And I want to be polite. They have all been very nice in this interview cycle.

It looks like I'll have a restful Christmas break and then get to the new job at the first of the year. New chapter in life and new job. Not bad.

This morning I finished up a different implementation of the CryptoQuip solver that I've been migrating from Obj-C to ruby - and now to clojure. A friend has already done a port of the logic, but he made slightly different implementation scheme, and therefore a different execution profile. This is a lot more along the lines of the the Obj-C and ruby ports, just in clojure.

What really impressed me what the exceptionally tight implementation of the functions in clojure. For the most part, the code is about the size of the ruby code, except where it comes to the reentrant attack code. There, clojure is once again, just amazing. The ruby looks like this:

  # This is the recursive entry point for attempting the "Word Block" attack
  # on the cyphertext starting at the 'index'th word in the quip. The idea is
  # that we start with the provided legend, and then for each plaintext word
  # in the 'index'ed cypherword that matches the legend, we add those keys not
  # in the legend, but supplied by the plaintext to the legend, and then try
  # the next cypherword in the same manner.
  #
  # If this attack results in a successful decoding of the cyphertext, this
  # method will return true, otherwise, it will return false.
  def do_word_block_attack(idx, key)
    p = @pieces[idx]
    cw = p.cypherword
    p.possibles.each do |pt|
      have_solution = false;
      if cw.can_match?(pt, key)
        # good! Now let's see if we are all done with all the words
        if (idx == @pieces.count - 1)
          # make sure we can really decode the last word
          if key.incorporate_mapping(cw.cyphertext, pt)
            # if it's good, add the solution to the list
            if (dec = key.decode(@cyphertext))
              @solutions << dec
              have_solution = true
            end
          end
        else
          # OK, we had a match but we have more cypherwords
          # to check. So, copy the legend, add in the assumed
          # values from the plaintext, and move to the next
          next_key = key.clone
          if next_key.incorporate_mapping(cw.cyphertext, pt)
            have_solution = do_word_block_attack(idx + 1, next_key)
          end
        end
      end
      # if we have any solutions - stop
      break if have_solution
    end
    @solutions.count > 0
  end
end

and the clojure code looks like:

  (defn attack
    "Function to do the block attack on the quip, broken down into a sequence
    of the cyphertext words, and their lists of possible plaintext words, as
    well as the index in that sequence to attack, and the clue (legend) to use.
    This will return the first match to the attack and that's it."
    [quip pieces idx clue]
    (if (and (coll? pieces) (map? clue))
      (let [{cw :cyphertext poss :possibles} (nth pieces idx)
            last? (= idx (dec (count pieces)))]
        (some identity (for [pt poss
                             :when (matches? clue cw pt)
                             :let [nc (merge-clue clue cw pt)]
                             :when nc]
                         (if last?
                           (decode nc quip)
                           (attack quip pieces (inc idx) nc)))))))

which is just amazingly simple and easy to follow.

The execution times don't beat those that my friend's code, but maybe it's due to loading, or maybe he'll be able to find something in the performance I missed. But you just can't beat the simplicity of the clojure code.

Just amazing!

Today my daughter and I went to BestBuy to get a few things - and among them was the Sonos system for the house. I've been looking at this for a long time, and even gone to the store on at least three occasions to get them, but then walked out of the store without a thing. I just didn't see it as a need. Then I saw her putting together her IKEA furniture listening to some tunes from her phone. I knew this was pretty standard for my kids, but still... it was just a little silly when we can make the house be filled with the sound from the same phone.

So we got them. She's got a Play:1 for her room, and a Play:3 for the living area downstairs. I got a Play:5 for the living room upstairs, and a Play:3 for the kitchen, and finally a Play:1 for the office. She gets to control all the sound downstairs, and I can control it upstairs. It's really amazingly impressive.

The sound fills the house, and as you walk around from room to room the sound appears to already be there - well... because it is! There's no "walking away" from the music, and it's not too loud in any room - as you can control the speakers independently. This is just exactly what I was hoping for.

The set-up could not have been easier. Set up the base unit - a "Boost" unit - connected to the router, and then just go around plugging in one speaker at a time, and hitting a few buttons on the iPhone (or Android) app and on the speaker to register each one, and then it's all done. I was a little worried that this would require something on my Mac, but not so - just an iPhone will do nicely.

Now I am able to stream music and it's honestly a little better than the AirPlay from Apple, as I've had drop-outs there, but have experienced nothing like that with Sonos. Very cool. And it's just in time to be playing all my Christmas favorites!

As I didn't have a lot to do this afternoon, I decided to check on the state of X11 on OS X 10.10.1 - and it's actually not bad at all. I was able to get Quartz 2.7.7 from the download site, and it installed easily enough. All the normal things run, and it's a complete X11 we just need the apps - or in the case of SSH access, getting to a linux machine for the X11 apps on the remote host.

Because I got rid of my home machines with X11 a while back, I'm not sure how much this is going to get used any more, but it's nice to know that it works before I really need it, so that I know I can go to it in a time of need.