Kategorie
Codility Java Script

BinaryGap

Zadanie BinaryGap z jedyny problem do rozwiązania z pierwszej lekcji Codility. W razie problemów z aspektem teoretycznym serwis udostępnia odpowiedni dokument PDF.

Problem

Zadanie wymaga napisania funkcji, która dla dodatniej liczby N zwróci długość jej najdłuższej przerwy binarnej, czyli ciągu zer pomiędzy jedynkami. Funkcja powinna zwracać 0, jeśli N nie posiada binarnej przerwy.

Przykładowo, dla liczby N = 9, zapisanej binarnie 1001 przerwa wynosi 2. Liczba 20 zapisana binarnie to 10100, a jej przerwa 1.

Zakładamy także, że N jest liczbą całkowitą z zakresu [1..2147483647].

Rozwiązanie

Rozwiązanie problemy podzielimy na kilka kroków:

  1. Konwersja liczby całkowitej do postaci binarnej
  2. Pozbycie się skrajnych zer z postaci binarnej
  3. Rozdzielenie postaci binarnej znakiem '1′
  4. Porównanie znalezionych ciągów zer i znalezienie najdłuższego
  5. Zwrócenie długości przerwy binarnej

JavaScript

Zaczynamy od zdefiniowania zmiennych, które będą nam potrzebne w czasie działania funkcji.

Zmienna gap będzie przechowywała wartość przerwy. Początkowa wartość została ustalona na 0, co w sytuacji braku binarnej przerwy pozwoli na obsłużenie tej sytuacji. Zmienna bin będzie reprezentowała liczbę N w postaci dwójkowej. Zmienne start i stop zostaną wykorzystane do przechowania informacji o indeksie pierwszej i ostatniej jedynki w binarnej postaci liczby, a zmienna parts do przechowania wszystkich ciągów zer w postaci binarnej.


var gap = 0,
    bin = (N).toString(2),
    start = bin.indexOf('1'),
    stop = bin.lastIndexOf('1'),
    parts = bin.substring(start, stop+1).split('1');

Funkcja toString() dla liczb w JavaScript zwraca wartość liczby w postaci ciągu znaków. Opcjonalny argument funkcji umożliwia ustalenie podstawy wyliczeń, mówiąc prościej (N).toString(2) zwróci liczbę N w postaci binarnej, czego właśnie potrzebujemy.

Kolejny krok wymaga pozbycia się skrajnych zer, gdyż nawet najdłuższe ciągi zer na początku i końcu nie będą rozdzielone znakiem '1′ z obu stron, co jest wymagane w opisie problemu. JavaScript udostępnia konkretne funkcje indexOf() oraz lastIndexOf() do znalezienia określonego ciągu znaków w zmiennej. Zatem start zawiera miejsce wystąpienia pierwszej, a stop – ostatniej jedynki w zmiennej bin, co w określonych przypadkach może być tym samym miejscem.

To akurat nie problem, większy stanowi kwestia, kiedy ciąg „1” nie zostanie znaleziony, bo wówczas funkcje zwracają -1 jako szukanego znaku ciągu. Jednak w naszym przypadku liczba N jest zawsze dodatnia, zatem ten problem pomijamy. Wówczas należałoby w tych sytuacjach ustawić warunkowo wartości 0 zmiennym start i stop.

Następny krok to podzielenie znakiem „1” podciągu postaci binarnej, uzyskanej przez funkcję substring(start, stop), czego wynikiem będą wszystkie ciągi zer spełniające warunek przerwy binarnej i przypisanie ich do zmiennej parts. Warto zwrócić uwagę na konsekwentne ustalenie podciągu do podziału (ze skrajnymi jedynkami lub bez), choć nawet bez zwiększania wartości stop bądź zmniejszania start algorytm zachowa się tak samo, gdyż co najwyżej uwzględni dodatkowe przerwy zerowej długości.

Kolejna czynność to znalezienie najdłuższej przerwy binarnej spośród dostępnych. Najłatwiejszy sposób to iteracja w pętli for zmiennej parts, która jest tablicą i porównanie każdego elementu z dotychczasową wartości zmiennej gap pod względem długości.


for (var i = 0; i < parts.length; i++) {
  if (parts[i].length > gap) {
    gap = parts[i].length;
  }
}

Na koniec pozostaje tylko zwrócenie wartości gap, czyli przerwy binarnej.

W razie potrzeby cały przykład dostępny jest na CodePen

W odpowiedzi na “BinaryGap”

Witam,
szczerze mówiąc nie bawiłem się nigdy Codility, ale poruszyłeś ciekawy problem.
Tak dla ciekawości można to zadanie rozwiązać również w inny sposób, wykorzystując wyrażenia regularne:
const binaryGap = (n) => Math.max(…(((n).toString(2).match(/0+(?=1)/g)||[”]).map(v => v.length)))

Krótki opis:
1. Najpierw liczbę n konwertujemy do postaci binarnej.
2. Następnie wyszukujemy wszystkie wystąpienia zer, po których znajduje się cyfra „1”. Metoda toString(2) w JavaScript zawsze „utnie” początkowe zera, więc mamy pewność, iż zawsze (po za (0).toString(2)) otrzymamy na początku cyfrę jeden.
3. W kolejnym kroku przelatujemy przez tablicę pozyskaną z match() i w miejsce każdego elementu wstawiamy jego długość, czyli np. dla liczby 3997 otrzymamy postać binarną „111110011101” i metoda match() zwróci tablicę [’00’, '0′], a po przeleceniu tego metodą map otrzymamy [2,1].
4. Ostatni krok to wywołanie metody obiektu Math.max() w celu zwrócenia największej z uzyskanych ilości zer. Metoda max nie operuje jednak na tablicach, dlatego należy przekazać jej pojedyncze elementy. Zastosowałem tu specjalny operator z ECMA Script 6, i wywołanie max(…[2,1]) stworzy w rzeczywistości wywołanie max(2,1) i metoda prawidłowo zwróci wartość 2.

Krótkie testy:
binaryGap(1); //0
binaryGap(1025); //9
binaryGap(3997); //2

Zastosowałem w całości składnię ES6 wraz z Arrow function. Dla osób nie znających tej składni pozostawiam jako ćwiczenie przerobienie sobie tego na zapis „standardowy” z function …
(w razie problemów chętnie pomogę)

Możliwość komentowania została wyłączona.