How to build a function that evaluates an integer as a LIFO collection in C#

Question

the problem is: write a function (AllExist), that receives as a parameter a non-empty stack stk (int), that will return true if all of the first digits of each number in the stack appear as a last digit in any of the numbers of stk, otherwise it will return false. for example: for stk (starting from the top going downwards) 122, 251, 565, 12334, 28, 7. the function will return true. 1 , 2 , 5 and 7 appear as last digits in any numbers in the stack.

** clone is a function that returns an identical stack to the given one.

my suggestion:

public static bool AllExist(stack<int> stk)
{
  int x=0; int i; int z; bool bl; string str;
  stack <int> stk1=clone (stk);
  while (!stk1.IsEmpty())
  {
    i=stk1.Pop();
    while(i>=10)
    i/=10;
    x=x*10+i;
  }
 str=x.ToString();
 stack<int> stk2=Clone(stk);
 while(!stk2.IsEmpty())
 {
   z=stk2.Pop()%10;
   if (str.IndexOf(z.ToString())>-1)
     bl=true;
   bl=false;
 }
return bl;
}

** this was all translates so sorry for any misunderstandings.

thank you!

Answer 1

When starting, always break the problem you are trying to solve into smaller problems and solve those. If you split it enough, the problems you really have to solve are practically one liners that can easily be verified as correct.

What do you need? First off a method that extracts the last digit of an integer. Ok, thats easy, the last digit of any number is the remainder of dividing by 10:

private static int ExtractLastDigit(this int i)
{
    return i % 10;
}

We also need a method that extracts the first digit. The easiest way to do this is to scale down the number so that the digit we are looking for is the only digit left. We can do this using Log10:

private static int ExtractFirstDigit(this int i)
{
    var scale = (int)Math.Log10(i);
    return (int)(i / Math.Pow(10, scale));
}

Now, there are tons of ways you can do this. The easiest to understand is to build two collections; one with all the first digits and another with the all the last digits an check if all the items in the former are present in the latter. Because you will be searching assiduously inside the latter, if the input collection is large enough, storing the last digits in a search efficient collection is, generally, a good idea. The framework provides such collection: HashSet<T>.

I will be using linq, but building the collections with classical loops is rather trivial.

var firstItems = inputStack.Select(i => i.ExtractFirstDigit());
var lastItems = new HashSet<int>(inputStack.Select(i => i.ExtractLastDigit()))

And now, with the logic operator All linq provides:

var validInput = firstItems.All(f => lastItems.Contains(f));

Which roughly translates to:

var validInput = true;

foreach (var first in firstItems)
{
    if (!lastItems.Contains(f))
    {
        validInput = false;
        break;
    }
}

And you are done.

Are there more efficient solutions? Sure, but do you really need them? If the answer is yes, get used to first building a working solution and then start trying to optimize it with clear performance goals you can measure and test. If you don't or it already meets your goals, then you have a working solution easy to understand and mantain.

Answer 2

You can solve this using LINQ, for example:

static void Main(string[] args)
{
     Console.WriteLine(AllExist(new Stack<int>(new List<int>() { 122, 251, 565, 12334, 28, 7 })));
}

public static bool AllExist(Stack<int> stk) => stk.All(
     firstDigitItem => stk.Where(
          lastDigitItem => lastDigitItem.ToString().Last() == firstDigitItem.ToString().First())
     .Count() > 0);
   

How it works:

• Using stk.All() you'll return true if all of the items in collection satisfy a condition.
• Then we select one item from collection - firstDigitItem and starting to compare first digit of this item with every other last digit item in collection. Using .ToString().First() or .ToString().Last()
• If more than 0 elements satisfy our condition - we continue to checking other items.
• Else: "Where" return false and "All" automatically returns false.

Or even more optimized way:

public static bool AllExist(Stack<int> stk) => stk.All(
     firstDigitItem => 
          stk.Any(lastDigitItem => lastDigitItem.ToString().Last() == firstDigitItem.ToString().First()));

Here, using "Any" we are looking for only first element, which satisfy our predicate, not all elements as "Where".