Después de leer un artículo sobre Bet you can't solve this Google interview question, me decidí a hacerlo, pero no en JavaScript, sino en Erlang para demostrar que es un buen lenguaje y se puede leer de forma muy fácil, ¿lo vemos?
Antes de nada, el problema:
Tienes una matriz de filas donde tienes diferentes colores, así que tienes que decir el númerro más grande de celdas adyacentes del mismo color.
Primero tengamos claras algunas propiedades de la "celdas adyacentes". Si una celda A es adyacente a B, la celda B es adyacente a la celda A así que tiene la propiedad conmutativa. Pero incluso, si la celda A es adyacente a la celda B y la celda B es adyacente a la celda C, todas ellas están dentro del mismo grupo sin importar si comenzaste a comprobar A, B o C.
También, si un grupo adyacente es mayor que otro no hace falta mantener todos los grupos adyacentes en memoria, no hace falta listarlos, solo necesitamos mantener el mayor encontrado.
El número de colores es variable. Vamos a definir con cuantos colores estamos trabajando:
-define(NUM_COLORS, 3).
colors() -> lists:seq(1, ?NUM_COLORS).
Esta función colors/0 generará 3 diferentes colores para nosotros. Simple hasta el momento. Lo siguiente a generar es la tabla completa. Podemos utilizar el sistema que queramos, el objetivo es generar 10 mil ítems, así que vamos a crear una matriz de 100x100 y elegir un color diferente de la lista de los colores en cada uno de ellos:
-define(MATRIX_X, 100).
-define(MATRIX_Y, 100).
pick_random(List) ->
Index = rand:uniform(length(List)) - 1,
lists:nth(Index + 1, List).
gen_matrix() ->
Colors = colors(),
Rows = lists:seq(1, ?MATRIX_Y),
Cols = lists:seq(1, ?MATRIX_X),
[[pick_random(Colors) || _ <- Cols] || _ <- Rows].Tenemos nuestra matriz. Como puntos extra, podemos comprobar la salida que genera la salida:
color(C) ->
io_lib:format("\e[48;5;~bm \e[0m", [C]).
output(Matrix) ->
lists:foreach(fun(Row) ->
io:format("~s~n", [lists:map(fun color/1, Row)])
end, Matrix).Esto lo conseguimos usando los códigos de escape ANSI.
De esta forma llamando a output/1 obtenemos la salida por pantalla de la matriz generada.
Podemos resolver el problema:
max_adjacent(Matrix) ->
Total = ?MATRIX_X * ?MATRIX_Y,
{Max, _} = lists:foldl(fun check_matrix/2, {0, Matrix}, lists:seq(1, Total)),
Max.
Creamos una función para calcular el máximo número de celdas adyacentes con el mismo color. Usamos Total para calcular la iteración en una sola dimensión y lists:foldl/3 para llamar a check_matrix/2 usando el acumulador {0, Matrix} indicando la primera parte de la tupla como el número máximo de celdas adyacentes y como segunda parte de la tupla la matriz cambiante.
Vamos a echar un vistazo a la función check_matrix/2 para saber cómo funciona:
check_matrix(R, {I, M}) ->
X = R rem ?MATRIX_X,
Y = R div ?MATRIX_X,
Row = lists:nth(Y + 1, M),
V = lists:nth(X + 1, Row),
case V of
undefined -> {I, M};
_ ->
{I2, M2} = check_adjacent({0, M}, X, Y, V),
{max(I, I2), M2}
end.
De nuevo, esta función es lo suficiente pequeña para seguirla de forma fácil. Primero obtenemos X e Y desde R. Entonces, podemos obtener V como el valor contenido dentro de la matriz para la posición de R. Finalmente, llamamos a check_adjacent/4 que comprobará los adyacentes desde la posición dada y retornará una tupla de nuevo con el primer valor como el número máximo de adyacentes encontrado y como segundo valor la matriz modificada.
Ten en mente que check_adjacent/4 es la función que modificará la matriz para cambiar el valor de los colores a undefined para evitar comprobarlos de nuevo en las siguientes llamadas.
El contenido de la función check_adjacent/4 es el que sigue:
replace_at(Index, NewValue, List) ->
{Left, [_OldValue | Right]} = lists:split(Index, List),
Left ++ [NewValue | Right].
check_adjacent({I, M}, X, Y, _V)
when X < 0; X >= ?MATRIX_X; Y < 0; Y >= ?MATRIX_Y -> {I, M};
check_adjacent({I, M}, X, Y, V) ->
Row = lists:nth(Y + 1, M),
case lists:nth(X + 1, Row) of
V ->
Row2 = replace_at(X, undefined, Row),
M2 = replace_at(Y, Row2, M),
I2 = I + 1,
{I3, M3} = check_adjacent({I2, M2}, X, Y - 1, V),
{I4, M4} = check_adjacent({I3, M3}, X - 1, Y, V),
{I5, M5} = check_adjacent({I4, M4}, X, Y + 1, V),
check_adjacent({I5, M5}, X + 1, Y, V);
_Other ->
{I, M}
end.
Como puedes ver, si los valores de X o Y se salen de los valores permitidos, termina la recursión.
La segunda clausura de la función se encarga de comprobar el contenido de la celda. Si sigue teniendo los valores permitidos se continúa la recursividad.
Ahora, rendimieento. Una vez hemos generado una matriz de 3 colores dentro de la variable M podemos ejecutar:
1> M = adjacent_cells:gen_matrix(), ok.
ok
2> timer:tc(fun() -> adjacent_cells:max_adjacent(M) end).
{224270,43}
Para esta ejecución, la función timer:tc/1 retorna una tupla con el primeer elemento como los microsegundos utilizados en la ejecución de la función y como segundo elemento el valor retornado por la función como el número máximo de adyacencias. Como puedes ver, tomó 224 ms para obtener el valor.
Por otro lado, si usamos solo un color y debido a que estamos modificando la matriz con valores undefined, este algoritmo es mucho mejor cuando tenemos un montón de adyacencias y pocos colores. Reduciendo el número de colores solo a uno el algoritmo toma 121 ms para obtener el valor de resultado.
Aquí puedes ver el código al completo:
-module(adjacent_cells).
-export([gen_matrix/0, output/1, max_adjacent/1]).
-define(NUM_COLORS, 3).
-define(MATRIX_X, 100).
-define(MATRIX_Y, 100).
colors() -> lists:seq(1, ?NUM_COLORS).
pick_random(List) ->
Index = rand:uniform(length(List)) - 1,
lists:nth(Index + 1, List).
gen_matrix() ->
Colors = colors(),
Rows = lists:seq(1, ?MATRIX_Y),
Cols = lists:seq(1, ?MATRIX_X),
[[pick_random(Colors) || _ <- Cols] || _ <- Rows].
color(C) ->
io_lib:format("\e[48;5;~bm \e[0m", [C]).
output(Matrix) ->
lists:foreach(fun(Row) ->
io:format("~s~n", [lists:map(fun color/1, Row)])
end, Matrix).
max_adjacent(Matrix) ->
Total = ?MATRIX_X * ?MATRIX_Y,
{Max, _} = lists:foldl(fun check_matrix/2, {0, Matrix}, lists:seq(0, Total - 1)),
Max.
check_matrix(R, {I, M}) ->
X = R rem ?MATRIX_X,
Y = R div ?MATRIX_X,
Row = lists:nth(Y + 1, M),
V = lists:nth(X + 1, Row),
case V of
undefined -> {I, M};
_ ->
{I2, M2} = check_adjacent({0, M}, X, Y, V),
{max(I, I2), M2}
end.
replace_at(Index, NewValue, List) ->
{Left, [_OldValue | Right]} = lists:split(Index, List),
Left ++ [NewValue | Right].
check_adjacent({I, M}, X, Y, _V)
when X < 0; X >= ?MATRIX_X; Y < 0; Y >= ?MATRIX_Y -> {I, M};
check_adjacent({I, M}, X, Y, V) ->
Row = lists:nth(Y + 1, M),
case lists:nth(X + 1, Row) of
V ->
Row2 = replace_at(X, undefined, Row),
M2 = replace_at(Y, Row2, M),
I2 = I + 1,
{I3, M3} = check_adjacent({I2, M2}, X, Y - 1, V),
{I4, M4} = check_adjacent({I3, M3}, X - 1, Y, V),
{I5, M5} = check_adjacent({I4, M4}, X, Y + 1, V),
check_adjacent({I5, M5}, X + 1, Y, V);
_Other ->
{I, M}
end.En tan solo 64 líneas ;-)
