Theaterbestuhlung

12

Aufgabe

Ein Theater hat 10 Zeilen, etikettieren , Aum Jvon vorne nach hinten, und 15 Sitze in jeder Zeile der Nummern 1 bis 15 von links nach rechts.

Das Programm verwendet die folgenden Regeln, um die besten Plätze auszuwählen.

  • Regel 1: Alle Sitzplätze in einer Buchung müssen in derselben Reihe nebeneinander liegen.
  • Regel 2: Die Sitze müssen so weit vorne wie möglich und dann so weit links wie möglich sein (niedrigster Buchstabe, dann niedrigste Zahl)

Schreiben Sie eine Funktion, die die Anzahl der gewünschten Tickets als Ganzzahleingabe ( n) verwendet und die besten verfügbaren Plätze in einer Längenliste ausgibt n.

Ihr Programm sollte:

  • Ausgang, -1wenn 1> Eingang oder Eingang> 15 *
  • Ausgabe, -1wenn die Plätze nicht verfügbar sind *
  • Haben Sie eine Funktion B(n), mit der der Benutzer die gewünschte Anzahl von Plätzen eingeben kann.

* Sie können -1 in einer Liste ausgeben, wenn dies einfacher ist

Beispiele

I / O

Das Aufrufen B(5)eines neuen Arrays sollte zurückgeben. Das [A1, A2, A3, A4, A5]
Aufrufen B(2)danach sollte zurückgeben. Das [A6, A7]
Aufrufen B(10)danach sollte zurückgeben. Das [B1, B2, ... B9, B10]
Aufrufen B(-1)sollte immer zurückgeben-1

Ungolfed 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
Harry Beadle
quelle
1
Ist "Haben Sie eine Liste der Sitzplätze in einem zweidimensionalen Array fest codiert" erforderlich? Es gibt zahlreiche Möglichkeiten, dies ohne das zu tun; Die Anforderung schränkt die Lösungen wirklich ein.
Justin
2
Sie sagen, das 2D-Array muss fest codiert sein, aber Ihr Python-Beispiel codiert es nicht einmal fest, sondern verwendet ein Verständnis, um zur Laufzeit eine neue Liste zu erstellen.
Tony Ellis
6
Warum überhaupt "eine Liste von Sitzen in einer zweidimensionalen Anordnung" erwähnen? Das klingt nach einem Implementierungsdetail, und wenn jemand ein Programm erstellt, das die erforderliche Ausgabe ohne Verwendung eines Arrays erfüllt, sollte dies kein Problem darstellen.
Greg Hewgill
2
Was ist, wenn der Eingang 0 ist?
edc65
1
@ edc65 Ich lasse meine nicht vorhandenen Kinogäste immer an der besten Stelle des Theaters sitzen, wenn nötig auf dem Schoß eines anderen Benutzers. Sie merken es nie.
Adam Davis

Antworten:

4

JavaScript - 172

Funktion selbst ist 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;}

Eingang:

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

Ausgabe:

-1
-1
[ 'A1', 'A2', 'A3', 'A4' ]
[ 'B1', 'B2', 'B3', 'B4', 'B5', 'B6', 'B7', 'B8', 'B9', 'B10', 'B11', 'B12', 'B13', 'B14', 'B15' ]
[ 'A5' ]
-1
Matt
quelle
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

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

Einige Ideen aus @ edc65

nderscore
quelle
c [B [a] = b] anstelle von c [] ist B [a] = b clever, scheitert aber für n = 0
edc65
@ edc65 schöner Fang. Ich habe es jetzt angepasst, um den Fall zu behandelnn=0
nderscore
Genial. Das ist etwas, an das man sich erinnern sollte, um eine Rückkehr zu vermeiden - danke fürs Teilen (+1)
edc65
@ edc65 danke! Ich fand es interessant. MT0 hat uns beide geschlagen! : 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)

Es mussten einige Anpassungen vorgenommen werden, damit dies in Haskell funktioniert: Es wird bein Paar zurückgegeben: die Tickets (falls möglich) und der neue Status des Theaters. tist der ursprüngliche Theaterzustand, bei dem alle Tickets nicht verkauft sind. Außerdem war die Rückgabe -1für Haskell unnatürlich. Wenn für eine Anforderung keine Tickets ausgestellt werden können, wird die leere Liste für die Tickets zurückgegeben.

λ: 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
quelle
3

APL (75)

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

Prüfung:

      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  

Erläuterung:

  • T←10 15⍴0: Tist eine 15-mal-10-Matrix, die den Theaterzustand enthält (0 = frei)
  • B←{... }: die Funktion
    • (⍵∊⍳15): wenn ist ein Mitglied der Menge von ganzen Zahlen von 1 bis 15,
    • ∨/Z←,T⍷⍨⍵/0: und Tenthält Nullen in einer Reihe (Speicherung möglicher Startpunkte in Z),
    • :: dann:
      • (⊃Z/,⍳⍴T): mögliche Startkoordinaten auswählen und die erste nehmen,
      • ∘+¨1-⍨⍳1⍵: ⍵-1Weitere Positionen rechts von der Startkoordinate hinzufügen
      • P←: Speichern Sie die Koordinaten in P
      • {⎕A[⍺],⍕⍵}/¨: Formatieren Sie die Koordinaten
      • T[P]←: Speichern Sie die formatierten Koordinaten an ihren Stellen in T. (Alle Werte ungleich Null in T reichen aus)
      • +: gebe das Ergebnis zurück, welches die formatierten Koordinaten sind (das Ergebnis einer Zuweisung ist standardmäßig stillschweigend)
    • ⋄¯1: Andernfalls kehren Sie zurück ¯1.
Marinus
quelle
3

Javascript (E6) 99 103 113 121

Wirklich, Sie müssen nur eine Nummer für jede Zeile speichern

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}

Prüfung

'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;
}
edc65
quelle
3

JavaScript (ECMAScript 6 Draft) - 96 95 91 Zeichen

Eine rekursive Lösung:

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)

(Danke an nderscore für die Inspiration zum Speichern von 1 Charakter)

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)

(Danke an nderscore )

Erläuterung:

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
quelle
Gute Lösung. Ich habe an etwas Ähnlichem gearbeitet. Hier ist -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
Danke, leider funktioniert das nicht ganz, da Sie Zeile J nicht buchen können, aber das Negieren des ersten Schecks 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)sollte funktionieren.
MT0
Ah, guter Fang.
nderscore
Und es geht immer tiefer ... (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)
runter Zwischenstand
2

GolfScript, 103 82 Bytes

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

Beispiele

$ 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

Wie es funktioniert

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
quelle
1

CoffeeScript - 171 150 149

Ich vermute, Ruby oder Perl werden das bald ausschalten.

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

Entsprechendes JavaScript / Erklärung :

Für diejenigen, die mit CoffeeScript nicht vertraut sind.

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

Probieren Sie es online aus .

Tony Ellis
quelle
1
Diese Lösung entspricht nicht der RegelAll seats in one booking must be in the same row, next to each other.
Zwischenstand
0

Cobra - 309

Dies sollte es tun, aber ich kann nicht tatsächlich für ein paar Stunden zu einem Compiler gelangen, so dass ich es später aktualisieren werde, wenn nötig.

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
quelle
0

C # - 289

Erster Versuch, Code Golf zu spielen.

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

Nicht golfen

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;
}
goldener Drache
quelle
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]]}

Hier sind zweifellos zahlreiche Verbesserungen vorzunehmen

tmartin
quelle
0

C ++ - 257

Auch ein erster Golfversuch.

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

Da to_string mit meinem Compiler nicht funktioniert hat, ist toS definiert als

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

Und als kleines 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;
}
celie56
quelle
1
Wenn Sie nur unnötige Leerzeichen entfernen, werden 243 Zeichen angezeigt.
Tomsmeding
Weiteres Golfen bis 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

268 Bytes

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

Ich hätte einige Anmerkungen in einen Kommentar zur Lösung von GoldenDragon geschrieben, anstatt meinen eigenen zu machen, aber mein Ruf lässt dies nicht zu.

Tsavinho
quelle