El comentario de anonimo en mi post anterior me ha descubierto una cosa que no conocía: la Programación Competitiva. Yo pensaba que esto era un invento de Google pero resulta que ya estaba inventado. Un gran aporte. Muchas gracias. Le he estado dando bastantes vueltas y he decidido mantener mi mente "virgen" porque lo que me interesa es saber hasta donde puedo llegar con mis limitaciones actuales, no preparame para ganar un concurso. El año que viene ya veremos si opino lo mismo.

Round 1A

Gracias a un "papá miedo" tuve la "suerte" de despertarme a las 3 de la mañana así que aproveché para ver los tres problemas y hacerme una idea de la dificultad. Vi asequibles tanto el "Problem A. Charging Chaos" como el "Problem B. Full Binary Tree" pero el "Problem C. Proper Shuffle" era más difícil.

Al día siguiente vi que el corte estaba en hacer los dos primeros problemas sin cometer equivocaciones así que tomé nota para la siguiente.

Round 1B

Tras haber solicitado el correspondiente permiso marital para poder pasar la tarde frente al ordenador empiezo por el primer problema.

Problem A. The Repeater

Lo que nos piden

En el primer problema nos piden cual es el número mínimo de pasos necesarios para igualar varias cadenas de texto cadenas de texto siguiendo dos reglas:

• Si hay dos caracteres consecutivos iguales se puede eliminar uno de los dos.
• Si hay un caracter se puede duplicar.

Por ejemplo, si tenemos la cadena "aaabcc" y queremos llegar a "abbbcc" tenemos que pasar por "aabcc", "abcc" y "abbcc". ¿Fácil no?

Aquí tenemos unos ejemplos del concurso:

• Caso 1: Cadenas:
  • mmaw
  • maw
  Solución: Case #1: 1
• Caso 2: Cadenas:
  • gcj
  • cj
  Solución: Case #2: Fegla Won
• Caso 3: Cadenas:
  • aaabbb
  • ab
  • aabb
  Solución: Case #3: 4
• Caso 4: Cadenas:
  • abc
  • abc
  Solución: Case #4: 0
• Caso 5: Cadenas:
  • aabc
  • abbc
  • abcc
  Solución: Case #5: 3

La solución

La solución consiste en primero comprobar si el problema tiene solución y en caso de tenerla averiguar cuantos pasos son necesarios para llegar desde una cadena a la otra. Si has hecho este problema probablemente esto te sonará un poco raro pero me explicaré más adelante.

#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import time
 
def getValue(inputFile,dataType="string"):
  line=""
  value=0
  while len(line)< 1:
    line=inputFile.readline()
 
  if dataType=="string":
    value=line.split()[0]
  elif dataType=="integer":
    value=int(line.split()[0])
  elif dataType=="float":
    value=float(line.split()[0])
 
  return value
 
def reducedCase(case):
  char=""
  reduced=""

  i=0
  while i< len(case):
    if not(char==case[i]):
      char=case[i]
      reduced=reduced+char
    i=i+1

  return reduced

def testPossible(cases):
  # For each case test if removing duplicates make them the same
  reduced=reducedCase(cases[0][0])
  possible=1
  i=1
  while i< len(cases) and possible==1:
    if not(reduced==reducedCase(cases[i][0])):
      possible=0
    i=i+1
  return possible

def convert(case1, case2):
  # Try to find the number of steps to translate case1 to case2
  steps=0

  diff=0
  i=0
  j=0
  char=case1[0]
  while i< len(case1) and j< len(case2):
    found=0
    while i< len(case1) and found==0:
      if char==case1[i]:
        i=i+1
      else: 
        found=1
    found=0
    while j< len(case2) and found==0:
      if char==case2[j]:
        j=j+1
      else:
        found=1
    steps=steps+abs(i-j-diff)
    diff=abs(i-j)

    if i< len(case1):
      char=case1[i]
  return steps
   
### solve it! ###
def solveIt(cases):
  res=1

  # Reducir duplicados en todos y comprobar que sale la misma cadena para ver si
  # es posible resolverlo
  possible=testPossible(cases)
  if possible==1:
    i=1
    while i< len(cases):
      #Elegir uno como plantilla e igualar el resto.
      steps=convert(cases[0][0],cases[i][0])
      cases[i][1]=steps
      i=i+1

    res=0
    for case in cases:
      if case[1]>res:
        res=case[1]
  else:
    res=-1
 
  return res
 
if __name__=='__main__':
  # Open input and output files
  inputFile=open(sys.argv[1],'r')
  outputFile=open(sys.argv[2],'w')
 
  # Get number of cases
  NoC=int(getValue(inputFile))
  # for each case
  for i in range(NoC):
    # get case data
    inputs=getValue(inputFile,"integer")
    cases=[]
    while inputs>0:
      case=getValue(inputFile,"string")
      cases.append([case,-1])
      inputs=inputs-1
    # solve problem
    res=solveIt(cases)
 
    # write data
    if res==-1:
      outputFile.write("Case #"+str(i+1)+": Fegla Won\n")
      print "Case #"+str(i+1)+": Fegla Won"
    else:
      outputFile.write("Case #"+str(i+1)+": "+str(res)+"\n")
      print "Case #"+str(i+1)+": "+str(res)
 
  # Close input and output files
  inputFile.close()
  outputFile.close()

Resultados

En el ejemplo que viene la entrada es:

5
2
mmaw
maw
2
gcj
cj
3
aaabbb
ab
aabb
2
abc
abc
3
aabc
abbc
abcc

Y la salida correcta es:

Case #1: 1
Case #2: Fegla Won
Case #3: 4
Case #4: 0
Case #5: 3

Sin embargo a mi me sale mal el último resultado y me empiezo a poner nervioso:

Case #1: 1
Case #2: Fegla Won
Case #3: 4
Case #4: 0
Case #5: 2

19:45

"La cagamos Luis"

... dijo Carlos Sainz cuando se enteró de que su motor llevaba estando defectuoso desde la salida.

Resuelvo el problema que he descrito pero no el que me piden y a estas horas ya no me da tiempo a rectificar.

Para resolver el problema hay que tener en cuenta todas las cadenas simultáneamente y yo las he tenido en cuenta de una en una

En el último caso yo obtengo como resultado 2 porque aabc->abc->abbc y aabc->abc->abcc . Así que como mucho necesito dos pasos pero lo que en realidad hay que hacer entiendo es pasar a la vez todas las cadenas a una sóla de esta forma:

["aabc","abbc"]->["abc","abbc"]->["abc","abc"]->["abcc","abcc"]

Y de ahí salen los tres pasos.

No tengo tiempo para volver a rediseñar el programa así que se acabó esta ronda para mí.

¿Round 1C?

"En habiendo agotado" todos los permisos maritales que tenía para el Google Code Jam, me tengo que retirar de esta convocatoria así que ya veremos el año que viene si aprendo a leer.

Creo que me tendré que conformar con presentarme al Tuenti Challenge 4 y acabar mi curso de mongodb para desarrolladores y mi curso de mongodb para administradores avanzados.