DEV Community: Gal Elmalah

Ready, Set, Go! My Goals for a Productive and Fulfilling 2023

Gal Elmalah — Sat, 31 Dec 2022 12:34:52 +0000

As the new year approaches, it's natural to think about our goals and aspirations for the coming year.

In this blog post, I've outlined a selection of personal goals that I hope to achieve in 2023. These goals are organized into categories, including Programming & Management, Personal Development and Personal Interests. By breaking down my goals into smaller, more obtainable pieces of work, I hope to stay focused and make progress towards things that will positively impact my life. Whether it's solving programming questions, diving deeper into Go, or writing more blog posts, I'm excited to take on the challenges of the new year and see where they lead me.

Making the Cut

Like every year, there are many things that I want to accomplish. However, I have limited time and energy, so it's important for me to focus on goals that will have the most impact on my life. To help me do this, I ask myself two questions:

What impact will achieving this goal have on my life? Will it make me happier or help me learn something new?
Can I break this goal down into smaller, more achievable pieces of work? Do I need to complete the entire goal at once, or can I make progress through smaller steps?

By answering these questions and categorizing my goals, I can stay focused and make progress towards things that are meaningful to me.

Programming & Managing

Solve 100+ Questions from CSES Problem Set

Impact

Overall it will make me a better coder and help me gain a deeper understanding of topics I want to know better like dynamic programming, data structures that support range queries and the list goes on and on.

Easier time during Advent of Code 2023.

To be honest, I just enjoy solving these questions...

Breakdown

I can start solving specific sections at first, for example, start by solving all the questions from the dynamic programming section

Dive deeper into Go

I started learning go while doing Advent of Code.

I enjoyed the language and I'll dive deeper into its main features. I also have a couple of side projects and blog posts in mind.

Impact

Add another valuable tool to my programming toolkit
Stay current with a language that is widely used in the tech industry
Enhance my understanding of Go's main features and capabilities
Use Go to build useful and fun side projects

Breakdown

Solve programming questions
Create a simple HTTP server using Go built-in libraries
Create a GRPC service
Implement parallel algorithms
Final project should be something useful and fun.

(1) and (4) can be done in whatever order I choose.

Interpreters & Compilers

I was always intrigued by interpreters and compilers BUT I have never written one or the other.

I'm planning to change that by following these two awesome books, Writing An Interpreter In Go and Writing A Compiler In Go.

As you can see this goal and the "Dive deeper into Go" really complement each other and in fact, one of the main reasons I started the "Learning go series" was to have an easier time following the above books

Impact

I guess I just want to do it, but there are some rational thoughts behind this decision as well:

Better understanding of how things work
Through learning these processes I will become a better programmer
It will complement some side projects that I had in mind for a year or more

I believe that achieving this goal will help me grow as a programmer and increase my professional value.

Breakdown

Finish the interpreter's book
Write a JSON parser based on the concepts learned
Write an interpreter for an RTL programming language
Finish the compilers book [Risk]

Reading the compilers book is not a must for me and can wait for 2024. In case ill have a really good time I will probably try and read that one during the year as well.

Project & Team Management

As a lead for a team of developers working in a complex domain, I want to deepen my understanding of how to create optimal settings for team growth and project management and most apply that knowledge

Impact

This goal is important to me because I believe that effective teams and project management is critical to the success of any project or organization. By learning more about these topics, I can contribute to the success of my team, organization and obviously myself.

Breakdown

Compile a list of books about team & project management
Choose at least 1 from each category
Write about them in my blog :)

Personal Development

Write 50+ Blog Posts

Why? Well, I want to improve that skill and you know what they say, practice makes perf...progress!

Impact

Better writing skills
Gain a deeper understanding of the topic I'm writing about
Social presence and better "branding" for myself

Breakdown

Not much to break here, but let's try anyway.

I can start by creating a series of posts about interesting topics from the CSES Problem set, for example:

Dynamic programming
Graph algorithms
Range queries

These types of blog posts are pretty easy to write, assuming you understand the question.

There is also an added value in diving deeper into a solution/problem/approach.

Besides solving coding questions, I would also like to write about various topics like team management, project management, books I liked, and some random thoughts.

Public Speaking

Why? It scares the living shit out of me and I hate that it does.

Impact

Self-confidence
Better public speaking skills
Gain a deeper understanding of the topic I'm talking about
Social presence and better "branding" for myself

Breakdown

Start with presentations inside the company and move on to conferences.
Ideally, I will speak between 8 to 12 times throughout the year.

Personal Interests

Read 30+ Books

Well, I just love reading.
This list is not limited to any particular type of book.
You can follow me on Goodreads to check out my progress.

Impact

Pure joy! There aren't many things that make me smile like a good fantasy book
Learning

Breakdown

Read, read and read some more.

Morning Routine

Well...I sort of have a morning routine at the moment but I'm really bad at staying consistent, usually, I stick with it for a week or two then I allow myself to chill and end up waking up at 9 am without doing anything.
How does an ideal morning routine look in my books?

Wake up at 6:00 am or before
Brush my teeth, drink a glass of water and get myself a big cup of coffee
6:15 am, 25 minutes of workout and stretches
6:45 am, write whatever in my journal
7:10 am, go over the upcoming day
Take a shower and head to the office

Impact

Joy and fulfillment
Better organization of thoughts and preparation for the coming day
Health

Breakdown

Start with the hard part, waking up at 6:00 am or before and stick with it for at least two months, then make (3) mandatory and gradually add (4) and (5).

Hopefully, by April or May, this routine will feel effortless.

Run Forrest Run!

I love running but due to a back injury, I was not able to run for the last 4 months or so.
Things are finally starting to look better and I'm ready to get back on the horse (my two legs).

Impact

Running, for me at least, is hard at the begging when you are not in proper shape but after 2-3 weeks when it's not pure suffering it becomes so much fun and helps me clear my head.

Joy
Physical and mental health

Breakdown

Running 3 times a week.
Participate in a couple of races.

Tour du Mont Blanc

I wanted to go on this trip for a while now and I think 2023 will be the year I'll finally make it happen.
Ideally, set on this adventure with my wife & father, making this a really meaningful experience for me.

Impact

Joy
Physical and mental health
Quality time with my family

Breakdown

Just to do it!

Passive Income

Impact

Piece of mind
Feeling of accomplishment
Money money money

Breakdown

Create a list of potential channels for income like selling templates online, an online store that sells some products, writing, etc...
Asses each option's potential
Choose and follow through with 2 of the highest potential options

Organizing my Finance

If I'm being honest with myself, my finance is a mess!
I need to create a clear picture regarding my current assets and investments, assess if I'm maximizing my money potential, and act accordingly.

Impact

Piece of mind
Organization
Money money money

Breakdown

Create a list of my assets and investments
Compare them to other types of investments in a 5 years window
If needed make changes to my portfolio and buy or sell assets
Start working towards future investments

So, there you have it: my goals for 2023! I'm excited to see where this new year takes me, and I hope that by setting some clear and achievable goals, I can make the most of it. I'm ready to take on whatever challenges come my way, and I can't wait to see what I'll achieve by the end of the year. Here's to a fantastic 2023!

Got any 2023 goals yourself? Share them with everyone in the comments section!

You can check out some of my other posts on my personal blog.

AoC Day 12 - Hill Climbing Algorithm

Gal Elmalah — Sat, 17 Dec 2022 13:54:42 +0000

Question

We are stuck at a river between two mountains, our communication device can't get a decent signal but don't worry
THIS IS FINE!! we can get through this if we only find a high enough place to get a signal out

cool cool cool, no doubt no doubt no doubt stay optimistic, and don't panic!!!

The one thing going for us at the moment is that we have a height map from our device, we just need to get to the heighst point and send a distress signal

Our map looks like this

Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi

Our current location is marked as S and our destination is marked as E
We are also told that the height of each location is the ASCII value of each letter
The value of S = a and E = z

This smells like a graph problem...

Parsing

We could have used the structure of the input as is but I wanted to make it a bit more meaningful so we will parse it into a matrix of points!
First, we will create a new Point struct

type Point struct {
  i, j, v int
}

