Page 1 of 1

### 11664 - Langton's Ant

Posted: Sun Sep 06, 2009 5:05 pm
Please correct me if I'am not right!
We have a board with position of lower left corner(1,1) and upper right(n,n). And we need to check if it is possible to reach cell(n,n) from cell(x,y),and initial direction is north?

### Re: 11664 - Langton's Ant

Posted: Sun Sep 06, 2009 10:48 pm
from cell(y,x)
north is y++

### Re: 11664 - Langton's Ant

Posted: Mon Sep 07, 2009 8:48 am
I don't understand why from (y,x)???
Here is a part of my code... I don't know why WA....

Code: Select all

``````Cut.......
``````

### Re: 11664 - Langton's Ant

Posted: Mon Sep 07, 2009 10:44 am
Hi Igor9669,

My AC code assumed, that cell(x,y) is cell in x-th column and y-th row.

I think, that your problem may be in reading of second number of input. According problem description, this value is in range 0 to 2^(n^2)-1 in decimal representation. For n=16, maximal value for this number is 115792089237316195423570985008687907853269984665640564039457584007913129639935. This is too much for int. You need use function for big numbers. But (div 2) and (mod 2) is enough for this problem. (mod 2 is very easy )

For clarify both facts, here is sample input and output from my AC program:

Input:

Code: Select all

``````3 511 3 2
3 511 2 3
3 509 3 2
3 509 2 3
16 115792089237316195423570985008687907853269984665640564039457584007913129639935 16 15
16 115792089237316195423570985008687907853269984665640564039457584007913129639935 15 16
16 115792089237316195423570985008687907853269984665640564039457584007913129639933 16 15
16 115792089237316195423570985008687907853269984665640564039457584007913129639933 15 16
0 0 0 0
``````
Output:

Code: Select all

``````Kaputt!
Yes
Kaputt!
Kaputt!
Kaputt!
Yes
Kaputt!
Kaputt!
``````
Hope you will get AC now. ### Re: 11664 - Langton's Ant

Posted: Mon Sep 07, 2009 3:46 pm
removed stringstream to get AC. stringstream is very slow. Got TLE

### Re: 11664 - Langton's Ant

Posted: Tue Sep 08, 2009 8:40 am
Thanks!
You are right it was a problem with the 2 number!
But when I fixed this bug I got a lot of WA, while I change my code to Java, and find another mistake in code!
Now Ac! ### Re: 11664 - Langton's Ant

Posted: Tue Sep 08, 2009 2:27 pm
can you guys show me code to convert from big integer to mod2 string ?

Code: Select all

``````string mapper[]={"0","1","2","3","4","5","6","7","8","9"};

inline string myconvert(const string& s){
if(s=="0") return "0";
if(s=="1") return "1";
string ns;
int num=0,carry=0,i;
for(i=0;i<s.size();i++){
num=carry*10 + s[i]-'0';
if(num>=2){
//stringstream str;
//str << num/2;
ns+=mapper[num/2];
carry=num&1;
} else {
if(ns.size()) ns+="0";
carry=num&1;
}
}
num=s[s.size()-1]-'0';
if(num&1) return myconvert(ns)+"1";
else return myconvert(ns)+"0";
}``````

### Re: 11664 - Langton's Ant

Posted: Wed Sep 09, 2009 9:56 pm
I have a problem with the input case:

Code: Select all

``16 115792089237316195423570985008687907853269984665640564039457584007913129639935 16 15``
I have checked and rechecked the code, but I can't find the error! Thanks

Code: Select all

``````#include <iostream>
#include <vector>
using namespace std;

enum Direction { NORTH = 0, EAST = 1, SOUTH = 2, WEST = 3 };

Direction turnCW(Direction d) {
return d < 3 ? Direction(d + 1) : NORTH;
}

Direction turnCCW(Direction d) {
return d > 0 ? Direction(d - 1) : WEST;
}

void move(int& row, int& column, Direction d) {
switch(d) {
case NORTH: --row; break;
case EAST: ++column; break;
case SOUTH: ++row; break;
case WEST: --column; break;
}
}

string div2(const string& s) {
const int SIZE = s.size();
const int TWO = 2;
string r;
int ten = 0;
for(int i = 0; i < SIZE; ++i) {
int digit = (s[i] - '0') + ten;
if(digit % TWO == 0) {
r += (digit / TWO) + '0';
} else {
if(digit != 1) {
r += (digit / TWO) + '0';
}
}
ten = (digit % TWO == 0) ? 0 : 10;
}
return r;
}

int mod2(const string& s) {
return (s[s.size() - 1] - '0') % 2;
}

void init(vector< vector<bool> >& world, const int n, string& c) {
for(int i = 0; i < n; ++i) {
for(int j = n - 1; j >= 0; --j) {
if(mod2(c) == 0) {
world[i][j] = false;
}
c = div2(c);
}
}
}

bool valid(const int x, const int y, const int n) {
return (x >= 0 && x < n && y >= 0 && y < n);
}

bool langtonAnt(const int n, string& c, int x, int y) {
x = n - x; // Adjust x-coordinate from Automata World to Computing Matrix
--y; // Adjust y-coordinate from Automata World to Computing Matrix
vector< vector<bool> > world(n, vector<bool>(n, true));
init(world, n, c);
Direction d = NORTH;
while(valid(x, y, n)) {
bool red = world[x][y];
world[x][y] = !red;
d = red ? turnCW(d) : turnCCW(d);
move(x, y, d);
if(x == 0 && y == n - 1) {
return true;
}
}
return false;
}

int main() {
int n = 0, column = 0, row = 0;
string c;
cin >> n >> c >> column >> row;
while(n != 0) {
cout << (langtonAnt(n, c, row, column) ? "Yes" : "Kaputt!") << endl;
cin >> n >> c >> column >> row;
}
return 0;
}``````

### Re: 11664 - Langton's Ant

Posted: Fri Sep 11, 2009 7:38 pm
Hi slxst,

test your function div2. For some inputs returns wrong answers. For example, for 215 returns 17 (correct 107 --> "0" is missing) for 441 returns 22 (correct 220 --> "0" is missing again), etc.

The reason is in this part:

Code: Select all

``````if(digit % TWO == 0) {
r += (digit / TWO) + '0';
} else {
if(digit != 1) {
r += (digit / TWO) + '0';
}
}
``````
If (digit % TWO == 1) and the digit is 1, then you need (almost every time) add figure "0" to the result. Only in one specific case, "0" shouldn't be added - when it is leading zero (except input "1") . Another wrong input is 1, your function returns nothing, correct output is "0". Try to fix it. Hope you will get AC now ### Re: 11664 - Langton's Ant

Posted: Thu Sep 17, 2009 3:51 am
Thanks jurajz!

I changed my function to:

Code: Select all

``````string div2(const string& s) {
const int SIZE = s.size();
const int TWO = 2;
string r;
int ten = 0;
for(int i = 0; i < SIZE; ++i) {
int digit = (s[i] - '0') + ten;
if(digit % TWO == 0) {
r += (digit / TWO) + '0';
} else {
if(digit != 1) {
r += (digit / TWO) + '0';
} else if(i != 0 || SIZE == 1){
r += '0';
}
}
ten = (digit % TWO == 0) ? 0 : 10;
}
return r;
}``````
The test cases seem OK but I still get WA.

I need to re-check all little details...

### Re: 11664 - Langton's Ant

Posted: Sun Oct 25, 2009 6:52 pm
Hello.
forgive my poor english.
i has resolv the langtons ant problem, but i cannot get AC, i get TLE.
i convert the string in binary with toString() method of BigInteger class, this have any problem??
how you resolv this problem.
thanks.