# Digital River (Shortest And Fastest Solution)

This is my first question, so I hope it goes well.

## Background:

It's not the rivers that you might be thinking about. The question revolves around the concept of digital rivers. A digital river is a sequence of numbers where the number following n is n plus the sum of its digits.

Explanation:

12345 is followed by 12360 since 1+2+3+4+5=15 and so 12345 + 15 gives 12360. similarly 145 is followed by 155. If the first number of a digital river is M we will call it river M.

For e.g: River 480 is the sequence beginning {480,492,507,519....}, and river 483 is the sequence beginning {483,498,519,....}. Normal streams and rivers can meet, and the same is true for digital rivers. This happens when two digital rivers share some of the same values.

Example:

River 480 meets river 483 at 519. River 480 meets river 507 at 507 and never meets river 481. Every digital river will eventually meet river 1, river 3 or river 9.

Write a program that can determine for a given integer n the value where river n first meets one of these three rivers.

## Input

The input may contain multiple test cases. Each test case occupies a separate line and contains an integer n (1 <= n <= 16384). A test case with value of 0 for n terminates the input and this test case must not be processed.

## Output

For each test case in the input first output the test case number (starting from 1) as shown in the sample output. Then on a separate line output the line "first meets river x at y". Here y is the lowest value where river n first meets river x (x = 1 or 3 or 9). If river n meets river x at y for more than one value of x, output the lowest value. Print a blank line between two consecutive test cases.

## Test case

Input:

86
12345
0


Output:

Case #1

first meets river 1 at 101

Case #2

first meets river 3 at 12423


## Scoring:

The fastest algorithm wins. In case of tie. The one with shorter code will win.

Thanks to mbomb007 for pointing out my error.

p.s: I want to have the fastest solution rather than the smallest one. I also have a solution of mine which is slow. For that look here.

## Note:

I will be using this for code testing. And performance checking.

• I'm not sure that you can score that way. What if someone's code is O(log(log n))? You can't cover them all, so you need to just say that the fastest algorithm wins, but in case of a tie, shortest code wins, and first posted wins in case both are the same length. Sep 16 '15 at 14:43
• I can't find anything on copyright or usability of old ACM-ICPC challenges, but I can find this challenge on the archive site. Is it permissible to use here? Sep 16 '15 at 15:00
• That has nothing to do with copyright. If in doubt, the easiest thing is normally to email the site owner(s) and ask. Sep 16 '15 at 15:03
• "If the last digit of a digital river is M we will call it river M" doesn't make sense for two reasons: firstly, if a river is an infinite sequence of numbers then it doesn't have a last digit; and secondly, in the next paragraph river M means the river starting at number M. Sep 16 '15 at 15:48
• From the linked CR.SE question, it seems like a river is whichever number started with in the series, but here's it's the last digit. Which is correct? Sep 16 '15 at 15:54

# C, 320 294 bytes

Compile with -std=c99

#include<stdio.h>
int s(int i){for(int j=i;j;j/=10)i+=j%10;return i;}int main(){int c=0,i;while(scanf("%d",&i)){c++;if(!i)continue;int j,o[]={1,3,9},p[]={1,3,9};Q:for(j=0;j<3;j++){if(o[j]==i)goto D;else if(o[j]<i){o[j]=s(o[j]);goto Q;}}i=s(i);goto Q;D:printf("Case #%d\n\nfirst meets river %d at %d\n\n",c,p[j],o[j]);}}


Ungolfed:

#include <stdio.h>

int s(int i)
{
for(int j = i; j; j /= 10)
i += j % 10;
return i;
}

int main()
{
int c = 0, i;
while(scanf("%d", &i))
{
c++;
if(!i)
continue;
int j,o[]={1,3,9},p[]={1,3,9};
Q: for(j = 0; j < 3; j++)
{
if(o[j] == i)
goto D;
else if(o[j] < i)
{
o[j] = s(o[j]);
goto Q;
}
}
i = s(i);
goto Q;
D: printf("Case #%d\n\nfirst meets river %d at %d\n\n", c, p[j], o[j]);
}
}


