32
\$\begingroup\$

Platforms are stretches of - characters separated by one or more characters.

For example:

------ --    ------ -

The above has 4 platforms sizes 6, 2, 6 and 1.

Platforms that are not supported will fall. To be supported platforms need Jimmies.

Jimmies look like this:

\o/

They are three units wide. Don't ask me what supports Jimmies.

Jimmies go under platforms to support them:

------------------
\o/  \o/  \o/  \o/

Each platform has a "center" of mass which is the average position of all its -s. (Or the average of the start and end.)

A platform is supported by Jimmies if its center of mass is between two points of the platform above a Jimmy or exactly above part of a Jimmy.

For example:

-----
 \o/

The above platform is supported because the center of mass is in a place the Jimmy is touching.

----------------
  \o/        \o/

The above platform is also supported because its center of mass is between the two Jimmies.

----
 \o/

In the above example the center of mass is between the Jimmy's hand and the Jimmy's head and thus the platform is supported by that Jimmy.

The following platform is not supported:

----
  \o/

This is because its center of mass is not directly above any part of the Jimmy and there is no Jimmy to the left.

A Jimmy can help support multiple platforms:

------- -------------
\o/   \o/           \o/

Your task is to take as input platforms (consisting only of -s and s). And output the minimum number of Jimmies required to support all the platforms given.

This is so answers will be scored in bytes with fewer bytes being better.

Test cases

Each line has the input, > and then the output. Below I have added one way to place the Jimmies to support the platforms. This is neither part of the input nor output, it's just there for your convenience.

-------------------------------- > 1
              \o/
--------------- ---------------- > 2
      \o/              \o/
- ---------------------------- - > 2
\o/                          \o/
-  --------------------------- - > 3
\o/\o/                       \o/
--- - ------------------------ - > 3
\o/ \o/                      \o/
- ------------- -------------- - > 3
\o/           \o/            \o/
--------------- - -------------- > 3
      \o/       \o/          \o/
- - -  ------------------------- > 3
\o/ \o/           \o/
\$\endgroup\$
13
  • 1
    \$\begingroup\$ @JohanduToit The rightmost Jimmy supports the entire rightmost platform. \$\endgroup\$ Sep 11 at 12:41
  • 3
    \$\begingroup\$ or exactly above part of a Jimmy: so my understanding is that a Jimmy can support a platform with his head like that. Is that correct? \$\endgroup\$
    – Arnauld
    Sep 11 at 13:04
  • 2
    \$\begingroup\$ @Arnauld In that example the CoM of the platform is between the Jimmy's hand and their head, they are supporting it. A Jimmy could even support a 1 wide platform with only their head as well. \$\endgroup\$
    – Grain Ghost
    Sep 11 at 14:36
  • 7
    \$\begingroup\$ Don't ask me what supports Jimmies.: It's Jimmies all the way down! \$\endgroup\$
    – LorenDB
    Sep 11 at 21:14
  • 1
    \$\begingroup\$ @LorenDB all the way down to what???? \$\endgroup\$
    – Baby_Boy
    Sep 13 at 12:37

12 Answers 12

12
\$\begingroup\$

Jelly,  18 13  10 bytes

ḲẈṣ0H«1§ĊS

A monadic Link that accepts a list of characters and yields an integer.

Try it online!

How?

Jimmies can't help if the gap is greater than one, so the result is the sum of Jimmies required for each section after partitioning at such gaps. In each section, we need one Jimmy per platform minus one Jimmy for every two length-one platforms, since then Jimmies can share the load of these and any intermediate platforms.

ḲẈṣ0H«1§ĊS - Link: list of characters, P
Ḳ          - split at spaces
 Ẉ         - length of each -> lengths of platforms with zeros between sections
  ṣ0       - split at zeros -> list of section platform lengths
                               (potentially including phantom empty sections)
    H      - halve (vectorises)
     «1    - minimum with one (vectorises)
       §   - sums
        Ċ  - ceiling (vectorises)
         S - sum
\$\endgroup\$
8
\$\begingroup\$

ARM T32 machine code, 32 bytes

0003 2000 2102 1e4a bf58 07d1 0fc9 3905
3102 f150 0000 cb04 2a20 d0f4 d8f8 4770

Following the AAPCS, this takes in r0 the address of the input as a null-terminated string in UTF-32 (if this is not allowed, +2 bytes for LDMIALDRB with writeback or 2 instructions), and returns the number of Jimmies needed in r0.

The problem can be solved by a greedy algorithm, reading the string one character at a time while maintaining some values: \$L\$, the length so far of the current platform or 0 if none; \$Z\$, a flag that is 1 if the current platform is supported at its left end, and 0 otherwise; and \$T\$, the number of Jimmies used so far.

When reading a platform character (-), if \$Z\$ is 0, we need to add a Jimmy (incrementing \$T\$) the first time (when \$L\$ is 0); if \$Z\$ is 1 (left-supported), we only need to add a Jimmy if the platform is longer than 1, so increment \$T\$ on the second platform character (when \$L\$ is 1). These cases can be combined: increment \$T\$ if \$L = Z\$. Afterwards, \$L\$ is incremented.

When reading a non-platform character ( ), the way \$Z\$ is modified is more complicated. For a long platform (\$L \ge 2\$), if the platform is not left-supported, its Jimmy supports only that platform, whereas if it is left-supported, its second Jimmy can be placed at its right end to potentially support a later platform; this means that \$Z\$ remains unchanged. For a short platform (\$L\$ is 1), an existing left-support is enough for it, while if it was not left-supported, then it gets a new Jimmy that can also support a later platform; this means that \$Z\$ is inverted. Finally, if there is no platform between two consecutive non-platform characters (\$L\$ is 0), then any out-hanging Jimmy runs out; \$Z\$ is set to 0. Afterwards, \$L\$ is set to 0. Here is a summary of the way \$Z\$ is changed: $$ \begin{array}{c|ccccc} & 0 & 1 & 2 & 3 & \cdots \\ \hline 0 & 0 & 1 & 0 & 0 & \cdots \\ 1 & 0 & 0 & 1 & 1 & \cdots \end{array} $$

In my program, \$L\$ and \$Z\$ are combined into a single value \$K = 2L - Z - 2\$.
Then, when reading a platform character (-), \$K\$ is increased by 2, and \$T\$ is incremented if \$K\$ changes from -2 to 0 or from -1 to 1, or equivalently, if \$K\$ changes from negative to nonnegative. When reading a non-platform character ( ), \$K\$ changes as follows: $$ \begin{array}{c|cccc|ccccc} \textrm{Before} & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & \cdots \\ \hline \textrm{After} & -2 & -2 & -2 & -3 & -3 & -2 & -3 & -2 & \cdots \end{array} $$

Assembly:

.code 16
.section .text
.syntax unified
.global njimmies
.thumb_func
njimmies:
    movs r3, r0       @ Transfer string address to r3
    movs r0, #0       @ Total number of Jimmies = 0
    movs r1, #2       @ K = 2 (will be changed by the following code before reading the string)
space:
    subs r2, r1, #1   @ Calculate K-1
    it pl             @ If the result is nonnegative...
    lslpl r1, r2, #31 @  shift the low bit of the result into the high bit of r1
    lsrs r1, r1, #31  @ Shift the high bit of r1 into the low bit; all other bits become 0
    subs r1, #5       @ Make the value -4 or -5, and fall through
platform:
    adds r1, #2       @ Add 2 to K
    adcs.w r0, #0     @ Count up one Jimmy if K went from negative to nonnegative
    ldmia r3!, {r2}   @ Load the next character
    cmp r2, #32
    beq space         @ Jump on ' '
    bhi platform      @ Jump on '-'
    bx lr             @ Return on the null terminator
\$\endgroup\$
7
\$\begingroup\$

Jelly, 21 20 19 bytes

OḂŒrµ=1EƇṣØ0Ẉ:2SạSḢ

Try it online!

This may or may not be an incredibly stupid way to do it.

Based on the following observation: the best way is to use one Jimmy per platform, unless there are two platforms of length 1 such that all spaces between them are also length 1, in which case they can be connected by Jimmies, saving one Jimmy.

\$\endgroup\$
4
  • \$\begingroup\$ Does this solution take into account that there can be 2 spaces between platforms and thus you need a Jimmie to support both? \$\endgroup\$
    – Hacky
    Sep 13 at 7:43
  • \$\begingroup\$ @Hacky I'm pretty sure it does. Can you find a case where it doesn't work? \$\endgroup\$
    – xigoi
    Sep 14 at 8:09
  • \$\begingroup\$ I don't know JElly, but I couldn't find a support for 2 spaces in your dscription. \$\endgroup\$
    – Hacky
    Sep 15 at 14:06
  • \$\begingroup\$ @Hacky "such that all spaces between them are also length 1" \$\endgroup\$
    – xigoi
    Sep 15 at 21:52
5
\$\begingroup\$

C (clang), 73 bytes

c;o;f(*s){for(c=o=1;*s;o=*s++)c=o-*s?*s%5?s[1]%5>0|c:s[1]%2-~c:c;*s=c/2;}

Try it online!

-7 byte thanks to ceilingcat!!

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

APL (Dyalog Unicode), 29 bytes

{+/⌈+/¨1⌊2÷⍨0(≠⊆⊢)≢¨⍵⊆⍨' '≠⍵}

Try it online!

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

R, 109 93 92 bytes

Or R>=4.1, 78 bytes by replacing two function appearances with \s.

function(x,`+`=strsplit,`?`=sum)?sapply(el(x+"  ")+" ",function(a)pmin(nchar(a)/2,1)?.5)%/%1

Try it online!

Port of @Jonathan Allan's solution.

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

05AB1E, 12 bytes

ð¡€g0¡<Ā>;OîO

Port of @JonathanAllan's Jelly answer.

Try it online or verify all test cases.

Explanation:

ð¡             # Split the (implicit) input-string on spaces
               # (`#` doesn't work here if the input lacks any spaces)
  €g           # Get the length of each part
    0¡         # Split this list of integers on 0s
      <        # Decrease each length by 1
       Ā       # Check which values are NOT 0 (0 if 0; 1 if >= 1)
        >      # Increase each by 1 (1 if 0; 2 if >= 1)
         ;     # Halve each (0.5 if 0; 1 if >= 1)
          O    # Sum each inner list
           î   # Ceil each sum
            O  # And sum those together again
               # (after which the result is output implicitly)
\$\endgroup\$
3
\$\begingroup\$

JavaScript (V8), 86 78 bytes

Thanks Johan du Toit for -8

x=>(a=.5,x.split`  `.map(p=>p.split` `.map(i=>a+=i?i[1]?1:.5:0,a=~~a+.5)),~~a)

Try it online!

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

Python 3, 88 81 79 77 bytes

lambda x:-sum(-sum(min(len(j),2)for j in i.split())//2for i in x.split('  '))

Try it online!

-7 bytes thanks to EnderShadow8 and movatica.
-2 bytes thanks to movatica.
-2 bytes thanks to Wheat Wizard.

Based on Jonathan Allan's answer. Outputs an integer.

\$\endgroup\$
5
  • \$\begingroup\$ You don't need to pass in a space to the first call to split. \$\endgroup\$ Sep 12 at 8:32
  • \$\begingroup\$ Instead of list comprehension, use a generator expression for sum(), which is iterable as well. That means, you can just drop both [] to save 4 bytes. \$\endgroup\$
    – movatica
    Sep 12 at 8:54
  • \$\begingroup\$ 81 bytes \$\endgroup\$
    – wasif
    Sep 12 at 9:11
  • \$\begingroup\$ You can pull out the outer minus, removing one pair of parenthesis for another two bytes less. \$\endgroup\$
    – movatica
    Sep 13 at 11:39
  • 1
    \$\begingroup\$ Save 2 bytes by combining the divisions \$\endgroup\$
    – Grain Ghost
    Sep 13 at 22:19
3
\$\begingroup\$

Retina, 12 bytes

--+
--
- ?-?

Try it online!

Reduce all long platforms to length 2, which doesn't change the result. Now each Jimmy can support up to two -s close together. Count such pairs of -s and excess single -s.

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

///, 31 bytes

/---/--//- -/--//--/1//-/1// //

Input should be appended to the program, as permitted here. Output is in unary.

Try it online!

This uses the same idea as one of my other answers – reduce all long platforms to length 2, which doesn't change the result, and then each Jimmy can support up to two -s close together – but does it in a somewhat more complicated way.

                                Example string: "- --- -  ---- -"
/---/--/    Reduce long platforms to length 2   "- -- -  -- -"
/- -/--/    Close short gaps                    "----  ---"
/--/1/      Count pairs of -s                   "11  1-"
/-/1/       Count leftover single -s            "11  11"
/ //        Remove spaces                       "1111"
\$\endgroup\$
0
\$\begingroup\$

Charcoal, 21 19 bytes

IΣE⪪S  ⌈⊘ΣE⪪ι ⌊⟦²Lλ

Try it online! Link is to verbose version of code. Explanation: Now a port of @Yousername's answer.

    S               Input string
   ⪪                Split on pairs of spaces
  E                 Map over runs
           ⪪ι       Split run on spaces
          E         Map over each platform
                 Lλ Length of platform
              ⌊⟦²   Minimum of that and 2
         Σ          Take the sum
        ⊘           Halved
       ⌈            Ceiling
 Σ                  Take the sum
I                   Cast to string
                    Implicitly print
\$\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.