CareerCup

thats really good thinking in writing the code but I want to point out some bugs in there. Please correct me if I am wrong.
1) Strings that you declared need to be declared as Arrays
2) You will have to delete the particular record from array and rearrange the array as soon as you find the "hit" because you will be comparing the non-hit ones with already hit ones. I hope you understand what I am trying to say.

The solution to this is really easy..

findHits(char *sol, char *guess)
{
  int hits = 0, phits = 0;
  int arrS[4]={0,0,0,0}, arrG[4]={0,0,0,0};
  while(*sol != '\0') {
    if(*sol == *guess) {
      hits++;
    }
    else {
      arrS[getIndex(*sol)]++;
      arrG[getIndex(*guess)]++;
    }
    sol++; guess++;
  }
  for(int i = 0i i<4; i++) {
    phits += min(arrS[i],arrG[i]);
  }
  // print hits n phits
}

Algo:

First check each char from guess with solution. If they match hit++, store the char. Take that char off from the solution.
Eliminate all the char which produce a hit (i.e. all Gs gone).
Sort the remaining (to remove all duplicates)
Then check if any of the remain char exist in the solution.

1. Hoping the algo is complete
2. Guessing that it is highly inefficient. If any one has ideas of how to make it more efficient / a more elegant solution please do post it

1. First scan the solution string and insert characters into the hashtable.
2. Now take the guess string.
a) Check if guess string char at i is equal to solution char at i
b) If it is then hits++
c) Otherwise, check if the guess string char is in the hashtable
d) If it is then pseudo-hits++

Save your optimizing for elsewhere -- we're talking about only four elements!

string solution = "RGGB";
string guess = "YRGB";

//creata hash entries for solution string
Hashtable HTable = new Hashtable();
HTable.Add(0, solution[0]);
HTable.Add(1, solution[1]);
HTable.Add(2, solution[2]);
HTable.Add(3, solution[3]);

for(int i = 0; i < guess.Length; i++)
{
if(guess[i] == solution[i])
{
hits++;
continue;
}

if(HTable.ContainsValue(guess[i]))
pseudoHits++;
}

I would also use a hashtable to allow O(1) lookup. Since the string is 4 characters, not including NULL, it's alright to search it iteratively by O(n). Basically, do a pairwise comparison...

Vars:
unsigned rHits=0;
unsigned pHits=0;

for(int i=0;i<str.length;i++)
if(str.charAt(i) != table.getValue(i))
rHits++;
else
pHits++;

the code feed got messed up

let's try that again w/ a minor bug fix...



for(int i=0;i<str.length;i++)
if(str.charAt(i) != table.getValue(i))
pHits++;
else
rHits++;

the 2nd condition should be...

!table.getValue(str.charAt(i))

You could try using an array but since the worst case is 16 comparisons, the overhead of using a hash table would probably be smaller than creating an array of 2^32 characters, assuming each color is a byte and 1 byte=8 bits.

btw checking if hashtable contains certain value is not O(1). hashtable runs in O(1) if you have key and retrieve the associated value. under different keys, if you store same values they will be mapped to different buckets so it is O(n). thus, not better than doing brute force linear search on solution array.

char *solution = "RGGB";
char *guess = "YRGB";

int realHit = 0;
int pseudoHit = 0;

for (int i=0; i<4; i++) {
if (solution[i] == guess[i]) {
realHit++;
guess[i] = 0;
solution[i] = 0;
}
}

for (i=0; i<4; i++) {
if (guess[i] == 0) continue;
for (int j=0; j<4; j++) {
if (guess[i] == solution[j]) {
pseudoHit++;
guess[i] = 0;
solution[j] = 0;
}
}
}

char *Soln = "RGGB"
char *Guess = "YRGB"

int iHit = 0;
int iPseudo = 0;
int iTemp = 0;

for(int i = 0;i < 4;i++) // First check for real hits
{
if(Soln[i] == Guess[i])
iHit++;
else
{
Soln[iTemp] = Soln[i];
Guess[iTemp] = Guess[i];
iTemp++;
}
}

for(int i = 0;i < iTemp;i++) // Check for Pseudo hits in the reduced array
{
for(int j = 0;j < iTemp;j++)
{
if(Guess[i] == Soln[j] && Soln[j] != 0)
{
iPseudo++;
Soln[j] = 0;
}
}
}

I just realized that you can do this in O(n) but we'd have to destroy the original string, but, thats fine because it is being done within a function.

Bugs and bashes welcome :)

Gayle- Awesome site!

Cheers!
Sunil Jagadish

-------------------------------------------

#include<stdio.h>
#include<string.h>

#define SIZE 10

void find_hits(char *, char *);

int main()
{

char org_str[SIZE], guess_str[SIZE];

printf("\nEnter the original string and the guess: ");
scanf("%s %s",org_str,guess_str);

find_hits(org_str, guess_str);
}

void find_hits(char *org, char *soln)
{
int hits=0, pseudohits=0;
int i=0;
char *c;

while(soln[i] != '\0')
{

if(tolower(soln[i]) == tolower(org[i]))
{
hits++;
i++;
continue;
}

// Get the first occurance of the character in the original str
ng
c = strchr(org, soln[i]);
if(c != NULL)
{
// If it is found, then set the character to '0' so that a
// second match isnt wrongly considered as a pseudo-hit
memset(c, '0', sizeof(char));
pseudohits++;
}

i++;
}
printf("\nOriginal string: %s\n\n", org);
printf("\nOutput:\nNo. of hits = %d\nNo. of pseudo-hits = %d\n\n",hits,
pseudohits);
}

The original string is actually destroyed because it is passed as a reference to the function :)

I think, in above solution, even if the outer for loop is O(n), we are not considering the complexity of strchr function. Its not some magic function, but internally searches the string sequentially to find out the occurrence.

Solve in O(n)
string a1="RGGB";
string a2="YRGB";
map<char, bool> color;
int hit=0;
int p_hit=0;
for(int i=0;i<4;i++)
{
if(!color[a1[i]])
color[a1[i]]=1;
if(a2[i]==a1[i])
{
hit++;
a2[i]='0';

}
}

for(int i=0;i<4;i++)
{
if(a2[i]!='0')
if(color[a2[i]])
p_hit++;

}
cout<<hit<<":"<<p_hit<<endl;

static hash[26];
j=0;
for(i=0;i<n;++i)
{
if(solu[i]== guess[i])hit++;
else { guess[j++]= guess[i]; hash[tolower(solu[i])-97]= 1;
}

for(i=0;i<j;++i)
if(hash[tolower(guess[i])-97)]==1){ pseudohit++; hash[tolower(guess[i])-97)]= 0;}

static hash[26];
j=0;
for(i=0;i<n;++i)
{
if(solu[i]== guess[i])hit++;
else { guess[j++]= guess[i]; hash[tolower(solu[i])-97]= 1; }
}

for(i=0;i<j;++i)
if(hash[tolower(guess[i])-97)]==1){ pseudohit++; hash[tolower(guess[i])-97)]= 0;}

package com.careercup.book.four.one;

import java.util.HashMap;
import java.util.Map;

public class NINETEEN_FIVE {

    public static void main(String[] args) {
        char[] solution = new char[] { 'R', 'G', 'G', 'B' };
        char[] guess = new char[] { 'Y', 'R', 'G', 'B' };
        displayHits_PsuedoHits(solution, guess);
    }

    protected static void displayHits_PsuedoHits(char[] solution, char[] guess) {
        Map<Integer, String> solutionMap = new HashMap<Integer, String>();
        for (int i = 0; i < solution.length; i++) {
            solutionMap.put(i, solution[i] + "");
        }
        int hits = 0, pseudoHits = 0;
        for (int i = 0; i < guess.length; i++) {
            if (guess[i] == solution[i]) {
                hits++;
                continue;
            }
            if (solutionMap.containsValue(guess[i] + "")) {
                pseudoHits++;
            }
        }

        System.out.println("Hits: " + hits);
        System.out.println("pseudoHits: " + pseudoHits);
    }
}

Output:

Hits: 2
pseudoHits: 1

I don't understand that code. The user doesn't guess anything and there's no interaction. How is that supposed to work?

I used the hashtable approach with O(n) but I got rejected. He guided me to use replace characters approach which is O(n^2). I tried to explain why I used hashtable but he wasn't interested and he said time is up and they rejected me after