Curbside Programming Challenge

decode.py

#!/usr/bin/env python

#
# Curbside Programming Challenge
#   by Moiz Merchant 
#

#------------------------------------------------------------------------------
# imports
#------------------------------------------------------------------------------

import collections
import json
import os
import subprocess
import sys

#------------------------------------------------------------------------------
# defines
#------------------------------------------------------------------------------

kDebug = False

#------------------------------------------------------------------------------
# structs
#------------------------------------------------------------------------------

Node = collections.namedtuple('Node', ['id', 'secret', 'next'])

#------------------------------------------------------------------------------
# curl methods
#------------------------------------------------------------------------------

def runCmd(cmd, env=None):
    """Run command on the shell and return the outputs and return code.
    """

    if kDebug:
        print "Running cmd: %s" % ' '.join(cmd)

    # run the process
    process = subprocess.Popen(cmd, stdin=subprocess.PIPE,
        stdout=subprocess.PIPE, stderr=subprocess.PIPE)

    # spin till cmd is complete
    stdOut, stdErr = process.communicate()

    # return results
    return (process.returncode, stdOut, stdErr)

#------------------------------------------------------------------------------

def curl(url, header=None):
    """Executes a curl request on the shell and returns the results.
    """

    cmd = ['curl'];

    # add header to curl request
    if header is not None:
        cmd += ['--header', header]

    # add url to curl request
    cmd.append(url)

    # run curl command
    code, out, err = runCmd(cmd)

    return out
        
#------------------------------------------------------------------------------

def queryShopCurbSide(route, sessionId=None):
    """Query ShopCurbSide and return the results.
    """

    # construct url
    url = 'http://challenge.shopcurbside.com/%s' % route

    # add session id to header
    header = None
    if sessionId is not None:
        header = "Session: %s" % sessionId

    # run the query
    results = curl(url, header)
    return results

#------------------------------------------------------------------------------
# Decoder
#------------------------------------------------------------------------------

class Decoder(object):
    """Traverses the ShopCurbSide challenge site decoding the secret message.
    """

    #--------------------------------------------------------------------------
    #  constants
    #--------------------------------------------------------------------------

    kErrorInvalidSessionId = 'Invalid session id, a token is valid for 10 requests.'

    #--------------------------------------------------------------------------
    # object
    #--------------------------------------------------------------------------

    def __init__(self):
        super(Decoder, self).__init__()

        # setup fields
        self._sessionId = None

    #--------------------------------------------------------------------------
    # query methods
    #--------------------------------------------------------------------------

    def _queryShopCurbSide(self, route, sessionId = None):
        """Queries ShopCurbSide for the requested route.
        """

        # run query
        results = queryShopCurbSide(route, sessionId)
        
        # add progress indicator to output
        sys.stdout.write('.')
        sys.stdout.flush()

        return results

    #--------------------------------------------------------------------------
        
    def _requestSessionId(self):
        """Queries ShopCurbSide for a new session Id.
        """
        
        return self._queryShopCurbSide('get-session');

    #--------------------------------------------------------------------------
    
    def _requestRoute(self, route):
        """Queries ShopCurbSide for the desired route.
        """
        
        # query ShopCurbSide
        results = json.loads(self._queryShopCurbSide(route, self._sessionId))

        # check for errors
        if 'error' in results:
            message = results['error']

            # resolve session id error
            if message == self.kErrorInvalidSessionId:
                self._sessionId = self._requestSessionId()
            else:
                raise Exception("Unknown error occured: %s" % message)

            # attempt to re-query the route
            return self._requestRoute(route)

        return results

    #--------------------------------------------------------------------------
    # methods
    #--------------------------------------------------------------------------
    
    def _traverse(self, name):
        """Traverses the tree like structure of the challenge.
        """

        # query the node
        results = self._requestRoute(name)

        # lowercase all keys
        for key in results.keys():
            results[key.lower()] = results[key]

        # create leaf node
        if 'secret' in results:
            node = Node(results['id'], results['secret'], None)

        # create intermediary node and process children
        elif 'next' in results:

            # inspect next fields type
            next_ = results['next']
            if isinstance(next_, unicode):
                children = [next_]
            elif isinstance(next_, list): 
                children = next_
            else:
                raise Exception("Invalid next field: %s" % next_)

            # create node
            node = Node(results['id'], None, map(self._traverse, children))

        else:
            raise Exception("Unknown node type recieved: %s" % results)

        return node

    #--------------------------------------------------------------------------

    def _extractLeafs(self, node, leafs):
        """Traverses the tree like structure and returns the leaf nodes
        """

        # add leaf node
        if node.next is None:
            leafs.append(node)

        # process intermediary node
        else:
            for child in node.next:
                self._extractLeafs(child, leafs)

    #--------------------------------------------------------------------------

    def run(self):
        """Runs the decoder and returns the secret message.
        """

        # aquire the initial session id
        self._sessionId = self._requestSessionId()

        # traverse the challenge
        root = self._traverse('start')

        # clear indicator line
        sys.stdout.write('\n')
        sys.stdout.flush()

        # extract leaf nodes
        leafs = []
        self._extractLeafs(root, leafs)

        # extract secrets
        secrets = map(lambda node: node.secret, leafs)

        # return glued secret letters together
        return "".join(secrets)

#------------------------------------------------------------------------------
# main
#------------------------------------------------------------------------------

if __name__ == '__main__':
    decoder = Decoder()
    message = decoder.run()
    print "Secret Message: %s" % message