DEV Community

Cover image for Perfectly Spherical Houses in a Vacuum
Robert Mion
Robert Mion

Posted on

Perfectly Spherical Houses in a Vacuum

Advent of Code 2015 Day 3

Part 1

  1. One last quad-directional puzzle
  2. I think I'm all Set()

One last quad-directional puzzle

  • Input is a string of characters, each denoting one of the four directions: N, E, S, W
  • Each move represents a location along an X and Y axis
  • Several moves are likely to cross a previously-visited location
  • I need to know the number of unique locations visited

I think I'm all Set()

  • I use a Set() to accumulate unique X|Y locations visited
  • After each move, I update the location and attempt to add it to the set
  • Lastly, I check the number of items in the Set()

My algorithm in JavaScript:

let directions = { '^': [-1,0], '>': [0,1], 'v': [1,0], '<': [0,-1] }
let houses = new Set()
let location = [0,0]
houses.add(location.join('|'))
input.forEach(char => {
  location = [
    location[0] + directions[char][0],
    location[1] + directions[char][1],
  ]
  houses.add(location.join('|'))
})
return houses.size
Enter fullscreen mode Exit fullscreen mode

It generated the correct answer!

Part 1, a year ago

This was my full working algorithm in JavaScript when I initially solved this puzzle:

let houses = { '0,0': 1 }
let x = 0, y = 0

input.split("").forEach(dir => {
  if (dir == "^") {
    y -= 1
  } else if (dir == ">") {
    x += 1
  } else if (dir == "v") {
    y += 1
  } else if (dir == "<") {
    x -= 1
  }
  if (!houses.hasOwnProperty(`${x},${y}`)) {
    houses[`${x},${y}`] = 0
  }
  houses[`${x},${y}`] += 1;
})

return Object.values(houses).length
Enter fullscreen mode Exit fullscreen mode
  • I was unaware of Set()s
  • I wasn't savvy enough to encapsulate the relative coordinate changes in a dictionary
  • So I had to use an object to store each visited coordinate and some control flow to update the location

My, how far I've come!

Part 2

modulo makes this easy

  • Every other character is now one or the other pilot's instruction
  • So, even characters are for one, and odd characters are for the other

Using modulo, even numbers are:

Number % 2 == 0
Enter fullscreen mode Exit fullscreen mode

Odd numbers are:

Number % 2 == 1
Enter fullscreen mode Exit fullscreen mode

Thus:

  • I'll use a two-element array, [0,1]
  • Filter the directions to only include numbers whose index is even or odd
  • Then process the resulting half-sized list, starting from [0,0], using the same Set()

My algorithm in JavaScript:

let directions = { '^': [-1,0], '>': [0,1], 'v': [1,0], '<': [0,-1] }
let houses = new Set()
let paths = [0,1]
paths.forEach(i => {
  let location = [0,0]
  houses.add(location.join('|'))
  input
    .filter((_, index) => index % 2 == i)
    .forEach(char => {
      location = [
        location[0] + directions[char][0],
        location[1] + directions[char][1],
      ]
      houses.add(location.join('|')
    )
  })
})
return houses.size
Enter fullscreen mode Exit fullscreen mode

It generated the correct answer!

Part 2, a year ago

This was my full working algorithm in JavaScript when I initially solved this puzzle:

let houses = { '0,0': 2 }
let x1 = 0, y1 = 0, x2 = 0, y2 = 0;

input.split("").forEach((dir, idx) => {
  if (idx % 2 == 1) {
    if (dir == "^") {
      y2 -= 1
    } else if (dir == ">") {
      x2 += 1
    } else if (dir == "v") {
      y2 += 1
    } else if (dir == "<") {
      x2 -= 1
    }
    if (!houses.hasOwnProperty(`${x2},${y2}`)) {
      houses[`${x2},${y2}`] = 0
    }
    houses[`${x2},${y2}`] += 1;
  } else {
    if (dir == "^") {
      y1 -= 1
    } else if (dir == ">") {
      x1 += 1
    } else if (dir == "v") {
      y1 += 1
    } else if (dir == "<") {
      x1 -= 1
    }
    if (!houses.hasOwnProperty(`${x1},${y1}`)) {
      houses[`${x1},${y1}`] = 0
    }
    houses[`${x1},${y1}`] += 1;
  }
})
return Object.values(houses).length
Enter fullscreen mode Exit fullscreen mode
  • Good news: I was savvy enough to use modulo!
  • But not savvy enough to leverage a two-element array and forEach() to make the code much less redundant

Proof of skills gained, knowledge gathered, and algorithmic growth!

I did it!!

  • I solved both parts!
  • Using more eloquent code than initially used!

Few things fell as rewarding as looking back and seeing what now feels like amateurish code.

Top comments (0)