Using Z3 to solve a simple logic puzzle

I was checking out Smullyan’s Lady of the Tiger. It starts with some very simple logic puzzles. Let’s make Z3 do one for us!

There are 100 politicians

at least one is honest

for any two at least one is crooked

How many honest politicians are there?

And here is one way of encoding this into z3:

Z3 is kind of a pain in that it won’t immediately cast to bools when I want them. A mistake I made at first was missing that “not i is j” in the list comprehension. Also an unfortunate feature is that this does not make it clear that there is a unique answer, due to permutations of the variables. But if we just asked for the number of honest, it’s not clear to me how to encode the forall2 constraint. Very curiously, z3 picks ‘x18’ to be the one honest man. I wonder why?

Propagators

When I first heard about Prolog, and that it’s “functions” are reversible (they are really more like relations) my first thought on how I would build such a thing was wrong. Let’s say you wanted plus(x,y,z). I thought maybe you’d write three functions, one for each of the possible outputs you’d like. so x+y -> z,  x-z -> y, and y-z->x. Then it’s not so hard to imagine something like wiring up the graph of connections between relations and figuring out an ordering of computation that gives you the query you want. You could make such a thing non-deterministic by returning a list of possible answers rather than a single answer if that is the case like square(x,y) (square root has plus and minus answer y-> [+sqrt(y),-sqrt(y)]).

Prolog actually uses a backtracking search mechanism though and doesn’t require you to write a function 3 times (although maybe under the hood primitive addition relations might have something like this for efficiency?) which makes the thing appear all the more magical at the programmer level.

But I think that first idea is somewhat related to something called a propagator.

 

Ed Kmett is a god. He is also horrendously opaque unless maybe you have some serious mathematical chops. The propagators are a unifying paradigm for some very disparate sounding things. The Introduction to Lattices book by Davey and Priestly he mentions is actually a fairly pleasant read. The reference about how orders are involved in programming languages that comes to mind is https://en.wikibooks.org/wiki/Haskell/Denotational_semantics. The laziness of Haskell makes a richer set of possibilities than just the result of a function is terminating or not. If you don’t look inside a data type, it may not matter that that piece involved a non-terminating computation. So it turns out you can define an ordering relation between data that have non-termination in different slots. the Haskell function fix, which is sort of a nasty (or useful) recursive higher order function is called so because it is related to taking the fixed point of a function from this order theory perspective.

It is very interesting that this analogy may allows you to apply the tricks of SAT solvers to speed up parallelism and stuff. As an example, I think the idea is that a function requires previous values that are it’s inputs to be computed before it can fire. So you have this mess of functions waiting to fire and every time a new answer gets completed, maybe you have to search through the mess for the next guy that is ready. But the two watched literal technique from SAT solvers is a nice way of doing this. It really reduces the number of functions from the blob you need to check by keeping tabs on only a much smaller set per intermediate result (you’d keep like a hash or list of all possible functions to check if ready to fire off after an intermediate result comes in). The two watched literal technique doesn’t keep ALL the possibly firing functions in the list. Per function, they only are put into two possibility lists. And when one of those intermediate results comes in, you pop the function out of that list and put it into one of the other lists of something else it needs that hasn’t come in yet. If you can’t find another list to put it in, it’s ready to fire off itself. Each function may end up getting inspected much less than the number of variables it has depending on the order intermediates come in rather than once per variable as you would in the naive approach.

http://composition.al/ This is the blog of Lindsey Kuper, who did that PhD work on LVars he mentions.

http://composition.al/blog/2013/09/22/some-example-mvar-ivar-and-lvar-programs-in-haskell/

The Bartosz Milewski himself talking about MVars (Last 2 videos in playlist)

MVars block on write if full and on read if empty. So they are useful for synchronization.

IVars can only be written to once and block on read until full. They are promises

CRDTs – https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type

Propagators are mentioned here

http://choco-solver.readthedocs.io/en/latest/2_modelling.html#constraints

https://github.com/ekmett/propagators

http://web.mit.edu/~axch/www/art.pdf

 

Caffe: Getting Started

To Use the Movidius neural network stick we have to use caffe.

http://caffe.berkeleyvision.org/install_osx.html

http://caffe.berkeleyvision.org/installation.html#compilation

Caffe is not super friendly or well documented in my opinion.

I’m having lots of installation problems on my mac.

Segmentation Fault 11

https://github.com/BVLC/caffe/issues/2677

Trying the last thing here. Be sure to change the version numbers in the path

I eventually got it to import with

PYTHON_INCLUDE := /usr/local/Cellar/python/2.7.13/Frameworks/Python.framework/Versions/2.7/include/python2.7 \
/usr/local/Cellar/python/2.7.13/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/numpy/core/include/

PYTHON_LIB := /usr/local/Cellar/python/2.7.13/Frameworks/Python.framework/Versions/2.7/lib

in MakeFile.config

I run the command with python2 which supposedly is the homebrew python.

python2 -m pip install protobuf scikit-image

 

Ok. Now we can start.

 

It is configuration file based. You make this protobuf file with the network and then load it up.

In standard configuration, you pull the data off of a database.

Data layers have the training data

top parameter is output of a layer

bottom is input

include Train Test are ways to include different guys at different stages

http://caffe.berkeleyvision.org/tutorial/loss.html

Any loss layer contributes to the eventual loss. You can weight them with a weighting parameter.  The solver runs to optimize loss layers by default. There is no parameter to specify which.

Some beginner files for syntax and exploration.

Sets input blobs in python (probably not the preferred methodology but it is fast to get up and running. Should probably at least dump into an hdf5)

Performs InnerProduct which is a matrix product and computes a euclidean loss.

Check out the mnist folder in caffe/examples. It has the clearest stuff.

 

 

 

 

 

This is the location of caffe.io

It has some routines for conversion to and from arrays and preprocessing in Transformer.

https://github.com/BVLC/caffe/blob/master/python/caffe/io.py

 

http://adilmoujahid.com/posts/2016/06/introduction-deep-learning-python-caffe/

 

http://christopher5106.github.io/deep/learning/2015/09/04/Deep-learning-tutorial-on-Caffe-Technology.html

 

View story at Medium.com

Deep Learning With Caffe In Python – Part I: Defining A Layer

https://github.com/BVLC/caffe/wiki

You can set certain layers to not train by setting learnign rate to 0

What a great talk! NP solvers in Clojure for puzzles

I was listening to this guy on this podcast Programming Throwdown and really liked the cut of his jib. So I sought out the talks he mentioned

Links to stuff mentioned

https://github.com/Engelberg/ycover

Rolling Stones – bindings to Java Sata solver Sat4j

https://github.com/Engelberg/rolling-stones

Tarantella – Dancing Links

https://github.com/Engelberg/tarantella

Loco – Choco   – CSP solver in java

 

SMT vs CSP?

https://cstheory.stackexchange.com/questions/29406/constraint-satisfaction-problem-csp-vs-satisfiability-modulo-theory-smt-wi

I guess the difference is the community as perspective. CSP tends to be from AI. SMT comes from formalizing and proving correctness of programs.

Simple GnuRadio Sonar Rangefinding

 

random_source-grc

A simple graph where you can see a peak move as you move the microphone closer and farther from the speaker.

Uses the FFT method to compute the cross-correlation between the source signal and the microphone signal.

The source signal is a random binary signal. The repetition of 2 helpful I think because of the window applied in the Fourier Transform elements. Since a binary signal at the sampling rate has a lot of high frequency components, I hypothesize that Even a very sharp low pass filter might hurt. Repetition ought to push the signal somewhere in the middle of the spectrum.

Suggestion:

Could use averaging to increase signal level.

 

The plan is to master the sonic case, where the electronics is much simpler, and then move into using my LimeSDR attached to IR diodes for a DIY Lidar unit. We’ll see where we get.

 

An interesting package that i should have investigated first

https://github.com/kit-cel/gr-radar

 

Elm, Eikonal, and Sol LeWitt

We saw this cool Sol LeWitt wall at MASS MoCA. It did not escape our attention that it was basically an eikonal equation and that the weird junctures were caustic lines.

It was drawn with alternating colored marker lines appearing a cm away from the previous line. This is basically Huygens principal.

So I hacked together a demo in elm. Elm is a Haskell-ish language for the web.

 

 

 

So I made a quick rip and run elm program to do this. This is the output, which I could make more dynamic.

The algorithm is to turn a list of points into their connecting lines. Then move the line perpendicular to itself, then recompute the new intersection points. It’s somewhat reminiscent of Verlet integration. Lines coordinates are momentum-like and points are position like and we alternate them. This is a finite difference version of the geometric Huygen’s principle.

Alternative methods which might work better include the Fast Marching Method or just using the wave equation and then plotting iso surfaces.

I also had to resample the function to get only the maximum y value for each x value in order to duplicate the LeWitt effect.

sol

These are the helper functions with lots of junk in there

And this is the svg main program.

 

 

notes on elm

elm is installed with npm

elm-repl

you import packages (including your own) with

import ThisPackage

and you check types by just writing them and hitting enter rather than :t

elm-live is a very handy thing. A live reloading server that watches for changes in your files.

elm-make myfile.elm

will generate the javascript and html

This is a good tutorial and a good snippet to get you going

 

Differences from Haskell:

elm isn’t lazy which is probably good.

The composition operator (.) is now <<

elm doesn’t have the multiline pattern match of haskell. You need  to use case expressions. I miss them.

typeclass facilities are not emphasized.

The list type is List a rather than [a]

 

A couple of interesting deep learning topics

https://hackernoon.com/up-to-speed-on-deep-learning-july-update-4513a5d61b78

Image Segmentation

How to find objects as subimages in an image:

https://blog.athelas.com/a-brief-history-of-cnns-in-image-segmentation-from-r-cnn-to-mask-r-cnn-34ea83205de4

Basically, use classifying networks on suggested subboxes. Then there are some tricks layered on top of that idea, like using a netowkr to suggest possible subboxes. There exist implementations of these things in tensorflow, caffe and others.

http://blog.qure.ai/notes/semantic-segmentation-deep-learning-review

One shot learning

https://hackernoon.com/one-shot-learning-with-siamese-networks-in-pytorch-8ddaab10340e

Differentiate whether two pictures are of the same object using only the one image.

One-Shot Imitation learning

https://arxiv.org/abs/1703.07326

Gstreamer

gstreamer is tinker toys for putting together media applications. Very reminiscent of gnuradio although it doesn’t have a nice gui editor. You smash together a bunch of blocks

It keeps coming up so I am looking into it more.

 

https://gstreamer.freedesktop.org/documentation/installing/on-linux.html

sudo apt install libgstreamer1.0-dev

copy example

https://gstreamer.freedesktop.org/documentation/tutorials/basic/hello-world.html#

gcc hello_gstream.c pkg-config --cflags --libs gstreamer-1.0

 

v4l2src is the webcam source of the /dev/video0 device

 

apt-get install gstreamer0.10-ffmpeg

gst-launch-1.0 -v \
v4l2src \
! qtdemux \
! h264parse \
! ffdec_h264 \
! ffmpegcolorspace \
! x264enc \
! rtph264pay \
! udpsink host=127.0.0.1 port=5000

helpful idiom

gst-inspect | grep “h264”

This let me view my webcam

gst-launch-1.0 -v v4l2src device=/dev/video0 ! video/x-raw,framerate=30/1,width=1280,height=720 ! xvimagesink

The video/x-raw is a “cap”, a capability, kind of defining the type of video flowing through. It isn’t a conversion step as I understand it. It is telling the graph which of the possible types of video available you’ve picked (your webcam can just be told to give you different stuff).

Ugh. The gstreamer elements are super useful, but where is an organized list of them. The manual just has a big dump. Most of these are probably not useful.

https://gstreamer.freedesktop.org/documentation/plugins.html

videoconvert sounds like a good one

There are some fun opencv and opengl ones. Like face detection or wacky effects. Handdetect is a curious one

fakesrc for testing

special sinks for os x –  osxvideosink

playbin for playing from a uri

x264enc – encodes into h264

uvch264 – gets a h264 stream right from the webcam

Using the Logitech C920 webcam with Gstreamer 1.2

Or you can just change the parameter to v4l2src to output h264. Ok this is not working on my webcam. I get

ERROR: from element /GstPipeline:pipeline0/GstV4l2Src:v4l2src0: Internal data flow error.

instead

gst-launch-1.0 -v v4l2src device=/dev/video0 ! video/x-raw,framerate=30/1,width=640,height=480 ! x264enc tune=zerolatency !  h264parse ! avdec_h264 ! xvimagesink

encodes h264 and then decodes it. May want to change that zerolatency to another setting option. Maybe?

https://gstreamer.freedesktop.org/data/doc/gstreamer/head/gst-plugins-ugly-plugins/html/gst-plugins-ugly-plugins-x264enc.html

 

okay continuing ahead with the streaming. I can’t get h264 to stream. It gives a ERROR: from element /GstPipeline:pipeline0/GstVideoTestSrc:videotestsrc0: Internal data flow error. when combined with the stock example code

GARBAGE. DO NOT USE.

 

https://gstreamer.freedesktop.org/data/doc/gstreamer/head/gst-plugins-good-plugins/html/gst-plugins-good-plugins-rtpbin.html

However. using h263 it does work. Needed to change ffenc to avenc from their example and ffdec to avdec

Sending

receiving

 

for receiving on my macbook

gst-launch-1.0 -v rtpbin name=rtpbin \

you need to specify a host for the udpsinks to get the video on another computer.

I would estimate the latency at 1/4 second maybe. Much better than other things I’ve tried.

okay default latency on rtpbin is 200ms.

on receiving side set latency=0 as an option to rtpbin (not totally sure if transmitting side should have it too.)

I wonder how bad that will fail in the event of packet loss? It’s probably not a good setting for some circumstances, but for a non-critical application on a LAN it seems pretty good.

I think the latency might have crept up a bit over a minute. Not too bad though.

 

https://github.com/GStreamer/gst-rtsp-server

 

Making a Podcast

I followed a couple tutorial websites

I’m using Zencastr for the moment. It is a browser based skype recording thing. Our first episode came out really out of sync between the two tracks

I’m using audacity to mix the two tracks together into a single file.

Hosting is on a blogspot. I think this was a bad choice. Should have used wordpress. Anyway, simple enough. Make a post per episode.

Using Feedburner to collect up the RSS feed from the blogspot and giving it more metadata. This service feels so crusty and ancient. I wonder if it still best practice

Domain names on Google Domains.

Google Drive with shared links was used for hosting. This works ok, but is not good enough for itunes. It is missing byte range requests and maybe nice urls with filenames in them? Google drive has some abilities that stopped in 2015 that would’ve been helpful. If you modify the usual shared link to look like

https://drive.google.com/uc?export=download&id=0ByV2UyFOHalnSHdkbTZnLVJUc2M

it works better, replacing that junk at the end with your junk

Using Amazon S3 for storage. I already had an AWS account and bucket, so no biggy. The cost should be cheap according to what I’m seeing? $0.04 /GB/month for storage and a couple of cents per 1000 requests supposedly. We’ll see. I’ve been burned and confused by AWS pricing before.

Submit podcast on https://podcastsconnect.apple.com/#/ for itunes

 

 

Nerve: Elixir OS packager for Raspberry Pi

I found out about Elxir Nerve on the Functional Geekery podcast. Seems right up my alley.

It builds a minimal linux image with erlang running. Runs on the raspberry pis and beaglebone.

Erlang and elixir does intrigue me a lot, but I haven’t gotten over the hump yet.

Summary of experience so far: Kind of painful. Docs aren’t great. Being an elixir newbie hurts. Strong suspicion that going outside the prebuilt stuff is gonna be tough.

https://hexdocs.pm/nerves/installation.html#linux

Installation

Getting Started

https://hexdocs.pm/nerves/getting-started.html#content

mix nerves.new hello_nerves

need to export the target variable. Why is this  not part of the config file. There probably is a reason.

export MIX_TARGET=rpi0

Building the firmware

mix firmware

writing to sd card

mix firmware.burn

says I need to install fwup

makes sense. Not in apt-get. Downloaded the deb file and installed

https://github.com/fhunleth/fwup

 

Booted up. Shows things on hdmi. Cool

went to

https://github.com/nerves-project/nerves_examples/tree/master/hello_wifi

run the following before building to set wifi stuff

mix deps.get

mix firmware

mix firmware.burn

 

Hmm. Can’t get it to work. i have Erlang 20 and It wants 19. Upon further inspection, this example is completely deprecated. Sigh.

 

Alright.

mix nerse.new wifi_test

https://github.com/nerves-project/nerves_examples/blob/master/hello_network/mix.exs

https://github.com/nerves-project/nerves_network

https://hexdocs.pm/nerves_network/Nerves.Network.html

add in the nerves_network dependency into mix.exs

added

at the end of the config file

 

Alright. I admit temporary defeat. The pi zero is an awful thing.

 

Hmmm!

If you plug the usb port of the pi zero into your computer it shows up as a serial device

in my case /dev/ttyACM0

you can open that up with screen or the arduino serial monitor

baud 115200

And you have access to an elixir console.

Interesting.

 

I was able to get linklocal ethernet connection working. You have to setup nerves_network usb0 to use method :linklocal.

I used nerves_init_gadget

https://github.com/fhunleth/nerves_init_gadget

In addition on unbutu you have you go into the netowrk settings and change the ipv4 dropdown in the options to linklocal only. Then the pi is available at nerves.local

 

The edimax wifi dongle does not work by default

https://www.grappendorf.net/tutorials/nerves-pizero-edimax.html

hmm buildroot https://buildroot.org/

This is intriguing. It is a build tool for getting linux on embedded systems