Logical testing numbers

Discussion in 'Programmer's Corner' started by Sparky49, Feb 28, 2015.

  1. Sparky49

    Thread Starter Active Member

    Jul 16, 2011
    834
    417
    Hi all,

    I was wondering if you may be able to help me with determining if five numbers in a sequence are the same or not, using C. I've had a go, but it seems terribly long winded and was wondering if there may be another way to accomplish this.

    I have represent my numbers with ABCDE, if they are the same then appropriate label is given the value 1. Then by using logic, I have written down all combinations of ABCDE where three are the same. But this is a lot of combinations.

    Is there a simpler way to do this in C?

    Many thanks for your time,

    Sparky
     
  2. MikeML

    AAC Fanatic!

    Oct 2, 2009
    5,450
    1,066
    Your problem statement is confusing.

    Assume that n is any number, including A-E.
    When matching the incoming sequence to the target, does this sequence AnCnE match ABCDE?
    So there are 5*4 = 20 places where two ns can be substituted and still match?
    And there are 5 place where one n can be substituted and still match?
     
    Sparky49 likes this.
  3. Sparky49

    Thread Starter Active Member

    Jul 16, 2011
    834
    417
    Sorry for the confusing post.

    This is for a game, where five shapes are randomly generated. If three and only three are the same, then the idea is that a player will press their button to score a point.

    I am attempting to do this by generating five random numbers, which will each correspond to a shape. If three of the numbers are the same, then the program 'knows' that three shapes are the same. What I am trying to do is create a test to determine if three out of the five numbers are the same.

    I hope that is clearer, if not just say and I'll be quick to reply. :)

    Many thanks again, Sparky.
     
  4. MikeML

    AAC Fanatic!

    Oct 2, 2009
    5,450
    1,066
    You didn't answer the questions I asked in post #2.

    But I see that the random number generator can generate only five possible values.
     
  5. Sparky49

    Thread Starter Active Member

    Jul 16, 2011
    834
    417
    I am sorry Mike, but I'm finding the questions a little confusing. I am unsure why we would want to match a AnCnE with ABCDE? Wouldn't there just be a comparison with ABCDE itself?
    Using pseudo code:
    Code (Text):
    1. int pass;
    2. int A, B, C, D, E;
    3.  
    4. generate random int;
    5. put into A;
    6.  
    7. generate random int;
    8. put into B;
    9.  
    10. //and so on until random int in A B C D and E
    11.  
    12. if (only three out of A B C D E are the same)
    13. { pass=1}
    14.  
    15. else pass=0;
    Sparky
     
  6. GopherT

    AAC Fanatic!

    Nov 23, 2012
    6,043
    3,806
    @Sparky49
    Use arrays. Load all of your 5 numbers into numArray

    They will be accessible as numArray[0] to numArray[4]

    Use two more counter variables, arrayIndex and zeroCounter

    As psudo-code

    Code (Text):
    1.  
    2. Int ZeroCounter == 0 ; set to zero
    3.  
    4. For (int n=0, n < 4, n=n+1)
    5. {
    6.      Int  arrayIndex = n
    7.      {
    8.           For (arrayIndex, arrayIndex < 4, arrayIndex = arrayIndex+ 1)
    9.           {
    10.           If (numArray[arrayIndex] - numArray[arrayIndex + 1] == 0)
    11.                {ZeroCounter++
    12.                }
    13.       }
    14. }
    If zeroCounter is greater than 2, you passed.
     
    RamaD and Sparky49 like this.
  7. djsfantasi

    AAC Fanatic!

    Apr 11, 2010
    2,804
    833
    GopherT,

    I read the problem statement, in post #3, to mean if a randomly generated sequence, out of a set of five different values, has three and exactly three of the same number, then it is a match. For example 1,2,1,4,1 is a match, as is 1,2,,3,3,3 (or using letters as the OP did, ABADA OR ABCCC). I didn't see a requirement that the letters be sequential. The first examples I cited wouldn't get identified in your algorithm.
    Code (Text):
    1.  
    2. {
    3. void setup() {
    4.   // put your setup code here, to run once:
    5. Serial.begin(9600);
    6.  
    7. int numarray[5]={1,3,1,1,5};  // array of numbers
    8. int countarray[5]={0,0,0,0,0}; // array to count occurrences
    9. int value=-1; //specific value
    10. boolean Found=false; // self-explanatory
    11.  
    12.  
    13. // for each number, count the number of occurrences in the set
    14. for(value=0;value<5;value++) {
    15.     for (int arrayindex=0; arrayindex<5; arrayindex++) {
    16.     if (value == numarray[arrayindex]) {
    17.        countarray[value]++;
    18.        }
    19.     }
    20. }
    21. // look through the count of values for 3 occurrences.
    22. for(value=0;value<5;value++) {
    23. //  Serial.println(countarray[value]);
    24.     if (countarray[value]==3) {
    25.        Serial.println("Found");
    26.        Found=true;
    27.        break;
    28.        }
    29.     }
    30.  
    31. // display result
    32. if (Found) {
    33.   Serial.print ("Value=");
    34.   Serial.println(value);
    35.   }
    36.  
    37. }
    38.  
    39.  
    40. void loop() {
    41.   // put your main code here, to run repeatedly:
    42.  
    43. }
    44. }
    45.  
    46.  
    Edit: I see my code suffers from identifying four numbers as a match. I originally did my counting and testing in two separate loops, which didn't suffer from this problem. Mea culpa.
    Note: That issue has been fixed. This code has been compiled and tested on an Arduino.
     
    Last edited: Feb 28, 2015
    Sparky49 likes this.
  8. Sparky49

    Thread Starter Active Member

    Jul 16, 2011
    834
    417
    Thanks guys, djsfantasi especially.

    Makes sense to use arrays, rather than a bunch of logic - would make it easier to expand on if I wanted, say, six or ten shapes, or a different number to match.

    Many thanks again,

    Sparky
     
  9. GopherT

    AAC Fanatic!

    Nov 23, 2012
    6,043
    3,806
    If it is limited in that way, it was not my intention.
    The two For loops were to test, for the five numbers,
    A, B, C, D, E

    A TEST
    B, C, D, E (add 1 to ZeroCounter if any difference is zero (iE.they are equal)

    Then, B test
    C, D, E

    Then C test
    D, E

    Then D test
    E


    By that time, all combinations are tested and. None thing requires consecutive numbers be equal.
     
  10. darrough

    Member

    Jan 18, 2015
    86
    19
    Here is a small function you might experiment with. This is just something to experiment with. I don't know if it could be made to work or not.

    public static void main(String[] args) {

    System.out.println("\n1 integer");
    System.out.println(countUniqueIntegers(1));

    System.out.println("\n2 integers");
    System.out.println(countUniqueIntegers(1, 2));
    System.out.println(countUniqueIntegers(1, 1));

    System.out.println("\n3 integers");
    System.out.println(countUniqueIntegers(1, 2, 3));
    System.out.println(countUniqueIntegers(1, 3, 3));
    System.out.println(countUniqueIntegers(3, 3, 3));

    System.out.println("\n4 integers");
    System.out.println(countUniqueIntegers(1, 2, 3, 4));
    System.out.println(countUniqueIntegers(1, 2, 4, 4));
    System.out.println(countUniqueIntegers(1, 4, 4, 4));
    System.out.println(countUniqueIntegers(4, 4, 4, 4));​

    System.out.println("\n5 integers");
    System.out.println(countUniqueIntegers(1, 2, 3, 4, 5));
    System.out.println(countUniqueIntegers(1, 2, 3, 5, 5));
    System.out.println(countUniqueIntegers(1, 2, 5, 5, 5));
    System.out.println(countUniqueIntegers(1, 5, 5, 5, 5));
    System.out.println(countUniqueIntegers(5, 5, 5, 5, 5));​

    return;​
    }


    public static int countUniqueIntegers(int ... integers) {

    int count = 0;

    for(int i0 = 0; i0 < integers.length; i0++) {
    for(int i1 = 0; i1 < integers.length; i1++) {
    if(integers[i0] - integers[i1] != 0) count = count + 1;​
    }​
    }

    return count;​
    }
     
    Sparky49 likes this.
  11. kubeek

    AAC Fanatic!

    Sep 20, 2005
    4,670
    804
    It would be less computational intesive for large array if you do it like this:
    The number of steps is N+M, instead of N*N, where N is the number of integers and M is the range of the numbers inputted.
    Code (Text):
    1. N=5, M=5;
    2. int[N] inputIntegers;
    3. int[M] count;
    4. int result;
    5. for(int i=0;i<N;i++)
    6. {
    7.   count[inputIntegers[i]]++;
    8. }
    9. for(int i=0;i<M;i++)
    10.   if(count[i]== 3)...;//match found
    11. }
     
    Last edited: Mar 1, 2015
    darrough and Sparky49 like this.
  12. Sparky49

    Thread Starter Active Member

    Jul 16, 2011
    834
    417
    Thanks guys, I'll have a play with those examples tonight. May need a couple of modifications as this is for pic based C (my compiler doesn't like declaring variables in for loops, for example).

    Many thanks again.
     
  13. darrough

    Member

    Jan 18, 2015
    86
    19
    Kubeek, that would work well, provided you you know the upper and lower bounds of the set in advance, and the upper bound were small enough and the lower bound >= 0.

    If the set had other properties, like it was powers of two, or all prime numbers, there might be some way to write a function that returned the number unique integers in the set.

    Actually though, the OP said "If three and only three are the same, then the idea is that a player will press their button to score a point.". In other words, it is not the number of unique numbers, but the number of duplicates.

    For example
    1 1 2 3 3 - 3 unique numbers but not 3 duplicates
    1 1 1 2 2 - 2 unique numbers but 3 duplicates
    1 1 1 2 3 - 3 unique numbers and 3 duplicates

    This problem requires more thinking.
     
  14. djsfantasi

    AAC Fanatic!

    Apr 11, 2010
    2,804
    833
    Ok, it may be inefficient, but is efficiency a requirement of the problem statement? Way back in the thread is a complete program, compiled and tested. It's only five numbers.

    "Perfect is the enemy of good enough" - Eric Johns
     
  15. darrough

    Member

    Jan 18, 2015
    86
    19
    Try this. I think it works.

    Code (Text):
    1.  
    2. // true iff the input set has any value with exactly matchingDupCount duplicates.
    3. public static boolean countDuplicates(int matchingDupCount, int ... numbers) {
    4.  
    5. int setsize = numbers.length;
    6.  
    7. // have to have at least three numbers to have three duplicates.if(setsize < 3) return false;
    8.  
    9. int[] counts = new int[setsize];
    10. int[] values = new int[setsize];
    11. int valndx = 0;
    12.  
    13. // iterate the input set, numbers
    14. next_number: for(int i = 0; i < setsize; i++) {
    15. // compare each number to numbers found on prior iterations.
    16. for(int j = 0; j < valndx; j++) {
    17.  
    18. // if this number matches a prior number then increment the count for that number
    19.  if(numbers[i] == values[j]) {
    20. counts[j]++;
    21. continue next_number;
    22. }
    23. }
    24.  
    25. // number matched any prior number would have continued to next_number.
    26. // therefore this number is unique. add it to the list of numbers found
    27. // during prior iterations.
    28. values[valndx] = numbers[i];
    29. counts[valndx] = 1;
    30. valndx++;  
    31. }
    32.  
    33. // valndx is now the number of unique numbers in the input set.
    34.  
    35. for(int i = 0; i < valndx; i++) {
    36. if(counts[i] == matchingDupCount) return true;
    37.  }
    38.  
    39. return false;
    40.  }
    41.  
    Something is not working with indentation. I dont get it.
     
    Last edited: Mar 1, 2015
  16. WBahn

    Moderator

    Mar 31, 2012
    17,743
    4,795
    But it seems that your approach is assuming that there are only five possible shapes, numbered 0 through 4. I don't see that this is a requirement of the problem statement, so what if there are 10 possible shapes and, from that pool, five a chosen randomly (with replacement)? So the values might be {2, 7, 6, 7, 7}.
     
  17. darrough

    Member

    Jan 18, 2015
    86
    19
    djsfantasi, your solution works as long as the set is always five numbers and the numbers in the set are all 1 2 3 4 or 5. It would not work, for example with -12, 292, 292, -12, 292, 19, 74.

    The OP does say that there are 5 numbers in the sequence, but he never said that they are in the range 1 <= X <= 5.
     
  18. djsfantasi

    AAC Fanatic!

    Apr 11, 2010
    2,804
    833
    Fair enough. Since the example given had five values, I did make that assumption. But the algorithm still holds and unless we are talking about a pool of values whose ordinality is orders of magnitude greater, it still is a "good enough" solution. IMHO
     
  19. WBahn

    Moderator

    Mar 31, 2012
    17,743
    4,795
    As with most things, what is "good enough" depends on the constraints. If this is in an extremely resource-starved micro, like some of the small PICs, then using an array to store the counts might be too expensive, while simply going through the loop and counting things might be more than fast enough. Consider the following:

    Code (Text):
    1.  
    2. #define SHAPES (5) // Sets the size of the array of integers.
    3. #define TOKEN (-1)  // Set to a value that can be represented but that is NOT a valid shape number.
    4. #define CRITERION (3) // How many of the of the same shape is required for a match.
    5.  
    6. int HitButton(int shapes[SHAPES])
    7. {
    8.    int index, j;
    9.    int count, found;
    10.  
    11.    for (index = 0, found = 0; index < SHAPES; index++)
    12.    {
    13.       if (TOKEN != shapes[index])
    14.       {
    15.          for (j = index+1, count = 1; j < shapes; j++)
    16.          {
    17.             if (shapes[j] == shapes[index])
    18.             {
    19.                count++;
    20.                shapes[j] = TOKEN;
    21.             }
    22.          }
    23.          if (CRITERION == count) return 1;
    24.       }
    25.    }
    26.    return 0;
    27. }
    28.  
    NOTE: This code has NOT been compiled or tested.
     
  20. RamaD

    Active Member

    Dec 4, 2009
    254
    33
    GopherT's initial program itself can be modified to suit the clarified requirement.

    Code (Text):
    1. for(i=0; i < 3; i++)
    2. {
    3.    zeroctr = 0;
    4.    for(j=i+1; j < 5; j++)
    5.    {
    6.       if(NumArray[i] == NumArray[j]) ++zeroctr;
    7.    }
    8.    if(zeroctr == 3)
    9.    {
    10.       // 3 & Only 3 Matches occurred. Do whatever required.
    11.    }
    12. }
     
Loading...