Angella Andrea - Italian Blog

Infinita passione per lo sviluppo software !
posts - 133, comments - 216, trackbacks - 9

My Links

News

MIT OpenCourseWare: I'm invested Wikipedia Affiliate Button


Sto leggendo:

Archives

Post Categories

Siti web realizzati

Siti web tecnici

Algoritmi – Determinare dal testo di una rivista se e’ possibile creare una ransom note


Problema 1:

Fino ad ora non sapevo cosa fosse una ransom note.
Praticamente si tratta di un testo realizzato utilizzando ritagli da una rivista.

ransom note

Dato il testo di una ransom note e il testo della rivista, dire se e’ possibile realizzare la ransom note.

Problema 2:

Risolvere lo stesso problema ma ritagliando parole invece che singoli caratteri.

Input:

Testo della ransom note che si vuole creare (stringa).
Testo della rivista da cui si vuole ritagliare (stringa).

Output:

True se e’ possibile realizzare la ransom note, False altrimenti.

Il mio ragionamento:

Scansiono due volte i testi e costruisco due vettori che conteggiano il numero di occorrenze di ciasun carattere. Fatto questo controllo che ci sia sempre un numero sufficiente di lettere per costruire la ransom note confrontando uno ad uno gli elementi corrispondenti di questi due array.

Per quanto riguarda il problema 2 invece di utilizzare due vettori, utilizzo due tabelle hash. La logica e’ sostanzialmente la stessa.

Le mie soluzioni:

public static bool IsCharacterRansomNotePossible(string noteText, string magazineText)
{
    if (String.IsNullOrEmpty(noteText) || String.IsNullOrEmpty(magazineText))
        throw new ArgumentException("noteText and/or magazineText cannot be null or empty");

    const int N = Char.MaxValue + 1;
    
    uint[] noteCount = new uint[N];
    uint[] magazineCount = new uint[N];

    foreach (char c in noteText) ++noteCount[c];            
    foreach (char c in magazineText) ++magazineCount[c];

    for (int i = 0; i < N; ++i)
        if (noteCount[i] > magazineCount[i])
            if(!char.IsWhiteSpace((char)i))
                return false;

    return true;
}

public static bool IsWordRansomNotePossible(string noteText, string magazineText)
{
    if (String.IsNullOrEmpty(noteText) || String.IsNullOrEmpty(magazineText))
        throw new ArgumentException("noteText and/or magazineText cannot be null or empty");

    var noteCount = new Dictionary<string, int>();
    var magazineCount = new Dictionary<string, int>();

    var noteWords = noteText.Split();
    var magazineWords = magazineText.Split();

    foreach (string s in noteWords)
        if (noteCount.ContainsKey(s)) ++noteCount[s];
        else noteCount[s] = 1;

    foreach (string s in magazineWords)
        if (magazineCount.ContainsKey(s)) ++magazineCount[s];
        else magazineCount[s] = 1;

    foreach (string word in noteCount.Keys)
        if (!magazineCount.ContainsKey(word) || noteCount[word] > magazineCount[word])
            return false;

    return true;
}


Qualunque commento e’ ben accetto. Il codice non e’ stato testato rigorosamente.

Soluzione di Ludovico Van:

public static bool IsCharRansomNotePossible(string note, string source)
{
    note = note == null ? string.Empty : note.Trim();
    source = source == null ? string.Empty : source.Trim();

    if (note.Length == 0)
        return true;

    int[] charCounts = new int[1 + char.MaxValue];

    int charSetCount = 0;

    foreach (char ch in note)
        if (!char.IsWhiteSpace(ch))
            if (charCounts[ch]++ == 0)
                ++charSetCount;

    foreach (char ch in source)
        if (charCounts[ch] != 0)
            if (--charCounts[ch] == 0)
                if (--charSetCount == 0)
                    return true;

    return false;
}

Print | posted on Thursday, September 2, 2010 12:51 AM | Filed Under [ Algoritmica ]

Feedback

Gravatar

# re: Algoritmi – Determinare dal testo di una rivista se e’ possibile creare una ransom note

Personalmente avrei usato il metodo "seek & destroy", ovvero le funzioni string.IndexOf e string.Remove per trovare ogni carattero o parola del parametro noteText in magazineText.
Una finezza potrebbe essere la verifica della lunghezza delle due stringa in testa alle funzioni: se magazineText è più corta di noteText non vale la pena continuare.
9/2/2010 11:58 AM | Marco
Gravatar

# re: Algoritmi – Determinare dal testo di una rivista se e’ possibile creare una ransom note

Nel codice che ho incollato sopra mancano un paio di graffe... comunque il risultato cambia di poco.

Questo e' un benchmark fino a 100,000 caratteri:

[0] len = 54 / 449, iter = 1000, elapsed = 28 ms
[1] len = 54 / 449, iter = 1000, elapsed = 305 ms
[2] len = 54 / 449, iter = 1000, elapsed = 294 ms
[3] len = 54 / 449, iter = 1000, elapsed = 1070 ms

[0] len = 1998 / 16613, iter = 400, elapsed = 340 ms
[1] len = 1998 / 16613, iter = 400, elapsed = 278 ms
[2] len = 1998 / 16613, iter = 400, elapsed = 254 ms
[3] len = 1998 / 16613, iter = 400, elapsed = 584 ms

[0] len = 101898 / 847263, iter = 500, elapsed = 22075 ms
[1] len = 101898 / 847263, iter = 500, elapsed = 10400 ms
[2] len = 101898 / 847263, iter = 500, elapsed = 8296 ms
[3] len = 101898 / 847263, iter = 500, elapsed = 9140 ms

E adesso davvero buonanotte... :)

-LV
9/3/2010 4:55 AM | LudovicoVan
Gravatar

# re: Algoritmi – Determinare dal testo di una rivista se e’ possibile creare una ransom note

Qui la migliore e' la numero 4, che e' la 2 facendo l'allocazione prima. La tua con allocazione prima e' la 5.

[0] len = 54 / 449, iter = 1000, elapsed = 30 ms
[1] len = 54 / 449, iter = 1000, elapsed = 376 ms
[2] len = 54 / 449, iter = 1000, elapsed = 367 ms
[3] len = 54 / 449, iter = 1000, elapsed = 1384 ms
[4] len = 54 / 449, iter = 1000, elapsed = 5 ms
[5] len = 54 / 449, iter = 1000, elapsed = 514 ms

[0] len = 1998 / 16613, iter = 400, elapsed = 340 ms
[1] len = 1998 / 16613, iter = 400, elapsed = 312 ms
[2] len = 1998 / 16613, iter = 400, elapsed = 275 ms
[3] len = 1998 / 16613, iter = 400, elapsed = 698 ms
[4] len = 1998 / 16613, iter = 400, elapsed = 126 ms
[5] len = 1998 / 16613, iter = 400, elapsed = 324 ms

[0] len = 41958 / 348873, iter = 500, elapsed = 9129 ms
[1] len = 41958 / 348873, iter = 500, elapsed = 4486 ms
[2] len = 41958 / 348873, iter = 500, elapsed = 3631 ms
[3] len = 41958 / 348873, iter = 500, elapsed = 4364 ms
[4] len = 41958 / 348873, iter = 500, elapsed = 3408 ms
[5] len = 41958 / 348873, iter = 500, elapsed = 3847 ms

-LV
9/3/2010 5:20 AM | LudovicoVan
Comments have been closed on this topic.

Powered by:
Powered By Subtext Powered By ASP.NET