9
\$\begingroup\$

The idea is based on this interactive game. Given a set of eight decimal digits which are not necessarily distinct, your task is to find a hyperjump trip with the specified length.

But what is a hyperjump? I ain't got time to click on HOW TO PLAY

Ok, you have a set of eight digits where none is 0 or 9. Let's say [1, 3, 6, 7, 8, 7, 7, 4]. The hyperjump is basically a sub-list of this list. A valid sequence can start at the left with any two numbers, e.g. 7, 7.

The next number must be the rightmost digit of a simple arithmetic operation (+ - * /) between the previous numbers of that sequence. For example:

7 + 7 = 14
7 / 7 = 1
7 - 7 = 0
7 * 7 = 49

So the next number can either be 4 or 1 because 0, 9 are not on the list. Let's choose 1:

7 - 1 = 6
7 + 1 = 8
7 / 1 = 7

By choosing 8 as the next number (7, 7, 1, 8) we have:

1 * 8 = 8
1 + 8 = 9
71 - 8 = 63

As you see, one can also combine the previous digits in the specified order to form a new number. Since there was just one 8 on the list, we can't choose it again. So the only option is 3. The resulting sequence can be expanded again by adding 4 (because 8 * 3 = 24) to get [7, 7, 1, 8, 3, 4]. The ultimate goal is to reach a 9 after n-steps, where n ∈ {5, 6, 7, 8}. Thus if n = 6 we have reached the desired hyperjumps trip since 83 - 4 = 79.

Challenge

You are given a list of eight digits in the range of 1..8 along with the number of steps n. Find a sub-list with length n that can form a hyperjump to 9.

  • The given set can have repeating elements.
  • The number of steps is either of 5, 6, 7, 8.
  • The sub-list can only use the elements of the main list (obviously!) and the number of repeating elements cannot exceed those in the main list. For example if the given list has three 7s, the hyperjump can have at most three 7s.
  • The inputs and output can be in any format that you are comfortable with. But the ordering of the output must be preserved.
  • Math operations must apply from left to right and negative results are not accepted. Hence a sequence cannot start with 6, 7, 1.
  • If no hyperjump exists, any kind of error message or an empty output is acceptable.
  • Standard rules apply.

Bonus point

You are a God if your program can find all possible hyperjumps with the specified length.

Examples:

list = [1, 3, 6, 7, 2, 7, 7, 4]; n = 5:
hyperjump = [7, 4, 3, 1, 2]

list = [1, 1, 8, 2, 2, 3, 4, 6]; n = 6:
hyperjump = [6, 2, 2, 1, 3, 4]

list = [5, 5, 5, 5, 5, 5, 5, 5]; n = 7:
hyperjump = []
\$\endgroup\$
12
  • \$\begingroup\$ Can we also combine several digits for the right operand (e.g. abc/de=f) or only for the left one? \$\endgroup\$
    – Arnauld
    Commented Apr 5, 2023 at 22:02
  • \$\begingroup\$ @Arnauld definitely yes! \$\endgroup\$ Commented Apr 5, 2023 at 22:06
  • \$\begingroup\$ Is / regular or integer division? I assume integer-division, but if not, do we take the last digit of the decimal value (e.g. will 4/5=0.8 result in 0 or 8 as right digit)? What about divisions where there is no last decimal digit (e.g. 4/7)? \$\endgroup\$ Commented Apr 6, 2023 at 6:58
  • 1
    \$\begingroup\$ The last 9 is not negative, because the previous numbers are combined. I said a sequence cannot start with 6,7,1. And you are right about the regular division allowed only for integer results @KevinCruijssen \$\endgroup\$ Commented Apr 6, 2023 at 7:13
  • 3
    \$\begingroup\$ @Jonathan TBH last night when I was going to sleep, I checked again and answered Arnaud's comment 😴. In the morning, I realized that I have messed up and given the wrong info, but IMO it was too late. So I see that based on that wrong info, the current answers are providing some wrong answers but I am too embarrassed to admit. Now that you have asked it again, I am really sorry to say that my first comment is wrong and the game won't accept such cases. I thought it was too rare to happen anyway. The second operand must always be a single digit. \$\endgroup\$ Commented Apr 6, 2023 at 13:04

4 Answers 4

4
\$\begingroup\$

JavaScript (ES6), 159 bytes

A version always using a single digit for the right operand, which apparently is the correct rule of the game.

a=>g=(n,o='',p,m)=>(n?a:[9]).some((v,i)=>m>>i&v<9|o>9&!a.some((_,i)=>[...'+-*/'].some(c=>(s=o.slice(i,-1))&&eval(s+c+p)%10==v))?0:n?g(n-1,o+v,v,m|1<<i):O=o)&&O

Try it online!


JavaScript (ES6), 175 bytes

Expects (list)(n). Returns either a string of digits, or false if there's no solution.

a=>g=(n,o='',m)=>(n?a:[9]).some((v,i)=>m>>i&v<9|o>9&!a.some((_,i)=>(h=j=>(s=o.slice(j))&&eval(o.slice(i,j)+'+-*/'[j*4&3]+s)%10==v|h(j+1/4))(i+1))?0:n?g(n-1,o+v,m|1<<i):O=o)&&O

Try it online!

Commented

a =>                   // a[] = input list of digits
g = (                  // g is a recursive function taking:
  n,                   //   n = counter
  o = '',              //   o = output string
  m                    //   m = bit mask of already used digits
) =>                   //
(n ? a : [9])          // using [9] for the last iteration or a[] otherwise,
.some((v, i) =>        // for each value v at index i:
  m >> i & v < 9 |     //   is the i-th bit of m set with v not equal to 9?
  o > 9 &              //   does o have at least 2 digits?
  !a.some((_, i) =>    //   for each entry in a[] at index i:
    ( h = j =>         //     h is a recursive function taking a pointer j
      (s = o.slice(j)) //     using j, extract the right operand s from o
      && eval(         //     unless s is empty, evaluate as JS code:
        o.slice(i, j)  //       the left operand (from i to j-1)
        + '+-*/'       //       followed by an operator
          [j * 4 & 3]  //       chosen according to the decimal part of j
        + s            //       followed by the right operand
      ) % 10 == v |    //     and test whether the result modulo 10 is v
      h(j + 1 / 4)     //     do a recursive call with j + 1/4
    )(i + 1)           //     initial call to h with j = i + 1
  ) ?                  //   end of some(); if the test fails:
    0                  //     do nothing
  :                    //   else:
    n ?                //     if there are more digits to add:
      g(               //       do a recursive call:
        n - 1,         //         decrement n
        o + v,         //         append v to o
        m | 1 << i     //         set the i-th bit of m
      )                //       end of recursive call
    :                  //     else:
      O = o            //       success: save o in O
) && O                 // end of some(); return either false or O
\$\endgroup\$
0
3
\$\begingroup\$

05AB1E, 40 bytes

.ÆʒV"+-*/"¹<ãεUYćsvyXNè.VDïθ}9Ê;)Ðd*ïQ}à

Slow brute-force. Inputs in the order \$n,list\$, and will output a list of all possible results (including duplicates); not because it's mentioned as Bonus point in the challenge description, but simply because it's 1 byte shorter. 😉

Try it online or verify all test cases with only the first valid result instead of all.

Explanation:

.Æ                      # Get all n-sized lists using items of the list, where `n` and
                        # the list are the first/second (implicit) inputs respectively
  ʒ                     # Filter this list of lists by:
   V                    #  Pop and store the current list in variable `Y`
                        #  (since we're gonna use it within an inner iterator)
   "+-*/"               #  Push the string of the four operands
         ¹<             #  Push the first input - 1
           ã            #  Get all input-1 sized combinations of operands
            ε           #  Map over each list of operands:
             U          #   Pop and store the current list of operands in variable `X`
             Y          #   Push digit-list `Y`
              ć         #   Extract head; push remainder-list and first item separately
               s        #   Swap so the remainder-list is at the top
                v       #   Loop over each digit of the remainder-list:
                 y      #    Push the current digit
                  XNè   #    Push the loop-index'th operand of list `X`
                     .V #    Evaluate and execute this operand as 05AB1E code
                 D      #    Duplicate the result
                  ï     #    Cast the copy to an integer to remove decimal values
                   θ    #    Pop and leave just its last digit
                }       #   After the loop:
                 9Ê     #   Check that the final digit is NOT 9 (0 if 9; 1 if [0-8])
                   ;    #   Halve this 0 or 1 to 0 or 0.5 respectively
             )          #   Wrap all values on the stack into a list
              Ð         #   Triplicate this list
               d        #   Check for each value whether it's non-negative (>=0)
                *       #   Multiply so all negative values in the list become 0s
                 ï      #   Cast all values to integers to remove decimal values
                  Q     #   Equals-check to verify the list is still the same
            }à          #  After the map: check whether any is truthy by taking the max
                        # (after which the filtered list is output implicitly as result)
\$\endgroup\$
2
\$\begingroup\$

Jelly, 36 bytes

ṖṪṭḌƊÐƤṖjþ“+_×÷”ẎVDṪ€
œ!;9e"ÇƤ$ṫ3ẠƲƇ

A dyadic Link that accepts the list of positive digits as integers on the left and the proposed length on the right and yields a list of all possible hyperjump solutions, including the duplicates available when there are repeated digits that may be used.

Try it online!

How?

Brute force checking.

ṖṪṭḌƊÐƤṖjþ“+_×÷”ẎVDṪ€ - Helper Link, get possibles for last digit: list, X
Ṗ                     - pop off the last digit (since it's the one we're aiming for)
     ÐƤ               - for each suffix:
    Ɗ                 -   last three links as a monad - f(S=suffix=[..., r]):
 Ṫ                    -     tail (S) and yield -> right operand = r (and S=[...])
   Ḍ                  -     convert (S) from base ten -> left operand = int([...])
                                                         (or 0 when nothing remains)
  ṭ                   -     tack -> [left operand, right operand]
       Ṗ              -   pop off the last result (removing the [0, r] which would
                                                   become e.g. "0+r", allowing any
                                                   repeated digit)
          “+_×÷”      -   list of characters = "+_×÷"
         þ            -   (operands list) table (characters) applying:
        j             -     (operands) join with (character)
                Ẏ     -   tighten to a list of equations
                 V    -   evaluate as jelly code -> list of results of the equations
                  D   -   convert the results to decimal
                   Ṫ€ -   tail each - note that this will be a negative digit if
                                      the equation result was negative
                                      (hence `DṪ€` rather than `%⁵`)

œ!;9e"ÇƤ$ṫ3ẠƲƇ - Main Link: list, L; integer N
œ!             - all permutations choosing N elements
             Ƈ - filter keep those of these "potentials" for which:
            Ʋ  -   last four links as a monad - f(potential):
  ;9           -     concatenate a nine
        $      -     last two links as a monad - f(potential):
       Ƥ       -       for each prefix:
      Ç        -         call the helper Link, above
     "         -       (potential) zip (that) applying:
    e          -         exists in?
         ṫ3    -     tail from index 3 on (remove the first two exists in checks)
           Ạ   -     all truthy?
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 125 114 113 bytes

⊞υ⟦⟦⟧θ⟧F⊕η«≔υθ≔⟦⟧υFθ«≔⊟κε≔⌊κδ≔↨δ⁰ζF⎇⁼ηι⟦⁹⟧Φχ№ελ¿∨‹ι²⊙Eδ↨✂δν⊖ι¹χ№﹪⟦∧μ⁺μζ∧›μζ⁻μζ×μζ∧¬﹪μζ÷μζ⟧χλ¿⁼ηιIκ⊞υ⟦⁺δ⟦λ⟧Φε⁻⌕ελν

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

⊞υ⟦⟦⟧θ⟧

Start a breadth-first search with a position of no digits in the list yet and the starting set.

F⊕η«

Loop over each step in the trip plus one for the last hyperjump to 9.

≔υθ

Save the list of previously found positions.

≔⟦⟧υ

Start recording a list of new positions.

Fθ«

Loop over the previous list of positions.

≔⊟κε

Get the set of remaining digits.

≔⌊κδ

Get the list of jumps so far.

≔↨δ⁰ζ

Get the last jump made, if any.

F⎇⁼ηι⟦⁹⟧Φχ№ελ

Loop over the remaining digits, or just 9 if this is the final hyperjump.

¿∨‹ι²

If this is one of the first two steps, or...

⊙Eδ↨✂δν⊖ι¹χ

... for any suffix of the previous jumps ...

№﹪⟦∧μ⁺μζ∧›μζ⁻μζ×μζ∧¬﹪μζ÷μζ⟧χλ

... any of the arithmetic operations results in a positive integer that ends with the desired digit, then:

¿⁼ηι

If this is the final hyperjump, then...

Iκ

... output the list, otherwise...

⊞υ⟦⁺δ⟦λ⟧Φε⁻⌕ελν

... save the position of the extended list and reduced set.

\$\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.