Page 1 of 1

11664 - Langton's Ant

Posted: Sun Sep 06, 2009 5:05 pm
by Igor9669
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
by Chimed
from cell(y,x)
north is y++

Re: 11664 - Langton's Ant

Posted: Mon Sep 07, 2009 8:48 am
by Igor9669
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
by jurajz
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
by tryit1
removed stringstream to get AC. stringstream is very slow. Got TLE

Re: 11664 - Langton's Ant

Posted: Tue Sep 08, 2009 8:40 am
by Igor9669
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! :D

Re: 11664 - Langton's Ant

Posted: Tue Sep 08, 2009 2:27 pm
by tryit1
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
by slxst
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
by jurajz
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
by slxst
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
by jochy
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.