„Kreatywne” sposoby określania, czy tablica jest sortowana

51

Biorąc pod uwagę tablicę liczb całkowitych, napisz program, który określa, czy jest sortowany w porządku rosnącym.

Pamiętaj, że jest to pytanie trollujące kod.

Szukam najciekawszych sposobów, które wymyślają ludzie.

Odpowiedź z największą liczbą głosów pozytywnych wygrywa.

To pytanie jest inspirowane „kreatywnym” rozwiązaniem, które kandydat dał mi w wywiadzie :)

„Kreatywne” rozwiązanie wyglądało mniej więcej tak:

  • Ponieważ dla posortowanej tablicy

    • wszystkie elementy po lewej stronie dowolnego elementu muszą być mniejsze
    • wszystkie elementy po prawej stronie dowolnego elementu muszą być większe

Dlatego uruchom główną pętlę dla wszystkich elementów i sprawdź powyższe dwa warunki, uruchamiając dwie zagnieżdżone pętle wewnątrz głównej (jedna dla lewej strony i jedna dla prawej strony)

Byłem zszokowany!!.

popularity-contest  code-trolling 
— drobnoustrój
źródło
58
To nie jest duplikat. Niektórzy moderatorzy uważają, że konieczne jest zaznaczenie każdego pytania duplikatem innym bez czytania. To wcale nie jest pytanie sortujące. Przeczytaj to.
— drobnoustrój
3
Na koniec konkursu chciałbym również poznać „kreatywne” rozwiązanie! :)
— Vereos
16
@micro Diamentowi moderatorzy są wybierani przez społeczność. Mylicie moderatorów z systemem uprawnień.
— Klamka
3
@microbian Więc zatrudniłeś tego faceta?
— VisioN
3
Gdyby tylko interfejs API StackExchange zezwalał na dostęp do zapisu, zadałbym pytanie „Czy ta tablica jest posortowana?” i liczę głosy pozytywne na pozytywne / negatywne odpowiedzi ..
— Michael Foukarakis

Odpowiedzi:

77

Rubin

Wszyscy wiedzą: sortowanie przebiega bardzo wolno i zajmuje wiele cykli (najlepsze, co możesz zrobić, to coś z tym zrobić n log(n)). Dlatego dość łatwo jest sprawdzić, czy tablica jest posortowana. Wszystko, co musisz zrobić, to porównać środowisko wykonawcze sortowania tablicy i sortowania posortowanej tablicy.

array = [1, 5, 4, 2, 3]

## measure the time needed to sort the array 1m times
tstart = Time.now
1000000.times {
  array.sort
}
trun = Time.now - tstart

## now do a reference measurement on a sorted array
array.sort!
tstart = Time.now
1000000.times {
  array.sort
}
treference = Time.now - tstart

## compare run times
if trun > treference
  print "array was not sorted"
else
  print "array was sorted"
end
— Howard
źródło
19
Zależy to jednak od algorytmu sortowania. Sortowanie według sortowania lub sortowanie według stosu nie pokazałoby żadnej różnicy, niezależnie od tego, czy tablica jest już posortowana, czy nie.
— Niklas B.,
4
@NiklasB. Ruby używa quicksort . To powiedziawszy, ta metoda może być trudna i dawać fałszywe wyniki dodatnie, gdy tablica wejściowa jest prawie posortowana, lub, co bardziej prawdopodobne, fałszywe negatywne, gdy tablica jest sortowana (byłoby to bardzo mało prawdopodobne treference <= trundla każdego posortowanego przypadku, tylko z powodu niedeterministycznych innych rzeczy) . Teoretycznie wydaje się, że dostaniesz około 50% fałszywych negatywów dla posortowanego przypadku?
— Jason C
6
Ciekawa myśl, ale nie deterministyczna. Jest mniej więcej tak dobry, jak można zrobić dziesięć pompek, a następnie jeszcze dziesięć pompek, a następnie zdecydować, czy pierwsza tablica została posortowana, czy nie, ponieważ jeden pocił się bardziej na drugim zestawie pompek. Czy zapomnieliśmy, że uruchamiamy kod na maszynach wielozadaniowych? Również na bardzo małych tablicach przedział czasu po prostu nie jest wystarczająco dokładny. +1 za szaloną próbę!
— LMSingh
1
@NiklasB. Timsort (wariant sortowania) działa w czasie liniowym na posortowanych (a także częściowo posortowanych) tablicach.
— Bakuriu
3
@JasonC - warto zauważyć, że czyni to powyższą implementację jeszcze bardziej wątpliwą: opiera się nie tylko na wiedzy, że wewnętrzny algorytm sortowania Ruby jest szybki (co samo w sobie jest nieudokumentowane, a zatem wątpliwe, na czym można polegać), ale na konkretnej implementacji jest zoptymalizowany dla przypadku już posortowanych danych (którym domyślnie nie jest Quicksort: Quicksort to tylko średni O (n log n) ... jego najgorszym przypadkiem jest O (n ^ 2) oraz w naiwnej implementacji, która najgorszym przypadkiem jest wywołanie już posortowanych danych).
— Jules
52

JavaScript

array = prompt("Give the array");
while (true) {
    sorted = prompt("Is it sorted?");
    if (/yes|Yes/.test(sorted)) {
        alert("The array is sorted.");
        break;
    } else if (/no|No/.test(sorted)) {
        alert("The array is not sorted.");
        break;
    } else {
        alert("Dear user:\n\nPlease refer to the manual (RTFM) to observe how to use the system accordingly to the defined business rules.\nNow, try again.");
    }
}
— Victor Stafusa
źródło
55
-1 za mało JQuery.
— Pierre Arlaud
3
Miałem podobny pomysł, który wymagałby tablicy, a następnie jeden po drugim monit „czy to jest większe niż to?” A jeśli wszystkie są prawdziwe, tablica jest sortowana
— Zach Thacker
41

Java - podzbiory rekurencyjne

Witamy w Stack Overflow! To doskonałe pierwsze pytanie, ponieważ zaskakuje nawet niektórych doświadczonych programistów. Pozwól, że dam ci trochę podstawowych informacji, zanim przekażę kod:

Określenie sortowania może być trudnym zadaniem na pierwszy rzut oka. Dla dowolnego zestawu długości n istnieje n! możliwe sposoby zamawiania. Są to tak zwane permutacje . Jeśli twoja tablica ma różne elementy, tylko jedna z tych możliwości jest posortowana! Aby znaleźć posortowane, musisz przesiać je wszystkie, aż znajdziesz właściwy (być może tylko jeden), odrzucając wszystkie pozostałe.

Co? Na pewno nie jest to takie trudne ...

Algorytmy z n! złożoność zajmuje dużo czasu przy większych nakładach, ale przy odrobinie pracy możemy to obejść i obniżyć cały stopień złożoności. To wciąż wykładniczy czas, ale jest znacznie lepszy niż czynnikowy.

Aby to zrobić, musimy wziąć pod uwagę następujący fakt matematyczny: Jeśli tablica jest sortowana, wówczas sortowany jest również każdy jej (względnie uporządkowany) podzbiór . Możesz poprosić ekspertów matematyki o formalny dowód, ale jest to intuicyjnie prawda. Na przykład dla zestawu 123odpowiednie są podzestawy 1 2 3 12 13 23. Widać, że wszystkie są uporządkowane. Teraz, gdyby oryginał był 213, miałbyś 2 1 3 21 23 13i od razu widać, że 21jest niesprawny.

Jest to ważne dlatego, że jest ich znacznie mniej niż n! podzbiory. W rzeczywistości tylko dwa N -2 podzbiory musimy oka. Możemy wykluczyć zestaw zawierający całą tablicę oryginalnych liczb, a także pusty zestaw.

Nadal 2 n -2 może być bardzo pracochłonne. Podobnie jak w przypadku większości rzeczy, które przekraczają czas wielomianowy, dobrze działa tutaj podejście dziel i zwyciężaj . Najprostsze podejście? Rekurencja !

Podstawowe kroki są proste. Dla każdego podzbioru danych wejściowych generowane są mniejsze podzbiory. Następnie dla każdego z nich robisz to samo. Gdy twoje podzbiory zostaną zmniejszone do rozmiaru 2, po prostu sprawdzisz, który z nich jest większy. Ponieważ za każdym razem zmniejszasz rozmiar podzbiorów, dzieje się to szybciej, niż się spodziewałeś.

Kluczowym faktem jest to, że możesz wyjść wcześniej , jak tylko znajdziesz jeden podzestaw zepsuty. Nie musisz przeszukiwać ich wszystkich. Jeśli ktoś jest zły, cała grupa jest zła. Jest to kwestia prędkości, której nie widać w wielu innych odpowiedziach.

Dość gadania, przygotujmy kod!

Zrobiłem to w Javie, ponieważ jest to popularny język i łatwy do odczytania. Elegancja rekurencji powinna być widoczna:

import java.util.ArrayList;

public class SortChecker {

    static final Integer[] input = {1, 2, 3, 4, 5};

    public static void main(String[] args) {
        if(isSorted(input))
            System.out.println("The array is sorted properly.");
        else
            System.out.println("The array was not sorted properly.");
    }

    public static boolean isSorted(Integer[] in){
        if(in.length == 1)
            return true;
        if(in.length == 2)
            return (in[0] <= in[1]);
        ArrayList<Integer[]> subsets = getSubsets(in);
        for(Integer[] next : subsets){
            if(!isSorted(next))
                return false;
        }
        return true;
    }

    public static ArrayList<Integer[]> getSubsets(Integer[] in){
        ArrayList<Integer[]> subsets = new ArrayList<Integer[]>();
        int bitmasks = (1 << in.length) - 1;
        for (int i = 1; i < bitmasks; i++){
            ArrayList<Integer> subset = new ArrayList<Integer>(); 
            for (int j = 0; j < in.length; j++)
                if ((i & (1 << j)) > 0) 
                    subset.add(in[j]);          
            subsets.add(subset.toArray(new Integer[1]));
        }
        return subsets;
    }
}

Dla przypomnienia, nudziłem się i zabiłem go po 15 minutach na uporządkowaną tablicę 12-elementową. Zrobi 11 elementów w około 45 sekund. Oczywiście, to naprawdę robi zjazd wcześniej dla non-sortowane, więc to, hm, dobre.

Aktualizacja: przy świeżym ponownym uruchomieniu wykonuje 12 elementów w 13 minut. 13 trwa prawie 3 godziny, a 14 trwa 20 godzin i wciąż rośnie.

— Geobity
źródło
8
+1 to prawdopodobnie najmniej wydajny algorytm, jaki kiedykolwiek widziałem. Powinno być w okolicy O (n! * 2 ^ (n!)) - Złożoność (prawdopodobnie gorsza).
— Ral Zarek
6
Jestem pewien, że widziałem gorzej, ale jest całkiem źle. Bez przekonania próbowałem określić złożoność, ale poddałem się i nazwałem to O(big).
— Geobity
1
Dostarczenie rozwiązania, które jest mniej wydajne niż nawet naiwna próba problemu podróżującego sprzedawcy jest imponujące!
— recursion.ninja
3
Ponieważ szansa na sortowanie tablicy 12 elementów wynosi tylko 1 na 479 milionów, to naprawdę nie ma znaczenia, że ​​potrzeba czasu, aby być absolutnie pewnym, że tak, na pewno? W rzeczywistości nigdy nie zobaczysz takiego w prawdziwym świecie ...
— Jules
2
@Geobits Nie ma problemu. Uruchom algorytm Victora i odpowiedz „tak” przy pierwszym pytaniu.
— Jason C
29

C ++ - metoda brutalnej siły

Wszyscy wiedzą, że metody brutalnej siły są zawsze najszybsze.

bool issorted(std::vector<int>& list)
{
  switch (list.size()) {
    case 0: case 1: return true;
    case 2: return list[0]<=list[1];
    case 3: return list[0]<=list[1] && list[1]<=list[2];
    case 4: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3];
    case 5: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4];
    case 6: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5];
    case 7: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6];
    case 8: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7];
    case 9: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8];
    case 10: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9];
    case 11: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10];
    case 12: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11];
    case 13: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12];
    case 14: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13];
    case 15: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14];
    case 16: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15];
    case 17: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16];
    case 18: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17];
    case 19: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18];
    case 20: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19];
    case 21: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20];
    case 22: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21];
    case 23: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22];
    case 24: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23];
    case 25: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24];
    case 26: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25];
    case 27: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26];
    case 28: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27];
    case 29: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28];
    case 30: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29];
    case 31: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30];
    case 32: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31];
    case 33: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32];
    case 34: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33];
    case 35: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34];
    case 36: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35];
    case 37: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36];
    case 38: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37];
    case 39: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38];
    case 40: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39];
    case 41: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40];
    case 42: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40] && list[40]<=list[41];
    case 43: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40] && list[40]<=list[41] && list[41]<=list[42];
    case 44: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40] && list[40]<=list[41] && list[41]<=list[42] && list[42]<=list[43];
    case 45: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40] && list[40]<=list[41] && list[41]<=list[42] && list[42]<=list[43] && list[43]<=list[44];
    case 46: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40] && list[40]<=list[41] && list[41]<=list[42] && list[42]<=list[43] && list[43]<=list[44] && list[44]<=list[45];
    case 47: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40] && list[40]<=list[41] && list[41]<=list[42] && list[42]<=list[43] && list[43]<=list[44] && list[44]<=list[45] && list[45]<=list[46];
    case 48: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40] && list[40]<=list[41] && list[41]<=list[42] && list[42]<=list[43] && list[43]<=list[44] && list[44]<=list[45] && list[45]<=list[46] && list[46]<=list[47];
    case 49: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40] && list[40]<=list[41] && list[41]<=list[42] && list[42]<=list[43] && list[43]<=list[44] && list[44]<=list[45] && list[45]<=list[46] && list[46]<=list[47] && list[47]<=list[48];
    case 50: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40] && list[40]<=list[41] && list[41]<=list[42] && list[42]<=list[43] && list[43]<=list[44] && list[44]<=list[45] && list[45]<=list[46] && list[46]<=list[47] && list[47]<=list[48] && list[48]<=list[49];
    case 51: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40] && list[40]<=list[41] && list[41]<=list[42] && list[42]<=list[43] && list[43]<=list[44] && list[44]<=list[45] && list[45]<=list[46] && list[46]<=list[47] && list[47]<=list[48] && list[48]<=list[49] && list[49]<=list[50];
    case 52: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40] && list[40]<=list[41] && list[41]<=list[42] && list[42]<=list[43] && list[43]<=list[44] && list[44]<=list[45] && list[45]<=list[46] && list[46]<=list[47] && list[47]<=list[48] && list[48]<=list[49] && list[49]<=list[50] && list[50]<=list[51];
  }
}

Rzeczywista rutyna jest dłuższa (dotyczy std :: npos), ale jestem ograniczony do 30000 znaków tutaj.

— Pan Lister
źródło
Naprawdę to lubię.
— Jakob
3
To jest jak podejście „wykorzystuj każdą część bawołu” do instrukcji case.
— Jonathan Van Matre
To jest niesamowite. Rozwiń wszystkie pętle!
— McKay,
wspaniała myśl!!!
— bikram990
26

Poinformować

Inform to język do pisania interaktywnych gier fabularnych dla klasycznego tłumacza maszynowego Infocom Z. Aby uniknąć spoilerów, najpierw podaję wyniki mojego programu, a potem kod źródłowy.

Edycja: Dokonałem niewielkiej zmiany, aby umożliwić dodawanie liczb do tablicy, i zamieściłem uroczy opis pokoju.

Sorted
An Interactive Fiction by Jonathan Van Matre
Release 1 / Serial number 140301 / Inform 7 build 6G60 (I6/v6.32 lib 6/12N) SD

Sorting Room
You are in the Sorting Room, a sterile expanse of pure white. Translucent
lucite walls leak a lambent clinical light into the spotless room.

You can see a safe (closed), a flask of poison, a radioactive isotope 
attached to a radiation detector that triggers a hammer, an array (empty) 
and Erwin Schrodinger here.

>open safe
You open the safe.

>put flask in safe
(first taking the flask of poison)

You put the flask of poison into the safe.

>put isotope in safe
(first taking the radioactive isotope attached to a radiation detector 
 that triggers a hammer)

You put the isotope detector assembly into the safe, carefully placing 
the hammer next to the fragile glass of the flask of poison.

>get array
Taken.

>put numeral 1 in array
(first taking the numeral 1)

You put the numeral 1 into the array.

>put 2 in array
(first taking the numeral 2)

You put the numeral 2 into the array.

>put 3 in array
(first taking the numeral 3)

You put the numeral 3 into the array.

>examine array
In the array are a numeral 3, a numeral 2 and a numeral 1.

>put array in safe
You put the array into the safe.

>ask Erwin about whether the array is sorted
Erwin grumbles and complains, "You haven't finished the experiment" 

>close safe
You close the safe.

>ask Erwin about whether the array is sorted
Erwin beams and proudly announces, "Indeterminate!"

A oto kod źródłowy:

"Sorted" by Jonathan Van Matre

The Sorting Room is a room. "You are in the Sorting Room, a sterile expanse of pure white. Translucent lucite walls leak a lambent clinical light into the spotless room."
The safe is a container. The safe is in the Sorting Room. The safe is openable. The safe is closed.
There is a flask of poison in the Sorting Room.
There is a radioactive isotope attached to a radiation detector that triggers a hammer in the Sorting Room.
There is an array in the Sorting Room. The array is a container.
There is a numeral 1 in the Sorting Room. The numeral 1 is undescribed.
There is a numeral 2 in the Sorting Room. The numeral 2 is undescribed.
There is a numeral 3 in the Sorting Room. The numeral 3 is undescribed.
There is a numeral 4 in the Sorting Room. The numeral 4 is undescribed.
There is a numeral 5 in the Sorting Room. The numeral 5 is undescribed.
There is a numeral 6 in the Sorting Room. The numeral 6 is undescribed.
There is a numeral 7 in the Sorting Room. The numeral 7 is undescribed.
There is a numeral 8 in the Sorting Room. The numeral 8 is undescribed.
There is a numeral 9 in the Sorting Room. The numeral 9 is undescribed.
In the Sorting Room is a man called Erwin Schrodinger.
Understand the command "ask" as something new.
Understand "ask [someone] about [text]" as asking it about.
After inserting the isotope into the safe:
    If the safe encloses the flask, say "You put the isotope detector assembly into the safe, carefully placing the hammer next to the fragile glass of the flask of poison.";
Instead of asking Erwin about something:
    If the safe is closed and the safe encloses the flask and the safe encloses the array and the safe encloses the isotope, say "Erwin beams and proudly announces, 'Indeterminate!' ";
    Otherwise say "Erwin grumbles and complains, 'You haven't finished the experiment' ";
— Jonathan Van Matre
źródło
21

Doge Ruby

Najpierw musisz uruchomić ten kod instalacyjny

class Array;alias ruby sort;end
def self.method_missing x,*a;x;end
def very x;$a=x;end
def many x;$b=$a.send x;end
def wow;puts $a==$b;end

Następnie po prostu zapisz tablicę w zmiennej o nazwie codingi uruchom:

  very coding

                 many ruby
so algorithm


      wow

Twoja odpowiedź zostanie wydrukowana (prawda lub fałsz).

Dodaj również kod doge, aby uzyskać optymalną wydajność:

#~! SET DOGE=1 PERFORMANCE=OPTIMAL ONERROR=nil PIC=
#                    ***=*                                                       
#                    **===*                                                      
#                    ***=-=&                                   &&**&             
#                    **==--=                                  ***===*            
#                   &***=---*                               $*=------*&          
#                   &***=---=*                             $**=----;;=&          
#                   &**==----=&                           &*===---;;;-*          
#                   &**==----=*                          &**=-==--;;;;=          
#                   ****=-----=*                       &&*==--=---;;;;-          
#                   **===------=&                     $&*==-------;;;;-          
#                   **===-------=*&$$                &*==------;;;;;;;-          
#                   **==----==-====***&&&&&&&&$$    &*==-;;---;;;;;;;;-&         
#                  &*=---=====================*******=---;---;;;;;;;-;;=         
#                  *=======*=========================---;;--;;;;;;;;;;;*         
#                  *===***=======================------;;--;;""""";;;;;=         
#                  *=*****========================;--;;;;--;;""""";;;;;*         
#                &*********====-----===============;;;;;----;"","";-;;-&         
#               ***********====----================-;;;;----;",,";;----          
#             &************===---====================-;;;;;;",,"";----=          
#            &*************===---=====================-;;;;",,,";-----*          
#            ******=*******===--=======================--;",,,"";-----&          
#           &**************==--=========================-;"","";----;-           
#          ****************==---====****=====-===========--;";;-;;;";=           
#         ****************==----==*******===--=============--;----;--=           
#        &*****=;"";==***===----==*******===----=============------;-=$          
#        &&&***;"",,"-**====---==********=====-===============----;;;-&          
#       &&&&&*=-;;";";*==========****=***======--=========***==---;;;-&          
#      $&&&&&&=="",,,-===**=======***==-;-=================**===--;;;;*          
#      &&&&&&&-="",,"==***==***======-",,,";=-===================--";;=          
#      &&&&&**=-""";==****=***===---;"-=-,,,"--===================-;;;=&         
#     &&&&&&***--;=***********=---;,,-*",,,,,"--==================--;--*         
#     &&&&&***=*=*************=-;;","=-,,,,,,"-====================----=$        
#    &&&&&&*******************==--","-;,,,,,"-====*****=============-===&        
#   $&&&&&&******************===---",";"""";=******************=====-===*        
#   &&&&&&&&&*****************======--;;--==********************=========&       
#  &&&&&&&&&&&******=**********===========*==*****&&************=========*       
#  &&&&&&&&*=---;--==**********==============*********************=======*&      
#  &&&&&&&-""""";;"";=**********==**=========*****&&&**************=======*      
# &&&&&&&*,,,,,,,,,,,"-****&************=*******&&&&&&&************========&     
# &&**&&&=,,,,,,,,,,,,;*&&&&***********************&&&&&&***********=======*     
# &&&*&&&*",,,,,,,,,,,;*&&&*************&&**********&**************========*&    
#&&&&&&&&-"",,,,,,,,,,-*&&&**********&**&&&&&&&******************==========**    
#&&&&&&&*=,,,,,,,,,,,"-***************&&&&&&&&&*****************====--======*&   
#&&***&&*=;,,,,,,,,,";=*==*****************&&&***************=======--=======&   
#*&&&&**=-;",,,,,,"";-=*********=**&*********&&**************=======--======**   
#&&&&&**=-""",,,,,"";==**==***===**********************======***===---=======*&  
#&&&&&**=-;"""""","";;=-===*======*********************==******====----======*&  
#*&&&&**=-;""""""""";=-============*****************==*********====---==--===**  
#&&&&&***=",,,,,,"""";--=============*******==****************====----=--====**& 
#&&&&&****"",,,,,,,,,;-=========--===****====******************====--==-======*& 
#&&&&&&&&*-"",,,,,,,,,"--==--;"""";====**===********************======--======** 
#&&&&&&***=-;",,,,,,,,,,,;",,,""";-=======********************===-------=======* 
#&&&&&&&****=;""""""""",,,"""";;--==**====*******************=====--------=====* 
# &&&&&&&***=-;;;;;;;;;"";;;;;---==***====*****************=====--=--------====*$
# &&&&&&*****=-;-----=--------=====*=======****************====-==---------=====&
#  &&&&&******==-==-=============***========*************======----=--------====&
#  &&&&************==========================***********=====----------------===*
#  $&&&&***************====================***********=*======-------------=--==*
#   &&*&************=====================**************======--------------=====*
#   &******************=================**************=========-----------======*
#    &***********=*****================************==========------;-------=====*
#    &*****************================***********=============---------========*
#     &*************===================**********==***========--------========***
#      **************==================********====**===*=====--------=======****
#      &************=============================*****=*=====--------=======*****
#       &****=*******=============================**============--=======*=******
#       $*****=====**===========================***===================**********&
#        &*****=====================-====-====*=*=====*=======--==***************
#         &*****===========---==--===============**=**=*========*****************
#          &*****====---=---------========********======***===*******************
#           *****=======-=-------======*******=**==****==*==*********************
#           $***======================******===**********************************
#            &***===================*******==***=******************************=&
#             &***=========-=========*************==***************************=&
#              ******===*=======*=*****************==*************************==&
#~! END

To jest najłatwiejszy sposób.

(grafika ASCII została wygenerowana przez skrypt, który napisałem, pochodzący z tego obrazu .)

— Klamka
źródło
7
Zapomniałeś „so algorytmu”. Prawdziwa próbka doży ma 3 zdania przed „wow”. I tak, bardzo dobrze się bawię na imprezach.
— Pierre Arlaud
@ArlaudPierre Heh, w porządku, naprawiono: P
— Klamka
11
Tak więc komentarz, bardzo poprawa, wiele przydatnych. Łał.
— Pierre Arlaud
Powinieneś napisać program BF w ascii w kształcie doży ... nowy pomysł na pytanie !!
— TheDoctor
19

PHP

Spodoba ci się łatwość i prostota następującego rozwiązania. Ogólna koncepcja i najnowocześniejsze funkcje zastosowane w tym arcydziele kodowania od razu doprowadzą Cię do elitarnej listy najlepszych programistów na świecie.

function is_sorted($input) {
    mysql_connect('localhost', 'name', 'password');
    mysql_select_db('database');

    mysql_query('
        CREATE TEMPORARY TABLE sorting_table (
          `value` int NOT NULL
        )');

    foreach ($input as $value) {
        mysql_query('INSERT INTO sorting_table VALUES (' . $value . ')');
    }

    $i = 0;
    $result = 'SORTED';
    $query = mysql_query('SELECT * FROM sorting_table ORDER BY value ASC');
    while ($value = reset(mysql_fetch_row($query))) {
        if ($input[$i++] != $value) {
            $result = 'NOT SORTED';
            break;
        }
    }

    mysql_query('DROP TABLE sorting_table');

    return $result;
}

print is_sorted(array(10, 20, 30, 40, 50));
— Wizja
źródło
+1 Ponieważ używasz tej samej koncepcji mojej odpowiedzi na pytanie sortujące
— Victor Stafusa
4
Czy to zadziałałoby, gdyby pani Roberts wprowadziła wartości?
— user80551
3
@ user80551 tak, ponieważ nie ma tabeli o nazwie studenci
— maniak ratchet
3
@JonathanVanMatre Z pewnością bezpieczeństwo jest jedną z najsilniejszych stron tego kodu.
— VisioN
1
To jest moja nowa ulubiona odpowiedź na tej stronie; ale dla dodatkowych znaków chciałbym zobaczyć, jak używasz PDO dla bezpieczeństwa
— alexandercannon
17

C # - Moc statystyki

Aby rozwiązać ten problem, należy ponownie sformułować pytanie w taki sposób, aby rozwiązanie było oczywiste. Ponieważ jest to w zasadzie pytanie typu „prawda-fałsz”, pytasz w zasadzie „w jaki sposób mogę być w 100% pewien, że tablica jest posortowana?” Jeśli jedno słowo wyskakuje z tego pytania, jest to słowo „pewne”. Jaki jest najlepszy sposób pomiaru pewności? Masz to: statystyki.

Inne odpowiedzi tutaj sprawdzają tylko, czy tablica jest posortowana w jednym kierunku . To rozwiązanie sprawdza jednocześnie rosnącą i malejącą kolejność. Sztuczka polega na tym, aby wziąć tablicę tego samego rozmiaru, o której wiesz, że jest posortowana (łatwo ją zrobić samodzielnie), a następnie dowiedzieć się, jak dobrze kolejność każdej tablicy koreluje z drugą. Obliczenie współczynnika korelacji rang Kendall jest najłatwiejszym sposobem:

using System;

namespace Homework
{
    class Example
    {
        static void Main(string[] args)
        {
            int[] n1 = { 23, 50, 16, 57, 19, 60, 40, 7, 30, 54 };
            int[] n2 = { 7, 16, 19, 23, 30, 40, 50, 54, 57, 60 };
            int[] n3 = { 60, 57, 54, 50, 40, 30, 23, 19, 16, 7 };

            Console.WriteLine(isSorted(n1));
            Console.WriteLine(isSorted(n2));
            Console.WriteLine(isSorted(n3));
        }

        static string isSorted(int[] a)
        {
            double t = 0;
            int n = a.Length;

            //Build a 'known' sorted array.
            int[] k = new int[n];
            for (int i = 1; i < n; i++)
            {
                k[i] = i;
            }

            //Find the Kendall's tau coefficient.
            //First the numerator...
            for (int i = 1; i < n; i++)
            {
                for (int j = 0; j < i; j++)
                {
                    t += Math.Sign(a[i] - a[j]) * Math.Sign(k[i] - k[j]);
                }
            }
            //...then the denominator.
            int d = n * (n-1) / 2;
            //This gives the correlation coefficient.
            double sortedness = t / d;
            //1 is perfect correlation (ascending), -1 is perfectly non-correlated (descending).
            if (Math.Abs(sortedness) == 1)
            {
                return "Sorted";
            }
            else
            {
                return "Unsorted";
            }
        }
    }
}

Wynik:

Unsorted
Sorted
Sorted

Ta funkcja jest również bardzo łatwa do rozszerzenia, ponieważ dodanie funkcji takich jak „Przeważnie posortowane” lub „Więcej posortowane niż nie” lub „Całkowicie losowe” byłoby banalne.

Edytować

Prawie zapomniałem omówić wydajność algorytmu. Jest to obecnie O (7). Jest jeden w nazwie metody, jeden w każdym ze słów kluczowych „for”, jeden w deklaracji „podwójnej” i dwa w zastosowaniu zmiennej „sortowanie”. Możesz to poprawić aż do O (0) (tak niskiego, jak to tylko możliwe), zmieniając nazwę funkcji, zmieniając podwójne na dziesiętne, usuwając „sortowanie” na „srtdnss” i przekształcając pętle for na podczas pętli.

— Komintern
źródło
2
Starannie przeliczyłem złożoność i ustaliłem, że jest to O (8). Odsuwasz ręcznie dane wyjściowe, które moim zdaniem powinny uwzględniać. Aby mieć naprawdę złożoność O (7), możesz rozważyć zwrot „rosnący” / „przypadkowy” zamiast „posortowanego” / „nieposortowanego”.
— Geobits
@Geobits - spojrzałem na to ponownie i oczywiście masz rację. Wydaje mi się, że pokazuje to minimalną złożoność O (1) podczas zwracania ciągów. Jest to jednak niewielka cena, ponieważ zwracanie wartości logicznej jest dwa razy gorsze.
— Komintern
1
+1 dla obliczenia O (). -1 za nie obliczanie rho Włócznika, ponieważ czy dwie korelacje nie są lepsze od jednej? I +1 za statystyki w C #, sprawdzonym faworycie statystyk.
— Jonathan Van Matre
Powiedz mi, że O(7)to żart
— mbatchkarov
@mbatchkarov - To mała notacja O. :-)
— Comintern
16

Rubin

Następująca strategia ostatecznie ujawni, jeśli tablica zostanie posortowana:

  1. ZAByć tablicą (albo sortowane lub sortowania, np [1,2,3] i [1,3,2])
  2. P jest tablicą zawierającą wszystkie permutacje A
  3. Jeśli A jest posortowane, jest to albo maksimum, albo minimum P (które w zasadzie są posortowanymi wersjami A w Ruby)

Wersja online do testowania.

class Array
   def is_sorted?
      permutations = permutation.to_a
      self == permutations.max || self == permutations.min
   end
end
— David Herrmann
źródło
1
Nie sądzę, że rozumiem wyjaśnienie. Jeśli tablica ma np. [1, 9, 100], wówczas min wynosi 10019, a maksimum to 91100, ale posortowana liczba to 19100. W przypadku wersji online maks. Wynosi [100,9,1] i min wynosi [19, 100]. Nie widzę, gdzie coś jest „reprezentowane przez liczbę”; wygląda na to, że tablice są właśnie uporządkowane leksykograficznie. Przypuszczam, że byłoby tak samo, gdyby wszystkie liczby były tylko jedną cyfrą.
— Joshua Taylor
„... maksimum lub minimum ...” bardzo się podobało.
— drobnoustrój
@JoshuaTaylor: Dzięki za heads-up! Chciałem to wyjaśnić w łatwo zrozumiały sposób - co ostatecznie było błędne;) Poprawiłem swój opis ...
— David Herrmann
2
@JoshuaTaylor metody ruby ​​Array # max i #min wybierz największy i najmniejszy element w odniesieniu do operatorów <i>. W tablicach <i> implementują sortowanie leksykograficzne. [1,9,100] to minima wszystkich uporządkowanych permutacji 1, 9 i 100 w porządku leksykograficznym.
— Karl Damgaard Asmussen
To prawie jakość produkcji.
— primo
12

C # - niedeterministyczne rozwiązanie

Ten kod prawdopodobnie działa.

static bool isSorted(int[] s)
{
    var rnd = new Random();
    for (var i = 0; i < s.Length * s.Length * s.Length; i++)
    {
        var i1 = rnd.Next(0, s.Length);
        var i2 = rnd.Next(0, s.Length);
        if (i1 < i2 && s[i1] > s[i2] || i1 > i2 && s[i1] < s[i2])
            return false; // definitely not sorted
    }
    return true; // probably sorted
}
— fejesjoco
źródło
8
Jeśli ustawisz liczbę iteracji na -n ^ 2 * ln (1-p), możesz zapewnić z prawdopodobieństwem p, że wszystkie kombinacje zostaną sprawdzone!
— Hannesh
A jakie wartości p są prawidłowe, aby to rozwiązanie zostało zaakceptowane jako „działający kod, ale trolling”? :)
— fejesjoco
2
Od stackoverflow.com/questions/2580933 , prawdopodobieństwo błędnego obliczenia porównania z powodu promieni kosmicznych wynosiłoby 0,0000018 (1,8e-6) co sekundę. Więc jeśli: 1) możesz dowiedzieć się, jak długo trwa iteracja, 2) Możemy użyć wzoru @ Hannesha do obliczenia prawdopodobieństwa, a następnie rozwiązać układ równań, aby znaleźć liczbę iteracji, które sprawiają, że twoje rozwiązanie jest nierozróżnialne od standardowa metoda isSorted.
— Xantix
11

Pyton

Jeśli lista jest posortowana, każda liczba jest mniejsza lub równa następnej liczbie. Dlatego usunięcie liczby najbardziej po lewej stronie zwiększy średnią wartość, w przeciwnym razie lista nie zostanie posortowana. Umieścimy to w pętli, aby sprawdzić każdy numer

def is_sorted(lst):
    def _avg(lst):
        return sum(lst)/(1.0*len(lst))
    for i in range(len(lst)-1):
        if _avg(lst[i:]) > _avg(lst[i+1:]):
            return False
    return True

is_sorted ([1,2,3]) #
True Prawda is_sorted ([3,2,1]) # False
is_sorted ([1,4,3,2,0,3,4,5]) #Fałsz

Spostrzegawczy czytelnik zauważy, że tak nie działa.
is_sorted ([1,4,3,2,0,3,4,11]) # False
is_sorted ([1,4,3,2,0,3,4,12]) # Prawda
is_sorted ([1,2 , 1,2,1,2,1,2,99]) # True

— VBCPP
źródło
9

Grzmotnąć 

mkdir -p nums
mynums=(1 2 3 4)
for i in "${mynums[@]}"
do
     touch "nums/$i"
done

result=`ls -v nums`
resultarray=(${result})
for i in "${!resultarray[@]}"
do
    if [ ${resultarray[$i]} != ${mynums[$i]} ]; then
        echo "not sorted!"
        rm -rf nums/*
        exit 1
    fi
done
echo "sorted!"
rm -rf nums/*

dotknij pliku dla każdego elementu w tablicy, ls katalog i porównaj wynik ls z oryginalną tablicą.

Nie jestem zbyt dobry w bash, chciałem tylko spróbować :)

— Zach Thacker
źródło
Fajnie, zakłada się, że katalog „./nums” już istnieje. Może gdzieś „mkdir -p nums”?
— camelthemammel
Och, tak, to ma sens: P
— Zach Thacker
8

DO#

Pojęcia „mniejszy” lub „większy” to tyle 2013 . Prawdziwi programiści używają tylko modulooperatora!

private static void Main()
{
    List<int> list = new List<int> { 1, 5, 7, 15, 22};
    List<int> list2 = new List<int> { 1, 5, 15, 7, 22 };

    bool a = IsSorted(list); // true
    bool b = IsSorted(list2); // false
}

private static bool IsSorted(List<int> list)
{
    for(int i = 0; i % list.Count != list.Count() - 1; i++)
    {
        if (list[i] % list[i + 1] != list[i] &&
            list[i] != list[i + 1])
        {
            return false;
        }
    }
    return true;
}
— Pierre-Luc Pineault
źródło
Co się stanie, jeśli ten sam numer pojawi się dwukrotnie? Następnie wypisz [i]% list [i + 1] == 0.
— Simon
@Simon Oh ho! Rzeczywiście, wydaje mi się, że posortowane są dwie identyczne liczby. Dodano porównanie dla tego przypadku krawędzi. Niezłe znalezisko.
— Pierre-Luc Pineault
5
Cieszę się, że {0, -1, 2} to posortowana lista.
— Pierre Arlaud
9
@ArlaudPierre Jeśli chcesz być prawdziwym programistą 2014, musisz odłożyć na bok wszystko, co jest negatywne. Świat jest pozytywny, świat jest absolutny, świat jest modulo!
— Pierre-Luc Pineault
1
Ponieważ nie podoba Ci się pojęcie „większy” i „mniejszy”, szkoda, że ​​musiałeś uwzględnić te znaki „mniej niż i więcej niż”. Powinieneś był użyć tablic zamiast list.
— Pan Lister
8

Scala

Sprawdzanie, czy tablica jest posortowana, jest łatwe! Wystarczy sprawdzić, czy pierwszy element jest mniejszy niż drugi. Następnie posortuj pozostałe i sprawdź, czy są równe.

Niestety sortowanie jest trudnym problemem. Nie ma wielu dobrze znanych lub wydajnych algorytmów do sortowania tablicy; w rzeczywistości jest to ogromny martwy punkt w obecnym stanie wiedzy informatycznej. Proponuję więc prosty algorytm: przetasuj tablicę, a następnie sprawdź, czy jest posortowana, co, jak już wspomniano, jest łatwe! Kontynuuj tasowanie, aż zostanie posortowane.

object Random {
  def isSorted(list: List[Int]): Boolean = {
    if (list.size <= 1) {
      true
    } else {
      sort(list.tail) == list.tail && list.head <= list.tail.head
    }
  }

  def sort(list: List[Int]): List[Int] = {
    val rand = new scala.util.Random()
    var attempt = list
    do {
      attempt = rand.shuffle(attempt)
    } while (!isSorted(attempt))
    attempt
  }

  def main(args: Array[String]): Unit = {
    println(isSorted(List(1, 2, 3)))
    println(isSorted(List(1, 3, 2)))
    println(isSorted(List(1, 2, 3, 4, 5, 6, 7, 8)))
  }
}

Zakładam, że te dane wyjściowe są „prawda, fałsz, prawda”. Od jakiegoś czasu działa ...

— Joe K
źródło
8

Posortowana tablica liczb całkowitych ma właściwość, że każda pod-tablica (powiedzmy elementy od n do m tablicy) jest również posortowaną tablicą liczb całkowitych. To oczywiście oznacza, że ​​najlepszą metodą jest funkcja REKURSOWA:

bool isSorted_inner(const std::vector<int> &array, int start, int length){
    if (length == 2){
        if (array[start] < array[start+1]){
            return true;
        }else{
            return false;
        }
    }else{
        return isSorted_inner(array, start, length-1) && isSorted_inner(array, start+1, length-1);
    }
}

bool isSorted(const std::vector<int> &array){
    return isSorted_inner(array, 0, array.size());
}

Może nie jest to najszybsza metoda, ale mimo wszystko BARDZO DOKŁADNY test, czy lista jest zamówiona, czy nie. Ten kod jest również niezwykle łatwy do odczytania i zrozumienia, ponieważ wykorzystuje paradygmat FUNKCJONALNY, a zatem jest wolny od horrorów związanych ze zmianą stanu i iteracyjnymi pętlami.

Mam nadzieję, że będą to dla ciebie przydatne informacje.

— Allen
źródło
6

C # - najdłuższy rosnący podciąg

W przypadku posortowanej tablicy długość najdłuższego wzrastającego podsekwencji jest równa długości tablicy. Skopiowałem stąd algorytm , zmodyfikowałem go tylko tak, aby nie zmniejszał się, zamiast zwiększać.

static bool isSorted(int[] s)
{
    return s.Length == LongestIncreasingSeq(s);
}

static public int LongestIncreasingSeq(int[] s)
{
    int[] l = new int[s.Length];  // DP table for max length[i]
    int[] p = new int[s.Length];  // DP table for predeccesor[i]
    int max = int.MinValue;

    l[0] = 1;

    for (int i = 0; i < s.Length; i++)
        p[i] = -1;

    for (int i = 1; i < s.Length; i++)
    {
        l[i] = 1;
        for (int j = 0; j < i; j++)
        {
            if (s[j] <= s[i] && l[j] + 1 > l[i])
            {
                l[i] = l[j] + 1;
                p[i] = j;
                if (l[i] > max)
                    max = l[i];
            }
        }
    }
    return max;
}
— fejesjoco
źródło
6

Stonescript (c) LMSingh - 0 minus (4102 palindromed).

Poniżej napisano w Stonescript (c), języku chronionym prawem autorskim i używanym przeze mnie wiele wieków temu, tj. W dawnych czasach przed ramkami. UWAGA: jest prekursorem sanskrytu.

1. Find a very straight stick in the jungle.  
2. Sum up all the values of the array elements and find that many equal sized stones.  
3. Line up all the values of the array along the side of straight stick from step 1. Each value is to be represented by number of stones for each array element like so...

Przykład tablicy z 8 elementami. Posortowane w kolejności malejącej :-) 

o
oo
oo
oooo
ooooo
ooooo
ooooo
oooooo
ooooooo
oooooooo
========
12345678

- Kod kontynuowany.

4. E-ball-uate. (In Shakespearean English that means Eye ball it.)  
  4.1 Run your eye from array position 1 top towards array position 8 top.  
  4.2 If it looks sorted, then it is.  
  4.2.1 Start jumping up and down and thumping chest.  
  4.2.2 Go to happy end.  
  4.3 If something isn't quite right, like in case of example below then it isn't.  
  4.3.1 Kick the stones in frustration and anger! Cuz it really is not sorted!  
  4.3.2 Go to sad end.

Przykład tablicy z 8 elementami. Nie posortowane :-( 

o
oo
oo
oo o
ooooo
ooooo
ooooo
oooooo
ooooooo
oooooooo
========
12345678

- Kod kontynuowany.

5. Sad end.  
  5.1 Eat an apple.  
  5.2 Fall from grace to next line.  
6. Happy end.

= - = - = - = - = - =
W celu dalszej optymalizacji, krok 4 liście stempli można zastąpić następującymi skrzydłami stempla.
= - = - = - = - = - = 

4. Roll a stone from top of position 1 towards top of position 8, pushing the rolling stone towards the top stone for each position while moving to the right.  
  4.1 If rolling stone reaches the position 8 then it's sorted.  
  4.1.1 Start jumping up and down and thumping chest.  
  4.1.2 Go to happy end.  
  4.2 If the rolling stone gets stuck in a trough, then it isn't.  
  4.3.1 Kick the stones in frustration and anger!  
  4.3.2 Go to sad end.

= - = - = - = - = - =
Dla was wszystkich oszustów kodu i debuggerów mocy, celowo dodałem błąd w powyższej drugiej odmianie kroku 4. Czy potrafisz go znaleźć?

— LMSingh
źródło
3
Znalazłem błąd - wszystko 4.3.*powinno być4.2.*
— Timtech
4

JavaScript

Właśnie dlatego zaskoczyła Cię „kreatywność”:

  • Ponieważ dla posortowanej tablicy

    * all the elements on the left side of any element must be smaller 
* all the elements on the right side of any element must be bigger

  • Dlatego uruchom główną pętlę dla wszystkich elementów i sprawdź powyższe dwa warunki, uruchamiając dwie zagnieżdżone pętle wewnątrz głównej (jedna dla lewej strony i jedna dla prawej strony)

Podaję więc implementację opisanego algorytmu w javascript:

function checkArraySorted(array) {
  for (a = 0; a < array.length; a++) {
    for (b = 0; b < a; b++) {
       if (array[b] > array[a]) return false;
    }
    for (b = a + 1; b < array.length; b++) {
       if (array[b] < array[a]) return false;
    }
  }
  return true;
}

Przetestujmy to:

checkArraySorted([]);
> true

checkArraySorted([1]);
> true

checkArraySorted([1, 2]);
> true

checkArraySorted([2, 1]);
> false

checkArraySorted([1, 2, 3]);
> true

checkArraySorted([1, 2, 3, 4]);
> true

Wydaje się działać idealnie! Ma złożoność O(n²)idealną dla algorytmu, który powinien być O(n), ale dzięki temu O(n²)staje się bardziej wydajny, ponieważ jest to miara wydajności, więc O(n²)jest bardziej wydajny niż O(n).

— Victor Stafusa
źródło
Nie chciałem używać „środka”. Pierwsza zagnieżdżona pętla miała wartość od 0 do a, a druga miała mieć wartość od + 1 do długości. BTW, 1,2,3 należy posortować, prawda?
— drobnoustrój
@microbian Ok, edytowane.
— Victor Stafusa
4

do

Odtąd „posortowane” oznacza „posortowane w porządku rosnącym”.

Tablica nie jest sortowana iff a[i]>a[i+1]

Więc jeśli pozwolimy x=a[i]-a[i+1] ,x będzie dodatni, jeśli tablica nie jest posortowana.

Aby przetestować xpozytywny wynik, możemy podzielić go na dwie części:x nie jest ujemna ix nie jest zerowa

Prostym testem na xto, czy jest ujemny, jest sprawdzenie, czy x*xjest on równy x*abs(x). Ten warunek powinien być fałszywy, jeślix jest ujemny, ponieważ(-1)*(-1)==1 .

Aby przetestować zero, możemy użyć innego prostego testu: 0./(float)xnie jest liczbą iffx wynosi zero.

Oto cały kod: (zakłada, że ​​tablica ma 5 elementów)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main() {
    int i, a[5];
    for(i=0;i<5;i++) scanf("%d",&a[i]);
    int sorted=1;
    for(i=0;i<4;i++) {
        int x=a[i]-a[i+1];
        if(x*x==x*abs(x)&&!isnan(0./(float)x)) {
            sorted=0;
            break;
        }
    }
    puts(sorted?"sorted":"not sorted");
    return 0;
}
— ace_HongKongIndependence
źródło
W rzeczywistości testowanie pod kątem a[i]-a[i+1] > 0jest już problematyczne. Nie musisz robić tego rodzaju rzeczy.
— n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳
Robienie niepotrzebnych rzeczy to cały trolling kodu, prawda? (A co masz na myśli przez problematyczne?)
— ace_HongKongIndependence
1
Przepełnienie ze znakiem całkowitym to UB. Nawet jeśli zdefiniujemy zachowanie zawijania, jeśli zrobimy INT_MAX - INT_MIN, wówczas wynikiem będzie liczba ujemna (zamień [i] na INT_MAX i [i + 1] na INT_MIN).
— n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳
Ponieważ jest to tylko zadanie domowe, załóżmy, że nauczyciel nie poda tak wielu liczb skrajnych.
— ace_HongKongIndependence
DOBRZE. Po prostu wolę trollować + być złym.
— n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳
4

Chodzi o to, jak pewny chcesz być. Ponieważ nie podano żadnej pewności, poniższe wyniki są całkiem dobre pod względem wydajności. Poniższy kod dobrze zgaduje, ale jeśli jesteś pewien, powinieneś powtórzyć tę funkcję kilka razy. Jeśli chcesz być naprawdę pewien, powinieneś uruchomić go w pętli i zrobić to kilkanaście razy. Idealna skalowalność!

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static const int size = 100;

int issorted(int *array, int size)
{
    int idx = random() % size;
    return (array[idx] >= array[0]);
}

void check_array(int *array, int size)
{
    if (issorted(array, size)) {
        puts("The array is sorted but I am not 100% sure.");
    } else {
        puts("The array is definitely not sorted in ascending order.");
    }
}

int main(void)
{
    int *array = malloc(sizeof(int) * size);
    int i = 0;

    srand(time(NULL));

    for (i = 0; i < size; i++) {
        array[i] = random();
    }

    check_array(array, size);

    for (i = 0; i < size; i++) {
        array[i] = i + 1;
    }

    check_array(array, size);
    free(array);

    return 0;
}

Czy to nie jest uczta?

— n0la
źródło
4

do

int is_sorted(int *T, int n)
{
return false;
}

Działa z prawdopodobieństwem 1- (1 / n!) I złożonością O (1). Oczywiście najlepsza metoda dla bardzo dużych losowych tablic.

Ponieważ złożoność wynosi tylko O ​​(1), dla lepszego oszacowania uruchom dwukrotnie.

— CPRI
źródło
3

do

Ta funkcja nie tylko informuje, czy tablica jest posortowana. Informuje o tym, ile elementów znajduje się we właściwym miejscu. Może być używany do dowolnego rodzaju danych.

Zwróć uwagę na znaczenie używania opisowych nazw zmiennych, aby ułatwić śledzenie kodu. Z drugiej strony nie musimy deklarować zmiennej i, ponieważ jest ona zadeklarowana gdzie indziej w programie.

int sortcheck(array_to_be_checked[10])
{
  int number_of_elements_in_right_place=0;

  for (i = 1; i = 10; i++)
    number_of_elements_in_right_place += i == array_to_be_checked[i];

  return number_of_elements_in_right_place;
}

Edycja: To lepszy sposób na większe tablice. Zaletą tego jest to, że jest podobny do sposobu, w jaki sprawdzałby człowiek.

int sortcheck(array_to_be_checked[32767])
{
  i=rand(); j=rand();
  while( (array_to_be_checked[i] > array_to_be_checked[j]) = (i > j) ) 
  {
    printf("I think it's sorted");
    i=rand(); j=rand();
  };
  printf("It wasn't sorted");
}
— Level River St
źródło
1
„Nie musimy deklarować zmiennej i, ponieważ musi ona zostać zadeklarowana gdzie indziej w programie”. było warte śmiechu.
— Jonathan Van Matre
@JonathanVanMatre Dzięki, ale to w żadnym wypadku nie jest jedyną wadą tego kodu.
— Level River St
3

JavaScript + więcej statystyk

Bardzo podobało mi się rozwiązanie sugerowane przez @Cominterm. Ale w porównaniu do już posortowanej listy? To jest oszukiwanie!

Zamiast tego obliczam autokorelację tablicy (korelacja między tablicą a tablicą przesunęła się o jedną pozycję w lewo). Następnie wiele razy tasuję tablicę i za każdym razem porównuję jej nową autokorelację z oryginalną autokorelacją. Gdyby tablica była posortowana, oryginalna autokorelacja byłaby najwyższa przez większość czasu!

http://jsfiddle.net/dB8HB/

Premia: Jeśli twoja wartość p <0,05, dane wyjściowe zautomatyzują zadanie stwierdzenia, że ​​tablica jest dla ciebie posortowana. O co więcej można prosić?

Bonus2: Chociaż ta implementacja korzysta z funkcji tablicy O (n) JavaScript dla wygody, podejście może wykorzystywać próbkowanie do działania w stałym czasie!

<form name="out"><textarea name="put" cols="80" rows="3">Press the button</textarea></form> 
<button onclick="startstop();">The button</button>
<script>
var iid=input=0, my=document.forms, isit={'true':0.5,'false':0.5}, ownAutocorr;
function startstop(){
     if(iid){
        clearInterval(iid);
        if(1 - isit.true / (isit.true+isit.false)<0.05){my.out.put.value+="\nYour array is sorted! (p<0.05)";}
        iid=input=0;isit={'true':0.5,'false':0.5}
     }
     else   {
        input=JSON.parse("["+prompt("Comma separated integers")+"]");
        ownAutocorr=pearsonCorrelation(input,cloneShiftArray(input));
        iid=setInterval(trial,50);
    }
}

function trial(){

 var newArr=shuffle(input.slice(0));
 var newAutocorr=pearsonCorrelation(newArr,cloneShiftArray(newArr));
 isit[newAutocorr<ownAutocorr]++;
 my.out.put.value="Your array is sorted with probability " + (isit.true / (isit.true+isit.false)).toFixed(2);
}

function cloneShiftArray(oldArr){
    var newArr=oldArr.slice(0); //clone the array
    var len=oldArr.length;
    //shift the array one
    for(var l=0;l<len-1;l++){
     //performance is important so we'll use bitwise operators
     newArr[l]^=newArr[l+1];
     newArr[l+1]^=newArr[l];
     newArr[l]^=newArr[l+1];
    }
    newArr[l]+=newArr[l-1   ];
    return newArr;
}
function pearsonCorrelation(p1, p2) { //Borrowed from teh interwebs
  var len = p1.length;
  var sum1=sum2=sum1Sq=sum2Sq=pSum = 0;
  for (var l = 0; l < len; l++) sum1 += p1[l];
  for (var l = 0; l < len; l++) sum2 += p2[l];
  for (var l = 0; l < len; l++) sum1Sq += Math.pow(p1[l], 2);
  for (var l = 0; l < len; l++) sum2Sq += Math.pow(p2[l], 2);
  for (var l = 0; l < len; l++) pSum += p1[l] * p2[l];
  var num = pSum - (sum1 * sum2 / len);
  var den = Math.sqrt((sum1Sq - Math.pow(sum1, 2) / len) *
      (sum2Sq - Math.pow(sum2, 2) / len));
  if (den == 0) return 0;
  return num / den;
}
function shuffle(array) {//also borrowed
  var currentIndex = array.length, temporaryValue, randomIndex;
  while (0 !== currentIndex) {
    randomIndex = Math.floor(Math.random() * currentIndex);
    currentIndex -= 1;
    temporaryValue = array[currentIndex];
    array[currentIndex] = array[randomIndex];
    array[randomIndex] = temporaryValue;
  }
  return array;
}
</script>
— Fabio Beltramini
źródło
3

JavaScript / SVG - sunDialsort

W tym rozwiązaniu nie stosuje się komparatorów <, <=,> lub> =. Próbowałem sprawić, by odczyt był tak mało jak funkcja sortowania, jak to możliwe.

metoda

  • Wykreśl wartości jako kropki wzdłuż łuku.
  • W przypadku tablicy rosnącej każda wartość powiększy całkowitą szerokość rysunku i nie zmniejszy początkowego X (wyjątek: dwie identyczne wartości).
  • Ponieważ szerokość nie może się zmniejszyć a! = Wystarczy,
  • Ponieważ X nie może wzrosnąć, wystarczy ==.
  • aby naprawić dwie identyczne wartości, każda kropka jest w rzeczywistości linią o coraz większej długości. Gdzie długość jednostki jest mniejsza niż 1 / liczba wartości.

Trolling

Dodałem następujące dłonie na twarzy w trakcie czytania tego bardzo złego kodu.

  • funkcja może wyglądać, jakby posortowała tablicę, o nazwie sunDialsort (premia złych wielkich liter)
  • zastosowano odniesienie lit-geek dla wszystkich nazw zmiennych
  • użył młota regex do zliczenia liczby elementów w tablicy
  • użył pola ostrzeżenia
  • rozwiązanie przypadku granicznego, w którym 2 kolejne zmienne są takie same, podwoiło ilość kodu (jedna linijka mogłaby go posortować), umieszczaj dużo tego kodu wcześnie, aby pomylić cel funkcji.
  • zamiast znajdować wartość minimalną i maksymalną, znajdź najdłuższą liczbę i zaokrąglić w górę do następnej potęgi dziesięciu, mam nadzieję, że zrzuci to ludzi z zapachu.

xml

<body>
<svg id="dial" height="400" width="400" transform=""></svg>
</body>

funkcjonować

sunDialsort = function (values)
{
    var twas = values.toString();  
    var brillig = twas.match(/,/g).length + 1; //<1>
    //find the sig figs we are working with (longest number)
    var and = [], the = 0;
    for (var jabberwock = 0; jabberwock < twas.length; jabberwock++)
    {
        switch (twas.charAt(jabberwock))
        {
        case ("."):
            break; //dont count
        case (","):
            and.push(the);
            the = 0;
            break;
        default:
            the++;
        }
    }
    and.push(the);
    var slithy = Math.max.apply(Math, and);
    //assume did/toves based on number of characters
    var toves = Math.pow(10, slithy);
    var did = toves * -1;
    console.log(did + "," + toves + "," + brillig);
    //for each number make a horizontal svg line of length (jabberwock*acuuracy)     
    var gyre = 1 / brillig;
    var gimble, wabe, all, mimsy, were, borogoves, mome, raths;
    var outgrabe = true;
    for (jabberwock = 0; jabberwock < brillig; jabberwock++)
    {
        gimble = document.createElementNS('http://www.w3.org/2000/svg', 'path');
        gimble.setAttribute("stroke", "blue"); //green is not a creative colour
        gimble.setAttribute("d", "M0 20 h " + (jabberwock * gyre));
        wabe = (values[jabberwock] - did) / (toves - did);
        mimsy = 90 - (wabe * 180);
        gimble.setAttribute("transform", "rotate(" + mimsy + ")");
        document.getElementById("dial").appendChild(gimble);
        borogoves = document.getElementById("dial").getBBox();
        if (mome)
        {
            raths = (borogoves.width != all && were == borogoves.x);
            console.log("test " + raths);
            all = borogoves.width;
            if (!raths)
            {
                outgrabe = false
            }
        }
        else
        {
            were = borogoves.x;
            all = borogoves.width;
            mome = true;
        }
    }
    return outgrabe
};
alert(sunDialsort([1, 2, 3, 3, 4341, 556]));

Jeśli ktoś chce przetestować, jest tutaj wersja z czytelnymi nazwami zmiennych. http://jsfiddle.net/outRideACrisis/r8Awy/

— OutRideACrisis
źródło
3

do

Ponieważ wyszukiwanie binarne działa tylko na posortowanych tablicach, aby sprawdzić, czy tablica jest posortowana, wystarczy sprawdzić, czy wyszukiwanie binarne działa dla wszystkich elementów tablicy. Jeśli nie uda się znaleźć żadnego elementu, wiemy, że tablica nie jest posortowana.

Przekazane argumenty wiersza poleceń muszą być liczbami całkowitymi dziesiętnymi bez zer wiodących.

#include <stdlib.h>
#include <string.h>

int compar(const void *a, const void *b) {
  char *const *sa = a, *const *sb = b;
  int cmp = strlen(*sa) - strlen(*sb);
  if (cmp == 0) cmp = strcmp(*sa, *sb);
  if (cmp == 0) cmp = sa - sb;
  return cmp;
}

int main(int argc, char *argv[]) {
  if (argc-- && argv++) {
    for (int i = 0; i != argc; i++) {
      if (bsearch(argv+i, argv, argc, sizeof *argv, compar) != argv+i) {
        return 1;
      }
    }
  }
  return 0;
}
— hvd
źródło
3

JavaScript

a = prompt("Please enter the data");
r = prompt("Does your array arouse moral distaste and contempt?");
if ((/yes/i).test(r))
  alert("The array is sordid.");
— Jason C.
źródło
1
{ 69 , 313 , 187 , 31338 }
— Geobits
2

do

  • Zrób kopię tablicy
  • posortuj kopię w porządku malejącym
  • sprawdź, czy ta tablica jest odwrotnością podanej tablicy
    #include<stdio.h>
    #include<stdlib.h>
    #include <stddef.h>
    #include<string.h>
    int main(){
     int arr[100],i,j,temp;
     int a[] = {1,2,3,4,5,6,7,8,9,10};
     char b[256];

     printf("Loading the program please wait...");
      int s = sizeof(a)/sizeof(a[0]);
     for(i=0; i<999999999; i++);//best way to make the program more realistic
     system("cls");

     for(i=0;i<s; i++ )
     arr[i] = a[i];

     for(i=0;i<s;i++){
          for(j=i;j<s;j++){
               if(arr[i] < arr[j]){
               temp=arr[i];
               arr[i]=arr[j];
               arr[j]=temp;
               }
           }
     } //sorting array in descending order

     int p = 0;
     for(i=0; i<s; i++)
     {
         if (a[s-i-1] != arr[i])
         p++;
     }

     if(p>0)
     printf("No");
     else
     printf("yes");
     getch();


     }
— Mhm
źródło
2

Matematyka

Ten algorytm wydaje się działać, ale jest nieco powolny. Być może istnieją szybsze sposoby sortowania, ale ich nie znalazłem.

  1. Weź losowe uporządkowanie listy i sprawdź, czy jest w porządku (z OrderedQ).
  2. Jeśli tak, przestań. W przeciwnym razie powtórz krok 1.

Poniższy kod posortował listę w nieco ponad 18 sekund. 

a = {23, 50, 16, 57, 19, 60, 40, 7, 30, 54};
n = 1;
Timing[While[! OrderedQ[a], a = RandomSample[a]; n++]]
n
a

{18.581763, Null}
8980699
{7, 16, 19, 23, 30, 40, 50, 54, 57, 60}

— DavidC
źródło
Zadanie polegało na sprawdzeniu, czy dane wejściowe są już posortowane.
— Ilmari Karonen
To jest podstawowa idea mojego rozwiązania (chociaż używam czasu kwadratowego OrderedQtylko dla miłośników gier) z dodatkowym sprawdzeniem na końcu „teraz, kiedy mamy posortowane, czy to jest to, od czego zaczęliśmy?”
— stoisko
2

JavaScript

function isSorted(arr) {
    if (arr.length === 1 && typeof arr[0] !== 'number' || arr[0].toString().indexOf('.') !== -1 || arr[0] > (-1 >>> 0) || arr[0] !== arr[0] || arr[0] === Infinity) {
        // Return false in the case of one non-number element.
        // isSorted returns false for arrays containing non-numbers for consistency
        // with PHP, but that doesn’t work for one element, so that’s the purpose
        // of this check.
        return false;
    }

    var obj = {};
    var i;

    for (i = arr.length; i--;)
        obj[arr[i]] = true;

    for (var x in obj)
        if (arr[++i] != x) return false;

    return true;
}

Ta funkcja może zwracać się falseniepoprawnie, ale nie w nowoczesnych przeglądarkach; możesz to sprawdzić i w razie potrzeby zapewnić wolniejszą rezerwę (jak opisano w pytaniu):

var isModern = /chrome/i.test(typeof navigator === 'object' && navigator.userAgent);

if (!isModern) {
    isSorted = function() {
        // I develop on good browsers, so the implementation is left as an exercise
        // to the reader if he or she wants to support outdated browsers.
    };
}

Mówią, że daje to nieprzewidywalne wyniki dla liczb ujemnych, ale tak naprawdę wszystko zależy od tego, jak dobrze potrafisz przewidywać różne rzeczy.

— Ry-
źródło
2
Chciałbym, żeby Chrome zmienił właściwości obiektów, aby ludzie nie robili takich rzeczy…
— Bergi
2

Java (odległość Levenshteina)

W tej implementacji sklonowałem oryginalną tablicę i posortowałem sklonowaną instancję. Następnie obliczana jest odległość Levenshteina. Jeśli wynosi zero, wówczas oryginalna tablica została posortowana.

Uwaga: Implementacja getLevenshteinDistance () jest pobierana z Jakarta Commons Lang i modyfikowana do pracy na int [] zamiast CharSequence.

import java.util.Arrays;

public class CheckSorting {

    public boolean isSorted(int[] array) {
        int[] sortedArray = Arrays.copyOf(array, array.length);
        Arrays.sort(sortedArray);

        return CheckSorting.getLevenshteinDistance(array, sortedArray) == 0;
    }

    public static int getLevenshteinDistance(int[] s, int[] t) {
        int n = s.length;
        int m = t.length;

        if (n == 0) {
            return m;
        } else if (m == 0) {
            return n;
        }

        if (n > m) {
            int[] tmp = s;
            s = t;
            t = tmp;
            n = m;
            m = t.length;
        }

        int p[] = new int[n + 1];
        int d[] = new int[n + 1];
        int _d[];

        int i;
        int j;

        int t_j;

        int cost;

        for (i = 0; i <= n; i++) {
            p[i] = i;
        }

        for (j = 1; j <= m; j++) {
            t_j = t[j - 1];
            d[0] = j;

            for (i = 1; i <= n; i++) {
                cost = s[i - 1] == t_j ? 0 : 1;
                d[i] = Math.min(Math.min(d[i - 1] + 1, p[i] + 1), p[i - 1] + cost);
            }

            _d = p;
            p = d;
            d = _d;
        }
        return p[n];
    }
}
— użytkownik3001267
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.