from alignment import Needleman, Hirschberg

def levenshteinDistance(s1, s2):
    if len(s1) > len(s2):
        s1, s2 = s2, s1

    distances = range(len(s1) + 1)
    for i2, c2 in enumerate(s2):
        distances_ = [i2+1]
        for i1, c1 in enumerate(s1):
            if c1 == c2:
                distances_.append(distances[i1])
            else:
                distances_.append(1 + min((distances[i1], distances[i1 + 1], distances_[-1])))
        distances = distances_
    return distances[-1]

def compare(str1, str2):
    seq1 = list(str1)
    seq2 = list(str2)
    for algorithm in [Needleman(), Hirschberg()]:
        a, b = algorithm.align(seq1, seq2)
        print("".join(a))
        print("".join(b))
        print()

original = [
    "riverrun, past Eve and Adam's, from swerve of shore to bend of bay, brings us by a commodius vicus of recirculation back to Howth Castle and Environs." , 
    "Sir Tristram, violer d'amores, fr'over the short sea, had passen-core rearrived from North Armorica on this side the scraggy isthmus of Europe Minor to wielderfight his penisolate war: nor had topsawyer's rocks by the stream Oconee exaggerated themselse to Laurens County's gorgios while they went doublin their mumper all the time: nor avoice from afire bellowsed mishe mishe to tauftauf thuartpeatrick: not yet, though venissoon after, had a kidscad buttended a bland old isaac: not yet, though all's fair in vanessy, were sosie sesthers wroth with twone nathandjoe. Rot a peck of pa's malt had Jhem or Shen brewed by arclight and rory end to the regginbrow was to be seen ringsome on the aquaface." , 
    "The fall (bababadalgharaghtakamminarronnkonnbronntqnner-ronntuonnthunntrovarrhounawnskawntoohoohoordenenthur-nuk!) of a once wallstrait oldparr is retaled early in bed and later on life down through all christian minstrelsy. The great fall of the offwall entailed at such short notice the pftjschute of Finnegan, erse solid man, that the humptyhillhead of humself prumptly sends an unquiring one well to the west in quest of his tumptytumtoes: and their upturapikepointandplace is at the knock out in the park where oranges have been laid to rust upon the green since dev-linsfirst loved livvy." ,
    "What clashes here of wills gen wonts, oystrygods gaggin fishy-gods! Brekkek Kekkek Kekkek Kekkek! Koax Koax Koax! Ualu Ualu Ualu! Quaouauh! Where the Baddelaries partisans are still out to mathmaster Malachus Micgranes and the Verdons cata-pelting the camibalistics out of the Whoyteboyce of Hoodie Head. Assiegates and boomeringstroms. Sod's brood, be me fear! Sanglorians, save! Arms apeal with larms, appalling. Killykill-killy: a toll, a toll. What chance cuddleys, what cashels aired and ventilated! What bidimetoloves sinduced by what tegotetab-solvers! What true feeling for their's hayair with what strawng voice of false jiccup! O here here how both sprowled met the duskt the father of fornicationists but, (O my shining stars and body!) how hath fanespanned most high heaven the skysign of soft advertisement! But was iz? Iseut? Ere were sewers. The oaks of aid now they lie in peat yet elms leap where askes lay. Phall if you but will, rise you must: and none so soon either shall the pharce for the nunce come to a setdown secular phoenish." ,
    "Bygmester Finnegan, of the Stuttering Hand, freemen's mau-rer, lived in the broadest way immarginable in his rushlit toofar-back for messuages before joshuan judges had given us numbers or Helviticus committed deuteronomy (one yeastyday he sternely struxk his tete in a tub for to watsch the future of his fates but ere he swiftly stook it out again, by the might of moses, the very wat-er was eviparated and all the guenneses had met their exodus so that ought to show you what a pentschanjeuchy chap he was!) and during mighty odd years this man of hod, cement and edi- fices in Toper's Thorp piled buildung supra buildung pon the banks for the livers by the Soangso. He addle liddle phifie Annie ugged the little craythur. Wither hayre in bonds tuck up your part inher. Oftwhile balbulous, mithre ahead, with goodly trowel in grasp and ivoroiled overalls which he habitacularly fondseed, like Haroun Childeric Eggeberth he would caligulate by multiplicab- les the alltitude and malltitude until he seesaw by neatlight of the liquor wheretwin 'twas born, his roundhead staple of other days to rise in undress maisonry upstanded (joygrantit!), a waalworth 7^*14 of a skyerscape of most eyeful hoyth entowerly, erigenating from next to nothing and celescalating the himals and all, hierarchite(> o UJtlk^ titiptitoploftical, with a burning bush abob off its baubletop and with larrons o'toolers clittering up and tombles a'buckets clotter-ing down."
]



parody = [
    "movierun, past new and hopes, from strike of back to bend of jeday, brings us by a commodius lucas of recirculation back to forestmoon and endor." ,
    "Sir Kywalker, violer d’amores, fr’over the short stars, had passen-core rearrived from North Dagobah on this side the scraggy isthwamp of yoda Minor to saberfight his penisolate war: nor had topsawyer’s rocks by the Duney Tattoee exaggerated themselse to fraherberts county’s Jabbios while they went doublin their muppets all the time: nor avoice from afire bellowsed mishe mishe to tauftauf thuartspaceoperatick not yet, though venissoon after, had a kidscad buttended a bland old threepeeo: not yet, though all’s fair in Leiaessy, were in-sistie smoochers wroth with twone famromance. Rot a peck of pa’s malt had Jhed or Sithen duelwed by arclight and rory end to the regginbrow was to be seen ringsome on the bewithyouforce." ,
    "The fall (bababadalgharaghtakamminarronnkonnbronntonner-ronntuonnthunntrovarr-hounawnskawntoohoohoordenenthur—nuk!) of a once moonhigh Deathstar is retaled early in bed and later on life down through all ewoke minstrelsy. The great fall of the offworld entailed at such short notice the pftjschoot of Falconmilleniums, erse solo man, that the humptyhillhead of zoomself prumptly sends an unquiring blast well to the core in darthdeathstarth of his powergenerator: and their aboutturnpikepoint is at the flight out of the innards where orangeplosions have been set to blast upon the core since fi-lmsfirst blew uppy." ,
    "What clashes here of woods gen wonts, blasterlaze gaggin ewokky-gods! Soundefects brékkek békkek kékkek kékkek! Kóax Kóax Kóax! Ualu Ualu Ualu! Stormtroops! Where the Baddielaries clonimans are still out to blastmaster Rebelscum and the Verdroids cata-pelting the camibalistics out of the Wookieeboyce of Bacca Head. Rollinlogs and boomeringstorms. Sidth’s brood, be me fear! Endorians, save! Arms apeal with larms, appalling. Killykill-killy: a toll, a toll. What chance cuddleys, what skulshells aired and ventilated! O here here how hoth sprowled met the duskt the vader of forcenicationists but, (O my shining stars and body!) how hath forcespanned most high heaven the skysign of deathstar advertisement! But was iz? Liuke? Ere were sibling? The oaks of ald now they lie under feat of Imperious ewokon Walkers yet elms leap where warmachine lay. Phall if you but will, be crushed you must: and none so soon either shall the pharce for the empirce come to a setdown secular phinish." ,
    "Bygmonster Annakin, of the Throatchokin Hand, forcemen’s mau-rer, lived in the broadest way immarginable in his rushlit toofar — back for messuages before jeduan jedges had given us sabers. Oftwhile balbulous, helmet ahead, with goodly evil in grasp and blaclycape overalls which he habitacularly fondseed, like High Council Emperor would caligulate by multidecap-les the alltitude and malltitude until he seesaw by neatlight of the midichloriquor wheretwin ’twas born, a waalworth of a skyerscape of most eyeful hoyth entowerly, erigenating from next to nothing and celescalating the himals and all, hierarchitec-titiptitoploftical, with a burning bush abob off its baubletop and with at last plucking the Palpatine up and tombles a’blastiets clottering down the urbam chasam. Hohohoho, Mister Vader, you’re going to be Mister Annagain! Comeday morm and, O, you’re devadered! Hahahaha, Mister Kinn, you’re going to be haydened again!"
]

for i in range(len(parody)):
    a, b = original[i], parody[i]
    print(len(a), len(b), levenshteinDistance(a,b))

for i in range(len(parody)):
    compare(original[i], parody[i])