Project Euler 254

/**
 * Copyright uwi ( http://wonderfl.net/user/uwi )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/sDkG
 */

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    import flash.events.*;
    import com.bit101.components.*;
    // @see http://projecteuler.net/index.php?section=problems&id=254
    // nの桁の順序を変えてもf(n)は変わらないのでnの桁を昇順にすれば同じ桁数では最小になる。
    // するとsg(i)の候補はn=1…12…2……9…9 という形になる。
    // ただしk(1,…,8)の桁数はk個以下。
    // それより大きい場合は次の数に吸収したほうが小さくなる。
    // この方法で、f(n)からnが一意に構成できる。
    // 
    // 一方、sf(n)=150となると、f(n)は17桁以上になるので、f(n)のしらみつぶしでは不可。
    // 各iについて、まず各桁の和がiとなる最小の数mを構成する。
    // sf(m)=iなので、m=f(n')となるn'が決まるが、
    // これより小さいnの9の個数は、n'の桁数より小さいので、
    // そこまでmをインクリメントしてsf(m)=i, m=f(n)をみたす最小のnを探せばよい。
    // 最小のn=g(i)が求まったらその各桁の和を出せばそれがsg(i)となる。
    public class Euler254 extends Sprite {
        private var _tf : TextField;
  
        public function Euler254() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var pb : PushButton = new PushButton(this, 350, 10);
            pb.label = "stop";
            pb.width = 100;
            pb.addEventListener(MouseEvent.CLICK, function(e : MouseEvent) : void
            {
                removeEventListener(Event.ENTER_FRAME, onEnterFrame);
            });
            
            _s = getTimer();
            solve(150);
            tr((getTimer() - _s) + " ms");
        }
        
        private var _s : int;
        private var lens : Array;
        private var ords : Array;
        private var sfs : Array;
        private var N : int;

        private function solve(N : int) : void
        {
            this.N = N;
            lens = new Array(362880);
            ords = new Array(362880);
            sfs = new Array(362880);
            var i : int, j : int, k : int;
            var ct : Array = [0, 0, 0, 0, 0, 0, 0, 0, 0];
            for(i = 0;i < 362880;i++){
                var len : int = 0;
                var ord : int = 0;
                var sf : int = 0;
                for(j = 1;j <= 8;j++){
                    len += ct[j];
                    ord = ord * 10 + ct[j];
                    sf += ct[j] * j;
                }
                lens[i] = len;
                ords[i] = ord;
                sfs[i] = sf;
                
                // inc
                ct[1]++;
                for(j = 1;j <= 8;j++){
                    if(ct[j] > j){
                        ct[j + 1]++;
                        ct[j] -= (j + 1);
                    }else{
                        break;
                    }
                }
            }

            ii = 1;
            ret = 0;
            base = "";       
            addEventListener(Event.ENTER_FRAME, onEnterFrame);
        }
        
        private var ii : int;
        private var ret : Number;
        private var base : String;
        
        private function onEnterFrame(e : Event) : void
        {
            if(ii % 9 == 0)base += "9";
            var lmin : MPI = new MPI((ii % 9) + base);
            var d : Array = MPI.divint(lmin, 362880);
            var minlen : Number = lens[d[1]] + d[0];
            
            var v : MPI = new MPI(lmin);
            var dsum : int = ii;
            var n9inf : Number = d[0];
            var sg : Number = 0;
            var re : MPI = new MPI(0);
            
            var i : int, len : Number, sf : Number;
            var ordd : int = 0;
            for(var n9 : Number = n9inf;n9 < minlen;n9++){
                for(i = n9 == n9inf ? d[1] : 0;i < 362880;i++){
                    if(dsum == ii){
                        len = lens[i] + n9;
                        sf = sfs[i] + 9 * n9;
                        if(len < minlen || (len == minlen && (ordd == 0 || ordd < ords[i]))){
                           ordd = ords[i];
                           minlen = len;
                           sg = sfs[i] + 9 * n9;
                           re = new MPI(v);
                       }
                    }
                    v.inc();
//                        v.addint_(1);
                    dsum -= 9 * v.nLast0();
                    dsum++;
                }
            }
            
            if(dsum == ii){
                len = lens[i] + n9;
                sf = sfs[i] + 9 * n9;
                if(len < minlen || (len == minlen && (ordd == 0 || ordd < ords[i]))){
                   ordd = ords[i];
                   minlen = len;
                   sg = sfs[i] + 9 * n9;
                   re = new MPI(v);
               }
            }
            
            tr(ii, minlen, sg, re, lmin);
            ret += sg;

            if(ii == N){
                tr("solved!");
                tr(ret);
                tr((getTimer() - _s) + " ms");
                removeEventListener(Event.ENTER_FRAME, onEnterFrame);
            }
            ii++;
        }

        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
            _tf.scrollV = _tf.maxScrollV;
        }
    }
}
/*
            var ret : Number = 0;
            for(var ii : int = 1;ii <= N;ii++){
                var lmin : Number = Math.pow(10, int(ii / 9)) * ((ii % 9) + 1) - 1;
                var minlen : Number = lens[lmin % 362880] + Math.floor(lmin / 362880);
                
                var v : Number = lmin;
                var dsum : int = ii;
                var n9inf : Number = Math.floor(v / 362880);
                var sg : Number = 0;
                var re : Number = 0;
                
                var ordd : int = 0;
                for(var n9 : Number = n9inf;n9 < minlen;n9++){
                    for(i = n9 == n9inf ? v % 362880 : 0;i < 362880;i++){
                        if(dsum == ii){
                            len = lens[i] + n9;
                            sf = sfs[i] + 9 * n9;
                            if(len < minlen || (len == minlen && (ordd == 0 || ordd < ords[i]))){
                               ordd = ords[i];
                               minlen = len;
                               sg = sfs[i] + 9 * n9;
                               re = 
                           }
                        }
                        v++;
                        for(j = 10;v % j == 0;j *= 10, dsum -= 9);
                        dsum++;
                    }
                }
                
                if(dsum == ii){
                    len = lens[i] + n9;
                    sf = sfs[i] + 9 * n9;
                    if(len < minlen || (len == minlen && (ordd == 0 || ordd < ords[i]))){
                       ordd = ords[i];
                       minlen = len;
                       sg = sfs[i] + 9 * n9;
                       re = v;
                   }
                }
                
                tr(ii, minlen, sg, re, lmin);
                ret += sg;
            }
*/

class MPI
{
    public var d : Vector.<uint>;
    
    public function MPI(v : * = 0)
    {
        if(v is Number){
            d = Vector.<uint>([]);
            for(var n : Number = v;n != 0;n = Math.floor(n / 10))d.push(n % 10);
            if(v == 0)d.push(0);
        }else if(v is String){
            d = Vector.<uint>([]);
            for(var i : int = v.length - 1;i >= 0;i--){
                d.push(uint(v.charAt(i)));
            }
        }else if(v is Array){
            d = Vector.<uint>(v);
        }else if(v is Vector.<uint>){
            d = v.concat();
        }else if(v is MPI){
            d = v.d.concat();
        }
        if(d)shave();
    }
    
    public static function add(a : MPI, b : MPI) : MPI
    {
        var ret : MPI = new MPI(a);
        var i : int;
        var minl : int = Math.min(ret.d.length, b.d.length);
        for(i = 0;i < minl;i++){
            ret.d[i] += b.d[i];
        }
        for(i = ret.d.length;i < b.d.length;i++){
            ret.d.push(b.d[i]);
        }
        ret.carry();
        return ret;
    }
    
    public static function addint(a : MPI, b : int) : MPI
    {
        var ret : MPI = new MPI(a);
        ret.d[0] += b;
        ret.carry();
        return ret;
    }
    
    public function addint_(b : int) : MPI
    {
        this.d[0] += b;
        this.carry();
        return this;
    }
    
    public function inc() : void
    {
        d[0]++;
        for(var i : int = 0;i < d.length;i++){
            if(d[i] >= 10){
                var c : uint = d[i] / 10;
                if(i == d.length - 1){
                    d.push(0);
                }
                d[i + 1] += c;
                d[i] %= 10;
            }else{
                break;
            }
        }
    }
    
