Random Walking Assets

a blog of software engineer, dreamer and daddy

Gift1

| Comments

Problem can be found here here

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

/*
 ID: chinux1
 PROG: gift1
 LANG: C++11
 */

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>

using namespace std;

class person
{
private:
    string _name;
    long _amount, _initialAmount;

public:
    person();
    person(string name, long money);
    void give(person & receiver);
    void send(vector<string>& list);
    void setInitialAmount(const long & money);

    vector<string> giftees;

    long netAmount();
};

static map<string, person>nameLookupTable;
static vector<string> orderOfName;

person::person()
{
    _name = "no name";
    _amount = 0;
    _initialAmount = 0;
    giftees = vector<string>{};
}

person::person(string name, long money)
{
    _name = name;
    _amount = 0;
    _initialAmount = money;
    giftees = vector<string>{};
}

void person::give(person &receiver)
{
    if (giftees.size() == 0) {
        return;
    }

    receiver._amount += _initialAmount / giftees.size();
}

void person::send(vector<string> &list)
{
    if (list.size() == 0) {
        _amount = _amount + _initialAmount;
    } else {
        for (auto person : list) {
            give(nameLookupTable[person]);
        }
        _amount = _amount + _initialAmount % list.size();
    }
}

void person::setInitialAmount(const long &money)
{
    _initialAmount = money;
}

long person::netAmount()
{
    return _amount - _initialAmount;
}


int main() {
    ofstream fout ("gift1.out");
    ifstream fin ("gift1.in");

    // Line 1
    int sizeOfGroup = 0;
    fin >> sizeOfGroup;

    // Line 2..NP+1
    for (int i = 0; i < sizeOfGroup; i++) {
        string name;
        fin >> name;
        person aPerson = person(name, 0);
        nameLookupTable.insert(nameLookupTable.end() ,std::pair<string, person>{name, aPerson});
        orderOfName.insert(orderOfName.end(), name);
    }

    // Line NP+2..end
    while (!fin.eof()) {
        string name;
        fin >> name;
        int initialAmount, numOfGiftees;
        fin >> initialAmount >> numOfGiftees;
        nameLookupTable[name].setInitialAmount(initialAmount);

        for (int i = 0; i < numOfGiftees; i++) {
            string nameOfGiftee;
            fin >> nameOfGiftee;
            nameLookupTable[name].giftees.push_back(nameOfGiftee);
        }

        nameLookupTable[name].send(nameLookupTable[name].giftees);
    }

    for (string name : orderOfName) {
        fout << name << " " << nameLookupTable[name].netAmount() << endl;
    }

    return 0;
}

Friday

| Comments

Problem: here

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

/*
 ID: chinux1
 PROG: friday
 LANG: C++11
 */

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>

using namespace std;


int getFebDays(int year);
bool isLeapYear(int year);

int getDaysForMonth(int year, int month)
{
    switch (month) {
        case 2:
            return getFebDays(year);
            break;
        case 4:
        case 6:
        case 11:
        case 9:
            return 30;
            break;
        default:
            return 31;
            break;
    }

}

int getFebDays(int year)
{
    if (isLeapYear(year)) {
        return 29;
    } else {
        return 28;
    }
}

bool isLeapYear(int year)
{
    if (year % 100 == 0 && year % 400 == 0) {
        return true;
    } else if (year % 100 == 0){
        return false;
    } else if (year % 4 == 0){
        return true;
    } else {
        return false;
    }
}

static vector<int> frequency = {0, 0, 0, 0, 0, 0, 0};

int main() {
    ofstream fout ("friday.out");
    ifstream fin ("friday.in");

    // Line 1
    int N = 0;
    fin >> N;

    // Compute Date for Jan 1st 1900
    int firstDayOfTheMonth = 0;

    for (int i = 0; i < N; i++) {
        int year = 1900 + i;

        for (int j = 1; j <= 12; j++) {
            frequency[(firstDayOfTheMonth + 12) % 7]++;
            // Update to next month
            firstDayOfTheMonth = (firstDayOfTheMonth + getDaysForMonth(year, j)) % 7;

        }

    }

    for (int i = 5; i < 12; i++) { // Starting from Saturday.
        fout << frequency[i % 7];
        if (i == 11) {
            fout << endl;
        } else
            fout << " ";
    }

    return 0;
}

Beads

| Comments

Problem: here

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
79
80
81
82
83
84
85
86
87

/*
 ID: chinux1
 PROG: beads
 LANG: C++11
 */

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>

using namespace std;

int countBeadsBackward(string necklace, int index)
{
    if (index > 0) {
        char firstColor = necklace[index-1];

        int i = index - 1;
        while (i > 0 && (firstColor == necklace[i] || necklace[i] == 'w' || firstColor == 'w')) {
            // first Color may be 'w', if so, we need to update
            if (firstColor == 'w' && necklace[i] != 'w') {
                firstColor = necklace[i];
            }
            i--;
        }
        return index - 1 - i;
    } else {
        return 0;
    }
}

int countBeadsForward(string necklace, int index)
{
    if (index < necklace.size()) {
        char firstColor = necklace[index];

        int i = index;
        while (i < necklace.size() && (firstColor == necklace[i] || necklace[i] == 'w' || firstColor == 'w')) {
            // first Color may be 'w', if so, we need to update
            if (firstColor == 'w' && necklace[i] != 'w') {
                firstColor = necklace[i];
            }
            i++;
        }
        return i - index;
    } else {
        return 0;
    }
}

int countBeads(string necklace, int index)
{
    return countBeadsBackward(necklace, index) + countBeadsForward(necklace, index);
}

int maxNumberOfBeads(string doubleNecklace)
{
    int maxBeads = 0;
    for (int i = 1; i < doubleNecklace.length(); i++) {
        int num = countBeads(doubleNecklace, i);
        if (num > maxBeads){
            maxBeads = num;
        }
    }
    return maxBeads;
}

int main() {
    ofstream fout ("beads.out");
    ifstream fin ("beads.in");

    // Line 1
    int N = 0;
    fin >> N;

    // Line 2
    string necklace;
    fin >> necklace;

    string doubleNecklace = necklace + necklace;

    fout << min(maxNumberOfBeads(doubleNecklace), N) << endl;

    return 0;
}

Ride

| Comments

Started my programming training.

Problem can be found here here

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

/*
 ID: chinux1
 PROG: ride
 LANG: C++11
 */

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

unsigned long mod47(string name)
{
    unsigned long groupNumber = 1;
    for (int i = 0; i < 6 && i < name.length(); i++) {
        groupNumber = groupNumber * (name[i] - 64);
    }

    return groupNumber % 47;
}

int main() {
    ofstream fout ("ride.out");
    ifstream fin ("ride.in");
    string a, b;
    fin >> a >> b;

    if (mod47(a) == mod47(b)) {
        fout << "GO" << endl;
    } else {
        fout << "STAY" << endl;
    }

    return 0;
}

Build Clang With Stdlibc++ 4.7 in Mac OS

| Comments

Claim: I am no where close to a C++ expert, but just trying to learn things as life goes along. This post is for newbies like me trying to make clang work in C++11 mode with libstdc++.

Motivation

  • C++11 has been out for a while now and I really want to get my hands on it to try it out.
  • Clang is a great Compiler (witht best-in-class quality and a lot of features).
  • The thing that I really enjoy is the AST that you can literally travese the source code like a “tree”. There are quite a few plugings that build on top of it
  • Vim Clang-Complete - quite cool, a really compiler generated complete, alot better than the ctags.
  • Syntax Highlight - i haven’t really tried that in Vim but looks possible and definitely interesting.

However, in order to use clang with C++11, i either have to use libc++ or rebuild clang with libstdc++4.6/7. This is kinda pain for a newbie like me. Things that I have tried that didn’t work out:

  • MacPort GCC4.7 - install with sudo port install gcc47
  • This only give you the gcc toolchains, not the llvm/clang.
  • MacPort Clang 3.2 - installs clang/llvm without gcc toolchains, that means I am back to the square one.
  • The post http://clang.llvm.org/get_started.html is bit advanced for newbie (at that time, i didn’t even know what is a GCC installation directory is. If you don’t know like me, keep reading).
  • And someone has similar experience http://lists.cs.uiuc.edu/pipermail/llvmdev/2012-April/048824.html.

Unforutunately that post is for ubuntu, not Mac OS. Can’t just copy/paste! Oh yeah, forgot. –gcc-tool-chain configure flag doesn’t work for by the way. Maybe I should send the problem to cfe? * After spending sometime trial and error, finally I am able to compile a C++11 code with clang with libstdc++ 4.7. I am not sure if this way is correct though, or if there is a better way? if someone knows, please comment below.

Preparetion

  • Make sure Xcode commandline tools is installed. We need it to build gcc

