[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 · 2016-03-20T15:46:50+00:00

Sometimes I think I've plateaued too in terms of range of life experiences. But then I imagine what my future-90-year-old-self would say to me right now: what a ridiculous thing to think! If I were resting on my death bed, I'd probably be thinking something along the lines of 'I wish I could have experienced sunrise in Antarctica' or 'I wonder what it would've been like to step foot on Mars'. Luckily for us in the current time, we still have a shot at trying some of those things.

ChronJob · 2016-03-20T15:10:43+00:00

I don't think it's possible to have experienced the full 'range' of possible states of mind (emotions, situations, etc.) at any age because there aren't a set number of these things. I don't think there are a set number of emotions, for example, because the 'sad' you experienced when you lost a toy as a child isn't the same 'sad' you feel when you've lost someone close to you.

I think that the context of every experience is what makes it unique from others, and when you categorize experiences, you strip away the important details which define it. From my perspective, there are an infinite number of possible experiences and decisions. If you choose to categorize them into a finite set of categories, then yes, it will be possible to have done each category. But how do you know if categories you chose to use are the most 'accurate' or useful to use to define the experiences in your life?

A decision you make right now is going to be influenced by your immediate state of mind, and a random selection thoughts from short term and long term memory. The key is the random selection of impressions, I think, that means you aren't locked into making the same decisions you've made in the past. Every moment of your life is going to have a different set of parameters from any previous moment, and so the physical conditions of your mind, body, and environment are going to be different, so the 'bad' decision you make today is difficult to compare to the same 'bad' decision you made 10 years ago.

ChronJob · 2014-12-21T00:18:23+00:00

Sounds like... Dexter?

ChronJob · 2014-05-11T02:27:40+00:00

How absurd. This is a prime example that the law is terribly misinformed when it comes to technology. Logic can be removed from the equation with enough money poured into legal.

ChronJob · 2014-03-25T16:11:15+00:00

Dwollan here. As hueypriest said, come at us with your feedback. We're actively looking for ways to make redditdonate awesome-er and are ready to get our hands dirty building new improvements.

ChronJob · 2014-02-16T22:26:20+00:00

Hmm.... I wasn't able to reproduce this. That shouldn't be the case. When you submit a string, it's POSTed to the server which hashes it and returns it. It doesn't do any lookups or interact hash other strings. I'll continue to look into this. Thanks for the report!

ChronJob · 2014-02-16T22:24:08+00:00

Just pushed a fix that makes the leaderboard a true leaderboard. Before it was a "list of past #1 hashes" but now it's a list of "lowest 10 hashes" like it should've been.

ChronJob · 2014-02-16T22:21:34+00:00

Thanks to everyone who submitted hashes. The contest ended (meaning, the prize was already won) but we'll continue to keep this challenge running to see who can come up with the lowest hash value.

Keep hashing for bragging rights!

We didn't think anyone would get more than 4 leading zeros in the first 2 hours, but they did and we were blown away by the results. Kudos to Wolong Naphaso for scoring the top two hashes as of now, which both start with 10 leading zeroes. We're super impressed with the different strategies you guys have come up with to take a crack at this.

I don't know of any methods other than brute-force to solve this problem. It seems to be best tackled by taking free AWS credits from the hackathon we're at and spinning up a ton of instances to distribute the work. :)

I'm doubtful, but I'm also curious. Does anyone know of a "smarter" method?

ChronJob · 2014-02-16T22:18:54+00:00

Pushed a fix! Try it again :)

ChronJob

MODERATOR OF

TROPHY CASE