Театра Гостиный

12

задача

Театр имеет 10 строк, помеченных , Aчтобы Jот передней части к задней, а также 15 мест в каждом ряду, пронумерованных от 1 до 15 слева направо.

Программа использует следующие правила, чтобы выбрать лучшие места.

  • Правило 1: Все места в одном бронировании должны быть в одном ряду, рядом друг с другом.
  • Правило 2: сиденья должны быть как можно ближе к передней части, а затем как можно ближе к левому краю (нижняя буква, затем наименьшее число)

Напишите функцию, которая принимает число желаемых билетов в качестве целочисленного input ( n) и выводит лучшие места, доступные в списке длины n.

Ваша программа должна:

  • Выведите, -1если 1> Вход или Вход> 15 *
  • Вывод, -1если места не доступны *
  • Есть функция, B(n)которую пользователь может использовать для ввода желаемого количества мест.

* Вы можете вывести -1 в списке, если это облегчает

Примеры

I / O

Вызов B(5)нового массива должен возвращать [A1, A2, A3, A4, A5]
Calling, B(2)после чего должен возвращаться [A6, A7]
Calling, B(10)после чего должен затем возвращаться [B1, B2, ... B9, B10]
Calling B(-1)должен всегда возвращаться-1

Un-golf 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
Гарри Бидл
источник
1
Нужно ли "жестко закодировать список мест в двумерном массиве"? Есть множество способов сделать это без этого; требование действительно ограничивает решения.
Джастин
2
Вы говорите, что двумерный массив должен быть жестко запрограммирован, но ваш пример Python даже не жестко его кодирует, он использует понимание для создания нового списка во время выполнения.
Тони Эллис
6
Зачем даже упоминать «список мест в двумерном массиве»? Это звучит как деталь реализации, и если кто-то создает программу, которая удовлетворяет требуемому выводу без использования массива, с этим не должно быть никаких проблем.
Грег Хьюгилл
2
Что делать, если на входе 0?
edc65
1
@ edc65 Я всегда заставляю своих несуществующих посетителей кинотеатра сидеть в лучшем месте театра, на коленях другого покровителя, если это будет необходимо. Они никогда не замечают.
Адам Дэвис

Ответы:

4

JavaScript - 172

Сама функция 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;}

Входные данные:

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

Выход:

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

Демо здесь: http://jsfiddle.net/tBu5G/

Некоторые идеи взяты из @ edc65

nderscore
источник
c [B [a] = b] вместо c [], B [a] = b умный, но терпит неудачу при n = 0
edc65
@ edc65 хороший улов. Я теперь настроил это, чтобы справиться с деломn=0
nderscore
Потрясающие. Это то, что нужно помнить, чтобы избежать «возврата» - спасибо, что поделились (+1)
edc65
@ edc65 спасибо! Я думал, что это было интересно. MT0 заставил нас обоих победить! : P
nderscore
3

Хаскелл, 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)

Нужно было внести некоторые изменения, чтобы сделать это функцией в Haskell: bвозвращает пару: билеты (если это возможно) и новое состояние театра. tявляется исходным состоянием театра со всеми непроданными билетами. Кроме того, возвращение -1было неестественным для Haskell, поэтому, если никакие билеты не могут быть выданы для запроса, пустой список возвращается для билетов.

λ: 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
источник
3

APL (75)

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

Тестовое задание:

      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  

Объяснение:

  • T←10 15⍴0: Tматрица 15 на 10, которая содержит состояние театра (0 = свободный)
  • B←{... }: функция
    • (⍵∊⍳15): является членом набора целых чисел от 1 до 15,
    • ∨/Z←,T⍷⍨⍵/0: и Tсодержит нули подряд (сохраняя возможные начальные точки в Z),
    • :: тогда:
      • (⊃Z/,⍳⍴T): выберите возможные начальные координаты и возьмите первые,
      • ∘+¨1-⍨⍳1⍵: добавить ⍵-1больше позиций справа от начальной координаты
      • P←: сохранить координаты в P
      • {⎕A[⍺],⍕⍵}/¨: отформатировать координаты
      • T[P]←: сохранить отформатированные координаты на своих местах в T. (любые ненулевые значения в T будут делать)
      • +: вернуть результат, который является отформатированными координатами (по умолчанию результат присвоения неявен)
    • ⋄¯1Иначе вернись ¯1.
Мэринус
источник
3

Javascript (E6) 99 103 113 121

На самом деле вам просто нужно сохранить номер для каждой строки

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}

Тестовое задание

'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
источник
3

JavaScript (ECMAScript 6 Draft) - 96 95 91 символов

Рекурсивное решение:

Версия 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

Версия 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)

(Спасибо Nderscore за вдохновение для сохранения 1 символа)

Версия 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)

(Спасибо nderscore )

Объяснение:

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
источник
Хорошее решение. Я работал над чем-то похожим. Вот -1 байт: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
Спасибо, к сожалению, что это не совсем работает, так как вы не можете забронировать строку J, но отмена первой проверки, чтобы дать, 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)должно работать.
MT0
Ах, хороший улов.
nderscore
И это продолжает понижаться ... (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 байта

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

Примеры

$ 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

Как это устроено

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.
}
Деннис
источник
1

CoffeeScript - 171 150 149

Я подозреваю, что Ruby или Perl скоро справятся с этим.

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 / Объяснение :

Для тех, кто не знаком с 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;
}

Попробуйте онлайн .

Тони Эллис
источник
1
Это решение не удовлетворяет правилуAll seats in one booking must be in the same row, next to each other.
nderscore
0

Кобра - 309

Это должно сработать, но я не могу получить компилятор в течение нескольких часов, поэтому я обновлю его позже, если потребуется.

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
источник
0

C # - 289

Первая попытка поиграть в гольф.

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;
}
Золотой дракон
источник
0

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

Есть, несомненно, многочисленные улучшения, которые должны быть сделаны здесь

tmartin
источник
0

С ++ - 257

Также первая попытка игры в гольф.

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

Поскольку to_string не работал с моим компилятором, toS определяется как

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

И как маленький интерфейс

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
источник
1
Простое удаление ненужных пробелов приводит к уменьшению его до 243 символов.
Томсминг
Больше игры в гольф до 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;}
Томсминг
0

C # - 268 байт

Гольф-код:

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:

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

Я бы написал несколько аннотаций в комментарии к решению GoldenDragon вместо того, чтобы делать свое, но моя репутация не позволяет этого.

tsavinho
источник