Instantly share code, notes, and snippets.

# king-11/Problem.md

Last active February 2, 2024 11:15
Show Gist options
• Save king-11/39b73277438088691dad796a43428582 to your computer and use it in GitHub Desktop.

# Boat Racing

You manage to sign up as a competitor in the boat races just in time. The organizer explains that it's not really a traditional race - instead, you will get a fixed amount of time during which your boat has to travel as far as it can, and you win if your boat goes the farthest.

As part of signing up, you get a sheet of paper (your puzzle input) that lists the time allowed for each race and also the best distance ever recorded in that race. To guarantee you win the grand prize, you need to make sure you go farther in each race than the current record holder.

The organizer brings you over to the area where the boat races are held. The boats are much smaller than you expected - they're actually toy boats, each with a big button on top. Holding down the button charges the boat, and releasing the button allows the boat to move. Boats move faster if their button was held longer, but time spent holding the button counts against the total race time. You can only hold the button at the start of the race, and boats don't move until the button is released.

For example:

``````Time:      7  15   30
Distance:  9  40  200
``````

This document describes three races:

• The first race lasts `7` milliseconds. The record distance in this race is `9` millimeters.
• The second race lasts `15` milliseconds. The record distance in this race is `40` millimeters.
• The third race lasts `30` milliseconds. The record distance in this race is `200` millimeters.

Your toy boat has a starting speed of zero millimeters per millisecond. For each whole millisecond you spend at the beginning of the race holding down the button, the boat's speed increases by one millimeter per millisecond.

So, because the first race lasts `7` milliseconds, you only have a few options:

• Don't hold the button at all (that is, hold it for `0` milliseconds) at the start of the race. The boat won't move; it will have traveled `0` millimeters by the end of the race.
• Hold the button for `1` millisecond at the start of the race. Then, the boat will travel at a speed of `1` millimeter per millisecond for `6` milliseconds, reaching a total distance traveled of `6` millimeters.
• Hold the button for `2` milliseconds, giving the boat a speed of `2` millimeters per millisecond. It will then get `5` milliseconds to move, reaching a total distance of `10` millimeters.
• Hold the button for `3` milliseconds. After its remaining `4` milliseconds of travel time, the boat will have gone `12` millimeters.
• Hold the button for `4` milliseconds. After its remaining `3` milliseconds of travel time, the boat will have gone `12` millimeters.
• Hold the button for `5` milliseconds, causing the boat to travel a total of `10` millimeters.
• Hold the button for `6` milliseconds, causing the boat to travel a total of `6` millimeters.
• Hold the button for `7` milliseconds. That's the entire duration of the race. You never let go of the button. The boat can't move until you let go of the button. Please make sure you let go of the button so the boat gets to move. `0` millimeters.

Since the current record for this race is `9` millimeters, there are actually `4` different ways you could win: you could hold the button for `2`, `3`, `4`, or `5` milliseconds at the start of the race.

In the second race, you could hold the button for at least `4` milliseconds and at most `11` milliseconds and beat the record, a total of `8` different ways to win.

In the third race, you could hold the button for at least `11` milliseconds and no more than `19` milliseconds and still beat the record, a total of `9` ways you could win.

To see how much margin of error you have, determine the number of ways you can beat the record in each race; in this example, if you multiply these values together, you get `288` (`4` * `8` * `9`).

Determine the number of ways you could beat the record in each race. What do you get if you multiply these numbers together?

## Part Two

As the race is about to start, you realize the piece of paper with race times and record distances you got earlier actually just has very bad kerning. There's really only one race - ignore the spaces between the numbers on each line.

So, the example from before:

``````Time:      7  15   30
Distance:  9  40  200
``````

``````Time:      71530
Distance:  940200
``````

Now, you have to figure out how many ways there are to win this single race. In this example, the race lasts for `71530` milliseconds and the record distance you need to beat is `940200` millimeters. You could hold the button anywhere from `14` to `71516` milliseconds and beat the record, a total of `71503` ways!

How many ways can you beat the record in this one much longer race?

# Rules

