Last active
December 26, 2022 16:45
-
-
Save markjenkins/89208994fdc78b102d8daae7703c5223 to your computer and use it in GitHub Desktop.
Advent of Code 2022 https://adventofcode.com/2022/
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python3 | |
# https://adventofcode.com/2022/day/1 Parts 1 and 2 with constant memory | |
# Mark Jenkins | |
from heapq import nlargest | |
def gen_elf_lines(): | |
"""a generator of consecutive elf lines, converted to int | |
call multiple times to get different elves, won't yield at all | |
(StopIteration exception) when there are no more. | |
Elves line items with value zero are included, so don't assume | |
sum(gen_elf_lines())==0 means end of file | |
""" | |
while True: | |
try: | |
yield int(input()) | |
# catching ValueError covers the blank lines, EOFError covers | |
# when we reach end of file | |
except (ValueError, EOFError): | |
break # while True | |
def gen_elf_sums(): | |
"""A generator of elf sums. | |
Uses constant memory, one elf with many items is fine | |
""" | |
while True: # StopIteration exception will stop this loop | |
# we test for more input by starting with one line | |
# StopIteration will be raised if we're all out | |
# | |
# this apprach supports 0 as an allowable input | |
# otherwise we would just sum(gen_elf_lines()) and stop when 0 hit | |
elf_line_gen = iter(gen_elf_lines()) | |
try: | |
first_elf_line = next(elf_line_gen) # raises StopIteration | |
except StopIteration: | |
break | |
yield sum(elf_line_gen, first_elf_line) | |
def part_1(): | |
return max(gen_elf_sums()) | |
# Part 2 code starts here | |
def n_largest_elves(n): | |
"""Find the n largest elves | |
Uses constant memory by using a heap priority queue of size n""" | |
return nlargest(n, gen_elf_sums()) | |
def sum_n_largest_elves(n): | |
"""Find the sum of the n largest elves. | |
Uses constant memory regardless of how many elves there are and | |
how many items they have""" | |
return sum(n_largest_elves(n)) | |
def part_2(): | |
return sum_n_largest_elves(3) | |
def print_part_1_and_2_combined(): | |
top_3_elves = n_largest_elves(3) | |
# use max for largest elf (part 1) because top_3_elves is not sorted | |
# but has heap invariant | |
print( "largest elf for part one: %d" % max(top_3_elves) ) | |
print( "top three elves sum for part two: %d" % sum(top_3_elves) ) | |
if __name__ == "__main__": | |
#print(part_1()) | |
#print(part_2()) | |
# comment this line and uncomment one of the above if you just | |
# want part 1 or 2 | |
print_part_1_and_2_combined() |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python3 | |
# https://adventofcode.com/2022/day/1 part one | |
def gen_elf_lines(): | |
while True: | |
try: | |
yield int(input()) | |
except (ValueError, EOFError): | |
break | |
def gen_elf_sums(): | |
while True: | |
elf_line_gen = iter(gen_elf_lines()) | |
try: | |
first_elf_line = next(elf_line_gen) | |
except StopIteration: | |
break | |
yield sum(elf_line_gen, first_elf_line) | |
if __name__ == "__main__": | |
print(max(gen_elf_sums())) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env guile | |
!# | |
;;; https://adventofcode.com/2022/day/1 part one | |
(use-modules (ice-9 rdelim) (srfi srfi-1)) | |
;;; we read all lines backwards because we can use | |
;;; this bare bones definition of unfold-right | |
;;; (simplified version of the one in the guile manual) | |
;;;(define (unfold-right p f g seed) | |
;;; (let lp ((seed seed) (lis '() )) | |
;;; (if (p seed) lis | |
;;; (lp (g seed) | |
;;; (cons (f seed) lis))))) | |
;;; | |
;;; The order of the lines in this problem isn't relevant | |
(define (read_all_lines_backwards) | |
(unfold-right eof-object? identity (lambda (x) (read-line)) (read-line)) ) | |
(define (not_empty_line_or_end_of_list x) | |
(not (or (equal? "" x) (null? x)) )) | |
(define (sum_until_blankline_or_end_of_list l) | |
(reduce + 0 (map string->number | |
(take-while not_empty_line_or_end_of_list l)))) | |
(define (skip_until_after_blankline_or_end_of_list l) | |
(let ((l_after_skip (drop-while not_empty_line_or_end_of_list l))) | |
(if (null? l_after_skip) | |
l_after_skip | |
(cdr l_after_skip) ))) | |
(define (sum_elfs elf_lines) | |
;; again, unfold-right, no need for the greater sophistication of fold | |
;; or reversing the list from unfold-right | |
(unfold-right null? ; predicate p | |
sum_until_blankline_or_end_of_list ; next list item f | |
skip_until_after_blankline_or_end_of_list ; seed updater g | |
elf_lines )) ; seed | |
(define elf_sums (sum_elfs (read_all_lines_backwards)) ) | |
(write-line (reduce max "no elves found" elf_sums) ) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python3 | |
# https://adventofcode.com/2022/day/1 part two | |
from aoc2022_day01_p1 import gen_elf_sums | |
from heapq import nlargest | |
print( sum(nlargest(3, gen_elf_sums())) ) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env guile | |
!# | |
(use-modules (srfi srfi-1)) | |
;;; https://adventofcode.com/2022/day/1 part two | |
(include "aoc2022_d01p1.scm") | |
(define (merge_item_into_list_and_drop_lowest i l) | |
(cdr (merge l (list i) <))) | |
(define (nlargest n l) | |
(fold merge_item_into_list_and_drop_lowest | |
(sort (take l n) <) ; initial list, first n items sorted | |
(drop l n) ) ) ; remaining items after n | |
(write-line (reduce + "no elves found" (nlargest 3 elf_sums) ) ) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python3 | |
# https://adventofcode.com/2022/day/2 part one | |
from sys import stdin | |
ROCK, PAPER, SCIS = (1, 2, 3) | |
OP_TABLE = {"A": ROCK, | |
"B": PAPER, | |
"C": SCIS, | |
} | |
REPLY_TABLE = {"X": ROCK, | |
"Y": PAPER, | |
"Z": SCIS, | |
} | |
LOSS, DRAW, WIN = (0, 3, 6) | |
def decode_strat_line(line, left_table=OP_TABLE, right_table=REPLY_TABLE): | |
op, reply = line.strip().split(" ") | |
return (left_table[op], right_table[reply]) | |
def gen_input_pairs(left_table=OP_TABLE, right_table=REPLY_TABLE): | |
for line in stdin: | |
yield decode_strat_line( | |
line, left_table=left_table, right_table=right_table) | |
def is_draw(op, reply): | |
return op==reply | |
def is_win(op, reply): | |
return ( (op==SCIS and reply==ROCK) or | |
(not (op==ROCK and reply==SCIS) and op<reply )) | |
def score_outcome(op, reply): | |
return ( DRAW if is_draw(op, reply) | |
else (WIN if is_win(op, reply) else LOSS) ) | |
def score_round(op,reply): | |
return score_outcome(op,reply) + reply | |
if __name__ == "__main__": | |
print( sum( score_round(op, reply) | |
for op, reply in gen_input_pairs() ) ) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env guile | |
!# | |
;;; https://adventofcode.com/2022/day/2 part one | |
;;; based on this solution: | |
;;; https://dev.to/nickymeuleman/advent-of-code-2022-day-2-3b18 | |
(use-modules (ice-9 rdelim) (srfi srfi-1)) | |
;;; we read all lines backwards because we can use | |
;;; this bare bones definition of unfold-right | |
;;; (simplified version of the one in the guile manual) | |
;;;(define (unfold-right p f g seed) | |
;;; (let lp ((seed seed) (lis '() )) | |
;;; (if (p seed) lis | |
;;; (lp (g seed) | |
;;; (cons (f seed) lis))))) | |
;;; | |
;;; The order of the lines in this problem isn't relevant | |
(define (read_all_lines_backwards) | |
(unfold-right eof-object? identity (lambda (x) (read-line)) (read-line)) ) | |
(define (convert_line_to_int_pair line) | |
(let ((line_parts (string->list line))) | |
(cons (- (char->integer (car line_parts) ) (char->integer #\A)) | |
(- (char->integer (caddr line_parts) ) (char->integer #\X)) ))) | |
(define (lines_as_int_pairs l) | |
(map convert_line_to_int_pair l) ) | |
(define (outcome opponent my_reply) | |
(modulo (+ my_reply (- opponent) 1) 3) ) | |
(define (outcome_score opponent my_reply) | |
(* 3 (outcome opponent my_reply))) | |
(define (score_outcome_and_my_play opponent my_reply) | |
(+ (+ 1 my_reply) (outcome_score opponent my_reply) )) | |
(define input_lines | |
(lines_as_int_pairs (read_all_lines_backwards) )) | |
(define (perform_scoring_with f input_line_pairs) | |
(map (lambda (x) (f (car x) (cdr x))) | |
input_line_pairs) ) | |
(write-line (reduce | |
+ | |
"no lines" | |
(perform_scoring_with score_outcome_and_my_play input_lines) )) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python3 | |
# https://adventofcode.com/2022/day/2 part two | |
#from sys import stdin | |
from aoc2022_d02p1 import \ | |
LOSS, DRAW, WIN, \ | |
ROCK, PAPER, SCIS, \ | |
gen_input_pairs, score_outcome, score_round | |
RPS = (ROCK, PAPER, SCIS) | |
LDW = (LOSS, DRAW, WIN) | |
OUTCOME_TABLE = {"X": LOSS, | |
"Y": DRAW, | |
"Z": WIN} | |
def find_reply_for_outcome(op, outcome): | |
for reply in RPS: | |
if outcome == score_outcome(op, reply): | |
return reply | |
# find_reply_for_outcome(op, outcome) is fast enough, but we build | |
# a cache of nsted lists WINNING_REPLY_CACHE[op][outcome] | |
# to show how such a thing can be done | |
# | |
# because ROCK, PAPER, SCIS are 1-3, we put None in the 0th entry | |
WINNING_REPLY_CACHE = [None] | |
# then we add entries 1-3 | |
WINNING_REPLY_CACHE.extend( [ | |
# our inner list is indexed with all the outcomes | |
# because these are 0, 3, and 6 we put None in the other spots | |
[(None if outcome not in LDW # not 0, 3, or 6 | |
else find_reply_for_outcome(op, outcome) ) | |
for outcome in range(max(LDW)+1)] | |
for op in RPS ]) | |
# WINNING_REPLY_CACHE[1] is [3, None, None 1, None, None 2] for example | |
print( sum( score_round(op, WINNING_REPLY_CACHE[op][outcome] ) | |
for op, outcome in gen_input_pairs(right_table=OUTCOME_TABLE) ) ) | |
# without the cache is similar | |
#print( sum( score_round(op, find_reply_for_outcome(op,outcome) ) | |
# for op, outcome in gen_input_pairs(right_table=OUTCOME_TABLE) ) ) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env guile | |
!# | |
;;; https://adventofcode.com/2022/day/2 part two | |
;;; based on this solution: | |
;;; https://dev.to/nickymeuleman/advent-of-code-2022-day-2-3b18 | |
(include "aoc2022_d02p1.scm") | |
(define (compute_my_play_and_score_outcome opponent outcome) | |
(score_outcome_and_my_play | |
opponent | |
(modulo (+ opponent -1 outcome) 3) )) | |
(write-line (reduce | |
+ | |
"no lines" | |
(perform_scoring_with | |
compute_my_play_and_score_outcome | |
input_lines) )) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python3 | |
from sys import stdin | |
def problem_input(): | |
for line in stdin: | |
line = line.strip() | |
p = len(line)//2 # partition_index | |
first_h, second_h = set(line[0:p]), set(line[p:]) | |
r = first_h.intersection(second_h) | |
assert(len(r)==1) # saved me during my "speed"-run | |
yield r.pop() | |
def prio(common_item): | |
return ord(common_item) + ( | |
1-ord("a") if common_item.islower() else 27-ord("A") ) | |
if __name__ == "__main__": | |
print( sum( prio(i) for i in problem_input() ) ) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env guile | |
!# | |
;;; https://adventofcode.com/2022/day/3 part one | |
(use-modules (ice-9 rdelim) (srfi srfi-1)) | |
(define (read_all_lines_backwards) | |
(unfold-right eof-object? identity (lambda (x) (read-line)) (read-line)) ) | |
;;; TODO, re-implement without (define-values) (split-at) and | |
;;; multiple return values concept | |
(define (split_at_to_pair l n) | |
(define-values (x y) (split-at l n)) | |
(cons x y) ) | |
(define (split_line_list_in_half line_as_list) | |
(split_at_to_pair line_as_list (/ (length line_as_list) 2))) | |
(define (lines_to_lists lines) | |
(map string->list lines) ) | |
(define (partition_all_lines lines) | |
(map split_line_list_in_half (lines_to_lists lines)) ) | |
(define (find_unique_char_to_pair p) | |
(let ((p_intersect (char-set-intersection (list->char-set (car p)) | |
(list->char-set (cdr p)) )) ) | |
(char-set-ref p_intersect (char-set-cursor p_intersect) ))) | |
(define (find_chars_uniq_to_partition partitioned_lines) | |
(map find_unique_char_to_pair partitioned_lines) ) | |
;;; after subtracting ascii codes for a or A we scale to 0 | |
(define LOWER_CASE_FACTOR (- (char->integer #\a) 1) ) ; 0-25 -> 1-26 | |
(define UPPER_CASE_FACTOR (- (char->integer #\A) 27) ) ; 0-25-> 27-52 | |
(define (priority c) | |
(- (char->integer c) | |
(if (char-lower-case? c) LOWER_CASE_FACTOR UPPER_CASE_FACTOR))) | |
(define input_lines (read_all_lines_backwards) ) | |
(write-line | |
(reduce + "no lines found" | |
(map priority | |
(find_chars_uniq_to_partition | |
(partition_all_lines input_lines) ) )) ) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python3 | |
from aoc2022_d03p1 import prio | |
from functools import reduce | |
from operator import and_ as set_intersection | |
from sys import stdin | |
def problem_input(): | |
input_sets_iter = iter(set(line.strip()) for line in stdin) | |
# instead of line at a time, triplet at a time | |
return zip(input_sets_iter, input_sets_iter, input_sets_iter) | |
# original version | |
#def problem_input(): | |
# while True: | |
# try: | |
# yield [set(input()) for i in range(3)] | |
# except EOFError: | |
# break # end while True | |
def find_common_item_in_sets(l): | |
return reduce(set_intersection, l).pop() | |
print( sum( | |
prio(find_common_item_in_sets(l)) for l in problem_input() ) ) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env guile | |
!# | |
;;; https://adventofcode.com/2022/day/3 part two | |
(include "aoc2022_d03p1.scm") | |
(define (combine_line_triplet t) | |
(let ((cs (reduce char-set-intersection #\nul | |
(map string->char-set t) ))) | |
(char-set-ref cs (char-set-cursor cs) ))) | |
(define (collapse_line_list_by_threes lines) | |
(unfold-right null? ; p predicate | |
;; f match each seed to list element | |
(lambda (x) | |
(combine_line_triplet (take x 3) ) ) | |
(lambda (x) (drop x 3)) ; g map each seed to next seed | |
lines ) ) ; initial seed | |
(write-line | |
(reduce + "no lines found" | |
(map priority (collapse_line_list_by_threes input_lines ) ))) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python3 | |
# https://adventofcode.com/day/4 part 1 | |
from sys import stdin | |
def problem_input(): | |
return ( | |
# each line of input results in a pair of pairs (nested lists) | |
# achieved below with nested list comprehensions | |
[ [int(id_num) for id_num in elf_range.split("-")] | |
for elf_range in line.strip().split(",") ] | |
for line in stdin ) | |
def prepend_length_to_pair(id_pair): | |
return (id_pair[1] - id_pair[0], id_pair[0], id_pair[1]) | |
def length_tagged_id_ranges(problem_input): | |
return ( | |
sorted( (prepend_length_to_pair(line_pair[0]), | |
prepend_length_to_pair(line_pair[1])) ) | |
for line_pair in problem_input ) | |
def gen_one_for_fully_overlapping_pairs(length_tagged_pairs): | |
return ( | |
1 | |
for ( (e1_len, e1_start, e1_end), | |
(e2_len, e2_start, e2_end) ) in length_tagged_pairs | |
if e1_start >= e2_start and e1_end <= e2_end ) | |
if __name__ == "__main__": | |
print( sum( gen_one_for_fully_overlapping_pairs( | |
length_tagged_id_ranges(problem_input()) ) ) ) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python3 | |
# https://adventofcode.com/day/4 part 2 | |
from aoc2022_d04p1 import problem_input | |
def gen_one_for_overlapping_pairs(pairs): | |
return ( | |
1 | |
for ( (e1_start, e1_end), | |
(e2_start, e2_end) ) in pairs | |
if ( (e2_start <= e1_start <= e2_end) or | |
(e1_start <= e2_start <= e1_end) ) ) | |
if __name__ == "__main__": | |
print( sum( gen_one_for_overlapping_pairs(problem_input()) ) ) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env guile | |
!# | |
;;; https://adventofcode.com/2022/day/5 part one | |
(use-modules (ice-9 rdelim) (srfi srfi-1)) | |
(define (read_all_lines_backwards) | |
(unfold-right eof-object? identity (lambda (x) (read-line)) (read-line)) ) | |
;;; TODO, re-implement without (define-values) (span) and | |
;;; multiple return values concept | |
(define (span_to_pair pred l) | |
(define-values (x y) (span pred l)) | |
(cons x y) ) | |
;;; TODO, re-implement without (define-values) (split-at) and | |
;;; multiple return values concept | |
(define (split-at-to-pair l n) | |
(define-values (x y) (split-at l n)) | |
(cons x y) ) | |
(define (convert_move_param_and_subtract move subval) | |
(- (string->number move) subval)) | |
;;; parse a move line into a triplet (cons magnitude (cons start end)) | |
;;; with each of the numbers converted and 1 subtracted from the indicies | |
(define (parse_move_line line) | |
(let ((split_move_line (string-split line #\space))) | |
(cons (string->number (second split_move_line)) | |
(map (lambda (x) (- (string->number x) 1)) | |
(list (fourth split_move_line) | |
(sixth split_move_line) ))))) | |
(define move_t_magnitude first) | |
(define move_t_start second) | |
(define move_t_end third) | |
(define (parse_state_line state_line) | |
(unfold null? ; p | |
second ; f, function to get list value(aka cadr) | |
(lambda (x) (drop x 4)) ; g to get next | |
;; after converting our line to a list of char | |
;; we add a space so as to be able to iterate 4 chars at a time | |
(append (string->list state_line) (list #\space) ))) | |
(define (n_empty_lists n) | |
;; unfold-right used on the assumption unfold-right is more performant | |
;; on bad implementations where unfold is defined as a reverse of unfold | |
(unfold-right (lambda (i) (= i n)) ; p | |
(lambda (i) '() ) ; f, function to create value | |
(lambda (i) (+ i 1) ); g function taking us to the next step | |
0 )); seed | |
(define (reconstruct_initial_stacks state_line stacks) | |
(unfold (lambda (x) (null? (car x))) ; p | |
;; function f | |
;; extend an individual stack with the relevant line component | |
;; as long as it is not a space | |
(lambda (x) | |
(let* ((line_prog (car x)) | |
(line_prog_c (car line_prog)) | |
(old_stacks (cdr x)) ) | |
(if (equal? line_prog_c #\space) | |
(car old_stacks) | |
(cons line_prog_c | |
(car old_stacks)) ))) | |
;; function g | |
;; advance our unfold state pair to have the next line component | |
;; and the next piece of old stack | |
(lambda (x) | |
(let ((line_prog (car x)) | |
(old_stacks (cdr x)) ) | |
(cons (cdr line_prog) | |
(cdr old_stacks) ))) ; g | |
;; seed pair | |
(cons state_line ; line_prog | |
stacks) )) ; old_stacks | |
(define (construct_initial_stacks state_lines_backwards num_col) | |
(fold reconstruct_initial_stacks ; proc | |
(n_empty_lists num_col) ; init | |
state_lines_backwards )) ; lst1 | |
(define stack_adding_function append-reverse) | |
(define (simulate_drop_on stacks target items) | |
(let* ((pair_before_push (split-at-to-pair stacks target)) | |
(first_half_of_stacks (car pair_before_push)) | |
(second_half_of_stacks (cdr pair_before_push)) | |
(selected_stack (car second_half_of_stacks)) | |
(rest_of_second_half_of_stacks (cdr second_half_of_stacks)) ) | |
(append first_half_of_stacks | |
(list (stack_adding_function items selected_stack)) | |
rest_of_second_half_of_stacks) )) | |
(define (simulate_pop_off stacks magnitude start end) | |
(let* ((pair_before_pop (split-at-to-pair stacks start)) | |
(first_half_of_stacks (car pair_before_pop)) | |
(second_half_of_stacks (cdr pair_before_pop)) | |
(selected_stack (car second_half_of_stacks)) | |
(rest_of_second_half_of_stacks (cdr second_half_of_stacks)) | |
(items_from_selected_stack (take selected_stack magnitude)) | |
(remainder_of_selected_stack (drop selected_stack magnitude)) ) | |
(list | |
; stacks | |
(append first_half_of_stacks | |
(list remainder_of_selected_stack) | |
rest_of_second_half_of_stacks) | |
end | |
items_from_selected_stack) )) | |
(define (simulate_move stacks magnitude start end) | |
(apply simulate_drop_on (simulate_pop_off stacks magnitude start end) )) | |
(define input_pair (span_to_pair (lambda (x) (string-prefix? "move" x)) | |
(read_all_lines_backwards) ) ) | |
;;; by using unfold-right we restore the move order | |
;;; could have also done | |
;;; (map parse_move_line (reverse (car input_pair))) | |
;;; to achieve the same result | |
(define moves (unfold-right null? ; p | |
(lambda (x) (parse_move_line (car x))) ; f | |
cdr ; g | |
(car input_pair) )) ; seed | |
;;; use cddr top drop the bottom two lines (labels and blank) | |
(define initial_state_lines_backwards (cddr (cdr input_pair))) | |
(define label_line (cadr (cdr input_pair))) | |
(define num_col | |
(string->number (cadr (reverse (string-split label_line #\space))))) | |
(define parsed_initial_state_lines_backwards | |
(map parse_state_line initial_state_lines_backwards)) | |
(define initial_stacks (construct_initial_stacks | |
parsed_initial_state_lines_backwards num_col)) | |
(define final_stacks | |
(fold | |
;; procedure proc generates a new set of stacks for a given 3-item move | |
(lambda (move stacks) (apply simulate_move stacks move )) | |
initial_stacks ; init | |
moves ) ) | |
(write-line (list->string (map car final_stacks) )) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env guile | |
!# | |
;;; https://adventofcode.com/2022/day/5 part two | |
(include "aoc2022_d05p1.scm") | |
(define (simulate_drop_on stacks target items) | |
(let* ((pair_before_push (split-at-to-pair stacks target)) | |
(first_half_of_stacks (car pair_before_push)) | |
(second_half_of_stacks (cdr pair_before_push)) | |
(selected_stack (car second_half_of_stacks)) | |
(rest_of_second_half_of_stacks (cdr second_half_of_stacks)) ) | |
(append first_half_of_stacks | |
(list (append items selected_stack)) | |
rest_of_second_half_of_stacks) )) | |
;; this is the change from part one to two, use of append | |
;; in building the new stack (add list on top) | |
;; instead of append-reverse which reverses the items before | |
;; putting them on top | |
(define stack_adding_function append) | |
(define final_stacks | |
(fold | |
;; procedure proc generates a new set of stacks for a given 3-item move | |
(lambda (move stacks) (apply simulate_move stacks move )) | |
initial_stacks ; init | |
moves ) ) | |
(write-line (list->string (map car final_stacks) )) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env guile | |
!# | |
;;; https://adventofcode.com/2022/day/6 part one | |
(use-modules (ice-9 rdelim) (srfi srfi-1)) | |
(define problem_input (string->list (read-line))) | |
(define (start_condition? so_far) | |
(= (length so_far) | |
(char-set-size (list->char-set so_far) ))) | |
(define (recursive_check so_far l count) | |
(if (start_condition? so_far) | |
count | |
(recursive_check (append (cdr so_far) (list (car l))) | |
(cdr l) | |
(+ count 1) ))) | |
(write-line (recursive_check (take problem_input 4) | |
(drop problem_input 4) | |
4)) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env guile | |
!# | |
;;; https://adventofcode.com/2022/day/6 part two | |
(include "aoc2022_d06p1.scm") | |
(write-line (recursive_check (take problem_input 14) | |
(drop problem_input 14) | |
14)) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python3 | |
# https://adventofcode.com/2022/day/7 part 1 | |
# Mark Jenkins <mark@parit.ca> | |
from collections import namedtuple | |
from sys import stdin | |
Node = namedtuple('Node', ['dirname', 'contents']) | |
Leaf = namedtuple('Leaf', ['filename', 'size']) | |
def init_empty_node(dirname): | |
return Node(dirname, {}) | |
def tokenize_line(line): | |
parts = line.split(" ") | |
return tuple( (p if not p.isdigit() else int(p)) | |
for p in parts ) | |
problem_input = [tokenize_line(line.strip()) for line in stdin] | |
problem_input.reverse() | |
# SantaFS traversal must start at the root | |
assert( ("$", "cd", "/") == problem_input.pop() ) # first list is cd | |
root_node = init_empty_node('') | |
def parse_ls_output(problem_input): | |
while(len(problem_input)>0): | |
p = problem_input.pop() | |
if p[0] == "$": | |
problem_input.append(p) | |
break | |
elif p[0] == "dir": | |
n = init_empty_node(p[1]) | |
yield (n.dirname, n) | |
else: | |
l = Leaf(*reversed(p)) # reverse for filename, size | |
yield (l.filename, l) | |
def recursively_build_santa_fs(current_node, problem_input): | |
while(len(problem_input)>0): | |
p = problem_input.pop() | |
prompt, command = p[:2] | |
assert(prompt=="$") | |
if command == "ls": | |
current_node.contents.update( parse_ls_output(problem_input) ) | |
elif ("cd", "..") == p[1:3]: | |
break | |
# a request to cd to / will break the whole recursion | |
# though this appears to be only on the first line | |
# so we could have just done an | |
# assert this wasn't so | |
elif ("cd", "/") == p[1:3]: | |
problem_input.append(p) | |
break | |
else: | |
assert( command == "cd" ) | |
recursively_build_santa_fs( current_node.contents[p[2]], | |
problem_input ) | |
# this function isn't used, but it helps illustrate things | |
# hoarding it in case SantaFS comes back | |
def recursively_pretty_print_santa_fs(current_node=root_node, pad=""): | |
print( pad + "dir", current_node.dirname ) | |
for blah in current_node.contents.values(): | |
if isinstance(blah, Node): | |
recursively_pretty_print_santa_fs(blah, pad + " ") | |
else: | |
assert( isinstance(blah, Leaf) ) | |
print( pad + "file", blah) | |
print( pad + "done with", current_node.dirname, "going back up") | |
def recursively_find_dir_sums(current_node=root_node): | |
files_in_this_dir = [stuff | |
for stuff in current_node.contents.values() | |
if isinstance(stuff, Leaf) ] | |
sum_of_files_in_this_dir = sum( stuff.size | |
for stuff in current_node.contents.values() | |
if isinstance(stuff, Leaf) ) | |
return sum( recursively_find_dir_sums(dirnode) | |
for dirnode in current_node.contents.values() | |
if isinstance(dirnode, Node) ) + sum_of_files_in_this_dir | |
def recursively_find_dirs_with_criteria(criteria, current_node=root_node): | |
if criteria(current_node): | |
yield current_node | |
for dirnode in current_node.contents.values(): | |
if isinstance(dirnode, Node): | |
yield from (recursively_find_dirs_with_criteria(criteria, dirnode)) | |
santa_fs = recursively_build_santa_fs(root_node, problem_input) | |
if __name__ == "__main__": | |
print(sum( | |
recursively_find_dir_sums(dirnode) | |
for dirnode in recursively_find_dirs_with_criteria( | |
# criteria | |
lambda node: recursively_find_dir_sums(node) <= 100000 ) )) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from aoc2022_d07p1 import ( | |
recursively_find_dirs_with_criteria, | |
recursively_find_dir_sums, | |
) | |
SPACE_AVAILABLE = 70000000 | |
UNUSED_TARGET = 30000000 | |
CURRENT_USED = recursively_find_dir_sums() | |
CURRENT_UNUSED = SPACE_AVAILABLE - CURRENT_USED | |
FREE_TARGET = UNUSED_TARGET - CURRENT_UNUSED | |
print(min( | |
recursively_find_dir_sums(dirnode) | |
for dirnode in recursively_find_dirs_with_criteria( | |
# criteria | |
lambda node: recursively_find_dir_sums(node) >= FREE_TARGET ) )) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env guile | |
!# | |
;;; https://adventofcode.com/2022/day/8 part one | |
(use-modules (ice-9 rdelim) (srfi srfi-1)) | |
(define (read_all_lines_backwards) | |
(unfold-right eof-object? identity (lambda (x) (read-line)) (read-line)) ) | |
(define input_lines_backwards (read_all_lines_backwards) ) | |
(define ASCII_ZERO (char->integer #\0)) | |
(define (input_char_to_number x) | |
(- (char->integer x) ASCII_ZERO)) | |
(define (replace_list_with_empty_lists l) | |
(map (lambda (x) '()) l) ) | |
(define (build_cols_out_of_row row cols_so_far) | |
(map (lambda (pair) (apply cons pair)) | |
(zip row cols_so_far) )) | |
(define (matrix_transpose matrix) | |
;; use fold-right because each final row (original cols) is built backwards | |
;; (map reverse (fold ... )) would also work | |
(fold-right build_cols_out_of_row ; proc | |
(replace_list_with_empty_lists matrix) ; init | |
matrix )) ; lst | |
(define row_col | |
(unfold-right null? ; p | |
;; f | |
(lambda (seed) | |
(map input_char_to_number | |
(string->list (car seed) ) )) | |
cdr ;; g | |
input_lines_backwards )) ; seed | |
(define col_row (matrix_transpose row_col)) | |
;;;(write-line row_col) | |
;;;(write-line col_row) | |
(define (item_on_edge? surroundings) | |
(any null? surroundings) ) | |
(define (analyze_item item items_left items_right items_above items_below) | |
(begin | |
;;(write-line (list "analyze_item: " item "\n" | |
;;"items_left:" items_left "items_right:" items_right "\n" | |
;; "items_above:" items_above "items_below:"items_below )) | |
(if (item_on_edge? | |
(list items_left items_right items_above items_below)) | |
1 | |
0 ) )) | |
(define (analyse_row row all_cols_above all_cols_below) | |
(begin | |
;;;(write-line | |
;;; (list "analysze," | |
;;; "row:" row "\n" | |
;;;"all_cols_above:" all_cols_above "\n" | |
;;;"all_cols_below:" all_cols_below) ) | |
(unfold (lambda (seed) (null? (fourth seed))) ; p | |
;; f | |
(lambda (seed) | |
(analyze_item | |
(car (fourth seed)) ; item | |
(third seed) ; items left | |
(cdr (fourth seed)) ; items_right, exclude current | |
(car (first seed)) ; items_above | |
(car (second seed)) )); items_below | |
;; g | |
(lambda (seed) | |
(let ((cols_above (first seed)) | |
(cols_below (second seed)) | |
(items_before (third seed)) | |
(item_and_items_after (fourth seed))) | |
(begin | |
;;(write-line (list "g" | |
;; cols_above cols_below | |
;; items_before item_and_items_after)) | |
;; rebuild seed | |
(list (cdr cols_above) | |
(cdr cols_below) | |
(cons (car item_and_items_after) items_before) | |
(cdr item_and_items_after) ) ))) | |
;; seed | |
(list all_cols_above all_cols_below '() row) ))) | |
(define (analyze_forest) | |
(unfold (lambda (seed) | |
(begin | |
;;;(write-line (list "p" | |
;;; (first seed) | |
;;; (second seed) | |
;;; (third seed) )) | |
(null? (first seed)) )) ; p | |
;; f | |
(lambda (seed) | |
(analyse_row (car (first seed) ) ; row | |
(second seed) ; all_cols_above | |
(map cdr (third seed)) ) ) ; all_cols_below | |
;; g | |
(lambda (seed) | |
(begin | |
;;;(write-line (list "forest G:" | |
;;; (first seed) | |
;;; (second seed) | |
;;; (third seed))) | |
(list (cdr (first seed)) | |
(map (lambda (x y) | |
(cons (car y) x) | |
) (second seed) (third seed) ) | |
(map cdr (third seed)) ))) | |
;; seed | |
(list row_col ; rows | |
(replace_list_with_empty_lists col_row) | |
col_row) )) ; current_cols_and_after | |
;;;(write-line (analyse_row (first row_col) | |
;;; (replace_list_with_empty_lists row_col) | |
;;; (list (cdr (first col_row)) | |
;;; (cdr (second col_row)) | |
;;; (cdr (third col_row)) ))) | |
;;;(write-line (analyse_row (second row_col) | |
;;; (map list (first row_col)) | |
;;; (list (cddr (first col_row)) | |
;;; (cddr (second col_row)) | |
;;; (cddr (third col_row)) ))) | |
;;;(write-line (analyse_row (third row_col) | |
;;; (list (cdr (reverse (first col_row))) | |
;;; (cdr (reverse (second col_row))) | |
;;; (cdr (reverse (third col_row))) ) | |
;;; (replace_list_with_empty_lists row_col) )) | |
;;;(write-line "") | |
(for-each (lambda (row) (write-line (reduce string-append "" (map number->string row)) ) ) | |
(analyze_forest) ) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment