var QUESTION_ID=83873,OVERRIDE_USER=48934;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+(?:\.\d+)?)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
Jawaban:
Kalkulus biner biner , 114 bit = 14,25 byte
Hexdump:
Biner:
Penjelasan
Ini adalah (λ x . (Λ y . X y (λ m . M (λ g . Λ n . N g 1) (λ n . Λ f . X ( n f )) x ) y ) (λ f . Λ z . f ( x f z ))) 3, di mana semua angka direpresentasikan sebagai angka Gereja. Angka gereja adalah standar representasi lambda kalkulus bilangan, dan mereka sangat cocok untuk masalah ini karena sejumlah gereja ditentukan oleh fungsi iterasi: n g adalah n th iterate dari fungsi g .
Misalnya, jika g adalah fungsi λ n . λ f . 3 ( n f ) yang dikalikan 3 dengan angka Gereja, lalu λ n . n g 1 adalah fungsi yang mengambil 3 pangkat dari angka Gereja. Iterasi operasi ini m kali memberi
m (λ g . λ n . n g 1) (λ n . λ f . 3 ( n f )) n = u (3, n , m ).
(Kami menggunakan multiplikasi u (-, -, 0) daripada exponentiation u (-, -, 1) sebagai alas kasus, karena mengurangi 1 dari angka Gereja tidak menyenangkan .)
Pengganti n = 3:
m (λ g . λ n . n g 1) (λ n . λ f . 3 ( n f )) 3 = u (3, 3, m ).
Iterasi operasi itu 64 kali, mulai dari m = 4, beri
64 (λ m . M (λ g . Λ n . N g 1) (λ n . Λ f . 3 ( n f )) 3) 4 = G .
Untuk mengoptimalkan ungkapan ini, gantikan 64 = 4 ^ 3 = 3 4:
3 4 (λ m . M (λ g . Λ n . N g 1) (λ n . Λ f . 3 ( n f )) 3) 4 = G .
Ingat 4 = succ 3 = λ f . λ z . f (3 f z ) sebagai argumen lambda:
(λ y . 3 y (λ m . m (λ g . λ n . n g 1) (λ n . λ f . 3 ( n f )) 3) y ) (λ f . λ z . f (3 f z )) = G .
Akhirnya, ingat 3 = λ f . λ z . f ( f ( f z )) sebagai argumen lambda:
(λ x . (λ y . x y (λ m . m (λ g . λ n . n g 1) (λ n . λ f . x ( n f )) x ) y ) (λ f . λ z . f ( x f z ))) 3 = G .
sumber
14.25 bytes
tampaknya mengacaukan leaderboard. Itu diurai sebagai25 bytes
, dan karena itu Anda ditempatkan sebagai yang kedua.Haskell, 41 byte
Penjelasan:
(`i`1)f n
=i f 1 n
menghitungn
iterate dari fungsif
mulai dari1
. Secara khusus,(`i`1)(*3)n
= 3 ^ n , dan iterasi konstruksi ini m kali memberikani(`i`1)(*3)m n
= u (3, n , m ). Kita dapat menulis ulang itu sebagai(($n).i(`i`1)(*3))m
= u (3, n , m ), dan iterasi konstruksi k kali ini untuk mendapatkani(($3).i(`i`1)(*3))4 k
= g _ k .sumber
Haskell, 43 byte
Ada cara yang lebih baik untuk flip
g
inline.46 byte:
48 byte:
Cukup menuliskan definisi.
Kasing dasar agak bersih didukung hingga 0, meskipun tidak menyimpan byte. Mungkin akan lebih mudah untuk menulis definisi alternatif.
sumber
+
untuk menghapus tanda kurung antaram-1
?(`g`3)
, bukan(3`g`)
.Pyth, 25 byte
Bagian pertama
M?H.UgbtH*G]3^3G
mendefinisikan metodeg(G,H) = u(3,G,H+1)
.Untuk menguji bagian pertama, periksa
7625597484987=u(3,3,2)=g(3,1)
:g3 1
.Bagian kedua
ug3tG64 4
dimulai darir0 = 4
dan kemudian menghitungrn = u(3,3,r(n-1)) = g(3,r(n-1))
64 kali, menghasilkan nilai akhir (r
dipilih alih-alihg
untuk menghindari kebingungan).Untuk menguji bagian ini, mulai dari
r0=2
dan kemudian menghitungr1
:ug3tG1 2
.sumber
^3
↦*3
,tG
↦G
), dan byte lain dengan.UgbtH*G]3
↦e.ugNtHG1
.*G]3
↦ShG
.Sesos , 30 byte
Dibongkar
Atau dalam notasi Brainfuck:
Pengujian
Untuk menghitung u (3, n , u (3, n , ... u (3, n , m ) ...)) dengan k panggilan bersarang ke u , mengganti tiga pertama
add
petunjukadd 4
,add 64
,add 3
denganadd m
,add k
,add n
, masing-masing. Karena Sesos tidak dapat membuat angka lebih cepat daripada dalam waktu linier, Anda praktis terbatas pada nilai kecil seperti u (3, 2, 2) = 27, u (3, 5, 1) = 243, dan u (3, 1 , u (3, 1, ... u (3, 1, m ) ...)) = 3.sumber
[-]
dengan,
karena EOF0
.JavaScript (ES7), 63 byte
sumber
Brachylog , 57 byte
Tidak mengharapkan Input atau Output dan menulis hasilnya ke
STDOUT
. Ini akan menghasilkan stack overflow pada satu titik.Untuk memeriksa apakah ini berfungsi untuk nilai kecil (mis.
u(3,3,2)
) Anda dapat mengganti4
dengan nilai darim
dan64
dengan1
.Penjelasan
Ini pada dasarnya adalah implementasi langsung dari cara yang dijelaskan dalam menghitung angka.
Predikat utama:
Predikat 1:
Predikat 2:
sumber
Karamel , 38 byte
Ini adalah gula sintaksis untuk ekspresi kalkulus lambda 64 (λ m . M (λ f . Λ n . N f 1) (λ n . Λ f . 3 ( n f )) 3) 4, di mana semua angka diwakili sebagai Gereja angka .
sumber
(n f->3 (n f))
tidakkah seharusnya dibacan-1
?(n f->3 (n f))
adalah fungsi untuk perkalian tiga oleh angka Gereja .Prolog (SWIPL), 129/137 byte
Untuk menampilkan nomor Graham, kueri untuk
g(64,G).
(jika 8 byte dari kueri ini dihitung, panjangnya 137 byte):Tapi seperti yang bisa diharapkan, ini kehabisan tumpukan.
Uji
Mundur menyebabkannya kehabisan tumpukan:
Tidak disatukan
Versi ungolfed menambahkan notasi panah atas umum, bukan hanya untuk 3, dan menggunakan pemotongan dan cek untuk menghindari situasi mundur dan tidak terdefinisi.
sumber
64
di kode Anda?C, 161 byte
EDIT: menyimpan 11 byte dengan menghapus tab dan baris baru. EDIT: thx auhmann menyimpan byte lain dan memperbaiki program saya
sumber
g(int a){if(a==1)return u(3,4);return g(a-1);}
karena tidak digunakan sama sekali ... Atau apakah Anda lupa sesuatu?return g(a-1)
seharusnyareturn u(3,g(a-1))
.u(a,b){return a<2?3:b<2?pow(3,a):u(u(a-1,b),b-1);}g(a){return a<2?u(3,4):u(3,g(a-1));}main(){printf("%d",g(64));}
Mathematica, 59 byte
Menggunakan operator infiks yang tidak ditentukan
±
yang hanya membutuhkan 1 byte saat disandikan dalam ISO 8859-1. Lihat @ Martin posting untuk info lebih lanjut. Fungsi Mathematica mendukung pencocokan pola untuk argumen mereka, sehingga dua kasus dasar dapat didefinisikan secara terpisah.sumber
n_ ±m_:=Nest[#±(m-1)&,3,n]
C,
114109 byteBerdasarkan jawaban oleh @thepiercingarrow ( tautan ) saya menurunkan sedikit jawabannya. Sebagian besar penghematan disebabkan oleh penyalahgunaan argumen pengetikan default saat melakukan fungsi gaya K&R dan penggantian pernyataan if dengan operator ternary. Menambahkan baris baru opsional antara fungsi untuk keterbacaan.
Ditingkatkan menjadi 109 berkat @LeakyNun.
sumber
g(a){return u(3,a<2?4:g(a-1));}
Python, 85 byte
The
v
Fungsi mendefinisikan fungsi yang sama seperti yang ditemukan di jawaban Dennis :v(n,m) = u(3,n+1,m+1)
. Theg
Fungsi adalah versi nol-diindeks dari iterasi tradisional:g(0) = v(2,3), g(n) = v(2,g(n-1))
. Jadi,g(63)
ini nomor Graham. Dengan mengatur nilai default darin
parameterg
fungsi ke63
, output yang diperlukan dapat diperoleh dengan memanggilg()
(tanpa parameter), sehingga memenuhi persyaratan kami untuk pengiriman fungsi yang tidak memerlukan input.Verifikasi
v(2,1) = u(3,3,2)
danv(4,0) = u(3,5,1)
uji kasus online: Python 2 , Python 3sumber
g
tampaknya tidak aktif. Bukankahv(2,n-1)
seharusnyag(n-1)
seperti itu?u
danv
artinya seharusnyag(n-1)-1
.Dyalog APL, 41 byte
Kasus cobaan:
sumber
1=⍺:3⋄1=⍵:3*⍺
menjadi just1=⍵:3*⍺
(3=3*1
)Ruby, 64 byte
Meminjam dari algoritma Teoritis untuk menghitung nomor Graham .
Sederhananya,
f a = u(3,3,a)
dan ini berlaku 64 kali.sumber
J, 107 byte
Saya sedang berusaha mengubah
u
menjadi agenda, tetapi untuk sekarang itu akan berhasil.sumber
u=:3^[`[:(3$:])/[#<:@]@.*@]
(tidak diuji)F #,
111108 byteSunting
Ini menggunakan fungsi di bawah untuk menghitung nomor Graham
Inilah jawaban saya sebelumnya yang, yah, tidak:
Cukup mudah. Hanya definisi
u
fungsi saja.Pemakaian:
Jika saya menganggap 3 sebagai nilai untuk, saya bisa memotongnya menjadi 60:
Pemakaian:
sumber
u
. Tentu saja Anda dapat menyertakan fungsi perantara yang Anda butuhkan, sepertiu
dengan atau tanpa argumen pertamanya ditetapkan pada 3.R,
154142128126118 byteSaya menggunakan definisi Wikipedia dari fungsi rekursif ini karena untuk beberapa alasan aneh yang disarankan tidak bekerja ... atau saya hanya mengisap R golf.
UPD: mencukur 12 + 14 = 26 byte berkat tip dari Leaky Nun . Versi sebelumnya menggunakan yang besar dan kurang efisien
UPD: dicukur 2 + 6 + 2 byte lebih (lagi, pujian untuk Leaky Nun ) karena penggantian yang cerdik dengan "jika (x)" bukan "jika (x == 0)" karena x <0 tidak pernah dimasukkan ke dalam fungsinya ... kan?
sumber
u
dengan kunci yang sama seperti Andag
dan menyimpan 6 byte lagi — luar biasa!PHP, 114 byte
abaikan jeda baris; hanya untuk keterbacaan.
Dimungkinkan untuk mengintegrasikan kasus kedua ke yang pertama: untuk
n=1
,3^n
sama dengan3
.Ini akan menghemat beberapa byte pada - sejauh yang saya bisa lihat - semua jawaban yang ada; menyimpan dua byte di my
versi sebelumnya, 62 + 43 + 11 = 116 byte
Asosiasi asosiatif kiri dari ternary membutuhkan tanda kurung ... atau urutan tes tertentu.
Ini menyimpan dua byte pada ekspresi yang di dalam tanda kurung.
Mungkin ada pendekatan iteratif, yang dapat memungkinkan golf lanjut ...
tapi saya tidak dapat meluangkan waktu untuk itu sekarang.
sumber