Posts Tagged ‘algorithm

19
May
09

[C++] Numbers with 6 divisors where none of the divisors are primes > 5

My uncle phoned me up to day with a question:

N is a number that has exactly 6 factors.
One of the factors is 1, and another is the number itself.
None of the prime factors of N can be greater than 5
Find a method for calculating a set of vales that would suit N.

Well. To be honest, after literally hours of trying to work out how to do this, I gave up and decided to program a brute force algorithm that would do this for me:

#include "stdafx.h"
#include "math.h"

int main()
{
	//Algorithm to calculate numbers where
	//Number of divisors < 7
	//None of the prime divisors > 5
	for(int i=1;i<100;i++) {
		int dc = 0; //divisor count
		bool pc = true; //prime check
		for(int k=1;k<(i/2)+1;k++) { //loop through all the numbers up to (n/2)+1
			if(i%k==0) { //check to see if divides with no remainder
				dc++; //increase divisor count
				if(dc > 5) { //if divisor count greater than 5, then quit - this number is not valid
					dc++;
					break;
				} else { //else we need to check the divisor
					if(k>5) {//if the divisor is bigger than 5, we need to check if it is prime
						bool ip = true; //is prime?
						for(int j = 2; j <= sqrt((double)k); j++)  //loop through the possible values
							if(k % j == 0) //check remainder
								ip=false;
						if(ip==true) { //sorry, its too big to be prime. quit
							pc=false;
							break;
						}
					}
				}
			}
		}
		if(dc==5 && pc==true) //check number is prime valid and has 6 divisors
			printf("Valid Number %d, \n", i);
	}
	return 0;
}

That would produce the list of valid numbers, those being:
12 : [1, 2, 3, 4, 6, 12]
18 : [1, 2, 3, 6, 9, 18]
20 : [1, 2, 4, 5, 10, 20]
32 : [1, 2, 4, 8, 16, 32]
45 : [1, 3, 5, 9, 15, 45]
50 : [1, 2, 5, 10, 25, 50]
75 : [1, 3, 5, 15, 25, 75]

17
Apr
09

[VB.Net] Bin Packing

An algorithm for packing a bin with a set of items
Allows for packing in descending order, which in most cases are more efficient

    Public Class Packing_Bin
        Public Number As Integer
        Public Size As Integer
        Public BinSpace As Integer
        Public Items As List(Of Integer)
    End Class

    Private Sub BinPack(ByVal Items As List(Of Integer), ByVal BinSize As Integer, Optional ByVal DecendingBinPack As Boolean = True)
        'Items:
        ''List of items to pack into the bins
        'BinSize:
        ''Declare the maximum size of the bins
        ''This is not necessary, you can just state the BinSize when you create a new bin
        'DecendingBinPack:
        ''Sorts the items into decending size order 

        If DecendingBinPack = True Then
            Items.Sort()
            Items.Reverse()
        End If

        ''Determine minimum number of bins required
        ''Again, not necessary, just used to check efficency of algorithm
        Dim MinimumBins As Integer
        For Each item As Integer In Items
            MinimumBins += item
        Next
        MinimumBins = Math.Ceiling(MinimumBins / BinSize)

        ''Create initial bin to be packed
        Dim Bins As New List(Of Packing_Bin)
        Dim InitialBin As New Packing_Bin
        With InitialBin
            .Number = 1
            .Size = BinSize
            .BinSpace = BinSize
            .Items = New List(Of Integer)
        End With
        Bins.Add(InitialBin)

        ''#Note - If you want to start with x bins with different properties, then create them here too
        ''Just declare a new Packing_Bin and set the properties

        ''Loop through out list of items
        For Each item As Integer In Items
            Dim Allocated As Boolean = False
            ''Loop through current bins
            For i As Integer = 0 To Bins.Count - 1
                ''If there is space in the bin, add it
                If Bins(i).BinSpace >= item Then
                    Bins(i).Items.Add(item)
                    Bins(i).BinSpace -= item
                    Allocated = True
                    Exit For
                End If
            Next
            ''If the item was not added to a bin, create a new bin an add it
            If Allocated = False Then
                Dim NewBin As New Packing_Bin
                With NewBin
                    .Number = Bins.Count + 1
                    .Size = BinSize
                    .BinSpace = BinSize - item
                    .Items = New List(Of Integer)
                    .Items.Add(item)
                End With
                ''Add the bin to our bin collection
                Bins.Add(NewBin)
            End If
        Next

        Debug.WriteLine("Minimum Number of Bins Required: " & MinimumBins)
        For Each bin As Packing_Bin In Bins
            Debug.Write("Bin #" & bin.Number & ": ")
            For i As Integer = 0 To bin.Items.Count - 2
                Debug.Write(bin.Items(i) & ", ")
            Next
            Debug.Write(bin.Items(bin.Items.Count - 1) & " - Space Remaining: " & bin.BinSpace & " of " & bin.Size & vbNewLine)
        Next
    End Sub

Usage:

        Dim BinSize As Integer = 15
        Dim Items As New List(Of Integer)
        Items.AddRange(New Integer() {12, 14, 15, 9, 8, 14, 9, 5, 9, 1, 5, 2, 6, 4, 14, 15, 1, 2, 12, 9})
        BinPack(Items, 15, True)

Would Output:
Minimum Number of Bins Required: 12
Bin #1: 15 – Space Remaining: 0 of 15
Bin #2: 15 – Space Remaining: 0 of 15
Bin #3: 14, 1 – Space Remaining: 0 of 15
Bin #4: 14, 1 – Space Remaining: 0 of 15
Bin #5: 14 – Space Remaining: 1 of 15
Bin #6: 12, 2 – Space Remaining: 1 of 15
Bin #7: 12, 2 – Space Remaining: 1 of 15
Bin #8: 9, 6 – Space Remaining: 0 of 15
Bin #9: 9, 5 – Space Remaining: 1 of 15
Bin #10: 9, 5 – Space Remaining: 1 of 15
Bin #11: 9, 4 – Space Remaining: 2 of 15
Bin #12: 8 – Space Remaining: 7 of 15

10
Apr
09

[Vb.Net] QuickSort

This uses the QuickSort algorithm to order a list of numbers:

  Private Function QuickSort(ByVal ListOfNumbers As List(Of Integer)) As List(Of Integer)
        ''If the list is 1 or 0 then it is sorted
        If ListOfNumbers.Count < 1 Then Return ListOfNumbers
        ''List of numbers smaller than the pivot, and larger than it
        Dim SmallList, LargeList As New List(Of Integer)
        ''Pivot = n/2 rounded down
        Dim Pivot As Integer = ListOfNumbers(Math.Floor((ListOfNumbers.Count) / 2))
        Dim PivotCount As Integer = 0
        QuickSort = New List(Of Integer)
        ''Add to appropriate list
        For i As Integer = 0 To ListOfNumbers.Count - 1
            If ListOfNumbers(i) < Pivot Then
                SmallList.Add(ListOfNumbers(i))
            ElseIf ListOfNumbers(i) > Pivot Then
                LargeList.Add(ListOfNumbers(i))
            Else
                PivotCount = PivotCount + 1
            End If
        Next
        ''Quicksort smaller list
        QuickSort.AddRange(QuickSort(SmallList))
        ''Add pivot
        While PivotCount > 0
            QuickSort.Add(Pivot)
            PivotCount -= 1
        End While
        ''Sort large list 
        QuickSort.AddRange(QuickSort(LargeList))
    End Function

Usage:

        Dim ArrayOfNumbers As Integer() = {21, 18, 16, 20, 11, 17, 15, 7, 3, 18, 19, 14, 11, 28, 12, 15, 7, 30, 27}
        Dim ListOfNumbers As New List(Of Integer)
        ListOfNumbers.AddRange(ArrayOfNumbers)
        For Each Number As Integer In QuickSort(ListOfNumbers)
            Debug.Write(Number & " ")
        Next
        Debug.Write(vbNewLine)

Would Output:
3 7 7 11 11 12 14 15 15 16 17 18 18 19 20 21 27 28 30

10
Apr
09

[VB.Net] Bubble Sort 2

This function displays the steps that are actually used in the algorithm, displaying each iteration and the state of the list at the end of each. This only works with numbers, however could easily be used to sort strings (just cast it to string instead of integer)

    Public Sub BubbleSortOutput(ByVal Delimiter As Char, ByVal NewDelimiter As Char, ByRef inText As String, ByRef outTextBox As TextBox)
        ''Create initial list of numbers from inText
        Dim Numbers As New List(Of Integer)
        ''Format number delimiter number delimiter number etc
        ''E.g. 1,2,3,4,5 or 1.2.3.4.5 or 1-2-3-4-5-6 etc
        ''Split the string and output to text box
        For Each str As String In inText.Split(Delimiter)
            Numbers.Add(CInt(str))
            outTextBox.Text += str & NewDelimiter
        Next
        outTextBox.Text += vbNewLine & "".PadRight(120, "-") & vbNewLine

        ''Starting the iterations
        Dim swaps As Boolean = True
        While swaps = True
            swaps = False
            Dim CurrentPass As List(Of Integer) = Numbers
            For i As Integer = 0 To Numbers.Count - 2
                ''Formatting tabs
                Dim delim As String = "".PadLeft(i, NewDelimiter)
                ''Display numbers that are being compared
                outTextBox.Text += delim & "[" & CurrentPass(i) & NewDelimiter & CurrentPass(i + 1) & "]" & vbNewLine
                ''If left is bigger than right, swap
                If CurrentPass(i) > CurrentPass(i + 1) Then
                    Dim temp As Integer = CurrentPass(i + 1)
                    CurrentPass(i + 1) = CurrentPass(i)
                    CurrentPass(i) = temp
                    swaps = True
                End If
            Next
            'Display output for pass
            outTextBox.Text += "".PadRight(120, "-") & vbNewLine
            For j As Integer = 0 To CurrentPass.Count - 2
                outTextBox.Text += CurrentPass(j) & NewDelimiter
            Next
            outTextBox.Text += CurrentPass(CurrentPass.Count - 1) & vbNewLine
            outTextBox.Text += "".PadRight(120, "-") & vbNewLine
        End While
    End Sub

Usage:

   BubbleSortOutput(","c, vbTab, TextBox1.Text, TextBox2)

Where TextBox1.Text contains: 92,28,48,37,77,34,94,46
and TextBox2 is a blank textbox.

Would output:

92	28	48	37	77	34	94	46
-----------------------------------------------------------
[92	28]
	[92	48]
		[92	37]
			[92	77]
				[92	34]
					[92	94]
						[94	46]
-----------------------------------------------------------
28	48	37	77	34	92	46	94
-----------------------------------------------------------
[28	48]
	[48	37]
		[48	77]
			[77	34]
				[77	92]
					[92	46]
						[92	94]
-----------------------------------------------------------
28	37	48	34	77	46	92	94
-----------------------------------------------------------
[28	37]
	[37	48]
		[48	34]
			[48	77]
				[77	46]
					[77	92]
						[92	94]
-----------------------------------------------------------
28	37	34	48	46	77	92	94
-----------------------------------------------------------
[28	37]
	[37	34]
		[37	48]
			[48	46]
				[48	77]
					[77	92]
						[92	94]
-----------------------------------------------------------
28	34	37	46	48	77	92	94
-----------------------------------------------------------
[28	34]
	[34	37]
		[37	46]
			[46	48]
				[48	77]
					[77	92]
						[92	94]
-----------------------------------------------------------
28	34	37	46	48	77	92	94
-----------------------------------------------------------
10
Apr
09

[VB.Net] Bubble Sort Algorithm

Two functions below, for using the Bubble sort algorithm on either Strings or Integers.
The two functions are fundamentally the same, just with different casting – and so could be combined into one function.

    Public Function BubbleSortNumber(ByVal ListofNumber As List(Of Integer)) As List(Of Integer)
        Dim swaps As Boolean = True
        While swaps = True
            swaps = False
            For i As Integer = 0 To ListofNumber.Count - 2
                If ListofNumber(i) > ListofNumber(i + 1) Then
                    Dim temp As Integer = ListofNumber(i + 1)
                    ListofNumber(i + 1) = ListofNumber(i)
                    ListofNumber(i) = temp
                    swaps = True
                End If
            Next
        End While
        Return ListofNumber
    End Function

Usage:

        ''Create List of Random Integers
        Dim randomG As New Random
        Dim ListOfInteger As New List(Of Integer)
        For i As Integer = 0 To 26
            ListOfInteger.Add(randomG.Next(0, 10))
        Next
        ''Sort and format
        Dim outpt2 As String = ""
        For Each bub As String In BubbleSortNumber(ListOfInteger)
            outpt2 += bub & " "
        Next
        Debug.WriteLine(outpt2)

Would output:
0 0 0 0 1 2 3 3 3 3 3 4 5 5 5 6 6 6 6 7 7 8 8 8 8 8 9

And for Strings

    Public Function BubbleSortString(ByVal ListofString As List(Of String)) As List(Of String)
        Dim swaps As Boolean = True
        While swaps = True
            swaps = False
            For i As Integer = 0 To ListofString.Count - 2
                If ListofString(i) > ListofString(i + 1) Then
                    Dim temp As String = ListofString(i + 1)
                    ListofString(i + 1) = ListofString(i)
                    ListofString(i) = temp
                    swaps = True
                End If
            Next
        End While
        Return ListofString
End Function

Usage:

        ''Create list of strings (in this case, characters)
        Dim ListOfString As New List(Of String)
        ListOfString.AddRange("q w e r t y u i o p a s d f g h j k l z x c v b n m".Split(" "))
        ''Sort and format
        Dim outpt1 As String = ""
        For Each bub As String In BubbleSortString(ListOfString)
            outpt1 += bub & " "
        Next
        Debug.WriteLine(outpt1)

Would output:
a b c d e f g h i j k l m n o p q r s t u v w x y z

30
Mar
09

[VB.Net] GetPixelColourCount

Decided to turn my solution to the question here into an easy to use function.
It uses the goto function, which I feel is frowned upon, but go ahead and complain ^_^

    ''' <summary >
    ''' Function to count the number of pixels of the same colour
    ''' </summary >
    ''' <param name="bmpImage" > The image as a Bitmap that you wish to count the pixels of</param >
    ''' <param name="Bounds" > The rectangle for the area that you wish to calculate</param >
    ''' <returns > A list of strings containing the pixels colour and the number of pixels of that colour</returns >
    ''' <remarks > sim0n</remarks >
    Private Function GetPixelColourCount(ByVal bmpImage As Bitmap, ByVal Bounds As RectangleF) As List(Of String())
        Dim Pixels As New List(Of String())
        For x As Integer = Bounds.Left To Bounds.Right - 1
            For y As Integer = Bounds.Top To Bounds.Bottom - 1
                Dim Found As Boolean = False
                For Each str As String() In Pixels
                    If str(0) = CStr(bmpImage.GetPixel(x, y).ToArgb) Then
                        str(1) = CStr(CInt(str(1)) + 1)
                        Found = True
                        GoTo pixelFound
                    End If
                Next
                Pixels.Add(New String() {CStr(bmpImage.GetPixel(x, y).ToArgb), 1})
pixelFound:
            Next
        Next
        Return Pixels
    End Function

Usage:
Using image: http://privatewww.essex.ac.uk/~sjs/research/iso_colour_blocks.png

        ''Get our image from PictureBox1
        Dim btmp As New Bitmap(PictureBox1.Image)
        ''Set the cursor to wait
        Me.Cursor = Cursors.WaitCursor
        ''Loop through the results - Rectangle is the entire image
        For Each str As String() In GetPixelColourCount(btmp, New RectangleF(0, 0, btmp.PhysicalDimension.Width, btmp.PhysicalDimension.Height))
            Debug.WriteLine(Color.FromArgb(str(0)).ToString & " | Count: " & str(1))
        Next
        ''Reset Cursor
        Me.Cursor = Cursors.Default

Would output:
Color [A=255, R=85, G=85, B=85] | Count: 65536
Color [A=255, R=0, G=255, B=0] | Count: 32768
Color [A=255, R=127, G=0, B=128] | Count: 32768
Color [A=255, R=0, G=0, B=255] | Count: 32768
Color [A=255, R=127, G=128, B=0] | Count: 32768
Color [A=255, R=255, G=0, B=0] | Count: 32768
Color [A=255, R=0, G=127, B=128] | Count: 32768

You can also just select regions of the image to calculate using the Bounds parameter, for example to get the colour of just one square, you could do:

  ''64 Pixels along
  ''0 Pixels down
  ''Width 64 pixels
  ''Heigh 64 Pixels
  For Each str As String() In GetPixelColourCount(btmp, New RectangleF(64, 0, 64, 64))
      Debug.WriteLine(Color.FromArgb(str(0)).ToString & " | Count: " & str(1))
  Next

Would output:
Color [A=255, R=127, G=128, B=0] | Count: 4096

30
Mar
09

[VB.Net] Q: Get the amount and colour of pixels in an Image

The question asked “How do i get the amount and colour of pixels in an Image?”

The Solution
I had to think a bit about this one, dealing with image processing needs to be as efficent as possible, however I couldnt see a better way than just looping through the pixels and adding them to a list.
Here is the solution that I posted to the users project:

    Dim PixelList As New List(Of String())

    Public Sub ColourInList(ByVal Colour As Color)
        Dim Found As Boolean = False
        For Each str As String() In PixelList
            If str(0) = CStr(Colour.ToArgb) Then
                str(1) = CStr(CInt(str(1)) + 1)
                Found = True
                Exit For
            End If
        Next
        If Found = False Then PixelList.Add(New String() {CStr(Colour.ToArgb), 1})
    End Sub

    Private Sub PictureBox1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles PictureBox1.Click
        Dim btmp As New Bitmap(PictureBox1.Image)
        For x As Integer = 0 To btmp.Width - 1
            For y As Integer = 0 To btmp.Height - 1
                ColourInList(btmp.GetPixel(x, y))
            Next
        Next
        For Each str As String() In PixelList
            Debug.WriteLine(Color.FromArgb(str(0)).ToString & " | Count: " & str(1))
        Next
    End Sub

Would Output:
Using this Image:
http://privatewww.essex.ac.uk/~sjs/research/iso_colour_blocks.png

Color [A=255, R=85, G=85, B=85] | Count: 65536
Color [A=255, R=0, G=255, B=0] | Count: 32768
Color [A=255, R=127, G=0, B=128] | Count: 32768
Color [A=255, R=0, G=0, B=255] | Count: 32768
Color [A=255, R=127, G=128, B=0] | Count: 32768
Color [A=255, R=255, G=0, B=0] | Count: 32768
Color [A=255, R=0, G=127, B=128] | Count: 32768