Telerik Academy Alpha Exam: Spell Caster Problem Solution


1

Здравейте приятели и нинджи,

Моля някои от успелите да решат задачата  "Spell Caster" (http://bgcoder.com/Contests/Practice/DownloadResource/1885)от изпита за Алфа академията да обясни как и защо така я е решил. По конкретно как става накрая преобразуването на стринговете (часта която да преместиш буквата по индекс). Благодаря предварително




Отговори



2

Здравей колега,

понеже не искам да отнемам от радостта и удовлетворението след решена задача, ще ти дам само насока за решението на задачата.

След като си стигнал до стринга, чийто букви трябва да бъдат преместени (от "Fun exam right" си стигнал до "nmtuahFxgei") трябва последователно, за всеки индекс, да изчислиш новия индекс, на който трябва да застане буквата от индекса (това означава, че може да има букви, които въобще не местиш и такива, които местиш по няколко пъти). За целта първо взимаш позицията на буквата в английската азбуката (напр. "n"="N"=14). След това изчисляваш новия индекс като тук трябва да намериш зависимост на новия индекс според стария индекс, позицията на буквата от индекса в азбуката и дължината на цялата дума - разгледай всяко от примерните преместванията внимателно (втората страница от описанието на задачата): 

"nmtuahFxgeir" има дължина 12.
На нулевия индекс от стринга имаш "n".
"n" e 14тата буква в английската азбуката.
Виждаш, че в техния пример новия индекс на "n" е 2 ("nmtuahFxgeir" => "mtnuahFxgeir").

"mtnuahFxgeir" има дължина 12.
На първия индекс от стринга имаш "t".
"t" e 20тата буква в английската азбука.
Виждаш, че в техния пример новия индекс на "t" е 9 ("mtnuahFxgeir" => "mnuahFxgetir").

и т.н.

Самото местене би станало най-чисто в нова функция:

string MoveLetterFromIndexXToIndexY(string str, int x, int y) {...}

която извикваш n пъти (с x = 0, x = 1, ...), винаги с актуалния, ъпдейтнат, получен стринг и изчислен, "нов" индекс y за буквата от индекс x в str.

Тук също трябва да си доста внимателен и трябва да си представиш какво става при местенето на дадена буква от индекс.

Отново ще илюстрирам с примери, а ти трябва да намериш зависимостта на отговора, спрямо другото инфо. Подсказвам, че трябва да разгледаш 2 случая - (x <= y и x > y):

Представи си, че извикваш функцията със следните аргументи:
str = "string", x = 2, y = 4
Отговора, който очакваш е "stinrg". Забележи, че буквите от индекси i < x, y остават непроменени.

str = "string", x = 4, y = 2
Отговора, който очакваш е "stnrig". Отново, буквите от индекси i < x, y остават непроменени.

Тоест ти остава само да видиш какво става във всеки от случаите (как се променя резултата) x <= y и x > y за индексите
i >= x, y.

И реално си готов. Остава само в един for цикъл да минеш един път по дължината на целия стринг и за всеки индекс да изчислиш:
1.) номера на буквата от индекса в английската азбука
2.) новия индекс, на който трябва да преместиш буквата

след това да преместиш буквата от индекса на новия индекс (извиквайки функцията, която си имплементирал) и да повториш цялото упражение n пъти (не забравяй, че трябва да използваш новополучения стринг всеки път).

Ако не се справяш и ти трябва още помощ - пиши! :)


от ggeorgievx (55 точки)


1

Благодаря ти за подробния отговор колега оценявам, че си отделил време да напишеш толко подробно обяснение. За повечето неща се сетих по време на изпита, но все не ми достигаше да го доизмисля този меджик метод MoveLetterFromIndexToIndex.  

Стигам до там имам индекс позиция на буквата в стринга и индекс къде трябва да отиде => След това блокаж.

Опитах да режа стрингове и след това добавям буквата и събирам сринговете, String.Insert след това String.Remove, Побитово сменях стойноста на буквата и още няколко неща когато бях забил 1 час на тази стъпка...

Все още немога да го измисля: хубаво премествам буквата на новата позиция но проблема идва от там, че когато я преместя ми набърква следващата буква след новата позиция, която трябва да застане преди вмъкването а тя остава след него.

Моля пиши решение на тази стъпка че вече губя увереност мозака ми е блокирал като я видя задачата и си казвам "Немога да я реша".


от tobeone (10 точки)

1

Здравей отново,

не съжалявай, че си прекарал толкова време опитвайки се да я решиш - сигурен съм, че си научил много нови неща. Точно затова в първия ми отговор не ти пратих директно решението.

Ето примерно решение за местенето на буквите от индекс на друг индекс (опитал съм с коментари в кода да разясня какво се случва):

