UVA 100: The 3n+1 Problem

First Submit: Time Limit Exceeded!

Reason:  I was thinking about building up the whole table from 1 to max(startInt, endInt) in advance. However, this process take too much time, and most of the entries in the table cannot be used during the computation.

Second Submit: Wrong Answer!

Reason:  I forgot to set the result variable back to 0 at the end of each running instance.

Third Submit: Accept!

Source code:

#include <iostream>
using namespace std;

const int size = 1000001;

int table[size] = {0};

int calcCycleLength(int n) {
    if (n < size && table[n])
        return table[n];

    if (n & 1) { // n is odd.
        if (n < size) {
            table[n] = 2 + calcCycleLength( (3 * n + 1) >> 1 );
            return table[n];
        } else {
            return 2 + calcCycleLength( (3 * n + 1) >> 1 );
        }
    } else { // n is even.
        if (n < size) {
            table[n] = 1 + calcCycleLength( n >> 1 );
            return table[n];
        } else {
            return 1 + calcCycleLength( n >> 1 );
        }
    }
}

int main() {
    int startInt, endInt;
    int result = 0, temp;

    table[1] = 1;

    cin >> startInt >> endInt;
    while (!cin.eof()) {

        if (startInt > endInt) {
            int i;

            for (i = endInt; i <= startInt; ++i) {
                temp = calcCycleLength(i);
                if (temp > result)
                    result = temp;
            }

        } else {
            int i;
            for (i = startInt; i <= endInt; ++i) {
                temp = calcCycleLength(i);
                if (temp > result)
                    result = temp;
            }
        }

        cout << startInt << " " << endInt << " " << result << endl;

        result = 0;

        cin >> startInt >> endInt;
    }

    return 0;
}

Report for LLVM Project

I get the SVN version of LLVM.

There are two kinds of LLVM: LLVM source code, and LLVM GCC front end. What I'm trying is LLVM source code.

In Ubuntu, it has some bug if associated with dragonegg module:

https://bugs.launchpad.net/ubuntu/+source/dragonegg/+bug/787800

The above is the bug report, and the solution is in #3.

Bug happened when I used llvm to compile toy.cpp:


----------------------------------------------------------------------------------------------
toy.cpp: In member function ‘virtual llvm::Value* CallExprAST::Codegen()’:
toy.cpp:401:75: error: no matching function for call to ‘llvm::IRBuilder<>::CreateCall(llvm::Function*&, std::vector<llvm::Value*, std::allocator<llvm::Value*> >::iterator, std::vector<llvm::Value*, std::allocator<llvm::Value*> >::iterator, const char [8])’
/usr/local/include/llvm/Support/IRBuilder.h:1119:13: note: candidates are: llvm::CallInst* llvm::IRBuilder<preserveNames, T, Inserter>::CreateCall(llvm::Value*, const llvm::Twine&) [with bool preserveNames = true, T = llvm::ConstantFolder, Inserter = llvm::IRBuilderDefaultInserter<true>]
/usr/local/include/llvm/Support/IRBuilder.h:1122:13: note:                 llvm::CallInst* llvm::IRBuilder<preserveNames, T, Inserter>::CreateCall(llvm::Value*, llvm::Value*, const llvm::Twine&) [with bool preserveNames = true, T = llvm::ConstantFolder, Inserter = llvm::IRBuilderDefaultInserter<true>]
/usr/local/include/llvm/Support/IRBuilder.h:1146:13: note:                 llvm::CallInst* llvm::IRBuilder<preserveNames, T, Inserter>::CreateCall(llvm::Value*, llvm::ArrayRef<llvm::Value*>, const llvm::Twine&) [with bool preserveNames = true, T = llvm::ConstantFolder, Inserter = llvm::IRBuilderDefaultInserter<true>]
toy.cpp: In member function ‘llvm::Function* PrototypeAST::Codegen()’:
toy.cpp:409:54: error: no matching function for call to ‘llvm::FunctionType::get(llvm::Type*, std::vector<const llvm::Type*>&, bool)’
/usr/local/include/llvm/DerivedTypes.h:105:24: note: candidates are: static llvm::FunctionType* llvm::FunctionType::get(llvm::Type*, llvm::ArrayRef<llvm::Type*>, bool)
/usr/local/include/llvm/DerivedTypes.h:110:24: note:                 static llvm::FunctionType* llvm::FunctionType::get(llvm::Type*, bool)
--------------------------------------------------------------------------------------------------

Alternatives for Scripts Parsing

Doxygen

ANTLR

Boost::Spirit

PCRECpp

Log for June 7th, 2011

In code.l, the path of parsing the class body is:

<Body>"class"  =>   <ClassName>   => <ClassVar>  =>  <Body>

And the function definition or declaration is dealt with in <Body>.


Timestamp: 16:14
--------------------------------------------------------

Log for June 6th, 2011

Today, I applied for New Mexico Non-Driver ID, and went to Motor Vehicle Division with Jim. The materials I brought were Passport, SSN card, latest Bank Statement, and Apartment Rental Agreement. The process was very successful and no exception happened.

Then about the book The History of Western Philosophy, I finished reading Plato's theory of ideas. This is the main part of Plato's book Republic, and here he tried to define the concept "philosophy", "knowledge", "reason", and "understand". Philosophy means the love of wisdom. In Plato's thought, wisdom is different from the things we can perceive. In the sense of metaphysic, say, there are many particular cats, and we call them all "cat". However, there should exist one perfect cat, which was created by God, to designate all attributes of a cat. Then what we can see in reality are all imperfect cats. Similarly, the beautiful things are quite vary, but the beauty behind them remains the same. A person who likes different beautiful music, books, flowers, etc. is just the one who love for beautiful things, but doesn't realize the beauty itself. In Plato's theory, all facts and knowledge are eternal, infallible, and immutable. And most of us humans, in a parable, are prisoners in the dark crime. We face the wall, and there is a fire behind us. What we are able to see are just shadows which has been made by the fire. But the philosophers are the group of persons who can break through the prison and are able to see the real things through the sunshine. And the guardians from this group are the persons who are brave to return to the prison, and make the rest people realize their situation and be accompany with them to break the prison and see the facts instead of the illusions.

For Meta-Math project, now I come across two bugs. One is for the following situation:

class SomeClass {
       private:
               int x;
       public:
              int getX(void);
};

int SomeClass::getX(void) {
         return x;
}

Doxygen cannot parse "int getX(void);" correctly. Actually, the bug is that when it deals with this case, then the current member object is NULL. But if working well, it should be the function's name "getX" or "SomeClass::getX".

The other bug is that Doxygen is not able to add the related MetaReference record for the member function invocations like:

a::c();
a.c();
a->c();
(*a)->c();
(*a).c();

This is what I should fix after the first bug.

Next, I shall test whether Doxygen works well for the nested class definiton case. Like,

Class Class1 {
         Class Class2 {
                   ...
         };
         ...
};

Mission for April 14th

1. 詩經·檜風·匪風
2. Implemented Set, P_queue, Stack ADTs in C++

Meta-Math For Today:

1.  A way to defining customized command:

In the ``ALIASES" section of the configure file, create the command by ``name=value" format.

E.g.: If we want to create a command "@Unit" such that "@Unit{Meter}" can refer to "<unit>Meter</unit>" in the resulting XML file, we can define our customized command as follows:

ALIASES     +=     Unit{1}=<unit>\1</unit>

2. The "@param" and "@retval" commands in Doxygen can specify the name of the target variables.

Summary for April 13th

Achievement:

1. Implemented the moving rules for 8 puzzle problem in C++.
2. Solve one problem in HW3 CS 500.
3. Learn 詩經·檜風之素冠，隰有萇楚.
4. Practice Taiji and Kendo.

Improvement:

I should have finished C++ implementation for 8 puzzle and sliding tile problems. Besides, I should have spent hours on Meta-Math project. For most of this semester, I didn't pay enough attention on it, so there's no concrete progress on this project, which makes me upset and ashamed. Though Prof. Kniss said nothing about it, I still have to work more diligently on it.

It's near the final of the semester, and there are many works should be finished by then. I should work harder so as to finish them perfectly.

顽张ってね！