miércoles, 4 de enero de 2012

TDSL segunda semana

El comienzo del viaje fue plácido pero con nubarrones amenazantes en el horizonte. Como el problema lo veia un tanto complicado para testear con mis conocimientos funcionales, decidí descomponer el problema más allá de lo habitual.

En pocas palabras, lo que hay que hacer es dada una palabra, generar todas las combinaciones según un mapa, los detalles están en http://seguridad-agile.blogspot.com/2011/12/tdsl.html

En php el código es [1], que emite por STDOUT en lugar de acumular, asi que la implementación es un poco menos sencilla de lo que se ve. Ya que lo voy a hacer bien, prescindiré de STDOUT, elevando el nivel de dificultad.

Parte del algoritmo que he implementado consiste en tranformar la palabra provista en un lista con sus posibles combinaciones, por ejemplo "hola" se transforma en:

[ ["h", "H"], ["o","O","0"],["l","L","1"],["a","A","4","@"] ]

El test es

preleet_nothing_test()->
  ?assertEqual([],transform:preleet("")).

preleet_one_simple_char_test()->
  ?assertEqual([[";"]],transform:preleet(";")).

preleet_one_complex_char_test()->
  ?assertEqual([["b","B","8"]],transform:preleet("b")).

preleet_many_mixed_char_test()->
  ?assertEqual([["a","A","4","@"],[";"],["b","B","8"]],transform:preleet("a;b")).


Mi implementación de esto es [2], pero la pongo al final por si querés probarlo.

Sin tener aún el aplomo de encarar lo más duro y a modo de entrenamiento, me desvié con una función que luego me resultará útil para profiling. Lo que hace es dada la lista anterior, calcular la cantidad de combinaciones.

El test es este y la implementación en [3]:

measure_empty_test()->
  ?assertEqual(0,transform:measure([])).

measure_one_element_size_one_test()->
  ?assertEqual(1,transform:measure([["1"]])).

measure_one_element_size_two_test()->
  ?assertEqual(2,transform:measure([["b","B"]])).

measure_two_elements_size_one_test()->
  ?assertEqual(1,transform:measure([["b"],["B"]])).

measure_two_elements_size_two_test()->
  ?assertEqual(4,transform:measure([["b","B"], ["a","A"]])).

measure_arbitrary4_test()->
  ?assertEqual(4,transform:measure([["b","B"], ["c"],["a","A"]])).

measure_arbitrary8_test()->
  ?assertEqual(8,transform:measure([["b","B"], ["c"],["a","A","4","@"]])).


Debo confersar que he pecado. Estuve en un vertiginoso remolino de codificación incompleta, tests que se fueron ajustando al código y viceversa sin ningún resultado. De repentete, a las 4:30 me llevé por delante la solución, que es tan groseramente sencilla, una vez que la conocés, claro, que no sé si ponerla. El problema es que estaba trabajando con partes internas de la implementación usando tdd cuando encontré la solución completa. Ops! tengo el resultado antes que el test, pero juro que no fue a propósito. Asi que este es el test y en [4] la implementación.

leet_a_test() ->
 ?assertEqual(["a","A","4","@"],transform:leet("a")).
leet_aa_test() ->
 ?assertEqual(["aa","aA","a4","a@","Aa","AA","A4","A@","4a","4A","44","4@","@a","@A","@4","@@"],transform:leet("aa")).
leet_bc_test() ->
 ?assertEqual(["bc","bC","b(","Bc","BC","B(","8c","8C","8("],transform:leet("bc")).


Lo único que falta es que dado a->A,@,4, tener A->a,@,4 y etc. pero me parece que lo voy a hardcodear en map/1.


[1] Implementación original en php. No entiendo bien lo que hice ni me interesa mucho. Me parece que el primer foreach agrega mayúsculas y "relaciones inversas", o sea si existe "a"-> "A"  crea o agrega "A"->"a". El segundo foreach genera el array de permutaciones (sea lo que sea) necesario para el string de entrada. Noto una cierta optimización.

$map = array(
    'a'=> array('@','4'),
    'e'=> array('3'),
   etc...
);

$baseArray = str_split($argv[1],1);

foreach ($baseArray as $char) {
    if (!isset($map[$char])) {
        $map[$char][]=$char;
    }

    if (! in_array(strtoupper($char) ,$map[$char] )) {
        $map[$char][]=strtoupper($char);
    }

    if (! in_array($char ,$map[$char] )) {
        $map[$char][]=$char;
    }
}

foreach ($baseArray as $pos=>$char) {
    $permArray[$pos]=$map[$char];
}

emit($permArray,0,'');

function emit(array $permArray, $level, $buffer) {
    if ($level >= count($permArray)) {
        echo "$buffer\n";
        return;
    }
    foreach ($permArray[$level] as $char) {
        emit($permArray, $level + 1, "$buffer$char");
    }
}


[2]  implementación de preleet/1

preleet([]) -> [];
preleet([Head|Tail]) -> [ find([Head], map()) | preleet(Tail) ].


siendo map/1

map() -> [
    {"a",["a","A","4","@"]},
    {"b",["b","B","8"]} ,
    {"c",["c","C","("]},


y el test de find/2

find_a_in_empty_map_test()->
  ?assertEqual(["a"],transform:find("a",[])).

find_a_in_map_first_test()->
  Map = [ { "a", [ "a", "A", "4", "@"] }, {"b", ["b","B"]} , {"c",["c","C","("]}],
  ?assertEqual([ "a", "A", "4", "@"],transform:find("a",Map)).

find_a_in_map_last_test()->
  Map = [ {"b", ["b","B"]} , {"c",["c","C","("]}, { "a", [ "a", "A", "4", "@"] } ],
  ?assertEqual([" "],transform:find(" ",Map)).

find_a_in_map_with_only_a_test()->
  Map = [ { "a", [ "a", "A", "4", "@"] }],
  ?assertEqual(["a","A", "4", "@"],transform:find("a", Map)).

find_something_in_map_without_something_test()->
  Map = [ {"b", ["b","B"]} , {"c",["c","C","("]}],
  ?assertEqual([";"],transform:find(";",Map)).

[3] implementación de measure/1

measure([]) -> 0;
measure(What) -> measure(What,1).
measure([],Total) -> Total;
measure([Load|Tail],Total) -> measure(Tail, length(Load) * Total).


[4] implementación de leet/1

leet(Word)->
  lists:foldl(
    fun (Elem, List) ->
    [ string:concat(X,E) || X <- List, E <-Elem ] end,
    hd(preleet(Word)), tl(preleet(Word) )).

No hay comentarios:

Publicar un comentario