Denis' Solution 1B: Safebreaker

This is the personal work of Denis Dmitriev; it is not an officially verified or endorsed solution.

Denis writes: The main idea of this solution is to take all the numbers [0000..9999] that may be part of an answer and to test them against the given conditions screening the unsuitable ones. -DD


C++ Source Code

#include <stdio.h>
#include <stdlib.h>

#include <vector>

using namespace std;

/* actual score function */
void score(char *correct,char *guess,int &_1,int &_2)
{
    /* initialize the counters */
    _1=_2=0;

    int i,j;
    bool res[4][2],match;

    /* check for exact matches */
    for(i=0;i<4;i++)
    {
        match=false;
        if(guess[i]==correct[i])
        {
            _1++;
            match=true;
        }
        res[i][0]=res[i][1]=match;
    }

    /* check for the correctly guessed digits in incorrect places */
    for(i=0;i<4;i++)
    {
        for(j=0;j<4;j++)
        {
            /* in order to be counted, the digit must be
             * misplaced,
             * must not be counted before and must not be one of
             * the exact matches
             */
            if(i!=j&&!res[j][1]&&!res[i][0]&&guess[j]==correct[i])
            {
                _2++;
                res[j][1]=true;
                break;
            }
        }
    }
}

void main(void)
{
    char against[5];
    int nt,ntests,i,_1,_2;

    vector<int> n;
    vector<int>::iterator fwd,end,curr;

    /* reserve space to avoid reallocations in the future */
    n.reserve(10000);

    FILE *fp=fopen("safe.in","r");
    FILE *fo=fopen("safe.out","w");

    fscanf(fp,"%d",&ntests);

    for(;ntests--;)
    {
        /* fill the vector with numbers */
        n.clear();
        for(i=0;i<10000;i++)
            n.push_back(i);

        fscanf(fp,"%d",&nt);

        for(end=n.end(),i=0;i<nt;i++)
        {
            /* read test case */
            fscanf(fp,"%s %d/%d",against,&_1,&_2);

            /* for every number in vector... */
            for(curr=fwd=n.begin();fwd!=end;fwd++)
            {
                int _t1,_t2;
                char init[5];
                sprintf(init,"%04d",*fwd);

                /* ...assume that it is an answer and check
                 * if
                 * it will cause the test case to produce
                 * the
                 * same score as given
                 */
                score(init,against,_t1,_t2);

                /* if it will -- consider it for the future
                 * */
                if(_t1==_1&&_t2==_2)
                    *curr++=*fwd;
            }

            /* shorten the sequence (removal of all the screened
             * numbers) */
            end=curr;
        }

        int size=end-n.begin();

        /* print the answer */
        if(!size)
            fprintf(fo,"impossible\n");
        else
        if(size==1)
            fprintf(fo,"%d\n",n[0]);
        else
            fprintf(fo,"indeterminate\n");
    }

    fclose(fo);
    fclose(fp);
}