6
\$\begingroup\$

The Brits aren't exactly known for being good at memorizing stuff. That's why scientists need newspaper articles to find those who are, and that's why it shouldn't be a surprise that they forget more than a 1000 things per year, including phone numbers, addresses, birthdays and more. Now, it is your duty to help the Brits remember their numbers.

In a 2010 video by the BBC (from 0:32 to 1:10), a trick is explained on how to do just that:

First, the base-10 string of the number is partitioned into several smaller non-overlapping parts, which then individually fit into one of four categories (three in the video, including one residual category for this challenge). No part of the partition is allowed to start with a 0, except individual digits (This makes the challenge fairer for languages that only work with numbers and not with strings). Each category then has an associated cost. Your goal is to find the partition of the string such that the total cost is minimal, and output that partition. The four categories are:


1. Addition or multiplication:

Three or four digits in which the first two add or multiply to the third or, in case of a carry, the third and fourth digit.

Examples:

112   # 1 + 1 = 2
347   # 3 + 4 = 7
549   # 5 + 4 = 9
5510  # 5 + 5 = 10
606   # 6 + 0 = 6
9817  # 9 + 8 = 17
111   # 1 * 1 = 1
3412  # 3 * 4 = 12
5420  # 5 * 4 = 20
5525  # 5 * 5 = 25
600   # 6 * 0 = 0
9872  # 9 * 8 = 72

Cost:

  • Addition without carry: 2
  • Addition with carry: 3
  • Multiplication without carry: 3
  • Multiplication with carry: 5
2. Relation to a year:

Four digits that form an year considered to contain an important date. For the sake of this challenge, this is every year in which a British monarch died.

Exhaustive list:

1714, 1727, 1760, 1820, 1830, 1837, 1901, 1910, 1936, 1952, 1972, 2022

Cost:

  • 18th and 19th century: 4
  • 20th century: 2
  • 21st century: 1
3. Similarity to a symbol:

A sequence of numbers that look like a symbol. Since Unicode is too vast and symbols are ill-defined, we will instead use any sequence of four digits that is a British word if typed on a 7-segment display calculator that is then rotated 180°.

Exhaustive list (taken from this file, filtered by whether there is a C1-level Oxford Dictionary entry of the same exact name):

3215, 3507, 3573, 3705, 5507, 5508, 5537, 7105, 7108, 7718, 7735, 7738

Cost: 3

4. Residual digit

Any digit not part of such a pattern will be treated as a residual digit and be assigned a cost of 2.

Challenge

In this challenge, you will be given a non-negative number as input and will output the partition of the number such that it is as easy to remember as possible for a Brit, minimizing the total cost. If multiple equivalent partitions exit, you may choose arbitrarily.

You may take the input as a 64-bit (or wider) integer, a string containing the decimal representation or a list of decimal digits. You may output the partition as a list of numbers, or, if your language doesn't support lists, a Gödel-encoded list or similar. You may additionally output the cost, but this is neither required nor beneficial (I'd assume).

If your language has a builtin for generating optimal partitions for Brits to remember numbers, usage of it is not discouraged.

This is , so the shortest code (as measured in bytes) wins.

Test cases

Note that the test case's outputs are only examples and you might output a different output with the same cost. Note that if you calculate a partition with a different cost, your solution is most likely faulty.

Input Output Cost Cost explanation Explanation
1972 [1972] 2 = 2 Monarch died 20th century Death of Edward VIII
19729 [1972, 9] 4 = 2 + 2 Monarch died 20th century + Single digit Death of Edward VIII followed by a 9
1972022 [1, 9, 7, 2022] 7 = 2 + 2 + 2 + 1 Single digit x3 + Monarch died 21st century Lone 1, 9 and 7 followed by the death of Elizabeth II
92183721 [9218, 3721] 10 = 5 + 5 Multiplication with carry x2 9 * 2 = 18, 3 * 7 = 21
123 [123] 2 = 2 Addition without carry 1 + 2 = 3
44812 [4, 4812] 5 = 2 + 3 Single digit + Addition with carry 4 followed by 4 + 8 = 12
48123 [4812, 3] 5 = 3 + 2 Addition with carry + Single digit 4 + 8 = 12 followed by 3
1820224610 [1, 8, 2022, 4610] 8 = 2 + 2 + 1 + 3 Single digit x2 + Monarch died 21st century + Addition with carry 1 and 8 followed by the death of Elizabeth II and 4 + 6 = 10
4312370550707 [4312, 3705, 5, 0, 707] 14 = 5 + 3 + 2 + 2 + 2 Multiplication with carry + British word + Single digit x2 + Addition without carry 4 * 3 = 12, then the word 'sole', a five, a zero and 7 + 0 = 7
54202243215 [5420, 224, 3215] 10 = 5 + 2 + 3 Multiplication with carry + Addition without carry + British word 5 * 4 = 20, 2 + 2 = 4, and the word 'size'
171419012022 [1714, 1901, 2022] 7 = 4 + 2 + 1 Monarch died 18th-19th century + Monarch died 20th century + Monarch died 21st century The death of every female British monarch
171450119010112022 [1714, 5, 0, 1, 1901, 0, 1, 1, 2022] 19 = 4 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 1 Monarch died 18th-19th century + Single digit x3 + Monarch died 20th century + Single digit x3 + Monarch died 21st century The death of every female British monarch, interrupted by 5, 0, 1 in the first and 0, 1, 1 in the second position
99819918182022 [9981, 9918, 1, 8, 2022] 13 = 5 + 3 + 2 + 2 + 1 Multiplication with carry + Addition with carry + Single digit x2 + Monarch died 21st century 9 * 9 = 81, 9 + 9 = 18, lone 1 and 8 followed by the death of Elizabeth II
1248163264128 [1, 248, 1, 6, 326, 4, 1, 2, 8] 20 = 2 + 3 + 2 + 2 + 3 + 2 + 2 + 2 + 2 Single digit + Multiplication without carry + Single digit x2 + Multiplication without carry + Single digit x4
123512351235 [1, 235, 1, 235, 1, 235] 12 = 2 + 2 + 2 + 2 + 2 + 2 Single digit + Addition without carry + Single digit + Addition without carry + Single digit + Addition without carry
23550877187738 [2, 3, 5508, 7718, 7738] 13 = 2 + 2 + 3 + 3 + 3 Single digit x2 + British word x3 2 and 3, 'boss', 'bill', 'bell'
732133933917141760 [7321, 339, 339, 1714, 1760] 19 = 5 + 3 + 3 + 4 + 4 Multiplication with carry + Multiplication without carry x2 + Monarch died 18th-19th century x2

Computer-readable test cases without explanations

1972 -> [1972] 
19729 -> [1972, 9] 
1972022 -> [1, 9, 7, 2022] 
92183721 -> [9218, 3721] 
123 -> [123] 
44812 -> [4, 4812] 
48123 -> [4812, 3] 
1820224610 -> [1, 8, 2022, 4610] 
4312370550707 -> [4312, 3705, 5, 0, 707] 
54202243215 -> [5420, 224, 3215] 
171419012022 -> [1714, 1901, 2022] 
171450119010112022 -> [1714, 5, 0, 1, 1901, 0, 1, 1, 2022] 
99819918182022 -> [9981, 9918, 1, 8, 2022] 
1248163264128 -> [1, 248, 1, 6, 326, 4, 1, 2, 8] 
123512351235 -> [1, 235, 1, 235, 1, 235] 
23550877187738 -> [2, 3, 5508, 7718, 7738] 
732133933917141760 -> [7321, 339, 339, 1714, 1760] 

I express my deepest gratitude for your unwavering support during these challenging times faced by Great Britain. Your contributions to assisting impoverished, forgetful Britons are truly cherished and immensely valued. May God save the King! 🇬🇧 🇬🇧 🇬🇧 🇬🇧 🇬🇧

\$\endgroup\$
11
  • 2
    \$\begingroup\$ @Arnauld It explicitly says "No part of the partition is allowed to start with a 0, except individual digits". \$\endgroup\$
    – leo848
    Oct 25, 2023 at 11:15
  • 2
    \$\begingroup\$ To the people who downvoted this challenge, I would really like to hear feedback as to why. I really tried to make this challenge interesting and would love to improve it. \$\endgroup\$
    – leo848
    Oct 25, 2023 at 12:12
  • 2
    \$\begingroup\$ Please note that this kind of formatting for the test cases is discouraged. I personally think it looks great, though, so maybe you should add a copy-paste-friendly version below with just input -> output. \$\endgroup\$
    – Arnauld
    Oct 25, 2023 at 14:34
  • 6
    \$\begingroup\$ @leo848 I did not downvote, since I think this is a high-effort and clearly written challenge. But since you are asking for feedback, I am not a huge fan of these "pile on a million rules" style challenges, since they are often just multiple challenges in one. I think 2 in 1 (or more) challenges are only interesting if the parts "hang together" in interesting computational ways -- ie, there is the chance of finding higher level connections between them. Here, however, many of the rules seem arbitrary, distinct, and irreducible. \$\endgroup\$
    – Jonah
    Oct 25, 2023 at 15:06
  • 3
    \$\begingroup\$ @Jonah Thanks for the criticism, I can see that. However I think that arbitrary challenges can have the benefit of not having a single obvious way to solve it in every language, as is common for some mathematical questions. I already tried to explain all choices I made, and there are certainly some patterns to be found (perhaps not exploitable enough?). Also, I tried to base this challenge off the video in the beginning, which may not have been the best idea, but obviously limits the amount of choice I had for the different sets. \$\endgroup\$
    – leo848
    Oct 25, 2023 at 19:11

7 Answers 7

4
\$\begingroup\$

JavaScript (ES7), 274 bytes

Expects a string and returns the partition as an array of integers.

f=([v,...a],p=[],s=q=0,c="",[w,x,y,z]=c)=>(v&&!z&&f(a,p,s,c+v),c?f(a,[...p,c++],s+=x?/1(bn|c0|cx|el|ev|f2|gu|h3|ht|i9|it|k7)|2(hc|pg|ra|uy)|49[01u]|5(he|hh|y[fwz])/.test(c.toString(36))?w>2?3:1<<16/x:[w-+-x]==(y+=+w?[z]:f)?3-!z:[w*x]==y?z?5:3:1/0:2,v):v||q&&s>q?o:(q=s,o=p))

Try it online!

This gives alternate solutions for a few test cases.

Scoring method

We make sure that each part \$c\$ is made of at most 4 characters and split them into \$[w,x,y,z]\$.

  • If \$x\$ is not defined: this is a single digit ➝ the score is \$2\$.

  • We test all special patterns at once with the following regular expression applied to the base-36 representation of \$c+1\$:

    /1(bn|c0|cx|el|ev|f2|gu|h3|ht|i9|it|k7) // 1715 to 2023
    |2(hc|pg|ra|uy)                         // 3508 to 3706
    |49[01u]                                // 5508 to 5538
    |5(he|hh|y[fwz])/                       // 7106 to 7739
    

    If a match is found:

    • If \$w>2\$, this is a 'symbol' ➝ the score is \$3\$.
    • Otherwise the score is given by the expression 1<<16/x (\$1\$ for 2023, \$2\$ for 19xx, \$4\$ for 17xx or 18xx).
  • If \$w\neq0\$:

    • If [w-+-x]==y+[z], the score is either \$2\$ or \$3\$.
    • If [w*x]==y+[z], the score is either \$3\$ or \$5\$.
  • If none of the above worked out, the score is \$\infty\$.

Below is the corresponding code:

x ?
  /1(bn|c0|cx|el|ev|f2|gu|h3|ht|i9|it|k7)|2(hc|pg|ra|uy)|49[01u]|5(he|hh|y[fwz])/
  .test(c.toString(36)) ?
    w > 2 ?
      3
    :
      1 << 16 / x
  :
    [w - +-x] == (y += +w ? [z] : f) ?
      3 - !z
    :
      [w * x] == y ?
        z ?
          5
        :
          3
      :
        1 / 0
:
  2

Main function

f = (                // f is a recursive function taking:
  [v, ...a],         //   v = next digit, a[] = remaining digits
  p = [],            //   p[] = list of parts
  s =                //   s = score
  q = 0,             //   q = best score so far, or 0 if not defined
  c = "",            //   c = current part
  [w, x, y, z] = c   //   (w, x, y, z) = the 4 characters in c
) => (               //
  v && !z &&         // if v is defined and z is undefined,
  f(a, p, s, c + v), // do a recursive call where v is added to c
  c ?                // if c is not empty:
    f(               //   do another recursive call:
      a,             //     pass a[]
      [...p, c++],   //     append c (coerced to an integer) to p[],
                     //     then increment c
      s += ...,      //     update the score (see above)
      v              //     set c = v
    )                //   end of recursive call
  :                  // else:
    v ||             //   if v is defined
    q && s > q ?     //   or q != 0 and s > q:
      o              //     leave the final output o unchanged
    :                //   else:
      (q = s, o = p) //     update q to s and o to p
)                    //
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 114 bytes

.œDεεgÐVi·ë5;÷i•иΩÅjnÃñ8ä{5pqŒΩ&™ l
&5ƒZtøà₆é~λãÝαB‡~hq•žEвyk©(iy¬_iëR3äí©`+QY<*D_i\®`*QYD4Q+*D_I*+}뮎ζ›₂в@O]OWkè

Try it online or verify almost all test cases (the largest two are omitted because they'll timeout on TIO).

Explanation:

.œ                         # Get all partitions of the (implicit) input
  D                        # Duplicate it
   ε                       # Map over each partition:
    ε                      #  Inner map over each part:
     g                     #   Pop and push the length of the part
      Ð                    #   Triplicate this length
       V                   #   Pop one copy, and store it in variable `Y`
      i                    #   Pop another copy, and if it's 1:
       ·                   #    Double the length to 2
      ë                    #   Else (the length is >=2):
       5;                  #    Push 2.5 (halve 5)
         ÷                 #    Integer-divide the length by this 2.5
       i                   #    If this is 1 (aka the length was 3 or 4):
        •иΩÅjnÃñ8ä{5pqŒΩ&™ l\n&5ƒZtøà₆é~λãÝαB‡~hq•
                           #     Push compressed integer 2059679753934118777767891051414020721847227706932308941504785260793787677550089063849770927917
         žEв               #     Convert it to base-8192 as list: [2022,1901,1910,1936,1952,1972,3215,3507,3573,3705,5507,5508,5537,7105,7108,7718,7735,7738,1714,1727,1760,1820,1830,1837]
             yk            #     Get the index of the current part in this list
                           #     (or -1 if it's not in this list)
               ©           #     Store this index in variable `®` (without popping)
        (i                 #     If the index is -1:
          y                #      Push the current part again
           ¬               #      Push its leading digit (without popping)
          _i               #      If this leading digit is a 0:
                           #       (use the current part implicitly)
           ë               #      Else:
            R              #       Reverse the part
             3ä            #       Split it into three parts
               í           #       Reverse each part
                           #       (converts the part to a triplet: ABC→[C,B,A] and ABCD→[CD,B,A])
                ©          #       Store this triplet in variable `®` (without popping)
                 `         #       Pop and push the parts to the stack
                  +        #       Add the top two (B+A)
                   Q       #       Check if its equal to the other integer (C or CD)
                    Y<     #       Push the part's length - 1
                      *    #       Multiply it to the check
            D              #       Duplicate it
             _i            #       Pop and if it's 0:
               \           #        Discard the duplicated part
                ®          #        Push triplet `®` again
                 `*Q       #        B*A this time
                    YD4Q+  #        Push the part's length + (length==4)
                         * #        Multiply it to the check
               D           #        Duplicate it
                _          #        Pop and check whether its 0
                 I*        #        Multiply it to the input
                   +       #        Add it to the earlier value
              }            #       Close this if-statement
                           #       (implicit else: use the duplicated value)
         ë                 #     Else (the index was not -1):
          ®                #      Push the index again from variable `®`
           Žζ›             #      Push compressed integer 17749
              ₂в           #      Convert it to base-26 as list: [1,0,6,17]
                @          #      Check for each whether it's >= the index
                 O         #      Sum those checks together
                           #    (implicit else: the length is 2 or >=5)
                           #     (implicitly use the implicit input-integer)
   ]                       # Close all if-else statements and the nested maps
    O                      # Sum each inner list together
     W                     # Push the minimum of the sums (without popping the list)
      k                    # Get the (first) index of this minimum in the list of sums
       è                   # Use that to index into the list of partitions
                           # (after which this partition is output implicitly as result)

See this 05AB1E tip of mine (sections How to compress large integers? and How to compress integer lists?) to understand how the compressed integers and lists work.

\$\endgroup\$
3
\$\begingroup\$

Haskell, 560 bytes

i x=read[x]
r x c=(\(a,b)->(a+c,x:b)).f
m(a:b:c:l)|i a+i b==i c&&a/='0'=r[a,b,c]2l
 |i a*i b==i c&&a/='0'=r[a,b,c]3l
m(a:b:c:d:l)|i a+i b==read[c,d]&&a/='0'&&c/='0'=r[a,b,c,d]3l
 |i a*i b==read[c,d]&&a/='0'&&c/='0'=r[a,b,c,d]5l
m _=(maxBound::Int,[])
y(a:b:c:d:l)|elem[a,b,c,d]$words"1714 1727 1760 1820 1830 1837"=r[a,b,c,d]4l
 |elem[a,b,c,d]$words"1901 1910 1936 1952 1972"=r[a,b,c,d]2l
 |[a,b,c,d]=="2022"=r[a,b,c,d]1l
 |elem[a,b,c,d]$words"3215 3507 3573 3705 5507 5508 5537 7105 7108 7718 7735 7738"=r[a,b,c,d]3l
y(x:l)=r[x]2l
f[]=(0,[])
f l=min(m l)$y l

Ungolfed version:


import Data.Char
import Control.Arrow

type Partition = [String]

badResult :: (Int, Partition)
badResult = (maxBound, [])


optimalMemorization :: String -> (Int, Partition)
optimalMemorization [] = (0, [])
optimalMemorization xs = minimum $ map ($ xs) [math, relation]

recurse :: String -> String -> Int -> (Int, Partition)
recurse prefix rest cost = ((+ cost) *** (prefix :)) (optimalMemorization rest)

math :: String -> (Int, Partition)
math (a:b:c:xs)
    | digitToInt a + digitToInt b == digitToInt c && a /= '0' = recurse [a, b, c] xs 2
    | digitToInt a * digitToInt b == digitToInt c && a /= '0' = recurse [a, b, c] xs 3
math (a:b:c:d:xs)
    | digitToInt a + digitToInt b == read ([c, d]) && a /= '0' && c /= '0' = recurse [a, b, c, d] xs 3
    | digitToInt a * digitToInt b == read ([c, d]) && a /= '0' && c /= '0' = recurse [a, b, c, d] xs 5
math _ = badResult

relation :: String -> (Int, Partition)
relation (a:b:c:d:xs)
    | [a, b, c, d] `elem` ["1714", "1727", "1760", "1820", "1830", "1837"] = recurse [a, b, c, d] xs 4
    | [a, b, c, d] `elem` ["1901", "1910", "1936", "1952", "1972"] = recurse [a, b, c, d] xs 2
    | [a, b, c, d] == "2022" = recurse [a, b, c, d] xs 1
    | [a, b, c, d] `elem` ["3215", "3507", "3573", "3705", "5507", "5508", "5537", "7105", "7108", "7718", "7735", "7738"] = recurse [a, b, c, d] xs 3
relation (x:xs) = recurse [x] xs 2 -- Residual option

We pass around (Int, Partition)s where the Int is the cost and Partition is the answer. As we go, we take a min of these. min on tuples compares the first element first, so we always take a minimum cost element using the default Haskell comparison.

In terms of branching, we only have to check math (m in the golfed version) and relation (resp. y). relation checks the year condition and the symbol condition, which are mutually exclusive and hence safe to check together. math checks the four mathematical conditions in order: 3-digit sum, 3-digit product, 4-digit sum, 4-digit product. This order will always produce an optimal mathematical result.

Proof: If 3-digit sum succeeds, then 3-digit product just costs more and is not optimal. 4-digit sum cannot succeed since two numbers cannot add up to two different results simultaneously, and 4-digit product is not optimal because it's worse than just taking the 3-digit sum and treating the fourth digit as residual (2 + 2 vs. 5). If 3-digit product succeeds, then 4-digit sum must fail (sums are not larger than products), and 4-digit product must fail since the product can't be two different numbers. Finally, if 4-digit sum succeeds, it's better than 4-digit product by cost alone. ∎

So implement our main function optimalMemorization (resp. f) recursively. If the string is empty, cost is zero. Else, try math and relation and take the minimum cost between the two (if the cost is the same, we choose the string that would appear first in the dictionary, which is a harmless tiebreaker).

recurse (resp. r) is a helper function, since we always combine our results in the same way, so it's better to give this helper a name. i in the golfed version is just Data.Char.digitToInt, but it's shorter to write it ourselves rather than importing.

Our badResult is just the "failure" case (since the math rules might not even apply at all) and produces a memorization string with the worst possible cost. Unfortunately, in the golfed version, we need a ::Int here. It didn't have to be here, but we had to put a type annotation somewhere, because without specifying that our math is being done with integers, all Haskell can tell is that our math is being done with some (Num a, Bounded a, Ord a) => a type, and it's ambiguous which one.

\$\endgroup\$
3
\$\begingroup\$

Jelly, 111 bytes

“ñJƈƑƁ€µlċ~vọẓɓ÷“©3“¿ẹ’,“¡¥Ƈæ½XṚỌ¢“?“¦ḍ’ḃ;@ƭ/€ÄFfḌ:ȷ2«21ị⁽⁵ȥD¤
3œṖS,PƊD⁼€ɗ/×2,3×LH_.ƲĊ;ÇoȷṂµLḤ$aL$Ḣ>2Ʋ?€S
ŒṖÇÞḢ

Try it online!

A monadic link that takes either an integer or a list of decimal digits and returns a list of lists of digits with the optimal score. If the output needs to be a list of integers, this can be done at the cost of one byte () at the end of the main link.

Explanation

“ñJƈƑƁ€µlċ~vọẓɓ÷“©3“¿ẹ’,“¡¥Ƈæ½XṚỌ¢“?“¦ḍ’ḃ;@ƭ/€ÄFfḌ:ȷ2«21ị⁽⁵ȥD¤  # ‎⁡Helper link 1: takes a list of digits and returns a score based on the two types of fixed four-digit integers, or zero if no match
“ñJƈƑƁ€µlċ~vọẓɓ÷“©3“¿ẹ’,“¡¥Ƈæ½XṚỌ¢“?“¦ḍ’                        # ‎⁢Compressed integer list of lists: [[105435108560611884151247538639414029, 1802, 3215], [15599387739683358002, 64, 1714]]
                                             €                  # ‎⁣For each list:
                                           ƭ/                   # ‎⁤- Reduce by doing the following alternately
                                        ḃ                       # ‎⁢⁡  - Convert to bijective base
                                         ;@                     # ‎⁢⁢  - Concatenate, in reverse order
                                              Ä                 # ‎⁢⁣Cumulative sum
                                               F                # ‎⁢⁤Flatten
                                                fḌ              # ‎⁣⁡Keep only those that match the helper link’s argument (after it’s been converted to an integer from decimal digits)
                                                  :ȷ2           # ‎⁣⁢Integer divide by 100
                                                     «21        # ‎⁣⁣Min of this and 21
                                                        ị⁽⁵ȥD¤  # ‎⁣⁤Index into 3,4,4,2,1 (⁽⁵ȥ encoded 34421 which is then split into decimal digits)

3œṖS,PƊD⁼€ɗ/×2,3×LH_.ƲĊ;ÇoȷṂµLḤ$aL$Ḣ>2Ʋ?€S                      # ‎⁤⁡Helper link 2: takes a list of lists of digits and works out the score for each sublist before summing them
                                        €                       # ‎⁤⁢For each list:
                                      Ʋ?                        # ‎⁤⁣- If the following is true:
                                aL$                             # ‎⁤⁤  - And list with its length (handles voiding lists that start with zero)
                                   Ḣ                            # ‎⁢⁡⁡  - Head
                                    >2                          # ‎⁢⁡⁢  - Is greater than 2
                            µ                                   # ‎⁢⁡⁣- Then:
3œṖ                                                             # ‎⁢⁡⁤  - Split before third list member
          ɗ/                                                    # ‎⁢⁢⁡  - Reduce this list using the following:
   S,PƊ                                                         # ‎⁢⁢⁢    - Sum paired with product
       D                                                        # ‎⁢⁢⁣    - Convert to decimal digits
        ⁼€                                                      # ‎⁢⁢⁤    - Check whether each equal to second half of list
            ×2,3                                                # ‎⁢⁣⁡  - Multiply by 2 (for addition) and 3 (for multiplication)
                ×    Ʋ                                          # ‎⁢⁣⁢  - Multiply by the following
                 LH                                             # ‎⁢⁣⁣    - Half the length of the list
                   _.                                           # ‎⁢⁣⁤    - Minus 0.5
                      Ċ                                         # ‎⁢⁤⁡  - Ceiling
                       ;Ç                                       # ‎⁢⁤⁢  - Concatenate to result of running helper link 1 on the original list
                         oȷ                                     # ‎⁢⁤⁣  - Or with 1000 (replaced zeros with 1000)
                           Ṃ                                    # ‎⁢⁤⁤  - Minimum
                             LḤ$                                # ‎⁣⁡⁡- Else: double the length of the list
                                         S                      # ‎⁣⁡⁢Sum

ŒṖÇÞḢ                                                           # ‎⁣⁡⁣Main link: takes an integer or a list of decimal digits and returns a list of lists of digits with the lowest score
ŒṖ                                                              # ‎⁣⁡⁤Partitions of list
  ÇÞ                                                            # ‎⁣⁢⁡Sort by results of helper list 2 on each partition
    Ḣ                                                           # ‎⁣⁢⁢Head
💎

Created with the help of Luminespire.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (Node.js), 315 bytes

g=([a,b,c,d,...x],v=W=0,L='')=>a?g(x,v+((0x148b65742d80bb478d07e4dd77f38b367e2a48dcc61f5efd8a935817bd574741de37e99f5b1b08aan+a).match(/..../g).includes(P=a+b+c+d)?a<2?b<9?2:4:a<3||3:[a- -b]==c+d?3:[a*b]==c+d?5:9),L+P+' ')+g([d,...x],v+(c-a-b?c-a*b?9:3:2,L+a+b+c+' '))&&g([b,c,d,...x],v+2,L+a+' '):v<W|!W?(W=v,R=L):R

Try it online!


JavaScript (Node.js), 268 bytes

Old answer, doesn't output solution and faultfully

f=([c,...x],s='')=>c?Math.min(f(x,s+=c),f(x)+('171417271760182018301837190119101936195219722022321535073573370555075508553771057108771877357738'.match(/..../g).includes([A,B,C,D,E]=s)?s<1900?4:s<3e3?3-A:3:B?!+A|E?1/0:A- -B==C+[D]?D?3:2:A*B==C+[D]?D?5:3:1/0:2)):s?1/0:0

Try it online!

f(string left, to encode)

\$\endgroup\$
2
  • 2
    \$\begingroup\$ From the ATO, this looks like it returns a number. In case it wasn't clear, you should return the partition itself. I may also have misunderstood the code though. \$\endgroup\$
    – leo848
    Oct 25, 2023 at 12:09
  • 1
    \$\begingroup\$ (0x148b65742d80bb478d07e4dd77f38b367e2a48dcc61f5efd8a935817bd574741de37e99f5b1b08aan+'') saves a few bytes \$\endgroup\$
    – emanresu A
    Oct 25, 2023 at 20:50
2
\$\begingroup\$

Charcoal, 156 bytes

≔⟦⟦⁰S⟧⟧θFθ«≔⊟ιη¿ηF⊞O⁺E⪪”)¶≕⁰∨℅U:.ï4◧Π-⊙⁵z›“Dνq⬤◧≦rS=≦:nW→NEE⊕ζTΣ✂aH⟲“↶¿!⧴p↘Y”⁵⪪κ⁴E∧›η1⟦Σ…η²Π…η²⟧⟦⁺…η²κ×⊕λLκ⟧⟦…η¹2⟧F¬⌕η§κ⁰⊞θ⁺Eι⎇νμ⁺Σ⊟κμ⟦…ηL§κ⁰✂ηL§κ⁰⟧⊞υι»✂⌊υ¹

Try it online! Link is to verbose version of code. Gives alternative results for two of the inputs. Explanation:

≔⟦⟦⁰S⟧⟧θFθ«

Perform a breadth first search over partitions starting with no partitions yet and a score of zero.

≔⊟ιη

Get the next unpartitioned suffix.

¿η

If it wasn't empty:

F⊞O⁺E⪪”...”⁵⪪κ⁴E∧›η1⟦Σ…η²Π…η²⟧⟦⁺…η²κ×⊕λLκ⟧⟦…η¹2⟧

Loop over three lists: a) A list of years and symbols, with their scores b) If the suffix does not begin with 0, then a list of additions and products, with their scores c) A list of the first digit with a score of 2.

F¬⌕η§κ⁰

If the suffix starts with this potential partition, then...

⊞θ⁺Eι⎇νμ⁺Σ⊟κμ⟦…ηL§κ⁰✂ηL§κ⁰⟧

Push the updated partition and score to the search list.

⊞υι

But if it was empty, then collect the completed partition in the predefined empty list.

»✂⌊υ¹

Output the partition with the lowest score, tied by shortest length of the first different substring.

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

Ruby -nl, 380 bytes

Probably the wrong approach to use. Creates a recursive function that checks the input against a gigantic regex sequence, cutting off valid pieces and comparing the scores to find the smallest one. Then, feed input from STDIN into that function and print the result.

r=(r=*1..9).product([0]+r)
f=->i,*k{i=~/(2022)|19(01|10|36|52|72)|18(20|30|37)|(3215|3507|3573|3705|550[78]|5537|710[58]|7718|773[58])|17(14|27|60)|(#{r.map{|a,b|[a,b,a+b]*''}*?|})|(#{r.map{|a,b|[a,b,a*b]*''}*?|})|(.)/
k=*$&;l=$&.size/4
s=$6?2+l:$7?3+2*l:[p,$1,$2||$8,$4,$3||$5].index{_1}
(n,v=f[$'];k+=n;s+=v)if$'[0]
i[1]&&(n,v=f[i[1..]];s>v+2&&[[i[0]]+n,v+2])||[k,s]}
p f[$_][0]

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.