cg #92

entry #1

written by seshoumara
submitted at 2026-01-02T09:41:19.790237+00:00
0 likes

guesses

seshoumara (by Olek Sabak)
seshoumara (by Dolphy)
seshoumara (by oleander)

comments 0

post a comment

#!/usr/bin/sed -nrf

:_Problem
	# SAT solver
	# https://codeguessing.gay/92/
:_Restrictions
	# expr: ( expr ) | ( NOT expr ) | ( expr AND expr ) | ( expr OR expr ) | TRUE | FALSE | P | Q | R | S | T


:main
	1v;h;x
	s:.{111}:&\\\n:g #cg only
	p;z;x
	b identify_variables
	:continue_1_m
	b generate_all_variable_combinations
	:continue_2_m
	b evaluate_all
	:continue_3_m
b display_result

:identify_variables
	x;G
	s/\n.*\bP\b/P:&/
	s/\n.*\bQ\b/Q:&/
	s/\n.*\bR\b/R:&/
	s/\n.*\bS\b/S:&/
	s/\n.*\bT\b/T:&/
	/^\n.*$/{
		s::zero variables#;:
		b continue_1_m
	}
	s/:\n.*$/\n;P1Q1R1S1T1P:Q2P:R2P:S2P:T2Q:R2Q:S2Q:T2R:S2R:T2S:T2P:Q:R3P:Q:S3P:Q:T3P:R:S3P:R:T3P:S:T3/
	s/$/Q:R:S3Q:R:T3Q:S:T3R:S:T3P:Q:R:S4P:Q:R:T4P:Q:S:T4P:R:S:T4Q:R:S:T4P:Q:R:S:T5/
	s/1/=f#=t#;/g
	s/2/=f:f#=f:t#=t:f#=t:t#;/g
	s/3/=f:f:f#=f:f:t#=f:t:f#=f:t:t#=t:f:f#=t:f:t#=t:t:f#=t:t:t#;/g
	s/4/=f:f:f:f#=f:f:f:t#=f:f:t:f#=f:f:t:t#=f:t:f:f#=f:t:f:t#=f:t:t:f#=f:t:t:t#=t:f:f:f#=t:f:f:t#=t:f4/g
	s/4/:t:f#=t:f:t:t#=t:t:f:f#=t:t:f:t#=t:t:t:f#=t:t:t:t#;/g
	s/5/=f:f:f:f:f#=f:f:f:f:t#=f:f:f:t:f#=f:f:f:t:t#=f:f:t:f:f#=f:f:t:f:t#=f:f:t:t:f#=f:f:t:t:t#=f:t:f5/g
	s/5/:f:f#=f:t:f:f:t#=f:t:f:t:f#=f:t:f:t:t#=f:t:t:f:f#=f:t:t:f:t#=f:t:t:t:f#=f:t:t:t:t#=t:f:f:f:f#=5/g
	s/5/t:f:f:f:t#=t:f:f:t:f#=t:f:f:t:t#=t:f:t:f:f#=t:f:t:f:t#=t:f:t:t:f#=t:f:t:t:t#=t:t:f:f:f#=t:t:f:5/g
	s/5/f:t#=t:t:f:t:f#=t:t:f:t:t#=t:t:t:f:f#=t:t:t:f:t#=t:t:t:t:f#=t:t:t:t:t#;/g
	s/^([^\n]+)\n.*;\1(=[^;]+;).*$/\1\2/
b continue_1_m

:generate_all_variable_combinations
	x;G
	/^([^\n]+)\n(zero variables#);/{
		s::\2-\1;:
		b continue_2_m
	}
	s:#(.*)$:#-\1#:
	:copy_loop_gavc
		s:^(.*)\n.*#-:&\1:
		h;x
		s/^.*\n([^=]+).*=([^#]+)(#-[^=;]+).*$/>\1:=@\2:\3/
		:assignment_loop_gavc
			:loop_gavc
				s:>([PQRST])(.*@)([ft])(.*#-.*)\b\1\b:>\1\2\3\4\3:
			t loop_gavc
			s/>([PQRST]:)(.*)@([ft]:)/\1>\2\3@/
		/>=.*@#/! b assignment_loop_gavc
		s:.*-::
		x;G
		s:#-[^=;]+(.*)\n(.*)$:#-\2\1:
		s:-([^#]+)#:\1#-:
	/#-$/!b copy_loop_gavc
	s:^.*\n([^#]+#)(.*)#-$:\1-\2:
	s:f:FALSE:g
	s:t:TRUE:g
b continue_2_m

:evaluate_all
	/#-((FALSE)|(TRUE));$/b continue_3_m
	s:#-([^=;]+)([=;]):#-<EVAL>\1#return_eval_result_ea<LAVE>\2:
	b eval
	:return_eval_result_ea
		s:<EVAL>((FALSE)|(TRUE))##return_eval_result_ea<LAVE>:\1:
	s:#-((FALSE)|(TRUE))([^#]+)#:#\1\4#-:
b evaluate_all

:display_result
	s:-::
	/zero variables/{
		s:^(zero variables)#FALSE;$:>[contradiction] \1;:
		s:^(zero variables)(#TRUE;)$:>[tautology] \1\2:
		b print_cleanup_dr
	}
	s:^[^=]+(=[^#]+#TRUE)+;$:&none:
	s:=[^#]+#FALSE::g
	/^(.*;)none$/{
		s::>[tautology] \1:
		b print_cleanup_dr
	}
	/=/{
		s:^:>[satisfied] :
		b print_cleanup_dr
	}
	s:^(.*);$:>[contradiction] \1=;:
	:print_cleanup_dr
		s:#TRUE::g
		s:=: = :g
		s: ?;$::
		s:.{111}:&\\\n:g #cg only
	p;x;z;$!p;x
b EOS

:user_redirects
	/##return_eval_result_ea<LAVE>/ b return_eval_result_ea
b EOS

###################################   BOOLEAN LIB   ###################################

#1: <NOT>FALSE#label<TON> -> <NOT>TRUE##label<TON>
#1: <NOT>TRUE#label<TON> -> <NOT>FALSE##label<TON>
:not
	t not
	s:(<NOT>)TRUE#:\1FALSE##:; t redirect
	s:(<NOT>)FALSE#:\1TRUE##:
b redirect

#2: <AND>FALSE FALSE#label<DNA> -> <AND>FALSE##label<DNA>
#2: <AND>FALSE TRUE#label<DNA> -> <AND>FALSE##label<DNA>
#2: <AND>TRUE FALSE#label<DNA> -> <AND>FALSE##label<DNA>
#2: <AND>TRUE TRUE#label<DNA> -> <AND>TRUE##label<DNA>
:and
	t and
	s:(<AND>TRUE) TRUE#:\1##:; t redirect
	s:(<AND>)[^#]+#:\1FALSE##:
b redirect

#2: <OR>FALSE FALSE#label<RO> -> <OR>FALSE##label<RO>
#2: <OR>FALSE TRUE#label<RO> -> <OR>TRUE##label<RO>
#2: <OR>TRUE FALSE#label<RO> -> <OR>TRUE##label<RO>
#2: <OR>TRUE TRUE#label<RO> -> <OR>TRUE##label<RO>
:or
	t or
	s:(<OR>FALSE) FALSE#:\1##:; t redirect
	s:(<OR>)[^#]+#:\1TRUE##:
b redirect

#1: <EVAL>false_boolean_expression#label<LAVE> -> <EVAL>FALSE##label<LAVE>
#1: <EVAL>true_boolean_expression#label<LAVE> -> <EVAL>TRUE##label<LAVE>
:eval
	/<EVAL>((FALSE)|(TRUE))#/{
		s::&#:
		b redirect
	}
	s:(<EVAL>[^#]*)\( ((FALSE)|(TRUE)) \):\1\2:
	/(<EVAL>[^#]*)\( NOT ((FALSE)|(TRUE)) \)/{
		s::\1<NOT>\2#return_NOT_result_e<TON>:
		b not
		:return_NOT_result_e
			s:<NOT>((FALSE)|(TRUE))##return_NOT_result_e<TON>:\1:
	}
	/(<EVAL>[^#]*)\( ((FALSE)|(TRUE)) AND ((FALSE)|(TRUE)) \)/{
		s::\1<AND>\2 \5#return_AND_result_e<DNA>:
		b and
		:return_AND_result_e
			s:<AND>((FALSE)|(TRUE))##return_AND_result_e<DNA>:\1:
	}
	/(<EVAL>[^#]*)\( ((FALSE)|(TRUE)) OR ((FALSE)|(TRUE)) \)/{
		s::\1<OR>\2 \5#return_OR_result_e<RO>:
		b or
		:return_OR_result_e
			s:<OR>((FALSE)|(TRUE))##return_OR_result_e<RO>:\1:
	}
b eval

##################################   FUNCTION GLUE   ##################################

:redirect
	/##return_NOT_result_e<TON>/ b return_NOT_result_e
	/##return_AND_result_e<DNA>/ b return_AND_result_e
	/##return_OR_result_e<RO>/ b return_OR_result_e
b user_redirects

:EOS

output_examples ASCII text

( ( P OR Q ) AND ( NOT ( P AND Q ) ) )
>[satisfied] P:Q = FALSE:TRUE = TRUE:FALSE

( ( R OR S ) OR ( ( NOT R ) AND ( NOT S ) ) )
>[tautology] R:S = FALSE:FALSE = FALSE:TRUE = TRUE:FALSE = TRUE:TRUE

( NOT FALSE )
>[tautology] zero variables

( T AND ( NOT T ) )
>[contradiction] T =

( FALSE )
>[contradiction] zero variables

( ( ( ( ( ( Q OR S ) OR T ) AND ( ( ( NOT Q ) OR ( NOT S ) ) OR T ) ) AND ( ( ( NOT Q ) OR S ) OR ( NOT T ) ) )\
 AND ( ( Q OR ( NOT S ) ) OR ( NOT T ) ) ) )
>[satisfied] Q:S:T = FALSE:FALSE:TRUE = FALSE:TRUE:FALSE = TRUE:FALSE:FALSE = TRUE:TRUE:TRUE

( ( ( ( P AND Q ) OR ( ( NOT R ) AND S ) ) AND ( T OR TRUE ) ) AND ( NOT FALSE ) )
>[satisfied] P:Q:R:S:T = FALSE:FALSE:FALSE:TRUE:FALSE = FALSE:FALSE:FALSE:TRUE:TRUE = FALSE:TRUE:FALSE:TRUE:FAL\
SE = FALSE:TRUE:FALSE:TRUE:TRUE = TRUE:FALSE:FALSE:TRUE:FALSE = TRUE:FALSE:FALSE:TRUE:TRUE = TRUE:TRUE:FALSE:FA\
LSE:FALSE = TRUE:TRUE:FALSE:FALSE:TRUE = TRUE:TRUE:FALSE:TRUE:FALSE = TRUE:TRUE:FALSE:TRUE:TRUE = TRUE:TRUE:TRU\
E:FALSE:FALSE = TRUE:TRUE:TRUE:FALSE:TRUE = TRUE:TRUE:TRUE:TRUE:FALSE = TRUE:TRUE:TRUE:TRUE:TRUE

entry #2

written by oleander
submitted at 2026-01-04T17:26:16.783681+00:00
0 likes

guesses

Dolphy (by seshoumara)
oleander (by Olek Sabak)
oleander (by Dolphy)

comments 0

post a comment

index.js ASCII text

// input specifications
const variableNames = ["x", "y"];
const andName = "AND";
const orName = "OR";
const notName = "NOT";
const inputString = "(x OR y) AND NOT (x AND y)";

//execution
const logicString = inputString.replaceAll(andName, "&&").replaceAll(orName, "||").replaceAll(notName, "!");
function check(variableNames, assigned){
    if (assigned.length == variableNames.length){
      let tempString = logicString;
      for (let i = 0; i < assigned.length; i++) {
        tempString = tempString.replaceAll(variableNames[i], assigned[i]);
      }
      return [eval(tempString)];
    }
    else{
        return [...check(variableNames, [...assigned, true]), ...check(variableNames, [...assigned, false])];
    }
}
const solutions = check(variableNames, []);
const solutionsNumber = solutions.filter(i=>i==true).length.toString();
console.log(solutionsNumber + " solution" + (solutionsNumber!="1" ? "s" : ""));

entry #3

written by Dolphy
submitted at 2026-01-05T18:18:06.617660+00:00
0 likes

guesses

Dolphy (by Olek Sabak)
Dolphy (by oleander)
oleander (by seshoumara)

comments 0

post a comment

expression.go Unicode text, UTF-8 text

package main

import (
	// "fmt"
	"fmt"
	"strings"
)

type ExprType int

func getPadding(depth int) string {
	if depth == 0 {
		return ""
	}
	return strings.Repeat("│   ", depth-1) + "└── "
}

const (
	EXPR_NOT = iota
	EXPR_OR
	EXPR_AND
	EXPR_ORLIST
	EXPR_ANDLIST
	EXPR_PAREN
	EXPR_VAR
)

type Expression interface {
	temp_evaluate() bool
	print(depth int) string
	is_equal(rhs Expression) bool
	optimize_stage1() (Expression, bool)
	optimize_stage2() (Expression, bool)
	pre_compile(temp_counter int) ([]Operation, int)
}

// NOT EXPRESSION
type NotExpr struct {
	expr Expression
}

func (e *NotExpr) temp_evaluate() bool {
	return !e.expr.temp_evaluate()
}

func (e *NotExpr) print(depth int) string {
	return getPadding(depth) + "NOT\n" + e.expr.print(depth+1)
}

func (e *NotExpr) is_equal(rhs Expression) bool {
	rhs_not, ok := rhs.(*NotExpr)
	if !ok {
		return false
	}
	return e.expr.is_equal(rhs_not.expr)
}

func (e *NotExpr) optimize_stage1() (Expression, bool) {
	var has_change bool
	e.expr, has_change = e.expr.optimize_stage1()

	// NOT NOT X === X
	if inner_not, ok := e.expr.(*NotExpr); ok {
		return inner_not.expr, true
	}

	// NOT (X) === NOT X
	if inner_paren, ok := e.expr.(*ParenExpr); ok {
		return &NotExpr{
			expr: inner_paren.expr,
		}, true
	}

	return e, has_change
}

func (e *NotExpr) optimize_stage2() (Expression, bool) {
	var has_change bool
	e.expr, has_change = e.expr.optimize_stage2()

	// NOT (X OR Y) = (NOT X) AND (NOT Y)
	if inner_or, ok := e.expr.(*OrExpr); ok {
		return &AndExpr{
			lhs: &NotExpr{inner_or.lhs},
			rhs: &NotExpr{inner_or.rhs},
		}, true
	}

	// NOT (X AND Y) = (NOT X) OR (NOT Y)
	if inner_and, ok := e.expr.(*AndExpr); ok {
		return &OrExpr{
			lhs: &NotExpr{inner_and.lhs},
			rhs: &NotExpr{inner_and.rhs},
		}, true
	}

	// NOT ORLIST(X1, X2, ..., XN) = ANDLIST(NOT X1, NOT X2, ..., NOT XN)
	if inner_orlist, ok := e.expr.(*OrListExpr); ok {
		for i := range len(inner_orlist.exprs) {
			inner_orlist.exprs[i] = &NotExpr{
				expr: inner_orlist.exprs[i],
			}
		}
		return &AndListExpr{
			exprs: inner_orlist.exprs,
		}, true
	}

	// NOT ANDLIST(X1, X2, ..., XN) = ORLIST(NOT X1, NOT X2, ..., NOT XN)
	if inner_andlist, ok := e.expr.(*AndListExpr); ok {
		for i := range len(inner_andlist.exprs) {
			inner_andlist.exprs[i] = &NotExpr{
				expr: inner_andlist.exprs[i],
			}
		}
		return &OrListExpr{
			exprs: inner_andlist.exprs,
		}, true
	}

	return e, has_change
}

func (e *NotExpr) pre_compile(temp_counter int) ([]Operation, int) {	
	var ops []Operation
	ops, temp_counter = e.expr.pre_compile(temp_counter)
	ops = append(ops, Operation{
		result_var: "*" + fmt.Sprint(temp_counter),
		op_type: OP_NOT,
		operands: []string{ops[len(ops) - 1].result_var},
	})

	return ops, temp_counter + 1
}

// OR EXPRESSION
type OrExpr struct {
	lhs Expression
	rhs Expression
}

func (e *OrExpr) temp_evaluate() bool {
	return e.lhs.temp_evaluate() || e.rhs.temp_evaluate()
}

func (e *OrExpr) print(depth int) string {
	return getPadding(depth) + "OR\n" + e.lhs.print(depth+1) + "\n" + e.rhs.print(depth+1)
}

func (e *OrExpr) is_equal(rhs Expression) bool {
	rhs_or, ok := rhs.(*OrExpr)
	if !ok {
		return false
	}
	return e.lhs.is_equal(rhs_or.lhs) && e.rhs.is_equal(rhs_or.rhs)
}

func (e *OrExpr) optimize_stage1() (Expression, bool) {
	var has_change bool = false
	var c1 bool
	var c2 bool
	e.lhs, c1 = e.lhs.optimize_stage1()
	e.rhs, c2 = e.rhs.optimize_stage1()
	has_change = (c1 || c2)

	// X OR X === X
	if e.lhs.is_equal(e.rhs) {
		return e.lhs, true
	}

	// 0 OR X === X
	if lhs_var, ok := e.lhs.(*VarExpr); ok && lhs_var.name == "0" {
		return e.rhs, true
	}

	// X OR 0 === X
	if rhs_var, ok := e.rhs.(*VarExpr); ok && rhs_var.name == "0" {
		return e.lhs, true
	}

	// 1 OR X === 1
	if lhs_var, ok := e.lhs.(*VarExpr); ok && lhs_var.name == "1" {
		return e.lhs, true
	}

	// X OR 1 === 1
	if rhs_var, ok := e.rhs.(*VarExpr); ok && rhs_var.name == "1" {
		return e.rhs, true
	}

	// X OR NOT X === 1
	if rhs_not, ok := e.rhs.(*NotExpr); ok && e.lhs.is_equal(rhs_not.expr) {
		return &VarExpr{name: "1"}, true
	}

	// NOT X OR X === 1
	if lhs_not, ok := e.lhs.(*NotExpr); ok && e.rhs.is_equal(lhs_not.expr) {
		return &VarExpr{name: "1"}, true
	}

	return e, has_change
}

func (e *OrExpr) optimize_stage2() (Expression, bool) {
	var has_change bool
	var c1 bool
	var c2 bool
	e.lhs, c1 = e.lhs.optimize_stage2()
	e.rhs, c2 = e.rhs.optimize_stage2()
	has_change = (c1 || c2)

	lhs := e.lhs
	rhs := e.rhs

	// Ignore redundant parenthesis
	if lhs_paren, ok := lhs.(*ParenExpr); ok {
		lhs = lhs_paren.expr
	}
	if rhs_paren, ok := rhs.(*ParenExpr); ok {
		rhs = rhs_paren.expr
	}

	//      OR
	//     /  \
	//    OR   Z
	//   /  \
	//  X    Y
	// Is equivalent to ORLIST(X, Y, Z)
	if lhs_or, ok := lhs.(*OrExpr); ok {
		return &OrListExpr{
			exprs: []Expression{lhs_or.lhs, lhs_or.rhs, rhs},
		}, true
	}
	//      OR
	//     /  \
	//    X   OR
	//       /  \
	//      Y    Z
	// Is equivalent to ORLIST(X, Y, Z)
	if rhs_or, ok := rhs.(*OrExpr); ok {
		return &OrListExpr{
			exprs: []Expression{lhs, rhs_or.lhs, rhs_or.rhs},
		}, true
	}

	//      OR
	//     /  \
	// ORLIST  Z
	// Is equivalent to adding one more element to the orlist
	if lhs_orlist, ok := lhs.(*OrListExpr); ok {
		lhs_orlist.exprs = append(lhs_orlist.exprs, rhs)
		return lhs_orlist, true
	}
	//      OR
	//     /  \
	//    X ORLIST
	//       /  \
	//      Y    Z
	// Is equivalent to adding one more element to the orlist
	if rhs_orlist, ok := rhs.(*OrListExpr); ok {
		rhs_orlist.exprs = append(rhs_orlist.exprs, lhs)
		return rhs_orlist, true
	}

	return e, has_change
}

func (e *OrExpr) pre_compile(temp_counter int) ([]Operation, int) {	
	var ops_left []Operation
	var ops_right []Operation
	ops_left, temp_counter = e.lhs.pre_compile(temp_counter)
	ops_right, temp_counter = e.rhs.pre_compile(temp_counter)
	left_operand := ops_left[len(ops_left) - 1].result_var
	right_operand := ops_right[len(ops_right) - 1].result_var

	ops_left = append(ops_left, ops_right...)
	ops_left = append(ops_left, Operation{
		result_var: "*"+fmt.Sprint(temp_counter),
		op_type: OP_OR,
		operands: []string{left_operand, right_operand},
	})

	return ops_left, temp_counter + 1
}

// AND EXPRESSION
type AndExpr struct {
	lhs Expression
	rhs Expression
}

func (e *AndExpr) temp_evaluate() bool {
	return e.lhs.temp_evaluate() && e.rhs.temp_evaluate()
}

func (e *AndExpr) print(depth int) string {
	return getPadding(depth) + "AND\n" + e.lhs.print(depth+1) + "\n" + e.rhs.print(depth+1)
}

func (e *AndExpr) is_equal(rhs Expression) bool {
	rhs_and, ok := rhs.(*AndExpr)
	if !ok {
		return false
	}
	return e.lhs.is_equal(rhs_and.lhs) && e.rhs.is_equal(rhs_and.rhs)
}

func (e *AndExpr) optimize_stage1() (Expression, bool) {
	var has_change bool = false
	var c1 bool
	var c2 bool
	e.lhs, c1 = e.lhs.optimize_stage1()
	e.rhs, c2 = e.rhs.optimize_stage1()
	has_change = (c1 || c2)

	// X AND X === X
	if e.lhs.is_equal(e.rhs) {
		return e.lhs, true
	}

	// 0 AND X === 0
	if lhs_var, ok := e.lhs.(*VarExpr); ok && lhs_var.name == "0" {
		return e.lhs, true
	}

	// X AND 0 === 0
	if rhs_var, ok := e.rhs.(*VarExpr); ok && rhs_var.name == "0" {
		return e.rhs, true
	}

	// 1 AND X === X
	if lhs_var, ok := e.lhs.(*VarExpr); ok && lhs_var.name == "1" {
		return e.rhs, true
	}

	// X AND 1 === X
	if rhs_var, ok := e.rhs.(*VarExpr); ok && rhs_var.name == "1" {
		return e.lhs, true
	}

	// X AND NOT X === 0
	if rhs_not, ok := e.rhs.(*NotExpr); ok && e.lhs.is_equal(rhs_not.expr) {
		return &VarExpr{name: "0"}, true
	}

	// NOT X AND X === 0
	if lhs_not, ok := e.lhs.(*NotExpr); ok && e.rhs.is_equal(lhs_not.expr) {
		return &VarExpr{name: "0"}, true
	}
	return e, has_change
}

func (e *AndExpr) optimize_stage2() (Expression, bool) {
	var has_change bool
	var c1 bool
	var c2 bool
	e.lhs, c1 = e.lhs.optimize_stage2()
	e.rhs, c2 = e.rhs.optimize_stage2()
	has_change = (c1 || c2)

	lhs := e.lhs
	rhs := e.rhs

	// Ignore redundant parenthesis
	if lhs_paren, ok := lhs.(*ParenExpr); ok {
		lhs = lhs_paren.expr
	}
	if rhs_paren, ok := rhs.(*ParenExpr); ok {
		rhs = rhs_paren.expr
	}

	//      AND
	//     /  \
	//   AND   Z
	//   /  \
	//  X    Y
	// Is equivalent to ANDLIST(X, Y, Z)
	if lhs_and, ok := lhs.(*AndExpr); ok {
		return &AndListExpr{
			exprs: []Expression{lhs_and.lhs, lhs_and.rhs, rhs},
		}, true
	}
	//     AND
	//     /  \
	//    X  AND
	//       /  \
	//      Y    Z
	// Is equivalent to ORLIST(X, Y, Z)
	if rhs_and, ok := rhs.(*AndExpr); ok {
		return &AndListExpr{
			exprs: []Expression{lhs, rhs_and.lhs, rhs_and.rhs},
		}, true
	}

	//     AND
	//     /  \
	// ANDLIST Z
	// Is equivalent to adding one more element to the orlist
	if lhs_andlist, ok := lhs.(*AndListExpr); ok {
		lhs_andlist.exprs = append(lhs_andlist.exprs, rhs)
		return lhs_andlist, true
	}
	//     AND
	//     /  \
	//    X ANDLIST
	//       /  \
	//      Y    Z
	// Is equivalent to adding one more element to the orlist
	if rhs_andlist, ok := rhs.(*AndListExpr); ok {
		rhs_andlist.exprs = append(rhs_andlist.exprs, lhs)
		return rhs_andlist, true
	}

	return e, has_change
}

func (e *AndExpr) pre_compile(temp_counter int) ([]Operation, int) {	
	var ops_left []Operation
	var ops_right []Operation
	ops_left, temp_counter = e.lhs.pre_compile(temp_counter)
	ops_right, temp_counter = e.rhs.pre_compile(temp_counter)
	left_operand := ops_left[len(ops_left) - 1].result_var
	right_operand := ops_right[len(ops_right) - 1].result_var

	ops_left = append(ops_left, ops_right...)
	ops_left = append(ops_left, Operation{
		result_var: "*" + fmt.Sprint(temp_counter),
		op_type: OP_AND,
		operands: []string{left_operand, right_operand},
	})

	return ops_left, temp_counter + 1
}

// OR LIST EXPRESSION
type OrListExpr struct {
	exprs []Expression
}

func (e *OrListExpr) temp_evaluate() bool {
	for _, ee := range e.exprs {
		if ee.temp_evaluate() {
			return true
		}
	}
	return false
}

func (e *OrListExpr) print(depth int) string {
	var out strings.Builder
	out.WriteString(getPadding(depth) + "ORLIST\n")
	for idx, item := range e.exprs {
		out.WriteString(item.print(depth + 1))
		if idx != len(e.exprs)-1 {
			out.WriteString("\n")
		}
	}
	return out.String()
}

func (e *OrListExpr) is_equal(rhs Expression) bool {
	rhs_orlist, ok := rhs.(*OrListExpr)
	if !ok {
		return false
	}
	if len(rhs_orlist.exprs) != len(e.exprs) {
		return false
	}

	for i := range len(e.exprs) {
		if !e.exprs[i].is_equal(rhs_orlist.exprs[i]) {
			return false
		}
	}
	return true
}

func (e *OrListExpr) optimize_stage1() (Expression, bool) {
	has_change := false
	if len(e.exprs) == 1 {
		return e.exprs[0].optimize_stage1()
	}

	for i := range len(e.exprs) {
		c := false
		e.exprs[i], c = e.exprs[i].optimize_stage1()
		has_change = has_change || c
	}

	for i := range len(e.exprs) {
		current := e.exprs[i]

		// If an ORLIST contains 1 it should evaluate to true
		if current_var, ok := current.(*VarExpr); ok && current_var.name == "1" {
			return current_var, true
		}

		// If an ORLIST contains 0 it should be removed
		if current_var, ok := current.(*VarExpr); ok && current_var.name == "0" {
			e.exprs = remove_at_index(e.exprs, i)
			return e, true
		}

		for j := i + 1; j < len(e.exprs); j++ {
			other := e.exprs[j]
			// X OR X === X
			if current.is_equal(other) {
				e.exprs = remove_at_index(e.exprs, j)
				return e, true
			}

			// X OR NOT X === 1
			if other_not, ok := other.(*NotExpr); ok && other_not.expr.is_equal(current) {
				return &VarExpr{name: "1"}, true
			}

			// NOT X OR X === 1
			if current_not, ok := current.(*NotExpr); ok && current_not.expr.is_equal(other) {
				return &VarExpr{name: "1"}, true
			}
		}
	}

	return e, has_change
}

func (e *OrListExpr) optimize_stage2() (Expression, bool) {
	has_change := false

	for i := range len(e.exprs) {
		c := false
		e.exprs[i], c = e.exprs[i].optimize_stage2()
		has_change = has_change || c
	}

	for i := range len(e.exprs) {
		current := e.exprs[i]
		if current_paren, ok := current.(*ParenExpr); ok {
			current = current_paren.expr
		}

		// Nested OR in ORLIST
		if current_or, ok := current.(*OrExpr); ok {
			e.exprs = remove_at_index(e.exprs, i)
			e.exprs = append(e.exprs, current_or.lhs)
			e.exprs = append(e.exprs, current_or.rhs)
			return e, true
		}
		// Nested ORLIST in ORLIST
		if current_orlist, ok := current.(*OrListExpr); ok {
			e.exprs = remove_at_index(e.exprs, i)
			e.exprs = append(e.exprs, current_orlist.exprs...)
			return e, true
		}
	}

	return e, has_change
}

func (e *OrListExpr) pre_compile(temp_counter int) ([]Operation, int) {	
	var ops []Operation
	var operands []string

	for _, e := range e.exprs {
		var expr_ops []Operation
		expr_ops, temp_counter = e.pre_compile(temp_counter)
		ops = append(ops, expr_ops...)
		operands = append(operands, expr_ops[len(expr_ops) - 1].result_var)
	}

	ops = append(ops, Operation{
		result_var: "*" + fmt.Sprint(temp_counter),
		op_type: OP_OR,
		operands: operands,
	})

	return ops, temp_counter + 1
}

// AND LIST EXPORESSION
type AndListExpr struct {
	exprs []Expression
}

func (e *AndListExpr) temp_evaluate() bool {
	for _, ee := range e.exprs {
		if !ee.temp_evaluate() {
			return false
		}
	}
	return true
}

func (e *AndListExpr) print(depth int) string {
	var out strings.Builder
	out.WriteString(getPadding(depth) + "ANDLIST\n")
	for idx, item := range e.exprs {
		out.WriteString(item.print(depth + 1))
		if idx != len(e.exprs)-1 {
			out.WriteString("\n")
		}
	}
	return out.String()
}

func (e *AndListExpr) is_equal(rhs Expression) bool {
	rhs_andlist, ok := rhs.(*AndListExpr)
	if !ok {
		return false
	}
	if len(rhs_andlist.exprs) != len(e.exprs) {
		return false
	}

	for i := range len(e.exprs) {
		if !e.exprs[i].is_equal(rhs_andlist.exprs[i]) {
			return false
		}
	}
	return true
}

func (e *AndListExpr) optimize_stage1() (Expression, bool) {
	if len(e.exprs) == 1 {
		return e.exprs[0].optimize_stage1()
	}
	has_change := false
	for i := range len(e.exprs) {
		c := false
		e.exprs[i], c = e.exprs[i].optimize_stage1()
		has_change = has_change || c
	}

	for i := range len(e.exprs) {
		current := e.exprs[i]

		// If an ANDLIST contains 0 it should evaluate to false
		if current_var, ok := current.(*VarExpr); ok && current_var.name == "0" {
			return current_var, true
		}

		// If an ANDLIST contains 1 it should be removed
		if current_var, ok := current.(*VarExpr); ok && current_var.name == "1" {
			e.exprs = remove_at_index(e.exprs, i)
			return e, true
		}

		for j := i + 1; j < len(e.exprs); j++ {
			other := e.exprs[j]
			// X AND X === X
			if current.is_equal(e.exprs[j]) {
				e.exprs = remove_at_index(e.exprs, j)
				return e, true
			}

			// X AND NOT X === 0
			if other_not, ok := other.(*NotExpr); ok && other_not.expr.is_equal(current) {
				return &VarExpr{name: "0"}, true
			}

			// NOT X AND X === 0
			if current_not, ok := current.(*NotExpr); ok && current_not.expr.is_equal(other) {
				return &VarExpr{name: "0"}, true
			}
		}
	}

	return e, has_change
}

func (e *AndListExpr) optimize_stage2() (Expression, bool) {
	has_change := false
	for i := range len(e.exprs) {
		c := false
		e.exprs[i], c = e.exprs[i].optimize_stage2()
		has_change = has_change || c
	}

	for i := range len(e.exprs) {
		current := e.exprs[i]
		if current_paren, ok := current.(*ParenExpr); ok {
			current = current_paren.expr
		}

		// Nested AND in ANDLIST
		if current_and, ok := current.(*AndExpr); ok {
			e.exprs = remove_at_index(e.exprs, i)
			e.exprs = append(e.exprs, current_and.lhs)
			e.exprs = append(e.exprs, current_and.rhs)
			return e, true
		}
		// Nested ANDLIST in ANDLIST
		if current_andlist, ok := current.(*AndListExpr); ok {
			e.exprs = remove_at_index(e.exprs, i)
			e.exprs = append(e.exprs, current_andlist.exprs...)
			return e, true
		}
	}

	return e, has_change
}

func (e *AndListExpr) pre_compile(temp_counter int) ([]Operation, int) {	
	var ops []Operation
	var operands []string

	for _, e := range e.exprs {
		var expr_ops []Operation
		expr_ops, temp_counter = e.pre_compile(temp_counter)
		ops = append(ops, expr_ops...)
		operands = append(operands, expr_ops[len(expr_ops) - 1].result_var)
	}

	ops = append(ops, Operation{
		result_var: "*" + fmt.Sprint(temp_counter),
		op_type: OP_AND,
		operands: operands,
	})

	return ops, temp_counter + 1
}

// PAREN EXPRESSION
type ParenExpr struct {
	expr Expression
}

func (e *ParenExpr) temp_evaluate() bool {
	return e.expr.temp_evaluate()
}

func (e *ParenExpr) print(depth int) string {
	return getPadding(depth) + "PAREN\n" + e.expr.print(depth+1)
}

func (e *ParenExpr) is_equal(rhs Expression) bool {
	rhs_paren, ok := rhs.(*ParenExpr)
	if !ok {
		return false
	}
	return e.expr.is_equal(rhs_paren.expr)
}

func (e *ParenExpr) optimize_stage1() (Expression, bool) {
	var has_change bool
	e.expr, has_change = e.expr.optimize_stage1()

	// (VAR) === VAR
	if inner_var, ok := e.expr.(*VarExpr); ok {
		return inner_var, true
	}

	// (NOT) === NOT
	if inner_not, ok := e.expr.(*NotExpr); ok {
		return inner_not, true
	}

	// ((X)) === (X)
	if inner_paren, ok := e.expr.(*ParenExpr); ok {
		return inner_paren, true
	}

	return e, has_change
}

func (e *ParenExpr) optimize_stage2() (Expression, bool) {
	var has_change bool
	e.expr, has_change = e.expr.optimize_stage2()

	return e, has_change
}

func (e *ParenExpr) pre_compile(temp_counter int) ([]Operation, int) {
	return e.expr.pre_compile(temp_counter)
}

// VAR EXPRESSION
type VarExpr struct {
	name string
}

func (e *VarExpr) temp_evaluate() bool {
	return temp_env[e.name]
}

func (e *VarExpr) print(depth int) string {
	return getPadding(depth) + "VAR(" + e.name + ")"
}

func (e *VarExpr) is_equal(rhs Expression) bool {
	rhs_var, ok := rhs.(*VarExpr)
	if !ok {
		return false
	}

	return e.name == rhs_var.name
}

func (e *VarExpr) optimize_stage1() (Expression, bool) {
	return e, false
}

func (e *VarExpr) optimize_stage2() (Expression, bool) {
	return e, false
}

func (e *VarExpr) pre_compile(temp_counter int) ([]Operation, int) {
	return []Operation{
		Operation{
			result_var: e.name,
			op_type: OP_NOP,
			operands: []string{},
		},
	}, temp_counter
}

main.go ASCII text

package main

import (
	"bufio"
	"fmt"
	"os"
);

func main() {
	reader := bufio.NewReader(os.Stdin)
    fmt.Print("> ")
    input, err := reader.ReadString('\n')
    if err != nil {
        fmt.Println("Error reading input:", err)
        return
    }

	// TOKENIZE & PARSE
	tokenizer := Tokenizer{
		str: input,
		current_pos: 0,
	}
	tokens := tokenizer.tokenize()
	p := Parser{
		tokens: tokens,
		current_pos: 0,
	}
	expr_tree := p.parse()

	// OPTIMIZE
	has_change := true
	for has_change {
		expr_tree, has_change = expr_tree.optimize_stage1()
		if has_change {
			continue
		}
		expr_tree, has_change = expr_tree.optimize_stage2()
	}

	// COMPILE
	pre_compiled, _ := expr_tree.pre_compile(0)
	compiled, environment := compile_and_build_environment(pre_compiled)

	// SAT SOLVE
	true_env, sat := sat_solve(compiled, environment)
	if sat {
		fmt.Println("Given expression is satisfiable with these values:")
		for var_name := range true_env.env {
			if var_name[0] != '*' {
				fmt.Printf("%v = %v\n", var_name, true_env.get(var_name))
			}
		}
	} else {
		fmt.Println("Given expression is unsatisfiable.")
	}
}

operation.go ASCII text

package main

type OperationType int

const (
	OP_NOP = iota
	OP_NOT
	OP_AND
	OP_OR
	OP_RET
)

type Operation struct {
	result_var string
	op_type OperationType
	operands []string
}

type Environment struct {
	env map[string]bool
}

func (environment *Environment) get(name string) bool {
	switch name {
	case "1":
		return true
	case "0":
		return false
	}
	return environment.env[name]
}

func (environment *Environment) set(name string, value bool) {
	if name == "1" || name  == "0" {
		return
	}
	environment.env[name] = value
} 

func compile_and_build_environment(pre_compiled []Operation) ([]Operation, Environment) {
	var compiled []Operation
	var env Environment = Environment{
		env: make(map[string]bool),
	}

	var final_var string
	for _, e := range pre_compiled {
		if e.op_type != OP_NOP {
			 compiled = append(compiled, e)
		} else {
			env.set(e.result_var, false)
		}
		final_var = e.result_var
	}
	compiled = append(compiled, Operation{
		result_var: final_var,
		op_type: OP_RET,
		operands: []string{},
	})
	return compiled, env
}

func execute(ops []Operation, env Environment) bool {
	if len(ops) == 0 {
		panic("Nothing to execute!")
	}

	for _, op := range ops {
		switch op.op_type {
		case OP_NOT:
			env.set(op.result_var, !env.get(op.operands[0]))
		case OP_OR:
			initial := false
			for _, elem := range op.operands {
				initial = (initial || env.get(elem))
			}
			env.set(op.result_var, initial)
		case OP_AND:
			initial := true
			for _, elem := range op.operands {
				initial = (initial && env.get(elem))
			}
			env.set(op.result_var, initial)
		case OP_RET:
			return env.get(op.result_var)
		case OP_NOP:
			panic("Compile your code first!")
		}
	}

	panic("Unreachable")
}

func sat_solve(code []Operation, env Environment) (Environment, bool) {
	keys := make([]string, 0, len(env.env))
    for k := range env.env {
        keys = append(keys, k)
    }

	for i := 0; i < (1 << len(keys)); i++ {
		env_copy := Environment{env: make(map[string]bool)}
		for j, name := range keys {
			env_copy.set(name, (i>>j)&1 == 1)
		}

		if execute(code, env_copy) {
			return env_copy, true
		}
	}
	return env, false
}

parser.go ASCII text

package main

import "fmt"

var temp_env map[string]bool = map[string]bool{"1": true, "0": false};


type Parser struct {
	tokens []Token
	current_pos int
}

// PARSE
func (p *Parser) expect(t TokenType) {
	tt := p.tokens[p.current_pos].token_type
	if tt == t {
		p.current_pos++
		return
	}
	panic(fmt.Errorf("Expected token type \"%v\". Got \"%v\"!", t, tt))
}

func (p *Parser) is_finished() bool {
	return p.current_pos >= len(p.tokens) || p.tokens[p.current_pos].token_type == TOK_EOF
}

func (p *Parser) parse() Expression {
	return p.parse_expr()
}

func (p *Parser) parse_expr() Expression {
	return p.parse_conj()
}

func (p *Parser) parse_conj() Expression {
	e1 := p.parse_disj()
	if p.is_finished() {
		return e1
	}

	if p.tokens[p.current_pos].token_type == TOK_OR {
		p.current_pos++
		e2 := p.parse_expr()
		return &OrExpr {
			lhs: e1,
			rhs: e2,
		}
	}
	return e1
}

func (p *Parser) parse_disj() Expression {
	e1 := p.parse_other()
	if p.is_finished() {
		return e1
	}

	if p.tokens[p.current_pos].token_type == TOK_AND {
		p.current_pos++
		e2 := p.parse_expr()
		return &AndExpr {
			lhs: e1,
			rhs: e2,
		}
	}
	return e1
}

func (p *Parser) parse_other() Expression {
	t := p.tokens[p.current_pos]
	switch t.token_type {
	case TOK_NOT:
		p.current_pos++
		return &NotExpr{
			expr: p.parse_expr(),
		}
	case TOK_LPAREN:
		p.current_pos++
		expr := p.parse_expr()
		p.expect(TOK_RPAREN)
		return &ParenExpr{
			expr: expr,
		}
	case TOK_VARIABLE, TOK_TRUE, TOK_FALSE:
		p.current_pos++
		temp_env[t.lexime] = (t.token_type == TOK_TRUE)
		return &VarExpr{
			name: t.lexime,
		}
	default:
		panic(fmt.Errorf("Unexpected token type \"%v\"!", t.token_type))
	}
}

tokenizer.go ASCII text

package main

import "fmt"

type TokenType int

const (
	TOK_NOT TokenType = iota
	TOK_OR
	TOK_AND
	TOK_TRUE
	TOK_FALSE
	TOK_LPAREN
	TOK_RPAREN
	TOK_VARIABLE
	TOK_EOF
)

type Token struct {
	token_type TokenType
	lexime     string
	position   int
}

type Tokenizer struct {
	str         string
	current_pos int
}

func is_valid_first_char(c byte) bool {
	return ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z') || c == '_'
}

func is_valid_char(c byte) bool {
	return is_valid_first_char(c) || ('0' <= c && c <= '9')
}

func is_whitespace(c byte) bool {
	return c == ' ' || c == '\t' || c == '\n'
}

func (t *Tokenizer) check(s string) (bool, string, error) {
	if t.current_pos+len(s) > len(t.str) {
		return false, "a", fmt.Errorf("Expected token \"%v\" is too long!", s)
	}
	substr := t.str[t.current_pos : t.current_pos+len(s)]
	return substr == s, substr, nil
}

func (t *Tokenizer) consume(l int) {
	t.current_pos += l
}

func (t *Tokenizer) expect(s string) error {
	got, substr, err := t.check(s)
	if err != nil {
		return err
	}
	if !got {
		return fmt.Errorf("Expected string \"%v\". Got \"%v\"!", s, substr)
	}
	t.consume(len(s))
	return nil
}

func (t *Tokenizer) tokenize() []Token {
	tokens := make([]Token, 0)

	for t.current_pos < len(t.str) {
		c := t.str[t.current_pos]
		if c == ' ' || c == '\t' || c == '\n' {
			t.current_pos++
		} else if got, _, _ := t.check("NOT"); got {
			t.expect("NOT")
			tokens = append(tokens, Token{
				token_type: TOK_NOT,
				lexime:     "NOT",
			})
		} else if got, _, _ := t.check("OR"); got {
			t.expect("OR")
			tokens = append(tokens, Token{
				token_type: TOK_OR,
				lexime:     "OR",
			})
		} else if got, _, _ := t.check("AND"); got {
			t.expect("AND")
			tokens = append(tokens, Token{
				token_type: TOK_AND,
				lexime:     "AND",
			})
		} else if c == '1' {
			tokens = append(tokens, Token{
				token_type: TOK_TRUE,
				lexime:     "1",
			})
			t.consume(1)
		} else if c == '0' {
			tokens = append(tokens, Token{
				token_type: TOK_FALSE,
				lexime:     "0",
			})
			t.consume(1)
		} else if c == '(' {
			t.current_pos++
			tokens = append(tokens, Token{
				token_type: TOK_LPAREN,
				lexime:     "(",
			})
		} else if c == ')' {
			t.current_pos++
			tokens = append(tokens, Token{
				token_type: TOK_RPAREN,
				lexime:     ")",
			})
		} else {
			if is_valid_first_char(c) {
				start_pos := t.current_pos
				t.current_pos++
				for t.current_pos < len(t.str) {
					cc := t.str[t.current_pos]
					if !is_valid_char(cc) {
						break
					}
					t.current_pos++
				}
				end_pos := t.current_pos
				tokens = append(tokens, Token{
					token_type: TOK_VARIABLE,
					lexime:     string(t.str[start_pos:end_pos]),
				})
			} else {
				panic(fmt.Errorf("Variable names cannot start with \"%v\"", string(c)))
			}
		}
	}

	tokens = append(tokens, Token{
		token_type: TOK_EOF,
		lexime:     "",
	})

	return tokens
}

util.go ASCII text

package main

func remove_at_index[T any](s []T, i int) []T {
    if i < 0 || i >= len(s) {
        return s
    }
    return append(s[:i], s[i+1:]...)
}

entry #4

written by Olek Sabak
submitted at 2026-01-03T19:01:41.605108+00:00
0 likes

guesses

Olek Sabak (by Dolphy)
Olek Sabak (by seshoumara)
Olek Sabak (by oleander)

comments 0

post a comment

dir 092

092-docs.factor ASCII text

! Copyright (C) 2026 Aleksander "olus2000" Sabak.
! See https://factorcode.org/license.txt for BSD license.
USING: bit-arrays effects help.markup help.syntax kernel quotations ;
IN: code-guessing.092

HELP: incorrect-number-of-outputs
{ $values
    { "quot" quotation } { "got" effect } { "expected" effect }
}
{ $description "Throws an " { $link incorrect-number-of-outputs } " error." }
{ $error-description "Thrown when the quotation passed to " { $link satisfy } " macro produces no outputs or more than one output." } ;

HELP: not-satisfiable
{ $values
    { "quot" quotation }
}
{ $description "Throws a " { $link not-satisfiable } " error." }
{ $error-description "Thrown when the predicate passed to " { $link satisfy } " is not satisfiable." } ;

HELP: satisfy
{ $values
    { "pred" { $quotation ( ... -- ? ) } }
    { "quot" { $quotation ( -- bit-array ) } }
}
{ $description "Compiles a " { $link bit-array } " with booleans that result in a truthy output when passed to it." }
{ $errors "Throws a " { $link incorrect-number-of-outputs } " error if " { $snippet "pred" } " produces no outputs or more than one ouput." $nl "Throws a " { $link not-satisfiable } " error if " { $snippet "pred" } " is not satisfiable." } ;

ARTICLE: "code-guessing.092" "code-guessing.092"
{ $vocab-link "code-guessing.092" } " is an implementation of a SAT solver macro for round 92 of the " { $url "https://codeguessing.gay/92/" "code guessing" } " contest." ;

ABOUT: "code-guessing.092"

092.factor ASCII text

! Copyright (C) 2026 Aleksander "olus2000" Sabak.
! See https://factorcode.org/license.txt for BSD license.
USING: accessors bit-arrays continuations effects kernel math
quotations sequences sequences.private stack-checker ;
IN: code-guessing.092


ERROR: incorrect-number-of-outputs
  { quot quotation }
  { got effect }
  { expected effect } ;

ERROR: not-satisfiable { quot quotation } ;

<PRIVATE

TUPLE: boolean-seqs bits ;

C: <boolean-seqs> boolean-seqs

INSTANCE: boolean-seqs sequence

M: boolean-seqs length bits>> 2^ ;

M: boolean-seqs nth-unsafe
  [ integer>bit-array dup length ] dip
  bits>> swap - <bit-array> prepend ;

M: boolean-seqs set-nth-unsafe immutable ;


: >expected-effect ( effect -- effect )
  in>> { "x" } clone <effect> ;

: (satisfy) ( quot -- bit-array )
  dup dup infer dup out>> length 1 =
  [ dup >expected-effect incorrect-number-of-outputs ] unless
  in>> length <boolean-seqs> swap
  [ with-datastack first ] curry find
  swap [ drop not-satisfiable ] unless
  nip ;

PRIVATE>


MACRO: satisfy ( pred -- quot ) (satisfy) 1quotation ;

authors.txt ASCII text

1	Aleksander "olus2000" Sabak

code guessing, round #92 (completed)

specification

results

entries

entry #1

post a comment

entry #2

post a comment

entry #3

post a comment

entry #4

post a comment