Advent of Code 2020

Unrack #541 Dic '20

#538 Ese diccionario seguro que tiene la forma de {'nodo': [nodos...]}

eisenfaust #542 Dic '20

Unrack #543 Dic '20

Vaya experto en networkx que me he vuelto esta mañana.....

spoiler

import re
import networkx as nx

def graph_from_txt(input):
    data = open(input).readlines()
    graph = nx.DiGraph()

for line in data:
    m = re.match(r"(.*) bags contain (.*)$", line)
    if m:
        color = m.group(1)
        remain = m.group(2)
        for child in re.findall(r"([\d]+) (.*?) bag", remain):
            graph.add_edge(color, child[1], count=int(child[0]))

return graph

def countBags(graph, root):
    return sum([val['count'] * countBags(graph, k) +val['count'] for k, val in graph[root].items()])

print(f"Part 1: {len(nx.ancestors(graph_from_txt('input.txt'), 'shiny gold'))}")
print(f"Part 2: {countBags(graph_from_txt('input.txt'), 'shiny gold')}")

Lo peor es que mañana se me va a olvidar

1 respuesta

R

RsTTa #544 Dic '20

Día 7. En la primera parte no me salia recursivo y lo he tenido que hacer iterativo. Luego para la segunda me ha tocado sacar papel y boli y ya si que la he hecho recursiva.
A ver cuanto duro por aquí, parece que ya van a empezar a requerir más tiempo. La verdad que he perdido bastante tiempo por no plantear primero la solución general en papel y luego hacer el código.

Parte 1

spoiler

import re


def count_node_parents(node_name, graph):
    stack = [node for node in graph.get(node_name, [])]
    visited_nodes = {node_name, *stack}
    parents_count = 0
    while stack:
        curr_node = stack.pop()
        parents_count += 1
        for node in graph.get(curr_node, []):
            if node not in visited_nodes:
                stack.append(node)
                visited_nodes.add(node)
    return parents_count


if __name__ == '__main__':
    graph = {}
    with open('input', 'r') as f:
        for line in f.readlines():
            container_info, content_info = line.split('contain')
            if content_info.strip() == 'no other bags.':
                continue
            container_color = re.search('.+?(?= bags)', container_info).group()
            for inner_bag_info in content_info.split(','):
                inner_bag_color = re.search('[a-z][a-z ]*(?= bags?)', inner_bag_info).group()
                if inner_bag_color not in graph:
                    graph[inner_bag_color] = []
                graph[inner_bag_color].append(cont

Parte 2

spoiler

import re


def count_node_childrens_with_weight(node_name, visited_nodes, graph):
    acc = 0
    for curr_node, curr_weight in graph.get(node_name, []):
        if curr_node not in visited_nodes:
            acc += curr_weight + \
                   curr_weight * \
                   count_node_childrens_with_weight(curr_node, {*visited_nodes, curr_node}, graph)
    return acc


if __name__ == '__main__':
    graph = {}
    with open('input', 'r') as f:
        for line in f.readlines():
            container_info, content_info = line.split('contain')
            if content_info.strip() == 'no other bags.':
                continue
            container_color = re.search('.+?(?= bags)', container_info).group()
            if container_color not in graph:
                graph[container_color] = []
            for inner_bag_info in content_info.split(','):
                match = re.search('([0-9]+)(?: )([a-z][a-z ]*(?= bags?))', inner_bag_info)
                amount, color = int(match.group(1)), match.group(2)
                graph[container_color].append((color, amount))
    print(count_node_childrens_with_weight('shiny gold', set(), graph))

eZpit #545 Dic '20 Juntabrackets

Yo hoy la verdad me he liado porque para la parte 1 he asumido que habría loops y desde el principio quería evitar recursividad infinita.

Day 7 pt 1

type InnerBagsRules = Vec<(String, usize)>;

pub fn count_bags_containing_shiny_gold(lines: &Vec<String>) -> usize {
    let rules = parse_bag_rules(lines);
    // Cache of already checked bags
    let mut cache = HashMap::<String, bool>::new();
    fn contains_shiny_gold(
        rules: &HashMap<String, InnerBagsRules>,
        contains: &mut HashMap<String, bool>,
        bag_color: &String
    ) -> bool {
        return contains.get(bag_color).copied().unwrap_or_else(|| {
            for (inner_color, _) in rules.get(bag_color).unwrap().iter() {
                if inner_color == "shiny gold" {
                    contains.insert(bag_color.clone(), true);
                    return true
                } else if contains_shiny_gold(rules, contains, inner_color) {
                    contains.insert(bag_color.clone(), true);
                    return true
                }
            }
            contains.insert(bag_color.clone(), false);
            return false
        })
    }
    let mut count = 0_usize;
    for (bag_color, _) in rules.iter() {
        if contains_shiny_gold(&rules, &mut cache, &bag_color) {
            count += 1
        }
    }
    return count
}

Day 7 pt 2

type InnerBagsRules = Vec<(String, usize)>;

pub fn count_bags_inside_shiny_gold(lines: &Vec<String>) -> usize {
    let rules = parse_bag_rules(lines);
    // Cache of already checked bags & their capacity
    let mut cache = HashMap::<String, usize>::new();
    fn find_capacity(
        rules: &HashMap<String, InnerBagsRules>,
        cache: &mut HashMap<String, usize>,
        bag_color: &String
    ) -> usize {
        return cache.get(bag_color).copied().unwrap_or_else(|| {
            let mut count = 0_usize;
            for (color, quantity) in rules.get(bag_color).unwrap().iter() {
                // Add the (bag iself + the inner bags) * number of times
                count += (1 + find_capacity(rules, cache, color)) * quantity;
            }
            cache.insert(bag_color.clone(), count);
            return count;
        })
    }
    return find_capacity(&rules, &mut cache, &"shiny gold".to_string())
}

1 respuesta

Fyn4r #546 Dic '20 Inocente

No lo pensé mucho pero no puede haber ciclos tal y como está planteado el problema, si no no habría solución

1

sergioRG #547 Dic '20 Juntabrackets

#543 me gusta networkx, la utilicé mucho en una asignatura de teoría de redes y facilita mucho la vida
#545 Piensa que si hubiera loops no tendría sentido que te pidieran respuesta alguna en ninguno de los dos apartados porque no podría existir.

2 respuestas

eZpit #548 Dic '20 Juntabrackets

#547 El primer apartado SI podría tener cierto sentido. E.g. si se da el caso que "bright white" -> "muted yellow" -> "bright white", puedes darte cuenta que estás en un loop y dejar de iterar porque no habrá "shiny gold" dentro. Aun así, necesitarías bags infinitas, que no tendría sentido xd

1 respuesta

sergioRG #549 Dic '20 Juntabrackets

#548 Cierto es. Yo asumí que era un DAG primero por la dificultad general de los problemas y segundo porque semánticamente se me haría raro en un problema así (y de hecho pensaba que era imposible). También porque siempre me ha dado mucho cáncer lo de las strongly connected components y deseaba con todo mi corazón que no hubiera que recurrir a ello.

Unrack #550 Dic '20

#547 Y tanto. No la había usado nunca la verdad y va finísima. Bueno he intentado hacer el plot automático que tiene y en este grafo se va de madre.

NeV3rKilL #551 Dic '20 :psyduck:

Yo este me da que no lo voy a sacar. No sé cómo salir de la recursividad

Traber #552 Dic '20

Mi solución de hoy:

Program.cs

using System;
using System.IO;

namespace Day7 {
	class Program {
		private static string[]      __Lines;
		public static BagCollection    Bags = new BagCollection();

	static void Main(string[] args) {
		__Init();

		int FirstSolution   = __FirstPart();
		long SecondSolution = __SecondPart();

		Console.WriteLine("First  part solution: " + FirstSolution);
		Console.WriteLine("Second part solution: " + SecondSolution);
	}

	public static int __FirstPart() {
		Bag InitialBag                  = Bags.Get(new Bag("shiny", "gold"));
		BagCollection DifferentBagTypes = new BagCollection();
		
		foreach (Bag bag in Bags.Items) {
			if (!bag.Equals(InitialBag)) {
				if (bag.CanHold(InitialBag, true)) {
					Console.WriteLine(bag.Attribute + " " + bag.Color);
					DifferentBagTypes.Add(bag);
				}
			}
		}
		
		return DifferentBagTypes.Count;
	}

	public static long __SecondPart() {
		Bag InitialBag = Bags.Get(new Bag("shiny", "gold"));

		return InitialBag.InnerBags();
	}

	private static void __Init() {
		__Lines = File.ReadAllLines("input.txt");

		foreach(string Line in __Lines) {
			/*
			light red bags contain 1 bright white bag, 2 muted yellow bags.
			dotted black bags contain no other bags.
			*/

			string[] LineData = Line.Split(" contain ");

			string[] BagData         = LineData[0].Replace(" bags", "").Split(" ");
			string[] ContainableData = LineData[1].Split(", ");

			Bag bag = new Bag(BagData[0], BagData[1]);
			foreach(string ContainableDataItem in ContainableData) {
				if(ContainableDataItem == "no other bags.") {
					continue;
				}

				string[] CurrentBagData = ContainableDataItem
					.Substring(2)
					.Split(" ")
				;

				int CurrentBagDataCount = Int32.Parse(ContainableDataItem.Substring(0, 1));

				bag.AddHoldable(new Bag(CurrentBagData[0].Trim(), CurrentBagData[1].Trim()), CurrentBagDataCount);
			}

			Bags.Add(bag);
		}
	}
}
}

Bag.cs

using System;
using System.Collections.Generic;
using System.Text;

namespace Day7 {
	public class Bag {
		private string __Attribute;
		public string Attribute {
			get {
				return this.__Attribute;
			}
		}

	private string __Color;
	public string Color {
		get {
			return this.__Color;
		}
	}

	private Dictionary<Bag, int> __CanContain = new Dictionary<Bag, int>();
	public Dictionary<Bag, int> CanContain {
		get {
			return this.__CanContain;
		}
	}

	public Bag(Bag Other) {
		this.__Attribute = Other.Attribute;
		this.__Color     = Other.Color;
	}

	public Bag(string Attribute, string Color) {
		this.__Attribute = Attribute;
		this.__Color     = Color;
	}

	public void AddHoldable(Bag bag, int Amount) {
		this.__CanContain.Add(bag, Amount);
	}

	public bool Equals(Bag Equatable) {
		return 
			this.Attribute == Equatable.Attribute
			&&
			this.Color     == Equatable.Color
		;
	}

	public bool CanHold(Bag HoldableBag, bool Recursive = false) {
		bool Result = false;
		foreach (Bag InnerBag in this.__CanContain.Keys) {
			if (Result) {
				continue;
			}

			Bag ReferencedBag = Program.Bags.Get(InnerBag);
			if(
				ReferencedBag.Equals(HoldableBag)
			) {
				Result = true;
			}

			if (!Result && Recursive) {
				Result = ReferencedBag.CanHold(HoldableBag, Recursive);
			}
		}

		return Result;
	}

	public long InnerBags(bool Recursive = true) {
		long Inner = 0;
		foreach (KeyValuePair<Bag, int> InnerBag in this.__CanContain) {
			Bag ReferencedBag = Program.Bags.Get(InnerBag.Key);

			Inner += InnerBag.Value;

			if (Recursive) {
				Inner += InnerBag.Value * ReferencedBag.InnerBags(Recursive);
			}
		}

		return Inner;
	}
}
}

BagCollection.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Day7 {
	public class BagCollection {
		private Dictionary<Tuple<string, string>, Bag> __Collection = new Dictionary<Tuple<string, string>, Bag>();

	public int Count {
		get {
			return this.__Collection.Count;
		}
	}

	public List<Bag> Items {
		get {
			return new List<Bag>(this.__Collection.Values);
		}
	}

	public BagCollection() { }

	public BagCollection Add(Bag bag) {
		this.__Collection.Add(this.__GetBagTuple(bag), bag);

		return this;
	}

	public Bag Get(Bag bag) {
		if (this.Contains(bag)) {
			return this.__Collection[this.__GetBagTuple(bag)];
		}

		return null;
	}

	public List<Bag> ContainableBy(Bag bag) {
		List<Bag> Containable = new List<Bag>();
		foreach(Bag StoredBag in this.__Collection.Values) {
			foreach(KeyValuePair<Bag, int> Holdable in StoredBag.CanContain) {
				if(
					Holdable.Equals(bag)
				) {
					Containable.Add(new Bag(StoredBag));
				}
			}
		}

		return Containable;
	}

	public bool Contains(Bag bag) {
		return this.__Collection.ContainsKey(this.__GetBagTuple(bag));
	}

	private Tuple<string, string> __GetBagTuple(Bag bag) {
		return new Tuple<string, string>(bag.Attribute, bag.Color);
	}
}
}

sergioRG #553 Dic '20 Juntabrackets

He hecho un video explicando como he hecho el 7 por si a alguien le ayuda, perdon por la nula edicion, voz de mierda y quedarme atascado, lo he improvisado un poco xd

No me tireis mucha mierda porfa

3 1 respuesta

AikonCWD #554 Dic '20 Git Gud

#553 es tu voz?

1 respuesta

sergioRG #555 Dic '20 Juntabrackets

#554 si, por?

1 respuesta

eondev #556 Dic '20

#555 tienes una voz muy bonita :$

eisenfaust #557 Dic '20

No les hagas caso. ¡Ánimo crack!

eondev #558 Dic '20

coño que yo lo digo en serio, es una voz agradable xDDDD

JuAn4k4 #559 Dic '20

Rust, modo vago hoy que estoy cansado

spoiler


fn main() {
    let (bag_contains, bag_contained_in) = create_graph();
    phase_1(bag_contained_in);
    phase_2(bag_contains);
}

type Graph = HashMap<String, HashMap<String, usize>>;

fn phase_1(bag_contained_in: Graph) {
    let bags = traverse(&bag_contained_in, vec!["shiny gold"], HashSet::new());
    println!("Day 7 Phase 1: {}", bags.len() - 1);
}

fn traverse(graph: &Graph, to_add: Vec<&str>, mut visited: HashSet<String>) -> HashSet<String> {
    let new_nodes: Vec<&str> = to_add.iter().filter(|x| !visited.contains(**x)).map(|x| *x).collect();
    

if new_nodes.is_empty() {
    return visited;
}

let next_to_add: Vec<&str> = new_nodes.iter()
    .flat_map(|new_node| graph.get(*new_node).unwrap().keys())
    .map(|x| x.as_str())
    .collect();
to_add.iter().for_each(|x| { visited.insert(x.to_string()); });

return traverse(graph, next_to_add, visited)
}

fn phase_2(bag_contains: Graph) {
    let how_many_bags = open(&bag_contains, &bag_contains.get("shiny gold").unwrap());
    println!("Day 7 Phase 2: {}", how_many_bags);
}

fn open(bag_contains: &Graph, bag: &HashMap<String, usize>) -> usize {
    if bag.is_empty() { return 0; }

bag.iter()
    .map(|(contained_bag, times)| times + times * open(bag_contains, &bag_contains.get(contained_bag).unwrap()))
    .sum()
}

fn create_graph() -> (Graph, Graph) {
    let mut bag_contains: Graph = HashMap::new();
    let mut bag_contained_in: Graph = HashMap::new();
    let contains_regex = Regex::new(r"(\d+) ([a-z ]+) bags?.?").unwrap();

read_file().iter().for_each(|rule| {
    let bag = rule.split("bags").nth(0).unwrap().trim();
    let contains_str: Vec<&str> = rule.split("contain").nth(1).unwrap()
        .split(',')
        .map(|x| x.trim())
        .collect();

    bag_contains.insert(bag.to_string(), HashMap::new());
    if !bag_contained_in.contains_key(bag) {
        bag_contained_in.insert(bag.to_string(), HashMap::new());
    }

    contains_str.iter().for_each(|contains_bag_str| { // N {bag_name} bag(s.)
        if contains_bag_str.eq_ignore_ascii_case("no other bags.") {
            return;
        }
        let caps = contains_regex.captures(contains_bag_str).unwrap();
        let count = caps.get(1).map_or(0, |m| m.as_str().parse::<usize>().unwrap());
        let bag_name = caps.get(2).map_or("", |m| m.as_str()).trim();

        if !bag_contained_in.contains_key(bag_name) {
            bag_contained_in.insert(bag_name.to_string(), HashMap::new());
        }

        bag_contains.get_mut(&bag.to_string()).unwrap().insert(bag_name.to_string(), count);
        bag_contained_in.get_mut(&bag_name.to_string()).unwrap().insert(bag.to_string(), count);
    });
});

return (bag_contains, bag_contained_in);
}


fn read_file() -> Vec<String> {
    let file = BufReader::new(File::open("day_7/src/day_7_input.txt").unwrap());
    file.lines().map(|l| l.unwrap()).collect()
}

test3y #560 Dic '20

¿Alguien que sepa de haskell sabe en qué hay que fijarse para saber si un paquete de hackage entra dentro de los "comunes" y es normal usarlo? Porque por lo que veo aquí no hay nada parecido a una librería standard, y no sé si hay que mirar el campo "safe haskell" y que ponga safe o trustworthy o en el campo "stability" o qué hostias xD.

Dejo los de ayer y hoy:

días 6 y 7

1

Leos #561 Dic '20

Día 2 terminado, la de tiempo que pierdo por ser rust pero cada vez me siento menos subnormal con él.

Segundo día finiquitado, a ver si recupero un poco el ritmo XD

https://github.com/Leos1113/Advent-of-code-2020/tree/main/day2

sergioRG #562 Dic '20 Juntabrackets

Bastante chulo el de hoy, no hay nada que parsear. La segunda parte la he hecho a fuerza bruta, pero la verdad es que tengo curiosidad por si hay alguna manera de hacerlo significativamente más rápido.

1 1 respuesta

Traber #563 Dic '20

#562 Lo que yo no entiendo es si hay que cambiar el código o el input, supongo que haciendo cualquiera de las dos cosas podría conseguirlo xd

1 respuesta

sergioRG #564 Dic '20 Juntabrackets

#563 Yo cambio el código una vez leído. Pero sí, podrías generar muchos ficheros con el mismo programa pero con una instrucción cambiada, ejecutarlos todos y ver cuál es el que te interesa.

Mi solución para ambas partes

spoiler

from copy import deepcopy

program = [
    (x[0], int(x[1]))
    for x in 
    [
        x.strip().split(' ')
        for x in open('input.txt', 'r').readlines()
    ]
]


def exec_instruction(ins_line, acc, ip):
    instruction, value = ins_line
    if instruction == 'acc':
        return acc + value, ip + 1
    elif instruction == 'jmp':
        return acc, ip + value
    else:
        return acc, ip + 1



def swap_instruction(instruction):
    if instruction == 'jmp':
        return 'nop'
    elif instruction == 'nop':
        return 'jmp'



def exec_program(p_lines, acc, visit_cnt, ip, nd=False):
    while ip >= 0 and ip < len(p_lines):
        instruction, value = p_lines[ip]
        if nd and instruction != 'acc':
            p_lines[ip] = (swap_instruction(instruction), value)
            exec_program(p_lines, acc, deepcopy(visit_cnt), ip, False)
            p_lines[ip] = (instruction, value)
        visit_cnt[ip] += 1
        if visit_cnt[ip] == 2: break
        acc, ip = exec_instruction(p_lines[ip], acc, ip)
    if all(x < 2 for x in visit_cnt) and ip == len(p_lines):
        print(f'loopless execution:{acc}')
    elif nd:
        print(f'infinite loop execution:{acc}')


exec_program(program, 0, [0] * len(program), 0, True)

La explicación

spoiler

Huk #565 Dic '20

brutal el hilo un 10

1 respuesta

sergioRG #566 Dic '20 Juntabrackets

#565 es como el conter pero todos somos publikeros

Traber #567 Dic '20

Bueno, fuerzabruteado por aquí también xD:

spoiler

using System;
using System.Collections.Generic;
using System.IO;

namespace Day8 {
	class Program {
		private static string[]  __Instructions;
		private static int       __CurrentIndex = 0;
		private static int       __Accumulator  = 0;
		private static List<int> __Stack        = new List<int>();

	static void Main(string[] args) {
		__Init();

		int FirstSolution  = __FirstPart();
		int SecondSolution = __SecondPart();

		Console.WriteLine("First  part solution: " + FirstSolution);
		Console.WriteLine("Second part solution: " + SecondSolution);
	}

	private static int __FirstPart() {
		__CleanStack();

		while (true) {
			if (__OutOfBounds() || __Repeated()) {
				break;
			}

			__Step();
		}

		return __Accumulator;
	}

	private static int __SecondPart() {
		__CleanStack();

		int __InstructionToSwap = __SwapInstruction(0);

		while (true) {
			if (__Repeated()) {
				__CleanStack();

				__InstructionToSwap = __SwapInstruction(__InstructionToSwap, true);

				if(__InstructionToSwap >= __Instructions.Length) {
					break;
				}
			}

			if (__OutOfBounds()) {
				Console.WriteLine("Line to swap: " + (__InstructionToSwap - 1));
				break;
			}

			__Step();
		}

		return __Accumulator;
	}

	private static int __SwapInstruction(int InitialIndex, bool Revert = false) {
		int Index = InitialIndex;
		if (Revert) {
			__DoSwap(InitialIndex);
		}
		Index++;

		while (true) {
			Index++;

			if(Index >= __Instructions.Length) {
				break;
			}

			if (__DoSwap(Index)) {
				break;
			}
		}

		return Index;
	}

	private static bool __DoSwap(int Index) {
		if (__Instructions[Index].Contains("nop")) {
			__Instructions[Index] = __Instructions[Index].Replace("nop", "jmp");
			return true;
		}
		else if (__Instructions[Index].Contains("jmp")) {
			__Instructions[Index] = __Instructions[Index].Replace("jmp", "nop");
			return true;
		}

		return false;
	}

	private static void __CleanStack() {
		__Stack        = new List<int>();
		__Accumulator  = 0;
		__CurrentIndex = 0;
	}

	private static void __Step() {
		string[] InstructionData   = __Instructions[__CurrentIndex].Split(" ");
		string   InstructionAction = InstructionData[0];
		int      InstructionValue  = Int32.Parse(InstructionData[1]);

		__Stack.Add(__CurrentIndex);
		switch (InstructionAction) {
			case "nop":
				__CurrentIndex++;
				break;
			case "acc":
				__Accumulator += InstructionValue;
				__CurrentIndex++;
				break;
			case "jmp":
				__CurrentIndex += InstructionValue;
				break;
		}
	}

	private static bool __OutOfBounds() {
		return
			(__CurrentIndex < 0) ||
			(__CurrentIndex >= __Instructions.Length)
		;
	}

	private static bool __Repeated() {
		return (__Stack.Contains(__CurrentIndex));
	}

	private static void __Init() {
		__Instructions = File.ReadAllLines("input.txt");
	}
}
}

Slowbro #568 Dic '20

Madre mía, que fuera estoy... lo que me ha costado el día 7.

spoiler

@sergioRG Hostia, te veo suelto con el tema de grafos, ¿alguna referencia más allá de practicar para ver bien estos ejercicios?

2 respuestas

HeXaN #569 Dic '20

#568Slowbro:
¿alguna referencia más allá de practicar para ver bien estos ejercicios?

Estudiar grafos.

https://runestone.academy/runestone/books/published/pythonds/Graphs/toctree.html

2

sergioRG #570 Dic '20 Juntabrackets

#568 Hacer muchos problemas de grafos, además de estudiar algo de teoría de ídem. Pero la verdad es que es más práctica y pelearse que otra cosa, no por leer mucho aprendes a resolver problemas más rápido.

Si vas haciendo de aquí mejoras fijo, además aquí puedes ver las soluciones que han enviado los demás usuarios. Si encuentras alguna legible puedes aprender bastante también, la verdad.

https://codeforces.com/problemset?order=BY_RATING_ASC&tags=graphs%2Ctrees

1

¿Dónde me apunto?

Normas

Leaderboard privado para el pique sano

Las respuestas se postean en Spoiler + code

Usuarios habituales

Tags