o Ruby

Muszę przyznać, że od zawsze uwielbiałem zadania, które wymagają myślenia, główkowania i kombinowania. W okresie mojej podstawówki dotyczyło to głównie rozwiązywania zadań z matematyki, potem (gdy tylko zetknąłem się z informatyką w LO) przeszło to na zadania algorytmiczne. To były zresztą moje początki z programowaniem i do dzisiaj mam ogromny sentyment do tej dziedziny informatyki.

Ostatnio na forum rubyonrails.pl zaproponowano, by rozwiązywać zadania ze strony o nazwie "Project Euler". Jak się okazało zadania są na pograniczu matematyki, logiki, kombinatoryki, algorytmiki i większość ma tę własność, że bez pomocy komputera nie da się ich rozwiązać.

To co mnie urzekło od samego początku to fakt, że nie zawsze chodzi o znalezienie najbardziej wydajnego rozwiązania. Nie ma bowiem narzuconego z góry żadnego limitu (na stronie musimy podać otrzymane rozwiązanie i sprawdzana jest jego poprawność). Często naiwne rozwiązanie wystarcza, co nie znaczy, że napisanie programu jest banalne! Barierą może być sam język, w którym piszemy. Sporo zadań wymaga obliczeń na dużych liczbach lub operowania danymi tekstowymi, co może okazać się bardzo niewygodne (nie mylić z "niemożliwe") w takich językach jak C/C++ czy Java. Z kolei te same zadania okazują się przysłowiową "bułką z masłem" jeśli użyjemy wysokopoziomowych języków, np. Ruby lub Python (jeśli oczywiści dana funkcjonalność występuje).

Weźmy dla przykładu zadanie 13ste, w którym chodzi o zsumowanie stu 50-cio cyfrowych liczb. Do reprezentacji takich liczb potrzeba około 167 bitów, a więc taki typ (znany np. z C, Javy) jak long po prostu odpada. Nawet jak przebrniemy przez ten problem (możemy napisać własną obsługę dużych liczb lub użyć gotowej biblioteki, np. gmp) to musimy poradzić sobie z przetworzeniem tekstu zawierającego te liczby. I znowu okaże się, że w przypadku języka C (i nie tylko) takie operacje są dosyć uciążliwe.

Spójrzmy na rozwiązania tego samego problemu w językach Java i Ruby:

import java.io.IOException;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.File;
import java.math.BigInteger;
import java.util.ArrayList;

public class E013 {
  public static BigInteger sumOf(Iterable<BigInteger> numbers) {
    BigInteger sum = new BigInteger("0");

    for (BigInteger number: numbers) {
      sum = sum.add(number);
    }
    return sum;
  }

  public static void main(String[] args) throws IOException {
    BufferedReader reader = new BufferedReader(new FileReader(new File("013.txt")));
    String line;

    ArrayList<BigInteger> numbers = new ArrayList<BigInteger>();
    while ((line = reader.readLine()) != null) {
      numbers.add(new BigInteger(line));
    }
    BigInteger sum = sumOf(numbers);
    System.out.println(sum.toString().substring(0, 10));
  }
}

puts File.read("013.txt").split("\n").inject(0) {|sum, n| sum + n.to_i }.to_s[0, 10]

Bo czasem jabłko jest lepsze od gruszki

Tak, to są równoważne programy! Oba robią to samo: wczytują kolejne linie z pliku 013.txt, konwertują je na liczby i sumują. Być może dla programistów niezaznajomionych z Ruby, wersja w tym języku może wydawać się trudna w odczytaniu, ale zapewniam Was, że tak nie jest. Wystarczy szybkie przeskanowanie tej jednej linijki by przekonać się, że program składa się z pięciu kroków: wczytaj z pliku (File.read("013.txt")), skonwertuj do tablicy dzieląc wedle znaku nowej linii (split("\n")), zsumuj skonwertowane do liczby kolejne linie (inject(0) {|sum, n| sum + n.to_i }), skonwertuj do łańcucha (to_s) i pobierz pierwsze 10 znaków ([0, 10]).

Wspomniany inject, który w tym wypadku sumuje liczby (arr.inject(0){|sum, item| sum + item }, jest już klasycznym idiomem tego języka.

A czasem i nawet gruszka lepsza od jabłka

Z kolei weźmy zadanie 5te, w którym musimy znaleźć najmniejszą liczbę naturalną, która będzie podzielna bez reszty przez wszystkie liczby całkowite z zakresu 1..20. Pozostańmy przy naiwnym rozwiązaniu, które wynika wprost z zadania. Sprawdzając kolejne liczby 2, 3, 4, 5 będziemy testować czy dzieli się bez reszty przez liczby z zakresu 2..20 (1 omijamy bo wiemy, że każda liczba całkowita jest podzielna przez nią bez reszty). Zacznijmy tym razem od wersji w Rubym.

puts 1.upto((2..20).inject(:*)).each {|n| break n if (2..20).all? {|e| n % e == 0} } 

Odpalając ten program na ruby1.9 dostaję odpowiedź po ponad 3 minutach. Na ruby1.8 nawet nie sprawdzam - będzie na pewno jeszcze dłużej. Spójrzmy zatem na rozwiązanie w javie.

public class E005 {
  public static long product(int from, int to) {
    long result = 1;
    for (int i = from; i < to; i++) {
      result *= i;
    }
    return result;
  }

  public static boolean isDivisibleBy(long number, int[] divisors) {
    for (int divisor: divisors) {
      if ((number % divisor) != 0) {
        return false;
      }
    }
    return true;
  }

  public static void main(String[] args) {
    long min = 1;
    long max = product(2, 20);
    int[] divisors = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};

    for (long i = min; i <= max; i++) {
      if (isDivisibleBy(i, divisors)) {
        System.out.println(i);
        break;
      }
    }
  }
}

Tym razem dostaję odpowiedź po około 10 sekundach. Oczywiście znowu wymagało to dłuższego kodu, ale zdecydowanie wolę czekać 10 sekund niż 3 minuty...

Nie myślcie, że te dwa przykłady mają prowadzić do wielkiej konkluzji. Raczej chodzi o pokazanie, co tracimy/zyskujemy decydując się na dany język. Java i Ruby są tu tylko przykładem. Mógłbym równie dobrze pokazać rozwiązania w Pascalu, Php, Pythonie czy też Erlangu (myślę, że to mogłoby być bardzo ciekawe doświadczenie). Zachęcam Was spróbowania własnych sił. Spróbujcie rozwiązywać te same zadania w kilku językach i wyciągajcie własne wnioski.

Ucz się sztuki programowania od innych

Ktoś kiedyś powiedział, że najważniejszym źródłem wiedzy jesteśmy my. Możemy uczyć się na własną rękę, ale i tak najwięcej nauczymy się od innych. Ta prawda sprawdza się idealnie jeśli chodzi o programowanie (czy też wiedzę związaną z komputerami). Niezależnie od użytego języka, praktycznie każdy problem można rozwiązać na mnóstwo sposobów, które będą mniej lub bardziej dobre. Czasem to kwestia znajomości standardowej lub zewnętrznej biblioteki, dobrze wykorzystanego API czy też zastosowanego algorytmu.

Dzięki tym zadaniom i rozwiązaniom innych mogłem przekonać się o potędze biblioteki prime dostępnej od wersji 1.9 Rubiego. Zadania, które wymagają operowania na liczbach pierwszych, czynnikach pierwszych lub podzielnikach liczb okazują się banalnie proste, jeśli mamy pod ręką taką bibliotekę (a z Ruby 1.9 mamy!).

Przykładowe zadanie i wykorzystanie tej biblioteki:

http://projecteuler.net/index.php?section=problems&id=3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

require "prime"

puts 600851475143.prime_division.max.first

Nawet jeśli takie przykłady można skwitować stwierdzeniem "to tylko kwestia biblioteki" to dla mnie bardzo ważny jest fakt, że na poziomie języka i jego standardowej biblioteki mogę zrobić

2**1000 + 15

aniżeli

System.out.println(new BigInteger("2").pow(1000).add(new BigInteger("15")));

Zapraszam Was do wspólnego rozwiązywania zadań i umieszczania ich w przygotowanym dziale na forum.rubyonrails.pl. Część moich rozwiązań znajdziecie w repozytorium gita na githubie.