Ugly code to solve a combinatorial problem with an integer sum

[Paul]

I tried the problem of generating solutions like 123 - 45 - 67 + 89 = 100. The point is that we get 100 and we use the digits from 1 to 9 in consecutive order.
My code is really ugly, and it also took me ages to do. Any insights on how I can improve it? The problem is stated more accurately in the initial comments.
Many thanks for your help.

Paul

/*Problem 5
Write a program that outputs all possibilities to put + or - or nothing between the numbers 1, 2, ..., 9 (in this order)
such that the result is always 100. For example: 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100.*/

// First a utility function that inserts + and - into a vector of numbers to get a result
int insertSigns (const std::vector<int>& numbers, const std::string& plusesAndMinuses)
{
if(numbers.empty())
return 0;

int result = numbers[0];
for(int i = 1; i < numbers.size(); ++i)
result += (plusesAndMinuses[i - 1] == '+' ? numbers[i] : -numbers[i]);

return result;
}

// Generate all combinations of plus/minus signs of a given length. Use recursion
std::vector<std::string> plusesAndMinuses(int n)
{
std::vector<std::string> results;

if(!n)
return results;

if(n == 1)
return {"+", "-"};

const std::vector<std::string> formerResults = plusesAndMinuses(n-1);

for(int i = 0; i < formerResults.size(); ++i)
{
results.push_back("+" + formerResults[i]);
results.push_back("-" + formerResults[i]);
}

return results;
}

// Generate all vectors of numbers that can arise from concatenations in a list of numbers
// Numbers can only be concatenated with their neighbours. Use recursion
std::vector<std::vector<int>> concatenation (const std::vector<int>& numbers, int base = 10)
{
if(numbers.size() <= 1)
return {numbers};

const std::vector<int> tail(++numbers.begin(), numbers.end());
const std::vector<std::vector<int>> concatenateTail = concatenation(tail, base);
std::vector<std::vector<int> > results;

for(int i = 0; i < concatenateTail.size(); ++i)
{
std::vector<int> newVec;
newVec.push_back(concatenate(numbers[0], concatenateTail[i][0]));
for(int j = 1; j < concatenateTail[i].size(); ++j)
newVec.push_back(concatenateTail[i][j]);

results.push_back(newVec);

newVec.clear();
newVec.push_back(numbers[0]);
for(int j = 0; j < concatenateTail[i].size(); ++j)
newVec.push_back(concatenateTail[i][j]);

results.push_back(newVec);
}

return results;
}

// Investigates whether a number can be obtained from concatenation of a given vector
// Keeps track of all +, - sequences and concatenations which work.
void findSequences (int numberObtained, const std::vector<int>& numbers, std::vector<std::string>& plusMinus, std::vector<std::vector<int>>& sequences, int base = 10)
{
plusMinus.clear();
sequences.clear();

auto collection = concatenation(numbers, base);
for(const auto& vec : collection)
{
const auto& signs = plusesAndMinuses(vec.size() - 1);
for(auto& str : signs)
if(insertSigns(vec, str) == numberObtained)
{
plusMinus.push_back(str);
sequences.push_back(vec);
}
}

}

// Display the above result
void display(int numberObtained, const std::vector<std::string>& plusMinus, const std::vector<std::vector<int>>& sequences)
{
if(plusMinus.empty())
std::cout << std::endl << numberObtained << " can not be obtained. ";

for(int i = 0; i < plusMinus.size(); ++i)
{
std::cout << std::endl;
std::cout << sequences[i][0];
for(int j = 0; j < plusMinus[i].length(); ++j)
std::cout << " " << plusMinus[i][j] << " " << sequences[i][j + 1];

std::cout << " = " << numberObtained << std::endl;
}
}

// Combining above steps to calculate and then display results.
void display(int numberObtained, const std::vector<int>& numbers, int base = 10)
{
std::vector<std::string> plusMinus;
std::vector<std::vector<int> > results;
findSequences(numberObtained, numbers, plusMinus, results, base);

display(numberObtained, plusMinus, results);
}

// Test with given input.
void testProblem5()
{
std::vector<int> testVec;
for(int i = 1; i < 10; ++i)
testVec.push_back(i);

const int numberObtained = 100;
display(numberObtained, testVec);
}

[Paul]

On Tuesday, June 16, 2015 at 8:12:30 PM UTC+1, Paul wrote:
> I tried the problem of generating solutions like 123 - 45 - 67 + 89 = 100. The point is that we get 100 and we use the digits from 1 to 9 in consecutive order.
> My code is really ugly, and it also took me ages to do. Any insights on how I can improve it? The problem is stated more accurately in the initial comments.
> Many thanks for your help.
>
> Paul

Sorry, I left off the concatenate function. There's also a bug so that, contrary to what I claim, it won't work with bases other than 10. I'll repost the whole thing, fixing that bug.

// Concatenating numbers
int concatenate(int x, int y, int base = 10)
{
for(int i = 0; i < numDigits(y, base); ++i)
x *= base;

return x + y;

newVec.push_back(concatenate(numbers[0], concatenateTail[i][0], base));

[K. Frank]

Hello Paul!

On Tuesday, June 16, 2015 at 3:12:30 PM UTC-4, Paul wrote:
> I tried the problem of generating solutions like 123 - 45 - 67 + 89 = 100. The point is that we get 100 and we use the digits from 1 to 9 in consecutive order.
> My code is really ugly, and it also took me ages to do. Any insights on how I can improve it? The problem is stated more accurately in the initial comments.
> Many thanks for your help.

I have some thoughts, but take them with a grain of
salt. There are generally lots of different ways of
doing things.

There are also style preferences for how much generality,
abstraction, and hewing to prescriptive "good practices"
one wants to deal with.

> /*Problem 5
> Write a program that outputs all possibilities to put + or - or nothing between the numbers 1, 2, ..., 9 (in this order)
> such that the result is always 100. For example: 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100.*/
>
> // First a utility function that inserts + and - into a vector of numbers to get a result

There is a question of what level of granularity one wants
for helper functions for a problem like this. You only call
insertSigns once in your code. If it were me, I might not
package a code fragment like this in a separate function.
(But that's just me.)

> int insertSigns (const std::vector<int>& numbers, const std::string& plusesAndMinuses)

> ...

I think you can simplify things (get rid of things like
concatenate and insertSigns and so on) if you organize
your problem as follows:

Recognize that there are three ways of linking neighboring
digits together: a plus sign, a minus sign, or concatenate
the digits together to form a multi-digit number.

Thus, maybe

enum Operation { concat, plus, minus };

> ...

>
> // Generate all combinations of plus/minus signs of a given length. Use recursion

First, you have stated a specific problem (single digits,
1 through 9, in order), and you haven't stated a generalized
version of the problem. I would therefore write specific
code -- I would bake the specifics of the problem into my
data and algorithm -- rather than write more general helper
functions. If you write a more general function, you (or
at least I) can't say whether it's right or wrong, because
you haven't set forth the more general specification that
your function should satisfy.

So I might use the following data structure:

const int nOperations = 8;
// there are eight concat's, '+'s, or '-'s inserted
// between 9 digits.
Operation operations[nOperations];

I would lean against recursion, and just use a simple
loop. There are 3^8 = 6561 choices for how you insert
concat, '+', or '-' between the 9 digits. (That is, the
data structure operations can take on 3^8 distinct values.)

> std::vector<std::string> plusesAndMinuses(int n)

> ...

> // Generate all vectors of numbers that can arise from concatenations in a list of numbers
> // Numbers can only be concatenated with their neighbours. Use recursion
> std::vector<std::vector<int>> concatenation (const std::vector<int>& numbers, int base = 10)

(Again, without a more general problem having been stated,
I would elect not to support the generality of having a
base other than 10.)

Again, I would use a loop rather than recursion. Also, if
you use an array (or vector, etc) of Operations as your
primary data structure, the loop where you generate the
pluses and minuses and the (implicit) loop where you (implicitly)
generate your concatenations can be one and the same.

> ...

Anyway, just some thoughts.


Good luck.


K. Frank

[Paul]

Many thanks for your suggestions. I am trying to incorporate some of these ideas.

I'm finding it very difficult to make this work, though -- no easier to write than my previous attempt.

The problem is that (123 + 4) concatenated with 5 = 1275 which is not a legal sequence.

So we need to make sure to keep the sequences legal, and then I end up basically redoing my previous code.

Anyway, I'm very pleased to see someone else thought about the problem.

Paul

[Victor Bazarov]

On 6/18/2015 6:09 AM, Paul wrote:
>[..]

> Many thanks for your suggestions. I am trying to incorporate some of
> these ideas.
>
> I'm finding it very difficult to make this work, though -- no easier
> to write than my previous attempt.
>
> The problem is that (123 + 4) concatenated with 5 = 1275 which is not
> a legal sequence.
>
> So we need to make sure to keep the sequences legal, and then I end
> up basically redoing my previous code.
>
> Anyway, I'm very pleased to see someone else thought about the
> problem.

I didn't think of it until you posted. I didn't read either your
solution or K's. My approach would be this. Since you need to find all
possible combinations of digits interspersed with pluses or minuses (and
I am assuming that plus-minus is not valid), then you only have a
limited (and well-defined) number of combinations to try. They all
follow the pattern

<digit> { <op or nothing> <digit> } ...

That, with nine digits to use, gives 3^8 combinations, 6561 sets of
symbols. What I'd write is a function to convert a number between 0 and
6561 into a ternary representation (- for 0, _ for 1 and + for 2), then
take the original string, which is "123456789", and "apply" that ternary
representation to it, after which remove all underscores. Once you got
the final sequence, compute the expression it contains. If the outcome
is what you need (whatever the target), store the expression.

Seems very straight-forward.

V
--
I do not respond to top-posted replies, please don't ask

[Victor Bazarov]

Here is my attempt to generate all possible sequences:

#include <list>
#include <string>
#include <iostream>
#include <sstream>

using namespace std;

list<string> solutions(string const& sequence, int goal)
{
list<string> retval;
if (!sequence.empty())
{
auto ns = pow(3, sequence.length() - 1);

for (int k = 0; k < ns; ++k)
{
int is = k;
// generate the possible solution
string possible;
decltype(sequence.length()) ic = 0;
ostringstream os;
os << "possible solution # " << is;
while (is > 0)
{
possible.push_back(sequence[ic++]);
switch (is % 3)
{
case 1:
possible.push_back('+'); break;
case 2:
possible.push_back('-'); break;
}

is /= 3;
}
while (ic < sequence.length())
possible.push_back(sequence[ic++]);

retval.push_back(os.str() + " : " + possible); // debugging
}
}
return retval;
}

int main()
{
list<string> ls = solutions("1234", 100);
for (auto ss : ls)
{
cout << ss << endl;
}
}

Now just add your code to calculate the expression and record only those
that give you the correct one.

[Ben Bacarisse]

Paul <peps...@gmail.com> writes:
<snip>

>> > /*Problem 5
>> > Write a program that outputs all possibilities to put + or - or
>> > nothing between the numbers 1, 2, ..., 9 (in this order)
>> > such that the result is always 100. For example: 1 + 2 + 34 - 5 +
>> > 67 - 8 + 9 = 100.*/

> Anyway, I'm very pleased to see someone else thought about the
> problem.

<snip> I did, too, but I chose to solve it in another language (C as it
happens). Where is the problem from?

I got lost in your code very quickly -- it looked overly-complex for the
task. You might get people to engage wit the code more if you give the
overall plan first.

--
Ben.

[Victor Bazarov]

> [...snip...]

>
> Now just add your code to calculate the expression and record only those
> that give you the correct one.

It was fun to add a recursive calculating function, and here is the
complete program:

#include <list>
#include <string>
#include <iostream>
#include <sstream>

using namespace std;

long calculate(string const &sequence)
{
auto pi = sequence.find('+');
auto mi = sequence.find('-');
if (pi == string::npos && mi == string::npos)
{
long val{0};
istringstream is(sequence);
is >> val;
return val;
}
else
{
if (mi == string::npos // only plus is there
|| pi < mi) // or plus comes first
{
return calculate(sequence.substr(0, pi))
+ calculate(sequence.substr(pi + 1));
}
else if (pi == string::npos // only minus is there
|| mi < pi) // or minus comes first
{
return calculate(sequence.substr(0, mi))
- calculate(sequence.substr(mi + 1));
}
}
return 0;
}

list<string> solutions(string const& sequence, long goal)

{
list<string> retval;
if (!sequence.empty())
{
auto ns = pow(3, sequence.length() - 1);

for (int k = 0; k < ns; ++k)
{
int is = k;
// generate the possible solution
string possible;
decltype(sequence.length()) ic = 0;
ostringstream os;
os << "possible solution # " << is;
while (is > 0)
{
possible.push_back(sequence[ic++]);
switch (is % 3)
{
case 1:
possible.push_back('+'); break;
case 2:
possible.push_back('-'); break;
}

is /= 3;
}

while (ic < sequence.length())
possible.push_back(sequence[ic++]);

if (calculate(possible) == goal)

retval.push_back(os.str() + " : " + possible); // debugging
}
}
return retval;
}

int main()
{

list<string> ls = solutions("123456789", 100);

for (auto ss : ls)
{
cout << ss << endl;
}
}

Enjoy!

[Victor Bazarov]

[...]

Nope. There is a bug somewhere... Back to find it...

[Victor Bazarov]

Found the bug. It was performing the calculation out of order. Need to
start from the back.

[Victor Bazarov]

OK, here it is:
=============================================================== >8

#include <list>
#include <string>
#include <iostream>
#include <sstream>

using namespace std;

long primary(string const &sequence,
remove_const<decltype(string::npos)>::type &end)

{
long val{0};
istringstream is(sequence);
is >> val;

end = sequence.find_first_not_of("123456789");
return val;
}

long calculate(string sequence)
{
auto sign = string::npos;
long result = primary(sequence, sign);

while (sign != string::npos)
{
char sg = sequence[sign];
sequence = sequence.substr(sign + 1);
long rhs = primary(sequence, sign);
if (sg == '+')
result += rhs;
else if (sg == '-')
result -= rhs;
}

return result;

=============================================================== >8
possible solution # 909 : 123-45-67+89
possible solution # 1185 : 12-3-4+5-6+7+89
possible solution # 1416 : 12+3+4+5-6-7+89
possible solution # 1602 : 123+4-5+67-89
possible solution # 2560 : 1+2+3-4+5+6+78+9
possible solution # 3045 : 12+3-4+5+67+8+9
possible solution # 3205 : 1+23-4+56+7+8+9
possible solution # 3784 : 1+2+34-5+67-8+9
possible solution # 4744 : 1+23-4+5+6+78-9
possible solution # 5274 : 123+45-67+8-9
possible solution # 5823 : 123-4-5-6-7+8-9

:-)

[kfran...@gmail.com]

Hi Paul!

On Thursday, June 18, 2015 at 6:09:34 AM UTC-4, Paul wrote:
> On Wednesday, June 17, 2015 at 10:19:48 PM UTC+1, K. Frank wrote:
> > Hello Paul!
> >
> > On Tuesday, June 16, 2015 at 3:12:30 PM UTC-4, Paul wrote:
> > > I tried the problem of generating solutions like 123 - 45 - 67 + 89 = 100. The point is that we get 100 and we use the digits from 1 to 9 in consecutive order.

> ...
> > I think you can simplify things (get rid of things like
> > concatenate and insertSigns and so on) if you organize
> > your problem as follows:
> >
> > Recognize that there are three ways of linking neighboring
> > digits together: a plus sign, a minus sign, or concatenate
> > the digits together to form a multi-digit number.
> >
> > Thus, maybe
> >
> > enum Operation { concat, plus, minus };
> > ...

> > So I might use the following data structure:
> >
> > const int nOperations = 8;
> > // there are eight concat's, '+'s, or '-'s inserted
> > // between 9 digits.
> > Operation operations[nOperations];
> >
> > I would lean against recursion, and just use a simple
> > loop. There are 3^8 = 6561 choices for how you insert
> > concat, '+', or '-' between the 9 digits. (That is, the
> > data structure operations can take on 3^8 distinct values.)

> ...

> Many thanks for your suggestions. I am trying to incorporate some of these ideas.
>
> I'm finding it very difficult to make this work, though -- no easier to write than my previous attempt.
>
> The problem is that (123 + 4) concatenated with 5 = 1275 which is not a legal sequence.

Let me give a little more detail about what I was
thinking.

Let's use '_', '+', and '-' for concat, plus, and
minus, respectively.

So (just for shorthand, for this post) I could use

"_+-++_++"

to represent

operations = {
concat,
plus,
minus,
plus,
plus,
concat,
plus,
plus
};

This value of the data structure operations corresponds
to a numerical value according to your rules for combining
the digits 1 through 9.

That is

"_+-++_++" --> 12 + 3 - 4 + 5 + 67 + 8 + 9

I don't see any need to ever create a string (or
vector or whatever) that actually contains

"12 + 3 - 4 + 5 + 67 + 8 + 9"

or ever work explicitly with the digits 1 through 9.

(Of course you can work with the digits, numbers and
sequences explicitly, along the lines, for example, of
the approach Victor posted. What he says makes sense,
and should work fine, too.)

It is easy enough to loop over operations and calculate
the value on the fly. Roughly:

int value = 0; // accumulate final value here
int number = 1; // first digit is always 1
if (operations[0] == concat) { number *= 10; number += 2; }
// more stuff and actual loop here
int sign = (operations[idx] == minus) ? -1 : +1;
value += sign * number;

> So we need to make sure to keep the sequences legal, and then I end up basically redoing my previous code.

If you keep the actual digits implicit then any sequence of
eight of the three operations is, by construction, legal.

For example, a couple of pluses and minuses mixed up with
some concats is automatically legal:

"__+-+_-_"

You just (implicitly) drop the operations in between the
digits to get:

"__+-+_-_" --> 123 + 4 - 5 + 67 - 89

It's then easy enough to initialize operations to a starting
value (using my shorthand notation):

operations = "________"; // eight concats

and then write a loop that "increments" operations
to cycle through all 6561 possible values.

> Anyway, I'm very pleased to see someone else thought about the problem.

I hope my suggestions make some sense to you.

> Paul


Happy Hacking!


K. Frank

[Paul]

Hi Ben,

I got the problem from here: https://blog.svpino.com/2015/05/07/five-programming-problems-every-software-engineer-should-be-able-to-solve-in-less-than-1-hour

Thanks,

Paul

[gwowen]

On Thursday, June 18, 2015 at 6:07:40 PM UTC+1, Paul wrote:

> I got the problem from here: https://blog.svpino.com/2015/05/07/five-programming-problems-every-software-engineer-should-be-able-to-solve-in-less-than-1-hour
>
> Thanks,
>
> Paul

Lashed this up last night in about 20 minutes...

#include <iostream>
#include <string>
typedef enum {
CAT = 0,
ADD = 1,
SUB = 2,
} token_t;

int main()
{
#define THREE_POW_8 6561
for(int b3 = 0; b3 < THREE_POW_8; ++b3){
int runtotal = 0;
int digits = 1;
std::string sum("1");

int encoding = b3;
token_t last_token = ADD;
for(int i = 2;i<10;++i){
token_t this_token = token_t(encoding % 3);
switch(this_token){
case CAT:
digits = digits * 10 + i;
break;

case ADD:
case SUB:
sum += ((this_token == ADD) ? "+" : "-");
if(last_token == ADD) {
runtotal += digits;
} else {
runtotal -= digits;
}
digits = i;
last_token = this_token;

break;
}
encoding /= 3;
sum += ('0'+i) ;
}

if(last_token == ADD) {
runtotal += digits;
} else {
runtotal -= digits;
}

if(runtotal == 100) std::cout << sum << "=" << runtotal << "\n";

}
}

[bartekltg]

On 16.06.2015 21:12, Paul wrote:
> I tried the problem of generating solutions like 123 - 45 - 67 + 89 =
> 100. The point is that we get 100 and we use the digits from 1 to 9
> in consecutive order. My code is really ugly, and it also took me
> ages to do. Any insights on how I can improve it? The problem is
> stated more accurately in the initial comments. Many thanks for your
> help.

Use stack, so you dont have to recompute previous part of
a expression. This stack have exactly the same function as
hardware stack during recursion, but at the end you can
easily read from all levels.

It is quite convinient to build expresion from the end,
and add operator on the right.
Operations in string "...-67+89" will be
"concatenate 9"
"add 8"
"concatenate 7"
"minus 6"

The last one (1) is treated as "+1".



bartek@Kotoputerek:~/QTproj/build-stack_comp_lang_cpp-Desktop_Qt_5_4_1_GCC_64bit-Release$
time ./stack_comp_lang_cpp
+1+23-4+56+7+8+9
+12+3-4+5+67+8+9
+1+2+34-5+67-8+9
+1+2+3-4+5+6+78+9
+123-4-5-6-7+8-9
+123+45-67+8-9
+1+23-4+5+6+78-9
+12-3-4+5-6+7+89
+12+3+4+5-6-7+89
+123-45-67+89
+123+4-5+67-89

real 0m0.003s
user 0m0.001s
sys 0m0.002s


**************

#include <iostream>
#include <stack>

using namespace std;

class state
{
public:
int accumulator;
int next_val;
int digits;
char last_op;

void res() {
cout<<accumulator<<" "<<next_val<<endl;
}

state():accumulator(0),next_val(0),digits(1),last_op(' '){}

void plus(int x) {
accumulator+= x*digits + next_val;
next_val = 0;
digits=1;
last_op = '+';
}
void minus(int x) {
accumulator-=x*digits + next_val;
next_val = 0;
digits=1;
last_op = '-';
}
void conc(int x){
next_val += digits*x;
digits*=10;
last_op = ' ';
}
};



stack<state> St;

void search ( int n )//main recursion
{

if (n==1) { // the last level
state s = St.top();
s.plus(n);
St.push(s);
if (s.accumulator==100) {
stack<state> stack_copy(St);
int i=1;
while (stack_copy.size()>1) //we have one dummy
{
s=stack_copy.top();
stack_copy.pop();
if (s.last_op==' ')
cout<<i;
else
cout<<s.last_op<<i;
i++;
}
cout<<endl;
}
St.pop();
}
else { //not the prettiest part. Add updated state to the
stack, run recursion, delete the state you just put from stack, repeat
for next two operations
state s = St.top();
s.plus(n);
St.push(s);
search(n-1);
St.pop();

s = St.top();
s.minus(n);
St.push(s);
search(n-1);
St.pop();

s = St.top();
s.conc(n);
St.push(s);
search(n-1);
St.pop();
}
}


int main()
{
St.push(state());//dummy
search(9);
return 0;
}

[bartekltg]

On 18.06.2015 19:07, Paul wrote:

> I got the problem from here: https://blog.svpino.com/2015/05/07/five-programming-problems-every-software-engineer-should-be-able-to-solve-in-less-than-1-hour

For more math oriented problems you can look at
https://projecteuler.net/
First several dozens are very easy, the newest are mostly
hardcore algebra and number theory, but it contain many
interesting and doable problems.


bartek

[Rosario19]

follow the above line:

#include <stdio.h>

#define G(a,b) if(a)goto b
#define R return
#define P printf
#define F for
#define u8 unsigned char
#define u32 unsigned
#define i32 int

//position 0 1 2 3 4 5 6 7 8
u8 n[10]={1,2,3,4,5,6,7,8,9,0}; // 9+1 numbers
// 1 2 3 4 5 6 7 8
// 0 1 2 3 4 5 6 7
u8 o[10]={0}; // 8+1 operators 0=concatenate 1='+' 2='-'
// first concatenate 123456789

static i32 xx=1; // if xx==1 the start is +1etc xx==2 -1etc

// increment mod 3 array operartors
// seen too the first sign in xx
u32 incMod3(u8* a)
{u32 i;

i=0;
a0: if(a[i]==2)
{a[i]=0;
++i;
if(i==8)
{if(xx==2) R 0;
else {xx=2; R 1;} // inizia con -1
}
G(1, a0);
}
else ++a[i];
R 1;
}


// represent n[0..8] numbers with o[0..7] operators
i32 sumShow(u8* nu, u8* op, u32 v)
{i32 s, r;
u32 x, i;

r=0; s=0; i=0; x=xx; // x=1 only if 12+etc x=2 only if -12+etc
// get number until concatenate in r
a0: r=r*10+nu[i];
if(op[i]==0)
{++i; G(i!=9,a0);}

if(x==1) {s+=r;
if(v) P("+%u", r);
}
else if(x==2) {s-=r;
if(v) P("-%u", r);
}
else R -1;
r=0; x=op[i]; ++i;
G(i<9, a0);
if(v) {P("==%d op=", s);
F(i=0; i<8; ++i)
P("%u ", op[i]);
P("\n");
}
R s;
}

int main(void)
{i32 s;

F(;;)
{s=sumShow(n, o, 0);
if(s==100)
sumShow(n, o, 1);
if(incMod3(o)==0) R 0;
}
R 0;
}

--------------------
+123-45-67+89==100 op=0 0 2 0 2 0 1 0
+12-3-4+5-6+7+89==100 op=0 2 2 1 2 1 1 0
+12+3+4+5-6-7+89==100 op=0 1 1 1 2 2 1 0
+123+4-5+67-89==100 op=0 0 1 2 1 0 2 0
+1+2+3-4+5+6+78+9==100 op=1 1 2 1 1 1 0 1
+12+3-4+5+67+8+9==100 op=0 1 2 1 1 0 1 1
+1+23-4+56+7+8+9==100 op=1 0 2 1 0 1 1 1
+1+2+34-5+67-8+9==100 op=1 1 0 2 1 0 2 1
+1+23-4+5+6+78-9==100 op=1 0 2 1 1 1 0 2
+123+45-67+8-9==100 op=0 0 1 0 2 0 1 2
+123-4-5-6-7+8-9==100 op=0 0 2 2 2 2 1 2
-1+2-3+4+5+6+78+9==100 op=1 2 1 1 1 1 0 1

this case sum==30 has more solutions

+12-3+4-5-67+89==30 op=0 2 1 2 2 0 1 0
+1+2-3+4-56-7+89==30 op=1 2 1 2 0 2 1 0
+123+4+5-6-7-89==30 op=0 0 1 1 2 2 2 0
+12-3-4-5+6+7+8+9==30 op=0 2 2 2 1 1 1 1
+12+3+4-5+6-7+8+9==30 op=0 1 1 2 1 2 1 1
+12+3-4+5+6+7-8+9==30 op=0 1 2 1 1 1 2 1
+1-2+34-5-6+7-8+9==30 op=2 1 0 2 2 1 2 1
+1+2+34+5-6-7-8+9==30 op=1 1 0 1 2 2 2 1
+1+2-3-45+6+78-9==30 op=1 2 2 0 1 1 0 2
+12-3-45+67+8-9==30 op=0 2 2 0 1 0 1 2
+1+2-34-5+67+8-9==30 op=1 2 0 2 1 0 1 2
+12-3+4+5+6+7+8-9==30 op=0 2 1 1 1 1 1 2
+1-23+4+56-7+8-9==30 op=2 0 1 1 0 2 1 2
+1+2+34-5+6-7+8-9==30 op=1 1 0 2 1 2 1 2
+123-4-5-67-8-9==30 op=0 0 2 2 2 0 2 2
+1-2+3-4+56-7-8-9==30 op=2 1 2 1 0 2 2 2
+12+3+45-6-7-8-9==30 op=0 1 1 0 2 2 2 2
-1-2-3-4-56+7+89==30 op=2 2 2 2 0 1 1 0
-12-3-45-6+7+89==30 op=0 2 2 0 2 1 1 0
-1-2+3+4-56-7+89==30 op=2 1 1 2 0 2 1 0
-1-2-3-45-6+78+9==30 op=2 2 2 0 2 1 0 1
-12-34-5-6+78+9==30 op=0 2 0 2 2 1 0 1
-12+3-45+67+8+9==30 op=0 1 2 0 1 0 1 1
-12+3+4+5+6+7+8+9==30 op=0 1 1 1 1 1 1 1
-1-2+34-5-6-7+8+9==30 op=2 1 0 2 2 2 1 1
-1+2-34-5+67-8+9==30 op=1 2 0 2 1 0 2 1
-1-23+4+56-7-8+9==30 op=2 0 1 1 0 2 2 1
-12-3+45+6-7-8+9==30 op=0 2 1 0 1 2 2 1
-1+2+34-5+6-7-8+9==30 op=1 1 0 2 1 2 2 1
-1-2+3-45+6+78-9==30 op=2 1 2 0 1 1 0 2
-1-23-4-5-6+78-9==30 op=2 0 2 2 2 1 0 2
-12-3+45-6+7+8-9==30 op=0 2 1 0 2 1 1 2
-1+2+34-5-6+7+8-9==30 op=1 1 0 2 2 1 1 2
-1-2-3+4+56-7-8-9==30 op=2 2 1 1 0 2 2 2

[Luca Risolia]

On 18/06/2015 16:53, Victor Bazarov wrote:
> possible solution # 909 : 123-45-67+89
> possible solution # 1185 : 12-3-4+5-6+7+89
> possible solution # 1416 : 12+3+4+5-6-7+89
> possible solution # 1602 : 123+4-5+67-89
> possible solution # 2560 : 1+2+3-4+5+6+78+9
> possible solution # 3045 : 12+3-4+5+67+8+9
> possible solution # 3205 : 1+23-4+56+7+8+9
> possible solution # 3784 : 1+2+34-5+67-8+9
> possible solution # 4744 : 1+23-4+5+6+78-9
> possible solution # 5274 : 123+45-67+8-9
> possible solution # 5823 : 123-4-5-6-7+8-9

Are those supposed to be ALL the possible solutions?

I don't see -1 +2 -3 +4 +5 +6 +78 +9 in the list, for example.

[gwowen]

On Friday, June 19, 2015 at 1:41:10 PM UTC+1, Luca Risolia wrote:

> Are those supposed to be ALL the possible solutions?
>
> I don't see -1 +2 -3 +4 +5 +6 +78 +9 in the list, for example.

You're not allowed a leading '-'

[Victor Bazarov]

The specification was that the arithmetic signs shall be placed *between
the digits*.

[Luca Risolia]

On 19/06/2015 14:24, Rosario19 wrote:

> +123-45-67+89==100 op=0 0 2 0 2 0 1 0
> +12-3-4+5-6+7+89==100 op=0 2 2 1 2 1 1 0
> +12+3+4+5-6-7+89==100 op=0 1 1 1 2 2 1 0
> +123+4-5+67-89==100 op=0 0 1 2 1 0 2 0
> +1+2+3-4+5+6+78+9==100 op=1 1 2 1 1 1 0 1
> +12+3-4+5+67+8+9==100 op=0 1 2 1 1 0 1 1
> +1+23-4+56+7+8+9==100 op=1 0 2 1 0 1 1 1
> +1+2+34-5+67-8+9==100 op=1 1 0 2 1 0 2 1
> +1+23-4+5+6+78-9==100 op=1 0 2 1 1 1 0 2
> +123+45-67+8-9==100 op=0 0 1 0 2 0 1 2
> +123-4-5-6-7+8-9==100 op=0 0 2 2 2 2 1 2

It seems that this one is not a solution because of the leading '-':

[Christian Gollwitzer]

Am 19.06.15 um 14:24 schrieb Rosario19:

> #include <stdio.h>
>
> #define G(a,b) if(a)goto b
> #define R return
> #define P printf
> #define F for
> #define u8 unsigned char
> #define u32 unsigned
> #define i32 int

> [...]

Are you preparing your submission to IOCCC?

Christian

[Victor Bazarov]

On 6/19/2015 11:36 AM, Stefan Ram wrote:

> Victor Bazarov <v.ba...@comcast.invalid> writes:
>> Here is my attempt to generate all possible sequences:
>

> Here's my attempt to print all terms summing up to 100:
> [..]

It is actually gratifying to see that all solutions are quite similar.

[gwowen]

On Friday, June 19, 2015 at 4:40:10 PM UTC+1, Victor Bazarov wrote:
> On 6/19/2015 11:36 AM, Stefan Ram wrote:
> > Victor Bazarov <v.ba...@comcast.invalid> writes:
> >> Here is my attempt to generate all possible sequences:
> >
> > Here's my attempt to print all terms summing up to 100:
> > [..]
>
> It is actually gratifying to see that all solutions are quite similar.

Maybe, but I am slightly amazed how many of them use recursion.

[Victor Bazarov]

I am not sure I am reading the meaning of your statement correctly. Do
you consider recursion superfluous? And, in general, what's your take,
is recursion OK or, if another solution (a loop, perhaps) exists,
recursion should be avoided?

[Rosario19]

not compile with these errors:
Error E2108 m.cpp 8: Improper use of typedef 'string'
Error E2293 m.cpp 8: ) expected
Error E2141 m.cpp 83: Declaration syntax error
*** 3 errors in Compile ***

[Rosario19]

for me the IOCCC ones, are the ones posted in this thread in C++;
i understand little in their C++ code, library use etc etc
i understand at first see, instead, what the above code does [or seems
to me so]

how one easy problem seen using some goto, some array and pointers in
C became difficult in C++ using hevy libraries etc

what is IOCCC became readable
and what would be readable is IOCCC (even the C++ compiler here not
compile one of these examples)

[guinne...@gmail.com]

For what it's worth, here's my (non-recursive) solution:

//--------8<--------

using namespace std;
enum JoinerType { add, subtract, concatenate, NumJoinerTypes };
size_t const NumJoiners = 8; // # places between the 9 nonzero digits

#include <array>
typedef array<JoinerType, NumJoiners> JoinerSequence;

JoinerSequence& operator++(JoinerSequence& joiners)
{
for (JoinerType& joiner: joiners)
{
joiner = static_cast<JoinerType>(joiner + 1);
if (joiner < NumJoinerTypes) break;
joiner = static_cast<JoinerType>(0);
}

return joiners;
}

int evaluate(JoinerSequence const& joiners)
{
int sum = 0;
unsigned digit = 1;
unsigned number = digit++;
unsigned next_operation = add;

for (JoinerType const joiner: joiners)
{
if (joiner != concatenate)
{
sum = (next_operation == add)? sum + number: sum - number;
next_operation = joiner;
number = 0;
}

number = (number * 10) + digit++;
}

return (next_operation == add)? sum + number: sum - number;
}

#include <ostream>
ostream& operator<<(ostream& output, JoinerSequence const& joiners)
{
char digit = '1';

for (JoinerType const joiner: joiners)
{
output << digit++;
if (joiner == subtract) output << " - ";
else if (joiner == add) output << " + ";
}

return output << digit;
}

#include <iostream>
int main()
{
JoinerSequence const first_sequence{};
JoinerSequence current_sequence = first_sequence;

do
{
if (evaluate(current_sequence) == 100)
{
cout << current_sequence << " = 100\n";
}
}
while (++current_sequence != first_sequence);
}

//--------8<--------

[Victor Bazarov]

On 6/19/2015 12:13 PM, Rosario19 wrote:
> On Thu, 18 Jun 2015 10:53:42 -0400, Victor Bazarov wrote:
>>
>> OK, here it is:

>> [..]

>
> not compile with these errors:
> Error E2108 m.cpp 8: Improper use of typedef 'string'
> Error E2293 m.cpp 8: ) expected
> Error E2141 m.cpp 83: Declaration syntax error
> *** 3 errors in Compile ***

Can't help you, sorry. Compiles for me fine. And if you include
<cmath>, compiles on G++ v4.8.3 online as well. Make sure your compiler
is C++11 compliant (at implements 'decltype').

[Richard]

[Please do not mail me a copy of your followup]

Victor Bazarov <v.ba...@comcast.invalid> spake the secret code
<mm1i2a$skl$1...@dont-email.me> thusly:

>On 6/19/2015 12:13 PM, Rosario19 wrote:
>> On Thu, 18 Jun 2015 10:53:42 -0400, Victor Bazarov wrote:
>>>
>>> OK, here it is:
>>> [..]
>>
>> not compile with these errors:
>> Error E2108 m.cpp 8: Improper use of typedef 'string'
>> Error E2293 m.cpp 8: ) expected
>> Error E2141 m.cpp 83: Declaration syntax error
>> *** 3 errors in Compile ***
>
>Can't help you, sorry. Compiles for me fine. And if you include
><cmath>, compiles on G++ v4.8.3 online as well. Make sure your compiler
>is C++11 compliant (at implements 'decltype').

And for gcc/clang be sure to use '-std' with an appropriate value.
(Why this isn't set to -std=c++11 as the default on a compiler that
implements C++11, I don't understand.)
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
The Terminals Wiki <http://terminals.classiccmp.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>

[gwowen]

On Friday, June 19, 2015 at 5:05:13 PM UTC+1, Victor Bazarov wrote:

> I am not sure I am reading the meaning of your statement correctly. Do
> you consider recursion superfluous?

Not superfluous, more of a necessary evil.

> And, in general, what's your take,
> is recursion OK or, if another solution (a loop, perhaps) exists,
> recursion should be avoided?

My personal opinion (and I accept that it is just an opinion) is that if an obvious loop-based solution of similar complexity exists, recursion should be avoided unless:
i) it's clearly a more elegant fit to the problem domain
ii) you can easily bound the stack space and algorithmic complexity

There are definitely cases in hard combinatoric problems where recursion simplifies everything - and any other solution will be almost certainly more complex and less comprehensible.

In this case, however, the enumeration is trivial (a string of length 8 from a three-symbol alphabet). You don't need recursion to do that, any more than you do to print the numbers from 100 to 0 counting backwards, or print the binary representation of a positive integer.

[gwowen]

On Friday, June 19, 2015 at 5:17:49 PM UTC+1, Stefan Ram wrote:
> For example, in C++, technically, the factorial is
> implemented better with a loop than with recursion.
>
> However, when it is know that the depth of the recursion
> does not exceed a small number, like maybe 32, one might use
> recursion in C++ when it is better readable or writeable for
> humans.
>
> Some problems with recursive data structures, like traversal
> of trees (filesystems) or AI (like chess) or parsers for
> languages with recursive grammars really beg for recursion,
> and it might become quite cumbersome to implement them in
> such a way that stack usage is O(1) instead of O(n).

I agree with everything Stefan wrote.

[bartekltg]

This may be measurement error, but it looks like my
recursion solution is 30% faster than yours (on my
computer, complicator etc.)
Other things than recursion vs. loops were more important
(for example, complexity: O(3^n) instead of O(n*3^n))

I think I should rewrite it to get rid of recursion,
and check, if it will run faster.


bartekltg

[gwowen]

On Friday, June 19, 2015 at 11:45:46 PM UTC+1, bartekltg wrote:

> This may be measurement error, but it looks like my
> recursion solution is 30% faster than yours (on my
> computer, complicator etc.)

Well, I do build more than 6,500 totally unnecessary strings in an incredibly inefficient way. That's going to dominate the runtime.

> Other things than recursion vs. loops were more important
> (for example, complexity: O(3^n) instead of O(n*3^n))

I'd be interested to see how you got O(3^n) for the recursive version. Not questioning it, just interested.

[gwowen]

On Saturday, June 20, 2015 at 7:16:50 AM UTC+1, gwowen wrote:
> I'd be interested to see how you got O(3^n) for the recursive version.
> Not questioning it, just interested.

No need Bart, I thought about it and I see now.
That's definitely a win for recursion when n gets large (as long as you can avoid smashing the stack). Tail-recursion would help.

[bartekltg]

On 20.06.2015 08:26, gwowen wrote:
> On Saturday, June 20, 2015 at 7:16:50 AM UTC+1, gwowen wrote:
>> I'd be interested to see how you got O(3^n) for the recursive version.
>> Not questioning it, just interested.

This post was superseded or my server lost it?

I have posted the solution in this thread earlier:
Message-ID: <mm0u43$7ie$1...@node1.news.atman.pl>
Not the prettiest one, but I think quite readable.

> No need Bart, I thought about it and I see now. That's definitely a
> win for recursion when n gets large (as long as you can avoid
> smashing the stack). Tail-recursion would help.

In this particular problem when a stack is to short,
life of the universe is to short to finish the computation too ;-)

I have no idea how good gcc is with tail-recursion (gcc is not ocaml;-)
In my code t-r is not used (A looked at asm output, three recursive
calls, and with tail-recursion should be two). But simple factorial
code gcc compile correctly to loop.

int factorial (int x){
if (x>1) return x*factorial(x-1);
else return x;
}

.type _Z9factoriali, @function
_Z9factoriali:
.LFB1879:
.cfi_startproc
cmpl $1, %edi
jle .L50
movl $1, %edx
.p2align 4,,10
.p2align 3
.L49:
leal -1(%rdi), %eax
imull %edi, %edx
cmpl $1, %eax
movl %eax, %edi
jne .L49
.L48:
imull %edx, %eax
ret
.L50:
movl %edi, %eax
movl $1, %edx
jmp .L48


bartekltg

[Luca Risolia]

> The specification was that the arithmetic signs shall be placed *between
> the digits*.

Right. Here is my algorithm then. Just to do something different, I
tried not to use strings or sequence of chars.

#include <iostream>
#include <cstdint>
#include <vector>
#include <list>

using Seq = std::vector<std::int32_t>;
using List = std::list<Seq>;

std::int32_t term(std::size_t p, std::size_t q) {
return q > p ? 10 * term(p, q - 1) + q : p;
}

void solve_(int m, int n, std::int32_t r, std::int32_t s,
Seq& terms, List& solutions) {
for (int i = m; i <= n; ++i) {
for (int f = -1; f <= 1; f += 2) {
auto t = term(m, i) * f;
if (t != -1) {
terms.push_back(t);
solve_(i + 1, n, r, s + t, terms, solutions);
terms.pop_back();
}
}
}
if (m > n && r == s)
solutions.push_back(terms);
}

List solve(int m, int n, std::int32_t r) {
Seq terms;
terms.reserve(n - m + 1);
List solutions;
solve_(m, n, r, 0, terms, solutions);
return solutions;
}

void print(const List& l) {
for (const auto& s : l) {
bool sign = false;
for (const auto& t : s) {
if (t > 0 && sign)
std::cout << '+';
std::cout << t;
sign = true;
}
std::cout << '\n';
}
}

int main() {
auto solutions = solve(1, 9, 100);
print(solutions);
}

---

// Output:
1+2+3-4+5+6+78+9
1+2+34-5+67-8+9
1+23-4+5+6+78-9
1+23-4+56+7+8+9
12-3-4+5-6+7+89
12+3-4+5+67+8+9
12+3+4+5-6-7+89
123-4-5-6-7+8-9
123+4-5+67-89
123-45-67+89
123+45-67+8-9

[Luca Risolia]

On 22/06/2015 12:27, Luca Risolia wrote:
> if (t != -1) {

better:
if (t > 0 || terms.size())

[Juha Nieminen]

if (t > 0 || !terms.empty())


--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---

[Luca Risolia]

On 19/06/2015 17:36, Stefan Ram wrote:
> prints:
>
> 1 2 3+4 5-6 7+8-9

Does not the problem say "put + or - *or nothing* between the numbers 1,
2, ..., 9"? I see some unneeded white spaces in your solutions.

[alf.p.s...@gmail.com]

On Tuesday, June 16, 2015 at 9:12:30 PM UTC+2, Paul wrote:
> My code is really ugly, and it also took me ages to do. Any insights on how I can improve it? The problem is stated more accurately in the initial comments.
> Many thanks for your help.
>
> Paul
>
> /*Problem 5
> Write a program that outputs all possibilities to put + or - or nothing between the numbers 1, 2, ..., 9 (in this order)
> such that the result is always 100. For example: 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100.*/

Well, I see that K. Frank already suggested the to me most natural solution, and Victor Bazarov already presented complete code for that solution.

But since different people's notion of beauty and ugliness differs, here's my take on it:

------------------------------------------------------------------------------

// Problem 5
// Write a program that outputs all possibilities to put + or - or nothing between
// the numbers 1, 2, ..., 9 (in this order) such that the result is always 100. For
// example: 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100.

#include <assert.h>

static_assert( int(987654321) == 987654321LL, "`int` isn't enough for 987654321" );

enum class Op { none = 0, plus, minus };

auto eval( int expr_id )
-> int
{
int operand = 0;
int result = 0;
Op previous_op = Op::plus;

for( int i = 1; i <= 10; ++i )
{
if( i != 10 ) { operand = 10*operand + i; }
Op const current_op = Op( expr_id % 3 );
if( i == 10 || current_op != Op::none )
{
switch( previous_op )
{
case Op::none: assert( false ); break;
case Op::plus: result += operand; break;
case Op::minus: result -= operand; break;
}
previous_op = current_op; operand = 0;
}
expr_id /= 3;
}
return result;
}

#include <iostream>
using namespace std;

auto main() -> int
{
for( int expr_id = 0; expr_id < 3*3*3*3*3*3*3*3; ++expr_id )
{
if( eval( expr_id ) == 100 )
{
cout << "100 = ";
int id = expr_id;
for( int i = 1; i <= 9; ++i )
{
static char const* const operators[] = {"", " + ", " - "};
cout << i << operators[id % 3];
id /= 3;
}
cout << endl;
}
}
}

Cheers & hth.,

- Alf

[Paul]

I like this solution very much. Regarding the static assert, if I were concerned about this, I would simply use long longs in the first place, but that's probably just me.

Paul

[Mr Flibble]

On 23/06/2015 03:08, alf.p.s...@gmail.com wrote:

Talk about being anal-retentive...

> auto main() -> int

int main()

/Flibble

[Öö Tiib]

On Tuesday, 23 June 2015 07:03:42 UTC+3, Stefan Ram wrote:

> alf.p.s...@gmail.com writes:
> >auto eval( int expr_id )
> > -> int

> ...
> > int result = 0;
> ...
> > return result;
>
> Since C++14 »-> int« is not necessary anymore:

Yes, but that was meant for generic contexts where
we usually do not have separate declaration and
definition and may have otherwise to write things
like '->decltype(that+other)' or worse.

It feels bad idea to not write a known simple return
type (like 'int') of mundane function out explicitly.
Think about the lot of nausea caused by (and
fortunately deprecated by now) implicit 'int' of C.

[gwowen]

Amen. Is this from some sort of competition to the write least-comprehensible and backward-compatible code possible?

What is the possible benefit of saying "please infer the return type (the answer is int, by the way)"?

[Öö Tiib]

Alf's style makes sense for people who feel that return
value of function in C and C++ is visually in "wrong"
place. It is matter of taste.

Lot of language neutral programming tools also show
declarations in style of PASCAL:

function max(num1, num2: integer): integer

For me both styles are readable; I only dislike
inconsistency within code-base. So if team wants
to switch then someone has to refactor *all* function
declarations and definitions in code base.

[Öö Tiib]

It helps visually a bit to differentiate between procedures
and functions (function is noun prefixed with 'auto',
procedure is verb prefixed with 'void').

So instead of ...:

// procedure
void burn_down_harddrive( Harddrive& h );
// function
double cosine( Degrees angle );

... we can have:

// procedure
void burn_down_harddrive( Harddrive& h );
// function
auto cosine( Degrees angle ) -> double;

I see that it is bit unorthodox at first but
if to look at it then it is tolerable when
used consistently in whole code base.

[gwowen]

On Thursday, June 25, 2015 at 10:24:25 AM UTC+1, Öö Tiib wrote:

> ... we can have:
>
> // procedure
> void burn_down_harddrive( Harddrive& h );
> // function
> auto cosine( Degrees angle ) -> double;

and what does

auto do_stuff( Degrees angle ) -> void;

denote?

void burn_down_harddrive(Harddrive&j);
double cosine( Degrees angle);

"void" means a procedure (or, get this, a function that doesn't return anything). "any other type" means a function that does return something, and I don't have to scan to the end of the argument list to see what.

> I see that it is bit unorthodox at first but
> if to look at it then it is tolerable when
> used consistently in whole code base.

Almost anything is tolerable. The question was, what's the advantage?

[David Brown]

In cases like this, it's only advantage is if you prefer that style for
cosmetic reasons.

The whole point of this syntax was for more complex expressions,
especially for template functions, where the return type depends on the
parameter types - thus you can't express the return type until after the
parameters are written.

[gwowen]

On Thursday, June 25, 2015 at 11:13:41 AM UTC+1, David Brown wrote:

> The whole point of this syntax was for more complex expressions,
> especially for template functions,

Lambda's, particularly. There its extremely handy because

auto l_obj []() -> int { .... }

Let's you be explicity about the return type of the lambda's operator(), while letting compiler worry about the type of the functor/closure itself.

> where the return type depends on the
> parameter types - thus you can't express the return type until after the
> parameters are written.

I can't think what you mean here. e.g.

template<class T> T::valuetype f(const T&t) {
...
} // works ok

[Öö Tiib]

On Thursday, 25 June 2015 13:07:39 UTC+3, gwowen wrote:
> On Thursday, June 25, 2015 at 10:24:25 AM UTC+1, Öö Tiib wrote:
>
> > ... we can have:
> >
> > // procedure
> > void burn_down_harddrive( Harddrive& h );
> > // function
> > auto cosine( Degrees angle ) -> double;
>
> and what does
>
> auto do_stuff( Degrees angle ) -> void;
> denote?

It denotes nonsense obfuscation. Same as that one:

typedef void Nothing;
Nothing do_stuff( Degrees angle );

All useful languages are very easy to use for expressing nonsense.

> void burn_down_harddrive(Harddrive&j);
> double cosine( Degrees angle);

What you meant by repeating code that I wrote and that you snipped?

> "void" means a procedure (or, get this, a function that doesn't return anything).

Yes, in C rhetoric a procedure is function that returns void. Decades ago when I learned C it did sound like lunatic's delirium ... but now I'm used to it. I just can't never learn to think that way.

> "any other type" means a function that does return something, and I don't have to scan to the end of the argument list to see what.

Can't get everything and functions name is more important to find from that pile than return type. Alf writes:

auto cosine( Degrees angle )
-> double;

I like them on same line, ')->' is fine enough visual separator for me.

> > I see that it is bit unorthodox at first but
> > if to look at it then it is tolerable when
> > used consistently in whole code base.
>
> Almost anything is tolerable. The question was, what's the advantage?

The advantage is that function's name is put before rest of the clutter. It is same what lot of language neutral programming tools do.

In C++ we have lot of Yoda-speak ... like "template class" (that means class template) and "const reference" (that means reference to immutable) and "const pointer" (that means pointer to immutable).
We are used to it but that does not make it right and I still feel like translating those everytime I hear.

[Öö Tiib]

It is for cases like

template<class A, class B>
decltype( *static_cast<A*>(nullptr) * *static_cast<B*>(nullptr) ) multiplication(A const &a, B const &b )
{
return a * b;
}

[David Brown]

Which you would write as:

template<class A, class B>

auto multiplication(A const &a, B const &b) -> decltype(a * b)
{
return a * b;
}


With C++14, you could omit the return type entirely here:

template<class A, class B>

auto multiplication(A const &a, B const &b)
{
return a * b;
}

You only need the explicit return type in C++14 if there are multiple
return statements leading to ambiguous return type deduction:

template<class A, class B>

auto multiplication(A const &a, B const &b) -> decltype(a * b)
{
if (a == 0) return 0;
if (b == 0) return 0;
return a * b;
}

[gwowen]

On Thursday, June 25, 2015 at 2:51:21 PM UTC+1, David Brown wrote:

> template<class A, class B>
> auto multiplication(A const &a, B const &b) -> decltype(a * b)
> {
> return a * b;
> }
>

Ah yes, I'd overlooked decltype. Thank you (and to Öö). Definitely useful there. It'd be nice to have a decltype-equiv that works on types...

// obviously issues with free functions v. member functions for operator*
template <class A,class B> decltype(operator*(const A&,const B&))
func(const A&a,const B&b){....}

[Öö Tiib]

On Thursday, 25 June 2015 17:23:12 UTC+3, gwowen wrote:
> On Thursday, June 25, 2015 at 2:51:21 PM UTC+1, David Brown wrote:
>
> > template<class A, class B>
> > auto multiplication(A const &a, B const &b) -> decltype(a * b)
> > {
> > return a * b;
> > }
> >
>
> Ah yes, I'd overlooked decltype. Thank you (and to Öö). Definitely useful there. It'd be nice to have a decltype-equiv that works on types...

There actually is ... the 'std::result_of' in <type_traits> (loaned from boost).
It is less powerful than 'decltype' but also sometimes less ugly. Its
main shortcoming is that it does not work with built-in operators
that you possibly may want to invoke in your example below.

[alf.p.s...@gmail.com]

On Thursday, June 25, 2015 at 12:07:39 PM UTC+2, gwowen wrote:
>
> The question was, what's the advantage?

Thank you for clarifying your earlier posting. I failed to infer that meaning from your earlier

> Is this from some sort of competition to the write least-comprehensible and backward-compatible code possible?

I read that as just a trolling maneuver.

Likewise, the following paragraph you posted,

> What is the possible benefit of saying "please infer the return type (the answer is int, by the way)"?

didn't strike me as technically meaningful, so I reasoned it was just trolling again.

But now, with your clarification, I, and possibly others, understand that you really meant to /ask/, "what's the advantage". And even though that question contains an unwarranted assumption of a single main advantage, it's answerable.

If you would care to ask that, possibly modified to get rid of the assumption, and not introducing more of that earlier difficult-to-read-as-other-than-trolling stuff, i.e. like "What are the advantages of this notation?", in direct response to my code, then if I happen to see it (I do not visit here often) I'll try to answer it. Or you may look at SO, where it's been answered numerous times.

[Chris Vine]

On Thu, 25 Jun 2015 08:49:42 -0700 (PDT)
alf.p.s...@gmail.com wrote:
> On Thursday, June 25, 2015 at 12:07:39 PM UTC+2, gwowen wrote:
> >
> > The question was, what's the advantage?
>
> Thank you for clarifying your earlier posting. I failed to infer that
> meaning from your earlier
>
> > Is this from some sort of competition to the write
> > least-comprehensible and backward-compatible code possible?
>
> I read that as just a trolling maneuver.
>
> Likewise, the following paragraph you posted,
>
> > What is the possible benefit of saying "please infer the return
> > type (the answer is int, by the way)"?
>
> didn't strike me as technically meaningful, so I reasoned it was just
> trolling again.

It hasn't taken you very long to get back to your "everyone who
disagrees with me is a troll" meme. Try hard to avoid it if you can:
not everyone will always agree with you, however poorly they explain
their disagreement to your satisfaction.

Chris

[gwowen]

On Thursday, June 25, 2015 at 4:50:02 PM UTC+1, alf.p.s...@gmail.com wrote:

> > What is the possible benefit of saying "please infer the return type (the answer is int, by the way)"?
>
> didn't strike me as technically meaningful, so I reasoned it was just trolling again.

Well, there's a surprise.

[Scott Lurndal]

=?ISO-8859-1?Q?=D6=F6_Tiib?= <oot...@hot.ee> writes:
>On Thursday, 25 June 2015 13:07:39 UTC+3, gwowen wrote:

>> Almost anything is tolerable. The question was, what's the advantage?
>

>The advantage is that function's name is put before rest of the clutter. It=
> is same what lot of language neutral programming tools do.=20
>

Please.

int
main(int argc, const char **argv, const char **envp)

accomplishes the same thing, is more readable, and
allows '/^main' in vi to jump directly to the function
definition.

That works with C++ functions as well

inline uint64_t
CpuCoreState::get_gpr(Register::Registers register)
{
returns _registers[register];
}

[Öö Tiib]

On Thursday, 25 June 2015 19:57:21 UTC+3, Scott Lurndal wrote:
> =?ISO-8859-1?Q?=D6=F6_Tiib?= <oot...@hot.ee> writes:
> >On Thursday, 25 June 2015 13:07:39 UTC+3, gwowen wrote:
>
> >> Almost anything is tolerable. The question was, what's the advantage?
> >
> >The advantage is that function's name is put before rest of the clutter. It=
> > is same what lot of language neutral programming tools do.=20
> >
>
> Please.
>
> int
> main(int argc, const char **argv, const char **envp)
>
> accomplishes the same thing, is more readable, and
> allows '/^main' in vi to jump directly to the function
> definition.

More readable is matter of taste, '/^auto main' takes
half a second longer to type indeed.

When I make list of all lines where overloads of function
are defined then it annoys me that these contain no return
types.

> That works with C++ functions as well
>
> inline uint64_t
> CpuCoreState::get_gpr(Register::Registers register)
> {
> returns _registers[register];
> }

The member functions of class often return class-local types and typedefs.
That results with stutter:

SomeContainer::const_iterator SomeContainer::middle()
{
// ...
}

Two lines or one ... still stutter. With return type after ... no stutter:

auto SomeContainer::middle() -> const_iterator
{
// ...
}

[Öö Tiib]

On Thursday, 25 June 2015 16:42:02 UTC+3, Stefan Ram wrote:

> Öö Tiib <oot...@hot.ee> writes:
> >>"void" means a procedure (or, get this, a function that doesn't return anything).
> >Yes, in C rhetoric a procedure is function that returns void.
>

> It's funny. Pascal or Algol seem to be a languages that are
> long dead. But they live on when programmers use their
> terminology as a common language. After all, that's where
> »procedure« comes from AFAIK. What will be in some decades
> when programmers do not learn Pascal or Algol anymore?

That family isn't entirely dead. Delphi and Ada are pretty much
among alive languages; one can find a well-paid job of using
those. Other programming languages (like Visual Basic) make
similarly clear distinction.

> Could it be that for future children we will explain:
> »What's a procedure? It's just a function returning void!«

The difference between subprograms that return something
and the ones that return nothing feels to be not about return
type but about fact that the lack of return means that it *must*
have side effect by other means to be not worthless.

Technically subprograms that return nothing are indeed
subtype of ones that return something but in programming
logic it feels as upside down like thinking of statements as
subtype of expressions.

[Chris Vine]

On Fri, 26 Jun 2015 02:22:46 -0700 (PDT)
Öö Tiib <oot...@hot.ee> wrote:
[snip]

> The difference between subprograms that return something
> and the ones that return nothing feels to be not about return
> type but about fact that the lack of return means that it *must*
> have side effect by other means to be not worthless.
>
> Technically subprograms that return nothing are indeed
> subtype of ones that return something but in programming
> logic it feels as upside down like thinking of statements as
> subtype of expressions.

If this distinction between "procedure" and "function" is to have any
logic, the word "function" should be applied to functions which are
referentially transparent and so analogous to mathematical functions
and "procedure" to those which are intended to have side effects.

Take the case of a function which returns a boolean value to indicate
whether its side effects succeeded or not (a common idiom in C based
languages). It is conceptually indistinguishable from a function which
returns void and transmits success or failure in some other way, such as
by exceptions in C++.

This distinction seems to come from early languages for batch
processing. Most modern languages intended to provide some support for
composability (ie all of them) don't bother to try making a distinction,
nor do early functional languages such as lisp (indeed I am pretty
certain that the Structure and Interpretation of Computer Languages
applies "function" only to mathematical functions and "procedure" to
their practical expression in computer code - in any event "procedure"
is the universally applied term in lisps). C++ certainly doesn't make a
distinction.

Chris

[Chris Vine]

On Fri, 26 Jun 2015 11:50:59 +0100
Chris Vine <chris@cvine--nospam--.freeserve.co.uk> wrote:
[snip]

> Structure and Interpretation of Computer Languages

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Structure and Interpretation of Computer Programs. My bad.

Chris

[alf.p.s...@gmail.com]

On Friday, June 26, 2015 at 3:24:34 PM UTC+2, Stefan Ram wrote:
> Öö Tiib <oot...@hot.ee> writes:
> >The difference between subprograms that return something
> >and the ones that return nothing feels to be not about return
> >type but about fact that the lack of return means that it *must*
> >have side effect by other means to be not worthless.
>

> That is not always so. For example, think of a printer
> framework that requires a callback to be invoked right
> before printing a page. So you open the framework with
>
> FRAMEWORK framework = new_framework( callback );
>
> . Incidentally, this time, you do not want additional action
> done before a page is being printed. So, you define:
>
> void callback() {}
>
> . This function has no return value and no effect
> (what you call »side effect«), yet it's perfectly
> worthwhile. It tells the framework that nothing has
> to be done before printing a page.

This is IMO a good observation, but only as a "do note that there are some exceptions" observation to novice readers. Öö Tiib is very well aware of dummy procedures, as am I, and indeed as any competent C++ programmer is, but in a debate, as opposed to when writing a textbook (say), pointing out all kinds of details that a novice might be unaware of is generally counter-productive, and might even be construed as condescending or patronizing. I am sure that the assumption that everybody would understand, is why it wasn't mentioned.

A perhaps more interesting example than a dummy callback, is a procedure used only for formal ODR "use" of its arguments, like this:

// With Visual C++ use "/W4", with g++ use "-Wall -Wextra".
template< class... Args >
void intentionally_unused( Args&&... ) {}

struct Base
{
virtual void foo( int n, char const* const id = "<no id>" ) const

#ifdef NO_WARNING
{ intentionally_unused( n, id ); } // A do-nothing default impl.
#else
{} // A do-nothing default impl.
#endif

};

auto main() -> int
{}

In the general case though, a procedure with no side effects is worthless, so it's a fair assumption that a procedure (void function) is designed for side effects -- as indeed the general purpose of a void callback is...

> >Technically subprograms that return nothing are indeed
> >subtype of ones that return something but in programming
> >logic it feels as upside down like thinking of statements as
> >subtype of expressions.
>

> In C++, there is no statement that is an expression and
> vice-versa.

That is incorrect in this informal context. Maybe you're thinking of the grammer-formal view that one must add a semicolon to an expression to get a statement. But if that's what you mean, then that was obviously assumed to be implicitly understood by the reader, for the notion of subset.

An expression used as a statement is called an "expression-statement" in the C++ grammar. The simplest example is perhaps

0;

Expression statements, the support for just discarding a value /by default/, are much of the reason why return types are ignored wrt. overload resolution.


> Processors have operations that have pre- and
> post-conditions. Higher programming languages usually try to
> fit some of this into algebraic notation, especially the
> mathematical notation of function application (therefore,
> »FORTRAN« = »formula translator«), but there are some
> mismatches between these two models.

Uhm, I didn't quite understand what you meant here, but no matter (I hope).

[Rosario19]

On Mon, 22 Jun 2015 19:08:27 -0700 (PDT), alf.p wrote:

> static char const* const operators[] = {"", " + ", " - "};

for me this is abomination
i refuse to think to const*const
i not find 1 useful use of const in all the few C++ or C i wrote
except for make the compiler compile some operator code

[Richard]

[Please do not mail me a copy of your followup]

Rosario19 <R...@invalid.invalid> spake the secret code
<3rtqoatc5ese89v68...@4ax.com> thusly:

I completely disagree.
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
The Terminals Wiki <http://terminals.classiccmp.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>

[Rosario19]

On Fri, 26 Jun 2015 18:04:09 +0200, Rosario19 <R...@invalid.invalid>
wrote:

all "private" "const" key word and all for limit the freedom of the
programmer for access to some variable, or some function, is just
wrong by disegn

[Richard]

[Please do not mail me a copy of your followup]

Rosario19 <R...@invalid.invalid> spake the secret code

<d8uqoad50f0208e27...@4ax.com> thusly:

Again, I completely disagree.

From this comment and several others you have posted lately, I think
you are in the wrong newsgroup.

You want comp.lang.asm.x86

[Mr Flibble]

In modern C++ macros are a sign of noobishness and should be avoided.
Also if "Base" is used with both "NO_WARNING" defined and not defined in
different translation units then your program is exhibiting undefined
behaviour as you are breaking the ODR rule.

/Flibble

[Rosario19]

On Fri, 26 Jun 2015 18:10:10 +0200, Rosario19 <R...@invalid.invalid>

yes i can be wrong on above, infact

the access of goto to only labels inside only the function where
that goto it is
is usefull in assembly too

[alf.p.s...@gmail.com]

Mr. Flibble, a.k.a. Leigh Johnston, most people consider the context when they evaluate a statement. For example, the answer "no" depends on the context. It is IMHO a good idea to always strive to consider the context.

The context here is example code to demonstrate two possible compiler behaviors.

Using a macro symbol to choose between two possibilities in such example code is perfectly OK. The alternative would be to provide two complete programs differing only in that single detail, or to give the reader the responsibility to edit the code to produce those two programs, which would be more work for the reader and without a guaranteed result. Defining a macro symbol or not is comparatively easy to do for the reader and guarantees the result (under other assumptions), and I guess that's what you failed to understand here.

> Also if "Base" is used with both "NO_WARNING" defined and not defined in
> different translation units then your program is exhibiting undefined
> behaviour as you are breaking the ODR rule.

I am not sure that you didn't INTEND to snip the "main" function that showed this to be a program example, since the snipping of one single line would otherwise appear to be unnecessary, and since you do refer to the code as a "program", but I hold open the possibility that it's due to a misunderstanding, something basic that was not understood; e.g., you might have thought that this was a header file, and with e.g. dyslexia (which you might have, like our king Olav had) you might have failed to see that the "main" function was in fact a "main" function, and then you might have just written "program" out of habit, thinking all the while that this was code in a header file. Not that your attempted point would have been relevant even with the misunderstanding that this was a header file. But with the misleading and otherwise unnecessary snipping it's less clear that the attempted misleading point is irrelevant.

Example code that demonstrates a feature is usually (and in this case) very different from production code. This particular code showed how warnings could be produced, and one way to silence them, as one possible use of a procedure with no side effects. In production code one does not usually add support to invoke one or another possible compiler behavior, and I guess that this was what you failed to notice for your second paragraph -- still assuming that the misleading snipping was not intentional.

Cheers & hth.,

- Alf (as you can see, accessing this group via GG I do see your postings).

[Mr Flibble]

On 26/06/2015 21:20, alf.p.s...@gmail.com wrote:

>
> Using a macro symbol to choose between two possibilities in such example code is perfectly OK.

No it isn't; macros should be avoided. How is a newbie supposed to know
that you didn't mean to use macros when you used macros?

>
>
>> Also if "Base" is used with both "NO_WARNING" defined and not defined in
>> different translation units then your program is exhibiting undefined
>> behaviour as you are breaking the ODR rule.
>

> Example code that demonstrates a feature is usually (and in this case) very different from production code.

Macros are bad, period, be it example code or production code.

>
> Cheers & hth.,
>
> - Alf (as you can see, accessing this group via GG I do see your postings).

Trollololol.

/Flibble

[Ian Collins]

Mr Flibble wrote:
> On 26/06/2015 21:20, alf.p.s...@gmail.com wrote:
>
>>
>> Using a macro symbol to choose between two possibilities in such example code is perfectly OK.
>
> No it isn't; macros should be avoided. How is a newbie supposed to know
> that you didn't mean to use macros when you used macros?

So all of your system and standard library headers are bad code?

--
Ian Collins

[Öö Tiib]

On Friday, 26 June 2015 13:51:09 UTC+3, Chris Vine wrote:
> On Fri, 26 Jun 2015 02:22:46 -0700 (PDT)
> Öö Tiib <oot...@hot.ee> wrote:
> [snip]
> > The difference between subprograms that return something
> > and the ones that return nothing feels to be not about return
> > type but about fact that the lack of return means that it *must*
> > have side effect by other means to be not worthless.
> >
> > Technically subprograms that return nothing are indeed
> > subtype of ones that return something but in programming
> > logic it feels as upside down like thinking of statements as
> > subtype of expressions.
>
> If this distinction between "procedure" and "function" is to have any
> logic, the word "function" should be applied to functions which are
> referentially transparent and so analogous to mathematical functions
> and "procedure" to those which are intended to have side effects.

In C++14 we can mark at least some of the pure functions (as opposed
to subroutines that happen to have OUT parameter) with 'constexpr'.

> Take the case of a function which returns a boolean value to indicate
> whether its side effects succeeded or not (a common idiom in C based
> languages). It is conceptually indistinguishable from a function which
> returns void and transmits success or failure in some other way, such as
> by exceptions in C++.

Yes. In C++ we can indicate fatal failure with exception so we have less
need for such return values and for checking those.

> This distinction seems to come from early languages for batch
> processing. Most modern languages intended to provide some support for
> composability (ie all of them) don't bother to try making a distinction,
> nor do early functional languages such as lisp (indeed I am pretty
> certain that the Structure and Interpretation of Computer Languages
> applies "function" only to mathematical functions and "procedure" to
> their practical expression in computer code - in any event "procedure"
> is the universally applied term in lisps). C++ certainly doesn't make a
> distinction.

Yes, but that does not matter if programming language makes distinction
or not. We are always far above of it. There are plenty of programming
languages that do not make distinction between immutable and mutable
objects or do not make distinction between virtual and non-virtual methods.
So what? Are these useless programming languages? No. The concepts are
still there, programmer just takes care if tool doesn't help.

So ... majority of objects are immutable and majority of methods are
non-virtual and the difference between function and procedure is still
like between noun and verb, regardless of programming language.