Lo script prende in input il file values.in

order.py

# -*- coding: utf-8 -*-
"""

    Order
    ~~~~~

    Determina il numero minimo di mosse per ordinare un
    array di elementi sapendo che è possibile spostare un 
    qualsiasi elemento in cima o in fondo.

    Per esempio:

    [1, 6, 2, 3, 4] -> 1 Mossa: -Metti 6 in fondo.

    [10, 40, 25, 10] -> 2 Mosse: -Metti 10 in cima;
                                 -Metti 40 in fondo.
    
    [4, 5, 6, 1, 2] -> 2 Mosse: -Metti 2 in cima;
                                -Metti 1 in cima;
    
    :copyright: (c) 2011 by Gianluca Bargelli
    :license: GPL3

"""

import sys

def load_file(path):
    # Importa i valori da ordinare dal file
    with open(path, 'r') as f:
        i = 1
        for line in f:
            lista = [int(item) for item in line.split(',')]
            print "Lista #{0}: {1}".format(i, lista)
            min_sort_moves(lista)
            print("=" * 25)
            i+=1
            

def min_sort_moves(lista):
    # Mantiene una copia della lista ordinata (per stabilire il punto di arrivo)
    sorted_lista = sorted(lista)
    # Inizializzazione contatore mosse
    mosse = 0
    max_index = -1

    while lista != sorted_lista:
        if lista[0] < lista[max_index]:
            candidate_list = [x for x in lista[:max_index] if x > lista[max_index]]

            if not candidate_list:
                # Se non ho candidati significa che ho trovato il massimo
                max_index -=1
            else:
                max_index = -1
                candidate = min(candidate_list)
                # Inserisci in fondo
                print "|MOSSA|: Inserisco {0} in FONDO alla lista;".format(candidate)
                lista.append(lista.pop(lista.index(candidate)))
                # Incrementa il numero di mosse
                mosse+=1
                print "Lista alla mossa {0}:".format(mosse)
                print lista
                print ("-" * 5)
                
        else:
            candidate_list = [x for x in lista[1:] if x < lista[0]]
            candidate = max(candidate_list)
            # Inserisci in cima
            print "|MOSSA|: Inserisco {0} in CIMA alla lista;".format(candidate)
            lista.insert(0, lista.pop(lista.index(candidate)))
            # Incrementa il numero di mosse
            mosse+=1
            print "Lista alla mossa {0}:".format(mosse)
            print lista
            print ("-" * 5)

    print "Lista FINALE:"

    print lista
    print "Numero di mosse MINIME: {0}".format(mosse)

if __name__ == '__main__':
    if len(sys.argv) > 1:
        load_file(sys.argv[1])
    else:
        print "Usage: {0} [FILE_PATH]".format(sys.argv[0])

values.in

1,6,2,3,4,5
18,40,25,10
4,5,6,1,2
58,29,97,12,70,30,16,99,24,33,69,98,35,47,52

values.out

Lista #1: [1, 6, 2, 3, 4, 5]
|MOSSA|: Inserisco 6 in FONDO alla lista;
Lista alla mossa 1:
[1, 2, 3, 4, 5, 6]
-----
Lista FINALE:
[1, 2, 3, 4, 5, 6]
Numero di mosse MINIME: 1
=========================
Lista #2: [18, 40, 25, 10]
|MOSSA|: Inserisco 10 in CIMA alla lista;
Lista alla mossa 1:
[10, 18, 40, 25]
-----
|MOSSA|: Inserisco 40 in FONDO alla lista;
Lista alla mossa 2:
[10, 18, 25, 40]
-----
Lista FINALE:
[10, 18, 25, 40]
Numero di mosse MINIME: 2
=========================
Lista #3: [4, 5, 6, 1, 2]
|MOSSA|: Inserisco 2 in CIMA alla lista;
Lista alla mossa 1:
[2, 4, 5, 6, 1]
-----
|MOSSA|: Inserisco 1 in CIMA alla lista;
Lista alla mossa 2:
[1, 2, 4, 5, 6]
-----
Lista FINALE:
[1, 2, 4, 5, 6]
Numero di mosse MINIME: 2
=========================
Lista #4: [58, 29, 97, 12, 70, 30, 16, 99, 24, 33, 69, 98, 35, 47, 52]
|MOSSA|: Inserisco 52 in CIMA alla lista;
Lista alla mossa 1:
[52, 58, 29, 97, 12, 70, 30, 16, 99, 24, 33, 69, 98, 35, 47]
-----
|MOSSA|: Inserisco 47 in CIMA alla lista;
Lista alla mossa 2:
[47, 52, 58, 29, 97, 12, 70, 30, 16, 99, 24, 33, 69, 98, 35]
-----
|MOSSA|: Inserisco 35 in CIMA alla lista;
Lista alla mossa 3:
[35, 47, 52, 58, 29, 97, 12, 70, 30, 16, 99, 24, 33, 69, 98]
-----
|MOSSA|: Inserisco 99 in FONDO alla lista;
Lista alla mossa 4:
[35, 47, 52, 58, 29, 97, 12, 70, 30, 16, 24, 33, 69, 98, 99]
-----
|MOSSA|: Inserisco 70 in FONDO alla lista;
Lista alla mossa 5:
[35, 47, 52, 58, 29, 97, 12, 30, 16, 24, 33, 69, 98, 99, 70]
-----
|MOSSA|: Inserisco 97 in FONDO alla lista;
Lista alla mossa 6:
[35, 47, 52, 58, 29, 12, 30, 16, 24, 33, 69, 98, 99, 70, 97]
-----
|MOSSA|: Inserisco 98 in FONDO alla lista;
Lista alla mossa 7:
[35, 47, 52, 58, 29, 12, 30, 16, 24, 33, 69, 99, 70, 97, 98]
-----
|MOSSA|: Inserisco 99 in FONDO alla lista;
Lista alla mossa 8:
[35, 47, 52, 58, 29, 12, 30, 16, 24, 33, 69, 70, 97, 98, 99]
-----
|MOSSA|: Inserisco 33 in CIMA alla lista;
Lista alla mossa 9:
[33, 35, 47, 52, 58, 29, 12, 30, 16, 24, 69, 70, 97, 98, 99]
-----
|MOSSA|: Inserisco 30 in CIMA alla lista;
Lista alla mossa 10:
[30, 33, 35, 47, 52, 58, 29, 12, 16, 24, 69, 70, 97, 98, 99]
-----
|MOSSA|: Inserisco 29 in CIMA alla lista;
Lista alla mossa 11:
[29, 30, 33, 35, 47, 52, 58, 12, 16, 24, 69, 70, 97, 98, 99]
-----
|MOSSA|: Inserisco 24 in CIMA alla lista;
Lista alla mossa 12:
[24, 29, 30, 33, 35, 47, 52, 58, 12, 16, 69, 70, 97, 98, 99]
-----
|MOSSA|: Inserisco 16 in CIMA alla lista;
Lista alla mossa 13:
[16, 24, 29, 30, 33, 35, 47, 52, 58, 12, 69, 70, 97, 98, 99]
-----
|MOSSA|: Inserisco 12 in CIMA alla lista;
Lista alla mossa 14:
[12, 16, 24, 29, 30, 33, 35, 47, 52, 58, 69, 70, 97, 98, 99]
-----
Lista FINALE:
[12, 16, 24, 29, 30, 33, 35, 47, 52, 58, 69, 70, 97, 98, 99]
Numero di mosse MINIME: 14
=========================