Herhangi Matematiksel Şeyler: Euler Projesi 259. Soru

Erişilebilir Sayılar

Aşağıdaki kurallara uygun olarak bir aritmetik işlem sonucu elde edilebilen pozitif bir tam sayı erişilebilir olarak adlandırılır:

1'den 9'a kadar olan rakamları bu sırayla ve her birini sadece birer kez kullanır.
Ardışık herhangi sayıdaki rakamlar birleştirilebilir (örneğin 2, 3 ve 4 rakamlarını kullanarak 234 sayısını elde edebiliriz).
Yalnızca dört ikili aritmetik işleme (toplama, çıkarma, çarpma ve bölme) izin verilir.
Her işlem herhangi sayıda kullanılabilir veya hiç kullanılmaz.
Tekil eksi kullanılamaz.
İşlemlerin sırasını tanımlamak için herhangi sayıda (muhtemelen yuvalanmış) parantez kullanılabilir.

Örneğin 42 sayısı ulaşılabilirdir, çünkü $$(1/23) * ((4 * 5) - 6) * (78-9) = 42.$$
Tüm pozitif erişilebilir tam sayıların toplamı nedir?
Çözüm: 20101196798

Python:
import fractions

def gen(m, n):
    x = m
    r = set()
    for i in range(m + 1, n):
        for a in cache[(m, i)]:
            for b in cache[(i, n)]:
                r.add(a + b)
                r.add(a - b)
                r.add(a * b)
                if b:
                    if isinstance(a, int) and isinstance(b, int) and a % b == 0:
                        r.add(a // b)
                    else:
                        r.add(fractions.Fraction(a, b))
        x = x * 10 + i
    r.add(x)
    return r

nmax = 10

cache = {}
for l in range(1, nmax + 1):
    for i in range(1, nmax - l + 1):
        cache[(i, i + l)] = gen(i, i + l)

s = sum(x for x in cache[(1, nmax)]
        if x > 0 and (isinstance(x, int) or x.denominator == 1))
print(s)

C/C++:
#include<iostream>
#include<vector>
#include<set>
#include<cmath>

using namespace std;

typedef long long Int;
typedef long double ld;

#define REP(i, n) for(int i=0;i<n;i++)
#define FOR(it, c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)

const ld EPS=1e-13;

pair<bool, Int> is_int(ld val){
  ld v2=floor(val+EPS);
  Int ret=(Int)(val+EPS);
  if(abs(v2-val)<EPS){
    ret-=2;
    while(true){
      if(abs(v2-ret)<EPS){
        break;
      }
      ret++;
    }
    return make_pair(true, ret);
  }else return make_pair(false, -1);
}

void setv(vector<int> &v, int k){
  Int tmp=0;
  REP(i, 9){
    tmp+=(i+1);
    if(i<9){
      if(k%2==1){
        v.push_back(tmp);
        tmp=0;
      }else{
        tmp*=10;
      }
    }
    k/=2;
  }
}

vector<int> v;

const int SIZE=10;

set<ld> st[SIZE][SIZE];
bool finded[SIZE][SIZE];
set<int> result;

void findout(int i, int j){
  assert(i+1<=j);
  set<ld> &ref=st[i][j];
  if(finded[i][j])return;
  if(i+1==j){
    ref.insert(v[i]);
  }else{
    for(int k=i+1;k<=j-1;k++){
      findout(i, k);findout(k, j);
      FOR(i1, st[i][k])FOR(i2, st[k][j]){
        ref.insert(*i1+*i2);
        ref.insert(*i1-*i2);
        ref.insert((*i1)*(*i2));
        if(abs(*i2)>EPS){
          ref.insert((*i1)/(*i2));
        }
      }
    }
  }
/*  cout<<"now find: "<<i<<" "<<j<<endl;
  FOR(i1, ref){
    cout<<*i1<<" ";
  }
  cout<<endl;
 */ 
  finded[i][j]=true;
  return;
}

void calc(){
  REP(i, SIZE)REP(j, SIZE){ st[i][j].clear();finded[i][j]=false;}
  cout<<v.size()<<endl;
  findout(0, v.size());
}

int main(){
  for(int i=0;i<256;i++){
    cout<<i<<endl;
    int k=i+256;
    v.clear();
    setv(v, k);
    REP(j, v.size()){
      cout<<v[j]<<" ";
    }
    cout<<endl;
    calc();
    set<ld> &ref=st[0][v.size()];
    FOR(it, ref){
      pair<bool, Int> p=is_int(*it);
      if(p.first and p.second>0){
        if(result.find(p.second)==result.end()){
          result.insert(p.second);
        }
      }
    }
  }
  Int sum=0;
  FOR(it, result){
    sum+=*it;
  }
  cout<<sum<<endl;
  return 0;
}

Haskell:
import Data.Ratio
import Data.Maybe
import Data.Array
import qualified Data.Set as S

data Expression = Leaf Rational | Tree Operator Expression Expression deriving Show
data Operator   = Add | Sub | Mul | Div deriving (Show, Enum)

generate l u = Leaf v :
    do k <- [l..u-1]
       o <- enumFrom Add
       l <- generate l k
       r <- generate (k+1) u
       return $ Tree o l r
    where v = foldl (\a b -> 10*a + b) 0 [l..u]

maybe' f (Just a) (Just b) = Just $ f a b
maybe' _ _ _ = Nothing

eval (Leaf a)       = Just a
eval (Tree Add a b) = maybe' (+) (eval a) (eval b)
eval (Tree Sub a b) = maybe' (-) (eval a) (eval b)
eval (Tree Mul a b) = maybe' (*) (eval a) (eval b)
eval (Tree Div a b)
    | eval b == Just 0 = Nothing
    | otherwise        = maybe' (/) (eval a) (eval b)

valid x = denominator x == 1 && x > 0

main = print.S.fold (+) 0.S.fromList.map numerator.filter valid.mapMaybe eval $ generate 1 9

ml:
let rec gcd a b=if b=0. then a else gcd b (mod_float a b)
let canon (a, b) = let m = gcd a b in a /. m, b /. m

let add (a,b) (c,d)= canon ( a *. d +. c *. b, b *. d)
let sub (a,b) (c,d)= canon ( a *. d -. c *. b, b *. d)
let mul (a,b) (c,d)= canon ( a *. c,           b *. d)
let div (a,b) (c,d)= mul (a, b) (d, c)

let cmp (a,b) (c,d)= compare (a *. d) (b *. c)

module FracSet = Set.Make (struct type t=float * float let compare=cmp end)

let prt acc =
    List.iter (fun i->Printf.printf "%d " i) acc; print_newline()

let main () =
    let rec merge set set1 set2 =
        FracSet.fold (fun f1 acc1->
            FracSet.fold (fun f2 acc2->
                List.fold_left (fun acc3 f3->
                    try FracSet.add (f3 f1 f2) acc3 with Division_by_zero -> acc3
                ) acc2 [add; sub; mul; div]
            ) set2 acc1
        ) set1 set

and proc2 set lis1 lis2 =
        let s1 = proc FracSet.empty lis1 in
        let s2 = proc FracSet.empty lis2 in
        merge set s1 s2

and proc1 set lis1 lis2 = match lis2 with
        | hd :: tl -> let set = proc2 set lis1 lis2 in
                                proc1 set (lis1 @ [ hd ]) tl
        | []       -> set

and proc set = function
        | hd :: [] -> FracSet.add (hd, 1.) set
        | hd :: tl -> proc1 set [ hd ] tl
        | []       -> set in

let rec loop set n acc =
        if n = 10 then
            let _ = prt (List.rev acc) in
            proc set (List.rev_map float acc) else match acc with
        | []       -> set
        | hd :: tl -> let set = loop set (n+1) (n       :: acc) in
                                loop set (n+1) (hd*10+n :: tl) in
    loop FracSet.empty 2 [ 1 ]
;;
let set = main () in
Printf.printf "Answer: %.f\n" (FracSet.fold (fun (a, b) c->let a = if b < 0. then -.a else a in
                    if a > 0. && b = 1. then c +. a else c) set 0.)

Lisp:
(defun op-list (list mask op)
  "mask is an integer acting as a bit mask where the list needs concatenating"
  (loop with cur = (car list)
       for x in (cdr list)
       for m = mask then (floor m 2)
       for r = (mod m 2)
       ;;do (format t "x=~d m=~d r=~d~%" x m r)
       when (= r 1) do (setf cur (funcall op cur x))
       else collect cur into newlist and do (setf cur x)
       finally (return (nconc newlist (list cur))))) 
       
(defun posint (n)
  (and (integerp n) (> n 0)))

(defun euler-259 ()
  (let ((list0 (list 1 2 3 4 5 6 7 8 9))
        (reachables (make-hash-table))
        (oplist (list #'+ #'- #'*))
        (memo (make-hash-table :test #'equal)))
    (flet ((reg-num (n)
             (when (posint n)
               (setf (gethash n reachables) t))))
      (labels ((rec-eval (list)
                 (when (= (length list) 1) (return-from rec-eval list))
                 (loop with collection 
                    for div from 1 to (1- (length list))
                    for ll = (butlast list div) 
                    for rl = (last list div)
                    for left = (or (gethash ll memo)
                                   (rec-eval ll))
                    for right = (or (gethash rl memo)
                                    (rec-eval rl))
                    do (format t "list: ~a~a left: ~d, right: ~d, col: ~d~%" 
                               ll rl (length left) (length right) (length collection))
                       (finish-output)
                      (if (<= (length right) (length left))
                          (loop for rn in right
                             do (loop for op in oplist
                                   for reslist = (mapcar (lambda (ln) (funcall op ln rn)) left)
                                   do (setf collection (nconc collection reslist)))
                             unless (zerop rn)
                             do (setf collection 
                                      (nconc collection 
                                             (mapcar (lambda (ln) (/ ln rn)) left))))
                          (loop for ln in left
                             do (loop for op in oplist
                                   for reslist = (mapcar (lambda (rn) (funcall op ln rn)) right)
                                   do (setf collection (nconc collection reslist)))
                             do (loop for rn in right
                                     unless (zerop rn) collect (/ ln rn) into lst
                                     finally (setf collection (nconc collection lst)))))
                    finally (return (if (< (length list) 8) 
                                        (setf (gethash list memo)
                                              (delete-duplicates collection))
                                        collection ;;(delete-duplicates collection)
                                        )))))
      (loop for mask from 0 to (1- (expt 2 8))
         for list = (op-list list0 mask (lambda (cur x) (+ (* 10 cur) x)))
         for l = (length list)
         do (print list) (finish-output)
         if (= l 1) do (reg-num (car list))
         else do
           (loop for n in (rec-eval list) do (reg-num n)))
      reachables))))

(defun calc-hash-sum (hash)
  (loop for k being each hash-key of hash
       summing k))

Java:
//Literal.java
package problem259;

public class Literal {
    public boolean num;
}

//Broj.java
package problem259;

public class Broj extends Literal{
    public int br;
    public Broj(int broj) {
        num = true;
        br = broj;
    }
    long getBr() {return br;}
    double getDouble() {return (double) br;}
}

//Op.java
package problem259;

public class Op extends Literal{
    private int op;
    public Op(char c) {
        num = false;
        switch (c) {
            case '+': op = 1; break;
            case '-': op = 2; break;
            case '*': op = 3; break;
            case '/': op = 4; break;
        }
    }
    public Op(int op) {this.op = op;}
    public int getOp() {return op;}
}

//Main.java
package problem259;

import java.util.BitSet;
import java.util.Stack;
import java.util.Vector;

public class Main {
    private static long result = 0;
    private static BitSet reachable = new BitSet(111111103);
    
    private static double vrednost(Vector<Literal> v) {
        Stack<double> st = new Stack<double>();
        for (Literal lit : v) {
            if (lit.num) st.push(((Broj)lit).getDouble());
            else {
                double op2 = st.pop();
                double op1 = st.pop();
                switch (((Op)lit).getOp()) {
                    case 1: st.push(op1 + op2); break;
                    case 2: st.push(op1 - op2); break;
                    case 3: st.push(op1 * op2); break;
                    case 4: st.push(op1 / op2); break;
                }
            }
        }
        double rez = st.pop();
        if (!st.empty()) System.out.println("Nepravilan izraz");
        return rez;
    }

private static void makePostFix(Vector<literal> v, Vector<literal> post, int brojeva, int operacija, int poz) {
        if (poz==v.size() && operacija==brojeva-1) {
            if (!post.lastElement().num) {
                double val=vrednost(post);
                if (Math.abs(val-(int)Math.round(val))<0.00000001&&val>0&&!reachable.get((int)Math.round(val))) {
                    reachable.set((int) Math.round(val));
                    result+=Math.round(val);
                }
            }
        }
        else {
            if (brojeva-1>operacija) {
                Vector<literal> pp = new Vector<literal>(post), pom = new Vector<literal>(post);
                pp.add(new Op(1));
                makePostFix(v, pp, new Integer(brojeva), new Integer(operacija+1), new Integer(poz));
                pp = new Vector<literal>(pom);
                pp.add(new Op(2));
                makePostFix(v, pp, new Integer(brojeva), new Integer(operacija+1), new Integer(poz));
                pp = new Vector<literal>(pom);
                pp.add(new Op(3));
                makePostFix(v, pp, new Integer(brojeva), new Integer(operacija+1), new Integer(poz));
                pp = new Vector<literal>(pom);
                pp.add(new Op(4));
                makePostFix(v, pp, new Integer(brojeva), new Integer(operacija+1), new Integer(poz));
                post = new Vector<literal>(pom);
            }
            if (poz<v.size()) {
                Vector<literal> pp = new Vector<literal>(post);
                pp.add(v.get(poz));
                makePostFix(v, pp, new Integer(brojeva+1), new Integer(operacija), new Integer(poz+1));
            }
        }
    }

private static void rek(Vector<integer> v, int koliko, int tar, int posl) {
        if (tar==koliko) {
            if (v.size()!=koliko) System.out.println("Greska");
            int pom=posl;
            for (int i=posl+1;i<=9;i++) {
                pom*=10; pom+=i;
            }
            v.add(pom);
            Vector<literal> vvv = new Vector<literal>();
            for (int br:v) vvv.add(new Broj(br));
            Vector<literal> pp = new Vector<literal>();
            pp.add(new Broj(v.get(0))); pp.add(new Broj(v.get(1)));
            makePostFix(vvv, pp, 2, 0, 2);
        }
        else {
            for (int i=posl;i<=9-koliko+tar;i++) {
                int pom=posl;
                int j;
                for (j=posl+1;j<=i;j++) {
                    pom*=10; pom+=j;
                }
                Vector<integer> novi = new Vector<integer>(v);
                novi.add(pom);
                rek (novi, koliko, new Integer(tar+1), new Integer(j));
            }
        }
    }

public static void main(String[] args) {
        for (int i=1;i<9;i++){
            System.out.println(i);
            rek (new Vector<integer>(), i, 0, 1);
        }
        System.out.println(result+123456789);
    }
}

Herhangi Matematiksel Şeyler

Sayfalar

14 Şubat 2019

Euler Projesi 259. Soru