DEV Community

Cover image for Crossed Wires
Robert Mion
Robert Mion

Posted on

Crossed Wires

#adventofcode #algorithms #javascript #programming

Advent of Code 2024 Day 24

Part 1

Hurry up and wait...and see

This feels like a queue-themed challenge:

  • Establish values
  • Generate an inventory of processable steps
  • Execute steps
  • Repeat until inventory is complete

I'm concerned there's something in the rules that I may miss or not fully understand.

Hopefully stepping through the first example will be enough to gain confidence to write an algorithm.

Understanding how to architect the example input

Here it is again:

x00: 1
x01: 1
x02: 1
y00: 0
y01: 1
y02: 0

x00 AND y00 -> z00
x01 XOR y01 -> z01
x02 OR y02 -> z02
Enter fullscreen mode Exit fullscreen mode

I can imagine a dictionary to store the initial values:

{
  x00: 1,
  x01: 1,
  x02: 1,
  y00: 0,
  y01: 1,
  y02: 0
}
Enter fullscreen mode Exit fullscreen mode

Then each gate needs some id other than its type, but needs to store it's type, inputs and output.

Hmmm...

[
  {
    'type': 'AND',
    'inputs': ['x00', 'y00'],
    'output': 'z00',
    'done': false
  },
  {
    'type': 'XOR',
    'inputs': ['x01', 'y01'],
    'output': 'z01',
    'done': false
  },
  {
    'type': 'OR',
    'inputs': ['x02', 'y02'],
    'output': 'z02',
    'done': false
  }
]
Enter fullscreen mode Exit fullscreen mode

That might work. It at least seems to have all pertinent information about a gate, and the index serves as a unique id.

Oh, and I will need to store and know the values of all output gates that didn't get initial values:

{
  x00: 1,
  x01: 1,
  x02: 1,
  y00: 0,
  y01: 1,
  y02: 0,
  z00: null,
  z01: null,
  z02: null
}
Enter fullscreen mode Exit fullscreen mode

Understanding how to process the example input's gates

If I think of this task as repeatedly checking the entire list of gates for only the ones whose inputs have values:

For each gate
  If both inputs have values
    Add to the list
Enter fullscreen mode Exit fullscreen mode

Out of the three, all gates' inputs have values.

So, the list will have all gates:

[0, 1, 2]
Enter fullscreen mode Exit fullscreen mode

I can iterate through each, process the inputs, save the value in the output, and mark them as done.

  • z00 gets 0 because 1 AND 0 is 0
  • z01 gets 0 because 1 XOR 1 is 0
  • z02 gets 1 because 1 OR 0 is 1

I think I understand.

I hope I understand.

I'm ready to code.

Turning puzzle input into a state machine

I plan to generate a dictionary and an array of dictionaries.

First, the dictionary of given initial values:

let [values, gates] = input.split('\n\n')
values = values.split('\n').reduce((obj, item) => {
    let [name, value] = item.split(': ')
    obj[name] = +value
    return obj
}, {})
Enter fullscreen mode Exit fullscreen mode

As expected, I see this as output:

{ x00: 1, x01: 1, x02: 1, y00: 0, y01: 1, y02: 0 }
Enter fullscreen mode Exit fullscreen mode

Next, the list of dictionaries filled with each gate's parameters:

gates = gates.split('\n').reduce((list, gate) => {
    let [input1, bool, input2, , output] = gate.split(' ')
    if (!(output in values)) {
        values[output] = null
    }
    list.push({
        'type': bool,
        'inputs': [input1, input2],
        'output': output,
        'done': false
    })
    return list
}, [])
Enter fullscreen mode Exit fullscreen mode

This creates the list of objects and updates the list of values to include the uninitialized values - most or all starting with z.

And I see the expected output:

[
  { type: 'AND', inputs: [ 'x00', 'y00' ], output: 'z00', done: false },
  { type: 'XOR', inputs: [ 'x01', 'y01' ], output: 'z01', done: false },
  { type: 'OR', inputs: [ 'x02', 'y02' ], output: 'z02', done: false }
]
Enter fullscreen mode Exit fullscreen mode

Next, I need to make functions for each of the three booleans:

function AND (a, b) {
    if (a == 1 && b == 1) {
        return 1
    } else if (a == 0 || b == 0) {
        return 0
    }
}
function OR (a, b) {
    if (a == 1 || b == 1) {
        return 1
    } else if (a == 0 && b == 0) {
        return 0
    }
}
function XOR (a, b) {
    if (a !== b) {
        return 1
    } else if (a == b) {
        return 0
    }
}
Enter fullscreen mode Exit fullscreen mode

Pretty straightforward, though maybe not concise. Still, very readable!

Time to start putting this all together with a loop and a queue.

The harder part: processing each set of ready gates

A gate only processes its inputs when both have a value.

The way it seems, only a few gates will have values at first. Then, as more outputs get values, more gates will become ready to process.

I need to write an algorithm that filters the full list for:

  • gates that are not done as per my object's property
  • gates whose inputs both have a non-null value

Then processes each gate's boolean and sets the output's value.

Seems straightforward.

Here I go!

let gatesRemaining = gates.length
while (gatesRemaining > 0) {
    gates.forEach(
      gate => {
        if (!gate.done) {
            if (
                 typeof values[gate.inputs[0]] == 'number' && 
                 typeof values[gate.inputs[1]] == 'number') 
            {
                values[gate.output] = eval(
                   `${gate.type}(values['${gate.inputs[0]}'],
                                 values['${gate.inputs[1]}'])`
                )
                gate.done = true
                gatesRemaining--
            }
        }
      }
    )
}
Enter fullscreen mode Exit fullscreen mode

The eval is a bit gross, but it does the job of calling the correct boolean function with the two inputs.

After a bit of debugging my sloppy array accessor syntax, I see the expected result:

  • values being added correctly
  • a counter decrementing correctly
  • a program ending thanks to a counter reaching 0

Time to check on the larger example input.

It works!

Piecing together the decimal

At least for the examples, I have the right keys with the right values.

Now I need to extract just the z-starting keys, put them in order with the values, and join the values to get the decimal.

This may be the toughest part!

Well, not toughest, but definitely a long statement:

let decimal = parseInt(
  Object.keys(values).filter(
    el => el[0].indexOf('z') == 0
  ).sort().reverse().map(el => values[el]).join(''), 
  2
)
Enter fullscreen mode Exit fullscreen mode
  • Make a list of the key names in my dictionary of values
  • Keep only the ones starting with z
  • Sort them alphabetically
  • Reverse their order
  • Replace each one with that key's associated value
  • Join them all into a string of 1s and 0s
  • Convert that binary string into a decimal

It works!

I see 2024 in my output!

Now, do I think it will work on my puzzle input?

Fingers are tightly crossed.

Although I'm fully expecting it to never terminate or generate an error for something I overlooked.

Time to find out...

Running my algorithm on my puzzle input

...

Wow! It ran and finished instantly!

And it output a big 'ol number!

And it was the correct answer!

Woohoo!!!

I'm so proud of myself for earning these gold stars on days above 20.

Ok, time to see what Part 2 demands.

Part 2

Confusion and intimidation

There's a lot more explanation here.

A lot about binary numbers.

And swapping.

And...more.

I'm confused.

And knowing how large my puzzle input is, I'm fully intimidated to even attempt understanding and coding anything.

So, I sadly bid today farewell without attempting Part 2.

It's a bummer, but my head hurts just reading each short paragraph in this additional explanation.

One gold star earned. Good riddance, Day 24.

Top comments (0)