Run
aoc_source(day = 5, part = 1)
input = aoc_read(day = 5)
aoc_run(solve_day5_part1(input))Elapsed: 0.035 seconds
Memory: 1391 KB2024
Day 1 Day 2 Day 3 Day 4 Day 5 Day 6 Day 7 Day 8 Day 9 Day 10 Day 11 Day 12 Day 13 Day 14 Day 15 Day 16
— R Day 5 Part 1 —
#' Find the middle number of sorted lists
#'
#' Given a sort of page ordering pairs x|y where y is after x. Store each y
#' against the same x in an environment (as a hashmap).
#'
#' Given lists of page updates, check each page for breaching the ordering rules
#' stored in the hashmap. For any update that doesn't breach, we find its middle
#' page number and sum them.
#'
#' @param input
#' Character vector of lines read from input. It has two sections - page
#' ordering pairs and lists of page numbers.
#'
#' @return
#' The sum of middle numbers of sorted page update lists.
solve_day5_part1 <- function(input) {
sep <- which(nchar(input) == 0)
# ordering rules map ----
ordering <- input[1:(sep-1)]
ordering <- strsplit(ordering, "\\|")
# using an environment as a hash map
after_map <- new.env()
# for each x|y pair
# store y in the map against x as the key
for (i in seq_along(ordering)) {
pair <- ordering[[i]]
key <- pair[[1]]
value <- pair[[2]]
# we don't need to sort here, but I did for some quick visual scanning
after_map[[key]] <- sort(c(after_map[[key]], value))
}
# pages to produce in each update ----
updates <- input[(sep+1):length(input)]
updates <- strsplit(updates, ",")
# check and extract ----
# storage for middle page numbers
middle_nums <- numeric(length(updates))
# iterate to find correctly sorted page lists
for (i in seq_along(updates)) {
update <- updates[[i]]
if (is_sorted(updates[[i]], after_map)) {
# storing their middle numbers
middle_index <- ceiling(length(update) / 2)
middle_nums[[i]] <- as.numeric(update[[middle_index]])
}
}
sum(middle_nums)
}
#' Whether a sequence of pages is in order
#'
#' Working backwards from the last page in the update to the first. Check
#' the pages before it in the list against that pages after_map list. If
#' any page is before when it should be after, the list is not sorted
#'
#' @param update
#' Character vector of page numbers
#' @param after_map
#' Environment, key-value pairs where each value is a character vector of pages
#' that should come after the key
#'
#' @return
#' Logical whether the pages are in order
is_sorted <- function(update, after_map) {
for (i in seq(length(update), 1, -1)) {
check_num <- update[[i]]
to_check <- update[i:1]
if (any(to_check %in% after_map[[check_num]])) {
return(FALSE)
}
}
TRUE
}— R Day 5 Part 2 —
#' Find the middle number of unsorted lists
#'
#' Given a sort of page ordering pairs x|y where y is after x. Store each y
#' against the same x in an environment (as a hashmap).
#'
#' Given lists of page updates, check each page for breaching the ordering rules
#' stored in the hashmap. For any updates that *do* breach, we find its middle
#' page number and sum them.
#'
#' @param input
#' Character vector of lines read from input. It has two sections - page
#' ordering pairs and lists of page numbers.
#'
#' @return
#' The sum of middle numbers of unsorted page update lists.
solve_day5_part2 <- function(input) {
sep <- which(nchar(input) == 0)
# ordering rules map ----
ordering <- input[1:(sep-1)]
ordering <- strsplit(ordering, "\\|")
# using an environment as a hash map
after_map <- new.env()
# for each x|y pair
# store y in the map against x as the key
for (i in seq_along(ordering)) {
pair <- ordering[[i]]
key <- pair[[1]]
value <- pair[[2]]
# we don't need to sort here, but I did for some quick visual scanning
after_map[[key]] <- sort(c(after_map[[key]], value))
}
# pages to produce in each update ----
updates <- input[(sep+1):length(input)]
updates <- strsplit(updates, ",")
# check and extract ----
# storage for middle page numbers
middle_nums <- numeric(length(updates))
# iterate to find lists which aren't sorted
for (i in seq_along(updates)) {
update <- updates[[i]]
if (!is_sorted(updates[[i]], after_map)) {
# then sort them and store their middle page number
middle_nums[[i]] <- find_middle(update, after_map)
}
}
sum(middle_nums)
}
#' Whether a sequence of pages is in order
#'
#' Working backwards from the last page in the update to the first. Check
#' the pages before it in the list against that pages after_map list. If
#' any page is before when it should be after, the list is not sorted
#'
#' @param update
#' Character vector of page numbers
#' @param after_map
#' Environment, key-value pairs where each value is a character vector of pages
#' that should come after the key
#'
#' @return
#' Logical whether the pages are in order
is_sorted <- function(update, after_map) {
for (i in seq(length(update), 1, -1)) {
check_num <- update[[i]]
to_check <- update[i:1]
if (any(to_check %in% after_map[[check_num]])) {
return(FALSE)
}
}
TRUE
}
#' Find the middle number of a list
#'
#' @param page_list
#' Character vector of page numbers
#'
#' @param after_map
#' Environment, key-value pairs where each value is a character vector of pages
#' that should come after the key
#'
#' @return
#' numeric(1) the middle number
find_middle <- function(page_list, after_map) {
half <- floor(length(page_list)/2)
for (i in seq_along(page_list)) {
check_num <- page_list[[i]]
# how many pages come after the page we're checking
nums_after <- sum(page_list %in% after_map[[check_num]])
if (nums_after == half) {
return(as.numeric(check_num))
}
}
}Run
aoc_source(day = 5, part = 2)
input = aoc_read(day = 5)
aoc_run(solve_day5_part2(input))Elapsed: 0.084 seconds
Memory: 5100 KB— Python Day 5 Part 1 —
def solve_day5_part1(input):
input = [line.replace("\n", "") for line in input]
split_at = [i for i,v in enumerate(input) if v == ""]
split_at = int(split_at[0])
rules = input[0:split_at]
pages = input[split_at+1:len(input)]
# build page ordering rule lookup
rules = [rule.split("|") for rule in rules]
order_lookup = dict()
for rule in rules:
key = rule[0]
if key in order_lookup:
order_lookup[key].append(rule[1])
else:
order_lookup[key] = [(rule[1])]
# iterate over page sequences checking whether any are out of order
pages = [line.split(",") for line in pages]
pages_are_in_order = [are_pages_in_order(sequence, order_lookup) for sequence in pages]
pages_in_order = [v for i, v in enumerate(pages) if pages_are_in_order[i]]
middle_pages = [seq[(len(seq)-1)//2] for seq in pages_in_order]
middle_numbers = [int(page) for page in middle_pages]
print(sum(middle_numbers))
def are_pages_in_order(sequence, order_lookup):
for i in reversed(range(len(sequence))):
if i == 0:
break
key = sequence[i]
if key in order_lookup:
lookup = order_lookup[key]
else:
continue
for page_number in sequence[:i]:
if page_number in lookup:
return(False)
return(True)Run
aoc_source(day = 5, part = 1)
input = aoc_read(day = 5)
result = aoc_run("solve_day5_part1(input)")Elapsed: 0.014 seconds
Memory: 593 KB— Python Day 5 Part 2 —
def solve_day5_part2(input):
input = [line.replace("\n", "") for line in input]
split_at = [i for i,v in enumerate(input) if v == ""]
split_at = int(split_at[0])
rules = input[0:split_at]
pages = input[split_at+1:len(input)]
# build page ordering rule lookup
rules = [rule.split("|") for rule in rules]
order_lookup = dict()
for rule in rules:
key = rule[0]
if key in order_lookup:
order_lookup[key].append(rule[1])
else:
order_lookup[key] = [(rule[1])]
# iterate over page sequences checking whether any are out of order
pages = [line.split(",") for line in pages]
pages_are_in_order = [are_pages_in_order(sequence, order_lookup) for sequence in pages]
pages_not_in_order = [v for i, v in enumerate(pages) if not pages_are_in_order[i]]
middle_pages = [get_middle_number(seq, order_lookup) for seq in pages_not_in_order]
middle_numbers = [int(page) for page in middle_pages]
print(sum(middle_numbers))
def are_pages_in_order(sequence, order_lookup):
for i in reversed(range(len(sequence))):
if i == 0:
break
key = sequence[i]
if key in order_lookup:
lookup = order_lookup[key]
else:
continue
for page_number in sequence[:i]:
if page_number in lookup:
return(False)
return(True)
def get_middle_number(sequence, order_lookup):
middle_loc = (len(sequence)-1)//2
for i, v in enumerate(sequence):
later_numbers = [page for page in sequence if page in order_lookup[v]]
if len(later_numbers) == middle_loc:
return(v)
print("oops")
Run
aoc_source(day = 5, part = 2)
input = aoc_read(day = 5)
result = aoc_run("solve_day5_part2(input)")5273
Elapsed: 0.013 seconds
Memory: 594 KB