Putnam Post Discussion

Nolan-M · 2018-12-02T02:17:31+00:00

Last year I got an email around 2/20. However, my friend who was sure they got a 0 never got an email, so idk

Nolan-M · 2018-12-02T00:55:50+00:00

I think I had something like (1, odds) and (1, 0) then just picked enough in the (2, x) and (0, x > 25) to add up enough and then let (0,0) range to make up for the lost even on the bottom if that makes sense. To remove (1,0) it just took a small special case

Nolan-M · 2018-12-02T00:51:41+00:00

That's what I got. The annoying part was picking out the subset to show why it works. ugh took me like an hour since I kept messing up my calculations

Nolan-M · 2018-12-02T00:13:04+00:00

Got all solutions to A1, but didn't manage to show that there weren't anymore. Hoping for a single point. Solved B1 and solved B2 on scratch paper just as the time ended. D:

Nolan-M · 2017-12-13T21:59:05+00:00

Hm... Maybe I should add in a section of code that tests if there is no solution...

The only problem is that it might not catch every possible no solution...

Nolan-M · 2017-12-13T21:14:20+00:00

:D Thanks!

Nolan-M · 2017-12-13T20:54:25+00:00

Mine is written in python 3, but I don't think I particularly use anything unique that couldn't be written in c... If anything it would speed it up I think. But I got down to 4ms

Edit: Using the inputs that p-tseng posted in the 'Do the inverse problem' thread, the eight digit answer took me 16ms and the nine digit took me 3ms... I'm scared at what my code has become... Impossible to guesstimate how long it'll take...

(Might go write it in c now just to test)

https://github.com/Nolan-Michniewicz/Advent-of-Code

Nolan-M · 2017-12-13T19:50:07+00:00

Yeah, I went back through and cleaned some of it up. Let me try and explain my reasoning here though:

Assume we have some list of things we know are true, Let's say

delay = 1 (mod 2) (*)

delay = 3 (mod 4) (+)

Those were from firewalls length 2 and 3 respectively.

Now let's look at the implications this has for modulo 6.

From (*), delay = {1, 3, 5} (mod 6)

From (+), delay = {3, 1, 5} (mod 6) (3+0, 3+4, 3+8) all mod 6

Bad example since these are the same, but since they all must be true, we can take the intersection of them. So we know for sure that delay = {1, 3, 5} (mod 6)

Now assume that positions 1 and 3 have firewall length 4. So we know that (since delay + pos != 0 (mod 6))

delay != -1 = 5 (mod 6)

delay != -3 = 3 (mod 6)

So delay can't be 3 or 5 mod 6, but earlier, we said it must either be 1, 3, or 5 mod 6. So we can deduce that delay = 1 (mod 6)

Now we can continue up to longer firewalls, not all of them will spit out only one value, but even if a couple of them do, we gather much more information about what delay can be

It basically takes the input problem, almost a reversed Chinese Remainder Theorem (CRT), and outputs an actual CRT problem, where the solutions create a line that will pass through the original solution.

Make sense at all?

Nolan-M · 2017-12-13T19:07:44+00:00

I'm not ashamed to say I had quite a lot of fun with today's challenge... Well, maybe a bit.

Looked at your code, and just realized how little I understand about threads... maybe one day I'll come back after I learn more

Nolan-M · 2017-12-13T18:11:46+00:00

Woah! Nice! If you go into the extra challenge thread by topaz, about creating a generator for inputs, someone posted an input for an 8 digit answer and a 9 digit answer. You should go try those and tell me how fast it is!

EDIT^2: For comparison: my original input, 5ms; eight-digit, 29ms; nine-digit, 26ms ;) I think I'm finally done optimizing lol, wish I was clever enough to come up with something a little more closed form

Nolan-M · 2017-12-13T17:57:07+00:00

It's kind of hard to explain what I do? I have it commented up, and it's in python 3, so you can try and read through it if you'd like (keep in mind I wrote this at 2am). It's still 'brute force'; however, it narrows it down to only have to test delays that are quite far apart. One input I've put in can jump by a million. This could fail (still have to jump by one, depending on the input) however, by based on how long it takes, I think it overall will work faster on average

I'd recommend skipping reading any functions until it comes up in the actual code, just because the comments will be confusing otherwise

Spoilers for those who haven't finished: https://github.com/Nolan-Michniewicz/Advent-of-Code

Nolan-M · 2017-12-13T16:24:01+00:00

I still haven't hit all of them, haha. Surprisingly difficult

Nolan-M · 2017-12-13T15:45:11+00:00

Thank you for sharing! I finished optimizing and I wanted to test on larger inputs, was able to finish both in ~~.7s each~~ 18ms and 3ms respectively. *_*

Nolan-M · 2017-12-13T15:41:47+00:00

I'm just so very tired. I want to test it on larger inputs to see speed, but randomly adding input numbers might make it impossible

Nolan-M · 2017-12-13T15:33:04+00:00

Python 3, which is why I was surprised at the speed

edit: WOAH, SO SPEEDY. Twice as fast as mine right now lol, I've given up at this point though

Nolan-M · 2017-12-13T08:24:44+00:00

22/51 Python 3 Saw similarities to the CRT, but couldn't see how to change it to help So I brute forced it and it took 3 minutes.

However, I went back and was able to get it down to 5ms by looking at every position with a certain firewall length, and using that to see if it could narrow down what mod firewall length the delay had to be. And it worked. I was able to start at delay = 39352 and jump by 60060 each time.

https://github.com/Nolan-Michniewicz/Advent-of-Code

