getFeedback function in O(k) time

Hello,
so i’ve been sitting on this problem for quite a while now.
I’m trying to calculate the array with the marks of each position and am stuck on the part that’s about assigning the WRONGPOS feedback result.
While I know how to code this part of the task i cannot figure out how to code it in linear time.
In the section “formal specification” there are indexes i, j and l used to describe what a WRONGPOS means so for that I might need even 3 for loops for that part which would most likely calculate the problem in O(k^3) time or at least O(k^2).
Can you give me any tips on how to approach this task?
Thanks in advance!

Tip zero would be to ignore the formal specification. It will not guide you towards an efficient algorithm :stuck_out_tongue:

Tip one would be to come up with two rather large (ie 10 to 15 character) words on paper, noting intermediary results, and trying to figure out the correct result. A working implementation (even if it is too slow) might help you double-check the on-paper results, to ensure that you know what you are doing.

If you do this often enough, you can maybe see some pattern you are repeatedly doing in the loop, that always computes the same or similar values. Perhaps you might even intuitively remember the last results for this subtask and not even do it anymore.

Once you recognize this, try changing the mental algorithm you are executing by explicitly writing down these sub-results and incorporating them into your algorithm.

For example, you could start with the example of having secret word ababababababab and user input cdabbabababacd. The correct solution is ⬛⬛🟩🟩🟨🟨🟨🟨🟨🟨🟨🟨⬛⬛, of course. Another didactically useful secret word for that guess could be ababababxyxyxy. Can you see a pattern?

Alternatively, inspiration can be taken from other seemingly impossible algorithms like sub-\!\mathcal O(n \log n) time sorting.

Hope this helps
Johannes

2 Likes