11664 - Langton's Ant

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

Moderator: Board moderators

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

11664 - Langton's Ant

Post by Igor9669 » 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?

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

Re: 11664 - Langton's Ant

Post by Chimed » Sun Sep 06, 2009 10:48 pm

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

Post by Igor9669 » 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.......
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

Post by jurajz » 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. :)

User avatar
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 11664 - Langton's Ant

Post by tryit1 » Mon Sep 07, 2009 3:46 pm

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

Post by Igor9669 » 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! :D

User avatar
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 11664 - Langton's Ant

Post by tryit1 » 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";
}

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

Re: 11664 - Langton's Ant

Post by slxst » 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;
}

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

Re: 11664 - Langton's Ant

Post by jurajz » 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 :)

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

Re: 11664 - Langton's Ant

Post by slxst » 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...

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

Re: 11664 - Langton's Ant

Post by jochy » 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.

Post Reply

Return to “Volume 116 (11600-11699)”