[FIXED] Finding faster solution for assignment

Issue

I have a homework in which I need to solve this problem in python:

• There are N houses in a street. Every house's garden can have only 1 out of 3 colors of flower planted.
• There is a list (in a file) which consists of price for every color of flower for every property and it looks something like that:

9 2 7

5 8 3

4 7 8

...

3 5 2

• Every row represents one house and every column one color. (lets say White, Yellow, Red) What I have to do is to find a cheapest way to plant flowers in this neighborhood, but if a 1 house has certain color planted then the houses next to it cant plant that color. So for set of 4 houses:

houses\colors   w y r
H1              5 6 7

H2              3 7 9

H3              6 7 3

H4              1 8 4

The cheapest way including the rule would be: 6+3+3+1 = 13. So the colors would be Yellow, White, Red, White.

So I have already found one solution for this problem using itertools and its product. I just made a list of all possibilities of a [1,2,3] in n-length set, and exclude every one that has 2 same adjacent numbers, then I just apply the prices for every combination and find the cheapest one. But with this solution with the larger N (maybe like >20) its very slow and might even crash because of memory error. So I'm asking if there is any faster solution. Also sorry for my rough english and probably bad explanation of the problem, if anyone has any question about the problem please ask them.

Edit - the code I have right now:

import itertools
file = open('domy.txt')
ceny = file.readlines()

for x in range(len(ceny)):
    ceny[x] = ceny[x][0:-1]

n = len(ceny)
domy = [[0]*3]*n

for x in range(n):
    test = ceny[x].split(' ')

test = list(itertools.product([1, 2, 3], repeat=n))

i = 0
while i < len(test):
    t = 0
    while t < len(test[t])-1:
        if test[i][t] == test[i][t+1]:
            test.pop(i)
            i -= 1
            break
        t += 1
    i += 1

index = 0
i = 0
minimum = 0
while i < len(test):
    suma = 0
    if i == 0:
        j = 0
        for x in test[i]:
            if x == 1:
                suma += int(ceny[j][0])
            elif x == 2:
                suma += int(ceny[j][2])
            elif x == 3:
                suma += int(ceny[j][4])
            j += 1
        index = i
        minimum = suma
    else:
        j = 0
        for x in test[i]:
            if x == 1:
                suma += int(ceny[j][0])
            elif x == 2:
                suma += int(ceny[j][2])
            elif x == 3:
                suma += int(ceny[j][4])
            j += 1
        if suma < minimum:
            minimum = suma
            index = i
    i += 1

print(minimum)
print(test[index])

Solution

The basic algorithm to find just the minimum sum goes through the rows and keeps track of the minimum sum for ending with each of the three columns (e.g., b is the minimum sum through the rows so far and buying the middle flower in the latest row so far).

def solve(rows):
    a = b = c = 0
    for x, y, z in rows:
        a, b, c = (
            min(b, c) + x,
            min(a, c) + y,
            min(a, b) + z
        )
    return min(a, b, c)

rows = [
    [5, 6, 7],
    [3, 7, 9],
    [6, 7, 3],
    [1, 8, 4]
]

print(solve(rows))

To also get the list of choices leading to the minimum sum, additionally keep track of the choices and reconstruct the path backwards afterwards. Annoying, left as exercise for the reader :-P

Oh well... Here's one also computing the list. Instead of tracking just sums, track (sum,path) pairs:

def solve(rows):
    a = b = c = (0, None)
    def extend(a, b, z, i):
        sum, path = min(a, b)
        return sum + z, (i, path)
    for x, y, z in rows:
        a, b, c = (
            extend(b, c, x, 1),
            extend(a, c, y, 2),
            extend(a, b, z, 3)
        )
    sum, path = min(a, b, c)
    flat = []
    while path:
        i, path = path
        flat.append(i)
    return sum, flat[::-1]

rows = [
    [5, 6, 7],
    [3, 7, 9],
    [6, 7, 3],
    [1, 8, 4]
]

print(*solve(rows))

Attempt This Online!

Answered By - Kelly Bundy