Part 1
It seems like an easy problem, but I've already went back and forth with some possibilities for solving it. My biggest point of concern is the amount of iterations over the whole input, but I think I have it settled, though.
The overall roadmap for solving is to
1. parse the whole input into a simple data structure of list[str, int], where each str corresponds to a hand, and the int to its bid.
2. map each hand to a sorted list of each card counts; ie. 32T3K maps to [['3', 2], ['K', 1], ['T', 1], ['2', 1]]. These results will be memoized for the sorting phase.
3. when sorting, the most valuable hand is either one with
a. highest card count; b. highest card value for the same count;
(ie. 32T3K and 42T4K both have a pair, but the latter wins because pair of 4 > pair of 3).
The sorting function must be recursive, to handle cases where the highest count corresponds to the same card, thus arising the need to check for subsequent counts.
A couple days later...
...the development was quick, although it is still not done and I've had to (and still am in the process of) debug. My hand ordering function is giving me trouble, and I think this is due to a lack of proper, quality unit tests, and maybe not having thoroughly thought about all the necessary conditions. Maybe I jumped the gun too quickly on making it recursive, which completely tunnel visioned my approach to the problem. In fact, one can just analyse all card counts and then, if they're the same, move onto individual card values.
After some three or four iterations of the hand-ordering function — with very visible bad orderings, such as the above — I seem to have hit a point where all my cards are well-ordered, and I'm missing the correct score by a small margin.
Well, desperate times call for desperate measures, and I resorted to Advent of Code's subreddit to get the correct sequencing from other peoples' correct code. And after comparing *many* results, I suppose I just...re-read the assignment.
So, 33332 and 2AAAA are both four of a kind hands, but 33332 is stronger because its first card is stronger. Similarly, 77888 and 77788 are both a full house, but 77888 is stronger because its third card is stronger (and both hands have the same first and second card). >>>
I feel a bit stupid, embarassed, inadequate; of course, I ought not feel this way; but... argh 😩 I'll refactor the code and tests to get me closer to the desired behaviour
The current top comment on the reddit megathread has a neat solution to attribute a unique numerical value to each hand layout: the sum of the number of ocurrences of each card, for each card. Thus a five-of-a-kind is 5*5, a four is 4*4 + 1*1, full-house is 3*3 + 2*2, which ends up having unique results all the way down to all cards being different.
Tests
TTEST_DATA = """
32T3K 765
T55J5 684
KK677 28
KTJJT 220
QQQJA 483
"""
class Test202307_01(unittest.TestCase):
def test_transform_input_into_game_data(self):
self.assertEqual(
get_game_data(TEST_DATA),
[["32T3K", 765],
["T55J5", 684],
["KK677", 28],
["KTJJT", 220],
["QQQJA", 483]],
)
def test_count_hand_card_count(self):
self.assertEqual(
get_card_counts("23456"),
5
)
self.assertEqual(
get_card_counts("32T3K"),
7
)
self.assertEqual(
get_card_counts("3322K"),
9
)
self.assertEqual(
get_card_counts("33213"),
11
)
self.assertEqual(
get_card_counts("33223"),
13
)
self.assertEqual(
get_card_counts("33323"),
17
)
self.assertEqual(
get_card_counts("33333"),
25
)
def test_hand_comparison(self):
self.assertEqual(
first_hand_bigger_than_second(
"32T3K",
"333K3"
),
False
)
self.assertEqual(
first_hand_bigger_than_second(
"33KT2",
"33AT2"
),
False
)
self.assertEqual(
first_hand_bigger_than_second(
"92222",
"23333"
),
True
)
def test_sorting_hands(self):
self.assertEqual(
sort_array_of_cards(get_game_data(TEST_DATA)),
[
['32T3K', 765],
['KTJJT', 220],
['KK677', 28],
['T55J5', 684],
['QQQJA', 483]
]
)
def test_get_sum_of_bids(self):
self.assertEqual(
get_sum_of_bids(get_game_data(TEST_DATA)),
6440
)
Code
It is finally done. This was a frustrating process, but in the end I find some solace in two things. First, I'm doing this to learn, and be a better programmer; and it is quite evident the latter depends on not spending so much time in front of the computer, trying to cram and produce as much as possible. Headspace is important. The second is that my code feels much more readable than most of the solutions I found. There were some cool tricks around, and people generally find very clever solutions; on the other hand, those are a bit tricker to communicate properly.
I finish part one by recalling a lemma that proved self-evidently during this whole process — in particular, when trying to tackle my very convoluted sorting function:
Kernighan's Law
Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.
from functools import cache
import sys
sys.setrecursionlimit(1050)
ORDER = "AKQJT98765432"[::-1]
def get_game_data(data: str):
return list(map(lambda game_line: [game_line[0],
int(game_line[1])],
map(lambda line: line.split(),
data.strip().splitlines())))
def merge_sort(array: list):
def merge(left: list, right: list) -> list:
if not left:
return right
if not right:
return left
left_card, right_card = left[0][0], right[0][0]
print(left_card, right_card)
return ([right[0]] + merge(left, right[1:])
if first_hand_bigger_than_second(
left_card,
right_card)
else [left[0]] + merge(left[1:], right))
if len(array) < 2:
return array
middle = len(array) // 2
left = array[:middle]
right = array[middle:]
return merge(merge_sort(left), merge_sort(right))
def first_hand_bigger_than_second(
first: str,
second: str
) -> bool:
def first_card_bigger(f: str, s: str) -> int:
return ORDER.index(f) - ORDER.index(s)
# compare the counts
if (get_card_counts(first) != get_card_counts(second)):
return get_card_counts(first) > get_card_counts(second)
# value of cards is only necessary
# if the counts in both hands are the same;
value_dif = (first_card_bigger(f, s) for f, s in zip(first, second))
# if the value difference is above zero,
# then first hand is bigger
return next((val for val in value_dif if val != 0)) > 0
@cache
def get_card_counts(hand: str):
return sum(map(lambda card: hand.count(card),
hand))
def sort_array_of_cards(
play: list[list[str, int]]
) -> list[list[str, int]]:
return merge_sort(play)
def get_sum_of_bids(play: list[list[str, int]]) -> int:
return sum(i * hand[1]
for i, hand in enumerate(sort_array_of_cards(play), start=1))
with open("input", 'r') as f:
data = get_game_data(f.read())
print(f"{get_sum_of_bids(data)}")Part 2
Part 2 introduces a nice twist. Jokers can substitute any other card, and will always maximize the hand value. In essence, what this does is increment the count of whatever was already highest. Luckily, for matters of comparing individual card values (to resolve ties in card count), it acts as J and not the substituted card.
Tests
class Test202307_02(unittest.TestCase):
def test_transform_input_into_game_data(self):
self.assertEqual(
get_game_data(TEST_DATA),
[["32T3K", 765],
["T55J5", 684],
["KK677", 28],
["KTJJT", 220],
["QQQJA", 483]],
)
def test_count_hand_card_count(self):
self.assertEqual(
get_card_counts_with_joker("23456"),
5
)
self.assertEqual(
get_card_counts_with_joker("T54J5"),
get_card_counts_with_joker("AAA32")
)
self.assertEqual(
get_card_counts_with_joker("T55J5"),
get_card_counts_with_joker("AAAA2")
)
self.assertEqual(
get_card_counts_with_joker("J55J5"),
get_card_counts_with_joker("AAAAA")
)
self.assertEqual(
get_card_counts_with_joker("234JK"),
get_card_counts_with_joker("234KK")
)
def test_sorting_hands(self):
self.assertEqual(
sort_array_of_cards(get_game_data(TEST_DATA)),
[
['32T3K', 765],
['KK677', 28],
['T55J5', 684],
['QQQJA', 483],
['KTJJT', 220]
]
)
def test_get_sum_of_bids(self):
self.assertEqual(
get_sum_of_bids(get_game_data(TEST_DATA)),
5905
)
Code
This was much easier than anticipated. Apparently I did a decent job at reading the assignment.
ORDER = "AKQT98765432J"[::-1]
def get_game_data(data: str):
return list(map(lambda game_line: [game_line[0],
int(game_line[1])],
map(lambda line: line.split(),
data.strip().splitlines())))
def merge_sort(array: list):
def merge(left: list, right: list) -> list:
if not left:
return right
if not right:
return left
left_card, right_card = left[0][0], right[0][0]
return ([right[0]] + merge(left, right[1:])
if first_hand_bigger_than_second(
left_card,
right_card)
else [left[0]] + merge(left[1:], right))
if len(array) < 2:
return array
middle = len(array) // 2
left = array[:middle]
right = array[middle:]
return merge(merge_sort(left), merge_sort(right))
def first_hand_bigger_than_second(
first: str,
second: str
) -> bool:
def first_card_bigger(f: str, s: str) -> int:
return ORDER.index(f) - ORDER.index(s)
# compare the counts
if (get_card_counts_with_joker(first) != get_card_counts_with_joker(second)):
return get_card_counts_with_joker(first) > get_card_counts_with_joker(second)
# value of cards is only necessary
# if the counts in both hands are the same;
value_dif = (first_card_bigger(f, s) for f, s in zip(first, second))
# if the value difference is above zero,
# then first hand is bigger
return next((val for val in value_dif if val != 0)) > 0
# the joker can simply add value to the highest count
@cache
def get_card_counts_with_joker(hand: str):
def get_highest_value_card(hand: str):
return ORDER[max(map(lambda card: ORDER.index(card),
set(hand).difference({"J"})))]
if 1 <= hand.count("J") <= 4:
max_count = max(map(lambda card: [card, hand.count(card)],
set(hand).difference({"J"})),
key=lambda x: x[1])
# all jokers contribute to the highest count
if max_count[1] > 1:
return get_card_counts_with_joker(
hand.replace("J", max_count[0]))
# no highest count;
# jokers will copy the highest value card
else:
return get_card_counts_with_joker(
hand.replace("J", get_highest_value_card(hand)))
return sum(map(lambda card: hand.count(card),
hand))
def sort_array_of_cards(
play: list[list[str, int]]
) -> list[list[str, int]]:
return merge_sort(play)
def get_sum_of_bids(play: list[list[str, int]]) -> int:
return sum(i * hand[1]
for i, hand in enumerate(sort_array_of_cards(play), start=1))
with open("input", 'r') as f:
data = get_game_data(f.read())
print(f"{get_sum_of_bids(data)}")