Track update and mentor feedback request

Programming Rust
1

Hello fellow Rustaceans!

Recent developments

In the last couple of days, several PRs were merged on the Rust track. Most notably, there is a new exercise generator based on tera templates which allows flexible (re-)generation of tests based on problem-specifications. The goal is to stay up to date with problem-specifications without much effort. Applying this generator to all exercises derived from problem-specifications is my next task.

A big thank you to @AurelienFT, who has done some great work on the Rust representer, bringing it inline with the spec such that it actually starts working! And indeed, it looks like we can now give feedback on representations!

Mentors, I need your help

I’ve started contributing to Exercism by doing lots of mentoring. During that time, I had many ideas about how to improve the track, based on what students were struggling with. Now that all of the time I can dedicate to Exercism is spent on maintenance, I don’t have that input anymore.

Mentors, that’s were I need your help. Please don’t hesitate to post any ideas you have on the forum. I don’t need you to do the work, though you can if you want to. I’m happy to do the work myself as time allows. I just need your ideas. You can comment ideas you already have in this post, but also feel free to create new posts with ideas in the future.

I’m going to be a bit rude and individually tag a couple recently active mentors, because you may not receive notifications on this topic. (Some of them I can’t even tag, presumably because they never joined the forum :slightly_frowning_face:)

@bobahop @deleted-user-33691 @victorprokhorov @maugier

Apologies for any inconvenience, I won’t tag individuals in the future. Consider activating notifications for this topic if you would like to stay in touch. I’d love some active communication between maintainers and mentors. Here’s what I suggest:

Go to https://forum.exercism.org/u/<YOUR_USER_TAG>/preferences/tracking

Add the Rust topic to either “Tracked” or “Watching First Post”, according to your preference:

image
image827Ă—372 40.3 KB

(also make sure you get emails for forum notifications)

Not all post will be relevant to mentors, but right now it’s very calm. If the topic somehow becomes spammy from the perspective of mentors, let me know and we’ll find a solution.

Existing ideas for improvements

Now that I’m asking for your ideas, I should mention those that are already planned / on my mind.

I want to integrate clippy (and rustfmt?) in the analyzer. That should be an easy way to generate high-quality feedback for all exercises. I also remember posting my snippet about clippy in many mentoring sessions. I think that’ll be my focus after bringing the track inline with problem-specifications.

The syllabus, the elephant in the house. I don’t want to do that myself at the moment. I don’t see myself as a creative exercise writer and educator, more like a janitor that makes sure everything is up to date and working. Maybe in the future, when I’m done mopping the floor. However, I’m always open to supporting anyone who wants to work on this, on the condition that we can first agree on a mode of cooperation which is enjoyable for everyone.

I’m looking forward to making the Rust track as good as it can be together with you! :heart:

3 Likes
2

Minesweeper seems to be a popular exercise recently and my current solution uses what I think is a novel approach based on scan() to efficiently reuse mine counts across neighboring squares.

I’d be willing to write a “dig deeper” page for this exercise discussing this and some other common approaches if this would be useful and someone can tell me how to submit it and get it reviewed and accepted?

3

Would love that. Thanks :slight_smile:

These docs should explain things, and you can use this PR as a reference to copy.

Your PR will be automatically closed when you submit it. However, if you message again here (or ideally start a new thread), we’ll reopen it for you and get it reviewed/merged :slight_smile: Thanks for checking first!

4

Hi @mattnewport

I’d love that as well. Iirc, minesweeper gets lots of mentoring requests, so I imagine people would be very curious to read approaches.

I hope you’re ok with discussion the code a bit, since it will be shown to many users prominently.

I actually didn’t know about scan before, so I had to look into how that works exactly. I’m usually hesitant to use mutable state inside iterator adapters. In my experience, iterators are at their best when dealing with immutable data. for-loops are often simpler when dealing with mutability.

Your solution can also be written by letting map capture a mutable reference to a variable outside the iterator chain:

let mut st = [0, 0, vertical_mine_count(r, 0)];
(0..minefield[r].len())
    .map(|c| {
        st = [st[1], st[2], vertical_mine_count(r, c + 1)];

        (minefield[r].as_bytes()[c] == b'*')
            .then_some('*')
            .or_else(|| Some(" 12345678".as_bytes()[st[0] + st[1] + st[2]] as char))
            .unwrap()
    })
    .collect()

So I’m not yet convinced of the benefit of using scan.

That being said, your sliding three-element window of vertical mine counts is perhaps the most elegant way to solve this exercise efficiently I’ve seen. It reminded me of the windows method on slices, which doesn’t work here because we need an additional zero on both sides of a row. The itertools crate has a tuple_windows method, which allows us to get the desired behaviour without any mutation, for example:

let mine_counts = std::iter::once(0)
    .chain((0..minefield[r].len()).map(|c| vertical_mine_count(r, c)))
    .chain(std::iter::once(0))
    .tuple_windows()
    .map(|(l, c, r)| l + c + r);
(0..minefield[r].len())
    .zip(mine_counts)
    .map(|(c, m_count)| {
        if minefield[r].as_bytes()[c] == b'*' {
            '*'
        } else {
            " 12345678".chars().nth(m_count).unwrap()
        }
    })
    .collect()

What do you think?

5

(Just as a side note, having different approaches that use different methods is very welcome, even if there are tradeoffs each each - where there is “controversy” is where different approaches shine most. The introduction file can and should explain the pros/cons/tradeoffs between them)

6

I think scan / prefix sum is the right operation to use here. It is a useful building block for many algorithms and is available in many languages’ standard libraries, although it is less well known than some other similar higher order functions. Scan is essentially a fold that also produces all of the intermediate values as well as the final value.

The most straightforward use of scan is for going from a sequence of frequencies to a sequence of cumulative frequencies, but it also has a lot of use in graphics for e.g. stream compaction and also for filtering type of operations which is essentially what this exercise is. I think this is actually a nice exercise to introduce scan as a general purpose building block.

Scan doesn’t generally imply mutable state. For example in F#, the functional programming language I am most familiar with, the signature of Seq.scan is:

Seq.scan folder state source

folder : 'State -> 'T -> 'State
A function that updates the state with each element from the sequence.

state : 'State
The initial state.

source : 'T seq
The input sequence.

Returns: 'State seq
The resulting sequence of computed states.

I am a bit puzzled why Rust treats the state as mutable rather than having scan() return an Option<(State, Item)> or Option<State> but the semantics here are really those of scan() still.

The nice thing about scan is that it can be parallelized efficiently and several languages’ libraries support that. For example C++ originally just had partial_sum() but now has inclusive_scan and exclusive_scan as part of the parallel algorithms library.

GPUs also offer hardware support for parallel prefix sum that can be accessed via e.g. HLSL as WavePrefixSum because it is such a useful building block for graphics algorithms.

7

Yes, I think I’d cover at least the more common approach that maps the operation of counting mines in all 8 surrounding squares, or in the full 3x3 block (equivalent for this exercise) and then explain how the scan based approach optimizes that.

I think this can also be viewed as a separable filter problem but I need to work through a solution using that approach to confirm it applies here. Often this would be the most efficient approach but given the details of this problem it would likely require an extra allocation of an intermediate grid and so the scan based approach in my current solution is probably more efficient.

8

Note, the approaches doc isn’t necessarily about the “right” or “most efficient” or “best” solution. It’s a place where students can understand different various approaches with their varying trade-offs. The most efficient approach has a place among these approaches. If scan isn’t well known or widely used, that suggests it probably shouldn’t be the only approach discussed.

9

Great :slight_smile:

10

Yes, I think multiple approaches should be discussed here, at least the more common map version that looks at the 8 surrounding squares for each square as well as the approach using scan.

Scan is probably not as well known or widely used as fold but it is well known in certain domains like graphics which is where I was first exposed to it.

1 Like
11

Great, looks like there’s plenty of content here for the approaches :smiley:

1 Like
12

Is there an easy way for me to test my changes to see what the output will look like, that it appears in the right place, that links are working, etc.?

13

Feedback welcome on this draft.

14

(cc @ErikSchierboom)

15

My main feedback would be that the introduction is usually a relatively high-level overview that then links to individual approach documents to go into more detail. See https://exercism.org/tracks/csharp/exercises/poker/dig_deeper for more information. The information in the document is great though!

16

Not sure what the status is on this. Consider opening a PR, so we can see diffs, subscribe to updates, discuss inline etc.

17

Is there an easy way for me to test my PR so I can see what the generated pages will look like?

18

They’ll look like how the look in GitHub when submit the PR (ie the markdown render is the same).