If the numbers 1  100 are written in one long string, how many substrings of minimum length 2 can be found with strictly decreasing numbers?
e.g. 12345678910 has three such substrings: 91, 910, 10.
CLS
FOR i = 1 TO 100
s$ = s$ + LTRIM$(STR$(i))
NEXT
PRINT LEN(s$), s$
FOR i = 2 TO LEN(s$)
IF MID$(s$, i, 1) < MID$(s$, i  1, 1) THEN
IF lCt = 0 THEN
lCt = 2
ELSE
lCt = lCt + 1
END IF
ELSE
IF lCt > 0 THEN
PRINT MID$(s$, i  lCt, lCt); " ";
totStr(lCt) = totStr(lCt) + 1
lCt = 0
END IF
END IF
NEXT
IF lCt > 0 THEN
PRINT MID$(s$, i  lCt, lCt); " ";
totStr(lCt) = totStr(lCt) + 1
lCt = 0
END IF
PRINT : PRINT
FOR i = 0 TO 9
PRINT totStr(i);
NEXT
PRINT
finds substrings of various lengths without counting lower levels of substring (that is, a length3 substring counts only as itself, and the two length2's within it aren't counted).
What it finds are 65 of length 2 and 9 of length 3. But the length3 substrings count for a total of three substrings eachthe length3 substring itself and two length2 substrings. So the total is 65 + 3*9 = 92.
With the above result completed, it's easier to retrofit an "analytic" solution:
Length3 strings:
At 910, 1920, 2930, ... , 99100 (but with 8990 excluded); so that's 10  1 = 9.
Length2 strings not within length3:
Teens: 1213, ... , 1819; Count: 7
20's: 2324, ... , 2829; Count: 6
21; Count 1
30's: 3435, ... , 3839; Count: 5
31, 32; Count 2
...
80's: 81, ... , 87; Count 7
90's: 90 (as 8990 wasn't counted already), 91, ... , 98; Count 9.
The teens through 80's count for 7 each, totalling 56. The nine from the 90's bring this to 65.
Then the 65 doubles and nine triples are combined as before: 65 + 3*9 = 92.

Posted by Charlie
on 20100727 13:59:29 