Maximise adjacent numbers in a functional style (PE#11)

Question

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the [provided] 20×20 grid? [source]

This solution works, and works effectively instantly.

The algorithm is \$ O ( n ) \$, as it loops through the entire field a total of four times.

However, it seems like I should be able to do this in one pass, rather than four.

More pertinent: I'm still new to writing using the functional interfaces (map, reduce, slice) as opposed to a more procedural style, so I'd like any comments on the readability of the four passes that I make.

import java.util.*

val grid = """
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
""".trim()

fun main(args: Array<String>) {
    val numbers = mutableListOf<List<Int>>()
    Scanner(grid).use {
        while (it.hasNext()) {
            val line = mutableListOf<Int>()
            Scanner(it.nextLine()).use {
                while (it.hasNext()) line += it.nextInt()
            }
            numbers += line
        }
    }

    var product = 0

    // Horizontal
    for (y in 0 until numbers.size)
        for (x in 0 until numbers[y].size - 3)
            product = Math.max(product, numbers[y].slice(x..x + 3).reduce(Int::times))

    // Vertical
    for (y in 0 until numbers.size - 3)
        for (x in 0 until numbers[y].size)
            product = Math.max(product, numbers.slice(y..y + 3).map { it[x] }.reduce(Int::times))

    // Down Right
    for (y in 0 until numbers.size - 3)
        for (x in 0 until numbers[y].size - 3)
            product = Math.max(product, numbers.slice(y..y + 3).mapIndexed { i, it -> it[x + i] }.reduce(Int::times))

    // Down Left
    for (y in 0 until numbers.size - 3)
        for (x in 3 until numbers[y].size)
            product = Math.max(product, numbers.slice(y..y + 3).mapIndexed { i, it -> it[x - i] }.reduce(Int::times))

    println(product)
}

Answer 1

1. You can parse your grid using some very useful functions in kotlin-stdlib:

   val numbers = grid.lines().map { line -> line.split(' ').map(String::toInt) }
   

2. Personally I prefer "row/column" instead of "y/x". Thinking "y" before "x" is unnatural.

3. You can always define your own methods too which can improve readability. e.g.:

   fun Iterable<Int>.product(): Int = reduce(Int::times)
   

4. Instead of using Math.max you might check to see if the given product is greater than the currently known maximum product and then assign it if it is. This is minor but personally I prefer to avoid unnecessary assignments.

5. I wouldn't worry about trying to do all of this in one pass. Each directional slice has different row/column bounds so I think four separate loops is the clearest/cleanest.

6. You can remove some duplicated code when it comes to calculating the product and updating the maximum.

e.g.:

var product = 0

fun maximizeProduct(numbers: List<Int>) {
    with(numbers.product()) { if (this > product) product = this }
}

// Horizontal
for (y in 0 until numbers.size)
    for (x in 0 until numbers[y].size - 3)
        maximizeProduct(numbers[y].slice(x..x + 3))

// Vertical
for (y in 0 until numbers.size - 3)
    for (x in 0 until numbers[y].size)
        maximizeProduct(numbers.slice(y..y + 3).map { it[x] })

// Down Right
for (y in 0 until numbers.size - 3)
    for (x in 0 until numbers[y].size - 3)
        maximizeProduct(numbers.slice(y..y + 3).mapIndexed { i, it -> it[x + i] })

// Down Left
for (y in 0 until numbers.size - 3)
    for (x in 3 until numbers[y].size)
        maximizeProduct(numbers.slice(y..y + 3).mapIndexed { i, it -> it[x - i] })

println(product)

Answer 2

I think a better solution if you want to go through it just just once would be to make functions that extract the sum from given coordinates like my solution here done in javascript.

<html>
<head>
    <script src="https://code.jquery.com/jquery-2.2.4.js"></script>

</head>
<body>
    <div class="grid">
        <div class="row">08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08</div>
        <div class="row">49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00</div>
        <div class="row">81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65</div>
        <div class="row">52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91</div>
        <div class="row">22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80</div>
        <div class="row">24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50</div>
        <div class="row">32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70</div>
        <div class="row">67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21</div>
        <div class="row">24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72</div>
        <div class="row">21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95</div>
        <div class="row">78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92</div>
        <div class="row">16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57</div>
        <div class="row">86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58</div>
        <div class="row">19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40</div>
        <div class="row">04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66</div>
        <div class="row">88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69</div>
        <div class="row">04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36</div>
        <div class="row">20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16</div>
        <div class="row">20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54</div>
        <div class="row">01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48</div>
    </div>
    <div class="result"></div>
     <script type="text/javascript">

        (function ($) {
                var grid = $('.row').map(function (i,e) {
                    return [$(e).text().split(' ').map(function(e,i){return e*1;})];
                });
                var prodLeft = function(x,y){
                     return grid.length > y && grid[y].length > x+3? grid[y][x] * grid[y][x+1] * grid[y][x+2] * grid[y][x+3] : 0;
                };
                var prodDown = function(x,y){
                     return grid.length > y+3 && grid[y].length > x  ? grid[y][x] * grid[y+1][x] * grid[y+2][x] * grid[y+3][x] : 0;
                };
                var prodDownLeft = function(x,y){
                     return grid.length > y+3 && grid[y].length > x+3 ? grid[y][x] * grid[y+1][x+1] * grid[y+2][x+2] * grid[y+3][x+3] : 0;
                };
                var prodDownRight = function(x,y){
                     return grid.length > y+3 && x-3 >= 0 ? grid[y][x] * grid[y+1][x-1] * grid[y+2][x-2] * grid[y+3][x-3] : 0;
                };
                var largest = [function(){return 0}];
                grid.map(function(y,e){
                    e.map(function(e,x){    
                        largest = prodLeft(x,y)         > largest[0].apply(this,largest.slice(1)) ? [prodLeft,x,y] : largest;
                        largest = prodDown(x,y)         > largest[0].apply(this,largest.slice(1)) ? [prodDown,x,y] : largest;
                        largest = prodDownLeft(x,y)     > largest[0].apply(this,largest.slice(1)) ? [prodDownLeft,x,y] : largest;
                        largest = prodDownRight(x,y)    > largest[0].apply(this,largest.slice(1)) ? [prodDownRight,x,y] : largest;
                    });
                });
                $('.result').append('result: ').append(largest[0].apply(this,largest.slice(1)));
        })(jQuery);


    </script>
</body>