The program generates random choices for nine different levels of the general problem.
I spent some time running the simulations to figure out the minimum value of MAX for each problem.
# shoes.awk - simulate putting on socks, shoes, and laces via simulation.
# shoes is Copyright Daniel K. Allen, 2018-2026.
# All rights reserved.
#
# 29 Jun 2026 - Created by Dan Allen. (N/N MCD IF)
# 21 Jul 2026 - Added pants & untying variations; now 8 different problems.
# 23 Jul 2026 - Confirmed 9072 for n = 10 by 1 million reps. (3hr w/Mac Studio!)
# 26 Jul 2026 - Added socks and shoes as n = 1.
# 27 Jul 2026 - 180x speedup by removing SHA1 digest hash; need for debug=1 gone.
#
# Usage: awk -f shoes.awk n
# Outputs a solution path as 1s and 0s.
# Usage: awk -f shoes awk n | sort -u | tt -n 1
# This numbers the unique solution paths.
# Usage: awk -f shoes awk n | topten -c
# This looks at path frequencies to help determine good values of MAX.
# Current heuristic: after 10 runs the minimum count should be five.
#
# ToDo: model the choices algorithmically.
#
function Clear() { mat=pants=pantL=pantR=untieL=untieR=sockL=shoeL=laceL=sockR=shoeR=laceR=0 }
function Steps4() { return sockL+shoeL+sockR+shoeR }
function Steps6() { return sockL+shoeL+laceL+sockR+shoeR+laceR }
function Steps7() { return pants+sockL+shoeL+laceL+sockR+shoeR+laceR }
function Steps8() { return pantL+pantR+sockL+shoeL+laceL+sockR+shoeR+laceR }
function Steps10() { return pantL+pantR+untieL+untieR+sockL+shoeL+laceL+sockR+shoeR+laceR }
function Encode4() { return sockL shoeL sockR shoeR }
function Encode6() { return sockL shoeL laceL sockR shoeR laceR }
function Encode7() { return pants sockL shoeL laceL sockR shoeR laceR }
function Encode8() { return pantL pantR sockL shoeL laceL sockR shoeR laceR }
function Encode10() { return pantL pantR sockL untieL shoeL laceL sockR untieR shoeR laceR }
BEGIN {
srand()
if (ARGC == 1) {
print "# Usage: awk -f shoes.awk n | sort -u | tt -n 1"
print "# n = 1 6 ways: sock, shoe"
print "# n = 2 20 ways: sock, shoe, knot"
print "# n = 3 52 ways: pants & socks, then shoes, knots"
print "# n = 4 70 ways: pant leg, sock, shoe, knot"
print "# n = 5 140 ways: sock, shoe, knot; pants any time"
print "# n = 6 252 ways: pant leg, sock, untie, shoe, knot"
print "# n = 7 280 ways: pant legs & socks, then shoes, knots"
print "# n = 8 1120 ways: sock, shoe, knot; pant legs any time"
print "# n = 10 9072 ways: pant leg & sock & untie, then shoe, knot"
}
if (ARGV[1] == 1) { # 4! /(2!*2!) = 6
THINGS = 4
MAX = 100 # returns 6 different permutations
for (n = 1; n <= MAX; n++) {
Clear()
while (Steps4() < THINGS) {
i = int(THINGS*rand)
a = Steps6()
if (i == 0 && !sockL) sockL = 1
if (i == 1 && sockL) shoeL = 1
if (i == 2 && !sockR) sockR = 1
if (i == 3 && sockR) shoeR = 1
b = Steps4()
if (a != b) save[mat++] = Encode4()
}
for (r = 0; r < THINGS; r++) printf("%s.", save[r])
printf("\n")
}
}
if (ARGV[1] == 2) { # 6! /(3!*3!) = 20
THINGS = 6
MAX = 400 # returns 20 different permutations
for (n = 1; n <= MAX; n++) {
Clear()
while (Steps6() < THINGS) {
i = int(THINGS*rand)
a = Steps6()
if (i == 0 && !sockL) sockL = 1
if (i == 1 && sockL) shoeL = 1
if (i == 2 && shoeL) laceL = 1
if (i == 3 && !sockR) sockR = 1
if (i == 4 && sockR) shoeR = 1
if (i == 5 && shoeR) laceR = 1
b = Steps6()
if (a != b) save[mat++] = Encode6()
}
for (r = 0; r < THINGS; r++) printf("%s.", save[r])
printf("\n")
}
}
if (ARGV[1] == 3) { # no formula determined yet = 52
THINGS = 7
MAX = 2000 # returns 52 different permutations
for (n = 1; n <= MAX; n++) {
Clear()
while (Steps7() < THINGS) {
i = int(THINGS*rand)
a = Steps7()
if (i == 0 && !pants) pants = 1
if (i == 1 && !sockL) sockL = 1
if (i == 2 && sockL && pants) shoeL = 1
if (i == 3 && shoeL) laceL = 1
if (i == 4 && !sockR) sockR = 1
if (i == 5 && sockR && pants) shoeR = 1
if (i == 6 && shoeR) laceR = 1
b = Steps7()
if (a != b) save[mat++] = Encode7()
}
for (r = 0; r < THINGS; r++) printf("%s.", save[r])
printf("\n")
}
}
if (ARGV[1] == 4) { # 8! /(4!*4!) = 70
THINGS = 8
MAX = 2000 # returns 70 different permutations
for (n = 1; n <= MAX; n++) {
Clear()
while (Steps8() < THINGS) {
i = int(THINGS*rand)
a = Steps8()
if (i == 0 && !pantL) pantL = 1
if (i == 1 && !pantR) pantR = 1
if (i == 2 && pantL) sockL = 1
if (i == 3 && pantR) sockR = 1
if (i == 4 && sockL) shoeL = 1
if (i == 5 && sockR) shoeR = 1
if (i == 6 && shoeL) laceL = 1
if