How to calculate elements needed from a loop?

Question

I have the following data: y-n-y-y-n-n-n This repeats infinitely, such as: y-n-y-y-n-n-n-y-n-y-y-n-n-n-y-n-y-y-n-n-n...

I have 5 "x". "x" only sticks with "y". Meaning, if I distribute x on the loop above, it will be: y-n-y-y-n-n-n-y-n-y-y-n-n-n x---x-x-----x-x

I want to count how many of the loop's element I needed to use to spread 5 x across, and the answer is 10.

How do I calculate it with a formula?

Answer 1

I presume what you're saying is that you need to process the first 10 elements of the infinite list to get 5 Y's, which match/stick with the 5 X's you have.

y-n-y-y-n-n-n-y-n-y-y-n-n-n-y-n-y-y-n-n-n... 
x-_-x-x-_-_-_-x-_-x 
                  ^
                  L____ 10 elements read from the infinite list to place the 5 x's. 

I also presume that your question is: given an input of 5 Xs, what is the number of elements you need to process in the infinite list to match those 5 Xs.

You could calculate it with a loop like the following pseudo-code:

iElementsMatchedCounter = 0 
iXsMatchedCounter = 0 
iXLimit = 5 
strElement = "" 

if (InfiniteList.IsEmpty() == false) 
{ 
    do 
    { 
        strElement = InfiniteList.ReadNextElement()

        if (strElement == "y") 
        { 
            iXsMatchedCounter += 1 
        } 

        iElementsMatchedCounter += 1 

    } while ( (InfiniteList.IsEndReached() == false) AND (iXsMatchedCounter < iXLimit) ) 
} 

if (iXsMatchedCounter = iXLimit) 
    then Print(iElementsMatchedCounter) 
    else Print("End of list reached before all X's were matched!") 

The drawback of the above approach is that you are actually reading the infinite list, which might not be preferable.

Instead, given you know your list is an infinitely repeating sequence of the same elements y-n-y-y-n-n-n, you don't even need to loop through the entire list, but just operate on the sub-list y-n-y-y-n-n-n. The following algorithm describes how:

Given your starting input:

• iNumberOfXs = 5 (you have 5 Xs to match)
• iNumberOfYsInSubList = 3 (you have 3 Ys in the sub-list, the total list repeats infinitely)
• iLengthOfSubList = 7 (you have 7 elements in the sub-list y-n-y-y-n-n-n)

We then have intermediate results which are calculated:

• iQuotient
• iPartialLengthOfList
• iPendingXs
• iPendingLengthOfList
• iResult

The following steps should give the result:

1. Divide the iNumberOfXs by iNumberOfYsInSubList. Here, this gives us 5/3 = 1.666....
2. Discard the remainder of the result (the 0.666...), so you're left with 1 as iQuotient. This is the number of complete sub-lists you have to iterate.
3. Multiply this quotient 1 with iLengthOfSubList, giving you 1*7=7 as iPartialLengthOfList. This is the partial sum of the result, and is the number of elements in the complete sub-lists you iterate.
4. Also multiply the quotient with iNumberOfYsInSubList, and subtract this product from iNumberOfXs, i.e. iNumberOfXs - (iQuotient * iNumberOfYsInSubList) = 5 - (1 * 3) = 2. Save this value 2 as iPendingXs, which is the number of as-yet unmatched X's.
5. Note that iPendingXs will always be less than iLengthOfSubList (i.e. it is a modulo, iPendingXs = iNumberOfXs MODULO iNumberOfYsInSubList).
6. Now you have the trivial problem of matching 2 X's (i.e. the value of iPendingXs calculated above) in the sub-list of y-n-y-y-n-n-n.
7. The pending items to match (counted as iPendingLengthOfList) is:
   • Equal to iPendingXs if iPendingXs is 0 or 1
   • Equal to iPendingXs + 1 otherwise (i.e. if iPendingXs is greater than 1)
   • In this case, iPendingLengthOfList = 3, because iPendingXs is greater than 1.
8. The sum of iPartialLengthOfList (7) and iPendingLengthOfList (3) is the answer, namely 10.

In general, if your sub-list y-n-y-y-n-n-n is not pre-defined, then you cannot hard-code the rule in step 6, but will instead have to loop through only the sub-list once to count the Ys and elements, similar to the pseudo-code given above.

When it comes to actual code, you can use integer division and modulo arithmetic to quickly to the operations in steps 2 and 4 respectively.

iQuotient = iNumberOfXs / iNumberOfYsInSubList     // COMMENT: here integer division automatically drops the remainder 
iPartialLengthOfList = iQuotient * iLengthOfSubList 

iPendingXs = iNumberOfXs  - (iQuotient  * iNumberOfYsInSubList) 
// COMMENT: can use modulo arithmetic like the following to calculate iPendingXs 
// iPendingXs = iNumberOfXs % iNumberOfYsInSubList 

// The following IF statement assumes the sub-list to be y-n-y-y-n-n-n 
if (iPendingXs > 1) 
    then iPendingLengthOfList = iPendingXs + 1 
    else iPendingLengthOfList = iPendingXs 

iResult = iPartialLengthOfList + iPendingLengthOfList