RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved sequence processing and a cost optimisation. (Note that this is open until 4 June 2023.)

Task 1: Sorted Squares

You are given a list of numbers.

Write a script to square each number in the list and return the sorted list, increasing order.

This is mostly a one-liner, though in some languages it's easier to sort as a separate operation.

Perl:

sub sortedsquares($lst) {
  return [sort {$a <=> $b} map{$_ * $_} @{$lst}];
}

The shortest version is in PostScript, though admittedly it relies on my libraries to provide map and quicksort.

/sortedsquares {
    { dup mul } map quicksort
} bind def

Task 2: Travel Expenditure

You are given two list, @costs and @days.

The list @costs contains the cost of three different types of travel cards you can buy.

The list @days contains the day number you want to travel in the year.

The periods of the cards are fixed at 1, 7 and 30 days, so the trick is to cover all days with one card or another at minimum total cost. Here's the JavaScript:

function travelexpenditure(costs, days0) {

Make sure the days are in order.

    let days = days0;
    days.sort(function(a,b) {
        return a-b;
    });

Set the validity periods.

    const validities = [1, 7, 30];

Set up the stack for a FIFO search.

    let stack = [];
    stack.push([0, days]);

One possible cost is an individual one-day ticket for each day, so let's set that as the starting value.

    let cheapest = days.length * costs[0];
    while (stack.length > 0) {
        const c = stack.shift();

As an entry comes off the stack, if there are no more days to cover, compare this cost with the cheapest found so far and log it if it's cheaper.

        if (c[1].length == 0) {
            if (c[0] < cheapest) {
                cheapest = c[0];
            }
        } else {

If we haven't finished but we're already costing more than the cheapest found so far, skip this leg.

            if (c[0] >= cheapest) {
                continue;
            }

The first day we'll cover in this leg is the lowest remaining value.

            const start = c[1][0];

Test each possible type of card.

            for (let i = 0; i <= 2; i++) {

Work out the last day for which this card will be valid.

                const ed = start + validities[i] - 1;

Remaining days are those later than that one.

                let dtd = c[1].filter(x => x > ed);

Push onto the stack the new cost, and the new remaining days.

                stack.push([c[0] + costs[i], dtd]);
            }
        }
    }
    return cheapest;
}

Since this is an exhaustive search it could have been done with a LIFO, but I felt like doing a FIFO, and at these sizes the performance loss (on languages without a dedicated double-ended array type) is very minor.

Full code on github.