Jarosław Zabiełło - BLOG

Projekt Eulera 17 - Ruby, Python, Scala

Opublikowane przez Jarosław Zabiełło Sun, 05 Apr 2009 21:24:00 GMT

Na polskim forum RoR pojawiła się informacja o projekcie Eulera składającym się z różnych łamigłówek programistycznych. Na forum RoR przedstawiane są rozwiązania w języku Ruby. Istnieją też rozwiązania w języku Clojure. Takie projekty są dobrym pretekstem do poćwiczenia swoich umiejętności programowania.

Zadanie 17 brzmi następująco.

Jeśli liczby od 1 do 5 zapisać za pomocą ich (angielskich) słów: one, two, three, four, five, to wtedy użyte zostanie 3 + 3 + 5 + 4 + 4 = 19 liter. Gdyby wszystkie liczby od 1 do 1000 zapisać za pomocą słów to ile w sumie by użyto liter? Uwaga: nie należy liczyć spacji ani myślników. Np. liczba 342 (three hundred and fourty-two) zawiera 23 litery a liczba 115 (one hundred and fifteen) zawiera 20 liter. Łącznik “and” jest wymagany w jęz. angielskim.

Rozwiązane podesłane w Ruby:

def to_words(num)
  a0 = %w{ one two three four five six seven eight nine ten eleven twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen }
  a1 = %w{ twenty thirty forty fifty sixty seventy eighty ninety }
  case num
  when 1..19
    a0[num-1]
  when 20..99
    num % 10 != 0 ? "#{a1[(num-20)/10]}#{a0[num % 10 - 1]}" : a1[(num-20)/10]
  when 100..999
    num % 100 != 0 ? "#{to_words(num/100)}hundredand#{to_words(num % 100)}" : "#{to_words(num/100)}hundred" 
  when 1000
    "onethousand" 
  end
end

puts (1..1000).inject('') { |acc,n| acc << to_words(n)}.size

W Pythonie można by to samo zapisać w zwarty sposób jako

def to_words(num):
  a0 = 'one two three four five six seven eight nine ten eleven twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen'.split(' ')
  a1 = 'twenty thirty forty fifty sixty seventy eighty ninety'.split(' ')
  if 1<= num <= 19:  return a0[num-1]
  if 20 <= num <= 99: return  "%s%s" % (a1[(num-20)/10], a0[num % 10 - 1]) if num % 10 != 0 else a1[(num-20)/10]
  if 100 <= num <= 999: return "%shundredand%s" % (to_words(num/100), to_words(num % 100)) if num % 100 != 0 else "%shundred" % to_words(num/100)
  if num == 1000: return "onethousand" 

print sum([len(to_words(n)) for n in range(1,1001)])

Zaś w Scali odpowiednikiem mógłby być kod:

def to_words(num: Int): String = {
  val a0 = "one two three four five six seven eight nine ten eleven twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen".split(' ')
  val a1 = "twenty thirty forty fifty si6xty seventy eighty ninety".split(' ')
  if (1 to 19 contains num) return a0(num-1)
  if (20 to 99 contains num) return if (num % 10 != 0) "%s%s".format(a1((num-20)/10), a0(num % 10 - 1)) else a1((num-20)/10)
  if (100 to 999 contains num) return if (num % 100 != 0) "%shundredand%s".format(to_words(num/100), to_words(num % 100)) else "%shundred".format(to_words(num/100))
  if (num == 1000) "onethousand" else "" 
}

println((for(n <- 1 to 1000) yield to_words(n).length).foldLeft(0)(_ + _))                                                                          

1 to 19 contains num

to zapis w notacji operatorowej odpowiadający

(1.to(19)).contains(num)

Warunek logiczny if zwraca wartość którą można przypisać do zmiennej. for() jest też wyrażeniem. Słówko yield powoduje, że całość jest zwracana jako lista. Z kolei kod

for(n <- 1 to 1000) yield to_words(n).length

można by zapisać w Pythonie za pomocą wyrażenia listowego

[len(to_words(n)) for n in range(1,10001)]

zaś w Ruby byłoby to

(1..1000).map{|n| to_words(n).size}

Z powyższego kodu można by wyrzucić uprościć warunki logiczne. Poza tym możemy nie chcieć, aby zmienne a0 i a1 były inicjowane przy każdym uruchomieniu funkcji. Poza tym Scala posiada świetny mechanizm znany w z języków funkcyjnych – pattern matching. Zatem w innej wersji, rozwiązanie mogłoby wyglądać następująco:

def to_words(num: Int): String = num match {
  case n if n <= 19 => a0(n-1)
  case n if n <= 99 => if (n % 10 != 0) "%s%s".format(a1((n-20)/10), a0(n % 10 - 1)) else a1((n-20)/10)
  case n if n <= 999 => if (n % 100 != 0) "%shundredand%s".format(to_words(n/100), to_words(n % 100)) else "%shundred".format(to_words(n/100))
  case _ => "out of 1..1000" 
}                                           

val a0 = ("one two three four five six seven eight nine ten eleven twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen").split(' ')
val a1 = "twenty thirty forty fifty sixty seventy eighty ninety".split(' ')

println((for(n <- 1 to 1000) yield to_words(n).length).foldLeft(0)(_ + _))       

Pewnym problemem jest to, że definicje zmiennych a0 i a1 które są wystawione na zewnątrz. Można to ominąć poprzez użycie funkcji jako obiektu i stworzenie w nim wewnętrznej metody.

  def to_words = {
    val a0 = ("one two three four five six seven eight nine ten eleven twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen").split(' ')
    val a1 = "twenty thirty forty fifty sixty seventy eighty ninety".split(' ')                

    def res(num: Int): String = num match {
      case n if n <= 19 => a0(n-1)
      case n if n <= 99 => if (n % 10 != 0) "%s%s".format(a1((n-20)/10), a0(n % 10 - 1)) else a1((n-20)/10)
      case n if n <= 999 => if (n % 100 != 0) "%shundredand%s".format(res(n/100), res(n % 100)) else "%shundred".format(res(n/100))
      case n if n == 1000 => "onethousand" 
      case _ => "out of 1..1000" 
    }
    res _
  }

Taki kod uruchomi inicjację listy słów tylko raz. Jednakże Scala pozwala na bardziej idiomatyczny zapis.

val to_words: Int => String = {
  val a0 = ("one two three four five six seven eight nine ten eleven twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen").split(' ')
  val a1 = "twenty thirty forty fifty sixty seventy eighty ninety".split(' ') 

  (num: Int) => num match {
    case n if n <= 19 => a0(n-1)
    case n if n <= 99 => if (n % 10 != 0) "%s%s".format(a1((n-20)/10), a0(n % 10 - 1)) else a1((n-20)/10)
    case n if n <= 999 => if (n % 100 != 0) "%shundredand%s".format(to_words(n/100), to_words(n % 100)) else "%shundred".format(to_words(n/100))
    case n if n == 1000 => "onethousand" 
    case _ => "out of 1..1000" 
  }
}

W tym wypadku użyto mechanizmu zarówno obiektowego (funkcja jest obiektem) jak i funkcyjnego (pattern matching).

O Scali można sobie podyskutować na polskich kanałach IRC #ruby.pl i (nowo powstałym) #scala.pl (oczywiście anglojęzyczny kanał #scala jest również bardzo pomocny).