Oh, you’re right. I will fix that in my post. Thank you!
1 Like
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
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()
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
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
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
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.)
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.
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.
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…
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).
Class Attendance
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.
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.
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.
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
I liked it. Also, I think we don’t have to make this “bit goal” explicit, nor talk about “disjoint” sets.
I like this story a lot. My only suggestion would be to maybe somehow “explain” why a bit set is used (to save space or perhaps as a curiosity or whatever).
Great work! Looking forward to implementing this.
2 Likes
With that example I get five sublists each with three elements for the longest continuous disjoint sublist, namely:
0 1 106
0 1 194
0 1 198
0 49 194
0 49 198
Do we want to catch all of those, or did I do a boo-boo ?
At first I wanted the length of the longest subarray of integers where no two elements have the same bit set to 1.
That’s what the tests and my example solution do.
| decimal | binary |
|---|---|
194 |
11000010 |
198 |
11000110 |
49 |
00110001 |
1 |
00000001 |
0 |
00000000 |
106 |
01101010 |
221 |
11011101 |
194 |
11000010 |
You can see that the three elements from 1 to 106 do not have the same bit set to 1. This subarray of length 3 is the longest subarray with that property.
In my story I switched 1 and 0 because I think marking the presence with 1 and the absence with 0 is more intuitive.
I will need to modify the tests and the example solution.
@siebenschlaefer are you still interested in moving forward with this exercise? I like it, and I think it would be a good addition.