Very Nice Friedman Numbers
Perl, 345 334 318 293 263 245B
$_='$_=$i=pop;$c=y///c-1;sub f{say if$c&&$i==eval pop=~s/\^/**/gr}A$m)$1$4"})};f"("x$c.$m}globOx$c.$i;A$1$4($m"})};f$m.")"x$c}glob$i.Ox$c;map{f$_}glob joinO,/./g';s!O!"{+,-,*,/,^}"!g;s!A!'map{m{(\d)((?R)|(\d)(?{$m=$3}))(.)(?{$m="'!ge;s!d!D!;eval
Call with perl -M5.10.0 scratch.pl 736
Results
The first few results that I found are:
^+343
736^+
7+3^6
^+/3125
^+^3125
/^+-11664
/^--11664
1-1+6^6/4
/^++14641
^^++14641
1+5^6/1-8
1+5^6^1-8
1+5^6-2-2
1+5^6-2^2
1+5^6+2-4
1+5^6+4^2
-^+^16377
-^-+16377
/^+^16384
/^-+16384
Explanation
Fully ungolfed
I tried to repeat myself as much as possible to make the later golfing easier.
#!perl
use 5.10.0;
$_ = $input = pop;
# y///c counts characters in $_
$count = y///c - 1;
sub f {
say if $count && $input == eval pop =~ s/\^/**/gr
}
# PREFIX
map {
m{ # Parses *^+1234
(\D) # $1 = first symbol
(
(?R) # RECURSE
|
(\d)(?{ # $3 = first digit
$match=$3
})
)
(.)(?{ # $4 = last digit
$match="$match)$1$4"
})
}x;
f "(" x $count . $match
}
# glob expands '{0,1}{0,1}' into 00,01,10,11
glob "{+,-,*,/,^}" x $count . $input;
# POSTFIX
map {
m{(\d)((?R)|(\d)(?{$match=$3}))(.)(?{$match="$1$4($match"})};
f $match. ")" x $count
}
glob $input . "{+,-,*,/,^}" x $count;
# INFIX
# /./g splits $_ into characters
map { f $_} glob join "{+,-,*,/,^}", /./g
How it's golfed
- Remove whitespace & comments and replace all vars with 1-character version
- Wrap program in
$_=q! ... !;eval
- Extract strings and substitute them in afterwards.
This gives something like this, from which you can remove the line breaks for the result:
$_='
$_=$i=pop;
$c=y///c-1;
sub f{say if$c&&$i==eval pop=~s/\^/**/gr}
A$m)$1$4"})};f"("x$c.$m}globOx$c.$i;
A$1$4($m"})};f$m.")"x$c}glob$i.Ox$c;
map{f$_}glob joinO,/./g
';
s!O!"{+,-,*,/,^}"!g;
s!A!'map{m{(\d)((?R)|(\d)(?{$m=$3}))(.)(?{$m="'!ge;
s!d!D!;
eval
Ruby 2.1.5 only - 213 220 238 + 9 = 247
Not sure how Ruby beats Perl, but here you go...
Run this with a -rtimeout flag (and either -W0 or send your stderr elsewhere).
To make this slightly more robust, replace send([].methods[81],z-1)
with repeated_permutation(z-1)
and score an extra character (so, 248).
g=$*[0].split //
exit if 2>z=g.size
d=->a,s{$><<a*''&&exit if$*[0].to_i==timeout(2){eval"#{(s*'').gsub(?^,'**')}"}rescue p}
l,r=[?(]*z,[?)]*z
%w{* / + - ^}.send([].methods[81],z-1){|o|d[m=g.zip(o),m]
d[g+o,l.zip(m)+r]
d[o+g,l+g.zip(r,o)]}
Basically, go through all permutations of operators and try infix, postfix, and prefix in that order. The d
method uses eval
on the second parameter to perform the calculations, catching any DivideByZero or Overflow exceptions.
You need to send stderr to /dev/null, though, or else eval
will sometimes print warnings like (eval):1: warning: in a**b, b may be too big
.
While I came up with this ungolfing, I found a way to save three chars!
Ungolfed (outdated but similar principles):
input = $*[0]
digits = input.split //
num_digits = digits.size
exit if 2 > num_digits # one-digit numbers should fail
def print_if_eval print_array, eval_array
# concatenate the array and replace ^ with **
eval_string = (eval_array * '').gsub(?^, '**')
val = eval(eval_string)
if input.to_i == val
$><<print_array*''
exit
end
rescue
# this catches any DivideByZero or Overflow errors in eval.
end
# technically, this should be * (num_digits - 1), but as long as we
# have AT LEAST (num_digits - 1) copies of the operators, this works
operators = %w{* / + - ^} * num_digits
left_parens = ['('] * num_digits
right_parens = [')'] * num_digits
operators.permutation(num_digits-1) { |op_set|
# infix
# just uses the native order of operations, so just zip it all together
# 1+2-3*4/5^6
print_if_eval(digits.zip(op_set),
digits.zip(op_set))
# postfix
# leftparen-digit-operator, repeat; then add right_parens
# (1+(2-(3*(4/(5^(6))))))
#
print_if_eval(digits+op_set,
(left_parens.zip(digits, op_set) + right_parens))
# prefix
# leftparens; then add digit-rightparen-operator, repeat
# ((((((1)+2)-3)*4)/5)^6)
print_if_eval(op_set+digits,
left_parens + digits.zip(right_parens, op_set))
}
Changelog
247 made this work for larger numbers instead of timing out.
220 shaved off three chars by declaring paren arrays, and fixed a bug where one-digit numbers were considered VNFNs
213 initial commit