battleship-board

Battleship Board

Battleship Board

You are given a string representing a “battleship board” of arbitrary width and height.

Each line is a row and each . is an empty cell. A series of the same letter in a row represents a ship positioned either vertically or horizontally.

How many ships of each length are on the board?

Example:

..AAA.......
..........CC
......B.....
......B.....
.AAAAAB..B.A
.........B.A
..BBBB..CCCA
.....CCC...A
........AA.A

Answer:

• Size 2: 3
• Size 3: 4
• Size 4: 1
• Size 5: 2

Implementation - the easy way (Racket)

There are a couple ways to do this - we can use a trick to go line by line and us regex to pull out all instances of letters A-Z with more than one of the same letter in a row

Something like this will pull out all instances of capital letters that occur more than once consequitively in a row

(regexp-match* #px"([A-Z])\\1+" "C.BBBB..CCCA")

We could run this on all lines giving us all horizontal ships

(require threading)

(define get-ships (lambda~>> (regexp-match* #px"([A-Z])\\1+")))

(define lines->horizontal-ships (lambda~>> (map get-ships)
                                           flatten))

<<requires>>
<<lines->horizontal-ships>>
(define board-lines (string-split board "\n"))
(lines->horizontal-ships board-lines)

'("AAA" "CC" "AAAAA" "BBBB" "CCC" "CCC" "AA")

Then rotate the board and check again giving us all veritcal ships. See this StackOverflow for an explanation on matrix rotation.

(define rotate-lines (lambda~>> (map string->list)
                                (apply map list)
                                (map list->string)))

<<requires>>
<<rotate-lines>>
(rotate-lines (string-split board "\n"))

'("........." "....A...." "A...A.B.." "A...A.B.." "A...A.B.." "....A.BC." "..BBB..C." ".......C." "......C.A" "....BBC.A" ".C....C.." ".C..AAAAA")

<<rotate-lines>>
<<lines->horizontal-ships>>
(define (lines->all-ships board-lines)
  (~>> board-lines
       rotate-lines
       lines->horizontal-ships
       (append (lines->horizontal-ships board-lines))))

<<requires>>
<<lines->all-ships>>
(lines->all-ships (string-split board "\n"))

'("AAA" "CC" "AAAAA" "BBBB" "CCC" "CCC" "AA" "BBB" "BB" "AAAAA")

And now we just group by length and sum up each group

<<requires>>
<<lines->all-ships>>
(~>> board
     (string-split _ "\n")
     lines->all-ships
     (group-by string-length)
     (map (lambda (ships) (~a "number of ships of length " (string-length (first ships)) ": " (length ships)))))

'("number of ships of length 3: 4" "number of ships of length 2: 3" "number of ships of length 5: 2" "number of ships of length 4: 1")

There we go!

Utils

(require threading)
(require racket/format)

Implementation (Js)

The Racket version with regex works, but its multiple passes what we could do in one (sorta). Instead, lets walk the board top left accross and down, skipping over previously visited cells. When we hit a letter, we try to find all instances of it downward and accross to find the current ship (because of how we’re moving down the board, only down and to the right are possibilities).

const isLetter = c => /^[A-Z]$/.test(c)
const valuesToTuple = (...args) => args
const zipLongest = function * (padding, ...collections) {
    if(!collections.length) return
    const its = collections.map(c => c[Symbol.iterator]())
    while(true) {
        const nexts = its.map(it => it.next())
        if(nexts.every(n => n.done))
            return
        yield nexts.map(n => n.done ? null : n.value)
    }
}

const getShips = function * (boardLines) {
    const rowCount = boardLines.length
    const visitedVerticalShipCells = new Set()
    for(const [line, row] of boardLines.map(valuesToTuple)) {
        const enumeratedLineWithNext = Array.from(zipLongest(null, line, line.substring(1))).map(valuesToTuple)
        const lineIt = enumeratedLineWithNext[Symbol.iterator]()
        for(let [[c, nextC], col] of lineIt) {
            //console.log(`${c}=>${nextC} (${row}, ${col})`)
            if(isLetter(c) && !visitedVerticalShipCells.has(`${row}, ${col}`)) {
                let ship = c
                if(c === nextC) { // the ship is horizontal
                    let {done, value: [[c2, nextC2], col]} = lineIt.next()
                    while(!done && c2 === c) {
                        ship += c2
                        if(nextC2 !== c)
                            break
                        ({done, value: [[c2, nextC2], col]} = lineIt.next())
                    }
                    yield ship
                } else { // the ship is vertical
                    for(let r2 = row+1; r2 < rowCount; r2+=1)
                        if(c === boardLines[r2][col]) {
                            ship += c
                            visitedVerticalShipCells.add(`${r2}, ${col}`)
                        }
                    yield ship
                }
            }
        }
    }
}

const ships = [...getShips(board.split(`\n`))]
const lengthCounts = new Map()
for(const s of ships)
    lengthCounts.set(s.length, (lengthCounts.get(s.length)||0)+1)
return lengthCounts 

Map { 3 => 4, 2 => 3, 5 => 2, 4 => 1 }