/
non-bouncy_numbers.sf
133 lines (92 loc) · 4.95 KB
/
non-bouncy_numbers.sf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#!/usr/bin/ruby
# Author: Trizen
# Date: 12 April 2023
# https://github.com/trizen
# Generate numbers with increasing and decreasing digits (which are called "non-bouncy numbers"), in a given base.
# See also:
# https://projecteuler.net/problem=112
func increasing_numbers(limit, base=10) {
func f(n, min_d) {
var seq = [n]
for d in (min_d ..^ base) {
var v = (n*base + d)
v <= limit || break
seq << __FUNC__(v, d)...
}
return seq
}
map(1..min(limit,base-1), {|d| f(d, d) }).flat.sort
}
func decreasing_numbers(limit, base=10) {
func f(n, max_d) {
var seq = [n]
for d in (0 .. max_d) {
var v = (n*base + d)
v <= limit || break
seq << __FUNC__(v, d)...
}
return seq
}
map(1..min(limit,base-1), {|d| f(d, d) }).flat.sort
}
func increasing_numbers_count(limit, base=10) {
func f(n, min_d) {
var count = 1
for d in (min_d ..^ base) {
var v = (n*base + d)
v <= limit || break
count += __FUNC__(v, d)
}
return count
}
sum(1..min(limit,base-1), {|d| f(d,d) })
}
func decreasing_numbers_count(limit, base=10) {
func f(n, max_d) {
var count = 1
for d in (0 .. max_d) {
var v = (n*base + d)
v <= limit || break
count += __FUNC__(v, d)
}
return count
}
sum(1..min(limit,base-1), {|d| f(d,d) })
}
func non_bouncy_count_slow(limit, base=10) {
increasing_numbers(limit, base) + decreasing_numbers(limit, base) -> uniq.len
}
func non_bouncy_count(limit, base=10) {
if (limit < base) {
return max(0, limit)
}
var t = (increasing_numbers_count(limit, base) + decreasing_numbers_count(limit, base))
t -= ((base-1) * (limit.len(base)-1))
var r = (base**limit.len(base) - 1)/(base-1)
for d in (1 ..^ base) {
r*d > limit && break
--t
}
return t
}
say ":: Increasing numbers <= 1000:"
say increasing_numbers(1e3)
say "\n:: Decreasing numbers <= 1000:"
say decreasing_numbers(1e3)
say ''
for (1..6) {|k|
var limit = 10**k
say "There are #{non_bouncy_count(limit)} non-bouncy numbers <= 10^#{k}"
#assert_eq(non_bouncy_count(limit), non_bouncy_count_slow(limit))
}
__END__
:: Increasing numbers <= 1000:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 22, 23, 24, 25, 26, 27, 28, 29, 33, 34, 35, 36, 37, 38, 39, 44, 45, 46, 47, 48, 49, 55, 56, 57, 58, 59, 66, 67, 68, 69, 77, 78, 79, 88, 89, 99, 111, 112, 113, 114, 115, 116, 117, 118, 119, 122, 123, 124, 125, 126, 127, 128, 129, 133, 134, 135, 136, 137, 138, 139, 144, 145, 146, 147, 148, 149, 155, 156, 157, 158, 159, 166, 167, 168, 169, 177, 178, 179, 188, 189, 199, 222, 223, 224, 225, 226, 227, 228, 229, 233, 234, 235, 236, 237, 238, 239, 244, 245, 246, 247, 248, 249, 255, 256, 257, 258, 259, 266, 267, 268, 269, 277, 278, 279, 288, 289, 299, 333, 334, 335, 336, 337, 338, 339, 344, 345, 346, 347, 348, 349, 355, 356, 357, 358, 359, 366, 367, 368, 369, 377, 378, 379, 388, 389, 399, 444, 445, 446, 447, 448, 449, 455, 456, 457, 458, 459, 466, 467, 468, 469, 477, 478, 479, 488, 489, 499, 555, 556, 557, 558, 559, 566, 567, 568, 569, 577, 578, 579, 588, 589, 599, 666, 667, 668, 669, 677, 678, 679, 688, 689, 699, 777, 778, 779, 788, 789, 799, 888, 889, 899, 999]
:: Decreasing numbers <= 1000:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 20, 21, 22, 30, 31, 32, 33, 40, 41, 42, 43, 44, 50, 51, 52, 53, 54, 55, 60, 61, 62, 63, 64, 65, 66, 70, 71, 72, 73, 74, 75, 76, 77, 80, 81, 82, 83, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 110, 111, 200, 210, 211, 220, 221, 222, 300, 310, 311, 320, 321, 322, 330, 331, 332, 333, 400, 410, 411, 420, 421, 422, 430, 431, 432, 433, 440, 441, 442, 443, 444, 500, 510, 511, 520, 521, 522, 530, 531, 532, 533, 540, 541, 542, 543, 544, 550, 551, 552, 553, 554, 555, 600, 610, 611, 620, 621, 622, 630, 631, 632, 633, 640, 641, 642, 643, 644, 650, 651, 652, 653, 654, 655, 660, 661, 662, 663, 664, 665, 666, 700, 710, 711, 720, 721, 722, 730, 731, 732, 733, 740, 741, 742, 743, 744, 750, 751, 752, 753, 754, 755, 760, 761, 762, 763, 764, 765, 766, 770, 771, 772, 773, 774, 775, 776, 777, 800, 810, 811, 820, 821, 822, 830, 831, 832, 833, 840, 841, 842, 843, 844, 850, 851, 852, 853, 854, 855, 860, 861, 862, 863, 864, 865, 866, 870, 871, 872, 873, 874, 875, 876, 877, 880, 881, 882, 883, 884, 885, 886, 887, 888, 900, 910, 911, 920, 921, 922, 930, 931, 932, 933, 940, 941, 942, 943, 944, 950, 951, 952, 953, 954, 955, 960, 961, 962, 963, 964, 965, 966, 970, 971, 972, 973, 974, 975, 976, 977, 980, 981, 982, 983, 984, 985, 986, 987, 988, 990, 991, 992, 993, 994, 995, 996, 997, 998, 999, 1000]
There are 10 non-bouncy numbers <= 10^1
There are 100 non-bouncy numbers <= 10^2
There are 475 non-bouncy numbers <= 10^3
There are 1675 non-bouncy numbers <= 10^4
There are 4954 non-bouncy numbers <= 10^5
There are 12952 non-bouncy numbers <= 10^6