Levenshtein distance & OEIS (Robbers)

11

This is the Robber post. The Cop post is here.

Your task is to take an integer input N and output the Nth digit in the sequence OEIS A002942.

The sequence consists of the square numbers written backwards:

1, 4, 9, 61, 52, 63, 94, 46, 18, 1, 121, 441, ...

Note that leading zeros are trimmed away (100 becomes 1, not 001). Concatenating this into a string (or one long number gives):

1496152639446181121441

You shall output the Nth digit in this string/number. You may choose to take N as 0-indexed or 1-indexed (please state which one you choose).

Test cases (1-indexed):

N = 5,      ==> 1
N = 17,     ==> 1   <- Important test case! It's not zero.
N = 20,     ==> 4
N = 78,     ==> 0
N = 100,    ==> 4
N = 274164, ==> 1

Your code should work for numbers up to N = 2^15 (unless your language can't handles 32 bit integers by default, in which case N can be lower).

Robbers:

You should try to crack the Cops' posts.

Your code must be in the same language as the Cop post, and have a Levenshtein distance exactly equal to the distance given by the cop. Your code cannot be longer than the original solution (but it can be the same size).

You may check the Levenshtein distance here!

The winner will be the robber that cracked the most posts.

Stewie Griffin

Posted 2017-11-02T14:04:31.547

Reputation: 43 471

Wait... so if the robber's result doesn't have to be the same as the original intended program... Can't the cop just write one program and make up a distance...? – Magic Octopus Urn – 2017-11-02T15:55:02.870

Well, the cops must provide the alternative code in order to mark the submission as safe and be eligible for the win. I've clarified in the cop post. :) – Stewie Griffin – 2017-11-02T17:03:29.377

I've never tried a cop-and-robber challenge. All of this was very confusing to me hah! – Magic Octopus Urn – 2017-11-02T17:11:42.940

Answers

4

Haskell, Laikoni

((show.(*1).read.reverse.show.(^2)=<<[1..])!!)

Try it online!

The (*1) was necessary for type checking.

H.PWiz

Posted 2017-11-02T14:04:31.547

Reputation: 10 962

3

JavaScript, Arnauld

/*ZZ*/m=>[...Array(m+1).keys()].map(eval(atob("eD0+K1suLi4iIit4KnhdLnJldmVyc2VgYC5qb2luYGA="))).join``[m]

Lynn

Posted 2017-11-02T14:04:31.547

Reputation: 55 648

1@Arnauld OK, I think Array(m+1) fixed it. – Lynn – 2017-11-03T09:09:28.247

It does. FWIW, I've added the intended solution to my post. – Arnauld – 2017-11-03T09:30:10.000

2

cQuents 0, Stephen

":\r$$

Try it online! I have no idea how this code works, but it still worked after removing the *.

Laikoni

Posted 2017-11-02T14:04:31.547

Reputation: 23 676

2

Wolfram Language (Mathematica), Jenny_mathy

(Join@@Table[k@FromDigits@Reverse@(k=IntegerDigits)[i*i],{i,10^4}])[[#]]&

Try it online!

Alternative version also at distance 43:

(Join@@IntegerDigits@IntegerReverse[Range@#^2])[[1#]]&

Try it online!

Misha Lavrov

Posted 2017-11-02T14:04:31.547

Reputation: 4 846

2

6502 Machine Code (C64), Felix Palmen

I tested this with all the questions test cases and quite a few extras (like 2^15... that took awhile), and it appears to work the same as the original with LD = 1.

00 C0 20 FD AE A0 00 99 5B 00 C8 20 73 00 90 F7 99 5B 00 A2 0B CA 88 30 09 B9
5B 00 29 0F 95 5B 10 F3 A9 00 95 5B CA 10 F9 A9 01 A0 03 99 69 00 88 10 FA A0
20 A2 76 18 B5 E6 90 02 09 10 4A 95 E6 E8 10 F4 A2 03 76 69 CA 10 FB 88 F0 11
A2 09 B5 5C C9 08 30 04 E9 03 95 5C CA 10 F3 30 D6 A2 03 B5 69 95 57 CA 10 F9
A9 01 85 FB A2 03 A9 00 95 FB CA D0 FB A2 03 B5 FB 95 22 95 26 CA 10 F7 A9 00
A2 03 95 69 CA 10 FB A0 20 A2 02 46 25 76 22 CA 10 FB 90 0C A2 7C 18 B5 AA 75
ED 95 ED E8 10 F7 A2 7D 06 26 36 AA E8 10 FB 88 10 DD A0 0B A9 00 99 5A 00 88
D0 FA A0 20 A2 09 B5 5C C9 05 30 04 69 02 95 5C CA 10 F3 06 69 A2 FD 36 6D E8
D0 FB A2 09 B5 5C 2A C9 10 29 0F 95 5C CA 10 F4 88 D0 D7 E0 0A F0 05 E8 B5 5B
F0 F7 09 30 99 5B 00 C8 E8 E0 0B F0 04 B5 5B 90 F1 88 B9 5B 00 C9 30 F0 F8 A2
7C 18 B5 DB E9 00 95 DB E8 10 F7 90 14 88 30 05 B9 5B 00 D0 EA A2 7C F6 7F D0
03 E8 10 F9 4C 73 C0 B9 5B 00 4C D2 FF

Online demo, usage: sys49152,n where n is the 0-indexed input.

Jo.

Posted 2017-11-02T14:04:31.547

Reputation: 974

This is correct because you found some utterly useless code I wasn't aware of and the change is in this code :o – Felix Palmen – 2017-11-10T08:27:07.813

1

Python 3, HyperNeutrino

lambda o:"".join(str(p*p+2*p+1)[::~0].lstrip("0")for p in range(o+1))[o]

Try it online!

Mr. Xcoder

Posted 2017-11-02T14:04:31.547

Reputation: 39 774

Ninja'd in 9 sec :P – Uriel – 2017-11-02T14:19:18.267

huh interesting, was not the one I had but nice :) – HyperNeutrino – 2017-11-02T14:19:30.817

You could also do '' instead of "" – Uriel – 2017-11-02T14:19:47.220

@Uriel Yeah, I know a ton of alternatives. – Mr. Xcoder – 2017-11-02T14:20:09.503

An alternative crack would be lambda i:"".join(str( (-~k)**2)[::-1]for k in range(i+1))[i].

– Erik the Outgolfer – 2017-11-02T14:24:25.150

For reference, my solution was lambda i:"".join(str(k**2)[::-1]for k in range(1,i+2))[i] – HyperNeutrino – 2017-11-02T14:47:30.697

@HyperNeutrino I was too lazy to not abuse the rules :) – Mr. Xcoder – 2017-11-02T14:53:43.577

I'm afraid this is invalid. It doesn't trim away leading zeros. Try f(16) for instance. – Stewie Griffin – 2017-11-02T15:05:34.920

@StewieGriffin Then... The initial answer is wrong too I think – Mr. Xcoder – 2017-11-02T15:06:18.640

Yes, I'm about to comment on it. – Stewie Griffin – 2017-11-02T15:07:40.390

1

Lua, Katenkyo

i=1s=""while(#s<...+0)do s=s..((i*i)..""):reverse():gsub("(0+)(%d+)$","%2")i=i+1 end
print(s:sub(...,...))

Try it online!

I don't know Lua, but this was a simple one, just replaced a space with a newline.

Erik the Outgolfer

Posted 2017-11-02T14:04:31.547

Reputation: 38 134

Hum, didn't think about that, the original was about replacing (0+)(%d+)$ with (0+)(%d+), so it was about regex ^^' – Katenkyo – 2017-11-02T14:32:51.047

1

Python 2, dylnan

d=lambda y:y if y%10>0 else d(y/10)
lambda n:''.join([str(d(x*x))[::-1]for x in range(1,n+1)])[n-1]#fix

Try it online!

Note: this cop submission was bugged and didn't work for inputs lower than 5. While I was at it I built this solution which has the correct Levenshtein distance AND fixes the bug.

Leo

Posted 2017-11-02T14:04:31.547

Reputation: 8 482

1

Perl 5, (-p) Xcali

Updated after comment, Levenshtein Distance between

a$j.=int reverse$_**2for 1..$_;$_--;say$j=~s/.{$_}(.).*/$1/r

and

p$_=substr w.(join"",map{whyddwzz;0|reverse$_**2}1..$_),$_,1

is 55

Try it online

Nahuel Fouilleul

Posted 2017-11-02T14:04:31.547

Reputation: 5 582

Given that M5.010 is "free", I don't think it should count here. I'm not really sure how to count the -a versus -p flags. The two solutions I came up with both used the same flags. I would think the flag would just be tacked onto the front without a space, but I'm willing to be swayed by others on that. – Xcali – 2017-11-03T13:04:33.747

updated my answer – Nahuel Fouilleul – 2017-11-03T16:05:23.890

1

Java 8, Kevin Cruijssen

/*!FooBarFooBarFoo!*/N->{String R="",T=R;for(int I=1,J;N+2>R.length();I++){for(T="",J=(I*I+"").length();0<J;T+=(I*I+"").charAt(--J));R+=new Long(T)+"";}return R.charAt(N);}

Try it online!

Change log

  • Replaced .replaceAll() with new Long().
  • Removed the test for perfect squares. Now using perfect squares directly.
  • Updated all variable names to upper-case.
  • Rewritten the inequalities.
  • And finally added a 21-byte leading comment to reach the correct LD.

Arnauld

Posted 2017-11-02T14:04:31.547

Reputation: 111 334

1Oh nice. That's completely different than I had in mind, but nice that you got to 92 LD anyway. The solution I had in mind was: n->{String r="";for(int i=1;r.length()<=n+1;r+=new Long(new StringBuffer(i*i+++"").reverse()+""));return r.charAt(n);} (118 bytes, 92 LD compared to my other answer.) – Kevin Cruijssen – 2017-11-04T11:09:31.857

1

Octave, Stewie Griffin

@(n)regexprep(fliplr(num2str((1:n)'.^2))'(:)',' +0*','')(n)%abcdefghijk

Try it online!

I was actually attempting my own Octave answer and spotted the existing one. Mine was already significantly shorter so adding a comment at the end was sufficient to get to the required distance of 63.

Tom Carpenter

Posted 2017-11-02T14:04:31.547

Reputation: 3 990

Well done :-) I had a loop with input() and everything that goes with it... – Stewie Griffin – 2017-11-04T19:25:11.883

1

PHP, Jo.

<?for($j++;strlen($p)<$argv[1];$j++)$p.=(int)strrev($j**2);echo($p[$argv[1]+2-3]);

Try it online!

(I was planning to switch the inequality in order to get even larger LD...)

Colera Su

Posted 2017-11-02T14:04:31.547

Reputation: 2 291

0

6502 Machine Code (C64), Felix Palmen

May also be a "simple" crack, but it appears to work as the original.
Having the LD = 1 is just so tempting to try to crack it (sorry, Felix). :)

00 C0 20 FD AE A0 00 99 5B 00 C8 20 73 00 90 F7 99 5B 00 A2 0B CA 98 88 30 09
B9 5B 00 29 0F 95 5B 10 F2 95 5B CA 10 FB A0 20 A2 76 18 B5 E6 90 02 09 10 4A
95 E6 E8 10 F4 A2 03 76 69 CA 10 FB 88 F0 11 A2 09 B5 5C C9 08 30 04 EB 03 95
5C CA 10 F3 30 D6 A2 03 B5 69 95 57 CA 10 F9 A9 01 85 FB A2 03 A9 00 95 FB CA
D0 FB A2 03 B5 FB 95 22 95 26 CA 10 F7 A9 00 A2 03 95 69 CA 10 FB A0 20 A2 02
46 25 76 22 CA 10 FB 90 0C A2 7C 18 B5 AA 75 ED 95 ED E8 10 F7 A2 7D 06 26 36
AA E8 10 FB 88 10 DD A2 0B A9 00 95 5A CA D0 FB A0 20 A2 09 B5 5C C9 05 30 04
69 02 95 5C CA 10 F3 06 69 A2 FD 36 6D E8 D0 FB A2 09 B5 5C 2A C9 10 29 0F 95
5C CA 10 F4 88 D0 D7 E8 B5 5B F0 FB 09 30 99 5B 00 C8 E8 E0 0B F0 04 B5 5B 90
F1 88 B9 5B 00 C9 30 F0 F8 A2 7C 18 B5 DB E9 00 95 DB E8 10 F7 90 14 88 30 05
B9 5B 00 D0 EA A2 7C F6 7F D0 03 E8 10 F9 4C 68 C0 B9 5B 00 4C D2 FF

Online demo, usage: sys49152,n where n is the 0-indexed input.

Jo.

Posted 2017-11-02T14:04:31.547

Reputation: 974

I'm not sure whether I have to accept this. It replaces E9 (a subtract command) by EB which is undefined in 6502 machine code, but happens to do the same on NMOS 6502 and 6510 chips. This program would for example crash on the C64 DTV1. But it's unlikely to find a real C64 that doesn't execute it correctly, so it could be considered a valid crack? I might ask for opinions on meta.... – Felix Palmen – 2017-11-15T10:25:22.650

I'd be interested in input here on meta.

– Felix Palmen – 2017-11-15T10:55:37.473

@FelixPalmen I'll take this answer down soon. – Jo. – 2017-11-16T02:24:42.413

keep it, see also my comment on meta. The community clearly expressed the opinion that it's valid. It's my fault not to require only documented 6502 code, and I'll keep that in mind for the future. – Felix Palmen – 2017-11-16T16:59:41.983

Asked: 2017-11-02T14:04:31.547

Viewed: 1 154 times

Active: 2017-11-15T08:14:37.200