答:
Boundary Finding Bot, Java 1.5+, 124 + 37 + 206 + 324 + 248 + 223 = 1172 steps

This bot attempts to locate and follow the boundaries of the maze knowing that the cheese will always be located on the boundary.

It does this by updating its internal view of the maze and constructing current candidates for the north, south, east and west boundary walls.

A* path finding is performed for any unexplored cells in these walls and the shortest path is chosen to follow. However only the candidate boundary walls that do not contain any blank spaces are able to be the "true" boundary wall and thus those that do contain blank cells are not considered for path finding. Unexplored cells within a path are given less desirable score with consecutive unexplored cells compounding the undesirability.

In this latest edit, the bot now has a negative weight to cells already visited. This gives a slight improvement.

A fail safe movement selection mechanism exists that ensures valid movement is chosen in the event that no paths are able to be found.

Note that this implementation is quite inefficient and can take many seconds to solve a maze in the worst case.

Deterministic.  Run with java BoundryFindingBot

import java.io.IOException;
import java.io.InputStream;

public class BoundryFindingBot {
    private static final char[] DIRECTION = {'n','e','s','w'};
    private static final int MAP_SIZE = 102;
    private static final int PATH_FINDING_MAX_STEPS = 50000;
    private static final int[][] offsets = new int[][]{{0,-1},{1,0},{0,1},{-1,0}};

    public static void main(String[] args) throws Exception
    {
        char[][] map = new char[MAP_SIZE][MAP_SIZE];
        int[][] visitCount = new int[MAP_SIZE][MAP_SIZE];
        int mx=MAP_SIZE/2-1, my=MAP_SIZE/2-1;
        int direction=0;

        String line=readLine(System.in);
        out:
        while (line!=null && !"0000".equals(line))
        {
            // update map with new information
            for (int i=0;i<4;i++)
            {
                map[mx+offsets[i][0]][my+offsets[i][1]] = line.charAt(i);

                // immediately move toward cheese if found.
                if (line.charAt(i) == '+')
                {
                    System.out.println(DIRECTION[i]);
                    break out;
                }
            }

            // determine the current boundary walls information
            int currentNorthWallY=-1,currentSouthWallY=-1,currentWestWallX=-1,currentEastWallX=-1;
            boolean currentNorthWallHasBlanks=false,currentSouthWallHasBlanks=false,currentEastWallHasBlanks=false,currentWestWallHasBlanks=false;
            for (int y=0;y<MAP_SIZE;y++)
            {
                for (int x=0;x<MAP_SIZE;x++)
                {
                    if (map[x][y]!=0)
                    {
                        if (currentNorthWallY > -1)
                        {
                            if (currentSouthWallY !=y)
                            {
                                currentSouthWallHasBlanks = false;
                            }
                            currentSouthWallY=y;
                            currentSouthWallHasBlanks|=map[x][y]==' ';
                        }
                        else
                        {
                            currentNorthWallY=y;
                        }

                        if (currentNorthWallY == y)
                        {
                            currentNorthWallHasBlanks|=map[x][y]==' ';
                        }

                    }
                }
            }
            for (int x=0;x<MAP_SIZE;x++)
            {
                for (int y=0;y<MAP_SIZE;y++)
                {
                    if (map[x][y]!=0)
                    {

                        if (currentWestWallX > -1)
                        {
                            if (currentEastWallX !=x)
                            {
                                currentEastWallHasBlanks = false;
                            }
                            currentEastWallX=x;
                            currentEastWallHasBlanks|=map[x][y]==' ';
                        }
                        else
                        {
                            currentWestWallX=x;
                        }

                        if (currentWestWallX == x)
                        {
                            currentWestWallHasBlanks|=map[x][y]==' ';
                        }

                    }
                }
            }

            int closestUnvisitedWallCellResult =0xFFFFFF;

            // attempt to find paths to undiscovered cells in the current north wall, setting the shortest path if shortest of any path
            if (!currentNorthWallHasBlanks)
            {
                for (int x=currentWestWallX;x<=currentEastWallX;x++)
                {
                    if (map[x][currentNorthWallY] == 0)
                    {
                        int result = pathFind(mx, my, x, currentNorthWallY, map,visitCount,currentWestWallX,currentNorthWallY,currentEastWallX,currentSouthWallY);
                        if ((result &0xFFFFFF) <(closestUnvisitedWallCellResult &0xFFFFFF))
                        {
                            closestUnvisitedWallCellResult = result;
                        }
                    }

                }
            }

            // attempt to find paths to undiscovered cells in the current south wall, setting the shortest path if shortest of any path
            if (!currentSouthWallHasBlanks)
            {
                for (int x=currentWestWallX;x<=currentEastWallX;x++)
                {
                    if (map[x][currentSouthWallY] == 0)
                    {
                        int result = pathFind(mx, my, x, currentSouthWallY, map,visitCount,currentWestWallX,currentNorthWallY,currentEastWallX,currentSouthWallY);
                        if ((result &0xFFFFFF) <(closestUnvisitedWallCellResult &0xFFFFFF))
                        {
                            closestUnvisitedWallCellResult = result;
                        }
                    }

                }
            }

            // attempt to find paths to undiscovered cells in the current east wall, setting the shortest path if shortest of any path
            if (!currentEastWallHasBlanks)
            {
                for (int y=currentNorthWallY;y<=currentSouthWallY;y++)
                {
                    if (map[currentEastWallX][y] == 0)
                    {
                        int result = pathFind(mx, my, currentEastWallX, y, map,visitCount,currentWestWallX,currentNorthWallY,currentEastWallX,currentSouthWallY);
                        if ((result &0xFFFFFF) <(closestUnvisitedWallCellResult &0xFFFFFF))
                        {
                            closestUnvisitedWallCellResult = result;
                        }
                    }

                }
            }

            // attempt to find paths to undiscovered cells in the current west wall, setting the shortest path if shortest of any path
            if (!currentWestWallHasBlanks)
            {
                for (int y=currentNorthWallY;y<=currentSouthWallY;y++)
                {
                    if (map[currentWestWallX][y] == 0 )
                    {
                        int result = pathFind(mx, my, currentWestWallX, y, map,visitCount,currentWestWallX,currentNorthWallY,currentEastWallX,currentSouthWallY);
                        if ((result &0xFFFFFF) <(closestUnvisitedWallCellResult &0xFFFFFF))
                        {
                            closestUnvisitedWallCellResult = result;
                        }
                    }
                }
            }

            // fail-safe if we are unable to find a path to a wall (i.e. initial game frame or all current boundary walls are known to have blanks and thus
            // not wall to head for. Simply tries to go north if possible or failing that try to head east, south, west consecutively
            if (closestUnvisitedWallCellResult == 0xFFFFFF)
            {
                for (int i=0;i<4;i++)
                {
                    if (map[mx+offsets[i][0]][my+offsets[i][1]] == ' ')
                    {
                        direction = i;
                        break;
                    }
                }
            }
            else
            {
                direction = closestUnvisitedWallCellResult >> 24;
            }

            mx +=offsets[direction][0];
            my +=offsets[direction][1];
            visitCount[mx][my]+=5;

            System.out.println(DIRECTION[direction]);

//// uncomment to bot's view of maze solving
//          System.err.println();
//          for (int y=currentNorthWallY;y<=currentSouthWallY;y++)
//          {
//              for (int x=currentWestWallX;x<=currentEastWallX;x++)
//              {
//                  if (x==mx && y==my)
//                  {
//                      System.err.print("O");
//                  }
//                  else
//                  {
//                      System.err.print(map[x][y]);
//                  }
//              }
//              System.err.println();
//          }
            line=readLine(System.in);
        }
        System.err.println("Exited");
    }

/**
 * returns a result that is the combination of movement direction and path length of a path found from the given start position to the target
 * position for cells within the given bounding box. Only empty cells and unexplored cells are traversable. Sequential cells of unexplored cells
 * are given increasing magnitude negative score to reduce desirability.
 */
static int pathFind(int startX, int startY, int targetX,int targetY,char[][] map,int[][] visitCount,int boundMinX,int boundMinY,int boundMaxX,int boundMaxY)
{
    // A*
    if (!(startX==targetX && startY==targetY))
    {

        int[] tileX = new int[PATH_FINDING_MAX_STEPS];
        int[] tileY = new int[PATH_FINDING_MAX_STEPS];
         int[] fscore = new int[PATH_FINDING_MAX_STEPS];
         int[] gscore = new int[PATH_FINDING_MAX_STEPS];
         int[] openList = new int[PATH_FINDING_MAX_STEPS];
         int[] tileParent = new int[PATH_FINDING_MAX_STEPS];
         int[] unexploredCellRun = new int[PATH_FINDING_MAX_STEPS];
         int[][] tileIsClosed = new int[MAP_SIZE][MAP_SIZE];
         int currentIndex = -1;

        int openListSize=1;
        int tileId=1;

        tileX[0]=targetX;
        tileY[0]=targetY;
        fscore[0]=1;
        gscore[0]=1;

        do
        {
          int currentBestIndex=-1;
          int currentBestScore=Integer.MAX_VALUE;
          //  Look for the lowest F cost square on the open list
          for (int ii=0;ii<openListSize;ii++)
          {
            if (fscore[openList[ii]]<currentBestScore)
            {
              currentBestScore=fscore[openList[ii]];
              currentBestIndex=ii;
            }
          }
          if (currentBestIndex==-1)
          {
            break;
          }
          currentIndex=openList[currentBestIndex];
          int currentTileX=tileX[currentIndex];
          int currentTileY=tileY[currentIndex];

          // found path
          if (startX==currentTileX && startY==currentTileY)
          {
            break;
          }

          // if not in closed list
          if (tileIsClosed[currentTileX][currentTileY]==0)
          {
                // Switch it to the closed list.
                tileIsClosed[currentTileX][currentTileY]=1;
                // remove from openlist
                openList[currentBestIndex]=openList[--openListSize];

                // add neigbours to the open list if necessary
                for (int i=0;i<4;i++)
                {

                        int surroundingCurrentTileX=currentTileX+offsets[i][0];
                        int surroundingCurrentTileY=currentTileY+offsets[i][1];
                        if (surroundingCurrentTileX>=boundMinX-1 && surroundingCurrentTileX<=boundMaxX+1 &&
                            surroundingCurrentTileY>=boundMinY-1 && surroundingCurrentTileY<=boundMaxY+1 )
                        {
                          tileX[tileId]=surroundingCurrentTileX;
                          tileY[tileId]=surroundingCurrentTileY;
                          if (map[surroundingCurrentTileX][surroundingCurrentTileY]==0)
                          {
                              unexploredCellRun[tileId]=0;
                          }
                          else if (map[surroundingCurrentTileX][surroundingCurrentTileY]=='!')
                          {
                              continue;
                          }
                          else
                          {
                              unexploredCellRun[tileId]=unexploredCellRun[currentIndex]+1;
                          }
                          int surroundingCurrentGscore=gscore[currentIndex]+visitCount[surroundingCurrentTileX][surroundingCurrentTileY]+1+((int) (unexploredCellRun[tileId]*10));
                          gscore[tileId]=surroundingCurrentGscore;
                          fscore[tileId]=surroundingCurrentGscore+Math.abs( surroundingCurrentTileX-startX)+Math.abs( surroundingCurrentTileY-startY);
                          tileParent[tileId]=currentIndex;
                          openList[openListSize++]=tileId++;
                     }
                }
          }
          else
          {
          // remove from openlist
          openList[currentBestIndex]=openList[--openListSize];
          }
        } while(true);

        if (tileX[tileParent[currentIndex]]-startX<0) return (3 <<24) + currentIndex;
        else if (tileX[tileParent[currentIndex]]-startX>0) return (1 <<24) + currentIndex;
        else if (tileY[tileParent[currentIndex]]-startY<0) return (0 <<24) + currentIndex;
        else if (tileY[tileParent[currentIndex]]-startY>0) return (2 <<24) + currentIndex;
    }
    throw new RuntimeException("Path finding failed");
 }

    /**
     * Reads a line of text from the input stream. Blocks until a new line character is read.
     * NOTE: This method should be used in favor of BufferedReader.readLine(...) as BufferedReader buffers data before performing
     * text line tokenization. This means that BufferedReader.readLine() will block until many game frames have been received.
     * @param in a InputStream, nominally System.in
     * @return a line of text or null if end of stream.
     * @throws IOException
     */
    private static String readLine(InputStream in) throws IOException
    {
       StringBuilder sb = new StringBuilder();
       int readByte = in.read();
       while (readByte>-1 && readByte!= '\n')
       {
          sb.append((char) readByte);
          readByte = in.read();
       }
       return readByte==-1?null:sb.toString();
    }

}
```

Title: Find the Cheese

Body:
Update: There are 6 mazes. They are included in the controller. There is a tar.gz of the mazes and their .bmp files here (dropbox). There is also a utility for making more mazes at that link (the maze_4.txt file is incorrect in archive). At this point, please feel free to run your own entry and update your score. Details on how to do so are included at the bottom. If you have questions or trouble, please ping me in chat.

You're a mouse. You're in a maze. Find the cheese.

Concept

You are in a maze that exists on a rectangular grid. Each space of the grid contains one of several things:

! - An impassable wall

  - An empty space, which is traversable

O - You, the mouse

+ - The cheese, your goal

Please use the same characters so that I do not have to modify the controller.

On each turn, you will be given the tiles that are North, South, East, and West of your current position. You must then output the direction that you wish to travel. You win when you get to the cheese. Fewer steps is better.

Input

You will be given input through stdin in the following fashion: nesw, where each letter represents the tile at that compass point. For example, if the current state looks like

```<code>  !          <--- Wall
 !O          <--- You
  +          <--- Cheese
