title: Fruit bagging factory

text:
# Question
Title: Fruit bagging factory
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
> 8 votes
## 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
> 10 votes
# 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
> 6 votes
# C++17, 9961.58 <sub>(average over some random seeds)</sub>

(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 votes
# 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
> 4 votes
# 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
> 4 votes
# 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
> 3 votes
# 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
> 2 votes
# 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
> 2 votes
# 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
> 1 votes
# 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
> 1 votes
# Haskell, 9981 bags

The AngsJonathan AllanJayCefortraanAlexRoman Czyborra codegolf python could cyclize back to Haskell for some added mathematical purity along the same major train of thought

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 user202729Jo Kingovs hencefore the deserved bounty went to Alex

---
Tags: number, code-challenge, sequence, optimization, restricted-time
---


title: Code golf the best permutation

text:
# Question
Title: Code golf the best permutation
**Challenge**

Given an integer **n ≥ 4**, output a permutation of the integers **\[0, n-1\]** with the property that no two consecutive integers are next to each other. The value of a permutation `pi` is the sum of `abs(pi[i] - i)` for all indices `i`.

**Examples**

* `(1, 3, 0, 2)` has value `6`
* `(0, 2, 4, 1, 3)` has value `6`
* `(0, 2, 4, 1, 3, 5)` has value `6`
* `(0, 2, 4, 1, 5, 3, 6)` has value `8`

**Score of your answer**

The score of your answer is the sum of the values of your permutations for `n = 4 .. 14` plus the number of bytes your code takes. The lower the score, the better. Your code must give valid output for all those values of `n`.

You must be able to run your submission to completion on your machine.

In case of ties, time of last edit that resulted in the relevant score will be the decider.

**Isn't this the same question as this one?**

Answers to the linked question will not be competitive for this question as they make no effort to optimize the value of a permutation. For example for `n=10`, the permutation `[1, 3, 5, 7, 9, 0, 2, 4, 6, 8]` given by most of the answers there gives a value of `30`. You can do much better than that.

For the permutation part of the question, the optimal value overall is at most `120`. (Thank you to @Laikoni.) Whereas Dennis's answer to the previous question scores 222. (Thank you to @user202729.)

# Answer
> 7 votes
# Jelly, ~~36~~ ~~34~~ ~~33~~ ~~32~~ ~~31~~ 30 bytes, result: 120

Thanks to Dennis for -1 byte! (implicitly by fixing a Jelly bug, although the feature postdates the challenge)

```
ðRḟISị“Æ¤¿‘Ʋœ?$;@µ2x5~4¦ṁ_4$Ä’

```

New feature: accumulated sum (`Ä`).

Try it online!

Use 1-indexing.

Takes linear time, too.

---

This C++ program generates the lexicographically smallest permutation, assuming that **|i - pi| ≤ width** (where **width** is a hardcoded constant) for all **0 ≤ i \< n**, with time complexity about ***O(width2 × 22×width × n)*** (which is just ***O(n)*** for fixed **width**): Try it online!

---

### How?

1. Write a C++ program attempting to solve the problem optimally.
2. Observe the pattern. We note that the sequence of all elements except 4 last ones is a prefix of

```
0 2 4 1 3 5 7 9 6 8 10 12 14 11 13 15 17 19 16 18 20 22 24 21 23 25 ...

```
3. Computes the sequence's incremental difference.

```
2 2 -3 2 2 2 2 -3 2 2 2 2 -3 2 2 2 2 -3 2 2 2 2 -3 2 2

```

Note the period 5.
4. The Jelly implementation:

* **n-4** first elements are taken from the sequence above. ***O(n)***.
    * For **4** last elements, ~~just brute force all 24 possibilities~~. ***O(1)***.

    (note: I no longer brute force all 24 possibilities from the 32-bytes version)

# Answer
> 7 votes
## CJam (60 bytes + 120 = 180 score)

```
{_5/4*8e!961=7_)er<:A\,^e!{A\+}%{2ew::-:z1&!},{_$.-:z1b}$0=}

```

Online test suite with integrated scoring

Extension up to n=24

### Dissection

```
{
  _5/4*        e# Work out how much of the hard-coded prefix to use
  8e!961=7_)er e# Prefix [0 2 4 1 3 5 8 6]
               e# I identified this by brute forcing up to n=10 and looking for patterns
               e# I then used the identified prefix [0 2 4 1] to brute-force further
  <:A          e# Take the desired prefix of the hard-coded array, and store a copy in A
  \,^e!        e# Generate all permutations of the values in [0 .. n-1] which aren't in A
  {A\+}%       e# Prepend A to each of them
  {            e# Filter...
    2ew::-     e#   Take each difference of two consecutive elements
    :z         e#   Find their absolute values
    1&         e#   Test whether 1 is among those absolute values
    !          e#   Reject if it is
  },
  {            e# Sort by...
    _$.-       e#   Take pairwise differences of permutation with the identity
    :z         e#   Absolute values
    1b         e#   Add them (by interpreting in base 1)
  }$
  0=           e# Take the first
}

```

# Answer
> 6 votes
# Haskell, 146+89 score+bytes

```
f i|k<-mod i 4=scanl(+)1$take(i-2-k)(cycle[2,-3,2,3])++[[2],[2,2],[5,-3,2],[5,-3,2,2]]!!k

```

Repeats pattern \[1,3,0,2\], last `mod i 4` elements are hand tuned.

### Previous algorithm (132+116):

```
f i=last$filter(\a->all(`elem`a)[0..i-1]).(!!(i-1)).iterate((\l->map((:l).(+head l))[-3,2,-2,3])=<<)$pure<$>[i-3..i]

```

Bruteforces the correct number of jumps of length ±2 or ±3. Selects the last one that has the correct numbers in it, seems to work just fine and is a lot cheaper than implementing the score. Tio just runs out time before the last score, which is 18.

Try it online!

# Answer
> 2 votes
# Japt, 120 + 20 = 140

(Copying one of my solutions from the other challenge would have scored me 227)

```
o á k_äa d¥1ÃñxÈaYÃg

```

Try it or use this version to check scores. Both versions may start crapping out on you around 9.

---

## Explanation

```
o                        :Range [0,input)
  á                      :All permutations
    k_      Ã            :Remove sub-arrays that return true
      äa                 :  Get the consecutive absolute differnces
         d¥1             :  Do any equal 1?
               È  Ã      :Pass the integers in each remaining sub-array through a function
                aY       :  Get the absolute difference with the integer's index
              x          :Reduce by addition
             ñ           :Sort the main array by those values
                   ñ     :Return the first sub-array

```

# Answer
> 2 votes
# Ruby, 120 score + ~~112 106 91~~ 82 bytes

```
->n{(0...n).map{|a|a+(a+2)%5-([[],[],[0,4,3],[-1,4,4,4],[1,1,6,1]][n%5][a-n]||2)}}

```

Try it online!

The sequence is basically `(a-2)+(a+2)%5`.

If n mod 5 is not 0 or 1, the last 3 or 4 elements are different.

This is still half-hardcoded, always finds the best solution, maybe it could be golfed a little more, but I have run out of ideas.

# Answer
> 1 votes
# JavaScript (Node.js), 148 score + ~~109~~ 73 bytes

```
n=>[...Array(n)].map(_=>l=!m|l>n%5+2&&l>m+2?[+m,m=l+2][0]:l+2,m=n>4,l=~m)

```

Try it online! Explanation: `l` keeps track of the last number generated and `m` keeps track of the next number of the opposite parity to `l`; once `l` exceeds `m+2` the variables are exchanged. An adjustment is made at the start of the sequence so that sequences whose lengths are not multiples of 5 do not miss out any numbers, and another adjustment is made for `n=4`.

---
Tags: code-challenge, permutations, optimization
---


title: Function clipboard: copy

text:
# Question
Title: Function clipboard: copy
*This challenge is related to some of the MATL language's features, as part of the May 2018 Language of the Month event.* *Associated challenge*: Function clipboard: paste.

---

# Introduction

MATL has several *clipboards*, where you can store values (copy) to be retrieved later (paste). Some clipboards are *automatic*, which means that copying is automatically triggered by certain events. This challenge focuses on one of the automatic clipbards, called the *function-input clipboard*, or simply *function clipboard*.

This clipboard stores the inputs to the four most recent calls to normal, input-taking functions. *Normal* functions are the most common type of functions in MATL. *Input-taking* means that the function takes at least one input (functions that do not take any input are not considered by the function clipboard).

This is best explained with the following examples, which use two normal functions:

* `+`, which pops two numbers from the stack and pushes their sum.
* `U`, which pops one number and pushes its square.

**Example 1**:

```
3 2 + 6 + 12 4 U + +

```

produces the result `39`. The code is interpreted as follows:

* Number literals such as `3` or `12` get pushed to the stack
* Functions such as `+` pop their inputs and push their outputs to the stack.

The function calls, in chronological order, are:

1. `3 2 +` gives `5`
2. `5 6 +` gives `11`
3. `4 U` gives `16`
4. `12 16 +` `28`
5. `11 28 +` gives `39`.

The clipboard can be viewed as a list of four lists. Each inner list contains the inputs to a function call, with *most recent calls first*. Within each inner list, *inputs are in their original order*.

So after running the code the clipboard contents are (in Python notation):

```
[[11, 28], [12, 16], [4], [5, 6]]

```

**Example 2**:

```
10 20 U 30 +

```

leaves numbers `10` and `430` on the stack. The stack is displayed bottom to top at the end of the program.

The function calls are

1. `20 U` gives `400`
2. `400 30 +` gives `430`

Since there have been only two function calls, some of the inner lists defining the clipboard will be *empty*. Note also how `10` is not used as input to any function.

Thus, the clipboard contents after running the code are:

```
[[400, 30], [20], [], []]

```

**Example 3** (invalid):

```
10 20 + +

```

is considered invalid, because an input to the second `+` is missing (in MATL this would implicitly trigger user input).

# The challenge

**Input**: a string *S* with number literals, `+` and `U`, separated by spaces.

**Output**: the contents of the function clipboard after evaluating the string *S*.

Clarifications:

* You may use any two consistent symbols to represent those functions, other than digits. Also, you can use any consistent symbol as separator, instead of space.
* Only the two indicated functions will be considered.
* The input string will contain at least one number literal and at least one function.
* All numbers will be positive integers, possibly with more than one digit.
* It is possible that some number literals are not used by any function, as in the example 2.
* The input is guaranteed to be valid code, without requiring additional numbers. So a string as in example 3 will never occur.
* Trailing empty inner lists in the output can be ommited. So the result in example 2 can be `[[400, 30], [20]]`
* Any reasonable, unambiguous output format is acceptable. For example, a string with comma as inner separator and semicolon as outer separator: `400,30;20;;`.

Additional rules:

# Test cases

```
Input
Output

3 2 + 6 + 12 4 U + +
[[11, 28], [12, 16], [4], [5, 6]]

15 3 4 + 2 U 8 + U +
[[7, 144], [12], [4, 8], [2]]

3 6 9 12 + + 10 8 U 6
[[8], [6, 21], [9, 12], []]

8 41 12 25 4 5 33 7 9 10 + + + + + + + +
[[41, 105], [12, 93], [25, 68], [4, 64]]

10 1 1 + U U U U U
[[65536], [256], [16], [4]]

```

# Answer
> 3 votes
# 05AB1E, 20 bytes

```
A"D¸ˆn‚DˆO"4ô‡.V¯R4£

```

Try it online!

-4 thanks to Emigna (as well as -8 thanks to him updating me about rules).

* U: `a`
* \+ : `b`

# Answer
> 5 votes
# Bash, 43 bytes

```
sed s/+/rdnFPrp+/g\;s/U/p2^/g|dc|tac|sed 4q

```

Try it online!

This prints the clipboard in the following format, note the usage of \x0F as the separator.

```
item_1\x0Fitem_2
item_3
.
.
item_m\x0Fitem_n

```

The key idea is to pass this into dc, a stack-based language, such that the required stack items will be printed.

The input is piped to sed where every `+` is replaced with `rdnFPrp+`, which in dc prints the second number on the stack followed by \x0F and then the top number before performing addition. sed also replaces every `U` with `p2^`, print the top stack element and square it.

> The first substitution command `s` replaces all, as is denoted by the **g**lobal flag `g`, `+`s with `rdnFPrp+`. In dc, `r` swaps the top two stack items, `d` duplicates the top item, `n` prints it without a newline, `F` pushes 15 onto the stack and `P` prints it as a character (which is the delimiter), `r` swaps again, `p` prints the top stack item and then `+` performs addition on the top two stack items.
>
> We have another command, and in sed, commands are separated by either semicolons or newlines, of which the first option is chosen. Simply having `;` will make bash interpret that as the end of the sed command, so it is escaped with a `\`.
>
> In the last substitution command, `U` is replaced globally with `p2^`. In dc, `p` prints, and `2^` raises it to the second power.

The result of sed is eval'ed as dc code, printing the entire clipboard.

> The pipe to dc makes dc interpret that as dc code. Now, the most recent calls are at the bottom and the older ones at the top.

Since the lines are in reverse order, `tac` (reverse `cat`) is used to fix that.

And finally, sed picks the first 4 lines from tac.

> This is a shorter way of doing `head -4`. sed performs the commands to every line of the input one at a time. If there are no commands, nothing is done to the input, and it is returned as it is. `4q` tells sed to perform the command `q` on line 4. When sed is processing line 4 of the input, the first three inputs have already been printed. The command `q` quits the program, so it prints the fourth line and quits, thus performing the equivalent of `head -4`.

# Answer
> 4 votes
# Python 2, 126 bytes

```
s=[0];b=[]
for c in input().split():k='U+'.find(c)+1;b=[s[k-1::-1]][:k]+b;s=[int([c,s[0]**2,sum(s[:2])][k])]+s[k:]
print b[:4]

```

Try it online!

# Answer
> 4 votes
# Haskell, ~~113~~ 109 bytes

```
take 4.([]#).words
x:y:s#"+":r=(x+y:s#r)++[[y,x]]
x:s#"U":r=(x*x:s#r)++[[x]]
s#n:r=read n:s#r
_#_=[]
infix 4#

```

The first line defines an anonymous function which takes a string, e.g. `"3 2 + 6 + 12 4 U + +"`, and returns a list of lists of ints: `[[11,28],[12,16],[4],[5,6]]`. Try it online!

# Answer
> 2 votes
# JavaScript (ES6), 107 bytes

Takes input as a list consisting of integers, `'+'` and `'U'`. Returns another list consisting of integers, arrays of 2 integers and `'_'` for empty slots.

```
a=>a.map(x=>s.push(+x?x:(c=[x>[a=s.pop(),r=a*a]?a:[r=s.pop(),(r+=a,a)],...c],r)),s=[c='___'])&&c.slice(0,4)

```

Try it online!

### Commented

```
a =>                          // a[] = input array
  a.map(x =>                  // for each entry x in a[]:
    s.push(                   //   update the stack:
      +x ?                    //     if x is a positive integer:
        x                     //       push x onto the stack
      :                       //     else:
        ( c = [               //       update the clipboard:
            x > [             //         compare x with '['
              a = s.pop(),    //         a = first operand
              r = a * a       //         use a² as the default result
            ] ?               //         if x is 'U' (greater than '['):
              a               //           save the 1st operand in the clipboard
            :                 //         else:
              [ r = s.pop(),  //           r = 2nd operand
                (r += a, a)   //           add the 1st operand
              ],              //           save both operands in the clipboard
            ...c              //         append the previous clipboard entries
          ],                  //       end of clipboard update
          r                   //       push r onto the stack
        )                     //
    ),                        //     end of stack update
    s = [c = '___']           //   initialize the stack; start with c = '___'
  ) &&                        // end of map()
  c.slice(0, 4)               // return the last 4 entries of the clipboard

```

# Answer
> 2 votes
# Clean, 140 bytes

```
import StdEnv,Text
k[a,b:n]["+":s]=k[a+b:n]s++[[b,a]]
k[a:n]["U":s]=k[a^2:n]s++[[a]]
k n[v:s]=k[toInt v:n]s
k _[]=[]
$s=k[](split" "s)%(0,3)

```

Try it online!

In classical Clean style, it's the Haskell solution except about 50% longer.

# Answer
> 2 votes
# Go, ~~305~~ ~~303~~ 295 bytes

Dropped 8 bytes thanks to @ovs

```
func e(s string){b,v,w,x,r:=[][]int{{},{},{},{}},[]int{},0,0,0;for _,d:=range Split(s," "){if d=="+"{w,x,v=v[0],v[1],v[2:];r=w+x;b=append([][]int{[]int{x,w}},b...)}else if d=="U"{w,v=v[0],v[1:];r=w*w;b=append([][]int{[]int{w}},b...)}else{n,_:=Atoi(d);r=n};v=append([]int{r},v...)};Print(b[0:4])}

```

Try it online!

# Answer
> 2 votes
# Octave, 206 bytes

```
s=strsplit(input(''));m=t=[];for z=s
if(q=str2num(p=z{1}))t=[t q];else
if(p-43)m{end+1}=(k=t(end));t(end)=k^2;else
m{end+1}=(k=t(end-1:end));t(end-1:end)=[];t(end+1)=sum(k);end
end
end
m(1:end-4)=[];flip(m)

```

Try it online!

If only Octave had a `pop` syntax. `m` is the memory clipboard, `t` the stack.

# Answer
> 1 votes
# Python 3, ~~218~~ 204 bytes

*-14 bytes thanks to ovs*

```
from collections import*
def f(s):
	a=deque(maxlen=4);z=a.appendleft;b=[];x=b.pop
	for i in s.split():
		if'+'==i:c=x(),x();z(c);r=sum(c)
		elif'U'==i:c=x();z(c);r=c*c
		else:r=int(i)
		b+=r,
	print([*a])

```

Try it online!

# Answer
> 1 votes
# Red, 335 330 bytes

```
func[s][b: copy[]foreach c split s" "[append b either c >"+"and(c <"U")[do c][c]]r: copy[]until[t: 0 until[not parse
b[to copy c[2 integer!"+"](insert/only r reduce[c/1 c/2]replace b c c/1 + c/2 t: 1)to end]]until[not parse b[to copy
c[integer!"U"](insert/only r to-block c/1 replace b c c/1 ** 2 t: 1)to end]]t = 0]take/part r 4]

```

Try it online!

## More readable:

```
f: func[s] [
    s: split s " "
    b: copy []
    foreach c s [
        append b either (c > "+") and (c < "U")[do c] [c]
    ]
    r: copy []
    until [
        t: 0
        until [
            not parse b [to copy c[2 integer! "+"]
            (insert/only r reduce[c/1 c/2]
            replace b c c/1 + c/2
            t: 1)
            to end]
        ]
        until [
            not parse b [to copy c[integer! "U"]
            (insert/only r to-block c/1
            replace b c c/1 ** 2
            t: 1)
            to end]
        ]
        t = 0
    ]
    take/part r 4
]

```

# Answer
> 1 votes
# C (gcc), ~~264~~ 249 bytes

* -15 bytes from @ceilingcat

I used recursion so that I could use the function stack as the data stack: the input list is walked through and the operations are performed: the results are displayed in reverse order, with stack pushes not displayed.

The stack is implemented as a linked list. Here's how it works:

* The current node is set up with \[pointer to value,pointer to previous node\]
* To push a value, it is stored and the function is called again with the current node.
* To pop a value or modify the value on the top of the stack, a previous node's value is modified and the function is called again with the previous node.

I originally used a structure for the nodes, but I switched to bare pointers to save space. An interesting feature of this linked list is that it cleans itself up when the recursion completes.

```
#define _ printf(
f(char**s,int**p){int v,*y[]={&v,p},**w=y,m,n,t,z=1;return*s?**s-85?**s-43?--z,t=14,v=atoi(*s):(t=6,w=p[1],m=**w,**w+=n=**p):(t=0,w=p,**w*=m=**p),_(v=f(s+1,w))<4?",[%d]\0,[%d,%d]"+t+!v:"",m,n),v+z:0;}g(int*s){_"[");f(s,0);_"]\n");}

```

Try it online!

# Answer
> 1 votes
# , ~~205~~ 182 bytes

```
function(P){S=F
M=list()
for(K in el(strsplit(P," "))){if(is.na(x<-strtoi(K))){if(K>1){M=c(m<-S[1],M)
S[1]=m^2}else{M=c(list(m<-S[2:1]),M)
S=c(sum(m),S[-2:0])}}else S=c(x,S)}
M[1:4]}

```

Try it online!

`M` is the memory clipboard, `P` is the program, and `S` is the stack.

Technically `S` is initialized as a vector containing a single zero but since we never get an invalid input, it saves me a byte from `S={}`.

---
Tags: code-golf, number
---


title: Not just a four fours puzzle

text:
# Question
Title: Not just a four fours puzzle
In this variant of the Four fours puzzle your should use up to `x` `x's` (and no other number) and a defined set of operations to reach every number from 0 to 100. If `x = 4` then you can use up to four `4s` and this question becomes the classic four fours puzzle (except you can use up to four 4s rather than having to use exactly four of them). We assume `1 < x <= 9`.

In this version, only the following operators are allowed:

* Addition (`+`), Subtraction (`-`), Multiplication (`*`), Division (`/`). Note this is real division, so that `5/2 = 2.5`.
* Exponentiation (e.g. 4^4) as this would involve no extra symbols if written normally by hand.
* You can make new integers by concatenating `xs`. E.g. you can make the integers `4, 44, 444, 4444`.

