import UIKit

let testValue1:String = "24,6723,23,111,43,1,昇順"
let testValue2:String = "え,い,う,か,と,昇順"
let testValue3:String = "-2,-22347999,あ,2,い,3,-1,ああ,昇順"

enum OrderType:String{
    case none = "例外"
    case ascending = "昇順"
    case descending = "降順"
}

enum ValueType:String{
    case Iregular = "例外"
    case Number = "数字"
    case Charactor = "ローマ字"
    case Japanese = "日本語"
}

//  ============= メイン処理 ==============
//  入力された文字列を分割
var inputValueList = testValue3.split(separator: ",")

//  ソートタイプのチェック
var orderType:OrderType = OrderType(rawValue: String(inputValueList.last ?? "")) ?? OrderType.none

if(orderType == OrderType.none){
    print("ソート方法を指定してください")
    print("指定がないため、昇順ソートを行います")
    
    orderType = OrderType.ascending
}else{
    //  ソート指定は邪魔なので取り除く
    inputValueList.removeLast()
}

//  入力文字列のタイプを判定
let valueType = CheckValueType(targetValueList: inputValueList)

//  ソート処理
var sortedNumberList:Array<Substring> = Array<Substring>()
sortedNumberList = Sort(targetNumberList:inputValueList)

//  何をソートしたか表示
switch valueType {
case .Number:
    print(ValueType.Number.rawValue + "ソート完了")
case .Charactor:
    print(ValueType.Charactor.rawValue + "ソート完了")
case .Japanese:
    print(ValueType.Japanese.rawValue + "ソート完了")
case .Iregular:
    print(ValueType.Iregular.rawValue + "ソート完了")
}

//  ソートタイプによって出力を切り替え
switch orderType {
case .ascending:
    print(sortedNumberList)
case .descending:
    print(Array(sortedNumberList.reversed()))
case .none:
    print("ソート失敗")
}

//  =====================================

//  ============== メソッド ===============
//  値のタイプを判定
func CheckValueType(targetValueList:Array<Substring>)-> ValueType{
    var retVal : ValueType = ValueType.Iregular
    let targetValueCount = targetValueList.count
    
    var numberCount = 0
    var charCount = 0
    var japaneseCount = 0
    
    //  数字の並びかチェック
    for i in 0...inputValueList.count - 1{
        let str:Int = Int(inputValueList[i].cString(using: .shiftJIS)!.first!)
        if(str >= 48 && str <= 57){         //  数字
            numberCount += 1
        }else if(str >= 97 && str <= 122){  //  小文字
            charCount += 1
        }else if(str >= 65 && str <= 90){   //  大文字
            charCount += 1
        }else if(str == -125){              //  ひらがな
            japaneseCount += 1
        }else if(str == -126){              //  カタカナ
            japaneseCount += 1
        }
    }
    
    
    if(numberCount == targetValueCount){
        retVal = ValueType.Number
    }else if(charCount == targetValueCount){
        retVal = ValueType.Charactor
    }else if(japaneseCount == targetValueCount){
        retVal = ValueType.Japanese
    }else{
        retVal = ValueType.Iregular
    }
    
    return retVal
}

//  ソート処理
func Sort(targetNumberList:Array<Substring>)->Array<Substring>{
    
    var sortList = targetNumberList
    var isChange = false
    
    for index in 0...sortList.count - 1{
        
        if(index + 1 == sortList.count)
        {
            break
        }
        
        let firstList = sortList[index].cString(using: .shiftJIS)!
        var firstSign = 1
        var firstJapaneseSign = 0
        
        let firstCheckValue = firstList.first!
        if(firstCheckValue == 45 )   //  マイナス符号
        {
            firstSign = -1
        }
        
        if(firstCheckValue == -125 ||  //  ひらがな
            firstCheckValue == -126)    //  カタカナ
        {
            firstJapaneseSign = Int(firstCheckValue) * -1
        }
        
        
        var first:Int = 0
        
        for fc in firstList{
            first += Int(fc) * firstSign
        }
        
        if(firstJapaneseSign != 0){
            first  *= firstJapaneseSign
        }
        
        
        let secondList = sortList[index+1].cString(using: .shiftJIS)!
        
        var secondSign = 1
        var secondJapaneseCheckSign = 0
        
        let secondCheckValue = secondList.first!
        if(secondCheckValue == 45)   //  マイナス符号
        {
            secondSign = -1
        }
        
        if(secondCheckValue == -125 ||  //  ひらがな
            secondCheckValue == -126)    //  カタカナ
        {
            secondJapaneseCheckSign = Int(secondCheckValue) * -1
        }
        var second:Int = 0
        
        for sc in secondList{
            second += Int(sc) * secondSign
        }
        
        if(secondJapaneseCheckSign != 0){
            second *= secondJapaneseCheckSign
        }

        
        let firstValue = sortList[index]
        let secondValue = sortList[index+1]
        
        if(first > second)
        {
            isChange = true

            sortList[index] = secondValue
            sortList[index + 1] = firstValue
        }
    }
    
    if(isChange){
        sortList = Sort(targetNumberList: sortList)
    }
    
    return sortList
}
//  =======================================

import UIKit

var targetMaze = [
    ["#","S","#","#","#","#","#","#","#","#","#"],
    ["#"," ","#","#","#","#","#","#"," ","#","#"],
    ["#"," "," "," "," ","#","#"," "," ","#","#"],
    ["#"," ","#","#"," "," "," "," ","#","#","#"],
    ["#","#","#","#"," ","#","#","#","#","#","#"],
    ["#"," "," "," "," ","#"," "," "," ","#","#"],
    ["#"," ","#","#","#","#"," ","#"," ","#","#"],
    ["#"," ","#","#","#","#"," ","#"," ","#","#"],
    ["#"," "," "," "," "," "," ","#"," ","#","#"],
    ["#","#","#","#","#","#","#","#","G","#","#"]
]

enum MapType:String
{
    case Start = "S"
    case Goal = "G"
    case Wall = "#"
    case Root = "+"
}

struct Vec2:Equatable{
    var X:Int = 0
    var Y:Int = 0
}

struct Direction
{
    var Now:Vec2

    var Up:Vec2?
    var Down:Vec2?
    var Right:Vec2?
    var Left:Vec2?
}

func CheckRoad(maze:[[String]],pos:Vec2?,beforPos:Vec2,maxPos:Vec2,checkType:MapType)-> Direction?
{
    if(pos == nil) {
        return nil
    }

    //  上,右,下,左
    var retPos:Direction = Direction(Now:pos!,Up:nil,Down: nil,Right: nil,Left: nil)

    //  上下左右の座標を取得
    let minusY = retPos.Now.Y - 1
    let plusY = retPos.Now.Y + 1
    let minusX = retPos.Now.X - 1
    let plusX = retPos.Now.X + 1

    // マップ内かチェック
    if(minusY >= 0){
        retPos.Down = Vec2()
    }
    if(plusY < maxPos.Y){
        retPos.Up = Vec2()
    }
    if(minusX >= 0){
        retPos.Left = Vec2()
    }
    if(plusX < maxPos.X){
        retPos.Right = Vec2()
    }

    //  壁があるかチェック
    if(retPos.Down == Vec2() &&
        (maze[minusY][retPos.Now.X] != checkType.rawValue) &&
        beforPos != Vec2(X: retPos.Now.X, Y: minusY))
    {
        retPos.Down = Vec2(X:retPos.Now.X,Y:minusY)
    }
    else{
        retPos.Down = nil
    }

    if(retPos.Up == Vec2() &&
        (maze[plusY][retPos.Now.X] != checkType.rawValue) &&
       beforPos != Vec2(X: retPos.Now.X, Y: plusY))
    {
        retPos.Up = Vec2(X:retPos.Now.X,Y:plusY)
    }else{
        retPos.Up = nil
    }

    if(retPos.Left == Vec2() &&
        (maze[retPos.Now.Y][minusX] != checkType.rawValue) &&
        beforPos != Vec2(X: minusX, Y: retPos.Now.Y))
    {
        retPos.Left = Vec2(X:minusX,Y:retPos.Now.Y)
    }else{
        retPos.Left = nil
    }

    if(retPos.Right == Vec2() &&
        (maze[retPos.Now.Y][plusX] != checkType.rawValue) &&
        beforPos != Vec2(X: plusX, Y: retPos.Now.Y))
    {
        retPos.Right = Vec2(X:plusX,Y:retPos.Now.Y)
    }else{
        retPos.Right = nil
    }


    return retPos
}

// 指定したターゲットの位置を返す
// 見つからなかった場合は、nilが返えってくる
func serchTargetPoint(maze:[[String]],targetMapType:MapType)->Vec2?
{
    var retPos:Vec2? = nil

    let mazeYCount = maze.count - 1
    let mazeXCount = maze[0].count - 1

    for Y in 0...mazeYCount
    {
        for X in 0...mazeXCount{
            let checkValue = maze[Y][X]

            if(checkValue == targetMapType.rawValue)
            {
                retPos = Vec2(X:X,Y:Y)
            }
        }
    }

    return retPos
}

func printMaze(maze:[[String]]){

    let mazeYCount = maze.count - 1
    let mazeXCount = maze[0].count - 1

    for Y in 0...mazeYCount
    {
        print("\n")
        for X in 0...mazeXCount{
            print(maze[Y][X], terminator: "")
        }
    }

    print("\n")
}


printMaze(maze:targetMaze)

let SPos = serchTargetPoint(maze:targetMaze,targetMapType:MapType.Start)
let GPos = serchTargetPoint(maze:targetMaze,targetMapType:MapType.Goal)

print(SPos ?? "スタートなし")
print(GPos ?? "ゴールなし")


let mazeYCount = targetMaze.count - 1
let mazeXCount = targetMaze[0].count - 1

let maxPos = Vec2(X: mazeYCount, Y: mazeXCount)

var RootList:Array<Direction> = Array<Direction>()
RootList.append (CheckRoad(maze:targetMaze,pos: SPos,beforPos: Vec2(X: 0,Y: 0),maxPos: maxPos,checkType: MapType.Wall)!)


var BlackList:Array<Vec2> = Array<Vec2>()

while true {

    let direction = CheckRoad(maze:targetMaze,pos: RootList.last?.Up ?? nil,beforPos: RootList.last?.Now ?? Vec2(),maxPos: maxPos,checkType: MapType.Wall)

    var checkFlag:Bool = false

    for black in BlackList
    {
        if(black == direction?.Now ?? Vec2())
        {
            checkFlag = true
        }
    }

    if(GPos == direction?.Now ?? Vec2())
    {
        break
    }


    if(direction != nil && !checkFlag)
    {
        RootList.append(direction!)
    }else
    {
        let direction = CheckRoad(maze:targetMaze,pos: RootList.last?.Right ?? nil,beforPos: RootList.last?.Now ?? Vec2(),maxPos: maxPos,checkType: MapType.Wall)

        var checkFlag:Bool = false

        for black in BlackList
        {
            if(black == direction?.Now ?? Vec2())
            {
                checkFlag = true
            }
        }

        if(GPos == direction?.Now ?? Vec2())
        {
            break
        }


        if(direction != nil && !checkFlag)
        {
            RootList.append(direction!)
        }else
        {
            let direction = CheckRoad(maze:targetMaze,pos: RootList.last?.Down ?? nil,beforPos: RootList.last?.Now ?? Vec2(),maxPos: maxPos,checkType: MapType.Wall)

            var checkFlag:Bool = false

            for black in BlackList
            {
                if(black == direction?.Now ?? Vec2())
                {
                    checkFlag = true
                }
            }

            if(GPos == direction?.Now ?? Vec2())
            {
                break
            }


            if(direction != nil && !checkFlag)
            {
                RootList.append(direction!)
            }else
            {
                let direction = CheckRoad(maze:targetMaze,pos: RootList.last?.Left ?? nil,beforPos: RootList.last?.Now ?? Vec2(),maxPos: maxPos,checkType: MapType.Wall)

                var checkFlag:Bool = false

                for black in BlackList
                {
                    if(black == direction?.Now ?? Vec2())
                    {
                        checkFlag = true
                    }
                }

                if(GPos == direction?.Now ?? Vec2())
                {
                    break
                }

                if(direction != nil && !checkFlag)
                {
                    RootList.append(direction!)
                }else
                {
                    BlackList.append(RootList.last?.Now ?? Vec2())
                    if(RootList.count > 0)
                    {
                        RootList.removeLast()
                    }else
                    {
                        break
                    }
                }
            }
        }
    }
}

for root in RootList
{
    print(root.Now)
    targetMaze[root.Now.Y][root.Now.X] = MapType.Root.rawValue
}

printMaze(maze:targetMaze)