Beautifull jumps and falls

Play the puzzle!

The Goal: Given a starting “sentence” (string) reach the goal “sentence” (string) by only applying the rules below.

• x and y represent any character strings and M, U, I represent the actual letters, the arrow may be read as “becomes”.

• For example the first rule can be read: Any string that ends in M becomes M and two times the reminder.

Try it, I will be waiting here :).

Poem

I like writing about where I am,

where I happen to be sitting,

the humidity or the clouds,

the scene outside the window–

a pink tree in bloom,

a neighbor walking his small, nervous dog.

And if I am drinking

a cup of tea at the time

or a small glass of whiskey,

I will find a line to put it on.

My wife hands these poems back to me

with a sigh.

She thinks I ought to be opening up

my aperture to let in

the wild rhododendrons of Ireland,

the sun-blanched stadiums of Rome,

that water clock in Bruges–

the world beyond my inkwell.

I tell her I will try again

and travel back to my desk

where the chair is turned to the window.

I think about the furniture of history.

I consider the globe, the lights of its cities.

I visualize a lion rampant on an iron shield,

a quiet battlefield, a granite monument.

And then–just between you and me–

I take a swallow of cold tea

and in the manner of the ancient Chinese

pick up my thin pen

and write down that bird I hear outside,

the one that sings,

pauses,

then sings again. In the Room of a Thousand Miles By Billy Collins (Picnic Lighting)

So lets talk about the puzzle you just played

It’s based on a simple formal system. When faced with it, you don’t know how to get to the goal (except for the first trivial cases that I put in as a tutorial).

The way most people solve it is by first trying the rules. We first have hunches and try things, the hunches sometimes get better over time and develop into strategies. We start to notice stuff about what we are doing and only then we can really improve towards the goal.

Notice that I use an analogy between getting to a solution and finding a road between 2 points. Do not fret too much about this, any problem can be reformulated as an optimality problem (finding a minimum or a maximum) and any optimal solution can be seen as a road in a n dimensional space (there are actual plots that look like roads for functions of 2 variables). If you are not that into optimality problems you can imagine that any solution that involves testing all the cases is actually walking down the knowledge tree, and testing all cases is the general (avoided) solution to every problem :) .

If you make a computer follow the rules and try every combination (walk every path), there are certain situations where it will run forever and never give you an answer (when the goal is unreachable for example). In this case the knowledge tree has some leafs that need infinite many steps to reach.

Humans make these “Beautiful jumps” into higher hierarchical systems or can “think outside the box” :) and then “fall back” down into the system and apply other, better rules and judgement that we got from the higher hierarchical system. There is some trickery involved: we have this natural notion of higher and lower hierarchical systems when in truth there is no high and low but just different rule systems. This process is called a “strange loop” and was coined by Douglas R Hofstadter. I love his book GEB and recommend it to anybody interested, great for programmers, great for humans in general :) and extremely well written (it is actually given as an example in On Writing Well ). It has recently been translated into romanian so it can be found even in romanian libraries .. yeah.. I know :).

These strange loops are believed (by Hofstadter) to be the basis of consciousness. He implies that consciousness is actually formed of these millions of loops.

I don’t know if the general case is true for all people but the strange loop seems to be part of the way I do things. If you watched the first course recommended in the previous article about artistmachine42, you may have seen that stringed hierarchical systems always do better than non hierarchical AIs, this may as well be because, for example convolution neural networks come close to multiple strange loops. The machine learning effectiveness could be attributed to the big do-small-things -> analyze-small-things-and-update-rules -> do-small-things-better strange loop.

We could go into a materialist view so we can then hope for creating machines that achieve consciousness but this is something I don’t quite care about. I am impartial to this as it’s more of an ethical problem. I am pleased with building better specialized problem solvers so we can then do more of what we love.

Let’s fall back to programming

We will first do the checks for applying the rules as these are really trivial:

function isRule1Valid(){string = $("#nchange1").text();var lastChar = string.charAt(string.length - 1);return (lastChar == "I");}
function isRule2Valid(){string = $("#nchange1").text();var firstChar = string.charAt(0);return (firstChar == "M");}
function isRule3Valid(){return (selectedText == "III");}
function isRule4Valid(){ return (selectedText == "UU");}

Ok so we basically need to select some text, and check what rules we can apply on the text and then create buttons for each rules. When the user will press a button he will apply the transformation. So lets have a look at the transformation functions:

function ApplyRule1()
{
  nchange     = $("#nchange1")
  oldString    = nchange.text()
  stringChange = oldString.substr(0,oldString.length - 1)
  nchange.text(stringChange)
  $("#change").text("I,IU,IU")
  DoAnim("bounceIn")
}

function ApplyRule2()
{
  nchange     = $("#nchange1")
  oldString    = nchange.text()
  stringChange = oldString.substr(1,oldString.length)
  nchange.text("M")
  chg = stringChange+stringChange
  $("#change").text(stringChange+","+chg+","+chg)
  DoAnim("swing")
}

function ApplyRule3()
{
  nchange1     = $("#nchange1")
  nchange2     = $("#nchange2")
  oldString    = nchange1.text()
  offset       = selectedBegin
  x1 = oldString.substr(0,offset);
  y1 = oldString.substr(offset+(""+selectedText).length,oldString.length);
  nchange1.text(x1);
  $("#change").text("III,U,U")
  nchange2.text(y1);
  DoAnim("bounceOutUp")
}


function ApplyRule4()
{
  nchange1     = $("#nchange1")
  nchange2     = $("#nchange2")
  oldString    = $("#nchange1").text()
  offset       = selectedBegin;
  x1 = oldString.substr(0,offset);
  y1 = oldString.substr(offset + (""+selectedText).length,oldString.length);
  nchange1.text(x1);
  $("#change").text("UU,,")
  nchange2.text(y1);
  DoAnim("bounceOutUp")
}

As you can see, the code above is really easy to understand, it just does what the rules say.

Let’s do a high jump

After implementing the first prototype we start to notice patterns and “rules of the rules” and do a more general approach. We now may be able to write a program that outputs another program that can generate variants of the these simple puzzles. We will not output text (even though this method is used all the time in a lot of engineering systems). Scripts that generate code for serializing, deserializing data, descriptor languages for network stubs and so on. We will do this at runtime because I don’t really like writing scripts that output programs.

And back to programming

In this second approach I have a better grasp of the rules for the rules of the system, and do the generalization towards something I believe will be useful. Of course the first prototype could be enough for an application, but the next one handles a bigger class of transformation rules. You can add to the generalization so that it handles even bigger classes of problems (then the rule match becomes something recursive like this “beautiful regexp matching code”) but I think you should do your loops smaller so you get back to reality and test how useful your generalization really is. Finding a balance between being a pragmatic programmer that does not see the bigger picture and rambling lunatic in love with his bad ideeas :) .

//we figure out the difference between static text (one that matches letter by letter) and variable text
// if a letter appears in a rule it can be a variable that holds a string or member of the alphabet
alphabet =['M','I','U']
// we have an array of rules that we use. As you can see we added this layer of indirection
//so we could have any number of rules of the form
// variable-Static-variable variable-Static Static-variable
rules = [
  {start:"xI", end:"xIU"},
  {start:"Mx", end:"Mxx"},
  {start:"xIIIy", end:"xUy"},
  {start:"xUUy", end:"xy"},
]

guiItemsText    = []
selectedText    = ""
selectedBegin   = 0
selectedEnd     = 0

animation_units = 0
// We do some analysis on the rules for easier computations. The most important part is creating a patch
// between start and end rules so we now what is added in general and what is removed and the same.
// We will use this information to play animations on letters
function PrepareRules()
{
    var dmp = new diff_match_patch();
    for(var i = 0; i< rules.length; i++)
    {
        rules[i].diff = dmp.patch_make(rules[i].start,rules[i].end)
        rules[i].isStaticLeft  = IsInAlphabet(rules[i].start[0])
        rules[i].isStaticRight = IsInAlphabet(rules[i].start[rules[i].start.length - 1])
        rules[i].selection = (!rules[i].isStaticRight && !rules[i].isStaticLeft)
        rules[i].valid = false
    }

}
//This is called at the begining of the program
PrepareRules()
//Helper function that checks if a character is inside the alphabet or outside it
function IsInAlphabet(c)
{
  return alphabet.indexOf(c) != -1;
}

//This function is actually used to hold the variables so they can be matched between start and end rules.
//Notice that this can be further developed to solve even bigger classes of problems.
//The biggest improvement that we can make, to unlock some more possibilities is making this recursive for
// variable matching (similar to beautifull code regex matching). I will leave this as an exercise for the
// reader (the reader can then understand why I did not include this :) )

function ApplyStartRule(string, ruleObject)
{
  rulestring   = ruleObject.start

  ruleIdxLeft   = 0
  stringIdxLeft = 0

  ruleIdxRight   = rulestring.length -1
  stringIdxRight = string.length -1

  ruleObject.split = {}

  if(ruleObject.isStaticLeft)
  {
    for(;ruleIdxLeft<rulestring.length && stringIdxLeft < string.length && IsInAlphabet(rulestring[ruleIdxLeft]); stringIdxLeft++,ruleIdxLeft++ )
    {
        if(rulestring[ruleIdxLeft] != string[stringIdxLeft])
        {
          return false
        }
    }
  }

  if(ruleObject.isStaticRight)
  {
    for(;ruleIdxRight>=0 && stringIdxRight >= 0 && IsInAlphabet(rulestring[ruleIdxRight]); stringIdxRight--,ruleIdxRight-- )
    {
        if(rulestring[ruleIdxRight] != string[stringIdxRight])
        {
          return false
        }
    }
  }

  if(ruleObject.isStaticRight || ruleObject.isStaticLeft)
  {
    ruleObject.split[rulestring[ruleIdxRight]] = string.substring(stringIdxLeft, stringIdxRight + 1)
  }
  else
  {
    ruleFixed = rulestring.substring(1,rulestring.length-1)
    indexmiddle = string.indexOf(ruleFixed);
    if(indexmiddle == -1)
      return false
    ruleObject.split[rulestring[0]]                 = string.substring(0, indexmiddle)
    ruleObject.split[rulestring[rulestring.length-1]]= string.substring(indexmiddle + ruleFixed.length, string.length)
  }

  return true
}

And also the transform function

//This function walks the end rule and matches the variables with what we found in the start rule.

//We also play animations of added and removed string parts
 function ApplyEndRule(ruleObject)
 {
   split = ruleObject.split
   rule  = ruleObject.end
   text  = ""
   rulediffs = ruleObject.diff[0].diffs
   prevmode  = 0

   prefix =""
   suffix =""

   if(ruleObject.selection == true)
   {
     fulltext = $("#"+static_text_div).text()
     prefix = fulltext.slice(0,selectedBegin)
     suffix = fulltext.slice(selectedEnd,fulltext.length)
   }

   prefixelement = AddTextSpan("static")
   prefixelement.text(prefix);

   for(var i = 0 ; i<rulediffs.length; i++)
   {
     diffobj = rulediffs[i]
     str     = diffobj[1]
     mode    = diffobj[0] + 1

     var item = ""
     for(var j = 0; j<str.length; j++)
     {
         item = item + ((IsInAlphabet(str[j]))? str[j]: split[str[j]])
     }
     types = [{anim:"bounceOutUp",cname:"dynamic_remove"},{anim:"none",cname:"static"},{anim:"bounceIn",cname:"dynamic_add"}]
     element = AddTextSpan(types[mode].cname)
     if(mode == 2 || mode == 0)
     {
       element.text(item+","+item);
     }
     else
     {
       element.text(item);
     }
     DoAnim(types[mode].anim,element)
   }

   suffixelement = AddTextSpan("static")
   suffixelement.text(suffix);

   $("#"+static_text_div).text("")

 }

Ending

I don’t know how useful this compositional approach is to simulating parts of reality but we can make a lot of games out of this :D . We could have better interfaces like replacing the visuals with colors instead of letters and so on. It’s like a game generator and the produced games could be seen as an one dimensional candy crush type games :D. Actually rule based game generators are discussed in some scientific papers as well as learning parameters for the “funness” of a game. Unfortunately this has not reached the point where humans can generate random fun games without tweaking and thinking about the rules but good efforts (and articles) about this are made here.

You can find the source code in this github repository.

The code is not really smart but I think the two developing steps create a strange loop. Actually even the way we program the first problem includes a strange loop because it involves thinking about the rules and programming in general is creating meta rules to simulate the rules.

I will end this article with 2 Escher paintings

and this picture I printed with artisticmachine42 work :)

Play the game again. Go on, read the poem one more time.