广度优先搜索

麻将胡牌算法(包括查听,查胡)

package main

import (
    "fmt"
)

func main() {
    list := []int{11, 12, 13, 14, 14, 15, 16, 12}
    // lists := combination(list, []int{})
    // for k, l := range lists {
    //  fmt.Printf("组合:%v===", k)
    //  for _, c := range l.combin {
    //      fmt.Printf("类型:%v 值:%v;", c.tp, c.values)
    //  }
    //  fmt.Println()
    // }

    m := outTS(list)
    for k, v := range m {
        fmt.Printf("打出:%v,可以胡%vn", k, v)
    }
}

func outTS(list []int) map[int][]int {
    var ts = make(map[int][]int, 0)
    out := make([]int, 0)
    if len(list)%3 != 2 {
        return ts
    }
    for k, v := range list {
        if v == 0 {
            continue
        }
        if exist(v, out) {
            continue
        }
        out = append(out, v)
        cpl := make([]int, len(list))
        copy(cpl, list)
        cpl = append(cpl[:k], cpl[k+1:]...)
        possbileCanHu := make([]int, 0)
        allPossbile := combination(cpl, []int{0})

        for _, possbilehu := range allPossbile {
            for _, comb := range possbilehu.combin {
                possbileCanHu = addtingCard(possbileCanHu, comb.laizitobe)
            }
        }
        if len(possbileCanHu) > 0 {
            ts[v] = possbileCanHu
        }
    }
    return ts
}

func addtingCard(src, dst []int) []int {
    for _, d := range dst {
        if !contain(src, d) {
            src = append(src, d)
        }
    }
    return src
}

func contain(src []int, dst int) bool {
    for _, s := range src {
        if s == dst {
            return true
        }
    }
    return false
}

type huList struct {
    combin []*combinat
}

type combinat struct {
    tp         int   // 1是将,2是顺子,3是克子
    values     []int // 值
    haslaizi   bool
    laizitobe  []int
    laiziIndex []int
}

func combination(list, laizi []int) []*huList {
    comb := make([]*huList, 0)
    findedJ := make([]int, 0)
    for index, value := range list {
        if value == 0 {
            continue
        }
        if exist(value, findedJ) {
            continue
        }
        findedJ = append(findedJ, value)
        cl := make([]int, len(list))
        copy(cl, list)
        cl = append(cl[:index], cl[index+1:]...)
        hus := find(value, cl, laizi)
        if len(hus) != 0 {
            comb = append(comb, hus...)
        }
    }
    return comb
}

func find(dst int, src, laizi []int) []*huList {
    possibleHu := new(huList)
    possibleHus := make([]*huList, 0)
    src = append(src, laizi...)
    index, j := findj(dst, src)
    if !j {
        return make([]*huList, 0)
    }
    jconmb := &combinat{
        tp:         1,
        values:     []int{dst, src[index]},
        haslaizi:   src[index] == 0,
        laizitobe:  []int{dst},
        laiziIndex: []int{1},
    }
    possibleHu.combin = append(possibleHu.combin, jconmb)
    src = append(src[:index], src[index+1:]...)
    possibleHus = find0(src, possibleHu, possibleHus)
    return possibleHus
}

func find0(src []int, hu *huList, hus []*huList) []*huList {
    comb3 := findComb3(src)
    for _, c := range comb3 {
        cpHu := new(huList)
        cpSrc := make([]int, len(src))
        copy(cpSrc, src)
        cpHu.combin = hu.combin
        cpSrc, cpHu = removeComb(cpSrc, c, cpHu)
        if len(cpSrc) == 0 {
            if !isexistHu(hus, cpHu) {
                hus = append(hus, cpHu)
            }
            break
        }
        hus = find0(cpSrc, cpHu, hus)
    }
    return hus
}

func isexistHu(hus []*huList, srcHu *huList) bool {
    for _, hu := range hus {
        indexs := make([]int, 0)
        for _, comb := range hu.combin {
            for k, srcComb := range srcHu.combin {
                if exist(k, indexs) {
                    continue
                }
                if isexistComb(comb, srcComb) {
                    indexs = append(indexs, k)
                    break
                }
            }
        }
        if len(indexs) == len(srcHu.combin) {
            return true
        }
    }
    return false
}

func isexistComb(dstComb, srcComb *combinat) bool {
    if len(dstComb.values) == len(srcComb.values) && dstComb.tp == srcComb.tp {
        for i := 0; i < len(dstComb.values); i++ {
            if dstComb.values[i] != srcComb.values[i] {
                return false
            }
        }
        return true
    }
    return false
}

func removeComb(src []int, comb *combinat, hu *huList) ([]int, *huList) {
    hu.combin = append(hu.combin, comb)
    for _, c := range comb.values {
        for index, s := range src {
            if s == c {
                src = append(src[:index], src[index+1:]...)
                break
            }
        }
    }
    return src, hu
}

func findComb3(src []int) []*combinat {
    comb3 := make([]*combinat, 0)
    comb3 = append(comb3, findk(src)...)
    comb3 = append(comb3, finds(src)...)
    return comb3
}

func findj(dst int, src []int) (int, bool) {
    for k, v := range src {
        if v == dst || v == 0 {
            return k, true
        }
    }
    return 0, false
}

func findk(src []int) []*combinat {
    possibleKe := make([]*combinat, 0)
    findedKe := make([]int, 0)

    for _, v := range src {
        if exist(v, findedKe) {
            continue
        }
        findedKe = append(findedKe, v)
        knum := 0
        laizi := 0
        for _, vv := range src {
            if v == vv {
                knum++
            }
            if v == 0 {
                laizi++
            }
        }
        if knum == 3 {
            possibleKe = append(possibleKe, &combinat{
                tp:       3,
                values:   []int{v, v, v},
                haslaizi: false,
            })
        }
        if knum == 2 && laizi >= 1 {
            possibleKe = append(possibleKe, &combinat{
                tp:         3,
                values:     []int{v, v, 0},
                haslaizi:   true,
                laizitobe:  []int{v},
                laiziIndex: []int{2},
            })
        }
        if knum == 1 && laizi >= 2 {
            possibleKe = append(possibleKe, &combinat{
                tp:         3,
                values:     []int{v, 0, 0},
                haslaizi:   true,
                laizitobe:  []int{v, v},
                laiziIndex: []int{1, 2},
            })
        }
    }
    return possibleKe
}

func finds(src []int) []*combinat {
    possibleShun := make([]*combinat, 0)
    findedShun := make([]int, 0)
    laizinum := 0
    for _, v := range src {
        if v == 0 {
            laizinum++
        }
    }
    for _, v := range src {
        if v == 0 {
            continue
        }
        s, f := findRs(v, src, laizinum)
        if f {
            if exist(s.values[0], findedShun) {
                continue
            }
            findedShun = append(findedShun, s.values[0])
            possibleShun = append(possibleShun, s)
        }
        s, f = findZs(v, src, laizinum)
        if f {
            if exist(s.values[0], findedShun) {
                continue
            }
            findedShun = append(findedShun, s.values[0])
            possibleShun = append(possibleShun, s)
        }
        s, f = findLs(v, src, laizinum)
        if f {
            if exist(s.values[0], findedShun) {
                continue
            }
            findedShun = append(findedShun, s.values[0])
            possibleShun = append(possibleShun, s)
        }
    }
    return possibleShun
}

func findRs(r int, src []int, laizinum int) (*combinat, bool) {
    if r%10 < 3 || r%10 > 9 {
        return nil, false
    }
    l := r - 2
    z := r - 1
    lnl, znl := false, false
    if !exist(l, src) {
        lnl = true
    }
    if !exist(z, src) {
        znl = true
    }
    if !lnl && !znl {
        return &combinat{
            tp:       2,
            values:   []int{l, z, r},
            haslaizi: false,
        }, true
    }
    if lnl && !znl && laizinum >= 1 {
        return &combinat{
            tp:         2,
            values:     []int{0, z, r},
            haslaizi:   true,
            laizitobe:  []int{l},
            laiziIndex: []int{0},
        }, true
    }
    if !lnl && znl && laizinum >= 1 {
        return &combinat{
            tp:         2,
            values:     []int{l, 0, r},
            haslaizi:   true,
            laizitobe:  []int{z},
            laiziIndex: []int{1},
        }, true
    }
    if lnl && znl && laizinum >= 2 {
        return &combinat{
            tp:         2,
            values:     []int{0, 0, r},
            haslaizi:   true,
            laizitobe:  []int{l, z},
            laiziIndex: []int{0, 1},
        }, true
    }
    return nil, false
}

func findLs(l int, src []int, laizinum int) (*combinat, bool) {
    if l%10 < 1 || l%10 > 7 {
        return nil, false
    }
    z := l + 1
    r := l + 2
    znl, rnl := false, false
    if !exist(z, src) {
        znl = true
    }
    if !exist(r, src) {
        rnl = true
    }
    if !znl && !rnl {
        return &combinat{
            tp:       2,
            values:   []int{l, z, r},
            haslaizi: false,
        }, true
    }
    if znl && !rnl && laizinum >= 1 {
        return &combinat{
            tp:         2,
            values:     []int{l, 0, r},
            haslaizi:   true,
            laizitobe:  []int{z},
            laiziIndex: []int{1},
        }, true
    }
    if !znl && rnl && laizinum >= 1 {
        return &combinat{
            tp:         2,
            values:     []int{l, z, 0},
            haslaizi:   true,
            laizitobe:  []int{r},
            laiziIndex: []int{2},
        }, true
    }
    if znl && rnl && laizinum >= 2 {
        return &combinat{
            tp:         2,
            values:     []int{l, 0, 0},
            haslaizi:   true,
            laizitobe:  []int{z, r},
            laiziIndex: []int{1, 2},
        }, true
    }
    return nil, false
}

func findZs(z int, src []int, laizinum int) (*combinat, bool) {
    if z%10 < 2 || z%10 > 8 {
        return nil, false
    }
    l := z - 1
    r := z + 1
    lnl, rnl := false, false
    if !exist(l, src) {
        lnl = true
    }
    if !exist(r, src) {
        rnl = true
    }
    if !lnl && !rnl {
        return &combinat{
            tp:       2,
            values:   []int{l, z, r},
            haslaizi: false,
        }, true
    }
    if lnl && !rnl && laizinum >= 1 {
        return &combinat{
            tp:         2,
            values:     []int{0, z, r},
            haslaizi:   true,
            laizitobe:  []int{l},
            laiziIndex: []int{0},
        }, true
    }
    if !lnl && rnl && laizinum >= 1 {
        return &combinat{
            tp:         2,
            values:     []int{l, z, 0},
            haslaizi:   true,
            laizitobe:  []int{r},
            laiziIndex: []int{2},
        }, true
    }
    if lnl && rnl && laizinum >= 2 {
        return &combinat{
            tp:         2,
            values:     []int{0, z, 0},
            haslaizi:   true,
            laizitobe:  []int{l, r},
            laiziIndex: []int{0, 2},
        }, true
    }
    return nil, false
}

func exist(dst int, src []int) bool {
    for _, v := range src {
        if v == dst {
            return true
        }
    }
    return false
}