package poker

import (
	"fmt"
	"sort"
)

type GroupType int

const (
	GtUnknown  GroupType = 0 // 不是组合
	GtKind     GroupType = 1 // 同花
	GtStraight GroupType = 2 // 顺子
)

type GroupPokers struct {
	Pokers    []*Poker
	GroupType GroupType
}

// 按顺子排序
func sortByStraight(pks []*Poker) []*Poker {
	var tmpPks []*Poker
	tmpPks = append(tmpPks, pks...)
	sort.Slice(tmpPks, func(i, j int) bool {
		if tmpPks[i].Color == tmpPks[j].Color {
			return tmpPks[i].Point < tmpPks[j].Point
		}
		return tmpPks[i].Color < tmpPks[j].Color
	})
	return tmpPks
}

// 按条子排序
func sortByKind(pks []*Poker) []*Poker {
	var tmpPks []*Poker
	tmpPks = append(tmpPks, pks...)
	sort.Slice(tmpPks, func(i, j int) bool {
		if tmpPks[i].Point == tmpPks[j].Point {
			return tmpPks[i].Color < tmpPks[j].Color
		}
		return tmpPks[i].Point < tmpPks[j].Point
	})
	return tmpPks
}

// 是否万能牌
func isWildPoker(wildPoker, pk *Poker) bool {
	return wildPoker.ToValue() == pk.ToValue()
}

// 手牌分为万能牌和正常牌
func divideWildPokers(wildPoker *Poker, pks []*Poker) (wildPokers []*Poker, normalPokers []*Poker) {
	for _, pk := range pks {
		if isWildPoker(wildPoker, pk) {
			wildPokers = append(wildPokers, pk)
			wildPokers = sortByKind(wildPokers)
		} else {
			normalPokers = append(normalPokers, pk)
		}
	}
	return
}

// 两牌是否递增， 不考虑万能牌
func isIncrement(c Color, p Point, pk *Poker) bool {
	if c == pk.Color {
		if p == PointK && pk.Point == PointA {
			return true
		}
		return pk.Point-p == 1
	}
	return false
}

// 两牌点数是不是相同，花色不同， 不考虑万能牌
func isSamePoint(pk1, pk2 *Poker) bool {
	if pk1.Color == pk2.Color || pk1.Point != pk2.Point {
		return false
	}
	return true
}

// 是否条子，不考虑万能牌
func isKind3(pk1, pk2, pk3 *Poker) bool {
	if pk1.Point != pk2.Point || pk2.Point != pk3.Point {
		return false
	}
	if pk1.Color == pk2.Color || pk2.Color == pk3.Color || pk1.Color == pk3.Color {
		return false
	}
	return true
}

// 查找出一个顺子组合
func findAStraightGroup(wildPokers, pks []*Poker) (group *GroupPokers, highPokes, wildPokers2 []*Poker) {
	pks = sortByStraight(pks)
	wildPokers2 = wildPokers
	highPokes = pks
	if len(pks) < 2 {
		return
	}
	var groupPokers []*Poker
	groupPokers = append(groupPokers, pks[0])
	// 找顺子，不考虑万能牌
	for i := 0; i < len(pks)-1; i++ {
		groupPokers = groupPokers[0:0]
		groupPokers = append(groupPokers, pks[i])
		// pks[i]与pks[i+1] 成顺子关系
		if isIncrement(pks[i].Color, pks[i].Point, pks[i+1]) {
			groupPokers = append(groupPokers, pks[i+1])
			if i+2 < len(pks) {
				// pks[i],pks[i+1],pks[i+2] 成顺子关系
				if isIncrement(pks[i+1].Color, pks[i+1].Point, pks[i+2]) {
					groupPokers = append(groupPokers, pks[i+2])
					group = &GroupPokers{Pokers: groupPokers, GroupType: GtStraight}
					highPokes = append(pks[:i], pks[i+3:]...)
					return
				}
			}
			// 最后两个为Q K，且第一个为A
			if i+2 == len(pks) && isIncrement(pks[i+1].Color, pks[i+1].Point, pks[0]) {
				groupPokers = append(groupPokers, pks[0])
				group = &GroupPokers{Pokers: groupPokers, GroupType: GtStraight}
				highPokes = pks[1:i]
				return
			}
		}
	}

	// 没有万能牌，直接返回
	if len(wildPokers) == 0 {
		return
	}
	// 加上万能牌找顺子
	for i := 0; i < len(pks)-1; i++ {
		groupPokers = groupPokers[0:0]
		groupPokers = append(groupPokers, pks[i])
		// 两个顺，加一个万能牌
		if isIncrement(pks[i].Color, pks[i].Point, pks[i+1]) {
			groupPokers = append(groupPokers, pks[i+1])
			groupPokers = append(groupPokers, wildPokers[len(wildPokers)-1])
			wildPokers2 = wildPokers[:len(wildPokers2)-1]
			group = &GroupPokers{Pokers: groupPokers, GroupType: GtStraight}
			highPokes = append(pks[:i], pks[i+2:]...)
			return
		}
		// 跳牌，中间放一个万能牌
		if isIncrement(pks[i].Color, pks[i].Point, pks[i+1]) || isIncrement(pks[i].Color, pks[i].Point+1, pks[i+1]) {
			groupPokers = append(groupPokers, wildPokers[len(wildPokers)-1])
			groupPokers = append(groupPokers, pks[i+1])
			wildPokers2 = wildPokers[:len(wildPokers2)-1]
			group = &GroupPokers{Pokers: groupPokers, GroupType: GtStraight}
			highPokes = append(pks[:i], pks[i+2:]...)
			return
		}
	}
	return
}

