.NET i takie tam

Sudoku Solver in C#

z 2 uwagami

Another breakable toy, my variation of Sudoku solver. I’ve created it without previously googling the topic, and I was quite surprised when latter I realized that most solutions out there use just dumb trial and error. I was also glad that I can re-invent backtracking algorithm ;)

Ok. let’s start, from having a Sudoku that we want to solve:

sudoku

After a little consideration I decided to solve it by elimination of possible values. Let’s consider first block (by block I mean inner 3×3 cells squares), possible values for empty cells:

Cell \ Value

1

3

6

7

8

9

A1

x

x

x

x

A2

x

x

x

x

A3

x

x

x

x

B2

x

x

x

B3

x

x

x

x

C3

x

x

x

We can see that value 1 can be only in A1 cell so fill it in. Check remaining cells and no single value in a row or column. So we evaluate next block:

Cell \ Value

1

2

3

4

6

A5

x

x

x

B3

x

x

x

x

B4

x

B5

x

x

x

x

C3

x

x

Now value 1 and 6 are only possible in cells B5 and B4 so we fill them in. Check remaining cells after reduction – no single possible values – we go to the next block.

We cycle through all blocks until all cells are filled in (will happen only for very simple Sudoku) or number of empty cells is not changed after a cycle. In the second case, we filled what we could using simple elimination and it’s time for more advanced solving techniques or guessing. This time I choose guessing, maybe later I’ll implement something more original. So we take first empty cell pick its first possible value fill it in and use recursion and backtrack algorithm to check if we can complete the puzzle. If not go back pick next possible value and try again.

That’s it the whole working solution can be found on github. To test the solution I’ve used online solver at http://www.sudokuwiki.org/sudoku.htm . Beside of detail description of different techniques of solving Sudoku, it allows to import and export puzzle as string of numbers which is really helpful.

Next step for me is to implement the same algorithm using less familiar languages. I think of Python, Ruby, JavaScript and Dart, F# and maybe Haskell.

Written by sakowicz

Styczeń 2, 2012 at 10:22 pm

User defined rules and how to host IronPython in .NET application

Skomentuj »

Currently I’m working on a data processing slash financial application where user can define their own processing rules. Those rules are defined in specially created scripting language – sounds impressive, right? Well it’s really interesting piece of code especially for someone like me who never worked before on parsers, tokenizes and all other stuff that is needed to built a compiler/interpreter. But this is also a problem – writing custom language is not a core part of the business. In result language evolved in a direction that was picked as we saw fit at the given moment. That is why we have nice, lean syntactical Frankenstein monster that is working fine with one exception – it’s rather slow.

So conclusion from this situation – if something is not core part of a business and it’s pretty important – think twice before you go and build it. Most likely business won’t spare enough time/money/developers to do this right.

Realizing this we decided to retire our friendly Frankenstein baby and use Python instead.

Python is a dynamic programming language which is getting more traction in recent years. It is used by companies like Google, Yahoo and even NASA. In result of its growing popularity Microsoft decided to create Python implementation for .NET. The project is called IronPython and it was open-sourced not so long ago. Because it is built on .NET using Dynamic Runtime Extensions (DLR) it can be easily integrate with other managed applications.

To embed Python in .NET app it’s enough to reference following assemblies:

  • Microsoft.Scripting.Metadata.dll
  • Microsoft.Scripting.dll
  • Microsoft.Dynamic.dll
  • IronPython.Modules.dll
  • IronPython.dll

And type two lines of code, like below, to execute you first script:

image

This is just simple evaluator – execution of something a bit more complicated let say mixing Python method and C# code, can be achieved like this:

image

After instantiation of necessary objects – ScriptingEngine, ScriptScope etc. about them in a moment, compile a Python method, obtain function delegate from ScriptScope and execute it.

There is four main classes that we need to work with IronPython or any language based on DLR for that matter:

  • ScriptEngine – this is a DLR object that represents language semantics e.g. IronPython, IronRuby etc. It’s responsible for executing code.
  • ScriptScope – essentially this class represents a namespace – it’s used for storing runtime variables. We can execute script in context of multiple ScriptScopes.
  • ScriptSource – represents source code and offers a variety of ways to execute or compile the source.
  • CompiledCode – represents compiled script – can improve performance in case we want to reuse it.

During integration of Python into the project one of the focuses was ability to reuse library of existing domain functions written in C# without burdening a user with knowledge about references, modules etc. How I choose to solve this problem was using ExpandoObject as a vessel for passing rule delegates into Python script. Let’s look at following example:

image

There are two important things here: first script defines function Add which sums two parameters a and b and third value that is obtained from C# function called GetValue(). GetValue in this example is as simple as it can gets:

image

Keyword RULE is global variable that we defined as ExpandoObject and passed to ScriptScope which is used to execute script. ExpandoObject holds delegates to functions we want to use in Python method.

It is possible to use dictionary or some other predefined object – instead Expando but first I think that syntax: variable.function(parameters) fit nicely with Python. Secondly we can add properties dynamically which in case of hundreds built in rules can come in handy. Just add some script analyzer and pass only delegates of required functions.

All above examples and some more can be found here.

Written by sakowicz

Listopad 10, 2011 at 10:25 pm

Napisane w .NET

Tagi: , , ,

Agatha and Request/Response pattern

Skomentuj »

Request/Response pattern is very simple pattern that can make our life easier when working with wcf services. The idea is to wrap all service operation parameters in one object that we call a request and return an object that we call a response. There is few advantages of such approach, the main ones (at least for me) are:

  • You can inherit request and responses from base objects where you can put some common properties like user information, security token or error message.
  • Simplifies versioning of a service
  • Generated proxy is easier to read and understand

Simple right? Sure – that is why I was surprised when I’ve read about framework that was described as a ‘Request/Response Service Layer’. Why the strait forward pattern needs a framework? Is this one of those projects that were created just for sake of creating it? I was almost ready to close the page when I saw a little bit of code that I sub conscience liked:

image
 

One class one operation? Interesting I must admit most services which I was working with – looked like bunch different procedures putted in the same file – procedural, ugly hard to read and understand. Is this possibly a solution?

Please meet Agatha – she will make your life easier or not – depends your preferences. So what this framework is doing? – simply it’s request dispatcher. There is predefined contract with one operation:

image
 

All messages are send to this operation – and Agatha based on request object type is routing it to specific handler. Basic sample can be found here. So what we gain:

  1. proper code separation for service operations – now we have handlers
  2. we can publish only one service for all implemented handlers
  3. no need to update client side proxy when service is changed
  4. authentication, authorization, error logging – can be done just in one place
  5. we can batch requests for traffic optimization – so ‘chatty’ services are not a problem anymore
  6. framework handles client and server endpoints with minimal wcf configuration

So it is nice simple and easy – but only when both client and server are using Agatha. We can still consume service in other languages but it will be awkward – request types will indicate what operation we want to call. One more issue that was actually mentioned by one of my colleagues is lack of clearly defined interface which will make service even more difficult to use by 3rd party.

In summary interesting approach for handling services. Especially if you want to use them for internal clients that you can control. But I would think twice if I had to develop something for greater audience.

You can find Agatha on GitHub. Example application is described here, and here you can find series of post describing framework in more details.

Written by sakowicz

Październik 29, 2011 at 8:04 pm

Napisane w .NET, frameworks, Tools, wcf

Tagi: , , ,

Performance Counters i ich kategorie

Skomentuj »

Performance Counters to taki mechanizm Windows, dzięki któremu możemy oszacować wydajność naszej aplikacji (i nie tylko naszej). Świetnie się również sprawdzają, przy identyfikacji wszelkich problemów z wyciekami pamięci lub przy poszukiwaniu niezamkniętych połączeń do bazy danych. Pełną listę odstępnych ‘liczników’ podzielonych na kategorie można zobaczyć uruchamiając Performance Monitor umieszczony Control Panel -> Administrative Tools.

image

Wszystkie liczniki podzielone są na kategorie – i właśnie z tymi kategoriami miałem problem. Otóż przykładowo, aby stworzyć nową kategorię i dodać do niej nasze liczniki, wywołamy następującą metodą:

CounterCreationDataCollection counters = new CounterCreationDataCollection();

counters.Add(new CounterCreationData("Counter 1",
                                        "Counter 1 Description",
                                        PerformanceCounterType.NumberOfItems32));
counters.Add(new CounterCreationData("Counter 2",
                                        "Counter 2 Description",
                                        PerformanceCounterType.NumberOfItems32));

PerformanceCounterCategory.Create("Nowa Kategoria",
                                    "Nowe Kategoria Description",
                                    PerformanceCounterCategoryType.Unknown, counters);

Fajnie, a co jeśli teraz chcemy dodać nowy licznik do naszej kategorii? No cóż klops – nieco skostniałe API nam tego nie umożliwia, przynajmniej nie bezpośrednio. Otóż, co możemy zrobić to pobrać wszystkie istniejące liczniki, skasować kategorie i utworzyć ja ponownie wzbogacona o nowe liczniki. Przykładowo:

string categoryName = "Nowa Kategoria";

CounterCreationDataCollection counters = new CounterCreationDataCollection();

if (PerformanceCounterCategory.Exists(categoryName))
{
    PerformanceCounterCategory pcc = PerformanceCounterCategory.GetCategories()
                      .Where(c => c.CategoryName == categoryName).FirstOrDefault();

    if (pcc != null)
    {
        var existingCouters = pcc.GetCounters().
                        Select(c => new CounterCreationData()
        {
            CounterName = c.CounterName,
            CounterHelp = c.CounterHelp,
            CounterType = c.CounterType
        }).ToArray();

        counters.AddRange(existingCouters);
    }

    PerformanceCounterCategory.Delete(categoryName);
}

counters.Add(new CounterCreationData("Counter 3",
                                     "Counter 3 Description",
                                     PerformanceCounterType.NumberOfItems32));

PerformanceCounterCategory.Create(categoryName,
                                  categoryName + " Description",
                                  PerformanceCounterCategoryType.Unknown, counters);

Powinno grac i buczeć. Jedno, na co trzeba zwrócić uwagę to, ze możliwy jest mały poślizg z ‘publikacja’ nowego licznika przez Windows. Co może powodować problemy? Gdy instalujemy cos np. serwisy windowsowe z pliku batch – licznik z jednego serwisu jeszcze nie został opublikowany a drugi serwis juz pobiera ich listę, aby je zmodyfikować.

Więcej o Performance Counters można znaleźć tutaj.

Written by sakowicz

Marzec 14, 2011 at 9:39 pm

Napisane w .NET, Aplikacje

Tagi: , , ,

OMG!! My knowledge is gone!!

Skomentuj »

image

Written by sakowicz

Marzec 1, 2011 at 10:22 pm

Napisane w Misc, Tools

Partial Methods

Skomentuj »

Codziennie można nauczyć się czegoś nowego. Dzisiaj odkryłem, że w .NET nie tylko klasy mogą być określane, jako partial, ale również metody. Wygląda to tak:

partial class Account
{
    private decimal _balance;

    public string Balance
    {
        get { return _balance; }
        set
        {
            OnBalanceChanging(value);
            _balance = value;
            OnBalanceChanged();
        }
    }

    partial void OnBalanceChanging(decimal balance);
    partial void OnBalanceChanged();
}

I klasa implementująca metody OnBalanceChanging i OnBalanceChanged:

partial class Account
{
    partial void OnBalanceChanging(decimal balance)
    {
        // do sth
    }

    partial void OnBalanceChanged()
    {
        // do sth
    }
}

Proste przejrzyste i przypominające eventy, prawda? Przykład wykorzystania można znaleźć np. w klasach generowanych przez Entity Framework 4.

Dokumentacja podaje zasady korzystania z partial methods (ciekawe jak by to przetłumaczyć metody cząstkowe, częściowe)?

· metoda musi być oznaczona słowem kluczowym partial i musi być private

· musi zwracać void

· metoda może mieć parametry oznaczone, jako ref, ale już nie, jako out (pewnie, dlatego, że niemożna zagwarantować, że zmienną oznaczoną, jako out zainicjujemy, co jest wymagane przy wykorzystaniu tego modyfikatora)

· metoda może być oznaczona, jako static bądź unsafe

Jeśli zdefiniujemy metodę partial, ale jej nie zaimplementujemy, kompilator po prostu usunie referencję do niej. Niestety, jeśli postąpimy na odwrót tj. będziemy mieli implementację a brak będzie jej definicji, kompilator zgłosi wyjątek.

Written by sakowicz

Luty 28, 2011 at 11:48 pm

Napisane w .NET

Tagi: , , ,

Ceny na Amazonie

z jednym komentarzem

Od jakiegoś roku korzystam z Amazon Kindle DX – świetne urządzenie które polecam każdemu kto sporo czyta szczególnie w podróży. Jednak ceny jakie widzę na Amazonie po prostu mnie wkurzają:

clip_image002

Książka papierowa jest tańsza od elektronicznej? Jak to możliwe? Cały proces od ścięcia drzewa, zrobienia papieru, przygotowania farby, druku, magazynowania aż po wysyłkę do klienta – zawarty jest w cenie wersji papierowej – a ta jest niższa od wersji elektronicznej? Dobra tylko o 9c, ale zakładając, że połowa ceny wersji papierowej to koszty przygotowania i druku – to na elektronicznej przepłacamy 50%. Ile kosztuje przygotowanie wersji elektronicznej, tyle co nic, bo jak książka została złożona i przygotowana do druku – to konwersja do formatu prc, mobi etc. to jest jedno kliknięcie. Dla mnie to już tylko czysta pazerność …

Written by sakowicz

Styczeń 30, 2011 at 4:06 pm

Napisane w Misc

Tagi: , , ,

Follow

Otrzymuj każdy nowy wpis na swoją skrzynkę e-mail.