“Square Digit Chains”

19Oct18

The following is my solution to the “Square Digit Chains” problem posed by Programming Praxis; I’d usually post my solution as a comment on that ‘site, but I learned after I posted as a comment on that ‘site my solution to the “Emirps” problem posed by that ‘site that that ‘site doesn’t support images in comments.

Lacking a “recent-vintage personal computer” – my solutions to the problems posed by the aforementioned ‘site are programmed- and run- on an Apple Power Mac G4 (AGP Graphics) (450MHz processor, 1GB memory) – and wanting to test my understanding of: compiling a project using a Metrowerks CodeWarrior IDE 2.1 (Discover Programming Edition) project with multiple targets; compiling a project using the command line; and compiling a project using a makefile with multiple targets; understanding that might be necessary if I’m to release an executable of my SDL2 joystick interrogator utility, or of my entry for Ludum Dare 5, for the Raspberry Pi, I interpreted the instruction that I should abide by “the usual Project Euler rule that your computation may take no more than a minute of computation on a recent-vintage personal computer” as an invitation to compare two methods for arriving at the result:

  1. a “brute force” method: if n is a starting number in the range \left[ 1,9999999 \right], the number chains beginning with n are formed, so determining the number of chains beginning with n that will eventually arrive at 89;
  2. and what I thought would be a more-optimised method: if n is a starting number in the range \left[ 1,9999999 \right] then the minimum sum of the squares of the digits of n is 1\cdot 1^{2}=1 and the maximum sum of the squares of the digits of n is 7\cdot 9^{2}=567; therefore, a binary tree is populated with pairs of the starting numbers in the range \left[ 1,567 \right] and the numbers that those starting numbers will eventually arrive at, and – rather than forming the number chains beginning with n as in the “brute force” method – that binary tree is used to look up the numbers that the sum of the squares of the digits of n will eventually arrive at, so determining the number of chains beginning with n that will eventually arrive at 89.

The results were surprising: not only was the first, “brute force”, method faster than the second, more-optimised, method (when running on both Mac OS 9.2.2 (International English), the program compiled using Metrowerks CodeWarrior IDE 2.1 (Discover Programming Edition), and Mac OS X 10.4.11, the program compiled using the command line: make method_1 and make method_2), but the first method arrived at the result in less than a minute (when running on Mac OS X 10.4.11) in spite of running on my aforementioned far from “recent-vintage personal computer”.

(I’m just trying to solve the problems posed by the aforementioned ‘site whilst I try to get a job; I’m well-aware that my solutions are far from the best – but, in my defence, I don’t have any traditional qualifications in computer science :/ )

Output:

It is stated that a number chain is formed by continuously summing together the squares of the digits of a number to form a new number, terminating when the "new" number so formed has already been encountered earlier in the chain.

Eg.
	44 -> 32 -> 13 -> 10 -> 1 -> 1
Or eg.
	85 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89

Furthermore, it is stated that any starting number will eventually arrive at either 1 or 89.

Fri Oct 19 09:00:00 2018

8581146 starting numbers in the range [ 1, 9999999 ] will eventually arrive at 89.

Fri Oct 19 09:00:18 2018

October 19th, 2018.cpp:

#include "printDateAndTime.h" /* <http://Gist.GitHub.com/sealfin/6d35f3a3958bd6797a0f> */
#include <stdio.h>
#include <stdlib.h>

unsigned int g_limit = 9999999;

unsigned int f_SumOfSquaresOfDigits( unsigned int p )
{
  unsigned int sum_of_squares_of_digits = 0;

  while( p > 0 )
  {
    const unsigned int digit = p % 10;

    p /= 10;
    sum_of_squares_of_digits += ( digit * digit );
  }
  return sum_of_squares_of_digits;
}

unsigned int g_numberOfStartingNumbersThatArriveAt89 = 0;

void p_DetermineNumberOfStartingNumbersThatArriveAt89( void );

int main( const int argc, const char * const argv[] )
{
  #ifndef __MWERKS__
  printf( "\n" );
  #endif

  printf( "It is stated that a number chain is formed by continuously summing together the squares of the digits of a number to form a new number, terminating when the \"new\" number so formed has already been encountered earlier in the chain.\n\n" );
  printf( "Eg.\n" );
  printf( "\t44 -> 32 -> 13 -> 10 -> 1 -> 1\n" );
  printf( "Or eg.\n" );
  printf( "\t85 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89\n\n" );
  printf( "Furthermore, it is stated that any starting number will eventually arrive at either 1 or 89.\n\n" );

  p_PrintDateAndTime();
  p_DetermineNumberOfStartingNumbersThatArriveAt89();
  printf( "\n" );
  if( g_numberOfStartingNumbersThatArriveAt89 == 0 )
    printf( "No" );
  else
    printf( "%u", g_numberOfStartingNumbersThatArriveAt89 );
  printf( " starting number%s in the range [ 1, %u ] will eventually arrive at 89.\n\n", ( g_numberOfStartingNumbersThatArriveAt89 != 1 )?"s":"", g_limit );
  p_PrintDateAndTime();

  #ifndef __MWERKS__
  printf( "\n" );
  #endif

  exit( EXIT_SUCCESS );
}

method #1.cpp:

extern unsigned int g_limit;

unsigned int f_SumOfSquaresOfDigits( unsigned int p );

extern unsigned int g_numberOfStartingNumbersThatArriveAt89;

void p_DetermineNumberOfStartingNumbersThatArriveAt89( void )
{
  unsigned int i = 1;

  for( ; i <= g_limit; i ++ )
  {
    unsigned int k = i;

    while(( k != 1 ) && ( k != 89 ))
      k = f_SumOfSquaresOfDigits( k );
    if( k == 89 )
      g_numberOfStartingNumbersThatArriveAt89 ++;
  }
}

method #2.cpp:

#include "seal_tree.h" /* <http://GitHub.com/sealfin/C-and-C-Plus-Plus/blob/master/seal_tree.h> */

static size_t f_NumberOfDigits( unsigned int p )
{
  if( p == 0 )
    return 1;

  size_t number_of_digits = 0;

  do
  {
    number_of_digits ++;
    p /= 10;
  }
  while( p > 0 );
  return number_of_digits;
}

extern unsigned int g_limit;

typedef struct t_NumberArrivesAt_TreeNode_struct
{
  unsigned int m_number;
  bool m_arrivesAtSet;
  unsigned int m_arrivesAt;
}
t_NumberArrivesAt_TreeNode;

class NumberArrivesAt_Tree : public seal_Tree<t_NumberArrivesAt_TreeNode, unsigned int>
{
  public:
    NumberArrivesAt_Tree( void )
    {
      p_SetNumber( 1 );
      p_SetArrivesAt( 1 );
      p_SetNumber( 89 );
      p_SetArrivesAt( 89 );
    }

    void p_SetNumber( unsigned int p )
    {
      t_NumberArrivesAt_TreeNode n;

      n.m_number = p;
      n.m_arrivesAtSet = false;
      seal_Tree<t_NumberArrivesAt_TreeNode, unsigned int>::p_Set( n );
    }

    void p_SetArrivesAt( unsigned int p )
    {
      p_SetArrivesAt( m_root, p );
    }

  private:
    void p_SetArrivesAt( struct t_seal_TreeNode<t_NumberArrivesAt_TreeNode> * const p_n, const unsigned int p_arrivesAt )
    {
      if( p_n != NULL )
      {
        p_SetArrivesAt( p_n->m_l, p_arrivesAt );
        if( !p_n->m_content.m_arrivesAtSet )
        {
          p_n->m_content.m_arrivesAtSet = true;
          p_n->m_content.m_arrivesAt = p_arrivesAt;
        }
        p_SetArrivesAt( p_n->m_r, p_arrivesAt );
      }
    }

  public:
    unsigned int f_GetArrivesAt( unsigned int p )
    {
      return f_Get( p ).m_arrivesAt;
    }

  private:
    t_seal_TREE_BRANCH_DIRECTION f_Compare_TT( t_NumberArrivesAt_TreeNode p_old, t_NumberArrivesAt_TreeNode p_new )
    {
      if( p_new.m_number < p_old.m_number )
        return k_seal_TREE_BRANCH_DIRECTION__LEFT;
      if( p_new.m_number == p_old.m_number )
        return k_seal_TREE_BRANCH_DIRECTION__STRAIGHT;
      return k_seal_TREE_BRANCH_DIRECTION__RIGHT;
    }

    t_seal_TREE_BRANCH_DIRECTION f_Compare_TU( t_NumberArrivesAt_TreeNode p_content, unsigned int p_identifier )
    {
      if( p_identifier < p_content.m_number )
        return k_seal_TREE_BRANCH_DIRECTION__LEFT;
      if( p_identifier == p_content.m_number )
        return k_seal_TREE_BRANCH_DIRECTION__STRAIGHT;
      return k_seal_TREE_BRANCH_DIRECTION__RIGHT;
    }

    t_NumberArrivesAt_TreeNode f_IsNotInTree( unsigned int p )
    {
    }
};

unsigned int f_SumOfSquaresOfDigits( unsigned int p );

extern unsigned int g_numberOfStartingNumbersThatArriveAt89;

void p_DetermineNumberOfStartingNumbersThatArriveAt89( void )
{
  unsigned int i = 1;
  const unsigned int limit = f_NumberOfDigits( g_limit ) * 9 * 9;
  NumberArrivesAt_Tree number_arrives_at;

  for( ; i <= limit; i ++ )
  {
    unsigned int k = i;

    while( !number_arrives_at.f_IsInTree( k ))
    {
      number_arrives_at.p_SetNumber( k );
      k = f_SumOfSquaresOfDigits( k );
    }
    number_arrives_at.p_SetArrivesAt( number_arrives_at.f_GetArrivesAt( k ));
  }
  for( i = 1; i <= g_limit; i ++ )
    if( number_arrives_at.f_GetArrivesAt( f_SumOfSquaresOfDigits( i )) == 89 )
      g_numberOfStartingNumbersThatArriveAt89 ++;
}

Makefile:

error:
	echo "Sorry, an error occurred: you must specify either \"method_1\" or \"method_2\"."

common: printDateAndTime.h printDateAndTime.c October\ 19th,\ 2018.cpp
	g++ -c printDateAndTime.c
	g++ -c October\ 19th,\ 2018.cpp

method_1: common method\ \#1.cpp
	g++ -c method\ \#1.cpp
	g++ printDateAndTime.o method\ \#1.o October\ 19th,\ 2018.o -o Method\ \#1
	rm printDateAndTime.o
	rm method\ \#1.o
	rm October\ 19th,\ 2018.o

method_2: common seal_tree.h method\ \#2.cpp
	g++ -c method\ \#2.cpp
	g++ printDateAndTime.o method\ \#2.o October\ 19th,\ 2018.o -o Method\ \#2
	rm printDateAndTime.o
	rm method\ \#2.o
	rm October\ 19th,\ 2018.o
Advertisements


No Responses Yet to ““Square Digit Chains””

  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s


%d bloggers like this: