Czwarte Zadanie

14/04/2009

Piąty Element, Szósty Zmysł, Siódme Niebo, Ósma Mila, Dziewiąte Wrota, Dziesiąty Krąg… Nie, nie, nie. Dziś nie o filmach – choć liczebniki porządkowe w tytułach zasługują chyba na osobną notkę – tylko znów o programowaniu. Zgodnie z tytułem wpis poświęcę czwartemu zadaniu projektu Eulera. Nie dlatego, że jest ono szczególnie skomplikowane, ale z powodu ewolucji, jaką przeszedł program służący mi do znalezienia rozwiązania.

Zanim jednak przejdziemy do rzeczy, chciałbym zachęcić do zarejestrowania się i samodzielnego rozwiązania zagadki. Oczywiście można bawić się bez zakładania konta, ale jego posiadanie daje nam później dostęp do opisu rozwiązania oraz odnośnik do wątku zawierającego propozycje innych użytkowników. Na zachętę podpowiem, że znalazłem wśród nich dowód przeprowadzony przy pomocy „kartki i ołówka” – krótszy od niektórych programów.

Tyle wstępu.

Zadanie

Treść zadania, w wolnym tłumaczeniu:

Palindrom liczbowy może być czytany „w obie strony” i za każdym razem otrzymujemy taką samą wartość. Największym palindromem, jaki możemy otrzymać w wyniku mnożenia dwóch, dwucyfrowych liczb jest 9009 = 91 x 99.

Należy odszukać największy palindrom będący iloczynem dwóch liczb trzycyfrowych.

Analiza

Jestem co prawda zwolennikiem metod czołgowych, ale stosowanych z pewną dozą wyczucia. Więc idea dwóch pętli odliczających od 999 do 100 i testowania iloczynu „na okoliczność palindromu” została odrzucona z miejsca.

Najlepiej byłoby stworzyć wszystkie możliwe palindromy, poukładać je w kolejności od największego do najmniejszego i kolejno sprawdzać, czy posiadają odpowiednie dzielniki.

Tylko, ile tego może być? Zobaczmy: Największą wartością jest liczba sześciocyfrowa (999 x 999 = 998001), najmniejszą – pięciocyfrowa (100 x 100 = 10000). Razem daje to jakieś 1798 palindromów, od 997799 do 10001. Potem wystarczy dzielić je przez wartości od 999 do 100 i szukać pierwszego przypadku, gdy otrzymamy w wyniku liczbę całkowitą. Nawet nie będzie tego tak dużo…

Pierwsze podejście

Pokrzepiony na duchu spłodziłem dość duży i – jak później uznałem – zbyt skomplikowany program. Za to działał. Jakoś. Bo na wykonanie swojej pracy potrzebował aż 0.2 sekundy.

main(_input) ->
    Palindromes = gen_pal(9,9,9,[],[]),
    display(lists:map(fun sub_div/1, Palindromes)).
%
%
display([]) ->
    0;
%
display([Head|Tail]) ->
    case Head of
        {N, Divisor} -> io:format("~B ~B ~B ~n", [N, Divisor, N div Divisor]);
        0            -> display(Tail)
    end.

%
%
gen_pal(0,_X,_Y,Table, Table2) ->
    lists:append(Table, Table2);
%
gen_pal(X,Y,Z,Table, Table2) ->
    Pal1 = X*100000 + Y*10000 + Z*1000 + Z*100 + Y*10 + X,
    Pal2 = X*10000 + Y*1000 + Z*100 + Y*10 + X,

    TmpTable  = lists:append(Table, [Pal1]),
    TmpTable2 = lists:append(Table2, [Pal2]),

    case {X,Y,Z} of
        {X,0,0} -> gen_pal(X-1,9,9, TmpTable, TmpTable2);
        {X,Y,0} -> gen_pal(X,Y-1,9, TmpTable, TmpTable2);
        {X,Y,Z} -> gen_pal(X,Y,Z-1, TmpTable, TmpTable2)
    end.
%
%
%
%
sub_div(N) ->
    sub_div(N,999).
%
sub_div(_N,99) ->
    0;
%
sub_div(N,Count) ->
    if
        N rem Count == 0 ->
            filter_values(N,Count);
        true ->
            sub_div(N,Count-1)
    end.
%
%
filter_values(N,Count) ->
    Num = N div Count,
    if
        (Num  99) -> {N, Count};
        true                        -> 0
    end.
%

Co to-to robi? Funkcja gen_pal/5 (czyli gen_pal z pięcioma argumentami) tworzy jednocześnie dwie listy z palindromami. Mógłbym tworzyć jedną, ale wtedy miałbym je uporządkowane na zasadzie 999999, 99999, 998899, 99899. Ponieważ istnieje bardzo duże prawdopodobieństwo, że szukana wartość jest sześciocyfrowa to wykonywanie obliczeń dla mniejszych jest stratą czasu. Więc tworzę dwie, które potem sklejam w jedną, uporządkowaną.

Potem zorientowałem się, że i tak wyszedłem przed orkiestrę, bo nikt (łącznie z autorami) nie zawracał sobie głowy pięciocyfrowymi przypadkami.

Po uzyskaniu listy palindromów resztę pracy załatwia za nas poniższa konstrukcja:

lists:map(fun sub_div/1, Palindromes)

Dla każdego elementu listy Palindromes lists:map/2 wywołuje funkcję sub_div/1 i zamienia dany element wynikiem jej działania. Sama sub_div/1 zwraca albo zero (jeśli nie udało się znaleźć trzycyfrowych dzielników dla danego przypadku) albo parę {Palindrom, Dzielnik} (tak, lista może zawierać i takie rzeczy).

Tak potraktowaną listę przekazujemy do funkcji display/1 która odcina z listy pierwszy element (Head) i sprawdza, czy zawiera parę wartości. Jeśli tak, to kończy pracę. Jeśli zaś znajdzie tam 0, to przekazuje ogon (Tail) do display/1, która odcina od niego pierwszy element… i tak do końca.

Podsumowując: użyłem tutaj paru konstrukcji, z którymi chciałem poćwiczyć (operacje na listach, odcinanie ogona), ale program nie wyszedł zbyt elegancki.

Druga próba

Pomińmy milczeniem kolejną próbę, którą należałoby podsumować słowami: „silne nawyki proceduralne w języku funkcyjnym” i przejdźmy do tego, na czym skończyłem swe działania:

Trzecia wersja

main(_input) ->
    check_pal(9,9,9).

check_pal(X,Y,Z) ->
    Pal = X*100000 + Y*10000 + Z*1000 + Z*100 + Y*10 + X,
    sub_div(Pal,X,Y,Z,999).

%
next_pal(X,Y,Z) ->
    case {X,Y,Z} of
        {0,Y,Z} -> {0,0,0};                % wyjscie bez wyn.
        {X,0,0} -> check_pal(X-1,9,9);
        {X,Y,0} -> check_pal(X,Y-1,9);
        {X,Y,Z} -> check_pal(X,Y,Z-1)
    end.

%
sub_div(_N,X,Y,Z,99) ->
    next_pal(X,Y,Z);

sub_div(N,X,Y,Z,Count) ->
    Num  = N div Count,
    Rest = N rem Count,
    if
        Num > Count -> next_pal(X,Y,Z);
        Num  sub_div(N,X,Y,Z,Count-1);
        Num > 999   -> next_pal(X,Y,Z);
        Rest ==  0  -> {N,Count,N div Count};      % wyjscie z wyn.
        true        -> sub_div(N,X,Y,Z,Count-1)
    end.
%

Jak widać – usunąłem dużo (wszystkie listy i operacje na nich) a dodałem jeden test (wypatrzony w rozwiązaniu): czy pierwszy dzielnik nie jest już mniejszy od wyniku – gdy wiemy już, że 20/10=2, to nie musimy testować tego w drugą stronę..

A ile czasu wykonuje się taki program? Jakieś 0.0016 sekundy. No i wygląda nieco ładniej, prawda?

Dopisek 1

A tutaj znalazłem najzwięźlejszą wersję. Bazuje na koncepcie, który odrzuciłem, ale jest krótka i piękna:

-module(p4).
-export([findLargestProduct/0]).

isPalindromic(N) when is_list(N) ->
  N == lists:reverse(N).

findLargestProduct() ->
  List = [X * Y || X <- lists:seq(100, 999),
                   Y <- lists:seq(100, 999),
                   isPalindromic(integer_to_list(X * Y))],
  lists:max(List).

Jest to także wersja najwolniejsza z zaprezentowanych: potrzebuje średnio 1.3 sekundy.

%d blogerów lubi to: