www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Advent of Code 2023

reply Siarhei Siamashka <siarhei.siamashka gmail.com> writes:
Advent of Code 2023 starts in a few hours from now. I suggest to 
discuss D language solutions here.
But to avoid spoilers, it's best to do this with a 24h delay 
after each puzzle is published.
Nov 30 2023
next sibling parent Sergey <kornburn yandex.ru> writes:
On Friday, 1 December 2023 at 01:01:31 UTC, Siarhei Siamashka 
wrote:

 Advent of Code 2023 starts in a few hours from now. I suggest 
 to discuss D language solutions here.
 But to avoid spoilers, it's best to do this with a 24h delay 
 after each puzzle is published.


Hi Siarhei. Nice to see that you are still around D forums. I 
thought you moved to Crystall.
Dec 01 2023
prev sibling parent reply Johannes Miesenhardt <johannesmiesenhardt gmail.com> writes:
On Friday, 1 December 2023 at 01:01:31 UTC, Siarhei Siamashka 
wrote:

 Advent of Code 2023 starts in a few hours from now. I suggest 
 to discuss D language solutions here.
 But to avoid spoilers, it's best to do this with a 24h delay 
 after each puzzle is published.


Day 1 solution

```d
version = Part2;

import std.stdio;
import std.algorithm;
import std.array;
import std.format;
import std.conv;
import std.string;

int[string] numberMap;

static this() {
	numberMap = [
		"one": 1,
		"two": 2,
		"three": 3,
		"four": 4,
		"five": 5,
		"six": 6,
		"seven": 7,
		"eight": 8,
		"nine": 9
	];
}

int findNum(T)(T /*char[] and string; since example and file read 
are different*/ str, bool reverse) {
	for(size_t i = reverse ? str.length - 1: 0; reverse ? i >= 0 : i 
< str.length; i += (reverse ? -1 : 1)) {
		auto c = str[i];
		if(c >= '0' && c <= '9')
			return to!int(c - '0');
		version(Part2) {
			foreach(key, value; numberMap) {
				if(key.length > str.length - i)
					continue;
				if(str[i..i+key.length] == key) {
					return value;
				}
			}
		}
	}
	writeln(str, " ", reverse);
	assert(false);
}

int main() {
	File("input")
		.byLine
	/*[
		"two1nine",
		"eightwothree",
		"abcone2threexyz",
		"xtwone3four",
		"4nineeightseven2",
		"zoneight234",
		"7pqrstsixteen"
	]*/
		.map!((str) {
			auto firstNum = findNum(str, false);
			auto secNum = findNum(str, true);
			auto code = firstNum * 10 + secNum;
			return code;
		})
		.sum
		.writeln;
	return 0;
}
```

I am a bloody beginner so if there are any things that are very 
wrong with this please point them out.
The fact that I need a template for accepting both a string and a 
char[] is very weird but I went with it. I am also curious if 
there is a better way for the reversible for-loop to happen. I 
saw foreach and foreach_reverse but I don't think that helps me 
here, since I swap them out based on a runtime argument.
Dec 02 2023
next sibling parent reply Sergey <kornburn yandex.ru> writes:
On Saturday, 2 December 2023 at 13:33:33 UTC, Johannes 
Miesenhardt wrote:

 Day 1 solution here, since I swap them out based on a runtime 
 argument.


In the Discord server we also have a topic about AoC2023. So feel 
free to join it as well.

Some other solutions that could be worth to check:

https://github.com/andrewlalis/AdventOfCode2023/blob/main/day_1/solution.d
https://github.com/schveiguy/adventofcode/blob/master/2023/day1/trebuchet.d
Dec 02 2023
parent reply Siarhei Siamashka <siarhei.siamashka gmail.com> writes:
On Saturday, 2 December 2023 at 14:35:19 UTC, Sergey wrote:

 Some other solutions that could be worth to check:

 https://github.com/andrewlalis/AdventOfCode2023/blob/main/day_1/solution.d
 https://github.com/schveiguy/adventofcode/blob/master/2023/day1/trebuchet.d


It's indeed a good idea to have solutions on github, so I pushed 
mine here: 
https://github.com/ssvb/adventofcode/blob/main/2023/day01/trebuchet.d

Maybe later I'll also publish all my D solutions for older 
puzzles from Advent of Code 2022, but that code needs a bit of 
cleanup.
Dec 03 2023
parent Siarhei Siamashka <siarhei.siamashka gmail.com> writes:
On Sunday, 3 December 2023 at 15:04:09 UTC, Siarhei Siamashka 
wrote:

 On Saturday, 2 December 2023 at 14:35:19 UTC, Sergey wrote:

 Some other solutions that could be worth to check:

 https://github.com/andrewlalis/AdventOfCode2023/blob/main/day_1/solution.d
 https://github.com/schveiguy/adventofcode/blob/master/2023/day1/trebuchet.d


 It's indeed a good idea to have solutions on github, so I 
 pushed mine here: 
 https://github.com/ssvb/adventofcode/blob/main/2023/day01/trebuchet.d


Bummer, looks like publishing the puzzle input data is forbidden: 
https://www.reddit.com/r/adventofcode/comments/18ehed6/re_not_sharing_inputs_psa_deleting_and_committing/

So for the purposes of automated testing and/or benchmarking, it 
would be necessary to invoke one of the numerous existing AoC 
command line client applications to download the input data 
before running the test. BTW, there seems to be no `aoc-cli` tool 
implemented in D yet ;-)
Dec 14 2023
prev sibling next sibling parent reply Siarhei Siamashka <siarhei.siamashka gmail.com> writes:
On Saturday, 2 December 2023 at 13:33:33 UTC, Johannes 
Miesenhardt wrote:

 I am a bloody beginner so if there are any things that are very 
 wrong with this please point them out.


Everything is fine as long as it works and does the job.


 The fact that I need a template for accepting both a string and 
 a char[] is very weird but I went with it.


The `string` type is not the same as `char[]`. It's actually 
`immutable(char)[]`. The differences are explained in the D 
language spec: 
https://dlang.org/spec/const3.html#const_and_immutable

Strings can be safely passed around between functions and 
multiple instances of the same string can share the same memory 
location, the characters inside of a string are read-only. 
Whereas character arrays allow read/write access.

Casting between character arrays and strings is a bad idea by 
design. Converting between strings and character arrays involves 
allocating memory for a new copy and this happens under the hood 
when calling `.dup`, `.idup`, `.to!string` or `.byLineCopy`.


 I am also curious if there is a better way for the reversible 
 for-loop to happen. I saw foreach and foreach_reverse but I 
 don't think that helps me here, since I swap them out based on 
 a runtime argument.


Below is my solution for the day 1 puzzle, which used 
https://dlang.org/library/std/range/retro.html to search 
characters starting from the end:

```D
import std;
void main() {
   auto input = stdin.byLineCopy.array;

   try {
     input.map!(s => (s.find!"a >= '0' && a <= '9'".front - '0') * 
10 +
                      s.retro.find!"a >= '0' && a <= '9'".front - 
'0')
          .sum.writefln!"Part1: %d";
   } catch (Error e) {
     writefln!"Part1: malformed input";
   }

   auto words = "one, two, three, four, five, six, seven, eight, 
nine"
        .split(", ").zip(iota(1, 10))
        .map!(x => tuple(x[0], x[0] ~ x[1].to!string ~ 
x[0])).array;
   input.map!(s => words.fold!((a, subst) => 
a.replace(subst[]))(s))
        .map!(s => (s.find!"a >= '0' && a <= '9'".front - '0') * 
10 +
                    s.retro.find!"a >= '0' && a <= '9'".front - 
'0')
        .sum.writefln!"Part2: %d";
}
```

The key features are:
* I'm using `import std;` and this makes the source code smaller 
(at the expense of a bit longer compile time). This is a bad 
style in real applications, but suitable here.
* I'm reading the input data from `stdin`, because it's a common 
convention for solving algorithmic puzzles on various websites 
(such as codeforces or atcoder).
* The string "one, two, three, four, five, six, seven, eight, 
nine" was copy-pasted from the puzzle text and then parsed by the 
code. This was it's a bit faster to implement and less prone to 
typos.
* For part2 the input text was preprocessed ("one" is replaced by 
"one1one", "two" is replaced by "two2two" and so on). And after 
such search & replace is complete, the whole task becomes the 
same as the already solved part1. Such approach makes the code 
slower, but the code is simpler and faster to implement. A useful 
tradeoff for the Advent of Code puzzles.
Dec 03 2023
parent reply Johannes Miesenhardt <johannesmiesenhardt gmail.com> writes:
On Sunday, 3 December 2023 at 14:51:37 UTC, Siarhei Siamashka 
wrote:

 [...]


Thanks, this is super helpful. I have one other question, in the 
solution you posted and also the one I posted in the discord 
today. I was required to use byLineCopy. I first used byLine but 
I for some reason that I can't really explain only got the last 
line from that. I switched to byLineCopy because I saw it in 
other peoples solution and that magically fixed all problems I 
had. What exactly happened here?
Dec 03 2023
next sibling parent Steven Schveighoffer <schveiguy gmail.com> writes:
On Sunday, 3 December 2023 at 18:56:32 UTC, Johannes Miesenhardt 
wrote:

 On Sunday, 3 December 2023 at 14:51:37 UTC, Siarhei Siamashka 
 wrote:

 [...]


 Thanks, this is super helpful. I have one other question, in 
 the solution you posted and also the one I posted in the 
 discord today. I was required to use byLineCopy. I first used 
 byLine but I for some reason that I can't really explain only 
 got the last line from that. I switched to byLineCopy because I 
 saw it in other peoples solution and that magically fixed all 
 problems I had. What exactly happened here?


byLine reuses the buffer. So it is only valid while you haven’t 
fetched the next line.

byLineCopy makes a copy of the line to give you so it will always 
remain valid.

In these simple small type problems I find it easier to just 
fetch the whole file into a string and work with that. The 
performance of parsing the input is negligible.

-Steve
Dec 03 2023
prev sibling parent Siarhei Siamashka <siarhei.siamashka gmail.com> writes:
On Sunday, 3 December 2023 at 18:56:32 UTC, Johannes Miesenhardt 
wrote:

 On Sunday, 3 December 2023 at 14:51:37 UTC, Siarhei Siamashka 
 wrote:

 [...]


 Thanks, this is super helpful. I have one other question, in 
 the solution you posted and also the one I posted in the 
 discord today. I was required to use byLineCopy. I first used 
 byLine but I for some reason that I can't really explain only 
 got the last line from that. I switched to byLineCopy because I 
 saw it in other peoples solution and that magically fixed all 
 problems I had. What exactly happened here?


It's very important to know how slices and garbage collector work 
together in D language. In particular, the results produced by 
the following code may look surprising to beginners:

```D
import std;

void f1(ref int[] x) {
   x[0] += 1;
   x    ~= [9, 9, 9, 9, 9, 9];
   x[0] -= 1;
}

void f2(int[] x) {
   x[0] += 1;
   x    ~= [9, 9, 9, 9, 9, 9];
   x[0] -= 1;
}

void main() {
   int[] a = [1, 2, 3, 4];
   writefln!"original:       %s"(a); // [1, 2, 3, 4]
   f1(a);
   writefln!"after f1:       %s"(a); // [1, 2, 3, 4, 9, 9, 9, 9, 
9, 9]
   f2(a);
   writefln!"after f2:       %s"(a); // [2, 2, 3, 4, 9, 9, 9, 9, 
9, 9]
   f2(a);
   writefln!"after f2 again: %s"(a); // [3, 2, 3, 4, 9, 9, 9, 9, 
9, 9]
   a.reserve(100);
   writefln!"reserved extra capacity to allow doing resize 
in-place";
   f2(a);
   writefln!"after f2 again: %s"(a); // [3, 2, 3, 4, 9, 9, 9, 9, 
9, 9]
}

```

Coming from the other programming languages, people are usually 
familiar with the concept of passing function arguments either by 
value or by reference. And the behavior of the `f2` function may 
seem odd in the example above. It never changes the size of the 
original array, but may modify its data in unexpected ways 
contrary to naive expectations. There's a detailed article on 
this topic, where all the necessary answers can be found: 
https://dlang.org/articles/d-array-article.html

Many functions in D language have their pairs/siblings. The 
potentially wasteful `.byLineCopy` has its potentially 
destructive sibling `.byLine`. There are also 
`.split`/`.splitter` or `.retro`/`.reverse` pairs with their own 
subtle, but important differences. The beginners may prefer to 
start with the less efficient, but easier to use variants with no 
undesirable side effects.
Dec 05 2023
prev sibling next sibling parent reply Julian Fondren <julian.fondren gmail.com> writes:
On Saturday, 2 December 2023 at 13:33:33 UTC, Johannes 
Miesenhardt wrote:

 I am a bloody beginner so if there are any things that are very 
 wrong with this please point them out.
 The fact that I need a template for accepting both a string and 
 a char[] is very weird but I went with it. I am also curious if 
 there is a better way for the reversible for-loop to happen. I 
 saw foreach and foreach_reverse but I don't think that helps me 
 here, since I swap them out based on a runtime argument.


Rather than putting `version = Part2;` in the source, you can 
specify that on the commandline. This doesn't work with rdmd, but 
these work:

```
$ dmd -run day1.d
$ dmd -version=Part2 day1.d
$ ldc2 --d-version=Part2 --run day1.d
$ gdc -fversion=Part2 day1.d && ./a.out
```

Rather than the template you could only accept 
`immutable(char)[]` and use `str.representation.assumeUTF` to get 
that from a string, without any extra allocation. There's a table 
at 
https://d.minimaltype.com/index.cgi/wiki?name=string+type+conversions that
might be helpful (although I notice the unicode tests have some bitrot due to
increased safety in the language.)

You may still want a template though, to specialize on the 
`reverse` variable. That only changes these lines:

```d
int findNum(bool reverse)(immutable(char)[] str) {
...
     auto firstNum = findNum!false(str.representation.assumeUTF);
     auto secNum = findNum!true(str.representation.assumeUTF);
```

Bonus from using a dynamic array: it would be much more annoying 
to have `reverse` as a template argument if you were still 
relying on an implicit `T` parameter at the callsite.

And, `unittest {}` is a great feature of d. Instead of editing 
your code to run tests, changing things while working with the 
real input, not realizing that you broke your tests, then getting 
timed out when you submit your answer to AoC, you can doublecheck 
just before submission that `dmd -unittest -run day1.d` still 
passes.

In your loop over numberMap, you could use

```d
if (str[i..$].startsWith(key) == key) return value;
```

Otherwise, I think it's fine good. People might differ on style, 
but it doesn't look bad at all compared to some other 
implementations I've seen. The several ternary operators are the 
only awkward bit. Since you're a beginner you might find it 
interesting to implement a range that yields chars in reverse 
order, and have `findNum` take a range.
Dec 03 2023
parent Julian Fondren <julian.fondren gmail.com> writes:
On Sunday, 3 December 2023 at 23:44:43 UTC, Julian Fondren wrote:

 ```d
 if (str[i..$].startsWith(key)) return value;
 ```


Corrected. The other doesn't compile, unless you never run it 
with -version=Part2 ...
Dec 03 2023
prev sibling parent reply matheus <matheus gmail.com> writes:
On Saturday, 2 December 2023 at 13:33:33 UTC, Johannes 
Miesenhardt wrote:

 On Friday, 1 December 2023 at 01:01:31 UTC, Siarhei Siamashka 
 wrote:

 Advent of Code 2023 starts in a few hours from now. I suggest 
 to discuss D language solutions here.
 But to avoid spoilers, it's best to do this with a 24h delay 
 after each puzzle is published.


 Day 1 solution

 ```d
 version = Part2;

 import std.stdio;
 import std.algorithm;
 import std.array;
 import std.format;
 import std.conv;
 import std.string;
 ...


Why do you do multiple imports instead of one import std;?

I means is there any difference in CT?

Matheus.
Dec 03 2023
parent reply Siarhei Siamashka <siarhei.siamashka gmail.com> writes:
On Monday, 4 December 2023 at 03:07:07 UTC, matheus wrote:

 import std.stdio;
 import std.algorithm;
 import std.array;
 import std.format;
 import std.conv;
 import std.string;
 ...


 Why do you do multiple imports instead of one import std;?

 I means is there any difference in CT?


The code indeed compiles faster with fewer imports and this pays 
off in the long run for the actively developed large projects. 
Additionally, it's a good idea not to pollute the namespace with 
the functions that the developer has no intention to use.
Dec 03 2023
parent Julian Fondren <julian.fondren gmail.com> writes:
On Monday, 4 December 2023 at 03:50:47 UTC, Siarhei Siamashka 
wrote:

 On Monday, 4 December 2023 at 03:07:07 UTC, matheus wrote:

 import std.stdio;
 import std.algorithm;
 import std.array;
 import std.format;
 import std.conv;
 import std.string;
 ...


 Why do you do multiple imports instead of one import std;?

 I means is there any difference in CT?


 The code indeed compiles faster with fewer imports and this 
 pays off in the long run for the actively developed large 
 projects. Additionally, it's a good idea not to pollute the 
 namespace with the functions that the developer has no 
 intention to use.


```
   dmd -betterC hellobc.d ran
     6.18 ± 0.33 times faster than dmd hellosel.d
    19.76 ± 1.06 times faster than dmd hellostd.d
```
26ms, 136ms, 470ms.
16MB, 56MB, 154MB.
-betterC with selected import of core.stdc.stdio
selected import of std.stdio.writeln
import std.

D has the capability to compile extremely quickly. dmd compiles 
itself in a second or two. But it also gives you plenty of 
opportunities to trade that for convenience.
Dec 03 2023