Minimal steps down to 1: Difference between revisions
Content deleted Content added
m →{{header|Go}}: A bit tidier output. |
julia example |
||
Line 185: | Line 185: | ||
[45925] |
[45925] |
||
</pre> |
</pre> |
||
=={{header|Julia}}== |
|||
Non-recursive, non-memoized. 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 falure condition, which in the example |
|||
is falling below 1. |
|||
<lang julia>import Base.print |
|||
struct Action |
|||
f::Function |
|||
i::Int |
|||
end |
|||
struct ActionOutcome |
|||
act::Action |
|||
out::Int |
|||
end |
|||
function Base.print(io::IO, ao::ActionOutcome) |
|||
print(io, "$(ao.act.f) $(ao.act.i) yields $(ao.out)") |
|||
end |
|||
function findshortest(start, goal, fails, actions, verbose=true, maxsteps=100000) |
|||
solutions, numsteps = Vector{Vector{ActionOutcome}}(), 0 |
|||
seqs = [ActionOutcome[ActionOutcome(Action(div, 0), start)]] |
|||
if start == goal |
|||
verbose && println("For start of $start, no steps needed.\n") |
|||
return 0 |
|||
end |
|||
while numsteps < maxsteps && isempty(solutions) |
|||
newsequences = Vector{Vector{ActionOutcome}}() |
|||
numsteps += 1 |
|||
for seq in seqs, (act, arr) in actions, x in arr |
|||
result = act(seq[end].out, x) |
|||
if !fails(result) |
|||
newactionseq = vcat(seq, ActionOutcome(Action(act, x), result)) |
|||
numsteps == 1 && popfirst!(newactionseq) |
|||
if result == goal |
|||
push!(solutions, newactionseq) |
|||
else |
|||
push!(newsequences, newactionseq) |
|||
end |
|||
end |
|||
end |
|||
seqs = newsequences |
|||
end |
|||
if verbose |
|||
println("Solutions for path from $start to $goal:") |
|||
for (n, sol) in enumerate(solutions) |
|||
print(" Solution $n has $numsteps step(s): ") |
|||
for step in sol |
|||
print(step, step.out == 1 ? "\n\n" : ", ") |
|||
end |
|||
end |
|||
end |
|||
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] |
|||
maxs = maximum(stepcounts) |
|||
maxstepnums = findall(x -> x == maxs, stepcounts) |
|||
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]):") |
|||
for n in 1:10 |
|||
findshortest(n, g, fails, acts) |
|||
end |
|||
for maxn in maxes |
|||
findmaxshortest(g, fails, acts, maxn) |
|||
end |
|||
end |
|||
teststeps(1, failed, actions1, [2000, 20000]) |
|||
teststeps(1, failed, actions2, [2000, 20000]) |
|||
</lang>{{out}} |
|||
<pre> |
|||
With goal 1, divisors [2, 3], subtractors [1]: |
|||
For start of 1, no steps needed. |
|||
Solutions for path from 2 to 1: |
|||
Solution 1 has 1 step(s): divide 2 yields 1 |
|||
Solution 2 has 1 step(s): subtract 1 yields 1 |
|||
Solutions for path from 3 to 1: |
|||
Solution 1 has 1 step(s): divide 3 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): divide 2 yields 2, subtract 1 yields 1 |
|||
Solution 3 has 2 step(s): subtract 1 yields 3, divide 3 yields 1 |
|||
Solutions for path from 5 to 1: |
|||
Solution 1 has 3 step(s): subtract 1 yields 4, divide 2 yields 2, divide 2 yields 1 |
|||
Solution 2 has 3 step(s): subtract 1 yields 4, divide 2 yields 2, subtract 1 yields 1 |
|||
Solution 3 has 3 step(s): subtract 1 yields 4, subtract 1 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] |
|||
There are 5 with 20 steps for start between 1 and 20000: [12959, 15551, 17279, 18143, 19439] |
|||
With goal 1, divisors [2, 3], subtractors [2]: |
|||
For start of 1, no steps needed. |
|||
Solutions for path from 2 to 1: |
|||
Solution 1 has 1 step(s): 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 |
|||
Solution 2 has 3 step(s): divide 2 yields 4, subtract 2 yields 2, divide 2 yields 1 |
|||
Solution 3 has 3 step(s): subtract 2 yields 6, divide 2 yields 3, divide 3 yields 1 |
|||
Solution 4 has 3 step(s): subtract 2 yields 6, divide 2 yields 3, subtract 2 yields 1 |
|||
Solution 5 has 3 step(s): subtract 2 yields 6, divide 3 yields 2, divide 2 yields 1 |
|||
Solutions for path from 9 to 1: |
|||
Solution 1 has 2 step(s): divide 3 yields 3, divide 3 yields 1 |
|||
Solution 2 has 2 step(s): divide 3 yields 3, subtract 2 yields 1 |
|||
Solutions for path from 10 to 1: |
|||
Solution 1 has 3 step(s): divide 2 yields 5, subtract 2 yields 3, divide 3 yields 1 |
|||
Solution 2 has 3 step(s): divide 2 yields 5, subtract 2 yields 3, subtract 2 yields 1 |
|||
There are 1 with 17 steps for start between 1 and 2000: [1699] |
|||
There are 1 with 24 steps for start between 1 and 20000: [19681] |
|||
</pre> |
|||
=={{header|Perl 6}}== |
=={{header|Perl 6}}== |