Home

Swayam Solver

Learn Programming & Prepare for NPTEL Exams... Swayam Solver is your one-stop destination for NPTEL exam preparation.

NPTEL Programming, Data Structures And Algorithms Using Python Jan 2025

NPTEL Programming, Data Structures And Algorithms Using Python Jan 2025

Posted on

 


NPTEL » Programming, Data Structures And Algorithms Using Python


  Please scroll down for latest Programs 👇 




Week 2 Programming Assignment

Due on 2025-02-06, 23:59 IST
Write three Python functions as specified below. Paste the text for all three functions together into the submission window. Your function will be called automatically with various inputs and should return values as specified. Do not write commands to read any input or print any output.
  • You may define additional auxiliary functions as needed.
  • In all cases you may assume that the value passed to the function is of the expected type, so your function does not have to check for malformed inputs.
  • For each function, there are normally some public test cases and some (hidden) private test cases.
  • "Compile and run" will evaluate your submission against the public test cases.
  • "Submit" will evaluate your submission against the hidden private test cases. There are 15 private test cases, 5 for each function below, with equal weightage. You will get feedback about which private test cases pass or fail, though you cannot see the actual test cases.
  • Ignore warnings about "Presentation errors".

  1. A positive integer m can be partitioned as primes if it can be written as p + q where p > 0, q > 0 and both p and q are prime numbers.

    Write a Python function primepartition(m) that takes an integer m as input and returns True if m can be partitioned as primes and False otherwise. (If m is not positive, your function should return False.)

    Here are some examples of how your function should work.

    >>> primepartition(7)
True

>>> primepartition(185)
False

>>> primepartition(3432)
True

  2. Write a function matched(s) that takes as input a string s and checks if the brackets "(" and ")" in s are matched: that is, every "(" has a matching ")" after it and every ")" has a matching "(" before it. Your function should ignore all other symbols that appear in s. Your function should return True if s has matched brackets and False if it does not.

    Here are some examples to show how your function should work.

     
>>> matched("zb%78")
True

>>> matched("(7)(a")
False

>>> matched("a)*(?")
False

>>> matched("((jkl)78(A)&l(8(dd(FJI:),):)?)")
True

  3. A list rotation consists of taking the first element and moving it to the end. For instance, if we rotate the list [1,2,3,4,5], we get [2,3,4,5,1]. If we rotate it again, we get [3,4,5,1,2].

    Write a Python function rotatelist(l,k) that takes a list l and a positive integer k and returns the list l after k rotations. If k is not positive, your function should return l unchanged. Note that your function should not change l itself, and should return the rotated list.

    Here are some examples to show how your function should work.

    >>> rotatelist([1,2,3,4,5],1)
[2, 3, 4, 5, 1]

>>> rotatelist([1,2,3,4,5],3)
[4, 5, 1, 2, 3]

>>> rotatelist([1,2,3,4,5],12)
[3, 4, 5, 1, 2]
Your last recorded submission was on 2025-02-03, 20:00 IST
Select the Language for this assignment. 
1
###########
2
def factors(n):
3
  factorlist = []
4
  for i in range(1,n+1):
5
    if n%i == 0:
6
      factorlist.append(i)
7
  return(factorlist)
8
def prime(n):
9
  return(factors(n)==[1,n])
10
def primepartition(n):
11
  for i in range(1,n//2+1):
12
    if prime(i) and prime(n-i):
13
      return(True)
14
  return(False)
15
###########
16
def matched(s):
17
  nesting = 0
18
  for c in s:
19
    if c == '(':
20
      nesting = nesting + 1
21
    elif c == ')':
22
      nesting = nesting - 1
23
    if nesting < 0:
24
      return(False)
25
  return(nesting == 0)
26
###########
27
def rotatelist(l,k):
28
  retlist = l[:]
29
  if k <= 0:
30
    return(retlist)
31
  for i in range(1,k+1):
32
    retlist = retlist[1:] + [retlist[0]]
33
  return(retlist)
0
~~~THERE IS SOME INVISIBLE CODE HERE~~~
You may submit any number of times before the due date. The final submission will be considered for grading.
This assignment has Public Test cases. Please click on "Compile & Run" button to see the status of Public test cases. Assignment will be evaluated only after submitting using Submit button below. If you only save as or compile and run the Program , your assignment will not be graded and you will not see your score after the deadline.
   


 
 
Public Test CasesInputExpected OutputActual OutputStatus
Test Case 1
primepartition(7)
True
True\n

Passed after ignoring Presentation Error
Test Case 2
primepartition(185)
False
False\n

Passed after ignoring Presentation Error
Test Case 3
primepartition(3432)
True
True\n

Passed after ignoring Presentation Error
Test Case 4
matched("(7)(a")
False
False\n

Passed after ignoring Presentation Error
Test Case 5
matched("a)*(?")
False
False\n

Passed after ignoring Presentation Error
Test Case 6
matched("((jkl)78(A)&l(8(dd(FJI:),):)?)")
True
True\n

Passed after ignoring Presentation Error
Test Case 7
rotatelist([1,2,3,4,5],1)
[2, 3, 4, 5, 1]
[2, 3, 4, 5, 1]\n

Passed after ignoring Presentation Error
Test Case 8
rotatelist([1,2,3,4,5],3)
[4, 5, 1, 2, 3]
[4, 5, 1, 2, 3]\n

Passed after ignoring Presentation Error
Test Case 9
rotatelist([1,2,3,4,5],12)
[3, 4, 5, 1, 2]
[3, 4, 5, 1, 2]\n

Passed after ignoring Presentation Error





Week 3 Programming Assignment

Due on 2025-02-13, 23:59 IST
Write three Python functions as specified below. Paste the text for all three functions together into the submission window. Your function will be called automatically with various inputs and should return values as specified. Do not write commands to read any input or print any output.
  • You may define additional auxiliary functions as needed.
  • In all cases you may assume that the value passed to the function is of the expected type, so your function does not have to check for malformed inputs.
  • For each function, there are normally some public test cases and some (hidden) private test cases.
  • "Compile and run" will evaluate your submission against the public test cases.
  • "Submit" will evaluate your submission against the hidden private test cases. There are 12 private test cases, with equal weightage. You will get feedback about which private test cases pass or fail, though you cannot see the actual test cases.
  • Ignore warnings about "Presentation errors".

  1. Define a Python function remdup(l) that takes a nonempty list of integers l and removes all duplicates in l, keeping only the last occurrence of each number. For instance:

    >>> remdup([3,1,3,5])
[1, 3, 5]

>>> remdup([7,3,-1,-5])
[7, 3, -1, -5]

>>> remdup([3,5,7,5,3,7,10])
[5, 3, 7, 10]

  2. Write a Python function splitsum(l) that takes a nonempty list of integers and returns a list [pos,neg], where pos is the sum of squares all the positive numbers in l and neg is the sum of cubes of all the negative numbers in l.

    Here are some examples to show how your function should work.

    >>> splitsum([1,3,-5])
[10, -125]

>>> splitsum([2,4,6])
[56, 0]

>>> splitsum([-19,-7,-6,0])
[0, -7418]

>>> splitsum([-1,2,3,-7])
[13, -344]

  3. A two dimensional matrix can be represented in Python row-wise, as a list of lists: each inner list represents one row of the matrix. For instance, the matrix

    1  2  3
4  5  6 
7  8  9

    would be represented as [[1, 2, 3], [4, 5, 6], [7, 8, 9]].

    A horizonatal flip reflects each row. For instance, if we flip the previous matrix horizontally, we get

    3  2  1
6  5  4 
9  8  7

    which would be represented as [[3, 2, 1], [6, 5, 4], [9, 8, 7]].

    A vertical flip reflects each column. For instance, if we flip the previous matrix that has already been flipped horizontally, we get

    9  8  7
6  5  4 
3  2  1

    which would be represented as [[9, 8, 7], [6, 5, 4], [3, 2, 1]].

    Write a Python function matrixflip(m,d) that takes as input a two dimensional matrix m and a direction d, where d is either 'h' or 'v'. If d == 'h', the function should return the matrix flipped horizontally. If d == 'v', the function should retun the matrix flipped vertically. For any other value of d, the function should return m unchanged. In all cases, the argument m should remain undisturbed by the function.

    Here are some examples to show how your function should work. You may assume that the input to the function is always a non-empty matrix.

    >>> myl = [[1,2],[3,4]]

>>> myl
[[1, 2], [3, 4]]  

>>> matrixflip(myl,'h')
[[2, 1], [4, 3]]

>>> myl
[[1, 2], [3, 4]]  

>>> matrixflip(myl,'v')
[[3, 4], [1, 2]]  

>>> myl
[[1, 2], [3, 4]]  

>>> matrixflip(matrixflip(myl,'h'),'v')
[[4, 3], [2, 1]]

>>> myl
[[1, 2], [3, 4]]  

>>> matrixflip(matrixflip(myl,'h'),'v')
[[4, 3], [2, 1]]

>>> myl
[[1, 2], [3, 4]]
Your last recorded submission was on 2025-02-12, 18:24 IST
Select the Language for this assignment. 
1
def remdup(l):
2
    if len(l) <= 1:
3
        return(l)
4
5
    if l[0] in l[1:]:
6
        return(remdup(l[1:]))
7
    else:
8
        return([l[0]] + remdup(l[1:]))
9
####
10
def splitsum(l):
11
    pos = 0
12
    neg = 0
13
    for x in l:
14
        if x > 0:
15
            pos = pos + x**2
16
        if x < 0:
17
            neg = neg + x**3
18
    return([pos,neg])
19
####
20
def matrixflip(l,d):
21
  outl = []
22
  for row in l:
23
    outl.append(row[:])
24
  if d == 'h':
25
    for row in outl:
26
      row.reverse()
27
  elif d == 'v':
28
    outl.reverse()
29
  return(outl)
0
~~~THERE IS SOME INVISIBLE CODE HERE~~~
You may submit any number of times before the due date. The final submission will be considered for grading.
This assignment has Public Test cases. Please click on "Compile & Run" button to see the status of Public test cases. Assignment will be evaluated only after submitting using Submit button below. If you only save as or compile and run the Program , your assignment will not be graded and you will not see your score after the deadline.
   


 
 
Public Test CasesInputExpected OutputActual OutputStatus
Test Case 1
remdup([3,1,3,5])
[1, 3, 5]
[1, 3, 5]\n

Passed after ignoring Presentation Error
Test Case 2
remdup([7,3,-1,-5])
[7, 3, -1, -5]
[7, 3, -1, -5]\n

Passed after ignoring Presentation Error
Test Case 3
remdup([3,5,7,5,3,7,10])
[5, 3, 7, 10]
[5, 3, 7, 10]\n

Passed after ignoring Presentation Error
Test Case 4
splitsum([1,3,-5])
[10, -125]
[10, -125]\n

Passed after ignoring Presentation Error
Test Case 5
splitsum([2,4,6])
[56, 0]
[56, 0]\n

Passed after ignoring Presentation Error
Test Case 6
splitsum([-19,-7,-6,0])
[0, -7418]
[0, -7418]\n

Passed after ignoring Presentation Error
Test Case 7
splitsum([-1,2,3,-7])
[13, -344]
[13, -344]\n

Passed after ignoring Presentation Error
Test Case 8
matrixflip([[1, 2], [3, 4]],'h')
[[2, 1], [4, 3]]
[[2, 1], [4, 3]]\n

Passed after ignoring Presentation Error
Test Case 9
matrixflip([[1, 2], [3, 4]],'v')
[[3, 4], [1, 2]]
[[3, 4], [1, 2]]\n

Passed after ignoring Presentation Error




Week 4 Programming Assignment

Due on 2025-02-20, 23:59 IST
Write two Python functions as specified below. Paste the text for all three functions together into the submission window. Your function will be called automatically with various inputs and should return values as specified. Do not write commands to read any input or print any output.
  • You may define additional auxiliary functions as needed.
  • In all cases you may assume that the value passed to the function is of the expected type, so your function does not have to check for malformed inputs.
  • For each function, there are normally some public test cases and some (hidden) private test cases.
  • "Compile and run" will evaluate your submission against the public test cases.
  • "Submit" will evaluate your submission against the hidden private test cases. There are 10 private test cases, with equal weightage. You will get feedback about which private test cases pass or fail, though you cannot see the actual test cases.
  • Ignore warnings about "Presentation errors".

  1. We have a list of annual rainfall recordings of cities. Each element in the list is of the form (c,r) where c is the city and r is the annual rainfall for a particular year. The list may have multiple entries for the same city, corresponding to rainfall recordings in different years.

    Write a Python function rainaverage(l) that takes as input a list of rainfall recordings and computes the avarage rainfall for each city. The output should be a list of pairs (c,ar) where c is the city and ar is the average rainfall for this city among the recordings in the input list. Note that ar should be of type float. The output should be sorted in dictionary order with respect to the city name.

    Here are some examples to show how rainaverage(l) should work.

    >>> rainaverage([(1,2),(1,3),(2,3),(1,1),(3,8)])
[(1, 2.0), (2, 3.0), (3, 8.0)]

>>> rainaverage([('Bombay',848),('Madras',103),('Bombay',923),('Bangalore',201),('Madras',128)])
[('Bangalore', 201.0), ('Bombay', 885.5), ('Madras', 115.5)]

  2. A list in Python can contain nested lists. The degree of nesting need not be uniform. For instance [1,2,[3,4,[5,6]]] is a valid Python list. Write a Python function flatten(l) that takes a nonempty list of lists and returns a simple list of all the elements in the nested lists, flattened out. You can make use of the following function that returns True if its input is of type list.

    def listtype(l):
  return(type(l) == type([]))

    Here are some examples to show how flatten(l) should work.

    >>> flatten([1,2,[3],[4,[5,6]]])
[1, 2, 3, 4, 5, 6]

>>> flatten([1,2,3,(4,5,6)])
[1, 2, 3, (4, 5, 6)]
Your last recorded submission was on 2025-02-19, 16:17 IST
Select the Language for this assignment. 
1
def rainaverage(l):
2
  raindata = {}
3
  for (c,r) in l:
4
    if c in raindata.keys():
5
      raindata[c].append(r)
6
    else:
7
      raindata[c] = [r]
8
  outputlist = []
9
  for c in sorted(raindata.keys()):
10
    thisaverage = sum(raindata[c])/len(raindata[c])
11
    outputlist.append((c,thisaverage))
12
  return(outputlist)
13
########
14
def flatten(l):
15
  if not(listtype(l)):
16
    return([l])
17
  flatlist = []
18
  for e in l:
19
    flatlist.extend(flatten(e))
20
  return(flatlist)
21
########
22
def listtype(l):
23
  return(type(l) == type([]))
0
~~~THERE IS SOME INVISIBLE CODE HERE~~~
You may submit any number of times before the due date. The final submission will be considered for grading.
This assignment has Public Test cases. Please click on "Compile & Run" button to see the status of Public test cases. Assignment will be evaluated only after submitting using Submit button below. If you only save as or compile and run the Program , your assignment will not be graded and you will not see your score after the deadline.
   


 
 
Public Test CasesInputExpected OutputActual OutputStatus
Test Case 1
rainaverage([(1,2),(1,3),(2,3),(1,1),(3,8)])
[(1, 2.0), (2, 3.0), (3, 8.0)]
[(1, 2.0), (2, 3.0), (3, 8.0)]\n

Passed after ignoring Presentation Error
Test Case 2
rainaverage([('Bombay',848),('Madras',103),('Bombay',923),('Bangalore',201),('Madras',128)])
[('Bangalore', 201.0), ('Bombay', 885.5), ('Madras', 115.5)]
[('Bangalore', 201.0), ('Bombay', 885.5), ('Madras', 115.5)]\n

Passed after ignoring Presentation Error
Test Case 3
flatten([1,2,[3],[4,[5,6]]])
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]\n

Passed after ignoring Presentation Error
Test Case 4
flatten([1,2,3,(4,5,6)])
[1, 2, 3, (4, 5, 6)]
[1, 2, 3, (4, 5, 6)]\n

Passed after ignoring Presentation Error
Test Case 5
flatten(["hello",True,3])
['hello', True, 3]
['hello', True, 3]\n

Passed after ignoring Presentation Error
Test Case 6
flatten([1,2,[3,["hello",True]],[4,[5,6]]])
[1, 2, 3, 'hello', True, 4, 5, 6]
[1, 2, 3, 'hello', True, 4, 5, 6]\n

Passed after ignoring Presentation Error



Week 5 Programming Assignment

Due on 2025-02-27, 23:59 IST

For this assignment, you have to write a complete Python program. Paste your code in the window below.

  • You may define additional auxiliary functions as needed.
  • In all cases you may assume that the input to your program has the expected format, so your program does not have to check for malformed inputs.
  • There are some public test cases and some (hidden) private test cases.
  • "Compile and run" will evaluate your submission against the public test cases.
  • "Submit" will evaluate your submission against the hidden private test cases. There are 6 private test cases, with equal weightage. You will get feedback about which private test cases pass or fail, though you cannot see the actual test cases.
  • Ignore warnings about "Presentation errors".

The academic office at the Hogwarts School of Witchcraft and Wizardry has compiled data about students' grades. The data is provided as text from standard input in three parts: information about courses, information about students and information about grades. Each part has a specific line format, described below..

  1. Information about courses
    Line format: Course Code~Course Name~Semester~Year~Instructor
  2. Information about students
    Line format: Roll Number~Full Name
  3. Information about grades
    Line format: Course Code~Semester~Year~Roll Number~Grade

The possible grades are A, AB, B, BC, C, CD, D with corresponding grade points 10, 9, 8, 7, 6, 5 and 4. The grade point average of a student is the sum of his/her grade points divided by the number of courses. For instance, if a student has taken two courses with grades A and C, the grade point average is 8.50 = (10+7)÷2. If a student has not completed any courses, the grade point average is defined to be 0.

You may assume that the data is internally consistent. For every grade, there is a corresponding course code and roll number in the input data.

Each section of the input starts with a line containing a single keyword. The first section begins with a line containing Courses. The second section begins with a line containing Students. The third section begins with a line containing Grades. The end of the input is marked by a line containing EndOfInput.

Write a Python program to read the data as described above and print out a line listing the grade point average for each student in the following format:

Roll Number~Full Name~Grade Point Average

Your output should be sorted by Roll Number. The grade point average should be rounded off to 2 digits after the decimal point. Use the built-in function round().

Here is a sample input and its corresponding output.

Sample Input

Courses
TRAN~Transfiguration~1~2011-2012~Minerva McGonagall
CHAR~Charms~1~2011-2012~Filius Flitwick
Students
SLY2301~Hannah Abbott
SLY2302~Euan Abercrombie
SLY2303~Stewart Ackerley
SLY2304~Bertram Aubrey
SLY2305~Avery
SLY2306~Malcolm Baddock
SLY2307~Marcus Belby
SLY2308~Katie Bell
SLY2309~Sirius Orion Black
Grades
TRAN~1~2011-2012~SLY2301~AB
TRAN~1~2011-2012~SLY2302~B
TRAN~1~2011-2012~SLY2303~B
TRAN~1~2011-2012~SLY2305~A
TRAN~1~2011-2012~SLY2306~BC
TRAN~1~2011-2012~SLY2308~A
TRAN~1~2011-2012~SLY2309~AB
CHAR~1~2011-2012~SLY2301~A
CHAR~1~2011-2012~SLY2302~BC
CHAR~1~2011-2012~SLY2303~B
CHAR~1~2011-2012~SLY2305~BC
CHAR~1~2011-2012~SLY2306~C
CHAR~1~2011-2012~SLY2307~B
CHAR~1~2011-2012~SLY2308~AB
EndOfInput

Sample Output

SLY2301~Hannah Abbott~9.5
SLY2302~Euan Abercrombie~7.5
SLY2303~Stewart Ackerley~8.0
SLY2304~Bertram Aubrey~0
SLY2305~Avery~8.5
SLY2306~Malcolm Baddock~6.5
SLY2307~Marcus Belby~8.0
SLY2308~Katie Bell~9.5
SLY2309~Sirius Orion Black~9.0
Your last recorded submission was on 2025-02-24, 11:56 IST
Select the Language for this assignment. 
1
# Convert letter grade to grade point
2
def gradetonum(grade):
3
    if grade == 'A':
4
        return(10)
5
    elif grade == 'AB':
6
        return(9)
7
    elif grade == 'B':
8
        return(8)
9
    elif grade == 'BC':
10
        return(7)
11
    elif grade == 'C':
12
        return(6)
13
    elif grade == 'CD':
14
        return(5)
15
    elif grade == 'D':
16
        return(4)
17
    else:
18
        return(0)
19
# Set up three dictionaries to store data
20
rollname = {}    # Key: roll number, Value: Name
21
gradepoint = {}  # Key: roll number, Value: Cumulative grade points
22
coursecount = {} # Key: roll number, Value: Number of courses taken
23
nextline = input().strip()
24
while nextline.find("Courses") < 0:
25
    nextline = input().strip()
26
# Read course data
27
while nextline.find("Students") < 0:
28
    nextline = input().strip()
29
    # Course data is irrelevant for this problem!
30
# Read students data
31
nextline = input().strip()
32
while nextline.find("Grades") < 0:
33
    fields = nextline.split('~')
34
    roll=fields[0]
35
    name=fields[1]
36
    rollname[roll] = name   # Initialize
37
    gradepoint[roll] = 0    # Initialize
38
    coursecount[roll] = 0   # Initialize
39
    nextline = input().strip()
40
# Read grades data
41
nextline = input().strip()
42
while nextline.find("EndOfInput") < 0:
43
    fields = nextline.split('~')
44
    roll=fields[3]
45
    grade=fields[4]
46
    gradepoint[roll] += gradetonum(grade)  # Update
47
    coursecount[roll] += 1                 # Update
48
    nextline = input().strip()
49
# Print output
50
for roll in sorted(rollname.keys()):
51
    if coursecount[roll] > 0:
52
        gpa = round(gradepoint[roll]/coursecount[roll],2)
53
    else:
54
        gpa = 0
55
    print(roll,rollname[roll],gpa,sep='~',end='\n' )
You may submit any number of times before the due date. The final submission will be considered for grading.
This assignment has Public Test cases. Please click on "Compile & Run" button to see the status of Public test cases. Assignment will be evaluated only after submitting using Submit button below. If you only save as or compile and run the Program , your assignment will not be graded and you will not see your score after the deadline.
   


 
 
Public Test CasesInputExpected OutputActual OutputStatus
Test Case 1
Courses
TRAN~Transfiguration~1~2011-2012~Minerva McGonagall
CHAR~Charms~1~2011-2012~Filius Flitwick
Students
SLY2301~Hannah Abbott
SLY2302~Euan Abercrombie
SLY2303~Stewart Ackerley
SLY2304~Bertram Aubrey
SLY2305~Avery
SLY2306~Malcolm Baddock
SLY2307~Marcus Belby
SLY2308~Katie Bell
SLY2309~Sirius Orion Black
Grades
TRAN~1~2011-2012~SLY2301~AB
TRAN~1~2011-2012~SLY2302~B
TRAN~1~2011-2012~SLY2303~B
TRAN~1~2011-2012~SLY2305~A
TRAN~1~2011-2012~SLY2306~BC
TRAN~1~2011-2012~SLY2308~A
TRAN~1~2011-2012~SLY2309~AB
CHAR~1~2011-2012~SLY2301~A
CHAR~1~2011-2012~SLY2302~BC
CHAR~1~2011-2012~SLY2303~B
CHAR~1~2011-2012~SLY2305~BC
CHAR~1~2011-2012~SLY2306~C
CHAR~1~2011-2012~SLY2307~B
CHAR~1~2011-2012~SLY2308~AB
EndOfInput
SLY2301~Hannah Abbott~9.5\n
SLY2302~Euan Abercrombie~7.5\n
SLY2303~Stewart Ackerley~8.0\n
SLY2304~Bertram Aubrey~0\n
SLY2305~Avery~8.5\n
SLY2306~Malcolm Baddock~6.5\n
SLY2307~Marcus Belby~8.0\n
SLY2308~Katie Bell~9.5\n
SLY2309~Sirius Orion Black~9.0
SLY2301~Hannah Abbott~9.5\n
SLY2302~Euan Abercrombie~7.5\n
SLY2303~Stewart Ackerley~8.0\n
SLY2304~Bertram Aubrey~0\n
SLY2305~Avery~8.5\n
SLY2306~Malcolm Baddock~6.5\n
SLY2307~Marcus Belby~8.0\n
SLY2308~Katie Bell~9.5\n
SLY2309~Sirius Orion Black~9.0\n

Passed after ignoring Presentation Error
Test Case 2
Courses
POT~Potions~1~2011-2012~Severus Snape
DADA~Defence Against the Dark ARTS~1~2011-2012~Gilderoy Lockhart 
Students
RAV4309~Angelina Johnson
HUF7201~Gwenog Jones
GRF9110~Parvati Patil
RAV4308~Olive Hornby
Grades
POT~1~2011-2012~RAV4308~C
POT~1~2011-2012~RAV4309~B
POT~1~2011-2012~GRF9110~A
EndOfInput
GRF9110~Parvati Patil~10.0\n
HUF7201~Gwenog Jones~0\n
RAV4308~Olive Hornby~6.0\n
RAV4309~Angelina Johnson~8.0
GRF9110~Parvati Patil~10.0\n
HUF7201~Gwenog Jones~0\n
RAV4308~Olive Hornby~6.0\n
RAV4309~Angelina Johnson~8.0\n

Passed after ignoring Presentation Error



Week 8 Programming Assignment - Here there be Dragons

Due on 2025-03-20, 23:59 IST

For this assignment, you have to write a complete Python program. Paste your code in the window below.

  • You may define additional auxiliary functions as needed.
  • There are some public test cases and some (hidden) private test cases.
  • "Compile and run" will evaluate your submission against the public test cases
  • "Submit" will evaluate your submission against the hidden private test cases. There are 12 private test cases, with equal weightage. You will get feedback about which private test cases pass or fail, though you cannot see the actual test cases.
  • Ignore warnings about "Presentation errors".

Here there be Dragons

(IOI Training Camp, 2012)

The kingdom is falling into ruin. People live in fear. Dragons pillage, kill, and just generally cause as much havoc as they possibly can. The king has just sent out a royal decree:

To any man out there who is able to bring me the heads of K dragons, I shall bequeath a lordship–to him, his sons and his grandsons, till the end of time.

Having seen this royal decree, and knowing that you are capable of killing dragons thanks to your extensive medieval combat training, you set out on a quest to hunt down the evil creatures. Being a busy kind of guy, you would like to complete your quest quickly and kill K dragons through the shortest route.

The kingdom is arranged in a grid with R rows, numbered 0 to R-1, and C columns, numbered 0 to C-1 You start your quest at the top left corner of the grid, (0,0).

The total number of dragons in the kingdom is D, of which you have to kill K. Dragons are very territorial in nature, so each row of the grid contains at most one dragon. Also, since the kingdom is situated on a hill, you travel only downwards on the grid, though you may move left or right as you please.

You are told that no two dragons are on the same row of the grid. Also, no dragon is at position (0,0).

For example, suppose the grid has 5 rows and 5 columns with 3 dragons, of which you have to kill any 2. The three dragons are located at (1,4), (2,3) and (4,4), as shown below. In this case, your shortest route is to take 7 steps and kill the dragons in row 1 and row 2. Killing any other combination of 2 dragons takes 8 steps, so this is the minimum possible. Note that once you've killed K dragons, you don't incur any cost to return home. You just want to find how long it takes to do all the killing. 

Solution hint

Number the dragons 1,2,…,D in ascending order of rows. Let mindist(i,j) denote the minimum distance travelled when the jth dragon killed is dragon i. Recall the constraint that there is no dragon at (0,0). Use dynamic programming to compute mindist(i,j) for all values of i and j, then find the minimum among mindist(i,K) for all i ≥ K.

Input format

  • Line 1 : Four space-separated integers, R, C, K and D.
  • Lines 2 to D+1 : Each line has two-space separated integers r and c, the row and column of the corresponding dragon.

Output format

A single integer, the minimum total distance travelled to kill K dragons.

Test Data:

  • In all testcases, K ≤ D ≤ R, and, for each dragon position (r,c), 0 ≤ r < R, and 0 ≤ c < C.
  • In all testcases, 1 ≤ K,D ≤ 300.
  • In 60% of the testcases, 1 ≤ R,C ≤ 300. In the remaining testcases, 1 ≤ R,C ≤ 100000.
  • No two dragons will be on the same row.
  • No dragon will be at position (0,0).

Sample Input:

5 5 2 3
1 4
4 4
2 3

Sample Output:

7

Your last recorded submission was on 2025-03-11, 18:18 IST
Select the Language for this assignment. 
1
# dist(i,j) = distance from dragon i to dragon j
2
# killed[i][j] = minimum distance to kill exactly j dragons ending with dragon i, i >= j
3
# killed[i][j] = min( killed[k][j-1] + dist(k,i) )
4
def dist(i,j):
5
  # Assume 0 <= i,j < d
6
  xdist = abs(dragons[i][0] - dragons[j][0])
7
  ydist = abs(dragons[i][1] - dragons[j][1])
8
  return(xdist+ydist)
9
(rstr,cstr,kstr,dstr) = input().strip().split()
10
(r,c,k,d) = (int(rstr),int(cstr),int(kstr),int(dstr))
11
dragons = [(0,0)]
12
for i in range(d):
13
  (xstr,ystr) = input().strip().split()
14
  (x,y) = (int(xstr),int(ystr))
15
  dragons.append((x,y))
16
dragons.sort()
17
killed = [[0 for col in range(k+1)] for row in range(d+1)]
18
for row in range(d+1):
19
  for col in range(k+1):
20
    if col != row:
21
      killed[row][col] = r*c+1
22
for dragon in range(1,d+1):
23
  for victim in range(1,min(dragon+1,k+1)):
24
    killed[dragon][victim] = min([ killed[i][victim-1] + dist(i,dragon) for i in range(victim-1,dragon) ])
25
optimum = min( [ killed[i][k] for i in range(dragon+1) ])
26
print(optimum, end='')
You may submit any number of times before the due date. The final submission will be considered for grading.
This assignment has Public Test cases. Please click on "Compile & Run" button to see the status of Public test cases. Assignment will be evaluated only after submitting using Submit button below. If you only save as or compile and run the Program , your assignment will not be graded and you will not see your score after the deadline.
   


 
 
Public Test CasesInputExpected OutputActual OutputStatus
Test Case 1
5 5 2 3
1 4
4 4
2 3
7
7
Passed
Test Case 2
5 5 3 4
1 1
3 2
2 4
0 4
9
9
Passed
Test Case 3
10 10 5 7
1 7
3 6
5 1
6 5
7 4
4 3
2 2
17
17
Passed















No comments:

Post a Comment

Keep your comments reader friendly. Be civil and respectful. No self-promotion or spam. Stick to the topic. Questions welcome.

Subscribe to: Post Comments (Atom)