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)(_ + _))                                                                          
Kod
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).

Tagi , , , , , ,  | 7 comments

Comments

  1. Avatar Wiki powiedział about 11 hours later:

    Nie wspominajac o tym, ze rozwiazanie, ktore przedstawiles z forum jest kompletnie nieoptymalne i wolne. To moze wlasnie dlatego Ruby jest wolny? =) Poniewaz optymalne rozwiazanie moze miec (o zgroza) troche wiecej linijek kodu :).

  2. Avatar Jarosław Zabiełło powiedział about 12 hours later:

    Moim zdaniem, wydajność w tych zadaniach nie jest zasadnicza. Chodzi bardziej o prostotę i elegancję rozwiązania.

  3. Avatar Mekk powiedział about 13 hours later:

    IMO publikowanie rozwiązań problemów z eulera jest co najmniej nieeleganckie, te zadania stale wiszą do rozwiązania, można nimi punktować.

    PS A sam project euler bardzo polecam

  4. Avatar calder powiedział about 14 hours later:

    Zgadzam się z Jarkiem, że nie chodzi tu tyle o optymalność wydajnościową co o czytelną prezentację algorytmu. Oczywiście z głową, nie chodzi o znajdowanie rozwiązań brute-forcem (co czasami jest wręcz niewykonalne, vide problem 67), ale też nie można przeginać i pisać kodu, który jest 3 razy dłuższy tylko po to, żeby znaleźć wynik kilka sekund szybciej :) Ja sam mam na koncie 19 rozwiązanych zadań w różnych językach programowania (od Erlanga poprzez Ruby po Groovy) i muszę powiedzieć, że takie ćwiczenie zawsze bardzo mi pomogało po pierwsze poznać dany język, a po drugie zdumiewająco szybko wychodziły na wierzch jego różne wady i zalety. Dzięki PE bardzo ładnie widać na przykład na ile łatwo i zwięźle dany język pozwala przełożyć ideę człowieka na postać zrozumiałą przez maszynę – wystarczy porównać przykładowe rozwiązanie problemu nr 1 w Pythonie i C++ dostępne na Wikipedii.

  5. Avatar Piotr Meyer powiedział 4 days later:

    Pozwoliłem sobie uzupełnić coś, czego zabrakło mi w powyższej notce i wyklepałem przykład w Erlangu.

  6. Avatar Dodek powiedział 2 months later:

    CL-USER> (format nil “~R” 21245) “twenty-one thousand two hundred forty-five”

    Z Common Lispem to zadanie jest az za łatwe.

  7. Avatar calder powiedział about 1 year later:

    Uno po pierwsze to nie jest pełne rozwiązanie w CL, kompletny kod będzie wyglądać np. tak:

    (format t “a” (length (remove #\Space (remove #\- (with-output-to-string (out) (loop for i from 1 to 1000 do (format out “r” i)) out)))))

    Uno po drugie zadziała jedynie dla języka angielskiego :)

(leave url/email »)

   Pomoc języka formatowania Obejrzyj komentarz