// 查找出一个条子组合
// 同花 1:必须是三种花色 2:除万能牌之外，不能出现点数不同 3.万能牌只能有一张或全是万能牌 4.所有牌都是万能牌，花色至少有两种
func findAKindGroup(wildPokers, pks []*Poker) (group *GroupPokers, highPokes, wildPokers2 []*Poker) {
	pks = sortByKind(pks)
	wildPokers2 = wildPokers
	highPokes = pks
	if len(pks)+len(wildPokers) < 2 {
		return
	}
	var groupPokers []*Poker
	// 找条子，不考虑万能牌
	for i := 0; i < len(pks)-2; i++ {
		// pks[i], pks[i+1], pks[i+2] 成条子关系
		if isKind3(pks[i], pks[i+1], pks[i+2]) {
			groupPokers = groupPokers[0:0]
			groupPokers = append(groupPokers, pks[i])
			groupPokers = append(groupPokers, pks[i+1])
			groupPokers = append(groupPokers, pks[i+2])
			group = &GroupPokers{Pokers: groupPokers, GroupType: GtKind}
			highPokes = append(pks[:i], pks[i+3:]...)
			return
		}
	}
	// 没有万能牌，直接返回
	if len(wildPokers) == 0 {
		return
	}
	// 加上万能牌找条子
	for i := 0; i < len(pks)-1; i++ {
		// 两条，加一个万能牌
		if isSamePoint(pks[i], pks[i+1]) {
			groupPokers = groupPokers[0:0]
			groupPokers = append(groupPokers, pks[i])
			groupPokers = append(groupPokers, pks[i+1])
			groupPokers = append(groupPokers, wildPokers[len(wildPokers)-1])
			wildPokers2 = wildPokers[:len(wildPokers)-1]
			group = &GroupPokers{Pokers: groupPokers, GroupType: GtKind}
			highPokes = append(pks[:i], pks[i+2:]...)
			return
		}
	}
	// 组合不能出现多张万能+一张其它牌，只能全是万能牌或只有一张万能牌
	//// 两张万能牌加一张散牌点数与万能牌点数相同，比如：散牌:♣5 ♣9  万能牌:♥9 ♥9 形成:♣9 ♥9 ♥9 散牌:♣5
	//if len(wildPokers) > 1 && len(pks) > 0 {
	//	for i := 0; i < len(pks); i++ {
	//		if isSamePoint(wildPokers[0], pks[i]) {
	//			groupPokers = groupPokers[0:0]
	//			groupPokers = append(groupPokers, pks[i])
	//			groupPokers = append(groupPokers, wildPokers[len(wildPokers)-1])
	//			groupPokers = append(groupPokers, wildPokers[len(wildPokers)-2])
	//			wildPokers2 = wildPokers[:len(wildPokers)-2]
	//			group = &GroupPokers{Pokers: groupPokers, GroupType: GtKind}
	//			highPokes = append(pks[:i], pks[i+1:]...)
	//			return
	//		}
	//	}
	//}
	// 三张万能牌组成条子
	if len(wildPokers) > 2 {
		for i := 0; i < len(wildPokers)-2; i++ {
			// 两条，加一个万能牌
			if isSamePoint(wildPokers[i], wildPokers[i+1]) {
				groupPokers = groupPokers[0:0]
				groupPokers = append(groupPokers, wildPokers[i])
				groupPokers = append(groupPokers, wildPokers[i+1])
				groupPokers = append(groupPokers, wildPokers[i+2])
				wildPokers2 = append(wildPokers[:i], wildPokers[i+3:]...)
				group = &GroupPokers{Pokers: groupPokers, GroupType: GtKind}
				return
			}
		}
	}
	return
}

// 顺子 1:万能牌最多只能有一个 2:只能同花色
func isStraight(wildPoker *Poker, pks ...*Poker) bool {
	straightPks := make([]*Poker, 0)

	wildCnt := 0 // 万能牌数量
	color := ColorUnknown
	point := PointUnknown
	for _, pk := range pks {
		// 万能牌只能有一个
		if isWildPoker(wildPoker, pk) {
			wildCnt++
			if wildCnt > 1 {
				return false
			}
		} else {
			if color == ColorUnknown {
				color = pk.Color
			}
			if point == PointUnknown {
				point = pk.Point
				if pk.Color != color {
					return false
				}
			} else {
				// 花色必须相同，点数必须不同
				if pk.Point == point || pk.Color != color {
					return false
				}
			}
			straightPks = append(straightPks, pk)
		}
	}

	sort.Slice(straightPks, func(i, j int) bool {
		return straightPks[i].Point < straightPks[j].Point
	})

	if straightPks[0].Point == PointA && straightPks[len(straightPks)-1].Point == PointK {
		straightPks = append(straightPks, straightPks[0])
		straightPks = straightPks[1:]
	}
	value := straightPks[0].Point
	step := 1
	for {
		if step == len(straightPks) {
			break
		}
		if value+1 == straightPks[step].Point {
			value = straightPks[step].Point
			step++
			continue
		}
		if value == PointK && straightPks[step].Point == PointA {
			value = straightPks[step].Point
			step++
			continue
		}
		if wildCnt > 0 {
			value++
			wildCnt--
			continue
		} else {
			return false
		}
	}
	return true
}

func addPokerToStraightGroup(wildPoker, pk *Poker, group *GroupPokers) (bool, *GroupPokers) {
	var tmpPokers []*Poker
	tmpPokers = append(tmpPokers, pk)
	tmpPokers = append(tmpPokers, group.Pokers...)
	if ok := isStraight(wildPoker, tmpPokers...); ok {
		group.Pokers = append(group.Pokers, pk)
		return true, group
	}
	return false, nil
}

func addPokerToKindGroup(wildPoker, pk *Poker, group *GroupPokers) (bool, *GroupPokers) {
	// 组合要么只有一个万能牌，要么全是万能牌
	wildNum := 0
	if isWildPoker(wildPoker, pk) {
		for _, p := range group.Pokers {
			if isWildPoker(wildPoker, p) {
				wildNum++
			}
		}
		if wildNum == 0 {
			group.Pokers = append(group.Pokers, pk)
			return true, group
		}
		if wildNum != len(group.Pokers) {
			return false, nil
		}
		// 全是万能牌的组合，可以一直添加万能牌
		group.Pokers = append(group.Pokers, pk)
		return true, group
	}
	// 与组牌中不是万能牌的牌比点数，必须相同
	cmp := false
	for _, gp := range group.Pokers {
		if !isWildPoker(wildPoker, gp) {
			cmp = isSamePoint(pk, group.Pokers[0])
			break
		}
	}
	if !cmp {
		return false, nil
	}
	colors := make(map[Color]int)
	colors[pk.Color] = 1
	// 组牌中除万能牌外，其它的牌的颜色最多只能出现三种
	for _, p := range group.Pokers {
		if !isWildPoker(wildPoker, p) {
			colors[p.Color] = 1
		}
	}
	if len(colors) > 3 {
		return false, nil
	}
	group.Pokers = append(group.Pokers, pk)
	return true, group
}

type GroupHigh struct {
	groups     []*GroupPokers
	high       []*Poker
	wildPokers []*Poker
}

func PopCopy(groups []*GroupPokers, high []*Poker, wildPokers []*Poker) *GroupHigh {
	gh := &GroupHigh{}
	for _, g := range groups {
		var gp GroupPokers
		gp.GroupType = g.GroupType
		gp.Pokers = append(gp.Pokers, g.Pokers...)
		gh.groups = append(gh.groups, &gp)
	}
	gh.high = append(gh.high, high...)
	gh.wildPokers = append(gh.wildPokers, wildPokers...)
	return gh
}

// 回溯函数
func backtrack(wildPoker *Poker, ghs, best *GroupHigh, deep int, id int) {
	id = id*10 + 1
	//if id == 21 {
	//	fmt.Println("")
	//}
	//fmt.Println(fmt.Sprintf("id:%v %s", id, DebugGroupsHigh(ghs.groups, ghs.high, ghs.wildPokers)))
	group, high, wild := findAStraightGroup(ghs.wildPokers, ghs.high)
	if group != nil {
		groups := append(ghs.groups, group)
		gh1 := PopCopy(groups, high, wild)
		backtrack(wildPoker, gh1, best, deep+1, id)
	}

	id++
	group, high, wild = findAKindGroup(ghs.wildPokers, ghs.high)
	if group != nil {
		groups := append(ghs.groups, group)
		gh1 := PopCopy(groups, high, wild)
		backtrack(wildPoker, gh1, best, deep+1, id)
	}

	var newHigh []*Poker
	for i := 0; i < len(high); i++ {
		add := false
		// 尝试将当前牌加入到一个现有组合中
		for k, gp := range ghs.groups {
			var aGroup *GroupPokers
			if gp.GroupType == GtKind {
				_, aGroup = addPokerToKindGroup(wildPoker, high[i], gp)
			}
			if gp.GroupType == GtStraight {
				_, aGroup = addPokerToStraightGroup(wildPoker, high[i], gp)
			}
			if aGroup != nil {
				ghs.groups[k] = aGroup
				tmpHigh := append(high[:i], high[i+1:]...)

				gh1 := PopCopy(ghs.groups, tmpHigh, wild)
				id++
				backtrack(wildPoker, gh1, best, deep+1, id)
				add = true
				break
			}
		}
		if !add {
			newHigh = append(newHigh, high[i])
		}
	}
	ghs.high = newHigh
	ghs.wildPokers = wild

	var newWild []*Poker
	for i := 0; i < len(wild); i++ {
		add := false
		// 尝试将万能牌加入到一个现有组合中
		for k, gp := range ghs.groups {
			var aGroup *GroupPokers
			if gp.GroupType == GtKind {
				_, aGroup = addPokerToKindGroup(wildPoker, wild[i], gp)
			}
			if gp.GroupType == GtStraight {
				_, aGroup = addPokerToStraightGroup(wildPoker, wild[i], gp)
			}
			if aGroup != nil {
				ghs.groups[k] = aGroup
				tmpWild := append(wild[:i], wild[i+1:]...)

				gh1 := PopCopy(ghs.groups, high, tmpWild)
				id++
				backtrack(wildPoker, gh1, best, deep+1, id)
				add = true
				break
			}
		}
		if !add {
			newWild = append(newWild, wild[i])
		}
	}
	//ghs.wildPokers = newWild
	// 如果所有牌都已处理完毕，则评估当前解的质量
	if len(ghs.high)+len(ghs.wildPokers) < len(best.high)+len(best.wildPokers) {
		best.high = ghs.high
		best.groups = ghs.groups
		best.wildPokers = ghs.wildPokers
		//fmt.Println(debugGroupsHigh(best))
	}
}

func DebugGroupsHigh(gs []*GroupPokers, highs []*Poker, wilds []*Poker) string {
	str := ""
	for _, g := range gs {
		str += fmt.Sprintf("组合:%s ", PokersToString(g.Pokers))
	}
	str += fmt.Sprintf("散牌:%s ", PokersToString(highs))
	if len(wilds) > 0 {
		str += fmt.Sprintf("万能牌:%s ", PokersToString(wilds))
	}
	return str
}

func FindBestGroupsAndRemains(wildPoker *Poker, pks []*Poker) ([]*GroupPokers, []*Poker) {
	wildPokers, normalPokers := divideWildPokers(wildPoker, pks)
	ghs := PopCopy(nil, normalPokers, wildPokers)
	best := PopCopy(nil, normalPokers, wildPokers)

	//fmt.Println(debugGroupsHigh(ghs))
	// 开始回溯
	backtrack(wildPoker, ghs, best, 0, 0)

	//fmt.Println(debugGroupsHigh(ghs))
	best.high = append(best.high, best.wildPokers...)
	best.wildPokers = best.wildPokers[:0]
	return best.groups, best.high
}