Saturday, December 15, 2007

Annotation on XObject from LINQ to XML

Annotation is something like tag or helper object on XML node. You could register multiple annotations. It is registered under signature of method which was used for registration. So when you are registering some classes with common interface, cast the registered instance to the interface first!
To get annotation of value type you will need to use typeof() as parameter.
interface IHandler { void Handle(XElement e);}
class CatHandler : IHandler
{
    public void Handle(XElement e) 
    { Console.WriteLine(e.Attribute("Food").Value); }
}
class DogHandler : IHandler
{
    public void Handle(XElement e) 
    { Console.WriteLine(e.Element("Friend").Value); }
}

class Test
{
static void Main(string[] args)
{
    List<XElement> list=new List<XElement>()
    {
        new XElement("Creature", 
            new XElement("Name", "Bijou"), 
            new XAttribute("Food", "milk"),
            new XAttribute("Type", "Cat")),
        new XElement("Creature", 
            new XElement("Name", "Goro"),
            new XElement("Friend", "Reiko"),
            new XAttribute("Type", "Dog"))
    };

    //registration
    foreach (XElement element in list)
    {
        switch(element.Attribute("Type").Value)
        {
        case "Cat" : 
            element.AddAnnotation((IHandler)new CatHandler());
            break;
        case "Dog" : 
            element.AddAnnotation((IHandler)new DogHandler());
            break;
        }
    }

    //usage
    foreach (XElement element in list)
    {
        element.Annotation<IHandler>().Handle(element);
    }
}
}

Thursday, December 6, 2007

Jabber behind corporate firewall at 443

Maybe everyone know it. Until recently I had open all ports to the Internet so I used 5222 and 5223. But now I'm behind some rude firewall. I realized that both Jabber servers I'm using are listening also on port 443! This is conn443.netlab.cz:443 for jabber.cz and talk.google.com:443 for GTalk. So, I'm online again.

Saturday, December 1, 2007

Paranoid Android

By 446F75676C6173204164616D73
2249207468696E6B20796F75206F7567687420746F206B6E6F772049276D2066
65656C696E672076657279206465707265737365642C2220697420736169642E
0A49747320766F69636520776173206C6F7720616E6420686F70656C6573732E
0A224F6820476F642C22206D75747465726564205A6170686F6420616E642073
6C756D70656420696E746F206120736561742E0A2257656C6C2C222073616964
205472696C6C69616E20696E20612062726967687420636F6D70617373696F6E
61746520746F6E652C202268657265277320736F6D657468696E6720746F206F
636375707920796F7520616E64206B65657020796F7572206D696E64206F6666
207468696E67732E220A22497420776F6E277420776F726B2C222064726F6E65
64204D617276696E2C202249206861766520616E20657863657074696F6E616C
6C79206C61726765206D696E642E220A224D617276696E2122207761726E6564
205472696C6C69616E2E0A22416C72696768742C222073616964204D61727669
6E2C20227768617420646F20796F752077616E74206D6520746F20646F3F220A
22476F20646F776E20746F206E756D6265722074776F20656E74727920626179
20616E64206272696E67207468652074776F20616C69656E7320757020686572
6520756E646572207375727665696C6C616E63652E220A576974682061206D69
63726F7365636F6E642070617573652C20616E6420612066696E656C79206361
6C63756C61746564206D6963726F6D6F64756C6174696F6E206F662070697463
6820616E642074696D627265202D206E6F7468696E6720796F7520636F756C64
2061637475616C6C792074616B65206F6666656E6365206174202D204D617276
696E206D616E6167656420746F20636F6E766579206869732075747465722063
6F6E74656D707420616E6420686F72726F72206F6620616C6C207468696E6773
2068756D616E2E0A224A75737420746861743F2220686520736169642E0A2259
65732C222073616964205472696C6C69616E206669726D6C792E0A224920776F
6E277420656E6A6F792069742C222073616964204D617276696E2E

Sunday, November 25, 2007

Manic Miner - theme for Nokia 6230i

I'm probably too old to play with themes on my mobile phone, but old enough to remember good old Manic Miner in days of its greatest glory.

manic

I've spent some time to put the theme together, so you can download it and enjoy it too! I was unable to set icon for Push to talk, does anybody know which item_id to use ?

Editor: S40 Series Studio 1.2
Format: .NTH is renamed zip file, with images and XML inside. To animate gif files they need to be in correct resolution, 208x208 for whole screen and 196x115 for icons for N6230i.

Tuesday, November 13, 2007

Cube21 Silver edition - database of all solutions

Cube21 or Square One is puzzle similar to Rubik's Cube. I'm proud owner of one from Silver edition (which have only two colors) since year 2000. Regular Cube21 has 6 colors. This cube is different from Rubik's mainly by changing it's shape. There are 90 distinct shapes. Good analysis could be found here so I don't need to repeat that now, more Cube21 links below.

Cube21
Because I was always more interested in programming than solving the cube by hands, I started to solve the cube by program. Soon I realized that deep search with some heuristics is not that funny. Same time my friend Berka provoked me to create something more challenging, the database of all shortest solutions.

Now after years I returned to that idea to exercise in new technologies. I implemented analytic part of the work in C#, brute force part in C++/CLI. User interface is done in 3D WPF. Because you will probably not want generate whole database at home, I connected the clients to database on my machine using WCF web service. Finally some of you may not have windows platform at all, but you would like to use the database. So for you I created simple ASP+AJAX form. Now some video of the client GUI solving the cube.

Model

So let's describe the model: cube has 16 pieces (8 small + 8 big). Those small are only of 4 types as my cube has only 2 colors. Big ones are unique. On middle layer, there are 2 halves, connected with axis. When you turn around the axis you must finish 180 degrees, so it has only two states. *We don't need to care about middle layer.* <- Update at the bottom.

Cube21
Now let's assign pieces some (hexadecimal) numbers. It's anticlockwise, first on top then on bottom half. Numbers are assigned on solved cube, so that 01234567-89ABCDEF is sequence of solved cube. Detailed model and guide to your puzzled cube here.

Note that small pieces are there twice so we have permutation of multiset Small 004488CC and big 13579BDF, this will give us 2.2*10^13 permutations. Let's also say that we could consider same all cube configurations which could be transformed to each other without turning left and right half of the cube. So rotation of top, bottom and flipping whole cube is still the same cube. Last note that we will mark solved cube with level 1, there is only cube on that level. When performed any operations with top, bottom and finally make turn of right part, we reached level 2. We could found all cubes on level 2 by doing all possible operations on cube on level 1. Level 3 will be result of all operations on all cubes on level 2, which are not on level 1 or 2. Similarly for other levels.

Notation of moves is (top, bottom), '/' is turn right half, '!' is flip whole cube. For both top and bottom rotation, positive is anticlockwise.

-- Here was Ajax frame with webservice to database. Is gone now.

Algorithmization

This is the best part, rest of the work was just cheery on the cake. My first idea years ago was very naive: do operations on cube model, then search whether cube is in the list of already found cubes and if not add it into the list. This doesn't work long, because growing list of cubes will be slower and slower. So, sort it and binary search ? Not in memory, because count of cubes is cca 6.8*10^9, that could not fit into 32bit memory space. Ok, we could B-tree on disk, maybe even with some existing database engine.

But there is better solution. For each cube configuration = permutation we could assign index of permutation. On such index we will store just level of the cube. But 2.2*10^13 permutations will give us 20 terabytes of data, not good yet. We know that there is 90 shapes, each shape has exact order of small and big pieces. For example CeCeCeCe/CeCeCeCe is shape of solved cube where 'C' is big and 'e' is small piece. So now we have 90 pieces * 2520 permutations of small pieces * 40320 permutations of big pieces. That is 9144576000 permutation and bytes. I guessed that there is no more than 15 levels (actually only 12), so we could use half byte to store level of any cube. This is 4.2 GB, good enough for my PC!

Now we could for each level go through whole database, and when we found some half-byte which is set to current level, we will do all possible operations on the cube which is described by address of such half-byte. Results will be converted back to address of new cube and written to the database, if new cube is not on same or previous level already. Before saving we should normalize the cube to one of 90 shapes, by rotating top, bottom or flipping whole cube.

Well we could save some work in analysis, we could skip all operations on the shape which will lead to same result for example (0,0)/! is same as (6,6)/ for all shapes. Also we could minimalize those shapes which stay in same shape after rotation, for example (3,6) on solved cube will not change shape, just colors. So we could only write that rotated cube, which has minimal index of color permutation. This will eliminate identical cubes from processing in next level.

Now we need some clever paging because is not possible get it all in memory at once with 2GB address space. There helps that transitions are always between pair of shapes, so we could use file of one shape as source and other as target. Memory mapped file is cool solution for shape files (50MB each). Also helps to lazy flush that files. And lastly try to order processing of page pairs in that order, that just few loading and flushing is performed for each file, because disk is slooow. This could be done because shapes don't produce cubes in all other shapes, just neighbor. Also helps that file is created whole at once to prevent fragmentation on disk. Windows Vista paging seems do better work than XP when working with mapped files. To keep busy processors and disk all the time, we could run more threads than we have processor cores, each thread one pair of shapes. When some thread is waiting for disk, other thread is heating the core.

Now we could optimize the operations on the cube. Here comes the C++/Cli. We generate optimized code branch for expanding cubes, specific for source and target shape. We could also optimize computation of index of permutation, because indexes of 2520 and 40320 permutations could be done by hash table and by lookup table on way back to permutation. And we could also do whole turn (rotation of top bottom, turn and rotation of top and bottom as normalization to the shape) just by using bitwise AND, OR and rotation on processor registers. Such operation could be done separately on permutation of small pieces and big pieces 32 bits each. Also prevent CLR to native and back transitions, so code for whole shape file scan should be native code.

Mike Masonjones did probably something similar in year 2005, maybe he had little bit harder problem, as he was solving cube with 6 colors. He had some old machine which was dedicated to the task and was running a year! My algorithm could do it in cca 8 hours. I have Dual core 2.4GHz + 4GB RAM, but I'm still happy with 1000 times speedup.

I had great time playing with that problem and learned lot. Interesting ? Found bug ? Any feedback ? Enjoy !

Numbers about silver edition

Level 11
Level 232
Level 3536
Level 47652
Level 5102204
Level 61296753
Level 715250126
Level 8153335000
Level 91138303312
Level 104067633460
Level 111434709972
Level 12164952
Total 6810804000 configurations.


Download

Source code under LGPL on SourceForge subversion.
GUI client + database creation engine binaries, .NET 3.0 required. Analysis report
Database of shapes in XML


Cube21 Links


Update: This is probably wrong. My idea was that the correction could be made by merging /(0,6)/(0,6)/(0,6) to last three turns when necessary. I currently don't have time to think about it deeply, but it seems to me now, that it wouldn't work for all shapes. I probably it could mean that my database is not 100% correct and that some paths will be one turn longer. It could also force me to store another bit of information in permutation, so disk space required could be twice bigger. I will welcome anyone who will do the fix :-)

Friday, November 9, 2007

FileLoadException when loading C++/CLI module

I created assembly in C++/CLI with some unmanaged code inside. Everything worked perfect as long as it was the executable which I was starting. But later I created some UI in C# which was wrapping that that C++ assembly. And got the problem:

System.IO.FileLoadException: Attempt to load an unverifiable executable with fix ups (IAT with more than 2 sections or a TLS section.) (Exception from HRESULT: 0x80131019).

Solution is that you change C++ assembly from EXE to DLL! There is probably some linker optimization during EXE loading which is not supported by CLR loader.

Tuesday, October 30, 2007

Recapitulation of hunting for developer's job

Last months I was in process of job change, so I attended lots of interviews and now I would like to share my conclusion about that process.

Usually both job aspirants and hiring companies are prepared to examine candidate. But I'm quite surprised that sometimes both parties fail to get/provide useful information in the other direction about the company to the candidate. I understand that companies are brief when advertising job offer, because lot of information could be seen as very internal. Note that candidate is providing very personal information.

But interview should be a meeting with balanced opportunities, as not only company is choosing candidate, but candidate is choosing company as well. Job is a trade, trade works only if both parties like that. I attended few interviews where we spent lot of time speaking about me, but when I started to ask questions about company and team, people had hard time, because they were not prepared for such questions and we also had lack of time to talk about it.

I assembled list of questions which helped me to find (hopefully) right job. I was able to identify what's important for me and what's not. I also used that list to inquire potential employers about their company and work style during the interviews. Hope that the list will help both parties of our society, candidates and companies to speak about important questions.

Those topics below are useful to get birds view of the company. Whether it's healthy, stable and has business background. First of all candidate should try to gather information from the internet, hopefully such information could be found on company's web site.
  • Products, Projects & Customers
  • Business partners, target platforms
  • Structure of customers, market share
  • Business model, licenses, SLA
  • Long-term product vision a strategy

Process. This is how they do That, this has major impact on daily life in company, how they are structured, how rigid process is. Whether you will have opportunity to change something, whether they are agile or not. Stress level, chaos level, amount of boring tasks. You may like to see example of analysis and design documentation. Also product documentation is worth seeing.
  • Development methodology, project management style
  • Work item management. Time tracking
  • How they choose new features, new projects
  • Anaysis, Architecture, Design
  • QA process, Unit testing
  • Configuration management, Deployment
  • Release management

Technologies & tool-set. This is important because older technologies are, bigger effort is spent on problems with infrastructure things. Missing IDE, debuggers, old compilers, missing libraries and components, support for too old hardware count here. Do they use third party components or homegrown ? Do they have right tools for their job ? Can they easily get them ? Are they able to upgrade technology time to time ? You would like to see some example of source code, to see their coding standard, amount of comments and readability.
  • Technologies, IDE, Tools
  • Libraries, components
  • Databases, OR mappers, code generators
  • Source version control, branches, releases, merging, workspaces
  • Long-term technological vision

Working environment.
  • People, communication in team, general mood
  • Education, hard-skills and soft-skills courses
  • Long term vision for local office, head counts
  • Occasional working online from home ?
  • Time to learn new things during work
  • Work vs. life balance in the company
  • Offices, dress code
  • Company events, sport and culture events

I also learned that some recruiting agencies could heavily damage your CV you gave them, even without your knowledge. They do that to assure that the employer don't have direct contact with you. In my case it was removal not only of email address, but also of links to my blog and to my open-source projects. This hurt a lot because there are examples of my work and I could get some extra points there. Also it broke formatting of that document. Next time I will distribute PDF file.

Of course I'm interested in your opinions!

Tuesday, October 23, 2007

Ranking permutations of multiset - more details

I refactored and documented my algorithms, which I described before to be more readable. Now I will try to explain how it work.

So, let's have multi-set, set with repetitions. For example (0,0,1,2). Let's agree that list of permutations will be ordered in lexicographic order. Permutations are indexed from zero.
0012


My algorithms are able to find index of given permutation, this is called Rank(). And for given index generate the permutation, this is called Unrank(). Now I will explain Unrank(), which is easier to understand. Let's try to find permutation with index 7 from total 12 possible permutations.
0012-2
We will iterate thru all 4 positions from,left to right and identify members of multiset which should be there. We fill now follow the first iteration of outer loop in algo below. So for first position, you can already see that we should choose member type 1, but in the algo we don't know it yet. Let's look at first column, what possibilities we have.
0012-2
As you can see, there is imbalance between number of permutations which start with member type 0. This is caused by fact that member type 0 appears twice in input multiset. Or from other viewpoint the number of possibilities (permutations) for sub-multisets is bigger for (0,1,2) than for (0,0,1) or (0,0,2). Those sub-multisets are defined as original multiset without member already used (chosen).
0012-2

Back to row on index 7, so we will shrink index(in range of potential) to fit to range of length. Then we will scan for offset of group which has selector inside of it's range. For our example it will be group of type 1 starting at offset 6. Now after some expanding we will subtract offset from index (we will shift base), so that all possible indexes are in range of new potential which is computed on next line. This potential is potential of sub-multiset of remaining, not yet used members. The new index (for our example) for that sub-multiset is 1. Outer loop will process next column now.

Now it should be easy follow the algo. Note that number of permutation is called 'potential' here and that some helper structures were filled before call to that method.
function Unrank(permutationIndex)
{
    // initialize: length, maximal potential and counts could be prepared for all ranking operation on same multiset
    currentPotential = maxPotential;
    currentLength = length;
    currentCounts[] = preparedCounts[];

    for each position from left
    {
        // note that 
        //  - sum of count of all currenttly remaining types is length of multiset
        //  - current potential is sum of potentials of sub-multisets
        
        // compute selector, which is just rank shrink to be in range between zero and current length of multiset
        selector = ((permutationIndex * currentLength) / currentPotential);
    
        // initialize
        offset = 0; type = 0;
    
        // scanning for offset of sub-multiset in which range selector could be found
        while ((offset + currentCounts[type]) <= selector)
        {
            offset += currentCounts[type];
            type++;
        }
    
        // remove consumed offset
        permutationIndex -= (currentPotential * offset) / currentLength;
    
        // compute potential of sub-multiset
        currentPotential = (currentPotential * currentCounts[type]) / currentLength;
    
        // consume type
        currentCounts[type]--;
        
        // store chosen type
        result[position] = type;
    }
    return result;
}

Ranking is very similar to this, but just inverse.

Ideas

It would be much better if we could have faster algo which will have only single loop thru positions, even when order of permutations wouldn't be lexicographical.

In simple example like one above, it could seem that solution is easy. Just pick type of current member which is on index of selector (in buffer of remaining unused members). Then swap that member from buffer of remaining members. But this will introduce problem for multisets where length of set is aliqant (not divisor) of permutation potential. This work in my algo, because when all members of same type are together, decimal fragments of such division is always inside one group (type). But swapping of already used members with unused ones broke groups of members of same type. This swapping idea works for ranking of set, because all sub-sets have same potential.
0012

Above is example of problematic multiset. Note that on first position we are choosing 1/6 permutations, in my algo by scanning for offset of group. But for swapped buffer we should find constant time function which will give member type with correct distribution for all permutations of working buffer (because buffer state/permutation could be heritage of ranking wider multiset).

I know that algo could be probably made bit faster by swapping out empty slots from currentCounts[] array. But this will help just a bit and will broke lexicographical order, while it will complicate algo lot. I don't think it's worth of trying for mid-sized sets.

I'am interested to hear your ideas! And of course corrections if I missed something.

Clarification 13.4.2008:

Whole algorithm is not designed for permutating of small multisets, because such small ones could be easily precomputed and stored in memory for reuse. Let's talk about multiset of 2*A, 2*B, 2*C ... 2*J or something like that. This (2*10)! / ((2!)*10), a big space.
My algo could find one rank in O(10*2*(10/2)) = circa 100 operations. (some of them are quite big, but constant time)
Also notice that reasonable limit for size of space is 64bit or 128bit numbers, so that it could fit into CPU register and allow for constant time operations.
I'm looking for something faster in terms of computational complexity. Linear not quadratic.

Monday, October 8, 2007

GET single byte from big binary file using JavaScript and XMLHttpRequest

Full example and testing page

For FireFox, trick is to map bytes to user part of unicode.
(Idea by mgran)
xmlhttp.open("GET", fileName, false);
xmlhttp.setRequestHeader("Range", "bytes="+position+"-"+position);
if (navigator.userAgent.indexOf("MSIE") == -1)
{
    eval("xmlhttp.overrideMimeType('text/plain; charset=x-user-defined')");
}
xmlhttp.send(null)
return xmlhttp.responseText.charCodeAt(0) & 0xFF; 
For Explorer in VBScript, because it is possible to access responseBody in VB but is not possible to overrideMimeType in IE.
(Idea by mgran's reader)
Function readbyteIE(fileName, position)
Dim xhr
Set xhr = CreateObject("Microsoft.XMLHTTP")

xhr.Open "GET", fileName, False
xhr.setRequestHeader "Range", "bytes=" & position & "-" & position
xhr.send Null

readbyteIE=AscB(MidB(xhr.responseBody, 1, 1)) 
End Function
Credits to mgran and his readers

PS: I'm new in browser scripting. Please correct me if I missed something.

Wednesday, October 3, 2007

Playing with C++/CLI

Few things to note for comfort transition from C# to C++/CLI Pragmas
// use on base level, outside of namespace
#pragma unmanaged
#pragma managed

//Regions
#pragma region Helpers
#pragma endregion
Needed rotate, not just shift
//native
#define asm_ror(val, shift) __asm { ror val,shift }
#define asm_rol(val, shift) __asm { rol val,shift }

//managed
#define managed_ror(val, shift) val=((val>>shift)|(val<<(32-shift)))
#define managed_rol(val, shift) val=((val<<shift)|(val>>(32-shift)))
Nested namespaces
namespace Zamboch
{
 namespace Engine
 {
...
 }
}
Calling to native code and back to CLR
#pragma once

#include <vcclr.h>
using namespace System;
using namespace System::Runtime::InteropServices;


#pragma unmanaged

extern "C" { 
    typedef void* (__stdcall *myCALLBACK)(int smallIndex);
}

// static pointer to managed function
myCALLBACK fnGetDataPage;

void foo()
{
    //Calling back to CLR
    void* dtpage=fnGetDataPage(1);
}

#pragma managed

ref class Class1
{
public:
    // testing entrypoint
    static void Main()
    {
        //Call to native
        foo();
    }

    //callback implementation
    static void* GetDataPage(int smallIndex)
    {
        void* dtpage = NULL;
        return dtpage;
    }

private:
#pragma region Delegate initialization

    delegate void* myCALLBACKDelegate(int smallIndex);

    static GCHandle gch;

    //static constructor, initialize delegate here
    static Class1()
    {
        myCALLBACKDelegate^ fp=gcnew myCALLBACKDelegate(GetDataPage);
        gch = GCHandle::Alloc(fp);
        fnGetDataPage = static_cast<myCALLBACK>(Marshal::GetFunctionPointerForDelegate(fp).ToPointer());
    }

#pragma endregion

};

Tuesday, October 2, 2007

Ranking and unranking permutations of multiset

Few years ago I started to play with my toy Cube21 programaticaly. I will probably write another article about that later. For that toy needed to get index of permutation of multiset (set with repetitions). I searched internet and was unable to find any algorithm which could do that. Best match I have found those days was Myrvold&Ruskey's Ranking of permutation. Very nice algo, but I needed multiset, so I developed one.

So, now I'm playing with toy again and decided to share my ranking algorithm with community.

This is C# class with two methods which are inverse. First will give you index of permutation, second permutation on index. You should initialize instance of class for particular multiset. Order of permutations is lexicographic. Also note, that this implementation operates on int data type, so it should be rewritten for bigger permutations.

Myrvold&Ruskey were able to create linear time algo (with number of set members). I tried hard, but for multiset I was unable to reach better time than circa O(n*(t/2)), where n is number of members and t is number of types of members (or members without repetitions).

I'm interested to learn more about topic, so please share your thoughts. Or if you have faster algo, please, let me know.

There is also zip file with whole VS solution.

Update More detailed explanation.

Monday, August 6, 2007

Redirect network to virtual interface programaticaly

Problem: Temporarily disconnect/redirect network interface, but still allow applications to open sockets on the end point. Simulate cable unplug.

Solution: Create virtual interface using Microsoft loopback adapter and redirect network address to it.

1) To install loopback adapter using devcon.exe folow this KB link.

2) Redirect network interface using netsh.exe learn something here

To change network address on interface use netsh commands add and remove in this order instead of "set" command. It will work for both single IP and multi IP interface.

It work without any reboot and MS loopback driver is signed.

Tuesday, July 31, 2007

Thursday, July 19, 2007

Tribute to Ant Attack

To learn Silverligt and have some fun I reused idea of Ant Attack. I was completely new to both SL and XAML and managed to learn basics during few nights. I implemented 3d view using transparent .png of cube. I know this is not rocket science, but it works. I have lot of ideas where to improve it, but most funny task would be add ants and implement their AI in Python, so you will be able to change AI script as an user. Anyone interested ?

Lesons learned:

  1. SL 1.1alpha supports transparency only in 24bit color + 8 bit alpha format. It could be converted in Blend
  2. ZIndex is slooow, use Remove() and Insert() methods on Children[] collection instead
  3. DoubleAnimation will stop animation on some non-integer number, so my pixelized cubes will be blured by antialiasing. Not nice.

Enjoy the Antesher City