Trinary

From wiki.winny.tech
Jump to: navigation, search

Hi!

01[edit]

#lang racket

(define input (map (compose1 string->number string)
                   (string->list (read-line))))

(define (solve input [offset 1])
  (for/sum ([a input]
            [b (sequence-tail (in-cycle input) offset)]
            #:when (= a b)) b))

(solve input)
(solve input (/ (length input) 2))

02[edit]

#lang racket
(require math/base srfi/26)

(define input (map (compose1 (curry map string->number) string-split)
                   (port->lines)))

(define (checksum sheet)
  (sum (map - (map (curry apply max) sheet)
              (map (curry apply min) sheet))))

(define (evenly-divides row)
  (findf (compose1 exact-integer? (curry apply /))
         (map (cute sort <> >) (combinations row 2))))

(checksum input)
(sum (map (compose1 (curry apply /) evenly-divides) input))

03[edit]

Explicit formular for the first part, but that didn't extend well to the second part.

Part 1:

#lang racket

(define input (string->number (read-line)))

(define (distance location)
  (define ring (floor (/ (ceiling (sqrt location)) 2)))
  (define side-length (add1 (* ring 2)))
  (define side-middles
    (map (λ (x) (- (sqr side-length)
                   (+ (/ (sub1 side-length) 2)
                      (* x (sub1 side-length)))))
         (range 4)))
  (define distance-to-side-middle
    (apply min (map (λ (x) (abs (- x location))) side-middles)))
  (+ ring distance-to-side-middle))

(distance input)

Spiral following generalised to both parts (slower than explicit, for a):

#lang racket
(require racket/fixnum math/base)

(define input (string->number (read-line)))

(define (fxv+ . args) (apply vector-map fx+ args))
(define (rot-left dir) (vector (- (vector-ref dir 1)) (vector-ref dir 0)))

(define (spiral-fill f #:limit limit)
  (do ([dir #(0 1)]
       [pos #(1 0) (fxv+ pos dir)]
       [steps 1 (add1 steps)]
       [steps-to-turn 1 (sub1 steps-to-turn)]
       [stepsize 2]
       [grid (make-hash '((#(0 0) . 1)))
             (begin
               (hash-set! grid pos (f grid pos steps))
               grid)])
      ((> steps limit)
       grid)
        (when (zero? steps-to-turn)
          (set! dir (rot-left dir))
          (set! steps-to-turn stepsize)
          ; stepsize never increments when going north or south
          (unless (zero? (vector-ref dir 1)) (set! stepsize (add1 stepsize))))))

(define neighbour-offsets
  (list->vector (map list->vector (filter-not (curry apply = 0) (cartesian-product (range -1 2) (range -1 2))))))
(define (sum-neighbours grid pos step)
  (for/sum ([offset neighbour-offsets])
    (hash-ref grid (fxv+ pos offset) 0)))

(define grid-a
  (spiral-fill (λ (grid pos step) (add1 step))
               #:limit input))

(for/first ([(k v) grid-a]
            #:when (equal? input v))
  (sum (map abs (vector->list k))))

(define grid-b (spiral-fill sum-neighbours #:limit (integer-sqrt input)))
(findf (curry < input) (sort (hash-values grid-b) <))

04[edit]

#lang racket

(define input (port->lines))

(define (valid-a? passphrase)
  (false? (check-duplicates (string-split passphrase))))

(define (string-sort s)
  (list->string (sort (string->list s) char<?)))

(define (valid-b? passphrase)
  (false? (check-duplicates (map string-sort (string-split passphrase)))))

(count valid-a? input)
(count valid-b? input)

05[edit]

First attempt used streams, took 9 minutes (21 after "optimisation" with data/collection) to run, so fallback to imperative do.

This one gets 20-30% slower if state and pc are wrapped in a struct.

#lang racket
(require racket/match)

(define input (list->vector (map string->number (port->lines))))

(define (step-a! tape pc)
  (define instr (vector-ref tape pc))
  (vector-set! tape pc (add1 instr))
  (+ instr pc))

(define (step-b! tape pc)
  (define instr (vector-ref tape pc))
  (vector-set! tape pc (if (>= instr 3) (sub1 instr) (add1 instr)))
  (+ instr pc))

(define (solve step! tape)
  (do ([tape (vector-copy tape)]
       [max-idx (sub1 (vector-length tape))]
       [step 0 (add1 step)]
       [pc 0 (step! tape pc)])
      ((not (<= 0 pc max-idx))
       step)))

(solve step-a! input)
(solve step-b! input)

04-syntax[edit]

#lang racket

(define input (port->lines))

(define (valid-a? passphrase)
(false? (check-duplicates (string-split passphrase))))

(define (string-sort s)
(list->string (sort (string->list s) char<?)))

(define (valid-b? passphrase)
(false? (check-duplicates (map string-sort (string-split passphrase)))))

(count valid-a? input)
(count valid-b? input)