Preparando el concurso

Dado que la entrada y salida de datos es siempre exactamente igual he hecho una plantilla que usaré en todos los retos:

# -*- coding: utf-8 -*-
#!/usr/bin/python
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 getList(inputFile, dataType="string", separator="space"):
    # dataType could be string, integer and float
    # separator can be space or none
    datalist = []

    line = ""
    while len(line) < 1:
        line = inputFile.readline()

        if  separator == "space":
            datalist = line.split()
        elif separator == "none":
            line = line.rstrip('\n')
            for i in range(len(line)):
                datalist.append(line[i])

    #if dataType=="string": ... already a string
    if dataType == "integer":
        i = 0
        while (i < len(datalist)):
            datalist[i] = int(datalist[i])
            i = i + 1
    elif dataType == "float":
        i = 0
        while (i < len(datalist)):
            datalist[i] = float(datalist[i])
            i = i + 1
    return datalist


def getBoard(inputFile, dimX, dimY, dataType="string", separator="none"):
    board = []

    for y in range(dimY):
        board.append(getList(inputFile, dataType, separator))

    return board


def printBoard(board, array="0"):
    #print board
    for i in range(len(board)):
        for j in range(len(board[i])):
            if array == "1":
                sys.stdout.write("[\"" + str(board[i][j]) + "\"]")
            else:
                sys.stdout.write(str(board[i][j]))

    print ("")


### solve it! ###
def solveIt(inputs, values, board):
#    time.sleep(1)
#    print ""
#    print inputs
#    print values
#    print board

    res = []
    i = 0
    j = 1

    res.append(i)
    res.append(j)

    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")
        values = getList(inputFile, "integer")
        board = getBoard(inputFile, "integer")
        # solve problem
        res = solveIt(inputs, values, board)

        # write data
        outputFile.write("Case #" + str(i + 1) + ": " + str(res[0] + 1) + " " + str(res[1] + 1) + "\n")
#        print "Case #"+str(i+1)+": "+str(res[0]+1)+" "+str(res[1]+1)

    # Close input and output files
    inputFile.close()
    outputFile.close()

Y pensarás ¿no puedes hacer eso el día del concurso? Pues no porque tengo los minutos contados. 10 minutos pueden suponer la diferencia entre que de tiempo a resolver un problema o no.

Insomnio provocado

Aprovecho una subida de fiebre del niño para despertarme del todo y valorar la dificultad de los problemas.

Esta vez me voy directo al "Contest scoreboard" donde veo que los mejores tardan 15 minutos en resolver el primero, otros 15 el segundo y alrededor de una hora el tercero y el cuarto así que supongo que los fáciles son el primero y el segundo.

Tras leer el primero, parece más una broma que un problema. El segundo también parece fácil pero necesita de una lectura más profunda del problema y con menos sueño.

Mañana será otro día. Bueno, hoy dentro de un rato será otro día.

Problem A. Magic Trick

Este problema es facilísimo. Nos dan dos arrays distintos en los que los números cambian de posición y nos piden que busquemos los números de una fila del primer array en otra fila del segundo array.

• Si se encuentran 2 -> Case #x: Bad magician!
• Si no se encuentran -> Volunteer cheated!
• Si se encuentra 1 -> Case #x: x

Tras un "tengo pis" y un "dale el antibiótico al niño" la solución, utilizando la plantilla como librería es la siguiente contenida en la función solveIt:

#!/usr/bin/python
# -*- coding: utf-8 -*- 
import time
import sys 
import gcjtemplate

