Skip to content

Instantly share code, notes, and snippets.

@huseyinyilmaz
Created January 17, 2012 12:52
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save huseyinyilmaz/1626535 to your computer and use it in GitHub Desktop.
Roman number puzzle solution
"""
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