writeups/2020/rgbctf/picking-pieces

Picking Up The Pieces

writeup by haskal for BLÅHAJ

Misc 403 points 93 solves

Can you help me? I had a flag that I bought at the store, but on the way home, I dropped parts of it on some roads! Now some roads have strings of text, and I can't tell which are part of my flag. I'm very smart and efficient (but somehow not smart or efficient enough to keep my flag), so I know that I took the fastest way from the store back to my house.

I have a map with a list of all 200000 roads between intersections, and what strings are on them. The format of the map is <intersection 1> <intersection 2> . My house is at intersection 1 and the store is at intersection 200000.

provided file: <map.txt>

writeup

consider the intersections and roads to be a (weighted) graph and use dijkstra's algorithm to find the shortest path. here is a solution in racket (because racket is good and you should use it)

#lang racket

(require graph)

;; this enables looking up the string labels when we're done
(define label-lookup (make-hash))

;; str -> (list num str str)
(define (parse-line line)
  (match-define (list from to distance label) (string-split line " "))
  (hash-set! label-lookup (list from to) label)
  (hash-set! label-lookup (list to from) label)
  (list (string->number distance) from to))

(displayln "reading file")
(define input
  (map parse-line (file->lines "map.txt")))

(displayln "creating graph")
(define g (weighted-graph/undirected input))

(displayln "running coding and algorithms")
(define-values [dist pred] (dijkstra g "1"))
(displayln "done")

;; prints the path in reverse order then the labels in forward order
(define (walk x)
  (displayln x)
  (define the-pred (hash-ref pred x #f))
  (unless (false? the-pred)
    (walk the-pred)
    (displayln (hash-ref label-lookup (list the-pred x)))))

(walk "200000")