Tag: graph

Yesterday was a busy day at work and also after, shopping for today: the Independence Day of Finland. Soon I’ll go to see the cannons fire at Linnansaari (Castle Island) with the kids’ families so just a short update on yesterday’s puzzle.

Part 1 was easy and fast to implement. I used last year’s Graph<T> algorithms I implemented to find out which book pages should precede other pages in a list of page numbers. Graph contains the list of pages (vertices) and for each page, those pages that should follow that page (edges).

Second puzzle then… I started with it way too complicated. When failed, I decided to go brute force. The goal was to fix broken page orders, so I thought that I’d just create all the permutations of page orders for a certain print job and try which of those would be correct.

Well, when the input data has page sequences like…:

74,56,86,81,84,44,53,92,12,36,15,66,95,26,71

…and you realize that this sequence of 15 elements alone has 15! permutations, that is 1 307 674 368 000, and the data set has 200+ such sequences, you’ll know that this will take way too much time.

So I left this puzzle alone yesterday and continued this morning, when I woke up after 5 am and couldn’t get any sleep, waiting for the trip to see the cannons fire.

Instead of permutations, the working (and fast) algorithm just goes through the sequence and checks if a page number following the previous is in the edge list of the previous page. If not, the pages are swapped. This is done in a loop that checks if the sequence is still not correct, the checking and swapping continues until the morale improves:

private func fix(_ pages: [Int], using graph: Graph<Int>) -> [Int] {
    var modPages = pages
    repeat {
      for index in 0..<modPages.count - 1 {
        let preceding = modPages[index]
        let following = modPages[index + 1]
        let edges = graph.edges(for: graph.vertex(for: preceding)!)?.map ( {$0.destination.item } )
        if edges != nil && !edges!.isEmpty {
          if !edges!.contains(following) {
            modPages.swapAt(index, index + 1)
          }
        } else {
          modPages.swapAt(index, index + 1)
        }
      }
    } while !isUpdateValid(modPages, graph)
    return modPages
}

This did the trick, and is fast, and the puzzle is solved. Let’s see how today’s puzzle is when I return from the morning trip.

$ swift run -c release AdventOfCode 5 --benchmark
Building for production...
[5/5] Linking AdventOfCode
Build of product 'AdventOfCode' complete! (2.73s)
Executing Advent of Code challenge 5...
Part 1: 4689
Part 2: 6336
Part 1 took 0.006513333 seconds, part 2 took 0.020255375 seconds.