Rosetta Code

Minimal steps down to 1: Difference between revisions

Page Discussion

Minimal steps down to 1 (view source)

Revision as of 08:59, 20 December 2019

1,797 bytes removed ,  4 years ago
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 allan possibleexample solutions areis to be listed. Interestingly, for the specified tasks only the starting points of 2 and 3 are processed without use of memoization.
 
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("SolutionsThere are ", length(solutions), " solutions for path fromof $startlength to $goal:"),
numsteps, " from $start to $goal.\nExample: ")
for (n, sol) in enumerate(solutions)
for step in solutions[1]
print(" Solution $n has $numsteps step(s): ")
forprint(step, step.out == 1 ? "\n\n" : in", sol")
print(step, step.out == 1 ? "\n\n" : ", ")
end
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.
 
SolutionsThere are 2 solutions for path of length 1 from 2 to 1:.
Example:
Solution 1 has 1 step(s): divide 2 yields 1
divide 2 yields 1
 
There are 1 solutions for path of length 1 from 3 to 1.
Solution 2 has 1 step(s): subtract 1 yields 1
Example:
divide 3 yields 1
 
SolutionsThere are 3 solutions for path of length 2 from 34 to 1:.
Example:
Solution 1 has 1 step(s): divide 3 yields 1
divide 2 yields 2, divide 2 yields 1
 
SolutionsThere are 3 solutions for path of length 3 from 45 to 1:.
Example:
Solution 1 has 2 step(s): divide 2 yields 2, divide 2 yields 1
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.
Solution 2 has 2 step(s): divide 2 yields 2, subtract 1 yields 1
Example:
divide 2 yields 3, divide 3 yields 1
 
There are 3 solutions for path of length 3 from 7 to 1.
Solution 3 has 2 step(s): subtract 1 yields 3, divide 3 yields 1
Example:
subtract 1 yields 6, divide 2 yields 3, divide 3 yields 1
 
SolutionsThere are 3 solutions for path of length 3 from 58 to 1:.
Example:
Solution 1 has 3 step(s): subtract 1 yields 4, divide 2 yields 2, divide 2 yields 1
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.
Solution 2 has 3 step(s): subtract 1 yields 4, divide 2 yields 2, subtract 1 yields 1
Example:
divide 3 yields 3, divide 3 yields 1
 
There are 1 solutions for path of length 3 from 10 to 1.
Solution 3 has 3 step(s): subtract 1 yields 4, subtract 1 yields 3, divide 3 yields 1
Example:
 
subtract 1 yields 9, divide 3 yields 3, divide 3 yields 1
Solutions for path from 6 to 1:
Solution 1 has 2 step(s): divide 2 yields 3, divide 3 yields 1
 
Solution 2 has 2 step(s): divide 3 yields 2, divide 2 yields 1
 
Solution 3 has 2 step(s): divide 3 yields 2, subtract 1 yields 1
 
Solutions for path from 7 to 1:
Solution 1 has 3 step(s): subtract 1 yields 6, divide 2 yields 3, divide 3 yields 1
 
Solution 2 has 3 step(s): subtract 1 yields 6, divide 3 yields 2, divide 2 yields 1
 
Solution 3 has 3 step(s): subtract 1 yields 6, divide 3 yields 2, subtract 1 yields 1
 
Solutions for path from 8 to 1:
Solution 1 has 3 step(s): divide 2 yields 4, divide 2 yields 2, divide 2 yields 1
 
Solution 2 has 3 step(s): divide 2 yields 4, divide 2 yields 2, subtract 1 yields 1
 
Solution 3 has 3 step(s): divide 2 yields 4, subtract 1 yields 3, divide 3 yields 1
 
Solutions for path from 9 to 1:
Solution 1 has 2 step(s): divide 3 yields 3, divide 3 yields 1
 
Solutions for path from 10 to 1:
Solution 1 has 3 step(s): 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.
 
SolutionsThere are 1 solutions for path of length 1 from 2 to 1:.
Example:
Solution 1 has 1 step(s): divide 2 yields 1
divide 2 yields 1
 
Solutions for path from 3 to 1:
Solution 1 has 1 step(s): divide 3 yields 1
 
Solution 2 has 1 step(s): subtract 2 yields 1
 
Solutions for path from 4 to 1:
Solution 1 has 2 step(s): divide 2 yields 2, divide 2 yields 1
 
Solution 2 has 2 step(s): subtract 2 yields 2, divide 2 yields 1
 
Solutions for path from 5 to 1:
Solution 1 has 2 step(s): subtract 2 yields 3, divide 3 yields 1
 
Solution 2 has 2 step(s): subtract 2 yields 3, subtract 2 yields 1
 
Solutions for path from 6 to 1:
Solution 1 has 2 step(s): divide 2 yields 3, divide 3 yields 1
 
Solution 2 has 2 step(s): divide 2 yields 3, subtract 2 yields 1
 
Solution 3 has 2 step(s): divide 3 yields 2, divide 2 yields 1
 
Solutions for path from 7 to 1:
Solution 1 has 3 step(s): subtract 2 yields 5, subtract 2 yields 3, divide 3 yields 1
 
Solution 2 has 3 step(s): subtract 2 yields 5, subtract 2 yields 3, subtract 2 yields 1
 
Solutions for path from 8 to 1:
Solution 1 has 3 step(s): divide 2 yields 4, divide 2 yields 2, divide 2 yields 1
 
There are 2 solutions for path of length 1 from 3 to 1.
Solution 2 has 3 step(s): divide 2 yields 4, subtract 2 yields 2, divide 2 yields 1
Example:
divide 3 yields 1
 
There are 2 solutions for path of length 2 from 4 to 1.
Solution 3 has 3 step(s): subtract 2 yields 6, divide 2 yields 3, divide 3 yields 1
Example:
divide 2 yields 2, divide 2 yields 1
 
There are 2 solutions for path of length 2 from 5 to 1.
Solution 4 has 3 step(s): subtract 2 yields 6, divide 2 yields 3, subtract 2 yields 1
Example:
subtract 2 yields 3, divide 3 yields 1
 
There are 3 solutions for path of length 2 from 6 to 1.
Solution 5 has 3 step(s): subtract 2 yields 6, divide 3 yields 2, divide 2 yields 1
Example:
divide 2 yields 3, divide 3 yields 1
 
SolutionsThere are 2 solutions for path of length 3 from 97 to 1:.
Example:
Solution 1 has 2 step(s): divide 3 yields 3, divide 3 yields 1
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.
Solution 2 has 2 step(s): divide 3 yields 3, subtract 2 yields 1
Example:
divide 2 yields 4, divide 2 yields 2, divide 2 yields 1
 
SolutionsThere are 2 solutions for path of length 2 from 109 to 1:.
Example:
Solution 1 has 3 step(s): divide 2 yields 5, subtract 2 yields 3, divide 3 yields 1
divide 3 yields 3, divide 3 yields 1
 
There are 2 solutions for path of length 3 from 10 to 1.
Solution 2 has 3 step(s): divide 2 yields 5, subtract 2 yields 3, subtract 2 yields 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]
Wherrera
4,108

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/296764"