Skip to content

Instantly share code, notes, and snippets.

@RichardVasquez
Last active December 1, 2021 20:54
Show Gist options
  • Save RichardVasquez/4997aac903c1dfc8cfd34faf74fd6f20 to your computer and use it in GitHub Desktop.
Save RichardVasquez/4997aac903c1dfc8cfd34faf74fd6f20 to your computer and use it in GitHub Desktop.
Day 7 Advent of Code 2020
using System;
using System.Collections.Generic;
using System.Linq;
using AdventOfCode.Library;
namespace AdventOfCode
{
// Day 07
internal static class Program
{
private const bool DoPart1 = true;
private const bool DoPart2 = true;
public static void Main()
{
var data = TextUtility.ReadLines(removeBlank: true);
// Clean up English to data
for (var i = 0; i < data.Count; i++)
{
string s = data[i].Replace(" bags contain ", "|").Replace("no other ", "0 ")
.Replace(" bag, ", ":").Replace(" bags, ", ":")
.Replace(" bags.", "").Replace(" bag.", "");
data[i] = s;
}
// Create the list of bags
var bags = data.Select(s => new Bag(s)).ToList();
// Establish the graph
foreach (var bag in bags)
{
var r = bag.References;
foreach (string s in r)
{
var pieces = s.Split(' ');
var total = Convert.ToInt32(pieces[0]);
string name = string.Join(" ", pieces.ToList().Skip(1).Take(pieces.Length - 1).ToArray());
var targetBag = bags.Find(b => b.Name == name);
if (total != 0)
{
bag.AddContents(total, targetBag);
}
targetBag?.AddContainer(bag);
}
}
data.Process(DoPart1, 1, bags, Solver1);
data.Process(DoPart2, 2, bags, Solver2);
}
private static string Solver1(List<string> arg1, object arg2)
{
var bags = (List<Bag>) arg2;
var node = bags.Find(n => n.Name == "shiny gold");
// Create pools of bags we're going to examine - prevent duplicates
// What we're looking at now
var examinePool = new HashSet<Bag>();
// Unique bags we've already looked at
var donePool = new HashSet<Bag>();
// Fresh set. These are the ones we're going to start with.
if (node != null)
{
foreach (var bag in node.Contained)
{
examinePool.Add(bag);
}
}
while (examinePool.Count > 0)
{
// Because you don't adjust iterables while iterating
var tempList = examinePool.ToList();
foreach (var bag in tempList)
{
// throw the current bag into ones we know we're counting
donePool.Add(bag);
// Add bags that can contain this bag to be examined as well.
examinePool.UnionWith(bag.Contained);
// Remove this bag from consideration in the next iteration
examinePool.Remove(bag);
}
}
return donePool.Count.ToString();
}
private static string Solver2(List<string> arg1, object arg2)
{
var bags = (List<Bag>) arg2;
var node = bags.Find(n => n.Name == "shiny gold");
return node != null
? node.CountInside().ToString()
: "-1";
}
}
}
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
namespace AdventOfCode
{
[DebuggerDisplay("Name: {Name} Parents: {Parents}")]
public class Bag
{
public readonly string Name;
private readonly Dictionary<Bag, int> _contains;
public readonly List<string> References;
public readonly List<Bag> Contained;
public string Parents => string.Join(":", Contained.Select(c => c.Name));
public Bag(string s)
{
var parts = s.Split('|');
Name = parts[0];
_contains = new Dictionary<Bag, int>();
Contained = new List<Bag>();
var contains = parts[1].Split(':');
References = contains.ToList();
}
public void AddContainer(Bag b)
{
Contained.Add(b);
}
public void AddContents(int amount, Bag b)
{
_contains[b] = amount;
}
public int CountInside()
{
// Sum the quantity of each color bag,
// plus multiply the quantity of each color bag with how many bags it has to contain.
return _contains.Values.ToList().Sum() +
_contains.Where(c => c.Value > 0)
.Sum(contain => contain.Value * contain.Key.CountInside());
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment