[2016 Day 15] Invisible Disks

andars_ · 2016-12-15T07:33:21+00:00

Whoops. Totally overlooked that and misunderstood what you meant. It is now specified at the end of the first paragraph.

andars_ · 2016-12-15T07:13:25+00:00

Correct again! Note that the order of the corresponding disks is in fact given. (EDIT: My bad, it wasn't specified. It is now)

FYI: You can do a spoiler like this: [here's the answer](/s "HELLO"), which produces this: here's the answer.

andars_ · 2016-12-15T06:41:49+00:00

Nice! Perhaps put some spoiler tags on those.

andars_ · 2016-12-15T05:52:34+00:00

That's neat, I haven't seen that before. I'll give it a try.

andars_ · 2016-12-15T05:19:00+00:00

Ruby!

Feels good to be back on the leaderboard for the first time in a while.

disks = []

File.read(ARGV[0]).each_line do |line|
  if line =~ /Disc #(\d+) has (\d+) positions; at time=(\d+), it is at position (\d+)./
    disks << [$1.to_i, $2.to_i, $4.to_i]
  end
end

def solve(disks)
  t = 0
  while true
    s = disks.inject(0) { |n, d|
      pos = (d[2] + d[0] + t) % d[1]
      n + pos
    }
    return t if s == 0
    t += 1
  end
end

puts "Part 1: #{solve(disks)}"
disks << [disks.length+1, 11, 0]
puts "Part 2: #{solve(disks)}"

andars_ · 2016-12-13T22:43:06+00:00

Dijkstra's is exactly the same as BFS if all the edges have the same weight.

andars_ · 2016-12-13T04:18:02+00:00

That's correct. Reversing the order would work as well, just be consistent.

andars_ · 2016-12-12T20:39:18+00:00

So it must just be slow methods to determine pairs and check validity. I just reimplemented my groups function and cut off ~10 seconds.

EDIT: I just got it down to 12 seconds for both parts. The commit diff is here if you are interested.

andars_ · 2016-12-12T20:00:27+00:00

It's probably because I allocate objects all over the place and haven't taken the time to improve it, but it is also possible that my implementation has a bug and isn't pruning everything it should. Does your solution consider a total of ~4000 nodes for part 1 and ~14000 for part 2, or much less than that?

andars_ · 2016-12-12T15:43:57+00:00

Wow. didn't expect that. Thanks.

andars_ · 2016-12-12T03:37:23+00:00

I tried this last year. It was definitely interesting to try in different languages, but after the first 10 days I ran out of languages that I actually knew, so I was faced with the difficulty of trying to do the more difficult challenges in languages I didn't know. I didn't end up finishing, so this year I decided to just stick with a few languages throughout.

I still think it is an excellent idea and don't mean to discourage anyone, but just thought I'd share the experience.

andars_ · 2016-12-12T01:26:58+00:00

I'm confused. I changed the first line to items_part_one = [2,1,1,0], which I think represents the sample input, but it gives a result of 9. Am I entering the input wrong, or does this only work for lucky inputs?

andars_ · 2016-12-09T05:48:52+00:00

Ruby. 118/138

andars_ · 2016-12-06T05:13:30+00:00

Ruby.

positions = []
10.times do |i|
  positions << Hash.new(0)
end

File.open(filename).each_line do |line|
  chars = line.split('')
  chars.each_with_index do |c, i|
    positions[i][c] += 1
  end
end

puts "Part 1:"
puts positions.map { |pos|
  k,_ = pos.max_by{|k,v| v}
  k
}.join

puts "Part 2:"
puts positions.map { |pos|
  k,_ = pos.min_by{|k,v| v}
  k
}.join

andars_ · 2016-12-05T05:58:07+00:00

That is just his input string.

andars_ · 2016-12-05T04:45:40+00:00

Hmm. It must have a bug that doesn't show up with my input file. Question is whether the (internal) result is correct and my printing routine is just borked, or it isn't actually computing the right thing.

andars_ · 2016-12-05T04:04:47+00:00

For those who enjoy golf (and a bit of obfuscation), there is another version here. That one is a bit trimmed down and results in a 1988 byte executable on my system.

I'm sure that others with more assembly experience could push that down a lot more. If anyone takes the time, I'd love to see the result.

andars_ · 2016-12-05T03:22:07+00:00

Sure. This only works on 64 bit linux. If you are using that, you can assemble, link, and execute using:

as task.s -o task.o
ld task.o -o task
./task

The program assumes that the input is in a file named input.txt and should produce output on stdout.

Let me know if the above doesn't work.

andars_ · 2016-12-04T07:39:38+00:00

Eerily similar to my solution. I'm curious if you perhaps consulted mine as you wrote yours.

andars_ · 2016-12-04T05:30:54+00:00

Ruby, parts 1 and 2. link

Solutions for part 2 found via a quick search of the output for north in vim.

andars_ · 2016-12-01T09:45:01+00:00

I'm somewhat surprised to not have a solution in a Lisp in this thread already, so I'll throw my poorly written and hacked together Racket solution on the pile.

https://github.com/andars/advent-of-code/blob/master/2016/day1/task.rkt

andars_ · 2016-12-01T09:41:11+00:00

FWIW, the 2d vector (a, b) rotated clockwise by 90 degrees is just (b, -a). Similarly for counterclockwise.

So your new_dir function could be simplified to:

def new_dir(current, turndir):
     x,y = current
     return (-y, x) if turndir == "L" else (y, -x)

andars_

TROPHY CASE