How to resolve the algorithm Langton's ant step by step in the CoffeeScript programming language

Published on 12 May 2024 09:40 PM
#Coffeescript

How to resolve the algorithm Langton's ant step by step in the CoffeeScript programming language

Table of Contents

Problem Statement

Langton's ant is a cellular automaton that models an ant sitting on a plane of cells, all of which are white initially, the ant facing in one of four directions. Each cell can either be black or white. The ant moves according to the color of the cell it is currently sitting in, with the following rules: This rather simple ruleset leads to an initially chaotic movement pattern, and after about 10000 steps, a cycle appears where the ant moves steadily away from the starting location in a diagonal corridor about 10 cells wide.
Conceptually the ant can then walk infinitely far away.

Start the ant near the center of a 100x100 field of cells, which is about big enough to contain the initial chaotic part of the movement. Follow the movement rules for the ant, terminate when it moves out of the region, and show the cell colors it leaves behind.

The problem has received some analysis; for more details, please take a look at the Wikipedia article   (a link is below)..

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Langton's ant step by step in the CoffeeScript programming language

Source code in the coffeescript programming language

class Ant
  constructor: (@world) ->
    @location = [0, 0]
    @direction = 'E'
    
  move: =>
    [x, y] = @location
    if @world.is_set x, y
      @world.unset x, y
      @direction = Directions.left @direction
    else
      @world.set x, y
      @direction = Directions.right @direction
    @location = Directions.forward(x, y, @direction)

# Model a theoretically infinite 2D world with a hash, allowing squares
# to be black or white (independent of any ants.)
class BlackWhiteWorld
  constructor: ->
    @bits = {}
    
  set: (x, y) ->
    @bits["#{x},#{y}"] = true
    
  unset: (x, y) ->
    delete @bits["#{x},#{y}"]
    
  is_set: (x, y) ->
    @bits["#{x},#{y}"]

  draw: ->
    # Most of this code just involves finding the extent of the world.
    # Always include the origin, even if it's not set.
    @min_x = @max_x = @min_y = @max_y = 0
    for key of @bits
      [xx, yy] = (coord for coord in key.split ',')
      x = parseInt xx
      y = parseInt yy
      @min_x = x if x < @min_x
      @max_x = x if x > @max_x
      @min_y = y if y < @min_y
      @max_y = y if y > @max_y
    console.log "top left: #{@min_x}, #{@max_y}, bottom right: #{@max_x}, #{@min_y}"
    for y in [@max_y..@min_y] by -1
      s = ''
      for x in [@min_x..@max_x]
        if @bits["#{x},#{y}"]
          s += '#'
        else
          s += '_'
      console.log s

# Simple code for directions, independent of ants.
Directions =
  left: (dir) ->
    return 'W' if dir == 'N'
    return 'S' if dir == 'W'
    return 'E' if dir == 'S'
    'N'
  
  right: (dir) ->
    return 'E' if dir == 'N'
    return 'S' if dir == 'E'
    return 'W' if dir == 'S'
    'N'
    
  forward: (x, y, dir) ->
    return [x, y+1] if dir == 'N'
    return [x, y-1] if dir == 'S'
    return [x+1, y] if dir == 'E'
    return [x-1, y] if dir == 'W'


world = new BlackWhiteWorld()
ant = new Ant(world)
for i in [1..11500]
  ant.move()
console.log "Ant is at #{ant.location}, direction #{ant.direction}"
world.draw()


> coffee langstons_ant.coffee 
Ant is at -24,46, direction W
top left: -25, 47, bottom right: 22, -29
_##__##_________________________________________
##_#####________________________________________
#____##_#_______________________________________
____#_#_##______________________________________
_####_###_#_____________________________________
_#####_#__##____________________________________
__#___##_##_#___________________________________
___###___#__##__________________________________
____#___##_##_#_________________________________
_____###___#__##________________________________
______#___##_##_#_______________________________
_______###___#__##______________________________
________#___##_##_#_____________________________
_________###___#__##____________________________
__________#___##_##_#___________________________
___________###___#__##__________________________
____________#___##_##_#_________________________
_____________###___#__##________________________
______________#___##_##_#_______________________
_______________###___#__##______________________
________________#___##_##_#_____________________
_________________###___#__##____________________
__________________#___##_##_#___________________
___________________###___#__##__________________
____________________#___##_##_#_________________
_____________________###___#__##________________
______________________#___##_##_#_______________
_______________________###___#__##______________
________________________#___##_##_#__##_________
_________________________###___#__##__##________
__________________________#___##_##__##___#_____
____________________####___###___#___#__###_____
___________________#____#___#___##_####___#_____
__________________###____#___#_#______#_##_#____
__________________###____#_##_____#_##__#_##____
___________________#____#___##_#_#_____##_______
___________________#_#______#_#####__#___#______
__________________#___#####__________##_######__
__________________###__##__#_##_#_#_#___##_#_##_
________________##__#_#######_#___#__###____##_#
_______________#__#__######_##___#__#_##___#___#
______________#____#_#_##_#__######_#######___#_
______________#_####_##_#_####____##__##_#_##_#_
_______________#____####___#__#_######_##____###
__________________#___#_##_#_###_#__##__##___###
_____________________#######____#__##_##_#_____#
_____________####__##_##__####_##_##_##__#_____#
____________#____#_#___###_##_###____#_####____#
___________###_______###_#_#_#####____#_#______#
___________#_#___###_####_##_#___##_###_##_____#
_________________##_##__####____####_#_#_#_____#
____________#____#__##___###__###_____###______#
____________##___##_###_####__#______###___##__#
____________##_#_####_____#___#__#_##_###_##___#
___________####_##___##_####__#_#__#__#__###___#
___________#_##_###__#_#_##_#_#_____#_#_____#_#_
_______________#_#__#____##_##__#_#__###_##_____
_______________##_#____#__#####_#____#____#__#_#
______________#_##_#__#____##_##_#__###______###
____________#_#___#__#__#__#__###___##__##____#_
___________###_#_#####_######_###_#######_#_##__
___________#_#_#____#####___##__#####_#####_____
_____________#__##___#______#__#_##__###_###____
__________####___#####_#########___#_#__________
_____##____#__#_____###_#_#___#_###__###________
____#__#__####_##___###_##___###_##_____##______
___###____#_##_#_#####___#____#__#__##_###______
___#_#####_#_#___##__##_____#____#___#__#_______
_______######_####__##_#___#__##__#_#_##________
_____##______#_###_##__####___#___###___________
______#__#_#####__#___#_##___#__#__#____________
______##_###_#######_____#_____#_##_____________
_____#_#__##_##______#___##____#________________
____#__#_####________###__##__#_________________
____#_##_###____________##__##__________________
_____##_________________________________________
______##________________________________________

You may also check:How to resolve the algorithm Short-circuit evaluation step by step in the Perl programming language
You may also check:How to resolve the algorithm Roman numerals/Encode step by step in the Fortran programming language
You may also check:How to resolve the algorithm Two's complement step by step in the Forth programming language
You may also check:How to resolve the algorithm Palindrome detection step by step in the k programming language
You may also check:How to resolve the algorithm Delete a file step by step in the Fortran programming language