The thought process of the equi index problem

GDNet Lounge Community

Started by Alpha_ProgDes September 18, 2010 07:16 PM

7 comments, last by Sneftel 14 years, 1 month ago

Alpha_ProgDes

Author

6,963

September 18, 2010 07:16 PM

This is probably really bad to ask. But how did you come up with:

def equi(A):    totals = list()    accum = 0    for element in A:        totals.append(accum)        accum += element    for idx in range(0, len(A)):        if totals[idx] == accum - totals[idx] - A[idx]:            return idx    return -1

Definition of Equilibrium index:

Quote:
Equilibrium index of a sequence is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. For example, in a sequence A:

A[0]=-7 A[1]=1 A[2]=5 A[3]=2 A[4]=-4 A[5]=3 A[6]=0
3 is an equilibrium index, because : :
A[0] A[1] A[2] = A[4] A[5] A[6]
6 is also an equilibrium index, because:
A[0] A[1] A[2] A[3] A[4] + A[5] = 0 (sum of zero elements is zero)
7 is not an equilibrium index, because it is not a valid index of sequence A.

If you still have doubts, this is a precise definition: the integer k is an equilibrium index of a sequence
A[0],A[1],...,A[n] if and only if 0≤k≤ n and Σm=0 k−1 A[m]=Σm=k+1 n A[m]. We assume that sum of zero elements is equal zero.

Write a function, that given a sequence, returns its equilibrium index (any) or -1 if no equilibrium indexes exist. Assume that the sequence may be very long. If possible, use one of the following languages and define your function as follows: int equi(int a[])

Originating thread: Equilibrium problem

[Edited by - Alpha_ProgDes on September 18, 2010 8:01:04 PM]

Beginner in Game Development? Read here. And read here.

Nytegard

842

September 18, 2010 07:32 PM

I think it comes down to what he originally stated:

Quote:
I don't think there's any secret to it, just that it takes lots of practice to develop the ability to rapidly condense a problem down to the simplest solution.

Sadly, in life, some people can just see the easiest solution while others can't. I don't think there's much of a thought process behind it honestly.

I mean, when you look at the page, it states that almost all solutions can be done in under 10 lines of code. And they give you the mathematical formula.

Prefect

373

September 18, 2010 10:17 PM

Perhaps it should be pointed out that the solution given in the thread starter is not actually the simplest solution. There are equivalently short solutions which do not require an auxiliary list.

As for the thought process that goes into that, it's kind of hard to tell. When you have a certain basic algorithmic training, a sweeping process is one of the first thing that should come to mind, right after having the intuition that this is really something that one should be able to do in linear time. It's just a matter of having seen enough algorithm design so that you have an intuitive feeling for what are the good approaches.

Widelands - laid back, free software strategy

Alpha_ProgDes

Author

6,963

September 19, 2010 02:38 AM

Well I was hoping that anyone who solved the question in 15 lines or less, could just jot down how they went about solving the problem. Example: The question asked for the sum of previous indexes = the sum of indexes afterwards, so I knew to sum up the whole list because....

But anyway...

Beginner in Game Development? Read here. And read here.

JSoftware

318

September 19, 2010 02:53 AM

Alright, I need to compare the sum of every element on one side of an index versus another. If they are equal return the index. Do this for every index. Easy peasy

Wait a minute. The values don't change. I'll just calculate it once and substract/add for every new index. Just like in moving average filters with circular buffers

That's more or less the thought process. Wrote it in less than 6 minutes, with score 100.

Remembered to make the sum 64 bit. I've made that error many times in moving average filters :)

Gage64

1,235

September 19, 2010 04:00 AM

I couldn't figure it out on time... My mind was fixed on an incorrect algorithm, and I spent the 30 minutes thinking about why I can't get it to work. I guess I should work on my algorithmic thinking. Maybe it's time to visit Project Euler...

Anyway, here's another way to think about it.

The simplest solution is for each index, compute the sum of the elements before and after it and compare them. This is very simple, but is it efficient? Another way to ask this is to ask if there's any redundent work being done, and indeed there is.

Suppose that we just did this for iteration i, so we have the sum of the elements at [0, i) and (i, N). Note that these are half open and open ranges, respectively.

Suppose the sums were different, and we want to move to the next index. Now we are at iteration i+1, so we need the sums of the elements at [0, i+1) and (i+1, N).

However, if we compute them from scratch, we are throwing away the results of computations performed in previous iterations - the current left sum is the left sum from the previous iteration, plus A. Similarly, the current right sum is the right sum from the previous iteration, minus A[i+2]. (Remember, we are at iteration i+1.)

So what are the initial values of the sums? Since we start at i=0, the left sum should equal to the sum of the elements up to (but not including) i. There are no such elements, so it starts out as 0. Similarly, the right sum should be the sum of all the elements after index 0, which is the sum of the entire array minus A[0].

Out of the solutions in the other thread, I think SiCrane's solution expresses this in the most concise and straightforward way, though I'll make a small change so that it matches the above line of thinking more closely:

def equi(A):  if len(A) == 0:    return -1  left = 0  right = sum(A) - A[0]  for i in range(len(A)):    # invariant:    # left == sum of [0, i)    # right == sum of (i, len(A))    if left == right:      return i    left += A    right -= A  return -1

EDIT: Added code to handle an empty array.

[Edited by - Gage64 on September 19, 2010 12:00:33 PM]

OOP Articles | C++: A Dialog (free book) | Thinking in C++ (free book) | Google Books - Free preview for many books

Alpha_ProgDes

Author

6,963

September 19, 2010 06:21 PM

A bump.

Beginner in Game Development? Read here. And read here.

Way Walker

745

September 19, 2010 07:53 PM

Basically repeating the general formula, it's similar to proof by induction. For me it's:

1) What are we checking? Put that in the loop body. In this case:
if left == right: return i

2) What is the difference between check i and check i-1? Put that in the loop body as well. In this case, left and right are the variables that change. In the last check, left was the sum of elements 0..i-2 and, for this check, it should be 0..i-1, so we need to add A[i-1]. Similarly, right was i..n-1 and should be i+1..n-1. So, if we modify them before the check:
left += A[i-1]
right -= A
or, modifying them after the check:
left += A
right -= A[i+1]

3) What is the first thing to check? Put that in front of the loop to initialize it. Here:
left = 0
right = sum(A) (or = sum(A[1:]) if we modify after the check)

4) What happens if all checks fail? Put that after the loop. Here:
return -1

5) Where does the code break? This is in two parts:

5a) Where does the code break on "normal" input? Here, either the code from (2) will break either at the first or last iteration, depending on how we decided to do it. You can either special case it like Sneftel, which is ugly but straightforward, or modify the logic a bit like SiCrane, which is elegant but strays slightly from the original logic.

5b) Where could the code break from "troublesome" input? Depending on the specifics, the empty array may or may not give us trouble, and we can do an early out if we like. I'd probably have missed the need for left and right to be 64 bits in C/C++. (One, because C89 and C++ don't have integer types guaranteed to be >32 bit. Also, because int is the "default" integer type. This means that their passing an array of int's (instead of long's) doesn't give any indication of the magnitude of the elements. It also leads me to use int without a specific reason not to (cf. returning int instead of size_t).)

Sneftel

1,788

September 19, 2010 08:35 PM

There's a certain number of algorithm "shapes". The most common three are greedy, dynamic programming, and divide-and-conquer. This problem lends itself to dynamic programming, because of the way in which the information you need to calculate in order to check whether index n is an equilibrium gives you most of what you need to know in order to check n+1. If you're interested in this stuff, check out "Algorithm Design" by Kleinberg and Tardos.

The thought process of the equi index problem

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

The thought process of the equi index problem

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines