tło

Etykieta łazienki, jeśli chodzi o dostępne pisuary, stwierdza, że ​​następny pisuar, który należy wypełnić, powinien być taki, który minimalizuje całkowity dyskomfort. Równanie całkowitego dyskomfortu daje następujący zestaw równań:

dist (x, y) = liniowa odległość między osobą x a osobą y w dyskomfortu w pisuarach
 (x) = suma (1 / (dist (x, y) * dist (x, y))) dla wszystkich osób y bez osoby x
 total_Discomfort = suma (dyskomfort (x)) dla wszystkich x

Bardziej szczegółowy artykuł na temat podobnego (nie dokładnie takiego samego) problemu można znaleźć tutaj: (Dzięki @Lembik za powiadomienie mnie o tym niesamowitym papierze!)

Wejście wyjście

Biorąc pod uwagę wkład pustych i pełnych pisuarów, wypisz wynikowy zestaw pisuarów z dodatkiem jednej osoby. W przypadku remisu na pozycji pisuary powinny być wypełniane od lewej do prawej. Dane wyjściowe powinny mieć taki sam format jak dane wejściowe.

• Jeśli podano skrzynkę z pełnymi pisuarami, zwróć dane wejściowe.
• Na wejściu zawsze będzie zdefiniowany przynajmniej jeden pisuar.

Przypadki testowe

WEJŚCIE -> WYJŚCIE
1000001 -> 1001001
101010101 -> 111010101
100 -> 101
00000 -> 10000
1111111 -> 1111111
0100 -> 0101
101000 -> 101001

Zasady

To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach. Standardowe otwory na pętle są zabronione.

Galaretka , 13 12 bajtów

J_þTݲSiṂ$Ṭo

Wypróbuj online! lub Zweryfikuj wszystkie przypadki testowe.

Wyjaśnienie

J_þTݲSiṂ$Ṭo  Input: boolean array A
J             Indices, returns [1, 2, ..., len(A)]
   T          Truthy indices, returns the indices which have a truthy value
 _þ           Form the subtraction (_) table (þ) between them
    İ         Inverse, find the reciprocal of each
     ²        Square each
      S       Sum the sublists column-wise
         $    Monadic chain
        Ṃ       Minimum
       i        Find the first index of that
          Ṭ   Untruth indices, returns a boolean array with 1's at those indices
           o  Logical OR between that and A, and return

MATL , 19 18 17 bajtów

lyf!Gn:-H_^Xs&X<(

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe (nieznacznie zmodyfikowany kod).

Wyjaśnienie

Wystarczy obliczyć odległość od każdej potencjalnej nowej pozycji do już zajętych. Pozostałe odległości nie zależą od potencjalnej nowej pozycji, a zatem stanowią stały element, który można zignorować.

Weźmy [1 0 0 0 0 0 1]za przykład przykład.

l      % Push 1
       % STACK: 1
y      % Take input implicitly. Duplicate from below
       % STACK: [1 0 0 0 0 0 1], 1, [1 0 0 0 0 0 1]
f!     % Indices of nonzero elements, as a column array
       % STACK: [1 0 0 0 0 0 1], 1, [1 7]
Gn:    % Push [1 2 ... n], where n is input size (array of possible positions)
       % STACK: [1 0 0 0 0 0 1], 1, [1; 7], [1 2 3 4 5 6 7]
-      % Matrix with all pairs of differences 
       % STACK: [1 0 0 0 0 0 1], 1, [1; 7], [0 -1 -2 -3 -4 -5 -6;
                                             6  5  4  3  2  1  0]
H_^    % Raise each entry to -2
       % STACK: [1 0 0 0 0 0 1], 1, [   Inf 1.0000 0.2500 0.1111 0.0625 0.0400 0.0278;
                                     0.0278 0.0400 0.0625 0.1111 0.2500 1.0000    Inf]
Xs     % Sum of each column
       % STACK: [1 0 0 0 0 0 1], 1, [Inf 1.04 0.3125 0.2222 0.3125 1.04 Inf]
&X<    % Index of minimum. Takes the first if there is a tie
       % STACK: [1 0 0 0 0 0 1], 1, 4
(      % Assign: write 1 at the position of the minimizer
       % STACK: [1 0 0 1 0 0 1]
       % Implicitly display

JavaScript (ES6), 89 bajtów

a=>a[a.map((e,i)=>!e&&(t=0,a.map((e,j)=>t+=(j-=i)&&e/j/j),t<m&&(m=t,k=i)),k=0,m=1/0),k]=1

Wyjście poprzez modyfikację tablicy wejściowej.

R, 83 76 67 bajtów

Właśnie zdałem sobie sprawę, że mogę zaoszczędzić kilka bajtów, nie zawracając sobie głowy sprawdzaniem, czy pisuary kandydatów są puste. Niepuste pisuary zawsze zwracają Infwartość dyskomfortu, dlatego są one wykluczane w trakcie obliczeń. Ponadto, zamiast bezpośredniego indeksowania replace, jest krótszy, ale mniej elegancki.

x=scan()
x[which.min(rowSums(outer(seq(x),which(!!x),`-`)^-2))]=1
x

Wyjaśnienie

x=scan()

Odczytujemy bieżący stan ze standardowego wejścia i nazywamy go x. Zakładamy, że wkład jest sekwencją 1si 0y znak spacji lub znakami nowej linii. Dla celów wyjaśnienia załóżmy, że wprowadzamy 1 0 0 0 0 0 1.

x[which.min(rowSums(outer(seq(x),which(!!x),`-`)^-2))]=1

Zastępujemy wartość xokreślonego indeksu wartością 1. Wszystko pomiędzy [ ]zastanawia się, jaki jest najlepszy indeks.

Ponieważ istniejące pisuary są niezmienne, nie musimy brać pod uwagę odległości między nimi. Musimy tylko wziąć pod uwagę odległości między zajętymi pisuarami i możliwym nowym. Tak więc określamy wskaźniki zajmowanych pisuarów. Używamy whichfunkcji do zwracania indeksów wektora logicznego TRUE. Wszystkie liczby w R po wymuszeniu wpisania logicalsą TRUEniezerowe i FALSEzerowe. Po prostu zrobienie which(x)spowoduje błąd typu argument to 'which' is not logical, podobnie jak xwektor numeryczny. Musimy zatem zmusić to do logiki. !to funkcja logicznej negacji R, która automatycznie zmienia się w logiczną. Zastosowanie go dwukrotnie !!xdaje wektor TRUEiFALSEwskazując, które pisuary są zajęte. (Alternatywne bajt równoważne coercions logicznemu obejmować operatorów logicznych &i |i przy pomocy poleceń wbudowanych Ti Fnp F|xalbo T&xi tak dalej. !!xWygląda bardziej wykrzyknikowy więc użyjemy tego.)

                                 which(!!x)

Jest to sparowane z seq(x), co zwraca sekwencję całkowitą od 1długości x, tj. Wszystkich lokalizacji pisuaru (a więc wszystkich możliwych lokalizacji do rozważenia).

                          seq(x)

Teraz mamy wskaźniki naszych zajętych pisuarów 1 7i naszych pustych pisuarów 1 2 3 4 5 6 7. Przekazujemy `-`funkcję odejmowania do outerfunkcji, aby uzyskać „odejmowanie zewnętrzne”, która jest następującą macierzą odległości między wszystkimi pisuarami a zajętymi pisuarami:

[, 1] [, 2]

[1] 0–6

[2,] 1–5

[3] 2–4

[4] 3–3

[5] 4–2

[6] 5–1

[7,] 6 0

                    outer(seq(x),which(!!x),`-`)

Podnosimy to do -2potęgi. (Dla tych, którzy są trochę zagubieni, w OP „dyskomfort” definiuje się jako 1 / (distance(x, y) * distance(x, y)), co upraszcza 1/d(x,y)^2, tj d(x,y)^-2.)

                    outer(seq(x),which(!!x),`-`)^-2

Weź sumę każdego wiersza w macierzy.

            rowSums(outer(seq(x),which(!!x),`-`)^-2)

Uzyskaj indeks najmniejszej wartości, czyli optymalnego pisuaru. W przypadku wielu najmniejszych wartości zwracana jest pierwsza (tj. Najbardziej lewa).

  which.min(rowSums(outer(seq(x),which(!!x),`-`)^-2))

I voilà, mamy indeks optymalnego pisuaru. Zamieniamy na wartość tego wskaźnika w xz 1. W przypadku danych 1111wejściowych nie ma znaczenia, który z nich zastąpimy, nadal będziemy mieć prawidłowe dane wyjściowe.

x[which.min(rowSums(outer(seq(x),which(!!x),`-`)^-2))]=1

Zwraca zmodyfikowane dane wejściowe.

x

PHP, 135 bajtów

$a=explode(1,$argv[1]);$b=0;foreach($a as$c=>$d){$l=strlen($d);if($l>$b){$b=$l;$e=$c;}}if($b)$a[$e][intval($b/2)]=1;echo implode(1,$a);

Jestem pewien, że jest na to znacznie szybszy sposób, ale mam niewyraźną głowę i nie mogę o tym myśleć!

Stary kod

Kod bez minimalizacji:

$a=explode(1,$argv[1]);
$b=0;
foreach($a as $c=>$d){
    $l=strlen($d);
    if($l>$b){
        $b=$l;
        $e=$c;
    }
}
if($b){
    $a[$e][intval($b/2)]=1;
}
echo implode(1,$a);

Python 3 223 222 165 bajtów

Okej, wiem, że to nie jest najładniejsza odpowiedź i jestem pewien, że można trochę pograć w golfa, ale po prostu bawiłem się i widziałem, co mogę zrobić

Krzycz na mbomb007, aby uzyskać wskazówki na temat białych znaków i komparatorów. Widziałem też, że mój licznik postaci online bierze wszystkie karty i zamienia je w spacje, więc liczba jest znacznie mniejsza niż początkowo

def u(a):
 m,r,x=9,0,len(a)
 for i in range(x): 
    d=0
    if a[i]<'1':
     for j in range(x):
        if a[j]>'0':d+=float((j-i)**-2)
     if d<m:r=i;m=d
 return a[:r]+'1'+a[r+1:]

Pokazuje zmienione białe znaki:

def u(a):
<sp> m,r,x=9,0,len(a)
<sp> for i in range(x): 
<tab> d=0
<tab> if a[i]<'1':
<tab><sp> for j in range(x):
<tab><tab> if a[j]>'0':d+=float((j-i)**-2)
<tab><sp> if d<m:r=i;m=d
<sp> return a[:r]+'1'+a[r+1:]

Oryginalny:

def u(a):
    m,r,x=9,0,len(a)
    for i in range(x): 
        d=0
        if a[i]!='1':
            for j in range(x):
                if a[j]=='1':d+=float(1/(j-i)**2)
            if d<m:r=i;m=d
    return a[:r]+'1'+a[r+1:]

Oczekuje, że ciąg przekazany do niego jako 1 i 0, "10001"i zwróci ciąg"10101"

Edycja: zmieniono 1/float((j-i)**2)nafloat((j-i)**-2)

Python 3, 574 471 347 bajtów

Prawdopodobnie popracuję nad tym trochę dłużej, biorąc pod uwagę, że inne rozwiązanie Python jest jak jedna piąta tego: [.

def a(I):
 D,l,r={},len(I),range
 for i in r(l):
  if I[i]<1:
   n,t,n[i]=I[:],[],1
   for j in r(l):
    if n[j]>0:
     q,Q=[],0
     for k in r(l):
      if k!=j and n[k]>0:q.append((k-j,j-k)[k<j])
     for i in q:Q+=1/(i**2)
    t.append(Q)
   T=sum(t)
   if T not in D.keys():D[T]=i
 if len(D)>0:I[D[min(D.keys())]]=1
 print(I)

Cóż, teraz jest o wiele lepiej, gdy nauczyłem się, że możesz używać pojedynczych spacji.

Python, 165 163 158 147 141 140 140 139 bajtów

def u(p):e=enumerate;a=[(sum((i-j)**-2for j,y in e(p)if"0"<y),i)for i,x in e(p)if"1">x];return a and p[:min(a)[1]]+"1"+p[min(a)[1]+1:] or p