Matrix arrangement issues in php

I would like to know some solutions to such a开发者_如何学C problem.

It is given a number lets say 16 and you have to arrange a matrix this way

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

the language doesn't matter, (preferably PHP);

[EDIT: Update] If language doesn't matter:

Go to: http://rosettacode.org/wiki/Spiral_matrix

In PHP:

Here you go:

<?php
function getSpiralArray($n)
{
    $pos = 0;
    $count = $n;
    $value = -$n;
    $sum = -1;

    do
    {
        $value = -1 * $value / $n;
        for ($i = 0; $i < $count; $i++)
        {
            $sum += $value;
            $result[$sum / $n][$sum % $n] = $pos++;
        }
        $value *= $n;
        $count--;
        for ($i = 0; $i < $count; $i++)
        {
            $sum += $value;
            $result[$sum / $n][$sum % $n] = $pos++;
        }
    } while ($count > 0);

    return $result;
}

function PrintArray($array)
{
    for ($i = 0; $i < count($array); $i++) {
        for ($j = 0; $j < count($array); $j++) {
            echo str_pad($array[$i][$j],3,' ');
        }
        echo '<br/>';
    }
}

$arr = getSpiralArray(4);
echo '<pre>';
PrintArray($arr);
echo '</pre>';
?>

In python:

from numpy import *

def spiral(N):
    A = zeros((N,N), dtype='int')
    vx, vy = 0, 1 # current direction
    x, y = 0, -1 # current position
    c = 1
    Z = [N] # Z will contain the number of steps forward before changing direction
    for i in range(N-1, 0, -1):
        Z += [i, i]
    for i in range(len(Z)):
        for j in range(Z[i]):
            x += vx
            y += vy
            A[x, y] = c
            c += 1
        vx, vy = vy, -vx
    return A

print spiral(4)  

Looks like the snake game might work. Track a direction vector, and turn right 90 degrees every time you hit a side or a populated square. The tail keeps extending indefinitely :)

Edit : Snakey v0.1 in C#. Works for non square grids too ;)

using System;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        public enum Direction
        {
            Up,
            Down,
            Left,
            Right
        }

        static void Main(string[] args)
        {
            int[,] maze;

            Direction currentDirection = Direction.Right;

            bool totallyStuck = false;
            bool complete = false;
            int currentX = 0;
            int currentY = 0;
            int boundX = 4;
            int boundY = 5;
            int currentNumber = 1;
            int stuckCounter = 0;
            bool placeNumber = true;

            maze = new int[boundY, boundX];

            while ((!totallyStuck) && (!complete))
            {
                if (placeNumber)
                {
                    maze[currentY, currentX] = currentNumber;
                    currentNumber++;
                    stuckCounter = 0;
                }

                switch (currentDirection)
                {
                    case Direction.Right:
                        // Noted short Circuit Bool Evan
                        if ((currentX + 1 < boundX) && (maze[currentY, currentX + 1] == 0))
                        {
                            placeNumber = true;
                            currentX++;
                            stuckCounter = 0;
                        }
                        else
                        {
                            placeNumber = false;
                            stuckCounter++;
                        }

                        break;
                    case Direction.Left:
                        if ((currentX - 1 >= 0) && (maze[currentY, currentX - 1] == 0))
                        {
                            placeNumber = true;
                            currentX--;
                            stuckCounter = 0;
                        }
                        else
                        {
                            placeNumber = false;
                            stuckCounter++;
                        }
                        break;
                    case Direction.Down:
                        if ((currentY + 1 < boundY) && (maze[currentY + 1, currentX] == 0))
                        {
                            placeNumber = true;
                            currentY++;
                            stuckCounter = 0;
                        }
                        else
                        {
                            placeNumber = false;
                            stuckCounter++;
                        }
                        break;
                    case Direction.Up:
                        if ((currentY - 1 >= 0) && (maze[currentY - 1, currentX] == 0))
                        {
                            placeNumber = true;
                            currentY--;
                            stuckCounter = 0;
                        }
                        else
                        {
                            placeNumber = false;
                            stuckCounter++;
                        }
                        break;
                }

                // Is Snake stuck? If so, rotate 90 degs right
                if (stuckCounter == 1)
                {
                    switch (currentDirection)
                    {
                        case Direction.Right:
                            currentDirection = Direction.Down;
                            break;
                        case Direction.Down:
                            currentDirection = Direction.Left;
                            break;
                        case Direction.Left:
                            currentDirection = Direction.Up;
                            break;
                        case Direction.Up:
                            currentDirection = Direction.Right;
                            break;
                    }
                }
                else if (stuckCounter > 1)
                {
                    totallyStuck = true;
                }
            }

            // Draw final maze
            for (int y = 0; y < boundY; y++)
            {
                for (int x = 0; x < boundX; x++)
                {
                    Console.Write(string.Format("{0:00} ",maze[y, x]));
                }
                Console.Write("\r\n");
            }
        }
    }
}

OK, I'm just posting this answer for fun.

The other solutions use variables to accumulate information iteratively. I wanted to try a functional solution, where the number of any table cell (or alternatively, the table cell for any number) could be known without iterating through any others.

Here it is in javascript. I know, it's not pure functional programming, nor is it extremely elegant, but the computation of the number for each table cell is done without reference to prior iterations. So it's multi-core friendly.

Now we just need somebody to do it in haskell. ;-)

BTW this was written before the comment that the 1 should end up in a certain location that is not necessarily the northwest corner (still unspecified as of now).

Since somebody mentioned the Ulam spiral, just for kicks I added code to put a red border around the primes (even though the spiral is inside out). Interestingly enough, there do seem to be diagonal streaks of primes, though I don't know if it's significantly different from the streaks you'd get with random odd numbers.

The code:

// http://stackoverflow.com/questions/3584557/logical-problem

/* Return a square array initialized to the numbers 1...n2, arranged in a spiral */
function spiralArray(n2) {
   var n = Math.round(Math.sqrt(n2));
   if (n * n != n2) {
      alert('' + n2 + ' is not a square.');
      return 0;
   }
   var h = n / 2;
   var arr = new Array(n);
   var i, j;

   for (i = 0; i < n; i++) {
      arr[i] = new Array(n);
      for (j = 0; j < n; j++) {
         // upper rows and lower rows of spiral already completed
         var ur = Math.min(i, n - i, j + 1, n - j, h),
            lr = Math.min(i, n - i - 1, j + 1, n - j - 1, h);
         // count of cells in completed rows
         // n + n-2 + n-4 ... n - 2*(ur-1) = ur*n - (ur*2*(ur - 1)/2) = ur * (n - ur + 1)
         // n-1 + n-3 + ... n-1 - 2*(lr-1) = lr*(n-1) - (lr*2*(lr - 1)/2) = lr * (n - 1 - lr + 1)
         var compr = ur * (n - ur + 1) + lr * (n - lr);
         // e.g. ur = 2, cr = 2*(5 - 2 + 1) = 2*4 = 8
         // left columns and right columns of spiral already completed
         var rc = Math.min(n - j - 1, i, n - i, j + 1, h),
            lc = Math.min(n - j - 1, i, n - i - 1, j, h);
         // count of cells in completed columns
         var compc = rc * (n - rc) + lc * (n - lc - 1);
         // offset along current row/column
         var offset;
         // Which direction are we going?
         if (ur > rc) {
            // going south
            offset = i - (n - j) + 1;
         } else if (rc > lr) {
            // going west
            offset = i - j;
         } else if (lr > lc) {
            // going north
            offset = n - i - 1 - j;
         } else {
            // going east
            offset = j - i + 1;
         }

         arr[i][j] = compr + compc + offset;
      }
   }
   return arr;
}

function isPrime(n) {
    // no fancy sieve... we're not going to be testing large primes.
    var lim = Math.floor(Math.sqrt(n));
    var i;
    if (n == 2) return true;
    else if (n == 1 || n % 2 == 0) return false;
    for (i = 3; i <= lim; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

// display the given array as a table, with fancy background shading
function writeArray(arr, tableId, m, n) {
   var tableElt = document.getElementById(tableId);
   var s = '<table align="right">';
   var scale = 1 / (m * n);
   var i, j;
   for (i = 0; i < m; i++) {
      s += '<tr>';
      for (j = 0; j < n; j++) {
         var border = isPrime(arr[i][j]) ? "border: solid red 1px;" : "";
         s += '<td style="' + border + '" >' + arr[i][j] + '</td>';
      }
      s += '</tr>';
   }
   s += '</table>';

   tableElt.innerHTML = s;
}

function tryIt(tableId) {
   var sizeElt = document.getElementById('size');
   var size = parseInt(sizeElt.value);
   writeArray(spiralArray(size * size), 'spiral', size, size);
}

The HTML page to exercise it:

<html>
    <head>
        <style type="text/css">
        td {
            text-align: right;
            font-weight: bold;
        }
        </style>
        <script type="text/javascript" src="so3584557.js" ></script>
    </head>
    <body>
        <form action="javascript:tryIt('spiral')">
            Size of spiral: <input type='text' id='size' />
        </form>
        <table id="spiral">
        </table>
    </body>
</html>

in java

   public static void main(final String args[]) {
      int numbercnt = 16;
      int dim = (int) Math.sqrt(numbercnt);
      int[][] numbers = new int[dim][dim];
      ArrayList < Integer > ref = new ArrayList < Integer >();
      for (int i = 0; i < numbercnt; i++) {
         ref.add(i);
      }
      for (int i = 0; i < numbers.length; i++) {
         for (int j = 0; j < numbers[i].length; j++) {
            int pos = (int) (Math.random() * ref.size());
            numbers[j][i] = ref.get(pos);
            ref.remove(pos);
         }
      }
      for (int i = 0; i < numbers.length; i++) {
         for (int j = 0; j < numbers[i].length; j++) {
            System.out.print(numbers[j][i] + " ");
         }
         System.out.println();
      }
   }

In PHP, but with recursion. You can set the size of the square box to be filled by specifying the length of a side.

The way this works is that the function initially fills in the value at the array location specified. Then it tries to keep moving in the direction it was moving. If it can't, it turns clockwise 90 degrees. If there are no moves left, it stops. This is handled with a switch() statement for the direction variable and recursion.

This can be adapted to rectangular shaped grids quite easily (just specify 2 constants instead of 1 for the side lengths).

Live Example with an 8x8 and your 4x4

The code:

<?php

  // Size of edge of matrix
define("SIZE", 4);

  // Create empty array
$array = array();

  // Fill array with a spiral.
fillerUp($array);

// Start at 0 / 0  and recurse
function fillerUp(& $array, $x = 0, $y = 0, $count = 1, $direction = "right")
{
      // Insert value
    $array[$x][$y] = $count;

      // Try to insert next value. Stop if matrix is full.
    switch ($direction)
    {

    case "right":        
        if (! $array[($x + 1) % SIZE][$y])
            fillerUp($array, $x + 1, $y, ++$count, "right");
        elseif (! $array[$x][($y + 1) % SIZE])
            fillerUp($array, $x, $y + 1, ++$count, "down");        
        break;

    case "down":  
        if (! $array[$x][($y + 1) % SIZE])
            fillerUp($array, $x, $y + 1, ++$count, "down");
        elseif (! $array[($x - 1) % SIZE][$y])
            fillerUp($array, $x - 1, $y, ++$count, "left");        
        break; 

    case "left":   
        if (! $array[abs(($x - 1) % SIZE)][$y])
            fillerUp($array, $x - 1, $y, ++$count, "left");
        elseif (! $array[$x][abs(($y - 1) % SIZE)])
            fillerUp($array, $x, $y - 1, ++$count, "up");        
        break;

    case "up":                   
        if (! $array[$x][abs(($y - 1) % SIZE)])
            fillerUp($array, $x, $y - 1, ++$count, "up");        
        elseif (! $array[($x + 1) % SIZE][$y])
            fillerUp($array, $x + 1, $y, ++$count, "right");            
        break; 

    }
}

// Show answer.
echo "<pre>";
for ($y = 0; $y < SIZE; ++$y)
{
    for ($x = 0; $x < SIZE; ++$x)    
    {
        echo str_pad($array[$x][$y], 4, " ", STR_PAD_BOTH);
    }
    echo "\n";
}
echo "</pre>";
?>