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.

SurveyJS custom survey software

Build Your Own Forms without Manual Coding

SurveyJS UI libraries let you build a JSON-based form management system that integrates with any backend, giving you full control over your data with no user limits. Includes support for custom question types, skip logic, an integrated CSS editor, PDF export, real-time analytics, and more.

Learn more

Top comments (0)

👋 Kindness is contagious

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

Okay