Hekealo.co challenge

hackealo.py

# -*- coding: utf-8 -*-

"""
A pretty lame test from:
http://hackealo.co/


El instituto geográfico nacional se encarga de, periódicamente,
tomar fotografías aéreas para detectar cambios en el relieve terrestre.
Para agilizar esta tarea desean tener una herramienta que, dada una imagen tomada,
pueda detectar los bordes de las montañas. Las imágenes son representadas con
matrices de números enteros que representan la altura sobre el nivel del mar en
metros en una posición determinada. Un conjunto de posiciones conexas con la misma
altura en la matriz se consideran estratos. Se considerarán bordes, aquellos estratos
que son mínimos locales, es decir, que ninguno de sus integrantes posee vecinos con
altura menor. Diseñar un algoritmo que, dada una matriz, devuelva otra matriz con 0
en todas sus posiciones excepto en los bordes de las montañas que encuentre, donde devuelva 1.
"""

# Para testear tu código en nuestros servidores debes mantener la estructura expuesta abajo.
# Eres libre de crear nuevas funciones/procedimientos.
# Recuerda que el código que escribas podrá ser visto por las empresas a las que te postules.
# Para validar los 'vecinos', ten presente las posiciones arriba, abajo, izquierda y derecha. Las posiciones diagonales NO deben ser tenidas en cuenta.
# relieve = [[9, 2, 2, 2, 3, 5], [9, 8, 3, 2, 4, 5], [9, 7, 2, 2, 4, 3], [9, 9, 2, 4, 4, 3], [9, 2, 3, 4, 3, 5]]


def get_vecinos(index_fila, index_elemento):
    """Return vecinos, may include out of index elements"""
    return tuple(
        (i_f, i_e)
        for i_f, i_e in (
            (index_fila, index_elemento + 1),
            (index_fila, index_elemento - 1),
            (index_fila + 1, index_elemento),
            (index_fila - 1, index_elemento))
        if i_f >= 0 and i_e >= 0)


def get_diagonales(index_fila, index_elemento):
    """Return diagonales, may include out of index elements"""
    return tuple(
        (i_f, i_e)
        for i_f, i_e in (
            (index_fila + 1, index_elemento + 1),
            (index_fila + 1, index_elemento - 1),
            (index_fila - 1, index_elemento + 1),
            (index_fila - 1, index_elemento - 1))
        if i_f >= 0 and i_e >= 0)


def get_conexos(relieve, index_fila, index_elemento):
    """
    Return all related elements to the current one\
    including neighbors and diagonals
    """
    conexos = {}
    conexos_raw = (
        get_vecinos(index_fila, index_elemento) +
        get_diagonales(index_fila, index_elemento))

    for i_f, i_e in conexos_raw:
        try:
            (conexos
             .setdefault(relieve[i_f][i_e], [])
             .append((i_f, i_e)))
        except IndexError:
            pass

    return conexos


def get_integrates_conexos(relieve, index_fila, index_elemento):
    """
    Return integrates conexos al elemento\
    relieve[index_fila][index_elemento] del estrato
    """
    return (get_conexos(relieve, index_fila, index_elemento)
            .get(relieve[index_fila][index_elemento], []))


def get_conexos_vecinos(relieve, index_fila, index_elemento):
    """Return just the neighbors related to the current element"""
    conexos = {}

    for i_f, i_e in get_vecinos(index_fila, index_elemento):
        try:
            (conexos
             .setdefault(relieve[i_f][i_e], [])
             .append((i_f, i_e)))
        except IndexError:
            pass

    return conexos


def es_elemento_menor(relieve, index_fila, index_elemento):
    """Check if there all neighbors are greater than the current element"""
    elemento = relieve[index_fila][index_elemento]
    return all(
        elemento <= conexo
        for conexo in get_conexos_vecinos(relieve, index_fila, index_elemento).keys())


# I'm taking a dynamic programming approach,
# python sucks at this particular topic btw :)
# creating a graph would be cool as well

memoization = {}


def walk(relieve, index_fila, index_elemento):
    """
    Walk through all the related elements to the current one\
    check if all of them are lesser than their neighbors

    Return True if this is a mountain border, return False otherwise
    """
    visitados = set()  # Avoid cyclic references

    # @functools.lru_cache()  # not available in Python 2
    def _walk(index_fila_, index_elemento_):
        if (index_fila_, index_elemento_) in memoization:
            return memoization[(index_fila_, index_elemento_)]

        res = []

        for i_f, i_e in get_integrates_conexos(relieve, index_fila_, index_elemento_):
            if (i_f, i_e) in visitados:
                continue

            visitados.add((i_f, i_e))
            res.append(_walk(i_f, i_e))

        is_border = es_elemento_menor(relieve, index_fila_, index_elemento_) and all(res)
        memoization[(index_fila_, index_elemento_)] = is_border
        return is_border

    return _walk(index_fila, index_elemento)


def encontrar_bordes(relieve):
    matriz_final = []

    for index_fila, fila in enumerate(relieve):
        matriz_final.append([])

        for index_elemento, _ in enumerate(fila):
            if walk(relieve, index_fila, index_elemento):
                matriz_final[-1].append(1)
            else:
                matriz_final[-1].append(0)

    return matriz_final


if __name__ == "__main__":
    result = encontrar_bordes([[9, 2, 2, 2, 3, 5], [9, 8, 3, 2, 4, 5], [9, 7, 2, 2, 4, 3], [9, 9, 2, 4, 4, 3], [9, 2, 3, 4, 3, 5]])
    expected = [[0, 1, 1, 1, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 1, 1, 0, 1], [0, 0, 1, 0, 0, 1], [0, 1, 0, 0, 1, 0 ]]

    assert result == expected