algorithms/array/garage/garage.jl at master · marcosfede/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
type FastList
  arr::Vector{Int}
  indexof::Dict{Int, Int}
  swaps::Int
  FastList(beg) = new(beg, Dict(v => i for (i, v) in enumerate(beg)), 0)
end
function get_index(fl::FastList, e::Int)
  return fl.indexof[e]
end
function swap(fl::FastList, e1::Int, e2::Int)
  i1 = fl.indexof[e1]
  i2 = fl.indexof[e2]
  # set element where 0 is to final element
  fl.arr[i1] = e2
  # update dict
  fl.indexof[e2] = i1
  # set 0 where the previous number was
  fl.arr[i2] = e1
  # update dict
  fl.indexof[e1] = i2
  fl.swaps += 1
  println(fl.arr)
end


function calc_moves(fl::FastList, en::Vector{Int})::Int
  while fl.arr != en
    i0 = get_index(fl, 0)
    if en[i0] != 0
      swap(fl, 0, en[i0])
      continue
    end
    for (ind, el) in enumerate(fl.arr)
      if el != en[ind]
        swap(fl, 0, el)
        break
      end
    end
  end
  return fl.swaps
end

function garage(beg::Vector{Int}, en::Vector{Int})
  fl = FastList(beg)
  return calc_moves(fl, en)
end

initial = [1, 2, 3, 0, 4]
final = [0, 3, 2, 1, 4]
println("initial:", initial)
println(garage(initial, final))
println("final should be:", final)