Turtles all the way down.

I won't be sharing all the code I used to solve day 3, but there's a 'new' form of memory that writes in a spiral, using every node, and we have to work with this.

There's a mathematical way to solve this

If you notice, the bottom right corners follow the sequence of being odd squares, so you can simply calculate the closest odd square to your input and count from there, Bam.

But the code man, the code!

But the code works too. To tackle this problem I dived into OOP, designing a very limited turtle class. This turtle has an x and y position, the number of moves left in the direction it's currently facing, a heading, and... well let's see it.

class Turtle
{
    private:
        int x_coord = 0;
        int y_coord = 0;
        int moves_left_in_direction = 1;
        int moves_factor = 1;
        char heading = 'E'; 
        int turns = 0;
    public:
        void move_up() {y_coord +=1; moves_left_in_direction--;}
        void move_down() {y_coord -=1; moves_left_in_direction--;}
        void move_left() {x_coord -=1; moves_left_in_direction--;}
        void move_right() {x_coord +=1; moves_left_in_direction--;}
        void move_forward()
        {
            switch (heading)
            {
                case 'E':
                    move_right();
                    break;
                case 'N':
                    move_up();
                    break;
                case 'W':
                    move_left();
                    break;
                case 'S':
                    move_down();
                    break;
            }
        }
        void turn_left()
        {
            turns++;
            switch (heading)
            {
                case 'E':
                    heading = 'N';
                    break;
                case 'N':
                    heading = 'W';
                    break;
                case 'W':
                    heading = 'S';
                    break;
                case 'S':
                    heading = 'E';
                    break;
            }
        }
       void check_moves()
        {
            if (moves_left_in_direction == 0)
            {
                turn_left();
                if (turns == 2)
                {
                    moves_factor++;
                    turns = 0;
                }
                moves_left_in_direction = moves_factor;
            }
        }
        void full_movement()
        {
            for (int i = 0; i < TOTAL_MOVES - 1; i++)
            {
                move_forward();
                check_moves();
            }
        }
        int get_x_coord() {return x_coord;}
        int get_y_coord() {return y_coord;}
};

Instantiating the turtle as myTurt and calling full_movement() on it, the directions are followed completely and we just have to calculate the Manhattan Distance by getting the absolute value of x and adding it to the absolute value of y.

Here's the driver program.

int main(int argc, char** argv)
{
    Turtle myTurt;
    myTurt.full_movement();
    int manhattan_distance = std::abs(myTurt.get_x_coord()) + std::abs(myTurt.get_y_coord());
    std::cout << "Manhattan Distance" << ": " << manhattan_distance << std::endl;
    return 0;   
}

That's it for part 1.

Part 2 requires building the memory spiral. This can easily be done with the same turtle program: We add a simple function to the turtle to get it to move, then check if it needs to change direction, and if so, does so.

        void next_move()
        {
            move_forward();
            check_moves();
        }

then

int main(int argc, char** argv)
{
    Turtle myTurt;
    int m = 1000;
    int n = 1000;
    std::vector<std::vector<int>> matrix(m, std::vector<int> (n, 0));
    int num_dropoff = 0;
    matrix[myTurt.get_x_coord()][myTurt.get_y_coord()] = 1;
    while (num_dropoff < TOTAL_VALUE)
    {
        myTurt.next_move();
        num_dropoff = 0;
        int x = myTurt.get_x_coord();
        int y = myTurt.get_y_coord();
        num_dropoff += matrix[x-1][y-1];
        num_dropoff += matrix[x+0][y-1];
        num_dropoff += matrix[x+1][y-1];
        num_dropoff += matrix[x-1][y];
        num_dropoff += matrix[x+0][y];
        num_dropoff += matrix[x+1][y];
        num_dropoff += matrix[x-1][y+1];
        num_dropoff += matrix[x+0][y+1];
        num_dropoff += matrix[x+1][y+1];
        matrix[x][y] = num_dropoff;
    }
    std::cout << num_dropoff << std::endl;

}

the neighbor addition is sloppy: it was originally written in nested for loops, but that was sloppy too. I'm sure there's a better method but this works and doesn't require much time or effort to run. This makes the turtle move, calculate the dropoff number, then drop it off on the matrix. It repeats this process until it drops off a number higher than the provided input, then spits it out.

Turtles are unnecessary!

There's many ways to solve this problem, and a turtle class isn't mandatory for any of it! However, I like to rely on oop when solving these challenges often. At first thought, I wasn't sure how to tackle this issue, but my cousin sent me a tiktok video saying a girl was wearing a nice watch, so clearly she 'ain't no turtle,' and images of LOGO in grade school came flooding back. By conceptualizing the 2d vector as the memory disk, and the turtle as a sort of stylus following instructions to build the grid in the spiral form. it came together nice and easy, despite being slightly longer code-line-wise.

If anybody solved this one with more functional programming or just in a simple way without using OOP, I'd be fascinated to learn more about it! But for now,

When to use OOP

I personally rely on OOP sort of abstraction and interpretation of problems in many contexts. By using a turtle object to build the graph in part 1, I only had to minorly change my driver program to build the new grid, and that's a powerful concept. This blog is about my learning journey, so I probably rely on OOP concepts a bit too much, but they get the job done. I was even going to build a NODE object and make a grid of those, but I figured I might as well keep it as simple as possible.

On to day 4!