Daily Programmer 2015-04-08 solution

box.groovy

class Maze {
    class Cell {
        boolean n
        boolean s
        boolean w
        boolean e

        Cell(boolean n, boolean s, boolean w, boolean e) {
            this.n = n
            this.s = s
            this.w = w
            this.e = e
        }

        Cell[][] bisectPassage() {
            def bisected = new Cell[2][2]
            bisected[0][0] = new Cell(true, true, true, true)
            bisected[0][1] = new Cell(true, true, true, true)
            bisected[1][0] = new Cell(true, true, true, true)
            bisected[1][1] = new Cell(true, true, true, true)

            // North main wall
            bisected[0][0].n = this.n
            bisected[0][1].n = this.n
            // South main wall
            bisected[1][0].s = this.s
            bisected[1][1].s = this.s
            // West main wall
            bisected[0][0].w = this.w
            bisected[1][0].w = this.w
            // East main wall
            bisected[0][1].e = this.e
            bisected[1][1].e = this.e

            // North cross wall
            bisected[0][0].e = !this.n
            bisected[0][1].w = !this.n
            // South cross wall
            bisected[1][0].e = !this.s
            bisected[1][1].w = !this.s
            // West cross wall
            bisected[0][0].s = !this.w
            bisected[1][0].n = !this.w
            // East cross wall
            bisected[0][1].s = !this.e
            bisected[1][1].n = !this.e

            bisected
        }

        String toString() {
            def sb = ''<<''
            sb << "North: " << n
            sb << ", South: " << s
            sb << ", West: " << w
            sb << ", East: " << e
        }
    }

    private int _w
    private int _h

    int getW() {
        return _w
    }
    int getH() {
        return _h
    }

    Cell[][] cells

    Maze(int w, int h) {
        _w = w
        _h = h

        generate()
    }

    Maze(Cell[][] cells) {
        _h = cells.length
        _w = cells[0].length
        this.cells = cells
    }

    void generate() {
        // Initialize cells
        cells = new Cell[_h][_w]
        for (int i = 0; i < _h; i++) {
            for (int j = 0; j < _w; j++) {
                cells[i][j] = new Cell(true, true, true, true)
            }
        }

        // Depth-first search is easiest to implement
        // Start from center
        def (startX, startY) = [(int)w/2, (int)h/2]

        def stack = [[startX, startY]]
        def visited = [[startX, startY]].toSet()

        def rand = new Random()

        while (stack) {
            def (x, y) = stack[-1]

            def candidates = []
            if (x > 0    && !([x-1, y] in visited)) candidates << [x-1, y]
            if (x < _w-1 && !([x+1, y] in visited)) candidates << [x+1, y]
            if (y > 0    && !([x, y-1] in visited)) candidates << [x, y-1]
            if (y < _h-1 && !([x, y+1] in visited)) candidates << [x, y+1]

            if (!candidates) {
                stack.pop()
                continue
            }
            else {
                def nextCell = candidates[rand.nextInt(candidates.size())]
                def (nx, ny) = nextCell

                stack << nextCell
                visited << nextCell
                if (nx < x) {
                    cells[ y][ x].w = false
                    cells[ny][nx].e = false
                }
                else if (nx > x) {
                    cells[ y][ x].e = false
                    cells[ny][nx].w = false
                }
                else if (ny < y) {
                    cells[ y][ x].n = false
                    cells[ny][nx].s = false
                }
                else if (ny > y) {
                    cells[ y][ x].s = false
                    cells[ny][nx].n = false
                }
            }
        }
    }

    List solve(start, end) {
        // Depth-first search is easiest to implement
        // Start from center
        def stack = [start]
        def visited = [start].toSet()

        def rand = new Random()

        while (stack) {
            if (stack[-1] == end) break

            def (x, y) = stack[-1]

            def candidates = []
            if (x > 0    && !(cells[y][x].w) && !([x-1, y] in visited)) candidates << [x-1, y]
            if (x < _w-1 && !(cells[y][x].e) && !([x+1, y] in visited)) candidates << [x+1, y]
            if (y > 0    && !(cells[y][x].n) && !([x, y-1] in visited)) candidates << [x, y-1]
            if (y < _h-1 && !(cells[y][x].s) && !([x, y+1] in visited)) candidates << [x, y+1]

            if (!candidates) {
                stack.pop()
                continue
            }
            else {
                def nextCell = candidates[rand.nextInt(candidates.size())]
                def (nx, ny) = nextCell

                stack << nextCell
                visited << nextCell
                if (nx < x) {
                    cells[ y][ x].w = false
                    cells[ny][nx].e = false
                }
                else if (nx > x) {
                    cells[ y][ x].e = false
                    cells[ny][nx].w = false
                }
                else if (ny < y) {
                    cells[ y][ x].n = false
                    cells[ny][nx].s = false
                }
                else if (ny > y) {
                    cells[ y][ x].s = false
                    cells[ny][nx].n = false
                }
            }
        }

        return stack
    }

    void printMaze() {
        for (int i = 0; i < h; i++) {
            // this weird initialization makes them StringBuffers
            def line1 = '+'<<''
            def line2 = ''<<''
            for (int j = 0; j < w; j++) {
                if (cells[i][j].n)
                    line1 << '--+'
                else
                    line1 << '  +'

                if (cells[i][j].w)
                    line2 << '|  '
                else
                    line2 << '   '
            }
            line2 << '|'

            println line1
            println line2
        }
        
        // last line
        def lastline = ''<<''
        for (int j = 0; j < w; j++) {
            lastline << '+--'
        }
        lastline << '+'
        println lastline
    }

    List bisectPassages() {
        def bisectedCells = new Cell[_h*2][_w*2]
        for (int i = 0; i < _h; i++) {
            for (int j = 0; j < _w; j++) {
                def sector = cells[i][j].bisectPassage()
                bisectedCells[i*2  ][j*2  ] = sector[0][0]
                bisectedCells[i*2  ][j*2+1] = sector[0][1]
                bisectedCells[i*2+1][j*2  ] = sector[1][0]
                bisectedCells[i*2+1][j*2+1] = sector[1][1]
            }
        }

        // pick new start and close the loop
        def rand = new Random()
        def (startX, startY) = [rand.nextInt(_w*2), rand.nextInt(_h*2)]
        def (endX, endY) = [startX, startY]
        if (!(bisectedCells[startY][startX].n)) {
            bisectedCells[startY][startX].n = true
            endY--
            bisectedCells[endY][endX].s = true
        }
        else if (!(bisectedCells[startY][startX].s)) {
            bisectedCells[startY][startX].s = true
            endY++
            bisectedCells[endY][endX].n = true
        }
        else if (!(bisectedCells[startY][startX].w)) {
            bisectedCells[startY][startX].w = true
            endX--
            bisectedCells[endY][endX].e = true
        }
        else if (!(bisectedCells[startY][startX].e)) {
            bisectedCells[startY][startX].e = true
            endX++
            bisectedCells[endY][endX].w = true
        }
        
        def newMaze = new Maze(bisectedCells)

        return [newMaze, [startX, startY], [endX, endY]]
    }
}

void packSentenceBox(String sentence) {
    String letters = sentence.replaceAll("\\s", "").toUpperCase()

    int len = letters.length()
    int lenToMultFour = len + (4 - len%4) % 4

    int packedLen, width=0, height=0
    for (packedLen = lenToMultFour; width == 0; packedLen += 4) {
        for (int i = 2; width == 0 && i < packedLen; i++) {
            if (packedLen % i == 0 && (int)(packedLen / i) >= i &&
              (int)(packedLen / i) % 2 == 0 && i % 2 == 0 &&
              ((int)(packedLen / i) / Math.sqrt(packedLen)) - 1.0 < 0.2) {
                width = (int)((packedLen / i) / 2)
                height = (int)(i / 2)
            }
        }
    }

    while (letters.length() < packedLen) {
        letters += "%"
    }

    def maze = new Maze(width, height)
    def (unicursal, start, end) = maze.bisectPassages()

    def path = unicursal.solve(start, end)

    def box = new char[height*2][width*2]
    
    for (int i = 0; i < path.size(); i++) {
        def (x, y) = path[i];
        box[y][x] = letters.charAt(i)
    }

    println start.join(" ")
    for (int i = 0; i < box.size(); i++) {
        println box[i].join(" ")
    }
}

packSentenceBox(args[0])