New Version of Ashish's Problem

[Amaj Nash (Suhas)]

Hi this problem is similar to that of Ashish's Problem. But a bit
complicated. Was asked in one of the ACM's competition I suppose. The
problem is that consider a spiral matrix increasing in cloackwise
fashion like this one..

7 8 9 ...
6 1 2
5 4 3

The position of element 1 is considered to b (0,0). Write a code to
find the position of the element entered. For example, if 3 is
entered, answer is (1,1). If 5 is entered, answer is (-1,-1)...
(The element can be any positive number...)

[ajinkya kale]

There is a mistake in the above problem...

co-ordinate of 3 is (1,1)
*co-ordinate of 5 is (-1,1) (this was the mistake)*

Ciao,
Ajinkya.

[Amaj Nash (Suhas)]

A solution by Ashish and Suhas.......

#include <stdio.h>

/*
43 44 45 46 47 48 49
42 21 22 23 24 25 26
41 20 7 8 9 10 27
40 19 6 1 2 11 28
39 18 5 4 3 12 29
38 17 16 15 14 13 30
37 36 35 34 33 32 31
*/
enum{RIGHT=0,LEFT=1,UP=2,DOWN=3};

int main()
{
int n,lrb=1,dub=1;
int i,j,k;
int x,y,dir,turnx,turny;
x=y=0;
dir=RIGHT;
scanf ("%d",&n);
turnx=turny=0;
for (i=1;i<n;i++)
{
switch(dir)
{
case 0:
x++;
turnx++;
if (turnx==lrb)
{
dir=3;
lrb++;
turnx=0;
}
break;

case 1:
x--;
turnx++;
if (turnx==lrb)
{
dir=2;
lrb++;
turnx=0;
}
break;

case 2:
y--;
turny++;
if (turny==dub)
{
dir=0;
dub++;
turny=0;
}
break;

case 3:
y++;
turny++;
if(turny==dub)
{
dir=1;
dub++;
turny=0;
}
break;
}
}

printf ("%d %d",x,y);
return 0;

[Ajinkya]

On Apr 12, 4:43 pm, "ajinkya kale" <kaleajin...@gmail.com> wrote:
> There is a mistake in the above problem...
>
> co-ordinate of 3 is (1,1)
> *co-ordinate of 5 is (-1,1) (this was the mistake)*
>
> Ciao,

#include<stdio.h>

int p;

int isLine(int n)
{
int no,i,first,temp,flag=0;

first=1;
temp=first;
p=0;
for(i=1;i<=8;i++)
{

while(temp<n)
{

temp=i+temp+8*p;
p++;
if(temp==n)
{

flag=1;
break;
}
}
if(flag==1)
break;
temp=first;
p=0;

}
return(i);

}

int main()
{
int no,i,first,temp,lineNo,cnt=0,x,y;
printf("Enter no. :");
scanf("%d",&no);

temp=no;
while(1)
{
temp--;
cnt++;
lineNo=isLine(temp);
if(lineNo!=9)
break;
if(temp==0)
break;
}
printf("\nLine no : %d\n",lineNo);
printf("\nSubtractions : %d\n",cnt);

switch(lineNo)
{
case 1:
x=p;
y=cnt;
break;
case 2:
x=p-cnt;
y=p;
break;
case 3:
x=-cnt;
y=p;
break;
case 4:
x=-p;
y=p-cnt;
break;
case 5:
x=-p;
y=-cnt;
break;
case 6:
x=cnt-p;
y=-p;
break;
case 7:
x=cnt;
y=-p;
break;
case 8:
if(cnt==1)
{
x=p+1;
y=-p;
}
else
{
x=p+1;
y=-p+cnt-1;
}
break;
}

printf("\nX : %d Y : %d\n",x,y);

return(0);
}

[ajinkya kale]

What i have done in my solution is that i got a relation for the elements on the +&-ve x axis and y axis and also the relations for nos. on the 45deg lines...from that i have calculated the co-ordinates of the middle elements...

 

The diff between the "differences" of nos. on these 8 axis(mentioned above) is 8..

 

eg:     21 22 23 24  25...

         20   7   8  9  10

         19   6   1  2  11

         18   5   4  3  12

         17 16 15 14  13  

 

       +ve X axis : 1, 2, 11, 28,... the diff bet nos. is 1, 9, 27.... so the diff bet the differences is 8

 

similarly 45deg line : 1,3,13,...diff are 2,10,... so diff bet diff.s is 8

 

Similarly we get the nos. on the 8 axes and using them as a reference we can find co-ordinates of other nos.  


 

[Jayanth Saimani]

21

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

i basically go around the matrix spirally by doing the following.
right,down,left,up

and the number of times i need to go in a particular dirction also
follows a logic
so for the innermost spiral..takin n=1;

for the right operation u need a extra 1 ...

so here is how it goes

so i have for n=1;
1 right to 2
then 1 down to 3
2 left to 5
2 up to 7

for n==2;
form 7
3 right to 10
3 down to13
4 left to 17
4 up tp 21

and so on...

so left and down are actually 2*n-1 steps
and right and up are 2*n steps

i will give my code...

On Apr 13, 7:32 pm, "ajinkya kale" <kaleajin...@gmail.com> wrote:
> What i have done in my solution is that i got a relation for the elements on
> the +&-ve x axis and y axis and also the relations for nos. on the 45deg
> lines...from that i have calculated the co-ordinates of the middle
> elements...
>
> The diff between the "differences" of nos. on these 8 axis(mentioned above)
> is 8..
>
> eg: 21 22 23 24 25...
> 20 7 8 9 10
> 19 6 1 2 11
> 18 5 4 3 12
> 17 16 15 14 13
>
> +ve X axis : 1, 2, 11, 28,... the diff bet nos. is 1, 9, 27.... so
> the diff bet the differences is 8
>
> similarly 45deg line : 1,3,13,...diff are 2,10,... so diff bet diff.s is 8
>
> Similarly we get the nos. on the 8 axes and using them as a reference we can
> find co-ordinates of other nos.
>

[Jayanth Saimani]

So in the process of travelling through the spiral ..i check whther
the number is encounter,,,
if it is then i print its co-ordinates
#include<stdio.h>
#include<conio.h>
int a=0,b=0,a1,a2,no;
int check(int d)
{
if(d==no)
{
printf("\n%d %d",a,b);
return 1;
}
return 0;
}

int main()
{
int i=0,mul=1,cnt=1,k=0;
int flag=1,st;
clrscr();
printf("Enter the no whoce co-ordinates to be found");
scanf("%d",&no);
for(k=0;k<100;k++)
{
a1=2*mul;
a2=(2*mul)-1;
//right
if(k!=0)
{
a1--;
}
if(k==0)
st=1;
else
st=0;
for(i=st;i<a1;i++)
{
if(check(cnt)==1)
{
flag=0;
}
if(flag==0)
break;
b++;
cnt=cnt+1;
}
if(flag==0)
break;
//down
if(flag!=0)
{
for(i=0;i<a2;i++)
{
if(check(cnt)==1)
{
flag=0;
}
if(flag==0)
break;
a++;
cnt++;
}
}

//left
if(k!=0)
{
a1++;
}
if(flag==0)
break;
//up
for(i=0;i<a1;i++)
{
if(check(cnt)==1)
{
flag=0;
}
if(flag==0)
break;
b--;
cnt++;

}
if(flag==0)
break;
for(i=0;i<=a2;i++)
{
if(check(cnt)==1)
{
flag=0;
}
if(flag==0)
break;
a--;
cnt++;
}
if(flag==0)
break;

mul++;

}

getch();
}

On Apr 16, 6:29 am, "Jayanth Saimani" <jayanthsaim...@gmail.com>
wrote:

[ashish gilda]

Jayant your logic is really good........
just tell me check is the function which checks weather we hav reached till input no. or not...

insted of that can we just run a loop for those many times...it will improve the complexity i think so....

   Tell me if i have misinterpreted ur logic.......

Cheers,

ashish

 

[jayanth saimani]

Ashish,

Yes we can do it that way.. and thats right,,,it will improve the complexity.

 

[Suhas Mahajan]

Hi Jayanth,

   Ur code seems difficult 2 understand. Can u please enum for Directions. Like define enum

enum Direction {RIGHT=0,LEFT,UP,DOWN}. I think that it will help to make your code better and do away with comments like right,left etc. Please do comment on this and may be we all could agree on some standards..... Everyone plz post your comments...

 

[Sangram Raje]

Won't it be better if we just give the algorithms here and use the code just to test against some cases. Understanding someone's code is anyway painful, unless we specifically want to debug some code.

I have even seen people write codes such as:

for(int i=n; i--; ){
 ....
}

instead of

for(int i=n-1; i >0; i--){
  ....
}

So, I feel : don't bother about the code ... just look at the algo!

What say?

Sangram

[ajinkya kale]

Exactly....

Only post codes for small and simple problems where efficiency matters.

eg: the reversing the order of words in the string.

 

Ciao,

Ajinkya

 

[Sangram Raje]

Test the reversing string codes on files generated by:

seq --separator=" " 1 1000000 > input
time ./a.out < input > output

should work ... check if the output is correct and report the User time taken.

Mine gives: 1.648s

Sangram

[BLOGGING! Nachiket R.Kakatkar]

Check out this one... (well I haven't gone through in much detail for
above algorithms(pgms)... but stilll just tell what do you think about
this approach)
one thing in this spiral form of writing the serial nos. with common
diff. = 1 is that the position of squares of nos. can be found easily.
Squares of odd number are on upper right corner for (n*n) square( n is
odd)

43 44 45 46 47 48 49

42 21 22 23 24 25 26.

41 20 7 8 9 10 27
40 19 6 1 2 11 28
39 18 5 4 3 12 29
38 17 16 15 14 13 30
37 36 35 34 33 32 31

And similarly the Squares of even number are on lower left corner for
(n*n) square( n is even)

Perhaps we can use this??... will post later on how ..?..(not yet
thought)
one issue that comes is now how to find the nearest 2 squares..???(in
good time)

On Apr 17, 6:04 pm, "Sangram Raje" <sangramr...@gmail.com> wrote:
> Test the reversing string codes on files generated by:
>
> seq --separator=" " 1 1000000 > input
> time ./a.out < input > output
>
> should work ... check if the output is correct and report the User time
> taken.
>
> Mine gives: 1.648s
>
> Sangram
>

> On 4/17/07, ajinkya kale <kaleajin...@gmail.com> wrote:
>
>
>
> > Exactly....
> > Only post codes for small and simple problems where efficiency matters.
> > eg: the reversing the order of words in the string.
>
> > Ciao,
> > Ajinkya
>

> > On 4/17/07, Sangram Raje <sangramr...@gmail.com> wrote:
>
> > > Won't it be better if we just give the algorithms here and use the code
> > > just to test against some cases. Understanding someone's code is anyway
> > > painful, unless we specifically want to debug some code.
>
> > > I have even seen people write codes such as:
>
> > > for(int i=n; i--; ){
> > > ....
> > > }
>
> > > instead of
>
> > > for(int i=n-1; i >0; i--){
> > > ....
> > > }
>
> > > So, I feel : don't bother about the code ... just look at the algo!
>
> > > What say?
>
> > > Sangram
>

> > > On 4/17/07, Suhas Mahajan <amaj.n...@gmail.com > wrote:
>
> > > > Hi Jayanth,
> > > > Ur code seems difficult 2 understand. Can u please enum for
> > > > Directions. Like define enum
> > > > enum Direction {RIGHT=0,LEFT,UP,DOWN}. I think that it will help to
> > > > make your code better and do away with comments like right,left etc. Please
> > > > do comment on this and may be we all could agree on some standards.....
> > > > Everyone plz post your comments...
>

> ...
>
> read more »

[BLOGGING! Nachiket R.Kakatkar]

One more thought...
Can we recursively do it like this...go on asking the next known
number his position such that if you know his position then your
position is known...
this asking will continue recursively till a known number comes..???
(like in factorial recursion we go on till we get 0 or 1because we
"know" that 0! and 1! is 1)... just a random thought plz comment...

On Apr 18, 6:09 am, "BLOGGING! Nachiket R.Kakatkar"

> ...
>
> read more »

[ajinkya kale]

I think this will be difficult...instead go outwards from 1 and follow the solution posted by Suhas(i think)

I think thats the simplest one.(Read my algo too though not the most efficient one)

 

[BLOGGING! Nachiket R.Kakatkar]

Frankly I didnt( try to also) read the other codes... its difficult!!
I read Suhas's code... i got the idea... i dont know really what
happens to efficiency etc.
... but still I "feel" that may be your(Ajinkya) or this(my) approach
might work better because it tries to find a pattern..?????

On Apr 18, 7:21 am, "ajinkya kale" <kaleajin...@gmail.com> wrote:
> I think this will be difficult...instead go outwards from 1 and follow the
> solution posted by Suhas(i think)
> I think thats the simplest one.(Read my algo too though not the most
> efficient one)
>

> On 4/17/07, BLOGGING! Nachiket R.Kakatkar <nachiketkakat...@gmail.com>

> ...
>
> read more »

[Nachiket]

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

Square approach cotd...
One thing is that squares we can find directly the co-ords.
Let ToFind be the input number whose co-ords are to be found.
User enters ToFind.
We find the two closest squares to this ToFind on either side.
for
e.g. if ToFind = 30 then 2 closest squares are 36 and 25. (greater
side square is even)
or
if ToFind = 40 then closest squares are 49 and 25 (greater side square
is odd)
There is a similar method in both cases to travel from the higher
square to lower square...
if higher square is even then keep Y const. and go on decreasing X
till we have traversed upto the number
Higher - ((Higher-Lower)/2)
And then keep X const and traverse upto the lower square..
And in this road from higher to lower somewhere we will encounter
ToFind...
else if
if higher square is odd then keep X const. and go on decreasing Y till
we have traversed upto the number
Higher - ((Higher-Lower)/2)
And then keep Y const and traverse upto the lower square..
And in this road from higher to lower somewhere we will encounter
ToFind...
What say ??????????

PS: The direction convention may change certain signs but this an
overalll approach.....

On Apr 18, 7:50 am, "BLOGGING! Nachiket R.Kakatkar"

> ...
>
> read more »

[Nachiket]

Sorry.!!! in above while copy pasting mistakingly foll. happened..

" e.g. if ToFind = 30 then 2 closest squares are 36 and 25. (greater
side square is even)
or
if ToFind = 40 then closest squares are 49 and [ 25 ] (greater side
square
is odd) "

[ 25] is mistake it should be 36....

Plz tell other unnoticed flaws....

> ...
>
> read more »