Kaprekar

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

"""
Nom du script : Kaprekar.py
Auteur : Alain Van Kerckhoven
Date : 26/08/2024
Version : 1.0
Licence : GPL

Modifications :
- 26/09/2024 : Création du script (Alain Van Kerckhoven)

Description :
Recherche les attracteurs de Kaprekar pour les nombres à n chiffres.


Remarques :
- Durée exponentielle (109 s pour 5 chiffres)

Dépendances :
- sys
- time
"""

import sys
import time

def kaprekar_step(number, n):
    """
    Performs one step of the Kaprekar process.

    Args:
    - number (int): The current number to process.
    - n (int): The number of digits for the current process.

    Returns:
    - int: The result of subtracting the ascending version of the digits from the descending version.
    """
    # Convert number to string and ensure it has exactly n digits (pad with zeros if necessary)
    num_str = str(number).zfill(n)

    # Create ascending and descending versions of the number
    ascending = int("".join(sorted(num_str)))
    descending = int("".join(sorted(num_str, reverse=True)))

    # Return the difference
    return descending - ascending

def find_kaprekar_attractors(n):
    """
    Finds the Kaprekar attractors for n-digit numbers.

    Args:
    - n (int): The number of digits to consider.

    Returns:
    - dict: A dictionary where the keys are attractors and the values are lists of numbers that converge to those attractors.
    """
    seen_numbers = {}

    # For n = 2, handle cases where numbers might reduce to a single digit
    start = 10 if n == 2 else 10**(n-1)
    end = 10**n

    # Iterate over all n-digit numbers
    for i in range(start, end):
        current = i
        # Print the number being tested, overwriting the previous number
        print(f"\rTesting number: {current}", end="")
        sys.stdout.flush()  # Ensure the output is immediately flushed to the console

        sequence = []
        while current not in sequence:
            sequence.append(current)
            current = kaprekar_step(current, n)

        # Identify the attractor
        attractor = current
        if attractor in seen_numbers:
            seen_numbers[attractor].append(i)
        else:
            seen_numbers[attractor] = [i]

    print()  # Ensure the final output is separated properly
    return seen_numbers

def main():
    """
    Main function to execute the Kaprekar attractor finding process.
    Asks the user for the number of digits, finds attractors, and displays the results.
    """
    # Prompt the user for the number of digits
    n = int(input("Enter the number of digits (n): "))

    # Start the timer
    start_time = time.time()

    # Find the attractors for n-digit numbers
    attractors = find_kaprekar_attractors(n)

    # Stop the timer
    end_time = time.time()

    # Display the results
    print("\nAttractors found:")
    for attractor, numbers in attractors.items():
        print(f"Attractor: {attractor}, Found from {len(numbers)} numbers")

    # Calculate and display the elapsed time
    elapsed_time = end_time - start_time
    print(f"\nCalculation completed in {elapsed_time:.2f} seconds.")

if __name__ == "__main__":
    main()