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

Published on 12 May 2024 09:40 PM
#Racket

How to resolve the algorithm Langton's ant step by step in the Racket 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 Racket programming language

Source code in the racket programming language

#lang racket

;; contracts allow us to describe expected behaviour of funcitons
(define direction/c (or/c 'u 'r 'l 'd))
(define turn/c (-> direction/c direction/c))
(define grid/c (hash/c integer? (hash/c integer? boolean?)))
(define-struct/contract ant ([d direction/c] [x integer?] [y integer?]))

(define/contract (turn-right dir) turn/c
  (case dir ((u) 'r) ((d) 'l) ((r) 'd) ((l) 'u)))

(define/contract (turn-left dir) turn/c
  (case dir ((u) 'l) ((d) 'r) ((r) 'u) ((l) 'd)))

(define/contract (move d x y)
  (-> direction/c integer? integer? (list/c direction/c integer? integer?))
  (list
   d
   (+ x (case d ((l) -1) ((r) 1) (else 0)))
   (+ y (case d ((u) -1) ((d) 1) (else 0)))))


(define/contract (move-ant d a) (-> direction/c ant? ant?)
  (apply make-ant (move d (ant-x a) (ant-y a))))

(define/contract (langton a grid) (-> ant? grid/c grid/c)
  (let ((ax (ant-x a)) (ay (ant-y a)))
    (if (and (<= 1 ax 100) (<= 1 ay 100))
        (let* ((grid-row (hash-ref grid ay hash))
               (cell-black? (hash-ref grid-row ax #f)))
          (langton
           (move-ant ((if cell-black? turn-left turn-right) (ant-d a)) a)
           (hash-set grid ay (hash-set grid-row ax (not cell-black?)))))
        grid)))

(define/contract (show-grid/text grid) (-> grid/c void?)
  (for* ; for* allows us to refer to y in rw
      ((y (in-range 1 101))
       (rw (in-value (hash-ref grid y #f)))
       #:when rw        ; if there is no row, the ant never visisted it
       #:when (newline) ; when can be used simply for its side effect
       (x (in-range 1 101)))
    (case (hash-ref rw x #\?)
      ((#\?) (display #\space)) ; distingush between "ant-visited white" vs. pure white
      ((#f)  (display #\:))     ; little anty footprints left
      ((#t)  (display #\#)))))


(show-grid/text (langton (make-ant 'u 50 50) (hash)))

(require 2htdp/image)
(define/contract (show-grid/png grid) (-> grid/c image?)
  (for*/fold
      ((scn (empty-scene 408 408)))
       ((y (in-range 1 101))
       (rw (in-value (hash-ref grid y #f)))
       #:when rw        ; if there is no row, the ant never visisted it
       (x (in-range 1 101)))
    (case (hash-ref rw x #\?)
      ((#\?) scn) ; distingush between "ant-visited white" vs. pure white
      ((#f)  (place-image (circle 2 "outline" "gray") (* x 4) (* y 4) scn))     ; little anty footprints left
      ((#t)  (place-image (circle 2 "solid" "black")  (* x 4) (* y 4) scn)))))
(show-grid/png (langton (make-ant 'u 50 50) (hash)))

You may also check:How to resolve the algorithm Cuban primes step by step in the Go programming language
You may also check:How to resolve the algorithm Sieve of Eratosthenes step by step in the Oberon-2 programming language
You may also check:How to resolve the algorithm 21 game step by step in the R programming language
You may also check:How to resolve the algorithm Hello world/Newline omission step by step in the Web 68 programming language
You may also check:How to resolve the algorithm Find limit of recursion step by step in the BASIC programming language