<div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div>I'm writing because I do not currently understand my next step. I may blog this. This is interesting because for most of the PWC challenges, there may be clever here or there, but mostly it's a simple matter of programming.<br><br><a href="https://perlweeklychallenge.org/blog/perl-weekly-challenge-096/" target="_blank">The Weekly Challenge - 096 (perlweeklychallenge.org)</a><b><br><br>You are given two strings $S1 and $S2.<br></b></div><div><b><br></b></div><div><b>Write a script to find out the minimum operations required to convert $S1 into $S2.<br>The operations can be insert, remove or replace a character.<br>Please check out Wikipedia page (</b><a href="https://en.wikipedia.org/wiki/Edit_distance" target="_blank">Edit distance - Wikipedia</a><b>) for more information.</b></div><br>The first example in the challenge and the wikipedia page is "kitten" and "sitting". There are three changes necessary to turn one to the other, shown by capitals.<br><br> kitten<br> Sitten<br> sittIn<br> sittinG<br clear="all"><div><br>As mentioned in the Wikipedia article, we can get to the count of steps using the Levenshtein Distance. I know about that because I saw it in perlbrew internals: This is how it knows to <br>suggest "exec" when you accidentally type "perlbrew esec", but I hadn't looked into HOW it works inside. So, I can say "there are three operations" but I can't, within the program, say we have to insert a G, replace K with S, and replace E with I.<br><br>So I finally read to understand the LD algorithm, rather than restate it from Wikipedia and say that's that. To demonstrate, we'll start comparing "test" with "test". In the below examples, the first row and the first column are preset, counting up from zero.<br><br><font face="monospace"> t e s t<br></font><div><font face="monospace"> [0,1,2,3,4]<br></font></div><div><font face="monospace">t [1,0,1,2,3]</font></div><div><font face="monospace">e [2,1,0,1,2]</font></div><div><font face="monospace">s [3,2,1,0,1]</font></div><div><font face="monospace">t [4,3,2,1,0]</font></div></div><div><br>If nothing is different in position [i,j], it simply copies the value of position i-1, j-i, and that transfers down,so that position [-1,-1], the last column of the last row, is 0, so there's no difference.</div><div><br><font face="monospace"> t e s t<br></font><div><font face="monospace"> [0,1,2,3,4]<br></font></div><div><font face="monospace">t [1,0,1,2,3]</font></div><div><font face="monospace">e [2,1,0,1,2]</font></div><div><font face="monospace">x [3,2,1,1,2]</font></div><div><font face="monospace">t [4,3,2,2,1]</font></div></div><div><br></div><div>Here we see that [3,3] is 1. It got that way because there is a difference, and took the minimum value of [2,2], [2,3], and [3,2], then added one.<br><br><div><font face="monospace"> l i g h t s</font></div><div><font face="monospace"> [0,1,2,3,4,5,6]</font></div><div><font face="monospace">s [1,1,2,3,4,5,5]</font></div><div><font face="monospace">l [2,1,2,3,4,5,6]</font></div><div><font face="monospace">i [3,2,1,2,3,4,5]</font></div><div><font face="monospace">g [4,3,2,1,2,3,4]</font></div><div><font face="monospace">h [5,4,3,2,1,2,3]</font></div><div><font face="monospace">t [6,5,4,3,2,1,2]</font></div><div><br></div><div>This compares "slight" with "lights", which, given the add, remove or change rules, give us two. This would be removing the S from the beginning and adding S to the end. 2 changes, as [-1,-1] indicates.</div><br>I'm <i>thinking</i> that the way forward is to travel up and to the left with the minimum of those three values, making no change if the minimum equals the current and <br><br>This Looks Like A Job For <i>RECURSION!</i> , but I believe most challenges look like that, until I think harder. Anyone else have thoughts about a better way to solve this?</div>-- <br><div dir="ltr"><div dir="ltr"><div dir="ltr">Dave Jacoby<br>
<a href="mailto:jacoby.david@gmail.com" target="_blank">jacoby.david@gmail.com</a><br>
<br>“There is nothing obvious” <br> — Theo<br></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>