26 February 2017

Blogger and Markdown

Blogger and Markdown

I have been writing on Blogger, on and off, since 2007. In all that time, I've always wanted to find a way to write my blog posts more easily without having to resort to HTML.

I am very happy to say that technology has finally caught up with my wish and my last few posts have been written using a combination of:

Before I go any further, I would like to extend many, many thanks to the authors of all this amazing software and to Dave Johnson for his blog post, Build an Amazing Markdown Editor Using Visual Studio Code and Pandoc, which helped me put it all together.

At a basic level, I followed Dave's steps pretty closely, so I won't repeat those here. Instead, I will focus on what I had to do to get this setup working.

Software installation

All software installation went very smoothly on my Windows machine, with no real problems. This post was made with the following versions of software:

  • Visual Studio Code: 1.9.1
    • Auto-Open Markdown Preview: 0.0.3
    • markdownlint: 0.6.2
    • vscode-pandoc: 0.0.8
  • Pandoc: 1.19.2.1

Blogger line break quirks

Blogger made a weird (though apparently well documented) decision to use <br> tags instead of <p> tags for line breaks in their WYSIWYG editor. Not only do they use only <br> tags, but the WYSIWYG editor will actively, and incorrectly, convert <p> tags to <br>. This is a huge pain until you realize what Blogger is doing. Luckily, there is a workaround.

  • Once Pandoc converts the Markdown into HTML, paste it into the editor's HTML mode.
  • Do not go to the editor's Compose mode after pasting your HTML.
  • If you want to see what your page will look like, use the Preview button.

When you stay out of Compose mode, all your <p> tags will be nicely preserved.

Pandoc's HTML vs. Blogger's expectations

Blogger expects you to provide the <body> portion of an HTML file for each blog post. But Pandoc produces full HTML files, including a header section. Again, there is a workaround.

When Pandoc creates an HTML 5 file, there are certain lines which it includes in the file that can be safely removed and, upon removal, will result in Blogger-compatible HTML.

In the segment below, the first set of ellipses represent your CSS for syntax highlighting (more on that below) and the second set of ellipses represent your actual blog content.

You want to remove all the lines that are shown in the code snippet below.

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <meta name="generator" content="pandoc">
  <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes">
  <title></title>
... <!-- Keep - CSS -->
</head>
<body>
... <!-- Keep - blog content -->
</body>
</html>

Syntax highlighting

Blogger does not come with any syntax highlighting function / mode. However, Pandoc provides a number of syntax highlighting styles. You can use these styles in Blogger to make your code easier to read.

First of all, please note that when Pandoc converts Markdown to HTML, it normally tries to produce multiple files - CSS and HTML in this instance.

You can force Pandoc to inline all the CSS code using the option -s, which will produce a standalone HTML file. You can then sanitize the HTML file per the above instructions.

Configuring markdownlint

The markdownlint plugin is extremely helpful in writing good Markdown files, especially for someone new to the format (like me). However, I chose to disable certain options (slightly different from what Dave Johnson did).

MD026 warns you when you have trailing punctuation in headers. For a few posts, my headers are questions and need the question mark at the end. I found the warning annoying and so turned it off.

MD007 warns you when sub-lists are indented more than 2 spaces. For Pandoc Markdown, I have to indent by 4 spaces, so I disabled this warning.

The contents of my .markdownlint.json file are below.

{
    "default": true,
    "MD026": false,
    "MD007": false,
    "no-hard-tabs": false,
    "line-length": false
}

Configuring vscode-pandoc

The vscode-pandoc plugin is the tool that connects Visual Studio Code, Pandoc, and your default browser. The plugin comes with 3 options - one each for the 3 output formats. I only changed the HTML-related option, since I am not interested in producing PDF or Docx files at this time.

My configuration for vscode-pandoc is as follows:

{
    ... // other user settings

    "pandoc.htmlOptString": "-s -f markdown -t html5 --highlight-style=pygments"
}

What do these options do?

-s
Produces a standalone file (combined CSS and HTML).
-f markdown
Sets the input type to Pandoc Markdown.
You can change this to original Markdown, GitHub-flavored Markdown, etc.
This "definition list" I am currently typing is courtesy of Pandoc Markdown.
-t html5
Produces a HTML 5 file.
--highlight-style=pygments
Sets the code highlight style to be similar to Pygments.
I recommend looking at the various options you have available (#18) and picking the style that suits your needs best.
Pygments is actually the default style, though I did test out all available options. I left this option in here in case Pandoc decides to change the default style in the future.

Unfulfilled items from my wish list

The one thing that I don't get with this setup is a sort of Intellisense / type inference / type annotation functionality that I've seen on some other blogs. This is an extremely cool feature that I can see being very helpful (almost akin to a more literate style of programming).

Specifically, there are some blogs out there which show you type information for F#, like function signatures, when you mouse-over the code in the post. I do not know at this time what plug-ins those writers are using to achieve this functionality. However, I will leave that investigation for another day.

Conclusion

I hope this blog post is helpful to people who are interested in using Markdown for their documentation needs. So far, I have found the experience of writing blog posts extremely enjoyable thanks to this setup and can see myself using it for the foreseeable future.

AOC 2016 - Day 1, Part 2

AOC 2016 - Day 1, Part 2

If you just want to jump into the code, the code for Day 1 is on GitHub.

The problem

Part 2 adds a small twist to the problem. Instead of just finding an end-point, you have to find the first block that you visit twice.

This is not as simple as checking against the end points of each move. Rather each intermediate block that you visit is a candidate for being the final answer.

Note about the problem

If you have not finished Day 1, Part 1 yet, the AOC website will not show you the Part 2 text. If you need to do Day 1, Part 1, please see my post on that subject.

Do the lines intersect?

There are a few ways to solve this problem.

  1. Keep a list of all Points (as sets of 2D Cartesian coordinates). Then, every time you move, check if you are passing over an already visited block.
  2. Store the lines that represent the moves you have made so far, in order. Then, when making a new move, check whether the new 'line of movement' intersects with any of the previous lines. If there is an intersection, find the point of intersection.

I first thought of implementing solution #1, but found solution #2 more interesting because I do not currently know how to calculate whether two lines intersect or what that intersection point is.

So, I started out by reading about lines and intersections. I started with various "game" / graphical algorithms because I assumed that this is a problem that game developers encounter often. Like most people (I imagine), I first ended up at Wikipedia. This is a great article that is heavy on theory and light on implementation details. A lot of the information, not only on Wikipedia but on various sites, involves knowing the equation of the line. I had the end-points, but did not readily have the slope-intercept form of the lines. After quite a bit of searching, I ended up on Martin Thoma's article, How to check if two line segments intersect.

I highly recommend reading this article if you haven't seen it before. He has an excellent explanation of line-line intersection. I actually implemented most of Martin's code (in F#) and it is quite solid. But then, I started reading Gregory Stein's comment on the same page regarding cross products of vectors. I really liked Gregory's idea, mainly due to the succinctness of the code. So, I also translated Gregory's code to F#. In the end, I went with Gregory's algorithm.

Here is what Gregory's code came out as:

let doLinesIntersect2 l1 l2 =
  let A = fst l1
  let B = snd l1
  let O = fst l2
  let M = snd l2
  let v1 = {x = A.x - O.x; y = A.y - O.y}
  let v2 = {x = B.x - O.x; y = B.y - O.y}
  let v3 = {x = M.x - O.x; y = M.y - O.y}
  let v4 = {x = A.x - M.x; y = A.y - M.y}
  let v5 = {x = B.x - M.x; y = B.y - M.y}

  let v4 = {x = v4.x + v5.x; y = v4.y + v5.y}
  let v5 = {x = v1.x + v2.x; y = v1.y + v2.y}
  let dotProduct = v4.x * v5.x + v4.y * v5.y

  if dotProduct > 0 then false
  else (
    let crossV1V3 = v1.x*v3.y - v1.y*v3.x
    let crossV3V2 = v3.x*v2.y - v3.y*v2.x
    (crossV1V3 < 0) = (crossV3V2 < 0)
  )

I can safely confirm that this code does work. This function has signature Point * Point -> Point * Point -> bool. Recall from Day 1 that a Point and a Location are defined as:

type Point = {
  x : int
  y : int
}

type Location = {
  dir : Direction
  pt : Point
}

Initially, my x-y coordinates were saved directly in the Location record. However, once I decided on a solution for Part 2, I actually went back, changed the data types, and refactored the Part 1 code so that it would continue working.

Where do they intersect?

Once I knew that two lines intersect, the next job was to find the intersection point. I looked at a number of sites and ended up adapting the code from Intersection of lines in 2D.

let intersectionPoint l1 l2 =
  let x1 = (fst l1).x
  let y1 = (fst l1).y
  let x2 = (snd l1).x
  let y2 = (snd l1).y
  let x3 = (fst l2).x
  let y3 = (fst l2).y
  let x4 = (snd l2).x
  let y4 = (snd l2).y

  let denom = (x1-x2)*(y3-y4)-(y1-y2)*(x3-x4)
  {x = ((x1*y2-y1*x2)*(x3-x4)-(x1-x2)*(x3*y4-y3*x4))/denom;
  y = ((x1*y2-y1*x2)*(y3-y4)-(y1-y2)*(x3*y4-y3*x4))/denom}

This function's signature is Point * Point -> Point * Point -> Point. It takes 2 lines, each represented as a pair of Points, and returns the intersection Point.

Putting it all together

I wanted to re-use, as much as possible, the code I had already written for Day 1, Part 1. Specifically, I wanted to re-use the move mechanic. To achieve this goal, I wrote my final function per the following spec:

  1. Parse the instructions
  2. Perform the moves while preserving all intermediate Locations.
  3. Extract the Points from the Locations, since the Direction isn't important once the moves are complete.
  4. Create conceptual lines by creating pairs of individual Points.
  5. Iterate over the list of Lines (which are really just Point tuples) to find an intersection, but with a built-in short-circuit. Once we find an intersection point, we don't want to update it again in the future.
  6. Finally, pull out the intersection point (if any) and calculate the distance from the startPt (which is at (0,0)).

The things I love about F# is that I was able to translate this spec almost line-for-line into code. I called this function dupFinder because I figured that we are trying to find the first Point that is a duplicate in the route we have traveled thus far:

let dupFinder strList =
  Regex.Matches (strList, @"[LR]\d+")
  |> Seq.cast
  |> Seq.scan
    (fun oldloc (instr : System.Text.RegularExpressions.Match) ->
      move
        (instr.Value.[0] |> toTurn)
        (instr.Value.Substring 1 |> int)
        oldloc
    )
    startLoc
  |> Seq.map (fun x -> x.pt)
  // Define lines
  |> Seq.pairwise
  |> Seq.fold
    (fun accum elt ->
      if snd accum = None then
        let s = fst accum
        if Seq.exists (doLinesIntersect2 elt) s then
          let ip = Seq.find (doLinesIntersect2 elt) s
          s, intersectionPoint ip elt |> Some
        else s @ [elt], None
      else accum
    )
    ([], None)
  |> snd
  |> fun x ->
    match x with
    | None -> failwith "No intersection"
    | Some y -> y
  |> distance startPt

And this is it. I invoked the dupFinder function with the input string (same string as Part 1) and got the correct answer.

The answer you get with this code is 141, which is, in fact, correct.

If you want to see the code for Day 1 (both parts), please head over to GitHub.

But what about testing?

As you may have noticed, I barely have any testing in my code. In the beginning, I debugged by code using a combination of code reading (gotta love static typing!) and the tee function to print debugging information during execution.

If you are not aware of tee, I highly recommend reading Extending F# Pipelines With A Tee Function and Scott Wlaschin's Railway oriented programming.

Here is the code for tee:

let tee f x =
  f x |> ignore
  x

This handy little function allows you to inject arbitrary commands (such as printfn or logger.Log) into the middle of a pipe chain without disturbing the rest of the code. It takes a function and an argument, executes the function, ignores the result (if any), and passes the original argument forward. Obviously, this wouldn't work so well if the function somehow mutated the argument. Luckily, F# makes it at least a little annoying to write functions that mutate values, and I almost always only use tee to do mid-pipe log entries / debug output.

See you next time!

18 February 2017

AOC 2016 - Day 1, Part 1

AOC 2016 - Day 1, Part 1

Disclaimer

I want to start this post by saying that when I first started with Advent of Code, I had no idea that each day's problem is divided into two parts. Thus, the code will often look awkward and weird. If I were to re-code the solution, knowing what I know now, I would definitely make some changes.

Please note that I have NOT gone back and "fixed up" the code. This is the actual code I wrote to successfully solve each challenge. Are there things I would change - Yes. However, I am much more interested in finding solutions for new problems than I am in fixing this code, especially since no one else is relying on it.

I have tried to learn from my mistakes, as will hopefully be obvious from code written for future challenges.

The setup

The following theme is used, at least as far as I know, to tie all 25 days worth of AOC problems together.

Santa's sleigh uses a very high-precision clock to guide its movements, and the clock's oscillator is regulated by stars. Unfortunately, the stars have been stolen... by the Easter Bunny. To save Christmas, Santa needs you to retrieve all fifty stars by December 25th.

The second paragraph actually tells you that there are 2 problems each day. Obviously, I was not paying attention to detail like I should have (emphasis is mine).

Collect stars by solving puzzles. Two puzzles will be made available on each day in the advent calendar; the second puzzle is unlocked when you complete the first. Each puzzle grants one star. Good luck!

The reason I mention this is that the code may look awkward for certain solutions when I am trying to re-use code from that day's first part.

The problem

Rather than copy-paste lots of text, I will briefly describe the problem. Please go to the AOC website to see the original information.

The first problem is a relatively simple example of writing an algorithm to move in a grid-like pattern with no diagonal movements (since you can only turn left and right by 90°) - this is also known as Taxicab geometry.

The solution

Types

Sidenote: Although I am solving all these problems in F#, what really got me back into programming (and loving it again!) is the language Elm. If you don't know what Elm is, I highly recommend taking a look. It is a beginner-friendly functional language designed to write safe web applications (it is compiled into Javascript). One of the tips to solve problems in Elm (or pretty much any language for that matter), is to start by defining your types. That is what I did here.

After a few false starts, here is how I chose to define the types. Initially, I did not have the Point type but this was added later on to facilitate work on Day 1, Part 2.

type Direction =
  | North
  | South
  | East
  | West

type TurnTo =
  | R
  | L

type Point = {
  x : int
  y : int
}

type Location = {
  dir : Direction
  pt : Point
}

In order to make life easier, I have a few base values for my complex types.

let startPt = {
  x = 0
  y = 0
}

let startLoc = {
  dir = North
  pt = startPt
}

Reading the instructions

Now that I have defined my types, I can start diving into the logic. The first task I need to solve is to convert instructions (which was not as easy as I thought - more on that further down in the post) into my nice types. I built a small helper function to translate a character representing the direction (L and R) into a TurnTo value.

let toTurn = function
  | 'R' -> R
  | 'L' -> L
  | _ -> failwith "Unknown turn type"

Individual moves

For each individual instruction in the list, I need to do 2 things:

  1. turn in the appropriate direction
  2. move forward the specified number of blocks.

In the spirit of writing small, digestible functions and stringing them together, I broke this logic into two steps. First, since my current location includes my cardinal direction, I wrote a small function to implement the turn. The signature of this function is TurnTo -> Location -> Location. It takes a Direction to turn in and the current Location (which includes my current Direction), and returns a new Location record where I am pointing in the updated direction based on the instruction.

let turn way loc =
  match way with
  | L ->
    match loc.dir with
    | North -> { loc with dir = West }
    | West -> { loc with dir = South }
    | South -> { loc with dir = East }
    | East -> { loc with dir = North }
  | R ->
    match loc.dir with
    | North -> { loc with dir = East }
    | East -> { loc with dir = South }
    | South -> { loc with dir = West }
    | West -> { loc with dir = North }

The second function I wrote advances me in the given direction. This function's signature is int -> Location -> Location. Similar to turn, this function takes the number of blocks to move and current Location, and returns a new, post-move Location.

let advance dist loc =
  match loc.dir with
  | North ->
    let npt = { x = loc.pt.x; y = loc.pt.y + dist }
    { loc with pt = npt }
  | South ->
    let npt = { x = loc.pt.x; y = loc.pt.y - dist }
    { loc with pt = npt }
  | West ->
    let npt = { x = loc.pt.x - dist; y = loc.pt.y }
    { loc with pt = npt }
  | East ->
    let npt = { x = loc.pt.x + dist; y = loc.pt.y }
    { loc with pt = npt }

And now we just need to tie them together to move. Move is quite simple - it's purpose is to put together a turn and an advancement into a single action. Its signature is TurnTo -> int -> (Location -> Location). What this means is that it takes a TurnTo and an int, then returns a function. When a Location is passed to this new function, the character will perform a single move. Here, I am using the F# function composition operator.  You can find a good writeup on it here.

let move way dist = (turn way) >> (advance dist)

Stringing moves together

Most of the guts of this algorithm are now coded, but we are still missing 2 main pieces:

  1. the connection from a list of instructions to actual movements, and
  2. calculating the distance from the start point (assumed to be (0,0) facing North) to the final Location.

This duty falls to the moveAll function. This function takes a string and returns a Location. It parses the list of instructions and then progressively folds the intermediate results into a final Location.

let moveAll strList =
  Regex.Matches (strList, @"[LR]\d+")
  |> Seq.cast
  |> Seq.fold
    (fun oldloc (instr : System.Text.RegularExpressions.Match) ->
      move
        (instr.Value.[0] |> toTurn)
        (instr.Value.Substring 1 |> int)
        oldloc
    )
    startLoc

Now we come to the end and put a bow on the solution. The distance function just calculates the distance between the initial and final points using Taxicab geometry and partOne : strList:string -> int ties moveAll to distance.

let distance stloc endloc = (abs (stloc.x - endloc.x)) + (abs (stloc.y - endloc.y))

let partOne strList =
  strList |> moveAll |> fun x -> distance startPt x.pt

Getting the answer, and a note about parsing and file manipulation

I mentioned earlier that I would speak more about parsing. Well, the smart thing to do with a problem like this is to take the input from the AOC website, put it into a file, and then parse it in the code. However, when I started on AOC, I did not know how to perform file manipulation with F# (and apparently didn't want to learn for the first few days of problems). Thus, you will see odd things like this block of code in my solutions for the first few days. At some point, I realized that copy/pasting large blocks of text into an F# script file is not a smart idea and learned how to manipulate files (which turns out to be quite easy in .NET).

Putting all this together and seeing it run (at last!) was a great feeling. The answer you get if you run my code is 239, which is, in fact, the correct answer.

I am intending to put all my code into GitHub sometime in the near future. Until then, all my code for the first solution is actually on this page (and in my gists) except for one import of System.Text.RegularExpressions.

See you next time!

17 February 2017

Advent of Code 2016 - What is it?

Introduction to Advent of Code 2016

When developing software as a hobby, it is important to find interesting problems to keep interest high. As I posted earlier, I will be making my future posts based on the Advent of Code challenge for 2016. But, what is Advent of Code?

If you're not familiar, here is a description from their website:

Advent of Code is a series of small programming puzzles for a variety of skill levels. They are self-contained and are just as appropriate for an expert who wants to stay sharp as they are for a beginner who is just learning to code. Each puzzle calls upon different skills and has two parts that build on a theme.

So far, having done 5 days, I've found the problems very interesting and, in at least one case, extremely challenging.

This is just meant to be an introductory post. Next post will dive into Day 1.

FizzBuzz?

So, I obviously missed something "profound" when I read the term FizzBuzz for the first time and had no idea what it was talking about. I started digging in and was actually a little astounded (and saddened) by what I read.

I wanted to see if I could some up with something that would work. Obviously, I wasn't in an interview setting with someone breathing down my neck, but this is what I wrote in about 5 minutes. Basic testing shows that it seems to work. So, I don't know who this will help, but I am posting my contribution to FizzBuzz:

14 February 2017

Coming back to blogging

Hi All,

It's been a long, LONG time, but I believe I am finally ready to come back to blogging.  It helps that I've finally found a good placed in life (in every way) and am starting to love development again.

I'll be restarting my blogging exercise by walking through my solutions for the Advent of Code challenge for 2016.  I've already got the solutions, in F# of course, for the first 5 days - i.e. 10 problems.  I'll post about those first, then continue with the remaining ones.

This promises to be quite an adventure - at least for me personally.  And I'm looking forward to sharing it with all of you (and learning from all of you as well).

Kind regards.