You may also use parentheses to group numbers simply in order to control the order of evaluation of the operators. You can't for example combine parentheses with concatenation as in `(4/4)(4/4) = (1)(1) = 11`.

No other symbols may be used and standard order of operations applies.

Your program should generate, given an `x` in the defined range and an `n` between `0` and `100` inclusive, a correct solution for that input if it exists. Otherwise your code must output something to indicate no such solution exists.

You must be able to run your submission to completion on your machine for any input values of `x` and `n` in the allowed range. This is code golf, so shortest solution wins.

This old related question uses more operators (and only 4s) and hence all numbers from 0 to 100 are solvable which won't be true for this challenge.

**Input and output**

Your code takes two integers `x` and `n` as input and should output a solution (or an indication there is no solution) in any human readable format you find convenient. Input `4 6` would mean "Using up to four 4s, make the number 6" for example. So if the input is `4 6` the output could be `(4+4)/4+4`.

# Answer
# Python 3, 265 bytes

```
def f(x,n):
 for e in g(x,x-(x>7)):
  try:
   if eval(e)==n:return e
  except:1
g=lambda x,d:{str(x)*-~i for i in range(d)}|{s%(a,b)for a in g(x,d-1)for b in g(x,d-a.count(str(x)))for s in'%s**%s (%s/%s) (%s+%s) (%s-%s) %s*%s %s/%s'.split()['**'in a+b:]}if d else{}

```

Try it online!

Works for *all* numbers in the reference linked by Engineer Toast.

Runs up to `x=8` on tio, `x=9` takes a couple of minutes on my machine.

---

The function `g` returns a set of all combinations with at most `x` number of `x`'s. `f` then loops through them and returns the first which evaluates to the number `n`.

The number of possible values i found for each `x` are:

```
x  possible numbers
------
2  5
3  17
4  35
5  56
6  83
7  101
8  101
9  101

```

All the numbers above can be generated from `(a+b)`, `(a-b)`, `(a+b)`, `a*b`, `a/b`, `(a/b)`, and `a^b`. `a+b` and `a-b` do not give more numbers.

`a^b` is also only used once, as otherwise huge numbers are created (this is also verified in the reference document above)

---

An alternate version which short-circuits as soon as it finds a solution (not as golfed):

This is much faster as for `x=7..9` all numbers can be created.

# Python 3, ~~338~~ 289 bytes

```
def f(x,n,d=-1):
 d=[d,x][d<0];X=str(x);r=set()
 for E in{X*-~i for i in range(d)}|{s%(a,b)for a in[0]*d and f(x,n,d-1)for b in f(x,n,d-a.count(X))for s in'%s**%s (%s/%s) (%s+%s) (%s-%s) %s*%s %s/%s'.split()['**'in a+b:]}:
  try:e=eval(E)
  except:e=-1
  if e==n:exit(E)
  r|={E}
 return r

```

Try it online!
> 4 votes

---
Tags: code-golf, arithmetic, expression-building
---


title: Find operations required to get result

text:
# Question
Title: Find operations required to get result
So task is simple, given array of numbers and result, you need to find what operations you need to use on numbers from array , to obtain requested result.

Let's make it simple for start, and allow only basic operations such as: addition, subtraction, multiplication and division.

Example:

```
Input  : [5,5,5,5,5] 100
Output : 5*5*5-5*5

```

To give some advantage to languages like Java, request is to implement function, not entire program, and result can be return via parameter or print to console.

Code is scored based on amount bytes, and as it's golf code challenge, lowest score wins.

Another requirment is ~~You can get additional -10 points~~ if for array contains only digids, support solutions where you could construct numbers from following digits. Ie

```
Input  : [1,2,3,4,5] 0
Output : 12-3-4-5

```

Note that, provided outputs are proposed outputs, some cases might have more than one solution. It's up to you will you provide one or more solutions for given task.

**EDIT:** Result has to be valid from mathematical point of view, hence division is rational division, not integer, and operation precedence is same as in classical math (first multiplication and division then addition and subtraction).

# Answer
# Pyth, 23 bytes

Due to security reasons, `*` and `/` won't evaluate online, but they theoretically work.

```
fqeQvTms.ihQd^"+-*/"lth

```

Test suite with only `+` and `-`.
> 4 votes

# Answer
# TSQL(sqlserver 2016) ~~310~~ ~~294~~ 280 bytes

What a wonderful opportunity to write ugly code:

Golfed:

```
DECLARE @ varchar(max)= '5,5,5'
DECLARE @a varchar(20) = '125'

,@ varchar(max)='';WITH D as(SELECT @a a UNION ALL SELECT STUFF(a,charindex(',',a),1,value)FROM STRING_SPLIT('*,+,./,-,',',')x,d WHERE a like'%,%')SELECT @+=a+','''+REPLACE(a,'.','')+'''),('FROM D WHERE a not like'%,%'EXEC('SELECT y FROM(values('+@+'null,null))g(x,y)WHERE x='+@b)

```

Try it online

Readable:(insertion of decimal point(.) and removal of the same is necessary in order for sql to accept that 4/5 is not 0 - well removal is for the people testing it)

```
DECLARE @a varchar(max)= '5,5,5'
DECLARE @b varchar(20) = '5'

,@ varchar(max)=''
;WITH D as
(
  SELECT @a a
  UNION ALL
  SELECT STUFF(a,charindex(',',a),1,value)
  FROM STRING_SPLIT('*,+,./,-,',',')x,d
  WHERE a like'%,%'
)
SELECT @+=a+','''+REPLACE(a,',','')+'''),('
FROM D
WHERE a not like'%,%'

EXEC('SELECT y FROM(values('+@+'null,null))g(x,y)WHERE x='+@b)

```

This solution can also handle these types of input:

> Input :\[1,2,3,4,5\] 0 Output : 12-3-4-5
> 4 votes

# Answer
# Oracle SQL 11.2, ~~322~~ ~~304~~ 270 bytes

```
SELECT o FROM(SELECT REPLACE(SUBSTR(:1,1,1)||REPLACE(SYS_CONNECT_BY_PATH(a||SUBSTR(:1,LEVEL*2+1,1),','),','),'_')o,LEVEL l FROM(SELECT SUBSTR('+-*/_',LEVEL,1)a FROM DUAL CONNECT BY LEVEL<6)CONNECT BY LEVEL<LENGTH(:1)/2)WHERE:2=dbms_aw.eval_number(o)AND l>LENGTH(:1)/2-1;

```

:1 is the list of digits
:2 is the result searched

Un-golfed :

```
SELECT o
FROM   (
         SELECT REPLACE(SUBSTR(:1,1,1)||REPLACE(SYS_CONNECT_BY_PATH(a||SUBSTR(:1,LEVEL*2+1,1),','),','),'_')o,LEVEL l
         FROM ( -- Create one row per operator
                SELECT SUBSTR('+-*/_',LEVEL,1)a FROM DUAL CONNECT BY LEVEL<6
              ) CONNECT BY LEVEL<LENGTH(:1)/2  -- Create every combination of operators, one per ','
)
WHERE :2=dbms_aw.eval_number(o)  -- filter on result = evaluation
  AND l>LENGTH(:1)/2-1           -- keep only expressions using every digits

```
> 4 votes

# Answer
# JavaScript (ES6), ~~165~~ 147 bytes

```
a=>o=>(c=[],i=c=>{for(j=0;!((c[j]?++c[j]:c[j]=1)%5);)c[j++]=0},eval(`while(eval(e=(a+'').replace(/,/g,(_,j)=>'+-*/'.charAt(c[~-j/2])))!=o)i(c);e`))

```

Nested `eval`... lovely.

```
f=a=>o=>(c=[],i=c=>{for(j=0;!((c[j]?++c[j]:c[j]=1)%5);)c[j++]=0},eval(`while(eval(e=(a+'').replace(/,/g,(_,j)=>'+-*/'.charAt(c[~-j/2])))!=o)i(c);e`))
console.log(f([5,5,5,5,5])(100))
console.log(f([1,2,3,4,5])(0))
console.log(f([3,4])(0.75))
console.log(f([3,4,5,6])(339))
```
> 3 votes

# Answer
## Python 3, ~~170~~ 155 bytes

```
from itertools import*
def f(n,o):print({k for k in[''.join(map(str,sum(j,())))[1:]for j in[zip(x,n)for x in product('+-*/',repeat=len(n))]]if eval(k)==o})

```

Create a generator with all possible orders of the operators, combine that with the numbers, then eval until we get the answer.

https://repl.it/C2F5
> 3 votes

# Answer
# Python, ~~195~~ 186 bytes

Here's an atrocious way of doing it.

```
def x(i,r):
 t=""
 from random import choice as c
 while True:
  for j in i:
   t+=str(j)
   if c([0,1]):t+="."+c("+-/*")
  t=t.strip("+-*/.")+"."
  v=eval(t)
  if v == r:print t
  t=""

```

The function `x` accepts an argument of a `list` and a `result` \- `x([1,2,3,4,5], 15)` for example.

The program begins a loop where we begin randomly selecting if we should append `"+", "-", "*", or "/"` between each number, or if we should concatenate them together. This seemed like a more concise option than actually going through permutations and trying every combination to find every result, and although it takes longer to run and is *much* less efficient. (Fortunately that's not a concern in this context!)

It also appends "." to each number to avoid doing integer-rounded operations like `6/4 = 1`. It then `eval`s our expression and determines if the result equal to what we are expecting, and if so, outputs the expression.

This program never exits - it will keep continually outputting results until killed.

**EDIT 1**: Remove unnecessary newlines where one-line `if` statements can be used.
> 2 votes

# Answer
## Matlab, 234 ~~238~~ ~~258~~ bytes

*I'm assuming based on the limitations of the other answers that the number order of the input array is maintained by fiat.*

```
n=length(x)-1
k=n*2+2
p=unique(nchoosek(repmat('*-+/',1,n),n),'rows')
p=[p char(' '*~~p(:,1))]'
c=char(x'*~~p(1,:))
o=p(:,r==cellfun(@eval,mat2cell(reshape([c(:) p(:)]',k,[]),k,0|p(1,:))))
reshape([repmat(x',size(o,2),1) o(:)]',k,[])'

```

This code takes a string of numbers `x`, say `x = '12345'` and a result `r`, say `r = 15` and returns all of the strings of expressions you can evaluate to get `r` from `x` using the four operators.

I've used two different length-equivalent ways of avoiding using `ones(length())`-type or `repmat(length())`-type expressions: `~~p(1,:)` which returns not-not values in `p` (i.e., a list of `1`s the samelength as the first dimension of `p`) and `0|p(:,1)` which returns 0 or is-there-a-value-in-`p` (i.e., a list of `1`s the same length as the second dimension of `p`).

Matlab doesn't have an `nchoosek` *with replacement* method, so I've duplicated the operators the correct number of times, computed the whole space of `nchoosek` for that larger selection of operators, and then used a `unique` call to pare the result down to what it should be (removing equivalent combinations like '\***+' and '\***+'). I add a trailing space to match the length of the input vector for concatenation purposes and then compose the operator strings with the input strings into the columns of a matrix. I then evaluate the expressions columnwise to get results and find the order of operators that corresponds to those columns with results that match our input `r`.

Test: `x = '12345'`, `r = 15`:

```
1*2*3+4+5
1+2+3+4+5
1-2*3+4*5

```

If I had to take an array of double precision values, I'd need `x = num2str(x,'%d');` in order to convert the digits to a string, adding 21 (20 without the `;`) to my score. \*The extra bytes were semicolons I left in purely so that anyone running this code won't see their command prompt blow up with long arrays. Since my edit produces a giant pile of warnings about logicals and colon-operands now anyway, I've removed the semicolons in the new version.

Edit 2: Forgot to replace a `2*n+2` with `k`.

Old answer:

```
n=length(x)-1;
p=unique(nchoosek(repmat(['*','-','+','/'],1,n),n),'rows');
l=length(p);
p=[p repmat(' ',l,1)]';
c=reshape([repmat(x',l,1) p(:)]',n*2+2,[]);
o = p(:,r == cellfun(@eval, mat2cell(c,n*2+2,ones(l,1))));
reshape([repmat(x',size(o,2),1) o(:)]',n*2+2,[])'

```
> 2 votes

# Answer
# JavaScript (ES6), 88 bytes

```
a=>o=>eval(`while(eval(e=(a+'').replace(/,/g,_=>'+-*/'.charAt(Math.random()*5)))!=o);e`)

```

Threw in a little randomness to the mix. Much easier than systematically iterating through the combinations.

## Test Suite

```
f=a=>o=>eval(`while(eval(e=(a+'').replace(/,/g,_=>'+-*/'.charAt(Math.random()*5)))!=o);e`)
console.log(f([5,5,5,5,5])(100))
console.log(f([1,2,3,4,5])(0))
console.log(f([3,4])(0.75))
console.log(f([3,4,5,6])(339))
```
> 2 votes

# Answer
# PHP, 108 bytes

```
for(;$i=$argc;eval("$s-$argv[1]?:die(\$s);"))for($s="",$x=$p++;--$i>1;$x/=4)$s.="+-*/"[$s?$x&3:4].$argv[$i];

```

takes input from command line arguments in reverse order. Run with `-r`.

**breakdown**

```
for(;                   # infinite loop:
    $i=$argc;               # 1. init $i to argument count
    eval("$s-$argv[1]?:"    # 3. if first argument equals expression value,
        ."die(\$s);")       #    print expression and exit
    )
    for($s="",              # 2. create expression:
        $x=$p++;            #    init map
        --$i>1;                 # loop from last to second argument
        $x/=4)                  # C: shift map by two bits
        $s.="+-*/"[$s?$x&3:4]   # A: append operator (none for first operand)
            .$argv[$i];         # B: append operand

```
> 1 votes

# Answer
## Perl 5 with `-pa`, 46 bytes

```
$"="{,\\*,/,+,-}";$x=<>;($_)=grep$x==eval,<@F>

```

Try it online!
> 1 votes

---
Tags: code-golf, expression-building
---


title: Are there mountain rings?

text:
# Question
Title: Are there mountain rings?
# Challenge

Given a matrix of positive integers, determine if there are any "rings" of mountains. The formal definition for this challenge is: given a matrix of positive integers, is there any positive integer `n` for which there is a closed ring of cells in the matrix that are strictly greater than `n` such that all cells enclosed in the ring are less than or equal to `n`.

Let's take a truthy example:

```
3 4 5 3
3 1 2 3
4 2 1 3
4 3 6 5

```

If we set `n` to `2`:

```
1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1

```

As we can clearly see, the `1`s along the edge form a ring.

We define a ring as an ordered collection of cells where adjacent cells in the collection are also adjacent (edge or corner) on the grid. Additionally, the ring must contain at least 1 cell inside of it; that is, attempting to edge-only BFS-floodfill the entire matrix excluding the cells in the collection and never traversing a cell in the collection must miss at least one cell.

# Truthy Test Cases

```
4 7 6 5 8 -> 1 1 1 1 1
6 2 3 1 5 -> 1 0 0 0 1 (n = 3)
6 3 2 1 5 -> 1 0 0 0 1
7 5 7 8 6 -> 1 1 1 1 1

1 3 2 3 2
1 6 5 7 2
1 7 3 7 4
1 6 8 4 6

1 3 1
3 1 3
1 3 1

7 5 8 7 5 7 8 -> if you have n = 4, you get an interesting ridge shape around the top and right of the grid
8 4 4 2 4 2 7
6 1 8 8 7 2 7
5 4 7 2 5 3 5
5 6 5 1 6 4 5
3 2 3 2 7 4 8
4 4 6 7 7 2 5
3 2 8 2 2 2 8
2 4 8 8 6 8 8

5 7 6 8 6 8 7 -> there is an island in the outer ring (n = 4), but the island is a ring
5 3 2 4 2 4 7
6 3 7 8 5 1 5
8 2 5 2 8 2 7
8 3 8 8 8 4 7
6 1 4 1 1 2 8
5 5 5 5 7 8 7

150 170 150
170 160 170
150 170 150

```

# Falsy Test Cases

```
1 2 3 2 1 -> this is just a single mountain if you picture it graphcially
2 3 4 3 2
3 4 5 4 3
2 3 4 3 2
1 2 3 2 1

4 5 4 3 2 -> this is an off-centered mountain
5 6 5 4 3
4 5 4 3 2
3 4 3 2 1

1 1 1 1 1 -> this is four mountains, but they don't join together to form a ring
1 2 1 2 1
1 1 1 1 1
1 2 1 2 1
1 1 1 1 1

3 3 3 3 3 -> there is a ring formed by the `3`s, but the `4` in the middle is taller so it doesn't qualify as a mountain ring
3 1 1 1 3
3 1 4 1 3
3 1 1 1 3
3 3 3 3 3

3 4 4 4 3
4 4 3 4 4
3 3 3 3 4
4 4 3 4 4
3 4 4 4 3

1  2  3  4  5
6  7  8  9  10
11 12 13 14 15
16 17 18 19 20
22 23 24 25 26

```

# Rules

* Standard Loopholes Apply
* This is , so the shortest answer in bytes in each language is declared the winner of its language. No answers will be accepted.
* The input may be taken as any reasonable form for a matrix of positive integers
* The output may be given as any two reasonable, consistent, distinct values indicating \[true\] or \[false\].

# Answer
# Jelly, 38 bytes

```
Ẇ€Z$⁺Ẏµ,ZẈ>2ẠµƇµḊṖZƊ⁺FṀ<,Z.ịḊṖ$€Ɗ€ƊȦ)Ṁ

```

Try it online!

Outputs **1** if the matrix contains mountain ranges, **0** otherwise.

## How it works (slightly outdated)

I may be able to shorten the code a bit, so this section will probably undergo heavy editing.

**The helper link**

```
,Z.ịḊṖ$€Ɗ€ – Helper link. Let S be the input matrix.
,Z         – Pair S with its transpose.
        Ɗ€ – For each matrix (S and Sᵀ), Apply the previous 3 links as a monad.
  .ị       – Element at index 0.5; In Jelly, the ị atom returns the elements at
             indices floor(x) and ceil(x) for non-integer x, and therefore this
             returns the 0th and 1st elements. As Jelly is 1-indexed, this is the
             same as retrieving the first and last elements in a list.
    ḊṖ$€   – And for each list, remove the first and last elements.

```

For example, given a matrix in the form:

```
A(1,1) A(1,2) A(1,3) ... A(1,n)
A(2,1) A(2,2) A(2,3) ... A(2,n)
A(3,1) A(3,2) A(3,3) ... A(3,n)
...
A(m,1) A(m,2) A(m,3) ... A(m,n)

```

This returns the arrays (the order doesn't matter):

```
A(1,2), A(1,3), ..., A(1,n-1)
A(m,2), A(m,3), ..., A(m,n-1)
A(2,1), A(3,1), ..., A(m-1,1)
A(2,n), A(3,n), ..., A(m-1,n)

```

Long story short, this generates the outermost rows and columns, with the corners removed.

**The main link**

```
Ẇ€Z$⁺Ẏµ,ZẈ>2ẠµƇµḊṖZƊ⁺FṀ<ÇȦ)Ṁ – Main link. Let M be the input matrix.
Ẇ€                           – For each row of M, get all its sublists.
  Z$                         – Transpose and group into a single link with the above.
    ⁺                        – Do twice. So far, we have all contiguous sub-matrices.
     Ẏ                       – Flatten by 1 level.
      µ      µƇ              – Filter-keep those that are at least 3 by 3:
       ,Z                      – Pair each sub-matrix S with Sᵀ.
         Ẉ                     – Get the length of each (no. rows, no. columns).
          >2                   – Element-wise, check if it's greater than 2.
            Ạ                  – All.
               µ          )  – Map over each sub-matrix S that's at least 3 by 3
                ḊṖ           – Remove the first and last elements.
                  ZƊ         – Zip and group the last 3 atoms as a single monad.
                    ⁺        – Do twice (generates the inner cells).
                     FṀ      – Flatten, and get the maximum.
                       <Ç    – Element-wise, check if the results of the helper
                               link are greater than those in this list.
                         Ȧ   – Any and all. 0 if it is empty, or contains a falsey
                               value when flattened, else 1.
                           Ṁ – Maximum.

```
> 3 votes

# Answer
# Clean, ~~224~~ ... 161 bytes

```
import StdEnv,StdLib
p=prod
~ =map
^ =reverse o$
@ =transpose o~(^o^)
$l=:[h:t]|h>1=l=[1: $t]
$e=e
?m=p[p(~p(limit(iterate(@o@)(~(~(\a|a>b=2=0))m))))\\n<-m,b<-n]

```

Try it online!

Defines the function `? :: [[Int]] -> Int`, returning `0` if there is an ring, and `1` otherwise.

Works by turning the matrix into `2`s for mountains and `0`s for valleys, then floods in with `1`s until the result stops changing. If any `0`s still exist for any mountain height, the product will be `0`.
> 2 votes

# Answer
# JavaScript (Node.js), 302 bytes

```
a=>a.some((b,i)=>b.some((n,j)=>(Q=(W=(i,j,f)=>[a.map((b,I)=>b.map((t,J)=>I==i&J==j)),...a+0].reduce(A=>A.map((b,I)=>b.map((t,J)=>f(I)(J)&&(A[I-1]||b)[J]|(A[I+1]||b)[J]|b[J-1]|b[J+1]|t))))(i,j,I=>J=>a[I][J]<=n)).some((b,i)=>b.some((d,j)=>d&&!i|!j|!Q[i+1]|b[j+1]==b.b))<!/0/.test(W(0,0,I=>J=>!Q[I][J]))))

```

Try it online!

Checks if flowing from a point can't reach the border, while border can walk to every point
> 1 votes

---
Tags: code-golf, decision-problem, matrix
---


title: Insta-Name... Just Add Coder!

text:
# Question
Title: Insta-Name... Just Add Coder!
In the English language, a surefire way to make a pronounceable nonsense letter combination is to make it entirely out of consonant-vowel pairs, e.g., *Wu* *ko* *pa* *ha*, or, *Me* *fa* *ro*, *consonant* first, followed by *vowel*.

### Challenge:

Write a program or function that will, given a user-specified number of letters, create a random name using this principle. It's that simple.

### Input:

An integer greater than or equal to 2 which designates the required number of letters in the output. Input can be taken from STDIN, command line arguments, or function arguments.

### Output:

A string of the given length containing randomly selected consonant-vowel pairs. It can be printed to STDOUT or closest alternative or returned in the case of a function.

### Rules:

1. Each consonant of the English alphabet should have equal probability of being selected for the first character of each pair, and each vowel of the English alphabet should have equal probability of being selected for the second character of each pair.
2. Letter pairs may be repeated.
3. Since this is a name, the first letter must be capitalized.
4. If the input is odd, a randomly selected letter pair in the name should have **y** or **h** appended to the end. The choice of y or h should be random as well.
5. Standard loopholes are not permitted.
6. Smallest code in bytes wins.

### Letter definitions:

Consonants:

```
bcdfghjklmnpqrstvwxyz

```

Vowels:

```
aeiou

```

### Example I/O:

```
Input: 6
Output: Mefaro

Input: 9
Output: Wukohpaha

```

Enjoy!

# Answer
# Pyth, 33 bytes

```
rsXOtQmO*-GJ"aeiou"J/Q2*%Q2O"hy"4

```

Demonstration.
> 7 votes

# Answer
# JavaScript ES6, ~~187~~ ~~180~~ 168 bytes

```
f=l=>{r=m=>Math.random()*m|0
d=l%2&&r(--l/2)*2+1
for(s='';l--;s+=s?a:a.toUpperCase())a=l%2?'bcdfghjklmnpqrstvwxyz'[r(21)]:'aeiou'[r(5)]+(l==d-1?'hy'[r(2)]:'')
return s}

```

Edit: I switched from using regex replace to a simple for loop, which improved the length considerably. Ungolfed code and test UI below. Input a negative number at your own risk because it makes an infinite loop. (Thanks to unclemeat for pointing that out.)

```
f=function(l){
  // Function to return a random integer between 0 and m-1 inclusive
  r=function(m){
    return Math.random()*m|0
  }
  // d is the position the h or y will be added
  // l is decremented only if l is odd so an extra consonant won't be added to the end
  d=l%2&&r(--l/2)*2+1

  for(s='';l--;){
    a=l%2?'bcdfghjklmnpqrstvwxyz'[r(21)]:'aeiou'[r(5)]+(l==d-1?'hy'[r(2)]:'')
    // If `s` is empty (i.e. this is the first leter), make it uppercase
    s+=s?a:a.toUpperCase()
  }
  return s
}

run=function(){ip=parseInt(document.getElementById('input').value);if(ip<2)return alert('Input must be greater than one.');document.getElementById('output').innerHTML=f(ip)};document.getElementById('run').onclick=run;run()
```

```
<input type="number" id="input" value="7" min="2" /><button id="run">Run</button><br />
<pre id="output"></pre>
```
> 7 votes

# Answer
# SWI-Prolog, ~~286~~ 285 bytes

```
a(I):-a(I,[]).
a(I,R):-(I=1,r(1,K),nth0(K,`hy`,V),length(R,L),random(1,L,W),nth0(W,[O:P|Q],V:0xFEFF,R);I=0,[O:P|Q]=R),N is O-32,p([N:P|Q]);r(5,A),nth0(A,`aeiou`,X),r(21,B),nth0(B,`bcdfghjklmnpqrstvwxyz`,Y),J is I-2,a(J,[Y:X|R]).
p([A:B|R]):-put(A),put(B),p(R);!.
r(I,R):-random(0,I,R).

```

Example: `a(13).` outputs `Leqihsekeqira`.

Note: You might need to replace the ``` with `"` if you have an old version of SWI-Prolog.
> 5 votes

# Answer
# Pyth, ~~52~~ 42 bytes

```
V/Q2=k++kO-GJ"aeiou"OJ;rs.SXZck2*%Q2O"hy"4

```

You can try it in the online compiler here.

Thanks to Jakube for golfing it down further, NinjaBearMonkey for clarifying the challenge, and issacg for creating Pyth and inadvertently teaching me about `X`.

This program randomly selects a consonant and a vowel to fill the string, adds 'h' or 'y' to one pair if the input is odd, then capitalizes the first character. Here is the breakdown:

```
V/Q2                                              For N in range(1, input/2):
    =k                                            Set k to:
        k                                         k (defaults to ""),
       + O G                                      plus a random letter from the alphabet...
          - J"aeiou"                              without the vowels,
      +             OJ                            plus a random vowel
                      ;                           End the loop
                             ck2                  Chop k into strings of length 2
                           XZ                     Append to the first string:
                                    O"hy"         'h' or 'y' picked at random,
                                *%Q2              repeated input mod 2 times
                         .S                       Shuffle the strings
                        s                         Convert them back to a single string
                       r                 4        Capitalize and print the string

```

It seems inefficient to append 'h' or 'y' to the first consonant-vowel pair and then scramble the list. I tried appending to a random pair but the code was always longer than this.
> 4 votes

# Answer
# Perl, ~~253~~ 238 bytes

```
@c=split"","bcdfghjklmnpqrstvwxyz";@v=split"","aeiou";@t=();chomp($n=<>);for(1..$n/2){$l=$c[$$=rand(21)];if($_<2){$l=uc$l};push@t,$l.$v[$$=rand(5)]};$x=0;$y=int(rand(@t));for(@t){print;if($x==$y&&$n%2>0){print qw(h y)[int(rand(1))]};$x++}

```

I can probably golf it further, but this should do for now.

Changes:

* Saved 10 bytes by myself, and 5 thanks to Alex A.
> 3 votes

# Answer
# Julia, 141 bytes

```
n->(R=rand;r=isodd(n)?R(1:n÷2):0;ucfirst(join([string("bcdfghjklmnpqrstvwxyz"[R(1:21)],"aeiou"[R(1:5)],i==r?"yh"[R(1:2)]:"")for i=1:n÷2])))

```

This creates an unnamed lambda function that accepts an integer as input and returns a string. it takes advantage of the fact that strings in Julia can be indexed and referenced like character arrays. To call it, give it a name, e.g. `f=n->...`.

Ungolfed + explanation:

```
function f(n)
    # There will be n÷2 consonant-vowel pairs
    p = n ÷ 2

    # Determine which pair will get a y or h, if any
    r = isodd(n) ? rand(1:p) : 0

    # Consonants and vowels
    c = "bcdfghjklmnpqrstvwxyz"
    v = "aeiou"

    # Randomly select letters for pairs, appending y or h as needed
    s = [string(c[rand(1:21)], v[rand(1:5)], i == r ? "yh"[rand(1:2)] : "") for i in 1:p]

    # Join s into a string and convert the first letter to uppercase
    ucfirst(join(s))
end

```

Examples:

```
julia> f(9)
"Luyvunize"

julia> f(2)
"Fe"

julia> f(16)
"Pahonapipesafuze"

```
> 3 votes

# Answer
# Python 2, ~~148~~ ~~169~~ 156

```
from random import*
I=input()
R=choice
i=I/2
S=[R('hybcdfgjklmnpqrstvwxz')+R('aeiou')for _ in[0]*i]
if I%2:S[R(range(i))]+=R('hy')
print ''.join(S).title()

```

Edit: Realized it didn't capitalize the first letter. Ill see if I can golf it back down tomorrow.
Edit 2: Remembered `.title` but I think that will be it.
> 3 votes

# Answer
# Marbelous, 203 bytes

```
}0}0@1
>>^0&1
--=0@1FF
??&0}0&0
&1
qqqqqq\\\\
//\\pppppp
:p
0000
?K\\?4..}2
<G++<4+5=0\/}0
<B++<3+5?111>1!!
<6++<2+3Mult-2
<3++<1+3+7}2{<
++//mm//mm--
mm..{1..{2{>
{0
:q
}2{2}0
pppppp{0{1
-W
:m
}061
{0{0

```

Test it out here (online interpreter). Input via arguments. Libraries and cylindrical boards must be enabled.

Commented/readable version:

```
}0 }0 @1 .. .. # 1st column: generate a number from 0 to length/2-1, wait on &1
>> ^0 &1 .. .. # 2nd column: check bottom bit; if zero activate &1, otherwise &0
-- =0 @1 FF .. # FF (wait on &0): if no h/y, set counter to 255 (0xFF)
?? &0 }0 &0 .. # Send copy of full length to :q
&1 .. .. .. ..
qq qq qq \\ \\ # Call :q with counter and length
// \\ pp pp pp # Output of :q falls into :p, which is called repeatedly until done

:p                      # prints a consonant/vowel pair, and h/y if needed
00 00 .. .. .. .. .. .. # two zeros, to be passed into ?K and ?4
?K \\ ?4 .. }2 .. .. .. # pass through ?K (0-20 = consonants) and ?4 (0-4 = vowels)
<G ++ <4 +5 =0 \/ }0 .. # 1st/2nd column: add 1-4 to skip vowels
<B ++ <3 +5 ?1 11 >1 !! # 3rd/4th column: add 3/6/11/16 to create nth vowel
<6 ++ <2 +3 Mu lt -2 .. # 5th/6th column: if counter is 0, generate either h or y
<3 ++ <1 +3 +7 }2 {< .. # 7th/8th column: if length left to print is 0-1, terminate
++ // mm // mm -- .. .. # mm: add 'a'. 1st/2nd start at 'b' (++)
                        #              5th/6th start at 'h' (+7)
mm .. {1 .. {2 {> .. .. # output consonant, vowel, h/y to {0, {1, {2
{0 .. .. .. .. .. .. .. # left input (length left): -2 + output to left
                        # right input (counter until print h/y): -1 + output to right

:q             # calls :p, but with the first letter capitalized
}2 {2 }0 .. .. # {2 is an unused output which prevents exit when all outputs are filled
pp pp pp {0 {1 # call :p, and forward return outputs to MB to start loop
-W .. .. .. .. # subtract W (0x20) from the first letter = capitalize it

:m    # add 0x61 ('a')
}0 61
{0 {0 # input + 0x61 is returned

```

This is roughly equivalent to the following pseudocode (`random(a,b)` generates numbers between `a` and `b` inclusive):

```
main(length)
    if length & 0x01 == 0 then
        counter, length_left = q(0xFF, , length)
    else
        counter, length_left = q(random(0, (length >> 1) - 1), , length)
    end
    while true do
        length_left, counter, consonant, vowel, hy = p(length_left, , counter)
        print consonant, vowel, hy
    end
p(length_left, , counter)
    if length_left <= 1 then terminate_program end
    consonant = random(0, 20)
    switch consonant
        case >16: ++consonant
        case >11: ++consonant
        case >6:  ++consonant
        case >3:  ++consonant
    ++consonant
    consonant = m(consonant)
    vowel = random(0, 4)
    switch vowel
        case >4: vowel += 5
        case >3: vowel += 5
        case >2: vowel += 3
        case >1: vowel += 3
    vowel = m(vowel)
    if counter == 0 then
        hy = random(0, 1) * 0x11
        hy += 7
        hy = m(hy)
    return length_left - 2, counter - 1, consonant, vowel, hy
q(counter, , length_left)
    length_left, counter, consonant, vowel, hy = p(length_left, , counter)
    print consonant - 0x20, vowel, hy
    return counter, length_left
m(number)
    return number + 'a'

```
> 3 votes

# Answer
## SmileBASIC 2 (Petit Computer), ~~197~~ 177 bytes

**CONTEMPORARY EDIT MAY 2018**: This was my first submission ever, nearly 3 years ago! My skills have improved a lot since then; -20 just from minor adjustments.

It starts with a prompt (it's left blank to save bytes, so it's just a ?) where you put in the length (stored in variable `L`).

```
C$="bcdfgjklmnpqrstvwxzhyaeiou"INPUT L
J=0 OR L/2K=-1IF L%2THEN K=RND(J)
FOR I=0TO J-1?CHR$(ASC(MID$(C$,RND(21),1))-32*!I)+MID$(C$,RND(5)+21,1)+MID$(C$,RND(2)+19,1)*(K==I);
NEXT

```

I'm sure participating with an obscure BASIC language is gonna get me nothing but weird looks, but I managed to make it pretty small for BASIC. It takes advantage of SB's weird quirks (like conditionals evaluating to 1 or 0 since there's no boolean type) to eliminate as many bytes as I possibly could have when I wrote this at 3AM.
> 3 votes

# Answer
# Ruby, 119 bytes

13 bytes for capitalizing...

```
->n{z=(0...n/2).map{([*(?a..?z)]-v=%w[a e i o u]).sample+v.sample}
n.odd?&&z[rand n/2]+='yh'[rand 2]
(z*'').capitalize}

```

Usage:

```
f=
->n{z=(0...n/2).map{([*(?a..?z)]-v=%w[a e i o u]).sample+v.sample}
n.odd?&&z[rand n/2]+='yh'[rand 2]
(z*'').capitalize}

2.upto(20) do |i|
  puts f[i]
end

```

Output:

```
Qo
Gah
Gilu
Baygu
Tevaba
Rohyori
Jigupadi
Diguvareh
Bidifenaji
Xohsuyileze
Depixoyizili
Boqizurejupiy
Buhuboketedasa
Vuwuhojetayduno
Forigikedawojawe
Qacetihxiheciyaju
Zoqigafukedugusoku
Bavuhlarofetucebapi
Zusiraxoxureqimavugo

```
> 2 votes

# Answer
# Ruby, ~~316 238~~ 216 chars

```
v=%w{a e i o u};c=[];(?a..?z).map{|i|v.include?(i)||c.push i};combos=[];c.map{|i| v.map{|j| combos.push i+j}};i=gets.to_i;o="";(i/2).times{o+=combos.sample};if i%2==1;(rand(4)==1?o+=?y:o+=?h); end; puts o.capitalize;

```

Odd number combos end in `h` or `y`.

Thanks to @blutorange for a complete dictionary of ruby golfing tips.

Whoa, I shortened my code by 100 chars.
> 1 votes

# Answer
# C, 219 characters

Seems to work, I'm still new to this.

```
char o[]="aeiouqwrtypsdfghjklzxcvbnm";n,i=0;main(int h,char**v){n=atol(v[1]);srand(time(0));h=n%2;for(;i<n-n%2;i+=2)printf("%c%c%c",o[rand()%21+5]-(i?0:32),o[rand()%5],(rand()%(n-1)<(i+2)&h)?h=0,'h'+(rand()%2?17:0):0);}

```
> 1 votes

# Answer
# R, 166 bytes

Takes input from STDIN and outputs to STDOUT.

```
l=letters;s=sample;n=scan();v=c(1,5,9,15,21);o=rbind(s(l[-v],i<-n/2),s(l[v],i,T));if(n%%2)o[a]=paste0(o[a<-s(i,1)*2],s(c('h','y'),1));o[1]=toupper(o[1]);cat(o,sep='')

```

Explanation

```
# Alias letters and sample
l=letters;
s=sample;
# Get input
n=scan();
# Vowel positions
v=c(1,5,9,15,21);
# Create a matrix with a row of
# consonants and a row of vowels
o=rbind(s(l[-v],i<-n/2),s(l[v],i,T));
# If odd paste either h or y to a vowel
if(n%%2)o[a]=paste0(o[a<-s(i,1)*2],s(c('h','y'),1));
# Upper case first letter
o[1]=toupper(o[1]);
# Output
cat(o,sep='')

```

Some tests

```
> l=letters;s=sample;n=scan();v=c(1,5,9,15,21);o=rbind(s(l[-v],i<-n/2),s(l[v],i,T));if(n%%2)o[a]=paste0(o[a<-s(i,1)*2],s(c('h','y'),1));o[1]=toupper(o[1]);cat(o,sep='')
1: 13
2:
Read 1 item
Vetigiysurale
> l=letters;s=sample;n=scan();v=c(1,5,9,15,21);o=rbind(s(l[-v],i<-n/2),s(l[v],i,T));if(n%%2)o[a]=paste0(o[a<-s(i,1)*2],s(c('h','y'),1));o[1]=toupper(o[1]);cat(o,sep='')
1: 12
2:
Read 1 item
Mucowepideko

```
> 1 votes

# Answer
# K5, 131 bytes

```
{r:(`c$-32+c@1?#c),{*d@1?#d:(v;(c::(`c$97+!26)^v::"aeiou"))@2!x}'1+1_!x;$[x=p:2*_x%2;r;,/(*w),("yh"@1?2),*|w:(0,2+2**1?_(#r)%2)_r]}

```

This will NOT work on Kona or kdb+; you need to use a K5 interpreter like oK.

Live demo. (Try setting the `5` at the end to a different number to try different inputs.)
> 1 votes

# Answer
## Perl 5, 112 bytes

```
@;=map{(grep aeiou!~$_,a..z)[rand 21].(a,e,i,o,u)[rand 5]}1..$_/2;$_%2?$;[rand@;].=time%2?h:'y':0;$_=$"^join"",@

```

Try it online!
> 1 votes

---
Tags: code-golf, random, word
---


title: Progression of Matrix Columns

text:
# Question
Title: Progression of Matrix Columns
Consider the infinite matrix:

```
0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1
0  0  2  3  0  0  2  3  0  0  2  3  0  0  2  3
0  0  0  4  5  6  0  0  0  4  5  6  0  0  0  4 ...
0  0  0  0  7  8  9 10  0  0  0  0  7  8  9 10
0  0  0  0  0 11 12 13 14 15  0  0  0  0  0 11
              ...

```

Each new row of the matrix is constructed by starting with `z` zeros, where `z` is the length of positive digits we're using in that row. The positive digits are constructed by starting with `1` and incrementing and adding an additional digit each time you iterate rows. That pattern is repeated infinitely to the right. So, for example, the first row starts `0, 1, 0, 1...` while the second row starts `0,0, 2,3, 0,0, 2,3...`. Following the pattern, the third row starts `0,0,0, 4,5,6, 0,0,0, 4,5,6...`.

Given two integers as input, `n` and `x`, output the first (top-most) `x` numbers of the `n`th column of the above matrix. (You can choose 0- or 1-indexing for the columns, just specify which in your submission.)

For example, for input `n = 0` (0-indexed), the column is entirely `0`s, so the output would just be `x` `0`s.

For input `n = 15` and `x = 6`, the output would be `[1, 3, 4, 10, 11, 0]`.

For input `n = 29` and `x = 15`, the output would be `[1, 0, 6, 8, 15, 0, 0, 34, 39, 0, 0, 0, 0, 0, 120]`.

For input `n = 99` and `x = 25`, the output would be `[1, 3, 4, 0, 15, 0, 0, 0, 37, 55, 56, 0, 87, 93, 0, 0, 151, 163, 176, 0, 0, 0, 0, 0, 325]`.

## I/O and Rules

* The input and output can be given by any convenient method.
* The input and output can be assumed to fit in your language's native number type.
* Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

# Answer
> 4 votes
# JavaScript (ES6), 45 bytes

Takes input in currying syntax `(n)(x)`.

```
n=>g=x=>x?[...g(x-1),n/x&1&&n%x+x*~-x/2+1]:[]

```

Try it online!

### How?

We use a direct formula to get the value of the cell at column **n** (0-indexed) and row **x** (1-indexed):

```
n / x & 1 &&     // is this cell zero or non-zero?
n % x +          // column modulo row --> increment for a non-zero value at this position
x * ~-x / 2 + 1  // minimum value of non-zero values for this row:
                 // ∑(i=1...x-1)(i) + 1 = x(x - 1) / 2 + 1

```

# Answer
> 3 votes
# , ~~80~~ 76 bytes

Thanks to @JayCe for pointing out a bug!

```
function(n,x)for(a in 1:x)print(rep(c(rep(0,a),((y=sum(1:a))-a+1):y),,n)[n])

```

Try it online!

Uses 1-based indexing for `n`. Very likely a golfier algorithm exists but `rep` is the enabler for the naive solution.

# Answer
> 2 votes
# Python 2, 69 bytes

```
n,x=input()
a=i=1
exec"print(([0]*i+range(a,a+i))*n)[n];a+=i;i+=1;"*x

```

Try it online!

# Answer
> 2 votes
# APL (Dyalog Classic), ~~27~~ ~~24~~ 23 bytes

-1 thanks to @FrownyFrog

```
⊢∘⍳(<×(+\⊣)--){+\⍵/2}|⊣

```

Try it online!

# Answer
> 2 votes
# MATL, ~~25~~ 18 bytes

```
x:"@:t~ys:b@-)h1G)

```

Try it online!

*Thanks to Luis Mendo for golfing out 6 bytes!*

This is essentially a MATL port of my R answer.

```
x		 % implicit input, read n and delete
:		 % implicit input, read x and push [1..x]
"		 % for loop with i = 1..x
 @:		 % push [1..i]
   t		 % duplicate
    ~		 % logical negate, turn to array of zeros
		 % stack: [[1..i], [0 .. (i times)]]
     y		 % duplicate from below
		 % stack: [[1..i], [0 .. (i times)], [1..i]]
      s:	 % sum and range
		 % stack: [[1..i], [0 .. (i times)], [1..(i * (i + 1)/2)]]
	b	 % bubble up
		 % stack: [[0 .. (i times)], [1..(i * (i + 1)/2)], [1..i]]
	 @-	 % push i and subtract. This will be used as a modular index to get the last i elements
		 % stack: [[0 .. (i times)], [1..(i * (i + 1)/2)], [1-i..0]]
	   )	 % index into array modularly to get the last i elements
		 % stack: [[0 .. (i times)], [(i-1)*i/2 + 1, .. (i * (i + 1)/2)]]
	    h	 % horizontally concatenate the array
	     1G) % push n and index modularly, leaving the result on the stack
		 % implicit end of for loop. The stack now contains the appropriate elements in order
		 % implicit end. Print stack contents

```

# Answer
> 1 votes
# Jelly, 11 bytes

```
ṖS+R¬;$)⁹ịⱮ

```

Try it online!

-1 thanks to Jonathan Allan.

Argument 1: **x**
Argument 2: **n + 1**

# Answer
> 1 votes
# Husk, 14 bytes

```
↑!Tzo¢+MRN0CNN

```

The argument `n` (first) is 1-indexed, try it online!

Alternatively we could use `↑!TṠzo¢+†K0CNN` for the same number of bytes.

### Explanation

```
↑!Tz(¢+)MRN0CNN -- example inputs n=4, x=3
            C N -- cut the natural numbers: [1,2,3,4,…]
             N  -- | using the natural numbers
                -- : [[1],[2,3],[4,5,6],[7,8,9,10],…]
        M N     -- map over the naturals
         R 0    -- | replicate 0 that many times
                -- : [[0],[0,0],[0,0,0],[0,0,0,0],…]
   z(  )        -- zip these two lists
      +         -- | concatenate
     ¢          -- | cycle
                -- : [[0,1,0,1,…],[0,0,2,3,0,0,2,3,…],…]
  T             -- transpose: [[0,0,0,0,…],[1,0,0,0,…],[0,1,0,0,…],[1,3,4,0,…],…]
 !              -- index into that list using n: [1,3,4,0,…]
↑               -- take x: [1,3,4]

```

# Answer
> 1 votes
# Husk, ~~21~~ 19 bytes

```
↑mȯ!⁰¢§+`R0§…ȯ→Σ←ΣN

```

Takes arguments as `n` (1-indexed), then `x`.
Saved 2 bytes thanks to BMO, but still not as short as BMO's answer.
My first attempt at using Husk.
Try it online!

# Answer
> 1 votes
# K (ngn/k), ~~33~~ 31 bytes

```
{(a>i)*(+\i)-i-a:(2*1+i:!y)!'x}

```

Try it online!

# Answer
> 1 votes
# Haskell, 75 bytes

```
u!v=take v[cycle((0<$l)++l)!!u|n<-[1..],l<-[take n$drop(sum[1..n-1])[1..]]]

```

Try it online!

# Answer
> 1 votes
# Python 2, 55 bytes

```
lambda n,x:[n/y%2*(n%y+y*~-y/2+1)for y in range(1,x+1)]

```

Try it online!

Developed independently; but I note that this ends up being a port of Arnauld's Javascript answer.

# Answer
> 1 votes
# Perl 5 `-n`, 52 bytes

```
/ /;say+(((0)x$_,($.+=--$_)..$.+$_)x$`)[$`]for 1..$'

```

Try it online!

# Answer
> 1 votes
# 05AB1E, 25 bytes

```
LO©LsL£¹£¹LÅ0s)øε˜®Ì∍}ø¹è

```

Try it online!

---

05AB1E goes with matrices like toothpaste and orange juice, but not a bad byte-count considered how bad my implementation is. Even my code is laughing at me "`LO©L`".

# Answer
> 0 votes
# Charcoal, 19 bytes

```
ＩＥ…·¹Ｎ§⁺Ｅι⁰ＥιＬ⊞Ｏυωη

```

Try it online! Link is to verbose version of code. Explanation:

```
    ¹               Literal 1
     Ｎ              First input (`x`) as a number
  …·                Inclusive range
 Ｅ                  Map (value `i`, 0-indexed counter `k`)
         ι          Current value
        Ｅ           Map over implicit range
          ⁰         Literal 0 (i.e. create array of `i` zeros)
            ι       Current value
           Ｅ        Map over implicit range
                 ω  Arbitrary variable
                υ   Predefined array
              ⊞Ｏ    Push
             Ｌ      Length
       ⁺            Concatenate arrays
      §           η Index by second input (`n`)
Ｉ                   Cast to string and implicitly print on separate lines

```

The snippet `ＥιＬ⊞Ｏυω` generates the next `i` integers by the expedient of pushing a dummy value to an array each pass through the loop and taking the length of the resulting array.

# Answer
> 0 votes
# Java 8, ~~65~~ ~~63~~ 60 bytes

```
n->x->{for(;x>0;)System.out.println(n/x%2*(n%x+x*--x/2+1));}

```

`n` is 0-indexed, `x` is 1-indexed, outputs the numbers new-line delimited and reversed.

Port of *@Arnauld's JavaScript (ES6) answer*.

Try it online.
A pretty-printed result in correct order is ~~8~~ 6 bytes longer: Try it online.

# Answer
> 0 votes
## Haskell, 67 bytes

```
i#l=cycle((++)=<<(0<$)$[i..l-1]):l#(l+l-i+1)
n!x=take x$(!!n)<$>1#2

```

Try it online!

```
i#l                  -- function # builds the infinite matrix
                     -- input: i and l are lowest and highest+1 non-zero number of
                     -- the current line
   = cycle           -- for the current line, repeat infinitely
           [i..l-1]  --   the non-zero numbers of the line appended
     (++)=<<(0<$)    --   to a list of 0s with the same length
   :                 -- append next row of the matrix
     l#(l+l-i+1)     --   which is a recursive call with i and l adjusted

n!x =                -- main function
              1#2    -- create matrix
      (!!n)<$>       -- pick nth element of each row
  take x             -- take the first x numbers thereof

```

---
Tags: code-golf, matrix
---