dongre.avinash
BAN USER1. Declare array of the type X of size 2
2. subtract address of 1st elemement x[0] from 2nd element i.e. x[1]
this will give you size of X
Kd-Tree is the data structure which will solve this problem.
- dongre.avinash August 23, 2011Here is my simpler version
1. Build a set of all the words ( from a dictionary )
2. Have one pointer left, which points to start of the string
3. have another pointer right which pointers to the end of the string
4. try finding the word ( left .. right ) in the set
5. If found you got the word
6. if not, reduce right pointer by 1
7. goto step 4
8. if you find the word, move left equal to left + size of the word found
9. continue this till left is not equal to right.
#include <set>
#include <fstream>
#include <string>
#include <iostream>
std::set<std::string> pDict;
int BuildDictionary(const char *filename) {
std::ifstream dictFile(filename);
if ( dictFile.peek() == EOF ) {
return -1;
}
std::string line;
if (dictFile.is_open()) {
while (! dictFile.eof() ) {
std::getline (dictFile,line);
pDict.insert(line);
}
dictFile.close();
} else {
return EXIT_FAILURE;
}
return 0;
}
int main ( int argc, char **argv) {
//BuildDictionary(argv[1]);
pDict.insert("i");
pDict.insert("this");
pDict.insert("saw");
pDict.insert("is");
pDict.insert("a");
pDict.insert("some");
pDict.insert("awesome");
std::string word(argv[1]);
std::string::iterator left = word.begin();
std::string::iterator right = word.end();
std::string::iterator rightMoving = left + 1;
while ( left != right ) {
std::string tempWord(left, right);
if ( pDict.find(tempWord) != pDict.end()) {
std::cout << tempWord << " ";
left = left + tempWord.size();
right = word.end();
continue;
} else {
right--;
}
}
return 0;
}
KD-Tree is appropriate data structure for this problem.
- dongre.avinash August 03, 2011#include <stdio.h>
#include <string>
#include <vector>
#include <queue>
#include <fstream>
#include <iostream>
#include <sstream>
#include <iterator>
#include <algorithm>
#include <map>
class BkTree {
public:
BkTree();
~BkTree();
void insert(std::string m_item);
int getWithinDistance(std::string center, size_t k);
std::vector<std::string> wordVector;
void solve();
int BuildDictionary();
int ReadInputFile(const char *inpFileName);
private:
size_t EditDistance( const std::string &s, const std::string &t );
struct Node {
std::string m_item;
size_t m_distToParent;
Node *m_firstChild;
Node *m_nextSibling;
Node(std::string x, size_t dist);
~Node();
};
Node *m_root;
protected:
};
BkTree::BkTree() {
m_root = NULL;
}
BkTree::~BkTree() {
if( m_root )
delete m_root;
}
BkTree::Node::Node(std::string x, size_t dist) {
m_item = x;
m_distToParent = dist;
m_firstChild = m_nextSibling = NULL;
}
BkTree::Node::~Node() {
if( m_firstChild )
delete m_firstChild;
if( m_nextSibling )
delete m_nextSibling;
}
void BkTree::insert(std::string m_item) {
if( !m_root ) {
m_root = new Node(m_item, -1);
return;
}
Node *t = m_root;
while( true ) {
size_t d = EditDistance( t->m_item, m_item );
if( !d )
return;
Node *ch = t->m_firstChild;
while( ch ) {
if( ch->m_distToParent == d ) {
t = ch;
break;
}
ch = ch->m_nextSibling;
}
if( !ch ) {
Node *newChild = new Node(m_item, d);
newChild->m_nextSibling = t->m_firstChild;
t->m_firstChild = newChild;
break;
}
}
}
size_t BkTree::EditDistance( const std::string &left, const std::string &right ) {
size_t asize = left.size();
size_t bsize = right.size();
std::vector<size_t> prevrow(bsize + 1);
std::vector<size_t> thisrow(bsize + 1);
for(size_t i = 0; i <= bsize; i++)
prevrow[i] = i;
for(size_t i = 1; i <= asize; i++) {
thisrow[0] = i;
for(size_t j = 1; j <= bsize; j++) {
thisrow[j] = std::min(prevrow[ j - 1] + size_t(left[ i - 1] != right[ j - 1]),
1 + std::min(prevrow[j],thisrow[ j - 1]) );
}
std::swap(thisrow,prevrow);
}
return prevrow[bsize];
}
int BkTree::getWithinDistance(std::string center, size_t k) {
if( !m_root ) return 0;
int found = 0;
std::queue< Node* > nodeQueue;
nodeQueue.push( m_root );
while( !nodeQueue.empty() ) {
Node *t = nodeQueue.front();
nodeQueue.pop();
size_t d = EditDistance( t->m_item, center );
if( d <= k ) {
found++;
break;
}
Node *pChild = t->m_firstChild;
while( pChild ) {
if( d - k <= pChild->m_distToParent && pChild->m_distToParent <= d + k )
nodeQueue.push(pChild);
pChild = pChild->m_nextSibling;
}
}
return found;
}
void trim(std::string& input_str) {
if(input_str.empty()) return;
size_t startIndex = input_str.find_first_not_of(" ");
size_t endIndex = input_str.find_last_not_of("\r\n");
std::string temp_str = input_str;
input_str.erase();
input_str = temp_str.substr(startIndex, (endIndex - startIndex + 1) );
}
int BkTree::BuildDictionary() {
std::ifstream dictFile("/var/tmp/twl06.txt");
if ( dictFile.peek() == EOF ) {
return -1;
}
std::string line;
if (dictFile.is_open()) {
while (! dictFile.eof() ) {
std::getline (dictFile,line);
trim(line);
std::transform(line.begin(), line.end(), line.begin(), ::tolower);
insert(line);
}
dictFile.close();
} else {
return EXIT_FAILURE;
}
return 0;
}
void BkTree::solve() {
std::map<std::string, int> mapWordDistance;
std::vector<std::string>::iterator iter;
int totalDistance = 0;
for ( iter = wordVector.begin(); iter != wordVector.end(); ++iter ) {
int startDistance = 0;
while ( true ) {
std::map<std::string, int>::const_iterator itr;
itr = mapWordDistance.find(*iter);
if ( itr != mapWordDistance.end()) {
totalDistance += itr->second;
break;
} else {
int result = getWithinDistance( *iter, startDistance );
if ( result != 0 ) {
totalDistance += startDistance;
mapWordDistance.insert(std::make_pair(*iter, startDistance));
break;
}
}
startDistance++;
} // Infinite loop ends here
}
std::cout << totalDistance << std::endl;
}
int BkTree::ReadInputFile(const char *inpFileName) {
std::ifstream inputFile(inpFileName);
if ( inputFile.peek() == EOF ) {
return -1;
}
std::string line;
while (getline(inputFile, line, '\n')) {
std::istringstream iss(line);
std::copy( std::istream_iterator<std::string>(iss),
std::istream_iterator<std::string>(),
std::back_inserter<std::vector<std::string> >(wordVector));
}
inputFile.close();
//t2.stop();
return 0;
}
int main( int argc, char **argv ) {
if ( argc <= 1 ) {
return EXIT_FAILURE;
}
BkTree *pDict = new BkTree();
if ( pDict->BuildDictionary() != 0 ) {
delete pDict;
return 0;
}
if ( pDict->ReadInputFile(argv[1]) != 0 ) {
delete pDict;
return 0;
}
pDict->solve();
delete pDict;
return EXIT_SUCCESS;
}
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits>
struct Point {
double pt[2];
int id;
double distance;
};
typedef std::vector<Point> PointList;
typedef PointList::iterator PointListItr;
struct compareX {
bool operator ()(const Point& left, const Point& right) const {
return left.pt[0] < right.pt[0];
}
};
struct compareY {
bool operator ()(const Point& left, const Point& right) const {
return left.pt[1] < right.pt[1];
}
};
struct compareD {
bool operator ()(const Point& left, const Point& right) const {
return left.distance < right.distance;
}
};
struct kdNode {
Point point;
kdNode *left;
kdNode *right;
kdNode(PointListItr begin,
PointListItr end,int depth);
};
kdNode::kdNode( PointListItr begin,
PointListItr end,int depth = 0) {
left = right = 0;
if (begin == end) {
return ;
}
if( end - begin == 1) {
point = *begin;
return;
}
if(depth & 1)
std::sort( begin, end, compareY());
else
std::sort( begin, end, compareX());
PointList::size_type median = (end - begin) / 2;
point = *(begin + median );
if ( begin != ( begin + median ))
left = new kdNode(begin , begin + median , depth + 1);
if ( (begin + median + 1 ) != end )
right = new kdNode(begin + median + 1, end, depth + 1);
}
void readPoints(const char* fileName, PointList& points) {
std::ifstream input(fileName);
if ( input.peek() != EOF ) {
while(!input.eof()) {
int id = 0;
double x_cord, y_cord;
input >> id >> x_cord >> y_cord;
Point t ;
t.pt[0] = x_cord;
t.pt[1] = y_cord;
t.id = id;
points.push_back(t);
}
input.close();
}
}
double dist(Point &p1, Point &p2) {
double a = p1.pt[0] - p2.pt[0];
double b = p1.pt[1] - p2.pt[1];
return (a * a) + (b * b);
}
Point nearest(kdNode *node, Point &point, Point &min, int depth = 0) {
if ( node ) {
int axis = depth % 2;
double d = point.pt[axis] - min.pt[axis];
kdNode *near = d <= 0 ? node->left : node->right;
kdNode *far = d <= 0 ? node->right : node->left;
min = nearest(near, point, min, depth + 1);
if ((d * d) < dist(point, min)){
min = nearest(far, point, min, depth + 1);
}
if (dist(point,node->point) < dist(point, min)) {
min = node->point;
}
}
return min;
}
void nearest_k(kdNode *node, Point &point,
PointList &min,
double k_dist = std::numeric_limits<double>::max(),
int depth = 0) {
if ( node ) {
int axis = depth % 2;
double d = point.pt[axis] - node->point.pt[axis];
kdNode *near = d <= 0 ? node->left : node->right;
kdNode *far = d <= 0 ? node->right : node->left;
nearest_k(near, point, min, k_dist, depth+1);
if ( (d * d ) < k_dist ) {
nearest_k(far, point, min, k_dist, depth+1);
}
d = dist(point, node->point);
if ( d < k_dist) {
node->point.distance = d;
min.push_back(node->point);
}
std::sort(min.begin(), min.end(), compareD());
if ( min.size() > 3 ) {
for ( int i = 0; i < min.size() - 3; i++) {
min.erase(min.begin() + i );
}
}
k_dist = min[0].distance;
}
return;
}
void printLevelWise(kdNode *root) {
std::queue<kdNode*> Q;
Q.push(root);
while ( !Q.empty()) {
root = Q.front();
if( root->left) {
Q.push(root->left);
}
if ( root->right) {
Q.push(root->right);
}
Q.pop();
}
}
void printPoint(Point p) {
std::cout << "( " << p.pt[0] << "," << p.pt[1] << " )" << std::endl;
}
int main(int argc, char** argv ) {
if ( argc <= 1 ) {
return 0;
}
PointList locations;
readPoints(argv[1], locations);
if ( locations.size() == 0 )
return 0;
kdNode *pKdTree = new kdNode(locations.begin(), locations.end(),0);
printLevelWise(pKdTree);
Point t;
t.pt[0] = 6;
t.pt[1] = 5;
Point root = pKdTree->point;
Point p = nearest(pKdTree, t, root, 0);
PointList result;
for ( PointListItr itr = locations.begin(); itr != locations.end(); ++itr) {
nearest_k( pKdTree, *itr, result);
std::cout << (*itr).id << " " << result[0].id << "," << result[1].id << "," << result[2].id << std::endl;
}
delete pKdTree;
return 0;
}
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <cmath>
#include <stdlib.h>
typedef struct {
long start, finish, weight;
} Interval;
Interval *I;
long *M;
long *P;
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
int compare(const void * left, const void * right) {
return (((Interval *)left)->finish - ((Interval *) right)->finish);
}
int IntervalSearch(int start, int high){
if (high == -1) return -1;
int low = 0;
int best = -1;
int mid;
int finish;
while (low <= high) {
mid = (low + high) /2 ;
finish = I[mid].finish;
if (finish >= start) {
high = mid-1;
} else {
best = mid;
low = mid + 1;
}
}
return best;
}
long Compute_Opt(long j) {
if (j == 0)
return 0;
if (M[j] != -1l) {
return M[j];
}
M[j] = MAX(I[j].weight + Compute_Opt(P[j]), Compute_Opt(j - 1));
return M[j];
}
int main( int argc, char **argv) {
if ( argc <= 1 ) {
return 0;
}
std::ifstream dnaInput(argv[1]);
if ( dnaInput.peek() == EOF ) {
return 0;
}
int lenDnaStr;
dnaInput >> lenDnaStr ;
for(int index = 0; index <= std::ceil(((float)lenDnaStr)/80.0); index++) {
dnaInput.ignore( lenDnaStr + 1, '\n');
}
int numOfIv = 0;
dnaInput >> numOfIv;
if ( numOfIv == 0 ) {
return 0;
}
numOfIv = numOfIv + 1;
I = (Interval *) malloc (sizeof(Interval) * numOfIv);
M = (long *)malloc(sizeof(long) * numOfIv);
P = (long *)malloc(sizeof(long) * numOfIv);
Interval t;
t.start = 0;
t.finish = 0;
t.weight = 0;
I[0] = t;
for ( int index = 1; index < numOfIv; index++) {
int start = 0, finish = 0, weight = 0;
dnaInput >> start >> finish >> weight;
Interval t;
t.start = start;
t.finish = finish;
t.weight = weight;
I[index] = t;
}
dnaInput.close();
qsort(I, numOfIv, sizeof(Interval), compare);
int best;
for (int index = 1; index < numOfIv; index++){
M[index] = -1l;
best = IntervalSearch(I[index].start,index - 1);
if (best != -1) {
P[index] = best;
} else {
P[index] = 0;
}
}
long res = Compute_Opt(numOfIv - 1);
free ( P );
free ( I );
free ( M );
std::cout << res << std::endl;
}
Checkout the solution at avi-programming-blog.blogspot.com/2011/08/programming-challenge-ii-adding-spaces.html
- dongre.avinash August 03, 2011This problem can be solved using Trie datastructure. You can check the code in my blog.
Here is the code
#include <string>
#include <map>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
//#include "Timer.h"
typedef std::vector<size_t> RowType;
typedef RowType::iterator RowTypeItr;
typedef std::deque<std::string> ResultType;
typedef ResultType::iterator ResultTypeItr;
typedef std::string String;
typedef String::iterator StringItr;
struct TrieNode {
typedef std::map<char, TrieNode *> ChildType;
typedef ChildType::iterator ChildTypeItr;
String m_word;
ChildType m_childMap;
bool m_visited;
TrieNode() :m_childMap(std::map<char, TrieNode*>()), m_visited(false) {}
void insert( String& word ) {
TrieNode *pNode = this;
for ( StringItr itr = word.begin(); itr != word.end(); ++itr) {
char letter = *itr;
if ( pNode->m_childMap.find(letter) == pNode->m_childMap.end()){
pNode->m_childMap[letter] = new TrieNode();
}
pNode = pNode->m_childMap[letter];
}
pNode->m_word = word;
}
void search_r(TrieNode *pTrie, char letter, String& word, RowType& previousRow, ResultType &results, size_t maxCost ) {
size_t columns = word.size() + 1;
RowType currentRow;
currentRow.push_back(previousRow[0] + 1);
size_t prevcol = 0;
for (size_t column = 1; column < columns; column++) {
if ( word[prevcol] == letter )
currentRow.push_back(previousRow[prevcol]);
else {
size_t min_elem = 0, temp = 0;
temp = (currentRow[prevcol] < previousRow[column]) ? currentRow[prevcol]: previousRow[column];
min_elem = (previousRow[prevcol] < temp) ? previousRow[prevcol] : temp;
currentRow.push_back(min_elem + 1);
}
prevcol = column;
}
if (currentRow[currentRow.size() - 1 ] <= maxCost && pTrie->m_word != "" ) {
if ( ! pTrie->m_visited ) {
results.push_back(pTrie->m_word);
pTrie->m_visited = true;
}
}
if((*min_element(currentRow.begin(), currentRow.end())) <= maxCost) {
for ( ChildTypeItr itr = pTrie->m_childMap.begin(); itr != pTrie->m_childMap.end(); ++itr) {
search_r(itr->second, itr->first, word, currentRow, results, maxCost );
}
}
}
void search( String& word, size_t maxCost, ResultType &results ) {
RowType currentRow ( word.size() + 1 );
int i = 0;
for ( RowTypeItr itr = currentRow.begin(); itr != currentRow.end(); ++itr)
*itr = i++;
for ( ChildTypeItr itr = m_childMap.begin(); itr != m_childMap.end(); ++itr)
search_r(itr->second, itr->first, word, currentRow, results, maxCost );
}
};
int main(int argc, char **argv) {
//Timer t1("Time taken by Program : " );
TrieNode trie;
std::ifstream dictFile(argv[1]);
String line;
if (dictFile.is_open()) {
while (! dictFile.eof() ) {
std::getline (dictFile,line);
if ( line.size()) {
trie.insert(line);
}
}
dictFile.close();
}
String inputString(argv[2]);
String outputString("");
String tempWord;
for ( String::iterator itr = inputString.begin(); itr != inputString.end(); ++itr){
ResultType results;
tempWord.push_back(*itr);
trie.search(tempWord,0,results);
if ( results.size() == 0 ){
continue;
} else {
outputString += tempWord;
outputString += " ";
tempWord.clear();
}
results.clear();
}
outputString += tempWord;
std::cout << "Output : " << outputString << std::endl;
}
- dongre.avinash August 10, 2022