10067 - Playing with Wheels

[Eric____]

this is not a popular problem but i need some help.
i represent every possible machine state as a vertex as an integer (0-9999)
there s an edge between 2 vertices if one can reach the other by one click
forbidden numbers are stored in a list to checked against validation.
my approach is to do a breath-first search on every test case to find the shortest path from start vertex to end vertex.
but i got MAX TIME EXCEED error. i dont see any way to make it more efficient , plz help.
thanks for looking

[cpp]
#include <iostream>
using namespace std;

#define MAXV 10000
#define MAXDEGREE 8
#define MAXQUEUELENGTH 10000

typedef struct {
int edges[MAXV+1][MAXDEGREE];
int degree[MAXV+1];
int nvertices;
int nedges;
}graph;

typedef struct {
int value[MAXQUEUELENGTH];
int start;
int size;
}queue;

void initialize_queue(queue *q);
void enqueue(queue *q, int k);
int dequeue(queue *q);
int size(queue *q);
void print_queue( queue *q);

void print_queue(queue *q)
{ cout <<"start ="<<q->start<<endl;
cout <<"size ="<<q->size<<endl;
int i;
for (i=q->start; i< q->start+q->size; i++)
cout <<q->value<<" ";
cout <<endl;
}

void read_graph(graph *g, bool directed, bool check_duplicate);
void initialize_graph(graph *g);
void insert_edge(graph *g, int x, int y, bool directed, bool check_duplicate);
void print_graph(graph *g);

void initialize_queue(queue *q)
{ q->start = 0;
q->size = 0;
}

void enqueue(queue *q, int k)
{ if (q->size >= MAXQUEUELENGTH)
cout <<"max capacity of queue reached"<<endl;
else
{ q->value[(q->start+q->size)%MAXQUEUELENGTH]=k;
q->size = (q->size+1)%MAXQUEUELENGTH;
}
}

int dequeue(queue *q)
{ if (q->size==0)
return -1;
int ans = q->value[q->start];
q->start = (q->start+1)%MAXQUEUELENGTH;
q->size--;
return ans;
}

int size(queue *q)
{ int ans;
ans = q->size;
return ans;
}
/*
void read_graph(graph *g, bool directed, bool check_duplicate)
{ int i;
int m;
int x, y, temp;
initialize_graph(g);
//scanf("%d %d", &(g->nvertices), &m); // num of vertices
//num of edges
cin >>temp ;
g->nvertices = temp;
cin >>m;
for (i=1; i<=m; i++)
{ cin>>x;
cin >> y;
insert_edge(g, x, y, directed, check_duplicate);
}
}
*/
void initialize_graph(graph *g)
{ int i;
g->nvertices = 0;
g->nedges = 0;
for (i=0; i<=MAXV; i++)
g->degree=0;
}

void insert_edge(graph *g, int x, int y, bool directed, bool check_duplicate)
{
int i;
bool found = false;
if (check_duplicate)
{ found = false;
for (i=0; i<g->degree[x]; i++)
{ if (g->edges[x]==y)
{ found = true;
cout<<"duplicate insert found"<<endl;
break;
}
}
}

if (!found)
{if (g->degree[x] > MAXDEGREE)
cout <<"Warning: insertion exceeds max degree"<<endl;
g->edges[x][g->degree[x]]=y;
g->degree[x]++;

if(directed == false)
insert_edge(g, y, x, true, check_duplicate);
else g->nedges++;
}
}
/*
void print_graph(graph *g)
{ cout <<"PRINT GRAPH"<<endl;

int i, j;
cout <<"g->nvertices ="<<g->nvertices<<endl;
cout <<"nedges ="<<g->nedges<<endl;
for (i=1; i<=g->nvertices; i++)
{ for (j=0; j<g->degree; j++)
cout <<i<<"-->"<<g->edges[j]<<" ";
cout <<endl;
}

int i;
for (i=0; i<=9999; i++)
cout <<g->degree<<" ";

}
*/
bool valid_edge(int edge, int barr[])
{ //return true;
//return false;
int i;
for (i=1; i<=barr[0]; i++)
{
if (edge == barr)
return false;

}

return true;
}

void process_vertex(int v)
{}

void process_edge(int from, int to)
{}

void bfs(graph *g, int start, int parent[], int barr[],int theEnd)
{ bool processed[MAXV];
bool discovered[MAXV];
// int parent[MAXV];

queue q;
int v;
int i;
//initialize the search
// cout <<"nvertices ="<<g->nvertices<<endl;
for (i=0; i< g->nvertices; i++)
{ processed = false;
discovered = false;
parent = -1;
}

initialize_queue(&q);

enqueue(&q, start);
discovered[start] = true;

while (size(&q)!=0)
{ v = dequeue(&q);
process_vertex(v);
processed[v] = true;



for (i=0; i<g->degree[v]; i++)
{ if(valid_edge(g->edges[v][i], barr)==true)
{
if (discovered[g->edges[v][i]] == false)
{ enqueue(&q, g->edges[v][i]);
discovered[g->edges[v][i]]=true;
parent[g->edges[v][i]] = v;
if (g->edges[v][i]==theEnd)
return;
}

if (processed[g->edges[v][i]] == false)
process_edge(v, g->edges[v][i]);
}
}
}
/*
for (i=1; i<=g->nvertices; i++)
cout << i<<" ";
cout <<endl;
for (i=1; i<=g->nvertices; i++)
cout << parent[i]<<" ";
cout<<endl;
*/
}

void main()
{// cout <<"hi"<<endl;
int i,j, temp1, temp2, temp3;
graph myGraph;
initialize_graph(&myGraph);
myGraph.nvertices = 10000;
for (i=0; i<=9999; i++)
{ for (j=1; j<=1000; j*=10)
{ temp1 = i/j;
temp2 = temp1%10;
if (temp2!=9)
temp3=i+j;
else
temp3=i-9*j;
insert_edge(&myGraph, i, temp3, false, true);
}
}


int n, start, end;
int bad;
int current, value, count, temp;
int f1, f2, f3, f4;
bool flag = false;
int parent[MAXV];
int barr[MAXV+1];
int theEnd;
cin >>n;



while (n!=0)
{ cin >> f1; cin>>f2; cin>>f3; cin>>f4;
start = 1000*f1+100*f2+10*f3+f4;
cin >> f1; cin>>f2; cin>>f3; cin>>f4;
end = 1000*f1+100*f2+10*f3+f4;
theEnd = end;

cin >> bad;
barr[0] = bad;

for (i=1; i<=bad; i++)
{
cin >> f1; cin>>f2; cin>>f3; cin>>f4;
temp = 1000*f1+100*f2+10*f3+f4;
barr[i] = temp;
}
bfs(&myGraph, start, parent, barr, theEnd);

count = 0;
current = end;
value = end;

while (value!=start && value!=-1)
{ current = value;
value = parent[current];
count++;
}

if (value==-1)
cout <<"-1"<<endl;
else cout <<count<<endl;

n--;
}




}

[/cpp]

[AllanLin]

HEY, I NEED SOME HELP FROM ALL YOUR SMART PEOPLE OUT THERE !


I been working on this problem and I tested it with a few of my own, and all seems ok! Well if anyone can give me a test case or maybe find a problem in my code it wuold be greatly apprechiated!


[c]
#include<stdio.h>

int n1,n2;
int change [8][4] ={ { +1 , +0 , +0 , +0 },
{ -1 , +0 , +0 , +0 },
{ +0 , +1 , +0 , +0 },
{ +0 , -1 , +0 , +0 },
{ +0 , +0 , +1 , +0 },
{ +0 , +0 , -1 , +0 },
{ +0 , +0 , +0 , +1 },
{ +0 , +0 , +0 , -1 } };
int q[10000];
int c[10000];
int f[10000];
int t=0,b=0;

int turn ( int num, int dir )
{
num = num + dir;
if( num > 9 ) num = 0;
if( num < 0 ) num = 9;
return num;
}


int push(int num, int cur)
{

int i ;

if(num== n2)
{

printf("%d\n",cur-1);
return 1;

}

for(i=0;i<t;i++)
if( q == num )
return 0;

c[t]=cur;
q[t]=num;
t++;
return 0;
}

int add(int num,int cur)
{
int i;
int a1,a2 = (num /1000) % 10;
int b1,b2 = (num /100) % 10;
int c1,c2 = (num /10) % 10;
int d1,d2 = (num /1) % 10;

for(i = 0; i < 8; i++ )
{
a1 = turn ( a2 ,change[0] );
b1 = turn ( b2 ,change[1] );
c1 = turn ( c2 ,change[2] );
d1 = turn ( d2 ,change[3] );

if(f[a1*1000+b1*100+c1*10+d1] == 0)
if(push(a1*1000+b1*100+c1*10+d1, cur+1))
return 1;
}
return 0;
}


int main()
{
int ntest,i,j,done;
int temp,temp1,fb;

scanf("%d",&ntest);
while( ntest > 0)
{
ntest--;
n1=0;n2=0;
temp =0;
temp1 =0;
fb =0;
for(i=0;i<10000;i++)
{
q=0;
f=0;
c=0;
}
for(i=0;i<4;i++)
{
scanf("%d",&temp);
n1 = n1*10 + temp;
}
for(i=0;i<4;i++)
{
scanf("%d",&temp);
n2 = n2*10 + temp;
}
scanf("%d",&fb);
for(i=0;i<fb;i++)
{
temp1 =0;
for(j=0;j<4;j++)
{
scanf("%d",&temp);
temp1 = temp1 * 10 + temp;
}
f[temp1]=1;
}

t = 0;
done = 0;

if( f[n2] )
{
printf("-1");
done = 1;
}

push(n1,1);
while(( b < t ) && ( done==0))
{
if(add( q, c))
done = 1;
b++;
}
if(done == 0)
printf("-1\n");
}
return 0;
}
[/c]
i know it might be kind of code but it should work


THANKS EVERYONE

[shamim]

One critical case is that the target itself could be forbidden.

[AllanLin]

This is BFS ...

Thank you for your help but I belive that my algorithm is BFS. I have tested it with serveral test cases and all seems to be right. No sure which crazy case will make this program wrong. But the grader marked it wrong. Please If you can think of a test case which can make this program fail please do... Thanks Greatly Appreciated!

[Larry]

Try a lot of cases.. or alternatively, set b = 0 before each case...

If that doesn't fix it, I don't know, though it seems very convoluted, it is a BFS..

[Subeen]

I tried my best with this programming and getting WA. please help to find bug in my program.
[c]...code deleted...[/c]

[titid_gede]

did u considered if the initial position is same with the target position?

[Subeen]

thanks, titid. after considering that case I got it AC

[abishek]

hi,
i solved this problem today and i find that the time taken to solve is 12... secs
and the timelimit for this problem has been extended to 15secs from the usual 10 secs
and then i go and see in the ranklist only to find that more that 100 people have times in 0....
types
i do plain BFS with the numbers as nodes and its eight new transformations as vertices
I hash each of the possible state of the wheel to an integer
is there anything more efficient that this that is possible?
bye
abi

[jagadish]

i used plain Bfs too and got ac with 0.65 secs ..probably u should to have a second look at the data structue u are using for nodes

[rmotome]

I have checked previous posts and know for sure that my solution is correct and most likely what first comes to mind when dealing with this problem. However, I still can't get mine excepted. If u have any ideas I would love to hear from u.

Thanks, Robert

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>
#define N 10001
#define INF ULONG_MAX
static char *buffer;
static int r;
static int color[N];
static int pre[N];
static int d[N];
enum { NIL = -1, WHITE = 0, GRAY, BLACK };
typedef struct node *link;
struct node {
int x;
link next;
};
static link head, tail;
static link graph[N];
link NEW(int x, link next)
{
link t = malloc(sizeof *t);
t->x = x;
t->next = next;
return t;
}
void QUEUEinit()
{
head = NULL;
}
int QUEUEempty()
{
return head == NULL;
}
void QUEUEput(int v)
{
if (QUEUEempty()) {
head = tail = NEW(v, head);
} else {
tail->next = NEW(v, tail->next);
tail = tail->next;
}
}
int QUEUEget()
{
link t;
int v;
t = head;
v = t->x;
head = head->next;
free(t);
return v;
}
void reverse(char *x)
{
int v;
int t;
int tmp;
v = 0;
t = strlen(x)-1;
while (v < t) {
tmp = x[v];
x[v] = x[t];
x[t] = tmp;
++v;
--t;
}
}
void f(char *x, int v)
{
int i;
i = 0;
do {
x[i++] = v % 10 + '0';
} while (v /= 10);
x = '\0';
reverse(x);
}
link adjlist(int v)
{
char *x;
char *t;
char p;
int tlen;
int i;
link coll;
f(x = &buffer[r], v);
r += strlen(x)+1;
sprintf(t = &buffer[r], "%04s", x);
r += strlen(t)+1;
coll = NULL;
tlen = strlen(t);
for (i = 0; i < tlen; i++) {
p = t;
if (p == '9')
t = '0';
else t = (char) p+1;
coll = NEW(atoi(t), coll);
t = p;
if (p == '0')
t = '9';
else t = (char) p-1;
coll = NEW(atoi(t), coll);
t = p;
}
return coll;
}
void bfs(int v, link forb)
{
int i;
link t;
link pos;
int x;
QUEUEinit();
for (i = 0; i < N; i++) {
color = WHITE;
pre = NIL;
d[i] = INF;
}
for (pos = forb; pos != NULL; pos = pos->next)
color[pos->x] = BLACK;
if (color[v] == BLACK) return;
d[v] = 0;
color[v] = GRAY;
QUEUEput(v);
while (!QUEUEempty()) {
i = QUEUEget();
for (t = graph[i]; t != NULL; t = t->next) {
if (color[t->x] == WHITE) {
color[t->x] = GRAY;
d[t->x] = d[i]+1;
pre[t->x] = i;
QUEUEput(t->x);
}
}
color[i] = BLACK;
}
}
void delete_list(link *x)
{
link t, tmp;
t = tmp = *x;
while (t != NULL) {
t = t->next;
free(tmp);
tmp = t;
}
}
void print_path(int x, int t)
{
if (x == t)
printf("%d\n", x);
else if (pre[t] == NIL)
printf("No path from %d to %d exists.\n", x, t);
else {
print_path(x, pre[t]);
printf("%d\n", t);
}
}
main()
{
char x[5];
char t[5];
char s[5];
link forb;
int v;
int w;
FILE *in;

in = stdin;
assert(in);
t[4] = '\0';
x[4] = '\0';
s[4] = '\0';
buffer = malloc(10000000*sizeof(char));
r = 0;
for (v = 0; v < N; v++)
graph[v] = adjlist(v);
forb = NULL;
fscanf(in, "%d\n", &v);
while (v--) {
fscanf(in, "%c %c %c %c\n", &t[0], &t[1], &t[2], &t[3]);
fscanf(in, "%c %c %c %c\n", &x[0], &x[1], &x[2], &x[3]);
fscanf(in, "%d\n", &w);
while (w--) {
fscanf(in, "%c %c %c %c\n", &s[0], &s[1], &s[2], &s[3]);
forb = NEW(atoi(s), forb);
}
bfs(atoi(t), forb);
#ifdef NDEBUG
print_path(atoi(t), atoi(x));
printf("button presses: %d\n", d[atoi(x)]);
#else
if (d[atoi(x)] == INF)
printf("%d\n", -1);
else
printf("%d\n", d[atoi(x)]);
#endif
delete_list(&forb);
forb = NULL;
}
}

[rmotome]

Just looking for input that could break my program, source is for ur experimentation pleasure

[rmotome]

Sorry, was just following the [bad] example of others on the board. I will have to do the work myself. On a related note, I just got a copy of the book "The Practice of Programming" thought I might learn good programming habits from the get-go. From the look of things many on the forum should consider taking a quick look at the book, it will not only improve the quality of your code but reduce the time you spend coding and debugging, book's claim not mine.

[N|N0]

Has anyone experiences with http://www.programming-challenges.com ?
I get AC here:

Dear Nino:

Your C program has solved Ok the problem 10067 (Playing with Wheels)
in 1.582 seconds using as much as 628 kbytes of virtual memory.
Congratulations!

But WA at http://www.programming-challenges.com.
Has anyone any clue?

[daveon]

To AllanLin,

One important thing to remember is turning the wheels.
The numbers are from 0-9.
So adding 1 to 9 -> 0 and not 10;
So subtracting 1 from 0 -> 9 and not -1;

Hope this helps.