karabouzouk... Δημοσ. 30 Απριλίου 2010 Δημοσ. 30 Απριλίου 2010 Προσπαθώ να φτιάξω ένα προγραμματάκι που δίνοντας σαν είσοδο κάποια γράμματα να βρίσκει σε ένα αρχείο ποιες λέξεις είναι δυνατόν να σχηματιστούν με αυτά τα γράμματα χρησιμοποιώντας το καθένα μόνο μια φορά.. Το γνωστό παιχνίδι του αναγραμματισμού δλδ... Επειδή έχω θολώσει λίγο όποιος μπορεί να βρει τι λάθος κάνω και δεν δουλευει σωστά θα του είμαι υπόχρεος.. >#include<iostream> #include <fstream> #include<string> using namespace std; bool is_anagram(string, string); int main() { int i, w1sz, w2sz, freqtbl[26], flag; ifstream fd; string cur_word, test_word, res[200]; fd.open("greek word list.txt"); if (!fd.is_open()) { printf("Error opening files....\n\n"); getchar(); return 1; } cout << "\n\nDwse Grammatoseira...: "; cin >> test_word; w1sz = test_word.length(); while (1) { flag = 0; cur_word = ""; fd >> cur_word; if (fd.eof()) break; w2sz = cur_word.length(); /* Sanity check */ if (w1sz < w2sz){ continue; } /* Initialize the histogram */ //bzero(freqtbl, 26 * sizeof (int)); for (i = 0; i < 26; i++) { freqtbl[i] = 0; } /* Read the first string, incrementing the corresponding histogram entry */ for (i = 0; i < w1sz; i++) { if (cur_word[i] >= 'A' && cur_word[i] <= 'Z') freqtbl[cur_word[i] - 'A']++; else if (cur_word[i] >= 'a' && cur_word[i] <= 'z') freqtbl[cur_word[i] - 'a']++; } /* Read the second string, decrementing the corresponding histogram entry */ for (i = 0; i < w2sz; i++) { if (test_word[i] >= 'A' && test_word[i] <= 'Z') { if (freqtbl[test_word[i] - 'A'] == 0) { flag = 1; break; } freqtbl[test_word[i] - 'A']--; } else if (test_word[i] >= 'a' && test_word[i] <= 'z') { if (freqtbl[test_word[i] - 'a'] == 0) { flag = 1; break; } freqtbl[test_word[i] - 'a']--; } } if (flag == 0) { cout << cur_word << endl; } } fd.close(); return (0); } Βάζω και ένα αρχείο με τις ελληνικές λέξεις με λίγο αλαγμένα γράμματα για να μην έχει αριθμούς που δε βολεύουν για τις δοκιμές.. Αν δεν σας βολεύει υπάρχουν πολλά word list με αγγλικές λέξεις για να δοκιμάσετε.. greek word list.zip
Directx Δημοσ. 30 Απριλίου 2010 Δημοσ. 30 Απριλίου 2010 Θα μπορούσες να το κάνεις ως εξής, διατηρείς σε ένα buffer το string του αναγραμματισμού σου (πχ. szMatch), αποθηκεύεις σε ένα δεύτερο buffer την κάθε πιθανή προς έλεγχο λέξη (πχ. szWord), ελέγχεις αν τα δυο buffer έχουν ίσο αριθμό χαρακτήρων ώστε να αποκλίσεις ελέγχους για εξόφθαλμα διαφορετικές λέξεις (αλφαριθμητικά ποίο σωστά) και ύστερα αρχίζεις να αντικαθιστάς με κενά (spc) κάθε χαρακτήρα που υπάρχει από το πρώτο buffer (szWord) στο δεύτερο (szMatch). Αν στο τέλος όλοι οι χαρακτήρες του δεύτερου buffer (szMatch) είναι κενά (συγκρίνεις μεταξύ szSpc -όπου έχει ίσα με szWord length κενά- και szMatch) τότε πιθανόν να πρόκειται για αναγραμματισμό του πρώτου buffer (szWord) οπότε το εκτυπώνεις στο STDOUT. Ακολουθεί ένα μικρό πρόγραμμα που εφαρμόζει την παραπάνω λογική: > /* * Anagram solver (dictionary based & case sensitive) by directx. * * Usage: dictionary-file anagram */ #include <stdio.h> #include <string.h> int main(int argc, char *argv[]) { char szWord[bUFSIZ]; FILE *fStream = NULL; /* Args check. */ if(argc != 3) { fprintf(stderr, "Usage: dictionary-file anagram\n"); return 1; } /* Open dictionary file for read. */ if((fStream = fopen(argv[1], "rt")) == NULL) { fprintf(stderr, "Cannot open file - %s\n", argv[1]); return 1; } else { /* Process each word. */ while(fscanf(fStream, "%s", szWord) != EOF) { char szMatch[bUFSIZ], szSpc[bUFSIZ]; char *ptrPos = NULL; /* Match word and anagram length. */ if(strlen(szWord) != strlen(argv[2])) continue; /* Does not match! */ /* Prepare check buffer (spc length should be equal to szWord length). */ memset(szSpc, ' ', sizeof(char) * strlen(szWord)); /* Duplicate argv[2] to szMatch. */ strcpy(szMatch, argv[2]); /* Eliminate each of the same character among szWord and szMatch. */ for(int MasterIdx = 0; MasterIdx < strlen(szWord); MasterIdx++) if((ptrPos = (char*)memchr(&szMatch, szWord[MasterIdx], sizeof(char) * strlen(szMatch))) != NULL) szMatch[ptrPos - szMatch] = ' '; /* Match the result of szMatch to szSpc whitespaced buffer. */ if(!memcmp(szMatch, szSpc, strlen(szWord))) printf("->%s\n", szWord); /* We have a possible match! */ } /* Free local resources. */ fclose(fStream); } printf("\nPress Enter to exit.."); getchar(); return 0; } ΕΙΣΟΔΟΣ > list.txt jteena ΕΞΟΔΟΣ > ->janete ->anteje Το πρόγραμμα έχει δοκιμασθεί σε CodeGear C++ Builder 2009 με βάση το λεξικό σου και ένα πολύ μικρό αριθμό αναγραμματισμών συνεπώς μπορεί να περιέχει bugs ή άλλες αβλεψίες. Καλή τύχη!
chigal Δημοσ. 30 Απριλίου 2010 Δημοσ. 30 Απριλίου 2010 > /* Sanity check */ if (w1sz < w2sz){ continue; } Εδώ γιατί ελέγχεις για μικρότερο και όχι για διάφορο? Αν έχουν διαφορετικό μήκος, τότε δε μπορεί το ένα να είναι anagram του άλλου. Παρ' όλα αυτά το δεύτερο loop θα σου βγάλει partial αποτελέσματα αν η λέξη από το αρχείο είναι anagram ενός κομματιού της λέξης που δίνει ο χρήστης. Αν κατάλαβα καλά, αυτό δεν το θες.
Acid_raiN Δημοσ. 30 Απριλίου 2010 Δημοσ. 30 Απριλίου 2010 Έχω φτιάξει μια παρόμοια εφαρμογή για το iPhone. Στην αρχή χρησιμοποίησα μία λύση παρόμοια με του DirectX, όμως επειδή το iPhone δεν είναι desktop PC αργούσε πολύ να βρει τους αναγραμματισμούς. Η λύση που τελικά προτίμησα ήταν να αλλάξω τη λίστα με τις λέξεις. Η λίστα έχει δύο στήλες, μία με την λέξη και μία με τα γράμματα της λέξης σε αλφαβητική σειρά. πχ ΑΡΗΣ ΑΗΡΣ. Όταν ο χρήστης έδινε τα γράμματα τα κάνω sort αλφαβητικά και ψάχνω τη δεύτερη στήλη της λίστας. Έτσι το πρόβλημα απλοποιείται αρκετά. Στη δική μου υλοποίηση όμως χρησιμοποιώ sqlite για την αποθήκευση και σάρωση της λίστας για λόγους ταχύτητας.
karabouzouk... Δημοσ. 30 Απριλίου 2010 Μέλος Δημοσ. 30 Απριλίου 2010 Ακολουθεί ένα μικρό πρόγραμμα που εφαρμόζει την παραπάνω λογική: Όντως απ όσο είδα και γω δουλεύει μιά χαρά αλλά πώς μπορώ να το κάνω να βρήσκει και λέξεις που έχουν λιγότερα γράμματα από τη συμβολοσειρά που δείνω σαν είσοδο γιατί δεν τα κατάφερα..? > /* Sanity check */ if (w1sz < w2sz){ continue; } Εδώ γιατί ελέγχεις για μικρότερο και όχι για διάφορο? Ναι συγγνώμη δεν το έκανα κατά λάθος αυτό απλά με ενδιαφέρουν και οι λέξεις με λιγότερα γράμματα από την γραμματοσειρά μου.. ετσι δεν πρέπει να το κάνω για να τις συμπεριλάβω και αυτές..? Έχω φτιάξει μια παρόμοια εφαρμογή για το iPhone. Στην αρχή χρησιμοποίησα μία λύση παρόμοια με του DirectX, όμως επειδή το iPhone δεν είναι desktop PC αργούσε πολύ να βρει τους αναγραμματισμούς. Η λύση που τελικά προτίμησα ήταν να αλλάξω τη λίστα με τις λέξεις. Η λίστα έχει δύο στήλες, μία με την λέξη και μία με τα γράμματα της λέξης σε αλφαβητική σειρά. πχ ΑΡΗΣ ΑΗΡΣ. Όταν ο χρήστης έδινε τα γράμματα τα κάνω sort αλφαβητικά και ψάχνω τη δεύτερη στήλη της λίστας. Έτσι το πρόβλημα απλοποιείται αρκετά. Στη δική μου υλοποίηση όμως χρησιμοποιώ sqlite για την αποθήκευση και σάρωση της λίστας για λόγους ταχύτητας. Καλή τεχνική αν αντιμετοπίζεις πρόβλημα με ταχύτητα.. όντως κερδίζεις αρκετούς υπολογισμούς έτσι.. στη δική μου λύση ακόμα να βρώ το λάθος μου.. μου βγάζει και κάποιες άσχετες λέξεις και γράμματα μερικές φορές σαν αποτελέσματα.. κάτι πατάτα πρέπει να έχω κάνει με τα continue ή με τους δείκτες στις γραμματοσειρές... όποιος μπορεί ας ρίξει μια ματιά μήπως βρει κάτι..
chigal Δημοσ. 30 Απριλίου 2010 Δημοσ. 30 Απριλίου 2010 cancel that - νομίζω μπερδεύτηκα με τα ονόματα των μεταβλητών ... EDIT: ΑΑΑ! Ένα pet peeve μου είναι τα μη περιγραφικά ονόματα μεταβλητών. Επειδή λοιπόν μπερδευόμουν έκανα ένα search&replace στον αρχικό κώδικα και μετά παρατήρησα το παρακάτω: > /* Read the first string, incrementing the corresponding histogram entry */ for (i = 0; i < input_word.length(); i++) { if (word_to_check[i] >= 'A' && word_to_check[i] <= 'Z') Το loop επαναλαμβάνεται με βάση το μήκος του input_word (που έδωσε ο χρήστης), αλλά ελέγχει τα περιεχόμενα του word_to_check (αυτό που ελέγχει από το αρχείο)
morgankalamos Δημοσ. 30 Απριλίου 2010 Δημοσ. 30 Απριλίου 2010 Ειναι για το hellenico? Όχι δεν είναι γι αυτό... απλά θέλω να εξαπατήσω κάποιους στο scrabble... Any ideas...? ps (karabouzouk...) ---------- Προσθήκη στις 18:21 ---------- Προηγούμενο μήνυμα στις 17:48 ---------- cancel that - νομίζω μπερδεύτηκα με τα ονόματα των μεταβλητών ... EDIT: ΑΑΑ! Ένα pet peeve μου είναι τα μη περιγραφικά ονόματα μεταβλητών. Επειδή λοιπόν μπερδευόμουν έκανα ένα search&replace στον αρχικό κώδικα και μετά παρατήρησα το παρακάτω: > /* Read the first string, incrementing the corresponding histogram entry */ for (i = 0; i < input_word.length(); i++) { if (word_to_check[i] >= 'A' && word_to_check[i] <= 'Z') Το loop επαναλαμβάνεται με βάση το μήκος του input_word (που έδωσε ο χρήστης), αλλά ελέγχει τα περιεχόμενα του word_to_check (αυτό που ελέγχει από το αρχείο) είσαι σίγουρος..? γιατί το βλέπω μια χαρά..! το w1sz που είναι στην πρώτη επανάληψη είναι το μέγεθος της λέξης που δίνω σαν είσοδο.. για κάνε ένα copy paste το λάθος μου από τον κώδικα που έχω δώσει να μου πεις τι εννοείς.. ps karabouzouk.. (είμαι σε άλλο pc και βαριέμαι να κάνω log out..)
chigal Δημοσ. 30 Απριλίου 2010 Δημοσ. 30 Απριλίου 2010 Από το αρχικό σου post: > cin >> test_word; w1sz = test_word.length(); fd >> cur_word; w2sz = cur_word.length(); /* Read the first string, incrementing the corresponding histogram entry */ for (i = 0; i < w1sz; i++) { if (cur_word[i] >= 'A' && cur_word[i] <= 'Z') freqtbl[cur_word[i] - 'A']++; κτλ κτλ Ομοίως και για το δεύτερο for Αλλά νομίζω πως το σωστό είναι: > for (i = 0; i < w1sz; i++) { if (test_word[i] >= 'A' && test_word[i] <= 'Z') freqtbl[test_word[i] - 'A']++;
karabouzouk... Δημοσ. 30 Απριλίου 2010 Μέλος Δημοσ. 30 Απριλίου 2010 Από το αρχικό σου post: > cin >> test_word; w1sz = test_word.length(); fd >> cur_word; w2sz = cur_word.length(); /* Read the first string, incrementing the corresponding histogram entry */ for (i = 0; i < w1sz; i++) { if (cur_word[i] >= 'A' && cur_word[i] <= 'Z') freqtbl[cur_word[i] - 'A']++; κτλ κτλ Ομοίως και για το δεύτερο for Αλλά νομίζω πως το σωστό είναι: > for (i = 0; i < w1sz; i++) { if (test_word[i] >= 'A' && test_word[i] <= 'Z') freqtbl[test_word[i] - 'A']++; ναι και στη δευτερη for είναι το cur_word.... έχω την εντύπωση ότι έχεισ απόλυτο δίκιο.... Αλλά πρέπει να πάω σχολή και θα το τσεκάρω μετά..! Ευχαριστώ..
m1cRo Δημοσ. 30 Απριλίου 2010 Δημοσ. 30 Απριλίου 2010 >//============================================================================ // Name : Algo.cpp // Author : m1cRo // Version : // Description : Permutation algorithm //============================================================================ #include <stdio.h> #include <conio.h> #include <string.h> using namespace std; char *alfa; char *result; void calculate(char *result,int index){ int len=strlen(alfa); if(index==len){ puts(result); return; } for(int i=0;i<len;i++){ result[index+1]='\0'; if(strchr(result,alfa[i])==NULL){ result[index]=alfa[i]; calculate(result,index+1); } } } int main(int argc,char **argv) { if(argc!=2){ puts("Wrong number of parameters"); return -1; } unsigned int aLen=strlen(argv[1]); alfa=new char[aLen]; if(alfa==NULL){ puts("Memory allocation error"); return -1; } result=new char[aLen]; if(result==NULL){ puts("Memory allocation error"); return -1; } strcpy(alfa,argv[1]); calculate(result,0); delete alfa; delete result; return 0; }
Directx Δημοσ. 30 Απριλίου 2010 Δημοσ. 30 Απριλίου 2010 Όντως απ όσο είδα και γω δουλεύει μιά χαρά αλλά πώς μπορώ να το κάνω να βρήσκει και λέξεις που έχουν λιγότερα γράμματα από τη συμβολοσειρά που δείνω σαν είσοδο γιατί δεν τα κατάφερα..?[..] Θα μπορούσε να γίνει με αντιστροφή των ελέγχων μεταξύ szWord και szMatch όσο και με την αλλαγή συνθήκης ελέγχου μήκους μεταξύ των εξεταζόμενων αλφαριθμητικών ώστε να μην ελέγχονται μεγαλύτερα strings από εκείνα του αναγραμματισμού. > /* * Anagram solver (dictionary based & case sensitive) by directx. * v2 - Partial matching when undef _ABS_SCAN. * * Usage: dictionary-file anagram */ #include <stdio.h> #include <string.h> #undef _ABS_SCAN int main(int argc, char *argv[]) { char szWord[bUFSIZ]; FILE *fStream = NULL; /* Args check. */ if(argc != 3) { fprintf(stderr, "Usage: dictionary-file anagram\n"); return 1; } /* Open dictionary file for read. */ if((fStream = fopen(argv[1], "rt")) == NULL) { fprintf(stderr, "Cannot open file - %s\n", argv[1]); return 1; } else { /* Process each word. */ while(fscanf(fStream, "%s", szWord) != EOF) { char szMatch[bUFSIZ], szSpc[bUFSIZ]; char *ptrPos = NULL; /* Match word and anagram length. */ #ifdef _ABS_SCAN if(strlen(szWord) != strlen(argv[2])) continue; /* Does not match! */ #else if(strlen(szWord) > strlen(argv[2])) continue; /* Won't match! */ /* Reset szSpc. */ memset(szSpc, 0x1, sizeof(char) * BUFSIZ); #endif /* Prepare check buffer (spc length should be equal to szWord length). */ memset(szSpc, ' ', sizeof(char) * strlen(szWord)); /* Duplicate argv[2] to szMatch. */ #ifdef _ABS_SCAN strcpy(szMatch, argv[2]); #else strcpy(szMatch, szWord); #endif /* Eliminate each of the same character among szWord and szMatch. */ #ifdef _ABS_SCAN for(int MasterIdx = 0; MasterIdx < strlen(szWord); MasterIdx++) if((ptrPos = (char*)memchr(&szMatch, szWord[MasterIdx], sizeof(char) * strlen(szMatch))) != NULL) szMatch[ptrPos - szMatch] = ' '; #else for(int MasterIdx = 0; MasterIdx < strlen(argv[2]); MasterIdx++) if((ptrPos = (char*)memchr(&szMatch, argv[2][MasterIdx], sizeof(char) * strlen(szMatch))) != NULL) szMatch[ptrPos - szMatch] = ' '; #endif /* Match the result of szMatch to szSpc whitespaced buffer. */ if(!memcmp(szMatch, szSpc, strlen(szWord))) printf("->%s\n", szWord); /* We have a possible match! */ } /* Free local resources. */ fclose(fStream); } printf("\nPress Enter to exit.."); getchar(); return 0; } ΕΙΣΟΔΟΣ > list.txt jteena ΕΞΟΔΟΣ > ->j ->janete ->jate ->jena ->jene ->a ->aete ->an ->anete ->ante ->anteje ->ate ->e ->ej ->ejane ->ean ->en ->ena ->enate ->enea ->etaje ->n ->na ->nae ->nea ->nee ->neta ->nete ->nte ->t ->ta ->taje Ελπίζω να είναι αυτό που ζητάς (αν και δεν έχω κάνει ενδελεχείς ελέγχους!). Καλή συνέχεια.
karabouzouk... Δημοσ. 1 Μαΐου 2010 Μέλος Δημοσ. 1 Μαΐου 2010 Σ'ευχαριστώ Directx για τον κόπο σου.. αυτό ακριβώς θέλω.. Αλλά θέλω και να τελειοποιήσω τον κώδικά μου.. Πρόσθεσα μια ταξινόμιση για να έχω τα αποτελέσματα σε σειρά με πρώτα αυτά με τα περισσότερα γράμματα.. Και μια επανάληψη για να μπορώ να ξαναδείνω γραμματοσειρά προς έλεγχο χωρίς να βγαίνω από το πρόγραμμα.. Αλλα όταν φτάνει στο τέλος του αρχείου και πάω να ξαναπροσπαθήσω πάω το δέικτη στην αρχή αλλά συνεχίζει να βγαίνει απο την επανάληψη στο σημείο που ελέγχω αν είναι στο τέλος του αρχείου.. Ριξτε μια ματιά αν κάνω κάτι λάθος >int main() { int i, w1sz, w2sz, freqtbl[26], flag, r, k, max; ifstream fd; string list_word, test_letters, res[200], temp; fd.open("greek word list.txt"); if (!fd.is_open()) { cout << "Error opening files....\n\n"; getchar(); return 1; } while (1) { cout << "\n\nDwse Grammatoseira...: "; cin >> test_letters; fd.seekg(0, ios::beg); //<<- edw paw to deikth sthn arxh r = 0; w1sz = test_letters.length(); //fd >> list_word; while (1) { flag = 0; fd >> list_word; if (fd.eof()) break; //<<- elegxos an vriskome sto telos tou arxeiou kai eksodos apo to loop (edw vgainei sunexia..) if (list_word.length() < 2) continue; w2sz = list_word.length(); /* Sanity check */ if (w1sz < w2sz) { continue; } /* Initialize the histogram */ //bzero(freqtbl, 26 * sizeof (int)); memset(freqtbl, 0, 26 * sizeof (int)); /* Read the first string, incrementing the corresponding histogram entry */ for (i = 0; i < w1sz; i++) { if (test_letters[i] >= 'A' && test_letters[i] <= 'Z') freqtbl[test_letters[i] - 'A']++; else if (test_letters[i] >= 'a' && test_letters[i] <= 'z') freqtbl[test_letters[i] - 'a']++; } /* Read the second string, decrementing the corresponding histogram entry */ for (i = 0; i < w2sz && flag == 0; i++) { if (list_word[i] >= 'A' && list_word[i] <= 'Z') { if (freqtbl[list_word[i] - 'A'] == 0) { flag = 1; } freqtbl[list_word[i] - 'A']--; } else if (list_word[i] >= 'a' && list_word[i] <= 'z') { if (freqtbl[list_word[i] - 'a'] == 0) { flag = 1; } freqtbl[list_word[i] - 'a']--; } } if (flag == 0) { res[r++] = list_word; } } for (i = 0; i < r - 1; i++) { max = i; for (k = i + 1; k < r; k++) { if (res[k].length() > res[max].length()) max = k; } temp = res[i]; res[i] = res[max]; res[max] = temp; } for (i = 0; i < r; i++) { cout << res[i] << " - " << i << endl; res[i].clear(); } } fd.close(); return (0); }
Directx Δημοσ. 1 Μαΐου 2010 Δημοσ. 1 Μαΐου 2010 [..]αλλα όταν φτάνει στο τέλος του αρχείου και πάω να ξαναπροσπαθήσω πάω το δέικτη στην αρχή αλλά συνεχίζει να βγαίνει απο την επανάληψη στο σημείο που ελέγχω αν είναι στο τέλος του αρχείου..[..] Αυτό συμβαίνει διότι την δεύτερη φορά που εκτελείται ο έλεγχος "fd.eof()" επιστρέφει true (δηλαδή το stream είναι ακόμα σε κατάσταση EOF ακόμα και αν έχεις ζητήσει ".seekg") οπότε λόγο "break" το "while(1)" διακόπτεται. Θα μπορούσες να επαναφέρεις το eof state flag του stream σε "good-state" με την βοήθεια της ".clear(ios::eofbit)", πχ. "fd.clear(ios::eofbit)" πριν το "fd.seekg": > [u][b]fd.clear(ios::eofbit);[/b][/u] fd.seekg(0, ios::beg); //<<- edw paw to deikth sthn arxh r = 0; w1sz = test_letters.length(); //fd >> list_word; while (1) {
karabouzouk... Δημοσ. 1 Μαΐου 2010 Μέλος Δημοσ. 1 Μαΐου 2010 Αυτό συμβαίνει διότι την δεύτερη φορά που εκτελείται ο έλεγχος "fd.eof()" επιστρέφει true (δηλαδή το stream είναι ακόμα σε κατάσταση EOF ακόμα και αν έχεις ζητήσει ".seekg") οπότε λόγο "break" το "while(1)" διακόπτεται. Θα μπορούσες να επαναφέρεις το eof state flag του stream σε "good-state" με την βοήθεια της ".clear(ios::eofbit)", πχ. "fd.clear(ios::eofbit)" πριν το "fd.seekg": > [u][b]fd.clear(ios::eofbit);[/b][/u] fd.seekg(0, ios::beg); //<<- edw paw to deikth sthn arxh r = 0; w1sz = test_letters.length(); //fd >> list_word; while (1) { Το δοκίμασες με τον κώδικα μου..? Γιατί το έβαλα και γίνεται πάλι το ίδιο.. μόλις φτάνει στον έλεγχο για το eof σταματάει το loop με το break...
Προτεινόμενες αναρτήσεις
Αρχειοθετημένο
Αυτό το θέμα έχει αρχειοθετηθεί και είναι κλειστό για περαιτέρω απαντήσεις.