Mercurial > repos > other > adventofcode2023

annotate day24b.rb @ 38:8e92cb172e6b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Output final distance Also minor code cleanup
author IBBoard <dev@ibboard.co.uk>
date Fri, 20 Sep 2024 20:30:11 +0100
parents ca54f9702892
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
35
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
1 #! /usr/bin/env ruby
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
2
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
3 require 'prime'
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
4
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
5 if ARGV.length != 1
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
6 abort("Incorrect arguments - needs input file")
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
7 elsif not File.exist? (ARGV[0])
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
8 abort("File #{ARGV[0]} did not exist")
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
9 end
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
10
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
11 file = ARGV[0]
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
12
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
13 MovingObject = Struct.new(:x, :y, :z, :dx, :dy, :dz)
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
14 Position = Struct.new(:x, :y, :z)
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
15
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
16 objects = File.open(file, "r").each_line(chomp: true).map do |line|
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
17 pos, vel = line.split(" @ ")
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
18 position = pos.split(", ").map(&:to_f)
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
19 velocity = vel.split(",").map(&:to_f)
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
20 MovingObject.new(position[0], position[1], position[2], velocity[0], velocity[1], velocity[2])
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
21 end
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
22
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
23 # Lots of answers talking about "gaussian elimination" and other maths, or use external libraries
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
24 # But some people pointed out that if there's two objects moving at the same speed in a given direction
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
25 # then the new object must move at some factor of the difference between their starting points
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
26 # so that it can cover the other two dimensions between them
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
27 matches = objects.combination(2).filter {|a,b| a.dx == b.dx || a.dy == b.dy || a.dz == b.dz}.group_by {|a,b| [a.dx == b.dx, a.dy == b.dy, a.dz == b.dz]}
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
28 puts "#{matches}"
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
29 x_objs = matches[[true,false,false]]
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
30 y_objs = matches[[false,true,false]]
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
31 z_objs = matches[[false,false,true]]
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
32 x_dist = (x_objs[0][0].x - x_objs[0][1].x).abs.to_i
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
33 y_dist = (y_objs[0][0].y - y_objs[0][1].y).abs.to_i
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
34 z_dist = (z_objs[0][0].z - z_objs[0][1].z).abs.to_i
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
35
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
36 puts "Starting distance gap: same x = #{x_dist}; same y = #{y_dist}; same z = #{z_dist}"
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
37 puts "GCD of x and y: #{x_dist.gcd(y_dist)}"
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
38 puts "GCD of x and z: #{x_dist.gcd(z_dist)}"
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
39 puts "GCD of x, y and z: #{x_dist.gcd(y_dist).gcd(z_dist)}"
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
40
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
41 # We can't use lowest common factor/greatest common divisor
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
42 # So try prime divisors that people talk about.
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
43 # (DistanceDifference % (RockVelocity-HailVelocity) = 0
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
44 x_candidates = x_objs.reduce(nil) do |accum, pair|
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
45 a, b = pair
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
46 x_diff = (a.x - b.x).abs.to_i
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
47
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
48 if x_diff > 0
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
49 candidates = (1..1000).map {|i| x_diff % i == 0 ? i + a.dx.abs : nil}.compact
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
50 puts "#{x_diff} => #{candidates}"
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
51 accum.nil? ? candidates : accum & candidates
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
52 else
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
53 accum
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
54 end
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
55 end
ca54f9702892 Day 24 part 2 instructions and partial solution
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
56 puts x_candidates