Offline real-time how to write F06 implementation example

Problem: http://nabetani.sakura.ne.jp/hena/ordf06numit/ Implementation links: https://qiita.com/Nabetani/items/deda571c9451bd7d3175

I think it's an option to make a memo while calling recursively, but how about it? People who are afraid of recursive calls may have their own stack, but if you recurse without worrying about it, it looks like this. First with ruby.

ruby:ruby2.4.2

class Solver
  def initialize( f, g )
    @f=f
    @g=g
    @memo={}
  end
  def solve( root, num )
    return 0  if root<num
    return @memo[root] ||= ( root==num ? 1 : 0 ) + solve( @f[root], num ) + solve( @g[root], num )
  end
end

class SolverNoMemo
  def initialize( f, g )
    @f=f
    @g=g
  end
  def solve( root, num )
    return 0  if root<num
    return ( root==num ? 1 : 0 ) + solve( @f[root], num ) + solve( @g[root], num )
  end
end

def solve( src )
  Solver.new(
    ->(x){ x/2-10 },
    ->(x){ x*2/3 }
  ).solve( *src.split(?,).map(&:to_i) ).to_s
end

DATA.map{ |line|
  num, src, expected = line.split(/\s+/)
  actual = solve( src )
  ok = actual == expected
  p [ ok ? "ok" : "**NG**", src, actual, expected ]
  ok
}.all?.tap{ |x| puts( x ? "okay" : "something wrong" ) }

__END__
0 123,4 5 links
1 1,1 1 link
30  5745432,1032 1287 Abbreviation

Most of the test data is omitted. "SolverNoMemo" is a version without notes. It takes about 1 minute here. If you make a memo, it will take less than a second.

Then with C99. This is only the version with memoization.

c99

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solve_impl( int root, int num, int * buffer )
{
  if ( root<num ){
    return 0;
  }
  if ( root==num ){
    return 1;
  }
  if ( buffer[root] ){
    return buffer[root];
  }
  int a=solve_impl( root/2-10, num, buffer) + solve_impl( root*2/3, num, buffer);
  buffer[root]=a;
  return a;
}

char const * solve( char const * src )
{
  int root = atoi(src);
  char const * comma = strchr( src, ',' );
  int num = atoi( comma+1 );
  int * buffer = calloc( sizeof(int), root+1 );
  int ans = solve_impl( root, num, buffer );
  free( (void*)buffer);
  char s[100];
  sprintf( s, "%d", ans );
  return strdup(s);
}

void test( char const * src, char const * expected )
{
  char const * actual = solve( src );
  _Bool okay = 0==strcmp( actual, expected );
  printf( "%s %s->%s / %s\n", (okay ? "ok" : "**NG**"), src, actual, expected );
  free( (void*)actual );
}

int main(void)
{
/*0*/ test( "123,4", "5" );
/*1*/ test( "1,1", "1" );
/*2*/ test( "2,1", "1" );
/*30*/ test( "5745432,1032", "1287" );  
}

This problem doesn't get much longer in C.

After all memory management is troublesome. If you forget to free it, you won't notice it.

There was a concern that it would be too straight as a problem, but there were various things in the field. I hope you enjoy it.