Need help reworking the saddle-points exercise introduction/instructions

Exercism Building Exercism
1

This is part of the exercise overhaul described here:

Basically for each exercise, we want to make sure that it is in the context of a story. Not an elaborate story, but something that helps you imagine a concrete scenario and make it just a bit more interesting.

As an example, instead of just “figure out if a sentence is a pangram”, we reframed the exercise to give a reason why you need to do this (you work for a company that makes fonts, and they want to use pangrams to show off the fonts on their website. https://github.com/exercism/problem-specifications/pull/2215).

I’ve been looking at the saddle-points exercise, and I’m a bit stumped, to be honest.

It seems like saddle-points can be used in optimization problems, so I’m trying to frame a story around a logistics/transportation company needing to do some optimization on their routes.

Here’s my current suggestion:

You work for a transportation company that needs to improve the efficiency of their routes.

You have been tasked with developing a program that can help the company identify routes that are problematic. These are locations where there is no optimal solution based purely on distance. The routes through these areas can then be analyzed by experts in the company, to find better solutions.

However, I have no idea if I’m even close to being right about this whole thing.

If someone could help me get this right, I would appreciate it very much.

For context, here are the tweaked instructions:

Your task is to find the saddle points in a matrix representing distances between cities.

A saddle point is a point where the surface curves up in one direction and down in another direction.
The saddle point isn’t the lowest point overall, nor is it the highest point overall.
It represents a point where there is no good solution.

In a matrix, a saddle point is an element that the largest in its row, while being the smallest in its column.

You may find other definitions of matrix saddle points online.
The tests for this exercise follow the above unambiguous definition.

A matrix might not have any saddle points at all.
Or it might have one, or even several.

Here is a matrix that has exactly one saddle point.

    1  2  3  4
  |-----------
1 | 9  8  7  8
2 | 5  3  2  4  <--- saddle point at row 2, column 1, with value 5
3 | 6  6  7  1
  • Row 2 has values 5, 3, and 1. The largest value is 5.
  • Column 1 has values 9, 5, and 6. The smallest value is 5.

So the point at [2, 1] (row: 2, column: 1) is a saddle point with value 5.

2

May I suggest a different approach, something like this:

Alice has access to a rectangular park, with trees of different heights planted at regular intervals. The heights of the trees are given to you as entries in a rectangular matrix.
She wants to build a tree house atop one of the trees, but because she likes sunsets and sunrises very much, she doesn’t want any other tree blocking her view to the east and to the west.
At the same time, she doesn’t like climbing too much, so she wants to pick a tree that is shortest among all the trees to the north and to the south.
Can you help her find all potential trees that are tallest in the east-to-west direction, while at the same time are shortest in the north-to-south direction.

5 Likes
3

That is waaaay better. Thank you!

4

That’s lovely @dreig!

5

I think that making it all about a story is much better because I don’t think it’s really connected to the optimisation idea of saddle points.

I posted about this on math overflow, but didn’t attract any expert answers to find out if I was wrong or not.

1 Like
6

Yeah. I’m wishing that all our stories were as concrete (dare I say) obvious-in-hindsight as the tree house story for saddle-points.

This went from an exercise that I felt really meh about, to being an exercise that I think is really nice.

1 Like
7

These improvements look great, folks. Thank you.

While looking at the R track, I found that the formatting was a little skew-whiff and put up a PR to improve it (saddle-points: Improve instructions by johnsyweb · Pull Request #250 · exercism/r · GitHub). While I was there, I spotted a couple of minor errors that could use tweaking across the tracks. Let me know if you’d like me to make any changes to the PR and whether you’d like me to replicate it for all the other tracks.

Cheers!

8

Thanks so much for picking this up! I’m happy with the corrections as proposed, so am going to accept them as is, but obviously also keen to align with any synchronised changes to all tracks based on what’s agreed upon here later.

9

Ah sorry, actually just seen that these problems were addressed in the upstream problem-specifications repo but these updates haven’t yet been sync’d to all tracks.

10

PR opened to remove the duplicated word here: Update instructions.md by jonmcalder · Pull Request #2279 · exercism/problem-specifications · GitHub

1 Like
11

Thanks Jon for publishing my fix to the R track and for the PR to remove the repeated word from the repository for practice exercises to be used across tracks this is much appreciated and I’ll know to check this repository first for any future changes.

As an aside, I wonder whether the markdown version of the grid is more accessible to screen-readers then the version using a code block.

:bowing_man:

12

Yes I did wonder about this too but don’t feel strongly about it. If you do, my suggestion is to start a new topic here on the forum to discuss it. The original issue raised in this topic (thread) has been addressed so it’s not a good place to discuss it further - I only found my way here because your PR to the R track alerted me to it.

You could also open an issue (or PR) on the problem-specifications repo but note that PR’s to that repo require 3 approving reviews and may not be accepted if there isn’t clear consensus about what is preferred.

Thanks again for picking this up and for your contributions so far!

1 Like