title: Implement a Simple Stopwatch

text:
# Question
Title: Implement a Simple Stopwatch
# Challenge

Your task is to write a program which, once a second (including immediately when your program is started), prints the elapsed time from the time your program was started.

# Rules

* Time must be printed in `hh:mm:ss` format. (leading zeros for single-digit values)
* The time stamps must be separated by CR, LF, or CRLF. (no leading whitespace)
* A new time must appear every second. (stdout cannot be buffered for a second)
* The behavior of the program if it is run past 23:59:59 is undefined.
* You may use `sleep(1)` even if a specific second may be skipped whenever the overhead to print, calculate, loop, etc. accumulates to a second.

Example output:

```
00:00:00
00:00:01
00:00:02
00:00:04
00:00:05
⋮

```

Note that `00:00:03` is missing here due to processing overhead. The actual skipped values (if any) are of course dependent on implementation and/or system.

Reference implementation in C: (POSIX-compatible systems only)

```
#include <unistd.h> // sleep()
#include <tgmath.h>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#ifndef __STDC_IEC_559__
#error "unsupported double"
#endif
static_assert(sizeof(double) == 8, "double must have double precision");
#define MAX_PRECISE_DOUBLE ((double)(1ULL << 52))

int main(void) {
    time_t start = time(NULL);
    if (start == (time_t)-1) return EXIT_FAILURE;
    while (1) {
        time_t now = time(NULL);
        if (now == (time_t)-1) return EXIT_FAILURE;

        double diff = difftime(now, start);
        if (isnan(diff) || diff < 0) return EXIT_FAILURE;
        if (diff > MAX_PRECISE_DOUBLE) return EXIT_FAILURE;

        unsigned long long seconds = diff;
        unsigned long long h = seconds / 3600;
        seconds %= 3600;
        unsigned long long m = seconds / 60;
        seconds %= 60;
        unsigned long long s = seconds;

        (void)printf("\r%02llu:%02llu:%02llu", h, m, s);
        (void)fflush(stdout);

        (void)sleep(1);
    }
}

```

# Winning criteria

This is , shortest code in bytes win!

# Answer
# MATL, ~~17~~ 16 bytes

```
`Z`12L/13XOD1Y.T

```

Try it at **MATL Online!**

### How it works

```
`         % Do...while loop
  Z`      %   Push seconds elapsed since start of program
  12L     %   Push 86400 (predefined literal)
  /       %   Divide. This transforms seconds into days
  13XO    %   Convert to date string with format 13, which is 'HH:MM:SS'
  D       %   Display
  1Y.     %   Pause for 1 second
  T       %   True. Used as loop condition for infinite loop
          % End loop (implicit)

```
> 9 votes

# Answer
# Operation Flashpoint scripting language,  ~~174~~  171 bytes

```
s=""
#l
t=_time
t=t-t%1
a=t%60
c=(t-a)/60
b=c%60
c=(c-b)/60
d=""
e=d
f=d
?a<10:d=0
?b<10:e=0
?c<10:f=0
s=s+format["%1%2:%3%4:%5%6\n",f,c,e,b,d,a]
hint s
@t+1<_time
goto"l"

```

**In action:**

**158 bytes, if the previous time is overwritten by the next time:**

```
#l
t=_time
t=t-t%1
a=t%60
c=(t-a)/60
b=c%60
c=(c-b)/60
d=""
e=d
f=d
?a<10:d=0
?b<10:e=0
?c<10:f=0
hint format["%1%2:%3%4:%5%6",f,c,e,b,d,a]
@t+1<_time
goto"l"

```

Technically, no carriage return is used, so I'm not sure if this version confines to the rules.
> 29 votes

# Answer
# Bash \+ coreutils, ~~28~~ 26 bytes

```
date -s0|yes date +c%T|sh

```

The unprintable character between `+` and `%` is an *ESC* byte.

**This sets the system time to 00:00:00** and thus requires root privileges. It also assumes that the timezone is UTC and that no other processes will interfere with the system clock.

Each new timing resets the terminal, thus overwriting the previous one.

---

# Bash \+ coreutils, ~~38~~ 29 bytes

```
date -s0|yes date +%T|sh|uniq

```

The same restrictions as before apply. Each new timing is shown on a new line.
> 13 votes

# Answer
# APL (Dyalog Unicode), 51 bytes

Full program body.

```
s←⎕AI
1↓∊':'@1∘⍕¨100+3↑0 60 60 1E3⊤3⊃⎕AI-s
⎕DL 1
→2

```

Try it online! (Press Ctrl+Enter to start, and again to stop.)

`⎕AI`**A**ccount **I**nformation (user ID, compute time, connect time, keying time)

`s←` assign to `s` (for **s**tart time)
`⎕AI-s` subtract `s` from `⎕AI`

`3⊃` pick the third element (connect time in milliseconds)
`0 60 60 1E3⊤` convert to this mixed-radix
`3↑` take the first 3 (drops the milliseconds)
`100+` one hundred added to each (to pad zeros)
`':'@1∘⍕¨` amend with a colon at the first character of the string representation of each
**ϵ**nlist (flatten)
`1↓` drop the first colon (and implicitly print to stdout)

`⎕DL 1`**D**e**l**ay one second

`→2` go to line number two
> 5 votes

# Answer
# , ~~59~~ 44 bytes

`F` in R defaults to `FALSE`, but it's a regular variable and can be redefined. When used in arithmetic, `FALSE` is coerced to `0`. Asking for `F+1` therefore returns `1`. We assign `F` to be `F+1`, format it nicely, print, and wait for one second. Continues indefinitely.

```
repeat{print(hms::hms(F<-F+1))
Sys.sleep(1)}

```

Doesn't work on TIO (due to lack of the `hms` package), but here's a sample output from my machine:

```
00:00:00
00:00:01
00:00:02
00:00:03
00:00:04
00:00:05
00:00:06
00:00:07
00:00:08
00:00:09
00:00:10
00:00:11
00:00:12
00:00:13

```
> 5 votes

# Answer
# bash \+ sleep + date, ~~also 50~~ ~~49~~ ~~47~~ ~~46~~ ~~45~~ 41 bytes

```
while date -ud@$[s++] +%T;do sleep 1;done

```

To take a lap time, quickly hit ^C, run this and then rerun the above:

```
laps=("${laps[@]}" $s) ; echo ${laps[-1]}

```

To reset:

```
s=0; unset laps

```

The $\[s++\] syntax appears to still work, but is no longer (AFAICS) documented in the `bash` man page. And it's still a byte shorter than using the for((...)) loop, once I removed the quotes around it.
> 5 votes

# Answer
# Swift, 144 bytes

```
import Foundation
let s=Date()
while 1>0{let d=Int(-s.timeIntervalSinceNow)
print(String(format:"%02d:%02d:%02d",d/3600,d/60%60,d%60))
sleep(1)}

```

## Explanation

```
import Foundation                       // Import `Date` and `sleep()`
let s = Date()                          // Get the time at the start of the program
while 1 > 0 {                           // While 1 > 0 (forever):
  let d = Int(-s.timeIntervalSinceNow)  //   Calculate time difference
  print(String(format:"%02d:%02d:%02d", //   Print the time
      d/3600,d/60%60,d%60))
  sleep(1)                              //   Sleep one second
}

```
> 4 votes

# Answer
# JavaScript (ES6), 99 bytes

```
f=_=>console.log(new Date(new Date-d).toUTCString().slice(17,25))
f(d=Date.now(setInterval(f,1e3)))
```
> 4 votes

# Answer
# Matlab (R2016b), 50 bytes

```
t=now;while 1,disp(datestr(now-t,13)),pause(1),end

```

Explanation:

```
t=now; % Stores the current time
while 1 % Loops forever
    disp(datestr(now-t,13)) % Computes the difference since the program started
    % And prints with format 13 ('HH:MM:SS') - this may change between versions
    pause(1) % Waits one second
end

```

Alternate version (50 bytes too :P):

```
now;while 1,disp(datestr(now-ans,13)),pause(1),end

```
> 4 votes

# Answer
# Julia 0.6, ~~75~~ 68 bytes

```
for h=0:23,m=0:59,s=0:59;@printf "%02i:%02i:%02i
" h m s;sleep(1)end

```

Try it online!

With sleep(1) allowed, simple nested for-loops are shorter than using Julias built-in time handling methods.

**Old solution without sleep(1) using DateTime**

```
t=now()-DateTime(0);Timer(x->println(Dates.format(now()-t,"HH:MM:SS")),0,1)

```

`t` is the amount of time passed from 'day 0' to when the program is started. `now()-t` is a *moment in time*, which is then formatted using `Dates.format()`.

`t0=now(); ...; now()-t0` would yield a *time difference*, that cannot be used with `Dates.format()`.

The timing itself is trivial with the build-in `Timer`.
> 3 votes

# Answer
## PHP 4+, ~~70~~ 64 bytes

```
$x=time();while(1){sleep(1);echo date('H:i:s',time()-$x)."\n";}

```

## PHP 5.3+, ~~69~~ 63 bytes

```
$x=time();a:sleep(1);echo date('H:i:s',time()-$x)."\n";goto a;

```
> 3 votes

# Answer
# JavaScript (ES6), 88 bytes

```
f=_=>console.log(new Date(i++*1e3).toUTCString().slice(17,25))
f(i=0,setInterval(f,1e3))
```

Essentially the same approach as @darrylyeo's answer, but works for all timezones and uses a slightly different way to get to 0.

\[Edit\] Darryl's answer has been fixed. This is still shorter, though.
> 3 votes

# Answer
# Python 2, 85 bytes

```
import time
t=0
while 1:print(":%02d"*3)[1:]%(t/3600,t/60%60,t%60);time.sleep(1);t+=1

```

# Credits
> 3 votes

# Answer
# \>\<\>, 82 + 7 = 89 bytes

```
0\!
:/+1oan~?=3ln?$0(a:o":"n~?=4ln?$0(a:ro":"n~?=5ln?$0(a:,*a6-}:%*a6:,*a6-}:%*a6:

```

Try it online!

+7 bytes for using the flag `-t.0125` to make the each instruction take 1/80th of a second. Each loop has 80 instructions, making each loop one second long. Because of computation time, this is actually longer in practice.

I actually had to buffer this all the way up to 100 until I saw @Not A Tree's answer which had 7 byte better way than mine to generate the hours and minutes, trimming it below 80. They also inspired the use of `\/` which are executed twice per loop.

### How It Works

```
0\...
./...
Initialises the stack with a 0 to represent the time

0\!
:/....................................................,*a6-}:%*a6:,*a6-}:%*a6:
Puts the hours, minutes and seconds in the stack

0\!
:/....n~?=3ln?$0(a:o":"n~?=4ln?$0(a:ro":"n~?=5ln?$0(a:...
Print out the hours, minutes, seconds separated by colons.
If the number is below 0, print a leading 0.
If the number is not, then there is an extra 0 on the stack, which is popped.

0\!
./+1oa...
Print a newline and increment the counter
And restart the loop

```

### Bonus:

A one line version of the same size, 80 + 9 bytes:

```
0::6a*%:}-6a*,:6a*%:}-6a*,:a(0$?nl5=?~n":"or:a(0$?nl4=?~n":"o:a(0$?nl3=?~nao1+>!

```

This uses the `-a` flag to add ticks for skipped instructions.
> 3 votes

# Answer
# Python 3, 112 bytes

Assuming using 1-second delays is ok, even if it (rarely) might skip a second.

```
from time import*;a=0
while 1:d=divmod;m,s=d(a,60);print(":".join(f"{k:02d}"for k in(*d(m,60),s)));a+=1;sleep(1)

```
> 2 votes

# Answer
# VBA, 90

```
t=0:while(1):?format(t,"hh:mm:ss"):t=t+timeserial(0,0,1):q=timer:while q-timer<1:wend:wend

```

run in immediate window:expected failure point somewhere around 23 million years (floating point resolution fails ~8.5e9 days)
> 2 votes

# Answer
# Clean, ~~173~~ ~~172~~ 168 bytes

```
import StdEnv,System.Time
$n i#i=(i/60^n)rem 60
=(i/10,i rem 10)
f i w#(Clock j,w)=clock w
#j=j/1000
|j>i=[j:f j w]=f i w
Start w=[($2i,':',$1i,':',$0i,'
')\\i<-f -1 w]

```

This one only works under the Windows Clean bundles.

Add 3 bytes if you want it to work under Linux, as Clean's `CLK_PER_TICK :== 1000000` on \*nix. If you want it to be cross-platform, add 8 bytes instead, as you need to use `CLK_PER_TICK` instead of the value it's set to. (*TIO link is larger due to above*)

Try it online!
> 2 votes

# Answer
# PHP, ~~59~~ 48 bytes

```
while(1){sleep(1);echo date('H:i:s',$i++)."\n";}

```

Inspired by Darren H's answer.

*Old version* :

```
<?php while(1){sleep(1);echo date('H:i:s',$i++-3600)."\n";}

```
> 2 votes

# Answer
# Bash \+ coreutils + GNU date, 50 bytes

```
o=`date +"%s"`;yes date +%X -ud\"-$o sec\"|sh|uniq

```

Inspired by @Dennis, this solution doesn't require the time to be changed. It store stores the initial offset from now to the UNIX epoch (1 Jan 1970 00:00:00 UTC), in 'o', and then displays \[-ud options\] (the current time - offset), in UTC date, but only \[+%X option\] HH:MM:SS. This should work in countries where the current time-zone isn't UTC.
> 2 votes

# Answer
# AWK, ~~110~~ ~~87~~ 86 bytes

```
BEGIN{for(;;i++){printf("%02d:%02d:%02d\n",i/3600%60,i/60%60,i%60);system("sleep 1")}}

```

Does not work in TIO.
> 2 votes

# Answer
# Jelly, 23 bytes

```
:⁽½c,60;%60d⁵j”:ṄœS1ṛ‘ß

```

Try it online!
> 2 votes

# Answer
# APL (Dyalog), 37 bytes

```
{∇⍵+×⎕DL 1⊣⎕←1↓∊':'@1∘⍕¨100+⍵⊤⍨3⌿60}0

```

Try it online!

Full program.

Pretty similar to Adám's answer, however independently written and uses a non-`⎕AI`-based approach.
> 2 votes

# Answer
# Python 2, 69 + 3 (`TZ=`) = 72 bytes

```
from time import*;s=time()
while 1:print ctime(time()-s)[11:19]+'\r',

```

This runs in a continuous loop, without sleeping, updating the time on the same line rather than printing a new line each second. (Still allowed by the rules, I hope.)

This slightly longer version (72+3=75 bytes) prints on a new line every second instead:

```
from time import*;s=time()
while 1:print ctime(time()-s)[11:19];sleep(1)

```

Both of these require you to be in the UTC timezone. On Linux you can achieve this by setting the `TZ` environment variable. E.g. `TZ= python`.
> 2 votes

# Answer
# \>\<\>, ~~106 bytes~~ 82 + 9 = 91 bytes

*Thanks to Jo King for suggesting the `-a` flag! Check out their answer too.*

```
0v+1oan<n0/
:/<</?(a:,*a6-}:%*a6:,*a6-}:%*a6:\\
n<n0/<</?(a:ro":"
":"n<n0/<</?(a:o

```

Try it online! (but you'll have to wait for the 60 second timeout).

I got to use a feature of \>\<\> that I've never needed before: this code requires the flag `-t.0125`, which sets the execution speed to 0.0125 seconds per tick, or 80 ticks per second. There's also the `-a` flag, which makes whitespace count as a tick (in some cases — the interpreter is a bit weird about this).

Basically, the code keeps a counter that's incremented each time the fish goes through the loop, and the rest of the loop converts the counter to `hh:mm:ss` format and prints it. The loop takes exactly 80 ticks.

This should work in theory, but in practice, each tick is slightly longer than 0.0125 seconds, because of computation time. Changing the `\\` on the second line to `<<` gives more accurate timings on TIO.

You can also watch the code in action at the fish playground, except that this interpreter treats whitespace slightly differently from the official interpreter. Alternatively, you can remove the flags on TIO to make the code run at top speed, to verify the behaviour for times after one minute.
> 2 votes

# Answer
# Java 8, full program, 150 bytes

```
interface M{static void main(String[]a)throws Exception{for(int i=0;;Thread.sleep(1000))System.out.printf("%02d:%02d:%02d%n",i/3600,i/60%60,i++%60);}}

```

Try it here (times out after 60 seconds, so I've set the sleep to 1 to see more output).

**Explanation:**

```
interface M{                    // Program:
  static void main(String[]a)   //  Mandatory main-method
     throws Exception{          //    Mandatory throws for Thread.sleep
    for(int i=0;                //   Start at 0
        ;                       //   Loop indefinitely
         Thread.sleep(1000))    //     After every iteration: Sleep for 1 sec
      System.out.printf("%02d:%02d:%02d%n",
                                //    Print in the format "HH:mm:ss\n":
        i/3600,i/60%60,i++%60); //     The hours, minutes and seconds
                                //     (and increase `i` by 1 afterwards with `i++`)
                                //   End of loop (implicit / single-line body)
  }                             //  End of mandatory main-method
}                               // End of program

```

---

# Java 8, function, 94 bytes

```
v->{for(int i=0;;Thread.sleep(1000))System.out.printf("%02d:%02d:%02d%n",i/3600,i/60%60,i++%60);}

```

Try it here (times out after 60 seconds, so I've set the sleep to 1 to see more output).

**Explanation:**

```
v->{   // Method with empty unused parameter and no return-type
  ...  //  Same as the program above
}      // End of method

```

Here is a small gif to see it works as intended when 1000 ms are used:
> 2 votes

# Answer
# Shell, 177 bytes

Notice that this is not entirely POSIX conformant because it uses `date +%s`, which is a common `date` expansion.

```
a=`date +%s`;while true;do b=`date +%s`;s=`expr $b - $a`;h=`expr $s / 3600`;s=`expr $s % 3600`;m=`expr $s / 60`;s=`expr $s % 60`;printf '\r%02d:%02d:%02d' $h $m $s;sleep 1;done

```
> 1 votes

# Answer
# Ruby, ~~192~~ 117 bytes (Credit to Dada)

```
t=Time.now
loop do
m,s=(Time.now-t).to_i.divmod(60)
h,m=m.divmod(60)
printf"%02d:%02d:%02d
",h,m,s
sleep 1
end

```

## How does it work?

Going to use the expanded version (Conversion to a time is given as a separate function and uses a different output format):

```
def format_secs(s) # Converts the value in seconds to the required format
    mins, secs = s.divmod(60) # divmod returns the quotient and the remainder of a number
    hours, mins = mins.divmod(60)
    [hours,mins,secs].map { |e| e.to_s.rjust(2,'0') }.join ':'

    =begin
    [hours,mins,secs] -Creates a new array using the values allready provided for hours, minutes and seconds
    .map { - Creates a new array based on a operation on each of an array's values
    .to_s.rjust(2,'0')} - Turns the number into a string, and then adds "0" if needed to make the timer's result at least two digits
    .join ':' - Combines the result of the operation into a single string with a ":" in between the two numbers
    =end
end

t = Time.now # Saves the time at the program's (Rough) start

loop do
    puts format_secs((Time.now - t).to_i) # Returns the result of  the "format_secs" operation on the difference between the two times (in seconds) converted to a pure integer
    sleep 1 # Waits for one second
end

```
> 1 votes

# Answer
# Powershell, 52 bytes

Newest (52 Bytes):

```
For($a=0){date -H:0 -Min:0 -S:$a -U:%T;Sleep 1;$a++}

```

Try it online!

It no longer requires admin, the solution is actually much simpler than before.

~~Using .Net (61 Bytes):~~

```
[DateTime]::Now.Date|set-date;For(1){get-date -U %T;Sleep(1)}

```

The .Net version exploits that Now.Date strips out the time, so it outputs 12:00 AM as the time. See: https://stackoverflow.com/a/9630340/8303961

~~Using only built-in commandlets (66 Bytes):~~

```
get-date -H:0 -Min:0 -S:0|set-date;For(1){get-date -U %T;Sleep(1)}

```

~~Both versions have to be run in a elevated powershell window due to changing the system time with set-date cmdlet.~~
> 1 votes

# Answer
# APL NARS, ~~109 63~~ 57 chars

```
q;t
t←0
{∊⍵,¨':: '}{1<⍴x←⍕⍵:x⋄'0',x}¨(3⍴60)⊤⌊t+←⎕DL 1⋄→2

```

3+3+48+3=57 (seen the others Apl solutions too)

```
{1<⍴x←⍕⍵:x⋄'0',x}

```

convert the INT ⍵ in the string of digits in a way if the lenght of that string is 1 than add one '0' in front of it

```
{∊⍵,¨':: '}

```

combine array in ⍵ with the array ':: '

```
00:00:01
00:00:02
00:00:03
00:00:04
00:00:05
00:00:06
00:00:07
00:00:08
00:00:09

```
> 1 votes

# Answer
# x86-64 machine code (Linux system call): 78 bytes

RDTSC spin-loop timing, Linux `sys_write` system call.

x86-64 doesn't provide a convenient way to query the RDTSC "reference clock" frequency at run time. You can read an MSR (and do a calculation based on that), but that requires kernel mode, or root + opening `/dev/cpu/%d/msr`, so I decided to make the frequency a build-time constant. (Adjust `FREQ_RDTSC` as necessary: any 32-bit constant won't change the size of the machine code)

Note that x86 CPUs for several years have had fixed RDTSC frequency so it is usable as a timesource, *not* a core clock cycle performance counter unless you take steps to disable frequency changes. (There are actual perf counters for counting real CPU cycles.) Usually it ticks near the nominal sticker frequency, e.g. 4008 MHz for my 4.0 GHz i7-6700k regardless of turbo or powersaving. (SO answer covering many aspects of RDTSC.)

Anyway, this busy-wait timing doesn't depend on load average / interrupts (like a calibrated delay-loop would), and also isn't sensitive to CPU power saving. (Related: Stack Overflow answer with a spin-wait on RDTSC, with delay cycles calculated from nanoseconds, although it still needs the ref frequency set externally.)

This code will work for any x86 with a reference frequency below 2^32 Hz, i.e. up to ~4.29 GHz. Beyond that, the low 32 of the timestamp would wrap all the way in 1 second, so I'd have to look at the `edx` high 32 bits of the result, too.

**Summary**:

push `00:00:00\n` on the stack. Then in a loop:

* `sys_write` system call
* ADC-loop over the digits (starting with the last) to increment the time by 1. Wrapping / carry-out handled with a `cmp` / `cmov`, with the CF result providing the carry-in for the next digit.
* `rdtsc` and save the start time.
* spin on `rdtsc` until the delta is \>= ticks per second of the RDTSC frequency.

NASM listing:

```
 1  Address                            ; mov  %1, %2       ; use this macro to copy 64-bit registers in 2 bytes (no REX prefix)
 2           Machine code           %macro MOVE 2
 3           bytes                      push  %2
 4                                      pop   %1
 5                                  %endmacro
 6
 7                                      ; frequency as a build-time constant because there's no easy way detect it without root + system calls, or kernel mode.
 8                                      FREQ_RDTSC equ 4000000000
 9                                  global _start
10                                  _start:
11 00000000 6A0A                        push     0xa                       ; newline
12 00000002 48BB30303A30303A3030        mov      rbx, "00:00:00"
13 0000000C 53                          push     rbx
14                                      ; rsp points to  `00:00:00\n`
20
21                                      ; rbp = 0                (Linux process startup.  push imm8 / pop is as short as LEA for small constants)
22                                      ; low byte of rbx = '0'
23                                  .print:
24                                      ; edx potentially holds garbage (from rdtsc)
25
26 0000000D 8D4501                      lea      eax, [rbp+1] ; __NR_write = 1
27 00000010 89C7                        mov      edi, eax     ; fd = 1 = stdout
28                                      MOVE     rsi, rsp
28 00000012 54                  <1>  push %2
28 00000013 5E                  <1>  pop %1
29 00000014 8D5008                      lea      edx, [rax-1 + 9]     ; len = 9 bytes.
30 00000017 0F05                        syscall               ; sys_write(1, buf, 9)
31
32                                      ;; increment counter string:  least-significant digits are at high addresses (in printing order)
33 00000019 FD                          std                        ;  so loop backwards from the end, wrapping each digit manually
34 0000001A 488D7E07                    lea      rdi, [rsi+7]
35                                      MOVE     rsi, rdi
35 0000001E 57                  <1>  push %2
35 0000001F 5E                  <1>  pop %1
36
37                                      ;; edx=9 from the system call
38 00000020 83C2FA                      add   edx, -9 + 3      ; edx=3 and set CF (so the low digit of seconds will be incremented by the carry-in)
39                                      ;stc
40                                  .string_increment_60:          ; do {
41 00000023 66B93902                    mov    cx, 0x0200 + '9'    ; saves 1 byte vs. ecx.
42                                      ; cl = '9' = wrap limit for manual carry of low digit.  ch = 2 = digit counter
43                                    .digitpair:
44 00000027 AC                          lodsb
45 00000028 1400                        adc      al, 0           ; carry-in = cmp from previous iteration; other instructions preserve CF
46 0000002A 38C1                        cmp      cl, al          ; manual carry-out + wrapping at '9' or '5'
47 0000002C 0F42C3                      cmovc    eax, ebx        ; bl = '0'.  1B shorter than JNC over a MOV al, '0'
48 0000002F AA                          stosb
49
50 00000030 8D49FC                      lea     ecx, [rcx-4]    ; '9' -> '5' for the tens digit, so we wrap at 59
51 00000033 FECD                        dec     ch
52 00000035 75F0                        jnz    .digitpair
53                                      ; hours wrap from 59 to 00, so the max count is 59:59:59
54
55 00000037 AC                          lodsb                        ; skip the ":" separator
56 00000038 AA                          stosb                        ; and increment rdi by storing the byte back again.  scasb would clobber CF
57
58 00000039 FFCA                        dec     edx
59 0000003B 75E6                        jnz   .string_increment_60
60
61                                      ; busy-wait for 1 second.  Note that time spent printing isn't counted, so error accumulates with a bias in one direction
62 0000003D 0F31                        rdtsc                         ; looking only at the 32-bit low halves works as long as RDTSC freq < 2^32 = ~4.29GHz
63 0000003F 89C1                        mov      ecx, eax             ; ecx = start
64                                  .spinwait:
65                                  ;    pause
66 00000041 0F31                        rdtsc                      ; edx:eax = reference cycles since boot
67 00000043 29C8                        sub      eax, ecx          ; delta = now - start.  This may wrap, but now we have the delta ready for a normal compare
68 00000045 3D00286BEE                  cmp      eax, FREQ_RDTSC   ; } while(delta < counts_per_second)
69                                   ;   cmp      eax, 40  ; fast count to test printing
70 0000004A 72F5                        jb     .spinwait
71
72 0000004C EBBF                        jmp .print
  next address = 0x4E = size = 78 bytes.

```

Uncomment the `pause` instruction to save significant power: this heats one core up by ~15 degrees C without `pause`, but only by ~9 with `pause`. (On Skylake, where `pause` sleeps for ~100 cycles instead of ~5. I think it would save more if `rdtsc` wasn't also slow-ish so the CPU isn't doing much a lot of the time).

---

A 32-bit version would be a few bytes shorter, e.g. using a 32-bit version of this to push the initial 00:00:00\n string.

```
16                          ;    mov      ebx, "00:0"
17                          ;    push     rbx
18                          ;    bswap    ebx
19                          ;    mov      dword [rsp+4], ebx    ; in 32-bit mode, mov-imm / push / bswap / push would be 9 bytes vs. 11

```

And also using 1-byte `dec edx`. The `int 0x80` system call ABI wouldn't use esi / edi, so the register setup for the syscall vs. lodsb / stosb might be simpler.
> 1 votes

# Answer
# q/kdb+, 40 bytes

**Solution:**

```
.z.ts:{-1($)18h$a+:1};a:-1;(.)"\\t 1000"

```

**Example:**

```
q).z.ts:{-1($)18h$a+:1};a:-1;(.)"\\t 1000"
q)00:00:00
00:00:01
00:00:02
00:00:03
00:00:04
00:00:05

```

**Explanation:**

There are three commands being executed here:

1. `.z.ts:{-1($)18h$a+:1}; / override timer function`
2. `a:-1; / initialise variable a to -1`
3. `(.)"\\t 1000" / start the timer with 1000ms precision`

Breakdown of the timer function:

```
.z.ts:{-1 string 18h$a+:1} / ungolfed timer function
      {                  } / lambda function
                     a+:1  / add 1 to variable a
                 18h$      / cast to seconds
          string           / cast to string
       -1                  / write to stdout
.z.ts:                     / assign this function to .z.ts

```

**Bonus:**

Alternative 1 for **41 bytes**:

```
a:.z.t;.z.ts:{-1($)18h$x-a};(.)"\\t 1000"

```

Alternative 2 for **26 + 7 bytes = 33 bytes**

```
.z.ts:{-1($)18h$a+:1};a:-1

```

and adding `-t 1000` as arguments to the q binary.
> 1 votes

# Answer
# Ocaml, ~~125~~ 117 bytes

```
let rec f i=Printf.printf"%02d:%02d:%02d\n"(i/3600)(i/60 mod 60)(i mod 60);flush stdout;Unix.sleep 1;f(i+1)let()=f 0

```

This is the naive way to do it, minus useless spaces. With a regular coding style, it is :

```
let rec f i =
  Printf.printf "%02d:%02d:%02d\n" (i/3600) (i/60 mod 60) (i mod 60);
  flush stdout;
  Unix.sleep 1;
  f (i+1)
let () = f 0

```

\[EDIT\] I forgot to remove spaces before submission... (-8 bytes)
> 0 votes

# Answer
# JavaScript (ES6), ~~68~~ 67 bytes

```
f=m=>setTimeout(f,c=1e3,m+c|c,alert((8+new Date(m|0)).split` `[4]))

```

Assumes the `alert` is dismissed immediately (for example, by holding down the `<enter>` key); if that's not permitted then add 6 bytes for `console.log`.

---

## Try it

`alert` overridden with `console.log` for your sanity!

```
alert=console.log
f=m=>setTimeout(f,c=1e3,m+c|c,alert((8+new Date(m|0)).split` `[4]))
f()
```
> 0 votes

# Answer
# Windows Batch, 218 bytes

Only golfed a bit, can be improved.

```
@echo off
set/ah=m=s=0
:L
set r=00%h%
set r=%r:~-2%
set t=00%m%
set t=%t:~-2%
set y=00%s%
set y=%y:~-2%
echo %r%:%t%:%y%
set/as+=1
if %s%==60 set s=0&set/am+=1
if %m%==60 set m=0&set/ah+=1
timeout 1 /nobreak>nul
goto L

```
> 0 votes

# Answer
## mIRC 7.49 53 Bytes

```
set %i 0 | timer 0 1 say $!duration(%i,3) $(|) inc %i

```
> 0 votes

# Answer
## Batch ~~183~~ 187 Bytes

```
@Set/AH=m=0,s=-1
:L
@(Set/As+=1,"1/(60-s)"||Set/As=0,m+=1,"1/(60-m)"||Set/Am=0,h+=1) 2> nul
@Set .s=0%s%&Set .m=0%m%&Set .h=0%h%
@Echo(%.h:~-2%:%.m:~-2%:%.s:~-2%&>nul Timeout 1&Goto:L

```
> 0 votes

# Answer
# Perl 5, 87 bytes

```
$s=time;{$n=time-$s;printf"%02d:%02d:%02d\n",int$n/3600,int$n/60%60,$n%60;sleep 1;redo}

```

Try it online!

*Note: The header section forces TIO to display the output; it is not required to run this on a local system.*

Ungolfed:

```
$start = time;
{
    $now = time - $start;
    printf(
        "%02d:%02d:%02d\n",
        int($now / 3600),
        int($now / 60 % 60),
        $now % 60
    );
    sleep 1;
    redo;
}

```
> 0 votes

---
Tags: code-golf, date
---


title: Sum powers to n

text:
# Question
Title: Sum powers to n
Each natural number (including 0) can be written as a sum of distinct powers of integers (with a minimum exponent of 2). Your task is to output the smallest power required to represent \\$n\\$.

For example:

```
2 = 1^2 + 1^3 // Output 3
9 = 1^2 + 2^3 = 3^2 // Output 2
15 = 2^2 + 2^3 + 1^4 + 1^5 + 1^6 // Output 6
20 = 2^2 + 0^3 + 2^4 // Output 4

```

Ungolfed slow reference implementation (js):

```
function f(x){
    for (let maxPower = 2; true; maxPower++){
        let bases = Array(maxPower - 1).fill(0);
        let sum = 0;
        while (sum != x && bases[0] ** 2 <= x){
            sum = bases.reduce((a, c, i) => a + c ** (i + 2), 0);
            let nextIncr = bases.length - 1;
            do {
                if (nextIncr < bases.length - 1) bases[nextIncr + 1] = 0;
                bases[nextIncr]++;
            } while (nextIncr && bases[nextIncr] ** (nextIncr--) > x)
        }
        if (sum == x) return maxPower;
    }
}

```

This is a challenge. The sequence is naturally 0-indexed, so you may **not** 1-index it. You may...

* Take a positive integer \\$n\\$ and output the first \\$n\\$ values.
* Take a positive integer \\$n\\$ and output the value for \\$n\\$.
* Take no input and output values indefinitely.

The sequence starts: `2,2,3,4,2,3,4,5,3,2,3,4,3,4,5,6,2,3,4,5`

This is , so the shortest code in bytes wins.

--

Honestly, I'm surprised this isn't on the OEIS. I'm also uncertain whether there's any number above 6 in the sequence - not that I've searched that far.

# Answer
# JavaScript (Node.js), 63 bytes

```
f=(n,m=2,i=0,p=n-i**m)=>p<0?f(n,m+1):!p||i&&f(p)<m?m:f(n,m,i+1)

```

Try it online!

Time out for not so large n as its terrible recursion design. It could be fast if we apply memorize to it (70 bytes).

```
f=(n,m=2,i=0,p=n-i**m)=>f[n]??=p<0?f(n,m+1):!p||i&&f(p)<m?m:f(n,m,i+1)

o.value = [...Array(50000)].map((_, i) => i).filter(v => f(v) > 5).join(', ')
```

```
<a href="https://oeis.org/A111151">A111151</a>: <output id=o></output>
```
> 8 votes

# Answer
# Python 3.8, 109 bytes

This could probably be a bit shorter, but I tried to make it fast. Prints the sequence indefinitely.

```
a=[i:=1]
k=2
while[print(k),k:=2]:
 while all(k<=a[i-b**k]for b in range(1,1+int(i**(1/k)))):k+=1
 a+=k,;i+=1

```

Try it online!
> 7 votes

# Answer
# JavaScript (ES7), 79 bytes

Returns the n-th term (0-indexed).

```
f=(n,q=2)=>(g=(k,t=n,i=0)=>t?i>t|k<2||g(k-1,t-i**k)*g(k,t,i+1):0)(q)?f(n,q+1):q

```

Try it online!

### Commented

```
f = (            // f is the outer recursive function taking:
  n,             //   n = input
  q = 2          //   q = upper bound for the exponent
) =>             //
(                //
  g = (          // g is the inner recursive function taking:
    k,           //   k = exponent
    t = n,       //   t = remainder
    i = 0        //   i = base
  ) =>           //
  t ?            //   if t is not equal to 0:
    i > t |      //     abort if i is greater than t
                 //     (this is slower but shorter than i ** k > t)
    k < 2 ||     //     or k = 1
    g(           //     otherwise, do a recursive call:
      k - 1,     //       decrement k
      t - i ** k //       subtract i ** k from t
    ) *          //     end of recursive call
    g(           //     do another recursive call:
      k,         //       leave k unchanged
      t,         //       leave t unchanged
      i + 1      //       increment i
    )            //     end of recursive call
  :              //   else:
    0            //     success: return 0
)(q)             // initial call with k = q
?                // if it failed:
  f(n, q + 1)    //   try again with q + 1
:                // else:
  q              //   success: return q

```
> 5 votes

# Answer
# 05AB1E, 17 bytes

Very inefficient brute force approach. Prints \\$a(n)\\$ given \\$n\\$.

```
∞>.ΔIÝy<ãεā>mO}Iå

```

Try it online!

A more efficient recursive version that is similar to my Python answer is 23 bytes long:

```
λNU∞>.ΔXyzmLymXα₅ß›]Y0ǝ

```

Try it online!

**Commented**:

```
∞>.ΔIÝy<ãεā>mO}Iå   -- Takes input n and prints a(n)
∞>                  -- infinite list [2, 3, 4, ...]
  .Δ                -- find the first value y in this list with:
    IÝ              --   range from 0 to the input n
      y<ã           --   cartesian power [0 .. n] ^ (y-1)
         ε    }     --   map over each (y-1)-tuple:
          ā>        --     range [2 .. length+1] = [2 .. y]
            m       --     exponentiation
             O      --     sum the values
               Iå   --   is the input in this list?

λNU∞>.ΔXyzmLymXα₅ß›]Y0ǝ -- takes no input and prints the infinite sequence
λ                   -- start recursive environment with a(0)=1
                    -- for each N in [1, 2, ...], calculate a(N) by:
 NU                 --   store N in variable X
   ∞>.Δ             --   find y in [2, 3, 4, ...] with:
        yz          --     1/y
       X  m         --     X ^ (1/y)
           L        --     [1..floor(X^(1/y))]
            ym      --     [1..floor(X^(1/y))]^y
              Xα    --     abs([1..floor(X^(1/y))]^y - X)
                ₅   --     a(abs([1..floor(X^(1/y))]^y - X))
                 ß› --     y > min(a(abs([1..floor(X^(1/y))]^y - X)))
Y0ǝ                 -- Set the value at index 0 to 2

```
> 4 votes

# Answer
# Vyxal, 18 bytes

```
λ›⁰ʀnÞẊƛż›e∑;?c;ṅ›

```

Try it Online!

Vyxal has become bugless at last.
> 4 votes

# Answer
# Ruby, ~~84~~ 74 bytes

```
->n,*r{(2..n**n).find{|x|a=0;r=1;x/=n while x>0&&a+=(x%n)**r+=1;a==n}?r:2}

```

Try it online!
> 3 votes

# Answer
# 05AB1E, 30 bytes

```
Åœ¬_æÙδì€`é.Δā>zδmœ€Å\1%_Pà}g>

```

Outputs the value for a *positive* input \\$n\\$.

Try it online or verify the values in the range \\$\[1,25\]\\$ (with `æÙ` replaced with `η¯š` to speed it up).

**Explanation:**

```
Åœ                # Get all possible sum-lists that equal the (implicit) input
                  # Because these sums lack 0s, we add those as well:
  ¬               #  Head (without popping), which are an input amount of 1s
   _              #  Convert each to a 0
    æ             #  Get the powerset of this
     Ù            #  Uniquify this list
    η¯š           #  Sped-up alternative:
    η             #   Get the prefixes of this list
     ¯š           #   And prepend an additional empty list
       δ          #  Apply double-vectorized:
        ì         #   Prepend-merge the lists
         €`       #  Flatten the list of lists one level down
                  # (we've now added [0,input] amount of 0s to each sum of `Åœ`)
é                 # Sort this list of lists by length
 .Δ               # Find the first/shortest which is truthy for:
   ā              #  Push a list in the range [1,length] (without popping)
    >             #  Increase each by 1 to make the range [2,length+1]
     z            #  Calculate 1/n for each: [1/2,1/3,...,1/(length+1)]
      δ           #  Apply double-vectorized:
       m          #   Exponentiation
                  #  Check if at least one of these lists uses each exponent in
                  #  the range [2,length+1]:
        œ         #   Get all permutations of this list of lists
         €        #   Map each permutation-matrix to:
          Å\      #    Pop and leave its main diagonal
            1%    #   Modulo-1 on each
              _   #   And check if its decimals are 0 (thus it's an integer)
               P  #   Product to check if this is truthy for all
                à #   Max to check if this is truthy for any main diagonal
  }g>             # When we've found our result: pop and push its length + 1
                  # (after which it is output implicitly as result)

```

See this for a step-by-step output with added debug-lines.
> 3 votes

# Answer
# Charcoal, ~~40~~ 39 bytes

```
ＦＮ⊞υ⊗¬ιＦ…²χＦ⮌⌕Ａυ⁰Ｆ⊙υΣ✂…υ⊕⁻κＸμι±¹§≔υκιＩυ

```

Try it online! Link is to verbose version of code. Outputs the first `n` values. Explanation:

```
ＦＮ⊞υ⊗¬ι

```

Start with `0` having been found to have a value of `2` but none of the other values having been found yet.

```
Ｆ…²χ

```

Try from squares up to ninth powers.

```
Ｆ⮌⌕Ａυ⁰

```

Loop over all of the values that haven't yet been found in reverse order, so the highest index is tested first.

```
Ｆ⊙υΣ✂…υ⊕⁻κＸμι±¹

```

Subtract the powers of all the integers up to `n` from the current index and see if any of those values had previously been found. This is harder than it sounds as it's necessary to defeat Charcoal's cyclic indexing.

```
§≔υκι

```

If so then mark this value with the necessary power.

```
Ｉυ

```

Output all of the values.
> 3 votes

# Answer
# , ~~91~~ 88 bytes

```
f=function(n,m=2,o=n+3,a=n-(0:n)^m)`if`(m<o&&all(a),min(sapply(a[a>0],f,m+1,o)),m/(m<o))

```

Try it online!

Outputs the value for `n`. Very slow for even moderate `n`.

```
f=function(n,        # recursive function with argument n
 m=2,                # m=power to use in this iteration
 o=n+3,              # o=maximum power: stop when m reaches this
 a=n-(0:n)^m         # a=array of values by subtracting 0..n raised to m-th power from n
 )
 `if`(m<o,...,Inf)   # if m is too big, stop
  `if`(all(a),...,m) # if there are any zero values in a, then we've got n: stop and return m
                     # otherwise:
   min(              # return the lowest value of
    sapply(a[a>0],f,m+1,o)
                     # recursive calls to f with all positive values of a, using power m+1
   )

```

---

# , 79\* bytes

(\* assuming that there are no values above 6 in the sequence, as conjectured in the comment to A111151)

```
f=function(n,m=2,a=n-(0:n)^m)`if`(m<7&all(a),min(sapply(a[a>0],f,m+1)),m/(m<7))

```

Try it online!

Also outputs the value for `n`, but somewhat more efficiently than the 91-byte code, as the recursion can stop much sooner.
> 2 votes

# Answer
# Haskell, 73 bytes

```
f n=head(filter((!)n)[2..])
n!m=n==0||(m>1&&any(\k->(n-k^m)!(m-1))[0..n])

```

Try it Online!

f(n) returns the nth value in the sequence (0-indexed). n!m calculates whether n can be expressed as the sum of m (or fewer) powers.
> 1 votes

---
Tags: code-golf, sequence, number-theory
---


# Question
Title: AoCG2021 Day 5: Balancing sleigh with lots of trunks
Part of **Advent of Code Golf 2021** event. See the linked meta post for details.

The story continues from AoC2015 Day 24, Part 2.

*Here's why I'm posting instead of Bubbler*

---

To recap: Santa gives you the list of gift packages' weights. The packages must be split into multiple groups so that each group has the same weight, so that the sleigh is balanced and Santa can defy physics to deliver the presents.

Also, one of the groups goes to the passenger compartment, and Santa wants to have the maximal legroom, so the number of packages in there must be minimal. If there are ties, choose the one with the minimal "quantum entanglement" - the product of all weights in that group - to minimize the risk of physics doing its job, so to speak.

If you were to divide `[1, 2, 3, 4, 5, 7, 8, 9, 10, 11]` into three groups of equal weight, the possible choices are (QE stands for Quantum Entanglement):

```
Group 1;             Group 2; Group 3
11 9       (QE= 99); 10 8 2;  7 5 4 3 1
10 9 1     (QE= 90); 11 7 2;  8 5 4 3
10 8 2     (QE=160); 11 9;    7 5 4 3 1
10 7 3     (QE=210); 11 9;    8 5 4 2 1
10 5 4 1   (QE=200); 11 9;    8 7 3 2
10 5 3 2   (QE=300); 11 9;    8 7 4 1
10 4 3 2 1 (QE=240); 11 9;    8 7 5
9 8 3      (QE=216); 11 7 2;  10 5 4 1
9 7 4      (QE=252); 11 8 1;  10 5 3 2
9 5 4 2    (QE=360); 11 8 1;  10 7 3
8 7 5      (QE=280); 11 9;    10 4 3 2 1
8 5 4 3    (QE=480); 11 9;    10 7 2 1
7 5 4 3 1  (QE=420); 11 9;    10 8 2

```

Since `[11, 9]` has the smallest number of packages, you should choose that one.

It turns out that Santa's sleigh is a pretty advanced model and has a bunch of trunks instead of one. Under the same conditions, determine which presents should go into the passenger compartment.

**Input:** The total number of groups `n`, and the list of packages' weights. `n` is at least 3, and it is guaranteed that the list of weights can be split into `n` groups of equal weight.

**Output:** The optimal list of packages to be placed in the passenger compartment. The individual packages may be output in any order. If there are multiple optimal solutions (same number of packages and same quantum entanglement), output any one of them.

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
Weights, Groups -> Answer
[1, 2, 3, 4, 5, 7, 8, 9, 10, 11], 3 -> [11, 9]
[1, 2, 3, 4, 5, 7, 8, 9, 10, 11], 4 -> [11, 4]
[1, 2, 3, 4, 5, 7, 8, 9, 10, 11], 5 -> [11, 1]
[1, 1, 2, 2, 6, 6, 6, 6, 9], 3 -> [1, 6, 6] or [2, 2, 9]
[1, 2, 2, 3, 3, 3, 4, 6, 6, 9], 3 -> [4, 9]
[3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2], 3 -> [3, 2, 2, 2]

```

# Answer
# Jelly, 20 bytes

```
Œ!ŒṖ€ẎL=¥Ƈ§E$ƇẎPÞLÞḢ

```

Try it online!

Very messy port of my Vyxal answer. Full program.

-1 thanks to ovs.

```
Œ!                   # Permutations
  ŒṖ€                # Partitions of each of these
     Ẏ               # Flattened by depth 1
      ---Ƈ           # Filter by...
        ¥            # Last two links as a dyad...
      L              # Length
       =             # Equal to other input value?
          ---Ƈ       # Filter by...
            $        # Last two links as a monad...
          §          # Vectorised sums...
           E         # All equal?
              Ẏ      # Flatten by one level
                 -Þ  # Sort by...
                 L   # Length
               -Þ    # Sort by (tiebreak) product
               P     # Product
                   Ḣ # Get the first item.

```
> 4 votes

# Answer
# 05AB1E, 20 bytes

Can at least run some of the cases fast enough for TIO, with 6 bytes more all of them.

```
OI÷ÅœΣP}éIã.Δ˜{¹{Q}н

```

Try it online!
> 4 votes

# Answer
# Python 3, 143 bytes

```
f=lambda a,p,u=[],v=[]:p<2and a or a and min(f(a[1:],p,a[:1]+u,v),f(a[1:],p,u,a[:1]+v),key=len)or sum(u)==sum(v)/~-p==sum(f(v,p-1))and u or u+v

```

Try it online!

```
f=(lambda
  a,                        # input array, weight of packages
  p,                        # how many groups
  u=[],                     # packages selected in this group
  v=[]:                     # packages not selected in this group
    p<2 and a or            # if we want only 1 group
                            # then we simply include everything to this group
    a and min(              # if there are any packages
      f(a[1:],p,a[:1]+u,v), # we try to include it in current group
      f(a[1:],p,u,a[:1]+v), # or try to exclude it in current group
      key=len) or           # find out the answer which is shorter
                            # otherwise, every package are processed
    sum(u)==sum(v)/~-p      # if sum of selected package is what we want
          ==sum(f(v,p-1))   # and remaining packages may be grouped correctly
      and u or              # We found a possible grouping
    u+v                     # We failed to find out a correct grouping
                            # We return `u+v` here as it would be long enough
                            # to avoid it been selected after the min function
)

```
> 3 votes

# Answer
# Python 3, 211 bytes

```
lambda l,n:min([z for x in c(chain(*[[*c(l,_)]for _ in range(len(l))]),n)if (sorted(chain(*x))==l)*(len({*map(sum,x)})<2)for z in x],key=lambda y:eval("*".join(map(str,y))))
from itertools import*
c=combinations

```

Try it online!

@tsh's method is too complex for me, so my own itertools based solution
> 3 votes

# Answer
# 05AB1E, 13 bytes

```
.ŒʒOË}€`ΣP}éн

```

First input is the amount of groups, second the list of weights.

Try it online (times out for the third test case with 5 groups, but works for the others).

**Explanation:**

```
.Œ          # Get all possible ways to split the (implicit) second input-list
            # into the first (implicit) input-integer amount of group-lists
  ʒ         # Filter this list of lists of group-lists by:
   O        #  Get the sum of each inner group-list
    Ë       #  And check if all sums are equal
  }€`       # After the filter: flatten the list of lists of lists one level down
     ΣP}    # Sort this list of lists by their product
        é   # After that sort again by their length
         н  # Pop and leave the first list
            # (which is output implicitly as result)

```
> 3 votes

# Answer
# Charcoal, 46 bytes

```
ＦＥＸηＬθＥηΦθ⁼λ﹪÷ιＸηξηＦ⁼Σθ×η⌈Ｅι↨¹κＦι⊞υ⟦ＬλΠλλ⟧Ｉ⊟⌊υ

```

Try it online! Link is to verbose version of code. Very slow so only the smallest test case completes on TIO. Explanation:

```
ＦＥＸηＬθＥηΦθ⁼λ﹪÷ιＸηξη

```

Loop through all possible allocations of presents to compartments (including redundant allocations such as switching the allocations of two compartments).

```
Ｆ⁼Σθ×η⌈Ｅι↨¹κ

