Asientos del teatro

12

Tarea

Un teatro tiene 10 filas, etiquetadas Aa Jde adelante hacia atrás, y 15 asientos en cada fila, numeradas del 1 al 15 de izquierda a derecha.

El programa utiliza las siguientes reglas para elegir los mejores asientos.

  • Regla 1: Todos los asientos en una reserva deben estar en la misma fila, uno al lado del otro.
  • Regla 2: Los asientos deben estar lo más cerca posible del frente, luego lo más cerca posible de la izquierda (letra más baja, luego el número más bajo)

Escriba una función que tome el número de tickets deseados como una entrada entera ( n) y genere los mejores asientos disponibles en una lista de longitud n.

Tu programa debe:

  • Salida -1si 1> Entrada o Entrada> 15 *
  • Salida -1si los asientos no están disponibles *
  • Tiene una función B(n)que el usuario puede usar para ingresar el número deseado de asientos.

* Puede generar el -1 en una lista si lo hace más fácil

Ejemplos

I / O

Llamar B(5)a una nueva matriz debería devolver [A1, A2, A3, A4, A5]
Llamar B(2)después de eso debería devolver [A6, A7]
Llamar B(10)después de eso debería regresar [B1, B2, ... B9, B10]
Llamar B(-1)siempre debería regresar-1

Solución sin golf Python

Theatre = [ [False] * 16 ] * 11

def B(n):
    if 0 <= n <= 15:         
        for i in range(10):
            for j in range(15-n+1):
                try:
                    if not Theatre[i][j]:
                        if not Theatre[i][j + n]:
                            row = i
                            start = j
                            List = []
                            for q in range(n):
                                List.append(chr(row + 65) + str(start + q + 1))
                                Theatre[row][start + q] = True
                            return List
                except:
                    break
    return -1
Harry Beadle
fuente
1
¿Es necesario "haber codificado una lista de asientos en una matriz bidimensional"? Existen numerosas formas de hacer esto sin eso; El requisito realmente restringe las soluciones.
Justin
2
Dices que la matriz 2-D debe estar codificada, pero tu ejemplo de Python ni siquiera lo codifica, utiliza una comprensión para crear una nueva lista en tiempo de ejecución.
Tony Ellis
66
¿Por qué incluso mencionar "una lista de asientos en una matriz bidimensional"? Eso suena como un detalle de implementación y si alguien crea un programa que satisfaga la salida requerida sin usar una matriz, no debería haber ningún problema con eso.
Greg Hewgill
2
¿Qué pasa si la entrada es 0?
edc65
1
@ edc65 Siempre hago que mis clientes inexistentes del cine se sienten en el mejor lugar del teatro, en el regazo de otro cliente si es necesario. Nunca se dan cuenta.
Adam Davis

Respuestas:

4

JavaScript - 172

La función en sí es 172:

//build persistent seats
m=[];
for(i=10;i--;){m[i]={r:String.fromCharCode(i+65),s:[]};for(j=0;j<15;j++)m[i].s.push(j+1);}

function b(z){for(i=0;i<m.length;i++)for(j=0,u=m[i].s.length;o=[],j<u;j++)if(u>=z&z>0){for(m[i].s=m[i].s.slice(z),p=m[i].s[0]||16;o[--z]=m[i].r+--p,z;);return o;}return-1;}

Entrada:

console.log(b(-1));
console.log(b(0));
console.log(b(4));
console.log(b(15));
console.log(b(1));
console.log(b(20));

Salida:

-1
-1
[ 'A1', 'A2', 'A3', 'A4' ]
[ 'B1', 'B2', 'B3', 'B4', 'B5', 'B6', 'B7', 'B8', 'B9', 'B10', 'B11', 'B12', 'B13', 'B14', 'B15' ]
[ 'A5' ]
-1
Mate
fuente
4

Javascript ( ES6 ) - 130 127 107 101 98

B=n=>(a=>{for(;n>0&a<9;)if((b=~~B[++a]+n)<16)for(B[a]=b;n--;)c[n]='ABCDEFGHIJ'[a]+b--})(c=[-1])||c

Demostración aquí: http://jsfiddle.net/tBu5G/

Algunas ideas tomadas de @ edc65

nderscore
fuente
c [B [a] = b] en lugar de c [], B [a] = b es inteligente, pero falla para n = 0
edc65
@ edc65 buena captura. Ahora lo he ajustado para manejar el cason=0
nderscore
Increíble. Eso es algo para recordar para evitar el 'retorno' - gracias por compartir (+1)
edc65
@ edc65 gracias! Pense que era interesante. ¡MT0 nos tiene vencidos a los dos! : P
nderscore
3

Haskell, 129

t=[[a:show s|s<-[1..15]]|a<-['A'..'J']]
b n=(n%).span((<n).length)
_%(h,[])=([],h)
n%(j,(r:s))=let(t,u)=splitAt n r in(t,j++u:s)

Hubo que hacer algunos ajustes para que esto funcionara en Haskell: bdevuelve un par: las entradas (si es posible) y el nuevo estado del teatro. tes el estado inicial del teatro, con todas las entradas sin vender. Además, regresar -1no era natural para Haskell, por lo que si no se pueden emitir boletos para una solicitud, se devuelve la lista vacía para los boletos.

λ: let (k1,t1) = b 5 t
λ: k1
["A1","A2","A3","A4","A5"]

λ: let (k2,t2) = b 2 t1
λ: k2
["A6","A7"]

λ: let (k3,t3) = b 10 t2
λ: k3
["B1","B2","B3","B4","B5","B6","B7","B8","B9","B10"]

λ: let (k4,t4) = b (-1) t3
λ: k4
[]

λ: let (k5,t5) = b 2 t4
λ: k5
["A8","A9"]
MtnViewMark
fuente
3

APL (75)

T←10 15⍴0⋄B←{(⍵∊⍳15)∧∨/Z←,T⍷⍨⍵/0:+T[P]←{⎕A[⍺],⍕⍵}/¨P←(⊃Z/,⍳⍴T)∘+¨1-⍨⍳1⍵⋄¯1}

Prueba:

      B 5
  A1    A2    A3    A4    A5  
      B 2
  A6    A7  
      B 10
  B1    B2    B3    B4    B5    B6    B7    B8    B9    B10  
      B ¯1
¯1
      B 3
  A8    A9    A10  

Explicación:

  • T←10 15⍴0: Tes una matriz de 15 por 10 que contiene el estado del teatro (0 = libre)
  • B←{... }: la función
    • (⍵∊⍳15): si es miembro del conjunto de enteros del 1 al 15,
    • ∨/Z←,T⍷⍨⍵/0: y Tcontiene ceros seguidos (almacenando posibles puntos de inicio Z),
    • :: luego:
      • (⊃Z/,⍳⍴T): seleccione las posibles coordenadas de inicio y tome la primera,
      • ∘+¨1-⍨⍳1⍵: agrega ⍵-1más posiciones a la derecha de la coordenada de inicio
      • P←: almacenar las coordenadas en P
      • {⎕A[⍺],⍕⍵}/¨: formatear las coordenadas
      • T[P]←: almacena las coordenadas formateadas en sus lugares en T. (cualquier valor distinto de cero en T servirá)
      • +: devuelve el resultado, que son las coordenadas formateadas (el resultado de una asignación es tácito por defecto)
    • ⋄¯1: de lo contrario, volver ¯1.
marinus
fuente
3

Javascript (E6) 99103113121

Realmente solo necesitas almacenar un número para cada fila

B=n=>{for(r=i=[-1];n>0&i++<9;)if((a=~~B[i]+n)<16)for(B[i]=a;n--;)r[n]='ABCDEFGHIJ'[i]+a--;return r}

Prueba

'5:'+B(5)+'\n2:'+B(2)+'\n10:'+B(10)+'\n0:'+B(0)+'\n1:'+B(-1))+'\n3:'+B(3)

Sin golf

B = n => {
  for (r = i = [-1]; n > 0 & i++ < 9;)
    if ((a = ~~B[i] + n) < 16)
      for (B[i] = a; n--; ) r[n] = 'ABCDEFGHIJ'[i] + a--;
  return r;
}
edc65
fuente
3

JavaScript (borrador de ECMAScript 6) - 96 95 91 caracteres

Una solución recursiva:

Versión 1

B=(n,r=0)=>n>0&&(k=~~B[r])+n<16?[...Array(n)].map(_=>'ABCDEFGHIJ'[r]+(B[r]=++k)):r<9?B(n,r+1):-1

Versión 2:

B=(n,r=0)=>n<1|r>9?-1:(k=B[r]|0)+n<16?[...Array(n)].map(_=>'ABCDEFGHIJ'[r]+(B[r]=++k)):B(n,r+1)

(Gracias a nderscore por la inspiración para guardar 1 personaje)

Versión 3:

B=(n,r=0)=>n<1|r>9?-1:(B[r]^=0)+n<16?[...Array(n)].map(_=>'ABCDEFGHIJ'[r]+ ++B[r]):B(n,r+1)

(Gracias a nderscore )

Explicación:

B = function(n,r=0)          // Create a function B with arguments:
                             // - n is the number of seats to book
                             // - r is the row number (defaults to 0)
{
  var k = ~~B[r];            // get the number of seats already booked in row r
  if (  n > 0                // ensure that n is a valid booking
     && k+n<16 )             // check that there are enough seats remaining in row r
  {
    var P = new Array(n);    // Create an array with length n with no elements initialised
    var Q = [...P];          // Use P to create an array with every element
                             // initialised to undefined
    var R = 'ABCDEFGHIJ'[r]; // get the row ID.
    B[r] = k + n;            // Increment the number of seats booked in row r by n.
    var S = Q.map(
      function(){
        return R + (++k);    // Map each value of Q to the row ID concatenated with
                             // the seat number.
      }
    );
    return S;                // Return the array of seats.
  }
  else if ( r < 9 )          // If there are more rows to check
  {
    return B(n,r+1);         // Check the next row.
  }
  else                       // Else (if n is invalid or we've run out of rows)
  {
    return -1;               // Return -1.
  }
}
MT0
fuente
Buena solución Estaba trabajando en algo similar. Aquí es -1 bytes:B=(n,r=0)=>n>0&r<9?(k=B[r]|0)+n<16?[...Array(n)].map(_=>'ABCDEFGHIJ'[r]+(B[r]=++k)):B(n,r+1):-1
nderscore
Gracias, desafortunadamente, esa no funciona del todo, ya que no se puede reservar la fila J, pero negar el primer cheque para dar B=(n,r=0)=>n<1|r>9?-1:(k=B[r]|0)+n<16?[...Array(n)].map(_=>'ABCDEFGHIJ'[r]+(B[r]=++k)):B(n,r+1)debería funcionar.
MT0
Ah, buena captura.
nderscore
Y sigue bajando ... (91)B=(n,r=0)=>n<1|r>9?-1:(B[r]^=0)+n<16?[...Array(n)].map(_=>'ABCDEFGHIJ'[r]+ ++B[r]):B(n,r+1)
nderscore
2

GolfScript, 103 82 bytes

226,1>15/[0]*:T{:&0>{T[{),&~)>:|T\/,2=}?]{T|-:T;|{(.[15/65+]\15%)`+}%}-1if}-1if}:B

Ejemplos

$ cat theatre.gs
226,1>15/[0]*:T
{:&0>{T[{),&~)>:|T\/,2=}?]{T|-:T;|{(.[15/65+]\15%)`+}%}-1if}-1if}:B

5  B p  # Execute B(5), stringify and print.
2  B p
15 B p
17 B p
0  B p

{}:puts # Disable automatic output.
$
$ golfscript theatre.gs
["A1" "A2" "A3" "A4" "A5"]
["A6" "A7"]
["B1" "B2" "B3" "B4" "B5" "B6" "B7" "B8" "B9" "B10" "B11" "B12" "B13" "B14" "B15"]
-1
-1

Cómo funciona

226,1>           # Push the array [ 1 … 225 ].
15/[0]*          # Split in chunks of 15 elements and join separating by zeros.
:T               # Save result in T.
{                #
  :&0>           # Save the function's argument in & and check if it's positive.
  {              # If it is:
    T[{          # For each seat S in T:
      ),         # Push [ 0 … S ].
      &~)>       # Reduce two [ S-(&-1) … S ].
      :|         # Save the result in |.
      T\/        # Split T around |.
      ,2=        # If there are two chunks, the seats are available.
    }?]          # Find the first S that satisfies the above condition.
    {            # If there was a match:
      T|-:T;     # Remove the seats in | from T.
      |{         # For each seat S in |:
        (.       # Push S+1 S+1.
        [15/65+] # Compute (S+1)/15+65; the ASCII character corresponding to the row.
        \15%)`+  # Compute (S+1)%15+1, stringify and concatenate. 
      }%         #
    }            #
    -1if         # If there was no match, push -1 instead.
  }              #
  -1if           # If the argument was non-positive, push -1 instead.
}
Dennis
fuente
1

CoffeeScript - 171 150 149

Sospecho que Ruby o Perl superarán esto en poco tiempo.

c=0;l=64;k=1
f=(n)->
 if n<0 or n>15 or 150-c<n
  return-1
 a=[]
 for i in[1..n]
  if c%15==0
   ++l;k=1
  ++c;a.push String.fromCharCode(l)+k;++k
 a

JavaScript equivalente / Explicación :

Para aquellos que no están familiarizados con CoffeeScript.

var seats  = 0; //Occupied seats.
var letter = 64; //ASCII code for row letter.
var index  = 1;  //Index of seat in row.

function seats( count )
{
    if( count < 0 || count > 15 || ( 150 - seats ) < count )
        return -1;

    var assignedSeats = [];

    for( var i = 1; i <= count; ++i )
    {
        if( ( seats % 15 ) === 0 )
        {
            ++letter;
            index = 1;
        }

        ++seats; //Occupy a seat.
        assignedSeats.push( String.fromCharCode( letter ) + index );
        ++index;
    }

    return assignedSeats;
}

Pruébalo en línea .

Tony Ellis
fuente
1
Esta solución no satisface la reglaAll seats in one booking must be in the same row, next to each other.
nderscore
0

Cobra - 309

Esto debería hacerlo, pero en realidad no puedo llegar a un compilador durante unas horas, así que lo actualizaré más tarde si es necesario.

class P
    var s=List<of List<of String>>()
    def main
        for l in 'ABCDEFGHIJ'
            t=[]
            for n in 1:16,t.insert(0,l.toString+n.toString)
            .s.add(t)
    def b(n) as List<of String>
        t=[]
        for r in .s.count,if .s[r].count>=n
            for i in n,t.add(.s[r].pop)
            break
        return if(n>0 and t<>[],t,['-1'])
Οurous
fuente
0

C # - 289

Primer intento de golf de código.

int[]s=new int[10];string[]B(int n){string[]x=new string[]{"-1"};if(n<1||n>15)return x;int m=(int)Math.Pow(2, n)-1;for(int i=0;i<10;++i){for(int j=0;j<15-n;++j){if((s[i] &m)==0){s[i]|=m;string[]r=new string[n];for(int k=0;k<n;++k)r[k]=(""+(char)(i+65)+(j+k+1));return r;}m<<=1;}}return x;}

Sin golf

int[] s = new int[10];
string[] B(int n)
{
    string[] x = new string[] { "-1" };
    if (n < 1 || n > 15) return x;
    int m = (int)Math.Pow(2, n) - 1;
    for (int i = 0; i < 10; ++i)
    {
        for (int j = 0; j < 15 - n; ++j)
        {
            if ((s[i] & m) == 0)
            {
                s[i] |= m;
                string[] r = new string[n];
                for (int k = 0; k < n; ++k)
                    r[k] = ("" + (char)(i + 65) + (j+k+1));
                return r;
            }
            m <<= 1;
        }
    }
    return x;
}
Dragón dorado
fuente
0

K, 140

d:10#,15#0b
B:{if[(x<0)|x>15;:-1];$[^r:*&&/'~:^a:{(*&&/'{x(!1+(#x)-y)+\:!y}[d x;y])+!y}[;x]'!#d;-1;[.[`d;(r;a r);~:];(10#.Q.A)[r],/:$1+a r]]}

Indudablemente, hay numerosas mejoras para realizar aquí

tmartin
fuente
0

C ++ - 257

También un primer intento de golf.

static vector< int > t (10, 0);

vector<string> b(int n){
    vector<string> o;
    int i=0,j;
    for(;i<10&&16>n&&n>0;i++){
        if(15-t[i]<n) continue;
        char l='A'+i;
        for(j=t[i];j<n+t[i];j++){
           o.push_back(l + toS(j + 1));
        }
        t[i]+=n;
        n=0;
    }
    if(o.empty()) o.push_back("-1");
    return o;
}

Como to_string no funcionaba con mi compilador, toS se define como

string toS(int i){
    return static_cast<ostringstream*>( &(ostringstream() << i) )->str();
}

Y como una pequeña interfaz

int main(){
int input = 0;
bool done = false;
while (!done){
    cout << "how many seats would you like? (0 to exit)\n";
    cin >> input;
    vector<string> selection = b(input);
    for (auto s : selection){
        cout << s << ' ';
    }
    cout << endl;
    if (input == 0) break;
}
return 0;
}
celie56
fuente
1
Solo eliminando espacios en blanco innecesarios lo reduce a 243 caracteres.
tomsmeding
Más golf a 236:vector<int> t(10,0);vector<string> b(int n){vector<string> o;for(int i=0,j;i<10&&16>n&&n>0;i++){if(15-t[i]<n)continue;char l='A'+i;for(j=0;j<n;j++)o.push_back(l+to_string(j+t[i]+1));t[i]+=n;n=0;}if(o.empty())o.push_back("-1");return o;}
tomsmeding
0

C # - 268 bytes

Código de golf:

int[]s=new int[10];string[]B(int n){string[]x={"-1"};if(n<1||n>15)return x;int m=(int)Math.Pow(2,n)-1;for(int i=0;++i<10;){for(int j=0;++j<15-n;){if((s[i]&m)==0){s[i]|=m;var r=new string[n];for(int k=0;++k<n;)r[k]=(""+(char)(i+65)+(j+k+1));return r;}m<<=1;}}return x;}

Código sin golf:

    int[] s = new int[10];
    string[] B(int n)
    {
        string[] x = { "-1" };
        if (n < 1 || n > 15) return x;
        int m = (int)Math.Pow(2, n) - 1;
        for (int i = 0; ++i < 10;)
        {
            for (int j = 0; ++j < 15 - n;)
            {
                if ((s[i] & m) == 0)
                {
                    s[i] |= m;
                    var r = new string[n];
                    for (int k = 0; ++k < n;)
                        r[k] = ("" + (char)(i + 65) + (j + k + 1));
                    return r;
                }
                m <<= 1;
            }
        }
        return x;
    }

Hubiera escrito algunas anotaciones en un comentario sobre la solución de GoldenDragon en lugar de hacer la mía, pero mi reputación no lo permite.

tsavinho
fuente