//algorytm Verhoeff'a
//www.algorytm.org
//(c)2007 by Tomasz Lubinski

#include "stdio.h"

char d[10][10] =
	   {{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
		{1, 2, 3, 4, 0, 6, 7, 8, 9, 5},
		{2, 3, 4, 0, 1, 7, 8, 9, 5, 6},
		{3, 4, 0, 1, 2, 8, 9, 5, 6, 7},
		{4, 0, 1, 2, 3, 9, 5, 6, 7, 8},
		{5, 9, 8, 7, 6, 0, 4, 3, 2, 1},
		{6, 5, 9, 8, 7, 1, 0, 4, 3, 2},
		{7, 6, 5, 9, 8, 2, 1, 0, 4, 3},
		{8, 7, 6, 5, 9, 3, 2, 1, 0, 4},
		{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}};

char p[8][10] =
		{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
		 {1, 5, 7, 6, 2, 8, 3, 0, 9, 4},
		 {5, 8, 0, 3, 7, 9, 6, 1, 4, 2},
		 {8, 9, 1, 6, 0, 4, 3, 5, 2, 7},
		 {9, 4, 5, 3, 1, 2, 6, 8, 7, 0},
		 {4, 2, 8, 6, 5, 7, 3, 9, 0, 1},
		 {2, 7, 9, 3, 8, 0, 6, 4, 1, 5},
		 {7, 0, 4, 6, 9, 1, 3, 2, 5, 8}};

char inv[10] =
		{0, 4, 3, 2, 1, 5, 6, 7, 8, 9};

/**
 * Check number
 * @param number
 * @return 1 if check digit in number is correct, 0 otherwise
 */
int verhoeffCheck(char *number)
{
	int c = 0;
	int digit, i;
	int length = strlen(number);

	for (i=0; i<length; i++)
	{
		digit = number[length - i - 1] - 48;
		c = d[c][p[i%8][digit]];
	}

	if (c == 0)
	{
		return 1;
	}
	return 0;
}

/**
 * Calculate check digit for a given number
 * @param number (with check digit with any value)
 * @return check digit
 */
int verhoeffCheckDigit(char *number)
{
	int c = 0;
	int digit, i;
	int length = strlen(number);

	for (i=1; i<length; i++)
	{
		digit = number[length - i - 1] - 48;
		c = d[c][p[i%8][digit]];
	}

	return inv[c];
}

/**
 * Get number and check it
 */
int main()
{
	char number[1000];

	printf("Podaj numer do sprawdzenia\n");
	scanf("%s", number);

	if (verhoeffCheck(number))
	{
		printf("Numer jest prawidlowy\n");
	}
	else
	{
		printf("Numer jest nieprawidlowy\n");
		printf("Dla tego numeru prawidlowa cyfra kontrolna to %d\n", verhoeffCheckDigit(number));
	}
}