scrabble code

[dimulator]

Γεια!

 

Το ξέρω πως δεν είναι το κατάλληλο φόρουμ για αυτήν την ερώτηση αλλά βλέπω πως υπάρχουν και εδώ άτομα που μπορούν να απαντήσουν.

 

Το θέμα έχει ως εξής:

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

 

π.χ. Α,Β,Γ,Ο

 

- ΑΒΓΟ

- ΑΒΟΓ

- ΑΟΒΓ

κτλ

 

2) να του δίνεις ένα αριθμό και να σου εμφανίζει όλες τις λέξεις με το λεξαριθμο του αριθού που έδωσες

 

ξέρει κανείς αν υπάρχει τέτοιο πρόγραμμα ή να ξέρει source code σε basic?

Edited October 6, 2009 by dimulator

[Lykon]

Πραγματικά κάτι τέτοιο θα με ενδιέφερε και μένα πάρα πολύ γιατί ψάχνω καιρό να βρω κάτι παρόμοιο. Όποιος μπορεί να βοηθήσει θα μου έλυνε τα χέρια σε διάφορα πραγματακιά που κάνω.

Edited October 6, 2009 by Lykon

[canislupus]

τι θελετε να αποκρυπτογραφισετε ?

[Firemaster]

Υπαρχει αυτο που λες και το μερος να το βρεις λεγεται C.I.A.. Περα απο την πλακα υπαρχουν και τετοια προγραμματα οπου μπορεις ν αγορασεις αλλα δνε ειναι κατι τοσο απλο. Σκεψου οτι πρεπει να εχεις ολες τις λεξεις που εινια γραμμενες με λατινικους χαρακτηρες η Ελληνικους, να μπορει να τρεχει αναμεσα στις λεξεις και να τις επιλεγει. Υπ' οψην οτι ενα τετοιο προγραμμα κοστιζει κατι περισσοτερο απο μια Porsche.... Βεβαια ενας αλλος τροπος ειναι να παρεις λεξικο (για να εχεις ολες τις λεξεις) και αφου μαθεις c++ (εξαιρετικη γλωσσα) να το φτιαξεις μονος σου! :Ρ

[Speedy]

Το πρώτο που λέει ο φίλος ο dimulator σίγουρα κάπου θα υπάρχει. Έχω δει και παιχνίδια στο Internet που πρέπει να κάνεις αυτή τη δουλειά με το μυαλό σου και ανταυτού, σα cheat, κάποιοι φτιάξανε ένα πρόγραμμα που σου δίνει έτοιμες τις λέξεις με βάση τα ανακατωμένα γράμματα που του βάζεις. Αυτό σίγουρα δεν είναι πιο ακριβό από μια Porsche.

 

Τώρα το 2ο μέρος που λες, φίλε dimulator, δε το έχω δει πουθενά συνεπώς ενδέχεται και να μην υπάρχει. Φαντάσου να του δίνεις τον αριθμό 20! Πόσες λέξεις βγαίνουν με αυτό; Δύσκολο....

[johnny]

Ίσως να μην είναι και τόσο δύσκολο, από την άποψη ότι ήδη υπάρχουν ηλεκτρονικά λεξικά και το μόνο που θα χρειαζόταν για κάτι τέτοιο θα ήταν ένα "Plugin" που να δίνει τις αντίστοιχες αριθμητικές αξίες στα γράμματα. Τίποτα το ιδιαίτερο από τεχνικής πλευράς δηλαδή...

[dimulator]

δεν με ενδιαφέρει οι λέξεις που βγάζει να τις ξεχωρίζει ποιες είναι όντως λέξεις και ποιες δεν είναι.

 

Αυτό απαιτεί να συγκρίνει την παραγώμενη λέξη με λέξεις από λίστα λεξικού και δεν διατίθεμαι να γράψω λεξικο.

Αυτό το ξεκαθαρισμα θα το κάνω εγώ στην αναγνωση της παραγώμενης λέξης.

 

 

Εκεί που κολλαω είναι πως να φτιάξω τον αλγόριθμο του συνδυασμού όλων των περιπτώσεων.

Υπόψιν ειμαι και προγραμματιστής και δεν μου έρχεται καμία ιδέα.

 

Σαν πρώτη σκέψη είναι να βάλω κάθε γράμμα σε έναν δυναμικό πίνακα Array() αλλά μετά δεν ξέρω την λογική πως να κάνω συνδυασμούς και μάλιστα όλους μεταξύ των στοιχείων του πίνακα. Αυτό θέλω.

 

Το δεύτερο βασίζεται στο πρώτο. Από την στιγμή που υπάρχει αντιστοιχεία γράμματος με αριθμό και ψάχνουμε μόνο αθροίσματα το ποιοι αριθμοί αν τους προσθέσεις κάνουν το 20 είναι εύκολο.

 

Υπάρχει κάποιος προγραμματιστής να ρίξει καμιά ιδέα;

 

Θα με διευκόλυνε αν ο αλγόριθμος είναι σε vbasic

Edited October 7, 2009 by dimulator

[johnny]

Σιγά μη σου φτιάξουμε και τον αλγόριθμο, που τον θες και σε vbasic.

Σοβαρά τώρα, δεν πρέπει να είναι πολύ δύσκολος ο συνδυασμός γραμμάτων για το σχηματισμό μιας λέξης, αρκεί να βρεις τρόπο να συνδέσεις το πρόγραμμα με τη βάση ενός ηλεκτρονικού λεξικού. Αυτό που δεν καταλαβαίνω όμως είναι γιατί να θες και συνδυασμούς που δεν αποτελούν λέξεις.

[dimulator]

απαιτήσεις ε? να θέλω και κώδικα.... τσ τσ

 

τέλος πάντων, μα αυτό λέω... δεν θέλω να συνδέσω το πρόγραμμα με λεξικό, απλά θέλω όλους τους συνδυασμούς τοποθέτησης των γραμμάτων.

 

Λοιπόν έκανα μια αρχή ενός αλγόριθμου και πάει ως εξής, (δουλεύει για μέχρι 9 γραμματα)

 

1 Βάζουμε τα γραμματα

2 Κάθε γραμμα έχει μια θέση κατά αύξουσα σειρά π.χ. α=1, β=2, γ=3

3 βρίσκω το παραγοντικό από το 1 έως το πλήθος των γραμμάτων π.χ. για 3 γράμματα !3=6

4 βρίσκω το μικρότερο νούμερο με το πλήθος των ψηφίων της λέξης π.χ. ψηφία 3 μικρότερος αριθμός 123

5 βρίσκω τον αριθμό paragontiko + 10^var(len(paragontiko)

6 Κάνω βρόχο από τον αριθμό 123 μέχρι τον αριθμό paragontiko + 10^var(len(paragontiko)

7 Παράγω κάθε αριθμό αυξανόμνο κατά 1

 

για παράδειγμα 123, 124, 126 κτλ

8. αθροιζω τα ψηφία καθε αριθμού και τα συγκρίνω με το παραγοντικό

π.χ. 123-> 1+2+3 = 6 μας κάνει λέξη αβγ

επόμενος αριθμός 124-> 1+2+4=7 όχι λέξη

.....

132-> 1+3+2=6 ναι μας κάνει λέξη αγβ

κτλ

έτσι καθε συνδυασμός μεταξύ των ψηφίων 1,2,3 όταν βγάζει 6 είναι λέξη αλλιώς δεν είναι

9 Τέλος βρόγχου μέχρι τον αριθμό paragontiko + 10^var(len(paragontiko)

10 Τέλος

 

Αυτός ο αλγόριθμος βρίσκει όλους τους συνδυασμούς για λέξεις μέχρι 9 γράμματα δλδ για αριθμό με ψηφία από το 1-9.

Μπορεί να ψάξει δλδ λέξη που αντιστοιχεί σε αριθμο από 123456789 έως 987654321

 

Αν η λέξη έχει 10 γράμματα δεν λειτουργεί....

μέχρι εδώ μπόρεσα να σκεφτώ καμιά ιδέα να λειτουργήσει πάνω από 10 γράμματα;

[dimulator]

Λοιπόν το πρώτο βρέθηκε.

 

phpAG

 

θα το μετατρέψω σε VB και θα το ανεβάσω να το έχετε.

 

 

Το δεύτερο ακόμη το ψάχνω

Edited October 28, 2009 by dimulator

[Τράγου Κέρατο]

Κλασικό πρόβλημα συνδυαστικής για συνδυασμό ν στοιχείων ανά μ.

 

Αν είναι σταθερός ο αριθμός των στοιχείων, μπορείς να το υλοποιήσεις απλά, με nested loops στυλ

 

for i=1 to n-m

for j=i to n-m+1

for k=j to n-m+2

 

κ.ο.κ.

 

Αν θες τώρα να το γράψεις γενικά για ν στοιχεία ανά m, θα πρέπει να το προσεγγίσεις πολύ διαφορετικά και δεν ξέρω αν μπορεί να γίνει χωρίς pointers. Σε C/C++ δηλαδή, θα κάνεις πρώτα allocate το χώρο στη μνήμη για μ δείκτες και μετά θα κάνεις την ίδια δουλειά με τους παραπάνω βρόχους - συγνώμη, θέλει αρκετή συγκέντρωση που δεν την έχω αυτήν τη στιγμή.

 

Πάντως, είναι λογικό να σου σκάει μετά από κάποια νούμερα. Τα παραγοντικά προβλήματα είναι τα πιο δύσκολα, ακόμα πιο δύσκολα κι από τα εκθετικά. Το πιθανότερο είναι πως θα φτάσεις σε νούμερο μεγαλύτερο από αυτόν που μπορεί να χειριστεί η γλώσσα προγραμματισμού ή θα σου τελειώσει η μνήμη. Οπότε καλύτερα να κρατάς τους δείκτες «στον αέρα» και να κρατάς μόνο τα χρήσιμα αποτελέσματα.

 

Α, υπόψην πως μπορείς να χρησιμοποιήσεις έτοιμο λεξικό, αυτό του aspell.

[Τράγου Κέρατο]

Ουφ! Γράψε λάθος γι' αυτά που σου έγραψα προηγουμένως. Παίζουν κι οι αντιμεταθέσεις των γραμμάτων. Οπότε πάμε σε άλλη τακτική.

 

Αν το σκεφτούμε ως αλγόριθμο με αναδρομή, μπορεί να υλοποιηθεί απλά, θεωρητικά. Δηλαδή:

 

Αντιμεταθέσεις ν γραμμάτων ανά μ, ισοδυναμεί με:

- Τις αντιμεταθέσεις του γράμματος 1 σε συνδυασμό με τις αντιμεταθέσεις των γραμμάτων 2..ν ανά μ-1

- Τις αντιμεταθέσεις του γράμματος 2 σε συνδυασμό με τις αντιμεταθέσεις των γραμμάτων 1,3..ν ανά μ-1

- Τις αντιμεταθέσεις του γράμματος 3 σε συνδυασμό με τις αντιμεταθέσεις των γραμμάτων 1,2,4..ν ανά μ-1

...

- Τις αντιμεταθέσεις του γράμματος ν σε συνδυασμό με τις αντιμεταθέσεις των γραμμάτων 1..ν-1 ανά μ-1

 

Οπότε μια τέτοια διαδικασία παίρνει το ένα ένα τα γράμμματα και καλεί τον εαυτό της έχοντας αφαιρέσει το τρέχον γράμμα και αφαιρώντας 1 από το μ. Συνθήκη εξόδου είναι το μ=1 οπότε θα επιστρέφει ένα-ένα τα γράμματα που έχουν απομείνει. Απλό και μπορεί να δουλέψει. Σε prolog είναι δύο κατηγορήματα:

 

combinations( [H | T], Letters) :-
   member(H,Letters),
   select(H,Letters,OtherLetters),
   combinations(T,OtherLetters).

combinations([],_).

doit(X) :-
   X=[A,B,C,D,E],
   Letters=[a,b,c,d,e],
   combinations(X, Letters).

 

 

Αν όμως πας να κρατήσεις τα αποτελέσματα στη μνήμη, την πάτησες, αφού οι συνδυασμοί 11 γραμμάτων ανά 11, είναι 39.916.800, και 11 bytes για να αποθηκεύσεις τον καθένα, θες 439084800 bytes (γύρω στα 439Μ) στη μνήμη για να τους αποθηκεύσεις ενώ για 12 ανά 12 θα χρειαστείς πάνω από 5G μνήμη. Στα 11 γράμματα δε, αν το αποθηκεύσεις και ψάχνεις μετά για έγκυρες λέξεις, ακόμα κι αν ψάχνει 1.000.000 λέξεις ανά δευτερόλεπτο, θα χρειαστείς 40 δευτερόλεπτα για να βρεις όλες τις λέξεις και γύρω στα 8 λεπτά για όλες τις λέξεις από 12 γράμματα.

 

Αν κατάλαβα καλά, από τον τίτλο του post, θες να βρεις όλες τις λέξεις που μπορεί να σχηματίζονται από κάποια δοσμένα γράμματα, κατάλαβα σωστά; Στη συγκεκριμένη περίπτωση, σε συμφέρει να ακολουθήσεις διαφορετική διαδρομή, κόβοντας κλαδιά από το δέντρο. Εγώ τι θα έκανα:

 

- Παίρνουμε τα πιθανά γράμματα.

- Σχηματίζουμε όλους τους πιθανούς συνδυασμούς δύο γραμμάτων. Ως αποτέλεσμα επιστρέφουμε το συνδυασμό και τα αχρησιμοποίητα γράμματα.

- Ελέγχουμε όλους τους συνδυασμούς για το αν ξεκινά λέξη από τον κάθε συνδυασμό. Τους συνδυασμούς από τους οποίους δεν ξεκινά λέξη, τους σβήνουμε.

- Επαναλαμβάνουμε τη διαδικασία, δίνοντας ως παραμέτρους κάθε συνδυασμό που έχει μείνει, συν τα αχρησιμοποίητα γράμματα.

 

Με αυτόν τον τρόπο ο υπολογιστής «κόβει» τα αχρείαστα κλαδιά του δέντρου και συντομεύει πάρα πολύ τη λύση.

[dimulator]

Χε χε καλό πρόβλημα ε!

 

Αλλά η λύση είναι πολύ απλή τελικά. Λύνεται με αναδρομή στο phpAG. Ιδού ο κώδικας για να δεις πόσο εύκολο τελικά ήταν.

 

δίνεις τα γράμματα ανακατεμένα όπως να ναι σε μια μεταβλητή $word

 

$len = strlen ($word);
$array = preg_split ('//', $word, -1, PREG_SPLIT_NO_EMPTY);
anag ($array, 0, $len);

function anag ($array, $start, $len) 
{
global $i;
if ($start < $len)
{
	for ($j = $start; $j < $len; ++$j) 
	{
		if ($j == $start || $array[$j] != $array[$start]) 
		{
			$tmp = $array[$j];
			$array[$j] = $array[$start];
			$array[$start] = $tmp;
			anag ($array, $start+1, $len); // η αναδρομη
		}
	}
}
else
{
	$word = implode ("", $array);
	$i = ++$i;
	echo "$i) $word <br>"; //pio aplo apo to printf
//		printf ("%'.-20d%'.20s%s", $i, ucfirst ($word), "<BR>\n");
}
}

 

βεβαια το μυαλό μου δεν πήγε σε αυτήν την λύση γιατί δεν έχει τύχει ποτέ να χρησιμοποιήσω αναδρομή στην php ή στην Vb ή Gambas που μέχρι τώρα προγραμματίζω.

Edited November 7, 2009 by dimulator

[Τράγου Κέρατο]

Εχμ... η ίδια ακριβώς λύση είναι με αυτή που έγραψα σε prolog, μόνο που είναι υλοποιημένη σε php...

[dimulator]

Εχμ... η ίδια ακριβώς λύση είναι με αυτή που έγραψα σε prolog, μόνο που είναι υλοποιημένη σε php...

 

ναι σωστά και το είπες κιόλας αλλά ego den kserei prolog... :blush: