Re: C++ help

On Mar 6, 5:20 am, Kai-Uwe Bux <jkherci...@gmx.net> wrote:


[proof]

In my defense, while my C++ is a bit rusty, my math
intuition seems to have actually fossilized from disuse.

[sample output]


There are a couple of subtle bugs in the code, by the way.


I freely admit that the slv() member function is an awful
mess. In my defense, the public interface is fairly clear,
and the terrible things going on in the deep, dark bowels
of a component are of no concern to the user of said
component. Also, if this was production-grade code, I
would've spent some time polishing and annotating it, so it
wouldn't have been *that* bad.

Anyway, while the solution given above does work for the
OP's problem, I decided to see if it could be improved on.
As I said, my math intuition is in no good shape, so I'm
not certain I got the period detection right. Here goes
nothing:

#include <cassert>
#include <string>
#include <iostream>
#include <istream>
#include <ostream>
#include <sstream>
#include <vector>
#include <map>

namespace xyz
{
  class dio
  {
    public :

      typedef unsigned long coeff ;

      typedef std :: vector < coeff > coeff_vec ;
      typedef std :: map < coeff , coeff > coeff_map ;
      typedef std :: vector < coeff_map > sol_vec ;

      typedef coeff_vec :: const_iterator coeff_vec_citr ;
      typedef coeff_map :: const_iterator coeff_map_citr ;
      typedef sol_vec :: const_iterator sol_vec_citr ;

      class sol
      {
        public :

          bool is_sol ( ) const { return is_sol_ ; }
          coeff eff ( ) const { return eff_ ; }

          const sol_vec & s_ref ( ) const { return s_ ; }

        protected :

          friend class dio ;

          sol ( ) : is_sol_ ( false ) , eff_ ( 0 ) { }
          sol ( coeff c ) ;
          sol ( const sol & s , coeff c , coeff i = 1 ) ;

          bool has ( coeff c ) const ;
          bool has ( const coeff_map & sol ) const ;

          void add ( const sol & s ) ;

          bool operator == ( const sol & s ) const
          {
            return
              ( is_sol ( ) == s . is_sol ( ) ) &&
              ( eff ( ) == s . eff ( ) ) ;
          }
          bool operator > ( const sol & s ) const
          {
            return
              ( ! is_sol ( ) && s . is_sol ( ) ) ||
              (
                ( is_sol ( ) && s . is_sol ( ) ) &&
                ( eff ( ) > s . eff ( ) )
              ) ;
          }
          bool operator < ( const sol & s ) const
            { return s > * this ; }
          bool operator >= ( const sol & s ) const
            { return ( * this > s ) || ( * this == s ) ; }
          bool operator <= ( const sol & s ) const
            { return ( * this < s ) || ( * this == s ) ; }

        private :

          bool is_sol_ ;
          coeff eff_ ;
          sol_vec s_ ;
      } ;

      dio ( const coeff_vec & c ) ;

      void init ( ) ;

      sol solve ( coeff sum ) ;

    private :

      typedef std :: vector < sol > sols_vec ;

      typedef sols_vec :: const_iterator sols_vec_citr ;

      bool inited_ ;

      coeff max_coeff_ ;
      coeff_map coeffs_ ;

      sols_vec precomp_ ;

      void populate ( ) ;

      bool pop_c ( coeff c ) ;
      bool pop ( coeff c ) ;
  } ;

  dio :: dio ( const coeff_vec & c ) : inited_ ( false )
  {
    for
    (
      coeff_vec_citr i_coeff = c . begin ( ) ;
      i_coeff != c . end ( ) ; ++ i_coeff
    )
    {
      assert ( 0 < * i_coeff ) ;
      assert ( ! coeffs_ [ * i_coeff ] ) ;

      coeffs_ [ * i_coeff ] = 1 ;
    }

    max_coeff_ = ( * ( -- coeffs_ . end ( ) ) ) . first ;
  }

  void dio :: init ( )
  {
    assert ( ! inited_ ) ;

    populate ( ) ;
    inited_ = true ;
  }

  dio :: sol dio :: solve ( coeff sum )
  {
    assert ( inited_ ) ;

    if ( sum < precomp_ . size ( ) )
      return precomp_ [ sum ] ;

    coeff st = precomp_ . size ( ) - max_coeff_ - 1 ;
    coeff of = sum - st ;
    coeff mx = of / max_coeff_ ;
    coeff ix = of % max_coeff_ ;

    return
      dio :: sol
        ( precomp_ [ st + ix ] , max_coeff_ , mx ) ;
  }

  void dio :: populate ( )
  {
    precomp_ . push_back ( sol ( ) ) ;

    coeff period_len = 0 ;
    for
      ( coeff c = 1 ; period_len != max_coeff_ + 1 ; ++ c )
    {
      bool p ;

      if ( coeffs_ . find ( c ) != coeffs_ . end ( ) )
        p = pop_c ( c ) ;
      else
        p = pop ( c ) ;

      if ( p )
        ++ period_len ;
      else
        period_len = 0 ;
    }
  }

  bool dio :: pop_c ( coeff c )
  {
    precomp_ . push_back ( sol ( c ) ) ;
    return true ;
  }

