Advent of Code 2022 https://adventofcode.com/2022/

aoc2022_d01_const_mem.py

#!/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()

aoc2022_d01p1.py

#!/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()))

aoc2022_d01p1.scm

#!/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) )

aoc2022_d01p2.py

#!/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())) )

aoc2022_d01p2.scm

#!/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) ) )

aoc2022_d02p1.py

#!/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() ) )

aoc2022_d02p1.scm

#!/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) ))

aoc2022_d02p2.py

#!/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) ) )

aoc2022_d02p2.scm

#!/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) ))

aoc2022_d03p1.py

#!/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() ) )

aoc2022_d03p1.scm

#!/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) ) )) )

aoc2022_d03p2.py

#!/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() ) )

aoc2022_d03p2.scm

#!/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 ) )))

aoc2022_d04p1.py

#!/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()) ) ) )

aoc2022_d04p2.py

#!/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()) ) )

aoc2022_d05p1.scm

#!/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) )

(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 (convert_move_param_and_subtract (second split_move_line) 0)
	  (cons (convert_move_param_and_subtract (fourth split_move_line) 1)
		(convert_move_param_and_subtract (sixth split_move_line) 1) ))))

(define move_t_magnitude car)
(define move_t_start cadr)
(define move_t_end cddr)

(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 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))

(write-line (construct_initial_stacks
	     parsed_initial_state_lines_backwards num_col))