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\$
  • \$\begingroup\$ Can a number ending in zero be a reverse Keith number? \$\endgroup\$ – Iszi Nov 18 '13 at 15:11
  • \$\begingroup\$ Iszi I don't think so. \$\endgroup\$ – Smetad Anarkist Nov 18 '13 at 15:57
  • \$\begingroup\$ Bah. That's going to force a little bloat in the code. \$\endgroup\$ – Iszi Nov 18 '13 at 16:24
  • 2
    \$\begingroup\$ For those needing test cases: oeis.org/A097060 \$\endgroup\$ – Iszi Nov 18 '13 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 Nov 21 '13 at 12:01
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\$
  • \$\begingroup\$ I always wonder how people can write APL. \$\endgroup\$ – Martin Thoma Nov 18 '13 at 18:26
  • \$\begingroup\$ @moose: you need a special keyboard layout \$\endgroup\$ – marinus Nov 18 '13 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\$ – Martin Thoma Nov 18 '13 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 Nov 18 '13 at 21:18
  • \$\begingroup\$ You used non-ascii even for variable names!!!(;°Д°) \$\endgroup\$ – TwiNight Dec 2 '13 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\$
  • 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\$ – Dom Hastings Nov 18 '13 at 13:44
  • 1
    \$\begingroup\$ Thanks for the tips. I'll definitely reuse eval join'+' in the future. \$\endgroup\$ – flesk Nov 18 '13 at 13:52
  • 1
    \$\begingroup\$ @DomHastings: I updated my answer with your suggestions. \$\endgroup\$ – flesk Nov 19 '13 at 13:12
  • \$\begingroup\$ Ah, nice catch with split// to s/./g, glad to have helped! \$\endgroup\$ – Dom Hastings Nov 19 '13 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\$
  • \$\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 Nov 18 '13 at 17:38
  • \$\begingroup\$ Fair enough. I grabbed the wrong code. \$\endgroup\$ – DavidC Nov 18 '13 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 Nov 18 '13 at 17:42
  • \$\begingroup\$ I rolled back to an earlier, correct version. \$\endgroup\$ – DavidC Nov 18 '13 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 Nov 20 '13 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\$
  • \$\begingroup\$ So... this only works on the first 6 Reverse Keith numbers? Kinda weak. \$\endgroup\$ – Iszi Dec 1 '13 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\$ – Thom Wiggers Dec 1 '13 at 10:28

Your Answer

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

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