DEV Community: verified_tinker

🦀 Solving with Rust: Advent of Code 2022 – Day 06

verified_tinker — Tue, 06 Dec 2022 06:55:52 +0000

See the entire, unedited problem on the official website.

Today's an easy one.

Part 1

Problem: We're given a stream of characters (and I say "stream", but the input is a full, single-line string), and we're to find the (1-based, not 0-based) index of the first character that completes a so-called start-of-packet marker—a 4-character string where each character is unique.

mjqjpqmgbljsphdztnvjfqwrcgsmlb: first marker after character 7—jpqm being the marker and m the 7th character
bvwbjplbgvbhsrlpgdmjqwftvncz: first marker after character 5
nppdvjthqldpwncqszvftbrmjlhg: first marker after character 6
nznrnfrfntjfmvfwmzdfjlvtqnbhcprsg: first marker after character 10
zcfzfwzzqfrljwzlrfnpqdbhtmscgvjw: first marker after character 11

This is known as a "sliding window" problem. We must first compare elements 1 through 4, then 2 through 5, 3 through 6, and so on until the end.

As it so happens, Rust's standard library comes with a function that does exactly that: std::slice::windows().

use std::collections::HashSet;

pub fn process_part_1(input: &str) -> usize {
    let window_size = 4;

    input
        .as_bytes()
        .windows(window_size)
        .position(|chars| {
            let set: HashSet<_> = chars.iter().collect();
            set.len() == window_size
        })
        .map(|idx| idx + window_size)
        .expect("There should always be an answer.")
}

Because windows() is a function on slices and not string slices (i.e. not &str), we use as_bytes() to get a slice. This works only because we know the input is an ASCII string and each character is represented by one byte. That returns an iterator over u8's and not char's, but it makes no difference. (If we were working with more than ASCII, we'd have to call input.chars().collect::<Vec<_>>() and proceed with that.)
As the name suggests, Iterator::position() finds the position—index—of the first occurrence that satisfies our condition.
An easy way to check that the characters are unique is to add them to a HashSet and confirm its length is the same as the number of characters added.
Because we want the end index of the window and not the start (plus 1, as we're counting from 1 and not 0), we add size to the result. Option implements map(), making that trivial.

Part 2

Problem: Exactly the same as above, but window_size is 14 instead.

Let's extract the code into a separate function and reuse that.

pub fn process_part_1(input: &str) -> usize {
    find_how_long_til_n_unique_chars(input, 4).expect("There should always be an answer.")
}

pub fn process_part_2(input: &str) -> usize {
    find_how_long_til_n_unique_chars(input, 14).expect("There should always be an answer.")
}

fn find_how_long_til_n_unique_chars(input: &str, n: usize) -> Option<usize> {
    use std::collections::HashSet;

    input
        .as_bytes()
        .windows(n)
        .position(|chars| {
            let set: HashSet<_> = chars.iter().collect();
            set.len() == n
        })
        .map(|idx| idx + n)
}

We're done!

As always, if you've got ideas for improvements, feel free to share them in the comments.

🦀 Solving with Rust: Advent of Code 2022 – Day 05

verified_tinker — Mon, 05 Dec 2022 09:06:14 +0000

View the code on GitHub.

See the entire, unedited problem on the official website.

We're given rows of crates, stacked in columns, and instructions for a crane to follow.

    [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 part represents the stacks of crates, and the second is the instructions. You can read them as, "Move 3 crates from Stack 1 to Stack 3."

Part 1

Problem: After all the instructions have been followed, determine which crates will end up on top of each stack. The crates are moved one at a time.

The expected result for the sample input above is "CMZ":

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

The problem can be broken down into three components:

Parse the crates into some usable format.
Parse the instructions.
Apply the instructions and calculate the output (the topmost crates).

Parsing the Crates.

I chose to store the configuration of the crates as a HashMap, where the position of a stack—in other words, its column—is the key and the crates themselves are a vector of characters.

fn parse_crates(input: &str) -> HashMap<usize, Vec<char>> {
    input
        .lines()
        .take_while(|line| line.trim_start().starts_with('['))
        .flat_map(|line| {
            line.chars()
                .chain(iter::once(' '))
                .array_chunks::<4>()
                .enumerate()
                .filter_map(|(col, [_, maybe_crate, _, _])| {
                    if maybe_crate == ' ' {
                        None
                    } else {
                        Some((col, maybe_crate))
                    }
                })
        })
        .fold(HashMap::new(), |mut crates, (col, char)| {
            // The instructions use one-based indexing, so adjust `col` accordingly.
            let col = col + 1;

            if let Some(chars) = crates.get_mut(&col) {
                chars.insert(0, char);
            } else {
                crates.insert(col, vec![char]);
            }

            crates
        })
}

Let's break that down.

The take_while() makes sure the iteration ends where it should.
Then we break up every line into groups of four using array_chunks(), a delightful little function from Nightly Rust.
Only then do we enumerate the elements. Had we done that before the chunking, we'd be counting characters. With this, we're counting chunks, and that tells us which column we're on.
We pattern match on the column and the array of 4 characters. The array will either be all whitespace or come in the form of "[_] ", so we check the second character.
Finally, we use fold() to continue the chain. It could be replaced with a procedural for loop, if that's your preference. Either way, we add the character to the beginning of the vector stack, because the iteration starts from the top, not the bottom. It'd be more efficient to just reverse the stacks once after the iteration or use VecDeque, and if the input was great enough I would, but as it is, I opted for simplicity.

Take note of chain(iter::once(' ')). We're chunking in fours because the first n - 1 stacks (where n is the amount of columns) are divisible into groups of "[_] ", but the rightmost stacks do not have trailing whitespace and are three characters long, so array_chunks() would leave them out. This fixes that.

Figuring Out Which Crates End Up On Top

While we're at it, let's also write a function that gets the topmost crates and builds the output string.

fn get_topmost_crates(crates: HashMap<usize, Vec<char>>) -> String {
    crates
        .into_iter()
        .sorted()
        .filter_map(|(_col, mut stack)| stack.pop())
        .collect()
}

Worthy of attention here is the sorted() part. That's a convenience function from itertools that takes an iterator and converts it to a sorted one.

It's impossible to sort a collection during iteration. You need to allocate the space for all the elements first. sorted() doesn't break that law; it allocates a vector behind the scenes, sorts it, and returns an iterator to it, letting us keep the builder pattern going.

Parsing the Instructions

This part is easy. Every instruction is exactly one line long and contains three numbers. All we need to do is extract them.

fn parse_instructions(input: &str) -> Vec<(usize, usize, usize)> {
    input
        .lines()
        .filter(|line| line.starts_with("move"))
        .map(|line| {
            line.split(' ')
                .filter_map(|str| str.parse::<usize>().ok())
                .collect_tuple()
                .expect("Every instruction should contain 3 numbers.")
        })
        .collect()
}

filter_map() takes a closure that returns Option. It discards any None values and automatically unwraps the Some() ones. However, parse() returns a Result, so we call ok() to convert it into Option.

Once again, we're using collect_tuple() from itertools to make things easier. If you dislike the use of expect(), it's possible to return Result<Vec<...>, ...>, like so:

fn parse_instructions(input: &str) -> Result<Vec<(usize, usize, usize)>, &'static str> {
    input
        .lines()
        .filter(|line| line.starts_with("move"))
        .map(|line| {
            line.split(' ')
                .filter_map(|str| str.parse::<usize>().ok())
                .collect_tuple()
                .ok_or("Every instruction should contain 3 numbers.")
        })
        .collect::<Result<Vec<_>, _>>()
}

In a real program, leaving error-handling to the caller may be wise, but I think expect() is better suited here, since we'd be unwrapping the return value anyway. I'll go with the initial version.

Putting It All Together

Now that we've written all the helper functions, it's time to assemble them. The only logic left is following the instructions.

pub fn process_part_1(input: &str) -> String {
    let mut crates = parse_crates(input);
    let instructions = parse_instructions(input);

    for (amount, from, to) in instructions {
        let popped_crates = crates.get_mut(&from).map_or_else(
            || panic!("Instruction tried to take from a stack that doesn't exist."),
            |stack| stack.split_off(stack.len() - amount),
        );

        crates.get_mut(&to).map_or_else(
            || panic!("Instruction tried to add to a stack that doesn't exist."),
            |stack| stack.extend(popped_crates.into_iter().rev()),
        );
    }

    get_topmost_crates(crates)
}

Two things stand out:

stack.split_off()
stack.extend()

Vec::split_off() receives an index as an argument and takes all the elements from there on, returning them as a separate vector. The original vector is mutated and loses the elements. Because we're taking from the top, we count from the end, subtracting amount from the total length.

There's a problem with that, though. Imagine we want to take 2 crates, and the stack looks as follows:

C
B
A

Since we're taking them one at a time, we'd take C and then put B on top, leaving us with:

  B
A C

However, split_off grabs the elements all at once, giving us this:

  C
A B

That's why we use Extend::extend() (Extend being a trait Vec implements) to add the new crates in reverse order.

Part 2

Problem: Turns out, the crane works differently than expected. Instead of grabbing crates one at a time, it can handle many at once.

The expected result is now "MCD":

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

What this means is that the finessing we did at the end of Part 1, reversing the order of the new crates, is no longer necessary.

pub fn process_part_2(input: &str) -> String {
    let mut crates = parse_crates(input);
    let instructions = parse_instructions(input);

    for (amount, from, to) in instructions {
-       let popped_crates = crates.get_mut(&from).map_or_else(
+       let mut popped_crates = crates.get_mut(&from).map_or_else(
            || panic!("Instruction tried to take from a stack that doesn't exist."),
            |stack| stack.split_off(stack.len() - amount),
        );

        crates.get_mut(&to).map_or_else(
            || panic!("Instruction tried to add to a stack that doesn't exist."),
-           |stack| stack.extend(popped_crates.into_iter().rev()),
+           |stack| stack.append(&mut popped_crates),
        );
    }

    get_topmost_crates(crates)
}

Instead of extend(), which takes an iterator, we use Vec::append() and pass in a mutable reference to the vector. (Which is why it's declared mutable.)

That's it!

Got any suggestions for improvements? Feel free to share them below.

🦀 Solving with Rust: Advent of Code 2022 – Day 04

verified_tinker — Sun, 04 Dec 2022 06:15:56 +0000

View the code on GitHub.

See the entire, unedited problem on the Advent of Code website.

Sample input:

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

A more visual representation:

.234.....  2-4
.....678.  6-8

.23......  2-3
...45....  4-5

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

.2345678.  2-8
..34567..  3-7

.....6...  6-6
...456...  4-6

.23456...  2-6
...45678.  4-8

Part 1

Problem: Every line contains the sections—represented as ranges of unsigned integers—covered by a pair of elves. Calculate the number of instances where the range of one of the elves wholly covers the other's.

Let's break this down into two parts. First, we must extract the textual input into usable form. Checking for overlaps can come afterward.

use itertools::Itertools;

pub fn process_part_1(input: &str) -> usize {
    input
        .lines()
        .map(|line| {
            line.split(',')
                .map(|sections| {
                    sections
                        .split('-')
                        .map(|section_id| {
                            section_id
                                .parse::<u32>()
                                .expect("Section IDs should be unsigned integers.")
                        })
                        .collect_tuple()
                        .expect("Covered sections should be described with a '-'.")
                })
                .collect_tuple()
                .expect("Pairs of covered sections should be separated by a ','.")
        })
    // ...
}

Tedious but straightforward. Notice the use of collect_tuple(). That's a convenience function from the trait itertools::Itertools that lets us avoid calling .next().unwrap() on the iterator twice. Since Rust doesn't allow collecting into arrays, this is the best we can do (that I know of).

Now, it's time to move on to the actual problem. There are several ways to solve it, but let's make use of Rust's built-in ranges.

All we need to find out is how many times overlaps happen. Or, to simplify, we must count the number of elements that satisfy some condition. That's a big, fat hint right there, and it tells us, "Use filter() and count()."

pub fn process_part_1(input: &str) -> usize {
    input
        .lines()
        .map(|line| {
            line.split(',')
                .map(|sections| {
                    sections
                        .split('-')
                        .map(|section_id| {
                            section_id
                                .parse::<u32>()
                                .expect("Section IDs should be unsigned integers.")
                        })
                        .collect_tuple()
                        .expect("Covered sections should be described with a '-'.")
                })
                .collect_tuple()
                .expect("Pairs of covered sections should be separated by a ','.")
        })
+       .filter(|((min1, max1), (min2, max2))| {
+           (min1..=max1).contains(&min2) && (min1..=max1).contains(&max2)
+               || (min2..=max2).contains(&min1) && (min2..=max2).contains(&max1)
+       })
+       .count()
}

The use of collect_tuple() lets us pattern-match on the section IDs in the closure signature. All that's left is to check whether each section range contains the start and the end of the other.

Make sure that the ranges are inclusive—in other words, don't forget the = after the ...

Part 2

Problem: The same as before, except that partial overlaps should be included, too.

The only change we need to make is replace the and operators (&&) with the or ones (||). Everything else stays identical.

.filter(|((min1, max1), (min2, max2))| {
    (min1..=max1).contains(&min2)
        || (min1..=max1).contains(&max2)
        || (min2..=max2).contains(&min1)
        || (min2..=max2).contains(&max1)
})

Simple, right?

Got any suggestions for improvements? Feel free to share them in the comments.

⏳ Understanding Delta (Δ) Time In Games

verified_tinker — Sun, 25 Oct 2020 13:09:39 +0000

You're watching a tutorial on player movement. "...Multiply the speed by time dot delta time," they say, "so that it's consistent across varying framerates."

You're watching a tutorial on custom gravity. "...Let's not forget to add delta time here."

You're watching a tutorial on shooting bullets. "Divide the distance by time dot delta time, and..."

You're watching—

Okay, we get it! Movement needs delta time. Fine.

...But why?

🔒 Let's Work Through A Problem

We have a car, and we want to move it at a constant speed.

For simplicity's sake, let's forgo vectors and do things in one dimension: the number line. The car will start at position 0, and we want to increment that by 10 units every second.

🔑 Solution

We'll do that by directly adjusting the car's position—a common method when you want total control over its velocity, rather than entrusting it to the game's physics engine.

Let's say we create the Update() function and write the following: car.position += speed. We set speed to 10 and run the game, but the car's way faster than intended. We dial it down to 0.2.

Everything seems okay now. The car's cruising along, but then, there's a sudden drop in FPS, and it slows to a halt. A second later, it's all back to normal.

In single-player, you might not find this strange: the game freezes and so does the car. But if you were racing against someone else online—let's call her Sarah—who was adjusting her own car's position on her own computer and experienced no such spike, it'd appear as if you screeched to a stop. Sure, you pick your speed back up immediately, but now you've fallen behind her.

The problem with our code is that it's executed every frame. We're not setting the car's speed to 0.2 units per second; we're setting it to 0.2 units per frame.

The reason the car was blazing fast in the beginning, before we adjusted speed, is that the Update() function is called dozens of times each second. If the game runs at 50 FPS, it means the car goes at 500 units per second, rather than the 10 we originally intended. When the framerate dropped to near-zero, a whole second passed without the car moving.

Now imagine you're back to racing in multiplayer, but your PC's beefier than your opponent's. Your game runs at a whopping 100 FPS instead of fifty. While Sarah's trudging along at 10 units per second (0.2 * 50 = 10—remember, we set speed = 0.2), you leave her coughing up dust with your 20 units per second (0.2 * 100 = 20). Sure, it feels good, but it's not very fair.

This is where delta time comes in. Delta time is the time it took to render the frame. Another way to put it: delta time is the time period between last frame and the current.

Delta means "difference".

Assuming a consistent framerate of 50, delta time will always be 1 / 50 = 0.02 seconds per frame. How can we use this? It's the same thing we did in our high-school physics classes.

When we write car.position += 10 * Time.deltaTime, we write (10 units) * (0.02 seconds / frame), or 0.2 units * seconds / frame. Since the game runs at 50 FPS, why, that's the same as saying the following:

Frames and seconds cancel out, and 50 frames later, we're left with 0.2 * 50 = 10 units!

Of course, games rarely, if ever, run at a dead-steady FPS. But as framerate changes, so does delta time. Remember that sudden FPS drop you experienced? Since a whole second passed until the next frame, delta time in that next frame would be 1 second per frame—up from 0.02.

Instead of adding speed * 0.02 to the car's position, the game would add speed * 1, or 0.2. To your eyes, the car would appear to teleport forward after that spike, but that's how it would've moved if the spike had never happened in the first place, and you wouldn't fall behind Sarah.

Of course, now that we're scaling the speed with delta time, setting it to 0.2 would be awfully slow. That's because it represents the car's actual speed. We can set it to 10, confident the car will now always travel at 10 units per second, and not have to blindly grope for a value that "feels right".

➕ Additional Example

Once you understand this, you realize how much more you can do with it. For example, I recently worked on a mechanic where you drag a ball around with your cursor and, when you let go, the ball goes flying.

The problem is that the ball will not, on its own, go flying. All I'd done was disable the physics and make it follow the mouse cursor when clicked. The moment the player let go, the ball would just... stop. And then physics would kick in again and gravity would take it down.

As such, I had to measure its velocity the instant I let go and assign it manually. The problem is there's no such thing as speed or velocity at some particular instant. By definition, an object's velocity describes change; change in position. It's measured by the time it took to cover a certain distance (recall: v = S/t), and if there's no change, there's no velocity.

If you measure over, say, an hour, sure, you get a velocity, but it hardly describes the object at a particular instant. Rather, we want the time frame to be as short as possible.

The shortest we can get in games is how much distance the object covered in one frame. We record that, and the result is 0.2 units. So, its speed is 0.2 units per frame.

Unfortunately, the physics engine doesn't run on units per frame. It runs on units per second. We need to convert our number if we're to make use of it.

If we, again, assume a steady framerate of 50, delta time is 0.02 seconds per frame. We divide the 0.2 units per frame with 0.02 seconds per frame, giving us the following:

Ta-da! 10 units per second. Now we just have to assign it to car.velocity (or rigidbody.velocity, if you're using Unity).

❓ Question

Why'd we get a result in units in the first problem and in units per second in the 2nd?

✔ Answer

Because, in the first problem, we were changing the position. Every frame, we needed to find the correct distance to advance with, such that it added up to ten after one second.

In the second problem, we were assigning velocity; once, when the player let go. Ergo, we needed not just distance (units) but speed (units per second).