Try it out!

Essentially, the "target" rivers are increased until they're greater than the river we're testing against, and afterwards the test river is increased. This is repeated until the test river is equal to some other river.

I'm not reading parameters from the command line in this program, and I'm not sure if you're supposed to. Now you can pass parameters to STDIN. You can terminate by passing a non-numeric input.

Also darn, beaten by half an hour.

• I am working on test cases for now. Only 3 input test cases wont be much suitable. Jun 29 '16 at 21:18
• please would you mind taking input from stdin. Jun 29 '16 at 21:21

# JavaScript (ES6)

This is a quite fast answer using a quite slow language. Really, executing time should not be a problem using any language with hash tables. All my tests under 100 ms.

Anonymous method with the list of test case as input parameter.

F=cases=>{
var t0 = +new Date
var result = 0
var spots = []
var top=[,1,3,,9]
var rivers=[,1,3,1,9,1,3,1]
cases.forEach((n,i)=>{
var found = result = spots[n]
for (;!found;)
{
found = top.some((v,i)=>{
for(;spots[v] |= i, v<n; top[i] = v)
[...v+''].forEach(d=>v-=-d)
return result = v-n ? 0 : i;
}) || (
[...n+''].forEach(d=>n-=-d),
result = spots[n]
)
}
console.log(Case #${i+1}\nfirst meets river${rivers[result]} at ${n}) }) return 'Time (ms) ' + (new Date-t0) } console.log(F([86, 12345, 123, 456, 789, 16384])) # Java 7, 519 505 bytes import java.util.*;String c(int i){if(i<=0)return"";ArrayList<Long>r=f(1),s=f(3),t=f(9),x=f(i);String z="first meets river ";for(int j=0;j<r.size();j++){long u=r.get(j),v=s.get(j),w=t.get(j);if(x.contains(u))return z+1+" at "+u;if(x.contains(v))return z+3+" at "+v;if(x.contains(w))return z+9+" at "+w;}return"";}ArrayList f(long i){ArrayList<Long>l=new ArrayList();l.add(i);for(long j=0,x;j<9e4;j++){x=l.get(l.size()-1);for(char c:(x+"").toCharArray())x+=new Long(c+"");l.add(x);if(x>16383)return l;}return l;}  Yes, it's long, ugly and can without a doubt be completely changed to code-golf it more.. I'm both distracted and tired, so perhaps I should just delete it again.. It was a pretty hard challenge to be honest.. But at least you have your first answer.. ;) (Which might even be longer than your original ungolfed C++ program.. xD) Ungolfed & test cases: Try it here. import java.util.*; class M{ static String c(int i){ if(i <= 0){ return ""; } ArrayList<Long> r = f(1), s = f(3), t = f(9), x = f(i); String z = "first meets river ", y = " at "; for(int j = 0; j < r.size(); j++){ long u = r.get(j), v = s.get(j), w = t.get(j); if(x.contains(u)){ return z+1+y+u; } if(x.contains(v)){ return z+3+y+v; } if(x.contains(w)){ return z+9+y+w; } } return ""; } static ArrayList f(long i){ ArrayList<Long> l = new ArrayList(); l.add(i); for(long j = 0, x; j < 9e4; j++){ x = l.get(l.size() - 1); for(char c : (x + "").toCharArray()){ x += new Long(c+""); } l.add(x); if(x > 16383){ return l; } } return l; } public static void main(String[] a){ System.out.println(c(86)); System.out.println(c(12345)); System.out.println(c(0)); } }  Output: first meets river 1 at 101 first meets river 3 at 12423 (empty output)  • I will compare yours program with mine. I am also going to post my solution too. Why to use a slow language. Use any fast language. Jun 29 '16 at 14:06 • I only noticed the fastest-algorithm tag later on.. I always post Java 7 code-golf answers here.. It's defintely not going to win in either shortest or fastest though.. Btw, your rextester gives errors when it should only give warnings for lack of casts / type-initializes.. It works on ideone (and in Eclipse IDE). Jun 29 '16 at 14:09 • ok. let me see. rextester gives compile time and execution time. So i used it Jun 29 '16 at 14:12 • well thats a problem here. I will look for other online compiler which gives the compile time and execution time Jun 29 '16 at 14:14 • @KishanKumar I've added the casts in my code, which shouldn't affect time a.f.a.i.k. Here is the working rextester code with the result: Compilation time: 0.62 sec, absolute running time: 0.14 sec, cpu time: 0.11 sec, memory peak: 22 Mb, absolute service time: 0,77 sec for me locally. So yeah, it's pretty slow.. Jun 29 '16 at 14:17 # Scala, 774 bytes I don't feel like golfing it. It finds a solution to the posed problem within 50ms Usage may not be exactly what you want: scala river.scala Now you can continuously input numbers followed by an enter. And terminate the program with 0. The result will be printed as soon as you hit enter. io.Source.stdin.getLines.map(_.toInt) .takeWhile(_ != 0) .map(stream(_).takeWhile(_ < 16383)) .zipWithIndex .map { cur => Seq(1, 3, 9).map { i => val s = stream(i).takeWhile(_ < 16383) (cur._2+1, i, s.intersect(cur._1).headOption) } }.foreach { opts => val options = opts.filterNot(_._3.isEmpty) if(options.isEmpty) { println("No result") } else { val opt = options(0) println(s"Case #${opt._1}\n\nfirst meets ${opt._2} at${opt._3.get}\n\n")
}
}

def stream(i:Int): Stream[Int] = {
def sub: Int => Stream[Int] = {
i => i #:: sub(a(i))
}
sub(i)
}

def a(i:Int): Int = i + i.toString.map{_.asDigit}.sum

• I don't know much about Scala. So please could you modify the code which will according to rextester.com/l/scala_online_compiler Sep 7 '16 at 15:59
• I tried to put it in there but it timed out while compiling. Sep 7 '16 at 16:16
• ok @AmazingDreams Sep 7 '16 at 16:21
• @KishanKumar even the default one times out so the site seems to be broken for scala Sep 7 '16 at 16:22
• @KisthanKumar Use this one scalafiddle.net/console/4ec96ef90786e0f2d9f7b61b5ab0209b it does not support stdin though so I had to change some minor things. Sep 7 '16 at 19:34

## C, 228 283300 bytes

This is a mod of Yakov's code to take advantage of the river patterns. This makes it ~3x faster. Also, unsigned integers avoid the cltod penalty on 64-bit machines, so it's a few bytes longer but fractionally faster.

#define sum(z) for(y=z;y;y/=10)z+=y%10;
n,x;main(){unsigned i,j,y;while(scanf("%d",&i)){if(i){j=x=1+!(i%3)*2+!(i%9)*6;do{while(j<i)sum(j)}while(j^i&&({sum(i)i;}));printf("Case #%u\n\nfirst meets river %u at %u\n\n",++n,x,i);}}}


Ungolfed:

#define sum(z) for(y=z;y;y/=10)z+=y%10;
n, x;
main() {
unsigned i, j, y;
while(scanf("%d", &i)) {
if(i){
j = x = 1 + !(i%3)*2 + !(i%9)*6;
do{
while (j < i) sum(j)
}
while(j^i&&({sum(i)i;}));
printf("Case #%u\n\nfirst meets river %u at %u\n\n", ++n, x, i);
}
}
}


Explanation:

j = x = 1 + !(i%3)*2 + !(i%9)*6;


This selects the correct river. River 1 meets every other river, so we use this as the fall-back case. If 3 is the greatest common divisor of the test river, we select river 3 (1 + !(i%3)*2). If 9 is the greatest common divisor of the test river, we override the previous values and select river 9.

Why does this work? River 9 goes 9, 18, 27, 36, etc. This steps by a multiple of 9 each time thus it will always be the shortest route to a sister river. River 3 will step by a multiple of 3 each time: 3, 6, 12, 15, 21, etc. While rivers that are a multiple of 9 are also a multiple of 3, we choose them as river 9 first, leaving only the multiples of 3. The remainder will meet river 1 first: 1, 2, 4, 8, 16, 23, 28, etc.

Once we have selected our correct river, we step the two rivers until they meet.

# Python 3, 144 bytes

r,a,b,c,i={int(input())},{1},{3},{9},1
while i:
for x in r,a,b,c:t=max(x);x|={sum(int(c)for c in str(t))+t}
if r&(a|b|c):i=print(*r&(a|b|c))


# C

Very simple, it just looks that long because I unrolled all the 3 rivers. It first generates the 3 rivers up to RIVER_LENGTH (which I hope is big enough), and then for each step on N it does a binary search on all three streams to see if it is in any of them. This works because the streams are already sorted, so we can do the contains check in log(n) time.

#include <stdio.h>

#define RIVER_LENGTH 10000

int main() {
int num_cases;
scanf("%d", &num_cases);
int cases[num_cases];
int N;
int s1[RIVER_LENGTH] = {1};
int s3[RIVER_LENGTH] = {3};
int s9[RIVER_LENGTH] = {9};
int i;
int temp;

for (i = 1; i < RIVER_LENGTH; i++) {
s1[i] = temp = s1[i-1];
while (temp) {
s1[i] += temp % 10;
temp /= 10;
}
}

for (i = 1; i < RIVER_LENGTH; i++) {
s3[i] = temp = s3[i-1];
while (temp) {
s3[i] += temp % 10;
temp /= 10;
}
}

for (i = 1; i < RIVER_LENGTH; i++) {
s9[i] = temp = s9[i-1];
while (temp) {
s9[i] += temp % 10;
temp /= 10;
}
}

int start;
int end;
int pivot;

for (i=1; i <= num_cases; i++) {
scanf("%d", &cases[i]);
}

for (i=1; i <= num_cases; i++) {
printf("Case #%d\n\n", i);
N = cases[i];

while (1) {

temp = N;
while (temp) {
N += temp % 10;
temp /= 10;
}

start = 0;
end = RIVER_LENGTH;
pivot = 1;

while (end != start && pivot != RIVER_LENGTH - 1) {
pivot = start + ((end - start) >> 1);
if (s1[pivot] == N) {
printf("first meets river 1 at %d\n\n", N);
goto case_done;
} else if (N < s1[pivot]){
end = pivot;
} else {
start = pivot+1;
}
}

start = 0;
end = RIVER_LENGTH;
pivot = 1;

while (end != start && pivot != RIVER_LENGTH - 1) {
pivot = start + ((end - start) >> 1);
if (s3[pivot] == N) {
printf("first meets river 3 at %d\n\n", N);
goto case_done;
} else if (N < s3[pivot]){
end = pivot;
} else {
start = pivot+1;
}
}

start = 0;
end = RIVER_LENGTH;
pivot = 1;

while (end != start && pivot != RIVER_LENGTH - 1) {
pivot = start + ((end - start) >> 1);
if (s9[pivot] == N) {
printf("first meets river 9 at %d\n\n", N);
goto case_done;
} else if (N < s9[pivot]){
end = pivot;
} else {
start = pivot+1;
}
}
}

case_done:;

}
}


It takes a number for the number of cases first, instead of using 0 to delimit the end of the inputs, because you know, C. This is just for convenience and doesn't really affect anything, so I hope its okay.

• This program hits a time limit exceeded on ideone on inputs 86,12345,0 Jun 29 '16 at 21:17
• ideone.com/mHCeef here is the link. And it gives a kill signal output on rextester Jun 29 '16 at 21:20
• @KishanKumar It takes a number for the number of cases first, instead of using 0 to delimit the end of the inputs, because you know, C. This is just for convenience and doesn't really affect anything, so I hope its okay. Jun 29 '16 at 21:28
• @KishanKumar try this one instead: rextester.com/XRJK89444 Jun 29 '16 at 21:29
• its ok. No problem. But i will have to write an extra script for your program. As i have to take average time of all the input range. Jun 30 '16 at 4:50