Help with complex reduction algorithm

Help with complex reduction algorithm
0

#1

UPD: Solved it.

Hi, thank you for wanting to help!

So I’m implementing a very hard (for me) script that should schedule the work of devices based on cost of kilowatt-hour in particular time of a day, combined power requirement as well as other factors. Of course it’s for training purpose, not production! :grinning:

I don’t yet know fundamental sorting algorithms, so the script is kinda crappy, but it also kinda works.

What is not working is the final part, where I’m creating a schedule for the day, where all of the devices should be corresponded to hours of the day. I’m trying to loop through each device, it’s hours to work, and for each hour push it to the array of this hour operating devices. There is also a power requirement that forbids device to be planned in the hour if it’s power consumption combined with already pushed devices will exceed the maximum allowed power consumption.

So I need a way to check if max power is exceeded (done), and if it is — redirect current device to the next hour. If in the next hour max power is also exceeded — redirect further and so on until there is no hours in a day left or if the device finally got scheduled.

I’m sorry for the amount of text and code in the example below, it’s really hard for me, but I refuse to give up on this problem. Please have a look at the code, specifically at the part at the bottom. Any additional critique, no matter how harsh, is also welcome!


#2

I see that you’ve solved this, but aren’t you complicating the whole process a bit too much?

This is my current understanding by looking to your code,

  • There is a constant amount of hourly power consumption limit
  • Devices can be run at any hour as long as they meet the daily quota
  • If devices are not running for 24h, the one with higher power consumption should run first.

Can’t you just use some greedy scheduling algorithm after placing all the device that must run for 24h? What is the need for all those sorting and reducing?


#3

There is some additional requirements on some devices (should be working only daily / nightly) that I’ve yet to implement, but yeah, you understood right.

Unfortunately, I haven’t yet studied algorithms, so I know nothing about “greedy scheduling algorithms” (other that it sounds kinda cool :sweat_smile:), though I’ve just googled something, but I don’t know if it’s the right one.

Maybe you can post a link on the right one?

Thanks for the feedback!


#4

Greedy scheduling is just a method of scheduling that picks best option on every turn and not looking back.

Here is how it might work for your application

  • Schedule all 24h running device. This reduces maximum hourly power capacity to constant amount.
  • Start filling the schedule array for each hour from the most power consuming device until the device quota is fulfilled or maximum power capacity is filled.

I’ll try to post the code, when I get some time.


#5

Right now this seems like something I’m currently doing in my code, huh.

I’ve found a bunch of resources about interval scheduling / partitioning / greedy algorithms, I’m reading them right now, maybe they’ll shed some light on this topic.

P.s. man I feel so much the need of a decent CS knowledge. I need to start learning CS basics asap.


#6

After I wrote the replica version of your algorithm, I can see that yours is pretty much the greedy algorithm that I’ve described. I just couldn’t see it in your code. I think your logic for this particular scheduling is solid although it works for good inputs only…

(My replica of your code is here: xvpm79loop-FCC-Problem
I’ve also added device.mode check and it seems to be working.)

I feel so much the need of a decent CS knowledge. I need to start learning CS basics asap.

Yep, this problem is less complex than things like OS scheduling, but knowing some CS would definitely benefit for any non trivial programming tasks.

There is a book called “Operating systems three easy pieces”, which you can freely look:
http://pages.cs.wisc.edu/~remzi/OSTEP/
From the chapter “CPU scheudling”, the book describes common issue with scheduling in general starting from primitive implementation.

GeeksForGeeks is also very nice for solving algorithm related problems and learning commonly used algorithms.


#7

Wow, our implementations ARE actually pretty similar (minus ugliness of mine compared to yours)! Thank you so much for taking the time to explain and write the solution!

This situation helped me to finally get my crap together and start the Harvard CS50. It is painful to feel myself handicapped by the lack of fundamentals.


#8

Yep, the logic is the same. Just put whatever best fitting stuff available at a time. I think this is as primitive as this type of problem gets.

I don’t know if CS50 is really a good introduction to CS. My impression was that it is more of a good introduction to programming with some CS. If you are comfortable with high school math and recursive thinking, then jumping directly into data structure and algorithm wouldn’t hurt.

But don’t listen to me, I’m not really advanced or anything like that.

P.S. It was fun for me to mess around with this, as well. I don’t get to solve things like this often.