2020 Programming Advent

stares at error messages · Dec 7, 2020

From https://kiwifarms.net/threads/programming-thread.41367/post-7859216

Some people were interested and others not. Best to put submission in there own place so not to clutter up other threads.

If you want to join-in all the problems are listed on https://adventofcode.com/

stares at error messages · Dec 7, 2020

Number 6 in Guile Scheme

Code:

#!/usr/bin/guile -s
!#

(use-modules
 (ice-9 regex)
 (srfi srfi-1))

(define test "abc\n\na\nb\nc\n\nab\nac\n\na\na\na\na\n\nb")
(define groups
  (map
   (lambda (s)
     (set! s (car s))
     (regexp-substitute/global #f "\n" s
                   'pre "" 'post))
   (eval-string
    (string-append "'((\""
           (regexp-substitute/global #f "\n\n" test
                         'pre "\") ( \"" 'post)
           "\"))"))))

(define (char-count-occurrence x count)
  (let ((chars (string->list x))
    (seen '()))
    (set! seen (cons (car chars) seen))
    (set! count (+ count 1))
    (map
     (lambda (k)
       (when (not (member k seen))
     (begin (set! count (+ count 1))
        (set! seen (cons k seen)))))
     chars)
    count))


(define result (fold char-count-occurrence 0 groups))
(format #t "There are ~a customs questions answered 'yes' in total.\n" result)

Otis Boi · Dec 7, 2020

Man if only I was better at coding would love to do something like this.

Kosher Salt · Dec 7, 2020

I've been doing them (mostly) in the browser's JS console, and in more or less piecewise fashion, so it'd be a pain to collect all the lines of code I enter on a given day into a single coherent solution for it (even if I wanted to).

Day 7 might be the most stupid thing I've seen, though. Bags in bags and bags... I mean come on.

edit: part 2 might be even dumber. I mean the correct answer should be "zero, leave your shiny gold bag at home and buy a single dull white bag to pack your shit in instead."

stares at error messages · Dec 7, 2020

Kosher Salt said:
I've been doing them (mostly) in the browser's JS console, and in more or less piecewise fashion, so it'd be a pain to collect all the lines of code I enter on a given day into a single coherent solution for it (even if I wanted to).

Day 7 might be the most stupid thing I've seen, though. Bags in bags and bags... I mean come on.

edit: part 2 might be even dumber. I mean the correct answer should be "zero, leave your shiny gold bag at home and buy a single dull white bag to pack your shit in instead."

I was just looking through the other problems in the advent. I agree with you, there not very good. For number 1 you would just fly to the tropical island and get your currency changed at the air port where you land. Dumb. It's like the problems just babel to fill the page.

Why don't we make up our own challenges? I've got some ideas. We could probably come up with something better than the problems in the advent.

RandomTwitterGuy · Dec 7, 2020

Otis Boi said:
Man if only I was better at coding would love to do something like this.

They are good training. Think of it as a way to test some skills.
Don't try and compare your self to some one else, it is all about trying things and starting to think in useful ways.

Take the first one.
You got some data and you want to compare every point with every ohter point.

It is all about getting the good idea and then trying things until they work and in this case you have a correct answer to compare to. So i say test things out.

Any way only had time to do the first and i will do a few if i have time tomorrow. I literally coded for 3-4 days straight now so i kind of don't want to do the second one, but i know how to do it as string manipulation is something i still know how to do.

I am coding it in C++ as it is the language i know best ohter then ST on plc, but i am not fucking doing it on a fucking PLC

Going to work my way through them when the mood strikes me.

Kosher Salt · Dec 8, 2020

stares at error messages said:
I was just looking through the other problems in the advent. I agree with you, there not very good. For number 1 you would just fly to the tropical island and get your currency changed at the air port where you land. Dumb. It's like the problems just babel to fill the page.

Why don't we make up our own challenges? I've got some ideas. We could probably come up with something better than the problems in the advent.

They're all bordering on retarded, but day 7 really took the cake.

Day 5 was kind of interesting in that it's literally just a binary encoding - replacing F and B and L and R with 0 and 1 in their respective cases, they can just be parsed as a binary integer to give you the seat ID. Then instead of coding to find the missing seat, I just copied-and-pasted the row and seat numbers into Excel and scatter plotted them and it was easy to spot the missing point.

CodeWars is a pretty good platform if you're into code challenges though.

edit: the latest, day 8, was a nice challenge.

cecograph · Dec 8, 2020

Haskell for me. Here was my day 6 for comparison:

Code:

import Data.Function
import Data.List
import Data.Maybe
import qualified Data.Set as S

splitOn :: (a -> Bool) -> [a] -> [[a]]
splitOn p =
  mapMaybe sequence
  . groupBy ((==) `on` isJust)
  . fmap (\x -> if p x then Nothing else Just x)

run :: ([String] -> Int) -> IO Int
run count = sum . fmap count . splitOn (== "") . lines <$> readFile "6.input"

part1 :: IO Int
part1 = run (length . nub . concat)

part2 :: IO Int
part2 = run (length . foldl1 S.intersection . fmap S.fromList)

Day 7 and 8 have a boring upfront bit of boilerplate in just parsing the input file. A lot of the advent of code problems have this. It means you get an advantage picking a language with a really ergonomic regex or parsing library.

I bet the Perl solutions are typically terse.

stares at error messages · Dec 8, 2020

Day 2

Code:

#!/usr/bin/guile -s
!#

(use-modules
 (ice-9 regex))

(define passwords
  "1-3 a: abcde
1-3 b: cdefg
2-9 c: ccccccccc")

(define test
  (map
   (lambda (y)
     (cons (string-split (car (car y)) char-set:whitespace) (cdr y)))
   (map
    (lambda (s)
      (eval-string
       (string-append "'((\""
              (regexp-substitute/global #f ": " s
                        'pre "\") \"" 'post)
              "\")")))
    (eval-string
     (string-append "'(\""
            (regexp-substitute/global #f "\n" passwords
                          'pre "\" \"" 'post)
            "\")")))))

(define result
  (map (lambda (t)
     (cons
      (not (not (string-match
             (string-append (car (cdr (car t)))
                    "{"
                    (regexp-substitute/global
                     #f "-" (car (car t)) 'pre "," 'post)
                    "}")
             (car (cdr t)))))
      (car (cdr t))))
       test))

(for-each (lambda (x)
        (if (car x)
        (format #t "Password ~a is valid" (cdr x))
        (format #t "Password ~a is not valid" (cdr x)))
        (newline))
      result)

I'm starting to think variables are not necessary and are just for my sake.

cecograph · Dec 9, 2020

stares at error messages said:

Day 2

Code:

#!/usr/bin/guile -s
!#

(use-modules
 (ice-9 regex))

(define passwords
  "1-3 a: abcde
1-3 b: cdefg
2-9 c: ccccccccc")

(define test
  (map
   (lambda (y)
     (cons (string-split (car (car y)) char-set:whitespace) (cdr y)))
   (map
    (lambda (s)
      (eval-string
       (string-append "'((\""
              (regexp-substitute/global #f ": " s
                        'pre "\") \"" 'post)
              "\")")))
    (eval-string
     (string-append "'(\""
            (regexp-substitute/global #f "\n" passwords
                          'pre "\" \"" 'post)
            "\")")))))

(define result
  (map (lambda (t)
     (cons
      (not (not (string-match
             (string-append (car (cdr (car t)))
                    "{"
                    (regexp-substitute/global
                     #f "-" (car (car t)) 'pre "," 'post)
                    "}")
             (car (cdr t)))))
      (car (cdr t))))
       test))

(for-each (lambda (x)
        (if (car x)
        (format #t "Password ~a is valid" (cdr x))
        (format #t "Password ~a is not valid" (cdr x)))
        (newline))
      result)

Doesn't look right to me. "1-3 a: bbbbaaaa" should fail parts 1 and 2, but this code says it's valid.

Your final regexp checks for a match of "m-n" contiguous occurrences of the letter, I think. But you want total occurrences.

I like the idea of first munging the data with a regular expression so you can read it as an s-expression. Do you need to use "eval-string" for this in Guile? Is there no equivalent to Common Lisp's "read"?

stares at error messages · Dec 10, 2020

cecograph said:
I like the idea of first munging the data with a regular expression so you can read it as an s-expression.

I first got the idea of using the structuer of cons to denote meaning for using the Guile Json library. You can feed in json formatted text and it turns the json into one big list you can work with in lisp. Latter I was watching this lecture, which now I really can't remember and don't want accidentally miss-quate, that said that before SGML Lisp was commonly used for structuring data like we would use XML for today. Using lisp this way actually starts to make a lot of scene once you start processing complicated lists for example:

Code:

  (define probe
    ;; no . (tit mb)
    `((35937 . ("Are the Planets Inhabited? by E. Walter Maunder"
        ,(+ 0.313 0.066 0.118 0.049 0.109)))
      (2000 . ("Don Quijote by Miguel de Cervantes Saavedra" 2.2))
      (61897 . ("Pieni palvelustyttö by Amy Le Feuvre" 0.250))
      (61903 . ("The Cable Game by Stanley Washburn"
        ,(+ 0.342 0.098 0.089 0.094 0.094 0.090 0.096 0.099 0.093 0.094 0.033 0.097)))
      (61899 . ("The Pirate Submarine by Percy F. Westerman" ,(+ 0.471 0.121 0.118 0.0063)))
      (1250 . ("Anthem by Ayn Rand" 0.138))
      (24145 . ("Doktoro Jekyll kaj Sinjoro Hyde by Robert Louis Stevenson"
        ,(+ 0.183 0.04)))
      (19876 . ("On the Fringe of the Great Fight by George Gallie Nasmith"
        ,(+ 0.465 0.098 0.092 0.156 0.117 0.124 0.133 0.132 0.151 0.172)))
      (13253 . ("Punch, or the London Charivari, Volume 100, February 21, 1891 by Various"
        ,(+ 0.095 0.027 0.264 0.079 0.052 0.031 0.027 0.131 0.262 0.06 0.24 0.086 0.0097 0.014 0.046 0.019)))
      (38374 . ("Abraham Lincoln: Was He a Christian? by John E. Remsburg" 0.484)) ))

There one list little mystery to cover. What are all these caar caddr cadar functions? Well you probably know car and cdr, you need these to while loop over things:

Code:

(define list '(a b c b e))
(while list
   (display (car list))
   (newline)
   (set! list (cdr list)))

Notice how all these strange extra function all start with C and end with R, well if you use cons and embedded cons to structure you data you find your self needing to take the cdr car car cdr and many other strange constitutions of taking the first member and then one deeper the first of the after first members. cdr car car cdr can now become cdaadr and it works just like when you had multiple calls to car and cdr. So every a in one these function is fist of one deeper and every d is the cdr of one deeper. This realization really makes it full circal that lisp expects you to use many bedded cons.

This might not be news to you but I got excited when this all fit together for me.

cecograph said:
Do you need to use "eval-string" for this in Guile? Is there no equivalent to Common Lisp's "read"?

In Guile (read) will just take stdin as a file port and parse it to lisp. It doesn't let you pass as string to it. I'm guessing because it's not implemented to take stdin as a string and instead uses binary representation of a file. Last time I looked at file ports I looked at file ports I think they needed you to specify encoding if changing them into strings. For example:

Code:

scheme@(guile-user)> (define thing (read))
this
$5 = this
scheme@(guile-user)> (symbol? thing)
$6 = #t
scheme@(guile-user)> (string? thing)
$7 = #f

There is a read-string function, but I'd have to look up which module it's in.

cecograph said:
Doesn't look right to me. "1-3 a: bbbbaaaa" should fail parts 1 and 2, but this code says it's valid.

Your final regexp checks for a match of "m-n" contiguous occurrences of the letter, I think. But you want total occurrences.

I see what I did wrong, I was relying on string-match to be both greedy and not permissive; take every occurrence and return #f not only if no matches were found, but if not the right matches were found. I understand why this didn't work. Taking this into mind, I also found that it would be easier to work with if the data was labeled, so I rewrote checking part with variables to make more readable.

Code:

#!/usr/bin/guile -s
!#

(use-modules
 (ice-9 regex))

;; (define passwords
;;   "1-3 a: abcde
;; 1-3 b: cdefg
;; 2-9 c: ccccccccc")

(define passwords
  "1-3 a: bbbbaaaa
1-4 n: nnnnnnnnnnnnnn
2-4 a: abababab
2-4 a: aababab
2-4 a: aaaa
2-4 a: aaabobobob")

(define test
  (map
   (lambda (y)
     (cons (string-split (car (car y)) char-set:whitespace) (cdr y)))
   (map
    (lambda (s)
      (eval-string
       (string-append "'((\""
              (regexp-substitute/global #f ": " s
                        'pre "\") \"" 'post)
              "\")")))
    (eval-string
     (string-append "'(\""
            (regexp-substitute/global #f "\n" passwords
                          'pre "\" \"" 'post)
            "\")")))))

(define (check-pw inputs)
  (map (lambda (t)
     (let ((letter (cadar t))
           (rule (caar t))
           (pw (cadr t))
           (matches '()))
       (set! matches
         (length (list-matches
          (string-append letter
                 "{"
                 (regexp-substitute/global
                  #f "-" rule 'pre "," 'post)
                 "}")
          pw)))

       ;; (display matches) (newline)

       (cond
        ((or (equal? matches 0) (> matches 1))
         (cons #f pw))
        ((equal? matches 1)
         (cons #t pw)))))
       inputs))

(define result (check-pw test))
(for-each (lambda (x)
        (if (car x)
            (format #t "Password ~a is valid" (cdr x))
            (format #t "Password ~a is not valid" (cdr x)))
        (newline))
      result)

I liked your implementation too. I'm not good at Haskell. Though I think you read the passwords in from a file which was a neat approach.

cecograph · Dec 11, 2020

stares at error messages said:
I first got the idea of using the structuer of cons to denote meaning for using the Guile Json library. You can feed in json formatted text and it turns the json into one big list you can work with in lisp. Latter I was watching this lecture, which now I really can't remember and don't want accidentally miss-quate, that said that before SGML Lisp was commonly used for structuring data like we would use XML for today.

I'm not sure how common it was. UNIX was around long before XML, but there are (very sadly) no s-expressions to be found in the UNIX core. It's just lots of horrible ad-hoc text formats. You see the same in early and now ubiquitous internet protocols, like email, which long predate XML.

Google Erik Naggum and XML to hear an old-school lisper rant aggressively against it. Naggum was heavily involved in the SGML project, so he knew what he was talking about.

SGML was the markup language that inspired HTML and XML. Its purpose was for marking up human written documents, being long bodies of text with annotations here and there for basic structure. The W3C decided to repurpose this markup language into a data format for arbitrary structured data. This is a really tortured repurposing that explains why XML is so god awful.

S-expressions, by contrast, were designed, way back in 1957, as a simultaneously human and machine readable format for arbitrary structured data. But it was criminally ignored in the 90s in favour of XML.

Nowadays, JSON has displaced XML to a great extent, and it seems the programming world has recovered a bit from that earlier insanity. JSON isn't god awful, but I still find s-expressions superior. It's still really shameful that it's been largely forgotten about. The story of s-expressions, XML and JSON is the story of why the computing world is badly amnesic and so is destined to reinvent shittier and shittier wheels.

So every a in one these function is fist of one deeper and every d is the cdr of one deeper. This realization really makes it full circal that lisp expects you to use many bedded cons.

Yep. And now consider that your own code is a cons! So even nesting code is nesting conses. But you can (and should!) use it for any data.

Code:
In Guile (read) will just take stdin as a file port and parse it to lisp. It doesn't let you pass as string to it. I'm guessing because it's not implemented to take stdin as a string and instead uses binary representation of a file. Last time I looked at file ports I looked at file ports I think they needed you to specify encoding if changing them into strings. For example:

Code:

scheme@(guile-user)> (define thing (read)) this $5 = this scheme@(guile-user)> (symbol? thing) $6 = #t scheme@(guile-user)> (string? thing) $7 = #f

There is a read-string function, but I'd have to look up which module it's in.

That's a little sad. Best I could do was:

Code:

> (call-with-input-string "(1 2 3)" read)

$1 = (1 2 3)

Code:
I see what I did wrong, I was relying on string-match to be both greedy and not permissive; take every occurrence and return #f not only if no matches were found, but if not the right matches were found. I understand why this didn't work. Taking this into mind, I also found that it would be easier to work with if the data was labeled, so I rewrote checking part with variables to make more readable.

Code:

[...]

This still doesn't look right. "2-4 a: abababab" should be valid (it has between 2 and 4 occurrences of 'a'). But your solution says it is invalid.

I'd avoid regular expressions entirely for this. Just use string splitting and then traverse the string in the password check, or convert the string to a list of characters and use set/list functions for the check.

I liked your implementation too. I'm not good at Haskell. Though I think you read the passwords in from a file which was a neat approach.

It's just so I can save the input page to a file from the browser, then run my code to get my answers.

Kosher Salt · Dec 11, 2020

cecograph said:
I'd avoid regular expressions entirely for this. Just use string splitting and then traverse the string in the password check, or convert the string to a list of characters and use set/list functions for the check.

Sort the characters. Then you know that the characters you're trying to count are all consecutive and are bounded either by other characters or by ends.

cecograph · Dec 11, 2020

Kosher Salt said:
Sort the characters. Then you know that the characters you're trying to count are all consecutive and are bounded either by other characters or by ends.

That'd work, but it's still not very Schemey, and besides, the count can be made in a single pass of the string.

There's a simple function listed here for the problem.

Today's problem was implementing a cellular automata. I gave it a go without using mutable data structures. It ran like dogshit in the interpreter, but after compiling with "-O2", I could solve both parts in under 1.5s.

Kosher Dill · Dec 11, 2020

cecograph said:
S-expressions, by contrast, were designed, way back in 1957, as a simultaneously human and machine readable format

They got the machine readable part at least.

Kosher Salt · Dec 11, 2020

cecograph said:
Today's problem was implementing a cellular automata. I gave it a go without using mutable data structures. It ran like dogshit in the interpreter, but after compiling with "-O2", I could solve both parts in under 1.5s.

Around 0.8-0.9 seconds in Javascript. I split the grid into an array of strings and in each iteration I created a new array and built the new strings one character at a time; the new array then became the starting array for the next cycle. The only thing that I reused was a lookup table that I initially built to hold the coordinates of the other chairs that could be seen from a given chair (e.g. the chair at 0,0 can see three chairs, which are at 0,1, at 1,1, and at 2,0 since there's an empty square of floor at 1,0).

Finding the chairs that could be seen from a given chair required working outward in each of the 8 queen's move directions from it until another chair was found, and doing that for each iteration of the loop would have been a lot of wasted effort.

stares at error messages · Dec 11, 2020

cecograph said:
This still doesn't look right. "2-4 a: abababab" should be valid (it has between 2 and 4 occurrences of 'a'). But your solution says it is invalid.

I'd avoid regular expressions entirely for this. Just use string splitting and then traverse the string in the password check, or convert the string to a list of characters and use set/list functions for the check.

I must have skimmed the instructions. I thought the matches were meant to be consecutive. I must have seen that the testing rule was the same as the {n,m} regexp syntax and ran from there. I've revised the it now. I still it's easier to do with regexp.

Code:

#!/usr/bin/guile -s
!#

(use-modules
 (ice-9 regex))

;; (define passwords
;;   "1-3 a: abcde
;; 1-3 b: cdefg
;; 2-9 c: ccccccccc")

(define passwords
  "1-3 a: bbbbaaaa
1-4 n: nnnnnnnnnnnnnn
2-4 a: abababab
2-4 a: aababab
2-4 a: aaaa
2-4 a: aaabobobob")

(define test
  (map
   (lambda (y)
     (cons (string-split (car (car y)) char-set:whitespace) (cdr y)))
   (map
    (lambda (s)
      (eval-string
       (string-append "'((\""
              (regexp-substitute/global #f ": " s
                        'pre "\") \"" 'post)
              "\")")))
    (eval-string
     (string-append "'(\""
            (regexp-substitute/global #f "\n" passwords
                          'pre "\" \"" 'post)
            "\")")))))

(define (check-pw inputs)
  (map (lambda (t)
     (let ((min (eval-string (car (string-split (caar t) (char-set #\-)))))
           (max (eval-string (cadr (string-split (caar t) (char-set #\-)))))
           (letter (cadar t))
           (pw (cadr t))
           (matches '()))
       (set! matches
         (length (list-matches letter pw)))

       ;; (display matches) (newline)

       (if (and (<= matches max) (>= matches min))
           (cons #t pw)
           (cons #f pw))))
     inputs))

;; (display test) (newline)

(define result (check-pw test))
(for-each (lambda (x)
        ;; (display x)
        (if (car x)
            (format #t "Password ~a is valid" (cdr x))
            (format #t "Password ~a is not valid" (cdr x)))
        (newline))
      result)

Erik Naggum is interesting. Thanks.

Kosher Salt · Dec 12, 2020

I found that they've got all of the previous years (oddly you don't get the list by clicking the year; you have to click Events to see the list of previous years, or just changing the date in the URL works obviously), and was working my way through the 2019 challenges.

Is it just me, or were they way tougher than this year's?

cecograph · Dec 12, 2020

Kosher Salt said:
I found that they've got all of the previous years (oddly you don't get the list by clicking the year; you have to click Events to see the list of previous years, or just changing the date in the URL works obviously), and was working my way through the 2019 challenges.

Is it just me, or were they way tougher than this year's?

I've done the first 5, and yeah. Day 5 was mostly bullshit. There's nothing clever involved. It's just laborious because it involves implementing a tedious spec.

Kosher Salt · Dec 12, 2020

cecograph said:
I've done the first 5, and yeah. Day 5 was mostly bullshit. There's nothing clever involved. It's just laborious because it involves implementing a tedious spec.

Let me know what you think of day 7.

2020 Programming Advent

stares at error messages

Readn' Tea Leaves

stares at error messages

Readn' Tea Leaves

Otis Boi

Sexy Cow man extraordinaire

Kosher Salt

(((NaCl)))

stares at error messages

Readn' Tea Leaves

RandomTwitterGuy

Kosher Salt

(((NaCl)))

cecograph

stares at error messages

Readn' Tea Leaves

cecograph

stares at error messages

Readn' Tea Leaves

cecograph

Kosher Salt

(((NaCl)))

cecograph

Kosher Dill

Potato Chips

Kosher Salt

(((NaCl)))

stares at error messages

Readn' Tea Leaves

Kosher Salt

(((NaCl)))

cecograph

Kosher Salt

(((NaCl)))