#!/usr/bin/ruby

#
## http://rosettacode.org/wiki/Knuth%27s_power_tree
#

var p = Hash(1 => 0)
var lvl = [[1]]

func path(n) is cached {
    n || return []
    while (n !~ p) {
        lvl[0] = gather {
            for x in lvl[0] {
                for y in path(x) {
                    break if (x+y ~~ p)
                    y = x+y
                    p{y} = x
                    take(y)
                }
            }
        }
    }
    path(p{n}) + [n]
}

func tree_pow(x, n) {
    var r = Hash(0 => 1, 1 => x)
    var p = 0
    for i in path(n) {
        r{i} = (r{i-p} * r{p})
        p = i
    }
    r{n}
}

func show_pow(x, n) {
    var fmt = ("%d: %s\n" + ["%g^%s = %f", "%s^%s = %s"][x.is_int] + "\n")
    print(fmt % (n, path(n), x, n, tree_pow(x, n)))
}

for x in ^9 { show_pow(2, x) }
show_pow(1.1, 81)
show_pow(3, 191)
