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

''#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).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)
End With
''Add the bin to our bin collection
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)
For i As Integer = 0 To ListOfNumbers.Count - 1
If ListOfNumbers(i) < Pivot Then
ElseIf ListOfNumbers(i) > Pivot Then
Else
PivotCount = PivotCount + 1
End If
Next
''Quicksort smaller list
While PivotCount > 0
PivotCount -= 1
End While
''Sort large list
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)
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)
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
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
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