Mercurial > lbo > hg > aoc22

changeset 47:55b04c1490ac

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Day 07 Part 1
author Lewin Bormann <lbo@spheniscida.de>
date Thu, 07 Dec 2023 21:16:16 +0100
parents a035d659f764
children 967c64a81311
files 2023/day07.ml 2023/dune 2023/input/07.txt 2023/input/07_test.txt
diffstat 4 files changed, 1127 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/2023/day07.ml	Thu Dec 07 21:16:16 2023 +0100
@@ -0,0 +1,115 @@
+open! Angstrom
+open! Base
+open! Core
+module Hashtbl = Base.Hashtbl
+
+type card = int [@@deriving sexp]
+type hand = card list [@@deriving sexp]
+type bid = { hand : hand; win : int } [@@deriving sexp]
+
+let max_card = 14
+let compare_card = Int.compare
+let _string_of_bids bids = Sexp.to_string_hum @@ List.sexp_of_t sexp_of_bid bids
+
+module Parse = struct
+  let maybe p = option () (p >>= fun _ -> return ())
+  let intP = take_while1 Char.is_digit >>| Int.of_string
+
+  let cardP : card Angstrom.t =
+    choice
+      [
+        satisfy Char.is_digit >>| String.of_char >>| Int.of_string;
+        char 'T' *> return 10;
+        char 'J' *> return 11;
+        char 'Q' *> return 12;
+        char 'K' *> return 13;
+        char 'A' *> return 14;
+      ]
+
+  let handP : hand Angstrom.t = count 5 cardP
+
+  let bidP =
+    let open Angstrom.Let_syntax in
+    let%bind hand = handP in
+    let%bind _ = char ' ' in
+    let%bind win = intP in
+    let%bind _ = maybe (char '\n') in
+    return { hand; win }
+
+  let bidsP = many1 bidP
+
+  exception Parse_exn of string
+
+  let parse_input str =
+    match parse_string ~consume:All bidsP str with
+    | Ok ok -> ok
+    | Error e -> raise (Parse_exn e)
+end
+
+module Part1 = struct
+  type typ =
+    | FiveOf
+    | FourOf
+    | FullHouse
+    | ThreeOf
+    | TwoPair
+    | OnePair
+    | High
+    | NoType
+  [@@deriving sexp]
+
+  let int_of_typ = function
+    | FiveOf -> 8
+    | FourOf -> 7
+    | FullHouse -> 6
+    | ThreeOf -> 5
+    | TwoPair -> 4
+    | OnePair -> 3
+    | High -> 2
+    | NoType -> 0
+
+  let compare_typ a b = Int.compare (int_of_typ a) (int_of_typ b)
+
+  let count_cards cards =
+    let counts = Array.create ~len:(max_card + 1) 0 in
+    let count c = counts.(c) <- counts.(c) + 1 in
+    List.iter ~f:count cards;
+    counts
+
+  let typ_of counts =
+    Array.sort ~compare:(fun a b -> Int.compare b a) counts;
+    match Array.to_list counts with
+    | 5 :: _ -> FiveOf
+    | 4 :: _ -> FourOf
+    | 3 :: 2 :: _ -> FullHouse
+    | 3 :: 1 :: 1 :: _ -> ThreeOf
+    | 2 :: 2 :: 1 :: _ -> TwoPair
+    | 2 :: 1 :: 1 :: 1 :: _ -> OnePair
+    | 1 :: 1 :: 1 :: 1 :: 1 :: _ -> High
+    | _ -> NoType
+
+  let typ_of_hand h =
+    let typ = typ_of (count_cards h) in
+    typ
+
+  let compare_hands a b =
+    let ta, tb = (typ_of_hand a, typ_of_hand b) in
+    match compare_typ ta tb with
+    | -1 -> -1
+    | 1 -> 1
+    | 0 -> List.compare compare_card a b
+    | _ -> assert false
+
+  let compare_bids { hand = a; _ } { hand = b; _ } = compare_hands a b
+  let sort_bids = List.sort ~compare:(fun a b -> compare_bids a b)
+
+  let winnings bids =
+    let sorted = sort_bids bids in
+    let f ix ac bid = ac + ((ix + 1) * bid.win) in
+    List.foldi ~f ~init:0 sorted
+end
+
+let () =
+  let inp = In_channel.input_all In_channel.stdin in
+  let bids = Parse.parse_input inp in
+  Out_channel.printf "Total winnings: %d\n" (Part1.winnings bids)
--- a/2023/dune	Wed Dec 06 20:16:51 2023 +0100
+++ b/2023/dune	Thu Dec 07 21:16:16 2023 +0100
@@ -39,3 +39,10 @@
  (libraries base core angstrom)
  (preprocess
   (pps ppx_let ppx_sexp_conv)))
+
+(executable
+ (name day07)
+ (modules day07)
+ (libraries base core angstrom)
+ (preprocess
+  (pps ppx_let ppx_sexp_conv)))
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/2023/input/07.txt	Thu Dec 07 21:16:16 2023 +0100
@@ -0,0 +1,1000 @@
+T6782 898
+26T7A 345
+56856 92
+88J88 379
+8QQJ8 792
+QQQT8 607
+98998 912
+888T7 491
+7A6Q9 220
+6QJ23 746
+T5297 133
+44874 357
+84854 864
+8JQQ2 383
+J2KT2 649
+84488 234
+JQ4QT 534
+JJAAA 855
+8J49Q 458
+5QK4A 474
+5535T 504
+T3785 237
+28J88 315
+4544A 680
+7T773 731
+KJKKK 190
+5Q5QK 249
+6664T 747
+QTQQT 164
+ATTAA 290
+95752 486
+J3JAA 324
+K9K9J 204
+99959 867
+K4KKK 980
+A937J 37
+654A9 700
+7553K 352
+8333K 361
+ATJT8 771
+26226 940
+TTJ7Q 834
+QQ33J 117
+62J57 890
+J3A4A 124
+T4JT4 677
+93528 31
+TJA2J 509
+Q222A 126
+52T67 177
+3J9TT 629
+33QQ3 471
+22232 9
+82279 283
+3A3AJ 583
+7343T 829
+93338 836
+T588Q 70
+88K85 593
+55353 926
+Q3749 295
+T6JAK 586
+9AA3J 183
+55565 342
+8K4Q8 910
+AA4A4 907
+78T2A 112
+4J66K 263
+TKJTT 386
+66Q6Q 131
+26266 187
+23AQ3 600
+95K3Q 279
+32522 684
+8Q8Q7 62
+KKAKK 579
+QJ885 899
+66J2K 396
+555J5 592
+88TJ6 767
+352K2 94
+J6488 634
+5A32J 943
+AAAKA 673
+J8AAA 667
+2K5JK 768
+Q4578 294
+4447K 227
+QQQQ7 808
+JJ333 176
+49586 515
+622T7 622
+94359 140
+8QJ2A 239
+Q69JT 939
+A75T9 425
+JKA93 887
+AA7AA 157
+TTTJ5 122
+J2J3J 118
+3J333 681
+3769A 429
+A2K92 123
+53Q8K 257
+A83K4 905
+2935K 543
+66466 421
+34394 963
+QQ433 520
+KTKKK 83
+66677 346
+Q83JQ 334
+6AT54 79
+K4949 442
+37374 627
+73777 571
+JQKKJ 648
+42242 226
+KK888 319
+5K6Q2 971
+AA3JA 51
+4AK87 78
+3J343 840
+K3333 25
+33484 401
+9J866 565
+Q399Q 116
+2K597 742
+66A53 793
+AQQAQ 779
+Q3QJJ 470
+75496 4
+8JJT3 775
+99JKJ 437
+22J9J 60
+39AAT 424
+3J43J 507
+33TJ9 414
+99395 209
+A984Q 821
+A88J8 757
+T3A68 432
+36666 646
+KKKAA 175
+K9TTK 392
+33KK5 308
+KK4K4 675
+64443 370
+TQJ9Q 645
+QT999 669
+J5T88 789
+89TJ4 245
+T436T 605
+6T464 36
+JQQ3Q 11
+68666 423
+KKJKT 785
+T4K3A 847
+6T6JT 915
+8Q756 163
+9AAA2 343
+9AJK8 556
+3JJ69 154
+7K7K3 316
+6737Q 641
+88J7J 975
+5J445 270
+KATJT 659
+6J866 717
+989T9 529
+2897K 321
+4A2T5 984
+7AA99 485
+JK222 397
+75468 282
+QT3J3 91
+3K777 532
+6Q566 460
+2KK75 339
+55258 766
+88558 46
+34J34 419
+T42A8 624
+6JA9K 950
+A8646 135
+66696 66
+37Q7Q 612
+KJAK6 753
+94999 306
+2JJJJ 765
+6JQ3A 459
+K8693 871
+477K7 26
+4T6T8 544
+44JK4 720
+5K5K9 372
+KQ66Q 590
+8A294 57
+JJJJJ 440
+88878 18
+J9649 389
+77677 698
+9K69J 145
+2QT2K 75
+77577 22
+AQ4KA 422
+97477 332
+33933 882
+63646 293
+53A3A 763
+4K93K 928
+KKK37 994
+TA259 173
+K896A 93
+6Q666 438
+J8477 674
+AJAQQ 531
+2JJ2J 726
+5KJT5 672
+A58A2 481
+JJAJT 754
+96444 179
+687A5 528
+TA48J 618
+7Q7Q7 537
+T4A44 23
+473Q6 988
+KQ467 64
+5T555 938
+67T33 444
+KAK99 591
+A6K78 160
+23Q7A 878
+TA5AT 292
+2T6Q5 559
+77979 222
+9AAJA 284
+TK47T 166
+694T2 679
+AAA23 838
+88KJK 170
+QJQ2Q 777
+84486 178
+535JQ 411
+J547T 595
+37773 602
+777JQ 188
+48989 825
+4944K 492
+J8959 375
+72Q5A 908
+Q2AAT 280
+Q3666 119
+48J24 238
+999JA 865
+KK9KK 831
+6Q3JT 909
+3A773 50
+38466 461
+37A25 300
+95555 307
+7Q228 557
+KQ66K 525
+8744K 727
+J9JQ9 475
+A5AKA 148
+A7KJT 309
+TT794 539
+53339 762
+Q9999 6
+A4AT4 993
+888AA 790
+6666A 480
+88Q63 274
+99J92 869
+J8988 884
+8K68J 839
+7QA72 498
+84697 581
+3QK3J 289
+59J8A 692
+Q5J5Q 761
+J777K 930
+T552K 251
+TAT26 715
+6J32T 380
+74K28 523
+22279 104
+8TKT2 393
+68J67 391
+55458 340
+5TK47 395
+822J8 893
+T9388 902
+8TQ3Q 252
+3T549 811
+88883 702
+55J2K 81
+4QTT4 138
+69669 272
+KTKTK 576
+T6668 822
+7J777 736
+9ATJT 892
+Q5QQQ 125
+66T9T 519
+4T244 589
+77747 174
+3J698 837
+39K28 665
+QA459 456
+22342 545
+J8478 489
+Q2962 468
+QAAAA 958
+K8T87 260
+J4KK7 706
+J5J95 695
+47445 724
+K268T 967
+33299 652
+KKKK2 664
+K9JKA 711
+85926 435
+J7K6J 511
+3667J 791
+229QA 633
+998K7 642
+8QQ77 774
+6347A 497
+46526 327
+QK327 750
+KAQ25 927
+27T34 134
+T633T 208
+KKQK7 810
+223J2 900
+5KKJ5 842
+99533 521
+A5Q85 553
+54455 570
+JA946 582
+69Q66 690
+99977 701
+282Q8 428
+4AA42 10
+75977 328
+99T99 948
+J5353 546
+QT95K 285
+KKK3K 896
+9696J 264
+T8275 436
+45J55 80
+69AAA 430
+27J4J 202
+6A888 404
+TQ5K8 819
+55858 113
+T828T 933
+T8888 12
+3KKKT 703
+657J6 291
+8699J 172
+9J99T 705
+A22A2 229
+32263 314
+8QQQQ 101
+2J222 354
+73373 107
+99398 946
+2AA2J 885
+T66J6 184
+3K8K8 903
+KJJKK 611
+22226 781
+9A2J9 191
+AK26J 964
+8KK2Q 317
+82898 883
+T9TTT 195
+584JT 743
+4AA45 61
+93J79 100
+3QJAK 241
+T74AQ 304
+4Q2QQ 548
+KKJ27 330
+A9TKK 39
+6J447 303
+592A6 449
+K9928 65
+9A94K 193
+8T646 431
+Q46K3 20
+K5777 833
+Q9756 30
+33838 638
+65686 298
+A9JAJ 599
+85555 784
+6TAA4 286
+3QQ89 446
+3JT37 463
+8AK5Q 230
+7JAAQ 580
+754TQ 74
+9AQQ4 729
+2933J 678
+62757 575
+29929 619
+A3AAA 216
+Q557Q 691
+A7Q8T 983
+3TJQT 668
+A3KJA 503
+7AA77 881
+88288 995
+7QJ3J 770
+5KKJK 265
+444J4 998
+82J87 89
+T3T3J 63
+2QQ76 510
+5QQ25 132
+KKKT5 441
+Q822Q 954
+84858 788
+37627 873
+22959 426
+K6KKJ 454
+4J844 359
+67JQ7 266
+TQ7T2 206
+5QT2J 854
+KK985 42
+3562T 877
+44343 999
+5J595 859
+37888 657
+J65AK 801
+77276 382
+22A22 207
+QQ4K3 253
+9K2K4 161
+888Q8 863
+75J77 518
+K2K2K 150
+2JT62 398
+J3993 719
+AA88A 813
+9499T 211
+A568Q 98
+6KQ6J 962
+QAKA8 367
+998A9 561
+J2357 196
+A797T 663
+6J9J6 505
+2T5T2 759
+K6464 381
+76677 373
+4K92J 33
+5A8JK 447
+8QQ88 660
+3298A 325
+37333 802
+JTQQT 7
+QQQ3A 820
+J5935 506
+K4334 2
+KA749 40
+94QQ9 415
+537KK 225
+25255 913
+835J9 601
+55TTT 647
+92J92 710
+66A6A 312
+A8TT8 914
+4KJKK 271
+T3242 835
+3K636 623
+93T5A 365
+J4739 816
+244A5 465
+A9TT5 560
+2JAA9 224
+TTT7T 356
+AQQAA 656
+QT5Q5 879
+7AA7J 632
+36344 127
+K5T89 243
+797A9 562
+66363 52
+68585 598
+KQ8A9 608
+999K2 21
+52253 151
+A5595 262
+KTTTT 366
+2922T 1000
+25328 815
+3T7T7 806
+Q2Q39 895
+3J432 786
+JA228 782
+AJJ99 621
+8AAQQ 809
+97QAT 143
+456J8 15
+AAJ2A 165
+J55J5 281
+K6945 322
+22A2J 799
+77AAA 666
+Q6J66 168
+7QTJ5 363
+Q38T2 709
+AKT86 936
+QQQQK 585
+JA4J4 130
+AJA73 796
+88QQQ 828
+QQ2Q2 390
+KK77K 301
+A5TQ9 805
+96677 477
+J7495 628
+24222 807
+8QQ83 992
+222K6 861
+949J5 473
+59873 555
+9K584 564
+AAQ7Q 989
+62J2K 445
+4732A 420
+2JT9K 136
+TT989 277
+JJ999 549
+Q9T6K 513
+36J6A 97
+A3J32 986
+8A7TJ 682
+T2784 59
+KJAAK 110
+8KJ88 919
+AKK77 256
+2J876 713
+K3TQ7 115
+8Q6AT 973
+45666 19
+33335 400
+J43K4 851
+A22A9 974
+8Q867 574
+993KA 185
+9K8Q4 464
+5AAAA 949
+27JJ5 686
+3TTT3 606
+T4444 533
+K8838 830
+75682 960
+J89JT 129
+45A5A 886
+KKK6T 416
+AJA6A 626
+AAJKA 182
+AA2A8 73
+7JK88 640
+JJ222 462
+4A455 49
+7JAKQ 812
+AAAA9 387
+777T7 769
+37K2A 348
+QTJ77 355
+KQQKA 500
+QQQ9Q 350
+65666 111
+T7TT7 407
+333TJ 214
+78876 8
+8Q478 409
+8K3AT 934
+6A583 814
+JTJAA 826
+3A373 278
+J4J44 171
+9AAA3 374
+32J32 199
+76TTA 858
+27222 305
+862K6 369
+QJKAA 568
+JK94J 524
+Q6QQ6 852
+2TQ22 987
+J6AJ7 385
+73A6T 106
+QAKQT 925
+2424T 737
+T7ATA 620
+T8A47 613
+J2858 636
+K7373 484
+7QK65 716
+K8QKK 981
+52454 443
+AAAAJ 738
+99J99 69
+6AQJ8 439
+774J9 798
+66JJ6 210
+TTQTQ 35
+7QJ97 694
+QJQQJ 918
+9K999 573
+Q7TT7 68
+46887 704
+T6379 661
+34888 326
+9A999 916
+6466J 849
+666J6 479
+QKKKK 247
+46K48 336
+J6729 467
+A22A6 269
+6KQKK 584
+68J86 961
+8KK87 670
+52656 542
+Q4AJ3 394
+79KJK 77
+Q8965 139
+44474 240
+QJQQQ 434
+AQ449 921
+57A9J 996
+J5835 817
+QQKK3 818
+3943J 13
+4T7A5 956
+44464 517
+5A55J 48
+2J254 722
+9JAT5 487
+Q4757 856
+5Q55A 749
+ATKJ5 82
+J8588 142
+646TQ 783
+38J39 922
+26J77 823
+2TT4T 162
+6666K 137
+QQQ83 758
+32KJT 733
+4J9K8 353
+KQJT7 501
+6T6TK 982
+Q42K9 147
+8734Q 538
+KKA67 794
+JQKKA 804
+QQ555 596
+4JJ45 32
+28383 904
+T5Q45 38
+5T5TJ 221
+Q3K9A 29
+99649 1
+94247 146
+4Q444 362
+5637T 734
+577TT 735
+TT244 364
+56QQQ 149
+K2AQ3 144
+9J959 493
+66Q44 405
+888K8 654
+6J624 635
+9QJKA 569
+K8K5K 120
+24443 344
+6666T 197
+6T747 740
+54523 935
+A96Q2 302
+AJJJA 697
+2T476 90
+55444 403
+QJ22Q 85
+KK9KJ 254
+4938T 156
+5JT8J 741
+Q55K3 527
+627JK 894
+T6245 917
+44864 410
+77QJ3 587
+823A4 457
+32323 259
+9T94T 609
+33J8K 158
+7AK4K 201
+44774 957
+4Q45T 180
+JA82K 978
+333J5 872
+J8948 267
+99933 433
+4T7JJ 563
+85534 862
+K7K8K 24
+JTTKK 824
+TQ8TT 803
+62677 797
+QQATT 965
+QQ668 870
+88724 551
+T3T43 17
+99749 275
+7T6J2 977
+67J77 203
+6T789 167
+22J28 639
+26744 850
+QQQ6Q 47
+QA72T 554
+3AT9T 897
+QJTQ2 261
+696JQ 631
+9KKQJ 490
+469T8 72
+QAT42 951
+AJ2AK 413
+8AQ2T 297
+AJ482 255
+QQQKK 931
+AJA7A 874
+34532 368
+74A44 945
+88989 418
+A2AAA 219
+39999 857
+J7774 687
+Q9925 630
+9JQ9Q 578
+8AA38 689
+8QA2A 427
+Q6Q99 800
+TTTTJ 399
+AA822 614
+ATT47 676
+K2AAA 514
+7J696 338
+J3J87 88
+55547 728
+5A338 86
+838T6 250
+87QAK 970
+795K7 723
+7QTJ6 152
+5A9KQ 494
+KA4TK 650
+Q2222 604
+K5953 452
+K2282 552
+4K586 760
+K4444 868
+724AA 516
+52224 55
+35Q33 58
+46644 331
+T8325 888
+9K229 388
+779TT 920
+97279 95
+JJ374 450
+8JJJJ 610
+84497 217
+8QK4J 233
+KQ6T6 360
+6637Q 53
+KK7QJ 683
+4828A 215
+5TT55 990
+J3768 536
+ATKTK 846
+5T9K4 780
+2T8AT 502
+7T776 712
+KQ93Q 114
+2474J 483
+QQQ46 408
+J5T82 718
+834A9 688
+JT977 615
+69663 296
+4A638 880
+QQQA7 27
+2K22K 377
+29379 972
+244J4 242
+K8KKK 56
+KTQKJ 891
+87K5J 730
+887AA 699
+9QJQA 725
+6J655 929
+8692A 844
+2QQQQ 194
+TJ79Q 969
+JATA9 128
+8448J 103
+9399J 953
+98J77 371
+TT3J5 192
+J3655 924
+6993K 616
+J8788 979
+K9KK3 756
+57AQ4 671
+88KQ7 955
+6AAA6 843
+9494J 105
+6A2QQ 942
+T222T 87
+J9JA5 244
+AKA4A 198
+Q4635 558
+2332T 889
+AKQQ5 827
+97QQQ 337
+JT575 603
+36336 478
+4A43T 653
+5QQ38 349
+97777 776
+TQ6TT 541
+57775 258
+68KKK 469
+92224 121
+4853Q 476
+2Q695 273
+2J626 732
+6A328 246
+5QT27 959
+KJJ77 658
+4K6KK 310
+JAK66 28
+QQK4K 16
+K4923 752
+57555 482
+46T5T 550
+333Q3 496
+2Q93J 755
+778J3 751
+K77KJ 276
+76A96 947
+QTT7T 335
+4T9K6 997
+26926 512
+66464 522
+59997 787
+K462A 508
+K4K7K 333
+Q3Q3Q 707
+A3TKK 772
+7T7J7 44
+TAK54 455
+44JKQ 287
+TQK49 748
+37335 577
+Q743J 200
+Q4A45 236
+KJ62K 288
+544K5 76
+TTTJJ 693
+89999 96
+K8JKK 351
+5JAT8 778
+TAAJT 67
+39339 911
+997K6 329
+5JK88 876
+338QQ 530
+88889 937
+884T8 526
+382QA 320
+86Q35 764
+KQ38A 412
+AA7A8 358
+22Q2K 637
+A22JK 248
+59855 906
+33AJ3 347
+42T2Q 108
+AQ2T6 99
+8KATJ 651
+9JQTT 832
+84847 451
+52K8K 453
+K6553 54
+87778 499
+TAAJA 223
+38298 643
+5557Q 841
+9K6K9 448
+77J73 617
+555K5 976
+A38T4 968
+3333A 472
+5KJ74 866
+7JJ8K 708
+J55Q5 714
+58KA4 795
+AAAA4 488
+Q8QQ7 45
+58A55 311
+27T7T 3
+2J4KA 43
+TT3T9 159
+475K6 109
+48844 323
+4T2T2 186
+Q7A7J 218
+JTJA6 744
+J96J4 721
+8TT88 41
+Q5T96 417
+QTA6T 213
+68A33 169
+J3TT8 34
+44JK8 14
+29983 540
+3666J 845
+436J2 685
+88A88 597
+889J9 313
+77754 848
+2TA99 406
+5KK5K 535
+3KJ75 547
+67666 662
+9T634 231
+QTQQQ 299
+J993T 745
+87Q98 155
+AAAKQ 376
+36Q43 696
+67K67 952
+25Q47 739
+44424 228
+K22JQ 941
+5434Q 232
+8AA6Q 5
+58J55 625
+37535 153
+66868 572
+87788 384
+J5993 860
+K42K4 402
+59Q7T 944
+J2475 495
+KKKK7 773
+9K5Q2 341
+9AQAQ 594
+T5974 181
+42442 901
+T6TTT 932
+25895 268
+44484 212
+88J63 588
+22777 102
+Q7K77 991
+QK9K9 235
+J4544 205
+7K523 985
+T4246 566
+9TQ3A 466
+884JT 644
+59995 84
+7772J 853
+JJ882 318
+25522 923
+TTT9J 189
+23333 378
+58J85 141
+7K45K 567
+JJ777 71
+74A47 875
+2J848 655
+93K65 966
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/2023/input/07_test.txt	Thu Dec 07 21:16:16 2023 +0100
@@ -0,0 +1,5 @@
+32T3K 765
+T55J5 684
+KK677 28
+KTJJT 220
+QQQJA 483