Find the area of an n-interesting polygon

Question

Consider:

I am trying to find the area of an n-interesting polygon, where (n=1, A=1, n=2, A=5, n=3, A=13, n=4, A=25, and so on). So the formula for an n-interesting polygon is the area of an (n-1)-interesting polygon+(n-1)*4. When running the program, a hidden test shows that the code is wrong. What is wrong with my code?

def shapeArea(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    for i in range(2, n+1):
        return (shapeArea(n-1) + (n-1)*4)

Answer 1

In case you need a optimized recursive function, I got a very simple solution:

def solution(n):
    if n == 1:
        return 1
    else:
        return solution(n-1) + n * 4 - 4

Explanation:

If we split it into 4 triangles, the outer side of each triangle will always be of length of n.

When n = 1: We will always have solution(1) = 1.

When n >1: We will always have solution(n-1) + the additional lengths of the outer side of each triangle.

This gives us the following formula:

solution(n-1) + (n * 4) + p

Where p = 4

Answer 2

I think the last part where you have written the 'for' loop is dodgy. If you're already using recursion why do you need a 'for' loop? Nonetheless, I did it this way without using recursion:

def shapeArea(n):
    if n == 1:
        return 1
    return n**2 + (n-1)**2

Answer 3

These worked fine for me.

n*n + (n-1) * (n-1)

n * (2*n - 1) - (n-1)

Answer 4

How can we find the formula if we don't see the partitioning trick? The definition f(1) = 1; f(n) = f(n-1) + 4*n for n > 1 relates an area to a length. We may therefore hypothesize that f(n) is quadratically related to n: a*n*n + b*b +c. We can determine the coefficients algebraically from the first 3 pairs: f(1) = 1, f(2) = 5, f(3) = 13, which give us 3 equations in 3 unknowns:

a + b + c = 1
4a + 2b + c = 5
9a + 3b + c = 13

Eliminating c = 1 - a - b first, we get

3a + b = 4
8a + 2b = 12

Eliminating b = 4 - 3a next, we get

2a = 4

Hence a = 2, b = -2, c = 1, so f(n) = 2*n*(n-1) + 1. We can verify by induction.

Note: Getting the formula for the sum of counts, f(0) = 0; f(n) = f(n-1) + n for n > 0, is even simpler because the first equation is c = 0. The remaining pair

a + b = 1
4a + 2b = 3

is easily solved to get a = b = 1/2, giving f(n) = n*(n+1)/2.

Answer 5

Here's an approach one can use to derive a formula.

The shapes always have a horizontal line across the middle. If you draw a rectangle that emcompasses both the top square and the horizontal line, there will always be a void of white squares within it large enough to be partially filled by the squares below the line.

Imagine that you fill that void above the line with the squares below the line. With the exception of n=1, your shape will be changed to a rectangle that still has some white squares in it. Let's look at a few.

n=2                n=3                         n=4

. X .   X X .      . . X . .    X X X . .      . . . X . . .    X X X X . . .
X X X   X X X      . X X X .    X X X X X      . . X X X . .    X X X X X X X
. X .   . . .      X X X X X    X X X X X      . X X X X X .    X X X X X X X
                   . X X X .    . . . . .      X X X X X X X    X X X X X X X
                   . . X . .    . . . . .      . X X X X X .    . . . . . . .
                                               . . X X X . .    . . . . . . .
                                               . . . X . . .    . . . . . . .

The new shape can be characterized with the formula: area = height * width - gap

If we chart that out to look for patterns, it looks like this:

n | height | width | gap
1 |    1   |   1   |  0
2 |    2   |   3   |  1
3 |    3   |   5   |  2
4 |    4   |   7   |  3

Both height and gap are counting by one, and width is skip-counting by 2. You can always characterize that linear trend as n*skipValue +/- constant. In this case,

height=n
width=2n-1
gap=n-1

Plugging those terms back into our formula for the area of the gapped rectangles,

area = height * width - gap becomes area = n * (2n - 1) - (n - 1)

Answer 6

I initially read the problem wrong. I thought we need to find the outside edges.

Let's first see how we can do that...and then it will lead to a more intuitive solution later for this problem.

For the number of edges, I was looking at the outermost diagonal and see 2*(n-1) edges on each of the four diagonals. It doesn't include the main four edges which are also present when n = 1.

So the total number of edges is (4 + 4 * 2 * (n-1))

Note that since we do not want to calculate number of edges, but the area, we will only use n-1 for the area rather than 2 * (n-1).

Also, we need to subtract one since we were looking at outer edges...or how many additional squares the next iteration will need...so we will use (n-1)-1

Now let’s use this to calculate the area:

n = 1 is 1
n = 2 we need to add 4 + 4* ((n-1)-1) squares or 4 + 4 * (n-2) squares
n = 3 we need to add an additional 4 + 4 * (n-2) squares
n = 4 we need to add an additional 4 + 4 * (n-2) squares

if n == 1:
    return 1

area = 1

for n in range (1, n+1):
   area += 4 + 4*(n-2)

return area

Answer 7

This may be a solution:

function shapeArea(n) {
    return ((n-1) * (n*2)) + 1;
}

Answer 8

In Python:

In every increasing n, the 4's table is added to the previous one's polygon number:

def solution(n):
    if n == 1:
        return 1
    else:
        c = 0
        for i in range(1, n):
            c += 4*i
    return c + 1

Answer 9

This works (Python 3):

def shapeArea(n):
    area = n*n + (n-1)*(n-1)
    return area

print(shapeArea(5))

Answer 10

If we see the given example,

when n=1, poly = 1

when n=2, poly = 5

when n=3, poly = 13

when n=4, poly = 25

the next pattern could be found by formula 2n(n-1) + 1:

def shapeArea(n):
    return 2 * n * (n - 1) + 1;

Answer 11

An easy-to-understand solution in Ruby without recursion:

def shapeArea(n)
    total = 0
    (1..n-1).each do |column|
       total += column + (column-1)
    end
    (total*2) + (n+(n-1))
end

• Both sides will have equal amounts of squares, except the center column that does not repeat. So we calculate the sides using the (1..n-1) loop, and the number of squares will be always column + (column - 1);
• After that we just need to multiply this by 2 to get the sum of both sides (total*2) and add the center column (n+(n-1)).

Answer 12

Use:

def shapeArea(n):
    sum = 0
    i = 1
    while(n>1):
        sum = sum + 2*i
        n = n - 1
        i = 2 + i
   sum = sum + i
   return sum

Try to calculate the sum of row wise squares (twice 2*i) and add the middle row at the end.

Answer 13

This passed all the tests without performance issues:

def IncreasingSequence(sequence):
  for x in range(0, len(sequence) - 1):
    if sequence[y] >= sequence[x + 1]:
        alt1 = sequence.copy()
        alt2 = sequence.copy()

        alt1.pop(x)
        alt2.pop(x+1)

        return (False, alt1, alt2)

  return (True, sequence, sequence)

def almostIncreasingSequence(sequence):
  boo, nl1, nl2 = IncreasingSequence(sequence)
  if boo == False:
    boo1, ll, ll1 = IncreasingSequence(nl1)
    if boo1 == False:
        boo2, l1, l2 =IncreasingSequence(nl2)
        return boo2
  return True

Answer 14

The easiest solution to the problem in JavaScript:

function shapeArea(n) {
    if(n<0) {
        return false
    }
    return (n*n) + ((n-1)*(n-1))
}

console.log(shapeArea(1))

Answer 15

Like an alternative, I found a solution using a for loop.

def shapeArea(n):
    return sum([( num * 4 ) for num in range(1, n)]) + 1

Answer 16

def shapeArea(n):
  if n == 1:
    return 1
  square_side = n+n-1
  outer_square_area = square_side**2
  white_pieces = 4*(1/2)*n*(n+1)
  area = outer_square - white_pieces
  return area

A different approach to the problem:

If you notice, each n-interesting polygon can be contained in a surrounding square that has sides of length 2n-1. One could take this "outter square" and subtract the area of the missing white spaces.

Coming up with a formula for the white pieces is tricky because you have to add up these weird stair-step-like pieces on each of the 4 sides. The area for these weird pieces can actually be calculated using the formula for consecutive integers or 1/2*N(N+1) (For this problem N=n-1)

This can easily be seen for for the n=2, the larger surrounding square side is 2+(2-1)=3 so the total area will be 9 - 4 = 5.

To better understand how the connection to how the white area is calculated see the visualization behind the formula. Notice how counting the area of these triangular blocks is similar to adding up integers from 1...n

Answer 17

This is a formula to find an area of polygon for given n

def shapeArea(n):
    return (n**2)+((n-1)**2)

shapeArea(3)

Output

13

Answer 18

As there are already coding examples, I will explain why the formula is n * n + (n-1) * (n-1)

1. You need to see the graph diagonally
2. You will notice that the sides are always n
3. For example, if n=4, the shape has for 4 squares on each side, thus n * n
4. However, if you notice, n * n does not account for all the squares. There are squares in between the once you accounted for
5. Take away the square you have accounted with n * n, you will notice now that the side of the shape is now n-1
6. Thus, you take into account of the squares in between, the formula is n * n + (n-1) * (n-1)
7. Example: if n = 4, the outer square is 4 * 4 = 16. Then take away the area you have just calculated, the inner squares is 3 * 3 = 9. Add together, you get 25.

Answer 19

I found the formula without the recursion. The test went through fine.

def shapeArea(n):
    if n>=10**4 or n<1:
        return False

    return (n**2+(n-1)**2)