Sunday, September 11, 2011

Exploring Common Lisp: Project Euler Number 8 in Common Lisp (Neophyte Version)

There isn't really much I can add about this example. The goal is to find the largest product of any consecutive digits given a 1000 digit number. I implemented the first approach that came to mind; I went with a large loop to iterate through the 1000 digits and then an inner loop to extract that digits we are going to use in our calculation. The key built-in lisp functions are "loop" and "reduce". If you are not used to a lisp programming language, a C version of this solution is provided.

;;
;; euler8.lisp (modify to find the "correct" solution)
;; Find the greatest product of five ;; consecutive digits in the 1000-digit number;;
;; [1] http://www.unixuser.org/~euske/doc/cl/loop.html
(defparameter *large-num* 
"73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843")

(defun find-great-product ()
  "Use reduce to find the product of a list of 5 digits out of the
 larger 1000 digit number"
  (let ((n (length *large-num*)) (m 0))
    (loop for i from 0 to (- n 5)
          for x = (let ((vals (loop for z from i to (+ i 4)
                                    for b = (digit-char-p (char *large-num* z))
                                    collect (if b b 1))))
                    (reduce #'* vals))
          do (when (> x m) (setf m x)))
    m))
(defun main ()
  (format t "Start~%")
  (print (find-great-product))
  (format t "Done~%"))
(main)

Saturday, September 10, 2011

Revisiting Self Replicating Molecules in an Artificial Chemistry Automaton

Introduction

  This blog entry describes an artificial chemistry simulation implemented through a cellular automaton. We show that basic rules can be used to produce complex behavior through simulated artificial chemical reactions. The chemical simulation exists on a fixed size two dimensional grid of cells.  Each active cell is represented by an artificial atom element, these atoms may collide with other atoms to produce a chemical reaction.  Strong chemical bonds will form if the chemical reaction is allowed by system.  Clusters of strong bonded atoms form molecule strings.   We show that self replicating molecule string patterns emerge from the artificial simulation.  This analysis is based on Timothy Hutton's artificial chemistry model from Squirm3.  It it is a basic model but a necessary step for analyzing and recreating similar natural systems.  Self-replication and self-organization is fundamental to all biological life.  Engineers use scientific knowledge to solve real-world problems.  Scientists study and experiment with nature and the Universe in order to add their research to the scientific knowledge base.  This small experiment attempts to simulate real chemical reactions using simple artificial physics.

  Chemical reactions occur when two atom cells collide.  In the simulated physical environment, this occurs when an atom cell sits next to another atom cell.  The chemical reaction rules are tested between the two atoms, if the rules allow the reaction then a bond forms.

Figure 1: Chemical Reactions over time



   The atom cell has a type of 'a', 'b', 'c', 'd', 'e', 'f'.  Each atom has a state of '0'-'8'.  Three chemical reactions typically occurred but eight were allowed.  During a chemical reaction, x3 for atom one and y6 for atom two with an output x2.  X and Y are variable substitutions for the atoms, 'a', 'b', 'c', 'd', 'e', 'f'.


Figure 2 : Squirm 3 Artificial Chemistry Java Application.  Clumps of bonded atoms represent molecules.

Figure 3 : Number of Bonds vs No Bond.  Over time, the bonded atoms will fill the screen.   Some atoms that don't have bonds still persist but with less frequency

Figure 4 : Total bonds over time



System Description

The simulation consists of a 2D grid, fifty cells in height and fifty cells in width.  A cell grid is inactive or active, the active grid cell may contain an atom element represented by a  'a', 'b', 'c', 'd', 'e', 'f' type and a 0-8 state,  e8 represents atom cell type 'e' with state 8.  Molecules consist of clumps of atoms.  We only use the atom type to chain molecule strings, cfab is a common molecule that self replicates in the simulation.

Establishing a chemical reaction, example reaction cell1=e8 + cell2=e0 creates cells e0 and e4 and a bond may form
After thousands of iterations, common patterns emerge on the grid.  Common bonded atoms (molecules) survive through out the simulation.



Figure 5 : Common Atoms and Atom State.  Common atom states fill the cell universe.
Figure 6 : Most Common Bonds

Figure 7 : Common Reactions
Source Code

https://github.com/berlinbrown/Squirm3ArtificialChemistry

References

[1] Evolvable Self-Replicating Molecules in an Artificial Chemistry Tim J. Hutton, Fall 2002, Vol. 8, No. 4, Pages 341-356 Posted Online March 11, 2006. (doi:10.1162/106454602321202417) at 2002 Massachusetts Institute of Technology

Date: 9/10/2011 -- Berlin Brown