Google Code Jam 2013 ... con obstáculos

Submitted by elmanytas on

07:30 Me dispongo a participar en el Google Code Jam 2013 donde los obstáculos son mi mujer y mis dos hijos, lo que lo hace muuuucho más interesante. ;-) Llegaré hasta donde mis circunstancias me dejen llegar. Para el que no conozca de qué va la cosa el Google Code Jam es un concurso de resolución de problemas que organiza Google todos los años. Iré poniendo mis soluciones por aquí pero no las publicaré hasta mañana por motivos obvios.

Leyendo los problemas

Dado que mi intención no es ganar sino ir pasando de ronda tengo que hacer una primera lectura de los problemas para hacerme una idea de su dificultad e ir haciéndolos de más fácil a más difícil. 07:58 He tardado media horita en leer los cuatro problemas y entenderlos.

Problem A. Tic-Tac-Toe-Tomek

Este problema consiste en, dado un tablero de Tic-Tac-Toe en el que hay una ficha "comodín" que cuenta para los dos, saber cuál de los dos ha ganado, empatado o si todavía no ha acabado la partida. Las fichas de los oponentes son 'X' y 'O'. El comodín es la 'T'. Se entiende viendo el ejemplo: 
Input
 
6
XXXT
....
OO..
....

XOXT
XXOO
OXOX
XXOO

XOX.
OX..
....
....

OOXX
OXXX
OX.T
O..O

XXXO
..O.
.O..
T...

OXXX
XO..
..O.
...O

Output
Case #1: X won
Case #2: Draw
Case #3: Game has not completed
Case #4: O won
Case #5: O won
Case #6: O won
Se resuelve buscando 4 símbolos iguales alineadas en el tablero. Se puede hacer recorriendo los bordes izquierdo e inferior trazando diagonales, horizontales y verticales.

Problem B. Lawnmower

Se trata de comprobar que en un área dada podemos pasar de un lado a otro sin que cambie el valor del número con el que se empezó. También se entiende bien con el ejemplo: 
Input
  	
3
3 3
2 1 2
1 1 1
2 1 2
5 5
2 2 2 2 2
2 1 1 1 2
2 1 2 1 2
2 1 1 1 2
2 2 2 2 2
1 3
1 2 1

Output
Case #1: YES
Case #2: NO
Case #3: YES
Este problema es primo hermano del anterior descartando las diagonales. Se puede resolver recorriendo la parte lateral e inferior, vemos que número hay y vamos moviéndonos hasta llegar al final o hasta que cambie el número.

Problem C. Fair and Square

Nos dan un rango de números y tenemos que recorrer todo el rango y decir cuántos de esos números que son palíndromos tienen una raíz cuadrada que también es palíndroma. También se entiende en el ejemplo: 
Input
 
3
1 4
10 120
100 1000

Output
Case #1: 2
Case #2: 0
Case #3: 2
Hay que recorrer el rango y comprobar lo que he dicho arriba. Este es muy fácil.

Problem D. Treasure

Te dan una llave al principio. Con esa llave puedes abrir otra puerta en la que puedes encontrar otras llaves o ninguna. Si encuentras más llaves puedes abrir más puertas. Se trata de conseguir ir por todas las puertas sin dejar ninguna sin abrir. Cada llave se puede usar una sola vez. Se entiende bien en el enunciado: 
Chest Number  |  Key Type To Open Chest  |  Key Types Inside
--------------+--------------------------+------------------
1             |  1                       |  None
2             |  1                       |  1, 3
3             |  2                       |  None
4             |  3                       |  2
Puedes abrir todas las puertas si vas en orden 2, 1, 4 y 3. Si empiezas por abrir primero el 1 te quedas sin llaves y no puedes seguir abriendo puertas. La entrada de ejemplo sería esta: 
Input
  	
3
1 4
1
1 0
1 2 1 3
2 0
3 1 2
3 3
1 1 1
1 0
1 0
1 0
1 1
2
1 1 1

Output
Case #1: 2 1 4 3
Case #2: 1 2 3
Case #3: IMPOSSIBLE
Este es un pelín más difícil que el resto. Se puede resolver de forma recursiva probando diferentes caminos como si fuera el típico problema del salto del caballo.

Orden de resolución

8:20 Me he tirado 20 minutos escribiendo lo anterior. :-/ Hay dos casos parecidos y dos distintos. De los distintos el último es el menos fácil así que iré a por el distinto fácil y luego mientras doy el desayuno a los niños pensaré los otros dos: 1.- Problem C. Fair and Square 2.- Problem A. Tic-Tac-Toe-Tomek 3.- Problem B. Lawnmower 4.- Problem D. Treasure

Problem C. Fair and Square

11:30 Tras dar de desayunar a los niños, vestirles, hacer camas ... terminé de resolver el problema. Resolverlo para pasar con "Small input" es sencillo, lo difícil es resolver los casos en los que hay muchas entradas. Una posible solución al problema es: 
#!/usr/bin/python
import math
import time

def isPalindrome(number):
  # Palindrome means that it is simetric
  strNumber=str(number)
  lenStrNumber=len(strNumber)
  isPalindrome=1
  i=-1
  j=lenStrNumber
  while i<(lenStrNumber-1) and isPalindrome==1:
    i=i+1
    j=j-1
    if strNumber[i]!=strNumber[j]:
      isPalindrome=0

  return isPalindrome

def isPerfectSquare(number):
  # Perfect square means that its decimal is 0
  perfectSquare=0
  if str(math.sqrt(number)).split('.')[1]=="0":
    perfectSquare=1
  else:
    perfectSquare=0
  return perfectSquare

# Open input file
inputF=open('C-large-1.in','r')
outputF=open('C-large-1.out','w')
# Get number of cases
line=""
while len(line)<1:
  line=inputF.readline()
NoC=int(line)

# Read all cases and solve it
case=0
while case < NoC:
  case=case+1
  print "Case: "+str(case)
  line=inputF.readline()
  while len(line)<1:
    line=inputF.readline()
  caseLine=line
  rangeBegins=int(caseLine.split()[0])
  rangeEnds=int(caseLine.split()[1])
  # All input data in rangeBegins, rangeEnds and case
  NumberIsFairAndSquare=0
  caseTest=rangeBegins-1
  while caseTest < rangeEnds:
    # Test if caseTest is a Fair and perfect Square
    caseTest=caseTest+1
    # Perfect square means that its decimal is 0
    if isPerfectSquare(caseTest):
      perfectSquare=int(math.sqrt(caseTest))
      if ((isPalindrome(caseTest)==1) and (isPalindrome(perfectSquare)==1)):
        NumberIsFairAndSquare=NumberIsFairAndSquare+1
        print "Found FairAndSquare: "+str(caseTest)+" with perfectSquare: "+str(perfectSquare)
  outputF.write("Case #"+str(case)+": "+str(NumberIsFairAndSquare)+"\n")
"+str(rangeBegins)+"-"+str(rangeEnds)+" is "+str(NumberIsFairAndSquare)

inputF.close()
outputF.close()
Con este caso he pagado varias novatadas:
  • No hacer buenas pruebas con la salida que se envía a Google. Me equivoqué y tuve que arreglar el formato de salida en los 4 minutos que te dan de plazo.
  • No programar pensando en la eficiencia. El "que funcione como sea" que he hecho yo aquí no sirve. En el caso con pocas entradas sólo tardó un segundo en ejecutarse cuando te dan 4 minutos. Con muchas entradas te dan 8 minutos pero mi programa tarda bastante más.
    • No desarrollar pensando en los cores de la máquina: el problema se puede dividir para lanzar cuatro procesos que se lanzarían uno en cada core y como tengo 4 iría 4 veces más rápido.
    • No desarrollar pensando en castings innecesarios ni en condiciones de bucles simples. En el código que he puesto arriba ya he quitado algunas cosas rematadamente mal hechas pero antes en cada if se hacía un casting para pasar de string a entero.
    • Elegir mal la forma de resolver el problema. Hacer una raíz cuadrada es varias órdenes de magnitud más lento que elevar al cuadrado. Hubiera sido mucho más rápido hacer una caché de cuadrados palíndromos almacenada en un diccionario que lo que yo he hecho.
    • Mala elección del lenguaje de programación. C y C++ son más rápidos. Quizás no sea necesario usarlos para pasar pero seguro que me ahorraría bastante tiempo de ejecución.
No es suficiente con programar bien y claro porque ¡el código también se sube a Google!. El código tiene que ser eficiente y aprovechar los recursos de tu máquina.

Problem B. Lawnmower

15:29 Estuve pensando en el problema en el parque mientras vigilaba a los niños y me ha parecido más difícil de lo que pensaba en un principio ya que se trata de poner la altura de la máquina al máximo y cortar todo el césped. Luego para cada altura hay que ir celda por celda intentando cortar el césped en horizontal y si no se puede en vertical. Si no se puede en horizontal ni en vertical es que no se puede. 00:30 Al final he desistido de terminar el código por falta de tiempo dejando sin hacer cutRow y cutColum. Lo que me ha dado tiempo a escribir es lo siguiente: 
#!/usr/bin/python
import sys
import pprint
import time

def getNumberOfCases(inputF):
  line=""
  NoC=0
  while len(line) < 1:
    line=inputF.readline()
  NoC=int(line)

  return NoC

 getLawn(inputF):
  line=""
  dimY=0
  dimX=0
  lawn=[]

  while len(line)<1:
    line=inputF.readline()

  dimY=int(line.split()[0])
  dimX=int(line.split()[1])

  for y in range(dimY):
    line=inputF.readline()
    #print "line "+str(y)+": "+line
    lawn.append(line.split())

  # Convert all data to int
  for i in range(len(lawn)):
    for j in range(len(lawn[0])):
      lawn[i][j]=int(lawn[i][j])

  return lawn

def maxHeight (lawn, x1, x2, y1, y2):
  maximum=0

  #print "x1="+str(x1)
  #print "x2="+str(x2)
  #print "y1="+str(y1)
  #print "y2="+str(y2)

  x=x1
  y=y1
  while y<=y2:
    x=0
    while x<=x2:
      maximum=max(maximum, lawn[x][y])
      #print "x="+str(x)
      #print "y="+str(y)
      x=x+1
    y=y+1

  return int(maximum)

def minHeight (lawn, x1, x2, y1, y2):
  minimum=999

  x=x1
  y=y1
  while y<=y2:
    x=0
    while x<=x2:
      minimum=min(minimum, lawn[x][y])
      x=x+1
    y=y+1

  return int(minimum)

  def cutColumn (lawn, column, height):
    possible=1
    # Aquí me quedé

    return possible,vLawn

  def cutRow (vLawn, x, y, height, lawn):
    possible=1
    # Aquí me quedé

    return possible,vLawn

def possibleLawn (lawn):
  height=0
  possible=1
  # Wanted:
  # 11111
  # 12221
  # 12321
  # 12321
  # 11111
  # 
  # Step 1  Step 2  Step 3
  # 33333   22222   11111
  # 33333   22222   12221
  # 33333   22322   12321
  # 33333   22322   12321
  # 33333   22222   11111
  #
  # Look for higher value and cut all lawn
  # Look for value-1 and cut lawn without touch higher values -> try vertical and horizontal cut
  maxH=maxHeight(lawn, 0, len(lawn)-1, 0, len(lawn[0])-1)
  minH=minHeight(lawn, 0, len(lawn)-1, 0, len(lawn[0])-1)
  # Create a virgin lawn with the same dimensions and set all to maxH
  vLawn=lawn

  for i in range(len(vLawn)):
    for j in range(len(vLawn[0])):
      vLawn[i][j]=maxH

  height=maxH
  while((possible==1) and (height>minH)):
    height=height-1
    # For each position in lawn

        minimum=min(minimum, lawn[x][y])

    y=len(vLawn)
    x=len(vLawn[0])
    while (y>=0) and (possible==1):
      x=len(vLawn[0])
      while (x>=0) and (possible==1):
        # if height desired in lawn is higher than height cut row to height
        possible,vLawn=cutRow (vLawn, x, y, height, lawn)
        if possible==0:
          # if cannot cut row, cut column
          possible,vLawn=cutColumn (vLawn, x, y, height, lawn)
          # else -> impossible
        x=x+1
      y=y+1

  return possible

if __name__=='__main__':
  # Open input and output files
  inputF=open(sys.argv[1],'r')
  outputF=open(sys.argv[2],'w')

  NoC=getNumberOfCases(inputF)

  # Read all cases and solve them
  case=0
  while case < NoC:
    case=case+1
    print "Case: "+str(case)
    lawn=getLawn(inputF)
    #pprint.pprint(lawn)
    #time.sleep(5)
    possible=possibleLawn(lawn)
    if (possible==1):
      outputF.write("Case #"+str(case)+": YES\n")
    else:
      outputF.write("Case #"+str(case)+": NO\n")

  # Close input and output files
  inputF.close()
  outputF.close()

Consejos para afrontar un Google Code Jam para geeks casados con hijos y poco tiempo

Al final no he podido terminar por falta de tiempo pero he sacado unas conclusiones para volver a intentarlo el año que viene, eso sí, sin intención de ganar los 10000$:
  • Lo primero es que los problemas no son fáciles. Tampoco son difíciles si lo que se quiere es que funcionen con entradas pequeñas. Cualquier persona que haya hecho los tres primeros años de Ingeniería (o Ingeniería Técnica) en Informática es capaz de resolver los problemas en tiempo para las entradas pequeñas. No debería llevar más de una hora frente a la pantalla para cada problema.
  • El Google Code Jam comienza a la 1 de la mañana hora española. Hay que leerse los problemas a la 1 de la mañana e irse a la cama a la 1:30 con los problemas en la cabeza para que nuestro cerebro piense por nosotros mientras dormimos. Los problemas se pueden resolver el día siguiente.
  • Tener varias funciones ya hechas. Hay que saber que el formato de entrada siempre es el mismo: número de casos en la primera línea y datos en las siguientes. Nos ahorraremos por lo menos una horas si ya las tenemos hechas y probadas.
  • Aprovecha el tiempo que no estás delante del ordenador. El tiempo que vas a tener para picar código es muy reducido así que llévate en el móvil el enunciado del problema que vas a resolver y piensa sobre él mientras vistes niños, les das de desayunar o les llevas al parque para que al estar frente a la pantalla puedas utilizar el 100% del tiempo escribiendo código.

Comentarios

Otra vez será! :)

Submitted by Suso (no verificado) on

Si para mí es difícil encontrar tiempo, no me quiero imaginar para ti :P

Me he reído cuando he leído lo de "Este es muy fácil" para el problema C :D En efecto el dataset simple era factible, pero los large eran bastante más complicados. Usar cuadrados en vez de raíces, o múltiples cores, o C en vez de Python no era suficiente. Había que ir generando los posibles números palíndromos con cuadrados palíndromos. Mi algoritmo no estaba mal del todo, aunque requería unas cuantas optimizaciones más. Y aún así he fallado el large-1 :(

El problema B se podía resolver de forma más sencilla. Lo que hacía era que para cada fila y cada columna buscaba la altura máxima, que era con la que se podía cortar. Entonces "cortaba" con esa altura y marcaba a True los cuadrados que se hubieran cortado a la altura deseada. Así recorría todas las filas y columnas, y al final simplemente tenía que comprobar si todos los cuadrados estaban puestos a True. Puedes verlo en mi solución (en el Scoreboard busca mi usuario: "netsuso")

Otro consejo para otro año: dedicar algo más de tiempo a analizar la dificultad real de los problemas, en especial teniendo en cuenta los datasets large. Y empezar siempre por el más fácil! En este caso el problema A no tenía ningún misterio, y te daba 30 de los 35 puntos necesarios :)

Buenas observaciones

Submitted by elmanytas on

He pagado la novatada de pensar que no había que pensar en la eficiencia de las soluciones pero eso sólo me va a pasar una vez.

En el problema B también pensé esa solución pero es verdad que al final me compliqué un poco la vida. De todas formas ya iba mal de tiempo.

Análisis, ahí está el punto. Para eso es lo de acostarse a la 1:30. Eso da tiempo a analizar los problemas para a la mañana siguiente ir directo a por el mejor.

Aunque este ha sido un fracaso y sólo he conseguido 10 puntos si Google que deja voy a hacer también el siguiente aunque ya no opte a premio (total, no voy a por él). Así podré comprobar si he aprendido algo o no.