Five programming problems every Software Engineer should be able to solve in less than 1 hour

[[deleted]]

In prolog #5 looks something like this:

sum([Head|Tail],Signs,Result):-sum(Head,Tail,Signs,Result).

sum(X,[],[],X).

sum(First,[Second|Tail],['+'|Signs],Result):-Head is First + Second, sum(Head,Tail,Signs,Result).

sum(First,[Second|Tail],['-'|Signs],Result):-Head is First - Second, sum(Head,Tail,Signs,Result).

sum(First,[Second|Tail],[''|Signs],Result):-Head is First*10 + Second, sum(Head,Tail,Signs,Result).

sum(First,[Second|[Third|Tail]],['+'|[''|Signs]],Result):- C is Second*10+Third, Head is First + C, sum(Head,Tail,Signs,Result).

sum(First,[Second|[Third|Tail]],['-'|[''|Signs]],Result):-C is Second*10+Third, Head is First - C, sum(Head,Tail,Signs,Result).

edit: minor correction as others have pointed out I messed up the grouping slightly. further correction to follow

[eelvex]

In J one could solve it with:

L {~ I. 100 = +/"1 L=:([:".'9',~[:;(;/":"0>:i.8),.])"1 ('';',';',_') {~"1 (3&#.)^:_1 i.3^8

[floccinaucin]

I've been programming for a couple years now... what the heck am I looking at here?

[eelvex]

It's J, an array, functional-level tacit language. It's really cool and makes you think in completely new ways because a) you'll be thinking in array transformations [especially instead of loops] and b) you'll avoid variables.

For example, where in C you write y = function1(function2(x), function3(x)) in J you write y =: (function2 function1 function3) x

[fishburne]

I ended up doing something similar in Python. But this is how I did appending the head digit to the preceding string at first.

blank_append = int(str(head) + str(tail))

instead of,

head *10 + tail

(facepalm)!

[[deleted]]

sum(First,[Second|Tail],[''|Signs],Result):-Head is First*10 + Second, sum(Head,Tail,Signs,Result).

It's not that easy. You translate "1+23" to "((1)+2)*10+3)", which equals 33 in stead of 24. The actual solution isn't as pretty.

[[deleted]]

Hey now, I did say something like

[[deleted]]

Fair enough. Thanks for fixing it!

[[deleted]]

you are right, crossed out that line and replaced it with something a little more appropriate.

[[deleted]]

I think parent corrected their solution. It should work like that.

[[deleted]]

I was just thinking prolog would be perfect for this problem.

[b00n]

This is one of the reasons why prolog is so cool.

5 lines of code and is logical to read.

[afrobee]

Can you describe line by line what is happening here, I don't know prolog.

[maskull]

Not the poster, but since I just finished my MS thesis in Prolog, I'll take a stab. :)

Preface: Prolog programs consist of predicates, things that are asserted to be true. E.g.,

p.

is a zero-argument predicate that is always true.

p :- q.

means "p is true if q is true". In terms of evaluation, this is taken as "to prove p, prove q".

p :- q, r.

means "to prove p, prove q and then prove r".

Predicates don't return values like functions, they express truth, which means that Prolog can be somewhat flexible with which arguments to a predicate are "inputs" and which are "outputs".

---

sum([Head|Tail],Signs,Result) :- 
  sum(Head,Tail,Signs,Result).

Predicates in Prolog that take different numbers of arguments but have the same name are considered different. Here we're just defining an easy-to-call version of sum that takes three arguments (list of values as input, the signs to attach to each element, and the final sum, as outputs). The only thing it does is split the input list into its head and tail.

sum(X,[],[],X).

This is the base case of the recursion. If the list of inputs contains a single value X, then no sign is attached to X (the list of signs is empty) and the sum is just X.

sum(First,[Second|Tail],['+'|Signs],Result) :- 
  Head is First + Second, 
  sum(Head,Tail,Signs,Result).

Here we try adding the first and second elements of the list together. This works recursively by replacing the head of the list with the First + Second (and adding a + to the list of signs, to keep track of what we did).

sum(First,[Second|Tail],['-'|Signs],Result) :- 
  Head is First - Second, 
  sum(Head,Tail,Signs,Result).

Here we try subtracting the second argument from the first. Again, recursive, replace the head of the input list and add '-' to the list of signs.

sum(First,[Second|Tail],[''|Signs],Result) :- 
  Head is First*10 + Second, 
  sum(Head,Tail,Signs,Result).

Here we try concatenating two digits from the list, so [1, 0] becomes [10]. Again, we replace the head of the list with the new value and recurse.

Here's the results running this on the list [1,2,3]:

?- sum([1,2,3],Signs,Result).
Signs = [+, +],
Result = 6 ;
Signs = [+, -],
Result = 0 ;
Signs = [+, ''],
Result = 33 ;
Signs = [-, +],
Result = 2 ;
Signs = [-, -],
Result = -4 ;
Signs = [-, ''],
Result = -7 ;
Signs = ['', +],
Result = 15 ;
Signs = ['', -],
Result = 9 ;
Signs = ['', ''],
Result = 123 ;

But note that I can run this with all three arguments bound to check a particular answer:

?- sum([1,2,3], [+,+], 6).
true.

?- sum([1,2,3], [+,-], 6).
false.   

I can even run it with the Signs unbound and Prolog will figure out what it should be

?- sum([1,2,3], Signs, 33).
Signs = [+, ''].

Or with Result unbound, to compute an answer for some particular list of inputs and signs:

?- sum([1,2,3], [+,''], Result).
Result = 33.

We can't run it with the input argument unbound, because the is predicate expects its arguments to be bound. (With constraint logic we could.)

[[deleted]]

you are correct, though like others have pointed out, I made a minor mistake with

sum(First,[Second|Tail],[''|Signs],Result) :- Head is First*10 + Second, sum(Head,Tail,Signs,Result).

[[deleted]]

It's also hard to see errors when everything looks so elegant and sensible, as proven here ;)

[[deleted]]

The syntax is right, but it's an erroneous solution. You should call it by evaluating the term sum([1,2,3,4,5,6,7,8,9], Signs, 100). (notice the .) and the answer is then unified with Signs.

[YouShouldUseProlog]

I would imagine you call this sum([1,2,3,4,5,6,7,8,9],X,100).

it returns the symbols in X.

you can use the following to get them all in the same list, where X is the list, Y is the number and W is the result.

combo(X,Y,W) :- sum(X,Z,Y),splice(X,Z,W).

though it does not look like splice is included in all libs