28 jun 2008

Un laberinto

Te encuentras parado afuera de un laberinto perfecto. Un laberinto se denomina "perfecto" si cumple las siguientes condiciones:
  1. Esta compuesto por una malla rectangular de habitaciones, F filas por C columnas (R rows by C columns).
  2. Tiene exactamente dos salidas hacia fuera del laberinto: la entrada y la salida. La entrada esta siempre en la pared norte, mientras que la salida puede estar en cualquier pared.
  3. Existe exactamente una ruta entre dos habitaciones cualesquiera en el laberinto(esto es, exactamente una ruta que no involucre un retroceso).
Has decidido resolver el laberinto perfecto utilizando el algoritmo "voltear siempre a la izquierda", que indica que debes tomar la desviación más a la izquierda en cada oportunidad. Si encuentras una ruta sin salida, volteas dos veces (180 grados en el sentido horario) y continuas. (Si sacas la mano izquierda y tocas la pared mientras sigues este algoritmo, resolveras el laberinto sin siquiera perder contacto con la pared). Cuando has terminado el laberinto, decides realizar un paso adicional y resolverlo nuevamente (siempre volteando a la derecha), pero empezando desde la salida y terminando en la entrada.

La ruta que tomas a través del laberinto puede ser descrita con tres caracteres: 'W' significa caminar hacia delante hacia la siguiente habitación, 'L' significa voltear 90 grados a la izquierda (o en sentido antihorario), y 'R' significa voltear 90 grados a la derecha (o en sentido horario).

Inicias directamente fuera de la entrada, de frente al laberinto. Finalizas cuando has salido fuera del laberinto a través de la salida.


Problema

Por ejemplo si la entrada esta en el norte y la salida en el oeste, tu ruta de salida a través del laberinto mostrado sería

WRWWLWWLWWLWLWRRWRWWWRWWRWLW

Si la entrada y la salida fueran invertidas, de modo tal que iniciaras fuera de la pared este y finalizaras fuera de la pared norte, tu ruta sería:

WWRRWLWLWWLWWLWWRWWRWWLW

Dadas lass dos rutas a través del laberinto (entrada hacia salida y salida hacia entrada), tu código debe retornar una descripción del laberinto.

Entrada

La primera línea de la entrada provee el número de casos, N. Siguen los N casos de prueba. Cada caso es una línea con el formato:

entrada_a_salida salida_a_entrada

Todas las rutas tendrán al menos dos caracteres de largo, compuestas solamente por los caracteres 'W', 'L', y 'R', y empezando y finalizando en 'W'.

Salida

Para cada caso de prueba, la salida debe mostrar una línea "Case #x:" por sí misma. Las siguientes F lineas (R lines) otorgan una descripción del laberinto F x C (R by C).
Cada línea debe tener C caracteres, cada uno representa las direcciones en las cuales es posible acceder a esa habitación. Vea la siguiente leyenda:
Caracter Norte? Sur? Oeste? Este?
1NoNoNo
2NoNoNo
3NoNo
4NoNoNo
5NoNo
6NoNo
7No
8NoNoNo
9NoNo
aNoNo
bNo
cNoNo
dNo
eNo
f



Limites

1 ≤ N ≤ 100.

Conjunto de datos pequeño

2 ≤ longitud(entrada_a_salida) ≤ 100,
2 ≤ longitud(salida_a_entrada) ≤ 100.

Conjunto de datos grande

2 ≤ longitud(entrada_a_salida) ≤ 10000,
2 ≤ longitud(salida_a_entrada) ≤ 10000.

Ejemplo

Entrada
2
WRWWLWWLWWLWLWRRWRWWWRWWRWLW WWRRWLWLWWLWWLWWRWWRWWLW
WW WW

Salida
Case #1:
ac5
386
9c7
e43
9c5
Case #2:
3

17 jun 2008

Firefox 3 Download Day

Hoy es el día, a partir de las 12:00 horas (hora de Perú) tendremos la posibilidad de descargar la última versión de Mozilla Firefox, adicionalmente podremos ayudar a que este programa establezca el record mundial de descargas en un solo día.
Download Day - Spanish
Actualización
1. Puedes descargarlo aqui o haciendo clic en la imagen.
2. Luego de descargar e instalar Firefox 3, puedes obtener tu certificado.

6 jun 2008

La muerte es el mejor invento de la vida

El titulo de este post puede llevarlos a pensar que me equivoqué de blog, un blog sobre tecnología no admite este tipo de temas podría pensar más de uno. Pues me temo que es una seria pérdida de perspectiva el creernos que la tecnología no tiene un lado humano y existencial. Toda la tecnología, desde las primeras puntas de flecha hasta los telescopios espaciales, tiene como origen y destino al ser humano.

A pesar de lo dicho, lo que quiero compartir con ustedes en esta ocasión no se adentrará en los dominios de la filosofía, la frase que sirve de título a este post es parte del discurso que Steve Jobs pronunció en el inicio del año académico 2005 en la Universidad de Standford, si bien es un discurso relativamente conocido, la novedad para mi fue encontrarlo subtitulado en español.

Si en algo los llega a tocar este discurso no duden en poner su respectivo comentario.



El discurso en inglés