Fruit bagging factory

Question

Your mission is to build an algorithm (program or function) that can optimize packing fruit from a conveyor belt into bags to be sent off to retailers, optimizing for a largest number of bags.

Each bag has to weight at least a certain amount, but any excess is lost profit since that weight could be used to fill another bag. Your bagging machine has always a lookahead of n fruits from the queue and may only choose to add any of these n fruits to the (single) bag that is being processed. It cannot look beyond the n first elements in the queue. The program always knows exactly how much weight there already is in the bag.

Another way to visualize this is having a conveyor belt with a loading area of size n at the end, from where a fruit has to be taken before a new fruit arrives. Any leftover fruit and a non-full bag at the end are discarded.

Inputs

• List/array of weights of fruits in queue (positive integers)
• Minimum total weight for bags (positive integer)
• Lookahead n (positive integer)

Output

Your algorithm should return for all bags the weights of the fruits in them, by whatever means is convenient for you and your language, be that stdin or a return value or something else. You should be able to run the program and calculate your score in one minute on your computer.

Example

Total weight 1000, lookahead of 3 and fruit queue: 
[171,163,172,196,156,175,162,176,155,182,189,142,161,160,152,162,174,172,191,185]

One possible output (indented to show how the lookahead affects the bagging):
[171,163,172,    156,175,    176]
                        [162,    155,182,189,    161,160]
                                                        [152,162,174,172,191,185]

Scoring

Your algorithm will be tested on six runs on a batch of 10000 oranges I have prepared for you, on lookaheads ranging from 2 to 7, inclusive on both ends. You shall pack them into bags weighing at least 1000 units. The oranges are normally distributed with a mean weight of 170 and a standard deviation of 13, if that is of any help.

Your score will be the sum of number of bags from the six runs. The highest score wins. Standard loopholes are disallowed.

Simple example implementation and test suite boilerplate in Haskell

Answer 1

Python 3, 9964 9981 bags

The idea of this solution is similar to those of Jonathan, JayCe and fortraan, but with a scoring function =)

This solution appends the best subsets of the lookahead area accoring to the score.

score provides an order over the subsets using the following scheme:

• A subset completing a bag is better than one that's not
• One subset completing a bag is better than another if it has less excess weight
• One subset not completing a bag is better than another if its mean is closer to what's expected to be in a bag

expected_mean tries to predict what the rest of the values should look like (assuming their choice is optimal).

UPD:

Here is another observation: you can place any oranges from the best subset into the bag without hurting the algorithm's performance. Moving any part of it still allows to move the rest afterwards, and the remainder should still be the best option (without new oranges) if the scoring is right. Moreover, this way there is a chance to dynamically improve the set of candidates to put into the bag by seeing more oranges before filling the bag. And you want to know as much information as possible, so there is no point in moving more than one orange to the bag at any given time.

import itertools as it
import math
from functools import partial
from collections import Counter


mean, std = 170, 13


def powerset(list_, max_items):
    return it.chain.from_iterable(it.combinations(list_, r) for r in range(1, max_items + 1))


def expected_mean(w):
    spread = std * 1
    return max(mean - spread, min(mean + spread, w / max(1, round(w / mean))))


def score(weight_needed, candidate):
    c_sum = sum(candidate)
    c_mean = c_sum / len(candidate)
    if c_sum >= weight_needed:
        return int(-2e9) + c_sum - weight_needed
    return abs(expected_mean(weight_needed) - c_mean)


def f(oranges, min_bag_weight, lookahead):
    check = Counter(oranges)

    oranges = oranges.copy()
    result = []
    bag = []

    while oranges:
        weight_needed = min_bag_weight - sum(bag)

        lookahead_area = oranges[:lookahead]
        tail = oranges[lookahead:]

        to_add = min(powerset(lookahead_area, lookahead),
                     key=partial(score, weight_needed))
        to_add = min(powerset(to_add, 1),
                     key=partial(score, weight_needed))

        bag.extend(to_add)
        for x in to_add:
            lookahead_area.remove(x)
        oranges = lookahead_area + tail

        if sum(bag) >= min_bag_weight:
            result.append(bag)
            bag = []

    assert check == Counter(oranges) + Counter(bag) + sum(map(Counter, result), Counter())

    return result


if __name__ == '__main__':
    with open('oranges') as file:
        oranges = list(map(int, file))
    res = [f(oranges, 1000, l) for l in range(2, 7+1)]
    print(sum(map(len, res)))

Try it!

Answer 2

Python 3, 9796 bags

Building on Jonathan's answer:

import itertools as it

def powerset(iterable):
    s = list(iterable)
    return it.chain.from_iterable(it.combinations(s, r) for r in range(len(s)+1))

def f(a,m,l):
 r=[];b=[]
 while a:
  c =  min(list(powerset(a[:l])),key=lambda w: abs(sum(b)+sum(w)-m))
  if sum(c)==0:
   c = a[:l]
  b+=[a.pop(a.index(min(c,key=lambda w: abs(sum(b)+w-m))))]
  if sum(b)>=m:r+=[b];b=[]
 return r

This relies on powerset from itertool's cookbook. First finds optimal subset of the buffer based on minimizing difference from target weight for all subsets, and then picks an element out of this subset based on same criterion. If no optimal subset selects from the whole buffer.

Answer 3

C++17, 9961.58 _{(average over some random seeds)}

(scroll down for explanation if you don't know C++)

#include<iostream>

#include<vector>
#include<random>

std::mt19937 engine(279); // random engine
// random distribution of the oranges
std::normal_distribution dist (170.,13.);

int constexpr N_NEW_ORANGES=7;

/** Input format: Current remaining weight of the bag (remain) and 
the weight of the oranges (weights)
Output: the index of the orange to be pick.
*/
struct pick_orange{
    std::vector<int>weights,sum_postfix;int remain;

    /// returns {min excess, mask}, (index) is the LSB
    std::pair<int,int> backtrack(int index, int remain) {
        if(sum_postfix[index]<remain)return {1e9,0};
        int min_excess=1e9, good_mask=0;
        for(int next=index;next<N_NEW_ORANGES;++next){
            if(weights[next]==remain){
                return {0, 1<<(next-index)};
            }else if(weights[next]>remain){
                if(weights[next]-remain<min_excess){
                    min_excess=weights[next]-remain;
                    good_mask=1<<(next-index);
                }
            }else{
                auto[excess,mask]=backtrack(next+1,remain-weights[next]);
                if(excess<min_excess){
                    min_excess=excess;
                    good_mask=(mask<<1|1)<<(next-index);
                }
            }
        }
        return {min_excess,good_mask};
    } 

    int ans;

    pick_orange(std::vector<int> weights_,int remain_)
        :weights(std::move(weights_)),remain(remain_){

        int old_size=weights.size();

        std::vector<int> count (N_NEW_ORANGES, 0);
        weights.resize(N_NEW_ORANGES, 0);

        sum_postfix.resize(N_NEW_ORANGES+1);
        sum_postfix.back()=0;

        for(int _=0; _<500; ++_){

            for(int i=old_size;i<N_NEW_ORANGES;++i)
                weights[i] = dist(engine);

            // prepare sum postfix
            for(int i=N_NEW_ORANGES;i-->0;)
                sum_postfix[i]=weights[i]+sum_postfix[i+1];

            // auto[excess,mask]=backtrack(0,remain);
            int mask = backtrack(0,remain).second;

            for(int i=0; 

                mask
                // i < N_NEW_ORANGES

                ; mask>>=1, ++i){

                // if(mask&1)std::cout<<'(';
                // std::cout<<weights[i];
                // if(mask&1)std::cout<<')';
                // std::cout<<' ';

                count[i]+=mask&1;
            }

            // std::cout<<"| "<<remain<<" | "<<excess<<'\n';

        }

        std::vector<double> count_balanced(old_size, -1);
        for(int i=0;i<old_size;++i){
            if(count_balanced[i]>-1)continue;
            int sum=0,amount=0;
            for(int j=i;j<old_size;++j)
                if(weights[j]==weights[i]){sum+=count[j];++amount;}

            double avg=sum;avg/=amount;
            for(int j=i;j<old_size;++j)
                if(weights[j]==weights[i])count_balanced[j]=avg;
        }

        ans=old_size-1;
        for(int i=ans;i-->0;)
            if(count_balanced[i]>count_balanced[ans])ans=i;
        // Fun fact: originally I wrote `<` for `>` here and wonder
        // why the number of bags is even less than that of the
        // randomized algorithm
    }

    operator int()const{return ans;}
};


#include<iostream>
#include<fstream>
#include<algorithm>

int main(){
    // read input from the file "data"
    std::ifstream data ("data");
    std::vector<int> weights;
    int weight;while(data>>weight)weights.push_back(weight);

    int constexpr BAG_SIZE=1000;
    int total_n_bag=0;
    for(int lookahead=2;lookahead<=7;++lookahead){
        auto weights1=weights;
        std::reverse(weights1.begin(),weights1.end());

        int remain=BAG_SIZE,n_bag=0;
        std::vector<int> w;
        for(int _=lookahead;_--;){
            w.push_back(weights1.back());
            weights1.pop_back();
        }
        while(!weights1.empty()){
            int index=pick_orange(w,remain);

            remain-=w[index];
            if(remain<=0){
                ++n_bag;remain=BAG_SIZE;

                if(n_bag%100==0)
                    std::cout<<n_bag<<" bags so far..."<<std::endl;
            }
            w[index]=weights1.back();weights1.pop_back();
        }

        while(!w.empty()){
            int index=pick_orange(w,remain);
            remain-=w[index];
            if(remain<=0){++n_bag;remain=BAG_SIZE;}
            w.erase(w.begin()+index);
        }

        std::cout<<"lookahead = "<<lookahead<<", "
            "n_bag = "<<n_bag<<'\n';
        total_n_bag += n_bag;
    }

    std::cout<<"total_n_bag = "<<total_n_bag<<'\n';
}

// Fun fact: originally I wrote < for > here and wonder
// why the number of bags is even less than that of the
// randomized algorithm

(if < is used basically the algorithm tries to minimize the number of bags)

Inspired by this answer.

TIO link for 250 repetitions: Try it online!

---

Defines a function (actually it just looks like a function, it's a struct) pick_orange that, given a vector<int> weights the weight of the oranges and int remain the remaining weight of the bag, returns the index of the orange that should be picked.

Algorithm:

repeat 500 times {
generates random (fake) oranges (normal distribution with mean 170 and stddev 13) until there are N_NEW_ORANGES=7 oranges
pick any subset whose sum is smallest and not smaller than remain (the function backtrack does that)
mark all oranges in that subset as good
}

average out the number of times an oranges being marked as good of the (real) oranges with equal weight
return the best orange

---

There are 3 hardcoded constants in the program that cannot be inferred from the problem:

• The random seed (this is not important)
• N_NEW_ORANGES (the prediction length). Increasing this makes the program runs exponentially longer (because backtrack)
• number of repetitions. Increasing this makes the program runs linearly longer.

Answer 4

Python 2, 9756 bags

Let's get the orange rolling...

def f(a,m,l):
 r=[];b=[]
 while a:
  b+=[a.pop(a.index(min(a[:l],key=lambda w:abs(sum(b)+w-m))))]
  if sum(b)>=m:r+=[b];b=[]
 return r

Try it online!

Always picks the fruit from the buffer which minimises the absolute difference of the new weight and the target weight.

Answer 5

Python 3, 9806 bags

Building on Jonathan and JayCe's answers:

import itertools as it

def powerset(iterable):
    s = list(iterable)
    return it.chain.from_iterable(it.combinations(s, r) for r in range(len(s)+1))

def f(a,m,l):
 r=[];b=[]
 while a:
  c =  min(list(powerset(list(reversed(sorted(a[:l]))))),key=lambda w: abs((sum(b)+sum(w))-m))
  if sum(c)==0:
   c = a[:l]
  b+=[a.pop(a.index(min(c,key=lambda w: abs((sum(b)+w)-m))))]
  if sum(b)>=m:r+=[b];b=[]
 return r

Try it online!

How it works

Say that the bag has 900 units in it, and there are 2 fruit available: a 99 unit fruit and a 101 unit fruit. If the 99 unit fruit is closer to the beginning of the lookahead list, then min will select it instead of 101. If this happens, we would now need another fruit to fulfill the remaining 1 unit needed. I changed the program to favor the higher-valued fruit in these cases.

It does this by sorting and then reversing the lookahead list before powersetting.

Answer 6

PHP, 9975 bags

• If possible go for 5 oranges
• When starting bag pick extreme value, balance later
• If possible fill bag immediately
• Try to keep bag weight close to estimated curve (n*200 for 5bag, n*167 for 6bag, etc)

longest out of all submissions but should be readable

class Belt
{
    private $file;
    private $windowSize;
    private $buffer = [];

    public function __construct($filename, $windowSize) {
        $this->file = new \SplFileObject($filename);
        $this->windowSize = $windowSize;
        $this->loadBuffer();
    }

    public function reset($windowSize) {
        $this->file->seek(0);
        $this->windowSize = $windowSize;
        $this->buffer = [];
        $this->loadBuffer();
    }

    public function peekBuffer() {
        return $this->buffer;
    }

    public function pick($index) {
        if (!array_key_exists($index, $this->buffer)) {
            return null;
        }
        $value = $this->buffer[$index];
        unset($this->buffer[$index]);
        $this->buffer = \array_values($this->buffer);
        $this->loadBuffer();
        return $value;
    }

    private function loadBuffer() {
        for ($c = count($this->buffer); $c < $this->windowSize; $c++) {
            if ($this->file->eof()) {
                return;
            }
            $line = $this->file->fgets();
            if (false !== $line && "" !== $line) {
                $this->buffer[] = trim($line);
            }
        }
    }
}

class Packer
{

    const BAG_TARGET_WEIGHT = 1000;
    const MEAN_WEIGHT = 170;
    const MEAN_COUNT = 6; //ceil(self::BAG_WEIGHT/self::MEAN_WEIGHT);
    const MEAN_TARGET_WEIGHT = 167; //ceil(self::BAG_WEIGHT/self::MEAN_COUNT);

    public static function pack(Belt $belt, Picker $picker) {
        $bag = ["oranges" => [], "buffers" => []];
        $bags = [];
        while ($oranges = $belt->peekBuffer()) {

            $index = $picker->pick($oranges, \array_sum($bag["oranges"]));
            $orange = $belt->pick($index);
            $bag["oranges"][] = $orange;
            $bag["buffers"][] = $oranges;

            if (\array_sum($bag["oranges"]) >= self::BAG_TARGET_WEIGHT) {
                $bags[] = $bag;
                $bag = ["oranges" => [], "buffers" => []];
            }
        }
        return $bags;
    }
}

class Base
{
    public static function bestPermutation($elements, $weight = 0) {
        if (\array_sum($elements) < Packer::BAG_TARGET_WEIGHT - $weight) {
            return null;
        }
        $permute = function ($weight, $elements) use (&$permute) {
            if ($weight >= Packer::BAG_TARGET_WEIGHT) {
                return [];
            }
            $best = \PHP_INT_MAX;
            $bestElements = [];
            foreach ($elements as $key => $value) {
                $sum = $weight + $value;
                $els = [$value];
                if ($sum < Packer::BAG_TARGET_WEIGHT) {
                    $subSet = $elements;
                    unset($subSet[$key]);
                    $els = $permute($weight + $value, $subSet);
                    $els[] = $value;
                    $sum = $weight + \array_sum($els);
                }
                if ($sum >= Packer::BAG_TARGET_WEIGHT && $sum < $best) {
                    $best = $sum;
                    $bestElements = $els;
                }
            }
            return $bestElements;
        };
        $best = $permute($weight, $elements);

        return $best;
    }

    public function pickLightestOutOfHeavierThan($buffer, $targetWeight) {
        $b = -1;
        $bW = PHP_INT_MAX;
        foreach ($buffer as $key => $value) {
            if ($targetWeight <= $value && $value < $bW) {
                $b = $key;
                $bW = $value;
            }
        }
        return $b;
    }

    public function pickClosestTo($buffer, $targetWeight) {
        $b = -1;
        $bW = PHP_INT_MAX;
        foreach ($buffer as $key => $value) {
            $diff = \abs($targetWeight - $value);
            if ($diff < $bW) {
                $b = $key;
                $bW = $diff;
            }
        }
        return $b;
    }

    public function pickFurthestFrom($buffer, $targetWeight) {
        $b = -1;
        $bW = \PHP_INT_MIN;
        foreach ($buffer as $key => $value) {
            $diff = \abs($targetWeight - $value);
            if ($diff > $bW) {
                $b = $key;
                $bW = $diff;
            }
        }
        return $b;
    }

    public function findMax($buffer) {
        $i = -1;
        $m = 0;
        foreach ($buffer as $k => $v) {
            if ($v > $m) {
                $m = $v;
                $i = $k;
            }
        }
        return $i;
    }

    public function findMin($buffer) {
        $i = -1;
        $m = \PHP_INT_MAX;
        foreach ($buffer as $k => $v) {
            if ($v < $m) {
                $m = $v;
                $i = $k;
            }
        }
        return $i;
    }

    public function minimalOrangeCount($buffer, $weight) {
        $elementsToAdd = ceil((Packer::BAG_TARGET_WEIGHT - $weight) / Packer::MEAN_WEIGHT);
        $buffer = \array_merge($buffer,
            \array_fill(0, \floor($elementsToAdd / 2), Packer::MEAN_WEIGHT - 7),
            \array_fill(0, \floor($elementsToAdd / 2), Packer::MEAN_WEIGHT + 7),
            \array_fill(0, $elementsToAdd - \floor($elementsToAdd / 2) * 2, Packer::MEAN_WEIGHT)
        );
        \rsort($buffer);
        $orangeCount = 0;
        foreach ($buffer as $w) {
            $weight += $w;
            $orangeCount++;
            if ($weight >= Packer::BAG_TARGET_WEIGHT) {
                return $orangeCount;
            }
        }
        return $orangeCount + (Packer::BAG_TARGET_WEIGHT - $weight) / Packer::MEAN_WEIGHT;
    }
}


class Picker extends Base
{
    public function pick($buffer, $weight) {
        $weightNeeded = Packer::BAG_TARGET_WEIGHT - $weight;

        $minimalOrangeCount = $this->minimalOrangeCount($buffer, $weight);
        $orangeTargetWeight = ceil($weightNeeded / $minimalOrangeCount);

        if (0 === $weight) {
            $mean = \array_sum($buffer) / count($buffer);
            if ($mean > $orangeTargetWeight) {
                return $this->findMin($buffer);
            } elseif ($mean < $orangeTargetWeight) {
                return $this->findMax($buffer);
            }
            return $this->pickFurthestFrom($buffer, $orangeTargetWeight);
        }

        $i = $this->pickLightestOutOfHeavierThan($buffer, $weightNeeded);
        if (-1 !== $i) {
            return $i;
        }
        $i = $this->pickClosestTo($buffer, $orangeTargetWeight);
        return -1 !== $i ? $i : 0;
    }
}

$bagCount = 0;
$belt = new Belt(__DIR__ . "/oranges.txt", 0);
for ($l = 2; $l <= 7; $l++) {
    $belt->reset($l);
    $bags = Packer::pack($belt, new Picker());
    $bagCount += count($bags);
    printf("%d -> %d\n", $l, count($bags));
}
echo "Total: $bagCount\n";

2 -> 1645 3 -> 1657 4 -> 1663 5 -> 1667 6 -> 1671 7 -> 1672 Total: 9975

Try It

Answer 7

Python 3, 9855 9928 9947 9956 9964 bags

Based on Jonathan Allan's starter code, but ungolfed to be readable.

Idea: Since 1000/170 = 5.88, we try to select fruits close to 1000/6 (I fiddled with the magic constants). However, if the last fruit in the bag can minimize waste, we use that instead.

This solution has bag sum targets for each fruit added. I'll probably stop here. I used Nelder-Mead to find my targets array:

[  165.79534144   343.58443287   522.58081597   680.76516204   845.93431713 1063.17204861]

def f(a, m, l, targets):
    bags = []
    bag = []
    bag_sum = 0
    while a:
        buffer = a[:l]
        finishers = tuple(filter(lambda w: bag_sum + w >= m, buffer))
        if finishers:
            next_fruits = [min(finishers)]

        else:
            ind = len(bag)
            next_fruits = [min(buffer, key=lambda w: abs(targets[ind]-bag_sum-w))]

        for next_fruit in next_fruits:
            bag.append(a.pop(a.index(next_fruit)))
            bag_sum += bag[-1]

        if sum(bag) >= m:
            bags.append(bag)
            bag = []  # Reset bag
            bag_sum = 0

    return bags

---

9956 bags

from itertools import combinations

def f(a,m,l):
    bags = []
    bag = []
    while a:
        buffer = a[:l]
        next_fruit = None
        single_fruit = True

        finishers = [w for w in buffer if sum(bag) + w >= m ]
        if finishers: next_fruit = min(finishers)

        if not next_fruit:
            if len(buffer) >= 4 and sum(bag) < 600:
                next_fruits = min(combinations(buffer, 2), key=
                                  lambda ws: abs(2*169-sum(ws)))
                for fruit in next_fruits:
                    bag.append(a.pop(a.index(fruit)))

                single_fruit = False  # Skip adding single fruit

            else:
                next_fruit = min(buffer, key=lambda w: abs(171.5-w))

        if single_fruit:
            bag.append(a.pop(a.index(next_fruit)))

        if sum(bag)>=m:
            bags.append(bag)
            bag = []

    return bags


oranges = [int(x.strip()) for x in open("fruit.txt").readlines()]
bagLists = []
for lookahead in (2,3,4,5,6,7):
    bagLists.append(f(oranges[:], 1000, lookahead))


totalBagsOver1000 = sum(map(len, bagLists))
print('bags: ', (totalBagsOver1000))

---

The 9947 bags program is particularly simple:

def f(a,m,l):
    bags = []
    bag = []
    while a:
        buffer = a[:l]
        next_fruit = None

        finishers = [w for w in buffer if sum(bag) + w >= m ]
        if finishers: next_fruit = min(finishers)

        if not next_fruit:
            next_fruit = min(buffer, key=lambda w: abs(171.5-w))

        bag.append(a.pop(a.index(next_fruit)))

        if sum(bag)>=m:
            bags.append(bag)
            bag = []

    return bags

Answer 8

Ruby, 9967 bags

def pick a, n
  if a.sum < n
    #return a.max
    d = n % 170
    return a.min_by{|w|
      [(w - d).abs, (w - d - 170).abs].min
    }
  end
  
  subsets = (0..a.length).map do |i|
    a.combination(i).to_a
  end.flatten(1)
  
  subsets.select!{|s|s.sum >= n}
  least_overkill = subsets.min_by{|s|s.sum}
  #puts "best: #{least_overkill.sort}"
  return least_overkill.min
end

def run list, weight, n
  bags = 0
  in_bag = 0
  while list.size > 0
    x = pick(list[0...n], weight - in_bag)
    i = list.index(x)
    raise new Exeption("not a valid weight") if(!i || i >= n)
    list.delete_at i
    in_bag += x
    if in_bag >= weight
      #puts in_bag
      in_bag = 0
      bags += 1
    end
  end
  return bags
end

Try it online!

If you have enough weight to fill the bag, find the lightest subset that can fill the bag and use the lightest orange of that subset. Otherwise, get the remaining weight as close as possible to a multiple of 170.

Answer 9

Racket/Scheme, 9880 bags

To decide which piece of fruit to add to the bag, compare the optimal bag weight to the weight of the bag with the additional piece of fruit. If it's the optimal weight, use it. If it's overweight, minimize the excess amount. If it's underweight, minimize the excess amount after trying to leave an optimal gap.

;; types

(define-struct bagger (fruit look tray bag bags)) ; fruit bagger

;; constants

(define MBW 1000) ; minimum bag weight
(define AFW 170) ; average piece-of-fruit weight
(define GAP (- MBW AFW)) ; targeted gap
(define FRUIT (file->list "fruit-supply.txt")) ; supplied fruit

;; utility functions

(define (weigh-it ls)
  (if (empty? ls)
      0
      (+ (car ls) (weigh-it (cdr ls)))))

(define (ref-to-car ls ref)
  (if (zero? ref)
      ls
      (let ((elem (list-ref ls ref)))
        (cons elem (remove elem ls)))))

;; predicates

(define (bag-empty? bgr) (empty? (bagger-bag bgr)))
(define (bag-full? bgr) (>= (weigh-it (bagger-bag bgr)) MBW))
(define (fruit-empty? bgr) (empty? (bagger-fruit bgr)))
(define (tray-empty? bgr) (empty? (bagger-tray bgr)))
(define (tray-full? bgr) (= (length (bagger-tray bgr)) (bagger-look bgr)))
(define (target-not-set? target value) (and (empty? target) (empty? value)))

;; pick best piece of fruit

(define (pf-rec tray bag i target value diff)
  (if (or (target-not-set? target value) (< diff value))
      (pick-fruit (cdr tray) bag (add1 i) i diff)
      (pick-fruit (cdr tray) bag (add1 i) target value)))

(define (pick-fruit tray bag i target value)
  (if (empty? tray)
      target
      (let ((weight (weigh-it (cons (car tray) bag))))
        (cond
          ((= weight MBW) i)
          ((> weight MBW) (pf-rec tray bag i target value (- weight MBW)))
          ((< weight MBW)
           (if (> weight GAP)
               (pf-rec tray bag i target value (- weight GAP))
               (pf-rec tray bag i target value (modulo (- MBW weight) AFW))))))))

;; load tray, bag, bags, etc.

(define (load-bag bgr)
  (let* ((tray (bagger-tray bgr))
         (bag (bagger-bag bgr))
         (weight (+ (weigh-it tray) (weigh-it bag))))
    (if (= weight MBW)
        (struct-copy bagger bgr
                     (tray empty)
                     (bag (append tray bag)))
        (let ((new-tray (ref-to-car tray (pick-fruit tray bag 0 empty empty))))
          (struct-copy bagger bgr
                       (tray (cdr new-tray))
                       (bag (cons (car new-tray) bag)))))))

(define (load-bags bgr)
  (struct-copy bagger bgr
               (bag empty)
               (bags (cons (bagger-bag bgr) (bagger-bags bgr)))))

(define (load-tray bgr)
  (struct-copy bagger bgr
               (fruit (cdr (bagger-fruit bgr)))
               (tray (cons (car (bagger-fruit bgr)) (bagger-tray bgr)))))

;; run the bagger factory

(define (run-bagger-aux bgr)
  (cond
    ((bag-full? bgr) (run-bagger-aux (load-bags bgr)))
    ((bag-empty? bgr)
     (cond
       ((tray-full? bgr) (run-bagger-aux (load-bag bgr)))
       ((tray-empty? bgr)
        (if (fruit-empty? bgr)
            (length (bagger-bags bgr))
            (run-bagger-aux (load-tray bgr))))
       (else
        (if (fruit-empty? bgr)
            (run-bagger-aux (load-bag bgr))
            (run-bagger-aux (load-tray bgr))))))
    (else
     (cond
       ((tray-full? bgr) (run-bagger-aux (load-bag bgr)))
       ((tray-empty? bgr)
        (if (fruit-empty? bgr)
            (run-bagger-aux (load-bags bgr))
            (run-bagger-aux (load-tray bgr))))
       (else
        (if (fruit-empty? bgr)
            (run-bagger-aux (load-bag bgr))
            (run-bagger-aux (load-tray bgr))))))))

(define (run-bagger fruit look)
  (run-bagger-aux (make-bagger fruit look empty empty empty)))

;; stackexchange problem run

(define (run-problem fruit looks)
  (if (empty? looks)
      0
      (+ (run-bagger fruit (car looks)) (run-problem fruit (cdr looks)))))

(run-problem FRUIT '(2 3 4 5 6 7)) ; result = 9880

Answer 10

Haskell, 9777 bags

This was my first attempt:

• it greedily filled a bag with a batch when it could,
• or flushed all oranges into the bag when it could not.

options[]=[(0,([],[]))]
options(first:rest)=[option|(sum,(now,later))<-options rest,
 option<-[(sum+first,(first:now,later)),(sum,(now,first:later))]]
bags _[_]_=[]
bags(w_sum,w_bag)(w_kilo:w_iyts)w_view=
 let(w_take,w_remd)=splitAt(w_view)w_iyts;
     w_fill=filter((>=(w_kilo-w_sum)).fst)(options w_take)
 in if null w_fill then bags(w_sum+sum w_take,w_bag++w_take)(w_kilo:w_remd)w_view
    else let(_,(w_now,w_later))=minimum w_fill in
         (w_bag++w_now):bags(0,[])(w_kilo:w_later++w_remd)w_view
main=print.sum$map(length.bags(0,[])(1000:batch))[2..7]

Try it online!

Answer 11

Haskell, 9981 bags

The Angs → Jonathan Allan → JayCe → fortraan → Alex → Roman Czyborra codegolf python could cyclize back to Haskell for some added mathematical purity along the same major train of thought

• only one orange gets sacked before a new orange is added into consideration
• bias prefers sufficing fruits ((<miss)==False<True)
• bias prefers fruits close to the most likely integer fill

• for that integer reverse the
  (m-n)/sqrt(n)==(n+1-m)/sqrt(n+1) <==> n=sqrt(m^2-1/4)-1/2 from a https://en.wikipedia.org/wiki/Sum_of_normally_distributed_random_variables

  

seasoned with some unecessary pointlessnesses

subsets[]=[[]];subsets(f:t)=[r|s<-subsets t,r<-[s,f:s]]
mean=uncurry(div).(id***max 1).(sum&&&length)
bags[]_ _=[];bags batch(miss:have)n=let
 goal=div miss$ceiling(sqrt((fromIntegral miss/170)^2+1/4)-1/2)
 best=minimumBy.comparing.(((<miss)&&&(abs.(goal-))).); desk=take n batch
 pick=best id.best(if sum desk<miss then mean else sum).filter(>[]).subsets$desk
 in if pick < miss then bags(delete pick batch)(miss-pick:pick:have)n
       else (pick:have):bags(delete pick batch)[miss+sum have]n
main=print$id&&&sum$map(length.bags batch[1000])[2..7]

Try it online!

without yielding a different numeric gain atop the 9981 nets of oranges harvested afore while my 10k011 bags packer grabbing unfit oranges back out of unclosed bags was disqualified by user69850 in persona user202729 → Jo King → ovs hencefore the deserved bounty went to Alex