# Rope Bridge

Using Structs to Improve Design.

## Problem Description

*The full description can be found in **RopeBridge.zip**.*

You will write an algorithm that opens a file `input.txt`

and follows a series of motions for the head of a rope. The rope comprises a series of knots that move per the rules of the rope. You will track the movement of the tail of the rope throughout the motions.

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 away from the tail, the tail is pulled toward the head. You can model the positions of the knots on a two-dimensional grid. Following a series of motions for the head, you will determine how the tail will move.

If the head is ever two steps up, down, left, or right from the tail, the tail must also move in one step in that direction so it's close enough.

Otherwise, if the head and tail aren't touching and aren't in the same row or column, the tail always moves one step diagonally to keep up.

Your goal is to simulate a rope consisting of *ten* knots. One knot is the head of the rope and moves according to the series of motions. Each knot further down the rope follows the knot in front of it using the same rules above. You need to keep track of the positions that the new tail, `9`

, visits.

You will compute the *number of positions that the tail of the rope visits at least once*. Encapsulate your answer in flag braces, i.e. `flag{36}`

. *Hint*: The start point is arbitrary.

## Walkthrough

This is an interesting challenge. There are many ways to solve this, and I don't think my solution is the best. I want to use this challenge to demonstrate my thought process in solving challenges. Although the most efficient solution may not come out the first time, that doesn't discount it as a working solution. If you want to practice writing more space-efficient solutions, I challenge you to track with a linked list and check for unique points before you enter them into the list. Be sure that you don't inadvertently write an `O(n^2 log n)`

solution; mine runs in `O(n log n)`

time.

**Remember that you have limited time during competitions.** If you spend all your time searching for a more optimal solution, you won't have time to solve other problems. It's better to have a working solution that is prone to bad input or isn't the most efficient than to lose points in other areas.

If you have spare time at the end, this is the time to polish solutions. I have submitted some weird solutions during competitions that worked, but were far less efficient. I then spent time at the end or while I'm polishing my write-ups to improve them.

Our goal is to track the number of unique points in the graph. A *static array* does this for us just fine.

We can make a

`struct`

to represent a point on the graph.We can make a

`struct`

to represent a vector between two points. This will help us track the distance between each knot to see if we must move any knot to catch up.

The vector `struct`

is not an intuitive idea. I didn't think about making one until most of the way through my solution. I'll mention when I decided to add this to my solution. It is perfectly valid to solve it without one, but it made sense in my head at the time of writing.

The current action plan is to read each line, perform the instruction, and then add the tail's position to the list. Then, we can sort the list of tail positions and count the unique points. *If you're comfortable, try to solve this by checking for unique points before adding to the list, but watch for exponential time complexity.*

### Reading the File

We'll begin with the basics. We need to open the file and initialize the data.

In this stage, we also need to define our `struct Point`

and `struct Vector`

.

This syntax allows us to set a default value. Note that `_default`

is not required, but I use this to distinguish that this object is the default for each `struct`

. If I want to initialize a `struct Point`

with the default, I can do the following:

Now, we need to initialize the chain. The chain contains 10 points. We can initialize them all to the default value.

We also need to hold the list of points that the tail visits. As stated previously, we are using a static array to do this.

### Parsing the Data

We can use the same `getline`

function that we used in the previous challenge to read each line. Since we know the length of each line and it doesn't matter to us, we don't need to store `read`

.

Each line has two items: a direction and a number of steps. We can use `strtok`

to parse each line.

We need to process each instruction `times`

times. For each instruction, we should determine which direction we travel and move the head of the chain. We must then adjust the rest of the chain to follow the head. Finally, we need to record the tail's position in the list.

We make a call to `adjust`

to move each link of the chain. I chose to make this a free function because we must do it for each chain link, and it makes the code a lot cleaner. This method must determine if the provided chain links are two far, then move the tail closer to the head.

Let's think about how we might do this. Below is a diagram of all the cases that you need to move the tail:

I chose to break this down by side. The end state is that the tail is in one of four positions:

Given each side, we are guaranteed one move for the tail: moving inward. Then, based on the perpendicular direction, we see if we need to move laterally to reach this position. We use a `struct Vector`

to represent the distance between `head`

and `tail`

. We use this difference to determine how we must move.

This completes the processing of the instructions.

### Printing the Flag

Now that our data is properly complete and processed, we must compute the flag. The flag is the number of unique positions that the tail visited. We can do this by sorting the list of points the tail visited. If duplicates are in the list, they will be adjacent. As we iterate across the list, we'll check for unique lists.

First, let's sort the data.

We need to define the comparison function. We'll arbitrarily choose to compare the `x`

values first, then the `y`

values.

Once our data is sorted, we can iterate and count the number of unique points. We'll define a function called `equal`

that returns `1`

if two points are equal and `0`

otherwise.

Then, we check if adjacent points are equal and count the unique points.

We can use this to print the flag! Don't forget to free your memory.

## Full Solution

The full solution is below:

Last updated