## 10067 - Playing with Wheels

Moderator: Board moderators

Eric____
New poster
Posts: 8
Joined: Thu Jan 30, 2003 10:13 am
Contact:

### 10067, playing with wheels

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 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 >> 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
New poster
Posts: 8
Joined: Thu Jun 26, 2003 3:38 am

### 10067 - Playing with Wheels

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 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))
{
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
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
One critical case is that the target itself could be forbidden.
Last edited by shamim on Tue Aug 26, 2003 10:53 am, edited 1 time in total.

AllanLin
New poster
Posts: 8
Joined: Thu Jun 26, 2003 3:38 am
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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:
I tried my best with this programming and getting WA. please help to find bug in my program.
[c]...code deleted...[/c]
Last edited by Subeen on Tue Jan 27, 2004 7:59 am, edited 1 time in total.

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
did u considered if the initial position is same with the target position?
Kalo mau kaya, buat apa sekolah?

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:
thanks, titid. after considering that case I got it AC

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

### time taken to solve

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

Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA
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
if u can think of it .. u can do it in software.

rmotome
New poster
Posts: 14
Joined: Mon Jan 10, 2005 12:20 pm

### 10067 AGAIN! :-(

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 };
struct node {
int x;
};
{
t->x = x;
t->next = next;
return t;
}
void QUEUEinit()
{
}
int QUEUEempty()
{
}
void QUEUEput(int v)
{
if (QUEUEempty()) {
} else {
tail->next = NEW(v, tail->next);
tail = tail->next;
}
}
int QUEUEget()
{
int v;
v = t->x;
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);
}
{
char *x;
char *t;
char p;
int tlen;
int i;
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;
}
{
int i;
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;
}
}
{
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];
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++)
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
New poster
Posts: 14
Joined: Mon Jan 10, 2005 12:20 pm
Just looking for input that could break my program, source is for ur experimentation pleasure

rmotome
New poster
Posts: 14
Joined: Mon Jan 10, 2005 12:20 pm

### I can't do what?!!!!!!!!!!!!!

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
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:
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
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am