Skip to content

Instantly share code, notes, and snippets.

@markjenkins
Last active December 26, 2022 16:45
Show Gist options
  • Save markjenkins/89208994fdc78b102d8daae7703c5223 to your computer and use it in GitHub Desktop.
Save markjenkins/89208994fdc78b102d8daae7703c5223 to your computer and use it in GitHub Desktop.
Advent of Code 2022 https://adventofcode.com/2022/
#!/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()
#!/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()))
#!/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) )
#!/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())) )
#!/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) ) )
#!/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() ) )
#!/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) ))
#!/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) ) )
#!/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) ))
#!/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() ) )
#!/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) ) )) )
#!/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() ) )
#!/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 ) )))
#!/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()) ) ) )
#!/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()) ) )
#!/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) ))
#!/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) ))
#!/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))
#!/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))
#!/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 ) ))
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 ) ))
#!/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