Minimal steps down to 1: Difference between revisions
Content deleted Content added
m second stretch goal |
m memoize |
||
| Line 187: | Line 187: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Non-recursive solution that is memoized for the count-only ortions of the task. When the steps are to be printed, the solution is not memoized in order to list all possible paths of the shortest length (all solutions). 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. |
|||
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 |
<lang julia>import Base.print |
||
| Line 206: | Line 203: | ||
print(io, "$(ao.act.f) $(ao.act.i) yields $(ao.out)") |
print(io, "$(ao.act.f) $(ao.act.i) yields $(ao.out)") |
||
end |
end |
||
memoized = Dict{Int, Int}() |
|||
function findshortest(start, goal, fails, actions, verbose=true, maxsteps=100000) |
function findshortest(start, goal, fails, actions, verbose=true, maxsteps=100000) |
||
| Line 217: | Line 216: | ||
newsequences = Vector{Vector{ActionOutcome}}() |
newsequences = Vector{Vector{ActionOutcome}}() |
||
numsteps += 1 |
numsteps += 1 |
||
for seq in seqs |
for seq in seqs |
||
for (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 |
||
end |
|||
if !verbose && isempty(solutions) && |
|||
all(x -> haskey(memoized, x[end].out), newsequences) |
|||
minresult = minimum(x -> memoized[x[end].out], newsequences) + numsteps |
|||
memoized[start] = minresult |
|||
return minresult |
|||
end |
end |
||
end |
end |
||
| Line 240: | Line 247: | ||
end |
end |
||
end |
end |
||
memoized[start] = numsteps |
|||
return numsteps |
return numsteps |
||
end |
end |
||
| Line 272: | Line 280: | ||
teststeps(1, failed, actions1, [2000, 20000, 50000]) |
teststeps(1, failed, actions1, [2000, 20000, 50000]) |
||
empty!(memoized) |
|||
teststeps(1, failed, actions2, [2000, 20000, 50000]) |
teststeps(1, failed, actions2, [2000, 20000, 50000]) |
||
</lang>{{out}} |
</lang>{{out}} |
||