An easy-to-implement solution for this brain teaser?
So, I have a brain teaser that I read on one of the algorithms and puzzles we meet on our uni, which looks like this:
There is a school there that rewards students that during a given period it is never too late more than ever, and who is never three or more consecutive days. How many possible permutations with repetition of presence (or lack thereof) can we construct in a given time frame to provide the student with a reward? Assuming every day is just a state of Time, late or absent for the whole day, don't worry about specific classes. Example: For 3-day time frames, we can create 19 such repetitive permutations that provide a reward.
I already posted it on math.SE yesterday because I wondered if there was some ready-made formula that we could derive to solve it, but it turned out not, and all the transformations are really quite complicated.
So I am asking here - how would you approach such an algorithm problem? I tried to narrow down the space of possibilities, but after a while all the possible permutations with repetitions became too large and the algorithm started to get really complicated, while I believe there must be some easy way to implement it, especially since most of the puzzles we exchange to a meeting, rather like that.
source to share
Here's a simplified version of Python 3 code implementing recursion in @ProgrammerPerson's answer:
from functools import lru_cache
def count_variants(max_late, base_absent, period_length):
"""
max_late – maximum allowed number of days the student can be late;
base_absent – the number of consecutive days the student can be absent;
period_length – days in a period."""
@lru_cache(max_late * base_absent * period_length)
def count(late, absent, days):
if late < 0: return 0
if absent < 0: return 0
if days == 0: return 1
return (count(late, base_absent, days-1) + # Student is on time. Absent reset.
count(late-1, base_absent, days-1) + # Student is late. Absent reset.
count(late, absent-1, days-1)) # Student is absent.
return count(max_late, base_absent, period_length)
Execution example:
In [2]: count_variants(1, 2, 3)
Out[2]: 19
source to share
This screams recursion (and / or dynamic programming)!
Let's assume we try to solve a small general problem:
We give a reward if a student is no more than L late, and not absent for A or more consecutive days.
Now we want to calculate the number of possibilities for n
days.
Call this method P(L, A, n)
Now try creating a recursion based on three cases in the first day of the period.
1) If the student is on the first day, the number is simply
P(L, A, n-1)
2) If the student is late on the first day, then the number
P(L-1, A, n-1)
3) If the student is absent on the first day, then the number
P(L, A-1, n-1)
This gives us recursion:
P (L, A, n) = P (L, A, n-1) + P (L-1, A, n-1) + P (L, A-1, n-1)
You can either memoize the recursion or just have the tables you are looking for.
Be careful with base cases that
P(0, *, *), P(*, 0, *) and P(*, *, 0)
and can be calculated using simple mathematical formulas.
Here's a quick python code, with memoization + recursion, to demonstrate:
import math
def binom(n, r):
return math.factorial(n)/(math.factorial(r)*math.factorial(n-r))
# The memoization table.
table = {}
def P(L, A, n):
if L == 0:
# Only ontime or absent.
# More absents than period.
if A > n:
return 2**n
# 2^n total possibilities.
# of that n-A+1 are non-rewarding.
return 2**n - (n - A + 1)
if A == 0:
# Only Late or ontime.
# need fewer than L+1 late.
# This is n choose 0 + n choose 1 + ... + n choose L
total = 0
for l in xrange(0, min(L,n)):
total += binom(n, l)
return total
if n == 0:
return 1
if (L, A, n) in table:
return table[(L, A, n)]
result = P(L, A, n-1) + P(L-1, A, n-1) + P(L, A-1, n-1)
table[(L, A, n)] = result
return result
print P(1, 3, 3)
Conclusion 19
.
source to share
Let S (n) be the number of strings of length n without 3 repetitions 1s.
Any such line (at least 3 in length) ends with "0", "01" or "011" (and after removing the suffix, any line without three consecutive 1s can appear).
Then for n> 2 S (n) = S (n-1) + S (n-2) + S (n-3) and S (0) = 1, S (1) = 2, S (2) = 4.
If you have a late day on day I (counting from 0), you have S (i) ways to organize missing days before and S (ni-1) ways to organize missing days after.
Thus, the solution to the original problem S (n) + sum (S (i) * S (ni-1) | i = 0 ... n-1)
We can compute solutions iteratively as follows:
def ways(n):
S = [1, 2, 4] + [0] * (n-2)
for i in xrange(3, n+1):
S[i] = S[i-1] + S[i-2] + S[i-3]
return S[n] + sum(S[i] * S[n-i-1] for i in xrange(n))
for i in xrange(1, 20):
print i, ways(i)
Output:
1 3
2 8
3 19
4 43
5 94
6 200
7 418
8 861
9 1753
10 3536
11 7077
12 14071
13 27820
14 54736
15 107236
16 209305
17 407167
18 789720
19 1527607
source to share