Rotated Digits


Dear awice, I am really impressed by the second solution. The code is very solid, though I do not quite agree with your verbal definition of the 3rd dimension:
I think the third dimension should be defined as:
0
: we must have at least one 2569 in[i:]
.1
: we may have one 2569 in[i:]
.
as we can see from the code:
 if
invo
is 0, which means we are not adding a 2569 at digiti
 If
invf
is 0, the code shows we look at[i+1][..][0]
. That means, we are trying to count good numbers in[i:]
that must have at least one 2569, that's why we need to look back at[i+1][..][0]
, because we don't have one inv digit ati
, we have to count on[i+1:]
to provide one.  If
invf
is 1, then code shows we look at[i+1][..][1]
. That means, we are trying to count good numbers in[i:]
with maybe one 2569. We did not provide one ati
becauseinvo = 0
, but it doesn't matter, because we are not mandated by anything. Look at how many good numbers are in[i+1:]
that may have 2569.
 If
 if
invo
is 1, which means we are providing an inv digit of 2569 ati
. Then we surely should be looking back at[i+1][..][1]
because we provided one 2569 ati
, and now it doesn't matter whatinvf
is (meaning whether we require there must or may be 2569 in[i:]
) because we got one.
And to better explain the initialization of
[K][..][1] = 1
and[K][..][0] = 0
, I modify the definition of the second dimension as well: The second dimension corresponds to whether, the counted numbers included in this
memo
cell, must be less or equal to the corresponding[K:]
of the given numberN
.
This is an intuitive interpretation, because, at termination, we only care about
[0][1][0]
with the second dimension being1
: meaning we only count those numbers that are less or equal toN
.Coming back to the initialization, why is it that the init is only determined by
invf
? Because talking about[K:]
, it's empty. Any number we build from digits[K:]
ofN
will be satisfying the less or equal condition. That's whyeqf
does not matter at all during initialization. Since the definition ofinvf = 1
indicates a may contain 2569, and we sure have to set those cells to 1 because does not contain belongs to may contain.Here is a helpful illustration of the first iteration. Be aware of the inversed
eqf
dimension: I apologize for that:

1st solution is overcomplicated
(d not in '347' for d in S)
and(d in '2569' for d in S)
are too expensiveBelow is 2x faster
A good number is a number which has none of bad digits( {3,4,7} ) and at least one good digit( {2,5,6,9} }
bad = ['3', '4', '7'] good = ['2', '5', '6', '9'] ans = 0 for i in map( str, range( 1, N + 1 )): to_continue = True for k in bad: if k in i: to_continue = False break if to_continue: for k in good: if k in i: ans += 1 break return ans