New exercise about bitwise operations

Exercism Building Exercism
1

A few days ago Erik encouraged us to add some new exercises.
Here’s an idea for an exercise about bitwise operations:

Integers can represent “bit sets” where each set/unset bit represents the presence/absence of a specific element.
Two integers (bit sets) bs1 and bs2 are “disjoint” if they do not have a common set bit, i.e. if bs1 AND bs2 is 0.
A list of integers is “disjoint” if all integers in the list are pairwise disjoint.

For example:

  • [1, 36, 18] is a disjoint list because the first bit (0b00_0001) is only set in the first element, the third and sixth bit (0b00_0100 and 0b10_0000) are only set in the second element, and the second and fifth bit (0b00_0010 and 0b01_0000) are only set in the third element.
  • [10, 12] on the other hand is not a disjoint list because the fourth bit (0b1000) is set in both elements.

Given a list of non-negative integers, find the longest continuous disjoint sublist.

For example:

  • In the list [222, 189, 148, 32, 144, 2, 0, 76, 26, 62] the longest continuous disjoint sublist is [32, 144, 2, 0, 76]
  • In the list [194, 198, 49, 1, 0, 106, 221, 194] the longest continuous disjoint sublist is [1, 0, 106]

This exercise can be solved in multiple ways:

  • with brute force, by testing all sublists.
  • greedily, by looping over the list and for each potential start of the sublist adding elements until a duplicate bit is found.
  • with a binary search, by “guessing” the length, trying to find a disjoint sublists of that length, and adjusting the bounds of the binary search accordingly.
  • with a sliding window, by looping over the list, narrowing the window on the left until the next element at the right can be included.

This fourth approach is the reason for this proposal, because it uses a combination of three bitwise operations: AND (to check if the window can be widened), OR (to actually widen the window and include an element), and XOR (to narrow the window and exclude an element).

This exercise is more on the algorithmic side but I think that’s just the consequence of aiming for a specific technique (bitwise operations). I’d say its difficulty is medium to medium-hard.

Open question: Do we want the exact sublist? And if multiple longest disjoint sublists exist, which one? Or do we just want the length of the longest disjoint sublist?

My biggest problem is coming up with a story that does not sound too artificial.
It needs a sequence of entities (people, objects, events, …), each with a subset of binary attributes.
It should make sense that we want to avoid duplicates and that we want a continuous sublist.

Here’s a braindump of ideas:

  • The daily meal in a cantina is made with a subset of ingredients (e.g. brokkoli and cheese on Monday, chicken and corn on Tuesday, pasta and chesse on Wednesday). Find the longest continuous span of days without a duplicate ingredient.
  • A gym offers daily course that train specific muscles or abilities (e.g. legs and endurance on Wednesday, flexibility on Friday, biceps and strength on Saturday). Find the longest continuous span of days with courses that do not train a muscle or ability twice.
  • You are part of a team of specialists with unique abilities. There’s a sequence of events with different requirements (e.g. Ben and Karen in week 1, Alexandra and Andrea in week 2, Eric and Aman in Week 3, Alexandra and Eric in Week 4). Find the longest interval that does not require one team member twice.

Edit: Fixed “non-positive”. Thank, Isaac

2 Likes
2

I like the disjoint part. The sublist part seems like it might have some overlap with the existing sublist exercise; it that an issue?

What does “non-positive” mean there?

3

The sublist part seems like it might have some overlap with the existing sublist exercise

In my experience the most common terms in similar contexts are “subsequence” (for an in-order selection of elements that are not necessarily contiguous) and “subarray” (for an in-order selection of contiguous elements).
Exercism does use the term “sublist” in one exercise (which is equivalent to “subarray”), so I chose to use that.

Otherwise this exercise doesn’t have much in common with the sublist exercise.

What does “non-positive” mean there?

Not negative, i.e. 0 or positive.

4

“non-positive” includes positive? Do you mean non-negative?

1 Like
5

Oh, you’re right. I will fix that in my post. Thank you!

1 Like
6

I’ll cross-post this from the exercise @tasx proposed…

When I’m evaluating exercises for myself, my main starting point is to write the code and then judge how easy/hard/elegant/interesting/etc the solutions can get. I then tend to backfill everything else based on that. Without the code, I feel like it’s really hard for me to evaluate how “good” at exercises is on the educational metrics.

So I’d love to see a solution (ideally in a high-level language - e.g. JS, Python, Ruby, C#, your QBasic one, etc) in order to get a feel for what this would look like. Ideally whatever solution you feel really shows off why it’s interesting etc.

2 Likes