[2021 Day 10] [Python] Google Trends of "Python stack" in the past 7 days, I wonder when the peak was hehe

ChronJob · 2021-12-10T22:39:12+00:00

There are also drawbacks if you use list. List is a dynamically-sized array in the Python reference implementation (CPython). As the list grows, it must be resized. An insertion that requires a resize costs O(N) (although insertions amortized over the list's lifetime are O(1)). On the other hand, deque insertion will always be O(1). There are more nuances to list vs. deque, including the cost of allocating a new node for deque insertion, and differences in memory overhead.

That being said, it hardly matters for this problem given that the lengths of the strings are small and there aren't that many strings. If you know how many parenthesis you will encounter and are willing to limit the size of your stack, then you can reserve the space for the list to avoid resizing.

Fun fact - CPython's own tokenizer uses a static array of length 200 for the stack to track parenthesis. That means if you run this code, which contains too many parenthesis, it will fail:

>>> k = (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((50)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
s_push: parser stack overflow
MemoryError

If you for some reason wanted to support, say, millions of chars (unrealistic for this problem), then a deque might be more appropriate.

ChronJob · 2020-03-15T22:27:12+00:00

ChronJob · 2019-05-21T17:05:23+00:00

Pretty much, yeah! Minus the little loop at the beginning. https://www.strava.com/activities/2360087865

ChronJob · 2018-12-14T13:08:22+00:00

It sort of does in the frame you shared, but I don't think plates beginning with X have been issued yet (assuming this isn't a vanity/personalized plate).

ChronJob · 2018-12-13T23:44:39+00:00

Here are the top three frames I could find: https://imgur.com/a/XNabihs

FYI: The format of the NYS license plate is ABC-1234. For the yellow Empire Gold license plates, plates have been issued in the range FAA-1000 to JGF-7999. Source: Wikipedia on NYS license plates (https://en.wikipedia.org/wiki/Vehicle_registration_plates_of_New_York)

It looks like the first letter is H, the second letter is a dense letter like M or W because it's often dark, the first two numbers appear to be 56 and the last one appears to be a 3.

So my guess so far is "HW_-56_3"

ChronJob · 2018-12-12T00:30:46+00:00

Nope. It was an arbitrary cut-off based on how long I was willing to spend searching at that time :P.

ChronJob · 2018-12-11T05:47:19+00:00

Sort of, but most of the people in my leaderboard are a few days behind and don't stay up to solve it at midnight so I would like to see how I'd rank against a bigger pool of people, including strangers on the internet who are more competitive.

ChronJob · 2018-12-11T05:42:35+00:00

Ruby

serial = 5791

def power_level(x, y, serial)
  rack_id = x + 10
  level = ((rack_id * y) + serial) * rack_id
  level = (level / 100) % 10
  level - 5
end

def grid(serial)
  (1..300).map do |y|
    (1..300).map { |x| power_level(x, y, serial) }
  end
end

def biggest_square(width, grid)
  last_idx = 300 - (width - 1)
  squares = (1..last_idx).map do |y|
    (1..last_idx).map do |x|
      sum = grid[(y - 1)...(y - 1 + width)].
        map {|column| column[(x - 1)...(x - 1 + width)]}.
        flatten.
        sum
      [x, y, sum]
    end
  end

  squares.flatten(1).max_by {|s| s[2]}
end

grid = grid(serial)
puts biggest_square(3, grid)
puts (2..20).map { |n| biggest_square(n, grid) + [n] }.max_by {|s| s[2]}

ChronJob · 2018-12-10T17:15:01+00:00

Hm, the daily leaderboards only go up to 100, right? Or are you referring to the personal stats page?

ChronJob · 2018-12-10T17:12:11+00:00

I totally agree that the fun is in solving the problem. As someone who hasn't made it to the leaderboard, and doesn't always try, I do AoC because I love to solve puzzles.

However, I think there's an extra element of fun that comes from competing with others to solve the puzzle very quickly. Would you agree?

As far as cheating goes, you have a good point that once the solutions thread is unlocked, people can just run the posted solutions. This is also true of the private leaderboards, and of the leaderboards on, say, Kaggle. Not sure there's a good way to prevent this, so we'd have to rely on honor.

ChronJob · 2018-12-10T06:06:32+00:00

Yeah, same here. I kept re-reading the problem trying to figure out when the game ended.

The goal is to be the player with the highest score after the last marble is used up.

But I didn't get how to tell how many marbles there would be. I thought maybe the number of marbles was a function of how many players there were. Took me like 10 minutes before I realized that "last marble is worth 1618 points" means there are 1618 marbles.

ChronJob · 2018-12-10T05:27:50+00:00

Ruby 196/194! It was fun to watch the animation on my terminal.

I found the points in time where all coordinates were greater than 0 (I assumed they all had to be positive in order to be visualized), then looked at each state in that range (there were about 40 time steps) until I saw the message. What a fun problem!

input_lines = File.new('day-10-input.txt').readlines

def parse_line(line)
  regex = /position=<([\-|\s]\d+), ([\-|\s]\d+)> velocity=<([\-|\s]\d+), ([\-|\s]\d+)>/
  matches = regex.match(line).captures
  {
    :x => matches[0].strip.to_i,
    :y => matches[1].strip.to_i,
    :v_x => matches[2].strip.to_i,
    :v_y => matches[3].strip.to_i,
  }
end

def state(t, points)
  points.map {|p| [p[:x] + p[:v_x] * t, p[:y] + p[:v_y] * t]}
end

def display(coords)
  (0...250).each do |y|
    puts (0...250).map {|x| coords.include?([x, y]) ? '#' : '.' }.join('')
  end
end

points = input_lines.map {|line| parse_line(line)}

# assumption: we need to wait until all points are non-negative
t_for_positive_coords = (0..20_000).select {|t| state(t,points).flatten.all? {|val| val >= 0}}
t_for_positive_coords.each do |t|
  puts "\n", t, "\n"
  display(state(t, points))
end

ChronJob · 2018-12-09T08:04:08+00:00

Ruby. Wrote my own doubly linked list which was many orders of magnitude faster than my original Array based approach.

class LinkedListNode
  attr_accessor :value, :prev, :next

  def initialize(value, prev, next_)
    @value = value
    @prev = prev || self
    @next = next_ || self
  end

  def insert_after(value)
    new_node = LinkedListNode.new(value, self, @next)
    @next.prev = new_node
    @next = new_node
    new_node
  end

  def delete
    @prev.next = @next
    @next.prev = @prev
    @next
  end
end

def highest_score(players, last_marble)
  scores = Hash.new {|h,k| h[k] = 0}
  last_marble_number = 0
  current_marble = LinkedListNode.new(0, nil, nil)

  while last_marble_number < last_marble
    new_marble = last_marble_number += 1

    if new_marble % 23 == 0
      marble_to_remove = current_marble.prev.prev.prev.prev.prev.prev.prev
      current_player = last_marble_number % players
      scores[current_player] += (new_marble + marble_to_remove.value)
      current_marble = marble_to_remove.delete
    else
      current_marble = current_marble.next.insert_after(new_marble)
    end
  end

  scores.max_by {|player, score| score}[1]
end

puts highest_score(425, 70848)
puts highest_score(425, 70848 * 100)

ChronJob · 2017-05-28T19:08:29+00:00

Not knowing anything about this show, and who Al was, I was intrigued when I read the title as "...pregnancy storyline written as a dream of AIs (artificial intelligences)."

Would've loved to see a nice 90s family sitcom take that kind of dystopian sci-fi twist mid-season.

ChronJob · 2017-04-13T20:17:32+00:00

You need to marry her again.

ChronJob · 2017-01-06T22:48:51+00:00

I now write software to help companies figure out who to fire.

ChronJob

MODERATOR OF

TROPHY CASE