import pathlib

base_dir = pathlib.Path(__file__).parent
filename = base_dir / "day9_input.txt"

with open(base_dir / filename) as f:
    lines = f.read().splitlines()

histories = [[int(n) for n in line.split()] for line in lines]

answer_p1 = 0
answer_p2 = 0

for history in histories:
    deltas: list[list[int]] = []
    last_line: list[int] = history

    while any(last_line):
        deltas.append(last_line)
        last_line = [last_line[i] - last_line[i - 1] for i in range(1, len(last_line))]

    first_value = 0
    last_value = 0
    for delta_list in reversed(deltas):
        last_value = delta_list[-1] + last_value
        first_value = delta_list[0] - first_value

    answer_p1 += last_value
    answer_p2 += first_value

print(f"{answer_p1=}")
print(f"{answer_p2=}")

private def parseLine (line : String) : Except String $ List Int :=
  line.split Char.isWhitespace
  |> List.map String.trim
  |> List.filter String.notEmpty
  |> List.mapM String.toInt?
  |> Option.toExcept s!"Failed to parse numbers in line \"{line}\""

def parse (input : String) : Except String $ List $ List Int :=
  let lines := input.splitOn "\n" |> List.map String.trim |> List.filter String.notEmpty
  lines.mapM parseLine

-------------------------------------------------------------------------------------------

private def differences : List Int → List Int
| [] => []
| _ :: [] => []
| a :: b :: as => (a - b) :: differences (b::as)

private theorem differences_length_independent_arg (a b : Int) (bs : List Int) : (differences (a :: bs)).length = (differences (b :: bs)).length := by
  induction bs <;> simp[differences]

-- BEWARE: Extrapolate needs the input reversed.
private def extrapolate : List Int → Int
| [] => 0
| a :: as =>
  if a == 0 && as.all (· == 0) then
    0
  else
    have : (differences (a :: as)).length < as.length + 1 := by
      simp_arith[differences]
      induction (as) <;> simp_arith[differences]
      case cons b bs hb => rw[←differences_length_independent_arg]
                           assumption
    a + extrapolate (differences (a :: as))
termination_by extrapolate a => a.length

def part1 : List (List Int) → Int :=
  List.foldl Int.add 0 ∘ List.map (extrapolate ∘ List.reverse)

-------------------------------------------------------------------------------------------

def part2 : List (List Int) → Int :=
  List.foldl Int.add 0 ∘ List.map extrapolate

import fs from "fs";

const rows = fs.readFileSync("./09/input.txt", "utf-8")
    .split(/[\r\n]+/)
    .map(row => row.trim())
    .filter(Boolean)
    .map(row => row.split(/\s+/).map(number => parseInt(number)));

console.info("Part 1: " + solve(structuredClone(rows)));
console.info("Part 2: " + solve(structuredClone(rows), true));

function solve(rows: number[][], part2 = false): number {
    let total = 0;
    for (const row of rows) {
        const sequences: number[][] = [row];
        while (sequences[sequences.length - 1].some(number => number !== 0)) { // Loop until all are zero
            const lastSequence = sequences[sequences.length - 1];
            const newSequence: number[] = [];
            for (let i = 0; i < lastSequence.length; i++) {
                if (lastSequence[i + 1] !== undefined) {
                    newSequence.push(lastSequence[i + 1] - lastSequence[i]);
                }
            }
            sequences.push(newSequence);
        }

        // For part two just reverse the sequences
        if (part2) {
            sequences.forEach(sequence => sequence.reverse());
        }

        // Add the first zero manually and loop the rest
        sequences[sequences.length - 1].push(0);
        for (let i = sequences.length - 2; i >= 0; i--) {
            sequences[i].push(part2
                ? sequences[i][sequences[i].length - 1] - sequences[i + 1][sequences[i + 1].length - 1]
                : sequences[i][sequences[i].length - 1] + sequences[i + 1][sequences[i + 1].length - 1]
            );
        }
    
        total += sequences[0].reverse()[0];
    }

    return total;
}

import re
import math
import argparse
import itertools

#https://stackoverflow.com/a/1012089
def iter_item_and_next(iterable):
    items, nexts = itertools.tee(iterable, 2)
    nexts = itertools.chain(itertools.islice(nexts, 1, None), [None])
    return zip(items, nexts)

class Sequence:
    def __init__(self,sequence:list) -> None:
        self.list = sequence
        if all([x == sequence[0] for x in sequence]):
            self.child:Sequence = ZeroSequence(len(sequence)-1)
            return
        
        child_sequence = list()
        for cur,next in iter_item_and_next(sequence):
            if next == None:
                continue
            child_sequence.append(next - cur)

        if len(child_sequence) > 1:
            self.child:Sequence = Sequence(child_sequence)
            return
        
        # can't do diff on single item, use zero list
        self.child:Sequence = ZeroSequence(1)

    def __repr__(self) -> str:
        return f"Sequence([{self.list}], Child:{self.child})"

    def getNext(self) -> int:
        if self.child == None:
            new = self.list[-1]
        else: 
            new = self.list[-1] + self.child.getNext()

        self.list.append(new)
        return new
    
    def getPrevious(self) -> int:
        if self.child == None:
            new = self.list[0]
        else: 
            new = self.list[0] - self.child.getPrevious()

        self.list.insert(0,new)
        return new

class ZeroSequence(Sequence):
    def __init__(self,count) -> None:
        self.list = [0]*count
        self.child = None

    def __repr__(self) -> str:
        return f"ZeroSequence(length={len(self.list)})"

    def getNext(self) -> int:
        self.list.append(0)
        return 0
    
    def getPrevious(self) -> int:
        self.list.append(0)
        return 0

def parse_line(string:str) -> list:
    return [int(x) for x in string.split(' ')]

def main(line_list):
    data = [Sequence(parse_line(x)) for x in line_list]
    print(data)

    # part 1
    total = 0
    for d in data:
        total += d.getNext()
    print("Part 1 After:")
    print(data)
    print(f"part 1 total: {total}")

    # part 2
    total = 0
    for d in data:
        total += d.getPrevious()
    print("Part 2 After:")
    print(data)
    print(f"part 2 total: {total}")


if __name__ == "__main__":
    parser = argparse.ArgumentParser(description="day 1 solver")
    parser.add_argument("-input",type=str)
    parser.add_argument("-part",type=int)
    args = parser.parse_args()
    filename = args.input
    if filename == None:
        parser.print_help()
        exit(1)
    file = open(filename,'r')
    main([line.rstrip('\n') for line in file.readlines()])
    file.close()