|  | Can this program be shortened? Measuring program-length? | | |
| | | r.e.s. |  |
|  Posted: Thu Jul 10, 2008 5:57 pm Post subject: Can this program be shortened? Measuring program-length? |  |
Can the following program be shortened? ...
def h(n,m):
E=n,
while (E!=())*m>0:n=h(n+1,m-1);E=E[:-1]+(E[-1]>0)*(E[-1]-1,)*n
return n
h(9,9)
Note: Although it halts eventually in principle, this program can't be
expected to terminate on any machine in the universe, as it computes a
number larger than Graham's number -- assuming Python is extended (if
necessary?) to access unbounded storage.
Besides using one-letter names and no unneeded whitespace, can something
more be done to shorten it? ("Obfuscating" the code would be okay.)
Also, I'm not really sure how best to measure a program's length, but
this one is now 98 bytes long (or 102 bytes, depending on how newlines
are handled). Is there a better measure of program-length?
Thanks for any feedback. |
| |
| | | Guest | |
| | Posted: Thu Jul 10, 2008 9:59 pm Post subject: Re: Can this program be shortened? Measuring program-length? | |
On 10 Jul., 21:57, "r.e.s." <r_e_s...@ZZZyahoo.com> wrote:
| Quote: | Can the following program be shortened? ...
def h(n,m):
E=n,
while (E!=())*m>0:n=h(n+1,m-1);E=E[:-1]+(E[-1]>0)*(E[-1]-1,)*n
return n
h(9,9)
|
Some ideas...
# h is your version
def h(n,m):
E=n,
while (E!=())*m>0:n=h(n+1,m-1);E=E[:-1]+(E[-1]>0)*(E[-1]-1,)*n
return n
def g(n,m):
E=n,
while E*m:n=h(n+1,m-1);E=E[:-1]+(E[-1]>0)*(E[-1]-1,)*n
return n
def f(n,m):
E=n,
while E*m:n=h(n+1,m-1);E=(E[0]>0)*(E[0]-1,)*n+E[1:]
return n
def e(n,m):
E=[n]
while E*m:n=h(n+1,m-1);E[:1]=(E[0]>0)*[E[0]-1]*n
return n
# some tests
print h(1,1), h(2,1), h(0,2)
print g(1,1), g(2,1), g(0,2)
print f(1,1), f(2,1), f(0,2)
print e(1,1), e(2,1), e(0,2) |
| |
| | | r.e.s. | |
| | Posted: Thu Jul 10, 2008 10:46 pm Post subject: Re: Can this program be shortened? Measuring program-length? | |
<wolfram.hinderer@googlemail.com> wrote ...
| Quote: | "r.e.s." <r_e_s...@ZZZyahoo.com> wrote:
Can the following program be shortened? ...
def h(n,m):
E=n,
while (E!=())*m>0:n=h(n+1,m-1);E=E[:-1]+(E[-1]>0)*(E[-1]-1,)*n
return n
h(9,9)
Some ideas...
# h is your version
def h(n,m):
E=n,
while (E!=())*m>0:n=h(n+1,m-1);E=E[:-1]+(E[-1]>0)*(E[-1]-1,)*n
return n
def g(n,m):
E=n,
while E*m:n=h(n+1,m-1);E=E[:-1]+(E[-1]>0)*(E[-1]-1,)*n
return n
def f(n,m):
E=n,
while E*m:n=h(n+1,m-1);E=(E[0]>0)*(E[0]-1,)*n+E[1:]
return n
def e(n,m):
E=[n]
while E*m:n=h(n+1,m-1);E[:1]=(E[0]>0)*[E[0]-1]*n
return n
# some tests
print h(1,1), h(2,1), h(0,2)
print g(1,1), g(2,1), g(0,2)
print f(1,1), f(2,1), f(0,2)
print e(1,1), e(2,1), e(0,2)
|
Very instructive! Thank you for the "step-by-step". |
| |
| | | r.e.s. | |
| | Posted: Thu Jul 10, 2008 11:03 pm Post subject: Re: Can this program be shortened? Measuring program-length? | |
"r.e.s." <r_e_s_01@ZZZyahoo.com> wrote ...
| Quote: | wolfram.hinderer@googlemail.com> wrote ...
"r.e.s." <r_e_s...@ZZZyahoo.com> wrote:
Can the following program be shortened? ...
def h(n,m):
E=n,
while (E!=())*m>0:n=h(n+1,m-1);E=E[:-1]+(E[-1]>0)*(E[-1]-1,)*n
return n
h(9,9)
Some ideas...
# h is your version
def h(n,m):
E=n,
while (E!=())*m>0:n=h(n+1,m-1);E=E[:-1]+(E[-1]>0)*(E[-1]-1,)*n
return n
def g(n,m):
E=n,
while E*m:n=h(n+1,m-1);E=E[:-1]+(E[-1]>0)*(E[-1]-1,)*n
^ |
g
| Quote: | return n
def f(n,m):
E=n,
while E*m:n=h(n+1,m-1);E=(E[0]>0)*(E[0]-1,)*n+E[1:]
^ |
f
| Quote: | return n
def e(n,m):
E=[n]
while E*m:n=h(n+1,m-1);E[:1]=(E[0]>0)*[E[0]-1]*n
^ |
e
| Quote: | return n
# some tests
print h(1,1), h(2,1), h(0,2)
print g(1,1), g(2,1), g(0,2)
print f(1,1), f(2,1), f(0,2)
print e(1,1), e(2,1), e(0,2)
Very instructive! Thank you for the "step-by-step".
|
I forgot to mention the obvious typos. Thanks again. |
| |
|
|
