Ubuntu-gr Forum

Προφανώς μετά από 1,5 χρόνο ο TS έχει ήδη λύσει την άσκηση, αλλά επειδή μου κίνησε το ενδιαφέρον (είναι έξυπνη άσκηση) νομίζω δεν βλάπτει να παραθέσουμε κώδικα για την επίλυσή της.

Ο κώδικας δεν συνθέτει λέξεις (αυτό είναι ζόρικο) αλλά ελέγχει ποιες λέξεις από αυτές που βρίσκονται μέσα στο αρχείο "lejeis.txt" ταιριάζουν σε επίπεδο ψηφίων με το νούμερο που εισαγάγει ο χρήστης από το πληκτρολόγιο, και τις τυπώνει στην οθόνη.

Πριν παραθέσω ολοκληρωμένο τον κώδικα θα ήθελα να επισημάνω κάποιες διευκρινήσεις και να εξηγήσω λίγο τη λογική του (ειδικά τον πίνακα αντιστοίχισης):

1. Οι λέξεις μέσα στο αρχείο "lejeis.txt" ΠΡΕΠΕΙ να είναι η μία κάτω από την άλλη (βαρέθηκα να το κάνω πιο ευέλικτο στην ανάγνωσής τους). Το διάβασμά τους το κάνω με τη συνάρτηση:

Κώδικας: Επιλογή όλων

char *s_fget(char *s, size_t len, FILE *fp)

η οποία είναι η παραλλαγή για αρχεία της συνάρτησης που έχω παραθέσει σε αυτό εδώ το post.

2. Το νούμερο που εισαγάγει ο χρήστης το διαβάζω ως string 7 ψηφίων, με τη συνάρτηση:

Κώδικας: Επιλογή όλων

int digs_ngets( char *digs, int n )

η οποία σε συνδυασμό με το do-while loop στην main() ΑΠΑΙΤΕΙ το νούμερο να είναι 7-ψήφιο.

3. Για να το συγκρίνω με κάθε λέξη του αρχείου, στο loop διαβάσματος μετατρέπω προσωρινά την κάθε λέξη επίσης σε string ψηφίων, με το κάθε ψηφίο να αντιστοιχεί στο κάθε γράμμα της λέξης βάσει των τηλεφωνικών κουμπιών που δείχνει η εικόνα της εκφώνησης. Η μετατροπή αυτή γίνεται με τη συνάρτηση:

Κώδικας: Επιλογή όλων

char *s_word2digs( char *digs, char *word, int *map )

(εξηγώ παρακάτω τι είναι το 'map')

4. Προφανώς η μετατροπή γράμματος σε ψηφίο, προϋποθέτει να υπάρχει αρχικά ένας πίνακας από strings, με τη θέση του κάθε string μέσα στον πίνακα να αντιστοιχεί στο ψηφίο του εκάστοτε κουμπιού και το ίδιο το string να αποτελείται από τα γράμματα του κουμπιού. Αυτός ο πίνακας στον κώδικα είναι ο:

Κώδικας: Επιλογή όλων


char *buttons[ MAX_BUTTONS ] = {
"xyzXYZ", "abAB", "cdeCDE", "fgFG", "hijHIJ",
"klKL", "mnoMNO", "pqrPQR", "stST", "uwvUWV"
};


(έχω προσθέσει και τα πεζά γράμματα μαζί με τα κεφαλαία).

5. Ενδεχομένως ο πιο κοινός τρόπος να γίνει η μετατροπή ενός γράμματος σε αντίστοιχο ψηφίο είναι με ένα loop από το κουμπί 0 έως το 9 στον παραπάνω πίνακα, και κατόπιν είτε με τη χρήση της στάνταρ συνάρτησης strchr() είτε με δικιά μας συνάρτηση να ελέγξουμε αν υπάρχει το γράμμα που ψάχνουμε μέσα στο string του τρέχοντος κουμπιού, κι αν υπάρχει να επιστρέφουμε τη θέση του string μέσα στον πίνακα (0 έως 9 δηλαδή) που είναι και το ζητούμενο ψηφίο. Αλλιώς να πηγαίνουμε στο επόμενο κουμπί και να επαναλαμβάνουμε τη διαδικασία.

Έτσι όμως όσο περισσότερες είναι οι λέξεις μέσα στο αρχείο και όσο μεγαλύτερα είναι τα strings των κουμπιών (πχ μπορούμε να προσθέσουμε και τα Ελληνικά γράμματα στο κάθε κουμπί, κεφαλαία και πεζά) και όσο σε πιο πίσω θέση του πίνακα βρίσκεται το string με το γράμμα που ψάχνουμε, τόσο περισσότερες αναζητήσεις κάνουμε και άρα τόσο περισσότερο καθυστερεί το πρόγραμμά μας.

Ακόμα και γρήγορους αλγόριθμους αναζήτησης να εφαρμόσουμε για την αναζήτηση του γράμματος στο κάθε string κουμπιού, σίγουρα κατά μέσο όρο θα κάνουμε πάνω από 2 αναζητήσεις ανά string κουμπιού κι αυτό για κάθε γράμμα των λέξεων.

6. Για να αποφύγω λοιπόν όλη αυτή την καθυστέρηση, χρησιμοποιώ έναν πίνακα αντιστοίχισης 'map' οπότε δεν χρειάζεται να κάνω ΚΑΜΙΑ αναζήτηση, με μοναδικό ΕΦΑΠΑΞ κόστος την αρχικοποίηση του πίνακα και το casting από char σε int, στη συνάρτηση:

Κώδικας: Επιλογή όλων

void map_buttons( int *map, char **buttons )

Αυτό που κάνω ουσιαστικά είναι ότι χαρτογραφώ μέσα στον πίνακα 'map' όλον τον πίνακα ASCII (256 χαρακτήρες δηλαδή). Αυτό σημαίνει πως οι θέσεις του πίνακα 'map' (δλδ τα indices του) είναι τα ASCII codes των χαρακτήρων από το 0 έως το 255. Με την ταχύτατη memset() αρχικοποιώ τις τιμές των κελιών του 'map' σε -1 και κατόπιν με ένα loop από 0 έως 9 (10 κουμπιά δλδ) διατρέχω τα κουμπιά εξετάζοντας τα γράμματα των strings τους, βάζοντας το ψηφίο που αντιστοιχεί στο κάθε γράμμα ως τιμή στο αντίστοιχο κελί του 'map' .

Οπότε, έχω πλέον ανά πάσα στιγμή το ψηφίο που αντιστοιχεί π.χ. στο γράμμα Α με ένα απλό indexing στον πίνακα map στη θέση 'A'...

Κώδικας: Επιλογή όλων


map['A']


Στον κώδικα έχω γράψει επίσης πολλά επεξηγηματικά σχόλια. Ελπίζω να φανεί χρήσιμος σε κάποιους. Βελτιώσεις, παρατηρήσεις, επισημάνσεις πάντα ευπρόσδεκτες. Κοιτάξτε και για κάνα bug, γιατί δεν έκανα πολύ testing με λέξεις.

ΟΛΟΚΛΗΡΩΜΕΝΟΣ ΚΩΔΙΚΑΣ

Κώδικας: Επιλογή όλων


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_BUTTONS 10
#define MAPPED_NCHARS 256
#define MAXLEN_WORD 7+1

#define myexit(n) printf("\npress ENTER to exit..."); fflush(stdin); getchar(); exit((n))

typedef enum { FALSE=0, TRUE } bool;

// ------------------------------------------------------------------------------------
// Διαβάζει το string 'digs' από το πληκτρολόγιο έως ότου είτε συμπληρωθούν 'n'
// χαρακτήρες, είτε πατηθεί ENTER, είτε εισαχθεί χαρακτήρας που ΔΕΝ είναι ψηφίο και
// μηδενίζει τον τελικό χαρακτήρα (αν ο τελικός ήταν ENTER ή ΜΗ ψηφίο, τον αντικαθιστά).
// ΕΠΙΣΤΡΕΦΕΙ -1 αν έστω κι ένας από τους χαρακτήρες δεν ήταν ψηφίο, αλλιώς επσιτρέφει
// το πλήθος των χαρακτήρων που εκχωρήθηκαν στο 'digs', εξαιρουμένου του τελικού '\0'
//
int digs_ngets( char *digs, int n )
{
bool digvalid = TRUE;
register char *cp = digs;

while ( digvalid && (*cp=getc(stdin)) != '\n' && (cp-digs) < n-1 )
{
if ( !isdigit( *cp ) )
digvalid = FALSE;
cp++;
}
*cp = '\0';

return digvalid ? cp-digs : -1 ;
}

// ------------------------------------------------------------------------------------
// Διαβάζει το string 's' από το αρχείο 'fp' έως ότου είτε συμπληρωθούν 'len' χαρακτήρες
// είτε βρεθεί αλλαγή γραμμής, είτε βρεθεί EOF. Αν δεν βρεθεί EOF, μηδενίζει τον τελικό
// χαρακτήρα (αν ήταν ENTER το σβήνει).
// ΕΠΙΣΤΡΕΦΕΙ NULL αν βρεθεί EOF, αλλιώς το "διαβασμένο" string 's'
//
char *s_fget(char *s, size_t len, FILE *fp)
{
if ( !fp )
return NULL;

char *cp = s;
for ( ; (*cp=getc(fp)) != '\n' && *cp != EOF && (cp-s) < len-1; cp++ )
; // for-loop with empty body

if ( *cp == EOF) // we've reached end of file
return NULL;

*cp = '\0'; // null-terminate last character

return s;
}

// ------------------------------------------------------------------------------------
// Χρησιμοποιεί τον πίνακα αντιστοίχισης 'map' για να αντιστοιχήσει τους χαρακτήρες
// του string 'word' σε χαρακτήρες ψηφίων, τους οποίους αποθηκεύει στο string 'digs'.
// ΕΠΙΣΤΡΕΦΕΙ το string 'digs' ή NULL σε περίπτωση σφάλματος.
//
char *s_word2digs( char *digs, char *word, int *map )
{
if ( !word || !map )
return NULL;

char *save = digs;
for ( ; *word; word++)
*digs++ = '0' + map[ (unsigned) *word ];
*digs = '\0';

return save;
}

// ------------------------------------------------------------------------------------
// Χρησιμοποιεί τα γράμματα των κουμπιών 'buttons' ως τιμές ευρετηρίου (indices) για
// τον πίνακα αντιστοίχισης 'map', και αποθηκεύει στον 'map'το ψηφίο που αντιστοιχεί
// στο κάθε γράμμα...
// π.χ. map['x'] = map['y'] = map['z] = 0, map['a'] = map['b'] = 1, κλπ.
// Όσοι χαρακτήρες δεν υπάρχουν στα κουμπιά, αρχικοποιούνται με την τιμη -1 (μέσω
// της συνάρτησης memset() ). Ο πίνακας αντιστοίχισης 'map' έχει χώρο για 256
// χαρακτήρες (MAPPED_NCHARS) ώστε να μπορούν να προστεθούν στα κουμπιά και χαρακτήρες
// με ASCII code από 128 έως 255 (όπως για παράδειγμα τα Ελληνικά της κωδικοσελίδας 737)
//
void map_buttons( int *map, char **buttons )
{
register int i;
register char *cp = NULL;

memset( map, -1, MAPPED_NCHARS * sizeof(int) );
for (i=0; i < MAX_BUTTONS; i++ )
for ( cp=buttons[i]; *cp != '\0'; cp++ )
map[ (int)*cp ] = i;

return;
}

// ------------------------------------------------------------------------------------
int main( void )
{
// τα γράμματα των κουμπιών (η θέση των κουμπιών
char *buttons[ MAX_BUTTONS ] = { // στον πίνακα ταυτίζεται με το ψηφίο τους)
"xyzXYZ", "abAB", "cdeCDE", "fgFG", "hijHIJ",
"klKL", "mnoMNO", "pqrPQR", "stST", "uwvUWV"
};
int map[ MAPPED_NCHARS ]; // για την αντιστοίχιση των γραμμάτων σε ψηφία
FILE *fp = NULL; // για το αρχείο 'lejeis.txt'
char word[ MAXLEN_WORD ]=""; // string για το διάβασμα λέξεων από το αρχείο
char digits[ MAXLEN_WORD ]=""; // το string ψηφίων που διαβάζουμε από το χρήστη
char tempdigs[ MAXLEN_WORD ] = ""; // προσωρινό string ψηφίων
int ndigits = 0; // προσωρινή μεταβλητή

fp = fopen("lejeis.txt", "r"); // άνοιγμα του αρχείου
if ( !fp ) { // αποτυχία ανοίγματος
puts("*** error: cannot open file"); // πρόωρος τερματισμός προγράμματος
myexit(1);
}

map_buttons(map, buttons); // γέμισμα του πίνακα αντιστοίχισης

do // εισαγωγή αριθμού από τον χρήστη
{ // (απαιτεί να είναι 7-ψήφιο νούμερο)
printf("Enter a valid 7-digit phone number: ");
fflush( stdin );
ndigits = digs_ngets( digits, MAXLEN_WORD );
} while ( ndigits == -1 || ndigits != MAXLEN_WORD-1 );

/*
* Διάβασμα των λέξων από το αρχείο 'lejeis.txt'.
* Η κάθε λέξη μετατρέπεται προσωρινά σε νέο string από ψηφία (tempdigs), τα οποία
* ψηφία αντιστοιχούν στα γράμματα της αυθεντικής λέξης. Κατόπιν, το προσωρινό
* string συγκρίνεται με το string ψηφίων που εισήαγαγε ο χρήστης (digits),
* κι αν ταιριάζουν τότε τυπώνεται η αυθεντική λέξη (word) στην οθόνη.
*/

bool dummy = FALSE;
while ( s_fget(word, MAXLEN_WORD, fp) ) // διάβασμα λέξης από αρχείο
{
s_word2digs(tempdigs, word, map); // μετατροπή της λέξης σε string ψηφίων

if ( !strcmp(digits, tempdigs) ) { // σύγκριση με τα ψηφία του χρήστη
puts(word);
dummy = (dummy || TRUE);
}
}

fclose( fp ); // κλείσιμο του αρχείου

if ( !dummy )
puts("No matching words found inside the file");

myexit(0);
}



ΕΝΔΕΙΚΤΙΚΟ ΑΡΧΕΙΟ: lejeis.txt
(ΔΟΚΙΜΑΣΤΕ ΚΙ ΑΛΛΕΣ ΛΕΞΕΙΣ, ΑΥΤΕΣ ΕΙΝΑΙ ΑΝΕΠΑΡΚΕΙΣ ΓΙΑ ΟΛΕΣ ΤΙΣ ΠΙΘΑΝΕΣ ΠΕΡΙΠΤΩΣΕΙΣ)

Κώδικας: Επιλογή όλων


BIOLOGY
KICKASS
PLAYERS
HIDEFTV
WELCOME
DRIVERS
MUSICAL
LEONARD
ROOMIES
FALLING