Trying to make patterns

input

line_id,operator_id,directiontype,name,stoparearef,latitude,longitude,pointorder,journeypatterns
HTM:3,HTM:8127,1,"Zoetermeer, Centrum-West",3006,52.060565,4.483079,1,{154579}
HTM:3,HTM:8103,1,"Zoetermeer, Centrum-West",3006,52.060597,4.483706,1,{154562}
HTM:3,HTM:1818,2,"Den Haag, Arnold Spoelplein",3165,52.05464,4.232891,1,"{154591,154580}"
HTM:3,HTM:8126,1,"Zoetermeer, Dorp",3177,52.054132,4.491709,2,"{154579,154562}"
HTM:3,HTM:1806,2,"Den Haag, Pisuissestraat",3131,52.057413,4.22792,2,"{154591,154580}"
HTM:3,HTM:8124,1,"Zoetermeer, Delftsewallen",3179,52.050779,4.486936,3,"{154579,154562}"
HTM:3,HTM:1813,2,"Den Haag, Mozartlaan",3164,52.060732,4.231698,3,"{154591,154580}"
HTM:3,HTM:8122,1,"Zoetermeer, Driemanspolder",3136,52.048483,4.477098,4,"{154579,154562}"
HTM:3,HTM:1802,2,"Den Haag, Heliotrooplaan",3133,52.062723,4.231297,4,"{154591,154580}"
HTM:3,HTM:8120,1,"Zoetermeer, Meerzicht",3139,52.055656,4.470055,5,"{154579,154562}"
HTM:3,HTM:1416,2,"Den Haag, Muurbloemweg",3061,52.063918,4.234912,5,"{154591,154580}"
HTM:3,HTM:8118,1,"Zoetermeer, Voorweg Hoog",3145,52.062927,4.471204,6,"{154579,154562}"
HTM:3,HTM:1424,2,"Den Haag, Hoefbladlaan",3161,52.065378,4.239891,6,"{154591,154580}"
HTM:3,HTM:8116,1,"Zoetermeer, Buytenwegh",2989,52.066798,4.47887,7,"{154579,154562}"
HTM:3,HTM:1419,2,"Den Haag, De Savornin Lohmanplein",3058,52.067317,4.246113,7,"{154591,154580}"
HTM:3,HTM:8114,1,"Zoetermeer, De Leyens",3183,52.071883,4.495074,8,"{154579,154562}"
HTM:3,HTM:1903,2,"Den Haag, Appelstraat",3069,52.06943,4.251748,8,"{154591,154580}"
HTM:3,HTM:8112,1,"Zoetermeer, Leidsewallen",3181,52.068941,4.51017,9,"{154579,154562}"
HTM:3,HTM:1213,2,"Den Haag, Zonnebloemstraat",3178,52.071458,4.25702,9,"{154591,154580}"
HTM:3,HTM:8110,1,"Zoetermeer, Seghwaert",3099,52.062973,4.515128,10,"{154579,154562}"
HTM:3,HTM:1218,2,"Den Haag, Azaleaplein",3176,52.073257,4.261862,10,"{154591,154580}"
HTM:3,HTM:8108,1,"Zoetermeer, Palenstein",3118,52.059699,4.506384,11,"{154579,154562}"
HTM:3,HTM:2004,2,"Den Haag, Goudenregenstraat",3182,52.075253,4.267574,11,"{154591,154580}"
HTM:3,HTM:8106,1,"Zoetermeer, Stadhuis",3116,52.061054,4.492883,12,"{154579,154562}"
HTM:3,HTM:2005,2,"Den Haag, Fahrenheitstraat",3187,52.076491,4.271102,12,"{154591,154580}"
HTM:3,HTM:8104,1,"Zoetermeer, Centrum-West",3006,52.060796,4.482681,13,"{154579,154562}"
HTM:3,HTM:2011,2,"Den Haag, Valkenbosplein",2961,52.078485,4.276567,13,"{154591,154580}"
HTM:3,HTM:8102,1,"Zoetermeer, Voorweg Laag",2997,52.062779,4.470639,14,"{154579,154562}"
HTM:3,HTM:1120,2,"Den Haag, Conradkade",3156,52.080614,4.28321,14,"{154591,154580}"
HTM:3,HTM:9597,1,"Den Haag, Leidschenveen",3162,52.065235,4.399754,15,"{154579,154562}"
HTM:3,HTM:1121,2,"Den Haag, Van Speijkstraat",2990,52.08122,4.288389,15,"{154591,154580}"
HTM:3,HTM:9595,1,"Den Haag, Forepark",3160,52.070315,4.392392,16,"{154579,154562}"
HTM:3,HTM:2213,2,"Den Haag, Elandstraat",2984,52.078087,4.292712,16,"{154591,154580}"
HTM:3,HTM:7212,1,"Voorburg, Leidschendam-Voorburg",3149,52.07773,4.381709,17,"{154595,154579,154562}"
HTM:3,HTM:2822,2,"Den Haag, MCH Westeinde",3108,52.072633,4.299657,17,"{154591,154580}"
HTM:3,HTM:7612,1,"Voorburg, Voorburg 't Loo",3073,52.082476,4.36497,18,"{154595,154579,154562}"
HTM:3,HTM:2823,2,"Den Haag, Brouwersgracht",3109,52.073901,4.304673,18,"{154591,154580}"
HTM:3,HTM:2683,1,"Den Haag, Laan van NOI",3063,52.078715,4.342064,19,"{154595,154579,154562}"
HTM:3,HTM:2882,2,"Den Haag, Grote Markt",3040,52.075471,4.309231,19,"{154591,154580}"
HTM:3,HTM:2663,1,"Den Haag, Beatrixkwartier",3119,52.080312,4.33463,20,"{154595,154579,154562}"
HTM:3,HTM:2880,2,"Den Haag, Spui",3041,52.077334,4.314394,20,"{154591,154580}"
HTM:3,HTM:2605,1,"Den Haag, Centraal Station",3045,52.08105,4.323759,21,"{154595,154579,154562}"
HTM:3,HTM:2608,2,"Den Haag, Centraal Station",3045,52.081185,4.324704,21,"{154591,154580}"
HTM:3,HTM:2881,1,"Den Haag, Spui",3041,52.077195,4.313945,22,"{154595,154579,154562}"
HTM:3,HTM:2662,2,"Den Haag, Beatrixkwartier",3119,52.079741,4.33514,22,"{154591,154580}"
HTM:3,HTM:2883,1,"Den Haag, Grote Markt",3040,52.075313,4.308607,23,"{154595,154579,154562}"
HTM:3,HTM:2682,2,"Den Haag, Laan van NOI",3063,52.078982,4.342758,23,"{154591,154580}"
HTM:3,HTM:2824,1,"Den Haag, Brouwersgracht",3109,52.073596,4.303689,24,"{154595,154579,154562}"
HTM:3,HTM:7611,2,"Voorburg, Voorburg 't Loo",3073,52.082255,4.365486,24,"{154591,154580}"
HTM:3,HTM:2820,1,"Den Haag, MCH Westeinde",3108,52.073302,4.29913,25,"{154595,154579,154562}"
HTM:3,HTM:7211,2,"Voorburg, Leidschendam-Voorburg",3149,52.077501,4.382225,25,"{154591,154580}"
HTM:3,HTM:2212,1,"Den Haag, Elandstraat",2984,52.078372,4.292384,26,"{154595,154579,154562,154560}"
HTM:3,HTM:9594,2,"Den Haag, Forepark",3160,52.070004,4.392764,26,"{154601,154591,154580}"
HTM:3,HTM:1122,1,"Den Haag, Van Speijkstraat",2990,52.081505,4.288061,27,"{154595,154579,154562,154560}"
HTM:3,HTM:9596,2,"Den Haag, Leidschenveen",3162,52.064762,4.400143,27,"{154601,154591,154580}"
HTM:3,HTM:1119,1,"Den Haag, Conradkade",3156,52.0805,4.282542,28,"{154595,154579,154562,154560}"
HTM:3,HTM:8101,2,"Zoetermeer, Voorweg Laag",2997,52.06264,4.471254,28,"{154601,154591,154580}"
HTM:3,HTM:2010,1,"Den Haag, Valkenbosplein",2961,52.078382,4.276146,29,"{154595,154579,154562,154560}"
HTM:3,HTM:8103,2,"Zoetermeer, Centrum-West",3006,52.060597,4.483706,29,"{154601,154591,154580}"
HTM:3,HTM:2006,1,"Den Haag, Fahrenheitstraat",3187,52.076414,4.270564,30,"{154595,154579,154562,154560}"
HTM:3,HTM:8105,2,"Zoetermeer, Stadhuis",3116,52.061138,4.493377,30,"{154601,154591,154580}"
HTM:3,HTM:2003,1,"Den Haag, Goudenregenstraat",3182,52.074985,4.26672,31,"{154595,154579,154562,154560}"
HTM:3,HTM:8107,2,"Zoetermeer, Palenstein",3118,52.059676,4.506953,31,"{154601,154591,154580}"
HTM:3,HTM:1217,1,"Den Haag, Azaleaplein",3176,52.073136,4.261427,32,"{154595,154579,154562,154560}"
HTM:3,HTM:8109,2,"Zoetermeer, Seghwaert",3099,52.063192,4.515561,32,"{154601,154591,154580}"
HTM:3,HTM:1214,1,"Den Haag, Zonnebloemstraat",3178,52.070969,4.255647,33,"{154595,154579,154562,154560}"
HTM:3,HTM:8111,2,"Zoetermeer, Leidsewallen",3181,52.069035,4.509628,33,"{154601,154591,154580}"
HTM:3,HTM:1904,1,"Den Haag, Appelstraat",3069,52.0693,4.251299,34,"{154595,154579,154562,154560}"
HTM:3,HTM:8113,2,"Zoetermeer, De Leyens",3183,52.07205,4.494589,34,"{154601,154591,154580}"
HTM:3,HTM:1420,1,"Den Haag, De Savornin Lohmanplein",3058,52.06714,4.245476,35,"{154595,154579,154562,154560}"
HTM:3,HTM:8115,2,"Zoetermeer, Buytenwegh",2989,52.066704,4.478361,35,"{154601,154591,154580}"
HTM:3,HTM:1423,1,"Den Haag, Hoefbladlaan",3161,52.065347,4.23944,36,"{154595,154579,154562,154560}"
HTM:3,HTM:8117,2,"Zoetermeer, Voorweg Hoog",3145,52.062611,4.471007,36,"{154601,154591,154580}"
HTM:3,HTM:1415,1,"Den Haag, Muurbloemweg",3061,52.063896,4.234446,37,"{154595,154579,154562,154560}"
HTM:3,HTM:8119,2,"Zoetermeer, Meerzicht",3139,52.055375,4.469857,37,"{154601,154591,154580}"
HTM:3,HTM:1801,1,"Den Haag, Heliotrooplaan",3133,52.062682,4.230758,38,"{154595,154579,154562,154560}"
HTM:3,HTM:8121,2,"Zoetermeer, Driemanspolder",3136,52.048416,4.477624,38,"{154601,154591,154580}"
HTM:3,HTM:1812,1,"Den Haag, Mozartlaan",3164,52.05879,4.232652,39,"{154595,154579,154562,154560}"
HTM:3,HTM:8123,2,"Zoetermeer, Delftsewallen",3179,52.050998,4.487311,39,"{154601,154591,154580}"
HTM:3,HTM:1805,1,"Den Haag, Pisuissestraat",3131,52.057135,4.227956,40,"{154595,154579,154562,154560}"
HTM:3,HTM:8125,2,"Zoetermeer, Dorp",3177,52.054387,4.492127,40,"{154601,154591,154580}"
HTM:3,HTM:1818,1,"Den Haag, Arnold Spoelplein",3165,52.05464,4.232891,41,"{154595,154579,154562,154560}"
HTM:3,HTM:8127,2,"Zoetermeer, Centrum-West",3006,52.060565,4.483079,41,"{154601,154580}"
HTM:3,HTM:8104,2,"Zoetermeer, Centrum-West",3006,52.060796,4.482681,41,{154591}

patterns.python

from math import radians, cos, sin, asin, sqrt
import csv

lines = {}
stops = {}

def LCSLength(x, y):
    C = [[0 for X in range(len(x))] for Y in range(len(y))]
    for i in range(len(x)):
       C[i][0] = 0
    for j in range(len(y)):
       C[0][j] = 0
    for i in range(len(x)):
        for j in range(len(y)):
            if x[i] == y[j]:
                C[i][j] = C[i-1][j-1] + 1
            else:
                C[i][j] = max(C[i][j-1], C[i-1][j])
    return C

def backtrack(C, X, Y, i, j):
    if i == 0 or j == 0:
        return ""
    elif X[i] == Y[j]:
        return backtrack(C, X, Y, i-1, j-1) + X[i]
    else:
        if C[i][j-1] > C[i-1][j]:
            return backtrack(C, X, Y, i, j-1)
        else:
            return backtrack(C, X, Y, i-1, j)

def DTWDistance(s, t):
    DTW = [[0 for X in range(len(s))] for Y in range(len(t))]

    for i in range(len(s)):
        DTW[i][0] = 99999999999
    for j in range(len(t)):
        DTW[0][i] = 99999999999
    DTW[0][0] = 0

    for i in range(1, len(s)):
        for j in range(1, len(t)):
            c = cost(s[i], t[j])
            DTW[i][j] = c + min(DTW[i-1][j], DTW[i][j-1],DTW[i-1][j-1])
    #return DTW[len(s)-1][len(t)-1]
    return DTW

def haversine(lon1, lat1, lon2, lat2):
    """
    http://stackoverflow.com/questions/4913349/haversine-formula-in-python-bearing-and-distance-between-two-gps-points
    Calculate the great circle distance between two points
    on the earth (specified in decimal degrees)
    """
    # convert decimal degrees to radians
    lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2])

    # haversine formula
    dlon = lon2 - lon1
    dlat = lat2 - lat1
    a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2
    c = 2 * asin(sqrt(a))

    # 6367 km is the radius of the Earth
    km = 6367 * c
    return km

def cost(a, b):
    return haversine(stops[a][0],stops[a][1], stops[b][0],stops[b][1])
    #return int(stops[a] == stops[b])

with open('lijn3.csv') as f:
    for l in csv.DictReader(f):
        if l['line_id'] not in lines:
            lines[l['line_id']] = {'1': [], '2': []}

        lines[l['line_id']][l['directiontype']].append(l['operator_id'])
        stops[l['operator_id']] = (float(l['longitude']),float(l['latitude']))


lines['HTM:3']['2'].reverse()

DTW = DTWDistance(lines['HTM:3']['1'], lines['HTM:3']['2'])
# Works with name
#C = LCSLength(lines['HTM:3']['1'], lines['HTM:3']['2'])
print backtrack(DTW, lines['HTM:3']['1'], lines['HTM:3']['2'], len(lines['HTM:3']['1'])-1, len(lines['HTM:3']['2'])-1)