Code Golf: Clockwise Spiral

Discussion

It's been a while (and everyone is well-rested after Advent Of Code!) so let's run another round of Code Golf.

Your task is navigating in a grid-like labyrinth in a clockwise spiral pattern. As it traverses the matrix, it collects characters, revealing a secret message.
Your challenge: find the shortest, most elegant code to decode this spiral cipher.
Input:
1. A multidimensional string array with comma separated characters (n x n)
2. Starting coordinates X and Y

Output:
The decoded message as a single string

Constraints:
1. 1 ≤ n ≤ 100
2. The starting position is always valid within the matrix
3. The matrix contains only printable ASCII characters

Example:

Input:

 matrix(1)="H,E,L"
 matrix(2)="R,L,L"
 matrix(3)="O,W,O"

Starting position: (1, 1)

Output: "HELLOWORL"

Note

Use this code to check the solution length

Rules

The signature of the contest entry MUST be:

Class codeGolf.ClockwiseWord
{

ClassMethod Solution(ByRef matrix, x, y) As %String
{
    // Your solution here
}

}

It is forbidden to modify class/signature, including but not limited to:
- Adding inheritance
- Setting default argument values
- Adding class elements (Parameters, Methods, Includes, etc).
It is forbidden to refer to non-system code from your entry. For example, this is not a valid entry:
```
ClassMethod Build(f As %Integer)
{
  W ##class(myPackage.myClass).test(a)
}
```
The use of $ZWPACK and $ZWBPACK is also discouraged.

You can use this test case:

