Question 2B - Bit String with Distinct Substrings
- Problem Sheet
- This is unavoidably a math question. First and foremost a lot of people had difficultly understanding the question. The goal is not to produce a (say) 36 bit number with 7 unique substrings tacked together, the goal is to produce a 36 bit number where every choice of 5 consectutive bits was different from every other choice of 5 consecutive bits. A lot harder, and I can't see a way of doing this without a full history of where you have previously exhausted your options (or paying a massive time penalty constantly recalculating that fact). The second thing that was hard about the problem is that you need to consider all n of your future substrings each time you make a choice between 0 or 1, otherwise you risk choosing a path that will later on require you to backtrack from. Using an actual tree is slightly slower, but allows for slightly larger numbers v.s. using a flattened tree implicitly stored in an array. I have also provided a couple of extra functions for double-checking an answer since 'human inspection' is clearly inadvisable.
- Sample Solution [input=>output] [input=>output]