• You can use any programming language of your choice.
• You need to read the input from a text file not `stdin`.
• The final answer should be printed out to `stdout`.
• The final file on which will run the character count needs to be in unicode format (not standard windows).
• To provide normalization, if you are using a dynamically typed language you need to provide in types to your variables.
• You shouldn't use anything apart from standard library of the particular language.
• Your program should print solution to both parts in no more than `30`secs.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 Time: 40 81 77 72 Distance: 219 1012 1365 1089

### king-11 commented Feb 2, 2024 • edited

```import kotlin.io.path.*
import kotlin.math.*
fun main() {
val nr = "\\s+".toRegex()
val nw = { t: Float, d: Float ->
val (f, s) = Pair(floor((t - sqrt(t * t - 4 * d)) / 2 + 1).toInt(), ceil((t + sqrt(t * t - 4 * d)) / 2 - 1).toInt())
s - f + 1
}
val p1 = { ix: List<String> ->
val rt = ix[0].split(nr).drop(1).map { it.toFloat() }.toList()
val rd = ix[1].split(nr).drop(1).map { it.toFloat() }.toList()
rt.mapIndexed { i, t -> t to rd[i] }.map { (t, d) -> nw(t, d) }.fold(1L) { acc, i -> acc * i }
}
val p2 = {ix: List<String> ->
val t =  ix[0].split(nr).drop(1).joinToString("").toFloat()
val d = ix[1].split(nr).drop(1).joinToString("").toFloat()
nw(t, d)
}
p1(input).println()
p2(input).println()
}```

### vstark21 commented Feb 2, 2024 • edited

python:

```from math import ceil,prod
def v(t):t,d=map(int,t);f=(t*t-4*d)**.5;return-((t-f+2)//2)+ceil((t+f)/2-1)+1
e,f=map(lambda x:x.split(':')[1].split(),[*open('b','r')]);print(prod(map(v,zip(e,f))),v([''.join(e),''.join(f)]))```

Number of characters: 219

cpp:

```#include <iostream>
#include <bits/stdc++.h>
#include <math.h>
using namespace std;typedef long double ld;typedef long long ll;
#define range(i,j,n) for(int i=j;i<n;i++)
ll v(ld t,ld d){ld f=sqrt(t*t-4*d);return -floor((t-f)/2+1)+ceil(((t+f)/2-1))+1;}
int main(){freopen("D:/temp/GolfCoding/b","r",stdin);string a,e,f;cin>>a;ll n=4,g=1;vector<ll> t(n),d(n);range(i,0,n){cin>>t[i];e+=to_string(t[i]);}cin>>a;range(i,0,n){cin>>d[i];f+=to_string(d[i]);}range(i,0,n){g=g*v(t[i],d[i]);}cout<<g<<" "<<v(stold(e),stold(f))<<"\n";return 0;}```

Number of characters: 532

### purijatin commented Feb 2, 2024 • edited

```val k::y::Nil=scala.io.Source.fromFile("i").getLines().map(_.split(":")(1)).map(_.trim.split("\\s+",-1).map(_.toLong)).toList
def f(p:Array[(Long,Long)])=p.map(w=>(1L to w._1).count(x=>x*(w._1-x)>w._2)).product
println(f(k.zip(y))+" "+f(Array((k.mkString("").toLong,y.mkString("").toLong))))```

To run: `scala File.scala`

Number of characters in program: 289

Program output for first test-case:
Time: 7 15 30
Distance: 9 40 200

288
71503

Program output for second test-case:
Time: 40 81 77 72
Distance: 219 1012 1365 1089

861300
28101347

### ankitdsi2010 commented Feb 2, 2024 • edited

Iteration 1: 302 characters
```from math import sqrt,floor,prod
def sol(t,d):m=sqrt(t**2-4*d);return floor((t+m)/2)-floor((t-m)/2)-(m==int(m))
print(prod(map(lambda x:sol(x[0],x[1]),zip(t,d))),sol(int(''.join(map(str,t))),int(''.join(map(str,d)))))
```
Iteration 2: 287 characters
```from math import sqrt,floor,prod
def sol(t:str,d:str)->int:t,d=int(t),int(d);m=sqrt(t**2-4*d);return floor((t+m)/2)-floor((t-m)/2)-(m==int(m))
```with open('input.txt') as f:l=f.readlines();t=l[0].split()[1:];d=l[1].split()[1:];