ece264/solutions/ECE264Solutions/PA04/answer04.c

/*
 * Please fill the functions in this file.
 * You can add additional functions. 
 *
 * Hint: 
 * You can write additonal functions.
 * You can test your functions with your own input file.
 * See details in README or typing command ./pa04 in terminal after make.
 * See output format examples in any of the files in directory expected.
 * 
 * You may create additional arrays if needed.  The maximum size
 * needed is specified by MAXLENGTH in pa04.h.
 */

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

/*
 * =================================================================
 * This function prints an array formatted as a partition.
 */
void partPrint(int *part, int index)
{
	int i;
	for(i = 0; i < index; i++)
	{
		if(i == 0)
			printf("= %d", part[i]); // print '=' in front of 0th index
		else
			printf(" + %d", part[i]); // print '+' in front of other indices
	}
	printf("\n");
}

/*
 * =================================================================
 * This function prints all partitions of a positive integer value
 * For example, if the value is 3:
 *
 * partitionAll 3
 * = 1 + 1 + 1
 * = 1 + 2
 * = 2 + 1
 * = 3
 */
void partitionAllHelp(int *part, int value, int index)
{	
	if (value == 0)
	{
		partPrint(part, index); // print last (initial) value
		return;
	}
	
	int i;
	for (i = 1; i <= value; i++)
	{
		part[index] = i;
		partitionAllHelp(part, value - i, index + 1); // partition other values
	}
}

void partitionAll(int value)
{
	printf("partitionAll %d\n", value);
	int part[MAXLENGTH]; // create array to store partition ints
	partitionAllHelp(part, value, 0); // call helper function
}

/*
 * =================================================================
 * This function prints the partitions that use increasing values.
 *
 * For example, if value is 5
 * 2 + 3 and
 * 1 + 4 are valid partitions
 *
 * 5 is a valid partition
 * 
 * 1 + 1 + 3 and
 * 2 + 1 + 2 and
 * 3 + 2 are invalid partitions.
 * 
 * The program should generate only valid partitions.  Do not
 * generates invalid partitions and checks validity before printing.
 *
 */
void partitionIncreasingHelp(int *part, int value, int index, int iIn)
{	
	if (value == 0)
	{
		partPrint(part, index);
		return;
	}

	int i;
	for (i = iIn++; i <= value; i++) // start with previous value of i
	{
		part[index] = i;
		partitionIncreasingHelp(part, value - i, index + 1, iIn++);
	}
}

void partitionIncreasing(int value)
{
  printf("partitionIncreasing %d\n", value);
	int part[MAXLENGTH];
	partitionIncreasingHelp(part, value, 0, 1);
}

/*
 * =================================================================
 * This function prints the partitions that use Decreasing values.
 *
 * For example, if value is 5
 * 3 + 2 and
 * 4 + 1 are valid partitions
 *
 * 5 is a valid partition
 * 
 * 1 + 1 + 3 and
 * 2 + 1 + 2 and
 * 2 + 3 are invalid partitions.
 * 
 * The program should generate only valid partitions.  Do not
 * generates invalid partitions and checks validity before printing.
 *
 */
void partitionDecreasingHelp(int *part, int value, int index, int iIn)
{	
	if (value == 0)
	{
		partPrint(part, index);
		return;
	}

	int i;
	for (i = iIn--; i > 0; i--) // reverse partitionDecreasing
	{
		part[index] = i;
		partitionDecreasingHelp(part, value - i, index + 1, iIn--);
	}
}

void partitionDecreasing(int value)
{
  printf("partitionDecreasing %d\n", value);
	int part[MAXLENGTH];
	partitionDecreasingHelp(part, value, 0, value);
}

/*
 * =================================================================
 * This function prints odd number only partitions of a positive integer value
 * For example, if value is 5
 * 1 + 1 + 1 + 1 + 1 and
 * 1 + 3 + 1 are valid partitions
 *
 * 5 is a valid partition
 * 
 * 1 + 1 + 1 + 2 and
 * 2 + 1 + 2 and
 * 2 + 3 are invalid partitions.
 * 
 * The program should generate only valid partitions.  Do not
 * generates invalid partitions and checks validity before printing.
 */
void partitionOddHelp(int *part, int value, int index)
{	
	if (value == 0)
	{
		partPrint(part, index);
		return;
	}

	int i;
	for (i = 1; i <= value; i = i + 2) // increment by 2 for only odd numbers
	{
		part[index] = i;
		partitionOddHelp(part, value - i, index + 1);
	}
}

void partitionOdd(int value)
{
	printf("partitionOdd %d\n", value);
	int part[MAXLENGTH];
	partitionOddHelp(part, value, 0);
}

/*
 * =================================================================
 * This function prints even number only partitions of a positive integer value
 * For example, if value is 8
 * 2 + 2 + 2 + 2and
 * 2 + 4 + 2 are valid partitions
 *
 * 8 is a valid partition
 *
 * 2 + 1 + 1 + 2 + 2and
 * 2 + 1 + 2 + 3and
 * 5 + 3 are invalid partitions.
 *
 * if the value is 5, there will be no result generated
 * 
 * The program should generate only valid partitions.  Do not
 * generates invalid partitions and checks validity before printing.
 */
void partitionEvenHelp(int *part, int value, int index)
{	
	if (value == 0)
	{
		partPrint(part, index);
		return;
	}

	int i;
	for (i = 2; i <= value; i = i + 2) // start with 2 and increment by 2 for only even numbers
	{
		part[index] = i;
		partitionEvenHelp(part, value - i, index + 1);
	}
}

void partitionEven(int value)
{
	printf("partitionEven %d\n", value);
	int part[MAXLENGTH];
	partitionEvenHelp(part, value, 0);
}

/*
 * =================================================================
 * This function prints alternate odd and even number partitions of a positive integer value. Each partition starts from and odd number, even number, ood number again, even number again...etc.
 *
 * For example, if value is 6
 * 1 + 2 + 1 + 2 and
 * 3 + 2 + 1 are valid partitions
 *
 * 6 is not a valid partition
 *
 * 2 + 1 + 1 + 2 and
 * 2 + 1 + 3and
 * 5 + 1 are invalid partitions.
 * 
 * The program should generate only valid partitions.  Do not
 * generates invalid partitions and checks validity before printing.
 */
void partitionOddAndEvenHelp(int *part, int value, int index, int iIn)
{	
	if (value == 0)
	{
		partPrint(part, index);
		return;
	}

	int i;
	for (i = iIn; i <= value; i = i + (iIn % 2) + 1) // start with odd (1)
	{																								 // increment by opposite
		if(i % 2 == 0 && iIn % 2 == 0) // check if i and iIn are even
		{
			part[index] = i;
			partitionOddAndEvenHelp(part, value - i, index + 1, iIn - 1);
		}
		if(i % 2 == 1 && iIn % 2 == 1) // check if i and iIn are odd
		{
			part[index] = i;
			partitionOddAndEvenHelp(part, value - i, index + 1, iIn + 1);
		}
	}
}

void partitionOddAndEven(int value)
{
	printf("partitionOddAndEven %d\n", value);
	int part[MAXLENGTH];
	partitionOddAndEvenHelp(part, value, 0, 1);
}

/*
 * =================================================================
 * This function returns 1 if a value is prime and 0 if it is not.
 */
int isPrime(int value)
{
  if (value <= 1) 
		return 0; // return 0 if value is less than 2 (not prime)

  int i;
  for (i = 2; i * i <= value; i++)  // start with 2, go until sqrt(value)
	{
    if (value % i == 0) // check value for divisibility
			return 0; // return 0 if evenly divisible value is found
  }

  return 1; // return 1 if value is prime
}
/*
 * =================================================================
 * This function prints prime number only partitions of a positive integer value
 * For example, if value is 6
 * 2 + 2 + 2 and
 * 3 + 3 are valid partitions
 *
 * 6 is not a valid partition
 * 
 * 2 + 4 and
 * 1 + 5 are invalid partitions.
 * 
 * The program should generate only valid partitions.  Do not
 * generates invalid partitions and checks validity before printing.
 */
void partitionPrimeHelp(int *part, int value, int index)
{
	if (value == 0)
	{
		partPrint(part, index);
		return;
	}

	int i;
	for (i = 2; i <= value; i++)
	{
		if(isPrime(i)) // check for primeness
		{
			part[index] = i;
			partitionPrimeHelp(part, value - i, index + 1);
		}
	}
}

void partitionPrime(int value)
{
	printf("partitionPrime %d\n", value);
	int part[MAXLENGTH];
	partitionPrimeHelp(part, value, 0);
}