Hello Friends.It took too long for me to post new article.But Impythonist came up with with really interesting Insight this time.
Ok,what is title refer to?.We all done programming days and nights,why we stumble if new challenge is given to us?.
This article is not intended for Hardco(ders)re,but main focus is on beginners & intermediate ones.
“The coding is an art which rises from deep of the heart”
So here we are going to see an use case challenge which arrives frequently in local or web code contests.We can use any programming
language but as a pythonist i was privileged to use python,a beautiful and elegant programming language.
The problem goes as follows:
“”” You are provided with a text file containing a list of integers.
Let S be the longest subsequence of consecutive increasing integers in this list,
such that the element at position n is greater than the element at position n-1.
If there are multiple sub-sequences of the same length, let S be the one that appears first in the list.
What is the absolute value of the sum of the elements in S?
For example, take the list [3, 4, 2, 5, 7, 7, 1, 2].
For this list, the longest subsequence of increasing integers has 3 elements: S = [2, 5, 7].
The absolute value of the sum of these elements is |2+5+7|=14
text file is below:
Step 1: Understand The Problem
It is not a simple question but thinking a bit could lead us to create theories for attacking the problem.
If we first see the question we will come up with an idea of dynamic programming.But only a little applicaton of dynamic
programming is required here.
step 2: Run the python Interpreter
Now assume how the beginning of the solution for the challenge could be!.what data types are required?,what python concepts
are involved in this.
By little observation from the question statement we draw following conclusions:
1.Usage of file handling concept in python
2.String handling is required little bit.
3.List manipulation is necessary and nothing more
Now go and get some coffee and rock on sleeves before knowing a technique.
step 3: No more steps.Jumping right on to the code.
#My Version Of Solution to The Subsequence Challenge
3. for l in fil:
6. while i<len(mylo):
7. if long_seq>temp: temp,max_seq_index=long_seq,i-1
9. while j!=len(mylo)-1 and mylo[j]<mylo[j+1] :
14. print “The longest sequence no in File is: %d and sum is %d”% (temp,total)
Just observe the above code.It is complete solution to the problem.Your feet will ache if you try to find
the solution in the other traditional languages.Don’t be panicked by seeing code,we are going to discuss each and every line.
It is simple.we are opening a file called num.txt in reading mode.readlines() method of file object returns a ‘list’ of
strings for all lines in the file.Here num.txt is in current directory.path can be specified instead.
Here we are planning to capture each line as a single value and store it into list.So create an empty list first.
for l in fil:
Now for each element in the returned list ‘fil’ we are casting each value to int and stores it into list mylo.
By this a list is set with values to work on.Actual logic starts from next lines.
In this line we are packing(assigning) four variables in a single line.see what the variables mean.
long_seq ———> This variable going to store maximum length of items satisfied condition for each iteration.
It may seem alien,but things will settle in some time.
i ———-> This variable is used for iteration of each element of list.
temp ———-> This variable is used to store the longest length of subsequence found.It means it consists
of part of answer i.e.what is the length of maximum matched elements satisfying required conditions.
s[i]<s[i+1].It is initialized with 1 because at least one element satisfy given condition.
max_seq_index —–> This variable holds the index for starting of maximum subsequence.This is later used by us to find out
the sum of all elements matching criteria s[i]<s[i+1] in longest subsequence.
Here we are iterating from first element in list ‘mylo’ up to last element.
if long_seq>temp: temp,max_seq_index=long_seq,i-1
Here comes the tricky part.Here this construct is written by seeing into future.That is what dynamic programming.It states if current
found sequence length is greater than previously calculated one then modify temp,and store index where we find the maximum subsequence
length into max_seq_index.why it is i-1 and not i because,we are looking into future.It will be clarified in few minutes.
long_seq is a temporary variable for each iteration.It is a sentinel which works for temp.It is analogous as follows.If money collected
by long_seq is greater temp will own it,other wise temp doesn’t care.Now long_seq is sent into battlefield with initializing one rupee.If
earn in the coming battle in next loop,it gets the longest sequence which is later fed to temp.j is initialized to i in order to find any
sub-sequence is availing for greater length.
while j!=len(mylo)-1 and mylo[j]<mylo[j+1] :
j!=len(mylo)-1 is written in afraid of array index out of bounds chance for next condition mylo[j]<mylo[j+1].If these two are passed then j
skids to next higher value and long_seq bagged 1 point for satisfying the condition.This continues until longer subsequence satisfying
condition happens.If condition fails i restarts with next element.
Simple,this is used to iterate i for each element in ‘mylo’
Here total stores sum of all the elements in of the largest subsequence satisfying the condition.The temp value is useful for stripping the list
‘mylo’ and return only part of it, which is a longest subsequence.predefined sum() method adds stripped list and abs() method returns absolute
value converting negative into positive.
print “The longest sequence no in File is: %d and sum is %d”% (temp,total)
As it is clear this line prints the longest subsequence length and sum as asked in challenge
In this way python constructs are highly optimized and used to write new libraries at lightening speed.Here dynamic programming approach might
confuse a little bit,but if you follow the execution path you will find easier how cleverly the problem was solved.
It is a little effort to enhance designing strategies for beginners.For further discussions feel free to mail me.
my mail address : firstname.lastname@example.org