Piet, 120 Codels
With codelsize 20:
Notes / How does it work?
Since it is not possible to use an array or string as input, this program works by taking a series of integers (representing ascii characters) as inputs. I thought about using character inputs at first but struggled to find a nice solution for termination, so now it terminates when any numer smaller than 1 is entered. It was originally only negative values for termination, but I had to change the initialization after writing the program, so now I can't fit the required 2
, only a 1
(26/45 on the trace image). This doesn't matter though because as per the challenge rules, only printable ascii characters are allowed.
Struggled for a long time with reentering the loop, though I found quite the elegant solution in the end. No pointer
or switch
operations, only the interpreter running into walls until it transitions back into the green codel to read the input (43->44 on the trace images).
Loop termination is achived by first duplicating the input, adding 1 and then checking if it is bigger than 1. If it is, the codel chooser is triggered and execution continues on the lower path. If it is not, the program contines left (Bright yellow codels, 31/50 on the trace images).
The supported input size is interpreter implementation dependent, though it would be possible to support an arbitrarily large input with the right interpreter (Say, for example, a Java interpreter that uses BigInteger
as internal values)
Just saw that the setup includes one unnecessary DUP
and CC
(7->8->9 in the trace images). No idea how that happened. This is effectively a noop though, it toggles the codel chooser 16 times which results in no change.
Npiet trace images
Setup and first loop:
Loop termination, output and exit:
Outputs
Forgive me if I only include one output, it just takes a long time to input :^)
String: "Eagles are great!"
PS B:\Marvin\Desktop\Piet> .\npiet.exe adler32.png
? 69
? 97
? 103
? 108
? 101
? 115
? 32
? 97
? 114
? 101
? 32
? 103
? 114
? 101
? 97
? 116
? 33
? -1
918816254
Npiet trace for [65, -1]
trace: step 0 (0,0/r,l nR -> 1,0/r,l dR):
action: push, value 4
trace: stack (1 values): 4
trace: step 1 (1,0/r,l dR -> 2,0/r,l dB):
action: duplicate
trace: stack (2 values): 4 4
trace: step 2 (2,0/r,l dB -> 3,0/r,l nM):
action: multiply
trace: stack (1 values): 16
trace: step 3 (3,0/r,l nM -> 4,0/r,l nC):
action: duplicate
trace: stack (2 values): 16 16
trace: step 4 (4,0/r,l nC -> 5,0/r,l nY):
action: duplicate
trace: stack (3 values): 16 16 16
trace: step 5 (5,0/r,l nY -> 6,0/r,l nM):
action: duplicate
trace: stack (4 values): 16 16 16 16
trace: step 6 (6,0/r,l nM -> 7,0/r,l nC):
action: duplicate
trace: stack (5 values): 16 16 16 16 16
trace: step 7 (7,0/r,l nC -> 8,0/r,l nY):
action: duplicate
trace: stack (6 values): 16 16 16 16 16 16
trace: step 8 (8,0/r,l nY -> 9,0/r,l lB):
action: switch
trace: stack (5 values): 16 16 16 16 16
trace: stack (5 values): 16 16 16 16 16
trace: step 9 (9,0/r,l lB -> 10,0/r,l dM):
action: multiply
trace: stack (4 values): 256 16 16 16
trace: step 10 (10,0/r,l dM -> 11,0/r,l nR):
action: multiply
trace: stack (3 values): 4096 16 16
trace: step 11 (11,0/r,l nR -> 12,0/r,l lY):
action: multiply
trace: stack (2 values): 65536 16
trace: step 12 (12,0/r,l lY -> 13,0/r,l lM):
action: duplicate
trace: stack (3 values): 65536 65536 16
trace: step 13 (13,0/r,l lM -> 14,0/r,l nM):
action: push, value 3
trace: stack (4 values): 3 65536 65536 16
trace: step 14 (14,0/r,l nM -> 15,0/r,l dM):
action: push, value 2
trace: stack (5 values): 2 3 65536 65536 16
trace: step 15 (15,0/r,l dM -> 16,0/r,l lC):
action: roll
trace: stack (3 values): 16 65536 65536
trace: step 16 (16,0/r,l lC -> 17,0/r,l nB):
action: sub
trace: stack (2 values): 65520 65536
trace: step 17 (17,0/r,l nB -> 18,0/r,l dB):
action: push, value 1
trace: stack (3 values): 1 65520 65536
trace: step 18 (18,0/r,l dB -> 19,0/r,l dM):
action: add
trace: stack (2 values): 65521 65536
trace: step 19 (19,0/r,l dM -> 19,1/d,r dC):
action: duplicate
trace: stack (3 values): 65521 65521 65536
trace: step 20 (19,1/d,r dC -> 18,1/l,l lC):
action: push, value 1
trace: stack (4 values): 1 65521 65521 65536
trace: step 21 (18,1/l,l lC -> 17,1/l,l nC):
action: push, value 1
trace: stack (5 values): 1 1 65521 65521 65536
trace: step 22 (17,1/l,l nC -> 16,1/l,l dB):
action: sub
trace: stack (4 values): 0 65521 65521 65536
trace: step 23 (16,1/l,l dB -> 15,1/l,l lB):
action: push, value 1
trace: stack (5 values): 1 0 65521 65521 65536
trace: step 24 (15,1/l,l lB -> 13,2/l,l dG):
action: in(number)
? 65
trace: stack (6 values): 65 1 0 65521 65521 65536
trace: step 25 (13,2/l,l dG -> 12,2/l,l dR):
action: duplicate
trace: stack (7 values): 65 65 1 0 65521 65521 65536
trace: step 26 (12,2/l,l dR -> 11,2/l,l lR):
action: push, value 1
trace: stack (8 values): 1 65 65 1 0 65521 65521 65536
trace: step 27 (11,2/l,l lR -> 10,2/l,l lY):
action: add
trace: stack (7 values): 66 65 1 0 65521 65521 65536
trace: step 28 (10,2/l,l lY -> 9,2/l,l nY):
action: push, value 1
trace: stack (8 values): 1 66 65 1 0 65521 65521 65536
trace: step 29 (9,2/l,l nY -> 8,1/l,r nB):
action: greater
trace: stack (7 values): 1 65 1 0 65521 65521 65536
trace: step 30 (8,1/l,r nB -> 7,1/l,r lY):
action: switch
trace: stack (6 values): 65 1 0 65521 65521 65536
trace: stack (6 values): 65 1 0 65521 65521 65536
trace: step 31 (7,1/l,l lY -> 6,2/l,l nY):
action: push, value 2
trace: stack (7 values): 2 65 1 0 65521 65521 65536
trace: step 32 (6,2/l,l nY -> 5,3/l,l dB):
action: pointer
trace: stack (6 values): 65 1 0 65521 65521 65536
trace: step 33 (5,3/r,l dB -> 7,4/r,l dM):
action: add
trace: stack (5 values): 66 0 65521 65521 65536
trace: step 34 (7,4/r,l dM -> 8,4/r,l dC):
action: duplicate
trace: stack (6 values): 66 66 0 65521 65521 65536
trace: step 35 (8,4/r,l dC -> 9,3/r,l lC):
action: push, value 3
trace: stack (7 values): 3 66 66 0 65521 65521 65536
trace: step 36 (9,3/r,l lC -> 10,3/r,l nC):
action: push, value 2
trace: stack (8 values): 2 3 66 66 0 65521 65521 65536
trace: step 37 (10,3/r,l nC -> 11,3/r,l dY):
action: roll
trace: stack (6 values): 0 66 66 65521 65521 65536
trace: step 38 (11,3/r,l dY -> 12,3/r,l dG):
action: add
trace: stack (5 values): 66 66 65521 65521 65536
trace: step 39 (12,3/r,l dG -> 13,3/r,l lG):
action: push, value 2
trace: stack (6 values): 2 66 66 65521 65521 65536
trace: step 40 (13,3/r,l lG -> 14,3/r,l nG):
action: push, value 1
trace: stack (7 values): 1 2 66 66 65521 65521 65536
trace: step 41 (14,3/r,l nG -> 15,3/r,l dR):
action: roll
trace: stack (5 values): 66 66 65521 65521 65536
trace: white cell(s) crossed - continuing with no command at 17,3...
trace: step 42 (15,3/r,l dR -> 17,3/r,l lB):
trace: step 43 (17,3/r,l lB -> 13,2/l,l dG):
action: in(number)
? -1
trace: stack (6 values): -1 66 66 65521 65521 65536
trace: step 44 (13,2/l,l dG -> 12,2/l,l dR):
action: duplicate
trace: stack (7 values): -1 -1 66 66 65521 65521 65536
trace: step 45 (12,2/l,l dR -> 11,2/l,l lR):
action: push, value 1
trace: stack (8 values): 1 -1 -1 66 66 65521 65521 65536
trace: step 46 (11,2/l,l lR -> 10,2/l,l lY):
action: add
trace: stack (7 values): 0 -1 66 66 65521 65521 65536
trace: step 47 (10,2/l,l lY -> 9,2/l,l nY):
action: push, value 1
trace: stack (8 values): 1 0 -1 66 66 65521 65521 65536
trace: step 48 (9,2/l,l nY -> 8,1/l,r nB):
action: greater
trace: stack (7 values): 0 -1 66 66 65521 65521 65536
trace: step 49 (8,1/l,r nB -> 7,1/l,r lY):
action: switch
trace: stack (6 values): -1 66 66 65521 65521 65536
trace: stack (6 values): -1 66 66 65521 65521 65536
trace: step 50 (7,1/l,r lY -> 6,1/l,r dY):
action: pop
trace: stack (5 values): 66 66 65521 65521 65536
trace: step 51 (6,1/l,r dY -> 4,1/l,r lY):
action: push, value 3
trace: stack (6 values): 3 66 66 65521 65521 65536
trace: step 52 (4,1/l,r lY -> 3,1/l,r nY):
action: push, value 2
trace: stack (7 values): 2 3 66 66 65521 65521 65536
trace: step 53 (3,1/l,r nY -> 2,1/l,r nM):
action: duplicate
trace: stack (8 values): 2 2 3 66 66 65521 65521 65536
trace: step 54 (2,1/l,r nM -> 1,1/l,r dG):
action: pointer
trace: stack (7 values): 2 3 66 66 65521 65521 65536
trace: step 55 (1,1/r,r dG -> 2,2/r,r lR):
action: roll
trace: stack (5 values): 65521 66 66 65521 65536
trace: step 56 (2,2/r,r lR -> 2,3/d,l nR):
action: push, value 1
trace: stack (6 values): 1 65521 66 66 65521 65536
trace: step 57 (2,3/d,l nR -> 2,4/d,l lC):
action: switch
trace: stack (5 values): 65521 66 66 65521 65536
trace: stack (5 values): 65521 66 66 65521 65536
trace: step 58 (2,4/d,r lC -> 2,5/d,r nM):
action: mod
trace: stack (4 values): 66 66 65521 65536
trace: step 59 (2,5/d,r nM -> 4,5/r,r dM):
action: push, value 3
trace: stack (5 values): 3 66 66 65521 65536
trace: step 60 (4,5/r,r dM -> 6,5/r,r lM):
action: push, value 2
trace: stack (6 values): 2 3 66 66 65521 65536
trace: step 61 (6,5/r,r lM -> 7,5/r,r nC):
action: roll
trace: stack (4 values): 65521 66 66 65536
trace: step 62 (7,5/r,r nC -> 8,5/r,r dM):
action: mod
trace: stack (3 values): 66 66 65536
trace: step 63 (8,5/r,r dM -> 11,5/r,r lM):
action: push, value 3
trace: stack (4 values): 3 66 66 65536
trace: step 64 (11,5/r,r lM -> 12,5/r,r nM):
action: push, value 1
trace: stack (5 values): 1 3 66 66 65536
trace: step 65 (12,5/r,r nM -> 13,5/r,r dC):
action: roll
trace: stack (3 values): 66 65536 66
trace: step 66 (13,5/r,r dC -> 14,5/r,r nB):
action: multiply
trace: stack (2 values): 4325376 66
trace: step 67 (14,5/r,r nB -> 15,5/r,r nM):
action: add
trace: stack (1 values): 4325442
trace: step 68 (15,5/r,r nM -> 16,5/r,r dB):
action: out(number)
4325442
trace: stack is empty
trace: white cell(s) crossed - continuing with no command at 19,5...
trace: step 69 (16,5/r,r dB -> 19,5/r,r nM):
8I will note that many of the answers here will fail with large or very large input sequences when they overflow the 32 or 64-bit integer sums, due to deferring the modulo operation until after the sums are computed. A truly compliant implementation would need to do the modulo operation at least periodically to keep the sums from overflowing. A 32-bit signed integer would overflow after only 4096 0xff's. A 64-bit signed integer would overflow after 256 MiB of 0xff's. – Mark Adler – 2016-04-30T19:01:08.397
@MarkAdler Hm, fair point. Since I didn't specify that the solutions would have to work for arbitrarily long strings and I don't want to invalidate existing answers, I'll set a limit for the input's length. – Dennis – 2016-04-30T19:20:59.920
@MarkAdler I don't think it matters. I'm fairly certain that overflow (signed 32-bit integers) can occur only with 4104 or more bytes of input, as the maximum value of high before the modulo is *n(n+1)/2255+n*. On top of that, the challenge restricts the input to bytes corresponding to printable ASCII characters. – Dennis – 2016-04-30T22:22:44.057
We could also allow languages to overflow their numeric types, and only require that the returned result be equivalent, accounting for overflow, to the correct result. – miles – 2016-04-30T23:32:45.450
Ah, ok. Missed the bit about ASCII, and you're correct about 4104. – Mark Adler – 2016-05-01T02:35:13.530
Using signed integer division, the longest string of
~
(126) that still works correctly isstd::string(5837, '~')
. 5838 fails. (In my x86-64 asm version, it fails with a SIGFPE divide error, because I picked noisy failure over wrong answers). @miles: Not sure what you mean. I think it makes a lot more sense to require actual correct results for ASCII-only strings up to 4096 bytes. This is not a problem for anything using 32bit or wider integers. It intentionally disqualifies delayed-modulo implementations that use narrower integers. – Peter Cordes – 2016-05-01T05:15:05.487When you say "array of integers", do you mean with every ASCII character zero-padded to 32-bits? That's incredibly convenient and generous, and I guess will save 2B in my x86 asm version (
lodsd
). I guess you're aiming to not bloat the code for languages that don't easily treat strings as arrays of numbers? – Peter Cordes – 2016-05-01T05:48:13.7271@PeterCordes Yes, arrays of 32-bit ints a perfectly fine. At least in my opinion, submissions should focus on golfing the algorithm, and pay as little attention as possible to I/O. – Dennis – 2016-05-01T05:53:21.770
Yeah, I agree with that motivation. It just feels weird for languages like C or asm that have no problem with byte arrays to save 2 bytes by requiring their caller to do a huge amount of memory copying to checksum a string. I listed both counts in my update, with / without taking advantage of that. There was some interesting golfing involved in saving 2 bytes, not just one, taking advantage of the known zero-padding. But it still feels wrong for that language, so it's a side-note, not the main code. Any thoughts? We should continue this discussion under my answer, if there's more to say. – Peter Cordes – 2016-05-01T06:09:24.023