Skip to Content
author's profile photo Deepak Tewari

CCC2: My Approach for Challenge No. 2 (As a UI5 developer, ABAPer and a HANA developer)

1. First and Foremost- The JavaScript Approach

getMaxCollatzUnder: function (k) {
 //Find which is the max number below 1000000, which has max steps for Collatz sequence
   var numOfSteps = 1,  //Auxilary variable to count steps for each number
       maxSteps = 0,    //Answer will be stored here
       maxNumber = 1,   //Answer will be stored here
       hashTabUsed = 0,  //no of times Hash Table helped in caching the data
       cacheHashTab = new Object(), //Hash table to keep caching data
       num = 1,         //Auxilary variable to apply Collatz formula
       currNum = 1;      //Current Number being processed

//For each number from 1 till input
  while (currNum <= k) {
    num = currNum;
    numOfSteps = 1;
	
//calculate Collatz Steps
   while (num !== 1) {
//Check if cache already knows the number of steps for this number
     if (cacheHashTab.hasOwnProperty(num)) {
	numOfSteps = numOfSteps + cacheHashTab[num] - 1;
	hashTabUsed++;
	break;
	}
     if (!(num % 2))
	num = num / 2;
     else
	num = (3 * num + 1);
     numOfSteps++;
				 }
//Keep caching the number of steps for further use
  cacheHashTab[currNum] = numOfSteps;
  if (numOfSteps > maxSteps) {
      maxSteps = numOfSteps;
      maxNumber = currNum;
     }
  //Next Number
   currNum++;
     }
	
//its upto you how you send the result back :), I just became lazy here
    var result = maxNumber + '/' + maxSteps;
sap.m.MessageToast.show("Hash Table helped: " + hashTabUsed + " times");  //This is just for fun :)
    return result;
}


//Gives result in approx 400 ms.

2. Second - An ABAP Program having local class method that does the job

REPORT Z2_CCC2.
*&---------------------------------------------------------------------*
*& Report z2_CCC2
*&---------------------------------------------------------------------*
*&
*&---------------------------------------------------------------------*
CLASS lcl_main DEFINITION.
  PUBLIC SECTION.
    CLASS-METHODS: get_answer IMPORTING i_number      TYPE i
                              EXPORTING e_maxno       TYPE i
                                        e_maxsteps    TYPE i
                                        e_hashtabused TYPE i.
ENDCLASS.


START-OF-SELECTION.
  lcl_main=>get_answer(
    EXPORTING
      i_number      = 1000000
    IMPORTING
      e_maxno       = DATA(lv_maxno)
      e_maxsteps    = DATA(lv_maxsteps)
      e_hashtabused = DATA(lv_hashtab)
  ).


   "Results are here, you can use them as you want (display a Message/ ALV/ Write Statements etc..)"


CLASS lcl_main IMPLEMENTATION.
  METHOD get_answer.
    "Find which is the max number below 1000000, which has max steps for Collatz sequence
    TYPES: BEGIN OF ty_hastab,
             key   TYPE p LENGTH 16 DECIMALS 0,
             value TYPE i,
           END OF ty_hastab.


    DATA: numofsteps   TYPE i VALUE 1,
          maxsteps     TYPE i VALUE 0,
          maxnumber    TYPE i VALUE 1,
          hashtabused  TYPE i VALUE 0,
          "Hash Table to keep hashing the data
          cachehashtab TYPE HASHED TABLE OF ty_hastab WITH UNIQUE KEY primary_key COMPONENTS key, 
          num          TYPE p LENGTH 16 VALUE 1,
          currnum      TYPE i VALUE 1.

    WHILE currnum LE i_number .
      num = currnum.
      numofsteps = 1.

      WHILE num <> 1.
        "Check if cache already knows the number of steps for this number
        DATA(cachestruct) = VALUE #( cachehashtab[ KEY primary_key COMPONENTS key = num ] OPTIONAL ).
        IF  cachestruct IS NOT INITIAL .
          numofsteps = numofsteps + cachestruct-value - 1.
          hashtabused = hashtabused + 1.
          EXIT.
        ENDIF.
        IF ( num MOD 2 = 0 ) .
          num = num DIV 2.
        ELSE.
          num = ( 3 * num + 1 ).
        ENDIF.
        numofsteps = numofsteps + 1.
      ENDWHILE.

      "Keep caching the number of steps for further use
      INSERT VALUE #( key = currnum value = numofsteps ) INTO TABLE cachehashtab.

      IF ( numofsteps > maxsteps ) .
        maxsteps = numofsteps.
        maxnumber = currnum.
      ENDIF.
      currnum = currnum + 1.
    ENDWHILE.

    e_maxno = maxnumber.
    e_maxsteps = maxsteps.
    e_hashtabused = hashtabused.
  ENDMETHOD.
ENDCLASS.


"Gives answer in approx 10-12 seconds

3. Last but not the least - HANA-SQLSCRIPT Code wrapped inside a table function

FUNCTION "XXXXX"."Deepak::CCC2_COLLATZ" ( number integer ) 
	RETURNS TABLE( maxno    int,
				   maxsteps int,
				   hashtabused int )
	LANGUAGE SQLSCRIPT
	SQL SECURITY INVOKER AS
BEGIN
/***************************** 
	Write your function logic
 *****************************
 --declare all local variables 
 DECLARE numofsteps    INTEGER;  
 DECLARE maxsteps      INTEGER;  
 DECLARE maxnumber     INTEGER;
 DECLARE hashtabused   INTEGER;
 DECLARE num           DOUBLE;
 DECLARE currnum       INTEGER;
 DECLARE hashval INTEGER;

 --This temporary table will be used for caching data
 DECLARE hashTable TABLE ( key_col DOUBLE,
  			   value_col integer );
            
      numofsteps  := 1;
      maxsteps    := 0;
      maxnumber   := 1;
      hashtabused := 0;
      num         := 1;
      currnum     := 1;     
      
  WHILE ( currnum <= number ) DO
      num := currnum;
      numofsteps := 1;

      --calculate Collatz Steps
      WHILE ( num <> 1 ) DO
        --Check if cache already knows the number of steps for this number
        hashval := 0;
        select  value_col INTO hashval default 0 from :hashTable where key_col = num;
        IF  hashval != 0  THEN
          numofsteps := numofsteps + hashval - 1;
          hashtabused := hashtabused + 1;
          BREAK;
        END IF;
        IF MOD (num,2) = 0 THEN
          num := num / 2;
        ELSE
          num := ( 3 * num + 1 );
        END IF;
        
        numofsteps := numofsteps + 1;
      END WHILE;

      --Keep caching the number of steps for further use
      INSERT INTO :hashTable VALUES ( :currnum, :numofsteps ) ;

      IF ( numofsteps > maxsteps ) THEN
        maxsteps := numofsteps;
        maxnumber := currnum;
      END IF;
      currnum := currnum + 1;
    END WHILE;     
     
    return select :maxnumber as maxno,
    			  :maxsteps  as maxsteps,
    			  :hashtabused as hashtabused
    		from dummy;	          
                 
END;

/*
--Usage: select * from "XXXXX"."Deepak::CCC2_COLLATZ"(1000000)

--Output:			
Statement 'select * from "XXXXX"."Deepak::CCC2_COLLATZ"(1000000)' 
successfully executed in 40:34.519 minutes  (server processing time: 40:33.636 minutes)
Fetched 1 row(s) in 0 ms 15 µs (server processing time: 0 ms 0 µs)
*/

All the above approaches use the same algorithm and give the same answer i.e. 837799, with 525 steps.

Suggestions and feedback over any of the above approaches is highly appreciated.

Thank You :)

* Please Login or Register to Comment on or Follow discussions.

0 Comments

    Add a comment
    10|10000 characters needed characters exceeded