patternkotlinMinor
Maximise adjacent numbers in a functional style (PE#11)
Viewed 0 times
adjacentnumbersmaximisestylefunctional
Problem
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 (
`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) {
val numbers = mutableListOf>()
Scanner(grid).use {
while (it.hasNext()) {
val line = mutableListOf
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) {
val numbers = mutableListOf>()
Scanner(grid).use {
while (it.hasNext()) {
val line = mutableListOf
Solution
-
You can parse your grid using some very useful functions in
-
Personally I prefer "row/column" instead of "y/x". Thinking "y" before "x" is unnatural.
-
You can always define your own methods too which can improve readability. e.g.:
-
Instead of using
-
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.
-
You can remove some duplicated code when it comes to calculating the product and updating the maximum.
e.g.:
You can parse your grid using some very useful functions in
kotlin-stdlib:val numbers = grid.lines().map { line -> line.split(' ').map(String::toInt) }-
Personally I prefer "row/column" instead of "y/x". Thinking "y" before "x" is unnatural.
-
You can always define your own methods too which can improve readability. e.g.:
fun Iterable.product(): Int = reduce(Int::times)-
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.-
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.
-
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) {
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)Code Snippets
val numbers = grid.lines().map { line -> line.split(' ').map(String::toInt) }fun Iterable<Int>.product(): Int = reduce(Int::times)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)Context
StackExchange Code Review Q#140082, answer score: 2
Revisions (0)
No revisions yet.