8
\$\begingroup\$

This year's AoC has a puzzle for day 24 that was (supposedly) intended to be solved with recursion.

Here is the description:

--- Day 24: Electromagnetic Moat ---

The CPU itself is a large, black building surrounded by a bottomless pit. Enormous metal tubes extend outward from the side of the building at regular intervals and descend down into the void. There's no way to cross, but you need to get inside.

No way, of course, other than building a bridge out of the magnetic components strewn about nearby.

Each component has two ports, one on each end. The ports come in all different types, and only matching types can be connected. You take an inventory of the components by their port types (your puzzle input). Each port is identified by the number of pins it uses; more pins mean a stronger connection for your bridge. A 3/7 component, for example, has a type-3 port on one side, and a type-7 port on the other.

Your side of the pit is metallic; a perfect surface to connect a magnetic, zero-pin port. Because of this, the first port you use must be of type 0. It doesn't matter what type of port you end with; your goal is just to make the bridge as strong as possible.

The strength of a bridge is the sum of the port types in each component. For example, if your bridge is made of components 0/3, 3/7, and 7/4, your bridge has a strength of 0+3 + 3+7 + 7+4 = 24.

For example, suppose you had the following components:

0/2
2/2
2/3
3/4
3/5
0/1
10/1
9/10

With them, you could make the following valid bridges:

0/1
0/1--10/1
0/1--10/1--9/10
0/2
0/2--2/3
0/2--2/3--3/4
0/2--2/3--3/5
0/2--2/2
0/2--2/2--2/3
0/2--2/2--2/3--3/4
0/2--2/2--2/3--3/5

(Note how, as shown by 10/1, order of ports within a component doesn't matter. However, you may only use each port on a component once.)

Of these bridges, the strongest one is 0/1--10/1--9/10; it has a strength of 0+1 + 1+10 + 10+9 = 31.

What is the strength of the strongest bridge you can make with the components you have available?

I've solved it via simple direct recursion:

var temp = File.ReadAllLines(@"N:\input.txt").Select(x => (int.Parse(x.Split('/').First()), int.Parse(x.Split('/').Last()))).ToList();
var workChain = new HashSet<(int, int)>();
var map = new Dictionary<(int, int), List<(int, int)>>(temp.Count);
foreach (var entry in temp)
{
    map.Add(entry, nextStack(entry));
}
int maxStr = 0, maxLen = 0, lenStr = 0;
temp.Clear();
temp.AddRange(map.Keys.Where(x => isRoot(x)));
foreach (var root in temp)
{
    workChain.Clear(); nextPiece(root, 0);
}
Console.WriteLine($"{maxStr} {lenStr}");

//helpers
bool isRoot(ValueTuple<int, int> node) { return node.Item1 == 0 || node.Item2 == 0; }

int chainSum(HashSet<(int, int)> curChain) // still faster than LINQ
{
    int sum = 0;
    foreach (var piece in curChain)
    {
        sum = sum + (piece.Item1 + piece.Item2);
    }
    return sum; }

int stackable(ValueTuple<int, int> cur, ValueTuple<int, int> tar, int p)
{
    if (commonPort(cur, tar) == p && cur.Item1 == cur.Item2 && cur.Item1 == p) { return p; }
    if ((cur.Item1 == tar.Item1 || cur.Item1 == tar.Item2) && cur.Item1 != p) { return cur.Item1; }
    if ((cur.Item2 == tar.Item1 || cur.Item2 == tar.Item2) && cur.Item2 != p) { return cur.Item2; }
    return -1;
}

int commonPort(ValueTuple<int, int> current, ValueTuple<int, int> target)
{
    if (current.Item1 == target.Item1 || current.Item1 == target.Item2) { return current.Item1; }
    else if (current.Item2 == target.Item1 || current.Item2 == target.Item2) { return current.Item2; }
    else { return -1; }
}

ValueTuple<int, int> nextPiece(ValueTuple<int, int> selected, int p)
{
    var x = (-1, -1);
    workChain.Add(selected);
    foreach (var piece in map[selected])
    {
        if (!selected.Equals(piece) && stackable(selected, piece, p) != -1 && !isRoot(piece) && !workChain.Contains(piece))
        {
            x = nextPiece(piece, stackable(selected, piece, p));
            if (x.Equals((-1, -1)))
            {
                int str = chainSum(workChain), len = workChain.Count;
                maxStr = str > maxStr ? str : maxStr;
                if (len > maxLen)
                {
                    maxLen = len;
                    lenStr = str;
                }
                else if (len == maxLen && str > lenStr)
                {
                    lenStr = str;
                }
                workChain.Remove(piece);
            }
        }
    }
    return x;
}

List<(int, int)> nextStack(ValueTuple<int, int> selected)
{
    workChain.Clear();
    for (int i = 0; i < temp.Count; i++)
        if (!selected.Equals(temp[i]) && commonPort(selected, temp[i]) != -1 && !isRoot(temp[i]))
            workChain.Add(temp[i]);
    return new List<(int, int)>(workChain);
}

I hate it, it is ugly as hell and I feel like there should be something simpler and more elegant without explicit/direct recursion. I feel like Visitor or Composite could be a better solution to this, although I heard Python users used iterative generators.

Any ideas?

\$\endgroup\$
5
\$\begingroup\$

Readability

I'll focus this review around this statement:

I hate it, it is ugly as hell and I feel like there should be more simpler and elegant ..

You then suggest some object-oriented (visitor, composite) and functional (generator) patterns as ways to improve readability. I would indeed make the code adhere more to OO principles.


Separation of Concerns

The first phase of refactoring the functional code is to define the concerns. You have: (1) Input Parsing (2) Calculator (3) Output Rendering. Ensure you split these concerns, by either providing separate classes, but definately separate methods, each focusing on their concern.


Object-Oriented Design

You have chosen Dictionary<(int, int), List<(int, int)>> as your state for the calculator. ValueTuple instances are great replacements for boiler-plate classes that group certain properties together. However, when you need re-occuring behavior, they are not the best choice. Have a look at some convoluted statements:

snippet 1:

if (commonPort(cur, tar) == p && cur.Item1 == cur.Item2 && cur.Item1 == p) { return p; }
if ((cur.Item1 == tar.Item1 || cur.Item1 == tar.Item2) && cur.Item1 != p) { return cur.Item1; }
if ((cur.Item2 == tar.Item1 || cur.Item2 == tar.Item2) && cur.Item2 != p) { return cur.Item2; }
return -1;

snippet 2:

if (current.Item1 == target.Item1 || current.Item1 == target.Item2) { return current.Item1; }
else if (current.Item2 == target.Item1 || current.Item2 == target.Item2) { return current.Item2; }
else { return -1; }

These are a direct consequence of not having provided custom classes. The (int, int) tuple you are using everywhere represents a Component in the puzzle. Let's make a class for it.

class Component : IEnumerable<int>
{
    public int Port1 { get; }
    public int Port2 { get; }

    public Component(int port1, int port2) => (Port1, Port2) = (port1, port2);

    // methods ..

    public IEnumerator<int> GetEnumerator()
    { 
        yield return Port1;
        yield return Port2;
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
}

Getting the common port can then be a method in this class.

public int? GetCommonPort(Component other) => this.Intersect(other).FirstOrDefault();

You may even decide to make a class Port to store some additional information which may be useful for linking components together. Only a disconnected port can get connected to a disconnected port of another component. This information is required to decide which components and which of their ports can connect.

class Port
{
    public int PortNumber { get; }
    public bool IsConnected { get; internal set; }

    public Port(int portNumber) => PortNumber = portNumber;
}

Another class I could imagine is Bridge, as it's a chain of components.

class Bridge
{
    Component First { get; private set; }
    Component Last { get; private set; }

    public void Construct(Component next)
    {
        Last.Connect(next);
        Last = next;
    }

    // and so on ..
}

This should give you a good idea how to rewrite the algorithm using an object-oriented approach. Have a go at it..

\$\endgroup\$
  • 1
    \$\begingroup\$ Perhaps we should rename the site from code review to home work review. Nice solution though \$\endgroup\$ – PPann Sep 5 at 6:29
  • 1
    \$\begingroup\$ @PPann we have the homework for it ;-] \$\endgroup\$ – t3chb0t Sep 5 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.