Trying to understand Kotlin yield, working on AoC 2015 Day 15

[Junilu Lacar]

Hi folks,

More Advent of Code adventures. Been working on Day 15 which asks to find the best mix of ingredients for a cookie. https://adventofcode.com/2015/day/15

I guess it's a variation of the Knapsack_problem. I couldn't figure out the algorithm without hardcoding so I resorted to stealing. Finally found a general solution but in Python. It used yield. Kotlin has a similar construct. Here's my Kotlin adaptation that worked:

fun proportions(parts: Int, total: Int): Sequence<IntArray> = sequence {
    val start = if (parts == 1) total else 0
    for (portionSize in (start..total)) {
        if (parts <= 1) {
            yield(intArrayOf(portionSize))
        }  else {
            for (portion in proportions(parts - 1, total - portionSize)) {
                yield(intArrayOf(portionSize) + portion)
            }
        }
    }
}

I tried the code below, thinking I could treat yield like a return, but it didn't work.

fun proportions(parts: Int, total: Int): Sequence<IntArray> = sequence {
    val start = if (parts == 1) total else 0
    for (portionSize in (start..total)) {
        if (parts <= 1) {
            yield(intArrayOf(portionSize))
        }  
        for (portion in proportions(parts - 1, total - portionSize)) {
            yield(intArrayOf(portionSize) + portion)
        }
    }
}

This version behaved like it got stuck in an endless loop in the inner for-loop. Not exactly sure why. Any help understanding what's going on here will be greatly appreciated. Thanks.

[Stephan van Hulst]

I will explain how yield in C# works, because I don't have a lot of experience with Kotlin. If Kotlin works the same way, then you have your answer.

In C#, yield is used when you want to return a lazily enumerated sequence. When execution reaches a yield statement, it returns the next element in the sequence.

So yes, yield is like return in that execution of the function is suspended, and a value is returned. However, yield is different in the following two ways:

yield returns a single element of the sequence, whereas return would return the entire sequence,

when the next element of the sequence is needed, execution of the function continues from the last yield,

The base case of your recursive call yields an element, but it doesn't cause your recursive call to unwind, because when the next element is needed, execution continues after the yield statement. In your second snippet, that means the inner for-loop is executed even if parts <= 1.

Again, I don't know Kotlin well enough to be certain that this will work, but in your second code snippet, try adding an empty return after your yield.

[Mike Simmons]

I believe Kotlin's yield does work pretty much as Stephan explained for C#.  The key part being that yes, execution will resume after a yield statement.  So you have to worry about what happens when the value of parts is 1, 0, or negative.  You might add some print statements within the code to see what's happening - I suspect you'll see it running toward negative infinity...

[Piet Souris]

No complicated yields here.

I did it two ways:

first, plain brute force. Very easy and it ran in 0 seconds.

second: look at the example given. Say you have A spoons of the first ingredient, and B spoons of the second. Then we have

                                                    constraint:
capacity:      -A + 2B                        -A + 2B > 0
durability:   -2A + 3B                      -2A + 3B > 0
flavor:          6A -2B                          6A - 2B > 0
texture:       3A - B                            3A - B > 0
and:                                                    0 <= A <= 100
                                                          B = 100 - A

You can put this in Excel (data -> solver) and maximize for

(-A + 2B) * (-2A + 3B) * (6A - 2B) * (3A - B)

(that tt-tag, (monospaced font) does a terrific job!