5 algorytmów na start w JavaScript. Wznieś się na wyższy poziom.

22/11/2018
Bartek Cis

Pisanie algorytmów w JS’ie to podstawowa umiejętność każdego Front-End Developera. Jeśli chcesz udoskonalić swoje umiejętności i poznać kilka nowych technik to jesteś w dobrym miejscu.

Czego się dzisiaj dowiesz?

Przedstawiłem tu 5 zadań programistycznych często spotykanych przy tworzeniu aplikacji internetowych. Przy każdym opisuję conajmniej jedną metodę rozwiązania przy użyciu prototypów dostępnych w JavaScript. Jeśli algorytmy są dla Ciebie nowością i chcesz się ich nauczyć to zdecydowanie polubisz ten wpis 🙂 Jeśli JS nie jest Ci obcy to kto wie? Może zobaczysz tutaj coś co Cię zaintryguje?

Poruszone zagadnienia można uznać za “podstawowe” i ich znajomość zdecydowanie pomaga znaleść pierwszą pracę jako Developer. Bo przecież zadania z programowania wcale nie są rzadkością przy rekrutacji…

Seria algorytmy w JavaScript

To zagadnienie jest bardzo ciekawe więc chciałbym je poruszyć dokładniej i rozbić to na trzy części. Dzisiejszy wpis jest pierwszym z serii:

  1. 5 Podstawowych algorytmów w JavaScript.
  2. 5 Średnio-zaawansowanych algorytmów w JavaScript.
  3. 5 Zaawansowanych algorytmów w JavaScript.

Informacje wstępne

Zanim zaczniemy zatrzymam się na chwilę i wyjaśnię samo słowo “algorytm” i odniosę się do jego użycia w przypadku JavaScript (i pewnie wszystkich innych językach programowania). Jest to początek serii więc wypada o tym wspomnieć.

Algorytm

To słowo potrafi zjeżyć włosy na głowie… Bo przecież brzmi tak skomplikowanie… Hehe, no tak 🙂 Jednak jak się Ciebie zapytam czym w zasadzie jest algorytm to co odpowiesz?

Odpowiedź jest bardzo prosta, to zbiór jasno określnych kroków/etapów które należy wykonać aby rozwiązać dany problem!

Weźmy np. Twoją poranną rutynę czyli zbiór czynności które wykonujesz każdego dnia aby przenieść się z Twojego wygodnego łóżka do mniej wygodnej ławki/biurka w szkole/uczelni czy pracy. Najpierw wstajesz z łóżka, ubierasz się, jesz śniadanie, myjesz się, przebierasz, wychodzisz z domu, przybywasz do celu, zajmujesz swoją strategiczną pozycję 🙂 Hehe u Ciebie może to oczywiście wyglądać inaczej ale te wszystkie kroki to jest właśnie algorytm!

Czyli… czyli Nasze życia to algorytmy?

Schemat blokowy algorytmu

Dużo łatwiej jest to sobie wyobrazić na przykładzie takiego schematu. Po prostu jasno widać krok po kroku co należy zrobić aby dojść z punktu A do punktu B.

Najzwyczajniej w Świecie, jestem w jednym miejscu i robię to i to. Jak się nie udaję to próbuje czegoś innego. Znowu nie wyszło? No to idę w innym kierunku. itp. itd… No nie! Teraz to wszystko się spierdzieliło! Wracam do punktu wyjścia! Zaczynam od nowa 🙁

Hehe, brzmi znajomo?

Programowanie

Programowanie to w zasadzie umiejętność pisania takich scenariuszy/ algorytmów które są zrozumiałe dla komputera. Wtedy on na spokojnie sobie wykonuje te kroki a Ty idziesz na kawę 🙂

Czyli każdy programista jest scenarzystą?

Złożoność obliczeniowa

Teraz całą sztuką jest aby napisać algorytm który rozwiąże dany problem w najszybszy możliwy sposób. Oszczędzi to czas i zasoby. Dlatego programiści i naukowcy analizują ciągle nowe problemy starając się znaleść optymalne algorytmy. Są to algorytmy które najlepiej rozwiążą dany problem.

Metody w JavaScript

Istnieją zadania programistyczne które spotykane są bardzo często np. posortuj jakieś dane lub sprawdź czy dany wyraz posiada literę “a”. Aby uniknąć mozolnych prób każdego programisty mających na celu posortować te dane współczesne języki programowania oferują wbudowane metody które rozwiązują problem za nas. Nie trzeba (choć warto) umieć posortować danego zbioru danych w sposób optymalny.

Zadania programistyczne

No to jak wszystko już jest to po co komu programista?

Otóż zadaniem programisty jest rozwiązywanie bardziej złożonych algorytmów przy użyciu metod wbudowanych w danym języku programowania. Często tych problemów nie da się rozwiązać z automatu bo każdy z nich może być unikalny i wymaga innego podejścia. I tu zaczyna się Twój czas. Zaraz rozwiążesz kilka takich zadań przy pomocy JavaScript!

Zakładam, że posiadasz już podstawową znajomość JavaScript. To zdecydowaniu ułatwi zrozumienie dalszej części tego wpisu.

Najdłuższy wyraz w zdaniu

Zaczniemy od czegoś prostego tzn. mając dowolne zdanie lub dłuższy ciąg znaków chcemy znaleść najdłuższy wyraz i wiedzieć z ilu się składa znaków. Spróbujmy to zrobić w podstawowy sposób, np. tak:

//1
let string = 'Kiedy byłem małym chłopcem hej, zawsze chciałem gładko golić się';

function longestWord(str) {
//2
    let words = str.split(' '),
//3
    maxLength = 0,
    word = '';
//4
    for (var i = 0; i < words.length; i++) {
        if (words[i].length > maxLength) {
            word = words[i];
            maxLength = words[i].length;
        }
    }
//5
    return [word, maxLength]; //["chłopcem", 8]
}

console.log(longestWord(string));

Wyjaśnię krok po kroku:

  1. Definiuję ciąg wyrazów który mnie interesuje. W tym wypadku zmienna string.
  2. Wewnątrz funkcji tworzę zmienną words która jest stworzona z argumentu atr na którym wywołujemy metodę split(). Co robi split? To super użyteczna metoda bo jest w stanie zamienić ciąg znaków w postaci stringa w tablicę czyli array. Wystarczy podać tylko separator czyli w tym wypadku spację (‘ ‘). Znaczy to tyle, że za każdym razem kiedy pojawi się spacja tworzony jest nowy element w tablicy.
  3. Dodatkowo tworzę zmienne pomocnicze czyli word i maxLength do których odpowiednio przypiszę najdłuższe słowo i jego długość.
  4. Kiedy mam już tablicę ze wszystkimi wyrazami w zdaniu po prostu używam zwykłej pętli for. Jeśli kolejny wyraz jest dłuższy od poprzedniego to przypisuje go do zmiennej word a jego długość do maxLength.
  5. Kiedy się pętla skończy funkcja zwraca tablicę z dwiema zmiennymi w tym wypadku jest to [“chłopcem”, 8]. To jest nasz najdłuższy wyraz.

Prawda, że to dość proste? Spróbuję to jednak załatwić kompletnie inaczej…

Funkcja Rekursywna / Recursive Function

Ten enigmatyczny termin znaczy tyle, że funkcja może wywołać siebie samą tylko należy uważać jakie jej się podaje parametry. Jak będziesz podawać to samo to się może zapętlić w nieskończoność 🙂 Niech to wygląda tak:

function longestWordRecursive(str) {
    //1
    str = str.split(' ');
    //2
    if (str.length === 1) {
        return [str[0], str[0].length]; //["chłopcem", 8]
    }
    //3
    if (str[0].length >= str[1].length) {
    //4
        str.splice(1, 1);
    //5 & 6
        return longestWordRecursive(str.join(' '));
    }

    // 7
    if (str[0].length <= str[1].length) {
        return longestWordRecursive(str.slice(1, str.length).join(' '));
    }
    return str.length;
}

console.log(longestWordRecursive(string));
  1. Konwertujemy zdanie w tablicę za pomocą split().
  2. Sprawdzamy długość tablicy. Jeśli wynosi 1 to zdanie ma tylko jeden wyraz jest on więc najdłuższy.
  3. W kolejnym warunku sprawdzamy długość pierwszych dwóch wyrazów w tablicy. Jeśli pierwszy jest dłuższy od drugiego to
  4. Używam metody splice() w tym zapisie tzn. .splice(1, 1) oznacza, że usuwam z tablicy drugi element (w tym wypadku krótszy wyraz). Tym sposobem nasza tablica właśnie straciła jeden z krótkich wyrazów.
  5. Teraz czas na rekursywne wywołanie naszej funkcji. Czyli zaczyna ona pracę od nowa tylko teraz z innym argumentem.
  6. Jako argument podajemy naszą skróconą tablicę i używamy na niej metody join(). Jest to odwrotność split() czyli jak zrobimy na tablicy .join(‘ ‘) to wszystkie elementy zostaną połączone za pomocą spacji w jeden długi string/ zdanie.
  7. Kolejnym warunkiem jest sprawdzenie czy drugi wyraz nie jest dłuższy od pierwszego. Jeśli tak to chcemy pozbyć się pierwszego. Używamy metody slice() czyli str.slice(1, str.length pozostawia w tablicy wszystkie elementy od drugiego do ostatniego. Na końcu łączymy tablicę za pomocą join() i tworzymy string który jest rekursywnie wywoływany.

W ten sposób funkcja analizuje dane zdanie wyraz po wyrazie usuwając te krótkie. Ostatecznie zostaje nam tylko ten najdłuższy 🙂

Palindrom

To zadanie to po prostu klasyk i powtarza się na wielu rekrutacjach. Palindrom to wyraz który brzmi tak samo po odwróceniu wszystkich liter np. KAJAK = KAJAK. Jak się za to zabrać?

function palindrome(str) {
    // 1 & 2 &3
    let reversed =  str.split('').reverse().join('');
    // 4
    return str === reversed ? true : false;
}

console.log(palindrome("kajak")); // true

Podążymy najprostszą logiką czyli odwrócimy wszystkie litery i porównamy do oryginału 🙂

1. Tworzymy zmienną reversed która będzie przechowywać odwróconą wersję wyrazu. Pierwszym krokiem jest użycie .split(”). Jeśli wewnątrz nie zdefiniujemy żadnego separatora to każdy znak w stringu będzie osobnym elementem w tablicy.

2. Następnie odwracamy wszystkie elementy w tablicy za pomocą reverse(). Prawda, że bardzo użyteczne?

3. Łączymy odwróconą tablicę do stringa za pomocą join(”) bez separatora.

4. Ostatnim krokiem jest zwrócenie wartości true lub false w zależności od tego czy obydwa wyrazy są takie same. Użyjemy do tego wyrażenie if zapisanego w postaci tenary operator czyli

if (str === reversed) {
    return true;
} else {
    return false;
}

znaczy to samo co

return str === reversed ? true : false;

W naszym wypadku widzimy, że ‘kajak’ jest palindromem 🙂

Ta metoda jednak wymaga dzielenia, odwracania, łączenia, porównywania… Można to zrobić szybciej…

Pętla while

Ta metoda jest szybsza bo na bieżąco porównujemy pierwszą i ostatnią literę i jeśli coś nie gra to odrzucamy cały wyraz…

function palindrome2(str) {
    //1
    let front = 0,
    back = str.length - 1;
    // 2
    while (back > front) {
        //3
        if (str[front].toLowerCase() !== str[back].toLowerCase()) return false;
        //2
        front++;
        back--;
    }
    // 4
    return true;
}

console.log(palindrome2("kajok")); // false
  1. Definiujemy dwie zmienne, które będą reprezentować indeksy kolejnych liter w wyrazie tzn. front będzie pierwszą a back ostatnią.
  2. Definiujemy pętlę while która będzie się wywoływana tak długo jak index back będzie większy od front. Na końcu pętli odpowiednio modyfikujemy każdą zmienną żeby nie było nieskończonej pętli. Zauważ, że w przypadku gdy wyraz na nieparzystą liczbę liter ta środkowa nie będzie do niczego porównywana. Bo po co? W końcu szukamy palindromu…
  3. Porównujemy kolejne litery używając metody toLowerCase() w ten sposób wiesz, że zawsze porównujesz małe litery w alfabecie bo JS nie uważa liter d i D za tożsame. Jeśli litery się nie zgadzają zwracamy false. To nie palindrom…
  4. Jeśli pętla się wywołała do końca mamy do czynienia z palindromem!

Niestety jak widać ‘Kajok’ nie jest palindromem…

Seek & Destroy

Ten algorytm ma za zadanie przefiltrowanie jednego zestawu danych w oparciu o drugi. W przykładzie mamy podstawową tablicę z liczbami oraz dodatkową tablicę gdzie mamy zestaw liczb które chcielibyśmy wykluczyć z pierwszej tablicy. Jeśli w pierwszej tablicy znajdziemy liczbę która znajduje się w drugiej to wtedy usuwamy ją z pierwotnej tablicy. Taki rodzaj filtrowania. Wygląda to tak:

  1. // 1
    let baseArray = [23, 12, 34, 234, 78, 153, 987, 12, 43, 67],
        filterArray = [34, 67, 32, 34, 98, 54, 67, 89, 345, 234];
    
    function filterFuntion(arr, arr1) {
        // 2 & 3
        return arr.filter((val) => {
        // 4 & 5
            return !arr1.includes(val);
        });
    }
    
    console.log(filterFuntion(baseArray, filterArray));

    Na początku definiujemy bazowy zestaw danych baseArray i bazę filtrów filterArray

  2. Funkcja ma zwrócić zmodyfikowaną główną tablicę
  3. Główna tablica będzie modyfikowana za pomocą metody filter() Jeśli podamy do niej jeden argument val będzie on symbolizował każdy kolejny element w tablicy arr. W ten sposób sprawdzimy kolejno każdy element czy spełnia określone warunki filtracji.
  4. Używamy return aby zwrócić te elementy które spełniają warunek. Jest on taki, że ten analizowany element val musi być zawarty w tablicy pomocniczej arr1. Używa się do tego metody includes().
  5. Jako, że w zasadzie chodzi nam o coś kompletnie innego tzn. jeśli element zawiera się tablicy pomocniczej musimy zanegować ten warunek używając wykrzyknika !. Znaczy to tyle, że zwróć element kiedy się nie zawiera w podzbiorze czyli coś jest prawdą jeśli nie jest prawdą 🙂 Ten wykrzyknik to chyba jakiś ukłon w stronę polityków i propagandzistów 🙂 W zapisie JavaScript wygląda to tak !arr1.includes(val)

Umieść cyfrę w odpowiednim miejscu

Kolejnym algorytmem który wezmę na tapetę jest wstawianie elementu do zbioru. Powiedzmy, że jest jakiś zestaw liczb i dołączyć jakąś nową wartość. Ta wartość ma być ustawiona w uporządkowanym miejscu i chcę wiedzieć dokładnie gdzie została wstawiona czyli jaka jest jej liczba porządkowa.

To będzie łatwe 🙂 Czyli po prostu wrzucę tą liczę do puli a potem przesortuję.

// 1
function itemIndex(arr, num) {
    // 2
    arr.push(num);
    // 3
    arr.sort((a,b) => {
        return a-b;
    });
    // 4
    return [arr, arr.indexOf(num)];
}

console.log(itemIndex([3,4,1,2], 1.5));  // [[1, 1.5, 2, 3, 4], 1]
  1. Definiuję funkcję która posiada dwa argumenty, pierwszy arr to tablica z liczbami a drugi num to liczba którą chcemy dołączyć. Dla zabawy niech to będzie ułamek czyli 1.5
  2. Używam metody push() aby dołączyć wybraną liczbę do zbioru. push() z założenia dodaje tą wartość na sam koniec tablicy.
  3. Następnie używam wbudowanej metody sort() do której podaje dwa parametry. Wewnątrz metody zwracam różnicę tych parametrów a-b otrzymując wtedy tablicę posortowaną od najmniejszych do największych wartości.
  4. Kiedy tablica łącznie z naszą wartością jest posortowana po prostu funkcja ją zwraca za pomocą return. Chcemy jeszcze znać pozycję tej liczby więc używamy metody indexOf() która pięknie podpowiada, że jest to 1. Każdy developer wie, że w tym wypadku 1 znaczy 2 🙂 Czyli ta liczba jest na drugim miejscu.

Szyfr Cezara

Ostatnim algorytmem w tym wpisie będzie szyfr Cezara. Czym jest? Jest to prosty sposób na zaszyfrowanie wiadomości. Działa on w ten sposób, że każda litera jest przesunięta o konkretną wartość np. A -> D, E -> H przez co wiadomość przestaje być czytelna.

KeyCodes i ASCII Codes

Aby lepiej zrozumieć o co chodzi w tym szyfrowaniu warto wiedzieć, że każda liczba i znak może mieć przyporządkowane odpowiednie kody. Do tych najpopularniejszych należą kody ASCII i Kody Klawiatury/Przycisków. 

Znając te kody możemy w łatwy sposób pisać formuły matematyczne które będą odpowiednio szyfrować nasze wiadomości. Jest to oczywiście bardzo ogólne podejście do sprawy. W JavaScript można bardzo łatwo modyfikować wartości keyCodes.

Alfabet

Dla ułatwienia w algorytmie posłużę się tylko literami alfabetu łacińskiego czyli A-Z które posiadają wartość charCode 65-90.

Szyfrowanie

Najpierw zaszyfruję komunikat podstawowym sposobem poprzez przesunięcie o 13 znaków:

function encrypt(str) {
    // 1
    return str.split('').map((char) => {
        // 2
        x = char.charCodeAt(0);
        // 3 - Sprawdz czy znak jest litera A-Z
        if (x < 65 || x > 90) {
            // 4 - zworc nie przekonwertowany znak
            return String.fromCharCode(x);
        }
        // 5 - jesli asci code jest mniejszy niz 78 to przesun o 13 znakow do przodu
        else if ( x < 78) {
            return String.fromCharCode(x + 13);
        }
        // 6 - w innym wypadku to przesun o 13 znakow do tylu
        else {
            return String.fromCharCode(x - 13);
        }
    // 7
    }).join('');
}

console.log(encrypt('BEDEKODZIC')); // ORQRXBQMVP
  1. A więc funkcja zwraca zmodyfikowany argument który jest podany w postaci stringa. Konwertujemy go do tablicy za pomocą split(”). Kolejnym krokiem jest iteracja przez tablicę za pomocą metody .map() gdzie argument char jest każdym kolejnym elementem tablicy.
  2. Teraz analizujemy każdy element tablicy. Na początek definiujemy zmienną x która reprezentuje charCode każdej litery taką konwersję robi się za pomocą metody .charCodeAt(0
  3. Jako, że analizujemy tylko litery to sprawdzamy czy kod znaku mieści się w odpowiednim zakresie, jeśli nie to nie szyfrujemy tego znaku.
  4. Konwertujemy kod do znaku za pomocą String.fromCharCode(x).
  5. Kolejnym warunkiem jest sprawdzenie czy kod jest mniejszy od 78 jeśli tak to przesunięcie w tył o 13 pozycji sprawi, że wyjdziemy poza zakres liter a o to nam nie chodzi. Wtedy dodajemy 13 pól do zmiennej x i konwertujemy kod na znak. Otrzymujemy zaszyfrowaną literę.
  6. W odwrotnym przypadku postępujemy analogicznie tylko odejmujemy od pierwotnego kodu 13 pozycji aby nie wypaść poza zakres liter. Zwracamy zaszyfrowany znak.
  7. Na koniec łączymy całą tablicę w string za pomocą metody join(). Jak widać zaszyfrowane Bedekodzic to ORQRXBQMVP 🙂

Odszyfrowanie

W tym wypadku musimy wykonać analogiczną operację tylko w odwrotnym kierunku. Użyję do tego innego, bardziej zaawansowanego algorytmu 🙂 :

function decrypt(str) {
    return str.replace(/[A-Z]/g, L => String.fromCharCode((L.charCodeAt(0) % 26) + 65));
}

console.log(decrypt('ORQRXBQMVP')); //BEDEKODZIC
  1. Na początku funkcja zwraca zmodyfikowany argument w postaci stringa.
  2. Modyfikujemy go za pomocą metody replace() i podajemy dwa parametry replace(a, b). Działa to w ten sposób, że jeśli w stringu znajduje się znak a to zostanie on zastąpiony znakiem b.
  3. Jako parametr a definiujemy tu wyrażenie regularne /[A-Z]/g oznacza ono, że poszukujemy wszystkich liter alfabetu od A do Z. W naszym wypadku chcemy zastąpić każdą literę.
  4. Nie chcemy dokonać zwykłej podmiany tylko na każdej literze dokonać konkretnej operacji. Dlatego definiujemy funkcję strzałkową => L
  5. Funkcja strzałkowa konwertuje każdą literę na inną literę za pomocą metody fromCharCode() jednak najpierw w miejscu na argument wykonuje pewną operację.
  6. Najpierw konwertuję daną literę na kod za pomocą charCodeAt(0)
  7. Następnie liczy modulo % dla nowego kodu. Modulo to po prostu reszta z dzielenia. W tym wypadku przez 26.
  8. Istnieje taka zależność, że jeśli do tej reszty z dzielenia dodamy 65 to otrzymamy pierwotny kod przy przesunięciu o 13 według Naszego schematu. Magia matematyki…
  9. Kiedy wszystkie operacje matematyczne zostaną wykonane to litery są odszyfrowywane 🙂 Wynik to BEDEKODZIC 🙂 Zaskoczony/a?

No i jak sobie z tym wszystkim poradzić?

Wiem, że na pierwszy rzut te algorytmy wcale nie wydają się podstawowe. Wymagają już dość dobrej znajomości JS’a jednak wszystko przychodzi z czasem.

Ważne jest aby zdawać sobie sprawę z jakimi typami zmiennych (Number, String, Array, Object itp.) masz do czynienia. Każdy typ zmiennej to odpowiedni obiekt w JavaScript i ma zdefiniowane unikalne metody/prototypy. Te metody to właśnie optymalne algorytmy które ułatwiają nam pracę. Warto je znać i wiedzieć kiedy co można zastosować.

Szczerze? Nie wiem jak bym sobie poradził, gdybym nie mógł używać tych wszystkich metod… To byłby po prostu dramat 🙂

Co dalej?

Gorąco polecam portal CODEWARS można tam złapać niezłego skilla w rozwiązywaniu takich zadań programistycznych 🙂

Podsumowanie

Programowanie to umiejętność pisania algorytmów o jak najmniejszej złożoności obliczeniowej. Prawdziwi mistrzowie są w stanie stworzyć wydajne aplikacje właśnie dzięki stosowaniu najlepszych praktyk tworzenia oprogramowania i optymalnych algorytmów. To sztuka.

Jeśli stawiasz swoje pierwsze kroki w JSie to mam nadzieję, że się dużo tu nauczyłeś/aś 🙂 Od tego właśnie jest ten blog 🙂

Jeżeli jednak ten materiał to dla Ciebie nic nowego, to podziel się swoją opinią? Czy walnąłem gdzieś jakąś gafę? A może rozwiązał byś jakiś problem w dużo lepszy sposób? Chętnie czegoś się od Ciebie nauczę!

Podziel się z innymi 🙂

Piszę dla was tego bloga bo lubię aplikacje internetowe. Mogę je projektować, kodować a potem o nich pisać czując dreszczyk ekscytacji za każdym razem gdy trafię na coś nowego. Bo uczymy się całe życie. Prawda?

warto

partnerzy:

dane kontaktowe:

kontakt@bedekodzic.pl

Social media & sharing icons powered by UltimatelySocial

Podoba Ci się ten blog? Podziel się ze znajomymi!

  • Facebook
    Facebook
  • Twitter
    Visit Us