Leet Code #2472

2472: Painting the Walls

Getting some more practice in, with more targetted prep to come.

Iteration One

Goals

Get a first working solution without looking at answers
Implement a >50% runtime solution

#include <iostream>
#include <string>

if (__cplusplus == 202101L) 
    std::cout << std::string("C++23");
else if (__cplusplus == 202002L) 
    std::cout << std::string("C++20");
else if (__cplusplus == 201703L) 
    std::cout << std::string("C++17");
else if (__cplusplus == 201402L) 
    std::cout << std::string("C++14");
else if (__cplusplus == 201103L) 
    std::cout << std::string("C++11");
else if (__cplusplus == 199711L) 
    std::cout << std::string("C++98");
else 
    std::cout << std::string("pre-standard C++.") << std::to_string(__cplusplus);

std::cout << std::string("\n");

#include <deque>
#include <iterator>
#include <iostream>
#include <string>
#include <algorithm>

// ---- COPY FROM HERE ----

class Solution {
public:
    /**
     * @pre size of cost == size of time
    */
    int paintWalls(std::vector<int>& cost, std::vector<int>& time) {

        // The greedy approach:
        //  - Sort pairs by cost, then time
        //  - Pop pairs off list for paid painter
        //  - Grab walls for free painter from other end

        // https://stackoverflow.com/questions/18478385/convert-two-vectors-of-int-with-the-same-length-into-one-vector-of-pairs-of-int
        std::vector<std::pair<int, int>> priorities;

        std::transform(cost.begin(), cost.end(), time.begin(), std::back_inserter(priorities),
            [] (int cost, int time) { return std::make_pair(cost, time); });

        for (auto iter = priorities.begin(); iter != priorities.end(); ++iter)
        {
            std::cout << (*iter).first << ", " << (*iter).second << std::endl << std::flush;
        }
        
        std::sort(priorities.begin(), priorities.end(), 
            [] (auto &left, auto &right) 
            {
                // Want to do lowest cost, and then lowest time
                // if (left.first < right.first)
                //     return true;
                // else if (left.first == right.first && left.second < right.second )
                //     return true;
                // else
                //     return false;

                // Cost per hour
                if ((left.first / left.second) < (right.first / right.second))
                    return true;
                // Equal cost per hour, then go with lesser cost
                else if ((left.first / left.second) == (right.first / right.second) && left.first < right.first )
                    return true;
                else
                    return false;
            });

        for (auto iter = priorities.begin(); iter != priorities.end(); ++iter)
        {
            std::cout << (*iter).first << ", " << (*iter).second << std::endl << std::flush;
        }
        
        int tmp_time = -1;
        int total_cost = 0;

        std::deque<std::pair<int,int>> work_deque(priorities.size());
        std::move(begin(priorities), end(priorities), back_inserter(work_deque));

        while (!work_deque.empty())
        {
            // Paid Worker
            std::pair paid_job = work_deque.front();
            work_deque.pop_front();
            tmp_time = paid_job.second;
            total_cost += paid_job.first;

            // Free Worker
            while (tmp_time > 0 && !work_deque.empty()) {
                // If there are only two jobs left and only get one for free
                if (work_deque.size() == 2 && tmp_time == 1) 
                {   
                    std::pair front = work_deque.front();
                    work_deque.pop_front();
                    std::pair back = work_deque.back();
                    work_deque.pop_back();

                    total_cost += std::min(front.first, back.first);
                }
                else
                {
                    work_deque.pop_back();
                    tmp_time--;
                }
            }
        }

        return total_cost;
    }
};

// ---- COPY FROM HERE ----

Solution tmp;
std::vector<int> cost1;
cost1 = { 1,2,3,2 };
std::vector<int> time1;
time1 = { 1,2,3,2 };
std::vector<int> cost2;
cost2 = { 2,3,4,2 };
std::vector<int> time2;
time2 = { 1,1,1,1 };
std::vector<int> cost3;
cost3 = { 26,53,10,24,25,20,63,51 };
std::vector<int> time3;
time3 = { 1, 1, 1, 1, 2, 2, 2, 1 };
std::vector<int> cost4;
cost4 = { 8,7,5,15 };
std::vector<int> time4;
time4 = { 1,1,2,1 };
std::vector<int> cost5;
cost5 = { 42,8,28,35,21,13,21,35 };
std::vector<int> time5;
time5 = { 2,1,1,1,2,1,1,2 };
std::vector<int> cost6;
cost6 = { 76,25,96,46,85,19,29,88,2,5 };
std::vector<int> time6;
time6 = { 1,2,1,3,1,3,3,3,2,1 };

std::cout << "Expected: 3 Generated: \n" << tmp.paintWalls(cost1,time1) << std::endl << std::flush;
std::cout << "Expected: 4 Generated: \n" << tmp.paintWalls(cost2,time2) << std::endl << std::flush;
std::cout << "Expected: 55 Generated: \n" << tmp.paintWalls(cost3,time3) << std::endl << std::flush;
std::cout << "Expected: 12 Generated: \n" << tmp.paintWalls(cost4,time4) << std::endl << std::flush;
std::cout << "Expected: 63 Generated: \n" << tmp.paintWalls(cost5,time5) << std::endl << std::flush;
std::cout << "Expected: 46 Generated: \n" << tmp.paintWalls(cost6,time6) << std::endl << std::flush;

%%timeit

Solution tmp;
std::vector<int> cost1;
cost1 = { 1,2,3,2 };
std::vector<int> time1;
time1 = { 1,2,3,2 };

tmp.paintWalls(cost1,time1);
tmp.paintWalls(cost2,time2);

Results

We will have to wait and see how our internal timings compare to leetCode runtime analysis

I started to look at a solution here, as the algorithm was proving to not be workable with my simple approach.
1812 / 2557 testcases passed: clearly there are edge cases where my algorithm doesn’t look to build a true solution, and makes greedy (incorrect) choices
My min cost/hour did help improve the amount of test cases that pass

Iteration Two

Goals

Implement DP in order to solve all test cases

Reference Solution

https://leetcode.com/problems/painting-the-walls/solutions/4166467/not-hard-video-solution-dynamic-programming-explained-easy-to-understand/

class Solution {
public:
    int paintWalls(int[] cost, int[] time) {
        int n = cost.length;
        int[] money = new int[n+1];
        Arrays.fill(money,(int)1e9);
        money[0]=0;
        for(int i=0;i<n;i++)
        {
            for(int j=n;j>0;j--)
            {
                money[j]=Math.min(money[j],money[Math.max(j-time[i]-1,0)]+cost[i]);
            }
        }
        return money[n];
    }
}

#include <vector>
#include <algorithm>

class Solution {
public:
    /**
     * @pre size of cost == size of time
    */
    int paintWalls(std::vector<int>& cost, std::vector<int>& time) {
        std::vector<int> cost_per_wall(cost.size() + 1, 1e9);
        cost_per_wall[0] = 0;

        // Loop forward over walls, determining cost as we go
        for(int i = 0; i < cost.size(); i++)
        {
            // Loop backwards from the end of the list
            // Start with trying to paint all walls in remaining time
            for(int j = cost.size(); j > 0; j--)
            {
                // 
                int x = j - time[i] - 1;
                int tmp = std::max(x, 0);
                // if tmp == 0, we ~can~ paint all remaining walls
                int tmp2 = cost_per_wall[tmp];
                // if tmp == 0, then tmp2 == 0
                int curr_wall_cost = cost[i];
                int curr_try_max = cost_per_wall[j];
                int tmp4 = std::min(curr_try_max, tmp2 + curr_wall_cost);
                // if we can paint all reamining walls with time, tmp2 == 0 and we take curr_wall_cost
                // Otherwise tmp = num_remaining_walls, tmp2 = best_guess_for_cost_to_paint_num_remaining,
                //      min (cost of painting this wall, best_guess + current_wall's cost)
                // As we build the solution dynamically, this should get us the best solution
                cost_per_wall[j] = tmp4;
            }

        }
        return cost_per_wall[cost.size()];
    }
};

#include <vector>
#include <algorithm>

class Solution {
public:
    /**
     * @pre size of cost == size of time
    */
    int paintWalls(std::vector<int>& cost, std::vector<int>& time) {
        std::vector<int> cost_per_wall(cost.size() + 1, 1e9);
        cost_per_wall[0] = 0;

        for(int i = 0; i < cost.size(); i++)
        {
            for(int j = cost.size(); j > 0; j--)
            {
                cost_per_wall[j] = std::min(cost_per_wall[j], cost_per_wall[std::max(j - time[i] - 1, 0)] + cost[i]);
            }

        }
        return cost_per_wall[cost.size()];
    }
};

I decided to leave it here, and taking a pening coding interview. Maybe look forward to more of this to come, but C++ proves difficult to do in this execution environment, and I think the Python side of things is the more interesting use-case for this, so will be the focus moving forward. Cool mini-series?