Hackaflag Garage Week (Bradesco) | Resolução da challenge da Pirâmide

garageweek.py

#!/usr/bin/env python
# -*- coding: utf-8; mode: python; py-indent-offset: 4; indent-tabs-mode: nil -*-
# vim: fileencoding=utf-8 tabstop=4 expandtab shiftwidth=4
# pylint: disable=C0103,C0301,W1202,W0212

"""
Hackaflag Garage Week (Bradesco)
Resolução do desafio da pirâmide:

HOST: 159.65.181.58 
PORTA: 8383
      ____    _    ____      _    ____ _____  __        _______ _____ _  __
     / ___|  / \  |  _ \    / \  / ___| ____| \ \      / / ____| ____| |/ /
    | |  _  / _ \ | |_) |  / _ \| |  _|  _|    \ \ /\ / /|  _| |  _| | ' / 
    | |_| |/ ___ \|  _ <  / ___ \ |_| | |___    \ V  V / | |___| |___| . \ 
     \____/_/   \_\_| \_\/_/   \_\____|_____|    \_/\_/  |_____|_____|_|\_\ 


 [+] Para surpreender a todos os participantes do Garage Week, a
     organização do evento decidiu distribuir os desafios de cada participante
     de uma maneira bem incomum. Cada participante irá receber um labirinto em
     forma de pirâmide de fluxo único.

 [+] Dessa forma, os participantes terão que escolher os seus desafios
     baseados na pontuação dos mesmos, seguindo as seguintes regras:
      - Os desafios estarão dispostos em forma de uma piramide e os valores das
        suas respectivas pontuações;
      - Cada desafio está ligado a outros dois desafios do nível inferior na
        piramide;
      - Todos os participantes começam pelo desafio do topo da pirâmide;
      - Ao resolver um desafio, o participante escolhe ir para a direita ou
        esquerda do caminho inferior; e
      - Somente os desafios do caminho de custo mínimo possuem solução.

 [+] Dessa forma, sua tarefa é, dada uma pirâmide completa, informar o
     valor do menor caminho da ponta até a base, que é o último desafio.  

 [+] Exemplo: 
    
    Valores: 7 3 5 6 3 4 8 1 9 3

                               7
                           3       5
                       6       3       4
                   8       1       9       3
                   |       |       |       |
    Somas:         24      14      22      19

    A resposta correta é 14.

 [+] O limite de tempo para cada resposta é de 3 segundos. 
 [+] Para começar, digite start
"""

import socket
import json
import time
from treearray import TreeArray

# a classe TreeArray pode ser encontrada em:
# https://github.com/tommelo/treearray

class SocketWrapper(object):

    BUFFER_SIZE = 1204

    def __init__(self, host, port):
        self.host = host
        self.port = port
        self.tcp = socket.socket(socket.AF_INET, 
            socket.SOCK_STREAM)

    def connect(self):
        self.tcp.connect((self.host, self.port))
        self.tcp.setblocking(False)

    def close(self):
        self.tcp.close()

    def sendall(self, message):
        self.tcp.sendall(message)
    
    def recvall(self, timeout=0.9):
        # não tão eficiente para leitura total do buffer
        # considere ajustar o timeout em caso da string ser truncada

        try:   
            
            total_data = []
            data = ''
                        
            begin = time.time()

            while True:
                
                if total_data and time.time() - begin > timeout:
                    break
                                
                elif time.time() - begin > timeout * 2:
                    break
                                
                try:

                    data = self.tcp.recv(SocketWrapper.BUFFER_SIZE)

                    if data:
                        total_data.append(data)                        
                        begin = time.time()
                    else:                        
                        time.sleep(0.1)

                except:
                    pass
                        
            return ''.join(total_data)
        
        except:
            return None

class GarageWeekGame(object):
    
    HOST = "159.65.181.58"
    PORT = 8383
    START_CMD = "start"

    def __init__(self):
        self.tcp = SocketWrapper(GarageWeekGame.HOST, 
            GarageWeekGame.PORT)

    def __challenge_array(self, challenge):
        try:

            array_start = challenge.rfind("[")
            array_end = challenge.rfind("]") + 1

            value = challenge[array_start:array_end]
                
            if not value:
                return None
            
            return json.loads(value)

        except:
            return None

    def quit(self):
        self.tcp.close()

    def start(self):
        self.tcp.connect()

        # captura o banner
        banner = self.tcp.recvall()                        
        print(banner)

        # inicia o game
        self.tcp.sendall(GarageWeekGame.START_CMD)                        

    def play(self):

        while True:
            
            challenge = self.tcp.recvall()
            print challenge

            array = self.__challenge_array(challenge)                        
            if not array:
                break
                        
            tree = TreeArray.make_tree(array)
            result = tree.shortest_path_sum()
                
            print result

            self.tcp.sendall(str(result))                                   

game = GarageWeekGame()
game.start()
game.play()
game.quit()