# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1576879931 18000
# Node ID 049e0d632763ede58053bbaad3838cd89c59ae44
# Parent  814719fdaa0d3906ec6b1d9853218f23b6abf7fe
INOD

diff -r 814719fdaa0d -r 049e0d632763 src/problems/inod.lisp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/problems/inod.lisp	Fri Dec 20 17:12:11 2019 -0500
@@ -0,0 +1,24 @@
+(in-package :rosalind)
+
+;; This one is trivial once you know the closed-form solution of N-2.  The
+;; intuition for that can come in two parts.
+;;
+;; First, a rooted binary tree has N-1 internal nodes.  This is because at any
+;; given point as you're building the tree, you select 2 of the remaining nodes
+;; and join them together with an internal node, which reduces the total
+;; remaining by 1.  You end when there is only one remaining node (the root) and
+;; so you did N-1 subtractions.
+;;
+;; To convert this to an unrooted tree, you replace the root node with an edge,
+;; which subtracts one more internal node from the graph.  So you're left with
+;; N-2 internal nodes.
+
+(define-problem inod (data stream)
+    "4"
+    "2"
+  (- (read data) 2))
+
+
+#; Scratch --------------------------------------------------------------------
+
+(problem-inod)