StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I found a solution by myself. </p> <p>Actually I'm checking only "qwerty" keyboards.</p> <p>The <code>getMaxPathLength</code> function gives the maximum path of adjacent keys searching in all the directions.</p> <pre><code><?php /* * Find the max path in a qwerty keyboard giving an input string Copyright (C) 2013 Danilo Rossini <rossinidan@gmail.com> This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>. USAGE: // Examples $array = array("qwertyui"); //get 8 as result $array = array("quedc"); //get 5 as result $array = array("qaz"); //get 3 as result $array = array("zxcdfvppp"); //get 6 as result $fp = new Path_length("qwertyu"); echo $fp->getMaxPathLength(); */ class Path_length{ private $maxPathLength = 1; /* * Keyboard layout: QUERTY */ private $matrix = array( array("1","2","3","4","5","6","7","8","9","0"), array("q","w","e","r","t","y","u","i","o","p"), array("a","s","d","f","g","h","j","k","l"), array("z","x","c","v","b","n","m"), ); private $colSize = 10; private $rowSize = 4; private $arrayInput = array(); private $arraySize = null; public function __construct($inputString) { if(!isset($inputString)) die("NULL input array!"); $this->splitStringInArray($inputString); $this->cycleMatrix(); } public function getMaxPathLength(){ return $this->maxPathLength; } /** * Split each element of the string into an array and store it, with his length * in global variables * @param type $string */ private function splitStringInArray($string){ $length = strlen($string); $tmpArray = array(); for ($i=0; $i<$length; $i++) { $tmpArray[$i] = $string[$i]; } $this->arraySize = $length; $this->arrayInput = $tmpArray; } /** * Iterate each element of the matrix, calling the function $this->findPath */ private function cycleMatrix(){ for($i=0;$i<$this->colSize;$i++){ for($j=0;$j<$this->rowSize;$j++){ if(isset($this->matrix[$j][$i]) && $this->arrayInput[0]==$this->matrix[$j][$i]){ $this->findPath($j, $i, $this->maxPathLength, 1); } } } } /** * Recursive function that search if the closest element in the matrix (up, down, left, right) * is contained in the input array at the cursor pointer. * It save into $this->maxPathLength the maximum length path found. * * @param int $a -> x position on the matrix * @param int $b -> y position on the matrix * @param int $max -> max path lenght found until now by the recursive call * @param int $c -> array cursor on the input array * @return int */ private function findPath($a, $b, $max, $c){ $this->maxPathLength = max(array($this->maxPathLength, $max)); if($a>=($this->rowSize-1) && $b>=($this->colSize-1)) { return 1; } if($c===$this->arraySize) { return 1; } /* Search next right key */ if(isset($this->matrix[$a+1][$b]) && $this->matrix[$a+1][$b]===$this->arrayInput[$c] && $this->findPath($a+1, $b, $max+1, $c+1)){ return 1; } /* Search next bottom key */ if(isset($this->matrix[$a][$b+1]) && $this->matrix[$a][$b+1]===$this->arrayInput[$c] && $this->findPath($a, $b+1, $max+1, $c+1)){ return 1; } /* Search next left key */ if(isset($this->matrix[$a-1][$b]) && $this->matrix[$a-1][$b]===$this->arrayInput[$c] && $this->findPath($a-1, $b, $max+1, $c+1)){ return 1; } /* Search next up key */ if(isset($this->matrix[$a][$b-1]) && $this->matrix[$a][$b-1]===$this->arrayInput[$c] && $this->findPath($a, $b-1, $max+1, $c+1)){ return 1; } return 0; } } </code></pre> <p><strong>Edit</strong></p> <p>New version of the previous code with detection of shifted keys.</p> <pre><code><?php /* * Find the max path in a qwerty keyboard giving an input string Copyright (C) 2013 Danilo Rossini <rossinidan@gmail.com> This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>. USAGE: // Examples $string = "qwertyui"; //get 8 as result $string = "qwedc"; //get 5 as result $fp = new Path_length("qwertyu"); echo $fp->getMaxPathLength(); */ class Path_length{ private $maxPathLength = 1; /* * Keyboard layout: QUERTY */ private $keyLower = array( array("1","2","3","4","5","6","7","8","9","0"), array("q","w","e","r","t","y","u","i","o","p"), array("a","s","d","f","g","h","j","k","l"), array("z","x","c","v","b","n","m"), ); private $keyUpper = array( array("1","2","3","4","5","6","7","8","9","0"), array("Q","W","E","R","T","Y","U","I","O","P"), array("A","S","D","F","G","H","J","K","L"), array("Z","X","C","V","B","N","M"), ); private $matrix = array(); private $colSize = 10; private $rowSize = 4; private $arrayInput = array(); private $arraySize = null; public function __construct($inputString) { if(!isset($inputString) || !is_string($inputString)) die("Invalid input string!"); $this->initKeyboard(); $this->splitStringInArray($inputString); $this->cycleMatrix(); } private function initKeyboard(){ $this->matrix[0] = $this->keyLower; $this->matrix[1] = $this->keyUpper; } public function getMaxPathLength(){ return $this->maxPathLength; } /** * Split each element of the string into an array and store it, with his length * in global variables * @param type $string */ private function splitStringInArray($string){ $length = strlen($string); $tmpArray = array(); for ($i=0; $i<$length; $i++) { $tmpArray[$i] = $string[$i]; } $this->arraySize = $length; $this->arrayInput = $tmpArray; } private function isUpper($chr){ return ctype_upper($chr) ? 1 : 0; } /** * Iterate each element of the matrix, calling the function $this->findPath */ private function cycleMatrix(){ for($i=0;$i<$this->colSize;$i++){ for($j=0;$j<$this->rowSize;$j++){ for($c=0; $c<$this->arraySize; $c++) { $isUp = $this->isUpper($this->arrayInput[$c]); if( isset($this->matrix[$isUp][$j][$i]) && $this->arrayInput[$c]===$this->matrix[$isUp][$j][$i]){ $this->findPath($j, $i, 1, $c+1, $isUp); } } } } } /** * Recursive function that search if the closest element in the matrix (up, down, left, right) * is contained in the input array at the cursor pointer. * It save into $this->maxPathLength the maximum length path found. * * @param int $a -> x position on the matrix * @param int $b -> y position on the matrix * @param int $max -> max path lenght found until now by the recursive call * @param int $c -> array cursor on the input array * @return int */ private function findPath($a, $b, $max, $c, $isUp){ $this->maxPathLength = max(array($this->maxPathLength, $max)); if($a>=($this->rowSize-1) && $b>=($this->colSize-1)) { return 1; } if($c===$this->arraySize) { return 1; } /* Search next right key */ if(isset($this->matrix[$isUp][$a+1][$b]) && $this->matrix[$isUp][$a+1][$b]===$this->arrayInput[$c] && $this->findPath($a+1, $b, $max+1, $c+1, $isUp)){ return 1; } /* Search next bottom key */ if(isset($this->matrix[$isUp][$a][$b+1]) && $this->matrix[$isUp][$a][$b+1]===$this->arrayInput[$c] && $this->findPath($a, $b+1, $max+1, $c+1, $isUp)){ return 1; } /* Search next left key */ if(isset($this->matrix[$isUp][$a-1][$b]) && $this->matrix[$isUp][$a-1][$b]===$this->arrayInput[$c] && $this->findPath($a-1, $b, $max+1, $c+1, $isUp)){ return 1; } /* Search next up key */ if(isset($this->matrix[$isUp][$a][$b-1]) && $this->matrix[$isUp][$a][$b-1]===$this->arrayInput[$c] && $this->findPath($a, $b-1, $max+1, $c+1, $isUp)){ return 1; } return 0; } } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload