The Coin Changing Problem!

Greedy algorithm change diagram

Image via Wikipedia

The coin changing problem is a known problem in the field of algorithms and a famous example in Greedy Algorithms which is one of the good ways for a making a good coin change. The problem states that “given a set of coins with several values, it is required to make a change using those coins for a particular amount of cents using the minimum number of coins”.

As we mentioned earlier, a greedy algorithm solution is known which is, in fact, how millions of people change money every day. That is, start chaning with the largest coin available until the remaining amount to change is less than the largest coin value, then start changing with the next possible coin(the coin with the lower value). Continue with repeated changing until there are no more cents left to change. Below is the VB.NET implementation of a simple coin changer using the above algorithm:

Private Function SetAvailableCoins(ByVal strCoins As String, _
                               ByRef Coins() As Int64) As Boolean
    Dim coinsstr() As String = strCoins.Split(","c)
    ReDim Coins(coinsstr.Length - 1)
    For i As Int64 = 0 To coinsstr.Length - 1
        If Not IsNumeric(coinsstr(i)) Then
            Erase Coins
            Return False
        Else
            Coins(i) = coinsstr(i)
        End If
    Next
    Return True
End Function

Private Function MakeChange(ByVal Amount As Int64, _
                            ByRef Coins() As Int64) As String
    Dim value As Int64 = Amount
    Dim str As String = String.Empty
    Dim count As Int64 = 0
    While value > 0
        Dim maxCoin As Int64 = 0
        For Each c As Int64 In Coins
            If c  maxCoin Then
                maxCoin = c
            End If
        Next
        Dim change As Int64 = Math.Floor(value / maxCoin)
        value -= change * maxCoin
        str &= change & " Coin(s) of value " & maxCoin & _
                 " (Remaining = " & value & ")" & vbCrLf
        count += change
    End While
    str &= vbCrLf & "Total number of coins = " & count
    Return str
End Function

Private Sub btnChange_Click(ByVal sender As System.Object, _
            ByVal e As System.EventArgs) Handles btnChange.Click
    Dim coins(0) As Int64
    If txtCoins.Text  "" AndAlso SetAvailableCoins(txtCoins.Text, _
                                                     coins) Then
        txtChange.Text = MakeChange(txtAmount.Value, coins)
    End If
End Sub

The functions above assume you have created the form below and added the appropriate controls:

In the example shown in the form above, we have 4 coins with values:1,5,10 and 25. The amount we would like to change is 36. When we click on the change button the result is displayed in the Change Textbox. Notice the result consists of 1 coin of value 25,1 coin of value 10 and 1 coin of value 1. This is in fact the optimal solution to the given amount of cents. Lets consider another for the value 30, as we would expect, the results will be 1 coin of value 25 and 1 coin of value 5 which is also the optimal solution. Now lets suppose we had only 3 coins instead of 4 by removing the coin of value 5 and we want to make change for 30 cents again. The results are displayed below:

As you can see, the change is 1 coin of value 25 and 5 coins of value 1 giving a sum of 6 coins!. Offoucrse, this is not an optimal solution because a human would have suggested to use 3 coins of value 10!. The reason for the error here is becuase greedy algorithms do not guarantee an optimal solution although they guarantee to find a solution in a reasonable amount of time. Assume we have millions of coin values and we want to make a change for an extremely large amount, it is not possible to be done by a human being! here is where the greedy algorithm we discussed comes into play.

The project is downloadable here CoinChangingProblem.zip(remove the .doc extension).

Advertisements

Using JQuery Shadowbox inside Asp.Net UpdatePanel

Shadowbox is an amazing extension for JQuery that allows you to easily play around with image galleries, modal dialogs,internal pages and much more while providing a rich user interface that captures the eye. It is also easy to implement in your web pages. However, .net developers often lose the functionality of shadowbox if they are using it from inside an update panel which is part of the microsoft ajax framework.

Shadowbox does not work inside the update panel becuase the content within the panel is dynamically updated after a partial postback. This causes the bindings of shadowbox on the inner html content to break and therefore, the nice shadowbox will not open again.

However, there is a nice little workaround to fix this issue. The solution is easy to implement and configure on you current project. All we need to do is reinitialize shadowbox after a partial postback is complete. This will cause html elements to rebind to shadowbox to get up and running again. The script below shows how to do this on the page you are using shadowbox or in the master page if you are using one.

<script type="text/javascript">
    Sys.WebForms.PageRequestManager.getInstance().add_endRequest(EndRequest);
    function EndRequest(sender, args) {Shadowbox.setup();}
</script>

Detect installed Antivirus from code

It is possible to use System.Management class to efficiently query the operating system about several software and hardware information. One nice feature is the ability to retrieve the currently installed antivirus product along with detailed information about its status.

Fist, you need to add reference to System.Management namespace

Now import the Management namespace at the top of the form using the Imports keyword

Imports System.Management

Next, you need to add a button to your form and a listbox(just for display) then paste the below code inside the button1_click event. You can also wrap it up in a function if you intend to use it in several places:

Dim scope As New ManagementScope("\\.\root\SecurityCenter")
Dim searcher As New ManagementObjectSearcher("SELECT * FROM antivirusproduct")
Dim arInst As New ArrayList
searcher.Scope = scope
Dim av As ManagementObjectCollection = searcher.Get()
Dim Enumerator As ManagementObjectCollection. _
ManagementObjectEnumerator = av.GetEnumerator()
While Enumerator.MoveNext
    Dim avp As ManagementObject = CType(Enumerator.Current, ManagementObject)
    arInst.Add(avp("displayName").ToString())
    arInst.Add(avp("companyName").ToString())
    arInst.Add(avp("versionNumber").ToString())
    arInst.Add(avp("productUptoDate").ToString())
    arInst.Add(avp("InstanceGUID").ToString())
End While
Me.ListBox1.Items.AddRange(arInst.ToArray)

When you click on the button, the listbox will be filled with information about your installed antivirus product.

Programmatically create “System Restore Point”

System Restore is a powerful feature used in windows operating systems to create backups of the current system state before installation of custom software and critical system changes so that in case of an error, the user will be able to go back to the point just before the system was changed.

Suppose you are developing a custom application and at a point in time your application needs to change some system settings. It would be a great idea if you can create a restore point from within your application without the need to notify the user to manually create a restore point.

To create a restore point from vb.net code, we will use the handy GetObject method to grab the system restore application and create an instance from it. Once we have a system restore variable in hand, we just need a call to CreateRestorePoint method passing in the name of the restore point. There are 2 more variables that you do not need to worry about, These are the RestorePointType and the EventType which have static values in most cases of 0 and 100 respectively. Note that the CreateRestorePoint method takes a few seconds to execute. Below is a simple implementation to create a test restore point:

Dim restPoint = GetObject("winmgmts:\\.\root\default:Systemrestore")
If restPoint IsNot Nothing Then
     If restPoint.CreateRestorePoint("test restore point", 0, 100) = 0 Then
         MsgBox("Restore Point created successfully")
    Else
         MsgBox("Could not create restore point!")
     End If
End If

Once the function finishes, navigate to your system restore point maker, you should see the name of the restore point you’ve just created from your application.

How to get non working devices using Vb.net

When it comes to hardware interaction, many .net developers feel frustrated and uncertain about the capability of doing what they have in mind. One common problem we face is to enumerate the devices installed on your computer. A harder problem is to get the devices that are not working properly or disabled!. If you are writing an application that requires the existence of a specific hardware device, it makes common sense to test whether the desired device is working and enabled.

In Windows, you can view the lis of devices from the Device Manager. Disabled devices appear with a down arrow next to the device and devices that are not working properly appear with a yellow exclamation mark icon next to it:

The solution to such problems in .Net Framework languages becomes simple if we make us of WMI Queries or Windows Management Instrumentation. Writing a WMI query to retrieve system information is as simple as wrting an SQL Query.In fact, it’s almost exactly the same syntax except the objects we are querying do differ. Take a look at the WMI query below that retrieves all installed devices on the local system:

    Select * from Win32_PnPEntity

As simple as that, the Win32_PnpEntity stores information about installed devices. So if want to filter out the results by getting only the non working devices, we simply add a Where clause just like we do if we filtering data from an sql table.

    Select * from Win32_PnPEntity WHERE ConfigManagerErrorCode  0

The ConfigManagerErrorCode property stores the state of the device, a value of 0 means Working and any other different value means the device is not working or disabled.

Lets create a Device class to convert each retrieved device to an object that we can deal with in our application. After all, we would want to list out all non working devices and bind the list to some bindable data object such as a DataGrid or a ListView.

Below is our base Device class having all the properties we need to show:

Public Class Device

    Private mName As String
    Private mManufacturer As String
    Private mDescription As String
    Private mService As String
    Private mDeviceID As String
    Private mPNPDeviceID As String
    Private mClassGUID As String

    Public Property Name() As String
        Get
            Return mName
        End Get
        Set(ByVal value As String)
            mName = value
        End Set
    End Property

    Public Property Manufacturer() As String
        Get
            Return mManufacturer
        End Get
        Set(ByVal value As String)
            mManufacturer = value
        End Set
    End Property

    Public Property Description() As String
        Get
            Return mDescription
        End Get
        Set(ByVal value As String)
            mDescription = value
        End Set
    End Property

    Public Property Service() As String
        Get
            Return mService
        End Get
        Set(ByVal value As String)
            mService = value
        End Set
    End Property

    Public Property DeviceID() As String
        Get
            Return mDeviceID
        End Get
        Set(ByVal value As String)
            mDeviceID = value
        End Set
    End Property

    Public Property PNPDeviceID() As String
        Get
            Return mPNPDeviceID
        End Get
        Set(ByVal value As String)
            mPNPDeviceID = value
        End Set
    End Property

    Public Property ClassGUID() As String
        Get
            Return mClassGUID
        End Get
        Set(ByVal value As String)
            mClassGUID = value
        End Set
    End Property
End Class

We are ready now to implement our two main function, GetAllDevices and GetNonWorkingDevices and add them to the Device class. Both methods will be Shared methods because they are generic and produce the same result across all instances of the Device class. Below is the impelemtation of both methods, note the use of the GetObject method which retrieves an instance of WMI on the local computer system:

Public Shared Function GetAllDevices() As List(Of Device)
    Dim pc As String = "." 'local
    Dim wmi As Object = GetObject("winmgmts:\\" & pc & "\root\cimv2")
    Dim allDevices As New List(Of Device)
    Dim devices As Object = wmi.ExecQuery("Select * from Win32_PnPEntity")
    Dim device As Device
    For Each d As Object In devices
        device = New Device
        With Device
        .mClassGUID = IIf(IsDBNull(d.ClassGuid), 0, d.ClassGuid)
        .mDescription = IIf(IsDBNull(d.Description), 0, d.Description)
        .DeviceID = IIf(IsDBNull(d.DeviceID), 0, d.DeviceID)
        .Manufacturer = IIf(IsDBNull(d.Manufacturer), 0, d.Manufacturer)
        .Name = IIf(IsDBNull(d.Name), 0, d.Name)
        .PNPDeviceID = IIf(IsDBNull(d.PNPDeviceID), 0, d.PNPDeviceID)
        .Service = IIf(IsDBNull(d.Service), 0, d.Service)
        End With
        allDevices.Add(device)
    Next
    Return allDevices
End Function

Public Shared Function GetNonWorkingDevices() As List(Of Device)
    Dim pc As String = "." 'local
    Dim wmi As Object = GetObject("winmgmts:\\" & pc & "\root\cimv2")
    Dim notWorking As New List(Of Device)
    Dim devices As Object = wmi.ExecQuery("Select * from " & _
          "Win32_PnPEntity WHERE ConfigManagerErrorCode  0")
    Dim device As Device
    For Each d As Object In devices
        device = New Device
        With Device
        .mClassGUID = IIf(IsDBNull(d.ClassGuid), 0, d.ClassGuid)
        .mDescription = IIf(IsDBNull(d.Description), 0, d.Description)
        .DeviceID = IIf(IsDBNull(d.DeviceID), 0, d.DeviceID)
        .Manufacturer = IIf(IsDBNull(d.Manufacturer), 0, d.Manufacturer)
        .Name = IIf(IsDBNull(d.Name), 0, d.Name)
        .PNPDeviceID = IIf(IsDBNull(d.PNPDeviceID), 0, d.PNPDeviceID)
        .Service = IIf(IsDBNull(d.Service), 0, d.Service)
        End With
        notWorking.Add(device)
    Next
    Return notWorking
End Function

Our Device class is now ready, we can simply now bind the results of each method to a DataGrid as i have done in the figure below:

Here is the code that produces the above results after adding a DatagridView to a form:

Private Sub Form1_Load(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles MyBase.Load
    DataGridView1.DataSource = Device.GetNonWorkingDevices
End Sub

The project with its source code can be downloaded here(remove the .jpg extension).