Round 3 : Minimum Sum

20Sep13

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 3):

Minimum Sum

By starting at the top of the triangle below and moving to adjacent numbers on the row below or numbers directly below, the lowest sum of the numbers from top to bottom is 13.

5

7 6

3 2 5

Find the lowest sum of numbers by moving from top to bottom in this triangle:

7

9 8

3 2 6

7 1 5 5

9 4 8 2 4

6 3 2 9 7 5

7 2 4 8 5 1 9

4 2 9 3 8 5 2 8

8 2 4 8 5 9 2 7 3

Solution (Minimum Sum.c):

Uses: seal_bool.

/*
Solution and answer for problem "Minimum Sum (Contest Coding Cup 2013 - Round 3)" (20th September 2013) of http://contestcoding.wordpress.com/

30

Solution programmed in C using Leonardo IDE 3.4.1; solution took ~1s to run on an 80MHz PowerPC 601.
*/

#include <stdio.h>
#include <stdlib.h>
#include "seal_bool.h"

typedef struct t_Row_struct
{
  struct t_Row_struct *m_up, *m_down;
  short *m_numbers, *m_sums;
}
t_Row;

t_Row *g_top = NULL;
size_t g_longestRowLength = 0;

void p_ReadRowsFromFile( FILE *p );

t_Row *f_SecondRowFromBottom( void )
{
  t_Row *r = g_top;
  while( r->m_down->m_down != NULL )
    r = r->m_down;
  return r;
}

short f_MinimumSum( const t_Row * const p_row, const size_t p_index )
{
  short a = -1, b, c, x, y;
  if( p_index > 0 )
    a = p_row->m_numbers[ p_index ] + p_row->m_down->m_sums[ p_index - 1 ];
  b = p_row->m_numbers[ p_index ] + p_row->m_down->m_sums[ p_index ];
  c = p_row->m_numbers[ p_index ] + p_row->m_down->m_sums[ p_index + 1 ];
  x = (( a < b ) && ( a != -1 ))?a:b;
  y = ( c < b )?c:b;
  return ( x < y )?x:y;
}

short f_MinimumSumRoute( void )
{
  t_Row *row = f_SecondRowFromBottom();
  size_t rowLength = g_longestRowLength - 1;
  while( row != NULL )
  {
    size_t i = 0;
    for( ; i < rowLength; i ++ )
      row->m_sums[ i ] = f_MinimumSum( row, i );
    row = row->m_up;
    rowLength --;
  }
  return g_top->m_sums[ 0 ];
}

void p_DeleteRow( t_Row *p );

void main( void )
{
  FILE *f = fopen( "Minimum Sum.in", "r" );
  p_ReadRowsFromFile( f );
  fclose( f );
  printf( "%d\n", f_MinimumSumRoute());
  p_DeleteRow( g_top );
}

bool f_ReadRowFromFile( FILE *p_file, t_Row *p_row )
{
  size_t i = 0;
  char c;
  for( ; i < g_longestRowLength; i ++ )
  {
    fscanf( p_file, "%c", &c );
    p_row->m_sums[ i ] = p_row->m_numbers[ i ] = c - '0';
    if( fscanf( p_file, "%c", &c ) == EOF ) // Discard spaces and newlines.
      return false;
  }
  return true;
}

void p_ReadRowsFromFile( FILE *p )
{
  t_Row *last = NULL;
  bool b;
  do
  {
    t_Row *r = ( t_Row* )malloc( sizeof( t_Row ));
    r->m_up = last;
    r->m_down = NULL;
    g_longestRowLength ++;
    r->m_numbers = ( short* )malloc( sizeof( short ) * g_longestRowLength );
    r->m_sums = ( short* )malloc( sizeof( short ) * g_longestRowLength );
    b = f_ReadRowFromFile( p, r );
    if( g_top == NULL )
      g_top = r;
    else
      last->m_down = r;
    last = r;
  }
  while( b );
}

void p_DeleteRow( t_Row *p )
{
  if( p != NULL )
  {
    p_DeleteRow( p->m_down );
    free( p->m_numbers );
    free( p->m_sums );
    free( p );
  }
}

Result:

30

Advertisements


No Responses Yet to “Round 3 : Minimum Sum”

  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: