Commit 6c30fb3f by GovanifY

parent 83b24f81
.gitignore 0 → 100644
 hack/*
 # foobar My Solutions for the [Google Foobar](https://google.com/foobar) challenge, full writeup available [here](https://govanify.com/post/foobar/)
 from math import atan2, sqrt """ The first thing you had to realize in order to solve this challenge is that you could simply mirror the room and check if the beam gets where you want. Let me show you: In our case let us make a room of dimension [3,2], with the position of the target at [1,2]. For the sake of simplicity let us imagine the beam is shot at [1,2] and so we are trying to shot ourselves. We get something like this: ----- |*xx| |xxx| ----- If we shoot with a vector of [1,0], aka straight ahead, we will get this result: ----- |*~~| |xxx| ----- We can see that the beam gets back to you directly, thanks to the reflection, and that the goal is achieved! But there is another way to do that: ----- ----- |*~~| |~~*| |xxx| |xxx| ----- ----- We can here realize that, by putting a mirror version of the room where the beam gets, we can make a straight line instead of calculating the reflection and see that it gets to our original target, [1,2], being ourselves! The good thing with that is that it also allows us to determine the distance needed by the beam to get through, and thus we can mirror the rooms up to the maximum distance easily. The next thing to realize was that room mirrors in a pattern, see the below diagram: ----- |*xx| |xxx| ----- [...] ----- [...] |xxx| |*xx| ----- ----- ----- ----- ----- ----- |*xx| |xx*| |*xx| |xx*| |*xx| |xxx| |xxx| |xxx| |xxx| |xxx| ----- ----- ----- ----- ----- ----- |xxx| |*xx| ----- [...] ----- [...] |*xx| |xxx| ----- x always repeats in the same way, and so does y Thus we need to figure out how to calculate how to mirror one room twice and we can make an entire atlas of mirrored rooms! In our case though the function below only calculates the mirrors of the point of coordinates node across an atlas of length (distance*2)^2 """ def mirror_atlas(node, dimensions, distance): node_mirrored=[] for i in range(len(node)): points=[] # since it is floored we add 1, and python stops before the upper bound # so +2 in our case for j in range(-(distance//dimensions[i])-1, (distance//dimensions[i]+2)): points.append(get_mirror(j, node[i], dimensions[i])) node_mirrored.append(points) return node_mirrored # this simply calculates the mirror nth of a point in a 1D space def get_mirror(mirror, coordinates, dimensions): res=coordinates mirror_rotation=[2*coordinates, 2*(dimensions-coordinates)] if(mirror<0): for i in range(mirror, 0): res-=mirror_rotation[(i+1)%2] else: for i in range(mirror, 0, -1): res+=mirror_rotation[i%2] return res # pretty simple too: we get the angle at which the beam is needed to be to get # to the guard and store its distance. First we do that to yourself, then to the # guard and if the distance for the guard is lower than yourself then he'll be # hit first by the beam. def answer(dimensions, your_position, guard_position, distance): mirrored = [mirror_atlas(your_position, dimensions, distance),mirror_atlas(guard_position, dimensions, distance)] res=set() angles_dist={} for i in range(0, len(mirrored)): for j in mirrored[i][0]: for k in mirrored[i][1]: # position of the beam to touch the node, either yourself or the # guard beam=atan2((your_position[1]-k), (your_position[0]-j)) # pythagorean theorem gets you the hypothenuse given two points # of a triangle, which is basically the distance between those # two points l=sqrt((your_position[0]-j)**2 + (your_position[1]-k)**2) if [j,k] != your_position and distance >= l: if((beam in angles_dist and angles_dist[beam] > l) or beam not in angles_dist): if i == 0: angles_dist[beam] = l else: angles_dist[beam] = l # we could find a better result later so let's just # put that in a set to sort out duplicates res.add(beam) return len(res)
 from fractions import gcd """ Ah, combinatronics maths, always fun. Let's suppose we have two guards starting with a and b bananas, where we assume a > b Let k be the largest positive integer such that a > (2^k - 1)b If a = b(2^k - 2^(m-1) - 1) or a = b(2^(k+1) - 2^m - 1) for some integer m between 0 and k included then we can match the two guards to play an infinite round of thumb wrestling. We can thus deduce the formula below after development. """ def loops(x, y): res = (x+y)/gcd(x,y) return bool(res & (res - 1)) """ This function might looks like a bottleneck but we need to find a way to update node sizes either way, so i don't think a better way is possible at the time of writing. I might totally be wrong but for our use case arrays won't be bigger than 100 so *shrug* """ def remove(guards, ref): for i in range(len(guards)): j = 0 while j < len(guards[i]): if(guards[i][j]==ref): guards[i].pop(j) j+=1 guards[ref]=[-1] def answer(banana_list): guards= [[] for i in range(len(banana_list))] bad=0 for i in range(len(guards)): for j in range(len(guards)): if(loops(banana_list[i], banana_list[j])): guards[i].append(j) to_process=len(banana_list) while(to_process>0): # we first find the lesser used number min_num=0 for i in range(len(guards)): if(i!=0 and (len(guards[i])
 """ Almost no computation there, we get positions of arrows depending of their type sorted and then do two nested loops to detect collisions, can't think of anything better rn """ def answer(s): # readme.txt if(len(s) > 100 or len(s) < 1): raise ValueError('Height is outside of bounds') # we keep only the arrows and cast it into a list ot make it iterable easily s = list(s.replace("-","")) left = [] right = [] res=0 for i in range(0,len(s)): if s[i] == '<': left.append(i) if s[i] == '>': right.append(i) # two nested loops to detect collision for i in right: for y in left: if i < y: res+=1 for i in left: for y in right: if y < i: res+=1 return res
end.py 0 → 100644
 import base64 encrypted="HEYGAwIKCxQSUlZbSUkAExAXFU5CR0YWGQ0FCwYGABNGSVRHRhAFFQwLCgQRUU1JSQIHExkTHR1AQU9WRgAABBMQEggLAgJGWVZGCA0PCBAABAQLCRVSVltJSRIPGRkCAgsDRllWRhsPBQMcAhJOTl1BUgUADwtATVVRBwYBQEFPVkYeBwlAUgs=" my_eyes=str.encode("gauvain") decoded=base64.b64decode(encrypted) decrypted="" for i in range(0,len(decoded)): decrypted+=chr((my_eyes[i%len(my_eyes)] ^ decoded[i])) print(decrypted)
 """ The hard part of this challenge was figuring out how to make it in the time limit, much like the old XOR challenge. This one though was on another optimization technique, memoization(I see what you did there Google, challenges using the skills you ask for interviews on your website). Hashing the entire list would have been too long, even as a tuple, so instead we had to be clever and use another trick: building an history of all the moves that happened. This allows us, given a pair of row and column a and b, to avoid having to do extreme amount of recursive computation to get a result, as long as an history of the last (past grid row + current move) moves is saved. The rest of the problem is fairly easy: we recursively try out all possible combinations for this grid and save the number of correct ones we could get. """ def answer(state, a=0, b=0, past=0, solutions=0, history=0): if(past==0): past=[[True] * (len(state[0])+1) for i in range(len(state)+1)] solutions = {} history = [] if(b==len(state[0])+1): return True res=0 index=((a,b), tuple(history[-(len(state)+2):])) if index in solutions: return solutions[index] for cell in [True, False]: # either all True(c[0][0] and 1 cell) or all False (!c[0][0] and !1 cell) if (not a or not b) or len(set([((past[a][b-1] + past[a-1][b] + past[a-1][b-1] + cell)==1), state[a-1][b-1]]))==1: history.append(cell) past[a][b] = cell res+=answer(state, a=(a+1)%(len(state)+1), b=b+(a+1)//(len(state)+1), past=past, solutions=solutions, history=history) history.pop() solutions[index]=res return res
 """ This one was really simple, compared to the XORFest I did before: you just get all the pairs that divide themselves with a larger number after, then do the same again. There's really nothing else to say, weird to see that as a level 3 """ def answer(l): triples = 0 pairs = [0]*len(l) for i in range(1, len(l)-1): for j in range(i): if(l[i]%l[j]==0): pairs[i]+=1 for i in range(2, len(l)): for j in range(1, i): if(l[i]%l[j]==0): triples += pairs[j] return triples
 """ Logic is pretty much self explained there, complexity should be also fairly low, but heck was it tricky """ def answer(n): # n is given as a string so let's cast it n=int(n) res = 0 while(n!=1): # if our number is odd then let's just divide by 2 if(n%2==0): n=n/2 # now this is the tricky part and took me a bunch of googling to figure # out: instead of going the brute force O(n²) way and just trying out # every possibility in nested loops you can actually figure out if you # should add or remove: when rightmost bits are set as "111" the # preferred operation is to add, as that would push back everything as # 000s, while any other case would be faster the other way around. elif((n==3) or ((n+1)&n) > ((n-1)&(n-2))): n-=1 else: n+=1 res+=1 return res
 """ Creating a perfect tree and going through it would be way over the top for that, so we just do a recursive search calculating on the fly the values, which results in an O(log(n)) complexity """ def find_item(item,cur,dif): #the difference between the right node and the left #node is the floor of the right node divided by 2: since we have a perfect #tree our tree have the same number of nodes on the left side and right #side; as such dividing by 2 should get you to the left one. right_node=cur-1 left_node=right_node-dif//2 #Check readme.txt if(right_node==item or left_node==item): return cur else: #Cannot be on the right side, otherwise it'd be larger than the #top left node thanks to perfect trees properties. if(item<=left_node): return find_item(item,left_node,dif//2) else: return find_item(item,right_node,dif//2) #Check readme.txt for what this function does, almost no computation there def answer(h, q): #check readme.txt if(h > 30 or h < 1): raise ValueError('Height is outside of bounds') if(len(q) > 10000 or len(q) < 1): raise ValueError('Flux converters list is outside of bounds') #Note: A perfect binary tree has 2n+1-1 nodes, where n is the height #https://xlinux.nist.gov/dads/HTML/perfectBinaryTree.html items=(2**h)-1 array=[] for i in range(len(q)): if (q[i]0): array.append(find_item(q[i],items,items-1)) else: array.append(-1) return array
queue_to_do.py 0 → 100644
 """ This would have been fairly easy without the time limit but of course we must do some XOR regression bs to get it working. This was actually fairly simple maths once you think about it! XOR is a rotary operator when dealing with lists of following integer, ie: >>> 1 1 >>> 1^2 3 >>> 1^2^3 0 >>> 1^2^3^4 4 >>> 1^2^3^4^5 1 [...] And thus we can deduce a pattern, noted below as the xor_rotation. Thanks to that and XOR properties we can reduce the complexity of the original dumb "XOR EVERYTHING" down to an O(1) for each array, so we end up roughly having an O(length) complexity """ def xor(a, b): if(a%2==0): xor_rotation = [b, 1, b+1, 0] else: xor_rotation= [a, a^b, a-1, (a-1)^b] return xor_rotation[(b-a)%4] def answer(start, length): res=0 for i in range(0, length): res ^= xor(start+(length*i), start+(length*i)+(length-i)-1) return res
solar_doomsday.py 0 → 100644
 #I might over-comment those solutions since it might be #reviewed one day, so bear with me, reviewers! """ Gets the biggest square below or equal to max_number I'm sure it can be optimized but as we never get over 1M it should be largely fast enough for most cpus: ➜ /tmp time python2 tmp.py [1000000] python2 tmp.py 0.01s user 0.00s system 96% cpu 0.009 total The code is also more readable this way """ def get_biggest_square(max_number): n=1 while(n*n < max_number+1): n=n+1 return n-1 #Check readme.txt for an explaination of what this does. # "Heavy" computation is done in get_biggest_square def answer(area): #check readme.txt if(area > 1000000 or area < 1): raise ValueError('Area is outside of bounds') array=[] #no need to sort or do fancy pant stuff, we go from biggest to smallest in #a natural fashion this way while(area != 0): res=get_biggest_square(area) array.append(res*res) area-=res*res return array
Markdown is supported
0% or .
You are about to add 0 people to the discussion. Proceed with caution.
Finish editing this message first!