149 lines
4.3 KiB
Batchfile
149 lines
4.3 KiB
Batchfile
:: Stable Marriage Problem in Rosetta Code
|
|
:: Batch File Implementation
|
|
|
|
@echo off
|
|
setlocal enabledelayedexpansion
|
|
|
|
:: Initialization (Index Starts in 0)
|
|
set "male=abe bob col dan ed fred gav hal ian jon"
|
|
set "femm=abi bea cath dee eve fay gay hope ivy jan"
|
|
|
|
set "abe[]=abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay"
|
|
set "bob[]=cath, hope, abi, dee, eve, fay, bea, jan, ivy, gay"
|
|
set "col[]=hope, eve, abi, dee, bea, fay, ivy, gay, cath, jan"
|
|
set "dan[]=ivy, fay, dee, gay, hope, eve, jan, bea, cath, abi"
|
|
set "ed[]=jan, dee, bea, cath, fay, eve, abi, ivy, hope, gay"
|
|
set "fred[]=bea, abi, dee, gay, eve, ivy, cath, jan, hope, fay"
|
|
set "gav[]=gay, eve, ivy, bea, cath, abi, dee, hope, jan, fay"
|
|
set "hal[]=abi, eve, hope, fay, ivy, cath, jan, bea, gay, dee"
|
|
set "ian[]=hope, cath, dee, gay, bea, abi, fay, ivy, jan, eve"
|
|
set "jon[]=abi, fay, jan, gay, eve, bea, dee, cath, ivy, hope"
|
|
|
|
set "abi[]=bob, fred, jon, gav, ian, abe, dan, ed, col, hal"
|
|
set "bea[]=bob, abe, col, fred, gav, dan, ian, ed, jon, hal"
|
|
set "cath[]=fred, bob, ed, gav, hal, col, ian, abe, dan, jon"
|
|
set "dee[]=fred, jon, col, abe, ian, hal, gav, dan, bob, ed"
|
|
set "eve[]=jon, hal, fred, dan, abe, gav, col, ed, ian, bob"
|
|
set "fay[]=bob, abe, ed, ian, jon, dan, fred, gav, col, hal"
|
|
set "gay[]=jon, gav, hal, fred, bob, abe, col, ed, dan, ian"
|
|
set "hope[]=gav, jon, bob, abe, ian, dan, hal, ed, col, fred"
|
|
set "ivy[]=ian, col, hal, gav, fred, bob, abe, ed, jon, dan"
|
|
set "jan[]=ed, hal, gav, abe, bob, jon, col, ian, fred, dan"
|
|
|
|
rem variable notation:
|
|
rem <boy>{<index>} = <girl>
|
|
rem <boy>[<girl>] = <index>
|
|
for %%M in (%male%) do (
|
|
set cnt=0
|
|
for %%. in (!%%M[]!) do (
|
|
set "%%M{!cnt!}=%%."
|
|
set "%%M[%%.]=!cnt!"
|
|
set /a cnt+=1
|
|
)
|
|
)
|
|
for %%F in (%femm%) do (
|
|
set cnt=0
|
|
for %%. in (!%%F[]!) do (
|
|
set "%%F[%%.]=!cnt!"
|
|
set /a cnt+=1
|
|
)
|
|
)
|
|
|
|
:: The Main Thing
|
|
echo(HISTORY:
|
|
call :stableMatching
|
|
echo(
|
|
echo(NEWLYWEDS:
|
|
call :display
|
|
echo(
|
|
call :isStable
|
|
echo(
|
|
echo(What if ed and hal swapped?
|
|
call :swapper ed hal
|
|
echo(
|
|
echo(NEW-NEWLYWEDS:
|
|
call :display
|
|
echo(
|
|
call :isStable
|
|
pause>nul
|
|
exit /b 0
|
|
|
|
:: The Algorithm
|
|
:stableMatching
|
|
set "free_men=%male%"
|
|
set "free_fem=%femm%"
|
|
for %%M in (%male%) do set "%%M_tried=0"
|
|
|
|
:match_loop
|
|
if "%free_men%"=="" goto :EOF
|
|
for /f "tokens=1* delims= " %%m in ("%free_men%") do (
|
|
rem get woman not yet proposed to, but if man's tries exceeds the number
|
|
rem of women (poor guy), he starts again to his most preferred woman (#0).
|
|
for /f %%x in ("!%%m_tried!") do if not defined %%m{%%x} (
|
|
set "%%m_tried=0" & set "w=!%%m{0}!"
|
|
) else set "w=!%%m{%%x}!"
|
|
set "m=%%m"
|
|
|
|
for /f %%x in ("free_fem:!w!=") do (
|
|
if not "!free_fem!"=="!%%x!" (
|
|
rem accept because !w! (the woman) is free
|
|
set "!m!_=!w!" & set "!w!_=!m!"
|
|
set "free_men=%%n" & set "free_fem=!%%x!"
|
|
echo( !w! ACCEPTED !m!.
|
|
) else (
|
|
rem here, !w! already has a pair; get his name and rank.
|
|
for /f %%. in ("!w!") do set "cur_man=!%%._!"
|
|
for /f %%. in ("!w![!cur_man!]") do set "rank_cur=!%%.!"
|
|
rem also, get the rank of current proposing man.
|
|
for /f %%. in ("!w![!m!]") do set "rank_new=!%%.!"
|
|
|
|
if !rank_new! lss !rank_cur! (
|
|
rem here, !w! will leave her pair, and choose !m!.
|
|
set "free_men=%%n !cur_man!"
|
|
echo( !w! LEFT !cur_man!.
|
|
rem pair them up now!
|
|
set "!m!_=!w!" & set "!w!_=!m!"
|
|
echo( !w! ACCEPTED !m!.
|
|
)
|
|
)
|
|
)
|
|
set /a "!m!_tried+=1"
|
|
)
|
|
goto :match_loop
|
|
|
|
:: Output the Couples
|
|
:display
|
|
for %%S in (%femm%) do echo. %%S and !%%S_!.
|
|
goto :EOF
|
|
|
|
:: Stability Checking
|
|
:isStable
|
|
for %%f in (%femm%) do (
|
|
for %%g in (%male%) do (
|
|
for /f %%. in ("%%f[!%%f_!]") do set "girl_cur=!%%.!"
|
|
set "girl_aboy=!%%f[%%g]!"
|
|
for /f %%. in ("%%g[!%%g_!]") do set "boy_cur=!%%.!"
|
|
set "boy_agirl=!%%g[%%f]!"
|
|
|
|
if !boy_cur! gtr !boy_agirl! (
|
|
if !girl_cur! gtr !girl_aboy! (
|
|
echo(STABILITY = FALSE.
|
|
echo(%%f and %%g would rather be together than their current partners.
|
|
goto :EOF
|
|
)
|
|
)
|
|
)
|
|
)
|
|
echo(STABILITY = TRUE.
|
|
goto :EOF
|
|
|
|
:: Swapper
|
|
:swapper
|
|
set %~1.tmp=!%~1_!
|
|
set %~2.tmp=!%~2_!
|
|
set "%~1_=!%~2.tmp!"
|
|
set "%~2_=!%~1.tmp!"
|
|
set "!%~1.tmp!_=%~2"
|
|
set "!%~2.tmp!_=%~1"
|
|
goto :EOF
|