snakesolver/snakesolver.functional.scala at master · steppicrew/snakesolver · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
object Main {

    val dim = 4
    val snake_short = List(
        (5, 1), (1, 2), (1, 1), (1, 6), (1, 1), (2, 2), (4, 2), (3, 4), (3, 5), (5, 2), (2, 4), (2, 2), (2, 0)
    )
    val exit_after_first_solution = true

    val dimp1 = dim + 1

    def buildSnake(snake: List[Tuple2[Int, Int]]):List[Int]=
        if (snake.isEmpty) Nil
        else (0 until snake.head._1).map(_ => 1).toList ::: (0 until snake.head._2).map(_ => 2).toList ::: buildSnake(snake.tail)

    val snake = buildSnake(snake_short)

    val visited= (0 to dimp1).map(
        x => (0 to dimp1).map(
            y => (0 to dimp1).map(
                z => (x, y, z)
            )
        ).reduce((a, b) => a ++ b)
    ).reduce((a, b) => a ++ b).filter(
        xyz => xyz._1 == 0 || xyz._1 == dimp1 || xyz._2 == 0 || xyz._2 == dimp1 || xyz._3 == 0 || xyz._3 == dimp1
    ).toSet

    val expected= (0 to dimp1).map(
        x => (0 to dimp1).map(
            y => (0 to dimp1).map(
                z => if (List(x, y, z).exists( i => i == 1 || i == dim)) List(x, y, z).map( i => (i + 3) / 2 ).reduce( (a, b) => a + b ) % 2 + 1 else 0
            )
        )
    )

    var tries = 0

    def get_cube(result: Seq[Seq[Seq[Int]]]) = {
        (1 to dim).map( z =>
            "z=" + z + "\n" +
            "\t+----+----+----+----+\t+---+---+---+---+\n" +

            (1 to dim).map( y =>
                "\t|" +

                (1 to dim).map( x =>
                    " %2d |".format(result(x)(y)(z))
                ).reduce( (a, b) => a + b) +

                "\t|" +

                (1 to dim).map( x =>
                    " " +
                    (if (result(x)(y)(z) < 0) "?" else if (snake(result(x)(y)(z)) == 1) "X" else " ") +
                    " |"
                ).reduce( (a, b) => a + b) +
                "\n\t+----+----+----+----+\t+---+---+---+---+\n"
            ).reduce( (a, b) => a + b)
        ).reduce( (a, b) => a + b) +
        "\n"
    }

    def print_solved(positions: Seq[Tuple3[Int,Int,Int]]) {
        print( "\n\nSOLVED with " + tries + " tries\n" )
        print( get_cube(
            (0 to dimp1).map(
                x => (0 to dimp1).map(
                    y => (0 to dimp1).map(
                        z => positions.indexOf((x, y, z))
                    )
                )
            )
        ) )

        if (exit_after_first_solution) System.exit(1)
    }

    def solve(positions: Seq[Tuple3[Int, Int, Int]], visited: Set[Tuple3[Int, Int, Int]]): Unit = {

        val xyz= positions.last

        if (positions.length == snake.length) {
//            print("Positions: " + positions + "\n")
//            print("Visited: " + visited + "\n")
            print_solved(positions)
            return
        }

        val expect= expected(xyz._1)(xyz._2)(xyz._3)
        if (expect != 0 && expect != snake(positions.length - 1)) {
//            print("color doesn't match: " + expect + " vs " + snake(positions.length - 1) + " at " + positions.length + "\n")
            return
        }

        tries += 1;
        if (tries % 300000 == 0) {
            println( "tries: " + tries + " " + xyz + " -> idx: " + positions.length + " (" + snake(positions.length) + ")")
        }

        Seq((1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0), (0, 0, 1), (0, 0, -1)).
            map(add => ( xyz._1 + add._1, xyz._2 + add._2, xyz._3 + add._3) ).
            filter( xyz => !visited.contains(xyz) ).
            map( xyz => solve(positions :+ xyz, visited + xyz) )
    }

    def main(args: Array[String]): Unit = {
        (1 to dim).map(
            x => (1 to dim).map(
                y => (1 to dim).map(
                    z => {
                        val xyz= (x, y, z)
                        print("Starting at " + xyz + "\n")
                        solve(Seq(xyz), visited + xyz)
                    }
                )
            )
        )
    }

}