ecmendenhall

Breadth-first numbering with a pure functional queue

My solution to Chris Okasaki's functional pearl: given a tree, reproduce a tree with the same structure with nodes numbered in breadth-first order (using only immutable data structures, of course).

For more on streams and lazy lists, check out chapter 3 of SICP. For more on pure functional queues, see this other paper by Chris Okasaki.

I'm not completely happy with my solution. On the plus side, it generalizes to non-binary trees. But performing a breadth-first search to calculate node numbers and a depth-first map to apply them is inefficient. I tried to construct my solution from the

ecmendenhall

#lang racket/base
(require rackunit)

(define simple-q '((1 2 3) (6 5 4)))

(define empty-queue '(()()))

(check-equal? empty-queue '(() ())
              "An empty queue is a list containing two empty lists.")

ecmendenhall

(ns prime-factors.core
  (:require [clojure.core.logic :refer :all])
  (:require [clojure.core.logic.fd :refer [in interval eq]]))

(defn factor-pairs [number]
  (run* [pair]
        (fresh [factor1 factor2]
               (in factor1 factor2 (interval 2 number))
               (eq (= number (* factor1 factor2)))
               (== pair [factor1 factor2]))))

ecmendenhall

(ns crypto-challenges.core
  (:require [clojure.edn :refer [read-string]]
            [clojure.string :refer [lower-case]]))

(def alphabet "ABCDEFGHIJKLMNOPQRSTUVWXYZ")

(def base64-values (str alphabet
                        (lower-case alphabet)
                        "0123456789+/"))

ecmendenhall

(describe "Converting hex to base64"

          (it "parses hex values from two-character strings"
              (should= 0x2f (parse-hex "2f")))

          (it "splits hex strings to sequences of strings"
              (should= ["00" "1a" "2b" "88"]
                       (split-hex-string "001a2b88")))

          (it "converts hex strings into sequences of hex values"

ecmendenhall

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>org.clojars.ecmendenhall</groupId>
    <artifactId>schtitt</artifactId>
    <version>0.9.2.1-SNAPSHOT</version>
    <description>A very simple HTTP server.</description>

ecmendenhall

(ns my-great-project.core-spec
  (:require [speclj.core :refer :all]
            [simple-check.core :as sc]
            [simple-check.generators :as gen]
            [simple-check.properties :as prop]
            [my-great-project.core :refer :all]))

(defmacro check-that [desc n property]
  `(it ~desc
     (let [check#  (sc/quick-check ~n ~property)

ecmendenhall

(ns primes.core)

(defn trial-division [n divisor factors]
  (if (< n 2)
    factors
    (if (= 0 (mod n divisor))
      (recur (/ n divisor) divisor (conj factors divisor))
      (recur n (inc divisor) factors))))

(defn prime-factors [n]

ecmendenhall

alias doge=cat
alias much=less
alias so=grep
alias wow=ls
alias such=cat
alias very=cd
alias plz=vim
alias halp="head -n 7 $( cd "$( dirname "${BASH_SOURCE[0]}" )" && pwd )/.dogerc"

ecmendenhall

nsad

A tool to disable OS X kernel extensions, based on the NSA guide to protecting yourself from the NSA.

To run on startup:

$ mv nsad /usr/local/bin
$ mv com.cmendenhall.nsad.plist /System/Library/LaunchDaemons