ivanseed / google-foobar-help Goto Github PK
View Code? Open in Web Editor NEWGuidance on how to tackle some of the foobar challenges.
Guidance on how to tackle some of the foobar challenges.
Hey,
Thanks so much for the info, I'm really close on this one thanks to you folks.
Unfortunately, I'm still failing tests 3, 9 and 10.
Anyone have any further insight into what is unique about those tests?
My solution attempt consists of two steps:
For the second step I am using the blossom algorithm by Jack Edmonds. However the test cases 3,4,5 seem to time out.
My questions:
For example you can pass all 5 test cases by recursively matching the node with the minimum edges with its neighbour with the minimum edges. However there are potential graphs for which this algorithms would fail:
# *3 *10
# / \ / \
# *2 *4 - *8 - *9 *11
# | | | |
# *1 *5 *15 *12
# | \ / | | \ /
# *0 *7-*6 *14-*13
# An adjacency list of the graph above. Numbers represent the indexes of the other nodes e.g. the first node [1] points to the second node [0,2,7] and the second node points back to the first node as well as the nodes at indexes 2 and 7
graph = [[1], [0, 2, 7], [1,3], [2,4], [3,8,5], [4,6,7], [5,7], [1,5,6], [4,9], [8,10,15], [9,11], [10,12], [11,13], [15,12,14], [15,13], [9,14,13]]
I have implemented your solution to the best of my ability, however I am only passing half of the tests.
Being as there is no output from the verify command, I'm unsure what I could possibly check for. Were you able to pass all the tests with your implementation of this solution ?
I found the solution for this problem a bit too slow (there can be 20*20 nodes and the solution is actually at least O(V^3)
where V=w*h
) and might give wrong result (not really sure). After passing the test, I'd like to share my solution.
It's actually pretty simple - you need to duplicate the original maze. Let's call the original maze M0
and the duplicate M1
(as the second layer). On top of all the other edges, for each wall in M0
, between P0
and P1
, you create a one-way edge of cost 1
from P0
into the corresponding P1'
in M1
, which is in the same position as P1
in M0
. This step makes traveling from M0
to M1
break exactly one wall. Then you only need to get the smaller one between the distance from the entrance of M0
to the exit of M0
(didn't break wall) and the distance from the entrance of M0
to the exit of M1
(break one wall).
There are ways to make it easier to implement but the second layer is the key.
I've come to the situation where for test 3 and 10 when multiplying f by r, f's columns do not match r's rows. f is a 4x4 and r is a 6x4 so the step of multiplying f x r cannot take place correctly.
Other than that, i'm passing all tests.
There is a problem on level 4 called "distract the guards" where it's about graph matching and math theory called distracted the guards. Although my code got AC but I've also found a counter case soon after submission. I figured out that I need some math theory expert to help me complete the puzzle and stop it from haunting me. (´・_・`)
Here's part of the problem: given a pair (x, y), f(x, y) = f(2x, y-x) if x < y else f(y, x). Determine if f(x, y) will end up in the state f(a, a). My partial solution determined it by considering if (x+y)/min(x,y) is a power of 2, but it fails in my custom case [9,15]. I had some discussions with others and figured out the correct determine function maybe (x+y)/gcd(x,y) intuitively, but we just can't find a solid proof to back it up. Thanks in advance to anyone who would share some thoughts about this problem.
I am solving "Bringing a gun to a guard fight" Level 4 problem. It would be great if you can add this problem. I am not able to understand this one, the problem statement is not clear to me, I have some doubts but no one to ask. I can't figure out how the sample output corresponds to the input.
I have a python solution and a java solution but both seem to be exceeding the time limit
can someone help me on the code ?
Python Code
from collections import deque
def memodict(f):
""" Memoization decorator for a function taking a single argument """
class memodict(dict):
def __missing__(self, key):
ret = self[key] = f(key)
return ret
return memodict().__getitem__
@memodict
def adjacent_to((maze_dim, point)):
neighbors = (
(point[0] - 1, point[1]),
(point[0], point[1] - 1),
(point[0], point[1] + 1),
(point[0] + 1, point[1]))
return [p for p in neighbors if 0 <= p[0] < maze_dim[0] and 0 <= p[1] < maze_dim[1]]
def removable(maz, ii, jj):
counter = 0
for p in adjacent_to(((len(maz), len(maz[0])), (ii, jj))):
if not maz[p[0]][p[1]]:
if counter:
return True
counter += 1
return False
def answer(maze):
path_length = 0
if not maze:
return
dims = (len(maze), len(maze[0]))
end_point = (dims[0]-1, dims[1]-1)
# list of walls that can be removed
passable_walls = set()
for i in xrange(dims[0]):
for j in xrange(dims[1]):
if maze[i][j] == 1 and removable(maze, i, j):
passable_walls.add((i, j))
shortest_path = 0
best_possible = dims[0] + dims[1] - 1
path_mat = [[None] * dims[1] for _ in xrange(dims[0])] # tracker matrix for shortest path
path_mat[dims[0]-1][dims[1]-1] = 0 # set the starting point to destination (lower right corner)
for wall in passable_walls:
temp_maze = maze
if wall:
temp_maze[wall[0]][wall[1]] = 0
stat_mat = [['-'] * dims[1] for _ in xrange(dims[0])] # status of visited and non visited cells
q = deque()
q.append(end_point)
while q:
curr = q.popleft()
if curr == (0,0):
break
for next in adjacent_to((dims, curr)):
if temp_maze[next[0]][next[1]] == 0: # Not a wall
temp = path_mat[curr[0]][curr[1]] + 1
if temp < path_mat[next[0]][next[1]] or path_mat[next[0]][next[1]] == None: # there is a shorter path to this cell
path_mat[next[0]][next[1]] = temp
if stat_mat[next[0]][next[1]] != '+': # Not visited yet
q.append(next)
stat_mat[curr[0]][curr[1]] = '+' # mark it as visited
if path_mat[0][0]+1 <= best_possible:
break
if shortest_path == 0 or path_mat[0][0]+1 < shortest_path:
shortest_path = path_mat[0][0]+1
return shortest_path
Java Code :
package googleTest;
public class Answer {
public static int answer(int[][] maze) {
// Your code goes here.
boolean[][] visited = new boolean[maze.length][maze[0].length];
return dfs(0, 0, true, visited, maze, 1);
}
private static int dfs(int x, int y, boolean allowRemove, boolean[][] visited, int[][] maze, int len){
if(x == maze.length - 1 && y == maze[0].length - 1){
return len;
}
int[] dx = {0, 0, -1, 1};
int[] dy = {-1, 1, 0, 0};
visited[x][y] = true;
int min = Integer.MAX_VALUE;
for(int i = 0; i < 4; i++){
int nx = dx[i] + x;
int ny = dy[i] + y;
if(nx < 0 || ny < 0 || nx >= maze.length || ny >= maze[0].length || visited[nx][ny]){
continue;
}
if(maze[nx][ny] == 0){
min = Math.min(dfs(nx, ny, allowRemove, visited, maze, len + 1), min);
}else if(allowRemove){
min = Math.min(dfs(nx, ny, false, visited, maze, len + 1), min);
}
if(min == maze.length + maze[0].length - 1){
break;
}
}
visited[x][y] = false;
return min;
}
public static void main(String[] args) {
int[][] maze1 = new int[][]{{ 0, 1, 1, 0},{ 0, 0, 0, 1 },{ 1, 1, 0, 0 },{ 1, 1, 1, 0 }};
System.out.println(answer(maze1));
int [][] maze2 = new int[][] {{0, 0, 0, 0, 0, 0}, {1, 1, 1, 1, 1, 0}, {0, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 1, 1}, {0, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0}};
System.out.println(answer(maze2));
}
}
I ma trying to follow the method given here. To calculate inverse of the matrix, what approach should I follow to maintain the output in Fractions of integers as given in post. Let me know if you need more details?
You were right about the videos being very helpful. Using the approach described there I was able to come up with a solution that almost satisfies the test. I started writing code 2.5 weeks ago, so I apologize for the overall unreadability. Please let me know if you have any thoughts regarding the case that I seem to be missing. And thank you for your time.
Python Code:
import sys
from fractions import Fraction
def matmult(a,b):
#the matmult function was post by Akavall and is more elegant than what I would have kludged together
#accessed 1/6/2017: http://stackoverflow.com/questions/10508021/matrix-multiplication-in-python
zip_b = zip(*b)
# uncomment next line if python 3 :
# zip_b = list(zip_b)
#print [[sum(ele_a*ele_b for ele_a, ele_b in zip(row_a, col_b))
#for col_b in zip_b] for row_a in a]
return [[sum(ele_a*ele_b for ele_a, ele_b in zip(row_a, col_b))
for col_b in zip_b] for row_a in a]
from copy import deepcopy
def invert(X):
"""
Invert a matrix X according to gauss-jordan elimination
In gauss-jordan elimination, we perform basic row operations to turn a matrix into
row-echelon form. If we concatenate an identity matrix to our input
matrix during this process, we will turn the identity matrix into our inverse.
X - input list of lists where each list is a matrix row
output - inverse of X
"""
#copy X to avoid altering input
#X = deepcopy(X)
#Get dimensions of X
rows = len(X)
cols = len(X[0])
#Get the identity matrix and append it to the right of X
#This is done because our row operations will make the identity into the inverse
identity = make_identity(rows,cols)
for i in xrange(0,rows):
X[i]+=identity[i]
i = 0
for j in xrange(0,cols):
#print("On col {0} and row {1}".format(j,i))
#Check to see if there are any nonzero values below the current row in the current column
zero_sum, first_non_zero = check_for_all_zeros(X,i,j)
#If everything is zero, increment the columns
#if zero_sum==0:
#if j==cols:
#return X
#raise Exception("Matrix is singular.")
#If X[i][j] is 0, and there is a nonzero value below it, swap the two rows
if first_non_zero != i:
X = swap_row(X,i,first_non_zero)
#Divide X[i] by X[i][j] to make X[i][j] equal 1
X[i] = [Fraction(m,X[i][j]) for m in X[i]]
#Rescale all other rows to make their values 0 below X[i][j]
for q in xrange(0,rows):
if q!=i:
scaled_row = [X[q][j] * m for m in X[i]]
X[q]= [X[q][m] - scaled_row[m] for m in xrange(0,len(scaled_row))]
#If either of these is true, we have iterated through the matrix, and are done
if i==rows or j==cols:
break
i+=1
#Get just the right hand matrix, which is now our inverse
for i in xrange(0,rows):
X[i] = X[i][cols:len(X[i])]
print X
return X
def check_for_all_zeros(X,i,j):
"""
Check matrix X to see if only zeros exist at or below row i in column j
X - a list of lists
i - row index
j - column index
returns -
zero_sum - the count of non zero entries
first_non_zero - index of the first non value
"""
non_zeros = []
first_non_zero = -1
for m in xrange(i,len(X)):
non_zero = X[m][j]!=0
non_zeros.append(non_zero)
if first_non_zero==-1 and non_zero:
first_non_zero = m
zero_sum = sum(non_zeros)
return zero_sum, first_non_zero
def swap_row(X,i,p):
"""
Swap row i and row p in a list of lists
X - list of lists
i - row index
p - row index
returns- modified matrix
"""
X[p], X[i] = X[i], X[p]
return X
def make_identity(r,c):
"""
Make an identity matrix with dimensions rxc
r - number of rows
c - number of columns
returns - list of lists corresponding to the identity matrix
"""
identity = []
for i in xrange(0,r):
row = []
for j in xrange(0,c):
elem = 0
if i==j:
elem = 1
row.append(elem)
identity.append(row)
return identity
def answer(m):
#m = [[0, 2, 1, 0, 0], [0, 0, 0, 3, 4], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
#m = [[0,1,0,0,0,1],[4,0,0,3,2,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
#m = [[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,1,0,0,0,1],[4,0,0,3,2,0]]
#m=[[0,0,1],[0,0,0],[1,0,0]]
#print m
x = 1
if len(m)==1:
return [1,1]
terminallist=[]
transientlist=[]
mrows = {}
mcols = {}
denominator = {}
relaventindex = []
#to identify null rows and columns
for i in xrange(len(m)):
mcols[i]=[]
if sum(m[i])>0:
denominator[i]=sum(m[i])
else:denominator[i]=1
for i in xrange(len(m)):
mrows[i]=m[i]
mrows[i][:]=[Fraction(x,denominator[i]) for x in mrows[i][:]]
for j in xrange(len(m)):
mcols[j].append(m[i][j])
#to identify terminal and transient operations
for i in xrange(len(m)):
if max(mrows[i])==0 and min(mrows[i])==0:
#if max(mcols[i]) != 0 or min(mcols[i]) != 0: #bounces unconnected locations
terminallist.append(i)
if max(mrows[i])!=0 or min(mrows[i])!=0:
transientlist.append(i)
new_order = terminallist+transientlist
#print new_order
#print "terminallist",terminallist
#print "transientlist", transientlist
#print "mrows",mrows
#print "mcols",mcols
#to build the matrices that will be dumped into gauss_jordan
modrows={}
modlist = []
m1=[[m[i][j] for j in new_order] for i in new_order]
#print "M1M1M1M1",m1
#print "MMMMMMMM",m
identitymat = make_identity(len(transientlist),len(transientlist))
Q = []
Qind=[]
for i in xrange(-len(transientlist),0,1):
templist =[]
tempind=[]
for j in xrange(-len(transientlist), 0, 1):
templist.append(m1[i][j])
tempind.append(i)
tempind.append(j)
Q.append(templist)
Qind.append(tempind)
#print Q
#print Qind
iminusQ = identitymat
for i in range(len(identitymat)):
for j in range(len(identitymat[0])):
iminusQ[i][j] = identitymat[i][j] - Q[i][j]
#print iminusQ
F= invert(iminusQ)
R= []
Rind = []
for i in xrange(-len(transientlist),0,1):
templist =[]
tempind=[]
for j in xrange(len(terminallist)):
templist.append(m1[i][j])
tempind.append(i)
tempind.append(j)
R.append(templist)
Rind.append(tempind)
#print R
#print Rind
FR = matmult(F,R)
#for i in xrange(len(FR[0])):
#FR[0][i]=FR[0][i].limit_denominator(100)
denlist = []
numlist = []
solution = []
for i in xrange(len(FR[0])):
denlist.append(FR[0][i].denominator)
for i in xrange(len(FR[0])):
numlist.append(FR[0][i]*max(denlist))
#print numlist
for i in xrange(len(FR[0])):
solution.append(numlist[i].numerator)
#print solution
solution.append(max(denlist))
print solution
print type(solution[1])
return solution
thanks for your detailed explanation. I got an issue regarding the F = (I-Q)^-1 calculation
once states are rearranged Q is [0,1|4,0]
but when you are going to calculate I-Q , Q is [0,1/2|4/9,0]
same for the I and R as well.
can you tell me the operation you did convert Q and I from first state to next state?
I feel this might be a basic operation that I missed.
Sorry for asking a dumb question.
Like others before, I'm having some trouble with doomsday_fuel. I've done my research on Markov Chains and feel like I have a pretty good understanding of them, and I'm using that to solve the problem.
I feel like I have everything right, but I'm missing test 8. I'm covering 1x1 chains, there don't seem to be any 2x2s (there are only 2 possible solutions to a 2x2, and I've tried hard-coding both)
Any ideas what I could be getting wrong?
Do you know any special input for the challenge ?
I use same method as you and I don't think my calculation is wrong because I got right answers for all the test cases except the 6th.
Now I got stuck, dont know what is wrong in my program.
I had one that would calculate the value at the coordinates of an arbitrarily large triangle of numbers like this
7
4 8
2 5 9
1 3 6 10
and they give you a coordinate like (3,2) and you need to answer 9.
theres a lot of different ways to solve, all pretty much revolving around series summing (the 4th number on the bottom row is 10 because its 4+3+2+1, etc). You can then use the diagonal run to get the coordinate value, based on the bottom row value.
Add more Google Foobar challenges if you have came across any others. Please follow the other examples as a guide on how to structure the guide, please do not post the exact answer in code.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.