  bool dio :: pop ( coeff c )
  {
    sol solution ;
    for
    (
      coeff_map_citr i_c = coeffs_ . begin ( ) ;
      i_c != coeffs_ . end ( ) ; ++ i_c
    )
    {
      coeff c_cand = ( * i_c ) . first ;

      if ( c_cand >= c ) continue ;

      sol s_cand
        ( precomp_ . at ( c - c_cand ) , c_cand ) ;

      if ( s_cand < solution )
        solution = s_cand ;
      else
        if ( s_cand == solution )
          solution . add ( s_cand ) ;
    }

    precomp_ . push_back ( solution ) ;

    return
      ( ! solution . is_sol ( ) ) ||
      ( solution . has ( max_coeff_ ) ) ;
  }

  dio :: sol :: sol ( coeff c )
    : is_sol_ ( true ) , eff_ ( 1 )
  {
    coeff_map solution ;
    solution [ c ] = 1 ;
    s_ . push_back ( solution ) ;
  }

  dio :: sol :: sol ( const sol & s , coeff c , coeff i )
    : is_sol_ ( s . is_sol ( ) ) , eff_ ( s . eff ( ) + i )
  {
    const sol_vec sols = s . s_ref ( ) ;
    for
    (
      sol_vec_citr i_sol = sols . begin ( ) ;
      i_sol != sols . end ( ) ; ++ i_sol
    )
    {
      coeff_map solution = ( * i_sol ) ;
      solution [ c ] += i ;
      s_ . push_back ( solution ) ;
    }
  }

  bool dio :: sol :: has ( coeff c ) const
  {
    if ( ! is_sol_ ) return false ;

    for
    (
      sol_vec_citr i_sol = s_ . begin ( ) ;
      i_sol != s_ . end ( ) ; ++ i_sol
    )
    {
      const coeff_map & sol = ( * i_sol ) ;
      if ( sol . find ( c ) == sol . end ( ) )
        return false ;
    }

    return true ;
  }

  bool dio :: sol :: has ( const coeff_map & sol ) const
  {
    for
    (
      sol_vec_citr i_sol = s_ . begin ( ) ;
      i_sol != s_ . end ( ) ; ++ i_sol
    )
      if ( sol == * i_sol ) return true ;

    return false ;
  }

  void dio :: sol :: add ( const sol & s )
  {
    const sol_vec sols = s . s_ref ( ) ;
    for
    (
      sol_vec_citr i_sol = sols . begin ( ) ;
      i_sol != sols . end ( ) ; ++ i_sol
    )
      if ( ! has ( * i_sol ) )
        s_ . push_back ( * i_sol ) ;
  }
} ;

int main ( int argc , char * argv [ ] )
{
  assert ( argc > 3 ) ;

  xyz :: dio :: coeff sum_from ;
  xyz :: dio :: coeff sum_to ;

  std :: string s_from ( argv [ 1 ] ) ;
  std :: string s_to ( argv [ 2 ] ) ;
  std :: istringstream iss_from ( s_from ) ;
  std :: istringstream iss_to ( s_to ) ;

  iss_from >> sum_from ;
  iss_to >> sum_to ;

  assert ( sum_from > 0 ) ;
  assert ( sum_to > 0 ) ;
  assert ( sum_to >= sum_from ) ;

  xyz :: dio :: coeff_vec stamps ;

  for ( xyz :: dio :: coeff i = 3 ; i != argc ; ++ i )
  {
    xyz :: dio :: coeff c ;

    std :: string s_c ( argv [ i ] ) ;
    std :: istringstream iss_c ( s_c ) ;

    iss_c >> c ;

    assert ( c > 0 ) ;

    stamps . push_back ( c ) ;
  }

  xyz :: dio d ( stamps ) ;

  d . init ( ) ;

  for
  (
    xyz :: dio :: coeff sum = sum_from ;
    sum != sum_to + 1 ; ++ sum
  )
  {
    xyz :: dio :: sol solutions = d . solve ( sum ) ;

    std :: cout << sum << std :: endl ;
    std :: cout << "--------------------------------"
      << std :: endl ;
    xyz :: dio :: sol_vec s = solutions . s_ref ( ) ;
    std :: cout << "eff:" << solutions . eff ( ) << " sol:"
      << ( solutions . is_sol ( ) ? "yes" : "no" )
      << std :: endl ;
    for
    (
      xyz :: dio :: sol_vec_citr is = s . begin ( ) ;
      is != s . end ( ) ; ++ is
    )
    {
      for
      (
        xyz :: dio :: coeff_map_citr ic =
          ( * is ) . begin ( ) ;
        ic != ( * is ) . end ( ) ; ++ ic
      )
        std :: cout << " + " << ( * ic ) . first << " x "
          << ( * ic ) . second ;
      std :: cout << std :: endl ;
    }
    std :: cout << "================================"
      << std :: endl ;
  }
}

Trading off memory footprint for speed. If it does work,
it's probably the best algorithm overall unless some alpha
geek from sci.math can come up with something even better
that would be way beyond my understanding.

Test run excerpt:

pavel@debian:~/dev/cxx/t16$ time ./a.out 10000000 10000040 3 5 112
1113 10001 96732
10000000
--------------------------------
eff:126 sol:yes
 + 3 x 1 + 5 x 5 + 112 x 9 + 1113 x 5 + 10001 x 3 + 96732 x 103
================================
....
10000040
--------------------------------
eff:124 sol:yes
 + 3 x 3 + 5 x 3 + 1113 x 3 + 10001 x 13 + 96732 x 102
================================

real 0m7.761s
user 0m7.448s
sys 0m0.104s

--
Pavel Lepin