Minimal steps down to 1: Difference between revisions
m
→{{header|Julia}}
m (Orthographic lint) |
|||
Line 187:
=={{header|Julia}}==
This is a non-recursive solution that is memoized for the count-only portions of the task, but not memoized when
Implemented as a generic solution for any functions acting on an integer and taking any range of second arguments, with the goal solution also specifiable. To do so generically, it is also necessary to specify a failure condition, which in the example is falling below 1.
<lang julia>import Base.print
struct Action{T}
f::Function
i::T
end
struct ActionOutcome{T}
act::Action{T}
out::T
end
Base.print(io::IO, ao::ActionOutcome) = print(io, "$(ao.act.f) $(ao.act.i) yields $(ao.out)")
memoized = Dict{Int, Int}()
function findshortest(start, goal, fails, actions, verbose=true, maxsteps=100000)
solutions, numsteps = Vector{Vector{ActionOutcome}}(), 0
Line 239:
end
if verbose
println("
numsteps, " from $start to $goal.\nExample: ")
for step in solutions[1]
end
end
Line 250 ⟶ 248:
return numsteps
end
failed(n) = n < 1
const divisors = [2, 3]
divide(n, x) = begin q, r = divrem(n, x); r == 0 ? q : -1 end
const subtractors1, subtractors2 = [1], [2]
subtract(n, x) = n - x
actions1 = Dict(divide => divisors, subtract => subtractors1)
actions2 = Dict(divide => divisors, subtract => subtractors2)
function findmaxshortest(g, fails, acts, maxn)
stepcounts = [findshortest(n, g, fails, acts, false) for n in 1:maxn]
Line 268 ⟶ 266:
println("There are $(length(maxstepnums)) with $maxs steps for start between 1 and $maxn: ", maxstepnums)
end
function teststeps(g, fails, acts, maxes)
println("\nWith goal $g, divisors $(acts[divide]), subtractors $(acts[subtract]):")
Line 278 ⟶ 276:
end
end
teststeps(1, failed, actions1, [2000, 20000, 50000])
empty!(memoized)
Line 287 ⟶ 285:
For start of 1, no steps needed.
Example:
divide 2 yields 1
There are 1 solutions for path of length 1 from 3 to 1.
Example:
divide 3 yields 1
Example:
divide 2 yields 2, divide 2 yields 1
Example:
subtract 1 yields 4, divide 2 yields 2, divide 2 yields 1
There are 3 solutions for path of length 2 from 6 to 1.
Example:
divide 2 yields 3, divide 3 yields 1
There are 3 solutions for path of length 3 from 7 to 1.
Example:
subtract 1 yields 6, divide 2 yields 3, divide 3 yields 1
Example:
divide 2 yields 4, divide 2 yields 2, divide 2 yields 1
There are 1 solutions for path of length 2 from 9 to 1.
Example:
divide 3 yields 3, divide 3 yields 1
There are 1 solutions for path of length 3 from 10 to 1.
Example:
subtract 1 yields 9, divide 3 yields 3, divide 3 yields 1
There are 16 with 14 steps for start between 1 and 2000: [863, 1079, 1295, 1439, 1511, 1583, 1607, 1619, 1691, 1727, 1823, 1871, 1895, 1907, 1919, 1943]
Line 343 ⟶ 328:
For start of 1, no steps needed.
Example:
divide 2 yields 1
There are 2 solutions for path of length 1 from 3 to 1.
Example:
divide 3 yields 1
There are 2 solutions for path of length 2 from 4 to 1.
Example:
divide 2 yields 2, divide 2 yields 1
There are 2 solutions for path of length 2 from 5 to 1.
Example:
subtract 2 yields 3, divide 3 yields 1
There are 3 solutions for path of length 2 from 6 to 1.
Example:
divide 2 yields 3, divide 3 yields 1
Example:
subtract 2 yields 5, subtract 2 yields 3, divide 3 yields 1
There are 5 solutions for path of length 3 from 8 to 1.
Example:
divide 2 yields 4, divide 2 yields 2, divide 2 yields 1
Example:
divide 3 yields 3, divide 3 yields 1
There are 2 solutions for path of length 3 from 10 to 1.
Example:
divide 2 yields 5, subtract 2 yields 3, divide 3 yields 1
There are 1 with 17 steps for start between 1 and 2000: [1699]
|