Monday, April 22, 2013

Moving...

So I decided to move to another platform, cause of some limited editing options here on blogger. I will still let this blog up, in case there were some links on it.

Sunday, April 7, 2013

Cooking demo coding assignment from Facebook.

I've bumped into facebook programming competition, which is not really a competition, however when you preform a good score in that timeframe u'll get definetly interviewed.

No, I did not went for it, however before proceeding there is a demo problem which got me interested. It's all about the Hanoi tower problem more specifically the general case, where the number of pegs and discs can vary. Lol I just realize that its "pegs" not "kegs". Well if you take a look on my code you will see I've used "kegs"...


I won't go into details about the problem, but describe my logic of solving it.

If you want to try it, you should download my burning-libraries repo and put it into the same folder as burning-recipes.

Let's say you are in your home directory, then enter:
~/ $ git clone https://github.com/burninggramma/burning-recipes.git
~/ $ git clone https://github.com/burninggramma/burning-libraries.git

After this follow the instruction in the README.md.

I've looked around and turns out there is no explicit solution after a small dimension. It is still an open problem, so if you feel up for it, you can get some fame! [:

I like these problems because they are a nice demonstration of computing power. We can solve them just generating all the possibilities and use a nice graph algorithm.

So let's dig into, how to solve this:

  1. Assume a starting state S ( like: every disk is on the first peg, there are 10 pegs and every disc should be on the last one ).
  2. From S you have some options ( putting the first disc on the second, the third ... ) which can bring you into another states ( A, B, C ... ).
  3. Lets mark the end state ( when every disc is on the last peg ) with T.
  4. With this notation you can imagine a directed graph, where every edge has the weight of one and the nodes are the different states ( S, A, B, C ... , T ).
  5. Lets build this graph by trying always every possible moves.
  6. You probably have heard about graph algorithms, there are quite a few of 'em, so lets choose a shortest-path algorithm like A* cause it's easy to implement.
  7. With such an algorithm we can find the shortest path between S and T.
  8. Tadaaa, finished!

The tricky part is to build the graph, the A* is not that big of a deal.




Wednesday, January 30, 2013

First open source contribution!

I've always wanted to contribute into some open-source project, but 'til yet I didn't find any project where I would dive into the TODO list and start working on features. Anyhow, this wasn't the case now either, but as I was using the gem websocket-rails, I've encountered a bug. After some time spent debugging I managed to fix the problem.

Then I decided to make a pull request about it. As a good droid, I've added some rspec tests for it and finally my pull request was merged into master. Hurray!

For this post to actually mean something I would like to write a few words about the gem.

The gem websocket-rails is a framework for using websockets inside rails applications. Websockets are a duplex channels simulating continuos connection between the browser (using javascript) and the server application, in our case rails. This way you can implement more network-heavy applications where the responsiveness of an app is critical. Let's say for example an online multiplayer game with HTML5 canvas. With this framework it does give a good starting point.

No need to go into any details, 'cause the github page of the project is very nicley documented. Props goes to DanKnox for the gem, thanks!

Saturday, November 3, 2012

Solution of the min coin change problem.

I was just rambling around on SO, when I bumped into a question which was not that trivial as I first thought.

It is the min-coin change problem. First I naturally went for the greedy solution then the owner of the question clarified me, that he's looking for the solution, which minimizes the count of the needed coins. So I start giggling googling like crazy. From page to page, wiki to wiki, but could not find any simple solution out there in the open.

Okay, let's do this I say! The solution you can find on my GitHub repo. I think it's quite selfexplenatory and I've inserted some comments around. Still I want to write down how I was thinking:

1. If I find all the solutions I could just select the one one of the least coin using solution. To make this effectiver and simpler, I will use a map, where the key will be the coins used for the solution and the value of course the solution itself.

2. I will need somehow to iterate from one solution to the other, hmm LETS FIND ALL THE INVARIANTS. Actually one good will be enough. When calculating a solution ( after the first iteration ), I will fix the count of the biggest type of used coins and decrease this on every step. For this to work I will need to begin with the solution which uses the most of the biggest type of coins, whaaat, I already got a solution for that, the greedy solution! HURRAY.

3. When will it stop? Sh*t, I know! When it reaches a solution where it uses only the lowest kind of coins.

However with this simple solutions there are some prequesits with the problem:
  • the useable coin array needs to be given like an increasing serie
  • the amount needs to return zero for MOD lowest_type_of_coin

Then there is nothing much to do, just use the first element of the solutions map, because on the lowest key, one can find the solution with the lowest coins necessary.

There could be more generalization and input handling in the code, but I don't think it's worth that much attention.  The prequesits could be easly solved with few lines.

Sunday, October 21, 2012

Rat Attack on saturday night!

Of course I stay home and code on saturday nights, what else?

The first problem I chose is called Rat Attack! It's from the UVA online judge, not sure what's goin' on, but they unreachable at the moment:

PING onlinejudge.org (157.88.129.177) 56(84) bytes of data.
^C
--- onlinejudge.org ping statistics ---
7 packets transmitted, 0 received, 100% packet loss, time 6008ms


In the meantime I decided to go for a raspberry pie cause I've always wanted one but the weak I/O kinda kept me back always. However the GERTBOARD is here, which pratically extends the pie into or actually more then an arduino, so it can be used effeciently for robotics. I did some robotics on a course and wanted to go for more but the dark force kept me away! There is a new subdomain/subtopic forming on stackexchange which I think will be very useful, I kinda wonder, how come it's under creation. There is a link for You, if You want in!


 Stack Exchange Q&A site proposal: Robotics

Thursday, October 4, 2012

Meanwhile cooking.

Guessed I'd be faster, but it's just the usual truth: calculate a timing... then multiply it by 3, then maybe by dat time U will finish describing what the actual problem is.

Gramma just wanted to post some link for you guys:
I'll  post a choosen problem/solution/test from UVa Online Judge on the next week.

Saturday, September 29, 2012

The beginning - a typical problem for an interview

So, I finished university and started to look for some job as a junior droid coder.

On the road, bricked with traps and pitfalls, lots of time I was asked for code sample or experience ofc. If you haven't ever contributed into open source project * what u should do *, or u got no project which u want to show, then what could u?

I had some preinterview tests, where I received a non-trivial problem to solve. Some of them I couldn't solve, and that got me frustrated, so I decided to try to make "solving of headcracker problems" into a habbit.

This is where the two connects. You prepare for future interviews both with code sample and with knowledge. Ok its all good, but how-where do I get these kind of problem descriptions?

Lots of that out there, but its critical, that one needs to see the statistics about the result of his/her own code ( and some other dudes ). If you aren't that practiced in testing extreme inputs, most of the time this will be done by these providers. For some extra its always good, if your result is available online too, you can link it in your CV or something.

This months problem on codilty, is a good start I think. Because of copyrights I won't paste the problem here, but as the problem expires, I'll post my solution, and part of that will contain the problems description.

Go ahead, solve it!