package main

import "fmt"

func main() {
    ret := strobogrammaticInRange("50", "100")
    fmt.Println(ret)
}

func strobogrammaticInRange(l, h string) int {
    low := []byte(l)
    high := []byte(h)
    if !equalMore(low, high) {
        return 0
    }
    lowLen := len(low)
    highLen := len(high)
    if lowLen == highLen {
        up1 := up(low, 0, false, 1)
        up2 := up(high, 0, false, 1)
        return up1 - up2 + twoSelectOne(valid(high), 1, 0)
    }
    ans := 0
    // lowLen = 3 hightLen = 7
    // 4 5 6
    for i := lowLen + 1; i < highLen; i++ {
        ans += all1(i)
    }
    ans += up(low, 0, false, 1)
    ans += down(high, 0, false, 1)
    return ans
}

func equalMore(low, cur []byte) bool {
    if len(low) != len(cur) {
        return len(low) < len(cur)
    }
    for i := 0; i < len(low); i++ {
        if low[i] != cur[i] {
            return low[i] < cur[i]
        }
    }
    return true
}

func valid(str []byte) bool {
    L := 0
    R := len(str) - 1
    for L <= R {
        t := L != R
        if convert2(str[L], t) != int(str[R]) {
            return false
        }
        L++
        R--
    }
    return true
}

// left想得到cha字符，right配合应该做什么决定，
// 如果left怎么也得不到cha字符，返回-1；如果能得到，返回right配合应做什么决定
// 比如，left!=right，即不是同一个位置
// left想得到0，那么就right就需要是0
// left想得到1，那么就right就需要是1
// left想得到6，那么就right就需要是9
// left想得到8，那么就right就需要是8
// left想得到9，那么就right就需要是6
// 除此了这些之外，left不能得到别的了。
// 比如，left==right，即是同一个位置
// left想得到0，那么就right就需要是0
// left想得到1，那么就right就需要是1
// left想得到8，那么就right就需要是8
// 除此了这些之外，left不能得到别的了，比如：
// left想得到6，那么就right就需要是9，而left和right是一个位置啊，怎么可能即6又9，返回-1
// left想得到9，那么就right就需要是6，而left和right是一个位置啊，怎么可能即9又6，返回-1
func convert2(cha byte, diff bool) int {
    switch cha {
    case '0':
        return '0'
    case '1':
        return '1'
    case '6':
        return twoSelectOne(diff, '9', -1)
    case '8':
        return '8'
    case '9':
        return twoSelectOne(diff, '6', -1)
    default:
        return -1
    }
}

// low [左边已经做完决定了 left.....right 右边已经做完决定了]
// 左边已经做完决定的部分，如果大于low的原始，leftMore = true;
// 左边已经做完决定的部分，如果不大于low的原始，那一定是相等，不可能小于，leftMore = false;
// 右边已经做完决定的部分，如果小于low的原始，rightLessEqualMore = 0;
// 右边已经做完决定的部分，如果等于low的原始，rightLessEqualMore = 1;
// 右边已经做完决定的部分，如果大于low的原始，rightLessEqualMore = 2;
// rightLessEqualMore < = >
//                    0 1 2
// 返回 ：没做决定的部分，随意变，几个有效的情况？返回！
func up(low []byte, left int, leftMore bool, rightLessEqualMore int) int {
    N := len(low)
    right := N - 1 - left
    if left > right { // 都做完决定了！
        // 如果左边做完决定的部分大于原始 或者 如果左边做完决定的部分等于原始&左边做完决定的部分不小于原始
        // 有效！
        // 否则，无效！
        return twoSelectOne(leftMore || (!leftMore && rightLessEqualMore != 0), 1, 0)
    }
    // 如果上面没有return，说明决定没做完，就继续做
    if leftMore { // 如果左边做完决定的部分大于原始
        return num(N - (left << 1))
    } else { // 如果左边做完决定的部分等于原始
        ways := 0
        // 当前left做的决定，大于原始的left
        for cha := (low[left] + 1); cha <= '9'; cha++ {
            if convert2(cha, left != right) != -1 {
                ways += up(low, left+1, true, rightLessEqualMore)
            }
        }
        // 当前left做的决定，等于原始的left
        convert := convert2(low[left], left != right)
        if convert != -1 {
            if convert < int(low[right]) {
                ways += up(low, left+1, false, 0)
            } else if convert == int(low[right]) {
                ways += up(low, left+1, false, rightLessEqualMore)
            } else {
                ways += up(low, left+1, false, 2)
            }
        }
        return ways
    }
}

// ll < =
// rs < = >
func down(high []byte, left int, ll bool, rs int) int {
    N := len(high)
    right := N - 1 - left
    if left > right {
        return twoSelectOne(ll || (!ll && rs != 2), 1, 0)
    }
    if ll {
        return num(N - (left << 1))
    } else {
        ways := 0
        for cha := byte(twoSelectOne((N != 1 && left == 0), '1', '0')); cha < high[left]; cha++ {
            if convert2(cha, left != right) != -1 {
                ways += down(high, left+1, true, rs)
            }
        }
        convert := convert2(high[left], left != right)
        if convert != -1 {
            if convert < int(high[right]) {
                ways += down(high, left+1, false, 0)
            } else if convert == int(high[right]) {
                ways += down(high, left+1, false, rs)
            } else {
                ways += down(high, left+1, false, 2)
            }
        }
        return ways
    }
}

func num(bits int) int {
    if bits == 1 {
        return 3
    }
    if bits == 2 {
        return 5
    }
    p2 := 3
    p1 := 5
    ans := 0
    for i := 3; i <= bits; i++ {
        ans = 5 * p2
        p2 = p1
        p1 = ans
    }
    return ans
}

// 如果是最开始 :
// Y X X X Y
// -> 1 X X X 1
// -> 8 X X X 8
// -> 9 X X X 6
// -> 6 X X X 9
// 如果不是最开始 :
// Y X X X Y
// -> 0 X X X 0
// -> 1 X X X 1
// -> 8 X X X 8
// -> 9 X X X 6
// -> 6 X X X 9
// 所有的len位数，有几个有效的？
func all1(len0 int) int {
    ans := twoSelectOne((len0&1) == 0, 1, 3)
    for i := twoSelectOne((len0&1) == 0, 2, 3); i < len0; i += 2 {
        ans *= 5
    }
    return ans << 2
}

// 我们课上讲的
func all2(len0 int, init0 bool) int {
    if len0 == 0 { // init == true，不可能调用all(0)
        return 1
    }
    if len0 == 1 {
        return 3
    }
    if init0 {
        return all2(len0-2, false) << 2
    } else {
        return all2(len0-2, false) * 5
    }
}

func twoSelectOne(c bool, a, b int) int {
    if c {
        return a
    } else {
        return b
    }
}