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.

Recommended Posts

Offline real-time how to write F06 implementation example
Offline real-time how to write F03 ruby and C implementation example
How to write offline real-time Java implementation example of F01 problem
How to write offline real time Implementation example by ruby and C99 of F04
Offline real-time how to write Implementation example of the problem in E05 (ruby, C11)
How to write offline 15th reference question answer
How to write Rails
How to write dockerfile
How to write docker-compose
How to write Mockito
How to write migrationfile
How to write good code
Bit Tetris (how to write)
How to write java comments
Great poor (how to write)
How to write Junit 5 organized
How to write Rails validation
How to write Rails seed
[Ruby] How to write blocks
How to write Rails routing
Studying Java # 6 (How to write blocks)
[Rails] How to write in Japanese
How to write a ternary operator
Rails on Tiles (how to write)
[Rails] How to write exception handling?
How to write Java variable declaration
Y-shaped road tour (how to write)
How to write easy-to-understand code [Summary 3]
[RSpec] How to write test code
[Basic] How to write a Dockerfile Self-learning ②
[Introduction to Java] How to write a Java program
[Java] How to output and write files!
How to write Spring AOP pointcut specifier
How to write an RSpec controller test
[SpringBoot] How to write a controller test
How to write and explain Dockerfile, docker-compose
JDBC promises and examples of how to write
Rails: How to write a rake task nicely
[JavaFX] How to write Eclipse permissions in build.gradle
[Rails] How to write when making a subquery
Java Development Basics ~ How to Write Programs * Exercise 1 ~
How to write an if statement to improve readability-java
JUnit 5: How to write test cases in enum
How to write code that thinks object-oriented Ruby
How to write test code with Basic authentication
How to write React Native bridge ~ Android version ~
[Java] Memo on how to write the source
How to write Java String # getBytes in Kotlin?
Notes on how to write comments in English
How to deploy
Javaer tries to summarize how to write properties in C #
[Ruby on Rails] How to write enum in Japanese
How to write Scala from the perspective of Java
[Java] Types of comments and how to write them
How to write a unit test for Spring Boot 2
java: How to write a generic type list [Note]
[Even beginners can do it! ] How to write Javadoc
How to write to apply gem Pagy (pagination) to an array
How to write a date comparison search in Rails
How to write an external reference key in FactoryBot
How to write modern Java. Immutable Java, consider Null safety.