Mercurial > repos > other > adventofcode2023
view day17.rb @ 36:7197f31970ff
Day 25 part 1 instructions and partial solution
author | IBBoard <dev@ibboard.co.uk> |
---|---|
date | Thu, 18 Apr 2024 19:56:23 +0100 |
parents | eb6c3a7d2f72 |
children | 455c825f5080 |
line wrap: on
line source
#! /usr/bin/env ruby require 'set' if ARGV.length != 1 abort("Incorrect arguments - needs input file") elsif not File.exist? (ARGV[0]) abort("File #{ARGV[0]} did not exist") end file = ARGV[0] Coord = Struct.new(:x, :y) Route = Struct.new(:steps, :distance) Routes = Struct.new(:routes, :min_distance) city_map = File.open(file, "r").each_line(chomp: true).map{ |line| line.each_char.map(&:to_i)} start_space = Coord.new(0,0) end_space = Coord.new(city_map[0].length - 1, city_map.length - 1) visited = {} routes = { start_space => Routes.new([Route.new([start_space], 0)], 0)} unvisited = Set.new unvisited << start_space #(0...city_map.length).each {|y| (0...city_map[0].length).each {|x| unvisited << Coord.new(x,y)}} $up = Coord.new(0, -1) $down = Coord.new(0, 1) $left = Coord.new(-1, 0) $right = Coord.new(1, 0) def get_neighbours(city_map, x, y) [$up, $down, $left, $right].map {|coord| Coord.new(coord.x + x, coord.y + y)}.filter {|coord| coord.x >= 0 and coord.y >= 0 and coord.x < city_map[0].length and coord.y < city_map.length} end def allowed_routes(city_map, routes, cur_node, next_node) next_step_distance = city_map[next_node.y][next_node.x] candidate_routes = routes[cur_node].routes.map {|route| Route.new(route.steps + [next_node], route.distance + next_step_distance)} valid_routes = candidate_routes.filter do |route| looped = route.steps.count(next_node) > 1 if route.steps.length < 5 ! looped else step_range = route.steps[-5..-2] !(step_range.all?{|step| step.x == next_node.x} or step_range.all?{|step| step.y == next_node.y}) and !looped end end valid_routes = valid_routes + routes[next_node].routes if !routes[next_node].nil? Routes.new(valid_routes, valid_routes.map(&:distance).min) end def get_distance(routes, node) if routes.key?(node) routes[node].min_distance else Float::INFINITY end end until unvisited.empty? # puts unvisited min_node = nil # min_node_direct_distance = Float::INFINITY unvisited.each do |node| # x_dist = (end_space.x - node.x).abs # y_dist = (end_space.y - node.y).abs # direct_distance = x_dist * x_dist + y_dist * y_dist if min_node.nil? || get_distance(routes, node) < get_distance(routes, min_node)# || direct_distance < min_node_direct_distance # puts "#{get_distance(routes, node)} < #{get_distance(routes, min_node)} || #{direct_distance} < #{min_node_direct_distance}" min_node = node # min_node_direct_distance = direct_distance end end # puts unvisited.length puts "Min node: #{min_node}" break if get_distance(routes, min_node) == Float::INFINITY or min_node == end_space get_neighbours(city_map, min_node.x, min_node.y).each do |neighbour| new_routes = allowed_routes(city_map, routes, min_node, neighbour) if new_routes.routes.length > 0 routes[neighbour] = new_routes unvisited << neighbour if !visited[neighbour] end end visited[min_node] = true unvisited = unvisited.delete(min_node) # puts "Delete #{min_node}" # a = $stdin.gets("\n") end =begin city_map.length.times do |y| city_map[0].length.times do |x| print routes[Coord.new(x,y)].routes.map(&:distance).min.to_s.rjust(3) + " " + city_map[y][x].to_s + " |" end puts end city_map.length.times do |y| city_map[0].length.times do |x| puts "#{x},#{y} ⇒ #{routes[Coord.new(x,y)].routes.length} - #{routes[Coord.new(x,y)].routes.map(&:distance).minmax}" end end =end puts routes[end_space].routes.sort {|a, b| a.distance <=> b.distance}[0] #puts "#{routes[end_space]}"