# IsIsogram() - I thought I'd made a more efficient version

Made my IsIsogram function using an array containing a number for each letter in the alphabet that I use to track the sum of each letter in a word, then just check if the max element of the array is > 1.
Meaning I only need to loop through the word once.

``````bool UBullCowCartridge::IsIsogram(const FString Word)
{
// Initialise alphabet array
//                         a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
int32 LetterCounts[26] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

// Loop through word adding occurences of letter to alphabet array
for (int32 i = 0; i < Word.Len(); i++)
{
char Letter = Word.ToLower()[i];
++LetterCounts[Letter - 'a'];
}

// Check if maximum value in alphabet array if greater than 1
if (*std::max_element(LetterCounts, LetterCounts + 26) > 1)
{
return false;
}

return true;
}
``````

Edit:
Iām aware this will fail if something other than a plain letter is passed to the function so Iām adding further input validation elsewhere in the program

Not bad but thereās a couple of improvements that could be made.

``````char Letter = Word.ToLower()[i];
``````

Here you are making the whole word lower and then discarding that each loop. You could instead use

``````Word.ToLowerInline()
``````

At the start of the function to make the whole word lower case once.

``````if (*std::max_element(LetterCounts, LetterCounts + 26) > 1) { return false; }
``````

This is looping the array when it could have just checked when the increment happened and returned without needing to go through the whole word first and then looped again.

Also Unreal has itās own implementations of the standard algorithms e.g.
https://docs.unrealengine.com/en-US/API/Runtime/Core/Algo/Algo__MaxElement/1/index.html

``````if (Algo::MaxElement(LetterCounts) > 1)
``````

And hereās a benchmark of 4 different solutions

``````Run on (16 X 3600 MHz CPU s)
CPU Caches:
L1 Data 32K (x8)
L1 Instruction 32K (x8)
L2 Unified 524K (x8)
L3 Unified 16777K (x2)
----------------------------------------------------------------
Benchmark                      Time             CPU   Iterations
----------------------------------------------------------------
NestedLoop/alphabet         1604 ns         1611 ns       407273
AdjacentFind/alphabet        144 ns          144 ns      4977778
Array1/alphabet             3774 ns         3749 ns       179200
Array2/alphabet              154 ns          153 ns      4480000

NestedLoop/planet           66.5 ns         66.3 ns      8960000
AdjacentFind/planet         28.4 ns         28.3 ns     24888889
Array1/planet                354 ns          353 ns      1947826
Array2/planet               35.8 ns         36.0 ns     18666667

NestedLoop/bob              10.1 ns         10.0 ns     64000000
AdjacentFind/bob            8.69 ns         8.72 ns     89600000
Array1/bob                   144 ns          144 ns      4977778
Array2/bob                  28.2 ns         27.8 ns     23578947
``````

NestedLoop is what is done in the course does
AdjacentFind sorts and then finds if any adjacent pairs are the same letter
Array2 is with my fixes

(the alphabet test is for the actual alphabet not the word āalphabetā)

1 Like

``````bool UBullCowCartridge::IsIsogram(FString Word)
{
// Initialise alphabet array
//                         a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
int32 LetterCounts[26] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

Word.ToLowerInline();

// Loop through word adding occurences of letter to alphabet array
for (int32 i = 0; i < Word.Len(); i++)
{
char Letter = Word[i];
if (++LetterCounts[Letter - 'a'] > 1)
{
return false;
}
}

return true;
}
``````

No idea how I missed something as obvious as checking the incremented value instantly. but I wouldāve never spotted the fact that I was calling ToLower each loop, thank you!

Oh I forgot to mention that you can just use `= { 0 };` to initialise all the elements to `0`

1 Like

interesting. Are you going to teach us the AdjacentFind method.? It is deadly efficient.
How do I post codes here? Like this? Do I have to create a new topic?
This is my implementation of nested loop. I looked for an FString function to check that the string contains only alphabet but cannot find, however there is one for checking numeric string.
/[code]
bool UBullCowCartridge::IsIsogram(FString Guess)
{
int i{};
int j{};

``````for ( i = ( Guess.Len() - 1) ; i > 0; --i)
{
//PrintLine(TEXT("i is %i ,Guess[i] is %c "), i, Guess[i]);	//debug line
for (j = (i - 1) ; j >= 0; --j)
{
//PrintLine(TEXT("j is %i ,Guess[j] is %c "), j, Guess[j]);	//debug line
if (Guess[i] == Guess[j])
{
return false;
}
}
}
return true;
``````

}
/[code]

You can create a new topic for things like this, but make sure you use the right category (this would probably be in the UE4 -> Ask category)

You format a multi-line code block with 3 grave (also called back-tick) symbols (```) on the line above the first line of code, and three more after the last line of code. You can also use HTML notation
``` with a <code> tag ```

Also if you want to check if a string contains only letters you can loop through each char and use `isalpha()`

Well first some disclaimers. These are tested with standard C++ and not Unreal to easily benchmark with Google Benchmark, so the numbers arenāt accurate with Unreal but should give a good indication of how it should perform as the only difference should be with the uses of ToLower.

One thing I forgot to do in the last post was to convert all the other benchmarks to use the `ToLower` alternative I created for the string as the rest of the tests just did `tolower` in the loop to not need to convert every character if itās not needed. So with Unreal you can use `FChar::ToLower` which is the same thing as `tolower`.

So here is the updated version which uses `tolower` in the loop. (also with an addition test for a 9 letter isogram).

``````Run on (16 X 3600 MHz CPU s)
CPU Caches:
L1 Data 32K (x8)
L1 Instruction 32K (x8)
L2 Unified 524K (x8)
L3 Unified 16777K (x2)
-----------------------------------------------------------------
Benchmark                       Time             CPU   Iterations
-----------------------------------------------------------------
NestedLoop/alphabet          1571 ns         1569 ns       448000
AdjacentFind/alphabet         143 ns          143 ns      4480000
Array/alphabet               75.0 ns         75.0 ns      8960000

NestedLoop/numerical          154 ns          153 ns      4072727
AdjacentFind/numerical       43.7 ns         43.9 ns     16000000
Array/numerical              24.0 ns         24.1 ns     29866667

NestedLoop/planet            66.4 ns         67.0 ns     11200000
AdjacentFind/planet          28.6 ns         28.5 ns     23578947
Array/planet                 16.5 ns         16.5 ns     40727273

NestedLoop/bob               10.2 ns         10.3 ns     64000000
AdjacentFind/bob             8.73 ns         8.79 ns     74666667
Array/bob                    8.69 ns         8.58 ns     74666667
``````

The adjacent find method requires the string to be sorted first.

``````Algo::Sort(Word);
for (int32 i = 0, j = 1; j < Word.Len(); ++i, ++j)
{
if (FChar::ToLower(Word[i]) == FChar::ToLower(Word[j]))
{
return false;
}
return true;
``````

Although if youāre handling player input you will likely already be making sure everything is the same case to make it easier to work with.

Forget it Dan,
I forgot ā;ā in the header file. Hopefully everything will be ok.

Thanks.

Hi All,
Thought Iāll share with you my version here as I believe it is pretty efficient as well (only one loop and as soon as first duplicate is found function returns false):

``````bool UBullCowCartridge::IsIsogram(const FString& Input)
{
TMap<TCHAR, int32> temp;
for (auto &&cr : Input.ToLower())
{
if (!temp.Contains(cr))
{