### solve it! ###
def solveIt(row1,board1,row2,board2):
  res=[]
  for i in board2[row2-1]:
    if i in board1[row1-1]:
      res.append(i)

  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(gcjtemplate.getValue(inputFile))

  # for each case
  for i in range(NoC):
    # get case data
    row1=gcjtemplate.getValue(inputFile,"integer")
    board1=gcjtemplate.getBoard(inputFile,4,4,"integer","space")
    row2=gcjtemplate.getValue(inputFile,"integer")
    board2=gcjtemplate.getBoard(inputFile,4,4,"integer","space")
    # solve problem
    res=solveIt(row1, board1, row2, board2)

    # write data    
    if len(res)==0:
      outputFile.write("Case #"+str(i+1)+": Volunteer cheated!\n")
      print ("Case #"+str(i+1)+": Volunteer cheated!")
    elif len(res)==1:
      outputFile.write("Case #"+str(i+1)+": "+str(res[0])+"\n")
      print ("Case #"+str(i+1)+": "+str(res[0]))
    elif len(res)>1:
      outputFile.write("Case #"+str(i+1)+": Bad magician!\n")
      print ("Case #"+str(i+1)+": Bad magician!")
    else:
      time.sleep(5)
      print "HELP, HELP!"

  # Close input and output files
  inputFile.close()
  outputFile.close()

Problem B. Cookie Clicker Alpha

En este problema la dificultad está más en comprenderlo que en resolverlo.

Tu objetivo es llegar a tener un número de galletas en el menor tiempo posible. Empiezas con una fábrica de galletas y que te ha costado x galletas. Cuando llegas a esas x galletas puedes elegir entre comprar una fábrica para doblar la capacidad de producción o seguir produciendo como hasta ahora.

Se trata de elegir la mejor estrategia para decir cual es el menor número de segundos que se tarda en llegar a conseguir el número de galletas que queremos.

Hay que tener en cuenta que nos dan unos límites que, aunque en python nos dan igual, en otros lenguajes nos vienen bien para elegir el tipo de datos.

Se levanta la tropa, les llevo al parque, reunión familiar, comilona, ...

Estoy a 1:15 de decidir si paso a la siguiente fase o no. En teoría es factible pero no me gusta ir tan corto de tiempo.

El que nos den 8 minutos para entregar el resultado de nuestro programa en vez de los 4 habituales es un indicador de que puede ser bastante costoso en términos computacionales.

Este problema es de naturaleza recursiva ya que para decidir entre comprar o no comprar otra fábrica de galletas hay que saber qué es lo que pasaría si no se comprara otra o qué pasaría si se comprara otra, en cuyo caso habría que volver a saber qué es lo que pasaría si no se comprara otra o qué pasaría si se comprara otra, ... hasta que viéramos que deja de salir a cuenta comprar otra fábrica.

Sin embargo el problema se puede enfocar desde un punto de vista más lineal si pensamos en qué vamos a basar la decisión final: si con la capacidad de producción que tengo ahora tardo menos en producir las galletas que aumentando la producción en una fábrica más es que no debo comprar más fábricas.

Ignorando el resto de la plantilla que he puesto arriba del todo, la solución es la siguiente:

### solve it! ###
def solveIt(c,f,x):
  res=0.0

  speed=2
  cookies=0.0
  spentSeconds=0

  finish=0
  while finish==0:
    withoutMoreFarms=x/speed

    secondsToBuyFarm=c/speed
    newSpeed=speed+f
    withOneMoreFarm=secondsToBuyFarm+x/newSpeed

    if withOneMoreFarm< withoutMoreFarms:
      spentSeconds=spentSeconds+secondsToBuyFarm
      speed=newSpeed
    else:
      spentSeconds=spentSeconds+withoutMoreFarms
      finish=1
    
#    print "spentSeconds: "+str(spentSeconds)

  res=spentSeconds
  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
    c,f,x=getList(inputFile,"float")
    # solve problem
    res=solveIt(c,f,x)

    # write data    
    outputFile.write("Case #"+str(i+1)+": "+str(round(res,7))+"\n")
    #print "Case #"+str(i+1)+": "+str(round(res,7))

  # Close input and output files
  inputFile.close()
  outputFile.close()

Una vez enviada la respuesta al Large Set te indican que:
You have already tried this input set. (Judged at the end of the contest.)
Así que no hay forma de saber si ya tengo los 25 puntos que necesito o no.

¿Mas?

Pues va a ser que a estas horas lo que me apetece es dormir. Mañana publicaré este post y el resultado del concurso.

¡He pasado!

Lo que no entiendo muy bien es cómo puede haber gente que lo haya hecho peor todavía que yo y haber pasado también, pero ahí están los resultados.

Para la próxima a mirar la librería multiprocessing que me hará falta para utilizar todos los cores de mi máquina.