func (p *Point) id() string {
  return fmt.Sprintf("(%d,%d)", p.i, p.j)
}

func newPoint(i, j, v int) *Point {
  return &Point{i: i, j: j, v: v}
}

Each point location is kept with i and j, and the value is stored in v.
We also create a struct method, id that we will probably need some time down the line

Although I'm by no means a go expert, having a new function for a struct seems like the standard. Probably because it's a lot less verbose.

Now let's change our input matrix into a matrix of Points

func createPoint(i, j int, r rune) *Point {
  switch r {
  case 'S':
    return newPoint(i, j, 0)
  case 'E':
    return newPoint(i, j, int('z')-int('a'))
  default:
    return newPoint(i, j, int(r)-int('a'))
  }
}

func parse(raw string) (matrix [][]*Point, start *Point, dest *Point) {
  lines := strings.Split(string(raw), "\n")
  matrix = make([][]*Point, len(lines))
  for i := range matrix {
    matrix[i] = make([]*Point, len(lines[0]))
    rows := []*Point{}
    for j, c := range lines[i] {
      if c == 'S' {
        start = createPoint(i, j, c)
      }
      if c == 'E' {
        dest = createPoint(i, j, c)
      }
      rows = append(rows, createPoint(i, j, c))
    }
    matrix[i] = rows
  }

  return matrix, start, dest
}

The first thing we do is to split our input on each \n this will give us an array of lines AKA rows.
We will split each of these "rows" to get each "cell" in our input
For each cell, we will create a new point and push it into the current row
eventually we will end up with a matrix of points

Part 1

We are asked to get from S to E with the least amount of steps.
Ohh and to make sure we won't get too tired along the way we can only travel from p1 to p2 if the value in p2 is at most one higher than the value in p1.

Reading the first line, "with the least amount of step" this is a dead giveaway that we can and should use BFS

Since we need a Queue to easily implement BFS and Go doesn't have anything built-in, we will need to create our Queue first
Create a new package named, well, queue and add the following logic and struct

package queue

import "fmt"

type Queue[T comparable] struct {
  items []T
}

// Enqueue - Adds an item T to the Q
func (q *Queue[T]) Enqueue(item T) {
  q.items = append(q.items, item)
}

// Dequeue - Removes an element from the Q - FIFO
func (q *Queue[T]) Dequeue() T {
  if q.IsEmpty() {
    fmt.Println("Trying to Dequeue from an empty Queue")
  }
  firstItem := q.items[0]
  q.items = q.items[1:]
  return firstItem
}

func (q *Queue[T]) Peek() T {
  return q.items[0]
}

func (q *Queue[T]) NumberOfItems() int {
  return len(q.items)
}

func (q *Queue[T]) IsEmpty() bool {
  return len(q.items) == 0
}

There is nothing fancy here, just your regular Q...
Armed with our new Queue we can start implementing BFS
The gist of BFS is

Start from node X and push all its neighbors to the "processing" Queue
To avoid duplicates in that Queue we will also maintain a Set of "seen" nodes, for that we will use our simple set from day 6
The last thing we need is to keep track of how we got to each node, this means for point p1 who got it inside the Queue that is the currently processed point. Let's look at some code

func BFS(graph [][]*Point, s *Point, destination *Point) int {
  // Creating a Queue
  Q := queue.Queue[*Point]{}
  // Adding the start node to the Queue
  Q.Enqueue(s)
  // Keeping track of who got us into the Queue
  backTrack := map[string]string{}
  // Nodes we have seen
  seen := set.NewSimpleSet[string]()
  // Mark the starting node as seen to avoid pushing it into the Queue again
  seen.Add(s.id())
  // We keep going over the "graph" while there are nodes in the Queue
  for !Q.IsEmpty() {
    // The node we are currently processing
    currentNode := Q.Dequeue()
    if currentNode == destination {
      // Yay we got to our destination, we can stop searching
      break
    }

    // Get all valid neighbors from our current node
    // we will go over the implementation of getting neighbors in a minute or two
    neighbors := getNeighbors(graph, currentNode)

    for _, v := range neighbors {
      // For each neighbor, if we haven't seen it before, do the following
      // 1. mark it as seen
      // 2. mark the node that got to him i.e our currently processed node
      // 3. push it to the Queue
      if !seen.Has(v.id()) {
        seen.Add(v.id())
        backTrack[v.id()] = currentNode.id()
        Q.Enqueue(v)
      }
    }
  }
  // go over the route to the destination node and count the number of steps it took us
  return count(backTrack, destination.id())
}

// simple recursive function that uses the node id to jump from p1 to p2 where p2 is the node that got p1 into the Queue
func count(backTrack map[string]string, id string) int {
  v, ok := backTrack[id]
  if ok {
    return 1 + count(backTrack, v)
  }
  return 0
}

func getNeighbors(graph [][]*Point, sink *Point) (neighbors []*Point) {
  // moves represent our up, right, down, and left options
  moves := [][]int{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}
  for _, move := range moves {
    // add the current move to the origin point
    di, dj := move[0]+sink.i, move[1]+sink.j
    // if the new indexes are inbound of our matrix/graph
    if di >= 0 && di < len(graph) && dj >= 0 && dj < len(graph[0]) {
      delta := graph[di][dj].v - sink.v
      // We were also told in the question that we need to make sure we make moves of at most 1
      if delta <= 1 {
        neighbors = append(neighbors, graph[di][dj])
      }
    }
  }
  return neighbors
}

I tried making everything as clear as possible but if there is something you are struggling with, hit me up in the comment section

Our final solution looks like this

func Part1(raw string) int {
  graph, start, dest := parse(raw)
  steps := BFS(graph, start, dest)
  return steps
}

Part 2

Part 2 is where things gets interesting, we are now asked to find the shortest path to our destination point but we can use every a in our map as a starting position and S
We can take a naive approach here and see if it works, what's the naive approach you ask?
Find all starting nodes and from each of those run our BFS and keep track of the minimum value
This also means that we need to change our parsing function to collect all starting points

// start is now an array of points
func parse2(raw string) (matrix [][]*Point, start []*Point, dest *Point) {
  lines := strings.Split(string(raw), "\n")
  matrix = make([][]*Point, len(lines))
  for i := range matrix {
    matrix[i] = make([]*Point, len(lines[0]))
    rows := []*Point{}
    for j, c := range lines[i] {
      if c == 'S' || c == 'a' {
        start = append(start, createPoint(i, j, c))
      }
      if c == 'E' {
        dest = createPoint(i, j, c)
      }
      rows = append(rows, createPoint(i, j, c))
    }
    matrix[i] = rows
  }

  return matrix, start, dest
}

And our solution for part 2 will look like this

func getMinValue(arr []int) (m int) {
  for i, e := range arr {
    if i == 0 || e < m && e != 0 {
      m = e
    }
  }
  return md
}

func Part2NaiveApproach(raw string) int {
  graph, start, dest := parse2(raw)
  steps := []int{}
  for _, s := range start {
    res := BFS(graph, s, dest)
    if res > 0 {
      steps = append(steps, res)
    }
  }

  return getMinValue(steps)
}

This works for the question input which surprised me but it takes about 3 seconds to complete, we can do better!

There's one thing that comes to mind, why do we need to do a BFS from each node, can't we just add all those starting nodes to our Queue as starting nodes?
Well, we can! its called multi-source BFS,
I happen to know this approach from solving the monster question on CSES, give it a try.

Before we start tweaking things and trying new approaches, let's write some benchmarks so we can make sure what we are doing have an impact.

func BenchmarkPart1(b *testing.B) {
  input := util.ReadFile("./input.txt")

  for n := 0; n < b.N; n++ {
    Part1(input)
  }
}

func BenchmarkPart2NaiveApproach(b *testing.B) {
  input := util.ReadFile("./input.txt")

  for n := 0; n < b.N; n++ {
    Part2NaiveApproach(input)
  }
}

Run go test bench=. -count 2

BenchmarkPart1-8                             183           7225891 ns/op
BenchmarkPart1-8                             182           7127653 ns/op
BenchmarkPart2NaiveApproach-8                  1        1530454249 ns/op
BenchmarkPart2NaiveApproach-8                  1        1476970916 ns/op

ophh... our naive approach is slow. it only run ones and took 1530454249ns which is roughly 1.53 seconds
compared to our part 1 results, this is just awful!

Our Multi-Source BFS approach is similar to our original BFS but there are changes in the first couple of lines

// s is now an array of starting points
func MultiSourceBFS(graph [][]*Point, s []*Point, destination *Point) int {
  Q := queue.Queue[*Point]{}
  seen := set.NewSimpleSet[string]()
  // for each starting point push int into the Queue and mark it as seen
  for _, v := range s {
    Q.Enqueue(v)
    seen.Add(v.id())
  }
  ...
  ...

See the complete code here

Let's write a benchmark for our Multi-Source BFS approach

func BenchmarkPart2MultiSourceBfs(b *testing.B) {
  input := util.ReadFile("./input.txt")
  // run the Fib function b.N times
  for n := 0; n < b.N; n++ {
    Part2MultiSourceBfs(input)
  }
}

Wow, what a difference! Our Multi-source BFS run ~205 times and each run took only ~5841816ns which is roughly 0.0058 seconds!
That's about 274 times faster!

BenchmarkPart1-8                             184           7306437 ns/op
BenchmarkPart1-8                             181           6429481 ns/op
BenchmarkPart2NaiveApproach-8                  1        1475075477 ns/op
BenchmarkPart2NaiveApproach-8                  1        1450753723 ns/op
BenchmarkPart2MultiSourceBfs-8               205           5841816 ns/op
BenchmarkPart2MultiSourceBfs-8               204           5818908 ns/op

So we had a fun graph problem and we have seen a few approaches to solve it, what a fun day!
hopefully, you learned something new from this day post.

As a final note I'll leave you all with a question, is there an even better way of doing what we just did?
Can we perhaps change our logic a bit and start from a different node and get our desired answer in an even more efficient way?
Let me know in the comments if you have any ideas :)

That's it for today, see you tomorrow ⭐️

You can find the complete code here
Thanks for reading!

AoC Day 11 - Math fun times

Gal Elmalah — Tue, 13 Dec 2022 20:17:00 +0000

I don't feel like I can eloquently explain this day solution, once AoC is done ill get back to this post and make sure its properly explained

AoC Day 10 - Cathode-Ray Tube

Gal Elmalah — Tue, 13 Dec 2022 20:14:52 +0000

Cathode-Ray Tube

Question

Crap seems like our rope physics knowledge from yesterday didn't help and we wound up in the river...
The elves are nowhere to be found and our communication system is spitting out weird signals and noise
Luckily we can probably get this device up and running in no time we just need to make a drop-in replacement for the device's video system.
To do that we need to decode the instructions from the CPU and the register value first

We are given the CPU output and told that each operation takes Y cycles to complete, for example:

noop
addx 3
addx -5

addx - takes two rounds, add the right-hand value to X
noop - take one round, does nothing

Parsing

First, Create a new Instruction struct

type Instruction struct {
  cycles int
  value  int
}

Compared to previous days the parsing here is a piece of cake

func parse(raw string) (instructions []*Instruction) {
  lines := strings.Split(string(raw), "\n")

  for _, l := range lines {
    if strings.Contains(l, "noop") {
      instructions = append(instructions, &Instruction{cycles: 1, value: 0})
    } else {
      parts := strings.Split(l, " ")
      instructions = append(instructions, &Instruction{cycles: 2, value: util.ParseInt(parts[1])})
    }
  }
  return
}

you might notice that our function signature is a bit weird, it ends with (instructions []Instruction) and we return nothing at the end of the function.
This syntax creates a variable at the top of our function, and the last return statement is called a "naked" return, which returns instructions by default.
In my opinion, it shouldn't be used for any function with more than a couple of lines of code, instead, we should use the named variable and return instructions but for the sake of learning new things we will stick with the "naked" return (I kind of like that terminology)

Part 1

We need to sample the value in register X*ticks in various CPU cycles, more precisly during the 20th, 60th, 100th, 140th, 180th, and 220th cycles and sum them up

There is no kind of gotchas in these sort of questions (usually), most simulation question just needs to be carefully read and then directly apply the instructions in the code