Build GCC 4.7

  • Download GCC 4.7 from svn. (To keep things easy and concrete, I’ll give example path as i.e $HOME/Repo/gcc47)
1
2
3
4
5

$ mkdir $HOME/Repo/buildgcc47
$ cd $HOME/Repo/buildgcc47
$ ../gcc47/configure
$ make -j 8
$ sudo make DESTDIR=/usr/local install

You need to watch for errors. How to solve error and successfully build gcc 4.7 is beyond the scope of this post, so you’ll have to figure it out. There are currently some dependency for gcc to build, namely mpr, gmp, and mpc?? ( i don’t remember the last one ) The “make -j 8” is to build gcc with 8 jobs (I have 4 cores with hyperthread, you can choose a number instead of 8 based on your computer configuration) The last step will install your newly built gcc to /usr/local

Build Clang

  • Download clang 3.2 from svn (i.e. $HOME/Repo/llvm)
  • READ TO COMPLETE BEFORE TRYING build clang according to this guide build clang page will not give me correct libstdc++ 4.7 and header search. So read next bullet point. But you need to check out clang and compiler-rt as stated in the web.
  • So, before configure or build, modify the InitHeaderSearch.cpp in llvm/tools/clang/lib/Frontend/InitHeaderSearch.cpp. Find the FIXME and add the following around line 354:
[InitHeaderSearch.cpp] [++] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

    case llvm::Triple::x86:
    case llvm::Triple::x86_64:
      AddGnuCPlusPlusIncludePaths("/usr/local/bin/../lib/gcc/x86_64-apple-darwin12.0.0/4.7.1/../../../../include/c++/4.7.1", "", "", "", triple);
      AddGnuCPlusPlusIncludePaths("/usr/local/bin/../lib/gcc/x86_64-apple-darwin12.0.0/4.7.1/../../../../include/c++/4.7.1/x86_64-apple-darwin12.0.0", "", "", "", triple);
      AddGnuCPlusPlusIncludePaths("/usr/local/bin/../lib/gcc/x86_64-apple-darwin12.0.0/4.7.1/../../../../include/c++/4.7.1/backward", "", "", "", triple);
      AddGnuCPlusPlusIncludePaths("/usr/local/bin/../lib/gcc/x86_64-apple-darwin12.0.0/4.7.1/include", "", "", "", triple);
      AddGnuCPlusPlusIncludePaths("/usr/local/bin/../lib/gcc/x86_64-apple-darwin12.0.0/4.7.1/include-fixed", "", "", "", triple);
      AddGnuCPlusPlusIncludePaths("/usr/local/include", "", "","", triple);
      AddGnuCPlusPlusIncludePaths("/usr/include", "", "", "", triple);
      AddGnuCPlusPlusIncludePaths("/System/Library/Frameworks", "","","",triple);
      AddGnuCPlusPlusIncludePaths("/Library/Frameworks", "", "", "", triple);

      /*
      AddGnuCPlusPlusIncludePaths("/usr/include/c++/4.7.1",
                                  "i686-apple-darwin12", "", "x86_64", triple);
      AddGnuCPlusPlusIncludePaths("/usr/include/c++/4.7.1",
                                  "i686-apple-darwin12", "", "", triple);
      */
      break;
  • now configure and build your clang
  • I installed it to /usr/local again (optional)

Set the Linked library in bash environment

  • after the compilation, if you use the newly clang
[My Clang Include Path] []
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

clang version 3.2 (trunk 161295)
Target: x86_64-apple-darwin12.0.0
Thread model: posix
 "/usr/local/bin/clang" -cc1 -triple x86_64-apple-macosx10.8.0 -fsyntax-only -disable-free -main-file-name null -pic-level 2 -mdisable-fp-elim -masm-verbose -munwind-tables -target-cpu core2 -target-linker-version 134.7 -v -resource-dir /usr/local/bin/../lib/clang/3.2 -fmodule-cache-path /var/folders/1l/m5km38_d3lxbrvysgv6s42680000gn/T/clang-module-cache -fdeprecated-macro -fdebug-compilation-dir /Users/chen/Repository/llvm -ferror-limit 19 -fmessage-length 122 -stack-protector 1 -mstackrealign -fblocks -fobjc-runtime=macosx-10.8.0 -fobjc-dispatch-method=mixed -fobjc-default-synthesize-properties -fcxx-exceptions -fexceptions -fdiagnostics-show-option -fcolor-diagnostics -x c++ /dev/null
clang -cc1 version 3.2 based upon LLVM 3.2svn default target x86_64-apple-darwin12.0.0
ignoring nonexistent directory "/usr/local/bin/../lib/gcc/x86_64-apple-darwin12.0.0/4.7.1/../../../../include/c++/4.7.1/x86_64-apple-darwin12.0.0/backward"
ignoring nonexistent directory "/usr/local/bin/../lib/gcc/x86_64-apple-darwin12.0.0/4.7.1/../../../../include/c++/4.7.1/backward/backward"
ignoring nonexistent directory "/usr/local/bin/../lib/gcc/x86_64-apple-darwin12.0.0/4.7.1/include/backward"
ignoring nonexistent directory "/usr/local/bin/../lib/gcc/x86_64-apple-darwin12.0.0/4.7.1/include-fixed/backward"
ignoring nonexistent directory "/usr/local/include/backward"
ignoring nonexistent directory "/usr/include/backward"
ignoring nonexistent directory "/System/Library/Frameworks/backward"
ignoring nonexistent directory "/Library/Frameworks/backward"
ignoring duplicate directory "/usr/local/bin/../lib/gcc/x86_64-apple-darwin12.0.0/4.7.1/../../../../include/c++/4.7.1"
ignoring duplicate directory "/usr/local/bin/../lib/gcc/x86_64-apple-darwin12.0.0/4.7.1/../../../../include/c++/4.7.1/x86_64-apple-darwin12.0.0"
ignoring duplicate directory "/usr/local/bin/../lib/gcc/x86_64-apple-darwin12.0.0/4.7.1/../../../../include/c++/4.7.1/backward"
ignoring duplicate directory "/usr/local/bin/../lib/gcc/x86_64-apple-darwin12.0.0/4.7.1/../../../../include/c++/4.7.1/backward"
ignoring duplicate directory "/usr/local/bin/../lib/gcc/x86_64-apple-darwin12.0.0/4.7.1/include"
ignoring duplicate directory "/usr/local/bin/../lib/gcc/x86_64-apple-darwin12.0.0/4.7.1/include-fixed"
ignoring duplicate directory "/usr/local/include"
ignoring duplicate directory "/usr/include"
ignoring duplicate directory "/System/Library/Frameworks"
ignoring duplicate directory "/Library/Frameworks"
ignoring duplicate directory "/usr/local/include"
ignoring duplicate directory "/usr/include"
#include "..." search starts here:
#include <...> search starts here:
 /usr/local/bin/../lib/gcc/x86_64-apple-darwin12.0.0/4.7.1/../../../../include/c++/4.7.1
 /usr/local/bin/../lib/gcc/x86_64-apple-darwin12.0.0/4.7.1/../../../../include/c++/4.7.1/backward
 /usr/local/bin/../lib/gcc/x86_64-apple-darwin12.0.0/4.7.1/../../../../include/c++/4.7.1/x86_64-apple-darwin12.0.0
 /usr/local/bin/../lib/gcc/x86_64-apple-darwin12.0.0/4.7.1/include
 /usr/local/bin/../lib/gcc/x86_64-apple-darwin12.0.0/4.7.1/include-fixed
 /usr/local/include
 /usr/include
 /System/Library/Frameworks
 /Library/Frameworks
 /usr/local/bin/../lib/clang/3.2/include
 /System/Library/Frameworks (framework directory)
 /Library/Frameworks (framework directory)
End of search list.
  • if your header search path is different, go back and check to see where you did wrong
  • Now, if you try to compile, the linker will still linked to libstdc++ 4.2 that comes with Mac OS. To overcome that, i modify the bash_profile
1
2

export PATH=/usr/local/bin:/usr/local/sbin:$PATH
export LIBRARY_PATH=/usr/local/lib:/usr/local/bin/../lib/gcc/x86_64-apple-darwin12.0.0/4.7.1:/usr/local/bin/../lib/gcc:/usr/local/bin/../lib/gcc/x86_64-apple-darwin12.0.0/4.7.1/../../../:/lib:/usr/lib
  • Now, quite your terminal and restart. It should use the newly compiled clang with gcc 4.7 libstdc++

    End Words

  • Now you can try in your main.cpp. It should just compile
1
2

#include <memory>
#include <tuple>
  • One last thing, I mean, I shouldn’t have to do all these just to get clang compiled with libstdc++. It allows me to set –gcc-tool-chain. That option supposed to work. Maybe it’s already working, i just need to modify the bash environment variables. I don’t know, i didn’t give it a try. If someone did try, or has a better way to do this, please post comments below