Hacker Cup 2013: Cadenas Bellas

¡Que empiecen los juegos! ... bueno, ya hace 72 horas de eso, pero ha sido emocionante. Este es el primer año que me ha dado por participar en la Facebook Hacker Cup y tengo que decir que me ha fascinado. No recuerdo haberme enfrentado a problemas tan complejos desde mi época de programación en la universidad, en las asignaturas de Programación III o más recientemente en Programación y Estructuras de Datos Avanzadas.

Actualizado 02/07/2021: si quieres saber más sobre Erlang/OTP puedes adquirir los dos volúmenes de Erlang/OTP: Un mundo concurrente donde se habla del lenguaje y los elementos de la máquina virtual (BEAM) y Las Bases de OTP donde se habla de este framework para construir aplicaciones.

Como estoy últimamente volcado con Erlang, he resuelto los ejercicios marcados empleando Erlang... y a modo de scripting, para que fuese más fácil su ejecución. La verdad es que me ha fascinado nuevamente lo fácil que ha sido realizar este tipo de tareas con Erlang. Pondré como ejemplo el primer ejercicio: beautiful strings.

Según el enunciado:

Cuando John era pequeño no tenía mucho que hacer. No tenía Internet, ni Facebook, ni programas que hackear. Así que hizo la única cosa que podía hacer... evaluó la belleza de cadenas en una búsqueda para descubrir la cadena más bella del mundo.

Dada una cadena s, el pequeño John definió la belleza de la cadena como la suma de la belleza de las letras contenidas en ella.

La belleza de cada letra es un entero entre 1 y 26, inclusivo, y no hay dos letras que tengan la misma belleza. Johnny no se preocupó acerca de si las letras estaban en mayúscula o minúscula, así que eso no afectaba a su belleza. (F mayúscula es exactamente igual de bella que f minúscula, por ejemplo).

Tu eres un estudiante escribiendo un informe sobre la juventud de John. Encuentras la cadena que Johnny consideró más bella. ¿Cuál es el máximo valor posible de esta cadena?

Los datos que dan como entrada son los siguientes:

5
ABbCcc
Good luck in the Facebook Hacker Cup this year!
Ignore punctuation, please :) 
Sometimes test cases are hard to make up.
So I just go consult Professor Dalves

Siendo la primera línea un número entero que indica la cantidad de líneas que hay en el fichero. El código que ejecute con esta información de entrada debe generar esta salida:

Case #1: 152
Case #2: 754
Case #3: 491
Case #4: 729
Case #5: 646

Teniendo en cuenta de que solo cuentan las letras y que se busca que cada línea tenga el máximo valor posible, tomamos como ejemplo la primera línea: ABbCcc. Esta línea tiene:

3c + 2b + a = 152

Si sabemos que hay 26 letras en el abecedario y que ninguna letra tiene el mismo valor, podemos llegar a despejar la ecuación con:

3(26) + 2(25) + 24 = 152.

Estos son los valores máximos que podemos conseguir con la primera línea. Por tanto, el programa debe de tomar las letras, su repetición, ordenarlas de mayor repetición a menor repetición, asignarles los valores del 26 al 1 y sumarlos. Esto nos da el resultado que buscamos.

El código en Erlang es así:

##!/usr/bin/env escript

main([File]) ->
    {ok, Pid} = file:open(File, [read]),
    {ok, Num} = file:read_line(Pid),
    Number = to_int(Num),
    lists:map(fun(I) ->
        {ok, L} = file:read_line(Pid),
        Letters = counter(cleaner(L)),
        SortedLetters = lists:sort(fun({_,A},{_,B}) ->
            A > B
        end, Letters),
        Sum = summa(SortedLetters, 26),
        io:format("Case #~w: ~w~n", [I, Sum])
    end, lists:seq(1,Number)),
    ;
main(_) ->
    io:format("Usage: beautiful <inputfile>~n"),
    1.

%% do the sums:

summa(Letters, Mul) ->
    summa(Letters, Mul, ).

summa([], _Mul, Sum) ->
    Sum;
summa([{_L,T}|Letters], Mul, Sum) ->
    summa(Letters, Mul-1, Sum+T*Mul).

%% set the data to work with them:

counter(Line) ->
    counter(Line, []).

counter([], Letters) ->
    Letters;
counter([H|T], Letters) ->
    Num = length([ X || X <- T, X =:= H ]) + 1,
    counter([ X || X <- T, X =/= H ], [{H, Num}|Letters]).

%% Functions to clear data from file:

to_int(Num) ->
    list_to_integer(lists:filter(fun(X) ->
        X >= $0 andalso X =< $9
    end, Num)).

cleaner(Line) ->
    lists:map(fun
        (Y) when (Y >= $a andalso Y =< $z) -> Y;
        (Y) -> Y + ($a - $A)
    end, lists:filter(fun(X) ->
        (X >= $a andalso X =< $z) orelse
        (X >= $A andalso X =< $Z)
    end, Line)).

Todo lo empleado en este código se explica de forma clara en el libro Erlang/OTP Volumen I.

Hay dos ejercicios más que completan la primera ronda de esta Hacker Cup 2013. En los siguientes días los subiré con explicaciones. Si queréis realizar algún comentario, mejora o sugerencia al mismo, no dudéis en comentarlo en esta misma entrada.