Skip to content

Instantly share code, notes, and snippets.

# mrkn/speee_vaccine_assignment.ipynb Secret

Created Jun 25, 2021
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
 { "cells": [ { "cell_type": "markdown", "id": "945c9be3", "metadata": {}, "source": [ "# Model definition" ] }, { "cell_type": "code", "execution_count": 1, "id": "1c91fbde", "metadata": {}, "outputs": [], "source": [ "mutable struct Model\n", " # The number of people\n", " M :: Int\n", "\n", " # The number of time frames\n", " N :: Int\n", "\n", " # Person labels\n", " people :: Vector{String}\n", "\n", " # Time frame labels\n", " time_frames :: Vector{String}\n", "\n", " # The forbidden matrix\n", " # If the (i, j)-element is 1, the i-th person cannot be assigned in the j-th time frame\n", " forbidden_matrix :: BitMatrix\n", "\n", " # Capacity of each time frame\n", " capacity :: Vector{Int}\n", "\n", " # People assignments\n", " assignments :: Vector{Int}\n", " \n", " # Time frame population\n", " population :: Vector{Int}\n", "\n", " function Model(M::Int, N::Int)\n", " people = Vector{String}(undef, M)\n", " time_frames = Vector{String}(undef, N)\n", " forbidden_matrix = zeros(Bool, (M, N))\n", " capacity = zeros(Int, N)\n", " assignments = zeros(Int, M)\n", " population = zeros(Int, N)\n", " new(\n", " M, N,\n", " people,\n", " time_frames,\n", " forbidden_matrix,\n", " capacity,\n", " assignments,\n", " population\n", " )\n", " end\n", "end" ] }, { "cell_type": "code", "execution_count": 2, "id": "6c814f70", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "check (generic function with 1 method)" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function Base.size(model::Model)\n", " (model.M, model.N)\n", "end\n", "\n", "function forbid!(model::Model, i, j)\n", " model.forbidden_matrix[i, j] = 1\n", "end\n", "\n", "function permit!(model::Model, i, j)\n", " model.forbidden_matrix[i, j] = 0\n", "end\n", "\n", "isassigned(model::Model, i) = model.assignments[i] != 0\n", "isfull(model::Model, j) = model.population[j] == model.capacity[j]\n", "isforbidden(model::Model, i, j) = model.forbidden_matrix[i, j]\n", "isassignable(model::Model, i, j) = !isforbidden(model, i, j) && !isfull(model, j)\n", "\n", "function assign!(model::Model, i, j)\n", " if isassignable(model, i, j)\n", " model.assignments[i] = j\n", " model.population[j] += 1\n", " true\n", " else\n", " false\n", " end\n", "end\n", "\n", "function reset!(model::Model)\n", " fill!(model.assignments, 0)\n", " fill!(model.population, 0)\n", "end\n", "\n", "function check(model::Model)\n", " valid = true\n", " for (i, j) in enumerate(model.assignments)\n", " if isforbidden(model, i, j)\n", " valid = false\n", " println(\"Assigned to forbidden time frame (\$(i), \$(j))\")\n", " end\n", " end\n", " valid\n", "end" ] }, { "cell_type": "code", "execution_count": 3, "id": "798ec201", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "solve! (generic function with 1 method)" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Tentative algorithm to find the solution by greedy-like algorithm\n", "function solve!(X :: Model)\n", " reset!(X)\n", "\n", " # The number of forbidden time frames\n", " n_forbiddens = vec(sum(X.forbidden_matrix, dims = 2))\n", "\n", " # Sort people in descendant order of the number of forbidden time frames\n", " sorted_people = sortperm(n_forbiddens, rev = true)\n", "\n", " # Sort time frames in ascending order of the capacity\n", " sorted_frames = sortperm(X.capacity)\n", "\n", " while sum(sorted_people) > 0 && sum(sorted_frames) > 0\n", " for (idx_j, j) in enumerate(sorted_frames)\n", " j == 0 && continue\n", "\n", " for (idx_i, i) in enumerate(sorted_people)\n", " i == 0 && continue\n", "\n", " if isassignable(X, i, j)\n", " assign!(X, i, j)\n", " sorted_people[idx_i] = 0\n", " break\n", " end\n", " end\n", "\n", " if isfull(X, j)\n", " sorted_frames[idx_j] = 0\n", " end\n", " end\n", " end\n", "end" ] }, { "cell_type": "markdown", "id": "6bcc2196", "metadata": {}, "source": [ "# Simple testing" ] }, { "cell_type": "code", "execution_count": 4, "id": "9829cf22", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "model = Model(10, 3)\n", "forbid!(model, 1, 1)\n", "forbid!(model, 3, 2)\n", "forbid!(model, 4, 2)\n", "forbid!(model, 4, 3)\n", "forbid!(model, 7, 1)\n", "forbid!(model, 9, 3)\n", "model.capacity[1] = 3\n", "model.capacity[2] = 4\n", "model.capacity[3] = 3" ] }, { "cell_type": "code", "execution_count": 5, "id": "0968b437", "metadata": {}, "outputs": [], "source": [ "solve!(model)" ] }, { "cell_type": "code", "execution_count": 6, "id": "724b79cf", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "10-element Vector{Int64}:\n", " 3\n", " 3\n", " 1\n", " 1\n", " 1\n", " 3\n", " 2\n", " 2\n", " 2\n", " 2" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "model.assignments" ] }, { "cell_type": "markdown", "id": "6d6c5f92", "metadata": {}, "source": [ "# Data loading" ] }, { "cell_type": "code", "execution_count": 7, "id": "63841fab", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "show_assignment (generic function with 1 method)" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "using CSV\n", "\n", "function match_timeframename(s)\n", " match(r\"(\\d+)年(\\d+)月(\\d+)日\\(.+\\)\\s*(\\d+):(\\d+)～\\s*(\\d+):(\\d+)\", s)\n", "end\n", "\n", "function Model(filename::String)\n", " people = String[]\n", " forbidden_frames = Dict{Int, Vector{Int}}()\n", " time_frames = Dict{String, Int}()\n", "\n", " raw_data = CSV.File(filename; skipto=2)\n", " for (i, row) in enumerate(raw_data)\n", " i < 3 && continue\n", " id = row[2]\n", " push!(people, id)\n", " people_index = length(people)\n", "\n", " frames = split(row[3], \",\")\n", " for frame in frames\n", " frame = strip(frame)\n", " if frame == \"どの日時も参加可能\"\n", " continue\n", " elseif match_timeframename(frame) !== nothing\n", " if haskey(time_frames, frame)\n", " frame_index = time_frames[frame]\n", " else\n", " frame_index = length(time_frames) + 1\n", " time_frames[frame] = frame_index\n", " end\n", " if !haskey(forbidden_frames, people_index)\n", " forbidden_frames[people_index] = Int[]\n", " end\n", " push!(forbidden_frames[people_index], frame_index)\n", " else\n", " println(\"XXX \$(id): \$(frame) XXX\")\n", " end\n", " end\n", " end\n", "\n", " M = length(people)\n", " N = length(time_frames)\n", " model = Model(M, N)\n", " model.people[:] = people\n", " model.time_frames[:] = collect(keys(time_frames))\n", "\n", " # Initialize forbidden matrix\n", " for (i, frame_indices) in forbidden_frames\n", " for j in frame_indices\n", " forbid!(model, i, j)\n", " end\n", " end\n", "\n", " return model\n", "end\n", "\n", "function start_datetime(s)\n", " m = match_timeframename(s)\n", " parse.(Int, (m[1], m[2], m[3], m[4], m[5]))\n", "end\n", "\n", "function show_assignment(model::Model)\n", " order = sortperm(model.time_frames, by=start_datetime)\n", " for (j, frame) in enumerate(model.time_frames[order])\n", " people_index = findall(model.assignments .== j)\n", " println(\"\$(frame) [\$(join(model.people[people_index], \", \"))]\")\n", " end\n", "end" ] }, { "cell_type": "markdown", "id": "e1836087", "metadata": {}, "source": [ "# Test by test data" ] }, { "cell_type": "code", "execution_count": 8, "id": "d7864e95", "metadata": { "scrolled": false }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "┌ Warning: thread = 1 warning: only found 3 / 4 columns around data row: 139. Filling remaining columns with `missing`\n", "└ @ CSV /home/mrkn/.julia/packages/CSV/Zl2ww/src/file.jl:612\n" ] }, { "data": { "text/plain": [ "Model(136, 24, [\"1\", \"3\", \"6\", \"9\", \"12\", \"13\", \"24\", \"25\", \"26\", \"47\" … \"189\", \"190\", \"191\", \"192\", \"193\", \"194\", \"195\", \"196\", \"197\", \"198\"], [\"2021年1月5日(火)11:30～12:00\", \"2021年1月6日(水)14:30～15:00\", \"2021年1月5日(火) 9:00～9:30\", \"2021年1月5日(火)11:00～11:30\", \"2021年1月6日(水) 9:30～10:00\", \"2021年1月6日(水)10:30～11:00\", \"2021年1月5日(火)12:00～12:30\", \"2021年1月6日(水)12:30～13:00\", \"2021年1月5日(火) 12:30～13:00\", \"2021年1月5日(火) 9:30～10:00\" … \"2021年1月6日(水)13:30～14:00\", \"2021年1月5日(火)10:30～11:00\", \"2021年1月5日(火)13:00～13:30\", \"2021年1月5日(火)14:00～14:30\", \"2021年1月5日(火)10:00～10:30\", \"2021年1月5日(火)14:30～15:00\", \"2021年1月5日(火)13:30～14:00\", \"2021年1月6日(水)12:00～12:30\", \"2021年1月6日(水)11:30～12:00\", \"2021年1月6日(水)11:00～11:30\"], Bool[0 0 … 0 0; 0 0 … 0 0; … ; 1 1 … 0 0; 0 0 … 0 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0 … 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0 … 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0 … 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "model = Model(\"vaccine_assignment_test.csv\")" ] }, { "cell_type": "code", "execution_count": 9, "id": "db11b99c", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(136, 24)" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "size(model)" ] }, { "cell_type": "code", "execution_count": 10, "id": "1900e156", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "24-element Vector{Int64}:\n", " 6\n", " 6\n", " 6\n", " 6\n", " 6\n", " 6\n", " 6\n", " 6\n", " 6\n", " 6\n", " 6\n", " 6\n", " 6\n", " 6\n", " 6\n", " 6\n", " 6\n", " 6\n", " 6\n", " 6\n", " 6\n", " 6\n", " 6\n", " 6" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "fill!(model.capacity, 6)" ] }, { "cell_type": "code", "execution_count": 11, "id": "78f950aa", "metadata": {}, "outputs": [], "source": [ "solve!(model)" ] }, { "cell_type": "code", "execution_count": 12, "id": "e7bfface", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "check(model)" ] }, { "cell_type": "code", "execution_count": 13, "id": "3da8ede4", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2021年1月5日(火) 9:00～9:30 [98, 124, 157, 166, 167, 176]\n", "2021年1月5日(火) 9:30～10:00 [50, 99, 110, 132, 144, 158]\n", "2021年1月5日(火)10:00～10:30 [94, 97, 101, 103, 161, 186]\n", "2021年1月5日(火)10:30～11:00 [13, 104, 120, 153, 163, 184]\n", "2021年1月5日(火)11:00～11:30 [96, 106, 137, 146, 164, 168]\n", "2021年1月5日(火)11:30～12:00 [49, 107, 133, 138, 154, 170]\n", "2021年1月5日(火)12:00～12:30 [6, 90, 108, 159, 171, 174]\n", "2021年1月5日(火) 12:30～13:00 [12, 26, 109, 173, 177, 182]\n", "2021年1月5日(火)13:00～13:30 [24, 55, 111, 180, 183, 187]\n", "2021年1月5日(火)13:30～14:00 [60, 95, 115, 185, 192, 194]\n", "2021年1月5日(火)14:00～14:30 [91, 100, 105, 117, 181, 188]\n", "2021年1月5日(火)14:30～15:00 [48, 122, 140, 148, 151, 190]\n", "2021年1月6日(水) 9:00～ 9:30 [53, 64, 102, 125, 143, 191]\n", "2021年1月6日(水) 9:30～10:00 [1, 89, 92, 93, 128, 193]\n", "2021年1月6日(水)10:00～10:30 [3, 56, 116, 121, 131, 195]\n", "2021年1月6日(水)10:30～11:00 [25, 61, 113, 134, 145, 198]\n", "2021年1月6日(水)11:00～11:30 [9, 47, 54, 135, 162]\n", "2021年1月6日(水)11:30～12:00 [51, 123, 126, 139, 172]\n", "2021年1月6日(水)12:00～12:30 [52, 127, 147, 169, 175]\n", "2021年1月6日(水)12:30～13:00 [57, 119, 142, 149, 178]\n", "2021年1月6日(水)13:00～13:30 [58, 130, 141, 150, 179]\n", "2021年1月6日(水)13:30～14:00 [59, 136, 152, 165, 189]\n", "2021年1月6日(水)14:00～14:30 [62, 112, 155, 196, 197]\n", "2021年1月6日(水)14:30～15:00 [63, 114, 118, 156, 160]\n" ] } ], "source": [ "show_assignment(model)" ] }, { "cell_type": "code", "execution_count": null, "id": "a7d46bd1", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Julia 1.6.1", "language": "julia", "name": "julia-1.6" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.6.1" } }, "nbformat": 4, "nbformat_minor": 5 }
to join this conversation on GitHub. Already have an account? Sign in to comment