Trees

A. A. Gill used to say that the little secret of TV was that it was mostly watched by women.

I assume he made an exception for the footie.

The feminisation of everything - "How did it make you feel?" - is evident in factual programs. The Sky at Night is a lost cause, but I was pleased to watch the BBC4 program, "Sword, Musket & Machine Gun", which seemed to be bloke TV.

Arguably, "How did it make you feel?" is rather superfluous.

At any rate, I was watching it avidly while Clare seemed glued to her tablet for once.

---

Weights this morning, lowered saddle on exercise bike (better!), skipped lunch. The Christmas effect has not yet disappeared according to my mirror. Then walked to Morrisons w. Clare to buy new mop bucket.

Waiting for gales and predicted weekend snow.

---

Another Christmas effect - the 2016 Waitrose Christmas Tree has become the 2017 garden tree.

As a bonus, its tub will make a neat wastebin, once the mud's been washed off.

---

Continuing on the subject of trees, my hobbyist AI project continues. I'm writing tree-search functions (bounded depth-first) and continuing to learn oh-so-many Common Lisp features.

The idea is to define a number of different kinds of game-players: random, human-powered, depth-first to some depth, complete generation of game tree + minimax .. for 'Noughts and Crosses'.

Once you have the (rather extensive) apparatus assembled, the tools can be generalised to more ambitious applications.

It has reminded me of the difficulties of programming: large, branching trees are huge sprawling objects, hard to visualise, and recursive operations often intricate. As always, subtle (and not-so-subtle) bugs dominate the ecosystem.

---

Here's my example tree from Wikipedia:

A node (below) is a triple comprising: node name, followed by question mark (may later become the best move) followed by the leaf non-zero score for testing minimax.

((N0 ? 0) (((N11 ? 0) (((N21 ? 0) (((N31 ? 0) (((N41 ? 10) NIL) ((N42 ? 20) NIL))) ((N32 ? 0)
(((N43 ? 5) NIL))))) ((N22 ? 0) (((N33 ? 0) (((N44 ? -10) NIL))))))) ((N12 ? 0)
(((N23 ? 0) (((N34 ? 0) (((N45 ? 7) NIL) ((N46 ? 5) NIL))) ((N35 ? 0) (((N47 ? -20) NIL)))))
 ((N24 ? 0) (((N36 ? 0) (((N48 ? -7) NIL) ((N49 ? -5) NIL)))))))))

Horrible, isn't it?

And here's some code which doesn't work properly 😕 with some debugging print statements.

(defun dl-dfs (tree depth)
   "depth-limited depth-first traversal - create a list of nodes"
   (cond ((equal depth 0) nil)
             ((leafp tree)   (tree-node tree))
             (t       (format t "tree node = ~a" (tree-node tree)) (format t "~%")
                       (cons (tree-node tree)
                                  (dl-dfs-aux (tree-children tree) (1- depth))))
              ))

(defun dl-dfs-aux (tree-list depth)
   (if (null tree-list) nil
                 (cons (dl-dfs (car tree-list) depth)
                          (dl-dfs-aux (cdr tree-list) depth)
)))

---

(dl-dfs T0 5) produces:

tree node = (N0 ? 0)
tree node = (N11 ? 0)
tree node = (N21 ? 0)
tree node = (N31 ? 0)
tree node = (N32 ? 0)
tree node = (N22 ? 0)
tree node = (N33 ? 0)
tree node = (N12 ? 0)
tree node = (N23 ? 0)
tree node = (N34 ? 0)
tree node = (N35 ? 0)
tree node = (N24 ? 0)
tree node = (N36 ? 0)

((N0 ? 0) ((N11 ? 0) ((N21 ? 0) ((N31 ? 0) (N41 ? 10) (N42 ? 20))
((N32 ? 0) (N43 ? 5))) ((N22 ? 0) ((N33 ? 0) (N44 ? -10)))) ((N12 ? 0)
((N23 ? 0) ((N34 ? 0) (N45 ? 7) (N46 ? 5))
((N35 ? 0) (N47 ? -20))) ((N24 ? 0) ((N36 ? 0) (N48 ? -7) (N49 ? -5)))))

I wanted a straightforward list! *

---

* I'll spare you anything else - I have some new ideas for this afternoon. I already realised that the recursion is basically just reiterating the tree structure so the results either have to be flattened or I need to accumulate the nodes in a parameter as I go.

And I noticed the termination condition for depth = 0 is wrong, thank you.

---

Update: Wednesday 11th January 2017 - Here's the right answer.

(defun dl-dfs (tree depth)
  "Depth-limited depth-first traversal - create list of nodes"
  (flatten (dl-dfs1 tree depth)))

(defun dl-dfs1 (tree depth)
  "creates a list of nodes, but nested as a tree - needs to be flattened"
  (cond  ((or (leafp tree) (equal depth 0))  (tree-node tree))
         (t            (cons (tree-node tree)
                             (dl-dfs-aux (tree-children tree) (1- depth))))
         ))

(defun dl-dfs-aux (tree-list depth)
  (if (null tree-list) nil
    (cons (dl-dfs1 (car tree-list) depth)
          (dl-dfs-aux (cdr tree-list) depth)
          )))

(defun flatten (l)
  (cond ((null l)  nil)
        ((atom l) (list l))
        ((not (embedded-listp l)) (list l))
         (t       (append (flatten (car l)) (flatten (cdr l)) ) )
  ))

(defun embedded-listp (l)
   "If the list l contains a list, this returns a true, ie non-nil value"
   (member t (mapcar #'listp l)))

with result as follows: (dl-dfs T0 4)

((N0 ? 0) (N11 ? 0) (N21 ? 0) (N31 ? 0) (N41 ? 10) (N42 ? 20)
 (N32 ? 0) (N43 ? 5) (N22 ? 0) (N33 ? 0) (N44 ? -10) (N12 ? 0)
 (N23 ? 0) (N34 ? 0) (N45 ? 7) (N46 ? 5) (N35 ? 0) (N47 ? -20)
 (N24 ? 0) (N36 ? 0) (N48 ? -7) (N49 ? -5))

You won't care about this at all, but I'm quietly pleased. 😌