Commits

Anonymous committed d3df0b1 Draft

Initial import of Jaccia[ta] version 1.0 revision 2009.0411.

Comments (0)

Files changed (9)

+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/2002/REC-xhtml1-20020801/DTD/xhtml1-strict.dtd">
+<html xmlns="http://www.w3.org/1999/xhtml" lang="en">
+<head>
+<title>The Jaccia and Jacciata Cellular Automata</title>
+</head>
+
+<h1>The Jaccia and Jacciata Cellular Automata</h1>
+
+<h2>Overview</h2>
+
+<p><dfn>Jaccia</dfn> and <dfn>Jacciata</dfn> are cellular automata inspired by the
+<a class="external" href="http://www.riken.go.jp/lab-www/frontier-div/NEWSLETTER/feb2001/ameboid_e.htm">Announcement
+of Scientific Proof that Slime Molds are Intelligent Maze Solvers</a>.</p>
+
+<p>Basically, the slime mold solves the maze by:</p>
+<ul>
+<li>initially being everywhere in the maze</li>
+<li>there being food at the entrance and exit of the maze</li>
+<li>minimizing its surface area by retreating from anywhere it can't get food.</li>
+</ul>
+
+<p>Jaccia operates the same way.  In the Jaccia automaton, slime cells survive if they have
+immediate neighbours in at least two cardinal directions that provide sustenance, i.e. are
+either food or other slime cells.  The result is the same: paths of slime cells that lead down
+dead ends have one end which provides no sustenance and dies off.  Eventually, only paths
+of slime cells that reach from food to food (or uninterrupted circular paths of slime cells)
+remain.  Jacciata is a more involved automaton which finds only the shortest path.</p>
+
+<h2>Properties</h2>
+
+<p>Jaccia has the property that, when started from this condition (entire maze filled
+with slime cells), the automaton will eventually reach a fixed point (steady state) which
+contains all possible paths from food to food.</p>
+
+<p>Jacciata is similar, but has the property that when it reaches a fixed point, it will contain
+the <em>shortest</em> path from food to food, if such a path exists and is unique.  If no
+such path exists, or is not unique, the result is undefined.  It is otherwise similar to Jaccia.</p>
+
+<p>The behaviour of both automata is also undefined if the slime configurations are not orthogonal
+(that is, if there are any diagonal slime paths.)</p>
+
+<h2>Definition</h2>
+
+<p>Both Jaccia and Jacciata are defined in ALPACA v0.94.  Jaccia is defined in
+the file <code>jaccia.alp</code> and Jacciata in <code>jacciata.alp</code>.
+The ALPACA definition is authoritative; what is given here is merely advisory.</p>
+
+<p>Both automata use basically the same set of symbols.  An initial Jaccia playfield
+generally serves as an initial Jacciata playfield with the same kind of solution.</p>
+
+<ul>
+<li><code>&nbsp;</code> - empty space</li>
+<li><code>#</code> - wall (purely decorative)</li>
+<li><code>%</code> - slime mold</li>
+<li><code>F</code> - food</li>
+<li><code>S</code> - "start" food (needed in Jacciata, optional in Jaccia)</li>
+<li><code>-</code> - exploratory head (Jacciata only)</li>
+<li><code>?</code> - exploratory body (Jacciata only)</li>
+<li><code>@</code> - solved (Jacciata only)</li>
+</ul>
+
+<h2>Discussion</h2>
+
+<p>Jacciata's definition is not very elegant, especially when compared to Jaccia.  In order for it to work, the
+two sources of food need to be labelled differently (S and F), there needs to be a "head" of
+an exploratory shoot that looks for solutions, and so on.  It could probably be made more elegant with
+some work.</p>
+
+<p>The definition of these automata in ALPACA suggests some
+possible improvements to that meta-language, particularly the definition of neighbourhoods
+different from the assumed von Neumann neighbourhood, and their use in the count
+operator.</p>
+
+<p>Happy intelligence!  Such as it is.
+<br/>Chris Pressey
+<br/>April 11, 2009
+<br/>Bellevue, WA</p>
+
+</body>
+</html>
+####S####
+#%%%%%%%#
+#%#####%#
+#%#%#%#%#
+#%#%#%#%#
+#%%%%%%%#
+####F####
+        F  
+ %%%%%%%%% 
+ %   %   % 
+ % % %%% % 
+ % % % %   
+ %%% % % % 
+     % % % 
+ % %%% %%% 
+ % %   %   
+ %%% %%%%% 
+         F 
+########S##
+#%%%%%%%%%#
+#%###%###%#
+#%#%#%%%#%#
+#%#%#%#%###
+#%%%#%#%#%#
+#####%#%#%#
+#%#%%%#%%%#
+#%#%###%###
+#%%%#%%%%%#
+#########F#
+####S####
+#%%%%%%%#
+#%#####%#
+#%#%%%#%#
+#%#%#%#%#
+#%%%#%%%#
+##F######
+#!/usr/bin/perl
+#  - automatically generated from  by:
+# alpaca.pl v0.93
+# http://catseye.webhop.net/projects/alpaca/
+######################################################
+
+use Alpaca qw(true false guess
+	      adjacent_state adjacent_class
+	      load_playfield display_playfield process_playfield);
+
+sub SustainerClassRules {
+  return 0
+ };
+
+sub SpaceStateRules {
+  return 'Space'
+ };
+
+sub WallStateRules {
+  return 'Wall'
+ };
+
+sub FoodStateRules {
+  return SustainerClassRules() || 'Food'
+ };
+
+sub Food2StateRules {
+  return SustainerClassRules() || 'Food2'
+ };
+
+sub SlimeStateRules {
+  return 'Space' if ((not ((SustainerClassMember($Playfield->[$x][$y-1]) and SustainerClassMember($Playfield->[$x+1][$y])) or (SustainerClassMember($Playfield->[$x][$y-1]) and SustainerClassMember($Playfield->[$x][$y+1])) or (SustainerClassMember($Playfield->[$x][$y-1]) and SustainerClassMember($Playfield->[$x-1][$y])) or (SustainerClassMember($Playfield->[$x+1][$y]) and SustainerClassMember($Playfield->[$x][$y+1])) or (SustainerClassMember($Playfield->[$x+1][$y]) and SustainerClassMember($Playfield->[$x-1][$y])) or (SustainerClassMember($Playfield->[$x][$y+1]) and SustainerClassMember($Playfield->[$x-1][$y])))));
+  return SustainerClassRules() || 'Slime'
+ };
+
+sub SustainerClassMember {
+  return $_[0] eq 'Food' ||
+         $_[0] eq 'Food2' ||
+         $_[0] eq 'Slime' ||
+         0
+};
+
+$Appearance = {
+  'Food' => 'F',
+  'Food2' => 'S',
+  'Slime' => '%',
+  'Space' => ' ',
+  'Wall' => '#',
+
+};
+
+$InputCodec = {
+  'F' => 'Food',
+  'S' => 'Food2',
+  '%' => 'Slime',
+  ' ' => 'Space',
+  '#' => 'Wall',
+
+};
+
+$StateRule = {
+  'Food' => \&main::FoodStateRules,
+  'Food2' => \&main::Food2StateRules,
+  'Slime' => \&main::SlimeStateRules,
+  'Space' => \&main::SpaceStateRules,
+  'Wall' => \&main::WallStateRules,
+
+};
+
+load_playfield($ARGV[0]);
+
+display_playfield();
+
+while (!$done)
+{
+  process_playfield();
+  display_playfield();
+}
+
+exit(0);
+
+### END ###

script/jacciata.pl

+#!/usr/bin/perl
+#  - automatically generated from  by:
+# alpaca.pl v0.93
+# http://catseye.webhop.net/projects/alpaca/
+######################################################
+
+use Alpaca qw(true false guess
+	      adjacent_state adjacent_class
+	      load_playfield display_playfield process_playfield);
+
+sub StarterClassRules {
+  return 0
+ };
+
+sub SustainerClassRules {
+  return 0
+ };
+
+sub SassyClassRules {
+  return 0
+ };
+
+sub SolutionClassRules {
+  return 0
+ };
+
+sub SpaceStateRules {
+  return 'Space'
+ };
+
+sub WallStateRules {
+  return 'Wall'
+ };
+
+sub SlimeStateRules {
+  return 'Space' if ((not ((SustainerClassMember($Playfield->[$x][$y-1]) and SustainerClassMember($Playfield->[$x+1][$y])) or (SustainerClassMember($Playfield->[$x][$y-1]) and SustainerClassMember($Playfield->[$x][$y+1])) or (SustainerClassMember($Playfield->[$x][$y-1]) and SustainerClassMember($Playfield->[$x-1][$y])) or (SustainerClassMember($Playfield->[$x+1][$y]) and SustainerClassMember($Playfield->[$x][$y+1])) or (SustainerClassMember($Playfield->[$x+1][$y]) and SustainerClassMember($Playfield->[$x-1][$y])) or (SustainerClassMember($Playfield->[$x][$y+1]) and SustainerClassMember($Playfield->[$x-1][$y])))) or (($Playfield->[$x][$y-1] eq 'Head' and $Playfield->[$x+1][$y] eq 'Head') or ($Playfield->[$x][$y-1] eq 'Head' and $Playfield->[$x][$y+1] eq 'Head') or ($Playfield->[$x][$y-1] eq 'Head' and $Playfield->[$x-1][$y] eq 'Head') or ($Playfield->[$x+1][$y] eq 'Head' and $Playfield->[$x][$y+1] eq 'Head') or ($Playfield->[$x+1][$y] eq 'Head' and $Playfield->[$x-1][$y] eq 'Head') or ($Playfield->[$x][$y+1] eq 'Head' and $Playfield->[$x-1][$y] eq 'Head')));
+  return 'Head' if ((StarterClassMember($Playfield->[$x][$y+1]) or StarterClassMember($Playfield->[$x][$y-1]) or StarterClassMember($Playfield->[$x+1][$y]) or StarterClassMember($Playfield->[$x-1][$y])));
+  return SustainerClassRules() || 'Slime'
+ };
+
+sub HeadStateRules {
+  return 'Body' if (1);
+  return StarterClassRules() || SustainerClassRules() || SassyClassRules() || 'Head'
+ };
+
+sub BodyStateRules {
+  return 'Solved' if ((SolutionClassMember($Playfield->[$x][$y+1]) or SolutionClassMember($Playfield->[$x][$y-1]) or SolutionClassMember($Playfield->[$x+1][$y]) or SolutionClassMember($Playfield->[$x-1][$y])));
+  return 'Space' if ((not ((SassyClassMember($Playfield->[$x][$y-1]) and SassyClassMember($Playfield->[$x+1][$y])) or (SassyClassMember($Playfield->[$x][$y-1]) and SassyClassMember($Playfield->[$x][$y+1])) or (SassyClassMember($Playfield->[$x][$y-1]) and SassyClassMember($Playfield->[$x-1][$y])) or (SassyClassMember($Playfield->[$x+1][$y]) and SassyClassMember($Playfield->[$x][$y+1])) or (SassyClassMember($Playfield->[$x+1][$y]) and SassyClassMember($Playfield->[$x-1][$y])) or (SassyClassMember($Playfield->[$x][$y+1]) and SassyClassMember($Playfield->[$x-1][$y])))));
+  return StarterClassRules() || SassyClassRules() || 'Body'
+ };
+
+sub SolvedStateRules {
+  return 'Space' if ((not ((SassyClassMember($Playfield->[$x][$y-1]) and SassyClassMember($Playfield->[$x+1][$y])) or (SassyClassMember($Playfield->[$x][$y-1]) and SassyClassMember($Playfield->[$x][$y+1])) or (SassyClassMember($Playfield->[$x][$y-1]) and SassyClassMember($Playfield->[$x-1][$y])) or (SassyClassMember($Playfield->[$x+1][$y]) and SassyClassMember($Playfield->[$x][$y+1])) or (SassyClassMember($Playfield->[$x+1][$y]) and SassyClassMember($Playfield->[$x-1][$y])) or (SassyClassMember($Playfield->[$x][$y+1]) and SassyClassMember($Playfield->[$x-1][$y])))));
+  return SassyClassRules() || SolutionClassRules() || 'Solved'
+ };
+
+sub StartStateRules {
+  return StarterClassRules() || SustainerClassRules() || SassyClassRules() || 'Start'
+ };
+
+sub FinishStateRules {
+  return SustainerClassRules() || SassyClassRules() || SolutionClassRules() || 'Finish'
+ };
+
+sub SassyClassMember {
+  return $_[0] eq 'Head' ||
+         $_[0] eq 'Body' ||
+         $_[0] eq 'Solved' ||
+         $_[0] eq 'Start' ||
+         $_[0] eq 'Finish' ||
+         0
+};
+
+sub SolutionClassMember {
+  return $_[0] eq 'Solved' ||
+         $_[0] eq 'Finish' ||
+         0
+};
+
+sub StarterClassMember {
+  return $_[0] eq 'Head' ||
+         $_[0] eq 'Body' ||
+         $_[0] eq 'Start' ||
+         0
+};
+
+sub SustainerClassMember {
+  return $_[0] eq 'Slime' ||
+         $_[0] eq 'Head' ||
+         $_[0] eq 'Start' ||
+         $_[0] eq 'Finish' ||
+         0
+};
+
+$Appearance = {
+  'Body' => '?',
+  'Finish' => 'F',
+  'Head' => '-',
+  'Slime' => '%',
+  'Solved' => '@',
+  'Space' => ' ',
+  'Start' => 'S',
+  'Wall' => '#',
+
+};
+
+$InputCodec = {
+  '?' => 'Body',
+  'F' => 'Finish',
+  '-' => 'Head',
+  '%' => 'Slime',
+  '@' => 'Solved',
+  ' ' => 'Space',
+  'S' => 'Start',
+  '#' => 'Wall',
+
+};
+
+$StateRule = {
+  'Body' => \&main::BodyStateRules,
+  'Finish' => \&main::FinishStateRules,
+  'Head' => \&main::HeadStateRules,
+  'Slime' => \&main::SlimeStateRules,
+  'Solved' => \&main::SolvedStateRules,
+  'Space' => \&main::SpaceStateRules,
+  'Start' => \&main::StartStateRules,
+  'Wall' => \&main::WallStateRules,
+
+};
+
+load_playfield($ARGV[0]);
+
+display_playfield();
+
+while (!$done)
+{
+  process_playfield();
+  display_playfield();
+}
+
+exit(0);
+
+### END ###
+/*
+ * The Jaccia automaton, expressed in ALPACA.
+ * Inspired by the Scientific Announcement that
+ *   Slime Molds are Intelligent Maze-Solvers.
+ * April 11 2009, Chris Pressey, Cat's Eye Technologies.
+ */
+
+class Sustainer;
+
+state Space " ";
+state Wall  "#";  /* purely decorative */
+state Food  "F"
+   is Sustainer;
+state Food2 "S"
+   is Sustainer;
+state Slime "%"
+   is Sustainer
+   to Space when not ((^ is Sustainer and > is Sustainer) or
+                      (^ is Sustainer and v is Sustainer) or
+                      (^ is Sustainer and < is Sustainer) or
+                      (> is Sustainer and v is Sustainer) or
+                      (> is Sustainer and < is Sustainer) or
+                      (v is Sustainer and < is Sustainer)).
+/*
+ * The Jacciata automaton, expressed in ALPACA.
+ * Inspired by Jaccia.
+ * April 11 2009, Chris Pressey, Cat's Eye Technologies.
+ */
+
+class Starter;
+class Sustainer;
+class Sassy;
+class Solution;
+
+state Space " ";
+state Wall  "#";  /* purely decorative */
+
+/*
+ * Slime stays alive so long as there is sustenance (food, or more slime, or the
+ * head of an exploratory shoot) on at least two sides.  Slime turns into an
+ * exploratory head if there is adjacent starter material.
+ */
+state Slime "%"
+   is Sustainer
+   to Space when not ((^ is Sustainer and > is Sustainer) or
+                      (^ is Sustainer and v is Sustainer) or
+                      (^ is Sustainer and < is Sustainer) or
+                      (> is Sustainer and v is Sustainer) or
+                      (> is Sustainer and < is Sustainer) or
+                      (v is Sustainer and < is Sustainer))
+                  or /* this part lets conflicts be resolved */
+                     ((^ Head and > Head) or
+                      (^ Head and v Head) or
+                      (^ Head and < Head) or
+                      (> Head and v Head) or
+                      (> Head and < Head) or
+                      (v Head and < Head)),
+   to Head when (v is Starter or ^ is Starter or > is Starter or < is Starter);
+
+state Head "-"
+   is Starter
+   is Sustainer
+   is Sassy
+   to Body;
+
+/*
+ * Body does not provide sustenance for slime.
+ * Body becomes solved cells when adjacent to a solution.
+ * Body stays alive so long as there is sassy on at least two sides;
+ * sassy is head, more body, or food, or a solved cell.
+ */
+state Body "?"
+   is Starter
+   is Sassy
+   to Solved when (v is Solution or ^ is Solution or > is Solution or < is Solution),
+   to Space when not ((^ is Sassy and > is Sassy) or
+                      (^ is Sassy and v is Sassy) or
+                      (^ is Sassy and < is Sassy) or
+                      (> is Sassy and v is Sassy) or
+                      (> is Sassy and < is Sassy) or
+                      (v is Sassy and < is Sassy));
+
+/*
+ * Solved cells survive on the same rules as body cells.
+ */
+state Solved "@"
+   is Sassy
+   is Solution
+   to Space when not ((^ is Sassy and > is Sassy) or
+                      (^ is Sassy and v is Sassy) or
+                      (^ is Sassy and < is Sassy) or
+                      (> is Sassy and v is Sassy) or
+                      (> is Sassy and < is Sassy) or
+                      (v is Sassy and < is Sassy));
+
+state Start "S"
+   is Starter
+   is Sustainer
+   is Sassy;
+state Finish "F"
+   is Sustainer
+   is Sassy
+   is Solution.
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.