From 098415483c31f06faa04200c08a7112c28c6c0ec Mon Sep 17 00:00:00 2001
From: Aditya Naik
Date: Fri, 1 Mar 2019 06:03:21 -0500
Subject: 429 AC

---
 429/in       | 72 ++++++++----------------------------------------------------
 429/in2      |  7 ------
 429/word.c   | 25 ---------------------
 429/word.cpp | 52 ++++++++++++++++++++++++++++---------------
 429/word.in  | 67 -------------------------------------------------------
 log.org      | 11 ++++++----
 6 files changed, 50 insertions(+), 184 deletions(-)
 delete mode 100644 429/in2
 delete mode 100644 429/word.c
 delete mode 100644 429/word.in

diff --git a/429/in b/429/in
index b79b8e8..7f0c46c 100644
--- a/429/in
+++ b/429/in
@@ -1,67 +1,13 @@
-4
+2
 
-dip
-lip
-mad
-map
-maple
-may
-pad
-pip
-pod
-pop
-sap
-sip
-slice
-slick
-spice
-stick
-stock
+aa
+bb
+ac
 *
-spice stock
-may pod
+aa ac
 
-dip
-lip
-mad
-map
-mapl
-maple
-may
-pad
-pip
-pod
-pop
-sap
-sip
-slice
-slick
-spice
-stick
-stock
+aa
+ab
+bb
 *
-spice slick
-may mad
-map maple
-maple map
-map map
-
-mapl
-maple
-mba
-mbal
-mbale
-mbple
-*
-mba mapl
-
-map
-mapl
-maple
-mba
-mbal
-mbale
-mbp
-mbple
-*
-mba mapl
+aa bb
diff --git a/429/in2 b/429/in2
deleted file mode 100644
index 8adc3ce..0000000
--- a/429/in2
+++ /dev/null
@@ -1,7 +0,0 @@
-1
-
-pip
-slkdj
-sdwi
-sdkj
-*
\ No newline at end of file
diff --git a/429/word.c b/429/word.c
deleted file mode 100644
index f8363aa..0000000
--- a/429/word.c
+++ /dev/null
@@ -1,25 +0,0 @@
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-int main(){
-    int tc;
-    char *word = malloc(10);
-    size_t st = 10;
-    scanf("%d", &tc);
-    while(tc--){
-	getline(&word, &st, stdin); /* blank line after tc number */
-	char dict[200][10];
-	int i = 0;
-	
-	getline(&word, &st, stdin);
-	while(word[0]!='*'){
-	    memcpy(dict[i++], word, st);
-	    getline(&word, &st, stdin);
-	}
-	int j=0;
-	for(;j<i; j++){
-	    printf("%s", dict[j]);
-	}
-    }
-}
diff --git a/429/word.cpp b/429/word.cpp
index 6685b17..066b59c 100644
--- a/429/word.cpp
+++ b/429/word.cpp
@@ -5,8 +5,8 @@
 #include <sstream>
 using namespace std;
 
-int get_dist(string a, string b);
-void make_graph(vector<string> wlist, int map[][200]);
+void makeGraph(vector<string> wlist, int map[][200]);
+int getDist(string a, string b);
 int bfs(int map[][200], int start, int dest, int s);
 
 int main(){
@@ -15,31 +15,36 @@ int main(){
     while(tc--){
 	string w="";
 	vector<string> wlist;
-	int map[200][200];
+	int map[200][200] = {0};
+	cin>>w;
 	while(w!="*"){
-	    cin>>w;
 	    wlist.push_back(w);
+	    cin>>w;
 	}
-	make_graph(wlist, map);
+	makeGraph(wlist, map);
 	cin.ignore();
 	
 	string line, s1, s2;
 	getline(cin, line);
 	while(line!=""){
-	    int l1, l2;
+	    int l1, l2; /* indices to words in map */
 	    istringstream iss(line);
 	    iss>>s1>>s2;
 
 	    for(int i=0; i<wlist.size(); i++){
 		if(wlist[i]==s1)
 		    l1 = i;
-		else if(wlist[i]==s2)
+		if(wlist[i]==s2)
 		    l2 = i;
 	    }
-	    
-	    cout<<s1<<" "<<s2<<" "<<bfs(map, l1, l2, wlist.size())<<"\n";
+	    int dist;
+
+	    dist = bfs(map, l1, l2, wlist.size());
+	    cout<<s1<<" "<<s2<<" "<<dist<<"\n";
 	    getline(cin, line);	    
 	}
+	if(tc>0)
+	    cout<<endl;
     }
 }
 
@@ -58,7 +63,7 @@ while !q.empty
 int bfs(int map[][200], int start, int dest, int s){
     queue<int> q;
     int pred[200], n;
-    bool visited[200] = {false};
+    bool visited[200] = {false};    
     
     q.push(start);
     while(!q.empty()){
@@ -81,21 +86,32 @@ int bfs(int map[][200], int start, int dest, int s){
     return len;
 }
 
-void make_graph(vector<string> wlist, int map[][200]){
+void makeGraph(vector<string> wlist, int map[][200]){    
     for(int i=0; i<wlist.size(); i++)
 	for(int j=0; j<wlist.size(); j++)
-	    if(i!=j && get_dist(wlist[i], wlist[j])==1){
+	    if(i!=j && getDist(wlist[i], wlist[j])==1){
 		map[i][j] = 1;
 		map[j][i] = 1;
 	    }
 }
 
-int get_dist(string a, string b){
+int getDist(string a, string b){
     int dist = 0;
-    int len = a.length();    
-    if(len == b.length())
-	for(int i=0; i<len; i++)
-	    if(a[i]!=b[i])
-		dist++;
+    string longer, shorter;
+
+    if(a.length() > b.length()){
+	longer = a;
+	shorter = b;
+    }
+    else{ /* Also accounts for equal length */
+	longer = b;
+	shorter = a;
+    }
+    dist += longer.length() - shorter.length();
+    
+    for(int i=0; i<shorter.length(); i++)
+	if(shorter[i]!=longer[i])
+	    dist+=1;
+
     return dist;
 }
diff --git a/429/word.in b/429/word.in
deleted file mode 100644
index b79b8e8..0000000
--- a/429/word.in
+++ /dev/null
@@ -1,67 +0,0 @@
-4
-
-dip
-lip
-mad
-map
-maple
-may
-pad
-pip
-pod
-pop
-sap
-sip
-slice
-slick
-spice
-stick
-stock
-*
-spice stock
-may pod
-
-dip
-lip
-mad
-map
-mapl
-maple
-may
-pad
-pip
-pod
-pop
-sap
-sip
-slice
-slick
-spice
-stick
-stock
-*
-spice slick
-may mad
-map maple
-maple map
-map map
-
-mapl
-maple
-mba
-mbal
-mbale
-mbple
-*
-mba mapl
-
-map
-mapl
-maple
-mba
-mbal
-mbale
-mbp
-mbple
-*
-mba mapl
diff --git a/log.org b/log.org
index fd24b6a..eacb8f5 100644
--- a/log.org
+++ b/log.org
@@ -3,9 +3,12 @@
 
 * DONE 146
 - Supposed to be solved with cpp stl, perhaps a c implementation of next_permutation will be more exciting?
-* UNFINISHED 429
+* WORKING 429
 - Word transformation: looks like a graph problem
+  - Appears under 'easy BFS' 
 - Needs to be revisited
-* WORKING 12532
-- On uhunt this problem is put under a 'tree-related structures', but not sure how a tree might be useful in this case
-  - Attempting a (naive) linear array first to see if it works (half expecting it to fail on time limit)
+* UNFINISHED 12532
+- On uhunt this problem is put under 'tree-related structures', but not sure how a tree might be useful in this case
+  - A segment tree perhaps?
+- Attempting a (naive) linear array first to see if it works (half expecting it to fail on time limit)
+  - Failed on TLE
-- 
cgit v1.2.3