4
\$\begingroup\$

DONT EVALUATE YET, ALMOST FINISHED, NEED A CLEAR WINNING CRITERION

Make me rich in minecraft

Minecraft is a 3D game made of blocks that you can destroy and place. There are some interesting farms you can build to provide you with game resources. In this problem, we will only have a look at pumpkin and melons farms. Here's a melon stem on the right that produced a melon block on the left.

Melon block

When the melon block grows, you can break it and the stem will produce another one later. Pumpkins farms have exactly the same behavior.

On some servers there's an economy going on where you can sell your items such as melons and pumpkins. The motivation behind this problem is to get rich selling pumpkins and melons.


Types of blocks

Since we're only gonna farm melons and pumpkins, we are not gonna take a look at the couple hundreds of blocks in the game. We will just focus on:

  • Dirt : Basic block, does not impact growth rate but provides a place when pumpkins/melons can grow
  • Farmland: Tiled dirt where you can plant stems
  • Hydrated farmland: Basically farmland but with water nearby. See irrigation section just below.
  • Stem: Money making magic plant.
  • Melon or pumpkin: Things your stems grow and you sell. They will appear around the stem.

Irrigation

Water can irragate farmland to hydrated farmlands if it's close enough. The water irrigates all blocks in a 9x9 grid centered on the source.

Irrigation

Note that the water will irrigate that grid no matter what is composing it. If there is a wall all around the water, it will still irrigate a 9x9 grid.


Stem behavior

A stem can only grow a fruit above dirt or farmland if the space is innocupied. To grow a fruit, the stem follows a complex game mechanic. Hang out for the next part, it's getting complicated.

Game mechanic

Each second, 400 blocks are choosen at random in a 16x16x128 area, they will receive an update. When a fully grown stem is choosen, it will have a chance to grow a fruit.

In the first time, the game select at random a block next to the stem (on his 4 sides, diagonals excluded). If the block choosen is dirt or farmland AND there is nothing above, it will then try to grow a fruit on this block. (Please note that if a fruit grows on a farmland, it turns it into dirt.)

The chance of a fruit growing depends on the score s of the stem. The score is calculated as following:

  • If the stem is planted in an hydrated farmland, the initial value of s is 4. If it is not hydrated, it is 2.
  • For each farmland in a 3x3 grid centered on the stem, the score gains 0.75. This also applies if the farmland has a stem growing in. If it's not hydrated farmland, the score gains 0.25.

The chance of trying to grow a fruit is then 1/(floor(25/s)+1)

Overfarming penalties: Stems don't like having neighboors. If there is another stem, of the same type only, in the 3x3 grid around it, the score s is halved. There is only one exception, if the stems are in a row, it's not halved. Note that if there are 8 stems around, the score is only halved once. Here's a pic to illustrate that rule, green stems have normal growth, orange ones are halved.

Stem layouts

An example to determine the income from a given layout

One stem and his neighboors

For this case, the stem is planted in an hydrated farmland (consider a water source nearby not represented). It is surrounded by 4 hydrated farmlands. The four others blocks are just dirt. There are 3 dirt blocks available for the fruit to grow on (the 3 on its sides), so the stem has a 3/4 chance to choose a valid spot.

The stem is planted on an hydrated farmland so the score is 4. There are 4 others farmlands in a 3x3 grid around the stem so the total score is s = 4 + 0.75*4 = 7. The chance to succeed the attempt is P = 1/(floor(25/s)+1) = 1/4.

So the chance for the fruit to grow is then 3/4 * 1/4 = 3/16

Now let's calculate the average number of fruit per hour this single stem can provide. Each second the stem has a 400 /(16x16x128) chance of being choosen. So in an hour, the block is choosen 3600x400 /(16x16x128) = 43.945 times on average. Each time it is choosen, the plant grows with a probability of 3/16. In an hour, the stem will then provide 43.945x3/16 = 8.24 fruits on average.


Rules

Money making

Each melon that grows is sold 5$. For the minecraft fans out there, a melon block drops on average 5 melon slices each one worth 1$.

Each pumpkin that grow is sold 8$.

Specifications

  • Stems can produce an infinite amount of fruits without ever breaking.
  • The fruit is always produced next to the stem (sides, not diagonals) on a dirt block.
  • The fruit is harvested instantly. Usually when the block grow, you are supposed to break it before the stem can produce another one. Here we will consider that all the fruits are harvested whenever they grow.
  • Since fruit production is random, we will only work with the average production.
  • Stems grow on farmland only but no fruit can grow above farmland (with ou without stem), since after a fruit grows it will turn farmland into dirt! Dirt is then the only valid spot for a fruit to grow on.
  • If a stem has another stem in a 3x3 grid, it is counted as a farmland for the score calculation. If the stem is not of the same type (like one melon and one pumpkin stem), there is no score penalties.
  • All stems are already in their final stage. In the game, to have a stem you need to plant a seed that will grow to its final stage and that will then stay this way and start producing fruits. We assume that when seeds are planted, they are already fully grown stems.
  • Water irrigates a 9x9 grid no matter what's around. So water can irrigate farms through walls.

Goal

In a given space, you need to design the best layout to produce the maximum amount of money per hour.

Input

You are given a grid containing 0 and # that represent the space allowed for your layout. # for occupied blocks where you can't place anything, 0 for the spot where you can place dirt/farmland/stem.

Output

Your program should return the maximum amount of money per hour you can make with this space allowed, and the layout that yields this result. The layout is composed of numbers that follow this code:

  • 0: Dirt block
  • 1: Farmland (blocked, no fruit can grow on it)
  • 2: Pumpkin stem
  • 3: Melon stem
  • 9: Water source

Test cases

Input

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Outputs

325.927734375
2 0 2 0
0 3 0 3
2 0 2 0
0 3 0 9

Here 0 means dirt, 1 blocked farmland, 2 pumpkin stem, 3 melon stem, 9 water.

results


Winning criterion

Your are given txt files that corresponds to inputs. There are labelled Level-3 to Level-20, where the number represent the size of the input. The level 6 for instance is a 6x6 input grid. The goal is to find the best solutions for each layout. Since I don't have the solution to all the layouts (I could just compute the first ones in bruteforce), the goal is not to find THE OPTIMAL solution, but a better solutions than all the ones already found. Hence, metaheuristics and original solutions are greatly appreciated.

Then, you should provide along with your solution all the results you get for each level. If any of them is above the best solution we found, it will be verified in the snippet and updated in the post.

Here is the snippet that will help you building your fitness function and that will be used to verify your layouts.

<!DOCTYPE html>
<html>
<body>

<p>Input your layout and select your size:</p>
<textarea rows="10" cols="40" id="myTextarea">2 0 2 0
0 3 0 3
2 0 2 0
0 3 0 9</textarea><br>
<select id="mySelect">
  <option value="16">16</option>
  <option value="32">32</option>
  <option value="64">64</option>
</select>
<button onclick="DrawCanvas()">Test it</button>
<img id="source" src="https://img15.hostingpics.net/pics/668575stem.png" width="65" height="33" hidden>

<p>The income is: <span id="result">None</span>.<br>Scroll down to see a graphical representation of your layout.</p>



<script>

<!DOCTYPE html>
<html>
<body>

<p>Input your layout:</p>
<textarea rows="10" cols="40" id="myTextarea">2 0 2 0
0 3 0 3
2 0 2 0
0 3 0 9</textarea><br>
<select id="mySelect">
  <option value="16">16</option>
  <option value="32">32</option>
  <option value="64">64</option>
</select>
<button onclick="DrawCanvas()">Test it</button>
<img id="source" src="https://img15.hostingpics.net/pics/546130stem.png" width="161" height="65" hidden>

<p>The income is: <span id="result">None</span></p>



<script>

function DrawCanvas() {
  var s = document.getElementById("mySelect").value;
  var t = document.getElementById("myTextarea").value;
  var n = t.split("\n")[0].split(" ").length;
  var m = t.split("\n").length;
  if (n != 0 && m != 0) {
var x = document.getElementById("myCanvas");
if (x) { document.getElementById("myCanvas").remove(); }
var canvas = document.createElement("canvas");
canvas.id     = "myCanvas";
canvas.width  = s*n;
canvas.height = s*m;
canvas.style.border   = "1px solid";
document.body.appendChild(canvas);
var arr = GetLayout(t);
var income = GetIncome(arr,canvas,s);
document.getElementById("result").innerHTML = income;
  }
}

function DrawLayout(arr,c) {
  var s = document.getElementById("mySelect").value;
  var ctx = c.getContext("2d");
  var img = document.getElementById("source");
  
  for (var i=0;i<arr.length;i++) {
for (var k=0;k<arr[i].length;k++) {
  if (arr[i][k] != "#") {
    if (arr[i][k] == 0) {
      ctx.drawImage(img, 0, 0,32,32,s*k,s*i,s,s);
    } else if (arr[i][k] == 1) {
      ctx.drawImage(img,32, 0,32,32,s*k,s*i,s,s);
    } else if (arr[i][k] == 2) {
      ctx.drawImage(img,64, 0,32,32,s*k,s*i,s,s);
    } else if (arr[i][k] == 3) {
      ctx.drawImage(img,96, 0,32,32,s*k,s*i,s,s);
    } else if (arr[i][k] == 5) {
      ctx.drawImage(img,32,32,32,32,s*k,s*i,s,s);
    } else if (arr[i][k] == 6) {
      ctx.drawImage(img,64,32,32,32,s*k,s*i,s,s);
    } else if (arr[i][k] == 7) {
      ctx.drawImage(img,96,32,32,32,s*k,s*i,s,s);
    } else if (arr[i][k] == 9) {
      ctx.drawImage(img, 0, 32,32,32,s*k,s*i,s,s);
    }
  } else {
  	ctx.drawImage(img, 128, 0,32,32,s*k,s*i,s,s);
  }
}
 }
}

function GetLayout(t) {
  var arr = t.split("\n");
  for (var i=0;i<arr.length;i++) {
arr[i] = arr[i].split(" ");
for (var k=0;k<arr[i].length;k++) {
  if (arr[i][k] != "#") {
    arr[i][k] = parseInt(arr[i][k]);
  }
}
 }
 return arr;
}

function GetIncome(arr,c) {
  arr = irrigate(arr);
  var n = arr[0].length;
  var m = arr.length;
  var s = 0;
  for (var i=0;i<arr.length;i++) {
for (var k=0;k<arr[i].length;k++) {  
  if (arr[i][k] == 2 || arr[i][k] == 6 ) {
    s += 8*EvalStem(arr,i,k,n,m);
  } else if (arr[i][k] == 3 || arr[i][k] == 7 ) {
    s += 5*EvalStem(arr,i,k,n,m);
  }
}
  }
  DrawLayout(arr,c);
  console.log(s*400*3600/(16*16*128));
  return s*400*3600/(16*16*128);
}

function EvalStem(arr,i,k,n,m){
  // returns the chance of a fruit to grow
  var nbs = 0;
  var sc = 2;
  var half = false;
  var row = [1,1];
  if (arr[i][k] > 5) {sc += 2; }
  for (var y = Math.max(i-1,0); y <= Math.min(i+1,m-1) ; y++) {
for (var x = Math.max(k-1,0); x <= Math.min(k+1,n-1) ; x++) {
  if (x != k || y != i) {
    if ( arr[y][x] == 1 || arr[y][x] == 2 || arr[y][x] == 3 ) {
      sc += 0.25;
    } else if ( arr[y][x] == 5 || arr[y][x] == 6 || arr[y][x] == 7 ) {
      sc += 0.75;
    }
    if ( (Math.abs(x-y)%2 == 1 && (i+k)%2 == 0) || (Math.abs(x-y)%2 == 0 && (i+k)%2 == 1) ) {
      if ( arr[y][x] == 0 ) {
        nbs += 1;
      }
      if ( Math.abs(arr[y][x] - arr[i][k]) == 4 || arr[y][x] == arr[i][k] ) { 
        if (row[0] == k+x || row[1] == i+y) {
          row = [x,y]
        } else {
          console.log(row, k, x, i, y);
          half = true;
        }
      }
    } else {
      if ( Math.abs(arr[y][x] - arr[i][k]) == 4 || arr[y][x] == arr[i][k] ) { 
        half = true;
        console.log(x,y,k,i)
      }
    }
  }
}
  }
  if (half == true) { sc /= 2.0; }
  console.log("STEM: "+i+","+k,"SCORE: "+sc,"NEIGHB: "+nbs,"HALVED: "+half,"CHANCE :"+ 1.0/(Math.floor(25/sc)+1) * (nbs/4.0));
  return (1.0/(Math.floor(25/sc)+1) * (nbs/4.0));
}

function irrigate(arr){
  var n = arr[0].length;
  var m = arr.length;
  for (var i=0;i<arr.length;i++) {
for (var k=0;k<arr[i].length;k++) {
  if (arr[i][k] == 9) {
    for (var y = Math.max(i-4,0); y <= Math.min(i+4,m-1) ; y++) {
      for (var x = Math.max(k-4,0); x <= Math.min(k+4,n-1) ; x++) {
        if ( arr[y][x] == 1 || arr[y][x] == 2 || arr[y][x] == 3 ) {
          arr[y][x] += 4;
        }
      }
    }
  }
}
  }
  return arr;
}

Element.prototype.remove = function() {
  this.parentElement.removeChild(this);
}
NodeList.prototype.remove = HTMLCollection.prototype.remove = function() {
  for(var i = this.length - 1; i >= 0; i--) {
if(this[i] && this[i].parentElement) {
  this[i].parentElement.removeChild(this[i]);
}
  }
}


</script>

</body>
</html>


Levels and highscores

It starts from this zip: https://file.io/IvA6rf

Level 3:  6.223 by ME
Level 4:  0
Level 5:  0
Level 6:  0
Level 7:  0
Level 8:  0
Level 9:  0
Level 10: 0
Level 11: 0
Level 12: 0
Level 13: 0
Level 14: 0
Level 15: 0
Level 16: 0
Level 17: 0
Level 18: 0
Level 19: 0
Level 20: 0
\$\endgroup\$

closed as off-topic by Laikoni, Stephen, Shaggy, Blue, Timtech Jun 1 '17 at 18:08

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – Laikoni, Stephen, Shaggy
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ Does water actually irrigate that far away from the source now? \$\endgroup\$ – mbomb007 Jun 1 '17 at 15:08
  • \$\begingroup\$ It always did bro, but no one paid attention to that at the time ;) \$\endgroup\$ – Philippe Jun 1 '17 at 15:11
  • 1
    \$\begingroup\$ I like this. I think that you should explain the mechanics a bit better, but otherwise Well thought out. You should note that having one output is not that great, and it's better to say for any given layout. \$\endgroup\$ – tuskiomi Jun 1 '17 at 16:53
  • 1
    \$\begingroup\$ I'm voting to close this question as off-topic because I think it would be better suited for puzzling.SE or generalised with an objective winning criteria \$\endgroup\$ – Blue Jun 1 '17 at 17:36
  • 1
    \$\begingroup\$ Regarding the title of the new edit, you should use the Sandbox for developing challenges. \$\endgroup\$ – Notts90 Jun 2 '17 at 9:11