Moved to Tokyo for Robotics Engineering experience

As a child, I used to watch this American sitcom called "Small Wonder" (https://en.m.wikipedia.org/wiki/Small_Wonder_(TV_series)) which made me go awestruck with the wonders that engineering could create! Coming from a doctors' family, this sitcom was my first hand exposure to what an engineer's life looked like.

Eventually, I ended up studying Computer Science and Engineering myself. But, it was not until now that I really got a chance to do something substantial on the robotics front.

Fast forwarding to about the last quarter this year, I bagged a job opportunity in a field that's an amalgamation of Software Engineering and Robotics! I graciously accepted the offer, changed countries and henceforth, will be working as a Software Development Engineer for Robotic Systems Software out of Tokyo, Japan for this Japanese company - Rapyuta Robotics, whose mission aligns so much with my vision.

I trust, it's all how it was destined to be and I wouldn't have been here without the experience that my previous gigs provided me. The knowledge of Linux systems software that I gained at IBM was definitely a pre-requisite for my current role and equipped with all these skills gained over years, I aim at creating and achieving many more milestones, with my team, for this new found love for empowering lives with connected machines.

That's all for now, and until next time, take care and happy hacking!

Some new problems solved and added to my git repo. last week

Some Stack-based practice programs:

6. COMPILER - My Submissions (directly view-able)
7. MMASS      - My Submissions , Accepted Solution
8. HISTOGRA - My Submissions , Accepted Solution
9. ANARC09A - My Submissions , Accepted Solution

✌😎
~
Happy hacking!

Image source: Google Images

Updates from last 3 weeks or so...

I took part in Codechef's November Challenge (which stretched from 3rd till 13th of Nov.) intermittently solving some of the tough problems (not necessarily quickly) to keep a track of my progress and increase my comfort in solving problems in a long contest setting.

Ranked at 2856 out of 7024 who submitted at-least one problem partially or completely correct, I'd say it was an slight better than average performance. My long-contest rating saw a big boost, but I simultaneously saw a drop in my overall codechef rating [performance graphs]. Solved 3 problems successfully, tried fourth and fifth one but couldn't figure out the problem so didn't attempt and saw wrong answer for a submission for the sixth problem. For the remaining four, I didn't even get a chance to go through given the limited time I had (this happens when you manage your job while stealing some time out for your hobby. ;) )

Successful submissions are open to public post closure of the contest:
https://www.codechef.com/NOV17/status/VILTRIBE,chandniverma
https://www.codechef.com/NOV17/status/CLRL,chandniverma
https://www.codechef.com/NOV17/status/PERPALIN,chandniverma

I am yet to up-solve those 7 problems which I couldn't solve during the contest.

-------

The following week, I got my free time busy with the 35th Week of Code by Hackerrank.
Ranked at 3181 out of 9289, I'd say I performed better than average among the participants but there is still a huge gap between my score (59) and that of the highest scorer (290).

Here, I solved the first 3 problems successfully.

The fourth problem, Matrix Land, was a show-stopper! I really recommend it! I spend 3 evenings on it and still was not able to come up with a working solution. I was trying to figure out a modification of Bellman-Ford algorithm (which is a Dynamic Programming algorithm) to solve it with some decent efficiency but was getting nowhere as there was no way to mark visited vertices...
It turns out, reading the insightful problem editorial, one could solve it using a bunch of dynamic programming equations.

I went through the 5th and 6th problems too which were number crunching problems and they despite of being hard and expert level, seemed easier than the 4th one but didn't get much time to think them through their solutions.

Again, I have yet to up-solve the unsolved ones.

[Problem4 SPOJ:PT07Z and Problem5 SPOJ:LABYR1] More on mazes

PROBLEMS: http://www.spoj.com/problems/PT07Z and http://www.spoj.com/problems/LABYR1

I set out to solve LABYR1 last early this week and found that PT07Z would act as a good precursory problem so solved that first.

There are a lot of forests on this way <= Does that ring a bell as to which road we should take?

Well, coming to the hints and note taking part...

I came across this article [ https://cptalks.quora.com/Diameter-of-a-Tree ] which claims to be an optimization I am yet to analyse.

A classic textbook lemma exists for such problems which I applied here.  I used DFS twice.


SOLUTIONS: https://github.com/glassrose/CPP_Problem_Solving/blob/master/SPOJ-PT07Z.cpp
and https://github.com/glassrose/CPP_Problem_Solving/blob/master/SPOJ-LABYR1.cpp

Tested here: http://www.spoj.com/status/PT07Z,chandniverma/
and http://www.spoj.com/status/LABYR1,chandniverma/

Complexities in the worst case:

For Problem 4: Time is O(N) where N is the no. of nodes in the tree.
Space needed is O(N) where N= no. of nodes in the tree.

For Problem 5: Time for each test case is O(R*C) where R and C=no. of rows and columns in the labyrinth respectively.

Space needed is O(R*C)

[Problem3 SPOJ:ROBOTGRI] A problem for lovers of mazes!

PROBLEM: http://www.spoj.com/problems/ROBOTGRI/

This was a tough nut!

Its a graph problem. Its actually a combination of 2 problems in one! I have voted it as hard and given it my recommendation.

I went through the following resources (none has the actual solution but all serve as hints) to finally come up with a solution for it:

https://www.cs.bu.edu/teaching/alg/maze/
https://www.hackerearth.com/practice/notes/dynamic-programming-problems-involving-grids/
http://www.geeksforgeeks.org/count-possible-paths-top-left-bottom-right-nxm-matrix/
http://www.geeksforgeeks.org/count-number-ways-reach-destination-maze/
https://www.youtube.com/watch?v=PwxGTHraMNg&feature=youtu.be
http://www.geeksforgeeks.org/applications-of-breadth-first-traversal/



SOLUTION: https://github.com/glassrose/CPP_Problem_Solving/blob/master/SPOJ-ROBOTGRI.cpp
Tested and Accepted: http://www.spoj.com/status/ROBOTGRI,chandniverma/

Time complexity in the worst case: O(n^2 + E)
where n = number of rows (or columns) in the grid
and E = number of edges in the connected graph containing the starting cell 'S'.

Space complexity: O(n^2)

[Problem2 SPOJ:JNEXT] Next Lexicographical Permutation Algorithm; Ad-Hoc

PROBLEM: http://www.spoj.com/problems/JNEXT/

I was solving SPOJ-JNEXT, and from the comments section I came across this page:

https://www.nayuki.io/page/next-lexicographical-permutation-algorithm

Nice explanation but there's a caveat to keep in mind to understand the working better-

It mentions:

If there is no such element – i.e. the entire sequence is non-decreasing – then this is already the last permutation.

It should rather be "non-increasing" instead of "non-decreasing".

[UPDATE: It has been corrected on the website nayuki.io. The author personally wrote a thank you note to me confirming  the error and rectifying it.]


My approach to solving this problem was similar so I won't bore you with another copy of how the algorithm works here: you may use the explanation in nayuki.io link above (with the correction in mind).

SOLUTION: https://github.com/glassrose/CPP_Problem_Solving/blob/master/SPOJ-JNEXT.cpp
Tested and accepted: http://www.spoj.com/status/JNEXT,chandniverma/

Time Complexity of get_next_perm() in worst case: O(n) where n is the number of digits in each test case in the input.
Space complexity: O(n)

[Problem1 SPOJ:STPAR] Stacks use case; Ad-hoc

Starting last weekend I have started picking up problems from the certification syllabus of the Codechef Certified Data Structure & Algorithms Programme: CCDSAP ( https://www.codechef.com/certification/prepare ). I would definitely recommend solving the practice material even if you are not willing to go for the certification.

I'll solve these in increasing order of difficulty and not necessarily sequentially while skipping the cake-walk ones and also probably the ones that I have done previously.
This way I can ensure this series of self-paced hackathon-cum-blogathon will eventually come to an end, with an end to the problems in this syllabus.

~
PROBLEM: http://www.spoj.com/problems/STPAR/

I had done this problem earlier so it was a good candidate for an ice-breaker. I first (sometime in 2010) solved this in Java. This time in C++ using an on-the-fly algorithm that doesn't store all inputs before processing them but processes each input as it comes in a single pass.


SOLUTION: https://github.com/glassrose/CPP_Problem_Solving/blob/master/SPOJ-STPAR.cpp
Tested and accepted at : http://www.spoj.com/status/STPAR,chandniverma/

The time complexity is O(n).
Space needed is O(n) (actually only n).