0b1001 путей решения задачи перевода римских цифр04.10.2016 13:33

image

Привет друзья. Вот вам простенькая задачка. Как бы вы перевели арабские цифры в римские используя Python? Правда с одним условием — цифры не могут быть больше чем 4000.

Я думаю это должно быть просто, но позвольте я вам покажу вам серию интересных решений и не тривиальных подходов:

»13 шагов» от StefanPochmann


Очень простая идея и при этом самая популярная. Мы делаем таблицу соответствий арабских и римских цифр. Идя по таблице этих соответствий мы уменьшая арабское число и увеличиваем римское.
def checkio(n):
    result = ''
    for arabic, roman in zip((1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1),
                             'M     CM   D    CD   C    XC  L   XL  X   IX V  IV I'.split()):
        result += n // arabic * roman
        n %= arabic
        print('({}) {} => {}'.format(roman, n, result))
    return result

Я добавил функцию print для вас, чтобы решение было понятнее. И вот какой будет вывод: 
>>> checkio(177)
(M) 177 => 
(CM) 177 => 
(D) 177 => 
(CD) 177 => 
(C) 77 => C
(XC) 77 => C
(L) 27 => CL
(XL) 27 => CL
(X) 7 => CLXX
(IX) 7 => CLXX
(V) 2 => CLXXV
(IV) 2 => CLXXV
(I) 0 => CLXXVII
'CLXXVII'

Теперь вы видите, как на каждой итерации меняется римское и арабское числа.

«thous, hunds, tens и ones» от mdeakyne


def checkio(data):
    ones = ["","I","II","III","IV","V","VI","VII","VIII","IX"]
    tens = ["","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"]
    hunds = ["","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"]
    thous = ["","M","MM","MMM","MMMM"]
    
    t = thous[data // 1000]
    h = hunds[data // 100 % 10]
    te = tens[data // 10 % 10]
    o =  ones[data % 10]
    
    return t+h+te+o

В этом случае у нас уже есть обратное соответствие арабских к римским. При этом нам уже не нужен цикл.

«base.replace» от MaikSchoepe


def checkio(data):
    base = "I"*data
    
    base = base.replace("I"*5, "V")
    base = base.replace("V"*2, "X")
    base = base.replace("X"*5, "L")
    base = base.replace("L"*2, "C")
    base = base.replace("C"*5, "D")
    base = base.replace("D"*2, "M")
    
    base = base.replace("DCCCC", "CM")
    base = base.replace("CCCC", "CD")
    base = base.replace("LXXXX", "XC")
    base = base.replace("XXXX", "XL")
    base = base.replace("VIIII", "IX")
    base = base.replace("IIII", "IV")
    
    return base

Я верю, что это не самый эффективный способ решения, но один из самых веселых. Он начинается с того, что делает длинную строку из «I», размером с переданное число. Следующей строй заменяет каждые пять символов «I» на символ «V». Далее два «V» на «X» и так далее. В конце пути мы получим строку, которую мы искали.

«Enum» от veky


Для того, чтобы понять, как работает следующее решение вам надо знать модуль Enum. Если не знаете — есть отличный шанс погуглить его.
from enum import Enum
​
class Roman(Enum):
    M  = 1000
    CM = 900
    D  = 500
    CD = 400
    C  = 100
    XC = 90
    L  = 50
    XL = 40
    X  = 10
    IX = 9
    V  = 5
    IV = 4
    I  = 1
​
    @classmethod
    def encode(cls, n):
        for numeral in cls:
            rep, n = divmod(n, numeral.value)
            yield numeral.name * rep
​
checkio = lambda n: ''.join(Roman.encode(n))

В целом пример работает так-же как мы видели в первом примере от StefanPochmann, но кое-каким синтаксическим сахором. Таким как Enum и yield

«A derelict battery» от veky


Все эти решения я собрал с CheckiO.

И когда пользователь публикует свое решение на этом ресурсе — он должен выбрать, в какую категорию он хочет его добавить. Есть такая категория как «Creative», где тебе не надо сильно заморачиваться на тему скорости или как легко твое решение читается. Единственная вещь, о который ты должен думать — это на сколько креативное и необычное твое решение.

Это решение как раз из такое категории.

import formatter, functools
checkio = functools.partial(formatter.AbstractFormatter.format_roman, None, 'I')

Да, вот и все. Стоит упомянуть, правда, что модуль formater задеприкейтили начиная с версии 3.4 из-за того, что мало кто его использовал. Так что мы скорее всего напишем петицию Гвидо, чтобы оставить этот модуль в Python. Своим ап-вотом за это решение — вы как-бы ставите свою подпись под этой петицией.

«Достаточно элегантно, но не очень по питоновски» от nathan.l.cook


Мы идем дальше и решения становятся тяжелее
def checkio(data):
    rom = ['I', 'V', 'X', 'L', 'C', 'D', 'M']
    str_data = str(data)
    str_data = str_data[::-1]
    num_digits = len(str_data)
    ans = ""
    rom_pointer = 0
​
    for place in range(num_digits):
        if str_data[place] in ["0", "1", "2", "3"]:
            ans = rom[rom_pointer] * int(str_data[place]) + ans
        elif str_data[place] in ["4"]:
             ans = rom[rom_pointer] + rom[rom_pointer + 1] + ans
        elif str_data[place] in ["5", "6", "7", "8"]:
             ans = rom[rom_pointer + 1] + rom[rom_pointer] * (int(str_data[place]) - 5) + ans
        elif str_data[place] in ["9"]:
             ans = rom[rom_pointer] + rom[rom_pointer + 2] + ans
        rom_pointer += 2
​
    return ans

Знаете, когда читаешь чье то решение и первые строки, которые ты видишь это: 
    str_data = str(data)
    str_data = str_data[::-1]

Ты думаешь: «Ок, тут ща точно будет какая-то магия»

«Немного истории от» от veky (или от …)


def checkio(n:int) -> str:
  pool = "m2d5c2l5x2v5i"
  rep = lambda t: int(pool[t - 1])
  def roman(n, j=0, v=1000):
    while True:
      while n >= v: yield pool[j]; n -= v
      if n <= 0: return
      k = j + 2; u = v // rep(k)
      if rep(k) == 2: k += 2; u //= rep(k)
      if n + u >= v: yield pool[k]; n += u
      else: j += 2; v //= rep(j)
  return "".join(roman(n)).upper()

Вы можете знать автора этого решения по таким книгам как The Art of Computer Programming, Concrete Mathematics, Surreal Numbers и так далее.

«Эта странная римская математика» от LukeSolo


Довольно часто ты встречаешь решения на CheckiO, и при этом ты даже не представляешь, как они работают: 
from math import sqrt
​
alpha = "IVXLCDM"
one = lambda n, s: (n % 5 >> n % 5 // 4 * 2) * alpha[s]
two = lambda n, s: (3 < n) * alpha[s + (3 < n) + (8 < n)]
three = lambda n, s: sqrt(n) == int(sqrt(n)) and ''.join(reversed(s)) or s
go = lambda n, s: three(n, two(n, s) + one(n, s))
​
def checkio(data, s = 0, conc = ""):
    d, m = divmod(data, 10)
    text = go(m, s) + conc
    return d and checkio(d, s + 2, text) or text

Но я думаю, что вы разберетесь :)

Спасибо


В списке используемых материалов я добавил ссылки на решения CheckiO пользователей, которые использовал в этой статье. Перейдя по ним, вы можете прочитать код-ревью других пользователей либо написать свое.

Это первый раз, когда я пытаюсь поделится такой вот коллекцией наиболее интересных решений на CheckiO. Дайте мне знать, насколько интересно вам о таком читать и на сколько вам нравится сам формат.

Для создания этой статьи использовались решения пользователей CheckiO:

  • »13 шагов» от StefanPochmann
  • «thous, hunds, tens и ones» от mdeakyne
  • «base.replace» от MaikSchoepe
  • «Enum» от veky
  • «A derelict battery» от veky
  • «Достаточно элегантно, но не очень по питоновски» от nathan.l.cook
  • «Немного истории от» от veky (или от …)
  • «Эта странная римская математика» от LukeSolo

ПС: Кстати, еще есть категория «Speedy» для решений. И когда ты говоришь, что решение задачи не может быть длиннее чем 4000 символов, то самым быстрым решением для этой задачи будет вот это. По понятным причинам я могу вам показать только ссылку.

Комментарии (2)

  • 4 октября 2016 в 13:18

    0

    ↑

    ↓

    Замечательно. Вы собрали вместе столько разных способов решить абсолютно бесполезную задачу…

    • 4 октября 2016 в 13:25

      0

      ↑

      ↓

      :)

      Я думаю полезность этой задачи только в том, что она сумела собрать столько разнообразных решений вокруг себя, что может научить людей чему-то новому. Людей, которые в последствии создадут что-то полезное для Вас лично.

© Habrahabr.ru