Algorithmic Thinking Snowflake Problem

The challenge in this problem is to identify identical snowflakes even when the data about the snowflakes are stored in the same sequence but in a different orientation. In this problem, snowflakes have six arms of lengths varying from 1 to 6. The snowflakes are randomly generated so one snowflake may have arms represented by [1, 2, 3, 4, 5, 6] and an identical snowflake have arms of [3, 4, 5, 6, 1, 2]. These are a match. These snowflakes are identical but were generated with different orientations. A snowflake with arms of [2, 1, 3, 4, 5, 6] is not a match because its arms, even though of the same lengths, do not occur in a sequence that can be made to match the first two.

In the function makeSnowflakes() my solution generates 2000 snowflakes as the problem set. Then in searchArrayForMatches() and identifyIdentical() the program compares each arm of each snowflake to the arms of every other snowflake.

I wrote and tested this in Xcode, the Mac IDE.

Caveat: I've coded very little C and it probably shows.

	#include <stdio.h>
	#include <stdlib.h>
	#include <string.h>
	#include <time.h>
	#include <stdbool.h>
	const int SIZEOFFLAKESARRAY = 2000;
	static int flakes[SIZEOFFLAKESARRAY][6];
	void makeSnowflakes() {
	time_t t;
	srand((unsigned) time(&t));
	for (int i = 0; i < SIZEOFFLAKESARRAY; i++) {
	for (int j = 0; j < 6; j++) {
	int num = 1 + rand() % (6);
	flakes[i][j] = num;
	}
	}
	}
	bool identifyIdentical(int a, int b) {
	bool allSixArmsMatch = true;
	for (int secondArmOffset = 0; secondArmOffset < 6; secondArmOffset++) {
	allSixArmsMatch = true;
	for (int armIndex = 0; armIndex < 6; armIndex++) {
	int totalOffset = armIndex + secondArmOffset;
	if (totalOffset > 5) {
	totalOffset -= 6;
	}
	if (flakes[a][armIndex] != flakes[b][totalOffset]) {
	allSixArmsMatch = false;
	break;
	}
	}
	if (allSixArmsMatch) break;
	}
	if (allSixArmsMatch) printf("\nmatch %d %d \n%d %d %d %d %d %d \n%d %d %d %d %d %d", a, b,
	flakes[a][0], flakes[a][1], flakes[a][2], flakes[a][3], flakes[a][4], flakes[a][5],
	flakes[b][0], flakes[b][1], flakes[b][2], flakes[b][3], flakes[b][4], flakes[b][5]);
	return allSixArmsMatch;
	}
	int searchArrayForMatches() {
	bool matched = false;
	int nbrMatched = 0;
	for (int firstSnowflake = 0; firstSnowflake < SIZEOFFLAKESARRAY - 1; firstSnowflake++) {
	for (int secondSnowflake = firstSnowflake + 1; secondSnowflake < SIZEOFFLAKESARRAY; secondSnowflake++) {
	matched = identifyIdentical(firstSnowflake, secondSnowflake);
	if (matched) nbrMatched += 1;
	}
	}
	return nbrMatched;
	}
	int main() {
	makeSnowflakes();
	// create match for test case
	for (int x=0; x<6; x++) {
	int offset = x + 2; if (offset > 5) offset -= 6;
	flakes[SIZEOFFLAKESARRAY - 1][offset] = flakes[SIZEOFFLAKESARRAY - 2][x];
	}
	int nbrMatched = searchArrayForMatches();
	printf("\nNumber Matched %d\n", nbrMatched);
	return 0;
	}

view raw snowflakes.c hosted with ❤ by GitHub

Program Output

. . .
match 1749 1824 
3 2 6 5 5 3 
5 3 3 2 6 5
match 1759 1859 
3 3 6 6 5 1 
3 6 6 5 1 3
match 1776 1900 
4 4 5 2 4 5 
2 4 5 4 4 5
match 1860 1905 
6 5 2 3 4 6 
6 5 2 3 4 6
match 1915 1977 
3 1 1 1 5 4 
1 1 1 5 4 3
match 1998 1999 
1 6 3 2 6 1 
6 1 1 6 3 2
Number Matched 244
Program ended with exit code: 0