На codingame решил все задачи из блока easy и перешёл к medium. Первой задачей "средней сложности", стала разработка вируса для битвы со Skynet. Ну а по сути, нужно было не дать боту достигнуть одной из целевых вершин (шлюзы) в ненаправленном графе.
Моя стратегия обороны была основана на том, что одна вершина не может быть напрямую связана более чем с одним шлюзом. Значит можно просто обрубать связи бот-шлюз, если такие есть, в противном случае выключать любую связь бот-вершина.
Как и раньше, при разработке решения основная цель - освоение OCaml. Исходя из этого, хотел сделать для графа свою структуру с вершинами и связями, чтобы поработать с определением новых типов, но потом отказался от этого в пользу матрицы смежности, реализованной на массивах целых чисел. Впрочем, похожего результата можно было добиться с помощью других структур данных, но я не стал долго возиться с выбором.
Первое решение
Вот так выглядел первый вариант решения, который смог победить бота. Несмотря на то, что с задачей этот код справляется, меня он не устраивал. Если бы писал бота для игры, то поддержка такого кода вызывала бы только нехорошие мысли об авторе. Поэтому я задумал рефакторинг.
let read_network_config () =
let init_data = read_line () in
Scanf.sscanf init_data "%d %d %d" (fun n l e -> (n, l, e))
let create_disconnected_network nodes_number =
Array.make_matrix nodes_number nodes_number 0
let connect_nodes network edges_number =
for i = 0 to edges_number - 1 do
let edge = read_line () in
let n1, n2 = Scanf.sscanf edge "%d %d" (fun n1 n2 -> (n1, n2)) in
network.(n1).(n2) <- 1;
network.(n2).(n1) <- 1;
done
let read_gateways gateway_number =
Array.init gateway_number (fun i -> read_int ())
let search_nodes_to_disconnect network gateways skynet_agent_position =
let to_destroy = Array.map (fun i -> if network.(i).(skynet_agent_position) = 1 then (Some i, Some skynet_agent_position) else (None, None)) gateways in
let e = Array.fold_left (fun a b ->
match a, b with
| (None, None), (None, None) -> (None, None)
| (Some x, Some y), (None, None) | (None, None), (Some x, Some y) -> (Some x, Some y)
) (None, None) to_destroy in
let rec find_edge e =
if e < Array.length network then
if network.(skynet_agent_position).(e) = 1 then
(
network.(skynet_agent_position).(e) <- 0;
network.(e).(skynet_agent_position) <- 0;
e
)
else find_edge (e + 1)
else
0
in
match e with
| (None, None) -> (skynet_agent_position, find_edge 0)
| (Some x, Some y) -> (
network.(x).(y) <- 0;
network.(y).(x) <- 0;
(x, y)
)
let disconnect_nodes (a, b) =
Printf.printf "%d %d\n" a b
let () =
let nodes_number, edges_number, gateway_number = read_network_config () in
let network = create_disconnected_network nodes_number in
connect_nodes network edges_number;
let gateways = read_gateways gateway_number in
while true do
read_int () |> search_nodes_to_disconnect network gateways |> disconnect_nodes
done
Рефакторинг
При рефакторинге для меня важно было добиться логичной структуры программы, читабельности и спрятать реализацию графа либо в модуль, либо просто в список функций. Делать класс не видел необходимости, потому что у меня не было потребности в динамическом связывании.
После рефакторинга
module Net = struct
let connect network a b =
network.(a).(b) <- 1;
network.(b).(a) <- 1;
()
let disconnect network a b =
network.(a).(b) <- 0;
network.(b).(a) <- 0;
()
let has_direct_connection network a b =
network.(a).(b) = 1
let find_any_connected_node network node_number =
let rec find num =
if num < Array.length network then
if network.(node_number).(num) = 1 then
num
else
find (num + 1)
else
node_number
in
find 0
let build nodes_number edges =
let network = Array.make_matrix nodes_number nodes_number 0 in
List.iter (fun (a, b) -> connect network a b) edges;
network
end
let read_network_config () =
let open Scanf in
let nodes_number, edges_number, gateway_number =
let init_data = read_line () in
sscanf init_data "%d %d %d" (fun n l e -> (n, l, e))
in
let rec read_edges = function
| 0 -> []
| num -> sscanf (read_line ()) "%d %d" (fun a b -> (a, b)) :: read_edges (num - 1)
in
let edges = read_edges edges_number in
let gateways =
Array.init gateway_number (fun i -> read_int ()) |> Array.to_list
in
nodes_number, edges, gateways
let fight_with_skynet network gateways =
let destroy_edge a b =
Net.disconnect network a b;
Printf.printf "%d %d\n" a b
in
let rec stop_skynet_agent () =
let skynet_agent_position = read_int () in
let agent_to_gateway_edges =
List.filter (fun gateway ->
Net.has_direct_connection network skynet_agent_position gateway)
gateways
in
let connected_node = match agent_to_gateway_edges with
| [] -> Net.find_any_connected_node network skynet_agent_position
| connected_gateway :: tl -> connected_gateway
in
destroy_edge skynet_agent_position connected_node;
stop_skynet_agent ()
in
stop_skynet_agent ()
let () =
let nodes_number, edges, gateways = read_network_config () in
let network = Net.build nodes_number edges in
fight_with_skynet network gateways
Заключение
В итоге у меня получилось решение, которое и задачу решало, и меня устраивало (во всяком случае, с текущем уровнем знаний в OCaml).
Недостаток решения задач на соревнованиях - нужен только результат, а не поддерживаемый код. Довольно сложно убедить себя в необходимости дорабатывать код, если все тесты пройдены, а возвращаться к коду вряд ли понадобится.
