🌟 Advent of Code (AoC) 2021 🌟

main = interact solve

solve input = "Problem 1: " ++ show (findLocalMin (cost fuel1 startPos) endPos)  ++ "\n"
           ++ "Problem 2: " ++ show (findLocalMin (cost fuel2 startPos) endPos) ++ "\n"
    where
        startPos = map read (words (map (\c->if c==',' then ' ' else c) input)) :: [Int]
        endPos = [minimum startPos..maximum startPos]
        fuel1 from to = abs (to-from)
        fuel2 from to = div ((fuel1 from to)*(fuel1 from to + 1)) 2
        cost fuel starts end = foldr (\from acc->acc+fuel from end) 0 starts

findLocalMin f xs
    | length xs <= 8 = minimum (map f xs)
    | otherwise = if sign1 == sign2 then findLocalMin f (drop half xs) else findLocalMin f (take (half+2) xs)
        where
            sign1 = (f (xs !! 0) - f (xs !! 1)) >= 0
            sign2 = (f (xs !! half) - f (xs !! half+1)) >= 0
            half = div (length xs) 2

int solve_part1(vector<int> data)
{
    //median minimizes the sum of absolute deviations
    sort(data.begin(), data.end());
    int median = data[data.size()/2];

    int result = accumulate(data.begin(), data.end(),0,[median](int a, int b){return a + abs(b - median);});
    
    return result;
}

int solve_part2(vector<int> data)
{
    //f(m) = sum_i((x_i-m)² + abs(x_i-m))/2
    //df/dm = 0 -> m = sum_i(x_i)/n +-1/2
    //optimal position m is within +-1/2 of the mean (sum_i(x_i)/n)

    float mean = accumulate(data.begin(),data.end(),0)/(float)data.size();

    int f1 = accumulate(data.begin(), data.end(),0,
        [mean](int a, int b){int d = abs(b-int(mean+.5)); return a + (d*d + d)/2;});
    int f2 = accumulate(data.begin(), data.end(),0,
        [mean](int a, int b){int d = abs(b-int(mean-.5)); return a + (d*d + d)/2;});

    return f1 < f2? f1 : f2; 

}

import numpy as np
import pandas as pd

df = pd.read_csv('d5.txt', names=['x1','y1x2','y2'], dtype=object)
df = pd.concat([df[['x1','y2']], df['y1x2'].str.split('->', expand=True)],axis=1).astype(int)
df.columns = ['x1','y2','y1','x2']

def dangerPoints(df_input, includeDiag):
    N = df_input.values.max()
    df_map = pd.DataFrame(np.zeros((N+1, N+1)), dtype=int)
    
    for row in df_input.iterrows():
        x = np.array(row[1][['x1','x2']])
        y = np.array(row[1][['y1','y2']])

        if (x[0] == x[1]) & (y[0] != y[1]):
            df_map.iloc[y.min():y.max()+1, x[0]] += 1
        elif (x[0] != x[1]) & (y[0] == y[1]):
            df_map.iloc[y[0], x.min():x.max()+1] += 1
        elif includeDiag & (abs(x[0]-x[1]) == abs(y[0]-y[1])):
            diag = np.eye(abs(x[0]-x[1])+1).astype(int)
            if (x[1] - x[0]) != (y[1] - y[0]):
                diag = np.fliplr(diag)    
            df_map.iloc[y.min():y.max()+1, x.min():x.max()+1] += diag
            
    print(df_map.ge(2).values.sum())
    
dangerPoints(df,False) # Part 1
dangerPoints(df,True)  # Part 2

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

#define MAX_POS                 2048

int g_crabs[MAX_POS];

int main(int argc, char **argv) {
        int crab;
        long long int i, j, k, acc, a, best = -1, best_tot = LLONG_MAX, tot;

        while (fscanf(stdin, "%i,", &crab) == 1)
                g_crabs[crab]++;
        for (i = 0; i < MAX_POS; i++) {
                for (j = 0, tot = 0; j < MAX_POS; j++) {
                        a = labs(i - j);
                        for (k = 0, acc = 0; k < a; k++)
                                acc += (k + 1);
                        tot += acc * g_crabs[j];
                }

                if (tot < best_tot)
                        best_tot = tot, best = i;
        }

        printf("Best total amount of fuel: %lli to pos %lli\n", best_tot, best);
        return 0;
}

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

func getPartOne(numbers []int) int {
	sum := 0
	for _, number := range numbers {
		sum += number
	}
	avg := sum / len(numbers)
	fmt.Println("avg", avg)

	fuels := make(map[int]int, avg)
	var min int
	var align int
	for i := 1; i <= avg; i++ {
		fuel := 0
		for _, number := range numbers {
			fuel += int(math.Abs(float64(i - number)))
		}
		if min == 0 || fuel < min {
			min = fuel
			align = i
		}
		fuels[i] = fuel
	}

	//	fmt.Println("Fuels", fuels)
	fmt.Println("Align", align)

	return min
}

func getPartTwo(numbers []int) int {
	sum := 0
	for _, number := range numbers {
		sum += number
	}
	avg := sum / len(numbers)
	fmt.Println("avg", avg)

	fuels := make(map[int]int, avg)
	var min int
	var align int
	for i := 1; i <= avg*2; i++ {
		fuel := 0
		for _, number := range numbers {
			difference := int(math.Abs(float64(i - number)))
			fuel += difference * (difference + 1) / 2
		}
		if min == 0 || fuel < min {
			min = fuel
			align = i
		}
		fuels[i] = fuel
	}

	fmt.Println("Fuels", fuels)
	fmt.Println("Align", align)

	return min
}

func getRows(filename string) []int {
	file, err := os.Open(filename)
	if err != nil {
		panic(err)
	}
	defer file.Close()
	scanner := bufio.NewScanner(file)
	var numbers []int
	for scanner.Scan() {
		row := scanner.Text()
		fields := strings.Split(row, ",")
		for _, field := range fields {
			val, err := strconv.Atoi(field)
			if err != nil {
				panic(err)
			}
			numbers = append(numbers, val)
		}

	}
	return numbers
}

func main() {
	fmt.Println("Part one:", getPartOne(getRows("../input.txt")))
	fmt.Println("Part two:", getPartTwo(getRows("../input.txt")))
}

d←⍎⊃⊃⎕NGET'7.txt'1
⌊/+⌿|d∘.-⍳⌈/d
⌊/+⌿2÷⍨(1∘+×⊢)|d∘.-⍳⌈/d

      ]runtime "⌊/+⌿|d∘.-⍳⌈/d" -repeat=1000

* Benchmarking "⌊/+⌿|d∘.-⍳⌈/d", repeat=1000
              (ms) 
 CPU (avg):  3.125 
 Elapsed:    3.135 
      ]runtime "⌊/+⌿2÷⍨(1∘+×⊢)|d∘.-⍳⌈/d" -repeat=1000

* Benchmarking "⌊/+⌿2÷⍨(1∘+×⊢)|d∘.-⍳⌈/d", repeat=1000
              (ms) 
 CPU (avg):  4.219 
 Elapsed:    4.22

val input = Using.resource(Source.fromFile("7.txt"))(_.mkString.trim.split(',').map(_.toInt).toVector)
(0 to input.max).map(x => input.map(y => (y - x).abs).sum).min
(0 to input.max).map(x => input.map(y => ((y - x).abs * ((y - x).abs + 1)) / 2).sum).min

object Day8 {
	val data = readLines("8/data.txt")

	case class Line(input: Seq[String], display: Seq[String]) {
		val allObservations = input ++ display
	}

	val lines = data.map { l =>
		val parts = l.split(" \\| ")
		Line(parts(0).split(" "), parts(1).split(" "))
	}

	val digits = Seq("abcefg", "cf", "acdeg", "acdfg", "bcdf", "abdfg", "abdefg", "acf", "abcdefg", "abcdfg").map { p =>
		p.map(_.toInt - 'a').toSet
	}

	def main(args: Array[String]): Unit = {
		part1()
		part2()
	}

	def part1() = {
		val l1478 = Set(2, 4, 3, 7)
		println(lines.flatMap(_.display).count(p => l1478.contains(p.length)))
	}

	def part2() = {
		def isValidObservation(candidate: String, observation: String): Boolean = {
			val leds = observation.map { ch =>
				candidate.indexOf(ch)
			}.toSet
			digits contains leds
		}

		val candidates = "abcdefg".permutations.toSeq

		def process(line: Line) = {
			val patternOpt = candidates.find { candidate =>
				line.allObservations.forall(observation => isValidObservation(candidate, observation))
			}

			patternOpt match {
				case Some(pattern) =>
					val toPos = (pattern.toSeq zip (0 until 7)).map { case (ch, c) => ch -> c }.toMap

					val ds = line.display.map { obs =>
						digits.indexOf(obs.map(toPos).toSet)
					}
					ds.mkString("").toLong

				case None => throw new RuntimeException(s"Line $line seems to have no solution!")
			}

		}
		println(lines.map(process).sum)
	}

}

internal class Puzzle8 : Puzzle<int>
{
        
    protected override void Solve(string[] lines)
    {
        var sums = lines
            .Select(x => x.Split(" | "))
            .Aggregate(new List<string>(), (sums, signalPatterns) =>
            {
                var decoder = CreateDecoder(signalPatterns[0].Split(" "));
                sums.Add(string.Concat(signalPatterns[1].Split(" ").Select(x => Decode(x, decoder))));
                return sums;
            });

        One = sums.Sum(sum => Regex.Matches(sum, "1|4|7|8").Count);
        Two = sums.Sum(int.Parse);
    }

    private static IDictionary<char, char> CreateDecoder(string[] signals)
    {
        var translatedSegments = new Dictionary<char, char>();

        var nums = signals
            .Select(signal => new { signal, digit = GetDigitByLength(signal) })
            .Where(x => x.digit != null)
            .ToDictionary(x => x.digit!.Value, x => x.signal);

        nums[6] = signals.First(x => x.Length == 6 && x.Contains(nums[1][0]) != x.Contains(nums[1][1]));

        translatedSegments['a'] = nums[7].First(c => !nums[1].Contains(c));
        translatedSegments['c'] = nums[6].Contains(nums[1][0]) ? nums[1][1] : nums[1][0];
        translatedSegments['f'] = nums[6].Contains(nums[1][0]) ? nums[1][0] : nums[1][1];

        nums[3] = signals.First(x => x.Length == 5 &&
            x.Contains(translatedSegments['c']) && x.Contains(translatedSegments['f']));

        translatedSegments['b'] = nums[4].First(c => !nums[3].Contains(c));
        translatedSegments['g'] = nums[3].First(c => c != translatedSegments['a'] && !nums[4].Contains(c));
        translatedSegments['d'] = nums[3].First(c => !translatedSegments.ContainsValue(c));
        translatedSegments['e'] = "abcdefg".First(c => !translatedSegments.ContainsValue(c));

        return translatedSegments.ToDictionary(x => x.Value, x => x.Key);
    }

    private static int? GetDigitByLength(string segments) => segments.Length switch
    {
        2 => 1,
        3 => 7,
        4 => 4,
        7 => 8,
        _ => null
    };

    private static int Decode(string segment, IDictionary<char, char> decoder) => 
        string.Concat(segment.Select(x => decoder[x]).OrderBy(c => c)) switch
        {
            "abcefg" => 0,
            "cf" => 1,
            "acdeg" => 2,
            "acdfg" => 3,
            "bcdf" => 4,
            "abdfg" => 5,
            "abdefg" => 6,
            "acf" => 7,
            "abcdefg" => 8,
            "abcdfg" => 9,
            _ => -1
        };
}

import { readFile } from "../utils";

const array: Array<number> = [];

function setup(fishes: number[]) {
  for (let day = 0; day <= 8; day++) {
    array[day] = fishes.filter((f) => f === day).length;
  }
}

function increaseWithDays(days: number) {
  for (let day = 0; day < days; day++) {
    const zeroes = array.shift();
    if (zeroes) {
      if (!array[6]) {
        array[6] = zeroes;
      } else {
        array[6] = array[6] += zeroes;
      }
      array[8] = zeroes;
    }
  }
}

function runDay6() {
  const fishes: number[] = readFile(__dirname)[0]
    .split(",")
    .map((f) => parseInt(f, 10));
  setup(fishes);
  increaseWithDays(256);
  console.log("Solution: " + array.reduce((prev, curr) => (prev += curr)));
}

runDay6();

(import std)

(define main
  (do io/bind
      (<- input (io/map unwrap! (read-file "inputs/day8.txt")))
      (let1 entries (map parse-line (lines input)))
      (display (str-append "Part 1: " (show-nat (part1 entries))))
      (display (str-append "Part 2: " (show-int (part2 entries))))))

(define (part1 entries)
  (apps |> entries
        (flat-map (<o array/iter cadr))
        (filter (apps <o
                      (flip (list/elem? num/cmp) (list 2 3 4 7))
                      to-int
                      string/length-bytes))
        count))

(define (part2 entries)
  (sum (map output-value entries)))

(define (output-value [in-patterns out-patterns])
  (let ((in-patterns (array/iter in-patterns))
        ((seg-set n) (apps |> in-patterns
                           (iter/find (<o (= (to-nat n)) string/length-bytes))
                           unwrap!
                           string/bytes
                           (set/collect num/cmp)))
        (s1 (seg-set 2))
        (s4 (seg-set 4))
        ((decode pat)
         (let (((n x) (= (to-nat x) (string/length-bytes pat)))
               (s (set/collect num/cmp (string/bytes pat)))
               ((isect-n m s') (= (to-nat m) (set/count (set/isect num/cmp s s')))))
           (cond ((and (n 6) (isect-n 1 (set/diff num/cmp s4 s1)))  0)
                 (     (n 2)                                1)
                 ((and (n 5) (isect-n 2 s4))                2)
                 ((and (n 5) (isect-n 2 s1))                3)
                 (     (n 4)                                4)
                 (     (n 5)                                5)
                 ((and (n 6) (isect-n 1 s1))                6)
                 (     (n 3)                                7)
                 (     (n 7)                                8)
                 (else                                      9)))))
    (apps |> out-patterns
          array/iter-rev
          enumerate
          (map (fun ([i p]) (* (decode p) (powi 10 i))))
          sum)))

(define (parse-line s)
  (define segs (parse/take-bytes-while (<o not whitespace-byte?)))
  (unwrap!
   (parse (do parse/bind
              (<- as (parse/n-times (to-nat 10) (parse/thenl segs parse/space1)))
              (parse/string "|")
              (<- bs (parse/n-times (to-nat 4) (parse/thenr parse/space1 segs)))
              (parse/pure [as bs]))
          (trim s))))

import Data.List

main = interact solve

solve input = "Problem 1: " ++ show solution1 ++ "\n"
           ++ "Problem 2: " ++ show solution2 ++ "\n"
    where
        solution1 = length (filter(\w->elem (length w) [2,3,4,7]) allValues)
        allValues = foldr (\line acc -> words (drop 61 line) ++ acc) [] (lines input)
        solution2 = sum (map decodeOutVal (lines input))

decodeOutVal :: String -> Int
decodeOutVal line = foldl (\acc cDig -> 10*acc + decode sigPatts cDig) 0 codedDigits
    where
        sigPatts = take 58 line
        codedDigits = words (drop 61 line)

decode :: String -> String -> Int
decode sigPatts digit
    | length digit == 2 = 1
    | length digit == 4 = 4
    | length digit == 3 = 7
    | length digit == 7 = 8
    | length digit == 5 && elem e digit = 2
    | length digit == 5 && elem c digit = 3
    | length digit == 5 = 5
    | length digit == 6 && not (elem e digit) = 9
    | length digit == 6 && elem c digit = 0
    | otherwise = 6
    where
        -- Assume the signal patterns contain one of each digit 1-0.
        -- Segment E should appear 4 times in the signal patterns.
        -- Segment F should appear 9 times in the signal patterns.
        -- Segment C and F appear in digit 1. If F is known, then we can find C.
        e = (head.head) (filter (\w->length w==4) ((group.sort.concat.words) sigPatts))
        f = (head.head) (filter (\w->length w==9) ((group.sort.concat.words) sigPatts))
        c = (head.head) (filter (\w->length w==1) (words (filter (/=f) sigPatts)))

int solve_part1(vector<string> string_data)
{
    int count = 0;
    int n = string_data.size();
    string input;

    for (int i = 0; i < n; i++)
    {
        string tmp = string_data[i];
        tmp = tmp.substr(tmp.find("|")+2, tmp.length()-1);
        
        stringstream sstream(tmp);
        while(getline(sstream,input,' '))
        {
            int strlen = input.length();
            if (strlen == 2) count++;
            if (strlen == 3) count++;
            if (strlen == 4) count++;
            if (strlen == 7) count++;
        }

    }

    return count;

}

int solve_part2(vector<string> string_data)
{

    int count = 0;
    int n = string_data.size();
    string input,input_nums, output_nums;

    for (int i = 0; i < n; i++)
    {
        map<char,string> test;
        vector<string> strings_in;
        string tmp = string_data[i];
        input_nums = tmp.substr(0, tmp.find("|")-1);
        output_nums = tmp.substr(tmp.find("|")+2, tmp.size()-1);

        stringstream sstream(input_nums);
        int index = 0;
        
        while(getline(sstream,input,' '))
        {
            sort(input.begin(), input.end());
            strings_in.push_back(input);
            
            int strlen = input.length();
            if (strlen == 2)
            {
                test.insert({'1',input});
            }
            if (strlen == 3)
            {
                test.insert({'7',input});
            }
            if (strlen == 4)
            {
                test.insert({'4',input});
            }
            if (strlen == 7)
            {
                test.insert({'8',input});
            }
        }

        for (int j = 0; j < strings_in.size(); j++)
        {
            if (strings_in[j].length() == 6)
            {
                cout << strings_in[j] << endl;
                cout << test['7'] << endl;

                if (!string_in_string(test['7'],strings_in[j]))
                {
                    test.insert({'6', strings_in[j]});
                } 
                else if (string_in_string(test['4'], strings_in[j]))
                {
                    test.insert({'9', strings_in[j]});
                }
                else
                {
                    test.insert({'0', strings_in[j]});
                }   
            }
        }

        for (int j = 0; j < strings_in.size(); j++)
        {
            if ((strings_in[j].length() == 5))
            {
                if (string_in_string(test['1'], strings_in[j]))
                {
                    test.insert({'3', strings_in[j]});
                }
                else if (string_in_string(strings_in[j],test['6']))
                {
                    test.insert({'5', strings_in[j]});
                }
                else
                {
                    test.insert({'2', strings_in[j]});
                }
            }
        }

        stringstream sstream2(output_nums);
        string output_digits = "";
        while (getline(sstream2,input,' '))
        {
            sort(input.begin(), input.end());
            for (const auto& [key, value] : test)
                if (value == input)
                {
                    output_digits.push_back(key);
                }
            
        }

        count += stoi(output_digits);

    }
    return count;
}

#include <stdio.h>
#include <stdint.h>

int count[10] = { 0 };
int total;

uint8_t read_segment(FILE *fp) {
        char buff[32] = { 0 };
        uint8_t segment = 0;
        int i;

        if (fscanf(fp, " %s", buff) < 1)
                return 0xFF;

        for (i = 0; buff[i]; i++)
                segment |= 1 << (buff[i] - 'a');
        return segment;
}


int lookup_segment(uint8_t seg, uint8_t *list) {
        int i;

        for (i = 0; i < 10; i++)
                if (seg == list[i])
                        return i;
        return 0;
}


int count_bits(uint8_t byte) {
        int i, n;

        for (i = n = 0; i < 8; i++)
                if (byte & (1 << i))
                        n++;
        return n;
}


void solve_segments(uint8_t *input_segments) {
        uint8_t tmp_segments[10] = { 0 };
        int i, j;

        for (i = j = 0; i < 10; i++) {
                if (count_bits(input_segments[i]) == 2)
                        tmp_segments[1] = input_segments[i];
                else if (count_bits(input_segments[i]) == 3)
                        tmp_segments[7] = input_segments[i];
                else if (count_bits(input_segments[i]) == 4)
                        tmp_segments[4] = input_segments[i];
                else if (count_bits(input_segments[i]) == 7)
                        tmp_segments[8] = input_segments[i];
        }
        for (i = 0; i < 10; i++)
                if (count_bits(input_segments[i]) == 5)
                        if ((input_segments[i] | tmp_segments[1]) == input_segments[i])
                                tmp_segments[3] = input_segments[i]; // Found number 3
        for (i = 0; i < 10; i++)
                if (count_bits(input_segments[i]) == 6) {
                        if ((input_segments[i] | tmp_segments[3]) == input_segments[i])
                                tmp_segments[9] = input_segments[i]; // Found number 9
                        else if ((input_segments[i] | tmp_segments[1]) == 0x7F)
                                tmp_segments[6] = input_segments[i]; // found number 6
                        else
                                tmp_segments[0] = input_segments[i]; // found number 0
                }

        for (i = 0; i < 10; i++)
                if (count_bits(input_segments[i]) == 5 && (input_segments[i] | tmp_segments[1]) != input_segments[i]) {
                        if ((input_segments[i] | tmp_segments[1]) == tmp_segments[9])
                                tmp_segments[5] = input_segments[i];
                        else
                                tmp_segments[2] = input_segments[i];
                }

        for (i = 0; i < 10; i++)
                input_segments[i] = tmp_segments[i];
}


int process_line(FILE *fp) {
        int i, j;
        uint8_t segments[10];

        for (i = 0; i < 10; i++)
                if ((segments[i] = read_segment(fp)) == 0xFF)
                        return 0;
        solve_segments(segments);
        fscanf(fp, " |");
        int seg[4], num;
        for (j = 0; j < 4; j++)
                count[(seg[j] = lookup_segment(read_segment(fp), segments))]++;
        num = seg[0] * 1000 + seg[1] * 100 + seg[2] * 10 + seg[3];
        total += num;
        return 1;
}


int main(int argc, char **argv) {
        while (process_line(stdin));
        printf("Result A: %i\n", count[1] + count[4] + count[7] + count[8]);
        printf("Result B: %i\n", total);

        return 0;
}

rows = open("8.in").readlines()
p1 = sum(len(segment) in [2, 3, 4, 7] for row in rows for segment in row.split(" | ")[1].split())
p2 = 0
for line in rows:
    inputs, outputs = line.split(" | ")
    segments = list(map(frozenset, inputs.split()))

    one = next(x for x in segments if len(x) == 2)
    four = next(x for x in segments if len(x) == 4)
    seven = next(x for x in segments if len(x) == 3)
    eight = next(x for x in segments if len(x) == 7)

    three = next(x for x in segments if len(x) == 5 and x | one == x)
    nine = next(x for x in segments if len(x) == 6 and x == four | three)
    zero = next(x for x in segments if len(x) == 6 and x != nine and x | one == x)
    six = next(x for x in segments if len(x) == 6 and x != nine and x != zero)
    five = next(x for x in segments if len(x) == 5 and (nine - one) | x == x)
    two = next(x for x in segments if len(x) == 5 and x != three and x != five)
    lookup = dict(zip((zero, one, two, three, four, five, six, seven, eight, nine), map(str, range(10))))

    p2 += int("".join(lookup[o] for o in map(frozenset, outputs.split())))

print(p1, p2)