Created
May 25, 2024 00:43
-
-
Save shiracamus/813ebd36a85a43d7063cfa72014ade26 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def two_digit_sieve(digits: tuple[int], numbers: list[int], i: int = 0) -> bool: | |
| """ | |
| 1桁数列digitsのi番目から順に1桁または2桁の数を作ってnumbersに追加し、digits | |
| をすべて使って数の重複がないnumbersが完成したらTrue、失敗したらFalseを返す | |
| """ | |
| if i == len(digits): | |
| return True # 完成 | |
| if (i + 1 < len(digits) and digits[i] != 0 and | |
| (number := digits[i]*10 + digits[i+1]) not in numbers): | |
| numbers.append(number) # 2桁数で試行 | |
| if two_digit_sieve(digits, numbers, i+2): | |
| return True # 完成 | |
| numbers.pop() # 失敗した2桁数を取り除く | |
| if digits[i] not in numbers: | |
| numbers.append(digits[i]) # 1桁数で試行 | |
| if two_digit_sieve(digits, numbers, i+1): | |
| return True # 完成 | |
| numbers.pop() # 失敗した1桁数を取り除く | |
| return False # 失敗 | |
| def main() -> None: | |
| s = "194844479992885193431281672755538710981664457433843176692585632179368224916037252154184211658086419457126285078707285638157343020599675354922614657775295148733139079401662636483232968398997" | |
| numbers = [] | |
| if two_digit_sieve(tuple(map(int, s)), numbers): | |
| print(numbers) | |
| else: | |
| print('no answer') | |
| if __name__ == '__main__': | |
| main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment