Find an order with the minimum total price

Question

We want to create an application for the analysis of the order history at an online store. Each order is made by a customer and concerns the purchase of one or more items. Orders are stored in OR, an array of integers having 4 columns. The generic line OR[i] = [o, a, q, p] denotes the fact that in the order with code "o" a quantity "q" of the article with code "a" is required, sold at a unit price equal to "p" (for which obviously the total price paid for the item a in the order "o" is equal to "p * q"). An order has as many rows in OR as there are different items contained in the order.

I must write a function "ordine_min(OR)" which returns the order code with the minimum total price. In case of a tie, any of the orders with the minimum total price must be returned.

def ordine_min(OR):
    ret = []
    for i in range(len(OR)):
        if prezzo(OR,i):
            ret.append((prezzo(OR, i),i))
    return min(ret)

def prezzo(OR, i):
    prezzo_tot = 0
    for k in range(len(OR)):
        if OR[k][0] == i:
            prezzo_tot += OR[k][2] * OR[k][3]
    return prezzo_tot

The matrix is here:

OR = [[1,1,2,2],
      [1,2,3,2],
      [2,1,1,2],
      [2,4,1,3],
      [3,3,2,1],
      [3,4,2,1],
      [4,4,1,7],
      [4,5,2,1],
      [5,1,2,4],
      [5,5,1,4],
      [6,1,2,1],
      [6,2,1,3]]

Answer 1

Your prezzo() function is very inefficient: for every line, you scan every line in OR to for a matching o, which makes your algorithm O(n²). To make it worse, you call it from twice from ordine_min(), doubling the work! Ideally, the calculations should be done in one single pass through OR.

Your code is also very hard to read and understand, due to cryptic naming — OR, i, OR[k][2] * OR[k][3]. Using destructuring assignments can help improve readability.

from collections import Counter

def ordine_min(ordini):
    prezzi_neg = Counter()
    for ordine, articolo, quantità, prezzo in ordini:
        # The Counter can efficiently find the maximum total.  We calculate
        # negative prices to trick it into finding the minimum instead.
        prezzi_neg[ordine] -= quantità * prezzo
    for ordine, prezzi_neg in prezzi_neg.most_common(1):
        return -prezzi_neg, ordine

Answer 2

1. Write code in English

   English should be the preferred language to write code in.

   It makes it easier for other people (for instance on this site) to understand what the code is doing.

2. Python comes with batteries included

   This means whenever possible make use of the modules that are in the standard library, in this case you could make use of the groupby function from the itertools package

   This function just groups data together with whatever key you supply

3. Use list comprehension when possible

   This is not only considered Pythonic, it should also be a bit faster

Revised code

from itertools import groupby
import doctest

def minimum_order(orders):
    """
    This will return *any* order with a minimum total price based on a list of orders
    Where each order consists of [code, _ quauntity, price]

    Returns a tuple with (total price, code)

    >>> minimum_order([[1,1,2,2],[1,2,3,2]])
    (10, 1)
    """
    return min(
        (
            (sum(x[2] * x[3] for x in g), k)
            for k, g in groupby(
                orders, 
                lambda x : x[0]
            )
        ), key=lambda x: x[0]
    )

if __name__ == '__main__':
    doctest.testmod()