Monday, March 6, 2017

Day 52

Current Challenge: No repeats please
Progress: I've been pretty busy the last couple of days and hence hadn't much time to make real progress. However, I figured how to pass the "No repeats please" challenge by just using some combinatorics but could not manage to generalize the idea, which really caused some frustration. Unfortunately, I found this article on StackOverflow only after I already figured it out myself, which could have saved me quite some time spent on thinking. Still, one major issue remains: finding a generalizable formula that handles both an arbitrary set of repeating and non-repeating characters, like "aaabbbbcccccdeffg" for instance. The solution to the problem can be abstractly described as "TOTAL - INVALID + OVERLAPS".

As long as we only have one character set with just one repeat, we are done after subtracting the INVALIDs from the TOTALs.

"aab": 3! - (2! * 3!) = 2

"abcdefa": 7! - (2! * 6!)  = 3600

If more than one character set with repeating letters is occurring we have to take care of the OVERLAPS as well since we deduct some permutations twice (or more) when subtracting the INVALID ones:

"aabb": 4! - (2! * 3!) - (2! * 3!) + (2! * 2! * 2!) = 8

"abfdefa": 7! - (2! * 6!) - (2! * 6!) + (2! * 2! * 5!) = 2640

Things start to get hairy if you have something like "aabbccd", i.e. more than two character sets with repeating letters since you have to add back all the overlaps, which are not as easy computable as above.

The same goes for character sets with more than 2 repeats like "aaab". Those two issues combined, say we have something like "aaaabbbccd", is way too complicated to grasp at the moment due to the different grouping possibilities you have to account for. If I'm trying to compute it manually I'm sometimes right but more often than not wrong. The thing I can't get my head around is recognizing a pattern.

Thoughts: For now, since I haven't made any real progress and it continues to discomfort me, I'll focus on just passing the tests with the next best algorithm I come up with.

My takeaway from this challenge is that I spent way too much time on figuring something out I'm not supposed to. But it has been nagging me ever since I had the idea of a somewhat "universal" formula, where you can just toss in the letters and it outputs the correct number, especially because seemingly no one on FreeCodeCamp has managed to solve it in this manner yet. I'm still convinced that there is a way but I've to put it back for the sake of my actual goal, learning to code.

My plans for the next days:
  • Work through the remaining "Advanced Algorithm Scripting" challenges
  • Finish chapter 9 on Regular Expression (including exercises; 'Eloquent JavaScript')
  • Gradually upload my work on GitHub

Follow me on GitHub

Follow me on FreeCodeCamp

Follow my Pens on Codepen

No comments:

Post a Comment