[48in24 Exercise] [03-26] Sieve

Exercism 48in24
1

This issue is a discussion for contributors to collaborate in getting ready to be featured in 48in24. Please refer to this forum topic for more info.

We will be featuring Sieve from Mar 26 onwards.

Staff jobs

These are things for Erik/Jeremy to do:

  • :ballot_box_with_check: Check/update exercise in Problem Specifications
  • :ballot_box_with_check: Create + schedule video

Community jobs

For each track:

  • Implement Sieve
  • Add approaches (and an approaches introduction!) for each idiomatic or interesting/educational approach.
  • Add video walkthroughs (record yourself solving and digging deeper into the exercise).
  • Highlight up to 16 different featured exercises (coming soon)

Existing Approaches

You can use these as the basis for approaches on your own tracks. Feel free to copy/paste/reuse/rewrite/etc as you see fit! Maybe ask ChatGPT to translate to your programming language.

Track Statuses

You can see an overview of which tracks have implemented the exercise at the #48in24 implementation status page.

2

I’ll port for CoffeeScript, D, Groovy, Pyret, and Vim script.

1 Like
3

For this exercise’s video, I currently have these solutions and taling points. If you know more or better versions of these, let me know.

  1. C++: vector of booleans and nested for loop

Store the sieve in a vector of booleans and use a nested for loop to cross off multiples

  1. C#: BitArray

Use a BitArray to efficiently encode each “cross” as a single bit

  1. Julia: double comprehension

Use a double comprehension

  1. Python: set difference, with set of all numbers and set of multiples

Define all numbers and multiples as sets, and primes are the difference of these sets

  1. R: vector operation and optimized loop limits

Use vector operations to efficiently cross off numbers and reduce number of iterations

  1. F#: recursion with immutable list

Use manual recursion and immutability crossing off list from range

  1. Lua: coroutine

Compute and yield primes in coroutine, allowing execution to be suspended

4

@habere-et-dispertire has one of the most concise solutions I’ve seen for this, using a reduction with symmetric set difference.

e.g. 2..8 becomes (2,4,6,8) ⊖ (3,6) ⊖ (4,8) ⊖ (5) ⊖ (6) ⊖ (7) ⊖ (8).

1 Like
5

That is absolutely brilliant. I’m not sure I 100% understand the reduction. Are the elements being reduced in pairs, or as a whole?

I’m asking because I would think that:

(2,4,6,8) ⊖ (3,6) ⊖ (4,8) ⊖ (5) ⊖ (6) =
(2,4,8,3) ⊖ (4,8) ⊖ (5) ⊖ (6) =
(2,3) ⊖ (5) ⊖ (6) =
(2,3,5) ⊖ (6) =
(2,3,5,6)

I can see that if one were to reduce them all at once, it would produce the right result.

And just to be clear, keys converts the resulting set to a sequence, which is unsorted and thus requires sort too?

1 Like
6

The reduction happens as a whole. The symmetric set difference operator in Raku has list associativity, and reduce in Raku makes use of an operator’s identity value and associativity: Operators | Raku Documentation

All of the sets in the list end up as arguments to a single subroutine call. Parentheses would be necessary if you did want to group them in a certain way.

For example, Perl and Raku both have an xor operator, but Perl’s is left associative, and Raku’s is list associative. 1 xor 1 xor 1 is true in Perl, but false in Raku, because the Raku equivalent of Perl’s behaviour is (1 xor 1) xor 1.

Yes you have the right idea for the sort. Under the hood, a set in Raku is a map where the keys are the elements, and the values are True, and initially those keys are not sorted.

7

Great, then I understand.

8

Ported for LFE:

I’m planning on porting for Elm next

9

Oh, sorry @kahgoh , I stepped on your toes for Elm:

1 Like
10

All good @gleenj :wink: thanks for letting me know

11

attn @BNAndras

1 Like
12

For OCaml

1 Like