Monthly Archives: January 2016

Oh my, am I really considering XML?

Since writing Why Markdown is not my favorite text markup language, I’ve been thinking more about document formats.

More and more I begin to see the impetus for the design of XML, despite its sometimes ugly implementation. With XML you avoid much of the ambiguity of parsing plain-text-based formats and just write the document AST directly. Whether this is a good or bad thing seems to depend on the tools you have available to you, but I think I’m starting to see the light.

At $WORK, for example, I’ve been writing directly in the “XML-ish” Confluence storage format since it was introduced in Confluence 4. Combined with the right editing environment (such as that provided by Emacs’ nxml-mode), it’s easy to navigate XML “structurally” in such a way that you no longer really see the tags.

It’s sort of like being Neo in The Matrix except that, instead of making cool shit happen in an immersive virtual world you’re, um, writing XML.

However, not all is roses in XML-land. In an ideal world, you could maintain a set of XML documents and reliably transform them into other valid formats using a simple set of tools that are easy to learn and use. In reality, many of the extant XML tools such as XSLT exhibit a design aesthetic that is deeply unappealing to most programmers. The semantics of XSLT are interesting, but the syntax appears to be a result of the mistakes that are often made when programmers decide to create their own DSLs. Olin Shivers has a good discussion of the often-broken “little language” phenomenon in his scsh paper.

Speaking of Scheme, it’s possible that something reasonable can be built with SXML. I’ve also had good results using Perl and Mojo::DOM to build Graphviz diagrams of the links among Confluence wiki pages as part of a hacked-together “link checker” (Users of Confluence in an industrial setting will know that the built-in link-checking in Confluence only “sort of” works, which is indistinguishable in practice from not actually working — hence the need to build my own thing).

I’ve also been playing around with MIT Scheme’s built-in XML Parser, and so far I’m preferring it to the Perl or SXML way of doing things.

Advent of Code, Day 3

In this post I’ll describe my solution for Day 3 of the Advent of Code.

Problem Description

Day 3: Perfectly Spherical Houses in a Vacuum

Santa is delivering presents to an infinite two-dimensional grid of houses.

He begins by delivering a present to the house at his starting location, and then an elf at the North Pole calls him via radio and tells him where to move next. Moves are always exactly one house to the north (‘^’), south (‘v’), east (‘>’), or west (‘<‘). After each move, he delivers another present to the house at his new location.

However, the elf back at the north pole has had a little too much eggnog, and so his directions are a little off, and Santa ends up visiting some houses more than once. How many houses receive at least one present?

For example:

‘>’ delivers presents to 2 houses: one at the starting location, and one to the east.

‘^>v<‘ delivers presents to 4 houses in a square, including twice to the house at his starting/ending location.

‘^v^v^v^v^v’ delivers a bunch of presents to some very lucky children at only 2 houses.

Solution

Broadly speaking, my solution consisted of:

  • Reading the directions file to determine the largest x and y values of the grid
  • Making a shaped array using those dimensions (specifically, we double the array dimensions to allow for movement up, down, forward, and back)
  • Starting in the center of the shaped array, follow the instructions from the “map” and mark every house (called a “position” in the code) if it hasn’t already been visited
  • Every time we visit a house we haven’t already visited, we bump a counter

Here’s the Scheme code that accomplishes those steps:

;; read in the string
;; sum the ^ and v chars to get the height of the matrix (graph)
;; sum the < and > chars to get the width of the matrix (graph)

(define (north? ch) (char=? ch #\^))
(define (south? ch) (char=? ch #\v))
(define (east? ch) (char=? ch #\>))
(define (west? ch) (char=? ch #\<))

(define (make-shape width height)
  ;; Int Int Int -> Shape
  (shape 0 width 0 height))

(define (read-shape-file file)
  ;; Pathname -> Shape
  (with-input-from-file file
    (lambda ()
      (let loop ((width 0)
         (height 0)
         (min-width  0)
         (max-width 0)
         (min-height 0)
         (max-height 0)
         (ch (read-char)))
    (if (eof-object? ch)
        (make-shape
         (* 2 (- max-width min-width))
         (* 2 (-  max-height min-height)))
        (cond ((north? ch)
           (loop width (+ height 1)
             min-width max-width
             (min min-height height)
             (max max-height height)
             (read-char)))
          ((south? ch)
           (loop width (- height 1)
             min-width max-width
             (min min-height height)
             (max max-height height)
             (read-char)))
          ((east? ch)
           (loop (+ width 1) height
             (min min-width width)
             (max max-width width)
             min-height max-height
             (read-char)))
          ((west? ch)
           (loop (- width 1) height
             (min min-width width)
             (max max-width width)
             min-height max-height
             (read-char)))
          (else (error "WHOA"))))))))

;; We make a shaped, multi-dimensional array (SRFI-25) in the size
;; it's determined we need by our earlier check.

(define (make-grid shape)
  ;; Shape -> Array
  (make-array shape #f))

;; The POSITION data type

(define-record-type position
  (make-position x y)
  position?
  (x position-x set-position-x!)
  (y position-y set-position-y!))

(define (array-center arr)
  ;; Array -> Position
  (let ((len-x (array-length arr 0))
    (len-y (array-length arr 1)))
    (make-position (/ len-x 2)
           (/ len-y 2))))

(define (make-relative-position x y ch)
  ;; Int Int Char -> Position
  (let ((vals '()))
    (cond ((north? ch)
       (set! vals (list (+ x 1) y)))
      ((south? ch)
       (set! vals (list (- x 1) y)))
      ((east? ch)
       (set! vals (list x (- y 1))))
      ((west? ch)
       (set! vals (list x (+ y 1))))
      (else (set! vals (list x y))))
    (make-position (first vals)
           (second vals))))

(define (visited? arr x y)
  ;; Array Int Int -> Bool
  (array-ref arr x y))

(define (set-visited! arr x y)
  ;; Array Int Int -> Undefined
  (array-set! arr x y #t))

(define (visit-locations arr file)
  ;; Pathname -> Int
  (let ((visited-count 0))
    (with-input-from-file file
      (lambda ()
    (let loop ((ch (read-char))
           (current-position (array-center arr)))
      (if (eof-object? ch)
          visited-count
          (begin
        (let* ((current-x (position-x current-position))
               (current-y (position-y current-position))
               (next-position
            (make-relative-position current-x current-y ch)))
          (if (not (visited? arr current-x current-y))
              (begin
            (set! visited-count (+ visited-count 1))
            (set-visited! arr current-x current-y)
            (loop (read-char)
                  next-position))
              (loop (read-char) next-position))))))))
    visited-count))

;; eof

Once this code is loaded up in the REPL, you can use it as shown below. (Note that the answer shown at the end isn’t real to avoid a spoiler.)

(set! *the-array* (make-grid (read-shape-file (expand-file-name "~/Code/personal/advent-of-code/03.dat"))))
'#{Array:srfi-9-record-type-descriptor}

> (array-size *the-array*)
42588

> (array-center *the-array*)
'#{Position}

> (define *the-file* (expand-file-name "~/Code/personal/advent-of-code/03.dat"))

> (visit-locations *the-array* *the-file*)
12345

Related Posts