Hello all,
I have tried to solve this puzzle :
https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd74/00000000002b1353
But so far my code only pass the first test and then I got a WA.
I tested on Eclipse my code and I do not manage to find out what is wrong.
I can't tell if it is a format error or that my solution is wrong.
I have tested that I did not twice on the same cell of the pascal triangle
and also that two consecutive cells are connected.
Here is my code :
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
public class Solution {
public static void main(String[] args) {
Scanner scanner = new Scanner( System.in );
int T= scanner.nextInt();
for(int useCase = 0;useCase < T;useCase++) {
solve(scanner,useCase);
}
}
private static void solve(Scanner scanner,int useCase) {
int N= scanner.nextInt();
List<Cell> usedCells = new ArrayList<>();
Cell c = new Cell(0, 0);
c.findPath(N,usedCells);
System.out.println(String.format("Case #%s:", useCase+1));
System.err.println("N : "+N);
for(Cell ce : usedCells) {
System.out.println(String.format("%s %s",ce.row+1,ce.k+1));
}
}
}
class valueComparator implements Comparator<Cell>
{
public int compare(Cell c1, Cell c2)
{
return c2.getValue().compareTo(c1.getValue());
}
}
class Cell{
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + k;
result = prime * result + row;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Cell other = (Cell) obj;
if (k != other.k)
return false;
if (row != other.row)
return false;
return true;
}
int row;
int k;
int value;
List<Cell> adjacentCell = new ArrayList<>();
public Integer getValue() {
return this.value;
}
public Cell(int row,int k) {
this.row = row;
this.k = k;
this.value = ncr(row, k);
}
public boolean findPath(int n, List<Cell> usedCells) {
if(usedCells.size() > 499) return false;
n = n - this.value;
if(n<0) return false;
usedCells.add(this);
if(n==0) return true;
this.addOthersCells();
for(Cell c:
this.adjacentCell.stream().filter(s->!usedCells.contains(s)).collect(Collectors.toList()))
{
if(c.findPath(n, usedCells)) {
return true;
}
}
usedCells.remove(this);
return false;
}
public void addOthersCells() {
int row = Math.max(this.row-1,0);
int col = Math.max(this.k-1,0);
//Row above
if(this.row != row) adjacentCell.add(new Cell(row,col));
col = this.k > row ? row : this.k;
if(this.row != row || this.k != col) if(!adjacentCell.contains(new
Cell(row,col))) adjacentCell.add(new Cell(row,col));
//Same row
row = this.row;
col = Math.max(this.k-1,0);
if(this.k != col) if(!adjacentCell.contains(new
Cell(row,col)))adjacentCell.add(new Cell(row,col));
col = Math.min(this.k+1,row);
if(this.k != col) if(!adjacentCell.contains(new
Cell(row,col)))adjacentCell.add(new Cell(row,col));
//Row below
row = this.row+1;
col = this.k;
if(!adjacentCell.contains(new Cell(row,col)))adjacentCell.add(new
Cell(row,col));
col = this.k+1;
if(!adjacentCell.contains(new Cell(row,col)))adjacentCell.add(new
Cell(row,col));
Collections.sort(adjacentCell,new valueComparator());
}
static int factorial(int n) {
int f;
for(f = 1; n > 1; n--){
f *= n;
}
return f;
}
static int ncr(int n,int r) {
return factorial(n) / ( factorial(n-r) * factorial(r) );
}
}
Thank you for your help.
Regards
Quentin
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/7d86e542-6155-4df1-8991-875bb50ea3f0%40googlegroups.com.
