Counting Digits
January 7, 2020
Here’s our solution:
(define (f lo hi) (define (is258 d) (or (= d 2) (= d 5) (= d 8))) (define (cnt n) (length (filter is258 (digits n)))) (do ((n lo (+ n 1)) (c 0 (+ c (cnt n)))) ((< hi n) c))) > (f 295 395) 9 > (time (f 11 100000)) (time (f 11 ...)) 2 collections 0.018759638s elapsed cpu time, including 0.000229760s collecting 0.018892309s elapsed real time, including 0.000238270s collecting 9539376 bytes allocated, including 16834208 bytes reclaimed 149997
You can run the program at https://ideone.com/FA3ADI.
Programming Praxis 
Happy new year & I hope everyone enjoyed the holiday break.
I thought that should be a more direct way of counting the digits than enumerating the entire range. For simplicity, dcount counts all the digits in range(n) – ie. not including n itself:
def dcount(digits,n): count = 0 m,m1 = 1,10 while n >= m: for k in digits: count += n//m1*m + min(m,max(n%m1-k*m,0)) m,m1 = m1,10*m1 return count digits = [2,5,8] print(dcount(digits,306)-dcount(digits,295)) # 9That needs some modification for digit ‘0’ (an exercise for the reader)- also the while condition can be ‘n > m’
This is better (and the ‘0’ count is correct if we assume numbers are zero padded on the left to the same length):
def dcount(digits,n): count = 0 m,m1 = 1,10 for _ in range(len(str(n-1))): count += n//m1*m*len(digits) for k in digits: count += min(m,max(n%m1-k*m,0)) m,m1 = m1,10*m1 return countOr wrap the whole thing up in a list comprehension:
def dcount(digits,n): return sum(sum(n//m1*m + min(m,max(n%m1-k*m,0)) for k in digits) for i in range(len(str(n-1))) for m in [10**i] for m1 in [10*m])Klong version
; $n - Change number to string ; ($n)?$x - Turn digit into string and store in a list the positions of digit in string ; #($n)?$x - Get number of positions ; {#($n)?$x}'"258"} - Function to do the aboved for each digit in "258" and return list of number of positions/hits ; +/... - Return sum of hits ; {[n];n::x;+/{...}...}'x+!1+y-x - Function to goo through each of the number in the range and run the inner function, returning a list of sums ; +/{...{...}... - Return total sum of hits ; {+/...}(295;305) - Run middle function ({}) with first and last number in range of numbers ; {+/{[n];n::x;+/{#($n)?$x}'"258"}'x+!1+y-x}(295;305)Klong results:
{+/{[n];n::x;+/{#($n)?$x}'”258″}’x+!1+y-x}(295;305)
9
Here’s a solution in Python, based on the digit counting algorithm from here.
from collections import Counter def count_digits(lo, hi): assert 0 <= lo <= hi counts = Counter() x = lo while x <= hi: digits = [int(c) for c in str(x)] counts += Counter(digits) power = len(str(x)) - len(str(x).rstrip('0')) if power > 0: nines = 10 ** power - 1 if x + nines <= hi: counts += Counter(dict.fromkeys(range(10), power * 10 ** (power - 1))) counts[0] -= power prefix = [int(c) for c in str(x).rstrip('0')] for digit in prefix: counts[digit] += nines x += nines x += 1 return dict(counts) def count_258(lo, hi): return sum(count for digit, count in count_digits(lo, hi).items() if digit in (2, 5, 8)) print(count_258(295, 305)) print(count_258(295_000_000_000, 305_000_000_000)) print(count_digits(0, 99))Output:
9 35000000001 {0: 10, 1: 20, 2: 20, 3: 20, 4: 20, 5: 20, 6: 20, 7: 20, 8: 20, 9: 20}