Directly from AoC
addx V takes two cycles to complete. After two cycles, the X register is increased by the value V. (V can be negative.
noop takes one cycle to complete. It has no other effect.

the thing to note here is that the instruction value takes effect only after the specific number of cycles has passed

So what does our solution needs to do?

Go over each instruction
Keep track of the system ticks (not the same as cycle)
Keep track of X
Sample X in each one of the intervals
Run each instruction Y number of cycles
Update X after each instruction

We are adding a notion of ticks, ticks happen on every run regardless of the number of cycles an instructions should take

func Part1(raw string) int {
  instructions := parse(raw)
  x := 1
  result := 0
  ticks := 0
  for _, ci := range instructions {
    for j := 0; j < ci.cycles; j++ {
      ticks++ // updating ticks on every cycle
      if ticks%20 == 0 && ticks%40 != 0 {
        result += x * ticks
      }
    }
    x += ci.value
  }

  return result
}

Part 2

using the value of X during each tick we need to draw some stuff to the screen
Our screen is 40 pixels wide and its height is 6 pixels

There is no notion of vertical positions, meaning that our x value needs to be translated to the range we defined above 40*6

We are told there is a sprite 3 pixels long and the x value determines her center position.
During each cycle we bump our location in the screen, if the current position includes the currently drawn pixel we say it lit and draw # otherwise its dark and we draw .

The output of this should be a sequence of chars and that will be our answer! How cool is that right?

This question is a bit trickier than part 1 but still, the main thing is to read the instructions carefully and translate them back into code

First, lets create a screen!

func printCrt(crt [][]string) {
  for i, r := range crt {
    fmt.Println(i, r)
  }
}

func makeCrt() [][]string {
  crt := make([][]string, 6)
  for i, _ := range crt {
    crt[i] = make([]string, 40)
  }
  return crt
}

Next comes our logic

func Part2(raw string) {
  instructions := parse(raw)
  crt := makeCrt()
  x := 1
  ticks := 0
  for _, ci := range instructions {
    for j := 0; j < ci.cycles; j++ {
      row := int(ticks / 40)
      col := ticks % 40
      d := util.Abs(col - x)
      if d < 2 {
        crt[row][col] = "#"
      } else {
        crt[row][col] = "."
      }
      ticks++
    }
    x += ci.value
  }

  print(crt)
}

Not everything here is obvious so let's go over the tricky lines one by one:

row := int(ticks / 40)
we know that each row is 40 long, so we can divide the number ticks by the width of each row to determine in each row we should be relative to our CRT e.g 30/40 -> 0, 90/40 -> 2 etc..

col := ticks%40
we have a "window" with a length of 40 and a value that is increasing but we still want to fall into that bucker of values e.g 30%40 -> 30, 50%40 -> 10 (second row 10th pixel), 220%40 -> 20 etc...

d := util.Abs(col - x)
our delta from the center of the sprite, if its smaller than 2 (remember that x is the center of the sprite) we draw a lit pixel, otherwise we draw a dark pixel

With my input I got the following output, what about you?

That's it for today, see you tomorrow ⭐️

You can find the complete code here
Thanks for reading!

AoC Day 9 - Rope Bridge

Gal Elmalah — Tue, 13 Dec 2022 06:07:12 +0000

Rope Bridge

Question AkA doing weird rope physics!

You come across an old rope bridge and you are not sure it can hold your fat a** so you decide to model some rope physics to distract yourself (like that's going to help...)

Directly from AoC
Consider a rope with a knot at each end; these knots mark the head and the tail of the rope. If the head moves far enough away from the tail, the tail is pulled toward the head.

We are given a series of moves to be done by the head, for example:

R 4
U 4
L 3
D 1
R 4
D 1
L 5
R 2

Parsing

Defining an Instruction struct, each instruction has a direction L,R,U,D and steps <number of steps to perform>
Iterating over our input we can map each line to our new instruction struct as follows

type Instruction struct {
  direction string
  steps     int
}

func parse(raw string) (instructions []Instruction) {
  lines := strings.Split(string(raw), "\n")
  for _, l := range lines {
    parts := strings.Split(l, " ")
    instructions = append(instructions, Instruction{direction: parts[0], steps: util.ParseInt(parts[1])})
  }
  return instructions
}

Part 1

We are asked to simulate the position of the tail after each instruction execution
We will treat both the head and tail as if they are starting from position 0,0

We know that the head should change its x or y value based on the current instruction direction.
Let's create a struct to represent a Point and expose a method move that mutates the point accordingly

type Point struct {
  x, y int
}

func (p *Point) move(direction string) {
  switch direction {
  case "L":
    p.x--
  case "R":
    p.x++
  case "U":
    p.y--
  case "D":
    p.y++
  }
}

func newPoint(x, y int) *Point {
  return &Point{x, y}
}

Now lets start writing our solution for part 1


instructions := parse(raw)
  head, tail := newPoint(0, 0), newPoint(0, 0)

  visited := set.NewSimpleSet[string]()
  for _, ci := range instructions {
    for i := 0; i < ci.steps; i++ {
      head.move(ci.direction)
      // we need to adjust the tail point according to the head location
    }

  }

  return visited.Size()
}

Next, adjust the tail point according to the head point

From the question description

Due to the aforementioned Planck lengths, the rope must be quite short; in fact, the head (H) and tail (T) must always be touching (diagonally adjacent and even overlapping both counts as touching):

As you can see, we need to "touch" the head at any point in time, or in other words, the distance between the points x and y cords is always less than 2

func (p *Point) adjust(leadingPoint *Point) {
  dx := util.Abs(leadingPoint.x - p.x)
  dy := util.Abs(leadingPoint.y - p.y)

  if dx >= 2 || dy >= 2 {
    if leadingPoint.x > p.x {
      p.x++
    } else if leadingPoint.x < p.x {
      p.x--
    }

    if leadingPoint.y > p.y {
      p.y++
    } else if leadingPoint.y < p.y {
      p.y--
    }
  }
}

Armed with our new point structure we can implement the actual logic for part 1
We will use our SimpleSet from day 6 to keep track of the number of points the tail visited
The size of that set will be the answer for this part

func Part1(raw string) int {
  instructions := parse(raw)
  head, tail := newPoint(0, 0), newPoint(0, 0)

  visited := set.NewSimpleSet[string]()
  for _, ci := range instructions {
    for i := 0; i < ci.steps; i++ {
      visited.Add(tail.id())
      head.move(ci.direction)
      tail.adjust(head)
    }

  }

  return visited.Size()
}

Part 2

Crap the rope just snaps and for some reason that does not make any sense we now have 10 knots to simulate... that's what happens when you combine elves and rope physics.

At first glance, this seems complicated but in reality, we just need to think about the new requirements as an array of points where points[j] is the tail of points[j+1] and for each move adjust all tail points according to their relative heads

func Part2(raw string) int {
  instructions := parse(raw)
  // 1 point for the leading edge + 9 tail points
  knots := make([]*Point, 10)

  // All points start from 0,0
  for i, _ := range knots {
    knots[i] = newPoint(0, 0)
  }

  visited := set.NewSimpleSet[string]()


  for _, ci := range instructions {
    for i := 0; i < ci.steps; i++ {
      // Move the actual head
      knots[0].move(ci.direction)

      // Adjust each point relative to its head
      for j := 0; j < len(knots)-1; j++ {
        head, tail := knots[j], knots[j+1]
        tail.adjust(head)
      }
      visited.Add(knots[len(knots)-1].id())
    }
  }

  return visited.Size()
}

Same as part one, we keep track of the points we visited using our SimpleSet

That's it for today, see you tomorrow ⭐️

You can find the complete code here
Thanks for reading!

AoC Day 8 - Treetop Tree House

Gal Elmalah — Sat, 10 Dec 2022 13:28:28 +0000

Treetop Tree House

Question

The elves come to you with a problem, they want to build a tree house but they want to make sure that they have enough cover.

We are given a map of the forest with a number representing each tree's height.

Parsing

We care about the location of each tree and its height.
All of the above is available to us if we parse our map into a matrix [][]int

func parse(raw string) [][]int {
    rows := strings.Split(string(raw), "\n")
    matrix := make([][]int, len(rows))
    for i, row := range rows {
        matrix[i] = make([]int, len(row))
    }

    for i, row := range rows {
        for j, c := range row {
            matrix[i][j] = util.ParseInt(string(c))
        }
    }

    return matrix
}

Part 1

We are tasked with determining how many visible trees there are on the map.

A tree is visible from a given direction (up, right, down, and left) only if all the trees directly on that line and to the edge are shorter than him.

From that definition, we can deduce that every tree on the edge of the map is visible and an initial amount of visible trees from the get-go

// (len(mat)-2)*2 top and bottom rows - the shared elements with the columns
// len(mat[0])*2 right and left most columns
visibleTrees := (len(mat)-2)*2 + len(mat[0])*2

Now for every other tree we need to check if its visible from some direction
To do that, we will write 4 functions, each to check a different direction


func checkLeft(mat [][]int, i, j int) bool {
    for k := j - 1; k >= 0; k-- {
        if mat[i][k] >= mat[i][j] {
            return false
        }
    }
    return true
}

func checkRight(mat [][]int, i, j int) bool {
    for k := j + 1; k < len(mat[0]); k++ {
        if mat[i][k] >= mat[i][j] {
            return false
        }
    }
    return true
}

func checkUp(mat [][]int, i, j int) bool {
    for k := i - 1; k >= 0; k-- {
        if mat[k][j] >= mat[i][j] {
            return false
        }
    }
    return true
}

func checkDown(mat [][]int, i, j int) bool {
    for k := i + 1; k < len(mat[0]); k++ {
        if mat[k][j] >= mat[i][j] {
            return false
        }
    }
    return true
}

For each direction, we are going all the way until the edge, if at some point one of the trees is taller than our current tree we return false and try another direction.

Let's see the complete solution for part one

func Part1(raw string) int {
    mat := parse(raw)
    visibleTrees := (len(mat)-2)*2 + len(mat[0])*2

    for i, row := range mat {
        if i == 0 || i == len(mat)-1 {
            continue
        }

        for j, _ := range row {
            if j == 0 || j == len(row)-1 {
                continue
            }
            if checkLeft(mat, i, j) {
                visibleTrees++
                continue
            }
            if checkRight(mat, i, j) {
                visibleTrees++
                continue
            }
            if checkUp(mat, i, j) {
                visibleTrees++
                continue
            }
            if checkDown(mat, i, j) {
                visibleTrees++
                continue
            }

        }
    }

    return visibleTrees
}

We have an if statement at the beginning of each loop to make sure we are not counting the edges again.

This solution is very verbose and there are a lot of ways we can optimize it, for example keeping track of the tallest tree in each column and row and with that information skipping some of the checks.

But...the current solution is fast enough and run's in 0.35s on my local machine with my AoC input.

Part 2

Calculate how many trees are visible from each tree in every direction, multiply the numbers and find the maximum value tree in our map

We are going to take our check functions and create a similar counterpart, named calc<Direction>

func calcLeft(mat [][]int, i, j int) int {
    vis := 0
    for k := j - 1; k >= 0; k-- {

        if mat[i][k] >= mat[i][j] {
            return vis + 1
        }
        vis++
    }
    return vis
}

func calcRight(mat [][]int, i, j int) int {
    vis := 0
    for k := j + 1; k < len(mat[0]); k++ {
        if mat[i][k] >= mat[i][j] {
            return vis + 1
        }
        vis++
    }
    return vis
}

func calcUp(mat [][]int, i, j int) int {
    vis := 0
    for k := i - 1; k >= 0; k-- {
        if mat[k][j] >= mat[i][j] {
            return vis + 1
        }
        vis++
    }
    return vis
}

func calcDown(mat [][]int, i, j int) int {
    vis := 0
    for k := i + 1; k < len(mat[0]); k++ {
        if mat[k][j] >= mat[i][j] {
            return vis + 1
        }
        vis++
    }
    return vis
}

Each calc function returns the number of trees that are visible from a point on the map.

Our solution now is fairly simple, for each tree we calculate a score based on the instructions.
We then compare that score with our current max and swap them if needed.

func Part2(raw string) int {
    mat := parse(raw)
    max := 0
    for i, row := range mat {
        for j, _ := range row {
            score := calcLeft(mat, i, j) * calcRight(mat, i, j) * calcUp(mat, i, j) * calcDown(mat, i, j)
            if score > max {
                max = score
            }
        }
    }

    return max
}

That's it for today, see you tomorrow ⭐️

You can find the complete code here
Thanks for reading!

AoC Day 7 - No Space Left On Device

Gal Elmalah — Sat, 10 Dec 2022 13:28:16 +0000

No Space Left On Device

Question
This was a fun day! we finally got something challenging.

We got a device from the elves when trying to update that device we got an error that notifies us that there isn't enough memory on our device

$ system-update --please --pretty-please-with-sugar-on-top
Error: No space left on the device

To determine what's going on we start exploring the device file system and record the output (our puzzle input)
For example

$ cd /
$ ls
dir a
14848514 b.txt
8504156 c.dat
dir d
$ cd a
$ ls
dir e
29116 f
2557 g
62596 h.lst
$ cd e
$ ls
584 i
$ cd ..
$ cd ..
$ cd d
$ ls
4060174 j
8033020 d.log
5626152 d.ext
7214296 k

represent the following structure

- / (dir)
  - a (dir)
    - e (dir)
      - i (file, size=584)
    - f (file, size=29116)
    - g (file, size=2557)
    - h.lst (file, size=62596)
  - b.txt (file, size=14848514)
  - c.dat (file, size=8504156)
  - d (dir)
    - j (file, size=4060174)
    - d.log (file, size=8033020)
    - d.ext (file, size=5626152)
    - k (file, size=7214296)

When I first solved it I iterated over all commands and didn't create any kind of structure and just kept track of the current dir and update its parent size once we are done with it.
I thought about trying something a bit more interesting for this post, let's create a file system representation from our input and use it later to answer today's puzzle

First, we need to make sense of each line of our input, for that we are going to create a tokenizer!
our tokens

// token/token.go
package token

type TokenType string

const (
    Cd   TokenType = "Cd"
    Ls   TokenType = "Ls"
    File TokenType = "File"
    Dir  TokenType = "Dir"
)

type Token struct {
    Type    TokenType
    Literal string
}

We have 4 types of tokens, one for each type of output line.
In addition, we also save the raw data in literal so we can make use of it later on.

Now let's write our tokenizer, its responsibility is to get our input and transform it into a list of meaningful tokens

// token/tokenizer.go
package token

import "strings"

func newToken(tokenType TokenType, literal string) Token {
    return Token{
        Type:    tokenType,
        Literal: literal,
    }
}

func Tokenize(raw string) []Token {
    lines := strings.Split(string(raw), "\n")
    tokens := []Token{}
    for _, l := range lines {
        parts := strings.Split(l, " ")
                // process commands
        if parts[0] == "$" {
            if parts[1] == "ls" {
                tokens = append(tokens, newToken(Ls, l))
            } else {
                tokens = append(tokens, newToken(Cd, l))
            }
                // process ls output
        } else {
            if parts[0] == "dir" {
                tokens = append(tokens, newToken(Dir, l))
            } else {
                tokens = append(tokens, newToken(File, l))
            }
        }
    }
    return tokens
}

Create a struct to represent our file system

type FileSystem struct {
    root *FileSystemNode
}

type FileSystemNode struct {
    Size   int
    Parent *FileSystemNode
    Token  token.Token
    Name   string
    Dirs   map[string]*FileSystemNode
}

Now to the fun part, going over our tokens and constructing a tree like structure based on that

func newFileSystemNode(name string, token token.Token, parent *FileSystemNode) *FileSystemNode {
    return &FileSystemNode{Name: name, Parent: parent, Token: token, Dirs: map[string]*FileSystemNode{}}
}

func NewFileSystem(tokens []token.Token) *FileSystem {
    root := newFileSystemNode("/", token.Token{Type: token.Dir, Literal: "/"}, nil)
    fileSystem := &FileSystem{root}
    current := root
    for _, t := range tokens {
        switch t.Type {
        case token.File:
            current.Size += CreateFileNode(t.Literal).Size
        case token.Dir:
            node := CreateDirNode(t.Literal)
            current.Dirs[node.Name] = newFileSystemNode(node.Name, t, current)
        case token.Ls:
            continue
        case token.Cd:
            cdNode := CreateCdNode(t.Literal)
            if cdNode.To == ".." {
                current.Parent.Size += current.Size
                current = current.Parent
            } else {
                _, ok := current.Dirs[cdNode.To]
                if ok {
                    current = current.Dirs[cdNode.To]
                }
            }
        default:
            fmt.Println("Unexpected token!", t)
        }

    }

    // In case we are not ending at the root node
    for current != root {
        current.Parent.Size += current.Size
        current = current.Parent
    }

    return fileSystem
}

We iterate over our tokens and perform some operations depending on the type of token we got

file token: add the file size to the current dir
dir token: create a new directory in the current dir and name it based on the token literal (the dir name)
ls token: we don't care about it and just continue our loop
cd token:
- ".." literal: we change current to be current.parent and add the size of the current dir to the parent
- else, its some dir that we have seen before using ls and we change the current dir to be current.Dirs[dirName]

type CdNode struct {
    To string
}

func CreateCdNode(str string) CdNode {
    parts := strings.Split(str, " ")
    return CdNode{
        To: parts[2],
    }
}

At the end of the function we backtrack to our root directory and add each directory size in that path to its parent, this is because our output does not contain .. commands back to the top.

Now that we have got our file system creation process all dialed in we can start implementing the first part solution

Part 1

We are tasked to find all directories with size <= 100,000
To do that we need to have a way to walk over each directory in our file system structure. Let's add methods to support that capability

func (tree *FileSystem) Walk(visitor func(t *FileSystemNode)) {
    tree.root.Walk(visitor)
}


func (node *FileSystemNode) Walk(visitor func(t *FileSystemNode)) {
    visitor(node)
    for _, t := range node.Dirs {
        t.Walk(visitor)
    }
}

Both FileSystem and FileSystemNode get a Walk method

We pass in a function that will be called on each node in our file system.
Using the above method our solution is now as simple as

func Part1(raw string) int {
    fs := parse(raw)
    sum := 0
    fs.Walk(func(node *fileSystem.FileSystemNode) {
        if node.Size <= 100000 {
            sum += t.Size
        }
    })

    return sum
}

Part 2

In part 2 we are tasked with increasing the amount of free space to at least 3,000,000 we also know that the total memory on our device is 7,000,000
We need to find the smallest directory that we can delete that will increase the amount of free memory >= 3,000,000

In our example, we have the following options:

Delete directory e, which would increase unused space by 584.
Delete directory a, which would increase unused space by 94853.
Delete directory d, which would increase unused space by 24933642.
Delete directory /, which would increase unused space by 48381165.

Directories e and a are both too small; deleting them would not free up enough space. However, directories d and / are both big enough! Between these, choose the smallest: d, increasing unused space by 24933642.

The logic to solve part 2 is also fairly straightforward but we do need to expose the size of our fileSystem first

func (tree *FileSystem) Size() int {
    return tree.root.Size
}

Part 2 solution

func Part2(raw string) int {
    fs := parse(raw)

    const OS_MEM = 70000000
    const THRESHOLD = 30000000

    unusedSpace := OS_MEM - fs.Size()
    min := OS_MEM
    fs.Walk(func(node *fileSystem.FileSystemNode) {
        if unusedSpace+node.Size > THRESHOLD {
            if min > node.Size {
                min = node.Size
            }
        }
    })

    return min
}

For each directory, we check if by deleting it we have enough free memory unusedSpace+t.Size > THRESHOLD if it does we check to see if it's less than our current smallest directory.

Pheww...That's it for day 7!
I know this approach is a bit too structured for an AoC problem and initially, I solved it without building the entire structure, tokens etc...
For the sake of this blog post, I thought I'll make things a bit more structured and interesting

You can find the complete code here
Thanks for reading!

AoC Day 6 - Tuning Trouble

Gal Elmalah — Sat, 10 Dec 2022 13:26:54 +0000

Tuning Trouble

Question
Finally, we move out of camp!
As we start heading out of the camp one of the elves gives us a communication device, it will come as no surprise that we got the only malfunctioning device...

The device receives streams of signals that are built from a list of chars, to fix our device we need to be able to find the start-of-packet marker.

Part 1

We are told that the start of the packet is defined as a series of four different consecutive chars.
Given our signle, we need to determine how many chars should be processed before the first marker appears or in other words the index at the end of our marker.

For example, mjq<start>jpqm<end>gbljsphdztnvjfqwrcgsmlb

<start> and <end> represents the start and end of the marker accordingly

meaning the answer should be 7 (index of m)

Basically what we need to accomplish here is to find 4 consecutive chars in a row, there are multiple ways of doing this but we will use a Set to count the number of unique chars within a given range i.e i -> i+4
In each position of that range, we will take the char and add it to our set, at the end of the range if the set size is 4 then we got a winner and we can return our current index i + 4.

Set is a data structure that guarantees the uniqueness of each key, in Go, there isn't a built-in type for that but we can easily create a set using a map[rune]bool type to make this a bit more interesting let's create a generic set package

Set

We will create a package called set and in it, a struct named SimpleSet that will support a basic set of operations

Add
Has
Size

Here is the code for our SimpleSet

package set

type SimpleSet[T comparable] struct {
    items map[T]bool
}

func NewSimpleSet[T comparable](values ...T) *SimpleSet[T] {
    m := make(map[T]bool)

    return &SimpleSet[T]{
        items: m,
    }
}

func (s *SimpleSet[T]) Add(key T) {
    s.items[key] = true
}

func (s *SimpleSet[T]) Has(key T) bool {
    _, ok := s.items[key]
    return ok
}

func (s *SimpleSet[T]) Size() int {
    return len(s.items)
}

I'm using generics to have this set useful in days to come, you can read more about it here

I don't get how come Go didn't have generics until recently, imagine repeating the same code for our set for every type!

Armed with our new set, lets solve part 1!

func Part1(raw string) int {
    for i := range raw {
        set := set.NewSimpleSet[rune]()
        for _, c := range raw[i : i+4] {
            set.Add(c)
        }

        if set.Size() == 4 {
            return i + 4
        }
    }
    return -1
}

Part 2

Exactly like part 1 but now the marker needs to be 14 consecutive chars
We can take our part 1 solution and have it accept an offset to fit both parts

func Part1(raw string, offset int) int {
    for i := range raw {
        set := set.NewSimpleSet[rune]()
        for _, c := range raw[i : i+offset] {
            set.Add(c)
        }

        if set.Size() == offset {
            return i + offset
        }
    }
    return -1
}

Our part 2 solution will be Part1(input, 14.

The solution can be optimized a bit by returning early if a char is already in our set, before we do anything we first need to measure our current solution.

This can be easily done using Go benchmarks capabilities.

Create a new file main_test.go and write our benchmarks there

package main

import (
    "testing"

    "github.com/galElmalah/aoc-2022/util"
)

func BenchmarkPart1(b *testing.B) {
    input := util.ReadFile("./input.txt")
    // run the Fib function b.N times
    for n := 0; n < b.N; n++ {
        Part1(input, 4)
    }
}

func BenchmarkPart2(b *testing.B) {
    input := util.ReadFile("./input.txt")
    // run the Fib function b.N times
    for n := 0; n < b.N; n++ {
        Part1(input, 14)
    }
}

Running go test -bench=. -count 3 results in

BenchmarkPart1-8            3819            285783 ns/op
BenchmarkPart1-8            3873            285734 ns/op
BenchmarkPart1-8            4021            284767 ns/op
BenchmarkPart2-8            1086           1083411 ns/op
BenchmarkPart2-8            1083           1073575 ns/op
BenchmarkPart2-8            1046           1075867 ns/op

Now let's add the following if to our inner loop

if set.Has(c) {
    break
}

re-run the benchmark

BenchmarkPart1-8            3607            296341 ns/op
BenchmarkPart1-8            3748            294505 ns/op
BenchmarkPart1-8            3734            289663 ns/op
BenchmarkPart2-8            2490            465996 ns/op
BenchmarkPart2-8            2526            454670 ns/op
BenchmarkPart2-8            2541            451878 ns/op

we can see that for part 1 there is barely an improvement but for part 2 that early return does make a noticeable difference, awesome!

That's it for today, we created our very own Set data structure and used go benchmarks to optimize our solution.

I hoped you enjoyed and learned something new cause I sure did!

You can find the complete code here
Thanks for reading!

AoC Day 5 - Supply Stacks

Gal Elmalah — Sat, 10 Dec 2022 13:21:12 +0000

Supply Stacks

Question

Welcome to day 5 of AoC, aka, annoying AF parsing day.

We are crane operators!
What do we want?! More stacks and crates!

Anyhow, we are charged to execute a series of delicate manuvers using our insane crane skills

Our input is given to us as follows

    [D]    
[N] [C]    
[Z] [M] [P]
 1   2   3 

move 1 from 2 to 1
move 3 from 1 to 3
move 2 from 2 to 1
move 1 from 1 to 2

The first half represents the current state of stacks and crates.
The second one is a series of moves we need to perform.

Crates can only be moved one at a time!

Parsing

How can we parse that input into something meaningful?
Well first let's seprate both halves using

parts := strings.Split(raw, "\n\n")
rawStacks := parts[0]
rawMoves := parts[1]

Now let's tackle parsing the crates!

One way we can go about it is simply copy-pasting our input into an object by hand but where is the fun in that?!

If we look closely at our input we might notice that the letters fit in chunks of four chars, for example


 0 | 1 | 2 | // positions in chunks array
xxxxxxxxxxxx
    [D]    
[N] [C]    
[Z] [M] [P]
 1   2   3 
             // row 1 col 1,2,3
chunks -> [ ["   ","[D] ","   "] ...]

Armed with that information we can write the following code to prase crates and classify them into the right stack

func parseStacks(crates []string) [][]string {
    stacks := make([][]string, 9)
    for _, row := range crates {
        rowOfCrates := chunkBy(strings.Split(row, ""), 4)
        for crateNo, crateCandidate := range rowOfCrates {
            for _, char := range crateCandidate {
                if char >= "A" && char <= "Z" {
                    //pre-appending an element to array
                    stacks[crateNo] = append([]string{char}, stacks[crateNo]...)
                }
            }
        }
    }
    return stacks
}

Let us look at the list of instructions, each line represents one command move x from y to z, lets's create a struct to populate exactly that and turn our list into a list of those structs

type Instruction struct {
    amount int
    from   int
    to     int
}

func toInts(fromStrings []string) (result []int) {
    for _, n := range fromStrings {
        num, _ := strconv.Atoi(n)
        result = append(result, num)
    }
    return result
}

func parseInstructions(rawInstructions []string) (instructions []Instruction) {
    matcher := regexp.MustCompile(`move (\d+) from (\d+) to (\d+)`)
    for _, line := range rawInstructions {
        match := toInts(matcher.FindStringSubmatch(line)[1:])
        instructions = append(instructions, Instruction{
            amount: match[0],
            from:   match[1] - 1,
            to:     match[2] - 1,
        })
    }

    return instructions
}

Combining parseInstructions and parseStacks to get our parse function

func parse(raw string) ([][]string, []Instruction) {
    chunks := strings.Split(string(raw), "\n\n")
    rawCrates := strings.Split(chunks[0], "\n")
    rawInstructions := strings.Split(chunks[1], "\n")

    return parseStacks(rawCrates), parseInstructions(rawInstructions)
}

In go you can have more than one return value.

Part 1

Perform the list of instructions then construct a string built from the top crate of each stack, for example in our current example its NDP but after the instructions are applied its CMZ

Using our parsed instructions and stacks, the solution becomes quite trivial

func Part1(raw string) string {

    stacks, instructions := parse(string(raw))

    // applying instructions
    for _, instruction := range instructions {
        from := instruction.from
        to := instruction.to
        // another approach is to create a slice of size amount from `moveFrom`
        // reverse that slice and push it to `moveTo` but the approach here is much simpler to reason about
        for i := 0; i < instruction.amount; i++ {
            stacks[to] = append(stacks[to], stacks[from][len(stacks[from])-1])
            stacks[from] = stacks[from][:len(stacks[from])-1]
        }
    }

    answer := ""
    for _, stack := range stacks {
        if len(stack) > 0 {
            answer += stack[len(stack)-1]
        }
    }

    return answer

}

And that's it for part one, besides the parsing it was quite simple.

Part 2

Something was off with our stacks, we went to make sure that our crane is CrateMover 9000 but it was the 9001 model! this means we can move multiple crates at once.

The meaning of this in the context of the code we wrote is that we don't need to preserve a stack-like order when moving crates, the top element from our source crane will stay on top instead of being at the bottom of the crates we are moving

func Part2(raw string) string {
    stacks, instructions := parse(string(raw))
    // mutating the stacks
    for _, instruction := range instructions {
        from := instruction.from
        to := instruction.to
        amount := instruction.amount
        takeRange := len(stacks[from]) - amount
        // take items from `takeRange` until the end of the slice and append them to the target stack
        stacks[to] = append(stacks[to], stacks[from][takeRange:]...)
        // remove items that come after the `takeRange` from our source crate
        stacks[from] = stacks[from][:takeRange]
    }

    answer := ""
    for _, stack := range stacks {
        if len(stack) > 0 {
            answer += stack[len(stack)-1]
        }
    }

    return answer

}

That's it for day 5 of AoC, hoped you enjoyed reading it, and feel free to suggest improvements to my poor Go or solution

You can find the complete code here
Thanks for reading!

AoC Day 4 - Camp Cleanup

Gal Elmalah — Wed, 07 Dec 2022 06:35:00 +0000

Camp Cleanup

Question
Seems like this time we are tasked with optimizing the elves' cleaning tasks! those elves can improve their lists...
The cleaning tasks are assigned to each pair of elves, for example:

2-4,6-8
2-3,4-5
5-7,7-9
2-8,3-7
6-6,4-6
2-6,4-8

For the first few pairs, this list means:

Within the first pair of Elves, the first Elf was assigned sections 2-4 (sections 2, 3, and 4), while the second Elf was assigned sections 6-8 (sections 6, 7, 8).

The Elves in the second pair were each assigned two sections.

As always, let's start with parsing our list of assignments to something we can work with

Parsing

First, let's decide what we would like our output to look like.
we can create a struct that represents each pair task but that seems a bit redundant, let's keep it simple and create something like
[[st1, et1, st2, et2] , ... ] where st1 and et1 is the first elf range of sections and st2 and et2 are the second elf range.

We will call a range of sections a "task" from now on.

To get that we can go with splitting on various delimiters but today I finally had an excuse to use a Regex in go.

We will create a regex, containing capture groups for each t and use
FindStringSubmatch to iterate over the resulting matches.

func parse(raw string) [][]int {
    lines := strings.Split(string(raw), "\n")
    pairs := [][]int{}
    r := regexp.MustCompile(`(\d+)-(\d+),(\d+)-(\d+)`)

    for _, l := range lines {
        match := r.FindStringSubmatch(l)
        pair := []int{}
        for _, m := range match[1:] {
            num, _ := strconv.Atoi(m)
            pair = append(pair, int(num))
        }
        pairs = append(pairs, pair)
    }

    return pairs
}

Its worth noting that the first match is the entire string we are passing and that's why we are skipping it when looping over the results range match[1:]

Part 1

The elves are really smart and noticed that some tasks entirely overlap with their partner tasks.
We are tasked with finding and counting those overlaps.

Let's draw this out so it will be a bit clearer

.234.....  2-4 // no overlapping 
.....678.  6-8

.23......  2-3 // no overlapping 
...45....  4-5

....567..  5-7 // just a partial overlapping NOT GOOD ENOUGH
......789  7-9

.2345678.  2-8 
..34567..  3-7 // contained in 2-8

.....6...  6-6 // contained in 4-6
...456...  4-6

.23456...  2-6 // again, partial overlapping 
...45678.  4-8

From the above, we can say that if one of the elves' starting tasks is greater or equal to the other elf starting task AND the final task is smaller or equal, then the assignment is contained.
We now write a solution to part 1

func part1(raw []byte) int {

    var assignments = parse(string(raw))
    count := 0
    for _, pairAssignmentRange := range assignments {
        st1 := pairAssignmentRange[0]
        et1 := pairAssignmentRange[1]
        st2 := pairAssignmentRange[2]
        et2 := pairAssignmentRange[3]
        if (st1 >= st2 && et1 <= et2) || (st2 >= st1 && et2 <= et1) {
            count++
        }

    }

    return count

}

If you know a better way to take those values from pairAssignmentRange let me know in the comment section

Part 2

We are asked to count overlapping tasks of any kind meaning its enough that we will have one overlapping "section" in our range for it to count as an overlap
What does that mean in code? it means that we are looking for tasks that are ending inside the range of the other task.
For example

....567..  5-7
......789  7-9

These tasks overlap over "section" 7.
We can now write our part 2 solution as follows


func part2(raw []byte) int {
    var assignments = parse(string(raw))
    count := 0
    for _, pairAssignmentRange := range assignments {
        st1 := pairAssignmentRange[0]
        et1 := pairAssignmentRange[1]
        st2 := pairAssignmentRange[2]
        et2 := pairAssignmentRange[3]
        if (et1 >= st2 && et1 <= et2) || (et2 >= st1 && et2 <= et1) {
            count++
        }

    }

    return count
}

The only thing we changed was the if statement to look at the ending task "section"

To sum things up, each day I feel more and more confident with Go, and the task's code starts flowing.

I think that one of Go's upsides is that the language is fairly small without any fancy concepts so the learning curve is not that long or hard.

You can find the complete code here
Thanks for reading!

AoC Day 3 - Rucksack Reorganization

Gal Elmalah — Wed, 07 Dec 2022 06:34:39 +0000

Rucksack Reorganization

Question
We are going into the jungle! We put Legolas in charge of packing the supplies for our journey but it seems like his packing abilities are nothing like his bow-aiming skills and he kind of sucks at packing...
We do however have a manifest of the items in each rucksack, that list looks as follows

vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDw

Each line represents one rucksack and each half of the line represents a compartment inside a rucksack.
Items are identifiable by their chars, and yes, "A" and "a" are not the same items.
For example
The first rucksack contains the items vJrwpWtwJgWrhcsFMMfFFhFp, which means its first compartment contains the items vJrwpWtwJgWr, while the second compartment contains the items hcsFMMfFFhFp. The only item type that appears in both compartments is lowercase p.

To help prioritize item rearrangement, every item type can be converted to a priority:

Lowercase item types a through z have priorities 1 through 26.
Uppercase item types A through Z have priorities 27 through 52.

In the above example, the priority of the item type that appears in both compartments of each rucksack is 16 (p), 38 (L), 42 (P), 22 (v), 20 (t), and 19 (s); the sum of these is 157.

Part 1

In part one we are tasked with summing up the priority of items that appears in both compartments

Let's start with parsing our input

Parsing

Ideally, we would like to have an array containing a tuple with a set for each half
for example vJrwpWtwJgWrhcsFMMfFFhFp -> [ [set(vJrwpWtwJgWr), set(hcsFMMfFFhFp)]... ]
We are choosing a set DS here to have the ability to easily answer the question "is the letter X in set Y?" later on

// go doesn't have a built in Set DS so we need to roll our own here
func makeSet(chars string) map[rune]bool {
    set := map[rune]bool{}
    for _, c := range chars {
        set[c] = true
    }
    return set
}

func parse() [][]map[rune]bool {
    data, _ := os.ReadFile("./input.txt")
    lines := strings.Split(string(data), "\n")

    rucksacks := [][]map[rune]bool{}
    for _, line := range lines {
        c1 := makeSet(line[:len(line)/2])
        c2 := makeSet(line[len(line)/2:])
        w := []map[rune]bool{c1, c2}
        rucksacks = append(rucksacks, w)
    }

    return rucksacks
}

Interesting to note that we are getting each char as a rune which is the ASCII value of said char

We are using : to slice our line into two parts, line[x:] means slice from x until the end, and lines[:x] means slice from the beginning of the array until x

Solution

Now that we are done preparing our data we can write the following code to calc the priority of each char

func calcPriority(c rune) int {
    if c >= 'a' && c <= 'z' {
        return int(c) - 'a' + 1
    } else {
        return int(c) - 'A' + 27
    }
}

Basically, we are taking our rune, deducting the base value e.g 'a' or 'A', and adding the range from the question, meaning, lowercase from 1 to 26 and uppercase from 27 to 52

This code won't work if I use double quotes in the comparison since you can't compare strings and runes, the single quotes actually define 'a' as having the type rune

Ok we are all ready to go now, let's solve part 1
We are going to iterate over all rucksacks and for each one of those find the letter that is in the first compartment and the second one.
When we find one, we pass it along to our calcPriority function and accumulate its value

func pt1() int {
    groups := parse()
    sum := 0
    for _, group := range groups {
        s1 := group[0] // first compartment 
        s2 := group[1] // second compartment 
        for k, _ := range s1 {
            if s2[k] {
                sum += calcPriority(k)
            }
        }
    }

    return sum
}

cool cool cool, we're all done with part 1 let's see what part 2 got in store for us

Part 2

We are not tasked with finding the priority of the group badges, a badge is defined to be an item that is contained in 3 consecutive rucksacks

From the example input above we can draw the following example

vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg

And the second group's rucksacks are the next three lines:

wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDw

In the first group, the only item type that appears in all three rucksacks is lowercase r; this must be their badges. In the second group, their badge item type must be Z.

Priorities for these items must still be found to organize the sticker attachment efforts: here, they are 18 (r) for the first group and 52 (Z) for the second group. The sum of these is 70.

We will need to tweak our parsing code a bit to create sets for chunks of 3 rows at a time, this looks like this

func chunkInto(s []string, size int) [][]string {
    results := [][]string{}
    for i := 0; i < len(s); i += size {
        results = append(results, s[i:i+size])
    }
    return results
}


func parse2() [][]map[rune]bool {
    data, _ := os.ReadFile("./input.txt")
    rows := strings.Split(string(data), "\n")
    groups := chunkInto(rows, 3)
    rucksacks := [][]map[rune]bool{}
    for _, chunk := range groups {
        w := []map[rune]bool{}
        for _, c := range chunk {
            w = append(w, makeSet(c))
        }
        rucksacks = append(rucksacks, w)
    }
    return rucksacks
}

We can now solve part 2 very similarly to part 1

func pt2() int {
    groups := parse2()

    sum := 0
    for _, group := range groups {
        s1 := group[0]
        s2 := group[1]
        s3 := group[2]
        for k, _ := range s1 {
            if s2[k] && s3[k] {
                sum += calcPriority(k)
            }
        }
    }

    return sum
}

And that's it for today boys and girls, I hope you are enjoying AoC as much as I do so far 🙂

You can find the complete code here
Thanks for reading!

AoC Day 2 - Rock Paper Scissors

Gal Elmalah — Sun, 04 Dec 2022 15:39:33 +0000

Rock Paper Scissors 🪨🧻✂

Question

The Elves begin to set up camp on the beach. To decide whose tent gets to be closest to the snack storage, a giant Rock Paper Scissors tournament is already in progress.

God the question's description is always pure gold...now let's jump right in.

We are given a string, our "strategy guide" that represents a rock, paper, scissors turn decision.
The string is divided into two columns, the first represents the first player's decision and the second ours.
For example:

A Y
B X
C Z

We are also told the following:
For player 1 - A = Rock, B = Paper, C = Scissors
For player 2 - X = Rock, Y = Paper, Z = Scissors
We are also given a score table for the outcome and the decision we made, for example, a win is 6 points and choosing paper is 2 points, etc...

Like previous questions, we'll start by parsing our input

Parsing

We can go (see what I did there?) with several options to represent our game but in my opinion, an array of tuples is the simplest option

func parse(raw string) [][]string {
    chunks := strings.Split(string(raw), "\n")
    pairs := make([][]string, len(chunks))
    for i := range pairs {
        pairs[i] = strings.Split(chunks[i], " ")
    }

    return pairs
}
// example output
// [ [A, Y], [B, X], [C, Z] ]

The make function allocates a piece of memory in a certain, specified size for our array

Part 1

We are asked to provide our total score if we play exactly as instructed in the strategy guide.
Let's think about this for a bit, there are several ways we can solve this, we can use a bunch of if statements or some fancy pattern matching, since go does not have pattern matching and I don't want to write a ton of if statements we will go with a hybrid approach.
We will create 3 different mappings:

Represents the points we get for our choice e.g rock, paper, or scissors
Winning state, meaning If we choose X what does the other player need to choose for us to Win
Tie state, essentially the same as .2

scores := map[string]int{
    "X": 1,
    "Y": 2,
    "Z": 3,
}

// If I choose X(Rock) I need him to choose C(scissors) in order to win
win := map[string]string{
    "X": "C", 
    "Y": "A",
    "Z": "B",
}

tie := map[string]string{
    "X": "A",
    "Y": "B",
    "Z": "C",
}

We don't take into account the losing state since its essentially a no-op (0 points)

Building on top of these maps and our parsing logic, we can now solve the first part with the following code

func part1(raw []byte) int {

    pairs := parse(string(raw))

    // X Rock, Y Paper, Z Scissors
    scores := map[string]int{
        "X": 1,
        "Y": 2,
        "Z": 3,
    }

    win := map[string]string{
        "X": "C",
        "Y": "A",
        "Z": "B",
    }

    tie := map[string]string{
        "X": "A",
        "Y": "B",
        "Z": "C",
    }

    score := 0
    for _, pair := range pairs {
        his := pair[0]
        my := pair[1]
        score += scores[my]
        if win[my] == his {
            score += WINNING_POINTS
        }

        if tie[my] == his {
            score += TIE_POINTS
        }

    }
    return score

}
// output for part 1 based on the example is
// 15 -> (8 + 1 + 6)

At each loop iteration we first add the points based on our choice score += scores[my] then we check if his move is what we need based on our player choice, to win or get a tie, and if it is we add the necessary points to our total score.

Part 2

In part two the sneaky elves switch things up a bit.
Instead of our column representing our moves, it represents the turn outcome where X = lose, Y = tie, and Z = win and we need to choose our choice accordingly.
For example, let's look at the first turn A Y, the new meaning of this pair is "player one chose Rock, and the game ended in a tie" building on this information we can create new mappings, the new mappings will be between player 1 choice and the choice player 2 need to make to get to a certain state e.g winning, losing, tie, etc...
Since it's pretty similar to part 1, we will jump right ahead and look at part 2 as a whole

func part2(raw []byte) int {

    var pairs = parse(string(raw))

    // X Lose, Y Tie, Z Win
    scores := map[string]int{
        "X": 1,
        "Y": 2,
        "Z": 3,
    }

    win := map[string]string{
        "C": "X",
        "A": "Y",
        "B": "Z",
    }

    tie := map[string]string{
        "A": "X",
        "B": "Y",
        "C": "Z",
    }

    lose := map[string]string{
        "A": "Z",
        "B": "X",
        "C": "Y",
    }
    score := 0

    for _, pair := range pairs {
        hisMove := pair[0]
        myMove := pair[1]

                // we lose
        if myMove == "X" {
            score += scores[lose[hisMove]]
        }
                // we end in a tie
        if myMove == "Y" {
            score += TIE_POINTS
            score += scores[tie[hisMove]]
        }
                // we win
        if myMove == "Z" {
            score += WINNING_POINTS
            score += scores[win[hisMove]]
        }
    }
    return score
}

For each desired state we check what move we need to do based on player 2 choice and pass it down to the scores map.

That's it we are all done with paper, rock, scissors and I must admit that I didn't think it can be so confusing 🤣

You can find the complete code here
Thanks for reading!