From a2169a1761148e8dd219f46d1b17ae356d45e18f Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jeremy@asynk.ch>
Date: Sun, 13 Sep 2020 17:03:44 +0200
Subject: FLNBot : build shortest paths

---
 lib/colonial_twilight/fln_bot.rb | 32 +++++++++++++++++++++++++++-----
 1 file changed, 27 insertions(+), 5 deletions(-)

diff --git a/lib/colonial_twilight/fln_bot.rb b/lib/colonial_twilight/fln_bot.rb
index 4964433..1b8b6a3 100644
--- a/lib/colonial_twilight/fln_bot.rb
+++ b/lib/colonial_twilight/fln_bot.rb
@@ -338,12 +338,13 @@ module ColonialTwilight
       return conducted_action
     end
 
-    def _paths dst, want, &cond
+    def _paths dst, want
       ws = dst.adjacents.map {|s| @board.spaces[s].wilaya }.uniq!       # adjacent Wilayas allowed
       spaces = @board.search{|s| s != dst and ws.include? s.wilaya }    # corresponding spaces
       puts "DST : #{dst}\nWilayas : #{ws.inspect}\n" + spaces.collect{|s| s.name }.join(' :: ') if @debug
-      tree = build_tree dst, ws, spaces, want
+      paths, tree = build_paths dst, ws, spaces, want
       tree.sort{|(x,a),(y,b)| a[:d]<=>b[:d]}.each{|k,v| puts "\t#{v[:d]} #{v[:fln][:max]}:#{v[:fln][:ok]} #{k.name} :: #{v[:adjs].map{|s| s.name}.join(' - ')}" }
+      paths.each{|p| puts p.collect{|s| s.name}.join ' -> '}
     end
 
     ##### RALLY OPERATION #####
@@ -633,7 +634,7 @@ module ColonialTwilight
       ( (to.support? or from.country?) and (flns + to.gov_cubes + (from.country? ? @board.border_zone_track : 0)) > 3 )
     end
 
-    def build_tree dst, ws, spaces, want
+    def build_paths dst, ws, spaces, want
       tree = ([dst] + spaces).inject({}) do |h,s|
         # filter out adjacents : dst OR adjacent to dst OR same wilaya
         a = s.adjacents.map{|n| @board.spaces[n]}.select{|a| a == dst or (spaces.include?(a) and (s.wilaya == a.wilaya or s == dst))}
@@ -654,7 +655,11 @@ module ColonialTwilight
           end
         end
       end
-      # filter out wilayas that have no eligible FLN
+      # filter_out dst, ws, tree
+      build_shortest_paths tree
+    end
+
+    def filter_out dst, ws, tree
       ws.each do |w|
         h = tree.select{|s,h| s != dst and s.wilaya == w}
         next if h.inject(false) {|b,(s,h)| b||h[:fln][:ok]}
@@ -663,7 +668,24 @@ module ColonialTwilight
           tree[dst][:adjs].delete s
         }
       end
-      tree
+    end
+
+    def build_shortest_paths tree
+      paths = []
+      def dfs s, tree, paths, path
+        l = tree[s][:adjs].sort{|a,b| tree[a][:d] <=> tree[b][:d]}
+        d = tree[l[0]][:d]
+        if d == 0
+          paths << (path << l[0])
+        else
+          l.each do |a|
+            break if tree[a][:d] > d
+            dfs a, tree, paths, path.clone << a
+          end
+        end
+      end
+      tree.select{|k,v| v[:fln][:ok]}.each{|k,v| dfs k, tree, paths, [k] }
+      [paths, tree]
     end
 
     def can_march_from s, want, with={}
-- 
cgit v1.1-2-g2b99