Skip to content

Miscellaneous Fun Things from Week 7 of Hacker School

2013 July 28
by Richard Harrington

I wrote a previous post about what I spent the majority of Week 7 doing — working on the Robotwar project — but here’s a couple more items, in the interest of giving people an idea of all the little things that go on there:

  • Pairing on an implementation of Conway’s Game of Life in Clojure with fellow Hacker Schooler Jimmy Li on Thursday. The main algorithm was twelve lines of code, and probably could be a bit shorter. Compare that to the JavaScript version I made a couple years ago, which is about two hundred. Most of that discrepancy can be attributed to a general increase in my programming ability without respect to any specific language, but a fair bit is due to the elegance of Clojure itself. I’m really starting to like that language.
  • A back-and-forth e-mail exchange over the weekend between fellow Hacker Schooler Sebastian Bauersfeld and myself over what is the best algorithm in Clojure to generate the powerset of a set, that is, the set of all subsets of that set (including the full set itself and the empty set). My first version was quite clever but somewhat convoluted and, it turned out, totally wrong — it only worked for sets of three items or less, which is all I had tested it on:

    (defn powerset [s]
      (let [range-len (range (count s))]
        (set (for [rot range-len
                   n range-len
                   sub-seq (split-at n (apply concat (reverse (split-at rot (seq s)))))]
               (set sub-seq)))))

    Sebastian’s was better — instead of doing weird stuff with rotation and splitting sets into two pieces as above, it had the correct idea, which was to progressively fold each element of the original set into the growing list of subsets:

    (defn powerset [s]
      (if (empty? s)
        #{s}
        (let [e (first s)
              power-e (powerset (disj s e))]
          (clojure.set/union
            power-e
            (set (map #(conj % e) power-e))))))

    But then he showed me this one that he found on the internets:

    (defn power-set [s]
      (reduce (fn [ss x] 
                (concat ss (map #(conj % x) ss))) 
              [#{}] 
              s))

    which put us both to shame. Actually, Sebastian’s was pretty close — it just used direct recursion instead of the `reduce` function. Mine was very far off.

    But that last one is so simple! So short! So obvious in retrospect! (although, to be fair, it returns a sequence, not a set, but making it return a set would just require one more function call).

    Sometimes I feel as though I have a mountain of things to learn, but then I’ll see that I was able to figure out how this guy’s powerset function works almost immediately, which I would NOT have been able to do a month ago. So although I don’t always see it day to day, occasionally I see inklings of the possibility that I will look back on this summer and realize that I learned an enormous amount.

Leave a Reply

Note: You may use basic HTML in your comments. Your email address will not be published.

Subscribe to this comment feed via RSS