左と右の有理数

締め切りが 2016/12/15 10:00 AM なので，その 1 分後に投稿されるように予約

【概要】

有理数を、図のようにならべます。

図では、紙面の都合で7段目までしか書かれていませんが、下に無限に広がっています。
与えられた有理数の、図上での左隣と右隣(図にある x は無視して)の有理数を求めてください。

【詳細】

有理数を並べるツリーは以下のルールに従っています：

    自分が p/q の場合、左の子は p/(p+q)
    自分が p/q の場合、右の子は (1-p/q)。ただし、自分が 1/2 以上の場合には右の子はいない。

入力は
3/7
という具合に標準入力から来ます。

出力は、左隣と右隣の有理数を、コンマ区切りで出力してください。
こんな
4/5,2/7
具合です。

ただし、左隣や右隣に有理数がない場合には、そこには有理数の代わりにハイフンをおいてください。
例えばこんな
-,4/5
3/4,-
具合です。

【例】

入力     出力
3/7     4/5,2/7
1/6     -,4/5
2/5     3/4,-

【補足】

不正な入力に対処する必要はありません。
入力の分母・分子 はいずれも正の整数で、分子<分母<二百五十 です。

=====

g = function(p, q) { # 親のノードを得る
    if (2 * p == q) {
        p = q = 0
    } else if (2 * p > q) {
        p = q - p
    } else {
        q = q - p
    }
    list(p = p, q = q)
}

h.l = function(p, q) { # 左側の子供のノードを得る
    list(p = p, q = p + q)
}

h.r = function(p, q) {# 右側の子供のノードを得る
    if (2 * p >= q) {
        p = q = 0
    } else {
        p = q - p
    }
    list(p = p, q = q)
}

case.r = function(p, q) { # 発端が右の子供の場合
    level = 0
    parent = g(p, q)
    l = h.l(parent$p, parent$q) # 発端者の左隣は親の左側の子供
    repeat { # 右隣の探索は，まず左側の子供を持つ親までさか上る
        parent = g(parent$p, parent$q)
        if (parent$p == 0) {
            return(list(l = l, r = parent))
        }
        level = level - 1
        r = h.r(parent$p, parent$q)
        if (r$p != p && r$q != q && r$p != 0 && r$q != 0) {
            break
        }
        p = parent$p
        q = parent$q
    }
    repeat { # しかる後に，左の子供をたどって下る
        if (level == 0) {
            break
        }
        level = level + 1
        r = h.l(r$p, r$q)
    }
    list(l = l, r = r)
}

case.ll = function(p, q) {
    level = -1
    parent = g(p, q)
    if (parent$p == 0 || parent$p == 1) {
        return(list(p = 0, q = 0))
    } else if (parent$p == 1) {
        return(h.l(parent$p, parent$q))
    }
    repeat { # 左隣の探索は，まず左側の子供を持つ親までさかのぼる
        parent = g(parent$p, parent$q)
        if (parent$p == 0) {
            return(list(p = 0, q = 0))
        }
        level = level - 1
        l = h.l(parent$p, parent$q)
        if (l$p != p && l$q != q && l$p != 0 && l$q != 0) {
            break
        }
        p = parent$p
        q = parent$q
    }
    level = level + 1
    l = h.l(parent$p, parent$q)
    if (level == 0) {
        return(l)
    }
    repeat {
        level = level + 1
        l = h.r(l$p, l$q)
        if (level == 0) {
            break
        }
        if (2 * l$p > l$q) {
            level = level + 1
            l = h.l(l$p, l$q)
            if (level == 0) {
                break
            }
        }
    }
    l
}

case.lr = function(p, q) {
    level = 0
    repeat {
        parent = g(p, q)
        r = h.r(parent$p, parent$q)
        if (0 > level && r$p == 0) {
            return(r)
        }
        if (r$p != parent$p && parent$q != q && r$p != 0) {
            break
        }
        level = level - 1
        p = parent$p
        q = parent$q
    }
    repeat {
        if (level == 0) {
            break
        }
        level = level + 1
        r = h.l(r$p, r$q)
    }
    r
}

f = function(p, q) {
    options(scipen = 100)
    l = r = list(p = 0, q = 0)
    if (2 * p > q) { # 右の子供が発端
        ans = case.r(p, q)
        l = ans$l
        r = ans$r
    } else { # 左の子供が発端
        l = case.ll(p, q) # 左隣
        r = case.lr(p, q) # 右隣
    }
    l = ifelse(l$p == 0, "-", sprintf("%s/%s", l$p, l$q))
    r = ifelse(r$p == 0, "-", sprintf("%s/%s", r$p, r$q))
    cat(sprintf("%s,%s", l, r))
}

f(3, 7) # 4/5,2/7
f(5, 37) # 16/41,27/32
f(1, 2) # -,-
f(1, 3) # -,-
f(248, 248) # -,-
f(1, 249) # -,247/248
f(2, 249) # 14662949395604/23725150497407,245/247
f(3, 248) # 1032569015/1670731762,242/245
f(144, 233) # 89/322,-
f(247, 248) # 1/249,246/493
f(65, 81) # 16/97,49/114
f(65, 73) # 8/81,57/122
f(134, 205) # 71/276,55/338