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
J
This is a problem where J’s biases lead one to a very different solution from most of the others. The natural representation of a directed graph in J is an adjacency matrix, and sorting is specified in terms of a permutation to apply rather than in terms of a comparator:
x /: y(respectivelyx \: y) determines the permutation that would putyin ascending (descending) order, then applies that permutation tox.data_file_name =: '5.data' lines =: cutopen fread data_file_name NB. manuals start with the first line where the index of a comma is < 5 start_of_manuals =: 1 i.~ 5 > ',' i.~"1 > lines NB. ". can't parse the | so replace it with a space edges =: ". (' ' & (2}))"1 > start_of_manuals {. lines NB. don't unbox and parse yet because they aren't all the same length manuals =: start_of_manuals }. lines max_page =: >./ , edges NB. adjacency matrix of the page partial ordering; e.i. makes identity matrix adjacency =: 1 (< edges)} e. i. >: max_page NB. ordered line is true if line is ordered according to the adjacency matrix ordered =: monad define pages =. ". > y NB. index pairs 0 <: i < j < n; box and raze to avoid array fill page_pairs =. ; (< @: (,~"0 i.)"0) i. # pages */ adjacency {~ <"1 pages {~ page_pairs ) midpoint =: ({~ (<. @: -: @: #)) @: ". @: > result1 =: +/ (ordered"0 * midpoint"0) manuals NB. toposort line yields the pages of line topologically sorted by adjacency NB. this is *not* a general topological sort but works for our restricted case: NB. we know that each individual manual will be totally ordered toposort =: monad define pages =. ". > y NB. for each page, count the pages which come after it, then sort descending pages \: +/"1 adjacency {~ <"1 pages ,"0/ pages ) NB. midpoint2 doesn't parse, but does remove trailing zeroes midpoint2 =: ({~ (<. @: -: @: #)) @: ({.~ (i. & 0)) result2 =: +/ (1 - ordered"0 manuals) * midpoint2"1 toposort"0 manuals