[RUBY] Exemple d'implémentation de F06 d'écriture en temps réel hors ligne

Problème: http://nabetani.sakura.ne.jp/hena/ordf06numit/ Liens d'implémentation: https://qiita.com/Nabetani/items/deda571c9451bd7d3175

Je pense que c'est une option pour faire un mémo tout en l'appelant récursivement. Les personnes qui ont peur des appels récursifs peuvent avoir leur propre pile, mais si vous vous récitez sans vous en soucier, cela ressemble à ceci. D'abord avec du rubis.

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 liens
1 1,1 1 lien
30  5745432,1032 1287 Abréviation

La plupart des données de test sont omises. "SolverNoMemo" est une version sans notes. Cela prend environ 1 minute ici. Si vous rédigez un mémo, cela prendra moins d'une seconde.

Puis avec C99. Ce n'est que la version avec mémo.

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" );  
}

Ce problème ne devient pas beaucoup plus long en C.

Après tout, la gestion de la mémoire est gênante. Si vous oubliez de le libérer, vous ne le remarquerez pas.

On craignait que ce ne soit trop simple comme problème, mais il y avait diverses choses sur le terrain. J'espère que ça vous plait.