Exercise idea - calculate PI using map/reduce

Exercism
1

Disclaimer: I’ve written a blog post which contains a solution to this problem in Java and Kotlin

I have an idea for an exercise: calculate PI using the Leibniz formula for π. The implementation should be done using map/reduce.

I’ve been trying to find a good example of using map/reduce and thought this would be nice since it does exactly what I was looking for: using the previous result to calculate the next one.

I have two questions:

  1. What do you think? Is it a good or bad idea?
  2. What should be my next step, should I create a PR in problem-specifications? Is there some kind of procedure I should follow otherwise?
2

The tests could look like this (kotlin):

    @Test
    fun millionIteration() {
        val computedPi = Pi.compute(1_000_000)
        assertEquals(PI, computedPi, 1e-6) // about 3.141593
    }
3 
-- Haskell solution
leibnizEstimate terms =
  abs $ foldl' (\acc n -> 4 / fromIntegral n - acc) 0 [1, 3 .. 2 * terms]

# Python solution
def leibniz_estimate(terms):
    return abs(reduce(
        lambda acc, n: 4 / float(n) - acc,
        range(1, 3, 2 * terms)
    ))

The expected solution either

  • does not use map but does use foldl/reduce, or
  • does use map but uses sum instead of foldl/reduce.

Also, it uses either iterate or a range.

4

You can certainly use map/reduce but it’s probably not going to the best approach since there’s no given collection to iterate over (can’t access the article so i might be wrong). Also, constructing a collection costs. So if the language provides a standard for loop which is faster i would probably pick that instead. If not, then i would be looking into map/reduce.

5

In kotlin and java you create an infinite sequence and then take the number of requested iterations. Then you use that when reducing.

6

The canonical problem sets pretty much all define black box behavior. “This input produces that output.” Very few exercises mandate specific approaches (map, fold). Some exercises suggest specific approaches, but rarely do tracks do any enforcement.

Are you proposing a problem where map/reduce is somehow actually enforced? Or is this a “calculate Pi” exercise with a suggestion that students consider using a specific approach? Or are those the same thing?

7

I guess it could be a suggestion though it looks like the natural strategy in my eyes

8

So I started sketching on a problem specification but I wonder how I should specify the expected value from each test, since it expects a decimal number within an interval, so for example with ten iteration, the solution should be π +/- 0.1, and for a hundred iterations it should be π +/- 0.01.
So should I write: “expected”: “π +/- 0.01”?

1 Like
9

Or maybe simply the expected distance:
“expected”: “0.01”

Then what should the property be? “distance”?

10

Hello. Thanks for opening a PR on Exercism. We are currently in a phase of our journey where we have paused community contributions to allow us to take a breather and redesign our community model. You can learn more in this blog post. As such, all issues and PRs in this repository are being automatically closed.

Didn’t realize that :(

11

That’s not to say we don’t take contributions at all for problem-specifications though! We do encourage discussion first here on the forum. Maybe others could chip in too?

12

To soft-enforce use of Leibniz’s approximation, you can check that the estimates fall within certain envelopes: for any given number of used terms the error is guaranteed to be less than some upper bound and greater than some lower bound.

13

My opinion on the matter: The PR includes the implementation as a requirement. Once again, I think the requirement should reflect the required input and output, and should not include the implementation. I think the implementation can be a strong recommendation but, unless you can somehow enforce it via tests, should not be listed as a requirement. The exercise should be “Compute Pi” and the prose can suggest using a specific approach for doing so.

I’m curious to hear what other maintainers think about this.

14

You can find the PR here in case you’re interested

15

I have three general top-of-the-head thoughts:

  1. If the hope is that a student completes it in a certain way in a certain track, details of that implementation can be added to that track’s “append” file. I think that’s more appropriate than in the PS version.
  2. Demonstrating a specific implementation is a perfect thing to create an Approach for and put on the Dig Deeper tab.
  3. If the decision was to have extra tests for a specific implementation, these should definitely be a scenario (paired with the append above). But I’m generally uncomfortable with this as a thing, because I’d rather allow a student try and solve it one way and then compare that to the map/reduce method and understand why map/reduce is a thing.

So I’d encourage a track-specific append (with a hint to try map/reduce as one interesting method) and an Approach (and maybe accompanying video on map/reduce approach!) as the way to resolve this.

1 Like
16

We’re in the process of overhauling all the problem specifications. (For context see [New Project] Making Practice Exercises more consistent and human across Exercism)

One of the things we are trying to do for each exercise is to provide a story to help frame the exercise and make it more concrete, approachable, and interesting. Not a great work of fiction, just a bit of context.

As an example, the pretext for pangram is that a company that sells fonts is running a competition to create pangrams that they can use to demonstrate the fonts on their site. The pretext for word count is that an English as a Second Language teacher is doing frequency analysis on subtitles from TV shows so that they can base their curriculum on gradually more challenging shows.

The mathy exercises have been much more challenging to work out decent stories for, and I really don’t want to have to reverse engineer something after the fact.

As such I would like to see some suggestions for stories/pretext before deciding whether or not to add this exercise.

17

Challenge accepted!

Maybe I can borrow something from Liu Cixin’s “To Hold Up The Sky”:

A breed of aliens is in the process of destroying stars to isolate an enemy. While deciding if a star should be destroyed or not, they look for intelligent life forms in the star’s system. If such is found, and the species are intelligent enough, they might reconsider leaving the star intact. To evaluate their intelligence, one of the tests they give those life forms is whether they can calculate Pi to an adequate number of decimals. The aliens have now approached you and it is up to you to save the world! If you fail, the consequences are devastating.

Suddenly, you remember Leibniz formula for Pi, an easy way to calculate Pi to a certain degree of precision. Now go write a function using that formula and remember: the future of the world depends on your success!

1 Like
18

Math-y and algorithm-y stories are tricky. (I’ll readily admit that I don’t love any of the ones I’ve come up with so far).

The word “story” might be the problem here. What we’re really aiming for is a wee bit of colorful context that helps make the exercise concrete.

For an example of where I was struggling and @dreig came to the rescue, see this thread: Need help reworking the saddle-points exercise introduction/instructions

Here, the story about the park with trees of different heights and a trade-off that is reasonable to imagine hits the perfect amount of story, to my mind.

Can you think of a more down-to-earth story for this particular approximation of Pi?

My gut sense is that if we don’t have a story that hits the right note, I’d prefer to not add it as an exercise.

1 Like
19

Also note Jeremy’s note about not making the specific implementation part of the requirement.

20

Yeah, I agree, it’s hard to find a down-to-earth-y excuse for having to calculate Pi to the nth decimal. We can skip that exercise if that is required.

1 Like