3.1 Part 1🔗

The input is a list of numbers. For each we must find a "maximum joltage", and sum the result. Maximum joltage is defined as the maximum 2-digit number, only picking digits from left to right.

One obvious option would be to iterate over all possible pairs and pick the maximum, but we can do better. Let’s appreciate the following:

• the max joltage starts with the highest digit, excluding the last one in the number

• the second digit it the highest digit between the first one and the end of the number

This has a linear complexity (relative to the number of digits), and sounds like a much better approach. It is also pretty easy to express in a function:

Therefore the solution for part one can be written as:

(for/sum ([s input]) (string->number (get-max-2 s)))

3.2 Part 2🔗

The second part changes slightly the definition of maximum joltage. Instead of a 2 digit number, it is now the highest 12 digits number, still taking digits from left to right. Good thing our solution does not rely on enumerating all combinations!

Actually, this second part can be done by generalizing the previous solution:

• the first digit is the highest, except for the 11 last digits

• the second digit it the highest between the first one and the 10 last digits

• the third digit it the highest between the second one and the 9 last digits

• and so on…

We can tweak our first solution adding a recursion, but the logic remains the same. Here is the result:

(define (get-max value nb-digits)

(cond

[(<= nb-digits 1) (string->max-digit value)]

[else

(let* ([len (string-length value)]

[max (string->max-digit-pos (substring value 0 (add1 (- len nb-digits))))]

[next-str (substring value (add1 max) len)])

(string-append

(string (string-ref value max))

(get-max next-str (sub1 nb-digits))))]))

So the solution would be:

(for/sum ([s input]) (string->number (get-max s 12)))

We can also rewrite the solution for part 1 using this new function, since the only difference is the number of digits:

(for/sum ([s input]) (string->number (get-max s 2)))

3.3 Complete implementation🔗

#lang racket

(define input

(if (file-exists? "inputs/day3.txt")

(file->lines "inputs/day3.txt")

(begin

(println "Warning: 'inputs/day3.txt' is not found, using 'samples/day3.txt' instead.")

(file->lines "samples/day3.txt"))))

(define (string->max-digit-pos s)

(let ([digits (map string->number (map string (string->list s)))])

(index-of digits (apply max digits))))

(define (string->max-digit s)

(let ([digits (map string->number (map string (string->list s)))])

(~a (apply max digits))))

(define (get-max value nb-digits)

(cond

[(<= nb-digits 1) (string->max-digit value)]

[else

(let* ([len (string-length value)]

[max (string->max-digit-pos (substring value 0 (add1 (- len nb-digits))))]

[next-str (substring value (add1 max) len)])

(string-append

(string (string-ref value max))

(get-max next-str (sub1 nb-digits))))]))

; -----------------------------------------------------------------------------

; PART 1

(define (part1 input)

(for/sum ([s input])

(string->number (get-max s 2))))

(define solution1 (part1 input))

(printf "Part 1: ~a~n" solution1)

; -----------------------------------------------------------------------------

; PART 2

(define (part2 input)

(for/sum ([s input])

(string->number (get-max s 12))))

(define solution2 (part2 input))

(printf "Part 2: ~a~n" solution2)