Python 101, second round entrance exam

README.md

https://gist.github.com/RadoRado/90ca673734a168d21b5019474e5b1f38

Stranger forms

Ivan and his friends love going to the cinema.

But when it comes to picking seats, they don't like the usual & boring "next to each other in one row" placement.

That's why they always pick their seats in a strange way. Maria should be above Ivan. Georgi should be to the right of Maria. Veronika should be above Maria.

And when they are done, they can take really strange forms (at least, strange in the eyes of the cinema owners).

Here's a way they can be placed, using the description above:

...*..V.*****..
..*..*MG..*.*..
....*.I...*....

Where:

• . represents an empty seat.
• * represents a reserved seat.
• I, M, G and V are the first letters of the respective people.

The task

You'll be represented with an input, including the layout of the cinema & the configuration our friends want to take.

In a language of your choice, implement a program that outputs all possible combinations of placements, that are possible with the given form.

At the end, output the number of those possible configurations.

Possible configuration is a configuration where:

• Our friends can book seats in the way they want.
• They are not going outside of the cinema.
• They are not taking any already reserved seats.

Input format

Here's one example input:

10 10
..*...*.**
.....**...
*.*...*..*
.**....*.*
...*..*.*.
.***...*..
*......*.*
.....**..*
..*.*.*..*
***.*.**..
6
A
BAA
FRA
CAB
DRC
EAD
GLE

Lets break it down:

• The first line - 10 10 represents the width & height of the cinema.
• The next 10 lines (the height) are the cinema layout itself. . is free, * is reserved.
• Next line - 6 - represents the numbre of configurations that our friends wants to make.
• Next line - A - that's the first letter of the name of someone, who is going to be "central" for the configuration.
• Next line - BAA - means - person with name B will be Above the person with name A.
• Next line - FRA - means - person with name F will be Right of the person with name A.
• Next line - CAB - means - person with name C will be Above the person with name B.
• Next line - DRC - means - person with name D will be Right of person with name C.
• Next line - EAD - means - person with name E will be Above the person with name D.
• Next line - GLE means - person with name G will be Left of the person with name E.

Few things to consider:

• The input will be correct - there won't be 2 people occupying the same place.
• All names are going to be unique.
• There won't be a configuration for someone not being previously introduced.

Example

If we take the example input from above, given to stdin, our program should output all possible configurations for our friends in the cinema layout:

 0123456789
0..*GE.*.**
1...CD**...
2*.*B..*..*
3.**AF..*.*
4...*..*.*.
5.***...*..
6*......*.*
7.....**..*
8..*.*.*..*
9***.*.**..
----------
 0123456789
0..*...*.**
1.....**...
2*.*.GE*..*
3.**.CD.*.*
4...*B.*.*.
5.***AF.*..
6*......*.*
7.....**..*
8..*.*.*..*
9***.*.**..
----------
 0123456789
0..*...*.**
1.....**...
2*.*...*..*
3.**.GE.*.*
4...*CD*.*.
5.***B..*..
6*...AF.*.*
7.....**..*
8..*.*.*..*
9***.*.**..
----------
3

For convinience, we've printed the row & col numbers (starting from 0). This is not necessary but it's going to be counted as an "extra", if done so.

Forms.java

/*
 * This program seats all correct configurations in a cinema salon.
 * I have taken left and right to be the mirror view left and right
 * not the ususal left and right for the people in the seats
 * as is the case in the example output.
 * 
 * Credit goes to Ivan Petrov who gave the idea of using switch - case and helped simplify my solution in other ways.
 * I don't know if I would have been able to finish in time and with such minimal implementation if he did not help.
 */
package forms;


import java.util.Arrays;
import java.util.Hashtable;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

/**
 *
 * @author Georgi Karapetrov
 */
public class Forms {
    //the firs set of variables allows to declare arrays in the prompt body
    //hoping that the input will be correct
    private final int rows;
    private final int cols;
    private final int instructionsCount;
    
    //stores the input salon configuration
    private final String[][] matrix;
    // deep clone of matrix
    private String[][] clone; 
    
    // store the names and their seating coordinates
    //with respct to the central name with coordinates [0,0]
    private final Hashtable<String, int[]> centralisedCoords; 
    

    //this constructor uses a user prompt and centalises the data
    public Forms()
    {
        this.centralisedCoords = new Hashtable<String, int[]>();
        Scanner input = new Scanner(System.in);
        
        //the first line gives us the salon dimensions
        String[] coords = input.nextLine().split(" ");
                
        rows = Integer.parseInt(coords[1]);
        cols = Integer.parseInt(coords[0]);
                
        this.matrix = new String[rows][cols];

        //populate the matrix
        for(int row = 0; row<rows; row++) {
            String line = input.nextLine();
            for(int col = 0; col<cols; col++) {
                this.matrix[row ][col] = line.substring(col, col+1);
            }
        }
        
        //next comes the number of instructions
        instructionsCount = Integer.parseInt(input.nextLine());
        
        //take the central element
        this.centralisedCoords.put(input.nextLine(), new int[]{0,0});
        //System.out.println(Arrays.toString(centralisedCoords.get( "A"  )));
        
        //the rest of the instructions
        for(int i = 0; i < instructionsCount; i++){
            String line = input.nextLine();
            String targetPerson = line.substring(0, 1);
            String referencePerson = line.substring(2, 3);
            String instruction = line.substring(1, 2);
            int[] delta = new int[2];
                
            //dictionary
            switch(instruction) {
                case "L":
                    delta[0] = 0;
                    delta[1] = -1;
                    break;
                case "R":
                    delta[0] = 0;
                    delta[1] = 1;
                    break;
                case "A":
                    delta[0] = -1;
                    delta[1] = 0;
                    break;
                case "B":
                    delta[0] = 1;
                    delta[1] = 0;
                    break;
            }
                
            int[] newCoordinates = new int[2];
            int[] referenceCoordinates = centralisedCoords.get(  referencePerson  );
            
            //luckily the translation is transitive
            newCoordinates[0] = referenceCoordinates[0] + delta[0];
            newCoordinates[1] = referenceCoordinates[1] + delta[1];
            
            //set
            this.centralisedCoords.put( targetPerson , newCoordinates);
        }
        // declare a resetable initial copy of the salon
        clone = new String[rows][cols];
    }
    
    //get
    public String[][] getSalon(){
        return this.matrix;
    }
    
    //get
    public Hashtable<String, int[]> getCoords(){
        return this.centralisedCoords;
    }
    
    //set clone to initial salon
    private String[][] resetClone() {        
        final String[][] clone = new String[matrix.length][];
        
        for (int row = 0; row < matrix.length; row++) {
            clone[row] = Arrays.copyOf(matrix[row], matrix[row].length);
        }
        
        return clone;
    }
    
    //maps the desired seating with respect to the central element and a given starting seat
    //this is the main method that follows the dictionary
    //and tries to map the seating fonfiguration on to the salon,
    //with respect to the central element only in order to avoid repeating solutions
    //this method also counts the solution in traversing the salon
    private boolean printIfValid(int startRow, int startCol, Set<Map.Entry<String,int[]>> entries, String[][] dummySolution)
    {
        int instructionCounter = 0;
        //for the set of instructions, follow each instruction
        //iff within the seating margins and if the seat in iteration is available
        for (Map.Entry<String, int[]> entry : entries) {
            String name = entry.getKey();
            int[] coordinates = entry.getValue();
            
            int x = startRow + coordinates[0];
            int y = startCol + coordinates[1];
            
            boolean isSafe = x >= 0 && y >= 0 && x < rows && y < cols && ".".equals(matrix[x][y]);
            
            if ( isSafe ) {
                dummySolution[x][y] = name;
            }
            
            else {
               break;
            }
            
            //print if also the last instruction has been carried out
            if( instructionCounter == entries.size() - 1) {
                this.print(dummySolution);
                return true;
            }
            
            instructionCounter++;
        }
        return false;
    }
    
    //format the printing in printIfValid()
    private void print( String[][] solution )
    {
        //print column indices
        System.out.print( " " );
        for(int j = 0; j<cols; j++)
        {
            System.out.print( j );
        }
        System.out.println( );
        
        //print the solution
        for (int i=0; i < rows; i++)
        {
            //print the row index
            System.out.print( i );
            
            //print the row
            for (int j=0; j < cols; j++)
            {
                System.out.print( solution[i][j] );
            }
            System.out.println();
        }
        //print end of solution delim
        System.out.println("----------");
    }
    
    //calls printIfValid()
    public void traverse(){
        int solutionCounter = 0;
        
        for(int row = 0; row < rows; row++) 
        {
            for(int col = 0; col < cols; col++)
            {
                
                if( printIfValid(row, col, centralisedCoords.entrySet(), this.resetClone() ) )
                {
                    solutionCounter++;
                }
            }
        }
        System.out.println( solutionCounter );
    }
    
    public static void main(String[] args) {
        Forms myCinema = new Forms();
        myCinema.traverse();
    }   
}