```

If the largest compartment under this allocation has the correct share of the total weight, then...

```
Ｆι⊞υ⟦ＬλΠλλ⟧

```

... save the size and product of the compartment with the compartment.

```
Ｉ⊟⌊υ

```

Output the compartment with the smallest size and product.

For comparison I've written a relatively fast algorithm, however it's 89 bytes long. (8 bytes can be trivially removed, but this makes the code much slower.)

```
≔⟦Ｅηυ⟧ζ≔⟦⟧εＷ⌈⁻θεＦ№θι«⊞ει≔⟦⟧δＦζＦηＦ¬∨⊙…λμ№νι›×η⁺ι↨¹§λμΣθ⊞δＥλ⎇⁼πμ⁺ξ⟦ι⟧ξ≔δζ»ＦζＦι⊞υ⟦ＬκΠκκ⟧Ｉ⊟⌊υ

```

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

```
≔⟦Ｅηυ⟧ζ

```

Start with `n` empty compartments.

```
≔⟦⟧εＷ⌈⁻θεＦ№θι«⊞ει

```

Enumerate the presents in descending order. (This is the best I can do given a lack of a sort primitive in Charcoal.)

```
≔⟦⟧δ

```

Start building up a new list of allocations of presents to compartments.

```
ＦζＦηＦ¬∨⊙…λμ№νι›×η⁺ι↨¹§λμΣθ

```

Loop through all of the compartments in all of the allocations, but ignore compartments when the same size present was already placed in an earlier compartment by a previous iteration or if it would overfill the current compartment.

```
⊞δＥλ⎇⁼πμ⁺ξ⟦ι⟧ξ

```

Save the new allocation.

```
≔δζ

```

Save the new list of allocations.

```
»ＦζＦι⊞υ⟦ＬκΠκκ⟧

```

At this point all of the presents will have been distributed to all of the compartments without overfilling any compartment, so flatten the list of allocations and get the size and product of each compartment.

```
Ｉ⊟⌊υ

```

Output the compartment with the smallest size and product.
> 2 votes

# Answer
# Python 3, 229 bytes:

```
f=lambda l,i,s,c,j:[(j,c)] if sum(c)==s else(l and f(l[:-1],i-1,s,c+[l[-1]],j+[i])+f(l[:-1],i-1,s,c,j))
y=lambda p,g:[q for w,q in f(p,len(p)-1,sum(p)//g,[],[]) if f([m for n,m in enumerate(p)if n not in w],0,sum(p)//g,[],[])][0]

```

Try it online!
> 2 votes

# Answer
# Pari/GP, 143 bytes

```
(w,g)->p=vecprod;s=vecsum(r=w)/g;forperm(vecsort(w),a,for(k=q=!c=0,#a,c+=a[k];c%s||q++>2||b=Vec(a[1..k]));#b==#r&&p(b)<p(r)||#b<#r&&q>g&&r=b);r

```

Try it online!

TIL: the `forperm` built-in only works for sorted lists. Thanks @tsh for providing a new testcase.
> 2 votes

# Answer
# Rust, 348 bytes

```
|w:&mut[_],g|{fn p(w:&mut[u64],i:usize,g:u64)->Option<Vec<u64>>{Some(if w[i..].iter().sum::<u64>()==g{if i!=0{p(&mut w[..i],0,g)?;}w[i..].to_vec()}else{let mut r=vec![];for j in i+1..w.len(){w.swap(i,[i+1,j][j%2]);p(w,j,g).map(|x|r.push(x));}r.iter().map(|x|(x.len(),x.iter().product::<u64>(),x)).min()?.2.to_vec()})}p(w,0,w.iter().sum::<u64>()/g)}

```

Try it online!

I think somebody should talk to Santa about time complexity.

Ungolfed:

```
|weights: &mut [_], group_size| {
    fn permutate(weights: &mut [u64], i: usize, group_weight: u64) -> Option<Vec<u64>> {
        Some(if weights[i..].iter().sum::<u64>() == group_weight {
            if i != 0 {
                permutate(&mut weights[..i], 0, group_weight)?;
            }
            weights[i..].to_vec()
        } else {
            let mut results = vec![];
            for j in i + 1..weights.len() {
                weights.swap(i, [i + 1, j][j % 2]);
                permutate(weights, j, group_weight).map(|x| results.push(x));
            }
            results
                .iter()
                .map(|x| (x.len(), x.iter().product::<u64>(), x))
                .min()?
                .2
                .to_vec()
        })
    }
    permutate(weights, 0, weights.iter().sum::<u64>() / group_size)
}

```
> 2 votes

# Answer
# Husk, 20 bytes

```
◄Π←kLΣfËΣföEeO¹OΣπ²Ṗ

```

Try it online!

Unfortunately too inefficient to run any of the provided test cases, but I *think* that it's correct based on testing with smaller ones:

```
[1,1,2,2,3] -> [3]
[3,1,2,2,4,0] -> [4]
[3,2,2,3,4,1] -> [4,1]

```

**How?**

`föEeO¹OΣπ²Ṗ` = Get all partitions, by filtering all combinations of n groups of all subsets of the input list (`π²Ṗ`), selecting () only those that are equal (`Ee`) to the sorted input list () after flattening & sorting (). I thought that the Husk `fork` (`§`) combinator should have saved a byte here, but I couldn't get it to work...

`fËΣ` = Filter (`f`) only those partitions with equal sums (`ËΣ`)

`←kLΣ` = Flatten the list of lists (`Σ`), and get the group of those with the smallest lengths (`←kL`)

`◄Π` = Return the list with the smallest product.
> 2 votes

# Answer
# TypeScript Types, 957 bytes

```
//@ts-ignore
type a<N,I=0,M=[]>=N extends M["length"]?M:a<N,I,[...M,I]>;type b<T,N=[]>=T extends[infer A,...infer T]?b<T,[...N,...a<A>]>:N;type c<T,S,G=[],U=T>=S extends[]?G:U extends U?S extends[...U[1],...infer S]?c<Exclude<T,U>,S,[...G,U]>:never:0;type d<A,B,N=[]>=A extends[...B,...infer A]?d<A,B,[...N,0]>:N;type e<T>={[K in keyof T]:T[K][1]};type f<T,N,S,G=[]>=N extends[0,...infer M]?c<T,S>extends infer X?X extends X?f<Exclude<T,X[number]>,M,S,[...G,e<X>]>:0:0:G;type M<I,N,M=a<N>,S=d<b<I>,M>,A=f<{[K in keyof I]:[K,a<I[K]>]}[number],M,S>[number],R=i<k<j<A>>>>={[K in keyof R]:R[K]["length"]};type g<A,B,C=[]>=A extends[0,...infer A]?g<A,B,[...C,...B]>:C;type h<T,N=[0]>=T extends[infer A,...infer T]?b<T,g<N,A>>:N;type i<T>=(T extends T?(x:()=>T)=>0:0)extends(x:infer U)=>0?U extends()=>infer V?V:0:0;type j<U,V=keyof U>=U extends U?keyof U extends V?U:never:never;type k<T,V=keyof(T extends T?h<T>:0)>=T extends T?keyof h<T>extends V?T:never:never

```

This really pushes TypeScript's type system to the limit. Calling the generic will give "Type instantiation is excessively deep and possibly infinite", but it will eventually still result in a valid answer for most test cases.

Try It Online!

Less Golfed (but just as cryptic)
> 2 votes

# Answer
# Vyxal, 26 bytes

```
ṖvøṖÞf'L⁰=;'Ṡ≈;vhƛ₍LΠwJ;↓Ṫ

```

Try it Online!

This was horrible to make. Vyxal is horridly cursed sometimes...

Note: Almost all sort-related functions are broken.

\\$O\left(n! \cdot 2^n\right)\\$ complexity I think, so can't run any testcases.

```
Ṗ                          # All permutations
 vøṖ                       # All partitions of these
    Þf                     # Flatten by 1 layer to get all partitions of permutations
      '   ;                # Filter by...
       L⁰=                 # Length is equal to input
           '  ;            # Filter by
            Ṡ≈             # Sums are all same
               vh          # Get first of each
                 ƛ     ;   # Map to...
                  ₍LΠ      # [length, product]
                     wJ    # Appended to original
                        ↓  # Minimum by last item ([length, product])
                         Ṫ # Remove the last of this.

```

22 byte version if sorting worked
> 1 votes

# Answer
# Ruby, ~~181 144 140~~ 129 bytes

```
->l,n{*r=l;(n**l.size).times{|x|z=l.group_by{(x/=n)%n}.values;z.map(&:sum).uniq[1]||r=(z<<r).min_by{|x|[x.size,x.reduce(:*)]}};r}

```

Try it online!
> 1 votes

# Answer
# Wolfram Language (Mathematica), 88 bytes

```
<<Combinatorica`
SortBy[Join@@Select[KSetPartitions@##,Equal@@Tr/@#&],1##&@@#+0#&][[1]]&

```

Try it online!
> 0 votes

---
Tags: code-golf, combinatorics
---


title: Draw Lines in ASCII

text:
# Question
Title: Draw Lines in ASCII
# Challenge

Draw lines in ASCII corresponding to given inputs:

in the first line there are given size of rows and columns of the view and number of separators between each point

in the second line is given list of lines separated by space

a line contains the position of head and tail coordinates (within the size of columns and rows) separated by space (x1 x2 y1 y2).

> In the below examples we used character '#' for filled spot, '.' for free spots and ' ' for the separator but you are free to use any other printable ASCII characters.

Sample input 1:

```
33 15 1
5 0 31 0 31 0 31 10 31 10 27 14 27 14 27 4 27 4 0 4 0 4 0 14 0 14 27 14 31 10 5 10 5 10 5 0 5 0 0 4 31 0 27 4 5 10 0 14

```

Sample output 1:

```
. . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # .
. . . . # # . . . . . . . . . . . . . . . . . . . . . . . . # # .
. . # # . # . . . . . . . . . . . . . . . . . . . . . . . # . # .
. # . . . # . . . . . . . . . . . . . . . . . . . . . . # . . # .
# # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . # .
# . . . . # . . . . . . . . . . . . . . . . . . . . . # . . . # .
# . . . . # . . . . . . . . . . . . . . . . . . . . . # . . . # .
# . . . . # . . . . . . . . . . . . . . . . . . . . . # . . . # .
# . . . . # . . . . . . . . . . . . . . . . . . . . . # . . . # .
# . . . . # . . . . . . . . . . . . . . . . . . . . . # . . . # .
# . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # .
# . . . # . . . . . . . . . . . . . . . . . . . . . . # . . # . .
# . # # . . . . . . . . . . . . . . . . . . . . . . . # . # . . .
# # . . . . . . . . . . . . . . . . . . . . . . . . . # # . . . .
# # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . .

```

Sample input 2:

```
31 15 0
0 0 30 14 0 14 30 0 15 0 15 14 0 7 30 7

```

Sample output 2:

```
##.............#.............##
..##...........#...........##..
....##.........#.........##....
.....###.......#......###......
........##.....#.....##........
..........###..#..###..........
.............#####.............
###############################
.............#####.............
..........###..#..###..........
.........##....#.....##........
......###......#......###......
....##.........#.........##....
..##...........#...........##..
##.............#.............##

```

**Bonus Points**

Use line position format like so `(y1,x1)-(y2,x2)`.

e.g.

```
31 15 0
(0,0)-(14,30) (14,0)-(0,30) (0,15)-(14,15) (7,0)-(7,30)

```

**Scoring**

This is `code-golf`, so the shortest solution wins.

---

Just to finish this up, simple python(3) answer would be:

Try it online!

```
a()

```

or python(1789) \*without escape characters:

Try it online!

```
""" Non-golfed version """

Resault = ""

def bresenham(x0, y0, x1, y1):
    dx = x1 - x0
    dy = y1 - y0
    xsign = 1 if dx > 0 else -1
    ysign = 1 if dy > 0 else -1
    dx = abs(dx)
    dy = abs(dy)
    if dx > dy:
        xx, xy, yx, yy = xsign, 0, 0, ysign
    else:
        dx, dy = dy, dx
        xx, xy, yx, yy = 0, ysign, xsign, 0
    D = 2 * dy - dx
    y = 0
    for x in range(dx + 1):
        yield x0 + x * xx + y * yx, y0 + x * xy + y * yy
        if D >= 0:
            y += 1
            D -= 2 * dx
        D += 2 * dy

class Point:
    def __init__(self, x: int, y: int):
        self.x = x
        self.y = y

class Line:
    def __init__(self, head: Point, tail: Point):
        self.head = head
        self.tail = tail

def drawline(size: tuple, lines: list, chrs=('.', '#', ' ')) -> Resault:
    global Resault
    co = []
    for line in lines:
        co.extend(list(bresenham(
            line.head.x, line.head.y, line.tail.x, line.tail.y)))
    for column in range(size[1]):
        for row in range(size[0]):
            if (row, column) in co:
                Resault += chrs[1]
            else:
                Resault += chrs[0]
            if row != size[0]-1:
                Resault += chrs[2]*size[2]
        if column != size[1]-1:
            Resault += "\n"
    return Resault

if __name__ == "__main__":
    size = tuple(map(int, input().split()))
    coordinates = [i[::-1] for i in [list(map(int, j.split(','))) for i in [
        i.split('-') for i in input().replace(')', '').replace(
            '(', '').split(' ')] for j in i]]
    coordinates = [coordinates[i-4:i] for i in range(4, len(coordinates)+4, 4)]
    lines = []
    for c in coordinates:
        lines.append(Line(Point(c[0][0], c[0][1]), Point(c[1][0], c[1][1])))
    print(drawline(size, lines))

```

# Answer
# Charcoal, 84 bytes, score unknown

```
≔⮌Ｉ⪪Ｓ θＵＯ⊟θ⊟θ.ＦＩＥ⪪Ｓ Ｅ⪪ι-⪪✂λ¹±¹¦¹,«≔Ｅ²↨Ｅι§μκ±¹ηＦ⊕⌈↔η«≔⁺·⁵Ｅ§ι⁰⁺λ∕×κ§ημ⌈↔ηκＪ⊟κ⊟κ#»»ＵＥ⊟θ

```

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

```
≔⮌Ｉ⪪Ｓ θ

```

Input the first line, split on spaces, cast to integer and reverse.

```
ＵＯ⊟θ⊟θ.

```

Draw the background of the desired size.

```
ＦＩＥ⪪Ｓ Ｅ⪪ι-⪪✂λ¹±¹¦¹,«

```

Input the second line, splice on spaces, split each piece on `-`, chop off the `()`s, split again on `,`, cast to integer, and loop over the sets of coordinates.

```
≔Ｅ²↨Ｅι§μκ±¹η

```

Calculate the difference between the start and end points.

```
Ｆ⊕⌈↔η«

```

Loop over the number of steps needed to draw the line.

```
≔⁺·⁵Ｅ§ι⁰⁺λ∕×κ§ημ⌈↔ηκ

```

Interpolate between the start and end point.

```
Ｊ⊟κ⊟κ#

```

Jump to the calculated position and output a `#`.

```
»»ＵＥ⊟θ

```

Space the output horizontally as desired.
> 0 votes

---
Tags: ascii-art, code-challenge, graphical-output, printable-ascii
---