# allint.R, 5 Apr 12 # # Enumerate all values generated by expressions # containing a given number of operators having # operand values between 1 and 9. PLUS=1 MINUS=2 TIMES=3 DIVIDE=4 EXPON=5 operators=c(PLUS, MINUS, TIMES , DIVIDE # , EXPON ) num_samples=0 prev_mean=0 cur_mean=0 prev_accum_var=0 cur_accum_var=0 # Calculate a running mean and standard deviation for # all calculated values running_m_s=function(vals) { #for (i in vals) # { # num_samples <<- num_samples+1 # prev_mean <<- cur_mean # cur_mean <<- prev_mean+(i-prev_mean)/num_samples # prev_accum_var <<- cur_accum_var # cur_accum_var <<- prev_accum_var+(i-prev_mean)*(i-cur_mean) # } } init_m_s=function() { num_samples <<- 0 cur_mean <<- 0 cur_accum_var <<- 0 } print_m_s=function() { #print(paste(cur_mean, sqrt(cur_accum_var/(num_samples-1)))) } do_op=function(op1, op2, operator) { if (operator == PLUS) { res=op1+op2 running_m_s(res) return(unique(res)) } if (operator == MINUS) { res=op1-op2 running_m_s(res) return(unique(res)) } if (operator == TIMES) { res=op1*op2 running_m_s(res) return(unique(res)) } if (operator == DIVIDE) { res=op1/op2 res=as.integer(res[op1 %% op2 == 0]) res=res[!is.na(res)] running_m_s(res) return(unique(res)) } if (operator == EXPON) { res=op1^op2 return(unique(res[res < 200000])) } } eval_op=function(op1, op2, operator) { l_op1=length(op1) l_op2=length(op2) if (l_op1 < l_op2) return(do_op(op1, sort(rep(op2, l_op1)), operator)) else return(do_op(sort(rep(op1, l_op2)), op2, operator)) } apply_all_ops=function(op1, op2) { result=c() for (i_op in operators) result=unique(c(result, eval_op(op1, op2, i_op))) return(result) } missing_val=function(val_list) { for (i in 1:length(val_list)) if (val_list[i] != i) return(i) } list_info=function(val_list) { pos_list=val_list[val_list >= 0] print(paste(length(val_list), length(pos_list), missing_val(val_list[val_list > 0]))) } all_lists=function() { list_info(all_1) list_info(all_2) list_info(all_3) list_info(all_4) list_info(all_5) list_info(all_6) list_info(all_7) } all_0=(1:9) init_m_s() all_1=sort(unique(apply_all_ops(all_0, all_0))) print_m_s() init_m_s() all_2=sort(unique(c( apply_all_ops(all_1, all_0), apply_all_ops(all_0, all_1)))) print_m_s() init_m_s() all_3=sort(unique(c( apply_all_ops(all_1, all_1), apply_all_ops(all_0, all_2), apply_all_ops(all_2, all_0)))) print_m_s() init_m_s() all_4=sort(unique(c( apply_all_ops(all_1, all_2), apply_all_ops(all_2, all_1), apply_all_ops(all_0, all_3), apply_all_ops(all_3, all_0)))) print_m_s() init_m_s() all_5=sort(unique(c( apply_all_ops(all_2, all_2), apply_all_ops(all_1, all_3), apply_all_ops(all_3, all_1), apply_all_ops(all_0, all_4), apply_all_ops(all_4, all_0)))) print_m_s() init_m_s() all_6=sort(unique(c( apply_all_ops(all_2, all_3), apply_all_ops(all_3, all_2), apply_all_ops(all_1, all_4), apply_all_ops(all_4, all_1), apply_all_ops(all_0, all_5), apply_all_ops(all_5, all_0)))) print_m_s() init_m_s() all_7=sort(unique(c( apply_all_ops(all_3, all_3), apply_all_ops(all_2, all_4), apply_all_ops(all_4, all_2), apply_all_ops(all_1, all_5), apply_all_ops(all_5, all_1), apply_all_ops(all_0, all_6), apply_all_ops(all_6, all_0)))) print_m_s() all_lists() png(file="small-mis-heat.png") hm_len=100*100 hv=vector(length=hm_len) hv=c(0) hv[all_6[all_6 > 0 & all_6 <= hm_len]]=6 hv[all_5[all_5 > 0 & all_5 <= hm_len]]=5 hv[all_4[all_4 > 0 & all_4 <= hm_len]]=4 hv[all_3[all_3 > 0 & all_3 <= hm_len]]=3 hv[all_2[all_2 > 0 & all_2 <= hm_len]]=2 hv[all_1[all_1 > 0 & all_1 <= hm_len]]=1 hm=matrix(data=hv, nrow=100, ncol=100) image(hm, col=rainbow(7), axes=FALSE) lab=c(1, seq(10, 100, by=10)) axis(1, label=lab, at=seq(0, 1, by=0.1)) axis(2, label=lab, at=seq(0, 1, by=0.1)) dev.off() fract=c(9, 93, 931, 11644, 126436, 1443224) all_int=c(9, 48, 236, 1274, 6489, 30229, 142320, 711955) pos_int=c(9, 40, 156, 740, 3668, 16948, 77861, 379034) all_smallest=c(10, 19, 92, 417, 851, 4237, 14771, 73237) plus_times=c(9, 39, 155, 689, 3099, 13561, 60654, 281249) pt_smallest=c(10, 19, 92, 239, 829, 2831, 10061, 38231) every_mean=c(5, 10.9172932330827, 41.7525846702318, 147.510180671063, 474.616693803143, 1570.80489222798, 5729.37942989558, 22131.2047168279) # Mean and standard deviation # 10.9172932330827 15.0621580617106 # 41.7525846702318 91.0858538543869 # 147.510180671063 507.587155699881 # 474.616693803143 2633.77987453846 # 1570.80489222798 13436.3708023783 # 5729.37942989558 69505.5330350386 # 22131.2047168279 362430.240896781 max_val=max(fract) png(file="uniq-val-per-op.png") par(las=1) par(pch=21) par(type="b") plot(c(1:6), fract, col="blue", type="b", xaxt="n", yaxt="n", log="y", xlim=c(1,8), ylim=c(6,max_val), xlab="Number of operators", ylab="Unique") x_l=seq(0, 7) axis(1, label=x_l, at=seq(1, 8)) y_l=c(1, 10, 100, 1000, 10000, 100000, 1000000) axis(2, label=y_l, at=y_l) plot_next=function(y_vals, clr) { par(new=TRUE) plot(c(1:8), y_vals, col=clr, type="b", xaxt="n", yaxt="n", log="y", xlim=c(1,8), ylim=c(6,max_val), xlab="", ylab="") } plot_next(all_int, "black") plot_next(pos_int, "red") plot_next(all_smallest, "green") par(pch=22) plot_next(plus_times, "red") plot_next(pt_smallest, "green") par(pch=23) plot_next(every_mean, "blue") dev.off()