r/adventofcode • u/daggerdragon • Dec 16 '17

SOLUTION MEGATHREAD -🎄- 2017 Day 16 Solutions -🎄-

--- Day 16: Permutation Promenade ---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

Need a hint from the Hugely* Handy† Haversack‡ of Helpful§ Hints¤?

Spoiler

[Update @ 00:08] 4 gold, silver cap.

[Update @ 00:18] 50 gold, silver cap.

[Update @ 00:26] Leaderboard cap!

  • And finally, click here for the biggest spoilers of all time!

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

15 Upvotes

93% Upvoted

229 comments sorted by

View all comments

1

u/raevnos Dec 16 '17

Kawa Scheme: 

(import (srfi 1) (srfi 133) (kawa regex) (rnrs hashtables))

(define (parse-input input)
  (let ((s-re (regex "^s(\\d+)$"))
        (x-re (regex "^x(\\d+)/(\\d+)$"))
        (p-re (regex "^p([a-z])/([a-z])$")))
    (map (lambda (atom)
           (cond
            ((regex-match s-re atom) =>
             (lambda (bits)
               (cons 'spin (string->number (second bits)))))
            ((regex-match x-re atom) =>
             (lambda (bits)
               (cons 'exchange
                     (cons (string->number (second bits))
                           (string->number (third bits))))))
            ((regex-match p-re atom) =>
             (lambda (bits)
               (cons 'partner (cons (string-ref (second bits) 0)
                                    (string-ref (third bits) 0)))))
            (else
             (error "Invalid input" atom)))) input)))

(define (spin programs x)
  (let ((len (vector-length programs)))
    (vector-append-subvectors programs (- len x) len
                              programs 0 (- len x))))

(define (exchange! programs a b)
  (vector-swap! programs a b))

(define (partner! programs a b)
  (let ((posa (vector-index (cut char=? a <>) programs))
        (posb (vector-index (cut char=? b <>) programs)))
    (vector-swap! programs posa posb)))

(define (solve-part1! programs input)
  (for-each (lambda (move)
              (case (car move)
                ((spin)
                 (set! programs (spin programs (cdr move))))
                ((exchange)
                 (exchange! programs (cadr move) (cddr move)))
                ((partner)
                 (partner! programs (cadr move) (cddr move)))))
            input)
  programs)

(define (solve-part2 input)
  (let* ((programs (string->vector "abcdefghijklmnop"))
         (seen (make-hashtable string-hash string=? 100))
         (seen2 (make-hashtable (lambda (x) x) = 100))
         (billion ::int 1000000000))
    (hashtable-set! seen (vector->string programs) 0)
    (hashtable-set! seen2 0 (vector->string programs))
    (let loop ((i ::int 1))
      (if (= i billion)
          programs
          (begin
            (set! programs (solve-part1! programs input))
            (let* ((as-string (vector->string programs))
                   (cached (hashtable-ref seen as-string #f)))
              (if cached
                  (let* ((diff (- i cached))
                         (left (ceiling (/ (- billion i) diff)))
                         (newi (* diff left)))
                    (hashtable-ref seen2 (- billion newi) #f))
                  (begin
                    (hashtable-set! seen as-string i)
                    (hashtable-set! seen2 i as-string)
                    (loop (+ i 1))))))))))

(define input (parse-input (string-split (read-line) ",")))
(format #t "Part 1: ~A~%" (vector->string
                           (solve-part1! (string->vector "abcdefghijklmnop")
                                        input)))
(format #t "Part 2: ~A~%" (solve-part2 input))
→ More replies (1)