10
\$\begingroup\$

You are given a nonary (base 9) non-negative integer consisting of the digits 0 through 8 as usual. However the number of digits in this number (with no leading zeros) is a prefect square.

Because of this, the number can be arranged in a square grid (with the reading order still preserved).

Example with 1480 (1125 base 10):

14
80

Now let every digit in such a nonary grid indicate a motion to another grid space (with periodic boundary conditions):

432
501
678

This is saying that

0 = stay still
1 = move right
2 = move right and up
3 = move up
...
8 = move right and down

So, if in the 1480 grid you start at the 4, you then move up (remember pbc) and left to the 8, which means you move right and down back to the 4, starting a cycle with period 2.

In general this process is continued until you get to a 0 or a cycle is noticed. (A 0 is considered a cycle with period 1.)

In the case of 1480, the period eventually reached at each of the 4 starting digits is 2 2 2 1 respectively.

For a larger grid these numbers might be larger than 8, but we can still use them as "digits" in a new nonary number (simply the coefficients of 9^n as if they were digits):

2*9^3 + 2*9^2 + 2*9 + 1 = 1639 (base 10) = 2221 (base 9)

We will call this the strength of the original nonary number. So the strength of 1480 is 1639 (base 10) or, equivalently, 2221 (base 9).

Challenge

Write the shortest program that tells whether the strength of a nonary number is greater than, less than, or equal to the nonary number itself. (You do not necessarily need to compute the strength.)

The input will be a non-negative nonary number that contains a square number of digits (and no leading zeros besides the special case of 0 itself). It should come from the command line or stdin.

The output should go to stdout as:

G if the strength is larger than the original number (example: 1480 -> strength = 2221)
E if the strength is equal to the original number (example: 1 -> strength = 1)
L if the strength is less than the original number (example: 5 -> strength = 1)

Fun Bonus Challenge:
Whats the highest input you can find that is equal to its strength? (Is there a limit?)

\$\endgroup\$
  • \$\begingroup\$ As for the input, is it given as a decimal number the digits of which are the same as the nonary number or as the decimal (or binary) representation of the nonary number? i.e: for 1480(non) will the input be 1480 or 1125? \$\endgroup\$ – overactor Aug 26 '14 at 10:31
  • \$\begingroup\$ @overactor In nonary format. \$\endgroup\$ – user31074 Aug 26 '14 at 10:37
  • 2
    \$\begingroup\$ I'm fairly confident that no-one will find a higher input that equals its strength than 10^71-1(non) that is, a 64 digit number that consists only of 8's \$\endgroup\$ – overactor Aug 26 '14 at 10:53
  • \$\begingroup\$ @overactor It might be possible with cycles of period greater than 8, I think. \$\endgroup\$ – Martin Ender Aug 26 '14 at 17:22
  • \$\begingroup\$ @MartinBüttner i will be thoroughly impressed if you find any of those. \$\endgroup\$ – overactor Aug 26 '14 at 17:51
2
\$\begingroup\$

Python 2, 213 209 202

Edit: Removed shortcircuiting, which is sometimes incorrect. See below.

(Largely) The same algorithm as @KSab, but very heavily golfed.

n=`input()`
s=int(len(n)**.5)
c=0
for i in range(s*s):
 a=[]
 while(i in a)<1:a+=[i];x='432501678'.find(n[i]);i=(i+x%3-1)%s+((i/s+x/3-1)%s)*s
 c=c*9+len(a)-a.index(i)
d=long(n,9)
print'EGL'[(c>d)-(c<d)]

Golfs:

  • 213: Short-circuiting, flawed solution.

  • 209: First working solution.

  • 202: Combined the two string lookups into one.

Edit: I just realised that this program, and thus KSab's too, were flawed in that they ignore multidigit cycle lengths. Example failure:

3117
2755
3117
7455

While the 3 has a cycle length of 2, and thus the above algorithm short circuits to 'L', this should in fact return 'G', because the cycle length of 14 on the second digit more than overcomes that. I have therefore changed the program. It also got shorter, funnily enough. To test your program, use 3117275531177455. It should return G.

\$\endgroup\$
  • \$\begingroup\$ Wow I thought I golfed it down a fair bit but you did some pretty clever stuff there. \$\endgroup\$ – KSab Aug 27 '14 at 3:27
  • \$\begingroup\$ @KSab Thanks - your algorithm was very clever to start with - I couldn't find any better way to do it. \$\endgroup\$ – isaacg Aug 27 '14 at 5:19
2
\$\begingroup\$

Python 296

Not actually too inefficient, it only checks as many digits as it needs to.

n=raw_input();s=int(len(n)**.5);t=0
for i in range(s**2):
    l=[]
    while i not in l:l.append(i);c=n[i];i=(i%s+(-1 if c in'456'else 1 if c in'218'else 0))%s+((i/s+(-1 if c in'432'else 1 if c in'678'else 0))%s)*s
    t=t*9+len(l)-l.index(i)
print'EGL'[cmp(t,long(n,9))]

As for numbers equal to their strength, I think the only solutions are, for every N x N square up to N=8 a square containing N in every space. My thinking is that since every number in a loop must be the same number (the length of the loop) each loop would have to be all in one direction. This of course means that the loop's size must be N (and each element must be N). I'm pretty sure that this logic can be applied to squares and loops of any size, meaning there are no squares equal to their strength other than the first 8.

\$\endgroup\$
  • \$\begingroup\$ Though unlikely, it might be possible for loops larger than 8. \$\endgroup\$ – overactor Aug 27 '14 at 6:14
  • 2
    \$\begingroup\$ I think this gives the wrong result on 3117275531177455, because of loop sizes greater than 8. See my post. \$\endgroup\$ – isaacg Aug 27 '14 at 6:51
  • 1
    \$\begingroup\$ @isaacg Oh I didn't see that, I changed it to make it work but I'm not going to try and golf it further because that would pretty much be just copy-pasting your answer. Oh and I think you can improve your last two lines by using cmp. \$\endgroup\$ – KSab Aug 27 '14 at 18:38
1
\$\begingroup\$

CJam - 81

q:X,:L,{[L2*{_[_Lmqi:Smd@X=432501678s#3md]2/z{~+(S+S%}%Sb}*]L>_&,\X=~-}%9bg"EGL"=

Try it at http://cjam.aditsu.net/

It can probably be golfed some more.

\$\endgroup\$
0
\$\begingroup\$

Lua - Not golfed yet

Just putting in here for safekeeping. I'll golf it (and implement the "For a larger grid these numbers might be larger than 8, but we can still use them as "digits"") later. Works though.

d={{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1}}
d[0]={0,0}ssd=''
n=arg[1]
q=math.sqrt(#n)t={}

    for y=1,q do
    table.insert(t,y,{})
    for x =1,q do
        v=(y-1)*q+x
        table.insert(t[y],x,n:sub(v,v)+0)
        io.write(t[y][x])
    end
end
for y=1,q do
    for x=1,q do
        cx=x cy=y pxy=''sd=0
        while pxy:match(cx..':%d*:'..cy..' ')==nil do
            pxy=pxy..cx..':'..sd..':'..cy.." "
            ccx=cx+d[t[cx][cy]][2]
            ccy=cy+d[t[cx][cy]][1]
            cx=ccx cy=ccy
            if cx<1 then cx=q elseif cx>q then cx=1 end
            if cy<1 then cy=q elseif cy>q then cy=1 end
            sd=sd+1
        end
        dds=(pxy:sub(pxy:find(cx..':%d+:'..cy)):match(':%d*'))
        ssd=ssd..(sd-dds:sub(2))
    end
end
print(ssd)
nn=tonumber(n,9) tn=tonumber(ssd,9)
if tn>nn then print("G") elseif tn==nn then print("E") else print("L") end
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy