We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Algorithms
- Recursion
- Crossword Puzzle
- Discussions
Crossword Puzzle
Crossword Puzzle
+ 0 comments my solution with c++
#include <bits/stdc++.h> using namespace std; #define speed std::ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define sz size() #define pb push_back #define all(v) v.begin(),v.end() #define sm(v) accumulate(all(v),0ll) #define cin(v) for(auto &i : v) cin>>i vector<string>g(10),words; vector<int>vis(10); bool done=0; void solve(int i ){ if(sm(vis)==words.sz && !done) {done=1;for(auto a:g) cout<<a<<"\n";} if(i==10) return ; for(int j=0;j<10;j++){ if(g[i][j]=='+') continue; for(int k=0;k<words.sz;k++){ if(vis[k]) continue; vis[k]=1; vector<int>added;int c=0; for(int m=0;m<words[k].sz;m++) { int ind=m+j; if(ind>=10 || g[i][ind] =='+') break; if(g[i][ind] =='-') g[i][ind]=words[k][m],added.pb(ind); else if(g[i][ind]!=words[k][m]) break; else c++; } if(added.sz+c==words[k].sz) solve(i); for(auto ind:added) { g[i][ind]='-'; } added.clear();c=0; for(int m=0;m<words[k].sz;m++) { int ind=m+i; if(ind>=10 || g[ind][j] =='+') break; if(g[ind][j] =='-') g[ind][j]=words[k][m],added.pb(ind); else if(g[ind][j]!=words[k][m]) break; else c++; } if(added.sz+c==words[k].sz) solve(i); for(auto ind:added) { g[ind][j]='-'; } vis[k]=0; } } solve(i+1); } void runCase(){ cin(g); string s,x;cin>>s; for(auto a:s){ if(a==';') {words.pb(x);x="";} else x+=a; } words.pb(x); solve(0); } int main(){speed; runCase(); }
+ 0 comments Easy recursive alg
def insert_horizontal_candidate(horiz, tmp, w): for j in range(10): new_s += horiz[tmp[-1]+1:] return new_s def insert_vertical_candidate(vertic, tmp, w, j): new_s = '' for i in range(10): if i in tmp: if new_s.find(w) != -1: continue new_s += w else: new_s += vertic[i][j] return new_s def crosswordPuzzle(crossword, words): if type(words) != list and words.find(';') > 0: words = words.split(';') if len(words) == 0:#if empty candidates word return crossword return crossword for i in range(10):#try insert first horizontal candidates horiz = crossword[i] if horiz.find('-') != -1: index_of_possible_fields = [] for j in range(10): if horiz[j] != '+': index_of_possible_fields.append(j) if len(index_of_possible_fields) > 0 and (horiz[j] == '+' or j == 9): mask = ''.join([horiz[j2] for j2 in index_of_possible_fields]) for word in words: if len(word) == len(mask): can_use = 0 for j3 in range(len(word)): if (mask[j3] == '-') or (mask[j3] != '-' and word[j3] == mask[j3]): can_use += 1 if can_use == len(word): crossword2 = crossword.copy() crossword2[i] = insert_horizontal_candidate(crossword2[i], index_of_possible_fields, word) new_words = [w2 for w2 in words if w2 != word] tmp_cross = crosswordPuzzle(crossword2, new_words) success = True for c in tmp_cross: if c.find('-') != -1: success = False if success:#if returned crossword don't have empty spaces return tmp_cross index_of_possible_fields = [] for j in range(10):#then try insert vertical candidates(at this moment crossword will be without empty horizontal) vertic = ''.join([crossword[i][j] for i in range(10)]) if vertic.find('-') != -1: index_of_possible_fields = [] for i in range(10): if vertic[i] != '+': index_of_possible_fields.append(i) if len(index_of_possible_fields) > 0 and (vertic[i] == '+' or i == 9 ): mask = ''.join([vertic[i2] for i2 in index_of_possible_fields]) for word in words: if len(word) == len(mask): can_use = 0 for j3 in range(len(word)): if (mask[j3] == '-') or (mask[j3] != '-' and word[j3] == mask[j3]): can_use += 1 if can_use == len(word): crossword2 = crossword.copy() new_s = insert_vertical_candidate(crossword2, index_of_possible_fields, word, j) for i2 in range(10): crossword2[i2] = crossword2[i2][:j] + new_s[i2] + crossword2[i2][j+1:] new_words = [w2 for w2 in words if w2 != word] tmp_cross = crosswordPuzzle(crossword2, new_words) success = True for c in tmp_cross: if c.find('-') != -1: success = False if success:#if returned crossword don't have empty spaces return tmp_cross index_of_possible_fields = [] return crossword
+ 0 comments Why this is not working?
void removeH(vector<string>&crossword, int i, int j, vector<bool>& wePlaced) { for(int k=0;k<wePlaced.size();k++) { if(wePlaced[k]) crossword[i][j+k]='-'; } } void removeV(vector<string>&crossword, int i, int j, vector<bool>& wePlaced) { for(int k=0;k<wePlaced.size();k++) { if(wePlaced[k]) crossword[i+k][j]='-'; } } vector<bool> placeH(vector<string>&crossword, string currWord, int i, int j) { vector<bool> res; for(int k=0;k<currWord.length();k++) { if(crossword[i][j+k]=='-') { res.push_back(true); crossword[i][j+k] = currWord[k]; } else res.push_back(false); } return res; } vector<bool> placeV(vector<string>&crossword, string currWord, int i, int j) { vector<bool> res; for(int k=0;k<currWord.length();k++) { if(crossword[i+k][j]=='-') { res.push_back(true); crossword[i+k][j] = currWord[k]; } else res.push_back(false); } return res; } bool canPlaceH(vector<string>&crossword, string currWord, int i, int j) { int len = currWord.length(); for(int x=0;x<len;x++) { if(x+j>=crossword.size()) return false; if(crossword[i][x+j]=='-' || crossword[i][x+j]==currWord[x]) continue; else return false; } return true; } bool canPlaceV(vector<string>&crossword, string currWord, int i, int j) { int len = currWord.length(); for(int x=0;x<len;x++) { if(x+i>=crossword.size()) return false; if(crossword[x+i][j]=='-' || crossword[x+i][j]==currWord[x]) continue; else return false; } return true; } void solve(int indX, vector<string>&crossword, vector<string>words) { if(indX==words.size()) return; string currWord = words[indX]; for(int i=0;i<crossword.size();i++) { for(int j=0;j<crossword.size();j++) { if(crossword[i][j]== '-' || crossword[i][j]==currWord[0]) { if(canPlaceH(crossword,currWord,i,j)) { vector<bool> wePlaced = placeH(crossword,currWord,i,j); solve(indX+1,crossword,words); removeH(crossword,i,j, wePlaced); } if(canPlaceV(crossword, currWord, i, j)) { vector<bool> wePlaced = placeV(crossword, currWord, i, j); solve(indX+1,crossword,words); removeV(crossword, i, j, wePlaced); } } } } } vector<string> crosswordPuzzle(vector<string>& crossword, string words) { vector<string>word; stringstream ss(words); while(ss.good()) { string substr; getline(ss, substr, ';'); word.push_back(substr); } solve(0, crossword, word); return crossword; }
+ 0 comments Here is Crossword Puzzle problem solution in Python Java C++ and c programming - https://programs.programmingoneonone.com/2021/03/hackerrank-crossword-puzzle-solution.html
+ 0 comments Clean Java Code for better understanding
static List<String> ans; public static List<String> crosswordPuzzle(List<String> crossword, String words) { // Write your code here ans=new ArrayList<>(); char[][] croswrd=new char[10][10]; int i=0; for(String s:crossword){ int j=0; for(char ch:s.toCharArray()){ croswrd[i][j]=ch; j++; } i++; } helper(croswrd,words.split(";"),0); return ans; } public static void helper(char[][] c,String[] words,int vidx){ if(vidx==words.length){ List<String> temp=new ArrayList<>(); for(char[] str:c){ String s=""; for(char ch:str){ s+=ch; } temp.add(s); } ans=temp; return; } String word=words[vidx]; for (int i = 0; i <= 9; i++) { for(int j = 0; j <= 9; j++){ if(canPlaceHori(c,word,i,j)){ boolean[][] vis=placeHori(c,word,i,j); helper(c,words,vidx+1); unplaceHori(c,word,vis,i,j); } if(canPlaceVert(c,word,i,j)){ boolean[][] vis=placeVert(c,word,i,j); helper(c,words,vidx+1); unplaceVert(c,word,vis,i,j); } // print(c); // System.out.println(); } } } public static void unplaceHori(char[][] c,String word,boolean[][] vis,int i,int j){ for(int k=0;k<word.length();k++){ if(vis[i][j+k]==true){ c[i][j+k]='-'; vis[i][j+k]=false; } } } public static void unplaceVert(char[][] c,String word,boolean[][] vis,int i,int j){ for(int k=0;k<word.length();k++){ if(vis[i+k][j]==true){ c[i+k][j]='-'; vis[i+k][j]=false; } } } public static boolean[][] placeHori(char[][] c,String word,int i,int j){ boolean[][] res=new boolean[10][10]; for(int k=0;k<word.length();k++){ if(j+k<10 && (c[i][j+k]=='-')){ c[i][j+k]=word.charAt(k); res[i][j+k]=true; } } return res; } public static boolean[][] placeVert(char[][] c,String word,int i,int j){ boolean[][] res=new boolean[10][10]; for(int k=0;k<word.length();k++){ if(i+k<10 && (c[i+k][j]=='-')){ c[i+k][j]=word.charAt(k); res[i+k][j]=true; } } return res; } public static boolean canPlaceHori(char[][] c,String word,int i,int j){ for(int k=0;k<word.length();k++){ if(j+k<10 && (c[i][j+k]=='-' || c[i][j+k]==word.charAt(k))){ }else{ return false; } } return true; } public static boolean canPlaceVert(char[][] c,String word,int i,int j){ for(int k=0;k<word.length();k++){ if(i+k<10 && (c[i+k][j]=='-' || c[i+k][j]==word.charAt(k))){ }else{ return false; } } return true; } public static void print(char[][] c){ for(char[] cc:c){ for(char ccc:cc){ System.out.print(ccc); } System.out.println(); } } }
Load more conversations
Sort 191 Discussions, By:
Please Login in order to post a comment