</code>```

then you will be given the string ! +!.

At the end of the game, the controller will send you a string of four zeroes: 0000. Upon receiving this string, your program should terminate. No other input given will contain the 0 character.

Please ignore all other inputs.

Output

You are to output one letter n, s, e, or w, to indicate which direction you want to travel, followed by a new line character.

Scoring

Your score on each test is the number of steps it takes you to find the cheese.

Your overall score will be the sum of your average score per maze across a battery of mazes of variable sizes, all of which will fit inside a square of length 50.

For example, if it takes your bot 100 moves to complete each of the 6 mazes, then your score is 600.

If your bot is not deterministic, please try each maze 10 times and use average as the score for that maze. Your final score will be the sum of all the averages.

Rules

Each maze will fit inside a 50x50 square.

Each maze will have at least one valid path from start to cheese.

Each maze will be entirely walled in, except that the cheese will always be on the outer wall so that it essentially serves as an exit to the maze.

If you run into a wall, your submission is disqualified.

If your submission takes too long (as determined by me, as I start testing), it will be disqualified. This is in large part to prevent infinite loops. The soft limit will be one minute per maze, although I reserve the right to change this at any time in either direction.

Entries need not be deterministic, but if you are too random, you will likely be disqualified by the above point.

At some point, the battery of mazes will be released, future answers may not optimize toward them, and they are subject to change.

Submissions:

Your submission is a full program that takes input via stdin and output via stdout. This is important because the submission will be interacting with the maze controller. I'm not going to ban languages that are not freely available, but know that someone else will have to offer their time to run the tests if I do not have access to the language.

Please include instructions on how to run your submission.

Please state whether your submission is deterministic or not, so that I know whether I need to run it multiple times.

Test Mazes

In the test mazes, . characters outline the shortest route to the cheese. They are the same as the  (space) character. They are not visible to your submission. The controller replaces them with spaces.

```<code>!!!!!!!!+!
!O..!....!
! !.!.! !!
! !.!.!  !
! !.!.!! !
!!!.!.!! !
!  .!.! !!
!!!...   !
!!!!!!!!!!
</code>```

31x31 test maze. Shamelessly stolen.

```<code> !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 ! O...!.......!   !  .....!.....!           !             !   !
 !!!!!.!.! !!!.! !!! !.!!!.!.!!!.!!!!!!! !!! !!!!!!!!! !!! ! ! !
 !   !...!   !.!     !.! !.!.! !.!       !   !         !   ! ! !
 ! !!!!! !!! !.!!!!!!!.! !.!.! !.! !!!!!!! !!! ! !!!!!!! !!! ! !
 !     !     !.........! !...!...!     !   !   ! !     !   ! ! !
 ! !!! !!!!!!!!!!!!!!!!! !!!!!.!!! !!! !!! ! ! !!! !!! !!! !!! !
 !   !         !     !   !.....!     !   ! ! ! !     !   !   ! !
 !!!!!!!!!!! ! ! !!! !!! !.!!!!!!!!!!!!! ! !!! ! !!!!!!! !!! ! !
 !           !   !       !.!             !   !     !     !     !
 ! !!!!!!! !!!!!!! !!!!!!!.! !!!!!!!!!!!!!!! !!!!!!! !!!!!!!!!!!
 ! !     ! !   !     !...!.!           !   !       ! !         !
 ! !!! ! ! ! ! !!!!!!!.!.!.! !!!!!!!!! ! ! !!!!!!! ! ! !!!!!!! !
 !   ! !   ! !       !.!...! !         ! !       ! ! !   !   ! !
 !!! ! !!!!! !!!!!!! !.!!!!!!! !!!!!!!!! !!! !!!!! ! !!! ! !!! !
 !   !   ! ! !       !...!     !   !     ! !           ! !   ! !
 ! !!!!! ! ! ! !!!!!!!!!.! !!!!! !!! !!!!! !!!!!!!!!!! ! ! ! ! !
 ! !       ! !   !   !...! !       ! !       !   !     ! ! ! ! !
 ! !!!!!!!!! !!! ! ! !.!!! !!!!!!! ! !!!!!!! ! ! !!!!!!! !!! ! !
 !             !   ! !...!       ! !     !   ! !             ! !
 !!!!!!!!!!!!!!!!!!! !!!.!!!!!!! ! !!!!! ! !!! !!!!!!!!!!!!!!! !
 !               !   !...!       !         !   !     !   !     !
 ! !!!!!!!!!!!!! ! ! !.!!! !!!!!!! !!!!!!!!! !!! !!! !!! ! !!! !
 ! !   !       !   ! !.! !     ! ! ! !     !     !   !   !   ! !
 ! ! ! !!!!! !!!!!!! !.! ! !!! ! ! ! ! !!! !!!!!!! !!! !!!!! !!!
 !   ! !   !       ! !.!     ! !     ! ! !     !   !       !   !
 !!!!! ! ! !!! !!! ! !.!!!!!!! !!!!!!! ! ! !!! ! !!!!!!!!! !!! !
 !     ! !   !   !   !.......!       ! ! ! !   !   !         ! !
 ! !!!!! !!! !!! !!!!!!!!!!!.!!!!!!! ! ! ! !!!!!!! ! !!!!!!! ! !
 !         ! !           !...!       ! ! !     !   ! !       ! !
 !!!!!!!!!!! !!!!!!!!!!! !.!!! !!!!!!! ! !!!!! ! !!! !!!!!!!!! !
 !         !     !     ! !.!       !   !     ! !     !         !
 ! !!!!!!! !!!!! ! !!! !!!.!!!!!!! ! !!!!! ! ! !!!!! ! !!!!!!!!!
 ! !     !     !   ! !   !.......! !       ! !       !         !
 ! ! !!! !!!!! ! !!! !!! !!!!!!!.! !!!!!!!!! !!!!!!!!!!!!!!!!! !
 !     !     ! !   !   ! !     !.!       !   ! !     !         !
 !!!!!!!!!!! ! !!! !!! ! ! ! !!!.! ! !!!!! !!! ! !!! ! !!!!!!! !
 !           ! !       !   ! !...! !       !   ! ! ! !     !   !
 ! !!!!!!!!!!! !!!!!!!!!!!!! !.!!! !!!!!!!!!!! ! ! ! ! !!! ! !!!
 !       !   !             ! !.! !   !         ! !   !   ! ! ! !
 !!!!!!! !!! !!!!!!!!!!!!! ! !.! !!! ! !!!!!!! ! !!! !!!!! ! ! !
 !       !         !     ! ! !.!   !   !     ! !   !       !   !
 ! !!!!!!! !!!!!!! ! !!!!! ! !.!!! !!!!!!! ! ! !!! !!!!!!!!!!!!!
 !   !         ! !   !       !.!           ! !   !             !
 ! ! ! !!!!!!! ! ! !!! !!!!!!!.! !!!!!!!!!!! ! !!!!!!!!!!!!!!! !
 ! ! ! !     ! !   !   ! !.....!   !   !     ! !...............!
 ! ! !!! !!! ! !!!!! !!! !.!!!!! ! ! ! !!!!!!! !.!!!!!!!!!!!!!.!
 ! !   !   ! !   !       !...!   !   !         !.!         !...!
 !!!!! !!! ! !!! ! !!!!!!!!!.!!!!!!! !!!!!!!!!!!.!!!!! !!!!!.!!!
 !     !   !   !   !       !.......!       !...!.....!      .! !
 ! !!!!! !!!!! !!!!! !!!!! !!!!!!!.!!!!!!!!!.!.!!!!!.!!!!!!!.! !
 !           !     ! !   !   !   !...........!...!...!.....!...!
 ! !!!!!!!!! !!!!! ! !!! ! !!! ! !!!!!!!!!!!!!!!.!.!!!.!!!.!!!.!
 ! !     !       ! !     !     !     !         !.!.....  !...!.!
 !!! !!! !!!!!!!!! !!!!! !!!!!!!!! ! !!!!!!! !!!.! !!!!!!!!!.!.!
 !   !     !   !   !   ! !       ! !         !...! !.........!.!
 ! !!!!!!! ! ! ! ! !!! ! !!!!!!! ! !!!!!!!!! !.!!!!!.!!!!!!!!!.!
 !       !   !   ! !   !         !   ! !   ! !.!.....!       !.!
 ! !!!!! !!!!!!!!! ! !!!!!!!!!!! !!! ! ! ! ! !.!.!!!!! !!!!! !.!
 ! !     !           !         ! ! ! !   !   !.!...!   !     !.!
 ! ! !!!!!!!!!!!!!!!!! !!! !!!!! ! ! !!!!!!!!!.!!!.! !!!!!!!!!.!
 ! !                     !         !          .....!          .!
 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!+!
</code>```

Controller

The controller is in Rust (1.11 Nightly)

    type Maze = Vec<Vec<char>>;

fn str_to_maze(input: &str) -> Result<Maze,i32> {
    let mut maze: Vec<Vec<char>> = vec![ vec![] ];
    let mut row: Vec<char> = vec![];

    for c in input.chars() {
        if c == '!' || c == '+' || c == 'O'  || c == ' ' {
            row.push(c);
        }
        else if c =='.' {
            row.push(' ');
        }
        else if c == '#' {
            maze.push(row);
            row = vec![];
        }
        else if c =='\0' {
            break;
        }
        else {
            println!("Bad character in maze: {}, exiting.", c);
            return Err(1);
        }
    }
    return Ok(maze);
}

fn display_maze(maze: &Maze, position: [usize;2]) {
    for y in 0..maze.len() {
        for x in 0..maze[y].len() {
            if [x,y] == position {
                print!("O");
            }
            else if maze[y][x] == '#' {
                println!("\n");
            }
            else {
                print!("{}",maze[y][x]);
            }
        }
        println!("");
    }
    println!("\n");
}

fn get_starting_position(maze: &mut Maze) -> Result<[usize;2],&str> {
    for y in 0..maze.len() {
        for x in 0..maze[y].len() {
            if maze[y][x] == 'O' {
                maze[y][x] = ' ';
                return Ok([x,y]);
            }
        }
    }
    return Err("No mouse found");
}

enum State {
    Continue([char;4]),
    Win,
    Disqualify,
}

fn output(maze: &Maze, position: [usize;2]) -> State {
    let x = position[0];
    let y = position[1];
    if maze[y][x] == '+' {
        return State::Win;
    }
    else if maze[y][x] == '!' {
        return State::Disqualify;
    }

    let n = maze[y-1][x];

    assert!(y+1<maze.len());
    let s = maze[y+1][x];

    let w = maze[y][x-1];

    assert!(x+1<maze[y].len());
    let e = maze[y][x+1];

    return State::Continue([n,e,s,w]);
}

fn get_input() -> char {
    use std::io;
    use std::io::Read;
    let mut buffer: [u8;2] = [0;2];
    io::stdin().read_exact(&mut buffer).unwrap();
    //println!("{:?}", buffer); // to see exactly what the input is
    return buffer[0] as char;
}

fn next_position(current_position: [usize;2], direction: char) -> Result<[usize;2],char> {
    let mut x = current_position[0];
    let mut y = current_position[1];
    if direction == 'n' {
        y -= 1;
    }
    else if direction == 'e' {
        x += 1;
    }
    else if direction == 's' {
        y += 1;
    }
    else if direction == 'w' {
        x -= 1;
    }
    else {
        return Err(direction);
    }
    return Ok([x,y]);
}

fn play(maze: &mut Maze) -> (State, usize) {
    let mut position: [usize;2];
    match get_starting_position(maze) {
        Ok(pos) => position = pos,
        Err(s) => {
            println!("{}",s);
            std::process::exit(2);
        }
    }

    let mut moves = 0;

    loop {

        let state = output(maze, position);

        /* uncomment below to view the maze at each step  */
        //display_maze(&maze, position);
        /* ----------------------------------------------*/

        match state {
            State::Win => {
                //println!("You found the cheese");
                return(State::Win, moves);
            }
            State::Disqualify => {
                //println!("You were disqualified");
                return(State::Disqualify, moves);
            }
            State::Continue(out) => {
                println!("{}{}{}{}",out[0],out[1],out[2],out[3]);
            }
        }
        // only get here with Continue
        let input = get_input();
        moves += 1;
        match next_position(position, input) {
            Err(c) => {
                println!("Invalid input: {}", c as u8);
                return (State::Disqualify, moves);
            }
            Ok(next_pos) => position = next_pos,
        }
    }
}

fn main() {

    let mut arg_counter = 0;
    for argument in std::env::args() {
        if arg_counter != 0 {

            let mut maze = match argument.as_str(){
                "1" => maze_1(),
                "2" => maze_2(),
                "3" => maze_3(),
                "4" => maze_4(),
                "5" => maze_5(),
                "6" => maze_6(),
                _ => {
                    println!("invalid input: {}, breaking", argument);
                    break;
                }

            };

            let game_result = play(&mut maze);

            println!("0000");
            match game_result.0 {
                State::Win => println!("WIN"),
                State::Disqualify => println!("DISQUALIFY"),
                _ => println!("Error"),
            }
            println!("moves: {}", game_result.1 );
        }
        arg_counter += 1;
    }

}

fn maze_1() -> Maze {
    let maze_str = "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#\
                    !O !                    !      !#\
                    !. ! !!!!!!!!!!!!!!!!!! ! !!!!!!#\
                    !. !                    ! !    !#\
                    !. ! !!!!!!!!!!!!!!!!!!!! ! !! !#\
                    !. !...........           ! !!.+#\
                    !. !.!!!!!!!!!.!!!!!!!!!!!!!!!.!#\
                    !.!..!        ...............!.!#\
                    !.!.!! !!!!!!!!!!!!!!!!!!!!!.!.!#\
                    !.!.!! !!!  !               .!.!#\
                    !.!.!! !!!  !!!!!!!!!!!!!!!!.!.!#\
                    !...!! !!!                  .!.!#\
                    ! ! !! !!!                  .!.!#\
                    ! ! !! !!!  !!!!!!!!! !!!!!!.!.!#\
                    ! ! !! !!!  !      !! !     .!.!#\
                    ! ! !! !!!  ! !!!!!!! !     .!.!#\
                    ! ! !! !!!  !      !! !     .!.!#\
                    ! ! !! !!!  !      !! !     .!.!#\
                    ! ! !!   !  !      !! !     .!.!#\
                    ! ! !! ! !  !!!!!! !! !     .!.!#\
                    ! ! !! ! !  !      !! !     ...!#\
                    ! ! !! ! !  !      !! !        !#\
                    ! ! !! ! !  !      !! !      ! !#\
                    ! ! !! ! !  !  !!!!!! !      ! !#\
                    ! ! !! ! !  !      !! !      ! !#\
                    ! !    !    !      !! !      ! !#\
                    ! !!!!!!  !!!!!!!! !! !      ! !#\
                    !                ! !! !      ! !#\
                    ! !!!!!!!!!!! !!!! !! !      ! !#\
                    !                     !      ! !#\
                    ! !!!!!!!! !!!!       !        !#\
                    !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#\
                    ";

    match str_to_maze(&maze_str) {
        Ok(x) => return x,
        Err(i) => std::process::exit(i),
    }
}

fn maze_2() -> Maze {
    let maze_str = "!!!!!!!!!!!!!!!#\
                    !      .......!#\
                    ! !!! !.!!!! .!#\
                    !   ! !.!!O!!.!#\
                    !!!   !....! .!#\
                    !   !!!!!!!!!.!#\
                    ! !!        ..!#\
                    !  !!!!!!!!!.!!#\
                    !           ..+#\
                    !!!!!!!!!!!!!!!#\
                    ";

    match str_to_maze(&maze_str) {
        Ok(x) => return x,
        Err(i) => std::process::exit(i),
    }
}

fn maze_3() -> Maze {
    let maze_str = "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#\
                    !                            !!!#\
                    ! !  !!!  !!!!!!!!!!!!!!!!!!   !#\
                    ! !  ! !!!              !!!  ! !#\
                    ! !  ! !!!!!!!!!!!!!!!!     !! !#\
                    ! !  !                  !!!!   !#\
                    ! !! !!!!!!!!!!        !!    ! !#\
                    !  ! !        !!!! !!!!!   !!! !#\
                    !! ! ! !!!!      !         !   !#\
                    !! ! ! !!!!   !!!!!!!!!!!!!! ! !#\
                    !! ! ! !!!! ! !              ! !#\
                    !! ! ! !!!! ! ! !!!!       ! ! !#\
                    !! ! ! !!!! ! ! !   !!!    ! ! !#\
                    !  ! ! !!!! ! ! !     !!!  ! ! !#\
                    !  ! ! !!!! ! ! !!!!!      !   !#\
                    !  ! ! !!!! !!! !   !!     ! !!!#\
                    !  ! !  !!!  !! !    !!!   ! !!!#\
                    !  ! !     ! !! !!!!   !!  ! !!!#\
                    !  ! !!    ! !! !  !!      ! !!!#\
                    !  !  !   !! !!     !!!    ! !!!#\
                    !  !! !!!!     !!!    !!   !   !#\
                    !!  ! !! !       !!!   !!  !!! !#\
                    !!  !    !    !    !           !#\
                    !!  !!!!!!    !!   !!!!!!!!!!! !#\
                    !             !!!! !!!!!!!!!!! !#\
                    !  ..........O!!!! !!!!!!!!!!!.+#\
                    !! .!!!!!!    !!   !!!!!!!!!!!.!#\
                    !! .!    !    !    !          .!#\
                    !!..! !! !       !!!   !!  !!!.!#\
                    ! .!! !!!!     !!!    !!   !...!#\
                    ! .!  !   !! !!     !!!    !.!!!#\
                    ! .! !!    ! !! !  !!      !.!!!#\
                    ! .! !     ! !! !!!!   !!  !.!!!#\
                    ! .! !  !!!  !! !    !!!   !.!!!#\
                    ! .! ! !!!! !!! !   !!     !.!!!#\
                    ! .! ! !!!! ! ! !!!!!      !...!#\
                    ! .! ! !!!! ! ! !     !!!  ! !.!#\
                    !!.! ! !!!! ! ! !   !!!    ! !.!#\
                    !!.! ! !!!! ! ! !!!!       ! !.!#\
                    !!.! ! !!!! ! !              !.!#\
                    !!.! ! !!!!   !!!!!!!!!!!!!! !.!#\
                    !!.! ! !!!!      !         !  .!#\
                    !..! !        !!!! !!!!!   !!!.!#\
                    !.!! !!!!!!!!!!        !!    !.!#\
                    !.!  !                  !!!!  .!#\
                    !.!  ! !!!!!!!!!!!!!!!!     !!.!#\
                    !.!  ! !!!              !!!  !.!#\
                    !.!  !!!  !!!!!!!!!!!!!!!!!!...!#\
                    !............................!!!#\
                    !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#\
                    ";

    match str_to_maze(&maze_str) {
        Ok(x) => return x,
        Err(i) => std::process::exit(i),
    }
}

fn maze_4() -> Maze {
    let maze_str = "!!!!!!!!!!!!!!!!!+!!!!!!!!!!!!!!#\
                    !.................           !!!#\
                    !.!  !!!  !!!!!!!!!!!!!!!!!!   !#\
                    !.!  ! !!!              !!!  ! !#\
                    !.!  ! !!!!!!!!!!!!!!!!     !! !#\
                    !.!  !                  !!!!   !#\
                    !.!! !!!!!!!!!!        !!    ! !#\
                    !..! !        !!!! !!!!!   !!! !#\
                    !!.! ! !!!!      !         !   !#\
                    !!.! ! !!!!   !!!!!!!!!!!!!! ! !#\
                    !!.! ! !!!! ! !              ! !#\
                    !!.! ! !!!! ! ! !!!!       ! ! !#\
                    !!.! ! !!!! ! ! !   !!!    ! ! !#\
                    ! .! ! !!!! ! ! !     !!!  ! ! !#\
                    ! .! ! !!!! ! ! !!!!!      !   !#\
                    ! .! ! !!!! !!! !   !!     ! !!!#\
                    ! .! !  !!!  !! !    !!!   ! !!!#\
                    ! .! !     ! !! !!!!   !!  ! !!!#\
                    ! .! !!    ! !! !  !!      ! !!!#\
                    ! .!  !   !! !!     !!!    ! !!!#\
                    ! .!! !!!!     !!!    !!   !   !#\
                    !!. ! !! !       !!!   !!  !!! !#\
                    !!. !    !    !    !           !#\
                    !!. !!!!!!    !!   !!!!!!!!!!! !#\
                    ! ........... !!!! !!!!!!!!!!! !#\
                    !           . !!!! !!!!!!!!!!! !#\
                    !!  !!!!!!  . !!   !!!!!!!!!!! !#\
                    !!  !    !  . !    !           !#\
                    !!  ! !! !  .    !!!   !!  !!! !#\
                    !  !! !!!!  .  !!!    !!   !   !#\
                    !  !  !   !!.!!     !!!    ! !!!#\
                    !  ! !!    !.!! !  !!      ! !!!#\
                    !  ! !     !.!! !!!!   !!  ! !!!#\
                    !  ! !  !!!..!! !    !!!   ! !!!#\
                    !  ! ! !!!!.!!! !   !!     ! !!!#\
                    !  ! ! !!!!.! ! !!!!!      !   !#\
                    !  ! ! !!!!.! ! !     !!!  ! ! !#\
                    !! ! ! !!!!.! ! !   !!!    ! ! !#\
                    !! ! ! !!!!.! ! !!!!       ! ! !#\
                    !! ! ! !!!!.! !              ! !#\
                    !! ! ! !!!!.  !!!!!!!!!!!!!! ! !#\
                    !! ! ! !!!!.....O!         !   !#\
                    !  ! !        !!!! !!!!!   !!! !#\
                    ! !! !!!!!!!!!!        !!    ! !#\
                    ! !  !                  !!!!   !#\
                    ! !  ! !!!!!!!!!!!!!!!!     !! !#\
                    ! !  ! !!!              !!!  ! !#\
                    ! !  !!!  !!!!!!!!!!!!!!!!!!   !#\
                    !                            !!!#\
                    !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#\
                    ";

    match str_to_maze(&maze_str) {
        Ok(x) => return x,
        Err(i) => std::process::exit(i),
    }
}

fn maze_5() -> Maze {
    let maze_str = "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#\
                    +......!!!!       !!!        !!!       !!!!     !!#\
                    !     .!       !!                            !!!!!#\
                    !  !!!.! !!      !!!  !!!!  !!!!!!!!!      !!!   !#\
                    ! !!...!   !!!!!   !!    !          !!    !!     !#\
                    !!!..!!         !    !!  !           !    !     !!#\
                    !! .!!........        !! !!!     !    !   !  !  !!#\
                    !!!. !.  !  !.   !      !!!!!    !!   !   ! !! !!!#\
                    !!!. !.  !  !.   !       !!!!!    !   !!    !  !!!#\
                    !!.. !.  !  !..  !        !  !    !!   !    !   !!#\
                    !!.! !.!  ! ! ..  ! !!!!!!  !      !   !    !   !!#\
                    !!.! !.!  ! !! .  ! !      !        !  !    !   !!#\
                    !!.! !.!  !  ! .  ! !!   !!    !!!! !  !    !   !!#\
                    !!.! !.!! !  ! .  !  !!!   !!!!     !  !    !!  !!#\
                    !!.! !. ! !  ! .  !    !!        !  !   !    !  !!#\
                    ! .!!!. ! !  !!.   !    !        !  !   !    !   !#\
                    ! .!!!. ! !   !.   !     !       !   !  !    !   !#\
                    ! .! !. ! !   !.   !     !       !   !   !   !   !#\
                    ! .! !. ! !!  !....!!!   !      !!   !     ! !   !#\
                    ! .!  ..!  !  !   ...!!!!       !    !     ! ! ! !#\
                    ! .!   .!  !  !!!!!!.... !!!!!!!             ! ! !#\
                    ! .! !!.!  !! !  !!!!  .!                        !#\
                    ! .!!!!.!   !!!! !!!   .!   !!!!!   !!!!!!!!!!!  !#\
                    ! .. !!.!    !!!  !!  !.!!                       !#\
                    !!!.. !. !   !!!      !..!        !!!   !   !    !#\
                    !!! .... !  !!!!      ! .!        !             !!#\
                    !!!!!!!!!!!!!!!!!!!!!!! .! !!!!!!!!!!!!!!!!!!!! !!#\
                    !!!  !                  .!                     !!!#\
                    !!   !   !!!  !!        .!                      !!#\
                    !!   !  !     !!  !!!!!!.!  !!!!!!              !!#\
                    !!   !  !    !!   !!!!!!.! !!!!!!!!          !  !!#\
                    !!  !   !   !!   !!!!!!!.! !!!!!! !!   !  !     !!#\
                    !!  !   !   !   !!!!!!!!.! !!!  !  !   !        !!#\
                    !!  !   !   !  !!!!!!!!!.! !!!! !   !  !  !  !  !!#\
                    !!  !   !   !           .!  !!  !   !  !     !  !!#\
                    !! !!!  !   !   !!!!!!  .!      !    !!         !!#\
                    !! ! !   !  !   !     !!. !    !!!    !    !    !!#\
                    !! ! !   !  !   ! !     .  !   ! !!    !     !  !!#\
                    !! ! !   !  !   ! !!  !!.   !!!   !!   !   ! !  !!#\
                    !! ! !   !  !!  ! !!! ! .....     !!   !      ! !!#\
                    !! ! !   !   !  ! !!!!!!!   .     !    !        !!#\
                    !  ! !   !   !  !  !!!  !   .!!!!     !  !       !#\
                    !  ! !   !   !! !       !   .!      !!.......... !#\
                    ! !! !   !    !  !!!!!!!!!  .!    !!  .!   !!!!. !#\
                    ! !  !   !    !!       !!!  .!!!!!   ..   !    . !#\
                    ! !  !    !!   !!!     !!!  .......... !!!!    . !#\
                    ! !  !     !!     !!!!      !!!!!!!!!!!!      !. !#\
                    ! !         !         !!!!!!                  O. !#\
                    !           !                                    !#\
                    !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#\
                    ";

    match str_to_maze(&maze_str) {
        Ok(x) => return x,
        Err(i) => std::process::exit(i),
    }
}

fn maze_6() -> Maze {
    let maze_str = "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#\
                    !      !!!!   ....!!!        !!!       !!!!     !!#\
                    !      !      .!!..........                  !!!!!#\
                    !  !!! ! !!   ...!!!  !!!!. !!!!!!!!!      !!!   !#\
                    ! !!   !   !!!!!.. !!    !.         !!    !!     !#\
                    !!!  !!         !.   !!  !.....      !    !     !!#\
                    !!  !!          ..    !! !!!  .  !    !   !  !  !!#\
                    !!!  !   !  !   .!      !!!!! .  !!   !   ! !! !!!#\
                    !!!  !   !  !   .!       !!!!!.   !   !!    !  !!!#\
                    !!   !   !  !   .!        !  !.   !!   !    !   !!#\
                    !! ! ! !  ! !   . ! !!!!!!  ! ..   !   !    !   !!#\
                    !! ! ! !  ! !!  . ! !      !   .....!  !    !   !!#\
                    !! ! ! !  !  !  . ! !!   !!    !!!!.!  !    !   !!#\
                    !! ! ! !! !  !  ..!  !!!   !!!!    .!  !    !!  !!#\
                    !! ! !  ! !  !   .!    !!        ! .!   !    !  !!#\
                    !  !!!  ! !  !!  . !    !        ! .!   !    !   !#\
                    !  !!!  ! !   !  ..!     !       ! . !  !    !   !#\
                    !  ! !  ! !   !   .!     !       ! . !   !   !   !#\
                    !  ! !  ! !!  !   .!!!   !      !! . !     ! !   !#\
                    !  !    !  !  !   ...!!!!       !  . !     ! ! ! !#\
                    !  !    !  !  !!!!!!.... !!!!!!!   .         ! ! !#\
                    !  ! !! !  !! !  !!!!  .!          .             !#\
                    !  !!!! !   !!!! !!!   .!   !!!!!  .!!!!!!!!!!!  !#\
                    !    !! !    !!!  !!  !.!!..........             !#\
                    !!!   !  !   !!!      !. !.       !!!   !   !    !#\
                    !!!      !  !!!!      !. !.       !             !!#\
                    !!!!!!!!!!!!!!!!!!!!!!!. !.!!!!!!!!!!!!!!!!!!!! !!#\
                    !!!  !                 . !.....................!!!#\
                    !!   !   !!!  !!  O..... !                    ..!!#\
                    !!   !  !     !!  !!!!!! !  !!!!!!             .!!#\
                    !!   !  !    !!   !!!!!! ! !!!!!!!!          ! .!!#\
                    !!  !   !   !!   !!!!!!! ! !!!!!! !!   !  !    .!!#\
                    !!  !   !   !   !!!!!!!! ! !!!  !  !   !       .!!#\
                    !!  !   !   !  !!!!!!!!! ! !!!! !   !  !  !  ! .!!#\
                    !!  !   !   !            !  !!  !   !  !     ! .!!#\
                    !! !!!  !   !   !!!!!!   !      !    !!        .!!#\
                    !! ! !   !  !   !     !!  !    !!!    !    !   .!!#\
                    !! ! !   !  !   ! !        !   ! !!    !     ! .!!#\
                    !! ! !   !  !   ! !!  !!    !!!   !!   !   ! ! .!!#\
                    !! ! !   !  !!  ! !!! !           !!   !      !.!!#\
                    !! ! !   !   !  ! !!!!!!!         !    !       .!!#\
                    !  ! !   !   !  !  !!!  !    !!!!     !  !     . !#\
                    !  ! !   !   !! !       !    !      !!         . !#\
                    ! !! !   !    !  !!!!!!!!!   !    !!   !   !!!!. !#\
                    ! !  !   !    !!       !!!   !!!!!        !    . !#\
                    ! !  !    !!   !!!     !!!   !         !!!!    . !#\
                    ! !  !     !!     !!!!      !!!!!!!!!!!!      !..+#\
                    ! !         !         !!!!!!                     !#\
                    !           !              !                     !#\
                    !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#\
                    ";

    match str_to_maze(&maze_str) {
        Ok(x) => return x,
        Err(i) => std::process::exit(i),
    }
}
```

<p>To test the larger maze, simply replace the maze string in the <code>maze_1</code> function. Make sure to append the correct <code>#\</code> characters to each line. </p>

<p><strong>Testing your entry</strong></p>

<p>This script can be used to test entries</p>

<pre class="lang-bash prettyprint-override"><code>#!/bin/bash

mkfifo /tmp/pipe1
mkfifo /tmp/pipe2

for arg in "$@"; do
    <path to controller> $arg < /tmp/pipe1 | tee /tmp/pipe2 trascript.txt &
    ( <path to entry> < /tmp/pipe2 | tee /tmp/pipe1 ) > /dev/null
done

rm /tmp/pipe1
rm /tmp/pipe2
</code>```

For example, my script looks like:

#!/bin/bash

mkfifo /tmp/pipe1
mkfifo /tmp/pipe2

for arg in "$@"; do
    ./maze/target/release/maze $arg < /tmp/pipe1 | tee /tmp/pipe2 trascript.txt &
    ( ./maze_test/main < /tmp/pipe2 | tee /tmp/pipe1 ) > /dev/null
done

rm /tmp/pipe1
rm /tmp/pipe2
```

<p>It is used in the following way:</p>

```./script <mazes to test>
```

<p>For example </p>

```./script 1 2 3 4 5 6
```

<p>It will print everything to the console as well as writing everything to a file called <code>transcript.txt</code></p>

<p>For the purpose of developing your entry, you can uncomment the </p>

```display_maze(&maze, position)
```

line in the play function. This will cause the controller to display the maze at each step.


问:
Golf bit weaving
Note: the first half of this challenge comes from Martin Ender's previous challenge, Visualize Bit Weaving.

The esoteric programming language evil has an interesting operation on byte values which it calls "weaving".

