jf 0 &start @raw dle_mode:0 exec_mode:0 gen_count: 10 gen_skip: 0 gen_label: 0 puzzle_iterations: 2000 start: add exec_mode &routine_table monkey_handler rbo &auto__end rbo 260642 ########################## # # AOC 2024 Day 22 Intcode Solver -- Unrolled Version # # Input is in ASCII, output is in ASCII. # # Since the input size is indeterminate, EOF must be reported via any of these means: # # - A blank line (i.e. ends in \n\n, or \r\n\r\n) # - 0x00 (ASCII NUL) # - 0x1A (Ctrl-Z, ASCII SB; MS-DOS or CPM end-of-file indicator) # - 0x04 (Ctrl-D, ASCII EOT; Default EOF replacement character on *nix-style TTY drivers) # - a negative number (`EOF` constant returned by `fgetc`, `getc`, or `getchar`; see `stdio.h`) # # NOTES: # # The Intcode CPU is surprisingly powerful in some ways, but remarkably weak in others. # One of the worst is the lack of general-use pointer registers, which means operations on dynamic memory addresses # necessarily involves a *lot* of self-modifying code. ########################## # # EXECUTION OPTIONS BLOCK - Memory addresses 3-4 # [3]: Intcode Debug Mode # [4]: Execution Mode # 0 = Solve puzzle normally # 1 = Generate GEN_COUNT successive secret numbers starting with #GEN_SKIP and print them out # 2 = As #1, but prints prices instead of the secret numbers # [5] GEN_COUNT for mode 1/2 (default 10) # [6] GEN_SKIP for mode 1/2 # [7] GEN_LABEL for mode 1/2 # [8] PUZZLE_ITERATIONS (default 2000) ###################### # # Read and process puzzle input # read_next_number: @call &read_integer jf ~1 blank_action:&read_next_number @cpy &end_of_input blank_action # okay, ~1 is the secret number seed. # fill the xorshift register with this value. @call &init_xorshift @call monkey_handler:*0 @jmp &read_next_number end_of_input: jt exec_mode &halt_program @cpy '1' ~1 @cpy part1_answer ~2 @call &print_part_n_answer @cpy '2' ~1 @cpy part2_answer ~2 @call &print_part_n_answer halt_program: hlt @raw routine_table: &process_monkey &generate_secrets &generate_prices ###################### # # generate_secrets: print the next GEN_COUNT (default 10) secret values and exit generate_secrets: @cpy &get_current_value ~1 @jmp &generate_secrets_core ###################### # # generate_prices: print the next GEN_COUNT (default 10) prices and exit generate_prices: @cpy &get_current_price ~1 @jmp &generate_secrets_core @fn 0 generate_secrets_core(extract_func) local(counter, skipcount) global(print_decimal, GEN_COUNT, GEN_SKIP, GEN_LABEL, xorshift_step, get_current_val_core) @cpy 0 counter @cpy GEN_SKIP skipcount @jmp &print_first loop: @call &xorshift_step print_first: add skipcount -1 skipcount @jge skipcount 0 &loop jf GEN_LABEL &no_print_label add GEN_SKIP counter ~1 @call &print_decimal out ':' out 32 no_print_label: @call extract_func @call &print_decimal out '\n' add counter 1 counter @jle counter GEN_COUNT &loop out '\n' @endfn ###################### # # print_part_n_answer: prints answers. @fn 0 print_part_n_answer(part_digit, number) global(str_part, str_answer, print_decimal, print_message) @cpy &str_part ~1 @call &print_message out part_digit @cpy &str_answer ~1 @call &print_message @cpy number ~1 @call &print_decimal out '\n' out '\n' @endfn @fn 0 init_xorshift(secret) global(int_to_bits, xorshift_state, memset) @cpy &xorshift_state ~1 @cpy 0 ~2 @cpy 24 ~3 @call &memset @cpy &xorshift_state ~1 @cpy secret ~2 @call &int_to_bits @endfn @raw pattern_id_dispatch: &get_pattern0_id &get_pattern1_id &get_pattern2_id &get_pattern3_id get_pattern_id: add &pattern_id_dispatch ~1 dispatch_ptr @jmp dispatch_ptr:*0 @fn 1 get_pattern0_id() global(pb0, pb1, pb2, pb3) add pb0 9 return0 mul return0 19 return0 add return0 pb1 return0 add return0 9 return0 mul return0 19 return0 add return0 pb2 return0 add return0 9 return0 mul return0 19 return0 add return0 pb3 return0 add return0 9 return0 @endfn @fn 1 get_pattern1_id() global(pb1, pb2, pb3, pb0) add pb1 9 return0 mul return0 19 return0 add return0 pb2 return0 add return0 9 return0 mul return0 19 return0 add return0 pb3 return0 add return0 9 return0 mul return0 19 return0 add return0 pb0 return0 add return0 9 return0 @endfn @fn 1 get_pattern2_id() global(pb2, pb3, pb0, pb1) add pb2 9 return0 mul return0 19 return0 add return0 pb3 return0 add return0 9 return0 mul return0 19 return0 add return0 pb0 return0 add return0 9 return0 mul return0 19 return0 add return0 pb1 return0 add return0 9 return0 @endfn @fn 1 get_pattern3_id() global(pb3, pb0, pb1, pb2) add pb3 9 return0 mul return0 19 return0 add return0 pb0 return0 add return0 9 return0 mul return0 19 return0 add return0 pb1 return0 add return0 9 return0 mul return0 19 return0 add return0 pb2 return0 add return0 9 return0 @endfn ###################### # @fn 0 process_monkey() local(itercount, price_count, price_head, prev_price, new_price, wrap_tmp, pattern_id) global(pattern_table, get_current_value, get_current_price, PUZZLE_ITERATIONS, xorshift_step, price_buffer, price_buffer_end, part1_answer, part2_answer, dle_output, monkey_count, get_pattern_id) add monkey_count 1 monkey_count #@cpy monkey_count ~1 #@call &dle_output #@call &get_current_value #@call &dle_output @cpy 0 price_head @cpy &price_buffer price_tail @cpy 0 price_count lt price_buffer dummy:0 dummy @call &get_current_price mul ~1 -1 prev_price @cpy PUZZLE_ITERATIONS itercount loop: @call &xorshift_step @call &get_current_price @cpy ~1 new_price # compute price delta add prev_price new_price prev_price #@cpy prev_price ~1 #@call &dle_output # write to price buffer @cpy prev_price price_tail:*0 # advance price_tail add price_tail 1 price_tail eq price_tail &price_buffer_end wrap_tmp mul wrap_tmp -4 wrap_tmp add wrap_tmp price_tail price_tail add price_count 1 price_count @jlt price_count 4 ¬_enough_prices @cpy price_head ~1 @call &get_pattern_id @cpy ~1 pattern_id #@call &dle_output mul pattern_id 2 pattern_id add pattern_id &pattern_table monkey_id_ptr_1 @cpy monkey_id_ptr_1 monkey_id_ptr_2 add 1 monkey_id_ptr_1 pattern_value_ptr_1 @cpy pattern_value_ptr_1 pattern_value_ptr_2 @cpy pattern_value_ptr_1 pattern_value_ptr_3 lt monkey_id_ptr_1:*0 monkey_count is_new_pattern_for_current_monkey @cpy monkey_count monkey_id_ptr_2:*0 mul new_price is_new_pattern_for_current_monkey:0 wrap_tmp add wrap_tmp pattern_value_ptr_1:*0 pattern_value_ptr_2:*0 @cpy pattern_value_ptr_3:*0 wrap_tmp @jge part2_answer wrap_tmp &no_new_winner @cpy wrap_tmp part2_answer no_new_winner: # advance price_head add price_head 1 price_head eq price_head 4 wrap_tmp mul wrap_tmp -4 wrap_tmp add wrap_tmp price_head price_head not_enough_prices: mul new_price -1 prev_price add itercount -1 itercount jt itercount &loop @call &get_current_value add part1_answer ~1 part1_answer #@call &dle_output @endfn @fn 0 debug_xorshift_register() global(xorshift_state) @cpy 24 counter @cpy &xorshift_state read_ptr loop: add read_ptr:*0 '0' ~1 out ~1 add read_ptr 1 read_ptr add counter -1 counter jt counter:0 &loop out '\n' @endfn ##################################### # # read_integer() # # reads a single integer on input, terminated by a newline. @fn 1 read_integer() local(accum, numcount, digcount, intmp) global(overflow_detected, internal_error, input_parse_error) @cpy 0 numcount #next_number: @cpy 0 accum @cpy 0 digcount seek_digit: in intmp @jeq intmp '\r' &seek_digit @jeq intmp '\n' &eol @jlt intmp '0' &nondigit @jle intmp '9' &process_digit nondigit: jt digcount &input_parse_error # NUL jf intmp &eof_detected # ctrl-Z @jeq intmp 26 &eof_detected # ctrl-D @jeq intmp 4 &eof_detected # EOF from getc() @jlt intmp 0 &eof_detected @jmp &input_parse_error @jmp &input_parse_error eol: eof_detected: @jmp &finis process_digit: @cpy accum accum_overflowcheck add 1 digcount digcount add -'0' intmp intmp mul 10 accum accum add accum intmp accum @jle accum accum_overflowcheck:0 &overflow_detected @jmp &seek_digit finis: @cpy accum return0 @endfn @fn 0 dle_output(n) out 16 out n @endfn ##################################### # # print_decimal(n) # # outputs 'n' in decimal ASCII @fn 0 print_decimal(n) global(print_next_decimal_digit, dle_mode) jf n &print_zero ############## NEGATIVE NUMBER SUPPORT # if you don't need negatives, comment out these instrucitons lt n 0 ~2 jf ~2 &positive out '-' mul n -1 n ############## END NEGATIVE NUMBER SUPPORT positive: @cpy n ~1 @cpy 1 ~2 @cpy &exitfun ~0 @jmp &print_next_decimal_digit print_zero: out '0' exitfun: @endfn @fn 1 print_next_decimal_digit(n, mask) local(dig, negmask) # PRECONDITIONS: n >= mask, mask is a power of 10 # POSTCONDITIONS: upon return, ~1 has all powers of 10 greater than mask removed @cpy n ~1 @jlt n mask &exitfn mul mask 10 ~2 @call &print_next_decimal_digit @cpy ~1 n mul mask -1 negmask @cpy '0' dig compute_digit: @jlt n mask &done_compute_digit add dig 1 dig add n negmask n @jmp &compute_digit done_compute_digit: out dig exitfn: @cpy n return0 @endfn ##################################### # # memset(ptr, val, count) @fn 0 memset(ptr, val, count) jf count &done @cpy ptr write_ptr loop: @cpy val write_ptr:*0 add write_ptr 1 write_ptr add count -1 count jt count &loop done: @endfn ##################################### # int_to_bits(buf_ptr, num) -> count_of_bits_written # # Convert an integer value into a bit string # # writes the bits that make up @num out to @buf_ptr, LSB-first (TODO: or should I do MSB-first?) # upon return, ~1 is the number of bits written (this will be 0 if num <= 0) # lightweight function with tail recursion int_to_bits: @cpy 1 ~3 @cpy 24 ~4 @jmp &int_to_bits_core ##################################### # int_to_bits_core(buf_ptr, num, pow2, buf_size) -> (count_of_bits_written, num_masked) # # Core to_bits implementation # # upon return, ~1 is the number of bits written (this will be 0 if num < pow2) and ~2 is num with all bits greater than or equal to pow2 masked out # GOTCHA: return parameters and incoming arguments share stack space, so return0 and return1 are aliased with buf_ptr and num, respectively # because of that, the parameter order was changed from "num, buf_ptr" to "buf_ptr, num" to avoid some juggling @fn 1 int_to_bits_core(buf_ptr, num, pow2, buf_size) local(bits_written) global(overflow_detected) @cpy 0 bits_written @jlt num pow2 &done # we need to write out at least one bit. if there's no room, report an error jf buf_size &overflow_detected # if there are any bits *higher* than pow2 set in num, we need to remove them @jle num pow2 &no_higher_bits # remove higher bits add 1 buf_ptr ~1 @cpy num ~2 mul pow2 2 ~3 add buf_size -1 ~4 @call &int_to_bits_core add bits_written ~1 bits_written @cpy ~2 num no_higher_bits: @cpy buf_ptr write_ptr lt num pow2 inverted_bit eq inverted_bit:0 0 write_ptr:*0 add bits_written 1 bits_written jt inverted_bit &done mul pow2 -1 subtract_mask add num subtract_mask:0 num done: @cpy bits_written return0 # num and return1 are aliases #@cpy num return1 @endfn ##################################### # xorshift_step # # UNROLLED VERSION # # based on some ideas from other 2024 puzzles, I was able to implement this using 57 instructions @fn 0 xorshift_step() global(xs00, xs01, xs02, xs03, xs04, xs05, xs06, xs07, xs08, xs09, xs10, xs11, xs12, xs13, xs14, xs15, xs16, xs17, xs18, xs19, xs20, xs21, xs22, xs23) eq xs23 xs17 xs23 eq xs23 0 xs23 eq xs22 xs16 xs22 eq xs21 xs15 xs21 eq xs20 xs14 xs20 eq xs19 xs13 xs19 eq xs18 xs12 xs18 eq xs17 xs11 xs17 eq xs16 xs10 xs16 eq xs15 xs09 xs15 eq xs14 xs08 xs14 eq xs13 xs07 xs13 eq xs12 xs06 xs12 eq xs11 xs05 xs11 eq xs11 0 xs11 eq xs10 xs04 xs10 eq xs09 xs03 xs09 eq xs08 xs02 xs08 eq xs07 xs01 xs07 eq xs06 xs00 xs06 eq xs00 xs05 xs00 eq xs01 xs06 xs01 eq xs02 xs07 xs02 eq xs03 xs08 xs03 eq xs04 xs09 xs04 eq xs05 xs10 xs05 eq xs06 xs11 xs06 eq xs07 xs12 xs07 eq xs08 xs13 xs08 eq xs08 0 xs08 eq xs09 xs14 xs09 eq xs09 0 xs09 eq xs10 xs15 xs10 eq xs10 0 xs10 eq xs11 xs16 xs11 eq xs12 xs17 xs12 eq xs13 xs18 xs13 eq xs14 xs19 xs14 eq xs15 xs20 xs15 eq xs16 xs21 xs16 eq xs17 xs22 xs17 eq xs18 xs23 xs18 eq xs23 xs12 xs23 eq xs22 xs11 xs22 eq xs21 xs10 xs21 eq xs20 xs09 xs20 eq xs19 xs08 xs19 eq xs18 xs07 xs18 eq xs17 xs06 xs17 eq xs16 xs05 xs16 eq xs15 xs04 xs15 eq xs14 xs03 xs14 eq xs13 xs02 xs13 eq xs12 xs01 xs12 eq xs11 xs00 xs11 # `eq` is XNOR, not XOR. the above logic leaves two registers inverted from their correct values. eq xs00 0 xs00 eq xs07 0 xs07 @endfn ##################################### # bits_to_int(buf_ptr, length) -> num # # Converts a bit string to an integer # # writes the bits that make up @num out to @buf_ptr, LSB-first (TODO: or should I do MSB-first?) # upon return, ~1 is the number of bits written (this will be 0 if num <= 0) #@fn 1 bits_to_int(buf_ptr, buf_len) local(bitval) # #@cpy buf_ptr read_ptr #@cpy 0 return0 #@cpy 1 bitval #jf buf_len &done #next_bit: # #mul read_ptr:*0 bitval read_bitval #add return0 read_bitval:0 return0 #mul bitval 2 bitval # #add read_ptr 1 read_ptr #add buf_len -1 buf_len #jt buf_len &next_bit #done: # #@endfn ##################################### # # get_current_price() -> price get_current_value: @cpy &xorshift_state ~1 @cpy 24 ~2 @jmp &bits_to_int ##################################### # # get_current_price() -> num @fn 1 get_current_price() local(accum, tmp) global(xs00, xs01, xs02, xs03, xs04, xs05, xs06, xs07, xs08, xs09, xs10, xs11, xs12, xs13, xs14, xs15, xs16, xs17, xs18, xs19, xs20, xs21, xs22, xs23) mul xs00 1 accum mul xs01 2 tmp add accum tmp accum mul xs02 4 tmp add accum tmp accum mul xs03 8 tmp add accum tmp accum mul xs04 6 tmp add accum tmp accum mul xs05 2 tmp add accum tmp accum mul xs06 4 tmp add accum tmp accum mul xs07 8 tmp add accum tmp accum mul xs08 6 tmp add accum tmp accum mul xs09 2 tmp add accum tmp accum mul xs10 4 tmp add accum tmp accum mul xs11 8 tmp add accum tmp accum mul xs12 6 tmp add accum tmp accum mul xs13 2 tmp add accum tmp accum mul xs14 4 tmp add accum tmp accum mul xs15 8 tmp add accum tmp accum mul xs16 6 tmp add accum tmp accum mul xs17 2 tmp add accum tmp accum mul xs18 4 tmp add accum tmp accum mul xs19 8 tmp add accum tmp accum mul xs20 6 tmp add accum tmp accum mul xs21 2 tmp add accum tmp accum mul xs22 4 tmp add accum tmp accum mul xs23 8 tmp add accum tmp accum # the largest possible value that accum can be is 115 # now, reduce modulo 10 lt 79 accum tmp mul tmp -80 tmp add accum tmp accum lt 39 accum tmp mul tmp -40 tmp add accum tmp accum lt 19 accum tmp mul tmp -20 tmp add accum tmp accum lt 9 accum tmp mul tmp -10 tmp add accum tmp return0 @endfn ##################################### # bits_to_int(buf_ptr, length) -> num # # Converts a bit string to an integer @fn 1 bits_to_int(buf_ptr, buf_len) local(bitval) @cpy buf_ptr read_ptr @cpy 0 return0 @cpy 1 bitval next_bit: mul read_ptr:*0 bitval read_bitval add return0 read_bitval:0 return0 mul bitval 2 bitval add read_ptr 1 read_ptr add buf_len -1 buf_len jt buf_len &next_bit @endfn ##################################### # # Print a message. @fn 0 print_message(str_ptr) local(str_len) @cpy str_ptr read_len_ptr @cpy read_len_ptr:*0 str_len jf str_len &done add str_ptr 1 read_ptr message_print_loop: add read_ptr:*0 0 ~1 add read_ptr 1 read_ptr out ~1 add str_len -1 str_len jt str_len &message_print_loop done: @endfn ##################################### # # error messages, etc. @raw errmsg_ptr:0 strlen:0 tmpchar:0 die_with_message: # @str puts a length prefix @cpy errmsg_ptr read_strlen add read_strlen:*0 0 strlen add 1 errmsg_ptr errmsg_reader message_print_loop: add errmsg_reader:*0 0 tmpchar add errmsg_reader 1 errmsg_reader out tmpchar add strlen -1 strlen jt strlen &message_print_loop hlt overflow_detected: @cpy &str_overflow_detected errmsg_ptr @jmp &die_with_message input_parse_error: @cpy &str_input_parse_error errmsg_ptr @jmp &die_with_message @str str_overflow_detected:"Integer overflow detected\n" @str str_input_parse_error:"Input parse error\n" @str str_part:"Part " @str str_answer:" answer: " @raw monkey_count: 0 @raw price_buffer: pb0:0 pb1:0 pb2:0 pb3:0 price_buffer_end: part1_answer: 0 part2_answer: 0 @raw xorshift_state: xs00:0 xs01:0 xs02:0 xs03:0 xs04:0 xs05:0 xs06:0 xs07:0 xs08:0 xs09:0 xs10:0 xs11:0 xs12:0 xs13:0 xs14:0 xs15:0 xs16:0 xs17:0 xs18:0 xs19:0 xs20:0 xs21:0 xs22:0 xs23:0 @raw &dle_mode &dle_output &debug_xorshift_register @raw pattern_table: 0