Skip to content

Instantly share code, notes, and snippets.

@schveiguy
Created September 4, 2019 20:14
Show Gist options
  • Save schveiguy/1ba3f77037b579d520d1c5501325d70d to your computer and use it in GitHub Desktop.
Save schveiguy/1ba3f77037b579d520d1c5501325d70d to your computer and use it in GitHub Desktop.
Raindrops demo code.
import std.algorithm;
void main(string[] args)
{
import std.stdio;
// args[0] is the program name, args[1] through args[n] are the input strings.
// first validate the input
auto input = args[1 .. $];
foreach(i; 1 .. input.length)
{
assert(input[i].length == input[i-1].length); // all same length
}
assert(input[0].length <= input.length); // can get to the house!
int spaces = cast(int)input[0].length + 1; // add one space for the house (no raindrops can fall there)
int ticks = cast(int)input.length + 1; // One tick extra for the starting state before you left your car.
int[][] raindrops = new int[][](ticks, spaces);
// beginning state, can only be starting at the car. We use int.max / 2 because
// we are looking for the minimum, and int.max / 2 will always be the highest
// thing. We divide by 2 to avoid integer overflow.
raindrops[0][] = int.max / 2;
raindrops[0][0] = 0; // start completely dry at the car
int curtick = 0;
foreach(droplist; input)
{
++curtick;
int hasDrop(int i)
{
if(i >= droplist.length)
// in house
return 0;
if(droplist[i] == '1')
return 1;
return 0;
}
// handle first and last spaces specially
raindrops[curtick][0] = min(raindrops[curtick - 1][0], raindrops[curtick - 1][1]) + hasDrop(0);
raindrops[curtick][spaces - 1] = min(raindrops[curtick - 1][spaces - 1],
raindrops[curtick - 1][spaces - 2]); // no raindrops in the house
foreach(j; 1 .. spaces - 1)
{
raindrops[curtick][j] =
min(raindrops[curtick - 1][j - 1], // move ahead one space
raindrops[curtick - 1][j], // stand still
raindrops[curtick - 1][j + 1]) // move back one space
+ hasDrop(j); // add the new raindrop at this space
}
}
// writeln(raindrops);
// result is in the house
writeln(raindrops[curtick][spaces - 1], " min raindrops");
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment