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?
@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)
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
O(1) for memory. It prints 3 parts of triangles inserted each other. Every triangle consists of 3 lines of numbers - left vertical, horizontal on bottom and numbers placed on diagonal of right side. For any internal triangle we know the start upper left conner number which is calculated by outer one. The printing procedure consists of 3 cycles which prints parts of triangles corresponding to current row:
It goes through all rows (i) and keeps number of triangles in t. Code in java, just change m in main to whatever you want:
public class TrianglePrint {
public static void main(String[] args) {
int m = 9;
int t = 1;
int p = 2;
for (int i = 1; i <= m; i++) {
if (t*2 < i && t+i < m) {
t++;
}
int m1 = 0;
for (int k = 1; k <= t && k <= i; k++) {
System.out.print((i-(k - 1)*2 + m1) + " ");
m1 = getEnd(m, k);
}
if (m - t + 1 == i) {
t--;
m1 = getEnd(m, t) + m-3*t;
for (int k = 1; k <= p; k++) {
System.out.print((k + m1) + " ");
}
p += 3;
}
for (int k = t; k > 0; k--) {
if (i < 2*k) {
continue;
}
m1 = getEnd(m, k) + 2*k;
System.out.print((m1 - i) + " ");
}
System.out.println();
}
}
private static int getEnd(int m, int t) {
if (t == 0) {
return 0;
}
int e = 3*m - 3;
for (int k = 1; k < t; k++) {
e += 3*(m - 3*k) - 3;
}
return e;
}
Couple results:
1
2 6
3 4 5
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 the code after some optimization:
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= i; j++) {
int t = Math.min(Math.min(i - j + 1, j), m - i + 1);
int tSide = m - 3 * (t - 1);
int end = (m + tSide + 1) * (m - tSide) / 2;
if (t == j) {
// vertical line
System.out.print(end + i - t * 2 + 2 + " ");
} else if (t == m - i + 1) {
// bottom line
System.out.print(end + tSide + j - t + " ");
} else {
// diagonal
System.out.print(end + tSide * 2 + m - i - t + " ");
}
}
System.out.println();
}
Here ye go, direct calculation of value, based on x y and m. O(1) time, O(1) space. I believe this type of method may be the fastest.
UPDATE: Pass By wrote a beautiful, succinct generalization seemingly inspired by this - see that answer.
Haskell code:
import Control.Monad (forM_)
f x y m
| rem m 3 /= 0 = error "Can only construct triangle if m is divisible by 3."
| x > m || y > m || x < 1 || y < 1 = error "x and/or y out of bounds."
| y == 1 = 1
| y == m = x - 1 + m
| y <= lastTop = if x > div (if even y then y else y - 1) 2 + 1
then xOnHypotenuse
else xOnAltitude
| otherwise = let x0 = div (div (2*m) 3) 2 + 1 - (y - 2 * div m 3)
x1 = x0 + 2 + 3*(y - 2 * div m 3 - 1)
in if x < x0
then xOnAltitude
else if x > x1
then xOnHypotenuse
else xOnBase x0
where top y = div (m*(m + 1)) 2
- div ((m - 3 * div y 2)*(m - 3 * div y 2 + 1)) 2
lastTop = div (2 * m) 3
xOnAltitude = let triangleNum = x
appropriateY = 2*(triangleNum - 1)
toAdd = y - appropriateY
in top appropriateY + toAdd
xOnHypotenuse = let triangleNum = y - x + 1
appropriateY = 2*triangleNum
toSubtract = y - appropriateY
in top appropriateY - toSubtract
xOnBase baseStartingPosition =
let triangleNum = m - y + 1
appropriateY = 2*(triangleNum - 1)
baseStartingNum = top appropriateY
+ m - (2 + if triangleNum > 2
then 3*(triangleNum-2)
else 0) - 1
toAdd = x - baseStartingPosition
in baseStartingNum + toAdd
display m =
let maxLength = length . show $ div (m*(m + 1)) 2
pad num = let x = length . show $ num
in concat (replicate (maxLength - x) " ") ++ show num
in forM_ [1..m] (\y ->
forM_ [1..y] (\x -> if x == y
then putStrLn (pad $ f x y m)
else putStr $ (pad $ f x y m) ++ " "))
Output:
*Main> f 3 4 6
21
*Main> f 5 7 9
44
*Main> f 4 11 12
44
*Main> f 53214 64321 99999
2777096745
(0.01 secs, 518532 bytes)
*Main> display 6
1
2 15
3 16 14
4 17 21 13
5 18 19 20 12
6 7 8 9 10 11
