algorithm - Determine number of iteration need to get the string using character increment in PHP

View Original

I need to find the number of iterations need to reach the given string using character incrementing in php. I have code the below approach but it is a resource and time-consuming.

$x = 'a';
$num = 1;

while ($x != 'zzzz'){
    $x++;
    $num++;
    echo "$num: $x <br>";
}

above code starts lookup from character a and goes through all the way to zzzz, is somehow good for small string but it blasts the memory for long strings, is there any shorter way to calculate this?

Answer

Solution:

A simplified answer which reduces the amount of loops to 1 (comments in code)....

// String we want to find the value from
$end = 'ae';

// The list of all possible characters in the alphabet
$alphabet = range('a', 'e');
// Flip this array so that the letter becomes the key and the value is index (0 based)
$alphabetSearch = array_flip($alphabet);

$result = 0;
$endLen = strlen($end);
// Use the target string as an array an iterate over each char
for ($i = 0; $i < $endLen; $i++) {
    // Multiply the result by the number of chars in the alphaber to maintain the scale of each char
    $result *= count($alphabet);
    // Add on the index of the new char (+1 as it's 0 based)
    $result += ($alphabetSearch[$end[$i]] ?? 0) + 1;
}
echo $result;

Which in this example (ae with a,b,c,d,e as the alphabet) gives

Answer

Solution:

I have implemented this using PHP, the full description is included below but the basic idea is

find the position of every character of the string in the alphabet table.
power the 26 to the total number of characters(a-z) - 1.
multiply the step 2 result by the position of the character on the alphabet table.

code.

{-code-1}

Hi Guys, it might worth to mention it because this operation is needed in many programs and codes such as cryptography, brute force attacks, web scrapping, and many other operations, here is the idea behind the code.

using method characterLookupOnAlphabetByString we are finding the location of the alphabet character on the alphabet table for example A is the number 1st character on the alphabet table Z is 26th character on the alphabet table, the method return results in this form.

 [
  {
    "x": 24
  },
  {
    "b": 2
  },
  {
    "c": 3
  }
]

I have given the string xbc to the characterLookupOnAlphabetByString method and it returned the above array. until now we just find the position of each character of string in the alphabet table. let's go to the main operation

next, we are going to find the total iteration for the string characters. using findCharacterLevelFromString method. this method will receive a string and then pass it to the characterLookupOnAlphabetByString method and receive back the above array-like result, next will need to find the number of characters in the given array.

next, we do foreach loop on the returned array, next, since the index of number for every character is that character we do not know the character which is entered in the string we do another inner foreach loop for each character(please check the array structure), inside the inner loop we find the power of 26 (which is total number of alphabet character) on (total character - 1) then the result is going to multiply to the position of the character in alphabet table

Answer

Solution:

Just get the excel column index of each string and subtract them to get the distance.
For every new position in the string, the previous results will be multiplied by 26 and we will add the ordinal of the current character to get it's exact state value.

Snippet:

<?php

function getExcelColumnIndex($str){
    $columnIndex = 0;
    $len = strlen($str);
    
    for($i = 0; $i < $len; ++$i){
         $columnIndex *= 26;
         $columnIndex += ord($str[$i]) - ord('a') + 1;
    }
    
    return $columnIndex;
}

echo getExcelColumnIndex("zzzz") - getExcelColumnIndex("a");

Source