Advent of Code: Not Quite Lisp

This post is written as a set of Literate Commits. The goal of this style is to show you how this program came together from beginning to end.

Each commit in the project is represented by a section of the article. Click each section's header to see the commit on Github, or check out the repository and follow along.

Written by Pete Corey on Aug 17, 2016.

Christmas in August

Today’s an exciting day! We’ll be tackling an entirely new set of code katas using an entirely different language! We’ll be working on the first challenge in the Advent of Code series.

In the same vein as one of our recent posts, we’ll be using the Elixir language to solve this challenge.

This first commit is the result of mix new advent_of_code_01 and creates a base Elixir project.

config/config.exs

+use Mix.Config

lib/advent_of_code_01.ex

+defmodule AdventOfCode01 do +end

mix.exs

+defmodule AdventOfCode01.Mixfile do + use Mix.Project + + def project do + [app: :advent_of_code_01, + version: "0.1.0", + elixir: "~> 1.3", + build_embedded: Mix.env == :prod, + start_permanent: Mix.env == :prod, + deps: deps()] + end + + def application do + [applications: [:logger]] + end + + defp deps do + [] + end +end

test/advent_of_code_01_test.exs

+defmodule AdventOfCode01Test do + use ExUnit.Case + doctest AdventOfCode01 + + test "the truth" do + assert 1 + 1 == 2 + end +end

test/test_helper.exs

+ExUnit.start()

Watching Tests

Out of the box, Elixir comes with a fantastic unit testing framework. ExUnit can be run against our current project by running the mix test command. Unfortunately, this runs the test suite one time and quits. It doesn’t watch our project and rerun our suite when it detects changes.

Thankfully, the mix_test_watch dependency does exactly that. We can add it to our project, and run the mix test.watch command. Our test suite will rerun on every file change.

Now that our test suite is up and running, we’ll remove the example test Elixir provided for us.

mix.exs

... defp deps do - [] + [ + {:mix_test_watch, "~> 0.2", only: :dev} + ] end

test/advent_of_code_01_test.exs

... doctest AdventOfCode01 - - test "the truth" do - assert 1 + 1 == 2 - end end

Our First Test

To get things going, let’s write the simplest test we can think of. Amazingly, tests for Elixir functions can be written within the documentation for the function itself. For example, we can write our first test like this:


iex> AdventOfCode01.which_floor "("
1

Elixir will tease these tests out of the function docs and run them as part of our test suite.

We can make this first test pass by simply returning 1 from our new which_floor function:


def which_floor(directions) do
  1
end

And with that, our test suite flips back to green.

lib/advent_of_code_01.ex

defmodule AdventOfCode01 do + + @doc """ + Determines which floor Santa will end up on. + + ## Examples + + iex> AdventOfCode01.which_floor "(" + 1 + + """ + def which_floor(directions) do + 1 + end + end

Jumping Forward

Our next test is slightly more complicated:


iex> AdventOfCode01.which_floor "(("
2

Normally, we might take a bit more time to flesh out more naive, intemediary solutions, but this is a fairly easy problem to solve. We want to split our directions string into its component characters, map those characters into numbers (1 in this case), and then sum the result:


directions
|> String.split("", trim: true)
|> Enum.map(&handle_direction/1)
|> Enum.sum()

Our handle_direction private function expects to recieve a "(" as its input and always returns a 1:


defp handle_direction("("), do: 1

With those changes, our suite returns to green.

lib/advent_of_code_01.ex

... + iex> AdventOfCode01.which_floor "((" + 2 + """ def which_floor(directions) do - 1 + directions + |> String.split("", trim: true) + |> Enum.map(&handle_direction/1) + |> Enum.sum() end + defp handle_direction("("), do: 1 + end

Handling All Matches

Let’s add one last test that excercises the ability to process “down” directions:


iex> AdventOfCode01.which_floor("()(")
1

After adding this test, our suite fails. It complains that it can’t find a “function clause matching in AdventOfCode01.handle_direction/1”.

This is because we’re only handling “up” directions ("(") in the handle_direction function:


defp handle_direction("("), do: 1

Let’s add a new match for “down” directions:


defp handle_direction(")"), do: -1

After adding that new function definition to our module, our tests flip back to green. Victory!

lib/advent_of_code_01.ex

... + iex> AdventOfCode01.which_floor "()(" + 1 + """ ... defp handle_direction("("), do: 1 + defp handle_direction(")"), do: -1

Final Thoughts

Elixir is a beautiful language with lots of exciting features. In this example, we got a taste of transformation pipelines and how pattern matching can be used to write expressive control flow structures.

The first class treatment of documentation and testing is a welcome surprise coming from an ecosystem where testing seems to be an afterthought.

Around here we’re big fans of using small practice problems and code katas to learn new languages and paradigms. Expect to see Elixir making appearances in upcoming Literate Commit posts!

Meteor in Front, Phoenix in Back - Part 1

Written by Pete Corey on Aug 15, 2016.

If you follow me on Twitter, it’s probably not surprise that I’ve been interested in Elixir and the Phoenix Framework for quite a while now. Coming from a Node.js and Meteor background, the promises of out-of-the-box reliability and scalability are incredibly attractive.

To get my feet wet, I decided to use Phoenix to build out a back-end for a simple Meteor example app.

Let’s put on our mad scientist hats and build a “Franken-stack”. We’ll be tearing the front-end out of an existing Meteor application, dropping it into a new Phoenix application, rewriting a Blaze template to use Phoenix Channels instead of DDP, and then writing a simple replacement back-end in Elixir.

Let’s get started!

Building Leaderboard

The Meteor example application we’ll be using is Leaderboard. It’s a very simple application that updates a single collection over DDP. The lack of moving parts makes it an ideal candidate for this kind of experimentation.

Let’s clone Leaderboard onto our machine and run it:


git clone https://github.com/meteor/leaderboard ~/leaderboard
cd ~/leaderboard
meteor

Fantastic! Meteor has built our Leaderboard application an moved the final build bundle into ~/leaderboard/.meteor/local/build. We’ll work more with that later.

Creating Phoenix Leaderboard

Now we need to create our new Phoenix project. Unsurprisingly, we’ll be calling this new app “Phoenix Leaderboard”. Let’s use Mix to create our application:


cd ~
mix phoenix.new phoenix_leaderboard
cd ~/phoenix_leaderboard
mix ecto.create

I’ll assume that you have a very basic understanding of a Phoenix project’s structure. If you don’t, check out the official guides for a quick introduction.

Now that we have our Phoenix project, we can start up our Phoenix server:


mix phoenix.server

Navigating to http://localhost:4000 should bring you to a “Welcome to Phoenix!” page.

Front-end Transplant

Now that we’ve laid our groundwork, we can move onto the more interesting bits of this experiment. Let’s get to work transplanting our Meteor front-end into our newly created Phoenix application.

Within our ~/leaderboard/.meteor/local/build/programs folder, our Meteor application’s font-end and back-end components are separated into the web.browser and server folders respectively.

Transplanting the front-end is really just a matter of copying over all of the required files within web.browser into our Phoenix application.

From web.browser, we’ll need the merged-stylesheets.css file, the entire app folder, and the entire packages folder. Let’s copy all of these into ~/phoenix_leaderboard/priv/static:


cp merged-stylesheets.css ~/phoenix_leaderboard/priv/static/
cp -r app ~/phoenix_leaderboard/priv/static/
cp -r packages ~/phoenix_leaderboard/priv/static/

Now we need to tell our Phoenix server that these files can be served as static assets. Let’s open up our lib/phoenix_leaderboard/endpoint.ex file and add them to our Plug.Static plug:


  plug Plug.Static,
    at: "/", from: :phoenix_leaderboard, gzip: false,
    only: ~w(app packages merged-stylesheets.css css js)

The last step of this transplant is to copy over the final HTML generated by our Meteor application. Head over to view-source:http://localhost:4000/ and copy the contents of this page into web/templates/layout/app.html.eex, replacing whatever’s already there.

That’s it!

After restarting our Phoenix server and navigating to http://localhost:4000/, we should see the (playerless) Leaderboard application!

Leveraging Brunch

Now that we’ve successfully transplanted out Meteor front-end into our Phoenix application, our next step is to wire it up to our server and start passing data.

To do this, we’re going to make some minor changes to the leaderboard Blaze template.

We’re going to be writing ES6 in this project, so we’ll want this transpiled into standard ES5-style Javascript. We can use Brunch, Phoenix’s default asset pipeline, to do this for us.

To leverage Brunch, I’m going to move the contents of priv/static/app/leaderboard.js into web/static/js/app.js, overwriting the current contents of app.js. Brunch watches web/static/js/* for changes and runs them through Babel, UglifyJS, etc… before moving it to priv/static/js/app.js.

Next, I’ll remove the self-executing function wrapper around the Blaze Template code, and import Phoenix’s socket module. Our new app.js should look something like this:


import socket from "./socket";

const Players = new Mongo.Collection("players");

Template.leaderboard.helpers({
  ...

Now we’ll change our app.html.eex file to pull in /js/app.js instead of /app/template.js:


<script src='<%= static_path(@conn, "/js/app.js") %>'></script>

Now that we’ve made these changes, we should still be able to load our new Leaderboard application without any problems.

Connecting to Channels

Now that we can freely change our leaderboard template, let’s remove our dependence on DDP and fetch player data from a Phoenix Channel instead.

Our plan of attack is to subscribe to a Channel when the leaderboard template is created and upsert any published players into our client-side Players Minimongo collection. By leveraging Minimongo, we won’t have to make any changes to our existing Meteor-style template functionality.

Let’s add an onCreated handler to our leaderboard Blaze template:


Template.leaderboard.onCreated(function() {
  this.channel = socket.channel("players");
  this.channel.join()
    .receive("ok", players => {
      players.map(player => Players.upsert(player.id, player));
    })
    .receive("error", e => console.log("Unable to join", e));
});

We’re opening a connection to a "players" Channel, and on successfully joining, we’re upserting all of the players we receive from the server into our local Players collection.

To make this work, we need to add a "players" Channel on our server.


By default, Phoenix creates a socket handler for us called PhoenixLeaderboard.UserSocket (web/channels/user_socket.ex). Here, we can define our "players" channel and assign it a controller module, PhoenixLeaderboard.PlayersChannel:


channel "players", PhoenixLeaderboard.PlayersChannel

Now let’s add a simple join handler to our new PhoenixLeaderboard.PlayersChannel (web/channels/players_channel.ex):


defmodule PhoenixLeaderboard.PlayersChannel do
  use Phoenix.Channel

  def join("players", _message, socket) do
    {:ok, [
      %{ id: 1, name: "Ada Lovelace", score: 5 },
      %{ id: 2, name: "Grace Hopper", score: 10 },
      %{ id: 3, name: "Marie Curie", score: 15 },
      %{ id: 4, name: "Carl Friedrich Gauss", score: 20 },
      %{ id: 5, name: "Nikola Tesla", score: 25 },
      %{ id: 6, name: "Claude Shannon", score: 30 }
    ], socket}
  end
end

Every time a client joins the "players" channel, we’ll send them a list of players in our reply.

If we go back to our application, we’ll see that all of our players are correctly pulled from the server and rendered in order of their score!

What’s Next and Final Thoughts

In good conscience, we should reiterate that this is just an experiment. We don’t recommend tearing a Meteor application in half and dropping its front-end into another application.

That being said, the fact that this is possible is really interesting!

It’s amazing that after dropping the Meteor front-end into our Phoenix application, we can still use all of the features of Blaze templates, Minimongo, and Session variables right out of the box!

In our next post, we’ll finish up our Franken-stack by wiring our Phoenix server up to a real database and using Channel events to implement the “Add Points” functionality.

Stay tuned!

The Captain's Distance Request

This post is written as a set of Literate Commits. The goal of this style is to show you how this program came together from beginning to end.

Each commit in the project is represented by a section of the article. Click each section's header to see the commit on Github, or check out the repository and follow along.

Written by Pete Corey on Aug 10, 2016.

Project Setup

Under the captain’s orders, we’ll be implementing a method that calculates the distance between two points on Earth given in degree/minute/second format.

As always, we’ll get started by creating a new project that uses Babel for ES6 transpilation and Mocha for all of our testing needs.

.babelrc

+{ + "presets": ["es2015"] +}

.gitignore

+node_modules/

package.json

+{ + "main": "index.js", + "scripts": { + "test": "mocha ./test --compilers js:babel-register" + }, + "dependencies": { + "babel-preset-es2015": "^6.9.0", + "babel-register": "^6.9.0", + "chai": "^3.5.0", + "lodash": "^4.12.0", + "mocha": "^2.4.5" + } +}

test/index.js

+import { expect } from "chai"; + +describe("index", function() { + + it("works"); + +});

The Simplest Test

To get started, we’ll write the simplest test we can think of. We would expect the distance between two identical coordinates to be zero kilometers:


expect(distance(
    "48° 12′ 30″ N, 16° 22′ 23″ E",
    "48° 12′ 30″ N, 16° 22′ 23″ E"
)).to.equal(0);

At first, our test suite does not run. distance is undefined. We can easily fix that by exporting distance from our main module and importing it into our test module.

Now the suite runs, but does not pass. It’s expecting undefined to equal 0. We can fix this by having our new distance function return 0.

index.js

+export function distance(coord1, coord2) { + return 0; +}

test/index.js

import { expect } from "chai"; +import { distance } from "../"; -describe("index", function() { +describe("The captain's distance", function() { - it("works"); + it("calculates the distance between two points", () => { + let coord1 = "48° 12′ 30″ N, 16° 22′ 23″ E"; + let coord2 = "48° 12′ 30″ N, 16° 22′ 23″ E"; + + expect(distance(coord1, coord2)).to.equal(0); + });

Splitting on Lat/Lon

We can think of our solution as a series of transformations. The first transformation we need to do is splitting our comma separated lat/lon string into two separate strings. One that holds the latitude of our coordinate, and the other that holds the longitude.


expect(splitOnLatLon("48° 12′ 30″ N, 16° 22′ 23″ E")).to.deep.equal([
    "48° 12′ 30″ N",
    "16° 22′ 23″ E"
]);

We can test that a function called splitOnLatLon does just this.

Implementing splitOnLatLon is just a matter of stringing together a few Lodash function calls.

index.js

+import _ from "lodash"; + +export function splitOnLatLon(coord) { + return _.chain(coord) + .split(",") + .map(_.trim) + .value(); +} + export function distance(coord1, coord2) {

test/index.js

import { expect } from "chai"; -import { distance } from "../"; +import { + distance, + splitOnLatLon +} from "../"; ... it("calculates the distance between two points", () => { - let coord1 = "48° 12′ 30″ N, 16° 22′ 23″ E"; - let coord2 = "48° 12′ 30″ N, 16° 22′ 23″ E"; + expect(distance( + "48° 12′ 30″ N, 16° 22′ 23″ E", + "48° 12′ 30″ N, 16° 22′ 23″ E" + )).to.equal(0); + }); - expect(distance(coord1, coord2)).to.equal(0); + it("splits on lat/lon", () => { + expect(splitOnLatLon("48° 12′ 30″ N, 16° 22′ 23″ E")).to.deep.equal([ + "48° 12′ 30″ N", + "16° 22′ 23″ E" + ]); });

DMS To Decimal

The next step in our transformation is converting our coordinates from their given degree, minute, second format into a decimal format that we can use to calculate distance.

We would expect our new toDecimal function to take in a DMS string and return a decimal interpretation of that lat/lon value.


expect(toDecimal("48° 12′ 30″ N")).to.be.closeTo(48.2083, 0.001);

We can represent each DMS string as a regular expression and use ES6 destructuring to easily extract the values we care about:


let regex = /(\d+)° (\d+)′ (\d+)″ ((N)|(S)|(E)|(W))/;
let [_, degrees, minutes, seconds, __, N, S, E, W] = regex.exec(dms);

From there, we do some basic conversions and math to transform the DMS values into their decimal equivilants.

index.js

... +export function toDecimal(dms) { + let regex = /(\d+)° (\d+)′ (\d+)″ ((N)|(S)|(E)|(W))/; + let [_, degrees, minutes, seconds, __, N, S, E, W] = regex.exec(dms); + let decimal = parseInt(degrees) + + (parseInt(minutes) / 60) + + (parseInt(seconds) / (60 * 60)); + return decimal * (N || E ? 1 : -1); +} + export function distance(coord1, coord2) {

test/index.js

... distance, - splitOnLatLon + splitOnLatLon, + toDecimal } from "../"; ... + it("converts dms to decimal format", () => { + expect(toDecimal("48° 12′ 30″ N")).to.be.closeTo(48.2083, 0.001); + expect(toDecimal("48° 12′ 30″ S")).to.be.closeTo(-48.2083, 0.001); + expect(toDecimal("16° 22′ 23″ E")).to.be.closeTo(16.3730, 0.001); + expect(toDecimal("16° 22′ 23″ W")).to.be.closeTo(-16.3730, 0.001); + }); + });

The Haversine Formula

The next step in our transformation is using the two sets of latidudes and longitudes we’ve constructured to calculate the distance between our two points.

We would expect the same two points to have zero distance between them:


expect(haversine(
    48.2083, 16.3730,
    48.2083, 16.3730,
    6371
)).to.be.closeTo(0, 0.001);

And we would expect another set of points to have a resonable amount of distance between them:


expect(haversine(
    48.2083, 16.3730,
    16.3730, 48.2083,
    6371
)).to.be.closeTo(3133.445, 0.001);

The haversize function is a fairly uninteresting implementation of the Haversine Formula. After implementing this formula, our tests pass!

index.js

... +export function haversine(lat1, lon1, lat2, lon2, R) { + let dlon = lon2 - lon1; + let dlat = lat2 - lat1; + let a = Math.pow(Math.sin(dlat/2), 2) + + Math.cos(lat1) * + Math.cos(lat2) * + Math.pow(Math.sin(dlon/2), 2); + let c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a)); + return R * c; +} + export function distance(coord1, coord2) {

test/index.js

... splitOnLatLon, - toDecimal + toDecimal, + haversine } from "../"; ... it("converts dms to decimal format", () => { - expect(toDecimal("48° 12′ 30″ N")).to.be.closeTo(48.2083, 0.001); - expect(toDecimal("48° 12′ 30″ S")).to.be.closeTo(-48.2083, 0.001); - expect(toDecimal("16° 22′ 23″ E")).to.be.closeTo(16.3730, 0.001); - expect(toDecimal("16° 22′ 23″ W")).to.be.closeTo(-16.3730, 0.001); + expect(toDecimal("48° 12′ 30″ N")).to.be.closeTo(48.208, 0.001); + expect(toDecimal("48° 12′ 30″ S")).to.be.closeTo(-48.208, 0.001); + expect(toDecimal("16° 22′ 23″ E")).to.be.closeTo(16.373, 0.001); + expect(toDecimal("16° 22′ 23″ W")).to.be.closeTo(-16.373, 0.001); + }); + + it("calculates distance using the haversine formula", () => { + expect(haversine( + 48.2083, 16.3730, + 48.2083, 16.3730, + 6371 + )).to.be.closeTo(0, 0.001); + + expect(haversine( + 48.2083, 16.3730, + 16.3730, 48.2083, + 6371 + )).to.be.closeTo(3133.445, 0.001); });

Finishing the Transformation

Now that we have all of the finished pieces of our transformation we can refactor our distance function.

The basic idea is that we want to split out the lat/lon of each coordinate, convert the DMS coordinates into decimal format, pass the resulting coordinates into haversine and finally round the result.

After doing this refactoring, our tests still pass!

index.js

... export function distance(coord1, coord2) { - return 0; + return _.chain([coord1, coord2]) + .map(splitOnLatLon) + .flatten() + .map(toDecimal) + .thru(([lat1, lon1, lat2, lon2]) => haversine(lat1, lon1, lat2, lon2, 6371)) + .divide(10) + .floor() + .multiply(10) + .value(); }

Final Tests and Bug Fixes

After adding in the remaining given tests in the code kata, I noticed I was getting incorrect results form my distance function. After looking at my code, I noticed an obvious error.

My toDecimal function was returning coordinates in degrees, but the haversine function was expecting the coordinates to be in radians.

The fix to our toDecimal function was simply to convert the result to radians by multipling by Math.PI / 180:


return decimal * (N || E ? 1 : -1) * (Math.PI / 180);

After making this change and refactoring our toDecimal tests, all of our tests passed.

index.js

... (parseInt(seconds) / (60 * 60)); - return decimal * (N || E ? 1 : -1); + return decimal * (N || E ? 1 : -1) * (Math.PI / 180); }

test/index.js

... )).to.equal(0); + + expect(distance( + "48° 12′ 30″ N, 16° 22′ 23″ E", + "23° 33′ 0″ S, 46° 38′ 0″ W" + )).to.equal(10130); + + expect(distance( + "48° 12′ 30″ N, 16° 22′ 23″ E", + "58° 18′ 0″ N, 134° 25′ 0″ W" + )).to.equal(7870); }); ... it("converts dms to decimal format", () => { - expect(toDecimal("48° 12′ 30″ N")).to.be.closeTo(48.208, 0.001); - expect(toDecimal("48° 12′ 30″ S")).to.be.closeTo(-48.208, 0.001); - expect(toDecimal("16° 22′ 23″ E")).to.be.closeTo(16.373, 0.001); - expect(toDecimal("16° 22′ 23″ W")).to.be.closeTo(-16.373, 0.001); + expect(toDecimal("48° 12′ 30″ N")).to.be.closeTo(0.841, 0.001); + expect(toDecimal("48° 12′ 30″ S")).to.be.closeTo(-0.841, 0.001); + expect(toDecimal("16° 22′ 23″ E")).to.be.closeTo(0.285, 0.001); + expect(toDecimal("16° 22′ 23″ W")).to.be.closeTo(-0.285, 0.001); });

Final Thoughts

Lately, we’ve been playing around with functional programming and languages like Elixir. Functional languages encourage you to express your programs as a series of pure transformations of your data.

This practice problem definitely shows some influences from that style of thinking. We leaned heavily on Lodash and wrote most of our functions as neatly chained transformations of their arguments.

While Javascript may not be the best language for writing code in this style, I’m a big fan of these kind of functional transformation pipelines. I feel like they produce very clear, very easily to follow functions and programs.

Be sure to check out the Github repo if you want to see the final source for this project!