jluebbert (owner)

Revisions

gist: 214701 Download_button fork
public
Public Clone URL: git://gist.github.com/214701.git
Embed All Files: show embed
C++ #
raw 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

#include <iostream>
#include <string>
#include <sstream>
using namespace std;
 
#define DAYS_IN_YEAR 360	// In order to simplify the program
#define DAYS 30				// use 30 days in each month.
#define MONTHS 12			// This still gives a rough estimate on how
// well the hashing functions work.
 
int hash1(int month, int day);
int hash2(int month, int day);
string formatDate(int month, int day);
 
int main()
{
    // for hash1
    string year1[DAYS_IN_YEAR];
    // for hash2
    string year2[DAYS_IN_YEAR];
    int numOfDays = 0;
    int collisions1 = DAYS_IN_YEAR;
    int collisions2 = DAYS_IN_YEAR;
 
    // clear both arrays
    for ( int i = 0; i < DAYS_IN_YEAR; i++ )
        year1[i] = year2[i] = "";
 
    for ( int i = 1; i <= MONTHS; i++ ) {
        for ( int j = 1; j <= DAYS; j++ ) {
            year1[ hash1(i, j) ] = formatDate(i, j);
            year2[ hash2(i, j) ] = formatDate(i, j);
        }
    }
 
    // total collisions for hash1
    for ( int i = 0; i < DAYS_IN_YEAR; i++ ) {
        if ( year1[i] != "" )
            numOfDays += 1;
    }
    collisions1 -= numOfDays;
 
    numOfDays = 0;
 
    // total collisions for hash2
    for ( int i = 0; i < DAYS_IN_YEAR; i++ ) {
        if ( year2[i] != "" )
            numOfDays += 1;
    }
    collisions2 -= numOfDays;
 
    //for ( int i = 0; i < DAYS_IN_YEAR; i++ ) {
    //	cout << "index: " << i << '\t' << year1[i] << endl;
 
    cout << "hash1" << '\t' << "hash2" << endl
        << "-------" << '\t' << "-------" << endl
        << collisions1 << '\t' << collisions2 << endl;
 
    return 0;
}
 
int hash1(int month, int day)
{
    return ( ( month + (3 * day) ) % 101 );
}
 
int hash2(int month, int day)
{
    return ( ( day + ( 3 * month ) ) % 101 );
}
 
string formatDate(int month, int day)
{
    stringstream ss;
    ss << month << "/" << day;
    return ( ss.str() );
}
 
Text only #
raw 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

#include <iostream>
#include <string>
using namespace std;
 
int hash( string value );
 
int main()
{
    string words[10];
    string w[] = { "AN", "AS", "AT", "BE", "DO", "GO", "HE",
        "IF", "IS", "IT", "ME", "NO", "ON", "SO", "TO", "WE" };
 
    string w2[] = { "AN", "AS", "AT", "BE", "DO", "GO", "HE",
        "IF", "IS", "IT", "ME", "NO", "ON", "SO", "TO", "WE",
        "AD", "AM", "AX", "BY", "HI", "ID", "IN", "MA", "MY",
        "OF", "OR", "OX", "PA", "PI", "UP", "US" };
 
    int words2count[10];
    for ( int i = 0; i < 10; i++ )
        words2count[i] = 0;
 
    string states[10];
    int statecount[10];
    for ( int i = 0; i < 10; i++ )
        statecount[i] = 0;
    string s[] = { "AL", "AK", "AZ",
        "AR", "CA", "CO", "CT", "DE", "FL", "GA",
        "HI", "ID", "IL", "IN", "IA", "KS", "KY",
        "LA", "ME", "MD", "MA", "MI", "MN", "MS",
        "MO", "MT", "NE", "NV", "NH", "NJ", "NM",
        "NY", "NC", "ND", "OH", "OK", "OR", "PA",
        "RI", "SC", "SD", "TN", "TX", "UT", "VT",
        "VA", "WA", "WV", "WI", "WY" };
 
    // 3a.
    //for ( int i = 0; i < 10; i++ )
        //words[ hash( w[i] ) ] = w[i];
 
    //for ( int i = 0; i < 10; i++ )
        //cout << words[i] << endl;
 
    // 3b.
    //for ( int i = 0; i < 32; i++ ) {
        //int index = hash( w2[i] );
        //if ( index < 10 ) {
            //int tmp = words2count[ index ];
            //words2count[ index ] = tmp + 1;
        //}
    //}
 
    //for ( int i = 0; i < 10; i++ )
        //cout << words2count[i] << endl;
        //
 
    for ( int i = 0; i < 50; i++ )
    {
        states[ hash( s[i] ) ] = s[i];
        statecount[ hash( s[i] ) ] += 1;
    }
 
    for ( int i = 0; i < 10; i++ )
        cout << states[i] << endl;
 
    for ( int i = 0; i < 10; i++ )
        cout << statecount[i] << endl;
 
}
 
int hash( string value )
{
    int first = int(value[0]) - 64;
    int second = int(value[1]) - 64;
 
    return ( 2 * ( first ) + 7 * ( second ) ) % 11;
}