# Picking Up The Pieces
writeup by [haskal](https://awoo.systems) for [BLÅHAJ](https://blahaj.awoo.systems)
**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> <distance> <string on the road>. My>house is at intersection 1 and the store is at intersection 200000.
provided file: [map.txt](https://git.lain.faith/BLAHAJ/writeups/raw/branch/writeups/2020/rgbctf/picking-pieces/map.txt)
## writeup
consider the intersections and roads to be a (weighted) graph and use dijkstra's algorithm to findthe shortest path. here is a solution in racket (because racket is good and you should use it)
(ctftime, being bad and awful doesn't highlight this correctly. see original writeup link)```scheme#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")```