1
\$\begingroup\$

Story

There is a woman, named Sarah, whom likes smooth horse rides. She's going to go for a ride down a path too thin to pass any other horses she may come across - and so that her ride can be as smooth as possible she does not want to have to change speed though she would prefer to get to her destination as fast as possible.

Situational Definition

There is a random number of horses traveling at a random speed which are at a random point between the start and end of the path when the Sarah departs. You must calculate the fastest speed at which she can travel without reaching another of the horses have having to slow her speed.

All horses on this path will slow to the speed of the horse in front of it if it reaches that horses position. It's a popular trail, and there is always at least 1 horse.

Example "starting" point graphic: enter image description here

Example "half way" graphic: enter image description here

Primary Success Criteria

Each post must have a code golf answer - in which you try to solve the problem in as few characters as possible.

I'm open to changes on these policies but I thought it would be interesting if I were allowed to have the following special rules: (If they are deemed unfair or flawed I'll certainly reconsider)

  • Line endings are assumed to be '\n' not '\r\n' and are only counted as 1 character. This may allow slightly more readable code in some languages.
  • To encourage answering in languages that would not usually be "winners" in code golf I'd like to institute a point modification system:
    • Code golf languages have their character count multiplied by 1.25. (I will consider any language in which at least 80% of it's operators or keywords are 1 or 2 characters to be a code golf language.)
    • Answers using compiled strictly typed languages (C, Java, etc) can have their character count multiplied by 0.85 (Because usually it requires more characters to code things in those languages.) Languages like Javascript that may be "compiled" by something like V8 do not count and are loosely typed.

(These may be modifiers may be altered or changed slightly if they are unfair or need improvement)

Implementation technical details You are not required to post surrounding code that is not specific to this problem and is required by your language for your code to execute. For example, in java your code would need a "class" and a main function to execute; however, you can simply provide code as if it were within the "main" function. Any import statements for standard libraries that are required for your code to run should be provided in a code block below your main code, and these will not count towards your character count. You shouldn't use any libraries someone who can compile or execute that language wouldn't have out of the box.

Code Scope Your code should work assuming that variables "d" and "h" (or a closest variant in your language if for some reason those are not acceptable) are present in your scope.

"d" is a number with decimal precision (ex. double/float) representing the distance to the destination from 0. "h" is an array or list of some structure that can support two values "p" and "s" which are also decimals.

Testing code You should provide a some lines for testing in a code block below your answer code block that assigns d to a random value between or equal to 200 and 1000, and "h" to a list of length between or equal to 10 and 40 in which each list item stores a value for position between 0 and the value of d, and speed is between or equal to 5 and 10. (Not Sarah's horse is the worlds fastest horse and can travel as fast as is optimal, even if that speed greatly exceeds 10)

Results Your answer should store the speed Sarah should travel in a variable capable of storing decimal values such that it could be used in lines below your code for any purpose including answer checking, logging to a console, or outputting in the programs UI. This variable should be named "o" if possible which is short for "optimal speed".

To recap your answer should:

  1. Have a code block which outputs the speed assuming "d" and "h" are present in the scope.
  2. Have a code block below which assigns "d" and "h" to appropriate values for distance and a list of horses.
  3. Output the correct value for "o" which is the speed to travel. (Again if these variable names are not acceptable in your language please just note why and what variable names you used in place of the ones provided)

The answer with the shortest character count wins.

Example situation:

"d" is 250, and "h" has one item with "p" of 50 and speed of "20". In this simple case Sarah can travel at 250/((250-50)/20)=25. So "o" should be 25 in this case.

You should be-able to handle cases in which there are numerous horses slowing after reaching the horse(s) in front of them.

Secondary Objective

If your answer is written in JavaScript and works with the data provided or you provide an additional conforming JavaScript answer in the same post, I will execute your code in something like this in a web page I will later create in the latest version of the chrome browser:

var horse = (pos, speed) => ({pos: pos, speed: speed})
var rhorse = (d) => horse(rand(d), rand(5)+1)

var rand = (i) => Math.random()*i
var irand = (i) => Math.round(Math.random()*i)

var answers = []

answers.push(function(d, h){
    //YOUR CODE
})

function checkAnswer(ans, d, h){
    // Code that which is proven to answer the question reliably
}
var speeds = []
for (var a = 0; a < answers.length; a++) {
    var totalTime = 0
    for (var i = 0; i < 1000; i++) {
        var d = rand(800)+200
        var numhorses = irand(30)+10
        var h = []

        for (var i = 0; i < numhorses; i++)
            horses.push(rhorse(d))

        var start = performance.now()

        answers[a]()

        totalTime += performance.now()-start

        if (!checkAnswer(ans)
    }
    var time = (totalTime/1000)
    speeds.push({time: time, answer: a})
    console.log("Answer " + a + " completed with an average speed of " + time)
}

//Todo: sort by time

console.log(speeds)

And then the times I got for each answer will be posted. This does not determine the winner or the question I will mark as the "answer". It is merely another metric that is being measured. (And if you have interest in trying to out-perform other code examples you can compete that way as well). As mentioned you may provide a second code blog to be used to for the performance comparison.

Example answer (That would fail)

" 62 Characters

someHorse = h[0]
o = (d-someHorse.p)/someHorse.s
o = d/o

Test code:

var horse = (p, s) => ({p: p, s: s})
var rhorse = (d) => horse(rand(d), rand(5)+1)

var rand = (i) => Math.random()*i
var irand = (i) => Math.round(Math.random()*i)
var d = rand(800)+200
var numhorses = irand(30)+10
var h = []

for (var i = 0; i < numhorses; i++)
    horses.push(rhorse(d))

"

You can just note you'll use my test code here if you're code is written in javascript.

Results:

  1. ppperry (By the way, where is he?)- 31 characters

Disclaimer

This is my first code golf question. I'm willing to fix flaws, please go easy with me.

This question was very strongly inspired by: https://code.google.com/codejam/contest/8294486/dashboard

\$\endgroup\$
1

4 Answers 4

6
+400
\$\begingroup\$

APL (Dyalog Classic), 10 9 bytes

⌊/s÷1-p÷d

Taking s, p and d as per the specs, respectively horse speeds, positions and the total distance to be travelled.

Explanation:

      p÷d  ⍝ Divide each horse position by the total distance
    1-     ⍝ and do 1 minus that.
  s÷       ⍝ Divide each speed s by each element in the list.
⌊/         ⍝ Finally go over the list accumulating the minimum.

You can try it online!

Previous 10 byte solution:

d÷⌈/s÷⍨d-p

Explanation:

       d-p ⍝ Find the distance each horse still has to travel
    s÷⍨    ⍝ and divide it by each horse's speed.
  ⌈/       ⍝ Now go over the list, accumulating the maximum.
d÷         ⍝ Finally divide the distance by that time.

You can try it online!

Thanks to @Grimmy for spotting a (now corrected) problem with my original answer and for saving me 1 byte.

\$\endgroup\$
6
  • \$\begingroup\$ +1 Nice first APL answer. Since your code is an expression, you can simply wrap it in a dummy program. The variables retain their values and will print when mentioned. Try it online! \$\endgroup\$
    – Adám
    Feb 12, 2020 at 22:49
  • 1
    \$\begingroup\$ @Adám wow this is really cool! I may like APL more than Jelly :p \$\endgroup\$
    – RGS
    Feb 12, 2020 at 23:03
  • 1
    \$\begingroup\$ You're always welcome to hang out in the APL Orchard. Great place to ask questions and get tips, advice, and all kinds of help. \$\endgroup\$
    – Adám
    Feb 12, 2020 at 23:07
  • \$\begingroup\$ @Grimmy Thank you for your attentive eye! You will be pleased to know I already corrected my error! \$\endgroup\$
    – RGS
    Feb 13, 2020 at 17:11
  • \$\begingroup\$ Nice fix! I don't know APL, but you might be able to save bytes by porting my simplified formula, o=min(x.s/(1-x.p/d)for x in h). \$\endgroup\$
    – Grimmy
    Feb 13, 2020 at 17:11
3
\$\begingroup\$

Python 3, 31 bytes

o=d/max((d-x.p)/x.s for x in h)

This challenge is actually much simpler than it seems. In order to avoid running in to other horses, you have to arrive at the end after whichever horse (not counting Sarah's) arrives at the end last. To go fastest, it is thus best to arrive at exactly the same time as that horse does.

Testing code:

import random
d=random.uniform(200, 1000)
h=[]
class Horse:__slots__=("p", "s")
for _ in range(random.randint(10, 40)):
    h.append(Horse())
    h[-1].p = random.uniform(0, d)
    h[-1].s = random.uniform(5, 10)
\$\endgroup\$
5
  • \$\begingroup\$ It is easier than it seems for sure. I decided if I ever want to do a more challenging problem I could require that the program can return the position horse "x" and time "t" given whatever distance and horses. \$\endgroup\$
    – csga5000
    Jul 29, 2017 at 21:31
  • 1
    \$\begingroup\$ I was litterally just about to say 'You do not initialize h in your test code. Adding "h = []" as line 3 fixed this for me'. Nice job catching it first. \$\endgroup\$
    – csga5000
    Jul 29, 2017 at 21:39
  • 1
    \$\begingroup\$ Your byte count is incorrect; I count 31 bytes. Additionally, you may not take input in the form of a variable; you must either declare a function, an anonymous lambda, or create a full program. \$\endgroup\$
    – hyper-neutrino
    Jul 29, 2017 at 22:06
  • 2
    \$\begingroup\$ Wait never mind, ignore what I said. I didn't read the part in the specs saying you were supposed to assume that they were in scope. Carry on, +1 :) \$\endgroup\$
    – hyper-neutrino
    Jul 29, 2017 at 22:06
  • \$\begingroup\$ This formula can be simplified to o=min(x.s/(1-x.p/d)for x in h). TIO link to check that the two are equivalent. \$\endgroup\$
    – Grimmy
    Feb 13, 2020 at 17:09
2
\$\begingroup\$

05AB1E, 5 bytes

/1α/ß

Try it online!

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

Pyth, 16 bytes * 1.25 = 20 bytes

=ZcdeS.ec-dhbebH

Most of this is dedicated to preserving the input format.

Used H instead of h because h isn't a variable in Pyth

While I could've taken that o isn't a variable as an excuse to use J or K and save a byte, in the end I decided to use Z (zerO) because it's what I would've had to do if o was available.

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Why are you multiplying the byte count by 1.25? \$\endgroup\$
    – RGS
    Feb 18, 2020 at 21:14
  • \$\begingroup\$ @RGS Some challenge specific rule :/ \$\endgroup\$
    – Citty
    Feb 19, 2020 at 16:31

Your Answer

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

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