Format daty to temat dziewiątego wpis na blogu, gdzie omówimy sobie jedno z zadań. Jest mi bliski z dwóch powodów. Po pierwsze SPOJ, od którego rozpoczynałem przygodę z algorytmami. Po drugie format daty, który był jednym z moim pierwszych zadań w pracy na etacie. Zadanie jest dość specyficzne, lecz przedstawię tu informacje na temat tego, jak prezentuje się format daty oraz odpowiem na pytania:

  • W jaki sposób wyliczyć rok przestępny?
  • Jak zaimplementować różny format daty?
  • W jaki sposób sprawdzić liczbę dni w miesiącu?

Dodatkowo zadanie wymaga od nas zapoznania się z systemem binarnym. Już nie mogę się doczekać rozwiązania.

Zaczynamy!

Treść zadania zapisu daty

Pełna treść zadania dostępna jest pod linkiem.

Zadanie na SPOJ zostało dodane w 2009 roku i jest to zadanie konkursowe o nagrodę Dziekana WI ZUT w Szczecinie. Celem jest format daty na jeden z dwóch sposobów. Międzynarodowa norma ISO 8601 (RRRR-MM-DD). Format daty w sposób binarny zwany roboczo DOSFAT. Format zapisywany jako 7 bitów na rok zaczynając od 1980 roku, 4 bity na miesiąc oraz 5 bitów na dzień.

Zgodnie z powyższym na wejście podajemy 10 znaków zgodnie z normą ISO 8601 lub 16 znakowy ciąg zer i jedynek. Na wyjściu w zależności od wejścia pokażemy, możemy uzyskać trzy możliwe ciągi znaków:

  • ISO 8601 w przypadku podania na wejście 16 znakowy ciąg binarny
  • binarnie w przypadku gdy na wejście podamy 10 znaków zgodnie ze standardem ISO
  • ERROR w przypadku błędnie podanego ciągu znaków na wejście

Jako przykłady podane mamy trzy przypadki.

  1. 0011101100110010  ->  2009-09-18
  2. 2009-09-18  ->  0011101100110010
  3. 0000000000000000  ->  ERROR

Format daty — opis rozwiązania 

Zawsze, gdy zasiadam do rozwiązania tego typu krótkiego zadania, staram się rozpisać rozwiązanie w miarę szczegółowo. Czasami ciężko jest od razu przewidzieć wszystkie możliwe pułapki, które na nas czekają i właściwy sposób implementacji. Przedstawię poniżej swój tok rozumowania i ewentualne problemy, z jakimi się spotkałem.

Początek programu

Na starcie skupię się na elementach, które dodał Visual Studio. Chodzi mianowicie o pierwsze cztery linie kodu. Dwie pierwsze linie to dodanie bibliotek. Dzięki nim będziemy mogli obsługiwać strumienie wejścia i wyjścia, operacje arytmetyczne czy zapytania za pomocą LINQ.

Czwarta linia to również automatycznie dodana przestrzeń nazw, która w tego typu krótkim programie konsolowym jest w zasadzie nieistotna.

using System;
using System.Linq;

namespace WI_DATY

Dane wejściowe i deklaracja zmiennych

W pierwszej kolejności zakładam, że na wejście pojawi się dowolny ciąg znaków, który będzie zawierał ilość znaków X. Wypisuję na konsolę komunikat z prośbą o podanie daty w jednym z dwóch założonych formatów. W kolejnych dwóch liniach deklaruję prywatne zmienne typu string oraz int do przechowywania roku, miesiąca oraz dnia. Wprawny programista zauważy pewnie, że zmienne można zapisać w jednym typie i próbować konwertować. Zostawiłem jednak furtkę do refaktoryzacji!

{
    Console.WriteLine("Podaj datę w formacie binarnym lub ISO 8601:");
    string dateFormatted = Console.ReadLine();
    string year = "", month = "", day = "";
    int monthInt = 0, dayInt = 0, yearInt = 0;
   

Główna walidacja danych wejściowych

Czas sprawdzić jakie dane dostajemy na wejście programu. Walidujemy ilości znaków w tekście i to czy nie różni się od 10 i 16. Sprawnie załatwia to instrukcja warunkowa. Gdy ilość różni się od wspomnianych wartości, to zgodnie z treścią polecenia wypisywany jest na ekran komunikat o błędzie.

int count = dateFormatted.Count();
if (count == 10)
{
}
else if (count == 16)
{
}
else
{
    Console.WriteLine("ERROR");
    return;
}

10 znaków na wejściu

Czas na najważniejszą część programu. Wspomniałem wcześniej, że mamy możliwość na wejściu podania ciągu znaków dowolnej długości. Jednak interesuje nas tylko ciąg o długości równej 10 lub 16. Aktualnie skupimy się na ciągu 10-znakowym.

Po spełnieniu warunku zakładam, że ciąg znaków wprowadzony jest w formacie RRRR-MM-DD, więc robię rozdzielenie tekstu poprzez separator – (znak minusa). Powstaje w ten sposób tablica, która powinna zawierać trzy elementy. Gdy ilość ta jest różna, wtedy wyświetlamy na ekranie ERROR. Oczywiście i ten element kodu ma możliwość zgrabnej refaktoryzacji z użyciem wyrażenia regularnego oraz sposobu wyświetlenia błędu. Temat ten również pozostawiam czytelnikowi. 

W liniach 22-24 przeprowadzam konwersję z wartości dziesiętnej do wartości binarnej. Stosowana jest do tego funkcja DecToBinary (opisana w akapicie poniżej), która za parametr przyjmuje wartość tekstową oraz rozmiar, który reprezentuje ilość zwróconych bitów. Ta część zadania jest praktycznie skończona. Pozostało tylko wypisać wynik na ekran jako połączenie binarnego roku, miesiąca i dnia. 

Warto zauważyć, że w przypadku roku przekazywana jest wartość roku pomniejszona o 1980, ponieważ rok 1980 jest najniżej reprezentowaną wartością zgodnie z treścią zadania. Dzięki takiej konstrukcji mamy pewność, że przekazujemy 0 i wartość binarna, jaka dla roku 1980 wróci, będzie wyglądała następująco — 0000000.

if (count == 10)
{
    var splittedData = dateFormatted.Split('-');

    if (splittedData.Count() == 3)
    {
        year = DecToBinary((int.Parse(splittedData[0]) - 1980).ToString(), 7);
        month = DecToBinary(splittedData[1], 4);
        day = DecToBinary(splittedData[2], 5);

        Console.WriteLine(year + month + day);
    }
    else
    {
        Console.WriteLine("ERROR");
        return;
    }

16 znaków na wejściu

Szybko przechodzimy do drugiej części programu. W przypadku gdy na wejściu dostaliśmy 16 znaków, to wpadniemy w drugi warunek, w którym siłą rzeczy dzieje się trochę więcej niż poprzednio. 

Analizę rozpocznę od linii 36-42, gdzie następują konwersje. Najpierw za pomocą metody BinaryToDec następuje zamiana z wartości binarnej do wartości tekstowej a w dalszej kolejności parsowanie do wartości liczbowej. Celowo dla czytelności kodu rozdzieliłem te dwie konwersje. Zaznaczam, że można w tym miejscu zabezpieczyć się i użyć funkcji TryParse, zamiast Parse, która uchroni przed parsowaniem na int wartości tekstowych niebędących liczbami. Tu również zachęcam czytelnika do samodzielnej refaktoryzacji!

Przypadek z 10 znakami na wejściu był tym przypadkiem mniej skomplikowanym. W przypadku 16 znaków musimy przeprowadzić dodatkową walidację, która w poniższym kodzie rozpoczyna się w linii 44.

Ilość dni tygodnia i numer miesiąca

Pierwsze trzy warunki są proste, miesiąc nie może być mniejszy od jedności i większy od 12. Tak samo dzień nie może być mniejszy od jedności. Warunek numer cztery sprawdza, czy miesiąc to kwiecień, czerwiec, wrzesień lub listopad i czy dzień danego miesiąca nie przekracza wartości 30 zgodnie z kalendarzem gregoriańskim.

Ostatnie dwa warunki dotyczą najbardziej skomplikowanego miesiąca, jakim jest luty i ilość dni w roku przestępnym. Jak każdy wie luty raz na cztery lata ma 29 dni, w pozostałych trzech latach tych dni posiada 28. Tak też skonstruowane są warunki. Oprócz sprawdzenia, czy miesiąc równa się 2 oraz, czy dzień jest większy od 28 lub 29 sprawdzamy dodatkowo, czy rok jest przestępny. Rok przestępny to taki, który podzielny jest na 4 oraz nie jest podzielny przez 100.

W przypadku, gdy jeden z tych warunków będzie prawdą, wtedy wypisywany jest ERROR na konsoli. Jeżeli nie, to walidacja zakończy się pozytywnie i następuje sprawdzenie, czy przypadkiem dzień lub miesiąc nie jest jednością — w przypadku jedności musimy dopisać zero z przodu, by nie pokazać daty w formacie 2019-1-2 tylko 2019-01-02. Po tych wszystkich operacjach możemy wypisać wynik na konsoli.

Sama instrukcja warunkowa w tym fragmencie kodu wydaje się skomplikowana, ale gdy rozłożymy ją na części pierwsze, to wydaje się logicznie spójna. Oczywiście i tu zostawiam furtkę i zachęcam do refaktoryzacji.

else if (count == 16)
{
    year = (1980 + BinaryToDec(dateFormatted.Substring(0, 7))).ToString();
    month = BinaryToDec(dateFormatted.Substring(7, 4)).ToString();
    day = BinaryToDec(dateFormatted.Substring(11, 5)).ToString();

    yearInt = int.Parse(year);
    monthInt = int.Parse(month);
    dayInt = int.Parse(day);

    if (
        monthInt > 12 ||
        monthInt < 1 ||
        dayInt < 1 ||
        ((monthInt == 4 || monthInt == 6 || monthInt == 9 || monthInt == 11) &amp;&amp; dayInt > 30) ||
        (monthInt == 2 &amp;&amp; dayInt > 29 &amp;&amp; (yearInt % 4 == 0 &amp;&amp; yearInt % 100 != 0)) ||
        (monthInt == 2 &amp;&amp; dayInt > 28 &amp;&amp; (yearInt % 4 != 0 || yearInt % 100 == 0))
        )
        {
            Console.WriteLine("ERROR");
            return;
         }
         else
         {
             if (month.Count() == 1)
                 month = "0" + month;
             if (day.Count() == 1)
                 day = "0" + day;

             Console.WriteLine(year + "-" + month + "-" + day);
          }
    }

Metoda BinaryToDec

Czas na jednego z dwóch cichych bohaterów. Ten akapicie będzie omówieniem działania metody BinaryToDec, która w skrócie zamienia podany na wejście string złożony z zer i jedynek na wartość dziesiętną. W tym miejscu warto zastanowić się, w jaki sposób przebiega konwersja z liczby binarnej na dziesiętną. Sam proces jest prosty i polega na „patrzeniu” na liczbę binarną od prawej strony, nie zaś jak w systemach dziesiętnych od lewej. Każda kolejna pozycja (reprezentowana przez 2) jest podnoszona do coraz to wyższej potęgi, przemnożeniu przez wartość bitu i sumowana z poprzednimi wartościami.

Dla przykładu sprawdźmy prosty, 5-bitowy ciąg 01001. Patrząc od prawej mamy następujące równanie.

 (20 * 1) + (21 * 0) + (22 * 0) + (23 * 1) + (24 * 0) = 1 + 0 + 0 + 8 + 0 = 9 

Nie będę zgłębiał teraz bardziej konwersji, ponieważ planuję na temat systemów liczbowych i ich zamiany zrobić osobny artykuł w przyszłości.

Wrócę jednak do tematu. Na początku w linii 75 następuje zamiana wartości tekstowej na tablicę znaków (w zasadzie wartość string w języku C# możemy traktować jako tablicę char — dla czytelności przypisują ją do osobnej tablicy). W kolejnej linii następuje odwrócenie tak, by poszczególne bity były w odpowiedniej kolejności. Wspominałem o tym chwilę wyżej, że na wartość binarną patrzymy od końca.

Właściwa część metody wykonuje się w pętli for, która jest odwzorowaniem mnożenia i dodawania, o którym napisałem wyżej. W iteracjach pętli sprawdzamy, czy badany aktualnie element tablicy ma wartość 1. Gdy jest to pierwsza iteracja pętli, wtedy dodajemy jeden, w innym przypadku następuje podniesienie dwójki do potęgi odpowiadającej aktualnemu numerowi iteracji. Warto się nad tym kodem chwilę zastanowić i zderzyć z pokolorowanym wyżej przykładem (binarną wartość 01001 trzeba do funkcji wprowadzić jako „nieodwróconą”, czyli 10010).

static int BinaryToDec(string input)
{
    char[] array = input.ToCharArray();
    Array.Reverse(array);

    int sum = 0;

    for (int i = 0; i < array.Length; i++)
    {
        if (array[i] == '1')
        {
            if (i == 0)
            {
                sum += 1;
            }
            else
            {
                 sum += (int)Math.Pow(2, i);
             }
         }
     }

    return sum;
}

Metoda DecToBinary

Drugi z cichych bohaterów. Funkcja trochę bardziej skomplikowana niż poprzednia. O ile w metodzie wyżej skupialiśmy się na podnoszeniu dwójki do kolejnej potęgi, o tyle tu wartość liczbową dzielimy z każdym kolejnym cyklem przez 2.

Metoda DecToBinary na wejściu przyjmuje dwa parametry. Wartość tekstową, którą będziemy konwertować oraz rozmiar, który reprezentuje ilość zwracanych bitów. Pierwsze trzy linie to deklaracja tablicy, w której przetrzymany zostanie wynik konwersji, zmienne typu int potrzebne do obsługi dwóch pętli oraz deklaracja zmiennej string, która zostanie zwrócona na końcu metody. Zostawiłem tu kolejne miejsce, które aż się prosi o refaktoryzację, dlatego pozostawiam to zadanie Tobie czytelniku.

Pierwsza pętla (linie 104-111) zawiera sprytny mechanizm, a mianowicie operacja wyznaczania reszty z dzielenia, zwane inaczej modulo. Dzięki temu z każdym obrotem pętli do tablicy dodajemy resztę z dzielenia. Jeżeli liczba jest nieparzysta, to w odpowiednie miejsce wstawiamy 1, inaczej 0. Teraz następuje zmniejszenie liczby o połowę i kolejna iteracja pętli. Poniżej rysunek, który obrazuje działanie wspomnianej pętli na przykładzie liczby 22.

Zapis daty - przykład konwersji dziesiętnej na binarną
Rysunek 1. Zamiana liczby 22 na wartość binarną 10110.

Liczbę 22 dzielimy przez 2, otrzymujemy 11 i resztę z dzielenia równą 0, w kolejnym kroku mamy wartość 11, która po podzieleniu na pół zwraca nam 5 oraz resztę 1, z 5 postępujemy analogicznie, czyli po podziale na pół mamy 2 plus resztę z dzielenia, która reprezentowana jest przez 1 (każda wartość z resztą jest zaokrąglana w dół do pełnej liczby, a reszta 0.5 reprezentowana jest przez wartość 1).

Wynik z prawej kolumny odczytujemy od dołu do góry i dzięki temu 22 zapisane dziesiętnie to 10110 zapisane binarnie. 

Druga pętla (linie 113-116) wykonują operację przypisania do zmiennej tekstowej wartości poszczególnych elementów tablicy w kolejności odwrotnej do tego, jak została ona wyżej uzupełniona. Odwróconą kolejność widać również na rysunku powyżej, o czym wspominałem.

static string DecToBinary(string input, int size)
{
    int[] a = new int[size];
    int i, counter, inputInt = int.Parse(input);
    string returnInt = "";

    for (counter = 0; inputInt > 0; counter++)
    {
        if (inputInt > 0)
        {
            a[counter] = inputInt % 2;
            inputInt = inputInt / 2;
        }
     }

     for (i = size - 1; i >= 0; i--)
     {
         returnInt += a[i];
     }

     return returnInt;
}

Słowem zakończenia

Miałem ochotę to zadanie napisać w bardziej zwięzły sposób, ale miałbym trudność opisać je później z takimi szczegółami jak powyżej. Celowo zostawiałem parę furtek, które pozwolą na zabawę z kodem i optymalizację. 

Czas rozwiązania zadania to jakieś 15 minut, plus kilka minut na ewentualne poprawki. Zachęcam do samodzielnej zabawy i czerpania frajdy z tego typu programistycznych problemów. 

Format daty — pełen kod

using System;
using System.Linq;

namespace WI_DATY
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Podaj datę w formacie binarnym lub ISO 8601:");
            string dateFormatted = Console.ReadLine();
            string year = "", month = "", day = "";
            int monthInt = 0, dayInt = 0, yearInt = 0;

            int count = dateFormatted.Count();
            if (count == 10)
            {
                var splittedData = dateFormatted.Split('-');

                if (splittedData.Count() == 3)
                {
                    year = DecToBinary((int.Parse(splittedData[0]) - 1980).ToString(), 7);
                    month = DecToBinary(splittedData[1], 4);
                    day = DecToBinary(splittedData[2], 5);

                    Console.WriteLine(year + month + day);
                }
                else
                {
                    Console.WriteLine("ERROR");
                    return;
                }
            }
            else if (count == 16)
            {
                year = (1980 + BinaryToDec(dateFormatted.Substring(0, 7))).ToString();
                month = BinaryToDec(dateFormatted.Substring(7, 4)).ToString();
                day = BinaryToDec(dateFormatted.Substring(11, 5)).ToString();

                yearInt = int.Parse(year);
                monthInt = int.Parse(month);
                dayInt = int.Parse(day);

                if (
                    monthInt > 12 ||
                    monthInt < 1 ||
                    dayInt < 1 ||
                    ((monthInt == 4 || monthInt == 6 || monthInt == 9 || monthInt == 11) &amp;&amp; dayInt > 30) ||
                    (monthInt == 2 &amp;&amp; dayInt > 29 &amp;&amp; (yearInt % 4 == 0 &amp;&amp; yearInt % 100 != 0)) ||
                    (monthInt == 2 &amp;&amp; dayInt > 28 &amp;&amp; (yearInt % 4 != 0 || yearInt % 100 == 0))
                    )
                {
                    Console.WriteLine("ERROR");
                    return;
                }
                else
                {
                    if (month.Count() == 1)
                        month = "0" + month;
                    if (day.Count() == 1)
                        day = "0" + day;

                    Console.WriteLine(year + "-" + month + "-" + day);
                }
            }
            else
            {
                Console.WriteLine("ERROR");
                return;
            }
        }

        static int BinaryToDec(string input)
        {
            char[] array = input.ToCharArray();
            Array.Reverse(array);

            int sum = 0;

            for (int i = 0; i < array.Length; i++)
            {
                if (array[i] == '1')
                {
                    if (i == 0)
                    {
                        sum += 1;
                    }
                    else
                    {
                        sum += (int)Math.Pow(2, i);
                    }
                }
            }

            return sum;
        }

        static string DecToBinary(string input, int size)
        {
            int[] a = new int[size];
            int i, counter, inputInt = int.Parse(input);
            string returnInt = "";

            for (counter = 0; inputInt > 0; counter++)
            {
                if (inputInt > 0)
                {
                    a[counter] = inputInt % 2;
                    inputInt = inputInt / 2;
                }
            }

            for (i = size - 1; i >= 0; i--)
            {
                returnInt += a[i];
            }

            return returnInt;
        }
    }
}

Podsumowanie

SPOJ to miejsce, na które trafiłem w 2011 roku jeszcze za czasów nauki w szkole średniej. Mamy tam dostępne naprawdę zróżnicowane problemy i musisz mi uwierzyć, każde poprawnie rozwiązane zadanie (nawet te najbardziej banalne) sprawiają ogromną frajdę. 

Przedstawione w tym wpisie zadanie jest z gatunku tych „średnich” jednak jak widać, można w trochę ponad 100 liniach kodu rozwiązać zadanie, które na pierwszy rzut oka wydaje się skomplikowane.

Sposobów rozwiązania problemu jest tyle, ilu jest programistów podejmujących się zadania.

Chcę zaznaczyć, że kod przedstawiający format daty jest akceptowane, lecz nie jest idealnie napisany. Można napisać go bardziej wydajnie, bardziej elegancko i w dużo mniejsze ilości linii. Jednak nie o to mi chodziło, celowo dałem parę elementów do refaktoryzacji i można to potraktować jako zadanie domowe. Wybór języka również nie gra tu roli. Równie dobrze mogłem napisać rozwiązanie w C++, Python czy Java (nie ukrywam, że z czasem nie pojawią się rozwiązania tego zadania w tych językach). Ważny jest sposób myślenia i podejścia do tematu — mniej istotna technologia. 

Kolejny, jubileuszowy, bo 10 wpis będzie na temat grafów.

Poniżej jak co tydzień zostawiam dawkę wiedzy w postaci dwóch książek!

PS. Będę wdzięczny za komentarze pod tym postem!

PS2. Czeka też na Ciebie prezent. Wystarczy, że zapiszesz się na Newsletter poniżej!

PS3. Dołącz do naszej grupy na Facebook!


Subskrybuj

Zapisz się na Newsletter, odbierz NAGRODĘ w postaci e-booka z 10 omówionymi algorytmami pojawiającymi się w pytaniach podczas REKRUTACJI..

Dodatkowo otrzymuj co niedzielę informacje na temat nowych wpisów, wiadomości ze świata IT i matematyki oraz ciekawych wydarzeniach. Nie przegap i dołącz już dziś do 959 osób!.
Autor

👨‍💻 .NET and Python programming passionate 🏦 Digtial Banking Solutions 🎓 Student 📊 Psychology 📚 Bookworm 🏠 Warsaw

Napisz komentarz

Witryna wykorzystuje Akismet, aby ograniczyć spam. Dowiedz się więcej jak przetwarzane są dane komentarzy.