Writing a string in a spiral
I had recently participated in coding competion sponsored by an company and there was this one question which I did not understood, as to what was it asking.
Here is the question:
The string "paypal is the faster, safer way to send money" is written in a clockwise spiral pattern inside a square starting from the upper left corner: (you may want to display this pattern in a fixed font for better legibility).
P A Y P A L
F E R W A I
A M O N Y S
S D Y E T T
R N E S O H
E T S A F E
Then read line after line: PAYPALFERWAIAMONYSSDYETTRNESOHETSAFE
Write the code that will take a string, calculate the minimum square that will contain it and return the converted string:
String convert(String text);
example:
convert("paypalisthefastersaferwaytosendmoney")
should return "paypalferwaiamonyssdyettrnesohetsafe"
Do you understand as to how we can app开发者_JAVA技巧roach this problem?
I believe that the question, as written, is meant to be interpreted as follows:
You are given a string and want to write that string as a spiral into a square grid. Write a function that finds the smallest square that can hold the string, writes the string into the grid by spiraling its characters around the grid clockwise, and finally concatenates the rows together.
As an example, the string "In a spiral" would look like this:
I N A
In a spiral -> A L S -> INAALSRIP
R I P
To see where the grid comes from, note that if you read it like this:
I -> N -> A
|
v
A -> L S
^ |
| v
R <- I <- P
You get back the initial text, and if you glue the rows "INA", "ALS," and "RIP" into a single string you get back "INAALSRIP."
Let's consider each problem separately. First, to see the smallest size of a rectangle that can hold the text, you're essentially looking for the smallest perfect square at least as large as the length of your text. To find this, you could take the square root of the length of your string and round it up to the nearest integer. That gives you the dimension you'd like. However, before you can do that, you need to strip out all of the punctuation and space characters from the string (and perhaps the numbers as well, depending on the application). You could do this by walking across the string and copying over the characters that are indeed alphabetic into a new buffer. In what follows, I'll assume that you've done this.
As for how to actually fill in the grid, there's a really great way to do this. The intuition is as follows. When you start off in an n x n grid, your only boundaries are the walls of the grid. Every time you march across the grid dropping letters and hit a wall, you've just shaved off a row or a column from the matrix. Consequently, your algorithm could work by keeping track of the first and last legal column and the first and last legal row. You then walk across the top row from left to right writing characters. When you're done, you then increment the first legal row, since you can't put anything there any more. Then, walk down the right side until you hit the bottom. Once you're done, you would then block off the last column from consideration as well. For example, to look back at our "In a spiral" example, we start off with an empty 3x3 grid:
. . .
. . .
. . .
After we write the first three characters across the top, we're left with this:
I N A
. . .
. . .
Now, we need to write the rest of the string into the blank space, starting from the upper-right square and moving down. Because we can't ever write back into the top row, one way of thinking about this is to think about solving the problem of writing the rest of the characters in a spiral in the smaller space
. . .
. . .
Starting from the upper-left corner and moving downward.
To actually realize this as an algorithm, we need to keep track of a few things at each point. First, we need to store the bounds of the world as we're updating them. We also need to store our current write location, along with what direction we're facing. In pseudocode, this is represented as follows:
firstRow = 0, lastRow = N - 1 // Bounds of the grid
firstCol = 0, lastCol = N - 1
dRow = 0 // Amount to move in the Y direction
dCol = 1 // Amount to move in the X direction
row = 0 // Current position
col = 0
for each character ch in the string:
Write character ch to position (row, col).
// See if we're blocked and need to turn.
If (row + dRow, col + dCol) is not contained in the rectangle [firstRow, lastRow] x [firstCol, lastCol]:
// Based on which way we are currently facing, adjust the bounds of the world.
If moving left, increment firstRow
If moving down, decrement lastCol
If moving right, decrement lastRow
If moving up, increment firstCol
Rotate 90 degrees
// Finally, move forward a step.
row += dRow
col += dCol
You can implement the ninety-degree turn using a trick from linear algebra: to rotate a vector 90 degrees to the left, you multiply it by the rotation matrix
| 0 1 |
| -1 0 |
So your new dy and dx are given by
|dCol'| = | 0 1 | dCol = |-dRow|
|dRow'| | -1 0 | dRow | dCol|
So you can turn left by computing
temp = dCol;
dCol = -dRow;
dRow = temp;
Alternatively, if you know for a fact that the character with numeric value zero never appears in the string, you can use the fact that Java initializes all arrays to hold zeros everywhere. You can then treat 0 as a sentinel meaning "it's safe to keep moving forward." That version of the (pseudo)code would look like this:
dRow = 0 // Amount to move in the X direction
dCol = 1 // Amount to move in the Y direction
row = 0 // Current position
col = 0
for each character ch in the string:
Write character ch to position (row, col).
If (row + dRow, col + dCol) is not contained in the rectangle [0, 0] x [n-1, n-1]
-or-
The character at [row + dRow, col + dCol] is not zero:
Rotate 90 degrees
// Move forward a step
row += dRow
col += dCol
Finally, once you've written the string into the spiral, you can convert that spiraled text back into a string by walking across the rows one at a time and concatenating together all of the characters that you find.
EDIT: As @Voo points out, you can simplify the last step of this algorithm by not actually creating a multidimensional array at all and instead encoding the multidimensional array as a single-dimensional array. This is a common (and clever!) trick. Suppose, for example, that we have a grid like this:
0 1 2
3 4 5
6 7 8
Then we can represent this using a one-dimensional array as
0 1 2 3 4 5 6 7 8
The idea is that given an (row, col) pair in an N x N grid, we can convert that coordinate to a corresponding location in the linearized array by looking at position row * N + col. Intuitively, this says that every step in the y direction that you take is equivalent to skipping all N elements of one row, and each horizontal step just moves one step horizontally in the linearized representation.
Hope this helps!
I wrote an implementation in Python, which I think, shows a workmanlike approach. Although you tagged your question Java, sometimes I think it's wise to prototype and learn about problems, especially "interview questions" in a very high level dynamic language. The language itself is like pseudo-code that runs, and this helps you understand the shape of the problem, or the shape of the question.
The clues are there in the way the person has asked the question:
- There is a nice box like shape of letters. A good place to start is to ask yourself, how do I write code that makes a box of letters.
- What data structure (array with an x+(y*c) lookup or, 2d array) will I store the box of letters in.
- How do I put them in and how do I get them out?
From the point where you break it down into smaller pieces, you should be able to understand the question, and then begin to formulate an answer.
It could probably be done in many fewer lines of code but I felt like doing it as linearly as possible. Here's a not-very-good-at-python answer:
from math import *
import pprint
directions = [ (0,1),(1,0),(0,-1),(-1,0) ]
def store_spiral(array,s,l):
direction = 0
dx = directions[direction][0]
dy = directions[direction][1]
x=0
y=0
for c in s:
array[x][y] = c
x = x +dx
y = y +dy
if (x >= l) or (y >= l) or (x<0) or (y<0):
x=x-dx
y=y-dy
direction = (direction + 1) % 4
dx = directions[direction][0]
dy = directions[direction][1]
x=x+dx
y=y+dy
elif (array[x][y]!=''):
x=x-dx
y=y-dy
direction = (direction + 1) % 4
dx = directions[direction][0]
dy = directions[direction][1]
x=x+dx
y=y+dy
def convert(s):
l = len(s)
sl = int(ceil(sqrt(l)))
# make empty 2d array of [ ['','', ... ], .... ]
ar2 = [['' for i in range(sl)] for j in range(sl)]
store_spiral(ar2,s,sl)
x=''
for ar in ar2:
for l in ar:
x=x+l
return x
a = convert("paypalisthefastersaferwaytosendmoney")
print a
And here's an idea how to make a cooler version, but it would require generating the series of values called 'limits' here, which is the "length of a walk before you turn".
from math import *
import pprint
# directions = East,South,West,North
directions = [ (0,1),(1,0),(0,-1),(-1,0) ]
x=0
y=-1
def store_spiral(array,s,l):
global x
global y
direction = 0
dx = directions[direction][0]
dy = directions[direction][1]
d=0
n=0
limits=[5,4,4,3,3,2,2,1,1,1,1]
limit=limits[n]
for c in s:
d=d+1
x=x+dx
y=y+dy
array[y+(x*l)]=c
if d>limit and (limit>0):
direction = (direction + 1) % 4
dx = directions[direction][0]
dy = directions[direction][1]
n=n+1
if n>=len(limits):
break
limit=limits[n]
d=0
def convert(s):
l = len(s)
sl = int(ceil(sqrt(l)))
# make empty 2d array of [ ['','', ... ], .... ]
ar = ['*' for i in range(l)]
#try:
store_spiral(ar,s,sl)
#except:
# pass
x=''
n=0
for l in ar:
x=x+l
print l,
n=n+1
if n==sl:
n=0
print
return x
a = convert("paypalisthefastersaferwaytosendmoney")
print
print 'result: ',a
Size of side of square is square root of square, where square is a length in first place.
Answer:
- Take length as an integer number
- Find square root of length as float number, i.e. root
- Check if fractional part of root is non-zero
- If there is non-zero in fractional part of root, add 1 to integer part of root, else add 0
- The result is an integer number
- This number is an answer how big is each side of your square
- Instantiate an empty square, sized as calculated
- Fill the square by visiting every slot "spirally" starting from top left corner
- Assert that nothing left in source string after vistiting is complete
- Assert that remaining unfilled part of square is less that (2x side size - 1)
- Revisit the square in left-to-right, top-to-down order to reconstruct the output
- Assert that length of output is equal to length of input
- Done
As I understand:
You have
ABCHIDGFE
You convert it to square (if possible)
A B C
H I D
G F E
And then make string going clockwise
A B C D E F G H I
And return this string
I'm not sure what to do if it's impossible to make square of it.
This is what I understand of the question.
Lets say we have the string "hello world this was the first script I ever programmed how are you today good"
This string has 64 characters.
Now if you look at the string you gave, it has 36 characters, of which the square root is 6, hence 6 letters on each side.
So the string above has 64 characters of which the square root is: 8
which means the minimum square would need to be 8 letters on each side.
This answer deals with the process behind the 'calculate the minimum size square' requirement.
//in c++
string convert(const string & s) { int len = s.size();
//base case
if (len == 0) return string("");
// minimum square calculation
int i = 1;
while (i*i < len) ++i;
//cout << "i=" << i << endl;
//matrix initialization
vector<vector<char> > matrix;
matrix.resize(i);
for (int j = 0; j < i; ++j)
matrix[j].resize(i);
for (int j = 0; j < i; ++j)
for (int k = 0; k < i; ++k)
matrix[j][k] = ' ';
//logic
int r = 0, c = 0;
bool right = true, down = false, left = false, up = false;
int curr_len = 0;
int side = i - 1;
while (curr_len < len)
{
if (right)
{
for (int j = 1; (j <= side) && ((curr_len+j) <= len); ++j)
{
matrix[r][c] = s[curr_len];
//cout << curr_len << "|" << r << "|" << c << "|" << matrix[r][c] << "\n";
++c;
++curr_len;
}
right = false;
down = true;
}
if (down)
{
for (int j = 1; (j <= side) && ((curr_len+j) <= len); ++j)
{
matrix[r][c] = s[curr_len];
//cout << curr_len << "|" << r << "|" << c << "|" << matrix[r][c] << "\n";
++r;
++curr_len;
}
down = false;
left = true;
}
if (left)
{
for (int j = 1; (j <= side) && ((curr_len+j) <= len); ++j)
{
matrix[r][c] = s[curr_len];
//cout << curr_len << "|" << r << "|" << c << "|" << matrix[r][c] << "\n";
--c;
++curr_len;
}
left = false;
up = true;
}
if (up)
{
for (int j = 1; (j <= side) && ((curr_len+j) <= len); ++j)
{
matrix[r][c] = s[curr_len];
//cout << curr_len << "|" << r << "|" << c << "|" << matrix[r][c] << "\n";
--r;
++curr_len;
}
up = false;
right = true;
side = side - 2;
++r; ++c;
}
}
stringstream ss;
for (int j = 0; j < i; ++j)
{
for (int k = 0; k < i; ++k)
{
ss << matrix[j][k];
}
}
return ss.str();
}
People are using lots of nested loops and if statements in their solutions above. Personally, i find it cleaner to think of how to do this in terms of:
direction
current input position
current row
current column
num rows to fill
num cols to fill
Fill right row 0 from column 0 to column 5.
Fill down column 5 from row 1 to row 4.
Fill left row 5 from column 4 to column 0
Fill up column 0 from row 4 to row 1
etc...
It's a classic recursive solution that could even be modified for a fork-join pool if you really wanted to. This particular solution actually adjusts the output grid size according to the input, so it's possible you might get a 5 rows x 6 cols if you trim enough chars off the input (though you could always leave the row trimming out and just produce a square with lots of blanks).
public static void placeright(char output[][], char input[], int position, int row, int col, int numrows, int numcols) {
for (int i=0;i<numcols && position < input.length;i++) {
output[row][col+i] = input[position++];
}
if (position < input.length){
placedown(output, input, position, row+1, col+numcols-1, numrows-1, numcols);
}
}
public static void placedown(char output[][], char input[], int position, int row, int col, int numrows, int numcols) {
for (int i=0;i<numrows && position < input.length;i++) {
output[row+i][col] = input[position++];
}
if (position < input.length){
placeleft(output, input, position, row+numrows-1, col-1, numrows, numcols-1);
}
}
public static void placeleft(char output[][], char input[], int position, int row, int col, int numrows, int numcols) {
for (int i=0;i<numcols && position < input.length;i++) {
output[row][col-i] = input[position++];
}
if (position < input.length){
placeup(output, input, position, row-1, col-numcols+1, numrows-1, numcols);
}
}
public static void placeup(char output[][], char input[], int position, int row, int col, int numrows, int numcols) {
for (int i=0;i<numrows && position < input.length;i++) {
output[row-i][col] = input[position++];
}
if (position < input.length){
placeright(output, input, position, row-numrows+1, col+1, numrows, numcols-1);
}
}
public static void main( String[] args )
{
String input = "paypalisthefastersaferwaytosendmoney".toUpperCase();
char chars[] = input.toCharArray();
int sqrtceil = (int) Math.ceil(Math.sqrt(chars.length));
int rows = sqrtceil;
int cols = sqrtceil;
while (cols*(rows-1) >= chars.length) {
rows--;
}
char output[][] = new char[rows][cols];
placeright(output, chars, 0, 0, 0, rows, cols);
for (int i=0;i<output.length;i++) {
for (int j=0;j<output[i].length;j++) {
System.out.print(output[i][j] + " ");
}
System.out.println();
}
}
Try this
package com.misc;
public class SprintSpiral {
public static void main(String[] args){
int xStart = 0;
int xEnd = 3;
int yStart = 0;
int yEnd = 3;
int[][] arr = new int[4][4];
arr[0][0]=1;
arr[1][0]=2;
arr[2][0]=3;
arr[3][0]=4;
arr[0][1]=5;
arr[1][1]=6;
arr[2][1]=7;
arr[3][1]=8;
arr[0][2]=9;
arr[1][2]=10;
arr[2][2]=11;
arr[3][2]=14;
arr[0][3]=15;
arr[1][3]=16;
arr[2][3]=17;
arr[3][3]=18;
for (int i = 0; i < 16; i++) {
for (int j = xStart; j <= xEnd; j++) {
System.out.println(arr[j][yStart]);
}
++yStart;
for (int j = yStart; j <= yEnd; j++) {
System.out.println(arr[xEnd][j]);
}
xEnd--;
for (int j = xEnd; j >= xStart; j--) {
System.out.println(arr[j][yEnd]);
}
yEnd--;
for (int j = yEnd; j >= yStart; j--) {
System.out.println(arr[xStart][j]);
}
xStart++;
}
}
}
First you fill a 6x6 matrix with point characters.Then you set direction to 1.Then you change direction each time the next character in the direction is not a point character.
public class Spiral {
static String phrase="paypalisthefastersaferwaytosendmoney";
static int deltax,deltay,direction;
public static void setDelta(){
if(direction==1){
deltax=1;
deltay=0;
}else if(direction==2){
deltax=0;
deltay=1;
}else if(direction==3){
deltax=-1;
deltay=0;
}else if(direction==4){
deltax=0;
deltay=-1;
}
}
public static void main(String[] args) {
int index=0,x,y,N=6;
char[][] MATRIX=new char[N][N];
for(y=0;y<N;y++){
for(x=0;x<N;x++) MATRIX[y][x]='.';
}
direction=1;
setDelta();
x=0;
y=0;
while(index<phrase.length()){
while(x<N && x>=0 && y<N && y>=0){
MATRIX[y][x]=phrase.charAt(index);
System.out.print(MATRIX[y][x]);
index++;
if(direction==1 && MATRIX[y][x+1]!='.' || x+1==N-1) break;
if(direction==2 && MATRIX[y+1][x]!='.' && y<N-2) break;
if(direction==3 && MATRIX[y][x-1]!='.' || x==0) break;
if(direction==4 && MATRIX[y-1][x]!='.' && y>=0) break;
x+=deltax;
y+=deltay;
}
if(direction==4) direction=1;
else direction++;
setDelta();
x+=deltax;
y+=deltay;
}
}
}
Calculating the minimum square is quite easy. you can just check the no of characters in input string and the minimum square size n*n.
1*1= 1
2*2 = 4
3*3 = 9
so you can easily find the n by putting in formula
n*n >= length(input string).
Looks like PAYPALISTHEFASTERSAFERWAYTOSENDMONEY is the input and
P A Y P A L
F E R W A I
A M O N Y S
S D Y E T T
R N E S O H
E T S A F E
is the output to me..
Even though the question was not clearly stating to provide an algorithm initially. Here is pseudo code for the recursive solution:
convert(input):
spiral(out[][],input,0,0,sqrt(input.len))
return out.toString()
spiral(out[][],input,ix,iy,size)
if size>0
//calculate the frame coords with starting indices ix,iy & size of the frame
place first 4*(size-1) chars on a frame on the ´out´ matrix
//recursive call to create inner frame
spiral(out,input.remainingString(),ix+1,iy+1,size-2)
else return
and implementation in java:
public class PayPal {
private enum Dir {
RIGHT, DOWN, LEFT, UP;
}
public String convert(String input) {
double dRoot = Math.sqrt(input.length());
int root;
if (Double.compare(dRoot, (int) dRoot) == 0) {
root = (int) dRoot;
} else {
root = (int) dRoot + 1;
}
char[][] out = new char[root][root];
spiral(out, 0, 0, root, input);
StringBuilder sb = new StringBuilder();
for (char[] line : out) {
sb.append(line);
}
return sb.toString();
}
private void spiral(char[][] out, int i, int j, int size, String input) {
Dir direction = Dir.RIGHT;
if (size > 0) {
if (size == 1) {
out[i][j] = input.charAt(0);
} else {
for (int k = 0; k < 4 * (size - 1); k++) {
int di = (k != 0 && k % (size - 1) == 0 ? size - 1 : k % (size - 1));
switch (direction) {
case RIGHT:
out[i][j + di] = input.charAt(k);
break;
case DOWN:
out[i + di][j + size - 1] = input.charAt(k);
break;
case LEFT:
out[i + size - 1][j + size - 1 - di] = input.charAt(k);
break;
case UP:
out[i + size - 1 - di][j] = input.charAt(k);
break;
}
if (k != 0 && (k % (size - 1) == 0)) //Change direction
{
direction = Dir.values()[direction.ordinal() + 1];
}
}
}
spiral(out, i + 1, j + 1, size - 2, input.substring(4 * (size - 1)));
} else {
return;
}
}
}
加载中,请稍侯......
精彩评论