Solution for Skiing in Singapore - a coding diversion (http://geeks.redmart.com/2015/01/07/skiing-in-singapore-a-coding-diversion/)

skiing.py

#!/usr/bin/env python3

import os
import sys
from itertools import product


def read_map(s):
    s = s.strip().split('\n')
    l, w = (int(x) for x in s[0].split(' '))
    map_ = []
    for r in s[1:]:
        map_.append([int(x) for x in r.split(' ')])
    return l, w, map_


def lower(map_, l, w, r, c):
    curr_elevation = map_[r][c]
    adj = ()

    if r > 0 and map_[r - 1][c] < curr_elevation:
        adj += ((r - 1, c),)

    if c > 0 and map_[r][c - 1] < curr_elevation:
        adj += ((r, c - 1),)

    if r < l - 1 and map_[r + 1][c] < curr_elevation:
        adj += ((r + 1, c),)

    if c < w - 1 and map_[r][c + 1] < curr_elevation:
        adj += ((r, c + 1),)

    return adj


def dfs(map_, l, w, r0, c0):
    open_ = [(r0, c0, ((r0, c0),))]
    paths = []

    while open_:
        r, c, path = open_.pop()
        adj = lower(map_, l, w, r, c)

        if len(adj) == 0:
            paths.append(path)
        else:
            for r1, c1 in adj:
                open_.append((r1, c1, path + ((r1, c1),)))

    return paths


def drop(map_, run):
    elevations = tuple(map_[r][c] for r, c in run)
    return elevations[0] - elevations[len(run) - 1]


def elevations(map_, run):
    return tuple(map_[r][c] for r, c in run)


def main():
    if sys.stdin.isatty():
        if len(sys.argv) > 1:
            with open(sys.argv[1]) as f:
                s = f.read()
        else:
            print('Usage: {} INPUT_FILE'.format(os.path.basename(__file__)))
            sys.exit(1)
    else:
        s = sys.stdin.read()

    l, w, map_ = read_map(s)

    # find all paths for all starting points
    runs = []
    for r0, c0 in product(range(l), range(w)):
        runs.extend(dfs(map_, l, w, r0, c0))

    # find max length of a run
    max_run_length = max(len(run) for run in runs)
    print('Longest run length:', max_run_length)

    # find runs of length max_run_length
    longest_runs = [run for run in runs if len(run) == max_run_length]

    # find longest drop
    longest_drop = max(drop(map_, run) for run in longest_runs)
    print('Longest drop:', longest_drop)

    # find all runs with longest drop
    longest_steepest_runs = [run for run in longest_runs if drop(map_, run) == longest_drop]

    # print elevations in longest and steepest runs
    print('Longest and steepest run coords:', longest_steepest_runs)
    print('Longest and steepest run elevations:', [elevations(map_, run) for run in longest_steepest_runs])


if __name__ == '__main__':
    main()