Making lists symmetrical by merging elements

Question

My code is based around the following problem:

http://orac.amt.edu.au/cgi-bin/train/problem.pl?set=aio16int&problemid=903

It's about making a series of plots of land symmetrical by knocking down fences, but out of context of this problem, the code: Takes a list, makes it symmetrical by adding elements together, and prints / writes the number of changes needed to achieve this.

My main concern is speed: the code works fine but it is taking too long to solve cases with long lists. (up to 100,000 elements, where each element is an integer up to 10,000) Any feedback welcomed!

infile = open("farmin.txt", "r")
outfile = open("farmout.txt", "w")
n = int(infile.readline())
plots = infile.readline().split()
infile.close()
plots = [int(i) for i in plots]
fencescut = 0
leftpos = 0
rightpos = 0

def mergeplots (direc, n1, n2):
    global plots
    if direc == "l":
        plots[n1] = plots[n1] + plots.pop(n2)
    else:
        plots[len(plots) - 1 - n1] = plots[len(plots) - 1 - n1] + plots.pop(len(plots) - 1 - n2)

while leftpos <= len(plots)/2 and rightpos <= len(plots)/2:
    if plots[len(plots) - 1 - rightpos] - plots[leftpos] > 0: # left fence needs to be cut
        fencescut += 1
        mergeplots("l",leftpos, leftpos + 1)
    elif plots[len(plots) - 1 - rightpos] - plots[leftpos] < 0: #right fence needs to be cut
        fencescut += 1
        mergeplots('r', rightpos, rightpos + 1)
    else: # no fence needs to be cut
        leftpos += 1
        rightpos += 1
outfile.write(str(fencescut))
outfile.close()

Answer 1

Removing elements from the middle of the list is expensive: list.pop(k) has an \$O(k)\$ time complexity, and therefore an entire program is quadratic.

However, physically removing fences is not necessary. You only need to track the widths of two current plots.

---

Counting rightpost up from 0 is dubious. It is confusing to the reader, and complicates mergeplots unnecessarily. I recommend to make it count down from plots.len() - 1.

As a side note, since you don't need to actually merge the plots (see above), mergeplots itself is not needed.

Answer 2

It is better to read input and output files using the with keyword because:

It is good practice to use the with keyword when dealing with file objects. This has the advantage that the file is properly closed after its suite finishes, even if an exception is raised on the way. It is also much shorter than writing equivalent try-finally blocks:

with open('farmin.txt', 'r') as input:
    # Process the code you need here.