Help with recursive block + forwarding (?)

1

Hi! I want to generate different ways to partition an integer, taking order into account. For example, for n = 3 we’d get

[0, 0, 3]
[0, 1, 2]
[0, 2, 1]
[0, 3, 0]
[1, 0, 2]
[1, 1, 1]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]
[3, 0, 0]

That’s for exercise 15 of AoC 2015.

In Ruby, a generator like this would work (could allocate less arrays, that’s an optimization to do after getting it right):

def each_partition(n, &block)
  each_partition2(n, n, &block)
end

def each_partition2(n, k)
  if k == 1
    yield [n]
  else
    0.upto(n) do |m|
      each_partition2(n - m, k - 1) do |partition|
        yield [m] + partition
      end
    end
  end
end

each_partition(3) do |partition|
  p partition
end

In Crystal, both methods could have the same name.

OK. I’ve read about using explicit block.calls for recursion due to block inlining, and also about block forwarding. I have tried to rewrite that in different ways, but do not manage to check all the marks so that it compiles.

Could you please help me?

2

Hi @fxn ! :wave:

When a block is captured you need to specify its type. This seems to work fine:

def each_partition(n, &block : Array(Int32) -> _)
  each_partition(n, n, &block)
end

def each_partition(n, k, &block : Array(Int32) -> _)
  if k == 1
    block.call([n])
  else
    0.upto(n) do |m|
      each_partition(n - m, k - 1) do |partition|
        block.call([m] + partition)
      end
    end
  end
end

each_partition(3) do |partition|
  p partition
end

Here, _ means the block can return anything (unrestricted). I used that because we don’t expect the block’s value to be of any given type.

3 Likes