5
\$\begingroup\$

Slighty inspired by my previous challenge regarding Keith Numbers I want to propose a challenge to create a function that takes an integer and gives back a true or false depending on the number is a Reverse Keith number or not.

A reverse Keith uses the same little algorithm as Keith numbers, but ends up with it's starting number in reverse.

For example 12 is a Reverse Keith number

12

1 + 2 = 3

2 + 3 = 5

3 + 5 = 8

5 + 8 = 13

8 + 13 = 21

\$\endgroup\$
5
  • \$\begingroup\$ Can a number ending in zero be a reverse Keith number? \$\endgroup\$
    – Iszi
    Commented Nov 18, 2013 at 15:11
  • \$\begingroup\$ Iszi I don't think so. \$\endgroup\$ Commented Nov 18, 2013 at 15:57
  • \$\begingroup\$ Bah. That's going to force a little bloat in the code. \$\endgroup\$
    – Iszi
    Commented Nov 18, 2013 at 16:24
  • 2
    \$\begingroup\$ For those needing test cases: oeis.org/A097060 \$\endgroup\$
    – Iszi
    Commented Nov 18, 2013 at 18:05
  • \$\begingroup\$ I've got a couple of questions after looking at some older questions on this site: 1) I noticed that some solutions use command switches. Are these allowed and if so do they count against the length of the solution? The way codegolf.com worked, if I wanted to add the loop switch -n to a Perl script, I'd have to add #!perl -n to the first line, and thus adding 10 characters to the length of the solution. 2) When this assignment (and others) ask for a true/false value, is a 1/0 output acceptable for languages which don't use explicit true/false for boolean values? \$\endgroup\$
    – flesk
    Commented Nov 21, 2013 at 12:01

6 Answers 6

3
\$\begingroup\$

APL (28)

⍙∊{1↓⍵,+/⍵}⍣{⊃⍺≥⍙∘←⍎⌽∆}⍎¨∆←⍞

Using more or less the same method as TwiNight did in the other question but reversing the number.

Explanation:

  • ∆←⍞: read a line as text, store in
  • ⍎¨: evaluate each character
  • {1↓⍵,+/⍵}: add the sum of the list to the end of the list, and drop the first item,
  • : until
  • {⊃⍺≥⍙∘←⍎⌽∆}: the first item on the list is greater or equal to , which is the evaluation () of the reverse () of .
  • ⍙∊: see if is contained in the final list.
\$\endgroup\$
5
  • \$\begingroup\$ I always wonder how people can write APL. \$\endgroup\$ Commented Nov 18, 2013 at 18:26
  • \$\begingroup\$ @moose: you need a special keyboard layout \$\endgroup\$
    – marinus
    Commented Nov 18, 2013 at 18:43
  • 1
    \$\begingroup\$ Not only the symbols ... you also have to know what the symbols mean. I can't even see control structures / loops / IO / variable declaration in that code. \$\endgroup\$ Commented Nov 18, 2013 at 19:34
  • 1
    \$\begingroup\$ @moose: It's not really hard. There's only about 80 symbols. They are visually distinct, most have at least a semi-obvious visual meaning, and even the ones that don't are internally consistent. For example, if you know that is eval, it's not hard to remember that is format. I find it a lot easier to read and write than Golfscript. \$\endgroup\$
    – marinus
    Commented Nov 18, 2013 at 21:18
  • \$\begingroup\$ You used non-ascii even for variable names!!!(;°Д°) \$\endgroup\$
    – TwiN
    Commented Dec 2, 2013 at 23:43
2
\$\begingroup\$

Perl, 126 111 110 chars

$r=reverse$_=shift;$l=@n=split//;while(1){$t=0;$t+=$_ for@n[-$l..-1];push@n,$t;die"true\n"if$r==$t;last if$t>$r}die"false\n";

Should be some room for improvement.

Updated with tips from Dom Hastings:

$r=reverse$_=shift;$l=@n=/./g;push(@n,$t=eval join'+',@n[-$l..-1])&&$r==$t&&die"true\n"while$r>$t;die"false\n"

You forgot that $t isn't being assigned a value with your suggestion, so that adds 3 characters if I want to use that in the following comparisons (it's still cheaper than using $n[-1] twice). However, I can save those by changing split// to /./g.

Slight improvement:

$r=reverse$_=shift;$l=@n=/./g;push@n,$t=eval join'+',@n[-$l..-1]and$r==$t&&die"true\n"while$r>$t;die"false\n"

Replaced && operators with lower precedence and to be able to drop parentheses around call to push. Saves one character.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Hi Flesk, thought I'd contribute a few extra savers: changing: $t=0;$t+=$_ for@n[-$l..-1];push@n,$t to: push@n,eval join'+',@n[-$l..-1] saves a few bytes and changing: die"true\n"if$r==$t to: $r==$t&&die"true\n" -0 char change, but now can use another statement modifier, changing: while(1){...last if$t>$r} to: ...while$r>=@n[-1] all those (and dropping the last semi-colon) should save you 15 chars in total! \$\endgroup\$ Commented Nov 18, 2013 at 13:44
  • 1
    \$\begingroup\$ Thanks for the tips. I'll definitely reuse eval join'+' in the future. \$\endgroup\$
    – flesk
    Commented Nov 18, 2013 at 13:52
  • 1
    \$\begingroup\$ @DomHastings: I updated my answer with your suggestions. \$\endgroup\$
    – flesk
    Commented Nov 19, 2013 at 13:12
  • \$\begingroup\$ Ah, nice catch with split// to s/./g, glad to have helped! \$\endgroup\$ Commented Nov 19, 2013 at 14:43
1
\$\begingroup\$

PowerShell: 149 135

Mostly derived from my original Keith Number Checker. I'm sure there's still some work to be done.

$k=+(($j=($i=+(read-host))-split''|?{$_})[99..0]-join'');While($x-lt$k){$x=0;$j|%{$x+=$_};$null,$j=$j+$x}$x-eq$k-and$i-gt9-and$i%10-ne0

I definitely need to double-check for redundant parenthesis and semicolons. It's possible one of the casts to integer is unnecessary. One thing I might also need to spend time on is finding out if I can avoid false-positives without -and$i%10-ne0.

It'd be really nice if there was a reliable way to do a left-shift-and-append that's shorter than $null,$j=$j;$j=@($j);$j+=$x.

EDIT: Found it! $null,$j=$j+$x

Cleanup $x between runs, and also $i, $j, $k when you're done.

\$\endgroup\$
1
\$\begingroup\$

Mathematica 157 96

f = (d = IntegerDigits@#; r = FromDigits@Reverse@d; 
NestWhile[Rest@Append[#, Tr@#] &, d, Max@# < r &][[-1]] == r) &

Based on code by Anton Vrba and considerably streamlined by @ssch.

f[11]  
f[12]
f[20]
f[24]

False
True
False
True

\$\endgroup\$
5
  • \$\begingroup\$ Something's wrong here. The numbers you have appear to be a series of Keith Numbers - not Reverse Keith Numbers. From Wikipedia's article on Keith Numbers, under Examples: 14, 19, 28, 47, 61, 75, 197, 742, 1104, 1537, 2208, 2580, 3684, 4788, 7385, 7647, 7909.... I don't know certainly about the rest, but I tested 14 and it definitely is not a Reverse Keith Number. Its progression jumps from 37 to 60, where it would need to pass through 41 to be a Reverse Keith Number. 1+4=5, 4+5=9, 5+9=14, 9+14=23, 14+23=37, 23+37=60 \$\endgroup\$
    – Iszi
    Commented Nov 18, 2013 at 17:38
  • \$\begingroup\$ Fair enough. I grabbed the wrong code. \$\endgroup\$
    – DavidC
    Commented Nov 18, 2013 at 17:40
  • \$\begingroup\$ A real hint should have been when the "find all" bit didn't produce the example given in the question, 12. ;-) \$\endgroup\$
    – Iszi
    Commented Nov 18, 2013 at 17:42
  • \$\begingroup\$ I rolled back to an earlier, correct version. \$\endgroup\$
    – DavidC
    Commented Nov 18, 2013 at 17:45
  • \$\begingroup\$ You can drop it down to 93 ( d = IntegerDigits[#]; r = FromDigits@Reverse@d; NestWhile[Rest@Append[#, Tr@#] &, d, Max@# < r &][[-1]] == r ) & \$\endgroup\$
    – ssch
    Commented Nov 20, 2013 at 15:26
1
\$\begingroup\$

Game Maker Language, 129 136

Make this the function/script f and compile with uninitialized variables as 0.

a=argument0;while(a>0){b*=10b+=(a mod 10)b div 10}k[]=1k[1]=1while(k[c]<b){c+=1k[c]=k[c-1]+k[c-2]}while(e<c){e+=1if k[e]==b r=1}return r

It returns true or false; call with f(any number you want)

Edit #1 Corrected invalid operators % and /= with mod and div.

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

Haskell, 106

This version only works for 0 < x < 100 though.

k x=(last$takeWhile((>=)x)(let f=(map(Data.Char.digitToInt)$reverse$show x)++zipWith(+)f(tail f)in f))==x

TODO: check up on Test if given number if a Keith number and implement a proper algorithm.

\$\endgroup\$
2
  • \$\begingroup\$ So... this only works on the first 6 Reverse Keith numbers? Kinda weak. \$\endgroup\$
    – Iszi
    Commented Dec 1, 2013 at 4:00
  • \$\begingroup\$ yeah, I didn't really have the algorithm down yet when I wrote this, and since it was 3 AM I decided to call it quits. \$\endgroup\$ Commented Dec 1, 2013 at 10:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.