mirror of
https://github.com/iritmaximus/tira.git
synced 2026-10-12 19:13:47 +03:00
68 lines
1.7 KiB
Python
68 lines
1.7 KiB
Python
from typing import List
|
|
import itertools
|
|
|
|
|
|
def check_increasing(number: str):
|
|
prev_num: int = -1
|
|
if len(number) > 1 and int(number[0]) == 0:
|
|
return False
|
|
|
|
for num in number:
|
|
if int(num) >= prev_num:
|
|
prev_num = int(num)
|
|
else:
|
|
return False
|
|
return True
|
|
|
|
|
|
def lower_than_res(res: str, numbers: str):
|
|
for (i, x) in enumerate(numbers):
|
|
if x >= res[0]:
|
|
return i
|
|
|
|
return 0
|
|
|
|
def count_numbers(length: int, numbers: str):
|
|
result: List[str] = [x for x in numbers]
|
|
while length-1> 0:
|
|
for i, res in enumerate(result.copy()):
|
|
# Remove previous step
|
|
result.remove(res)
|
|
|
|
# Don't calculate unnecessary things
|
|
i_lower = lower_than_res(res, numbers)
|
|
for num in numbers[i_lower:]:
|
|
if i != 0 and res[-1] == "0":
|
|
continue
|
|
if num >= res[-1] and res[-1] != "0":
|
|
result.append(res + num)
|
|
|
|
length -= 1
|
|
|
|
print(len(result))
|
|
return len(result)
|
|
|
|
|
|
# Way too slow on the last test
|
|
def count_numbers2(length: int, numbers: str):
|
|
result: int = 0
|
|
for comb in itertools.product(numbers, repeat=length):
|
|
# print(comb, check_increasing(comb))
|
|
if check_increasing(comb):
|
|
result += 1
|
|
|
|
print(result)
|
|
# print()
|
|
return result
|
|
|
|
|
|
if __name__ == "__main__":
|
|
assert count_numbers(5, "1") == 1
|
|
assert count_numbers(1, "0") == 1
|
|
assert count_numbers(3, "123") == 10
|
|
assert count_numbers(2, "0") == 0
|
|
assert count_numbers(2, "137") == 6
|
|
assert count_numbers(8, "25689") == 495
|
|
assert count_numbers(10, "12") == 11
|
|
assert count_numbers(10, "123456789") == 43758
|