It is essentially a permutation of the eight bits of the byte (it doesn't matter which end we start counting from, as the pattern is symmetric):

Bit 0 is moved to bit 2

Bit 1 is moved to bit 0

Bit 2 is moved to bit 4

Bit 3 is moved to bit 1

Bit 4 is moved to bit 6

Bit 5 is moved to bit 3

Bit 6 is moved to bit 7

Bit 7 is moved to bit 5

For convenience, here are three other representations of the permutation. As a cycle:

```<code>(02467531)
</code>```

As a mapping:

```<code>57361402 -> 76543210 -> 64725031
</code>```

And as a list of pairs of the mapping:

```<code>[[0,2], [1,0], [2,4], [3,1], [4,6], [5,3], [6,7], [7,5]]
</code>```

After 8 weavings, the byte is essentially reset.

For example, weaving the number 10011101 (which is 157 in base 10) will produce 01110110 (which is 118 in base 10).

Input

There are only 256 valid inputs, namely all the integers between 0 and 255 inclusive. That may be taken in any base, but it must be consistent and you must specify it if the base you choose is not base ten.

You may not zero-pad your inputs.

Output

You should output the result of the bit weaving, in any base, which must also be consistent and specified if not base ten.

You may zero-pad your outputs.

Related: Visualize Bit Weaving

答:
Labyrinth, <s>27</s> 26 bytes

```<code>_1@
&,)}}}=}}=}}=}!{!!{{!"
</code>```

Input and output in base 2. Output is padded.

Try it online!

ContentLicense: CC BY-SA 3.0

Title: Golf bit weaving

Body:
Labyrinth, <s>27</s> 26 bytes

_1@
&,)}}}=}}=}}=}!{!!{{!"

Input and output in base 2. Output is padded.

Try it online!


问:
Twinkle Twinkle Little Star
Write a program to play the popular English nursery rhyme.

(This file is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license. Attribution: Helix84 at the English language Wikipedia; Blahedo at the English language Wikipedia.)

Some Wikipedia articles that may be useful:

Twinkle Twinkle Little Star (has an audio clip of what your program's output should sound like)

Modern musical symbols (to learn about the music notation used above)

Musical note#Note frequency (in hertz) (the formula for calculating the frequency of each note)

Some guidelines for your submission:

Your program must use the computer's sound card. If your programming language doesn't have convenient access to audio hardware, your program must create an output file in some standard format such as WAV or MIDI.

Your program must actually generate its output. For example, embedding the Ogg Vorbis file from Wikipedia would not be allowed.

The audio quality must be acceptable. At the very least, the song should be easily recognizable. Preferably, it should sound good as well.

The focus should be on code size, sound quality, or both (explain which one you decided on). Elegant solutions would also be great. Have fun!

This is a code-golf, so shortest code wins

答:
Python 317 305 301

This is my solution, using only standard python libraries:

```<code>import math,wave,struct;d=24000;r=1100.;t=wave.open("t.wav","w");t.setparams((1,2,int(r),d,"NONE",""));a=[0,7,9,7];b=[5,4,2,0];c=[7,5,4,2]
for h in[math.sin(6*[240*2**(j/12.)for j in a+b+c+c+a+b][x/1000]*(x/r))*(x%500>9 or x/1000%4>2)for x in range(d)]:t.writeframes(struct.pack('h', int(h*64000/2)))
</code>```

And here it is with some more whitespace for readability:

```<code>import math,wave,struct;d=24000;r=1100.
a=[0,7,9,7];b=[5,4,2,0];c=[7,5,4,2];s=[240*2**(j/12.) for j in a+b+c+c+a+b]
z=[math.sin(6*s[int(x/1000)]*(x/r))*(x%500>10 or int(x/1000)%4>2) for x in range(d)]
t=wave.open("t.wav","w");t.setparams((1,2,int(r),d,"NONE",""))
for h in z:t.writeframes(struct.pack('h', int(h*64000./2)))
</code>```

ContentLicense: CC BY-SA 4.0

Title: Twinkle Twinkle Little Star

Body:
Python 317 305 301

This is my solution, using only standard python libraries:

import math,wave,struct;d=24000;r=1100.;t=wave.open("t.wav","w");t.setparams((1,2,int(r),d,"NONE",""));a=[0,7,9,7];b=[5,4,2,0];c=[7,5,4,2]
for h in[math.sin(6*[240*2**(j/12.)for j in a+b+c+c+a+b][x/1000]*(x/r))*(x%500>9 or x/1000%4>2)for x in range(d)]:t.writeframes(struct.pack('h', int(h*64000/2)))

And here it is with some more whitespace for readability:

import math,wave,struct;d=24000;r=1100.
a=[0,7,9,7];b=[5,4,2,0];c=[7,5,4,2];s=[240*2**(j/12.) for j in a+b+c+c+a+b]
z=[math.sin(6*s[int(x/1000)]*(x/r))*(x%500>10 or int(x/1000)%4>2) for x in range(d)]
t=wave.open("t.wav","w");t.setparams((1,2,int(r),d,"NONE",""))
for h in z:t.writeframes(struct.pack('h', int(h*64000./2)))


问:
Autonest an array
Everybody loves nested lists! However, sometimes it's hard to make a nested list. You have to decide if you want to nest it deeper, or if you need to nest it shallower. So for your challenge, you must "Autonest" a list. To autonest a list, compare every pair of items in the list.

If the second item is smaller, separate the two elements by inserting closing and opening brackets between them, like this:

```<code>  } {
{2 , 1}
</code>```

For example, {2, 1} becomes {2}, {1}, and {3, 2, 1} becomes {3}, {2}, {1}

If the second item is the same, then change nothing. For example, {1, 1, 1} stays the same, and {2, 1, 1, 1} would become {2}, {1, 1, 1}.

If the second item is larger, then nest every following item one level deeper. For example, {1, 2} would become {1, {2}} and {1, 2, 3} would become {1, {2, {3}}}

The Challenge

You must write a program or function that takes in a list of numbers, and returns the same list after being autonested. Take this input in your languages native list format (or the closest alternative) or as a string. You do not have to use curly braces like I did in my examples. You can use whichever type of brackets are most natural in your language, as long as this is consistent. You can safely assume the list will only contain integers. You can also assume the list will have at least 2 numbers in it. Here is some sample IO:

```<code>{1, 3, 2}                         -->   {1, {3}, {2}}
{1, 2, 3, 4, 5, 6}                -->   {1, {2, {3, {4, {5, {6}}}}}}
{6, 5, 4, 3, 2, 1}                -->   {6}, {5}, {4}, {3}, {2}, {1}
{7, 3, 3, 2, 6, 4}                -->   {7}, {3, 3}, {2, {6}, {4}}
{7, 3, 1, -8, 4, 8, 2, -9, 2, 8}  -->   {7}, {3}, {1}, {-8, {4, {8}, {2}, {-9, {2, {8}}}}}
</code>```

Standard loopholes apply, and the shortest answer in bytes wins!

答:
CJam, <s>51</s> <s>49</s> <s>48</s> 46 bytes

Exploits the fact that the number of last bracket is one more than number of adjacent pair that is increasing in array.

And I don't know ew operator before that I had to reimplement.

The input is space separated list delimited by square brackets.

```<code>'[q~_W=\2ew_{~\_@-g)["["S"]["]=}%@@{~>M']?}%']
</code>```

Explanation

```<code>'[q~_W=\2ew_{~\_@-g)["["S"]["]=}%@@{~>M']?}%']
'[                                             e# Opening bracket
  q~                                           e# Read the input
    _W=\2ew                                    e# Save the last item and turn array into array of pair of next item and the item itself.
            _                                  e# We need two copies of that item
             {~\_@-g)["["S"]["]=}%             e# Build the "body" that consist of the item and the suitable delimiter, space if equal, opening brace if the first item is the smallest, otherwise, closing bracket and opening bracket.
                                  @@           e# Put in the last item. (It was omitted in previous phase)
                                    {~<']""?}% e# Create the closing bracket as many as the number of increasing adjacent pair
                                               '] e# And one more bracket.
</code>```

I will find out how to do this with actual nested array instead of relying on prettyprinting.

Finally, <s>at par with</s> beaten MATL's answer.

Title: Autonest an array

Body:
CJam, <s>51</s> <s>49</s> <s>48</s> 46 bytes

Exploits the fact that the number of last bracket is one more than number of adjacent pair that is increasing in array.

And I don't know ew operator before that I had to reimplement.

The input is space separated list delimited by square brackets.

'[q~_W=\2ew_{~\_@-g)["["S"]["]=}%@@{~>M']?}%']

Explanation

'[q~_W=\2ew_{~\_@-g)["["S"]["]=}%@@{~>M']?}%']
'[                                             e# Opening bracket
  q~                                           e# Read the input
    _W=\2ew                                    e# Save the last item and turn array into array of pair of next item and the item itself.
            _                                  e# We need two copies of that item
             {~\_@-g)["["S"]["]=}%             e# Build the "body" that consist of the item and the suitable delimiter, space if equal, opening brace if the first item is the smallest, otherwise, closing bracket and opening bracket.
                                  @@           e# Put in the last item. (It was omitted in previous phase)
                                    {~<']""?}% e# Create the closing bracket as many as the number of increasing adjacent pair
                                               '] e# And one more bracket.

I will find out how to do this with actual nested array instead of relying on prettyprinting.

Finally, <s>at par with</s> beaten MATL's answer.


答:
CJam, <s>15</s> 12 bytes

Thanks to FryAmTheEggman for saving 3 bytes.

```<code>l8Te[m!6532=
</code>```

Input in base 2. Output also in base 2, padded to 8 bits with zeros.

Test it here.

Explanation

```<code>l      e# Read the input.
8Te[   e# Left-pad it to 8 elements with zeros.
m!     e# Generate all permutations (with duplicates, i.e. treating equal elements
       e# in different positions distinctly).
6532=  e# Select the 6533rd, which happens to permute the elements like [1 3 0 5 2 7 4 6].
</code>```

Title: Golf bit weaving

Body:
Note: the first half of this challenge comes from Martin Ender's previous challenge, Visualize Bit Weaving.

The esoteric programming language evil has an interesting operation on byte values which it calls "weaving".

It is essentially a permutation of the eight bits of the byte (it doesn't matter which end we start counting from, as the pattern is symmetric):

Bit 0 is moved to bit 2

Bit 1 is moved to bit 0

Bit 2 is moved to bit 4

Bit 3 is moved to bit 1

Bit 4 is moved to bit 6

Bit 5 is moved to bit 3

Bit 6 is moved to bit 7

Bit 7 is moved to bit 5

For convenience, here are three other representations of the permutation. As a cycle:

```<code>(02467531)
</code>```

As a mapping:

```<code>57361402 -> 76543210 -> 64725031
</code>```

And as a list of pairs of the mapping:

```<code>[[0,2], [1,0], [2,4], [3,1], [4,6], [5,3], [6,7], [7,5]]
</code>```

After 8 weavings, the byte is essentially reset.

For example, weaving the number 10011101 (which is 157 in base 10) will produce 01110110 (which is 118 in base 10).

Input

There are only 256 valid inputs, namely all the integers between 0 and 255 inclusive. That may be taken in any base, but it must be consistent and you must specify it if the base you choose is not base ten.

You may not zero-pad your inputs.

Output

You should output the result of the bit weaving, in any base, which must also be consistent and specified if not base ten.

You may zero-pad your outputs.

Related: Visualize Bit Weaving

Body:
CJam, <s>15</s> 12 bytes

Thanks to FryAmTheEggman for saving 3 bytes.

l8Te[m!6532=

Input in base 2. Output also in base 2, padded to 8 bits with zeros.

Test it here.

Explanation

l      e# Read the input.
8Te[   e# Left-pad it to 8 elements with zeros.
m!     e# Generate all permutations (with duplicates, i.e. treating equal elements
       e# in different positions distinctly).
6532=  e# Select the 6533rd, which happens to permute the elements like [1 3 0 5 2 7 4 6].


Title: Golf bit weaving

Body:
Python 2.7, 44 -> 36 bytes

lambda x:x/4&42|x*2&128|x*4&84|x/2&1


问:
Visualise Bit Weaving
The esoteric programming language evil has an interesting operation on byte values which it calls "weaving". It is essentially a permutation of the eight bits of the byte (it doesn't matter which end we start counting from, as the pattern is symmetric):

Bit 0 is moved to bit 2

Bit 1 is moved to bit 0

Bit 2 is moved to bit 4

Bit 3 is moved to bit 1

Bit 4 is moved to bit 6

Bit 5 is moved to bit 3

Bit 6 is moved to bit 7

Bit 7 is moved to bit 5

For convenience, here are two other representations of the permutation. As a cycle:

```<code>(02467531)
</code>```

And as a list of pairs of the mapping:

```<code>[[0,2], [1,0], [2,4], [3,1], [4,6], [5,3], [6,7], [7,5]]
</code>```

Your task is to visualise this permutation, using the box-drawing characters ─, │, ┌, ┐, └, ┘, ┼ (Unicode code points: U+2500, U+2502, U+250C, U+2510, U+2514, U+2518, U+253C). This visualisation should satisfy the following constraints:

The first and last line are exactly:

```<code>0 1 2 3 4 5 6 7
</code>```

Between those, you can use as many lines as you want of up to 15 characters each to fit your box drawing characters (you will need at least 4 lines). The lines should start vertically beneath one of the digits on the first row and end vertically above the corresponding digit on the last row. The eight lines must be connected, and may only cross via ┼ (which is always a crossing, never two turning lines which are touching). The exact paths of the lines are up to you (and finding a particularly golfable layout is the core of this challenge). One valid output would be:

```<code>0 1 2 3 4 5 6 7
│ │ └─┼┐│ │ └┐│
└─┼─┐ ││└─┼─┐││
┌─┘ │ ││  │ │││
│ ┌─┼─┘│  │ │││
│ │ │ ┌┼──┘ │││
│ │ │ │└┐ ┌─┼┼┘
│ │ │ │ │ │ │└┐
0 1 2 3 4 5 6 7
</code>```

However, any other layout that correctly connects the right digits is fine too. Please show your chosen output in your answer.

You may write a program or function and will not take any input. Output the diagram either to STDOUT (or closest alternative) or as a function return value in the form of a string or a list of strings (each representing one line).

Standard code-golf rules apply, so the shortest code (in bytes) wins.

答:
Sprects, 99 bytes (87 chars)

```<code>$8
AC
BE
DA
C 9
9E 9
9 D
8$E B B B$D9A 9A 9A 9$C9 A9 A9 A9$B┌┼┘$A└┐$9│$80 1 2 3 4 5 6 7
</code>```

Uses @Marco's output (replace every 16th character with a newline (regex: (.{15}). -> \1\n)).```0 1 2 3 4 5 6 7
└┐│ └┐│ └┐│ └┐│
┌┼┘ ┌┼┘ ┌┼┘ ┌┼┘
│└┐ │└┐ │└┐ │└┐
│ └┐│ └┐│ └┐│ │
│ ┌┼┘ ┌┼┘ ┌┼┘ │
│ │└┐ │└┐ │└┐ │
0 1 2 3 4 5 6 7```

Title: Visualise Bit Weaving

Body:
Sprects, 99 bytes (87 chars)

$8
AC
BE
DA
C 9
9E 9
9 D
8$E B B B$D9A 9A 9A 9$C9 A9 A9 A9$B┌┼┘$A└┐$9│$80 1 2 3 4 5 6 7

Uses @Marco's output (replace every 16th character with a newline (regex: (.{15}). -> \1\n)).
0 1 2 3 4 5 6 7
└┐│ └┐│ └┐│ └┐│
┌┼┘ ┌┼┘ ┌┼┘ ┌┼┘
│└┐ │└┐ │└┐ │└┐
│ └┐│ └┐│ └┐│ │
│ ┌┼┘ ┌┼┘ ┌┼┘ │
│ │└┐ │└┐ │└┐ │
0 1 2 3 4 5 6 7


问:
Digital River (Shortest And Fastest Solution)
This is my first question, so I hope it goes well.

Background:

It's not the rivers that you might be thinking about. The question revolves around the concept of digital rivers. A digital river is a sequence of numbers where the number following n is n plus the sum of its digits.

Explanation:

12345 is followed by 12360 since 1+2+3+4+5=15 and so 12345 + 15 gives
12360. similarly 145 is followed by 155. If the first number of a digital river is M we will call it river M.

For e.g: River 480 is the sequence beginning {480,492,507,519....}, and river 483 is the sequence beginning {483,498,519,....}. Normal streams and rivers can meet, and the same is true for digital rivers. This happens when two digital rivers share some of the same values.

Example:

River 480 meets river 483 at 519. River 480 meets river 507 at 507 and never meets river 481. Every digital river will eventually meet river 1, river 3 or river 9.

Write a program that can determine for a given integer n the value where river n first meets one of these three rivers.

Input

The input may contain multiple test cases. Each test case occupies a separate line and contains an integer n (1 <= n <= 16384). A test case with value of 0 for n terminates the input and this test case must not be processed.

Output

For each test case in the input first output the test case number (starting from 1) as shown in the sample output. Then on a separate line output the line "first meets river x at y". Here y is the lowest value where river n first meets river x (x = 1 or 3 or 9). If river n meets river x at y for more than one value of x, output the lowest value. Print a blank line between two consecutive test cases.

Test case

Input:

```<code>86
12345
0
</code>```

Output:

```<code>Case #1

first meets river 1 at 101

Case #2

first meets river 3 at 12423
</code>```

Scoring:

The fastest algorithm wins. In case of tie. The one with shorter code will win.

Thanks to mbomb007 for pointing out my error.

p.s: I want to have the fastest solution rather than the smallest one.
I also have a solution of mine which is slow. For that look here.

Note:

I will be using this for code testing. And performance checking.

答:
Java 7, <s>519</s> 505  bytes

```<code>import java.util.*;String c(int i){if(i<=0)return"";ArrayList<Long>r=f(1),s=f(3),t=f(9),x=f(i);String z="first meets river ";for(int j=0;j<r.size();j++){long u=r.get(j),v=s.get(j),w=t.get(j);if(x.contains(u))return z+1+" at "+u;if(x.contains(v))return z+3+" at "+v;if(x.contains(w))return z+9+" at "+w;}return"";}ArrayList f(long i){ArrayList<Long>l=new ArrayList();l.add(i);for(long j=0,x;j<9e4;j++){x=l.get(l.size()-1);for(char c:(x+"").toCharArray())x+=new Long(c+"");l.add(x);if(x>16383)return l;}return l;}
</code>```

Yes, it's long, ugly and can without a doubt be completely changed to code-golf it more.. I'm both distracted and tired, so perhaps I should just delete it again..

It was a pretty hard challenge to be honest.. But at least you have your first answer.. ;) (Which might even be longer than your original ungolfed C++ program.. xD)

Ungolfed & test cases:

Try it here.

```<code>import java.util.*;
class M{
  static String c(int i){
    if(i <= 0){
      return "";
    }
    ArrayList<Long> r = f(1),
                    s = f(3),
                    t = f(9),
                    x = f(i);
    String z = "first meets river ",
           y = " at ";
    for(int j = 0; j < r.size(); j++){
      long u = r.get(j),
           v = s.get(j),
           w = t.get(j);
      if(x.contains(u)){
        return z+1+y+u;
      }
      if(x.contains(v)){
        return z+3+y+v;
      }
      if(x.contains(w)){
        return z+9+y+w;
      }
    }
    return "";
  }

  static ArrayList f(long i){
    ArrayList<Long> l = new ArrayList();
    l.add(i);
    for(long j = 0, x; j < 9e4; j++){
      x = l.get(l.size() - 1);
      for(char c : (x + "").toCharArray()){
        x += new Long(c+"");
      }
      l.add(x);
      if(x > 16383){
        return l;
      }
    }
    return l;
  }

  public static void main(String[] a){
    System.out.println(c(86));
    System.out.println(c(12345));
    System.out.println(c(0));
  }
}
</code>```

Output:

```<code>first meets river 1 at 101
first meets river 3 at 12423
(empty output)
</code>```

Body:
Java 7, <s>519</s> 505  bytes

import java.util.*;String c(int i){if(i<=0)return"";ArrayList<Long>r=f(1),s=f(3),t=f(9),x=f(i);String z="first meets river ";for(int j=0;j<r.size();j++){long u=r.get(j),v=s.get(j),w=t.get(j);if(x.contains(u))return z+1+" at "+u;if(x.contains(v))return z+3+" at "+v;if(x.contains(w))return z+9+" at "+w;}return"";}ArrayList f(long i){ArrayList<Long>l=new ArrayList();l.add(i);for(long j=0,x;j<9e4;j++){x=l.get(l.size()-1);for(char c:(x+"").toCharArray())x+=new Long(c+"");l.add(x);if(x>16383)return l;}return l;}

Yes, it's long, ugly and can without a doubt be completely changed to code-golf it more.. I'm both distracted and tired, so perhaps I should just delete it again..

It was a pretty hard challenge to be honest.. But at least you have your first answer.. ;) (Which might even be longer than your original ungolfed C++ program.. xD)

Ungolfed & test cases:

Try it here.

import java.util.*;
class M{
  static String c(int i){
    if(i <= 0){
      return "";
    }
    ArrayList<Long> r = f(1),
                    s = f(3),
                    t = f(9),
                    x = f(i);
    String z = "first meets river ",
           y = " at ";
    for(int j = 0; j < r.size(); j++){
      long u = r.get(j),
           v = s.get(j),
           w = t.get(j);
      if(x.contains(u)){
        return z+1+y+u;
      }
      if(x.contains(v)){
        return z+3+y+v;
      }
      if(x.contains(w)){
        return z+9+y+w;
      }
    }
    return "";
  }

  static ArrayList f(long i){
    ArrayList<Long> l = new ArrayList();
    l.add(i);
    for(long j = 0, x; j < 9e4; j++){
      x = l.get(l.size() - 1);
      for(char c : (x + "").toCharArray()){
        x += new Long(c+"");
      }
      l.add(x);
      if(x > 16383){
        return l;
      }
    }
    return l;
  }

  public static void main(String[] a){
    System.out.println(c(86));
    System.out.println(c(12345));
    System.out.println(c(0));
  }
}

Output:

first meets river 1 at 101
first meets river 3 at 12423
(empty output)


答:
Mathematica, 34 bytes

```<code>PadLeft[#,8][[{2,4,1,6,3,8,5,7}]]&
</code>```

Anonymous function. Takes a list of binary digits, and outputs a padded list of 8 binary digits.

Title: Golf bit weaving

Body:
Mathematica, 34 bytes

PadLeft[#,8][[{2,4,1,6,3,8,5,7}]]&

Anonymous function. Takes a list of binary digits, and outputs a padded list of 8 binary digits.


答:
MATL, 14 bytes

```<code>&8B[2K1B3D5C])
</code>```

Input is in decimal. Output is zero-padded binary.

Try it online!

Explanation

```<code>&8B         % Take input number implicitly. Convert to binary array with 8 digits
[2K1B3D5C]  % Push array [2 4 1 6 3 8 5 7]
)           % Index first array with second array. Implicitly display
</code>```

Title: Golf bit weaving

Body:
MATL, 14 bytes

&8B[2K1B3D5C])

Input is in decimal. Output is zero-padded binary.

Try it online!

Explanation

&8B         % Take input number implicitly. Convert to binary array with 8 digits
[2K1B3D5C]  % Push array [2 4 1 6 3 8 5 7]
)           % Index first array with second array. Implicitly display


答:
Jelly, 11 bytes

```<code>+⁹BḊŒ!6533ị
</code>```

Translation of Martin’s CJam answer. Try it here.

```<code>+⁹BḊ          Translate (x+256) to binary and chop off the MSB.
              This essentially zero-pads the list to 8 bits.
    Œ!        Generate all permutations of this list.
      6533ị   Index the 6533rd one.
</code>```

Title: Golf bit weaving

Body:
Jelly, 11 bytes

+⁹BḊŒ!6533ị

Translation of Martin’s CJam answer. Try it here.

+⁹BḊ          Translate (x+256) to binary and chop off the MSB.
              This essentially zero-pads the list to 8 bits.
    Œ!        Generate all permutations of this list.
      6533ị   Index the 6533rd one.


答:
Matlab, <s>49</s> <s>48</s> 44 bytes

```<code>s=sprintf('%08s',input(''));s('24163857'-48)
</code>```

Takes input as string of binary values. Output padded.
4 bytes saved thanks to @Luis Mendo.

Explanation:

```<code>input('')             -- takes input
s=sprintf('%08s',...) -- pads with zeros to obtain 8 digits
s('24163857'-48)      -- takes positions [2 4 1 6 3 8 5 7] from s (48 is code for '0')
</code>```

Title: Golf bit weaving

Body:
Matlab, <s>49</s> <s>48</s> 44 bytes

s=sprintf('%08s',input(''));s('24163857'-48)

Takes input as string of binary values. Output padded.
4 bytes saved thanks to @Luis Mendo.

Explanation:

input('')             -- takes input
s=sprintf('%08s',...) -- pads with zeros to obtain 8 digits
s('24163857'-48)      -- takes positions [2 4 1 6 3 8 5 7] from s (48 is code for '0')


问:
Generate N number of "Go First" dice

Background

As described here http://www.ericharshbarger.org/dice/#gofirst_4d12, "Go First" Dice is a set of four dice, each with unique numbering, so that:

There will never be a tie. Each die has a unique set of numbers.

Regardless of what subset of dice are rolled against one another, each player will always have an equal chance of rolling the high number.

Here is the specific numbering for the four dice mentioned, as an example:

```<code>DICE COUNT: 4
FACE COUNT: 12
D1: 1,8,11,14,19,22,27,30,35,38,41,48
D2: 2,7,10,15,18,23,26,31,34,39,42,47
D3: 3,6,12,13,17,24,25,32,36,37,43,46
D4: 4,5, 9,16,20,21,28,29,33,40,44,45
</code>```

(via)

Goal

Without requiring any particular result, I would like to be able to generate a set of N "Go First" dice... Such that, example output might look like so (formatted, python console):

```<code>    >>> generate_dice(players=4)
    [[1,8,11,14,19,22,27,30,35,38,41,48],
     [2,7,10,15,18,23,26,31,34,39,42,47],
     [3,6,12,13,17,24,25,32,36,37,43,46],
     [4,5,9,16,20,21,28,29,33,40,44,45]]
</code>```

The number of sides here is chosen just for example purposes, because it matches the other example given. The number of sides of the dice can be determined by the algorithm used.

Ideally the solution would be in Python, but I can also read PHP, Javascript, some Ruby, quite well.

I'm honestly puzzling over this, and would love to understand what terminology/math I should have studied to figure this out. I've tried to explain it before, but seem to be having trouble not using words that imply too many things about what should be generated, and what odds should be, etc. I'm specifically interested in being able to generate "a set of N 'Go First' dice".

Extra

Here's some ugly python, to "prove" the dice, and perhaps give an example.

```<code>def fair_chance(die1, die2):
    wins = 0
    losses = 0
    ties = 0
    for i in die1:
        for x in die2:
            if cmp(i, x) < 0:
                losses += 1
            if cmp(i, x) > 0:
                wins += 1
            if cmp(i, x) == 0:
                ties += 1
    if wins == losses and losses != 0 and ties == 0:
        return True
    return False
</code>```

Give the above example dice:

```<code>D1 = [1,8,11,14,19,22,27,30,35,38,41,48]
D2 = [2,7,10,15,18,23,26,31,34,39,42,47]
D3 = [3,6,12,13,17,24,25,32,36,37,43,46]
D4 = [4,5, 9,16,20,21,28,29,33,40,44,45]

fair_chance(D1, D2)  # True
fair_chance(D1, D3)  # True
fair_chance(D1, D4)  # True
fair_chance(D2, D3)  # True
fair_chance(D2, D4)  # True
fair_chance(D3, D4)  # True
</code>```

Thus, the function generate_dice should work, such that output in a Python shell would look like this:

```<code>>>> dice = generate_dice(players=4)
>>> D1 = dice[0]
>>> D2 = dice[1]
>>> D3 = dice[2]
>>> D4 = dice[3]
>>> fair_chance(D1, D2)
True
>>> fair_chance(D1, D3)
True
>>> fair_chance(D1, D4)
True
>>> fair_chance(D2, D3)
True
>>> fair_chance(D2, D4)
True
>>> fair_chance(D3, D4)
True
</code>```

答:
Well, I believe that this deals with telescoping series. As it turns out, the number of dice and number of sides you use is very important. For example, try to make 4, 4 sided dice that fits the same requirement.

Using the numbers from 1 to 16, one of the dice has to get the number 16.
Which ever dice has 16 already has a 25% chance of landing on the highest number when all 4 are rolled. However, the chance that any particular dice is first must = 25%. Thus, the remaining numbers must have 0% chance of being the highest number. This makes the first dice [1,2,3,16]. However this doesn't fit the requirement that when rolling 2 dice, you still have a equal probability of going first. Now you only have 25% instead of 50%. Thus when you have 4 dice, you must have more than 4 sides for these requirements to work.

I think the fact that they used 4 d12 is not just by chance. I would bet it's the minimum number of sides for 4 dice that works. I think if 4d8 or 4d6 worked, they would have just done that, because it's simpler to prove correct.

Thus, with 4 dice, you need a number of sides which is >=12 to meet all the properties.

In the example, the die with the highest number (48) has only a 1/12 of getting that number. Since this die has a 1/12 of going first, it should also have a 1/12 of going last, so it gets a (1).

Notice that the relative order of the numbers of each dice forms a sort of palindrome of pairs.
(1 4) (3 2) (3 2) (3 2) (3 2) (1 4) the first dice sequence
This is obviously on purpose. I'd check to see if other palindromes have the same property.

Title: Generate N number of "Go First" dice


答:
J, 12 bytes

```<code>6532 A._8&{.
</code>```

Uses the permute builtin A. with permutation index 6532 which corresponds to the bit-weaving operation.

Usage

Input is a list of binary digits. Output is a zero-padded list of 8 binary digits.

```<code>   f =: 6532 A._8&{.
   f 1 0 0 1 1 1 0 1
0 1 1 1 0 1 1 0
   f 1 1 1 0 1 1 0
1 1 0 1 1 0 0 1
</code>```

Explanation

```<code>6532 A._8&{.  Input: s
       _8&{.  Takes the list 8 values from the list, filling with zeros at the front
              if the length(s) is less than 8
6532          The permutation index for bit-weaving
     A.       permute the list of digits by that index and return
</code>```

Title: Golf bit weaving

Body:
J, 12 bytes

6532 A._8&{.

Uses the permute builtin A. with permutation index 6532 which corresponds to the bit-weaving operation.

Usage

Input is a list of binary digits. Output is a zero-padded list of 8 binary digits.

   f =: 6532 A._8&{.
   f 1 0 0 1 1 1 0 1
0 1 1 1 0 1 1 0
   f 1 1 1 0 1 1 0
1 1 0 1 1 0 0 1

Explanation

6532 A._8&{.  Input: s
       _8&{.  Takes the list 8 values from the list, filling with zeros at the front
              if the length(s) is less than 8
6532          The permutation index for bit-weaving
     A.       permute the list of digits by that index and return


答:
05AB1E, <s>14</s> 12 bytes

```<code>žz+b¦œ6532èJ
</code>```

Explanation

```<code>žz+b¦           # convert to binary padded with 0's to 8 digits
     œ6532è     # get the 6532th permutation of the binary number
           J    # join and implicitly print
</code>```

Input is in base 10.

Output is in base 2.

Borrows the permutation trick from MartinEnder's CJam answer

Try it online

Title: Golf bit weaving

Body:
05AB1E, <s>14</s> 12 bytes

žz+b¦œ6532èJ

Explanation

žz+b¦           # convert to binary padded with 0's to 8 digits
     œ6532è     # get the 6532th permutation of the binary number
           J    # join and implicitly print

Input is in base 10.

Output is in base 2.

Borrows the permutation trick from MartinEnder's CJam answer

Try it online


问:
Choose from an existing set of weights to make a target sum
When doing weightlifting, I want to make a specific weight by attaching several plates to a bar.

I have the following plates:

6 plates of 1 kg each

6 plates of 2.5 kg each

6 plates of 5 kg each

6 plates of 10 kg each

The bar itself weighs 10 kg.

It's only allowed to attach the plates in pairs - they are attached at each end of the bar, and the arrangement at the two ends must be completely symmetrical (e.g. attaching two 5-kg plates at one end, and one 10-kg plate at the other end is forbidden for reasons of safety).

Make a program or a function that tells me how many plates of each kind I have to use in order to get a given total weight. The input is an integer greater than 11; the output is a list/array/string of 4 numbers. If it's impossible to combine existing plates to get the target weight, output a zero/empty array, an invalid string, throw an exception or some such.

If there are several solutions, the code must output only one (don't make the user choose - he is too busy with other things).

Test cases:

```<code>12 -> [2 0 0 0] - 2 plates of 1 kg plus the bar of 10 kg
13 -> [0 0 0 0] - a special-case output that means "impossible"
20 -> [0 0 2 0] - 2 plates of 5 kg + bar
20 -> [0 4 0 0] - a different acceptable solution for the above
21 -> [6 2 0 0] - 6 plates of 1 kg + 2 plates of 2.5 kg + bar
28 -> [0 0 0 0] - impossible
45 -> [0 2 6 0] - a solution for a random number in range
112 -> [2 4 6 6] - a solution for a random number in range
121 -> [6 6 6 6] - maximal weight for which a solution is possible
</code>```

If your code outputs the numbers in the opposite order (from the heavy plate to the light one), please specify this explicitly to avoid confusion.

答:
Pyth, <s>34</s> <s>31</s> 25 bytes

```
<s>h+fqQ+;s*VT[1 2.5 5;)yMM^U4 4]*4]0</s>
<s>yMh+fqQ+;s*VT[2 5;y;)^U4 4]*4]0</s>
yMhfqQ+;s*VT[2 5;y;)^U4 4
```

Test suite.

Errors in impossibility.

This is essentially a brute-force.

This is quite fast, since there are only 256 possible arrangements.

Body:
Pyth, <s>34</s> <s>31</s> 25 bytes

<s>h+fqQ+;s*VT[1 2.5 5;)yMM^U4 4]*4]0</s>
<s>yMh+fqQ+;s*VT[2 5;y;)^U4 4]*4]0</s>
yMhfqQ+;s*VT[2 5;y;)^U4 4

Test suite.

Errors in impossibility.

This is essentially a brute-force.

This is quite fast, since there are only 256 possible arrangements.


答:
PowerShell v2+, 34 bytes

```<code>("{0:D8}"-f$args)[1,3,0,5,2,7,4,6]
</code>```

Translation of @LegionMammal978's answer. Full program. Takes input via command-line argument as a binary number, outputs as a binary array, zero-padded.

The "{0:D8}"-f portion uses standard numeric format strings to prepend 0 to the input $args. Since the -f operator supports taking an array as input, and we've explicitly said to use the first element {0:, we don't need to do the usual $args[0]. We encapsulate that string in parens, then index into it [1,3,0,5,2,7,4,6] with the weaving. The resultant array is left on the pipeline and output is implicit.

Examples

(the default .ToString() for an array has the separator as `n, so that's why the output is newline separated here)

```<code>PS C:\Tools\Scripts\golfing> .\golf-bit-weaving.ps1 10011101
0
1
1
1
0
1
1
0

PS C:\Tools\Scripts\golfing> .\golf-bit-weaving.ps1 1111
0
0
0
1
0
1
1
1
</code>```

Title: Golf bit weaving

Body:
PowerShell v2+, 34 bytes

("{0:D8}"-f$args)[1,3,0,5,2,7,4,6]

Translation of @LegionMammal978's answer. Full program. Takes input via command-line argument as a binary number, outputs as a binary array, zero-padded.

The "{0:D8}"-f portion uses standard numeric format strings to prepend 0 to the input $args. Since the -f operator supports taking an array as input, and we've explicitly said to use the first element {0:, we don't need to do the usual $args[0]. We encapsulate that string in parens, then index into it [1,3,0,5,2,7,4,6] with the weaving. The resultant array is left on the pipeline and output is implicit.

Examples

(the default .ToString() for an array has the separator as `n, so that's why the output is newline separated here)

PS C:\Tools\Scripts\golfing> .\golf-bit-weaving.ps1 10011101
0
1
1
1
0
1
1
0

PS C:\Tools\Scripts\golfing> .\golf-bit-weaving.ps1 1111
0
0
0
1
0
1
1
1


答:
Mathematica, 70 bytes

```<code>Select[FrobeniusSolve[{2,5,10,20},2#-20],AllTrue[EvenQ@#&&#<7&]][[1]]&
</code>```

Anonymous function. Takes a number as input, and either outputs a list or errors and returns {}[[1]] if there is no solution.

Title: Choose from an existing set of weights to make a target sum

Body:
When doing weightlifting, I want to make a specific weight by attaching several plates to a bar.

I have the following plates:

6 plates of 1 kg each

6 plates of 2.5 kg each

6 plates of 5 kg each

6 plates of 10 kg each

The bar itself weighs 10 kg.

It's only allowed to attach the plates in pairs - they are attached at each end of the bar, and the arrangement at the two ends must be completely symmetrical (e.g. attaching two 5-kg plates at one end, and one 10-kg plate at the other end is forbidden for reasons of safety).

Make a program or a function that tells me how many plates of each kind I have to use in order to get a given total weight. The input is an integer greater than 11; the output is a list/array/string of 4 numbers. If it's impossible to combine existing plates to get the target weight, output a zero/empty array, an invalid string, throw an exception or some such.

If there are several solutions, the code must output only one (don't make the user choose - he is too busy with other things).

Test cases:

```<code>12 -> [2 0 0 0] - 2 plates of 1 kg plus the bar of 10 kg
13 -> [0 0 0 0] - a special-case output that means "impossible"
20 -> [0 0 2 0] - 2 plates of 5 kg + bar
20 -> [0 4 0 0] - a different acceptable solution for the above
21 -> [6 2 0 0] - 6 plates of 1 kg + 2 plates of 2.5 kg + bar
28 -> [0 0 0 0] - impossible
45 -> [0 2 6 0] - a solution for a random number in range
112 -> [2 4 6 6] - a solution for a random number in range
121 -> [6 6 6 6] - maximal weight for which a solution is possible
</code>```

If your code outputs the numbers in the opposite order (from the heavy plate to the light one), please specify this explicitly to avoid confusion.

Body:
Mathematica, 70 bytes

Select[FrobeniusSolve[{2,5,10,20},2#-20],AllTrue[EvenQ@#&&#<7&]][[1]]&

Anonymous function. Takes a number as input, and either outputs a list or errors and returns {}[[1]] if there is no solution.


答:
Jelly, 25 bytes

```<code>×2,5,10,20S+⁵⁼³
4ṗ4’ÇÐfḢḤ
</code>```

Try it here.

Body:
Jelly, 25 bytes

×2,5,10,20S+⁵⁼³
4ṗ4’ÇÐfḢḤ

Try it here.


Title: Golf bit weaving

Body:
JavaScript (ES6), 30 bytes

f=n=>n*4&84|n*2&128|n/2&1|n/4&42


答:
MATL, <s>29</s> 28 bytes

```<code>4t:qEZ^!"[l2.5AX]@Y*10+G=?@.
</code>```

For inputs that have no solution this produces an empty output (without error).

Try it online!

Explanation

```<code>4           % Push 4
t:q         % Duplicate 4 and transform into range [0 1 2 3]
E           % Multiply by 2: transform into [0 2 4 6]
Z^          % Cartesian power. Each row is a "combination" of the four numbers
!           % Transpose
"           % For each column
  [l2.5AX]  %   Push [1 2.5 5 10]
  @         %   Push current column
  Y*        %   Matrix multiply. Gives sum of products
  10+       %   Add 10
  G=        %   Compare with input: are they equal?
  ?         %   If so
    @       %     Push current column, to be displayed
    .       %     Break loop
            %   Implicit end
            % Implicit end
            % Implicit display
</code>```

Body:
MATL, <s>29</s> 28 bytes

4t:qEZ^!"[l2.5AX]@Y*10+G=?@.

For inputs that have no solution this produces an empty output (without error).

Try it online!

Explanation

4           % Push 4
t:q         % Duplicate 4 and transform into range [0 1 2 3]
E           % Multiply by 2: transform into [0 2 4 6]
Z^          % Cartesian power. Each row is a "combination" of the four numbers
!           % Transpose
"           % For each column
  [l2.5AX]  %   Push [1 2.5 5 10]
  @         %   Push current column
  Y*        %   Matrix multiply. Gives sum of products
  10+       %   Add 10
  G=        %   Compare with input: are they equal?
  ?         %   If so
    @       %     Push current column, to be displayed
    .       %     Break loop
            %   Implicit end
            % Implicit end
            % Implicit display


问:
Recursion bracketed; or Dyck words generation
We already have challenges to check if a string of brackets is fully matched and to count the number of balanced strings. It remains for us to generate these strings, but it will not be so easy…

A Dyck word is a string, of length 2n, consisting of n opening and n closing parentheses (( and )) fully matched (that is to say: for all prefixes of the string, the number of opening parentheses is greater than or equal to the number of closing ones).

It is interesting to note that the number of different Dyck words of length 2n is equal to the (n + 1)-th Catalan number.

It’s pretty straightforward to write a program that generates these words with a recursive function. But the goal here is to do the same thing without.

Challenge

Write a full program or function that takes a positive integer, n, using stdin or an acceptable alternative, and outputs all the different Dyck words of length 2n. The words can appear in any order and each must be separated from each other by a line break. Moreover, your program should not use recursive functions (see details below).

Rules

The output of your program should only contain Dyck words of length 2n, separated by line breaks. Each word must appear only once.

Your program must work at minimum for inputs 0 to 15.

You may not write recursive functions, neither direct (a function that calls itself) nor indirect (e.g. a function f that calls another function g that calls function f). That being said, you can still use the standard functions of your language without worry of how they work internally.

Similarly, your program should not call itself.

You may not use non-standard librairies.

Your program may not read or write files.

Your program must be able to run in a reasonable time for 0 ≤ n ≤ 15 (hence, naively generate all arrangements is probably not a good idea). Let’s say less than 20 minutes with a memory limit of 4 GB (my reference implementation in C manages n = 15 in less than 5 seconds).

All standard loopholes are forbidden.

As usual in code-golf, the shortest code in bytes wins. But if you have found an interesting way to achieve this challenge in your language, please do not hesitate.

Test I/O

For this input:

```<code>3
</code>```

The output could be (any other order is correct too):

```<code>((()))
()()()
(()())
(())()
()(())
</code>```

答:
C, <s>748</s> <s>746</s> 651 bytes

```<code>#define C(v,n) for(v=n==D;v<=(n<=D);v++)
void p(Z){unsigned long long R,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D=Z*2,E,F;C(C,30)C(B,29)C(A,28)C(z,27)C(y,26)C(x,25)C(w,24)C(v,23)C(u,22)C(t,21)C(s,20)C(r,19)C(q,18)C(p,17)C(o,16)C(n,15)C(m,14)C(l,13)C(k,12)C(j,11)C(i,10)C(h,9)C(g,8)C(f,7)C(e,6)C(d,5)C(c,4)C(b,3)C(a,2){R=C<<29|B<<28|A<<27|z<<26|y<<25|x<<24|w<<23|v<<22|u<<21|t<<20|s<<19|r<<18|q<<17|p<<16|o<<15|n<<14|m<<13|l<<12|k<<11|j<<10|i<<9|h<<8|g<<7|f<<6|e<<5|d<<4|c<<3|b<<2|a<<1;if(__builtin_popcount(R)!=Z)goto X;F=0;for(E=D-1;E;E--)if(R&1<<E)F++;else if(F)F--;else goto X;for(;E<D;E++)putchar(40+!(R&1<<D-E-1));puts("");X:;}}
</code>```

At a whopping >600 bytes, this isn't really much of a contender...but it's pretty fast and memory efficient.

Works by encoding the parentheses strings as integers, with a set bit representing ( and an unset bit representing ). For instance, (()) would be 1100. I made the following observations:

All permutations must begin with ( and end with ); otherwise, it won't be valid.

Every valid permutation must have n left parentheses and n right parentheses, where n is the input number. I used __builtin_popcount for this.

When built via icc -march=native -O3, it takes 17s on my computer, though others have reported better times (~3-7s) on their (presumably faster) computers. In addition, it uses around 1.5 KB of memory.

Here's the code with explanatory comments:

```<code>// Z is the input number.
void p(Z){
    // All the variables.
    // R is the resulting paren number, with 1 bits for open parens and 0s for closed ones.
    // a-C are used to hold the state of each paren (1 if open, 0 if closed).
    // D holds Z*2, or the total length of the paren string.
    // E and F are used later on.
    unsigned long long R,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D=Z*2,E,F;
    /* Each loop performs a basic check. If D is equal to the corresponding
       number, then the variable will start at 1 (since the first paren must
       always be open). If D is greater than or equal to the number, then the loop
       will only be run once with the variable set to 0, and a later check will
       cause the variable to be ignored. Otherwise, it will loop twice; one for a
       closed paren (0), and one for an open one (1). Of course, if D == the
       number, then it will only loop for the open paren (as stated above). */
    for (C = (D == 30); C <= (30 <= D); C++)
    for (B = (D == 29); B <= (29 <= D); B++)
    for (A = (D == 28); A <= (28 <= D); A++)
    for (z = (D == 27); z <= (27 <= D); z++)
    for (y = (D == 26); y <= (26 <= D); y++)
    for (x = (D == 25); x <= (25 <= D); x++)
    for (w = (D == 24); w <= (24 <= D); w++)
    for (v = (D == 23); v <= (23 <= D); v++)
    for (u = (D == 22); u <= (22 <= D); u++)
    for (t = (D == 21); t <= (21 <= D); t++)
    for (s = (D == 20); s <= (20 <= D); s++)
    for (r = (D == 19); r <= (19 <= D); r++)
    for (q = (D == 18); q <= (18 <= D); q++)
    for (p = (D == 17); p <= (17 <= D); p++)
    for (o = (D == 16); o <= (16 <= D); o++)
    for (n = (D == 15); n <= (15 <= D); n++)
    for (m = (D == 14); m <= (14 <= D); m++)
    for (l = (D == 13); l <= (13 <= D); l++)
    for (k = (D == 12); k <= (12 <= D); k++)
    for (j = (D == 11); j <= (11 <= D); j++)
    for (i = (D == 10); i <= (10 <= D); i++)
    for (h = (D == 9); h <= (9 <= D); h++)
    for (g = (D == 8); g <= (8 <= D); g++)
    for (f = (D == 7); f <= (7 <= D); f++)
    for (e = (D == 6); e <= (6 <= D); e++)
    for (d = (D == 5); d <= (5 <= D); d++)
    for (c = (D == 4); c <= (4 <= D); c++)
    for (b = (D == 3); b <= (3 <= D); b++)
    for (a = (D == 2); a <= (2 <= D); a++) {
        /* R is the result here. Each variable is shifted and bitwise-ORd with the
           others to generate a number representing the string.

           For instance, (()) would be 1100, and ()(()) would be 101100. */
        R=C<<29|B<<28|A<<27|z<<26|y<<25|x<<24|w<<23|v<<22|u<<21|t<<20|s<<19|r<<18|
          q<<17|p<<16|o<<15|n<<14|m<<13|l<<12|k<<11|j<<10|i<<9|h<<8|g<<7|f<<6|
          e<<5|d<<4|c<<3|b<<2|a<<1;
        // If there is an uneven balance of parens, then just jump to the loop end.
        if(__builtin_popcount(R)!=Z) goto X;
        // F here is the number of opening parens.
        F=0;
        // E is a counter used to extract each bit.
        for(E=D-1;E;E--)
            // If the bit is set, then increment the number of open parens.
            if(R&1<<E) F++;
            // If the bit wasn't set, then decrement the number of open parens...
            else if(F) F--;
            // ...but, if there were no open parens, then it's unbalanced; jump to the end
            else goto X;
        // E (the bit counter) is already 0.
        // Loop through each bit...
        for(;E<D;E++)
            /* ...and print it out. 40 is the ASCII code for `(`. If the bit
               is set, the ! will negate it, and 0 will be added to the `(`.
               Otherwise, it will turn the left paren into a right paren. */
            putchar(40+!(R&1<<D-E-1));
        // Newline.
        puts("");
        // End of loop.
        X:;
    }
}
</code>```

746-byte version

```<code>#define C(v,n) for(v=(n==D);v<=(n<=D);v++){
void p(Z){unsigned long long R,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D=Z*2,E,F;C(C,30)C(B,29)C(A,28)C(z,27)C(y,26)C(x,25)C(w,24)C(v,23)C(u,22)C(t,21)C(s,20)C(r,19)C(q,18)C(p,17)C(o,16)C(n,15)C(m,14)C(l,13)C(k,12)C(j,11)C(i,10)C(h,9)C(g,8)C(f,7)C(e,6)C(d,5)C(c,4)C(b,3)C(a,2)R=(C<<29)|(B<<28)|(A<<27)|(z<<26)|(y<<25)|(x<<24)|(w<<23)|(v<<22)|(u<<21)|(t<<20)|(s<<19)|(r<<18)|(q<<17)|(p<<16)|(o<<15)|(n<<14)|(m<<13)|(l<<12)|(k<<11)|(j<<10)|(i<<9)|(h<<8)|(g<<7)|(f<<6)|(e<<5)|(d<<4)|(c<<3)|(b<<2)|(a<<1);if(__builtin_popcount(R)!=Z)continue;F=0;for(E=D-1;E;E--)if(R&(1<<E))F++;else if(F)F--;else goto X;for(;E<D;E++)putchar('('+!(R&(1<<D-E-1)));puts("");X:;}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
</code>```

Body:
C, <s>748</s> <s>746</s> 651 bytes

#define C(v,n) for(v=n==D;v<=(n<=D);v++)
void p(Z){unsigned long long R,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D=Z*2,E,F;C(C,30)C(B,29)C(A,28)C(z,27)C(y,26)C(x,25)C(w,24)C(v,23)C(u,22)C(t,21)C(s,20)C(r,19)C(q,18)C(p,17)C(o,16)C(n,15)C(m,14)C(l,13)C(k,12)C(j,11)C(i,10)C(h,9)C(g,8)C(f,7)C(e,6)C(d,5)C(c,4)C(b,3)C(a,2){R=C<<29|B<<28|A<<27|z<<26|y<<25|x<<24|w<<23|v<<22|u<<21|t<<20|s<<19|r<<18|q<<17|p<<16|o<<15|n<<14|m<<13|l<<12|k<<11|j<<10|i<<9|h<<8|g<<7|f<<6|e<<5|d<<4|c<<3|b<<2|a<<1;if(__builtin_popcount(R)!=Z)goto X;F=0;for(E=D-1;E;E--)if(R&1<<E)F++;else if(F)F--;else goto X;for(;E<D;E++)putchar(40+!(R&1<<D-E-1));puts("");X:;}}

At a whopping >600 bytes, this isn't really much of a contender...but it's pretty fast and memory efficient.

Works by encoding the parentheses strings as integers, with a set bit representing ( and an unset bit representing ). For instance, (()) would be 1100. I made the following observations:

All permutations must begin with ( and end with ); otherwise, it won't be valid.

Every valid permutation must have n left parentheses and n right parentheses, where n is the input number. I used __builtin_popcount for this.

When built via icc -march=native -O3, it takes 17s on my computer, though others have reported better times (~3-7s) on their (presumably faster) computers. In addition, it uses around 1.5 KB of memory.

Here's the code with explanatory comments:

// Z is the input number.
void p(Z){
    // All the variables.
    // R is the resulting paren number, with 1 bits for open parens and 0s for closed ones.
    // a-C are used to hold the state of each paren (1 if open, 0 if closed).
    // D holds Z*2, or the total length of the paren string.
    // E and F are used later on.
    unsigned long long R,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D=Z*2,E,F;
    /* Each loop performs a basic check. If D is equal to the corresponding
       number, then the variable will start at 1 (since the first paren must
       always be open). If D is greater than or equal to the number, then the loop
       will only be run once with the variable set to 0, and a later check will
       cause the variable to be ignored. Otherwise, it will loop twice; one for a
       closed paren (0), and one for an open one (1). Of course, if D == the
       number, then it will only loop for the open paren (as stated above). */
    for (C = (D == 30); C <= (30 <= D); C++)
    for (B = (D == 29); B <= (29 <= D); B++)
    for (A = (D == 28); A <= (28 <= D); A++)
    for (z = (D == 27); z <= (27 <= D); z++)
    for (y = (D == 26); y <= (26 <= D); y++)
    for (x = (D == 25); x <= (25 <= D); x++)
    for (w = (D == 24); w <= (24 <= D); w++)
    for (v = (D == 23); v <= (23 <= D); v++)
    for (u = (D == 22); u <= (22 <= D); u++)
    for (t = (D == 21); t <= (21 <= D); t++)
    for (s = (D == 20); s <= (20 <= D); s++)
    for (r = (D == 19); r <= (19 <= D); r++)
    for (q = (D == 18); q <= (18 <= D); q++)
    for (p = (D == 17); p <= (17 <= D); p++)
    for (o = (D == 16); o <= (16 <= D); o++)
    for (n = (D == 15); n <= (15 <= D); n++)
    for (m = (D == 14); m <= (14 <= D); m++)
    for (l = (D == 13); l <= (13 <= D); l++)
    for (k = (D == 12); k <= (12 <= D); k++)
    for (j = (D == 11); j <= (11 <= D); j++)
    for (i = (D == 10); i <= (10 <= D); i++)
    for (h = (D == 9); h <= (9 <= D); h++)
    for (g = (D == 8); g <= (8 <= D); g++)
    for (f = (D == 7); f <= (7 <= D); f++)
    for (e = (D == 6); e <= (6 <= D); e++)
    for (d = (D == 5); d <= (5 <= D); d++)
    for (c = (D == 4); c <= (4 <= D); c++)
    for (b = (D == 3); b <= (3 <= D); b++)
    for (a = (D == 2); a <= (2 <= D); a++) {
        /* R is the result here. Each variable is shifted and bitwise-ORd with the
           others to generate a number representing the string.

           For instance, (()) would be 1100, and ()(()) would be 101100. */
        R=C<<29|B<<28|A<<27|z<<26|y<<25|x<<24|w<<23|v<<22|u<<21|t<<20|s<<19|r<<18|
          q<<17|p<<16|o<<15|n<<14|m<<13|l<<12|k<<11|j<<10|i<<9|h<<8|g<<7|f<<6|
          e<<5|d<<4|c<<3|b<<2|a<<1;
        // If there is an uneven balance of parens, then just jump to the loop end.
        if(__builtin_popcount(R)!=Z) goto X;
        // F here is the number of opening parens.
        F=0;
        // E is a counter used to extract each bit.
        for(E=D-1;E;E--)
            // If the bit is set, then increment the number of open parens.
            if(R&1<<E) F++;
            // If the bit wasn't set, then decrement the number of open parens...
            else if(F) F--;
            // ...but, if there were no open parens, then it's unbalanced; jump to the end
            else goto X;
        // E (the bit counter) is already 0.
        // Loop through each bit...
        for(;E<D;E++)
            /* ...and print it out. 40 is the ASCII code for `(`. If the bit
               is set, the ! will negate it, and 0 will be added to the `(`.
               Otherwise, it will turn the left paren into a right paren. */
            putchar(40+!(R&1<<D-E-1));
        // Newline.
        puts("");
        // End of loop.
        X:;
    }
}

746-byte version

#define C(v,n) for(v=(n==D);v<=(n<=D);v++){
void p(Z){unsigned long long R,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D=Z*2,E,F;C(C,30)C(B,29)C(A,28)C(z,27)C(y,26)C(x,25)C(w,24)C(v,23)C(u,22)C(t,21)C(s,20)C(r,19)C(q,18)C(p,17)C(o,16)C(n,15)C(m,14)C(l,13)C(k,12)C(j,11)C(i,10)C(h,9)C(g,8)C(f,7)C(e,6)C(d,5)C(c,4)C(b,3)C(a,2)R=(C<<29)|(B<<28)|(A<<27)|(z<<26)|(y<<25)|(x<<24)|(w<<23)|(v<<22)|(u<<21)|(t<<20)|(s<<19)|(r<<18)|(q<<17)|(p<<16)|(o<<15)|(n<<14)|(m<<13)|(l<<12)|(k<<11)|(j<<10)|(i<<9)|(h<<8)|(g<<7)|(f<<6)|(e<<5)|(d<<4)|(c<<3)|(b<<2)|(a<<1);if(__builtin_popcount(R)!=Z)continue;F=0;for(E=D-1;E;E--)if(R&(1<<E))F++;else if(F)F--;else goto X;for(;E<D;E++)putchar('('+!(R&(1<<D-E-1)));puts("");X:;}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}