Fastest way to print a list of integers as a triangle from the exterior to the interior

Question

Consider the following problem:

You receive some integer m and set n=1+2+...+m,

Now you need to print all number from 1 to n as a triangle from the exterior to the interior.

Example:

Input:

m=6
n=1+2+3+4+5+6 = 21

Output:

1
2 15
3 16 14
4 17 21 13
5 18 19 20 12
6  7  8  9 10 11

What's the fastest way to do this if you can use any supportive data-structure? what's the fastest way if you can't use more than O(1) memory?

Answer 1

@groovy: I would like to add comment to your post, but I cannot (I am new to here). I think the function can be simplified as:

var a=0;
var atemp=0;
var edge=0;
function cal(x,y,m){
    a=Math.min((y-x),(x),(m-1-y));
    atemp=(((m+(m-3*a+1))*3*a)/2);
    edge=m-3*a;
    if(a==x){
        return atemp+1+y-a*2;
    }else if(a==m-1-y){
        return atemp+edge+x-a;
    }else{
        return atemp+edge*2-2+m-y-a;
    }
}

Forgive me that i am not used to give good names, and I haven't got compiler on hand so I wrote it in JS, O(1) memory for:

a (minimum number of the position to the bottom, left and right), 
atemp (the total number of the outer loops of triangle caused i.e. for m=4, when we print number 10, 1-9 forms the outer loop of triangle and atemp is 9), 
edge (the edge is the longest edge of the current triangle)

only, O(n) for time complexity for you to print all numbers out (without paddings) by nested loop sth like (not JS):

for(i=0;i<m;i++){ for(j=0;j<=i;j++) print cal(j,i,m); print '\n'}

(ps. I dun understand hashkell, but i guess your idea is somehow like this, please kindly point out if I had missed any case)

Answer 2

Here's a method that uses a constant amount of memory, if you assume tail-call optimization prevents the call stack from growing unnecessarily. (code is in Python, but does not use any constructs that aren't easily ported)

#returns the value at the given position in the triangle of a particular size.
def valueAt(x,y,size):
    #is position out of bounds?
    if x >= size or y >= size or x > y:
        return None
    #is position on the left edge of the triangle?
    if x == 0:
        return y+1
    #is position on the bottom edge of the triangle?
    if y == size - 1:
        return x + size
    #is position on the right edge of the triangle?
    if x == y:
        return 3*size - 2 - x
    #position must lie somewhere within the triangle.
    return 3*size - 3 + valueAt(x-1, y-2, size-3)

This is a recursive function whose first four conditionals form the base case. If the coordinates lie out of bounds or on the edge of the triangle, we can easily find the value lying there. If the coordinates lie within the triangle's interior, we strip the big triangle like an onion, revealing a triangle three sizes smaller, and retrieve the value from that.

You can then take these values and print them by iterating through the necessary coordinates.

#adds spaces to the start of the string.
def pad(v, amt):
    while len(v) < amt:
        v = " " + v
    return v

def showTriangle(size):
    #figure out how many characters long each value should be, 
    #based on the length of the largest number
    maxValue = size * (size+1) / 2
    maxLength = len(str(maxValue))

    for y in range(size):
        print "\n",
        for x in range(y+1):
            val = valueAt(x,y,size)
            if val:
                print pad(str(val), maxLength),

for i in range(3, 12+1, 3):
    showTriangle(i)
    print "\n"

Result:

1
2 6
3 4 5


 1
 2 15
 3 16 14
 4 17 21 13
 5 18 19 20 12
 6  7  8  9 10 11


 1
 2 24
 3 25 23
 4 26 39 22
 5 27 40 38 21
 6 28 41 45 37 20
 7 29 42 43 44 36 19
 8 30 31 32 33 34 35 18
 9 10 11 12 13 14 15 16 17


 1
 2 33
 3 34 32
 4 35 57 31
 5 36 58 56 30
 6 37 59 72 55 29
 7 38 60 73 71 54 28
 8 39 61 74 78 70 53 27
 9 40 62 75 76 77 69 52 26
10 41 63 64 65 66 67 68 51 25
11 42 43 44 45 46 47 48 49 50 24
12 13 14 15 16 17 18 19 20 21 22 23

Edit: if your particular system doesn't implement tail-call optimization, you can implement the iterative form yourself:

def valueAt(x,y,size):
    acc = 0
    while True:
        #is position out of bounds?
        if x >= size or y >= size or x > y:
            return None
        #is position on the left edge of the triangle?
        if x == 0:
            return acc + y+1
        #is position on the bottom edge of the triangle?
        if y == size - 1:
            return acc + x + size
        #is position on the right edge of the triangle?
        if x == y:
            return acc + 3*size - 2 - x
        #position must lie somewhere within the triangle.
        acc += 3*size - 3
        x-= 1
        y -= 2
        size -= 3