Skip to content

Instantly share code, notes, and snippets.

@mattsan
Created February 11, 2013 12:10
Show Gist options
  • Save mattsan/4754107 to your computer and use it in GitHub Desktop.
Save mattsan/4754107 to your computer and use it in GitHub Desktop.
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