Hi stackoverflow, I would like to know some solutions to such a problem.
It is given a number lets say 16 and you have to arange 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, (prefferably PHP);
+3
A:
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");
}
}
}
}
nonnb
2010-08-27 13:29:17
A pseudocode algorithm for that would be nice
fredley
2010-08-27 13:32:36
This can't work. If you start from the inside and work outward, you'll never hit an occupied square. If you start from the outside and work inside, you'll also never hit an occupied square. And if you start with an empty grid, you'll go in a straight line forever regardless.
meagar
2010-08-27 13:33:26
Unless you counted the number of numbers you had and build your grid based on that info.
Blair McMillan
2010-08-27 13:53:06
@meagar - o ye of little faith ;)
nonnb
2010-08-27 14:24:07
+7
A:
[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>';
?>
shamittomar
2010-08-27 13:36:15
+1 interesting use of $value as a vector describing current direction. A "virtual" -1 for uninformative variable names $value, $count
LarsH
2010-08-27 18:42:01
Peter Ajtai
2010-08-29 19:45:36
@christian, I don't think the OP was looking for a random arrangement of numbers, but a spiral.
LarsH
2010-08-27 14:29:10
+2
A:
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)
François
2010-08-27 13:49:40
+2
A:
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>
LarsH
2010-08-27 19:27:39
+1
A:
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>";
?>
Peter Ajtai
2010-08-27 21:25:59