Roman number puzzle solution
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
""" | |
http://www.johndcook.com/blog/2012/01/14/roman-numeral-puzzle/ | |
Question - How many different roman characters consists of unique letters. | |
Range - 0 < number < 4000 | |
For roman numerals I followed the rules that explaind here | |
http://mathsyear7.wikispaces.com/Roman+Numerals | |
""" | |
from collections import OrderedDict | |
digit_representations = ['I', 'V', 'X', 'L', 'C', 'D', 'M'] | |
digit_mapping = OrderedDict([(9, 'oneten'), | |
(5, 'five'), | |
(4, 'onefive'), | |
(1, 'one')]) | |
def get_digits(num): | |
""" | |
Gets a number and returns list of digits | |
""" | |
return [int(i) for i in str(num)] | |
def digit_to_roman(digit): | |
""" | |
Gets a digit and returns a roman equvelnt of digits | |
Return numbers are not returned as regular roman numbers instead | |
we the number written in english for example | |
I => one | |
IV => onefive | |
VII => fiveoneone | |
we have to do this because when we replace digit values. | |
We might be mixing real value with digit value | |
""" | |
resp = "" | |
for key, value in digit_mapping.iteritems(): | |
# How many of times we will repeat the current | |
# value | |
repeat = digit / key | |
if repeat: | |
resp += value * repeat | |
# remove added value from digit | |
digit -= key * repeat | |
return resp | |
def int_to_roman(num): | |
assert 0 < num < 4000 | |
"Value must be between 1 and 3999"\ | |
% digit_representations | |
resp = "" | |
# get reversed digit list. For instance, for | |
# 3210 we need [0,1,2,3] | |
digit_list = get_digits(num) | |
digit_list.reverse() | |
for i, digit in enumerate(digit_list): | |
# get current digit as str | |
digit_str = digit_to_roman(digit) | |
# get possible letters to use for current digit | |
# for example, in tens digit my letters list must be | |
# ['X','L','C'] | |
letters = digit_representations[i * 2:((i * 2) + 3)] | |
# Replace digit represenation with its current values | |
digit_str = digit_str.replace('one', letters[0]) | |
if len(letters) >= 2: | |
digit_str = digit_str.replace('five', letters[1]) | |
if len(letters) >= 3: | |
digit_str = digit_str.replace('ten', letters[2]) | |
# add current digit to result value | |
resp = digit_str + resp | |
return resp | |
def main(): | |
total = 0 | |
for num in range(1, 4000): | |
roman = int_to_roman(num) | |
if len(roman) == len(set(roman)): | |
total += 1 | |
print 'total number of unique lettered numbers = %s' % total # 316 | |
if __name__ == '__main__': | |
main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment