Project Euler #8 - Largest Product in a series - Python

n = map(int, raw_input().split()) #To read the number of digits and 
                                  #k consecutive numbers
num = int(raw_input()) # To read the digit
#print n[1]
#print num
stri = str(num)
product = 0
for i in xrange(len(stri) - n[1] + 1):
        temp = 1
        k = i
        for j in range(n[1]):        
            temp = temp * int(stri[k])
            k = k + 1
           
        if(temp > product):
            product = temp
            #print product
print product  

Longest Increasing Sequence using python

import sys
import copy

#Binary search
def binary(s, num):
#print "in binary s:"  + str(s)
#print "in binary num:" + str(num)
    l = len(s)
    mid = l/2
    #print "in binary s:" + str(s)
    #print "in binary num:" + str(num)
    #print "s[mid]:" + str(s[mid])
    if((l!=0) and  (l == 1)):
    if(s[mid] < num):
    return s[mid]

    if((l!=0) and (l != 1)):
   if ((s[mid] >= num) and (s[mid - 1 ] < num)):
       return s[mid - 1]
   elif ((s[mid] > num) and (s[mid - 1] > num)):
       return binary(s[:mid -1] , num)
   else:
       return binary(s[mid:], num)
     
 
 
t = int(raw_input())
for p in xrange(0,t):
    n = int(raw_input())
    arr = map(int, raw_input().split())
#maxlen in  worst case would be 1 and end element index is 0.
    maxlen = 1
    bestend = 0

    s = []
    LIS = []
    s.append(arr[bestend])
    LIS.append(s)
    #LIS[-1].append(s)
    #print s
    #print LIS

    #To get last elements of all lists
    #print max(LIS, key=len)[-1]
    # to get the last element of the max length in the list
     
 
    for i in xrange(1,n):
        #print "arr[i]:" + str(arr[i])
        #print "list end element to compare:" + str(max(LIS, key=len)[-1])
        if(arr[i] > max(LIS, key=len)[-1]):
         
            seq = copy.deepcopy(LIS)
         
            max(seq, key=len).append(arr[i])        

            LIS.append(max(seq, key=len))
            #print "post updated LIS:" + str(LIS)
         
         
     
        else:
         
            seq = copy.deepcopy(LIS)
            last_elem = [x[-1] for x in seq]
            val_greater_elem = binary(sorted(last_elem), arr[i])
            if val_greater_elem in last_elem:
                ind = last_elem.index(val_greater_elem)
                #print "Index of ele:" + str(ind)# to get index of the ele to append
                #print "seq ind to append:" + str(seq[ind][-1])
                seq[ind].append(arr[i])#replace element
                #print "updated seq:" + str(seq)
                #print "updated seq index:" + str(seq[ind])
                #print "Length of seq:" + str(len(seq[ind]))
                len_of_updated = len(seq[ind])
                k = [x for x in LIS if (len(x) == len_of_updated)]
                [LIS.remove(l) for l in k]
                #print "post discard LIS:" + str(LIS)
                LIS.append(seq[ind])
                #print "post updated LIS:" + str(LIS)
     
    print len(max(LIS, key=len))
    print "Final subseq:" + str(max(LIS, key=len))
 
     
stdin:
1
16
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15            

Output:
6
Final subseq: [0 2 6 9 11 15]
    

Binary search to find largest smaller element than given value python

import sys
def binary(s, num):
    l = len(s)
    mid = l/2
    #print "in binary s:" + str(s)
    #print "in binary num:" + str(num)
    #print "s[mid]:" + str(s[mid])
    if((l!=0) and  (l == 1)):
     if(s[mid] < num):
     return s[mid]
        #else:
#return None
    if((l!=0) and (l != 1)):
    if ((s[mid] >= num) and (s[mid - 1 ] < num)):
        return s[mid - 1]
    elif ((s[mid] > num) and (s[mid - 1] > num)):
        return binary(s[:mid -1] , num)
    else:
        return binary(s[mid:], num)


lst = [8,0]

print binary(sorted(lst), 4)

Output:

0

Artificial Intelligence using python

The below code is to reach a goal in a board game with robot at position with value 'r' and goal with value 'g' in the row* column board.

Below are the conventions for the code to solve the problem.


m - size of grid
grid - position of the board(in row * col)
g - goal position
r - robot current postion in the board


#!/bin/python
def find_m_position(grid):
for row in range(m):
for col in range(m):
if grid[row][col] == 'r':
return (row,col)

def find_p_postion(grid):
for row in range(m):
for col in range(m):
if grid[row][col] == 'g':
return (row, col)


def PathtoGoal(n,grid):
#print all the moves here
#pass
row_m, col_m = find_m_position(grid)
row_p, col_p = find_p_postion(grid)

while((row_m != row_p) and (col_m != col_p)):
diff_row = row_m - row_p
diff_col = col_m - col_p
if(diff_row < 0):
print "DOWN"
row_m = row_m + 1


else:
print "UP"
row_m = row_m - 1

if(diff_col > 0):
print "LEFT"
col_m = col_m - 1
else:
print "RIGHT"
col_m = col_m + 1


return None

m = input()

grid = []
for i in xrange(0, m):
grid.append(raw_input().strip())

#print grid

PathtoGoal(m,grid)

Project Euler - Problem 2 - Sum of even Fibonaaci numbers

def euler2(n):

su = 0
lst = []
for i in xrange(1,n,3):
    if(i == 1):
        res = 2
    elif (i == 4):
        res = 8
    else:
        res = 4* lst[-1]+ lst[-2]


    if(res < n):
        lst.append(res)

    else:
        break


print sum(lst)