title: The Great Wumpus Hunt

text:
# Question
Title: The Great Wumpus Hunt
## COMPLETE

Wumpus season has ended, and with, the lives of many a vicious Wumpus and brave Hunter. As well as some cowardly, immoral and downright stupid Hunters. But at the end of the day, NascarHunter by Dr Heckle came away with the most loot and glory. We salute you, oh brave... driver?

It's open season on Wumpuses, and hunters from around the world are flocking to the Wumpus Caves to try to get rich of off valuable Wumpus Pelts.

# The Game

Based on the classic Hunt the Wumpus game, with a few variations.

## The Map

A dodecahedron. There are 20 rooms, each connected to 3 other room, making basically 3 rings with bridges in between.

## The Wumpus

The Wumpus is a mystical beast. None are sure what it looks like, but all agree that it is ferocious. The Wumpus lives in the caves, and likes to eat dead things. If there is a corpse in a cave next to the Wumpus, he will move there and eat it. If the Wumpus happens to move into a cave containing hunters, he will kill and eat them as well. If the Wumpus hears an arrow near him, he will panic and run into a random room.

**Optional traits**: These are currently included to make the game more interesting, but can be removed at popular request if they add too much randomness.

Enraged Wumpus: If the Wumpus is shot, he has a 20% of surviving and rampaging for 3 days. When rampaging, he will randomly move twice a day, but still be attracted to corpses. After 3 days, he will die. A second arrow shot will also kill the Wumpus.

Wandering Wumpus: Each day, if nothing else triggers the Wumpus, he has a 25% chance of moving.

## The Hunters

Four hunters can enter the caves at a time. The caves are dark, so the hunters cannot see, but they can use their other senses. Hunters can smell the Wumpus in an adjacent room, smell a corpse in an adjacent room, hear other hunters moving in adjacent rooms, and hear if an arrow is shot into an adjacent room.

Hunters have two actions: Shoot or move. A hunter can shoot an arrow into an adjacent room or his own room, and move similarly.

## Gameplay

In each round, hunters will first take note of their surroundings, and then make one move. Movement occurs before arrows, so if an arrow is shot into a room that a hunter is moving out of, the hunter will survive. After all hunter moves have been made, the arrows are evaluated. If a single occupant and arrow are in the same room, the occupant will be shot and die. If two or more occupants share a room, one will randomly be hit and die. Note: Corpses are occupants, so a dead body may serve as a partial shield.

After all hunter moves, the Wumpus will respond. If a hunter has moved into the room with the Wumpus, the Wumpus will eat him/her. If the Wumpus moves, it will also eat the occupants of the new room.

After 100 days, if the hunters have not killed the Wumpus, or fallen victim, they will die of starvation within the caves.

# The Code

All source code can be found here. All submissions should be in Java, unless somebody wants to write me a stdIn/stdOut adaptor ;)

Bots should extend the Hunter class. To name your Hunter, add a constructor with no parameters that sets the name field. T o respond, override the getResponse function. In this function, each turn, you will be passed an array of 5 booleans that tells you about your surroundings.

status 0 = "You smell a wumpus"

status 1 = "You hear another hunter"

status 2 = "You smell a corpse"

status 3 = "You hear an arrow clatter"

status 4 = "You feel another hunter in the same room as you"

The Hunter class has 2 slots: nextMove and nextDirection, that use the enums Move and Direction respectively. Move can either be MOVE or SHOOT, direection can be LEFT, RIGHT, BACK, or HERE. Directions are consistent, meaning back will always return you to the previous room you were in, and if entering from the same room, LEFT and RIGHT will always be the same. However, if you enter from a different direction, LEFT and RIGHT will take you to different places.

Feel free to implement your own methods as well. Memory is persistent throughout the whole tournament, meaning your hunter will only be constructed once. However, at the start of each round, the newGame() method is called to let your hunter know a new game has started.

## Scoring

Four hunters compete at a time. If killed, the Wumpus pelt is worth 60 points, split evenly among all surviving hunters. Full round robin style, so each combination of 4 hunters will play together.

5 sample Hunters are included: 4 with very basic functionality, and one that allows user input to play, for testing purposes.

If you have any suggestions/requests, please let me know!

# The End is in sight!

The worlds Wumpus population is being hunted at an alarming rate. The Protect Our Wumpuses Act is expected to be passed on Wednesday, June 17th. After this date, no more hunters will be allowed in the caves, and a winner will be chosen.

# Scoreboard

*Note :* My apologies, there was a bug in the code that could cause Hunters to stay dead through multiple games. Having fixed it, it does not change the overall rankings very much, but does largely change the stats.

Scores are in, running each set of hunter in 1000 games each. NascarHunter and FullCoverageHunter lead the pack, and although the addition of AntiHunter has given the Wumpuses a 2% survival boost, they are still shaking in their suckered feet at the 32% survival rate of their kind. Arrows from fellow hunters are more than ever the biggest threat in the caves.

```
1. NascarHunter : 16557175 (17.08)
2. FullCoverageHunter : 15195545 (15.68)
3. Trig : 14459385 (14.92)
4. Idomeneus : 13428570 (13.85)
5. Eats Shoots and Leaves : 12763945 (13.17)
6. WalkingIdiot : 12329610 (12.72)
7. NealHunter : 12287140 (12.68)
8. Unnamed : 11013720 (11.36)
9. MonsterHunter : 10686035 (11.02)
10. Pacer : 9187000 (9.48)
11. Badger : 9042570 (9.33)
12. Stay : 8721210 (9.0)
13. Emo Wumpus : 7831050 (8.08)
14. Paranoid : 7722965 (7.97)
15. Huddle : 7465420 (7.7)
16. ElmerFudd : 7245995 (7.47)
17. Laomedon : 6963845 (7.18)
18. Pacifist : 6944960 (7.16)
19. ScaredyCat : 6937370 (7.15)
20. Wumpus : 114170 (0.11)

Total rounds: 4845000
Humans killed by arrows: 5289674 (1.09)
Humans dead by starvation: 1046024 (0.21)
Humans killed by wumpus: 1887634 (0.38)
Wumpus victories: 1563372 (0.32)

```

# Answer
## NascarHunter

Not much logic to it. Its rules are simple: turn left, scorched earth, repeat. And, hey, he might get lucky!

**8 June edit:**

Added in additional logic to Nascar to account of adjacency to a Wumpus relative to its last move. Consider it a pit stop, to stay in theme. If it sense a Wumpus after shooting down a hallway, then it must have arrived in one of the other two adjacent rooms, since it would've died to the shot the hunter just took. It effectively give either the Wumpus 2 turns to live if it doesn't move again, or Nascar 1 turn to live if he's standing on a corpse. Also accounts for a third option if it's the first turn, but just the once. I'll port to to FCH eventually, busy busy.

```
package Hunters;

import Mechanics.*;

public class NascarHunter extends Hunter {

    private int state;
    private boolean shootHall;
    private boolean newGame;

    public NascarHunter(){

        name = "NascarHunter";
        state = 0;
        shootHall = true;
        newGame = true;

    }

    public void newGame(){

        state = 0;
        newGame = true;

    }

    public void getResponse(boolean[] status){

        // Wumpus about - stand and deliver
        if( status[0] ){

            nextMove = Move.SHOOT;

            switch( state ){

            case 0: // Must be in either Right or Back
                if(newGame){

                    // try Left if this is the first turn, just in case
                    nextDirection = Direction.LEFT;
                    newGame = false;

                }
                else if(shootHall) nextDirection = Direction.BACK;
                else               nextDirection = Direction.RIGHT;
                shootHall = !shootHall;
                break;
            case 2: // Must be in either Left or Back
                if(newGame){

                    // try Right if this is the first turn, just in case
                    nextDirection = Direction.RIGHT;
                    newGame = false;

                }
                else if(shootHall) nextDirection = Direction.BACK;
                else               nextDirection = Direction.LEFT;
                shootHall = !shootHall;
                break;
            default: // Must be in either Left or Right
                if(newGame){

                    // try Back if this is the first turn, just in case
                    nextDirection = Direction.BACK;
                    newGame = false;

                }
                else if(shootHall) nextDirection = Direction.RIGHT;
                else               nextDirection = Direction.LEFT;
                shootHall = !shootHall;
                break;

            }

        }else{

            // disregard state, shove out and light 'em up!
            switch( state ){

            case 0: // move out
                nextMove = Move.MOVE;
                nextDirection = Direction.LEFT;
                state++;
                break;
            case 1: // shoot right
                nextMove = Move.SHOOT;
                nextDirection = Direction.RIGHT;
                state++;
                break;
            case 2: // shoot behind
                nextMove = Move.SHOOT;
                nextDirection = Direction.BACK;
                state++;
                break;
            case 3: // shoot left
                nextMove = Move.SHOOT;
                nextDirection = Direction.LEFT;
                state = 0;
                break;

            }

        }

    }

}

```

## FullCoverageHunter

Follows the same credo of the NascarHunter, but alternates his pathing, which is guaranteed to form a loop 10 unique rooms long. Since every room is unique, and we fire at every direction per room, all rooms get fired into. This is true for any starting room (postulated by my buddy Neal, thanks Neal!). Dodecahedra are pretty cool like that!

I'd like to point out that this is is different than our friend, the MonsterHunter, as he doesn't try any trickery or any real "tactics." The strength of this is the fact that every room gets fired into, again: the brute force solution. This has a theoretical leg up on the NascarHunter, since Nascar will only hit 10 of the 20 rooms, covering only half the area.

**11 June edit:**

Added in Wumpus detection logic pattern from NascarHunter. Should objectively improve score.

```
package Hunters;

import Mechanics.*;

public class FullCoverageHunter extends Hunter {

    private int state;
    private boolean headLeft;
    private boolean shootHall;
    private boolean newGame;

    public FullCoverageHunter(){

        name = "FullCoverageHunter";
        state = 0;
        headLeft = false;
        shootHall = true;

    }

    public void newGame() {
        state = 0;
        headLeft = false;
        newGame = true;
    }

    public void getResponse(boolean[] status){

        // Wumpus about - stand and deliver
        if( status[0] ){

            nextMove = Move.SHOOT;

            switch( state ){

            case 0: // Must be in either Right or Back
                if(newGame){

                    // try Left if this is the first turn, just in case
                    nextDirection = Direction.LEFT;
                    newGame = false;

                }
                else if(shootHall) nextDirection = Direction.BACK;
                else               nextDirection = Direction.RIGHT;
                shootHall = !shootHall;
                break;
            case 2: // Must be in either Left or Back
                if(newGame){

                    // try Right if this is the first turn, just in case
                    nextDirection = Direction.RIGHT;
                    newGame = false;

                }
                else if(shootHall) nextDirection = Direction.BACK;
                else               nextDirection = Direction.LEFT;
                shootHall = !shootHall;
                break;
            default: // Must be in either Left or Right
                if(newGame){

                    // try Back if this is the first turn, just in case
                    nextDirection = Direction.BACK;
                    newGame = false;

                }
                else if(shootHall) nextDirection = Direction.RIGHT;
                else               nextDirection = Direction.LEFT;
                shootHall = !shootHall;
                break;

            }

        }else{

            // disregard state, shove out (in an alternating fashion!) and light 'em up!
            switch( state ){

            case 0: // move out, change alternation state
                nextMove = Move.MOVE;
                if(headLeft) nextDirection = Direction.LEFT;
                else         nextDirection = Direction.RIGHT;
                state++;
                headLeft = !headLeft;
                break;
            case 1: // shoot into non-exit path
                nextMove = Move.SHOOT;
                if(headLeft) nextDirection = Direction.RIGHT;
                else         nextDirection = Direction.LEFT;
                state++;
                break;
            case 2: // shoot behind
                nextMove = Move.SHOOT;
                nextDirection = Direction.BACK;
                state++;
                break;
            default: // shoot into next room,
                nextMove = Move.SHOOT;
                if(headLeft) nextDirection = Direction.LEFT;
                else         nextDirection = Direction.RIGHT;
                state = 0;
                break;

            }

        }

    }

}

```

Let me know if there're any errors, package didn't play nice with my IDE :(
> 11 votes

# Answer
# Badger

He doesn't like visitors.

```
package Hunters;

import Mechanics.*;

public class Badger extends Hunter {

    public Badger(){
        name = "Badger";
    }

    @Override
    public void getResponse(boolean[] status){
        nextMove = Move.SHOOT;
        nextDirection = Direction.values()[((int) (Math.random() * 3))];
    }
}

```
> 7 votes

# Answer
# Elmer Fudd

"Shhh. Be vewy vewy quiet, I'm hunting wumpus"

Elmer is fixated on the prey and ignores everything except corpses and the Wumpus. He tries to find a corpse then backs off and starts shooting. If he smells a Wumpus, he will back off and if he still smells him he will shoot.

My apologies to all the java programmers, this is probably extremely ugly, full of syntax errors and I have probably messed up my logic.

```
package Hunters;

import Mechanics.*;

public class ElmerFudd extends Hunter {

    private state int;
    private previousDir int;

    public ElmerFudd(){
        name = "ElmerFudd";
    }

    public void newGame() {
        state=0;
        previousDir = Direction.LEFT;
    }

    public void getResponse(boolean[] status){

        nextMove = Move.MOVE;
        switch (previousDir) {
            case Direction.LEFT:
                nextDirection = Direction.RIGHT;
                break;
            case Direction.RIGHT:
                nextDirection = Direction.LEFT;
                break;
        }

        if(status[2]&&state==0) {
            state = 1;
            return;
        }

        if(state==1){
            if(status[2]){
                state=2;
            };
            nextDirection = Direction.BACK;
            return;
        }

        if(state==2){
            nextMove = Move.SHOOT;
            nextDirection = Direction.BACK;
            return;
        }

        if(state==3&&status[0])
            nextMove = Move.SHOOT;
            nextDirection = Direction.BACK;
            return;
        }

        if(state==3) {
            state = 0;
        }

        if(status[0]){
            state=3;
            nextDirection = Direction.BACK;
        }

    }
}

```

# Pacifist

This guy is morally against any sort of blood sport and wondering how he turned up in this situation at all. He will run away from any sort of contact and never take a shot.

```
package Hunters;

import Mechanics.*;

public class Pacifist extends Hunter {

    public Pacifist(){
        name = "Pacifist";
    }

    public void getResponse(boolean[] status){
        nextMove = Move.MOVE;
        if(status[0]||status[1]||status[2]||status[3]||status[4]){
            nextDirection = Direction.values()[((int) (Math.random() * 3))];
            return;
        }
        nextDirection = Direction.HERE;
    }
}

```
> 6 votes

# Answer
# MonsterHunter

We are hunting a monster and we are 4... It reminds me of my favorite game ! This hunter will walk most of the map by moving left-right alternatively, and if the Wumpus is near, he will lure him by going backward to be able to determine precisely were it is.

I could get rid of lastDirection, but I keep for semantics and readability :). Actually, it dies quite a lot, but the controller often put 2/3 hunter in the same room at the start, and often with the Wumpus near (can also be in the same room)... so insta death ^^'.

```
package Hunters;

import Mechanics.*;

public class MonsterHunter extends Hunter
{
    private Direction lastDirection=Direction.HERE;
    private boolean[] lastStatus=new boolean[5];
    private int   shooted=0;
    private boolean   walkMode=true;
    private int         turnStayed=0;

    public MonsterHunter(){
        super();
        name = "MonsterHunter";
    }

    @Override
    public void getResponse(boolean[] status)
    {
        if(status[0])
        {
            if(!lastStatus[0]||shooted==0)
            {
                nextDirection=(walkMode)?Direction.RIGHT:Direction.LEFT;;
                nextMove=Move.SHOOT;
            }
            else if(lastStatus[0]&&shooted==1)
            {
                nextDirection=Direction.BACK;
                nextMove=Move.MOVE;
            }
            else
            {
                nextDirection=Direction.BACK;
                nextMove=Move.SHOOT;
            }
        }

        else if(status[2])
        {
            nextMove=Move.MOVE;
            if(Math.random()*6<turnStayed)
            {
                nextDirection=Direction.HERE;
                turnStayed++;
            }
            else
                nextDirection=(walkMode)?Direction.RIGHT:Direction.LEFT;
        }
        else
        {
            nextMove=(!status[1]&&Math.random()<0.5)?Move.MOVE:Move.SHOOT;
            nextDirection=(walkMode)?Direction.RIGHT:Direction.LEFT;
        }

        if(nextMove==Move.MOVE)
        {
            if(shooted>0)
                walkMode=walkMode^(shooted>0);
            if(lastStatus[0]&&shooted==1)
                shooted++;
            else
                shooted=0;
            lastDirection=nextDirection;
        }
        else
            shooted++;
        for(int i=0;i<status.length;i++)
            lastStatus[i]=status[i];
    }
}

```
> 5 votes

# Answer
# PacingHunter

Back and forth, between to rooms. if it smells a Wumpus or hears a player it shoots left then right. if a Wumpus is next to him to start with than he shoots the room he will move to.

```
package Hunters;

import Mechanics.Direction;
import Mechanics.Hunter;
import Mechanics.Move;

public class PacingHunter extends Hunter {

    int state = 0;//Pacing
    int turn = 0;

    public PacingHunter() {
        name = "Pacer";
    }

    public void newGame() {
        turn =  0;
        state = 0;
    }

    public void getResponse(boolean[] status){
        turn += 1;
        if(state == 0 && status[0] && turn == 1){
            nextMove = Move.SHOOT;
            nextDirection = Direction.BACK;
            return;
        }
        if(state == 0 &&(status[0] || status[1])){
            nextMove = Move.SHOOT;
            nextDirection = Direction.LEFT;
            state = 1;
            return;
        }
        if(state == 1 && (status[0] || status[1])){
            nextMove = Move.SHOOT;
            nextDirection = Direction.RIGHT;
            state = 0;
            return;
        }
        if(status[1] && state == 0){
            nextMove = Move.SHOOT;
            nextDirection = Direction.BACK;
            state = 0;
            return;

    }
    nextMove = Move.MOVE;
    nextDirection = Direction.BACK;
}

```

}
> 4 votes

# Answer
# ScaredyCat

ScaredyCat is scared of everything. If it smells a wumpus or a corpse or hears an arrow or a hunter, it runs to a random direction. Otherwise, it simply keeps shooting arrows in random directions.

```
package Hunters;

import Mechanics.*;

public class ScaredyCat extends Hunter {

    public ScaredyCat(){
        name = "ScaredyCat";
    }

    @Override
    public void getResponse(boolean[] status){

        for(int i=0; i<status.length; i++)
            if(status[i])
            {
                nextMove = Move.MOVE;
                nextDirection = Direction.values()[((int) (Math.random() * 3))];
                return;
            }

        nextMove = Move.SHOOT;
        nextDirection = Direction.values()[((int) (Math.random() * 3))];
    }
}

```
> 4 votes

# Answer
# Eats Shoots and Leaves

Unlike the Panda of grammar book fame, this hunter doesn't actually eat anything, but we either shoot if the Wumpus is about or we leave on a trail that should hopefully keep us from walking in circles.

```
package Hunters;

import java.util.Random;

import Mechanics.Hunter;
import Mechanics.Move;
import Mechanics.Direction;
import Mechanics.Room;

public class EatsShootsAndLeaves extends Hunter {

    private static Direction [] allDirections = { Direction.LEFT, Direction.RIGHT, Direction.BACK, Direction.HERE };
    private static Direction [] movePath = { Direction.LEFT, Direction.RIGHT, Direction.LEFT, Direction.BACK, Direction.RIGHT, Direction.BACK };

    private static int numGames = 0;
    private static int totalLife = 0;

    private static class RoomInfo  {

        public boolean hasWumpus = false;
        public boolean hasLocalHunter = false;
        public boolean hasNeighborHunter = false;
        public boolean hasCorpse = false;
        public boolean hasArrow = false;
        public RoomInfo(Room r) {
            boolean [] status = r.getInfo();
            hasWumpus = status[0];
            hasNeighborHunter = status[1];
            hasCorpse = status[2];
            hasArrow = status[3];
            hasLocalHunter = status[4];
        }

        public String toString() {
            return new String("Status: "
                              + (hasWumpus ? "Wumpus " : "")
                              + (hasNeighborHunter ? "Close Hunter " : "")
                              + (hasCorpse ? "Corpse " : "")
                              + (hasArrow ? "Arrow " : "")
                              + (hasLocalHunter ? "Local Hunter " : ""));
        }
    }

    int turnsAlive = 0;
    int shots = 0, moves = 0;

    public EatsShootsAndLeaves(){
        name = "Eats Shoots and Leaves";
    }

    public void newGame() {

        totalLife += turnsAlive;
        numGames++;

        turnsAlive = shots = moves = 0;
    }

    public void getResponse(boolean[] status){

        turnsAlive++;

        RoomInfo info = new RoomInfo(this.getRoom());
        if (info.hasNeighborHunter || info.hasWumpus) {
            nextMove = Move.SHOOT;
            nextDirection = allDirections[shots++ % 3];
        } else {
            nextMove = Move.MOVE;
            nextDirection = movePath[moves++ % movePath.length];
        }
    }
}

```
> 4 votes

# Answer
# Idomeneus

Idomeneus is quite simple- if the Wumpus or another hunter is nearby, he fire sarrows everywhere and prays that the goddess of hunting is on his side. If he's near a corpse he lies in wait for the Wumpus. He doesn't like other hunters and will run away if they start firing arrows near him, or if they are in the same room as him. Finally if he's feeling bored he randomly paces the eternal corridors.

```
package Hunters;
import Mechanics.Direction;
import Mechanics.Hunter;
import Mechanics.Move;
import java.util.Random;

public class Idomeneus extends Hunter
{
    int direction;
    Random r;
    public Idomeneus()
    {
        super();
        name = "Idomeneus";
        direction = 0;
        r = new Random();
    }

    @Override
    public void getResponse(boolean[] status){
        boolean wumpusNear = status[0];
        boolean hunterNear = status[1];
        boolean corpseNear = status[2];
        boolean arrowNear = status[3];
        boolean hunterHere = status[4];
        direction++;

        if(wumpusNear)
        {
            //ATTACK!!!
            nextMove = Move.SHOOT;
            nextDirection = Direction.values()[direction%3];
        }
        else if(hunterHere || arrowNear)
        {
            //Run away
            nextMove = Move.MOVE;
            nextDirection = Direction.values()[r.nextInt(3)];
        }
        else if(hunterNear)
        {
            //ATTACK!!!
            nextMove = Move.SHOOT;
            nextDirection = Direction.values()[direction%3];
        }
        else if(corpseNear)
        {
            //Stay and wait...
            nextMove = Move.MOVE;
            nextDirection = Direction.HERE;
        }
        else
        {
            //wander around
            nextMove = Move.MOVE;
            nextDirection = Direction.values()[r.nextInt(3)];
        }

    }

    public void newGame(){}

}

```
> 3 votes

# Answer
# Emo Wumpus (Hunter)

Emo Wumpuses (related to Emo Wolves which sometimes use guns and fly planes) hate everything (especially Java). They make no distinction between Hunters and Wumpuses, and try to shoot them all the same. They also hate Nascar drivers, and will always shoot right. If no one is around to shoot, they move right, but will only do this thirteen times in a row before they get even more depressed about being alone and try to shoot themselves (thirteen is an unlucky number). On turn 99, if they are still alive, they will attempt to shoot themselves because starvation is such a lame way to die.

Wumpuses are larger (and heavier) than Wolves, but this one has still starved itself to 424 bytes (as opposed to the hefty 2.72 kb of NascarHunter).

```
package Hunters;import Mechanics.*;public class EmoWumpus extends Hunter{private int c, t;public EmoWumpus(){name="Emo Wumpus";this.c=0;this.t=0;}public void newGame(){this.c=0;this.t=0;}public void getResponse(boolean[] status){nextMove=Move.SHOOT;if(c<13 && t<100){if(status[0]||status[1]){nextDirection=Direction.RIGHT;}else{nextMove=Move.MOVE;nextDirection=Direction.RIGHT;c++;}}else{nextDirection=Direction.HERE;}t++;}}

```

Why not just commit suicide in the first place? Emo Wumpuses believe that the one act of good that can do is end the suffering of others before killing themselves. Therefore, they will kill all that they can before it is their time to die.

# Wumpus? (Anti-Hunter)

Um, What is a Wumpus doing on the hunters roster? This guy got super pissed that humans were killing his kin, so he decided to dress up as one of them and join in on the hunt. His main goal is to just kill hunters. He tries to hide near corpses, which will give him a chance at a shield from the hunters. If no hunters are nearby, he will move in a direction until hunters are detected, in which case he will try to kill them before moving in the other direction.

Unfortunately, most Wumpuses are stupid, and are still going to try to kill him. Regardless, he considers his sacrifices necessary for the good of Wumpuses everywhere.

```
package Hunters;

import Mechanics.*;

public class AntiHunter extends Hunter {

private boolean left;

public AntiHunter() {
    name = "Wumpus";
    this.left = true;
}

public void newGame() {
    this.left = true;
}

public void getResponse(boolean[] status) {
    if(status[4]) {
        nextMove = Move.SHOOT;
        nextDirection = Direction.HERE;
    }
    else if(status[2] || status[1]) {
        nextMove = Move.SHOOT;
        if(this.left) {
            this.left = false;
            nextDirection = Direction.LEFT;
        }
        else {
            this.left = true;
            nextDirection = Direction.RIGHT;
        }
    }
    else {
        nextMove = Move.MOVE;
        if(this.left)
            nextDirection = Direction.LEFT;
        else
            nextDirection = Direction.RIGHT;
    }
}

```

}
> 3 votes

# Answer
# Laomedon

Laomedon wanders aimlessly trying to find a corpse. Once he's found one and works out where it is he stays in the same place next to the corpse. When he smells the Wumpus he fires arrows into the Corpse's room.

```
package Hunters;
import Mechanics.Direction;
import Mechanics.Hunter;
import Mechanics.Move;
public class Laomedon extends Hunter {
    private enum status
    {
        START,
        SEARCHED_LEFT,
        SEARCHED_RIGHT,
        INITIAL_CORPSE_LEFT,
        INITIAL_CORPSE_RIGHT,
        SMELT_CORPSE,
        CORPSE_BEHIND,
        CORPSE_LEFT
    }

    status myState;
    public Laomedon() {
        this.name = "Laomedon";
    }
    @Override
    public void getResponse(boolean[] status) {
        boolean wumpusNear = status[0];
        boolean hunterNear = status[1];
        boolean corpseNear = status[2];
        boolean arrowNear = status[3];
        boolean hunterHere = status[4];
        switch (myState) {
        case CORPSE_BEHIND:
            if(wumpusNear)
            {
                this.nextDirection = Direction.BACK;
                this.nextMove = Move.SHOOT;
            }
            else
            {
                this.nextDirection = Direction.HERE;
                this.nextMove = Move.MOVE;
            }
            break;
        case CORPSE_LEFT:
            if(wumpusNear)
            {
                this.nextDirection = Direction.LEFT;
                this.nextMove = Move.SHOOT;
            }
            else
            {
                this.nextDirection = Direction.HERE;
                this.nextMove = Move.MOVE;
            }
            break;
        case INITIAL_CORPSE_LEFT:
            if(corpseNear)
            {
                this.nextDirection = Direction.RIGHT;
                this.nextMove = Move.MOVE;
                this.myState = Laomedon.status.INITIAL_CORPSE_RIGHT;
            }
            else
            {
                this.nextDirection = Direction.BACK;
                this.nextMove = Move.MOVE;
                this.myState = Laomedon.status.SEARCHED_LEFT;
            }
            break;
        case INITIAL_CORPSE_RIGHT:
            if(corpseNear)
            {
                this.nextDirection = Direction.LEFT;
                this.nextMove = Move.MOVE;
                myState = Laomedon.status.INITIAL_CORPSE_LEFT;
            }
            else
            {
                this.nextDirection = Direction.BACK;
                this.nextMove = Move.MOVE;
                this.myState = Laomedon.status.SEARCHED_LEFT;
            }
            break;
        case SEARCHED_LEFT:
            if(corpseNear)
            {
                this.nextDirection = Direction.LEFT;
                this.nextMove = Move.MOVE;
                this.myState = Laomedon.status.SMELT_CORPSE;
            }
            else
            {
                this.nextDirection = Direction.RIGHT;
                this.nextMove = Move.MOVE;
                this.myState = Laomedon.status.SEARCHED_RIGHT;
            }
            break;
        case SEARCHED_RIGHT:
            if(corpseNear)
            {
                this.nextDirection = Direction.LEFT;
                this.nextMove = Move.MOVE;
                this.myState = Laomedon.status.SMELT_CORPSE;
            }
            else
            {
                this.nextDirection = Direction.LEFT;
                this.nextMove = Move.MOVE;
                this.myState = Laomedon.status.SEARCHED_LEFT;
            }
            break;
        case SMELT_CORPSE:
            if(corpseNear)
            {
                this.nextDirection = Direction.BACK;
                this.nextMove = Move.MOVE;
                this.myState = Laomedon.status.CORPSE_BEHIND;
            }
            else
            {
                this.nextDirection = Direction.BACK;
                this.nextMove = Move.MOVE;
                this.myState = Laomedon.status.CORPSE_LEFT;
            }
            break;
        case START:
            if(corpseNear)
            {
                this.nextDirection = Direction.LEFT;
                this.nextMove = Move.MOVE;
                this.myState = Laomedon.status.INITIAL_CORPSE_LEFT;
            }
            else
            {
                this.nextDirection = Direction.LEFT;
                this.nextMove = Move.MOVE;
                this.myState = Laomedon.status.SEARCHED_LEFT;
            }
            break;
        }
    }

    @Override
    public void newGame() {

        super.newGame();
        myState = status.START;
    }
}

```

Unfortunately for him, the other hunters don't appreciate his skills and they seem to shoot him a lot...
> 2 votes

# Answer
# NealHunter

After talking about this with my friend DoctorHeckle, I'd thought it would be fun to try it myself. Used the idea for alternating left and right to cover the most area, and then decided to add a bit of responding to the states, but only 0 and 1 - whether or not a Wumpus or hunter are nearby. Doesn't perform as well as NascarHunter, which surprised me at first. After some thinking though, I realized that shooting an arrow in a random direction (like this does) after hearing a hunter/smelling a Wumpus won't do anything if they're moving that turn, since arrows are shot into rooms, but movement is carried out before it kills them. Not quite as effective as I thought... still performs well though!

```
package Hunters;

import Mechanics.*;
import java.util.Random;

public class NealHunter extends Hunter {

    private boolean goLeft;

    public NealHunter(){
        name = "NealHunter";
        goLeft = false;
    }

    public void newGame() {
        goLeft = false;
    }

    public void getResponse(boolean[] status){

        Random rand = new Random();

        if(status[0] || status[1]){
            nextMove = Move.SHOOT;

            switch ( rand.nextInt(3) ){
                case 0:
                    nextDirection = Direction.LEFT;
                    break;
                case 1:
                    nextDirection = Direction.BACK;
                    break;
                case 2:
                    nextDirection = Direction.RIGHT;
                    break;
            }
        } else {
            nextMove = Move.MOVE;
            if (goLeft) {
                nextDirection = Direction.LEFT;
            } else {
                nextDirection = Direction.RIGHT;
            }

            goLeft = !goLeft;
        }
    }
}

```
> 2 votes

# Answer
# WalkingIdiot

This one walks until he finds the wumpus. Then, he shoots right. If the wumpus is still there, it must be on the left, so shoot once again. On the way, he doesn't care about other hunters or corpses, hence the name.

```
package Hunters;

import Mechanics.*;

public class WalkingIdiot extends Hunter {
    private boolean wumpusNear = false;

    @Override
    public void newGame() {
        wumpusNear = false;
    }

    public WalkingIdiot(){
        name = "WalkingIdiot";
    }

    @Override
    public void getResponse(boolean[] status){
        boolean wumpusWasNear = wumpusNear;
        wumpusNear = status[0];
        if (status[0]) {
            nextMove = Move.SHOOT;
            if (wumpusWasNear) {
                nextDirection = Direction.LEFT;
            } else {
                nextDirection = Direction.RIGHT;
            }
            return;
        }
        nextMove = Move.MOVE;
        nextDirection = Math.random() < 0.5 ? Direction.LEFT : Direction.RIGHT;
    }
}

```

# Stay

Stay doesn't like to walk. It simply shoots around and remembers if he shot a hunter.

```
package Hunters;

import Mechanics.*;

public class Stay extends Hunter {
    private Direction lastShot = Direction.LEFT;
    private Direction corpse = null;
    private boolean hunterNear = false;

    public Stay(){
        name = "Stay";
    }

    @Override
    public void newGame() {
        corpse = null;
        hunterNear = false;
        lastShot = Direction.LEFT;
    }

    @Override
    public void getResponse(boolean[] status){
        nextMove = Move.SHOOT;//always
        boolean hunterWasNear = hunterNear;
        hunterNear = status[1];

        if (hunterWasNear && status[2] && !status[1]) {
            corpse = lastShot;
        }

        if (status[0]) {
            if (corpse != null) {
                nextDirection = corpse;
                return;
            }
        }
        if ((status[1] && !status[4]) || status[0]) {
            switch (lastShot) {
                case LEFT: lastShot = nextDirection = Direction.RIGHT; break;
                case RIGHT: lastShot = nextDirection = Direction.BACK; break;
                case BACK: lastShot = nextDirection = Direction.LEFT; break;
            }
            return;
        }

        //default
        lastShot = nextDirection = Direction.LEFT;
    }
}

```
> 1 votes

---
Tags: king-of-the-hill, java
---


title: Find the Shortest Swype Path

text:
# Question
Title: Find the Shortest Swype Path
## Introduction

Lately, I've been getting used to typing with Swype.

I've noticed certain words can be produced by drawing a straight line from your starting letter to your ending letter, or by skipping letters that repeat.

For example, I can type the word `balloon` by Swyping across the following letters:

`b` \> `a` \> `l` \> `o` \> `n`.

## Challenge

Let us define the **Shortest Swype Path**, or `SSP`, as the minimum number of distinguishable line segments needed to type a string. A line segment is a continuous straight line between any two, or more, letters. Any change in direction starts a new line segment - though some words may be Swyped by drawing only a single straight line.

Use this simple QWERTY keyboard layout:

```
q w e r t y u i o p
a s d f g h j k l
  z x c v b n m

```

In the above example, the word `balloon` will have an `SSP` of `4` as detailed in the sequence below:

```
1) Start at `b` (line segments = 0)
2) slide to `a` (line segments = 1)
3) slide to `l` (line segments = 2)
4) slide to `o` (line segments = 3)
5) slide to `n` (line segments = 4)

```

The string `qwerty` has `SSP` = 1 since no change of direction is required when Swyping this word.

## Input

A single word string containing any `a-z` via STDIN, function argument, or command line.

## Output

Print via STDOUT, return, or your languages closest alternative, the number `n` representing the string's `SSP`.

One trailing newline optional in outut. Standard loopholes disallowed. Shortest submission in bytes wins.

## Notes

* A change in direction starts a new line segment.
* Letters that repeat are only counted once (e.g.: `bookkeeper` should be treated as `bokeper`).
* Normally, Swpye corrects missed letters by looking at neighboring letters and filling in its best guess. For this challenge, assume there is no natural language augmentations, predictive text or error correction.
* Uppercase `A-Z` inputs are treated like their lowercase counterparts.
* Ignore any numbers `0-9` in the input.
* Diagonal paths are allowed - that is, a straight line that covers letters `o`, `k`, `n`, for example, count as `1` segment. This rule applies to any diagonal slope (e.g.: letters `c`, `h`, `i` are in line).

## Examples

```
Input          Output
---------------------
a                0
aa               0
aaaaaa           0
aaaaaabc         2
in               1
int              2
java             3
qwerty           1
chicago          5
balloon          4
BALLOON          4
typewriter       5
bookkeeper       6
stackexchange    11
2hello7          3
2HELLO7          3

```

# Answer
# CJam, ~~78~~ ~~76~~ ~~73~~ ~~68~~ 62 bytes

```
relA,s-:_2ew{:-},{{i"x8LÑejPG ÀÏi"225b28b=A+Ab}/.-:ma}%e`,

```

Note that the code contains unprintable characters.

*Borrowing @isaacg's clever idea of using RLE to count the paths saved 6 bytes.*

Try it online in the CJam interpreter. If the link doesn't work, copy the code from this paste.

### How it works

```
rel      e# Read a token from STDIN and cast it to lowercase.
A,s-     e# Remove all digits.
:_       e# Duplicate each element of the argument (string/array).
2ew      e# Push all overlapping slices of length 2.
{:-},    e# Filter out slices where both elements are equal.
{        e# For each slice:
  {      e#   For each character of the slice:
    i    e#     Push its code point.

    "x8LÑejPG ÀÏi"225b28b

         e#     Convert the string from base 225 to base 28, pushing the array
         e#     [15 7 16 17 18 27 26 8 9 0 3 11 4 6 24 1 22 5 21 10 25 23 12 2 13 14].
         e#     These are the positions on the QWERTY keyboard, starting from the
         e#     upper left corner and going right.

    =    e#     Select the element that corresponds to the code point.

         e#     Arrays wrap around in CJam. Since 'a' has code point 97, the array has
         e#     length 26 and 97 % 26 == 19, 'a' corresponds to the 20th element.

    A+Ab e#     Add 10 and convert to base 10. Example: 8 -> [1 8]
  }/     e#
  .-     e#     Vectorized subtraction. [a b] [c d] -> [a-c b-d]
  :ma    e#     atan2. Pushes the angle of the direction. [y x] -> arctan(y/x)
}%       e#
e`       e# Apply run-length encoding.
,        e# Count the runs.

```
> 8 votes

# Answer
# Pyth, ~~53~~ ~~50~~ 49 bytes

```
lrPMfT-VJm.jF.D@jC"XÖ;¿ìÇ×;¤ð$  _"28CdT@GrzZtJ8

```

Keyboard compression format thanks to @Dennis.

This answer contains some unprintable characters. See the links below for the correct code.

Demonstration. Test Harness.

Explanation:

```
lrPMfT-VJm.jF.D@jC"..."28CdT@GrzZtJ8
                              rzZ      Convert input to lowercase.
                            @G         Take the intersection with G.
                                       This removes the numbers.
         m                             Map over the characters
                 C"..."                Treat the string as a base 256 number.
                j      28              Convert this number to base 28, giving:
                                       [15, 7, 16, 17, 18, 27, 26,  ... ]
                                       which is the character positions
                                       from top left, rotated by 97 places.
               @         Cd            Index this list by ord(character)
             .D            T           divmod by 10, giving the x-y position.
          .jF                          Convert this to a complex number.
        J                              Save the result to J.
      -VJ                        tJ    Vectorize - over J and J[1:]. This gives
                                       pairwise diffeences between J's elements.
    fT                                 Filter the differences on being truthy.
                                       This removes letter pairs with no movement.
  PM                                   Map the remaining complex numbers to their
                                       phases, which indicates their directions.
 r                                 8   Run-length encode the result.
l                                      Print out the number of separate RLE groups.

```
> 3 votes

---
Tags: code-golf
---


# Question
Title: Resize rasterized text and make it look non-pixellated
This is a screenshot of some text typed in a text editor:

This is the same text at a larger size.

Notice how visible the aliasing is on letters with prominent diagonal strokes like `x` and `z`. This issue is a major reason why raster fonts have lost popularity to “scalable” formats like TrueType.

But maybe this isn't an inherent problem with raster fonts, just with the way scaling of them is typically implemented. Here's an alternative rendering using simple bilinear interpolation combined with thresholding.

This is smoother, but not ideal. Diagonal strokes are still bumpy, and curved letters like `c` and `o` are still polygons. This is especially noticeable at large sizes.

So is there a better way?

# The task

Write a program that takes three command-line arguments.

```
resize INPUT_FILE OUTPUT_FILE SCALE_FACTOR

```

where

* INPUT\_FILE is the name of the input file, which is assumed to be an image file containing black text on a white background. You may use any mainstream *raster* image format (PNG, BMP, etc.) that's convenient.
* OUTPUT\_FILE is the name of the output file. It can be either a raster or vector image format. You may introduce color if you're doing some ClearType-like subpixel rendering.
* SCALE\_FACTOR is a positive floating-point value that indicates how much the image may be resized. Given an *x* × *y* px input file and scaling factor *s*, the output will have a size of *sx* × *sy* px (rounded to integers).

You may use a third-pary open-source image processing library.

In addition to your code, include sample outputs of your program at scale factors of **1.333, 1.5, 2, 3, and 4** using my first image as input. You may also try it with other fonts, including proportionally-spaced ones.

# Scoring

This is a popularity contest. The entry with the greatest number of upvotes minus downvotes wins. In case of an exact tie, the earlier entry wins.

**Edit**: Deadline extended due to lack of entries. TBA.

Voters are encouraged to judge based primarily on how good the output images look, and secondarily on the simplicity/elegance of the algorithm.

# Answer
# Ruby, with RMagick

The algorithm is very simple—find patterns of pixels that look like this:

```
    ####
    ####
    ####
    ####
########
########
########
########

```

and add triangles to make them look like this:

```
    ####
   #####
  ######
 #######
########
########
########
########

```

Code:

```
#!/usr/bin/ruby

require 'rmagick'
require 'rvg/rvg'
include Magick

img = Image.read(ARGV[0] || 'img.png').first
pixels = []
img.each_pixel{|px, x, y|
    if px.red == 0 && px.green == 0 && px.blue == 0
        pixels.push [x, y]
    end
}

scale = ARGV[2].to_f || 5.0
rvg = RVG.new((img.columns * scale).to_i, (img.rows * scale).to_i)
    .viewbox(0, 0, img.columns, img.rows) {|cnv|
    # draw all regular pixels
    pixels.each do |p|
        cnv.rect(1, 1, p[0], p[1])
    end
    # now collect all 2x2 rectangles of pixels
    getpx = ->x, y { !!pixels.find{|p| p[0] == x && p[1] == y } }
    rects = [*0..img.columns].product([*0..img.rows]).map{|x, y|
        [[x, y], [
            [getpx[x, y  ], getpx[x+1, y  ]],
            [getpx[x, y+1], getpx[x+1, y+1]]
        ]]
    }
    # WARNING: ugly code repetition ahead
    # (TODO: ... fix that)
    # find this pattern:
    # ?X
    # XO
    # where X = black pixel, O = white pixel, ? = anything
    rects.select{|r| r[1][0][1] && r[1][1][0] && !r[1][2][1] }
        .each do |r|
            x, y = r[0]
            cnv.polygon x+1,y+1, x+2,y+1, x+1,y+2
        end
    # OX
    # X?
    rects.select{|r| r[1][0][1] && r[1][3][0] && !r[1][0][0] }
        .each do |r|
            x, y = r[0]
            cnv.polygon x+1,y+1, x+0,y+1, x+1,y+0
        end
    # X?
    # OX
    rects.select{|r| r[1][0][0] && r[1][4][1] && !r[1][5][0] }
        .each do |r|
            x, y = r[0]
            cnv.polygon x+1,y+1, x+0,y+1, x+1,y+2
        end
    # XO
    # ?X
    rects.select{|r| r[1][0][0] && r[1][6][1] && !r[1][0][1] }
        .each do |r|
            x, y = r[0]
            cnv.polygon x+1,y+1, x+2,y+1, x+1,y+0
        end
}
rvg.draw.write(ARGV[1] || 'out.png')

```

Outputs (click any to view image by itself):

1.333

1.5

2

3

4
> 4 votes

---
Tags: popularity-contest, image-processing
---


# Question
Title: Compute 30000 Digits of Pi (π), as Fast as Possible
Compute 30000 digits of the mathematical constant π, with the fastest code.

Implement in any computer programming language that I can run in my 64 bit Linux machine. You should provide your compiler optimization options if any. I am ready to install a new compiler or language runtime to run your code, given that I am not spending any money.

The code that finishes calculation and prints the output in the shortest time wins! I will measure the running time with the `time` command.

note 1: The program should be single threaded.
note 2: With 3.14, the number of digits is 3; with 3.1415, 5, and so on.
note 3: Hard coding π is not allowed.
note 4: Now you can use any number form in your code, not only integer.
note 5: Your output, which should be in decimal digits, need not contain the `.`. Just print out the numbers.
note 6: Your last digit should **not** be rounded up. If the next digit after the last is 5 or more, you should ~~round up your last digit~~ still leave the last digit as is.

*Since this question was marked as duplicate, to this question. I should explain that this is a 'fastest-code' question not 'code-golf' and thus not a dupliate. The 'code-golf' answers are not well suited as an answer to this question; they are not the 'fastest'.*

# Answer
# Python 2 (Spigot Algorithm)

This is just Jeremy Gibbon's algorithm implemented in python. Definitely will be faster once someone else implements this in another language. Other methods might be faster too since I started working on this when the rules stated that I could only use integers. I originally tried doing this without string conversion and joining, but it was actually slower..

```
def p():
 q,r,t,j=1,180,60,2
 while True:
    u,y=3*(3*j+1)*(3*j+2),(q*(27*j-12)+5*r)//(5*t);yield y;q,r,t,j=10*q*j*(2*j-1),10*u*(q*(5*j-2)+r-y*t),t*u,j+1
p=p()
print''.join(str(p.next())for x in[1]*30000)

```

Completes on my work machine in about 53 seconds.
> 3 votes

---
Tags: math, fastest-code
---


title: Boggle Board Compression

text:
# Question
Title: Boggle Board Compression
When working on Non-Palindromic Polyglot Boggle, I found it quite tedious to pack the codes as efficiently as possible onto the Boggle board, even with only two strings. But we're programmers, right? We know how to automate things.

Given a list of strings, you're to generate a Boggle board on which each of those strings can be found (independently of the others). The challenge is to make the Boggle board as small as possible. As this is (hopefully) a rather difficult task, this is a : there is no requirement for optimality - the challenge is to do it as well as you can.

## Rules

* The Boggle board will be rectangular and contain only upper case letters. Therefore, the input strings will also contain only upper case letters.
* The usual Boggle rules apply: a string is part of the board if, starting anywhere, you can find the string by repeatedly moving to adjacent characters (horizontally, vertically, or diagonally). To form a single string, you cannot use any cell of the board more than once. However, characters *may* be reused between different strings.
* You've got 30 minutes to process the test data, and your code must not use more than 4 GB of memory. I will give a little bit of leeway on the memory limit, but if your program consistently uses more than 4 GB or spikes significantly above it, I will (temporarily) disqualify it.
* I will test all submissions on my own machine, which is running Windows 8. I do have a Ubuntu VM, but if I have to test on that you won't be able to make as much use of the 30 minutes as otherwise. Please include a link to a free interpreter/compiler for your chosen language, as well as instructions on how to compile/run your code.
* Your score will be the size of the Boggle board for the test data below (not counting the newlines). In the case of a tie (e.g. because multiple people managed to produce an optimal solution), the winner will be the submission that produces this optimal solution faster.
* You must not optimise your code specifically towards the test data. If I suspect anyone of doing so, I reserve the right to generate new test data.

## Example

Given the strings

```
FOO
BAR
BOOM

```

Once could trivially put them in a 4x3 Boggle board:

```
FOOX
BARX
BOOM

```

By making use of the fact that strings don't have to be straight, we can compress it to 5x2:

```
BORFO
OMABO

```

But we can make it even smaller by reusing characters between different strings, and fit the strings in 4x2:

```
FOOM
BARX

```

Now the `B` is used for both `BOOM` and `BAR`, and the `OO` is used for both `BOOM` and `FOO`.

## Test Data

Your submission will be tested on the following 50 strings. For testing purposes you can simply use smaller subsets of this data which should then run more quickly. I believe that the absolute lower bound for this test data is a board with 120 characters, although this is not necessarily achievable.

```
T
WP
GVI
CIHM
EGWIV
QUTYFZ
LWJVPNG
XJMJQWSW
JLPNHFDUW
SWMHBBZWUG
XVDBMDQWDEV
TIUGAVZVUECC
IWDICFWBPSPQR
MMNWFBGMEXMSPY
YIHYXGJXKOUOIZA
BZSANEJNJWWNUJLJ
XTRMGOVPHVZYLLKKG
FLXFVVHNTWLMRRQYFQ
VZKJRAFQIYSBSXORTSH
FNQDIGCPALCHVLHDNZAV
GEAZYFSBSWCETXFKMSWLG
KWIZCEHVBDHEBGDGCJHOID
SKMQPHJAPDQKKHGTIPJCLMH
ZSFQDNYHALSUVWESQVVEUIQC
HXHBESUFCCECHNSTQGDUZPQRB
DSLXVHMOMLUXVHCNOJCBBRPVYB
DVTXKAOYYYRBVAVPSUAOYHIPPWN
PJAIYAWHMTNHTQDZDERPZYQEMLBZ
SYNSHJNOIWESMKWTBIANYUAUNRZOS
WADGUKIHUUFVRVUIBFUXQIOLAWIXAU
LGLXUFIXBEPSOFCKIAHXSHVKZPCXVPI
LIUYFHITTUYKDVQOZPNGZLWOZSRJTCTZ
IZDFTFFPNEBIYGVNTZHINICBXBXLBNBAL
BSKQNTPVUAVBXZGHVZCOUCRGCYISGFGYAS
DPGYYCIKDGCETXQOZGEQQLFQWACMVDTRYAT
RQDNIPGUHRYDRVHIPJLOWKBXMIBFAWCJGFMC
PFKOAGEQLXCMISSVEARWAPVYMRDCLSLPJOMQQ
EQPCNHQPTWABPFBVBXHQTFYELPNMNCWVKDDKGR
RAHTJMGIQJOJVWJBIHVRLJYVCSQJCKMEZRGRJMU
SZBJBPQYVYKDHAJHZMHBEWQEAQQKIEYCFACNLJBC
ANVDUCVXBPIZVRAXEBFEJOHSYKEKBIJELPIWEYXKH
DJUNPRLTISBFMGBEQNXSNUSOGDJNKESVKGAAMTIVXK
TZPUHDSHZFEURBNZTFBKXCDPYRELIAFMUWDIQTYWXGU
FJIKJROQSFSZUCGOOFJIEHBZREEUUSZWOLYFPCYHUSMR
TPMHJEAWVAJOCSDOPMQMHKRESBQSTRBXESYGCDVKLFOVS
ABJCCDJYMYDCYPZSGPGIAIKZQBYTZFDWYUZQBOESDSDGOY
IIHKTVPJNJDBCBOHCIYOPBKOVVKGNAKBDKEEKYIPRPHZOMF
IABGEPCSPNSMLVJBSGLRYNFSSYIALHWWAINTAVZAGJRVMDPW
GFMFVEFYJQJASVRIBLULUEHPMZPEXJMHIEMGJRMBLQLBDGTWT
YPWHLCVHQAVKVGHMLSOMPRERNHVYBECGCUUWTXNQBBTCMVTOVA

```

## Verifier

You can use the following Stack Snippet to verify whether a Boggle board contains all strings in a given list. I ported the Boggle search code from edc65's answer over here. Let me know if anything seems buggy.

```
function verify() {
  var strings = document.getElementById("strings").value;
  var board = document.getElementById("board").value;
  strings = strings.match(/[A-Z]+/g) || [];
  board = board.split('\n');
  var valid = true;
  var len = board[0].length;
  var result = 'Valid';
  for (var i = 0; i < board.length; ++i)
  {
    if (board[i].length != len)
    {
      valid = false;
      result = 'Invalid: Board not rectangular.';
    }
    if (/[^A-Z]/.test(board[i]))
    {
      valid = false;
      result = 'Invalid: Board contains invalid character on line '+i+'.';
    }
    if (!valid) break;
  }
  if (valid)
    for (i = 0; i < strings.length; ++i) {
      if (!findInBoard(board, strings[i]))
      {
        valid = false;
        result = 'Invalid: String "'+strings[i]+'"not found in board.';
        break;
      }
    }
  document.getElementById("output").innerHTML = result;
}

function findInBoard(b, w) {
  var l = b[0].length;
  var r = 0;
  var Q = function(p, n) {
    return (r |= !w[n]) ||
    (
      b[p] = 0,
      [1,l,l+1,l+2,-1,-l,-l-1,-l-2].map( function(q) { return b[q+=p]==w[n] && Q(q,n+1) }),
      b[p] = w[n-1]
    );
  }
  b = (b+'').split('');
  b.map(function(e, p) { return e==w[0] && Q(p,1) });
  return r;
}
```

```
Strings that should be part of the Boggle board:
<br>
<textarea id="strings" cols="60" rows="10"></textarea>
<br>
Boggle board:
<br>
<textarea id="board" cols="60" rows="10"></textarea>
<br>
<input type="button" value="Verify" onclick="verify()" />
<br>
<br>
<div id="output"></div>
```

# Answer
# C++11, score = 992 ~~1024~~

The algorithm is really stupid, but so far no one else made a serious one either, so I'll post it. It more or less randomly sticks words on a square board, and then starts over if it doesn't manage to make them fit. It kind of tries to maximize overlap with the existing words, but in a really inefficient way.

Edit: Improved score by adding 1 to a side length and trying a rectangle after failing 50 times. Also sorted input strings by size instead of randomizing the order.

```
#include <iostream>
#include <cstring>
#include <string>
#include <random>
#include <algorithm>
using namespace std;

struct grid {
    char *g;
    int h,w;
    grid(int h, int w):h(h),w(w) {
        g = new char[h*w];
        memset(g,0,h*w*sizeof(*g));
    }
    grid(const grid &o) {
        h=o.h, w=o.w;
        g = new char[h*w];
        memcpy(g,o.g,h*w*sizeof(*g));
    }
    grid(grid &&o) {
        h=o.h, w=o.w;
        g = o.g;
        o.g = 0;
    }
    grid& operator=(const grid &o) {
        h=o.h, w=o.w;
        memcpy(g,o.g,h*w*sizeof(*g));
        return*this;
    }
    grid& operator=(grid &&o) {
        h=o.h, w=o.w;
        g = o.g;
        o.g = 0;
        return*this;
    }
    char& operator()(int i, int j) {
        return g[i*w+j];
    }
    ~grid() { delete []g; }
};
typedef struct { int n, i, j; grid g; } ng;

const int qmax = 140;
const bool sizesort = true;
const int maxtries = 50;

inline int sq(int x){return x*x;}
bool operator<(const ng &a, const ng& b) {return a.n < b.n;}
void search(vector<string>& s) {
    int tl = 0;
    for(auto&x: s) tl += x.size();
    int l = 0;
    while(l*l < tl) l++;
    vector<string*> v;
    for(size_t i = 0; i < s.size(); i++) v.push_back(&s[i]);
    struct{bool operator()(string*a,string*b){return a->size()>b->size();}} scmp;
    if(sizesort) sort(v.begin(), v.end(), scmp);
    mt19937 rng;
    for(;;l--) {
        int tries = 0;
        int side2 = l;
        retry:
        tries++;
        if(!sizesort) shuffle(v.begin(), v.end(), rng);

        if(tries == maxtries) cout<<"rectangle",side2++;
        grid g(l,side2);

        for(string* x: v) {
            string& z = *x;
            vector<ng> p;
            for(int i = 0; i < g.h; i++)
            for(int j = 0; j < g.w; j++) {
                if(g(i,j) && g(i,j) != z[0]) continue;
                p.push_back({!g(i,j), i,j, g});
                p.back().g(i,j) = z[0]|32;
            }
            for(size_t zi = 1; zi < z.size(); zi++) {
                vector<ng> p2;
                for(ng &gg: p) {
                    for(int i = max(gg.i-1,0); i <= min(gg.i+1,g.h-1); i++)
                    for(int j = max(gg.j-1,0); j <= min(gg.j+1,g.w-1); j++) {
                        if(!gg.g(i,j) || gg.g(i,j) == z[zi]) {
                            p2.push_back({gg.n+!g(i,j),i,j,gg.g});
                            p2.back().g(i,j) = z[zi]|32;
                        }
                    }
                }
                shuffle(p2.begin(), p2.end(), rng);
                sort(p2.begin(), p2.end());
                if(p2.size() > qmax) p2.erase(p2.begin() + qmax, p2.end());
                p = move(p2);
            }
            if(p.empty()) goto retry;
            g = p[0].g;
            for(int i = 0; i < g.h; i++)
            for(int j = 0; j < g.w; j++)
                g(i,j) &= ~32;
        }
        cout<<g.w*g.h;
        for(int i = 0; i < g.h; i++) {
            cout<<'\n';
            for(int j = 0; j < g.w; j++)
                cout<<(g(i,j)?g(i,j):'X');
        }
        cout<<endl;
    }
}

int main()
{
    vector<string> v = {"T","WP","GVI","CIHM","EGWIV","QUTYFZ","LWJVPNG","XJMJQWSW","JLPNHFDUW","SWMHBBZWUG","XVDBMDQWDEV","TIUGAVZVUECC","IWDICFWBPSPQR","MMNWFBGMEXMSPY","YIHYXGJXKOUOIZA","BZSANEJNJWWNUJLJ","XTRMGOVPHVZYLLKKG","FLXFVVHNTWLMRRQYFQ","VZKJRAFQIYSBSXORTSH","FNQDIGCPALCHVLHDNZAV","GEAZYFSBSWCETXFKMSWLG","KWIZCEHVBDHEBGDGCJHOID","SKMQPHJAPDQKKHGTIPJCLMH","ZSFQDNYHALSUVWESQVVEUIQC","HXHBESUFCCECHNSTQGDUZPQRB","DSLXVHMOMLUXVHCNOJCBBRPVYB","DVTXKAOYYYRBVAVPSUAOYHIPPWN","PJAIYAWHMTNHTQDZDERPZYQEMLBZ","SYNSHJNOIWESMKWTBIANYUAUNRZOS","WADGUKIHUUFVRVUIBFUXQIOLAWIXAU","LGLXUFIXBEPSOFCKIAHXSHVKZPCXVPI","LIUYFHITTUYKDVQOZPNGZLWOZSRJTCTZ","IZDFTFFPNEBIYGVNTZHINICBXBXLBNBAL","BSKQNTPVUAVBXZGHVZCOUCRGCYISGFGYAS","DPGYYCIKDGCETXQOZGEQQLFQWACMVDTRYAT","RQDNIPGUHRYDRVHIPJLOWKBXMIBFAWCJGFMC","PFKOAGEQLXCMISSVEARWAPVYMRDCLSLPJOMQQ","EQPCNHQPTWABPFBVBXHQTFYELPNMNCWVKDDKGR","RAHTJMGIQJOJVWJBIHVRLJYVCSQJCKMEZRGRJMU","SZBJBPQYVYKDHAJHZMHBEWQEAQQKIEYCFACNLJBC","ANVDUCVXBPIZVRAXEBFEJOHSYKEKBIJELPIWEYXKH","DJUNPRLTISBFMGBEQNXSNUSOGDJNKESVKGAAMTIVXK","TZPUHDSHZFEURBNZTFBKXCDPYRELIAFMUWDIQTYWXGU","FJIKJROQSFSZUCGOOFJIEHBZREEUUSZWOLYFPCYHUSMR","TPMHJEAWVAJOCSDOPMQMHKRESBQSTRBXESYGCDVKLFOVS","ABJCCDJYMYDCYPZSGPGIAIKZQBYTZFDWYUZQBOESDSDGOY","IIHKTVPJNJDBCBOHCIYOPBKOVVKGNAKBDKEEKYIPRPHZOMF","IABGEPCSPNSMLVJBSGLRYNFSSYIALHWWAINTAVZAGJRVMDPW","GFMFVEFYJQJASVRIBLULUEHPMZPEXJMHIEMGJRMBLQLBDGTWT","YPWHLCVHQAVKVGHMLSOMPRERNHVYBECGCUUWTXNQBBTCMVTOVA"};
    search(v);
    return 0;
}

```

The board:

```
TGBHXEXMPYTECWBSFYOXKXKXFSQJXKXX
UZBWMLJKSXXPIXSVYYXATVDLVOCVCXMT
WWPSJGBUFWPOUHPAKRZMXIPCHHXJYEAX
SQPBNXFQNMLAYSQVBGAESYGWQJOVXJZY
RJXWJJDWMNSGFUQXSEAWXBMIJAYWLRTR
XMXFEIWIHTIHIGMOJTKVARJNPSVFJVDG
XJHNCGCCQXTYLSJHVNOJXHTSCKERBHMR
XVCLACEDGTCCDGLPMCJXXMQMQPVGIAJC
DLZSFPURZYUGRKENTWSDPVLSHBFFHBMA
HNBUQYZPDOKNMYDDVBBOGJBQGKSMLUWQ
XXZRSEBQNCQDPVFNKSSQNCDLXERPMSLF
XKVAIHMHTGZVUXPTQUSXXGEBRXEZHOUQ
XRJUXYNLQFJLHAVQPNNXTCXYMRJPKEQH
FAPIHATDBSWXWGBHCQHPBWUVNMJGKGVP
XQVVWMLJRZZOVRZXESFQTAUFHIMLLYZV
XIWXUSOQTXTLSEABVBIPXGXSYEAEMGOX
WEYQCBIUXCNSJKGRFZXTBXXSMFLIRYPQ
XGSBIPFLPAMIBEEMVEJLXDWDUBHTYXDX
XQSUXIZQGFOCPLKSUOAREVYQDWDVXCTA
XXVEBKXLEKCIOFYYHCBJPCTKIAWKIMZE
ORVEUGVIXYEWFPCCDJCNUDANHIBODFCI
XTOFPUSHKQXAZYDYIYOBJZVZBFMXLGOU
SZNSCXHLWQQSGCTQMBPDGAXXTRACJJXO
HRUAUKIAXEUOPGUIKWRJMNKKDGUWPBGK
ZVEYNGDNBUEOJIAZQORVGBDSEEOYIYXX
VMHCCAIBHRHFAESSBXVJKQOSKYFZHVPB
ALEVJPTWLMZJHXXFJYXIZUEFLIGUSRRB
GZCBDHPKMXXBXDSBTZJDUYVXNQPPHDYC
UIPJQKEQSBNICKYPNEFHWVHFDFRUZOJX
KWTGKXGBEOIJHNVQFBTLNTNMYXLTXNMX
DIOHJCXDGWHZTSGYIFJPMRRQOMXVHCFX

```
> 6 votes

# Answer
# Python 3, score = 1225

In this solution we use only 1 row. Starting from the empty string in every step we add the word which guarantees the largest possible overlap. (The words are checked in all 4 possible orientations.)

This gives a score of 1225 which is 50 lower than the score of 1275 for concatenating all the words together with no overlapping.

The result:

```
CBJLNCAFCYEIKQQAEQWEBHMZHJAHDKYVYQPBJBZSFQDNYHALSUVWESQVVEUIQCMFGJCWAFBIMXBKWOLJPIHVRDYRHUGPINDQRQPSPBWFCIDWIPVXCPZKVHSXHAIKCFOSPEBXIFUXLGLWSMKFXTECWSBSFYZAEGWIVGNPVJWLIUYFHITTUYKDVQOZPNGZLWOZSRJTCTZPUHDSHZFEURBNZTFBKXCDPYRELIAFMUWDIQTYWXGUWZBBHMWSKMQPHJAPDQKKHGTIPJCLMHICCEUVZVAGUITAYRTDVMCAWQFLQQEGZOQXTECGDKICYYGPDIOHJCGDGBEHDBVHECZIWKXVITMAAGKVSEKNJDGOSUNSXNQEBGMFBSITLRPNUJDSLXVHMOMLUXVHCNOJCBBRPVYBZSANEJNJWWNUJLJLPNHFDUWPDMVRJGAZVATNIAWWHLAIYSSFNYRLGSBJVLMSNPSCPEGBAIZDFTFFPNEBIYGVNTZHINICBXBXLBNBALQUTYFZBLMEQYZPREDZDQTHNTMHWAYIAJPFKOAGEQLXCMISSVEARWAPVYMRDCLSLPJOMQQFYQRRMLWTNHVVFXLFNQDIGCPALCHVLHDNZAVOTVMCTBBQNXTWUUCGCEBYVHNRERPMOSLMHGVKVAQHVCLHWPYPSMXEMGBFWNMMXJMJQWSWADGUKIHUUFVRVUIBFUXQIOLAWIXAUMJRGRZEMKCJQSCVYJLRVHIBJWVJOJQIGMJTHARGKDDKVWCNMNPLEYFTQHXBVBFPBAWTPQHNCPQEXVDBMDQWDEVZKJRAFQIYSBSXORTSHXHBESUFCCECHNSTQGDUZPQRBSKQNTPVUAVBXZGHVZCOUCRGCYISGFGYASYNSHJNOIWESMKWTBIANYUAUNRZOSVOFLKVDCGYSEXBRTSQBSERKHMQMPODSCOJAVWAEJHMPTWTGDBLQLBMRJGMEIHMJXEPZMPHEULULBIRVSAJQJYFEVFMFGKKLLYZVHPVOGMRTXYIHYXGJXKOUOIZANVDUCVXBPIZVRAXEBFEJOHSYKEKBIJELPIWEYXKHDVTXKAOYYYRBVAVPSUAOYHIPPWNFJIKJROQSFSZUCGOOFJIEHBZREEUUSZWOLYFPCYHUSMRABJCCDJYMYDCYPZSGPGIAIKZQBYTZFDWYUZQBOESDSDGOYIIHKTVPJNJDBCBOHCIYOPBKOVVKGNAKBDKEEKYIPRPHZOMF

```

The code:

```
import sys

def com_len(a,b):
    for i in range(min(len(a),len(b)),-1,-1):
        if (a[-i:] if i else '')==b[:i]:
            return i

def try_s(a,b,sn,mv):
    v=com_len(a,b)
    if v>mv:
        return a+b[v:],v
    return sn,mv

ws=[w.rstrip() for w in sys.stdin.readlines()]
s=''
while ws:
    mv=-1
    sn=None
    mi=None
    for i in range(len(ws)):
        mvo=mv
        for a in [s,s[::-1]]:
            for b in [ws[i],ws[i][::-1]]:
                sn,mv=try_s(a,b,sn,mv)
        if mvo<mv:
            mi=i
    s=sn
    del ws[mi]
print(s)

```
> 4 votes

# Answer
# C, score 1154

```
AVOTVMCTBBQNXTWUUCGCEBYVHNRERPMOSLMHGVKVAQHVCLHWPYGOSUNSXNQEBGMFBSITLRPNUJDXJMHIEMGJRMBLQLBDGTWTWVJOJQIGMJTHARYPDCXKBFTZNBRUEFZHSDHUPZTCUZSFSQORJKIJFYNDQFSZOWLZGNPZOQVDKYUTTIHFYUILHWWAINTAVZAGJRVMDPWPQRBEAWVAJOCSDOPMQMHKRESBQSTRBXESYGCDVKLFOVSOYNUAUYNAIBTWKMSEWIONJHSNYSKYVYQPBJBZSOHCIYOPBKOVVKGNAKBDKEEKYIPRPHZOMFGJCWAFBIMXBKWOLJPIHVRDYRHUGPINDQRQPSPBWFCIDWIVPAWRAEVSSIMCXLQEGAOKFPFFTFDZIWLMRRQYFQSXORTSHLUXVHCNOJCBBRPVYBMKSNTPVUAVBXZGHVZCOUCRGCYISGFGYASOZGEQQLFQWACMVDTRYATIAJPVUECCYFSBSWCETXFKMSWLGFUUHIKUGDAWIYXCPZKVHSXHAIKCFOSPEBXIFUXLGLJNHFDUWSWQJMJXWSMXEMGBFWNMMGOVPHVZY
NDUCVXBPIZVRAEBFEJOHSYKEKBIJLPIWEYXKKXITMAGKSEKNJDFMFVEFYJQJASVRILULUEHMZPEUMRGRZKCJQSCVYJRVHIBJUGXWYTDWUFAILERMSUHYCPYLOWZSUERBEIJFOOGQIEVVQEWVUSLAHZTCTJRIABGEPCSNSMLJBSGLRYNFSSYAXHBESUFCCECHNSTQGUZTMHJABJCCDYMYDCYZSGPGIAIKZBYZFDWYUZQBOESDSDGZRCBJLNCAFCYEIQQAQEBHMZJAHDIIHKTVJNDCBNWPPHAUSPVABRYYYOAKXTVDWQDMBDVXCRGKDDKVWCNNPLEYFTQHXBBFPBAWTPQHCPEQMOJLSLCDRMYLABNBLXBXBCNIHZTNVYIBENLXVVHNTVZKJAFISBDLVHMOMCJPITGHKKQDPAJHPQBSQKWIZCEHDHEBDGCJHIDDPYYCKDCETXQZBLMYZPREDZDQTHNMHWYUGVZIWGAZUAXIWALOIQUBIUVRVAZIOUOXJXYHPVAZNDHLCLAPCGDQNBZANJNJWWNUJLPGPVJWLGUZBBHMYPHICQUTYZXTRVIXGKKLL

```

Use two lines so newly added words can reuse the letters from the top line.

```
char l[2][2000];
char s[2][2000];
char w[100][200];
int d[200];
void pri() {
    puts(l[0]);
    puts(l[1]);
}
void sav() { memcpy(s,l,sizeof(l)); }
void res() { memcpy(l,s,sizeof(l)); }
int fit(char *t, int l0, int l1) {
    if (!*t) return 0;
    if (l[0][l0] == *t && (l0 <= l1 || l[1][l1])) return 1+fit(t+1,l0+1,l1+(l1<l0));
    if (l[1][l1] == *t && (l1 <= l0 || l[0][l0])) return 1+fit(t+1,l0+(l0<l1),l1+1);
    if (!l[0][l0]) {
    strcpy(l[0]+l0,t);
    return 0;
    }
    if (!l[0][l1]) {
    strcpy(l[0]+l1,t);
    return 0;
    }
    if (!l[1][l1]) {
    l[1][l1] = *t;
    return fit(t+1,l0+(l0<l1),l1+1);
    }
    return 1000;
}
int main(){
    int j,i,n,best,besti,bestk,c,tot = 0;
    for (i = 0; scanf("%s ",w[i])>0; i+=2) {
    int j = strlen(w[i]);
    for (c = 0; c < j; c++) w[i+1][c] = w[i][j-c-1];
    }
    n = i;
    pri();
    for (j = 0; j < n/2; j++) {
    int k = -1;
    best = -1;
    for (k = 0; k <= strlen(l[1]); k++) {
    for (i = 0; i<n; i++) if (!d[i/2]) {
    sav();
    c = fit(w[i],k,k);
    if (c < 1000 && c >= best) best = c, besti = i, bestk = k;
    res();
    }
    }
    fit(w[besti],bestk,bestk);
    d[besti/2] = 1; tot += best;
    }
    pri();
    printf("%d - %d\n",tot, strlen(l[0])+strlen(l[1]));
    return 0;
}

```
> 4 votes

# Answer
# CJam, ~~1122~~ 1089 letters

```
qN%{,}$__W%Wf%+:A;s[,mQ)__2#_S*:B;+2/:P;:DX1$W*W]:M;1:L;{BQCelt:B;}:T;
{A,,{B:G;P:H;D:I;L:J;A=:Z{:C;PL+D-:QB=C=
{T}{QD+:QB=C={T}{BPCelt:B;PD+:PL+B=' ={MD#)M=:D;ML#)M=:L;}&}?}?}/BS-,Z,-G:B;H:P;I:D;J:L;}$
0=:KA={:C;PL+D-:QB=C={T}{QD+:QB=C=
{T}{BPCelt:B;PD+:PL+B=' ={MD#)M=:D;ML#)M=:L;}&}?}?}/Beu:B;AKWtK~WtW-:A}g
{PL+B=' -PD-L+B=' -e&}{BP'Zt:B;PD+:P;}w
BM0=/Sf-Oa-N*

```

The program constructs the rectangle from its center, spiraling outwards. This is a rather simple approach so far. There's still room for improvement.

The code is a big mess right now. I'll clean it up when I'm satisfied with my score.

Try it online in the CJam interpreter.

### Board

```
GXVDBDQDEVGPVJWLWSWQJMJMHCFNQDIGC
UIWESMKWBIANYUANRZOLGLXUFIXBEPSOP
WOPZUDGQTSHCCCUSEBHSKMQHJADKKHGFA
ZNQDKVWCMNPLEYFTQHXBVBPBATPQHNTCL
BJRDOWLZNPZQVDKYUTTIHFYILWADGCIKH
BHBKZXZGHZCOUCGCIGFGYSUGXYQIUPJAV
MSNGSBSMLVJSGLRYNSSIALHWWNTDKQCHL
WYWPRVNDSEBQZUYWFZTYBQZIAIAWIELXD
GSPAJAPSDIOHJDGHDBECZIWKSGVUHQMSN
VTHITUCGAWUUCGEBYVHNERPMZPZMUQHVZ
EIOYCVPONTFOOCUZSSQORJKOBGAFUMDKA
WGUAZTEYVXJYGDVKLFOSFMISJSJIVOPZV
IASWRNGTDNISBCBDJJPVTOJLBZRLRJGCS
IVPHDQBWUQHEOGOSUNNQKZFMPYVEVPYXF
WZVMNKATCBBXHDTROXSEHHTHQCMRULYVQ
DUATISIGVTZBCJSVZFBGIPMGYDPYISCPD
IEVNPBSDXCERINHKTYSMIRHVYMWDBLIYN
FCBHGRXLBMETYKDJQUIFKPJKDJGCFCKHA
WCRTUAVQPVUSOEURAFQBXIEVHDFXUDGYL
BQYQHTHLITUQPSNPLTISVYAQACMKQRCXS
PFYDRJMBZOZSBVKGAAMTIKWHJCFBIMEGU
SQYZYGOMRVWEKOVNKBDKEEVCHJVFOYTJV
PROEDILJXAORHMQMPOSCOJALZBETLVXKW
QRAPRQUGECLYFPCYHUMRYPWHMAFZAPQOE
WMKZVJXMFBJNCAFEIKQQAEQEBHYNWROUS
ULXYHOVIEJOHSYKKBJELPIWYXKJBIAZIQ
DWTQIJCHMXEPZMPHEULUBRVSAJQRXEGAV
FNVEPVNOJCBBRPVYBTZPHDSHZFEUAVQGV
PHDMJWJBIHVRLJYCSQJCKMEZRGRJMSQKE
LVMBLOKXMBFAWCGFMCPFOAGQLXCMISLKU
JVNZGEAZYFSBSETXKSWLGTYRTDVAWQFLI
WFWFBMXMSPYZANJNJWNUJLJXMGOPHVZYQ
PXLLANBLXBXBCIIHZTVGYIBENPFFTFDIC

```
> 3 votes

# Answer
# Python 3, score = 1014

Starting from a null sized area we add words letter by letter to the area in a way that the area will always be a rectangular spiral:

```
  .
32.
41.
567

```

We keep 10 boards candidates throughout the computation. At every step to every candidate we try to add every word that board has left in every possible legal way keeping the spiral layout. We score each of the resulting new boards based on the `total used word length / total area used` fraction. We keep the best 10 boards and repeat the step until there are no words left.

To minimize unused space at the end of the spiral we try taking some steps ahead before spiraling to create non-square spirals. E.g.:

```
98765
.1234
..

```

The word list is given in stdin. The (quite ugly) code takes about 30 minutes on my slow laptop. (If you want to wait less, you can choose `nonspiral_length=13` rather than looping through the possible values.)

The resulting board:

```
JFOOGCUZSFSQORKIJFYGDSDSEOQZUYWDFZTYBQZ
ISDHUZTIIHKTJNJDBCBOHIYOPBKVVGNAKBDKEEK
EHOJPSLCDRMYVPAWESSIMCLQEGAOKFPJLCAFCKI
BZMFYLPNMNKDKGRAVMCTBBXTWUUCGCBYHNREYPA
RFQTXESYGCDVKLFOVSSFQNYHALSVWESQVEQRIRI
EELQBZNGZLWOZSRJTCTZWDGUIHUUFVRVUICPKPG
UUAHROPSCPGBAVXCPZVHXAIKCOSPBXIFUBTMQHG
SRBXTQNSXYEIPLJIBKKYSHOJEFBEXRIPXFAOQZS
WZNBSVMAHKWZCEHVDHEGDGHIDTIGAVZBLQYSAOZ
OTLVQDLYXMTIVXKBYVRBCJONHVXULMVXGIRLEMP
LFXFBKVGHAFBGEXMSPSPBWFCIDWIMOUCLOTMQFY
YKBPSYJFBAWNTMRRQYNQDIGPALCHXLEDTADHWTC
FDXBEUBGEGMHJWLSMKFXTECBSFYVDSCVXWVGEWD
HPCARTLSSKMVVGUWZBBHMWSGEAZLBJCNKIMKBTY
UYIWKTRIUVZFPNQTYFXJJQWIVNDHMLPAOXCVHGM
SRNTHINYFSKXLFYIHXGKOUOZAEWQDJNIYAWAMDY
MEIPMHFGCEJRASBSXORTSHBSJNJWNUHTYUQHZBJ
XLZHQYSRCKNDGOUNNQEBGMFITLRPUDFGYXFVJLD
XITNMNSUECHSTQGDUZPSKQPHJAPDQKKHRTLCAQC
XAVCPHYOCZVGZXBVAVTNQNWPYOUSPVAVBMQHDLC
XFGQOJIALHWWAINTAGJRVMDGKKLLYZHPOGQWKBJ
XMYEDNOWESMKTBAYUUNZOSYYCIDGCETXQZEPYMA
XUICSCJAVJHPJAIWHMTHTQDZDERPZYQEMLBYVRA
XWBMFGWFBIMXBKWOLJPIVRYRHUGINDRSZBJPQJH
XDENPFTDZGFFVEFYJQASIBLULPMZPEXJMHIEMGT
XIQTYWXGUMJRGRZEMKCJQSCVYJLRVHIBWVJOJQI

```

The generating code:

```
import sys

class b:
    def __init__(s,l,ws):
        s.d=[' ']*(l*l)
        s.x,s.y=l//2,l//2
        s.l=l
        s.dir=1j
        s.ws=ws[:]
        # last char pos, remaining word part, used positions
        s.wx,s.wy,s.wp,s.wu=None,None,None,None

    def copy(s):
        #print('copy',s.x,s.y,s.wp)
        c=b(s.l,s.ws)
        c.d=s.d[:]
        c.x,c.y=s.x,s.y
        c.dir=s.dir*1
        c.wx,c.wy=s.wx,s.wy
        c.wp=s.wp[:] if s.wp!=None else None
        c.wu=s.wu[:] if s.wu!=None else None
        return c#copy.deepcopy(s) is very slow

    def score(s):
        placed_chars=allwlen-sum([len(w) for w in s.ws])
        used_cells=0
        for i in range(s.l):
            for j in range(s.l):
                if s.d[i*s.l+j]!=' ':
                    used_cells+=1
        return placed_chars/used_cells

    def get_next_bs(s):
        bl=[]
        for wi in range(len(s.ws)):
            bl+=s.get_b_for_w(wi)
        return bl

    def get_b_for_w(s,wi):
        w=s.ws[wi]
        bl=[]
        for i in range(1,s.l-1,3):
            for j in range(1,s.l-1,3):
                for reversed in True,False:
                    if abs(i-s.x)+abs(j-s.y)>5:
                        continue
                    bn=s.copy()
                    bn.wx,bn.wy=i,j
                    bn.wp=w if not reversed else w[::-1]
                    del bn.ws[wi]
                    bn.wu=[]
                    bnr=bn.get_bs_for_wp()
                    bl+=bnr
        # only use the best for a given word
        best_b=max(bl,key=lambda b:b.score())
        return [best_b]

    def get_bs_for_wp(s):
        if len(s.wp)==0:
            return [s]
        bl=[]
        for ir in -1,0,1:
            for jr in -1,0,1:
                i=s.wx+ir
                j=s.wy+jr
                if (i,j) not in s.wu and (s.d[i*s.l+j]==s.wp[0] or (i==s.x and j==s.y)):
                    bn=s.copy()
                    assert bn.d[i*bn.l+j] in (bn.wp[0],' ')
                    #add/owerwrite char
                    bn.d[i*bn.l+j]=bn.wp[0]
                    bn.wp=bn.wp[1:]
                    bn.wu+=[(i,j)]
                    bn.wx,bn.wy=i,j
                    if (i==bn.x and j==bn.y):
                        spiraling=not (bn.x==bn.l//2 and bn.l//2+nonspiral_length>bn.y>=bn.l//2 )
                        #turn
                        nd=bn.dir*1j
                        if bn.d[int(bn.x+nd.real)*bn.l+int(bn.y+nd.imag)]==' ' and spiraling:
                            bn.dir=nd
                        #move
                        bn.x+=bn.dir.real
                        bn.y+=bn.dir.imag

                    #add bs from new state
                    bl+=bn.get_bs_for_wp()
        return bl

    def __repr__(s):
        #borders
        x1,x2,y1,y2=s.l,0,s.l,0
        for i in range(s.l):
            for j in range(s.l):
                if s.d[i*s.l+j]!=' ':
                    x1=min(i,x1)
                    x2=max(i,x2)
                    y1=min(j,y1)
                    y2=max(j,y2)
        r=''
        for i in range(x1,x2+1):
            for j in range(y1,y2+1):
                r+=s.d[i*s.l+j] if s.d[i*s.l+j]!=' ' else 'X'
            r+='\n'
        return r

progress_info=False # toggle to print progress info

allws=[w.rstrip() for w in sys.stdin.readlines()]
allws=allws[:]
allwlen=sum([len(w) for w in allws])
max_nonspiral_length=16
best_score=allwlen*2+1 # maxint
best_b=None

for nonspiral_length in range(1,max_nonspiral_length+1,3):

    length=int(allwlen**0.5)+nonspiral_length*2+5 #size with generous padding

    bl=[b(length,allws)]

    for wc in range(len(allws)):
        bln=[]
        for be in bl:
            bln+=be.get_next_bs()

        bln.sort(key=lambda b:b.score(),reverse=True)
        bl=bln[:10]
        if progress_info:
            print(wc,end=' ')
            sys.stdout.flush()
        #print(bl[0].score(),wc)

    real_score=len(repr(bl[0]))-repr(bl[0]).count('\n')
    #print(bl[0])
    if progress_info:
        print()
        print(nonspiral_length,'score =',real_score)

    if real_score<best_score:
        best_b=bl[0]
        best_score=real_score

if progress_info:
    print()
print(best_b)
if progress_info:
    print('score =',best_score)

```
> 3 votes

---
Tags: code-challenge, compression, boggle
---


# Question
Title: Copy Memory Only Using Store And Subtraction
A peer of mine approached me with this challenge and I wasn't able to come up with an elegant solution. After discussing my approach, we began to wonder what the people at Code Golf would come up with.

# Given

* A processor that implements only two instructions:

1. STO \<register\>, \<address\> (`store` from this `register` to this `address`)
    2. SUB \<register\>, \<address\> (`subtract` the value at this `address` from this `register`)
* It also only contains `2`, `32-bit` registers: `A` and `B`
* As well as `2`, `32-bit` RAM address: `0x00` and `0x01`
* The values of `A` and `B` are unknown

# Challenge

Write a program to `copy` RAM address `0x00` into `0x01` optimised to use the `fewest` number of instructions possible.

# Answer
> 6 votes
Assuming registers are signed and/or wrapping

8 instructions:

```
STO A 0x01
SUB A 0x01
SUB A 0x00
STO A 0x00
SUB A 0x00
SUB A 0x00
STO A 0x00
STO A 0x01

```

A 7-instruction version provided by lrn:

```
STO A 0x01
SUB A 0x01
SUB A 0x00
STO A 0x01
SUB A 0x01
SUB A 0x01
STO A 0x01

```

---
Tags: atomic-code-golf, assembly
---


title: Is My Graph Planar?

text:
# Question
Title: Is My Graph Planar?
Your task is to determine whether a graph is planar.

A graph is planar if it can embedded in the plane, or in other words if it can be drawn without any crossing edges.

**Input:** You will be given an undirected graph in your choice of the following formats:

* Edge list, e.g. `[(0, 1), (0, 2), (0, 3)]`
* Adjacency map, e.g. `{0: [1, 2, 3], 1:[0], 2:[0], 3:[0]}`
* Adjacent matrix, e.g. `[[0, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]`

Node names may be numbers, strings or similar, but your chosen format must be able to support an an arbitrary graph. No putting code in the node names. There will be no self loops.

Standard choice of input, including STDIN, command line arguments and function arguments.

**Output:** You should return a specific output for all planar graphs, and a different specific output for all nonplanar graphs.

Standard choice of output, including STDOUT, function return value.

**Examples:**

Planar:

```
[]
[(0,1), (0,2), (0,3), (0,4), (0,5), (0,6)]
[(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)]
[(0,2), (0,3), (0,4), (0,5), (1,2), (1,3), (1,4), (1,5), (2,3),
 (2,5), (3,4), (4,5)]

```

Nonplanar:

```
[(0,1), (0,2), (0,3), (0,4), (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)]
[(0,3), (0,4), (0,5), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5)]
[(0,3), (0,4), (0,6), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (5,6),
 (7,8), (8,9), (7,9)]

```

Any function which explicitly performs planarity testing or otherwise specifically references planar embeddings is disallowed.

This is code golf. May the shortest code win.

# Answer
# Mathematica, 201 bytes

```
f@g_:=EdgeCount@g<9||!(h=g~IsomorphicGraphQ~CompleteGraph@#&)@5&&!h@{3,3}&&And@@(f@EdgeDelete[g,#]&&f@EdgeContract[g,#]&/@EdgeList@g);And@@(f@Subgraph[g,#]&/@ConnectedComponents[g=Graph[#<->#2&@@@#]])&

```

This evaluates to an unnamed function, which takes an edge list like

```
{{0, 3}, {0, 4}, {0, 5}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}}

```

This is a horribly inefficient recursive approach based on Wagner's theorem:

> A finite graph is planar if and only if it does not have *K5* or *K3,3* as a minor.

Here, *K5* is the complete graph with 5 vertices, and *K3,3* is the complete bipartite graph with 3 vertices in each group. A graph *A* is a minor of graph *B* if it can be obtained from *B* by a sequence of edge deletions and edge contractions.

So this code just checks if the graph is isomorphic to *K5* or *K3,3* and if not then it recursively calls itself once for every possible edge deletion or contraction.

The catch is that deleting or contracting edges in one component of an unconnected graph will never get rid of all the vertices there, so we'll never find the desired isomorphisms. Hence, we apply this search to each connected component of the input graph separately.

This works very fast for the given inputs, but if you add a few more edges it will quickly take catastrophically long (and take a lot of memory as well).

Here is an indented version of `f` (the unnamed function after it just generates a graph object from the input:

```
f@g_ :=
  EdgeCount@g < 9 ||
  ! (h = g~IsomorphicGraphQ~CompleteGraph@# &)@5 &&
  ! h@{3, 3} &&
  And @@ (f@EdgeDelete[g, #] && f@EdgeContract[g, #] & /@ EdgeList@g)

```

And this is the unnamed function which converts the input to a graph and calls `f` for each connected component:

```
And @@ (
  f @ Subgraph[g, #] & /@ ConnectedComponents[
    g=Graph[# <-> #2 & @@@ #]
  ]
)&

```

I can save a couple of bytes by changing the termination condition from `EdgeCount@g<9` to `g==Graph@{}`, but that will blow up the runtime significantly. The second test case then takes 30 seconds, and the last one hasn't completed yet.
> 14 votes

---
Tags: code-golf, graph-theory
---


title: Solving a Jigsaw Puzzle!

text:
# Question
Title: Solving a Jigsaw Puzzle!
I've just bought a new jigsaw puzzle but, as a programmer, I'm too lazy to do it by myself. So I've devised a way to encode the pieces, and now I need a way to solve the puzzle itself.

## Challenge

A puzzle piece will have from 2 to 4 connecting corners, defined by a letter; and a color, defined by a number.

```
  a
B 1 c
  D

a 2 b
  C

3 A
b

```

The challenge is to build the puzzle from the pieces according to the next rules:

* Two pieces may only be adjacent if they have a matching connection in the corner where they are adjacent. If a piece doesn't have a connection in one of the sides, that side is a corner and can't be connected to another piece.
* Lowercase letters are considered indents and uppercase letters are considered outdents. An uppercase letter connects with its lowercase pair.
* The color of 4-adjacent pieces will differ at most by 1.
* Every piece can and has to be used exactly once.

## Input

Your program will receive a randomized list of the pieces, separated with newlines, as seen in the examples. The input pieces are in the right direction: you don't need to rotate them (there is a bonus for inputs with rotated pieces, see below).

## Output

Your program should output a solution to the puzzle, with columns separated by blank space (space or tab are okay) and rows by newlines. It might not be unique, but only one possible solution is required.

```
1 2 3 4 3 4 5 4
1 1 2 3 4 4 4 5
2 1 1 2 3 4 5 6
3 2 2 3 4 5 6 7
2 3 3 4 5 6 7 8
3 4 4 5 6 7 8 9
3 4 5 6 7 8 9 10

```

## Scoring

The shortest answer in bytes wins.

### Bonus

The generator script provides options to randomize the rotation of the pieces, but since it may become more complex, a 50% bonus is awarded to whoever implements it (that is, your-byte-count * 0.5).

For that case, assume all the tiles in the input will have a randomized rotation, except the first one, which will have the rotation of the original grid (so as to avoid having at least 4 different solutions).

## Test Cases

Test cases can be obtained using the following ruby scripts:

https://gist.github.com/rcrmn/2ba23845d65649c82ca8

The first one generates the solution grid. The second one generates the puzzle pieces from it. Note that they have optional arguments, described in each ruby file.

Following is an example. It's here because I made it by hand before writing the generator and I got attached to it:

http://pastebin.com/PA9wZHma

This test case should output:

```
1 2 3 4
2 3 4 5
3 4 5 6

```

As usual, common loopholes are not permitted.

Good luck!

# Answer
> 1 votes
# Ruby, 1220

Wow that was something... I didn't think it would take THAT much to make this, but hey, only way to learn was try it. It's clear now why there weren't any answers to the question...

Well, I'm sure this is golfable, but It's been a whole job only to make it. Following is golfed code and then ungolfed with some explanations:

```
e=[[]]
while(a=gets)
if(a=a.chomp)==""
e.push []
else
e.last.push a.chomp
end
end
e.keep_if{|p|p!=[]}
e.map!{|p|m={}
t=p[0].strip
if t.length==1
m[:t]=t
l=p[1].split" "
b=p[2]
else
m[:t]=nil
l=t.split" "
b=p[1]
end
x=l[0]=~/\d/
m.merge!({l: !x ? l[0]:nil,v:(x ? l[0]:l[1]).to_i,r:x ? l[1]:l[2]})
m[:b]=b.nil? ? nil:b.strip
m}
w=e.select{|p|p[:t].nil?}.length
h=e.length/w
def c(j,p,l)
x=l[0]
y=l[1]
(x==0&&p[:l].nil?||x!=0&&(j[x-1][y].nil?||j[x-1][y][:r].swapcase==p[:l]&&(j[x-1][y][:v]-p[:v]).abs<2))&&(x==j.length-1&&p[:r].nil?||x!=j.length-1&&(j[x+1][y].nil?||j[x+1][y][:l].swapcase==p[:r]&&(j[x+1][y][:v]-p[:v]).abs<2))&&(y==0&&p[:t].nil?||y!=0&&(j[x][y-1].nil?||j[x][y-1][:b].swapcase==p[:t]&&(j[x][y-1][:v]-p[:v]).abs<2))&&(y==j[0].length-1&&p[:b].nil?||y!=j[0].length-1&&(j[x][y+1].nil?||j[x][y+1][:t].swapcase==p[:b]&&(j[x][y+1][:v]-p[:v]).abs<2))
end
def d(j,q,l)
f=[false,[]]
q.each_index{|i|p=q[i]
if c j,p,l
r=q.dup
r.delete_at i
j2=j.dup
j2[l[0]][l[1]] = p
if r.length==0
f = [true,j2]
break
else
n=l[0]+1
l2=[n%j.length, l[1]+n/j.length]
f = d(j2,r,l2)
break if f[0]
end
end}
f
end
j=[]
w.times{j.push [];h.times{j.last.push nil}}
s=d(j,e,[0,0])
h.times{|y|w.times{|x|print s[1][x][y][:v].to_s+" "}
puts''}

```

Ungolfed:

```
pieces=[[]]
while (a=gets) # Read the input and separate by pieces when finding an empty line
  if (a=a.chomp)==""
    pieces.push []
  else
    pieces.last.push a.chomp
  end
end
pieces.keep_if{|p|p!=[]} # Remove possible empty pieces
pieces.map!{|p| # Parse each piece
  m={}
  t=p[0].strip
  if t.length==1
    m[:t]=t
    l=p[1].split" "
    b=p[2]
  else
    m[:t]=nil
    l=t.split" "
    b=p[1]
  end
  x=l[0]=~/\d/
  m.merge!({l: !x ? l[0]:nil,v:(x ? l[0]:l[1]).to_i,r:x ? l[1]:l[2]})
  m[:b]=b.nil? ? nil:b.strip
  m
}
w=pieces.select{|p|p[:t].nil?}.length
h=pieces.length/w

def fits(j,p,l) # This function determines if a piece fits in an empty spot
  (l[0]==0&&p[:l].nil? || l[0]!=0 && (j[l[0]-1][l[1]].nil? || j[l[0]-1][l[1]][:r].swapcase==p[:l] && (j[l[0]-1][l[1]][:v]-p[:v]).abs<2)) &&
    (l[0]==j.length-1&&p[:r].nil? || l[0]!=j.length-1 && (j[l[0]+1][l[1]].nil? || j[l[0]+1][l[1]][:l].swapcase==p[:r] && (j[l[0]+1][l[1]][:v]-p[:v]).abs<2)) &&
    (l[1]==0&&p[:t].nil? || l[1]!=0 && (j[l[0]][l[1]-1].nil? || j[l[0]][l[1]-1][:b].swapcase==p[:t] && (j[l[0]][l[1]-1][:v]-p[:v]).abs<2)) &&
    (l[1]==j[0].length-1&&p[:b].nil? || l[1]!=j[0].length-1 && (j[l[0]][l[1]+1].nil? || j[l[0]][l[1]+1][:t].swapcase==p[:b] && (j[l[0]][l[1]+1][:v]-p[:v]).abs<2))
end

def rec(j,pl,l) # Recursive function to try every piece at every position it can fit
  found = [false,[]]
  pl.each_index{|i|
    p=pl[i]
    if fits(j,p,l) # Try the piece in the spot
      pl2=pl.dup
      pl2.delete_at i
      j2=j.dup
      j2[l[0]][l[1]] = p
      if pl2.length==0 # If we have spent all the pieces, then we have a complete puzzle
        found = [true,j2]
        break
      else             # Keep recurring until we use up all the pieces
        n=l[0]+1
        l2=[n%j.length, l[1]+n/j.length]
        found = rec(j2,pl2,l2)
        break if found[0]
      end
    end
  }
  found
end

j=[]
w.times { j.push []; h.times { j.last.push nil }}
solved = rec(j, pieces, [0,0])
h.times{|y|
  w.times{|x|
    print solved[1][x][y][:v].to_s + " "
  }
  puts ''
}

```

---
Tags: code-golf, puzzle-solver
---