day10.cs

class Day10
{
	// http://adventofcode.com/2017/day/10

	// An example worthy of note that uses lots of LINQ. Neat!
	// https://www.reddit.com/r/adventofcode/comments/7irzg5/2017_day_10_solutions/dr15bpc/

	private const int DayID = 10;

	private byte[] Lengths1;
	private byte[] Lengths2;

	private const int ByteArrayLength = 256;

	private const int Iterations1 = 1;
	private const int Iterations2 = 64;

	public Day10()
	{
		string data = Utils.ReadDataFile(DayID);
		int dataLen = data.Length;

		// As specified by the puzzle. This is used
		// for part 1.
		// Parse the array as a comma delimited list
		// of integers.
		this.Lengths1 = Utils.StringToArrayMulti<byte>(data);

		// As specified by the puzzle. This is used
		// for part 2.
		// Read each character from the input
		// string as a byte this time.
		this.Lengths2 = new byte[dataLen];
		for (int i = 0; i < dataLen; i++)
		{
			this.Lengths2[i] = (byte)data[i];
		};

		// Append the additional array items as specified
		// by the part 2 puzzle.
		byte[] additional = new byte[] { 17, 31, 73, 47, 23 };
		this.Lengths2 = this.Lengths2.Concat(additional).ToArray();
	}

	public int Part1()
	{
		byte[] list = this.KnotHash(this.Lengths1,
									Day10.Iterations1);

		return list[0] * list[1];
	}


	public string Part2()
	{
		byte[] list = this.KnotHash(this.Lengths2,
									Day10.Iterations2);

		// Now that we have our sparse hash we need to
		// convert it into a dense hash.
		// This is done by reducing each block of
		// 16 integers into a single integer by XOR'ing
		// the 16 elements within the block against
		// each other.
		// This will leave us with an array of 16
		// integers instead of 256 integers.
		byte[] blocks = this.PackArray(list);

		// Conver our dense hash into a hexadecimal
		// string for our output.
		string hex = "";
		foreach (byte block in blocks)
		{
			// Convert the integer into hexadecimal
			// and pad as required.
			hex += block.ToString("x").PadLeft(2, '0');
		}

		return hex;
	}

	private byte[] PackArray(byte[] sparce)
	{
		int len = sparce.Length;
		if (len % 16 != 0)
		{
			throw new ArgumentException("The array must have an array length that is divisible by 16.");
		}

		byte[] blocks = new byte[len / 16];
		int blockID = 0;
		for (int i = 0; i < Day10.ByteArrayLength; i++)
		{
			// If we have processed 16 integers
			// then we need to move to the next block.
			// The exception being element 0 which
			// should not cause us to move to the
			// next block.
			if (i > 0 && i % 16 == 0)
			{
				++blockID;
			}

			// XOR this value against the value already
			// contained within this block.
			blocks[blockID] ^= sparce[i];
		}

		return blocks;
	}

	private byte[] KnotHash(byte[] lengths, int iterations)
	{
		// Create the base byte list.
		byte[] list = Utils.InitializeByteArray(Day10.ByteArrayLength);
		byte[] section;

		// The current position and skip size are
		// preserved with each loop iteration.
		int currentPos = 0, sectionPos = 0, skipSize = 0;
		int sectionStartPos = 0, sectionLength = 0;

		int lengthsLen = lengths.Length;
		while (iterations > 0)
		{
			for (int i = 0; i < lengthsLen; i++)
			{
				// Get the next section length.
				sectionLength = lengths[i];

				// Initialize our array to be the length of the
				// next section that we are going to extract.
				section = new byte[sectionLength];

				// Set our section start position to the current
				// position within the original list.
				sectionStartPos = currentPos;

				// This will be used when iterating through
				// the elements to be added to our section
				// list. We do not want to modify
				// currentPos as it is used below!
				sectionPos = currentPos;

				// Extract the section of the list that
				// we need to reverse.
				for (int j = 0; j < sectionLength; j++)
				{
					// Wrap around if the current position
					// falls outside of the length of the
					// array.
					if (sectionPos == Day10.ByteArrayLength)
					{
						sectionPos = 0;
					}

					section[j] = list[sectionPos++];
				}

				// Reverse the extracted section.
				section = section.Reverse().ToArray();

				// Splice the extracted section back into
				// the original list.
				for (int j = 0; j < sectionLength; j++)
				{
					// Wrap around if the current position
					// falls outside of the length of the
					// array.
					if (sectionStartPos == Day10.ByteArrayLength)
					{
						sectionStartPos = 0;
					}

					list[sectionStartPos++] = section[j];
				}

				// Move the current position forward by the
				// length of the section plus the skip
				// size.
				currentPos += sectionLength + skipSize++;

				// Wrap around if the current position
				// falls outside of the length of the
				// array. This could be done with a 
				// modulo but that is quite a bit slower.
				while (currentPos > Day10.ByteArrayLength)
				{
					currentPos -= Day10.ByteArrayLength;
				}
			}

			--iterations;
		}

		return list;
	}
}