## 11664 - Langton's Ant

Moderator: Board moderators

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### 11664 - Langton's Ant

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?

Chimed
New poster
Posts: 12
Joined: Mon Oct 20, 2008 10:37 am

### Re: 11664 - Langton's Ant

from cell(y,x)
north is y++

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11664 - Langton's Ant

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.......
``````
Last edited by Igor9669 on Tue Sep 08, 2009 10:48 am, edited 1 time in total.

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

### Re: 11664 - Langton's Ant

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. tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### Re: 11664 - Langton's Ant

removed stringstream to get AC. stringstream is very slow. Got TLE

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11664 - Langton's Ant

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! tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### Re: 11664 - Langton's Ant

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";
}``````

slxst
New poster
Posts: 23
Joined: Mon Oct 16, 2006 2:18 am

### Re: 11664 - Langton's Ant

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;
}``````

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

### Re: 11664 - Langton's Ant

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 slxst
New poster
Posts: 23
Joined: Mon Oct 16, 2006 2:18 am

### Re: 11664 - Langton's Ant

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

jochy
New poster
Posts: 5
Joined: Sun Oct 25, 2009 6:39 pm

### Re: 11664 - Langton's Ant

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.