praveen pandit
BAN USERtypedef struct _node{
int data;
_node *left;
_node *right;
}node;
int getParent(int i){
if (i == 0) return i;
return (((i % 2) > 0) ? (i / 2) : ((i / 2) - 1));
}
node* getNode(node* root, int i){
if (i < 0) return NULL;
if (i == 0) return root;
queue<node*> q;
q.push(root);
while (1){
node *temp = q.front();
if (i == 0) return temp;
i--;
if (temp->left) q.push(temp->left);
if (temp->right) q.push(temp->right);
q.pop();
}
}
int findNode(node* root, int data){
if (root == NULL) return -1;
if (root->data == data) return 0;
queue<node*> q;
q.push(root);
int i = 0;
while (!q.empty()){
node *temp = q.front();
if (temp->data == data) return i;
if (temp->left) q.push(temp->left);
if (temp->right) q.push(temp->right);
q.pop(); i++;
}
return -1;
}
node* commonParent(node* root, int n1, int n2){
if (root == NULL) return root;
int p1 = getParent(findNode(root, n1));
int p2 = getParent(findNode(root, n2));
if (p1 < 0 || p2 < 0) return NULL;
while (p1 != p2){
if (p1 > p2) p1 = getParent(p1);
else p2 = getParent(p2);
}
return getNode(root,p1);
}
#include <stdio.h>
#define len(s) sizeof(s)/sizeof(s[0]) - 1
#define MAX(a,b) ((a) > (b)) ? (a) : (b)
void addBitStrings(char *op1, int op1_s, char *op2, int op2_s, int carry, char *result, int result_s){
if (result_s < 0) return;
int first = 0;
int second = 0;
if (op1_s >= 0)
first = op1[op1_s] - '0';
if (op2_s >= 0)
second = op2[op2_s] - '0';
result[result_s] = (first ^ second ^ carry) + '0';
carry = (first & second) | (second & carry) | (carry & first);
addBitStrings(op1, op1_s - 1, op2, op2_s - 1, carry, result, result_s - 1);
}
int main(){
char op1[] = "1100011";
char op2[] = "10";
char *result;
int max = MAX(len(op1), len(op2)) + 1;
result = (char*)calloc(sizeof(char)*max + 1, 1);
printf("%s", addBitStrings(op1, len(op1) - 1, op2, len(op2) - 1, 0, result, max - 1));
return 0;
}
#include <stdio.h>
void swap(char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}
bool isSimTogether(char *a, int size){
for (int i = 0; i < size; i++){
if (a[i] == a[i + 1])
return true;
}
return false;
}
void permute(char *a, int l, int r)
{
int i;
if (l == r && !isSimTogether(a,r)){
printf("%s\n", a);
}
else
{
for (i = l; i <= r; i++)
{
if (l == i) continue;
swap((a + l), (a + i));
permute(a, l + 1, r);
swap((a + l), (a + i));
}
}
}
int main()
{
char str[] = "AABC";
int n = sizeof(str) / sizeof(str[0]) - 1;
permute(str, 0, n - 1);
return 0;
}
ABCA
ACAB
BACA
If we implement this using Interval-Tree would have been more generic a solution.
#include <stdio.h>
typedef struct _Interval{
int low;
int high;
}interval;
bool doOverlap(interval i, interval j){
return (i.low <= j.high && j.low <= i.high) ? true: false;
}
void findAllOverlaps(interval *arr, interval j, int size, interval *ret, int *ii){
for (int i = 0; i < size; i++){
if (doOverlap(arr[i], j))
ret[(*ii)++] = arr[i];
}
}
int main(){
interval arr1[3] = { { 3, 11 }, { 17, 25 }, { 58, 73 } };
interval arr2[2] = { { 6, 18 }, { 40, 47 } };
int next = 0;
interval temp[3];
for (int jj = 0; jj < 2; jj++)
{
int j = 0;
findAllOverlaps(arr1, arr2[jj], 3, temp, &j);
next += j;
if (j > 0){
arr1[jj].low = temp[0].low;
arr1[jj].high = temp[j - 1].high;
}
else arr1[jj] = arr2[jj];
}
for (int jj = next; jj < SIZE; jj++)
arr1[jj] = arr1[jj];
for (int i = 0; i < SIZE; i++)
printf("%d-%d ",arr1[i].low, arr1[i].high);
return 0;
}
employee = {
"BILL" : ["DOM", "SAMIR","MICHAEL"],
"DOM" : ["BOB", "PETER", "PORTER"],
"PETER" : ["MILTON", "NINA"],
}
def dfs_path(graph, end, start = 'BILL', path=None):
if path is None:
path = [start]
if start == end:
yield path
for next in set(graph[start]) - set(path):
try:
for i in dfs_path(graph, end, next, path + [next]):
yield i
except KeyError:
continue
def closestCommonManager(name1,name2):
path_name1 = []
path_name2 = []
for name in dfs_path(employee,name1):
path_name1 += name
for name in dfs_path(employee,name2):
path_name2 += name
max_len = max(path_name1.__len__(),path_name2.__len__())
## print path_name1,path_name2,max_len
for i in range(max_len):
try:
if path_name1[i] != path_name2[i]:
break
except IndexError:
print path_name1[i - 1]
return
print path_name1[i -1]
closestCommonManager('MILTON','NINA') :: PETER
closestCommonManager('PORTER','NINA') :: DOM
closestCommonManager('SAMIR','NINA') :: BILL
closestCommonManager('PETER','NINA') :: PETER
it wasn't well tested..
please comment on below.
int arr[][2] = {
{ '{','}'},
{ '[',']'},
{ '(',')'}
/* Keep on adding new set of brackets*/
};
void getvalue(char ch, int *f, int *t){
if (ch == 0) return;
for (int i = *f + 1; i < sizeof(arr) / sizeof(arr[0]); i++){
if (ch == arr[i][0]){
*f = i;
*t = 0;
break;
}
if (ch == arr[i][1]){
*f = i;
*t = 1;
break;
}
}
}
bool fun1(char *str, stack<char> *s){
if (*str == 0){
if (s->empty()) return true;
else return false;
}
int f = 0;
int t = 0;
getvalue(*str, &f, &t);
if (t == 0) s->push(*str);
else{
if (s->empty()) return false;
else{
char ch = s->top();
int ff = 0;
int tt = 0;
getvalue(ch, &ff, &tt);
if (ff == f && tt == 0) {
s->pop();
return fun1(str + 1, s);
}
else return false;
}
}
return (true && fun1(str + 1, s));
}
void fun2(char *str){
int *arr = (int*)calloc(sizeof(int)*128,1);
}
int main(){
stack<char> s;
printf("%d",fun1("(({}[(){}]))",&s));
return 0;
}
void fun2(char *str){
int *arr = (int*)calloc(sizeof(int)* 128, 1);
while (*str)
arr[*str++]++;
for (int i = 0; i < 128; i++)
if (arr[i] != 0)
printf("(%c %d)\n", i, arr[i]);
}
#include <stdio.h>
int arr[][2] = {
{ '{','}'},
{ '[',']'},
{ '(',')'}
/* Keep on adding new set of brackets*/
};
void getvalue(char ch, int *f, int *t){
if (ch == 0) return;
for (int i = *f + 1; i < sizeof(arr) / sizeof(arr[0]); i++){
if (ch == arr[i][0]){
*f = i;
*t = 0;
break;
}
if (ch == arr[i][1]){
*f = i;
*t = 1;
break;
}
}
}
bool fun(char *str){
if (*str == 0) return true;
int f = -1;
int t = 0;
getvalue(*str, &f, &t);
if (f == -1) return true;
else if (t == 0) return (true && fun(str + 1));
else {
int ff = -1;
int tt = 0;
getvalue(*(str - 1), &ff, &tt);
if (ff == f && tt == 0) return true;
else return false;
}
}
int main(){
printf("%d",fun("([{exp[exp]})"));
return 0;
}
MainMatrixSize = MainMatrixSize - Pattern_size;
- praveen pandit March 08, 2016int fun(int *i, int *j){
for (int ii = 0; ii < Pattern_size; ii++){
for (int jj = 0; jj < Pattern_size; jj++){
if (arr[ii][jj] != arr_main[ii + *i][jj + *j]) return -1;
}
}
return 0;
}
int fun1(int *i, int *j, int MainMatrixSize){
for (*i = 0; *i < MainMatrixSize; (*i)++){
for (*j = 0; *j < MainMatrixSize; (*j)++){
if(fun(i, j) == 0) return 0;
}
}
return -1;
}
How about this
#include <stdio.h>
int arr[] = { 1, 1, 0, 0, 1, 1, 1, 0, 1, 1 };
int k = 1;
int fun(int arr[], int i, int size, int k){
if (size == i) return 0;
if (k < 0) return -1;
if (arr[i] == 1)
return (1 + fun(arr, i + 1, size, k));
if (arr[i] == 0)
return (1 + fun(arr, i + 1, size, k - 1));
}
int main(){
int size = sizeof(arr) / sizeof(arr[0]);
int sum = 0;
for (int i = 0; i < size; i++)
{
int count = fun(arr, i, size, k);
if(sum < count) sum = count;
}
printf("%d", sum);
return 0;
}
I guess based on above rule IDDI should be 34215
#include <stdio.h>
int fun(char *str, int dnum, int inum, int num, int *out, int mul){
if (*str == 0) return *out = *out + num;
*out = *out + num*mul;
if (*str == 'I'){
fun(str + 1, dnum, inum + 1, inum + 1, out, mul/10);
}
else if (*str == 'D'){
fun(str + 1, dnum - 1, inum, dnum - 1, out, mul/10);
}
return *out;
}
int main(){
char *str = "IDDI";
int dcount = 1;
int mul = 1;
int out = 0;
char *temp = str;
while (*temp++){
if (*temp == 'D') dcount++;
mul *= 10;
}
printf("%d", fun(str, dcount, dcount, dcount, &out, mul));
return 0;
}
inorderPath(root,NULL,1);
void inorderPath(tree *root, tree* prev, int flag){
if (root == NULL) return;
inorderPath(root->left, root, 1);
if (flag) root->random = prev;
else prev->random = root;
inorderPath(root->right, root, 0);
}
please let me know the if it will work for non empty tree.
inorderPath(root, root->left);
/*for non empty tree, has at least one node*/
tree* inorderPath(tree *root, tree* next){
if (root == NULL || next == NULL) return root;
next->random = inorderPath(root->left, next->left);
inorderPath(root->right, root);
return root;
}
this is the way I approach
typedef struct _co_ordinates{
int x;
int y;
} co_ordinates;
bool isValid(co_ordinates c, int size){
return (c.x >= 0 && c.x < size && c.y >= 0 && c.y < size) ? true : false;
}
co_ordinates left(co_ordinates c){
return { c.x - 1, c.y };
}
co_ordinates right(co_ordinates c){
return{ c.x + 1, c.y };
}
co_ordinates up(co_ordinates c){
return{ c.x, c.y - 1};
}
co_ordinates down(co_ordinates c){
return{ c.x, c.y + 1};
}
co_ordinates(*direction[4])(co_ordinates) = { up, right, down, left };
int countIsland(int** arr, int size){
int sum = 0;
for (int i = 0; i < size; i++){
for (int j = 0; j < size; j++){
if (arr[i][j] > 1) continue;
if (arr[i][j] == 0){
arr[i][j] = 2;
continue;
}
if (arr[i][j] == 1){
arr[i][j] = 3;
sum += countIslandUntil(arr, i, j, size);
}
}
}
return sum;
}
int countIslandUntil(int **arr, int x, int y, int size){
queue<co_ordinates> q;
co_ordinates c = { x, y };
q.push(c);
while (!q.empty()){
co_ordinates c = q.front();
q.pop();
int i = 4;
while (i){
co_ordinates temp = direction[--i](c);
if (isValid(temp,size) && arr[temp.x][temp.y] == 1){
arr[temp.x][temp.y] = 3;
q.push(temp);
}
}
}
return 1;
}
like below to find the nearest node in binary tree, similar could be done to get the nearest location between to point (x,y) in tree and (x1,y1) the point you are looking from. use some vector algebra.
tree* findNearestNumnew(tree* root, int num){
tree* cur = root;
tree* minnode = NULL;
int diff = INT_MAX;
while (cur != NULL){
if (diff > abs(cur->data - num)){
diff = abs(cur->data - num);
minnode = cur;
}
cur = (num < cur->data) ? cur->left : cur->right;
}
return minnode;
}
k-d binary tree are the suitable data structure to keep the geographical co-ordinates in k-dimensional plane. where k is 2,3.....n. for k=1 we have generic binary tree data structure.
- praveen pandit March 06, 2016k-d binary tree are the suitable data structure to keep the geographical co-ordinates in k-dimensional plane. where k is 2,3.....n. for k=1 we have generic binary tree data structure.
- praveen pandit March 06, 2016/* re-arrange the list of rope in sorted order
then get the cost of first two biggest rope joining
with the smallet rope from both the end.
so the cost will be
L1 + 2S1 + L2*/
int minCost(int *arr, int size){
int f = 0;
for (int s = 1, l = size - 1; arr[s] != INT_MIN; f++, s++, l--){
arr[s] = arr[f] + 2 * arr[l] + arr[s];
arr[l] = INT_MIN;
arr[f] = INT_MIN;
}
return arr[f];
}
input rope array :: 15 14 8 37 20
isorted rope passed to minCost() :: 37 20 15 14 8
minimum cost = 116
Not Much different from last
void smartModify(list *head, int m, int n){
if (head == NULL) return;
list *cur = head;
while (cur != NULL){
list *mnode = NULL;
list *nnode = NULL;
int mnum = m;
int nnum = n;
while (cur != NULL && mnum > 0){
if (--mnum == 0) mnode = cur;
cur = cur->next;
}
while (cur != NULL && nnum > 0){
if (--nnum == 0) nnode = cur;
cur = cur->next;
}
if (mnode)
mnode->next = (nnode == NULL) ? NULL : nnode->next;
}
}
how about this
void findNearestNode(tree* root, int num, tree *outNode, int *out){
if (root == NULL) return;
if (*out > abs(root->data - num)){
*out = abs(root->data - num);
outNode->data = root->data;
}
if (num < root->data)
findNearestNode(root->left, num, outNode, out);
else
findNearestNode(root->right, num, outNode, out);
}
int main(){
tree nd;
int out = INT_MAX;
findNearestNode(root, 34, &nd, &out);
return 0;
}
How about this, and thanks for the above suggestions.
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
int P[] = { 6, 11, 101, 15, 105, 110 };
void getElementsofS(int P[], int size) {
int *S = (int*)calloc(sizeof(int)*size, 1);
assert(S != NULL);
S[0] = (P[0] + P[1] - P[size - 1]) / 2;
printf("S = %d ", S[0]);
for (int i = 1; i < size; i++) {
printf("%d ",S[i] = P[i - 1] - S[0]);
}
}
int fact(unsigned int n){
if (n == 1) return 1;
return n * fact(n - 1);
}
int main(){
int i = 3;
int maxSize = (sizeof(P) / sizeof(P[0]));
for (; i < maxSize; i++){
if (fact(i - 1) == maxSize)
break;
}
if (i == maxSize){
printf("Array P is not of set Rule\n");
return 0;
}
getElementsofS(P, i);
return 0;
}
How about this solution
#include <stdio.h>
#include <stdlib.h>
typedef struct _tree
{
int data;
_tree *left;
_tree *right;
}tree;
#define SIZE 10
int l, r; // for simplicity get help of global variable
int arr[10] = { 6, 3, 4, 5, 1, 0, 9, 2, 8, 7 };
void getIndex(tree *root, int *left, int *right){
if (root == NULL) return;
if (l > left) l = left;
if (r < right) r = right;
getIndex(root->left, left - 1, right);
getIndex(root->right, left, right + 1);
}
void colDisp(tree* root, int col){
if (root == NULL) return;
if (col == 0) printf("%d ", root->data);
colDisp(root->left, col + 1);
colDisp(root->right, col - 1);
}
int main(int argc, char** argv){
tree *root = NULL;
/*assumed tree get prepared*/
//tree *root = prepBinaryTree(arr, SIZE);
getIndex(root, 0, 0);
printf("\n%d %d\n", l, r);
for (int i = l; i <= r; i++)
colDisp(root, i);
return 0;
}
outPut:: 9 5 3 2 6 1 7 4 8 0
- praveen pandit March 05, 2016recursive solution
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#define SIZE 10
int arr[SIZE] = { 42, 19, 41, 33, 39, 96, 19, 24, 38, 96 };
void reArrange(int *arr, int i, int size){
if (i == size) return;
int left = i % 2;
int right = left;
int mid = (left == 0) ? 1 : 0;
if (mid){
if (arr[i] > arr[i + 1]) swap(arr + i, arr + i + 1);
if (arr[i + 1] < arr[i + 2]) swap(arr + i + 1, arr + i + 2);
}
else{
if (arr[i] < arr[i + 1]) swap(arr + i, arr + i + 1);
if (arr[i + 1] > arr[i + 2]) swap(arr + i + 1, arr + i + 2);
}
reArrange(arr, i + 1, size);
}
void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
int main()
{
reArrange(arr, 0, SIZE);
return 0;
}
OutPut :: 19 42 33 41 39 96 19 38 24 96
- praveen pandit March 03, 2016how about this
int main(){
long total = 9 * 8 * 7 * 6;
long sum = total;
for (int i = 5; i > 0; i--){
total *= i;
sum += total;
}
printf("%ld",sum);
return 0;
}
how about this solution
#include <stdio.h>
#include <stdlib.h>
#define SIZE 6
int fib(int n, int arr[]){
if (n == 0 || n == 1){
arr[n] = n;
return n;
}
return arr[n] = (fib(n - 1, arr) + fib(n - 2, arr));
}
int main(){
int *arr = (int*)calloc(sizeof(int)* SIZE, 1);
fib(SIZE, arr);
for (int i = 0; i < SIZE; i++)
printf("%d ", arr[i]);
return 0;
}
void getMax(int arr[], int size, int x){
if (x + 2 >= size) return;
int temp;
printf("%d ", (temp = (arr[x] > arr[x + 1]) ? arr[x] : arr[x + 1]) > arr[x + 2] ? temp : arr[x + 2]);
getMax(arr, size, x + 1);
}
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <time.h>
typedef struct _list
{
int data;
_list *next;
} list;
int arr[11] = {78, 40, 25, 40, 17, 65, 3, 47, 54, 98, 23};
void preplist(list **head, int arr[], int size){
list **cur = head;
int i = size;
while (i){
list *temp = (list*)calloc(sizeof(list), 1);
assert(temp != NULL);
temp->data = arr[--i];
temp->next = *cur;
*cur = temp;
}
}
void displist(list* head){
printf("\nProduced List :: ");
while (head){
printf("%d->", head->data);
head = head->next;
}
printf("NULL");
}
void smartReverse(list **head){
if (*head == NULL || (*head)->next == NULL)
return;
list *first = *head;
list *second = first->next;
smartReverse(&(second->next));
first->next = second->next;
second->next = first;
*head = second;
}
int main(){
list *head = NULL;
preplist(&head, arr, SIZE);
displist(head);
smartReverse(&head);
displist(head);
getchar();
return 0;
}
OutPut
Produced List :: 78->40->25->40->17->65->3->47->54->98->23->NULL
Produced List :: 40->78->40->25->65->17->47->3->98->54->23->NULL
#include <iostream>
#include <stack>
using namespace std;
#define SIZE 6
bool topoSort(char vtx[], bool visited[], char edges[][SIZE], char start_vtx, stack<char> *s){
if (isExist(*s, start_vtx)){
printf(" There is a Cycle between %c and %c \n", start_vtx, s->top());
return false;
}
if (visited[start_vtx - 'A'] == false)
{
s->push(start_vtx);
visited[start_vtx - 'A'] = true;
if (edges[start_vtx - 'A'][0] != 0)
topoSort(vtx, visited, edges, edges[start_vtx - 'A'][0], s);
}
return true;
}
bool isExist(stack<char> s, char ch){
while (!s.empty()){
if (s.top() == ch)
return true;
s.pop();
}
return false;
}
/* Edges between*/
char vertices[SIZE] = { 'A', 'B', 'C', 'D', 'E', 'F' };
bool visited[SIZE] = { false, false, false, false, false };
/*Edges matrix for non-cyclic dependency*/
char edgeList[][SIZE] = {
/* A -> */{ 'B', 'C', 0, 0, 0, 0 },
/* B -> */{ 'C', 'D', 'E', 0, 0, 0 },
/* C -> */{ 'D', 'E', 0, 0, 0, 0 },
/* D -> */{ 'F', 0, 0, 0, 0, 0 },
/* E -> */{ 0, 0, 0, 0, 0, 0 },
/* F -> */{ 0, 0, 0, 0, 0, 0 }
};
/*Edges matrix for cyclic dependency*/
//char edgeList[][SIZE] = {
// /* A -> */{ 'B', 'C', 0, 0, 0, 0 },
// /* B -> */{ 'C', 'D', 'E', 0, 0, 0 },
// /* C -> */{ 'D', 'E', 0, 0, 0, 0 },
// /* D -> */{ 'F', 0, 0, 0, 0, 0 },
// /* E -> */{ 0, 0, 0, 0, 0, 0 },
// /* F -> */{ 'B', 0, 0, 0, 0, 0 }
//};
int main(){
stack<char> s;
for (int i = 0; i < SIZE; i++)
if (!visited[i] && topoSort(vertices, visited, edgeList, vertices[i], &s));
while (!s.empty()){
printf("%c ", s.top());
s.pop();
}
return 0;
}
#include <iostream>
#include <stack>
using namespace std;
#define SIZE 6
bool topoSort(char vtx[], bool visited[], char edges[][SIZE], char start_vtx, stack<char> *s){
if (isExist(*s, start_vtx)){
printf(" There is a Cycle between %c and %c \n", start_vtx, s->top());
return false;
}
if (visited[start_vtx - 'A'] == false)
{
s->push(start_vtx);
visited[start_vtx - 'A'] = true;
if (edges[start_vtx - 'A'][0] != 0)
topoSort(vtx, visited, edges, edges[start_vtx - 'A'][0], s);
}
return true;
}
bool isExist(stack<char> s, char ch){
while (!s.empty()){
if (s.top() == ch)
return true;
s.pop();
}
return false;
}
/* Edges between*/
char vertices[SIZE] = { 'A', 'B', 'C', 'D', 'E', 'F' };
bool visited[SIZE] = { false, false, false, false, false };
/*Edges matrix for non-cyclic dependency*/
char edgeList[][SIZE] = {
/* A -> */{ 'B', 'C', 0, 0, 0, 0 },
/* B -> */{ 'C', 'D', 'E', 0, 0, 0 },
/* C -> */{ 'D', 'E', 0, 0, 0, 0 },
/* D -> */{ 'F', 0, 0, 0, 0, 0 },
/* E -> */{ 0, 0, 0, 0, 0, 0 },
/* F -> */{ 0, 0, 0, 0, 0, 0 }
};
/*Edges matrix for cyclic dependency*/
//char edgeList[][SIZE] = {
// /* A -> */{ 'B', 'C', 0, 0, 0, 0 },
// /* B -> */{ 'C', 'D', 'E', 0, 0, 0 },
// /* C -> */{ 'D', 'E', 0, 0, 0, 0 },
// /* D -> */{ 'F', 0, 0, 0, 0, 0 },
// /* E -> */{ 0, 0, 0, 0, 0, 0 },
// /* F -> */{ 'B', 0, 0, 0, 0, 0 }
//};
int main(){
stack<char> s;
for (int i = 0; i < SIZE; i++)
if (!visited[i] && topoSort(vertices, visited, edgeList, vertices[i], &s));
while (!s.empty()){
printf("%c ", s.top());
s.pop();
}
return 0;
}
#include <stdio.h>
char dict[][5] = { "FOOL", "POOL", "POLL", "POLE", "PALE", "SALE", "SAGE",
"COLD", "CORD", "CARD", "WARD", "WARM" };
int diff(char* s1, char* s2, int length){
int num = 0;
for (int i = 0; i < length; i++)
if (s1[i] != s2[i])
num++;
return num;
}
void ladder_until(char dict[][5], int length, char* start, char* end, struct index *id){
for (int i = 0; i < length; i++){
if (!diff(start, dict[i], 4)) id->s = i;
if (!diff(end, dict[i], 4)) id->e = i;
}
}
int ladder(char dict[][5], int index, char* start, char* end){
if (!diff(start, end, 4)) return 0;
if (diff(start, dict[index], 4) == 1)
return (1 + ladder(dict, index, dict[index], end));
else
return ladder(dict, index + 1, dict[index], end);
}
int main(){
struct index id = { "FOOL", -1, "POOL", -1 };
ladder_until(dict, sizeof(dict)/sizeof(dict[0]), id.start, id.end, &id);
if (id.s != -1 || id.e != -1)
return 0;
if (id.s < id.e)
printf("%d \n", ladder(dict, id.s, id.start, id.end));
else
printf("%d \n", ladder(dict, id.e, id.end, id.start));
return 0;
}
#include <stdio.h>
char dict[][5] = { "FOOL", "POOL", "POLL", "POLE", "PALE", "SALE", "SAGE",
"COLD", "CORD", "CARD", "WARD", "WARM" };
int diff(char* s1, char* s2, int length){
int num = 0;
for (int i = 0; i < length; i++)
if (s1[i] != s2[i])
num++;
return num;
}
void ladder_until(char dict[][5], int length, char* start, char* end, struct index *id){
for (int i = 0; i < length; i++){
if (!diff(start, dict[i], 4)) id->s = i;
if (!diff(end, dict[i], 4)) id->e = i;
}
}
int ladder(char dict[][5], int index, char* start, char* end){
if (!diff(start, end, 4)) return 0;
if (diff(start, dict[index], 4) == 1)
return (1 + ladder(dict, index, dict[index], end));
else
return ladder(dict, index + 1, dict[index], end);
}
int main(){
struct index id = { "FOOL", -1, "POOL", -1 };
ladder_until(dict, sizeof(dict)/sizeof(dict[0]), id.start, id.end, &id);
if (id.s != -1 || id.e != -1)
return 0;
if (id.s < id.e)
printf("%d \n", ladder(dict, id.s, id.start, id.end));
else
printf("%d \n", ladder(dict, id.e, id.end, id.start));
return 0;
}
if any issue with this please let us know
- praveen pandit March 14, 2016