Skip to content

Instantly share code, notes, and snippets.

@dideler
Last active December 9, 2023 19:32
Show Gist options
  • Save dideler/1568fb211cf8636f77f16c54b8cc38f9 to your computer and use it in GitHub Desktop.
Save dideler/1568fb211cf8636f77f16c54b8cc38f9 to your computer and use it in GitHub Desktop.
Code katas - small toy problems to practice technique
# At a building there are two queues of people: entering and leaving.
# Only one person can go through the turnstile at a time.
# A person leaving and a person entering can approach the turnstile at the same time.
# Given two integer arrays of times and directions of people, figure out who goes when.
#
# If no conflict at time t, first come first served
# Otherwise,
# if gate was not used in previous second, out has priority
# if gate was used in previous second to go out, out has priority
# if gate was used in previous second to go in, in has priority
# person 0 approaches turnstile at time 0 and wants to exit
# person 1 approaches turnstile at time 1 and wants to enter
# person 2 approaches turnstile at time 1 and wants to exit
# person 3 approaches turnstile at time 3 and wants to exit
# person 4 approaches turnstile at time 3 and wants to enter
times = [0, 1, 1, 3, 3]
directions = [0, 1, 0, 0, 1]
# person 0 uses turnstile at time 0
# person 1 uses turnstile at time 2
# person 2 uses turnstile at time 1
# person 3 uses turnstile at time 4
# person 4 uses turnstile at time 3
expected = [0, 2, 1, 4, 3]
defmodule Person do
defstruct [:id, :approach_time, :direction, :pass_time]
def new(id, times, directions) do
struct(__MODULE__,
id: id,
approach_time: Enum.at(times, id),
direction: if(Enum.at(directions, id) == 0, do: :out, else: :in)
)
end
end
n = length(times)
range = 0..(n - 1)
people = Enum.map(range, &Person.new(&1, times, directions))
# [
# %Person{approach_time: 0, direction: :out, id: 0, pass_time: nil},
# %Person{approach_time: 1, direction: :in, id: 1, pass_time: nil},
# %Person{approach_time: 1, direction: :out, id: 2, pass_time: nil},
# %Person{approach_time: 3, direction: :out, id: 3, pass_time: nil},
# %Person{approach_time: 3, direction: :in, id: 4, pass_time: nil}
# ]
timing_conflicts = Enum.group_by(people, & &1.approach_time)
# %{
# 0 => [
# %Person{approach_time: 0, direction: :out, id: 0, pass_time: nil}
# ],
# 1 => [
# %Person{approach_time: 1, direction: :in, id: 1, pass_time: nil},
# %Person{approach_time: 1, direction: :out, id: 2, pass_time: nil}
# ],
# 3 => [
# %Person{approach_time: 3, direction: :out, id: 3, pass_time: nil},
# %Person{approach_time: 3, direction: :in, id: 4, pass_time: nil}
# ]
# }
person_priority = fn
[%{direction: dir} = a, b], dir -> {a, b}
[a, %{direction: dir} = b], dir -> {b, a}
end
Enum.reduce(timing_conflicts, [], fn
# No conflict, person can enter/leave right away.
{t, [solo_person]}, pqueue ->
[
%{solo_person | pass_time: t}
| pqueue
]
# Two people are conflicting on enter/leave time, resolve the priority.
{t, person_pair}, pqueue ->
case Enum.find(pqueue, &(&1.pass_time == t - 1)) do
# Gate not used in previous second, out has priority
nil ->
{leaving, entering} = person_priority.(person_pair, :out)
[
%{leaving | pass_time: t},
%{entering | pass_time: t + 1}
| pqueue
]
# Gate used in previous second to leave, so leave has priority.
%{direction: :out} ->
{leaving, entering} = person_priority.(person_pair, :out)
[
%{leaving | pass_time: t},
%{entering | pass_time: t + 1}
| pqueue
]
# Gate used in previous second to enter, so enter has priority.
%{direction: :in} ->
{entering, leaving} = person_priority.(person_pair, :in)
[
%{entering | pass_time: t},
%{leaving | pass_time: t + 1}
| pqueue
]
end
end)
|> Enum.sort_by(& &1.id)
|> Enum.map(& &1.pass_time)
|> IO.inspect()
|> Kernel.==(expected)
|> IO.inspect()
@cshintov
Copy link

cshintov commented Dec 9, 2023

Shouldn't the expected be

[0, 2, 1, 3, 4]

?

Since at 2 second there's no use of the turnstile 3 - exit gets priority?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment