Setiap pemain memiliki nomor. Bisakah Anda menjadi yang terjauh dari semuanya?

Persyaratan

Tulis nama fungsi Java, Python 2, atau Ruby choose()yang menerima tiga argumen:

• bilangan bulat - jumlah putaran sudah selesai
• integer - jumlah pemain
• array string - hasil dari setiap putaran sebelumnya
  • setiap string adalah daftar bilangan bulat yang dipisahkan oleh ruang, disortir dari terendah ke tertinggi

Misalnya, choose(2, 4, ["4 93 93 174", "1 84 234 555"])berarti:

• sudah ada dua putaran (ini adalah putaran ketiga)
• total ada empat pemain
• di babak pertama, angka yang dipilih adalah 4, 93, 93, 174
• di babak kedua, angka yang dipilih adalah 1, 84, 234, 555

Anda harus mengembalikan seluruh nomor dari 1 hingga 999 (inklusif).

Untuk setiap pemain lain, skor Anda adalah akar kuadrat dari jarak antara nomor Anda dan mereka. Skor Anda untuk babak ini adalah total dari semua skor ini.

100 putaran akan dimainkan. Total skor tertinggi menang!

Aturan

• Kode Anda tidak boleh menggunakan I / O, termasuk konsol, file, jaringan, dll.
• Anda tidak boleh mengganggu program kontrol atau pemain lain.
• Program yang sepertinya melanggar aturan di atas akan dikecualikan.
• Setiap panggilan fungsi harus di bawah lima detik di komputer saya (Intel Core i5 2450M dengan 8GB RAM).
• Jika suatu program melempar pengecualian atau mengembalikan nilai yang tidak valid, itu akan diperlakukan seolah-olah itu mengembalikan 1.
• Setiap pengguna dapat mengirimkan paling banyak satu program.

Lain-lain

• Program kontrol ada di GitHub .
• Ada tiga pemain built-in. Mereka dapat ditemukan dalam jawaban ini .
• Pemenang akan dipilih pada 28 Januari.

Papan peringkat

Pemenangnya adalah Konservator .

Sebutan terhormat untuk Gustav , pemain dengan skor tertinggi dengan strategi tidak konstan.

• Konservator - 36226
• Tinggi - 36115
• FloorHugger - 35880
• NumberOne - 35791
• Overestimator - 35791
• Gustav - 35484
• Sejarawan - 35201
• Sampler - 34960
• Incrementer - 34351
• JumpRightIn - 34074
• Vickrey - 34020
• Remaja - 33907
• Randu - 33891
• Angkat Besi - 33682
• Perantara - 33647
• BounceInwards - 33529
• NastyMathematician - 33292
• Jumper - 33244
• Copycat - 33049

Hasil lengkapnya dapat ditemukan di sini . (Saya sarankan menonaktifkan pembungkus teks.)

Python, Konservator

def choose(round, players, scores):
    return 999

Karena setiap pengecualian melempar 1, ia menjauh sejauh mungkin darinya. Membuat kekayaan dengan mengorbankan yang lemah.

Fakta menyenangkan: Saya berpikir untuk memperbaikinya, tetapi tidak bisa menemukan cara yang lebih baik daripada hanya bersembunyi di sudut.

Nomor Satu, Jawa

Namanya menjelaskan ini sepenuhnya.

public static int choose(int round, int players, String[] args) {
    return 1;
}

Python, AncientHistorian

Tegas percaya bahwa masa depan akan persis seperti masa lalu, tetapi percaya bahwa ronde terakhir terlalu baru untuk menjadi histiry, sehingga hanya melewati 1-999 dan memilih apa yang akan menjadi yang terbaik dari putaran sebelumnya kecuali yang terakhir. 2 babak pertama menghasilkan 500.

def choose(round, players, scores):
    calc = lambda n, scores: sum([abs(int(i)-n)**.5 for i in scores.split(' ')])
    return max(range(1, 1000), key=lambda n: sum([calc(n, j) for j in scores[1:]])) if round>1 else 500

Python, Vickrey

def choose(rounds, players, results):        
    if not results:
        return (id(0)/7)%999 + 1

    def best(array):
        score = lambda x: sum(abs(x-y)**.5 for y in array)
        m = max(score(x) for x in range(1, 1000))
        return [x for x in range(1, 1000) if score(x) == m]

    def second_best(array):
        array.extend(best(array))
        options = best(array)
        return options[(id(0)/7) % len(options)]

    results = [map(int, s.split()) for s in results]
    counts = {}

    for round_ in results:
        for number in round_:
            counts[number] = counts.get(number, 0) + 1

    most_common = sorted([(c, n) for n,c in counts.items()], reverse=True)
    to_avoid = [t[1] for t in most_common[:players]]

    return second_best(to_avoid)

Membuat daftar angka yang sudah sering diputar, mengasumsikan bahwa semua orang akan bermain secara optimal dan memilih yang kedua pilihan terbaik diberikan daftar.

Misalnya, jika angka yang paling umum adalah [1, 990, 999], maka Vickrey menyisipkan permainan optimal 200 untuk diberikan [1, 200, 990, 999], kemudian memilih opsi terbaik untuk array baru (yaitu 556).

Java, Overestimator

Seperti namanya, program ini mengasumsikan semua program lain akan mencoba bermain "dengan baik" dengan memilih jawaban terbaik berdasarkan putaran terakhir - jadi "overestimator" ini selalu memilih posisi terburuk berdasarkan putaran sebelumnya.

 public static int choose(int round, int players, String[] args) {
     String[] lastRoundStrings = args[args.length - 1].split(" ");
     int[] lastRound = new int[lastRoundStrings.length];
     int worstSelection = 0;
     for (int i = 0; i < lastRound.length; i++) {
         double worstScore = Double.MAX_VALUE;
         for (int j = 1; j < 999; j++) {
             double computedScore = score(j, lastRound);
             if (computedScore < worstScore) {
                 worstScore = computedScore;
                 worstSelection = j;
             }
         }
     }
     return worstSelection;
 }

 public static double score(int position, int[] otherPositions) {
     double total = 0;
     for (int i = 0; i < otherPositions.length; i++) {
         total += Math.sqrt(Math.abs(otherPositions[i] - position));
     }
     return total;
 }

Java - Angkat Besi

Putar 1-999 untuk mencari tahu mana yang akan menjadi yang terbaik untuk setiap putaran. Timbang sesuai dengan kebaruan (putaran terakhir memiliki bobot lebih), dan kembalikan tebakan keseluruhan terbaiknya. Mudah-mudahan jika pola terbentuk di babak selanjutnya, ini akan dapat mengambilnya.

Sunting: Sekarang dengan + Inf% lebih banyak rekursi! Tidak bisa menyimpan / menyimpan / melihat apa yang Anda pilih pada putaran sebelumnya adalah hambatan. Mengambil masukan Anda sendiri ke messes akun Anda ketika mencoba untuk mencari tahu apa yang orang lain akan lakukan. Jadi, mari kita hitung! Ini sekarang akan berulang untuk mencari tahu apa yang dipilih pada putaran sebelumnya dan mengabaikan itu ketika menghitung langkah selanjutnya.

Perhatikan bahwa itu hanya benar - benar mengabaikan input sendiri dari belokan terakhir, tetapi karena yang tertimbang yang tertinggi, tampaknya berfungsi dengan baik. Ini bisa diperbaiki dengan sedikit lebih banyak pekerjaan, tetapi saya akan menunggu leaderboard untuk melihat apakah itu diperlukan.

int choose(int rounds, int players, String[] hist){
    if(rounds < 1)
        return 1;

    int lastChoice = choose(rounds-1,players,java.util.Arrays.copyOf(hist, hist.length-1));

    int[][] history = new int[hist.length][players];
    for(int i=0;i<hist.length;i++){
        String[] tokens = hist[i].split(" ");
        boolean flag = false;
        for(int j=0;j<tokens.length;j++){
            history[i][j] = Integer.parseInt(tokens[j]);
            if(i==history.length-1 && history[i][j]==lastChoice && !flag){
                flag = true;
                history[i][j] = -1;
            }
        }
    }

    double best = 0;
    int guess = 1;
    for(int i=1;i<1000;i++){
        double score = 0;
        for(int j=0;j<history.length;j++){
            double weight = (double)(j+1)/history.length;
            for(int k=0;k<history[j].length;k++){
                if(history[j][k] > 0)
                    score += Math.sqrt(Math.abs(history[j][k]-i)) * weight;
            }
        }
        if(score > best){
            best = score;
            guess = i;
        }
    }
    return guess;
}

Ruby, Copycat

Cukup kembalikan nomor yang menang terakhir kali.

def choose r, p, hist
  last = hist.last.split.map &:to_i
  scores = last.map{|n| last.map{|m| (n-m).abs ** 0.5 }.inject :+ }
  last[scores.index scores.max]
end

Ruby, JumpRightIn

def choose(round, players, args)
    return 500 if args.size == 0
    last_round = args[-1].split.map(&:to_i) + [1000]
    max_gap = 0
    last = 0
    move = 1
    last_round.each { |i|
        gap = i - last - 1
        if gap > max_gap
            max_gap = gap
            move = (i + last)/2
        end
        last = i
    }
    move
end

Ini mungkin strategi yang paling mudah. Ia menemukan celah terbesar di babak terakhir, dan memilih angka tepat di tengah-tengah celah itu.

Gustav (Python 2)

Ini adalah strategi meta yang cukup lurus ke depan, disalin tanpa malu-malu dari salah satu jawaban lama saya dalam tantangan KotH yang serupa. Ini mempertimbangkan beberapa strategi sederhana, terlihat bagaimana mereka akan melakukan semua putaran sebelumnya, dan kemudian mengikuti satu penilaian tertinggi untuk babak berikutnya.

def choose(k, N, h):
    if k<2: return 999
    H = [[int(x) for x in l.split()] for l in h]
    score = lambda x,l: sum(abs(x-y)**.5 for y in l)
    S = [range(1,1000)
         + [max(range(1,1000), key=lambda x: score(x, H[i-1]))]
         + [max(range(1,1000), key=lambda x: score(x, H[i-2]))]
         + [min(range(1,1000), key=lambda x: score(x, H[i-1]))]
         + [min(range(1,1000), key=lambda x: score(x, H[i-2]))]
         for i in range(2,k+1)]
    scores = [sum(score(s[j],l) for s,l in zip(S[:-1], H[2:]))
              for j in range(len(S[0]))]
    return max(zip(scores, S[-1]))[1]

Saya menyadari sekarang bahwa algoritma ini masih memiliki beberapa kekurangan. Misalnya ia mungkin terus "mengejar dirinya sendiri" karena ia tidak membedakan gerakannya sendiri dari gerakan lawan. Namun, saya akan membiarkannya seperti ini untuk saat ini.

Python, Randu

Angka dipilih oleh penghasil angka acak yang paling tidak masuk akal yang pernah ada .

def choose(round, players, scores):
    x = 15
    for i in range(round * players + 1):
        x = (x * 65539) % 2147483648
    y = int((x / 2147483648.0) * 999.0)+1
    return y

Tiga program berikut ini terintegrasi.

Tinggi (Ruby)

def choose(round, players, args)
    return 990
end

Incrementer (Jawa)

public static int choose(int round, int players, String[] args) {
    return round * 10 + 5;
}

FloorHugger (Python)

def choose(round, players, args):
    if len(args) == 0:
        return 10
    last = args[-1].split();

# next line from http://stackoverflow.com/a/7368801/3148067
    last = map(int, last)

    dist = 0
    for i in range(1, 999):
        if i in last:
            dist = 0
        else:
            dist = dist + 1
            if dist == 10:
                return i
    return 500

Python, Sampler

Di luar daftar tempat, pilih tempat yang paling jauh dari angka yang baru digunakan, abaikan giliran sebelumnya.

def choose(turn, players, history):
    sample = map(int, (' '.join( history[-5:-1] )).split())
    def distance(x): return sum(abs(x-y)**0.5 for y in sample)
    places = range(1, 1000, 13)
    score, place = max((distance(x), x) for x in places)
    return place

Java, BounceInwards

Mulai dari 1, secara bertahap semakin mendekati 500 sambil memantul antara opsi yang lebih tinggi dan lebih rendah.

public static int choose(int round, int players, String[] args) {
    return round%2 == 0 ? round * 5 : 1000 - round * 5;
}

NastyMathematician (Jawa)

Periksa dua putaran terakhir (jika angka terbaik adalah 70 dan 80, itu akan menghasilkan 90). Itu jahat karena mencoba mengambil angka setinggi mungkin untuk menang melawan lawan-lawannya.

public static int choose(int round, int players, String[] args) {
    if (round == 0) {
        return 999;
    }

    int[][] results = new int[args.length][players];

    // parse input
    for (int i = 0; i < args.length; i++) {
        String[] rounds = args[i].split(" ");
        for (int j = 0; j < rounds.length; j++) {
            results[i][j] = Integer.parseInt(rounds[j]);
        }
    }

    int bestNumber = 0;
    double bestScore = -1;

    // get the best number for the last round
    for (int i = 1; i < 1000; i++) {
        double score = 0;
        for (int result : results[results.length - 1]) {
            score += Math.sqrt(Math.abs(i - result));
        }
        if (score >= bestScore) {
            bestScore = score;
            bestNumber = i;
        }
    }

    if (round == 1) {
        return bestNumber;
    }

    int bestNumber2 = 0;
    double bestScore2 = -1;

    // get the best number for the second last round
    for (int i = 1; i < 1000; i++) {
        double score = 0;
        for (int result : results[results.length - 2]) {
            score += Math.sqrt(Math.abs(i - result));
        }
        if (score > bestScore2) {
            bestScore2 = score;
            bestNumber2 = i;
        }
    }

    // add the difference between last round and second last round to get this rounds best number
    int difference = bestNumber - bestNumber2;
    bestNumber = bestNumber + difference;

    return bestNumber > 999 ? 999 : bestNumber;
}

Python - Saya tidak ingin memikirkan nama ...

Jika rata-rata angka yang dipilih dalam putaran terakhir kurang dari 500, itu memilih 999. Itu memilih 1 sebaliknya.

def choose(a,b,c):
    total=0
    for i in c:
        for j in i.split(" "):
            total+=int(i)
    average=total/(a*b)
    if average<500:
        return 999
    return 1

Python, Middleman (berdasarkan konservator oleh @clabacchio)

def choose(round, players, scores):
    return 500;

Setelah saya perhatikan bahwa tepi atas skor tinggi (dan mengungguli tepi bawah), saya bertanya-tanya apakah ada yang lebih buruk daripada hanya terjebak di tengah.

Jumper (Ruby)

def choose(round, players, args)
    495*(round%3)+5
end

Bergantian antara bagian bawah, tengah dan atas. (5.500.995)