ProgrammingChallenges/getting_digits.py

#!/usr/bin/env python3

# Dictionary letter -> (number, position in number)
LN = {
    'A': [],
    'B': [],
    'C': [],
    'D': [],
    'E': [(0,1),(1,2),(3,3),(3,4),(5,3),(7,1),(7,3),(8,0),(9,3)],
    'F': [(4,0),(5,0)],
    'G': [(8,2)],
    'H': [(3,1),(8,3)],
    'I': [(5,1),(6,1),(8,1),(9,1)],
    'J': [],
    'K': [],
    'L': [],
    'M': [],
    'N': [(1,1),(7,4),(9,0),(9,2)],
    'O': [(0,3),(1,0),(2,2),(4,1)],
    'P': [],
    'Q': [],
    'R': [(0,2),(3,2),(4,3)],
    'S': [(6,0),(7,0)],
    'T': [(2,0),(3,0),(8,4)],
    'U': [(4,2)],
    'V': [(5,2),(7,2)],
    'W': [(2,1)],
    'X': [(6,2)],
    'Y': [],
    'Z': [(0,0)]
}

def print_scoreboard(scoreboard, NUMS):
    for s in NUMS:
        print(s, end=' ')
    print()
    for n in scoreboard:
        for score in n:
            print(str(score) if score != 0 else ' ', end='')
        print(' ', end='')
    print('\n')

# Criteria of rarity (shortest number of (number, position) couples for the letter)
# Sort of a lambda, but in python
def criteria(l):
    return len(LN[l])

def get_digits(s):
    NUMS = ["ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN",
        "EIGHT", "NINE"]
    scoreboard = []
    for num in NUMS:
        scoreboard.append([0]*len(num))
    numbers = [0] * 10

    # Sort the string by rarity of letters (all Vs come before Es)
    s = "".join(sorted(s, key=criteria))

    for c in s:
        last_n = None
        last_pos = None
        # For every (number, position) ordered pair for our letter
        for k in range(len(LN[c])):
            np = LN[c][k]
            if last_n != np[0]:
                # Increment the letter if the we've never seen this number
                scoreboard[np[0]][np[1]] += 1
                last_n = np[0]
                last_pos = np[1]
            elif scoreboard[np[0]][np[1]] < scoreboard[np[0]][last_pos] - 1:
                # If we have a duplicate letter in more positions, increment evenly
                # instead of incrementing just the first letter.
                # This code works if the are at most 2 positions for each letter, which
                # is true with the numbers from ZERO to NINE
                scoreboard[np[0]][last_pos] -= 1
                scoreboard[np[0]][np[1]] += 1
                last_n = None

        # Debug print the scoreboard, uncomment this if unclear
        # print_scoreboard(scoreboard, NUMS)

        for i in range(10):
            # Check if the scoreboard for number i is BINGO
            valid = True
            for j in range(len(scoreboard[i])):
                if scoreboard[i][j] == 0:
                    valid = False
                    break
            if valid:
                # If true, mark BINGO and remove all the "ticks" for other numbers
                numbers[i] += 1
                # print(numbers)
                for c in NUMS[i]:
                    last_n = None
                    last_pos = None
                    for k in range(len(LN[c])):
                        np = LN[c][k]
                        if last_n != np[0]:
                            scoreboard[np[0]][np[1]] -= 1
                            last_n = np[0]
                            last_pos = np[1]
                        elif scoreboard[np[0]][np[1]] > scoreboard[np[0]][last_pos] + 1:
                            # Decrement magic similar to the even incrementation above.
                            # Note that this decrements the first position first, but the code
                            # for incrementing is able to cope with this oddity, so whatever man...
                            scoreboard[np[0]][last_pos] += 1
                            scoreboard[np[0]][np[1]] -= 1
                            last_n = None

    # Print the scoreboard if not clean (this should never happen if the input string is valid)
    # for a in scoreboard:
    #     for b in a:
    #         if b != 0:
    #             print(scoreboard, end=' ')
    #             break
    #     else:
    #         continue
    #     break

    # Build the output string using our BINGO log
    output = ""
    for i in range(10):
        output += str(i) * numbers[i]
    return output

if __name__ == "__main__":
    n = int(input())
    for i in range(1, n + 1):
        print("Case #" + str(i) + ": " + get_digits(input()))