% Longest Common Subsequence, 04-feb-2014 % LPImmes % Employ pragma declaration in order to memoize. %longCommSubseq 487>uname -a %Darwin luke-immess-imac-2.local 13.0.0 Darwin Kernel %Version 13.0.0: Thu Sep 19 22:22:27 PDT 2013; %root:xnu-2422.1.72~6/RELEASE_X86_64 x86_64 %Make sure that .bashrc has: % MERCURY_GCC=/Developer-3.2/usr % ... % $MERCURY_GCC/bin:\ % ... % % Comment out this path entry for compiling, e.g., python modules. % %longCommSubseq 485>gcc --version %i686-apple-darwin10-gcc-4.2.1 (GCC) 4.2.1 (Apple Inc. build 5646) %Copyright (C) 2007 Free Software Foundation, Inc. %This is free software; see the source for copying conditions. There is NO %warranty; not even for MERCHANTABILITY %or FITNESS FOR A PARTICULAR PURPOSE. % %longCommSubseq 483>mmc -version %mercury_compile: invalid grade `ion' %Mercury Compiler, version 13.05, configured for x86_64-apple-darwin12.5.0 %Copyright (C) 1993-2013 The University of Melbourne %Usage: mmc [] %Use `mmc --help' for more information. %BUILD, either one: % mmc --make --fully-strict -E -v -O 0 --use-subdirs longCommSubseq % mmc --grade none.gc.stseg --fully-strict -E -v -O 0 --use-subdirs longCommSubseq % RUN: % longCommSubseq 507>./longCommSubseq :- module longCommSubseq. % name of file, for now :- interface. :- import_module io. :- pred main(io, io). :- mode main(di, uo) is det. :- implementation. :- import_module pair, char, int, list, array, string. :- func findLngCmnSubsq(pair(list(string), list(string)), string) = string. :- mode findLngCmnSubsq(in, in) = out is det. :- pragma memo(findLngCmnSubsq/2). % Cache old results; no need to write additional code. findLngCmnSubsq(Pair, CurLngCmn) = LngCmnSq :- % Don't use ';' even though a little easier to read, because this neccessites 'multi'. % And multi can be problematic with memo pragma. % Compare left to right, 1st element, rest...x First = fst(Pair), Second = snd(Pair), A = list.det_index0(First, 0), B = list.det_index0(Second, 0), (if (A = ""; B = "") % ; means or then LngCmnSq = CurLngCmn else % End char is =, split further... list.det_drop(1, First, First_remaining), list.det_drop(1, Second, Second_remaining), (if A = B then LngCmnSq = findLngCmnSubsq( pair(First_remaining, Second_remaining), CurLngCmn ++ A) % Compare shorter one to a longer one, split further... else S1 = findLngCmnSubsq( pair(First, Second_remaining), CurLngCmn), S2 = findLngCmnSubsq( pair(First_remaining, Second), CurLngCmn), (if string.length(S1) >= string.length(S2) then LngCmnSq = S1 else LngCmnSq = S2 ) % S1 >= S2 ) % A = B ). % empty test :- pred charToStrLst(list(char), list(string), list(string)). :- mode charToStrLst(in, in, out) is det. charToStrLst([H | T], Accum, LstStr) :- % [H|T] can fail (if list.is_empty([H|T]) then LstStr = Accum else format("%c", [c(H)], Str), charToStrLst(T, [Str | Accum], LstStr) ). :- func longestCommonSubsequence(int) = string. :- mode longestCommonSubsequence(in) = out is det. % because of charToStrLst longestCommonSubsequence(Indx) = LngCmnSubsq :- % Input test cases from tst/0: 0, 1, 2, 3, 4. PairsTst = array.lookup(tst, Indx), Apair = list.det_index0(PairsTst, 0), charToStrLst(string.to_char_list(Apair), [], LstFrst), Bpair = list.det_index0(PairsTst, 1), charToStrLst(string.to_char_list(Bpair), [], LstSnd), PairsLst = pair(LstFrst, LstSnd), LngCmnSubsq = findLngCmnSubsq(PairsLst, ""). :- func tst = array(list(string)). :- mode tst = out is det. % When prompted for test index, use either: 0, 1, 2, 3, 4. tst = array.array([ ["a", "" ] ] ). main(In, Out) :- write_string("Input test case 0, 1, 2, 3, 4. Output longest common subsequence.\n^d to quit.\n", In, Out1), mainAux(Out1, Out). :- pred mainAux(io, io). :- mode mainAux(di, uo) is det. mainAux(In, Out) :- read_line_as_string(Result, In, Out0), % blank line, wait for input from console ( Result = eof, % c^d write_string("хорошо́ EOF, Quit\n", Out0, Out) ; Result = error(Error), format("IO error: %s\n", [s(io.error_message(Error))], Out0, Out) % IO error from readLine ; Result = ok(IndxStr), Indx = string.det_to_int(string.strip(IndxStr)), % use det_ so func. is det format("Longest Common Subsequence: '%s'\n", [ s(longestCommonSubsequence(Indx)) ], Out0, Out1), mainAux(Out1, Out) % do it again ).