Menu
EDIT: Path, not line --- it can wind around and stuff. The path connects adjacent squares. You cannot go diagonally.
Also, my proposed solution was an attempt to take every possible string of 50-digit numbers base 4 - so that, you start at each square, and move left, right, up or down --- in every possible combination 4^50
This problem asks you to find the greatest sum of 50 numbers that can be connected by a path, without going 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 random paths and turns after each of the 50 steps - up, right, down, left - without crossing over itself. It gets me to about 2750, but I need at least 2800 to complete the assignment. //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 full solution - it attempt to take every possible string of 50-digit numbers base 4 - so that, you start at each square, and move left, right, up or down --- in every possible combination 4^50
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;
}
*/
}
602
EDIT: Here is some sample code demonstrating some of the techniques I've outlined. It solves this problem reasonably well. While experimenting, I did find some improvements that are not in code below. Improving the speed/efficiency of this program is 100% possible, but left as an exercise to 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's 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 - o.x;
if (xdiff == 0) return this.y - o.y;
else return xdiff;
}
@Override
public boolean equals(Object other) {
if (other instanceof Coords) {
Coords o = (Coords) other;
return this.x == o.x && this.y == o.y;
} 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 insights that allow us to do something more efficient than brute force:
Insight Two sub-paths with the same current node and same set of used nodes, have the same top-score.
How We Use This Use an LRU_Cache which recognizes paths which use the same nodes and have the same current node, as equivalent. This causes MANY early cutoffs, at depths as early as 4. Subtrees whose root node is at a depth of 4 with respect to the main tree contain 3^46 paths each. Pruning an appreciable fraction of them out is huge.
Insight A sub-path of length k can only obtain a maximum score of sub-path.score + best_length_n-k_path.score
How We Use This First solve for the best path of length 2, then use that to find the best path of length 3. Use both of them to find the best path of length 4, etc. You can early cutoff anytime a current path of length k cannot exceed the max score even with your previous best n-k length path added on. Solving for n = 2, 3, 4, 5 ... 50 seems like a lot more work than just solving n = 50 directly, but for this problem it turns out the savings from early pruning are worth more.
173
If the lines can't be diagonal, here's a way to do it
It (tries to) checks EVERY possibility:
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 execution time is weirdly low
EDIT : When i print the size of the checked list using this:
if (sum > result){
result = sum;
System.out.println(checked.size());
}
Its going above 50... although its not supposed to. Any idea?
Here, count + checked.size() should ALWAYS be equals to 50
EDIT 2 :
Found it!
I just had to create a new array for each search:
if(checkable)
search(newpos, count, new ArrayList<Position>(checked), sum);
Just realise that its going to check 16*16*3^50 cases... meh, worth a try
23
I feel like a good place to start would be finding the areas of highest intensity.
A strategy could be ranking each location as a sum of its neighbors multiplied by a Gaussian distribution centered at each location:
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 a value in the original map, and constant is a decay factor. And values that fall outside of the original bounds are considered zero.
After doing this for each pixel a new rank map is formed. The highest values from this map will indicate the areas on the original map which contain, on average, higher numbered neighbors. Traveling between these points will make it more likely for you to guess higher numbered locations correctly.
1
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
