title: Block Building Bot Flocks!

text:
# Question
Title: Block Building Bot Flocks!
*The contest is over!*

# Intro

This is an interactive contest where the controller is fully contained in a Stack Snippet at the bottom of the question. The controller automatically reads the answers and plays through games. Anyone can run it at any time right in their browser.

The mechanics of this contest are very similar to those of Red vs. Blue - Pixel Team Battlebots. Except the game being played, while still grid based, is entirely different. Each game is 1 vs. 1 and there are no teams. Each entry is fighting for itself and only one will be the final champion.

The controller uses JavaScript, and as JavaScript is the only client-side scripting language most browsers support, **all answers must be written in JavaScript too**.

In this spec, *italicized text* is used to indicate the formal term for a game mechanic or property. These terms are used throughout to help maintain a cohesive and clear way of referring to the different parts of the game.

# Gameplay

### Basics

Every answer to this question represents a *player*. A *game* is a competition between two players, *P1* and *P2*. Each player controls a *flock* of 8 *bots*, numbered 0 through 7. Games takes place in the *grid*, a 128×64 *cell* arena whose bottom 8 rows start out as *walls* (the 'blocks') and other rows start as *air*. Cells outside the grid bounds are considered air.

The grid's x coordinate ranges from 0 on the left to 127 on the right, and y ranges from 0 at the top to 63 at the bottom.

Sample starting grid:

Bots always stay aligned to the grid cells and multiple bots may occupy the same cell. Bots can only occupy air cells. P1's bots always start in a line 0-7 at the very left of the row above the walls and P2's bots always start in a line 7-0 at the very right.

The *neighbors* of a bot or cell are the 8 cells directly orthogonal and diagonal to it.

The field of view (*FOV*) of a bot is the 13×13 cell square centered on a bot. A cell or enemy bot is said to be in a player's FOV if it is in the FOV of at least one of the player's bots.

### Moves & Actions

During a game, each player gets to *move* 1000 times. P1 moves first, then P2, then P1 and so on until 2000 total moves have been made, at which point the game ends.

During a move, each player receives information about the game state and the grid cells and enemy bots in their FOV, and uses it to decide on an *action* for each of their bots to take.

The default action is *do nothing*, where the bot does not move or interact with the grid.

The other actions are *move*, *grab*, and *place*:

* A bot can **move** to one of its neighboring cells C if:

+ C is not out of bounds,
    + C is air (i.e. not a wall),
    + and at least one of C's neighbors is a wall.

If successful, the bot will move to C.
* A bot can **grab** one of its neighboring cells C if:

+ C is not out of bounds,
    + C is a wall,
    + and the bot is not already carrying a wall.

If successful, C will become air and the bot will now be carrying a wall.
* A bot can **place** to one of its neighboring cells C if:

+ C is not out of bounds,
    + C is air,
    + no bots of either player occupy C,
    + and the bot is carrying a wall.

If successful, C will become a wall and the bot will no longer be carrying a wall.

**Unsuccessful actions result in a do nothing.**

A cell occupied by at least one wall-carrying bot has a small wall-colored square drawn over it. Bots start without walls.

### Memory

During a move, a player can access and change their *memory*, an initially empty string that lasts throughout the game and can be used to store strategic data.

### Goal

The cell in the yellow crosshair is the *goal*, which starts in a random position. Each player has a *score* that starts at 0. When a player's bot moves to the goal, that player's score increases by 1 and the goal is randomly repositioned before the next turn. The player with the highest score at the end of a game wins. It's a tie if the scores are equal.

If multiple bots move to the goal during a move, the player still only gets one point.

If the goal has been in the same place for 500 moves, it is randomly repositioned again. Any time the goal is randomly positioned, it is guaranteed to not be placed on a cell occupied by a bot.

# What to Program

Write a **body** for this function:

```
function myMove(p1, id, eid, move, goal, grid, bots, ebots, getMem, setMem) {
    //body goes here
}

```

It will be called once every time your player moves and needs to return the actions you want each of your bots to take during that move.

You can use the Baseline code as a starting point.

### Parameters

> * `p1` is a bool that's `true` if you are P1 and `false` if you are P2
> * `id` is an integer that is the answer ID of your answer.
>     + You can find the ID of an answer by clicking the 'share' link below it and looking for the number right after `a/` in the URL.
>     + The ID of the Test Entry is -1.
> * `eid` is an integer that is the answer ID of your enemy's answer.
> * `move` is an integer from 1 to 1000 that says what move you are on.
> * `goal` is an object with `x` and `y` properties. These are the goal's coordinates. They are given even if the goal is out of your FOV.
> * `grid` is a function that takes in x and y arguments, e.g. `grid(x,y)`. It returns:
>     + `-1` for 'unknown' if the arguments aren't two integers or if `x,y` is not in your FOV.
>     + `0` for 'air' if `x,y` is out of bounds or if the cell at `x,y` is air.
>     + `1` for 'wall' if the cell at `x,y` is a wall.
> * `bots` is an array of your 8 bots. Its elements are objects with properties `x`, `y`, and `hasWall`:
>
> + `x` and `y` are the bot's coordinates.
>     + `hasWall` is `true` if the bot is carrying a wall and `false` if not.
>
> `bots` is always ordered normally, the Nth index corresponds to bot number N.
> * `ebots` is an array of objects with `x`, `y`, and `hasWall` properties just like `bots`. Only the enemy bots in your FOV are in `ebots`. So it would have length 0 if if there are no enemy bots in your FOV. It is ordered randomly.
> * `getMem` is a function with no arguments that returns your memory.
> * `setMem` is a function that takes one argument M. If M is a string of 256 characters or less, your memory is updated to M, otherwise nothing happens.

The browser `console` object is available for the Test Entry alone.

### Return Value

Your function needs to return an array of exactly 8 integers, each ranging from 0 to 24. The value at index N is the action that bot number N will take.

All your bots will do nothing if your function:

* Throws an error of any kind. (*error*)
* Takes longer than **20 milliseconds** to execute. (*timeout*)
* Doesn't return an array of 8 integers ranging from 0 to 24. (*malformed*)

For convenience, the number of errors, timeouts, and malformed actions are displayed when a game ends.

Each of the numbers from 0 to 24 corresponds to a particular bot action:

* 0 is for doing nothing.
* 1-8 are for moving.
* 9-16 are for grabbing.
* 17-24 are for placing.

Each of the 8 values for moving, grabbing, and placing corresponds to one of the bot's neighboring cells, as shown here:

So, for example, `15` is the action for grabbing the cell below the bot.

Bot actions are handled in the order bot 0 to bot 7. For example, if during one move bot 0 is told to place a wall in the same air cell bot 1 was told to move to, the air cell will become a wall before bot 1's action is handled and bot 1 will be unsuccessful.

Unsuccessful actions become do nothings and are said to have *failed*. Failed action counters are also displayed when the game ends.

# Rules

I may temporarily or permanently *disqualify* users or answers that don't follow these rules. Disqualified entries are not eligible to win.

* **When declaring variables or functions, you must use the `var` keyword.**
e.g. `var x = 10` or `var sum = function(a, b){ return a + b }`
Things declared without `var` become global and could interfere with the controller. Steps have been taken so that this interference should be impossible, but do this to make sure.
* **Your code shouldn't run slowly or waste time.**
It's impossible to stop JavaScript functions mid-execution, so each player's code is run to completion. If your code takes a long time to run, everyone running your player will notice and be annoyed. Ideally, entries will always run well within the 20ms limit.
* You must use code compatible with ECMAScript 5 in the latest version of Firefox as this is where I'll be running it. **Do not use features from ECMAScript 6** as it is not yet supported in many browsers.
* You may answer **up to 3** times, but only if each of your strategies is considerably different. You can edit answers as much as desired.
* You may not attempt to have any sort of memory except through the use of `getMem` and `setMem`.
* You may not attempt to access or modify the controller, other player's code, or external resources.
* You may not attempt to modify anything built into JavaScript.
* Answers need not be deterministic. You may use `Math.random`.

# Answer Format

```
#EntryName

Notes, etc.

<!-- language: lang-js -->

    //function body
    //probably on multiple lines

More notes, etc.

```

The first multiline code block must contain your function body.
The entry name is limited to 20 characters.

Your entry will show up in the controller with the title `EntryName - Username [answer ID]`, plus `[DQ]` if it's disqualified.

# Winning

When the question has been up for at least 3 weeks and once answering has settled down, I will crown the champion.

I'll use the controller's *autorun* feature. In an autorun round, every non-disqualified player plays two games with every other, one as P1, one as P2 (a double round-robin).

I'll autorun as many rounds as I can in the period of a few hours. This will depend on how many submissions there are and how time intensive they are. But rest assured, I'm committed to getting an accurate final leaderboard. The player with the most wins is the champion and their answer will be accepted.

I'll be using Firefox on a laptop with Windows 8.1 64-bit, 4 GB ram, and a 1.6GHz quad-core processor.

### Prize

I will write and post a PPCG challenge specifically dedicated to the champion. It will somehow involve their username or avatar or something about them. I'll privately decide on what the challenge will be about when this contest is over. I'll write it to the best of my ability and try to make sure it becomes a Hot Network Question.

# Controller

Run this snippet or go to this JSFiddle to use the controller. It starts with random players selected. I've only thoroughly tested it in Firefox and Chrome.