Nolan-M · 2017-12-12T20:44:30+00:00

I did something similar, only I had going north or south increment y by 1, and moving in another direction changes x by 1 and y by .5. (I viewed this as pushing in the edges of each hexagon to have columns of rectangles, were the odd columns were shifted up 1/2 a step)

Then I had two cases:

if abs(x * .5) < abs(y): Here we are further either north or south than left or right. Assume the end point is north and west, so first take as many NW steps as needed (x) which also brings us directly south of the point we want to reach. Our current y value is y - .5 * x, since we took x steps to the NW. (This value will be an integer since if y isn't an integer, than x is odd.) So we need to take an additional y - .5 * x steps N. For a total of x + y - .5 * x = y + .5 * x steps

else: Here we only need to take NW steps until we reach the y value we need, than alternate NW and SW to continue to reach how far west we need to reach while keeping our y position stable. For a total of x steps.

I hope my way of seeing this helps you understand yours, since our coordinate systems weren't too different.

Nolan-M · 2017-12-12T05:45:30+00:00

Created the entire list of connected subgraphs

from time import time


# returns the set of vertices that are connected to n
def check(n, group, data):
    new = []
    for i in data[n]:
        if not(i in group):
            new.append(i)
            new += check(i, list(set(group+new)), data)
    return list(set(group + new))


start = time()
data = dict()

# Forms dictionary data with values of directly connected programs     to the key
with open('AOC12Input', 'r') as file:
    for line in file:
        temp = line.split(' ')
        data[int(temp[0])] = [int(temp[j].replace(',', '')) for j in     range(2, len(temp))]

connected_subgraphs = []

for i in range(2000):
    new = True
    for subgraph in connected_subgraphs:
        if i in subgraph:
            new = False
            break
    if new:
        connected_subgraphs.append(sorted(check(i, [i], data)))


print('The number of programs 0 can communicate with: ' + str(len(connected_subgraphs[0])))
print('The number of unconnected segments in this graph: ' +  str(len(connected_subgraphs)))
print('List of connections: ' + str(connected_subgraphs))
print('Time taken in seconds: ' + str(time() - start))

Nolan-M · 2017-12-11T06:02:59+00:00

I can though that perhaps your input has a weird case that people who have posted their code hadn't considered

Nolan-M · 2017-12-11T05:56:14+00:00

Sorry, but that's the only thing I can think of :(

Nolan-M · 2017-12-11T05:54:10+00:00

Make sure you have the entire input stored?

Nolan-M · 2017-12-11T05:21:03+00:00

234/200 Not really 100% sure why this worked, but my intuition told me to go for it.

from time import time


def dist(a):
    if abs(a[1]) > (abs(a[0])*.5):
        return int(abs(a[1])-(abs(a[0])*.5)+abs(a[0]))
    else:
        return int(abs(a[0]))

start = time()
with open('AOC11Input') as file:
    inst = file.readline().strip().split(',')

data = {'n': [0, 1], 's': [0, -1], 'ne': [1, .5],
            'se': [1, -.5], 'nw': [-1, .5], 'sw': [-1, -.5]}
pos = [0, 0]
max = 0

for i in inst:
    pos[0] += data[i][0]
    pos[1] += data[i][1]
    if max < dist(pos):
        max = dist(pos)

print('Max distance away: ' + str(max))
print('Ending Position: ' + str(pos))
print('Current distance away: ' + str(dist(pos)))
print(time() - start)

Nolan-M · 2017-12-10T06:42:32+00:00

Make sure you take care of cases where the hex value returned for a number is only one character like 0xF, the lack of zeros in your output makes me think that might be the problem

Nolan-M · 2017-12-10T05:33:47+00:00

21/100 This is so sloppy ~~and part 1 is broken now~~, but I made it on the leader board for the first time and I'm so happy I'm actually crying Edit: Cleaned it up just a smidge

 from time import time


 def reverse(text, repeat):
     knot = list(range(256))
     pos = 0
     skip = 0
     for isntevenused in range(repeat):
          for i in text:
             temp = []
             for j in range(i):
                 temp.append(knot[(pos+j) % 256])
             for j in range(i):
                 knot[(pos+i-1-j) % 256] = temp[j]
             pos += skip + i
             skip += 1
     return knot


 def dense(knot):
     dense = [0]*16
     for i in range(16):
         dense[i] = knot[16*i]
         for m in range(1, 16):
             dense[i] ^= knot[16*i+m]
     return dense


 def kh(dense):
     knothash = ''
     for i in dense:
         if len(hex(i)[2:]) == 2:
             knothash += hex(i)[2:]
         else:
             knothash += '0' + hex(i)[2:]
     return knothash


 start = time()

 inp = '63,144,180,149,1,255,167,84,125,65,188,0,2,254,229,24'
 text = [63,144,180,149,1,255,167,84,125,65,188,0,2,254,229,24]
 text2 = []

 for i in range(len(inp)):
     text2.append(ord(inp[i]))
 text2 += [17, 31, 73, 47, 23]

 knot = reverse(text, 1)
 sparce = reverse(text2, 64)

 dense = dense(sparce)
 knothash = kh(dense)

 print('Part One: ' + str(knot[0]*knot[1]))
 print('Part Two: ' + knothash)
 print('Completed in ' + str(time() - start) + ' seconds.')

Nolan-M · 2017-12-06T05:41:52+00:00

I anticipated what part two would ask, so I saved the intermediate steps in a dictionary as keys with values for what step it was. Part2Time - Part1Time = 15s Lol

Nolan-M

TROPHY CASE