Project Euler

[migf1]

Παιδιά, καταλαβαίνει κάποιος τι ρωτάει το 13ο πρόβλημα του Euler;
http://projecteuler.net/index.php?secti ... lems&id=13

EDIT: Μάλλον κατάλαβα, θέλει να αθροιστούν οι 100 αυτοί αριθμοί και να επιστρέψουμε μετά τα 10 πρώτα ψηφία του αθροίσματος, ε;

[Ilias95]

Παιδιά, καταλαβαίνει κάποιος τι ρωτάει το 13ο πρόβλημα του Euler;
http://projecteuler.net/index.php?secti ... lems&id=13

EDIT: Μάλλον κατάλαβα, θέλει να αθροιστούν οι 100 αυτοί αριθμοί και να επιστρέψουμε μετά τα 10 πρώτα ψηφία του αθροίσματος, ε;

Και 'γω αυτό καταλαβαίνω...
Αλλά βρίσκω ότι το άθροισμα έχει 5 ψηφία... :S Εκτός αν έχω κάνει κάποιο λάθος...

[Ilias95]

Άκυρο! Τελικά λάθος κατάλαβα και γι' αυτό είχα λάθος αποτέλεσμα!
Αρχικά νόμιζα ότι ήταν όλο μαζί ένας αριθμός και έπρεπε να αθροίσουμε τα ψηφία του.
Αλλά τελικά είναι 50 αριθμοί των οποίων το άθροισμα πρέπει να βρεις.

Edit: Χαζό πρόβλημα μου φαίνεται πάντως...

[migf1]

Εγώ έχω πιάσει στο 20 αλλά ενώ αλγοριθμικά το έχω λύσει, αντιμετωπίζω πρόβλημα με το floating precision της στάνταρ βιβλιοθήκης math (και δεν θέλω να χρησιμοποιήσω advanced βιβλιοθήκη).

[Ilias95]

Από C δεν έχω ιδέα ακόμα αλλά στην python αυτό που έκανα ήταν:

Problem 13: Find the first ten digits of the sum of one-hundred 50-digit numbers.

Spoiler: show

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

numbers = [num1, num2.....]
sum = 0
for number in numbers:
sum += number
sum = str(sum)
print(sum[:10])

[migf1]

Από C δεν έχω ιδέα ακόμα...

Άσε, ξενέρωσα τώρα!

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

http://sputsoft.com/blog/2009/07/implem ... art-1.html
http://sputsoft.com/blog/2009/08/implem ... art-2.html

http://en.wikipedia.org/wiki/Arbitrary- ... arithmetic

[Ilias95]

Από C δεν έχω ιδέα ακόμα...

Άσε, ξενέρωσα τώρα!

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

Ή υπάρχει και άλλη λύση:

Programming is fun
When the work is done
if you wanna make your work also fun:
use Python!

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

[migf1]

Βασικά, με χρήση της gmplib (η advanced μαθηματική βιβλιοθήκη της GNU) είναι 4-5 γραμμές κώδικα όλο κι όλο, αλλά δεν έτσι δεν είναι... fun

Τέσπα, νομίζω βρήκα τρόπο να το κάνω χρησιμοποιώντας πίνακα για να κρατάω ενδιάμεσα αποτελέσματα του / 10 και του % 10, αλλά σπάστηκα και το παρατάω!!

[migf1]

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.

What is the total of all the name scores in the file?

Η λύση μου σε C...

Spoiler: show

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


#include <stdio.h>
#include <string.h> // for strncmp
#include <stdlib.h> // for calloc(), free()

#define MAX_WLEN 100
#define LETTVAL(c) ((c)-'A'+1)

typedef enum { FALSE=0, TRUE } Bool;

typedef struct node {
char word[ MAX_WLEN ]; // the word
struct node *next; // pointer to next node
} Node;

typedef struct {
Node *head, *tail; // pointers to 1st & last nodes
long int len; // UNUSED
} List;

// ------------------------------------------------------------------------------------
char *s_ncopy( char *dst, const char *src, int n )
{
char *ret = dst;
while ( (dst-ret) < n-1 && (*dst=*src) != '\0' )
dst++, src++;

if ( *dst )
*dst = 0;

return ret;
}
// ------------------------------------------------------------------------------------
Bool list_putascend( List *list, char *data )
{
Node *curr = NULL, *prev = NULL;
Node *new = calloc( 1, sizeof(struct node) );
if ( !new || !data ) // calloc failed or invalid data
return FALSE;

s_ncopy(new->word, data, MAX_WLEN); // initialize newly created node
new->next = NULL; // ...

if ( list->head == NULL) { // list was empty, direct insertion
list->head = list->tail = new;
(list->len)++;
return TRUE;
}
// direct append
if ( strncmp(data, list->tail->word, MAX_WLEN ) >= 0 ) {
list->tail->next = new;
list->tail = new;
(list->len)++;
return TRUE;
}

curr = prev = list->head; // general case (traversing)
// find spot for the insertion
while ( curr && strncmp(curr->word, data, MAX_WLEN) <= 0 )
{ // use <= data, to allow duplicates
prev = curr; // save previous node
curr = curr->next;
}

// insert BEFORE 1st node
if ( list->head == curr /* && curr->data != data */ ) {
list->head = new;
new->next = curr;
(list->len)++;
return TRUE;
}
// insert AFTER 1st node
if ( !curr || strncmp(curr->word, data, MAX_WLEN) != 0 ) {
prev->next = new;
new->next = curr;
}
(list->len)++;

return TRUE;
}
// ------------------------------------------------------------------------------------
void list_destroy( List *list )
{
if ( list->head == NULL )
return;

Node *dummy = NULL;
while ( list->head ) {
dummy = list->head->next;
free( list->head );
list->head = dummy;
}

return;
}
// ------------------------------------------------------------------------------------
Bool get_fcontents( const char *fname, const char *delims, List *list )
{
FILE *fp = fopen(fname, "r");
char s[ MAX_WLEN ] = {0}; // important! filling up with 0s

if ( !fp || !list) // fopen error or invalid list
return FALSE;

while ( !feof(fp) )
{
fscanf (fp, delims, s); // read next clean word
if ( !list_putascend( list, s) ) { // if insertion to list fails
fclose( fp ); // cleanup & return error
return FALSE;
}
}
fclose( fp );

return TRUE;
}

// ------------------------------------------------------------------------------------
int main( void )
{
List list = {.head=NULL, .tail=NULL, .len=0L}; // linked list for sorted words
Node *pnode = NULL; // for traversing the list
long int i, score = 0; // node counter & total score

// read file contents into list, in ascending order
get_fcontents( "names.txt", "\"%[a-zA-Z]\",", &list );

// calc the total score
for (i=0, pnode = list.head; pnode; i++ )
{
int wscore = 0; // individual word score
char *cp = pnode->word; // for traversing a word
while ( *cp ) // calc individual score
wscore += LETTVAL( *cp++ );
score += (i+1) * wscore;
pnode = pnode->next;
}

printf("%ld\n", score ); // print the total score
list_destroy( &list ); // free mem reserved for list

exit( EXIT_SUCCESS );
}


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

Θα πάω σπίτι να δω μήπως μπορώ να σινιάρω καθόλου τον κώδικα και να τον ανεβάσω και στο ideone.com.

ΥΓ. Είδα λύση σε Python σε 3 γραμμές !!!!!!!! (χρησιμοποιούσε lamdas) και κόντεψα να βάλω τα κλάμματα

[migf1]

...
Θα πάω σπίτι να δω μήπως μπορώ να σινιάρω καθόλου τον κώδικα και να τον ανεβάσω και στο ideone.com.
...

Λοιπόν, 2 υλοποιήσεις:

1. με περισσότερες συναρτήσεις: http://ideone.com/4vH8q
2. με λιγότερες συναρτήσεις: http://ideone.com/t1Mcv