🌟 Advent of Code (AoC) 2024 🌟

use std::fs;

pub const INPUT_FILE: &str = "input.txt";

pub fn read_words(path: &str) -> Vec<Vec<char>> {
    fs::read_to_string(path)
        .expect(&format!("File {} should be present", path))
        .lines()
        .map(|s| s.chars().collect())
        .collect()
}

pub fn count_xmas(words: &[Vec<char>]) -> i32 {
    let character_offsets = &[
        vec![(0, 0), (1, 0), (2, 0), (3, 0)], // Vertically
        vec![(3, 0), (2, 0), (1, 0), (0, 0)], // Rev vertically
        vec![(0, 0), (0, 1), (0, 2), (0, 3)], // Horizontally
        vec![(0, 3), (0, 2), (0, 1), (0, 0)], // Rev horizontally
        vec![(0, 0), (1, 1), (2, 2), (3, 3)], // One diagonal
        vec![(3, 3), (2, 2), (1, 1), (0, 0)], // Rev One diagonal
        vec![(0, 3), (1, 2), (2, 1), (3, 0)], // Other diagonal
        vec![(3, 0), (2, 1), (1, 2), (0, 3)], // Rev Other diagonal
    ];
    let search_term = &['X', 'M', 'A', 'S'];
    count_word(words, search_term, character_offsets)
}

pub fn count_x_mas(words: &[Vec<char>]) -> i32 {
    let character_offsets = &[
        vec![(0, 0), (2, 0), (1, 1), (0, 2), (2, 2)], // MAS-MAS
        vec![(2, 2), (2, 0), (1, 1), (0, 2), (0, 0)], // SAM-MAS
        vec![(0, 0), (0, 2), (1, 1), (2, 0), (2, 2)], // MAS-SAM
        vec![(2, 2), (0, 2), (1, 1), (2, 0), (0, 0)], // SAM-SAM
    ];
    let search_term = &['M', 'M', 'A', 'S', 'S'];
    count_word(words, search_term, character_offsets)
}

fn count_word(
    words: &[Vec<char>],
    search_term: &[char],
    character_offsets: &[Vec<(usize, usize)>],
) -> i32 {
    let mut num_xmas = 0;
    for y in 0..words.len() {
        for x in 0..words[0].len() {
            for offsets in character_offsets {
                if is_match(words, search_term, x, y, offsets) {
                    num_xmas += 1;
                }
            }
        }
    }
    num_xmas
}

fn is_match(
    words: &[Vec<char>],
    search_term: &[char],
    x: usize,
    y: usize,
    offsets: &[(usize, usize)],
) -> bool {
    offsets.iter().zip(search_term).all(|(&(dx, dy), &ch)| {
        let xi = x + dx;
        let yi = y + dy;
        yi < words.len() && xi < words[yi].len() && words[yi][xi] == ch
    })
}

fn main() {
    let words = read_words(&INPUT_FILE);
    println!("part 1: {}", count_xmas(&words));
    println!("part 2: {}", count_x_mas(&words));
}

package main

import (
	"bufio"
	"fmt"
	"log"
	"os"
)

func readValuesFromFile(filename string) ([][]rune, error) {
	file, err := os.Open(filename)

	if err != nil {
		return nil, fmt.Errorf("failed to open file: %w", err)
	}

	defer file.Close()

	scanner := bufio.NewScanner(file)

	values := [][]rune{}

	for scanner.Scan() {
		row := []rune(scanner.Text())
		values = append(values, row)
	}

	if err := scanner.Err(); err != nil {
		return nil, fmt.Errorf("error reading file: %w", err)
	}

	return values, nil
}

type Direction struct {
	X int
	Y int
}

func getAvailableDirections(x int, y int, length int, wordSearch [][]rune) []Direction {
	directions := []Direction{{X: 0, Y: 1}, {X: 1, Y: 0}, {X: 1, Y: 1}, {X: 0, Y: -1}, {X: -1, Y: 0}, {X: -1, Y: -1}, {X: 1, Y: -1}, {X: -1, Y: 1}}

	available := []Direction{}

	for _, direction := range directions {
		newX := x + length*direction.X
		newY := y + length*direction.Y

		if newX >= 0 && newX < len(wordSearch[0]) && newY >= 0 && newY < len(wordSearch) {
			available = append(available, direction)
		}
	}
	return available
}

func wordCount(wordSearch [][]rune, word []rune) (int, error) {
	count := 0

	for y, row := range wordSearch {
		for x, col := range row {

			if col == word[0] {
				availableDirections := getAvailableDirections(x, y, len(word)-1, wordSearch)

			directionLoop:
				for _, direction := range availableDirections {
					for i, char := range word[1:] {
						newX := x + (i+1)*direction.X
						newY := y + (i+1)*direction.Y

						if wordSearch[newY][newX] != char {
							continue directionLoop
						}
					}
					count++
				}
			}
		}
	}

	return count, nil
}

func getCharacters(wordSearch [][]rune, x int, y int, direction Direction, length int) []rune {
	result := []rune{}

	for i := range length {
		newX := x + (i+1)*direction.X
		newY := y + (i+1)*direction.Y

		result = append(result, wordSearch[newY][newX])
	}

	return result
}

func xwordCount(wordSearch [][]rune, word []rune) (int, error) {
	if len(word)%2 == 0 {
		return 0, fmt.Errorf("xword length must be odd: %s", string(word))
	}

	diagionals := [][]Direction{{{X: 1, Y: 1}, {X: -1, Y: -1}}, {{X: 1, Y: -1}, {X: -1, Y: 1}}}

	lengthFromMiddle := (len(word) - 1) / 2

	reverseWord := reverseRunes(word)

	count := 0

	for y, row := range wordSearch {
		if y < lengthFromMiddle || y > len(wordSearch)-1-lengthFromMiddle {
			continue
		}

	outer:
		for x, col := range row {
			if x < lengthFromMiddle || x > len(wordSearch[0])-1-lengthFromMiddle {
				continue
			}

			if col == word[lengthFromMiddle] {
				for _, directions := range diagionals {

					diag1 := getCharacters(wordSearch, x, y, directions[0], lengthFromMiddle)
					diag2 := getCharacters(wordSearch, x, y, directions[1], lengthFromMiddle)

					if !(compareRuneSlices(diag1, word[:lengthFromMiddle]) && compareRuneSlices(diag2, word[lengthFromMiddle+1:])) &&
						!(compareRuneSlices(diag1, reverseWord[:lengthFromMiddle]) && compareRuneSlices(diag2, reverseWord[lengthFromMiddle+1:])) {
						continue outer
					}
				}
				count++
			}
		}
	}

	return count, nil
}

func compareRuneSlices(slice1, slice2 []rune) bool {
	if len(slice1) != len(slice2) {
		return false
	}

	for i := range slice1 {
		if slice1[i] != slice2[i] {
			return false
		}
	}

	return true
}

func reverseRunes(runes []rune) []rune {
	runesCopy := make([]rune, len(runes))
	copy(runesCopy, runes)

	n := len(runesCopy)
	for i := 0; i < n/2; i++ {
		runesCopy[i], runesCopy[n-1-i] = runesCopy[n-1-i], runesCopy[i]
	}
	return runesCopy
}

func main() {
	value, err := readValuesFromFile("input.txt")
	if err != nil {
		log.Fatalf("Error reading data: %s", err)
	}

	total, err := wordCount(value, []rune("XMAS"))
	if err != nil {
		log.Fatalf("Error calculating part 1: %s", err)
	}
	fmt.Printf("Part 1: %d\n", total)

	total2, err := xwordCount(value, []rune("MAS"))
	if err != nil {
		log.Fatalf("Error calculating part 2: %s", err)
	}
	fmt.Printf("Part 2: %d\n", total2)

}

<?php
// Data from Source: https://adventofcode.com/2024/day/5/input
$data1 = "65|79
ETC|ETC";
$data2 = "47,89,77,74,61,53,82,38,45,73,15,76,41,24,56,55,67,68,95
ETC,ETC,ETC,ETC,ETC,ETC,ETC,ETC,ETC,ETC,ETC,ETC,ETC,ETC,ETC,ETC";

// Get data in managable way
$data1 = array_map('rtrim', explode("\n", $data1));
$data2 = str_replace(",", "|", $data2);
$data2 = array_map('rtrim', explode("\n", $data2));
$data1 = array_map(function ($x) {
    return explode("|", $x);
}, $data1);

function ExtractMiddleArrayValue($array)
{
    return $array[ceil(count($array) / 2) - 1];
}

function TwoArrayElementsAreInStringAndInValidOrder($string, $array)
{
    $first = $array[0];
    $second = $array[1];

    if (strpos($string, $first) !== false && strpos($string, $second) !== false) {
        if (strpos($string, $first) < strpos($string, $second)) {
            return true;
        } else {
            return false;
        }
    }

    return null;
}

function getValidStrings($testdata1, $testdata2)
{

    foreach ($testdata2 as $string) {
        $valid = true;

        foreach ($testdata1 as $rule) {
            $result = TwoArrayElementsAreInStringAndInValidOrder($string, $rule);
            if ($result === false) {
                $valid = false;
                break;
            }
        }

        if ($valid) {
            $validStrings[] = $string;
        }
    }

    return $validStrings;
}

// Get only valid strings and sum up their middle array element value
$validStrings = getValidStrings($data1, $data2);
$sumOfMiddleNumbers = 0;
foreach ($validStrings as $string) {
    $sumOfMiddleNumbers += ExtractMiddleArrayValue(explode("|", $string));
}

echo "Day 5 Part 1 Answer: " . $sumOfMiddleNumbers;

?>

// FRÅGA: Jag undrar om jag skulle kunna fixa permutationsfunktionen 
// för faktorialfunktionen är ju till för att berätta hur många olika 
// permutationer en given array har. Och så ska den loopa igenom
// så många gånger för att prova alla kombinationer.

function findFactorialNumberForArray($n)
{
    if (!is_array($n)) {
        throw new Exception("Input must be an array");
    } else {
        $n = count($n);
    }
    $factorial = 1;
    for ($i = 1; $i <= $n; $i++) {
        $factorial *= $i;
    }
    return $factorial;
}

// Function that generates permutations of an array to brute force all possible combinations
function generatePermutations($array)
{
    if (count($array) === 1) {
        return [$array];
    }

    $permutations = [];
    foreach ($array as $key => $value) {
        // Remove the current element
        $remaining = $array;
        unset($remaining[$key]);

        // Recursively generate permutations for the rest
        $remainingPermutations = generatePermutations($remaining);

        foreach ($remainingPermutations as $permutation) {
            // Prepend the current element to each permutation
            $permutations[] = array_merge([$value], $permutation);
        }
    }
    return $permutations;
}

function getInvalidStrings($testdata1, $testdata2)
{
    $invalidStrings = [];
    foreach ($testdata2 as $string) {
        foreach ($testdata1 as $rule) {
            $result = TwoArrayElementsAreInStringAndInValidOrder($string, $rule);
            if ($result === false) {
                $invalidStrings[] = $string;
                break;
            }
        }
    }

    return $invalidStrings;
}

// RUN DAY 5 PART 2
$invalidStrings = getInvalidStrings($testdata1, $testdata2); // Get all invalid strings instead
//var_dump($invalidStrings);

// We loop through and generate permutations (combinations) of each invalid string
// and for each permutations we check against valid rules and if they are valid
foreach ($invalidStrings as $string) {
    $string = explode("|", $string);
    $permutations = generatePermutationsIteratively($string);

    foreach ($permutations as $permutation) {
        $valid = true;
        foreach ($testdata1 as $rule) {
            $result = TwoArrayElementsAreInStringAndInValidOrder(implode("|", $permutation), $rule);
            if ($result === false) {
                $valid = false;
                break;
            }
        }

        if ($valid) {
            $sumOfMiddleNumbers += ExtractMiddleArrayValue($permutation);
            $foundValid = true;
            break;
        }
    }
}

echo "\nDay 5 Part 2 Answers: " . $sumOfMiddleNumbers;
// KRUXET är ju att även om jag hittar en giltig regel så kan ju någon annan regel
// ändå vara ogiltig vilket skulle innebära att strängen skulle ogiltighetsförklaras. HM!

from collections import defaultdict  
from functools import cmp_to_key

(order, pages), precede, s = open("input05.txt", "r").read().split("\n\n"), defaultdict(set), [0,0]

[precede[o.split("|")[0]].add(o.split("|")[1]) for o in order.split("\n")]
    
for p in pages.strip().split("\n"):
    l1 = p.split(",")
    l2 = sorted(l1, key=cmp_to_key(lambda x, y: 1 if x in precede[y] else -1))
    s[l1 != l2] += int(l2[len(l2) // 2])
print(*s)

// Function that generates permutations of an array to brute force all possible combinations
function generatePermutations($array)
{
    $result = [];
    $recurse = function ($array, $start_i = 0) use (&$result, &$recurse) {
        if ($start_i === count($array) - 1) {
            array_push($result, $array);
        }

        for ($i = $start_i; $i < count($array); $i++) {
            //Swap array value at $i and $start_i
            $t = $array[$i];
            $array[$i] = $array[$start_i];
            $array[$start_i] = $t;

            //Recurse
            $recurse($array, $start_i + 1);

            //Restore old order
            $t = $array[$i];
            $array[$i] = $array[$start_i];
            $array[$start_i] = $t;
        }
    };
    $recurse($array);

    return $result;
}

function solvePart2($invalidStrings, $testdata1)
{
    $chunkSum = 0;
    foreach ($invalidStrings as $string) {
        $string = explode("|", $string);
        $permutations = generatePermutations($string);

        foreach ($permutations as $permutation) {
            $valid = true;
            foreach ($testdata1 as $rule) {
                $result = TwoArrayElementsAreInStringAndInValidOrder(implode("|", $permutation), $rule);
                if ($result === false) {
                    $valid = false;
                    break;
                }
            }

            if ($valid) {
                $chunkSum += ExtractMiddleArrayValue($permutation);
                $foundValid = true;
                break;
            }
        }
    }

    return $chunkSum;
}

$chunks = array_chunk($invalidStrings, 1);
foreach ($chunks as $chunk) {
    $sumOfMiddleNumbers += solvePart2($chunk, $testdata1);
    unset($chunk);
    gc_collect_cycles();
}

public class Solver
{
    private static bool IsValidLine(Dictionary<string, List<string>> rulesInput, string line)
    {
        var pageNumbers = line.Split(',').ToList();
        for (var i = 0; i < pageNumbers.Count; i++)
        {
            var pageNumber = pageNumbers[i];
            if (!rulesInput.TryGetValue(pageNumber, out var ruleValues)) continue;
            if (ruleValues.Any(mustBeLessThan => pageNumbers.Where((t, j) => t == mustBeLessThan && j <= i).Any()))
            {
                return false;
            }
        }
        return true;
    }

    private static string MakeLineValid(Dictionary<string, List<string>> rulesInput, string line)
    {
        var newLine = line;
        do
        {
            var pageNumbers = newLine.Split(',').ToList();
            
            for (var i = 0; i < pageNumbers.Count; i++)
            {
                var pageNumber = pageNumbers[i];
                if (!rulesInput.TryGetValue(pageNumber, out var ruleValues)) continue;
                foreach (var mustBeLessThan in ruleValues)
                {
                    for (var j = 0; j < pageNumbers.Count; j++)
                    {
                        if (pageNumbers[j] != mustBeLessThan) continue;
                        if (j > i) continue;
                        var temp = pageNumbers[i].ToString();
                        pageNumbers[i] = pageNumbers[j];
                        pageNumbers[j] = temp;
                    }
                }
            }

            newLine = string.Join(",", pageNumbers);
        } while (!IsValidLine(rulesInput, newLine));
        
        return newLine;
    }

    private static Dictionary<string, List<string>>  ParseInputRules(List<string> inputRules)
    {
        inputRules = inputRules.OrderBy(i => i.Split('|')[0]).ThenBy(i => i.Split('|')[1]).ToList();

        var rulesDict = new Dictionary<string, List<string>>();
        foreach (var rule in inputRules)
        {
            var key = rule.Split('|')[0];
            var value = rule.Split('|')[1];
            if(rulesDict.ContainsKey(key)) rulesDict[key].Add(value);
            else rulesDict.Add(key, [value]);
        }

        return rulesDict;
    }
    public static int Run_PartOne(string input)
    {
        var split = input.Split("\r\n\r\n");
        var rules = split[0].Split("\r\n").ToList();
        var updates = split[1].Split("\r\n").ToList();
        
        var rulesDict = ParseInputRules(rules);

        return updates
            .Where(line => IsValidLine(rulesDict, line))
            .Select(line => line.Split(',').ToList())
            .Select(numbers => int.Parse(numbers[(numbers.Count - 1) / 2]))
            .Sum();
    }
    public static int Run_PartTwo(string input)
    {
        var split = input.Split("\r\n\r\n");
        var rules = split[0].Split("\r\n").ToList();
        var updates = split[1].Split("\r\n").ToList();
        
        var rulesDict = ParseInputRules(rules);

        return updates
            .Where(line => !IsValidLine(rulesDict, line))
            .Select(line => MakeLineValid(rulesDict, line).Split(',').ToList())
            .Select(numbers => int.Parse(numbers[(numbers.Count - 1) / 2]))
            .Sum();
    }
}

public class Puzzle_2024_5 : Puzzle
{
    public override object PartOne(string data)
    {
        var (rules, updates) = LoadData(data);
        RuleComparer comparer = new RuleComparer(rules);
        return updates.Aggregate(0, (acc, update) =>
        {
            var sorted = update.OrderBy(x => x, comparer);
            if (update.SequenceEqual(sorted))
                acc += update[update.Count / 2];
            return acc;
        });
    }

    public override object PartTwo(string data)
    {
        var (rules, updates) = LoadData(data);
        RuleComparer comparer = new RuleComparer(rules);
        return updates.Aggregate(0, (acc, update) =>
        {
            var sorted = update.OrderBy(x => x, comparer).ToList();
            if (!update.SequenceEqual(sorted))
            {
                acc += sorted[sorted.Count / 2];
            }

            return acc;
        });
    }

    private static (HashSet<(int, int)> rules, List<List<int>> updates) LoadData(string data)
    {
        var sections = data.Split("\r\n\r\n");
        var rulesList = sections[0].Split("\r\n").Select(line => line.Split('|').Select(int.Parse).ToList()).ToList();
        HashSet<(int, int)> rules = [];
        foreach (var rule in rulesList)
        {
            rules.Add((rule[0], rule[1]));
        }

        var updates = sections[1].Split("\r\n").Select(line => line.Split(',').Select(int.Parse).ToList()).ToList();
        return (rules, updates);
    }

    private class RuleComparer(HashSet<(int i, int j)> rules) : IComparer<int>
    {
        public int Compare(int x, int y)
        {
            if (rules.Contains((x, y)))
                return -1;

            return rules.Contains((y, x)) ? 1 : 0;
        }
    }
}

open System

let pairs, updates =
        let data = System.IO.File.ReadAllText("input.txt") |> _.Split("\n\n", System.StringSplitOptions.RemoveEmptyEntries)
        let pairs = data.[0] |> _.Split("\n") |> Seq.map (fun x -> x.Split("|") |> (fun x-> (int x.[0], int x.[1]))) |> Set.ofSeq
        let updates = data.[1] |> _.Split("\n") |> Seq.map (fun x -> x.Split(",", StringSplitOptions.TrimEntries) |> Seq.map int |> Seq.toList) |> Seq.toList
        (pairs, updates)
        
        
let isSorted = List.pairwise >> List.exists (fun (x,y) -> Set.contains (y,x) pairs) >> not
    
let part' filter mapper = 
    updates |> List.filter filter  |> List.map mapper |> Seq.map (fun x->
            let length = x |> Seq.length
            let middle = length / 2
            x |> Seq.skip middle |> Seq.head
            )
            |> Seq.sum

let comparer x y =
        if Set.contains (x,y) pairs then -1
        elif Set.contains (y,x) pairs then 1
        else 0
        
let part1 = part' isSorted id 
let part2 = part' (isSorted >> not) (List.sortWith comparer) 
    
printfn "part 1: %A" part1
printfn "part 2: %A" part2

use std::fs;

pub const INPUT_FILE: &str = "input.txt";

pub fn read_page_rules(path: &str) -> (Vec<u128>, Vec<Vec<u32>>) {
    let file_content = fs::read_to_string(path).expect(&format!("File {} should be present", path));
    let mut groups = file_content.split("\n\n");
    (
        groups
            .next()
            .expect("Missing first group")
            .lines()
            .fold(Vec::new(), |mut filter, line| {
                let mut parts = line.split('|');
                let a: usize = parts.next().unwrap().parse().unwrap();
                let b: usize = parts.next().unwrap().parse().unwrap();
                if a >= filter.len() {
                    filter.resize(a + 1, 0);
                }
                filter[a] |= 1 << b;
                filter
            }),
        groups
            .next()
            .expect("Missing second group")
            .lines()
            .map(|line| line.split(',').map(|num| num.parse().unwrap()).collect())
            .collect(),
    )
}

pub fn correct_order_middle_page_sum(rules: &[u128], page_updates: &[Vec<u32>]) -> u32 {
    page_updates
        .iter()
        .filter(|updates| is_pages_in_correct_order(rules, updates))
        .map(|pages| pages[pages.len() / 2])
        .sum()
}

pub fn corrected_order_middle_page_sum(rules: &[u128], page_updates: &[Vec<u32>]) -> u32 {
    page_updates
        .iter()
        .filter(|updates| !is_pages_in_correct_order(rules, updates))
        .map(|incorrect_order| correct_order(rules, incorrect_order))
        .map(|pages| pages[pages.len() / 2])
        .sum()
}

fn is_pages_in_correct_order(rules: &[u128], page_updates: &[u32]) -> bool {
    let mut mask = 1 << page_updates[0];
    for i in 1..page_updates.len() {
        let page = page_updates[i] as usize;
        if (mask & rules[page]) != 0 {
            return false;
        }
        mask |= 1 << page;
    }
    true
}

fn correct_order(rules: &[u128], incorrect_order: &[u32]) -> Vec<u32> {
    let mut pages = incorrect_order.to_vec();
    let mut mask: u128 = pages.iter().map(|&page| 1 << page).sum();
    for i in (1..pages.len()).rev() {
        for (j, &page) in pages[0..=i].iter().enumerate() {
            if (mask & rules[page as usize]) == 0 {
                pages.swap(i, j);
                mask ^= 1 << page;
                break;
            }
        }
    }
    pages
}

fn main() {
    let (rules, page_updates) = read_page_rules(&INPUT_FILE);
    println!(
        "part 1: {}",
        correct_order_middle_page_sum(&rules, &page_updates)
    );
    println!(
        "part 2: {}",
        corrected_order_middle_page_sum(&rules, &page_updates)
    );
}

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

int main(int argc, char *argv[])
{
    FILE *fp;
    char *a = NULL;
    long flen;

    fp = fopen("input.txt", "r");
    (void)fseek(fp, 0L, SEEK_END);
    flen = ftell(fp);
    rewind(fp);

    a = malloc((size_t)flen);
    fread(a, 1, (size_t)flen, fp);
    fclose(fp);

    // part 1 and 2
    int enabled = 1, j = 0, k = 0, d1 = 0, d2 = 0, part1 = 0, part2 = 0;
    for (int i = 0; i < (flen-8); i++) { // mul(1,1) minimum 8 chars
        j = k = d1 = d2 = 0;
        if (a[i] == 'd' && a[i+1] == 'o' && a[i+2] == '(' && a[i+3] == ')') {
            enabled = 1;
            i += 3;
            continue;
        } else if (a[i] == 'd' && a[i+1] == 'o' && a[i+2] == 'n' && a[i+3] == '\'' && a[i+4] == 't' && a[i+5] == '(' && a[i+6] == ')') {
            enabled = 0;
            i += 6;
            continue;
        }
        if (a[i] == 'm' && a[i+1] == 'u' && a[i+2] == 'l' && a[i+3] == '(') {
            for(j = i+4; j < i+4+4; j++) {
                if (isdigit(a[j])) {
                    d1 = d1 * 10 + (a[j]-'0');
                    continue;
                } else if (a[j] == ',') {
                    for (k = j+1; k < (k+1+3) && k < flen; k++) {
                        if (isdigit(a[k])) {
                            d2 = d2 * 10 + (a[k]-'0');
                            continue;
                        } else if (a[k] == ')') {
                            part1 += d1 * d2;
                            if (enabled) {
                                part2 += d1 * d2;
                            }
                        }
                        i = k-1;
                        break;
                    }
                    if (i == k-1) {
                        break;
                    }
                } else {
                    i = j-1;
                    break;
                }
            }
        }
    }
    free(a);

    printf("part 1: %d\n", part1);
    printf("part 2: %d\n", part2);

    return 0;
}

package main

import (
	"bufio"
	"fmt"
	"log"
	"os"
	"sort"
	"strconv"
	"strings"
)

func readRulesFromFile(filename string) ([]Rule, error) {
	file, err := os.Open(filename)

	if err != nil {
		return nil, fmt.Errorf("failed to open file: %w", err)
	}

	defer file.Close()

	scanner := bufio.NewScanner(file)

	values := []Rule{}

	for scanner.Scan() {
		columns := strings.Split(scanner.Text(), "|")

		before, err := strconv.Atoi(columns[0])
		if err != nil {
			return nil, fmt.Errorf("rule data not an integer: %s", columns[0])
		}
		after, err := strconv.Atoi(columns[1])
		if err != nil {
			return nil, fmt.Errorf("rule data not an integer: %s", columns[1])
		}

		values = append(values, Rule{Before: before, After: after})
	}

	if err := scanner.Err(); err != nil {
		return nil, fmt.Errorf("error reading file: %w", err)
	}

	return values, nil
}

func readValuesFromFile(filename string) ([][]int, error) {
	file, err := os.Open(filename)

	if err != nil {
		return nil, fmt.Errorf("failed to open file: %w", err)
	}

	defer file.Close()

	scanner := bufio.NewScanner(file)

	values := [][]int{}

	for scanner.Scan() {
		columns := strings.Split(scanner.Text(), ",")

		update := []int{}

		for _, val := range columns {

			value, err := strconv.Atoi(val)
			if err != nil {
				return nil, fmt.Errorf("input data not an integer: %s", val)
			}

			update = append(update, value)

		}

		values = append(values, update)
	}

	if err := scanner.Err(); err != nil {
		return nil, fmt.Errorf("error reading file: %w", err)
	}

	return values, nil
}

type Rule struct {
	Before int
	After  int
}

type CustomSorter struct {
	data        []int
	compareFunc func(a, b int) bool
}

func (cs CustomSorter) Len() int {
	return len(cs.data)
}

func (cs CustomSorter) Less(i, j int) bool {
	return cs.compareFunc(cs.data[i], cs.data[j])
}

func (cs CustomSorter) Swap(i, j int) {
	cs.data[i], cs.data[j] = cs.data[j], cs.data[i]
}

func isValidUpdate(update []int, compareFunc func(a, b int) bool) bool {
	sorter := CustomSorter{
		data:        update,
		compareFunc: compareFunc,
	}
	return sort.IsSorted(sorter)

	/*
		did this first, but there's really no point after having the sorter...

		for i := range len(update) {
			validPreviousPages := pageToValidPreviousPages[update[i]]

			for _, previousPage := range update[:i] {
				if !contains(validPreviousPages, previousPage) {
					return false
				}
			}
		}

		return true
	*/
}

func isInvalidUpdate(update []int, compareFunc func(a, b int) bool) bool {
	return !isValidUpdate(update, compareFunc)
}

func getCompareFunc(rules []Rule) func(a, b int) bool {
	pageToValidPreviousPages := getRulesMap(rules)

	compareFunc := func(a, b int) bool {
		validPrevious := pageToValidPreviousPages[b]
		return contains(validPrevious, a)
	}

	return compareFunc
}

func filterUpdates(updates [][]int, rules []Rule, filterFunc func([]int, func(int, int) bool) bool) [][]int {
	valid := [][]int{}

	compareFunc := getCompareFunc(rules)

	for _, update := range updates {

		if filterFunc(update, compareFunc) {
			valid = append(valid, update)
		}
	}

	return valid
}

func fixUpdate(update []int, compareFunc func(a, b int) bool) []int {
	fixUpdate := make([]int, len(update))
	copy(fixUpdate, update)

	sorter := CustomSorter{
		data:        fixUpdate,
		compareFunc: compareFunc,
	}
	sort.Sort(sorter)

	return fixUpdate
}

func fixUpdates(updates [][]int, rules []Rule) [][]int {
	fixed := [][]int{}
	compareFunc := getCompareFunc(rules)

	for _, update := range updates {
		fixed = append(fixed, fixUpdate(update, compareFunc))
	}

	return fixed
}

func contains(slice []int, element int) bool {
	for _, v := range slice {
		if v == element {
			return true
		}
	}
	return false
}

func getRulesMap(rules []Rule) map[int][]int {
	mustBeBefore := map[int][]int{}

	for _, rule := range rules {
		current := mustBeBefore[rule.After]
		if current == nil {
			current = []int{}
		}

		current = append(current, rule.Before)
		mustBeBefore[rule.After] = current
	}

	return mustBeBefore
}

func getMiddlePage(updates [][]int) []int {
	middlePages := []int{}

	for _, update := range updates {
		middle := (len(update) - 1) / 2
		middlePages = append(middlePages, update[middle])
	}

	return middlePages
}

func sum(values []int) int {
	sum := 0

	for _, val := range values {
		sum += val
	}

	return sum
}

func main() {
	rules, err := readRulesFromFile("rules.txt")
	if err != nil {
		log.Fatalf("Error reading data: %s", err)
	}

	updates, err := readValuesFromFile("input.txt")
	if err != nil {
		log.Fatalf("Error reading data: %s", err)
	}

	validUpdates := filterUpdates(updates, rules, isValidUpdate)
	middlePages := getMiddlePage(validUpdates)
	total := sum(middlePages)
	fmt.Printf("Part 1: %d\n", total)

	invalidUpdates := filterUpdates(updates, rules, isInvalidUpdate)
	fixedUpdates := fixUpdates(invalidUpdates, rules)
	fixedMiddlePages := getMiddlePage(fixedUpdates)
	fixedTotal := sum(fixedMiddlePages)

	fmt.Printf("Part 2: %d\n", fixedTotal)
}

namespace Day_6;

public class Solver
{
    private enum Direction { Up, Right, Down, Left };
    private record struct Point(int X, int Y) { }
    private record struct VisitedPointWithDirections(Point Point, Direction IncomingDirection, Direction OutgoingDirection);
    
    private static Point Move(Point p, Direction dir) => dir switch
    {
        Direction.Up => p with { Y = p.Y - 1 },
        Direction.Down => p with { Y = p.Y + 1 },
        Direction.Left => p with { X = p.X - 1 },
        Direction.Right => p with { X = p.X + 1 },
        _ => p
    };
    
    private static bool IsPosInBounds(Point pos, int maxWidth, int maxHeight) 
        => pos.X >= 0 && pos.Y >= 0 && pos.X < maxWidth && pos.Y < maxHeight;

    private static Direction RotateDirection(Direction dir) => dir switch
    {
        Direction.Up => Direction.Right,
        Direction.Down => Direction.Left,
        Direction.Left => Direction.Up,
        Direction.Right => Direction.Down,
        _ => Direction.Up
    };
    
    private static Dictionary<Point, int> GetGuardVisitedPositions(string[,] grid, Point startPos)
    {
        var visitedPositions = new Dictionary<Point, int>();
        var currentDir = Direction.Up;
        var currentPos = startPos;
        while (true)
        {
            var newPos = Move(currentPos, currentDir);
            if (!IsPosInBounds(newPos, grid.GetLength(0), grid.GetLength(1)))
            {
                visitedPositions[currentPos] = 1;
                break;
            }
            
            if (grid[newPos.Y, newPos.X] == "#")
            {
                currentDir = RotateDirection(currentDir);
            }
            else
            {
                visitedPositions[currentPos] = 1;
                currentPos = newPos;
            }
        }

        return visitedPositions;
    }
    
    private static int GetNumberOfLoopedRoutes(string[,] grid, Dictionary<Point, int> visitedPositions, Point startPos)
    {
        int numberOfLoopedRoutes = 0;
        
        for(int i = 0; i < visitedPositions.Count; i++)
        { 
            var currentDir = Direction.Up;
            var currentPos = startPos;
            var currentIterPos = visitedPositions.ElementAt(i);
            if (currentIterPos.Key == startPos) continue;
            
            grid[currentIterPos.Key.Y, currentIterPos.Key.X] = "O";
            
            var pointsWithDirections = new Dictionary<VisitedPointWithDirections, int>();
            while (true)
            {
                var newPos = Move(currentPos, currentDir);
                if (!IsPosInBounds(newPos, grid.GetLength(0), grid.GetLength(1)))
                    break;
            
                if (grid[newPos.Y, newPos.X] == "#" || grid[newPos.Y, newPos.X] == "O")
                {
                    var newDir = RotateDirection(currentDir);
                    var pointWithDirection = new VisitedPointWithDirections(currentPos, currentDir, newDir);
                    if (!pointsWithDirections.TryAdd(pointWithDirection, 1))
                    {
                        numberOfLoopedRoutes++;
                        break;
                    }

                    currentDir = RotateDirection(currentDir);
                }
                else
                {
                    currentPos = newPos;
                }
            }

            grid[currentIterPos.Key.Y, currentIterPos.Key.X] = ".";
        }
       
        return numberOfLoopedRoutes;
    }
    
    private static string[,] GetGrid(string input)
    {
        string[] lines = input.Split(Environment.NewLine, StringSplitOptions.RemoveEmptyEntries);
        int height = lines.Length;
        int width = lines[0].Length;
        string[,] grid = new string[width, height];
        
        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                grid[y, x] = lines[y][x].ToString();
            }
        }

        return grid;
    }
    
    public static int Run_PartOne(string input)
    {
        // Something in front; Turn 90 degrees to the right
        // Move forward
        // Add each position (including starting position) to a dictionary.

        var grid = GetGrid(input);
        var startPos = new Point();
        for (int y = 0; y < grid.GetLength(0); y++)
        {
            for (int x = 0; x < grid.GetLength(1); x++)
            {
                if (grid[y, x] == "^") startPos = new Point(x, y);
            }
        }
      
        var visitedPositions = GetGuardVisitedPositions(grid, startPos);
        var distinctPositions = visitedPositions.Keys.Count;
        return distinctPositions;
    }
    
    public static int Run_PartTwo(string input)
    {
        // Start by running PartOne to get all the positions visited.
        // Place a new obstacle in any of the visited positions (except the startPos) and run the loop detection:
        //
        // Record the direction, position and new direction every time you need to change direction.
        // If the data already exists, you know you've been here before and is thus in a loop.
        // Repeat until every visited position has been tried at least once (except startPos)
        
        var grid = GetGrid(input);
        var startPos = new Point();
        for (int y = 0; y < grid.GetLength(0); y++)
        {
            for (int x = 0; x < grid.GetLength(1); x++)
            {
                if (grid[y, x] == "^") startPos = new Point(x, y);
            }
        }
      
        var visitedPositions = GetGuardVisitedPositions(grid, startPos);
        var loopedRoutes = GetNumberOfLoopedRoutes(grid, visitedPositions, startPos);
        return loopedRoutes;
    }
}

<?php include '_helpers.php';

$data = "https://adventofcode.com/2024/day/6/input";
$steps = 1;
$distinctPositions = [];
$map = generateXYCoordinates($data, "\n");
$startCoordinate = array_search("^", $map);
$distinctPositions[] = $startCoordinate;

$start = moveInOneDirectionInCoordinateUntilStopChar("TOP", $startCoordinate, $map, "#", $steps, $distinctPositions);

while (is_array($start)) {
    $start = moveInOneDirectionInCoordinateUntilStopChar(turnRight90Degrees($start[1]), $start[0], $map, "#", $steps, $distinctPositions);
    if ($start == "FOUND") {
        break;
    }
}

echo "Steps: " . $steps;

function generateXYCoordinates($data, $splitOn = "")
{
    $coordinateSystem = [];
    if ($splitOn != "") {
        $data = explode("\n", $data);
    }

    if ($splitOn == "\n") {
        $data = array_map('rtrim', $data);
    }

    if (!is_array($data)) {
        throw new Exception("Data is not an array, please provide an array or a split on value.");
    }

    foreach ($data as $y => $row) {
        for ($x = 0; $x < strlen($row); $x++) {
            $coord = ($x + 1) . "," . ($y + 1);
            $coordinateSystem[$coord] = $row[$x];
        }
    }
    return $coordinateSystem;
}

function getCharAt($coordinate, $coordinateSystem, $relativePosition = "", $relativeOffset = 0)
{
    if ($relativePosition == "") {
        return isset($coordinateSystem[$coordinate]) ? $coordinateSystem[$coordinate] : "?";
    }

    [$x, $y] = array_map('intval', explode(",", $coordinate));
    switch ($relativePosition) {
        case "TOP":
            return isset($coordinateSystem[$x . "," . ($y - 1 - $relativeOffset)]) ? $coordinateSystem[$x . "," . ($y - 1 - $relativeOffset)] : "?";
        case "BOTTOM":
            return isset($coordinateSystem[$x . "," . ($y + 1 + $relativeOffset)]) ? $coordinateSystem[$x . "," . ($y + 1 + $relativeOffset)] : "?";
        case "LEFT":
            return isset($coordinateSystem[($x - 1 - $relativeOffset) . "," . $y]) ? $coordinateSystem[($x - 1 - $relativeOffset) . "," . $y] : "?";
        case "RIGHT":
            return isset($coordinateSystem[($x + 1 + $relativeOffset) . "," . $y]) ? $coordinateSystem[($x + 1 + $relativeOffset) . "," . $y] : "?";
        case "TOP LEFT":
            return isset($coordinateSystem[($x - 1 - $relativeOffset) . "," . ($y - 1 - $relativeOffset)]) ? $coordinateSystem[($x - 1 - $relativeOffset) . "," . ($y - 1 - $relativeOffset)] : "?";
        case "TOP RIGHT":
            return isset($coordinateSystem[($x + 1 + $relativeOffset) . "," . ($y - 1 - $relativeOffset)]) ? $coordinateSystem[($x + 1 + $relativeOffset) . "," . ($y - 1 - $relativeOffset)] : "?";
        case "BOTTOM LEFT":
            return isset($coordinateSystem[($x - 1 - $relativeOffset) . "," . ($y + 1 + $relativeOffset)]) ? $coordinateSystem[($x - 1 - $relativeOffset) . "," . ($y + 1 + $relativeOffset)] : "?";
        case "BOTTOM RIGHT":
            return isset($coordinateSystem[($x + 1 + $relativeOffset) . "," . ($y + 1 + $relativeOffset)]) ? $coordinateSystem[($x + 1 + $relativeOffset) . "," . ($y + 1 + $relativeOffset)] : "?";
        default:
            return "?";
    }
}

function turnRight90Degrees($currentDirection)
{
    switch ($currentDirection) {
        case "TOP":
            return "RIGHT";
        case "RIGHT":
            return "BOTTOM";
        case "BOTTOM":
            return "LEFT";
        case "LEFT":
            return "TOP";
        default:
            throw new Exception("Invalid direction provided, please provide a valid direction.");
    }
}

function moveInOneDirectionInCoordinateUntilStopChar($direction, $startCoordinate, $coordinateSystem, $stopAt = "", &$stepCounter = null, &$distinctPositions)
{
    $currentCoordinate = $startCoordinate;
    $currentChar = getCharAt($currentCoordinate, $coordinateSystem);

    while ($currentChar != $stopAt) {
        [$x, $y] = extractCoordinates($currentCoordinate);
        $oldCoordinate = $currentCoordinate;
        switch ($direction) {
            case "TOP":
                $currentCoordinate = $x . "," . ($y - 1);
                break;
            case "BOTTOM":
                $currentCoordinate = $x . "," . ($y + 1);
                break;
            case "LEFT":
                $currentCoordinate = ($x - 1) . "," . $y;
                break;
            case "RIGHT":
                $currentCoordinate = ($x + 1) . "," . $y;
                break;
            case "TOP LEFT":
                $currentCoordinate = ($x - 1) . "," . ($y - 1);
                break;
            case "TOP RIGHT":
                $currentCoordinate = ($x + 1) . "," . ($y - 1);
                break;
            case "BOTTOM LEFT":
                $currentCoordinate = ($x - 1) . "," . ($y + 1);
                break;
            case "BOTTOM RIGHT":
                $currentCoordinate = ($x + 1) . "," . ($y + 1);
                break;
            default:
                throw new Exception("Invalid direction provided, please provide a valid direction.");
        }

        if (getCharAt($currentCoordinate, $coordinateSystem) == $stopAt) {
            echo "Obstacle found at: ($currentCoordinate) in direction $direction\n";
            return [$oldCoordinate, $direction];
        } 
        elseif (getCharAt($currentCoordinate, $coordinateSystem) == "?") {
            echo "Found the exit at at: ($currentCoordinate) in direction $direction\n";
            return "FOUND";
        }
.
        if (!isset($distinctPositions[$currentCoordinate])) {
            $distinctPositions[$currentCoordinate] = 1;
            $stepCounter++;
        }
        $currentChar = getCharAt($currentCoordinate, $coordinateSystem);

        echo "Moved ($direction|$currentCoordinate). Found: " . $currentChar . "| Steps: $stepCounter\n";
    }
    return [$currentCoordinate, $direction];
}

using System.Diagnostics;
var lines = File.ReadAllLines("input.txt");
Dictionary<(int x, int y), char> grid = [];
for (int x = 0; x < lines.Length; x++)
    for (int y = 0; y < lines[x].Length; y++)
        grid[(x, y)] = lines[x][y];

char[] guard = ['^', '<', '>', 'v'];
var origin = grid.Where(x => guard.Contains(x.Value)).FirstOrDefault();
Stopwatch sw = Stopwatch.StartNew();
//part 1
(var cpos, var cval) = (origin.Key, origin.Value);
GuardLoops(grid, cpos, cval);
Console.WriteLine("Part 1: " + grid.Where(x => x.Value == 'X').Sum(x => 1));
Console.WriteLine("Part 1 time: " + sw.Elapsed);
sw.Restart();

// part 2
grid[origin.Key] = origin.Value;
var possibles = grid.Where(x => x.Value != '.');
int sumpart2 = 0;
Parallel.ForEach(possibles, pos =>
{
    var gridcopy = grid.ToDictionary(entry => entry.Key, entry => entry.Value);
    gridcopy[pos.Key] = '#';
    (var cpos, var cval) = (origin.Key, origin.Value);
    if (GuardLoops(gridcopy, cpos, cval))
        Interlocked.Increment(ref sumpart2);
});
sw.Stop();
Console.WriteLine("Part 2: " + sumpart2);
Console.WriteLine("Part 2 time: " + sw.Elapsed);

static bool GuardLoops(Dictionary<(int x, int y), char> grid, (int x, int y) cpos, char cval)
{
    HashSet<((int x, int y), char)> steps = [];
    while (true)
    {
        (int x, int y) npos = cval switch
        {
            '^' => ((cpos.x - 1), (cpos.y)),
            '>' => ((cpos.x), (cpos.y + 1)),
            'v' => ((cpos.x + 1), (cpos.y)),
            _ => ((cpos.x), (cpos.y - 1)), // '<'        
        };
        if (grid.TryGetValue(npos, out char nval))
        {
            if (nval == '#')
            {
                cval = cval switch
                {
                    '^' => '>',
                    '>' => 'v',
                    'v' => '<',
                    _ => '^' // '<'
                };
            }
            else
            {
                if (steps.Contains((cpos, cval)))
                    return true;
                else
                    steps.Add((cpos, cval));
                grid[cpos] = 'X';
                cpos = npos;
            }
        }
        else
        {
            grid[cpos] = 'X';
            return false;
        }
    }
}