Diskuze: Anagramy

Jozef

Člen

Jozef:14.7.2015 18:57

Zdravím,
potreboval by som pomôcť zistiť, akú chybu mám v programe. Najprv prikladám zadanie úlohy:

Two words are said to be anagrams of each other if the letters from one word can be rearranged to form the other word. For example, occurs is an anagram of succor; however, dear is not an anagram of dared (because the d appears twice in dared, but only once in dear). The most famous anagram pair (in English) is dog and god.

The anagrammatic distance between any two words is the minimum number of letters which must be removed so that the remaining portions of the two words become anagrams. For example, given the words sleep and leap, we need to remove a minimum of three letters – two from sleep and one from leap – before what's left are anagrams of each other (in each case, lep). With words such as dog and cat, where the two have absolutely no letters in common, the anagrammatic distance is an extreme (explicitly 6) since all the letters need to be removed. (Here, a word is always an anagram of itself.)

You must write a program to calculate the anagrammatic distance between any two given words.

Input

The first line of the input will contain a positive integer value N (less than 60,000) indicating the number of cases. Each case will consist of two words, possibly empty, each given on a single line (for a total of 2N additional lines).

Although they may have zero length, the words are simple – the letter are all lowercase and are taken from the usual twenty-six letter English alphabet (abcdefghijklmnopqrstuvwxyz). The longest word is pneumonoultramicroscopicsilicovolcanoconiosis.

Output

The output should consist of the case number and the anagrammatic distance, formatted as shown.

Example

input

4
crocus
succor
dares
seared
empty

smell
lemon

output

Case #1: 0
Case #2: 1
Case #3: 5
Case #4: 4

Prikladám svoj zdroják. Mojou hlavnou myšlienkou je vytvoriť zoznam početností jednotlivých písmen
v oboch slovách a potom odčítaním každej početnosti jednotlivých písmen(v absolútnej hodnote) mi vyjde
celkový počet písmen, ktoré treba odobrať, aby vznikol anagram. Problém je, že pre prvé 2 vstupné testy mi môj kód funguje, avšak pri treťom teste vyhodí Wrong Answer. Vedel by mi niekto povedať, prečo to nefunguje? Lebo základná myšlienka je(aspoň podľa mňa) správna.
Vďaka.

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

int main()
{
  int alphabet[2][26];     //zoznam početností jednotlivých písmen
  int i,j,n,index,result;
  char *string;
  string = (char *)malloc(100*sizeof(char));
  scanf("%d ",&n);
  for(int k = 0; k < n; k++){
    result = 0;                          //vynulovanie výsledku
    for(j = 0; j < 2; j++)             //vloženie 0 do polí
        for(i = 0; i < 26; i++)
            alphabet[j][i] = 0;
    fgets(string,100,stdin);       //načítanie 1. slova
    for(i = 0;i < strlen(string); i++){   //zvyšovanie početností jednotlivých písmen
        index = string[i] - 'a';             //index získam odčítaním 'a' od jednotlivých písmen
        alphabet[0][index]++;
    }
    fgets(string,100,stdin);            // to isté pre druhé slovo
    for(i = 0;i < strlen(string); i++){
        index = string[i] - 'a';
        alphabet[1][index]++;
    }
    for(i = 0; i < 26; i++){             //k výsledku pripočítam absolútnu hodnotu odčítaním početností písmen
        result += abs(alphabet[0][i] - alphabet[1][i]);
    }
    printf("Case #%d: %d\n",k+1,vysledok);
  }
  return 0;
}

Odpovědět

14.7.2015 18:57

I'm not afraid to die on a treadmill

caller

Člen

caller:14.7.2015 21:02

Zdravím, nevím proč ti to nefunguje, každopádně jsem ten kód zkopíroval, spustil, zadal input z toho příkladu a výsledky byly stejné, takže se to zdá být funkční. Tedy až na to že ten printf, který se volá po zadání každého páru a ne až po zadání N párů jako je to v ukázkovém příkladu, ale to je jen estetický detail. Jediné co mě napadá jako chyba je, že v printf používáš proměnnou vysledek, která neexistuje, měla by tam být proměnná "result", ale hádám že jsi se jen přepsal, protože jinak by ti to nejspíš nefungovalo vůbec.

Nahoru Odpovědět

14.7.2015 21:02

Jozef

Člen

Jozef:14.7.2015 22:42

veď práve, tiež neviem prečo to nefunguje, či je chyba v testovači alebo ako...
Máš pravdu, s tým výsledkom som sa prepísal, lebo som to upravoval na anglické výrazy a sem som to vložil ešte neupravené úplne.
Pre prvé 2 testové vstupy mi to funguje, potom pri treťom už nie. Možno je celá moja základná myšlienka zlá, ale podľa mňa by mala byť správna, pretože úlohou v podstate je, aby obe slová obsahovali rovnaké písmená --> teda v mojom prípade aby v každom jednom poli bolo rovnaké číslo. A absolútna hodnota odčítanie čísel je teoreticky ich vzdialenosť na číselnej osi, či? Takže o tú vzdialenosť by sa malo buď zväčšiť alebo zmenšiť.

Nahoru Odpovědět

14.7.2015 22:42

I'm not afraid to die on a treadmill

coells

Tvůrce

coells:15.7.2015 0:15

Nechtěně zapisuješ mimo vyhrazenou paměť a přepisuješ si jinou proměnnou.
<string> obsahuje newline character, takže první cyklus zapisuje na zápornou pozici histogramu.

Tohle je typické chování, pokud si přepisuješ vlastní paměť, program nespadne, ale chová se pokaždé jinak.
Vítej ve světě C-ckařů.

Akceptované řešení
+20 Zkušeností
+2,50 Kč

Nahoru Odpovědět

15.7.2015 0:15

Jozef

Člen

Jozef:15.7.2015 0:40

Mal si pravdu, po úprave tejto časti kódu:

scanf("%d ",&n);

na toto:

char *pomoc;
pomoc = (char *)malloc(100*sizeof(char));
n = atoi(fgets(pomoc,100,stdin));

Problém bol teda zrejme v tom, že scanf("%d ",&n) zanechalo prebytočný znak nového riadku, ktorý potom spôsobil prepísanie určitej časti pamäte? Alebo ako to presne funguje? Ak by si mi to mohol presnejšie priblížiť, bol by som ti vďačný. Lebo pre všetky moje vstupy,čo som skúšal, to dávalo správne výsledky, iba v testovači to na konkrétnom mieste spadlo. Prečo to vždy prestalo fungovať na určitom konkrétnom mieste, keď dovtedy program funguje v poriadku?

Nahoru Odpovědět

15.7.2015 0:40

I'm not afraid to die on a treadmill

coells

Tvůrce

coells:15.7.2015 0:48

Z dokumentace fgets():

Parsing stops if end-of-file occurs or a newline character is found, in which case str will contain that newline character.

Takže proměnná string obsahuje "crocus\n" a "succor\n".
Při zápisu do histogramu inkrementuješ pozici ('\n' - 'a') = -87

U sebe v debug módu to nepoznáš, protože proměnné jsou v paměti sestaveny opatrně, ale pokud kompilátoru nastavíš optimalizace, což je zřejmě případ testovače, bude se to chovat divně nebo padat.

Nahoru Odpovědět

15.7.2015 0:48

Jozef

Člen

Jozef:15.7.2015 0:56

takže scanf() teda po sebe vždy zanecháva newline character?
Kedysi som to podobný problém riešil týmto:

fflush(stdin);

avšak pri použití tohoto sú všetky odpovede pri testovaní posunuté

Nahoru Odpovědět

15.7.2015 0:56

I'm not afraid to die on a treadmill

coells

Tvůrce

coells:15.7.2015 1:03

:-)) Tak ještě jednou, funkce fgets() čte ze vstupu, dokud nenajde new-line nebo end-of-file.
Pokud najde new-line, bude ho výsledný řetězec obsahovat.

Problém je v tomhle cyklu:

for(i = 0;i < strlen(string); i++){   //zvyšovanie početností jednotlivých písmen
        index = string[i] - 'a';             //index získam odčítaním 'a' od jednotlivých písmen
        alphabet[0][index]++;
    }

Řešení:

for (char *p = string; *p >= 'a' && *p <= 'z'; p++)
    alphabet[0][*p - 'a']++;

Nahoru Odpovědět

15.7.2015 1:03

Jozef

Člen

Jozef:15.7.2015 1:07

Ja som už vyššie písal,že zmena

scanf("%d ",&n);

na

char *pomoc;
pomoc = (char *)malloc(100*sizeof(char));
n = atoi(fgets(pomoc,100,stdin));

pomohla, už mi to funguje. Ostatné časti som nechal nezmenené, takže zostal aj cyklus

for(i = 0;i < strlen(string); i++){   //zvyšovanie početností jednotlivých písmen
        index = string[i] - 'a';             //index získam odčítaním 'a' od jednotlivých písmen
        alphabet[0][index]++;
    }

a kód funguje.

Nahoru Odpovědět

15.7.2015 1:07

I'm not afraid to die on a treadmill

coells

Tvůrce

coells:15.7.2015 1:10

Kód nefunguje, jenom jsi měl štěstí díky změně struktury alokované paměti. Stále zapisuješ někam, kam nemáš, ale tentokrát se to tváří, že je to v pořádku. Vezmi jiný kompilátor nebo zapni -O3 optimalizace a uvidíš, jestli to pořád bude fungovat.

Nahoru Odpovědět

15.7.2015 1:10

Jozef

Člen

Jozef:15.7.2015 1:16

Aha, takže stále je kód zlý. No na mieste kde predtým v testovači padal už teraz funguje bez problémov, tak som myslel, že sa to tým opravilo.

Nahoru Odpovědět

15.7.2015 1:16

I'm not afraid to die on a treadmill

coells

Tvůrce

coells:15.7.2015 11:58

To je jednoduché, jak už jsi psal na začátku, myšlenka řešení je správná.
Kód také vypadá správně, sice to není moc Cčko, ale budiž, žádná do očí bijící chyba tam není.

Takže kde je problém?
Oblíbeným místem bývá indexování pole, zvlášť, když indexuješ na základě neošetřeného vstupu.

Zkus tenhle kus kódu

for(i = 0;i < strlen(string); i++){   //zvyšovanie početností jednotlivých písmen
    index = string[i] - 'a';             //index získam odčítaním 'a' od jednotlivých písmen
    alphabet[0][index]++;
}

Nahradit tímhle kódem

void inc_array(int *hist, i) {
    if (i < 0 || i >= 26) {
        printf("invalid index %d", i);
        exit();
    }
    hist[i]++;
}

    for(i = 0;i < strlen(string); i++){
        index = string[i] - 'a';
        inc_array(alphabet[0], index);
    }

Nahoru Odpovědět

15.7.2015 11:58

Jozef

Člen

Jozef:15.7.2015 21:06

Aha vďaka, už mi je to jasnejšie, ale presne nechápem, prečo potom tento kód, ktorý si navrhoval:

for (char *p = string; *p >= 'a' && *p <= 'z'; p++)
    alphabet[0][*p - 'a']++;

už so zápisom mimo vyhradenej pamäte nemá problém?
A ešte jednu otázku, ak smiem otravovať, kedže si písal,

sice to není moc Cčko

ako by to malo byť?

Nahoru Odpovědět

15.7.2015 21:06

I'm not afraid to die on a treadmill

coells

Tvůrce

coells:15.7.2015 22:07

Jazyku C nesluší, když se moc rozepisuješ, programy musí být krátké a vyplatí se šetřit.

Když napíšeš...

for(i = 0;i < strlen(string); i++){
        index = string[i] - 'a';
        inc_array(alphabet[0], index);
}

... tak se v jedné každé iteraci zavolá strlen(), která projde celý řetězec od začátku do konce a vrátí ti jeho délku. A vzhledem k tomu, že chceš projít celý řetězec, tak je to zbytečné. Korektní kód v C, který dělá to samé, vypadá takhle:

for (char *pc = string; *pc; pc++)
    alphabet[0][*pc - 'a']++;

A vzhledem k tomu, že navíc chceš kontrolovat obsah řetězce kvůli nepovoleným znakům, můžeš nahradit podmínku na ukončení podmínkou na nevyhovující znak, takže můj kód opravdu mimo pole nezapisuje.

for (char *pc = string; *pc >= 'a' && *pc <= 'z'; pc++)
    alphabet[0][*pc - 'a']++;

Také mít dvě pole, alphabet[0] a alphabet[1], je zbytečné.
Zkus vymyslet, jak bys mohl histogramy pro obě slova dát do jednoho pole?
Na konstanty používej konstantní proměnné nebo definice, samotná čísla 100 a 26 by se měly v programu objevit pouze jednou.

Ve výsledku ti ve tvém kódu zmizí několik řádek a kód se hezky pročistí.

Nahoru Odpovědět

15.7.2015 22:07

Jozef

Člen

Jozef:15.7.2015 22:14

Vďaka za rady

Nahoru Odpovědět

15.7.2015 22:14

I'm not afraid to die on a treadmill

Jozef

Člen

Jozef:15.7.2015 22:26

Takže ten kód by mal vyzerať približne takto?

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

#define SIZE 26
#define LIMIT 100

int main()
{
  int alphabet[SIZE];
  int result = 0;
  int i,n;
  char *string,*pomoc;
  string = (char *)malloc(LIMIT*sizeof(char));
  pomoc = (char *)malloc(LIMIT*sizeof(char));
  n = atoi(fgets(pomoc,LIMIT,stdin));
  for(int k = 0; k < n; k++){
    result = 0;
    for(i = 0; i < SIZE; i++)
        alphabet[i] = 0;
    fgets(string,LIMIT,stdin);
    for (char *p = string; *p >= 'a' && *p <= 'z'; p++)
        alphabet[*p - 'a']++;
    fgets(string,LIMIT,stdin);
    for (char *pc = string; *pc >= 'a' && *pc <= 'z'; pc++)
         alphabet[*pc - 'a']--;
    for(i = 0; i < SIZE; i++){
        result += abs(alphabet[i]);
    }
    printf("Case #%d: %d\n",k+1,result);
  }
  return 0;
}

Nahoru Odpovědět

15.7.2015 22:26

I'm not afraid to die on a treadmill

coells

Tvůrce

coells:15.7.2015 22:55

Ještě kosmetické úpravy:
1/ dej pryč proměnnou pomoc, kterou nepotřebuješ
2/ definice SIZE a LIMIT pojmenuj tak, abys rozeznal, k čemu jsou
3/ pro každé volání malloc() dávej automaticky free()

Jinak tohle už vypadá velice slušně.

Nahoru Odpovědět

15.7.2015 22:55