Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
{
"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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment