This page is not created by, affiliated with, or supported by Slack Technologies, Inc.

## 2019-10-11

## Channels

- # announcements (6)
- # architecture (9)
- # beginners (120)
- # calva (13)
- # cider (28)
- # clj-kondo (8)
- # cljs-dev (7)
- # clojure (113)
- # clojure-europe (13)
- # clojure-italy (7)
- # clojure-nl (9)
- # clojure-spec (44)
- # clojure-uk (7)
- # clojuredesign-podcast (15)
- # clojurescript (18)
- # cursive (9)
- # data-science (3)
- # datomic (32)
- # defnpodcast (1)
- # events (2)
- # fulcro (6)
- # jobs (1)
- # kaocha (5)
- # london-clojurians (2)
- # luminus (2)
- # nyc (2)
- # off-topic (54)
- # ring (6)
- # shadow-cljs (136)
- # sql (1)
- # testing (2)
- # tools-deps (64)
- # vim (83)

Yesterday I did a simple problem: you were given a grid in input, count the number of battleships in it. https://leetcode.com/problems/battleships-in-a-board/ The problem was on the additional challenge: > Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board? We had a debate over what one-pass means. For me it means accessing the value of each cell only once. For other people, looping through the grid once but for each cell potentially checking it's neighbors was single-pass.

I was fairly certain my definition was the good one, but as I can't find any solution that satisfies it... well, maybe I was wrong. It just seems that checking the neighbourgs for each cell makes the algorithm too simple for an "additional challenge".

I've bought a new iPhone and I'm struggling here to copy my Google Authenticator app codes to a new phone... seems like there's no way to copy the secrets to the new phone

It’s a bit too late now, but get yourself a password manager if you don’t already have one and store the authenticator seeds with the logins to the sites in question. Make damn sure that the password manager is secure.

yeah, I'm looking for an app like this, I generally use system keychain to store passwords

There's a bunch of other authenticator apps in the Apple App store, I have hard time choosing, does anyone have any recommendations? I would like to be able to have same codes in multiple devices, which seems to be a no-no with Google Authenticator app

Authy is an option

I'll try that, thanks

Hm authy doesn't seem to be able to move codes between devices without using their cloud backup service

Found an app that does what I want: 2FAS Auth

I've been very much enjoying my clojure journey which is mostly made up of happy distractions. Ironically my current distraction is charting my distractions. Maybe you'll find it amusing too: https://cdn.jsdelivr.net/gh/lread/lee-clojure-journey@5c3ef6986ef260050218361fb5cec800a91927fd/lee-clojure-journey.svg

hey thanks @UG1C3AD5Z, glad you like it!

It links to itself. Very meta-circular. Loved it 💯

a recent discovery for me: http://draw.io

I know right? I was an old OmniGraffle user and find http://draw.io to be a great free alternative!

Given http://draw.io, is Omnigraffle worth the money? I know it's a bit subjective but, wanna know your thoughts...

I think it's valuable to have an open source / free alternative as it's more open to contributors

That said, my paid copy of OmniGraffle is so out of date it does not work anymore. I’m not going to pay to update it unless I’m on a project that both prefers OmniGraffle and pays me. 🙂

Im a fan of http://plantuml.com/ I write my system descriptions in edn, then write a transformer to create the text to pipe into plant uml.

Ya that's cool! If you are an asciidoctor user, many of these textual descriptions can be embedded in your doc and rendered by asciidoctor diagram https://asciidoctor.org/docs/asciidoctor-diagram/

I started the book but didn't dive deep into it. Hard to run through after doing clojure I found.

I really love the fact that the guru in in the Unicorn Project is called Erik. This cannot be a coincidence.

@sova Pinging you in *#off-topic* channel in case you want to discuss P vs. NP issues here.

A well known computational problem long proven to be in P is: given a graph with nodes and edges, each edge having a positive length, is there a path from node A to node B with total cost M or less?

It is proved to be in set P by giving an algorithm (or for that problem, we have several good ones) that are guaranteed to terminate with the correct answer in run time that is polynomial in the size of the input.

A slightly different problem not known to be in set P, but known to be in NP, is: given a similar input, is there a path from node A to node B (with no nodes repeated) with total cost M or more?

The first is called the shortest path problem, the second the longest path problem. No one has published an algorithm for longest paths that is guaranteed to find the correct answer in polynomial time.

If you could find such an algorithm, that would be one way to prove that P=NP.

Would that really prove P=NP ?!

finding any one successful mapping of a known P problem to a known NP problem makes all P equal all NP ? o.o Please explain this "or more" part. bit fuzzy

The problem is the algorithm needs to work for all possible given inputs. If you test a graph for the longest path, and you test for a cost smaller than the minimal part, you could have the answer in P. The problem harder once the value gets higher, as you need to prove there is no possible path with a certain length, which seems only possible by trying out all the possible paths making it NP. It's probably or more and not exactly because then maybe you could use some heuristic using all the lenghts?

Traveling salesman is another famous NP problem, on a similar input, https://en.wikipedia.org/wiki/Travelling_salesman_problem

Finding a polynomial time algorithm for a so-called "NP-complete" problem would prove P=NP. "NP-complete" problems are effectively the hardest problems in NP to solve, because if you could find a polynomial time algorithm for any one of them, you can turn it into a polynomial time algorithm for all of the rest of them, too.

I think it's sufficient to claim that there exists such a transformation from NP to P for every single NP problem. The contra is: prove there are zero mappings from NP-complete problems to P, which (if could be done for one problem) would settle the matter that P is not NP?

TSP and other problems have been studied to death, I don't think P/NP will be resolved with a graph problem. Graphs are notoriously difficult to untangle, they are straight up bundles of string. Are there any other classes of NP problem you can tell me about? I wonder what the best approach vector would be to try and prove something like this, and I think choosing the right problem(s) is key

There are thousands of known NP-complete problems. https://en.wikipedia.org/wiki/Boolean_satisfiability_problem. https://en.wikipedia.org/wiki/Integer_programming. https://en.wikipedia.org/wiki/Shortest_common_supersequence_problem

One of my teachers used this book for a class in the 1980s for teaching the subject: https://en.wikipedia.org/wiki/Computers_and_Intractability

I still remember working though the proof I believe was from Turing machine to SAT. Don’t remember what it proves though.

The basic idea is that it proves you can take any problem instance of the form "simulate this Turing machine with this input, to see whether it answers yes or no to its input", and "encode" it as an instance of the SAT problem. If the answer to the first problem is yes, then the SAT problem will also have yes as the answer, and vice versa. Thus any function foo for solving SAT can be used to solve the Turing machine problem, solved by first doing the transformation in the proof, and then calling 'foo' on that, and you will get the correct answer to the original problem.

More basically, programmers frequently will take problem A that they do not have code to solve, and a library B that solves a different problem, and find a way to transform the data for problem A into a form that library B solves for them. The programmer must write code to transform problem A to problem B, and often also code to transform the solution for B back into a form that is the solution to the original problem.