<commit_before><commit_msg>solution to project euler, problem 14, using dynamic programming<commit_after>#include <iostream>
#include <map>

long collatzLength( long x, std::map<long, long> &collatzMap );

int main()
{
    std::map<long, long> collatzMap;
    long longest_index = 1;
    long longest_length = 1;
    long length;

    for ( int i = 0; i < 1000000; i++ )
    {
        length = collatzLength( i, collatzMap );

        collatzMap[i] = length;
        if ( length > longest_length )
        {
            longest_length = length;
            longest_index = i;
        }
    }

    std::cout << longest_index << std::endl;

    return 0;
}

long collatzLength( long x, std::map<long, long> &collatzMap )
{
    std::map<long,long>::iterator iter;
    if ( (iter = collatzMap.find( x )) != collatzMap.end() )
    {
        return iter->second;
    }
        
    long count = 1;
    while( x > 1 )
    {
        if ( (iter = collatzMap.find( x )) != collatzMap.end() )
        {
            return (iter->second + count);
        }
        if ( x % 2 == 0 )
        {
            x = x >> 1;
        }
        else
        {
            x = 3*x + 1;
        }
        count++;
    }

    return count;
}

{'fraction_non_alphanumeric': 0.13393590797041907, 'fraction_numerical': 0.016433853738701727, 'mean_word_length': 1.7494356659142212, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1056513', 'n_tokens_mistral': 423, 'n_tokens_neox': 401, 'n_words': 101}