Advent of Code 2024 - Day 9

Hello, Erlang enthusiasts! Ukrainian Erlanger is here! :metal: Today’s challenge, Day 9, has us diving into the world of file systems and disk compacting! :floppy_disk: It’s time to bring some order to the chaos and solve the amphipod’s disk fragmentation woes.

The task: Rearrange file blocks to remove gaps and calculate a checksum based on the final arrangement. It’s a fantastic opportunity to leverage Erlang’s functional power to process the disk map efficiently!

:bulb: Tips for tackling Day 9:

  • Parse the dense disk map carefully, ensuring you extract file and free space segments correctly.
  • Think about how to simulate the file-moving process step by step.
  • Use lists or maps modules to calculate the checksum in an efficient and elegant way.

:sparkles: Motivation for today:
Even the most fragmented problem can be solved, one block at a time. Let’s rearrange, calculate, and Beam together!

Post your progress, insights, or full solutions below. Whether you’re compacting files or computing checksums, this is your space to share and learn.

Happy coding, and may your disk map always be compact! :christmas_tree::computer:

Okay. The solution is quite… immense, but it is O(n)-ish in one loop from both ends and calculates the checksum incrementally.
Reading this code without comments is quite complicated, therefore some explanations:

  • If forward iter is even: it is a “file” sequence, so we update the checksum and total lengths of “file blocks” and continue.
  • If forward iter is odd: it is a “gap”, so we try to fetch a sufficient buffer by walking backward. Afterward, we drain that buffer by the length of the current “gap” and forward the remainder of this buffer to the next iteration.

This doesn’t look like idiomatic Erlang, I suppose, but I didn’t know the length of the input while writing the solution, so went with as optimized a solution as I was able to come up with. Now I ran out of the brain juice for part two, so see you later folks.

-module(day_09).

-export([main/1]).

main(File) ->
	{ok, Input} = file:read_file(File),
	LastIndex = byte_size(Input) - 1,
	calculate_checksum(Input, 0, LastIndex).

calculate_checksum(Input, ForwardIter, ReverseIter) ->
	calculate_checksum(Input, ForwardIter, ReverseIter, 0, 0, []).
calculate_checksum(Input, ForwardIter, ReverseIter, TotalLength, Checksum, BackBuffer) when ForwardIter >= ReverseIter ->
	BlockSize = block_size(Input, ForwardIter),	
	Checksum + derive_partial_checksum(ForwardIter div 2, TotalLength, BlockSize) + buffer_checksum(BackBuffer, TotalLength + BlockSize);
calculate_checksum(Input, ForwardIter, ReverseIter, TotalLength, Checksum, BackBuffer) ->
	BlockSize = block_size(Input, ForwardIter),	
	case ForwardIter rem 2 of
		0 -> 
			calculate_checksum(
				Input,
				ForwardIter+1,
				ReverseIter,
				TotalLength + BlockSize,
				Checksum + derive_partial_checksum(ForwardIter div 2, TotalLength, BlockSize),
				BackBuffer
			 );
		1 when (ReverseIter rem 2) == 0 -> 
			BufferSize = lists:foldl(fun({BufBlockSize, _}, Acc) -> Acc + BufBlockSize end, 0, BackBuffer),
			{NewRevIter, BufExtension} = fetch_buffer(Input, BlockSize - BufferSize, ReverseIter),
			{NewBuffer, Drainage} = drain_buffer(BackBuffer ++ BufExtension, BlockSize),
			PartialChecksum = buffer_checksum(Drainage, TotalLength),

			calculate_checksum(
				Input,
				ForwardIter+1,
				NewRevIter,
				TotalLength + BlockSize,
				Checksum + PartialChecksum,
				NewBuffer
			 );
		_ ->
			calculate_checksum(
				Input,
				ForwardIter,
				ReverseIter-1,
				TotalLength,
				Checksum,
				BackBuffer
			 )
	end.

fetch_buffer(Input, RequiredSize, ReverseIter) ->
	fetch_buffer(Input, RequiredSize, ReverseIter, []).
fetch_buffer(_, RequiredSize, ReverseIter, Buffer) when RequiredSize < 1 ->
	{ReverseIter, lists:reverse(Buffer)};
fetch_buffer(Input, RequiredSize, ReverseIter, Buffer) -> 
	BlockSize = block_size(Input, ReverseIter),
	fetch_buffer(
		Input, 
	  	RequiredSize-BlockSize,
		ReverseIter-2,
		[{BlockSize, ReverseIter div 2} | Buffer]
	 ).

drain_buffer(Buf, FetchSize) ->
	drain_buffer(Buf, FetchSize, []).
drain_buffer(Buf, FetchSize, Drainage) when FetchSize < 1 ->
	{Buf, lists:reverse(Drainage)};
drain_buffer([{BlockSize, Index} = H | T], FetchSize, Drainage) ->
	case BlockSize - FetchSize of
		SizeDelta when SizeDelta > 0 ->
			drain_buffer([{SizeDelta, Index} | T], 0, [{FetchSize, Index} | Drainage]);
		_ ->
			drain_buffer(T, FetchSize - BlockSize, [H | Drainage])
		end.

derive_partial_checksum(Value, Index, Iterations) ->
	derive_partial_checksum(Value, Index, Iterations, 0).
derive_partial_checksum(_, _, 0, Checksum) ->
	Checksum;
derive_partial_checksum(Value, Index, Iterations, Checksum) ->
	derive_partial_checksum(Value, Index+1, Iterations-1, Checksum + Value*Index).

buffer_checksum(Buffer, Index) ->
	{Checksum, _} = lists:foldl(
	  	fun({BlockSize, Value}, {Sum, Len}) -> {Sum + derive_partial_checksum(Value, Len, BlockSize), Len + BlockSize} end,
	  	{0, Index}, 
	  	Buffer
	  ),

	Checksum.

block_size(Input, Index) -> binary:at(Input, Index) - $0.
1 Like

Your solution is quite an impressive feat of optimization! :rocket: The incremental checksum calculation and dual iteration from both ends are creative and efficient, especially given the constraints of not knowing the input length beforehand. While it might not look like traditional idiomatic Erlang, it showcases how to adapt the language to meet performance needs. Rest up and good luck tackling part two - this is already an excellent piece of work! :christmas_tree::computer: