#include <stdio.h>
#include <math.h>

int main()
{
	FILE* infile, *outfile;
	unsigned char ch,ch2;
	int rows=0,cols=0,max=0;
	int n,m,p,k;
	infile=fopen("image.ppm","r");
	for(n=0;n<3;n++)
	{
		fread(&ch,sizeof(char),1,infile); //P,6,\n
	}
	while(1)
	{
		fread(&ch,sizeof(char),1,infile);
		if(ch==' ') break;
		cols*=10;
		cols+=(ch-'0');
	}
	while(1)
	{
		fread(&ch,sizeof(char),1,infile);
		if(ch=='\n') break;
		rows*=10;
		rows+=(ch-'0');
	}
	while(1)
	{
		fread(&ch,sizeof(char),1,infile);
		if(ch=='\n') break;
		max*=10;
		max+=(ch-'0');
	}
	int color[rows][cols][3];
	for(n=0;n<rows;n++)
	{
		for(m=0;m<cols;m++)
		{
			for(p=0;p<3;p++)
			{
				fread(&ch,sizeof(char),1,infile);
				color[n][m][p]=(int)(ch);
			}
		}
	}
	int gray[rows][cols];	
	for(n=0;n<rows;n++)
        {
		for(m=0;m<cols;m++)
		{
			gray[n][m]=(color[n][m][0]+color[n][m][1]+color[n][m][2])/3;
		}
	}
	fclose(infile);
	printf("%d\t%d\n",rows,cols);
	outfile=fopen("gradient.ppm","w");
	fprintf(outfile,"P6\n%d %d\n%d\n",cols,rows,max);
	int gradient[rows][cols];
	for(n=0;n<rows;n++)
	{
		gradient[n][0]=255;
		gradient[n][cols-1]=255;
	}
	for(n=0;n<cols;n++)
	{
		gradient[0][n]=255;
		gradient[rows-1][n]=255;
	}
	for(n=1;n<rows-1;n++)
	{
		for(m=1;m<cols-1;m++)
		{
			gradient[n][m]=abs(gray[n][m+1]-gray[n][m]);
			
		}
	}
	for(n=0;n<rows;n++)
	{
		for(m=0;m<cols;m++)
		{
			for(p=0;p<3;p++) fprintf(outfile,"%c",gradient[n][m]);
		}
	}
	fclose(outfile);
	int newwidth=cols/2;
	for(p=cols;p>newwidth;p--)
	{
		int minsum=256*rows;
		int minpath[rows];
		int sum=0;
		int path[rows];
		int lowIndex,low;
		for(n=1;n<p-1;n++) //loops through starting pixels
		{
			path[0]=n;
			sum+=gradient[0][n];
			for(m=1;m<rows;m++)
			{
				if(gradient[m][path[m-1]-1] > gradient[m][path[m-1]] && 
				gradient[m][path[m-1]-1] > gradient[m][path[m-1]+1]) 
				{
					lowIndex=path[m-1]-1; 
					low=gradient[m][path[m-1]-1];
				}
				else if(gradient[m][path[m-1]] > gradient[m][path[m-1]+1]) 
				{
					lowIndex=path[m-1]; 
					low=gradient[m][path[m-1]];
				}
				else 
				{
					lowIndex=path[m-1]+1; 
					low=gradient[m][path[m-1]+1];
				}
				sum+=low;
				path[m]=lowIndex;
			}
			if(sum<minsum) 
			{
				minsum=sum;
				for(m=0;m<rows;m++) 
					minpath[m]=path[m];
			}
			sum=0;
		}
		for(n=0;n<rows;n++)
		{
			for(m=minpath[n];m<cols-1;m++)
			{
				color[n][m][0]=color[n][m+1][0];
				color[n][m][1]=color[n][m+1][1];
				color[n][m][2]=color[n][m+1][2];
			}
		}
		//generate grayscale
		for(n=0;n<rows;n++)
	        {
			for(m=0;m<p;m++)
			{
				gray[n][m]=(color[n][m][0]+color[n][m][1]+color[n][m][2])/3;
			}
		}
		//generate gradient
		for(n=0;n<rows;n++)
		{
			gradient[n][0]=255;
			gradient[n][p-1]=255;
		}
		for(n=0;n<p;n++)
		{
			gradient[0][n]=255;
			gradient[rows-1][n]=255;
		}
		for(n=1;n<rows-1;n++)
		{
			for(m=1;m<p-1;m++)
			{
				gradient[n][m]=abs(gray[n][m+1]-gray[n][m]);		
			}
		}
	}
	outfile=fopen("final.ppm","w");
	fprintf(outfile,"P6\n%d %d\n%d\n",newwidth,rows,max);
	for(n=0;n<rows;n++)
	{
		for(m=0;m<newwidth;m++)
		{
			fprintf(outfile,"%c",color[n][m][0]);
			fprintf(outfile,"%c",color[n][m][1]);
			fprintf(outfile,"%c",color[n][m][2]);
		}
	}
	fclose(outfile);
	return 0;
}