niedziela, 21 lipca 2013

Proste filtry graficzne w Processing : zrozumieć zapis koloru

Strasznie mi wstyd, że od miesiąca nie znalazłem czasu, by tu zajrzeć.
Dziś wrócę do moich korzeni, czyli styku programowania i grafiki komputerowej. Chciałbym pokazać osobom mniej zaawansowanym jak napisać prosty filtr do obrazu statycznego. Będę pracował nad zdjęciem Cateriny, której fotkę można znaleźć tu: http://commons.wikimedia.org/wiki/File:Luca_Patrone_Caterina_in_autumn.jpg Obraz pochodzi z Wikicommons, czyli możemy z niego legalnie i za darmo korzystać; objęty jest licencją CC BY-SA (tutaj możesz poczytać o czym ona mówi). Obraz został znormalizowany i skadrowany.

Filtr, który będę pokazywał nazywa się plamą barwną. Obraz po zadziałaniu filtra winien wyglądać, jakby był malowany farbami. Znajdujące się obok siebie piksele powinny zlać się ze sobą dając efekt plamy, która powstanie poprzez zatarcie drobnych różnic kolorystycznych pomiędzy pikselami. Nie będziemy rozmazywali obrazu.

Zanim jednak, muszę przypomnieć dwie tożsamości z logiki Boole'a. Z tabeli prawdy koniunkcji wynika, że:

W językach C, C++ czy Java (Processing jest nakładką na Java) istnieją dwa operatory koniunkcji. Pojedynczy ampersand (&) oraz podwójny (&&). Użycie podwójnego ampersanda bierze lewe i prawe wyrażenie, i pomiędzy tymi dwoma wyrażeniami oblicza wartość logiczną. Nas bardziej interesuje operator pojedynczego ampersanda. Oba operandy pojedynczego ampersanda (liczby, nie wartości logiczne) są traktowane operatorem koniunkcji w taki sposób, że pierwszy bit pierwszego operandu jest w koniunkcji z pierwszym bitem drugiego operandu, drugi bit pierwszego operandu z drugim bitem drugiego operandu itd.




Na rysunku powyżej pokazałem przykład działania operatora ampersand. Z tożsamości u góry wynika, że te bity drugiego operandu na których są jedynki spowodują przepisanie bitów pierwszego operandu, a tam gdzie drugi operand ma zera, w wyniku znajdą się zera. Aby było szybciej, operację koniunkcji bitowej będę nazywał and-owaniem.

Zakładam, że obraz zapisany jest za pomocą przestrzeni koloru RGB, 24 bity / piksel, w formacie RGBRGBRGB... Załóżmy, że obraz jest w skali szarości, czyli R=G=B. Na ostatnim bicie (prawym, LSB) można zapisać wartość co najwyżej wartość 1, na skrajnie lewym (MSB) co najwyżej 127.

Jesteśmy w skali szarości. Wykonując koniunkcję piksela przez wartość 255 jego wartość się nie zmieni, natomiast jeżeli dwa piksele różnią się minimalnie (o jeden), to gdyby wykonać koniunkcję przez 0b11111110, czyli 254, to różnice między tymi pikselami by się zatarły. Bazując na tej zasadzie będzie wykonywany efekt plamy barwnej. Wpierw na obrazie w skali szarości (znormalizowanym), później kolorowym. Caterina będzie miała ciężki dzień.

Przygotowałem następujący zestaw masek przez które będę and-ował kolejne piksele obrazka:




odpowiadające kolejno wartościom: 0xFF, 0xF8, 0xF0, 0xE0, 0xC0, 0x80. Ponieważ każda z tych masek dotyczy tylko jednej składowej koloru, to w praktyce każdy piksel trzeba będzie and-ować przez 0xFFFFFF, 0xF8F8F8 itd...

Wraz z kolejną maską zacierane będzie coraz więcej informacji o kolorze, co oznacza że coraz liczniejsze grupy pikseli będą miały identyczną wartość.

Uruchomiłem kod generujący maskowanie pikseli zgodnie z opisanym algorytmem. Wyszło tak:


Lewy górny róg obrazu opisuje wartość hex maski użytej do uzyskania obrazu.

Na obrazie kolorowym można spodziewać się efektów dodatkowych. Wartości RGB będą różne, zatem możliwe że dla danego koloru przeand-owanie piksela spowoduje że nie wszystkie składowe koloru ulegną zmianie, a w rezultacie że na obrazie pojawią się kolory, których nigdy nie było. Przykład:


 
Oba kolory po prawej powstały przez przeand-owanie koloru po lewej, lecz tak jak w pierwszym wypadku z zieleni przeszło w zieleń, tak w drugim pojawił się niepodobny kolor. Wracając, na obrazie kolorowym wyszło tak:


Kod generujący powyższe filtr w języku Processing wygląda następująco:


/*
 * Prosty filtr graficzny - efekt barwnej plamy w Processing
 * Copyright (C) 2013  Adam 'foo-script' Rakowski
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.

 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.

 * Źrodło obrazka z przykładu: http://commons.wikimedia.org/wiki/File:Luca_Patrone_Caterina_in_autumn.jpg
 * Obraz na licencji CC BY-SA
 */


PImage przed;

void setup()
{
  przed = loadImage("obraz.jpg");
  if (przed==null)
  {
    print("Obraz nie istnieje");
    return;
  }
  
  size( przed.width*2, przed.height*3);
  
  int[] maski = { 0xf8f8f8, 0xf0f0f0, 0xe0e0e0, 0xc0c0c0, 0x808080 };

  image( przed, 0, 0 );
  for (int w=0; w<3; w++)
    for (int k=0; k<2; k++)
    {
      if (w==0 && k==0) continue;
      image( filtr_plamy(przed, maski[2*w+k-1]) , k*przed.width, w*przed.height);
      text( String.format("%H", maski[2*w+k-1]) , k*przed.width, w*przed.height+10 );
    }
}

PImage filtr_plamy(PImage zrodlo, int maska)
{
  assert(zrodlo != null);
  PImage wynik=przed.get();
  wynik.loadPixels();
  for (int i=0; i<zrodlo.width * zrodlo.height; i++)
    wynik.pixels[i] &= maska;
  return wynik;
}

niedziela, 23 czerwca 2013

Przyszłośc komputerów PC

Na Asymco znalazłem bardzo ciekawy artykuł prezentujący zmianę trendu w sprzedaży komputerów ( mobilnych i wolnostojących ). Wykres nr 4 pokazuje trend wśród sprzedaży nowych urządzeń, nie obejmuje urządzeń już dostępnych na rynku. Wniosek jest jeden: cokolwiek produkujesz, celuj wpierw na platformy mobilne.

Artykuł: http://www.asymco.com/2012/01/17/the-rise-and-fall-of-personal-computing/

sobota, 22 czerwca 2013

Dlaczego polskie uczelnie nie są Stanfordem?

Na Coursera ruszył kurs startupów. Całość realizowana jest przez trzech pracowników naukowych Uniwersytetu Stanforda. Fantastyczne, że kurs ma podejście całościowe; z jednej strony filozofia startupów, problematyka zbierania funduszy, kwestie designu, projektu UI i właściwości niefunkcjonalnych, z drugiej podejście techniczne: HTML5 i Node.js, hostingi, ...

Dlaczego nie jesteśmy Stanfordem? Otóż dlatego, że studenci ogromu polskich uczelni nie są uczeni robienia pieniędzy. Co by nie mówić, edukacja ma służyć właśnie temu i nawet jeżeli nikt za nią nie płaci ( "nikt" w systemie socjalnym jest moim ulubionym słówkiem ), to i tak edukacja zdobywana jest po to, aby więcej zarabiać. Uczestniczę w tym kursie i głównym kryterium oceny jest ocena społeczności sieciowej, tj.:
  • przychód z tytułu mikropłatności (BitCoin)
  • popularność usługi na Facebook
  • popularność usługi na Twitter
Przez tyle lat edukacji w Polsce nigdy nikt nie kazał nam wyprodukować usługi / produktu z zastosowaniem komercyjnym, w celu zdobycia wysokiego udziału, wyeliminowania innego produktu bądź po prostu zarobienia maksymalnej kwoty pieniędzy.

Szkoda. Taki cel zmienia sposób działania, planowania i pokazuje zupełnie nowe podejście do procesu wytwarzania oprogramowania. Przykład: pierwszy rok studiów drugiego stopnia, przedmiot: technologie internetowe. Zadanie: zaprojektować dowolną stronę w czystym html + php + mysql. Założenia:
  • tematyka dowolna
  • żadnych frameworków
  • bez jQuery, Dojo, Backbone, CoffeScript, ...
  • PHP czysty, bez korzystania z bibliotek zewnętrznych
  • HTML5? Niewymagany...
  • Walory użyteczności, innowacyjności: nieoceniane
  • Brak możliwości użycia silnika innego na przykład Ruby / Python / JS
  • Bez wykorzystania narzędzi wersjonowania, trac'u, etc etc etc
  • Ocena przez pryzmat popularności i zarobków? Nie-eee
Po co? A gdybym ja to wiedział.
Szkoda, że nie jesteśmy Stanfordem.

środa, 5 czerwca 2013

Programowanie wizualne : Google Blockly

Wczoraj o analizie algorytmów w Python, dziś nieco o programowaniu wizualnym. Ostatnio miałem okazję, by zderzyć się ze współczesnymi językami wizualnymi stworzonymi dla potrzeb nauczania podstaw programowania. Wyszło średnio, ponieważ większość języków będących zwieńczeniem publikacji / monografii na ten temat albo przestało być rozwijanych, albo dotyczą projektów zamkniętych (np. na potrzeby amerykańskiego wojska). Nie znalazłem niczego, co by łączyło wieloparadygmatowość, licencję WiOO, intuicyjny interface i wygodę analizy działania, debuggowania etc.. Na szczęście po drodze wpadło mi w ręce parę na prawdę fajnych narzędzi. Jedno to UUhistle opisane post wcześniej, kolejne to Blockly ( http://code.google.com/p/blockly/ ). Narzędzie zostało stworzone przez Google jako zestaw komponentów do wizualnego wyrażania programów. Celowo unikam zdania "wizualny język programowania", gdyż Blockly samo w sobie to komponenty. Dopiero z nich utworzono przykładową aplikację Blockly Code ( http://blockly-demo.appspot.com/static/apps/code/en.html ) umożliwiającą programowanie wizualne. Aplikacja jest na licencji WiOO, komponenty też, całość działa w przeglądarce i jest napisana w HTML5. Co jeszcze ciekawsze, interfejs jest dużo lżejszy i wygodniejszy, niż w osławionym MIT Scratchu, a na dodatek kod wyklikany z klocków jest na bieżąco zapisywany także w postaci kodu Python / JavaScript / XML.

Blockly prezentuje się następująco:


Oprócz przedstawionego programu "Code", twórcy przygotowali jeszcze kilka innych aplikacji demonstrujących możliwości, chociażby grafika żółwia oparta o ... mapy Google. Tak, tak, za pomocą instrukcji żółwia prowadzimy żółtego ludzika (tego ze StreetView) po mapie, aby doszedł do celu. Zupełnie jak podczas Juwenaliów ;)

Dla powyższego listingu kod Python wygląda tak:


Dość siermiężnie, natomiast w kontekście nauczania podstaw programowania, myślę że doskonale jest łączyć Blockly i UUhistle. Jedno tworzy kod Python, drugie umożliwia wizualizację. Fajny pakiet do nauczania osób, które nigdy nie miały styczności z programowaniem.



Ponieważ znowu doszły mnie słuchy, że "nigdzie nie wytłumaczono dobrze jak działają wskaźniki", wpadłem na pomysł napisania 3-4 wpisów tłumaczących od zera ideę wskaźników. A nuż komuś to pomoże.

wtorek, 4 czerwca 2013

UUhistle - wizualizacja kodu Python

Moje doświadczenie z nauczaniem programowania pokazało, że uczącym się najtrudniej zrozumieć ideę sekwencyjności (mimo że na logikę zmiana kolejności instrukcji winna mieć znaczenie) oraz pojęcia zagnieżdżenia wywołania funkcji i rekurencji.

Niedawno odkryłem narzędzie UUhistle napisane przez Juhę Sorvę z Universytetu w Aalto, w Finlandii. Aplikacja powstała jako element pracy doktorskiej.

 
Aplikacja umożliwia wizualizację sposobu działania kodu napisanego w Python 2.X, w szczególności wizualizację stanu sterty (dostępne zmienne, ich wartości, do czego odnoszą się referencje), stosu (przy rekurencji) oraz prezentowania sposobu w jaki wykonuje się program. W obszarze "A" znajduje się kod (można wklejać), w obszarze "B" całość jest wizualizowana, natomiast "C" to kontrola wykonania programu. Aplikację można uruchamiać w trybie pojedynczej instrukcji, normalnym, a także ... cofać instrukcje. Z tej przyczyny wyłączono możliwość pracy na strumieniach danych, czyli nie można korzystać z plików, gniazd czy potoków. Oprócz tego wyłączono kilka innych możliwości języka. Najważniejsze braki dotyczą: leniwego wartościowania (yield, generatory), rozwinięcia list, dziedziczenie, rozmiaru biblioteki standardowej, możliwości stosowania lambd. Co ciekawe, klasy jako takie są obsługiwane w ograniczonym zakresie. Wszystkie ograniczenia opisano tutaj.

UUhistle wydaje się być narzędziem stworzonym wyłącznie do wizualizacji najprostszych algorytmów. Idealnie wizualizuje np. dlaczego przy zamianie wartości dwóch zmiennych musi istnieć zmienna pomocnicza. Algorytmy tej klasy trudności mogą być bez trudności realizowane za pomocą UUhistle, natomiast prawdę mówiąc jeżeli ktoś potrzebuje wyrażeń generatorowych i rozumie sens leniwego wartościowania, to prawdopodobnie nie potrzebuje UUhistle w jego podstawowym zastosowaniu.

Aplikacja zajmuje ok. 13MB i nie wymaga instalacji Python.

Przykładowy zrzut z wizualizacji sortowania bąbelkowego:



Zalety:
  • świetna wizualizacja (animacje, kolorowanie, wyodrębnianie struktur kodu) 
  • wizualizuje kod Python, a Python jest dobry w nauczaniu programowania
  • dystrybuowane jako JAR, przenośne + żadnych instalatorów
  • tryb "tutorial", tryb interaktywny
  • darmowy do celów niekomercyjnych

Wady:
  • zamknięta licencja, zamknięty kod (aczkolwiek jak się go otworzy w programie dekompresującym... )
  • okno kodu nie koloruje kodu, nie podpowiada składni
  • nie można zmienić ani zwiększyć czcionki ( Courier 9pt )
Moja prywatna opinia: poza bardzo niedopracowanym oknem kodu, cała aplikacja jest świetnie zrobiona. Bardzo polecam.

środa, 10 kwietnia 2013

FLOSSowa wiosna

Cały czas trwają warsztaty programistyczne organizowane przez SzLUUG. Materiały z dotychczasowych prelekcji dostępne są na stronie. Mimo, że studenci (do których adresowano szkolenie) niezbyt dopisali frekwencją, to pewne że odbędzie się kolejna sesja warsztatowa. Ponownie poruszymy temat Git'a oraz prawdopodobnie rozpoczniemy cykl zajęć wprowadzających do Linux. Podczas szkolenia wyszło, że uczestnicy mają problem z elementarnym rozumieniem działania konsoli systemu. Polecenia echo, czy tworzenie pliku poprzez przekierowanie strumienia do nieistniejącego pliku przerosły niektórych. Chcemy to poprawić. Siła Windowsa nie polega na tym, że jest "łatwy". Windows nie jest łatwy, lecz maskując przez użytkownikiem ogrom możliwości jakie powinien dawać system operacyjny sprawia wrażenie prostego. To dziwne, ale mamy 2013 rok a standardowa konsola Windows dalej nie obsługuje wyrażeń regularnych.

Wracając, chcemy pokazać co powinien dawać użytkownikowi dobry system operacyjny i pokazać co może dać użytkownikowi Linux (bez wywyższania go spośród innych systemów). Chcemy pokazać podstawy poruszania się po systemie, wyjaśnić elementy struktury plikowo-dyskowej i wprowadzić do konsoli, a także podstawowych narzędzi (sed/awk/grep/echo/cat, ...). Może uda mi się wprowadzić po cichu kurs dla nauczycieli pokazujący nauczanie wspomagane komputerowo. Chętnie bym pokazał jak pracować z wykorzystaniem narzędzi z KDE-Edu (np. KStep) , narzędzi Tux4Kids, a także jak ciekawie uczyć nauk z pogranicza matematyki, robotyki i programowania (np. z użyciem Robocode).

Oby się udało ^^


Pomimo małej frekwencji na SzLUUGowych warsztatach z C udało się utworzyć fajny plug-in do programu TuxPaint. Autorem jest Łukasz Dmitrowski, który to został wciągnięty w projekt TuxPaint właśnie dzięki warsztatom. Plugin nazywa się XOR, działa w trybie pędzla (w przeciwieństwie do filtrów typu pełnoekranowego). Efektem jego działania jest utworzenie pod pędzlem mozaiki kolorystycznej. Tło pod pędzlem zostaje zamalowane. Kod znajduje się na GitHubie. Dobra robota, Łukasz :)




Opublikowano listy projektów zaakceptowanych w tegorocznym Google's Summer of Code. Życie jest piękne ^^

środa, 3 kwietnia 2013

Processing : gra w życie

Napisałem wizualizację gry w życie Conway'a w Processing.

Kod wygląda tak:
int ileKomorek=40;
int wysKomorki = 8;
int ileStartowych=300;
boolean[][] przed, po;

int ileSasiadow(int i, int j, int rozmiar)
{
  int ile=0;
  int[] xoff = {
    i-1, i, i+1
  };
  int[] yoff = {
    j-1, j, j+1
  };

  for (int ii=0; ii<3; ii++)
  {
    if (xoff[ii] < 0) xoff[ii]+=rozmiar;
    if (yoff[ii] < 0) yoff[ii]+=rozmiar;
    if (xoff[ii] >= rozmiar) xoff[ii]-=rozmiar;
    if (yoff[ii] >= rozmiar) yoff[ii]-=rozmiar;
  }

  for (int x=0; x<3; x++)
    for (int y=0; y<3; y++)
      if (x!=1 || y!=1)
        if (przed[xoff[x]][yoff[y]]) ile++;

  assert(ile>=0 && ile<=8);
  return ile;
}

void setup()
{
  size(ileKomorek*wysKomorki, ileKomorek*wysKomorki);
  background(255);
  przed = new boolean[ileKomorek][ileKomorek];
  po = new boolean[ileKomorek][ileKomorek];

  int i=0;
  while (i<ileStartowych)
  {
    if (!przed[int(random(0, ileKomorek))][int(random(0, ileKomorek))])
    {
      przed[int(random(0, ileKomorek))][int(random(0, ileKomorek))] = true;
      i++;
    }
  }
  fill(204, 102, 0);
  noStroke();
}

void draw()
{
  background(255);
  for (int i=0; i<ileKomorek; i++)
  {
    for (int j=0; j<ileKomorek; j++)
    {
      if (przed[i][j])
      {
        rect(i*wysKomorki, j*wysKomorki, wysKomorki, wysKomorki);
        po[i][j] = (ileSasiadow(i, j, ileKomorek) >=2 && ileSasiadow(i, j, ileKomorek) <= 3);
      }
      else if (ileSasiadow(i, j, ileKomorek) ==3) po[i][j] = true;
    }
  }

  for (int i=0; i<ileKomorek; i++)
    for (int j=0; j<ileKomorek; j++)
      przed[i][j]=po[i][j];
  delay(1000);
}
A teraz wyobraź sobie, że masz to samo napisać w C++ lub czymś jeszcze bardziej niskopoziomowym.
BTW: Przymierzam się do zrobienia implementacji w Haskell

sobota, 23 marca 2013

Edytor map w MS Excel / LibreOffice Calc

Pare dni temu widziałem prostą gierkę pisaną przez początkującego programistę. Gra polega na chodzeniu ludzikiem (znak ASCII) po mapie rysowanej kodem ASCII. Nie ma szału, ale to doskonały projekt aby wykazać że dobra organizacja kodu ratuje (grzebie) projekt.

Osoba pisząca tą grę wymyśliła sobie problem rysowania mapy w ten sposób, że każda mapa była rysowana oddzielną procedurą. Okey... ale skąd brano topologie mapy? No jasne, że z palca! Każda linia mapy była pisana z palca, znak w znak. W zasadzie procedury rysujące mapy różniły się jedynie sekwencją znaków, a nie samym działaniem. Koszmar :/

Podrzuciłem pomysł rysowania mapy w Excelu. Tak, tak.. w tym arkuszu kalkulacyjnym. Tutaj pokaże to samo używają OpenOffice / LibreOffice Calc, aczkolwiek w Excel też zadziała.

Moja gra będzie oparta na scenariuszu chodzenia po mapie przypominającej labirytnt. Zakładam, że ściany będę oznaczał symbolem "x", podczas gdy punkt startowy gracza oznaczę "@", a punkt docelowy przez "&". Okey, a co ma do tego Excel?

Zaznaczam wszystkie wiersze i kolumny ( przycisk nad wierszem 1, na lewo od kolumny A ), ustalam szerokość kolumny na 0,8 ( zlokalizowane arkusze kalkulacyjne używają przecinka jako separatora części ułamkowej ).


Teraz cały arkusz wygląda mniej-więcej, jakby był złożony z kwadratów. Chciałbym, aby po wstawieniu w komórkę znaku x ta komórka się zaczerniła. Dzięki temu będę lepiej widział jak wygląda rysowana mapa. Aby nie kolorować ręcznie, użyję formatowania warunkowego.
Ustalam 3 reguły:
  • czarne tło dla znaku x
  • zielone tło dla znaku startu @
  • czerwone dla końca &


[ LOffice Calc sprytnie zauważy, że czarny tekst na czarnym tle jest średnio widoczny, więc automatycznie wypełnione na czarno komórki będą miały kolor czcionki zmieniony na biel ]

Mapa wyświetlana na terminalu Windows ma domyślnie 80x25 znaków, czyli plansza w Excel zaczyna się na komórce (A,1) a kończy na (CB, 25). Postawiłem ramkę wokół tego obszaru + zmieniłem domyślne tło na niebieski. Dzięki temu nie przedobrzę z obszarem rysowania.

Tak oto za pomocą stawiania x-ów, jednego startu i jednego końca namalowałem mapę. Tutaj jest ona dużo węższa, niż szerokość terminala, ale to w niczym nie przeszkadza.


Ważne, że to co widać w Excel będzie wiernie odwzorowane na ekranie gracza. Tak zrobioną mapę zapisuję do formatu CSV ( comma separate values ). Jako separator ustawiam średnik ( ; ). Urok formatu CSV polega na tym, że w wypadku danych numerycznych obsługuje go każdy cywilizowany program obliczeniowy - począwszy od R przez Matlaby, MathCADy, Mathematica, Octave, NumPy a kończywszy na Excel i Calc. Dodatkowo ten format jest idealny do parsowania. Prościej się nie da.

Po obejrzeniu tego pliku w dowolnym edytorze tekstowym powinien on wyglądać mniej więcej tak:
Puste komórki zostały pominięte, czyli zapis ;; oznacza, że dana komórka nie miała wartości. Obraz może wydawać się "rozjechany", ale bezproblemowo można go poskładać, tj. usunąć znak separatora, a puste pola zamienić na spację. Terminale używają czcionek monospace, dzięki czemu całość pięknie wyrówna się na ekranie.

Na szybko napisałem funkcję, która realizuje wyświetlenie takiego pliku mapy w formacie CSV na konsoli. Kod:

#include <iostream>
#include <fstream>
using namespace std;

inline void parseLine(string s)
{
 char c;
 char delim=';', fill=' ';
 size_t pos=-1;
 
 if (s.empty()) return;
 
 do {
  pos = s.find(delim, pos+1);
  if ( pos != string::npos )
  {
   if ( pos==0 || s[pos-1]==delim) cout << fill;
   else cout << s[pos-1];
  }
 } while (pos != string::npos);
 
 cout << ( c=s[s.size()-1],c == delim ? fill : c ) << endl;
}

int main()
{
 ifstream mapa("mapa.csv");
 string s;
 

 if (!mapa)
 {
  perror("Blad ladowania mapy");
  return -1;
 }

 while ( !mapa.eof() && mapa )
 {  
  getline(mapa, s);
  parseLine(s);
 }

 mapa.close();
 return 0;
}

W rezultacie całość wygląda w konsoli tak:


Przy tak prostych aplikacjach wysilanie się na własny edytor map jest przerostem formy nad treścią. Bardzo zachęcam do korzystania np. z Calc/Excela w takich sytuacjach.

środa, 20 marca 2013

MongoDB, NoSQL, Spring Data i Strefa 89

Dzisiaj w Strefie 89 obyło się szkolenie z MongoDB prowadzone przez Macieja Walkowiaka ( organizatorem był JUG ). Szkolenie super. Oprócz szybkiego wprowadzenia do idei NoSQL pokazano także Spring Data mongoDB. W zasadzie to 80% szkolenia poświęcone było SDmDB.

Nie jestem przekonany, że Java to najbardziej elastyczny język świata, natomiast wygoda operowania danymi, jaką utworzono w SDmDB bardzo zaskakuje. Łatwość mapowania dokumentów Mongo na klasy, predefiniowane operacje pobrania i filtracji niezależnie od sposobu budowy dokumentu, rozwiązywanie dziedziczenia, etc ... przerosła moje oczekiwania.

Trochę głupio mi to powiedzieć, ale czas powoduje, że przełamuję się do Javy.

Dodatkiem do dobrego wrażenia jest Strefa 89. Niesamowite miejsce z bardzo kreatywnym wnętrznem, barem, przestrzenią co-workingu oraz fajną atmosferą. Lokalizacja w samym centrum Szczecina, prawie na deptaku.

Polecam ^^

sobota, 16 marca 2013

Darmowe wykłady renomowanych uczelni

Otwarte, darmowe kursy prowadzone pod szyldem renomowanych uczelni ( Stanford, Princeton, University of California ... ) z rozmaitych dziedzin: od produkcji muzyki przez antropologię, programowanie i kryptografię.

Wszystko za friko: https://www.coursera.org

sobota, 9 marca 2013

Znalazłem bardzo, bardzo dobry podręcznik do matematyki dla informatyków. Napisany jest lżej, niż "Matematyka konkretna" Grahama. Całość za darmo i dostępna online ^-^

Eric Lehman and Tom Leighton: "Mathematics for Computer Science" - http://www.cs.princeton.edu/courses/archive/spr10/cos433/mathcs.pdf

wtorek, 5 marca 2013

Warsztaty dla studentów piszących w C, Java, PHP

SzLUUG organizuje cykl szkoleń dla studentów wprowadzający w świat "realnego programowania", czyli pracy w środowisku wieloosobowym, z rozbudowaną dokumentacją, metodologią, z dużym kodem źródłowym.
Chcemy pokazać studentom coś nowego + zainteresować ich programowaniem pod Linux (kto nie spróbował nie zrozumie) + zachęcić do FLOSS : jako idei, jako programów i jako sposobu aktywności.

Już w tą niedzielę (10.03) prowadzę warsztat z "realnego programowania" w C. Nie ma mowy o kursie języka. Zakładam, że uczestnicy będą go znać co najmniej w stopniu średniozaawansowanym i ruszymy z Linuxową otoczką programowania w C, czyli:
  • Autotools, bootstrap
  • configure i Makefile
  • Git
  • Czytanie dokumentacji
  • "Coding standards"
  • Branchowanie / diffowanie / commitowanie
  • Valgrind i gdb (oby nie trzeba było ;) )
  • SDL
  • Korzystanie z zewnętrznego API
Będziemy rozwijać projekt TuxPaint tworząc nowe filtry graficzne.

Zapraszam ^-^

poniedziałek, 4 marca 2013

Jak zrobić tablicę wielowymiarową bez tablicy wielowymiarowej

Załóżmy, że trzeba zrobić tablicę wielowymiarową. W C wielowymiarowość jest nieprzyjemna, szczególnie gdy chcemy uniwersalne funkcje operujące na tablicy o dowolnej wymiarowości. W C++ sprawa jest prostsza, bo są wektory, które można wzajemnie zagnieżdżać. Inne, że wygoda takiego rozwiązania jest podobna jak w C, z tym że odpada problem de-re-alokacji.

W Python jest NumPy, czyli jest cudownie ^^

Czy w zasadzie potrzebujemy tablic wielowymiarowych? Programowanie przypomina tworzenie filmu. Ważne jest co zobaczy użytkownik, a nie jak to powstało ( zastanawiam się czy aluzja do parówek nie była by bardziej stosowna ).

Załóżmy, że potrzebujemy napisać w C++ mechanizm wygodnej tablicy 1D, 2D i 3D. Nie chcemy robić wektora wektorów wektorów, bo to nieeleganckie, nieefektywne i siermiężne.

Tablicę dowolnej wymiarowości można trzymać w wektorze. Istnieje mapowanie tablicy dowolnej wymiarowości N na wymiarowość niższą, włączając jednowymiarową. Niech nasza tablica wygląda tak:

, a chcemy ją zapisać za pomocą wektora 1D, czyli szukamy mapowania


 Każde równanie mapujące tablicę ND na MD jest równaniem liniowym. My będziemy chcieli tablicę 2D sprowadzić do 1D. Sprowadzając cokolwiek do 1D nasze równanie będzie zawsze postaci wielowymiarowego równania linowego, np:





To, co stoi po lewej stronie to indeks liniowy, czyli pod którym indeksie w wektorze znajdzie się element, gdy tablicę ND sprowadzimy do wektora. W tym przypadku aby z wektora wydobyć element znajdujący się na w-tym wierszu i w k-tej kolumnie należy posłużyć się dwoma zmiennymi (w,k), czyli równaniem z dwoma zmiennymi:


Ściślej, nasze równanie będzie wyglądało i ( w, k ) = a*w+b*k+c. Niewiadomych ( a, b, c ) pozbędziemy się dzięki układowi równań. Typuję 3 indeksy z mojej tablicy, które posłużą mi do
wyznaczenia stałych ( a, b, c ). Zakładam dla siebie, że wiersze i kolumny indeksujemy od 0. Wektor w którym będziemy trzymać dane też jest indeksowany od 0. Wybrałem te elementy:



czyli dla elementów (w=1, k=2) wyliczam indeks liniowy (2), analogicznie dla elementów (w=1, k=0) oraz (w=1, k=1).


Gdyby wybrać indeks (w=0, k=0), od razu by było widać, że c=0.

Wracając, wśród współczynników widać wartość a=3. Ta trójka to nic innego, jak ilość kolumn w tabeli. Ostatecznie równanie funkcji mapującej 2D -> 1D to:

Widać, że  ilość wierszy nie ma żadnego przełożenia na to, pod jakim indeksem będzie trzymana wartość.

Poniżej kod prezentujący na szybko jak stosować taką tablicę:

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

typedef struct Tab2D
{
 private:
  vector<int> v; //jednowymiarowy
  size_t iw, ik;

 public: 
  typedef pair<size_t, size_t> wymiar;
  
  Tab2D(int w, int k, int wypelnienie=0)
  {
   v.resize( w * k, wypelnienie );
   iw=w;
   ik=k;
  }
  
  int& operator()(size_t indeksLiniowy)
  {
   return v.at ( indeksLiniowy );
  }
  
  int& operator()(size_t w, size_t k)
  {
   return v.at( w*ik + k ); //to wynika z rownania liniowego mapujacego 2D -> 1D
  }
  
  wymiar wezWymiar()
  {
   return make_pair(iw, ik);
  }
  
  void wypisz()     //TYLKO DO CELOW TESTOWYCH
  {
   cout << "-------" << endl;
   for (int w=0; w<iw; w++)
    for (int k=0; k<ik; k++)
     cout << w << ' ' << k  << ' ' << (*this)(w,k) << endl;
  }
 
} Tab2D;

int main()
{
 Tab2D t(3,2);
 
 cout << t.wezWymiar().first << ' ' << t.wezWymiar().second << endl;
 
 t.wypisz();
 
 for (int w=0; w<t.wezWymiar().first; w++)
  for (int k=0; k<t.wezWymiar().second; k++)
   t(w, k) = w+k;

 t.wypisz();

 return 0;
}

niedziela, 3 marca 2013

(C/C++) Smaczki ukryte w operatorach

Krzak pisał o tajemnym operatorze w C: downto, to może też dorzucę coś od siebie ;)

W C i C++ tablice nie są obiektami, natomiast swobodny dostęp do nich realizowany jest przez operator nawiasu kwadratowego. Truizm.

Czy wiesz, że taki kod:
char[] str="Alicja";
std::cout<< str[3] <<endl;

może być zapisany tak:

char[] str="Alicja";
std::cout<< 3[str] <<endl;

Zdziwienie?
W C++ operator [] jest przemienny, tj. tab[i] jest tożsame z i[tab]. To prowadzi do absurdalnych wniosków, jakoby mozna było indeksować liczby tablicami. Owszem, można.

Rozwiązanie zagadki: Tablice w C są wskaźnikami. Formalnie: tworząc tablicę na prawdę uzyskujemy wskaźnik do zadeklarowanego obszaru pamięci. Operator nawiasu kwadratowego na wskaźniku działa następująco:
std::cout<<tab[ind]<<std::endl;
//jest tozsame z
std::cout<<*(tab+ind)<<std::endl;

Skoro dodawanie jest przemienne, to *(tab+ind) jest tożsame z *(ind+tab), czyli ind[tab]. Oto cała tajemnica....

piątek, 1 marca 2013

Testowanie wizualne z Processing

Wspomniałem kiedyś o Processing, który ogromnie cenię za szybkość prototypowania algorytmów i wielopoziomowość. Z jednej strony daje łatwość współpracy obiektami wysokiego poziomu (np. abstrakcyjne struktury danych w Java, systemy okienkowe) oraz niskim poziomem, np. Arduino czy port szeregowy + operacje bitowe.

Pare dni temu siedziałem nad detektorem kolizji dla prostej gry 2D. "Coś" nie działało, więc pierwsze podejrzenie na funkcję analizującą, czy 2 prostokąty nachodzą na siebie. Wyglądało to mniej więcej tak:

boolean doesColide(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2)
{
    return (
                max(ax1, ax2) >= min(bx1, bx2) &&
                min(ax1, ax2) <= max(bx1, bx2) &&
                min(by1, by2) <= max(ay1, ay2) &&
                max(by1, by2) >= min(ay1, ay2)  );
}


Pisanie testów? Zdecydowanie nie. Testowanie interaktywne jest szybsze i łatwiej wypatrzeć gdzie algorytm się nie sprawdza. Przeniosłem kod tej metody do Processing ( czyli Javy :P ), obudowałem wizualizacją (jeden kwadrat nieruchomy, drugi porusza się wraz z kursorem). Jeżeli ruchomy jest zielony - brak kolizji. W przeciwnym wypadku - czerwony.

Czas pisania kodu: 2 minuty. Czas testowania: 2 minuty.
boolean doesColide(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2)
{
    return (
                max(ax1, ax2) >= min(bx1, bx2) &&
                min(ax1, ax2) <= max(bx1, bx2) &&
                min(by1, by2) <= max(ay1, ay2) &&
                max(by1, by2) >= min(ay1, ay2)  );
}

void setup()
{
 size(400, 400);
 background(255); 
}

void draw()
{
  background(255);
  rect(150, 150, 100, 100);
  if (doesColide(mouseX-50, mouseY-50, mouseX+50, mouseY+50, 150, 150, 250, 250) ) 
    fill(255, 0, 0);
  else fill(0, 255, 0);
  rect(mouseX-50, mouseY-50, 100, 100);
  fill(0);
}

środa, 27 lutego 2013

Się dzieje w Szczecinie

W marcu, w Szczecinie odbędzie się kilka imprez branżowych:
Warsztaty są efektem krótkiej rozmowy na liście dyskusyjnej  SzLUUG na temat "co możemy zrobić, aby poprawić jakośc nauczania na WIZUT". Od słowa do słowa padł pomysł nauczenia studentów "czegoś", co z jednej strony wprowadzi ich w świat Open Source, z drugiej strony pozwoli wyjść poza pisanie akademickich programów klasy "struktura zagnieżdżajaca wskaźnik referencji na instancje". Uhhh... Do realizacji dołączył Szczeciński JUG

Gorąco zapraszam na obie imprezy :))) Będę prowadził warsztaty z C ^-^

Plan przewiduje pobranie + ustawienie środowiska programistycznego dla aplikacji TuxPaint oraz napisanie kilku wtyczek ( filtrów graficznych ). Wszystko w duchu pracy grupowej, Git'a, tworzenia dobrej dokumentacji, forków, commitów i Wolnego Oprogramowania. Będzie kreatywnie ^-^

Wciąż mam nadzieję, że kiedyś uda nam się na WIZUT zrobić zrobić imprezę Random Hacks of Kindness...

Stracony czas

Strasznie mi przykro, ale zapomniałem o własnym blogu. Na szczęście od paru dni "wpis do bloga" jest periodykiem w moim kalendarzu, więc nie powinno się to już powtórzyć :)