Elixir circular data structure marbles for solving Advent of Code 2018 day 9
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
defmodule Marbles do | |
def new do | |
%{size: 0, current: 0, counter: 0} | |
end | |
def to_list(state) do | |
[] | |
|> do_to_list(state, state.current, state.current) | |
|> Enum.reverse | |
end | |
defp do_to_list(list, state, current, current) when length(list) > 0 do | |
list | |
end | |
defp do_to_list(list, state, current, last) do | |
{_, value, next} = state[current] | |
do_to_list([value | list], state, next, last) | |
end | |
def size(state) do | |
state.size | |
end | |
def move_next(state) do | |
{_, _, next} = state[state.current] | |
state | |
|> Map.put(:current, next) | |
end | |
def insert_next(%{size: 0} = state, value) do | |
id = state.counter + 1 | |
do_insert_next(state, id, {id, value, id}) | |
end | |
def insert_next(state, value) do | |
id = state.counter + 1 | |
prev = state.current | |
{_, _, next} = state[state.current] | |
do_insert_next(state, id, {prev, value, next}) | |
end | |
defp do_insert_next(state, id, {prev, value, next} = item) do | |
state | |
|> Map.put(id, item) | |
|> Map.put(:current, id) | |
|> Map.update(prev, item, &put_elem(&1, 2, id)) | |
|> Map.update(next, item, &put_elem(&1, 0, id)) | |
|> Map.update(:size, 0, &(&1 + 1)) | |
|> Map.update(:counter, 0, &(&1 + 1)) | |
end | |
def remove_current(%{size: 0} = state), do: state | |
def remove_current(state) do | |
{prev, _, next} = state[state.current] | |
state | |
|> Map.update(prev, nil, &put_elem(&1, 2, next)) | |
|> Map.update(next, nil, &put_elem(&1, 0, prev)) | |
|> Map.put(:current, next) | |
|> Map.update(:size, 0, &(&1 - 1)) | |
|> Map.delete(state.current) | |
end | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
defmodule Adventofcode.Day09MarbleMania.MarblesTest do | |
use ExUnit.Case | |
import Adventofcode.Day09MarbleMania.Marbles | |
describe "new/0" do | |
test "initializes a circular datastructure" do | |
assert %{size: 0, counter: 0, current: 0} == new() | |
end | |
end | |
describe "to_list/1" do | |
test "collects all values into a list" do | |
marbles = new() | |
|> insert_next("hej") | |
|> insert_next("hopp") | |
|> insert_next("tada") | |
assert ["tada", "hej", "hopp"] = to_list(marbles) | |
end | |
end | |
describe "move_next/1" do | |
test "moves current to what next was" do | |
marbles = new() | |
|> insert_next("hej") | |
|> insert_next("hopp") | |
|> insert_next("tada") | |
assert %{current: 1} = marbles = move_next(marbles) | |
assert %{current: 2} = marbles = move_next(marbles) | |
assert %{current: 3} = marbles = move_next(marbles) | |
end | |
end | |
describe "insert_next/0" do | |
test "inserts initial value" do | |
marbles = new() | |
assert %{ | |
:size => 1, | |
:counter => 1, | |
:current => 1, | |
1 => {1, "hej", 1} | |
} == insert_next(marbles, "hej") | |
end | |
test "inserts a second value" do | |
marbles = new() |> insert_next("hej") | |
assert %{ | |
:size => 2, | |
:counter => 2, | |
:current => 2, | |
1 => {2, "hej", 2}, | |
2 => {1, "hopp", 1} | |
} == insert_next(marbles, "hopp") | |
end | |
test "inserts a third value, forming a circle" do | |
marbles = new() | |
|> insert_next("hej") | |
|> insert_next("hopp") | |
assert %{ | |
:size => 3, | |
:counter => 3, | |
:current => 3, | |
1 => {3, "hej", 2}, | |
2 => {1, "hopp", 3}, | |
3 => {2, "tada", 1} | |
} == insert_next(marbles, "tada") | |
end | |
end | |
describe "remove_current/1" do | |
test "removes first node" do | |
marbles = new() |> insert_next("hej") | |
assert %{ | |
:size => 0, | |
:counter => 1, | |
:current => 1 | |
} == remove_current(marbles) | |
end | |
test "removes second node" do | |
marbles = new() | |
|> insert_next("hej") | |
|> insert_next("hopp") | |
assert %{ | |
:size => 1, | |
:counter => 2, | |
:current => 1, | |
1 => {1, "hej", 1}, | |
} == remove_current(marbles) | |
end | |
test "removes third node" do | |
marbles = new() | |
|> insert_next("hej") | |
|> insert_next("hopp") | |
|> insert_next("tada") | |
assert %{ | |
:size => 2, | |
:counter => 3, | |
:current => 1, | |
1 => {2, "hej", 2}, | |
2 => {1, "hopp", 1}, | |
} == remove_current(marbles) | |
end | |
test "removing a non existant node is a no-op" do | |
marbles = new() | |
assert %{ | |
:size => 0, | |
:counter => 0, | |
:current => 0 | |
} == remove_current(marbles) | |
end | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment