<div dir="ltr">Slightly off-topic:<div><br></div><div>Norvig's code is both concise and -- to my eye -- highly readable. E.g.</div><div><pre class="" style="padding:2px;border:1px solid rgb(136,136,136);color:rgb(0,0,0);background-color:rgb(238,238,238)"><span class="" style="color:rgb(0,0,136)">def</span><span class=""> edits1</span><span class="" style="color:rgb(102,102,0)">(</span><span class="">word</span><span class="" style="color:rgb(102,102,0)">):</span><span class=""><br> splits </span><span class="" style="color:rgb(102,102,0)">=</span><span class=""> </span><span class="" style="color:rgb(102,102,0)">[(</span><span class="">word</span><span class="" style="color:rgb(102,102,0)">[:</span><span class="">i</span><span class="" style="color:rgb(102,102,0)">],</span><span class=""> word</span><span class="" style="color:rgb(102,102,0)">[</span><span class="">i</span><span class="" style="color:rgb(102,102,0)">:])</span><span class=""> </span><span class="" style="color:rgb(0,0,136)">for</span><span class=""> i </span><span class="" style="color:rgb(0,0,136)">in</span><span class=""> range</span><span class="" style="color:rgb(102,102,0)">(</span><span class="">len</span><span class="" style="color:rgb(102,102,0)">(</span><span class="">word</span><span class="" style="color:rgb(102,102,0)">)</span><span class=""> </span><span class="" style="color:rgb(102,102,0)">+</span><span class=""> </span><span class="" style="color:rgb(0,102,102)">1</span><span class="" style="color:rgb(102,102,0)">)]</span><span class=""><br> deletes </span><span class="" style="color:rgb(102,102,0)">=</span><span class=""> </span><span class="" style="color:rgb(102,102,0)">[</span><span class="">a </span><span class="" style="color:rgb(102,102,0)">+</span><span class=""> b</span><span class="" style="color:rgb(102,102,0)">[</span><span class="" style="color:rgb(0,102,102)">1</span><span class="" style="color:rgb(102,102,0)">:]</span><span class=""> </span><span class="" style="color:rgb(0,0,136)">for</span><span class=""> a</span><span class="" style="color:rgb(102,102,0)">,</span><span class=""> b </span><span class="" style="color:rgb(0,0,136)">in</span><span class=""> splits </span><span class="" style="color:rgb(0,0,136)">if</span><span class=""> b</span><span class="" style="color:rgb(102,102,0)">]</span><span class=""><br> transposes </span><span class="" style="color:rgb(102,102,0)">=</span><span class=""> </span><span class="" style="color:rgb(102,102,0)">[</span><span class="">a </span><span class="" style="color:rgb(102,102,0)">+</span><span class=""> b</span><span class="" style="color:rgb(102,102,0)">[</span><span class="" style="color:rgb(0,102,102)">1</span><span class="" style="color:rgb(102,102,0)">]</span><span class=""> </span><span class="" style="color:rgb(102,102,0)">+</span><span class=""> b</span><span class="" style="color:rgb(102,102,0)">[</span><span class="" style="color:rgb(0,102,102)">0</span><span class="" style="color:rgb(102,102,0)">]</span><span class=""> </span><span class="" style="color:rgb(102,102,0)">+</span><span class=""> b</span><span class="" style="color:rgb(102,102,0)">[</span><span class="" style="color:rgb(0,102,102)">2</span><span class="" style="color:rgb(102,102,0)">:]</span><span class=""> </span><span class="" style="color:rgb(0,0,136)">for</span><span class=""> a</span><span class="" style="color:rgb(102,102,0)">,</span><span class=""> b </span><span class="" style="color:rgb(0,0,136)">in</span><span class=""> splits </span><span class="" style="color:rgb(0,0,136)">if</span><span class=""> len</span><span class="" style="color:rgb(102,102,0)">(</span><span class="">b</span><span class="" style="color:rgb(102,102,0)">)</span>><span class="" style="color:rgb(0,102,102)">1</span><span class="" style="color:rgb(102,102,0)">]</span><span class=""><br> replaces </span><span class="" style="color:rgb(102,102,0)">=</span><span class=""> </span><span class="" style="color:rgb(102,102,0)">[</span><span class="">a </span><span class="" style="color:rgb(102,102,0)">+</span><span class=""> c </span><span class="" style="color:rgb(102,102,0)">+</span><span class=""> b</span><span class="" style="color:rgb(102,102,0)">[</span><span class="" style="color:rgb(0,102,102)">1</span><span class="" style="color:rgb(102,102,0)">:]</span><span class=""> </span><span class="" style="color:rgb(0,0,136)">for</span><span class=""> a</span><span class="" style="color:rgb(102,102,0)">,</span><span class=""> b </span><span class="" style="color:rgb(0,0,136)">in</span><span class=""> splits </span><span class="" style="color:rgb(0,0,136)">for</span><span class=""> c </span><span class="" style="color:rgb(0,0,136)">in</span><span class=""> alphabet </span><span class="" style="color:rgb(0,0,136)">if</span><span class=""> b</span><span class="" style="color:rgb(102,102,0)">]</span><span class=""><br> inserts </span><span class="" style="color:rgb(102,102,0)">=</span><span class=""> </span><span class="" style="color:rgb(102,102,0)">[</span><span class="">a </span><span class="" style="color:rgb(102,102,0)">+</span><span class=""> c </span><span class="" style="color:rgb(102,102,0)">+</span><span class=""> b </span><span class="" style="color:rgb(0,0,136)">for</span><span class=""> a</span><span class="" style="color:rgb(102,102,0)">,</span><span class=""> b </span><span class="" style="color:rgb(0,0,136)">in</span><span class=""> splits </span><span class="" style="color:rgb(0,0,136)">for</span><span class=""> c </span><span class="" style="color:rgb(0,0,136)">in</span><span class=""> alphabet</span><span class="" style="color:rgb(102,102,0)">]</span><span class=""><br> </span><span class="" style="color:rgb(0,0,136)">return</span><span class=""> set</span><span class="" style="color:rgb(102,102,0)">(</span><span class="">deletes </span><span class="" style="color:rgb(102,102,0)">+</span><span class=""> transposes </span><span class="" style="color:rgb(102,102,0)">+</span><span class=""> replaces </span><span class="" style="color:rgb(102,102,0)">+</span><span class=""> inserts</span><span class="" style="color:rgb(102,102,0)">)</span></pre></div><div class="gmail_extra"><div class="gmail_quote">Python's concise list comprehensions, destructuring, string slice operators, and operator overloading slot together nicely to make this kind of thing easy to knock out.</div><div class="gmail_quote"><br></div><div class="gmail_quote">I was able to achieve the following in Racket, but it's a fair bit of extra for a lesser result:</div><div class="gmail_quote"><div class="gmail_quote"><br></div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><font face="monospace, monospace">(define (edits1 word)<br></font><font face="monospace, monospace"> (define sub substring)<br></font><font face="monospace, monospace"> (define nth string-ref)<br></font><font face="monospace, monospace"> (define splits (for/list ([i (range (add1 (string-length word)))])<br></font><font face="monospace, monospace"> (cons (sub word 0 i) (sub word i))))<br></font><font face="monospace, monospace"> <br></font><font face="monospace, monospace"> (define (map-splits min-b f [chars '(dummy)])<br></font><font face="monospace, monospace"> (for*/list ([split splits]<br></font><font face="monospace, monospace"> [a (in-value (car split))]<br></font><font face="monospace, monospace"> [b (in-value (cdr split))]<br></font><font face="monospace, monospace"> #:when (>= (string-length b) min-b)<br></font><font face="monospace, monospace"> [ch chars])<br></font><font face="monospace, monospace"> (f a b ch)))<br></font><font face="monospace, monospace"> <br></font><font face="monospace, monospace"> (let ([deletes (map-splits 1 (λ (a b _) (~a a (sub b 1))))]<br></font><font face="monospace, monospace"> [transposes (map-splits 2 (λ (a b _) (~a a (nth b 1) (nth b 0) (sub b 2))))]<br></font><font face="monospace, monospace"> [replaces (map-splits 1 (λ (a b ch) (~a a ch (sub b 1))) alphabet)]<br></font><font face="monospace, monospace"> [inserts (map-splits 0 (λ (a b ch) (~a a ch b)) alphabet)])<br></font><font face="monospace, monospace"> (append deletes transposes replaces inserts)))</font></blockquote><div><br></div><div>Comments? Suggestions?</div><div><br></div><div>Dan</div><div> </div></div></div></div><div class="gmail_extra"><div class="gmail_signature"><div dir="ltr"></div></div> </div></div>