Hacker News Reader

Comment by Chobilet | Hacker News Reader

Without going into spoilers, its interesting that people jumped to regex to solve this. For me that was a fairly non intuitive when I first saw the problem(both parts).

What jumped to me is the problem statement indicated a finite number of states and I crafted a solution based on that information. But its really cool to see how we all jump to different implementations.

View on HN

FWIW regex are also a DSL for finite state machines acting on strings, so in that light it’s a straightforward jump

While I didn't go with regexes per se, I did go with I think a fairly "standard" solution of iterating the string and finding matches, and got caught in the trap that a lot of people are mentioning.

In the end, I figured out a manual way around that, but then afterwards I realised that the iteration isn't really necessary given the problem at hand, and ended up going a completely different route that was a lot faster.

What surprised me is that I'd thought of the alternative at the start while reading the description, and then dismissed it because iteration is typically so convenient for these sorts of things.

I took one look at the overlaps, decided I had things I'd theoretically like to accomplish today that didn't involve tracking overlapping subsets of strings, and hardcoded the nine possible overlaps, i.e. [1]

[1] https://git.sr.ht/~bsprague/advent-of-code/tree/main/item/20...

I also started to write a finite state machine for part 2 but found it too tedious to craft by hand. How did you do it?

Not OP, but I too first thought of a state machine. As soon as I started to write it I realized I was over-solving a day-1 problem. So I switched to brute force

https://pastebin.com/r1jNCSdm

Once I get a line back from that, it's the same problem as part A.

Sorry all, I misused the word finite state. I meant it more from a combinatorics viewpoint(e.g. we only have X amount of operations per Y interval). You could consider my solution to be brute force code.

Abstractly I do this:

  read_file()
  lines = read_lines()
  sum = 0
  while lines:
    left = get_first_num_forwards(line)
    right = get_first_num_backwards(line)
    sum += integer(left+right)
  return sum

I define get_first_num() something like this:

  get_first_num(line):
    lowest_index_pair = None
    for key,val in dict.values():
       get_index_of_key_if_exists()
       if_exists: update_lowest_index_pair()
    index,num find_first_instance_num() //just gets the first num that appears
    update_lowest_index_pair()
    return lowest_index_pair[1]//just returns the number

Basically the idea is very similar to yours. We parse each line 11 times in both direction(10 per the word_vals dict and once more to find the index of the first numerical) which is only 22 parses. Then we grab the minimum index from this list and concat with the opposite side.

I just don't do any replacements at the cost of a longer run time. But I figure the cost of 11 parses was low enough that it wouldnt impact the run time significantly for this exercise.

The key point is that overlaps are not an issue because we check for string comparisons in the methods

That's ok, you misused the word 'word' to apply to 'finite' and 'state' :-P.

lol you know how it goes :). The mind does what it does.

I made use of the fact that "egrep -o [some regex]" will print the first (going left-to-right) match for the regex. So I ran egrep -o, and several other programs, once per line of input. (And to go from right to left, I used "rev" and an egrep on the reversed string.) My computer wept, but it worked.

  pbpaste | bash -c '
    tt=0
    while read x; do
      y=$(( 10 *
            $(echo $x |
              egrep -o "[0-9]|one|two|three|four|five|six|seven|eight|nine" |
              head -1 |
              sed -E "s/one/1/; s/two/2/; s/three/3/; s/four/4/; s/five/5/; s/six/6/; s/seven/7/; s/eight/8/; s/nine/9/")
          + $(echo $x |
              rev |
              egrep -o "[0-9]|eno|owt|eerht|ruof|evif|xis|neves|thgie|enin" |
              head -1 |
              rev |
              sed -E "s/one/1/; s/two/2/; s/three/3/; s/four/4/; s/five/5/; s/six/6/; s/seven/7/; s/eight/8/; s/nine/9/")))
      tt=$((tt+y))
    done
    echo $tt'

Reply on news.ycombinator.com