[PYTHON] Codeiq milk delivery route problem

A version that recursively solves with a tree structure

Practice using wood structures.

#!/bin/env python
# coding:utf-8

import csv
import sys

"""
Search is also performed while recursively creating a tree structure from the root node with priority on depth.
Cost aggregation is also performed halfway, and when the minimum cost is exceeded, the subsequent search for offspring nodes is stopped.
I'm not used to writing tree-structured programs, so I coded it straightforwardly.
"""


class Accumulator(object):
    def __init__(self, sum=sys.maxsize, route=[]):
        self.sum = sum
        self.route = route


class Node(object):
    def __init__(self, id, parent=None, cost_from_root=0, children=[]):
        self.id = id
        self.parent = parent
        self.cost_from_root = cost_from_root
        self.children = children

    def __repr__(self):
        return "%i, cost: %i -> %s\n" % (self.id, self.cost_from_root, repr(self.children))


class DeliveryCostCalculator(object):

    def __init__(self, filename):
        self.filename = filename
        self.cost_table = self.get_table()
        self.acc = Accumulator(sys.maxsize, [])

    def get_table(self):
        cost_table = []
        with open(self.filename, 'r') as f:
            reader = csv.reader(f)
            for row in reader:
                cost_table.append([int(col) for col in row])
        return cost_table

    def calc_total_cost(self, current):
        #If there is no remaining, cost total
        tmp = Node(0, current, current.cost_from_root + self.cost_table[current.id][0], None)
        current.children.append(tmp)
        if tmp.cost_from_root < self.acc.sum:
            #If the cost is the lowest, also aggregate the list of routes and pass it to the accumulator
            self.acc.sum = tmp.cost_from_root

            def _min_r(n, acc):
                if n.parent is None:
                    acc.append(n)
                    return acc
                acc.append(n)
                return _min_r(n.parent, acc)
            self.acc.route = _min_r(tmp, [])
            self.acc.route.reverse()

    def main(self):
        def _f(slot, current):
            if len(slot) <= 0:
                self.calc_total_cost(current)
                return
            for i in slot:
                #Register the next node in the child
                tmp = Node(i, current, current.cost_from_root + self.cost_table[current.id][i])
                if self.acc.sum < tmp.cost_from_root:
                    #If the cost at this point exceeds the minimum cost, stop further exploration
                    return
                current.children.append(tmp)
                #Remove the added number from the list and recurse
                a = list(slot)
                a.remove(i)
                _f(a, tmp)
        _f(range(1, len(self.cost_table)), Node(0))
        return self.acc.sum, self.acc.route


if __name__ == "__main__":
    c = DeliveryCostCalculator(sys.argv[1])
    (sum, route) = c.main()
    print(sum)
    print(" -> ".join([str(n.id + 1) for n in route]))
    # print([(n.id + 1, n.cost_from_root) for n in route])

A version that lists combinations in advance

Create a permutation that does not allow repetition with permutations, and then use for to aggregate costs. I also wanted to do something cool with functools.reduce, but I couldn't do it well.

#!/bin/env python
# coding:utf-8

import csv
import sys
from itertools import permutations

def get_table(filename):
    cost_table = []
    with open(filename, 'r') as f:
        reader = csv.reader(f)
        for row in reader:
            cost_table.append([int(col) for col in row])
    return cost_table


def main(filename):
    cost_table = get_table(filename)
    min_cost = sys.maxsize
    min_route = ()
    for p in permutations(range(1, len(cost_table))):
        # add an initial and a last node
        p = (0,) + p + (0,)
        total_cost = 0
        for i in range(len(p)):
            if i == len(p) - 1:
                continue
            # get a cost between a current and next
            total_cost += cost_table[p[i]][p[i + 1]]
            if min_cost < total_cost:
                break
        # print(total_cost, p)
        if total_cost < min_cost:
            min_cost = total_cost
            min_route = p
    return min_cost, min_route


if __name__ == "__main__":
    c, r = main(sys.argv[1])
    print(c)
    print(" -> ".join([str(n + 1) for n in r]))