This week's book giveaway is in the Servlets forum.
We're giving away four copies of Murach's Java Servlets and JSP and have Joel Murach on-line!
See this thread for details.
The moose likes Beginning Java and the fly likes determine least number of keypress Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "determine least number of keypress" Watch "determine least number of keypress" New topic
Author

determine least number of keypress

mat anungin
Greenhorn

Joined: Feb 27, 2008
Posts: 2
hi guys,

My brother brought home a test question that he wasnt able to answer. i tried to look at it and decided to try it for my practice but tweak the problem a bit. what i basically want to do is this: a user enters a word/s and the program computes the total number of moves one has to make using the arrow keys. but heres the kicker, you cant use the arrow keys so its basically just computing the least number moves you have to make. for example: "GPS"

* letter A is always the starting point
* no new lines or carriage return in the input string







to key in the word "GPS" the user would move DOWN 1 to select "G" then move RIGHT 3 and DOWN 1 to select "P", then move DOWN 1 and LEFT 3 to select "S". in total the least number of moves is 9 to form the word GPS.

there is no problem with that since G is at the top of the virtual keyboard, P is below G and S is below P so its ascending. and no problem for an array. but the thing is when you need to move back like for example "ECHO ROCK". if you count the least number of steps it total to 25 but when i do it in my program, its 33. i tried deducting some moves and it ended at 20 which is still off

here is my code to better understand:





btw, this is test was given to highschool kids. i feel really embarrassed not being able to solve it

any ideas?

thanks!

mat
Gavin Tranter
Ranch Hand

Joined: Jan 01, 2007
Posts: 333
Hi,
I would suggest that you should look at your problem and your code. Loops are the wrong way to do this.

Basicly you have 30 charactors that are of interest, and a 6 by 5 grid (6x6 with the final row not used (helps with the maths), as a clue, this is basicly vectors, each move between letters is a vector.

So if your grid co-ords start at 0 and you number each cell in the grid starting at 0. All you have to do is translate the charactor value to the cell value (a simple offset sum, with if statements for SPACE, -, . and ENT).

Then you can calculate the grid co-ord from the cell, then for each move/vector, its just a matter of calculating each component (x and y) of the vector, inverting any negative numbers and summing the compont, and adding this to your running total.

(There might be an ease way to add matrix's in Java but I dont know it)

For example A -> E equals 4. 4,0 - 0,0.

You will only have to do as many iterations as you have letters in the text?

Is this for a text entry system??

Gavin
Tim LeMaster
Ranch Hand

Joined: Aug 31, 2006
Posts: 226
I would go about this much differently - IE only one loop to loop through the characters of the incoming string - and create a data structure to get the position based on the character instead of looping through the keyboard each time.

However using your code - you need to calculate the distance (moves) from one key to the next, I'm not sure what the code is trying to do - however when moving from E to C.

tmp is 4 and x+y = 2
so the else runs and does
total = 4 - 4 - giving zero
total = 0 + 4 - (0 + 2) - giving two

So your algorithm gives 2 moves for the string "EC";

To me the critical bit is to create a formula that given two positions returns the moves required to move between them. Then you just do this for all keys versus the previous key (starting with 0,0 for the first calculation) and add up these values.
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
[mat]: a user enters a word/s and the program computes the total number of moves one has to make using the arrow keys. but heres the kicker, you cant use the arrow keys so its basically just computing the least number moves you have to make.

I'm not sure what the second sentence means here. It's the number of moves to make useing the arrow keys, except we can't use the arrow keys?

Ignoring that second sentence, everything else seems to make sense. I agree with Tim's comments about how best to go about this.


"I'm not back." - Bill Harding, Twister
mat anungin
Greenhorn

Joined: Feb 27, 2008
Posts: 2
hi guys!

thank you for your input, i came up with this:



it does what i want it to do.

@Gavin
yes its just a small exercise for myself. ideally, if you dont have a keyboard and you just have arrow keys to select letters you would use the arrow keys to navigate along the virtual keyboard. i wanted to find out the least number of arrow key moves required when typing something in the virtual keyboard. so yes, its sort of a text entry exercise.

when you said vectors, is it the same as map or hashmap? if i recall properly, vectors are like arrays but you can add and remove elements? is it the same as arraylist or is it more like hashmap or map?


Tim
we have the same thing in mind -guess? have a look at my revised code and see if thats what you meant


Jim
sorry for the confusion. its like this, you have a device with no physical keyboard and only arrow keys. the only visible keyboard is the on-screen keyboard and the way to navigate that on-screen keyboard is using the arrow keys. i just wanted to find out the least number of moves a user can make using the arrow keys to navigate the virtual keyboard
Gavin Tranter
Ranch Hand

Joined: Jan 01, 2007
Posts: 333
Hi Matt,
No, in this sense I meant the maths construct (vector), i.e. a value (such as velocity) that has direction and magnitude, as oppoise to a normal value (such as area) that has just magnitude and is a scalar value.
I would expect this to be a GCSE maths questions, so yes I would assume this is ok for high school. Do'nt know if kids learn programming at GCSE level here, so cant say if its a high school computing question.

However, in answer to your question Vectors are pretty much the same as ArraList, only Vectors are syncronised and thus considered thread safe. This increases their access time.

If we ignore the puntuation marks, this can be done without any data sturtures, and in fact you could probably do this using recursion so would not require any loops.
What I did was to convert the numerical value of the number to a cell value in the grid, and use that cell value to compute the co-ordinates then work out the vectors. Now you could just go stright from the numerical value of the number to the vectors, but that makes the maths look a lil untidy to my mind.

Here is my code:


Glad you found a solution.
Gavin

PS, the instance variable _gridSize represents the size of teh grid in the x axis, I think this is because we are moving in the X direction as we build our grid, so if we had two long columns rather then a square (ish) grid we would have a _gridSize of 2... I think.

[ March 03, 2008: Message edited by: Gavin Tranter ]

[ March 03, 2008: Message edited by: Gavin Tranter ]

[ March 03, 2008: Message edited by: Gavin Tranter ]
[ March 03, 2008: Message edited by: Gavin Tranter ]
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: determine least number of keypress
 
Similar Threads
Private variables inherited but not accessible
Knight's tour
|| operand
June Newsletter Puzzle
Inheritance