Langton’s ant Java solution. Java and Servlet version

This is my implementation of the Langton’s ant problem. It’s one of the Project Euler problems.(https://projecteuler.net/problem=349).

Problem statement:

An ant moves on a regular grid of squares that are coloured either black or white.
The ant is always oriented in one of the cardinal directions (left, right, up or down) and moves from square to adjacent square according to the following rules:
– if it is on a black square, it flips the color of the square to white, rotates 90 degrees counterclockwise and moves forward one square.
– if it is on a white square, it flips the color of the square to black, rotates 90 degrees clockwise and moves forward one square.

Starting with a grid that is entirely white, how many squares are black after 1018 moves of the ant?

My solution:

Drawing1.jpg

I tried to solve this problem by brute forcing, but this approach won’t work, because you need to much memory just for 10^8 steps and it will too long to get the result.

I observed that after around step 10000 the ant enters the so called highway, meaning it’s steps will be repeated every 104 steps, also this 104 steps will yield 12 black dots. Meaning that we can simply do this (10^18 – 10000)/104 * 12 . This should yield the correct answer, but this is slightly wrong. Because the final step (which is 10^18) may not be perfectly divisible by 104((10^18 – 10000)%104 != 0 in most of the cases). Therefore we need more accurate calculation. For this I decided to count how many black dots are there until step 10000 then divide the remaing steps by 104. First 10000 yields 720 black dots and the remainging we can calculate, however there will be some left over of steps for them we need to resume the calculation from the place where it stop at step 10000.

You can find the codes in my GitHub: https://github.com/NyghmetElemesov/solved-problems

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s