scrabble code

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

Ε, καλά μωρέ, ούτε εγώ ήξερα μέχρι πέρυσι..

[dimulator]

λοιπόν δοκίμασα τον κώδικα σε vb σέρνεται μέχρι να βγάλει τις λέξεις με πάνω από 5 γράμματα...

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

Στάκα λίγο.

 

Θες να βγάλεις όλους τους πιθανούς συνδυασμούς σε ένα text file ας πούμε ή στην οθόνη και τελείωσε; Ή θες να βγάζει τους πιθανούς συνδυασμούς κι εσύ μετά να τους επεξεργάζεσαι με κάποιον τρόπο; Το πρώτο είναι εύκολο, λογικό είναι η VB να σέρνεται, αν θες ταχύτητα, τότε η C (μη σου πω ούτε καν η C++) είναι μονόδρομος. Το δεύτερο, θέλει περισσότερη μελέτη...

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

Ιδού το πρώτο, σε κλασική C:

 

/*
*  main.c
*  anagrams
*
*  Created by Tragou Kerato on 07/11/2009.
*  Copyright 2009 Avaptisto. All rights reserved.
*
*/
#include <string.h>

void process(char* prefix, int prefixLen, char * letters, int len, int anaglen){
char * letterbuf;
char * prefixbuf;
int i,j;
char c;

if(anaglen==1){
	for(i = 0; i < len; i ++){
		printf("%s%c\n", prefix, *(letters+i));
	} 
} else {
	letterbuf = (char *) malloc (len);
	prefixbuf = (char *) malloc (prefixLen+1);
	for(i = 0; i < len; i++){
		strcpy(letterbuf, letters);
		for(j=i; j < len;j++){
			c = *(letterbuf+j+1);
			*(letterbuf+j) = c;
		}
		strcpy(prefixbuf, prefix);
		*(prefixbuf+prefixLen) = *(letters+i);
		*(prefixbuf+prefixLen+1) = 0;
		process(prefixbuf, prefixLen+1, letterbuf, len-1, anaglen-1);
	}
	free(letterbuf);
	free(prefixbuf);
}
}

void main(){
char * g_letters = "abcdefg";
char * prefix    = "";

process(prefix, 0, g_letters, 7, 7);
}

 

Μπορεί να πάρει βελτιώσεις βεβαίως, αλλά δουλεύει.

Edited November 7, 2009 by Τράγου Κέρατο

[dimulator]

όχι δεν θέλω ιδιαίτερη επεξεργασία των λέξεων.

Απλά να κάνει όλους τους συνδυασμούς.

 

Καλά είσαι καταπληκτικός!!! Το έκανες κιόλας σε C ! Εύγε!

 

Εγώ έκανα πορτ ακριβώς τον κώδικα του phpAG σε Vb και έβαζα τα αποτελέσματα σε ένα Textbox.

 

Για μένα το θέμα έχει λυθεί η php μου είναι μια χαρά αλλά έλεγα να το κάνω σε vb για να το βάλλω στο φόρουμ γιατί το θέλουν και άλλοι όπως θα είδες, και επειδή δεν μπορούν όλοι να έχουν web server και να τρέχουν php.

 

Αλλά η vb σέρνεται σε τέτοια οπότε το άφησα. Από την άλλη μόνο vb και php ξέρω.

Η gambas είναι πιο καλή και μάλλον δεν θα σέρνεται αλλά ποιός έχει linux ειναι το θέμα!

Edited November 7, 2009 by dimulator

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

E, OK, ο κώδικας είναι διαθέσιμος (όπως είδες τα copyrights ανήκουν στο Αβάπτιστο ) και λογικά με τον τζάμπα borland compiler θα γίνεται εκτελέσιμο για windows. Οι λινουξάδες ξέρουν να το κάνουν εκτελέσιμο, οι δε συνάδελφοι Mac users θα τα βρούμε.

 

Προφανώς πάντως φταίει το textbox για την καθυστέρηση. Με κάθε print, πρέπει να αυξάνεται η μνήμη που αφιερώνεται στο textbox και η απόδοση μνήμης όχι απλώς είναι ακριβή διαδικασία, αλλά γίνεται και πιο δύσκολη όσο αυξάνεται η μνήμη. Εκεί είναι που θέλει βελτίωση κι ο κώδικας που έγραψα: κάνει malloc και free σε κάθε αναδρομική κλήση. Θα μπορούσε να κάνει την ανάθεση της μνήμης μια φορά στο setup και μετά κάθε κλήση να χρησιμοποιεί τον ήδη κρατημένο χώρο. Αλλά αυτό θα χρειαστεί pointers σε pointers ( char ** ) και βαριόμουν να το φτιάξω γιατί χάνεις πολύ εύκολα τη μπάλλα. Έτσι κι αλλιώς βγάζει όλους τους συνδυασμούς για 10 γράμματα σε λιγότερο από 10 λεπτά στο MacBook μου.

 

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

[dimulator]

λοιπόν αν μπορούσες να κάνεις μια μικρή τροποποίηση στο κώδικα C, 8α το κάνω exe,

 

η τροποποίηση είναι να μπορεί να δίνει ο χρήστης τα γράμματα από την γραμμή εντολών κάπως έτσι

 

c:\anagram.exe -letters abcdefg

οπότε κάτι πρέπει να γίνει εδώ αλλά δεν ξέρω να το κάνω

 

void main(){
       char * g_letters = "abcdefg"; // μια μικρή τροποποιηση ίσως εδώ ώστε να υπάρχει input
       char * prefix    = "";

       process(prefix, 0, g_letters, 7, 7);
}

[dimulator]

δοκιμασα τον κώδικα σε TC και είδα ότι λείπαν κάποιες βιβλιοθήκες για την printf, alloc και έκανα μια μικρή επεξεργασία του κώδικα

 

/*
*  main.c
*  anagrams
*
*  Created by Tragou Kerato on 07/11/2009.
*  Edited by Dimulator on 08/11/2009.
*  Copyright 2009 Avaptisto. All rights reserved.
*
*/
#include <string.h>
#include <stdio.h> //προσθήκη
#include <alloc.h> //προσθήκη


void process(char* prefix, int prefixLen, char * letters, int len, int anaglen){
       char * letterbuf;
       char * prefixbuf;
       int i,j;
       char c;

       if(anaglen==1){
               for(i = 0; i < len; i ++){
                       printf("%s%c\n", prefix, *(letters+i));
               } 
       } else {
               letterbuf = (char *) malloc (len);
               prefixbuf = (char *) malloc (prefixLen+1);
               for(i = 0; i < len; i++){
                       strcpy(letterbuf, letters);
                       for(j=i; j < len;j++){
                               c = *(letterbuf+j+1);
                               *(letterbuf+j) = c;
                       }
                       strcpy(prefixbuf, prefix);
                       *(prefixbuf+prefixLen) = *(letters+i);
                       *(prefixbuf+prefixLen+1) = 0;
                       process(prefixbuf, prefixLen+1, letterbuf, len-1, anaglen-1);
               }
               free(letterbuf);
               free(prefixbuf);
       }
}

void main(){
char * g_letters = "abcdefg";
       char * prefix    = "";

       process(prefix, 0, g_letters, 7, 7); //επίσης το μηκος της λέξης θα πρέπει να υπολοίζεται, να μην είναι φιξ 7.
}

 

δεν ξέρω γιατί αλλά δοκίμασα το κωδικα σε C++ και είναι ακόμη ποιο αργός από VB!!!

Edited November 8, 2009 by dimulator

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

Έκανα την προσθήκη, έβαλα και τις βιβλιοθήκες που έλειπαν (αν και ο δικός μου compiler δεν γκρίνιαζε):

 

/*
*  main.c
*  anagrams
*
*  Created by Tragou Kerato on 07/11/2009.
*  Copyright 2009 Avaptisto. All rights reserved.
*
*/
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

void process(char* prefix, int prefixLen, char * letters, int len, int anaglen){
char * letterbuf;
char * prefixbuf;
int i,j;
char c;

if(anaglen==1){
	for(i = 0; i < len; i ++){
		printf("%s%c\n", prefix, *(letters+i));
	} 
} else {
	letterbuf = (char *) malloc (len);
	prefixbuf = (char *) malloc (prefixLen+1);
	for(i = 0; i < len; i++){
		strcpy(letterbuf, letters);
		for(j=i; j < len;j++){
			c = *(letterbuf+j+1);
			*(letterbuf+j) = c;
		}
		strcpy(prefixbuf, prefix);
		*(prefixbuf+prefixLen) = *(letters+i);
		*(prefixbuf+prefixLen+1) = 0;
		process(prefixbuf, prefixLen+1, letterbuf, len-1, anaglen-1);
	}
	free(letterbuf);
	free(prefixbuf);
}
}

void print_instructions(){
printf("Usage:\n");
printf("\n");
printf("anagrams <string> [combination_length]\n");
printf("\n");
printf("e.g. anagrams abcdefg 5\n");
printf("Will output all combinations of letters \"abcdefg\" that are 5 characters long.\n");
printf("\n");
printf("\n");
}

int main(int argc, char * argv[]){
char * g_letters;
int g_letters_len, perm;
char * prefix    = "";

if(argc==1){
	printf("No letters were given.\n");
	print_instructions();
	return -1;
} else {
	if(argc>=2){
		g_letters = argv[1];
		g_letters_len = strlen(g_letters);
		perm = g_letters_len;
	}
	if(argc>=3){
		perm=atoi(argv[2]);
		if(perm<=0 || perm > g_letters_len){
			printf("No length of anagrams was given or illegal length specified.");
			print_instructions();
			return -1;
		}
	}
	process(prefix, 0, g_letters, g_letters_len, perm);
	return 0;
}
}

Edited November 8, 2009 by Τράγου Κέρατο

[dimulator]

ωραία! Το δοκίμασα αλλά με 4 γράμματα "abcd" αργεί πολύ να βγάλει τα ποτελεσματα από την 6η λέξη και μετά και ρουφάει κυριολεκτικά πολύ μνήμη.

 

Παρόλα αυτά το αρχείο είναι αυτό.

ANAGRAMS.zip

[dimulator]

προσπαθώ να κάνω ακόμη το πρόγραμμα σε VB, τελικά το έκανα πολύ γρήγορο πιο γρήγορο από την C αλλά έχω ένα bug και προσπαθώ να το βρω.

Τράγε ξέρεις καθόλου από VB5?

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

ωραία! Το δοκίμασα αλλά με 4 γράμματα "abcd" αργεί πολύ να βγάλει τα ποτελεσματα από την 6η λέξη και μετά και ρουφάει κυριολεκτικά πολύ μνήμη.

 

ΕΛΑ;!;! Εγώ στο mac που το έτρεξα, σου είπα, έβγαλε όλους τους αναγραμματισμούς 10 γραμμάτων σε λιγότερο από 2 λεπτά. Το άλλο που λες πως «ρουφάει πολλή μνήμη» μου φαίνεται ακατανόητο. Τα malloc και τα free ταιριάζουν απόλυτα. Κάπου δημιουργείται memory leak, αλλά δε βλέπω που μπορεί να δημιουργείται το πρόβλημα.

 

προσπαθώ να κάνω ακόμη το πρόγραμμα σε VB, τελικά το έκανα πολύ γρήγορο πιο γρήγορο από την C αλλά έχω ένα bug και προσπαθώ να το βρω.

Τράγε ξέρεις καθόλου από VB5?

 

Καλά, και μόνο που μου λες πως σε VB τρέχει πιο γρήγορα από C, είναι πολύ ύποπτο. Από VB5 δεν ξέρω, μόνο με VBA είχα ασχοληθεί προ δεκαετίας. Μόνο από BASIC ξέρω, γράψε τον κώδικα, αλλά έτσι κι αλλιώς δεν έχω windows μηχάνημα στο σπίτι για να το κάνω compile.

Edited November 8, 2009 by Τράγου Κέρατο

[dimulator]

ΕΛΑ;!;! Εγώ στο mac που το έτρεξα, σου είπα, έβγαλε όλους τους αναγραμματισμούς 10 γραμμάτων σε λιγότερο από 2 λεπτά. Το άλλο που λες πως «ρουφάει πολλή μνήμη» μου φαίνεται ακατανόητο. Τα malloc και τα free ταιριάζουν απόλυτα. Κάπου δημιουργείται memory leak, αλλά δε βλέπω που μπορεί να δημιουργείται το πρόβλημα.

 

 

 

Καλά, και μόνο που μου λες πως σε VB τρέχει πιο γρήγορα από C, είναι πολύ ύποπτο. Από VB5 δεν ξέρω, μόνο με VBA είχα ασχοληθεί προ δεκαετίας. Μόνο από BASIC ξέρω, γράψε τον κώδικα, αλλά έτσι κι αλλιώς δεν έχω windows μηχάνημα στο σπίτι για να το κάνω compile.

 

Λοιπόν το πρόγραμμα σε vb ειναι το παρακάτω. Έκανα και exe αλλά σημειώνω ότι δεν βγάζει σωστά αποτελέσματα, τρώει κάποιες λέξεις και εμφανίζει ίδιες. Το περίεργο είναι ότι ο ίδιος ακριβώς κώδικας στην php τρέχει μια χαρά.

Anagrams VB.zip

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

Χωρίς compiler και χωρίς VB Studio δυσκολεύομαι. Ωστόσο, μόνο και μόνο η αλλαγή από for...next σε do..while προκαλεί πρόβλημα. Το for..next θα εκτελέσει το loop μόνο αν ισχύει η συνθήκε ενώ η do..while θα το εκτελέσει οπωσδήποτε μια φορά. Άλλαξέ το σε while..wend loop.

[dimulator]

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

 

ο κώδικας είναι ο εξής

 

Private Sub Command1_Click()

Dim iLen As Integer                     'Set word length

iLen = Len(Text1.Text)                  'Get word length
ReDim sArray(iLen) As String            'Set an array with elements as many are letters of word

For i = 0 To iLen                       'Split word into letters and put every letter in array
sArray(i) = Mid(Text1.Text, i + 1, 1)
Next

Text2.Text = ""                         'Reset and clear output textbox to be ready to get new results

Call anag(0, iLen, sArray())            'Make anagrams

End Sub

-------------------------------------------------------------------------------------------

Private Function anag(iStart As Integer, iLen As Integer, sArray() As String)

'Port code from phpAG

'FIXME H synartisi enw einai idia me ayth tou phpAG den douleuei gia kapoio logo
'dokimase leksi me tria grammata gia na deis ti kanei p.x. abc

   If iStart < iLen Then
       j = iStart
       While (j < iLen)

           If j = iStart Or sArray(j) <> sArray(iStart) Then
               tmp = sArray(j)
               sArray(j) = sArray(iStart)
               sArray(iStart) = tmp
               Call anag((iStart + 1), iLen, sArray())
           End If

       j = j + 1
       Wend
   Else
       word = implode(sArray())
       Text2.Text = Text2.Text & word & vbNewLine

 End If


'H synartisi anag toy phpAG einai h akolou8i

'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);
'            }
'        }
'*/

'O parapanw kwdikas pou einai se sxolia einai o idios me ton parakatw
'dokimasmenos kai douleuei
'o logos allaghs einai dioti sthn VB den einai idia h syntaxi to for...next opote eprepe na ginei do...while

'        $j = $start;
'        Do
'        {
'            if ($j == $start || $array[$j] != $array[$start])
'            {
'                $tmp = $array[$j];
'                $array[$j] = $array[$start];
'                $array[$start] = $tmp;
'                anag ($array, $start+1, $len);
'            }
'
'            $j++;
'        } while ( $j < $len );
'
'
'    }
'    Else
'    {
'        $word = implode ("", $array);
'        $i = ++$i;
'        echo "$i) $word<br>";
'//      printf ("%'.-20d%'.20s%s", $i, ucfirst ($word), "<BR>\n");
'    }
'}



End Function

-------------------------------------------------------------------------------------------


Private Function implode(sArray() As String) As String
'This function makes a string from the elements of a string array

For i = 0 To UBound(sArray)
word = word & sArray(i)
Next

implode = word
End Function

Edited November 8, 2009 by dimulator