Interesting grid 16x16

Question

EDIT: A path, not a line --- it can rotate around and stuff. A path connects adjacent squares. You cannot go diagonally.

In addition, my proposed solution was an attempt to take each possible line from a 50-digit number, base 4 - so that you start from each square and move left, right, up or down --- in every possible 4 ^ 50 combination

This problem asks you to find the largest sum of 50 numbers that can be connected by without intersecting diagonally in this 16x16 grid:

{{50,54,46,55,45,56,44,53,47,59,41,60,40,59,41,59}, {47,57,46,49,52,46,53,47,53,41,59,40,60,41,59,41}, {56,42,54,51,48,54,47,53,53,57,48,54,49,57,46,59}, {48,50,52,54,56,58,57,47,48,49,48,47,46,53,52,51}, {50,56,50,48,49,50,51,59,42,60,39,62,38,63,38,50}, {60,40,50,50,50,50,60,40,55,45,55,45,56,44,56,44}, {60,45,46,37,56,50,43,39,50,53,56,39,50,58,39,49}, {26,56,54,38,48,50,67,64,32,54,50,49,48,47,46,45}, {28,45,35,57,54,34,34,32,64,57,58,74,24,64,34,50}, {40,50,60,54,45,56,46,47,35,36,39,27,38,50,51,52}, {29,38,47,58,48,37,50,58,37,46,50,50,50,50,50,50}, {47,48,49,50,52,65,64,52,49,47,43,47,58,46,30,32}, {59,47,47,56,65,34,45,56,75,24,35,45,56,65,50,54}, {53,46,35,45,29,46,46,50,23,32,40,46,64,64,64,20}, {53,54,56,58,60,43,43,34,34,35,64,30,50,40,49,59}, 

This algorithm tries to use random paths and rotates after each of the 50 steps up, right, down, left - without crossing itself. I get about 2750, but I need at least 2800 to complete the task. // lol

 import java.util.ArrayList; public class lol { private int[][] square = {{50,54,46,55,45,56,44,53,47,59,41,60,40,59,41,59}, {47,57,46,49,52,46,53,47,53,41,59,40,60,41,59,41}, {56,42,54,51,48,54,47,53,53,57,48,54,49,57,46,59}, {48,50,52,54,56,58,57,47,48,49,48,47,46,53,52,51}, {50,56,50,48,49,50,51,59,42,60,39,62,38,63,38,50}, {60,40,50,50,50,50,60,40,55,45,55,45,56,44,56,44}, {60,45,46,37,56,50,43,39,50,53,56,39,50,58,39,49}, {26,56,54,38,48,50,67,64,32,54,50,49,48,47,46,45}, {28,45,35,57,54,34,34,32,64,57,58,74,24,64,34,50}, {40,50,60,54,45,56,46,47,35,36,39,27,38,50,51,52}, {29,38,47,58,48,37,50,58,37,46,50,50,50,50,50,50}, {47,48,49,50,52,65,64,52,49,47,43,47,58,46,30,32}, {59,47,47,56,65,34,45,56,75,24,35,45,56,65,50,54}, {53,46,35,45,29,46,46,50,23,32,40,46,64,64,64,20}, {53,54,56,58,60,43,43,34,34,35,64,30,50,40,49,59}, {52,12,17,50,63,62,62,64,50,51,52,57,43,44,42,69}}; ; public static void main(String [] args) { lol lol1 = new lol(); } public lol() { ArrayList<Integer> record = new ArrayList<Integer>(); int max =0; for(int count = 0; count<10000; count++) { for(int startx=0; startx<16; startx++) { for(int starty =0; starty<16; starty++) { int[] pos = new int[2]; pos[0] = starty; pos[1] = startx; ArrayList<Integer> past = new ArrayList<Integer>(); int total = 0; for(int i=0; i<50; i++) { int random = (int)(Math.random()*4); int switchcount = 0; past.add(100*pos[0] + pos[1]); total+= square[pos[0]][pos[1]]; if(random == 0) { if(pos[0] == 0 || checkexists((pos[0]-1)*100+pos[1],past)) { random++; switchcount++; } else { pos[0]--; } } if(random == 1) { if(pos[0] == 15 || checkexists((pos[0]+1)*100+pos[1],past)) { random++; switchcount++; } else { pos[0]++; } } if(random == 2) { if(pos[1] == 0 || checkexists((pos[0])*100+pos[1]-1,past)) { random++; switchcount++; } else { pos[1]--; } } if(random == 3) { if(pos[1] == 15 || checkexists((pos[0])*100+pos[1]+1,past)) { if(switchcount >= 3) { break; } else { random = 0; if(pos[0] == 0 || checkexists((pos[0]-1)*100+pos[1],past)) { random++; switchcount++; } else { pos[0]--; } if(random == 1) { if(pos[0] == 15 || checkexists((pos[0]+1)*100+pos[1],past)) { random++; switchcount++; } else { pos[0]++; } } if(random == 2) { if(pos[1] == 0 || checkexists((pos[0])*100+pos[1]-1,past)) { break; } else { pos[1]--; } } } } else { pos[1]++; } } } if (total>max) { max = total; record = past; } } } } for(int p = 0; p<record.size(); p++) { System.out.println(record.get(p)); } System.out.println("\n\n" + max); } public boolean checkexists(int pos, ArrayList<Integer> past) { for(int i=0; i<past.size(); i++) { if(past.get(i) == pos) { //System.out.println("TRUE"); return true; } } return false; } } 

This is my attempt at a complete solution - she is trying to take every possible line from the 50-digit base number 4 - so that you start from each square and move left, right, up or down - each possible 4 ^ 50 combination

 import java.util.ArrayList; public class lol2 { private int[][] square = {{50,54,46,55,45,56,44,53,47,59,41,60,40,59,41,59}, {47,57,46,49,52,46,53,47,53,41,59,40,60,41,59,41}, {56,42,54,51,48,54,47,53,53,57,48,54,49,57,46,59}, {48,50,52,54,56,58,57,47,48,49,48,47,46,53,52,51}, {50,56,50,48,49,50,51,59,42,60,39,62,38,63,38,50}, {60,40,50,50,50,50,60,40,55,45,55,45,56,44,56,44}, {60,45,46,37,56,50,43,39,50,53,56,39,50,58,39,49}, {26,56,54,38,48,50,67,64,32,54,50,49,48,47,46,45}, {28,45,35,57,54,34,34,32,64,57,58,74,24,64,34,50}, {40,50,60,54,45,56,46,47,35,36,39,27,38,50,51,52}, {29,38,47,58,48,37,50,58,37,46,50,50,50,50,50,50}, {47,48,49,50,52,65,64,52,49,47,43,47,58,46,30,32}, {59,47,47,56,65,34,45,56,75,24,35,45,56,65,50,54}, {53,46,35,45,29,46,46,50,23,32,40,46,64,64,64,20}, {53,54,56,58,60,43,43,34,34,35,64,30,50,40,49,59}, {52,12,17,50,63,62,62,64,50,51,52,57,43,44,42,69}}; public static void main(String [] args) { lol2 lol1 = new lol2(); } public lol2() { ArrayList<Integer> record = new ArrayList<Integer>(); int max =0; for(int count = 0; count<10000; count++) { for(int startx=0; startx<16; startx++) { for(int starty =0; starty<16; starty++) { for(int a1 = 0; a1 <4; a1++) { for(int a2 = 0; a2 <4; a2++) { for(int a3 = 0; a3 <4; a3++) { for(int a4 = 0; a4 <4; a4++) { for(int a5 = 0; a5 <4; a5++) { for(int a6 = 0; a6 <4; a6++) { for(int a7 = 0; a7 <4; a7++) { for(int a8 = 0; a8 <4; a8++) { for(int a9 = 0; a9 <4; a9++) { for(int a10 = 0; a10 <4; a10++) { for(int a11 = 0; a11 <4; a11++) { for(int a12 = 0; a12 <4; a12++) { for(int a13 = 0; a13 <4; a13++) { for(int a14 = 0; a14 <4; a14++) { for(int a15 = 0; a15 <4; a15++) { for(int a16 = 0; a16 <4; a16++) { for(int a17 = 0; a17 <4; a17++) { for(int a18 = 0; a18 <4; a18++) { for(int a19 = 0; a19 <4; a19++) { for(int a20 = 0; a20 <4; a20++) { for(int a21 = 0; a21 <4; a21++) { for(int a22 = 0; a22 <4; a22++) { for(int a23 = 0; a23 <4; a23++) { for(int a24 = 0; a24 <4; a24++) { for(int a25 = 0; a25 <4; a25++) { for(int a26 = 0; a26 <4; a26++) { for(int a27 = 0; a27 <4; a27++) { for(int a28 = 0; a28 <4; a28++) { for(int a29 = 0; a29 <4; a29++) { for(int a30 = 0; a30 <4; a30++) { for(int a31 = 0; a31 <4; a31++) { for(int a32 = 0; a32 <4; a32++) { for(int a33 = 0; a33 <4; a33++) { for(int a34 = 0; a34 <4; a34++) { for(int a35 = 0; a35 <4; a35++) { for(int a36 = 0; a36 <4; a36++) { for(int a37 = 0; a37 <4; a37++) { for(int a38 = 0; a38 <4; a38++) { for(int a39 = 0; a39 <4; a39++) { System.out.println("SPAM"); for(int a40 = 0; a40 <4; a40++) { for(int a41 = 0; a41 <4; a41++) { for(int a42 = 0; a42 < 4; a42++){ for(int a43=0; a43<4; a43++){ for(int a44 =0; a44<4; a44++){ for(int a45=0; a45<4; a45++){ for(int a46=0; a46<4; a46++){ for(int a47=0; a47<4; a47++){ for(int a48=0; a48<4; a48++){ for(int a49=0; a49<4; a49++){ for(int a50=0; a50<4; a50++){ int[] pos = new int[2]; pos[0] = starty; pos[1] = startx; ArrayList<Integer> past = new ArrayList<Integer>(); int total = 0; String path = "" + a1 + a2+a3+a4+a5+a6+a7+a8+a9+a10+a11+a12+a13+a14+a15+a16+a17+a18+a19+a20+a21+a22+a23+a24+a25+a26+a27+a28+a29+a30+a31+a32+a33+a34+a35+a36+a37+a38+a39+a40+a41+a42+a43+a44+a45+a46+a47+a48+a49+a50; for(int i =0; i<50; i++) { int random = Integer.parseInt(path.substring(i,i+1)); int switchcount = 0; past.add(100*pos[0] + pos[1]); total+= square[pos[0]][pos[1]]; if(random == 0) { if(pos[0] == 0 || checkexists((pos[0]-1)*100+pos[1],past)) { random++; switchcount++; } else { pos[0]--; } } if(random == 1) { if(pos[0] == 15 || checkexists((pos[0]+1)*100+pos[1],past)) { random++; switchcount++; } else { pos[0]++; } } if(random == 2) { if(pos[1] == 0 || checkexists((pos[0])*100+pos[1]-1,past)) { random++; switchcount++; } else { pos[1]--; } } if(random == 3) { if(pos[1] == 15 || checkexists((pos[0])*100+pos[1]+1,past)) { if(switchcount >= 3) { break; } else { random = 0; if(pos[0] == 0 || checkexists((pos[0]-1)*100+pos[1],past)) { random++; switchcount++; } else { pos[0]--; } if(random == 1) { if(pos[0] == 15 || checkexists((pos[0]+1)*100+pos[1],past)) { random++; switchcount++; } else { pos[0]++; } } if(random == 2) { if(pos[1] == 0 || checkexists((pos[0])*100+pos[1]-1,past)) { break; } else { pos[1]--; } } } } else { pos[1]++; } } } if (total>max) max = total;f } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } for(int p = 0; p<record.size(); p++) { System.out.println(record.get(p)); } System.out.println("\n\n" + max); } public boolean checkexists(int pos, ArrayList<Integer> past) { for(int i=0; i<past.size(); i++) { if(past.get(i) == pos) { //System.out.println("TRUE"); return true; } } return false; } /*public ArrayList<String> setint() { ArrayList<String> bob = new ArrayList<String>(); for(BigInteger i =1267650600228229401496703205376; ; i<2535301200456458802993406410752; i++) { String number = i + ""; bob.add(BigInteger.toString(BigInteger.parseInt(number, 10), 4)); } return bob; } */ 

}

Answer 1

EDIT: Here is a sample code demonstrating some of the methods I described. He solves this problem quite well. During the experiments, I found some improvements that are not contained in the code below. Increasing the speed / effectiveness of this program by 100% is possible, but is left as an exercise for any future reader.

 import java.util.*; public class SquareSolver { /** * The LRU_Cache data structure is useful in a LOT of optimization problems, where storing all the problems you've solved so far * is infeasible, but there significant time savings to be had if your program can * realize "Wait, I've solved this sub-problem already", and just re-use earlier answers. * It stores things, until it gets above LRUCacheSize, then it automatically ejects the least recently used entry. * This is strictly an optimization, because things get ejected from the cache automatically, you should not rely on * presence (or not) of an element for correctness. */ private HashMap<Integer, LRUCache> leastRecentlyUsedCache; private Map<Integer, Integer> bestShortPathScores; private Map<Integer, Integer> depthEarlyCutoffsMap; private Map<Integer, Integer> depthCacheHitsMap; private int squareSize, targetLength; private Map<Coords, Integer> coordScores; private Set<Coords> neighborOffsets; private Path bestPath; private boolean isLongPath; private long startTime; private long timeout; private class LRUCache extends LinkedHashMap<Path, Integer>{ private int LRUCacheSize; LRUCache(int LRUCacheSize){ super(LRUCacheSize * 4 / 3, 0.75f, true); this.LRUCacheSize = LRUCacheSize; } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > LRUCacheSize; } } public SquareSolver(int LRUCacheSize, int squareSize, int targetLength) { neighborOffsets = new HashSet<>(Arrays.asList(new Coords[]{new Coords(-1, 0), new Coords(1, 0), new Coords(0, -1), new Coords(0, 1)})); this.targetLength = targetLength; this.squareSize = squareSize; leastRecentlyUsedCache = new HashMap<>(); for(int i = 0; i <= targetLength; i++) { leastRecentlyUsedCache.put(i, new LRUCache(LRUCacheSize / targetLength)); } coordScores = new HashMap<>(); } public static void main(String[] args) { int[][] testSquare = new int[][]{ {50, 54, 46, 55, 45, 56, 44, 53, 47, 59, 41, 60, 40, 59, 41, 59}, {47, 57, 46, 49, 52, 46, 53, 47, 53, 41, 59, 40, 60, 41, 59, 41}, {56, 42, 54, 51, 48, 54, 47, 53, 53, 57, 48, 54, 49, 57, 46, 59}, {48, 50, 52, 54, 56, 58, 57, 47, 48, 49, 48, 47, 46, 53, 52, 51}, {50, 56, 50, 48, 49, 50, 51, 59, 42, 60, 39, 62, 38, 63, 38, 50}, {60, 40, 50, 50, 50, 50, 60, 40, 55, 45, 55, 45, 56, 44, 56, 44}, {60, 45, 46, 37, 56, 50, 43, 39, 50, 53, 56, 39, 50, 58, 39, 49}, {26, 56, 54, 38, 48, 50, 67, 64, 32, 54, 50, 49, 48, 47, 46, 45}, {28, 45, 35, 57, 54, 34, 34, 32, 64, 57, 58, 74, 24, 64, 34, 50}, {40, 50, 60, 54, 45, 56, 46, 47, 35, 36, 39, 27, 38, 50, 51, 52}, {29, 38, 47, 58, 48, 37, 50, 58, 37, 46, 50, 50, 50, 50, 50, 50}, {47, 48, 49, 50, 52, 65, 64, 52, 49, 47, 43, 47, 58, 46, 30, 32}, {59, 47, 47, 56, 65, 34, 45, 56, 75, 24, 35, 45, 56, 65, 50, 54}, {53, 46, 35, 45, 29, 46, 46, 50, 23, 32, 40, 46, 64, 64, 64, 20}, {53, 54, 56, 58, 60, 43, 43, 34, 34, 35, 64, 30, 50, 40, 49, 59}, {52, 12, 17, 50, 63, 62, 62, 64, 50, 51, 52, 57, 43, 44, 42, 69}}; SquareSolver testSolver = new SquareSolver(500 * 1000, 16, 50); Path bestPath = testSolver.solveSquare(testSquare, 30 * 1000); System.out.println("Best Score:\t" + bestPath.getScore()); System.out.println("Best Path:\t" + bestPath.toString()); } private boolean inSquare(Coords coords) { int x = coords.getX(); int y = coords.getY(); return x >= 0 && y >= 0 && x < squareSize && y < squareSize; } public void solveSquareHelper(Path currentPath) { // Base Case if (currentPath.size() == targetLength) { synchronized (bestPath) { if (currentPath.getScore() > bestPath.getScore()) { System.out.print("."); bestPath = currentPath; } } return; } // Don't run forever. if (System.currentTimeMillis() > startTime + timeout){ return; } // Least Recently Used Cache can save us a lot of work if (lru_hit(currentPath)) { return; } // Early Cutoff can save us a lot of work too if (can_early_cutoff(currentPath)) { return; } // Recursive Case expandLegalNeighbors(currentPath); } private void expandLegalNeighbors(Path currentPath) { Coords currentCoords = currentPath.getCurrentCoords(); neighborOffsets.stream() .map(currentCoords::add) // Get all neighbors of current coords .filter(this::inSquare) // Filter out coords outside the square .filter(currentPath::doesNotContain) // Filter out coords already in currentPath .sorted(Comparator.comparing(Coords::getProximityToOrigin)) // This order maximizes the usefulness of LRUCache .forEachOrdered(neighbor -> solveSquareHelper(new Path(currentPath, neighbor))); } private boolean can_early_cutoff(Path currentPath) { int futurePathLength = targetLength - currentPath.size(); int upperBoundFutureScore = bestShortPathScores.get(futurePathLength); if (currentPath.getScore() + upperBoundFutureScore <= bestPath.getScore()) { depthEarlyCutoffsMap.put(currentPath.size(), depthEarlyCutoffsMap.get(currentPath.size()) + 1); return true; } else { return false; } } private boolean lru_hit(Path currentPath) { LRUCache currentDepthCache = leastRecentlyUsedCache.get(currentPath.size()); if (currentDepthCache.containsKey(currentPath)) { depthCacheHitsMap.put(currentPath.size(), depthCacheHitsMap.get(currentPath.size()) + 1); currentDepthCache.put(currentPath, currentDepthCache.get(currentPath) + 1); return true; } else { currentDepthCache.put(currentPath, 0); } return false; } public Path solveSquare(int[][] square, long timeout){ Map<Integer, Integer> smallPathScores = new HashMap<>(); smallPathScores.put(1, -10); for(int i =0; i < squareSize; i++){ for(int j = 0; j < squareSize; j++){ if(square[i][j] > smallPathScores.get(1)){ smallPathScores.put(1, square[i][j]); } } } Coords fakeCoords = new Coords(-10, -10); coordScores.put(fakeCoords, -10); Path bestSmallPath = new Path(fakeCoords); for(int i = 2; i < targetLength; i++){ SquareSolver smallSolver = new SquareSolver(500 * 1000, squareSize, i); bestSmallPath = smallSolver.solveSquare(square, timeout * i, smallPathScores, bestSmallPath); smallPathScores.put(i, bestSmallPath.getScore()); System.gc(); } return solveSquare(square, timeout * targetLength, smallPathScores, bestSmallPath); } public Path solveSquare(int[][] square, long timeout, Map<Integer, Integer> shortPathScores, Path initialBestPath) { bestPath = initialBestPath; bestShortPathScores = shortPathScores; System.out.println("=============================Target Length:\t" + targetLength + "(Timeout:\t" + timeout/60000.0 + " minutes)==========================="); System.out.println("Best Short Path Scores (for early cutoff):\t" + bestShortPathScores); startTime = System.currentTimeMillis(); this.timeout = timeout; depthCacheHitsMap = new HashMap<>(); depthEarlyCutoffsMap = new HashMap<>(); for (int i = 1; i < targetLength; i++) { depthCacheHitsMap.put(i, 0); depthEarlyCutoffsMap.put(i, 0); } for (int i = 0; i < squareSize; i++) { for (int j = 0; j < squareSize; j++) { coordScores.put(new Coords(i, j), square[i][j]); } } System.out.print("Expanding from best shorter node"); expandLegalNeighbors(initialBestPath); System.out.println("Starting from every spot"); coordScores.keySet() .stream() .sorted(Comparator.comparing(Coords::getProximityToOrigin)) .forEachOrdered(startingCoords -> solveSquareHelper(new Path(startingCoords))); System.out.println(); System.out.println("Best Path:\t" + bestPath); System.out.println("Best Score:\t" + bestPath.getScore()); System.out.println("LRU Cache stats:\t" + depthCacheHitsMap); System.out.println("Early Cutoff stats:\t" + depthEarlyCutoffsMap); return bestPath; } private class Coords implements Comparable<Coords> { private int x, y; private double proximityToOrigin; Coords(int x, int y) { this.x = x; this.y = y; this.proximityToOrigin = Math.sqrt((x - squareSize/2) * (x - squareSize/2) + (y - squareSize/2) * (y - squareSize/2)); } int getX() { return this.x; } int getY() { return this.y; } double getProximityToOrigin() { return proximityToOrigin; } Coords add(Coords other) { return new Coords(this.x + other.x, this.y + other.y); } @Override public int compareTo(Coords o) { int xdiff = this.x - ox; if (xdiff == 0) return this.y - oy; else return xdiff; } @Override public boolean equals(Object other) { if (other instanceof Coords) { Coords o = (Coords) other; return this.x == ox && this.y == oy; } else { return false; } } @Override public int hashCode() { return this.x * squareSize + this.y; } @Override public String toString() { return "(" + this.x + ", " + this.y + ")"; } } private class Path { private TreeSet<Coords> usedCoords; private Coords currentCoords; private int score; Path(Coords newCoords) { this.usedCoords = new TreeSet<>(); usedCoords.add(newCoords); currentCoords = newCoords; this.score = coordScores.get(newCoords); } Path(Path previousPath, Coords newCoords) { this(newCoords); this.usedCoords.addAll(previousPath.usedCoords); this.score += previousPath.score; } Coords getCurrentCoords() { return this.currentCoords; } int size() { return usedCoords.size(); } int getScore() { return this.score; } boolean doesNotContain(Coords coords) { return !usedCoords.contains(coords); } @Override public String toString() { return this.usedCoords.toString(); } @Override public int hashCode() { return this.usedCoords.hashCode(); } @Override public boolean equals(Object other) { if (other instanceof Path) { Path o = (Path) other; return this.usedCoords.equals(o.usedCoords) && this.currentCoords.equals(o.currentCoords); } else { return false; } } } } 

Some key ideas that allow us to do something more effective than brute force:

Insight Two sub-paths with the same current node and the same set of nodes used have the same top score.

How we use it Use LRU_Cache, which recognizes paths that use the same nodes and have the same node current as the equivalent. This causes MANY MUCH early cuts at depths of another 4. Undercuts whose root node is at a depth of 4 relative to the main tree contain 3 46 routes each. Trimming a significant portion of them is huge.

Insight A subpath of length k can only get the maximum score sub-path.score + best_length_n-k_path.score

How do we use this . First decide for the best path of length 2, and then use this to find the best path of length 3. Use both of them to find the best path of length 4, etc. You can early interrupt at any time when the current path of length k cannot exceed the maximum score, even if your previous best path of length nk is added. The solution for n = 2, 3, 4, 5 ... 50 seems a lot more difficult than just solving n = 50 directly, but for this problem it turns out that the savings from early pruning cost more.

Answer 2

If the lines cannot be diagonal, here is a way to do it
He (tries) checks EVERY opportunity:

Test.java

 import java.util.ArrayList; public class Test { private int[][] square = {{50,54,46,55,45,56,44,53,47,59,41,60,40,59,41,59}, {47,57,46,49,52,46,53,47,53,41,59,40,60,41,59,41}, {56,42,54,51,48,54,47,53,53,57,48,54,49,57,46,59}, {48,50,52,54,56,58,57,47,48,49,48,47,46,53,52,51}, {50,56,50,48,49,50,51,59,42,60,39,62,38,63,38,50}, {60,40,50,50,50,50,60,40,55,45,55,45,56,44,56,44}, {60,45,46,37,56,50,43,39,50,53,56,39,50,58,39,49}, {26,56,54,38,48,50,67,64,32,54,50,49,48,47,46,45}, {28,45,35,57,54,34,34,32,64,57,58,74,24,64,34,50}, {40,50,60,54,45,56,46,47,35,36,39,27,38,50,51,52}, {29,38,47,58,48,37,50,58,37,46,50,50,50,50,50,50}, {47,48,49,50,52,65,64,52,49,47,43,47,58,46,30,32}, {59,47,47,56,65,34,45,56,75,24,35,45,56,65,50,54}, {53,46,35,45,29,46,46,50,23,32,40,46,64,64,64,20}, {53,54,56,58,60,43,43,34,34,35,64,30,50,40,49,59}, {52,12,17,50,63,62,62,64,50,51,52,57,43,44,42,69}}; int result = 0; Test() { for (int i = 0; i < 15; i++) for (int j = 0; j < 15; j++) search(new Position(i,j), new ArrayList<Position>(), 0); //Starts at every position System.out.println(result); } public void search(Position actual, ArrayList<Position> checked, int sum){ checked.add(actual); //Add the actual position to avoid going through it multiple times sum += square[actual.row][actual.column]; if (checked.size() != 50) for (int i = 0; i < 2; i++) for (int j = -1; j < 2; j += 2){ //Checks every direction boolean checkable = true; Position newpos; if (i != 0) newpos = new Position(actual.row, actual.column + j); else newpos = new Position(actual.row + j, actual.column); if (newpos.row >= 0 && newpos.column >= 0 && newpos.row <= 15 && newpos.column <= 15){ for (Position pos : checked) if(pos.equals(newpos)) //If the new position has already been calculated checkable = false; if(checkable) search(newpos, new ArrayList<Position>(checked), sum); //If the position haven't been checked, starts a new search } } if (sum > result){ result = sum; System.out.println(sum); } } 

}

Position.java

 public class Position{ public int row, column; Position(int x, int y){ row = x; column = y; } public boolean equals(Position pos) { return pos.row == this.row && pos.column == this.column; } } 

Main.java

 public class Main { public static void main(String [] args){ new Test(); } } 

Current Output: 2578
Comment, if I forgot something / have any suggestions / questions
The lead time is slightly low.

EDIT: When I print the size of the checked list using this:

  if (sum > result){ result = sum; System.out.println(checked.size()); } 

His movement is above 50 ... although he was not supposed to. Any idea?
Here count + checked.size() should ALWAYS be 50

EDIT 2: Find it! I just needed to create a new array for each search:

 if(checkable) search(newpos, count, new ArrayList<Position>(checked), sum); 

Just understand that he is going to check 16 * 16 * 3 ^ 50 cases ... meh, it's worth a try

Answer 3

I feel that a good place to start is to find the areas with the highest intensity.

A strategy can evaluate each location as the sum of its neighbors, multiplied by a Gaussian distribution , concentrated in each place:

 rank(a, b) = 0 for j in -16 to 16: for k in -16 to 16: rank(a, b) += value(a+j, b+k)*exp(-((a)^2+(b)^2)/constant) 

Where value(x, y) is the value on the original map, and constant is the decay coefficient. Values ​​that go beyond the original limits are considered zero.

After that, a new rank map will be created for each pixel. The highest values ​​on this map will display areas on the original map, which contain, on average, higher neighbors with numbers. Traveling between these points will make you more likely to correctly identify a higher number location.

Answer 4

This is similar to the dynamic programming homework question. I would recommend you adapt something like this to the solution. For any given element, the maximum amount path may potentially end on that element. Ie, the 50th element of a path can have 4 possible paths to it from the elements surrounding it (which themselves are the 49th element of a path)