Minimal steps down to 1: Difference between revisions

Content deleted Content added
PureFox (talk | contribs)
m →‎{{header|Go}}: A bit tidier output.
Wherrera (talk | contribs)
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}}==