Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Task

A theatre has 10 rows, labelled A to J from front to back, and 15 seats in each row, numbered 1 to 15 from left to right.

The program uses the following rules to choose the best seats.

  • Rule 1: All seats in one booking must be in the same row, next to each other.
  • Rule 2: The seats must be as close to the front as possible, then as close to the left as possible (lowest letter, then lowest number)

Write a function which takes the number of tickets wanted as an integer input (n), and outputs the best seats available in a list of length n.

Your program should:

  • Output -1 if 1 > Input or Input > 15*
  • Output -1 if the seats aren't available*
  • Have a function B(n) that the user can use to input the desired number of seats.

*You can output the -1 in a list if it makes it easier

Examples

I/O

Calling B(5) on a new array should return [A1, A2, A3, A4, A5]
Calling B(2) after that should then return [A6, A7]
Calling B(10) after that should then return [B1, B2, ... B9, B10]
Calling B(-1) should always return -1

Un-golfed Solution 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
share|improve this question
1  
Is "Have hardcoded a list of seats in a two dimensional array" necessary? There are numerous ways to do this without that; the requirement really restricts solutions. –  Quincunx May 23 at 1:42
2  
You say the 2-D array must be hard-coded, but your Python example doesn't even hard-code it, it uses a comprehension to create a new list at runtime. –  Tony H. May 23 at 1:53
6  
Why even mention "a list of seats in a two dimensional array"? That sounds like an implementation detail and if somebody creates a program that satisfies the required output without using an array, there should be no problem with that. –  Greg Hewgill May 23 at 2:19
2  
what if input is 0? –  edc65 May 23 at 15:17
1  
@edc65 I always make my nonexistent movie theater patrons sit in the best spot of the theater, on another patron's lap if need be. They never notice. –  Adam Davis May 23 at 15:56

13 Answers 13

JavaScript - 172

Function itself is 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;}

Input:

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

Output:

-1
-1
[ 'A1', 'A2', 'A3', 'A4' ]
[ 'B1', 'B2', 'B3', 'B4', 'B5', 'B6', 'B7', 'B8', 'B9', 'B10', 'B11', 'B12', 'B13', 'B14', 'B15' ]
[ 'A5' ]
-1
share|improve this answer

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

Demo here: http://jsfiddle.net/tBu5G/

Some ideas taken from @edc65

share|improve this answer
    
c[B[a]=b] instead of c[],B[a]=b is clever, but fails for n=0 –  edc65 May 24 at 7:25
    
@edc65 nice catch. I've now adjusted it to handle the case n=0 –  nderscore May 24 at 15:16
    
Awesome. That's something to remember to avoid 'return' - thanks for sharing (+1) –  edc65 May 25 at 21:41
    
@edc65 thanks! I thought it was interesting. MT0's got us both beat though! :P –  nderscore May 25 at 21:45

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)

Some adjustments had to be made to make this a function in Haskell: b returns a pair: the tickets (if possible), and the new state of the theater. t is the initial theater state, with all tickets unsold. Also, returning -1 was unnatural for Haskell, so if no tickets can be issued for a request, the empty list is returned for the tickets.

λ: 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"]
share|improve this answer

Javascript (E6) 99 103 113 121

Really you just need to store a number for each row

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}

Test

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

Ungolfed

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;
}
share|improve this answer

JavaScript (ECMAScript 6 Draft) - 96 95 91 Characters

A recursive solution:

Version 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

Version 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)

(Thanks to nderscore for the inspiration for the 1 character saving)

Version 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)

(Thanks to nderscore)

Explanation:

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.
  }
}
share|improve this answer
    
Nice solution. I was working on something similar. Here's -1 byte: 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 May 25 at 21:42
    
Thanks, unfortunately that one doesn't quite work as you can't book row J but negating the first check to give 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) should work. –  MT0 May 25 at 22:16
    
Ah, good catch. –  nderscore May 25 at 22:24
    
And it keeps going lower... (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 May 26 at 6:59

APL (75)

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

Test:

      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  

Explanation:

  • T←10 15⍴0: T is a 15-by-10 matrix that holds the theater state (0 = free)
  • B←{...}: the function
    • (⍵∊⍳15): if is a member of the set of integers from 1 to 15,
    • ∨/Z←,T⍷⍨⍵/0: and T contains zeroes in a row (storing possible start points in Z),
    • :: then:
      • (⊃Z/,⍳⍴T): select possible start coordinates, and take the first one,
      • ∘+¨1-⍨⍳1⍵: add ⍵-1 more positions to the right of the start coordinate
      • P←: store the coordinates in P
      • {⎕A[⍺],⍕⍵}/¨: format the coordinates
      • T[P]←: store the formatted coordinates at their places in T. (any nonzero values in T will do)
      • +: return the result, which is the formatted coordinates (the result of an assignment is tacit by default)
    • ⋄¯1: otherwise, return ¯1.
share|improve this answer

GolfScript, 103 82 bytes

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

Examples

$ 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

How it works

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.
}
share|improve this answer

CoffeeScript - 171 150 149

I suspect Ruby or Perl will beat this out before long.

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

Equivalent JavaScript/Explanation:

For those unfamiliar with 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;
}

Try it online.

share|improve this answer
1  
This solution doesn't satisfy the rule All seats in one booking must be in the same row, next to each other. –  nderscore May 23 at 4:26

Cobra - 309

This should do it, but I can't actually get to a compiler for a few hours, so I'll update it later if needed.

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'])
share|improve this answer

C# - 289

First attempt at code golfing.

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;}

Un-golfed

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;
}
share|improve this answer

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]]}

There are undoubtedly numerous improvements to be made here

share|improve this answer

C++ - 257

Also a first attempt at golfing.

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;
}

Because to_string wasn't working with my compiler, toS is defined as

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

And as a little interface

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;
}
share|improve this answer
1  
Just removing unnecessary whitespace brings it down to 243 characters. –  tomsmeding May 23 at 15:30
    
More golfing to 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.emp‌​ty())o.push_back("-1");return o;} –  tomsmeding May 23 at 15:38

C# - 268 Bytes

Golfed code:

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;}

Ungolfed code:

    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;
    }

I would have written some annotations into a comment on GoldenDragon's solution instead of making my own, but my reputation doesn't allow it.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.