LAN Party

Advent of Code 2024 Day 23

Part 1

An exercise in triangle classification

It seems the challenge is to find every instance where three computers are connected via two shared edges each:

 A
 |\
 | \
 |  \
 B---C

So, a triangle! In this case, the edges are:

A-B
B-C
C-A

For something that simple, how could I write an algorthm that knows those three edges comprise a triangle?

Walking through a possible algorithm

First line:

A-B

A connects to B, and vice versa:

{
    'A': ['B'],
    'B': ['A']
}

Second line:

B-C

B connects to C, and vice versa:

{
    'A': ['B'],
    'B': ['A', 'C'],
    'C': ['B']
}

Third line:

C-A

C connects to A, and vice versa:

{
    'A': ['B', 'C'],
    'B': ['A', 'C'],
    'C': ['B', 'A']
}

How would an algorithm know it has a triangle?

• Three keys where each key contains both of the other two

Although, I know that with A: B I have B: A.

I just need to determine whether C has C: B and C: A.

Well, really just C: B.

Wow, this may be real simple:

• A has B and C
• That's two edges
• I just need to confirm the remaining edge
• Does C have B?
• If so, triangle!

Maybe this is my algorithm:

For each key, A
  For each connected key, B
    For each remaining key, Y
      If the remaining key connects to B
        Triangle!

It's a ton of loops, which isn't great.

But at least I only perform one look-up.

And for this first part, I only have to run these loops on the nodes with a t in them.

So, hopefully, this runs fairly quickly, even on an input with a list of a few thousand connections.

Time to write the actual algorithm.

Writing actual code

I wrote the dictionary-building portion all at once instead of in pieces.

Here's the full statement:

let nodes = input.split('\n').reduce((obj, node) => {
    let PCs = node.split('-')
    PCs.forEach((pc, i) => {
        if (!(pc in obj)) {
            obj[pc] = []
        }
        obj[pc].push(PCs[1 - i])
    })
    return obj
}, {})

The code explained:

• Use reduce to build an object
• Iterate through each line of input
• Split each line at the - character to get both computers
• Create a key if it doesn't already exist
• Add the other computer to the list of connections

Thankfully, when run on the example input, I see my expected output:

{
  kh: [ 'tc', 'qp', 'ub', 'ta' ],
  tc: [ 'kh', 'wh', 'td', 'co' ],
  qp: [ 'kh', 'ub', 'td', 'wh' ],
  de: [ 'cg', 'co', 'ta', 'ka' ],
  cg: [ 'de', 'tb', 'yn', 'aq' ],
  ka: [ 'co', 'tb', 'ta', 'de' ],
  co: [ 'ka', 'ta', 'de', 'tc' ],
  yn: [ 'aq', 'cg', 'wh', 'td' ],
  aq: [ 'yn', 'vc', 'cg', 'wq' ],
  ub: [ 'qp', 'kh', 'wq', 'vc' ],
  tb: [ 'cg', 'ka', 'wq', 'vc' ],
  vc: [ 'aq', 'ub', 'wq', 'tb' ],
  wh: [ 'tc', 'td', 'yn', 'qp' ],
  ta: [ 'co', 'ka', 'de', 'kh' ],
  td: [ 'tc', 'wh', 'qp', 'yn' ],
  wq: [ 'tb', 'ub', 'aq', 'vc' ]
}

Next, I only want to search for triangles among the t-containing computer names:

let tNames = Object.keys(nodes).filter(el => el.indexOf('t') !== -1)

Thankfully, that correctly flags the example input's four target computers:

[ 'tc', 'tb', 'ta', 'td' ]

Next, I want to iterate through each of these target computers' connection lists to find triangles:

let triangles = tNames.reduce((sets, pc) => {
    for (let a = 0; a < nodes[pc].length - 1; a++) {
        for (let b = 1; b < nodes[pc].length; b++) {
            if (nodes[nodes[pc][b]].includes(nodes[pc][a])) {
                sets.push([pc, nodes[pc][a], nodes[pc][b]])
            }
        }
    }
    return sets
}, [])

This took a bit of debugging on account of me messing up all the array accessor syntax.

But I eventually got it working as expected, and generated this output list:

[
  [ 'tc', 'wh', 'td' ],
  [ 'tc', 'td', 'wh' ],
  [ 'tb', 'wq', 'vc' ],
  [ 'ta', 'co', 'ka' ],
  [ 'ta', 'co', 'de' ],
  [ 'ta', 'ka', 'de' ],
  [ 'ta', 'de', 'ka' ],
  [ 'td', 'tc', 'wh' ],
  [ 'td', 'wh', 'qp' ],
  [ 'td', 'wh', 'yn' ],
  [ 'td', 'qp', 'wh' ]
]

Can you spot the issue with this list?

Spoiler: it contains duplicates.

How can I resolve that?

• I can sort the list alphabetically
• And use a Set() instead of an array
• That way it only adds unique values

Let's try!

if (nodes[nodes[pc][b]].includes(nodes[pc][a])) {
    set.add([pc, nodes[pc][a], nodes[pc][b]].sort().join(','))
}

That did the trick! Now my output is the correct items and length:

{
  'tc,td,wh',
  'tb,vc,wq',
  'co,ka,ta',
  'co,de,ta',
  'de,ka,ta',
  'qp,td,wh',
  'td,wh,yn'
}

Is my algorthm ready to take on my puzzle input?

Only one way to find out.

Running my algorithm on my puzzle input

Fingers crossed this works!

...

Oops, one small but major mistake:

• My algorithm targets computers with a t anywhere in their name
• But I need to target computers that start with a t

Small fix:

let tNames = Object.keys(nodes).filter(el => el.indexOf('t') == 0)

Running again...

...

The results in my output look more promising.

And my count is just under half of the input list.

This could be a winning number.

It's worth a failed submission attempt to see if it's the correct answer.

...

It is the correct answer!

Woohoo!!!

I'm so glad I was able to solve this part with a simple and performant algorithm.

Now, what wrench could Part 2 throw my way?

Part 2

Surprse, surprise

Find the largest interconnect network of computers.

Not a huge twist.

But certainly a huge task.

For me, at least.

I don't know how I would attempt to solve this besides brute force.

And that makes me feel the urge to just skip it.

Take my one well-earned gold star and move along.

That's what I'm gonna do.

Fun Part 1, though!