[BRAINFUCK] /prog/ challenge [EXPERT]

Problem: Write the shortest brainfuck program that outputs the value of 2¹⁰⁰⁰ in decimal, followed by a newline.  The brainfuck program must not accept any input.

Judging: The entries will be judged by their correctness (the most correct first), then by their length (shortest first), and finally by their dates of submission (earliest first).  Note that a longer correct entry wins to a shorter incorrect one.

Participating: You are required to cryptographically sign your solution (e.g. by creating a throwaway GPG key with fake info and sync'ing it to a keyserver).  This is needed so you that may claim your prize (and not an impostor).  The lack of any means of authentication leads to immediate disqualification.  You may submit as many entries as you like.

Remark. I realize that not everyone here is familiar with GPG.  This should give you a head start:
$ cat submission.txt
+++[...
$ gpg --gen-key
Please select what kind of key you want:
   (1) RSA and RSA (default)
   (2) DSA and Elgamal
   (3) DSA (sign only)
   (4) RSA (sign only)
Your selection? 2
DSA keys may be between 1024 and 3072 bits long.
What keysize do you want? (2048) 2048
Requested keysize is 2048 bits
Please specify how long the key should be valid.
         0 = key does not expire
      <n>  = key expires in n days
      <n>w = key expires in n weeks
      <n>m = key expires in n months
      <n>y = key expires in n years
Key is valid for? (0) 1y
Key expires at Fri 31 Jan 2014 04:26:47 PM EST
Is this correct? (y/N) y

You need a user ID to identify your key; the software constructs the user ID
from the Real Name, Comment and Email Address in this form:
    "Heinrich Himmler (Der Henker) <heinrichh@duesseldorf.de>"

Real name: hello kitty
Email address:
Comment:
You selected this USER-ID:
    "hello kitty"

Change (N)ame, (C)omment, (E)mail or (O)kay/(Q)uit? o
You need a Passphrase to protect your secret key.

You don't want a passphrase - this is probably a *bad* idea!
I will do it anyway.  You can change your passphrase at any time,
using this program with the option "--edit-key".

(snip)

pub   2048D/0xD77B493754AB980C 2013-01-31 [expires: 2014-01-31]
      Key fingerprint = 6531 777E 6F1D BC81 2786  BE6F D77B 4937 54AB 980C
uid                 [ultimate] hello kitty
sub   2048g/0xF1AB3377C8CB418C 2013-01-31 [expires: 2014-01-31]

$ gpg --send-keys 54AB980C
gpg: sending key 0xD77B493754AB980C to hkp server pgp.mit.edu
$ gpg --clearsign -u "hello kitty" submission.txt
$ cat submission.txt.asc
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

+++[...
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iF4EAREKAAYFAlEK5hYACgkQ13tJN1SrmAyvSwEAtLoi4LXi1YQtJV0rbH3t4gNr
3MMBC2KmorxTRr+3HakA/RxqRTy0ARjbYDV9DG2/z5OOQb/a1S6QngsM7trHYZzd
=4/xg
-----END PGP SIGNATURE-----
$

Prize: The winner will be offered a document describing the art of infinite multiple quotation on Shi_tchan.  If the prize is not claimed within one week of its announcement, it will be offered to the next best submitter.

Deadline: 2013-04-01 at 00:00 UTC.


Attached: Signed version of this post.
data:application/octet-stream;_{^{base64,owGFV81vI0kVz7KwYpsPMaeV0Eo8RiOtvTNufybOmJ1dHNtxPiZOYmdmyFpeVN1ddte6u6qnujpOZ/kDOCFOSIgj4ghXrkgg7YHLnrlyWIS4wYULu6+qOk4YIhFZSafr1fv4vfd+7/nn33p9w7l39fnzXzmffeN7r/32m3/y3vRDEkWUL+ip8/mnU292IoUX0Xha9WYdeCGZoqBCCmkopKKpAk8SxueZv4REioUkMR4TBSJTSaZSI3tBooyCmENjmmbJrF6r1aZV/QSMQ0B9FpPoEcxFFIkVDcDLgQCnq4hx6gKcoYb/NRJnaJsLBcT3aYJ/eI7a0KTrOOj1QRYsGF9Yr7UGypVkNIUViyLwKHyMAtYWesgk+EJK6itO0xRK2ulYoIHiLcyZTFX5kZblN3c0TCqE0hqLazHCA3zmCGR+Ix0QlNEopJkXszRlgkOJEhmxm6sY7kgYhBFCApHAPKx9MzHkGAFHWAUeW7sS476WEIiYif+ESMV8lhC1RuFcZEAkBUlfZkxi7KjDl3miNKBJyHzjbsoWHHKRSUhFlCnrpLtwdRy+pEYfmlahFCuyIjkMT4awpNothGJOlhTdmQsDQZpz/x0tz5R1GOVSKi+oLJu8shTwwykN0JtUaLM28hj1+hFhsfUkkeyKQkmrNBnnwOIE0yMKPRQigqWB0OoqiCnhBmeS6XQhDMSEEVESGOBYHNOAYTYgYOnLjERsXsigNo2SNm+ShLZS/A+VXpcP/q+9jNjSAM1mYxoTuZxW2cyFfcQWtV0V+dO+Ugw2x6xASBF6jHZOYhYxIi1eCN41EpjMLApgwS6oMUHwCkFYFGay40zj2QNAJ28Vj6sulfPw4cOp67rOA1gkC6hUFpRXEGXnBKNNsUtppMtipd1ZMsQPYdHJ0gZWhKNiACjVyzCedE3K9N9SQOcki1TZHDbK0C8OB9GCYKua1037umTqRfAot9Itq+r263NTTMYR9PoDwOps6Ip09H1dEQZvbEmPqhXF/qrXGi1jr1lrN8BjyCK6EVznhQkDb2iIA7GO4gP0stbaLhvV+GC0j7HMsbGwsq5vIMj61GhcA5Qg/cxzCMXKGDF8pREq0uEZ9mKBq6OzPzV4YiQCgfVgcnyZYD8VAu/x96EQsO9TTXJIcyRPb0RWd4lg8MtbMvFdMrHgKrwllN8llCOrpM4hvsaQjftIrhJRqhmI6rkB6PDWNcR1VzJo1uEAu6tRq7eg1uo0tjqtNpwcwWBy5uxrLkd9BdWgtrw6MvqsOp1n08tYuRl2Oez3TbMFugXnue1kdPUHdnyIuVppNvIFT5XM/GJUFDeduRSxeTHGjoIRiekj6AlsXK5sKcaERdANAqkJG6M2vmGUsSlpuL9HGZfMD2EP2z1CpaU+/tqjfInsA++FxXH4wwCrBKszEHLuBvT9+45jTHI02dHRhRTHEjaPUjZOa5lYyx1wCq/wSQNg61yTq/bn2WQwruz3C5duaUIrvZAguUNpVDbBlXplqwgfB2VjQ6DTx+Ulyaul03LGlGkdYZy4hfUJSdMklLqYEW4cj0p3vGVwioxtOsa16QkEf0eZlsGLyc3FinUXP3jfI16kJ/C7Hgne1fkj33f27dzEnmNm1CLxF1zpY734NhTL1TdaiZ3KimF8TpYy013WhhnhhgF1jkViCPp+pYK8rDR/3UeHSylnSdlxksxD9HTn9qu1y367vdN63GxPs9lmq7vzeLvWm1azma7ZZqVWr2AJT4uq7phCti9nRcvoosfJjFMVhwrC8AS2NvFKu90ewNZuvQ87ve06NNrbWwA7g61d0PZAG4TCIlybdDLsq1d/psibuM4oOoNb6XbSdQwLjGG33t1pNtvt3nZvp1Xf7v1/59f8nlIeVAxpvgKAg+cd0McaZ00JN1hdy+kCCZcJ2BkMySJxcca5NMjW+v1Ic4cm70r23xX76uS5axy5JPXBqeifncFwfwQnwxOY7A9Hgz4cDSaT7nBgDp09koYdmOx1N+sNZz3E7rjYPXs2Lu48p1Lb6cCQZ7hzXNTdlltvQGk4elZ9ynh2ibXCdluD7nhw2O2e73ajweFmeN7tLZan9aY6GNUnMu7mF5PVoKueCtZ6+iNWPz9VB89r0ttrqtZiJJ3m0dFOr3EYC3l5NpYPm3tk2a2OL1+Oz/Jad/yxd95//rg/bFSvNo+PT70qqU+2TvkiPWoruXf+4VXgPGlVLxc2ksGof1ccD6bVeGaXNL3X3KyouNhxKtcbqpjPqTQtHgg/M8wX0NSXzGPFnMLNQA903LcY13t5rIsviSi8zISySw9+JiHDtdubTdNEMGTCmcLlu3jUa7g30/2L7bw/N1rttsXsbDNbGDqhe5VpddSMKWMWKZtwLjLuU0tcyA2vOo8Vp3VyeonfFPSea/cq3FrtntrHHUfv+RYF2we66jV51GqdWg2enfVQ1OkqRfyQBlg1WJ2o+cKWg/bEsgouhK6jy+inH311456z8cbXvqK/wmw4b37n+hvOt3+y8UV4dXUw+Ifz7+4nw+mL3//i6+7P3v7dp3994w8//ovf+uw30VsbX3zy57//7bth1lz+896v/zP447R877T8r+FxfPLa4ji8+OX+lw==}}

> a
b
c
gay

a
> > b
> > > c
>>> gay

a
> b
> c

What
the
hell
is
going
on
around
here?

>LELLLLLLLLLL
L >> L> LLEEEEEEEEEEEEEELLLLLLLLLLLLLL
<> >> >>KKLELELLLLLLLLLLL L
>>>>   >>>LLELLEEEEEEEEEEEELLLLLLLLLLLLLLLLLLLLLLLL
[i][i]LLLLLLLLEEEEEEEWEWLLLLLLLLLLLLLLLLLLLL[/i][m]=
:>> >>>>>>           LEEEEEEEEE :LLLLLLLLLLLL
LE NBABBYCODE LLLEEEEEEEEEELLLLLLL XDDDDDDDD

fuck
this
> shit

[quote]dicks[/quote]

white power dubz checkem

o/ o/ o/ o/ o/

2^1000 is only 125 bytes, but in brainfuck you'd need to print byte by byte, so 301 bytes

you could calculate it with 125 bytes, then use another 301 bytes to print it

if only in brainfuck there was some var acessible at all times, no matter where in the tape you are...

in brainfuck you'd need to print byte by byte

my head hurts at this stupid

my stupid hurts at this head

Missed the deadline. I don't even give a fuck.

[-]>[-]<>++++++++[<++++++++>-]<+.>+++++++[<+++++++>-]<--.++.>+++[<--->-]<.+++.>+++++++++[<--------->-]<+++++.>++++++[<++++++>-]<++.>++++++[<++++++>-]<+++++..---.>+++[<+++>-]<--.

>>93
You got me. You got me good.

>>2-92
Nobody wins, fuck you. I am extending this indefinitely (or at least until I leave this board); anyone who solves the challenge in non-trivial way will receive the prize (given that they authenticated properly).

>>94
Please do not refer to your harebrained authentication scheme as `proper'.

>>95
fuck you dipshit

>>96
wow stop posting you shithead. >>7 won.

>>97
fuck you I won't do what you tell me

>>96

OK YOU FUQIN MADE AN EXPERT PROGRAMMER feel kind of bad. I don't like church numerals though. I don't know how to subtract them. So instead I will implement numbers as stacks of dinner plates.

It's a start. This should be translatable to unlambda, but right now it is too slow.


(define (i x) x)

(define (zero is-zero receive-predecessor)
  (is-zero))

(define (do-nothing) zero)

(define (successor n)
  (lambda (is-zero receive-predecessor)
    (receive-predecessor n)))

(define one (successor zero))

(define (add n1 n2)
  (n2 (lambda () n1)
      (lambda (n2-pred)
        (add (successor n1)
             n2-pred))))

(define (signed-sub n1 n2 pos neg)
  (n2 (lambda () (pos n1))
      (lambda (n2-pred)
        (n1 (lambda () (neg n2))
            (lambda (n1-pred)
              (signed-sub n1-pred n2-pred pos neg))))))

(define (sub n1 n2)
  (signed-sub n1 n2 i (lambda (n) (error "Cannot subtract and get a negative"))))

;; to be optimized
(define (add-times n1 n2 sum)
  (n2 (lambda () sum)
      (lambda (n2-pred)
        (add-times n1 n2-pred (add n1 sum)))))

(define (mul n1 n2)
  (add-times n1 n2 zero))

;; to be optimized
(define (mul-times n1 n2 product)
  (n2 (lambda () product)
      (lambda (n2-pred)
        (mul-times n1 n2-pred (mul n1 product)))))

(define (pow n1 n2)
  (mul-times n1 n2 one))

(define (div_ n d q ret)
  (signed-sub n d (lambda (n2)
                    (div_ n2 d (successor q) ret))
                  (lambda (n2)
                    (ret q n))))

(define (div n d ret)
  (div_ n d zero ret))

(define (quot n d)
  (div n d (lambda (q r) q)))

(define (mod n d)
  (div n d (lambda (q r) r)))

(define (to-num n)
  (n (lambda () 0)
     (lambda (n1-pred)
       (+ 1 (to-num n1-pred)))))

(define two (add one one))
(define four (pow two two))
(define eight (mul two four))
(define ten (add eight two))
(define five (quot ten two))
(define three (mod eight five))
(define nine (pow three two))
(define seven (add five two))
(define six (sub ten four))


(define (print-digit n done)
  (n (lambda () (display #\0) (done))
     (lambda (n-1)
       (n-1 (lambda () (display #\1) (done))
            (lambda (n-2)
              (n-2 (lambda () (display #\2) (done))
                   (lambda (n-3)
                     (n-3 (lambda () (display #\3) (done))
                          (lambda (n-4)
                            (n-4 (lambda () (display #\4) (done))
                                 (lambda (n-5)
                                   (n-5 (lambda () (display #\5) (done))
                                        (lambda (n-6)
                                          (n-6 (lambda () (display #\6) (done))
                                               (lambda (n-7)
                                                 (n-7 (lambda () (display #\7) (done))
                                                      (lambda (n-8)
                                                        (n-8 (lambda () (display #\8) (done))
                                                             (lambda (n-9)
                                                                (n-9 (lambda () (display #\9) (done))
                                                                     (lambda (n-10)
                                                                       (error "digit value is greater than nine"))))))))))))))))))))))

(define (cons_ car cdr)
  (lambda (is-null f)
    (f car cdr)))

(define (null is-null f) (is-null))

(define (for-each_ f lis)
  (lis (lambda () null)
       (lambda (car cdr)
          (f car (lambda ()
                   (for-each_ f cdr))))))

(define (digits-list_ n base acc)
  (div n base (lambda (q r)
                (q (lambda () (cons_ r acc))
                   (lambda (q-pred)
                     (digits-list_ q base (cons_ r acc)))))))

(define (digits-list n base)
  (digits-list_ n base null))

(define (print-num n)
  (for-each_ print-digit (digits-list n ten)))

(print-num (pow two nine)) (newline) ;; proof of concept for small number


;; too slow to run
;(define one-thousand (pow ten three))
;(define two-to-the-one-thousand (pow two one-thousand))
;(print-num two-to-the-one-thousand) (newline)

this one is asymptotically acceptable. Still slower than hardware arithmetic, but what can you do. I will be slowly translating it to ski now.





;; booleans

(define (true true-case false-case)
  (true-case))

(define (false true-case false-case)
  (false-case))

(define (not_ v)
  (v (lambda () false)
     (lambda () true)))

(define (or_ v1 v2)
  (v1 (lambda () true)
      (lambda ()
        (v2 (lambda () true)
            (lambda () false)))))

(define (and_ v1 v2)
  (v1 (lambda ()
        (v2 (lambda () true)
            (lambda () false)))
      (lambda () false)))

(define (xor_ v1 v2)
  (v1 (lambda () (not_ v2))
      (lambda () v2)))

(define (addition-circuit v1 v2 carry-in ret)
  (ret (xor_ (xor_ v1 v2) carry-in)
       (or_ (and_ v1 v2)
            (or_ (and_ v1 carry-in)
                 (and_ v2 carry-in)))))

(define (subtraction-circuit v1 v2 borrow-in ret)
  (ret (xor_ (xor_ v1 v2) borrow-in)
       (or_ (and_ (and_ v1 v2) borrow-in)
            (and_ (not_ v1) (or_ v2 borrow-in)))))



;; lists

(define (null is-null f)
  (is-null))

(define (cons_ car cdr)
  (lambda (is-null f)
    (f car cdr)))

(define (reverse__ lis acc)
  (lis (lambda () acc)
       (lambda (car cdr)
         (reverse__ cdr (cons_ car acc)))))

(define (reverse_ lis)
  (reverse__ lis null))

(define (for-each_ f lis)
  (lis (lambda () null)
       (lambda (car cdr)
         (f car (lambda ()
                  (for-each_ f cdr))))))



;; numbers

(define zero null)
(define one (cons_ true null))

(define (add_ n1 n2 carry-in)
  (n1 (lambda ()
        (n2 (lambda ()
              (carry-in (lambda () one)
                        (lambda () zero)))
            (lambda (n2-car n2-cdr)
              (carry-in (lambda () (add_ n2 one false))
                        (lambda () n2)))))
      (lambda (n1-car n1-cdr)
        (n2 (lambda ()
              (carry-in (lambda () (add_ n1 one false))
                        (lambda () n1)))
            (lambda (n2-car n2-cdr)
              (addition-circuit n1-car
                                n2-car
                                carry-in
                                (lambda (out carry-out)
                                  (cons_ out
                                         (add_ n1-cdr n2-cdr carry-out)))))))))

(define (add n1 n2)
  (add_ n1 n2 false))

(define (sub_ n1 n2 borrow-in negative ret)
  (n1 (lambda ()
        (n2 (lambda ()
              (borrow-in (lambda () (negative))
                         (lambda () (ret zero))))
            (lambda (n2-car n2-cdr)
              (negative))))
      (lambda (n1-car n1-cdr)
        (n2 (lambda ()
              (borrow-in (lambda () (sub_ n1 one false negative ret))
                         (lambda () (ret n1))))
            (lambda (n2-car n2-cdr)
              (subtraction-circuit n1-car
                                   n2-car
                                   borrow-in
                                   (lambda (out borrow-out)
                                     (sub_ n1-cdr
                                           n2-cdr
                                           borrow-out
                                           negative
                                           (lambda (rest-sub)
                                             (out (lambda () (ret (cons_ out rest-sub)))
                                                  (lambda ()
                                                    (rest-sub (lambda () (ret null)) ;; truncate significant zeros.
                                                              (lambda (rest-sub-car rest-sub-cdr)
                                                                (ret (cons_ out rest-sub)))))))))))))))

(define (sub n1 n2 negative ret)
  (sub_ n1 n2 false negative ret))

(define (sub-pos n1 n2)
   (sub n1 n2 (lambda () (error "Cannot subtract and get a negative")) (lambda (x) x)))

(define (even?_ n)
  (n (lambda () true)
     (lambda (n-car n-cdr)
       (n-car (lambda () false)
              (lambda () true)))))

(define (double n)
  (n (lambda () null)
     (lambda (n-car n-cdr)
       (cons_ false n))))

(define (double-and-inc n)
  (cons_ true n))

(define (floor-div-2 n)
  (n (lambda () zero)
     (lambda (n-car n-cdr) n-cdr)))

(define (mul n1 n2)
  (n2 (lambda () zero)
      (lambda (n2-car n2-cdr)
        (n2-cdr (lambda () n1)
                (lambda (n2-cadr n2-cddr)
                  (n2-car (lambda () (add n1 (double (mul n1 n2-cdr))))
                          (lambda () (double (mul n1 n2-cdr)))))))))

(define (square n)
  (mul n n))

(define (pow b p)
  (p (lambda () one)
     (lambda (p-car p-cdr)
       (p-cdr (lambda () b)
              (lambda (p-cadr p-cddr)
                (p-car (lambda () (mul b (square (pow b p-cdr))))
                       (lambda () (square (pow b p-cdr)))))))))

(define (div n d ret)
  (n (lambda () (ret zero zero))
     (lambda (n-car n-cdr)
       (n-car (lambda () ;; n odd
                (div n-cdr d (lambda (q_ r_)
                               (sub (double-and-inc r_) d (lambda () (ret (double q_) (double-and-inc r_)))
                                                          (lambda (double-inc-r_-d)
                                                            (ret (double-and-inc q_) double-inc-r_-d))))))
              (lambda () ;; n even
                (div n-cdr d (lambda (q_ r_)
                               (sub (double r_) d (lambda () (ret (double q_) (double r_)))
                                                  (lambda (double-r_-d)
                                                    (ret (double-and-inc q_) double-r_-d))))))))))

(define (quot n d)
  (div n d (lambda (q r) q)))

(define (mod_ n d)
  (div n d (lambda (q r) r)))



(define (print-hex-word n done)
  (n (lambda () (display #\0) (done))
     (lambda (n-car n-cdr)
       (n-cdr (lambda () (display #\1) (done))
              (lambda (n-cadr n-cddr)
                (n-cddr (lambda ()
                          (n-car (lambda () (display #\3) (done))
                                 (lambda () (display #\2) (done))))
                        (lambda (n-caddr n-cdddr)
                          (n-cdddr (lambda ()
                                     (n-cadr (lambda ()
                                               (n-car (lambda () (display #\7) (done))
                                                      (lambda () (display #\6) (done))))
                                             (lambda ()
                                               (n-car (lambda () (display #\5) (done))
                                                      (lambda () (display #\4) (done))))))
                                   (lambda (n-cadddr n-cddddr)
                                     (n-cddddr (lambda ()
                                                 (n-caddr (lambda ()
                                                            (n-cadr (lambda ()
                                                                      (n-car (lambda () (display #\F) (done))
                                                                             (lambda () (display #\E) (done))))
                                                                    (lambda ()
                                                                      (n-car (lambda () (display #\D) (done))
                                                                             (lambda () (display #\C) (done))))))
                                                          (lambda ()
                                                            (n-cadr (lambda ()
                                                                      (n-car (lambda () (display #\B) (done))
                                                                             (lambda () (display #\A) (done))))
                                                                    (lambda ()
                                                                      (n-car (lambda () (display #\9) (done))
                                                                             (lambda () (display #\8) (done))))))))
                                               (lambda (n-caddddr n-cdddddr)
                                                 (error "Number too large to print as a hex digit"))))))))))))

(define (base-digits n base)
  (n (lambda () null)
     (lambda (n-car n-cdr)
       (div n base (lambda (n-quot n-mod)
                     (cons_ n-mod (base-digits n-quot base)))))))

(define (print-base n base)
  (n (lambda () (print-hex-word zero (lambda () null)))
     (lambda (n-car n-cdr)
       (for-each_ print-hex-word (reverse_ (base-digits n base))))))


(define two (add one one))
(define three (add two one))
(define four (pow two two))
(define eight (pow two three))
(define nine (mul three three))
(define ten (add nine one))
(define five (quot ten two))
(define six (sub-pos eight two))
(define seven (sub-pos ten three))

(define (print_ n)
  (print-base n ten))



;; main

(print_ (pow two (pow ten three)))

dude what that's not brainfuck.

If you think of it as a logarithmic catch up rate with a critical point (the flash) signifying the point where their time line comes into phase and is assimilated into the true present then it makes sense.