    public static function sub(a: MPI, b : MPI) : MPI
    {
        if(comp(a, b) < 0){
            var m : MPI = a; a = b; b = m;
        }
        // a - b
        var ret : MPI = new MPI(a);
        var i : int;
        for(i = 0;i < b.d.length;i++){
            ret.d[i] -= b.d[i];
        }
        
        ret.minuscarry();
        return ret;
    }
    
    public static function subint(a : MPI, b : int) : MPI
    {
        var ret : MPI = new MPI(a);
        ret.d[0] -= b;
        ret.minuscarry();
        return ret;
    }
    
    public function subint_(b : int) : MPI
    {
        this.d[0] -= b;
        this.minuscarry();
        return this;
    }
    
    public static function comp(a : MPI, b : MPI) : int
    {
        if(a.d.length != b.d.length)return a.d.length - b.d.length;
        for(var i : int = a.d.length - 1;i >= 0;i--){
            if(a.d[i] != b.d[i]){
                return a.d[i] - b.d[i];
            }
        }
        return 0;
    }
    
    public static function mul(a : MPI, b : MPI) : MPI
    {
        var retv : Vector.<uint> = new Vector.<uint>(a.d.length + b.d.length);
        var i : int, j : int;
        for(i = 0;i < retv.length;i++)retv[i] = 0;
        for(i = 0;i < a.d.length;i++){
            for(j = 0;j < b.d.length;j++){
                retv[i + j] += a.d[i] * b.d[j];
            }
        }
        var ret : MPI = new MPI(retv);
        ret.carry();
        ret.shave();
        return ret;
    }
    
    public static function mulint(a : MPI, b : int) : MPI
    {
        var ret : MPI = new MPI(a);
        for(var i : int = 0;i < ret.d.length;i++){
            ret.d[i] *= b;
        }
        ret.carry();
        return ret;
    }
    
    public function mulint_(b : int) : MPI
    {
        for(var i : int = 0;i < d.length;i++){
            this.d[i] *= b;
        }
        this.carry();
        return this;
    }
    
    public static function div(a : MPI, b : MPI) : Array
    {
        var bm : Array = new Array(10);
        var i : int, j : int;
        for(i = 1;i <= 9;i++)bm[i] = mulint(b, i);
        
        var retr : Vector.<uint> = Vector.<uint>([]);
        var m : MPI = new MPI(0);
        for(i = a.d.length - 1;i >= 0;i--){
            m = addint(mulint(m, 10), a.d[i]);
            for(j = 1;j <= 9;j++){
                if(comp(m, bm[j]) < 0)break;
            }
            retr.push(j - 1);
            if(j >= 2)m = sub(m, bm[j - 1]);
        }
        
        var ret : MPI = new MPI(retr.reverse());
        ret.shave();
        m.shave();
        return [ret, m];
    }
    
    public static function divint(a : MPI, b : int) : Array
    {
        var i : int;
        
        var retr : Vector.<uint> = Vector.<uint>([]);
        var m : int = 0;
        for(i = a.d.length - 1;i >= 0;i--){
            m = m * 10 + a.d[i];
            var dv : int = m / b;
            retr.push(dv);
            m %= b;
        }
        
        var ret : MPI = new MPI(retr.reverse());
        ret.shave();
        return [ret, m];
    }
    
    public function nLast0() : int
    {
        for(var i : int = 0;i < d.length && d[i] == 0;i++);
        return i;
    }
    
    // 位上げ
    public function carry() : void
    {
        for(var i : int = 0;i < d.length;i++){
            if(d[i] >= 10){
                var c : uint = d[i] / 10;
                if(i == d.length - 1){
                    d.push(0);
                }
                d[i + 1] += c;
                d[i] %= 10;
            }
        }
    }
    
    // 位下げ
    public function minuscarry() : void
    {
        for(var i : int = 0;i < d.length;i++){
            if(d[i] <= 2147483648)continue; // やっつけ
            var v : int = d[i] - 4294967296;
            var c : int = (-v + 9) / 10;
            d[i + 1] -= c;
            d[i] += 10 * c;
        }
        shave();
    }
    
    // 上位の桁から0を削る
    public function shave() : void
    {
        for(var i : int = d.length - 1;i >= 1;i--){
            if(d[i] > 0)break;
            d.pop();
        }
    }
    
    public function toString() : String
    {
        return d.concat().reverse().join('');
    } 
}