Assuming 2 units of time the sequence our possible responses are as follows:<\/p>\n
![\"sig-1\"](\"\/wp-content\/uploads\/2017\/04\/sig-1.gif\")
<\/p>\n
The software that controls our device will automatically stop in any one of the\u00a0 following conditions:<\/p>\n
- \n
- Received two Failures at any time<\/li>\n
- Received three consecutive corrupted data<\/li>\n<\/ul>\n
Based on this definition the sequence for 2 units of time the possible valid signals are 8 :<\/p>\n
![\"sig-2\"](\"\/wp-content\/uploads\/2017\/04\/sig-2.gif\")
<\/p>\n(Note that the FF sequence has been dropped)<\/p>\n
To make our requirement cleaner assuming 3 units of time the sequence of valid signals (19) will be the following:<\/p>\n
![\"sig-3\"](\"\/wp-content\/uploads\/2017\/04\/sig-3.png\")
<\/p>\nNote that the following 8 signals are dropped:
\n![\"sig-4\"](\"\/wp-content\/uploads\/2017\/04\/sig-4.png\")
<\/p>\n<\/p>\n
Our problem is the following:<\/p>\n
For a given number of units of time calculate the count of all possible valid sequences of signals<\/strong><\/em><\/p>\n
The Brutal Solution<\/h2>\n
At this point you should pause and re-read the definition of the problem and try to digest it.<\/p>\n
We already have the following test data:<\/p>\n
\n\n
\n Units of time<\/th>\n Number of sequences<\/th>\n<\/tr>\n \n 1<\/td>\n 3<\/td>\n<\/tr>\n \n 2<\/td>\n 8<\/td>\n<\/tr>\n \n 3<\/td>\n 19<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n Simply be noticing that each new sequence multiplies the existing signals by a factor of 3 for each Success, Failure and Corrupted message received we can easily code a brutal force solution which for each new time unit creates the new sequences and drops those ending with three corruptions or containing two failures at any point. Using our test data our brutal solution looks like the following:<\/p>\n
\r\ndef count_sequences_brutal(units_of_time):\r\n sequences = ['S', 'F', 'C']\r\n for i in range(1, units_of_time):\r\n new_sequences = []\r\n for sequence in sequences:\r\n for c in 'SFC':\r\n new_str = sequence + c\r\n if 'CCC' in new_str or new_str.count('F') >= 2:\r\n continue\r\n new_sequences.append(new_str)\r\n sequences = new_sequences\r\n return len(sequences)\r\n\r\n\r\nassert count_sequences_brutal(1) == 3\r\nassert count_sequences_brutal(2) == 8\r\nassert count_sequences_brutal(3) == 19\r\n<\/pre>\nNow that we have a correct solution in place lets try to see how efficient it is in terms of performance as the number of time units is increasing:<\/p>\n
Running the following code:<\/p>\n
\r\nimport timeit\r\nimport functools\r\n\r\nfor time_units in [2, 3, 6, 10, 20, 25]:\r\n print(\r\n 'time_units:', time_units, 'duration:',\r\n timeit.timeit(stmt=functools.partial(count_sequences_brutal, time_units), number=1)\r\n )\r\n<\/pre>\n
We are getting the following output:<\/p>\n
![\"sig-5\"](\"\/wp-content\/uploads\/2017\/04\/sig-5.png\")
<\/p>\nNote how quickly the\u00a0 running time grows; for 10 unit times 0.006 seconds are required but for 25 we are reaching more than 89 seconds!<\/p>\n
Obviously our brutal force algorithm is terrible in terms in performance as it big O complexity is exponential. It still can be helpful for us since we create the following testing data that we will use later to test our efficient algorithm:<\/p>\n
\n\n
\n Units of time<\/th>\n Number of sequences<\/th>\n<\/tr>\n \n 1<\/td>\n 3<\/td>\n<\/tr>\n \n 2<\/td>\n 8<\/td>\n<\/tr>\n \n 3<\/td>\n 19<\/td>\n<\/tr>\n \n 4<\/td>\n 43<\/td>\n<\/tr>\n \n 5<\/td>\n 94<\/td>\n<\/tr>\n \n 6<\/td>\n 200<\/td>\n<\/tr>\n \n 7<\/td>\n 418<\/td>\n<\/tr>\n \n 8<\/td>\n 861<\/td>\n<\/tr>\n \n 9<\/td>\n 1753<\/td>\n<\/tr>\n \n 10<\/td>\n 3536<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n Analyzing the problem<\/h2>\n
At this point we have enough data and understanding of our problem so we can analyze it further and try to discover some hidden tricks that might allow us to come up with a smart algorithm that will solve it efficiently.<\/p>\n
Thinking about our problem we can see that all of the following statements are all correct about a valid sequence:<\/p>\n
- \n
- Ends with one of the letters S<\/strong> F<\/strong> C<\/strong> or CC<\/strong><\/li>\n
- Contains none or a single failure F<\/strong><\/li>\n
- Does not contain a CCC<\/strong> sub-sequence<\/li>\n<\/ul>\n
Each iteration goes through all of the previous sequences and for each of them creates three new sequences appending the S<\/strong> F<\/strong> C<\/strong> to its end; as this happens some of them will be rejected as invalid due to the rules we have defined above as can be seen in this picture:<\/p>\n
![\"sig-7\"](\"\/wp-content\/uploads\/2017\/04\/sig-7.gif\")
<\/p>\nHaving said this, we can express the count of valid sequences at any point by adding up the following counters:<\/p>\n
\n\n
\n Counter Name<\/th>\n Description<\/th>\n<\/tr>\n \n FS<\/strong><\/td>\n exactly one F<\/strong>, ending with S<\/strong><\/td>\n<\/tr>\n \n FC<\/strong><\/td>\n exactly one F<\/strong>, ending with C<\/strong><\/td>\n<\/tr>\n \n FCC<\/strong><\/td>\n exactly one F<\/strong>, ending with CC<\/strong><\/td>\n<\/tr>\n \n S<\/strong><\/td>\n no F<\/strong>, ending with S<\/strong><\/td>\n<\/tr>\n \n C<\/strong><\/td>\n no F<\/strong>, ending with C<\/strong><\/td>\n<\/tr>\n \n CC<\/strong><\/td>\n no F<\/strong>, ending with CC<\/strong><\/td>\n<\/tr>\n \n F<\/strong><\/td>\n ending with F<\/strong><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n If we could calculate these counters for each iteration using their previous value our solution could have become very fast as only one pass would be sufficient to solve the problem and this exactly what we will try to do next.<\/p>\n
The algorithmic solution<\/h2>\n
After the first time unit our sequences look as follows:<\/p>\n
![\"sig-6\"](\"\/wp-content\/uploads\/2017\/04\/sig-6.gif\")
<\/p>\nwith the following counters:<\/p>\n
\n\n
\n Counter Name<\/th>\n Count><\/th>\n<\/tr>\n \n FS<\/strong><\/td>\n 0<\/td>\n<\/tr>\n \n FC<\/strong><\/td>\n 0<\/td>\n<\/tr>\n \n FCC<\/strong><\/td>\n 0<\/td>\n<\/tr>\n \n S<\/strong><\/td>\n 1<\/td>\n<\/tr>\n \n C<\/strong><\/td>\n 1<\/td>\n<\/tr>\n \n CC<\/strong><\/td>\n 0<\/td>\n<\/tr>\n \n F<\/strong><\/td>\n 1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n Adding all counters we get 3 which matches the valid signals we have so far.<\/p>\n
The second time unit will append each or the S F C to each of the existing sequences, creating 9 possible combinations.<\/p>\n
Since we already have broken down the existing sequences based on the rules of the problem, instead of creating all the combinations we can now use the known information to increase all the available counters for each of the S F C.<\/p>\n
The next received message will do the following:<\/p>\n
Processing the S (success) case<\/strong>
\nThe FS<\/strong> counter (has one Failure, ends with Success) becomes the total of the previous: FS, FC, FCC and F
\nThe S<\/strong> counter (has no Failure, ends with Success) becomes the total of the previous: S, C, CC<\/p>\nProcessing the C (corrupted message) case<\/strong><\/p>\n
The FC<\/strong> counter (has one Failure, ends with C) becomes the total of the previous: FS and F
\nThe C<\/strong> counter (has no Failure, ends with C) becomes the previous: S
\nThe FCC<\/strong> counter (has no Failure, ends with C) becomes the previous: FC
\nThe CC<\/strong> counter (has no Failure, ends with C) becomes the previous: C<\/p>\nProcessing the F (failure message) case<\/strong>
\nThe F<\/strong> counter (ending with Failure) will become the previous: C, S, CC<\/p>\nan easier to visualize view of what is said above is the following:<\/p>\n
\n\n
\n Counters sequence with length N<\/th>\n Calculated based on previous sequence<\/th>\n<\/tr>\n \n FS [n] <\/strong><\/td>\n FS [n-1] + FC [n-1] + FCC [n-1] + F [n-1] <\/strong><\/td>\n<\/tr>\n \n FC [n]<\/td>\n FS [n-1] + F [n-1]<\/td>\n<\/tr>\n \n FCC [n]<\/td>\n FC [n-1]<\/td>\n<\/tr>\n \n S [n]<\/td>\n S [n-1] + C [n-1] + CC [n-1]<\/td>\n<\/tr>\n \n C [n]<\/td>\n S [n-1]<\/td>\n<\/tr>\n \n CC [n]<\/td>\n C [n-1]<\/td>\n<\/tr>\n \n F [n]<\/td>\n C [n-1] + S [n-1] + CC [n-1]<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n Manually applying these calculations for several iterations we are getting the following results:<\/p>\n
\n\n
\n \nCounter<\/th>\n 1<\/th>\n 2<\/th>\n 3<\/th>\n 4<\/th>\n 5<\/th>\n 6<\/th>\n 7<\/th>\n 8<\/th>\n 9<\/th>\n 10<\/th>\n<\/tr>\n<\/thead>\n \n FS<\/strong><\/td>\n 0<\/td>\n 1<\/td>\n 4<\/td>\n 12<\/td>\n 30<\/td>\n 70<\/td>\n 156<\/td>\n 337<\/td>\n 712<\/td>\n 1479<\/td>\n<\/tr>\n \n FC<\/strong><\/td>\n 0<\/td>\n 1<\/td>\n 3<\/td>\n 8<\/td>\n 19<\/td>\n 43<\/td>\n 94<\/td>\n 200<\/td>\n 418<\/td>\n 861<\/td>\n<\/tr>\n \n FCC<\/strong><\/td>\n 0<\/td>\n 0<\/td>\n 1<\/td>\n 3<\/td>\n 8<\/td>\n 19<\/td>\n 43<\/td>\n 94<\/td>\n 200<\/td>\n 418<\/td>\n<\/tr>\n \n S<\/strong><\/td>\n 1<\/td>\n 2<\/td>\n 4<\/td>\n 7<\/td>\n 13<\/td>\n 24<\/td>\n 44<\/td>\n 81<\/td>\n 149<\/td>\n 274<\/td>\n<\/tr>\n \n C<\/strong><\/td>\n 1<\/td>\n 1<\/td>\n 2<\/td>\n 4<\/td>\n 7<\/td>\n 13<\/td>\n 24<\/td>\n 44<\/td>\n 81<\/td>\n 149<\/td>\n<\/tr>\n \n CC<\/strong><\/td>\n 0<\/td>\n 1<\/td>\n 1<\/td>\n 2<\/td>\n 4<\/td>\n 7<\/td>\n 13<\/td>\n 24<\/td>\n 44<\/td>\n 81<\/td>\n<\/tr>\n \n F<\/strong><\/td>\n 1<\/td>\n 2<\/td>\n 4<\/td>\n 7<\/td>\n 13<\/td>\n 24<\/td>\n 44<\/td>\n 81<\/td>\n 149<\/td>\n 274<\/td>\n<\/tr>\n \n Totals<\/strong><\/td>\n 3<\/strong><\/td>\n 8<\/strong><\/td>\n 19<\/strong><\/td>\n 43<\/strong><\/td>\n 94<\/strong><\/td>\n 200<\/strong><\/td>\n 418<\/strong><\/td>\n 861<\/strong><\/td>\n 1753<\/strong><\/td>\n 3536<\/strong><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n Note that the bottom line of the above table contains the totals for each iteration; comparing them with we have gotten from the brutal solution we happily see that the results are matching so our algorithm is correct.<\/p>\n
The code<\/h2>\n
Now that we have figured out the algorithm the next (and easiest) step is to to express it in code as can be seen here:<\/p>\n
\r\ndef count_sequences(N):\r\n fs = 0\r\n fc = 0\r\n fcc = 0\r\n s = 1\r\n c = 1\r\n cc = 0\r\n f = 1\r\n\r\n n = 1\r\n while n < N:\r\n fs, fc, fcc, s, c, cc, f = (\r\n fs + fc + fcc + f,\r\n fs + f,\r\n fc,\r\n s + c + cc,\r\n s,\r\n c,\r\n c + s + cc\r\n )\r\n n += 1\r\n\r\n return fs + fc + fcc + s + c + cc + f\r\n<\/pre>\n
We can also use the brutal solution to validate our implementation:<\/p>\n
\r\nfor i in range(1, 10):\r\n assert count_sequences(i) == count_sequences_brutal(i)\r\n<\/pre>\n
Running the performance test as we did with the brutal solution previously:<\/p>\n
\r\nfor time_units in [2, 3, 6, 10, 20, 25, 10000]:\r\n print(\r\n 'time_units:', time_units, 'duration:',\r\n timeit.timeit(stmt=functools.partial(count_sequences, time_units), number=1)\r\n )\r\n<\/pre>\n
gives us the following results:<\/p>\n
![\"sig-8\"](\"\/wp-content\/uploads\/2017\/04\/sig-8.gif\")
<\/p>\nComparing this output with what we have gotten before proves that now we have an extremely much faster algorithm that can be used for a very large number of iteration without significant delays.<\/p>\n
To be more precise the time complexity of our algorithm is linear (O(n)) while its space complexity is O(1) as we do not allocate any additional memory to run it.<\/p>\n
Conclusion<\/h2>\n
In this posting we had to deal with a problem whose obvious solution was very time consuming but after thinking a bit and understanding it better we were able to discover a “smart” trick to solve it efficiently; the same approach is applicable to many similar problems where the best solution lies in discovering some “hidden” properties that are not apparent from the first glance.<\/p>\n","protected":false},"excerpt":{"rendered":"
Solving a programming problem that requires a custom algorithm can be broken in several steps which can be summarized in the creation of testing data,…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"footnotes":""},"categories":[6],"tags":[],"class_list":["post-187","post","type-post","status-publish","format-standard","hentry","category-programming"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","jetpack-related-posts":[{"id":211,"url":"https:\/\/codingismycraft.blog\/index.php\/2020\/07\/01\/thinking-about-algorithmic-problems\/","url_meta":{"origin":187,"position":0},"title":"Thinking about Algorithmic problems","author":"john","date":"July 1, 2020","format":false,"excerpt":"In this posting we will discuss algorithmic thinking and try to propose a way of thinking that might become helpful when trying to solve a problem that does not have an obvious solution and some level of improvisation is required. Based on my experience the three most important qualities of\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/codingismycraft.blog\/index.php\/category\/programming\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":204,"url":"https:\/\/codingismycraft.blog\/index.php\/2020\/07\/06\/buying-and-selling-stocks-with-maximum-profit\/","url_meta":{"origin":187,"position":1},"title":"Buying and Selling stocks with maximum profit","author":"john","date":"July 6, 2020","format":false,"excerpt":"Summary This posting continues the discussion about algorithmic thinking solving a well know problem that is known as\u00a0 Best Time to Buy and Sell Stock with maximum profit. The solution to this problem is hard and I do not believe that it makes a good interview question but it is\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/codingismycraft.blog\/index.php\/category\/programming\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":46,"url":"https:\/\/codingismycraft.blog\/index.php\/2013\/05\/01\/be-extra-cautious-of-early-decisions-in-your-development-cycle\/","url_meta":{"origin":187,"position":2},"title":"Be extra cautious of early decisions in your development cycle","author":"john","date":"May 1, 2013","format":false,"excerpt":"I do not see how can anyone disagree with The McDonald Theory which states that initiating a process is more important than finding the ultimate solution at once. In deed this is how science and technology are progressing and naturally the same principle applies to any human activity which can\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/codingismycraft.blog\/index.php\/category\/programming\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":348,"url":"https:\/\/codingismycraft.blog\/index.php\/2025\/03\/19\/stop-chasing-technology-how-to-build-ai-that-solves-genuine-problems\/","url_meta":{"origin":187,"position":3},"title":"Stop Chasing Technology: Finding the user\u2019s problem is the real problem!","author":"john","date":"March 19, 2025","format":false,"excerpt":"There\u2019s a common critique in the AI community: too often, AI solutions emerge from asking, \u201cWhat can we do?\u201d rather than, \u201cWhat problem do we need to solve?\u201d Developers frequently jump on the latest algorithm or innovative model and then search for a suitable use case. This approach tends to\u2026","rel":"","context":"In "AI"","block_context":{"text":"AI","link":"https:\/\/codingismycraft.blog\/index.php\/category\/ai\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":64,"url":"https:\/\/codingismycraft.blog\/index.php\/2015\/10\/07\/metrics-converted-to-goals-lose-their-focus\/","url_meta":{"origin":187,"position":4},"title":"Metrics converted to goals lose their focus","author":"john","date":"October 7, 2015","format":false,"excerpt":"One of the common discussions I have had with my colleagues over the last years was about the creation of metrics to express the productivity and the quality of an individual developer. At first glance, the idea of expressing the ability of a programmer, with a small set of easy\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/codingismycraft.blog\/index.php\/category\/programming\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":40,"url":"https:\/\/codingismycraft.blog\/index.php\/2013\/03\/11\/abstractions-and-specializations\/","url_meta":{"origin":187,"position":5},"title":"Abstractions and Specializations","author":"john","date":"March 11, 2013","format":false,"excerpt":"Sometimes when developing a solution I stop my coding for a several minutes visualizing my work as a battle between abstractions and specializations. The contrast of these opposites is a major characteristic of any program developed ever and the talent, experience and determination of the developer are stamping the final\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/codingismycraft.blog\/index.php\/category\/programming\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/posts\/187","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/comments?post=187"}],"version-history":[{"count":16,"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/posts\/187\/revisions"}],"predecessor-version":[{"id":203,"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/posts\/187\/revisions\/203"}],"wp:attachment":[{"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/media?parent=187"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/categories?post=187"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/tags?post=187"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
- Contains none or a single failure F<\/strong><\/li>\n
- Ends with one of the letters S<\/strong> F<\/strong> C<\/strong> or CC<\/strong><\/li>\n