Javascript (E6) 215 (315 - 2*50 bonus) 252
Edit Simplified. Correct bug of 0 missing
Defined as a function, then counting 10 more byte for output using alert()
Important Really this one is not valid according to the rules, because javascript can not handle big numbers. For instance with parameters 2,5 it can't find 2^2^2^2^2 (ie 2^65536). A number this big is 'Infinity' in javascript.
Golfed
F=(n,k,g={})=>{k+=k-1;for (l=i=1;x=i.toString(6),l+=!!x[l],l<k;i++)if(x.split(0).length*2==l+1){for(s=[n,n],p=l;o=x[--p];)
if(-o)b=s.pop(),a=s.pop(),s.push(o<2?a+b:o<3?a-b:o<4?a*b:o<5?a/b:Math.pow(a,b));else s.push(x[p]=n);
r=Math.floor(s.pop());r>=0&isFinite(r)&!isNaN(r)&!g[r]&&(g[r]=x)}return Object.keys(g)};
To be golfed. I have an idea I want to share: use a postfix notation. In postfix any type of expression is made just of values and operators - no parentheses needed.
The postfix notation can be translated to usual algebraic infix notation - but that's out of scope in this challenge.
Usage
alert(F(4,3))
Output 1,2,3,4,5,8,12,16,20,32,64,252,256,260,1024,4096,65536,4294967296,1.3407807929942597e+154
Ungolfed
F=(n, k, g={})=>{
k += k - 1;
// Count in base 6 - '0' means Value, '1'..'5' means operators
// A valid expression starts with Value twice, then n operators intermixed with n-1 Values
// x: Coded expression, l: Expression length, k Expression limit length from param
for (l = i = 1; x = i.toString(6), l += !!x[l], l<k; i++)
if (x.split(0).length*2 == l+1) // check balancing values/operators
{
for (s = [n,n], p = l; o = x[--p];) // Calc stack starts with N,N
if (-o) // If not '0'
b=s.pop(),a=s.pop(), // Do calc
s.push(o<2 ? a+b : o<3 ? a-b : o<4 ? a*b : o<5 ? a/b : Math.pow(a,b))
else // Push value
s.push(n) //
r = Math.floor(s.pop()); // Last result in stack
r >= 0 & isFinite(r) & !isNaN(r) & !g[r] && (g[r]=x) // Put in hashtable avoiding duplicates
}
// Uncomment this to see the postfix expression list
// for (i in g) console.log(i, [n,n,...[...g[i]].reverse().map(v=>v>0?'x+-*/^'[v]:n)])
return Object.keys(g) // Retust list of hashtable keys
}
First version this is more complicated but maybe easier to follow
Display the postfix expression for each number
F=(n,k)=> {
var i,l,s;
var cmd;
var op='n+-*/^'
var bag = {}
function Calc(val,pos,stack)
{
while (c = cmd[pos])
{
if (c == 0)
{
stack.push(n);
cmd[pos] = n
pos++
}
else
{
var b=stack.pop(), a=stack.pop();
stack.push(c < 2 ? a+b : c < 3 ? a-b : c < 4 ? a*b : c < 5 ? a/b
: Math.pow(a,b))
cmd[pos]=op[c]
pos++
}
}
var res = Math.floor(stack.pop())
if (res > 0 && isFinite(res) && !isNaN(res) && !bag[res])
{
bag[res] = cmd
}
}
k=k+k-3;
for (i=1;s=i.toString(6), !s[k]; i++)
{
l=s.split(0).length;
if (l+l-1==s.length)
{
var cmd = (s+'00').split('').reverse()
Calc(n, 0, [], cmd.map(c=>op[c]).join(' '))
}
}
for (i in bag)
{
console.log(bag[i],'=', i)
}
}
Usage
F(4,3)
Output
[4, 4, "/"] = 1
[4, 4, "+", 4, "/"] = 2
[4, 4, 4, "/", "-"] = 3
[4, 4, "-", 4, "+"] = 4
[4, 4, "/", 4, "+"] = 5
[4, 4, "+"] = 8
[4, 4, "+", 4, "+"] = 12
[4, 4, "*"] = 16
[4, 4, "*", 4, "+"] = 20
[4, 4, "+", 4, "*"] = 32
[4, 4, "*", 4, "*"] = 64
[4, 4, "^", 4, "-"] = 252
[4, 4, "^"] = 256
[4, 4, "^", 4, "+"] = 260
[4, 4, "^", 4, "*"] = 1024
[4, 4, "+", 4, "^"] = 4096
[4, 4, "*", 4, "^"] = 65536
[4, 4, "^", 4, "^"] = 4294967296
[4, 4, 4, "^", "^"] = 1.3407807929942597e+154
3>
2so 2 should be included in the output. 2. by exponentiation you mean raising to a power, note^x?3. if you want code-golf (shortest code) then the code-challenge tag is redundant.@steveverrill: I concur on point 1, that needs to be clarified. I think most people call
2^x(or2**x) as exponentiation, whereasexp(x)is the exponential. As per 3, that was part of an edit I was making, so that's removed now – Kyle Kanos – 2014-06-20T01:35:37.610I meant that the base must be some expression of n (and not e). The only numerical value that can exist in the expression is n. – Ryan – 2014-06-20T01:44:12.077
1
Ryan, welcome to Programming Puzzles and Code Golf. Setting a well-specified challenge is difficult, so you always get a load of helpful comments. The idea is to make sure there is an unambiguous winner. This is a nice simple challenge. If you want to do a more complex one, you can use http://meta.codegolf.stackexchange.com/q/1596/15599 but I would also encourage you to take a look around and answer some questions, to get a feel of what we're about.
– Level River St – 2014-06-20T01:49:05.237Wait, what if total score will be negative due to bonus? – nicael – 2014-06-20T06:11:41.297
@nicael Then the score is negative. That happens. – Martin Ender – 2014-06-20T08:04:57.707
2Is outputting only non-negative integers a hard requirement or is it okay if we also output negative results? – Martin Ender – 2014-06-20T11:24:38.537
Related: Four fours, Obtaining target from given numbers
– Peter Taylor – 2014-06-20T11:55:56.047There is also the question of how we deal with operator precendence. For instance does
4 + 4 / 4give5or2? Is that up to us to decide? – Martin Ender – 2014-06-20T12:31:25.513@m.buettner I think we should use the common algebraic rules, the OP speaks of parenthese too – edc65 – 2014-06-20T13:17:39.030
@edc65 oh damn, the parentheses actually complicate things a lot – Martin Ender – 2014-06-20T13:18:56.523
@m.buettner It is a hard requirement if your language supports modifying arrays/sets/etc. (since removing negative elements from an array isn't that hard to do). If your language does not support that, then it is not a hard requirement. – Ryan – 2014-06-20T14:38:50.107
2Should be better not changing the rules during the challenge – edc65 – 2014-06-20T15:08:09.817
@m.buettner I don't know Mathematica, but I wouldn't be surprised if it has an operator for non-precedented string evaluation, which is basically equal to parentheses – ɐɔıʇǝɥʇuʎs – 2014-06-20T16:06:49.987
@Ryan There are still a few things that are unclear. For instance, do we need to use exactly
kinstances ofnor at most? You've written the latter, but using one2I can produce2(which is not in your list) and using two4s I can produce0(which is not in your list). Furthermore, my last question still stands: if we're to support parentheses, why is2not in your list for4 3? And if not, which operator precendence should we use? Currently the submissions generate vastly different results because of different interpretations of these questions. – Martin Ender – 2014-06-20T18:34:13.543