Mercurial > repos > other > adventofcode2023

annotate day7b.rb @ 39:0e17e4bd97a9 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Rewrite as four-dimensional route finding The grid isn't just a 2D grid. The constraints make it 4D: * X * Y * Last direction * Number of steps in that direction By tracking all four dimensions, we can find the shortest route for _all_ combinations of the constraint. Previously, we were dropping routes that were currently longer but ended up shorter because they could take subsequent steps that other routes couldn't.
author IBBoard <dev@ibboard.co.uk>
date Sun, 22 Sep 2024 11:30:53 +0100
parents 9ec95ff0d33d
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
9
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
1 #! /usr/bin/env ruby
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
2
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
3 require 'set'
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
4
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
5 if ARGV.length != 1
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
6 abort("Incorrect arguments - needs input file")
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
7 elsif not File.exist? (ARGV[0])
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
8 abort("File #{ARGV[0]} did not exist")
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
9 end
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
10
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
11 file = ARGV[0]
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
12
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
13 Hand = Struct.new(:cards, :score, :bid)
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
14
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
15 $card_scoring = ["J"].concat(("2".."9").to_a).concat(["T", "J", "Q", "K", "A"])
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
16
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
17 JOKER_VALUE = $card_scoring.index("J")
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
18 FULL_HOUSE = Set.new([2,3])
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
19 TWO_PAIR = {2 => 2, 1 => 1}
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
20
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
21 def score_hand(cards)
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
22 card_vals = cards.each_char.map {|c| $card_scoring.index(c)}
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
23 card_groups = card_vals.group_by{|v| v}.sort {|a,b|
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
24 # Push jokers to the start so that we can find the biggest group
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
25 # to add them to
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
26 if a[0] == JOKER_VALUE then -1
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
27 elsif b[0] == JOKER_VALUE then 1
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
28 # Then order by number of values
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
29 elsif a[1].length < b[1].length then -1
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
30 elsif a[1].length > b[1].length then 1
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
31 # Then order by card score
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
32 else a[0] <=> b[0]
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
33 end
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
34 }
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
35 jokers = card_vals.count(JOKER_VALUE)
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
36 joker_replacement = card_groups.last[0]
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
37 card_counts = card_groups.map {|v|
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
38 # If it's the joker replacement, add the number of jokers (which may be 0)
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
39 if v[0] == joker_replacement and v[0] != JOKER_VALUE then v[1].length + jokers
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
40 # If it's the jokers and we're not a hand of jokers then remove them - they're added elsewhere
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
41 elsif v[0] == JOKER_VALUE and joker_replacement != JOKER_VALUE then 0
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
42 # Else just take the count
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
43 else v[1].length
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
44 end
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
45 }.select {|num| num != 0}
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
46 card_count_counts = card_counts.group_by{|v| v}.map{|k,v| [k, v.length]}.to_h
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
47 dejokered_card_vals = card_vals.map {|v| v == 0 ? card_vals.max : v}
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
48 of_a_kind = card_counts.max
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
49 rank = of_a_kind * 10 # 5, 4 or 3 of a kind or a pair
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
50 if Set.new(card_counts) == FULL_HOUSE
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
51 rank = 35
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
52 elsif card_count_counts == TWO_PAIR
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
53 rank = 25
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
54 end
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
55 card_vals.reduce("#{rank}") {|str, v| "#{str}.#{(v+1).to_s.rjust(2, '0')}"}
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
56 end
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
57
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
58 hands = File.open(file, "r").each_line(chomp: true).map {|line| cards, bid = line.split(" "); Hand.new(cards, score_hand(cards), bid.to_i)}
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
59
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
60 puts hands.sort {|a, b| a.score <=> b.score}.map.with_index(1) {|val, i| puts "#{val}"; i * val.bid}.sum
9ec95ff0d33d Add Day 7 solutions with string sorting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
61 # Rest of algorithm here