Solution of estate division problem using hydraulic idea of Marek Kaminski

nucleolus-three-widows-estate-problem.rb

# https://www.researchgate.net/publication/265440203_How_the_Talmud
# http://gaidarfund.ru/articles/1983/

require 'rspec'

# @param amount - Integer, Float: amount of estate
# @param claims - Hash: { 'name of the creditor' => amount_of_claim }
# @return - Hash: { 'name of the creditor' => payment_amount }
def solve(amount, claims)
  amount_left = amount

  res = claims.map { |creditor, _| [creditor, 0] }.to_h
  claims_left = claims
  # Halves of the claims
  claim_stairs = claims.map { |creditor, debt| [creditor, debt/2.0] }.to_h

  # Fill the volume step by step, when it will be half-filled
  half_filled = false

  while amount_left > 0
    half_filled ||= claims_left.count == 1
    # Creditor with minimal claims
    min_creditor, min_claim = *claims_left.min_by { |creditor, _| claims[creditor] }

    # On each step divide equal amount of estate between claiming creditors
    step =
      if half_filled
        prev_creditor, _ = *claims
          .reject { |creditor, debt| claims[creditor] >= claims[min_creditor]  }
          .max_by { |creditor, debt| claims[creditor] }

        step =
          if prev_creditor
            (claims[min_creditor] - claim_stairs[prev_creditor]) - res[min_creditor]
          else
            claim_stairs[min_creditor]
          end

        if step == 0
          claims_left[prev_creditor] = claims[prev_creditor] - res[prev_creditor]
        elsif step * claims_left.count > amount_left
          step = amount_left / claims_left.count.to_f
        end

        step
      else
        step = claim_stairs[min_creditor] - res[min_creditor]
        amount_left >= step * claims_left.count ? step : amount_left / claims_left.count.to_f
      end

    claims_left.each do |creditor, _|
      res[creditor] += step
    end

    amount_left -= step * claims_left.count

    claims_left = claims_left
      .map { |creditor, debt| [creditor, debt - step] }
      .select { |_, debt| debt > 0 }
      .reject { |creditor, _| !half_filled && creditor == min_creditor }
      .to_h
  end

  res.map { |creditor, debt| [creditor, debt.truncate(1)] }.to_h
end

describe '#solve' do
  subject { solve(amount, claims) }

  let(:claims) { { 'widow1' => 100, 'widow2' => 200, 'widow3' => 300 } }

  context 'equal division' do
    let(:amount) { 100 }

    it { is_expected.to eq('widow1' => 33.3, 'widow2' => 33.3, 'widow3' => 33.3) }
  end

  context '150' do
    let(:amount) { 150 }

    it { is_expected.to eq('widow1' => 50.0, 'widow2' => 50.0, 'widow3' => 50.0) }
  end

  context 'strange division' do
    let(:amount) { 200 }

    it { is_expected.to eq('widow1' => 50.0, 'widow2' => 75.0, 'widow3' => 75.0) }
  end

  context '250' do
    let(:amount) { 250 }

    it { is_expected.to eq('widow1' => 50.0, 'widow2' => 100.0, 'widow3' => 100.0) }
  end

  context 'proportional division' do
    let(:amount) { 300 }

    it { is_expected.to eq('widow1' => 50.0, 'widow2' => 100.0, 'widow3' => 150.0) }
  end

  context '350' do
    let(:amount) { 350 }

    it { is_expected.to eq('widow1' => 50.0, 'widow2' => 100.0, 'widow3' => 200.0) }
  end

  context '400' do
    let(:amount) { 400 }

    it { is_expected.to eq('widow1' => 50.0, 'widow2' => 125.0, 'widow3' => 225.0) }
  end

  context '450' do
    let(:amount) { 450 }

    it { is_expected.to eq('widow1' => 50.0, 'widow2' => 150.0, 'widow3' => 250.0) }
  end

  context '500' do
    let(:amount) { 500 }

    it { is_expected.to eq('widow1' => 66.6, 'widow2' => 166.6, 'widow3' => 266.6) }
  end

  context '550' do
    let(:amount) { 550 }

    it { is_expected.to eq('widow1' => 83.3, 'widow2' => 183.3, 'widow3' => 283.3) }
  end

  context 'over half proportional division' do
    let(:amount) { 600 }

    it { is_expected.to eq('widow1' => 100.0, 'widow2' => 200.0, 'widow3' => 300.0) }
  end
end