StrongPassword.ts

//检查数量 满足  则 只Replace
//迭代修复
//1中行为 修复多个问题
//最优解

//解决问题顺序
//解决问题方法
//所有解中的最优解决方案
class LinkedNode<T>{
    data : T = null
    pre : LinkedNode<T> = null
    next : LinkedNode<T> = null
}
class LinkedList<T> {
    head : LinkedNode<T> = null
    tail : LinkedNode<T> = null
    constructor(){
        this.head = new LinkedNode<T>()
        this.tail = this.head
    }
    IsEmpty(): boolean{
        return this.head == this.tail
    }
    PopFirst() : T{
        if(this.IsEmpty()) return null;
        let pop = this.head.next
        this.head.next = pop.next
        if(this.head.next == null) this.tail = this.head
        else this.head.next.pre = this.head
        return pop.data
    }
    First() : T{
        if(this.IsEmpty()) return null
        let pop = this.head.next
        return pop.data
    }
    Last() : T {
        if(this.IsEmpty()) return null
        let pop = this.tail
        return pop.data
    }
    PopLast(): T{
        if(this.IsEmpty()) return null
        let pop = this.tail
        this.tail = this.tail.pre
        this.tail.next = null
        return pop.data
    }
    Push(d : T){
        let n = new LinkedNode<T>()
        n.data = d
        n.pre = this.tail
        n.next = null
        this.tail.next = n
        this.tail = n
    }
}
enum ProblemType {
    More,
    Less,
    Miss,
    Repeat,
}

class HowFix {
    type : ProblemType
    minFixNum : number
}
class ErrorNode {
    start : number = 0
    len : number = 0
    char : string = null
}
class MissType {
    misUp : boolean = false
    misLow : boolean = false
    misNum : boolean = false
}
enum Problem {
    Same,
    Char,
    Count,
}
enum Method {
    Replace,
    Insert,
    Remove,
}

enum NodeType {
    Root,
    Seq,
    Prob,
    Met,
}
class FixNode {
    problem : Problem = null
    method : Method = null
    minStep : number = -1
    parent : FixNode = null
    allChild : FixNode[] = []
    nodeType : NodeType = null
}

class NextRet {
    ok : boolean = false
    minPos : number = -1
    isMax : boolean = false
}

//大数量无法解决 寻找小数量
//剩下的用Replace解决
//Operation Machine
//FixMachine 随机解决问题
//每次只解决一个问题
//输出一个新串
class SameInfo {
    sameNodes : ErrorNode[]
    
    //重复节点 最多移除多少个节点可以达到 不同字符相间
    maxRemoveNum(){
        let rNum = 0
        this.sameNodes.forEach(element => {
            rNum += element.len-1
        });
        return rNum
    }
    //最多加多少个节点可以解决所有SameNode问题
    maxAddNum() {
        let addNum = 0
        this.sameNodes.forEach(element => {
            addNum += Math.floor((element.len-1)/2)
        });
        return addNum
    }
    //替换多少个解决替换问题
    replaceNum() {
        let rn = 0
        this.sameNodes.forEach(element =>{
            rn += Math.floor(element.len/3)
        })
        return rn
    }
}
class Premutation {
    num : number = 0
    ret : number[][] = []
    Gen(){
        let init : number[] = []
        for(let i = 0; i < this.num; i++){
            init.push(i)
        }
        this.ret.push(this.CopyArr(init))
        let cur = init
        while(true) {
            let canFixIndex = 0
            // while(true) {
                let minPos = this.FixNext(cur, canFixIndex)
                if(minPos.isMax) return
                // if(!minPos.ok) break
                // canFixIndex = minPos.minPos+1
            // }
            this.ret.push(this.CopyArr(cur)) 
        }
    }
    FixNext(cur : number[], startIndex : number) : NextRet{
        // console.log("FindNext", cur, startIndex)
        let ret = new NextRet()
        let curValue = -1
        let curMinIndex = -1
        for(let i = this.num-1; i>= startIndex; i--) {
            let c = cur[i]
            //first Max Num
            if(c < curValue) {
                curMinIndex = i
                break
            }else {
                curValue = c
            }
        }
        if(curMinIndex == -1){
            if(startIndex == 0){
                ret.isMax = true
            }
            ret.ok = false
            ret.minPos = -1
            return ret
        }

        let curMinValue = cur[curMinIndex]
        let replaceIndex = -1
        for(let i = this.num-1; i> curMinIndex; i--){
            let c = cur[i]
            if(c > curMinValue){
                replaceIndex = i
                break
            }
        }
        if(replaceIndex == -1) {
            ret.isMax = false
            ret.ok = false
            ret.minPos = -1
            return ret
        }
        this.Swap(cur, curMinIndex, replaceIndex)
        ret.isMax = false
        ret.ok = true
        ret.minPos = curMinIndex
        let i = this.num-1
        let j = curMinIndex+1
        for(; i > j; i--, j++)
        {
            let t1 = cur[i]
            let t2 = cur[j]
            cur[j] = t1
            cur[i] = t2
        }

        // console.log(cur, ret.minPos, replaceIndex)
        return ret
    }
    Swap<T>(a : Array<T>, i : number, j : number){
        let temp = a[i]
        let t2 = a[j]
        a[i] = t2
        a[j] = temp
    } 
    CopyArr(a : number[]):number[] {
        let na : number[] = []
        for(let i = 0; i < a.length; i++){
            na.push(a[i])
        }
        return na
    }
}
class Strong {
    password : string = null
    sameNodes : ErrorNode[] = []
    treeNodes : FixNode[] = []

    Check3() {
        
    }
    Check2() {
        let rootNode = new FixNode()
        rootNode.nodeType = NodeType.Root
        //组合遍历 0 1 2
        let pre = new Premutation()
        pre.num = 3
        pre.Gen()
        console.log(pre.ret)

        for(let i = 0; i < pre.ret.length; i++)
        {
            let mn = new FixNode()
            mn.parent = rootNode
            mn.nodeType = NodeType.Seq
            rootNode.allChild.push(mn)
            let ret= pre.ret[i]
            for(let j = 0; j < ret.length; j++){
                let m = new FixNode()
                m.parent = mn
                m.problem = ret[j]
                mn.allChild.push(m)
                m.nodeType = NodeType.Prob
                for(let k = 0; k < 3; k++) {
                    let mm = new FixNode()
                    mm.nodeType = NodeType.Met
                    mm.parent = m
                    m.allChild.push(mm)
                }
            }
        }
        this.VisitTree(rootNode)
        console.log(this.treeNodes)
    }
    VisitTree(node : FixNode) {
        this.treeNodes.push(node)
        node.allChild.forEach(element => {
            this.VisitTree(element)
        });
    }
    Check():number{
        let f1 = this.FixSame()
        let f2 = this.FixChar()
        let f3 = this.FixCount()
        return f1+f2+f3
    }
    FixSame():number{
        let curChar : string = null;
        let newNode = new ErrorNode()
        newNode.start = 0
        newNode.len = 0
        newNode.char = curChar
        for(let i = 0; i < this.password.length; i++)
        {
            let pc = this.password[i]
            // console.log("s", pc, curChar, newNode, i)
            if(pc != curChar)
            {
                if(newNode.len > 1) {
                    this.sameNodes.push(newNode)
                    newNode = new ErrorNode()
                    newNode.start = i
                    newNode.len = 1
                    newNode.char = pc
                }else {
                    newNode.start = i
                    newNode.len = 1
                    newNode.char = pc
                }
                curChar = pc
            }else {
                newNode.len++;
            }
        }
        if(newNode.len > 1) {
            this.sameNodes.push(newNode)
        }

        //选择修正的方法 和 修正的手段
        let totalReplaceNum = 0
        for(let i = 0; i < this.sameNodes.length; i++){
            let fixNum = Math.floor(this.sameNodes.length/3)
            totalReplaceNum += fixNum
        }
        return totalReplaceNum
    }
    FixChar() :number{
        let mis = new MissType()
        mis.misLow = true
        mis.misNum = true
        mis.misUp = true
        for(let i = 0; i < this.password.length; i++){
            let pc = this.password[i]
            if(pc == pc.toLowerCase()) mis.misLow = false
            if(pc == pc.toUpperCase()) mis.misUp = false
            if(!isNaN(Number(pc))) mis.misNum = false
        }
        let misWhat = 0
        if(mis.misNum) misWhat++
        if(mis.misLow) misWhat++
        if(mis.misUp) misWhat++
        return misWhat
    }
    FixCount():number {
        let fixNum = 0
        let l = this.password.length
        if(l < 6) fixNum = 6-l
        if(l > 20) fixNum = l-20
        return fixNum
    }

    Replace(){

    }

    Remove(){

    }

    Add() {

    }
}

let s = "aaaaaaaabbbcccddd"
let str = new Strong()
str.password = s
// str.Check()
str.Check2()

// console.log(str.sameNodes)