backtracking

backtracking.cpp

#include <iostream>
#include <string>

template<typename ITEM, typename CONTAINER>
int search(const ITEM& item, const CONTAINER& container)
{
    for(int i = 0; i < container.size() - 2; ++i)
    {
        if((container[i] == item) && (container[i + 1] == item) && (container[i + 2] == item))
        {
            return i;
        }
    }

    for(int i = 0; i < container.size() - 1; ++i)
    {
        if((container[i] == item) && (container[i + 1] == item))
        {
            return i;
        }
    }

    for(int i = 0; i < container.size(); ++i)
    {
        if(container[i] == item)
        {
            return i;
        }
    }

    return -1;
}

int main(int, char* [])
{
    static const std::string values[] =
    {
        "AAAAAAAAAAAA",
        "AA-AAA-AAA-A",
        "-AA-AA-AAA--",
        "-AA-AA-AA-AA",
        "-A--A--A--AA",
        "-A--A--A--A-",
        "------------"
    };

    for(int i = 0; i < 7; ++i)
    {
        int pos = search('A', values[i]);
        std::cout << values[i] << " => " << pos << "\n";
    }

    return 0;
}

backtracking.hs

import Control.Monad

search3 _ [_,_] = Nothing
search3 c (x1:x2:x3:xs) = if (c == x1) && (c == x2) && (c == x3) then Just 0 else fmap (1+) (search3 c (x2:x3:xs))

search2 _ [_] = Nothing
search2 c (x1:x2:xs) = if (c == x1) && (c == x2) then Just 0 else fmap (1+) (search2 c (x2:xs))

search1 _ [] = Nothing
search1 c (x1:xs)  = if c == x1 then Just 0 else fmap (1+) (search1 c xs)

search c xs = let Just n = (search3 c xs) `mplus` (search2 c xs) `mplus` (search1 c xs) `mplus` (Just (-1)) in n

values = [ "AAAAAAAAAAAA"
       , "AA-AAA-AAA-A"
       , "-AA-AA-AAA--"
       , "-AA-AA-AA-AA"
       , "-A--A--A--AA"
       , "-A--A--A--A-"
       , "------------"
       ]

main = mapM_ (\xs -> do putStr xs; putStr " => "; putStrLn $ show (search 'A' xs)) values

backtracking.prolog

search3(C, [C,C,C|_], 0).
search3(C, [X|XS], POS) :- search3(C, XS, POS1), POS is POS1 + 1.

search2(C, [C,C|_], 0).
search2(C, [X|XS], POS) :- search2(C, XS, POS1), POS is POS1 + 1.

search1(C, [C|_], 0).
search1(C, [X|XS], POS) :- search1(C, XS, POS1), POS is POS1 + 1.

search(C, XS, POS) :- search3(C, XS, POS), !.
search(C, XS, POS) :- search2(C, XS, POS), !.
search(C, XS, POS) :- search1(C, XS, POS), !.
search(_, _, -1)   :- !.

values([ "AAAAAAAAAAAA"
       , "AA-AAA-AAA-A"
       , "-AA-AA-AAA--"
       , "-AA-AA-AA-AA"
       , "-A--A--A--AA"
       , "-A--A--A--A-"
       , "------------"
       ]).

main([]).
main([D|DS]) :-
  search(0'A, D, POS),
  format('~s => ~d~n', [D, POS]),
  main(DS).