liancheng
BAN USERMy C++ code here. Solved in DFS style, heavily depends on Boost and STL to shorten the code.
The input file:
cat dot
cat cot dot dog
Here's the code:
#include <boost/bind.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/istream_range.hpp>
using namespace boost;
using namespace boost::adaptors;
using namespace std;
bool match (string const& lhs, string const& rhs)
{
if (lhs.length () != rhs.length ())
return false;
auto pos = mismatch (lhs, rhs);
if (pos.first == lhs.cend ())
return false;
pos = mismatch (make_iterator_range (pos.first + 1, lhs.cend ()),
make_iterator_range (pos.second + 1, rhs.cend ()));
return pos.first == lhs.cend ();
}
template <
typename ForwardTraversalRange,
typename OutputIterator
>
bool solve (string const& src,
string const& dst,
ForwardTraversalRange words,
OutputIterator output)
{
if (src == dst)
return true;
if (empty (words))
return false;
vector<string> candidates;
auto pred = bind (match, _1, src);
copy (words | filtered (pred), back_inserter (candidates));
for (auto word : candidates) {
vector<string> new_words;
auto pred = bind (not_equal_to<string> (), _1, src);
copy (words | filtered (pred), back_inserter (new_words));
if (solve (word, dst, new_words, output)) {
*output = word;
return true;
}
}
return false;
}
int main (int argc, char* argv [])
{
string src, dst;
vector<string> words;
cin >> src >> dst;
copy (istream_range<string> (cin), back_inserter (words));
vector<string> path;
solve (src, dst, words, back_inserter (path));
path.push_back (src);
copy (path | reversed, ostream_iterator<string> (cout, "\n"));
return 0;
}
- liancheng November 16, 2012Here's my DFS in Racket Scheme:
#lang racket
(define (match? src str)
(and (= (string-length src)
(string-length str))
(= 1
(count identity
(map (lambda (lhs rhs) (not (eq? lhs rhs)))
(string->list src)
(string->list str))))))
(define (solve src dst words)
(let solve* ((src src)
(words words)
(path '()))
(cond [(equal? src dst) (cons #t (cons src path))]
[(null? words) (cons #f path)]
[else (call/cc
(lambda (return)
(let ([words (remove src words)])
(for-each (lambda (word)
(let* ([path (cons src path)]
[result (solve* word words path)])
(when (car result)
(return (cons #t (cdr result))))))
(filter ((curry match?) src) words)))
(cons #f path)))])))
(let* ([src "cat"]
[dst "dog"]
[words '("cat" "cot" "bat" "dog" "dot")]
[result (solve src dst words)])
(if (car result)
(printf "~a~%" (reverse (cdr result)))
(printf "failed~%")))
Here's a working Python code:
- liancheng November 18, 2012