lambdaway :: lcs

8 | list | login |load

| |

_h1 longuest common subsequence
_p Following [[rosetta|https://rosettacode.org/wiki/Longest_common_subsequence]]

_h2 javascript

{pre
function lcs(a0, b0) '{
  var a1 = a0.substr(0, a0.length - 1);
  var b1 = b0.substr(0, b0.length - 1);
  
  if (a0.length === 0 || b0.length === 0) {
    return '';
  } else if (a0.charAt(a0.length - 1) === 
             b0.charAt(b0.length - 1)) {
    return lcs(a1, b1) + a0.charAt(a0.length - 1);
  } else {
    var x = lcs(a0, b1);
    var y = lcs(a1, b0);
    return (x.length > y.length) ? x : y;
  }
}

'{jslcs testing123testing thisisatest}
-> tsitest    // 130ms
}

_h2 lambdatalk

{prewrap
'{def lcs
 {def lcs.rec
  {lambda {:a :b :w}
   {if {or {< {W.length :a} 2} {< {W.length :b} 2} }
    then {W.rest :w}
    else {if {W.equal? {W.first :a} {W.first :b}} 
          then {lcs.rec {W.rest :a} {W.rest :b} :w{W.first :a}}
          else {let { {:x {lcs.rec :a {W.rest :b} :w}} 
                      {:y {lcs.rec {W.rest :a} :b :w}}
                    } {if {> {W.length :x} {W.length :y}}
                       then :x
                       else :y} }}}}}
 {lambda {:a :b}
  {lcs.rec :a# :b# #}}}  
-> {def lcs
 {def lcs.rec
  {lambda {:a :b :w}
   {if {or {< {W.length :a} 2} {< {W.length :b} 2} }
    then {W.rest :w}
    else {if {W.equal? {W.first :a} {W.first :b}} 
          then {lcs.rec {W.rest :a} {W.rest :b} :w{W.first :a}}
          else {let { {:x {lcs.rec :a {W.rest :b} :w}} 
                      {:y {lcs.rec {W.rest :a} :b :w}}
                    } {if {> {W.length :x} {W.length :y}}
                       then :x
                       else :y} }}}}}
 {lambda {:a :b}
  {lcs.rec :a# :b# #}}}

'{lcs testing123testing thisisatest}
-> tsitest     // 23000ms

}

{script 
  function lcs(a0, b0) {
    var a1 = a0.substr(0, a0.length - 1);
    var b1 = b0.substr(0, b0.length - 1);
  
    if (a0.length === 0 || b0.length === 0) {
      return '';
    } else if (a0.charAt(a0.length - 1) === 
               b0.charAt(b0.length - 1)) {
      return lcs(a1, b1) + a0.charAt(a0.length - 1);
    } else {
      var x = lcs(a0, b1);
      var y = lcs(a1, b0);
      return (x.length > y.length) ? x : y;
    }
  }

LAMBDATALK.DICT["jslcs"] = function() {
    var args = arguments[0].split(" ");
    return lcs( args[0], args[1] )
  };

LAMBDATALK.DICT["foo"] = function() {
    var a = [1,2,3,4,5];
    return a[a.length -1]
  };
}