Skip to content

Instantly share code, notes, and snippets.

@deevis

deevis/path_finder.rb

Created January 24, 2022 02:11
Show Gist options
  • Save deevis/2649fc99ef3273dd37fe98477713ed1b to your computer and use it in GitHub Desktop.
Save deevis/2649fc99ef3273dd37fe98477713ed1b to your computer and use it in GitHub Desktop.
Download ZIP
PathFinder along with solution visualization
Raw
path_finder.rb
# originally a solution for Codewars.com: Path Finder #3: the Alpinist
class PathFinder
# Options for display_strategy: [nil, :highlight, :animate]
def initialize(display_strategy =nil)
@display_strategy = display_strategy
end
# Options for display_strategy: [nil, :highlight, :animate]
def path_finder(maze, display_strategy = nil)
t = Time.now
if display_strategy
@display_strategy = display_strategy
end
@animate = @display_strategy == :animate
@animate_count = 0
@best_score = nil
# puts maze
@imaze = maze.split.map{|x| x.chars.map(&:to_i)}
@n = @imaze.length
@lowest_route_score_grid = Array.new(@n){Array.new(@n)}
@traversing = Array.new(@n){Array.new(@n)}
@paths_tried_count = 0
# dump_path(@traversing)
system 'clear' if @animate
puts "-" * @n if @animate
traverse(0, 0)
dump_path(@best_path)
puts "Tried #{@paths_tried_count} total paths"
puts "Finished #{@n}x#{@n} in #{Time.now - t} seconds"
puts "Best path found with score: #{@best_score}"
@best_score
end
def traverse(r, c, previous_value = nil, sum = 0)
return if @traversing[r][c]
val = @imaze[r][c]
previous_value ||= val
sum += (val - previous_value).abs
return if @best_score && sum > @best_score
if r == c && r == (@n - 1)
@paths_tried_count += 1
console_output(2, @n + 10, "Paths Tried: #{@paths_tried_count} ") if @animate && @paths_tried_count % 10 == 0
@traversing[r][c] = 1
console_output(r,c,val,:on) if @animate
if @best_score.nil? || sum < @best_score
@best_path = @traversing.map{|r| r.clone}
# dump_path(@traversing)
# puts "Score: #{sum}"
@best_score = sum
console_output(3, @n + 10, " Best Score: #{@best_score} ") if @animate
end
@traversing[r][c] = nil
console_output(r,c,val) if @animate
return
end
# if rand > 0.98
# dump_path(@traversing)
# puts "Random path dump"
# end
console_output(r,c,val,:on) if @animate
if @lowest_route_score_grid[r][c] && @lowest_route_score_grid[r][c] <= sum
@paths_tried_count += 1
console_output(2, @n + 10, "Paths Tried: #{@paths_tried_count} ") if @animate && @paths_tried_count % 10 == 0
#puts " - bailing > #{@lowest_route_score_grid[r][c]}"
console_output(r,c,val) if @animate
return
end
@lowest_route_score_grid[r][c] = sum
# dump_path(@traversing, row: r, col: c)
@traversing[r][c] = 1
traverse(r, c+1, val, sum) if c + 1 < @n
traverse(r+1, c, val, sum) if r + 1 < @n
traverse(r, c-1, val, sum) if c > 0
traverse(r-1, c, val, sum) if r > 0
@traversing[r][c] = nil
console_output(r,c,val) if @animate
end
def dump_path(path)
system 'clear' if @animate
puts "-" * @n
path.each_with_index do |r, row|
r.each_with_index do |n, col|
c = @imaze[row][col]
if @animate || @display_strategy == :highlight
if n == 1
print "\033[34;103m#{c}"
else
print "\033[37;40m#{c}"
end
else
print c
end
end
if @animate || @display_strategy == :highlight
puts "\033[37;40m"
else
puts ""
end
end
puts "-" * @n
console_output(2, @n + 10, "Paths Tried: #{@paths_tried_count} ") if @animate
console_output(3, @n + 10, " Best Score: #{@best_score} ") if @animate
console_output(@n + 2, @n+10, "\r\n") if @animate
end
# move to cursor position at (r,c) and print x
def console_output(r,c,x,on_or_off = :off)
@animate_count += 1
color = on_or_off == :on ? "\033[34;103m" : "\033[37;40m"
# https://en.wikipedia.org/wiki/ANSI_escape_code
print "\033[#{r+2};#{c+1}H#{color}#{x}"
if @n > 20
return
elsif @n <= 10 && @animate_count % 5 == 0
sleep 0.001
elsif @n <= 14 && @animate_count % 30 == 0
sleep 0.001
elsif @animate_count % 50 == 0
sleep 0.001
end
end
end
A = [
"000",
"000",
"000"
].join("\n")
B = [
"010",
"010",
"010"
].join("\n")
C = [
"010",
"101",
"010"
].join("\n")
D = [
"0707",
"7070",
"0707",
"7070"
].join("\n")
E = [
"700000",
"077770",
"077770",
"077770",
"077770",
"000007"
].join("\n")
F = [
"777000",
"007000",
"007000",
"007000",
"007000",
"007777"
].join("\n")
G = [
"000000",
"000000",
"000000",
"000010",
"000109",
"001010"
].join("\n")
# 20x20 Answer: 57
H = <<~MAZE
94026455762233898746
78651937607839316298
85985048089899427533
13881055069284815944
65679091181504346372
22843456669745976012
24180772458313803951
30043948504742994942
54632837721433682840
96799071542434598813
10728436250428028777
33642699375330721932
60172879407967138046
36468183287353848044
37131010672307051527
40047110258861935765
15280434095840848020
85113222218602324538
61272428813250996802
81900807096429851210
MAZE
# 25x25 Answer: 68
I = <<~MAZE
8883417411585299275385931
5751568986401601285559302
9130721320479851367507063
3252063307590455839144782
6262738912379333785072993
1465494599446266786375104
4821210361324655738768184
1946499134917746305956957
6391754820349550229347959
8688797399644992974795977
0199338686458390183000652
8995245074276460675448663
6441368410510805269602194
8491161758656881112888868
2998957467372426061166590
6323326679458154020593848
2168958315131961107528288
8681425227875149101281467
8981010735840794148767760
1917169164382218080338061
4977514309120957156614084
5165264055057947738746828
7463876975650348122713511
7614263053686338613203668
7795614751802123471515016
MAZE
# 30x30 Answer: 76
J = <<~MAZE
309192567892746158334025029028
287967805532349689501251386896
357270393996718212064282126386
046155150064781055582854519388
587233265943835061802925662581
119241172708498964196439028643
215432283213635404194465153847
429386540668573106564442337557
759707693452256700759425289534
848726588670102647729719866357
372999568396090847652965122745
178511785490715536435111149150
226023523042121010073679232489
537515542445621955137446023414
061861367655259205166150680422
873763648023046060932339262649
147004198182084435721440904738
116777978588768638933280841264
456633114685926670992934811437
383359323966907793783123937405
779800762665466350073676157765
936313771904603512527999818456
550998579661921895232494628191
910492522400007604235518457056
952346144070456536337077182661
250918893444897612174769949842
769576676660331674006770662929
362648133934423562447057859724
931651660298095666923056183428
536379029345576016216687966663
MAZE
# 35x35 Answer: 100
K = <<~MAZE
35916283412575666830917956191129863
97233956017350632596536864535443811
90839591796941581456839355578948566
02285445247823992668015501253529305
26606112120906980256812469175889998
81784032115699226334907410914258107
03509264423970810484311327939410045
00272578915129369899995758910490685
58957149773123731466513089962122575
91798814449245811542454814144286576
82947037327965224396114132407150324
56288175861279926605719323931298432
56097323302001571684122390867132416
90259765151909780724290249942775508
78258535523368429446399826879815847
69205230237028185482094936491726905
17849399764102566469769200260683421
81582244807474902475357295964755805
11527802886687981834148217753601979
40893922128182915945901175447209832
42132927738977529027567082367393616
55449105474514226781283136249257719
83902479193234749209894398318901187
72604624752685155402493245511327765
44223071273982978679725807498651069
10190732229176111877089892235088358
28118015797100314300191609967046880
55817389107161856845235282492515030
54297447683101526221502220242309327
48074463233810809235225069895149298
94803405700705881309883987756230178
69325376771701152401209695486503087
56758072517098062528483152708523520
85089936066544623350525813672065494
61778788542959110258845510564787785
MAZE
# 40x40 Answer: 98
L = <<~MAZE
7298437607715370122016451055326387516778
4142604191019784075543552144489133878387
7259223505925642841646488055082835415760
7085352331897769394834982828400769567619
6904677958208975289332349197758371275379
0398484552912861424452748320960614369447
5966321970407979456755138745732667752649
8008980840122848779970259994540012278292
3471615783684947344152519395680782248193
5673169634964869022298941822848155368988
7012349668995455905457211749107480642968
3312390881256771316009750305255643952413
3966282219222472100315602132695513406707
7293828632170596851790675775287454325490
3402699021576503484497112213290829535940
4328997549859445730110248342502972003422
6349732085679345183866180502977774389952
4901287449722137217158236813680739759388
0592004994467897601270653764372200478778
1509698938354663067419534948366567589008
7077941976109787011492744544973719928138
6872746536350564058297147195688859116034
0738232734922194305915262372721436202886
6131633101200309263784296550771836807931
6884433872574577283224483879350604630252
3274667518233182943321925137275048214754
0247741266849498192073967765871114487657
6135197523409778649031050554653183484769
6730847251937417400756232617862234752078
8351929129428887228273891920458398544820
5886491241518463903954603842520406745224
7446135077537437498981833011880449537811
2738021242569030113954283531173149597245
7942815781491646230086601561052000896604
5826867081218134887508391034917383560381
6876263927419708026679186005919555083760
0071879253262726749912754008121706032522
2137185086103089730026931043188672202685
5383099058060642461041212700718060116553
7283212749541139823682403709920748370255
MAZE
# 46x46 Answer: 120
M = <<~MAZE
5302982202387031901372564703963623955078219368
3221120756729163033277060936320622251424243776
4600382861349783935703703884157568482676452291
5841888228236186321169620728795399385666275896
6796688083695335463357049871144291737833283263
4645601634380457862136329750499232956756297314
7765119860130731146051229546562531363566160493
3081678971562613624000752996574052565465445407
5027756676164005672839903636158298106159267930
7823463335849611299882839537602728357633548509
9743591248626042598189686434883389206241442355
1610175541951878627963257015058464457596789349
2733066156751551979711199501217039342451489480
5908098716412648564671074257949952630302450687
1583545984286534686136524852450123327471021551
8703351311509480097827392888909041319007364657
6030610063200450671234451373639399881805735500
3870763189212243686491069607350581396194093823
0864529333895184577996621959486285931616406370
0541370086894341478487999814687962811092834167
7566395408721784065707422079113801738749597282
3708062130721187431285847849349551961036249637
7148978408587183932008292946844511867170955337
4310959507741884085365624379365221697108656043
7054077044596857656133413884181165580419521303
1345115694444405623189979798888799848880011593
6945041625512664798553376067675539499998211781
7390593467647959351794056698382089491108627615
6134216956110172054445863013203562880477687128
8037573866922012228581660884007679601916766498
0776109375747150588172835234256950675475918502
9302117722916707938253878106612807978792825047
8068439267947064572802476958425329898838714317
8191997198534790936277702761843505929543909931
0365632735818979533661172782441425984917588967
9784365347971503821784044099602480103222893638
6248630818810280121319647493263299236285121989
1671850915199235281643204498278530846585927202
1850062991410141814012292296425243535170557411
5721604064925622102877638492579171836533893377
7228192134482474249486119686334448837104862759
2913613025619958864937491505192004478110978216
1606581645764118646785444258282540726322026121
9915078440856445138626726052427455718025846639
1223927738984484658191124099253017369145808229
1496475482700078034882575242326884531089039717
MAZE
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment