Google CodeJam 2008 i els nombres extraterrestres

Fa un parell de setmanes (el cap de setmana abans de l’examen de Fonaments Físics de la Informàtica) em vaig assabentar que els de Google organitzaven un campionat d’algorísmica i dic: “Coi, vaig a apuntar-me a veure quin tipus de problemes plantegen”. Aprofitant els moments en que la idea del suïcidi em passava pel cap (vaig estar el cap de setmana sol al pis sense sortir, no proveu mai d’estar dos dies sense parlar amb cap humà…) em vaig posar a llegir els problemes que estaven plantejats per al període de proves i vaig resoldre el primer de quatre (el fàcil, clar).

El problema que es plantejava era un simple canvi de base entre dos sistemes de numeració, tradueixo la descripció del problema:

El sistema numèric decimal està composat per deu dígits, els quals representem com “0123456789″ (els dígits en un sistema estan escrits del menor al major). Imagina que has descobert un sistema numèric extraterrestres compost per uns quants dígits numèrics, els quals poden ser o no els mateixos del sistema decimal. Per exemple, si el sistema numèric extraterrestres es representa com “oF8″, els nombres de l’1 al 10 serien (F, 8, Fo, FF, F8, 8o, 8F, 88, Foo, FoF). Voldríem poder treballar amb nombres d’un sistema extraterrestres arbitrari. Més generalment, volem ser capaços de convertir un nombre qualsevol que està escrit en un sistema extraterrestres, a un altre sistema extraterrestres.

El que se me va ocòrrer a mi va ser generalitzar els canvis de base binari-decimal i decimal-binari i xim-pum. Tant senzill com això. En la meva solució faig un canvi de base del sistema extraterrestre d’entrada a decimal i després de decimal al sistema extraterrestre de sortida. Per què? Doncs no sé, perquè se me va ocórrer de fer així i és el que estic acostumat a fer per passar d’hexadecimal a decimal o a binari. Però en principi no hi ha cap problema per fer una conversió directa entre els dos sistemes, sols has de saber fer-ho i jo no m’he aturat a pensar-ho.

Per programar la solució vaig utilitzar el llenguatge C++, que tenia ganes de provar-lo i el qual segurament utilitzaré aquest estiu per a un xicotet projecte pendent que tinc (ja us parlaré d’ell, però està relacionat amb el Número de Bacon) i que és el llenguatge utilitzat en Estructures de Dades i Algorismes (EDA), una assignatura que tindré l’any que ve i que, no vaig a enganyar-vos, tinc ganes de cursar (disculpeu la meva  els que us heu tingut que enfrontar a ella…). Una de les estructures implementades en la llibreria STL de C++ que he utilitzat és el map (mapa, per als qui necessiteu traducció ¬¬), que no sé quina diferència presenta respecte d’una taula Hash. L’he utilitzada per relacionar un símbol del sistema extraterrestre d’entrada amb un valor i poder així operar amb ells.

En fi, ací teniu la solució (que és correcta) i uns exemples de canvi de base:

• Nombre: 9; Sistema d’entrada: 0123456789; Sistema de sortida: oF8; Solució: Foo
• Nombre: Foo; Sistema d’entrada: oF8; Sistema de sortida: 0123456789; Solució: 9
• Nombre: 13; Sistema d’entrada: 0123456789abcdef; Sistema de sortida: 01; Solució: 10011
• Nombre: CODE; Sistema d’entrada: O!CDE?; Sistema de sortida: A?JM!.; Solució: JAM!
• Nombre: eEEeeeEEeeeEeE…E; Sistema d’entrada: E.e; Sistema de sortida: !0TtKXJ]hZi_|Q8sg[>~DNAnWx$Gf%,k"2L&ydYB; Solució: T$|gB~
• Nombre: <-"i4g; Sistema d'entrada: m<zqSI#F2]$`”9+~4>kQxoGV{?T;7yvR_l3B-ti/ag6.%ews[8; Sistema de sortida: u%v; Solució: %%u%%vu%u%vvu%%u%vv

La primera fase de la competició, la de qualificació, és el pròxim 16 de Juliol de les 23:00 UTC fins el 17 de Juliol a la mateixa hora (la fase dura 24h). Tinc curiositat per veure els problemes que plantegen, però no crec que sàpiga resoldre’n cap. No sé prou d’algorísmica. Per a que us feu una idea, el quart problema de la fase d’entrenament d’on he tret el problema anterior, és el següent:

Teniu una llista d’objectes a comprar avui, i sabeu els llocs (representats per punts en uns eixos cartesians) d’unes poques tendes en l’àrea. Sabeu també quines coses de la vostra llista ven cada tenda i a quin preu ho venen. Donat el preu de la gasolina, quina és la mínima quantitat de diners que necessiteu per comprar tots els objectes i tornar a casa? Comences i acabes a la teva casa, que està en la posició (0,0) dels eixos cartesià.

Per fer les coses més interessants, alguns dels objectes en la llista es poden fer malbé. Quan compreu un o més d’aquests productes, no podeu conduir fins una altra tenda sense abans passar per casa. Tots els objectes de la vostra llista es troben en alguna tenda, per tant el viatge sempre és possible.

Aquest problema ja és xunguet, almenys per als coneixements que tinc jo. Em recorda al problema del carter xinès o algun paregut, un famós problema del qual he sentit parlar per la xarxa mare i no tinc ni idea de com es resol. S’agrairia als visitants que han fet Algorísmica (que sé que hi han) que ens contaren alguna cosa a través dels comentaris…