[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).

Blogging after a long time... turning my blog into an algorithmist's blog solving this world's time and memory efficiency problems in computing.

... Since I cannot talk much about what things I work on as part of my day job and since I feel that's making my blog boring and making the viewers wait a lot between my blogging sessions, I've decided to start blogging about algorithmic programming skills which every computer software engineer should be good at!

I'll do this because I like spending my free time in sharpening my algorithmic skills and while I take notes, why not should someone-on-the-web learn something out of it?

I'll post codes into a Github public repository which will have C++ solutions (why C++? due to it's speed, presence of STL and intuitiveness of Object Orient-ism) tested by online judges and if I learn something triggering an Aha moment, I'll jot down a quick blog post with links to an actual runnable code and the problem it solves.

You all can send thank you notes and suggestions for improvements my way, as always!

Sounds fun?
Watch this space!

Making lshw, IBM PowerPC compliant

Dear Linux Community,

The first tool that comes to mind when we think of obtaining hardware inventory on a computer is lshw, a concise tool leveraging C++ capabilities which already generates good results when run on a number of platforms, including x86.

lshw, like other cross-platform tools has generic code portions which are same across all platforms and some platform-specific code portions.

I am glad to tell that efforts to make lshw display correct and accurate platform-specific results when run on IBM PowerPC server systems running Linux are paying off as code-changes are getting merged upstream:
https://ezix.org/src/pkg/lshw/commits/branch/master/search?q=Chandni+Verma
(OR https://github.com/lyonel/lshw/commits/master?author=glassrose)
AND
https://ezix.org/src/pkg/lshw/commits/branch/master/search?q=Jack+Miller
https://ezix.org/src/pkg/lshw/commits/branch/master/search?q=Jeremy+Kerr
https://ezix.org/src/pkg/lshw/commits/branch/master/search?q=Vasant+Hegde

Update:
[
My other notable commits(despite of Lyonel Vincent not retaining my Author name and signoff tag) include:
https://ezix.org/src/pkg/lshw/commit/a5fb8431d9888cbd4b40e6435d4379bf0c86cdec
https://ezix.org/src/pkg/lshw/commit/d15668eb9569fd7d8259c3b5ca669781081d81c7
and
https://ezix.org/src/pkg/lshw/commit/27b1d1d18696be949dbe0b8a1639c5683de4ca8f

(or equivalently on github:
https://github.com/lyonel/lshw/commit/a5fb8431d9888cbd4b40e6435d4379bf0c86cdec
https://github.com/lyonel/lshw/commit/d15668eb9569fd7d8259c3b5ca669781081d81c7
and
https://github.com/lyonel/lshw/commit/27b1d1d18696be949dbe0b8a1639c5683de4ca8f
)
]

I'd like to thank lshw maintainer, Lyonel Vincent, for acknowledging and accepting all work from IBM. It would also be nice, if he can give me my rightful author name to the commits where he ripped them off from.

Research is ongoing on abilities that are required but are lacking in the generic code as well and some of those require deep knowledge of ioctls, SCSI, SAS etc. and their workings. We're seeing how to expose more of those hardware inventory (encapsulated by certain subsystems) along with their location-codes and Vital Product Data (VPD) to the users so watch the above spaces and keep your systems updated!

Cheers,
Happy Hacking!

Learning Python!

Here are my first few basic Python programs (before my first Python assignment consuming and processing perf samples). :)


1)

#!/usr/bin/python
i = raw_input()
print i

2)

#!/usr/bin/python
T = int(raw_input())
print "Range of t is", range(T)
for i in range(T):
    print i
    ans = 42
    print "Case #%d: %d" % (i+1, ans)

    

3)

#!/usr/bin/python
T = int(raw_input())
for i in range(T):
    line = raw_input()
    N, J = line.split()
    N, J = int(N), int(J)
    print "N = %d, J = %d" % (N, J)   

4)

#!/usr/bin/python
T = int(raw_input())
i = 1
while i<=T:
    tmp = raw_input()
    N = int (tmp.split()[0])
    J = int (tmp.split()[1])
    print N, J
    print 2**N
    print 2**N-1
    print bin(2**N-1)
    i +=1   

5)

#!/usr/bin/python
#program 5
T = int(raw_input())
i = 1
while i<=T:
    tmp = raw_input()
    N = int (tmp.split()[0])
    J = int (tmp.split()[1])
    print N, J
    print 2**N
    print 2**N-1
    print bin(2**N-1)
    s = bin(2**N-1)[2:]
    print int(s, 2)
    print int(s, 3)
    print int(s, 4)
    print int(s, 10)
    i+=1      

6)

#!/usr/bin/python
 
#program 6
#defining functions
def factorial(n):
    ret = 1
    for i in range(n):
        ret *= i+1
     
    return ret
 
print factorial(5)
print factorial(4), factorial(3)