Day 10: Hoof It

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • @Karmmah
    2•2 days ago

    Julia

    Quite happy that today went a lot smoother than yesterday even though I am not really familiar with recursion. Normally I never use recursion but I felt like today could be solved by it (or using trees, but I’m even less familiar with them). Surprisingly my solution actually worked and for part 2 only small modifications were needed to count peaks reached by each trail.

    Code 
    function readInput(inputFile::String)
	f = open(inputFile,"r")
	lines::Vector{String} = readlines(f)
	close(f)
	topoMap = Matrix{Int}(undef,length(lines),length(lines[1]))
	for (i,l) in enumerate(lines)
		topoMap[i,:] = map(x->parse(Int,x),collect(l))
	end
	return topoMap
end

function getTrailheads(topoMap::Matrix{Int})
	trailheads::Vector{Vector{Int}} = []
	for (i,r) in enumerate(eachrow(topoMap))
		for (j,c) in enumerate(r)
			c==0 ? push!(trailheads,[i,j]) : nothing
		end
	end
	return trailheads
end

function getReachablePeaks(topoMap::Matrix{Int},trailheads::Vector{Vector{Int}})
	reachablePeaks = Dict{Int,Vector{Vector{Int}}}()
	function getPossibleMoves(topoMap::Matrix{Int},pos::Vector{Int})
		possibleMoves::Vector{Vector{Int}} = []
		pos[1]-1 in 1:size(topoMap)[1] && topoMap[pos[1]-1,pos[2]]==topoMap[pos[1],pos[2]]+1 ? push!(possibleMoves,[pos[1]-1,pos[2]]) : nothing #up?
		pos[1]+1 in 1:size(topoMap)[1] && topoMap[pos[1]+1,pos[2]]==topoMap[pos[1],pos[2]]+1 ? push!(possibleMoves,[pos[1]+1,pos[2]]) : nothing #down?
		pos[2]-1 in 1:size(topoMap)[2] && topoMap[pos[1],pos[2]-1]==topoMap[pos[1],pos[2]]+1 ? push!(possibleMoves,[pos[1],pos[2]-1]) : nothing #left?
		pos[2]+1 in 1:size(topoMap)[2] && topoMap[pos[1],pos[2]+1]==topoMap[pos[1],pos[2]]+1 ? push!(possibleMoves,[pos[1],pos[2]+1]) : nothing #right?
		return possibleMoves
	end
	function walkPossMoves(topoMap::Matrix{Int},pos::Vector{Int},reachedPeaks::Matrix{Bool},trailId::Int)
		possMoves::Vector{Vector{Int}} = getPossibleMoves(topoMap,pos)
		for m in possMoves
			if topoMap[m[1],m[2]]==9
				reachedPeaks[m[1],m[2]]=1
				trailId += 1
				continue
			end
			reachedPeaks,trailId = walkPossMoves(topoMap,m,reachedPeaks,trailId)
		end
		return reachedPeaks, trailId
	end
	peaksScore::Int = 0; trailsScore::Int = 0
	trailId::Int = 0
	for (i,t) in enumerate(trailheads)
		if !haskey(reachablePeaks,i); reachablePeaks[i]=[]; end
		reachedPeaks::Matrix{Bool} = zeros(size(topoMap))
		trailId = 0
		reachedPeaks,trailId = walkPossMoves(topoMap,t,reachedPeaks,trailId)
		trailPeaksScore = sum(reachedPeaks)
		peaksScore += trailPeaksScore
		trailsScore += trailId
	end
	return peaksScore,trailsScore
end #getReachablePeaks

topoMap::Matrix{Int} = readInput("input/day10Input")
trailheads::Vector{Vector{Int}} = getTrailheads(topoMap)
@info "Part 1"
reachablePeaks = getReachablePeaks(topoMap,trailheads)[1]
println("reachable peaks: ",reachablePeaks)
@info "Part 2"
trailsScore::Int = getReachablePeaks(topoMap,trailheads)[2]
println("trails score: $trailsScore")