1. Hey guys, Hope you all are doing great. I am back with another problem of Project Euler on
    Project Euler #11: Largest product in a grid

    In the 20×20 grid below, four numbers along a diagonal line have been marked in bold.
    89 90 95 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08  
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00  
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65  
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91  
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80  
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50  
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70  
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21  
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72  
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95  
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92  
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57  
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58  
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40  
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66  
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69  
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36  
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16  
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54  
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
    The product of these numbers is 26 × 63 × 78 × 14 = 1788696.
    What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?
    Input Format
    Input consists of 20 lines each containing 20 integers.
    Output Format
    Print the required answer.
    Constraints
    0 ≤ Each integer in the grid ≤ 100
    Sample Input
    89 90 95 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08  
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00  
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65  
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91  
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80  
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50  
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70  
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21  
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72  
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95  
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92  
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57  
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58  
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40  
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66  
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69  
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36  
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16  
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54  
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
    Sample Output
    73812150

    Algorithm:


    This problem ask for a simple approach to check for the product of numbers in:
    1. Horizontal - Left to Right
    2. Vertical - Top to Bottom
    3. Diagonal - Top Left to Bottom Right
    In this way we can cover all the possible 4 number sets:
    1. Horizontal: 17 * 20 (17 because we are taking sets of 4).
    2. Vertical: 17 * 20 (17 because we are taking sets of 4).
    3. Diagonal: 17*17
    So total of 969 calculations.
    I will jump to the program which is pretty straight forward.

    Program:

    grid=list()
for i in range(20):
    grid.append(map(int, raw_input().split()))
ans=0
for i in range(20):
    for j in range(20 - 4 + 1):
        phv = max(grid[i][j] * grid[i][j+1] * grid[i][j+2] * grid[i][j+3], grid[j][i] * grid[j+1][i] * grid[j+2][i] * grid[j+3][i])
        if (i < 20 - 4):
            pdd = max(grid[i][j] * grid[i+1][j+1] * grid[i+2][j+2] * grid[i+3][j+3], grid[i][j+3] * grid[i+1][j+2] * grid[i+2][j+1] * grid[i+3][j])
        ans = max(ans, phv, pdd)
print ans
    Output:
    73812150

    And Presto!! Its Done!!

     Please let me know how i can improve my post and any other feedback are welcome.

     Till then Cheers!!
    Posted by
    Labels: Algorithms Hackerrank Hackerrank.com Mathematics Programming Python
    0

    Add a comment

  2. Hey guys, Hope you all are doing great.
    Today i came across an intruding method, which is not used in generally but is very effective and we encounter its application a lot of .

     That's 

    Tabibitosan method


    Tabibitosan: is a Japanese word which literally means "Pilgrim". This came up when people thought it as a method there you transverse through a consecutive pattern (same as going from temple to temple).

    I came across this method while exploring Oracle Community Forum written by Aketi Jyuuzou who explained it beautifully.

    Thanks Aketi Jyuuzou!!

    Tabibitosan method is useful in below application:
    1. For counting consecutive value sets.
    2. For getting distinct attributes based on continued start and end dates
    3. Grouping of continuous dates
    4. Counting continues years, months, weeks.
    5. To optimize cases where there are duplicate records. (In Next Post we will discuss on optimum duplicate detection and removal techniques.)
    6. There can be many more application depending on your need.
    Now, understanding how this method works, I will pic an example as a problem in Hackerrank Advanced Join section 

    Projects


    You are given a table, Projects, containing three columns: Task_ID, Start_Date and End_Date. It is guaranteed that the difference between the End_Date and the Start_Date is equal to 1 day for each row in the table.
    If the End_Date of the tasks are consecutive, then they are part of the same project. Samantha is interested in finding the total number of different projects completed.
    Write a query to output the start and end dates of projects listed by the number of days it took to complete the project in ascending order. If there is more than one project that have the same number of completion days, then order by the start date of the project.
    Sample Input
    Sample Output
    2015-10-28 2015-10-29
2015-10-30 2015-10-31
2015-10-13 2015-10-15
2015-10-01 2015-10-04

    What we need to do?
    The example describes following four projects:
    • Project 1: Tasks 1, 2 and 3 are completed on consecutive days, so these are part of the project. Thus start date of project is 2015-10-01 and end date is 2015-10-04, so it took 3 days to complete the project.
    • Project 2: Tasks 4 and 5 are completed on consecutive days, so these are part of the project. Thus, the start date of project is 2015-10-13 and end date is 2015-10-15, so it took 2 days to complete the project.
    • Project 3: Only task 6 is part of the project. Thus, the start date of project is 2015-10-28 and end date is 2015-10-29, so it took 1 day to complete the project.
    • Project 4: Only task 7 is part of the project. Thus, the start date of project is 2015-10-30 and end date is 2015-10-31, so it took 1 day to complete the project.
    So in all we need to find the projects which have continued start date and end date.
    We will use Tabibitosan method:

    So we will do like i move from last end date to next start date, if the time is 1 then its continued, else its a break in count, here is how we will realize that in SQL:


    SELECT  START_DATE, END_DATE, END_DATE - ROW_NUMBER() OVER (ORDER BY END_DATE) DIST
FROM PROJECTS


    Here we will have list of start date and end date with a third date that is common to the continued dates.

    Output to above problem's data for the SQL will be:

     
    START_DATE      END_DATE      DIST
2015-10-28     2015-10-29    2015-10-14
2015-10-30     2015-10-31    2015-10-15
2015-10-13     2015-10-15    2015-10-07
2015-10-14     2015-10-16    2015-10-07
2015-10-01     2015-10-04    2015-09-30
2015-10-01     2015-10-04    2015-09-30
2015-10-01     2015-10-04    2015-09-30
2015-10-01     2015-10-04    2015-09-30

    Now its easy to group the Start and End Date by the common Distance date, with lower limit as MIN(START_DATE) and upper limit as MAX(END_DATE).

     And Presto!! We are done.

    Below is the final code:

     
    SELECT SD,ED
FROM
(SELECT MIN(START_DATE) SD, MAX(END_DATE) ED, ( MAX(END_DATE)-MIN(START_DATE)) dd
FROM
(
SELECT  START_DATE, END_DATE, END_DATE - ROW_NUMBER() OVER (ORDER BY END_DATE) DIST
FROM PROJECTS
 ORDER BY 1)
GROUP BY DIST
 ORDER BY 3,1);

    Output:


    SD         ED
2015-10-28 2015-10-29
2015-10-30 2015-10-31
2015-10-13 2015-10-15
2015-10-01 2015-10-04


    Hope you guys find it useful. Please let me know about your feed backs, areas where i can improve.

     Till then keep coding!!


    Posted by
    Labels: Hackerrank Hackerrank.com Mathematics Oracle SQL Tabibitosan
    8

    View comments

  3. Hey guys, 
    Hope you all are doing great. I am back with another problem of Project Euler on

    The sum of the primes below  is 
    Find the sum of all the primes not greater than given .
    Input Format
    The first line contains an integer  i.e. number of the test cases.
    The next  lines will contains an integer .
    Output Format
    Print the value corresponding to each test case in separate line.
    Constraints

    Sample Input
    2
5
10
    Sample Output
    10
17

    Algorithm:

    The Sieve of Eratosthenes is a simple algorithm that finds the prime numbers up to a given integer. Implement this algorithm, with the only allowed optimization that the outer loop can stop at the square root of the limit, and the inner loop may start at the square of the prime just found. That means especially that you shouldn't optimize by using pre computed wheels, i.e. don't assume you need only to cross out odd numbers (wheel based on 2), numbers equal to 1 or 5 modulo 6 (wheel based on 2 and 3), or similar wheels based on low primes.

    Odds-only version of the array sieve above
    The below code uses only odd composite operations (for a factor of over two) and because it has been optimized to use slice operations for composite number culling to avoid extra work by the interpreter

    Program:



    def primes2(limit):
    if limit < 2: return []
    if limit < 3: return [2]
    lmtbf = (limit - 3) // 2
    buf = [True] * (lmtbf + 1)
    for i in range((int(limit ** 0.5) - 3) // 2 + 1):
        if buf[i]:
            p = i + i + 3
            s = p * (i + 1) + i
            buf[s::p] = [False] * ((lmtbf - s) // p + 1)
    return sum([2] + [i + i + 3 for i, v in enumerate(buf) if v])

t=input()
while(t>0):
    print primes2(input())
    t-=1

    Hope you liked this post.
    Do let me know about any improvements i can incorporate to anything in the blog.

    Till Then...Cheers!!

    Posted by
    Labels: Algorithms Hackerrank Hackerrank.com Mathematics Prime Numbers Programming Project Euler Python
    0

    Add a comment

Loading