Question Sets and All Paths

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 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.

  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.

  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))