Fork me on GitHub
#adventofcode
<
2017-12-07
>
minikomi02:12:27

Never really used reduced before.. useful!

minikomi03:12:52

how about (drop max-idx (take (+ max-val max-idx) (cycle (range memory-length))))

mfikes03:12:41

Cool. Nice way to avoid mod 🙂

cjmurphy03:12:12

@minikomi Yes (cycle (range num-memory-banks)) is better than (mapcat identity (repeat (range num-memory-banks))). Now that I know about cycle I won't have to coerce it from other functions. Thanks @mfikes 🙂

mfikes04:12:58

cycle can also be useful in the day 1 problem, where the problem definition indicates "The list is circular"

minikomi04:12:13

Got a banana and my cup of tea. Ready.

grzm05:12:42

done yet?

grzm05:12:31

I'm about to start

grzm05:12:37

no pressure 🙂

minikomi05:12:52

oops.. emacs locked up when i pasted in the input lol

minikomi05:12:34

I think all the parenthesis messed with it

minikomi05:12:18

stuck on part 2 😕

minikomi06:12:53

Getting the "right" answer for the test input, but being denied on my actual input

dyankowsky06:12:17

it's a good one

grzm06:12:14

yeah, I need practice with trees 🙂

dyankowsky06:12:04

I managed to get the correct solution partially "by hand", now I'm going back to finish the code

dyankowsky06:12:08

to part2 that is

minikomi06:12:28

got it but ... but what a mess lol

minikomi06:12:07

"Elapsed time: 3.052496 msecs" ... quick though

dyankowsky06:12:29

heh, mine's about 3x slower

dyankowsky06:12:33

but I'm OK with that

minikomi06:12:37

ah, input probably different haha

minikomi06:12:48

can you send me your input private message?

minikomi06:12:56

i'll give it a whirl

minikomi06:12:33

also works 😜

grzm07:12:00

okay. I think I'm going for the most baroque solution

borkdude08:12:28

Solved the problem, but have to clean up the code. Also used ex-info 🙂

minikomi08:12:37

I bet there's a good way to use some kind of walk here

minikomi09:12:39

ah -- tree-seq was what i wanted

minikomi10:12:56

I discovered tree-seq and went crazy with it on my refactor hahaha

borkdude10:12:39

To keep it sustainable, I’ll try not to think about this puzzle and to tweak things all day 😉

minikomi10:12:10

yeah, you know how it is when you find a new tool though 😉

orestis11:12:58

I had a very bad night sleep so I solved part 2 almost by hand.

orestis11:12:32

This is one I would like to go back to and see how trees work in clojure!

nooga11:12:09

it’s ugly and I forgot about tree-seq existence

nooga11:12:16

but it seems to work 😄

nooga13:12:39

my goal with these is to arrive at the solution asap, without too much tinkering with performance and algorithmic elegance

thegeez13:12:42

Well that was the first actual challenge of this years calendar for me

val_waeselynck13:12:55

Getting to try some libs that make it easy to solve the problems can be a good value add too. Working on last year's problems, I've been able to use Clara Rules for example

thegeez13:12:08

Looking through your datascript solution now, never applied datascript or datomic to any advent problems yet

val_waeselynck13:12:08

Frankly, for this problem, DataScript turned out to be more overkill than I hoped.

val_waeselynck13:12:24

still, quite comfortable for representing graphs.

borkdude14:12:40

I thought I would need a delay construction like with 2015's day 7, but this problem didn’t require it because of the regularity in the graph

borkdude14:12:25

Fun useless fact: both part 1 and 2 run at about 6.8 ms (using criterium)

minikomi02:12:04

Getting under 2ms for part 2 with your input on my loop/recur solution.. tree-seq solution turns out to be slower at ~14ms.. guess we can stop early once an unbalanced branch has a balanced set of children.

borkdude14:12:52

All you needed to parse this one was clojure.edn/read-string and destructuring (SPOILER in thread) 🙂

borkdude14:12:50

[[name [weight]
    & [arrow & names]]]

borkdude14:12:43

I like what thegeez did with the underscore for the arrow, to emphasize this is just a separator

mfikes15:12:08

Nice parsing approach @borkdude I like it!

borkdude15:12:45

@mfikes Ah, set/mapinvert and oh yes, .indexOf

borkdude15:12:05

@mfikes Nice solution again!

mfikes15:12:12

I too had difficulty with part 2, trying perhaps 3 incorrect solutions until I figured out what was needed. And I did that part by hand, and backfilled the code 🙂

borkdude15:12:47

This year my extra challenge is to finish before coffee, so I wasn’t too concerned of making it the most beautiful

Miķelis Vindavs15:12:26

has anyone tried an approach with inverting the whole tree?

borkdude15:12:56

I don’t know about inverting the whole tree, but I keep a map of name -> ancestors and I’ve inverted that one in the second part

Miķelis Vindavs15:12:58

in part 1 i iteratively pruned off all leaves and references to them until only the root is left

Miķelis Vindavs15:12:14

right, well that’s essentially inverting it i guess

borkdude15:12:24

in part 1 I simply found the name without any ancestors

Miķelis Vindavs15:12:44

that’s simpler

borkdude15:12:44

set/difference as mfikes did

Miķelis Vindavs15:12:49

didn’t think of that

Miķelis Vindavs15:12:01

the puzzles publish at 7am local time 😅

borkdude15:12:14

local time, really?

Miķelis Vindavs15:12:16

for me part 2 is an ugly solution with println which kinda works like throw in some of the other solutions

Miķelis Vindavs15:12:36

i rewrote it to use reduced but it’s uglier than the throw variant

borkdude15:12:48

yeah, exceptions really helped me too 😉

borkdude15:12:56

ex-data ftw

Miķelis Vindavs15:12:02

sometimes that’s really nice for an early return

mfikes15:12:23

For me, I started with reduced for early return, and then went with some

Miķelis Vindavs15:12:28

i’m hoping to try a solution with walk

Miķelis Vindavs15:12:07

can you explain more?

Miķelis Vindavs15:12:21

did you get rid of the reduced and replaced it with some, or used both?

Miķelis Vindavs15:12:00

(let [[w tops] (get tower root)
        top-res (group-by #(find-unbalanced tower %) tops)]
    (or (some (comp #(when (reduced? %) %) first) top-res)
the problem that prevented me from an elegant solution is the fact that I need frequencies or group-by and only one of the values is reduced?

Miķelis Vindavs15:12:13

but I haven’t spent much time trying to make it prettier

Miķelis Vindavs15:12:44

since in the morning I wasted around 20 minutes because my parsing regex was using (....) for the name part since in the test input all names were 4 chars long

Miķelis Vindavs15:12:51

and I thought I had an error in the solution itself which I couldn’t find… until i fixed the regex to be ([^ ]+)

mfikes15:12:31

I started by reduceing over the data, but I had a nil (and ignored) accumulator, and had it stop with reduced when it found the unbalanced bit. I then took this reduce, and took the accumulator out of the reducing function, and essentially turned it into a predicate for some. Example:

(reduce (fn [_ x] (when (odd? x) (reduced x))) nil [2 4 2 7 2])
can be simplified to
(some (fn [x] (when (odd? x) x)) [2 4 2 7 2])

mfikes15:12:27

I'm curious about people using Spec to parse this one. Digging through the solutions now...

borkdude15:12:05

I found spec a bit overkill for this one

mfikes15:12:21

Yes, I like your destructuring

borkdude15:12:07

haha, even using the mapping from "(20)" to 20 by first 😉

borkdude15:12:38

or (nth 0) is what destructuring is using

mfikes15:12:38

Yes. I couldn't figure out how to get Spec to do that for me.

borkdude15:12:04

Sometimes things just map co-incidentally well to edn

mfikes15:12:27

Hmm. A lot of silver stars right now. I wonder if that is normal for this time of day.

borkdude15:12:49

If you have kids and have to start early at work, I can imagine this is not something you do on the bus

mfikes15:12:48

Yeah. Perhaps part 2 is challenging. I found the spiral more challenging.

borkdude15:12:04

I found this one more challenging, but when I found out about the squares at the bottom right, I felt really dumb

mfikes15:12:59

Yeah, I'm not like Gauss. I would have started adding 1, 2, 3...

borkdude15:12:15

Ulam’s spiral, it’s a thing

mfikes15:12:34

Yep, Ulam is what immediately came to mind for me as well 🙂

borkdude15:12:15

Never heard of it before. These are not typical problems you run into in day to day coding

borkdude15:12:43

But now I love it. Will never forget Ulam again 😛.

mfikes15:12:30

Do the AoC problems get progressively more difficult over the month?

mfikes15:12:52

(Like 4Clojure?)

borkdude15:12:30

I hope not. 😛

val_waeselynck15:12:05

@mfikes @borkdude From what I saw in AoC 2016, they do get more difficult 😛

mfikes15:12:35

I recall some of the 4Clojure problems getting into the 4-hour range near the end

val_waeselynck15:12:37

(only did a subset of AoC 2016)

mfikes15:12:39

Interestingly, if you look at tentamen's part 2 solution (https://github.com/tentamen/adventofcode/blob/master/src/adventofcode2017/day7.clj), you can see that the input resulted in the unbalanced node being at the root of the tree, and if you are lucky with such a data set, you can skip some coding. (If I try that code on my input, it exhausts the stack somewhere in it)

val_waeselynck15:12:15

Since we've been talking a lot about performance lately: I've been working on problem 23 of AoC 2016, in which performance ends up being rather critical. (The problem is to implement an interpreter about a very basic assembly that self-modifies code: https://adventofcode.com/2016/day/23) I first did a "Clojure-idiomatic" solution, with immutable state and multimethods (https://github.com/vvvvalvalval/advent-of-code-2017/blob/master/src/aoc2016/day23.clj#L44). Then I saw it tooks at least 30min to run on part 2, and did a second version that uses more primitive Java stuff (arrays, primitive, enums): See https://github.com/vvvvalvalval/advent-of-code-2017/blob/master/src/aoc2016/day23.clj#L165 and https://github.com/vvvvalvalval/advent-of-code-2017/blob/master/java/aoc2016/Day23.java The second version turned out to be about 100 times faster (16 seconds instead of 20 minutes).

val_waeselynck15:12:33

Thought people might find this interesting

mfikes15:12:08

Yeah, @val_waeselynck it seems like this assertion might be true: "If you solve any problem with Clojure, you can come up with a succinct, maintainable, readable solution. If you need perf, there is often an order of magnitude or more available by switching to lower level constructs, and you can often get away with going down that path for the perf-critical portion of your code."

mfikes15:12:05

One a large project I was on recently (where overall perf was critical), it felt like 80–90% of the code could be Clojure, and the rest could still be "Clojure", but really Java in disguise.

mfikes15:12:08

I think this assertion is true for the ClojureScript compiler, in a sense. Most of it is normal code, but the hot spots have been optimized in ways that deviate from "normal"

val_waeselynck15:12:41

However, I saw Martin Odersky say in a talk that a compiler typically has no hot spots - but that may be more true of compilers that have to do a fair amount of static inference

mfikes16:12:00

Hmm. Very odd. The ClojureScript compiler seems like any other program to me. It has bits that are very hot compared to others. Martin is a genius so perhaps I'll dig up that talk.

val_waeselynck15:12:49

@mfikes Totally agree with that. It should also be noted that even if I had started with the Java thing, it would have taken me more time overall to debug it and run it, given the time it took me to debug it 🙂 (granted, that may be because my Java is a little rusty)

mfikes15:12:21

Also, lots of the highly-performant and desirable algorithms that were invented in the 60s and 70s heavily rely on mutation. Perhaps that caused a lot of what I saw when working on the large project.

mfikes15:12:51

(Literature is thin on functional algorithms.)

val_waeselynck16:12:02

@mfikes I would argue SQL query engines are examples of highly-performant functional algorithms - i.e they yields highly performant programs that manipulate only immutable values

mfikes16:12:42

Good point. I wonder if they are functional on the outside but inside it is like "transient city"

val_waeselynck16:12:27

I believe they totally are transient inside - but it's a good testimony that being declarative makes a lot of room for global optimizations

val_waeselynck16:12:49

The virtual DOM is another such example

mfikes16:12:58

This entire subject is, of course, important. If it weren't for the availability of these tradeoffs, you really couldn't use Clojure for a large class of problems.

mfikes16:12:02

In other words, if you buy into using Clojure, I think you have to accept that for parts of your program, you can't insist on the ideal Clojure approach. (Unless your problem has no perf aspects, of course.)

borkdude16:12:16

@mfikes about the input, I checked if I wasn’t just lucky with my input so I took yours: https://github.com/borkdude/aoc2017/blob/master/src/day7.clj#L111

mfikes16:12:12

Yeah, for tentamen you can see that part of the code has a comment showing that the root is where the unbalanced node is. Then the remainder of the code leverages that fact. Fair.

val_waeselynck16:12:26

@mfikes I even find that Clojure can be a more elegant solution to some problems in the high-performance space, what with macros and the runtime compiler as zero-cost abstractions

borkdude16:12:15

yeah, or take Om vs React being faster due to immutable state

mfikes16:12:25

Definitely: Here is another effect I've seen. Since it is so damned easy to change Clojure code to do something in a different way, it is often feasible to explore different approaches and end up with a faster solution than if you were working in Java.

mfikes16:12:51

If you were in Java, you get calcified in an approach quickly.

mfikes16:12:57

Time is money. If you can't explore alternatives you often have to accept the perf you have.

val_waeselynck16:12:43

@mfikes Funnily, you could say that Clojure programmers are to Java Programmers what JITs interpreters are to AOT compilers: the first start very quickly and spend a little time optimizing the critical parts based on experience, the other ones start slowly and spend a lot of time speculating on what is going to be critical (and being pessimistic about it)

mfikes16:12:55

Think about the extreme of programming in machine code. Once you've solved a problem, you are pretty challenged to try a different approach, no matter how fasts your machine code runs.

mfikes16:12:11

This has led to a philosophy: Develop in the highest-level programming paradigm you can find that also affords you the opportunity to delve lower when needed.

borkdude16:12:25

Breadth first

borkdude16:12:35

Also, when correctness isn’t an issue (you want to research solutions first, handling all edge cases is not a problem) then types can get in the way a bit, where you have to be explicit when you don’t want to be

mfikes16:12:13

@val_waeselynck I like your JIT to AOT analogy

borkdude16:12:52

Also, the REPL helps a lot in this

mfikes16:12:52

Exactly. The fact that ClojureScript can be thought of as a compiler is the wrong way of thinking of it, IMHO. The best way to think of ClojureScript is just as a Lisp, but with a mode that can be AOT'd to produce a small artifact when you really need it.

val_waeselynck16:12:09

@borkdude totally. Being able to use Criterium and Tufte on the fly helps a lot when optimizing stuff

borkdude16:12:15

tufte… hmm, never used it before. @mfikes I see it’s crossplatform…

minikomi02:12:57

Ah, was looking for a walk/postwalk based answer 😄

grzm16:12:21

That was like slogging through mud. I posted it, only because I want to be able to look back in the future and say "Oh, my! I have improved!"

grzm16:12:44

I don't even want to look at the other solutions yet. I feel like I need to keep pounding on it.

grzm17:12:26

And speaking of datomic and databases, Vik Fearing has been solving them using postgres: https://github.com/xocolatl/advent-of-code-2017

Miķelis Vindavs18:12:38

I’m surprised.. for few (3) elements, maps seem faster than vectors

Miķelis Vindavs18:12:43

that is, mapping to

{:id     name
     :weight   (parse-int weight)
     :children (some-> top (str/split #", "))}))
and then indexing on :id is some 5-10% faster than doing the same with a 3-tuple and first

grzm18:12:17

Any different when using (get x 0)?

Miķelis Vindavs18:12:07

I’m using destructuring for both, didn’t try get or nth

borkdude18:12:40

@grzm how are you profiling?

grzm18:12:56

I'm not, for the most part.

grzm18:12:23

I'm trying to focus on habit at a time. And in this case it's been transducers and cljc. It's too easy for me to yak shave.

borkdude18:12:50

@grzm I’d be happy to throw it against criterium if you have the full snippet

grzm18:12:06

Is this in reference to my "mud" comment? Or perhaps you mean @mikelis.vindavs? The performance of mine was pretty good: 78ms iirc.

borkdude18:12:24

Ah sorry. I meant @mikelis.vindavs 🙂 about the 3-tuples

Miķelis Vindavs18:12:04

just (time (dotimes [_ 1000] (solve)))

borkdude18:12:44

That may not render realistic results

borkdude18:12:38

Try with criterium and then quick-bench

grzm18:12:44

And when I did a bit of refactoring, the mud cleaned up a bit. I don't like throwing to get a result, but that's what I ended up doing.

borkdude18:12:16

@grzm Me too. I don’t see that as a problem. Could easily refactor it, but I find it a creative way of solving the problem 🙂

grzm18:12:53

an application of creative destruction 😉 shows my bias with respect to throwing: I'm inclined to view it as something negative, rather than the tool it actually is.

Miķelis Vindavs18:12:54

I’ll try your suggestions , thanks

borkdude18:12:54

Detecting an error is fine with throw/catch and that was what the puzzle was about 😉

borkdude18:12:39

How do you know the common-weight is in the first spot there?

grzm18:12:10

I'm grouping by the tree weight, so the keys are the weights. Given the constraints of the problem, I know there's only going to be one that's an odd tree weight, so everything else is going to have the same tree weight. Then the sort-by transforms the map into a sequence of two vectors, odd-tree-weight first.

grzm18:12:38

It's kind of obscured by the destructuring, but that let only has a single binding in it.

borkdude18:12:10

ah, missed that, I thought it was the argument to the function… getting tired 😉

grzm18:12:37

Where are you at?

grzm19:12:04

I'm in the US midwest.

borkdude19:12:12

Europe, Netherlands

grzm19:12:38

I've been staying up and starting AoC at 11PM my time. Not the best to start working on a puzzle, especially ones like this one. Lots of little mistakes getting in the way of getting to the solution.

grzm19:12:04

Anyway, thanks for your evangelism wrt AoC! It's made it more enjoyable for me.

grzm18:12:12

Three levels deep. Once you're there it's revealing a pretty specific solution, but it's cool that destructuring works so robustly.

mfikes18:12:35

@mikelis.vindavs I was a little surprised as well when I changed my solution for yesterday to represent banks of memory as integer-indexed maps instead of vectors, and it ran slightly faster. I did not make this change for perf reasons, but so that the code would be correct when using (merge-with + ,,,) Here is the revision I'm talking about if curious : https://github.com/mfikes/advent-of-code/commit/9a178036eeb2c39b168712fed3388007217933ea

Miķelis Vindavs18:12:56

benchmarked with criterium, same thing — the difference is small, but still there

Miķelis Vindavs19:12:21

but what’s even more interesting that maps vs vectors is the fact that for the 1st part of the problem

Miķelis Vindavs19:12:30

a set difference approach is slower than an iterative pruning one

Miķelis Vindavs19:12:40

I can’t wrap my head around why that would be true. Is set/difference slow?

mfikes19:12:07

We may actually be seeing completely different effects, since mine is in ClojureScript. (I don't know JavaScript that well, but it seems like arrays are integer-indexed maps in a sense anyway, at least until the optimizer does something about them.)

mfikes19:12:45

I've never heard anyone suggesting that set/difference should be avoided for perf reasons.

Miķelis Vindavs19:12:25

the difference is pretty small, but in the other approach, I’m iteratively - removing nodes that have no children (`filter + into {}`) - removing references to those nodes (`map + filter + into {}`) until there’s only 1 entry left which seems like a ton more work than 2 map + set difference

Miķelis Vindavs19:12:23

is there a way to load a leiningen project in cljs? i have planck installed but am not very familiar with it

Miķelis Vindavs19:12:34

also I suppose io/resource isn’t implemented in cljs

mfikes19:12:54

@mikelis.vindavs You can run lein classpath to spit out a classpath, and Planck -c to take a classpath

mfikes19:12:41

Planck has a namespace that defines resource. I've been using it: https://github.com/mfikes/advent-of-code/blob/master/src/advent_2017/day_05.cljc#L7

mfikes19:12:34

To be honest lein classpath dumps out a lot of stuff you may not need, so I often manually specify the classpath, and there is -D sugar that Planck and Lumo have to expand to existing deps in your local Maven repo: http://planck-repl.org/dependencies.html

Miķelis Vindavs19:12:43

thanks, I’ll try that

mfikes19:12:21

Yeah, just take a peek at my repo https://github.com/mfikes/advent-of-code to see how I have it set up to run both Planck and Clojure with one source tree.

mfikes19:12:57

Wow. Hefty import list. Wonder if that is normal in PureScript.

mfikes19:12:28

Most of my Clojure solution namespaces are about the same size as that import list

borkdude19:12:37

_total = _Newtype <<< prop (SProxy :: SProxy "total")
 let childrensTotals = split.right ^.. traversed <<< _total
lenses…

mfikes19:12:30

I Like how Kris came to the same spot where the last bit of code wasn't necessary (you could do the last bit by hand faster than writing the code for it)

borkdude19:12:33

Yeah, but I want my part-2 function to always give the answer.. it’s part of my implicit contract

borkdude19:12:46

Maybe I have to write a protocol for it 😉

borkdude19:12:39

What’s a better way for this:

(defn find-by-val
  [m v]
  (ffirst
   (filter (fn [[k v’]]
             (= v v’))
           m)))

borkdude19:12:46

Could have used map-invert, but you’re never sure if the map has duplicate values

mfikes20:12:07

@borkdude If you want early termination and nil is not a concern, this seems to read nicely

(defn find-by-val
  [m v]
  (some (fn [[k v']]
          (when (= v v')
            k))
    m))

Miķelis Vindavs20:12:51

I’m using

(defn find-where [pred coll]
  (some #(when (pred %) %) coll))

mfikes20:12:53

Hmm. Maybe they both produce the same result, even with nil in the map as key or value

Miķelis Vindavs20:12:01

ahh but that’s sequences not maps

borkdude20:12:14

first + filter is also early termination, but yeah, some is also nice

Miķelis Vindavs20:12:56

it’s unfortunate this isn’t in core

borkdude20:12:33

I tried .indexOf but this time it didn’t work 😜

borkdude20:12:49

Nope, lein findfn "{:a 1}" 1 :a, nothing 😉

mfikes21:12:18

Ahh, right yeah ffirst / filter is indeed lazy

grzm21:12:37

@mfikes I was there, too (with you and Kris). I had a prn stuck in my recursive search function which printed out the unbalanced nodes. Did that by hand, then went back and finished the code.

grzm21:12:28

Makes me think there's something getting in the way of me using the machine to explore the problem space. Either practice, or tooling.

grzm21:12:41

Or technique (which is coupled with practice)

bhauman21:12:30

now to read the chat log and see whats up ...

borkdude21:12:44

(time (part-2 data)) 1864, is that milliseconds — or probably the solution 🙂

bhauman21:12:44

yeah the solution

bhauman21:12:06

@borkdude our data setup is spooky similar

mfikes21:12:27

@chrisblom Ahh, you got away with calling set/difference with a non-set smaller 2nd argument. For example this works (set/difference #{:a :b :c} [:a :b]) while this doesn't (set/difference #{:a :b :c} [:a :b :c :d :e])

chrisblom21:12:49

ow, thats nasty

chrisblom21:12:27

pretend you did not see that

mfikes21:12:34

Hah. I can't unsee it.

chrisblom21:12:17

i forgot how wonky clojure.set functions are for a moment

borkdude21:12:51

@bhauman indeed, great minds alike 😜

Miķelis Vindavs21:12:00

that’s a beautiful solution!

Miķelis Vindavs21:12:57

but does it assume that the weight will always need to be adjusted up?

Miķelis Vindavs06:12:02

still pretty nice & readable

chrisblom21:12:56

hmm, yeah, thought that was ok, but on second thought its probably not

chrisblom21:12:03

just got lucky with my input

Miķelis Vindavs21:12:04

I found that getting the “odd one out” was surprisingly complicated

borkdude21:12:09

Yeah. This is mine, but I’m sure there are other solutions:

(defn unbalanced-balanced
  [vals]
  (->> (frequencies vals)
       (group-by val)
       sort
       (map #(second %))
       (map #(ffirst %))))

mfikes21:12:28

I went with a construct like

((set/map-invert (frequencies [2 2 17 2])) 1)

borkdude21:12:44

I wanted both numbers in fixed order

mfikes22:12:34

Yeah, I needed both as well, went with (.indexOf [2 2 17 2] 17) for the second bit

grzm22:12:41

.indexOf is something I don't often reach for. I take it it's available in cljs?

borkdude22:12:49

Actually this works too:

(defn unbalanced-balanced
  [[a b c]]
  (if (= a b)
        [c a]
        [a b]))

borkdude22:12:53

much simpler 🙂

grzm22:12:03

That is nice

mfikes22:12:58

But what if you call it like (unbalanced-balanced [2 2 2 2 17 2])

mfikes22:12:22

I think we do know there are at least 3 items, because if there were 2 it would violate the constraint that "exactly one program is the wrong weight."

borkdude22:12:01

yeah, that was my thought too

mfikes22:12:06

Maybe something like the triplet comparison can yield an answer though.

mfikes22:12:27

Maybe a recursive version of that somehow?

borkdude22:12:34

Maybe partition and then moving over those

mfikes22:12:18

This might be correct

(let [[a b :as all] (sort [2 2 17 2])]
  (if (= a b)
    (last all)
    a))

mfikes22:12:32

^ Inspired by @borkdude’s comparison

borkdude22:12:28

Somewhat ugly but fast:

(defn unbalanced-balanced
  [[a b c & nums]]
  (let [[balanced maybe-unbalanced]
        (cond (= a b) [a c]
              (= a c) [a b]
              (= b c) [b a])]
    [(some #(when (not= balanced %) %)
           (cons maybe-unbalanced nums))
     balanced]))

borkdude22:12:00

In fact, in the third condition, we know for sure that a is the unbalanced one, but I didn’t want to write a special case for that

mfikes22:12:01

The computational complexity of this game https://www.youtube.com/watch?v=Sm-zWDaoCtI

borkdude22:12:33

Another version, more optimized:

(defn unbalanced-balanced
  [[a b c & nums]]
  (let [find-other (fn [v nums]
                     (some #(when (not= v %) %)
                           nums))]
    (cond (= a b) [a (find-other a (cons c nums))]
          (= a c) [a (find-other a (cons b nums))]
          (= b c) [b a])))

borkdude22:12:29

Something is wrong maybe, because I don’t get the right output

borkdude22:12:05

oh yes, wrong order of returned numbers, but apart from that it should work

borkdude22:12:03

anyway, in theory this should be faster, but in reality, I get 7 ms instead of 6 ms… this is BS 🙂

borkdude22:12:27

moving the function to its own defn works

borkdude22:12:58

Final call for “the odd one out”:

(defn unbalanced-balanced
  [[a b c & nums]]
  (cond (= a b) [(some
                  #(when (not= a %) %)
                  (conj nums c))
                 a]
        (= a c) [b a]
        :else   [a b]))