11
\$\begingroup\$

Given two natural numbers (less than 100) as input print the sequence of intermediate results obtained when computing the sum of the two numbers using only the following operations1:

  • n <-> (m+1) for integers nand m satisfying that equation
  • (a+b)+c <-> a+(b+c) for integers a,b and c (associative law)

You are not allowed to use the commutative law (swapping the arguments of +)

Example

5+3           # Input
5+(2+1)       # 3 = 2+1
(5+2)+1       # Associative law
(5+(1+1))+1   # 2 = 1+1
((5+1)+1)+1   # Associative law
(6+1)+1       # 5+1 = 6
7+1           # 6+1 = 7
8             # 7+1 = 8

Rules

  • Input: two natural numbers (positive integers)
  • Output list of all intermediate steps in the calculation of the sum (using the rules defined above), you may omit the final result
  • The expressions can be output in any reasonable format (the left and right operands of each + should be clearly determinable)
  • You can choose the order in which the operations are applied as long as you reach the final result
  • Each expression in the output has to be obtained from the previous expression by applying exactly one allowed operation to the previous operation
  • This is the shortest code wins

Test cases

infix notation:

2+2 -> 2+(1+1) -> (2+1)+1 -> 3+1 -> 4
3+1 -> 4
1+3 -> 1+(2+1) -> 1+((1+1)+1) -> (1+(1+1))+1 -> ((1+1)+1)+1 -> (2+1)+1 -> 3+1 -> 4
1+3 -> 1+(2+1) -> (1+2)+1     -> (1+(1+1))+1 -> ((1+1)+1)+1 -> (2+1)+1 -> 3+1 -> 4
5+3 -> 5+(2+1) -> (5+2)+1     -> (5+(1+1))+1 -> ((5+1)+1)+1 -> (6+1)+1 -> 7+1 -> 8

postfix notation:

 2 2+ -> 2 1 1++ -> 2 1+ 1+ -> 3 1+ -> 4
 3 1+ -> 4
 1 3+ -> 1 2 1++ -> 1 1 1+ 1++ -> 1 1 1++ 1+ -> 1 1+ 1+ 1+ -> 2 1+ 1+ -> 3 1+ -> 4
 1 3+ -> 1 2 1++ -> 1 2+ 1+    -> 1 1 1++ 1+ -> 1 1+ 1+ 1+ -> 2 1+ 1+ -> 3 1+ -> 4
 5 3+ -> 5 2 1++ -> 5 2+ 1+    -> 5 1 1++ 1+ -> 5 1+ 1+ 1+ -> 6 1+ 1+ -> 7 1+ -> 8

Example implementation


1 The operations are based on the formal definition of additon but modified to work without the concept of a successor function.

\$\endgroup\$
3
  • \$\begingroup\$ Does this challenge fit in expression-building? \$\endgroup\$
    – bsoelch
    Nov 13, 2023 at 15:18
  • \$\begingroup\$ Thanks for clarifying... Should I delete my attempt? See here \$\endgroup\$
    – Tobias321
    Nov 14, 2023 at 12:42
  • 1
    \$\begingroup\$ @Tobias321 Yes, you can undelete it once you have found time to fix your solution \$\endgroup\$
    – bsoelch
    Nov 14, 2023 at 14:39

8 Answers 8

7
\$\begingroup\$

Jelly, 22 bytes

FṖ.ịoƲ€2¦ṁ¥,/ƭ$ƬṪ§Ƭ;@Ɗ

A monadic Link that accepts a pair of positive integers and yields a list of nested lists representing (much like the reference implementation) one way to perform their sum.

Try it online!

How?

FṖ.ịoƲ€2¦ṁ¥,/ƭ$ƬṪ§Ƭ;@Ɗ - Link: pair of positive integers, A = [n, m]
               Ƭ       - starting with X=A collect up while distinct under:
              $        -   last two links as a monad - f(X):
F                      -     flatten X
             ƭ         -     alternate between:
          ¥            -     (1) last two links as a dyad - F(Flat_X, X):
      €2¦              -           apply to second element, V, of X:
     Ʋ                 -             last four links as a monad - f(V):
 Ṗ                     -               pop -> [1 .. V-1]        or [] if V == 1
  .                    -               0.5
   ị                   -               index into -> [V-1, 1]   or [] if V == 1
    o                  -               logical OR V -> [V-1, 1] or  V if V == 1
            /          -     (2) reduce Flat_X by:
           ,           -           pair -> ...[[[[a,b],c],d],...]
                     Ɗ - last three links as a monad - f(StepsSoFar):
                Ṫ      -   tail -> removes and yields PreviousStep
                  Ƭ    -   starting with PreviousStep collect up while distinct under:
                 §     -     sums
                   ;@  -   append to the tailed StepsSoFar

Seems like the sums (§) could be performed within the first collect-loop (Ƭ), but I've not figured out a good way to do so...

\$\endgroup\$
6
\$\begingroup\$

Python, 98 bytes

f=lambda m,n:[f"{m}+{n}"]+([n:=n-1]*n and[f"{m}+({n}+1)",*(f"({x})+1"for x in f(m,n)),f"{m+n}+1"])

Attempt This Online!

-1 thanks to @STerliakov

Original Python, 100 bytes

f=lambda m,n:[f"{m}+{n}"]+(n-1and[f"{m}+({n-1}+1)",*(f"({x})+1"for x in f(m,n-1)),f"{m+n-1}+1"]or[])

Attempt This Online!

Outputs a list of strings in infix notation.

\$\endgroup\$
1
  • \$\begingroup\$ 99 by extracting n-1 into variable \$\endgroup\$
    – STerliakov
    Nov 15, 2023 at 2:09
4
\$\begingroup\$

Charcoal, 64 bytes

NθNηF⊖ηE²⪫⟦×(ιθ+×(κI⁻η⁺ικ×+1)κ×)+1ι⟧ω⮌Eη⪫⟦×(ι⁻⁺θη⊕ι+1×)+1ι⟧ωI⁺θη

Try it online! Link is to verbose version of code. Explanation:

NθNη

Input the two numbers.

F⊖ηE²⪫⟦×(ιθ+×(κI⁻η⁺ικ×+1)κ×)+1ι⟧ω

Output the steps that split the second number into units and associate them with the first number.

⮌Eη⪫⟦×(ι⁻⁺θη⊕ι+1×)+1ι⟧ω

Output the steps that add the units to the first number.

I⁺θη

Finish with the final sum.

\$\endgroup\$
2
\$\begingroup\$

Retina 0.8.2, 90 bytes

\d+
$*
+`\+1(1+)(.*$)
$&¶$%`+($1+1)$2¶($%`+$1)+1$2
+`\(?(1+)\+1\)?(.*$)
$&¶$%`1$1$2
1+
$.&

Try it online! Link is to test suite that outputs all the test cases. Explanation:

\d+
$*

Convert to unary.

+`\+1(1+)(.*$)
$&¶$%`+($1+1)$2¶($%`+$1)+1$2

Repeatedly convert x+<1y> into x+(y+1) and then (x+y)+1 until y is 1.

+`\(?(1+)\+1\)?(.*$)
$&¶$%`1$1$2

Repeatedly convert (x+1) into <1x>.

1+
$.&

Convert to decimal.

\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 99 bytes

x=>g=(y,a='',b=`
`)=>(--y?a+x+`+${y+1+b+a+x}+(${y}+1)`+b+g(y,'('+a,')+1'+b)+a:a)+x+++`+1${a?b:b+x}`

Try it online!

\$\endgroup\$
0
1
\$\begingroup\$

Python, 140 137 bytes

lambda x,y,a='',b='':(a+f"{x}+{y}{b}\n{a}{x}+({y-1}+1){b}\n{f(x,y-1,'('+a,b+')+1')}\n"if~-y else'')+a+f"{x+y-1}+1{b or chr(10)+str(x+y)}"

Attempt This Online!

A port of l4m2's JavaScript answer

\$\endgroup\$
0
1
\$\begingroup\$

Perl 5 (-lp), 135 bytes

1while print,s/\+(?!1\b)\d+/"+(".($&-1)."+1)"/e||s/(\d+)\+\((\d+)\+(\d+)\)/($1+$2)+$3/||(s/^[^+\d]*\K(\d+)\+1\b/$1+1/e,s/\((\d+)\)/$1/)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Scala 3, 153 bytes

def f(m:Int,n:Int):Seq[String]=n match{case 1=>Seq(s"$m+1");case _=>Seq(s"$m+$n")++Seq(s"$m+(${n-1}+1)")++f(m,n-1).map(x=>s"($x)+1")++Seq(s"${m+n-1}+1")}

Attempt This Online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.