Alien fingers en Prolog

Hace pocos días me encontré con el problema de "Alien fingers" en mi TL de Twitter. Se trata de un sencillo problema, que podemos resolver en Prolog de forma 100% declarativa.

El puzzle, escrito por Chris Maslanka, viene a decir que los aliens usan notación hexadecimal para escribir números. Resulta que el número que escribieron, era de dos dígitos y era muy curioso, porque su valor era el mismo que los dígitos invertidos en notación decimal. ¿Qué número era?.

Para encontrar la respuesta en Prolog, primero vamos a definir la notación hexadecimal, para ello usaremos DCGs.

La DCG en cuestión describirá, para un número N, su representación en hexadecimal con dos dígitos.

:- use_module(library(dcgs)).
:- use_module(library(clpz)).

hex_number(N) -->
    hex(A),
    hex(B),
    {
        N #= B + A*16
    }.

hex(0) --> "0".
hex(1) --> "1".
hex(2) --> "2".
hex(3) --> "3".
hex(4) --> "4".
hex(5) --> "5".
hex(6) --> "6".
hex(7) --> "7".
hex(8) --> "8".
hex(9) --> "9".
hex(10) --> "A".
hex(11) --> "B".
hex(12) --> "C".
hex(13) --> "D".
hex(14) --> "E".
hex(15) --> "F".

Básicamente, hex_number de N describe la lista compuesta de hex(A) y hex(B). hex de N describe a su vez un caracter, siendo N el número que que representa (del 10 al 15 usamos de la A hasta la F). Finalmente calculamos el valor numérico del número representado.

Esta DCG se puede usar en muchos sentidos. Podemos usarla para generar todos los númeroe hexadecimales de 2 dígitos, para parsear un número en notación hexadecimal o para generar la representación hexadecimal de un número.

Para los números decimales es igual pero más sencillo ya que es nuestra notación natural

dec_number(N) -->
    dec(A),
    dec(B),
    {
        N #= B + A*10
    }.

dec(0) --> "0".
dec(1) --> "1".
dec(2) --> "2".
dec(3) --> "3".
dec(4) --> "4".
dec(5) --> "5".
dec(6) --> "6".
dec(7) --> "7".
dec(8) --> "8".
dec(9) --> "9".

Ahora simplemente necesitamos algo para que las representaciones se puedan invertir. En Scryer Prolog, podemos tratar los strings como listas a todos los efectos, es por ello que podemos usar el predicado reverse/2. Sin embargo, como este caso es muy sencillo, podemos usar un predicado casero que solo sirva para invertir listas de dos elementos. Se haría así:

inv([A, B], [B, A]).

Ahora ya podemos resolver el puzzle. Simplemente escribimos el enunciado del problema en Prolog

puzzle(Hex) :-
    phrase(hex_number(N), Hex), % Un número N en notación hexadecimal Hex que...
    inv(Hex, Dec), % Invirtiendo los caracteres ...
    phrase(dec_number(N), Dec). %  es igual al mismo número N pero en notación decimal

¡Y obtenemos los resultados!

Nos da dos soluciones, una trivial de "00" y otra, más interesante de "35". "35" en hexadecimal representa el número 53, que en notación decimal se escribe como "35" pero invertido. ¡Ese es el número que escribieron los aliens!