/* input: str: стринга, чийто букви разместваме x: позицията на буквата, която искаме да преместим у: позицията, на която искаме да преместим буквата output: res: първоначалния стринг с преместена буква от позиция x на позиция y (пример: "string", 2, 4 => "stinrg") */ static string MoveLetterFromIndexXToIndexY(string str, int x, int y) { string res = ""; //стринг, в който "построяваме" отговора int i = 0; //i ще следи индекса, до който сме стигнали - забележи, че го декларирам преди for-цикъла, за да е достъпно и след това for (; ((i < x) && (i < y)); i++) { res += str[i]; } //минаваме по input стринга до i < x && i < y понеже нямаме промяна за тези букви и остават така - директно ги "копираме" в res if (x <= y) { //първия случай int l; // използваме l вместо i понеже имаме два случая и искаме i да има същата стойност и при втория слчай for (l = i + 1; (l <= y) && (l < str.Length); l++) { res += str[l]; } //прескачаме индекса x и копираме всичко след това докато не стигнем позиция y res += str[x]; //добавяме индекса x на позиция y for (; l < str.Length; l++) { res += str[l]; } //довършваме "копирането" } if (x > y) { //втория случай int l; res += str[x]; //понеже сме стигнали до позиция y, на която трябва да дойде буквата от индекс x - "копираме" я for (l = i; l < str.Length; l++) { if (l == x) { continue; } res += str[l]; } //"копираме" всичко останало след y, като внимаваме да не "копираме" буквата от индекс x още веднъж } return res; //връщаме "новопостроения" стринг }


Успех!


от ggeorgievx (55 точки)


1

Здравейте,
Ето и моето решение:
Стъпка 1:
1.1 За инпута използваме .Split() метода, за да не броим спейсовете.
1.2 Намираме дължината на най-дългата дума от инпута.
1.3 Екстрактването:
1.3.1 Два вложени цикъла (външният за буквите, а вътрешният за думите)
1.3.2 Външният цикъл върти до дължината на най-дългата дума, 
а вътрешният до дължината на инпута.
1.3.3 При условие,че индекса на вънщния цикъл е в рамките на настоящата
дума от вътрешния цикъл, записваме съответната буква към празен стринг.

Стъпка 2:
2.1 Резултата(стринга), който сме получили от 1.3.3 го превръщаме в
масив от чарове.
2.2 Местенето на буквите в масива:
2.2.1 Правим цикъл за всеки индекс от масива от чарове
2.2.2 Намираме новата позиция на буквата от съответния
индекс от цикъла 2.2.1
2.2.3 Имаме две условия за местене на буквата:
2.2.3.1 Настоящия индекс от цикъла 2.2.1 е ПО-МАЛЪК от новата позиция,
следователно местим буквата от настоящия индекс от Ляво на дясно:
(цикъл int j=index(2.2.1); j<нова позиция; j++)
2.2.3.2 Настоящия индекс от цикъла 2.2.1 е ПО-ГОЛЯМ от новата позиция,
следователно местим буквата от настоящия индекс от Дясно на ляво:
(int j = index(2.2.1); j > нова позиция; j--)
Това е в общи линии ако имате въпроси питайте.
Ето и кодът ми:

using System;

class Program
{
    static void Main(string[] args)
    {
        //Step 1
        string[] sentence = Console.ReadLine().Split();
        int longestWord = FindLongestWordLength(sentence);
        string extracted = ExtractingLastCharacters(sentence, longestWord);
        //Step 2
        char[] result = extracted.ToCharArray();
        result = MovingCharacters(result);
        foreach (var letter in result)
        {
            Console.Write(letter);
        }

    }
    static int FindLongestWordLength(string[] sentence)
    {
        int longestWord = 0;
        foreach (var word in sentence)
        {
            if (word.Length>longestWord)
            {
                longestWord = word.Length;
            }
        }
        return longestWord;
    }
    static string ExtractingLastCharacters(string[] sentence,int longestWord)
    {
        string extracted = string.Empty;
        for (int i = 0; i < longestWord; i++) //loop for extracting the last characters in words
        {
            for (int j = 0; j < sentence.Length; j++) //loop for switching the words in sentence
            {
                string temp = sentence[j];
                if (temp.Length-i-1>=0) //temp.Length-i-1 moving from temp[temp.length-1] to temp[0]
                {
                    extracted += temp[temp.Length - i - 1]; //adding the extracted charaters to the string
                }
            }
        }
        return extracted;
    }
    static char[] MovingCharacters(char[] result)
    {
        for (int i = 0; i < result.Length; i++) // int i = current position in the array
        {
            int letterValue = char.ToLower(result[i])-'a'+1; //giving the letters the Latin alphabet value
            int position = letterValue + i; //the new position of the current character
            if (position>result.Length-1) //the position of the character if it's>result[lastindex]
            {
                position %= result.Length;
            }

            if (i<position)
            {
                result = MovingCharFromLeftToRight(result, position, i);
            }
            else if (position<i)
            {
                result = MovingCharFromRightToLeft(result, position, i);
            }
        }
        return result;
    } 
    static char[] MovingCharFromLeftToRight(char[]result,int position,int i)
    {
        for (int j = i; j < position; j++)
        {
            char temp = result[j];
            result[j] = result[j + 1];
            result[j + 1] = temp;
        }
        return result;
    }
    static char[] MovingCharFromRightToLeft(char[] result, int position, int i)
    {
        for (int j = i; j > position; j--)
        {
            char temp = result[j];
            result[j] = result[j - 1];
            result[j - 1] = temp;
        }
        return result;
    }
}