ADC #4 Results

[Prelude]

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

#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.

#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.

#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.

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:

#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!

[ygfperson]

Nice job

[Magos]

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 .

[swoopy]

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

[darksaidin]

Too bad you can't define a shorter macro for "define" Would have saved a few more bytes in Salems code....

[quzah]

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.

[XSquared]

>>funner
It's 'more fun', not 'funner'.

[quzah]

Originally posted by XSquared
>>funner
It's 'more fun', not 'funner'.

No. It's more gooder. Not more fun.

Quzah.

[quzah]

Here's the last recursive version that was in the project workspace:

#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.

[Sang-drax]

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.