backtracking
#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; | |
} |
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 |
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). |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment