Day 5: Print Queue
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
Uiua
Well it’s still today here, and this is how I spent my evening. It’s not pretty or maybe even good, but it works on the test data…
spoiler
Uses Kahn’s algorithm with simplifying assumptions based on the helpful nature of the data.
Try it here
Data ← ⊜(□)⊸≠@\n "47|53\n97|13\n97|61\n97|47\n75|29\n61|13\n75|53\n29|13\n97|29\n53|29\n61|53\n97|53\n61|29\n47|13\n75|47\n97|75\n47|61\n75|61\n47|29\n75|13\n53|13\n\n75,47,61,53,29\n97,61,53,29,13\n75,29,13\n75,97,47,61,53\n61,13,29\n97,13,75,29,47" Rs ← ≡◇(⊜⋕⊸≠@|)▽⊸≡◇(⧻⊚⌕@|)Data Ps ← ≡⍚(⊜⋕⊸≠@,)▽⊸≡◇(¬⧻⊚⌕@|)Data NoPred ← ⊢▽:⟜(≡(=0/+⌕)⊙¤)◴♭⟜≡⊣ # Find entry without predecessors. GetLead ← ⊸(▽:⟜(≡(¬/+=))⊙¤)⟜NoPred # Remove that leading entry. Rules ← ⇌⊂⊃(⇌⊢°□⊢|≡°□↘1)[□⍢(GetLead|≠1⧻)] Rs # Repeatedly find rule without predecessors (Kaaaaaahn!). Sorted ← ⊏⍏⊗,Rules IsSorted ← /×>0≡/-◫2⊗°□: Rules MidVal ← ⊡:⟜(⌊÷ 2⧻) ⇌⊕□⊸≡IsSorted Ps # Group by whether the pages are in sort order. ≡◇(/+≡◇(MidVal Sorted)) # Find midpoints and sum.Does this language ever look pretty? Great for signaling UFOs though :D
Those unicode code points won’t use themselves.
Ah, but the terseness of the code allows the beauty of the underlying algorithm to shine through :-)
Oh my. I just watched yernab’s video, and this becomes so much easier:
# Order is totally specified, so sort by number of predecessors, # check to see which were already sorted, then group and sum each group. Data ← ⊜(□⊜□⊸≠@\n)⊸(¬⦷"\n\n")"47|53\n97|13\n97|61\n97|47\n75|29\n61|13\n75|53\n29|13\n97|29\n53|29\n61|53\n97|53\n61|29\n47|13\n75|47\n97|75\n47|61\n75|61\n47|29\n75|13\n53|13\n\n75,47,61,53,29\n97,61,53,29,13\n75,29,13\n75,97,47,61,53\n61,13,29\n97,13,75,29,47" Rs ← ≡◇(⊜⋕⊸≠@|)°□⊢Data Ps ← ≡⍚(⊜⋕⊸≠@,)°□⊣Data ⊕(/+≡◇(⊡⌊÷2⧻.))¬≡≍⟜:≡⍚(⊏⍏/+⊞(∈Rs⊟)..).Ps