Dynamic programming to solve two printers with different speeds

Question

I solved this problem using a Class, but thought I might try to figure out this memoization thing.

Problem
There are two printers that print pages at different speeds (X, Y). What is the minimum amount of time it takes to print (N) pages?

Input Data
First line contains the number of test cases
Each test case is on a new line in the form of X Y N

Output
The minimum printing time for each test case separated by spaces

e.g.

input data:
2
1 1 5
3 5 4
output:
3 9

The math here is trickier than it appears, so make the assumption that my math is correct (it is).

Code

Option Explicit On
Option Strict On
Option Infer On
Option Compare Text
Module Module1
 <STAThread>
 Sub Main()
 Const inputPath As String = "C:\Temp\printers.txt"
 Dim delimiters As String = " " & System.Environment.NewLine
 Dim data() As Integer = System.IO.File.ReadAllText(inputPath).Split(delimiters.ToCharArray(), StringSplitOptions.RemoveEmptyEntries) _
 .Select(Function(i) Integer.Parse(i)).ToArray
 Dim result As String
 For i As Integer = 0 To data(0) - 1
 result = result & BestTime(data(i * 3 + 1), data(i * 3 + 2), data(i * 3 + 3)) & " "
 Next
 result = result.Trim()
 System.IO.File.AppendAllText(inputPath, Environment.NewLine & result)
 End Sub
 Public Function BestTime(ByVal X As Double, ByVal Y As Double, ByVal N As Integer) As Double
 Dim myTimes(1) As Double
 For nextpage As Integer = N To 1 Step -1
 If myTimes(0) + X <= myTimes(1) + Y Then
 myTimes(0) = myTimes(0) + X
 Else
 myTimes(1) = myTimes(1) + Y
 End If
 Next
 Return myTimes.Max
 End Function
End Module

For some reason I couldn't get the delimiters to work as a constant. I'm using doubles because I kept getting overflow.

---

Additional test data

Input

16
206 120 2925144
5680 2268 173606
443 144 2231807
1336 1966 235314
251936 215499 755
1 1 610653060
27229864 68593621 7
13 11 58925803
25 13 39786943
936 301 970391
6811369 9145334 90
3070457 3923385 93
111 126 4757640
16350510 10897861 9
171127 91014 3379
2 2 373415582

Output

221808480 281383956 242540784 187180894 87708093 305326530 137187242 
351099580 340283073 221013936 354191188 160858785 280761012 65387166 
200776884 373415582

Answer 1

Your BestTime method looks great. The nextpage variable is never used, so it doesn't really matter which direction the loop goes. I'd be curious why you are using a decrementing loop, but it doesn't matter which direction you use in the grand scheme of things.

---

Choosing Double because Integer gives you overflow seems misleading. At first I thought "oh good, it handles decimal rates, like 2 1/2 pages per minute". The algorithm looks like it should work for floating point, though.

If you only want to support integral types, you can use Long or ULong. Based on the test cases you provided, Long is sufficient.

---

myTimes(0) + X and myTimes(1) + Y are calculated twice. For this scale of number it's not a huge performance loss. But if you were extending this to BigInteger levels, you could calculate them both once and assign the number if needed.

This is the kind of optimization that would require benchmarking before deciding if it is worthwhile.

---

A Const for delimeters won't work because System.Environment.NewLine is read only property that is not available at compile time. There are a couple of alternatives:

• use a ReadOnly field instead of Const
• use vbNewLine instead of System.Environment.NewLine
  • Note, this will (possibly) be different functionality.

However, you only use delimeters in one spot, so a method variable like you currently have is fine.

---

You did a good job separating the algorithm from input/output. You could take it further by wrapping input handling in its own function outside of Main.

---

If this weren't for a "competition" style of programming, I would recommend a parameter for the input file name so that the user can change it. I'd also strongly encourage a separate parameter for output. Right now, the user needs to perform an extra step before running your program a second time.

Additionally, you could use more descriptive variable names than X, Y, and N. It matches the competition specs so it's perfect in this instance. But for a long term program I would recommend something like printerXSpeed or numberOfPagesToPrint. The caveat is you never know when that one off function you write gets put in production for years.