DEV Community

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

Posted on

2 1

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.

Sentry blog image

How I fixed 20 seconds of lag for every user in just 20 minutes.

Our AI agent was running 10-20 seconds slower than it should, impacting both our own developers and our early adopters. See how I used Sentry Profiling to fix it in record time.

Read more

Top comments (0)

nextjs tutorial video

Youtube Tutorial Series 📺

So you built a Next.js app, but you need a clear view of the entire operation flow to be able to identify performance bottlenecks before you launch. But how do you get started? Get the essentials on tracing for Next.js from @nikolovlazar in this video series 👀

Watch the Youtube series

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay