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).
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.
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 this formula as well. I viewed it as an expanding binary tree where you end up cutting branches early, similar to a alpha beta pruning search tree
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.
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
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.
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 wrote some python code which should give the right answer
def formula(total_qs, terminating):
total = 1 << (total_qs - len(terminating))
for i, num in enumerate(terminating):
total += 1 << (num - i)
return total
print(formula(10, [1, 5]))```
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.
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.
Thus, len(question_paths(totq, term)) is equal to sum([2**(term[i] - i) for i in range(len(term))]) + 2**(totq - len(term)).