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.<\/p>\n\n\n\n
Part 1 was easy and fast to implement. I used last year’s 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.<\/p>\n\n\n\n Well, when the input data has page sequences like…:<\/p>\n\n\n\n …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<\/em> time.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n 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:<\/p>\n\n\n\n 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.<\/p>\n\n\n\n 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> … Continue reading “Advent of Code Day 5 – Print Queue”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_post_was_ever_published":false},"categories":[2],"tags":[136,48,149,151,70,46],"class_list":["post-1126","post","type-post","status-publish","format-standard","hentry","category-coding","tag-advent-of-code","tag-algorithms","tag-aoc2024","tag-graph","tag-programming","tag-swift"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/posts\/1126","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/comments?post=1126"}],"version-history":[{"count":1,"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/posts\/1126\/revisions"}],"predecessor-version":[{"id":1127,"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/posts\/1126\/revisions\/1127"}],"wp:attachment":[{"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/media?parent=1126"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/categories?post=1126"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/tags?post=1126"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}Graph<T><\/code> 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).<\/p>\n\n\n\n74,56,86,81,84,44,53,92,12,36,15,66,95,26,71<\/pre>\n\n\n\n
private func fix(_ pages: [Int], using graph: Graph<Int>) -> [Int] {\n var modPages = pages\n repeat {\n for index in 0..<modPages.count - 1 {\n let preceding = modPages[index]\n let following = modPages[index + 1]\n let edges = graph.edges(for: graph.vertex(for: preceding)!)?.map ( {$0.destination.item } )\n if edges != nil && !edges!.isEmpty {\n if !edges!.contains(following) {\n modPages.swapAt(index, index + 1)\n }\n } else {\n modPages.swapAt(index, index + 1)\n }\n }\n } while !isUpdateValid(modPages, graph)\n return modPages\n}<\/code><\/pre>\n\n\n\n$ 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.<\/pre>\n","protected":false},"excerpt":{"rendered":"