Round 4 : Perfect Squares Circular Sum Vector

04Oct13

I recently participated in the Contest Coding Cup 2013 organised by Lewis Cornwall, being amongst the six (out of fourteen) participants to progress to the final round, in which I achieved a rank of 6th.

As submissions of solutions to that contest are now closed, I’m posting here the solutions I submitted to that contest.

Problem (Round 4):

Perfect Squares Circular Sum Vector

Find a sequence of size 40 using integers 1 thru 40 such that every number in the sequence is a perfect square when summed with the next number in that sequence and such that the first and final numbers sum to make to a perfect square.

– This puzzle was suggested by Richard Zapor

Solution (Round_4.java):

/*
Solution and answer for problem "Perfect Squares Circular Sum Vector (Contest Coding Cup 2013 - Round 4)" (4th October 2013) of http://contestcoding.wordpress.com/

Fri Nov 08 07:39:21 GMT+00:00 2013

[ 1, 3, 6, 19, 30, 34, 2, 7, 18, 31, 33, 16, 9, 40, 24, 25, 39, 10, 15, 21, 28, 36, 13, 23, 26, 38, 11, 5, 20, 29, 35, 14, 22, 27, 37, 12, 4, 32, 17, 8 ]

Fri Nov 08 07:42:57 GMT+00:00 2013

Solution programmed in Java using Metrowerks CodeWarrior IDE 2.1 (Discover Programming Edition); solution took ~3:36 to run on an 80MHz PowerPC 601.
*/

import java.util.Date;

public class Round_4 // "Perfect_Squares_Circular_Sum_Vector.java" exceeds Mac OS 8's limitation on the length of file names.
{
  private static final int K = 40;
  private static boolean integerUsed[] = new boolean[ K ];
  private static int value[] = new int[ K ];

  public static void main( String p[] )
  {
    System.out.println( new Date());

    for( int i = 0; i < K; i ++ )
      integerUsed[ i ] = false;
    determineValues( 1 );
    System.out.print( "\n[ " );
    for( int i = 0; i < K; i ++ )
    {
      System.out.print( value[ i ] );
      if( i + 1 < K )
        System.out.print( ", " );
    }
    System.out.println( " ]\n" );

    System.out.println( new Date());
  }

  private static boolean determineValues( int i )
  {
    if( i == 1 )
    {
      integerUsed[ 1 - 1 ] = true;
      value[ i - 1 ] = 1;
      if( determineValues( i + 1 ))
        return true;
    }
    else
      if( i != K )
      {
        int n = 0;
        do
        {
          if(( n = integerNecessaryForPerfectSquare( value[ i - 2 ], n )) != -1 )
          {
            integerUsed[ n - 1 ] = true;
            value[ i - 1 ] = n;
            if( determineValues( i + 1 ))
              return true;
            integerUsed[ n - 1 ] = false;
          }
        }
        while( n != -1 );
      }
      else
      {
        int n = 0;
        do
        {
          if(( n = integerNecessaryForPerfectSquare( value[ 0 ], n )) != -1 )
          {
            if( isPerfectSquare( value[ K - 2 ] + n ))
            {
              integerUsed[ n - 1 ] = true;
              value[ K - 1 ] = n;
              return true;
            }
          }
        }
        while( n != - 1 );
      }
    return false;
  }

  private static int integerNecessaryForPerfectSquare( int p_otherInteger, int p_integerMustBeGreaterThan )
  {
    for( int i = p_integerMustBeGreaterThan + 1; i <= K; i ++ )
      if( !integerUsed[ i - 1 ] && isPerfectSquare( p_otherInteger + i ))
        return i;
    return -1;
  }

  private static boolean isPerfectSquare( int p )
  {
    final double d = Math.sqrt( p );
    return d == ( int )d;
  }
}

Result:

Fri Nov 08 07:39:21 GMT+00:00 2013

[ 1, 3, 6, 19, 30, 34, 2, 7, 18, 31, 33, 16, 9, 40, 24, 25, 39, 10, 15, 21, 28, 36, 13, 23, 26, 38, 11, 5, 20, 29, 35, 14, 22, 27, 37, 12, 4, 32, 17, 8 ]

Fri Nov 08 07:42:57 GMT+00:00 2013
Advertisements


No Responses Yet to “Round 4 : Perfect Squares Circular Sum Vector”

  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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s


%d bloggers like this: