26
\$\begingroup\$

My stovetop has 10 different settings of heat (0 through 9) and a very odd way of cycling through them.

  • When I hit plus (+) it increments the number, unless the number is 9 in which case it becomes 0, or the number is 0 in which case it becomes 9.

  • When I hit minus (-) it decrements the number, unless the number is zero in which case it becomes 4.

There are no other temperature control buttons.

So when I am cooking on one temperature and I want to change to another, it's always a bit of a puzzle to figure out what the easiest way to get to that temperature is.

In this challenge you will take a starting temperature and a desired temperature and give the shortest sequence of button presses to get from the starting temperature to the desired temperature.

You should take input as two integers on the range 0-9 and output a sequence of instructions. You may output the instructions either as the characters/strings + and - or as the numbers 1 and -1. If there are two equally minimal sequences you may output either or both.

This is so the goal is to minimize the size of your source code as counted by the number of bytes.

Test cases

0 0 -> ""
0 1 -> "----"
0 2 -> "---"
0 3 -> "--"
0 4 -> "-"
0 5 -> "-+"
0 6 -> "-++"
0 7 -> "+--"
0 8 -> "+-"
0 9 -> "+"
1 0 -> "-"
1 1 -> ""
1 2 -> "+"
1 3 -> "++"
1 4 -> "--"
1 5 -> "--+"
1 6 -> "--++"
1 7 -> "-+--"
1 8 -> "-+-"
1 9 -> "-+"
2 0 -> "--"
2 1 -> "-"
2 2 -> ""
2 3 -> "+"
2 4 -> "++"
2 5 -> "+++"
2 6 -> "++++"
2 7 -> "+++++" or "--+--"
2 8 -> "--+-"
2 9 -> "--+"
8 0 -> "++"
8 1 -> "++----"
8 2 -> "++---"
8 3 -> "++--"
8 4 -> "++-"
8 5 -> "---"
8 6 -> "--"
8 7 -> "-"
8 8 -> ""
8 9 -> "+"
9 0 -> "+"
9 1 -> "+----"
9 2 -> "+---"
9 3 -> "+--"
9 4 -> "+-"
9 5 -> "+-+"
9 6 -> "---"
9 7 -> "--"
9 8 -> "-"
9 9 -> ""
\$\endgroup\$
5
  • 7
    \$\begingroup\$ Related: codegolf.stackexchange.com/q/218360 \$\endgroup\$
    – Neil
    Feb 8 at 11:04
  • \$\begingroup\$ Can we output as 0 for - and 1 for +? \$\endgroup\$
    – Jitse
    Feb 8 at 15:36
  • \$\begingroup\$ @Jitse You can output -1 and 1. \$\endgroup\$
    – Wheat Wizard
    Feb 8 at 15:37
  • 2
    \$\begingroup\$ FWIW, the only cases where 2 distinct solutions exist are (2,7), (3,8), (4,9) and (5,0). (And +++++ is one of the solutions for all of them.) \$\endgroup\$
    – Arnauld
    Feb 8 at 17:11
  • 1
    \$\begingroup\$ Is this actually how it works in real life? \$\endgroup\$ Feb 10 at 2:05

14 Answers 14

10
\$\begingroup\$

JavaScript, 146 144 bytes

(a,b)=>{for(z=2;i=a;++z){y=z.toString(2).slice(1);for(x of y)i=x>0?i++?i%10:9:i--?i:4;if(i==b)return a-b?y[r='replaceAll'](0,'-')[r](1,'+'):''}}

Demo

This snippet recreates the test cases from the post.

let f =

(a,b)=>{for(z=2;y=z.toString(2,i=a).slice(1);++z){for(x of y)i=x>0?i++?i%10:9:i--?i:4;if(i==b)return a-b?y[r='replaceAll'](0,'-')[r](1,'+'):''}}

// Test all cases from the original challenge
for (const startVal of [0,1,2,8,9]){
    for (const endVal of [...Array(10).keys()]){
        console.log(`${startVal} ${endVal} -> "${f(startVal,endVal)}"`)
    }
}

Explanation

This is my first time golfing, but hey, there has to be a first time for everything.

To explain the code, I'll first format the code and rename variables:

function stove(startVal, endVal) {
    for (iterator = 2; y = iterator.toString(2, currentVal = startVal).slice(1); ++iterator) {
        for (x of y) currentVal = x > 0 ? currentVal++ ? currentVal % 10 : 9 : currentVal-- ? currentVal : 4;
        if (currentVal - endVal == 0) return startVal-endVal?y[r = 'replaceAll'](0, '-')[r](1, '+'):''
    }
}

and then break it apart to a non-golfed version with comments

function stove(startVal, endVal) {
    // Iterate through all possible stove inputs, starting from the shortest
    for (let iterator = 2; true; iterator++) {
        // Reset the currentVal variable every loop
        let currentVal = startVal;

        // Convert iterator to binary to convert it to stove inputs later on
        let bin = iterator.toString(2);
        // Start the iterator at 2 and remove the first character
        // This allows for combinations such as 000/--- to appear when they normally wouldn't
        let buttonSequence = bin.slice(1);

        // Run the stove simulation
        for (const button of buttonSequence) {
            currentVal = button > 0 ? currentVal++ ? currentVal % 10 : 9 : currentVal-- ? currentVal : 4
        }

        // If currentVal and endVal are the same, meaning we've reached the desired end state
        if (currentVal - endVal == 0) {
          // Replace ones and zeroes in the button combination with plusses and minuses, then return
          // If currentVal and endVal are the same, return '' instead, because no button pushes are required
          return (startVal-endVal) ? buttonSequence.replaceAll('0', '-').replaceAll('1', '+') : '';
        }
    }
}

Funnily enough, implementing the game was the easiest part, i=x>0?i++?i%10:9:i--?i:4 runs one round of the entire game, so here's a breakdown of that:

// This is true for the string '1' and false for '0'
if (button > 0) {
    // The + button was pressed
    if (currentVal > 0) {
        // If the value is not 0, increase it by one and mod 10 so 9 becomes 0
        currentVal = (currentVal + 1) % 10;
    } else {
        // If the value is 0, set it to 9 as the rules require
        currentVal = 9;
    }
} else {
    // The - button was pressed
    if (currentVal > 0) {
        // If the value is not 0, decrease it
        currentVal--;
    } else {
        // If the value is 0, set it to 4
        currentVal = 4;
    }
}
\$\endgroup\$
1
  • 5
    \$\begingroup\$ Welcome to Code Golf, and nice answer! Can you shorten i-b==0 to i==b? \$\endgroup\$ Feb 8 at 16:08
10
\$\begingroup\$

JavaScript (ES6),  88 86 75  74 bytes

Expects (desired_temp)(starting_temp).

b=>g=a=>a-b?"+-"[q=a>b^b<"7489001156"[a]^!a^a<4]+g(a?q?a-1:-~a%10:9>>q):""

Try it online! (test cases)

Try it online! (all cases, checked against an ungolfed brute force search)

How?

The most natural behavior is to hit + when the desired temperature \$b\$ is greater than the current temperature \$a\$, and to hit - when it's lower.

Below are all the cases where we need to do the opposite of the natural behavior, along with the corresponding test on \$b\$ according to \$a\$:

   | 0 1 2 3 4 5 6 7 8 9 | test
---+---------------------+-------
 0 | X X X X X X X - - - | b < 7
 1 | - - - - X X X X X X | b > 3
 2 | - - - - - - - - X X | b > 7
 3 | - - - - - - - - - X | b > 8
 4 | - - - - - - - - - - | none
 5 | - - - - - - - - - - | none
 6 | X - - - - - - - - - | !b
 7 | X - - - - - - - - - | !b
 8 | X X X X X - - - - - | b < 5
 9 | X X X X X X - - - - | b < 6

This can be encoded with the following lookup table:

[b < 7, b > 3, b > 7, b > 8,,, !b, !b, b < 5, b < 6][a]

By normalizing all tests to \$b<t_a\$ and inverting the result when \$a\in\{1,2,3\}\$, this can be further optimized to:

b < "7489001156"[a] ^ !a ^ a < 4

The result is XOR'ed (again) with the test a > b, leading to either \$0\$ for + or \$1\$ for -.

We then do a recursive call where \$a\$ is updated using the same logic as in my answer to the reverse challenge and keep going that way until \$a=b\$.

\$\endgroup\$
7
\$\begingroup\$

Haskell, 89 bytes

g s=f[[s]]
f((w:a):x)e|e==w=a|1>0=f(x++[w!d:a++[d]|d<-[1,-1]])e
9!1=0
0!1=9
0!_=4
t!d=t+d

Try it online!

\$\endgroup\$
5
\$\begingroup\$

JavaScript (node.js), 125 bytes

g=(q,r)=>(o=[],f=((v,r)=>!o[r]||v.length<o[r].length?(o[r]=v,f(v+'+',r?(r+1)%10:9),f(v+'-',r?r-1:4)):0),f('',q),q==r?'':o[r])

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Feb 8 at 15:33
5
\$\begingroup\$

JavaScript (Node.js), 65 bytes

t=>g=(s,o='',...r)=>s-t?g(...r,s%9?s+1:9-s,o+'+',s?s-1:4,o+'-'):o

Try it online!


Python 3, 82 bytes

f=lambda t,s,o="",*r:s-t and f(t,*r,[9-s,s+1][0<s<9],o+"+",[4,s-1][0<s],o+"-")or o

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Jelly,  28  25 bytes

o8r4¤+⁹ị@%⁵
ȷŒPḂo-烳⁼ɗƇḢ

A full program that accepts the from and to values which prints a list of -1s and 1s.

Don't try it online (it's checking \$2^{1000}\$ instruction strings, for golf!)

Try it online! (with a reduction from the powerset of \$1000\$ items to just \$12\$ so it runs in time)

Or try 10 at a time, from the given value to all others. (Takes about 20 seconds; as above, but also uses the register, ®, in place of the second program argument, , since that's not mutable.)

Lastly, this 26 byter that only forms strings up to length six is much faster.

How?

o8r4¤+⁹ị@%⁵ - Link 1, make a move: current value, V ([0,9]); button, B (+/-1)
 8r4¤       - [8,7,6,5,4]
o           - V logical OR that (either [V,V,V,V,V] or [8,7,6,5,4] if V=0)
     +⁹     - add B to each of those values
       ị@   - use B to index into that list
              (1-indexed and modular: if B=1 the first; if B=-1 the fourth)
         %⁵ - modulo 10

ȷŒPḂo-烳⁼ɗƇḢ - Main Link: from, F ([0,9]); to, T ([0,9])
ȷ             - 1000 (saves a byte over `12`)
 ŒP           - powerset (shorter strings come first)
   Ḃ          - modulo 2
    o-        - logical OR -1 (vectorises)
           Ƈ  - filter keep those for which:
          ɗ   -   last three links as a dyad - f(instruction, T)
        ³     -     first program argument, V
       ƒ      -     reduce [V]+instruction by:
      ç       -       call last Link (Link 1) as a dyad
         ⁼    -     equals T?
            Ḣ - head (gets a/the shortest string)
\$\endgroup\$
2
\$\begingroup\$

R, 149 bytes

Or R>=4.1, 135 bytes by replacing two function occurrences with \s.

function(a,b,x=combn(rep(-1:1,6),6),y=x[,apply(x,2,function(t){for(i in t)a=(a+i)%%10+"if"(i>0,8,-5)*i*!a;a==b})],z=y[,order(colSums(!!y))[1]])z[!!z]

Try it online!

Brute-force approach. Probably porting one of the clever non-brute-force solutions would be shorter.

Borrows some code from Xi'an's answer to the related challenge.

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

05AB1E, 29 27 bytes

®X‚6иæé.Δ¹svDy+T%Ƶ₆yè‚s_è}Q

Input as two separated integers; output as as a list of -1,1 for -+ respectively.

Try it online or verify all test cases.

Since I was curious: a hard-coded approach of all test cases would be 52 bytes in comparison:

•‡fsΣï6ÿIi†_³•„+-Åв•3o₂₁∞5û±Õ¸ôk,ƒ
cÆмÄœº•0š£ITβè

Input as a pair; output as a list of -+ characters.

Try it online or verify all test cases.

Explanation:

®X‚            # Push pair [-1,1]
   6и          # Repeat it 6 times as list: [-1,1,-1,1,-1,1,-1,1,-1,1,-1,1]
     æ         # Take the powerset of this
      é        # Sort it by length
.Δ             # Find the first/shortest list that is truthy for:
  ¹            #  Push the first input
   s           #  Swap so the list is at the top again
    v          #  Loop over each of its items `y`:
     D         #   Duplicate the current result
      y+       #   Add `y` to the copy
        T%     #   Modulo-10
      Ƶ₆       #   Push 194
        yè     #   Index `y` into it (1→9; -1→4)
          ‚    #   Pair the two together
           s   #   Swap so the result is at the top again
            _  #   Check if it's 0 (1 if 0; 0 otherwise)
             è #   Index it into the pair
    }          #  Close the loop
     Q         #  Check if it's now equal to the (implicit) second input
               # (after which the found list is output implicitly as result)
•‡fsΣï6ÿIi†_³•
            # Push 664379026224093486851406838200392383
 „+-Åв      # Convert it to custom base-"+-"
            # (basically convert it to base-2, and index into "+-")
  •3o₂₁∞5û±Õ¸ôk,ƒ\ncÆмÄœº•
            # Push 4321233211012234432210123454326543321011543233210
   0š       # Convert it to a list of digits, and prepend a 0
     £      # Split the list of "+-" into lists of that size
      I     # Push the input-pair
       Tβ   # Convert it from a base-10 list to an integer
         è  # Use that to index into the earlier list
            # (after which the list is output implicitly as result)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why Ƶ₆ is 194; •‡fsΣï6ÿIi†_³• is 664379026224093486851406838200392383; and •3o₂₁∞5û±Õ¸ôk,ƒ\ncÆмÄœº• is 4321233211012234432210123454326543321011543233210.

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

Python 3, 97 bytes

f=lambda a,b,*c:a!=b<10>len(c)and min((f((-i%7+3,a+i)[a>0]%10,b,*c,i)for i in(-1,1)),key=len)or c

Try it online!

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

Perl 5, 131 bytes

sub{($_,$w,$s,@t)=@_;@t=sort{length$$b[1]<=>length$$a[1]}@t,[$_?$_-1:4,"$s-"],[$_++?$_%10:9,"$s+"]and($_,$s)=@{pop@t}while$_-$w;$s}

Try it online!

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

Charcoal, 46 bytes

Nθ⊞υ⟦Nω⟧FυF²F¬⊙υ№λθ⊞υEι⎇ν⁺μ§+-κ⎇κ⊖∨μ⁵﹪⊕∨μ⁸χ⊟⊟υ

Try it online! Link is to verbose version of code. Takes the desired temperature first and the starting temperature second. Explanation:

Nθ

Input the desired temperature.

⊞υ⟦Nω⟧Fυ

Start a breadth-first search with the starting temperature and no button presses.

F²

Check each button.

F¬⊙υ№λθ

Stop processing once all the desired temperature has been found.

⊞υEι⎇ν⁺μ§+-κ⎇κ⊖∨μ⁵﹪⊕∨μ⁸χ

Calculate the next temperature and push that with its updated list of button presses.

⊟⊟υ

Output the button presses that reached the desired temperature.

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

Brachylog, 40 bytes

;X≜{∧1w₄&{0∧9!|9∧0|+₁}|∧_1w₄&{0∧4|-₁}}ⁱ⁾

Try it online!

Starting temperature through input variable, target temperature through output variable, prints solution at end of program (+3 bytes if the 1/-1 format doesn't extend to strings; if it's permitted with a separator just replace both ws with s). Brute-forces all sequences shortest first until one reaches the target.

Can probably be shorter. Checked against Arnauld's JS solution.

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

Python3, 168 bytes:

lambda *x:min(f(*x),key=len)
def f(a,b,c=''):
 if a==b:yield c
 if len(c)<10:
  yield from f([a+1,[9,0][a==9]][a in[0,9]],b,c+'+')
  yield from f([4,a-1][a!=0],b,c+'-')

Try it online!

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

T-SQL, 190 bytes

WITH C as(SELECT @ a,cast(''as VARCHAR(max))r
UNION ALL
SELECT(a+iif(a=0,4-5*~p/2,p))%10,r+CHAR(44-p)FROM
C,(VALUES(1),(-1))X(p)WHERE len(r)<6)SELECT
top 1r FROM C WHERE @2=a ORDER BY len(r)

Try it online

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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