Herkese merhabalar,
linkindeki soruyu çözmeye çalışıyorum. Ama bu soruyu çözmek için nasıl bir algoritma oluşturacağımı bulamadım.
Bu soruyu çözmek için nasıl bir algoritma uygulamalıyım ?
Yardımlarınız için şimdiden teşekkür ederim.
Sorunun sacma sapan geyiklerden arinmis versiyonu var mi?
Bir keresinde fontu beğenmediğimiz için o ana kadar yazılmış olan tüm soruları silme kararı almıştık. Bir sefer de yandaki marketten almak çok yorucu gelmiş olsa gerek; tüm CodeFest ekibi olarak Londra’daki Adana Şalgamı Günü’ne katılmak için günübirlik Londra’ya uçmuştuk.
Haklısın, biraz komedyenlik yapmayı tercih etmiş gibi görünüyorlar.
Ben soruyu şöyle anladım:
Oyunda 124 kart vardır.
input format: seyircinin rasgele seçtiği 5 kart
Burada cem, 5 karttan rasgele birini değil, Rena’nın %100 tahmin edeceği bir sayıyı seçmeli.
İş burada bitmiyor tabi: Cem, kalan 4 kartı, Rena’nın 5. kartı %100 bilebilmesi için ilk 4 kartı doğru sıra ile Rena’ya göstermesi gerekiyor.
Kısaca output olarak Rena’ya göstermesi gereken kartları ve sırasını istiyor.
Sana yardımcı olması bakımından birtakım input-outputlar:
https://paste.ubuntu.com/p/QHt9Kp6xnR/
Bunu dün veremedim, çünkü mobilde her input ve output ı sorunun ait olduğu siteden alarak teker teker ellerimle yazmak zorundaydım.
Sirf sen aciklamaya ugrastin diye ben de gidip bastan sona okumaya ugrastim :)
Anladigim kadariyla problem su:
- Rastgele 5 tane (tekrarsiz) 0-123 arasi tamsayi seciliyor
- Girdi olarak ilk 4’u herhangi bir sirayla verildiginde, 5.'nin ne oldugunu bulacak algoritma isteniyor
Sirali 4 kartin permutasyonu 24 tane. Yani kartlarin sirasiyla log₂(24) bitlik bilgi aktarimi mumkun; kalan karti bulmak icin yetersiz. Ancak bulunacak karti secebiliyorsak, bir log₂(5) bit de oradan geliyor; toplam log₂(120) bit bilgi ile 120 karttan birini ucu ucuna bulabiliriz gibi gozukuyor. Yani:
- Girdi olarak belirli 4’u belirli bir sirayla verildiginde, geriye kalanin ne oldugunu bulacak algoritma isteniyor
Sayilar rastgele geldigi icin paritelerini kullanmak gerekiyor gibi geliyor.
Algoritmayi dusunuyorum…
log₂(24) tam olarak neye eşit oluyor henüz logaritma görmediğim için bilmiyorum ufak bir araştırma yaptım ama sadece tabanların değişmediğini üstlerin yer değiştirdiğini v.s gördüm yani 2 üzeri x = 11 gibi ifadelerde kullanılıyormuş fakat bu değer tam olarak neye eşit
log₂(24) = 4.5850…
Logaritma bilmiyorsan temsil ettigi Shannon entropisine hic girmeyeyim o zaman.
Ama soyle ozetleyebilirim: 24 karttan biri gizlice secilirse, secilen karti bulmak icin kac tane evet-hayir sorusu sormak gerekiyor? Cevap 4.585…
Hesap makinende log₂ yoksa:
log₂(x) = logₙ(x) / logₙ(2)
Bu arada rastgele mi deniyorsun @Cihat_Altiparmak?
Sey denesene…
1 2 3 4 5
1 2 3 4 6
1 2 3 4 120
1 2 3 5 4
1 2 4 3 5
100 101 102 103 104
Pattern (oruntu) bulmak icin pattern denemek lazim.
Abi işin aslı, codefest diye bir yarışma var. Bu soru da geçmiş yıllarda sorulmuş problemlerden biri.
Adamlar soruyu verir, input siteden zaten verilir, output’ı sen oluşturursun.
En başta sadece 2 input-output verilmişti soruda.
Ben de bu 2 input-output 'a bakınca bir an küçükten büyüğe sıralama zannettim.
Buna göre kod yazıp bu kodu siteye submit’ledim.
Ben sana tüm input-output’ları veremedim ama,
30 tane input-output’dan sadece sorunun en başta kendi verdiği 2 input-output’ı sağladı.
Ben de bu soru nasıl çözülebilir diye düşünmeye başladım.
Google’da 124 kart oyunu vs. vs. arattırdım, ne yazık ki hiçbir şey çıkmadı.
Bunun üzerinde platformlara sormaya karar verdim. Olur ya, matematiği benden yüksek olan biri çıkar belki diye.
Son olarak, kusura bakma, ben sana 30 Input-Output 'dan sadece 12 tane verebildim. 30 Input-Output’ın tümünü istersen senin için uğraşıp tümünü verebilirim.
Bunların hepsini ben de yaşadım. Ama bir çözüm bulamadım.
Hiç mantıklı değil.
Neden 124? Hangi sayıyı seçmeli? Nasıl sıralamalı? Sayılara bağlı bir sıralama mı var? 30 farklı input için 30 farklı output yöntemi mi yazmalı? Tek bir kural mı var? Babam böyle pasta yapmayı nereden öğrendi?
1 Beğeni
Ha pardon, ben su anda siteye girip ornek input-output alabiliyorsun zannettim. Kasma yoksa, algoritmayi bulmak daha zevkli zaten.
Challenge sitelerine asikarim ama hackerrank un/pw’mi bulamadim. Daha cok vaktim oldugu bir ara tekrar bakarim, iyice denerim.
Bu arada belki 124 kart degil—derken aklima once bunu 2 secilmis kartla cozmek geldi. Evet, dur bakayim bugun bunu dusuneyim 
1 Beğeni
Anladım teşekkür ederim ay olsaydı log 2 tabanında 12 yapacaktık o zaman biraz araştırdım bu shannon entropisini ama logaritma öğrenmeye başlasam zor gelir mi 10. sınıf yeni bitti.
Ustlu sayilari biliyorsan gelmez.
2⁵ = 32
log₂(32) = 5
log₂(2ⁿ) = n
logₓ(xⁿ) = n
10^(2.5) = 316.23
iki tarafin da log₁₀unu al:
log10(10^(2.5)) = log10(316.23)
2.5 = log10(316.23)
Her bir evet-hayir sorusu olasiliklari ikiye boluyor.
Oyleyse n soru olasiliklari 2ⁿ’e boluyor.
Oyleyse X olasiligi bulmak icin gereken ideal soru sayisi log₂(X).
Ornegin: 1 ile 8 arasinda sayi tuttum (5)
S1: Sayi 4.5’tan buyuk mu? (1/2/3/4 mu yoksa 5/6/7/8 mi)
C1: Buyuk (5/6/7/8)
S2: 6.5’tan buyuk mu? (5/6 mi 7/8 mi)
C2: Kucuk (5/6)
S3: 5.5’tan buyuk mu? (5 mi 6 mi)
C3: Kucuk (5)
5!
2 Beğeni
Bu arada bir SAT solver yardimiyla sorunun ufak versiyonlarinin cozumlerini cikarttim:
import itertools as it
ALPHA = [1,2,3,4,5,6]
HAND = 3
hands = list(it.combinations(ALPHA, HAND))
hand_shows = { hand: [show for show in it.permutations(hand, HAND-1) if all(map(lambda s: s in hand, show))] for hand in hands }
hslen = len(hand_shows[hands[0]])
print(len(hands), "hands")
def encode(hand, show):
return hands.index(hand) * hslen + hand_shows[hand].index(show) + 1
def decode(n):
hand = hands[(n-1) // hslen]
show = hand_shows[hand][(n-1) % hslen]
return hand, show
constraints = []
for hand in hands:
constraints.append(list(map(lambda s: encode(hand, s), hand_shows[hand])))
for hand in hands:
for s1, s2 in it.combinations(hand_shows[hand], 2):
constraints.append([-encode(hand, s1), -encode(hand, s2)])
for h1, h2 in it.combinations(hands, 2):
for s1, s2 in it.product(hand_shows[h1], hand_shows[h2]):
if s1 == s2:
constraints.append([-encode(h1, s1), -encode(h2, s2)])
import pycosat
solutions = pycosat.itersolve(constraints)
for sol in solutions:
print("---")
for c in sol:
if c > 0:
hand, show = decode(c)
print(hand, "->", show)
break
Kod dogasi geregi cirkin oldu, terimleri aciklamak lazim:
-
ALPHA-> alfabe, kullanilan kartlar -
HAND-> secilen kart sayisi (bir azi gosterilecek) -
hand-> secilen kartlar -
show-> sihirbaza gosterilen kartlar, sirasiyla
Program her hand icin essiz bir show bulmaya calisiyor. Belki guzel bir oruntu yakalayip bir algoritma cikartabilirim dedim, fakat cozum uzayi cok buyuk. Kart sayisini filan artirip az sayida cozumlu parametreler bulmaya calisacagim, belki o zaman olur.
Ornek iki cozum:
(1, 2, 3) -> (3, 2)
(1, 2, 4) -> (4, 2)
(1, 2, 5) -> (5, 2)
(1, 2, 6) -> (6, 2)
(1, 3, 4) -> (4, 3)
(1, 3, 5) -> (5, 3)
(1, 3, 6) -> (6, 3)
(1, 4, 5) -> (5, 4)
(1, 4, 6) -> (6, 4)
(1, 5, 6) -> (6, 5)
(2, 3, 4) -> (3, 4)
(2, 3, 5) -> (3, 5)
(2, 3, 6) -> (2, 3)
(2, 4, 5) -> (2, 5)
(2, 4, 6) -> (2, 4)
(2, 5, 6) -> (2, 6)
(3, 4, 5) -> (4, 5)
(3, 4, 6) -> (4, 6)
(3, 5, 6) -> (3, 6)
(4, 5, 6) -> (5, 6)
(1, 2, 3) -> (3, 2)
(1, 2, 4) -> (4, 2)
(1, 2, 5) -> (5, 2)
(1, 2, 6) -> (6, 2)
(1, 3, 4) -> (4, 3)
(1, 3, 5) -> (5, 3)
(1, 3, 6) -> (6, 3)
(1, 4, 5) -> (5, 4)
(1, 4, 6) -> (6, 4)
(1, 5, 6) -> (6, 1)
(2, 3, 4) -> (3, 4)
(2, 3, 5) -> (3, 5)
(2, 3, 6) -> (2, 3)
(2, 4, 5) -> (2, 5)
(2, 4, 6) -> (2, 4)
(2, 5, 6) -> (2, 6)
(3, 4, 5) -> (4, 5)
(3, 4, 6) -> (4, 6)
(3, 5, 6) -> (3, 6)
(4, 5, 6) -> (5, 6)
HAND=2 icin |ALPHA|=3’te 2 cozum var:
(1, 2) -> (2,)
(1, 3) -> (1,)
(2, 3) -> (3,)
---
(1, 2) -> (1,)
(1, 3) -> (3,)
(2, 3) -> (2,)
daha otesinde yok.
HAND=3’te 8 kart icin binlerce cozum var, 9 kart icin cozum bulamadim.
Yukarida yaptigim “x kartin siralamasi veya x’ten 1 kartin secilmesi + kalan (x-1)'in siralamasi” entropisi formulu tutuyor:
Max |ALPHA| = HAND! + HAND - 1
Acaba OEIS ne diyecek…
Bu böyle değil de daha çok bir insanın seyirciyi fazla bekletmeden cevaplamasını sağlayacak bir çözüm olmalı.
Sunu yazayim, alt alta 4 reply olmadigindan kalmisti:
…A030495 - OEIS dedi
a(n) is also the maximum size for a deck of cards in the Communicating the Card magic trick.
Gosterilen her el dogrudan bir sakli karta tekabul ediyor, beklenecek veya bekletilecek bir sey yok.
1 Beğeni
Herkese merhabalar,
Problemin mantığını anlamış bulunmaktayım. Bu sorunu çözmemde yardımcı olduğu için @aib 'e teşekkür etmekteyim.
Mantığını size şu anda açıklayamamakla birlikte şuradan mantığını ingilizce olarak anlatıyor. Müsait bir zaman bulabilirsem mantığını da anlatmayı çok isterim.
#include <bits/stdc++.h>
using namespace std;
int get_index(vector<int> x, int wanted, int n)
{
for(int i=0; i<n; i++)
{
if(wanted == x[i]) return i;
}
}
int f(int a, int b){return a<b;}
int factorial(int n)
{
if(n<=1) return 1;
return factorial(n-1) *n;
}
int lexicographic_sorting(vector<int> arr, vector<int> b)
{
int graduate = 0;
int n = 4;
for (int i = 0; i < 4; i++)
{
int index = get_index(b, arr[i], n);
graduate += index * factorial(4-i-1);
b.erase(b.begin() + index);
n--;
}
return graduate;
}
int main(){
vector<int> deck(4);
vector<int> X;
for(int i=0; i<4; i++)
{
cin>>deck[i];
}
int total = 0;
for(int i=0; i<4; i++){
total += deck[i];
}
vector<int> b;
for(int i=0; i<4; i++) b.push_back(deck[i]);
sort(b.begin( ), b.end( ), f);
// ihtimaller
int k=0;
int limit=b[k];
int i = 1;
while(i<=124)
{
if(i>=limit){
i = limit + 1;
k++;
k==4 ? limit = 125 : limit = b[k];
continue;
}
if((i + total)%5==(k+1)%5 ) X.push_back(i);
i++;
}
cout<<X[lexicographic_sorting(deck, b)];
return 0;
}
bu kod verilen 4 karttan yararlanarak saklanan 5.kartı bulur.
#include <bits/stdc++.h>
using namespace std;
int get_index(vector<int> x, int wanted, int n)
{
for(int i=0; i<n; i++)
{
if(wanted == x[i]) return i;
}
return -1;
}
int f(int a, int b){return a<b;}
int factorial(int n)
{
if(n<=1) return 1;
return factorial(n-1) *n;
}
void find_order(vector<int> &b, vector<int> sorted, int order)
{
int index;
int factorial_result;
for(int i=0; i<4; i++)
{
factorial_result = factorial(4-i-1);
index = order / factorial_result;
b[i] = sorted[index];
sorted.erase(sorted.begin() + index);
order -= index * factorial_result;
}
}
int main(int argc, char const *argv[])
{
vector<int> selected_carts(5); // seyircinin sectigi kartlar
vector<int> show(4); // gosterilen kartlar
vector<int> sorted;
vector<int> X; // ihtimaller
int hand; // elde tutulan kart
int total=0;
for(int i=0; i<5; i++){
cin>>selected_carts[i];
sorted.push_back(selected_carts[i]);
total += selected_carts[i];
}
int mode = total % 5;
sort(sorted.begin(), sorted.end(), f);
if(mode == 0)
{
hand = sorted[4];
sorted.erase(sorted.begin() + 4);
}
else
{
hand = sorted[mode-1];
sorted.erase(sorted.begin() + mode -1);
}
int k=0;
int limit=sorted[k];
int i = 1;
total -= hand;
while(i<=124)
{
if(i>=limit){
i = limit + 1;
k++;
k==4 ? limit = 125 : limit = sorted[k];
continue;
}
if((i + total)%5==(k+1)%5 ) X.push_back(i);
i++;
}
int order = get_index(X, hand, 24);
find_order(show, sorted, order);
for(int i=0; i<4; i++) cout<<show[i]<<' ';
return 0;
}
Bu kod da seçilen 5 karttan birini saklayıp 4’ünü sırayla Rena’ya gösterir.
Ama bu kodda hata var ama ben bulamadım.
Hataları çözmeye çalışacağım.
Ayriyeten her cevaba da açığım.
İyi günler dilerim.
edit: hata çözüldü
Of evet cok guzel makale. Buldugum aksam okumustum.
Nasil bir cagda yasiyoruz, problemin patladigi sayilari aratip ogretim perspektifinden anlatan makaleyi bulabiliyoruz…