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!