10067 - Playing with Wheels

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10067, playing with wheels

Post by Eric____ » Sun Mar 30, 2003 10:53 pm

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

10067 - Playing with Wheels

Post by AllanLin » Wed Aug 06, 2003 3:48 am

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

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


[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 :o

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Wed Aug 06, 2003 9:22 am

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

Post by AllanLin » Wed Aug 06, 2003 11:08 pm

:( 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!
:lol:

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Aug 07, 2003 12:01 am

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
Location: Bangladesh
Contact:

Post by Subeen » Sat Jan 24, 2004 9:25 am

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

Post by titid_gede » Mon Jan 26, 2004 6:28 am

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
Location: Bangladesh
Contact:

Post by Subeen » Tue Jan 27, 2004 7:54 am

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

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

time taken to solve

Post by abishek » Sat Mar 06, 2004 7:27 am

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
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish » Sat May 22, 2004 9:55 pm

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
Location: Kitchener, Ontario, Canada

10067 AGAIN! :-(

Post by rmotome » Mon Jan 17, 2005 5:01 pm

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
New poster
Posts: 14
Joined: Mon Jan 10, 2005 12:20 pm
Location: Kitchener, Ontario, Canada

Post by rmotome » Sat Feb 12, 2005 6:49 am

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
Location: Kitchener, Ontario, Canada

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

Post by rmotome » Sun Feb 13, 2005 5:18 am

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.

User avatar
N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:

Post by N|N0 » Wed Apr 27, 2005 7:04 pm

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
Location: TORONTO, CANADA

Post by daveon » Sun Aug 07, 2005 5:01 pm

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.

Post Reply

Return to “Volume 100 (10000-10099)”