======= Nordpolen - ClasseNisses Ohlyckssäkrade Modem (COM) =======
De stiger in till COM. En gladlynt nisse möter upp dom. "Välkomna, jag är ClasseNisse. Det är inte varje dag jag får besök här. Ända sen dom släckte ner Good-Game-nätet (2G) har jag inte haft några kunder. Dom säger att dom 'inte har någon täckning' här på Nordpolen.", säger han.
"Vi utvecklar nya modem i en rasande takt. Vilken modell vill ni ha? Jag kan rekommendera den nya Please-Lets-Synchronize-63 (PLS63), en riktig pang-modell kan jag säga. Annars har vi också You-Only-Listen-Once (YOLO), lite äldre men riktigt stabil", fortsätter han.
Nissarna säger att det gamla modemet var av versionen Tried-but-Maybe-Never-Tested (TMNT) och ClasseNisse funderar och svarar: "Det där är ett riktigt gammalt modem. Tror inte jag har det i lager längre. Men jag borde ha en version som är bakåtkompatibel med den".
Han plockar fram en lista med alla modeller han har i lager:
PLS63
YOLO
5TQCTXOM2H48EU
40N.6724COQK
R2TF.OQR.UJ4
VC0.FXPXRGKHE
IUB0H3OSPK5BU5
.D1DARULMWVTSPI
JC5YS.57NBD
XQYI4FVWK9J
J2UB3DXASERF2JQ
.OQWL4V9VC5TD7
QCDKEHUHQ.L
5GGX6WIAZX
PRE5JKSF9M2K4X
L87EQSR8X0S
7DYJTIVX5QWY
D.DL9QYRH6NL
2V7M.93D91
N8PU8RCYGXZ
HSBTBTY..JD
AHL7MT0Z.DK
QRS.3FS3EHM66
N.Y.QJIHI5
TFT.UN8BERGF
ZZ54MV.SKRKGG97
VAY1W8ZX3SZM7
PYDQPGSYZXXNW
HR.YIZ.REOY4D.Z
IKJ.SIUL3NN84
RMCHIV0IA16
CQ69QT93XRP2YM.
C2BD.0S7LH9E78O
VWIY.NCDV7
SC.HT.S0BV95
H9ODM1N6J0S.
6.Y.VU6G5KMZ8..
EZN665ZKHH7A2II
JY5ZVBTO3O685
D.XRTZNE.C7ASF
.AB5O9477MGUML
CSI3J03G.3JCKX
GB0NY4S.9PACH76
4R1E4INPTX3C
E2LWC9K..MT5.CY
.I.VFMUCL7H
CGXNTV00NWRB
SYRPZ...C3EY
60JDKB17A77
R8.5SIS4O.C.CC
0.9100I761TPYDW
4YCINFPJ.87
ZHXIVEKC8ZX
2YAWJZNJAMTZD
8.0A9OHY6XD1Q
.FHPOI6SLNDZ2Y
7XY902E14YV7YF
P3.M.TRGVM.P.
OTYCM.7HDR
NHX0BJN4JLPN
.AMUHA.AL2W9KXI
XOABW9MR.DII
.1YQ25P.5XNJV
X1OH.T6HU1E7T
7R.DX0LP7Z
.QMM376.JFQ.Z
4FAOB8LW.U
PQOETFDIHA2A6GB
BZ5VWM8V18JLI.F
GMQEIG.9DGPE
25A.A.5PX4U9.CC
O1WWZN.W.VBP
Z.UIGWMRO8A5Y4
224KMTL9PHY434
Z1GON.4RECKEG
I9.JU.CQ0CELL
Men han kan inte komma ihåg vilken version som är bakåtkompatibel med TMNT. Han rotar runt i en byrålåda och tar fram en bunt papper. "Det här är grejer ska ni veta! Här har jag skrivit ner alla modem jag någonsin gjort och vilka dess efterföljare är"
Här är versionslistan:
3TUOXNWX44.GTZL -> I9.JU.CQ0CELL
FR1MOQOUHRU.. -> TV3D0LRJAHW.4
NRW.CJ36JP.J -> BBV1I6W.0CVT33
.N.E.MX0ULSOFDM -> .1YQ25P.5XNJV
2UB.LNJI6A9U. -> 8K.Q1GY1VIENTN.
CXWN2K8X55F -> .AB5O9477MGUML
06DPO06FYEW -> QRS.3FS3EHM66
J702QW6W4H.ZB -> 1WN4K47PW2D7ZUQ
IMG.V4MANAX -> VC0.FXPXRGKHE
G44VW6.IMZUL -> IKJ.SIUL3NN84
LTU.6IMPTGU2E9C -> O2VLI34.YO5YZB
B9MU1XZP5S -> ITJM875LTZ9
2O.WGM35356.IW -> BZ5VWM8V18JLI.F
01FG439F96R -> Z.UIGWMRO8A5Y4
UU6R2ZRYI6B8 -> .QMM376.JFQ.Z
LTU.6IMPTGU2E9C -> LYI0FPP.RHP9
J702QW6W4H.ZB -> 5.M7XGKTB1N10X1
LOZ.7XZM1MJ. -> 7DYJTIVX5QWY
J8WP251II2.K -> EA5T4VNXB3P10J3
EA5T4VNXB3P10J3 -> 5GGX6WIAZX
LTU.6IMPTGU2E9C -> 06DPO06FYEW
RQUGF.LWBT -> VAY1W8ZX3SZM7
PJ.C6A9AKCGNZ -> JC5YS.57NBD
SMY5ZN3.T1 -> 40N.6724COQK
PDGP2Q.ALKMU7 -> J8WP251II2.K
GMFP1MSDFK61CL -> 88QBHRMO6ZMFKS
.BRVUY7NYWME -> 2O.WGM35356.IW
EA5T4VNXB3P10J3 -> .OQWL4V9VC5TD7
CXWN2K8X55F -> CSI3J03G.3JCKX
.8Z8RSLI8F -> IVOL3SMUQBIYAK
PJ.C6A9AKCGNZ -> J2UB3DXASERF2JQ
8K.Q1GY1VIENTN. -> 5TQCTXOM2H48EU
PJ.C6A9AKCGNZ -> XQYI4FVWK9J
88QBHRMO6ZMFKS -> ZZ54MV.SKRKGG97
WHY3VME34N.VUBV -> VWIY.NCDV7
TV3D0LRJAHW.4 -> G44VW6.IMZUL
TMNT -> OYZ5SJVG0HF6IPP
.N.E.MX0ULSOFDM -> 7R.DX0LP7Z
1WN4K47PW2D7ZUQ -> 60JDKB17A77
8.W0TF.PKOG -> .AMUHA.AL2W9KXI
XTPOUEHBORZGRQ -> EZN665ZKHH7A2II
8YUTU.KOYZFB -> ZHXIVEKC8ZX
2O.WGM35356.IW -> 25A.A.5PX4U9.CC
IVOL3SMUQBIYAK -> SC.HT.S0BV95
LOZ.7XZM1MJ. -> L87EQSR8X0S
G44VW6.IMZUL -> RMCHIV0IA16
SI7GUBFARQD -> XT6JD3HABO4ODMR
G5VV0PG.LQGY3 -> UU6R2ZRYI6B8
2O.WGM35356.IW -> GMQEIG.9DGPE
5.M7XGKTB1N10X1 -> R8.5SIS4O.C.CC
OYZ5SJVG0HF6IPP -> B9MU1XZP5S
SI7GUBFARQD -> .BRVUY7NYWME
BBV1I6W.0CVT33 -> 4R1E4INPTX3C
88QBHRMO6ZMFKS -> N.Y.QJIHI5
.8Z8RSLI8F -> XTPOUEHBORZGRQ
TV3D0LRJAHW.4 -> WHY3VME34N.VUBV
SI7GUBFARQD -> G5VV0PG.LQGY3
BBV1I6W.0CVT33 -> GB0NY4S.9PACH76
8YUTU.KOYZFB -> 4YCINFPJ.87
B22LD.LAFVZUG -> 2YAWJZNJAMTZD
P.MEY0V5MJWT2E5 -> PJ.C6A9AKCGNZ
PDGP2Q.ALKMU7 -> 2UB.LNJI6A9U.
J8WP251II2.K -> LOZ.7XZM1MJ.
4J57X6Q..1R -> G0APR4TLCXX
1WN4K47PW2D7ZUQ -> SYRPZ...C3EY
UU6R2ZRYI6B8 -> PQOETFDIHA2A6GB
ITJM875LTZ9 -> B22LD.LAFVZUG
O2VLI34.YO5YZB -> D.DL9QYRH6NL
XT6JD3HABO4ODMR -> 4.KJY.OYH.L
IMG.V4MANAX -> IUB0H3OSPK5BU5
4.KJY.OYH.L -> OTYCM.7HDR
WHY3VME34N.VUBV -> C2BD.0S7LH9E78O
IMOQTF0S0O -> JY5ZVBTO3O685
06DPO06FYEW -> AHL7MT0Z.DK
SMY5ZN3.T1 -> R2TF.OQR.UJ4
4J57X6Q..1R -> PDGP2Q.ALKMU7
PDGP2Q.ALKMU7 -> P.MEY0V5MJWT2E5
XTPOUEHBORZGRQ -> 6.Y.VU6G5KMZ8..
IMOQTF0S0O -> D.XRTZNE.C7ASF
GMFP1MSDFK61CL -> RQUGF.LWBT
IMG.V4MANAX -> .D1DARULMWVTSPI
OYZ5SJVG0HF6IPP -> FR1MOQOUHRU..
LYI0FPP.RHP9 -> N8PU8RCYGXZ
BFXL99WWTT -> CGXNTV00NWRB
TMNT -> 4J57X6Q..1R
UU6R2ZRYI6B8 -> 4FAOB8LW.U
3TUOXNWX44.GTZL -> Z1GON.4RECKEG
5.M7XGKTB1N10X1 -> 0.9100I761TPYDW
8.W0TF.PKOG -> XOABW9MR.DII
G0APR4TLCXX -> GMFP1MSDFK61CL
B9MU1XZP5S -> J702QW6W4H.ZB
3TUOXNWX44.GTZL -> 224KMTL9PHY434
G0APR4TLCXX -> LTU.6IMPTGU2E9C
IVOL3SMUQBIYAK -> H9ODM1N6J0S.
G44VW6.IMZUL -> HR.YIZ.REOY4D.Z
O2VLI34.YO5YZB -> 2V7M.93D91
.BRVUY7NYWME -> 3TUOXNWX44.GTZL
FR1MOQOUHRU.. -> .8Z8RSLI8F
E.XS83KLF20T -> 7XY902E14YV7YF
ITJM875LTZ9 -> 8YUTU.KOYZFB
.BRVUY7NYWME -> 01FG439F96R
J702QW6W4H.ZB -> BFXL99WWTT
B22LD.LAFVZUG -> 8.0A9OHY6XD1Q
8K.Q1GY1VIENTN. -> YOLO
P.MEY0V5MJWT2E5 -> IMG.V4MANAX
LYI0FPP.RHP9 -> HSBTBTY..JD
BFXL99WWTT -> .I.VFMUCL7H
XT6JD3HABO4ODMR -> 8.W0TF.PKOG
01FG439F96R -> O1WWZN.W.VBP
RQUGF.LWBT -> PYDQPGSYZXXNW
2UB.LNJI6A9U. -> SMY5ZN3.T1
FR1MOQOUHRU.. -> NRW.CJ36JP.J
OYZ5SJVG0HF6IPP -> SI7GUBFARQD
E.XS83KLF20T -> P3.M.TRGVM.P.
EA5T4VNXB3P10J3 -> QCDKEHUHQ.L
E.XS83KLF20T -> .FHPOI6SLNDZ2Y
88QBHRMO6ZMFKS -> TFT.UN8BERGF
8K.Q1GY1VIENTN. -> PLS63
.N.E.MX0ULSOFDM -> X1OH.T6HU1E7T
.8Z8RSLI8F -> IMOQTF0S0O
NRW.CJ36JP.J -> CXWN2K8X55F
4.KJY.OYH.L -> NHX0BJN4JLPN
ITJM875LTZ9 -> E.XS83KLF20T
G5VV0PG.LQGY3 -> .N.E.MX0ULSOFDM
LOZ.7XZM1MJ. -> PRE5JKSF9M2K4X
WHY3VME34N.VUBV -> CQ69QT93XRP2YM.
BBV1I6W.0CVT33 -> E2LWC9K..MT5.CY
Listan är konstruerad som så att varje rad visar den gamla versionen till vänster följt av en pil (->) och sen den nya versionen till höger.
Observera att en version kan ha flera olika efterföljare. Vissa av dom är bakåtkompatibla, andra är det inte. Men alla versioner har alltid en bakåtkompatibel efterföljare (om den inte är den senaste versionen).
För att avgöra vilken version som är bakåtkompatibel beräknar man Levenshtein-avståndet mellan den gamla versionens namn och vardera av dess uppföljare. Den med det minsta Levenshtein-avståndet är den bakåtkompatibla efterföljaren.
T.ex.
ABC -> ABCDE
ABC -> ABCE
visar att ABC efterföljdes av ABCDE och ABCE. De har Levenshtein-avstånden 2 respektive 1 från ABC.
Således är ABCE bakåtkompatibel eftersom den har det minsta avståndet.
Vilken av modellerna i lager är bakåtkompatibel med TMNT?
"Use the dict, Luke" - Ben Kenobi
Levenshteinavståndet kan beräknas med funktionen:
def levenstein(s1: str, s2: str) -> int: if len(s1) == 0: return len(s2) if len(s2) == 0: return len(s1) head1 = s1[0] head2 = s2[0] tail1 = s1[1:] tail2 = s2[1:] if head1 == head2: return levenstein(tail1, tail2) else: return 1 + min(levenstein(tail1, s2), levenstein(s1, tail2), levenstein(tail1, tail2))