Class codeGolf.unittests.ClockwiseWord Extends %UnitTest.TestCase
{
    Method TestSolutions()
    {
        Set matrix($Increment(matrix)) = "H,E,L"
        Set matrix($Increment(matrix)) = "R,L,L"
        Set matrix($Increment(matrix)) = "O,W,O"
        Do $$$AssertEquals(##class(codeGolf.ClockwiseWord).Solution(.matrix, 1, 1), "HELLOWORL")
    }

    Method TestStartTopRight()
    {
        Set matrix($Increment(matrix)) = "A,B,C"
        Set matrix($Increment(matrix)) = "H,I,D"
        Set matrix($Increment(matrix)) = "G,F,E"
        Do $$$AssertEquals(##class(codeGolf.ClockwiseWord).Solution(.matrix, 1, 3), "CDEFGHABI")
    }

    Method TestStartMiddleRight()
    {
        Set matrix($Increment(matrix)) = "A,B,C"
        Set matrix($Increment(matrix)) = "H,I,D"
        Set matrix($Increment(matrix)) = "G,F,E"
        Do $$$AssertEquals(##class(codeGolf.ClockwiseWord).Solution(.matrix, 2, 3), "DEFGHABI")
    }

    Method Test1x1Matrix()
    {
        Set matrix($Increment(matrix)) = "A"
        Do $$$AssertEquals(##class(codeGolf.ClockwiseWord).Solution(.matrix, 1, 1), "A")
    }

    Method Test4x4Matrix()
    {
        Set matrix($Increment(matrix)) = "C,O,D,E"
        Set matrix($Increment(matrix)) = "U,C,H,G"
        Set matrix($Increment(matrix)) = "M,U,F,O"
        Set matrix($Increment(matrix)) = "S,I,F,L"
        Do $$$AssertEquals(##class(codeGolf.ClockwiseWord).Solution(.matrix, 1, 1), "CODEGOLFISMUCHFU")
    }

    Method TestStartBottomLeft()
    {
        Set matrix($Increment(matrix)) = "1,2,3"
        Set matrix($Increment(matrix)) = "8,9,4"
        Set matrix($Increment(matrix)) = "7,6,5"
        Do $$$AssertEquals(##class(codeGolf.ClockwiseWord).Solution(.matrix, 1, 3), "781234569")
    }

    Method TestAllSameCharacters()
    {
        Set matrix($Increment(matrix)) = "X,X"
        Set matrix($Increment(matrix)) = "X,X"
        Do $$$AssertEquals(##class(codeGolf.ClockwiseWord).Solution(.matrix, 1, 1), "XXXX")
    }
}

Set matrix($Increment(matrix)) = "C,O,D,E" Set matrix($Increment(matrix)) = "U,C,H,G" Set matrix($Increment(matrix)) = "M,U,F,O" Set matrix($Increment(matrix)) = "S,I,F,L"

ClassMethod Solution(ByRef n, r, c) As %String { s (a,p)=$g(n),b=1,q=1,o="" g:c=1 4:r>1 g:c=a 3:r=p,2 g 3:r=p 1 s e=0 F c=c:1:a{d m} S q=$i(r) 2 F r=r:1:p{d m} S c=c-1,a=c 3 F c=c:-1:b{d m} S r=r-1,p=r 4 F r=r:-1:q{d m} S b=$i(c) g:e 1 q o m S o=o_$P(n(r),",",c),e=1 }

Stuart Strickland · Feb 18

It took me a minute or two to spot that you had gone with the valid assumption that n would be defined as the number of rows and columns from $I(matrix) which I didn't notice, and the matrix would be square.

I've gone for an interpretation that I think is equivalent to clockwise, the result is the same: I'm going East (right), South (down), West (left), North (up), then back to East again. Heading in a direction until a dead end then changing direction. As such I have variable V to indicate direction of movement V=1 for vertical (up or down, north or south) and V=0 for horizontal (left or right, west or east). Then another variable D, D=1 indicating increase and D=-1 for decrease. When you hit a dead end change V with V='V and if V becomes 0 then D=-D. That will always spin you clockwise but without limits so you need code to spot a dead end. Also, as others have said, there's no way to know which direction to start in. If you are in the bottom left corner do you start by going right or up?

Here's my code with comments:

ClassMethod Solution(ByRef m, x, y) As %String
{
// enforcing a decreasing spiral, 210 without comments
// Right means change y with V=0, D=1
// Down means change x with V=1, D=1
// Left means change y with V=0, D=-1
// Up means change x with V=1 ,D=-1
//
// first letter starts the word
s w=$p(m(x),",",y),V=0,D=1
// mark the position so it can't be re-used
// get the next letter from $$n, end when no letter comes back, extend the word if it does, and repeat
a s n(x,y)=w,l=$$n q:e=3 w s w=w_l g a
// default start position to right and clockwise
// quit if you've tried 2 directions
// get the letter in that direction
// if no letter or already got then change direction clockwise
// to change direction, if currently vertical then you won't be for the next move and vice versa
// if you are now horizontal then change direction
n() q:$i(e)=3 "" s X=V*D+x,Y='V*D+y,l=$p($g(m(X)),",",Y) i l=""!$d(n(X,Y)) S V='V S:'V D=-D q $$n()
// flag any anticlockwise letter as used
s n(V*-D+x,'V*-D+y)=0,x=X,y=Y,e=0 q l
}

0 0

Set matrix($INCREMENT(matrix)) = "A,B,C" Set matrix($INCREMENT(matrix)) = "H,I,D" Set matrix($INCREMENT(matrix)) = "G,F,E" d $$$AssertEquals(..Solution(.matrix, 1, 1), "ABCDEFGHI") d $$$AssertEquals(..Solution(.matrix, 1, 2), "BCDEFGHI") d $$$AssertEquals(..Solution(.matrix, 1, 3), "CDEFGHABI") d $$$AssertEquals(..Solution(.matrix, 2, 3), "DEFGHABI") d $$$AssertEquals(..Solution(.matrix, 3, 3), "EFGHABCDI") d $$$AssertEquals(..Solution(.matrix, 3, 2), "FGHABCDI") d $$$AssertEquals(..Solution(.matrix, 3, 1), "GHABCDEFI") d $$$AssertEquals(..Solution(.matrix, 2, 1), "HABCDEFI")

Set matrix($INCREMENT(matrix)) = "A,B,C" Set matrix($INCREMENT(matrix)) = "H,I,D" Set matrix($INCREMENT(matrix)) = "G,F,E" d $$$AssertEquals(..Solution(.matrix, 1, 1), "ABCDEFGHI") d $$$AssertEquals(..Solution(.matrix, 1, 2), "BCDEFGHI") d $$$AssertEquals(..Solution(.matrix, 1, 3), "CDEFGHI") d $$$AssertEquals(..Solution(.matrix, 2, 3), "DEFGHI") d $$$AssertEquals(..Solution(.matrix, 3, 3), "EFGHI") d $$$AssertEquals(..Solution(.matrix, 3, 2), "FGHI") d $$$AssertEquals(..Solution(.matrix, 3, 1), "GHI") d $$$AssertEquals(..Solution(.matrix, 2, 1), "HI")

Set matrix($INCREMENT(matrix)) = "A,B,C" Set matrix($INCREMENT(matrix)) = "H,I,D" Set matrix($INCREMENT(matrix)) = "G,F,E" d $$$AssertEquals(..Solution(.matrix, 1, 1), "ABCDEFGHI") d $$$AssertEquals(..Solution(.matrix, 1, 2), "BCDEFGHA") // !!? d $$$AssertEquals(..Solution(.matrix, 1, 3), "CDEFGHABI") d $$$AssertEquals(..Solution(.matrix, 2, 3), "DEFGHABC") // !!? d $$$AssertEquals(..Solution(.matrix, 3, 3), "EFGHABCDI") d $$$AssertEquals(..Solution(.matrix, 3, 2), "FGHABCDE") // !!? d $$$AssertEquals(..Solution(.matrix, 3, 1), "GHABCDEFI") d $$$AssertEquals(..Solution(.matrix, 2, 1), "HABCDEFG") // !!?

1x1 2x2 3x3 4x4 5x5 a-a a-d a-i a- a-y a ab abc abcd abcde dc hid lmne pqrsf gfe kpof oxytg jihg nwvuh mlkji Matrix: 4x4, starting points: (1,1) --> abcdefghijklmnop (1,2) --> bcdefghijklmnop (2,3) --> nop (2,4) --> efghijklmnop (3,1) --> klmnop (3,2) --> p (3,3) --> op You always go from the starting point to the endpoint (in the center)

Julius Kavay · Feb 13

You talk about a multidimensional matrix but obviously mean a two dimensional matrix - right?
You talk about a matrix of size: N x N but neither the given code signaure nor the task description specify where the value N is given. In your examples you create the matrix by continuous incrementing the root node of matrix - the root node is equal to N, is this always valid or just in your examples or in other words, would this be a valid call:

kill box
set box(1)="A,B"
set box(2)="C,D"

do ##class(codeGolf.ClockwiseWord).Solution(.box,1,1)

I know, I one can obtain the value for N with a simple $order()

set N = $order(matrix(""),-1)

You expect a correct solution, we expect correct a description
justmy2cents

1 0

Vitaliy Serdtsev · Feb 14

It seems to me that there is a typo in the TestStartBottomLeft method:

should be  Do $$$AssertEquals(##class(codeGolf.ClockwiseWord).Solution(.matrix, 3, 1), "781234569")

2 0

Robert Cemper · Feb 16

The clockwise logic is simple for a 3*3 matrix
though starting with 4*4 there is some rule missing on how the handle a dead end
Starting at a corner (1,1) or similar is trivial.
BUT: starting at any other point may create a rathole or miss some boxes

Start (1,1) is in the example but
Start (1,2) runs ODEGOLFISMU what is the next to (2,1) ? (1,1) or (2,2) or ??
worse with Start(2,2) already the first according to description could be
up (1,2) or right (2,3) or left (2,1) leaving dead ends clockwise.
And this is only with N=4 larger grids may create multiple lost cells.
Clockwise spiral is just not detailed enough for a UNIQUE result to collect ALL cells
A rule how to handle / skip already consumed cells might improve.
Just as I type a non straight spiral solution to (2,2) consuming the full matrix
might be CUISMUCODEGOLFFH
I fail to imagine grids >5*5

Just at a 2nd view also N=3 has that problem.
StarMiddleTop (1,2) has the same Problem as MiddleRight (2,3)
Not all characters of the matrix show up in the result.
it shows DEFGHABI but DEFGHABC looks similar correct according to published rules
Is this expected behavior?

2cents more

Paul Waterman · Feb 17

I am finding this quite a challenge.

I have made the following assumptions, based on comments from others:

The array will always have N at the top. The data will always be square.

The bottom left test is corrected to Solution(.matrix,3,1)

You can only start on the edge of the square (first or last row/column). I am not sure what starting in the middle of a 5x5 grid would mean.. My program misses/re-uses some data.

Starting in the middle of an edge will miss any bits that are anti-clockwise (this is covered in the test: Solution(.matrix, 2, 3)="DEFGHABI" which misses the C)

An empty/N=0 array returns "", although the initial requirement says n>=1, so could save a few chars there.

My solution is 231.

Stuart Strickland · Feb 17

Hello Paul.

I think I have the same issue as you with missing the anticlockwise characters. Making it miss them after going round once cost me 29 characters. I'll put some thought into that. Currently at 227 chars.

Am happy with the clockwise algorithm but could probably improve on limiting the spiral to stay inside itself.

Paul Waterman · Feb 18

Hi Stuart,

I did not publish my solution because I thought 231 sounded a bit embarrassing for this game. 227 sounds in the same league so I am happier now.

I also applied the "what would Stuart do?" theory to my shot, and what do you know: 227.

Stuart, neat but not complete. The initial tests say bottom left start goes up.

On the following test:

Yours fails when starting on E,F,G,H.

I have tidied up mine and got rid of the mess of gotos at the top and assumes the matrix is not empty, current score 214.

You are correct Paul, but there's a problem with other tests too. The one with 3,1 above could return GHABCDI because you could argue that when the spiral leaves an outer edge it should never return to it. If the test that starts at 1,2 doesn't return to row 1 then why should 1,3 return to row 1 after leaving? These could be the correct tests:

Julius Kavay · Feb 18

Exactly, that's the correct way (according to my opinion, and it seems, you go with me).
In the above example, a 'H' never may be followed by an 'A', that would make a full circle but we want a spiral...

Stuart Strickland · Feb 19

Hi Julius, I was playing Devil's "avocado 😁" with that. One could argue the case for that being the correct approach. One could also argue for Paul's unit tests based on seeing no reason why rotational symmetry couldn't apply. (I think my solution for that is 225 and doesn't beat my friend Paul's answer so I don't like it.) The point is that the spiral has to get smaller somewhere but we haven't been given a clear enough rule to follow. In the example in the question, the spiral only turns inward when it hits a used letter or a corner - a dead end as @Robert Cemper puts it. The unit tests below could also be valid. (My solution for this is 199)

There's an unwritten rule in the question that could be "as a human, make a decision when to turn inwards to make sense out of the order of letters". How do you code that?

Paul Waterman · Feb 19

There is only one person who can answer what the expected result should be. I think Eduard made it clear by providing the tests that should pass.

TestStartMiddleRight - this is the same as the my test starting at D
TestStartBottomLeft - this is the same as my test starting at G

My other tests were based on simply rotating the matrix - I was not happy that my code was passing those two tests but could still be wrong, in my opinion, starting at the bottom middle of the grid.

My last go at this is 212.

I hope the next hole is not as controversial.

Julius Kavay · Feb 19

I think he didn't made it clear. The examples Test1x1Matrix() and TestAllSameCharacters() are exaples without any information. And by the way, a 1x1 and 2x2 matrices aren't the best examples to show a spiral way!

In absence of clear rules, it's wasting time to write a code. Or one makes his own rule and writes a code which confirms to this rule.

My perception of travelling along the cells of a quadratic matrix in a clockwise spiral way is this You start at the big red point (1,1) and go along the cells until the last cell. Of course, you can start at any point, including the last one (then is your start and endpoint are the same and no motion is requered). If you start, for example in a 4x4 matrix at (1,3), this means, you skip the first two cells: (1,1) and (1,2) and if you reached the last point (3,2) there is no way (I mean, no sense) to came back to (1,1)

Julius Kavay · Feb 20

in the above answer, after "...spiral way is this" and "You start..." there should be a picture - it seems, something is went wrong with the upload. I try it a second time...

Now we have two time the same image... nice

Robert Cemper · Feb 20

I followed this rules with (1,1) as base
Starting any other point than (1,1) simply shortens the spiral.
now I reached 259

I really dislike the result as it is composed so unfriendly
just to save same bytes that nobody asked for.

Julius Kavay · Feb 17

I absence of welldefined rules, it's a matter of opinion, how one does a "clockwise spiral walk" in a quadratic matrix.
First, I would define the TOP-LEFT corner as point (1,1) with the addition, that (1,1) is always the top-left corner.
For a 1x1, 2x2, 3x3, 4x4 and 5x5 matrix I would go this way (I use the 25 letters to show my clockwise spiral way, starting at top-left with the letter 'a'):

All odd matrices (1x1, 3x3, 5x4,...) have a middle-point at (N+1\2, N+1\2)

According to original constraints #2 "The starting position is always valid within the matrix". I interpret that as
one can start at any point a clockwise spiral reading, for example, reading the 4x4 matrix, starting at (3,4) gives you: 'fghijklmnop' The sequence 'abcde' is skipped.

A reading like: 'fghijklabcdenm' gives a clockwise spiral but never touches 'op' on the other hand, reading like: 'fghijklabcdenopm' is not clockwise-spiral because at the sequence 'eno' suddenly takes an counterclockwise turn!

Hi Julius,

This interpretation makes things easier to understand - I am not sure how it impacts the program. However it does not match the test cases.

In the test TestStartMiddleRight all letters are used apart from C. In your example above, starting at (3,4), I think this means use all letters except d and e.

TestStartBottomLeft also uses all of the grid, which I think your interpretation does not. Although you do not show what you expect when your starting point is in a corner.

These two tests are, I think, making up most of my program: working out which direction you are facing at the start and then making sure you go to the edges you have not covered yet. But its also what makes starting in the middle so hard: what direction to start walking?

I think this interpretation would require a different program to mine.

Robert Cemper · Feb 19

I see a general problem in interpretation of the "spiral"
so I took some drawing for aquadratíc and a rectangular matrix.

depending on the starting point you have to take a pre-designed direction
if you hit the diagonal you have to turn right
you have to invalidate the row/column you just were on
proceeding to invalid points is not allowed.
start a the central point is an immediate termination as it has no direction to proceed

The diagonal came to my mind thinking how to NOT increase the imaginative radius of the spiral.
The related subscripts for the diagonale points of an n*m are found as (-n/2+x,-m/2+y)
The pink subscripts are obviously (n/2,m/2) and might be just virtual.

As subscripts start with 1 and first piece position is also 1
some more adjustment of coordinates is required

I haven't written any useful line yet.