Microsoft Visual Basic

frmMain - 1 ' ' ' ' ' '

OPTIMAL TYPESETTING 6.046 Problem Set 7, Problem 7-1 Kayla Jacobs 11/13/06 Recitation section: Shivani Agarwal, Friday 11am

' Collaborator: Dave Held

' The following Visual Basic code refers to the controls of the frmMain form. (See image) ' txtM is the textbox in which the value for M is entered. ' cmdLoad is the command button which loads the input text file when clicked ' txtOutput is the textbox in which the output (the input paragraph with lines ' optimally divided) is printed ' dlgOpen is the a Visual Basic Common Dialog Box control that provides the ' standard "Load File" dialog box for the user to load the input text file ' cmdQuit is a command button that exits the program when clicked

' ' ' ' ' ' ' ' '

But first, a BASIC limerick! (To make up for the non-hard-k0r3-ness of the programming language.) Beginners ' is who it is for. All-purpose? It lets you do more. Symbolic is how the Instruction is now; the Code loaded is what we adore. -- By user otherwisefine on OEDILF, the Omnificent English Dictionary In Limerick Form

' Global variables: '-----------------Private intInfinity As Integer Private strFileName As String Private M As String Private WordsArray() As String Private n As Integer Private CostsArray() As Long Private LineCostsMatrix() As Long Private EndWordsArray() As Integer

Private Sub cmdLoad_Click() '-------------------------' The action of the Load command button when clicked

frmMain - 2

'Open Common Dialog "Open File" box, with *.txt as default extension, ' and retrieve file name of text file to process dlgOpen.FileName = "*.txt" dlgOpen.ShowOpen strFileName = dlgOpen.FileName M = CInt(txtM.Text) Call TheActualAlgorithm End Sub Private Sub cmdQuit_Click() '-------------------------Unload Me End Sub Private Sub txtM_Change() '-----------------------'Once a value for M has been entered, enable "Load File" command button. Otherwise, keep it grayed out. If (txtM.Text <> "") Then cmdLoad.Enabled = True Else cmdLoad.Enabled = False End If End Sub Private Sub TheActualAlgorithm() '------------------------------intInfinity = -9999 ' Populate WordsArray: Call LoadWordsArray n = UBound(WordsArray) - LBound(WordsArray) 'Initialize each entry of the LineCostsMatrix to -1: ReDim LineCostsMatrix(1 To n, 1 To n) Dim i, j As Integer For i = 1 To n

frmMain - 3 For j = 1 To n LineCostsMatrix(i, j) = -1 Next j Next i 'Initialize each entry of CostsArray to -1: ReDim CostsArray(1 To n) For i = 1 To n CostsArray(i) = -1 Next i ReDim EndWordsArray(1 To n) Dim lngMinCost As Long For i = n - 1 To 1 Step -1 lngMinCost = MinCost(i) Next i Dim strOutput As String strOutput = "M is " & Str(M) & vbCrLf

' Note vbCrLf makes a line break

strOutput = strOutput & "COST = " & intMinCost & vbCrLf Dim intStartWord, intEndWord, intNumberOfLines, intLine, intLineChars, intWord As Integer intStartWord = 1 intNumberOfLines = 0 intLine = 1 Do While (intStartWord < n) intNumberOfLines = intNumberOfLines + 1 intEndWord = EndWordsArray(intStartWord) intStartWord = intEndWord + 1 Loop intStartWord = 1 For i = 1 To n MsgBox EndWordsArray(i) Next i Do While (intStartWord <= n) intEndWord = EndWordsArray(intStartWord) intLineChars = SumOfLengthsOfWords(intStartWord, intEndWord)

frmMain - 4 'len(wordsarray(intEndWord)) - len(intStartWord 'Add spaces before fewer-digited line numbers: For i = NumberOfDigits(intLine) To NumberOfDigits(intNumberOfLines) - 1 strOutput = strOutput & " " Next i strOutput = strOutput & Str(intLine) & ": [" & Str(intLineChars) & "] " For i = intStartWord To intEndWord strOutput = strOutput & WordsArray(i) & " " Next i strOutput = strOutput & vbCrLf intStartWord = intEndWord + 1 intLine = intLine + 1 Loop txtOutput.Text = strOutput End Sub Private Sub LoadWordsArray() '--------------------------' Post: WordsArray contains the n words in the file strFileName, in the order in which they appear. 'Initialize WordsArray to empty: ReDim WordsArray(0) 'Load file strFileName for input: Dim intFileNum As Integer intFileNum = FreeFile Open strFileName For Input As #intFileNum Dim Dim Dim Dim

strTempLine As String intTempNumberofWordsinLine TempLine() As String i As Integer

Do While (EOF(intFileNum) = False)

'(EOF = End Of File)

'Input the next line in the file as strTempWord: Input #intFileNum, strTempLine

frmMain - 5 TempLine = Split(strTempLine) 'Resize WordsArray, increasing its length by the number of words in TempLine ReDim Preserve WordsArray(UBound(WordsArray) - LBound(WordsArray) + UBound(TempLine) - LBound(TempLine)) For i = LBound(TempLine) To UBound(TempLine) WordsArray(UBound(WordsArray) - (UBound(TempLine) - LBound(TempLine)) + i) = TempLine(i) Next i Loop Close #intFileNum End Sub Private Function SumOfLengthsOfWords(ByVal intStartWord As Integer, ByVal intEndWord As Integer) As Integer '-------------------------------------------------------------------------'Post: Returns the sum of the lengths of the WordsArray(k) as k ranges from intStartWord to intEndWord inclusive SumOfLengthsOfWords = 0 Dim temp As Integer temp = intStartWord Do While (temp <= intEndWord) SumOfLengthsOfWords = SumOfLengthsOfWords + Len(WordsArray(intStartWord)) temp = temp + 1 Loop End Function Private Function LineCost(intStartWord As Integer, intEndWord As Integer) As Long '-------------------------------------------------------------------------------' Post: Returns the cost of printing words intStartWord through intEndWord on a line 'If words intStartWord through intEndWord do not fit on a line If (SumOfLengthsOfWords(intStartWord, intEndWord) > M) Then LineCost = intInfinity 'If j=n (intStartWord.e. last line): ElseIf (intEndWord = UBound(WordsArray)) Then LineCost = 0 Else LineCost = (M - intEndWord + intStartWord - SumOfLengthsOfWords(intStartWord, intEndWord)) ^ 3

frmMain - 6 End If End Function Private Function MinCost(ByVal i As Integer) As Long '--------------------------------------------------If (i >= n) Then 'Last word or beyond MsgBox "Oh no! The world is coming to an end!" Unload Me Else Dim lngRemainingCost As Long 'If CostsArray(i) has not yet been calculated If (CostsArray(i) = -1) Then Dim j As Integer For j = i To n - 1 'If LineCostsMatrix(i, j) has not yet been calculated: If (LineCostsMatrix(i, j) = -1) Then LineCostsMatrix(i, j) = LineCost(i, j) If (LineCostsMatrix(i, j) = intInfinity) Then Exit For End If End If If (j = n - 1) Then intRemainingCost = 0 'Last word Else If (CostsArray(j + 1) = -1) Then intRemainingCost = MinCost(j + 1) Else intRemainingCost = CostsArray(j + 1) End If End If If (LineCostsMatrix(i, j) <> intInfinity And LineCostsMatrix(i, j) >= 0 And (CostsArray(i) = -1 Or ((LineCosts Matrix(i, j) + intRemainingCost) < CostsArray(i)))) Then CostsArray(i) = LineCostsMatrix(i, j) + intRemainingCost EndWordsArray(i) = j End If

frmMain - 7 Next j End If MinCost = CostsArray(i) End If End Function Private Function NumberOfDigits(ByVal x As Integer) As Integer '--------------------------------------------------------------' Post: Returns the number of digits in i (in base 10) ' Example: NumberOfDigits(3)=1, NumberOfDigits(522)=3 NumberOfDigits = 1 Dim temp As Integer temp = x Do While (temp >= 10) temp = Int(temp / 10) 'Int function performs floor action NumberOfDigits = NumberOfDigits + 1 Loop End Function

frmMain - 1 VERSION 5.00 Object = "{F9043C88-F6F2-101A-A3C9-08002B2F49FB}#1.2#0"; "comdlg32.ocx" Begin VB.Form frmMain Caption = "Typesetting" ClientHeight = 4956 ClientLeft = 48 ClientTop = 336 ClientWidth = 7320 ControlBox = 0 'False LinkTopic = "Form1" ScaleHeight = 4956 ScaleWidth = 7320 StartUpPosition = 2 'CenterScreen Begin VB.CommandButton cmdQuit Caption = "Quit" Height = 372 Left = 6120 TabIndex = 6 Top = 4560 Width = 1092 End Begin VB.TextBox txtM Height = 288 Left = 3360 TabIndex = 4 Text = "10" Top = 240 Width = 612 End Begin VB.TextBox txtOutput BeginProperty Font Name = "Courier" Size = 9.6 Charset = 0 Weight = 400 Underline = 0 'False Italic = 0 'False Strikethrough = 0 'False EndProperty Height = 3732 Left = 120 ScrollBars = 2 'Vertical TabIndex = 3 Top = 720 Width = 7092 End

frmMain - 2 Begin VB.CommandButton cmdLoad Caption = "Load Input Text File" Height = 372 Left = 5520 TabIndex = 2 Top = 240 Width = 1692 End Begin MSComDlg.CommonDialog dlgOpen Left = 5640 Top = 4560 _ExtentX = 677 _ExtentY = 677 _Version = 393216 End Begin VB.Label lblDate AutoSize = -1 'True Caption = "11/13/06" Height = 192 Left = 2760 TabIndex = 7 Top = 4560 Width = 648 End Begin VB.Label Label1 AutoSize = -1 'True Caption = "Enter value for M (max # of characters/line):" Height = 192 Left = 120 TabIndex = 5 Top = 240 Width = 3072 End Begin VB.Label lblKayla AutoSize = -1 'True Caption = "Kayla Jacobs" Height = 192 Left = 120 TabIndex = 1 Top = 4560 Width = 984 End Begin VB.Label lbl6046 AutoSize = -1 'True Caption = "6.046 Problem 7-1" Height = 192

frmMain - 3 Left TabIndex Top Width End End

= = = =

1320 0 4560 1272

Enter value for M (max # of characters/line):

Kayla Jacobs

6.046 Problem 7-1

11/13/06