ADC #4 Results

This is a discussion on ADC #4 Results within the Contests Board forums, part of the Community Boards category; We had a pretty poor turnout this time around, only four entries. However, they were all top notch programmers and ...

  1. #1
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796

    ADC #4 Results

    We had a pretty poor turnout this time around, only four entries. However, they were all top notch programmers and certainly submitted interesting code. Here are the results (the code posted may not look the same as in my tests):

    Salem
    -----
    Correct at 330 bytes
    Code:
    #define R return s
    #define C const char
    #define I int
    #define L(a,b) for(r=a;r<b&&!s;r++)for(c=a;c<b&&!s;c++)I f(C**t,C*w,I*i,I y,I 
    
    x){I 
    
    r,c,s=1;if(!*w)R;s--;if((x|y)<0||y>4||x>4||*w!=t[y][x])R;i[0]=i[1]=-1;L(-1,2)if(r
    
    |c)s=f(t,w+1,i+2,y+r,x+c);if(s){*i++=y;*i=x;}R;}I wordSearch(C**t,C*w,I*i){I 
    
    r,c,s=0;L(0,5)s=f(t,w,i,r,c);R;}

    Sang-drax
    ---------
    Correct at 361 bytes.
    Code:
    #include <string.h>
    int wordSearch(const char**T,const char*O,int*I){int 
    
    H=strlen(T[0]),W=0,X=0,Y,x,y,d,f,F,i;const 
    
    char*w;while(strlen(T[++W])>0);for(;X<W;++X)for(Y=0;Y<H;++Y)for(d=-1;d<=1;++d)for
    
    (f=-1;f<=1;++f)if(d||f){w=O;x=X;y=Y;F=1;i=0;while(*w){if(x<0||x>W||y<0||y>H){F=0;
    
    break;}if(*w++!=T[x][y])F=0;I[i++]=x;I[i++]=y;x+=d;y+=f;}if(F)return 1;}return 
    
    0;}

    Magos
    -----
    Correct in 3 of 6 tests, 532 bytes.
    Code:
    #include <string>
    #define r return
    typedef const char* c;typedef int i;i S,X,Y,*I,v=0;c w,*T;
    i R(i C,i X,i Y,i x,i y){if(w[C]=='\0')r 1;if(X+x<0||X+x>=S||Y+y<0||Y+y>=S)r 
    
    0;if(T[X+x][Y+y]==w[C]){if(R(C+1,X+x,Y+y,x,y)==1){I[C*2]=X+x;I[C*2+1]=Y+y;r 1;}}r 
    
    0;}
    i W(c*t,c V,i*n){S=strlen(t[0]);w=V;I=n;T=t;for(i y=0;y<S;y++){for(i 
    
    x=0;x<S;x++){if(t[x][y]==w[0]){v+=R(1,x,y,1,1);v+=R(1,x,y,1,0);v+=R(1,x,y,1,-1);v
    
    +=R(1,x,y,0,1);v+=R(1,x,y,0,-1);v+=R(1,x,y,-1,1);v+=R(1,x,y,-1,0);v+=R(1,x,y,-1,-
    
    1);if(v>0){I[0]=x;I[1]=y;r 1;}}}}r 0;}

    Swoopy
    ------
    Correct at 477 bytes.
    Code:
    int wordSearch(const char **tab,const char *word,int *indices){int 
    
    r,c,k,x,y,i,m,n;int 
    
    d[8][2]={-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1};for(r=0;tab[r][0];r++)for(c=0;tab
    
    [r][c];c++)if(tab[r][c]==*word)for(i=0;i<8;i++){n=0;indices[n++]=r;indices[n++]=c
    
    ;m=1;for(x=r+d[i][0],y=c+d[i][1],k=1;word[k]&&x!=-1&&y!=-1&&tab[x][0]&&tab[x][y];
    
    x+=d[i][0],y+=d[i][1],k++){if(tab[x][y]!=word[k])m=0;indices[n++]=x;indices[n++]=
    
    y;}if(m&&!word[k]){indices[n]=-1;return 1;}}*indices=-1;return 0;}
    And my test code:
    Code:
    #include <stdio.h>
    #include <string.h>
    
    void showWord(const char **wordTable, const int *indices)
    {
        while (*indices != -1) {
            putchar(wordTable[*indices][*(indices + 1)]);
            indices += 2;
        }
    }
    
    void doTest(const char *word, int *indices, int size)
    {
        const char *tab[] = {
            "abcde",
            "babef",
            "taehc",
            "eetrh",
            "sfghi",
            ""
        };
    
        int i;
        for (i = 0; i < size; i++)
            indices[i] = -1;
    
        if (wordSearch(tab, word, indices) != 0) {
            printf("%s == ", word);
            showWord(tab, indices);
        }
        else
            puts("FAILED");
    }
    
    int main(void)
    {
        int indices[11];
    
        doTest("cat", indices, 11);
        doTest("bat", indices, 11);
        doTest("abe", indices, 11);
        doTest("cheat", indices, 11);
        doTest("bet", indices, 11);
        doTest("set", indices, 11);
    
        return 0;
    }
    The winner is Salem! Congratulations!
    My best code is written with the delete key.

  2. #2
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,493
    Nice job

  3. #3
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Congratulations.
    I must've made a mistake when "shrinking" my code, cause my original code works fine in your test function. Oh well, that's life .
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  4. #4
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    Congratulations to Salem, and to San-drax for finishing second! I also expected more entries. Isn't it fun to see the differing approaches to a contest? I guess Iamien never got his STL version working. Don't you imagine Prelude could compose an interesting entry for this one.

    Swoopy

  5. #5
    *******argv[] - hu? darksaidin's Avatar
    Join Date
    Jul 2003
    Posts
    314
    Too bad you can't define a shorter macro for "define" Would have saved a few more bytes in Salems code....
    [code]

    your code here....

    [/code]

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    This is just basic pathfinding. Commonly done with recursion. You can do it without recursion, but recursion is the easiest way to do it. I started a recursive version, but then thought non-recursive would be funner--so I stopped working on that one--and never got either one done.

    My problem is poor initial design. I tend to change my mind too much because I think of a funner way to do something.

    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    >>funner
    It's 'more fun', not 'funner'.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Originally posted by XSquared
    >>funner
    It's 'more fun', not 'funner'.
    No. It's more gooder. Not more fun.

    Quzah.
    Hope is the first step on the road to disappointment.

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Here's the last recursive version that was in the project workspace:
    Code:
    #define V(s)i[(s)*2+1]
    #define H(s)i[(s)*2]
    #define F for
    #define I int
    
    I m(char**t,char*w,I*i,I*x,I c,I d,I s){if
    (!w[s])return!(H(s)=V(s)=-1);H(s+1)=H(s)+(
    d>0&&d<4?1:d>4?-1:0);V(s+1)=V(s)+(d<2||d>6
    ?-1:d>2&&d<6?1:0);return H(s+1)<0?0:H(s+1
    )>x[V(s)]-1?0:V(s+1)<0?0:V(s+1)>c-1?0:w[s
    ]!=t[V(s)][H(s)]?0:1+m(t,w,i,x,c,d,s+1);}
    
    int wordSearch( char **tab, char *word, int *indices )
    {
    	I c,d,h,v,*x;
    
    	/* These give us our boundries. */
    	F(d=0;strlen(tab[d]);d++);c=d;
    	if((x=malloc(sizeof(int)*c))==NULL)
    		exit(0);
    	F(d=0;d<c;d++)x[d]=strlen(tab[d]);
    
    	/* For each cell, for each direction. */
    	F( v = 0; v < c; v++ )
            	F( h = 0; h < x[v]; h++ )
                		F( d = 0; d < 8; d++ )
    			{
    				indices[0]=h;
    				indices[1]=v;
    				memset( indices+2, -1, sizeof(int)*c-2 );
    				if( word[0]==tab[v][h] && m( tab, word, indices, x, c, d, 0 ) == strlen( word ) )
    					return 1;
    			}
        return 0;
    }
    A few things it won't do, because I don't feel like hunting them down:
    1) It won't do full length strings. It crashes. Boundry checking will likely be the issue here. It should be case, and I know about where the problem should be, I just haven't bothered fixing it because I missed the deadline (having only read this thread a few days before it ended).

    2) It has a problem with I believe in odd cases of what appears to be diagonal-repetetive-letter finds. For example, use the test block and have it find "ccc", it will fail. If you do a horiznotal "ccc" in the test block, it works fine.

    Anyway, I honestly spent more time trying to get the block of code to end up the same line length than actually writing that function. It was funner.

    I threw a couple of comments in so you'd know what it was doing. For size wise you'd naturally remove comments. #define-ing 'char' here doesn't get you any savings because it isn't used enough times.

    I don't have the non-recursive version, because I overwrote it at one point in time apparently. Non-recursive is harder, more looping. It can be done, it's just not as "clean". However, we're hardly going for cleanlyness are we?

    I also use two functions instead of one. I had a recursive version that only called 'wordSearch' recursivly, but I changed my design so much, it's gone too.

    [edit]
    I also malloc an index and count strings, so you can have different sized line lengths. This works sort of. The problem here is with the full-lenght-string and/or diagonal-repetetive problem, which again, I never bothered chasing down because I missed the date.

    Another odd thing I gave up on, is the actual search process itself. If you move the !w[s] check to the main return statement with all the rest of the checks, it will fail. Always. Very odd. I tried repositioning the check multiple times and finally figured it wasn't worth the time.

    I also memset the path when I drop from the loop. Normally you wouldn't do this, you'd just have your backtrack step take care of it (in pathfinding), but since I wanted to make sure the indices were right at the end without having to make it undo itself, I did it there. (The reason being, I was dumping the contents of the indices to the screen at the end to see what they held, stopping on -1.)
    [/edit]

    Quzah.
    Last edited by quzah; 08-28-2003 at 05:10 AM.
    Hope is the first step on the road to disappointment.

  10. #10
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Congratulations Salem!

    I could've shrunk my code a few more bytes by assuming that the table was NxN, which I didn't, but I still think you'd have beaten me.

    I could also have gotten rid of the "if(d||f)" part of the code, but then my program wouldn't have worked with word consisting of only one character. That would have been sort of cheating, though.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 72hour GDC Results
    By jverkoey in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 07-06-2004, 12:46 AM
  2. ADC #3 Results
    By Prelude in forum Contests Board
    Replies: 19
    Last Post: 08-19-2003, 12:25 AM
  3. ADC #2 Results
    By Prelude in forum Contests Board
    Replies: 20
    Last Post: 08-11-2003, 07:59 AM
  4. ADC #1 Results
    By Prelude in forum Contests Board
    Replies: 26
    Last Post: 08-06-2003, 04:57 AM
  5. Same seed for srand yields different results
    By codegirl in forum C++ Programming
    Replies: 3
    Last Post: 06-23-2003, 03:39 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21