Square spiral make you giddy?

Computer Science Level 2

Consider the rectangular spiral in the image below. It starts from the origin and twirls and twirls forever in an anticlockwise direction along the integer coordinates of the Cartesian coordinate plane.Each point along the spiral is numbered with an integer $Z$ as shown in the image below.

What is the value of the integer $Z$ at the coordinate $(12,-22)$ ?

Details and assumptions

As an explicit example $Z$ is $10$ for $(2,0)$ , $3$ for $(0,1)$ and $10$ for $(2,0)$ .

The answer is 2014.

6 solutions

Discussions for this problem are now closed

Thaddeus Abiy
Apr 10, 2014

def f(m,n):
    Z = 0
    while((m!=0) or (n!=0)):
        if((n>m) and (n>=-m)):
            m+=1
        elif((n>=m) and (n < -m)):
            n+=1
        elif((n<=m) and (n > -m+1)):
            n-=1
        else:
            m-=1
        Z+=1
    return count
print f(12,-22)

Nice observation. I couldn't think of any simple pattern of changing directions and ended up implementing a complicated algorithm.

Nice solution and nice problem. Keep posting more.

Lokesh Sharma - 7 years, 2 months ago

Seriously, nicely observed.

Sangyatri Singh - 7 years, 2 months ago

you're a programer!!!

Dương Tươi - 7 years, 2 months ago

java solution

class Temp {

public static void main(String... s)
{  
    int x = 0,y = 0;
    int cx = 0,cy = 0;

    int axis_x=12,axis_y=-22;

    int count = 0;

    for(int i = 1;;i++)
    {
        x=i;
        y=i;

        if(x%2!=0&&(cx!=axis_x||cy!=axis_y))
        {
            for(int j = 0 ; j < x; j++)
            {
              cx++;
              count++;
              System.out.println("count="+count+",i="+i);
               if(cx==axis_x)
               {
                   break;
               }
            }
        }
        else if(x%2==0&&(cx!=axis_x||cy!=axis_y))
        {
            for(int j = 0 ; j < x; j++)
            {
              cx--;
              count++;
              System.out.println("count="+count+",i="+i);
              if(cx==axis_x)
               {
                   break;
               }
            }

        }

        if(y%2!=0&&(cx!=axis_x||cy!=axis_y))
        {
            for(int k = 0 ; k < y; k++)
            {
              cy++;
              count++;
              System.out.println("count="+count+",i="+i);
               if(cy==axis_y)
               {
                   break;
               }
            }
        }
        else if(y%2==0&&(cx!=axis_x||cy!=axis_y))
        {
            for(int k = 0 ; k < y; k++)
            {
              cy--;
              count++;
              System.out.println("count="+count+",i="+i);
              if(cy==axis_y)
               {
                   break;
               }
            }

        }


      System.out.println("x="+cx);
      System.out.println("y="+cy);
      System.out.println("Xcount="+count+",i="+i);


    if(cx==axis_x&&cy==axis_y)
     break;

    }



}

}

Saurav Dash - 7 years, 1 month ago

Great job ! Much better than my code :D

Nhók Đăng - 6 years, 8 months ago

@Thaddeus Abiy I wanted to thank you for letting us know that Google Code Jam has started.

I read your status and was able to submit the problems just a couple of hours before the deadline. It was very interesting. How much did you scored in the Qualification Round?

Lokesh Sharma - 7 years, 2 months ago

You are welcome.Unfortunately the power went out as soon I did the first two problems and it didn't come the whole night.I was able to scrape a mere 25 points and qualify. The problems were very interesting though..It would be great if someone shared them here.

Thaddeus Abiy - 7 years, 2 months ago

It is so dumb to write a computer program and have the computer solve it for you just by brute force enumeration. At least the mathematicians were intelligent enough to find a formula to calculate it by themselves

Khushro Shahookar - 7 years ago

It seems you are at a wrong place.Computer Science is not your cup of tea

Swapnil Bhargava - 7 years ago

Pi Han Goh
Apr 9, 2014

Let $X = Z + 1$ .

$X = (2 \cdot 0 + 1)^2$ for $(0,0 )$

$X = (2 \cdot 1 + 1)^2$ for $(1,-1 )$

$X = (2 \cdot 2 + 1)^2$ for $(2,-2 )$

$\ldots$

$X = (2 \cdot 22 + 1)^2 = 2025$ for $(22,-22 )$

$X = 2025 - 10 = 2015$ for $(12,-22 )$

Answer is $2015- 1 = \boxed{2014}$

Can you please explain why multiplying every first value with 2? Like (2.0+1)^2 & (2.1+1)^2 etc. Inside every bracket, how "2" came, any rules? Thanks.

Arsalan Iqbal - 7 years, 2 months ago

Nice!

Thaddeus Abiy - 7 years, 2 months ago

Bhavik Knight
Apr 14, 2014

Diag (1,0), (2,-1),(3,-2)....(23,-22) say (n+1, -n)

Int Z at points [n+1- ( - n)]^2 i.e. (2n+1)^2

z(23,-22)=[ 2x22 + 1]^2= 45x45= 2025

so, z(12,-22)= z(23,-22)-11= 2025-11= 2014 [ current year ;) ]

Exactly !!!

Shakti Kheria - 6 years, 9 months ago

Syler Haker
Apr 16, 2014

My-Solution in Python :

moves=[(1,0),(0,1),(-1,0),(0,-1)]

def SquareSpiral(x,y):
    z=0; i=0
    while True:
        for j in range(int(i/2)+1):
            if (x,y)==(0,0):
                return z
            z+=1
            x-=moves[i%4][0]
            y-=moves[i%4][1]
        i+=1

print(SquareSpiral(12,-22))

Python + Modular Arithmetic = The Shortest Working Code for Solving this Problem !

Syler Haker - 6 years, 11 months ago

Lokesh Sharma
Apr 12, 2014

Nice Problem.

Here's my solution in Python:

moves = {'up':[0, 1],
         'down':[0, -1],
         'left':[-1, 0],
         'right':[1, 0]}

class position(object):
    '''
    Makes a position object
    '''
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def move(self, oneMove):
        delta_x, delta_y = moves[oneMove]
        self.x += delta_x
        self.y += delta_y

    def getPosition(self):
        return [self.x, self.y]

    def __str__(self):
        return '<' + str(self.x) + str(self.y) + '>'

def getZ(pos):
    '''
    Returns Z value of given postion
    '''
    moveOrder = ['right', 'up', 'left', 'down'] 
    point = position(0, 0) # Initializes a position object
    z = 0
    noOfSameMoves = 1 # It gets incremented after every 2 directions
    pointer = 0 # Useful to change direction after every noOfSameMoves

    while True:
        for i in range(noOfSameMoves):
            point.move(moveOrder[pointer%4])
            z += 1
            if point.getPosition() == pos.getPosition():
                return z

        pointer += 1
        for i in range(noOfSameMoves):
            point.move(moveOrder[pointer%4])
            z += 1
            if point.getPosition() == pos.getPosition():
                return z            
        pointer += 1

        noOfSameMoves += 1

I was very surprised to see that this bizarre looking code actually worked and that too in the first attempt. This is the story most of the time. It works when you actually didn't expect it to work at all and sometimes it abruptly fails when you are dead sure that it will work.

Lokesh Sharma - 7 years, 2 months ago

I think I was able to solve the problem because of spirals. Hhaha!

Lokesh Sharma - 7 years, 2 months ago

Anthony Ferreira
Apr 15, 2014

(-n, -n) => 2x1+2x2+2x3+...+4n = 2(1+2+...+2n) = 2n(1 + 2n)

(-22, -22) => 2(1+...+44) = 44(1+44) = 1980

D = (12, -22) - (-22, -22) = (34, 0)

Z = 1980 + 34 = 2014

Spiral sp=new Spiral(0,0,100); int x=sp.getX(); int y=sp.getY(); int z=0;

    for(int i=1;i<=sp.getZ();i++)
    {
        for(int j=1;j<=i;j++)
        {
            z++;
            x++;
            if(x==12 && y==-22)
            {
                System.out.println("Z = "+z);
            }

        }

        for(int j=1;j<=i;j++)
        {
            z++;
            y++;

        }
        i++;

        for(int j=1;j<=i;j++)
        {
            z++;
            x--;
            if(x==12 && y==-22)
            {
                System.out.println("Z = "+z);
            }

        }
        for(int j=1;j<=i;j++)
        {
            z++;
            y--;
        }

    }

Samih El Bouzidi - 7 years, 1 month ago

Square spiral make you giddy?

The answer is 2014.

6 solutions

Discussions for this problem are now closed

0 pending reports