2d House Robber : Dynamic Programming

import sys
from itertools import product
import operator
from io import StringIO

"""
The 2D House Robber is : Given a City laid out on a grid, there are R rows
of houses and C columns of houses. Each house is known to contain some amount
of valuables totaling v_ij. Your task is to rob as many houses as possible
to maximize the amount of loot. However there is a security system in place
and if you rob two adjacent houses an alarm will go off
Find the optimum set of non-adjacent houses to rob.
    e.g.:  Houses:  alignment:
          10 20 10     0  1  0
          20 30 20 =>  1  0  1
          10 20 10     0  1  0
        This alignment results in the maximum of 80.

This solution is optimized to about O(N*φ^N) for an NxN matrix

"""
def read_input(stream):
    """ read an input file like object

    first line of input contains two integers, R and C specifying the
    number of rows and columns. This is followed by R rows of C integers
    specifying the input matrix
    """
    R,C = map(int,stream.readline().strip().split())
    tbl = [ list(map(int,line.strip().split()))[:C] for line in stream ]
    return R,C,tbl

def compute_alignments(n):
    """ return all valid alignments for a single row

    an alignment is valid if there are no adjacent 1's

    for a given input n, there are approximately 1.6^(n+1) valid alignments
    (which is equivalent to the n+1'th Fibonacci number.)
    """
    for ali in product([0,1,],repeat=n):
        for i in range(1,n):
            if ali[i]&ali[i-1]:
                break
        else:
            yield ali

def compute_alignment_pairs(alignments_all):
    """ return a mapping for compatible alignments for each alignment

    alignments are compatible, if when stacked on top of each other (in 2d)
    there is no 1 at the same x position.
    """
    alipairs = [ set() for i in range(len(alignments_all)) ]
    for a,ali1 in enumerate(alignments_all):
        for b,ali2 in enumerate(alignments_all):
            if any( x&y for x,y in zip(ali1,ali2)):
                continue
            alipairs[a].add(b)
    return alipairs

def solve(R,C,tbl,alignments_all,alignment_pairs):
    """
    Solve the 2D House Robber problem by comparing all possible
    valid alignments for each row in the matrix.
    """
    N = len(alignments_all)
    # small optimization for dot product (remove reference to global variables)
    dot = lambda a,b,sum=sum,map=map,mul=operator.mul : sum(map(mul, a, b))
    # d_prev / d_next are the score given alignment i for a given row.
    d_prev = [ dot(tbl[0],ali) for ali in alignments_all ]
    # p is the predecessors array
    p =[ None,]*R
    p[0] = [0,]*N
    for i in range(1,R):
        values = [ dot(tbl[i],ali) for ali in alignments_all ]
        d_next = [0,] * N
        p[i]   = [0,] * N # new array for predecessors for this row

        for a in range(N):
            for b in alignment_pairs[a]:
                value = d_prev[a]+values[b]
                if value > d_next[b]:
                    d_next[b] = value
                    p[i][b] = a
        d_prev = d_next

    # read back solutions for optimal alignment
    value = max(d_prev)
    index = d_prev.index(value)
    ali = []
    for i in reversed(range(0,R)):
        ali.insert(0,alignments_all[index])
        index = p[i][index]
    return value,ali

def main():

    string_input="""3 3
10 20 10
20 30 20
10 20 10
"""
    #R,C,tbl = read_input(sys.stdin)
    R,C,tbl = read_input(StringIO(string_input))

    alignments_all = list(compute_alignments(C))
    alignment_pairs = compute_alignment_pairs(alignments_all)
    value_max,alignment = solve(R,C,tbl,alignments_all,alignment_pairs)
    for row in tbl:
        print(row)
    print("max:",value_max)
    for row in alignment:
        print(row)

if __name__ == '__main__':
    main()