Lakukan NP: temukan klik terbesar

22

Latar Belakang

Pada saat penulisan ini, masalah P vs NP masih belum terpecahkan, tetapi Anda mungkin pernah mendengar tentang makalah baru Norbert Blum yang mengklaim bukti bahwa P! = NP, yang sudah diduga salah (tapi kita akan lihat nanti).

Masalah yang dibahas dalam makalah ini adalah masalah klik . Setidaknya itulah yang saya baca di artikel surat kabar, jadi perbaiki jika saya salah, tetapi dalam hal apa pun, saya ingin Anda menulis sebuah program yang memecahkan varian berikut:

Tugas

Anggaplah kita memiliki sekolah besar dengan banyak siswa. Masing-masing siswa memiliki beberapa teman di sekolah ini. Sebuah kelompok mahasiswa adalah kelompok yang terdiri hanya dari siswa yang berteman dengan setiap anggota lainnya .

Program Anda akan menerima pasangan siswa yang menjadi teman sebagai masukan. Dari informasi ini, program harus menemukan ukuran klik terbesar . Siswa diidentifikasi dengan ID integer .

Jika Anda lebih suka istilah matematika, ini berarti Anda mengumpankan tepi grafik yang tidak terarah, diidentifikasi oleh dua node masing-masing.

Memasukkan

Input Anda akan berupa daftar pasangan integer positif yang tidak kosong, mis [[1,2],[2,5],[1,5]]. Anda dapat mengambil input ini dalam bentuk apa pun yang masuk akal, misalnya sebagai array array, sebagai baris teks yang masing-masing berisi dua angka, dll ...

Keluaran

Output yang diharapkan adalah angka tunggal n >= 2: ukuran klik terbesar. Dengan contoh input di atas, hasilnya akan menjadi 3, karena semua siswa ( 1, 2dan 5) berteman satu sama lain.

Uji kasus

[[1,2]]
=> 2

[[1,2],[3,1],[3,4]]
=> 2

[[1,2],[2,5],[1,5]]
=> 3

[[2,5],[2,3],[4,17],[1,3],[7,13],[5,3],[4,3],[4,1],[1,5],[5,4]]
=> 4 (the largest clique is [1,3,4,5])

[[15,1073],[23,764],[23,1073],[12,47],[47,15],[1073,764]]
=> 3 (the largest clique is [23,764,1073])

[[1296,316],[1650,316],[1296,1650],[1296,52],[1650,711],[711,316],[1650,52],
 [52,711],[1296,711],[52,316],[52,1565],[1565,1296],[1565,316],[1650,1565],
 [1296,138],[1565,138],[1565,711],[138,1650],[711,138],[138,144],[144,1860],
 [1296,1860],[1860,52],[711,1639]]
=> 6 (the largest clique is [52,316,711,1296,1565,1650])

Anda dapat menggunakan implementasi referensi (bodoh) ini (mencetak hasil tambahan dengan -dbendera) untuk memverifikasi hasil dari kasus uji lainnya.

Aturan

  1. Program Anda tidak memerlukan hasil yang ditentukan pada input yang tidak valid. Jadi Anda dapat berasumsi bahwa:
    • Anda akan selalu mendapatkan setidaknya sepasang ID
    • setiap pasangan terdiri dari dua ID yang berbeda
    • tidak ada pasangan yang muncul dua kali (menukar tempat ID akan tetap menjadi pasangan yang sama)
  2. Algoritme Anda tidak diizinkan untuk menetapkan batas atas pada ukuran input. Batasan dan batasan teknis murni yang ditentukan oleh bahasa / lingkungan Anda (seperti ukuran tumpukan, waktu komputasi, dll) tentu saja tidak dapat dihindari.
  3. Celah standar dilarang.
  4. Ini adalah , jadi kode terpendek, diukur dalam byte, menang.
  5. Jika algoritme Anda memiliki kompleksitas waktu polinomial, Anda skor -1langsung terlepas dari ukuran kode Anda, tetapi dalam hal ini, Anda mungkin ingin mengirimkan solusi Anda di tempat lain. ;)
Felix Palmen
sumber
4
Saya hampir dapat menjamin bahwa akan ada seseorang yang akan melakukannya (atau mencoba), jadi itu akan lebih aman untuk menghapusnya. Jika Anda ingin memberi penghargaan kepada orang-orang karena melakukannya, Anda dapat menawarkan hadiah untuk jawaban terpendek yang melakukannya saat jumlahnya banyak.
caird coinheringaahing
4
@cairdcoinheringaahing jika seseorang melakukannya, -1itu memang layak ;)
Felix Palmen
13
@cairdcoinheringaahing Jika seseorang berhasil membuktikan bahwa P = NP, mereka memiliki skor terendah otomatis pada masalah kode golf adalah yang paling tidak menjadi perhatian kami. Yang mengatakan, Aturan 5 tidak benar-benar berkontribusi banyak pada tantangan, jadi saya setuju bahwa itu harus dihapus.
Mego
11
@Mego hanya menyumbangkan lelucon dan bonus kecil untuk 1 juta yang ditawarkan oleh CMI.
Felix Palmen
30
Yah, saya tidak akan, mendukung beberapa orang yang memiliki rasa "humor ilmiah". Tolong jangan berkomentar lebih banyak saran mengenai ini, terima kasih :)
Felix Palmen

Jawaban:

6

Jelly ,  15 18  16 byte

+3 byte untuk memperbaiki bug dalam metode saya.
-2 byte berkat mil (mencatat bahwa n × (n-1) ÷ 2 = nC2 )

ẎQL©c2⁼Lȧ®
ŒPÇ€Ṁ

Tautan monadik dengan mengambil daftar pertemanan (tepian) dan mengembalikan integer.

Cobalah online! membentuk power-set tepi dalam memori sehingga tidak efisien baik dalam ruang dan waktu (ya, itu O (2 n ) orang)!

Bagaimana?

ẎQL©c2⁼Lȧ® - Link 1, isClique?: list, edges  e.g. [[1,3],[2,3],[3,4],[4,1],[4,2],[2,1]]
Ẏ          - tighten                              [ 1,3 , 2,3 , 3,4 , 4,1 , 4,2 , 2,1 ]
 Q         - de-duplicate (gets unique ids)          [1,3,2,4]
  L        - length (get number of people involved)  4
   ©       - (copy to the register)
    c2     - combinations of 2 (z-choose-2)          6
       L   - length (of edges)                       6
      ⁼    - equal?                                  1
         ® - recall value from register              4
        ȧ  - logical and                             4
           - (Note: the number of edges of a clique of size n is n*(n-1) and we're
           -  guaranteed no repeated edges and that all edges are two distinct ids)

ŒPÇ€Ṁ - Link: list of lists, edges
ŒP    - power-set (all possible sets of edges (as lists))
  Ç€  - call last link (1) as a monad for €ach
    Ṁ - maximum
Jonathan Allan
sumber
Wow, penjelasan ketika Anda punya waktu, silakan
Tn. Xcoder
@EriktheOutgolfer Saya setuju. Saya mungkin dapat menambahkan kode untuk menyelamatkan ...
Jonathan Allan
Mari kita lanjutkan diskusi ini dalam obrolan .
Erik the Outgolfer
16 byte
mil
@miles - bagus, saya hanya menghabiskan beberapa waktu mencoba untuk mendapatkan 15 dari itu, saya merasa seperti itu mungkin!
Jonathan Allan
13

Mathematica, 34 byte

Tr[1^#&@@FindClique[#<->#2&@@@#]]&  

Pada dasarnya FindClique melakukan pekerjaannya dan "menemukan klik terbesar pada grafik g."
Semua hal lainnya adalah mengubah daftar input menjadi grafik

Memasukkan

[{{2, 5}, {2, 3}, {4, 17}, {1, 3}, {7, 13}, {5, 3}, {4, 3}, {4, 1}, {1, 5}, {5, 4}}]

Keluaran

4

Memasukkan

[{{1296, 316}, {1650, 316}, {1296, 1650}, {1296, 52}, {1650, 711}, {711, 316}, {1650, 52}, {52, 711}, {1296, 711}, {52, 316}, {52, 1565}, {1565, 1296}, {1565, 316}, {1650, 1565}, {1296, 138}, {1565, 138}, {1565 , 711}, {138, 1650}, {711, 138}, {138, 144}, {144, 1860}, {1296, 1860}, {1860, 52}, {711, 1639}}]

Keluaran

6

thanx @Kelly Lowder untuk -10 byte

J42161217
sumber
23
Tentu saja Mathematica memiliki dasar untuk ini.
Erik the Outgolfer
1
Shave off 10 Bytes denganTr[1^#&@@FindClique[#<->#2&@@@#]]&
Kelly Lowder
12
FindCliqueಠ ___ ಠ
Mr. Xcoder
6

Jelly , 20 byte

ŒPẎ€µQL’=ċЀ`ẠµÐfṪQL

Cobalah online!

Tentu saja ini tidak layak jutaan: p

Ini akan mengalahkan Pyth, jika bukan untuk µ(...)µdan 2-byte Ðf.

Erik the Outgolfer
sumber
Luar biasa. Saya mungkin juga menyerah sekarang.
Mark Thomas
@FelixPalmen brute force: p
Erik the Outgolfer
@EriktheOutgolfer Saya tidak bermaksud runtime kode;)
Felix Palmen
@FelixPalmen Maksudku, pendekatan brute force tidak perlu banyak berpikir: p
Erik the Outgolfer
Memberikan MemoryError dengan kasus uji terbesar :( Tentu saja masih valid, ini adalah "batasan teknis" - tetapi hanya karena penasaran, apakah ada cara untuk meningkatkan sumber daya yang tersedia dengan jelly?
Felix Palmen
3

J , 36 byte

[:>./](#(]*[=2!])#@~.@,)@#~2#:@i.@^#

Cobalah online!

Berjalan dalam waktu O (2 n ) di mana n adalah jumlah pasangan.

Solusi yang lebih cepat untuk 65 byte adalah

3 :'$>{._2{~.@((+.&(e.&y)&<|.)@(-.,-.~)&>/#&,/:~@~.@,&.>/)~^:a:y'

Cobalah online!

Penjelasan

[:>./](#(]*[=2!])#@~.@,)@#~2#:@i.@^#  Input: list of pairs
                                   #  Length
                           2      ^   2^n
                               i.@    Range [0, 2^n)
                            #:@       Binary
                         #~           Copy
      (                )@             For each
                      ,                 Flatten
                   ~.@                  Unique
                 #@                     Length
        (       )                       Dyad with RHS at previous and LHS as next
               ]                          Get RHS
             2!                           Binomial coefficient, choose 2
            =                             Equals
           [                              Get LHS
          *                               Times
         ]                                Get RHS
       #                                Length
[:>./                                 Reduce using maximum
mil
sumber
2

Python 2 , 180 byte

G=input()
m=0
L=len
for i in range(2**L(G)):
 u=[];p=sum([G[j]for j in range(L(G))if 2**j&i],u)
 for j in p:u+=[j][j in u:]
 m=max(m,L(u)*all(p.count(j)==L(u)-1for j in u))
print m

Cobalah online!

-2 Berkat shooqie .
-1 terima kasih kepada Tn . Xcoder .
-3 Berkat rekursif .

Erik the Outgolfer
sumber
Anda dapat menyimpan dua byte dengan menetapkan lenke variabel
shooqie
183 byte . (x not in y)berarti 0**(x in y).
Tn. Xcoder
@ Mr.Xcoder Saya tahu ada cara untuk mempersingkatnya! Terima kasih!
Erik the Outgolfer
Saya belum pernah menggunakan itu sebelumnya, hanya sebuah trik yang terlintas di benak saya beberapa hari yang lalu tetapi belum dapat digunakan untuk itu.
Tn. Xcoder
@ Mr.Xcoder Tidak masalah, jika berhasil maka mengapa tidak? : D BTW Anda juga dapat mengganti 0**dengan -~-.
Erik the Outgolfer
1

Pyth, 28 byte

l{sSef<T.{SMQm.{ft{T.Cd2yS{s

Cobalah online

Penjelasan

l{sSef<T.{SMQm.{ft{T.Cd2yS{s
                         S{sQ  Get the distinct nodes in the (implicit) input.
                        y      Take every subset.
             m      .Cd2       Get the pairs...
                ft{T           ... without the [x, x] pairs...
              .{               ... as sets.
     f<T                        Choose the ones...
        .{  Q                   ... which are subsets of the input...
          SM                    ... with edges in sorted order.
    e                           Take the last element (largest clique).
l{sS                            Get the number of distinct nodes.

sumber
1

Python 3 , 162 159 byte

lambda x,f=lambda x:{i for s in x for i in s}:len(f(x))if all([(y,z)in x or(z,y)in x for y in f(x)for z in f(x)if y<z])else max(c(x.difference({y}))for y in x)

Cobalah online!

Fungsi c mengambil simpul dalam bentuk satu set tupel yang diurutkan ({(x, y), ...} di mana x kurang dari y). Fungsi yang disebut "entri" ada di header TIO untuk menguji dengan data dalam daftar format daftar yang tidak disortir . Jika klik, kembalikan panjang. Jika tidak klik, kembalikan ukuran simpul klik maksimum, minus simpul untuk setiap simpul dalam simpul. Melebihi waktu pada test case terakhir di TIO

Perbarui: "atau (z, y) dalam porsi x" yang ditambahkan untuk menghapus ketergantungan pada penyortiran "f = lambda x: {i untuk s di x untuk i dalam s}" "alih-alih itertools.chain yang dibungkus set.

-minus 3 byte terima kasih kepada @Jonathan Allen

Conner Johnston
sumber
Selain itu - Anda tidak perlu menyebutkan nama c, sehingga dapat menghapus c=(Anda harus meletakkannya c=\di akhir tajuk dan menempatkannya lambdadi bagian atas blok kode untuk TIO)
Jonathan Allan
Andas juga dapat menyingkirkan dan mengganti s(...)dengan {*...}memungkinkan penghapusan beberapa ruang juga.
Jonathan Allan
1
@JonathanAllan terima kasih, penyortiran telah diperbaiki
Conner Johnston
1

Jelly , 28 byte

œ^e³;U¤
Œcç/Ðfœ|Ṣ¥/€QµÐĿ-ịḢL

Cobalah online!

Solusi lebih cepat yang mampu menyelesaikan kasus tes terakhir dalam sedetik di TIO.

mil
sumber
Dan kompleksitas apa yang dimilikinya? Jika lebih rendah dari O (2ⁿ) maka itu layak $ 1.000.000.
Erik the Outgolfer
1
@EriktheOutgolfer, Anda salah, ada algoritma yang memiliki runtime O (1.1888ⁿ) .
rus9384
Selain itu, bernilai satu juta, nmungkin hanya muncul di pangkalan :)
Felix Palmen
@ Feliksmen, atau tidak bisa. Pokoknya, untuk sejuta, satu dari dua pernyataan harus dibuktikan.
rus9384
1
Saya percaya ini O (1.414 ^ n). Anda dapat melihat kinerja yang lebih buruk ketika inputnya berupa grafik lengkap.
mil
1

Java + Jambu 23.0, 35 + 294 = 329 byte

import com.google.common.collect.*;
a->{int l=0,o=1,c,z=a.size();for(;o>0&l<z;){o=0;c:for(Iterable<int[]>s:Sets.combinations(a,l*(l+1)/2)){Multiset<Integer>m=TreeMultiset.create();for(int[]x:s){m.add(x[0]);m.add(x[1]);}c=m.elementSet().size();for(int e:m.elementSet())if (m.count(e)!=c-1)continue c;l+=o=1;break;}}return z<3?2:l;}

Algoritma ini bukan grafik, melainkan menghasilkan semua kombinasi pasangan, dengan ukuran tertentu. Saya memberi makan semua kombinasi pasangan ke dalam multiset dan memeriksa apakah semuanya memiliki ukuran yang diharapkan (jumlah entri unik - 1). Jika mereka melakukannya, saya menemukan sebuah klik dan saya mencari yang lebih besar.

Dari perpustakaan Guava, saya menggunakan combinationsmetode baru , dan tipe koleksi alat Multiset.

Tidak disatukan

import com.google.common.collect.*;
import java.util.function.*;

public class Main {

  public static void main(String[] args) {
    ToIntFunction<java.util.Set<int[]>> f
        = a -> {
          int l = 0, o = 1, c, z = a.size();
          for (; o > 0 & l < z;) {
            o = 0;
            c:
            for (Iterable<int[]> s : Sets.combinations(a, l * (l + 1) / 2)) {
              Multiset<Integer> m = TreeMultiset.create();
              for (int[] x : s) {
                m.add(x[0]);
                m.add(x[1]);
              }
              c = m.elementSet().size();
              for (int e : m.elementSet()) {
                if (m.count(e) != c - 1) {
                  continue c;
                }
              }
              l += o = 1;
              break;
            }
          }
          return z < 3 ? 2 : l;
        };
    int[][][] tests = {
      {{1, 2}},
      {{1, 2}, {3, 1}, {3, 4}},
      {{1, 2}, {2, 5}, {1, 5}},
      {{2, 5}, {2, 3}, {4, 17}, {1, 3}, {7, 13}, {5, 3}, {4, 3}, {4, 1}, {1, 5}, {5, 4}},
      {{15, 1073}, {23, 764}, {23, 1073}, {12, 47}, {47, 15}, {1073, 764}},
      {{1296, 316}, {1650, 316}, {1296, 1650}, {1296, 52}, {1650, 711}, {711, 316}, {1650, 52}, {52, 711}, {1296, 711}, {52, 316}, {52, 1565}, {1565, 1296}, {1565, 316}, {1650, 1565}, {1296, 138}, {1565, 138}, {1565, 711}, {138, 1650}, {711, 138}, {138, 144}, {144, 1860}, {1296, 1860}, {1860, 52}, {711, 1639}}
    };
    for (int[][] test : tests) {
      java.util.Set<int[]> s = new java.util.HashSet<int[]>();
      for (int[] t : test) {
        s.add(t);
      }
      System.out.println(f.applyAsInt(s));
    }
  }
}
Olivier Grégoire
sumber
Saya akan sangat terkejut, lihat Menemukan klik maksimum dalam grafik acak - tetapi saya perlu waktu beberapa saat untuk menganalisis kode ini, saya tidak terlalu terbiasa dengan Java :)
Felix Palmen
@FelixPalmen Saya menyukai tantangan ini sehingga jawaban saya akan tetap tidak peduli apa, tapi saya benar-benar baik-baik saja dengan menghapus "-1" jika itu bukan kompleksitas polinomial. Maka saya mungkin harus meninjau beberapa buku: P
Olivier Grégoire
" Kombinasi ukuran xadalah polinomial " <- apakah Anda yakin? Saya kira itulah metode yang digunakan . Nilai pengembaliannya adalah AbstractSetdengan iterator, dan forloop berikut akan memanggil iterator ini x!kali jika saya tidak salah ...
Felix Palmen
Koreksi: selama x < n(dengan nukuran lengkap set input), itu n!/(x!(n-x)!), masih belum jumlahnya banyak :)
Felix Palmen
@FelixPalmen Anda kemungkinan besar benar. Juga, apakah Anda mengatakan bahwa jika saya membuat combinationsmetode itu X^n(yang sepenuhnya mungkin), saya bisa mendapatkannya? Sementara itu, saya menghapus klaim saya atas "-1".
Olivier Grégoire
1

Python 2 , 102 byte

def f(g):
 x=g
 while x:y=x;x=map(set,{tuple(u|v)for u in x for v in x if u^v in g})
 return len(y[0])

Cobalah online!

mil
sumber
0

6502 kode mesin (C64), 774 703 byte

(Saya hanya harus melakukan ini, C64 saya dapat melakukan segalanya ... hehe)

hexdump:

00 C0 A9 00 A2 08 9D 08 00 CA 10 FA A2 04 9D FB 00 CA 10 FA 20 54 C0 B0 20 AD 
C9 C2 AE CA C2 20 92 C1 B0 31 8D 31 C0 AD CB C2 AE CC C2 20 92 C1 B0 23 A2 FF 
20 FE C1 90 DB 20 6A C2 20 C1 C1 B0 05 20 6A C2 50 F6 A5 FB 8D D3 C2 20 43 C1 
A9 CD A0 C2 20 1E AB 60 A2 00 86 CC 8E 61 C0 20 E4 FF F0 FB A2 FF C9 0D F0 10 
E0 0B 10 0C 9D BD C2 20 D2 FF E8 8E 61 C0 D0 E5 C6 CC A9 20 20 D2 FF A9 0D 20 
D2 FF A9 00 9D BD C2 AA BD BD C2 F0 5C C9 30 30 0E C9 3A 10 0A 9D CD C2 E8 E0 
06 F0 4C D0 E9 C9 20 D0 46 A9 00 9D CD C2 E8 8E BC C0 20 EB C0 AD D3 C2 8D C9 
C2 AD D4 C2 8D CA C2 A2 FF A0 00 BD BD C2 F0 0F C9 30 30 21 C9 3A 10 1D 99 CD 
C2 C8 E8 D0 EC A9 00 99 CD C2 20 EB C0 AD D3 C2 8D CB C2 AD D4 C2 8D CC C2 18 
60 38 60 A2 FF E8 BD CD C2 D0 FA A0 06 88 CA 30 0A BD CD C2 29 0F 99 CD C2 10 
F2 A9 00 99 CD C2 88 10 F8 A9 00 8D D3 C2 8D D4 C2 A2 10 A0 7B 18 B9 53 C2 90 
02 09 10 4A 99 53 C2 C8 10 F2 6E D4 C2 6E D3 C2 CA D0 01 60 A0 04 B9 CE C2 C9 
08 30 05 E9 03 99 CE C2 88 10 F1 30 D2 A2 06 A9 00 9D CC C2 CA D0 FA A2 08 A0 
04 B9 CE C2 C9 05 30 05 69 02 99 CE C2 88 10 F1 A0 04 0E D3 C2 B9 CE C2 2A C9 
10 29 0F 99 CE C2 88 10 F2 CA D0 D9 C8 B9 CD C2 F0 FA 09 30 9D CD C2 E8 C8 C0 
06 F0 05 B9 CD C2 90 F0 A9 00 9D CD C2 60 85 0A A4 09 C0 00 F0 11 88 B9 D5 C2 
C5 0A D0 F4 8A D9 D5 C3 D0 EE 98 18 60 A4 09 E6 09 D0 01 60 A5 0A 99 D5 C2 8A 
99 D5 C3 98 99 D5 C4 18 60 A6 0B E4 09 30 01 60 BD D5 C5 C5 0B 30 09 A9 00 9D 
D5 C5 E6 0B D0 E9 A8 FE D5 C5 8A 29 01 D0 02 A0 00 BD D5 C4 59 D5 C4 9D D5 C4 
59 D5 C4 99 D5 C4 5D D5 C4 9D D5 C4 A9 00 85 0B 18 60 A8 A5 0C D0 08 A9 20 C5 
0D F0 21 A5 0C 8D 1E C2 8D 21 C2 A5 0D 09 60 8D 1F C2 49 E0 8D 22 C2 8C FF FF 
8E FF FF E6 0C D0 02 E6 0D 18 60 86 0E 84 0F A5 0D 09 60 8D 54 C2 49 E0 8D 5F 
C2 A6 0C CA E0 FF D0 10 AC 54 C2 88 C0 60 10 02 18 60 8C 54 C2 CE 5F C2 BD 00 
FF C5 0E F0 04 C5 0F D0 E0 BD 00 FF C5 0E F0 04 C5 0F D0 D5 38 60 A2 00 86 FC 
86 FD 86 FE BD D5 C4 A8 A6 FE E4 FC 10 11 BD D5 C7 AA 20 2B C2 90 14 E6 FE A6 
FE E4 FC D0 EF A6 FD BD D5 C4 A6 FC E6 FC 9D D5 C7 E6 FD A6 FD E4 09 D0 16 A6 
FB E4 FC 10 0F A2 00 BD D5 C7 9D D5 C6 E8 E4 FC D0 F5 86 FB 60 A0 00 84 FE F0 
B5

Demo online

Penggunaan: Mulai dengan sys49152, lalu masukkan pasangan satu per baris seperti misalnya

15 1073
23 764
23 1073
12 47
47 15
1073 764

Backsapce tidak ditangani selama input (tetapi jika Anda menggunakanvice , cukup salin & tempel input Anda ke emulator). Masukkan baris kosong untuk memulai perhitungan.

Ini terlalu besar untuk mengirim daftar pembongkaran penjelas di sini, tetapi Anda dapat menelusuri sumber perakitan bergaya ca65 . Algoritma ini sangat tidak efisien, menghasilkan setiap permutasi yang mungkin dari node dan dengan masing-masing dengan rakus membangun klik dengan memeriksa semua tepi. Hal ini memungkinkan untuk efisiensi ruang dari O (n) (jenis penting pada mesin dengan RAM kecil ini), tetapi memiliki mengerikan efisiensi runtime (*) . Batas teoritis hingga 256 node dan hingga 8192 tepi.

  • -71 byte: dioptimalkan rutin untuk memeriksa tepi dan penggunaan zeropage

Ada versi yang lebih besar ( 883 805 byte) dengan fitur yang lebih baik:

  • umpan balik visual selama perhitungan (setiap permutasi node mengubah warna batas)
  • menggunakan peralihan bank untuk menyimpan bagian tepi dalam RAM yang "disembunyikan" oleh ROM untuk menghemat ruang
  • menampilkan ukuran dan simpul dari klik maksimal yang ditemukan

Demo online

Jelajahi sumber


(*) Test case terakhir membutuhkan waktu antara 12 dan 20 jam (saya tidur ketika akhirnya selesai). Kasus uji lainnya selesai paling buruk dalam beberapa menit.

Cuplikan layar dari test case terakhir

Felix Palmen
sumber