3
\$\begingroup\$

I already solved it in JavaScript, where I'm more comfortable. I pretty much ported the algorithm from there.

I wanted to try the first Advent of Code puzzle in a new language and I picked Racket.

It's a taxicab geometry navigation problem. Given input R3, L5 you:

  • turn right 90 degrees
  • move forward 3 steps
  • turn left 90 degrees
  • move forward 5 steps

The goal: at the end of the instructions:

how far are you from the start?

It's my first Racket program. I've read around Lisps but not written much. How could I improve it?

#lang racket

; convert "L1" to '(#\L 1)
(define (parse step)
  (let ([dir (string-ref step 0)]
        [distance (string->number (substring step 1))])
    (list dir distance)))

; given a direction (#\L or #\R) and the last heading 0-3,
; compute the heading after the next step
(define (get-heading dir last-heading)
  (define raw
    (match dir
      [#\L (+ last-heading 1)]
      [#\R (- last-heading 1)]))
  (modulo raw 4))

; compute the x coordinate after the next step
(define (get-x heading last-x distance)
  (match heading
    [1 (+ last-x distance)]
    [3 (- last-x distance)]
    [_ last-x]))

; compute the y coordinate after the next step
(define (get-y heading last-y distance)
  (match heading
    [0 (+ last-y distance)]
    [2 (- last-y distance)]
    [_ last-y]))

; iterate over the instructions, computing
; x, y and heading after each step
(define (walk steps)
  (define-values (x y _)
    (for/fold
        ([x 0] [y 0] [heading 0])
        ([step steps])
      (match-define (list dir distance) step)
      (let* ([next-heading (get-heading dir heading)]
             [next-x (get-x next-heading x distance)]
             [next-y (get-y next-heading y distance)])
        (values next-x next-y next-heading))))
    (+ (abs x) (abs y))
  )

;;;; input
(define input "R3, L5, R1, R2, L5, R2, R3, L2, L5, R5, L4, L3, R5, L1, R3, R4, R1, L3, R3, L2, L5, L2, R4, R5, R5, L4, L3, L3, R4, R4, R5, L5, L3, R2, R2, L3, L4, L5, R1, R3, L3, R2, L3, R5, L194, L2, L5, R2, R1, R1, L1, L5, L4, R4, R2, R2, L4, L1, R2, R53, R3, L5, R72, R2, L5, R3, L4, R187, L4, L5, L2, R1, R3, R5, L4, L4, R2, R5, L5, L4, L3, R5, L2, R1, R1, R4, L1, R2, L3, R5, L4, R2, L3, R1, L4, R4, L1, L2, R3, L1, L1, R4, R3, L4, R2, R5, L2, L3, L3, L1, R3, R5, R2, R3, R1, R2, L1, L4, L5, L2, R4, R5, L2, R4, R4, L3, R2, R1, L4, R3, L3, L4, L3, L1, R3, L2, R2, L4, L4, L5, R3, R5, R3, L2, R5, L2, L1, L5, L1, R2, R4, L5, R2, L4, L5, L4, L5, L2, L5, L4, R5, R3, R2, R2, L3, R3, L2, L5")
(define steps
  (map parse
    (string-split input ", ")))

;;;; run
(walk steps)
\$\endgroup\$
2
\$\begingroup\$

Generative approach

The idea of functionally generating the next value from the current value rather than mutating a location is consistent with good Racket practice.

Naming

  1. Instead of 0 1 2 3 using the symbols 'north...it's not obvious what comes next without taking notes and working through the code and figuring out the implementation details...'south 'east 'west is more typical of Racket and other Lisps. The reason is that it aligns the level of abstraction in the program with the abstractions in the problem domain.

  2. When I see the parameter dir in the procedure get-heading my first thought is that it's type is a directory. The code base starting with low level string parsing probably sets me up. The extra characters of directory are worth the added clarity.

Abstractions

As with Naming 1. the abstractions in the code don't closely follow the business logic of the problem statement. There's no reference to Easter Bunny Headquarters or Taxicab Distance in the code. If the specification changed from taxicab to crowflight distance, it's not immediately obvious how to change the code.

  (define (distance-to-easterbunny-headquarters x y)
    (+ (abs x) (abs y))

Makes the code more modular and expresses the 'business logic' in the underlying problem explicitly. Because Racket treats functions as data, higher order functions allow further expression of the business logic and decoupling within the implementation.

  (define (taxicab-distance x y)
    (+ (abs x) (abs y))
  (define (distance-to-easterbunny-headquarters x y distance-function)
    (distance-function x y)

Even in the absence of change, the code will be more readable. And by extension a reviewer will spend less time trying to map the problem statement into the code.

In Racket, unlike many other languages, the idiom is to err on the side of verbosity and explanation. The guiding document is How to Design Programs (first edition, second edition) often referred to as HtDP. The methodology includes lots and lots of comments...even for someone who thinks the Easter Bunny and self-documenting code share some common features. Code golf the method is not.

Data Structures

HtDP methodology starts with data structures. The data structures should reflect the problem domain / business logic. Conversely as a general rule, working with values is a often code smell in Racket. There are a few corner cases where it is necessary and perhaps a few existing code bases where doing so maintains consistency. Otherwise it is likely that data structures will produce more modular and easier to read code.

Being only parameters passed to procedures, the review code's data structures are ad hoc and diffuse. Programmer defined data types are an idiomatic alternative.

(struct position (x y orientation))
(struct instruction (rotation distance))

These programmer defined data types automatically provide functions like position-x and instruction-rotation that align with the business logic and require. During debugging, a programmer defined data type provides something explicit to inspect. As the code evolves it provides a single place to implement changes, a known type to pass among procedures, semantics for creating a list of easter bunny headquarters locations, or hash table to memoize intermediate locations.

Formatting

Racket also has a style guide. It is typical to limit line length to 102 characters. For example:

(define input "R3, L5, R1, R2, L5, R2, R3, L2, L5, R5, L4, L3, R5, L1, R3,
               R4, R1, L3, R3, L2, L5, L2, R4, R5, R5, L4, L3, L3, R4, R4, 
               R5, L5, L3, R2, R2, L3, L4, L5, R1, R3, L3, R2, L3, R5")

is a typical way to handle long lists for improved readability.

The style guide also favors define over let and it's related forms. The advantages beyond readability include not having to debug against the differences between let let* let-rec.

Proximity

Explicitly naming is good. Limiting the scope of symbols lexically can avoid subtle bugs. The first definition in the code is parse it is not used until the last definition and it is only used there.

Nesting the definitions is probably appropriate here. It might also have made my confusion in Naming 2. less likely.

(define steps

  ; convert "L1" to '(#\L 1)
  (define (parse step)
    (let ([dir (string-ref step 0)]
          [distance (string->number (substring step 1))])
      (list dir distance)))

  (map parse
    (string-split input ", ")))
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ You're welcome. I learned a bit writing it. If you're interested, there is an Edx course on the HtDP methodology that's very good: edx.org/course/… Gregor Kickzales who teaches it came up with aspect oriented programming and wrote The MetaObject Protocol. \$\endgroup\$ – ben rudgers Dec 8 '16 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.