The number of paths is the sum of 2^(y - x) over each pair (x, y) such that the x-th terminating question is the y-th question overall, plus 2^(number of non-terminating questions overall).<p>In other words, for each possible termination point (including making it all the way through), consider how many non-terminating questions come before that termination point, raise 2 to that power, and then sum these all up.<p>Thus, len(question_paths(totq, term)) is equal to sum([2**(term[i] - i) for i in range(len(term))]) + 2**(totq - len(term)).
I got nerd sniped by this question, and I think I have a closed form formula. Obviously it needs a summation since the order/placement of the numbers matters.<p>The formula is 2^(# of questions - # terminating questions) + SUM[2^(terminiating question number - idx in terminating question list] where the SUM is over all the terms in the list given as input to the question_paths function<p>for example: we take the example of question_paths(10,[1,5]), where the answer is 274. From the formula, we take 2^(10-2) + 2^(1-0) + 2^(5-1) which equals 274.<p>similarly for question_paths(10,[6,8]), where the answer is 448. From the formula, we take 2^(10-2) + 2^(6-0) + 2^(8-1) which equals 448.
I think there is no closed formula, but it's posible to calculate it using recursion (or a loop). From the end, add 1 for terminating questions and multiply by 2 for non terminating ones.<p><pre><code> len(question_paths(10,[1,5])) # 274
2×(1+2×2×2×(1+2×2×2×2×1))
len(question_paths(10,[6,8])) # 448
2×2×2×2×2×2×(1+2×(1+2×1))
len(question_paths(10,[0,1])) # 258
(1+(1+2×2×2×2×2×2×2×2×1))
len(question_paths(10,[8,9])) # 768
2×2×2×2×2×2×2×2×(1+(1+1))</code></pre>