```
<style>html *{font-family:Consolas,Arial,sans-serif}canvas{margin:6px}button,input table,select{font-size:100%}textarea{font-family:monospace}input[type=text],textarea{padding:2px}textarea[readonly]{background-color:#eee}select{width:250pt;margin:3px 0}input[type=radio]{vertical-align:-.25em}input[type=checkbox]{vertical-align:-.15em}.c{margin:12px}.h{font-size:125%;font-weight:700}#main td{padding:12px;text-align:left}#main table{margin-left:auto;margin-right:auto}#main{text-align:center}#title{margin:12px;font-size:175%;font-weight:700;color:#333}#delay{text-align:right}#statsTable table{border-collapse:collapse}#statsTable td{border:1px solid gray;padding:3pt;font-family:monospace;text-align:center}#footnotes{margin:18px 0 0;font-size:75%}#arWrapper{border:2px solid red;background-color:#fff4f4}</style><div id=loadStatus>Loading entries...</div><div id=main><div id=title>Block Building Bot Flocks</div><div><span id=p1Title class=p1Color></span> vs. <span id=p2Title class=p2Color></span></div><canvas id=canvas>Canvas unsupported!</canvas><div><span id=p1Score class=p1Color>0</span> | <span id=moveCounter>0</span> | <span id=p2Score class=p2Color>0</span></div><div class=c><button id=runPause type=button onclick=runPause()>Run</button> <button id=moveOnce type=button onclick=moveOnce()>Move Once</button> <button type=button onclick=newGame()>New Game</button></div><div class=c><input id=delay size=4 value=20> ms delay <input id=showNumbers type=checkbox onclick=toggleNumbers()><label for=showNumbers>Show bot numbers</label> <input id=showLOS type=checkbox onclick=toggleLOS()><label for=showLOS>Show field of view</label></div><table><tr><td><div id=p1Header class="p1Color h">Player 1</div><div><select id=p1Select onchange=changeSelect(!0)></select></div><div><a id=p1Link href=javascript:;>Answer Link</a></div><td><div id=p2Header class="p2Color h">Player 2</div><div><select id=p2Select onchange=changeSelect(!1)></select></div><div><a id=p2Link href=javascript:;>Answer Link</a></div></table><div>Test Entry</div><div><textarea id=testEntry rows=8 cols=64>return [0,0,0,0,0,0,0,0]</textarea></div><div class=c><button type=button onclick=autorun()>Autorun N Rounds</button> N = <input id=N size=4 value=1> <input id=arTestEntry type=checkbox><label for=arTestEntry>Include Test Entry</label></div><div id=footnotes><input id=debug type=checkbox onclick=toggleDebug()><label for=debug>Console debug messages</label> | Scale: <input id=sc1 type=radio name=sc value=1><label for=sc1>Micro</label><input id=sc3 type=radio name=sc value=3><label for=sc3>Small</label><input id=sc6 type=radio name=sc value=6 checked><label for=sc6>Normal</label><input id=sc9 type=radio name=sc value=9><label for=sc9>Large</label> | Colors: <input id=normalCo type=radio name=co value=normal checked><label for=normalCo>Normal</label><input id=pastelCo type=radio name=co value=pastel><label for=pastelCo>Pastels</label><input id=neonCo type=radio name=co value=neon><label for=neonCo>Neon</label>  <button type=button onclick=reload()>Reload</button><div id=invalidWrapper><br>No entry name/code found: <span id=invalid></span></div></div></div><div id=arWrapper><div id=arInfo class=c>Autorun in progress. Running game <span id=arProgress></span>.</div><div id=arResults><div class="c h">Autorun Results</div><div class=c>Players: <span id=arPlayers></span><br>Rounds: <span id=arRounds></span><br>Games per round: <span id=arGpR></span><br>Total games: <span id=arTotal></span><br></div><div class=c><strong>Leaderboard:</strong></div><div id=leaderboard class=c></div><div class=c>(W = wins, T = ties, L = losses, G = total goals, E = errors, I = timeouts, M = malformed actions, F = failed actions)</div><div class=c><strong>Player vs. Player Statistics:</strong></div><div id=statsTable class=c></div><div class=c>The top row has the ID's of P1.<br>The left column has the ID's of P2.<br>Every other cell not on the diagonal has the form "[P1 win count] [tie count] [P2 win count]".</div><div class=c><button type=button onclick=closeAutorun()>Close</button></div></div></div><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><script>function setGlobals(e){G={},G.QID=50690,G.SITE="codegolf",G.DQ_ANSWERS=[],G.DQ_USERS=[],G.DEBUG=Q("#debug").is(":checked"),G.SHOW_NUMBERS=Q("#showNumbers").is(":checked"),G.SHOW_LOS=Q("#showLOS").is(":checked"),G.BOTS=8,G.LOS=6,G.W=128,G.H=64,G.SCALE=e?6:parseInt(Q('input[name="sc"]:checked').val()),G.CW=G.SCALE*G.W,G.CH=G.SCALE*G.H,G.TOTAL_MOVES=2e3,G.GOAL_LIFESPAN=500,G.MEM_MAX_LENGTH=256,G.TIME_LIMIT=20;var t=Q('input[name="co"]:checked').val();e||"normal"===t?G.COLORS={AIR:"#ccc",WALL:"#888",GOAL:"rgba(255,255,0,0.6)",BG:"#f7f7f7",P1:"#00f",P1_TEXT:"#008",P1_LOS:"rgba(0,0,255,0.1)",P2:"#f00",P2_TEXT:"#800",P2_LOS:"rgba(255,0,0,0.1)"}:"pastel"===t?G.COLORS={AIR:"#cef0ff",WALL:"#66cc66",GOAL:"rgba(0,0,0,0.3)",BG:"#fdfde6",P1:"#f4a034",P1_TEXT:"#a35f00",P1_LOS:"rgba(255,179,71,0.2)",P2:"#f67cf6",P2_TEXT:"#b408b4",P2_LOS:"rgba(249,128,249,0.2)"}:"neon"===t&&(G.COLORS={AIR:"#000",WALL:"#444",GOAL:"rgba(255,255,0,0.9)",BG:"#999",P1:"#0f0",P1_TEXT:"#5f5",P1_LOS:"rgba(255,128,0,0.15)",P2:"#f0f",P2_TEXT:"#f5f",P2_LOS:"rgba(0,255,255,0.15)"}),G.SCOREBOARD={P1SCORE:void 0,MOVE:void 0,P2SCORE:void 0},G.CTX=void 0,G.PLAYERS=void 0,G.GAME=void 0,G.TIMER=void 0,G.RUNNING=!1}function reload(){var e="undefined"==typeof G;e||stopTimer(),setGlobals(e);var t=Q("#canvas");t.width(G.CW).height(G.CH).prop({width:G.CW,height:G.CH}),G.CTX=t[0].getContext("2d"),G.CTX.font=(2*G.SCALE).toString()+"px Courier New",G.SCOREBOARD.P1SCORE=Q("#p1Score"),G.SCOREBOARD.MOVE=Q("#moveCounter"),G.SCOREBOARD.P2SCORE=Q("#p2Score"),Q("body").css("background-color",G.COLORS.BG),Q(".p1Color").css("color",G.COLORS.P1),Q(".p2Color").css("color",G.COLORS.P2),Q("#invalidWrapper").hide(),Q("#arWrapper").hide(),loadAnswers(G.SITE,G.QID,function(e){Q.isArray(e)?(Q("#loadStatus").remove(),loadPlayers(e),newGame()):Q("#loadStatus").text("Error loading entries - "+e)})}function maskedEval(e,t){var r={};for(i in this)r[i]=void 0;for(i in t)t.hasOwnProperty(i)&&(r[i]=t[i]);return new Function("with(this) { "+e+";}").call(r)}function toKey(e,t){return G.W*t+e}function fromKey(e){return{x:e%G.W,y:Math.floor(e/G.W)}}function outOfBounds(e,t){return 0>e||e>=G.W||0>t||t>=G.H}function rnd(e){return Math.floor(Math.random()*e)}function isInt(e){return"number"==typeof e&&e%1===0}function isString(e){return"string"==typeof e||e instanceof String}function decode(e){return Q("<textarea>").html(e).text()}function shuffle(e){for(var t,r,o=e.length;o;t=rnd(o),r=e[--o],e[o]=e[t],e[t]=r);}function makeTable(e){for(var t=Q("<table>"),r=0;r<e.length;r++){for(var o=Q("<tr>"),a=0;a<e[r].length;a++)o.append(Q("<td>").text(e[r][a]));t.append(o)}return t}function toggleDebug(){G.DEBUG=Q("#debug").is(":checked")}function toggleNumbers(){G.SHOW_NUMBERS=Q("#showNumbers").is(":checked"),drawGame(G.GAME)}function toggleLOS(){G.SHOW_LOS=Q("#showLOS").is(":checked"),drawGame(G.GAME)}function closeAutorun(){Q("#arWrapper").hide(),Q("#main").show()}function changeSelect(e){var t=Q(e?"#p1Select":"#p2Select").val(),r=Q(e?"#p1Link":"#p2Link");null===t&&0>t?r.attr("href","javascript:;"):r.attr("href",G.PLAYERS[t].link)}function stopTimer(){"undefined"!=typeof G.TIMER&&clearInterval(G.TIMER)}function moveOnce(){gameOver(G.GAME)||(moveGame(G.GAME),drawGame(G.GAME),gameOver(G.GAME)&&(stopTimer(),Q("#runPause").text("Run").prop("disabled",!0),Q("#moveOnce").prop("disabled",!0),G.DEBUG&&console.log("======== GAME OVER: "+G.GAME.p1.score+" TO "+G.GAME.p2.score+" ========"),alert(gameOverMessage(G.GAME))))}function runPause(){if(G.RUNNING)stopTimer(),Q("#runPause").text("Run"),Q("#moveOnce").prop("disabled",!1);else{var e=parseInt(Q("#delay").val());if(isNaN(e)||0>e)return void alert("Delay must be a non-negative integer.");Q("#runPause").text("Pause"),Q("#moveOnce").prop("disabled",!0),G.TIMER=setInterval(moveOnce,e)}G.RUNNING=!G.RUNNING}function newGame(){stopTimer();var e=G.PLAYERS[Q("#p1Select").val()],t=G.PLAYERS[Q("#p2Select").val()];G.RUNNING=!1,Q("#runPause").text("Run").prop("disabled",!1),Q("#moveOnce").prop("disabled",!1),Q("#p1Title").text(e.title),Q("#p2Title").text(t.title),G.GAME=createGame(e,t),drawGame(G.GAME)}function tryParse(e,t){var r=parseInt(Q(e).val());return!isNaN(r)&&r>=0?r:void alert(t+" must be a non-negative integer.")}function autorun(){function e(){for(var e=new Array(a.length),t={},r=["wins","goals","errors","timeouts","malformed","invalid"],n=0;n<e.length;n++){t.wins=t.ties=t.losses=t.goals=t.errors=t.timeouts=t.malformed=t.invalid=0;for(var l=0;l<e.length;l++)n!==l&&(t.ties+=s[n][l].ties+s[l][n].ties,t.losses+=s[n][l].p2.wins+s[l][n].p1.wins,r.forEach(function(e){t[e]+=s[n][l].p1[e]+s[l][n].p2[e]}));e[n]={wins:t.wins,text:a[n].title+" : "+t.wins+"W, "+t.ties+"T, "+t.losses+"L, "+t.goals+"G, "+t.errors+"E, "+t.timeouts+"I, "+t.malformed+"M, "+t.invalid+"F"}}e=e.sort(function(e,t){return t.wins-e.wins}).map(function(t,r){return r+1+". "+t.text+(r<e.length-1?"<br>":"")});for(var i=new Array(s.length+1),G=0;G<i.length;G++){i[G]=new Array(s.length+1);for(var c=0;c<i.length;c++){var f;i[G][c]=0===c&&0===G?"P2\\P1":0===c?a[G-1].id:0===G?a[c-1].id:(f=s[c-1][G-1])?f.p1.wins+" "+f.ties+" "+f.p2.wins:"-"}}Q("#arPlayers").text(a.length),Q("#arRounds").text(o),Q("#arGpR").text(S/o),Q("#arTotal").text(S),Q("#leaderboard").empty().append(e),Q("#statsTable").empty().append(makeTable(i)),Q("#arInfo").hide(),Q("#arResults").show()}function t(e,t){for(var r=createGame(a[e],a[t]);!gameOver(r);)moveGame(r);r.p1.score>r.p2.score?s[e][t].p1.wins++:r.p1.score<r.p2.score?s[e][t].p2.wins++:s[e][t].ties++,["p1","p2"].forEach(function(o){s[e][t][o].goals+=r[o].score,s[e][t][o].errors+=r[o].stats.errors,s[e][t][o].timeouts+=r[o].stats.timeouts,s[e][t][o].malformed+=r[o].stats.malformed,s[e][t][o].invalid+=r[o].stats.invalid.reduce(function(e,t){return e+t},0)})}function r(){if(c!==f&&(t(c,f),++p<=S&&Q("#arProgress").text(p+"/"+S)),f+1<a.length)f++;else if(f=0,c+1<a.length)c++;else{if(c=0,!(o>i+1))return void e();i++}setTimeout(r,0)}var o=parseInt(Q("#N").val());if(isNaN(o)||1>o)return void alert("N must be a positive integer.");var a=[];Q("#arTestEntry").is(":checked")&&a.push(G.PLAYERS[0]);for(var n=1;n<G.PLAYERS.length;n++)G.PLAYERS[n].dq||a.push(G.PLAYERS[n]);for(var s=new Array(a.length),n=0;n<a.length;n++){s[n]=new Array(a.length);for(var l=0;l<a.length;l++)n!==l&&(s[n][l]={ties:0,p1:{wins:0,goals:0,errors:0,timeouts:0,malformed:0,invalid:0},p2:{wins:0,goals:0,errors:0,timeouts:0,malformed:0,invalid:0}})}var i=0,c=0,f=0,p=1,S=o*a.length*(a.length-1);Q("#arProgress").text("1/"+S),Q("#main").hide(),Q("#arInfo").show(),Q("#arResults").hide(),Q("#arWrapper").show(),setTimeout(r,0)}function gameOver(e){return e.move>=G.TOTAL_MOVES}function gameOverMessage(e){function t(e,t){return"P"+(t?1:2)+": "+e.entry.title+"\nScore: "+e.score+"\nErrors: "+e.stats.errors+"\nTimeouts: "+e.stats.timeouts+"\nMalformed actions: "+e.stats.malformed+"\nFailed actions: ["+e.stats.invalid.toString().replace(/,/g,", ")+"]"}var r="GAME OVER - ";return r+=e.p1.score>e.p2.score?"PLAYER 1 WINS":e.p1.score<e.p2.score?"PLAYER 2 WINS":"TIE GAME",r+="\n\n"+t(e.p1,!0)+"\n\n"+t(e.p2,!1)}function createGame(e,t){function r(e){return{entry:e,bots:new Array(G.BOTS),mem:"",score:0,stats:{errors:0,timeouts:0,malformed:0,invalid:Array.apply(null,new Array(G.BOTS)).map(Number.prototype.valueOf,0)}}}var o={},a=Math.floor(.875*G.H)-1;o.move=0,o.walls=new Array(G.H);for(var n=0;n<G.H;n++){o.walls[n]=new Array(G.W);for(var s=0;s<G.W;s++)o.walls[n][s]=n>a}o.p1=r(e),o.p2=r(t);for(var l=0;l<G.BOTS;l++)o.p1.bots[l]={x:l,y:a,hasWall:!1},o.p2.bots[l]={x:G.W-1-l,y:a,hasWall:!1};if(-1===o.p1.entry.id||-1===o.p2.entry.id){var i=decode(Q("#testEntry").val());-1===o.p1.entry.id&&(o.p1.entry.code=i),-1===o.p2.entry.id&&(o.p2.entry.code=i)}return resetGoal(o),G.DEBUG&&console.log("======== NEW GAME: "+o.p1.entry.title+" VS "+o.p2.entry.title+" ========"),o}function moveGame(e){movePlayer(e,++e.move%2===1),++e.goal.age>=G.GOAL_LIFESPAN&&resetGoal(e)}function setupParams(e,t){function r(e,t){var r=toKey(e,t);if(!n.hasOwnProperty(r)){n[r]=!1;for(var a=0;a<G.BOTS;a++)if(Math.abs(o.bots[a].x-e)<=G.LOS&&Math.abs(o.bots[a].y-t)<=G.LOS){n[r]=!0;break}}return n[r]}var o=t?e.p1:e.p2,a=t?e.p2:e.p1,n={},s={};s.p1=t,s.id=o.entry.id,s.eid=a.entry.id,s.score=o.score,s.escore=a.score,s.move=Math.floor((e.move+1)/2),s.goal={x:e.goal.x,y:e.goal.y},s.getMem=function(){return o.mem},s.setMem=function(e){isString(e)&&e.length<=G.MEM_MAX_LENGTH&&(o.mem=e)},s.grid=function(t,o){return isInt(t)&&isInt(o)&&r(t,o)?outOfBounds(t,o)?0:e.walls[o][t]?1:0:-1},s.bots=new Array(G.BOTS),s.ebots=[];for(var l=0;l<G.BOTS;l++)s.bots[l]={x:o.bots[l].x,y:o.bots[l].y,hasWall:o.bots[l].hasWall},r(a.bots[l].x,a.bots[l].y)&&s.ebots.push({x:a.bots[l].x,y:a.bots[l].y,hasWall:a.bots[l].hasWall});return shuffle(s.ebots),-1===o.entry.id&&(s.console=console),s}function movePlayer(e,t){var r,o,a=t?e.p1:e.p2,n=t?e.p2:e.p1,s=setupParams(e,t);G.DEBUG&&(console.log("######## MOVE "+e.move+" - P"+(t?1:2)+" ########"),console.log("PARAMETERS:"),console.log(s)),o=performance.now();try{r=maskedEval(a.entry.code,s)}catch(n){return a.stats.errors++,void(G.DEBUG&&(console.log("!!!! ERRORED !!!!"),console.log(n)))}if(o=performance.now()-o,G.DEBUG&&console.log("TIME TAKEN: "+o+"ms"),o>G.TIME_LIMIT)return a.stats.timeouts++,void(G.DEBUG&&console.log("!!!! TIMED OUT !!!!"));if(G.DEBUG&&(console.log("ACTIONS:"),console.log(r)),!Array.isArray(r)||r.length!==G.BOTS)return a.stats.malformed++,void(G.DEBUG&&console.log("!!!! MALFORMED ACTIONS !!!!"));for(var l=0;l<G.BOTS;l++)if(!isInt(r[l])||r[l]<0||r[l]>24)return a.stats.malformed++,void(G.DEBUG&&console.log("!!!! MALFORMED ACTIONS !!!!"));performActions(e,a,r)}function performActions(e,t,r){function o(e){t.stats.invalid[e]++,G.DEBUG&&console.log("!! BOT"+e+" ACTION FAILED !!")}function a(e){return e.x!==i||e.y!==c}for(var n=!1,s=0;s<G.BOTS;s++){var l=r[s];if(l){var i,c;switch((l-1)%8){case 0:i=-1,c=-1;break;case 1:i=0,c=-1;break;case 2:i=1,c=-1;break;case 3:i=-1,c=0;break;case 4:i=1,c=0;break;case 5:i=-1,c=1;break;case 6:i=0,c=1;break;case 7:i=1,c=1}if(i+=t.bots[s].x,c+=t.bots[s].y,outOfBounds(i,c))o(s);else switch(Math.floor((l-1)/8)){case 0:!e.walls[c][i]&&(i>0&&c>0&&e.walls[c-1][i-1]||c>0&&e.walls[c-1][i]||i<G.W-1&&c>0&&e.walls[c-1][i+1]||i>0&&e.walls[c][i-1]||i<G.W-1&&e.walls[c][i+1]||i>0&&c<G.H-1&&e.walls[c+1][i-1]||c<G.H-1&&e.walls[c+1][i]||i<G.W-1&&c<G.H-1&&e.walls[c+1][i+1])?(t.bots[s].x=i,t.bots[s].y=c,i!==e.goal.x||c!==e.goal.y||n||(n=!0,G.DEBUG&&console.log("** BOT"+s+" REACHED GOAL **"))):o(s);break;case 1:e.walls[c][i]&&!t.bots[s].hasWall?(e.walls[c][i]=!1,t.bots[s].hasWall=!0):o(s);break;case 2:!e.walls[c][i]&&t.bots[s].hasWall&&e.p1.bots.every(a)&&e.p2.bots.every(a)?(e.walls[c][i]=!0,t.bots[s].hasWall=!1):o(s)}}}n&&(t.score++,resetGoal(e)),G.DEBUG&&(console.log("FINAL PLAYER STATE:"),console.log(t))}function resetGoal(e){for(var t={},r=[],o=0;o<G.BOTS;o++)t[toKey(e.p1.bots[o].x,e.p1.bots[o].y)]=!0,t[toKey(e.p2.bots[o].x,e.p2.bots[o].y)]=!0;for(var a=0;a<G.H;a++)for(var n=0;n<G.W;n++){var s=toKey(n,a);t.hasOwnProperty(s)||r.push(s)}var l=fromKey(r[rnd(r.length)]);e.goal={age:0,x:l.x,y:l.y}}function drawGame(e){function t(e,t){G.CTX.fillRect(e*G.SCALE,t*G.SCALE,G.SCALE,G.SCALE)}function r(e,t){G.CTX.fillRect(e*G.SCALE+1,t*G.SCALE+1,G.SCALE-2,G.SCALE-2)}G.CTX.fillStyle=G.COLORS.AIR,G.CTX.fillRect(0,0,G.CW,G.CH),G.CTX.fillStyle=G.COLORS.WALL;for(var o=0;o<G.H;o++)for(var a=0;a<G.W;a++)e.walls[o][a]&&t(a,o);if(G.SHOW_LOS){var n=(2*G.LOS+1)*G.SCALE;G.CTX.fillStyle=G.COLORS.P1_LOS;for(var s=0;s<G.BOTS;s++)G.CTX.fillRect((e.p1.bots[s].x-G.LOS)*G.SCALE,(e.p1.bots[s].y-G.LOS)*G.SCALE,n,n);G.CTX.fillStyle=G.COLORS.P2_LOS;for(var s=0;s<G.BOTS;s++)G.CTX.fillRect((e.p2.bots[s].x-G.LOS)*G.SCALE,(e.p2.bots[s].y-G.LOS)*G.SCALE,n,n)}G.CTX.fillStyle=G.COLORS.P1;for(var s=0;s<G.BOTS;s++)t(e.p1.bots[s].x,e.p1.bots[s].y);G.CTX.fillStyle=G.COLORS.P2;for(var s=0;s<G.BOTS;s++)t(e.p2.bots[s].x,e.p2.bots[s].y);G.CTX.fillStyle=G.COLORS.WALL;for(var s=0;s<G.BOTS;s++)e.p1.bots[s].hasWall&&r(e.p1.bots[s].x,e.p1.bots[s].y),e.p2.bots[s].hasWall&&r(e.p2.bots[s].x,e.p2.bots[s].y);if(G.SHOW_NUMBERS){var l=-.1,i=2.75;G.CTX.fillStyle=G.COLORS.P1_TEXT;for(var s=0;s<G.BOTS;s++)G.CTX.fillText(s.toString(),(e.p1.bots[s].x+l)*G.SCALE,(e.p1.bots[s].y+i)*G.SCALE);G.CTX.fillStyle=G.COLORS.P2_TEXT;for(var s=0;s<G.BOTS;s++)G.CTX.fillText(s.toString(),(e.p2.bots[s].x+l)*G.SCALE,(e.p2.bots[s].y+i)*G.SCALE)}G.CTX.fillStyle=G.COLORS.GOAL,t(e.goal.x+1,e.goal.y),t(e.goal.x-1,e.goal.y),t(e.goal.x,e.goal.y+1),t(e.goal.x,e.goal.y-1),G.SCOREBOARD.P1SCORE.text(e.p1.score),G.SCOREBOARD.MOVE.text(e.move),G.SCOREBOARD.P2SCORE.text(e.p2.score)}function loadPlayers(e){var t=/<pre\b[^>]*><code\b[^>]*>([\s\S]*?)<\/code><\/pre>/,r=/<h1\b[^>]*>(.*?)<\/h1>/;G.PLAYERS=[];var o={id:-1,dq:!1,code:void 0,link:"javascript:;",title:"TEST ENTRY [-1]"};G.PLAYERS.push(o);var a=[];e.forEach(function(e){var o=decode(e.owner.display_name),n=t.exec(e.body),s=r.exec(e.body);if(null===n||n.length<=1||null===s||s.length<=1)return a.push(" "),void a.push(Q("<a>").text(o).attr("href",e.link));var l={};l.id=e.answer_id,l.dq=G.DQ_ANSWERS.indexOf(e.answer_id)>-1||G.DQ_USERS.indexOf(e.owner.user_id)>-1,l.code=decode(n[1]),l.link=e.link,l.title=s[1].substring(0,20)+" - "+o+" ["+l.id.toString()+"]",l.dq&&(l.title+="[DQ]"),G.PLAYERS.push(l)}),a.length>0&&(Q("#invalid").empty().append(a),Q("#invalidWrapper").show());for(var n=new Array(G.PLAYERS.length),s=new Array(G.PLAYERS.length),l=0;l<G.PLAYERS.length;l++)n[l]=Q("<option>").text(G.PLAYERS[l].title).val(l),s[l]=Q("<option>").text(G.PLAYERS[l].title).val(l);Q("#p1Select").empty().append(n).val(rnd(G.PLAYERS.length)),changeSelect(!0),Q("#p2Select").empty().append(s).val(rnd(G.PLAYERS.length)),changeSelect(!1)}function loadAnswers(e,t,r){function o(){Q.get("https://api.stackexchange.com/2.2/questions/"+t.toString()+"/answers?page="+(s++).toString()+"&pagesize=100&order=asc&sort=creation&site="+e+"&filter=!YOKGPOBC5Yad4mOOn8Z4WcAE6q",a)}function a(e){e.hasOwnProperty("error_id")?r(e.error_id.toString()):(n=n.concat(e.items),e.hasMore?o():r(n))}var n=[],s=1;o(s,a)}Q=jQuery,Q(reload);</script>
```

**This question has its own chatroom.** I'll post leaderboards there every few days.

# Answer
# Black Knight

The bot's name comes from an early plan to have it be able to move like a chess knight: over two, up one, etc, which would be faster in some cases.

```
var moves = new Array(8),
    mem = getMem(), newMem = '';

var decodeMem = function(){
  //mmtxy
  for(var ind = 0; ind < 8; ind++){
    var sub = mem.substr(ind * 5, 5)
    bots[ind].lastMove = parseInt(sub[0], 36);
    bots[ind].last2Move = parseInt(sub[1], 36);
    bots[ind].timesStill = sub.charCodeAt(2) - 48;
    bots[ind].lastX = sub.charCodeAt(3) - 187;
    bots[ind].lastY = sub.charCodeAt(4) - 187;
  }
}
decodeMem();

var distanceTo = function(fromX, fromY, toX, toY){
  // Chebyshev distance
  return Math.max(Math.abs(fromX - toX),
                  Math.abs(fromY - toY));
}

var direction = function(from, to){ // Math.sign()
  var diff = to - from;
  return diff > 0 ? 1 : (diff < 0 ? -1 : 0);
}

var dirs = [
  [1, 2, 3],
  [4, 0, 5],
  [6, 7, 8]
];

var moveTo = function(from, to){
  var prioritiesWall = [
    [0],
    [1, 2, 4, 17, 18, 20, 19, 22, 23, 21, 3, 6, 5, 7, 24, 8],
    [2, 3, 1, 17, 19, 18, 23, 22, 24, 4, 5, 20, 21, 6, 8, 7],
    [3, 2, 5, 19, 18, 21, 17, 24, 23, 20, 1, 8, 4, 7, 22, 6],
    [4, 1, 6, 22, 17, 20, 21, 24, 19, 2, 7, 18, 23, 3, 8, 5],
    [5, 3, 8, 24, 19, 21, 20, 22, 17, 2, 7, 18, 23, 1, 6, 4],
    [6, 4, 7, 22, 20, 23, 17, 24, 18, 21, 1, 8, 2, 5, 19, 3],
    [7, 8, 6, 22, 24, 23, 18, 17, 19, 4, 5, 20, 21, 1, 3, 2],
    [8, 5, 7, 24, 21, 23, 19, 22, 18, 20, 3, 6, 2, 4, 17, 1]
  ];
  var prioritiesNoWall = [
    [9, 10, 11, 12, 13, 14, 15, 16, 0],
    [1, 2, 4, 9, 16, 10, 12, 3, 6, 11, 14, 5, 7, 13, 15, 8],
    [2, 3, 1, 10, 15, 14, 16, 4, 5, 12, 13, 9, 11, 6, 8, 7],
    [3, 2, 5, 11, 14, 10, 13, 1, 8, 9, 16, 4, 7, 12, 15, 6],
    [4, 1, 6, 12, 13, 16, 11, 2, 7, 10, 15, 9, 14, 3, 8, 5],
    [5, 3, 8, 13, 12, 14, 9, 2, 7, 10, 15, 11, 16, 1, 6, 4],
    [6, 4, 7, 14, 11, 12, 15, 1, 8, 9, 16, 2, 5, 10, 13, 3],
    [7, 8, 6, 15, 10, 9, 11, 4, 5, 12, 13, 14, 16, 1, 3, 2],
    [8, 5, 7, 16, 9, 13, 15, 3, 6, 11, 14, 2, 4, 10, 12, 1]
  ];

  var dir = dirs[direction(from.y, to.y) + 1][direction(from.x, to.x) + 1],
      method = from.hasWall ? prioritiesWall[dir] : prioritiesNoWall[dir];

  if(distanceTo(from.x, from.y, goal.x, goal.y) === 1){
    method.splice(1,2);
  }

  for(var i=0; i<method.length; i++){
    var attempt = method[i];
    if(checkMove(from, attempt)) return attempt;
  }
  return 0;
}

var numWalls = function(x, y, indexes){
  var allCoords = [
    [x - 1, y - 1],
    [x,     y - 1],
    [x + 1, y - 1],
    [x - 1, y    ],
    [x + 1, y    ],
    [x - 1, y + 1],
    [x,     y + 1],
    [x + 1, y + 1],
  ];
  var allTypes = allCoords.map(function(e){
    return grid(e[0], e[1]); // air = 0, wall = 1
  });
  var justWalls = allTypes.filter(function(e){
    return e === 1;
  }).length;

  return indexes ? allTypes : justWalls;
}

var checkMove = function(coords, moveCode){
  var x = coords.x, y = coords.y,
      baseX = [0, -1, 0, 1, -1, 1, -1, 0, 1],
      baseY = [0, -1, -1, -1, 0, 0, 1, 1, 1],
      targetX = x + baseX[(moveCode - 1) % 8 + 1],
      targetY = y + baseY[(moveCode - 1) % 8 + 1];

  if((targetX > 127 || targetX < 0 || targetY > 63 || targetY < 0) || // Don't bother if it's out of bounds
     (coords.timesStill > 2 && x == coords.lastX && y == coords.lastY && (moveCode == coords.lastMove || moveCode == coords.last2Move)))
    // Or is doing the same moves and not moving
    return false;

  var targetGrid = grid(targetX, targetY), enemyNear = false, couldStrandEnemy = false,
      eWallDirMove, hasNeighbor = numWalls(targetX, targetY) > 0;

  ebots.forEach(function(ebot){
    // Don't place a wall where an enemy can take it
    if(distanceTo(targetX, targetY, ebot.x, ebot.y) === 1 && !ebot.hasWall && (y != ebot.y || x != ebot.x))
      enemyNear = true;

    // Don't move if you can strand an enemy
    var eWallDir = numWalls(ebot.x, ebot.y, true).indexOf(1) + 1,
        wallX = ebot.x + baseX[eWallDir], wallY = ebot.y + baseY[eWallDir];

    if(!coords.hasWall && numWalls(ebot.x, ebot.y) === 1 &&
       distanceTo(x, y, wallX, wallY) === 1){
      eWallDirMove = dirs[direction(y, wallY) + 1][direction(x, wallX) + 1] + 8;
      couldStrandEnemy = true;
    }
  })

  if(targetX == goal.x && targetY == goal.y && targetGrid === 0){
    targetGrid = 2 // Don't place a wall in the goal
  } else {
    ebots.concat(bots).forEach(function(bot){
      // Ensure target cell doesn't have a bot in it
      if(bot.x == targetX && bot.y == targetY) targetGrid = 2;
    });
  }

  return ((moveCode < 9 && targetGrid !== 1 && hasNeighbor && !couldStrandEnemy) || // Move
          (moveCode > 8 && moveCode < 17 && targetGrid === 1 && !coords.hasWall && (!couldStrandEnemy || (couldStrandEnemy && eWallDirMove == moveCode))) || // Grab
          (moveCode > 16 && targetGrid === 0 && coords.hasWall && !enemyNear)) // Place
}

var goalClosest = {dist: Infinity}, rescuers = {};
bots.forEach(function(bot, index){

  // Check if bot is stranded
  bot.stranded = false;
  if(numWalls(bot.x, bot.y) / 8 == bot.hasWall){
    bot.stranded = true;
    rescuers[index] = -1;
  }
});

bots.forEach(function(bot, index){
  if(!bot.stranded){
    // Find which bot is closest to the goal
    var goalDist = distanceTo(bot.x, bot.y, goal.x, goal.y);

    if(goalDist < goalClosest.dist){
      goalClosest.dist = goalDist;
      goalClosest.index = index;
    }
  }
});

bots.forEach(function(bot, index){
  var destination = {
    x: 14 + (index % 4) * 32 + 3 * (index > 3),
    y: index > 3 ? 55 : 27
  }
  if(index == goalClosest.index){
    destination = goal;
  }

  moves[index] = moveTo(bot, destination);

  if(moves[index] == bot.lastMove || moves[index] == bot.last2Move) bot.timesStill++;

  newMem += moves[index].toString(36) +
    bot.lastMove.toString(36) +
    String.fromCharCode(bot.timesStill + 48) +
    String.fromCharCode(bot.x + 187) +
    String.fromCharCode(bot.y + 187);
});

setMem(newMem);

return moves;

```

## Explanation

Determining which move to make for each bot can be divided into two main tasks: figuring out where to go and how to get there.

### Where to go

The basic task of figuring out where to go is easy: go towards the goal if you're closest, or otherwise try to position yourself as far away from teammates. It first goes through each bot and determines if it is stranded (i.e. it has no blocks surrounding it and isn't holding a wall, or it is surrounded by walls and holds a wall). It then loops through the bots again to find the non-stranded bot closest to the goal. All other bots make their way towards being spaced out, with the bottom row on the surface of the blocks (`y=55`) and the top row at `y=27`. Once it knows where to go, it hands it off to the `moveTo` function.

### How to get there

Deciding how to get to the destination is far more difficult because the bots must always be adjacent to a wall to move. It first figures out the direction code (1–8) of the destination relative to its current position. For example, if a bot were at the bottom-left corner and it wanted to go to the top right, it would use the direction code 3. For each direction, I hardcoded a list of moves, with the first being the ideal, top-priority move, and the last being the last resort. This is separated by whether or not the bot has a wall, because you cannot use a place move without a wall or use a grab move while already having a wall.

Of course, using the ideal move doesn't always work, and it would result in a lot of failed actions. This is where `checkMove` comes in. This function checks the potential move against every requirement, to prevent the bot from moving out of bounds or into a wall, for example. If a nearby enemy bot can be stranded (it has only one adjacent wall that can be taken by the bot), that becomes its priority, so the function will return `false` for an otherwise legitimate move so it can skip to the grab moves and take out the enemy. The function prevents several other stupid moves like placing a wall in the goal or another bot.

### The memory string

Sometimes the bot will not be actually stranded but will keep trying the same move and not end up moving (usually picking up a wall and putting it down, picking it up and putting it down, etc). To prevent this, it uses the memory string to remember its last two moves, its last x and y position, and how many times it has been still. Each datum is encoded as a single character for easy splitting. (The string has to be 256 *characters*, not bytes, so using multibyte Unicode characters isn't a problem, as it is with typical golfing challenges.)

For example, say a bot grabbed the wall on its left (code `12`) this turn, replaced it to its left (code `20`) in its previous turn, and has been at the coordinates (`107`, `3`) for the past `16` turns. The memory string for this instance would be encoded as follows:

* `ck`: The two latest action codes are converted to base36 to make the two-digit numbers a single letter.
* `@`: The number of times it has been still is represented as the ASCII character with that code + 48 to skip over unprintable characters and so the first nine times still shows the actual number (`String.fromCharCode(0 + 48)``0`).
* `Ħ¾`: The x and y coordinates are also represented as as the character with that value, this time offset by the somewhat-arbitrary value of 187 to avoid problematic characters.

A typical memory string during the game might be `53äÇØb7¼ðÌ00ßĉÖ7m±ĪÚ00ĝÌò00Ĝìò00ĖČò00ĈĬò`, with a group of five characters for each of the eight bots.
> 13 votes

# Answer
# Outposts

The 8 bots each take a 32 by 32 square and run to the centre of it (I offset the centres slightly otherwise they end up pairing up and travelling vertically with one wall block between them, so one of them gets stranded).

Each bot will stay in the centre of its square unless the goal is within 32 cells of its respective centre, in which case it will run to the goal and then back to its centre.

This still uses the Baseline method of reaching its target (goal or centre) so does not move diagonally. Just a starting point...

```
var encodeAction = function(type, dx, dy) {
    var d
    if (dx === -1 && dy === -1) d = 1
    else if (dx === 0 && dy === -1) d = 2
    else if (dx === 1 && dy === -1) d = 3
    else if (dx === -1 && dy === 0) d = 4
    else if (dx === 1 && dy === 0) d = 5
    else if (dx === -1 && dy === 1) d = 6
    else if (dx === 0 && dy === 1) d = 7
    else if (dx === 1 && dy === 1) d = 8
    else return 0
    return 8 * type + d
}

var getNeighborCell = function(x, y, wallState) {
    if (x > 0 && y > 0 && grid(x - 1, y - 1) === wallState) return { x: x - 1, y: y - 1 }
    if (y > 0 && grid(x, y - 1) === wallState) return { x: x, y: y - 1 }
    if (x < 127 && y > 0 && grid(x + 1, y - 1) === wallState) return { x: x + 1, y: y - 1 }
    if (x > 0 && grid(x - 1, y) === wallState) return { x: x - 1, y: y }
    if (x < 127 && grid(x + 1, y) === wallState) return { x: x + 1, y: y }
    if (x > 0 && y < 63 && grid(x - 1, y + 1) === wallState) return { x: x - 1, y: y + 1 }
    if (y < 63 && grid(x, y + 1) === wallState) return { x: x, y: y + 1 }
    if (x < 127 && y < 63 && grid(x + 1, y + 1) === wallState) return { x: x + 1, y: y + 1 }
    return null
}

var moveBot = function(n) {
    var assignedX = (n % 4) * 32 + 14 + Math.floor(n/4) * 4
    var assignedY = (Math.floor(n / 4)) * 32 + 16
    if (Math.abs(goal.x - assignedX) < 33 && Math.abs(goal.y - assignedY) < 33) {
        assignedX = goal.x
        assignedY = goal.y
    }
    var b = bots[n], moveX = b.x !== assignedX, x = b.x, y = b.y, type
    if (moveX) {
        x += b.x < assignedX ? 1 : -1
    } else {
        y += b.y < assignedY ? 1 : -1
    }
    if (grid(x, y) === 1) {
        if (b.hasWall) {
            type = 2 //place
            var c = getNeighborCell(b.x, b.y, 0)
            if (!c) { //stuck holding wall with walls all around
                return 0
            }
            x = c.x
            y = c.y
        } else {
            type = 1 //grab
        }
    } else if (grid(x, y) === 0) {
        if (getNeighborCell(x, y, 1)) {
            type = 0 //move
        } else {
            if (b.hasWall) {
                type = 2 //place
                if (moveX) {
                    y += y > 0 ? -1 : 1
                } else {
                    x += x > 0 ? -1 : 1
                }
            } else {
                type = 1 //grab
                var c = getNeighborCell(b.x, b.y, 1)
                if (!c) { //stuck without wall in midair
                    return 0
                }
                x = c.x
                y = c.y
            }
        }
    } else {
        return 0 //should never get here
    }
    return encodeAction(type, x - b.x, y - b.y)
}

var actions = []
for (var i = 0; i < 8; i++) {
    actions[i] = moveBot(i)
}

return actions

```
> 12 votes

# Answer
# Baseline

This is the simplest consistently functioning bot flock controller I could think of. It will be my only non-disqualified answer and will serve as a baseline to judge other answers by. It is technically in the running to win the contest, but beating it should not be difficult.

Any of the code here may be copied and used in another answer, no attribution required.

```
var encodeAction = function(type, dx, dy) {
    var d
    if (dx === -1 && dy === -1) d = 1
    else if (dx === 0 && dy === -1) d = 2
    else if (dx === 1 && dy === -1) d = 3
    else if (dx === -1 && dy === 0) d = 4
    else if (dx === 1 && dy === 0) d = 5
    else if (dx === -1 && dy === 1) d = 6
    else if (dx === 0 && dy === 1) d = 7
    else if (dx === 1 && dy === 1) d = 8
    else return 0
    return 8 * type + d
}

var getNeighborCell = function(x, y, wallState) {
    if (x > 0 && y > 0 && grid(x - 1, y - 1) === wallState) return { x: x - 1, y: y - 1 }
    if (y > 0 && grid(x, y - 1) === wallState) return { x: x, y: y - 1 }
    if (x < 127 && y > 0 && grid(x + 1, y - 1) === wallState) return { x: x + 1, y: y - 1 }
    if (x > 0 && grid(x - 1, y) === wallState) return { x: x - 1, y: y }
    if (x < 127 && grid(x + 1, y) === wallState) return { x: x + 1, y: y }
    if (x > 0 && y < 63 && grid(x - 1, y + 1) === wallState) return { x: x - 1, y: y + 1 }
    if (y < 63 && grid(x, y + 1) === wallState) return { x: x, y: y + 1 }
    if (x < 127 && y < 63 && grid(x + 1, y + 1) === wallState) return { x: x + 1, y: y + 1 }
    return null
}

var moveBot = function(n) {
    var b = bots[n], moveX = b.x !== goal.x, x = b.x, y = b.y, type
    if (moveX) {
        x += b.x < goal.x ? 1 : -1
    } else {
        y += b.y < goal.y ? 1 : -1
    }
    if (grid(x, y) === 1) {
        if (b.hasWall) {
            type = 2 //place
            var c = getNeighborCell(b.x, b.y, 0)
            if (!c) { //stuck holding wall with walls all around
                return 0
            }
            x = c.x
            y = c.y
        } else {
            type = 1 //grab
        }
    } else if (grid(x, y) === 0) {
        if (getNeighborCell(x, y, 1)) {
            type = 0 //move
        } else {
            if (b.hasWall) {
                type = 2 //place
                if (moveX) {
                    y += y > 0 ? -1 : 1
                } else {
                    x += x > 0 ? -1 : 1
                }
            } else {
                type = 1 //grab
                var c = getNeighborCell(b.x, b.y, 1)
                if (!c) { //stuck without wall in midair
                    return 0
                }
                x = c.x
                y = c.y
            }
        }
    } else {
        return 0 //should never get here
    }
    return encodeAction(type, x - b.x, y - b.y)
}

var actions = []
for (var i = 0; i < 8; i++) {
    actions[i] = moveBot(i)
}

return actions

```

Each of the 8 bots independently follows the same basic method. They tend to clump together because of this, unless they get separated by something external. The bots never care about where teammates or enemies are, they only attempt to move toward the goal. They only move orthogonally, first matching their x with the goal x, then their y. Never moving diagonally means they waste a lot of time in travel.

The movement algorithm of each bot is as follows:

```
If my X is not equal to the goal's X
    P = position to my left or right that is closer to the goal
    Make a note that I'm trying to move horizontal
Else
    P = position above or below me that is closer to the goal
    Make a note that I'm trying to move vertical

If P is a wall
    If I'm holding a wall
        Place my wall in any neighboring air cell
    Else
        Grab the wall at P
Else if P is air
    If P has a wall neighboring it (i.e. if I can move to P)
        Move to P
    Else
        If I'm holding a wall
            If I'm trying to move horizontal
                Place my wall above or below P
            Else if I'm trying to move vertical
                Place my wall to the left or right of P
        Else
            Grab wall from any neighboring wall cell

```
> 9 votes

# Answer
# Seekers

Stll work in progress. I have many ideas, but almost none of them do work.

~~Above all, big problem with failed actions.~~ Solved!

```
var action=[], myGrid=[], goalSort=[], i, j, curBot, curAction, goalSeek;

var check = function(x,y) {
  return (myGrid[[x,y]] || (myGrid[[x,y]] = grid(x,y)))|0;
};

var setGrid = function(x,y,v) {
  myGrid[[x,y]] = v + '';
};

var orGrid = function(x,y,v) {
  myGrid[[x,y]] |= v;
};

var encodeDir = function(dx, dy) {
    return dx < 0 && dy < 0 ? 1
    : dx === 0 && dy < 0 ? 2
    : dx > 0 && dy < 0 ? 3
    : dx < 0 && dy === 0 ? 4
    : dx > 0 && dy === 0 ? 5
    : dx < 0 && dy > 0 ? 6
    : dx === 0 && dy > 0 ? 7
    : dx > 0 && dy > 0 ? 8
    : 0;
};

var distance = function(p1, p2) {
  return Math.max(Math.abs(p1.x-p2.x),Math.abs(p1.y-p2.y));
};

var cellNearWall = function(x,y)
{
  var r = check(x,y) == 1 ? 0
  : check(x-1,y-1) == 1 ? 1
  : check(x,y-1) == 1 ? 2
  : check(x+1,y-1) == 1 ? 3
  : check(x-1,y) == 1 ? 4
  : check(x+1,y) == 1 ? 5
  : check(x-1,y+1) == 1 ? 6
  : check(x,y+1) == 1 ? 7
  : check(x+1,y+1) == 1 ? 8
  : 0;
  return r;
};

var cellNearBot = function(x,y,m)
{
  return check(x-1,y-1) & m ? 1
  : check(x,y-1) & m ? 2
  : check(x+1,y-1) & m ? 3
  : check(x-1,y) & m ? 4
  : check(x+1,y) & m ? 5
  : check(x-1,y+1) & m ? 6
  : check(x,y+1) & m ? 7
  : check(x+1,y+1) & m ? 8
  : 0;
};

var tryGrabWall = function(x, y)
{
  var dx, dy, r = 8;
  for(dy = -1; dy < 2; ++dy)
  {
    for(dx = -1; dx < 2; ++dx)
    {
      if (dx|dy)
      {
        ++r;
        if (check(x+dx, y+dy) == 1)
        {
          setGrid(x+dx, y+dy, 0); // remember that the wall is not there anymore
          return r;
        }
      }
    }
  }
  return 0;
};

var tryDropWall= function(x, y)
{
  var dx, dy, r = 16;
  for(dy = -1; dy < 2; ++dy)
  {
    for(dx = -1; dx < 2; ++dx)
    {
      if (dx|dy)
      {
        ++r;
        if (x+dx>=0 & x+dx < 128 & y+dy >= 0 & y+dy < 64 && check(x+dx, y+dy) == 0)
        {
          setGrid(x+dx, y+dy, 1); // remember that the wall is there
          return r;
        }
      }
    }
  }
  return 0;
};

var approach = function(bot, target)
{
  var dx, dy, tx, ty, r = 0, wallPos;

  var checkDrop = function(dx,dy)
  {
    var x = bot.x+dx, y = bot.y+dy;
    if (check(x,y) == 0 && cellNearBot(x,y,8) == 0)
    {
      setGrid(x, y, 1);
      return 16 + encodeDir(dx, dy);
    }
  };

  dy = target.y - bot.y;
  dy = dy < 0 ? -1 : dy > 0 ? 1 : 0;
  dx = target.x - bot.x;
  dx = dx < 0 ? -1 : dx > 0 ? 1 : 0;
  tx = bot.x+dx;
  ty = bot.y+dy;

  if ((dx|dy) === 0)
  {
    if (!bot.hasWall) {
      return tryGrabWall(bot.x, bot.y);
    }
    return 0;
  }

  if (cellNearWall(tx,ty))
  {
    setGrid(tx, ty, 2);
    return encodeDir(dx, dy);
  }

  if (dx === 0)
  {
    if (cellNearWall(bot.x-1,ty))
    {
      setGrid(bot.x-1, ty, 2);
      return encodeDir(-1, dy);
    }
    if (cellNearWall(bot.x+1,ty))
    {
      setGrid(bot.x+1, ty, 2);
      return encodeDir(1, dy);
    }
    if (bot.hasWall)
    {
      if (wallPos = checkDrop(1,dy)) { return wallPos; }
      if (wallPos = checkDrop(-1,dy)) { return wallPos; }
      if (wallPos = checkDrop(1,0)) { return wallPos; }
      if (wallPos = checkDrop(-1,0)) { return wallPos; }
    }
  }
  else if (dy === 0)
  {
    if (cellNearWall(tx,bot.y-1))
    {
      setGrid(tx, bot.y-1, 2);
      return encodeDir(dx, -1);
    }
    if (cellNearWall(tx,bot.y+1))
    {
      setGrid(tx, bot.y+1, 2);
      return encodeDir(dx, 1);
    }
    if (bot.hasWall)
    {
      if (wallPos = checkDrop(dx,1)) { return wallPos; }
      if (wallPos = checkDrop(dx,-1)) { return wallPos; }
      if (wallPos = checkDrop(0,1)) { return wallPos; }
      if (wallPos = checkDrop(0,-1)) { return wallPos; }
    }
  }
  else
  {
    if (cellNearWall(tx,bot.y))
    {
      setGrid(tx, bot.y, 2);
      return encodeDir(dx, 0);
    }
    if (cellNearWall(bot.x,ty))
    {
      setGrid(bot.x, ty, 2);
      return encodeDir(0,dy);
    }
    if (bot.hasWall) {
      if (wallPos = checkDrop(dx,0)) { return wallPos; }
      if (wallPos = checkDrop(0,dy)) { return wallPos; }
      if (wallPos = checkDrop(dx,dy)) { return wallPos; }
    }
  }

  if (!bot.hasWall)
  {
  if (check(tx, ty) == 1)
  {
      setGrid(tx, ty, 0); // remember that the wall is not there anymore
      return 8 + encodeDir(dx, dy);
    };
    return tryGrabWall(bot.x, bot.y);
  }
  else
  {
    return tryDropWall(bot.x, bot.y);
  }
};

for (i=0; curBot=ebots[i]; i++)
{
  setGrid(curBot.x, curBot.y, curBot.hasWall ? 4 : 8);
}

var goalDistance=[]

for (i=0; curBot=bots[i]; i++)
{
  orGrid(curBot.x, curBot.y, 2);
  goalDistance[i] = distance(curBot, goal);
}
var sorted = goalDistance.slice().sort(function(a,b){return a-b})
var ranks = goalDistance.slice().map(function(v){ return sorted.indexOf(v)});

var tt = p1
? [ { x:32, y:20 },{ x:32, y:55 },{ x:64, y:20 },{ x:64, y:55 },
   { x:96, y:20 },{ x:96, y:55 },{ x:16, y:30 },{ x:112, y:30 }]
: [ { x:96, y:20 },{ x:96, y:55 },{ x:64, y:20 },{ x:64, y:55 },
   { x:32, y:20 },{ x:32, y:55 },{ x:112, y:30 },{ x:16, y:30 }]

var goalSeek = 3;

for (i=0; curBot=bots[i]; i++)
{
  if (ranks[i] < goalSeek)
  {
    curAction = approach(curBot, goal);
    if (curAction == 0) goalSeek += 1;
  }
  else
    curAction = approach(curBot, tt[i]);

  action[i] = curAction;
}

return action;

```
> 6 votes

# Answer
# Teamplayer

At the moment, this submission is far from perfect. It has a similar strategy like Outposts, but only 6 bots are "in the air". The other 2 bots supply them with walls if they got stolen. **Edit:** The supporter bots perform much better now.

```
var outside = function(x,y) {
    return x < 0 || x > 127 || y < 0 || y > 127
}

var distance = function(x1, y1, x2, y2){
  return Math.sqrt(Math.pow(x1-x2, 2) + Math.pow(y1-y2, 2));
}

var isStuck = function(bot) {
    if (bot.hasWall) {
        for (var i=-1; i<=1; i++) {
            for (var j=-1; j<=1; j++) {
                if ((i != 0 || j != 0) && grid(bot.x+i,bot.y+j) == 0 && !outside(bot.x+i,bot.y+j))
                    return false
            }
        }
        return true
    }
    for (var i=-1; i<=1; i++) {
        for (var j=-1; j<=1; j++) {
            if (grid(bot.x+i, bot.y+j) == 1)
                return false
        }
    }
    return true
}

var isPlayer = function(x,y) {
    for (var i = 0; i < bots.length; i++) {
        if (bots[i].x == x && bots[i].y == y)
            return true
    }
    for (var i = 0; i < ebots.length; i++) {
        if (ebots[i].x == x && ebots[i].y == y)
            return true
    }
    return false
}

var encodeAction = function(type, dx, dy) {
    var d
    if (dx === -1 && dy === -1) d = 1
    else if (dx === 0 && dy === -1) d = 2
    else if (dx === 1 && dy === -1) d = 3
    else if (dx === -1 && dy === 0) d = 4
    else if (dx === 1 && dy === 0) d = 5
    else if (dx === -1 && dy === 1) d = 6
    else if (dx === 0 && dy === 1) d = 7
    else if (dx === 1 && dy === 1) d = 8
    else return 0
    return 8 * type + d
}

var surrounding = function(x,y) {
    var cell = {hasStone:false, cells: []}
    for (var i=-1; i<=1; i++) {
        for(var j=-1; j<=1; j++) {
            if ((i != 0 || j != 0) && !outside(x+i,y+j)) {
                cell.cells.push({x:x+i, y:y+j})
                if (grid(x+i,y+j) == 1) {
                    cell.hasStone = true
                }
            }
        }
    }
    return cell
}

var hunt = function(i, destination) {
    destination = destination || {x: 31+((i-2)%3)*32, y: 20+((i-2)%2)*21}, bot = bots[i]
    if (i < 5 && i > 1) {
        destination.x -= 2
    }
    if (bot.isStuck) {
        return 0
    }
    if ((p1 && destination.x >= move + i) || (!p1 && 127 - destination.x > move - i)) {
        destination.y = bot.y
    }
    if (i == bestBotId && move > 50) {
        destination.x = goal.x
        destination.y = goal.y
    }
    var dx = destination.x > bot.x ? 1 : destination.x == bot.x ? 0 : -1, newX = bot.x + dx
    var dy = destination.y > bot.y ? 1 : destination.y == bot.y ? 0 : -1, newY = bot.y + dy
    var surr = surrounding(newX, newY), botSurr = surrounding(bot.x, bot.y)
    if (grid(newX, newY) == 0) {
        if (surr.hasStone) {
            return encodeAction(0, dx, dy)
        } else {
            if (bot.hasWall) {
                for (var i=0; i<surr.cells.length; i++) {
                    var cell = surr.cells[i];
                    if (Math.abs(cell.x - bot.x) <= 1 && Math.abs(cell.y - bot.y) <= 1 && grid(cell.x, cell.y) == 0 && !isPlayer(cell.x, cell.y)) {
                        return encodeAction(2, cell.x - bot.x, cell.y - bot.y)
                    }
                }
            } else {
                if (bot.walls.length == 1) {
                    return encodeAction(1, bot.walls[0].x - bot.x, bot.walls[0].y - bot.y)
                } else {
                    for (var i=0; i<bot.walls.length; i++) {
                        var wall = bot.walls[i], canUseWall = true
                        for (var j=0; j<bots.length; j++) {
                            if (bots[j].walls.length == 1 && bots[j].walls[0].x == wall.x && bots[j].walls[0].y == wall.y) {
                                canUseWall = false
                            }
                        }
                        if (canUseWall) {
                            return encodeAction(1, wall.x - bot.x, wall.y - bot.y)
                        }
                    }
                }
            }
        }
    } else {
        if (bot.hasWall) {
            for (var i=0; i<botSurr.cells.length; i++) {
                var cell = botSurr.cells[i];
                if (grid(cell.x, cell.y) == 0 && !isPlayer(cell.x, cell.y) && !outside(cell.x, cell.y)) {
                    return encodeAction(2, cell.x - bot.x, cell.y - bot.y)
                }
            }
        } else {
            return encodeAction(1, dx, dy)
        }
    }
    return 0 //hopefully never happens
}

var help = function(i) {
    if (bots[i].isStuck) {
        return 0
    }
    var bot = bots[i], destination = helpDestinations[i]
    if (destination.stuckBot == -1) {
        if (bot.walls.length >= 2 || (bot.hasWall && bot.walls.length == 1)) {
            var stuckId = -1
            for (var j = 0; j < bots.length; j++) {
                if (j != helpDestinations[(i+1)%2].stuckBot && bots[j].isStuck)
                    stuckId = j
            }
            if (stuckId != -1) {
                destination.stuckBot = stuckId
                destination.x = bots[stuckId].x
                destination.y = bots[stuckId].y
                return 0
            } else {
                return hunt(i, destination)
            }
        } else if (bot.x == destination.x && bot.y == destination.y) {
            if (move % 2 == 0)
                destination.y += 1
            else
                destination.x -= 1
            return hunt(i, destination)
        } else {
            return hunt(i, destination)
        }
    } else if (bots[destination.stuckBot].isStuck) {
        if (bot.walls.length < 2 && !(bot.hasWall && bot.walls.length == 1)) {
            destination.stuckBot = -1
            destination.x = i == 0 ? 42 : 85
            destination.y = 55
            return hunt(i, destination)
        }
        var dx = destination.x > bot.x ? 1 : destination.x == bot.x ? 0 : -1, newX = bot.x + dx
        var dy = destination.y > bot.y ? 1 : destination.y == bot.y ? 0 : -1, newY = bot.y + dy
        var surr = surrounding(newX, newY), botSurr = surrounding(bot.x, bot.y), surrWalls = 0
        for (var i = 0; i < surr.cells.length; i++) {
            var cell = surr.cells[i]
            if (grid(cell.x,cell.y) == 1)
                surrWalls++
        }
        if (grid(newX, newY) == 0) {
            if (surrWalls >= 2 || (surr.hasWall && bot.hasWall)) {
                return encodeAction(0, dx, dy)
            } else {
                if (bot.hasWall) {
                    for (var i=0; i<surr.cells.length; i++) {
                        var cell = surr.cells[i];
                        if (Math.abs(cell.x - bot.x) <= 1 && Math.abs(cell.y - bot.y) <= 1 && grid(cell.x, cell.y) == 0 && !isPlayer(cell.x, cell.y)) {
                            return encodeAction(2, cell.x - bot.x, cell.y - bot.y)
                        }
                    }
                } else {
                    if (bot.walls.length == 1) {
                        return encodeAction(1, bot.walls[0].x - bot.x, bot.walls[0].y - bot.y)
                    } else {
                        for (var i=0; i<bot.walls.length; i++) {
                            var wall = bot.walls[i], canUseWall = true
                            for (var j=0; j<bots.length; j++) {
                                if (bots[j].walls.length == 1 && bots[j].walls[0].x == wall.x && bots[j].walls[0].y == wall.y) {
                                    canUseWall = false
                                }
                            }
                            for (var j=0; j<surr.cells.length; j++) {
                                if (surr.cells[j].x == wall.x && surr.cells[j].y == wall.y)
                                    canUseWall = false
                            }
                            if (canUseWall) {
                                return encodeAction(1, wall.x - bot.x, wall.y - bot.y)
                            }
                        }
                    }
                }
            }
        } else {
            if (bot.hasWall) {
                for (var i=0; i<botSurr.cells.length; i++) {
                    var cell = botSurr.cells[i];
                    if (grid(cell.x, cell.y) == 0 && !isPlayer(cell.x, cell.y)) {
                        return encodeAction(2, cell.x - bot.x, cell.y - bot.y)
                    }
                }
            } else {
                return encodeAction(1, dx, dy)
            }
        }
    } else {
        destination.stuckBot = -1
        destination.x = i == 0 ? 42 : 85
        destination.y = 55
        return hunt(i, destination)
    }
    return 0 //hopefully never happens
}

var moves = new Array(8)
var mem = getMem(), helpDestinations = []
if (mem.length == 0) {
    mem = "42,55,-1 85,55,-1"
}
mem = mem.split(" ")
for (var i = 0; i < mem.length; i++) {
    var cell = mem[i].split(",")
    helpDestinations.push({x: parseInt(cell[0]), y: parseInt(cell[1]), stuckBot: parseInt(cell[2])})
}

for (var i = 0; i < 8; i++) {
    var bot = bots[i]
    var surr = surrounding(bot.x, bot.y)
    bot.walls = []
    for (var j = 0; j < surr.cells.length; j++) {
        if (grid(surr.cells[j].x, surr.cells[j].y) == 1) {
            bot.walls.push(surr.cells[j])
        }
    }
}

bots.forEach(function(bot, index) {
    if(isStuck(bot)) {
        bot.isStuck = true
    }
})

var bestDistance = 1000
var bestBotId = -1
for (var i=2; i<8; i++) {
    var dist = distance(bots[i].x, bots[i].y, goal.x, goal.y)
    if (dist < bestDistance && !bots[i].isStuck) {
        bestDistance = dist
        bestBotId = i
    }
}

for (var i=0; i<8; i++) {
    if (i < 2) {
        moves[i] = help(i)
    } else {
        moves[i] = hunt(i)
    }
}

setMem(helpDestinations[0].x + "," + helpDestinations[0].y + "," + helpDestinations[0].stuckBot + " " + helpDestinations[1].x + "," + helpDestinations[1].y + "," + helpDestinations[1].stuckBot)

return moves

```
> 6 votes

---
Tags: game, geometry, king-of-the-hill, grid, javascript
---


title: Me Want Honeycomb

text:
# Question
Title: Me Want Honeycomb
Write the shortest program that prints this ASCII art section of a hexagonal tiling or honeycomb:

```
       __
    __/  \__
 __/  \__/  \__
/  \__/  \__/  \
\__/  \__/  \__/
/  \__/  \__/  \
\__/  \__/  \__/
/  \__/  \__/  \
\__/  \__/  \__/
   \__/  \__/
      \__/

```
* No input should be taken.
* Output to stdout or your language's closest alternative.
* Instead of a program, you may write a *named* function that takes no parameters and prints the result normally or returns it as a string.
* The output may have any number of leading and/or trailing newlines and each line in the output may have any number of leading and/or trailing spaces (as long as the pattern lines up properly.)
* **The shortest code in bytes wins.**

# Answer
> 33 votes
# CJam, ~~45~~ ~~43~~ ~~42~~ ~~41~~ 40 bytes

```
741e8 36+Ab"\__/  "38*21/.{G2$-<\S*.e<N}

```

Try it online in the CJam interpreter.

### How it works

```
"\__/  "38*21/

```

repeats the pattern `\__/` **38** times and splits it into chunks of length **21**. If the chunks were separated by linefeeds, this would be the result:

```
\__/  \__/  \__/  \__
/  \__/  \__/  \__/
\__/  \__/  \__/  \__
/  \__/  \__/  \__/
\__/  \__/  \__/  \__
/  \__/  \__/  \__/
\__/  \__/  \__/  \__
/  \__/  \__/  \__/
\__/  \__/  \__/  \__
/  \__/  \__/  \__/
\__/  \__/  \__/

```

This clearly contains the desired honeycomb. All that's left to do is to replace some characters with spaces, cut off some others and actually introduce the linefeeds.

```
741e8 36+Ab

```

generates the integer **74 100 000 036** and converts it into the array **\[7 4 1 0 0 0 0 0 0 3 6\]**. Each array element encodes the number of leading characters of the corresponding line that have to get replaced with spaces. By subtracting this number from **16**, we also obtain the correct length for this line.

```
.{            } e# Execute for each pair of a digit D and a line L:
  G2$-<         e#   Chop off L after 16 - D characters.
       \S*      e#   Push a string of D spaces.
          .e<   e#   Compute the vectorized minimum.
             N  e#   Push a linefeed.

```

Since a space has a lower code point than the other characters of **L** and vectorized operators leave the characters of the longer string that do not correspond to one of the shorter one untouched, `.e<` replaces the first **D** characters with spaces.

# Answer
> 28 votes
# Python 2, 73

```
i=0
exec"k=max(7-i,i-24,0);print' '*k+('\__/  '*9)[i:][k:16-k];i+=3;"*11

```

See it run.

For each of the 11 output rows, computes the number of leading spaces `k` as a maximum of three linear functions that form the envelope of the left side of the hexagon. Because the diagonal lines have slope `3` and `-3`, it's better to index the row number as `i=0,3,...30`.

To create the hexagon mesh, we first tile enough of the unit `'\__/ '`. Then, shifting `[i:]` realigns it by 3 for odd rows. Finally, we take the needed portion `[k:16-k]` of it, leaving a margin of `k` on the left and right.

# Answer
> 22 votes
# CJam, ~~65~~ ~~56~~ 55 bytes

```
"Ý6TNð*¯5"303b4b["/\_")"_ "4*S]f=sB/z{_W%"\/"_W%erN}/

```

Try it online in the CJam interpreter.

### Idea

The right half of each line is a reversed copy of the left half with slashes and backslashes swapped. Therefore, it suffices to encode the left half of the honeycomb:

```
       _
    __/
 __/  \_
/  \__/
\__/  \_
/  \__/
\__/  \_
/  \__/
\__/  \_
   \__/
      \_

```

Rather than analyzing this pattern line by line, we can analyze it column by column:

```
   /\/\/\
  _ _ _ _
  _ _ _ _
  /\/\/\/\
 _ _ _ _ _
 _ _ _ _ _
 /\/\/\/\/\
_ _ _ _ _ _

```

Obvious patterns emerge:

* The string `_ _ _ _` occurs five times.
* Every `/` is followed by a `\`.

By replacing every `/\`, `_`, `_ _ _ _` and space with a number from 0 to 3, we can convert the resulting array from a base 4 number to a higher base and store the complete pattern in a compact fashion.

### Code

```
"Ý6TNð*¯5"303b4b  e# Convert the string from base 303 to base 4.
["/\_")"_ "4*S]f= e# Replace each resulting digit by the corresponding item of the array
                  e# ["/\" "_" "_ _ _ _ " " "].
sB/               e# Split into strings of length 11.
z                 e# Zip: transpose rows with columns.
{             }/  e# For each string:
 _W%              e#     Push a reversed copy.
    "\/"_W%er     e#     Swap slashes and backslashes.
             N    e#     Push a linefeed.

```

# Answer
> 10 votes
## C, ~~148~~ ~~144~~ 140 bytes

```
k,r,c,d,p;f(){for(;k<187;k++){r=k/17;c=k%17;d=c+r%2*3;p=3*r+c-7<33u&3*r-c+8<33u;putchar(c==16?10:p&(d+5)%6<2?95:p&d%6==3?47:!p|d%6?32:92);}}

```

With whitespace, without compiler warnings, and before some code tweaks to save a few bytes:

```
#include <stdio.h>

int k, r, c, d, p;

void f() {
    for ( ; k < 187; k++) {
        r = k / 17;
        c = k % 17;
        d = c + 3 * (r % 2);
        p = 3 * r + c - 7 < 33u && 3 * r - c + 8 < 33u;
        putchar(
            c == 16 ? 10 :
            p && (d + 5) % 6 < 2 ? 95 :
            p && d % 6 == 3 ? 47 :
            p && d % 6 == 0 ? 92 :
            32);
    }
}

```

This approach does not use any character/string tables. It loops over all 187 (11 rows, 17 columns including newlines), and decides which character to print for each position, based on a combination of conditions.

The conditions include a test for being inside/outside the 4 corners, using 4 line equations, with the result stored in variable `p`. The rest is then mostly repeating every 6 characters, with the odd rows shifted by 3 characters relative to the even rows.

# Answer
> 7 votes
## Ruby - 78 Bytes

```
(-5..5).map{|i|puts' '*(j=[i.abs*3-i/6-9,0].max)+('/  \__'*4)[j+i%2*3,16-j*2]}

```

---

**A transcription of xnor's solution (69 Bytes):**

```
11.times{|i|puts' '*(j=[7-i*=3,i-24,0].max)+('\__/  '*9)[i+j,16-j*2]}

```

# Answer
> 6 votes
# JavaScript (ES6), 129 ~~130~~

That's a pure string replace/replace/replace ... not taking advantage of any geometric property.

Using template strings, all newlines are significant and count.

Run snippet in Firefox to test

```
f=_=>`70
405
 055
9992 3051
6301`[R='replace'](/9/g,`55123
30551
`)[R](/5/g,1230)[R](/\d/g,n=>['__','/',,'\\'][n]||' '.repeat(n))

// TEST

O.innerHTML = f()
```

```
<pre id=O></pre>
```

# Answer
> 6 votes
# PHP - ~~139~~ ~~137~~ ~~107~~ ~~101~~ ~~91~~ 87 bytes

I don't know if this is the best way to golf it but here is my try at it:

*~~30~~ ~~36~~ ~~46~~ -50 bytes thanks to Ismael Miguel*

Test it online here

```
<?='       __
    __',$a='/  \__',"
 __$a$a
",$c="$a$a/  \
\__$a$a/
","$c$c   \__$a/
      \__/";

```

```
<script src="http://ideone.com/e.js/WHWEZS" type="text/javascript" ></script>
```

old code:

```
<?php $a="/  \\__";$c=$a.$a."/  \\\n\__".$a.$a."/\n";echo "       __\n    __".$a."\n __".$a,$a."\n".$c,$c,$c."   \\__".$a."/\n      \\__/";

```

# Answer
> 4 votes
# Lua 146

```
T="       __\n    __/  \\__\n __/  \\__/  \\__\n"
S="/  \\__/  \\__/  \\\n\\__/  \\__/  \\__/\n"
B="   \\__/  \\__/\n      \\__/"
io.write(T,S,S,S,B)

```

(newlines added for clarity)

# Answer
> 3 votes
## Dart - 113

```
main({r:"/  \\__"}){print("       __\n    __$r\n __$r$r\n${"$r$r/  \\\n\\__$r$r/\n"*3}   \\__$r/\n      \\__/");}

```

Pure string-interpolation solution, nothing fancy. String operations like "substring" are too verbose to compete in practice.

Run it on DartPad.

# Answer
> 3 votes
# Python 3, ~~100~~ 87 bytes

```
n=0x85208e08e08dd445
while n:l=n>>2&15;print(' '*(8-l)+('\__/  '*4)[n&3:n&3|l*2]);n>>=6

```

And a readable version of the code below. The idea is to hardcode the intervals (begin, length) and then pad with the correct amount of spaces to center the interval.

```
hexagon_string = '\__/  ' * 4
for i in range(11):
    # Pick the begin and length of the i-th interval using hardcoded numbers
    b = (0x00030303111 >> 4*i) & 3   # n is a combination of these two numbers
    l = (0x25888888741 >> 4*i) & 15  #
    # Print the interval with appropriate whitespace in front of it
    spaces = ' ' * (8-l)
    print(spaces + hexagon_string[b : b+l*2])

```

# Answer
> 3 votes
# Javascript (*ES7 Draft*), 96 94 93 bytes

Inspiration taken from a few solutions here...

*Edit: -1 from edc65*

```
f=z=>[for(x of[741e6]+36)' '.repeat(x)+'/  \\__'.repeat(4,z^=3).slice(+x+z,16-x+z)].join(`
`)

// For snippet demo:
document.write('<pre>'+f()+'</pre>');
```

**Commented:**

```
f=z=>[
        for(x of [741e6] + 36)        // for each character "x" in "74100000036"
            ' '.repeat(x) +           // x spaces
            '/  \\__'.repeat(4,       // build pattern string
            z ^= 3).                  // toggle z offset (3) for even lines
            slice(+x + z, 16 - x + z) // get appropriate substring
    ].join(`                          // join with newlines
    `)

```

# Answer
> 3 votes
# Retina, 66 bytes

```
<empty line>
sss __<LF>ssa__<LF> aa__<LF>lll dau<LF>ssdu
l
/daa<LF>\aau<LF>
a
ud
u
__/
d
s\
s

```

Each line should go to its own file and `<LF>` means actual newline in the file. 1 byte per extra file added to byte-count.

You can run the code as one file with the `-s` flag, keeping the `<LF>` markers and maybe changing them to newlines in the output for readability if you wish.

The algorithm is 5 simple substitute steps (change odd line content to even line content) starting from an empty input string. The results after each steps are (delimited by `=`'s):

```
sss __
ssa__
 aa__
lll dau
ssdu
============
sss __
ssa__
 aa__
/daa
\aau
/daa
\aau
/daa
\aau
 dau
ssdu
============
sss __
ssud__
 udud__
/dudud
\ududu
/dudud
\ududu
/dudud
\ududu
 dudu
ssdu
============
sss __
ss__/d__
 __/d__/d__
/d__/d__/d
\__/d__/d__/
/d__/d__/d
\__/d__/d__/
/d__/d__/d
\__/d__/d__/
 d__/d__/
ssd__/
============
sss __
ss__/s\__
 __/s\__/s\__
/s\__/s\__/s\
\__/s\__/s\__/
/s\__/s\__/s\
\__/s\__/s\__/
/s\__/s\__/s\
\__/s\__/s\__/
 s\__/s\__/
sss\__/
============
       __
    __/  \__
 __/  \__/  \__
/  \__/  \__/  \
\__/  \__/  \__/
/  \__/  \__/  \
\__/  \__/  \__/
/  \__/  \__/  \
\__/  \__/  \__/
   \__/  \__/
      \__/

```

# Answer
> 1 votes
# Javascript, ~~154~~ 151 bytes

```
b="\n",c="\t",d="/  \\",f="__",g="\\",h="/",a=f+d,j=a+a,i=d+j+b+g+j+f+h+b,k="   ";console.log(c+k+f+b+c+a+f+b+" "+j+f+b+i+i+i+k+g+a+f+h+b+c+"  "+g+f+h)

```

---
Tags: code-golf, ascii-art, kolmogorov-complexity, tiling, hexagonal-grid
---


title: Permutations of the Fifteen Puzzle

text:
# Question
Title: Permutations of the Fifteen Puzzle
# The Challenge

Consider the following diagram of the Fifteen Puzzle in its solved state:

```
_____________________
|    |    |    |    |
| 1  | 2  | 3  | 4  |
|____|____|____|____|
|    |    |    |    |
| 5  | 6  | 7  | 8  |
|____|____|____|____|
|    |    |    |    |
| 9  | 10 | 11 | 12 |
|____|____|____|____|
|    |    |    |    |
| 13 | 14 | 15 |    |
|____|____|____|____|

```

At every move, an excited puzzler has the opportunity to move one piece adjacent to the blank space into the blank space. For example, after `1` move, we have `2` possible scenarios (let `0` be a blank space):

```
1   2   3   4          1   2   3   4
5   6   7   8          5   6   7   8
9   10  11  12   and   9   10  11  0
13  14  0   15         13  14  15  12

```

After `2` moves, the puzzle has `5` different outcomes (Note that the two cases above are excluded, since they cannot be reached in 2 moves). One of these situations is the original solved state, and can be reached in two different ways.

Your task in this challenge is to produce the *number* of different outcomes that a certain number of moves can lead to. As input, take a number `N >= 0`, and output the number of **unique** situations that may appear after `N` moves.

# Rules

* This is code-golf. Shortest code wins!
* Standard loopholes are disallowed.
* Your code should be able to compute the case for `N = 10` within a few minutes. I will likely not test this rule unless an obvious abuse of time exists in an answer.

# Test Cases

(Results generated from summations of OEIS A089484 (As Geobits described in chat), automated by Martin Büttner's script. Thanks for all the help!)

```
0 moves: 1
1 moves: 2
2 moves: 5
3 moves: 12
4 moves: 29
5 moves: 66
6 moves: 136
7 moves: 278
8 moves: 582
9 moves: 1224
10 moves: 2530
11 moves: 5162
12 moves: 10338
13 moves: 20706
14 moves: 41159
15 moves: 81548
16 moves: 160159
17 moves: 313392
18 moves: 607501
19 moves: 1173136
20 moves: 2244884
21 moves: 4271406
22 moves: 8047295
23 moves: 15055186
24 moves: 27873613
25 moves: 51197332
26 moves: 93009236
27 moves: 167435388
28 moves: 297909255
29 moves: 524507316
30 moves: 911835416
31 moves: 1566529356

```

# Answer
# Pyth, 36 bytes

```
lu{smmXd,0@dk)fq1.a.DR4,Txd0UdGQ]U16

```

Demonstration. Test harness.

```
lu{smmXd,0@dk)fq1.a.DR4,Txd0UdGQ]U16

                 .a.DR4,Txd0            Find the Euclidean distance between the
                                        present location of 0 and a given location.
              fq1           Ud          Filter over all locations on that distance
                                        equaling 1.
     mXd,0@dk)                          Map each such location to the grid with 0
                                        and the value at that location swapped.
  {sm                         G         Map all unique grids possible after n-1
                                        steps to all unique grids after n steps.
 u                             Q]U16    Repeat <input> times, starting with the
                                        initial grid.
l                                       Print the length of the resulting set.

```
> 5 votes

# Answer
# CJam, ~~54~~ ~~52~~ ~~51~~ ~~50~~ ~~49~~ ~~47~~ 45 bytes

```
G,ari{{:S0#S{4md2$4md@-@@-mh1=},f{Se\}}%:|}*,

```

Try it online in the CJam interpreter (should take less than 10 seconds).

### How it works

```
G,a       e# Push R := [[0 1 ... 15]].
ri{       e# Do int(input()) times:
  {:S     e#   For each S in R:
    0#    e#     Push the index of 0 in S (I).
    S{    e#     Filter S; for each J in in S:
      4md e#       Push J/4 and J%4.
      2$  e#       Copy I.
      4md e#       Push I/4 and I%4.
      @-  e#       Compute (I%4)-(J%4).
      @@- e#       Compute (J%4)-(I%4).
      mh  e#       2-norm distance: a b -> sqrt(aa + bb)
      1=  e#       Check if the distance is 1.
    },    e#     Keep all values of J with distance 1 from I.
    f{    e#     For each J:
      S   e#       Push S.
      e\  e#       Swap S at indexes I and J.
    }     e#     This pushes an array of all valid modifications of S.
  }%      e#   Collect the results for all S in R in an array.
  :|      e#   Reduce the outmost array using set union (removes duplicates).
}*        e#

```
> 3 votes

# Answer
# Retina, ~~289~~ 276 bytes

```
^
,abcd%efgh%ijkl%mnox,
(`(,[^,]*)x([^,%])([^,y]*),
$0$1$2x$3y,
(,[^,]*)([^,%])x([^,y]*),
$0$1x$2$3y,
(,[^,]*)x([^,]{4})([^,])([^,y]*),
$0$1$3$2x$4y,
(,[^,]*)([^,])([^,]{4})x([^,y]*),
$0$1x$3$2$4y,
,.{19},(?=.*1)|,[^,]{20},(?=[^1]*$)|y|1$

+)`([^,]{19})(.*),\1,
$1$2
[^a]

a
1

```

Takes input and prints output in unary.

You can put each line in a single file or run the code as is with the `-s` flag. E.g.:

```
> echo -n 111|retina -s fifteen_puzzle
111111111111

```

The core of the method is that we keep track of all possible positions (without repetition) which can occur after exactly `k` steps. We start form `k = 0` and repeat the substitution steps (using the `(` and )` modifiers`) until we reach the input number of steps.

During this computation our string always has the form of

```
(,[puzzle_state]y?,)+1*

```

where `puzzle_state` is `abcd%efgh%ijkl%mnox` with some permutation of the letters. `x` stands for the empty place, the rest of the letters are the tiles. `%`'s are row delimiters.

`y` marks that the state is generated in the current step (`k`) so it shouldn't be used to generate other states in this step.

`1`'s mark the number of steps left.

The basic mechanic of the Retina code is that every match of an odd line is changed to the next (even) line.

The code with added explanation:

```
initialize string
^
,abcd%efgh%ijkl%mnox,

while string changes
(`

for every old (y-less) state concatenate a new state with moving the empty tile to r/l/d/u if possible
right
(,[^,]*)x([^,%])([^,y]*),
$0$1$2x$3y,
left
(,[^,]*)([^,%])x([^,y]*),
$0$1x$2$3y,
down
(,[^,]*)x([^,]{4})([^,])([^,y]*),
$0$1$3$2x$4y,
up
(,[^,]*)([^,])([^,]{4})x([^,y]*),
$0$1x$3$2$4y,

if we should have made this step (there are 1's left) remove old states
,.{19},(?=.*1)

if we should not have made this step (no more 1's left) remove new states
,[^,]{20},(?=[^1]*$)

remove y markers
y

remove one 1 (decrease remaining step count)
1$

remove duplicates until string changes (with + modifier)
+`([^,]{19})(.*),\1,
$1$2

end while
)`

remove non-a's, 1 a stays from each state
[^a]

change a's to 1's
a
1

```

10 bytes saved thanks to @MartinButtner.
> 3 votes

# Answer
# Python, ~~310~~ ~~253~~ ~~243~~ 229 bytes

Latest version with improvement suggested by @randomra:

```
s=set()
s.add(tuple(range(16)))
def e(a,b):s.add(t[:a]+(t[b],)+t[a+1:b]+(t[a],)+t[b+1:])
for k in range(input()):
 p,s=s,set()
 for t in p:j=t.index(0);j%4and e(j-1,j);j%4>2or e(j,j+1);j<4or e(j-4,j);j>11or e(j,j+4)
print len(s)

```

My own version, which was longer (243 bytes), but easier to read:

```
s=set()
s.add(tuple(range(16)))
def e(a,b):s.add(t[:a]+(t[b],)+t[a+1:b]+(t[a],)+t[b+1:])
for k in range(input()):
 p,s=s,set()
 for t in p:
  j=t.index(0)
  if j%4:e(j-1,j)
  if j%4<3:e(j,j+1)
  if j>3:e(j-4,j)
  if j<12:e(j,j+4)
print len(s)

```

Simple breadth first search, encoding the states as tuples, and storing them in a set to keep them unique.

Takes about 0.03 seconds on my laptop for N=10. Running time does increase substantially for larger numbers, for example about 12 seconds for N=20.
> 2 votes

# Answer
# Perl, 148

```
#!perl -p
$s{"abcd.efgh.ijkl.mno#"}=1;for(1..$_){$x=$_,map{$r{$_}=1if
s/($x)/$3$2$1/}keys%s for
qw!\w)(# #)(\w \w)(.{4})(# #)(.{4})(\w!;%s=%r;%r=()}$_=keys%s

```

Example:

```
$ time perl 15.pl <<<20
2244884
real    0m39.660s
user    0m38.822s
sys 0m0.336s

```
> 1 votes

---
Tags: code-golf, combinatorics, sequence, grid, permutations
---


# Question
Title: Compute the Resistance of a 4 Band Color Coded Resistor
Resistors commonly have color coded bands that are used to identify their resistance in Ohms. In this challenge we'll only consider the normal 4-band, tan, axial-lead resistors. We'll express them as:

```
xyzt

```

Where `x` is the first band for the first significant figure, `y` is the second band for the second significant figure, `z` the third band for the multiplier, and `t` is the fourth band for the tolerance.

Each of `xyzt` represents a letter that abbreviates the color of the band:

```
K = Black
N = Brown
R = Red
O = Orange
Y = Yellow
G = Green
B = Blue
V = Violet
A = Gray
W = White
g = Gold
s = Silver
_ = None

```

So, for example, `NKOg` is some particular resistor.

The resistance can be calculated with the help of this table:

As the table suggests:

* `x` and `y` can be any letters except `g`, `s`, and `_`.
* `z` can be anything except `_`.
* We'll restrict `t` to only be `g`, `s`, or `_`.

(Here's a handy resistance calculator that deals with exact same set of resistors we are.)

The resistance is `10 * x + y` times the `z` multiplier, to a tolerance of the `t` percentage.

> For example, to calculate the resistance of `NKOg`, we see that:
>
> 1. `N` means Brown for 1.
> 2. `K` means Black for 0.
> 3. `O` means Orange for 103.
> 4. `g` means Gold for ±5%.
>
> So the resistance is `(10*1 + 0)*10^3``10000 Ω ±5%`.

# Challenge

Write a program or function that takes in a 4 character string of the form `xyzt` and prints or returns the resistance in the form `[resistance] Ω ±[tolerance]%`.

* **The resistor may be "upside-down", i.e. in the reverse order `tzyx`. For example, both `NKOg` and `gOKN` should produce `10000 Ω ±5%`.**
* The resistance is always in plain ohms, never kilohms, megohms, etc.
* `Ω` may be replaced with `ohms`, e.g. `10000 ohms ±5%`.
* `±` may be replaced with `+/-`, e.g. `10000 Ω +/-5%`.
* Having trailing zeros to the right of a decimal point is fine. (e.g. `10000.0 Ω +/-5%`)
* You can assume input is always valid (`x` and `y` never `gs_`; `z` never `_`; `t` only `gs_`).
* All 10×10×12×3 = 3600 possible resistors (2×3600 possible inputs) need to be supported even if some color band combinations aren't produced in real life.

**The shortest code in bytes wins.**

# Examples

1. `gOKN``10000 ohms +/-5%`
2. `KKR_``0 Ω +/-20%`
3. `ggKN``1 ohms ±5%`
4. `ggGO``3.5 Ω ±5%`
5. `ssGO``0.350 Ω ±10%`
6. `GOOs``53000 ohms +/-10%`
7. `YAK_``48.0 ohms +/-20%`
8. `_WAV``78000000000 Ω ±20%`
9. `gBBB``66000000.000 ohms ±5%`
10. `_RYR``2400.00 ohms ±20%`

Iff you enjoy my challenges, consider checking out Block Building Bot Flocks!

# Answer
> 10 votes
# CJam, ~~59~~ ~~58~~ ~~56~~ 50 bytes

```
r_W%e>"sgKNROYGBVAW"f#2f-~A*+A@#*" Ω ±"@[KA5]='%

```

Try it online in the CJam interpreter.

# Answer
> 9 votes
# CJam, ~~53~~ ~~51~~ 50 bytes

```
" Ω ±"l_W%e<)iB%5*F-'%@"gKNROYGBVAW"f#:(2/'e*s~o

```

Try it online.

*(Thanks to @user23013 for a byte)*

---

I started out in Python, but

```
eval("%d%de%d"%tuple("gKNROYGBVAW".find(x)-1for x in L))

```

was too expensive...

# Answer
> 4 votes
## Python 3, ~~130~~ 114 bytes

```
def f(v):
 a,b,c,d=["_sgKNROYGBVAW".index(x)-3for x in v[::(1,-1)[v[0]in'sg_']]]
 return "%s Ω ±%s%%"%((10*a+b)*10**c,2.5*2**-d)

```

*edit:* @Sp3000 points out that the ordering can be better detected with `min(v,v[::-1])` rather than `v[::(1,-1)[v[0]in'sg_']]` (saving 10 bytes), not check the index of `_` and remove some unnecessary whitespace.

```
def f(v):a,b,c,d=["sgKNROYGBVAW".find(x)-2for x in min(v,v[::-1])];return"%s Ω ±%s%%"%((10*a+b)*10**c,2.5*2**-d)

```

# Answer
> 3 votes
# Perl, 93 bytes

```
#!perl -lp
ord>90and$_=reverse;s/./-3+index zsgKNROYGBVAW,$&/ge;$_=s/..\K/e/*$_." Ω ±"./.$/*5*$&."%"

```

# Answer
> 1 votes
# Haskell, ~~135 132~~ 130 bytes

```
r y|y<"["=p[k|j<-y,(c,k)<-zip"_ sgKNROYGBVAW"[-4..],c==j]
r y=r.reverse$y
p[a,b,c,d]=show((a*10+b)*10**c)++" Ω ±"++show(-5*d)++"%"

```

**Explanation:**

```
r y|y<"["=            If first letter of argument is a capital
p[..]                 Call p on the list created
[k|                   Make a list of all k
   j<-y               Draw character j from input
       ,(c,k)<-       With (c,k) being a pair from
               zip    A list of pairs of corresponding elements from the lists:
"_ sgKNROYGBVAW"       The space at 2nd position is to match '_' with -4, but 's' with -2
[-4..]                 An infinite list starting at -4
,c==j]                Only use element k if j equals the character c

r y=r.reverse$y       If first call fails, call again with reversed argument.

p[a,b,c,d]=           Assign the first four elements of the argument to a,b,c,d respectively.
show                  Turn (number) into string
10**c                 10 to the power of c
++                    Concatenate strings
-5*d                  This works for the tolerance because '_' makes d=-4

```

*Thanks to nimi, I shaved off another 2 bytes.*

---
Tags: code-golf, arithmetic
---


title: Order and Chaos and Codegolf

text:
# Question
Title: Order and Chaos and Codegolf
Order and Chaos is a variant of Tic-Tac-Toe played on a 6x6 board. What makes the game unique, however, is that both players can place either an X or an O! Each turn (starting with Order), a player places an X or O in any unoccupied square.
Winning is simple. Order wins if there are 5 Xs or Os (vertically, horizontally, or diagonally) in a row on the board. Chaos wins if the board is filled and there are no strings of 5 Xs or Os on the board. Your job? Well, since this is **Programming** Puzzles and Code Golf, you're going to program the game, and golf it.

### The Rules

* You must accept input as `x y t`, where `x` and `y` are coordinates, and `t` is the tile type (`X` or `O`). Coordinates start with `0 0` in the upper-left corner and increase up to `5 5` (the lower-right corner).
* You must accept `q` to quit, and print `INVALID` if the user enters invalid coordinates, tiles, any input not in the form of `x y t`, or tries to place a tile where there already is one. (The only exception is `q`, as this quits the program.)
* If Order wins, you will output `P1 WINS`. If Chaos wins, you will output `P2 WINS`.
* Order must go first.
* A blank space is represented by `.`.
* Tiles are `X` and `O` (uppercase). You do not have to accept lowercase, but uppercase is required.
* Your board must only consist of `.XO`.
* You're actually simulating both players playing the game, not being given a board and checking who wins. It accepts a move as input, then prints the board, accepts another move, and so on, until one player wins.

The starting board looks like this:

```
......
......
......
......
......
......

```

And after the first player (Order) inputs `1 2 X`, it should look like this:

```
......
......
.X....
......
......
......

```

Likewise, when the next player (Chaos) inputs `3 3 O`, it will look like this:

```
......
......
.X....
...O..
......
......

```

And this continues until one player wins.

As always, Standard loopholes which take the fun out of everything are forbidden.

The winner is the one with the shortest code on June 15, 00:00 UTC (about one month from when this challenge was posted.)

# Answer
# PHP, 316

Here is my submission. It has to be executed by php in the command line.

Note that this code produces notices because of some shortcuts I made. Let me know if this is ok. I can fix it by adding a few more characters. I checked this page and the top answer says to assume that error reporting is turned off if there is no mention about it.

```
<?for(;$i++<6;)$b.='......|';while(($a=trim(fgets(STDIN)))!='q'){preg_match('/^([0-5]) ([0-5]) ([XO])$/',$a,$d)&($b[$c=$d[2]*7+$d[1]]=='.')?$b[$c]=$d[3]:print"INVALID\n";echo str_replace("|","\n",$b); foreach([0,5,6,7]as$e)preg_match('/(X|O)(.{'.$e.'}\1){4}/',$b)-1?:die("P1 Wins");strstr($b,'.')?'':die("P2 Wins");}

```

And here is the un-golfed version of the code:

```
<?php
error_reporting(E_ALL & ~E_NOTICE);

for(;$i++<6;)$b.='......|';
while(($a=trim(fgets(STDIN)))!='q'){

    #Validate and assign
    preg_match('/^([0-5]) ([0-5]) ([XO])$/',$a,$d)&($b[$c=$d[2]*7+$d[1]]=='.')?$b[$c]=$d[3]:print"INVALID\n";

    #Output
    echo str_replace("|","\n",$b);

    #Check if Order wins
    foreach([0,5,6,7]as$e) {
        preg_match('/(X|O)(.{'.$e.'}\1){4}/',$b)-1?:die("P1 Wins");
    }

    #Check if Chaos wins
    strstr($b,'.')?'':die("P2 Wins");
}

```
> 1 votes

# Answer
# JavaScript, 360

**Edit** Modified interactive game, should run even in MSIE

As requested, text based game, input via popup, output in console (so to have a monospaced font).

Quit game with 'q' or clicking 'cancel' at prompt.

Not using ES5 features, it should run on any moder browser (where you can have a JS console panel)

```
b='\n......'.repeat(6).split('');
for(h=t=0;!h&t<36;)
{
  i=prompt();
  if(i=='q')i=null;
  i=i.match(/([0-5]) ([0-5]) ([XO])/);
  m='INVALID';
  if(b[p=i?i[2]*7-~i[1]:0]=='.')
  {
    ++t;
    b[p]=i[3];
    m=b.join('');
    for(x=z='',c=0;c++<6;)
      for(x+='_',z+='_',r=0;r<6;r++)
        x+=b[c+r*7],z+=b[c<4?c-1+r*8:c+1+r*6];
    h=(/X{5}|O{5}/.test(b.join('')+x+z))
  }
  console.log(m);
}
console.log("P"+(2-h)+" WINS")
```

**Now, some more fun** Interactive and graphic version, run snippet to play.

```
function start() {
  b=Array(7).join('\n......').split('');
  t=0;
  $('#O').text('');
  $('table')[0].className='';
  show();
  $('th').eq(1).html('Left-click: O<br>Right-click: X');
  $('#B')
  .off('mouseup')
  .on('mouseup','td.F',function(ev){
    var x,y, p=~~this.id.slice(1)
    x=p%7-1
    y=p/7|0
    b[p]=ev.which > 1 ?'X':'O';
    ++t
    for(x=z='',c=0;c++<6;)
      for(x+='_',z+='_',r=0;r<6;r++)
        x+=b[c+r*7],z+=b[c<4?c-1+r*8:c+1+r*6];
    show()
    if (/X{5}|O{5}/.test(b.join('')+x+z))
      end(1)
    else if(t==6*6)
      end(2)
    return false
  })
}

function end(w) {
  var n=['Order','Chaos'][w-1]
  $('th').eq(0).text('P'+w+' '+n+' Wins')
  $('th').eq(1).text('Click to play again')

  $('table')[0].className=$('tr')[0].className =n[0];
  $('#B').off('mouseup').on('mouseup', start)
}
function show() {
  var w,p
  p=t&1
  $('tr')[0].className=$('#B')[0].className='OC'[p];
  w=b.map(function(c,i){
    return c>' '?'<td class='+(c=='.'?'F':'X')+' id=C'+i+'>'+c+'</td>':'</tr><tr>'
  }).join('');
  $('th').eq(0).text('Playing: '+['Order','Chaos'][p]);
  $('#B').html('<tr>' + w +'</tr>');
}

start()
```

```
th {
  font-size: 12px;
}
.C th { color: #807; }
.O th { color: #047; }
.C td.F:hover { background: #f0e; }
.O td.F:hover { background: #0fe; }
table.C td { background: #f0e; }
table.O td { background: #0fe; }

td {
  font-family: monospace;
  font-size: 12px;
  width: 1.2em;
  height: 1em;
  text-align: center;
}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>
<table>
  <tr><th colspan=6></th></tr>
  <tbody id=B></tbody>
  <tr><th colspan=6></th></tr>
</table>
<p id=O></p>
```
> 4 votes

# Answer
# Octave, 453

```
format plus 'XO.'
disp(F=zeros(6))
r=@()fread(0,1);R=@()r()-47;q=@(m)printf(m)&&quit;e=@()q("INVALID");l=@(n)n<1||n>6&&e();s=@()r()==32||e();w="P1 WINS";f=@(v)abs(sum(v))==22.5&&q(w);g=@(m)any(abs(sum(m))==22.5)&&q(w);d=@diag;while 1
i=R();i==66&&quit;l(i);s();l(j=R());s();F(j,i)&&e();abs(v=R()-36.5)==4.5||e();F(j,i)=v;disp(F)
r();f(d(F,-1));f(d(F,0)(2:6));f(d(F,0)(1:5));f(d(F,1));g(F(1:5,:));g(F(2:6,:));g(F(:,1:5)');g(F(:,2:6)');F&&q("P2 WINS");end

```

The implementation is quite straightforward, the only real “trick” to use `format plus` to take care of printing. Here is a commented version:

```
format plus 'XO.'               # this is where the magic happens

## initialize and print empty board
disp(F=zeros(6))

## shortcuts
r=@()fread(0,1);
R=@()r()-47;
q=@(m)printf(m)&&quit;
e=@()q("INVALID");
l=@(n)n<1||n>6&&e();
s=@()r()==32||e();
w="P1 WINS";
f=@(v)abs(sum(v))==22.5&&q(w);
g=@(m)any(abs(sum(m))==22.5)&&q(w);
d=@diag;

while 1
  i=R();                        # read index 1
  i==66&&quit;                  # ‘q’?
  l(i);                         # check bounds
  s();                          # read and check space
  l(j=R());                     # read and check index 2
  s();                          # read and check space
  F(j,i)&&e();                  # square already filled?
  abs(v=R()-36.5)==4.5||e();    # valid mark?
  F(j,i)=v;                     # assign …
  disp(F)                       # and print board
  r();                          # read off newline

  ## check diagonals
  f(d(F,-1));
  f(d(F,0)(2:6));
  f(d(F,0)(1:5));
  f(d(F,1));

  ## check rows
  g(F(1:5,:));
  g(F(2:6,:));

  ## check columns
  g(F(:,1:5)');
  g(F(:,2:6)');

  ## check chaos
  F&&q("P2 WINS");
end

```

Because of the requirement to check input syntax and validity, the code uses `fread()` to read one character at a time.

I took care to output the board and messages in a tidy manner. If some extra output is acceptable, I could shave off a couple of bytes. For example, using automatic printing (no `disp(F)`), the board would be shown as

```
F =

......
......
......
......
......
......

```

Also, I interpreted that each move is given on a separate line.

---

Sample interaction (the `-q` switch is just to suppress Octave's header):

```
$ octave -q order_chaos.m
......
......
......
......
......
......
3 3 X
......
......
......
...X..
......
......
2 3 O
......
......
......
..OX..
......
......
3 3 O
INVALID

```

The invalid move caused the program to exit (not sure if that was intended).
> 1 votes

# Answer
# Java, 565 chars D:

```
public class M{public static void main(String[]r){int[]p=new int[36];int u=0;for(;;){String l=new java.util.Scanner(System.in).nextLine();if(l == "q")break;int a=l.charAt(0)-'0'+(l.charAt(2)-'0')*6,i=p[a]==0?1:0;if(i>0)p[a]=l.charAt(4);u+=i;r(i==0?"INVALID\n":"");if(u==36){r("P2 WINS");break;}for(int x=0;x<6;x++)for(int y=0;y<6;y++)for(int d=0;d<3;d++)try{int e=1,c=p[x+y*6],z=x,h=y;if(c=='X'||c=='Y'){for(;e<6;e++){if(d%2==0)z++;if(d>0)h++;if(p[z+h*6]!=c)break;}if(e==5){r("P1 WINS");return;}}}catch(Exception e){}}}static void r(Object o){System.out.print(o);}}

```

This is probably the longest code-golf ever. I'm really not good at this.
> 1 votes

---
Tags: code-golf, board-game
---