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.
  • You’re teaching a class of high school students who are sick or absent from time to time. You store these absences in bitsets, one bitset per day, where each bit represents whether a specific student has been absent. You want to know the longest period in days in which no student has missed class twice or more.

Edit: Fixed “non-positive”. Thank, Isaac
Edit 2: added another possible story

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
7

I’ve written a Python version of the exercise, stripped down to the core, without any story.
First a stub with some tests for anybody who wants to try to solve it by themselves:

#! /usr/bin/env python3

import unittest


def longest_disjoint_sublist(bitsets: list[int]) -> int:
    """Determine the length of the longest disjoint sublist."""
    # TODO: your solution here
    # Happy coding!


class LongestDisjointSublistTest(unittest.TestCase):
    """Test the function `longest_disjoint_sublist`."""

    def test_empty_list(self) -> None:
        """The longest sublist of an empty list is empty."""
        self.assertEqual(longest_disjoint_sublist([]), 0)

    def test_single_element(self) -> None:
        """Any list of length 1 is disjoint."""
        self.assertEqual(longest_disjoint_sublist([23]), 1)

    def test_two_equal_non_empty_bitsets(self) -> None:
        """Two equal non-empty bitsets are not disjoint."""
        self.assertEqual(longest_disjoint_sublist([10, 10]), 1)

    def test_two_bitsets_with_one_common_bit(self) -> None:
        """Two bitsets with a common set bit are not disjoint."""
        self.assertEqual(longest_disjoint_sublist([39, 28]), 1)

    def test_two_bitsets_without_common_bit(self) -> None:
        """Two bitsets without a common set bit are disjoint."""
        self.assertEqual(longest_disjoint_sublist([21, 42]), 2)

    def test_all_bitsets_disjoint(self) -> None:
        """If all bitsets have unique set bits the whole list is disjoint."""
        self.assertEqual(longest_disjoint_sublist([1, 32, 2, 16, 4, 8]), 6)

    def test_longer_list_with_short_disjoint_sublists(self) -> None:
        """A list with multiple disjoint sublist of length 2."""
        bitsets = [
                854, 798, 768, 32, 733, 416, 342, 447, 302, 382, 968, 739, 51,
                934, 852, 0, 100, 1020, 0, 76, 373, 83, 0, 1023, 1023, 256,
                500, 511, 192, 582]
        # all distjoint sublists of length 2:
        # [768, 32]
        # [32, 733]
        # [852, 0]
        # [0, 100]
        # [1020, 0]
        # [0, 76]
        # [83, 0]
        # [0, 1023]
        self.assertEqual(longest_disjoint_sublist(bitsets), 2)

    def test_longer_list_with_shorter_disjoint_sublist(self) -> None:
        """A list with one disjoint sublist of length 4."""
        bitsets = [
                8, 272, 329, 8, 86, 828, 80, 16, 202, 10, 8, 40, 428, 8, 32,
                1, 317, 1, 16, 0, 973, 1, 4, 2, 769, 120, 64, 321, 136, 881]
        # longest disjoint sublist: [4, 2, 769, 120]
        self.assertEqual(longest_disjoint_sublist(bitsets), 4)

    def test_longer_list_with_long_disjoint_sublist(self) -> None:
        """A list with one disjoint sublist of length 8."""
        bitsets = [
                256, 256, 9, 72, 16, 80, 4, 128, 64, 16, 128, 1, 128, 32,
                0, 0, 64, 16, 6, 64, 16, 1, 128, 64, 132, 512, 1, 4, 16, 2]
        # longest disjoint sublist: [1, 128, 32, 0, 0, 64, 16, 6]
        self.assertEqual(longest_disjoint_sublist(bitsets), 8)

    def test_long_list_with_long_disjoint_sublist(self) -> None:
        """A list with one disjoint sublist of length 7."""
        bitsets = [
                1, 538, 63, 510, 1023, 0, 0, 64, 718, 900, 989, 635, 128, 828,
                4, 0, 0, 167, 256, 570, 895, 0, 417, 1022, 788, 128, 0, 0, 33,
                578, 0, 8, 1023, 144, 33, 386, 608, 1015, 260, 2, 0, 959, 0,
                144, 0, 288, 767, 292, 64, 1023, 0, 1022, 991, 1018, 310, 368,
                733, 959, 356, 764, 269, 507, 1021, 834, 394, 0, 503, 940, 991,
                1022, 5, 352, 1007, 336, 666, 667, 512, 97, 19, 828, 767, 641,
                517, 592, 640, 364, 1023, 4, 285, 229, 281, 511, 1006, 767, 0,
                503, 678, 141, 195, 128, 14, 283, 951, 12, 0, 447, 1021, 575,
                0, 0, 0, 962, 8, 763, 0, 385, 0, 1023, 540, 768, 979, 242, 773,
                782, 621, 4, 1019, 751, 409, 430, 895, 274, 146, 105, 414, 596,
                8, 0, 495, 336, 421, 727, 1023, 1, 81, 987, 971, 991, 215,
                1019, 256, 256, 745, 32, 550, 849, 1023, 332, 0, 950, 521, 119,
                0, 877, 1023, 4, 1023, 0, 313, 957, 605, 0, 987, 66, 36, 367,
                32, 1023, 693, 32, 791, 991, 885, 445, 0, 917, 500, 1007, 703,
                8, 1023, 580, 1, 24, 731, 514, 468, 284, 918, 72, 271, 102,
                762, 817, 635, 425, 518, 988, 331, 235, 0, 383, 859, 1023, 858,
                2, 36, 64, 1023, 0, 0, 509, 289, 503, 969, 1015, 0, 609, 1022,
                991, 1, 581, 478, 312, 100, 0, 959, 128, 502, 144, 192, 3, 767,
                117, 1, 255, 324, 206, 629, 735, 511, 1023, 6, 201, 580, 774,
                832, 579, 657, 392, 16, 821, 726, 949, 4, 667, 660, 386, 999,
                959, 26, 711, 186, 518, 0, 147, 1007, 1023, 225, 133, 937, 437,
                305, 35, 767, 937, 973, 511, 299, 10, 1021, 515, 766, 132, 782,
                72, 957, 383, 0, 516]
        # longest disjoint sublist: [128, 0, 0, 33, 578, 0, 8]
        self.assertEqual(longest_disjoint_sublist(bitsets), 7)


if __name__ == '__main__':
    unittest.main()
8

Here’s my implementation of the solution:

def longest_disjoint_sublist(bitsets: list[int]) -> int:
    """Determine the length of the longest disjoint sublist."""
    max_len = or_sum = first_idx = 0
    for last_idx, bs in enumerate(bitsets):
        while or_sum & bs:
            or_sum ^= bitsets[first_idx]
            first_idx += 1
        or_sum |= bs
        max_len = max(max_len, last_idx - first_idx + 1)
    return max_len
9

Could this build off problem-specifications/exercises/allergies/description.md at main · exercism/problem-specifications · GitHub in some way? We’re using bitwise operations there so this could be some sort of validation effort across multiple tests from the same individual. So we’d have Allergies and Allergies (Extended?) like how Resistor Color, Resistor Color Duo, and Resistor Color Trio are interconnected.

2 Likes
10

Given how similar the resistor exercises, I personally find it more annoying than helpful that I need to replicate my solution in multiple places. I think I’d personally find this exercise as an independent exercise. Though others may feel very differently.

2 Likes
11

I thought, I might be imagining, that there was now a way to create “libraries of your code” that you can require across exercises now… that might alleviate part of that “multiple replication of solutions”.

I did see something related to this in someone’s replication repository where they had created a single file to include when they wanted to skip all the tests, so that they could stop writing it in every file (I suspect they also practice locally, though.)

12

Okay, how about we do the gym exercise framing device then? That’s fairly different from other exercises, which isn’t a requirement, but it would hopefully draw a student’s eye.

13

This proposed exercise and the “allergies” exercise both use bitsets but different aspects of them.

Solutions of the “allergies” exercise operate on a single bitset and on single elements (i.e. bits), create a bitmask (with a bitwise left-shift), they test whether a bit is set (with a bitwise AND) and extract all “elements” (with bitwise left- or right shifts and a bitwise AND).

To solve this exercise efficiently you need to operate on multiple bitsets, compute their intersection (with bitwise AND), their union (with bitwise OR) and their difference (with bitwise XOR or a combination of bitwise AND and bitwise NOT).

To me that’s different enough to make this a separate exercise. But that’s just a soft preference, I’m OK with making this a “part 2” of the “allergies” exercise if a majority of comments wants that.

14

For me the story is the hardest part. It has to make sense that we want to search for the longest continuous sequence of bitsets without a repeating bit.
Of my four ideas that I listed above I like the one with the teacher the most. But perhaps somebody else has an idea…

15

Is there (or could there be) some restrictions on the integers as a bitset abstraction? It might be that each integer represents a week (5 bits, possibly 6 if there’s a class at the weekend). Or a month (at most 31 bits).

16

Class Attendance

teacher

You’re teaching a class of high school students who are sick or absent from time to time. You store the attendance in bit sets, one bitset per day, where each bit represents whether a specific student has been present.

For example yesterday’s bitset might be 0b10110111 (decimal value 183) where the bits #0, #1, #2, #4, #5, and #7 (from the left) are set. That means six students were present, students #3 and #6 were absent.

     #7   #6   #5   #4   #3   #2   #1   #0
┈──┬────┬────┬────┬────┬────┬────┬────┬────┐
 … │  1 │  0 │  1 │  1 │  0 │  1 │  1 │  1 │
┈──┴────┴────┴────┴────┴────┴────┴────┴────┘

After a while you notice that your students miss class quite often and you start analyzing the attendance records.

For example, last week’s attendance records might look like this:
[80, 40, 119, 62, 111]
In binary notation that’s
[0b1010000, 0b0101000, 0b1110111, 0b0111110, 0b1101111].
And in a spreadsheet it might look like this:

#6 #5 #4 #3 #2 #1 #0
Monday 1 0 1 0 0 0 0
Tuesday 0 1 0 1 0 0 0
Wednesday 1 1 1 0 1 1 1
Thursday 0 1 1 1 1 1 0
Friday 1 1 0 1 1 1 1

Now you want to know the longest period (in days) in which no student has missed class twice or more.

In the example above, from Wednesday to Friday each student was absent at most once. That’s a 3-day streak.

17

I’m not sure I understand the question.
My idea was one bitset per <time_period>, each bit represents the presence/absence of a specific element.

18

Ah, sorry, I misinterpreted. I thought that the bitset represented the attendace of a single student over time (each bit a day). But the bitset represents the attendace of the whole class (each bit a student).

But, in your example, if a bit set represents a student’s presence and if the sequence must not have the same bit set more than once, aren’t you looking for the longest sequence where no student was present more than once?

From wednesday to friday, numbers are not disjoint. For instance, bit 2 is set in all of those days.

Loved the exercise, by the way.

19

But, in your example, if a bit set represents a student’s presence and if the sequence must not have the same bit set more than once, aren’t you looking for the longest sequence where no student was present more than once?

This exercise started with an abstract idea: Find the length of the longest subarray of integers where no two elements have the same bit set to 1.

When I wrote the story about the attendance record it felt weird storing the absence of a student as 1 and their presence as 0, so I switched set and unset bits.

So now the task has become: Find the length of the longest subarray of integers where no two elements have the same bit set to 0. That a little bit less elegant but IMHO it makes more sense in the context of the story.

What do you think?

1 Like
20

I liked it. Also, I think we don’t have to make this “bit goal” explicit, nor talk about “disjoint” sets.