It's called spiral numbers. Being the expert programmers you are you've probably already have heard of it, but if not it goes a little something like this:
Given two positive integers a and b, output on the screen a rectangle with width = b numbers and height = a rows, containing the numbers from 1 to a*b in a spiraling fashion, as shown below. For a = 4 and b = 3, the output is:
1 2 3
10 11 4
9 12 5
8 7 6
The columns must be properly n+1 positions, where n is the number of digits in the decimal representation of a *b.
Write a program that prompts for a and b and then displays the appropriate rectangle of numbers.
Example:
If a = 3 and b = 4, the above rectangle should be
1 2 3 4
10 11 12 5
9 8 7 6
Here's some more examples from my own implementation written in snake tongue.
>>2
Yes, this problem is clearly recursive in nature. Print out the first B integers, shave off that row, rotate the entire table 90 degrees, and recurse from the current index.
The restriction on not being able to use an array makes this problem more interesting, as any sort of preprocessing is now out of the question. Regardless, there shouldn't be any problem solving this using only two indices. I'll begin working on a solution right away.
Name:
Anonymous2009-05-01 21:24
Seems like the fastest way, if you disregard the fact it is written in Java.
public class Spiral {
public static void main(String[] args) {
java.util.Scanner sc = new java.util.Scanner(System.in);
System.out.print("Width: ");
int width = sc.nextInt();
System.out.print("Height: ");
int height = sc.nextInt();
int[] xmove = {0, 1, 0, -1};
int[] ymove = {-1, 0, 1, 0};
int gap = 0, direction = 1, x = 0, y = 0, num = 1;
int[][] grid = new int[width][height];
int[] pad = new int[width];
while(true) {
grid[x][y] = num;
int len = String.valueOf(num).length();
if(len>pad[x]) pad[x] = len;
num++;
if(num>width*height) break;
x+=xmove[direction];
y+=ymove[direction];
if(x>=width-gap || x<gap || y>=height-gap || (y<gap+1 && direction==0)) {
x-=xmove[direction];
y-=ymove[direction];
if(direction==0)
gap++;
direction = (direction+1)%4;
x+=xmove[direction];
y+=ymove[direction];
}
}
for(int i=0; i<height; i++) {
for(int j=0; j<width; j++) {
int padAmt = pad[j] - String.valueOf(grid[j][i]).length();
StringBuilder tmpPad = new StringBuilder(padAmt+1);
for(int k=0; k<padAmt+(j==0?0:1); k++) tmpPad.append(" ");
System.out.print(tmpPad.toString()+grid[j][i]);
}
System.out.println();
}
}
}
Name:
Anonymous2009-05-01 21:25
>>5 To make things interesting, you are not allowed to use an array datatype of any kind, and your solution must be recursive. Good luck!
Name:
Anonymous2009-05-01 21:29
>>6
Funny, I don't recall any IOI/ACM-ICPC problems having any restrictions on how you should go about solving a problem- which is what this read like.
Name:
Anonymous2009-05-01 21:43
>>4
It's also recursive in the N*N case, where the N*N spiral contains the (N-2)*(N-2) spiral inside of it
Name:
Anonymous2009-05-01 22:34
Post your python implementation and I'll get some benchmarks going. I removed all arrays as well.
>>15
That's like saying "You can only use Sussmen; no DQNs allowed".
Name:
Anonymous2009-05-02 1:01
import List
import IO
spiral' a b i t | a == 0 = []
| b == 0 = []
| otherwise = [i+1..b+i]:(map reverse $ transpose $ spiral' b (a-1) (i+b) t)
spiral a b = spiral' a b 0 (a*b)
pad l str | length str < l = (++) str $ replicate (l - length str) ' '
| otherwise = str
printSpiral [] _ = return ()
printSpiral ([]:xss) l = putChar '\n' >> printSpiral xss l
printSpiral ((x:xs):xss) l = putStr (pad l $ show x) >> printSpiral (xs:xss) l
main = do
putStr "Width:"
hFlush stdout
w <- readLn
putStr "Height:"
hFlush stdout
h <- readLn
printSpiral (spiral h w) ((+1).length $ show $ w*h)
>>19
More like ~ $ ./9 << HERE 10000 10000 HERE
Segmentation fault
because you allocate huge amounts of memory without checking.
Here's a OMG OPTIMIZED version of >>14, benchmarks first: ~ $ gcc -std=c99 -O3 9.c -o 9 -Wall
9.c: In function 'main':
9.c:28: warning: operation on 'direction' may be undefined
~ $ time ./9 > /dev/null << HERE 7000 7000 HERE
real 0m8.192s
user 0m7.716s
sys 0m0.373s
~ $ gcc -std=c99 -O3 31.c -o 31 -Wall
~ $ time ./31 7000 7000 > /dev/null
real 0m6.938s
user 0m6.866s
sys 0m0.037s
And the code: #include <stdio.h>
#include <stdlib.h>
int main(int w, char **v)
{
if(w != 3) return 1;
char *e;
long a = strtol(v[1], &e, 0);
if(*e || !*v[1] || a < 0) return 2;
long b = strtol(v[2], &e, 0);
if(*e || !*v[2] || b < 0) return 3;
for(long ai = 0; ai < a; ai++) {
long c = 1, aq = a - 1, bq = b - 1, aiq = ai, biq = 0;
for(long bi= 0; bi < b; bi++, biq++) {
if(aiq > aq || biq > bq)
{
aq += 2;
bq += 2;
aiq++;
biq++;
c -= 2 * aq + 2 * bq;
} else if(aiq != 0 && biq != 0 && aiq < aq && biq < bq) {
c += 2 * aq + 2 * bq;
aiq--;
biq--;
aq -= 2;
bq -= 2;
}
long r;
if(aiq == 0) {
r = c + biq;
} else if(biq == bq) {
r = c + bq + aiq;
} else if(aiq == aq) {
r = c + bq + aq + (bq - biq);
} else if(biq == 0) {
r = c + bq + aq + bq + (aq - aiq);
} else {
return 5;
}
>>31
I find this result laughable. The time complexity of >>9 is clearly better, but because YOUR system can't allocate enough memory for it to run in larger test cases you write it off as worse in a SPEED benchmark on account of small test cases where the results differ by a couple of seconds? The point of a speed benchmark it to ignore memory consumption and look at the growth rate of time against different input- if you want to compare memory requirements you should go and do that, don't try and mix and match things to suit your case, and in particular don't try and say one algorithm is faster because it solves a problem two seconds faster for an extremely trivial test case.
>>1
God whoever wrote this problem is a fucking retard. "No arrays/lists" is absolute bullshit. There's no reason to put any kind of constraint on the nature of the data structures used to solve any problem.
You should instead say "solve this problem in constant space and logarithmic time (or better) with respect to the height/width of the spiral". Because that's really what you mean.
Name:
Anonymous2009-05-03 18:32
>>39
I understand if you weren't able to solve the problem, most people do take umbrage to the constraints. Nevertheless, if you ever go to a programming job interview, they will more than likely place arbitrary restrictions on problems, such as no arrays, no for loops, etc.